Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -279,15 +279,15 @@ let ParentPackage = CplusplusAlpha in { +def IteratorRangeChecker : Checker<"IteratorRange">, + HelpText<"Check for iterators used outside their valid ranges">, + 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,821 @@ +//===-- 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; + SymbolRef Offset; + IteratorPosition(const MemRegion *C, SymbolRef Of) + : Cont(C), Offset(Of) {} + +public: + const MemRegion *getContainer() const { return Cont; } + SymbolRef getOffset() const { return Offset; } + + static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { + return IteratorPosition(C, Of); + } + + IteratorPosition setTo(SymbolRef NewOf) const { + return IteratorPosition(Cont, NewOf); + } + + bool operator==(const IteratorPosition &X) const { + return Cont == X.Cont && Offset == X.Offset; + } + + bool operator!=(const IteratorPosition &X) const { + return Cont != X.Cont || Offset != X.Offset; + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + ID.AddPointer(Cont); + ID.Add(Offset); + } +}; + +typedef llvm::PointerUnion RegionOrSymbol; + +struct ContainerData { +private: + SymbolRef End; + + ContainerData(SymbolRef E) : End(E) {} + +public: + static ContainerData fromEnd(SymbolRef E) { + return ContainerData(E); + } + + SymbolRef getEnd() const { return End; } + + ContainerData newEnd(SymbolRef E) const { return ContainerData(E); } + + bool operator==(const ContainerData &X) const { + return End == X.End; + } + + bool operator!=(const ContainerData &X) const { + return End != X.End; + } + + void Profile(llvm::FoldingSetNodeID &ID) const { + 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::LiveSymbols, check::DeadSymbols, + eval::Assume> { + + std::unique_ptr OutOfRangeBugType; + + void handleComparison(CheckerContext &C, const SVal &RetVal, const SVal &LVal, + const SVal &RVal, OverloadedOperatorKind Op) const; + void verifyDereference(CheckerContext &C, const SVal &Val) const; + void 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 reportOutOfRangeBug(const StringRef &Message, const SVal &Val, + CheckerContext &C, ExplodedNode *ErrNode) const; + +public: + IteratorChecker(); + + enum CheckKind { + CK_IteratorRangeChecker, + 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 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; +}; +} // 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 isEndCall(const FunctionDecl *Func); +bool isSimpleComparisonOperator(OverloadedOperatorKind OK); +bool isDereferenceOperator(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); +SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); +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); +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); +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); +} + +void IteratorChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + // Check for out of range access + const auto *Func = dyn_cast_or_null(Call.getDecl()); + if (!Func) + return; + + if (Func->isOverloadedOperator()) { + 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)); + } + } + } +} + +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 (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 { + 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 (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::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.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); +} + +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::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::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)); +} + +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); + +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 isDereferenceOperator(OverloadedOperatorKind OK) { + return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || + OK == OO_Subscript; +} + +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) { + 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 getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { + const auto *CDataPtr = getContainerData(State, Cont); + if (!CDataPtr) + return nullptr; + + return CDataPtr->getEnd(); +} + +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) { + // 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); + } + + return State; +} + +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 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(); + + const auto comparison = + SVB.evalBinOp(State, Opc, nonloc::SymbolVal(Sym1), + nonloc::SymbolVal(Sym2), SVB.getConditionType()) + .getAs(); + + if(comparison) { + return !!State->assume(*comparison, true); + } + + return false; +} + +} // 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) 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,61 @@ 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; + } - __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 +72,136 @@ 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; + } + + 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 __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,30 +212,142 @@ 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); } + + void clear(); + + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + + 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 clear(); + + 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); + } - void push_back(); - T pop_back(); + void clear(); + void push_back(const T &value); + void push_back(T &&value); + void pop_back(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + T &operator[](size_t n) { return _start[n]; } @@ -77,10 +358,52 @@ 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(); + + void clear(); + + void push_front(const T &value); + void push_front(T &&value); + void pop_front(); + + 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,41 +570,41 @@ 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); - template - ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2); - template - ForwardIterator1 find_first_of(ForwardIterator1 first1, - ForwardIterator1 last1, - ForwardIterator2 first2, - ForwardIterator2 last2); - template - InputIterator find_if(InputIterator first, InputIterator last, - UnaryPredicate pred); - template - InputIterator find_if_not(InputIterator first, InputIterator last, - UnaryPredicate pred); - template - InputIterator lower_bound(InputIterator first, InputIterator last, - const T &val); - template - InputIterator upper_bound(InputIterator first, InputIterator last, - const T &val); - template - ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, - ForwardIterator2 first2, ForwardIterator2 last2); - template - 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:514 {{Called C++ object pointer is null}} #endif } 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,15 @@ +// 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_bad_end(const std::vector &v) { + auto i = v.end(); + *i; // expected-warning{{Iterator accessed outside of its range}} +}