Index: clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp @@ -179,39 +179,46 @@ } } else { if (const auto *InstCall = dyn_cast(&Call)) { - const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); - if (Handler0) { - (this->**Handler0)(C, InstCall->getCXXThisVal(), - InstCall->getCXXThisExpr()); + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; + + if (isBeginCall(Func)) { + handleBegin(C, OrigExpr, getReturnIterator(Call), + InstCall->getCXXThisVal()); return; } - const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); - if (Handler1) { - (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); + if (isEndCall(Func)) { + handleEnd(C, OrigExpr, getReturnIterator(Call), + InstCall->getCXXThisVal()); return; } - const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call); - if (Handler2) { - (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0), - Call.getArgSVal(1)); + const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); + if (Handler0) { + (this->**Handler0)(C, InstCall->getCXXThisVal(), + InstCall->getCXXThisExpr()); return; } - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) + if (Call.getNumArgs() < 1) return; - if (isBeginCall(Func)) { - handleBegin(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); + if (Handler1) { + (this->**Handler1)(C, InstCall->getCXXThisVal(), Arg0); return; } - if (isEndCall(Func)) { - handleEnd(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); + if (Call.getNumArgs() < 2) + return; + + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call); + if (Handler2) { + (this->**Handler2)(C, InstCall->getCXXThisVal(), Arg0, Arg1); return; } } @@ -257,7 +264,7 @@ } void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Cont) const { + SVal RetVal, SVal Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -273,13 +280,14 @@ C.getLocationContext(), C.blockCount()); BeginSym = getContainerBegin(State, ContReg); } + State = setIteratorPosition(State, RetVal, IteratorPosition::getPosition(ContReg, BeginSym)); C.addTransition(State); } void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Cont) const { + SVal RetVal, SVal Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -295,6 +303,7 @@ C.getLocationContext(), C.blockCount()); EndSym = getContainerEnd(State, ContReg); } + State = setIteratorPosition(State, RetVal, IteratorPosition::getPosition(ContReg, EndSym)); C.addTransition(State); Index: clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/InvalidatedIteratorChecker.cpp @@ -30,9 +30,9 @@ std::unique_ptr InvalidatedBugType; - void verifyAccess(CheckerContext &C, const SVal &Val) const; - void reportBug(const StringRef &Message, const SVal &Val, - CheckerContext &C, ExplodedNode *ErrNode) const; + void verifyAccess(CheckerContext &C, SVal Val) const; + void reportBug(const StringRef &Message, SVal Val, CheckerContext &C, + ExplodedNode *ErrNode) const; public: InvalidatedIteratorChecker(); @@ -60,12 +60,14 @@ if (const auto *InstCall = dyn_cast(&Call)) { verifyAccess(C, InstCall->getCXXThisVal()); } else { - verifyAccess(C, Call.getArgSVal(0)); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + verifyAccess(C, Arg0); } } } -void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { +void InvalidatedIteratorChecker::verifyAccess(CheckerContext &C, + SVal Val) const { auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Val); if (Pos && !Pos->isValid()) { @@ -78,7 +80,7 @@ } void InvalidatedIteratorChecker::reportBug(const StringRef &Message, - const SVal &Val, CheckerContext &C, + SVal Val, CheckerContext &C, ExplodedNode *ErrNode) const { auto R = std::make_unique(*InvalidatedBugType, Message, ErrNode); Index: clang/lib/StaticAnalyzer/Checkers/Iterator.h =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.h +++ clang/lib/StaticAnalyzer/Checkers/Iterator.h @@ -174,6 +174,17 @@ bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, BinaryOperator::Opcode Opc); +// Returns the value of the iterator argument if it non-class value (a pointer +// or a reference). Otherwise it returns the iterator parameter location (see +// CallEvent::getParameterLocation()). +SVal getIteratorArg(const CallEvent &Call, unsigned Index, unsigned BlockCount); + +// If the call returns an class instance iterator by value then this function +// retrieves and returns it from the construction context of the call. +// Otherwise (for non-class types) it simply returns the return value of the +// call. +SVal getReturnIterator(const CallEvent &Call); + } // namespace iterator } // namespace ento } // namespace clang Index: clang/lib/StaticAnalyzer/Checkers/Iterator.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.cpp +++ clang/lib/StaticAnalyzer/Checkers/Iterator.cpp @@ -10,6 +10,8 @@ // //===----------------------------------------------------------------------===// +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" + #include "Iterator.h" namespace clang { @@ -158,8 +160,6 @@ return State->get(Reg); } else if (const auto Sym = Val.getAsSymbol()) { return State->get(Sym); - } else if (const auto LCVal = Val.getAs()) { - return State->get(LCVal->getRegion()); } return nullptr; } @@ -171,10 +171,8 @@ return State->set(Reg, Pos); } else if (const auto Sym = Val.getAsSymbol()) { return State->set(Sym, Pos); - } else if (const auto LCVal = Val.getAs()) { - return State->set(LCVal->getRegion(), Pos); } - return nullptr; + return State; } ProgramStateRef createIteratorPosition(ProgramStateRef State, const SVal &Val, @@ -284,6 +282,32 @@ return !State->assume(comparison.castAs(), false); } +SVal getIteratorArg(const CallEvent& Call, unsigned Index, + unsigned BlockCount) { + SVal Arg = Call.getArgSVal(Index); + const Expr *ArgExpr = Call.getArgExpr(Index); + + if (ArgExpr->getValueKind() != VK_RValue) + return Arg; + + if (!ArgExpr->getType().getDesugaredType( + Call.getState()->getStateManager().getContext())->isRecordType()) + return Arg; + + return loc::MemRegionVal(Call.getParameterLocation(Index, BlockCount)); +} + +SVal getReturnIterator(const CallEvent &Call) { + Optional RetValUnderConstr = Call.getReturnValueUnderConstruction(); + if (RetValUnderConstr.hasValue()) { + llvm::errs()<<"Return Value Under Construction: "<<*RetValUnderConstr<<"\n"; + return *RetValUnderConstr; + } + + llvm::errs()<<"Return Value: "<, - check::Bind, check::LiveSymbols, check::DeadSymbols> { + : public Checker { using AdvanceFn = void (IteratorModeling::*)(CheckerContext &, const Expr *, SVal, SVal, SVal) const; @@ -96,25 +96,25 @@ const AdvanceFn *Handler) const; void handleComparison(CheckerContext &C, const Expr *CE, SVal RetVal, - const SVal &LVal, const SVal &RVal, - OverloadedOperatorKind Op) const; + SVal LVal, SVal RVal, OverloadedOperatorKind Op) const; void processComparison(CheckerContext &C, ProgramStateRef State, - SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal, + SymbolRef Sym1, SymbolRef Sym2, 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 handleIncrement(CheckerContext &C, SVal RetVal, + SVal Iter, bool Postfix) const; + void handleDecrement(CheckerContext &C, SVal RetVal, + SVal Iter, bool Postfix) const; void handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, - OverloadedOperatorKind Op, const SVal &RetVal, - const SVal &LHS, const SVal &RHS) const; - void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, - SVal Amount) const; - void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, - SVal Amount) const; - void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, SVal Iter, - SVal Amount) const; - void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, + OverloadedOperatorKind Op, + SVal RetVal, SVal LHS, + SVal RHS) const; + void handleAdvance(CheckerContext &C, const Expr *CE, SVal RetVal, + SVal Iter, SVal Amount) const; + void handlePrev(CheckerContext &C, const Expr *CE, SVal RetVal, + SVal Iter, SVal Amount) const; + void handleNext(CheckerContext &C, const Expr *CE, SVal RetVal, + SVal Iter, SVal Amount) const; + void assignToContainer(CheckerContext &C, const Expr *CE, SVal RetVal, const MemRegion *Cont) const; bool noChangeInAdvance(CheckerContext &C, SVal Iter, const Expr *CE) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, @@ -144,20 +144,14 @@ 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; }; bool isSimpleComparisonOperator(OverloadedOperatorKind OK); -ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); +ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val); ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, bool Equal); -bool isBoundThroughLazyCompoundVal(const Environment &Env, - const MemRegion *Reg); const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call); } // namespace @@ -191,15 +185,17 @@ auto State = C.getState(); // Already bound to container? - if (getIteratorPosition(State, Call.getReturnValue())) + SVal RetVal = getReturnIterator(Call); + if (getIteratorPosition(State, RetVal)) 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); + SVal Arg = getIteratorArg(Call, 0, C.blockCount()); + if (const auto *Pos = getIteratorPosition(State, Arg)) { + State = setIteratorPosition(State, RetVal, *Pos); if (cast(Func)->isMoveConstructor()) { - State = removeIteratorPosition(State, Call.getArgSVal(0)); + State = removeIteratorPosition(State, Arg); } C.addTransition(State); return; @@ -212,10 +208,12 @@ // 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 (isIteratorType(Call.getArgExpr(i)->getType()) && + Call.getArgExpr(i)->getType().getNonReferenceType().getDesugaredType( + C.getASTContext()).getTypePtr() == + Call.getResultType().getDesugaredType(C.getASTContext()).getTypePtr()) { if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { - assignToContainer(C, OrigExpr, Call.getReturnValue(), - Pos->getContainer()); + assignToContainer(C, OrigExpr, RetVal, Pos->getContainer()); return; } } @@ -225,6 +223,9 @@ void IteratorModeling::checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const { auto State = C.getState(); + if (Val.getAs()) + return; + const auto *Pos = getIteratorPosition(State, Val); if (Pos) { State = setIteratorPosition(State, Loc, *Pos); @@ -238,17 +239,6 @@ } } -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 alive @@ -256,8 +246,9 @@ 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)) + if (isa(*i)) { SR.markLive(*i); + } } auto SymbolMap = State->get(); @@ -278,12 +269,7 @@ 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); - } + State = State->remove(Reg.first); } } @@ -301,61 +287,64 @@ IteratorModeling::handleOverloadedOperator(CheckerContext &C, const CallEvent &Call, OverloadedOperatorKind Op) const { - if (isSimpleComparisonOperator(Op)) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; + 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; - } + if (isSimpleComparisonOperator(Op)) { + llvm::errs()<<"Simple comparison operator\n"; + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; - handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1), Op); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + if (const auto *InstCall = dyn_cast(&Call)) { + handleComparison(C, OrigExpr, Call.getReturnValue(), + InstCall->getCXXThisVal(), Arg0, Op); return; - } else if (isRandomIncrOrDecrOperator(Op)) { - 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, Op, Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0)); - return; - } - } else { - if (Call.getNumArgs() >= 2 && - Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, OrigExpr, Op, Call.getReturnValue(), - Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + handleComparison(C, OrigExpr, Call.getReturnValue(), Arg0, Arg1, Op); + return; + } else if (isRandomIncrOrDecrOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + if (Call.getNumArgs() >= 1 && + Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { + handleRandomIncrOrDecr(C, OrigExpr, Op, getReturnIterator(Call), + InstCall->getCXXThisVal(), Call.getArgSVal(0)); + return; } - } else if (isIncrementOperator(Op)) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); + } else { + if (Call.getNumArgs() >= 2 && + Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + handleRandomIncrOrDecr(C, OrigExpr, Op, getReturnIterator(Call), Arg0, + Call.getArgSVal(1)); return; } - - handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), + } + } else if (isIncrementOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleIncrement(C, getReturnIterator(Call), InstCall->getCXXThisVal(), Call.getNumArgs()); return; - } else if (isDecrementOperator(Op)) { - 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()); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + handleIncrement(C, getReturnIterator(Call), Arg0, Call.getNumArgs()); + return; + } else if (isDecrementOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleDecrement(C, getReturnIterator(Call), InstCall->getCXXThisVal(), + Call.getNumArgs()); return; } + + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + handleDecrement(C, getReturnIterator(Call), Arg0, Call.getNumArgs()); + return; + } } void @@ -363,9 +352,10 @@ const CallEvent &Call, const Expr *OrigExpr, const AdvanceFn *Handler) const { - if (!C.wasInlined) { - (this->**Handler)(C, OrigExpr, Call.getReturnValue(), - Call.getArgSVal(0), Call.getArgSVal(1)); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + if (!C.wasInlined) { + (this->**Handler)(C, OrigExpr, getReturnIterator(Call), Arg0, + Call.getArgSVal(1)); return; } @@ -374,29 +364,31 @@ const auto *IdInfo = cast(Call.getDecl())->getIdentifier(); if (IdInfo) { if (IdInfo->getName() == "advance") { - if (noChangeInAdvance(C, Call.getArgSVal(0), OrigExpr)) { - (this->**Handler)(C, OrigExpr, Call.getReturnValue(), - Call.getArgSVal(0), Call.getArgSVal(1)); + if (noChangeInAdvance(C, Arg0, OrigExpr)) { + (this->**Handler)(C, OrigExpr, getReturnIterator(Call), Arg0, + Call.getArgSVal(1)); } } } } void IteratorModeling::handleComparison(CheckerContext &C, const Expr *CE, - SVal RetVal, const SVal &LVal, - const SVal &RVal, - OverloadedOperatorKind Op) const { + SVal RetVal, SVal LVal, 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(); + auto State = C.getState(); const auto *LPos = getIteratorPosition(State, LVal); const auto *RPos = getIteratorPosition(State, RVal); const MemRegion *Cont = nullptr; + llvm::errs()<<"Comparison\n LVal: "<getContainer(); } else if (RPos) { + llvm::errs()<<" RPos: "<getContainer(); } if (!Cont) @@ -437,7 +429,7 @@ void IteratorModeling::processComparison(CheckerContext &C, ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, const SVal &RetVal, + SymbolRef Sym2, SVal RetVal, OverloadedOperatorKind Op) const { if (const auto TruthVal = RetVal.getAs()) { if ((State = relateSymbols(State, Sym1, Sym2, @@ -465,8 +457,8 @@ } } -void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { +void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal, + SVal Iter, bool Postfix) const { // Increment the symbolic expressions which represents the position of the // iterator auto State = C.getState(); @@ -491,8 +483,8 @@ C.addTransition(State); } -void IteratorModeling::handleDecrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { +void IteratorModeling::handleDecrement(CheckerContext &C, SVal RetVal, + SVal Iter, bool Postfix) const { // Decrement the symbolic expressions which represents the position of the // iterator auto State = C.getState(); @@ -520,30 +512,30 @@ void IteratorModeling::handleRandomIncrOrDecr(CheckerContext &C, const Expr *CE, OverloadedOperatorKind Op, - const SVal &RetVal, - const SVal &LHS, - const SVal &RHS) const { + SVal RetVal, SVal Iter, + SVal Amount) const { // Increment or decrement the symbolic expressions which represents the // position of the iterator auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, LHS); + const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) return; - const auto *value = &RHS; - SVal val; - if (auto loc = RHS.getAs()) { - val = State->getRawSVal(*loc); - value = &val; + const auto *AmountVal = &Amount; + SVal AmountV; + if (auto L = Amount.getAs()) { + AmountV = State->getRawSVal(*L); + AmountVal = &AmountV; } - auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; + SVal TgtVal = + (Op == OO_PlusEqual || Op == OO_MinusEqual) ? Iter : RetVal; auto NewState = - advancePosition(State, LHS, Op, *value); + advancePosition(State, Iter, Op, *AmountVal); if (NewState) { - const auto *NewPos = getIteratorPosition(NewState, LHS); + const auto *NewPos = getIteratorPosition(NewState, Iter); assert(NewPos && "Iterator should have position after successful advancement"); @@ -561,17 +553,19 @@ } void IteratorModeling::handlePrev(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Iter, SVal Amount) const { + SVal RetVal, SVal Iter, + SVal Amount) const { handleRandomIncrOrDecr(C, CE, OO_Minus, RetVal, Iter, Amount); } void IteratorModeling::handleNext(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Iter, SVal Amount) const { + SVal RetVal, SVal Iter, + SVal Amount) const { handleRandomIncrOrDecr(C, CE, OO_Plus, RetVal, Iter, Amount); } void IteratorModeling::assignToContainer(CheckerContext &C, const Expr *CE, - const SVal &RetVal, + SVal RetVal, const MemRegion *Cont) const { Cont = Cont->getMostDerivedObjectRegion(); @@ -622,6 +616,7 @@ Pos.getContainer()->dumpToStream(Out); Out<<" ; Offset == "; Pos.getOffset()->dumpToStream(Out); + Out<<"\n"; } for (const auto &Reg : RegionMap) { @@ -632,6 +627,7 @@ Pos.getContainer()->dumpToStream(Out); Out<<" ; Offset == "; Pos.getOffset()->dumpToStream(Out); + Out<<"\n"; } } } @@ -642,16 +638,14 @@ return OK == OO_EqualEqual || OK == OO_ExclaimEqual; } -ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) { +ProgramStateRef removeIteratorPosition(ProgramStateRef State, 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; + return State; } ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, @@ -686,18 +680,6 @@ return NewState; } -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; -} - const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) { while (Node) { ProgramPoint PP = Node->getLocation(); Index: clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp @@ -76,24 +76,25 @@ if (!Func) return; + SVal Arg0; + if (Call.getNumArgs() >= 1) + Arg0 = getIteratorArg(Call, 0, C.blockCount()); + if (Func->isOverloadedOperator()) { + llvm::errs()<<"Overloaded operator\n"; if (isIncrementOperator(Func->getOverloadedOperator())) { // Check for out-of-range incrementions if (const auto *InstCall = dyn_cast(&Call)) { verifyIncrement(C, InstCall->getCXXThisVal()); } else { - if (Call.getNumArgs() >= 1) { - verifyIncrement(C, Call.getArgSVal(0)); - } + verifyIncrement(C, Arg0); } } else if (isDecrementOperator(Func->getOverloadedOperator())) { // Check for out-of-range decrementions if (const auto *InstCall = dyn_cast(&Call)) { verifyDecrement(C, InstCall->getCXXThisVal()); } else { - if (Call.getNumArgs() >= 1) { - verifyDecrement(C, Call.getArgSVal(0)); - } + verifyDecrement(C, Arg0); } } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { if (const auto *InstCall = dyn_cast(&Call)) { @@ -108,7 +109,7 @@ if (Call.getNumArgs() >= 2 && Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), - Call.getArgSVal(0), Call.getArgSVal(1)); + Arg0, Call.getArgSVal(1)); } } } else if (isDereferenceOperator(Func->getOverloadedOperator())) { @@ -116,18 +117,20 @@ if (const auto *InstCall = dyn_cast(&Call)) { verifyDereference(C, InstCall->getCXXThisVal()); } else { - verifyDereference(C, Call.getArgSVal(0)); + verifyDereference(C, Arg0); } } } else { const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call); if (Verifier) { + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + if (Call.getNumArgs() > 1) { - (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1)); + (this->**Verifier)(C, Arg0, Call.getArgSVal(1)); } else { auto &BVF = C.getSValBuilder().getBasicValueFactory(); (this->**Verifier)( - C, Call.getArgSVal(0), + C, Arg0, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); } } Index: clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp +++ clang/lib/StaticAnalyzer/Checkers/MismatchedIteratorChecker.cpp @@ -32,16 +32,12 @@ std::unique_ptr MismatchedBugType; - void verifyMatch(CheckerContext &C, const SVal &Iter, - const MemRegion *Cont) const; - void verifyMatch(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; - void reportBug(const StringRef &Message, const SVal &Val1, - const SVal &Val2, CheckerContext &C, - ExplodedNode *ErrNode) const; - void reportBug(const StringRef &Message, const SVal &Val, - const MemRegion *Reg, CheckerContext &C, - ExplodedNode *ErrNode) const; + void verifyMatch(CheckerContext &C, SVal Iter, const MemRegion *Cont) const; + void verifyMatch(CheckerContext &C, SVal Iter1, SVal Iter2) const; + void reportBug(const StringRef &Message, SVal Val1, SVal Val2, + CheckerContext &C, ExplodedNode *ErrNode) const; + void reportBug(const StringRef &Message, SVal Val, const MemRegion *Reg, + CheckerContext &C, ExplodedNode *ErrNode) const; public: MismatchedIteratorChecker(); @@ -65,51 +61,55 @@ if (!Func) return; + // If the call has no arguments, there is nothing to check here + if (Call.getNumArgs() < 1) + return; + if (Func->isOverloadedOperator() && isComparisonOperator(Func->getOverloadedOperator())) { // Check for comparisons of iterators of different containers + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); if (const auto *InstCall = dyn_cast(&Call)) { - if (Call.getNumArgs() < 1) - return; - if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) || !isIteratorType(Call.getArgExpr(0)->getType())) return; - verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); + verifyMatch(C, InstCall->getCXXThisVal(), Arg0); } else { if (Call.getNumArgs() < 2) return; + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); if (!isIteratorType(Call.getArgExpr(0)->getType()) || !isIteratorType(Call.getArgExpr(1)->getType())) return; - verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); + verifyMatch(C, Arg0, Arg1); } } else if (const auto *InstCall = dyn_cast(&Call)) { const auto *ContReg = InstCall->getCXXThisVal().getAsRegion(); if (!ContReg) return; + + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); // Check for erase, insert and emplace using iterator of another container if (isEraseCall(Func) || isEraseAfterCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); + verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion()); if (Call.getNumArgs() == 2) { - verifyMatch(C, Call.getArgSVal(1), - InstCall->getCXXThisVal().getAsRegion()); + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + verifyMatch(C, Arg1, InstCall->getCXXThisVal().getAsRegion()); } } else if (isInsertCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); + verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion()); if (Call.getNumArgs() == 3 && isIteratorType(Call.getArgExpr(1)->getType()) && isIteratorType(Call.getArgExpr(2)->getType())) { - verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2)); + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + SVal Arg2 = getIteratorArg(Call, 2, C.blockCount()); + verifyMatch(C, Arg1, Arg2); } } else if (isEmplaceCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); + verifyMatch(C, Arg0, InstCall->getCXXThisVal().getAsRegion()); } } else if (isa(&Call)) { // Check match of first-last iterator pair in a constructor of a container @@ -128,7 +128,9 @@ !isIteratorType(Call.getArgExpr(1)->getType())) return; - verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + verifyMatch(C, Arg0, Arg1); } else { // The main purpose of iterators is to abstract away from different // containers and provide a (maybe limited) uniform access to them. @@ -166,7 +168,7 @@ if (!isIteratorType(TAType)) continue; - SVal LHS = UndefinedVal(); + Optional LHS = None; // For every template parameter which is an iterator type in the // instantiation look for all functions' parameters' type by it and @@ -178,17 +180,20 @@ if (!ParamType || ParamType->getReplacedParameter()->getDecl() != TPDecl) continue; - if (LHS.isUndef()) { - LHS = Call.getArgSVal(J); + + SVal ArgJ = getIteratorArg(Call, J, C.blockCount()); + + if (!LHS.hasValue()) { + LHS = ArgJ; } else { - verifyMatch(C, LHS, Call.getArgSVal(J)); + verifyMatch(C, *LHS, ArgJ); } } } } } -void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter, +void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter, const MemRegion *Cont) const { // Verify match between a container and the container of an iterator Cont = Cont->getMostDerivedObjectRegion(); @@ -219,14 +224,13 @@ if (!N) { return; } - reportBug("Container accessed using foreign iterator argument.", - Iter, Cont, C, N); + reportBug("Container accessed using foreign iterator argument.", Iter, Cont, + C, N); } } -void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, - const SVal &Iter1, - const SVal &Iter2) const { +void MismatchedIteratorChecker::verifyMatch(CheckerContext &C, SVal Iter1, + SVal Iter2) const { // Verify match between the containers of two iterators auto State = C.getState(); const auto *Pos1 = getIteratorPosition(State, Iter1); @@ -263,10 +267,8 @@ } } -void MismatchedIteratorChecker::reportBug(const StringRef &Message, - const SVal &Val1, - const SVal &Val2, - CheckerContext &C, +void MismatchedIteratorChecker::reportBug(const StringRef &Message, SVal Val1, + SVal Val2, CheckerContext &C, ExplodedNode *ErrNode) const { auto R = std::make_unique(*MismatchedBugType, Message, ErrNode); @@ -275,8 +277,8 @@ C.emitReport(std::move(R)); } -void MismatchedIteratorChecker::reportBug(const StringRef &Message, - const SVal &Val, const MemRegion *Reg, +void MismatchedIteratorChecker::reportBug(const StringRef &Message, SVal Val, + const MemRegion *Reg, CheckerContext &C, ExplodedNode *ErrNode) const { auto R = std::make_unique(*MismatchedBugType, Message, Index: clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/STLAlgorithmModeling.cpp @@ -24,12 +24,12 @@ namespace { class STLAlgorithmModeling : public Checker { - bool evalFind(CheckerContext &C, const CallExpr *CE) const; + void evalFind(CheckerContext &C, const CallExpr *CE, SVal Begin, + SVal End) const; - void Find(CheckerContext &C, const CallExpr *CE, unsigned paramNum) const; - - using FnCheck = bool (STLAlgorithmModeling::*)(CheckerContext &, - const CallExpr *) const; + using FnCheck = void (STLAlgorithmModeling::*)(CheckerContext &, + const CallExpr *, SVal Begin, + SVal End) const; const CallDescriptionMap Callbacks = { {{{"std", "find"}, 3}, &STLAlgorithmModeling::evalFind}, @@ -67,51 +67,53 @@ bool STLAlgorithmModeling::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; - - return (this->**Handler)(C, CE); -} - -bool STLAlgorithmModeling::evalFind(CheckerContext &C, - const CallExpr *CE) const { // std::find()-like functions either take their primary range in the first // two parameters, or if the first parameter is "execution policy" then in // the second and third. This means that the second parameter must always be // an iterator. - if (!isIteratorType(CE->getArg(1)->getType())) + if (Call.getNumArgs() < 2 || !isIteratorType(Call.getArgExpr(1)->getType())) return false; + unsigned ArgNum = 999; + // If no "execution policy" parameter is used then the first argument is the // beginning of the range. - if (isIteratorType(CE->getArg(0)->getType())) { - Find(C, CE, 0); - return true; + if (isIteratorType(Call.getArgExpr(0)->getType())) { + ArgNum = 0; } // If "execution policy" parameter is used then the second argument is the // beginning of the range. - if (isIteratorType(CE->getArg(2)->getType())) { - Find(C, CE, 1); - return true; + if (ArgNum > 0 && + Call.getNumArgs() > 2 && isIteratorType(Call.getArgExpr(2)->getType())) { + ArgNum = 1; } - return false; + if (ArgNum == 999) + return false; + + SVal ArgB = getIteratorArg(Call, ArgNum, C.blockCount()); + SVal ArgE = getIteratorArg(Call, ArgNum + 1, C.blockCount()); + + 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)(C, CE, ArgB, ArgE); + return true; } -void STLAlgorithmModeling::Find(CheckerContext &C, const CallExpr *CE, - unsigned paramNum) const { +void STLAlgorithmModeling::evalFind(CheckerContext &C, const CallExpr *CE, + SVal Begin, SVal End) const { auto State = C.getState(); auto &SVB = C.getSValBuilder(); const auto *LCtx = C.getLocationContext(); SVal RetVal = SVB.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); - SVal Param = State->getSVal(CE->getArg(paramNum), LCtx); auto StateFound = State->BindExpr(CE, LCtx, RetVal); @@ -119,7 +121,7 @@ // assume that in case of successful search the position of the found element // is not ahead of it. // FIXME: Reverse iterators - const auto *Pos = getIteratorPosition(State, Param); + const auto *Pos = getIteratorPosition(State, Begin); if (Pos) { StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(), CE, LCtx, C.blockCount()); @@ -135,13 +137,11 @@ StateFound = StateFound->assume(GreaterOrEqual.castAs(), true); } - Param = State->getSVal(CE->getArg(paramNum + 1), LCtx); - // If we have an iterator position for the range-end argument then we can // assume that in case of successful search the position of the found element // is ahead of it. // FIXME: Reverse iterators - Pos = getIteratorPosition(State, Param); + Pos = getIteratorPosition(State, End); if (Pos) { StateFound = createIteratorPosition(StateFound, RetVal, Pos->getContainer(), CE, LCtx, C.blockCount()); @@ -160,7 +160,7 @@ C.addTransition(StateFound); if (AggressiveStdFindModeling) { - auto StateNotFound = State->BindExpr(CE, LCtx, Param); + auto StateNotFound = State->BindExpr(CE, LCtx, End); C.addTransition(StateNotFound); } } Index: clang/test/Analysis/iterator-modeling.cpp =================================================================== --- clang/test/Analysis/iterator-modeling.cpp +++ clang/test/Analysis/iterator-modeling.cpp @@ -1862,7 +1862,7 @@ void clang_analyzer_printState(); void print_state(std::vector &V) { - const auto i0 = V.cbegin(); + auto i0 = V.cbegin(); clang_analyzer_printState(); // CHECK: "checker_messages": [ @@ -1871,12 +1871,15 @@ // CHECK-NEXT: "i0 : Valid ; Container == SymRegion{reg_$[[#]] & V>} ; Offset == conj_$[[#]]{long, LC[[#]], S[[#]], #[[#]]}" // CHECK-NEXT: ]} - const auto i1 = V.cend(); + ++i0; + auto i1 = V.cend(); clang_analyzer_printState(); - + // CHECK: "checker_messages": [ // 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: ]} + + --i1; }