Iterator.h
5.59 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
//=== Iterator.h - Common functions for iterator checkers. ---------*- C++ -*-//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Defines common functions to be used by the itertor checkers .
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
#define LLVM_CLANG_LIB_STATICANALYZER_CHECKERS_ITERATOR_H
#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
namespace clang {
namespace ento {
namespace iterator {
// Abstract position of an iterator. This helps to handle all three kinds
// of operators in a common way by using a symbolic position.
struct IteratorPosition {
private:
// Container the iterator belongs to
const MemRegion *Cont;
// Whether iterator is valid
const bool Valid;
// Abstract offset
const SymbolRef Offset;
IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
: Cont(C), Valid(V), Offset(Of) {}
public:
const MemRegion *getContainer() const { return Cont; }
bool isValid() const { return Valid; }
SymbolRef getOffset() const { return Offset; }
IteratorPosition invalidate() const {
return IteratorPosition(Cont, false, Offset);
}
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
return IteratorPosition(C, true, Of);
}
IteratorPosition setTo(SymbolRef NewOf) const {
return IteratorPosition(Cont, Valid, NewOf);
}
IteratorPosition reAssign(const MemRegion *NewCont) const {
return IteratorPosition(NewCont, Valid, Offset);
}
bool operator==(const IteratorPosition &X) const {
return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
}
bool operator!=(const IteratorPosition &X) const {
return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
}
void Profile(llvm::FoldingSetNodeID &ID) const {
ID.AddPointer(Cont);
ID.AddInteger(Valid);
ID.Add(Offset);
}
};
// Structure to record the symbolic begin and end position of a container
struct ContainerData {
private:
const SymbolRef Begin, End;
ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
public:
static ContainerData fromBegin(SymbolRef B) {
return ContainerData(B, nullptr);
}
static ContainerData fromEnd(SymbolRef E) {
return ContainerData(nullptr, E);
}
SymbolRef getBegin() const { return Begin; }
SymbolRef getEnd() const { return End; }
ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
bool operator==(const ContainerData &X) const {
return Begin == X.Begin && End == X.End;
}
bool operator!=(const ContainerData &X) const {
return Begin != X.Begin || End != X.End;
}
void Profile(llvm::FoldingSetNodeID &ID) const {
ID.Add(Begin);
ID.Add(End);
}
};
class IteratorSymbolMap {};
class IteratorRegionMap {};
class ContainerMap {};
using IteratorSymbolMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(SymbolRef, IteratorPosition);
using IteratorRegionMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, IteratorPosition);
using ContainerMapTy = CLANG_ENTO_PROGRAMSTATE_MAP(const MemRegion *, ContainerData);
} // namespace iterator
template<>
struct ProgramStateTrait<iterator::IteratorSymbolMap>
: public ProgramStatePartialTrait<iterator::IteratorSymbolMapTy> {
static void *GDMIndex() { static int Index; return &Index; }
};
template<>
struct ProgramStateTrait<iterator::IteratorRegionMap>
: public ProgramStatePartialTrait<iterator::IteratorRegionMapTy> {
static void *GDMIndex() { static int Index; return &Index; }
};
template<>
struct ProgramStateTrait<iterator::ContainerMap>
: public ProgramStatePartialTrait<iterator::ContainerMapTy> {
static void *GDMIndex() { static int Index; return &Index; }
};
namespace iterator {
bool isIteratorType(const QualType &Type);
bool isIterator(const CXXRecordDecl *CRD);
bool isComparisonOperator(OverloadedOperatorKind OK);
bool isInsertCall(const FunctionDecl *Func);
bool isEraseCall(const FunctionDecl *Func);
bool isEraseAfterCall(const FunctionDecl *Func);
bool isEmplaceCall(const FunctionDecl *Func);
bool isAccessOperator(OverloadedOperatorKind OK);
bool isDereferenceOperator(OverloadedOperatorKind OK);
bool isIncrementOperator(OverloadedOperatorKind OK);
bool isDecrementOperator(OverloadedOperatorKind OK);
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK);
const ContainerData *getContainerData(ProgramStateRef State,
const MemRegion *Cont);
const IteratorPosition *getIteratorPosition(ProgramStateRef State,
const SVal &Val);
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
const IteratorPosition &Pos);
ProgramStateRef advancePosition(ProgramStateRef State,
const SVal &Iter,
OverloadedOperatorKind Op,
const SVal &Distance);
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
BinaryOperator::Opcode Opc);
bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
BinaryOperator::Opcode Opc);
} // namespace iterator
} // namespace ento
} // namespace clang
#endif