clang 19.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 if (auto Reg = Val.getAsRegion()) {
186 Reg = Reg->getMostDerivedObjectRegion();
187 return State->get<IteratorRegionMap>(Reg);
188 } else if (const auto Sym = Val.getAsSymbol()) {
189 return State->get<IteratorSymbolMap>(Sym);
190 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
191 return State->get<IteratorRegionMap>(LCVal->getRegion());
192 }
193 return nullptr;
194}
195
197 const IteratorPosition &Pos) {
198 if (auto Reg = Val.getAsRegion()) {
199 Reg = Reg->getMostDerivedObjectRegion();
200 return State->set<IteratorRegionMap>(Reg, Pos);
201 } else if (const auto Sym = Val.getAsSymbol()) {
202 return State->set<IteratorSymbolMap>(Sym, Pos);
203 } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
204 return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
205 }
206 return nullptr;
207}
208
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(S, LCtx, ACtx.LongTy, blockCount);
218 State = assumeNoOverflow(State, Sym, 4);
219 return setIteratorPosition(State, Val,
221}
222
224 OverloadedOperatorKind Op, SVal Distance) {
225 const auto *Pos = getIteratorPosition(State, 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(-IntDist.getValue()));
246 BinOp = (BinOp == BO_Add) ? BO_Sub : BO_Add;
247 }
248 const auto NewPos =
249 Pos->setTo(SVB.evalBinOp(State, BinOp,
250 nonloc::SymbolVal(Pos->getOffset()),
251 IntDist, SymMgr.getType(Pos->getOffset()))
252 .getAsSymbol());
253 return setIteratorPosition(State, Iter, 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?
264 long Scale) {
265 SValBuilder &SVB = State->getStateManager().getSValBuilder();
267
268 QualType T = Sym->getType();
270 APSIntType AT = BV.getAPSIntType(T);
271
272 ProgramStateRef NewState = State;
273
274 llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
275 SVal IsCappedFromAbove =
276 SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
278 if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
279 NewState = NewState->assume(*DV, true);
280 if (!NewState)
281 return State;
282 }
283
284 llvm::APSInt Min = -Max;
285 SVal IsCappedFromBelow =
286 SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
288 if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
289 NewState = NewState->assume(*DV, true);
290 if (!NewState)
291 return State;
292 }
293
294 return NewState;
295}
296
299 return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
300}
301
304 auto &SVB = State->getStateManager().getSValBuilder();
305
306 const auto comparison =
307 SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
308
309 assert(isa<DefinedSVal>(comparison) &&
310 "Symbol comparison must be a `DefinedSVal`");
311
312 return !State->assume(comparison.castAs<DefinedSVal>(), false);
313}
314
315} // namespace iterator
316} // namespace ento
317} // 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:661
Represents a function declaration or definition.
Definition: Decl.h:1932
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:276
A (possibly-)qualified type.
Definition: Type.h:941
Stmt - This represents one statement.
Definition: Stmt.h:84
The base class of the type hierarchy.
Definition: Type.h:1829
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1882
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2167
bool isPointerType() const
Definition: Type.h:7996
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs,...
Definition: Type.cpp:605
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:97
BasicValueFactory & getBasicValueFactory()
Definition: SValBuilder.h:161
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:153
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:297
const llvm::APSInt & getValue() const
Definition: SVals.h:301
Represents symbolic expression that isn't a location.
Definition: SVals.h:276
bool isEraseCall(const FunctionDecl *Func)
Definition: Iterator.cpp:98
const IteratorPosition * getIteratorPosition(ProgramStateRef State, SVal Val)
Definition: Iterator.cpp:184
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
ProgramStateRef createIteratorPosition(ProgramStateRef State, SVal Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:209
bool isAccessOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:126
bool isEmplaceCall(const FunctionDecl *Func)
Definition: Iterator.cpp:87
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
Definition: Iterator.cpp:263
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
ProgramStateRef advancePosition(ProgramStateRef State, SVal Iter, OverloadedOperatorKind Op, SVal Distance)
Definition: Iterator.cpp:223
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:297
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71
ProgramStateRef setIteratorPosition(ProgramStateRef State, SVal Val, const IteratorPosition &Pos)
Definition: Iterator.cpp:196
bool isDereferenceOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:140
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
The JSON file list parser is used to communicate input to InstallAPI.
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
BinaryOperatorKind
UnaryOperatorKind
const FunctionProtoType * T
@ AS_public
Definition: Specifiers.h:121
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)
Definition: Iterator.h:50