23 using namespace clang;
25 using namespace iterator;
29 class 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;
37 void verifyDereference(CheckerContext &C, SVal Val)
const;
38 void verifyIncrement(CheckerContext &C, SVal Iter)
const;
39 void verifyDecrement(CheckerContext &C, SVal Iter)
const;
41 SVal LHS, SVal RHS)
const;
42 void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS)
const;
43 void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS)
const;
44 void verifyNext(CheckerContext &C, SVal LHS, SVal RHS)
const;
45 void reportBug(
const StringRef &Message, SVal Val, CheckerContext &C,
46 ExplodedNode *ErrNode)
const;
49 IteratorRangeChecker();
51 void checkPreCall(
const CallEvent &Call, CheckerContext &C)
const;
52 void checkPreStmt(
const UnaryOperator *UO, CheckerContext &C)
const;
53 void checkPreStmt(
const BinaryOperator *BO, CheckerContext &C)
const;
55 void checkPreStmt(
const MemberExpr *ME, CheckerContext &C)
const;
57 using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
60 CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
61 {{{
"std",
"advance"}, 2}, &IteratorRangeChecker::verifyAdvance},
62 {{{
"std",
"prev"}, 2}, &IteratorRangeChecker::verifyPrev},
63 {{{
"std",
"next"}, 2}, &IteratorRangeChecker::verifyNext},
74 IteratorRangeChecker::IteratorRangeChecker() {
75 OutOfRangeBugType.reset(
76 new BugType(
this,
"Iterator out of range",
"Misuse of STL APIs"));
79 void IteratorRangeChecker::checkPreCall(
const CallEvent &Call,
80 CheckerContext &C)
const {
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),
138 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
144 void IteratorRangeChecker::checkPreStmt(
const UnaryOperator *UO,
145 CheckerContext &C)
const {
154 verifyDereference(C, SubVal);
156 verifyIncrement(C, SubVal);
158 verifyDecrement(C, SubVal);
163 CheckerContext &C)
const {
166 SVal LVal =
State->getSVal(BO->
getLHS(),
C.getLocationContext());
169 verifyDereference(C, LVal);
171 SVal RVal =
State->getSVal(BO->
getRHS(),
C.getLocationContext());
180 CheckerContext &C)
const {
182 SVal LVal =
State->getSVal(ASE->
getLHS(),
C.getLocationContext());
183 verifyDereference(C, LVal);
186 void IteratorRangeChecker::checkPreStmt(
const MemberExpr *ME,
187 CheckerContext &C)
const {
192 SVal BaseVal =
State->getSVal(ME->
getBase(),
C.getLocationContext());
193 verifyDereference(C, BaseVal);
196 void IteratorRangeChecker::verifyDereference(CheckerContext &C,
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);
209 void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter)
const {
210 auto &BVF =
C.getSValBuilder().getBasicValueFactory();
211 verifyRandomIncrOrDecr(C, OO_Plus, Iter,
212 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
215 void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter)
const {
216 auto &BVF =
C.getSValBuilder().getBasicValueFactory();
217 verifyRandomIncrOrDecr(C, OO_Minus, Iter,
218 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
221 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
223 SVal LHS, SVal RHS)
const {
224 auto State =
C.getState();
227 if (
auto ValAsLoc = RHS.getAs<Loc>()) {
231 if (
Value.isUnknownOrUndef())
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);
263 void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
265 verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
268 void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
270 verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
273 void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
275 verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
278 void IteratorRangeChecker::reportBug(
const StringRef &Message, SVal Val,
280 ExplodedNode *ErrNode)
const {
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();
301 nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
306 const auto *Cont = Pos.getContainer();
311 const auto End = CData->getEnd();
313 if (isEqual(
State, Pos.getOffset(),
End)) {
322 const auto *Cont = Pos.getContainer();
327 const auto Beg = CData->getBegin();
329 if (isLess(
State, Pos.getOffset(), Beg)) {
338 const auto *Cont = Pos.getContainer();
343 const auto End = CData->getEnd();
345 if (isGreater(
State, Pos.getOffset(),
End)) {
367 void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
368 mgr.registerChecker<IteratorRangeChecker>();
371 bool ento::shouldRegisterIteratorRangeChecker(
const CheckerManager &mgr) {