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