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, const Stmt *S,
211 const LocationContext *LCtx,
212 unsigned blockCount) {
213 auto &StateMgr = State->getStateManager();
214 auto &SymMgr = StateMgr.getSymbolManager();
215 auto &ACtx = StateMgr.getContext();
216
217 auto Sym = SymMgr.conjureSymbol(E: S, LCtx, T: ACtx.LongTy, VisitCount: blockCount);
218 State = assumeNoOverflow(State, Sym, Scale: 4);
219 return setIteratorPosition(State, Val,
220 Pos: IteratorPosition::getPosition(C: Cont, Of: Sym));
221}
222
223ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter,
224 OverloadedOperatorKind Op, SVal Distance) {
225 const auto *Pos = getIteratorPosition(State, Val: Iter);
226 if (!Pos)
227 return nullptr;
228
229 auto &SymMgr = State->getStateManager().getSymbolManager();
230 auto &SVB = State->getStateManager().getSValBuilder();
231 auto &BVF = State->getStateManager().getBasicVals();
232
233 assert ((Op == OO_Plus || Op == OO_PlusEqual ||
234 Op == OO_Minus || Op == OO_MinusEqual) &&
235 "Advance operator must be one of +, -, += and -=.");
236 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
237 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
238 if (!IntDistOp)
239 return nullptr;
240
241 // For concrete integers we can calculate the new position
242 nonloc::ConcreteInt IntDist = *IntDistOp;
243
244 if (IntDist.getValue().isNegative()) {
245 IntDist = nonloc::ConcreteInt(BVF.getValue(X: -IntDist.getValue()));
246 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
247 }
248 const auto NewPos =
249 Pos->setTo(SVB.evalBinOp(state: State, op: BinOp,
250 lhs: nonloc::SymbolVal(Pos->getOffset()),
251 rhs: IntDist, type: SymMgr.getType(SE: Pos->getOffset()))
252 .getAsSymbol());
253 return setIteratorPosition(State, Val: Iter, Pos: NewPos);
254}
255
256// This function tells the analyzer's engine that symbols produced by our
257// checker, most notably iterator positions, are relatively small.
258// A distance between items in the container should not be very large.
259// By assuming that it is within around 1/8 of the address space,
260// we can help the analyzer perform operations on these symbols
261// without being afraid of integer overflows.
262// FIXME: Should we provide it as an API, so that all checkers could use it?
263ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym,
264 long Scale) {
265 SValBuilder &SVB = State->getStateManager().getSValBuilder();
266 BasicValueFactory &BV = SVB.getBasicValueFactory();
267
268 QualType T = Sym->getType();
269 assert(T->isSignedIntegerOrEnumerationType());
270 APSIntType AT = BV.getAPSIntType(T);
271
272 ProgramStateRef NewState = State;
273
274 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(RawValue: Scale);
275 SVal IsCappedFromAbove =
276 SVB.evalBinOpNN(state: State, op: BO_LE, lhs: nonloc::SymbolVal(Sym),
277 rhs: nonloc::ConcreteInt(Max), resultTy: SVB.getConditionType());
278 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
279 NewState = NewState->assume(Cond: *DV, Assumption: true);
280 if (!NewState)
281 return State;
282 }
283
284 llvm::APSInt Min = -Max;
285 SVal IsCappedFromBelow =
286 SVB.evalBinOpNN(state: State, op: BO_GE, lhs: nonloc::SymbolVal(Sym),
287 rhs: nonloc::ConcreteInt(Min), resultTy: SVB.getConditionType());
288 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
289 NewState = NewState->assume(Cond: *DV, Assumption: true);
290 if (!NewState)
291 return State;
292 }
293
294 return NewState;
295}
296
297bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
298 BinaryOperator::Opcode Opc) {
299 return compare(State, NL1: nonloc::SymbolVal(Sym1), NL2: nonloc::SymbolVal(Sym2), Opc);
300}
301
302bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
303 BinaryOperator::Opcode Opc) {
304 auto &SVB = State->getStateManager().getSValBuilder();
305
306 const auto comparison =
307 SVB.evalBinOp(state: State, op: Opc, lhs: NL1, rhs: NL2, type: SVB.getConditionType());
308
309 assert(isa<DefinedSVal>(comparison) &&
310 "Symbol comparison must be a `DefinedSVal`");
311
312 return !State->assume(Cond: comparison.castAs<DefinedSVal>(), Assumption: false);
313}
314
315} // namespace iterator
316} // namespace ento
317} // namespace clang
318