Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -63,28 +63,36 @@ struct ContainerData { private: - SymbolRef End; + SymbolRef Begin, End; - ContainerData(SymbolRef E) : End(E) {} + ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {} public: + static ContainerData fromBegin(SymbolRef B) { + return ContainerData(B, nullptr); + } + static ContainerData fromEnd(SymbolRef E) { - return ContainerData(E); + return ContainerData(nullptr, E); } + SymbolRef getBegin() const { return Begin; } SymbolRef getEnd() const { return End; } - ContainerData newEnd(SymbolRef E) const { return ContainerData(E); } + ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); } + + ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); } bool operator==(const ContainerData &X) const { - return End == X.End; + return Begin == X.Begin && End == X.End; } bool operator!=(const ContainerData &X) const { - return End != X.End; + return Begin != X.Begin || End != X.End; } void Profile(llvm::FoldingSetNodeID &ID) const { + ID.Add(Begin); ID.Add(End); } }; @@ -112,6 +120,7 @@ class IteratorChecker : public Checker, check::PostStmt, check::LiveSymbols, check::DeadSymbols, eval::Assume> { @@ -121,10 +130,22 @@ void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, const SVal &RVal, OverloadedOperatorKind Op) const; void verifyDereference(CheckerContext &C, const SVal &Val) const; + void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, + bool Postfix) const; + void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, + bool Postfix) const; + void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, + const SVal &RetVal, const SVal &LHS, + const SVal &RHS) const; + void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, + const SVal &Cont) const; void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const; void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, const MemRegion *Cont) const; + void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, + const SVal &RetVal, const SVal &LHS, + const SVal &RHS) const; void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, CheckerContext &C, ExplodedNode *ErrNode) const; @@ -141,6 +162,7 @@ void checkPreCall(const CallEvent &Call, CheckerContext &C) const; void checkPostCall(const CallEvent &Call, CheckerContext &C) const; + void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const; void checkPostStmt(const MaterializeTemporaryExpr *MTE, CheckerContext &C) const; void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; @@ -170,9 +192,13 @@ bool isIteratorType(const QualType &Type); bool isIterator(const CXXRecordDecl *CRD); +bool isBeginCall(const FunctionDecl *Func); bool isEndCall(const FunctionDecl *Func); bool isSimpleComparisonOperator(OverloadedOperatorKind OK); bool isDereferenceOperator(OverloadedOperatorKind OK); +bool isIncrementOperator(OverloadedOperatorKind OK); +bool isDecrementOperator(OverloadedOperatorKind OK); +bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); BinaryOperator::Opcode getOpcode(const SymExpr *SE); const RegionOrSymbol getRegionOrSymbol(const SVal &Val); const ProgramStateRef processComparison(ProgramStateRef State, @@ -183,7 +209,11 @@ const SVal &RVal, bool Eq); const IteratorComparison *loadComparison(ProgramStateRef State, const SymExpr *Condition); +SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); +ProgramStateRef createContainerBegin(ProgramStateRef State, + const MemRegion *Cont, + const SymbolRef Sym); ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym); const IteratorPosition *getIteratorPosition(ProgramStateRef State, @@ -208,6 +238,8 @@ ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, const ContainerData &CData); bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos); +bool isZero(ProgramStateRef State, const NonLoc &Val); +SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym); std::pair createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2); const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1, @@ -229,6 +261,22 @@ if (Func->isOverloadedOperator()) { if (ChecksEnabled[CK_IteratorRangeChecker] && + isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&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)); + } + } + } else if (ChecksEnabled[CK_IteratorRangeChecker] && isDereferenceOperator(Func->getOverloadedOperator())) { // Check for dereference of out-of-range iterators if (const auto *InstCall = dyn_cast(&Call)) { @@ -257,6 +305,36 @@ handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0), Call.getArgSVal(1), Op); } + } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + if (Call.getNumArgs() >= 1) { + handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), + InstCall->getCXXThisVal(), Call.getArgSVal(0)); + } + } else { + if (Call.getNumArgs() >= 2) { + handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), + Call.getReturnValue(), Call.getArgSVal(0), + Call.getArgSVal(1)); + } + } + } else if (isIncrementOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + } else { + handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + } + } else if (isDecrementOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getNumArgs()); + } else { + handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), + Call.getNumArgs()); + } } } else { const auto *OrigExpr = Call.getOriginExpr(); @@ -272,7 +350,11 @@ return; if (const auto *InstCall = dyn_cast(&Call)) { - if (isEndCall(Func)) { + if (isBeginCall(Func)) { + handleBegin(C, OrigExpr, Call.getReturnValue(), + InstCall->getCXXThisVal()); + return; + } else if (isEndCall(Func)) { handleEnd(C, OrigExpr, Call.getReturnValue(), InstCall->getCXXThisVal()); return; @@ -307,6 +389,27 @@ } } +void IteratorChecker::checkPreStmt(const CXXOperatorCallExpr *COCE, + CheckerContext &C) const { + const auto *ThisExpr = COCE->getArg(0); + + auto State = C.getState(); + const auto *LCtx = C.getLocationContext(); + + const auto CurrentThis = State->getSVal(ThisExpr, LCtx); + if (const auto *Reg = CurrentThis.getAsRegion()) { + if (!Reg->getAs()) + return; + const auto OldState = C.getPredecessor()->getFirstPred()->getState(); + const auto OldThis = OldState->getSVal(ThisExpr, LCtx); + const auto *Pos = getIteratorPosition(OldState, OldThis); + if (!Pos) + return; + State = setIteratorPosition(State, CurrentThis, *Pos); + C.addTransition(State); + } +} + void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, CheckerContext &C) const { /* Transfer iterator state for to temporary objects */ @@ -339,6 +442,9 @@ auto ContMap = State->get(); for (const auto Cont : ContMap) { const auto CData = Cont.second; + if (CData.getBegin()) { + SR.markLive(CData.getBegin()); + } if (CData.getEnd()) { SR.markLive(CData.getEnd()); } @@ -459,6 +565,150 @@ } } +void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal, + const SVal &Iter, bool Postfix) const { + // Increment the symbolic expressions which represents the position of the + // iterator + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (Pos) { + auto &SymMgr = C.getSymbolManager(); + const auto oldOffset = Pos->getOffset(); + auto newOffset = + compact(SymMgr, SymMgr.getSymIntExpr(oldOffset, BO_Add, One, + SymMgr.getType(oldOffset))); + auto newPos = Pos->setTo(newOffset); + State = setIteratorPosition(State, Iter, newPos); + State = setIteratorPosition(State, RetVal, Postfix ? *Pos : newPos); + C.addTransition(State); + } +} + +void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal, + const SVal &Iter, bool Postfix) const { + // Decrement the symbolic expressions which represents the position of the + // iterator + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (Pos) { + auto &SymMgr = C.getSymbolManager(); + const auto oldOffset = Pos->getOffset(); + auto newOffset = + compact(SymMgr, SymMgr.getSymIntExpr(oldOffset, BO_Sub, One, + SymMgr.getType(oldOffset))); + auto newPos = Pos->setTo(newOffset); + State = setIteratorPosition(State, Iter, newPos); + State = setIteratorPosition(State, RetVal, Postfix ? *Pos : newPos); + C.addTransition(State); + } +} + +void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C, + OverloadedOperatorKind Op, + const SVal &RetVal, + const SVal &LHS, + const SVal &RHS) const { + // Increment or decrement the symbolic expressions which represents the + // position of the iterator + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, LHS); + if (!Pos) + return; + + const auto *value = &RHS; + if (auto loc = RHS.getAs()) { + const auto val = State->getRawSVal(*loc); + value = &val; + } + + auto &SymMgr = C.getSymbolManager(); + 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()) { + // For concrete integers we can calculate the new position + newOffset = compact( + SymMgr, SymMgr.getSymIntExpr(oldOffset, BinOp, intValue->getValue(), + SymMgr.getType(oldOffset))); + } 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()); + } + auto newPos = Pos->setTo(newOffset); + auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; + State = setIteratorPosition(State, TgtVal, newPos); + C.addTransition(State); +} + +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)) + return; + + auto value = RHS; + if (auto loc = RHS.getAs()) { + value = State->getRawSVal(*loc); + } + + // Incremention or decremention by 0 is never bug + if (isZero(State, value.castAs())) + return; + + auto &SymMgr = C.getSymbolManager(); + auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; + const auto oldOffset = Pos->getOffset(); + const auto intValue = value.getAs(); + if (!intValue) + return; + + SymbolRef newOffset = compact( + SymMgr, SymMgr.getSymIntExpr(oldOffset, BinOp, intValue->getValue(), + SymMgr.getType(oldOffset))); + auto newPos = Pos->setTo(newOffset); + + // If out of range, the only valid operation is to step into the range + if (isOutOfRange(State, newPos)) { + auto *N = C.generateNonFatalErrorNode(State); + if (!N) + return; + reportOutOfRangeBug("Iterator accessed past its end.", LHS, C, N); + } +} + +void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE, + const SVal &RetVal, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // If the container already has a begin symbol then use it. Otherwise first + // create a new one. + auto State = C.getState(); + auto BeginSym = getContainerBegin(State, ContReg); + if (!BeginSym) { + auto &SymMgr = C.getSymbolManager(); + BeginSym = SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + State = createContainerBegin(State, ContReg, BeginSym); + } + State = setIteratorPosition(State, RetVal, + IteratorPosition::getPosition(ContReg, BeginSym)); + C.addTransition(State); +} + void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, const SVal &Cont) const { const auto *ContReg = Cont.getAsRegion(); @@ -516,6 +766,7 @@ BinaryOperator::Opcode Opc); bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, BinaryOperator::Opcode Opc); +std::pair decompose(const SymbolRef Sym); bool isIteratorType(const QualType &Type) { if (Type->isPointerType()) @@ -569,6 +820,13 @@ HasPostIncrOp && HasDerefOp; } +bool isBeginCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + return IdInfo->getName().endswith_lower("begin"); +} + bool isEndCall(const FunctionDecl *Func) { const auto *IdInfo = Func->getIdentifier(); if (!IdInfo) @@ -585,6 +843,18 @@ OK == OO_Subscript; } +bool isIncrementOperator(OverloadedOperatorKind OK) { + return OK == OO_PlusPlus; +} + +bool isDecrementOperator(OverloadedOperatorKind OK) { + return OK == OO_MinusMinus; +} + +bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { + return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || + OK == OO_MinusEqual; +} BinaryOperator::Opcode getOpcode(const SymExpr *SE) { if (const auto *BSE = dyn_cast(SE)) { return BSE->getOpcode(); @@ -644,6 +914,14 @@ return State->get(Condition); } +SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { + const auto *CDataPtr = getContainerData(State, Cont); + if (!CDataPtr) + return nullptr; + + return CDataPtr->getBegin(); +} + SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { const auto *CDataPtr = getContainerData(State, Cont); if (!CDataPtr) @@ -652,6 +930,24 @@ return CDataPtr->getEnd(); } +ProgramStateRef createContainerBegin(ProgramStateRef State, + const MemRegion *Cont, + const SymbolRef Sym) { + // Only create if it does not exist + const auto *CDataPtr = getContainerData(State, Cont); + if (CDataPtr) { + if (CDataPtr->getBegin()) { + return State; + } else { + const auto CData = CDataPtr->newBegin(Sym); + return setContainerData(State, Cont, CData); + } + } else { + const auto CData = ContainerData::fromBegin(Sym); + return setContainerData(State, Cont, CData); + } +} + ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, const SymbolRef Sym) { // Only create if it does not exist @@ -751,7 +1047,7 @@ const IteratorPosition &Pos1, const IteratorPosition &Pos2, bool Equal) { - // Try to compare them and get a defined value + // First Try to compare them and get a defined value auto &SVB = State->getStateManager().getSValBuilder(); const auto comparison = SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Pos1.getOffset()), @@ -761,9 +1057,50 @@ return State->assume(*comparison, Equal); } + // If we did not get a defined value for the comparison, store the difference + // as a constraint. Positions are represented in A, A+n or A-n format, where + // A is a conjured symbol and n a concrete integer. So for e.g. A+n == B+m + // assume A-B == m-n. + auto &SymMgr = State->getSymbolManager(); + SymbolRef diffSim; + llvm::APSInt diffVal; + std::tie(diffSim, diffVal) = + createDifference(SymMgr, Pos1.getOffset(), Pos2.getOffset()); + + if (Equal) { + const auto equality = + SVB.makeNonLoc(diffSim, BO_EQ, diffVal, SVB.getConditionType()) + .getAs(); + + if (equality) { + return State->assume(*equality, Equal); + } + } + return State; } +bool isZero(ProgramStateRef State, const NonLoc &Val) { + return compareToZero(State, Val, BO_EQ); +} + +bool compareToZero(ProgramStateRef State, const NonLoc &Val, + BinaryOperator::Opcode Opc) { + auto &SMgr = State->getStateManager(); + auto &SVB = SMgr.getSValBuilder(); + + const auto comparison = + SVB.evalBinOpNN(State, Opc, Val, nonloc::ConcreteInt(Zero), + SVB.getConditionType()) + .getAs(); + + if (!comparison) + return false; + + ProgramStateRef StateTrue = State->assume(*comparison, true); + return !!StateTrue; +} + bool isOutOfRange(ProgramStateRef State, const IteratorPosition &Pos) { const auto *Cont = Pos.getContainer(); const auto *CData = getContainerData(State, Cont); @@ -773,6 +1110,13 @@ // Out of range means less than the begin symbol or greater or equal to the // end symbol. + const auto Beg = CData->getBegin(); + if (Beg) { + if (isLess(State, Pos.getOffset(), Beg)) { + return true; + } + } + const auto End = CData->getEnd(); if (End) { if (isGreaterOrEqual(State, Pos.getOffset(), End)) { @@ -796,16 +1140,100 @@ auto &SMgr = State->getStateManager(); auto &SVB = SMgr.getSValBuilder(); + llvm::APSInt Int1, Int2; + + // Positions are in the format A, A+n or A-n, where A is a conjured symbol and + // n is a concrete integer. Decompose them to A and n (in case of A, we get + // zero instead of n and in case of A-n we get -n. + std::tie(Sym1, Int1) = decompose(Sym1); + std::tie(Sym2, Int2) = decompose(Sym2); + + // Try to compare the symbols. Currently, we only get equality if they are + // exactly the same. const auto comparison = - SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1), + SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), SVB.getConditionType()) .getAs(); - if(comparison) { - return !!State->assume(*comparison, true); + // If the are not the same, try to retrieve their difference from the + // assumptions. If found, adjust the concrete integers with the difference. + ProgramStateRef newState; + if (!comparison) { + const auto *Diff = getDifference(State, Sym1, Sym2); + if (Diff) { + Int1 += *Diff; + } else { + Diff = getDifference(State, Sym2, Sym1); + if (Diff) { + Int2 += *Diff; + } else { + return false; + } + } + newState = State; + } else { + newState = State->assume(*comparison, true); + if (!newState) + return false; } - return false; + auto &BVF = newState->getSymbolManager().getBasicVals(); + return BVF.evalAPSInt(Opc, Int1, Int2)->getExtValue(); +} + +SymbolRef compact(SymbolManager &SymMgr, const SymbolRef Sym) { + // Turn A+m+n into A+k, where k=m+n + if (const auto *Expr = dyn_cast(Sym)) { + if (const auto *LExpr = dyn_cast(Expr->getLHS())) { + auto &BVF = SymMgr.getBasicVals(); + const auto &newRHS = (Expr->getOpcode() == LExpr->getOpcode()) + ? BVF.getValue(LExpr->getRHS() + Expr->getRHS()) + : BVF.getValue(LExpr->getRHS() - Expr->getRHS()); + if (newRHS != 0) { + return SymMgr.getSymIntExpr(LExpr->getLHS(), LExpr->getOpcode(), newRHS, + Expr->getType()); + } else { + return LExpr->getLHS(); + } + } else { + return Expr; + } + } else { + return Sym; + } +} + +std::pair +createDifference(SymbolManager &SymMgr, SymbolRef Sym1, SymbolRef Sym2) { + // Turn A+n and B+m into a pair of A-B and k, where k==m-n + llvm::APSInt Int1, Int2; + std::tie(Sym1, Int1) = decompose(Sym1); + std::tie(Sym2, Int2) = decompose(Sym2); + + SymbolRef newSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType()); + llvm::APSInt newInt = Int2 - Int1; + + return std::make_pair(newSym, newInt); +} + +const llvm::APSInt *getDifference(ProgramStateRef State, SymbolRef Sym1, + SymbolRef Sym2) { + // Try to retrieve the difference A-B from the constraint manager + auto &SymMgr = State->getSymbolManager(); + auto &CM = State->getConstraintManager(); + auto diffSym = SymMgr.getSymSymExpr(Sym1, BO_Sub, Sym2, Sym1->getType()); + return CM.getSymVal(State, diffSym); +} + +std::pair decompose(SymbolRef Sym) { + // Decompose A+n to a pair of A and n + if (const auto *Expr = dyn_cast(Sym)) { + auto Int = + (Expr->getOpcode() == BO_Add) ? Expr->getRHS() : (-Expr->getRHS()); + return std::make_pair(Expr->getLHS(), Int); + } else { + return std::make_pair(Sym, Zero); + } } } // namespace Index: test/Analysis/iterator-range.cpp =================================================================== --- test/Analysis/iterator-range.cpp +++ test/Analysis/iterator-range.cpp @@ -9,7 +9,96 @@ *i; // no-warning } +void simple_good_end_negated(const std::vector &v) { + auto i = v.end(); + if (!(i == v.end())) + *i; // no-warning +} + void simple_bad_end(const std::vector &v) { auto i = v.end(); *i; // expected-warning{{Iterator accessed outside of its range}} } + +void simple_good_begin(const std::vector &v) { + auto i = v.begin(); + if (i != v.begin()) + *--i; // no-warning +} + +void simple_good_begin_negated(const std::vector &v) { + auto i = v.begin(); + if (!(i == v.begin())) + *--i; // no-warning +} + +void simple_bad_begin(const std::vector &v) { + auto i = v.begin(); + *--i; // expected-warning{{Iterator accessed outside of its range}} +} + +void copy(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void decrease(const std::vector &v) { + auto i = v.end(); + --i; + *i; // no-warning +} + +void copy_and_decrease1(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i1; // no-warning +} + +void copy_and_decrease2(const std::vector &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void copy_and_increase1(const std::vector &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (i1 == v.end()) + *i2; // no-warning +} + +void copy_and_increase2(const std::vector &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (i2 == v.end()) + *i2; // expected-warning{{Iterator accessed outside of its range}} +} + +void tricky(std::vector &V, int e) { + const auto first = V.begin(); + const auto comp1 = (first != V.end()), comp2 = (first == V.end()); + if (comp1) + *first; +} + +void loop(std::vector &V, int e) { + auto start = V.begin(); + while (true) { + auto item = std::find(start, V.end(), e); + if (item == V.end()) + break; + *item; // no-warning + start = ++item; // no-warning + } +} + +void bad_move(std::list &L1, std::list &L2) { + auto i0 = --L2.cend(); + L1 = std::move(L2); + *++i0; // expected-warning{{Iterator accessed outside of its range}} +}