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,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 @@ -422,29 +426,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())) { @@ -924,14 +945,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 +963,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 +1031,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, 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 + // ot of range position is undefined behaviour + if (isOutOfRange(State, advancePosition(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 +1564,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,6 +1632,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,14 +2322,17 @@ 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) return false; - // Out of range means less than the begin symbol or greater or equal to the - // end symbol. + // If `IncludeEnd` is false, "out of range" means less than the begin symbol + // or greater or equal to the end symbol. + // If `IncludeEnd` is true, "out of range" means less than the begin symbol + // or greater than the end symbol. const auto Beg = CData->getBegin(); if (Beg) { @@ -2312,7 +2343,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 +2356,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}} +}