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