xref: /freebsd/contrib/llvm-project/clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp (revision 770cf0a5f02dc8983a89c6568d741fbc25baa999) 
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/Checker.h"
17 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.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, ConstCFGElementRef Elem, SVal RetVal,
36                    SVal Cont) const;
37   void handleEnd(CheckerContext &C, ConstCFGElementRef Elem, SVal RetVal,
38                  SVal Cont) const;
39   void handleAssignment(CheckerContext &C, SVal Cont, ConstCFGElementRef Elem,
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       {{CDM::CXXMethod, {"clear"}, 0}, &ContainerModeling::handleClear},
75       {{CDM::CXXMethod, {"assign"}, 2}, &ContainerModeling::handleAssign},
76       {{CDM::CXXMethod, {"push_back"}, 1}, &ContainerModeling::handlePushBack},
77       {{CDM::CXXMethod, {"emplace_back"}, 1},
78        &ContainerModeling::handlePushBack},
79       {{CDM::CXXMethod, {"pop_back"}, 0}, &ContainerModeling::handlePopBack},
80       {{CDM::CXXMethod, {"push_front"}, 1},
81        &ContainerModeling::handlePushFront},
82       {{CDM::CXXMethod, {"emplace_front"}, 1},
83        &ContainerModeling::handlePushFront},
84       {{CDM::CXXMethod, {"pop_front"}, 0}, &ContainerModeling::handlePopFront},
85   };
86 
87   CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
88       {{CDM::CXXMethod, {"insert"}, 2}, &ContainerModeling::handleInsert},
89       {{CDM::CXXMethod, {"emplace"}, 2}, &ContainerModeling::handleInsert},
90       {{CDM::CXXMethod, {"erase"}, 1}, &ContainerModeling::handleErase},
91       {{CDM::CXXMethod, {"erase_after"}, 1},
92        &ContainerModeling::handleEraseAfter},
93   };
94 
95   CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
96       {{CDM::CXXMethod, {"erase"}, 2}, &ContainerModeling::handleErase},
97       {{CDM::CXXMethod, {"erase_after"}, 2},
98        &ContainerModeling::handleEraseAfter},
99   };
100 };
101 
102 bool isBeginCall(const FunctionDecl *Func);
103 bool isEndCall(const FunctionDecl *Func);
104 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
105 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
106 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
107 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
108 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
109 ProgramStateRef createContainerBegin(ProgramStateRef State,
110                                      const MemRegion *Cont,
111                                      ConstCFGElementRef Elem, QualType T,
112                                      const LocationContext *LCtx,
113                                      unsigned BlockCount);
114 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
115                                    ConstCFGElementRef Elem, QualType T,
116                                    const LocationContext *LCtx,
117                                    unsigned BlockCount);
118 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
119                                  const ContainerData &CData);
120 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
121                                                const MemRegion *Cont);
122 ProgramStateRef
123 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
124                                      const MemRegion *Cont, SymbolRef Offset,
125                                      BinaryOperator::Opcode Opc);
126 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
127                                             SymbolRef Offset,
128                                             BinaryOperator::Opcode Opc);
129 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
130                                             SymbolRef Offset1,
131                                             BinaryOperator::Opcode Opc1,
132                                             SymbolRef Offset2,
133                                             BinaryOperator::Opcode Opc2);
134 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
135                                              const MemRegion *Cont,
136                                              const MemRegion *NewCont);
137 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
138                                                    const MemRegion *Cont,
139                                                    const MemRegion *NewCont,
140                                                    SymbolRef Offset,
141                                                    BinaryOperator::Opcode Opc);
142 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
143     ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
144     SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
145 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
146                         SymbolRef OldSym, SymbolRef NewSym);
147 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
148 
149 } // namespace
150 
151 void ContainerModeling::checkPostCall(const CallEvent &Call,
152                                      CheckerContext &C) const {
153   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
154   if (!Func)
155     return;
156 
157   if (Func->isOverloadedOperator()) {
158     const auto Op = Func->getOverloadedOperator();
159     if (Op == OO_Equal) {
160       // Only handle the assignment operator with implicit this
161       const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call);
162       if (!InstCall)
163         return;
164 
165       if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
166         handleAssignment(C, InstCall->getCXXThisVal(), Call.getCFGElementRef(),
167                          Call.getArgSVal(0));
168         return;
169       }
170 
171       handleAssignment(C, InstCall->getCXXThisVal(), C.getCFGElementRef());
172       return;
173     }
174   } else {
175     if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
176       const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
177       if (Handler0) {
178         (this->**Handler0)(C, InstCall->getCXXThisVal(),
179                            InstCall->getCXXThisExpr());
180         return;
181       }
182 
183       const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
184       if (Handler1) {
185         (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
186         return;
187       }
188 
189       const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
190       if (Handler2) {
191         (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
192                            Call.getArgSVal(1));
193         return;
194       }
195 
196       const auto *OrigExpr = Call.getOriginExpr();
197       if (!OrigExpr)
198         return;
199 
200       if (isBeginCall(Func)) {
201         handleBegin(C, Call.getCFGElementRef(), Call.getReturnValue(),
202                     InstCall->getCXXThisVal());
203         return;
204       }
205 
206       if (isEndCall(Func)) {
207         handleEnd(C, Call.getCFGElementRef(), Call.getReturnValue(),
208                   InstCall->getCXXThisVal());
209         return;
210       }
211     }
212   }
213 }
214 
215 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
216                                          SymbolReaper &SR) const {
217   // Keep symbolic expressions of container begins and ends alive
218   auto ContMap = State->get<ContainerMap>();
219   for (const auto &Cont : ContMap) {
220     const auto CData = Cont.second;
221     if (CData.getBegin()) {
222       SR.markLive(CData.getBegin());
223       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
224         SR.markLive(SIE->getLHS());
225     }
226     if (CData.getEnd()) {
227       SR.markLive(CData.getEnd());
228       if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
229         SR.markLive(SIE->getLHS());
230     }
231   }
232 }
233 
234 void ContainerModeling::checkDeadSymbols(SymbolReaper &SR,
235                                          CheckerContext &C) const {
236   // Cleanup
237   auto State = C.getState();
238 
239   auto ContMap = State->get<ContainerMap>();
240   for (const auto &Cont : ContMap) {
241     if (!SR.isLiveRegion(Cont.first)) {
242       // We must keep the container data while it has live iterators to be able
243       // to compare them to the begin and the end of the container.
244       if (!hasLiveIterators(State, Cont.first)) {
245         State = State->remove<ContainerMap>(Cont.first);
246       }
247     }
248   }
249 
250   C.addTransition(State);
251 }
252 
253 void ContainerModeling::handleBegin(CheckerContext &C, ConstCFGElementRef Elem,
254                                     SVal RetVal, SVal Cont) const {
255   const auto *ContReg = Cont.getAsRegion();
256   if (!ContReg)
257     return;
258 
259   ContReg = ContReg->getMostDerivedObjectRegion();
260 
261   // If the container already has a begin symbol then use it. Otherwise first
262   // create a new one.
263   auto State = C.getState();
264   auto BeginSym = getContainerBegin(State, ContReg);
265   if (!BeginSym) {
266     State = createContainerBegin(State, ContReg, Elem, C.getASTContext().LongTy,
267                                  C.getLocationContext(), C.blockCount());
268     BeginSym = getContainerBegin(State, ContReg);
269   }
270   State = setIteratorPosition(State, RetVal,
271                               IteratorPosition::getPosition(ContReg, BeginSym));
272   C.addTransition(State);
273 }
274 
275 void ContainerModeling::handleEnd(CheckerContext &C, ConstCFGElementRef Elem,
276                                   SVal RetVal, SVal Cont) const {
277   const auto *ContReg = Cont.getAsRegion();
278   if (!ContReg)
279     return;
280 
281   ContReg = ContReg->getMostDerivedObjectRegion();
282 
283   // If the container already has an end symbol then use it. Otherwise first
284   // create a new one.
285   auto State = C.getState();
286   auto EndSym = getContainerEnd(State, ContReg);
287   if (!EndSym) {
288     State = createContainerEnd(State, ContReg, Elem, C.getASTContext().LongTy,
289                                C.getLocationContext(), C.blockCount());
290     EndSym = getContainerEnd(State, ContReg);
291   }
292   State = setIteratorPosition(State, RetVal,
293                               IteratorPosition::getPosition(ContReg, EndSym));
294   C.addTransition(State);
295 }
296 
297 void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
298                                          ConstCFGElementRef Elem,
299                                          SVal OldCont) const {
300   const auto *ContReg = Cont.getAsRegion();
301   if (!ContReg)
302     return;
303 
304   ContReg = ContReg->getMostDerivedObjectRegion();
305 
306   // Assignment of a new value to a container always invalidates all its
307   // iterators
308   auto State = C.getState();
309   const auto CData = getContainerData(State, ContReg);
310   if (CData) {
311     State = invalidateAllIteratorPositions(State, ContReg);
312   }
313 
314   // In case of move, iterators of the old container (except the past-end
315   // iterators) remain valid but refer to the new container
316   if (!OldCont.isUndef()) {
317     const auto *OldContReg = OldCont.getAsRegion();
318     if (OldContReg) {
319       OldContReg = OldContReg->getMostDerivedObjectRegion();
320       const auto OldCData = getContainerData(State, OldContReg);
321       if (OldCData) {
322         if (const auto OldEndSym = OldCData->getEnd()) {
323           // If we already assigned an "end" symbol to the old container, then
324           // first reassign all iterator positions to the new container which
325           // are not past the container (thus not greater or equal to the
326           // current "end" symbol).
327           State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
328                                                      OldEndSym, BO_GE);
329           auto &SymMgr = C.getSymbolManager();
330           auto &SVB = C.getSValBuilder();
331           // Then generate and assign a new "end" symbol for the new container.
332           auto NewEndSym =
333               SymMgr.conjureSymbol(Elem, C.getLocationContext(),
334                                    C.getASTContext().LongTy, C.blockCount());
335           State = assumeNoOverflow(State, NewEndSym, 4);
336           if (CData) {
337             State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
338           } else {
339             State = setContainerData(State, ContReg,
340                                      ContainerData::fromEnd(NewEndSym));
341           }
342           // Finally, replace the old "end" symbol in the already reassigned
343           // iterator positions with the new "end" symbol.
344           State = rebaseSymbolInIteratorPositionsIf(
345               State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
346         } else {
347           // There was no "end" symbol assigned yet to the old container,
348           // so reassign all iterator positions to the new container.
349           State = reassignAllIteratorPositions(State, OldContReg, ContReg);
350         }
351         if (const auto OldBeginSym = OldCData->getBegin()) {
352           // If we already assigned a "begin" symbol to the old container, then
353           // assign it to the new container and remove it from the old one.
354           if (CData) {
355             State =
356                 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
357           } else {
358             State = setContainerData(State, ContReg,
359                                      ContainerData::fromBegin(OldBeginSym));
360           }
361           State =
362               setContainerData(State, OldContReg, OldCData->newBegin(nullptr));
363         }
364       } else {
365         // There was neither "begin" nor "end" symbol assigned yet to the old
366         // container, so reassign all iterator positions to the new container.
367         State = reassignAllIteratorPositions(State, OldContReg, ContReg);
368       }
369     }
370   }
371   C.addTransition(State);
372 }
373 
374 void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
375                                      const Expr *ContE) const {
376   const auto *ContReg = Cont.getAsRegion();
377   if (!ContReg)
378     return;
379 
380   ContReg = ContReg->getMostDerivedObjectRegion();
381 
382   // The assign() operation invalidates all the iterators
383   auto State = C.getState();
384   State = invalidateAllIteratorPositions(State, ContReg);
385   C.addTransition(State);
386 }
387 
388 void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
389                                     const Expr *ContE) const {
390   const auto *ContReg = Cont.getAsRegion();
391   if (!ContReg)
392     return;
393 
394   ContReg = ContReg->getMostDerivedObjectRegion();
395 
396   // The clear() operation invalidates all the iterators, except the past-end
397   // iterators of list-like containers
398   auto State = C.getState();
399   if (!hasSubscriptOperator(State, ContReg) ||
400       !backModifiable(State, ContReg)) {
401     const auto CData = getContainerData(State, ContReg);
402     if (CData) {
403       if (const auto EndSym = CData->getEnd()) {
404         State =
405             invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
406         C.addTransition(State);
407         return;
408       }
409     }
410   }
411   const NoteTag *ChangeTag =
412     getChangeTag(C, "became empty", ContReg, ContE);
413   State = invalidateAllIteratorPositions(State, ContReg);
414   C.addTransition(State, ChangeTag);
415 }
416 
417 void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
418                                        const Expr *ContE) const {
419   const auto *ContReg = Cont.getAsRegion();
420   if (!ContReg)
421     return;
422 
423   ContReg = ContReg->getMostDerivedObjectRegion();
424 
425   // For deque-like containers invalidate all iterator positions
426   auto State = C.getState();
427   if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
428     State = invalidateAllIteratorPositions(State, ContReg);
429     C.addTransition(State);
430     return;
431   }
432 
433   const auto CData = getContainerData(State, ContReg);
434   if (!CData)
435     return;
436 
437   // For vector-like containers invalidate the past-end iterator positions
438   if (const auto EndSym = CData->getEnd()) {
439     if (hasSubscriptOperator(State, ContReg)) {
440       State = invalidateIteratorPositions(State, EndSym, BO_GE);
441     }
442     auto &SymMgr = C.getSymbolManager();
443     auto &BVF = SymMgr.getBasicVals();
444     auto &SVB = C.getSValBuilder();
445     const auto newEndSym =
446       SVB.evalBinOp(State, BO_Add,
447                     nonloc::SymbolVal(EndSym),
448                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
449                     SymMgr.getType(EndSym)).getAsSymbol();
450     const NoteTag *ChangeTag =
451       getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
452     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
453     C.addTransition(State, ChangeTag);
454   }
455 }
456 
457 void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
458                                       const Expr *ContE) const {
459   const auto *ContReg = Cont.getAsRegion();
460   if (!ContReg)
461     return;
462 
463   ContReg = ContReg->getMostDerivedObjectRegion();
464 
465   auto State = C.getState();
466   const auto CData = getContainerData(State, ContReg);
467   if (!CData)
468     return;
469 
470   if (const auto EndSym = CData->getEnd()) {
471     auto &SymMgr = C.getSymbolManager();
472     auto &BVF = SymMgr.getBasicVals();
473     auto &SVB = C.getSValBuilder();
474     const auto BackSym =
475       SVB.evalBinOp(State, BO_Sub,
476                     nonloc::SymbolVal(EndSym),
477                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
478                     SymMgr.getType(EndSym)).getAsSymbol();
479     const NoteTag *ChangeTag =
480       getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE);
481     // For vector-like and deque-like containers invalidate the last and the
482     // past-end iterator positions. For list-like containers only invalidate
483     // the last position
484     if (hasSubscriptOperator(State, ContReg) &&
485         backModifiable(State, ContReg)) {
486       State = invalidateIteratorPositions(State, BackSym, BO_GE);
487       State = setContainerData(State, ContReg, CData->newEnd(nullptr));
488     } else {
489       State = invalidateIteratorPositions(State, BackSym, BO_EQ);
490     }
491     auto newEndSym = BackSym;
492     State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
493     C.addTransition(State, ChangeTag);
494   }
495 }
496 
497 void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
498                                         const Expr *ContE) const {
499   const auto *ContReg = Cont.getAsRegion();
500   if (!ContReg)
501     return;
502 
503   ContReg = ContReg->getMostDerivedObjectRegion();
504 
505   // For deque-like containers invalidate all iterator positions
506   auto State = C.getState();
507   if (hasSubscriptOperator(State, ContReg)) {
508     State = invalidateAllIteratorPositions(State, ContReg);
509     C.addTransition(State);
510   } else {
511     const auto CData = getContainerData(State, ContReg);
512     if (!CData)
513       return;
514 
515     if (const auto BeginSym = CData->getBegin()) {
516       auto &SymMgr = C.getSymbolManager();
517       auto &BVF = SymMgr.getBasicVals();
518       auto &SVB = C.getSValBuilder();
519       const auto newBeginSym =
520         SVB.evalBinOp(State, BO_Sub,
521                       nonloc::SymbolVal(BeginSym),
522                       nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
523                       SymMgr.getType(BeginSym)).getAsSymbol();
524       const NoteTag *ChangeTag =
525         getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
526       State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
527       C.addTransition(State, ChangeTag);
528     }
529   }
530 }
531 
532 void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
533                                        const Expr *ContE) const {
534   const auto *ContReg = Cont.getAsRegion();
535   if (!ContReg)
536     return;
537 
538   ContReg = ContReg->getMostDerivedObjectRegion();
539 
540   auto State = C.getState();
541   const auto CData = getContainerData(State, ContReg);
542   if (!CData)
543     return;
544 
545   // For deque-like containers invalidate all iterator positions. For list-like
546   // iterators only invalidate the first position
547   if (const auto BeginSym = CData->getBegin()) {
548     if (hasSubscriptOperator(State, ContReg)) {
549       State = invalidateIteratorPositions(State, BeginSym, BO_LE);
550     } else {
551       State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
552     }
553     auto &SymMgr = C.getSymbolManager();
554     auto &BVF = SymMgr.getBasicVals();
555     auto &SVB = C.getSValBuilder();
556     const auto newBeginSym =
557       SVB.evalBinOp(State, BO_Add,
558                     nonloc::SymbolVal(BeginSym),
559                     nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
560                     SymMgr.getType(BeginSym)).getAsSymbol();
561     const NoteTag *ChangeTag =
562       getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
563     State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
564     C.addTransition(State, ChangeTag);
565   }
566 }
567 
568 void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
569                                      SVal Iter) const {
570   const auto *ContReg = Cont.getAsRegion();
571   if (!ContReg)
572     return;
573 
574   ContReg = ContReg->getMostDerivedObjectRegion();
575 
576   auto State = C.getState();
577   const auto *Pos = getIteratorPosition(State, Iter);
578   if (!Pos)
579     return;
580 
581   // For deque-like containers invalidate all iterator positions. For
582   // vector-like containers invalidate iterator positions after the insertion.
583   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
584     if (frontModifiable(State, ContReg)) {
585       State = invalidateAllIteratorPositions(State, ContReg);
586     } else {
587       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
588     }
589     if (const auto *CData = getContainerData(State, ContReg)) {
590       if (const auto EndSym = CData->getEnd()) {
591         State = invalidateIteratorPositions(State, EndSym, BO_GE);
592         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
593       }
594     }
595     C.addTransition(State);
596   }
597 }
598 
599 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
600                                     SVal Iter) const {
601   const auto *ContReg = Cont.getAsRegion();
602   if (!ContReg)
603     return;
604 
605   ContReg = ContReg->getMostDerivedObjectRegion();
606 
607   auto State = C.getState();
608   const auto *Pos = getIteratorPosition(State, Iter);
609   if (!Pos)
610     return;
611 
612   // For deque-like containers invalidate all iterator positions. For
613   // vector-like containers invalidate iterator positions at and after the
614   // deletion. For list-like containers only invalidate the deleted position.
615   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
616     if (frontModifiable(State, ContReg)) {
617       State = invalidateAllIteratorPositions(State, ContReg);
618     } else {
619       State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
620     }
621     if (const auto *CData = getContainerData(State, ContReg)) {
622       if (const auto EndSym = CData->getEnd()) {
623         State = invalidateIteratorPositions(State, EndSym, BO_GE);
624         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
625       }
626     }
627   } else {
628     State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
629   }
630   C.addTransition(State);
631 }
632 
633 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
634                                     SVal Iter2) const {
635   const auto *ContReg = Cont.getAsRegion();
636   if (!ContReg)
637     return;
638 
639   ContReg = ContReg->getMostDerivedObjectRegion();
640   auto State = C.getState();
641   const auto *Pos1 = getIteratorPosition(State, Iter1);
642   const auto *Pos2 = getIteratorPosition(State, Iter2);
643   if (!Pos1 || !Pos2)
644     return;
645 
646   // For deque-like containers invalidate all iterator positions. For
647   // vector-like containers invalidate iterator positions at and after the
648   // deletion range. For list-like containers only invalidate the deleted
649   // position range [first..last].
650   if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
651     if (frontModifiable(State, ContReg)) {
652       State = invalidateAllIteratorPositions(State, ContReg);
653     } else {
654       State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
655     }
656     if (const auto *CData = getContainerData(State, ContReg)) {
657       if (const auto EndSym = CData->getEnd()) {
658         State = invalidateIteratorPositions(State, EndSym, BO_GE);
659         State = setContainerData(State, ContReg, CData->newEnd(nullptr));
660       }
661     }
662   } else {
663     State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
664                                         Pos2->getOffset(), BO_LT);
665   }
666   C.addTransition(State);
667 }
668 
669 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
670                                         SVal Iter) const {
671   auto State = C.getState();
672   const auto *Pos = getIteratorPosition(State, Iter);
673   if (!Pos)
674     return;
675 
676   // Invalidate the deleted iterator position, which is the position of the
677   // parameter plus one.
678   auto &SymMgr = C.getSymbolManager();
679   auto &BVF = SymMgr.getBasicVals();
680   auto &SVB = C.getSValBuilder();
681   const auto NextSym =
682     SVB.evalBinOp(State, BO_Add,
683                   nonloc::SymbolVal(Pos->getOffset()),
684                   nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
685                   SymMgr.getType(Pos->getOffset())).getAsSymbol();
686   State = invalidateIteratorPositions(State, NextSym, BO_EQ);
687   C.addTransition(State);
688 }
689 
690 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
691                                          SVal Iter1, SVal Iter2) const {
692   auto State = C.getState();
693   const auto *Pos1 = getIteratorPosition(State, Iter1);
694   const auto *Pos2 = getIteratorPosition(State, Iter2);
695   if (!Pos1 || !Pos2)
696     return;
697 
698   // Invalidate the deleted iterator position range (first..last)
699   State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
700                                       Pos2->getOffset(), BO_LT);
701   C.addTransition(State);
702 }
703 
704 const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C,
705                                                StringRef Text,
706                                                const MemRegion *ContReg,
707                                                const Expr *ContE) const {
708   StringRef Name;
709   // First try to get the name of the variable from the region
710   if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
711     Name = DR->getDecl()->getName();
712   // If the region is not a `DeclRegion` then use the expression instead
713   } else if (const auto *DRE =
714              dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) {
715     Name = DRE->getDecl()->getName();
716   }
717 
718   return C.getNoteTag(
719       [Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string {
720         if (!BR.isInteresting(ContReg))
721           return "";
722 
723         SmallString<256> Msg;
724         llvm::raw_svector_ostream Out(Msg);
725         Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" )
726             << Text;
727         return std::string(Out.str());
728       });
729 }
730 
731 void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State,
732                                   const char *NL, const char *Sep) const {
733   auto ContMap = State->get<ContainerMap>();
734 
735   if (!ContMap.isEmpty()) {
736     Out << Sep << "Container Data :" << NL;
737     for (const auto &Cont : ContMap) {
738       Cont.first->dumpToStream(Out);
739       Out << " : [ ";
740       const auto CData = Cont.second;
741       if (CData.getBegin())
742         CData.getBegin()->dumpToStream(Out);
743       else
744         Out << "<Unknown>";
745       Out << " .. ";
746       if (CData.getEnd())
747         CData.getEnd()->dumpToStream(Out);
748       else
749         Out << "<Unknown>";
750       Out << " ]";
751     }
752   }
753 }
754 
755 namespace {
756 
757 bool isBeginCall(const FunctionDecl *Func) {
758   const auto *IdInfo = Func->getIdentifier();
759   if (!IdInfo)
760     return false;
761   return IdInfo->getName().ends_with_insensitive("begin");
762 }
763 
764 bool isEndCall(const FunctionDecl *Func) {
765   const auto *IdInfo = Func->getIdentifier();
766   if (!IdInfo)
767     return false;
768   return IdInfo->getName().ends_with_insensitive("end");
769 }
770 
771 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
772                                       const MemRegion *Reg) {
773   auto TI = getDynamicTypeInfo(State, Reg);
774   if (!TI.isValid())
775     return nullptr;
776 
777   auto Type = TI.getType();
778   if (const auto *RefT = Type->getAs<ReferenceType>()) {
779     Type = RefT->getPointeeType();
780   }
781 
782   if (const auto *PtrT = Type->getAs<PointerType>()) {
783     Type = PtrT->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,
853                                      ConstCFGElementRef Elem, QualType T,
854                                      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 =
863       SymMgr.conjureSymbol(Elem, LCtx, T, BlockCount, "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                                    ConstCFGElementRef Elem, 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 =
886       SymMgr.conjureSymbol(Elem, LCtx, T, BlockCount, "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