Index: clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp =================================================================== --- clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp +++ clang/lib/StaticAnalyzer/Checkers/ContainerModeling.cpp @@ -32,24 +32,44 @@ class ContainerModeling : public Checker { - 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, SVal Cont, const Expr *CE = nullptr, - SVal OldCont = UndefinedVal()) const; - void handleAssign(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handleClear(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handlePushBack(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handlePopBack(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handlePushFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handlePopFront(CheckerContext &C, SVal Cont, const Expr *ContE) const; - void handleInsert(CheckerContext &C, SVal Cont, SVal Iter) const; - void handleErase(CheckerContext &C, SVal Cont, SVal Iter) const; - void handleErase(CheckerContext &C, SVal Cont, SVal Iter1, SVal Iter2) const; - void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter) const; - void handleEraseAfter(CheckerContext &C, SVal Cont, SVal Iter1, - SVal Iter2) const; + void handleAssignment(CheckerContext &C, const Expr *CE, SVal Cont, + Optional = None) const; + + // Handler functions for different container operations. + // SVal Parameters: + // - Cont: The affected container (*this) + // - RetVal: Return value of the operation + // - Iter (or Iter1 and Iter2): Iterator parameters + + void handleBegin(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handleEnd(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handleEmpty(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handleAssign(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handleClear(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handlePushBack(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handlePopBack(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handlePushFront(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handlePopFront(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal RetVal) const; + void handleInsert(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal Iter, SVal RetVal) const; + void handleErase(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal Iter, SVal RetVal) const; + void handleErase(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const; + void handleEraseAfter(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal Iter, SVal RetVal) const; + void handleEraseAfter(CheckerContext &C, const Expr *CE, const Expr *ContE, + SVal Cont, SVal Iter1, SVal Iter2, SVal RetVal) const; + const NoteTag *getChangeTag(CheckerContext &C, StringRef Text, const MemRegion *ContReg, const Expr *ContE) const; @@ -63,54 +83,50 @@ void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; - using NoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, - const Expr *) const; - using OneItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, - SVal) const; - using TwoItParamFn = void (ContainerModeling::*)(CheckerContext &, SVal, SVal, - 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}, + using ZeroItParamFn = + void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *, + SVal, SVal) const; + using OneItParamFn = + void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *, + SVal, SVal, SVal) const; + using TwoItParamFn = + void (ContainerModeling::*)(CheckerContext &, const Expr *, const Expr *, + SVal, SVal, SVal, SVal) const; + + CallDescriptionMap ZeroIterParamFunctions = { + // Iterators + {{0, "cbegin", 0}, &ContainerModeling::handleBegin}, + {{0, "cend", 0}, &ContainerModeling::handleEnd}, + {{0, "begin", 0}, &ContainerModeling::handleBegin}, + {{0, "end", 0}, &ContainerModeling::handleEnd}, + + // Capacity + {{0, "empty", 0}, &ContainerModeling::handleEmpty}, + + // Modifiers + {{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}, + {{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}, + {{0, "erase", 2}, &ContainerModeling::handleErase}, + {{0, "erase_after", 2}, &ContainerModeling::handleEraseAfter}, }; - }; -bool isBeginCall(const FunctionDecl *Func); -bool isEndCall(const FunctionDecl *Func); bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); bool backModifiable(ProgramStateRef State, const MemRegion *Reg); @@ -169,12 +185,12 @@ // Overloaded 'operator=' must be a non-static member function. const auto *InstCall = cast(&Call); if (cast(Func)->isMoveAssignmentOperator()) { - handleAssignment(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), - Call.getArgSVal(0)); + handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal(), + Call.getArgSVal(0)); return; } - handleAssignment(C, InstCall->getCXXThisVal()); + handleAssignment(C, Call.getOriginExpr(), InstCall->getCXXThisVal()); return; } } else if (const auto *InstCall = dyn_cast(&Call)) { @@ -182,42 +198,31 @@ if (!OrigExpr) return; - if (isBeginCall(Func)) { - handleBegin(C, OrigExpr, getReturnIterator(Call), - InstCall->getCXXThisVal()); - return; - } - - if (isEndCall(Func)) { - handleEnd(C, OrigExpr, getReturnIterator(Call), - InstCall->getCXXThisVal()); - return; - } + SVal RetVal = Call.getReturnValue(); + if (isIteratorType(Call.getResultType())) + RetVal = getReturnIterator(Call); - const NoItParamFn *Handler0 = NoIterParamFunctions.lookup(Call); + const ZeroItParamFn *Handler0 = ZeroIterParamFunctions.lookup(Call); if (Handler0) { - (this->**Handler0)(C, InstCall->getCXXThisVal(), - InstCall->getCXXThisExpr()); + (this->**Handler0)(C, OrigExpr, InstCall->getCXXThisExpr(), + InstCall->getCXXThisVal(), RetVal); return; } - if (Call.getNumArgs() < 1) - return; - - SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); const OneItParamFn *Handler1 = OneIterParamFunctions.lookup(Call); if (Handler1) { - (this->**Handler1)(C, InstCall->getCXXThisVal(), Arg0); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + (this->**Handler1)(C, OrigExpr, InstCall->getCXXThisExpr(), + InstCall->getCXXThisVal(), Arg0, RetVal); return; } - 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); + SVal Arg0 = getIteratorArg(Call, 0, C.blockCount()); + SVal Arg1 = getIteratorArg(Call, 1, C.blockCount()); + (this->**Handler2)(C, OrigExpr, InstCall->getCXXThisExpr(), + InstCall->getCXXThisVal(), Arg0, Arg1, RetVal); return; } } @@ -262,7 +267,8 @@ } void ContainerModeling::handleBegin(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Cont) const { + const Expr *, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -285,7 +291,7 @@ } void ContainerModeling::handleEnd(CheckerContext &C, const Expr *CE, - SVal RetVal, SVal Cont) const { + const Expr *, SVal Cont, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -307,8 +313,9 @@ C.addTransition(State); } -void ContainerModeling::handleAssignment(CheckerContext &C, SVal Cont, - const Expr *CE, SVal OldCont) const { +void ContainerModeling::handleAssignment(CheckerContext &C, const Expr *CE, + SVal Cont, + Optional OldCont) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -325,8 +332,8 @@ // 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 (OldCont.hasValue()) { + const auto *OldContReg = OldCont->getAsRegion(); if (OldContReg) { OldContReg = OldContReg->getMostDerivedObjectRegion(); const auto OldCData = getContainerData(State, OldContReg); @@ -383,8 +390,65 @@ C.addTransition(State); } -void ContainerModeling::handleAssign(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handleEmpty(CheckerContext &C, const Expr *CE, + const Expr *, 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 *LCtx = C.getLocationContext(); + + auto BeginSym = getContainerBegin(State, ContReg); + if (!BeginSym) { + State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, + LCtx, C.blockCount()); + BeginSym = getContainerBegin(State, ContReg); + } + auto EndSym = getContainerEnd(State, ContReg); + if (!EndSym) { + State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, + LCtx, 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(); + 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) { + // The return value of the `empty()` call contradicts the emptyness of + // the container. + C.generateSink(State, C.getPredecessor()); + return; + } + + if (StateEmpty) + C.addTransition(StateEmpty); + + if (StateNonEmpty) + C.addTransition(StateNonEmpty); + } +} + +void ContainerModeling::handleAssign(CheckerContext &C, const Expr *CE, + const Expr *, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -397,8 +461,9 @@ C.addTransition(State); } -void ContainerModeling::handleClear(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handleClear(CheckerContext &C, const Expr *CE, + const Expr *ContE, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -426,8 +491,9 @@ C.addTransition(State, ChangeTag); } -void ContainerModeling::handlePushBack(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handlePushBack(CheckerContext &C, const Expr *CE, + const Expr *ContE, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -466,8 +532,9 @@ } } -void ContainerModeling::handlePopBack(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handlePopBack(CheckerContext &C, const Expr *CE, + const Expr *ContE, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -506,8 +573,9 @@ } } -void ContainerModeling::handlePushFront(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handlePushFront(CheckerContext &C, const Expr *CE, + const Expr *ContE, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -541,8 +609,9 @@ } } -void ContainerModeling::handlePopFront(CheckerContext &C, SVal Cont, - const Expr *ContE) const { +void ContainerModeling::handlePopFront(CheckerContext &C, const Expr *CE, + const Expr *ContE, SVal Cont, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -577,8 +646,9 @@ } } -void ContainerModeling::handleInsert(CheckerContext &C, SVal Cont, - SVal Iter) const { +void ContainerModeling::handleInsert(CheckerContext &C, const Expr *CE, + const Expr *, SVal Cont, SVal Iter, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -608,8 +678,9 @@ } } -void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, - SVal Iter) const { +void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE, + const Expr *, SVal Cont, SVal Iter, + SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -642,8 +713,9 @@ C.addTransition(State); } -void ContainerModeling::handleErase(CheckerContext &C, SVal Cont, SVal Iter1, - SVal Iter2) const { +void ContainerModeling::handleErase(CheckerContext &C, const Expr *CE, + const Expr *, SVal Cont, SVal Iter1, + SVal Iter2, SVal RetVal) const { const auto *ContReg = Cont.getAsRegion(); if (!ContReg) return; @@ -678,8 +750,9 @@ C.addTransition(State); } -void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont, - SVal Iter) const { +void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE, + const Expr *, SVal Cont, SVal Iter, + SVal RetVal) const { auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Iter); if (!Pos) @@ -699,8 +772,9 @@ C.addTransition(State); } -void ContainerModeling::handleEraseAfter(CheckerContext &C, SVal Cont, - SVal Iter1, SVal Iter2) const { +void ContainerModeling::handleEraseAfter(CheckerContext &C, const Expr *CE, + const Expr *, 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); @@ -766,20 +840,6 @@ namespace { -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"); -} - const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, const MemRegion *Reg) { auto TI = getDynamicTypeInfo(State, Reg); Index: clang/lib/StaticAnalyzer/Checkers/Iterator.h =================================================================== --- clang/lib/StaticAnalyzer/Checkers/Iterator.h +++ clang/lib/StaticAnalyzer/Checkers/Iterator.h @@ -179,6 +179,14 @@ const SVal &Distance); ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, long Scale); + +// Returns states with comparison results assumed to `true` and `false`. If +// only one of them is possible then the second value of the pair is `nullptr`. +// If none is possible then both values are `nullptr`. +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 @@ -18,6 +18,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; @@ -26,6 +29,28 @@ return isIterator(CRD); } +static bool hasOperator(const CXXRecordDecl *CRD, OverloadedOperatorKind Op, + unsigned NumParams) { + for (const auto *Method : CRD->methods()) { + if (!Method->isOverloadedOperator()) + continue; + + if (Method->getOverloadedOperator() == Op && + Method->getNumParams() == NumParams) + return true; + } + + for (auto Base : CRD->bases()) { + const auto *BaseCRD = + Base.getType()->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); + + if (BaseCRD && hasOperator(BaseCRD, Op, NumParams)) + return true; + } + + return false; +} + bool isIterator(const CXXRecordDecl *CRD) { if (!CRD) return false; @@ -35,39 +60,27 @@ Name.endswith_lower("it"))) return false; - bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false, - HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false; - for (const auto *Method : CRD->methods()) { - if (const auto *Ctor = dyn_cast(Method)) { - if (Ctor->isCopyConstructor()) { - HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public; - } - continue; - } - if (const auto *Dtor = dyn_cast(Method)) { - HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public; - continue; - } - if (Method->isCopyAssignmentOperator()) { - HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public; - continue; - } - if (!Method->isOverloadedOperator()) - continue; - const auto OPK = Method->getOverloadedOperator(); - if (OPK == OO_PlusPlus) { - HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0); - HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1); - continue; - } - if (OPK == OO_Star) { - HasDerefOp = (Method->getNumParams() == 0); - continue; - } - } + if ((!CRD->hasSimpleCopyConstructor() && + !CRD->hasUserDeclaredCopyConstructor()) || + (!CRD->hasSimpleCopyAssignment() && + !CRD->hasUserDeclaredCopyAssignment()) || + (!CRD->hasSimpleDestructor() && + !CRD->hasUserDeclaredDestructor())) + return false; + + // Operator Prefix ++ + if (!hasOperator(CRD, OO_PlusPlus, 0)) + return false; - return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp && - HasPostIncrOp && HasDerefOp; + // Operator Postfix ++ + if (!hasOperator(CRD, OO_PlusPlus, 1)) + return false; + + // Operator * + if (!hasOperator(CRD, OO_Star, 0)) + return false; + + return true; } bool isComparisonOperator(OverloadedOperatorKind OK) { @@ -294,6 +307,62 @@ return NewState; } +std::pair +assumeComparison(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, + DefinedSVal RetVal, OverloadedOperatorKind Op) { + assert(CXXOperatorCallExpr::isComparisonOp(Op) && + "`Op` must be a comparison operator"); + if (const auto TruthVal = RetVal.getAs()) { + State = relateSymbols(State, Sym1, Sym2, + (Op == OO_EqualEqual) == TruthVal->getValue()); + return std::make_pair(State, 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 @@ -157,8 +157,6 @@ bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool isSimpleComparisonOperator(BinaryOperatorKind OK); ProgramStateRef removeIteratorPosition(ProgramStateRef State, SVal Val); -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal); const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call); } // namespace @@ -493,37 +491,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, 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 (StateNonEqual) + C.addTransition(StateNonEqual); } - if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) { - StateFalse = StateFalse->assume(*ConditionVal, false); - C.addTransition(StateFalse); - } } void IteratorModeling::handleIncrement(CheckerContext &C, SVal RetVal, @@ -777,38 +762,6 @@ return State; } -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; -} - const ExplodedNode *findCallEnter(const ExplodedNode *Node, const Expr *Call) { while (Node) { ProgramPoint PP = Node->getLocation(); 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 @@ -344,6 +344,8 @@ const T& front() const { return *begin(); } T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } + + bool empty() const; }; template @@ -415,6 +417,8 @@ const T& front() const { return *begin(); } T& back() { return *--end(); } const T& back() const { return *--end(); } + + bool empty() const; }; template @@ -496,6 +500,8 @@ const T& front() const { return *begin(); } T& back() { return *(end() - 1); } const T& back() const { return *(end() - 1); } + + bool empty() const; }; template @@ -560,6 +566,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(); @@ -56,6 +62,40 @@ // expected-note@-1{{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}} + // expected-note@-3 {{TRUE}} expected-note@-3 {{FALSE}} +} + +void non_empty1(const std::vector &V) { + assert(!V.empty()); // expected-note{{'?' condition is true}} + for (auto n: V) {} + clang_analyzer_eval(clang_analyzer_container_begin(V) == + clang_analyzer_container_end(V)); + // expected-warning@-2{{FALSE}} + // expected-note@-3 {{FALSE}} +} + +void non_empty2(const std::vector &V) { + for (auto n: V) {} + assert(!V.empty()); // expected-note{{'?' condition is true}} + clang_analyzer_eval(clang_analyzer_container_begin(V) == + clang_analyzer_container_end(V)); + // expected-warning@-2{{FALSE}} + // expected-note@-3 {{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:709 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:717 {{Called C++ object pointer is null}} #endif } Index: clang/test/Analysis/smart-ptr-text-output.cpp =================================================================== --- clang/test/Analysis/smart-ptr-text-output.cpp +++ clang/test/Analysis/smart-ptr-text-output.cpp @@ -80,7 +80,7 @@ void derefOnStdSwappedNullPtr() { std::unique_ptr P; // expected-note {{Default constructed smart pointer 'P' is null}} std::unique_ptr PNull; // expected-note {{Default constructed smart pointer 'PNull' is null}} - std::swap(P, PNull); // expected-note@Inputs/system-header-simulator-cxx.h:979 {{Swapped null smart pointer 'PNull' with smart pointer 'P'}} + std::swap(P, PNull); // expected-note@Inputs/system-header-simulator-cxx.h:987 {{Swapped null smart pointer 'PNull' with smart pointer 'P'}} // expected-note@-1 {{Calling 'swap'}} // expected-note@-2 {{Returning from 'swap'}} P->foo(); // expected-warning {{Dereference of null smart pointer 'P' [alpha.cplusplus.SmartPtr]}}