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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<nonloc::ConcreteInt>()) {
- // 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<Loc>()) {
- value = State->getRawSVal(*loc);
+ auto Value = RHS;
+ if (auto ValAsLoc = RHS.getAs<Loc>()) {
+ Value = State->getRawSVal(*ValAsLoc);
}
- // Incremention or decremention by 0 is never bug
- if (isZero(State, value.castAs<NonLoc>()))
+ 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<nonloc::ConcreteInt>();
- if (!intValue)
+ // Incremention or decremention by 0 is never a bug.
+ if (isZero(State, Value.castAs<NonLoc>()))
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<nonloc::ConcreteInt>()) {
+ // 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<int> &v) {
auto i = v.end();
- *i; // expected-warning{{Iterator accessed outside of its range}}
-}
-
-void simple_good_begin(const std::vector<int> &v) {
- auto i = v.begin();
- if (i != v.begin()) {
- clang_analyzer_warnIfReached();
- *--i; // no-warning
- }
-}
-
-void simple_good_begin_negated(const std::vector<int> &v) {
- auto i = v.begin();
- if (!(i == v.begin())) {
- clang_analyzer_warnIfReached();
- *--i; // no-warning
- }
-}
-
-void simple_bad_begin(const std::vector<int> &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<int> &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<int> &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<int> &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<int> &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 <class InputIterator, class T>
@@ -116,14 +95,14 @@
void bad_non_std_find(std::vector<int> &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<int> &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<int> &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<int> &L, int n) {
@@ -159,7 +138,7 @@
void bad_pop_back(std::list<int> &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<int> &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<int> &L, int n) {
@@ -184,13 +163,13 @@
void bad_pop_front(std::list<int> &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<int> &L1, std::list<int> &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<int> &L1, std::list<int> &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<int> &L) {
+ auto i0 = L.begin();
+ ++i0; // no-warning
+}
+
+void bad_decr_begin(const std::list<int> &L) {
+ auto i0 = L.begin();
+ --i0; // expected-warning{{Iterator decremented ahead of its valid range}}
+}
+
+void good_decr_end(const std::list<int> &L) {
+ auto i0 = L.end();
+ --i0; // no-warning
+}
+
+void bad_incr_end(const std::list<int> &L) {
+ auto i0 = L.end();
+ ++i0; // expected-warning{{Iterator incremented behind the past-the-end iterator}}
}