25using namespace iterator;
29class IteratorRangeChecker
30 :
public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
31 check::PreStmt<BinaryOperator>,
32 check::PreStmt<ArraySubscriptExpr>,
33 check::PreStmt<MemberExpr>> {
35 std::unique_ptr<BugType> OutOfRangeBugType;
49 IteratorRangeChecker();
61 {{{
"std",
"advance"}, 2}, &IteratorRangeChecker::verifyAdvance},
62 {{{
"std",
"prev"}, 2}, &IteratorRangeChecker::verifyPrev},
63 {{{
"std",
"next"}, 2}, &IteratorRangeChecker::verifyNext},
74IteratorRangeChecker::IteratorRangeChecker() {
75 OutOfRangeBugType.reset(
76 new BugType(
this,
"Iterator out of range",
"Misuse of STL APIs"));
82 const auto *
Func = dyn_cast_or_null<FunctionDecl>(
Call.getDecl());
86 if (
Func->isOverloadedOperator()) {
89 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
90 verifyIncrement(
C, InstCall->getCXXThisVal());
92 if (
Call.getNumArgs() >= 1) {
93 verifyIncrement(
C,
Call.getArgSVal(0));
98 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
99 verifyDecrement(
C, InstCall->getCXXThisVal());
101 if (
Call.getNumArgs() >= 1) {
102 verifyDecrement(
C,
Call.getArgSVal(0));
106 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
108 if (
Call.getNumArgs() >= 1 &&
109 Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
110 verifyRandomIncrOrDecr(
C,
Func->getOverloadedOperator(),
111 InstCall->getCXXThisVal(),
115 if (
Call.getNumArgs() >= 2 &&
116 Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
117 verifyRandomIncrOrDecr(
C,
Func->getOverloadedOperator(),
118 Call.getArgSVal(0),
Call.getArgSVal(1));
123 if (
const auto *InstCall = dyn_cast<CXXInstanceCall>(&
Call)) {
124 verifyDereference(
C, InstCall->getCXXThisVal());
126 verifyDereference(
C,
Call.getArgSVal(0));
130 const AdvanceFn *Verifier = AdvanceFunctions.lookup(
Call);
132 if (
Call.getNumArgs() > 1) {
133 (this->**Verifier)(
C,
Call.getArgSVal(0),
Call.getArgSVal(1));
135 auto &BVF =
C.getSValBuilder().getBasicValueFactory();
137 C,
Call.getArgSVal(0),
144void IteratorRangeChecker::checkPreStmt(
const UnaryOperator *UO,
151 SVal SubVal = State->getSVal(UO->
getSubExpr(),
C.getLocationContext());
154 verifyDereference(
C, SubVal);
156 verifyIncrement(
C, SubVal);
158 verifyDecrement(
C, SubVal);
166 SVal LVal = State->getSVal(BO->
getLHS(),
C.getLocationContext());
169 verifyDereference(
C, LVal);
171 SVal RVal = State->getSVal(BO->
getRHS(),
C.getLocationContext());
182 SVal LVal = State->getSVal(ASE->
getLHS(),
C.getLocationContext());
183 verifyDereference(
C, LVal);
186void IteratorRangeChecker::checkPreStmt(
const MemberExpr *ME,
192 SVal BaseVal = State->getSVal(ME->
getBase(),
C.getLocationContext());
193 verifyDereference(
C, BaseVal);
198 auto State =
C.getState();
200 if (Pos && isPastTheEnd(State, *Pos)) {
201 auto *N =
C.generateErrorNode(State);
204 reportBug(
"Past-the-end iterator dereferenced.", Val,
C, N);
210 auto &BVF =
C.getSValBuilder().getBasicValueFactory();
211 verifyRandomIncrOrDecr(
C, OO_Plus,
Iter,
216 auto &BVF =
C.getSValBuilder().getBasicValueFactory();
217 verifyRandomIncrOrDecr(
C, OO_Minus,
Iter,
224 auto State =
C.getState();
227 if (
auto ValAsLoc = RHS.
getAs<
Loc>()) {
228 Value = State->getRawSVal(*ValAsLoc);
231 if (
Value.isUnknownOrUndef() || !isa<NonLoc>(
Value))
246 "Iterator should have position after successful advancement");
247 if (isAheadOfRange(State, *PosAfter)) {
248 auto *N =
C.generateErrorNode(State);
251 reportBug(
"Iterator decremented ahead of its valid range.", LHS,
254 if (isBehindPastTheEnd(State, *PosAfter)) {
255 auto *N =
C.generateErrorNode(State);
258 reportBug(
"Iterator incremented behind the past-the-end "
259 "iterator.", LHS,
C, N);
265 verifyRandomIncrOrDecr(
C, OO_PlusEqual, LHS, RHS);
270 verifyRandomIncrOrDecr(
C, OO_Minus, LHS, RHS);
275 verifyRandomIncrOrDecr(
C, OO_Plus, LHS, RHS);
278void IteratorRangeChecker::reportBug(
const StringRef &Message,
SVal Val,
281 auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message,
285 assert(Pos &&
"Iterator without known position cannot be out-of-range.");
287 R->markInteresting(Val);
288 R->markInteresting(Pos->getContainer());
289 C.emitReport(std::move(R));
299 auto &BVF = State->getBasicVals();
311 const auto End = CData->getEnd();
313 if (isEqual(State, Pos.
getOffset(), End)) {
327 const auto Beg = CData->getBegin();
329 if (isLess(State, Pos.
getOffset(), Beg)) {
343 const auto End = CData->getEnd();
345 if (isGreater(State, Pos.
getOffset(), End)) {
354 return compare(State, Sym1, Sym2, BO_LT);
358 return compare(State, Sym1, Sym2, BO_GT);
362 return compare(State, Sym1, Sym2, BO_EQ);
371bool ento::shouldRegisterIteratorRangeChecker(
const CheckerManager &mgr) {
static bool compare(const PathDiagnostic &X, const PathDiagnostic &Y)
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Expr * getLHS()
An array access can be written A[4] or 4[A] (both are equivalent).
A builtin binary operation expression such as "x + y" or "x <= y".
static OverloadedOperatorKind getOverloadedOperator(Opcode Opc)
Retrieve the overloaded operator kind that corresponds to the given binary opcode.
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
bool isImplicitAccess() const
Determine whether the base of this explicit is implicit.
bool isIntegralOrEnumerationType() const
Determine whether this type is an integral or enumeration type.
UnaryOperator - This represents the unary-expression's (except sizeof and alignof),...
Expr * getSubExpr() const
An immutable map from CallDescriptions to arbitrary data.
Represents an abstract call to a function or method along a particular path.
CHECKER * registerChecker(AT &&... Args)
Used to register checkers.
SVal - This represents a symbolic expression, which can be either an L-value or an R-value.
std::optional< T > getAs() const
Convert to the specified SVal type, returning std::nullopt if this SVal is not of the desired type.
Value representing integer constant.
ProgramStateRef advancePosition(ProgramStateRef State, const SVal &Iter, OverloadedOperatorKind Op, const SVal &Distance)
const IteratorPosition * getIteratorPosition(ProgramStateRef State, const SVal &Val)
bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK)
const ContainerData * getContainerData(ProgramStateRef State, const MemRegion *Cont)
bool isDecrementOperator(OverloadedOperatorKind OK)
bool isDereferenceOperator(OverloadedOperatorKind OK)
bool isIncrementOperator(OverloadedOperatorKind OK)
OverloadedOperatorKind
Enumeration specifying the different kinds of C++ overloaded operators.
SymbolRef getOffset() const
const MemRegion * getContainer() const