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