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,12 @@ ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData); bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isZero(ProgramStateRef State, const NonLoc &Val); +SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym); +std::pair +createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2); +const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1, + SymbolRef Sym2); } // namespace IteratorChecker::IteratorChecker() { @@ -272,6 +315,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 +359,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 +404,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 +445,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 +479,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 +614,160 @@ 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(); + const auto OldOffset = Pos->getOffset(); + auto NewOffset = + compact(SymMgr, SymMgr.getSymIntExpr(OldOffset, BO_Add, + BVF.getValue(llvm::APSInt::get(1)), + SymMgr.getType(OldOffset))); + 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(); + const auto OldOffset = Pos->getOffset(); + auto NewOffset = + compact(SymMgr, SymMgr.getSymIntExpr(OldOffset, BO_Sub, + BVF.getValue(llvm::APSInt::get(1)), + SymMgr.getType(OldOffset))); + auto NewPos = Pos->setTo(NewOffset); + State = setIteratorPosition(State, Iter, NewPos); + State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); + C.addTransition(State); + } +} + +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 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 = compact( + SymMgr, SymMgr.getSymIntExpr(OldOffset, BinOp, intValue->getValue(), + SymMgr.getType(OldOffset))); + } 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()); + } + 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 BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; + const auto OldOffset = Pos->getOffset(); + const auto intValue = value.getAs(); + if (!intValue) + return; + + SymbolRef NewOffset = compact( + SymMgr, SymMgr.getSymIntExpr(OldOffset, BinOp, intValue->getValue(), + SymMgr.getType(OldOffset))); + 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 = 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(); @@ -529,9 +819,14 @@ namespace { +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool compareToZero(ProgramStateRef State, const NonLoc &Val, + BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); +std::pair decompose(SymbolManager &SymMgr, + const SymbolRef Sym); bool isIteratorType(const QualType &Type) { if (Type->isPointerType()) @@ -585,6 +880,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 +903,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 +975,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 +991,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 +1014,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 +1104,7 @@ const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal) { - // Try to compare them and get a defined value + // First 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()), @@ -777,9 +1114,52 @@ return State->assume(*comparison, Equal); } + // If we did not get a defined value for the comparison, store the difference + // as a constraint. Positions are represented in A, A+n or A-n format, where + // A is a conjured symbol and n a concrete integer. So for e.g. A+n == B+m + // assume A-B == m-n. + auto &SymMgr = State->getSymbolManager(); + SymbolRef diffSim; + llvm::APSInt diffVal; + std::tie(diffSim, diffVal) = + createDifference(SymMgr, Pos1.getOffset(), Pos2.getOffset()); + + if (Equal) { + const auto equality = + SVB.makeNonLoc(diffSim, BO_EQ, diffVal, SVB.getConditionType()) + .getAs(); + + if (equality) { + return State->assume(*equality, Equal); + } + } + return State; } +bool isZero(ProgramStateRef State, const NonLoc &Val) { + return compareToZero(State, Val, BO_EQ); +} + +bool compareToZero(ProgramStateRef State, const NonLoc &Val, + BinaryOperator::Opcode Opc) { + auto &SymMgr = State->getStateManager(); + auto &SVB = SymMgr.getSValBuilder(); + auto &BVF = SymMgr.getBasicVals(); + + const auto comparison = + SVB.evalBinOpNN(State, Opc, Val, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), + SVB.getConditionType()) + .getAs(); + + if (!comparison) + return false; + + ProgramStateRef StateTrue = State->assume(*comparison, true); + return !!StateTrue; +} + bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) { const auto *Cont = Pos.getContainer(); const auto *CData = getContainerData(State, Cont); @@ -789,6 +1169,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,25 +1186,111 @@ 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(); + auto &SymMgr = State->getSymbolManager(); + auto &SVB = State->getStateManager().getSValBuilder(); + llvm::APSInt Int1, Int2; + + // Positions are in the format A, A+n or A-n, where A is a conjured symbol and + // n is a concrete integer. Decompose them to A and n (in case of A, we get + // zero instead of n and in case of A-n we get -n. + std::tie(Sym1, Int1) = decompose(SymMgr, Sym1); + std::tie(Sym2, Int2) = decompose(SymMgr, Sym2); + + // Try to compare the symbols. Currently, we only get equality if they are + // exactly the same. const auto comparison = - SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1), + SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), SVB.getConditionType()) .getAs(); - if(comparison) { - return !!State->assume(*comparison, true); + // If the are not the same, try to retrieve their difference from the + // assumptions. If found, adjust the concrete integers with the difference. + ProgramStateRef newState; + if (!comparison) { + const auto *Diff = getDifference(State, Sym1, Sym2); + if (Diff) { + Int1 += *Diff; + } else { + Diff = getDifference(State, Sym2, Sym1); + if (Diff) { + Int2 += *Diff; + } else { + return false; + } + } + newState = State; + } else { + newState = State->assume(*comparison, true); + if (!newState) + return false; } - return false; + auto &BVF = newState->getSymbolManager().getBasicVals(); + return BVF.evalAPSInt(Opc, Int1, Int2)->getExtValue(); +} + +SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym) { + // Turn A+m+n into A+k, where k=m+n + if (const auto *Expr = dyn_cast(Sym)) { + if (const auto *LExpr = dyn_cast(Expr->getLHS())) { + auto &BVF = SymMgr.getBasicVals(); + const auto &newRHS = (Expr->getOpcode() == LExpr->getOpcode()) + ? BVF.getValue(LExpr->getRHS() + Expr->getRHS()) + : BVF.getValue(LExpr->getRHS() - Expr->getRHS()); + if (newRHS != 0) { + return SymMgr.getSymIntExpr(LExpr->getLHS(), LExpr->getOpcode(), newRHS, + Expr->getType()); + } + return LExpr->getLHS(); + } + return Expr; + } + return Sym; +} + +std::pair +createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2) { + // Turn A+n and B+m into a pair of A-B and k, where k==m-n + llvm::APSInt Int1, Int2; + std::tie(Sym1, Int1) = decompose(SymMgr, Sym1); + std::tie(Sym2, Int2) = decompose(SymMgr, Sym2); + + SymbolRef newSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType()); + llvm::APSInt newInt = Int2 - Int1; + + return std::make_pair(newSym, newInt); +} + +const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1, + SymbolRef Sym2) { + // Try to retrieve the difference A-B from the constraint manager + auto &SymMgr = State->getSymbolManager(); + auto &CM = State->getConstraintManager(); + auto diffSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType()); + return CM.getSymVal(State, diffSym); +} + +std::pair decompose(SymbolManager &SymMgr, + SymbolRef Sym) { + // Decompose A+n to a pair of A and n + if (const auto *Expr = dyn_cast(Sym)) { + auto Int = + (Expr->getOpcode() == BO_Add) ? Expr->getRHS() : (-Expr->getRHS()); + return std::make_pair(Expr->getLHS(), Int); + } + auto &BVF = SymMgr.getBasicVals(); + return std::make_pair(Sym, BVF.getValue(llvm::APSInt::get(0))); } } // namespace 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/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 @@ -13,7 +13,102 @@ } } +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 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}} +}