1 //===-- ContainerModeling.cpp -------------------------------------*- C++ -*--//
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
7 //===----------------------------------------------------------------------===//
9 // Defines a modeling-checker for modeling STL container-like containers.
11 //===----------------------------------------------------------------------===//
13 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
14 #include "clang/AST/DeclTemplate.h"
15 #include "clang/Driver/DriverDiagnostic.h"
16 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
17 #include "clang/StaticAnalyzer/Core/Checker.h"
18 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
19 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
20 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
26 using namespace clang;
28 using namespace iterator;
32 class ContainerModeling
33 : public Checker<check::PostCall, check::LiveSymbols, check::DeadSymbols> {
35 void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal,
37 void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal,
39 void handleAssignment(CheckerContext &C, SVal Cont, const Expr *CE = nullptr,
40 SVal OldCont = UndefinedVal()) const;
41 void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const;
42 void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const;
43 void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
44 void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const;
45 void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
46 void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const;
47 void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const;
48 void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const;
49 void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const;
50 void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const;
51 void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1,
53 const NoteTag *getChangeTag(CheckerContext &C, StringRef Text,
54 const MemRegion *ContReg,
55 const Expr *ContE) const;
56 void printState(raw_ostream &Out, ProgramStateRef State, const char *NL,
57 const char *Sep) const override;
60 ContainerModeling() = default;
62 void checkPostCall(const CallEvent &Call, CheckerContext &C) const;
63 void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const;
64 void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
66 using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
68 using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal,
70 using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal,
73 CallDescriptionMap<NoItParamFn> NoIterParamFunctions = {
75 &ContainerModeling::handleClear},
77 &ContainerModeling::handleAssign},
79 &ContainerModeling::handlePushBack},
80 {{0, "emplace_back", 1},
81 &ContainerModeling::handlePushBack},
83 &ContainerModeling::handlePopBack},
84 {{0, "push_front", 1},
85 &ContainerModeling::handlePushFront},
86 {{0, "emplace_front", 1},
87 &ContainerModeling::handlePushFront},
89 &ContainerModeling::handlePopFront},
92 CallDescriptionMap<OneItParamFn> OneIterParamFunctions = {
94 &ContainerModeling::handleInsert},
96 &ContainerModeling::handleInsert},
98 &ContainerModeling::handleErase},
99 {{0, "erase_after", 1},
100 &ContainerModeling::handleEraseAfter},
103 CallDescriptionMap<TwoItParamFn> TwoIterParamFunctions = {
105 &ContainerModeling::handleErase},
106 {{0, "erase_after", 2},
107 &ContainerModeling::handleEraseAfter},
112 bool isBeginCall(const FunctionDecl *Func);
113 bool isEndCall(const FunctionDecl *Func);
114 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg);
115 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg);
116 bool backModifiable(ProgramStateRef State, const MemRegion *Reg);
117 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont);
118 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont);
119 ProgramStateRef createContainerBegin(ProgramStateRef State,
120 const MemRegion *Cont, const Expr *E,
121 QualType T, const LocationContext *LCtx,
122 unsigned BlockCount);
123 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
124 const Expr *E, QualType T,
125 const LocationContext *LCtx,
126 unsigned BlockCount);
127 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
128 const ContainerData &CData);
129 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
130 const MemRegion *Cont);
132 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
133 const MemRegion *Cont, SymbolRef Offset,
134 BinaryOperator::Opcode Opc);
135 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
137 BinaryOperator::Opcode Opc);
138 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
140 BinaryOperator::Opcode Opc1,
142 BinaryOperator::Opcode Opc2);
143 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
144 const MemRegion *Cont,
145 const MemRegion *NewCont);
146 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
147 const MemRegion *Cont,
148 const MemRegion *NewCont,
150 BinaryOperator::Opcode Opc);
151 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
152 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
153 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc);
154 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr,
155 SymbolRef OldSym, SymbolRef NewSym);
156 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont);
160 void ContainerModeling::checkPostCall(const CallEvent &Call,
161 CheckerContext &C) const {
162 const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
166 if (Func->isOverloadedOperator()) {
167 const auto Op = Func->getOverloadedOperator();
168 if (Op == OO_Equal) {
169 // Overloaded 'operator=' must be a non-static member function.
170 const auto *InstCall = cast<CXXInstanceCall>(&Call);
171 if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) {
172 handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(),
177 handleAssignment(C, InstCall->getCXXThisVal());
181 if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) {
182 const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call);
184 (this->**Handler0)(C, InstCall->getCXXThisVal(),
185 InstCall->getCXXThisExpr());
189 const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call);
191 (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0));
195 const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call);
197 (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0),
202 const auto *OrigExpr = Call.getOriginExpr();
206 if (isBeginCall(Func)) {
207 handleBegin(C, OrigExpr, Call.getReturnValue(),
208 InstCall->getCXXThisVal());
212 if (isEndCall(Func)) {
213 handleEnd(C, OrigExpr, Call.getReturnValue(),
214 InstCall->getCXXThisVal());
221 void ContainerModeling::checkLiveSymbols(ProgramStateRef State,
222 SymbolReaper &SR) const {
223 // Keep symbolic expressions of container begins and ends alive
224 auto ContMap = State->get<ContainerMap>();
225 for (const auto &Cont : ContMap) {
226 const auto CData = Cont.second;
227 if (CData.getBegin()) {
228 SR.markLive(CData.getBegin());
229 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin()))
230 SR.markLive(SIE->getLHS());
232 if (CData.getEnd()) {
233 SR.markLive(CData.getEnd());
234 if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd()))
235 SR.markLive(SIE->getLHS());
240 void ContainerModeling::checkDeadSymbols(SymbolReaper &SR,
241 CheckerContext &C) const {
243 auto State = C.getState();
245 auto ContMap = State->get<ContainerMap>();
246 for (const auto &Cont : ContMap) {
247 if (!SR.isLiveRegion(Cont.first)) {
248 // We must keep the container data while it has live iterators to be able
249 // to compare them to the begin and the end of the container.
250 if (!hasLiveIterators(State, Cont.first)) {
251 State = State->remove<ContainerMap>(Cont.first);
256 C.addTransition(State);
259 void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE,
260 SVal RetVal, SVal Cont) const {
261 const auto *ContReg = Cont.getAsRegion();
265 ContReg = ContReg->getMostDerivedObjectRegion();
267 // If the container already has a begin symbol then use it. Otherwise first
269 auto State = C.getState();
270 auto BeginSym = getContainerBegin(State, ContReg);
272 State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy,
273 C.getLocationContext(), C.blockCount());
274 BeginSym = getContainerBegin(State, ContReg);
276 State = setIteratorPosition(State, RetVal,
277 IteratorPosition::getPosition(ContReg, BeginSym));
278 C.addTransition(State);
281 void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE,
282 SVal RetVal, SVal Cont) const {
283 const auto *ContReg = Cont.getAsRegion();
287 ContReg = ContReg->getMostDerivedObjectRegion();
289 // If the container already has an end symbol then use it. Otherwise first
291 auto State = C.getState();
292 auto EndSym = getContainerEnd(State, ContReg);
294 State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy,
295 C.getLocationContext(), C.blockCount());
296 EndSym = getContainerEnd(State, ContReg);
298 State = setIteratorPosition(State, RetVal,
299 IteratorPosition::getPosition(ContReg, EndSym));
300 C.addTransition(State);
303 void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont,
304 const Expr *CE, SVal OldCont) const {
305 const auto *ContReg = Cont.getAsRegion();
309 ContReg = ContReg->getMostDerivedObjectRegion();
311 // Assignment of a new value to a container always invalidates all its
313 auto State = C.getState();
314 const auto CData = getContainerData(State, ContReg);
316 State = invalidateAllIteratorPositions(State, ContReg);
319 // In case of move, iterators of the old container (except the past-end
320 // iterators) remain valid but refer to the new container
321 if (!OldCont.isUndef()) {
322 const auto *OldContReg = OldCont.getAsRegion();
324 OldContReg = OldContReg->getMostDerivedObjectRegion();
325 const auto OldCData = getContainerData(State, OldContReg);
327 if (const auto OldEndSym = OldCData->getEnd()) {
328 // If we already assigned an "end" symbol to the old container, then
329 // first reassign all iterator positions to the new container which
330 // are not past the container (thus not greater or equal to the
331 // current "end" symbol).
332 State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg,
334 auto &SymMgr = C.getSymbolManager();
335 auto &SVB = C.getSValBuilder();
336 // Then generate and assign a new "end" symbol for the new container.
338 SymMgr.conjureSymbol(CE, C.getLocationContext(),
339 C.getASTContext().LongTy, C.blockCount());
340 State = assumeNoOverflow(State, NewEndSym, 4);
342 State = setContainerData(State, ContReg, CData->newEnd(NewEndSym));
344 State = setContainerData(State, ContReg,
345 ContainerData::fromEnd(NewEndSym));
347 // Finally, replace the old "end" symbol in the already reassigned
348 // iterator positions with the new "end" symbol.
349 State = rebaseSymbolInIteratorPositionsIf(
350 State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT);
352 // There was no "end" symbol assigned yet to the old container,
353 // so reassign all iterator positions to the new container.
354 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
356 if (const auto OldBeginSym = OldCData->getBegin()) {
357 // If we already assigned a "begin" symbol to the old container, then
358 // assign it to the new container and remove it from the old one.
361 setContainerData(State, ContReg, CData->newBegin(OldBeginSym));
363 State = setContainerData(State, ContReg,
364 ContainerData::fromBegin(OldBeginSym));
367 setContainerData(State, OldContReg, OldCData->newBegin(nullptr));
370 // There was neither "begin" nor "end" symbol assigned yet to the old
371 // container, so reassign all iterator positions to the new container.
372 State = reassignAllIteratorPositions(State, OldContReg, ContReg);
376 C.addTransition(State);
379 void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont,
380 const Expr *ContE) const {
381 const auto *ContReg = Cont.getAsRegion();
385 ContReg = ContReg->getMostDerivedObjectRegion();
387 // The assign() operation invalidates all the iterators
388 auto State = C.getState();
389 State = invalidateAllIteratorPositions(State, ContReg);
390 C.addTransition(State);
393 void ContainerModeling::handleClear(CheckerContext &C, SVal Cont,
394 const Expr *ContE) const {
395 const auto *ContReg = Cont.getAsRegion();
399 ContReg = ContReg->getMostDerivedObjectRegion();
401 // The clear() operation invalidates all the iterators, except the past-end
402 // iterators of list-like containers
403 auto State = C.getState();
404 if (!hasSubscriptOperator(State, ContReg) ||
405 !backModifiable(State, ContReg)) {
406 const auto CData = getContainerData(State, ContReg);
408 if (const auto EndSym = CData->getEnd()) {
410 invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE);
411 C.addTransition(State);
416 const NoteTag *ChangeTag =
417 getChangeTag(C, "became empty", ContReg, ContE);
418 State = invalidateAllIteratorPositions(State, ContReg);
419 C.addTransition(State, ChangeTag);
422 void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont,
423 const Expr *ContE) const {
424 const auto *ContReg = Cont.getAsRegion();
428 ContReg = ContReg->getMostDerivedObjectRegion();
430 // For deque-like containers invalidate all iterator positions
431 auto State = C.getState();
432 if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) {
433 State = invalidateAllIteratorPositions(State, ContReg);
434 C.addTransition(State);
438 const auto CData = getContainerData(State, ContReg);
442 // For vector-like containers invalidate the past-end iterator positions
443 if (const auto EndSym = CData->getEnd()) {
444 if (hasSubscriptOperator(State, ContReg)) {
445 State = invalidateIteratorPositions(State, EndSym, BO_GE);
447 auto &SymMgr = C.getSymbolManager();
448 auto &BVF = SymMgr.getBasicVals();
449 auto &SVB = C.getSValBuilder();
450 const auto newEndSym =
451 SVB.evalBinOp(State, BO_Add,
452 nonloc::SymbolVal(EndSym),
453 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
454 SymMgr.getType(EndSym)).getAsSymbol();
455 const NoteTag *ChangeTag =
456 getChangeTag(C, "extended to the back by 1 position", ContReg, ContE);
457 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
458 C.addTransition(State, ChangeTag);
462 void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont,
463 const Expr *ContE) const {
464 const auto *ContReg = Cont.getAsRegion();
468 ContReg = ContReg->getMostDerivedObjectRegion();
470 auto State = C.getState();
471 const auto CData = getContainerData(State, ContReg);
475 if (const auto EndSym = CData->getEnd()) {
476 auto &SymMgr = C.getSymbolManager();
477 auto &BVF = SymMgr.getBasicVals();
478 auto &SVB = C.getSValBuilder();
480 SVB.evalBinOp(State, BO_Sub,
481 nonloc::SymbolVal(EndSym),
482 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
483 SymMgr.getType(EndSym)).getAsSymbol();
484 const NoteTag *ChangeTag =
485 getChangeTag(C, "shrank from the back by 1 position", ContReg, ContE);
486 // For vector-like and deque-like containers invalidate the last and the
487 // past-end iterator positions. For list-like containers only invalidate
489 if (hasSubscriptOperator(State, ContReg) &&
490 backModifiable(State, ContReg)) {
491 State = invalidateIteratorPositions(State, BackSym, BO_GE);
492 State = setContainerData(State, ContReg, CData->newEnd(nullptr));
494 State = invalidateIteratorPositions(State, BackSym, BO_EQ);
496 auto newEndSym = BackSym;
497 State = setContainerData(State, ContReg, CData->newEnd(newEndSym));
498 C.addTransition(State, ChangeTag);
502 void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont,
503 const Expr *ContE) const {
504 const auto *ContReg = Cont.getAsRegion();
508 ContReg = ContReg->getMostDerivedObjectRegion();
510 // For deque-like containers invalidate all iterator positions
511 auto State = C.getState();
512 if (hasSubscriptOperator(State, ContReg)) {
513 State = invalidateAllIteratorPositions(State, ContReg);
514 C.addTransition(State);
516 const auto CData = getContainerData(State, ContReg);
520 if (const auto BeginSym = CData->getBegin()) {
521 auto &SymMgr = C.getSymbolManager();
522 auto &BVF = SymMgr.getBasicVals();
523 auto &SVB = C.getSValBuilder();
524 const auto newBeginSym =
525 SVB.evalBinOp(State, BO_Sub,
526 nonloc::SymbolVal(BeginSym),
527 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
528 SymMgr.getType(BeginSym)).getAsSymbol();
529 const NoteTag *ChangeTag =
530 getChangeTag(C, "extended to the front by 1 position", ContReg, ContE);
531 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
532 C.addTransition(State, ChangeTag);
537 void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont,
538 const Expr *ContE) const {
539 const auto *ContReg = Cont.getAsRegion();
543 ContReg = ContReg->getMostDerivedObjectRegion();
545 auto State = C.getState();
546 const auto CData = getContainerData(State, ContReg);
550 // For deque-like containers invalidate all iterator positions. For list-like
551 // iterators only invalidate the first position
552 if (const auto BeginSym = CData->getBegin()) {
553 if (hasSubscriptOperator(State, ContReg)) {
554 State = invalidateIteratorPositions(State, BeginSym, BO_LE);
556 State = invalidateIteratorPositions(State, BeginSym, BO_EQ);
558 auto &SymMgr = C.getSymbolManager();
559 auto &BVF = SymMgr.getBasicVals();
560 auto &SVB = C.getSValBuilder();
561 const auto newBeginSym =
562 SVB.evalBinOp(State, BO_Add,
563 nonloc::SymbolVal(BeginSym),
564 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
565 SymMgr.getType(BeginSym)).getAsSymbol();
566 const NoteTag *ChangeTag =
567 getChangeTag(C, "shrank from the front by 1 position", ContReg, ContE);
568 State = setContainerData(State, ContReg, CData->newBegin(newBeginSym));
569 C.addTransition(State, ChangeTag);
573 void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont,
575 const auto *ContReg = Cont.getAsRegion();
579 ContReg = ContReg->getMostDerivedObjectRegion();
581 auto State = C.getState();
582 const auto *Pos = getIteratorPosition(State, Iter);
586 // For deque-like containers invalidate all iterator positions. For
587 // vector-like containers invalidate iterator positions after the insertion.
588 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
589 if (frontModifiable(State, ContReg)) {
590 State = invalidateAllIteratorPositions(State, ContReg);
592 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
594 if (const auto *CData = getContainerData(State, ContReg)) {
595 if (const auto EndSym = CData->getEnd()) {
596 State = invalidateIteratorPositions(State, EndSym, BO_GE);
597 State = setContainerData(State, ContReg, CData->newEnd(nullptr));
600 C.addTransition(State);
604 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont,
606 const auto *ContReg = Cont.getAsRegion();
610 ContReg = ContReg->getMostDerivedObjectRegion();
612 auto State = C.getState();
613 const auto *Pos = getIteratorPosition(State, Iter);
617 // For deque-like containers invalidate all iterator positions. For
618 // vector-like containers invalidate iterator positions at and after the
619 // deletion. For list-like containers only invalidate the deleted position.
620 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
621 if (frontModifiable(State, ContReg)) {
622 State = invalidateAllIteratorPositions(State, ContReg);
624 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE);
626 if (const auto *CData = getContainerData(State, ContReg)) {
627 if (const auto EndSym = CData->getEnd()) {
628 State = invalidateIteratorPositions(State, EndSym, BO_GE);
629 State = setContainerData(State, ContReg, CData->newEnd(nullptr));
633 State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ);
635 C.addTransition(State);
638 void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1,
640 const auto *ContReg = Cont.getAsRegion();
644 ContReg = ContReg->getMostDerivedObjectRegion();
645 auto State = C.getState();
646 const auto *Pos1 = getIteratorPosition(State, Iter1);
647 const auto *Pos2 = getIteratorPosition(State, Iter2);
651 // For deque-like containers invalidate all iterator positions. For
652 // vector-like containers invalidate iterator positions at and after the
653 // deletion range. For list-like containers only invalidate the deleted
654 // position range [first..last].
655 if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) {
656 if (frontModifiable(State, ContReg)) {
657 State = invalidateAllIteratorPositions(State, ContReg);
659 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE);
661 if (const auto *CData = getContainerData(State, ContReg)) {
662 if (const auto EndSym = CData->getEnd()) {
663 State = invalidateIteratorPositions(State, EndSym, BO_GE);
664 State = setContainerData(State, ContReg, CData->newEnd(nullptr));
668 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE,
669 Pos2->getOffset(), BO_LT);
671 C.addTransition(State);
674 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
676 auto State = C.getState();
677 const auto *Pos = getIteratorPosition(State, Iter);
681 // Invalidate the deleted iterator position, which is the position of the
682 // parameter plus one.
683 auto &SymMgr = C.getSymbolManager();
684 auto &BVF = SymMgr.getBasicVals();
685 auto &SVB = C.getSValBuilder();
687 SVB.evalBinOp(State, BO_Add,
688 nonloc::SymbolVal(Pos->getOffset()),
689 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))),
690 SymMgr.getType(Pos->getOffset())).getAsSymbol();
691 State = invalidateIteratorPositions(State, NextSym, BO_EQ);
692 C.addTransition(State);
695 void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont,
696 SVal Iter1, SVal Iter2) const {
697 auto State = C.getState();
698 const auto *Pos1 = getIteratorPosition(State, Iter1);
699 const auto *Pos2 = getIteratorPosition(State, Iter2);
703 // Invalidate the deleted iterator position range (first..last)
704 State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT,
705 Pos2->getOffset(), BO_LT);
706 C.addTransition(State);
709 const NoteTag *ContainerModeling::getChangeTag(CheckerContext &C,
711 const MemRegion *ContReg,
712 const Expr *ContE) const {
714 // First try to get the name of the variable from the region
715 if (const auto *DR = dyn_cast<DeclRegion>(ContReg)) {
716 Name = DR->getDecl()->getName();
717 // If the region is not a `DeclRegion` then use the expression instead
718 } else if (const auto *DRE =
719 dyn_cast<DeclRefExpr>(ContE->IgnoreParenCasts())) {
720 Name = DRE->getDecl()->getName();
724 [Text, Name, ContReg](PathSensitiveBugReport &BR) -> std::string {
725 if (!BR.isInteresting(ContReg))
728 SmallString<256> Msg;
729 llvm::raw_svector_ostream Out(Msg);
730 Out << "Container " << (!Name.empty() ? ("'" + Name.str() + "' ") : "" )
732 return std::string(Out.str());
736 void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State,
737 const char *NL, const char *Sep) const {
738 auto ContMap = State->get<ContainerMap>();
740 if (!ContMap.isEmpty()) {
741 Out << Sep << "Container Data :" << NL;
742 for (const auto &Cont : ContMap) {
743 Cont.first->dumpToStream(Out);
745 const auto CData = Cont.second;
746 if (CData.getBegin())
747 CData.getBegin()->dumpToStream(Out);
752 CData.getEnd()->dumpToStream(Out);
762 bool isBeginCall(const FunctionDecl *Func) {
763 const auto *IdInfo = Func->getIdentifier();
766 return IdInfo->getName().endswith_lower("begin");
769 bool isEndCall(const FunctionDecl *Func) {
770 const auto *IdInfo = Func->getIdentifier();
773 return IdInfo->getName().endswith_lower("end");
776 const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State,
777 const MemRegion *Reg) {
778 auto TI = getDynamicTypeInfo(State, Reg);
782 auto Type = TI.getType();
783 if (const auto *RefT = Type->getAs<ReferenceType>()) {
784 Type = RefT->getPointeeType();
787 return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl();
790 bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) {
791 const auto *CRD = getCXXRecordDecl(State, Reg);
795 for (const auto *Method : CRD->methods()) {
796 if (!Method->isOverloadedOperator())
798 const auto OPK = Method->getOverloadedOperator();
799 if (OPK == OO_Subscript) {
806 bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) {
807 const auto *CRD = getCXXRecordDecl(State, Reg);
811 for (const auto *Method : CRD->methods()) {
812 if (!Method->getDeclName().isIdentifier())
814 if (Method->getName() == "push_front" || Method->getName() == "pop_front") {
821 bool backModifiable(ProgramStateRef State, const MemRegion *Reg) {
822 const auto *CRD = getCXXRecordDecl(State, Reg);
826 for (const auto *Method : CRD->methods()) {
827 if (!Method->getDeclName().isIdentifier())
829 if (Method->getName() == "push_back" || Method->getName() == "pop_back") {
836 SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) {
837 const auto *CDataPtr = getContainerData(State, Cont);
841 return CDataPtr->getBegin();
844 SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) {
845 const auto *CDataPtr = getContainerData(State, Cont);
849 return CDataPtr->getEnd();
852 ProgramStateRef createContainerBegin(ProgramStateRef State,
853 const MemRegion *Cont, const Expr *E,
854 QualType T, const LocationContext *LCtx,
855 unsigned BlockCount) {
856 // Only create if it does not exist
857 const auto *CDataPtr = getContainerData(State, Cont);
858 if (CDataPtr && CDataPtr->getBegin())
861 auto &SymMgr = State->getSymbolManager();
862 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
864 State = assumeNoOverflow(State, Sym, 4);
867 const auto CData = CDataPtr->newBegin(Sym);
868 return setContainerData(State, Cont, CData);
871 const auto CData = ContainerData::fromBegin(Sym);
872 return setContainerData(State, Cont, CData);
875 ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont,
876 const Expr *E, QualType T,
877 const LocationContext *LCtx,
878 unsigned BlockCount) {
879 // Only create if it does not exist
880 const auto *CDataPtr = getContainerData(State, Cont);
881 if (CDataPtr && CDataPtr->getEnd())
884 auto &SymMgr = State->getSymbolManager();
885 const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount,
887 State = assumeNoOverflow(State, Sym, 4);
890 const auto CData = CDataPtr->newEnd(Sym);
891 return setContainerData(State, Cont, CData);
894 const auto CData = ContainerData::fromEnd(Sym);
895 return setContainerData(State, Cont, CData);
898 ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont,
899 const ContainerData &CData) {
900 return State->set<ContainerMap>(Cont, CData);
903 template <typename Condition, typename Process>
904 ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond,
906 auto &RegionMapFactory = State->get_context<IteratorRegionMap>();
907 auto RegionMap = State->get<IteratorRegionMap>();
908 bool Changed = false;
909 for (const auto &Reg : RegionMap) {
910 if (Cond(Reg.second)) {
911 RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second));
917 State = State->set<IteratorRegionMap>(RegionMap);
919 auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>();
920 auto SymbolMap = State->get<IteratorSymbolMap>();
922 for (const auto &Sym : SymbolMap) {
923 if (Cond(Sym.second)) {
924 SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second));
930 State = State->set<IteratorSymbolMap>(SymbolMap);
935 ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State,
936 const MemRegion *Cont) {
937 auto MatchCont = [&](const IteratorPosition &Pos) {
938 return Pos.getContainer() == Cont;
940 auto Invalidate = [&](const IteratorPosition &Pos) {
941 return Pos.invalidate();
943 return processIteratorPositions(State, MatchCont, Invalidate);
947 invalidateAllIteratorPositionsExcept(ProgramStateRef State,
948 const MemRegion *Cont, SymbolRef Offset,
949 BinaryOperator::Opcode Opc) {
950 auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
951 return Pos.getContainer() == Cont &&
952 !compare(State, Pos.getOffset(), Offset, Opc);
954 auto Invalidate = [&](const IteratorPosition &Pos) {
955 return Pos.invalidate();
957 return processIteratorPositions(State, MatchContAndCompare, Invalidate);
960 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
962 BinaryOperator::Opcode Opc) {
963 auto Compare = [&](const IteratorPosition &Pos) {
964 return compare(State, Pos.getOffset(), Offset, Opc);
966 auto Invalidate = [&](const IteratorPosition &Pos) {
967 return Pos.invalidate();
969 return processIteratorPositions(State, Compare, Invalidate);
972 ProgramStateRef invalidateIteratorPositions(ProgramStateRef State,
974 BinaryOperator::Opcode Opc1,
976 BinaryOperator::Opcode Opc2) {
977 auto Compare = [&](const IteratorPosition &Pos) {
978 return compare(State, Pos.getOffset(), Offset1, Opc1) &&
979 compare(State, Pos.getOffset(), Offset2, Opc2);
981 auto Invalidate = [&](const IteratorPosition &Pos) {
982 return Pos.invalidate();
984 return processIteratorPositions(State, Compare, Invalidate);
987 ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State,
988 const MemRegion *Cont,
989 const MemRegion *NewCont) {
990 auto MatchCont = [&](const IteratorPosition &Pos) {
991 return Pos.getContainer() == Cont;
993 auto ReAssign = [&](const IteratorPosition &Pos) {
994 return Pos.reAssign(NewCont);
996 return processIteratorPositions(State, MatchCont, ReAssign);
999 ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State,
1000 const MemRegion *Cont,
1001 const MemRegion *NewCont,
1003 BinaryOperator::Opcode Opc) {
1004 auto MatchContAndCompare = [&](const IteratorPosition &Pos) {
1005 return Pos.getContainer() == Cont &&
1006 !compare(State, Pos.getOffset(), Offset, Opc);
1008 auto ReAssign = [&](const IteratorPosition &Pos) {
1009 return Pos.reAssign(NewCont);
1011 return processIteratorPositions(State, MatchContAndCompare, ReAssign);
1014 // This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`,
1015 // `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator
1016 // position offsets where `CondSym` is true.
1017 ProgramStateRef rebaseSymbolInIteratorPositionsIf(
1018 ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym,
1019 SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) {
1020 auto LessThanEnd = [&](const IteratorPosition &Pos) {
1021 return compare(State, Pos.getOffset(), CondSym, Opc);
1023 auto RebaseSymbol = [&](const IteratorPosition &Pos) {
1024 return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym,
1027 return processIteratorPositions(State, LessThanEnd, RebaseSymbol);
1030 // This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`,
1031 // `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression
1033 SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB,
1034 SymbolRef OrigExpr, SymbolRef OldExpr,
1036 auto &SymMgr = SVB.getSymbolManager();
1037 auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr),
1038 nonloc::SymbolVal(OldExpr),
1039 SymMgr.getType(OrigExpr));
1041 const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>();
1045 return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym),
1046 SymMgr.getType(OrigExpr)).getAsSymbol();
1049 bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) {
1050 auto RegionMap = State->get<IteratorRegionMap>();
1051 for (const auto &Reg : RegionMap) {
1052 if (Reg.second.getContainer() == Cont)
1056 auto SymbolMap = State->get<IteratorSymbolMap>();
1057 for (const auto &Sym : SymbolMap) {
1058 if (Sym.second.getContainer() == Cont)
1067 void ento::registerContainerModeling(CheckerManager &mgr) {
1068 mgr.registerChecker<ContainerModeling>();
1071 bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) {
1072 if (!mgr.getLangOpts().CPlusPlus)
1075 if (!mgr.getAnalyzerOptions().ShouldAggressivelySimplifyBinaryOperation) {
1076 mgr.getASTContext().getDiagnostics().Report(
1077 diag::err_analyzer_checker_incompatible_analyzer_option)
1078 << "aggressive-binary-operation-simplification" << "false";