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