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