diff --git a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td --- a/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td +++ b/clang/include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -602,6 +602,11 @@ let ParentPackage = CplusplusAlpha in { +def ContainerModeling : Checker<"ContainerModeling">, + HelpText<"Models C++ containers">, + Documentation, + Hidden; + def DeleteWithNonVirtualDtorChecker : Checker<"DeleteWithNonVirtualDtor">, HelpText<"Reports destructions of polymorphic objects with a non-virtual " "destructor in their base class">, @@ -613,6 +618,7 @@ def IteratorModeling : Checker<"IteratorModeling">, HelpText<"Models iterators of C++ containers">, + Dependencies<[ContainerModeling]>, Documentation, Hidden; @@ -1373,9 +1379,14 @@ HelpText<"Emits a warning for every statement.">, Documentation; +def DebugContainerModeling : Checker<"DebugContainerModeling">, + HelpText<"Check the analyzer's understanding of C++ containers">, + Dependencies<[ContainerModeling]>, + Documentation; + def DebugIteratorModeling : Checker<"DebugIteratorModeling">, HelpText<"Check the analyzer's understanding of C++ iterators">, - Dependencies<[IteratorModeling]>, + Dependencies<[DebugContainerModeling, IteratorModeling]>, Documentation; } // end "debug" diff --git a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt --- a/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ b/clang/lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -25,10 +25,12 @@ CheckerDocumentation.cpp ChrootChecker.cpp CloneChecker.cpp + ContainerModeling.cpp ConversionChecker.cpp CXXSelfAssignmentChecker.cpp DeadStoresChecker.cpp DebugCheckers.cpp + DebugContainerModeling.cpp DebugIteratorModeling.cpp DeleteWithNonVirtualDtorChecker.cpp DereferenceChecker.cpp diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp copy from clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp copy to clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp --- a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp @@ -1,4 +1,4 @@ -//===-- IteratorModeling.cpp --------------------------------------*- C++ -*--// +//===-- ContainerModeling.cpp -------------------------------------*- C++ -*--// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. @@ -6,64 +6,9 @@ // //===----------------------------------------------------------------------===// // -// Defines a checker for using iterators outside their range (past end). Usage -// means here dereferencing, incrementing etc. +// Defines a modeling-checker for modeling STL container-like containers. // //===----------------------------------------------------------------------===// -// -// In the code, iterator can be represented as a: -// * type-I: typedef-ed pointer. Operations over such iterator, such as -// comparisons or increments, are modeled straightforwardly by the -// analyzer. -// * type-II: structure with its method bodies available. Operations over such -// iterator are inlined by the analyzer, and results of modeling -// these operations are exposing implementation details of the -// iterators, which is not necessarily helping. -// * type-III: completely opaque structure. Operations over such iterator are -// modeled conservatively, producing conjured symbols everywhere. -// -// To handle all these types in a common way we introduce a structure called -// IteratorPosition which is an abstraction of the position the iterator -// represents using symbolic expressions. The checker handles all the -// operations on this structure. -// -// Additionally, depending on the circumstances, operators of types II and III -// can be represented as: -// * type-IIa, type-IIIa: conjured structure symbols - when returned by value -// from conservatively evaluated methods such as -// `.begin()`. -// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as -// variables or temporaries, when the iterator object is -// currently treated as an lvalue. -// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the -// iterator object is treated as an rvalue taken of a -// particular lvalue, eg. a copy of "type-a" iterator -// object, or an iterator that existed before the -// analysis has started. -// -// To handle any of these three different representations stored in an SVal we -// use setter and getters functions which separate the three cases. To store -// them we use a pointer union of symbol and memory region. -// -// The checker works the following way: We record the begin and the -// past-end iterator for all containers whenever their `.begin()` and `.end()` -// are called. Since the Constraint Manager cannot handle such SVals we need -// to take over its role. We post-check equality and non-equality comparisons -// and record that the two sides are equal if we are in the 'equal' branch -// (true-branch for `==` and false-branch for `!=`). -// -// In case of type-I or type-II iterators we get a concrete integer as a result -// of the comparison (1 or 0) but in case of type-III we only get a Symbol. In -// this latter case we record the symbol and reload it in evalAssume() and do -// the propagation there. We also handle (maybe double) negated comparisons -// which are represented in the form of (x == 0 or x != 0) where x is the -// comparison itself. -// -// Since `SimpleConstraintManager` cannot handle complex symbolic expressions -// we only use expressions of the format S, S+n or S-n for iterator positions -// where S is a conjured symbol and n is an unsigned concrete integer. When -// making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as -// a constraint which we later retrieve when doing an actual comparison. #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" #include "clang/AST/DeclTemplate.h" @@ -83,72 +28,92 @@ namespace { -class IteratorModeling - : public Checker, - check::Bind, check::LiveSymbols, check::DeadSymbols> { - - void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal, - const SVal &LVal, const SVal &RVal, - OverloadedOperatorKind Op) const; - void processComparison(CheckerContext &C, ProgramStateRef State, - SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal, - OverloadedOperatorKind Op) const; - void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, - bool Postfix) const; - void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, - bool Postfix) const; - void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, - OverloadedOperatorKind Op, const SVal &RetVal, - const SVal &LHS, const SVal &RHS) const; +class ContainerModeling + : public Checker { + void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const; void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const; - void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const MemRegion *Cont) const; - void handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE = nullptr, - const SVal &OldCont = UndefinedVal()) const; + void handleAssignment(CheckerContext &C, const SVal &Cont, + const Expr *CE = nullptr, + const SVal &OldCont = UndefinedVal()) const; + void handleAssign(CheckerContext &C, const SVal &Cont) const; void handleClear(CheckerContext &C, const SVal &Cont) const; void handlePushBack(CheckerContext &C, const SVal &Cont) const; void handlePopBack(CheckerContext &C, const SVal &Cont) const; void handlePushFront(CheckerContext &C, const SVal &Cont) const; void handlePopFront(CheckerContext &C, const SVal &Cont) const; - void handleInsert(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter1, + void handleInsert(CheckerContext &C, const SVal &Cont, + const SVal &Iter) const; + void handleErase(CheckerContext &C, const SVal &Cont, const SVal &Iter) const; + void handleErase(CheckerContext &C, const SVal &Cont, const SVal &Iter1, const SVal &Iter2) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter1, + void handleEraseAfter(CheckerContext &C, const SVal &Cont, + const SVal &Iter) const; + void handleEraseAfter(CheckerContext &C, const SVal &Cont, const SVal &Iter1, const SVal &Iter2) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; public: - IteratorModeling() {} + ContainerModeling() {} void checkPostCall(const CallEvent &Call, CheckerContext &C) const; - void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; - void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; - void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const; - void checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const; void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; + + typedef void (ContainerModeling::*NoItParamFn)(CheckerContext &, + const SVal &) const; + typedef void (ContainerModeling::*OneItParamFn)(CheckerContext &, + const SVal &, + const SVal &) const; + typedef void (ContainerModeling::*TwoItParamFn)(CheckerContext &, + const SVal &, + const SVal &, + const SVal &) const; + + CallDescriptionMap NoIterParamFunctions = { + {{0, "clear", 0}, + &ContainerModeling::handleClear}, + {{0, "assign", 2}, + &ContainerModeling::handleAssign}, + {{0, "push_back", 1}, + &ContainerModeling::handlePushBack}, + {{0, "emplace_back", 1}, + &ContainerModeling::handlePushBack}, + {{0, "pop_back", 0}, + &ContainerModeling::handlePopBack}, + {{0, "push_front", 1}, + &ContainerModeling::handlePushFront}, + {{0, "emplace_front", 1}, + &ContainerModeling::handlePushFront}, + {{0, "pop_front", 0}, + &ContainerModeling::handlePopFront}, + }; + + CallDescriptionMap OneIterParamFunctions = { + {{0, "insert", 2}, + &ContainerModeling::handleInsert}, + {{0, "emplace", 2}, + &ContainerModeling::handleInsert}, + {{0, "erase", 1}, + &ContainerModeling::handleErase}, + {{0, "erase_after", 1}, + &ContainerModeling::handleEraseAfter}, + }; + + CallDescriptionMap TwoIterParamFunctions = { + {{0, "erase", 2}, + &ContainerModeling::handleErase}, + {{0, "erase_after", 2}, + &ContainerModeling::handleEraseAfter}, + }; + }; bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); -bool isAssignCall(const FunctionDecl *Func); -bool isClearCall(const FunctionDecl *Func); -bool isPushBackCall(const FunctionDecl *Func); -bool isEmplaceBackCall(const FunctionDecl *Func); -bool isPopBackCall(const FunctionDecl *Func); -bool isPushFrontCall(const FunctionDecl *Func); -bool isEmplaceFrontCall(const FunctionDecl *Func); -bool isPopFrontCall(const FunctionDecl *Func); -bool isAssignmentOperator(OverloadedOperatorKind OK); -bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); bool backModifiable(ProgramStateRef State, const MemRegion *Reg); @@ -164,9 +129,6 @@ unsigned BlockCount); ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData); -ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale); ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, const MemRegion *Cont); ProgramStateRef @@ -192,258 +154,75 @@ ProgramStateRef rebaseSymbolInIteratorPositionsIf( ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal); SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, SymbolRef OldSym, SymbolRef NewSym); bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); -bool isBoundThroughLazyCompoundVal(const Environment &Env, - const MemRegion *Reg); } // namespace -void IteratorModeling::checkPostCall(const CallEvent &Call, +void ContainerModeling::checkPostCall(const CallEvent &Call, CheckerContext &C) const { - // Record new iterator positions and iterator position changes const auto *Func = dyn_cast_or_null(Call.getDecl()); if (!Func) return; if (Func->isOverloadedOperator()) { const auto Op = Func->getOverloadedOperator(); - if (isAssignmentOperator(Op)) { + if (Op == OO_Equal) { // Overloaded 'operator=' must be a non-static member function. const auto *InstCall = cast(&Call); if (cast(Func)->isMoveAssignmentOperator()) { - handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), + handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), Call.getArgSVal(0)); return; } - handleAssign(C, InstCall->getCXXThisVal()); - return; - } else if (isSimpleComparisonOperator(Op)) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (const auto *InstCall = dyn_cast(&Call)) { - handleComparison(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); - return; - } - - handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1), Op); - return; - } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (const auto *InstCall = dyn_cast(&Call)) { - if (Call.getNumArgs() >= 1 && - Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), - Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0)); - return; - } - } else { - if (Call.getNumArgs() >= 2 && - Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, OrigExpr, Func->getOverloadedOperator(), - Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1)); - return; - } - } - } else if (isIncrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } - - handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); - return; - } else if (isDecrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } - - handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); + handleAssignment(C, InstCall->getCXXThisVal()); return; } } else { if (const auto *InstCall = dyn_cast(&Call)) { - if (isAssignCall(Func)) { - handleAssign(C, InstCall->getCXXThisVal()); - return; - } - - if (isClearCall(Func)) { - handleClear(C, InstCall->getCXXThisVal()); - return; - } - - if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { - handlePushBack(C, InstCall->getCXXThisVal()); - return; - } - - if (isPopBackCall(Func)) { - handlePopBack(C, InstCall->getCXXThisVal()); + const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); + if (Handler0) { + (this->**Handler0)(C, InstCall->getCXXThisVal()); return; } - if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { - handlePushFront(C, InstCall->getCXXThisVal()); + const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); + if (Handler1) { + (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); return; } - if (isPopFrontCall(Func)) { - handlePopFront(C, InstCall->getCXXThisVal()); + const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call); + if (Handler2) { + (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0), + Call.getArgSVal(1)); return; } - if (isInsertCall(Func) || isEmplaceCall(Func)) { - handleInsert(C, Call.getArgSVal(0)); + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) return; - } - - if (isEraseCall(Func)) { - if (Call.getNumArgs() == 1) { - handleErase(C, Call.getArgSVal(0)); - return; - } - - if (Call.getNumArgs() == 2) { - handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - - if (isEraseAfterCall(Func)) { - if (Call.getNumArgs() == 1) { - handleEraseAfter(C, Call.getArgSVal(0)); - return; - } - if (Call.getNumArgs() == 2) { - handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - } - - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (!isIteratorType(Call.getResultType())) - return; - - auto State = C.getState(); - - if (const auto *InstCall = dyn_cast(&Call)) { if (isBeginCall(Func)) { handleBegin(C, OrigExpr, Call.getReturnValue(), InstCall->getCXXThisVal()); return; } - + if (isEndCall(Func)) { handleEnd(C, OrigExpr, Call.getReturnValue(), InstCall->getCXXThisVal()); return; } } - - // Already bound to container? - if (getIteratorPosition(State, Call.getReturnValue())) - return; - - // Copy-like and move constructors - if (isa(&Call) && Call.getNumArgs() == 1) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { - State = setIteratorPosition(State, Call.getReturnValue(), *Pos); - if (cast(Func)->isMoveConstructor()) { - State = removeIteratorPosition(State, Call.getArgSVal(0)); - } - C.addTransition(State); - return; - } - } - - // Assumption: if return value is an iterator which is not yet bound to a - // container, then look for the first iterator argument, and - // bind the return value to the same container. This approach - // works for STL algorithms. - // FIXME: Add a more conservative mode - for (unsigned i = 0; i < Call.getNumArgs(); ++i) { - if (isIteratorType(Call.getArgExpr(i)->getType())) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { - assignToContainer(C, OrigExpr, Call.getReturnValue(), - Pos->getContainer()); - return; - } - } - } } } -void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S, - CheckerContext &C) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos) { - State = setIteratorPosition(State, Loc, *Pos); - C.addTransition(State); - } else { - const auto *OldPos = getIteratorPosition(State, Loc); - if (OldPos) { - State = removeIteratorPosition(State, Loc); - C.addTransition(State); - } - } -} - -void IteratorModeling::checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const { - /* Transfer iterator state to temporary objects */ - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr())); - if (!Pos) - return; - State = setIteratorPosition(State, C.getSVal(MTE), *Pos); - C.addTransition(State); -} - -void IteratorModeling::checkLiveSymbols(ProgramStateRef State, - SymbolReaper &SR) const { - // Keep symbolic expressions of iterator positions, container begins and ends - // alive - auto RegionMap = State->get(); - for (const auto &Reg : RegionMap) { - const auto Offset = Reg.second.getOffset(); - for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) - if (isa(*i)) - SR.markLive(*i); - } - - auto SymbolMap = State->get(); - for (const auto &Sym : SymbolMap) { - const auto Offset = Sym.second.getOffset(); - for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) - if (isa(*i)) - SR.markLive(*i); - } - +void ContainerModeling::checkLiveSymbols(ProgramStateRef State, + SymbolReaper &SR) const { + // Keep symbolic expressions of container begins and ends alive auto ContMap = State->get(); for (const auto &Cont : ContMap) { const auto CData = Cont.second; @@ -460,30 +239,11 @@ } } -void IteratorModeling::checkDeadSymbols(SymbolReaper &SR, - CheckerContext &C) const { +void ContainerModeling::checkDeadSymbols(SymbolReaper &SR, + CheckerContext &C) const { // Cleanup auto State = C.getState(); - - auto RegionMap = State->get(); - for (const auto &Reg : RegionMap) { - if (!SR.isLiveRegion(Reg.first)) { - // The region behind the `LazyCompoundVal` is often cleaned up before - // the `LazyCompoundVal` itself. If there are iterator positions keyed - // by these regions their cleanup must be deferred. - if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) { - State = State->remove(Reg.first); - } - } - } - - auto SymbolMap = State->get(); - for (const auto &Sym : SymbolMap) { - if (!SR.isLive(Sym.first)) { - State = State->remove(Sym.first); - } - } - + auto ContMap = State->get(); for (const auto &Cont : ContMap) { if (!SR.isLiveRegion(Cont.first)) { @@ -498,178 +258,7 @@ C.addTransition(State); } -void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE, - SVal RetVal, const SVal &LVal, - const SVal &RVal, - OverloadedOperatorKind Op) const { - // Record the operands and the operator of the comparison for the next - // evalAssume, if the result is a symbolic expression. If it is a concrete - // value (only one branch is possible), then transfer the state between - // the operands according to the operator and the result - auto State = C.getState(); - const auto *LPos = getIteratorPosition(State, LVal); - const auto *RPos = getIteratorPosition(State, RVal); - const MemRegion *Cont = nullptr; - if (LPos) { - Cont = LPos->getContainer(); - } else if (RPos) { - Cont = RPos->getContainer(); - } - if (!Cont) - return; - - // At least one of the iterators have recorded positions. If one of them has - // not then create a new symbol for the offset. - SymbolRef Sym; - if (!LPos || !RPos) { - auto &SymMgr = C.getSymbolManager(); - Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, Sym, 4); - } - - if (!LPos) { - State = setIteratorPosition(State, LVal, - IteratorPosition::getPosition(Cont, Sym)); - LPos = getIteratorPosition(State, LVal); - } else if (!RPos) { - State = setIteratorPosition(State, RVal, - IteratorPosition::getPosition(Cont, Sym)); - RPos = getIteratorPosition(State, RVal); - } - - // We cannot make assumpotions on `UnknownVal`. Let us conjure a symbol - // instead. - if (RetVal.isUnknown()) { - auto &SymMgr = C.getSymbolManager(); - auto *LCtx = C.getLocationContext(); - RetVal = nonloc::SymbolVal(SymMgr.conjureSymbol( - CE, LCtx, C.getASTContext().BoolTy, C.blockCount())); - State = State->BindExpr(CE, LCtx, RetVal); - } - - processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op); -} - -void IteratorModeling::processComparison(CheckerContext &C, - ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, const SVal &RetVal, - OverloadedOperatorKind Op) const { - if (const auto TruthVal = RetVal.getAs()) { - if ((State = relateSymbols(State, Sym1, Sym2, - (Op == OO_EqualEqual) == - (TruthVal->getValue() != 0)))) { - C.addTransition(State); - } else { - C.generateSink(State, C.getPredecessor()); - } - return; - } - - const auto ConditionVal = RetVal.getAs(); - if (!ConditionVal) - return; - - if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) { - StateTrue = StateTrue->assume(*ConditionVal, true); - C.addTransition(StateTrue); - } - - if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) { - StateFalse = StateFalse->assume(*ConditionVal, false); - C.addTransition(StateFalse); - } -} - -void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { - // Increment the symbolic expressions which represents the position of the - // iterator - auto State = C.getState(); - auto &BVF = C.getSymbolManager().getBasicVals(); - - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - auto NewState = - advancePosition(State, Iter, OO_Plus, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); - assert(NewState && - "Advancing position by concrete int should always be successful"); - - const auto *NewPos = getIteratorPosition(NewState, Iter); - assert(NewPos && - "Iterator should have position after successful advancement"); - - State = setIteratorPosition(State, Iter, *NewPos); - State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos); - C.addTransition(State); -} - -void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { - // Decrement the symbolic expressions which represents the position of the - // iterator - auto State = C.getState(); - auto &BVF = C.getSymbolManager().getBasicVals(); - - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - auto NewState = - advancePosition(State, Iter, OO_Minus, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); - assert(NewState && - "Advancing position by concrete int should always be successful"); - - const auto *NewPos = getIteratorPosition(NewState, Iter); - assert(NewPos && - "Iterator should have position after successful advancement"); - - State = setIteratorPosition(State, Iter, *NewPos); - State = setIteratorPosition(State, RetVal, Postfix ? *Pos : *NewPos); - C.addTransition(State); -} - -void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, - const Expr *CE, - OverloadedOperatorKind Op, - const SVal &RetVal, - const SVal &LHS, - const SVal &RHS) const { - // Increment or decrement the symbolic expressions which represents the - // position of the iterator - auto State = C.getState(); - - const auto *Pos = getIteratorPosition(State, LHS); - if (!Pos) - return; - - const auto *value = &RHS; - if (auto loc = RHS.getAs()) { - const auto val = State->getRawSVal(*loc); - value = &val; - } - - auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; - - auto NewState = - advancePosition(State, LHS, Op, *value); - if (NewState) { - const auto *NewPos = getIteratorPosition(NewState, LHS); - assert(NewPos && - "Iterator should have position after successful advancement"); - - State = setIteratorPosition(NewState, TgtVal, *NewPos); - C.addTransition(State); - } else { - assignToContainer(C, CE, TgtVal, Pos->getContainer()); - } -} - -void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE, +void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -691,7 +280,7 @@ C.addTransition(State); } -void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE, +void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -713,23 +302,9 @@ C.addTransition(State); } -void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE, - const SVal &RetVal, - const MemRegion *Cont) const { - Cont = Cont->getMostDerivedObjectRegion(); - - auto State = C.getState(); - auto &SymMgr = C.getSymbolManager(); - auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, Sym, 4); - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(Cont, Sym)); - C.addTransition(State); -} - -void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE, const SVal &OldCont) const { +void ContainerModeling::handleAssignment(CheckerContext &C, const SVal &Cont, + const Expr *CE, + const SVal &OldCont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -792,7 +367,7 @@ ContainerData::fromBegin(OldBeginSym)); } State = - setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); + setContainerData(State, OldContReg, OldCData->newBegin(nullptr)); } } else { // There was neither "begin" nor "end" symbol assigned yet to the old @@ -804,7 +379,21 @@ C.addTransition(State); } -void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const { +void ContainerModeling::handleAssign(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); + + // The assign() operation invalidates all the iterators + auto State = C.getState(); + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); +} + +void ContainerModeling::handleClear(CheckerContext &C, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -830,7 +419,7 @@ C.addTransition(State); } -void IteratorModeling::handlePushBack(CheckerContext &C, +void ContainerModeling::handlePushBack(CheckerContext &C, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -868,7 +457,7 @@ C.addTransition(State); } -void IteratorModeling::handlePopBack(CheckerContext &C, +void ContainerModeling::handlePopBack(CheckerContext &C, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -906,7 +495,7 @@ } } -void IteratorModeling::handlePushFront(CheckerContext &C, +void ContainerModeling::handlePushFront(CheckerContext &C, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -939,7 +528,7 @@ } } -void IteratorModeling::handlePopFront(CheckerContext &C, +void ContainerModeling::handlePopFront(CheckerContext &C, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) @@ -973,7 +562,14 @@ } } -void IteratorModeling::handleInsert(CheckerContext &C, const SVal &Iter) const { +void ContainerModeling::handleInsert(CheckerContext &C, const SVal &Cont, + const SVal &Iter) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); + auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) @@ -981,24 +577,30 @@ // For deque-like containers invalidate all iterator positions. For // vector-like containers invalidate iterator positions after the insertion. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); + if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { + if (frontModifiable(State, ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); } else { State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); } - if (const auto *CData = getContainerData(State, Cont)) { + if (const auto *CData = getContainerData(State, ContReg)) { if (const auto EndSym = CData->getEnd()) { State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); + State = setContainerData(State, ContReg, CData->newEnd(nullptr)); } } C.addTransition(State); } } -void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter) const { +void ContainerModeling::handleErase(CheckerContext &C, const SVal &Cont, + const SVal &Iter) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); + auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) @@ -1007,17 +609,16 @@ // For deque-like containers invalidate all iterator positions. For // vector-like containers invalidate iterator positions at and after the // deletion. For list-like containers only invalidate the deleted position. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); + if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { + if (frontModifiable(State, ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); } else { State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); } - if (const auto *CData = getContainerData(State, Cont)) { + if (const auto *CData = getContainerData(State, ContReg)) { if (const auto EndSym = CData->getEnd()) { State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); + State = setContainerData(State, ContReg, CData->newEnd(nullptr)); } } } else { @@ -1026,8 +627,14 @@ C.addTransition(State); } -void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { +void ContainerModeling::handleErase(CheckerContext &C, const SVal &Cont, + const SVal &Iter1, + const SVal &Iter2) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + ContReg = ContReg->getMostDerivedObjectRegion(); auto State = C.getState(); const auto *Pos1 = getIteratorPosition(State, Iter1); const auto *Pos2 = getIteratorPosition(State, Iter2); @@ -1038,17 +645,16 @@ // vector-like containers invalidate iterator positions at and after the // deletion range. For list-like containers only invalidate the deleted // position range [first..last]. - const auto *Cont = Pos1->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); + if (hasSubscriptOperator(State, ContReg) && backModifiable(State, ContReg)) { + if (frontModifiable(State, ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); } else { State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); } - if (const auto *CData = getContainerData(State, Cont)) { + if (const auto *CData = getContainerData(State, ContReg)) { if (const auto EndSym = CData->getEnd()) { State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); + State = setContainerData(State, ContReg, CData->newEnd(nullptr)); } } } else { @@ -1058,7 +664,7 @@ C.addTransition(State); } -void IteratorModeling::handleEraseAfter(CheckerContext &C, +void ContainerModeling::handleEraseAfter(CheckerContext &C, const SVal &Cont, const SVal &Iter) const { auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); @@ -1079,8 +685,9 @@ C.addTransition(State); } -void IteratorModeling::handleEraseAfter(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { +void ContainerModeling::handleEraseAfter(CheckerContext &C, const SVal &Cont, + const SVal &Iter1, + const SVal &Iter2) const { auto State = C.getState(); const auto *Pos1 = getIteratorPosition(State, Iter1); const auto *Pos2 = getIteratorPosition(State, Iter2); @@ -1093,9 +700,8 @@ C.addTransition(State); } -void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State, +void ContainerModeling::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { - auto ContMap = State->get(); if (!ContMap.isEmpty()) { @@ -1113,43 +719,13 @@ CData.getEnd()->dumpToStream(Out); else Out << ""; - Out << " ]" << NL; - } - } - - auto SymbolMap = State->get(); - auto RegionMap = State->get(); - - if (!SymbolMap.isEmpty() || !RegionMap.isEmpty()) { - Out << Sep << "Iterator Positions :" << NL; - for (const auto &Sym : SymbolMap) { - Sym.first->dumpToStream(Out); - Out << " : "; - const auto Pos = Sym.second; - Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == "; - Pos.getContainer()->dumpToStream(Out); - Out<<" ; Offset == "; - Pos.getOffset()->dumpToStream(Out); - } - - for (const auto &Reg : RegionMap) { - Reg.first->dumpToStream(Out); - Out << " : "; - const auto Pos = Reg.second; - Out << (Pos.isValid() ? "Valid" : "Invalid") << " ; Container == "; - Pos.getContainer()->dumpToStream(Out); - Out<<" ; Offset == "; - Pos.getOffset()->dumpToStream(Out); + Out << " ]"; } } } - namespace { -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg); - bool isBeginCall(const FunctionDecl *Func) { const auto *IdInfo = Func->getIdentifier(); if (!IdInfo) @@ -1164,82 +740,18 @@ return IdInfo->getName().endswith_lower("end"); } -bool isAssignCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 2) - return false; - return IdInfo->getName() == "assign"; -} - -bool isClearCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "clear"; -} - -bool isPushBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_back"; -} - -bool isEmplaceBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_back"; -} - -bool isPopBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_back"; -} - -bool isPushFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_front"; -} - -bool isEmplaceFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_front"; -} - -bool isPopFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_front"; -} +const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, + const MemRegion *Reg) { + auto TI = getDynamicTypeInfo(State, Reg); + if (!TI.isValid()) + return nullptr; -bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } + auto Type = TI.getType(); + if (const auto *RefT = Type->getAs()) { + Type = RefT->getPointeeType(); + } -bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { - return OK == OO_EqualEqual || OK == OO_ExclaimEqual; + return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); } bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { @@ -1288,20 +800,6 @@ return false; } -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg) { - auto TI = getDynamicTypeInfo(State, Reg); - if (!TI.isValid()) - return nullptr; - - auto Type = TI.getType(); - if (const auto *RefT = Type->getAs()) { - Type = RefT->getPointeeType(); - } - - return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); -} - SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { const auto *CDataPtr = getContainerData(State, Cont); if (!CDataPtr) @@ -1369,119 +867,6 @@ return State->set(Cont, CData); } -ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) { - if (auto Reg = Val.getAsRegion()) { - Reg = Reg->getMostDerivedObjectRegion(); - return State->remove(Reg); - } else if (const auto Sym = Val.getAsSymbol()) { - return State->remove(Sym); - } else if (const auto LCVal = Val.getAs()) { - return State->remove(LCVal->getRegion()); - } - return nullptr; -} - -// This function tells the analyzer's engine that symbols produced by our -// checker, most notably iterator positions, are relatively small. -// A distance between items in the container should not be very large. -// By assuming that it is within around 1/8 of the address space, -// we can help the analyzer perform operations on these symbols -// without being afraid of integer overflows. -// FIXME: Should we provide it as an API, so that all checkers could use it? -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale) { - SValBuilder &SVB = State->getStateManager().getSValBuilder(); - BasicValueFactory &BV = SVB.getBasicValueFactory(); - - QualType T = Sym->getType(); - assert(T->isSignedIntegerOrEnumerationType()); - APSIntType AT = BV.getAPSIntType(T); - - ProgramStateRef NewState = State; - - llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); - SVal IsCappedFromAbove = - SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Max), SVB.getConditionType()); - if (auto DV = IsCappedFromAbove.getAs()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - llvm::APSInt Min = -Max; - SVal IsCappedFromBelow = - SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Min), SVB.getConditionType()); - if (auto DV = IsCappedFromBelow.getAs()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - return NewState; -} - -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal) { - auto &SVB = State->getStateManager().getSValBuilder(); - - // FIXME: This code should be reworked as follows: - // 1. Subtract the operands using evalBinOp(). - // 2. Assume that the result doesn't overflow. - // 3. Compare the result to 0. - // 4. Assume the result of the comparison. - const auto comparison = - SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1), - nonloc::SymbolVal(Sym2), SVB.getConditionType()); - - assert(comparison.getAs() && - "Symbol comparison must be a `DefinedSVal`"); - - auto NewState = State->assume(comparison.castAs(), Equal); - if (!NewState) - return nullptr; - - if (const auto CompSym = comparison.getAsSymbol()) { - assert(isa(CompSym) && - "Symbol comparison must be a `SymIntExpr`"); - assert(BinaryOperator::isComparisonOp( - cast(CompSym)->getOpcode()) && - "Symbol comparison must be a comparison"); - return assumeNoOverflow(NewState, cast(CompSym)->getLHS(), 2); - } - - return NewState; -} - -bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { - auto RegionMap = State->get(); - for (const auto &Reg : RegionMap) { - if (Reg.second.getContainer() == Cont) - return true; - } - - auto SymbolMap = State->get(); - for (const auto &Sym : SymbolMap) { - if (Sym.second.getContainer() == Cont) - return true; - } - - return false; -} - -bool isBoundThroughLazyCompoundVal(const Environment &Env, - const MemRegion *Reg) { - for (const auto &Binding : Env) { - if (const auto LCVal = Binding.second.getAs()) { - if (LCVal->getRegion() == Reg) - return true; - } - } - - return false; -} - template ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, Process Proc) { @@ -1628,12 +1013,28 @@ SymMgr.getType(OrigExpr)).getAsSymbol(); } +bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { + auto RegionMap = State->get(); + for (const auto &Reg : RegionMap) { + if (Reg.second.getContainer() == Cont) + return true; + } + + auto SymbolMap = State->get(); + for (const auto &Sym : SymbolMap) { + if (Sym.second.getContainer() == Cont) + return true; + } + + return false; +} + } // namespace -void ento::registerIteratorModeling(CheckerManager &mgr) { - mgr.registerChecker(); +void ento::registerContainerModeling(CheckerManager &mgr) { + mgr.registerChecker(); } -bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) { +bool ento::shouldRegisterContainerModeling(const LangOptions &LO) { return true; } diff --git a/clang/lib/StaticAnalyzer/Checkers/DebugContainerModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/DebugContainerModeling.cpp new file mode 100644 --- /dev/null +++ b/clang/lib/StaticAnalyzer/Checkers/DebugContainerModeling.cpp @@ -0,0 +1,138 @@ +//==-- DebugContainerModeling.cpp ---------------------------------*- C++ -*--// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Defines a checker for debugging iterator modeling. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +#include "Iterator.h" + +using namespace clang; +using namespace ento; +using namespace iterator; + +namespace { + +class DebugContainerModeling + : public Checker { + + std::unique_ptr DebugMsgBugType; + + template + void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C, + Getter get) const; + void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const; + void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const; + ExplodedNode *reportDebugMsg(llvm::StringRef Msg, CheckerContext &C) const; + + typedef void (DebugContainerModeling::*FnCheck)(const CallExpr *, + CheckerContext &) const; + + CallDescriptionMap Callbacks = { + {{0, "clang_analyzer_container_begin", 1}, + &DebugContainerModeling::analyzerContainerBegin}, + {{0, "clang_analyzer_container_end", 1}, + &DebugContainerModeling::analyzerContainerEnd}, + }; + +public: + DebugContainerModeling(); + + bool evalCall(const CallEvent &Call, CheckerContext &C) const; +}; + +} //namespace + +DebugContainerModeling::DebugContainerModeling() { + DebugMsgBugType.reset( + new BugType(this, "Checking analyzer assumptions", "debug", + /*SuppressOnSink=*/true)); +} + +bool DebugContainerModeling::evalCall(const CallEvent &Call, + CheckerContext &C) const { + const auto *CE = dyn_cast_or_null(Call.getOriginExpr()); + if (!CE) + return false; + + const FnCheck *Handler = Callbacks.lookup(Call); + if (!Handler) + return false; + + (this->**Handler)(CE, C); + return true; +} + +template +void DebugContainerModeling::analyzerContainerDataField(const CallExpr *CE, + CheckerContext &C, + Getter get) const { + if (CE->getNumArgs() == 0) { + reportDebugMsg("Missing container argument", C); + return; + } + + auto State = C.getState(); + const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion(); + if (Cont) { + const auto *Data = getContainerData(State, Cont); + if (Data) { + SymbolRef Field = get(Data); + if (Field) { + State = State->BindExpr(CE, C.getLocationContext(), + nonloc::SymbolVal(Field)); + C.addTransition(State); + return; + } + } + } + + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + State = State->BindExpr(CE, C.getLocationContext(), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); +} + +void DebugContainerModeling::analyzerContainerBegin(const CallExpr *CE, + CheckerContext &C) const { + analyzerContainerDataField(CE, C, [](const ContainerData *D) { + return D->getBegin(); + }); +} + +void DebugContainerModeling::analyzerContainerEnd(const CallExpr *CE, + CheckerContext &C) const { + analyzerContainerDataField(CE, C, [](const ContainerData *D) { + return D->getEnd(); + }); +} + +ExplodedNode *DebugContainerModeling::reportDebugMsg(llvm::StringRef Msg, + CheckerContext &C) const { + ExplodedNode *N = C.generateNonFatalErrorNode(); + if (!N) + return nullptr; + + auto &BR = C.getBugReporter(); + BR.emitReport(std::make_unique(*DebugMsgBugType, + Msg, N)); + return N; +} + +void ento::registerDebugContainerModeling(CheckerManager &mgr) { + mgr.registerChecker(); +} + +bool ento::shouldRegisterDebugContainerModeling(const LangOptions &LO) { + return true; +} diff --git a/clang/lib/StaticAnalyzer/Checkers/DebugIteratorModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/DebugIteratorModeling.cpp --- a/clang/lib/StaticAnalyzer/Checkers/DebugIteratorModeling.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/DebugIteratorModeling.cpp @@ -30,11 +30,6 @@ std::unique_ptr DebugMsgBugType; template - void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C, - Getter get) const; - void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const; - void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const; - template void analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C, Getter get, SVal Default) const; void analyzerIteratorPosition(const CallExpr *CE, CheckerContext &C) const; @@ -46,10 +41,6 @@ CheckerContext &) const; CallDescriptionMap Callbacks = { - {{0, "clang_analyzer_container_begin", 1}, - &DebugIteratorModeling::analyzerContainerBegin}, - {{0, "clang_analyzer_container_end", 1}, - &DebugIteratorModeling::analyzerContainerEnd}, {{0, "clang_analyzer_iterator_position", 1}, &DebugIteratorModeling::analyzerIteratorPosition}, {{0, "clang_analyzer_iterator_container", 1}, @@ -87,49 +78,6 @@ } template -void DebugIteratorModeling::analyzerContainerDataField(const CallExpr *CE, - CheckerContext &C, - Getter get) const { - if (CE->getNumArgs() == 0) { - reportDebugMsg("Missing container argument", C); - return; - } - - auto State = C.getState(); - const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion(); - if (Cont) { - const auto *Data = getContainerData(State, Cont); - if (Data) { - SymbolRef Field = get(Data); - if (Field) { - State = State->BindExpr(CE, C.getLocationContext(), - nonloc::SymbolVal(Field)); - C.addTransition(State); - return; - } - } - } - - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - State = State->BindExpr(CE, C.getLocationContext(), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); -} - -void DebugIteratorModeling::analyzerContainerBegin(const CallExpr *CE, - CheckerContext &C) const { - analyzerContainerDataField(CE, C, [](const ContainerData *D) { - return D->getBegin(); - }); -} - -void DebugIteratorModeling::analyzerContainerEnd(const CallExpr *CE, - CheckerContext &C) const { - analyzerContainerDataField(CE, C, [](const ContainerData *D) { - return D->getEnd(); - }); -} - -template void DebugIteratorModeling::analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C, Getter get, diff --git a/clang/lib/StaticAnalyzer/Checkers/Iterator.h b/clang/lib/StaticAnalyzer/Checkers/Iterator.h --- a/clang/lib/StaticAnalyzer/Checkers/Iterator.h +++ b/clang/lib/StaticAnalyzer/Checkers/Iterator.h @@ -163,6 +163,8 @@ const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance); +ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, + long Scale); bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, diff --git a/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp b/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp --- a/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/Iterator.cpp @@ -204,6 +204,47 @@ return nullptr; } +// This function tells the analyzer's engine that symbols produced by our +// checker, most notably iterator positions, are relatively small. +// A distance between items in the container should not be very large. +// By assuming that it is within around 1/8 of the address space, +// we can help the analyzer perform operations on these symbols +// without being afraid of integer overflows. +// FIXME: Should we provide it as an API, so that all checkers could use it? +ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, + long Scale) { + SValBuilder &SVB = State->getStateManager().getSValBuilder(); + BasicValueFactory &BV = SVB.getBasicValueFactory(); + + QualType T = Sym->getType(); + assert(T->isSignedIntegerOrEnumerationType()); + APSIntType AT = BV.getAPSIntType(T); + + ProgramStateRef NewState = State; + + llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); + SVal IsCappedFromAbove = + SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), + nonloc::ConcreteInt(Max), SVB.getConditionType()); + if (auto DV = IsCappedFromAbove.getAs()) { + NewState = NewState->assume(*DV, true); + if (!NewState) + return State; + } + + llvm::APSInt Min = -Max; + SVal IsCappedFromBelow = + SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), + nonloc::ConcreteInt(Min), SVB.getConditionType()); + if (auto DV = IsCappedFromBelow.getAs()) { + NewState = NewState->assume(*DV, true); + if (!NewState) + return State; + } + + return NewState; +} + bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc) { return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp b/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp --- a/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ b/clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -6,8 +6,7 @@ // //===----------------------------------------------------------------------===// // -// Defines a checker for using iterators outside their range (past end). Usage -// means here dereferencing, incrementing etc. +// Defines a modeling-checker for modeling STL iterator-like iterators. // //===----------------------------------------------------------------------===// // @@ -100,27 +99,8 @@ void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, OverloadedOperatorKind Op, const SVal &RetVal, const SVal &LHS, const SVal &RHS) const; - void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const SVal &Cont) const; - void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const SVal &Cont) const; void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const; - void handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE = nullptr, - const SVal &OldCont = UndefinedVal()) const; - void handleClear(CheckerContext &C, const SVal &Cont) const; - void handlePushBack(CheckerContext &C, const SVal &Cont) const; - void handlePopBack(CheckerContext &C, const SVal &Cont) const; - void handlePushFront(CheckerContext &C, const SVal &Cont) const; - void handlePopFront(CheckerContext &C, const SVal &Cont) const; - void handleInsert(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; @@ -137,66 +117,10 @@ void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; }; -bool isBeginCall(const FunctionDecl *Func); -bool isEndCall(const FunctionDecl *Func); -bool isAssignCall(const FunctionDecl *Func); -bool isClearCall(const FunctionDecl *Func); -bool isPushBackCall(const FunctionDecl *Func); -bool isEmplaceBackCall(const FunctionDecl *Func); -bool isPopBackCall(const FunctionDecl *Func); -bool isPushFrontCall(const FunctionDecl *Func); -bool isEmplaceFrontCall(const FunctionDecl *Func); -bool isPopFrontCall(const FunctionDecl *Func); -bool isAssignmentOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); -bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); -bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); -bool backModifiable(ProgramStateRef State, const MemRegion *Reg); -SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); -SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); -ProgramStateRef createContainerBegin(ProgramStateRef State, - const MemRegion *Cont, const Expr *E, - QualType T, const LocationContext *LCtx, - unsigned BlockCount); -ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, - const Expr *E, QualType T, - const LocationContext *LCtx, - unsigned BlockCount); -ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, - const ContainerData &CData); ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale); -ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont); -ProgramStateRef -invalidateAllIteratorPositionsExcept(ProgramStateRef State, - const MemRegion *Cont, SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset1, - BinaryOperator::Opcode Opc1, - SymbolRef Offset2, - BinaryOperator::Opcode Opc2); -ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont); -ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont, - SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef rebaseSymbolInIteratorPositionsIf( - ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, - SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, bool Equal); -SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, - SymbolRef OldSym, SymbolRef NewSym); -bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg); @@ -211,18 +135,7 @@ if (Func->isOverloadedOperator()) { const auto Op = Func->getOverloadedOperator(); - if (isAssignmentOperator(Op)) { - // Overloaded 'operator=' must be a non-static member function. - const auto *InstCall = cast(&Call); - if (cast(Func)->isMoveAssignmentOperator()) { - handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), - Call.getArgSVal(0)); - return; - } - - handleAssign(C, InstCall->getCXXThisVal()); - return; - } else if (isSimpleComparisonOperator(Op)) { + if (isSimpleComparisonOperator(Op)) { const auto *OrigExpr = Call.getOriginExpr(); if (!OrigExpr) return; @@ -280,90 +193,15 @@ return; } } else { - if (const auto *InstCall = dyn_cast(&Call)) { - if (isAssignCall(Func)) { - handleAssign(C, InstCall->getCXXThisVal()); - return; - } - - if (isClearCall(Func)) { - handleClear(C, InstCall->getCXXThisVal()); - return; - } - - if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { - handlePushBack(C, InstCall->getCXXThisVal()); - return; - } - - if (isPopBackCall(Func)) { - handlePopBack(C, InstCall->getCXXThisVal()); - return; - } - - if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { - handlePushFront(C, InstCall->getCXXThisVal()); - return; - } - - if (isPopFrontCall(Func)) { - handlePopFront(C, InstCall->getCXXThisVal()); - return; - } - - if (isInsertCall(Func) || isEmplaceCall(Func)) { - handleInsert(C, Call.getArgSVal(0)); - return; - } - - if (isEraseCall(Func)) { - if (Call.getNumArgs() == 1) { - handleErase(C, Call.getArgSVal(0)); - return; - } - - if (Call.getNumArgs() == 2) { - handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - - if (isEraseAfterCall(Func)) { - if (Call.getNumArgs() == 1) { - handleEraseAfter(C, Call.getArgSVal(0)); - return; - } - - if (Call.getNumArgs() == 2) { - handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - } + if (!isIteratorType(Call.getResultType())) + return; const auto *OrigExpr = Call.getOriginExpr(); if (!OrigExpr) return; - if (!isIteratorType(Call.getResultType())) - return; - auto State = C.getState(); - if (const auto *InstCall = dyn_cast(&Call)) { - if (isBeginCall(Func)) { - handleBegin(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); - return; - } - - if (isEndCall(Func)) { - handleEnd(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); - return; - } - } - // Already bound to container? if (getIteratorPosition(State, Call.getReturnValue())) return; @@ -426,8 +264,7 @@ void IteratorModeling::checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const { - // Keep symbolic expressions of iterator positions, container begins and ends - // alive + // Keep symbolic expressions of iterator positions alive auto RegionMap = State->get(); for (const auto &Reg : RegionMap) { const auto Offset = Reg.second.getOffset(); @@ -444,20 +281,6 @@ SR.markLive(*i); } - auto ContMap = State->get(); - for (const auto &Cont : ContMap) { - const auto CData = Cont.second; - if (CData.getBegin()) { - SR.markLive(CData.getBegin()); - if(const auto *SIE = dyn_cast(CData.getBegin())) - SR.markLive(SIE->getLHS()); - } - if (CData.getEnd()) { - SR.markLive(CData.getEnd()); - if(const auto *SIE = dyn_cast(CData.getEnd())) - SR.markLive(SIE->getLHS()); - } - } } void IteratorModeling::checkDeadSymbols(SymbolReaper &SR, @@ -484,17 +307,6 @@ } } - auto ContMap = State->get(); - for (const auto &Cont : ContMap) { - if (!SR.isLiveRegion(Cont.first)) { - // We must keep the container data while it has live iterators to be able - // to compare them to the begin and the end of the container. - if (!hasLiveIterators(State, Cont.first)) { - State = State->remove(Cont.first); - } - } - } - C.addTransition(State); } @@ -669,50 +481,6 @@ } } -void IteratorModeling::handleBegin(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // If the container already has a begin symbol then use it. Otherwise first - // create a new one. - auto State = C.getState(); - auto BeginSym = getContainerBegin(State, ContReg); - if (!BeginSym) { - State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, - C.getLocationContext(), C.blockCount()); - BeginSym = getContainerBegin(State, ContReg); - } - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(ContReg, BeginSym)); - C.addTransition(State); -} - -void IteratorModeling::handleEnd(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // If the container already has an end symbol then use it. Otherwise first - // create a new one. - auto State = C.getState(); - auto EndSym = getContainerEnd(State, ContReg); - if (!EndSym) { - State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, - C.getLocationContext(), C.blockCount()); - EndSym = getContainerEnd(State, ContReg); - } - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(ContReg, EndSym)); - C.addTransition(State); -} - void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const { @@ -728,395 +496,8 @@ C.addTransition(State); } -void IteratorModeling::handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE, const SVal &OldCont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // Assignment of a new value to a container always invalidates all its - // iterators - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (CData) { - State = invalidateAllIteratorPositions(State, ContReg); - } - - // In case of move, iterators of the old container (except the past-end - // iterators) remain valid but refer to the new container - if (!OldCont.isUndef()) { - const auto *OldContReg = OldCont.getAsRegion(); - if (OldContReg) { - OldContReg = OldContReg->getMostDerivedObjectRegion(); - const auto OldCData = getContainerData(State, OldContReg); - if (OldCData) { - if (const auto OldEndSym = OldCData->getEnd()) { - // If we already assigned an "end" symbol to the old container, then - // first reassign all iterator positions to the new container which - // are not past the container (thus not greater or equal to the - // current "end" symbol). - State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, - OldEndSym, BO_GE); - auto &SymMgr = C.getSymbolManager(); - auto &SVB = C.getSValBuilder(); - // Then generate and assign a new "end" symbol for the new container. - auto NewEndSym = - SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, NewEndSym, 4); - if (CData) { - State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); - } else { - State = setContainerData(State, ContReg, - ContainerData::fromEnd(NewEndSym)); - } - // Finally, replace the old "end" symbol in the already reassigned - // iterator positions with the new "end" symbol. - State = rebaseSymbolInIteratorPositionsIf( - State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT); - } else { - // There was no "end" symbol assigned yet to the old container, - // so reassign all iterator positions to the new container. - State = reassignAllIteratorPositions(State, OldContReg, ContReg); - } - if (const auto OldBeginSym = OldCData->getBegin()) { - // If we already assigned a "begin" symbol to the old container, then - // assign it to the new container and remove it from the old one. - if (CData) { - State = - setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); - } else { - State = setContainerData(State, ContReg, - ContainerData::fromBegin(OldBeginSym)); - } - State = - setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); - } - } else { - // There was neither "begin" nor "end" symbol assigned yet to the old - // container, so reassign all iterator positions to the new container. - State = reassignAllIteratorPositions(State, OldContReg, ContReg); - } - } - } - C.addTransition(State); -} - -void IteratorModeling::handleClear(CheckerContext &C, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // The clear() operation invalidates all the iterators, except the past-end - // iterators of list-like containers - auto State = C.getState(); - if (!hasSubscriptOperator(State, ContReg) || - !backModifiable(State, ContReg)) { - const auto CData = getContainerData(State, ContReg); - if (CData) { - if (const auto EndSym = CData->getEnd()) { - State = - invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE); - C.addTransition(State); - return; - } - } - } - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); -} - -void IteratorModeling::handlePushBack(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // For deque-like containers invalidate all iterator positions - auto State = C.getState(); - if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) { - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); - return; - } - - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - // For vector-like containers invalidate the past-end iterator positions - if (const auto EndSym = CData->getEnd()) { - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - } - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newEndSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(EndSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(EndSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); - } - C.addTransition(State); -} - -void IteratorModeling::handlePopBack(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - if (const auto EndSym = CData->getEnd()) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto BackSym = - SVB.evalBinOp(State, BO_Sub, - nonloc::SymbolVal(EndSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(EndSym)).getAsSymbol(); - // For vector-like and deque-like containers invalidate the last and the - // past-end iterator positions. For list-like containers only invalidate - // the last position - if (hasSubscriptOperator(State, ContReg) && - backModifiable(State, ContReg)) { - State = invalidateIteratorPositions(State, BackSym, BO_GE); - State = setContainerData(State, ContReg, CData->newEnd(nullptr)); - } else { - State = invalidateIteratorPositions(State, BackSym, BO_EQ); - } - auto newEndSym = BackSym; - State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); - C.addTransition(State); - } -} - -void IteratorModeling::handlePushFront(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // For deque-like containers invalidate all iterator positions - auto State = C.getState(); - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); - } else { - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - if (const auto BeginSym = CData->getBegin()) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newBeginSym = - SVB.evalBinOp(State, BO_Sub, - nonloc::SymbolVal(BeginSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(BeginSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); - C.addTransition(State); - } - } -} - -void IteratorModeling::handlePopFront(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - // For deque-like containers invalidate all iterator positions. For list-like - // iterators only invalidate the first position - if (const auto BeginSym = CData->getBegin()) { - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateIteratorPositions(State, BeginSym, BO_LE); - } else { - State = invalidateIteratorPositions(State, BeginSym, BO_EQ); - } - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newBeginSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(BeginSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(BeginSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); - C.addTransition(State); - } -} - -void IteratorModeling::handleInsert(CheckerContext &C, const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions after the insertion. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - C.addTransition(State); - } -} - -void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions at and after the - // deletion. For list-like containers only invalidate the deleted position. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ); - } - C.addTransition(State); -} - -void IteratorModeling::handleErase(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { - auto State = C.getState(); - const auto *Pos1 = getIteratorPosition(State, Iter1); - const auto *Pos2 = getIteratorPosition(State, Iter2); - if (!Pos1 || !Pos2) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions at and after the - // deletion range. For list-like containers only invalidate the deleted - // position range [first..last]. - const auto *Cont = Pos1->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - } else { - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE, - Pos2->getOffset(), BO_LT); - } - C.addTransition(State); -} - -void IteratorModeling::handleEraseAfter(CheckerContext &C, - const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // Invalidate the deleted iterator position, which is the position of the - // parameter plus one. - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto NextSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(Pos->getOffset()), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(Pos->getOffset())).getAsSymbol(); - State = invalidateIteratorPositions(State, NextSym, BO_EQ); - C.addTransition(State); -} - -void IteratorModeling::handleEraseAfter(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { - auto State = C.getState(); - const auto *Pos1 = getIteratorPosition(State, Iter1); - const auto *Pos2 = getIteratorPosition(State, Iter2); - if (!Pos1 || !Pos2) - return; - - // Invalidate the deleted iterator position range (first..last) - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT, - Pos2->getOffset(), BO_LT); - C.addTransition(State); -} - void IteratorModeling::printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const { - - auto ContMap = State->get(); - - if (!ContMap.isEmpty()) { - Out << Sep << "Container Data :" << NL; - for (const auto &Cont : ContMap) { - Cont.first->dumpToStream(Out); - Out << " : [ "; - const auto CData = Cont.second; - if (CData.getBegin()) - CData.getBegin()->dumpToStream(Out); - else - Out << ""; - Out << " .. "; - if (CData.getEnd()) - CData.getEnd()->dumpToStream(Out); - else - Out << ""; - Out << " ]" << NL; - } - } - auto SymbolMap = State->get(); auto RegionMap = State->get(); @@ -1144,231 +525,12 @@ } } - namespace { -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg); - -bool isBeginCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - return IdInfo->getName().endswith_lower("begin"); -} - -bool isEndCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - return IdInfo->getName().endswith_lower("end"); -} - -bool isAssignCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 2) - return false; - return IdInfo->getName() == "assign"; -} - -bool isClearCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "clear"; -} - -bool isPushBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_back"; -} - -bool isEmplaceBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_back"; -} - -bool isPopBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_back"; -} - -bool isPushFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_front"; -} - -bool isEmplaceFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_front"; -} - -bool isPopFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_front"; -} - -bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } - bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { return OK == OO_EqualEqual || OK == OO_ExclaimEqual; } -bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->isOverloadedOperator()) - continue; - const auto OPK = Method->getOverloadedOperator(); - if (OPK == OO_Subscript) { - return true; - } - } - return false; -} - -bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->getDeclName().isIdentifier()) - continue; - if (Method->getName() == "push_front" || Method->getName() == "pop_front") { - return true; - } - } - return false; -} - -bool backModifiable(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->getDeclName().isIdentifier()) - continue; - if (Method->getName() == "push_back" || Method->getName() == "pop_back") { - return true; - } - } - return false; -} - -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg) { - auto TI = getDynamicTypeInfo(State, Reg); - if (!TI.isValid()) - return nullptr; - - auto Type = TI.getType(); - if (const auto *RefT = Type->getAs()) { - Type = RefT->getPointeeType(); - } - - return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); -} - -SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { - const auto *CDataPtr = getContainerData(State, Cont); - if (!CDataPtr) - return nullptr; - - return CDataPtr->getBegin(); -} - -SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { - const auto *CDataPtr = getContainerData(State, Cont); - if (!CDataPtr) - return nullptr; - - return CDataPtr->getEnd(); -} - -ProgramStateRef createContainerBegin(ProgramStateRef State, - const MemRegion *Cont, const Expr *E, - QualType T, const LocationContext *LCtx, - unsigned BlockCount) { - // Only create if it does not exist - const auto *CDataPtr = getContainerData(State, Cont); - if (CDataPtr && CDataPtr->getBegin()) - return State; - - auto &SymMgr = State->getSymbolManager(); - const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, - "begin"); - State = assumeNoOverflow(State, Sym, 4); - - if (CDataPtr) { - const auto CData = CDataPtr->newBegin(Sym); - return setContainerData(State, Cont, CData); - } - - const auto CData = ContainerData::fromBegin(Sym); - return setContainerData(State, Cont, CData); -} - -ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, - const Expr *E, QualType T, - const LocationContext *LCtx, - unsigned BlockCount) { - // Only create if it does not exist - const auto *CDataPtr = getContainerData(State, Cont); - if (CDataPtr && CDataPtr->getEnd()) - return State; - - auto &SymMgr = State->getSymbolManager(); - const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, - "end"); - State = assumeNoOverflow(State, Sym, 4); - - if (CDataPtr) { - const auto CData = CDataPtr->newEnd(Sym); - return setContainerData(State, Cont, CData); - } - - const auto CData = ContainerData::fromEnd(Sym); - return setContainerData(State, Cont, CData); -} - -ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, - const ContainerData &CData) { - return State->set(Cont, CData); -} - ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) { if (auto Reg = Val.getAsRegion()) { Reg = Reg->getMostDerivedObjectRegion(); @@ -1381,47 +543,6 @@ return nullptr; } -// This function tells the analyzer's engine that symbols produced by our -// checker, most notably iterator positions, are relatively small. -// A distance between items in the container should not be very large. -// By assuming that it is within around 1/8 of the address space, -// we can help the analyzer perform operations on these symbols -// without being afraid of integer overflows. -// FIXME: Should we provide it as an API, so that all checkers could use it? -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale) { - SValBuilder &SVB = State->getStateManager().getSValBuilder(); - BasicValueFactory &BV = SVB.getBasicValueFactory(); - - QualType T = Sym->getType(); - assert(T->isSignedIntegerOrEnumerationType()); - APSIntType AT = BV.getAPSIntType(T); - - ProgramStateRef NewState = State; - - llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); - SVal IsCappedFromAbove = - SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Max), SVB.getConditionType()); - if (auto DV = IsCappedFromAbove.getAs()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - llvm::APSInt Min = -Max; - SVal IsCappedFromBelow = - SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Min), SVB.getConditionType()); - if (auto DV = IsCappedFromBelow.getAs()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - return NewState; -} - ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, bool Equal) { auto &SVB = State->getStateManager().getSValBuilder(); @@ -1454,22 +575,6 @@ return NewState; } -bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { - auto RegionMap = State->get(); - for (const auto &Reg : RegionMap) { - if (Reg.second.getContainer() == Cont) - return true; - } - - auto SymbolMap = State->get(); - for (const auto &Sym : SymbolMap) { - if (Sym.second.getContainer() == Cont) - return true; - } - - return false; -} - bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg) { for (const auto &Binding : Env) { @@ -1482,152 +587,6 @@ return false; } -template -ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, - Process Proc) { - auto &RegionMapFactory = State->get_context(); - auto RegionMap = State->get(); - bool Changed = false; - for (const auto &Reg : RegionMap) { - if (Cond(Reg.second)) { - RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); - Changed = true; - } - } - - if (Changed) - State = State->set(RegionMap); - - auto &SymbolMapFactory = State->get_context(); - auto SymbolMap = State->get(); - Changed = false; - for (const auto &Sym : SymbolMap) { - if (Cond(Sym.second)) { - SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); - Changed = true; - } - } - - if (Changed) - State = State->set(SymbolMap); - - return State; -} - -ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont) { - auto MatchCont = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont; - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, MatchCont, Invalidate); -} - -ProgramStateRef -invalidateAllIteratorPositionsExcept(ProgramStateRef State, - const MemRegion *Cont, SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto MatchContAndCompare = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont && - !compare(State, Pos.getOffset(), Offset, Opc); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, MatchContAndCompare, Invalidate); -} - -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto Compare = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), Offset, Opc); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, Compare, Invalidate); -} - -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset1, - BinaryOperator::Opcode Opc1, - SymbolRef Offset2, - BinaryOperator::Opcode Opc2) { - auto Compare = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), Offset1, Opc1) && - compare(State, Pos.getOffset(), Offset2, Opc2); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, Compare, Invalidate); -} - -ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont) { - auto MatchCont = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont; - }; - auto ReAssign = [&](const IteratorPosition &Pos) { - return Pos.reAssign(NewCont); - }; - return processIteratorPositions(State, MatchCont, ReAssign); -} - -ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont, - SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto MatchContAndCompare = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont && - !compare(State, Pos.getOffset(), Offset, Opc); - }; - auto ReAssign = [&](const IteratorPosition &Pos) { - return Pos.reAssign(NewCont); - }; - return processIteratorPositions(State, MatchContAndCompare, ReAssign); -} - -// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`, -// `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator -// position offsets where `CondSym` is true. -ProgramStateRef rebaseSymbolInIteratorPositionsIf( - ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, - SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { - auto LessThanEnd = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), CondSym, Opc); - }; - auto RebaseSymbol = [&](const IteratorPosition &Pos) { - return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym, - NewSym)); - }; - return processIteratorPositions(State, LessThanEnd, RebaseSymbol); -} - -// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`, -// `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression -// `OrigExpr`. -SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, - SymbolRef OrigExpr, SymbolRef OldExpr, - SymbolRef NewSym) { - auto &SymMgr = SVB.getSymbolManager(); - auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr), - nonloc::SymbolVal(OldExpr), - SymMgr.getType(OrigExpr)); - - const auto DiffInt = Diff.getAs(); - if (!DiffInt) - return OrigExpr; - - return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym), - SymMgr.getType(OrigExpr)).getAsSymbol(); -} - } // namespace void ento::registerIteratorModeling(CheckerManager &mgr) { diff --git a/clang/test/Analysis/container-modeling.cpp b/clang/test/Analysis/container-modeling.cpp new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/container-modeling.cpp @@ -0,0 +1,189 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=false %s -verify + +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,debug.DebugIteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorModeling,debug.ExprInspection -analyzer-config aggressive-binary-operation-simplification=true %s 2>&1 | FileCheck %s + +#include "Inputs/system-header-simulator-cxx.h" + +template +long clang_analyzer_container_begin(const Container&); +template +long clang_analyzer_container_end(const Container&); + +void clang_analyzer_denote(long, const char*); +void clang_analyzer_express(long); +void clang_analyzer_eval(bool); +void clang_analyzer_warnIfReached(); + +void begin(const std::vector &V) { + V.begin(); + + clang_analyzer_denote(clang_analyzer_container_begin(V), "$V.begin()"); + clang_analyzer_express(clang_analyzer_container_begin(V)); //expected-warning{{$V.begin()}} +} + +void end(const std::vector &V) { + V.end(); + + clang_analyzer_denote(clang_analyzer_container_end(V), "$V.end()"); + clang_analyzer_express(clang_analyzer_container_end(V)); //expected-warning{{$V.end()}} +} + +//////////////////////////////////////////////////////////////////////////////// +/// +/// C O N T A I N E R A S S I G N M E N T S +/// +//////////////////////////////////////////////////////////////////////////////// + +// Move + +void move_assignment(std::vector &V1, std::vector &V2) { + V1.cbegin(); + V1.cend(); + V2.cbegin(); + V2.cend(); + long B1 = clang_analyzer_container_begin(V1); + long E1 = clang_analyzer_container_end(V1); + long B2 = clang_analyzer_container_begin(V2); + long E2 = clang_analyzer_container_end(V2); + V1 = std::move(V2); + clang_analyzer_eval(clang_analyzer_container_begin(V1) == B2); //expected-warning{{TRUE}} + clang_analyzer_eval(clang_analyzer_container_end(V2) == E2); //expected-warning{{TRUE}} +} + +//////////////////////////////////////////////////////////////////////////////// +/// +/// C O N T A I N E R M O D I F I E R S +/// +//////////////////////////////////////////////////////////////////////////////// + +/// push_back() +/// +/// Design decision: extends containers to the ->RIGHT-> (i.e. the +/// past-the-end position of the container is incremented). + +void push_back(std::vector &V, int n) { + V.cbegin(); + V.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(V), "$V.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(V), "$V.end()"); + + V.push_back(n); + + clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} + clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() + 1}} +} + +/// emplace_back() +/// +/// Design decision: extends containers to the ->RIGHT-> (i.e. the +/// past-the-end position of the container is incremented). + +void emplace_back(std::vector &V, int n) { + V.cbegin(); + V.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(V), "$V.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(V), "$V.end()"); + + V.emplace_back(n); + + clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} + clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() + 1}} +} + +/// pop_back() +/// +/// Design decision: shrinks containers to the <-LEFT<- (i.e. the +/// past-the-end position of the container is decremented). + +void pop_back(std::vector &V, int n) { + V.cbegin(); + V.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(V), "$V.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(V), "$V.end()"); + + V.pop_back(); + + clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} + clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() - 1}} +} + +/// push_front() +/// +/// Design decision: extends containers to the <-LEFT<- (i.e. the first +/// position of the container is decremented). + +void push_front(std::deque &D, int n) { + D.cbegin(); + D.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(D), "$D.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(D), "$D.end()"); + + D.push_front(n); + + clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() - 1 (to correctly track the container's size) + clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} +} + +/// emplace_front() +/// +/// Design decision: extends containers to the <-LEFT<- (i.e. the first +/// position of the container is decremented). + +void deque_emplace_front(std::deque &D, int n) { + D.cbegin(); + D.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(D), "$D.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(D), "$D.end()"); + + D.emplace_front(n); + + clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin - 1 (to correctly track the container's size) + clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} +} + +/// pop_front() +/// +/// Design decision: shrinks containers to the ->RIGHT-> (i.e. the first +/// position of the container is incremented). + +void deque_pop_front(std::deque &D, int n) { + D.cbegin(); + D.cend(); + + clang_analyzer_denote(clang_analyzer_container_begin(D), "$D.begin()"); + clang_analyzer_denote(clang_analyzer_container_end(D), "$D.end()"); + + D.pop_front(); + + clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin() + 1}} + clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} +} + +void clang_analyzer_printState(); + +void print_state(std::vector &V) { + V.cbegin(); + clang_analyzer_printState(); + +// CHECK: "checker_messages": [ +// CHECK-NEXT: { "checker": "alpha.cplusplus.ContainerModeling", "messages": [ +// CHECK-NEXT: "Container Data :", +// CHECK-NEXT: "SymRegion{reg_$[[#]] & V>} : [ conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} .. ]" +// CHECK-NEXT: ]} + + V.cend(); + clang_analyzer_printState(); + +// CHECK: "checker_messages": [ +// CHECK-NEXT: { "checker": "alpha.cplusplus.ContainerModeling", "messages": [ +// CHECK-NEXT: "Container Data :", +// CHECK-NEXT: "SymRegion{reg_$[[#]] & V>} : [ conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} .. conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} ]" +// CHECK-NEXT: ]} +} diff --git a/clang/test/Analysis/debug-container-modeling.cpp b/clang/test/Analysis/debug-container-modeling.cpp new file mode 100644 --- /dev/null +++ b/clang/test/Analysis/debug-container-modeling.cpp @@ -0,0 +1,31 @@ +// RUN: %clang_analyze_cc1 -std=c++11\ +// RUN: -analyzer-checker=core,cplusplus\ +// RUN: -analyzer-checker=debug.DebugContainerModeling,debug.ExprInspection\ +// RUN: -analyzer-config aggressive-binary-operation-simplification=true\ +// RUN: -analyzer-config c++-container-inlining=false %s -verify + +// RUN: %clang_analyze_cc1 -std=c++11\ +// RUN: -analyzer-checker=core,cplusplus\ +// RUN: -analyzer-checker=debug.DebugContainerModeling,debug.ExprInspection\ +// RUN: -analyzer-config aggressive-binary-operation-simplification=true\ +// RUN: -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +template +long clang_analyzer_container_begin(const Container&); +template +long clang_analyzer_container_end(const Container&); +void clang_analyzer_denote(long, const char*); +void clang_analyzer_express(long); + +void container_begin_end(const std::vector v0) { + v0.begin(); + v0.end(); + + clang_analyzer_denote(clang_analyzer_container_begin(v0), "$b0"); + clang_analyzer_denote(clang_analyzer_container_end(v0), "$e0"); + + clang_analyzer_express(clang_analyzer_container_begin(v0)); // expected-warning{{$b0}} + clang_analyzer_express(clang_analyzer_container_end(v0)); // expected-warning{{$e0}} +} diff --git a/clang/test/Analysis/debug-iterator-modeling.cpp b/clang/test/Analysis/debug-iterator-modeling.cpp --- a/clang/test/Analysis/debug-iterator-modeling.cpp +++ b/clang/test/Analysis/debug-iterator-modeling.cpp @@ -30,15 +30,12 @@ void iterator_position(const std::vector v0) { auto b0 = v0.begin(), e0 = v0.end(); - clang_analyzer_denote(clang_analyzer_iterator_position(b0), "$b0"); - clang_analyzer_denote(clang_analyzer_iterator_position(e0), "$e0"); + clang_analyzer_denote(clang_analyzer_container_begin(v0), "$b0"); + clang_analyzer_denote(clang_analyzer_container_end(v0), "$e0"); clang_analyzer_express(clang_analyzer_iterator_position(b0)); // expected-warning{{$b0}} clang_analyzer_express(clang_analyzer_iterator_position(e0)); // expected-warning{{$e0}} - clang_analyzer_express(clang_analyzer_container_begin(v0)); // expected-warning{{$b0}} - clang_analyzer_express(clang_analyzer_container_end(v0)); // expected-warning{{$e0}} - ++b0; clang_analyzer_express(clang_analyzer_iterator_position(b0)); // expected-warning{{$b0 + 1}} diff --git a/clang/test/Analysis/iterator-modelling.cpp b/clang/test/Analysis/iterator-modelling.cpp --- a/clang/test/Analysis/iterator-modelling.cpp +++ b/clang/test/Analysis/iterator-modelling.cpp @@ -246,7 +246,6 @@ clang_analyzer_eval(clang_analyzer_iterator_container(i1) == &L1); // expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &L1); // expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L1)); // expected-warning{{$L2.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L2.begin()}} } @@ -265,7 +264,6 @@ clang_analyzer_eval(clang_analyzer_iterator_container(i1) == &V1); // expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &V1); // expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(V1)); // expected-warning{{$V2.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$V2.begin()}} } @@ -284,7 +282,6 @@ clang_analyzer_eval(clang_analyzer_iterator_container(i1) == &D1); // expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_container(i2) == &D1); // expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(D1)); // expected-warning{{$D2.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$D2.begin()}} } @@ -302,7 +299,6 @@ clang_analyzer_eval(clang_analyzer_iterator_container(i1) == &FL1); // expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL1)); // expected-warning{{$FL2.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL2.begin()}} } @@ -400,10 +396,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} FIXME: Should be $L.end() + 1 } @@ -422,10 +415,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$V.end() - 1}} } @@ -443,9 +433,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} FIXME: Should be $D.end() + 1 (to correctly track the container's size) } /// emplace_back() @@ -469,10 +456,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} FIXME: Should be $L.end() + 1 } @@ -491,10 +475,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$V.end() - 1}} } @@ -512,9 +493,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} FIXME: Should be $D.end() + 1 (to correctly track the container's size) } /// pop_back() @@ -538,10 +516,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} FIXME: Should be $L.end() - 1 } @@ -560,10 +535,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(V)); // expected-warning{{$V.end() - 1}} } /// std::deque-like containers: Iterators to the last element are invalidated. @@ -582,10 +554,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$D.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end() - 1}} } /// push_front() @@ -608,10 +577,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end()}} } @@ -629,10 +595,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() - 1 (to correctly track the container's size) - - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} } /// std::forward_list-like containers: No iterators are invalidated. @@ -648,10 +610,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.end()}} } @@ -675,10 +634,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end()}} } @@ -696,10 +652,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin - 1 (to correctly track the container's size) - - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} } /// std::forward_list-like containers: No iterators are invalidated. @@ -715,10 +667,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.end()}} } @@ -743,10 +692,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.begin() + 1}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -765,10 +711,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$D.begin() + 1}} - - clang_analyzer_express(clang_analyzer_container_end(D)); // expected-warning{{$D.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$D.end()}} } @@ -787,10 +730,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin() + 1}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.begin() + 1}} - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.end()}} } @@ -817,11 +757,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $L.begin() - 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end()}} } @@ -837,12 +774,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.begin() + 1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.begin() - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -861,13 +795,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$i1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i - 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -883,10 +813,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.end() - 2 @@ -904,10 +831,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end() - 1}} FIXME: should be $L.end() - 2 clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.end() - 1 @@ -928,10 +852,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $V.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); // FIXME: expect warning $V.end() } void vector_insert_behind_begin(std::vector &V, int n) { @@ -946,11 +867,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); // FIXME: expect -warning $V.begin() - - // clang_analyzer_express(clang_analyzer_container_end(V)); // FIXME: expect warning $V.end() } void vector_insert_unknown(std::vector &V, int n) { @@ -966,12 +884,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expecte warning $i1 - 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME expect warning $V.end() } void vector_insert_ahead_of_end(std::vector &V, int n) { @@ -986,10 +900,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.end() - 2 } @@ -1005,10 +916,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$V.end() - 1}} FIXME: Should be $V.end() - 2 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.end() - 1 } @@ -1027,10 +935,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $D.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_insert_behind_begin(std::deque &D, int n) { @@ -1045,10 +950,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_insert_unknown(std::deque &D, int n) { @@ -1064,11 +966,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_insert_ahead_of_end(std::deque &D, int n) { @@ -1083,9 +981,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.end() - 2 } @@ -1101,9 +996,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.end() - 1 } @@ -1128,11 +1020,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $FL.begin() + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.end()}} } @@ -1148,12 +1037,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.begin() + 1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $FL.begin() + 2 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.end()}} } @@ -1170,13 +1056,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} - clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$i1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.end()}} } @@ -1203,11 +1085,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $L.begin() - 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end()}} } @@ -1223,12 +1102,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.begin() + 1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.begin() - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -1247,13 +1123,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$i1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i - 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -1269,10 +1141,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end() - 1}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.end() - 2 @@ -1290,10 +1159,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.end() - 1}} FIXME: should be $L.end() - 2 clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.end() - 1 @@ -1313,11 +1179,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $V.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); // FIXME: expect warning $V.end() } void vector_emplace_behind_begin(std::vector &V, int n) { @@ -1332,11 +1194,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); // FIXME: expect -warning $V.begin() - - // clang_analyzer_express(clang_analyzer_container_end(V)); // FIXME: expect warning $V.end() } void vector_emplace_unknown(std::vector &V, int n) { @@ -1352,12 +1211,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expecte warning $i1 - 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME expect warning $V.end() } void vector_emplace_ahead_of_end(std::vector &V, int n) { @@ -1372,10 +1227,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.end() - 2 } @@ -1391,10 +1243,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$V.end() - 1}} FIXME: Should be $V.end() - 2 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.end() - 1 } @@ -1412,11 +1261,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $D.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_emplace_behind_begin(std::deque &D, int n) { @@ -1430,11 +1275,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin - 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.begin() - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_emplace_unknown(std::deque &D, int n) { @@ -1450,11 +1291,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 - 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_emplace_ahead_of_end(std::deque &D, int n) { @@ -1469,9 +1306,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.end() - 2 } @@ -1487,9 +1321,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.end() - 1 } @@ -1514,11 +1345,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i0)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} // clang_analyzer_express(clang_analyzer_iterator_position(i2)); FIXME: expect warning $FL.begin() + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.end()}} } @@ -1535,12 +1363,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$FL.begin() + 1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $FL.begin() + 2 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.end()}} } @@ -1557,13 +1382,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} - clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$i1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.end()}} } @@ -1592,11 +1413,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be$L.begin() + 1 clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$L.begin() + 1}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.begin() + 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -1612,11 +1430,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() + 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} FIXME: Should be $L.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.begin() + 2 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -1633,12 +1448,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 + 1 - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} } @@ -1654,10 +1465,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(L)); // expected-warning{{$L.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$L.begin()}} - - clang_analyzer_express(clang_analyzer_container_end(L)); // expected-warning{{$L.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$L.end()}} // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $L.end() } @@ -1677,10 +1485,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.begin() + 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() } void vector_erase_behind_begin(std::vector &V, int n) { @@ -1695,11 +1500,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() + 1 clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} FIXME: Should be $V.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.begin() + 2 - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() } void vector_erase_unknown(std::vector &V) { @@ -1715,12 +1517,8 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 + 1 - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() } void vector_erase_ahead_of_end(std::vector &V) { @@ -1735,10 +1533,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(V)); // expected-warning{{$V.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$V.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(V)); FIXME: expect warning $V.end() // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $V.end() } @@ -1762,10 +1557,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.begin() + 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning{{$D.end() } void deque_erase_behind_begin(std::deque &D, int n) { @@ -1780,10 +1572,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} FIXME: Should be $D.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.begin() + 2 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_erase_unknown(std::deque &D) { @@ -1799,11 +1588,7 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $i1 + 1 - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() } void deque_erase_ahead_of_end(std::deque &D) { @@ -1818,9 +1603,6 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i1)); //expected-warning{{FALSE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{FALSE}} - clang_analyzer_express(clang_analyzer_container_begin(D)); // expected-warning{{$D.begin()}} - - // clang_analyzer_express(clang_analyzer_container_end(D)); FIXME: expect warning $D.end() // clang_analyzer_express(clang_analyzer_iterator_position(i3)); FIXME: expect warning $D.end() } @@ -1851,12 +1633,9 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i2)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i3)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i2)); // expected-warning{{$FL.begin() + 2}} FIXME: Should be $FL.begin() + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i4)); FIXME: expect warning $FL.begin() + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i3)); // expected-warning{{$FL.end()}} } @@ -1879,14 +1658,10 @@ clang_analyzer_eval(clang_analyzer_iterator_validity(i3)); //expected-warning{{TRUE}} clang_analyzer_eval(clang_analyzer_iterator_validity(i4)); //expected-warning{{TRUE}} - clang_analyzer_express(clang_analyzer_container_begin(FL)); // expected-warning{{$FL.begin()}} clang_analyzer_express(clang_analyzer_iterator_position(i0)); // expected-warning{{$FL.begin()}} - clang_analyzer_express(clang_analyzer_iterator_position(i1)); // expected-warning{{$i1}} clang_analyzer_express(clang_analyzer_iterator_position(i3)); // expected-warning{{$i1 + 2}} FIXME: Should be $i1 + 1 // clang_analyzer_express(clang_analyzer_iterator_position(i5)); FIXME: expect warning $i1 + 1 - - clang_analyzer_express(clang_analyzer_container_end(FL)); // expected-warning{{$FL.end()}} clang_analyzer_express(clang_analyzer_iterator_position(i4)); // expected-warning{{$FL.end()}} } @@ -1981,9 +1756,7 @@ clang_analyzer_printState(); // CHECK: "checker_messages": [ -// CHECK-NEXT: { "checker": "alpha.cplusplus.IteratorModeling", "messages": [ -// CHECK-NEXT: "Container Data :", -// CHECK-NEXT: "SymRegion{reg_$[[#]] & V>} : [ conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} .. ]", +// CHECK: { "checker": "alpha.cplusplus.IteratorModeling", "messages": [ // CHECK-NEXT: "Iterator Positions :", // CHECK-NEXT: "i0 : Valid ; Container == SymRegion{reg_$[[#]] & V>} ; Offset == conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]}" // CHECK-NEXT: ]} @@ -1992,9 +1765,7 @@ clang_analyzer_printState(); // CHECK: "checker_messages": [ -// CHECK-NEXT: { "checker": "alpha.cplusplus.IteratorModeling", "messages": [ -// CHECK-NEXT: "Container Data :", -// CHECK-NEXT: "SymRegion{reg_$[[#]] & V>} : [ conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} .. conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]} ]", +// CHECK: { "checker": "alpha.cplusplus.IteratorModeling", "messages": [ // CHECK-NEXT: "Iterator Positions :", // CHECK-NEXT: "i1 : Valid ; Container == SymRegion{reg_$[[#]] & V>} ; Offset == conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]}" // CHECK-NEXT: ]}