baloghadamsoftware created this revision.
baloghadamsoftware added a reviewer: NoQ.
baloghadamsoftware added a project: clang.
Herald added subscribers: donat.nagy, Szelethus, mikhail.ramalho, a.sidorin,
rnkovacs, szepet, whisperity.
Herald added a reviewer: george.karpenkov.
Previously, the iterator range checker only warned upon dereference of
iterators outside their valid range as well as increments and decrements of
out-of range iterators where the result remains out-of range. However, the
`C++` standard is more strict than this: decrementing `begin()` or inrementing
`end()` results in undefined behavior even if the iterator is not dereferenced
afterward. Coming back to the range once out-of-range is also undefined.
This patch corrects the behavior of the iterator range checker: warnings are
given for any operation whose result is ahead of `begin()` or past the `end()`
(which is the past-end iterator itself, thus now we are speaking of past
past-end).
Repository:
rC Clang
https://reviews.llvm.org/D53812
Files:
lib/StaticAnalyzer/Checkers/IteratorChecker.cpp
test/Analysis/iterator-range.cpp
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<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}}
-}
-
void copy(const std::vector<int> &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<int> &L, int n) {
@@ -184,7 +163,7 @@
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 accessed outside of its range}}
}
void bad_move(std::list<int> &L1, std::list<int> &L2) {
@@ -200,3 +179,23 @@
++i0;
*++i0; // expected-warning{{Iterator accessed outside of its range}}
}
+
+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 accessed outside of its 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 accessed outside of its range}}
+}
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<CXXInstanceCall>(&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<CXXInstanceCall>(&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<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));
}
} 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<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, 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<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 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
+ // 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<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,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);
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
