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 advancePosition(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,9 @@ bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); bool isBoundThroughLazyCompoundVal(const Environment &Env, const MemRegion *Reg); -bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); +bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); bool isZero(ProgramStateRef State, const NonLoc &Val); } // namespace @@ -422,29 +427,46 @@ verifyAccess(C, Call.getArgSVal(0)); } } - 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)); + if (ChecksEnabled[CK_IteratorRangeChecker]) { + if (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 (Call.getNumArgs() >= 2) { - verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), - Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1)); + } else if (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 (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(), + InstCall->getCXXThisVal(), + Call.getArgSVal(0)); + } + } else { + if (Call.getNumArgs() >= 2) { + verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } else if (isDereferenceOperator(Func->getOverloadedOperator())) { + // Check for dereference of out-of-range iterators + if (const auto *InstCall = dyn_cast(&Call)) { + verifyDereference(C, InstCall->getCXXThisVal()); + } else { + verifyDereference(C, Call.getArgSVal(0)); } - } - } else if (ChecksEnabled[CK_IteratorRangeChecker] && - isDereferenceOperator(Func->getOverloadedOperator())) { - // Check for dereference of out-of-range iterators - if (const auto *InstCall = dyn_cast(&Call)) { - verifyDereference(C, InstCall->getCXXThisVal()); - } else { - verifyDereference(C, Call.getArgSVal(0)); } } else if (ChecksEnabled[CK_MismatchedIteratorChecker] && isComparisonOperator(Func->getOverloadedOperator())) { @@ -895,11 +917,12 @@ const SVal &Val) const { auto State = C.getState(); const auto *Pos = getIteratorPosition(State, Val); - if (Pos && isOutOfRange(State, *Pos)) { + if (Pos && isPastTheEnd(State, *Pos)) { auto *N = C.generateNonFatalErrorNode(State); if (!N) return; - reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N); + reportOutOfRangeBug("The past-the-end iterator dereferenced.", Val, C, N); + return; } } @@ -924,14 +947,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 = + advancePosition(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 +965,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 = + advancePosition(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 +1033,64 @@ 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, advancePosition(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 a 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 + // out of range position is undefined behaviour + if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) { auto *N = C.generateNonFatalErrorNode(State); if (!N) return; - reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N); + reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS, + C, N); + } + if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) { + auto *N = C.generateNonFatalErrorNode(State); + if (!N) + return; + reportOutOfRangeBug("Iterator incremented behind the past-the-end " + "iterator.", LHS, C, N); } } @@ -1566,6 +1574,35 @@ C.addTransition(State); } +IteratorPosition IteratorChecker::advancePosition(CheckerContext &C, + OverloadedOperatorKind Op, + const IteratorPosition &Pos, + const SVal &Distance) const { + auto State = C.getState(); + auto &SymMgr = C.getSymbolManager(); + auto &SVB = C.getSValBuilder(); + + assert ((Op == OO_Plus || Op == OO_PlusEqual || + Op == OO_Minus || Op == OO_MinusEqual) && + "Advance operator must be one of +, -, += and -=."); + 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,7 +1642,8 @@ namespace { bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); -bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isEqual(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, @@ -2294,14 +2332,27 @@ BO_EQ); } -bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) { +bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { const auto *Cont = Pos.getContainer(); const auto *CData = getContainerData(State, Cont); if (!CData) return false; - // Out of range means less than the begin symbol or greater or equal to the - // end symbol. + const auto End = CData->getEnd(); + if (End) { + if (isEqual(State, Pos.getOffset(), End)) { + return true; + } + } + + return false; +} + +bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) { + const auto *Cont = Pos.getContainer(); + const auto *CData = getContainerData(State, Cont); + if (!CData) + return false; const auto Beg = CData->getBegin(); if (Beg) { @@ -2310,9 +2361,18 @@ } } + return false; +} + +bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { + const auto *Cont = Pos.getContainer(); + const auto *CData = getContainerData(State, Cont); + if (!CData) + return false; + const auto End = CData->getEnd(); if (End) { - if (isGreaterOrEqual(State, Pos.getOffset(), End)) { + if (isGreater(State, Pos.getOffset(), End)) { return true; } } @@ -2324,8 +2384,12 @@ return compare(State, Sym1, Sym2, BO_LT); } -bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { - return compare(State, Sym1, Sym2, BO_GE); +bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_GT); +} + +bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_EQ); } bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -23,34 +23,13 @@ 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}} + *i; // expected-warning{{The past-the-end iterator dereferenced}} } void copy(const std::vector &v) { auto i1 = v.end(); auto i2 = i1; - *i2; // expected-warning{{Iterator accessed outside of its range}} + *i2; // expected-warning{{The past-the-end iterator dereferenced}} } void decrease(const std::vector &v) { @@ -70,7 +49,7 @@ auto i1 = v.end(); auto i2 = i1; --i1; - *i2; // expected-warning{{Iterator accessed outside of its range}} + *i2; // expected-warning{{The past-the-end iterator dereferenced}} } void copy_and_increase1(const std::vector &v) { @@ -86,7 +65,7 @@ auto i2 = i1; ++i1; if (i2 == v.end()) - *i2; // expected-warning{{Iterator accessed outside of its range}} + *i2; // expected-warning{{The past-the-end iterator dereferenced}} } void copy_and_increase3(const std::vector &v) { @@ -94,7 +73,7 @@ auto i2 = i1; ++i1; if (v.end() == i2) - *i2; // expected-warning{{Iterator accessed outside of its range}} + *i2; // expected-warning{{The past-the-end iterator dereferenced}} } template @@ -116,14 +95,14 @@ void bad_non_std_find(std::vector &V, int e) { auto first = nonStdFind(V.begin(), V.end(), e); - *first; // expected-warning{{Iterator accessed outside of its range}} + *first; // expected-warning{{The past-the-end iterator dereferenced}} } 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; + *first; // no-warning } void loop(std::vector &V, int e) { @@ -147,7 +126,7 @@ auto i0 = --L.cend(); L.push_back(n); ++i0; - *++i0; // expected-warning{{Iterator accessed outside of its range}} + *++i0; // expected-warning{{The past-the-end iterator dereferenced}} } void good_pop_back(std::list &L, int n) { @@ -159,7 +138,7 @@ void bad_pop_back(std::list &L, int n) { auto i0 = --L.cend(); --i0; L.pop_back(); - *++i0; // expected-warning{{Iterator accessed outside of its range}} + *++i0; // expected-warning{{The past-the-end iterator dereferenced}} } void good_push_front(std::list &L, int n) { @@ -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 decremented ahead of its valid range}} } void good_pop_front(std::list &L, int n) { @@ -184,13 +163,13 @@ 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 decremented ahead of its valid range}} } 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}} + *++i0; // expected-warning{{The past-the-end iterator dereferenced}} } void bad_move_push_back(std::list &L1, std::list &L2, int n) { @@ -198,5 +177,25 @@ L2.push_back(n); L1 = std::move(L2); ++i0; - *++i0; // expected-warning{{Iterator accessed outside of its range}} + *++i0; // expected-warning{{The past-the-end iterator dereferenced}} +} + +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 decremented ahead of its valid 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 incremented behind the past-the-end iterator}} }