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