Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -238,14 +238,17 @@ void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; void handleEraseAfter(CheckerContext &C, const SVal &Iter1, const SVal &Iter2) const; + void verifyIncrement(CheckerContext &C, const SVal &Iter) const; + void verifyDecrement(CheckerContext &C, const SVal &Iter) const; void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, - const SVal &RetVal, const SVal &LHS, - const SVal &RHS) const; + const SVal &LHS, const SVal &RHS) const; void verifyMatch(CheckerContext &C, const SVal &Iter, const MemRegion *Cont) const; void verifyMatch(CheckerContext &C, const SVal &Iter1, const SVal &Iter2) const; - + IteratorPosition shiftPosition(CheckerContext &C, OverloadedOperatorKind Op, + const IteratorPosition &Pos, + const SVal &Distance) const; void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const; void reportMismatchedBug(const StringRef &Message, const SVal &Val1, @@ -388,7 +391,8 @@ bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg); -bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos, + bool IncludeEnd = false); bool isZero(ProgramStateRef State, const NonLoc &Val); } // namespace @@ -423,19 +427,37 @@ } } if (ChecksEnabled[CK_IteratorRangeChecker] && + isIncrementOperator(Func->getOverloadedOperator())) { + // Check for out-of-range incrementions + if (const auto *InstCall = dyn_cast(&Call)) { + verifyIncrement(C, InstCall->getCXXThisVal()); + } else { + if (Call.getNumArgs() >= 1) { + verifyIncrement(C, Call.getArgSVal(0)); + } + } + } else if (ChecksEnabled[CK_IteratorRangeChecker] && + isDecrementOperator(Func->getOverloadedOperator())) { + // Check for out-of-range decrementions + if (const auto *InstCall = dyn_cast(&Call)) { + verifyDecrement(C, InstCall->getCXXThisVal()); + } else { + if (Call.getNumArgs() >= 1) { + verifyDecrement(C, Call.getArgSVal(0)); + } + } + } else 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)); + Call.getArgSVal(0), Call.getArgSVal(1)); } } } else if (ChecksEnabled[CK_IteratorRangeChecker] && @@ -924,14 +946,9 @@ 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); + const auto NewPos = + shiftPosition(C, OO_Plus, *Pos, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); State = setIteratorPosition(State, Iter, NewPos); State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); C.addTransition(State); @@ -947,14 +964,9 @@ 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); + const auto NewPos = + shiftPosition(C, OO_Minus, *Pos, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); State = setIteratorPosition(State, Iter, NewPos); State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); C.addTransition(State); @@ -1020,69 +1032,56 @@ 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, 4); - } - auto NewPos = Pos->setTo(NewOffset); auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; - State = setIteratorPosition(State, TgtVal, NewPos); + State = + setIteratorPosition(State, TgtVal, shiftPosition(C, Op, *Pos, *value)); C.addTransition(State); } +void IteratorChecker::verifyIncrement(CheckerContext &C, + const SVal &Iter) const { + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + verifyRandomIncrOrDecr(C, OO_Plus, Iter, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); +} + +void IteratorChecker::verifyDecrement(CheckerContext &C, + const SVal &Iter) const { + auto &BVF = C.getSValBuilder().getBasicValueFactory(); + verifyRandomIncrOrDecr(C, OO_Minus, Iter, + nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); +} + 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)) + if (!Pos) return; - auto value = RHS; - if (auto loc = RHS.getAs()) { - value = State->getRawSVal(*loc); + auto Value = RHS; + if (auto ValAsLoc = RHS.getAs()) { + Value = State->getRawSVal(*ValAsLoc); } - // Incremention or decremention by 0 is never bug - if (isZero(State, value.castAs())) + if (Value.isUnknown()) 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) + // Incremention or decremention by 0 is never bug + if (isZero(State, Value.castAs())) 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)) { + // The result may be the past-end iterator of the container, but any other + // ot of range position is undefined behaviour + if (isOutOfRange(State, shiftPosition(C, Op, *Pos, Value), true)) { auto *N = C.generateNonFatalErrorNode(State); if (!N) return; - reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N); + reportOutOfRangeBug("Iterator accessed outside of its range.", LHS, C, N); } } @@ -1566,6 +1565,31 @@ C.addTransition(State); } +IteratorPosition IteratorChecker::shiftPosition(CheckerContext &C, + OverloadedOperatorKind Op, + const IteratorPosition &Pos, + const SVal &Distance) const { + auto State = C.getState(); + auto &SymMgr = C.getSymbolManager(); + auto &SVB = C.getSValBuilder(); + auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; + if (const auto IntDist = Distance.getAs()) { + // For concrete integers we can calculate the new position + return Pos.setTo(SVB.evalBinOp(State, BinOp, + nonloc::SymbolVal(Pos.getOffset()), *IntDist, + SymMgr.getType(Pos.getOffset())) + .getAsSymbol()); + } else { + // For other symbols create a new symbol to keep expressions simple + const auto &LCtx = C.getLocationContext(); + const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx, + SymMgr.getType(Pos.getOffset()), + C.blockCount()); + State = assumeNoOverflow(State, NewPosSym, 4); + return Pos.setTo(NewPosSym); + } +} + void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const { @@ -1605,6 +1629,7 @@ namespace { bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isGreater(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); @@ -2294,7 +2319,8 @@ BO_EQ); } -bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) { +bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos, + bool IncludeEnd) { const auto *Cont = Pos.getContainer(); const auto *CData = getContainerData(State, Cont); if (!CData) @@ -2312,7 +2338,8 @@ const auto End = CData->getEnd(); if (End) { - if (isGreaterOrEqual(State, Pos.getOffset(), End)) { + if ((IncludeEnd && isGreater(State, Pos.getOffset(), End)) || + (!IncludeEnd && isGreaterOrEqual(State, Pos.getOffset(), End))) { return true; } } @@ -2324,6 +2351,10 @@ return compare(State, Sym1, Sym2, BO_LT); } +bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_GT); +} + bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { return compare(State, Sym1, Sym2, BO_GE); } Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -26,27 +26,6 @@ *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; @@ -172,7 +151,7 @@ auto i0 = L.cbegin(); L.push_front(n); --i0; - *--i0; // expected-warning{{Iterator accessed outside of its range}} + --i0; // expected-warning{{Iterator accessed outside of its range}} } void good_pop_front(std::list &L, int n) { @@ -184,7 +163,7 @@ void bad_pop_front(std::list &L, int n) { auto i0 = ++L.cbegin(); L.pop_front(); - *--i0; // expected-warning{{Iterator accessed outside of its range}} + --i0; // expected-warning{{Iterator accessed outside of its range}} } void bad_move(std::list &L1, std::list &L2) { @@ -200,3 +179,23 @@ ++i0; *++i0; // expected-warning{{Iterator accessed outside of its range}} } + +void good_incr_begin(const std::list &L) { + auto i0 = L.begin(); + ++i0; // no-warning +} + +void bad_decr_begin(const std::list &L) { + auto i0 = L.begin(); + --i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_decr_end(const std::list &L) { + auto i0 = L.end(); + --i0; // no-warning +} + +void bad_incr_end(const std::list &L) { + auto i0 = L.end(); + ++i0; // expected-warning{{Iterator accessed outside of its range}} +}