lib/StaticAnalyzer/Checkers/IteratorRangeChecker.cpp - llvm-project/clang - Git at Google

 //===-- IteratorRangeChecker.cpp ----------------------------------*- C++ -*--//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Defines a checker for dereference of the past-the-end iterator and
 // out-of-range increments and decrements.
 //
 //===----------------------------------------------------------------------===//

 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

 #include "Iterator.h"

 using namespace clang;
 using namespace ento;
 using namespace iterator;

 namespace {

 class IteratorRangeChecker
   : public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
                    check::PreStmt<BinaryOperator>,
                    check::PreStmt<ArraySubscriptExpr>,
                    check::PreStmt<MemberExpr>> {

   const BugType OutOfRangeBugType{this, "Iterator out of range",
                                   "Misuse of STL APIs"};

   void verifyDereference(CheckerContext &C, SVal Val) const;
   void verifyIncrement(CheckerContext &C, SVal Iter) const;
   void verifyDecrement(CheckerContext &C, SVal Iter) const;
   void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
                               SVal LHS, SVal RHS) const;
   void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
   void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
   void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
   void reportBug(StringRef Message, SVal Val, CheckerContext &C,
                  ExplodedNode *ErrNode) const;

 public:
   void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
   void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
   void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
   void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
   void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;

   using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
                                                    SVal) const;

   // FIXME: these three functions are also listed in IteratorModeling.cpp,
   // perhaps unify their handling?
   CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
       {{CDM::SimpleFunc, {"std", "advance"}, 2},
        &IteratorRangeChecker::verifyAdvance},
       {{CDM::SimpleFunc, {"std", "prev"}, 2},
        &IteratorRangeChecker::verifyPrev},
       {{CDM::SimpleFunc, {"std", "next"}, 2},
        &IteratorRangeChecker::verifyNext},
   };
 };

 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, NonLoc Val);

 } // namespace

 void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
                                         CheckerContext &C) const {
   // Check for out of range access
   const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
   if (!Func)
     return;

   if (Func->isOverloadedOperator()) {
     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 (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 &&
             Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
           verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
                                  InstCall->getCXXThisVal(),
                                  Call.getArgSVal(0));
         }
       } else {
         if (Call.getNumArgs() >= 2 &&
             Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
           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 {
     const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
     if (Verifier) {
       if (Call.getNumArgs() > 1) {
         (this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
       } else {
         auto &BVF = C.getSValBuilder().getBasicValueFactory();
         (this->**Verifier)(
             C, Call.getArgSVal(0),
             nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
       }
     }
   }
 }

 void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
                                         CheckerContext &C) const {
   if (isa<CXXThisExpr>(UO->getSubExpr()))
     return;

   ProgramStateRef State = C.getState();
   UnaryOperatorKind OK = UO->getOpcode();
   SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());

   if (isDereferenceOperator(OK)) {
     verifyDereference(C, SubVal);
   } else if (isIncrementOperator(OK)) {
     verifyIncrement(C, SubVal);
   } else if (isDecrementOperator(OK)) {
     verifyDecrement(C, SubVal);
   }
 }

 void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
                                         CheckerContext &C) const {
   ProgramStateRef State = C.getState();
   BinaryOperatorKind OK = BO->getOpcode();
   SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());

   if (isDereferenceOperator(OK)) {
     verifyDereference(C, LVal);
   } else if (isRandomIncrOrDecrOperator(OK)) {
     SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
     if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
       return;
     verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
                            RVal);
   }
 }

 void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
                                         CheckerContext &C) const {
   ProgramStateRef State = C.getState();
   SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
   verifyDereference(C, LVal);
 }

 void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
                                         CheckerContext &C) const {
   if (!ME->isArrow() || ME->isImplicitAccess())
     return;

   ProgramStateRef State = C.getState();
   SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
   verifyDereference(C, BaseVal);
 }

 void IteratorRangeChecker::verifyDereference(CheckerContext &C,
                                              SVal Val) const {
   auto State = C.getState();
   const auto *Pos = getIteratorPosition(State, Val);
   if (Pos && isPastTheEnd(State, *Pos)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportBug("Past-the-end iterator dereferenced.", Val, C, N);
     return;
   }
 }

 void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
   auto &BVF = C.getSValBuilder().getBasicValueFactory();
   verifyRandomIncrOrDecr(C, OO_Plus, Iter,
                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 }

 void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
   auto &BVF = C.getSValBuilder().getBasicValueFactory();
   verifyRandomIncrOrDecr(C, OO_Minus, Iter,
                      nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
 }

 void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
                                                   OverloadedOperatorKind Op,
                                                   SVal LHS, SVal RHS) const {
   auto State = C.getState();

   auto Value = RHS;
   if (auto ValAsLoc = RHS.getAs<Loc>()) {
     Value = State->getRawSVal(*ValAsLoc);
   }

   if (Value.isUnknownOrUndef() || !isa<NonLoc>(Value))
     return;

   // Incremention or decremention by 0 is never a bug.
   if (isZero(State, Value.castAs<NonLoc>()))
     return;

   // The result may be the past-end iterator of the container, but any other
   // out of range position is undefined behaviour
   auto StateAfter = advancePosition(State, LHS, Op, Value);
   if (!StateAfter)
     return;

   const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
   assert(PosAfter &&
          "Iterator should have position after successful advancement");
   if (isAheadOfRange(State, *PosAfter)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportBug("Iterator decremented ahead of its valid range.", LHS,
                         C, N);
   }
   if (isBehindPastTheEnd(State, *PosAfter)) {
     auto *N = C.generateErrorNode(State);
     if (!N)
       return;
     reportBug("Iterator incremented behind the past-the-end "
                         "iterator.", LHS, C, N);
   }
 }

 void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
                                          SVal RHS) const {
   verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
 }

 void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
                                       SVal RHS) const {
   verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
 }

 void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
                                       SVal RHS) const {
   verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
 }

 void IteratorRangeChecker::reportBug(StringRef Message, SVal Val,
                                      CheckerContext &C,
                                      ExplodedNode *ErrNode) const {
   auto R = std::make_unique<PathSensitiveBugReport>(OutOfRangeBugType, Message,
                                                     ErrNode);

   const auto *Pos = getIteratorPosition(C.getState(), Val);
   assert(Pos && "Iterator without known position cannot be out-of-range.");

   R->markInteresting(Val);
   R->markInteresting(Pos->getContainer());
   C.emitReport(std::move(R));
 }

 namespace {

 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
 bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);

 bool isZero(ProgramStateRef State, NonLoc Val) {
   auto &BVF = State->getBasicVals();
   return compare(State, Val,
                  nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
                  BO_EQ);
 }

 bool isPastTheEnd(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 (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) {
     if (isLess(State, Pos.getOffset(), Beg)) {
       return true;
     }
   }

   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 (isGreater(State, Pos.getOffset(), End)) {
       return true;
     }
   }

   return false;
 }

 bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
   return compare(State, Sym1, Sym2, BO_LT);
 }

 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);
 }

 } // namespace

 void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
   mgr.registerChecker<IteratorRangeChecker>();
 }

 bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
   return true;
 }
	//===-- IteratorRangeChecker.cpp ----------------------------------- C++ ---//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// Defines a checker for dereference of the past-the-end iterator and
	// out-of-range increments and decrements.
	//
	//===----------------------------------------------------------------------===//

	#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
	#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
	#include "clang/StaticAnalyzer/Core/Checker.h"
	#include "clang/StaticAnalyzer/Core/PathSensitive/CallDescription.h"
	#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
	#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"

	#include "Iterator.h"

	using namespace clang;
	using namespace ento;
	using namespace iterator;

	namespace {

	class IteratorRangeChecker
	: public Checker<check::PreCall, check::PreStmt<UnaryOperator>,
	check::PreStmt<BinaryOperator>,
	check::PreStmt<ArraySubscriptExpr>,
	check::PreStmt<MemberExpr>> {

	const BugType OutOfRangeBugType{this, "Iterator out of range",
	"Misuse of STL APIs"};

	void verifyDereference(CheckerContext &C, SVal Val) const;
	void verifyIncrement(CheckerContext &C, SVal Iter) const;
	void verifyDecrement(CheckerContext &C, SVal Iter) const;
	void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op,
	SVal LHS, SVal RHS) const;
	void verifyAdvance(CheckerContext &C, SVal LHS, SVal RHS) const;
	void verifyPrev(CheckerContext &C, SVal LHS, SVal RHS) const;
	void verifyNext(CheckerContext &C, SVal LHS, SVal RHS) const;
	void reportBug(StringRef Message, SVal Val, CheckerContext &C,
	ExplodedNode *ErrNode) const;

	public:
	void checkPreCall(const CallEvent &Call, CheckerContext &C) const;
	void checkPreStmt(const UnaryOperator *UO, CheckerContext &C) const;
	void checkPreStmt(const BinaryOperator *BO, CheckerContext &C) const;
	void checkPreStmt(const ArraySubscriptExpr *ASE, CheckerContext &C) const;
	void checkPreStmt(const MemberExpr *ME, CheckerContext &C) const;

	using AdvanceFn = void (IteratorRangeChecker::*)(CheckerContext &, SVal,
	SVal) const;

	// FIXME: these three functions are also listed in IteratorModeling.cpp,
	// perhaps unify their handling?
	CallDescriptionMap<AdvanceFn> AdvanceFunctions = {
	{{CDM::SimpleFunc, {"std", "advance"}, 2},
	&IteratorRangeChecker::verifyAdvance},
	{{CDM::SimpleFunc, {"std", "prev"}, 2},
	&IteratorRangeChecker::verifyPrev},
	{{CDM::SimpleFunc, {"std", "next"}, 2},
	&IteratorRangeChecker::verifyNext},
	};
	};

	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, NonLoc Val);

	} // namespace

	void IteratorRangeChecker::checkPreCall(const CallEvent &Call,
	CheckerContext &C) const {
	// Check for out of range access
	const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl());
	if (!Func)
	return;

	if (Func->isOverloadedOperator()) {
	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 (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 &&
	Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) {
	verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(),
	InstCall->getCXXThisVal(),
	Call.getArgSVal(0));
	}
	} else {
	if (Call.getNumArgs() >= 2 &&
	Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) {
	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 {
	const AdvanceFn *Verifier = AdvanceFunctions.lookup(Call);
	if (Verifier) {
	if (Call.getNumArgs() > 1) {
	(this->**Verifier)(C, Call.getArgSVal(0), Call.getArgSVal(1));
	} else {
	auto &BVF = C.getSValBuilder().getBasicValueFactory();
	(this->**Verifier)(
	C, Call.getArgSVal(0),
	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
	}
	}
	}
	}

	void IteratorRangeChecker::checkPreStmt(const UnaryOperator *UO,
	CheckerContext &C) const {
	if (isa<CXXThisExpr>(UO->getSubExpr()))
	return;

	ProgramStateRef State = C.getState();
	UnaryOperatorKind OK = UO->getOpcode();
	SVal SubVal = State->getSVal(UO->getSubExpr(), C.getLocationContext());

	if (isDereferenceOperator(OK)) {
	verifyDereference(C, SubVal);
	} else if (isIncrementOperator(OK)) {
	verifyIncrement(C, SubVal);
	} else if (isDecrementOperator(OK)) {
	verifyDecrement(C, SubVal);
	}
	}

	void IteratorRangeChecker::checkPreStmt(const BinaryOperator *BO,
	CheckerContext &C) const {
	ProgramStateRef State = C.getState();
	BinaryOperatorKind OK = BO->getOpcode();
	SVal LVal = State->getSVal(BO->getLHS(), C.getLocationContext());

	if (isDereferenceOperator(OK)) {
	verifyDereference(C, LVal);
	} else if (isRandomIncrOrDecrOperator(OK)) {
	SVal RVal = State->getSVal(BO->getRHS(), C.getLocationContext());
	if (!BO->getRHS()->getType()->isIntegralOrEnumerationType())
	return;
	verifyRandomIncrOrDecr(C, BinaryOperator::getOverloadedOperator(OK), LVal,
	RVal);
	}
	}

	void IteratorRangeChecker::checkPreStmt(const ArraySubscriptExpr *ASE,
	CheckerContext &C) const {
	ProgramStateRef State = C.getState();
	SVal LVal = State->getSVal(ASE->getLHS(), C.getLocationContext());
	verifyDereference(C, LVal);
	}

	void IteratorRangeChecker::checkPreStmt(const MemberExpr *ME,
	CheckerContext &C) const {
	if (!ME->isArrow() \|\| ME->isImplicitAccess())
	return;

	ProgramStateRef State = C.getState();
	SVal BaseVal = State->getSVal(ME->getBase(), C.getLocationContext());
	verifyDereference(C, BaseVal);
	}

	void IteratorRangeChecker::verifyDereference(CheckerContext &C,
	SVal Val) const {
	auto State = C.getState();
	const auto *Pos = getIteratorPosition(State, Val);
	if (Pos && isPastTheEnd(State, *Pos)) {
	auto *N = C.generateErrorNode(State);
	if (!N)
	return;
	reportBug("Past-the-end iterator dereferenced.", Val, C, N);
	return;
	}
	}

	void IteratorRangeChecker::verifyIncrement(CheckerContext &C, SVal Iter) const {
	auto &BVF = C.getSValBuilder().getBasicValueFactory();
	verifyRandomIncrOrDecr(C, OO_Plus, Iter,
	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
	}

	void IteratorRangeChecker::verifyDecrement(CheckerContext &C, SVal Iter) const {
	auto &BVF = C.getSValBuilder().getBasicValueFactory();
	verifyRandomIncrOrDecr(C, OO_Minus, Iter,
	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))));
	}

	void IteratorRangeChecker::verifyRandomIncrOrDecr(CheckerContext &C,
	OverloadedOperatorKind Op,
	SVal LHS, SVal RHS) const {
	auto State = C.getState();

	auto Value = RHS;
	if (auto ValAsLoc = RHS.getAs<Loc>()) {
	Value = State->getRawSVal(*ValAsLoc);
	}

	if (Value.isUnknownOrUndef() \|\| !isa<NonLoc>(Value))
	return;

	// Incremention or decremention by 0 is never a bug.
	if (isZero(State, Value.castAs<NonLoc>()))
	return;

	// The result may be the past-end iterator of the container, but any other
	// out of range position is undefined behaviour
	auto StateAfter = advancePosition(State, LHS, Op, Value);
	if (!StateAfter)
	return;

	const auto *PosAfter = getIteratorPosition(StateAfter, LHS);
	assert(PosAfter &&
	"Iterator should have position after successful advancement");
	if (isAheadOfRange(State, *PosAfter)) {
	auto *N = C.generateErrorNode(State);
	if (!N)
	return;
	reportBug("Iterator decremented ahead of its valid range.", LHS,
	C, N);
	}
	if (isBehindPastTheEnd(State, *PosAfter)) {
	auto *N = C.generateErrorNode(State);
	if (!N)
	return;
	reportBug("Iterator incremented behind the past-the-end "
	"iterator.", LHS, C, N);
	}
	}

	void IteratorRangeChecker::verifyAdvance(CheckerContext &C, SVal LHS,
	SVal RHS) const {
	verifyRandomIncrOrDecr(C, OO_PlusEqual, LHS, RHS);
	}

	void IteratorRangeChecker::verifyPrev(CheckerContext &C, SVal LHS,
	SVal RHS) const {
	verifyRandomIncrOrDecr(C, OO_Minus, LHS, RHS);
	}

	void IteratorRangeChecker::verifyNext(CheckerContext &C, SVal LHS,
	SVal RHS) const {
	verifyRandomIncrOrDecr(C, OO_Plus, LHS, RHS);
	}

	void IteratorRangeChecker::reportBug(StringRef Message, SVal Val,
	CheckerContext &C,
	ExplodedNode *ErrNode) const {
	auto R = std::make_unique<PathSensitiveBugReport>(OutOfRangeBugType, Message,
	ErrNode);

	const auto *Pos = getIteratorPosition(C.getState(), Val);
	assert(Pos && "Iterator without known position cannot be out-of-range.");

	R->markInteresting(Val);
	R->markInteresting(Pos->getContainer());
	C.emitReport(std::move(R));
	}

	namespace {

	bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
	bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);
	bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2);

	bool isZero(ProgramStateRef State, NonLoc Val) {
	auto &BVF = State->getBasicVals();
	return compare(State, Val,
	nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))),
	BO_EQ);
	}

	bool isPastTheEnd(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 (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) {
	if (isLess(State, Pos.getOffset(), Beg)) {
	return true;
	}
	}

	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 (isGreater(State, Pos.getOffset(), End)) {
	return true;
	}
	}

	return false;
	}

	bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) {
	return compare(State, Sym1, Sym2, BO_LT);
	}

	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);
	}

	} // namespace

	void ento::registerIteratorRangeChecker(CheckerManager &mgr) {
	mgr.registerChecker<IteratorRangeChecker>();
	}

	bool ento::shouldRegisterIteratorRangeChecker(const CheckerManager &mgr) {
	return true;
	}