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