diff options
Diffstat (limited to 'lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp | 840 |
1 files changed, 0 insertions, 840 deletions
diff --git a/lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp b/lib/StaticAnalyzer/Checkers/IteratorPastEndChecker.cpp deleted file mode 100644 index f0f7c98c9640..000000000000 --- a/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 <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_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>(); -} |