clang 18.0.0git
Iterator.cpp
Go to the documentation of this file.
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
20 if (Type->isPointerType())
21 return true;
22
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("iterator") ||
33 Name.ends_with_insensitive("iter") || Name.ends_with_insensitive("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>(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>(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
72 return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
73 OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
74}
75
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(Func->getParamDecl(0)->getType()))
83 return false;
84 return IdInfo->getName() == "insert";
85}
86
88 const auto *IdInfo = Func->getIdentifier();
89 if (!IdInfo)
90 return false;
91 if (Func->getNumParams() < 2)
92 return false;
93 if (!isIteratorType(Func->getParamDecl(0)->getType()))
94 return false;
95 return IdInfo->getName() == "emplace";
96}
97
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(Func->getParamDecl(0)->getType()))
105 return false;
106 if (Func->getNumParams() == 2 &&
107 !isIteratorType(Func->getParamDecl(1)->getType()))
108 return false;
109 return IdInfo->getName() == "erase";
110}
111
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(Func->getParamDecl(0)->getType()))
119 return false;
120 if (Func->getNumParams() == 2 &&
121 !isIteratorType(Func->getParamDecl(1)->getType()))
122 return false;
123 return IdInfo->getName() == "erase_after";
124}
125
127 return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
129}
130
132 return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
134}
135
138}
139
141 return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
142 OK == OO_Subscript;
143}
144
146 return OK == UO_Deref;
147}
148
150 return OK == BO_PtrMemI;
151}
152
154 return OK == OO_PlusPlus;
155}
156
158 return OK == UO_PreInc || OK == UO_PostInc;
159}
160
162 return OK == OO_MinusMinus;
163}
164
166 return OK == UO_PreDec || OK == UO_PostDec;
167}
168
170 return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
171 OK == OO_MinusEqual;
172}
173
175 return OK == BO_Add || OK == BO_AddAssign ||
176 OK == BO_Sub || OK == BO_SubAssign;
177}
178
180 const MemRegion *Cont) {
181 return State->get<ContainerMap>(Cont);
182}
183
185 const SVal &Val) {
186 if (auto Reg = Val.getAsRegion()) {
187 Reg = Reg->getMostDerivedObjectRegion();
188 return State->get<IteratorRegionMap>(Reg);
189 } else if (const auto Sym = Val.getAsSymbol()) {
190 return State->get<IteratorSymbolMap>(Sym);
191 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
192 return State->get<IteratorRegionMap>(LCVal->getRegion());
193 }
194 return nullptr;
195}
196
198 const IteratorPosition &Pos) {
199 if (auto Reg = Val.getAsRegion()) {
200 Reg = Reg->getMostDerivedObjectRegion();
201 return State->set<IteratorRegionMap>(Reg, Pos);
202 } else if (const auto Sym = Val.getAsSymbol()) {
203 return State->set<IteratorSymbolMap>(Sym, Pos);
204 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
205 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
206 }
207 return nullptr;
208}
209
211 const MemRegion *Cont, const Stmt* S,
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(S, LCtx, ACtx.LongTy, blockCount);
219 State = assumeNoOverflow(State, Sym, 4);
220 return setIteratorPosition(State, Val,
222}
223
226 const SVal &Distance) {
227 const auto *Pos = getIteratorPosition(State, Iter);
228 if (!Pos)
229 return nullptr;
230
231 auto &SymMgr = State->getStateManager().getSymbolManager();
232 auto &SVB = State->getStateManager().getSValBuilder();
233 auto &BVF = State->getStateManager().getBasicVals();
234
235 assert ((Op == OO_Plus || Op == OO_PlusEqual ||
236 Op == OO_Minus || Op == OO_MinusEqual) &&
237 "Advance operator must be one of +, -, += and -=.");
238 auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
239 const auto IntDistOp = Distance.getAs<nonloc::ConcreteInt>();
240 if (!IntDistOp)
241 return nullptr;
242
243 // For concrete integers we can calculate the new position
244 nonloc::ConcreteInt IntDist = *IntDistOp;
245
246 if (IntDist.getValue().isNegative()) {
247 IntDist = nonloc::ConcreteInt(BVF.getValue(-IntDist.getValue()));
248 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
249 }
250 const auto NewPos =
251 Pos->setTo(SVB.evalBinOp(State, BinOp,
252 nonloc::SymbolVal(Pos->getOffset()),
253 IntDist, SymMgr.getType(Pos->getOffset()))
254 .getAsSymbol());
255 return setIteratorPosition(State, Iter, NewPos);
256}
257
258// This function tells the analyzer's engine that symbols produced by our
259// checker, most notably iterator positions, are relatively small.
260// A distance between items in the container should not be very large.
261// By assuming that it is within around 1/8 of the address space,
262// we can help the analyzer perform operations on these symbols
263// without being afraid of integer overflows.
264// FIXME: Should we provide it as an API, so that all checkers could use it?
266 long Scale) {
267 SValBuilder &SVB = State->getStateManager().getSValBuilder();
269
270 QualType T = Sym->getType();
272 APSIntType AT = BV.getAPSIntType(T);
273
274 ProgramStateRef NewState = State;
275
276 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
277 SVal IsCappedFromAbove =
278 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
280 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
281 NewState = NewState->assume(*DV, true);
282 if (!NewState)
283 return State;
284 }
285
286 llvm::APSInt Min = -Max;
287 SVal IsCappedFromBelow =
288 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
290 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
291 NewState = NewState->assume(*DV, true);
292 if (!NewState)
293 return State;
294 }
295
296 return NewState;
297}
298
301 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
302}
303
306 auto &SVB = State->getStateManager().getSValBuilder();
307
308 const auto comparison =
309 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
310
311 assert(isa<DefinedSVal>(comparison) &&
312 "Symbol comparison must be a `DefinedSVal`");
313
314 return !State->assume(comparison.castAs<DefinedSVal>(), false);
315}
316
317} // namespace iterator
318} // namespace ento
319} // namespace clang
unsigned Iter
Definition: HTMLLogger.cpp:154
Represents a C++ struct/union/class.
Definition: DeclCXX.h:258
method_range methods() const
Definition: DeclCXX.h:660
Represents a function declaration or definition.
Definition: Decl.h:1957
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:275
A (possibly-)qualified type.
Definition: Type.h:737
Stmt - This represents one statement.
Definition: Stmt.h:84
The base class of the type hierarchy.
Definition: Type.h:1603
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1819
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2104
bool isPointerType() const
Definition: Type.h:7032
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs,...
Definition: Type.cpp:565
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
llvm::APSInt getMaxValue() const LLVM_READONLY
Returns the maximum value for this type.
Definition: APSIntType.h:65
llvm::APSInt getValue(uint64_t RawValue) const LLVM_READONLY
Definition: APSIntType.h:69
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:96
BasicValueFactory & getBasicValueFactory()
Definition: SValBuilder.h:157
virtual SVal evalBinOpNN(ProgramStateRef state, BinaryOperator::Opcode op, NonLoc lhs, NonLoc rhs, QualType resultTy)=0
Create a new value which represents a binary expression with two non- location operands.
QualType getConditionType() const
Definition: SValBuilder.h:149
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:55
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:104
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Definition: SVals.h:86
QualType getType(const ASTContext &) const
Try to get a reasonable type for the given value.
Definition: SVals.cpp:181
const MemRegion * getAsRegion() const
Definition: SVals.cpp:120
Symbolic value.
Definition: SymExpr.h:30
virtual QualType getType() const =0
Value representing integer constant.
Definition: SVals.h:305
const llvm::APSInt & getValue() const
Definition: SVals.h:309
Represents symbolic expression that isn't a location.
Definition: SVals.h:284
bool isEraseCall(const FunctionDecl *Func)
Definition: Iterator.cpp:98
bool isIterator(const CXXRecordDecl *CRD)
Definition: Iterator.cpp:27
bool isInsertCall(const FunctionDecl *Func)
Definition: Iterator.cpp:76
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
bool isAccessOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:126
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
Definition: Iterator.cpp:224
bool isEmplaceCall(const FunctionDecl *Func)
Definition: Iterator.cpp:87
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
Definition: Iterator.cpp:265
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos)
Definition: Iterator.cpp:197
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
Definition: Iterator.cpp:179
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc)
Definition: Iterator.cpp:299
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71
bool isDereferenceOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:140
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:210
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
BinaryOperatorKind
UnaryOperatorKind
@ AS_public
Definition: Specifiers.h:119
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)
Definition: Iterator.h:50