baloghadamsoftware updated this revision to Diff 78352. baloghadamsoftware added a comment.
Updated according to comments. https://reviews.llvm.org/D25660 Files: include/clang/StaticAnalyzer/Checkers/Checkers.td lib/StaticAnalyzer/Checkers/CMakeLists.txt lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp lib/StaticAnalyzer/Core/ExprEngine.cpp test/Analysis/Inputs/system-header-simulator-for-iterators.h test/Analysis/iterator-past-end.cpp
Index: test/Analysis/iterator-past-end.cpp =================================================================== --- /dev/null +++ test/Analysis/iterator-past-end.cpp @@ -0,0 +1,193 @@ +// RUN: %clang_cc1 -std=c++11 -analyze -analyzer-checker=core,cplusplus,alpha.cplusplus.IteratorPastEnd -analyzer-eagerly-assume %s -verify + +#include "Inputs/system-header-simulator-for-iterators.h" + +void simple_good(const std::vector<int> &v) { + auto i = v.end(); + if (i != v.end()) + *i; // no-warning +} + +void simple_good_negated(const std::vector<int> &v) { + auto i = v.end(); + if (!(i == v.end())) + *i; // no-warning +} + +void simple_bad(const std::vector<int> &v) { + auto i = v.end(); + *i; // expected-warning{{Iterator accessed past its end}} +} + +void copy(const std::vector<int> &v) { + auto i1 = v.end(); + auto i2 = i1; + *i2; // expected-warning{{Iterator accessed past its end}} +} + +void decrease(const std::vector<int> &v) { + auto i = v.end(); + --i; + *i; // no-warning +} + +void copy_and_decrease1(const std::vector<int> &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i1; // no-warning +} + +void copy_and_decrease2(const std::vector<int> &v) { + auto i1 = v.end(); + auto i2 = i1; + --i1; + *i2; // expected-warning{{Iterator accessed past its end}} +} + +void copy_and_increase1(const std::vector<int> &v) { + auto i1 = v.begin(); + auto i2 = i1; + ++i1; + if (i1 == v.end()) + *i2; // no-warning +} + +void copy_and_increase2(const std::vector<int> &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<int> &vec, int e) { + auto first = std::find(vec.begin(), vec.end(), e); + if (vec.end() != first) + *first; // no-warning +} + +void bad_find(std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec) { + auto first = std::find_if(vec.begin(), vec.end(), odd); + if (vec.end() != first) + *first; // no-warning +} + +void bad_find_if(std::vector<int> &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<int> &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<int> &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<int> &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<int> &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<int> &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<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &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<int> &vec, std::vector<int> &seq) { + auto nth = std::search_n(vec.begin(), vec.end(), seq.begin(), seq.end()); + *nth; // expected-warning{{Iterator accessed past its end}} +} + +template <class InputIterator, class T> +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<int> &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<int> &vec, int e) { + auto first = nonStdFind(vec.begin(), vec.end(), e); + *first; // expected-warning{{Iterator accessed past its end}} +} + +void tricky(std::vector<int> &vec, int e) { + const auto first = vec.begin(); + const auto comp1 = (first == vec.begin()), comp2 = (first == vec.end()); + if(comp1) + *first; +} Index: test/Analysis/Inputs/system-header-simulator-for-iterators.h =================================================================== --- /dev/null +++ test/Analysis/Inputs/system-header-simulator-for-iterators.h @@ -0,0 +1,62 @@ +#pragma clang system_header + +template <typename T, typename Ptr, typename Ref> struct __iterator { + typedef __iterator<T, T *, T &> iterator; + typedef __iterator<T, const T *, const T &> const_iterator; + + __iterator<T, Ptr, Ref> operator++() { return *this; } + __iterator<T, Ptr, Ref> operator++(int) { return *this; } + __iterator<T, Ptr, Ref> operator--() { return *this; } + __iterator<T, Ptr, Ref> operator--(int) { return *this; } + 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; } + +private: + Ptr ptr; +}; + +namespace std { + +template <typename T> struct vector { + typedef __iterator<T, T *, T &> iterator; + typedef __iterator<T, const T *, const T &> const_iterator; + + iterator begin(); + const_iterator begin() const; + iterator end(); + const_iterator end() const; +}; + +template <class InputIterator, class T> +InputIterator find(InputIterator first, InputIterator last, const T &val); +template <class ForwardIterator1, class ForwardIterator2> +ForwardIterator1 find_end(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2); +template <class ForwardIterator1, class ForwardIterator2> +ForwardIterator1 find_first_of(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2); +template <class InputIterator, class UnaryPredicate> +InputIterator find_if(InputIterator first, InputIterator last, + UnaryPredicate pred); +template <class InputIterator, class UnaryPredicate> +InputIterator find_if_not(InputIterator first, InputIterator last, + UnaryPredicate pred); +template <class InputIterator, class T> +InputIterator lower_bound(InputIterator first, InputIterator last, + const T &val); +template <class InputIterator, class T> +InputIterator upper_bound(InputIterator first, InputIterator last, + const T &val); +template <class ForwardIterator1, class ForwardIterator2> +ForwardIterator1 search(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2); +template <class ForwardIterator1, class ForwardIterator2> +ForwardIterator1 search_n(ForwardIterator1 first1, ForwardIterator1 last1, + ForwardIterator2 first2, ForwardIterator2 last2); +} Index: lib/StaticAnalyzer/Core/ExprEngine.cpp =================================================================== --- lib/StaticAnalyzer/Core/ExprEngine.cpp +++ lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -1221,7 +1221,14 @@ case Expr::MaterializeTemporaryExprClass: { Bldr.takeNodes(Pred); const MaterializeTemporaryExpr *MTE = cast<MaterializeTemporaryExpr>(S); - CreateCXXTemporaryObject(MTE, Pred, Dst); + ExplodedNodeSet dstPrevisit; + getCheckerManager().runCheckersForPreStmt(dstPrevisit, Pred, MTE, *this); + ExplodedNodeSet dstExpr; + for (ExplodedNodeSet::iterator i = dstPrevisit.begin(), + e = dstPrevisit.end(); i != e ; ++i) { + CreateCXXTemporaryObject(MTE, *i, dstExpr); + } + getCheckerManager().runCheckersForPostStmt(Dst, dstExpr, MTE, *this); Bldr.addNodes(Dst); break; } Index: lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp =================================================================== --- /dev/null +++ lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp @@ -0,0 +1,849 @@ +//===-- 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 <utility> + +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<const MemRegion *, SymbolRef> 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<CXXOperatorCallExpr>, + check::PostStmt<CXXConstructExpr>, check::PostStmt<DeclStmt>, + check::PostStmt<MaterializeTemporaryExpr>, check::BeginFunction, + check::DeadSymbols, eval::Assume, eval::Call> { + mutable IdentifierInfo *II_std = nullptr, *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<BugType> 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; + +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) + +namespace { + +static bool isIteratorType(const QualType &Type); +static bool isIterator(const CXXRecordDecl *CRD); +static bool isEndCall(const FunctionDecl *Func); +static bool isSimpleComparisonOperator(OverloadedOperatorKind OK); +static bool isAccessOperator(OverloadedOperatorKind OK); +static bool isDecrementOperator(OverloadedOperatorKind OK); +static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II); +static BinaryOperator::Opcode getOpcode(const SymExpr *SE); +static const RegionOrSymbol getRegionOrSymbol(const SVal &Val); +static const ProgramStateRef processComparison(ProgramStateRef State, + RegionOrSymbol LVal, + RegionOrSymbol RVal, bool Equal); +static const ProgramStateRef saveComparison(ProgramStateRef State, + const SymExpr *Condition, + const SVal &LVal, const SVal &RVal, + bool Eq); +static const IteratorComparison *loadComparison(ProgramStateRef State, + const SymExpr *Condition); +static const IteratorPosition *getIteratorPosition(ProgramStateRef State, + const SVal &Val); +static const IteratorPosition *getIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym); +static ProgramStateRef setIteratorPosition(ProgramStateRef State, + const SVal &Val, + IteratorPosition Pos); +static ProgramStateRef setIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + IteratorPosition Pos); +static ProgramStateRef adjustIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + IteratorPosition Pos, bool Equal); +static bool contradictingIteratorPositions(IteratorPosition Pos1, + IteratorPosition Pos2, bool Equal); +} + +IteratorPastEndChecker::IteratorPastEndChecker() { + PastEndBugType.reset(new BugType(this, "Iterator Past End", "C++ STL Error")); + PastEndBugType->setSuppressOnSink(true); +} + +void IteratorPastEndChecker::checkPreCall(const CallEvent &Call, + CheckerContext &C) const { + const auto *Func = Call.getDecl()->getAsFunction(); + if (!Func) + return; + if (Func->isOverloadedOperator()) { + if (isAccessOperator(Func->getOverloadedOperator())) { + if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { + handleAccess(C, InstCall->getCXXThisVal()); + } else { + handleAccess(C, Call.getArgSVal(0)); + } + } + } +} + +void IteratorPastEndChecker::checkPostCall(const CallEvent &Call, + CheckerContext &C) const { + 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<const CXXInstanceCall &>(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<const CXXInstanceCall &>(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<CXXTempObjectRegion>()) + 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 { + auto State = C.getState(); + const auto *LCtx = C.getLocationContext(); + + const auto *Site = cast<StackFrameContext>(LCtx)->getCallSite(); + if (!Site) + return; + + const auto *FD = dyn_cast<FunctionDecl>(LCtx->getDecl()); + if (!FD) + return; + + const auto *CE = dyn_cast<CallExpr>(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 { + 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 { + for (const auto *D : DS->decls()) { + const auto *VD = dyn_cast<VarDecl>(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 { + 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<IteratorRegionMap>(); + for (const auto Reg : RegionMap) { + if (!SR.isLiveRegion(Reg.first)) { + State = State->remove<IteratorRegionMap>(Reg.first); + } + } + + auto SymbolMap = State->get<IteratorSymbolMap>(); + for (const auto Sym : SymbolMap) { + if (SR.isDead(Sym.first)) { + State = State->remove<IteratorSymbolMap>(Sym.first); + } + } + + auto ComparisonMap = State->get<IteratorComparisonMap>(); + for (const auto Comp : ComparisonMap) { + if (SR.isDead(Comp.first)) { + State = State->remove<IteratorComparisonMap>(Comp.first); + } + } +} + +ProgramStateRef IteratorPastEndChecker::evalAssume(ProgramStateRef State, + SVal Cond, + bool Assumption) const { + 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<SymIntExpr>(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 D20811) 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(); + if (!II_std) + II_std = &Ctx.Idents.get("std"); + if (!II_find) + II_find = &Ctx.Idents.get("find"); + if (!II_find_end) + II_find_end = &Ctx.Idents.get("find_end"); + if (!II_find_first_of) + II_find_first_of = &Ctx.Idents.get("find_first_of"); + if (!II_find_if) + II_find_if = &Ctx.Idents.get("find_if"); + if (!II_find_if_not) + II_find_if_not = &Ctx.Idents.get("find_if_not"); + if (!II_lower_bound) + II_lower_bound = &Ctx.Idents.get("lower_bound"); + if (!II_upper_bound) + II_upper_bound = &Ctx.Idents.get("upper_bound"); + if (!II_search) + II_search = &Ctx.Idents.get("search"); + if (!II_search_n) + II_search_n = &Ctx.Idents.get("search_n"); + + if (FD->getKind() == Decl::Function) { + if (inTopLevelNamespace(FD, II_std)) { + 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) { + 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 { + 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<nonloc::ConcreteInt>()) { + 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<BugReport>(*PastEndBugType, Message, ErrNode); + R->markInteresting(Val); + C.emitReport(std::move(R)); +} + +namespace { + +static bool isIteratorType(const QualType &Type) { + if (Type->isPointerType()) + return true; + + const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); + return isIterator(CRD); +} + +static 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<CXXConstructorDecl>(Method)) { + if (Ctor->isCopyConstructor()) { + HasCopyCtor = !Ctor->isDeleted() && Ctor->getAccess() == AS_public; + } + continue; + } + if (const auto *Dtor = dyn_cast<CXXDestructorDecl>(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; +} + +static bool isEndCall(const FunctionDecl *Func) { + const auto *IdInfo = Func->getIdentifier(); + if (!IdInfo) + return false; + return IdInfo->getName().endswith_lower("end"); +} + +static bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { + return OK == OO_EqualEqual || OK == OO_ExclaimEqual; +} + +static 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; +} + +static bool isDecrementOperator(OverloadedOperatorKind OK) { + return OK == OO_MinusEqual || OK == OO_MinusMinus; +} + +static BinaryOperator::Opcode getOpcode(const SymExpr *SE) { + if (const auto *BSE = dyn_cast<BinarySymExpr>(SE)) { + return BSE->getOpcode(); + } else if (const auto *SC = dyn_cast<SymbolConjured>(SE)) { + const auto *COE = dyn_cast<CXXOperatorCallExpr>(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 +} + +static bool inTopLevelNamespace(const Decl *D, IdentifierInfo *II) { + const auto *ND = dyn_cast<NamespaceDecl>(D->getDeclContext()); + if (!ND) + return false; + + if (ND->getIdentifier() != II) + return false; + + return isa<TranslationUnitDecl>(ND->getDeclContext()); +} + +static 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<nonloc::LazyCompoundVal>()) { + return LCVal->getRegion(); + } + return RegionOrSymbol(); +} + +static 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; +} + +static 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<IteratorComparisonMap>(Condition, + IteratorComparison(Left, Right, Eq)); +} + +static const IteratorComparison *loadComparison(ProgramStateRef State, + const SymExpr *Condition) { + return State->get<IteratorComparisonMap>(Condition); +} + +static const IteratorPosition *getIteratorPosition(ProgramStateRef State, + const SVal &Val) { + if (const auto Reg = Val.getAsRegion()) { + return State->get<IteratorRegionMap>(Reg); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->get<IteratorSymbolMap>(Sym); + } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { + return State->get<IteratorRegionMap>(LCVal->getRegion()); + } + return nullptr; +} + +static const IteratorPosition *getIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym) { + if (RegOrSym.is<const MemRegion *>()) { + return State->get<IteratorRegionMap>(RegOrSym.get<const MemRegion *>()); + } else if (RegOrSym.is<SymbolRef>()) { + return State->get<IteratorSymbolMap>(RegOrSym.get<SymbolRef>()); + } + return nullptr; +} + +static ProgramStateRef setIteratorPosition(ProgramStateRef State, + const SVal &Val, + IteratorPosition Pos) { + if (const auto Reg = Val.getAsRegion()) { + return State->set<IteratorRegionMap>(Reg, Pos); + } else if (const auto Sym = Val.getAsSymbol()) { + return State->set<IteratorSymbolMap>(Sym, Pos); + } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { + return State->set<IteratorRegionMap>(LCVal->getRegion(), Pos); + } + return nullptr; +} + +static ProgramStateRef setIteratorPosition(ProgramStateRef State, + RegionOrSymbol RegOrSym, + IteratorPosition Pos) { + if (RegOrSym.is<const MemRegion *>()) { + return State->set<IteratorRegionMap>(RegOrSym.get<const MemRegion *>(), + Pos); + } else if (RegOrSym.is<SymbolRef>()) { + return State->set<IteratorSymbolMap>(RegOrSym.get<SymbolRef>(), Pos); + } + return nullptr; +} + +static 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; + } +} + +static bool contradictingIteratorPositions(IteratorPosition Pos1, + IteratorPosition Pos2, bool Equal) { + return ((Pos1 != Pos2) && Equal) || + ((Pos1.isOutofRange() && Pos2.isOutofRange()) && !Equal); +} +} + +void ento::registerIteratorPastEndChecker(CheckerManager &Mgr) { + Mgr.registerChecker<IteratorPastEndChecker>(); +} Index: lib/StaticAnalyzer/Checkers/CMakeLists.txt =================================================================== --- lib/StaticAnalyzer/Checkers/CMakeLists.txt +++ lib/StaticAnalyzer/Checkers/CMakeLists.txt @@ -38,6 +38,7 @@ FixedAddressChecker.cpp GenericTaintChecker.cpp IdenticalExprChecker.cpp + IteratorPastEndChecker.cpp IvarInvalidationChecker.cpp LLVMConventionsChecker.cpp LocalizationChecker.cpp Index: include/clang/StaticAnalyzer/Checkers/Checkers.td =================================================================== --- include/clang/StaticAnalyzer/Checkers/Checkers.td +++ include/clang/StaticAnalyzer/Checkers/Checkers.td @@ -268,6 +268,10 @@ HelpText<"Check virtual function calls during construction or destruction">, DescFile<"VirtualCallChecker.cpp">; +def IteratorPastEndChecker : Checker<"IteratorPastEnd">, + HelpText<"Check iterators used past end">, + DescFile<"IteratorPastEndChecker.cpp">; + } // end: "alpha.cplusplus"
_______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits