Index: clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp @@ -31,28 +31,36 @@ 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 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 &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 &Cont, - const SVal &Iter) const; - void handleEraseAfter(CheckerContext &C, const SVal &Cont, const SVal &Iter1, - const SVal &Iter2) const; + void handleBegin(CheckerContext &C, const Expr *CE, SVal RetVal, + SVal Cont) const; + void handleEnd(CheckerContext &C, const Expr *CE, SVal RetVal, + SVal Cont) const; + void handleAssignment(CheckerContext &C, const Expr *CE, SVal Cont, + SVal OldCont = UndefinedVal()) const; + void handleEmpty(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handleAssign(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handleClear(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handlePushBack(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handlePopBack(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handlePushFront(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handlePopFront(CheckerContext &C, const Expr *CE, SVal Cont, + SVal RetVal) const; + void handleInsert(CheckerContext &C, const Expr *CE, SVal Cont, SVal Iter, + SVal RetVal) const; + void handleErase(CheckerContext &C, const Expr *CE, SVal Cont, SVal Iter, + SVal RetVal) const; + void handleErase(CheckerContext &C, const Expr *CE, SVal Cont, SVal Iter1, + SVal Iter2, SVal RetVal) const; + void handleEraseAfter(CheckerContext &C, const Expr *CE, SVal Cont, SVal Iter, + SVal RetVal) const; + void handleEraseAfter(CheckerContext &C, const Expr *CE, SVal Cont, + SVal Iter1, SVal Iter2, SVal RetVal) const; void printState(raw_ostream &Out, ProgramStateRef State, const char *NL, const char *Sep) const override; @@ -63,17 +71,21 @@ 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::*NoItParamFn)(CheckerContext &, const Expr *, + SVal, SVal) const; typedef void (ContainerModeling::*OneItParamFn)(CheckerContext &, - const SVal &, - const SVal &) const; + const Expr *, SVal, SVal, + SVal) const; typedef void (ContainerModeling::*TwoItParamFn)(CheckerContext &, - const SVal &, - const SVal &, - const SVal &) const; + const Expr *, SVal, SVal, + SVal, SVal) const; CallDescriptionMap NoIterParamFunctions = { + // Capacity + {{0, "empty", 0}, + &ContainerModeling::handleEmpty}, + + // Modifiers {{0, "clear", 0}, &ContainerModeling::handleClear}, {{0, "assign", 2}, @@ -172,39 +184,42 @@ // Overloaded 'operator=' must be a non-static member function. const auto *InstCall = cast(&Call); if (cast(Func)->isMoveAssignmentOperator()) { - handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), + handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal(), Call.getArgSVal(0)); return; } - handleAssignment(C, InstCall->getCXXThisVal()); + handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal()); return; } } else { + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; + if (const auto *InstCall = dyn_cast(&Call)) { const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); if (Handler0) { - (this->**Handler0)(C, InstCall->getCXXThisVal()); + (this->**Handler0)(C, OrigExpr, InstCall->getCXXThisVal(), + Call.getReturnValue()); return; } const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); if (Handler1) { - (this->**Handler1)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); + (this->**Handler1)(C, OrigExpr, InstCall->getCXXThisVal(), + Call.getArgSVal(0), Call.getReturnValue()); return; } const TwoItParamFn *Handler2 = TwoIterParamFunctions.lookup(Call); if (Handler2) { - (this->**Handler2)(C, InstCall->getCXXThisVal(), Call.getArgSVal(0), - Call.getArgSVal(1)); + (this->**Handler2)(C, OrigExpr, InstCall->getCXXThisVal(), + Call.getArgSVal(0), Call.getArgSVal(1), + Call.getReturnValue()); return; } - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - if (isBeginCall(Func)) { handleBegin(C, OrigExpr, Call.getReturnValue(), InstCall->getCXXThisVal()); @@ -259,7 +274,7 @@ } void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { + SVal RetVal, SVal Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -281,7 +296,7 @@ } void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { + SVal RetVal, SVal Cont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -302,9 +317,8 @@ C.addTransition(State); } -void ContainerModeling::handleAssignment(CheckerContext &C, const SVal &Cont, - const Expr *CE, - const SVal &OldCont) const { +void ContainerModeling::handleAssignment(CheckerContext &C, const Expr *CE, + SVal Cont, SVal OldCont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -379,8 +393,60 @@ C.addTransition(State); } -void ContainerModeling::handleAssign(CheckerContext &C, - const SVal &Cont) const { +void ContainerModeling::handleEmpty(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) 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); + } + auto EndSym = getContainerEnd(State, ContReg); + if (!EndSym) { + State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, + C.getLocationContext(), C.blockCount()); + EndSym = getContainerEnd(State, ContReg); + } + + // 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); + } + + if (const auto DefRetVal = RetVal.getAs()) { + ProgramStateRef StateEmpty, StateNonEmpty; + std::tie(StateEmpty, StateNonEmpty) = + assumeComparison(State, BeginSym, EndSym, *DefRetVal, OO_EqualEqual); + + if (!StateEmpty && !StateNonEmpty) { + C.generateSink(State, C.getPredecessor()); + return; + } + + if (StateEmpty) + C.addTransition(StateEmpty); + + if (StateNonEmpty) + C.addTransition(StateNonEmpty); + } +} + +void ContainerModeling::handleAssign(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -393,7 +459,8 @@ C.addTransition(State); } -void ContainerModeling::handleClear(CheckerContext &C, const SVal &Cont) const { +void ContainerModeling::handleClear(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -419,8 +486,8 @@ C.addTransition(State); } -void ContainerModeling::handlePushBack(CheckerContext &C, - const SVal &Cont) const { +void ContainerModeling::handlePushBack(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -457,8 +524,8 @@ C.addTransition(State); } -void ContainerModeling::handlePopBack(CheckerContext &C, - const SVal &Cont) const { +void ContainerModeling::handlePopBack(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -495,8 +562,8 @@ } } -void ContainerModeling::handlePushFront(CheckerContext &C, - const SVal &Cont) const { +void ContainerModeling::handlePushFront(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -528,8 +595,8 @@ } } -void ContainerModeling::handlePopFront(CheckerContext &C, - const SVal &Cont) const { +void ContainerModeling::handlePopFront(CheckerContext &C, const Expr *CE, + SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -562,8 +629,8 @@ } } -void ContainerModeling::handleInsert(CheckerContext &C, const SVal &Cont, - const SVal &Iter) const { +void ContainerModeling::handleInsert(CheckerContext &C, const Expr *CE, + SVal Cont, SVal Iter, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -593,8 +660,8 @@ } } -void ContainerModeling::handleErase(CheckerContext &C, const SVal &Cont, - const SVal &Iter) const { +void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE, + SVal Cont, SVal Iter, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -627,9 +694,9 @@ C.addTransition(State); } -void ContainerModeling::handleErase(CheckerContext &C, const SVal &Cont, - const SVal &Iter1, - const SVal &Iter2) const { +void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE, + SVal Cont, SVal Iter1, SVal Iter2, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -664,8 +731,9 @@ C.addTransition(State); } -void ContainerModeling::handleEraseAfter(CheckerContext &C, const SVal &Cont, - const SVal &Iter) const { +void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE, + SVal Cont, SVal Iter, + SVal RetVal) const { auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) @@ -685,9 +753,9 @@ C.addTransition(State); } -void ContainerModeling::handleEraseAfter(CheckerContext &C, const SVal &Cont, - const SVal &Iter1, - const SVal &Iter2) const { +void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE, + SVal Cont, SVal Iter1, SVal Iter2, + SVal RetVal) const { auto State = C.getState(); const auto *Pos1 = getIteratorPosition(State, Iter1); const auto *Pos2 = getIteratorPosition(State, Iter2); Index: clang/lib/StaticAnalyzer/Checkers/Iterator.h =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.h +++ clang/lib/StaticAnalyzer/Checkers/Iterator.h @@ -169,6 +169,9 @@ const SVal &Distance); ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale); +std::pair +assumeComparison(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, + DefinedSVal RetVal, OverloadedOperatorKind Op); bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, Index: clang/lib/StaticAnalyzer/Checkers/Iterator.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.cpp +++ clang/lib/StaticAnalyzer/Checkers/Iterator.cpp @@ -16,6 +16,9 @@ namespace ento { namespace iterator { +ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, + SymbolRef Sym2, bool Equal); + bool isIteratorType(const QualType &Type) { if (Type->isPointerType()) return true; @@ -266,6 +269,63 @@ return NewState; } +std::pair +assumeComparison(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, + DefinedSVal RetVal, OverloadedOperatorKind Op) { + if (const auto TruthVal = RetVal.getAs()) { + if ((State = relateSymbols(State, Sym1, Sym2, + (Op == OO_EqualEqual) == + (TruthVal->getValue() != 0)))) { + return std::make_pair(State, nullptr); + } + return std::make_pair(nullptr, nullptr); + } + + ProgramStateRef StateTrue = + relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual); + ProgramStateRef StateFalse = + relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual); + + if (StateTrue) + StateTrue = StateTrue->assume(RetVal, true); + if (StateFalse) + StateFalse = StateFalse->assume(RetVal, false); + + return std::make_pair(StateTrue, StateFalse); +} + +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 compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc) { return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); Index: clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/IteratorModeling.cpp @@ -119,8 +119,6 @@ bool isSimpleComparisonOperator(OverloadedOperatorKind OK); ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal); bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg); @@ -360,37 +358,24 @@ State = State->BindExpr(CE, LCtx, RetVal); } - processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op); -} + if (const auto DefRetVal = RetVal.getAs()) { + ProgramStateRef StateEqual, StateNonEqual; + std::tie(StateEqual, StateNonEqual) = + assumeComparison(State, LPos->getOffset(), RPos->getOffset(), *DefRetVal, + 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 { + if (!StateEqual && !StateNonEqual) { C.generateSink(State, C.getPredecessor()); + return; } - return; - } - const auto ConditionVal = RetVal.getAs(); - if (!ConditionVal) - return; + if (StateEqual) + C.addTransition(StateEqual); - 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); + if (StateNonEqual) + C.addTransition(StateNonEqual); } + } void IteratorModeling::handleIncrement(CheckerContext &C, const SVal &RetVal, @@ -540,38 +525,6 @@ return nullptr; } -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 isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg) { for (const auto &Binding : Env) { Index: clang/test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- clang/test/Analysis/Inputs/system-header-simulator-cxx.h +++ clang/test/Analysis/Inputs/system-header-simulator-cxx.h @@ -334,6 +334,8 @@ const T& front() const { return *begin(); } T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } + + bool empty() const; }; template @@ -405,6 +407,8 @@ const T& front() const { return *begin(); } T& back() { return *--end(); } const T& back() const { return *--end(); } + + bool empty() const; }; template @@ -486,6 +490,8 @@ const T& front() const { return *begin(); } T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } + + bool empty() const; }; template @@ -550,6 +556,8 @@ T& front() { return *begin(); } const T& front() const { return *begin(); } + + bool empty() const; }; template Index: clang/test/Analysis/container-modeling.cpp =================================================================== --- clang/test/Analysis/container-modeling.cpp +++ clang/test/Analysis/container-modeling.cpp @@ -16,6 +16,12 @@ void clang_analyzer_eval(bool); void clang_analyzer_warnIfReached(); +extern void __assert_fail (__const char *__assertion, __const char *__file, + unsigned int __line, __const char *__function) + __attribute__ ((__noreturn__)); +#define assert(expr) \ + ((expr) ? (void)(0) : __assert_fail (#expr, __FILE__, __LINE__, __func__)) + void begin(const std::vector &V) { V.begin(); @@ -52,6 +58,37 @@ clang_analyzer_eval(clang_analyzer_container_end(V2) == E2); //expected-warning{{TRUE}} } +//////////////////////////////////////////////////////////////////////////////// +/// +/// C O N T A I N E R C A P A C I T Y +/// +//////////////////////////////////////////////////////////////////////////////// + +/// empty() + +void empty(const std::vector &V) { + for (auto n: V) {} + clang_analyzer_eval(clang_analyzer_container_begin(V) == + clang_analyzer_container_end(V)); + // expected-warning@-2{{TRUE}} expected-warning@-2{{FALSE}} +} + +void non_empty1(const std::vector &V) { + assert(!V.empty()); + for (auto n: V) {} + clang_analyzer_eval(clang_analyzer_container_begin(V) == + clang_analyzer_container_end(V)); + // expected-warning@-2{{FALSE}} +} + +void non_empty2(const std::vector &V) { + for (auto n: V) {} + assert(!V.empty()); + clang_analyzer_eval(clang_analyzer_container_begin(V) == + clang_analyzer_container_end(V)); + // expected-warning@-2{{FALSE}} +} + //////////////////////////////////////////////////////////////////////////////// /// /// C O N T A I N E R M O D I F I E R S Index: clang/test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- clang/test/Analysis/diagnostics/explicit-suppression.cpp +++ clang/test/Analysis/diagnostics/explicit-suppression.cpp @@ -19,6 +19,6 @@ void testCopyNull(C *I, C *E) { std::copy(I, E, (C *)0); #ifndef SUPPRESSED - // expected-warning@../Inputs/system-header-simulator-cxx.h:698 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:706 {{Called C++ object pointer is null}} #endif }