Index: clang/include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -683,6 +683,14 @@ def ContainerModeling : Checker<"ContainerModeling">, HelpText<"Models C++ containers">, + CheckerOptions<[ + CmdLineOption + ]>, Documentation, Hidden; Index: clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp @@ -44,16 +44,16 @@ void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const; void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handleInsert(CheckerContext &C, SVal Cont, SVal Iter, - SVal RetVal) const; - void handleInsertAfter(CheckerContext &C, SVal Cont, SVal Iter, - SVal RetVal) const; - void handleErase(CheckerContext &C, SVal Cont, SVal Iter, - SVal RetVal) const; + void handleInsert(CheckerContext &C, SVal Cont, SVal Iter, SVal RetVal, + const Expr *CE) const; + void handleInsertAfter(CheckerContext &C, SVal Cont, SVal Iter, SVal RetVal, + const Expr *CE) const; + void handleErase(CheckerContext &C, SVal Cont, SVal Iter, SVal RetVal, + const Expr *CE) const; void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const; - void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter, - SVal RetVal) const; + void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter, SVal RetVal, + const Expr *CE) const; void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const; const NoteTag *getChangeTag(CheckerContext &C, StringRef Text, @@ -65,14 +65,16 @@ public: ContainerModeling() = default; + DefaultBool AggressiveEraseModeling; + void checkPostCall(const CallEvent &Call, CheckerContext &C) const; void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, const Expr *) const; - using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, - SVal, SVal) const; + using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal, + SVal, const Expr*) const; using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal, SVal, SVal) const; @@ -222,7 +224,7 @@ const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); if (Handler1) { (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0), - RetVal); + RetVal, Call.getOriginExpr()); return; } @@ -590,8 +592,8 @@ } } -void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont, - SVal Iter, SVal RetVal) const { +void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont, SVal Iter, + SVal RetVal, const Expr*) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -629,7 +631,8 @@ } void ContainerModeling::handleInsertAfter(CheckerContext &C, SVal Cont, - SVal Iter, SVal RetVal) const { + SVal Iter, SVal RetVal, + const Expr*) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -655,8 +658,8 @@ C.addTransition(State); } -void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, - SVal Iter, SVal RetVal) const { +void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter, + SVal RetVal, const Expr *CE) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -697,7 +700,36 @@ SymMgr.getType(Pos->getOffset())).getAsSymbol(); auto RetPos = IteratorPosition::getPosition(Pos->getContainer(), RetOffset); State = setIteratorPosition(State, RetVal, RetPos); + + if (AggressiveEraseModeling) { + SymbolRef EndSym = getContainerEnd(State, ContReg); + // For std::vector and std::queue-like containers we just removed the + // end symbol from the container data because the past-the-end iterator + // was also invalidated. The next call to member function `end()` would + // create a new one, but we need it now so we create it now. + if (!EndSym) { + State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, + C.getLocationContext(), C.blockCount()); + EndSym = getContainerEnd(State, ContReg); + } + const auto RetEnd = + SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(RetOffset), + nonloc::SymbolVal(EndSym), SVB.getConditionType()) + .getAs(); + if (RetEnd) { + ProgramStateRef StateEnd, StateNotEnd; + std::tie(StateEnd, StateNotEnd) = State->assume(*RetEnd); + if (StateEnd) { + C.addTransition(StateEnd); + } + if (StateNotEnd) { + C.addTransition(StateNotEnd); + } + return; + } + } } + C.addTransition(State); } @@ -745,7 +777,13 @@ } void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont, - SVal Iter, SVal RetVal) const { + SVal Iter, SVal RetVal, + const Expr *CE) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) @@ -769,7 +807,30 @@ SymMgr.getType(NextSym)).getAsSymbol(); auto RetPos = IteratorPosition::getPosition(Pos->getContainer(), RetOffset); State = setIteratorPosition(State, RetVal, RetPos); + + if (AggressiveEraseModeling) { + if (const auto *CData = getContainerData(State, ContReg)) { + if (const SymbolRef EndSym = CData->getEnd()) { + const auto RetEnd = + SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(RetOffset), + nonloc::SymbolVal(EndSym), SVB.getConditionType()) + .getAs(); + if (RetEnd) { + ProgramStateRef StateEnd, StateNotEnd; + std::tie(StateEnd, StateNotEnd) = State->assume(*RetEnd); + if (StateEnd) { + C.addTransition(StateEnd); + } + if (StateNotEnd) { + C.addTransition(StateNotEnd); + } + return; + } + } + } + } } + C.addTransition(State); } @@ -1154,7 +1215,11 @@ } // namespace void ento::registerContainerModeling(CheckerManager &mgr) { - mgr.registerChecker(); + auto *Checker = mgr.registerChecker(); + Checker->AggressiveEraseModeling = + mgr.getAnalyzerOptions().getCheckerBooleanOption( + "alpha.cplusplus.ContainerModeling", "AggressiveEraseModeling"); + } bool ento::shouldRegisterContainerModeling(const CheckerManager &mgr) { Index: clang/test/Analysis/analyzer-config.c =================================================================== --- clang/test/Analysis/analyzer-config.c +++ clang/test/Analysis/analyzer-config.c @@ -7,6 +7,7 @@ // CHECK-NEXT: alpha.clone.CloneChecker:IgnoredFilesPattern = "" // CHECK-NEXT: alpha.clone.CloneChecker:MinimumCloneComplexity = 50 // CHECK-NEXT: alpha.clone.CloneChecker:ReportNormalClones = true +// CHECK-NEXT: alpha.cplusplus.ContainerModeling:AggressiveEraseModeling = false // CHECK-NEXT: alpha.cplusplus.STLAlgorithmModeling:AggressiveStdFindModeling = false // CHECK-NEXT: alpha.osx.cocoa.DirectIvarAssignment:AnnotatedFunctions = false // CHECK-NEXT: alpha.security.MmapWriteExec:MmapProtExec = 0x04 Index: clang/test/Analysis/iterator-range-aggressive-erase-modeling.cpp =================================================================== --- /dev/null +++ clang/test/Analysis/iterator-range-aggressive-erase-modeling.cpp @@ -0,0 +1,38 @@ +// RUN: %clang_analyze_cc1 -std=c++11 \ +// RUN: -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange \ +// RUN: -analyzer-config aggressive-binary-operation-simplification=true \ +// RUN: -analyzer-config c++-container-inlining=false %s \ +// RUN: -analyzer-config alpha.cplusplus.ContainerModeling:AggressiveEraseModeling=true \ +// RUN: -verify + +// RUN: %clang_analyze_cc1 -std=c++11 \ +// RUN: -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange \ +// RUN: -analyzer-config aggressive-binary-operation-simplification=true \ +// RUN: -analyzer-config c++-container-inlining=true -DINLINE=1 %s \ +// RUN: -analyzer-config alpha.cplusplus.ContainerModeling:AggressiveEraseModeling=true \ +// RUN: -verify + +#include "Inputs/system-header-simulator-cxx.h" + +extern void __assert_fail (__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__ ((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail (#expr, __FILE__, __LINE__, __func__)) + +void bad_erase_loop(std::list L) { + for (auto i = L.cbegin(); i != L.end(); ++i) { // expected-warning{{Iterator incremented behind the past-the-end iterator}} + i = L.erase(i); + } +} + +void bad_erase_loop(std::vector V) { + for (auto i = V.cbegin(); i != V.end(); ++i) { // expected-warning{{Iterator incremented behind the past-the-end iterator}} + i = V.erase(i); + } +} +void bad_erase_loop(std::deque D) { + for (auto i = D.cbegin(); i != D.end(); ++i) { // expected-warning{{Iterator incremented behind the past-the-end iterator}} + i = D.erase(i); + } +}