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