1//=== Iterator.cpp - Common functions for iterator checkers. -------*- C++ -*-//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// Defines common functions to be used by the itertor checkers .
10//
11//===----------------------------------------------------------------------===//
12
13#include "Iterator.h"
14
15namespace clang {
16namespace ento {
17namespace iterator {
18
19bool isIteratorType(const QualType &Type) {
20 if (Type->isPointerType())
21 return true;
22
23 const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24 return isIterator(CRD);
25}
26
27bool isIterator(const CXXRecordDecl *CRD) {
28 if (!CRD)
29 return false;
30
31 const auto Name = CRD->getName();
32 if (!(Name.ends_with_insensitive(Suffix: "iterator") ||
33 Name.ends_with_insensitive(Suffix: "iter") || Name.ends_with_insensitive(Suffix: "it")))
34 return false;
35
36 bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
37 HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
38 for (const auto *Method : CRD->methods()) {
39 if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Val: Method)) {
40 if (Ctor->isCopyConstructor()) {
41 HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
42 }
43 continue;
44 }
45 if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Val: Method)) {
46 HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
47 continue;
48 }
49 if (Method->isCopyAssignmentOperator()) {
50 HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
51 continue;
52 }
53 if (!Method->isOverloadedOperator())
54 continue;
55 const auto OPK = Method->getOverloadedOperator();
56 if (OPK == OO_PlusPlus) {
57 HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
58 HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
59 continue;
60 }
61 if (OPK == OO_Star) {
62 HasDerefOp = (Method->getNumParams() == 0);
63 continue;
64 }
65 }
66
67 return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
68 HasPostIncrOp && HasDerefOp;
69}
70
71bool isComparisonOperator(OverloadedOperatorKind OK) {
72 return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
73 OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
74}
75
76bool isInsertCall(const FunctionDecl *Func) {
77 const auto *IdInfo = Func->getIdentifier();
78 if (!IdInfo)
79 return false;
80 if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
81 return false;
82 if (!isIteratorType(Type: Func->getParamDecl(i: 0)->getType()))
83 return false;
84 return IdInfo->getName() == "insert";
85}
86
87bool isEmplaceCall(const FunctionDecl *Func) {
88 const auto *IdInfo = Func->getIdentifier();
89 if (!IdInfo)
90 return false;
91 if (Func->getNumParams() < 2)
92 return false;
93 if (!isIteratorType(Type: Func->getParamDecl(i: 0)->getType()))
94 return false;
95 return IdInfo->getName() == "emplace";
96}
97
98bool isEraseCall(const FunctionDecl *Func) {
99 const auto *IdInfo = Func->getIdentifier();
100 if (!IdInfo)
101 return false;
102 if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
103 return false;
104 if (!isIteratorType(Type: Func->getParamDecl(i: 0)->getType()))
105 return false;
106 if (Func->getNumParams() == 2 &&
107 !isIteratorType(Type: Func->getParamDecl(i: 1)->getType()))
108 return false;
109 return IdInfo->getName() == "erase";
110}
111
112bool isEraseAfterCall(const FunctionDecl *Func) {
113 const auto *IdInfo = Func->getIdentifier();
114 if (!IdInfo)
115 return false;
116 if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
117 return false;
118 if (!isIteratorType(Type: Func->getParamDecl(i: 0)->getType()))
119 return false;
120 if (Func->getNumParams() == 2 &&
121 !isIteratorType(Type: Func->getParamDecl(i: 1)->getType()))
122 return false;
123 return IdInfo->getName() == "erase_after";
124}
125
126bool isAccessOperator(OverloadedOperatorKind OK) {
127 return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
128 isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK);
129}
130
131bool isAccessOperator(UnaryOperatorKind OK) {
132 return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
133 isDecrementOperator(OK);
134}
135
136bool isAccessOperator(BinaryOperatorKind OK) {
137 return isDereferenceOperator(OK) || isRandomIncrOrDecrOperator(OK);
138}
139
140bool isDereferenceOperator(OverloadedOperatorKind OK) {
141 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
142 OK == OO_Subscript;
143}
144
145bool isDereferenceOperator(UnaryOperatorKind OK) {
146 return OK == UO_Deref;
147}
148
149bool isDereferenceOperator(BinaryOperatorKind OK) {
150 return OK == BO_PtrMemI;
151}
152
153bool isIncrementOperator(OverloadedOperatorKind OK) {
154 return OK == OO_PlusPlus;
155}
156
157bool isIncrementOperator(UnaryOperatorKind OK) {
158 return OK == UO_PreInc || OK == UO_PostInc;
159}
160
161bool isDecrementOperator(OverloadedOperatorKind OK) {
162 return OK == OO_MinusMinus;
163}
164
165bool isDecrementOperator(UnaryOperatorKind OK) {
166 return OK == UO_PreDec || OK == UO_PostDec;
167}
168
169bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) {
170 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
171 OK == OO_MinusEqual;
172}
173
174bool isRandomIncrOrDecrOperator(BinaryOperatorKind OK) {
175 return OK == BO_Add || OK == BO_AddAssign ||
176 OK == BO_Sub || OK == BO_SubAssign;
177}
178
179const ContainerData *getContainerData(ProgramStateRef State,
180 const MemRegion *Cont) {
181 return State->get<ContainerMap>(key: Cont);
182}
183
184const IteratorPosition *getIteratorPosition(ProgramStateRef State, SVal Val) {
185 if (auto Reg = Val.getAsRegion()) {
186 Reg = Reg->getMostDerivedObjectRegion();
187 return State->get<IteratorRegionMap>(key: Reg);
188 } else if (const auto Sym = Val.getAsSymbol()) {
189 return State->get<IteratorSymbolMap>(key: Sym);
190 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
191 return State->get<IteratorRegionMap>(key: LCVal->getRegion());
192 }
193 return nullptr;
194}
195
196ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val,
197 const IteratorPosition &Pos) {
198 if (auto Reg = Val.getAsRegion()) {
199 Reg = Reg->getMostDerivedObjectRegion();
200 return State->set<IteratorRegionMap>(K: Reg, E: Pos);
201 } else if (const auto Sym = Val.getAsSymbol()) {
202 return State->set<IteratorSymbolMap>(K: Sym, E: Pos);
203 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
204 return State->set<IteratorRegionMap>(K: LCVal->getRegion(), E: Pos);
205 }
206 return nullptr;
207}
208
209ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val,
210 const MemRegion *Cont,
211 ConstCFGElementRef Elem,
212 const LocationContext *LCtx,
213 unsigned blockCount) {
214 auto &StateMgr = State->getStateManager();
215 auto &SymMgr = StateMgr.getSymbolManager();
216 auto &ACtx = StateMgr.getContext();
217
218 auto *Sym = SymMgr.conjureSymbol(Elem, LCtx, T: ACtx.LongTy, VisitCount: blockCount);
219 State = assumeNoOverflow(State, Sym, Scale: 4);
220 return setIteratorPosition(State, Val,
221 Pos: IteratorPosition::getPosition(C: Cont, Of: Sym));
222}
223
224ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
225 OverloadedOperatorKind Op, SVal Distance) {
226 const auto *Pos = getIteratorPosition(State, Val: Iter);
227 if (!Pos)
228 return nullptr;
229
230 auto &SymMgr = State->getStateManager().getSymbolManager();
231 auto &SVB = State->getStateManager().getSValBuilder();
232 auto &BVF = State->getStateManager().getBasicVals();
233
234 assert ((Op == OO_Plus || Op == OO_PlusEqual ||
235 Op == OO_Minus || Op == OO_MinusEqual) &&
236 "Advance operator must be one of +, -, += and -=.");
237 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
238 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
239 if (!IntDistOp)
240 return nullptr;
241
242 // For concrete integers we can calculate the new position
243 nonloc::ConcreteInt IntDist = *IntDistOp;
244
245 if (IntDist.getValue()->isNegative()) {
246 IntDist = nonloc::ConcreteInt(BVF.getValue(X: -IntDist.getValue()));
247 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
248 }
249 const auto NewPos =
250 Pos->setTo(SVB.evalBinOp(state: State, op: BinOp,
251 lhs: nonloc::SymbolVal(Pos->getOffset()),
252 rhs: IntDist, type: SymMgr.getType(SE: Pos->getOffset()))
253 .getAsSymbol());
254 return setIteratorPosition(State, Val: Iter, Pos: NewPos);
255}
256
257// This function tells the analyzer's engine that symbols produced by our
258// checker, most notably iterator positions, are relatively small.
259// A distance between items in the container should not be very large.
260// By assuming that it is within around 1/8 of the address space,
261// we can help the analyzer perform operations on these symbols
262// without being afraid of integer overflows.
263// FIXME: Should we provide it as an API, so that all checkers could use it?
264ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
265 long Scale) {
266 SValBuilder &SVB = State->getStateManager().getSValBuilder();
267 BasicValueFactory &BV = SVB.getBasicValueFactory();
268
269 QualType T = Sym->getType();
270 assert(T->isSignedIntegerOrEnumerationType());
271 APSIntType AT = BV.getAPSIntType(T);
272
273 ProgramStateRef NewState = State;
274
275 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(RawValue: Scale);
276 SVal IsCappedFromAbove = SVB.evalBinOpNN(
277 state: State, op: BO_LE, lhs: nonloc::SymbolVal(Sym),
278 rhs: nonloc::ConcreteInt(BV.getValue(X: Max)), resultTy: SVB.getConditionType());
279 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
280 NewState = NewState->assume(Cond: *DV, Assumption: true);
281 if (!NewState)
282 return State;
283 }
284
285 llvm::APSInt Min = -Max;
286 SVal IsCappedFromBelow = SVB.evalBinOpNN(
287 state: State, op: BO_GE, lhs: nonloc::SymbolVal(Sym),
288 rhs: nonloc::ConcreteInt(BV.getValue(X: Min)), resultTy: SVB.getConditionType());
289 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
290 NewState = NewState->assume(Cond: *DV, Assumption: true);
291 if (!NewState)
292 return State;
293 }
294
295 return NewState;
296}
297
298bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
299 BinaryOperator::Opcode Opc) {
300 return compare(State, NL1: nonloc::SymbolVal(Sym1), NL2: nonloc::SymbolVal(Sym2), Opc);
301}
302
303bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
304 BinaryOperator::Opcode Opc) {
305 auto &SVB = State->getStateManager().getSValBuilder();
306
307 const auto comparison =
308 SVB.evalBinOp(state: State, op: Opc, lhs: NL1, rhs: NL2, type: SVB.getConditionType());
309
310 assert(isa<DefinedSVal>(comparison) &&
311 "Symbol comparison must be a `DefinedSVal`");
312
313 return !State->assume(Cond: comparison.castAs<DefinedSVal>(), Assumption: false);
314}
315
316} // namespace iterator
317} // namespace ento
318} // namespace clang
319