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