Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -279,15 +279,23 @@ let ParentPackage = CplusplusAlpha in { +def IteratorRangeChecker : Checker<"IteratorRange">, + HelpText<"Check for iterators used outside their valid ranges">, + DescFile<"IteratorChecker.cpp">; + +def MismatchedIteratorChecker : Checker<"MismatchedIterator">, + HelpText<"Check for use of iterators of different containers where iterators of the same container are expected">, + DescFile<"IteratorChecker.cpp">; + +def InvalidatedIteratorChecker : Checker<"InvalidatedIterator">, + HelpText<"Check for use of invalidated iterators">, + DescFile<"IteratorChecker.cpp">; + def MisusedMovedObjectChecker: Checker<"MisusedMovedObject">, HelpText<"Method calls on a moved-from object and copying a moved-from " "object will be reported">, DescFile<"MisusedMovedObjectChecker.cpp">; -def IteratorPastEndChecker : Checker<"IteratorPastEnd">, - HelpText<"Check iterators used past end">, - DescFile<"IteratorPastEndChecker.cpp">; - } // end: "alpha.cplusplus" Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -39,7 +39,7 @@ GenericTaintChecker.cpp GTestChecker.cpp IdenticalExprChecker.cpp - IteratorPastEndChecker.cpp + IteratorChecker.cpp IvarInvalidationChecker.cpp LLVMConventionsChecker.cpp LocalizationChecker.cpp Index: lib/StaticAnalyzer/Checkers/IteratorChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/IteratorChecker.cpp @@ -0,0 +1,2486 @@ +//===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Defines a checker for using iterators outside their range (past end). Usage +// means here dereferencing, incrementing etc. +// +//===----------------------------------------------------------------------===// + +#include "ClangSACheckers.h" +#include "clang/AST/DeclTemplate.h" +#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" +#include "clang/StaticAnalyzer/Core/Checker.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" + +#include + +using namespace clang; +using namespace ento; + +namespace { + +struct IteratorPosition { +private: + const MemRegion *Cont; + bool Valid; + SymbolRef Offset; + IteratorPosition(const MemRegion *C, bool V, SymbolRef Of) + : Cont(C), Valid(V), Offset(Of) {} + +public: + const MemRegion *getContainer() const { return Cont; } + bool isValid() const { return Valid; } + SymbolRef getOffset() const { return Offset; } + + IteratorPosition invalidate() const { + return IteratorPosition(Cont, false, Offset); + } + + static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { + return IteratorPosition(C, true, Of); + } + + IteratorPosition setTo(SymbolRef NewOf) const { + return IteratorPosition(Cont, Valid, NewOf); + } + + IteratorPosition reAssign(const MemRegion *NewCont) const { + return IteratorPosition(NewCont, Valid, Offset); + } + + bool operator==(const IteratorPosition &X) const { + return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; + } + + bool operator!=(const IteratorPosition &X) const { + return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset; + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddPointer(Cont); + ID.AddInteger(Valid); + ID.Add(Offset); + } +}; + +typedef llvm::PointerUnion RegionOrSymbol; + +struct ContainerData { +private: + SymbolRef Begin, End; + + 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(nullptr, E); + } + + SymbolRef getBegin() const { return Begin; } + SymbolRef getEnd() const { return End; } + + 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 Begin == X.Begin && End == X.End; + } + + bool operator!=(const ContainerData &X) const { + return Begin != X.Begin || End != X.End; + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.Add(Begin); + ID.Add(End); + } +}; + +struct IteratorComparison { +private: + RegionOrSymbol Left, Right; + bool Equality; + +public: + IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq) + : Left(L), Right(R), Equality(Eq) {} + + RegionOrSymbol getLeft() const { return Left; } + RegionOrSymbol getRight() const { return Right; } + bool isEquality() const { return Equality; } + bool operator==(const IteratorComparison &X) const { + return Left == X.Left && Right == X.Right && Equality == X.Equality; + } + bool operator!=(const IteratorComparison &X) const { + return Left != X.Left || Right != X.Right || Equality != X.Equality; + } + void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); } +}; + +class IteratorChecker + : public Checker, + check::PreStmt, + check::PostStmt, check::Bind, + check::BeginFunction, check::LiveSymbols, + check::DeadSymbols, eval::Assume, eval::Call> { + mutable IdentifierInfo *II_find = nullptr, *II_find_end = nullptr, + *II_find_first_of = nullptr, *II_find_if = nullptr, + *II_find_if_not = nullptr, *II_lower_bound = nullptr, + *II_upper_bound = nullptr, *II_search = nullptr, + *II_search_n = nullptr; + + std::unique_ptr OutOfRangeBugType; + std::unique_ptr MismatchedBugType; + std::unique_ptr InvalidatedBugType; + + void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, + const SVal &RVal, OverloadedOperatorKind Op) const; + void verifyAccess(CheckerContext &C, const SVal &Val) 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 handleAssign(CheckerContext &C, const SVal &Cont, + const Expr *CE = nullptr, + const SVal &OldCont = UndefinedVal()) const; + void handleClear(CheckerContext &C, const SVal &Cont) const; + void handlePushBack(CheckerContext &C, const SVal &Cont) const; + void handlePopBack(CheckerContext &C, const SVal &Cont) const; + void handlePushFront(CheckerContext &C, const SVal &Cont) const; + void handlePopFront(CheckerContext &C, const SVal &Cont) const; + void handleInsert(CheckerContext &C, const SVal &Iter) const; + void handleErase(CheckerContext &C, const SVal &Iter) const; + void handleErase(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const; + void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; + void handleEraseAfter(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const; + void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, + const SVal &RetVal, 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; + bool evalFind(CheckerContext &C, const CallExpr *CE) const; + bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const; + bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const; + bool evalFindIf(CheckerContext &C, const CallExpr *CE) const; + bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const; + bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const; + bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const; + bool evalSearch(CheckerContext &C, const CallExpr *CE) const; + bool evalSearchN(CheckerContext &C, const CallExpr *CE) const; + void Find(CheckerContext &C, const CallExpr *CE) const; + + void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; + void reportMismatchedBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; + void reportInvalidatedBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; + + void initIdentifiers(ASTContext &Ctx) const; + +public: + IteratorChecker(); + + enum CheckKind { + CK_IteratorRangeChecker, + CK_MismatchedIteratorChecker, + CK_InvalidatedIteratorChecker, + CK_NumCheckKinds + }; + + DefaultBool ChecksEnabled[CK_NumCheckKinds]; + CheckName CheckNames[CK_NumCheckKinds]; + + void checkPreCall(const CallEvent &Call, CheckerContext &C) const; + void checkPostCall(const CallEvent &Call, CheckerContext &C) const; + void checkPreStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; + void checkPreStmt(const CXXOperatorCallExpr *COCE, CheckerContext &C) const; + void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; + void checkBeginFunction(CheckerContext &C) const; + void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; + void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const; + void checkPostStmt(const MaterializeTemporaryExpr *MTE, + CheckerContext &C) const; + void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; + void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; + ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond, + bool Assumption) const; + bool evalCall(const CallExpr *CE, CheckerContext &C) const; +}; +} // namespace + +REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition) +REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *, + IteratorPosition) + +REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData) + +REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *, + IteratorComparison) + +#define INIT_ID(Id) \ + if (!II_##Id) \ + II_##Id = &Ctx.Idents.get(#Id) + +static llvm::APSInt Zero = llvm::APSInt::get(0); +static llvm::APSInt One = llvm::APSInt::get(1); + +namespace { + +bool isIteratorType(const QualType &Type); +bool isIterator(const CXXRecordDecl *CRD); +bool isComparisonOperator(OverloadedOperatorKind OK); +bool isBeginCall(const FunctionDecl *Func); +bool isEndCall(const FunctionDecl *Func); +bool isAssignCall(const FunctionDecl *Func); +bool isClearCall(const FunctionDecl *Func); +bool isPushBackCall(const FunctionDecl *Func); +bool isEmplaceBackCall(const FunctionDecl *Func); +bool isPopBackCall(const FunctionDecl *Func); +bool isPushFrontCall(const FunctionDecl *Func); +bool isEmplaceFrontCall(const FunctionDecl *Func); +bool isPopFrontCall(const FunctionDecl *Func); +bool isInsertCall(const FunctionDecl *Func); +bool isEraseCall(const FunctionDecl *Func); +bool isEraseAfterCall(const FunctionDecl *Func); +bool isEmplaceCall(const FunctionDecl *Func); +bool isAssignmentOperator(OverloadedOperatorKind OK); +bool isSimpleComparisonOperator(OverloadedOperatorKind OK); +bool isAccessOperator(OverloadedOperatorKind OK); +bool isDereferenceOperator(OverloadedOperatorKind OK); +bool isIncrementOperator(OverloadedOperatorKind OK); +bool isDecrementOperator(OverloadedOperatorKind OK); +bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); +bool hasSubscriptOperator(const MemRegion *Reg); +bool frontModifiable(const MemRegion *Reg); +bool backModifiable(const MemRegion *Reg); +BinaryOperator::Opcode getOpcode(const SymExpr *SE); +const RegionOrSymbol getRegionOrSymbol(const SVal &Val); +const ProgramStateRef processComparison(ProgramStateRef State, + RegionOrSymbol LVal, + RegionOrSymbol RVal, bool Equal); +const ProgramStateRef saveComparison(ProgramStateRef State, + const SymExpr *Condition, const SVal &LVal, + 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, + const SVal &Val); +const IteratorPosition *getIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym); +ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, + const IteratorPosition &Pos); +ProgramStateRef setIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + const IteratorPosition &Pos); +ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); +ProgramStateRef adjustIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + const IteratorPosition &Pos, bool Equal); +ProgramStateRef relateIteratorPositions(ProgramStateRef State, + const IteratorPosition &Pos1, + const IteratorPosition &Pos2, + bool Equal); +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont); +ProgramStateRef +invalidateAllIteratorPositionsExcept(ProgramStateRef State, + const MemRegion *Cont, SymbolRef Offset, + BinaryOperator::Opcode Opc); +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset, + BinaryOperator::Opcode Opc); +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset1, + BinaryOperator::Opcode Opc1, + SymbolRef Offset2, + BinaryOperator::Opcode Opc2); +ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont); +ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont, + SymbolRef Offset, + BinaryOperator::Opcode Opc); +ProgramStateRef replaceSymbolInIteratorPositionsIf( + ProgramStateRef State, SymbolManager &SymMgr, SymbolRef OldSym, + SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); +const ContainerData *getContainerData(ProgramStateRef State, + const MemRegion *Cont); +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, + SymbolRef Sym2); +} // namespace + +IteratorChecker::IteratorChecker() { + OutOfRangeBugType.reset( + new BugType(this, "Iterator of out Range", "Misuse of STL APIs")); + OutOfRangeBugType->setSuppressOnSink(true); + MismatchedBugType.reset( + new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs")); + MismatchedBugType->setSuppressOnSink(true); + InvalidatedBugType.reset( + new BugType(this, "Iterator invalidated", "Misuse of STL APIs")); + InvalidatedBugType->setSuppressOnSink(true); +} + +void IteratorChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + // Check for out of range access or access of invalidated position and + // iterator mismatches + const auto *Func = dyn_cast_or_null(Call.getDecl()); + if (!Func) + return; + + if (Func->isOverloadedOperator()) { + if (ChecksEnabled[CK_InvalidatedIteratorChecker] && + isAccessOperator(Func->getOverloadedOperator())) { + // Check for any kind of access of invalidated iterator positions + if (const auto *InstCall = dyn_cast(&Call)) { + verifyAccess(C, InstCall->getCXXThisVal()); + } else { + verifyAccess(C, Call.getArgSVal(0)); + } + } + 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)) { + verifyDereference(C, InstCall->getCXXThisVal()); + } else { + verifyDereference(C, Call.getArgSVal(0)); + } + } else if (ChecksEnabled[CK_MismatchedIteratorChecker] && + isComparisonOperator(Func->getOverloadedOperator())) { + // Check for comparisons of iterators of different containers + if (const auto *InstCall = dyn_cast(&Call)) { + if (Call.getNumArgs() < 1) + return; + + if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) || + !isIteratorType(Call.getArgExpr(0)->getType())) + return; + + verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); + } else { + if (Call.getNumArgs() < 2) + return; + + if (!isIteratorType(Call.getArgExpr(0)->getType()) || + !isIteratorType(Call.getArgExpr(1)->getType())) + return; + + verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } else if (const auto *InstCall = dyn_cast(&Call)) { + if (!ChecksEnabled[CK_MismatchedIteratorChecker]) + return; + + const auto *ContReg = InstCall->getCXXThisVal().getAsRegion(); + if (!ContReg) + return; + // Check for erase, insert and emplace using iterator of another container + if (isEraseCall(Func) || isEraseAfterCall(Func)) { + verifyMatch(C, Call.getArgSVal(0), + InstCall->getCXXThisVal().getAsRegion()); + if (Call.getNumArgs() == 2) { + verifyMatch(C, Call.getArgSVal(1), + InstCall->getCXXThisVal().getAsRegion()); + } + } else if (isInsertCall(Func)) { + verifyMatch(C, Call.getArgSVal(0), + InstCall->getCXXThisVal().getAsRegion()); + if (Call.getNumArgs() == 3 && + isIteratorType(Call.getArgExpr(1)->getType()) && + isIteratorType(Call.getArgExpr(2)->getType())) { + verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2)); + } + } else if (isEmplaceCall(Func)) { + verifyMatch(C, Call.getArgSVal(0), + InstCall->getCXXThisVal().getAsRegion()); + } + } else if (!isa(&Call)) { + // The main purpose of iterators is to abstract away from different + // containers and provide a (maybe limited) uniform access to them. + // This implies that any correctly written template function that + // works on multiple containers using iterators takes different + // template parameters for different containers. So we can safely + // assume that passing iterators of different containers as arguments + // whose type replaces the same template parameter is a bug. + + if (!ChecksEnabled[CK_MismatchedIteratorChecker]) + return; + + const auto *Templ = Func->getPrimaryTemplate(); + if (!Templ) + return; + + const auto *TParams = Templ->getTemplateParameters(); + const auto *TArgs = Func->getTemplateSpecializationArgs(); + + for (auto i = 0U; i < TParams->size(); ++i) { + const auto *TPDecl = dyn_cast(TParams->getParam(i)); + if (!TPDecl) + continue; + + if (TPDecl->isParameterPack()) + continue; + + const auto TAType = TArgs->get(i).getAsType(); + if (!isIteratorType(TAType)) + continue; + + SVal LHS = UndefinedVal(); + + for (auto j = 0U; j < Func->getNumParams(); ++j) { + const auto *Param = Func->getParamDecl(j); + const auto *ParamType = + Param->getType()->getAs(); + if (!ParamType || + ParamType->getReplacedParameter()->getDecl() != TPDecl) + continue; + if (LHS.isUndef()) { + LHS = Call.getArgSVal(j); + } else { + verifyMatch(C, LHS, Call.getArgSVal(j)); + } + } + } + } +} + +void IteratorChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + // Record new iterator positions and iterator position changes + const auto *Func = dyn_cast_or_null(Call.getDecl()); + if (!Func) + return; + + if (Func->isOverloadedOperator()) { + const auto Op = Func->getOverloadedOperator(); + if (isAssignmentOperator(Op)) { + const auto *InstCall = dyn_cast(&Call); + if (Func->getParamDecl(0)->getType()->isRValueReferenceType()) { + handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), + Call.getArgSVal(0)); + } else { + handleAssign(C, InstCall->getCXXThisVal()); + } + } else if (isSimpleComparisonOperator(Op)) { + if (const auto *InstCall = dyn_cast(&Call)) { + handleComparison(C, Call.getReturnValue(), InstCall->getCXXThisVal(), + Call.getArgSVal(0), Op); + } else { + 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 { + if (const auto *InstCall = dyn_cast(&Call)) { + if (isAssignCall(Func)) { + handleAssign(C, InstCall->getCXXThisVal()); + } else if (isClearCall(Func)) { + handleClear(C, InstCall->getCXXThisVal()); + } else if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { + handlePushBack(C, InstCall->getCXXThisVal()); + } else if (isPopBackCall(Func)) { + handlePopBack(C, InstCall->getCXXThisVal()); + } else if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { + handlePushFront(C, InstCall->getCXXThisVal()); + } else if (isPopFrontCall(Func)) { + handlePopFront(C, InstCall->getCXXThisVal()); + } else if (isInsertCall(Func) || isEmplaceCall(Func)) { + handleInsert(C, Call.getArgSVal(0)); + } else if (isEraseCall(Func)) { + if (Call.getNumArgs() == 1) { + handleErase(C, Call.getArgSVal(0)); + } else if (Call.getNumArgs() == 2) { + handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1)); + } + } else if (isEraseAfterCall(Func)) { + if (Call.getNumArgs() == 1) { + handleEraseAfter(C, Call.getArgSVal(0)); + } else if (Call.getNumArgs() == 2) { + handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1)); + } + } + } + + const auto *OrigExpr = Call.getOriginExpr(); + if (!OrigExpr) + return; + + if (!isIteratorType(Call.getResultType())) + return; + + auto State = C.getState(); + // Already bound to container? + if (getIteratorPosition(State, Call.getReturnValue())) + return; + + if (const auto *InstCall = dyn_cast(&Call)) { + if (isBeginCall(Func)) { + handleBegin(C, OrigExpr, Call.getReturnValue(), + InstCall->getCXXThisVal()); + return; + } else if (isEndCall(Func)) { + handleEnd(C, OrigExpr, Call.getReturnValue(), + InstCall->getCXXThisVal()); + return; + } + } + + // Copy-like and move constructors + if (isa(&Call) && Call.getNumArgs() == 1) { + if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { + State = setIteratorPosition(State, Call.getReturnValue(), *Pos); + if (cast(Func)->isMoveConstructor()) { + State = removeIteratorPosition(State, Call.getArgSVal(0)); + } + C.addTransition(State); + return; + } + } + + // Assumption: if return value is an iterator which is not yet bound to a + // container, then look for the first iterator argument, and + // bind the return value to the same container. This approach + // works for STL algorithms. + for (unsigned i = 0; i < Call.getNumArgs(); ++i) { + if (isIteratorType(Call.getArgExpr(i)->getType())) { + if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { + assignToContainer(C, OrigExpr, Call.getReturnValue(), + Pos->getContainer()); + return; + } + } + } + } +} + +void IteratorChecker::checkPreStmt(const CXXConstructExpr *CCE, + CheckerContext &C) const { + // Check match of first-last iterator pair in a constructor of a container + if (CCE->getNumArgs() < 2) + return; + + const auto *Ctr = CCE->getConstructor(); + if (Ctr->getNumParams() < 2) + return; + + if (Ctr->getParamDecl(0)->getName() != "first" || + Ctr->getParamDecl(1)->getName() != "last") + return; + + if (!isIteratorType(CCE->getArg(0)->getType()) || + !isIteratorType(CCE->getArg(1)->getType())) + return; + + auto State = C.getState(); + const auto *LCtx = C.getPredecessor()->getLocationContext(); + + verifyMatch(C, State->getSVal(CCE->getArg(0), LCtx), + State->getSVal(CCE->getArg(1), LCtx)); +} + +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::checkBind(SVal Loc, SVal Val, const Stmt *S, + CheckerContext &C) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos) { + State = setIteratorPosition(State, Loc, *Pos); + C.addTransition(State); + } else { + const auto *OldPos = getIteratorPosition(State, Loc); + if (OldPos) { + State = removeIteratorPosition(State, Loc); + C.addTransition(State); + } + } +} + +void IteratorChecker::checkBeginFunction(CheckerContext &C) const { + // Copy state of iterator arguments to iterator parameters + auto State = C.getState(); + const auto *LCtx = C.getLocationContext(); + + const auto *Site = cast(LCtx)->getCallSite(); + if (!Site) + return; + + const auto *FD = dyn_cast(LCtx->getDecl()); + if (!FD) + return; + + const auto *CE = dyn_cast(Site); + if (!CE) + return; + + bool Change = false; + int idx = 0; + for (const auto P : FD->parameters()) { + auto Param = State->getLValue(P, LCtx); + auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent()); + const auto *Pos = getIteratorPosition(State, Arg); + if (!Pos) + continue; + State = setIteratorPosition(State, Param, *Pos); + Change = true; + } + if (Change) { + C.addTransition(State); + } +} + +void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, + CheckerContext &C) const { + /* Transfer iterator state for to temporary objects */ + auto State = C.getState(); + const auto *LCtx = C.getLocationContext(); + const auto *Pos = + getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx)); + if (!Pos) + return; + State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos); + C.addTransition(State); +} + +void IteratorChecker::checkLiveSymbols(ProgramStateRef State, + SymbolReaper &SR) const { + // Keep symbolic expressions of iterator positions, container begins and ends + // alive + auto RegionMap = State->get(); + for (const auto Reg : RegionMap) { + const auto Pos = Reg.second; + SR.markLive(Pos.getOffset()); + } + + auto SymbolMap = State->get(); + for (const auto Sym : SymbolMap) { + const auto Pos = Sym.second; + SR.markLive(Pos.getOffset()); + } + + 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()); + } + } +} + +void IteratorChecker::checkDeadSymbols(SymbolReaper &SR, + CheckerContext &C) const { + // Cleanup + auto State = C.getState(); + + auto RegionMap = State->get(); + for (const auto Reg : RegionMap) { + if (!SR.isLiveRegion(Reg.first)) { + State = State->remove(Reg.first); + } + } + + auto SymbolMap = State->get(); + for (const auto Sym : SymbolMap) { + if (!SR.isLive(Sym.first)) { + State = State->remove(Sym.first); + } + } + + auto ContMap = State->get(); + for (const auto Cont : ContMap) { + if (!SR.isLiveRegion(Cont.first)) { + State = State->remove(Cont.first); + } + } + + auto ComparisonMap = State->get(); + for (const auto Comp : ComparisonMap) { + if (!SR.isLive(Comp.first)) { + State = State->remove(Comp.first); + } + } +} + +ProgramStateRef IteratorChecker::evalAssume(ProgramStateRef State, SVal Cond, + bool Assumption) const { + // Load recorded comparison and transfer iterator state between sides + // according to comparison operator and assumption + const auto *SE = Cond.getAsSymExpr(); + if (!SE) + return State; + + auto Opc = getOpcode(SE); + if (Opc != BO_EQ && Opc != BO_NE) + return State; + + bool Negated = false; + const auto *Comp = loadComparison(State, SE); + if (!Comp) { + // Try negated comparison, which is a SymExpr to 0 integer comparison + const auto *SIE = dyn_cast(SE); + if (!SIE) + return State; + + if (SIE->getRHS() != 0) + return State; + + SE = SIE->getLHS(); + Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation + Opc = getOpcode(SE); + if (Opc != BO_EQ && Opc != BO_NE) + return State; + + Comp = loadComparison(State, SE); + if (!Comp) + return State; + } + + return processComparison(State, Comp->getLeft(), Comp->getRight(), + (Comp->isEquality() == Assumption) != Negated); +} + +// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions +// checker (see patch r284960) or another similar checker for C++ STL +// functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions). +bool IteratorChecker::evalCall(const CallExpr *CE, CheckerContext &C) const { + const FunctionDecl *FD = C.getCalleeDecl(CE); + if (!FD) + return false; + + ASTContext &Ctx = C.getASTContext(); + initIdentifiers(Ctx); + + if (FD->getKind() == Decl::Function) { + if (FD->isInStdNamespace()) { + if (FD->getIdentifier() == II_find) { + return evalFind(C, CE); + } else if (FD->getIdentifier() == II_find_end) { + return evalFindEnd(C, CE); + } else if (FD->getIdentifier() == II_find_first_of) { + return evalFindFirstOf(C, CE); + } else if (FD->getIdentifier() == II_find_if) { + return evalFindIf(C, CE); + } else if (FD->getIdentifier() == II_find_if_not) { + return evalFindIfNot(C, CE); + } else if (FD->getIdentifier() == II_upper_bound) { + return evalUpperBound(C, CE); + } else if (FD->getIdentifier() == II_lower_bound) { + return evalLowerBound(C, CE); + } else if (FD->getIdentifier() == II_search) { + return evalSearch(C, CE); + } else if (FD->getIdentifier() == II_search_n) { + return evalSearchN(C, CE); + } + } + } + + return false; +} + +void IteratorChecker::handleComparison(CheckerContext &C, const SVal &RetVal, + const SVal &LVal, const SVal &RVal, + OverloadedOperatorKind Op) const { + // Record the operands and the operator of the comparison for the next + // evalAssume, if the result is a symbolic expression. If it is a concrete + // value (only one branch is possible), then transfer the state between + // the operands according to the operator and the result + auto State = C.getState(); + if (const auto *Condition = RetVal.getAsSymbolicExpression()) { + const auto *LPos = getIteratorPosition(State, LVal); + const auto *RPos = getIteratorPosition(State, RVal); + if (!LPos && !RPos) + return; + State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual); + C.addTransition(State); + } else if (const auto TruthVal = RetVal.getAs()) { + if ((State = processComparison( + State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal), + (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) { + C.addTransition(State); + } else { + C.generateSink(State, C.getPredecessor()); + } + } +} + +void IteratorChecker::verifyDereference(CheckerContext &C, + const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && isOutOfRange(State, *Pos)) { + // If I do not put a tag here, some range tests will fail + static CheckerProgramPointTag Tag("IteratorRangeChecker", + "IteratorOutOfRange"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + if (!N) { + return; + } + reportOutOfRangeBug("Iterator accessed outside of its range.", Val, C, N); + } +} + +void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Val); + if (Pos && !Pos->isValid()) { + // If I do not put a tag here, some invalidation tests will fail + static CheckerProgramPointTag Tag("InvalidatedIteratorChecker", + "InvalidatedIterator"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + if (!N) { + return; + } + reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N); + } +} + +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::verifyMatch(CheckerContext &C, const SVal &Iter, + const MemRegion *Cont) const { + // Verify match between a container and the container of an iterator + while (const auto *CBOR = Cont->getAs()) { + Cont = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (Pos && Pos->getContainer() != Cont) { + auto *N = C.generateNonFatalErrorNode(State); + if (!N) { + return; + } + reportMismatchedBug("Iterator access mismatched.", Iter, C, N); + } +} + +void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const { + // Verify match between the containers of two iterators + auto State = C.getState(); + const auto *Pos1 = getIteratorPosition(State, Iter1); + const auto *Pos2 = getIteratorPosition(State, Iter2); + if (Pos1 && Pos2 && Pos1->getContainer() != Pos2->getContainer()) { + // If I do not put a tag here, the comparison test will fail + static CheckerProgramPointTag Tag("MismatchedIteratorChecker", + "MismatchedIterator"); + auto *N = C.generateNonFatalErrorNode(State, &Tag); + if (!N) { + return; + } + reportMismatchedBug("Iterator access mismatched.", Iter1, 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(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // If the container already has an end symbol then use it. Otherwise first + // create a new one. + auto State = C.getState(); + auto EndSym = getContainerEnd(State, ContReg); + if (!EndSym) { + auto &SymMgr = C.getSymbolManager(); + EndSym = SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + State = createContainerEnd(State, ContReg, EndSym); + } + State = setIteratorPosition(State, RetVal, + IteratorPosition::getPosition(ContReg, EndSym)); + C.addTransition(State); +} + +void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE, + const SVal &RetVal, + const MemRegion *Cont) const { + while (const auto *CBOR = Cont->getAs()) { + Cont = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + auto &SymMgr = C.getSymbolManager(); + auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + State = setIteratorPosition(State, RetVal, + IteratorPosition::getPosition(Cont, Sym)); + C.addTransition(State); +} + +void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont, + const Expr *CE, const SVal &OldCont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // Assignment of a new value to a container always invalidates all its + // iterators + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (CData) { + State = invalidateAllIteratorPositions(State, ContReg); + } + + // In case of move, iterators of the old container (except the past-end + // iterators) remain valid but refer to the new container + if (!OldCont.isUndef()) { + const auto *OldContReg = OldCont.getAsRegion(); + if (OldContReg) { + while (const auto *CBOR = OldContReg->getAs()) { + OldContReg = CBOR->getSuperRegion(); + } + const auto OldCData = getContainerData(State, OldContReg); + if (OldCData) { + if (const auto OldEndSym = OldCData->getEnd()) { + State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, + OldEndSym, BO_GE); + auto &SymMgr = C.getSymbolManager(); + auto NewEndSym = + SymMgr.conjureSymbol(CE, C.getLocationContext(), + C.getASTContext().LongTy, C.blockCount()); + if (CData) { + State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); + } else { + State = setContainerData(State, ContReg, + ContainerData::fromEnd(NewEndSym)); + } + State = replaceSymbolInIteratorPositionsIf( + State, SymMgr, OldEndSym, NewEndSym, OldEndSym, BO_LT); + } else { + State = reassignAllIteratorPositions(State, OldContReg, ContReg); + } + if (const auto OldBeginSym = OldCData->getBegin()) { + if (CData) { + State = + setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); + } else { + State = setContainerData(State, ContReg, + ContainerData::fromBegin(OldBeginSym)); + } + State = + setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); + } + } else { + State = reassignAllIteratorPositions(State, OldContReg, ContReg); + } + } + } + C.addTransition(State); +} + +void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // The clear() operation invalidates all the iterators, except the past-end + // iterators of list-like containers + auto State = C.getState(); + if (!hasSubscriptOperator(ContReg) || !backModifiable(ContReg)) { + const auto CData = getContainerData(State, ContReg); + if (CData) { + if (const auto EndSym = CData->getEnd()) { + State = + invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE); + C.addTransition(State); + return; + } + } + } + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); +} + +void IteratorChecker::handlePushBack(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // For deque-like containers invalidate all iterator positions + auto State = C.getState(); + if (hasSubscriptOperator(ContReg) && frontModifiable(ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); + return; + } + + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + // For vector-like containers invalidate the past-end iterator positions + if (const auto EndSym = CData->getEnd()) { + if (hasSubscriptOperator(ContReg)) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + } + auto &SymMgr = C.getSymbolManager(); + const auto newEndSym = + compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Add, One, + SymMgr.getType(EndSym))); + State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); + } + C.addTransition(State); +} + +void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + if (const auto EndSym = CData->getEnd()) { + auto &SymMgr = C.getSymbolManager(); + const auto BackSym = + compact(SymMgr, SymMgr.getSymIntExpr(EndSym, BO_Sub, One, + SymMgr.getType(EndSym))); + // For vector-like and deque-like containers invalidate the last and the + // past-end iterator positions. For list-like containers only invalidate + // the last position + if (hasSubscriptOperator(ContReg) && backModifiable(ContReg)) { + State = invalidateIteratorPositions(State, BackSym, BO_GE); + State = setContainerData(State, ContReg, CData->newEnd(nullptr)); + } else { + State = invalidateIteratorPositions(State, BackSym, BO_EQ); + } + auto newEndSym = BackSym; + State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); + C.addTransition(State); + } +} + +void IteratorChecker::handlePushFront(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + // For deque-like containers invalidate all iterator positions + auto State = C.getState(); + if (hasSubscriptOperator(ContReg)) { + State = invalidateAllIteratorPositions(State, ContReg); + C.addTransition(State); + } else { + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + if (const auto BeginSym = CData->getBegin()) { + auto &SymMgr = C.getSymbolManager(); + const auto newBeginSym = + compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Sub, One, + SymMgr.getType(BeginSym))); + State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); + C.addTransition(State); + } + } +} + +void IteratorChecker::handlePopFront(CheckerContext &C, + const SVal &Cont) const { + const auto *ContReg = Cont.getAsRegion(); + if (!ContReg) + return; + + while (const auto *CBOR = ContReg->getAs()) { + ContReg = CBOR->getSuperRegion(); + } + + auto State = C.getState(); + const auto CData = getContainerData(State, ContReg); + if (!CData) + return; + + // For deque-like containers invalidate all iterator positions. For list-like + // iterators only invalidate the first position + if (const auto BeginSym = CData->getBegin()) { + if (hasSubscriptOperator(ContReg)) { + State = invalidateIteratorPositions(State, BeginSym, BO_LE); + } else { + State = invalidateIteratorPositions(State, BeginSym, BO_EQ); + } + auto &SymMgr = C.getSymbolManager(); + const auto newBeginSym = + compact(SymMgr, SymMgr.getSymIntExpr(BeginSym, BO_Add, One, + SymMgr.getType(BeginSym))); + State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); + C.addTransition(State); + } +} + +void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (!Pos) + return; + + // For deque-like containers invalidate all iterator positions. For + // vector-like containers invalidate iterator positions after the insertion. + const auto *Cont = Pos->getContainer(); + if (hasSubscriptOperator(Cont) && backModifiable(Cont)) { + if (frontModifiable(Cont)) { + State = invalidateAllIteratorPositions(State, Cont); + } else { + State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); + } + if (const auto *CData = getContainerData(State, Cont)) { + if (const auto EndSym = CData->getEnd()) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + State = setContainerData(State, Cont, CData->newEnd(nullptr)); + } + } + C.addTransition(State); + } +} + +void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (!Pos) + return; + + // For deque-like containers invalidate all iterator positions. For + // vector-like containers invalidate iterator positions at and after the + // deletion. For list-like containers only invalidate the deleted position. + const auto *Cont = Pos->getContainer(); + if (hasSubscriptOperator(Cont) && backModifiable(Cont)) { + if (frontModifiable(Cont)) { + State = invalidateAllIteratorPositions(State, Cont); + } else { + State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); + } + if (const auto *CData = getContainerData(State, Cont)) { + if (const auto EndSym = CData->getEnd()) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + State = setContainerData(State, Cont, CData->newEnd(nullptr)); + } + } + } else { + State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ); + } + C.addTransition(State); +} + +void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const { + auto State = C.getState(); + const auto *Pos1 = getIteratorPosition(State, Iter1); + const auto *Pos2 = getIteratorPosition(State, Iter2); + if (!Pos1 || !Pos2) + return; + + // For deque-like containers invalidate all iterator positions. For + // vector-like containers invalidate iterator positions at and after the + // deletion range. For list-like containers only invalidate the deleted + // position range [first..last]. + const auto *Cont = Pos1->getContainer(); + if (hasSubscriptOperator(Cont) && backModifiable(Cont)) { + if (frontModifiable(Cont)) { + State = invalidateAllIteratorPositions(State, Cont); + } else { + State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); + } + if (const auto *CData = getContainerData(State, Cont)) { + if (const auto EndSym = CData->getEnd()) { + State = invalidateIteratorPositions(State, EndSym, BO_GE); + State = setContainerData(State, Cont, CData->newEnd(nullptr)); + } + } + } else { + State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE, + Pos2->getOffset(), BO_LT); + } + C.addTransition(State); +} + +void IteratorChecker::handleEraseAfter(CheckerContext &C, + const SVal &Iter) const { + auto State = C.getState(); + const auto *Pos = getIteratorPosition(State, Iter); + if (!Pos) + return; + + // Invalidate the deleted iterator position, which is the position of the + // parameter plus one. + auto &SymMgr = C.getSymbolManager(); + auto NextSym = SymMgr.getSymIntExpr(Pos->getOffset(), BO_Add, One, + SymMgr.getType(Pos->getOffset())); + State = invalidateIteratorPositions(State, NextSym, BO_EQ); + C.addTransition(State); +} + +void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1, + const SVal &Iter2) const { + auto State = C.getState(); + const auto *Pos1 = getIteratorPosition(State, Iter1); + const auto *Pos2 = getIteratorPosition(State, Iter2); + if (!Pos1 || !Pos2) + return; + + // Invalidate the deleted iterator position range (first..last) + State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT, + Pos2->getOffset(), BO_LT); + C.addTransition(State); +} + +bool IteratorChecker::evalFind(CheckerContext &C, const CallExpr *CE) const { + if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalFindEnd(CheckerContext &C, const CallExpr *CE) const { + if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType()) && + isIteratorType(CE->getArg(2)->getType()) && + isIteratorType(CE->getArg(3)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalFindFirstOf(CheckerContext &C, + const CallExpr *CE) const { + if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType()) && + isIteratorType(CE->getArg(2)->getType()) && + isIteratorType(CE->getArg(3)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalFindIf(CheckerContext &C, const CallExpr *CE) const { + if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalFindIfNot(CheckerContext &C, + const CallExpr *CE) const { + if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalLowerBound(CheckerContext &C, + const CallExpr *CE) const { + if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalUpperBound(CheckerContext &C, + const CallExpr *CE) const { + if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalSearch(CheckerContext &C, const CallExpr *CE) const { + if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType()) && + isIteratorType(CE->getArg(2)->getType()) && + isIteratorType(CE->getArg(3)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +bool IteratorChecker::evalSearchN(CheckerContext &C, const CallExpr *CE) const { + if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && + isIteratorType(CE->getArg(0)->getType()) && + isIteratorType(CE->getArg(1)->getType())) { + Find(C, CE); + return true; + } + return false; +} + +void IteratorChecker::Find(CheckerContext &C, const CallExpr *CE) const { + auto state = C.getState(); + auto &svalBuilder = C.getSValBuilder(); + const auto *LCtx = C.getLocationContext(); + + auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); + auto SecondParam = state->getSVal(CE->getArg(1), LCtx); + + auto stateFound = state->BindExpr(CE, LCtx, RetVal); + auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam); + + C.addTransition(stateFound); + C.addTransition(stateNotFound); +} + +void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*OutOfRangeBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + +void IteratorChecker::reportMismatchedBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*MismatchedBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + +void IteratorChecker::reportInvalidatedBug(const StringRef &Message, + const SVal &Val, CheckerContext &C, + ExplodedNode *ErrNode) const { + auto R = llvm::make_unique(*InvalidatedBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + +void IteratorChecker::initIdentifiers(ASTContext &Ctx) const { + INIT_ID(find); + INIT_ID(find_end); + INIT_ID(find_first_of); + INIT_ID(find_if); + INIT_ID(find_if_not); + INIT_ID(lower_bound); + INIT_ID(upper_bound); + INIT_ID(search); + INIT_ID(search_n); +} + +namespace { + +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); +bool compareToZero(ProgramStateRef State, const NonLoc &Val, + BinaryOperator::Opcode Opc); +bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, + BinaryOperator::Opcode Opc); +std::pair decompose(const SymbolRef Sym); +const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg); +SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef Expr, SymbolRef OldSym, + SymbolRef NewSym); + +bool isIteratorType(const QualType &Type) { + if (Type->isPointerType()) + return true; + + const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); + return isIterator(CRD); +} + +bool isIterator(const CXXRecordDecl *CRD) { + if (!CRD) + return false; + + const auto Name = CRD->getName(); + if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") || + Name.endswith_lower("it"))) + return false; + + bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false, + HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false; + for (const auto *Method : CRD->methods()) { + if (const auto *Ctor = dyn_cast(Method)) { + if (Ctor->isCopyConstructor()) { + HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public; + } + continue; + } + if (const auto *Dtor = dyn_cast(Method)) { + HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public; + continue; + } + if (Method->isCopyAssignmentOperator()) { + HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public; + continue; + } + if (!Method->isOverloadedOperator()) + continue; + const auto OPK = Method->getOverloadedOperator(); + if (OPK == OO_PlusPlus) { + HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0); + HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1); + continue; + } + if (OPK == OO_Star) { + HasDerefOp = (Method->getNumParams() == 0); + continue; + } + } + + return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp && + HasPostIncrOp && HasDerefOp; +} + +bool isComparisonOperator(OverloadedOperatorKind OK) { + return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less || + OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual; +} + +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) + return false; + return IdInfo->getName().endswith_lower("end"); +} + +bool isAssignCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 2) + return false; + return IdInfo->getName() == "assign"; +} + +bool isClearCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + return IdInfo->getName() == "clear"; +} + +bool isPushBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() != 1) + return false; + return IdInfo->getName() == "push_back"; +} + +bool isEmplaceBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1) + return false; + return IdInfo->getName() == "emplace_back"; +} + +bool isPopBackCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + return IdInfo->getName() == "pop_back"; +} + +bool isPushFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() != 1) + return false; + return IdInfo->getName() == "push_front"; +} + +bool isEmplaceFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1) + return false; + return IdInfo->getName() == "emplace_front"; +} + +bool isPopFrontCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() > 0) + return false; + return IdInfo->getName() == "pop_front"; +} + +bool isInsertCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 2 || Func->getNumParams() > 3) + return false; + if (!isIteratorType(Func->getParamDecl(0)->getType())) + return false; + return IdInfo->getName() == "insert"; +} + +bool isEmplaceCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 2) + return false; + if (!isIteratorType(Func->getParamDecl(0)->getType())) + return false; + return IdInfo->getName() == "emplace"; +} + +bool isEraseCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1 || Func->getNumParams() > 2) + return false; + if (!isIteratorType(Func->getParamDecl(0)->getType())) + return false; + if (Func->getNumParams() == 2 && + !isIteratorType(Func->getParamDecl(1)->getType())) + return false; + return IdInfo->getName() == "erase"; +} + +bool isEraseAfterCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + if (Func->getNumParams() < 1 || Func->getNumParams() > 2) + return false; + if (!isIteratorType(Func->getParamDecl(0)->getType())) + return false; + if (Func->getNumParams() == 2 && + !isIteratorType(Func->getParamDecl(1)->getType())) + return false; + return IdInfo->getName() == "erase_after"; +} + +bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } + +bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { + return OK == OO_EqualEqual || OK == OO_ExclaimEqual; +} + +bool isAccessOperator(OverloadedOperatorKind OK) { + return isDereferenceOperator(OK) || isIncrementOperator(OK) || + isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); +} + +bool isDereferenceOperator(OverloadedOperatorKind OK) { + return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || + 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(); + } else if (const auto *SC = dyn_cast(SE)) { + const auto *COE = dyn_cast(SC->getStmt()); + if (!COE) + return BO_Comma; // Extremal value, neither EQ nor NE + if (COE->getOperator() == OO_EqualEqual) { + return BO_EQ; + } else if (COE->getOperator() == OO_ExclaimEqual) { + return BO_NE; + } + return BO_Comma; // Extremal value, neither EQ nor NE + } + return BO_Comma; // Extremal value, neither EQ nor NE +} + +bool hasSubscriptOperator(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->isOverloadedOperator()) + continue; + const auto OPK = Method->getOverloadedOperator(); + if (OPK == OO_Subscript) { + return true; + } + } + return false; +} + +bool frontModifiable(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->getDeclName().isIdentifier()) + continue; + if (Method->getName() == "push_front" || Method->getName() == "pop_front") { + return true; + } + } + return false; +} + +bool backModifiable(const MemRegion *Reg) { + const auto *CRD = getCXXRecordDecl(Reg); + if (!CRD) + return false; + + for (const auto *Method : CRD->methods()) { + if (!Method->getDeclName().isIdentifier()) + continue; + if (Method->getName() == "push_back" || Method->getName() == "pop_back") { + return true; + } + } + return false; +} + +const CXXRecordDecl *getCXXRecordDecl(const MemRegion *Reg) { + QualType Type; + if (const auto *TVReg = Reg->getAs()) { + Type = TVReg->getValueType(); + } else if (const auto *SymReg = Reg->getAs()) { + Type = SymReg->getSymbol()->getType(); + } else { + return nullptr; + } + + if (const auto *RefT = Type->getAs()) { + Type = RefT->getPointeeType(); + } + + return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); +} + +const RegionOrSymbol getRegionOrSymbol(const SVal &Val) { + if (const auto Reg = Val.getAsRegion()) { + return Reg; + } else if (const auto Sym = Val.getAsSymbol()) { + return Sym; + } else if (const auto LCVal = Val.getAs()) { + return LCVal->getRegion(); + } + return RegionOrSymbol(); +} + +const ProgramStateRef processComparison(ProgramStateRef State, + RegionOrSymbol LVal, + RegionOrSymbol RVal, bool Equal) { + const auto *LPos = getIteratorPosition(State, LVal); + const auto *RPos = getIteratorPosition(State, RVal); + if (LPos && !RPos) { + State = adjustIteratorPosition(State, RVal, *LPos, Equal); + } else if (!LPos && RPos) { + State = adjustIteratorPosition(State, LVal, *RPos, Equal); + } else if (LPos && RPos) { + State = relateIteratorPositions(State, *LPos, *RPos, Equal); + } + return State; +} + +const ProgramStateRef saveComparison(ProgramStateRef State, + const SymExpr *Condition, const SVal &LVal, + const SVal &RVal, bool Eq) { + const auto Left = getRegionOrSymbol(LVal); + const auto Right = getRegionOrSymbol(RVal); + if (!Left || !Right) + return State; + return State->set(Condition, + IteratorComparison(Left, Right, Eq)); +} + +const IteratorComparison *loadComparison(ProgramStateRef State, + const SymExpr *Condition) { + 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) + return nullptr; + + 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 + const auto *CDataPtr = getContainerData(State, Cont); + if (CDataPtr) { + if (CDataPtr->getEnd()) { + return State; + } else { + const auto CData = CDataPtr->newEnd(Sym); + return setContainerData(State, Cont, CData); + } + } else { + const auto CData = ContainerData::fromEnd(Sym); + return setContainerData(State, Cont, CData); + } +} + +const ContainerData *getContainerData(ProgramStateRef State, + const MemRegion *Cont) { + return State->get(Cont); +} + +ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, + const ContainerData &CData) { + return State->set(Cont, CData); +} + +const IteratorPosition *getIteratorPosition(ProgramStateRef State, + const SVal &Val) { + if (const auto Reg = Val.getAsRegion()) { + return State->get(Reg); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->get(Sym); + } else if (const auto LCVal = Val.getAs()) { + return State->get(LCVal->getRegion()); + } + return nullptr; +} + +const IteratorPosition *getIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym) { + if (RegOrSym.is()) { + return State->get(RegOrSym.get()); + } else if (RegOrSym.is()) { + return State->get(RegOrSym.get()); + } + return nullptr; +} + +ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, + const IteratorPosition &Pos) { + if (const auto Reg = Val.getAsRegion()) { + return State->set(Reg, Pos); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->set(Sym, Pos); + } else if (const auto LCVal = Val.getAs()) { + return State->set(LCVal->getRegion(), Pos); + } + return nullptr; +} + +ProgramStateRef setIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + const IteratorPosition &Pos) { + if (RegOrSym.is()) { + return State->set(RegOrSym.get(), + Pos); + } else if (RegOrSym.is()) { + return State->set(RegOrSym.get(), Pos); + } + return nullptr; +} + +ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val) { + if (const auto Reg = Val.getAsRegion()) { + return State->remove(Reg); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->remove(Sym); + } else if (const auto LCVal = Val.getAs()) { + return State->remove(LCVal->getRegion()); + } + return nullptr; +} + +ProgramStateRef adjustIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + const IteratorPosition &Pos, + bool Equal) { + if (Equal) { + return setIteratorPosition(State, RegOrSym, Pos); + } else { + return State; + } +} + +ProgramStateRef relateIteratorPositions(ProgramStateRef State, + const IteratorPosition &Pos1, + const IteratorPosition &Pos2, + bool Equal) { + // 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()), + nonloc::SymbolVal(Pos2.getOffset()), SVB.getConditionType()) + .getAs(); + if (comparison) { + 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; +} + +template +ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, + Process Proc) { + auto RegionMap = State->get(); + for (const auto Reg : RegionMap) { + if (Cond(Reg.second)) { + State = setIteratorPosition(State, Reg.first, Proc(Reg.second)); + } + } + + auto SymbolMap = State->get(); + for (const auto Sym : SymbolMap) { + if (Cond(Sym.second)) { + State = setIteratorPosition(State, Sym.first, Proc(Sym.second)); + } + } + + return State; +} + +ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont) { + auto MatchCont = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont; + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, MatchCont, Invalidate); +} + +ProgramStateRef +invalidateAllIteratorPositionsExcept(ProgramStateRef State, + const MemRegion *Cont, SymbolRef Offset, + BinaryOperator::Opcode Opc) { + auto MatchContAndCompare = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont && + !compare(State, Pos.getOffset(), Offset, Opc); + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, MatchContAndCompare, Invalidate); +} + +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset, + BinaryOperator::Opcode Opc) { + auto Compare = [&](const IteratorPosition &Pos) { + return compare(State, Pos.getOffset(), Offset, Opc); + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, Compare, Invalidate); +} + +ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, + SymbolRef Offset1, + BinaryOperator::Opcode Opc1, + SymbolRef Offset2, + BinaryOperator::Opcode Opc2) { + auto Compare = [&](const IteratorPosition &Pos) { + return compare(State, Pos.getOffset(), Offset1, Opc1) && + compare(State, Pos.getOffset(), Offset2, Opc2); + }; + auto Invalidate = [&](const IteratorPosition &Pos) { + return Pos.invalidate(); + }; + return processIteratorPositions(State, Compare, Invalidate); +} + +ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont) { + auto MatchCont = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont; + }; + auto ReAssign = [&](const IteratorPosition &Pos) { + return Pos.reAssign(NewCont); + }; + return processIteratorPositions(State, MatchCont, ReAssign); +} + +ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, + const MemRegion *Cont, + const MemRegion *NewCont, + SymbolRef Offset, + BinaryOperator::Opcode Opc) { + auto MatchContAndCompare = [&](const IteratorPosition &Pos) { + return Pos.getContainer() == Cont && + !compare(State, Pos.getOffset(), Offset, Opc); + }; + auto ReAssign = [&](const IteratorPosition &Pos) { + return Pos.reAssign(NewCont); + }; + return processIteratorPositions(State, MatchContAndCompare, ReAssign); +} + +ProgramStateRef replaceSymbolInIteratorPositionsIf( + ProgramStateRef State, SymbolManager &SymMgr, SymbolRef OldSym, + SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { + auto LessThanEnd = [&](const IteratorPosition &Pos) { + return compare(State, Pos.getOffset(), CondSym, Opc); + }; + auto ReplaceSymbol = [&](const IteratorPosition &Pos) { + return Pos.setTo(replaceSymbol(SymMgr, Pos.getOffset(), OldSym, NewSym)); + }; + return processIteratorPositions(State, LessThanEnd, ReplaceSymbol); +} + +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); + if (!CData) + return false; + + // 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)) { + return true; + } + } + + return false; +} + +bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_LT); +} + +bool isGreaterOrEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { + return compare(State, Sym1, Sym2, BO_GE); +} + +bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, + BinaryOperator::Opcode Opc) { + 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, BO_EQ, nonloc::SymbolVal(Sym1), + nonloc::SymbolVal(Sym2), SVB.getConditionType()) + .getAs(); + + // 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; + } + + auto &BVF = newState->getSymbolManager().getBasicVals(); + return BVF.evalAPSInt(Opc, Int1, Int2)->getExtValue(); +} + +SymbolRef replaceSymbol(SymbolManager &SymMgr, SymbolRef OrigExpr, + SymbolRef OldExpr, SymbolRef NewSym) { + // We have a symbolic expression in the format of A+n, where we want to + // replace A+m with B, so the result becomes B+k, where k==n-m. + SymbolRef OrigSym, OldSym; + llvm::APSInt OrigInt, OldInt; + std::tie(OrigSym, OrigInt) = decompose(OrigExpr); + std::tie(OldSym, OldInt) = decompose(OldExpr); + if (OrigSym == OldSym) { + auto NewInt = OrigInt - OldInt; + if (NewInt == 0) { + return NewSym; + } else { + auto OpCode = (NewInt > 0) ? BO_Add : BO_Sub; + auto &BVF = SymMgr.getBasicVals(); + auto &AbsInt = + (NewInt > 0) ? BVF.getValue(NewInt) : BVF.getValue(-NewInt); + return SymMgr.getSymIntExpr(NewSym, OpCode, AbsInt, OrigExpr->getType()); + } + } else { + return OrigExpr; + } +} + +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 + +#define REGISTER_CHECKER(name) \ + void ento::register##name(CheckerManager &Mgr) { \ + auto *checker = Mgr.registerChecker(); \ + checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \ + checker->CheckNames[IteratorChecker::CK_##name] = \ + Mgr.getCurrentCheckName(); \ + } + +REGISTER_CHECKER(IteratorRangeChecker) +REGISTER_CHECKER(MismatchedIteratorChecker) +REGISTER_CHECKER(InvalidatedIteratorChecker) Index: lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp =================================================================== --- lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp +++ /dev/null @@ -1,840 +0,0 @@ -//===-- IteratorPastEndChecker.cpp --------------------------------*- C++ -*--// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Defines a checker for using iterators outside their range (past end). Usage -// means here dereferencing, incrementing etc. -// -//===----------------------------------------------------------------------===// - -#include "ClangSACheckers.h" -#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" -#include "clang/StaticAnalyzer/Core/Checker.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" - -#include - -using namespace clang; -using namespace ento; - -namespace { -struct IteratorPosition { -private: - enum Kind { InRange, OutofRange } K; - IteratorPosition(Kind InK) : K(InK) {} - -public: - bool isInRange() const { return K == InRange; } - bool isOutofRange() const { return K == OutofRange; } - - static IteratorPosition getInRange() { return IteratorPosition(InRange); } - static IteratorPosition getOutofRange() { - return IteratorPosition(OutofRange); - } - - bool operator==(const IteratorPosition &X) const { return K == X.K; } - bool operator!=(const IteratorPosition &X) const { return K != X.K; } - void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(K); } -}; - -typedef llvm::PointerUnion RegionOrSymbol; - -struct IteratorComparison { -private: - RegionOrSymbol Left, Right; - bool Equality; - -public: - IteratorComparison(RegionOrSymbol L, RegionOrSymbol R, bool Eq) - : Left(L), Right(R), Equality(Eq) {} - - RegionOrSymbol getLeft() const { return Left; } - RegionOrSymbol getRight() const { return Right; } - bool isEquality() const { return Equality; } - bool operator==(const IteratorComparison &X) const { - return Left == X.Left && Right == X.Right && Equality == X.Equality; - } - bool operator!=(const IteratorComparison &X) const { - return Left != X.Left || Right != X.Right || Equality != X.Equality; - } - void Profile(llvm::FoldingSetNodeID &ID) const { ID.AddInteger(Equality); } -}; - -class IteratorPastEndChecker - : public Checker< - check::PreCall, check::PostCall, check::PreStmt, - check::PostStmt, check::PostStmt, - check::PostStmt, check::BeginFunction, - check::DeadSymbols, eval::Assume, eval::Call> { - mutable IdentifierInfo *II_find = nullptr, - *II_find_end = nullptr, *II_find_first_of = nullptr, - *II_find_if = nullptr, *II_find_if_not = nullptr, - *II_lower_bound = nullptr, *II_upper_bound = nullptr, - *II_search = nullptr, *II_search_n = nullptr; - - std::unique_ptr PastEndBugType; - - void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, - const SVal &RVal, OverloadedOperatorKind Op) const; - void handleAccess(CheckerContext &C, const SVal &Val) const; - void handleDecrement(CheckerContext &C, const SVal &Val) const; - void handleEnd(CheckerContext &C, const SVal &RetVal) const; - - bool evalFind(CheckerContext &C, const CallExpr *CE) const; - bool evalFindEnd(CheckerContext &C, const CallExpr *CE) const; - bool evalFindFirstOf(CheckerContext &C, const CallExpr *CE) const; - bool evalFindIf(CheckerContext &C, const CallExpr *CE) const; - bool evalFindIfNot(CheckerContext &C, const CallExpr *CE) const; - bool evalLowerBound(CheckerContext &C, const CallExpr *CE) const; - bool evalUpperBound(CheckerContext &C, const CallExpr *CE) const; - bool evalSearch(CheckerContext &C, const CallExpr *CE) const; - bool evalSearchN(CheckerContext &C, const CallExpr *CE) const; - void Find(CheckerContext &C, const CallExpr *CE) const; - - void reportPastEndBug(const StringRef &Message, const SVal &Val, - CheckerContext &C, ExplodedNode *ErrNode) const; - void initIdentifiers(ASTContext &Ctx) const; - -public: - IteratorPastEndChecker(); - - 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 checkBeginFunction(CheckerContext &C) const; - void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; - void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const; - void checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const; - void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; - ProgramStateRef evalAssume(ProgramStateRef State, SVal Cond, - bool Assumption) const; - bool evalCall(const CallExpr *CE, CheckerContext &C) const; -}; -} - -REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition) -REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *, - IteratorPosition) - -REGISTER_MAP_WITH_PROGRAMSTATE(IteratorComparisonMap, const SymExpr *, - IteratorComparison) - -#define INIT_ID(Id) \ - if (!II_##Id) \ - II_##Id = &Ctx.Idents.get(#Id) - -namespace { - -bool isIteratorType(const QualType &Type); -bool isIterator(const CXXRecordDecl *CRD); -bool isEndCall(const FunctionDecl *Func); -bool isSimpleComparisonOperator(OverloadedOperatorKind OK); -bool isAccessOperator(OverloadedOperatorKind OK); -bool isDecrementOperator(OverloadedOperatorKind OK); -BinaryOperator::Opcode getOpcode(const SymExpr *SE); -const RegionOrSymbol getRegionOrSymbol(const SVal &Val); -const ProgramStateRef processComparison(ProgramStateRef State, - RegionOrSymbol LVal, - RegionOrSymbol RVal, bool Equal); -const ProgramStateRef saveComparison(ProgramStateRef State, - const SymExpr *Condition, const SVal &LVal, - const SVal &RVal, bool Eq); -const IteratorComparison *loadComparison(ProgramStateRef State, - const SymExpr *Condition); -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - const SVal &Val); -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym); -ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, - IteratorPosition Pos); -ProgramStateRef setIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym, - IteratorPosition Pos); -ProgramStateRef adjustIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym, - IteratorPosition Pos, bool Equal); -bool contradictingIteratorPositions(IteratorPosition Pos1, - IteratorPosition Pos2, bool Equal); -} - -IteratorPastEndChecker::IteratorPastEndChecker() { - PastEndBugType.reset( - new BugType(this, "Iterator Past End", "Misuse of STL APIs")); - PastEndBugType->setSuppressOnSink(true); -} - -void IteratorPastEndChecker::checkPreCall(const CallEvent &Call, - CheckerContext &C) const { - // Check for access past end - const auto *Func = Call.getDecl()->getAsFunction(); - if (!Func) - return; - if (Func->isOverloadedOperator()) { - if (isAccessOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast(&Call)) { - handleAccess(C, InstCall->getCXXThisVal()); - } else { - handleAccess(C, Call.getArgSVal(0)); - } - } - } -} - -void IteratorPastEndChecker::checkPostCall(const CallEvent &Call, - CheckerContext &C) const { - // Record end() iterators, iterator decrementation and comparison - const auto *Func = Call.getDecl()->getAsFunction(); - if (!Func) - return; - if (Func->isOverloadedOperator()) { - const auto Op = Func->getOverloadedOperator(); - if (isSimpleComparisonOperator(Op)) { - if (Func->isCXXInstanceMember()) { - const auto &InstCall = static_cast(Call); - handleComparison(C, InstCall.getReturnValue(), InstCall.getCXXThisVal(), - InstCall.getArgSVal(0), Op); - } else { - handleComparison(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1), Op); - } - } else if (isDecrementOperator(Func->getOverloadedOperator())) { - if (Func->isCXXInstanceMember()) { - const auto &InstCall = static_cast(Call); - handleDecrement(C, InstCall.getCXXThisVal()); - } else { - handleDecrement(C, Call.getArgSVal(0)); - } - } - } else if (Func->isCXXInstanceMember()) { - if (!isEndCall(Func)) - return; - if (!isIteratorType(Call.getResultType())) - return; - handleEnd(C, Call.getReturnValue()); - } -} - -void IteratorPastEndChecker::checkPreStmt(const CXXOperatorCallExpr *COCE, - CheckerContext &C) const { - const auto *ThisExpr = COCE->getArg(0); - - auto State = C.getState(); - const auto *LCtx = C.getPredecessor()->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 IteratorPastEndChecker::checkBeginFunction(CheckerContext &C) const { - // Copy state of iterator arguments to iterator parameters - auto State = C.getState(); - const auto *LCtx = C.getLocationContext(); - - const auto *Site = cast(LCtx)->getCallSite(); - if (!Site) - return; - - const auto *FD = dyn_cast(LCtx->getDecl()); - if (!FD) - return; - - const auto *CE = dyn_cast(Site); - if (!CE) - return; - - bool Change = false; - int idx = 0; - for (const auto P : FD->parameters()) { - auto Param = State->getLValue(P, LCtx); - auto Arg = State->getSVal(CE->getArg(idx++), LCtx->getParent()); - const auto *Pos = getIteratorPosition(State, Arg); - if (!Pos) - continue; - State = setIteratorPosition(State, Param, *Pos); - Change = true; - } - if (Change) { - C.addTransition(State); - } -} - -void IteratorPastEndChecker::checkPostStmt(const CXXConstructExpr *CCE, - CheckerContext &C) const { - // Transfer iterator state in case of copy or move by constructor - const auto *ctr = CCE->getConstructor(); - if (!ctr->isCopyOrMoveConstructor()) - return; - const auto *RHSExpr = CCE->getArg(0); - - auto State = C.getState(); - const auto *LCtx = C.getLocationContext(); - - const auto RetVal = State->getSVal(CCE, LCtx); - - const auto RHSVal = State->getSVal(RHSExpr, LCtx); - const auto *RHSPos = getIteratorPosition(State, RHSVal); - if (!RHSPos) - return; - State = setIteratorPosition(State, RetVal, *RHSPos); - C.addTransition(State); -} - -void IteratorPastEndChecker::checkPostStmt(const DeclStmt *DS, - CheckerContext &C) const { - // Transfer iterator state to new variable declaration - for (const auto *D : DS->decls()) { - const auto *VD = dyn_cast(D); - if (!VD || !VD->hasInit()) - continue; - - auto State = C.getState(); - const auto *LCtx = C.getPredecessor()->getLocationContext(); - const auto *Pos = - getIteratorPosition(State, State->getSVal(VD->getInit(), LCtx)); - if (!Pos) - continue; - State = setIteratorPosition(State, State->getLValue(VD, LCtx), *Pos); - C.addTransition(State); - } -} - -void IteratorPastEndChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const { - /* Transfer iterator state for to temporary objects */ - auto State = C.getState(); - const auto *LCtx = C.getPredecessor()->getLocationContext(); - const auto *Pos = - getIteratorPosition(State, State->getSVal(MTE->GetTemporaryExpr(), LCtx)); - if (!Pos) - return; - State = setIteratorPosition(State, State->getSVal(MTE, LCtx), *Pos); - C.addTransition(State); -} - -void IteratorPastEndChecker::checkDeadSymbols(SymbolReaper &SR, - CheckerContext &C) const { - auto State = C.getState(); - - auto RegionMap = State->get(); - for (const auto Reg : RegionMap) { - if (!SR.isLiveRegion(Reg.first)) { - State = State->remove(Reg.first); - } - } - - auto SymbolMap = State->get(); - for (const auto Sym : SymbolMap) { - if (SR.isDead(Sym.first)) { - State = State->remove(Sym.first); - } - } - - auto ComparisonMap = State->get(); - for (const auto Comp : ComparisonMap) { - if (SR.isDead(Comp.first)) { - State = State->remove(Comp.first); - } - } -} - -ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State, - SVal Cond, - bool Assumption) const { - // Load recorded comparison and transfer iterator state between sides - // according to comparison operator and assumption - const auto *SE = Cond.getAsSymExpr(); - if (!SE) - return State; - - auto Opc = getOpcode(SE); - if (Opc != BO_EQ && Opc != BO_NE) - return State; - - bool Negated = false; - const auto *Comp = loadComparison(State, SE); - if (!Comp) { - // Try negated comparison, which is a SymExpr to 0 integer comparison - const auto *SIE = dyn_cast(SE); - if (!SIE) - return State; - - if (SIE->getRHS() != 0) - return State; - - SE = SIE->getLHS(); - Negated = SIE->getOpcode() == BO_EQ; // Equal to zero means negation - Opc = getOpcode(SE); - if (Opc != BO_EQ && Opc != BO_NE) - return State; - - Comp = loadComparison(State, SE); - if (!Comp) - return State; - } - - return processComparison(State, Comp->getLeft(), Comp->getRight(), - (Comp->isEquality() == Assumption) != Negated); -} - -// FIXME: Evaluation of these STL calls should be moved to StdCLibraryFunctions -// checker (see patch r284960) or another similar checker for C++ STL -// functions (e.g. StdCXXLibraryFunctions or StdCppLibraryFunctions). -bool IteratorPastEndChecker::evalCall(const CallExpr *CE, - CheckerContext &C) const { - const FunctionDecl *FD = C.getCalleeDecl(CE); - if (!FD) - return false; - - ASTContext &Ctx = C.getASTContext(); - initIdentifiers(Ctx); - - if (FD->getKind() == Decl::Function) { - if (FD->isInStdNamespace()) { - if (FD->getIdentifier() == II_find) { - return evalFind(C, CE); - } else if (FD->getIdentifier() == II_find_end) { - return evalFindEnd(C, CE); - } else if (FD->getIdentifier() == II_find_first_of) { - return evalFindFirstOf(C, CE); - } else if (FD->getIdentifier() == II_find_if) { - return evalFindIf(C, CE); - } else if (FD->getIdentifier() == II_find_if_not) { - return evalFindIfNot(C, CE); - } else if (FD->getIdentifier() == II_upper_bound) { - return evalUpperBound(C, CE); - } else if (FD->getIdentifier() == II_lower_bound) { - return evalLowerBound(C, CE); - } else if (FD->getIdentifier() == II_search) { - return evalSearch(C, CE); - } else if (FD->getIdentifier() == II_search_n) { - return evalSearchN(C, CE); - } - } - } - - return false; -} - -void IteratorPastEndChecker::handleComparison(CheckerContext &C, - const SVal &RetVal, - const SVal &LVal, - const SVal &RVal, - OverloadedOperatorKind Op) const { - // Record the operands and the operator of the comparison for the next - // evalAssume, if the result is a symbolic expression. If it is a concrete - // value (only one branch is possible), then transfer the state between - // the operands according to the operator and the result - auto State = C.getState(); - if (const auto *Condition = RetVal.getAsSymbolicExpression()) { - const auto *LPos = getIteratorPosition(State, LVal); - const auto *RPos = getIteratorPosition(State, RVal); - if (!LPos && !RPos) - return; - State = saveComparison(State, Condition, LVal, RVal, Op == OO_EqualEqual); - C.addTransition(State); - } else if (const auto TruthVal = RetVal.getAs()) { - if ((State = processComparison( - State, getRegionOrSymbol(LVal), getRegionOrSymbol(RVal), - (Op == OO_EqualEqual) == (TruthVal->getValue() != 0)))) { - C.addTransition(State); - } else { - C.generateSink(State, C.getPredecessor()); - } - } -} - -void IteratorPastEndChecker::handleAccess(CheckerContext &C, - const SVal &Val) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos && Pos->isOutofRange()) { - auto *N = C.generateNonFatalErrorNode(State); - if (!N) { - return; - } - reportPastEndBug("Iterator accessed past its end.", Val, C, N); - } -} - -void IteratorPastEndChecker::handleDecrement(CheckerContext &C, - const SVal &Val) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos && Pos->isOutofRange()) { - State = setIteratorPosition(State, Val, IteratorPosition::getInRange()); - // FIXME: We could also check for iterators ahead of their beginnig in the - // future, but currently we do not care for such errors. We also - // assume that the iterator is not past its end by more then one - // position. - C.addTransition(State); - } -} - -void IteratorPastEndChecker::handleEnd(CheckerContext &C, - const SVal &RetVal) const { - auto State = C.getState(); - State = setIteratorPosition(State, RetVal, IteratorPosition::getOutofRange()); - C.addTransition(State); -} - -bool IteratorPastEndChecker::evalFind(CheckerContext &C, - const CallExpr *CE) const { - if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalFindEnd(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType()) && - isIteratorType(CE->getArg(2)->getType()) && - isIteratorType(CE->getArg(3)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalFindFirstOf(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType()) && - isIteratorType(CE->getArg(2)->getType()) && - isIteratorType(CE->getArg(3)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalFindIf(CheckerContext &C, - const CallExpr *CE) const { - if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalFindIfNot(CheckerContext &C, - const CallExpr *CE) const { - if (CE->getNumArgs() == 3 && isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalLowerBound(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalUpperBound(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 3 || CE->getNumArgs() == 4) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalSearch(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType()) && - isIteratorType(CE->getArg(2)->getType()) && - isIteratorType(CE->getArg(3)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -bool IteratorPastEndChecker::evalSearchN(CheckerContext &C, - const CallExpr *CE) const { - if ((CE->getNumArgs() == 4 || CE->getNumArgs() == 5) && - isIteratorType(CE->getArg(0)->getType()) && - isIteratorType(CE->getArg(1)->getType())) { - Find(C, CE); - return true; - } - return false; -} - -void IteratorPastEndChecker::Find(CheckerContext &C, const CallExpr *CE) const { - auto state = C.getState(); - auto &svalBuilder = C.getSValBuilder(); - const auto *LCtx = C.getLocationContext(); - - auto RetVal = svalBuilder.conjureSymbolVal(nullptr, CE, LCtx, C.blockCount()); - auto SecondParam = state->getSVal(CE->getArg(1), LCtx); - - auto stateFound = state->BindExpr(CE, LCtx, RetVal); - auto stateNotFound = state->BindExpr(CE, LCtx, SecondParam); - - C.addTransition(stateFound); - C.addTransition(stateNotFound); -} - -void IteratorPastEndChecker::reportPastEndBug(const StringRef &Message, - const SVal &Val, - CheckerContext &C, - ExplodedNode *ErrNode) const { - auto R = llvm::make_unique(*PastEndBugType, Message, ErrNode); - R->markInteresting(Val); - C.emitReport(std::move(R)); -} - -void IteratorPastEndChecker::initIdentifiers(ASTContext &Ctx) const { - INIT_ID(find); - INIT_ID(find_end); - INIT_ID(find_first_of); - INIT_ID(find_if); - INIT_ID(find_if_not); - INIT_ID(lower_bound); - INIT_ID(upper_bound); - INIT_ID(search); - INIT_ID(search_n); -} - -namespace { - -bool isIteratorType(const QualType &Type) { - if (Type->isPointerType()) - return true; - - const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); - return isIterator(CRD); -} - -bool isIterator(const CXXRecordDecl *CRD) { - if (!CRD) - return false; - - const auto Name = CRD->getName(); - if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") || - Name.endswith_lower("it"))) - return false; - - bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false, - HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false; - for (const auto *Method : CRD->methods()) { - if (const auto *Ctor = dyn_cast(Method)) { - if (Ctor->isCopyConstructor()) { - HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public; - } - continue; - } - if (const auto *Dtor = dyn_cast(Method)) { - HasDtor = !Dtor->isDeleted() && Dtor->getAccess() == AS_public; - continue; - } - if (Method->isCopyAssignmentOperator()) { - HasCopyAssign = !Method->isDeleted() && Method->getAccess() == AS_public; - continue; - } - if (!Method->isOverloadedOperator()) - continue; - const auto OPK = Method->getOverloadedOperator(); - if (OPK == OO_PlusPlus) { - HasPreIncrOp = HasPreIncrOp || (Method->getNumParams() == 0); - HasPostIncrOp = HasPostIncrOp || (Method->getNumParams() == 1); - continue; - } - if (OPK == OO_Star) { - HasDerefOp = (Method->getNumParams() == 0); - continue; - } - } - - return HasCopyCtor && HasCopyAssign && HasDtor && HasPreIncrOp && - HasPostIncrOp && HasDerefOp; -} - -bool isEndCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - return IdInfo->getName().endswith_lower("end"); -} - -bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { - return OK == OO_EqualEqual || OK == OO_ExclaimEqual; -} - -bool isAccessOperator(OverloadedOperatorKind OK) { - return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || - OK == OO_Plus || OK == OO_PlusEqual || OK == OO_PlusPlus || - OK == OO_Subscript; -} - -bool isDecrementOperator(OverloadedOperatorKind OK) { - return OK == OO_MinusEqual || OK == OO_MinusMinus; -} - -BinaryOperator::Opcode getOpcode(const SymExpr *SE) { - if (const auto *BSE = dyn_cast(SE)) { - return BSE->getOpcode(); - } else if (const auto *SC = dyn_cast(SE)) { - const auto *COE = dyn_cast(SC->getStmt()); - if (!COE) - return BO_Comma; // Extremal value, neither EQ nor NE - if (COE->getOperator() == OO_EqualEqual) { - return BO_EQ; - } else if (COE->getOperator() == OO_ExclaimEqual) { - return BO_NE; - } - return BO_Comma; // Extremal value, neither EQ nor NE - } - return BO_Comma; // Extremal value, neither EQ nor NE -} - -const RegionOrSymbol getRegionOrSymbol(const SVal &Val) { - if (const auto Reg = Val.getAsRegion()) { - return Reg; - } else if (const auto Sym = Val.getAsSymbol()) { - return Sym; - } else if (const auto LCVal = Val.getAs()) { - return LCVal->getRegion(); - } - return RegionOrSymbol(); -} - -const ProgramStateRef processComparison(ProgramStateRef State, - RegionOrSymbol LVal, - RegionOrSymbol RVal, bool Equal) { - const auto *LPos = getIteratorPosition(State, LVal); - const auto *RPos = getIteratorPosition(State, RVal); - if (LPos && !RPos) { - State = adjustIteratorPosition(State, RVal, *LPos, Equal); - } else if (!LPos && RPos) { - State = adjustIteratorPosition(State, LVal, *RPos, Equal); - } else if (LPos && RPos) { - if (contradictingIteratorPositions(*LPos, *RPos, Equal)) { - return nullptr; - } - } - return State; -} - -const ProgramStateRef saveComparison(ProgramStateRef State, - const SymExpr *Condition, const SVal &LVal, - const SVal &RVal, bool Eq) { - const auto Left = getRegionOrSymbol(LVal); - const auto Right = getRegionOrSymbol(RVal); - if (!Left || !Right) - return State; - return State->set(Condition, - IteratorComparison(Left, Right, Eq)); -} - -const IteratorComparison *loadComparison(ProgramStateRef State, - const SymExpr *Condition) { - return State->get(Condition); -} - -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - const SVal &Val) { - if (const auto Reg = Val.getAsRegion()) { - return State->get(Reg); - } else if (const auto Sym = Val.getAsSymbol()) { - return State->get(Sym); - } else if (const auto LCVal = Val.getAs()) { - return State->get(LCVal->getRegion()); - } - return nullptr; -} - -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym) { - if (RegOrSym.is()) { - return State->get(RegOrSym.get()); - } else if (RegOrSym.is()) { - return State->get(RegOrSym.get()); - } - return nullptr; -} - -ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, - IteratorPosition Pos) { - if (const auto Reg = Val.getAsRegion()) { - return State->set(Reg, Pos); - } else if (const auto Sym = Val.getAsSymbol()) { - return State->set(Sym, Pos); - } else if (const auto LCVal = Val.getAs()) { - return State->set(LCVal->getRegion(), Pos); - } - return nullptr; -} - -ProgramStateRef setIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym, - IteratorPosition Pos) { - if (RegOrSym.is()) { - return State->set(RegOrSym.get(), - Pos); - } else if (RegOrSym.is()) { - return State->set(RegOrSym.get(), Pos); - } - return nullptr; -} - -ProgramStateRef adjustIteratorPosition(ProgramStateRef State, - RegionOrSymbol RegOrSym, - IteratorPosition Pos, bool Equal) { - - if ((Pos.isInRange() && Equal) || (Pos.isOutofRange() && !Equal)) { - return setIteratorPosition(State, RegOrSym, IteratorPosition::getInRange()); - } else if (Pos.isOutofRange() && Equal) { - return setIteratorPosition(State, RegOrSym, - IteratorPosition::getOutofRange()); - } else { - return State; - } -} - -bool contradictingIteratorPositions(IteratorPosition Pos1, - IteratorPosition Pos2, bool Equal) { - return ((Pos1 != Pos2) && Equal) || - ((Pos1.isOutofRange() && Pos2.isOutofRange()) && !Equal); -} -} - -void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) { - Mgr.registerChecker(); -} Index: test/Analysis/Inputs/system-header-simulator-cxx.h =================================================================== --- test/Analysis/Inputs/system-header-simulator-cxx.h +++ test/Analysis/Inputs/system-header-simulator-cxx.h @@ -8,18 +8,112 @@ typedef unsigned char uint8_t; typedef __typeof__(sizeof(int)) size_t; +typedef __typeof__((char*)0-(char*)0) ptrdiff_t; void *memmove(void *s1, const void *s2, size_t n); -template struct __iterator { - typedef __iterator iterator; - typedef __iterator const_iterator; +namespace std { + struct input_iterator_tag { }; + struct output_iterator_tag { }; + struct forward_iterator_tag : public input_iterator_tag { }; + struct bidirectional_iterator_tag : public forward_iterator_tag { }; + struct random_access_iterator_tag : public bidirectional_iterator_tag { }; + + template struct iterator_traits { + typedef typename Iterator::difference_type difference_type; + typedef typename Iterator::value_type value_type; + typedef typename Iterator::pointer pointer; + typedef typename Iterator::reference reference; + typedef typename Iterator::iterator_category iterator_category; + }; +} - __iterator(const Ptr p) : ptr(p) {} +template struct __vector_iterator { + typedef __vector_iterator iterator; + typedef __vector_iterator const_iterator; + + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef Ptr pointer; + typedef Ref reference; + typedef std::random_access_iterator_tag iterator_category; + + __vector_iterator(const Ptr p = 0) : ptr(p) {} + __vector_iterator(const iterator &rhs): ptr(rhs.base()) {} + __vector_iterator operator++() { ++ ptr; return *this; } + __vector_iterator operator++(int) { + auto tmp = *this; + ++ ptr; + return tmp; + } + __vector_iterator operator--() { -- ptr; return *this; } + __vector_iterator operator--(int) { + auto tmp = *this; -- ptr; + return tmp; + } + __vector_iterator operator+(difference_type n) { + return ptr + n; + } + __vector_iterator operator-(difference_type n) { + return ptr - n; + } + __vector_iterator operator+=(difference_type n) { + return ptr += n; + } + __vector_iterator operator-=(difference_type n) { + return ptr -= n; + } + + Ref operator*() const { return *ptr; } + Ptr operator->() const { return *ptr; } + + bool operator==(const iterator &rhs) const { return ptr == rhs.ptr; } + bool operator==(const const_iterator &rhs) const { return ptr == rhs.ptr; } + + bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; } + bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; } + + const Ptr& base() const { return ptr; } + +private: + Ptr ptr; +}; + +template struct __deque_iterator { + typedef __deque_iterator iterator; + typedef __deque_iterator const_iterator; + + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef Ptr pointer; + typedef Ref reference; + typedef std::random_access_iterator_tag iterator_category; + + __deque_iterator(const Ptr p = 0) : ptr(p) {} + __deque_iterator(const iterator &rhs): ptr(rhs.base()) {} + __deque_iterator operator++() { ++ ptr; return *this; } + __deque_iterator operator++(int) { + auto tmp = *this; + ++ ptr; + return tmp; + } + __deque_iterator operator--() { -- ptr; return *this; } + __deque_iterator operator--(int) { + auto tmp = *this; -- ptr; + return tmp; + } + __deque_iterator operator+(difference_type n) { + return ptr + n; + } + __deque_iterator operator-(difference_type n) { + return ptr - n; + } + __deque_iterator operator+=(difference_type n) { + return ptr += n; + } + __deque_iterator operator-=(difference_type n) { + return ptr -= n; + } - __iterator operator++() { return *this; } - __iterator operator++(int) { return *this; } - __iterator operator--() { return *this; } - __iterator operator--(int) { return *this; } Ref operator*() const { return *ptr; } Ptr operator->() const { return *ptr; } @@ -29,10 +123,85 @@ bool operator!=(const iterator &rhs) const { return ptr != rhs.ptr; } bool operator!=(const const_iterator &rhs) const { return ptr != rhs.ptr; } + const Ptr& base() const { return ptr; } + private: Ptr ptr; }; +template struct __list_iterator { + typedef __list_iterator iterator; + typedef __list_iterator const_iterator; + + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef Ptr pointer; + typedef Ref reference; + typedef std::bidirectional_iterator_tag iterator_category; + + __list_iterator(T* it = 0) : item(it) {} + __list_iterator(const iterator &rhs): item(rhs.base()) {} + __list_iterator operator++() { item = item->next; return *this; } + __list_iterator operator++(int) { + auto tmp = *this; + item = item->next; + return tmp; + } + __list_iterator operator--() { item = item->prev; return *this; } + __list_iterator operator--(int) { + auto tmp = *this; + item = item->prev; + return tmp; + } + + Ref operator*() const { return item->data; } + Ptr operator->() const { return item->data; } + + bool operator==(const iterator &rhs) const { return item == rhs->item; } + bool operator==(const const_iterator &rhs) const { return item == rhs->item; } + + bool operator!=(const iterator &rhs) const { return item != rhs->item; } + bool operator!=(const const_iterator &rhs) const { return item != rhs->item; } + + const T* &base() const { return item; } + +private: + T* item; +}; + +template struct __fwdl_iterator { + typedef __fwdl_iterator iterator; + typedef __fwdl_iterator const_iterator; + + typedef ptrdiff_t difference_type; + typedef T value_type; + typedef Ptr pointer; + typedef Ref reference; + typedef std::forward_iterator_tag iterator_category; + + __fwdl_iterator(T* it = 0) : item(it) {} + __fwdl_iterator(const iterator &rhs): item(rhs.base()) {} + __fwdl_iterator operator++() { item = item->next; return *this; } + __fwdl_iterator operator++(int) { + auto tmp = *this; + item = item->next; + return tmp; + } + Ref operator*() const { return item->data; } + Ptr operator->() const { return item->data; } + + bool operator==(const iterator &rhs) const { return item == rhs->item; } + bool operator==(const const_iterator &rhs) const { return item == rhs->item; } + + bool operator!=(const iterator &rhs) const { return item != rhs->item; } + bool operator!=(const const_iterator &rhs) const { return item != rhs->item; } + + const T* &base() const { return item; } + +private: + T* item; +}; + namespace std { template struct pair { @@ -43,29 +212,227 @@ pair(const T1 &a, const T2 &b) : first(a), second(b) {} template - pair(const pair &other) : first(other.first), second(other.second) {} + pair(const pair &other) : first(other.first), + second(other.second) {} }; typedef __typeof__(sizeof(int)) size_t; + + template class initializer_list; + template< class T > struct remove_reference {typedef T type;}; + template< class T > struct remove_reference {typedef T type;}; + template< class T > struct remove_reference {typedef T type;}; + + template + typename remove_reference::type&& move(T&& a) { + typedef typename remove_reference::type&& RvalRef; + return static_cast(a); + } + template class vector { - typedef __iterator iterator; - typedef __iterator const_iterator; + typedef T value_type; + typedef size_t size_type; + typedef __vector_iterator iterator; + typedef __vector_iterator const_iterator; T *_start; T *_finish; T *_end_of_storage; public: vector() : _start(0), _finish(0), _end_of_storage(0) {} + template + vector(InputIterator first, InputIterator last); + vector(const vector &other); + vector(vector &&other); ~vector(); size_t size() const { return size_t(_finish - _start); } + + vector& operator=(const vector &other); + vector& operator=(vector &&other); + vector& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + template + void emplace_back(Args&&... args); + void pop_back(); + + iterator insert(const_iterator position, const value_type &val); + iterator insert(const_iterator position, size_type n, + const value_type &val); + template + iterator insert(const_iterator position, InputIterator first, + InputIterator last); + iterator insert(const_iterator position, value_type &&val); + iterator insert(const_iterator position, initializer_list il); + + template + iterator emplace(const_iterator position, Args&&... args); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + + T &operator[](size_t n) { + return _start[n]; + } + + const T &operator[](size_t n) const { + return _start[n]; + } + + iterator begin() { return iterator(_start); } + const_iterator begin() const { return const_iterator(_start); } + const_iterator cbegin() const { return const_iterator(_start); } + iterator end() { return iterator(_finish); } + const_iterator end() const { return const_iterator(_finish); } + const_iterator cend() const { return const_iterator(_finish); } + T& front() { return *begin(); } + const T& front() const { return *begin(); } + T& back() { return *(end() - 1); } + const T& back() const { return *(end() - 1); } + }; + + template + class list { + struct __item { + T data; + __item *prev, *next; + } *_start, *_finish; + public: + typedef T value_type; + typedef size_t size_type; + typedef __list_iterator<__item, T *, T &> iterator; + typedef __list_iterator<__item, const T *, const T &> const_iterator; + + list() : _start(0), _finish(0) {} + template + list(InputIterator first, InputIterator last); + list(const list &other); + list(list &&other); + ~list(); + + list& operator=(const list &other); + list& operator=(list &&other); + list& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + template + void emplace_back(Args&&... args); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + template + void emplace_front(Args&&... args); + void pop_front(); + + iterator insert(const_iterator position, const value_type &val); + iterator insert(const_iterator position, size_type n, + const value_type &val); + template + iterator insert(const_iterator position, InputIterator first, + InputIterator last); + iterator insert(const_iterator position, value_type &&val); + iterator insert(const_iterator position, initializer_list il); - void push_back(); - T pop_back(); + template + iterator emplace(const_iterator position, Args&&... args); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); + + iterator begin() { return iterator(_start); } + const_iterator begin() const { return const_iterator(_start); } + const_iterator cbegin() const { return const_iterator(_start); } + iterator end() { return iterator(_finish); } + const_iterator end() const { return const_iterator(_finish); } + const_iterator cend() const { return const_iterator(_finish); } + + T& front() { return *begin(); } + const T& front() const { return *begin(); } + T& back() { return *--end(); } + const T& back() const { return *--end(); } + }; + + template + class deque { + typedef T value_type; + typedef size_t size_type; + typedef __deque_iterator iterator; + typedef __deque_iterator const_iterator; + + T *_start; + T *_finish; + T *_end_of_storage; + public: + deque() : _start(0), _finish(0), _end_of_storage(0) {} + template + deque(InputIterator first, InputIterator last); + deque(const deque &other); + deque(deque &&other); + ~deque(); + + size_t size() const { + return size_t(_finish - _start); + } + + deque& operator=(const deque &other); + deque& operator=(deque &&other); + deque& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + template + void emplace_back(Args&&... args); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + template + void emplace_front(Args&&... args); + void pop_front(); + + iterator insert(const_iterator position, const value_type &val); + iterator insert(const_iterator position, size_type n, + const value_type &val); + template + iterator insert(const_iterator position, InputIterator first, + InputIterator last); + iterator insert(const_iterator position, value_type &&val); + iterator insert(const_iterator position, initializer_list il); + + template + iterator emplace(const_iterator position, Args&&... args); + + iterator erase(const_iterator position); + iterator erase(const_iterator first, const_iterator last); T &operator[](size_t n) { return _start[n]; @@ -77,10 +444,79 @@ iterator begin() { return iterator(_start); } const_iterator begin() const { return const_iterator(_start); } + const_iterator cbegin() const { return const_iterator(_start); } iterator end() { return iterator(_finish); } const_iterator end() const { return const_iterator(_finish); } + const_iterator cend() const { return const_iterator(_finish); } + T& front() { return *begin(); } + const T& front() const { return *begin(); } + T& back() { return *(end() - 1); } + const T& back() const { return *(end() - 1); } }; + template + class forward_list { + struct __item { + T data; + __item *next; + } *_start; + public: + typedef T value_type; + typedef size_t size_type; + typedef __fwdl_iterator<__item, T *, T &> iterator; + typedef __fwdl_iterator<__item, const T *, const T &> const_iterator; + + forward_list() : _start(0) {} + template + forward_list(InputIterator first, InputIterator last); + forward_list(const forward_list &other); + forward_list(forward_list &&other); + ~forward_list(); + + forward_list& operator=(const forward_list &other); + forward_list& operator=(forward_list &&other); + forward_list& operator=(std::initializer_list ilist); + + void assign(size_type count, const T &value); + template + void assign(InputIterator first, InputIterator last); + void assign(std::initializer_list ilist); + + void clear(); + + void push_front(const T &value); + void push_front(T &&value); + template + void emplace_front(Args&&... args); + void pop_front(); + + iterator insert_after(const_iterator position, const value_type &val); + iterator insert_after(const_iterator position, value_type &&val); + iterator insert_after(const_iterator position, size_type n, + const value_type &val); + template + iterator insert_after(const_iterator position, InputIterator first, + InputIterator last); + iterator insert_after(const_iterator position, + initializer_list il); + + template + iterator emplace_after(const_iterator position, Args&&... args); + + iterator erase_after(const_iterator position); + iterator erase_after(const_iterator first, const_iterator last); + + iterator begin() { return iterator(_start); } + const_iterator begin() const { return const_iterator(_start); } + const_iterator cbegin() const { return const_iterator(_start); } + iterator end() { return iterator(); } + const_iterator end() const { return const_iterator(); } + const_iterator cend() const { return const_iterator(); } + + T& front() { return *begin(); } + const T& front() const { return *begin(); } + }; + class exception { public: exception() throw(); @@ -247,6 +683,34 @@ OutputIter copy_backward(InputIter II, InputIter IE, OutputIter OI) { return __copy_backward(II, IE, OI); } +} + +template +void __advance (BidirectionalIterator& it, Distance n, + std::bidirectional_iterator_tag) { + if (n >= 0) while(n-- > 0) ++it; else while (n++<0) --it; +} + +template +void __advance (RandomAccessIterator& it, Distance n, + std::random_access_iterator_tag) { + it += n; +} + +namespace std { + template + void advance (InputIterator& it, Distance n) { + __advance(it, n, typename InputIterator::iterator_category()); + } + + template + BidirectionalIterator + prev (BidirectionalIterator it, + typename iterator_traits::difference_type n = + 1) { + advance(it, -n); + return it; + } template InputIterator find(InputIterator first, InputIterator last, const T &val); @@ -277,11 +741,9 @@ ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2); - struct input_iterator_tag { }; - struct output_iterator_tag { }; - struct forward_iterator_tag : public input_iterator_tag { }; - struct bidirectional_iterator_tag : public forward_iterator_tag { }; - struct random_access_iterator_tag : public bidirectional_iterator_tag { }; + template + OutputIterator copy(InputIterator first, InputIterator last, + OutputIterator result); } Index: test/Analysis/diagnostics/explicit-suppression.cpp =================================================================== --- test/Analysis/diagnostics/explicit-suppression.cpp +++ test/Analysis/diagnostics/explicit-suppression.cpp @@ -19,6 +19,6 @@ void testCopyNull(C *I, C *E) { std::copy(I, E, (C *)0); #ifndef SUPPRESSED - // expected-warning@../Inputs/system-header-simulator-cxx.h:191 {{Called C++ object pointer is null}} + // expected-warning@../Inputs/system-header-simulator-cxx.h:627 {{Called C++ object pointer is null}} #endif } Index: test/Analysis/invalidated-iterator.cpp =================================================================== --- /dev/null +++ test/Analysis/invalidated-iterator.cpp @@ -0,0 +1,399 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.InvalidatedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void bad_copy_assign_operator_list1(std::list &L1, + const std::list &L2) { + auto i0 = L1.cbegin(); + L1 = L2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_vector1(std::vector &V1, + const std::vector &V2) { + auto i0 = V1.cbegin(); + V1 = V2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_deque1(std::deque &D1, + const std::deque &D2) { + auto i0 = D1.cbegin(); + D1 = D2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_copy_assign_operator_forward_list1(std::forward_list &FL1, + const std::forward_list &FL2) { + auto i0 = FL1.cbegin(); + FL1 = FL2; + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_assign_list1(std::list &L, int n) { + auto i0 = L.cbegin(); + L.assign(10, n); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_assign_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(); + V.assign(10, n); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_assign_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(); + D.assign(10, n); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_assign_forward_list1(std::forward_list &FL, int n) { + auto i0 = FL.cbegin(); + FL.assign(10, n); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_clear_list1(std::list &L) { + auto i0 = L.cend(); + L.clear(); + --i0; // no-warning +} + +void bad_clear_list1(std::list &L) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.clear(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_clear_vector1(std::vector &V) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.clear(); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_clear_deque1(std::deque &D) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.clear(); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_push_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.push_back(n); + *i0; // no-warning + --i1; // no-warning +} + +void good_push_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.push_back(n); + *i0; // no-warning +} + +void bad_push_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.push_back(n); + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_push_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.push_back(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_emplace_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.emplace_back(n); + *i0; // no-warning + --i1; // no-warning +} + +void good_emplace_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.emplace_back(n); + *i0; // no-warning +} + +void bad_emplace_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(); + V.emplace_back(n); + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_emplace_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.emplace_back(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--; + L.pop_back(); + *i0; // no-warning + *i2; // no-warning +} + +void bad_pop_back_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(), i2 = i1--; + L.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--; + V.pop_back(); + *i0; // no-warning +} + +void bad_pop_back_vector1(std::vector &V, int n) { + auto i0 = V.cbegin(), i1 = V.cend(), i2 = i1--; + V.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} + --i2; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--; + D.pop_back(); + *i0; // no-warning +} + +void bad_pop_back_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(), i2 = i1--; + D.pop_back(); + *i1; // expected-warning{{Invalidated iterator accessed}} + --i2; // expected-warning{{Invalidated iterator accessed}} +} + +void good_push_front_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.push_front(n); + *i0; // no-warning + --i1; // no-warning +} + +void bad_push_front_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.push_front(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_push_front_forward_list1(std::forward_list &FL, int n) { + auto i0 = FL.cbegin(), i1 = FL.cend(); + FL.push_front(n); + *i0; // no-warning +} + +void good_emplace_front_list1(std::list &L, int n) { + auto i0 = L.cbegin(), i1 = L.cend(); + L.emplace_front(n); + *i0; // no-warning + --i1; // no-warning +} + +void bad_emplace_front_deque1(std::deque &D, int n) { + auto i0 = D.cbegin(), i1 = D.cend(); + D.emplace_front(n); + *i0; // expected-warning{{Invalidated iterator accessed}} + --i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_emplace_front_forward_list1(std::forward_list &FL, int n) { + auto i0 = FL.cbegin(), i1 = FL.cend(); + FL.emplace_front(n); + *i0; // no-warning +} + +void good_pop_front_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_front_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_pop_front_forward_list1(std::forward_list &FL, int n) { + auto i1 = FL.cbegin(), i0 = i1++; + FL.pop_front(); + *i1; // no-warning +} + +void bad_pop_front_forward_list1(std::forward_list &FL, int n) { + auto i1 = FL.cbegin(), i0 = i1++; + FL.pop_front(); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_insert_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.insert(i1, n); + *i0; // no-warning + *i1; // no-warning +} + +void good_insert_vector1(std::vector &V, int n) { + auto i1 = V.cbegin(), i0 = i1++; + V.insert(i1, n); + *i0; // no-warning +} + +void bad_insert_vector1(std::vector &V, int n) { + auto i1 = V.cbegin(), i0 = i1++; + V.insert(i1, n); + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_insert_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.insert(i1, n); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_emplace_list1(std::list &L, int n) { + auto i1 = L.cbegin(), i0 = i1++; + L.emplace(i1, n); + *i0; // no-warning + *i1; // no-warning +} + +void good_emplace_vector1(std::vector &V, int n) { + auto i1 = V.cbegin(), i0 = i1++; + V.emplace(i1, n); + *i0; // no-warning +} + +void bad_emplace_vector1(std::vector &V, int n) { + auto i1 = V.cbegin(), i0 = i1++; + V.emplace(i1, n); + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_emplace_deque1(std::deque &D, int n) { + auto i1 = D.cbegin(), i0 = i1++; + D.emplace(i1, n); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_list1(std::list &L) { + auto i2 = L.cbegin(), i0 = i2++, i1 = i2++; + L.erase(i1); + *i0; // no-warning + *i2; // no-warning +} + +void bad_erase_list1(std::list &L) { + auto i0 = L.cbegin(); + L.erase(i0); + *i0; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_vector1(std::vector &V) { + auto i2 = V.cbegin(), i0 = i2++, i1 = i2++; + V.erase(i1); + *i0; // no-warning +} + +void bad_erase_vector1(std::vector &V) { + auto i1 = V.cbegin(), i0 = i1++; + V.erase(i0); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_erase_deque1(std::deque &D) { + auto i2 = D.cbegin(), i0 = i2++, i1 = i2++; + D.erase(i1); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} + *i2; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_list2(std::list &L) { + auto i3 = L.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++; + L.erase(i1, i3); + *i0; // no-warning + *i3; // no-warning +} + +void bad_erase_list2(std::list &L) { + auto i2 = L.cbegin(), i0 = i2++, i1 = i2++; + L.erase(i0, i2); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_vector2(std::vector &V) { + auto i3 = V.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++;; + V.erase(i1, i3); + *i0; // no-warning +} + +void bad_erase_vector2(std::vector &V) { + auto i2 = V.cbegin(), i0 = i2++, i1 = i2++; + V.erase(i0, i2); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} + *i2; // expected-warning{{Invalidated iterator accessed}} +} + +void bad_erase_deque2(std::deque &D) { + auto i3 = D.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++; + D.erase(i1, i3); + *i0; // expected-warning{{Invalidated iterator accessed}} + *i1; // expected-warning{{Invalidated iterator accessed}} + *i2; // expected-warning{{Invalidated iterator accessed}} + *i3; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_after_forward_list1(std::forward_list &FL) { + auto i2 = FL.cbegin(), i0 = i2++, i1 = i2++; + FL.erase_after(i0); + *i0; // no-warning + *i2; // no-warning +} + +void bad_erase_after_forward_list1(std::forward_list &FL) { + auto i1 = FL.cbegin(), i0 = i1++; + FL.erase_after(i0); + *i1; // expected-warning{{Invalidated iterator accessed}} +} + +void good_erase_after_forward_list2(std::forward_list &FL) { + auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++; + FL.erase_after(i0, i3); + *i0; // no-warning + *i3; // no-warning +} + +void bad_erase_after_forward_list2(std::forward_list &FL) { + auto i3 = FL.cbegin(), i0 = i3++, i1 = i3++, i2 = i3++; + FL.erase_after(i0, i3); + *i1; // expected-warning{{Invalidated iterator accessed}} + *i2; // expected-warning{{Invalidated iterator accessed}} +} Index: test/Analysis/iterator-past-end.cpp =================================================================== --- test/Analysis/iterator-past-end.cpp +++ /dev/null @@ -1,205 +0,0 @@ -// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify -// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify - -#include "Inputs/system-header-simulator-cxx.h" - -void simple_good(const std::vector &v) { - auto i = v.end(); - if (i != v.end()) - *i; // no-warning -} - -void simple_good_negated(const std::vector &v) { - auto i = v.end(); - if (!(i == v.end())) - *i; // no-warning -} - -void simple_bad(const std::vector &v) { - auto i = v.end(); - *i; // expected-warning{{Iterator accessed past its end}} -} - -void copy(const std::vector &v) { - auto i1 = v.end(); - auto i2 = i1; - *i2; // expected-warning{{Iterator accessed past its end}} -} - -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 past its end}} -} - -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 past its end}} -} - -void good_find(std::vector &vec, int e) { - auto first = std::find(vec.begin(), vec.end(), e); - if (vec.end() != first) - *first; // no-warning -} - -void bad_find(std::vector &vec, int e) { - auto first = std::find(vec.begin(), vec.end(), e); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void good_find_end(std::vector &vec, std::vector &seq) { - auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end()); - if (vec.end() != last) - *last; // no-warning -} - -void bad_find_end(std::vector &vec, std::vector &seq) { - auto last = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end()); - *last; // expected-warning{{Iterator accessed past its end}} -} - -void good_find_first_of(std::vector &vec, std::vector &seq) { - auto first = - std::find_first_of(vec.begin(), vec.end(), seq.begin(), seq.end()); - if (vec.end() != first) - *first; // no-warning -} - -void bad_find_first_of(std::vector &vec, std::vector &seq) { - auto first = std::find_end(vec.begin(), vec.end(), seq.begin(), seq.end()); - *first; // expected-warning{{Iterator accessed past its end}} -} - -bool odd(int i) { return i % 2; } - -void good_find_if(std::vector &vec) { - auto first = std::find_if(vec.begin(), vec.end(), odd); - if (vec.end() != first) - *first; // no-warning -} - -void bad_find_if(std::vector &vec, int e) { - auto first = std::find_if(vec.begin(), vec.end(), odd); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void good_find_if_not(std::vector &vec) { - auto first = std::find_if_not(vec.begin(), vec.end(), odd); - if (vec.end() != first) - *first; // no-warning -} - -void bad_find_if_not(std::vector &vec, int e) { - auto first = std::find_if_not(vec.begin(), vec.end(), odd); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void good_lower_bound(std::vector &vec, int e) { - auto first = std::lower_bound(vec.begin(), vec.end(), e); - if (vec.end() != first) - *first; // no-warning -} - -void bad_lower_bound(std::vector &vec, int e) { - auto first = std::lower_bound(vec.begin(), vec.end(), e); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void good_upper_bound(std::vector &vec, int e) { - auto last = std::lower_bound(vec.begin(), vec.end(), e); - if (vec.end() != last) - *last; // no-warning -} - -void bad_upper_bound(std::vector &vec, int e) { - auto last = std::lower_bound(vec.begin(), vec.end(), e); - *last; // expected-warning{{Iterator accessed past its end}} -} - -void good_search(std::vector &vec, std::vector &seq) { - auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end()); - if (vec.end() != first) - *first; // no-warning -} - -void bad_search(std::vector &vec, std::vector &seq) { - auto first = std::search(vec.begin(), vec.end(), seq.begin(), seq.end()); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void good_search_n(std::vector &vec, std::vector &seq) { - auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end()); - if (vec.end() != nth) - *nth; // no-warning -} - -void bad_search_n(std::vector &vec, std::vector &seq) { - auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end()); - *nth; // expected-warning{{Iterator accessed past its end}} -} - -template -InputIterator nonStdFind(InputIterator first, InputIterator last, - const T &val) { - for (auto i = first; i != last; ++i) { - if (*i == val) { - return i; - } - } - return last; -} - -void good_non_std_find(std::vector &vec, int e) { - auto first = nonStdFind(vec.begin(), vec.end(), e); - if (vec.end() != first) - *first; // no-warning -} - -void bad_non_std_find(std::vector &vec, int e) { - auto first = nonStdFind(vec.begin(), vec.end(), e); - *first; // expected-warning{{Iterator accessed past its end}} -} - -void tricky(std::vector &vec, int e) { - const auto first = vec.begin(); - const auto comp1 = (first != vec.end()), comp2 = (first == vec.end()); - if (comp1) - *first; -} - -void loop(std::vector &vec, int e) { - auto start = vec.begin(); - while (true) { - auto item = std::find(start, vec.end(), e); - if (item == vec.end()) - break; - *item; // no-warning - start = ++item; // no-warning - } -} Index: test/Analysis/iterator-range.cpp =================================================================== --- /dev/null +++ test/Analysis/iterator-range.cpp @@ -0,0 +1,286 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorRange -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void simple_good_end(const std::vector &v) { + auto i = v.end(); + if (i != v.end()) + *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 good_find(std::vector &V, int e) { + auto first = std::find(V.begin(), V.end(), e); + if (V.end() != first) + *first; // no-warning +} + +void bad_find(std::vector &V, int e) { + auto first = std::find(V.begin(), V.end(), e); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_find_end(std::vector &V, std::vector &seq) { + auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end()); + if (V.end() != last) + *last; // no-warning +} + +void bad_find_end(std::vector &V, std::vector &seq) { + auto last = std::find_end(V.begin(), V.end(), seq.begin(), seq.end()); + *last; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_find_first_of(std::vector &V, std::vector &seq) { + auto first = + std::find_first_of(V.begin(), V.end(), seq.begin(), seq.end()); + if (V.end() != first) + *first; // no-warning +} + +void bad_find_first_of(std::vector &V, std::vector &seq) { + auto first = std::find_end(V.begin(), V.end(), seq.begin(), seq.end()); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +bool odd(int i) { return i % 2; } + +void good_find_if(std::vector &V) { + auto first = std::find_if(V.begin(), V.end(), odd); + if (V.end() != first) + *first; // no-warning +} + +void bad_find_if(std::vector &V, int e) { + auto first = std::find_if(V.begin(), V.end(), odd); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_find_if_not(std::vector &V) { + auto first = std::find_if_not(V.begin(), V.end(), odd); + if (V.end() != first) + *first; // no-warning +} + +void bad_find_if_not(std::vector &V, int e) { + auto first = std::find_if_not(V.begin(), V.end(), odd); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_lower_bound(std::vector &V, int e) { + auto first = std::lower_bound(V.begin(), V.end(), e); + if (V.end() != first) + *first; // no-warning +} + +void bad_lower_bound(std::vector &V, int e) { + auto first = std::lower_bound(V.begin(), V.end(), e); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_upper_bound(std::vector &V, int e) { + auto last = std::lower_bound(V.begin(), V.end(), e); + if (V.end() != last) + *last; // no-warning +} + +void bad_upper_bound(std::vector &V, int e) { + auto last = std::lower_bound(V.begin(), V.end(), e); + *last; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_search(std::vector &V, std::vector &seq) { + auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end()); + if (V.end() != first) + *first; // no-warning +} + +void bad_search(std::vector &V, std::vector &seq) { + auto first = std::search(V.begin(), V.end(), seq.begin(), seq.end()); + *first; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_search_n(std::vector &V, std::vector &seq) { + auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end()); + if (V.end() != nth) + *nth; // no-warning +} + +void bad_search_n(std::vector &V, std::vector &seq) { + auto nth = std::search_n(V.begin(), V.end(), seq.begin(), seq.end()); + *nth; // expected-warning{{Iterator accessed outside of its range}} +} + +template +InputIterator nonStdFind(InputIterator first, InputIterator last, + const T &val) { + for (auto i = first; i != last; ++i) { + if (*i == val) { + return i; + } + } + return last; +} + +void good_non_std_find(std::vector &V, int e) { + auto first = nonStdFind(V.begin(), V.end(), e); + if (V.end() != first) + *first; // no-warning +} + +void bad_non_std_find(std::vector &V, int e) { + auto first = nonStdFind(V.begin(), V.end(), e); + *first; // 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 good_push_back(std::list &L, int n) { + auto i0 = --L.cend(); + L.push_back(n); + *++i0; // no-warning +} + +void bad_push_back(std::list &L, int n) { + auto i0 = --L.cend(); + L.push_back(n); + ++i0; + *++i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_pop_back(std::list &L, int n) { + auto i0 = --L.cend(); --i0; + L.pop_back(); + *i0; // no-warning +} + +void bad_pop_back(std::list &L, int n) { + auto i0 = --L.cend(); --i0; + L.pop_back(); + *++i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_push_front(std::list &L, int n) { + auto i0 = L.cbegin(); + L.push_front(n); + *--i0; // no-warning +} + +void bad_push_front(std::list &L, int n) { + auto i0 = L.cbegin(); + L.push_front(n); + --i0; + *--i0; // expected-warning{{Iterator accessed outside of its range}} +} + +void good_pop_front(std::list &L, int n) { + auto i0 = ++L.cbegin(); + L.pop_front(); + *i0; // no-warning +} + +void bad_pop_front(std::list &L, int n) { + auto i0 = ++L.cbegin(); + L.pop_front(); + *--i0; // expected-warning{{Iterator accessed outside of its range}} +} + +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}} +} + +void bad_move_push_back(std::list &L1, std::list &L2, int n) { + auto i0 = --L2.cend(); + L2.push_back(n); + L1 = std::move(L2); + ++i0; + *++i0; // expected-warning{{Iterator accessed outside of its range}} +} Index: test/Analysis/mismatched-iterator.cpp =================================================================== --- /dev/null +++ test/Analysis/mismatched-iterator.cpp @@ -0,0 +1,151 @@ +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=false %s -verify +// RUN: %clang_analyze_cc1 -std=c++11 -analyzer-checker=core,cplusplus,alpha.cplusplus.MismatchedIterator -analyzer-eagerly-assume -analyzer-config c++-container-inlining=true -DINLINE=1 %s -verify + +#include "Inputs/system-header-simulator-cxx.h" + +void good_insert1(std::vector &v, int n) { + v.insert(v.cbegin(), n); // no-warning +} + + +void good_insert2(std::vector &v, int len, int n) { + v.insert(v.cbegin(), len, n); // no-warning +} + +void good_insert3(std::vector &v1, std::vector &v2) { + v1.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // no-warning +} + +void good_insert4(std::vector &v, int len, int n) { + v.insert(v.cbegin(), {n-1, n, n+1}); // no-warning +} + +void good_insert_find(std::vector &v, int n, int m) { + auto i = std::find(v.cbegin(), v.cend(), n); + v.insert(i, m); // no-warning +} + +void good_erase1(std::vector &v) { + v.erase(v.cbegin()); // no-warning +} + +void good_erase2(std::vector &v) { + v.erase(v.cbegin(), v.cend()); // no-warning +} + +void good_emplace(std::vector &v, int n) { + v.emplace(v.cbegin(), n); // no-warning +} + +void good_ctor(std::vector &v) { + std::vector new_v(v.cbegin(), v.cend()); // no-warning +} + +void good_find(std::vector &v, int n) { + std::find(v.cbegin(), v.cend(), n); // no-warning +} + +void good_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v2.cend()); // no-warning +} + +void good_copy(std::vector &v1, std::vector &v2, int n) { + std::copy(v1.cbegin(), v1.cend(), v2.begin()); // no-warning +} + +void good_comparison(std::vector &v) { + if (v.cbegin() == v.cend()) {} // no-warning +} + +void bad_insert1(std::vector &v1, std::vector &v2, int n) { + v2.insert(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_insert2(std::vector &v1, std::vector &v2, int len, int n) { + v2.insert(v1.cbegin(), len, n); // expected-warning{{Iterator access mismatched}} +} + +void bad_insert3(std::vector &v1, std::vector &v2) { + v2.insert(v1.cbegin(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + v1.insert(v1.cbegin(), v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + v1.insert(v1.cbegin(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} +} + +void bad_insert4(std::vector &v1, std::vector &v2, int len, int n) { + v2.insert(v1.cbegin(), {n-1, n, n+1}); // expected-warning{{Iterator access mismatched}} +} + +void bad_erase1(std::vector &v1, std::vector &v2) { + v2.erase(v1.cbegin()); // expected-warning{{Iterator access mismatched}} +} + +void bad_erase2(std::vector &v1, std::vector &v2) { + v2.erase(v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} + v2.erase(v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + v2.erase(v1.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} +} + +void bad_emplace(std::vector &v1, std::vector &v2, int n) { + v2.emplace(v1.cbegin(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_ctor(std::vector &v1, std::vector &v2) { + std::vector new_v(v1.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} +} + +void bad_find(std::vector &v1, std::vector &v2, int n) { + std::find(v1.cbegin(), v2.cend(), n); // expected-warning{{Iterator access mismatched}} +} + +void bad_find_first_of(std::vector &v1, std::vector &v2) { + std::find_first_of(v1.cbegin(), v2.cend(), v2.cbegin(), v2.cend()); // expected-warning{{Iterator access mismatched}} + std::find_first_of(v1.cbegin(), v1.cend(), v2.cbegin(), v1.cend()); // expected-warning{{Iterator access mismatched}} +} + +void bad_comparison(std::vector &v1, std::vector &v2) { + if (v1.cbegin() != v2.cend()) { // expected-warning{{Iterator access mismatched}} + *v1.cbegin(); + } +} + +void bad_insert_find(std::vector &v1, std::vector &v2, int n, int m) { + auto i = std::find(v1.cbegin(), v1.cend(), n); + v2.insert(i, m); // expected-warning{{Iterator access mismatched}} +} + +void good_overwrite(std::vector &v1, std::vector &v2, int n) { + auto i = v1.cbegin(); + i = v2.cbegin(); + v2.insert(i, n); // no-warning +} + +void bad_overwrite(std::vector &v1, std::vector &v2, int n) { + auto i = v1.cbegin(); + i = v2.cbegin(); + v1.insert(i, n); // expected-warning{{Iterator access mismatched}} +} + +template +bool is_cend(Container cont, Iterator it) { + return it == cont.cend(); +} + +void good_empty(std::vector &v) { + is_cend(v, v.cbegin()); // no-warning +} + +void bad_empty(std::vector &v1, std::vector &v2) { + is_cend(v1, v2.cbegin()); // expected-warning@130{{Iterator access mismatched}} +} + +void good_move(std::vector &v1, std::vector &v2) { + const auto i0 = ++v2.cbegin(); + v1 = std::move(v2); + v1.erase(i0); // no-warning +} + +void bad_move(std::vector &v1, std::vector &v2) { + const auto i0 = ++v2.cbegin(); + v1 = std::move(v2); + v2.erase(i0); // expected-warning{{Iterator access mismatched}} +}