| //===-- 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_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; |
| 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<CXXInstanceCall>(&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<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 { |
| // Copy state of iterator arguments to iterator parameters |
| 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 { |
| // 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<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 { |
| /* 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<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 { |
| // 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<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 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) { |
| 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<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)); |
| } |
| |
| 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<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; |
| } |
| |
| 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<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 |
| } |
| |
| 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(); |
| } |
| |
| 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<IteratorComparisonMap>(Condition, |
| IteratorComparison(Left, Right, Eq)); |
| } |
| |
| const IteratorComparison *loadComparison(ProgramStateRef State, |
| const SymExpr *Condition) { |
| return State->get<IteratorComparisonMap>(Condition); |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } |
| |
| 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; |
| } |
| |
| 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<IteratorPastEndChecker>(); |
| } |