xref: /llvm-project/clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp (revision 0b9d3a6e53e6c6488b531f3c8c281b485ca3b14a) 
1 //===-- ContainerModeling.cpp -------------------------------------*- C++ -*--//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // Defines a modeling-checker for modeling STL container-like containers.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "clang/AST/DeclTemplate.h"
14 #include "clang/Driver/DriverDiagnostic.h"
15 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17 #include "clang/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
21 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
22 
23 #include "Iterator.h"
24 
25 #include <utility>
26 
27 using namespace clang;
28 using namespace ento;
29 using namespace iterator;
30 
31 namespace {
32 
33 class ContainerModeling
34   : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
35 
36   void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
37                    SVal Cont) const;
38   void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
39                  SVal Cont) const;
40   void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
41                         SVal OldCont = UndefinedVal()) const;
42   void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
43   void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
44   void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
45   void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
46   void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
47   void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
48   void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const;
49   void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const;
50   void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const;
51   void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const;
52   void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1,
53                         SVal Iter2) const;
54   const NoteTag *getChangeTag(CheckerContext &C, StringRef Text,
55                               const MemRegion *ContReg,
56                               const Expr *ContE) const;
57   void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
58                   const char *Sep) const override;
59 
60 public:
61   ContainerModeling() = default;
62 
63   void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
64   void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
65   void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
66 
67   using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
68                                                   const Expr *) const;
69   using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
70                                                    SVal) const;
71   using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal,
72                                                    SVal) const;
73 
74   CallDescriptionMap<NoItParamFn> NoIterParamFunctions = {
75     {{0, "clear", 0},
76      &ContainerModeling::handleClear},
77     {{0, "assign", 2},
78      &ContainerModeling::handleAssign},
79     {{0, "push_back", 1},
80      &ContainerModeling::handlePushBack},
81     {{0, "emplace_back", 1},
82      &ContainerModeling::handlePushBack},
83     {{0, "pop_back", 0},
84      &ContainerModeling::handlePopBack},
85     {{0, "push_front", 1},
86      &ContainerModeling::handlePushFront},
87     {{0, "emplace_front", 1},
88      &ContainerModeling::handlePushFront},
89     {{0, "pop_front", 0},
90      &ContainerModeling::handlePopFront},
91   };
92 
93   CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
94     {{0, "insert", 2},
95      &ContainerModeling::handleInsert},
96     {{0, "emplace", 2},
97      &ContainerModeling::handleInsert},
98     {{0, "erase", 1},
99      &ContainerModeling::handleErase},
100     {{0, "erase_after", 1},
101      &ContainerModeling::handleEraseAfter},
102   };
103 
104   CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
105     {{0, "erase", 2},
106      &ContainerModeling::handleErase},
107     {{0, "erase_after", 2},
108      &ContainerModeling::handleEraseAfter},
109   };
110 
111 };
112 
113 bool isBeginCall(const FunctionDecl *Func);
114 bool isEndCall(const FunctionDecl *Func);
115 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
116 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
117 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
118 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
119 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
120 ProgramStateRef createContainerBegin(ProgramStateRef State,
121                                      const MemRegion *Cont, const Expr *E,
122                                      QualType T, const LocationContext *LCtx,
123                                      unsigned BlockCount);
124 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
125                                    const Expr *E, QualType T,
126                                    const LocationContext *LCtx,
127                                    unsigned BlockCount);
128 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
129                                  const ContainerData &CData);
130 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
131                                                const MemRegion *Cont);
132 ProgramStateRef
133 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
134                                      const MemRegion *Cont, SymbolRef Offset,
135                                      BinaryOperator::Opcode Opc);
136 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
137                                             SymbolRef Offset,
138                                             BinaryOperator::Opcode Opc);
139 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
140                                             SymbolRef Offset1,
141                                             BinaryOperator::Opcode Opc1,
142                                             SymbolRef Offset2,
143                                             BinaryOperator::Opcode Opc2);
144 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
145                                              const MemRegion *Cont,
146                                              const MemRegion *NewCont);
147 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
148                                                    const MemRegion *Cont,
149                                                    const MemRegion *NewCont,
150                                                    SymbolRef Offset,
151                                                    BinaryOperator::Opcode Opc);
152 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
153     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
154     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
155 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
156                         SymbolRef OldSym, SymbolRef NewSym);
157 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
158 
159 } // namespace
160 
161 void ContainerModeling::checkPostCall(const CallEvent &Call,
162                                      CheckerContext &C) const {
163   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
164   if (!Func)
165     return;
166 
167   if (Func->isOverloadedOperator()) {
168     const auto Op = Func->getOverloadedOperator();
169     if (Op == OO_Equal) {
170       // Overloaded 'operator=' must be a non-static member function.
171       const auto *InstCall = cast<CXXInstanceCall>(&Call);
172       if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
173         handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
174                      Call.getArgSVal(0));
175         return;
176       }
177 
178       handleAssignment(C, InstCall->getCXXThisVal());
179       return;
180     }
181   } else {
182     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
183       const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
184       if (Handler0) {
185         (this->**Handler0)(C, InstCall->getCXXThisVal(),
186                            InstCall->getCXXThisExpr());
187         return;
188       }
189 
190       const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
191       if (Handler1) {
192         (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
193         return;
194       }
195 
196       const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
197       if (Handler2) {
198         (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
199                            Call.getArgSVal(1));
200         return;
201       }
202 
203       const auto *OrigExpr = Call.getOriginExpr();
204       if (!OrigExpr)
205         return;
206 
207       if (isBeginCall(Func)) {
208         handleBegin(C, OrigExpr, Call.getReturnValue(),
209                     InstCall->getCXXThisVal());
210         return;
211       }
212 
213       if (isEndCall(Func)) {
214         handleEnd(C, OrigExpr, Call.getReturnValue(),
215                   InstCall->getCXXThisVal());
216         return;
217       }
218     }
219   }
220 }
221 
222 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
223                                          SymbolReaper &SR) const {
224   // Keep symbolic expressions of container begins and ends alive
225   auto ContMap = State->get<ContainerMap>();
226   for (const auto &Cont : ContMap) {
227     const auto CData = Cont.second;
228     if (CData.getBegin()) {
229       SR.markLive(CData.getBegin());
230       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
231         SR.markLive(SIE->getLHS());
232     }
233     if (CData.getEnd()) {
234       SR.markLive(CData.getEnd());
235       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
236         SR.markLive(SIE->getLHS());
237     }
238   }
239 }
240 
241 void ContainerModeling::checkDeadSymbols(SymbolReaper &SR,
242                                          CheckerContext &C) const {
243   // Cleanup
244   auto State = C.getState();
245 
246   auto ContMap = State->get<ContainerMap>();
247   for (const auto &Cont : ContMap) {
248     if (!SR.isLiveRegion(Cont.first)) {
249       // We must keep the container data while it has live iterators to be able
250       // to compare them to the begin and the end of the container.
251       if (!hasLiveIterators(State, Cont.first)) {
252         State = State->remove<ContainerMap>(Cont.first);
253       }
254     }
255   }
256 
257   C.addTransition(State);
258 }
259 
260 void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE,
261                                    SVal RetVal, SVal Cont) const {
262   const auto *ContReg = Cont.getAsRegion();
263   if (!ContReg)
264     return;
265 
266   ContReg = ContReg->getMostDerivedObjectRegion();
267 
268   // If the container already has a begin symbol then use it. Otherwise first
269   // create a new one.
270   auto State = C.getState();
271   auto BeginSym = getContainerBegin(State, ContReg);
272   if (!BeginSym) {
273     State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
274                                  C.getLocationContext(), C.blockCount());
275     BeginSym = getContainerBegin(State, ContReg);
276   }
277   State = setIteratorPosition(State, RetVal,
278                               IteratorPosition::getPosition(ContReg, BeginSym));
279   C.addTransition(State);
280 }
281 
282 void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE,
283                                  SVal RetVal, SVal Cont) const {
284   const auto *ContReg = Cont.getAsRegion();
285   if (!ContReg)
286     return;
287 
288   ContReg = ContReg->getMostDerivedObjectRegion();
289 
290   // If the container already has an end symbol then use it. Otherwise first
291   // create a new one.
292   auto State = C.getState();
293   auto EndSym = getContainerEnd(State, ContReg);
294   if (!EndSym) {
295     State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
296                                C.getLocationContext(), C.blockCount());
297     EndSym = getContainerEnd(State, ContReg);
298   }
299   State = setIteratorPosition(State, RetVal,
300                               IteratorPosition::getPosition(ContReg, EndSym));
301   C.addTransition(State);
302 }
303 
304 void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
305                                          const Expr *CE, SVal OldCont) const {
306   const auto *ContReg = Cont.getAsRegion();
307   if (!ContReg)
308     return;
309 
310   ContReg = ContReg->getMostDerivedObjectRegion();
311 
312   // Assignment of a new value to a container always invalidates all its
313   // iterators
314   auto State = C.getState();
315   const auto CData = getContainerData(State, ContReg);
316   if (CData) {
317     State = invalidateAllIteratorPositions(State, ContReg);
318   }
319 
320   // In case of move, iterators of the old container (except the past-end
321   // iterators) remain valid but refer to the new container
322   if (!OldCont.isUndef()) {
323     const auto *OldContReg = OldCont.getAsRegion();
324     if (OldContReg) {
325       OldContReg = OldContReg->getMostDerivedObjectRegion();
326       const auto OldCData = getContainerData(State, OldContReg);
327       if (OldCData) {
328         if (const auto OldEndSym = OldCData->getEnd()) {
329           // If we already assigned an "end" symbol to the old container, then
330           // first reassign all iterator positions to the new container which
331           // are not past the container (thus not greater or equal to the
332           // current "end" symbol).
333           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
334                                                      OldEndSym, BO_GE);
335           auto &SymMgr = C.getSymbolManager();
336           auto &SVB = C.getSValBuilder();
337           // Then generate and assign a new "end" symbol for the new container.
338           auto NewEndSym =
339               SymMgr.conjureSymbol(CE, C.getLocationContext(),
340                                    C.getASTContext().LongTy, C.blockCount());
341           State = assumeNoOverflow(State, NewEndSym, 4);
342           if (CData) {
343             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
344           } else {
345             State = setContainerData(State, ContReg,
346                                      ContainerData::fromEnd(NewEndSym));
347           }
348           // Finally, replace the old "end" symbol in the already reassigned
349           // iterator positions with the new "end" symbol.
350           State = rebaseSymbolInIteratorPositionsIf(
351               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
352         } else {
353           // There was no "end" symbol assigned yet to the old container,
354           // so reassign all iterator positions to the new container.
355           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
356         }
357         if (const auto OldBeginSym = OldCData->getBegin()) {
358           // If we already assigned a "begin" symbol to the old container, then
359           // assign it to the new container and remove it from the old one.
360           if (CData) {
361             State =
362                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
363           } else {
364             State = setContainerData(State, ContReg,
365                                      ContainerData::fromBegin(OldBeginSym));
366           }
367           State =
368               setContainerData(State, OldContReg, OldCData->newBegin(nullptr));
369         }
370       } else {
371         // There was neither "begin" nor "end" symbol assigned yet to the old
372         // container, so reassign all iterator positions to the new container.
373         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
374       }
375     }
376   }
377   C.addTransition(State);
378 }
379 
380 void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
381                                      const Expr *ContE) const {
382   const auto *ContReg = Cont.getAsRegion();
383   if (!ContReg)
384     return;
385 
386   ContReg = ContReg->getMostDerivedObjectRegion();
387 
388   // The assign() operation invalidates all the iterators
389   auto State = C.getState();
390   State = invalidateAllIteratorPositions(State, ContReg);
391   C.addTransition(State);
392 }
393 
394 void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
395                                     const Expr *ContE) const {
396   const auto *ContReg = Cont.getAsRegion();
397   if (!ContReg)
398     return;
399 
400   ContReg = ContReg->getMostDerivedObjectRegion();
401 
402   // The clear() operation invalidates all the iterators, except the past-end
403   // iterators of list-like containers
404   auto State = C.getState();
405   if (!hasSubscriptOperator(State, ContReg) ||
406       !backModifiable(State, ContReg)) {
407     const auto CData = getContainerData(State, ContReg);
408     if (CData) {
409       if (const auto EndSym = CData->getEnd()) {
410         State =
411             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
412         C.addTransition(State);
413         return;
414       }
415     }
416   }
417   const NoteTag *ChangeTag =
418     getChangeTag(C, "became empty", ContReg, ContE);
419   State = invalidateAllIteratorPositions(State, ContReg);
420   C.addTransition(State, ChangeTag);
421 }
422 
423 void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
424                                        const Expr *ContE) const {
425   const auto *ContReg = Cont.getAsRegion();
426   if (!ContReg)
427     return;
428 
429   ContReg = ContReg->getMostDerivedObjectRegion();
430 
431   // For deque-like containers invalidate all iterator positions
432   auto State = C.getState();
433   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
434     State = invalidateAllIteratorPositions(State, ContReg);
435     C.addTransition(State);
436     return;
437   }
438 
439   const auto CData = getContainerData(State, ContReg);
440   if (!CData)
441     return;
442 
443   // For vector-like containers invalidate the past-end iterator positions
444   if (const auto EndSym = CData->getEnd()) {
445     if (hasSubscriptOperator(State, ContReg)) {
446       State = invalidateIteratorPositions(State, EndSym, BO_GE);
447     }
448     auto &SymMgr = C.getSymbolManager();
449     auto &BVF = SymMgr.getBasicVals();
450     auto &SVB = C.getSValBuilder();
451     const auto newEndSym =
452       SVB.evalBinOp(State, BO_Add,
453                     nonloc::SymbolVal(EndSym),
454                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
455                     SymMgr.getType(EndSym)).getAsSymbol();
456     const NoteTag *ChangeTag =
457       getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
458     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
459     C.addTransition(State, ChangeTag);
460   }
461 }
462 
463 void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
464                                       const Expr *ContE) const {
465   const auto *ContReg = Cont.getAsRegion();
466   if (!ContReg)
467     return;
468 
469   ContReg = ContReg->getMostDerivedObjectRegion();
470 
471   auto State = C.getState();
472   const auto CData = getContainerData(State, ContReg);
473   if (!CData)
474     return;
475 
476   if (const auto EndSym = CData->getEnd()) {
477     auto &SymMgr = C.getSymbolManager();
478     auto &BVF = SymMgr.getBasicVals();
479     auto &SVB = C.getSValBuilder();
480     const auto BackSym =
481       SVB.evalBinOp(State, BO_Sub,
482                     nonloc::SymbolVal(EndSym),
483                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
484                     SymMgr.getType(EndSym)).getAsSymbol();
485     const NoteTag *ChangeTag =
486       getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE);
487     // For vector-like and deque-like containers invalidate the last and the
488     // past-end iterator positions. For list-like containers only invalidate
489     // the last position
490     if (hasSubscriptOperator(State, ContReg) &&
491         backModifiable(State, ContReg)) {
492       State = invalidateIteratorPositions(State, BackSym, BO_GE);
493       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
494     } else {
495       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
496     }
497     auto newEndSym = BackSym;
498     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
499     C.addTransition(State, ChangeTag);
500   }
501 }
502 
503 void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
504                                         const Expr *ContE) const {
505   const auto *ContReg = Cont.getAsRegion();
506   if (!ContReg)
507     return;
508 
509   ContReg = ContReg->getMostDerivedObjectRegion();
510 
511   // For deque-like containers invalidate all iterator positions
512   auto State = C.getState();
513   if (hasSubscriptOperator(State, ContReg)) {
514     State = invalidateAllIteratorPositions(State, ContReg);
515     C.addTransition(State);
516   } else {
517     const auto CData = getContainerData(State, ContReg);
518     if (!CData)
519       return;
520 
521     if (const auto BeginSym = CData->getBegin()) {
522       auto &SymMgr = C.getSymbolManager();
523       auto &BVF = SymMgr.getBasicVals();
524       auto &SVB = C.getSValBuilder();
525       const auto newBeginSym =
526         SVB.evalBinOp(State, BO_Sub,
527                       nonloc::SymbolVal(BeginSym),
528                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
529                       SymMgr.getType(BeginSym)).getAsSymbol();
530       const NoteTag *ChangeTag =
531         getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
532       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
533       C.addTransition(State, ChangeTag);
534     }
535   }
536 }
537 
538 void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
539                                        const Expr *ContE) const {
540   const auto *ContReg = Cont.getAsRegion();
541   if (!ContReg)
542     return;
543 
544   ContReg = ContReg->getMostDerivedObjectRegion();
545 
546   auto State = C.getState();
547   const auto CData = getContainerData(State, ContReg);
548   if (!CData)
549     return;
550 
551   // For deque-like containers invalidate all iterator positions. For list-like
552   // iterators only invalidate the first position
553   if (const auto BeginSym = CData->getBegin()) {
554     if (hasSubscriptOperator(State, ContReg)) {
555       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
556     } else {
557       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
558     }
559     auto &SymMgr = C.getSymbolManager();
560     auto &BVF = SymMgr.getBasicVals();
561     auto &SVB = C.getSValBuilder();
562     const auto newBeginSym =
563       SVB.evalBinOp(State, BO_Add,
564                     nonloc::SymbolVal(BeginSym),
565                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
566                     SymMgr.getType(BeginSym)).getAsSymbol();
567     const NoteTag *ChangeTag =
568       getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
569     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
570     C.addTransition(State, ChangeTag);
571   }
572 }
573 
574 void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
575                                      SVal Iter) const {
576   const auto *ContReg = Cont.getAsRegion();
577   if (!ContReg)
578     return;
579 
580   ContReg = ContReg->getMostDerivedObjectRegion();
581 
582   auto State = C.getState();
583   const auto *Pos = getIteratorPosition(State, Iter);
584   if (!Pos)
585     return;
586 
587   // For deque-like containers invalidate all iterator positions. For
588   // vector-like containers invalidate iterator positions after the insertion.
589   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
590     if (frontModifiable(State, ContReg)) {
591       State = invalidateAllIteratorPositions(State, ContReg);
592     } else {
593       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
594     }
595     if (const auto *CData = getContainerData(State, ContReg)) {
596       if (const auto EndSym = CData->getEnd()) {
597         State = invalidateIteratorPositions(State, EndSym, BO_GE);
598         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
599       }
600     }
601     C.addTransition(State);
602   }
603 }
604 
605 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
606                                     SVal Iter) const {
607   const auto *ContReg = Cont.getAsRegion();
608   if (!ContReg)
609     return;
610 
611   ContReg = ContReg->getMostDerivedObjectRegion();
612 
613   auto State = C.getState();
614   const auto *Pos = getIteratorPosition(State, Iter);
615   if (!Pos)
616     return;
617 
618   // For deque-like containers invalidate all iterator positions. For
619   // vector-like containers invalidate iterator positions at and after the
620   // deletion. For list-like containers only invalidate the deleted position.
621   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
622     if (frontModifiable(State, ContReg)) {
623       State = invalidateAllIteratorPositions(State, ContReg);
624     } else {
625       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
626     }
627     if (const auto *CData = getContainerData(State, ContReg)) {
628       if (const auto EndSym = CData->getEnd()) {
629         State = invalidateIteratorPositions(State, EndSym, BO_GE);
630         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
631       }
632     }
633   } else {
634     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
635   }
636   C.addTransition(State);
637 }
638 
639 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
640                                     SVal Iter2) const {
641   const auto *ContReg = Cont.getAsRegion();
642   if (!ContReg)
643     return;
644 
645   ContReg = ContReg->getMostDerivedObjectRegion();
646   auto State = C.getState();
647   const auto *Pos1 = getIteratorPosition(State, Iter1);
648   const auto *Pos2 = getIteratorPosition(State, Iter2);
649   if (!Pos1 || !Pos2)
650     return;
651 
652   // For deque-like containers invalidate all iterator positions. For
653   // vector-like containers invalidate iterator positions at and after the
654   // deletion range. For list-like containers only invalidate the deleted
655   // position range [first..last].
656   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
657     if (frontModifiable(State, ContReg)) {
658       State = invalidateAllIteratorPositions(State, ContReg);
659     } else {
660       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
661     }
662     if (const auto *CData = getContainerData(State, ContReg)) {
663       if (const auto EndSym = CData->getEnd()) {
664         State = invalidateIteratorPositions(State, EndSym, BO_GE);
665         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
666       }
667     }
668   } else {
669     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
670                                         Pos2->getOffset(), BO_LT);
671   }
672   C.addTransition(State);
673 }
674 
675 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
676                                         SVal Iter) const {
677   auto State = C.getState();
678   const auto *Pos = getIteratorPosition(State, Iter);
679   if (!Pos)
680     return;
681 
682   // Invalidate the deleted iterator position, which is the position of the
683   // parameter plus one.
684   auto &SymMgr = C.getSymbolManager();
685   auto &BVF = SymMgr.getBasicVals();
686   auto &SVB = C.getSValBuilder();
687   const auto NextSym =
688     SVB.evalBinOp(State, BO_Add,
689                   nonloc::SymbolVal(Pos->getOffset()),
690                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
691                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
692   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
693   C.addTransition(State);
694 }
695 
696 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
697                                          SVal Iter1, SVal Iter2) const {
698   auto State = C.getState();
699   const auto *Pos1 = getIteratorPosition(State, Iter1);
700   const auto *Pos2 = getIteratorPosition(State, Iter2);
701   if (!Pos1 || !Pos2)
702     return;
703 
704   // Invalidate the deleted iterator position range (first..last)
705   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
706                                       Pos2->getOffset(), BO_LT);
707   C.addTransition(State);
708 }
709 
710 const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C,
711                                                StringRef Text,
712                                                const MemRegion *ContReg,
713                                                const Expr *ContE) const {
714   StringRef Name;
715   // First try to get the name of the variable from the region
716   if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
717     Name = DR->getDecl()->getName();
718   // If the region is not a `DeclRegion` then use the expression instead
719   } else if (const auto *DRE =
720              dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) {
721     Name = DRE->getDecl()->getName();
722   }
723 
724   return C.getNoteTag(
725       [Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string {
726         if (!BR.isInteresting(ContReg))
727           return "";
728 
729         SmallString<256> Msg;
730         llvm::raw_svector_ostream Out(Msg);
731         Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" )
732             << Text;
733         return std::string(Out.str());
734       });
735 }
736 
737 void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State,
738                                   const char *NL, const char *Sep) const {
739   auto ContMap = State->get<ContainerMap>();
740 
741   if (!ContMap.isEmpty()) {
742     Out << Sep << "Container Data :" << NL;
743     for (const auto &Cont : ContMap) {
744       Cont.first->dumpToStream(Out);
745       Out << " : [ ";
746       const auto CData = Cont.second;
747       if (CData.getBegin())
748         CData.getBegin()->dumpToStream(Out);
749       else
750         Out << "<Unknown>";
751       Out << " .. ";
752       if (CData.getEnd())
753         CData.getEnd()->dumpToStream(Out);
754       else
755         Out << "<Unknown>";
756       Out << " ]";
757     }
758   }
759 }
760 
761 namespace {
762 
763 bool isBeginCall(const FunctionDecl *Func) {
764   const auto *IdInfo = Func->getIdentifier();
765   if (!IdInfo)
766     return false;
767   return IdInfo->getName().endswith_insensitive("begin");
768 }
769 
770 bool isEndCall(const FunctionDecl *Func) {
771   const auto *IdInfo = Func->getIdentifier();
772   if (!IdInfo)
773     return false;
774   return IdInfo->getName().endswith_insensitive("end");
775 }
776 
777 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
778                                       const MemRegion *Reg) {
779   auto TI = getDynamicTypeInfo(State, Reg);
780   if (!TI.isValid())
781     return nullptr;
782 
783   auto Type = TI.getType();
784   if (const auto *RefT = Type->getAs<ReferenceType>()) {
785     Type = RefT->getPointeeType();
786   }
787 
788   return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
789 }
790 
791 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
792   const auto *CRD = getCXXRecordDecl(State, Reg);
793   if (!CRD)
794     return false;
795 
796   for (const auto *Method : CRD->methods()) {
797     if (!Method->isOverloadedOperator())
798       continue;
799     const auto OPK = Method->getOverloadedOperator();
800     if (OPK == OO_Subscript) {
801       return true;
802     }
803   }
804   return false;
805 }
806 
807 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
808   const auto *CRD = getCXXRecordDecl(State, Reg);
809   if (!CRD)
810     return false;
811 
812   for (const auto *Method : CRD->methods()) {
813     if (!Method->getDeclName().isIdentifier())
814       continue;
815     if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
816       return true;
817     }
818   }
819   return false;
820 }
821 
822 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
823   const auto *CRD = getCXXRecordDecl(State, Reg);
824   if (!CRD)
825     return false;
826 
827   for (const auto *Method : CRD->methods()) {
828     if (!Method->getDeclName().isIdentifier())
829       continue;
830     if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
831       return true;
832     }
833   }
834   return false;
835 }
836 
837 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
838   const auto *CDataPtr = getContainerData(State, Cont);
839   if (!CDataPtr)
840     return nullptr;
841 
842   return CDataPtr->getBegin();
843 }
844 
845 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
846   const auto *CDataPtr = getContainerData(State, Cont);
847   if (!CDataPtr)
848     return nullptr;
849 
850   return CDataPtr->getEnd();
851 }
852 
853 ProgramStateRef createContainerBegin(ProgramStateRef State,
854                                      const MemRegion *Cont, const Expr *E,
855                                      QualType T, const LocationContext *LCtx,
856                                      unsigned BlockCount) {
857   // Only create if it does not exist
858   const auto *CDataPtr = getContainerData(State, Cont);
859   if (CDataPtr && CDataPtr->getBegin())
860     return State;
861 
862   auto &SymMgr = State->getSymbolManager();
863   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
864                                                    "begin");
865   State = assumeNoOverflow(State, Sym, 4);
866 
867   if (CDataPtr) {
868     const auto CData = CDataPtr->newBegin(Sym);
869     return setContainerData(State, Cont, CData);
870   }
871 
872   const auto CData = ContainerData::fromBegin(Sym);
873   return setContainerData(State, Cont, CData);
874 }
875 
876 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
877                                    const Expr *E, QualType T,
878                                    const LocationContext *LCtx,
879                                    unsigned BlockCount) {
880   // Only create if it does not exist
881   const auto *CDataPtr = getContainerData(State, Cont);
882   if (CDataPtr && CDataPtr->getEnd())
883     return State;
884 
885   auto &SymMgr = State->getSymbolManager();
886   const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
887                                                   "end");
888   State = assumeNoOverflow(State, Sym, 4);
889 
890   if (CDataPtr) {
891     const auto CData = CDataPtr->newEnd(Sym);
892     return setContainerData(State, Cont, CData);
893   }
894 
895   const auto CData = ContainerData::fromEnd(Sym);
896   return setContainerData(State, Cont, CData);
897 }
898 
899 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
900                                  const ContainerData &CData) {
901   return State->set<ContainerMap>(Cont, CData);
902 }
903 
904 template <typename Condition, typename Process>
905 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
906                                          Process Proc) {
907   auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
908   auto RegionMap = State->get<IteratorRegionMap>();
909   bool Changed = false;
910   for (const auto &Reg : RegionMap) {
911     if (Cond(Reg.second)) {
912       RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
913       Changed = true;
914     }
915   }
916 
917   if (Changed)
918     State = State->set<IteratorRegionMap>(RegionMap);
919 
920   auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
921   auto SymbolMap = State->get<IteratorSymbolMap>();
922   Changed = false;
923   for (const auto &Sym : SymbolMap) {
924     if (Cond(Sym.second)) {
925       SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
926       Changed = true;
927     }
928   }
929 
930   if (Changed)
931     State = State->set<IteratorSymbolMap>(SymbolMap);
932 
933   return State;
934 }
935 
936 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
937                                                const MemRegion *Cont) {
938   auto MatchCont = [&](const IteratorPosition &Pos) {
939     return Pos.getContainer() == Cont;
940   };
941   auto Invalidate = [&](const IteratorPosition &Pos) {
942     return Pos.invalidate();
943   };
944   return processIteratorPositions(State, MatchCont, Invalidate);
945 }
946 
947 ProgramStateRef
948 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
949                                      const MemRegion *Cont, SymbolRef Offset,
950                                      BinaryOperator::Opcode Opc) {
951   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
952     return Pos.getContainer() == Cont &&
953            !compare(State, Pos.getOffset(), Offset, Opc);
954   };
955   auto Invalidate = [&](const IteratorPosition &Pos) {
956     return Pos.invalidate();
957   };
958   return processIteratorPositions(State, MatchContAndCompare, Invalidate);
959 }
960 
961 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
962                                             SymbolRef Offset,
963                                             BinaryOperator::Opcode Opc) {
964   auto Compare = [&](const IteratorPosition &Pos) {
965     return compare(State, Pos.getOffset(), Offset, Opc);
966   };
967   auto Invalidate = [&](const IteratorPosition &Pos) {
968     return Pos.invalidate();
969   };
970   return processIteratorPositions(State, Compare, Invalidate);
971 }
972 
973 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
974                                             SymbolRef Offset1,
975                                             BinaryOperator::Opcode Opc1,
976                                             SymbolRef Offset2,
977                                             BinaryOperator::Opcode Opc2) {
978   auto Compare = [&](const IteratorPosition &Pos) {
979     return compare(State, Pos.getOffset(), Offset1, Opc1) &&
980            compare(State, Pos.getOffset(), Offset2, Opc2);
981   };
982   auto Invalidate = [&](const IteratorPosition &Pos) {
983     return Pos.invalidate();
984   };
985   return processIteratorPositions(State, Compare, Invalidate);
986 }
987 
988 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
989                                              const MemRegion *Cont,
990                                              const MemRegion *NewCont) {
991   auto MatchCont = [&](const IteratorPosition &Pos) {
992     return Pos.getContainer() == Cont;
993   };
994   auto ReAssign = [&](const IteratorPosition &Pos) {
995     return Pos.reAssign(NewCont);
996   };
997   return processIteratorPositions(State, MatchCont, ReAssign);
998 }
999 
1000 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
1001                                                    const MemRegion *Cont,
1002                                                    const MemRegion *NewCont,
1003                                                    SymbolRef Offset,
1004                                                    BinaryOperator::Opcode Opc) {
1005   auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1006     return Pos.getContainer() == Cont &&
1007     !compare(State, Pos.getOffset(), Offset, Opc);
1008   };
1009   auto ReAssign = [&](const IteratorPosition &Pos) {
1010     return Pos.reAssign(NewCont);
1011   };
1012   return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1013 }
1014 
1015 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1016 // `OldSym - Int` to `NewSym - Int` and  `OldSym` to `NewSym` in any iterator
1017 // position offsets where `CondSym` is true.
1018 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1019     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1020     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1021   auto LessThanEnd = [&](const IteratorPosition &Pos) {
1022     return compare(State, Pos.getOffset(), CondSym, Opc);
1023   };
1024   auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1025     return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1026                                    NewSym));
1027   };
1028   return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1029 }
1030 
1031 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1032 // `OldExpr - Int` to `NewExpr - Int` and  `OldExpr` to `NewExpr` in expression
1033 // `OrigExpr`.
1034 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1035                        SymbolRef OrigExpr, SymbolRef OldExpr,
1036                        SymbolRef NewSym) {
1037   auto &SymMgr = SVB.getSymbolManager();
1038   auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1039                               nonloc::SymbolVal(OldExpr),
1040                               SymMgr.getType(OrigExpr));
1041 
1042   const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1043   if (!DiffInt)
1044     return OrigExpr;
1045 
1046   return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1047                          SymMgr.getType(OrigExpr)).getAsSymbol();
1048 }
1049 
1050 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1051   auto RegionMap = State->get<IteratorRegionMap>();
1052   for (const auto &Reg : RegionMap) {
1053     if (Reg.second.getContainer() == Cont)
1054       return true;
1055   }
1056 
1057   auto SymbolMap = State->get<IteratorSymbolMap>();
1058   for (const auto &Sym : SymbolMap) {
1059     if (Sym.second.getContainer() == Cont)
1060       return true;
1061   }
1062 
1063   return false;
1064 }
1065 
1066 } // namespace
1067 
1068 void ento::registerContainerModeling(CheckerManager &mgr) {
1069   mgr.registerChecker<ContainerModeling>();
1070 }
1071 
1072 bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) {
1073   if (!mgr.getLangOpts().CPlusPlus)
1074     return false;
1075 
1076   if (!mgr.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) {
1077     mgr.getASTContext().getDiagnostics().Report(
1078         diag::err_analyzer_checker_incompatible_analyzer_option)
1079       << "aggressive-binary-operation-simplification" << "false";
1080     return false;
1081   }
1082 
1083   return true;
1084 }
1085