Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -46,19 +46,25 @@ // 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 past-end iterator for -// all containers whenever their `.end()` is called. Since the Constraint -// Manager cannot handle SVals we need to take over its role. We post-check -// equality and non-equality comparisons and propagate the position of the -// iterator to the other side of the comparison if it is past-end and we are in -// the 'equal' branch (true-branch for `==` and false-branch for `!=`). +// 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 +// 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 "ClangSACheckers.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" @@ -80,7 +86,7 @@ const MemRegion *Cont; // Abstract offset - SymbolRef Offset; + const SymbolRef Offset; IteratorPosition(const MemRegion *C, SymbolRef Of) : Cont(C), Offset(Of) {} @@ -113,31 +119,39 @@ typedef llvm::PointerUnion RegionOrSymbol; -// Structure to record the symbolic end position of a container +// Structure to record the symbolic begin and end position of a container struct ContainerData { private: - SymbolRef End; + const SymbolRef Begin, End; - ContainerData(SymbolRef E) : End(E) {} + ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {} public: + static ContainerData fromBegin(SymbolRef B) { + return ContainerData(B, nullptr); + } + static ContainerData fromEnd(SymbolRef E) { - return ContainerData(E); + return ContainerData(nullptr, E); } + SymbolRef getBegin() const { return Begin; } SymbolRef getEnd() const { return End; } - ContainerData newEnd(SymbolRef E) const { return ContainerData(E); } + ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); } + + ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); } bool operator==(const ContainerData &X) const { - return End == X.End; + return Begin == X.Begin && End == X.End; } bool operator!=(const ContainerData &X) const { - return End != X.End; + return Begin != X.Begin || End != X.End; } void Profile(llvm::FoldingSetNodeID &ID) const { + ID.Add(Begin); ID.Add(End); } }; @@ -167,8 +181,9 @@ class IteratorChecker : public Checker, check::PostStmt, - check::DeadSymbols, + check::LiveSymbols, check::DeadSymbols, eval::Assume> { std::unique_ptr OutOfRangeBugType; @@ -176,10 +191,22 @@ void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; void verifyDereference(CheckerContext &C, const SVal &Val) 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, 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 verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, + const SVal &RetVal, const SVal &LHS, + const SVal &RHS) const; void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const; @@ -196,8 +223,10 @@ void checkPreCall(const CallEvent &Call, CheckerContext &C) const; void checkPostCall(const CallEvent &Call, CheckerContext &C) const; + void checkPreStmt(const CXXOperatorCallExpr *COCE, 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; ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond, bool Assumption) const; @@ -217,9 +246,13 @@ bool isIteratorType(const QualType &Type); bool isIterator(const CXXRecordDecl *CRD); +bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool isDereferenceOperator(OverloadedOperatorKind OK); +bool isIncrementOperator(OverloadedOperatorKind OK); +bool isDecrementOperator(OverloadedOperatorKind OK); +bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); BinaryOperator::Opcode getOpcode(const SymExpr *SE); const RegionOrSymbol getRegionOrSymbol(const SVal &Val); const ProgramStateRef processComparison(ProgramStateRef State, @@ -230,7 +263,11 @@ const SVal &RVal, bool Eq); const IteratorComparison *loadComparison(ProgramStateRef State, const SymExpr *Condition); +SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); +ProgramStateRef createContainerBegin(ProgramStateRef State, + const MemRegion *Cont, + const SymbolRef Sym); ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym); const IteratorPosition *getIteratorPosition(ProgramStateRef State, @@ -255,6 +292,7 @@ ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData); bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isZero(ProgramStateRef State, const NonLoc &Val); } // namespace IteratorChecker::IteratorChecker() { @@ -272,6 +310,22 @@ if (Func->isOverloadedOperator()) { if (ChecksEnabled[CK_IteratorRangeChecker] && + isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + // Check for out-of-range incrementions and decrementions + if (Call.getNumArgs() >= 1) { + verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), + InstCall->getCXXThisVal(), Call.getArgSVal(0)); + } + } else { + if (Call.getNumArgs() >= 2) { + verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), Call.getArgSVal(0), + Call.getArgSVal(1)); + } + } + } else if (ChecksEnabled[CK_IteratorRangeChecker] && isDereferenceOperator(Func->getOverloadedOperator())) { // Check for dereference of out-of-range iterators if (const auto *InstCall = dyn_cast(&Call)) { @@ -300,6 +354,36 @@ handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0), Call.getArgSVal(1), Op); } + } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + if (Call.getNumArgs() >= 1) { + handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), + InstCall->getCXXThisVal(), Call.getArgSVal(0)); + } + } else { + if (Call.getNumArgs() >= 2) { + handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), Call.getArgSVal(0), + Call.getArgSVal(1)); + } + } + } else if (isIncrementOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + } else { + handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + } + } else if (isDecrementOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + } else { + handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + } } } else { const auto *OrigExpr = Call.getOriginExpr(); @@ -315,6 +399,11 @@ return; 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()); @@ -351,6 +440,27 @@ } } +void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE, + CheckerContext &C) const { + const auto *ThisExpr = COCE->getArg(0); + + auto State = C.getState(); + const auto *LCtx = C.getLocationContext(); + + const auto CurrentThis = State->getSVal(ThisExpr, LCtx); + if (const auto *Reg = CurrentThis.getAsRegion()) { + if (!Reg->getAs()) + return; + const auto OldState = C.getPredecessor()->getFirstPred()->getState(); + const auto OldThis = OldState->getSVal(ThisExpr, LCtx); + const auto *Pos = getIteratorPosition(OldState, OldThis); + if (!Pos) + return; + State = setIteratorPosition(State, CurrentThis, *Pos); + C.addTransition(State); + } +} + void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, CheckerContext &C) const { /* Transfer iterator state to temporary objects */ @@ -364,6 +474,34 @@ C.addTransition(State); } +void IteratorChecker::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 Pos = Reg.second; + SR.markLive(Pos.getOffset()); + } + + auto SymbolMap = State->get(); + for (const auto Sym : SymbolMap) { + const auto Pos = Sym.second; + SR.markLive(Pos.getOffset()); + } + + auto ContMap = State->get(); + for (const auto Cont : ContMap) { + const auto CData = Cont.second; + if (CData.getBegin()) { + SR.markLive(CData.getBegin()); + } + if (CData.getEnd()) { + SR.markLive(CData.getEnd()); + } + } +} + void IteratorChecker::checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const { // Cleanup @@ -471,13 +609,208 @@ static CheckerProgramPointTag Tag("IteratorRangeChecker", "IteratorOutOfRange"); auto *N = C.generateNonFatalErrorNode(State, &Tag); - if (!N) { + if (!N) return; - } reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N); } } +void IteratorChecker::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(); + const auto *Pos = getIteratorPosition(State, Iter); + if (Pos) { + auto &SymMgr = C.getSymbolManager(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto OldOffset = Pos->getOffset(); + auto NewOffset = + SVB.evalBinOp(State, BO_Add, + nonloc::SymbolVal(OldOffset), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(OldOffset)).getAsSymbol(); + auto NewPos = Pos->setTo(NewOffset); + State = setIteratorPosition(State, Iter, NewPos); + State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); + C.addTransition(State); + } +} + +void IteratorChecker::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(); + const auto *Pos = getIteratorPosition(State, Iter); + if (Pos) { + auto &SymMgr = C.getSymbolManager(); + auto &BVF = SymMgr.getBasicVals(); + auto &SVB = C.getSValBuilder(); + const auto OldOffset = Pos->getOffset(); + auto NewOffset = + SVB.evalBinOp(State, BO_Sub, + nonloc::SymbolVal(OldOffset), + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), + SymMgr.getType(OldOffset)).getAsSymbol(); + auto NewPos = Pos->setTo(NewOffset); + State = setIteratorPosition(State, Iter, NewPos); + State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); + C.addTransition(State); + } +} + +// 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? +static ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym) { + 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() >> 3; // Divide by 4. + 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; +} + +void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C, + 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 &SymMgr = C.getSymbolManager(); + auto &SVB = C.getSValBuilder(); + auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; + const auto OldOffset = Pos->getOffset(); + SymbolRef NewOffset; + if (const auto intValue = value->getAs()) { + // For concrete integers we can calculate the new position + NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset), + *intValue, + SymMgr.getType(OldOffset)).getAsSymbol(); + } else { + // For other symbols create a new symbol to keep expressions simple + const auto &LCtx = C.getLocationContext(); + NewOffset = SymMgr.conjureSymbol(nullptr, LCtx, SymMgr.getType(OldOffset), + C.blockCount()); + State = assumeNoOverflow(State, NewOffset); + } + auto NewPos = Pos->setTo(NewOffset); + auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; + State = setIteratorPosition(State, TgtVal, NewPos); + C.addTransition(State); +} + +void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C, + OverloadedOperatorKind Op, + const SVal &RetVal, + const SVal &LHS, + const SVal &RHS) const { + auto State = C.getState(); + + // If the iterator is initially inside its range, then the operation is valid + const auto *Pos = getIteratorPosition(State, LHS); + if (!Pos || !isOutOfRange(State, *Pos)) + return; + + auto value = RHS; + if (auto loc = RHS.getAs()) { + value = State->getRawSVal(*loc); + } + + // Incremention or decremention by 0 is never bug + if (isZero(State, value.castAs())) + return; + + auto &SymMgr = C.getSymbolManager(); + auto &SVB = C.getSValBuilder(); + auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; + const auto OldOffset = Pos->getOffset(); + const auto intValue = value.getAs(); + if (!intValue) + return; + + auto NewOffset = SVB.evalBinOp(State, BinOp, nonloc::SymbolVal(OldOffset), + *intValue, + SymMgr.getType(OldOffset)).getAsSymbol(); + auto NewPos = Pos->setTo(NewOffset); + + // If out of range, the only valid operation is to step into the range + if (isOutOfRange(State, NewPos)) { + auto *N = C.generateNonFatalErrorNode(State); + if (!N) + return; + reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N); + } +} + +void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE, + const SVal &RetVal, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // 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) { + auto &SymMgr = C.getSymbolManager(); + BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + State = assumeNoOverflow(State, BeginSym); + State = createContainerBegin(State, ContReg, BeginSym); + } + State = setIteratorPosition(State, RetVal, + IteratorPosition::getPosition(ContReg, BeginSym)); + C.addTransition(State); +} + void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); @@ -496,6 +829,7 @@ auto &SymMgr = C.getSymbolManager(); EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(), C.getASTContext().LongTy, C.blockCount()); + State = assumeNoOverflow(State, EndSym); State = createContainerEnd(State, ContReg, EndSym); } State = setIteratorPosition(State, RetVal, @@ -514,6 +848,7 @@ auto &SymMgr = C.getSymbolManager(); auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), C.getASTContext().LongTy, C.blockCount()); + State = assumeNoOverflow(State, Sym); State = setIteratorPosition(State, RetVal, IteratorPosition::getPosition(Cont, Sym)); C.addTransition(State); @@ -529,9 +864,12 @@ namespace { +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); +bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, + BinaryOperator::Opcode Opc); bool isIteratorType(const QualType &Type) { if (Type->isPointerType()) @@ -585,6 +923,13 @@ HasPostIncrOp && HasDerefOp; } +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) @@ -601,6 +946,19 @@ OK == OO_Subscript; } +bool isIncrementOperator(OverloadedOperatorKind OK) { + return OK == OO_PlusPlus; +} + +bool isDecrementOperator(OverloadedOperatorKind OK) { + return OK == OO_MinusMinus; +} + +bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { + return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || + OK == OO_MinusEqual; +} + BinaryOperator::Opcode getOpcode(const SymExpr *SE) { if (const auto *BSE = dyn_cast(SE)) { return BSE->getOpcode(); @@ -660,6 +1018,14 @@ return State->get(Condition); } +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) @@ -668,6 +1034,22 @@ return CDataPtr->getEnd(); } +ProgramStateRef createContainerBegin(ProgramStateRef State, + const MemRegion *Cont, + const SymbolRef Sym) { + // Only create if it does not exist + const auto *CDataPtr = getContainerData(State, Cont); + if (CDataPtr) { + if (CDataPtr->getBegin()) { + return State; + } + 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 SymbolRef Sym) { // Only create if it does not exist @@ -675,14 +1057,12 @@ if (CDataPtr) { if (CDataPtr->getEnd()) { return State; - } else { - const auto CData = CDataPtr->newEnd(Sym); - return setContainerData(State, Cont, CData); } - } else { - const auto CData = ContainerData::fromEnd(Sym); + const auto CData = CDataPtr->newEnd(Sym); return setContainerData(State, Cont, CData); } + const auto CData = ContainerData::fromEnd(Sym); + return setContainerData(State, Cont, CData); } const ContainerData *getContainerData(ProgramStateRef State, @@ -767,7 +1147,6 @@ const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal) { - // Try to compare them and get a defined value auto &SVB = State->getStateManager().getSValBuilder(); const auto comparison = SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()), @@ -780,6 +1159,13 @@ return State; } +bool isZero(ProgramStateRef State, const NonLoc &Val) { + auto &BVF = State->getBasicVals(); + return compare(State, Val, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), + BO_EQ); +} + bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) { const auto *Cont = Pos.getContainer(); const auto *CData = getContainerData(State, Cont); @@ -789,6 +1175,13 @@ // Out of range means less than the begin symbol or greater or equal to the // end symbol. + const auto Beg = CData->getBegin(); + if (Beg) { + if (isLess(State, Pos.getOffset(), Beg)) { + return true; + } + } + const auto End = CData->getEnd(); if (End) { if (isGreaterOrEqual(State, Pos.getOffset(), End)) { @@ -799,22 +1192,29 @@ return false; } +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_LT); +} + bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { return compare(State, Sym1, Sym2, BO_GE); } bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc) { - auto &SMgr = State->getStateManager(); - auto &SVB = SMgr.getSValBuilder(); + return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); +} + +bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, + BinaryOperator::Opcode Opc) { + auto &SVB = State->getStateManager().getSValBuilder(); const auto comparison = - SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1), - nonloc::SymbolVal(Sym2), SVB.getConditionType()) + SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()) .getAs(); - if(comparison) { - return !!State->assume(*comparison, true); + if (comparison) { + return !State->assume(*comparison, false); } return false; Index: test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- test/Analysis/Inputs/system-header-simulator-cxx.h +++ test/Analysis/Inputs/system-header-simulator-cxx.h @@ -252,6 +252,12 @@ return size_t(_finish - _start); } + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + T &operator[](size_t n) { return _start[n]; } @@ -295,6 +301,8 @@ list& operator=(list &&other); list& operator=(std::initializer_list ilist); + void clear(); + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } @@ -330,6 +338,16 @@ return size_t(_finish - _start); } + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + T &operator[](size_t n) { return _start[n]; } @@ -369,6 +387,12 @@ forward_list(forward_list &&other); ~forward_list(); + void clear(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } const_iterator cbegin() const { return const_iterator(_start); } Index: test/Analysis/constraint_manager_negate_difference.c =================================================================== --- test/Analysis/constraint_manager_negate_difference.c +++ test/Analysis/constraint_manager_negate_difference.c @@ -1,4 +1,4 @@ -// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection,core.builtin -verify %s +// RUN: %clang_analyze_cc1 -analyzer-checker=debug.ExprInspection,core.builtin -analyzer-config aggressive-relational-comparison-simplification=true -verify %s void clang_analyzer_eval(int); Index: test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- test/Analysis/diagnostics/explicit-suppression.cpp +++ 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:490 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:514 {{Called C++ object pointer is null}} #endif } Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -1,5 +1,5 @@ -// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify -// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config aggressive-relational-comparison-simplification=true -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify #include "Inputs/system-header-simulator-cxx.h" @@ -13,7 +13,110 @@ } } +void simple_good_end_negated(const std::vector &v) { + auto i = v.end(); + if (!(i == v.end())) { + clang_analyzer_warnIfReached(); + *i; // no-warning + } +} + void simple_bad_end(const std::vector &v) { auto i = v.end(); *i; // expected-warning{{Iterator accessed outside of its range}} } + +void simple_good_begin(const std::vector &v) { + auto i = v.begin(); + if (i != v.begin()) { + clang_analyzer_warnIfReached(); + *--i; // no-warning + } +} + +void simple_good_begin_negated(const std::vector &v) { + auto i = v.begin(); + if (!(i == v.begin())) { + clang_analyzer_warnIfReached(); + *--i; // no-warning + } +} + +void simple_bad_begin(const std::vector &v) { + auto i = v.begin(); + *--i; // expected-warning{{Iterator accessed outside of its range}} +} + +void copy(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void decrease(const std::vector &v) { + auto i = v.end(); + --i; + *i; // no-warning +} + +void copy_and_decrease1(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i1; // no-warning +} + +void copy_and_decrease2(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void copy_and_increase1(const std::vector &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (i1 == v.end()) + *i2; // no-warning +} + +void copy_and_increase2(const std::vector &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (i2 == v.end()) + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void copy_and_increase3(const std::vector &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (v.end() == i2) + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void tricky(std::vector &V, int e) { + const auto first = V.begin(); + const auto comp1 = (first != V.end()), comp2 = (first == V.end()); + if (comp1) + *first; +} + +void loop(std::vector &V, int e) { + auto start = V.begin(); + while (true) { + auto item = std::find(start, V.end(), e); + if (item == V.end()) + break; + *item; // no-warning + start = ++item; // no-warning + } +} + +void bad_move(std::list &L1, std::list &L2) { + auto i0 = --L2.cend(); + L1 = std::move(L2); + *++i0; // expected-warning{{Iterator accessed outside of its range}} +}