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