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