clang  14.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 
15 namespace clang {
16 namespace ento {
17 namespace iterator {
18 
20  if (Type->isPointerType())
21  return true;
22 
23  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
24  return isIterator(CRD);
25 }
26 
27 bool isIterator(const CXXRecordDecl *CRD) {
28  if (!CRD)
29  return false;
30 
31  const auto Name = CRD->getName();
32  if (!(Name.endswith_insensitive("iterator") ||
33  Name.endswith_insensitive("iter") || Name.endswith_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 
76 bool 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(Func->getParamDecl(0)->getType()))
83  return false;
84  return IdInfo->getName() == "insert";
85 }
86 
87 bool 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(Func->getParamDecl(0)->getType()))
94  return false;
95  return IdInfo->getName() == "emplace";
96 }
97 
98 bool 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(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 
112 bool 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(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,
221  IteratorPosition::getPosition(Cont, Sym));
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(comparison.getAs<DefinedSVal>() &&
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
clang::FunctionDecl::getNumParams
unsigned getNumParams() const
Return the number of parameters this function must have based on its FunctionType.
Definition: Decl.cpp:3380
clang::ento::BasicValueFactory
Definition: BasicValueFactory.h:108
clang::ento::APSIntType::getValue
llvm::APSInt getValue(uint64_t RawValue) const LLVM_READONLY
Definition: APSIntType.h:69
clang::LocationContext
It wraps the AnalysisDeclContext to represent both the call stack with the help of StackFrameContext ...
Definition: AnalysisDeclContext.h:215
clang::ento::NonLoc
Definition: SVals.h:305
clang::ento::SVal::getAsRegion
const MemRegion * getAsRegion() const
Definition: SVals.cpp:131
clang::ento::iterator::ContainerMap
Definition: Iterator.h:116
clang::ento::iterator::isIteratorType
bool isIteratorType(const QualType &Type)
Definition: Iterator.cpp:19
clang::QualType
A (possibly-)qualified type.
Definition: Type.h:673
clang::FunctionDecl::getParamDecl
const ParmVarDecl * getParamDecl(unsigned i) const
Definition: Decl.h:2506
clang::ento::iterator::IteratorPosition
Definition: Iterator.h:26
clang::ento::nonloc::ConcreteInt
Value representing integer constant.
Definition: SVals.h:386
clang::ento::APSIntType::getMaxValue
llvm::APSInt getMaxValue() const LLVM_READONLY
Returns the maximum value for this type.
Definition: APSIntType.h:65
clang::Type
The base class of the type hierarchy.
Definition: Type.h:1490
clang::ento::SVal::getAs
Optional< T > getAs() const
Convert to the specified SVal type, returning None if this SVal is not of the desired type.
Definition: SVals.h:111
clang::ento::MemRegion
MemRegion - The root abstract class for all memory regions.
Definition: MemRegion.h:94
APSInt
llvm::APSInt APSInt
Definition: ByteCodeEmitter.cpp:19
clang::ento::DefinedSVal
Definition: SVals.h:269
clang::ento::iterator::isIterator
bool isIterator(const CXXRecordDecl *CRD)
Definition: Iterator.cpp:27
clang::ento::iterator::createIteratorPosition
ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, const MemRegion *Cont, const Stmt *S, const LocationContext *LCtx, unsigned blockCount)
Definition: Iterator.cpp:210
clang::Type::isSignedIntegerOrEnumerationType
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:2032
clang::CXXRecordDecl::methods
method_range methods() const
Definition: DeclCXX.h:631
clang::ento::SymExpr::getType
virtual QualType getType() const =0
clang::ento::iterator::isComparisonOperator
bool isComparisonOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:71
clang::AS_public
@ AS_public
Definition: Specifiers.h:109
clang::ento::iterator::assumeNoOverflow
ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
Definition: Iterator.cpp:265
clang::ento::SymExpr
Symbolic value.
Definition: SymExpr.h:29
clang::ento::iterator::getIteratorPosition
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
Definition: Iterator.cpp:184
clang::ento::iterator::isIncrementOperator
bool isIncrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:153
clang::ento::SValBuilder::getBasicValueFactory
BasicValueFactory & getBasicValueFactory()
Definition: SValBuilder.h:181
clang::ento::iterator::isDereferenceOperator
bool isDereferenceOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:140
clang::Type::getAsCXXRecordDecl
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1760
clang::ento::iterator::isEraseCall
bool isEraseCall(const FunctionDecl *Func)
Definition: Iterator.cpp:98
clang::ento::nonloc::LazyCompoundVal
Definition: SVals.h:493
clang::ento::iterator::IteratorPosition::getPosition
static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of)
Definition: Iterator.h:50
clang::ento::APSIntType
A record of the "type" of an APSInt, used for conversions.
Definition: APSIntType.h:19
clang::OverloadedOperatorKind
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:21
clang::ento::SValBuilder
Definition: SValBuilder.h:53
clang::ento::iterator::getContainerData
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
Definition: Iterator.cpp:179
clang::CXXRecordDecl
Represents a C++ struct/union/class.
Definition: DeclCXX.h:255
clang::Type::isPointerType
bool isPointerType() const
Definition: Type.h:6672
clang::NamedDecl::getIdentifier
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:270
clang::ento::SValBuilder::evalBinOpNN
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.
Iterator.h
clang::ento::iterator::IteratorSymbolMap
Definition: Iterator.h:114
State
LineState State
Definition: UnwrappedLineFormatter.cpp:986
clang::UnaryOperatorKind
UnaryOperatorKind
Definition: OperationKinds.h:30
clang::BinaryOperatorKind
BinaryOperatorKind
Definition: OperationKinds.h:25
clang::ento::iterator::ContainerData
Definition: Iterator.h:78
clang::ento::nonloc::ConcreteInt::getValue
const llvm::APSInt & getValue() const
Definition: SVals.h:390
clang::ento::iterator::compare
bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc)
Definition: Iterator.cpp:299
clang::ento::nonloc::SymbolVal
Represents symbolic expression that isn't a location.
Definition: SVals.h:356
clang::ento::iterator::isEraseAfterCall
bool isEraseAfterCall(const FunctionDecl *Func)
Definition: Iterator.cpp:112
clang::IdentifierInfo::getName
StringRef getName() const
Return the actual identifier string.
Definition: IdentifierTable.h:195
clang
Definition: CalledOnceCheck.h:17
clang::ento::iterator::isRandomIncrOrDecrOperator
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:169
clang::Stmt
Stmt - This represents one statement.
Definition: Stmt.h:69
clang::ento::iterator::isEmplaceCall
bool isEmplaceCall(const FunctionDecl *Func)
Definition: Iterator.cpp:87
clang::ento::iterator::setIteratorPosition
ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, const IteratorPosition &Pos)
Definition: Iterator.cpp:197
clang::ento::iterator::isInsertCall
bool isInsertCall(const FunctionDecl *Func)
Definition: Iterator.cpp:76
clang::Type::getUnqualifiedDesugaredType
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs,...
Definition: Type.cpp:539
clang::ento::iterator::isAccessOperator
bool isAccessOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:126
clang::ento::SVal
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
Definition: SVals.h:75
clang::ento::iterator::isDecrementOperator
bool isDecrementOperator(OverloadedOperatorKind OK)
Definition: Iterator.cpp:161
clang::ValueDecl::getType
QualType getType() const
Definition: Decl.h:687
clang::ento::SVal::getAsSymbol
SymbolRef getAsSymbol(bool IncludeBaseRegions=false) const
If this SVal wraps a symbol return that SymbolRef.
Definition: SVals.cpp:123
clang::ento::iterator::IteratorRegionMap
Definition: Iterator.h:115
clang::ento::SValBuilder::getConditionType
QualType getConditionType() const
Definition: SValBuilder.h:173
clang::FunctionDecl
Represents a function declaration or definition.
Definition: Decl.h:1856
clang::ento::BasicValueFactory::getAPSIntType
APSIntType getAPSIntType(QualType T) const
Returns the type of the APSInt used to store values of the given QualType.
Definition: BasicValueFactory.h:143
clang::ento::SVal::getType
QualType getType(const ASTContext &) const
Try to get a reasonable type for the given value.
Definition: SVals.cpp:193
llvm::IntrusiveRefCntPtr
Definition: LLVM.h:47
clang::ento::iterator::advancePosition
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
Definition: Iterator.cpp:224
clang::NamedDecl::getName
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:276