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