clang  8.0.0svn
IteratorChecker.cpp
Go to the documentation of this file.
1 //===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Defines a checker for using iterators outside their range (past end). Usage
11 // means here dereferencing, incrementing etc.
12 //
13 //===----------------------------------------------------------------------===//
14 //
15 // In the code, iterator can be represented as a:
16 // * type-I: typedef-ed pointer. Operations over such iterator, such as
17 // comparisons or increments, are modeled straightforwardly by the
18 // analyzer.
19 // * type-II: structure with its method bodies available. Operations over such
20 // iterator are inlined by the analyzer, and results of modeling
21 // these operations are exposing implementation details of the
22 // iterators, which is not necessarily helping.
23 // * type-III: completely opaque structure. Operations over such iterator are
24 // modeled conservatively, producing conjured symbols everywhere.
25 //
26 // To handle all these types in a common way we introduce a structure called
27 // IteratorPosition which is an abstraction of the position the iterator
28 // represents using symbolic expressions. The checker handles all the
29 // operations on this structure.
30 //
31 // Additionally, depending on the circumstances, operators of types II and III
32 // can be represented as:
33 // * type-IIa, type-IIIa: conjured structure symbols - when returned by value
34 // from conservatively evaluated methods such as
35 // `.begin()`.
36 // * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as
37 // variables or temporaries, when the iterator object is
38 // currently treated as an lvalue.
39 // * type-IIc, type-IIIc: compound values of iterator-typed objects, when the
40 // iterator object is treated as an rvalue taken of a
41 // particular lvalue, eg. a copy of "type-a" iterator
42 // object, or an iterator that existed before the
43 // analysis has started.
44 //
45 // To handle any of these three different representations stored in an SVal we
46 // use setter and getters functions which separate the three cases. To store
47 // them we use a pointer union of symbol and memory region.
48 //
49 // The checker works the following way: We record the begin and the
50 // past-end iterator for all containers whenever their `.begin()` and `.end()`
51 // are called. Since the Constraint Manager cannot handle such SVals we need
52 // to take over its role. We post-check equality and non-equality comparisons
53 // and record that the two sides are equal if we are in the 'equal' branch
54 // (true-branch for `==` and false-branch for `!=`).
55 //
56 // In case of type-I or type-II iterators we get a concrete integer as a result
57 // of the comparison (1 or 0) but in case of type-III we only get a Symbol. In
58 // this latter case we record the symbol and reload it in evalAssume() and do
59 // the propagation there. We also handle (maybe double) negated comparisons
60 // which are represented in the form of (x == 0 or x != 0) where x is the
61 // comparison itself.
62 //
63 // Since `SimpleConstraintManager` cannot handle complex symbolic expressions
64 // we only use expressions of the format S, S+n or S-n for iterator positions
65 // where S is a conjured symbol and n is an unsigned concrete integer. When
66 // making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as
67 // a constraint which we later retrieve when doing an actual comparison.
68 
69 #include "ClangSACheckers.h"
70 #include "clang/AST/DeclTemplate.h"
76 
77 #include <utility>
78 
79 using namespace clang;
80 using namespace ento;
81 
82 namespace {
83 
84 // Abstract position of an iterator. This helps to handle all three kinds
85 // of operators in a common way by using a symbolic position.
86 struct IteratorPosition {
87 private:
88 
89  // Container the iterator belongs to
90  const MemRegion *Cont;
91 
92  // Whether iterator is valid
93  const bool Valid;
94 
95  // Abstract offset
96  const SymbolRef Offset;
97 
98  IteratorPosition(const MemRegion *C, bool V, SymbolRef Of)
99  : Cont(C), Valid(V), Offset(Of) {}
100 
101 public:
102  const MemRegion *getContainer() const { return Cont; }
103  bool isValid() const { return Valid; }
104  SymbolRef getOffset() const { return Offset; }
105 
106  IteratorPosition invalidate() const {
107  return IteratorPosition(Cont, false, Offset);
108  }
109 
110  static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) {
111  return IteratorPosition(C, true, Of);
112  }
113 
114  IteratorPosition setTo(SymbolRef NewOf) const {
115  return IteratorPosition(Cont, Valid, NewOf);
116  }
117 
118  IteratorPosition reAssign(const MemRegion *NewCont) const {
119  return IteratorPosition(NewCont, Valid, Offset);
120  }
121 
122  bool operator==(const IteratorPosition &X) const {
123  return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset;
124  }
125 
126  bool operator!=(const IteratorPosition &X) const {
127  return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset;
128  }
129 
130  void Profile(llvm::FoldingSetNodeID &ID) const {
131  ID.AddPointer(Cont);
132  ID.AddInteger(Valid);
133  ID.Add(Offset);
134  }
135 };
136 
137 typedef llvm::PointerUnion<const MemRegion *, SymbolRef> RegionOrSymbol;
138 
139 // Structure to record the symbolic begin and end position of a container
140 struct ContainerData {
141 private:
142  const SymbolRef Begin, End;
143 
144  ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {}
145 
146 public:
147  static ContainerData fromBegin(SymbolRef B) {
148  return ContainerData(B, nullptr);
149  }
150 
151  static ContainerData fromEnd(SymbolRef E) {
152  return ContainerData(nullptr, E);
153  }
154 
155  SymbolRef getBegin() const { return Begin; }
156  SymbolRef getEnd() const { return End; }
157 
158  ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); }
159 
160  ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); }
161 
162  bool operator==(const ContainerData &X) const {
163  return Begin == X.Begin && End == X.End;
164  }
165 
166  bool operator!=(const ContainerData &X) const {
167  return Begin != X.Begin || End != X.End;
168  }
169 
170  void Profile(llvm::FoldingSetNodeID &ID) const {
171  ID.Add(Begin);
172  ID.Add(End);
173  }
174 };
175 
176 // Structure fo recording iterator comparisons. We needed to retrieve the
177 // original comparison expression in assumptions.
178 struct IteratorComparison {
179 private:
180  RegionOrSymbol Left, Right;
181  bool Equality;
182 
183 public:
184  IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq)
185  : Left(L), Right(R), Equality(Eq) {}
186 
187  RegionOrSymbol getLeft() const { return Left; }
188  RegionOrSymbol getRight() const { return Right; }
189  bool isEquality() const { return Equality; }
190  bool operator==(const IteratorComparison &X) const {
191  return Left == X.Left && Right == X.Right && Equality == X.Equality;
192  }
193  bool operator!=(const IteratorComparison &X) const {
194  return Left != X.Left || Right != X.Right || Equality != X.Equality;
195  }
196  void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); }
197 };
198 
199 class IteratorChecker
200  : public Checker<check::PreCall, check::PostCall,
201  check::PostStmt<MaterializeTemporaryExpr>, check::Bind,
202  check::LiveSymbols, check::DeadSymbols,
203  eval::Assume> {
204 
205  std::unique_ptr<BugType> OutOfRangeBugType;
206  std::unique_ptr<BugType> MismatchedBugType;
207  std::unique_ptr<BugType> InvalidatedBugType;
208 
209  void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal,
210  const SVal &RVal, OverloadedOperatorKind Op) const;
211  void verifyAccess(CheckerContext &C, const SVal &Val) const;
212  void verifyDereference(CheckerContext &C, const SVal &Val) const;
213  void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
214  bool Postfix) const;
215  void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter,
216  bool Postfix) const;
217  void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
218  const SVal &RetVal, const SVal &LHS,
219  const SVal &RHS) const;
220  void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal,
221  const SVal &Cont) const;
222  void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal,
223  const SVal &Cont) const;
224  void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal,
225  const MemRegion *Cont) const;
226  void handleAssign(CheckerContext &C, const SVal &Cont,
227  const Expr *CE = nullptr,
228  const SVal &OldCont = UndefinedVal()) const;
229  void handleClear(CheckerContext &C, const SVal &Cont) const;
230  void handlePushBack(CheckerContext &C, const SVal &Cont) const;
231  void handlePopBack(CheckerContext &C, const SVal &Cont) const;
232  void handlePushFront(CheckerContext &C, const SVal &Cont) const;
233  void handlePopFront(CheckerContext &C, const SVal &Cont) const;
234  void handleInsert(CheckerContext &C, const SVal &Iter) const;
235  void handleErase(CheckerContext &C, const SVal &Iter) const;
236  void handleErase(CheckerContext &C, const SVal &Iter1,
237  const SVal &Iter2) const;
238  void handleEraseAfter(CheckerContext &C, const SVal &Iter) const;
239  void handleEraseAfter(CheckerContext &C, const SVal &Iter1,
240  const SVal &Iter2) const;
241  void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
242  const SVal &RetVal, const SVal &LHS,
243  const SVal &RHS) const;
244  void verifyMatch(CheckerContext &C, const SVal &Iter,
245  const MemRegion *Cont) const;
246  void verifyMatch(CheckerContext &C, const SVal &Iter1,
247  const SVal &Iter2) const;
248 
249  void reportOutOfRangeBug(const StringRef &Message, const SVal &Val,
250  CheckerContext &C, ExplodedNode *ErrNode) const;
251  void reportMismatchedBug(const StringRef &Message, const SVal &Val1,
252  const SVal &Val2, CheckerContext &C,
253  ExplodedNode *ErrNode) const;
254  void reportMismatchedBug(const StringRef &Message, const SVal &Val,
255  const MemRegion *Reg, CheckerContext &C,
256  ExplodedNode *ErrNode) const;
257  void reportInvalidatedBug(const StringRef &Message, const SVal &Val,
258  CheckerContext &C, ExplodedNode *ErrNode) const;
259 
260 public:
261  IteratorChecker();
262 
263  enum CheckKind {
264  CK_IteratorRangeChecker,
265  CK_MismatchedIteratorChecker,
266  CK_InvalidatedIteratorChecker,
267  CK_NumCheckKinds
268  };
269 
270  DefaultBool ChecksEnabled[CK_NumCheckKinds];
271  CheckName CheckNames[CK_NumCheckKinds];
272 
273  void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
274  void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
275  void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const;
276  void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const;
277  void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const;
278  void checkPostStmt(const MaterializeTemporaryExpr *MTE,
279  CheckerContext &C) const;
280  void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
281  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
282  ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond,
283  bool Assumption) const;
284 };
285 } // namespace
286 
287 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition)
288 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *,
289  IteratorPosition)
290 
291 REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData)
292 
293 REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *,
295 
296 namespace {
297 
298 bool isIteratorType(const QualType &Type);
299 bool isIterator(const CXXRecordDecl *CRD);
301 bool isBeginCall(const FunctionDecl *Func);
302 bool isEndCall(const FunctionDecl *Func);
303 bool isAssignCall(const FunctionDecl *Func);
304 bool isClearCall(const FunctionDecl *Func);
305 bool isPushBackCall(const FunctionDecl *Func);
306 bool isEmplaceBackCall(const FunctionDecl *Func);
307 bool isPopBackCall(const FunctionDecl *Func);
308 bool isPushFrontCall(const FunctionDecl *Func);
309 bool isEmplaceFrontCall(const FunctionDecl *Func);
310 bool isPopFrontCall(const FunctionDecl *Func);
311 bool isInsertCall(const FunctionDecl *Func);
312 bool isEraseCall(const FunctionDecl *Func);
313 bool isEraseAfterCall(const FunctionDecl *Func);
314 bool isEmplaceCall(const FunctionDecl *Func);
322 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
323 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
324 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
325 BinaryOperator::Opcode getOpcode(const SymExpr *SE);
326 const RegionOrSymbol getRegionOrSymbol(const SVal &Val);
328  RegionOrSymbol LVal,
329  RegionOrSymbol RVal, bool Equal);
331  const SymExpr *Condition, const SVal &LVal,
332  const SVal &RVal, bool Eq);
334  const SymExpr *Condition);
335 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
336 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
338  const MemRegion *Cont,
339  const SymbolRef Sym);
340 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
341  const SymbolRef Sym);
342 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
343  const SVal &Val);
344 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
345  RegionOrSymbol RegOrSym);
347  const IteratorPosition &Pos);
349  RegionOrSymbol RegOrSym,
350  const IteratorPosition &Pos);
353  RegionOrSymbol RegOrSym,
354  const IteratorPosition &Pos, bool Equal);
356  const IteratorPosition &Pos1,
357  const IteratorPosition &Pos2,
358  bool Equal);
360  const MemRegion *Cont);
363  const MemRegion *Cont, SymbolRef Offset,
366  SymbolRef Offset,
369  SymbolRef Offset1,
371  SymbolRef Offset2,
374  const MemRegion *Cont,
375  const MemRegion *NewCont);
377  const MemRegion *Cont,
378  const MemRegion *NewCont,
379  SymbolRef Offset,
382  ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
383  SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
384 const ContainerData *getContainerData(ProgramStateRef State,
385  const MemRegion *Cont);
386 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
387  const ContainerData &CData);
388 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
389 bool isBoundThroughLazyCompoundVal(const Environment &Env,
390  const MemRegion *Reg);
391 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos);
392 bool isZero(ProgramStateRef State, const NonLoc &Val);
393 } // namespace
394 
395 IteratorChecker::IteratorChecker() {
396  OutOfRangeBugType.reset(
397  new BugType(this, "Iterator out of range", "Misuse of STL APIs"));
398  OutOfRangeBugType->setSuppressOnSink(true);
399  MismatchedBugType.reset(
400  new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs"));
401  MismatchedBugType->setSuppressOnSink(true);
402  InvalidatedBugType.reset(
403  new BugType(this, "Iterator invalidated", "Misuse of STL APIs"));
404  InvalidatedBugType->setSuppressOnSink(true);
405 }
406 
407 void IteratorChecker::checkPreCall(const CallEvent &Call,
408  CheckerContext &C) const {
409  // Check for out of range access or access of invalidated position and
410  // iterator mismatches
411  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
412  if (!Func)
413  return;
414 
415  if (Func->isOverloadedOperator()) {
416  if (ChecksEnabled[CK_InvalidatedIteratorChecker] &&
417  isAccessOperator(Func->getOverloadedOperator())) {
418  // Check for any kind of access of invalidated iterator positions
419  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
420  verifyAccess(C, InstCall->getCXXThisVal());
421  } else {
422  verifyAccess(C, Call.getArgSVal(0));
423  }
424  }
425  if (ChecksEnabled[CK_IteratorRangeChecker] &&
426  isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
427  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
428  // Check for out-of-range incrementions and decrementions
429  if (Call.getNumArgs() >= 1) {
430  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
431  Call.getReturnValue(),
432  InstCall->getCXXThisVal(), Call.getArgSVal(0));
433  }
434  } else {
435  if (Call.getNumArgs() >= 2) {
436  verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
437  Call.getReturnValue(), Call.getArgSVal(0),
438  Call.getArgSVal(1));
439  }
440  }
441  } else if (ChecksEnabled[CK_IteratorRangeChecker] &&
442  isDereferenceOperator(Func->getOverloadedOperator())) {
443  // Check for dereference of out-of-range iterators
444  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
445  verifyDereference(C, InstCall->getCXXThisVal());
446  } else {
447  verifyDereference(C, Call.getArgSVal(0));
448  }
449  } else if (ChecksEnabled[CK_MismatchedIteratorChecker] &&
450  isComparisonOperator(Func->getOverloadedOperator())) {
451  // Check for comparisons of iterators of different containers
452  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
453  if (Call.getNumArgs() < 1)
454  return;
455 
456  if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) ||
457  !isIteratorType(Call.getArgExpr(0)->getType()))
458  return;
459 
460  verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
461  } else {
462  if (Call.getNumArgs() < 2)
463  return;
464 
465  if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
466  !isIteratorType(Call.getArgExpr(1)->getType()))
467  return;
468 
469  verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
470  }
471  }
472  } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
473  if (!ChecksEnabled[CK_MismatchedIteratorChecker])
474  return;
475 
476  const auto *ContReg = InstCall->getCXXThisVal().getAsRegion();
477  if (!ContReg)
478  return;
479  // Check for erase, insert and emplace using iterator of another container
480  if (isEraseCall(Func) || isEraseAfterCall(Func)) {
481  verifyMatch(C, Call.getArgSVal(0),
482  InstCall->getCXXThisVal().getAsRegion());
483  if (Call.getNumArgs() == 2) {
484  verifyMatch(C, Call.getArgSVal(1),
485  InstCall->getCXXThisVal().getAsRegion());
486  }
487  } else if (isInsertCall(Func)) {
488  verifyMatch(C, Call.getArgSVal(0),
489  InstCall->getCXXThisVal().getAsRegion());
490  if (Call.getNumArgs() == 3 &&
491  isIteratorType(Call.getArgExpr(1)->getType()) &&
492  isIteratorType(Call.getArgExpr(2)->getType())) {
493  verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2));
494  }
495  } else if (isEmplaceCall(Func)) {
496  verifyMatch(C, Call.getArgSVal(0),
497  InstCall->getCXXThisVal().getAsRegion());
498  }
499  } else if (isa<CXXConstructorCall>(&Call)) {
500  // Check match of first-last iterator pair in a constructor of a container
501  if (Call.getNumArgs() < 2)
502  return;
503 
504  const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl());
505  if (Ctr->getNumParams() < 2)
506  return;
507 
508  if (Ctr->getParamDecl(0)->getName() != "first" ||
509  Ctr->getParamDecl(1)->getName() != "last")
510  return;
511 
512  if (!isIteratorType(Call.getArgExpr(0)->getType()) ||
513  !isIteratorType(Call.getArgExpr(1)->getType()))
514  return;
515 
516  verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1));
517  } else {
518  // The main purpose of iterators is to abstract away from different
519  // containers and provide a (maybe limited) uniform access to them.
520  // This implies that any correctly written template function that
521  // works on multiple containers using iterators takes different
522  // template parameters for different containers. So we can safely
523  // assume that passing iterators of different containers as arguments
524  // whose type replaces the same template parameter is a bug.
525  //
526  // Example:
527  // template<typename I1, typename I2>
528  // void f(I1 first1, I1 last1, I2 first2, I2 last2);
529  //
530  // In this case the first two arguments to f() must be iterators must belong
531  // to the same container and the last to also to the same container but
532  // not neccessarily to the same as the first two.
533 
534  if (!ChecksEnabled[CK_MismatchedIteratorChecker])
535  return;
536 
537  const auto *Templ = Func->getPrimaryTemplate();
538  if (!Templ)
539  return;
540 
541  const auto *TParams = Templ->getTemplateParameters();
542  const auto *TArgs = Func->getTemplateSpecializationArgs();
543 
544  // Iterate over all the template parameters
545  for (size_t I = 0; I < TParams->size(); ++I) {
546  const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I));
547  if (!TPDecl)
548  continue;
549 
550  if (TPDecl->isParameterPack())
551  continue;
552 
553  const auto TAType = TArgs->get(I).getAsType();
554  if (!isIteratorType(TAType))
555  continue;
556 
557  SVal LHS = UndefinedVal();
558 
559  // For every template parameter which is an iterator type in the
560  // instantiation look for all functions' parameters' type by it and
561  // check whether they belong to the same container
562  for (auto J = 0U; J < Func->getNumParams(); ++J) {
563  const auto *Param = Func->getParamDecl(J);
564  const auto *ParamType =
565  Param->getType()->getAs<SubstTemplateTypeParmType>();
566  if (!ParamType ||
567  ParamType->getReplacedParameter()->getDecl() != TPDecl)
568  continue;
569  if (LHS.isUndef()) {
570  LHS = Call.getArgSVal(J);
571  } else {
572  verifyMatch(C, LHS, Call.getArgSVal(J));
573  }
574  }
575  }
576  }
577 }
578 
579 void IteratorChecker::checkPostCall(const CallEvent &Call,
580  CheckerContext &C) const {
581  // Record new iterator positions and iterator position changes
582  const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
583  if (!Func)
584  return;
585 
586  if (Func->isOverloadedOperator()) {
587  const auto Op = Func->getOverloadedOperator();
588  if (isAssignmentOperator(Op)) {
589  const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
590  if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) {
591  handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
592  Call.getArgSVal(0));
593  } else {
594  handleAssign(C, InstCall->getCXXThisVal());
595  }
596  } else if (isSimpleComparisonOperator(Op)) {
597  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
598  handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
599  Call.getArgSVal(0), Op);
600  } else {
601  handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0),
602  Call.getArgSVal(1), Op);
603  }
604  } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) {
605  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
606  if (Call.getNumArgs() >= 1) {
607  handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
608  Call.getReturnValue(),
609  InstCall->getCXXThisVal(), Call.getArgSVal(0));
610  }
611  } else {
612  if (Call.getNumArgs() >= 2) {
613  handleRandomIncrOrDecr(C, Func->getOverloadedOperator(),
614  Call.getReturnValue(), Call.getArgSVal(0),
615  Call.getArgSVal(1));
616  }
617  }
618  } else if (isIncrementOperator(Func->getOverloadedOperator())) {
619  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
620  handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
621  Call.getNumArgs());
622  } else {
623  handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0),
624  Call.getNumArgs());
625  }
626  } else if (isDecrementOperator(Func->getOverloadedOperator())) {
627  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
628  handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(),
629  Call.getNumArgs());
630  } else {
631  handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0),
632  Call.getNumArgs());
633  }
634  }
635  } else {
636  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
637  if (isAssignCall(Func)) {
638  handleAssign(C, InstCall->getCXXThisVal());
639  } else if (isClearCall(Func)) {
640  handleClear(C, InstCall->getCXXThisVal());
641  } else if (isPushBackCall(Func) || isEmplaceBackCall(Func)) {
642  handlePushBack(C, InstCall->getCXXThisVal());
643  } else if (isPopBackCall(Func)) {
644  handlePopBack(C, InstCall->getCXXThisVal());
645  } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) {
646  handlePushFront(C, InstCall->getCXXThisVal());
647  } else if (isPopFrontCall(Func)) {
648  handlePopFront(C, InstCall->getCXXThisVal());
649  } else if (isInsertCall(Func) || isEmplaceCall(Func)) {
650  handleInsert(C, Call.getArgSVal(0));
651  } else if (isEraseCall(Func)) {
652  if (Call.getNumArgs() == 1) {
653  handleErase(C, Call.getArgSVal(0));
654  } else if (Call.getNumArgs() == 2) {
655  handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1));
656  }
657  } else if (isEraseAfterCall(Func)) {
658  if (Call.getNumArgs() == 1) {
659  handleEraseAfter(C, Call.getArgSVal(0));
660  } else if (Call.getNumArgs() == 2) {
661  handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1));
662  }
663  }
664  }
665 
666  const auto *OrigExpr = Call.getOriginExpr();
667  if (!OrigExpr)
668  return;
669 
670  if (!isIteratorType(Call.getResultType()))
671  return;
672 
673  auto State = C.getState();
674 
675  if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
676  if (isBeginCall(Func)) {
677  handleBegin(C, OrigExpr, Call.getReturnValue(),
678  InstCall->getCXXThisVal());
679  return;
680  }
681  if (isEndCall(Func)) {
682  handleEnd(C, OrigExpr, Call.getReturnValue(),
683  InstCall->getCXXThisVal());
684  return;
685  }
686  }
687 
688  // Already bound to container?
689  if (getIteratorPosition(State, Call.getReturnValue()))
690  return;
691 
692  // Copy-like and move constructors
693  if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) {
694  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) {
695  State = setIteratorPosition(State, Call.getReturnValue(), *Pos);
696  if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) {
697  State = removeIteratorPosition(State, Call.getArgSVal(0));
698  }
699  C.addTransition(State);
700  return;
701  }
702  }
703 
704  // Assumption: if return value is an iterator which is not yet bound to a
705  // container, then look for the first iterator argument, and
706  // bind the return value to the same container. This approach
707  // works for STL algorithms.
708  // FIXME: Add a more conservative mode
709  for (unsigned i = 0; i < Call.getNumArgs(); ++i) {
710  if (isIteratorType(Call.getArgExpr(i)->getType())) {
711  if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) {
712  assignToContainer(C, OrigExpr, Call.getReturnValue(),
713  Pos->getContainer());
714  return;
715  }
716  }
717  }
718  }
719 }
720 
721 void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S,
722  CheckerContext &C) const {
723  auto State = C.getState();
724  const auto *Pos = getIteratorPosition(State, Val);
725  if (Pos) {
726  State = setIteratorPosition(State, Loc, *Pos);
727  C.addTransition(State);
728  } else {
729  const auto *OldPos = getIteratorPosition(State, Loc);
730  if (OldPos) {
732  C.addTransition(State);
733  }
734  }
735 }
736 
737 void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE,
738  CheckerContext &C) const {
739  /* Transfer iterator state to temporary objects */
740  auto State = C.getState();
741  const auto *Pos =
742  getIteratorPosition(State, C.getSVal(MTE->GetTemporaryExpr()));
743  if (!Pos)
744  return;
745  State = setIteratorPosition(State, C.getSVal(MTE), *Pos);
746  C.addTransition(State);
747 }
748 
749 void IteratorChecker::checkLiveSymbols(ProgramStateRef State,
750  SymbolReaper &SR) const {
751  // Keep symbolic expressions of iterator positions, container begins and ends
752  // alive
753  auto RegionMap = State->get<IteratorRegionMap>();
754  for (const auto Reg : RegionMap) {
755  const auto Offset = Reg.second.getOffset();
756  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
757  if (isa<SymbolData>(*i))
758  SR.markLive(*i);
759  }
760 
761  auto SymbolMap = State->get<IteratorSymbolMap>();
762  for (const auto Sym : SymbolMap) {
763  const auto Offset = Sym.second.getOffset();
764  for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i)
765  if (isa<SymbolData>(*i))
766  SR.markLive(*i);
767  }
768 
769  auto ContMap = State->get<ContainerMap>();
770  for (const auto Cont : ContMap) {
771  const auto CData = Cont.second;
772  if (CData.getBegin()) {
773  SR.markLive(CData.getBegin());
774  if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
775  SR.markLive(SIE->getLHS());
776  }
777  if (CData.getEnd()) {
778  SR.markLive(CData.getEnd());
779  if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
780  SR.markLive(SIE->getLHS());
781  }
782  }
783 }
784 
785 void IteratorChecker::checkDeadSymbols(SymbolReaper &SR,
786  CheckerContext &C) const {
787  // Cleanup
788  auto State = C.getState();
789 
790  auto RegionMap = State->get<IteratorRegionMap>();
791  for (const auto Reg : RegionMap) {
792  if (!SR.isLiveRegion(Reg.first)) {
793  // The region behind the `LazyCompoundVal` is often cleaned up before
794  // the `LazyCompoundVal` itself. If there are iterator positions keyed
795  // by these regions their cleanup must be deferred.
796  if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) {
797  State = State->remove<IteratorRegionMap>(Reg.first);
798  }
799  }
800  }
801 
802  auto SymbolMap = State->get<IteratorSymbolMap>();
803  for (const auto Sym : SymbolMap) {
804  if (!SR.isLive(Sym.first)) {
805  State = State->remove<IteratorSymbolMap>(Sym.first);
806  }
807  }
808 
809  auto ContMap = State->get<ContainerMap>();
810  for (const auto Cont : ContMap) {
811  if (!SR.isLiveRegion(Cont.first)) {
812  // We must keep the container data while it has live iterators to be able
813  // to compare them to the begin and the end of the container.
814  if (!hasLiveIterators(State, Cont.first)) {
815  State = State->remove<ContainerMap>(Cont.first);
816  }
817  }
818  }
819 
820  auto ComparisonMap = State->get<IteratorComparisonMap>();
821  for (const auto Comp : ComparisonMap) {
822  if (!SR.isLive(Comp.first)) {
823  State = State->remove<IteratorComparisonMap>(Comp.first);
824  }
825  }
826 
827  C.addTransition(State);
828 }
829 
830 ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond,
831  bool Assumption) const {
832  // Load recorded comparison and transfer iterator state between sides
833  // according to comparison operator and assumption
834  const auto *SE = Cond.getAsSymExpr();
835  if (!SE)
836  return State;
837 
838  auto Opc = getOpcode(SE);
839  if (Opc != BO_EQ && Opc != BO_NE)
840  return State;
841 
842  bool Negated = false;
843  const auto *Comp = loadComparison(State, SE);
844  if (!Comp) {
845  // Try negated comparison, which is a SymExpr to 0 integer comparison
846  const auto *SIE = dyn_cast<SymIntExpr>(SE);
847  if (!SIE)
848  return State;
849 
850  if (SIE->getRHS() != 0)
851  return State;
852 
853  SE = SIE->getLHS();
854  Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation
855  Opc = getOpcode(SE);
856  if (Opc != BO_EQ && Opc != BO_NE)
857  return State;
858 
859  Comp = loadComparison(State, SE);
860  if (!Comp)
861  return State;
862  }
863 
864  return processComparison(State, Comp->getLeft(), Comp->getRight(),
865  (Comp->isEquality() == Assumption) != Negated);
866 }
867 
868 void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal,
869  const SVal &LVal, const SVal &RVal,
870  OverloadedOperatorKind Op) const {
871  // Record the operands and the operator of the comparison for the next
872  // evalAssume, if the result is a symbolic expression. If it is a concrete
873  // value (only one branch is possible), then transfer the state between
874  // the operands according to the operator and the result
875  auto State = C.getState();
876  if (const auto *Condition = RetVal.getAsSymbolicExpression()) {
877  const auto *LPos = getIteratorPosition(State, LVal);
878  const auto *RPos = getIteratorPosition(State, RVal);
879  if (!LPos && !RPos)
880  return;
881  State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual);
882  C.addTransition(State);
883  } else if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) {
884  if ((State = processComparison(
885  State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal),
886  (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) {
887  C.addTransition(State);
888  } else {
889  C.generateSink(State, C.getPredecessor());
890  }
891  }
892 }
893 
894 void IteratorChecker::verifyDereference(CheckerContext &C,
895  const SVal &Val) const {
896  auto State = C.getState();
897  const auto *Pos = getIteratorPosition(State, Val);
898  if (Pos && isOutOfRange(State, *Pos)) {
899  auto *N = C.generateNonFatalErrorNode(State);
900  if (!N)
901  return;
902  reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N);
903  }
904 }
905 
906 void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const {
907  auto State = C.getState();
908  const auto *Pos = getIteratorPosition(State, Val);
909  if (Pos && !Pos->isValid()) {
910  auto *N = C.generateNonFatalErrorNode(State);
911  if (!N) {
912  return;
913  }
914  reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N);
915  }
916 }
917 
918 void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal,
919  const SVal &Iter, bool Postfix) const {
920  // Increment the symbolic expressions which represents the position of the
921  // iterator
922  auto State = C.getState();
923  const auto *Pos = getIteratorPosition(State, Iter);
924  if (Pos) {
925  auto &SymMgr = C.getSymbolManager();
926  auto &BVF = SymMgr.getBasicVals();
927  auto &SVB = C.getSValBuilder();
928  const auto OldOffset = Pos->getOffset();
929  auto NewOffset =
930  SVB.evalBinOp(State, BO_Add,
931  nonloc::SymbolVal(OldOffset),
932  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
933  SymMgr.getType(OldOffset)).getAsSymbol();
934  auto NewPos = Pos->setTo(NewOffset);
935  State = setIteratorPosition(State, Iter, NewPos);
936  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
937  C.addTransition(State);
938  }
939 }
940 
941 void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal,
942  const SVal &Iter, bool Postfix) const {
943  // Decrement the symbolic expressions which represents the position of the
944  // iterator
945  auto State = C.getState();
946  const auto *Pos = getIteratorPosition(State, Iter);
947  if (Pos) {
948  auto &SymMgr = C.getSymbolManager();
949  auto &BVF = SymMgr.getBasicVals();
950  auto &SVB = C.getSValBuilder();
951  const auto OldOffset = Pos->getOffset();
952  auto NewOffset =
953  SVB.evalBinOp(State, BO_Sub,
954  nonloc::SymbolVal(OldOffset),
955  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
956  SymMgr.getType(OldOffset)).getAsSymbol();
957  auto NewPos = Pos->setTo(NewOffset);
958  State = setIteratorPosition(State, Iter, NewPos);
959  State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos);
960  C.addTransition(State);
961  }
962 }
963 
964 // This function tells the analyzer's engine that symbols produced by our
965 // checker, most notably iterator positions, are relatively small.
966 // A distance between items in the container should not be very large.
967 // By assuming that it is within around 1/8 of the address space,
968 // we can help the analyzer perform operations on these symbols
969 // without being afraid of integer overflows.
970 // FIXME: Should we provide it as an API, so that all checkers could use it?
972  long Scale) {
973  SValBuilder &SVB = State->getStateManager().getSValBuilder();
974  BasicValueFactory &BV = SVB.getBasicValueFactory();
975 
976  QualType T = Sym->getType();
978  APSIntType AT = BV.getAPSIntType(T);
979 
980  ProgramStateRef NewState = State;
981 
982  llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale);
983  SVal IsCappedFromAbove =
984  SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym),
985  nonloc::ConcreteInt(Max), SVB.getConditionType());
986  if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) {
987  NewState = NewState->assume(*DV, true);
988  if (!NewState)
989  return State;
990  }
991 
992  llvm::APSInt Min = -Max;
993  SVal IsCappedFromBelow =
994  SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym),
995  nonloc::ConcreteInt(Min), SVB.getConditionType());
996  if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) {
997  NewState = NewState->assume(*DV, true);
998  if (!NewState)
999  return State;
1000  }
1001 
1002  return NewState;
1003 }
1004 
1005 void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C,
1007  const SVal &RetVal,
1008  const SVal &LHS,
1009  const SVal &RHS) const {
1010  // Increment or decrement the symbolic expressions which represents the
1011  // position of the iterator
1012  auto State = C.getState();
1013  const auto *Pos = getIteratorPosition(State, LHS);
1014  if (!Pos)
1015  return;
1016 
1017  const auto *value = &RHS;
1018  if (auto loc = RHS.getAs<Loc>()) {
1019  const auto val = State->getRawSVal(*loc);
1020  value = &val;
1021  }
1022 
1023  auto &SymMgr = C.getSymbolManager();
1024  auto &SVB = C.getSValBuilder();
1025  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
1026  const auto OldOffset = Pos->getOffset();
1027  SymbolRef NewOffset;
1028  if (const auto intValue = value->getAs<nonloc::ConcreteInt>()) {
1029  // For concrete integers we can calculate the new position
1030  NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
1031  *intValue,
1032  SymMgr.getType(OldOffset)).getAsSymbol();
1033  } else {
1034  // For other symbols create a new symbol to keep expressions simple
1035  const auto &LCtx = C.getLocationContext();
1036  NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset),
1037  C.blockCount());
1038  State = assumeNoOverflow(State, NewOffset, 4);
1039  }
1040  auto NewPos = Pos->setTo(NewOffset);
1041  auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal;
1042  State = setIteratorPosition(State, TgtVal, NewPos);
1043  C.addTransition(State);
1044 }
1045 
1046 void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C,
1048  const SVal &RetVal,
1049  const SVal &LHS,
1050  const SVal &RHS) const {
1051  auto State = C.getState();
1052 
1053  // If the iterator is initially inside its range, then the operation is valid
1054  const auto *Pos = getIteratorPosition(State, LHS);
1055  if (!Pos || !isOutOfRange(State, *Pos))
1056  return;
1057 
1058  auto value = RHS;
1059  if (auto loc = RHS.getAs<Loc>()) {
1060  value = State->getRawSVal(*loc);
1061  }
1062 
1063  // Incremention or decremention by 0 is never bug
1064  if (isZero(State, value.castAs<NonLoc>()))
1065  return;
1066 
1067  auto &SymMgr = C.getSymbolManager();
1068  auto &SVB = C.getSValBuilder();
1069  auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub;
1070  const auto OldOffset = Pos->getOffset();
1071  const auto intValue = value.getAs<nonloc::ConcreteInt>();
1072  if (!intValue)
1073  return;
1074 
1075  auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset),
1076  *intValue,
1077  SymMgr.getType(OldOffset)).getAsSymbol();
1078  auto NewPos = Pos->setTo(NewOffset);
1079 
1080  // If out of range, the only valid operation is to step into the range
1081  if (isOutOfRange(State, NewPos)) {
1082  auto *N = C.generateNonFatalErrorNode(State);
1083  if (!N)
1084  return;
1085  reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N);
1086  }
1087 }
1088 
1089 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter,
1090  const MemRegion *Cont) const {
1091  // Verify match between a container and the container of an iterator
1092  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
1093  Cont = CBOR->getSuperRegion();
1094  }
1095 
1096  auto State = C.getState();
1097  const auto *Pos = getIteratorPosition(State, Iter);
1098  if (Pos && Pos->getContainer() != Cont) {
1099  auto *N = C.generateNonFatalErrorNode(State);
1100  if (!N) {
1101  return;
1102  }
1103  reportMismatchedBug("Container accessed using foreign iterator argument.", Iter, Cont, C, N);
1104  }
1105 }
1106 
1107 void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1,
1108  const SVal &Iter2) const {
1109  // Verify match between the containers of two iterators
1110  auto State = C.getState();
1111  const auto *Pos1 = getIteratorPosition(State, Iter1);
1112  const auto *Pos2 = getIteratorPosition(State, Iter2);
1113  if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) {
1114  auto *N = C.generateNonFatalErrorNode(State);
1115  if (!N)
1116  return;
1117  reportMismatchedBug("Iterators of different containers used where the "
1118  "same container is expected.", Iter1, Iter2, C, N);
1119  }
1120 }
1121 
1122 void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE,
1123  const SVal &RetVal, const SVal &Cont) const {
1124  const auto *ContReg = Cont.getAsRegion();
1125  if (!ContReg)
1126  return;
1127 
1128  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1129  ContReg = CBOR->getSuperRegion();
1130  }
1131 
1132  // If the container already has a begin symbol then use it. Otherwise first
1133  // create a new one.
1134  auto State = C.getState();
1135  auto BeginSym = getContainerBegin(State, ContReg);
1136  if (!BeginSym) {
1137  auto &SymMgr = C.getSymbolManager();
1138  BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1139  C.getASTContext().LongTy, C.blockCount());
1140  State = assumeNoOverflow(State, BeginSym, 4);
1141  State = createContainerBegin(State, ContReg, BeginSym);
1142  }
1143  State = setIteratorPosition(State, RetVal,
1144  IteratorPosition::getPosition(ContReg, BeginSym));
1145  C.addTransition(State);
1146 }
1147 
1148 void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE,
1149  const SVal &RetVal, const SVal &Cont) const {
1150  const auto *ContReg = Cont.getAsRegion();
1151  if (!ContReg)
1152  return;
1153 
1154  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1155  ContReg = CBOR->getSuperRegion();
1156  }
1157 
1158  // If the container already has an end symbol then use it. Otherwise first
1159  // create a new one.
1160  auto State = C.getState();
1161  auto EndSym = getContainerEnd(State, ContReg);
1162  if (!EndSym) {
1163  auto &SymMgr = C.getSymbolManager();
1164  EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1165  C.getASTContext().LongTy, C.blockCount());
1166  State = assumeNoOverflow(State, EndSym, 4);
1167  State = createContainerEnd(State, ContReg, EndSym);
1168  }
1169  State = setIteratorPosition(State, RetVal,
1170  IteratorPosition::getPosition(ContReg, EndSym));
1171  C.addTransition(State);
1172 }
1173 
1174 void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE,
1175  const SVal &RetVal,
1176  const MemRegion *Cont) const {
1177  while (const auto *CBOR = Cont->getAs<CXXBaseObjectRegion>()) {
1178  Cont = CBOR->getSuperRegion();
1179  }
1180 
1181  auto State = C.getState();
1182  auto &SymMgr = C.getSymbolManager();
1183  auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(),
1184  C.getASTContext().LongTy, C.blockCount());
1185  State = assumeNoOverflow(State, Sym, 4);
1186  State = setIteratorPosition(State, RetVal,
1187  IteratorPosition::getPosition(Cont, Sym));
1188  C.addTransition(State);
1189 }
1190 
1191 void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont,
1192  const Expr *CE, const SVal &OldCont) const {
1193  const auto *ContReg = Cont.getAsRegion();
1194  if (!ContReg)
1195  return;
1196 
1197  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1198  ContReg = CBOR->getSuperRegion();
1199  }
1200 
1201  // Assignment of a new value to a container always invalidates all its
1202  // iterators
1203  auto State = C.getState();
1204  const auto CData = getContainerData(State, ContReg);
1205  if (CData) {
1206  State = invalidateAllIteratorPositions(State, ContReg);
1207  }
1208 
1209  // In case of move, iterators of the old container (except the past-end
1210  // iterators) remain valid but refer to the new container
1211  if (!OldCont.isUndef()) {
1212  const auto *OldContReg = OldCont.getAsRegion();
1213  if (OldContReg) {
1214  while (const auto *CBOR = OldContReg->getAs<CXXBaseObjectRegion>()) {
1215  OldContReg = CBOR->getSuperRegion();
1216  }
1217  const auto OldCData = getContainerData(State, OldContReg);
1218  if (OldCData) {
1219  if (const auto OldEndSym = OldCData->getEnd()) {
1220  // If we already assigned an "end" symbol to the old conainer, then
1221  // first reassign all iterator positions to the new container which
1222  // are not past the container (thus not greater or equal to the
1223  // current "end" symbol).
1224  State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
1225  OldEndSym, BO_GE);
1226  auto &SymMgr = C.getSymbolManager();
1227  auto &SVB = C.getSValBuilder();
1228  // Then generate and assign a new "end" symbol for the new container.
1229  auto NewEndSym =
1230  SymMgr.conjureSymbol(CE, C.getLocationContext(),
1231  C.getASTContext().LongTy, C.blockCount());
1232  State = assumeNoOverflow(State, NewEndSym, 4);
1233  if (CData) {
1234  State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
1235  } else {
1236  State = setContainerData(State, ContReg,
1237  ContainerData::fromEnd(NewEndSym));
1238  }
1239  // Finally, replace the old "end" symbol in the already reassigned
1240  // iterator positions with the new "end" symbol.
1242  State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
1243  } else {
1244  // There was no "end" symbol assigned yet to the old container,
1245  // so reassign all iterator positions to the new container.
1246  State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1247  }
1248  if (const auto OldBeginSym = OldCData->getBegin()) {
1249  // If we already assigned a "begin" symbol to the old container, then
1250  // assign it to the new container and remove it from the old one.
1251  if (CData) {
1252  State =
1253  setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
1254  } else {
1255  State = setContainerData(State, ContReg,
1256  ContainerData::fromBegin(OldBeginSym));
1257  }
1258  State =
1259  setContainerData(State, OldContReg, OldCData->newEnd(nullptr));
1260  }
1261  } else {
1262  // There was neither "begin" nor "end" symbol assigned yet to the old
1263  // container, so reassign all iterator positions to the new container.
1264  State = reassignAllIteratorPositions(State, OldContReg, ContReg);
1265  }
1266  }
1267  }
1268  C.addTransition(State);
1269 }
1270 
1271 void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const {
1272  const auto *ContReg = Cont.getAsRegion();
1273  if (!ContReg)
1274  return;
1275 
1276  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1277  ContReg = CBOR->getSuperRegion();
1278  }
1279 
1280  // The clear() operation invalidates all the iterators, except the past-end
1281  // iterators of list-like containers
1282  auto State = C.getState();
1283  if (!hasSubscriptOperator(State, ContReg) ||
1284  !backModifiable(State, ContReg)) {
1285  const auto CData = getContainerData(State, ContReg);
1286  if (CData) {
1287  if (const auto EndSym = CData->getEnd()) {
1288  State =
1289  invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
1290  C.addTransition(State);
1291  return;
1292  }
1293  }
1294  }
1295  State = invalidateAllIteratorPositions(State, ContReg);
1296  C.addTransition(State);
1297 }
1298 
1299 void IteratorChecker::handlePushBack(CheckerContext &C,
1300  const SVal &Cont) const {
1301  const auto *ContReg = Cont.getAsRegion();
1302  if (!ContReg)
1303  return;
1304 
1305  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1306  ContReg = CBOR->getSuperRegion();
1307  }
1308 
1309  // For deque-like containers invalidate all iterator positions
1310  auto State = C.getState();
1311  if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
1312  State = invalidateAllIteratorPositions(State, ContReg);
1313  C.addTransition(State);
1314  return;
1315  }
1316 
1317  const auto CData = getContainerData(State, ContReg);
1318  if (!CData)
1319  return;
1320 
1321  // For vector-like containers invalidate the past-end iterator positions
1322  if (const auto EndSym = CData->getEnd()) {
1323  if (hasSubscriptOperator(State, ContReg)) {
1324  State = invalidateIteratorPositions(State, EndSym, BO_GE);
1325  }
1326  auto &SymMgr = C.getSymbolManager();
1327  auto &BVF = SymMgr.getBasicVals();
1328  auto &SVB = C.getSValBuilder();
1329  const auto newEndSym =
1330  SVB.evalBinOp(State, BO_Add,
1331  nonloc::SymbolVal(EndSym),
1332  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1333  SymMgr.getType(EndSym)).getAsSymbol();
1334  State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1335  }
1336  C.addTransition(State);
1337 }
1338 
1339 void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const {
1340  const auto *ContReg = Cont.getAsRegion();
1341  if (!ContReg)
1342  return;
1343 
1344  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1345  ContReg = CBOR->getSuperRegion();
1346  }
1347 
1348  auto State = C.getState();
1349  const auto CData = getContainerData(State, ContReg);
1350  if (!CData)
1351  return;
1352 
1353  if (const auto EndSym = CData->getEnd()) {
1354  auto &SymMgr = C.getSymbolManager();
1355  auto &BVF = SymMgr.getBasicVals();
1356  auto &SVB = C.getSValBuilder();
1357  const auto BackSym =
1358  SVB.evalBinOp(State, BO_Sub,
1359  nonloc::SymbolVal(EndSym),
1360  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1361  SymMgr.getType(EndSym)).getAsSymbol();
1362  // For vector-like and deque-like containers invalidate the last and the
1363  // past-end iterator positions. For list-like containers only invalidate
1364  // the last position
1365  if (hasSubscriptOperator(State, ContReg) &&
1366  backModifiable(State, ContReg)) {
1367  State = invalidateIteratorPositions(State, BackSym, BO_GE);
1368  State = setContainerData(State, ContReg, CData->newEnd(nullptr));
1369  } else {
1370  State = invalidateIteratorPositions(State, BackSym, BO_EQ);
1371  }
1372  auto newEndSym = BackSym;
1373  State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
1374  C.addTransition(State);
1375  }
1376 }
1377 
1378 void IteratorChecker::handlePushFront(CheckerContext &C,
1379  const SVal &Cont) const {
1380  const auto *ContReg = Cont.getAsRegion();
1381  if (!ContReg)
1382  return;
1383 
1384  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1385  ContReg = CBOR->getSuperRegion();
1386  }
1387 
1388  // For deque-like containers invalidate all iterator positions
1389  auto State = C.getState();
1390  if (hasSubscriptOperator(State, ContReg)) {
1391  State = invalidateAllIteratorPositions(State, ContReg);
1392  C.addTransition(State);
1393  } else {
1394  const auto CData = getContainerData(State, ContReg);
1395  if (!CData)
1396  return;
1397 
1398  if (const auto BeginSym = CData->getBegin()) {
1399  auto &SymMgr = C.getSymbolManager();
1400  auto &BVF = SymMgr.getBasicVals();
1401  auto &SVB = C.getSValBuilder();
1402  const auto newBeginSym =
1403  SVB.evalBinOp(State, BO_Sub,
1404  nonloc::SymbolVal(BeginSym),
1405  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1406  SymMgr.getType(BeginSym)).getAsSymbol();
1407  State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1408  C.addTransition(State);
1409  }
1410  }
1411 }
1412 
1413 void IteratorChecker::handlePopFront(CheckerContext &C,
1414  const SVal &Cont) const {
1415  const auto *ContReg = Cont.getAsRegion();
1416  if (!ContReg)
1417  return;
1418 
1419  while (const auto *CBOR = ContReg->getAs<CXXBaseObjectRegion>()) {
1420  ContReg = CBOR->getSuperRegion();
1421  }
1422 
1423  auto State = C.getState();
1424  const auto CData = getContainerData(State, ContReg);
1425  if (!CData)
1426  return;
1427 
1428  // For deque-like containers invalidate all iterator positions. For list-like
1429  // iterators only invalidate the first position
1430  if (const auto BeginSym = CData->getBegin()) {
1431  if (hasSubscriptOperator(State, ContReg)) {
1432  State = invalidateIteratorPositions(State, BeginSym, BO_LE);
1433  } else {
1434  State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
1435  }
1436  auto &SymMgr = C.getSymbolManager();
1437  auto &BVF = SymMgr.getBasicVals();
1438  auto &SVB = C.getSValBuilder();
1439  const auto newBeginSym =
1440  SVB.evalBinOp(State, BO_Add,
1441  nonloc::SymbolVal(BeginSym),
1442  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1443  SymMgr.getType(BeginSym)).getAsSymbol();
1444  State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
1445  C.addTransition(State);
1446  }
1447 }
1448 
1449 void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const {
1450  auto State = C.getState();
1451  const auto *Pos = getIteratorPosition(State, Iter);
1452  if (!Pos)
1453  return;
1454 
1455  // For deque-like containers invalidate all iterator positions. For
1456  // vector-like containers invalidate iterator positions after the insertion.
1457  const auto *Cont = Pos->getContainer();
1458  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1459  if (frontModifiable(State, Cont)) {
1460  State = invalidateAllIteratorPositions(State, Cont);
1461  } else {
1462  State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1463  }
1464  if (const auto *CData = getContainerData(State, Cont)) {
1465  if (const auto EndSym = CData->getEnd()) {
1466  State = invalidateIteratorPositions(State, EndSym, BO_GE);
1467  State = setContainerData(State, Cont, CData->newEnd(nullptr));
1468  }
1469  }
1470  C.addTransition(State);
1471  }
1472 }
1473 
1474 void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const {
1475  auto State = C.getState();
1476  const auto *Pos = getIteratorPosition(State, Iter);
1477  if (!Pos)
1478  return;
1479 
1480  // For deque-like containers invalidate all iterator positions. For
1481  // vector-like containers invalidate iterator positions at and after the
1482  // deletion. For list-like containers only invalidate the deleted position.
1483  const auto *Cont = Pos->getContainer();
1484  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1485  if (frontModifiable(State, Cont)) {
1486  State = invalidateAllIteratorPositions(State, Cont);
1487  } else {
1488  State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
1489  }
1490  if (const auto *CData = getContainerData(State, Cont)) {
1491  if (const auto EndSym = CData->getEnd()) {
1492  State = invalidateIteratorPositions(State, EndSym, BO_GE);
1493  State = setContainerData(State, Cont, CData->newEnd(nullptr));
1494  }
1495  }
1496  } else {
1497  State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
1498  }
1499  C.addTransition(State);
1500 }
1501 
1502 void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1,
1503  const SVal &Iter2) const {
1504  auto State = C.getState();
1505  const auto *Pos1 = getIteratorPosition(State, Iter1);
1506  const auto *Pos2 = getIteratorPosition(State, Iter2);
1507  if (!Pos1 || !Pos2)
1508  return;
1509 
1510  // For deque-like containers invalidate all iterator positions. For
1511  // vector-like containers invalidate iterator positions at and after the
1512  // deletion range. For list-like containers only invalidate the deleted
1513  // position range [first..last].
1514  const auto *Cont = Pos1->getContainer();
1515  if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) {
1516  if (frontModifiable(State, Cont)) {
1517  State = invalidateAllIteratorPositions(State, Cont);
1518  } else {
1519  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
1520  }
1521  if (const auto *CData = getContainerData(State, Cont)) {
1522  if (const auto EndSym = CData->getEnd()) {
1523  State = invalidateIteratorPositions(State, EndSym, BO_GE);
1524  State = setContainerData(State, Cont, CData->newEnd(nullptr));
1525  }
1526  }
1527  } else {
1528  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
1529  Pos2->getOffset(), BO_LT);
1530  }
1531  C.addTransition(State);
1532 }
1533 
1534 void IteratorChecker::handleEraseAfter(CheckerContext &C,
1535  const SVal &Iter) const {
1536  auto State = C.getState();
1537  const auto *Pos = getIteratorPosition(State, Iter);
1538  if (!Pos)
1539  return;
1540 
1541  // Invalidate the deleted iterator position, which is the position of the
1542  // parameter plus one.
1543  auto &SymMgr = C.getSymbolManager();
1544  auto &BVF = SymMgr.getBasicVals();
1545  auto &SVB = C.getSValBuilder();
1546  const auto NextSym =
1547  SVB.evalBinOp(State, BO_Add,
1548  nonloc::SymbolVal(Pos->getOffset()),
1549  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
1550  SymMgr.getType(Pos->getOffset())).getAsSymbol();
1551  State = invalidateIteratorPositions(State, NextSym, BO_EQ);
1552  C.addTransition(State);
1553 }
1554 
1555 void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1,
1556  const SVal &Iter2) const {
1557  auto State = C.getState();
1558  const auto *Pos1 = getIteratorPosition(State, Iter1);
1559  const auto *Pos2 = getIteratorPosition(State, Iter2);
1560  if (!Pos1 || !Pos2)
1561  return;
1562 
1563  // Invalidate the deleted iterator position range (first..last)
1564  State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
1565  Pos2->getOffset(), BO_LT);
1566  C.addTransition(State);
1567 }
1568 
1569 void IteratorChecker::reportOutOfRangeBug(const StringRef &Message,
1570  const SVal &Val, CheckerContext &C,
1571  ExplodedNode *ErrNode) const {
1572  auto R = llvm::make_unique<BugReport>(*OutOfRangeBugType, Message, ErrNode);
1573  R->markInteresting(Val);
1574  C.emitReport(std::move(R));
1575 }
1576 
1577 void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1578  const SVal &Val1, const SVal &Val2,
1579  CheckerContext &C,
1580  ExplodedNode *ErrNode) const {
1581  auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1582  R->markInteresting(Val1);
1583  R->markInteresting(Val2);
1584  C.emitReport(std::move(R));
1585 }
1586 
1587 void IteratorChecker::reportMismatchedBug(const StringRef &Message,
1588  const SVal &Val, const MemRegion *Reg,
1589  CheckerContext &C,
1590  ExplodedNode *ErrNode) const {
1591  auto R = llvm::make_unique<BugReport>(*MismatchedBugType, Message, ErrNode);
1592  R->markInteresting(Val);
1593  R->markInteresting(Reg);
1594  C.emitReport(std::move(R));
1595 }
1596 
1597 void IteratorChecker::reportInvalidatedBug(const StringRef &Message,
1598  const SVal &Val, CheckerContext &C,
1599  ExplodedNode *ErrNode) const {
1600  auto R = llvm::make_unique<BugReport>(*InvalidatedBugType, Message, ErrNode);
1601  R->markInteresting(Val);
1602  C.emitReport(std::move(R));
1603 }
1604 
1605 namespace {
1606 
1607 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1608 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
1609 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
1611 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
1613 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1614  const MemRegion *Reg);
1615 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
1616  SymbolRef OldSym, SymbolRef NewSym);
1617 
1618 bool isIteratorType(const QualType &Type) {
1619  if (Type->isPointerType())
1620  return true;
1621 
1622  const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
1623  return isIterator(CRD);
1624 }
1625 
1626 bool isIterator(const CXXRecordDecl *CRD) {
1627  if (!CRD)
1628  return false;
1629 
1630  const auto Name = CRD->getName();
1631  if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") ||
1632  Name.endswith_lower("it")))
1633  return false;
1634 
1635  bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false,
1636  HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false;
1637  for (const auto *Method : CRD->methods()) {
1638  if (const auto *Ctor = dyn_cast<CXXConstructorDecl>(Method)) {
1639  if (Ctor->isCopyConstructor()) {
1640  HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public;
1641  }
1642  continue;
1643  }
1644  if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(Method)) {
1645  HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public;
1646  continue;
1647  }
1648  if (Method->isCopyAssignmentOperator()) {
1649  HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public;
1650  continue;
1651  }
1652  if (!Method->isOverloadedOperator())
1653  continue;
1654  const auto OPK = Method->getOverloadedOperator();
1655  if (OPK == OO_PlusPlus) {
1656  HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0);
1657  HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1);
1658  continue;
1659  }
1660  if (OPK == OO_Star) {
1661  HasDerefOp = (Method->getNumParams() == 0);
1662  continue;
1663  }
1664  }
1665 
1666  return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp &&
1667  HasPostIncrOp && HasDerefOp;
1668 }
1669 
1671  return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less ||
1672  OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual;
1673 }
1674 
1675 bool isBeginCall(const FunctionDecl *Func) {
1676  const auto *IdInfo = Func->getIdentifier();
1677  if (!IdInfo)
1678  return false;
1679  return IdInfo->getName().endswith_lower("begin");
1680 }
1681 
1682 bool isEndCall(const FunctionDecl *Func) {
1683  const auto *IdInfo = Func->getIdentifier();
1684  if (!IdInfo)
1685  return false;
1686  return IdInfo->getName().endswith_lower("end");
1687 }
1688 
1689 bool isAssignCall(const FunctionDecl *Func) {
1690  const auto *IdInfo = Func->getIdentifier();
1691  if (!IdInfo)
1692  return false;
1693  if (Func->getNumParams() > 2)
1694  return false;
1695  return IdInfo->getName() == "assign";
1696 }
1697 
1698 bool isClearCall(const FunctionDecl *Func) {
1699  const auto *IdInfo = Func->getIdentifier();
1700  if (!IdInfo)
1701  return false;
1702  if (Func->getNumParams() > 0)
1703  return false;
1704  return IdInfo->getName() == "clear";
1705 }
1706 
1707 bool isPushBackCall(const FunctionDecl *Func) {
1708  const auto *IdInfo = Func->getIdentifier();
1709  if (!IdInfo)
1710  return false;
1711  if (Func->getNumParams() != 1)
1712  return false;
1713  return IdInfo->getName() == "push_back";
1714 }
1715 
1716 bool isEmplaceBackCall(const FunctionDecl *Func) {
1717  const auto *IdInfo = Func->getIdentifier();
1718  if (!IdInfo)
1719  return false;
1720  if (Func->getNumParams() < 1)
1721  return false;
1722  return IdInfo->getName() == "emplace_back";
1723 }
1724 
1725 bool isPopBackCall(const FunctionDecl *Func) {
1726  const auto *IdInfo = Func->getIdentifier();
1727  if (!IdInfo)
1728  return false;
1729  if (Func->getNumParams() > 0)
1730  return false;
1731  return IdInfo->getName() == "pop_back";
1732 }
1733 
1734 bool isPushFrontCall(const FunctionDecl *Func) {
1735  const auto *IdInfo = Func->getIdentifier();
1736  if (!IdInfo)
1737  return false;
1738  if (Func->getNumParams() != 1)
1739  return false;
1740  return IdInfo->getName() == "push_front";
1741 }
1742 
1743 bool isEmplaceFrontCall(const FunctionDecl *Func) {
1744  const auto *IdInfo = Func->getIdentifier();
1745  if (!IdInfo)
1746  return false;
1747  if (Func->getNumParams() < 1)
1748  return false;
1749  return IdInfo->getName() == "emplace_front";
1750 }
1751 
1752 bool isPopFrontCall(const FunctionDecl *Func) {
1753  const auto *IdInfo = Func->getIdentifier();
1754  if (!IdInfo)
1755  return false;
1756  if (Func->getNumParams() > 0)
1757  return false;
1758  return IdInfo->getName() == "pop_front";
1759 }
1760 
1761 bool isInsertCall(const FunctionDecl *Func) {
1762  const auto *IdInfo = Func->getIdentifier();
1763  if (!IdInfo)
1764  return false;
1765  if (Func->getNumParams() < 2 || Func->getNumParams() > 3)
1766  return false;
1767  if (!isIteratorType(Func->getParamDecl(0)->getType()))
1768  return false;
1769  return IdInfo->getName() == "insert";
1770 }
1771 
1772 bool isEmplaceCall(const FunctionDecl *Func) {
1773  const auto *IdInfo = Func->getIdentifier();
1774  if (!IdInfo)
1775  return false;
1776  if (Func->getNumParams() < 2)
1777  return false;
1778  if (!isIteratorType(Func->getParamDecl(0)->getType()))
1779  return false;
1780  return IdInfo->getName() == "emplace";
1781 }
1782 
1783 bool isEraseCall(const FunctionDecl *Func) {
1784  const auto *IdInfo = Func->getIdentifier();
1785  if (!IdInfo)
1786  return false;
1787  if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
1788  return false;
1789  if (!isIteratorType(Func->getParamDecl(0)->getType()))
1790  return false;
1791  if (Func->getNumParams() == 2 &&
1792  !isIteratorType(Func->getParamDecl(1)->getType()))
1793  return false;
1794  return IdInfo->getName() == "erase";
1795 }
1796 
1797 bool isEraseAfterCall(const FunctionDecl *Func) {
1798  const auto *IdInfo = Func->getIdentifier();
1799  if (!IdInfo)
1800  return false;
1801  if (Func->getNumParams() < 1 || Func->getNumParams() > 2)
1802  return false;
1803  if (!isIteratorType(Func->getParamDecl(0)->getType()))
1804  return false;
1805  if (Func->getNumParams() == 2 &&
1806  !isIteratorType(Func->getParamDecl(1)->getType()))
1807  return false;
1808  return IdInfo->getName() == "erase_after";
1809 }
1810 
1811 bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; }
1812 
1814  return OK == OO_EqualEqual || OK == OO_ExclaimEqual;
1815 }
1816 
1818  return isDereferenceOperator(OK) || isIncrementOperator(OK) ||
1820 }
1821 
1823  return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar ||
1824  OK == OO_Subscript;
1825 }
1826 
1828  return OK == OO_PlusPlus;
1829 }
1830 
1832  return OK == OO_MinusMinus;
1833 }
1834 
1836  return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus ||
1837  OK == OO_MinusEqual;
1838 }
1839 
1840 BinaryOperator::Opcode getOpcode(const SymExpr *SE) {
1841  if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) {
1842  return BSE->getOpcode();
1843  } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) {
1844  const auto *COE = dyn_cast_or_null<CXXOperatorCallExpr>(SC->getStmt());
1845  if (!COE)
1846  return BO_Comma; // Extremal value, neither EQ nor NE
1847  if (COE->getOperator() == OO_EqualEqual) {
1848  return BO_EQ;
1849  } else if (COE->getOperator() == OO_ExclaimEqual) {
1850  return BO_NE;
1851  }
1852  return BO_Comma; // Extremal value, neither EQ nor NE
1853  }
1854  return BO_Comma; // Extremal value, neither EQ nor NE
1855 }
1856 
1857 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
1858  const auto *CRD = getCXXRecordDecl(State, Reg);
1859  if (!CRD)
1860  return false;
1861 
1862  for (const auto *Method : CRD->methods()) {
1863  if (!Method->isOverloadedOperator())
1864  continue;
1865  const auto OPK = Method->getOverloadedOperator();
1866  if (OPK == OO_Subscript) {
1867  return true;
1868  }
1869  }
1870  return false;
1871 }
1872 
1873 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
1874  const auto *CRD = getCXXRecordDecl(State, Reg);
1875  if (!CRD)
1876  return false;
1877 
1878  for (const auto *Method : CRD->methods()) {
1879  if (!Method->getDeclName().isIdentifier())
1880  continue;
1881  if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
1882  return true;
1883  }
1884  }
1885  return false;
1886 }
1887 
1888 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
1889  const auto *CRD = getCXXRecordDecl(State, Reg);
1890  if (!CRD)
1891  return false;
1892 
1893  for (const auto *Method : CRD->methods()) {
1894  if (!Method->getDeclName().isIdentifier())
1895  continue;
1896  if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
1897  return true;
1898  }
1899  }
1900  return false;
1901 }
1902 
1903 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
1904  const MemRegion *Reg) {
1905  auto TI = getDynamicTypeInfo(State, Reg);
1906  if (!TI.isValid())
1907  return nullptr;
1908 
1909  auto Type = TI.getType();
1910  if (const auto *RefT = Type->getAs<ReferenceType>()) {
1911  Type = RefT->getPointeeType();
1912  }
1913 
1915 }
1916 
1917 const RegionOrSymbol getRegionOrSymbol(const SVal &Val) {
1918  if (const auto Reg = Val.getAsRegion()) {
1919  return Reg;
1920  } else if (const auto Sym = Val.getAsSymbol()) {
1921  return Sym;
1922  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
1923  return LCVal->getRegion();
1924  }
1925  return RegionOrSymbol();
1926 }
1927 
1929  RegionOrSymbol LVal,
1930  RegionOrSymbol RVal, bool Equal) {
1931  const auto *LPos = getIteratorPosition(State, LVal);
1932  const auto *RPos = getIteratorPosition(State, RVal);
1933  if (LPos && !RPos) {
1934  State = adjustIteratorPosition(State, RVal, *LPos, Equal);
1935  } else if (!LPos && RPos) {
1936  State = adjustIteratorPosition(State, LVal, *RPos, Equal);
1937  } else if (LPos && RPos) {
1938  State = relateIteratorPositions(State, *LPos, *RPos, Equal);
1939  }
1940  return State;
1941 }
1942 
1944  const SymExpr *Condition, const SVal &LVal,
1945  const SVal &RVal, bool Eq) {
1946  const auto Left = getRegionOrSymbol(LVal);
1947  const auto Right = getRegionOrSymbol(RVal);
1948  if (!Left || !Right)
1949  return State;
1950  return State->set<IteratorComparisonMap>(Condition,
1951  IteratorComparison(Left, Right, Eq));
1952 }
1953 
1955  const SymExpr *Condition) {
1956  return State->get<IteratorComparisonMap>(Condition);
1957 }
1958 
1959 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
1960  const auto *CDataPtr = getContainerData(State, Cont);
1961  if (!CDataPtr)
1962  return nullptr;
1963 
1964  return CDataPtr->getBegin();
1965 }
1966 
1967 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
1968  const auto *CDataPtr = getContainerData(State, Cont);
1969  if (!CDataPtr)
1970  return nullptr;
1971 
1972  return CDataPtr->getEnd();
1973 }
1974 
1976  const MemRegion *Cont,
1977  const SymbolRef Sym) {
1978  // Only create if it does not exist
1979  const auto *CDataPtr = getContainerData(State, Cont);
1980  if (CDataPtr) {
1981  if (CDataPtr->getBegin()) {
1982  return State;
1983  }
1984  const auto CData = CDataPtr->newBegin(Sym);
1985  return setContainerData(State, Cont, CData);
1986  }
1987  const auto CData = ContainerData::fromBegin(Sym);
1988  return setContainerData(State, Cont, CData);
1989 }
1990 
1991 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
1992  const SymbolRef Sym) {
1993  // Only create if it does not exist
1994  const auto *CDataPtr = getContainerData(State, Cont);
1995  if (CDataPtr) {
1996  if (CDataPtr->getEnd()) {
1997  return State;
1998  }
1999  const auto CData = CDataPtr->newEnd(Sym);
2000  return setContainerData(State, Cont, CData);
2001  }
2002  const auto CData = ContainerData::fromEnd(Sym);
2003  return setContainerData(State, Cont, CData);
2004 }
2005 
2006 const ContainerData *getContainerData(ProgramStateRef State,
2007  const MemRegion *Cont) {
2008  return State->get<ContainerMap>(Cont);
2009 }
2010 
2011 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
2012  const ContainerData &CData) {
2013  return State->set<ContainerMap>(Cont, CData);
2014 }
2015 
2016 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2017  const SVal &Val) {
2018  if (const auto Reg = Val.getAsRegion()) {
2019  return State->get<IteratorRegionMap>(Reg);
2020  } else if (const auto Sym = Val.getAsSymbol()) {
2021  return State->get<IteratorSymbolMap>(Sym);
2022  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2023  return State->get<IteratorRegionMap>(LCVal->getRegion());
2024  }
2025  return nullptr;
2026 }
2027 
2028 const IteratorPosition *getIteratorPosition(ProgramStateRef State,
2029  RegionOrSymbol RegOrSym) {
2030  if (RegOrSym.is<const MemRegion *>()) {
2031  return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>());
2032  } else if (RegOrSym.is<SymbolRef>()) {
2033  return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>());
2034  }
2035  return nullptr;
2036 }
2037 
2038 ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val,
2039  const IteratorPosition &Pos) {
2040  if (const auto Reg = Val.getAsRegion()) {
2041  return State->set<IteratorRegionMap>(Reg, Pos);
2042  } else if (const auto Sym = Val.getAsSymbol()) {
2043  return State->set<IteratorSymbolMap>(Sym, Pos);
2044  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2045  return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos);
2046  }
2047  return nullptr;
2048 }
2049 
2051  RegionOrSymbol RegOrSym,
2052  const IteratorPosition &Pos) {
2053  if (RegOrSym.is<const MemRegion *>()) {
2054  return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(),
2055  Pos);
2056  } else if (RegOrSym.is<SymbolRef>()) {
2057  return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos);
2058  }
2059  return nullptr;
2060 }
2061 
2062 ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) {
2063  if (const auto Reg = Val.getAsRegion()) {
2064  return State->remove<IteratorRegionMap>(Reg);
2065  } else if (const auto Sym = Val.getAsSymbol()) {
2066  return State->remove<IteratorSymbolMap>(Sym);
2067  } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) {
2068  return State->remove<IteratorRegionMap>(LCVal->getRegion());
2069  }
2070  return nullptr;
2071 }
2072 
2074  RegionOrSymbol RegOrSym,
2075  const IteratorPosition &Pos,
2076  bool Equal) {
2077  if (Equal) {
2078  return setIteratorPosition(State, RegOrSym, Pos);
2079  } else {
2080  return State;
2081  }
2082 }
2083 
2085  const IteratorPosition &Pos1,
2086  const IteratorPosition &Pos2,
2087  bool Equal) {
2088  auto &SVB = State->getStateManager().getSValBuilder();
2089 
2090  // FIXME: This code should be reworked as follows:
2091  // 1. Subtract the operands using evalBinOp().
2092  // 2. Assume that the result doesn't overflow.
2093  // 3. Compare the result to 0.
2094  // 4. Assume the result of the comparison.
2095  const auto comparison =
2096  SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()),
2097  nonloc::SymbolVal(Pos2.getOffset()),
2098  SVB.getConditionType());
2099 
2100  assert(comparison.getAs<DefinedSVal>() &&
2101  "Symbol comparison must be a `DefinedSVal`");
2102 
2103  auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal);
2104  if (const auto CompSym = comparison.getAsSymbol()) {
2105  assert(isa<SymIntExpr>(CompSym) &&
2106  "Symbol comparison must be a `SymIntExpr`");
2108  cast<SymIntExpr>(CompSym)->getOpcode()) &&
2109  "Symbol comparison must be a comparison");
2110  return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2);
2111  }
2112 
2113  return NewState;
2114 }
2115 
2116 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
2117  auto RegionMap = State->get<IteratorRegionMap>();
2118  for (const auto Reg : RegionMap) {
2119  if (Reg.second.getContainer() == Cont)
2120  return true;
2121  }
2122 
2123  auto SymbolMap = State->get<IteratorSymbolMap>();
2124  for (const auto Sym : SymbolMap) {
2125  if (Sym.second.getContainer() == Cont)
2126  return true;
2127  }
2128 
2129  return false;
2130 }
2131 
2132 bool isBoundThroughLazyCompoundVal(const Environment &Env,
2133  const MemRegion *Reg) {
2134  for (const auto Binding: Env) {
2135  if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) {
2136  if (LCVal->getRegion() == Reg)
2137  return true;
2138  }
2139  }
2140 
2141  return false;
2142 }
2143 
2144 template <typename Condition, typename Process>
2145 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
2146  Process Proc) {
2147  auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
2148  auto RegionMap = State->get<IteratorRegionMap>();
2149  bool Changed = false;
2150  for (const auto Reg : RegionMap) {
2151  if (Cond(Reg.second)) {
2152  RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
2153  Changed = true;
2154  }
2155  }
2156 
2157  if (Changed)
2158  State = State->set<IteratorRegionMap>(RegionMap);
2159 
2160  auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
2161  auto SymbolMap = State->get<IteratorSymbolMap>();
2162  Changed = false;
2163  for (const auto Sym : SymbolMap) {
2164  if (Cond(Sym.second)) {
2165  SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
2166  Changed = true;
2167  }
2168  }
2169 
2170  if (Changed)
2171  State = State->set<IteratorSymbolMap>(SymbolMap);
2172 
2173  return State;
2174 }
2175 
2177  const MemRegion *Cont) {
2178  auto MatchCont = [&](const IteratorPosition &Pos) {
2179  return Pos.getContainer() == Cont;
2180  };
2181  auto Invalidate = [&](const IteratorPosition &Pos) {
2182  return Pos.invalidate();
2183  };
2184  return processIteratorPositions(State, MatchCont, Invalidate);
2185 }
2186 
2189  const MemRegion *Cont, SymbolRef Offset,
2190  BinaryOperator::Opcode Opc) {
2191  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2192  return Pos.getContainer() == Cont &&
2193  !compare(State, Pos.getOffset(), Offset, Opc);
2194  };
2195  auto Invalidate = [&](const IteratorPosition &Pos) {
2196  return Pos.invalidate();
2197  };
2198  return processIteratorPositions(State, MatchContAndCompare, Invalidate);
2199 }
2200 
2202  SymbolRef Offset,
2203  BinaryOperator::Opcode Opc) {
2204  auto Compare = [&](const IteratorPosition &Pos) {
2205  return compare(State, Pos.getOffset(), Offset, Opc);
2206  };
2207  auto Invalidate = [&](const IteratorPosition &Pos) {
2208  return Pos.invalidate();
2209  };
2210  return processIteratorPositions(State, Compare, Invalidate);
2211 }
2212 
2214  SymbolRef Offset1,
2216  SymbolRef Offset2,
2217  BinaryOperator::Opcode Opc2) {
2218  auto Compare = [&](const IteratorPosition &Pos) {
2219  return compare(State, Pos.getOffset(), Offset1, Opc1) &&
2220  compare(State, Pos.getOffset(), Offset2, Opc2);
2221  };
2222  auto Invalidate = [&](const IteratorPosition &Pos) {
2223  return Pos.invalidate();
2224  };
2225  return processIteratorPositions(State, Compare, Invalidate);
2226 }
2227 
2229  const MemRegion *Cont,
2230  const MemRegion *NewCont) {
2231  auto MatchCont = [&](const IteratorPosition &Pos) {
2232  return Pos.getContainer() == Cont;
2233  };
2234  auto ReAssign = [&](const IteratorPosition &Pos) {
2235  return Pos.reAssign(NewCont);
2236  };
2237  return processIteratorPositions(State, MatchCont, ReAssign);
2238 }
2239 
2241  const MemRegion *Cont,
2242  const MemRegion *NewCont,
2243  SymbolRef Offset,
2244  BinaryOperator::Opcode Opc) {
2245  auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
2246  return Pos.getContainer() == Cont &&
2247  !compare(State, Pos.getOffset(), Offset, Opc);
2248  };
2249  auto ReAssign = [&](const IteratorPosition &Pos) {
2250  return Pos.reAssign(NewCont);
2251  };
2252  return processIteratorPositions(State, MatchContAndCompare, ReAssign);
2253 }
2254 
2255 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
2256 // `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator
2257 // position offsets where `CondSym` is true.
2259  ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
2260  SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
2261  auto LessThanEnd = [&](const IteratorPosition &Pos) {
2262  return compare(State, Pos.getOffset(), CondSym, Opc);
2263  };
2264  auto RebaseSymbol = [&](const IteratorPosition &Pos) {
2265  return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
2266  NewSym));
2267  };
2268  return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
2269 }
2270 
2271 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
2272 // `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression
2273 // `OrigExpr`.
2274 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
2275  SymbolRef OrigExpr, SymbolRef OldExpr,
2276  SymbolRef NewSym) {
2277  auto &SymMgr = SVB.getSymbolManager();
2278  auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
2279  nonloc::SymbolVal(OldExpr),
2280  SymMgr.getType(OrigExpr));
2281 
2282  const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
2283  if (!DiffInt)
2284  return OrigExpr;
2285 
2286  return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
2287  SymMgr.getType(OrigExpr)).getAsSymbol();
2288 }
2289 
2290 bool isZero(ProgramStateRef State, const NonLoc &Val) {
2291  auto &BVF = State->getBasicVals();
2292  return compare(State, Val,
2293  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
2294  BO_EQ);
2295 }
2296 
2297 bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) {
2298  const auto *Cont = Pos.getContainer();
2299  const auto *CData = getContainerData(State, Cont);
2300  if (!CData)
2301  return false;
2302 
2303  // Out of range means less than the begin symbol or greater or equal to the
2304  // end symbol.
2305 
2306  const auto Beg = CData->getBegin();
2307  if (Beg) {
2308  if (isLess(State, Pos.getOffset(), Beg)) {
2309  return true;
2310  }
2311  }
2312 
2313  const auto End = CData->getEnd();
2314  if (End) {
2315  if (isGreaterOrEqual(State, Pos.getOffset(), End)) {
2316  return true;
2317  }
2318  }
2319 
2320  return false;
2321 }
2322 
2323 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2324  return compare(State, Sym1, Sym2, BO_LT);
2325 }
2326 
2327 bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
2328  return compare(State, Sym1, Sym2, BO_GE);
2329 }
2330 
2331 bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2,
2332  BinaryOperator::Opcode Opc) {
2333  return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc);
2334 }
2335 
2336 
2337 bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2,
2338  BinaryOperator::Opcode Opc) {
2339  auto &SVB = State->getStateManager().getSValBuilder();
2340 
2341  const auto comparison =
2342  SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType());
2343 
2344  assert(comparison.getAs<DefinedSVal>() &&
2345  "Symbol comparison must be a `DefinedSVal`");
2346 
2347  return !State->assume(comparison.castAs<DefinedSVal>(), false);
2348 }
2349 
2350 } // namespace
2351 
2352 #define REGISTER_CHECKER(name) \
2353  void ento::register##name(CheckerManager &Mgr) { \
2354  auto *checker = Mgr.registerChecker<IteratorChecker>(); \
2355  checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \
2356  checker->CheckNames[IteratorChecker::CK_##name] = \
2357  Mgr.getCurrentCheckName(); \
2358  }
2359 
2360 REGISTER_CHECKER(IteratorRangeChecker)
2361 REGISTER_CHECKER(MismatchedIteratorChecker)
2362 REGISTER_CHECKER(InvalidatedIteratorChecker)
const ProgramStateRef processComparison(ProgramStateRef State, RegionOrSymbol LVal, RegionOrSymbol RVal, bool Equal)
Represents a function declaration or definition.
Definition: Decl.h:1717
bool isInsertCall(const FunctionDecl *Func)
A (possibly-)qualified type.
Definition: Type.h:642
SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont)
ProgramStateRef rebaseSymbolInIteratorPositionsIf(ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc)
bool isSimpleComparisonOperator(OverloadedOperatorKind OK)
bool operator==(CanQual< T > x, CanQual< U > y)
const SymExpr * SymbolRef
REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *, IteratorPosition) REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap
Stmt - This represents one statement.
Definition: Stmt.h:66
QualType getPointeeType() const
If this is a pointer, ObjC object pointer, or block pointer, this returns the respective pointee...
Definition: Type.cpp:497
IntrusiveRefCntPtr< const ProgramState > ProgramStateRef
Defines the C++ template declaration subclasses.
bool isAssignmentOperator(OverloadedOperatorKind OK)
The base class of the type hierarchy.
Definition: Type.h:1415
Represents a call to a C++ constructor.
Definition: ExprCXX.h:1262
bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos)
bool isZero(ProgramStateRef State, const NonLoc &Val)
Represents a prvalue temporary that is written into memory so that a reference can bind to it...
Definition: ExprCXX.h:4077
const T * getAs() const
Member-template getAs<specific type>&#39;.
Definition: Type.h:6590
Represents the result of substituting a type for a template type parameter.
Definition: Type.h:4486
IdentifierInfo * getIdentifier() const
Get the identifier that names this declaration, if there is one.
Definition: Decl.h:269
bool isAccessOperator(OverloadedOperatorKind OK)
Expr * GetTemporaryExpr() const
Retrieve the temporary-generating subexpression whose value will be materialized into a glvalue...
Definition: ExprCXX.h:4118
ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont, const MemRegion *NewCont)
bool isEraseAfterCall(const FunctionDecl *Func)
LineState State
ProgramStateRef adjustIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym, const IteratorPosition &Pos, bool Equal)
BinaryOperatorKind
bool isPopFrontCall(const FunctionDecl *Func)
uint32_t Offset
Definition: CacheTokens.cpp:43
bool isAssignCall(const FunctionDecl *Func)
ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, const MemRegion *Cont, const MemRegion *NewCont, SymbolRef Offset, BinaryOperator::Opcode Opc)
bool isEndCall(const FunctionDecl *Func)
bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg)
const Type * getUnqualifiedDesugaredType() const
Return the specified type with any "sugar" removed from the type, removing any typedefs, typeofs, etc., as well as any qualifiers.
Definition: Type.cpp:411
CXXRecordDecl * getAsCXXRecordDecl() const
Retrieves the CXXRecordDecl that this type refers to, either because the type is a RecordType or beca...
Definition: Type.cpp:1605
Represents a non-static C++ member function call, no matter how it is written.
Definition: CallEvent.h:681
const IteratorPosition * getIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym)
bool isPushBackCall(const FunctionDecl *Func)
bool frontModifiable(ProgramStateRef State, const MemRegion *Reg)
This represents one expression.
Definition: Expr.h:105
SourceLocation End
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
Declaration of a template type parameter.
bool isComparisonOperator(OverloadedOperatorKind OK)
bool isDereferenceOperator(OverloadedOperatorKind OK)
SourceLocation Begin
ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym)
ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, SymbolRef Offset1, BinaryOperator::Opcode Opc1, SymbolRef Offset2, BinaryOperator::Opcode Opc2)
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
bool isComparisonOp() const
Definition: Expr.h:3193
ProgramStateRef invalidateAllIteratorPositionsExcept(ProgramStateRef State, const MemRegion *Cont, SymbolRef Offset, BinaryOperator::Opcode Opc)
ProgramStateRef setIteratorPosition(ProgramStateRef State, RegionOrSymbol RegOrSym, const IteratorPosition &Pos)
bool isPopBackCall(const FunctionDecl *Func)
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:505
ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont)
const ParmVarDecl * getParamDecl(unsigned i) const
Definition: Decl.h:2254
bool isSignedIntegerOrEnumerationType() const
Determines whether this is an integer type that is signed or an enumeration types whose underlying ty...
Definition: Type.cpp:1852
SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont)
bool isDecrementOperator(OverloadedOperatorKind OK)
ProgramStateRef relateIteratorPositions(ProgramStateRef State, const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal)
const IteratorComparison * loadComparison(ProgramStateRef State, const SymExpr *Condition)
StringRef getName() const
Return the actual identifier string.
bool isPushFrontCall(const FunctionDecl *Func)
Dataflow Directional Tag Classes.
bool isClearCall(const FunctionDecl *Func)
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
Definition: OperatorKinds.h:22
DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *Reg)
Get dynamic type information for a region.
#define REGISTER_CHECKER(name)
BinaryOperator::Opcode getOpcode(const SymExpr *SE)
bool isIteratorType(const QualType &Type)
ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val)
bool backModifiable(ProgramStateRef State, const MemRegion *Reg)
ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData)
bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg)
bool isEmplaceCall(const FunctionDecl *Func)
Base for LValueReferenceType and RValueReferenceType.
Definition: Type.h:2647
bool isEmplaceBackCall(const FunctionDecl *Func)
const ProgramStateRef saveComparison(ProgramStateRef State, const SymExpr *Condition, const SVal &LVal, const SVal &RVal, bool Eq)
bool isEmplaceFrontCall(const FunctionDecl *Func)
X
Add a minimal nested name specifier fixit hint to allow lookup of a tag name from an outer enclosing ...
Definition: SemaDecl.cpp:13824
bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont)
Represents a C++ struct/union/class.
Definition: DeclCXX.h:300
bool isBeginCall(const FunctionDecl *Func)
const RegionOrSymbol getRegionOrSymbol(const SVal &Val)
bool operator!=(CanQual< T > x, CanQual< U > y)
StringRef getName() const
Get the name of identifier for this declaration as a StringRef.
Definition: Decl.h:275
bool isEraseCall(const FunctionDecl *Func)
ProgramStateRef createContainerBegin(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym)
bool isPointerType() const
Definition: Type.h:6177
bool isIncrementOperator(OverloadedOperatorKind OK)
QualType getType() const
Definition: Decl.h:647
unsigned getNumParams() const
Return the number of parameters this function must have based on its FunctionType.
Definition: Decl.cpp:3019
bool isIterator(const CXXRecordDecl *CRD)
static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale)
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
method_range methods() const
Definition: DeclCXX.h:865