diff options
Diffstat (limited to 'clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp')
| -rw-r--r-- | clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp | 2542 |
1 files changed, 0 insertions, 2542 deletions
diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp deleted file mode 100644 index 7ed11146397..00000000000 --- a/clang/lib/StaticAnalyzer/Checkers/IteratorChecker.cpp +++ /dev/null @@ -1,2542 +0,0 @@ -//===-- IteratorChecker.cpp ---------------------------------------*- C++ -*--// -// -// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. -// See https://llvm.org/LICENSE.txt for license information. -// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception -// -//===----------------------------------------------------------------------===// -// -// Defines a checker for using iterators outside their range (past end). Usage -// means here dereferencing, incrementing etc. -// -//===----------------------------------------------------------------------===// -// -// In the code, iterator can be represented as a: -// * type-I: typedef-ed pointer. Operations over such iterator, such as -// comparisons or increments, are modeled straightforwardly by the -// analyzer. -// * type-II: structure with its method bodies available. Operations over such -// iterator are inlined by the analyzer, and results of modeling -// these operations are exposing implementation details of the -// iterators, which is not necessarily helping. -// * type-III: completely opaque structure. Operations over such iterator are -// modeled conservatively, producing conjured symbols everywhere. -// -// To handle all these types in a common way we introduce a structure called -// IteratorPosition which is an abstraction of the position the iterator -// represents using symbolic expressions. The checker handles all the -// operations on this structure. -// -// Additionally, depending on the circumstances, operators of types II and III -// can be represented as: -// * type-IIa, type-IIIa: conjured structure symbols - when returned by value -// from conservatively evaluated methods such as -// `.begin()`. -// * type-IIb, type-IIIb: memory regions of iterator-typed objects, such as -// variables or temporaries, when the iterator object is -// currently treated as an lvalue. -// * type-IIc, type-IIIc: compound values of iterator-typed objects, when the -// iterator object is treated as an rvalue taken of a -// particular lvalue, eg. a copy of "type-a" iterator -// object, or an iterator that existed before the -// analysis has started. -// -// To handle any of these three different representations stored in an SVal we -// use setter and getters functions which separate the three cases. To store -// them we use a pointer union of symbol and memory region. -// -// The checker works the following way: We record the begin and the -// past-end iterator for all containers whenever their `.begin()` and `.end()` -// are called. Since the Constraint Manager cannot handle such SVals we need -// to take over its role. We post-check equality and non-equality comparisons -// and record that the two sides are equal if we are in the 'equal' branch -// (true-branch for `==` and false-branch for `!=`). -// -// In case of type-I or type-II iterators we get a concrete integer as a result -// of the comparison (1 or 0) but in case of type-III we only get a Symbol. In -// this latter case we record the symbol and reload it in evalAssume() and do -// the propagation there. We also handle (maybe double) negated comparisons -// which are represented in the form of (x == 0 or x != 0) where x is the -// comparison itself. -// -// Since `SimpleConstraintManager` cannot handle complex symbolic expressions -// we only use expressions of the format S, S+n or S-n for iterator positions -// where S is a conjured symbol and n is an unsigned concrete integer. When -// making an assumption e.g. `S1 + n == S2 + m` we store `S1 - S2 == m - n` as -// a constraint which we later retrieve when doing an actual comparison. - -#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h" -#include "clang/AST/DeclTemplate.h" -#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" -#include "clang/StaticAnalyzer/Core/Checker.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h" - -#include <utility> - -using namespace clang; -using namespace ento; - -namespace { - -// Abstract position of an iterator. This helps to handle all three kinds -// of operators in a common way by using a symbolic position. -struct IteratorPosition { -private: - - // Container the iterator belongs to - const MemRegion *Cont; - - // Whether iterator is valid - const bool Valid; - - // Abstract offset - const SymbolRef Offset; - - IteratorPosition(const MemRegion *C, bool V, SymbolRef Of) - : Cont(C), Valid(V), Offset(Of) {} - -public: - const MemRegion *getContainer() const { return Cont; } - bool isValid() const { return Valid; } - SymbolRef getOffset() const { return Offset; } - - IteratorPosition invalidate() const { - return IteratorPosition(Cont, false, Offset); - } - - static IteratorPosition getPosition(const MemRegion *C, SymbolRef Of) { - return IteratorPosition(C, true, Of); - } - - IteratorPosition setTo(SymbolRef NewOf) const { - return IteratorPosition(Cont, Valid, NewOf); - } - - IteratorPosition reAssign(const MemRegion *NewCont) const { - return IteratorPosition(NewCont, Valid, Offset); - } - - bool operator==(const IteratorPosition &X) const { - return Cont == X.Cont && Valid == X.Valid && Offset == X.Offset; - } - - bool operator!=(const IteratorPosition &X) const { - return Cont != X.Cont || Valid != X.Valid || Offset != X.Offset; - } - - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddPointer(Cont); - ID.AddInteger(Valid); - ID.Add(Offset); - } -}; - -// Structure to record the symbolic begin and end position of a container -struct ContainerData { -private: - const SymbolRef Begin, End; - - ContainerData(SymbolRef B, SymbolRef E) : Begin(B), End(E) {} - -public: - static ContainerData fromBegin(SymbolRef B) { - return ContainerData(B, nullptr); - } - - static ContainerData fromEnd(SymbolRef E) { - return ContainerData(nullptr, E); - } - - SymbolRef getBegin() const { return Begin; } - SymbolRef getEnd() const { return End; } - - ContainerData newBegin(SymbolRef B) const { return ContainerData(B, End); } - - ContainerData newEnd(SymbolRef E) const { return ContainerData(Begin, E); } - - bool operator==(const ContainerData &X) const { - return Begin == X.Begin && End == X.End; - } - - bool operator!=(const ContainerData &X) const { - return Begin != X.Begin || End != X.End; - } - - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.Add(Begin); - ID.Add(End); - } -}; - -class IteratorChecker - : public Checker<check::PreCall, check::PostCall, - check::PostStmt<MaterializeTemporaryExpr>, check::Bind, - check::LiveSymbols, check::DeadSymbols, eval::Call> { - - std::unique_ptr<BugType> OutOfRangeBugType; - std::unique_ptr<BugType> MismatchedBugType; - std::unique_ptr<BugType> InvalidatedBugType; - std::unique_ptr<BugType> DebugMsgBugType; - - void handleComparison(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const SVal &LVal, const SVal &RVal, - OverloadedOperatorKind Op) const; - void processComparison(CheckerContext &C, ProgramStateRef State, - SymbolRef Sym1, SymbolRef Sym2, const SVal &RetVal, - OverloadedOperatorKind Op) const; - void verifyAccess(CheckerContext &C, const SVal &Val) const; - void verifyDereference(CheckerContext &C, const SVal &Val) const; - void handleIncrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, - bool Postfix) const; - void handleDecrement(CheckerContext &C, const SVal &RetVal, const SVal &Iter, - bool Postfix) const; - void handleRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, - const SVal &RetVal, const SVal &LHS, - const SVal &RHS) const; - void handleBegin(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const SVal &Cont) const; - void handleEnd(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const SVal &Cont) const; - void assignToContainer(CheckerContext &C, const Expr *CE, const SVal &RetVal, - const MemRegion *Cont) const; - void handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE = nullptr, - const SVal &OldCont = UndefinedVal()) const; - void handleClear(CheckerContext &C, const SVal &Cont) const; - void handlePushBack(CheckerContext &C, const SVal &Cont) const; - void handlePopBack(CheckerContext &C, const SVal &Cont) const; - void handlePushFront(CheckerContext &C, const SVal &Cont) const; - void handlePopFront(CheckerContext &C, const SVal &Cont) const; - void handleInsert(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter) const; - void handleErase(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter) const; - void handleEraseAfter(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; - void verifyIncrement(CheckerContext &C, const SVal &Iter) const; - void verifyDecrement(CheckerContext &C, const SVal &Iter) const; - void verifyRandomIncrOrDecr(CheckerContext &C, OverloadedOperatorKind Op, - const SVal &LHS, const SVal &RHS) const; - void verifyMatch(CheckerContext &C, const SVal &Iter, - const MemRegion *Cont) const; - void verifyMatch(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const; - IteratorPosition advancePosition(CheckerContext &C, OverloadedOperatorKind Op, - const IteratorPosition &Pos, - const SVal &Distance) const; - void reportOutOfRangeBug(const StringRef &Message, const SVal &Val, - CheckerContext &C, ExplodedNode *ErrNode) const; - void reportMismatchedBug(const StringRef &Message, const SVal &Val1, - const SVal &Val2, CheckerContext &C, - ExplodedNode *ErrNode) const; - void reportMismatchedBug(const StringRef &Message, const SVal &Val, - const MemRegion *Reg, CheckerContext &C, - ExplodedNode *ErrNode) const; - void reportInvalidatedBug(const StringRef &Message, const SVal &Val, - CheckerContext &C, ExplodedNode *ErrNode) const; - template <typename Getter> - void analyzerContainerDataField(const CallExpr *CE, CheckerContext &C, - Getter get) const; - void analyzerContainerBegin(const CallExpr *CE, CheckerContext &C) const; - void analyzerContainerEnd(const CallExpr *CE, CheckerContext &C) const; - template <typename Getter> - void analyzerIteratorDataField(const CallExpr *CE, CheckerContext &C, - Getter get, SVal Default) const; - void analyzerIteratorPosition(const CallExpr *CE, CheckerContext &C) const; - void analyzerIteratorContainer(const CallExpr *CE, CheckerContext &C) const; - void analyzerIteratorValidity(const CallExpr *CE, CheckerContext &C) const; - ExplodedNode *reportDebugMsg(llvm::StringRef Msg, CheckerContext &C) const; - - typedef void (IteratorChecker::*FnCheck)(const CallExpr *, - CheckerContext &) const; - - CallDescriptionMap<FnCheck> Callbacks = { - {{0, "clang_analyzer_container_begin", 1}, - &IteratorChecker::analyzerContainerBegin}, - {{0, "clang_analyzer_container_end", 1}, - &IteratorChecker::analyzerContainerEnd}, - {{0, "clang_analyzer_iterator_position", 1}, - &IteratorChecker::analyzerIteratorPosition}, - {{0, "clang_analyzer_iterator_container", 1}, - &IteratorChecker::analyzerIteratorContainer}, - {{0, "clang_analyzer_iterator_validity", 1}, - &IteratorChecker::analyzerIteratorValidity}, - }; - -public: - IteratorChecker(); - - enum CheckKind { - CK_IteratorRangeChecker, - CK_MismatchedIteratorChecker, - CK_InvalidatedIteratorChecker, - CK_DebugIteratorModeling, - CK_NumCheckKinds - }; - - DefaultBool ChecksEnabled[CK_NumCheckKinds]; - CheckerNameRef CheckNames[CK_NumCheckKinds]; - - void checkPreCall(const CallEvent &Call, CheckerContext &C) const; - void checkPostCall(const CallEvent &Call, CheckerContext &C) const; - void checkBind(SVal Loc, SVal Val, const Stmt *S, CheckerContext &C) const; - void checkPostStmt(const CXXConstructExpr *CCE, CheckerContext &C) const; - void checkPostStmt(const DeclStmt *DS, CheckerContext &C) const; - void checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const; - void checkLiveSymbols(ProgramStateRef State, SymbolReaper &SR) const; - void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const; - bool evalCall(const CallEvent &Call, CheckerContext &C) const; -}; -} // namespace - -REGISTER_MAP_WITH_PROGRAMSTATE(IteratorSymbolMap, SymbolRef, IteratorPosition) -REGISTER_MAP_WITH_PROGRAMSTATE(IteratorRegionMap, const MemRegion *, - IteratorPosition) - -REGISTER_MAP_WITH_PROGRAMSTATE(ContainerMap, const MemRegion *, ContainerData) - -namespace { - -bool isIteratorType(const QualType &Type); -bool isIterator(const CXXRecordDecl *CRD); -bool isComparisonOperator(OverloadedOperatorKind OK); -bool isBeginCall(const FunctionDecl *Func); -bool isEndCall(const FunctionDecl *Func); -bool isAssignCall(const FunctionDecl *Func); -bool isClearCall(const FunctionDecl *Func); -bool isPushBackCall(const FunctionDecl *Func); -bool isEmplaceBackCall(const FunctionDecl *Func); -bool isPopBackCall(const FunctionDecl *Func); -bool isPushFrontCall(const FunctionDecl *Func); -bool isEmplaceFrontCall(const FunctionDecl *Func); -bool isPopFrontCall(const FunctionDecl *Func); -bool isInsertCall(const FunctionDecl *Func); -bool isEraseCall(const FunctionDecl *Func); -bool isEraseAfterCall(const FunctionDecl *Func); -bool isEmplaceCall(const FunctionDecl *Func); -bool isAssignmentOperator(OverloadedOperatorKind OK); -bool isSimpleComparisonOperator(OverloadedOperatorKind OK); -bool isAccessOperator(OverloadedOperatorKind OK); -bool isDereferenceOperator(OverloadedOperatorKind OK); -bool isIncrementOperator(OverloadedOperatorKind OK); -bool isDecrementOperator(OverloadedOperatorKind OK); -bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK); -bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg); -bool frontModifiable(ProgramStateRef State, const MemRegion *Reg); -bool backModifiable(ProgramStateRef State, const MemRegion *Reg); -SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont); -SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont); -ProgramStateRef createContainerBegin(ProgramStateRef State, - const MemRegion *Cont, const Expr *E, - QualType T, const LocationContext *LCtx, - unsigned BlockCount); -ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, - const Expr *E, QualType T, - const LocationContext *LCtx, - unsigned BlockCount); -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - const SVal &Val); -ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, - const IteratorPosition &Pos); -ProgramStateRef removeIteratorPosition(ProgramStateRef State, const SVal &Val); -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale); -ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont); -ProgramStateRef -invalidateAllIteratorPositionsExcept(ProgramStateRef State, - const MemRegion *Cont, SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset1, - BinaryOperator::Opcode Opc1, - SymbolRef Offset2, - BinaryOperator::Opcode Opc2); -ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont); -ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont, - SymbolRef Offset, - BinaryOperator::Opcode Opc); -ProgramStateRef rebaseSymbolInIteratorPositionsIf( - ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, - SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc); -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal); -const ContainerData *getContainerData(ProgramStateRef State, - const MemRegion *Cont); -ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, - const ContainerData &CData); -bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont); -bool isBoundThroughLazyCompoundVal(const Environment &Env, - const MemRegion *Reg); -bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); -bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos); -bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos); -bool isZero(ProgramStateRef State, const NonLoc &Val); -} // namespace - -IteratorChecker::IteratorChecker() { - OutOfRangeBugType.reset( - new BugType(this, "Iterator out of range", "Misuse of STL APIs")); - MismatchedBugType.reset( - new BugType(this, "Iterator(s) mismatched", "Misuse of STL APIs", - /*SuppressOnSink=*/true)); - InvalidatedBugType.reset( - new BugType(this, "Iterator invalidated", "Misuse of STL APIs")); - DebugMsgBugType.reset( - new BugType(this, "Checking analyzer assumptions", "debug", - /*SuppressOnSink=*/true)); -} - -void IteratorChecker::checkPreCall(const CallEvent &Call, - CheckerContext &C) const { - // Check for out of range access or access of invalidated position and - // iterator mismatches - const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); - if (!Func) - return; - - if (Func->isOverloadedOperator()) { - if (ChecksEnabled[CK_InvalidatedIteratorChecker] && - isAccessOperator(Func->getOverloadedOperator())) { - // Check for any kind of access of invalidated iterator positions - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - verifyAccess(C, InstCall->getCXXThisVal()); - } else { - verifyAccess(C, Call.getArgSVal(0)); - } - } - if (ChecksEnabled[CK_IteratorRangeChecker]) { - if (isIncrementOperator(Func->getOverloadedOperator())) { - // Check for out-of-range incrementions - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - verifyIncrement(C, InstCall->getCXXThisVal()); - } else { - if (Call.getNumArgs() >= 1) { - verifyIncrement(C, Call.getArgSVal(0)); - } - } - } else if (isDecrementOperator(Func->getOverloadedOperator())) { - // Check for out-of-range decrementions - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - verifyDecrement(C, InstCall->getCXXThisVal()); - } else { - if (Call.getNumArgs() >= 1) { - verifyDecrement(C, Call.getArgSVal(0)); - } - } - } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - // Check for out-of-range incrementions and decrementions - if (Call.getNumArgs() >= 1 && - Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { - verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), - InstCall->getCXXThisVal(), - Call.getArgSVal(0)); - } - } else { - if (Call.getNumArgs() >= 2 && - Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { - verifyRandomIncrOrDecr(C, Func->getOverloadedOperator(), - Call.getArgSVal(0), Call.getArgSVal(1)); - } - } - } else if (isDereferenceOperator(Func->getOverloadedOperator())) { - // Check for dereference of out-of-range iterators - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - verifyDereference(C, InstCall->getCXXThisVal()); - } else { - verifyDereference(C, Call.getArgSVal(0)); - } - } - } else if (ChecksEnabled[CK_MismatchedIteratorChecker] && - isComparisonOperator(Func->getOverloadedOperator())) { - // Check for comparisons of iterators of different containers - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - if (Call.getNumArgs() < 1) - return; - - if (!isIteratorType(InstCall->getCXXThisExpr()->getType()) || - !isIteratorType(Call.getArgExpr(0)->getType())) - return; - - verifyMatch(C, InstCall->getCXXThisVal(), Call.getArgSVal(0)); - } else { - if (Call.getNumArgs() < 2) - return; - - if (!isIteratorType(Call.getArgExpr(0)->getType()) || - !isIteratorType(Call.getArgExpr(1)->getType())) - return; - - verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); - } - } - } else if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - if (!ChecksEnabled[CK_MismatchedIteratorChecker]) - return; - - const auto *ContReg = InstCall->getCXXThisVal().getAsRegion(); - if (!ContReg) - return; - // Check for erase, insert and emplace using iterator of another container - if (isEraseCall(Func) || isEraseAfterCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); - if (Call.getNumArgs() == 2) { - verifyMatch(C, Call.getArgSVal(1), - InstCall->getCXXThisVal().getAsRegion()); - } - } else if (isInsertCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); - if (Call.getNumArgs() == 3 && - isIteratorType(Call.getArgExpr(1)->getType()) && - isIteratorType(Call.getArgExpr(2)->getType())) { - verifyMatch(C, Call.getArgSVal(1), Call.getArgSVal(2)); - } - } else if (isEmplaceCall(Func)) { - verifyMatch(C, Call.getArgSVal(0), - InstCall->getCXXThisVal().getAsRegion()); - } - } else if (isa<CXXConstructorCall>(&Call)) { - // Check match of first-last iterator pair in a constructor of a container - if (Call.getNumArgs() < 2) - return; - - const auto *Ctr = cast<CXXConstructorDecl>(Call.getDecl()); - if (Ctr->getNumParams() < 2) - return; - - if (Ctr->getParamDecl(0)->getName() != "first" || - Ctr->getParamDecl(1)->getName() != "last") - return; - - if (!isIteratorType(Call.getArgExpr(0)->getType()) || - !isIteratorType(Call.getArgExpr(1)->getType())) - return; - - verifyMatch(C, Call.getArgSVal(0), Call.getArgSVal(1)); - } else { - // The main purpose of iterators is to abstract away from different - // containers and provide a (maybe limited) uniform access to them. - // This implies that any correctly written template function that - // works on multiple containers using iterators takes different - // template parameters for different containers. So we can safely - // assume that passing iterators of different containers as arguments - // whose type replaces the same template parameter is a bug. - // - // Example: - // template<typename I1, typename I2> - // void f(I1 first1, I1 last1, I2 first2, I2 last2); - // - // In this case the first two arguments to f() must be iterators must belong - // to the same container and the last to also to the same container but - // not necessarily to the same as the first two. - - if (!ChecksEnabled[CK_MismatchedIteratorChecker]) - return; - - const auto *Templ = Func->getPrimaryTemplate(); - if (!Templ) - return; - - const auto *TParams = Templ->getTemplateParameters(); - const auto *TArgs = Func->getTemplateSpecializationArgs(); - - // Iterate over all the template parameters - for (size_t I = 0; I < TParams->size(); ++I) { - const auto *TPDecl = dyn_cast<TemplateTypeParmDecl>(TParams->getParam(I)); - if (!TPDecl) - continue; - - if (TPDecl->isParameterPack()) - continue; - - const auto TAType = TArgs->get(I).getAsType(); - if (!isIteratorType(TAType)) - continue; - - SVal LHS = UndefinedVal(); - - // For every template parameter which is an iterator type in the - // instantiation look for all functions' parameters' type by it and - // check whether they belong to the same container - for (auto J = 0U; J < Func->getNumParams(); ++J) { - const auto *Param = Func->getParamDecl(J); - const auto *ParamType = - Param->getType()->getAs<SubstTemplateTypeParmType>(); - if (!ParamType || - ParamType->getReplacedParameter()->getDecl() != TPDecl) - continue; - if (LHS.isUndef()) { - LHS = Call.getArgSVal(J); - } else { - verifyMatch(C, LHS, Call.getArgSVal(J)); - } - } - } - } -} - -void IteratorChecker::checkPostCall(const CallEvent &Call, - CheckerContext &C) const { - // Record new iterator positions and iterator position changes - const auto *Func = dyn_cast_or_null<FunctionDecl>(Call.getDecl()); - if (!Func) - return; - - if (Func->isOverloadedOperator()) { - const auto Op = Func->getOverloadedOperator(); - if (isAssignmentOperator(Op)) { - // Overloaded 'operator=' must be a non-static member function. - const auto *InstCall = cast<CXXInstanceCall>(&Call); - if (cast<CXXMethodDecl>(Func)->isMoveAssignmentOperator()) { - handleAssign(C, InstCall->getCXXThisVal(), Call.getOriginExpr(), - Call.getArgSVal(0)); - return; - } - - handleAssign(C, InstCall->getCXXThisVal()); - return; - } else if (isSimpleComparisonOperator(Op)) { - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - handleComparison(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0), Op); - return; - } - - handleComparison(C, OrigExpr, Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1), Op); - return; - } else if (isRandomIncrOrDecrOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - if (Call.getNumArgs() >= 1 && - Call.getArgExpr(0)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), - Call.getReturnValue(), - InstCall->getCXXThisVal(), Call.getArgSVal(0)); - return; - } - } else { - if (Call.getNumArgs() >= 2 && - Call.getArgExpr(1)->getType()->isIntegralOrEnumerationType()) { - handleRandomIncrOrDecr(C, Func->getOverloadedOperator(), - Call.getReturnValue(), Call.getArgSVal(0), - Call.getArgSVal(1)); - return; - } - } - } else if (isIncrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - handleIncrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } - - handleIncrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); - return; - } else if (isDecrementOperator(Func->getOverloadedOperator())) { - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - handleDecrement(C, Call.getReturnValue(), InstCall->getCXXThisVal(), - Call.getNumArgs()); - return; - } - - handleDecrement(C, Call.getReturnValue(), Call.getArgSVal(0), - Call.getNumArgs()); - return; - } - } else { - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - if (isAssignCall(Func)) { - handleAssign(C, InstCall->getCXXThisVal()); - return; - } - - if (isClearCall(Func)) { - handleClear(C, InstCall->getCXXThisVal()); - return; - } - - if (isPushBackCall(Func) || isEmplaceBackCall(Func)) { - handlePushBack(C, InstCall->getCXXThisVal()); - return; - } - - if (isPopBackCall(Func)) { - handlePopBack(C, InstCall->getCXXThisVal()); - return; - } - - if (isPushFrontCall(Func) || isEmplaceFrontCall(Func)) { - handlePushFront(C, InstCall->getCXXThisVal()); - return; - } - - if (isPopFrontCall(Func)) { - handlePopFront(C, InstCall->getCXXThisVal()); - return; - } - - if (isInsertCall(Func) || isEmplaceCall(Func)) { - handleInsert(C, Call.getArgSVal(0)); - return; - } - - if (isEraseCall(Func)) { - if (Call.getNumArgs() == 1) { - handleErase(C, Call.getArgSVal(0)); - return; - } - - if (Call.getNumArgs() == 2) { - handleErase(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - - if (isEraseAfterCall(Func)) { - if (Call.getNumArgs() == 1) { - handleEraseAfter(C, Call.getArgSVal(0)); - return; - } - - if (Call.getNumArgs() == 2) { - handleEraseAfter(C, Call.getArgSVal(0), Call.getArgSVal(1)); - return; - } - } - } - - const auto *OrigExpr = Call.getOriginExpr(); - if (!OrigExpr) - return; - - if (!isIteratorType(Call.getResultType())) - return; - - auto State = C.getState(); - - if (const auto *InstCall = dyn_cast<CXXInstanceCall>(&Call)) { - if (isBeginCall(Func)) { - handleBegin(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); - return; - } - - if (isEndCall(Func)) { - handleEnd(C, OrigExpr, Call.getReturnValue(), - InstCall->getCXXThisVal()); - return; - } - } - - // Already bound to container? - if (getIteratorPosition(State, Call.getReturnValue())) - return; - - // Copy-like and move constructors - if (isa<CXXConstructorCall>(&Call) && Call.getNumArgs() == 1) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(0))) { - State = setIteratorPosition(State, Call.getReturnValue(), *Pos); - if (cast<CXXConstructorDecl>(Func)->isMoveConstructor()) { - State = removeIteratorPosition(State, Call.getArgSVal(0)); - } - C.addTransition(State); - return; - } - } - - // Assumption: if return value is an iterator which is not yet bound to a - // container, then look for the first iterator argument, and - // bind the return value to the same container. This approach - // works for STL algorithms. - // FIXME: Add a more conservative mode - for (unsigned i = 0; i < Call.getNumArgs(); ++i) { - if (isIteratorType(Call.getArgExpr(i)->getType())) { - if (const auto *Pos = getIteratorPosition(State, Call.getArgSVal(i))) { - assignToContainer(C, OrigExpr, Call.getReturnValue(), - Pos->getContainer()); - return; - } - } - } - } -} - -void IteratorChecker::checkBind(SVal Loc, SVal Val, const Stmt *S, - CheckerContext &C) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos) { - State = setIteratorPosition(State, Loc, *Pos); - C.addTransition(State); - } else { - const auto *OldPos = getIteratorPosition(State, Loc); - if (OldPos) { - State = removeIteratorPosition(State, Loc); - C.addTransition(State); - } - } -} - -void IteratorChecker::checkPostStmt(const MaterializeTemporaryExpr *MTE, - CheckerContext &C) const { - /* Transfer iterator state to temporary objects */ - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, C.getSVal(MTE->getSubExpr())); - if (!Pos) - return; - State = setIteratorPosition(State, C.getSVal(MTE), *Pos); - C.addTransition(State); -} - -void IteratorChecker::checkLiveSymbols(ProgramStateRef State, - SymbolReaper &SR) const { - // Keep symbolic expressions of iterator positions, container begins and ends - // alive - auto RegionMap = State->get<IteratorRegionMap>(); - for (const auto Reg : RegionMap) { - const auto Offset = Reg.second.getOffset(); - for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) - if (isa<SymbolData>(*i)) - SR.markLive(*i); - } - - auto SymbolMap = State->get<IteratorSymbolMap>(); - for (const auto Sym : SymbolMap) { - const auto Offset = Sym.second.getOffset(); - for (auto i = Offset->symbol_begin(); i != Offset->symbol_end(); ++i) - if (isa<SymbolData>(*i)) - SR.markLive(*i); - } - - auto ContMap = State->get<ContainerMap>(); - for (const auto Cont : ContMap) { - const auto CData = Cont.second; - if (CData.getBegin()) { - SR.markLive(CData.getBegin()); - if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getBegin())) - SR.markLive(SIE->getLHS()); - } - if (CData.getEnd()) { - SR.markLive(CData.getEnd()); - if(const auto *SIE = dyn_cast<SymIntExpr>(CData.getEnd())) - SR.markLive(SIE->getLHS()); - } - } -} - -void IteratorChecker::checkDeadSymbols(SymbolReaper &SR, - CheckerContext &C) const { - // Cleanup - auto State = C.getState(); - - auto RegionMap = State->get<IteratorRegionMap>(); - for (const auto Reg : RegionMap) { - if (!SR.isLiveRegion(Reg.first)) { - // The region behind the `LazyCompoundVal` is often cleaned up before - // the `LazyCompoundVal` itself. If there are iterator positions keyed - // by these regions their cleanup must be deferred. - if (!isBoundThroughLazyCompoundVal(State->getEnvironment(), Reg.first)) { - State = State->remove<IteratorRegionMap>(Reg.first); - } - } - } - - auto SymbolMap = State->get<IteratorSymbolMap>(); - for (const auto Sym : SymbolMap) { - if (!SR.isLive(Sym.first)) { - State = State->remove<IteratorSymbolMap>(Sym.first); - } - } - - auto ContMap = State->get<ContainerMap>(); - for (const auto Cont : ContMap) { - if (!SR.isLiveRegion(Cont.first)) { - // We must keep the container data while it has live iterators to be able - // to compare them to the begin and the end of the container. - if (!hasLiveIterators(State, Cont.first)) { - State = State->remove<ContainerMap>(Cont.first); - } - } - } - - C.addTransition(State); -} - -void IteratorChecker::handleComparison(CheckerContext &C, const Expr *CE, - 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(); - const auto *LPos = getIteratorPosition(State, LVal); - const auto *RPos = getIteratorPosition(State, RVal); - const MemRegion *Cont = nullptr; - if (LPos) { - Cont = LPos->getContainer(); - } else if (RPos) { - Cont = RPos->getContainer(); - } - if (!Cont) - return; - - // At least one of the iterators have recorded positions. If one of them has - // not then create a new symbol for the offset. - SymbolRef Sym; - if (!LPos || !RPos) { - auto &SymMgr = C.getSymbolManager(); - Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, Sym, 4); - } - - if (!LPos) { - State = setIteratorPosition(State, LVal, - IteratorPosition::getPosition(Cont, Sym)); - LPos = getIteratorPosition(State, LVal); - } else if (!RPos) { - State = setIteratorPosition(State, RVal, - IteratorPosition::getPosition(Cont, Sym)); - RPos = getIteratorPosition(State, RVal); - } - - processComparison(C, State, LPos->getOffset(), RPos->getOffset(), RetVal, Op); -} - -void IteratorChecker::processComparison(CheckerContext &C, - ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, const SVal &RetVal, - OverloadedOperatorKind Op) const { - if (const auto TruthVal = RetVal.getAs<nonloc::ConcreteInt>()) { - if ((State = relateSymbols(State, Sym1, Sym2, - (Op == OO_EqualEqual) == - (TruthVal->getValue() != 0)))) { - C.addTransition(State); - } else { - C.generateSink(State, C.getPredecessor()); - } - return; - } - - const auto ConditionVal = RetVal.getAs<DefinedSVal>(); - if (!ConditionVal) - return; - - if (auto StateTrue = relateSymbols(State, Sym1, Sym2, Op == OO_EqualEqual)) { - StateTrue = StateTrue->assume(*ConditionVal, true); - C.addTransition(StateTrue); - } - - if (auto StateFalse = relateSymbols(State, Sym1, Sym2, Op != OO_EqualEqual)) { - StateFalse = StateFalse->assume(*ConditionVal, false); - C.addTransition(StateFalse); - } -} - -void IteratorChecker::verifyDereference(CheckerContext &C, - const SVal &Val) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos && isPastTheEnd(State, *Pos)) { - auto *N = C.generateErrorNode(State); - if (!N) - return; - reportOutOfRangeBug("Past-the-end iterator dereferenced.", Val, C, N); - return; - } -} - -void IteratorChecker::verifyAccess(CheckerContext &C, const SVal &Val) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Val); - if (Pos && !Pos->isValid()) { - auto *N = C.generateErrorNode(State); - if (!N) { - return; - } - reportInvalidatedBug("Invalidated iterator accessed.", Val, C, N); - } -} - -void IteratorChecker::handleIncrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { - // Increment the symbolic expressions which represents the position of the - // iterator - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (Pos) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - const auto NewPos = - advancePosition(C, OO_Plus, *Pos, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); - State = setIteratorPosition(State, Iter, NewPos); - State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); - C.addTransition(State); - } -} - -void IteratorChecker::handleDecrement(CheckerContext &C, const SVal &RetVal, - const SVal &Iter, bool Postfix) const { - // Decrement the symbolic expressions which represents the position of the - // iterator - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (Pos) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - const auto NewPos = - advancePosition(C, OO_Minus, *Pos, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); - State = setIteratorPosition(State, Iter, NewPos); - State = setIteratorPosition(State, RetVal, Postfix ? *Pos : NewPos); - C.addTransition(State); - } -} - -void IteratorChecker::handleRandomIncrOrDecr(CheckerContext &C, - OverloadedOperatorKind Op, - const SVal &RetVal, - const SVal &LHS, - const SVal &RHS) const { - // Increment or decrement the symbolic expressions which represents the - // position of the iterator - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, LHS); - if (!Pos) - return; - - const auto *value = &RHS; - if (auto loc = RHS.getAs<Loc>()) { - const auto val = State->getRawSVal(*loc); - value = &val; - } - - auto &TgtVal = (Op == OO_PlusEqual || Op == OO_MinusEqual) ? LHS : RetVal; - State = - setIteratorPosition(State, TgtVal, advancePosition(C, Op, *Pos, *value)); - C.addTransition(State); -} - -void IteratorChecker::verifyIncrement(CheckerContext &C, - const SVal &Iter) const { - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - verifyRandomIncrOrDecr(C, OO_Plus, Iter, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); -} - -void IteratorChecker::verifyDecrement(CheckerContext &C, - const SVal &Iter) const { - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - verifyRandomIncrOrDecr(C, OO_Minus, Iter, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1)))); -} - -void IteratorChecker::verifyRandomIncrOrDecr(CheckerContext &C, - OverloadedOperatorKind Op, - const SVal &LHS, - const SVal &RHS) const { - auto State = C.getState(); - - // If the iterator is initially inside its range, then the operation is valid - const auto *Pos = getIteratorPosition(State, LHS); - if (!Pos) - return; - - auto Value = RHS; - if (auto ValAsLoc = RHS.getAs<Loc>()) { - Value = State->getRawSVal(*ValAsLoc); - } - - if (Value.isUnknown()) - return; - - // Incremention or decremention by 0 is never a bug. - if (isZero(State, Value.castAs<NonLoc>())) - return; - - // The result may be the past-end iterator of the container, but any other - // out of range position is undefined behaviour - if (isAheadOfRange(State, advancePosition(C, Op, *Pos, Value))) { - auto *N = C.generateErrorNode(State); - if (!N) - return; - reportOutOfRangeBug("Iterator decremented ahead of its valid range.", LHS, - C, N); - } - if (isBehindPastTheEnd(State, advancePosition(C, Op, *Pos, Value))) { - auto *N = C.generateErrorNode(State); - if (!N) - return; - reportOutOfRangeBug("Iterator incremented behind the past-the-end " - "iterator.", LHS, C, N); - } -} - -void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter, - const MemRegion *Cont) const { - // Verify match between a container and the container of an iterator - Cont = Cont->getMostDerivedObjectRegion(); - - if (const auto *ContSym = Cont->getSymbolicBase()) { - if (isa<SymbolConjured>(ContSym->getSymbol())) - return; - } - - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - const auto *IterCont = Pos->getContainer(); - - // Skip symbolic regions based on conjured symbols. Two conjured symbols - // may or may not be the same. For example, the same function can return - // the same or a different container but we get different conjured symbols - // for each call. This may cause false positives so omit them from the check. - if (const auto *ContSym = IterCont->getSymbolicBase()) { - if (isa<SymbolConjured>(ContSym->getSymbol())) - return; - } - - if (IterCont != Cont) { - auto *N = C.generateNonFatalErrorNode(State); - if (!N) { - return; - } - reportMismatchedBug("Container accessed using foreign iterator argument.", - Iter, Cont, C, N); - } -} - -void IteratorChecker::verifyMatch(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { - // Verify match between the containers of two iterators - auto State = C.getState(); - const auto *Pos1 = getIteratorPosition(State, Iter1); - if (!Pos1) - return; - - const auto *IterCont1 = Pos1->getContainer(); - - // Skip symbolic regions based on conjured symbols. Two conjured symbols - // may or may not be the same. For example, the same function can return - // the same or a different container but we get different conjured symbols - // for each call. This may cause false positives so omit them from the check. - if (const auto *ContSym = IterCont1->getSymbolicBase()) { - if (isa<SymbolConjured>(ContSym->getSymbol())) - return; - } - - const auto *Pos2 = getIteratorPosition(State, Iter2); - if (!Pos2) - return; - - const auto *IterCont2 = Pos2->getContainer(); - if (const auto *ContSym = IterCont2->getSymbolicBase()) { - if (isa<SymbolConjured>(ContSym->getSymbol())) - return; - } - - if (IterCont1 != IterCont2) { - auto *N = C.generateNonFatalErrorNode(State); - if (!N) - return; - reportMismatchedBug("Iterators of different containers used where the " - "same container is expected.", Iter1, Iter2, C, N); - } -} - -void IteratorChecker::handleBegin(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // If the container already has a begin symbol then use it. Otherwise first - // create a new one. - auto State = C.getState(); - auto BeginSym = getContainerBegin(State, ContReg); - if (!BeginSym) { - State = createContainerBegin(State, ContReg, CE, C.getASTContext().LongTy, - C.getLocationContext(), C.blockCount()); - BeginSym = getContainerBegin(State, ContReg); - } - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(ContReg, BeginSym)); - C.addTransition(State); -} - -void IteratorChecker::handleEnd(CheckerContext &C, const Expr *CE, - const SVal &RetVal, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // If the container already has an end symbol then use it. Otherwise first - // create a new one. - auto State = C.getState(); - auto EndSym = getContainerEnd(State, ContReg); - if (!EndSym) { - State = createContainerEnd(State, ContReg, CE, C.getASTContext().LongTy, - C.getLocationContext(), C.blockCount()); - EndSym = getContainerEnd(State, ContReg); - } - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(ContReg, EndSym)); - C.addTransition(State); -} - -void IteratorChecker::assignToContainer(CheckerContext &C, const Expr *CE, - const SVal &RetVal, - const MemRegion *Cont) const { - Cont = Cont->getMostDerivedObjectRegion(); - - auto State = C.getState(); - auto &SymMgr = C.getSymbolManager(); - auto Sym = SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, Sym, 4); - State = setIteratorPosition(State, RetVal, - IteratorPosition::getPosition(Cont, Sym)); - C.addTransition(State); -} - -void IteratorChecker::handleAssign(CheckerContext &C, const SVal &Cont, - const Expr *CE, const SVal &OldCont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // Assignment of a new value to a container always invalidates all its - // iterators - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (CData) { - State = invalidateAllIteratorPositions(State, ContReg); - } - - // In case of move, iterators of the old container (except the past-end - // iterators) remain valid but refer to the new container - if (!OldCont.isUndef()) { - const auto *OldContReg = OldCont.getAsRegion(); - if (OldContReg) { - OldContReg = OldContReg->getMostDerivedObjectRegion(); - const auto OldCData = getContainerData(State, OldContReg); - if (OldCData) { - if (const auto OldEndSym = OldCData->getEnd()) { - // If we already assigned an "end" symbol to the old container, then - // first reassign all iterator positions to the new container which - // are not past the container (thus not greater or equal to the - // current "end" symbol). - State = reassignAllIteratorPositionsUnless(State, OldContReg, ContReg, - OldEndSym, BO_GE); - auto &SymMgr = C.getSymbolManager(); - auto &SVB = C.getSValBuilder(); - // Then generate and assign a new "end" symbol for the new container. - auto NewEndSym = - SymMgr.conjureSymbol(CE, C.getLocationContext(), - C.getASTContext().LongTy, C.blockCount()); - State = assumeNoOverflow(State, NewEndSym, 4); - if (CData) { - State = setContainerData(State, ContReg, CData->newEnd(NewEndSym)); - } else { - State = setContainerData(State, ContReg, - ContainerData::fromEnd(NewEndSym)); - } - // Finally, replace the old "end" symbol in the already reassigned - // iterator positions with the new "end" symbol. - State = rebaseSymbolInIteratorPositionsIf( - State, SVB, OldEndSym, NewEndSym, OldEndSym, BO_LT); - } else { - // There was no "end" symbol assigned yet to the old container, - // so reassign all iterator positions to the new container. - State = reassignAllIteratorPositions(State, OldContReg, ContReg); - } - if (const auto OldBeginSym = OldCData->getBegin()) { - // If we already assigned a "begin" symbol to the old container, then - // assign it to the new container and remove it from the old one. - if (CData) { - State = - setContainerData(State, ContReg, CData->newBegin(OldBeginSym)); - } else { - State = setContainerData(State, ContReg, - ContainerData::fromBegin(OldBeginSym)); - } - State = - setContainerData(State, OldContReg, OldCData->newEnd(nullptr)); - } - } else { - // There was neither "begin" nor "end" symbol assigned yet to the old - // container, so reassign all iterator positions to the new container. - State = reassignAllIteratorPositions(State, OldContReg, ContReg); - } - } - } - C.addTransition(State); -} - -void IteratorChecker::handleClear(CheckerContext &C, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // The clear() operation invalidates all the iterators, except the past-end - // iterators of list-like containers - auto State = C.getState(); - if (!hasSubscriptOperator(State, ContReg) || - !backModifiable(State, ContReg)) { - const auto CData = getContainerData(State, ContReg); - if (CData) { - if (const auto EndSym = CData->getEnd()) { - State = - invalidateAllIteratorPositionsExcept(State, ContReg, EndSym, BO_GE); - C.addTransition(State); - return; - } - } - } - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); -} - -void IteratorChecker::handlePushBack(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // For deque-like containers invalidate all iterator positions - auto State = C.getState(); - if (hasSubscriptOperator(State, ContReg) && frontModifiable(State, ContReg)) { - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); - return; - } - - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - // For vector-like containers invalidate the past-end iterator positions - if (const auto EndSym = CData->getEnd()) { - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - } - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newEndSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(EndSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(EndSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); - } - C.addTransition(State); -} - -void IteratorChecker::handlePopBack(CheckerContext &C, const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - if (const auto EndSym = CData->getEnd()) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto BackSym = - SVB.evalBinOp(State, BO_Sub, - nonloc::SymbolVal(EndSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(EndSym)).getAsSymbol(); - // For vector-like and deque-like containers invalidate the last and the - // past-end iterator positions. For list-like containers only invalidate - // the last position - if (hasSubscriptOperator(State, ContReg) && - backModifiable(State, ContReg)) { - State = invalidateIteratorPositions(State, BackSym, BO_GE); - State = setContainerData(State, ContReg, CData->newEnd(nullptr)); - } else { - State = invalidateIteratorPositions(State, BackSym, BO_EQ); - } - auto newEndSym = BackSym; - State = setContainerData(State, ContReg, CData->newEnd(newEndSym)); - C.addTransition(State); - } -} - -void IteratorChecker::handlePushFront(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - // For deque-like containers invalidate all iterator positions - auto State = C.getState(); - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateAllIteratorPositions(State, ContReg); - C.addTransition(State); - } else { - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - if (const auto BeginSym = CData->getBegin()) { - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newBeginSym = - SVB.evalBinOp(State, BO_Sub, - nonloc::SymbolVal(BeginSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(BeginSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); - C.addTransition(State); - } - } -} - -void IteratorChecker::handlePopFront(CheckerContext &C, - const SVal &Cont) const { - const auto *ContReg = Cont.getAsRegion(); - if (!ContReg) - return; - - ContReg = ContReg->getMostDerivedObjectRegion(); - - auto State = C.getState(); - const auto CData = getContainerData(State, ContReg); - if (!CData) - return; - - // For deque-like containers invalidate all iterator positions. For list-like - // iterators only invalidate the first position - if (const auto BeginSym = CData->getBegin()) { - if (hasSubscriptOperator(State, ContReg)) { - State = invalidateIteratorPositions(State, BeginSym, BO_LE); - } else { - State = invalidateIteratorPositions(State, BeginSym, BO_EQ); - } - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto newBeginSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(BeginSym), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(BeginSym)).getAsSymbol(); - State = setContainerData(State, ContReg, CData->newBegin(newBeginSym)); - C.addTransition(State); - } -} - -void IteratorChecker::handleInsert(CheckerContext &C, const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions after the insertion. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - C.addTransition(State); - } -} - -void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions at and after the - // deletion. For list-like containers only invalidate the deleted position. - const auto *Cont = Pos->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - } else { - State = invalidateIteratorPositions(State, Pos->getOffset(), BO_EQ); - } - C.addTransition(State); -} - -void IteratorChecker::handleErase(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { - auto State = C.getState(); - const auto *Pos1 = getIteratorPosition(State, Iter1); - const auto *Pos2 = getIteratorPosition(State, Iter2); - if (!Pos1 || !Pos2) - return; - - // For deque-like containers invalidate all iterator positions. For - // vector-like containers invalidate iterator positions at and after the - // deletion range. For list-like containers only invalidate the deleted - // position range [first..last]. - const auto *Cont = Pos1->getContainer(); - if (hasSubscriptOperator(State, Cont) && backModifiable(State, Cont)) { - if (frontModifiable(State, Cont)) { - State = invalidateAllIteratorPositions(State, Cont); - } else { - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE); - } - if (const auto *CData = getContainerData(State, Cont)) { - if (const auto EndSym = CData->getEnd()) { - State = invalidateIteratorPositions(State, EndSym, BO_GE); - State = setContainerData(State, Cont, CData->newEnd(nullptr)); - } - } - } else { - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GE, - Pos2->getOffset(), BO_LT); - } - C.addTransition(State); -} - -void IteratorChecker::handleEraseAfter(CheckerContext &C, - const SVal &Iter) const { - auto State = C.getState(); - const auto *Pos = getIteratorPosition(State, Iter); - if (!Pos) - return; - - // Invalidate the deleted iterator position, which is the position of the - // parameter plus one. - auto &SymMgr = C.getSymbolManager(); - auto &BVF = SymMgr.getBasicVals(); - auto &SVB = C.getSValBuilder(); - const auto NextSym = - SVB.evalBinOp(State, BO_Add, - nonloc::SymbolVal(Pos->getOffset()), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(1))), - SymMgr.getType(Pos->getOffset())).getAsSymbol(); - State = invalidateIteratorPositions(State, NextSym, BO_EQ); - C.addTransition(State); -} - -void IteratorChecker::handleEraseAfter(CheckerContext &C, const SVal &Iter1, - const SVal &Iter2) const { - auto State = C.getState(); - const auto *Pos1 = getIteratorPosition(State, Iter1); - const auto *Pos2 = getIteratorPosition(State, Iter2); - if (!Pos1 || !Pos2) - return; - - // Invalidate the deleted iterator position range (first..last) - State = invalidateIteratorPositions(State, Pos1->getOffset(), BO_GT, - Pos2->getOffset(), BO_LT); - C.addTransition(State); -} - -IteratorPosition IteratorChecker::advancePosition(CheckerContext &C, - OverloadedOperatorKind Op, - const IteratorPosition &Pos, - const SVal &Distance) const { - auto State = C.getState(); - auto &SymMgr = C.getSymbolManager(); - auto &SVB = C.getSValBuilder(); - - assert ((Op == OO_Plus || Op == OO_PlusEqual || - Op == OO_Minus || Op == OO_MinusEqual) && - "Advance operator must be one of +, -, += and -=."); - auto BinOp = (Op == OO_Plus || Op == OO_PlusEqual) ? BO_Add : BO_Sub; - if (const auto IntDist = Distance.getAs<nonloc::ConcreteInt>()) { - // For concrete integers we can calculate the new position - return Pos.setTo(SVB.evalBinOp(State, BinOp, - nonloc::SymbolVal(Pos.getOffset()), *IntDist, - SymMgr.getType(Pos.getOffset())) - .getAsSymbol()); - } else { - // For other symbols create a new symbol to keep expressions simple - const auto &LCtx = C.getLocationContext(); - const auto NewPosSym = SymMgr.conjureSymbol(nullptr, LCtx, - SymMgr.getType(Pos.getOffset()), - C.blockCount()); - State = assumeNoOverflow(State, NewPosSym, 4); - return Pos.setTo(NewPosSym); - } -} - -void IteratorChecker::reportOutOfRangeBug(const StringRef &Message, - const SVal &Val, CheckerContext &C, - ExplodedNode *ErrNode) const { - auto R = std::make_unique<PathSensitiveBugReport>(*OutOfRangeBugType, Message, - ErrNode); - R->markInteresting(Val); - C.emitReport(std::move(R)); -} - -void IteratorChecker::reportMismatchedBug(const StringRef &Message, - const SVal &Val1, const SVal &Val2, - CheckerContext &C, - ExplodedNode *ErrNode) const { - auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message, - ErrNode); - R->markInteresting(Val1); - R->markInteresting(Val2); - C.emitReport(std::move(R)); -} - -void IteratorChecker::reportMismatchedBug(const StringRef &Message, - const SVal &Val, const MemRegion *Reg, - CheckerContext &C, - ExplodedNode *ErrNode) const { - auto R = std::make_unique<PathSensitiveBugReport>(*MismatchedBugType, Message, - ErrNode); - R->markInteresting(Val); - R->markInteresting(Reg); - C.emitReport(std::move(R)); -} - -void IteratorChecker::reportInvalidatedBug(const StringRef &Message, - const SVal &Val, CheckerContext &C, - ExplodedNode *ErrNode) const { - auto R = std::make_unique<PathSensitiveBugReport>(*InvalidatedBugType, - Message, ErrNode); - R->markInteresting(Val); - C.emitReport(std::move(R)); -} - -bool IteratorChecker::evalCall(const CallEvent &Call, - CheckerContext &C) const { - if (!ChecksEnabled[CK_DebugIteratorModeling]) - return false; - - const auto *CE = dyn_cast_or_null<CallExpr>(Call.getOriginExpr()); - if (!CE) - return false; - - const FnCheck *Handler = Callbacks.lookup(Call); - if (!Handler) - return false; - - (this->**Handler)(CE, C); - return true; -} - -template <typename Getter> -void IteratorChecker::analyzerContainerDataField(const CallExpr *CE, - CheckerContext &C, - Getter get) const { - if (CE->getNumArgs() == 0) { - reportDebugMsg("Missing container argument", C); - return; - } - - auto State = C.getState(); - const MemRegion *Cont = C.getSVal(CE->getArg(0)).getAsRegion(); - if (Cont) { - const auto *Data = getContainerData(State, Cont); - if (Data) { - SymbolRef Field = get(Data); - if (Field) { - State = State->BindExpr(CE, C.getLocationContext(), - nonloc::SymbolVal(Field)); - C.addTransition(State); - return; - } - } - } - - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - State = State->BindExpr(CE, C.getLocationContext(), - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); -} - -void IteratorChecker::analyzerContainerBegin(const CallExpr *CE, - CheckerContext &C) const { - analyzerContainerDataField(CE, C, [](const ContainerData *D) { - return D->getBegin(); - }); -} - -void IteratorChecker::analyzerContainerEnd(const CallExpr *CE, - CheckerContext &C) const { - analyzerContainerDataField(CE, C, [](const ContainerData *D) { - return D->getEnd(); - }); -} - -template <typename Getter> -void IteratorChecker::analyzerIteratorDataField(const CallExpr *CE, - CheckerContext &C, - Getter get, - SVal Default) const { - if (CE->getNumArgs() == 0) { - reportDebugMsg("Missing iterator argument", C); - return; - } - - auto State = C.getState(); - SVal V = C.getSVal(CE->getArg(0)); - const auto *Pos = getIteratorPosition(State, V); - if (Pos) { - State = State->BindExpr(CE, C.getLocationContext(), get(Pos)); - } else { - State = State->BindExpr(CE, C.getLocationContext(), Default); - } - C.addTransition(State); -} - -void IteratorChecker::analyzerIteratorPosition(const CallExpr *CE, - CheckerContext &C) const { - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) { - return nonloc::SymbolVal(P->getOffset()); - }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); -} - -void IteratorChecker::analyzerIteratorContainer(const CallExpr *CE, - CheckerContext &C) const { - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - analyzerIteratorDataField(CE, C, [](const IteratorPosition *P) { - return loc::MemRegionVal(P->getContainer()); - }, loc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); -} - -void IteratorChecker::analyzerIteratorValidity(const CallExpr *CE, - CheckerContext &C) const { - auto &BVF = C.getSValBuilder().getBasicValueFactory(); - analyzerIteratorDataField(CE, C, [&BVF](const IteratorPosition *P) { - return - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get((P->isValid())))); - }, nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0)))); -} - -ExplodedNode *IteratorChecker::reportDebugMsg(llvm::StringRef Msg, - CheckerContext &C) const { - ExplodedNode *N = C.generateNonFatalErrorNode(); - if (!N) - return nullptr; - - auto &BR = C.getBugReporter(); - BR.emitReport(std::make_unique<PathSensitiveBugReport>(*DebugMsgBugType, - Msg, N)); - return N; -} - -namespace { - -bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); -bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); -bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2); -bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, - BinaryOperator::Opcode Opc); -bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, - BinaryOperator::Opcode Opc); -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg); -SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, SymbolRef Expr, - SymbolRef OldSym, SymbolRef NewSym); - -bool isIteratorType(const QualType &Type) { - if (Type->isPointerType()) - return true; - - const auto *CRD = Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); - return isIterator(CRD); -} - -bool isIterator(const CXXRecordDecl *CRD) { - if (!CRD) - return false; - - const auto Name = CRD->getName(); - if (!(Name.endswith_lower("iterator") || Name.endswith_lower("iter") || - Name.endswith_lower("it"))) - return false; - - bool HasCopyCtor = false, HasCopyAssign = true, HasDtor = false, - HasPreIncrOp = false, HasPostIncrOp = false, HasDerefOp = false; - for (const auto *Method : CRD->methods()) { - if (const auto *Ctor = dyn_cast<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 isComparisonOperator(OverloadedOperatorKind OK) { - return OK == OO_EqualEqual || OK == OO_ExclaimEqual || OK == OO_Less || - OK == OO_LessEqual || OK == OO_Greater || OK == OO_GreaterEqual; -} - -bool isBeginCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - return IdInfo->getName().endswith_lower("begin"); -} - -bool isEndCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - return IdInfo->getName().endswith_lower("end"); -} - -bool isAssignCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 2) - return false; - return IdInfo->getName() == "assign"; -} - -bool isClearCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "clear"; -} - -bool isPushBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_back"; -} - -bool isEmplaceBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_back"; -} - -bool isPopBackCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_back"; -} - -bool isPushFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() != 1) - return false; - return IdInfo->getName() == "push_front"; -} - -bool isEmplaceFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1) - return false; - return IdInfo->getName() == "emplace_front"; -} - -bool isPopFrontCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() > 0) - return false; - return IdInfo->getName() == "pop_front"; -} - -bool isInsertCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 2 || Func->getNumParams() > 3) - return false; - if (!isIteratorType(Func->getParamDecl(0)->getType())) - return false; - return IdInfo->getName() == "insert"; -} - -bool isEmplaceCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 2) - return false; - if (!isIteratorType(Func->getParamDecl(0)->getType())) - return false; - return IdInfo->getName() == "emplace"; -} - -bool isEraseCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1 || Func->getNumParams() > 2) - return false; - if (!isIteratorType(Func->getParamDecl(0)->getType())) - return false; - if (Func->getNumParams() == 2 && - !isIteratorType(Func->getParamDecl(1)->getType())) - return false; - return IdInfo->getName() == "erase"; -} - -bool isEraseAfterCall(const FunctionDecl *Func) { - const auto *IdInfo = Func->getIdentifier(); - if (!IdInfo) - return false; - if (Func->getNumParams() < 1 || Func->getNumParams() > 2) - return false; - if (!isIteratorType(Func->getParamDecl(0)->getType())) - return false; - if (Func->getNumParams() == 2 && - !isIteratorType(Func->getParamDecl(1)->getType())) - return false; - return IdInfo->getName() == "erase_after"; -} - -bool isAssignmentOperator(OverloadedOperatorKind OK) { return OK == OO_Equal; } - -bool isSimpleComparisonOperator(OverloadedOperatorKind OK) { - return OK == OO_EqualEqual || OK == OO_ExclaimEqual; -} - -bool isAccessOperator(OverloadedOperatorKind OK) { - return isDereferenceOperator(OK) || isIncrementOperator(OK) || - isDecrementOperator(OK) || isRandomIncrOrDecrOperator(OK); -} - -bool isDereferenceOperator(OverloadedOperatorKind OK) { - return OK == OO_Star || OK == OO_Arrow || OK == OO_ArrowStar || - OK == OO_Subscript; -} - -bool isIncrementOperator(OverloadedOperatorKind OK) { - return OK == OO_PlusPlus; -} - -bool isDecrementOperator(OverloadedOperatorKind OK) { - return OK == OO_MinusMinus; -} - -bool isRandomIncrOrDecrOperator(OverloadedOperatorKind OK) { - return OK == OO_Plus || OK == OO_PlusEqual || OK == OO_Minus || - OK == OO_MinusEqual; -} - -bool hasSubscriptOperator(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->isOverloadedOperator()) - continue; - const auto OPK = Method->getOverloadedOperator(); - if (OPK == OO_Subscript) { - return true; - } - } - return false; -} - -bool frontModifiable(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->getDeclName().isIdentifier()) - continue; - if (Method->getName() == "push_front" || Method->getName() == "pop_front") { - return true; - } - } - return false; -} - -bool backModifiable(ProgramStateRef State, const MemRegion *Reg) { - const auto *CRD = getCXXRecordDecl(State, Reg); - if (!CRD) - return false; - - for (const auto *Method : CRD->methods()) { - if (!Method->getDeclName().isIdentifier()) - continue; - if (Method->getName() == "push_back" || Method->getName() == "pop_back") { - return true; - } - } - return false; -} - -const CXXRecordDecl *getCXXRecordDecl(ProgramStateRef State, - const MemRegion *Reg) { - auto TI = getDynamicTypeInfo(State, Reg); - if (!TI.isValid()) - return nullptr; - - auto Type = TI.getType(); - if (const auto *RefT = Type->getAs<ReferenceType>()) { - Type = RefT->getPointeeType(); - } - - return Type->getUnqualifiedDesugaredType()->getAsCXXRecordDecl(); -} - -SymbolRef getContainerBegin(ProgramStateRef State, const MemRegion *Cont) { - const auto *CDataPtr = getContainerData(State, Cont); - if (!CDataPtr) - return nullptr; - - return CDataPtr->getBegin(); -} - -SymbolRef getContainerEnd(ProgramStateRef State, const MemRegion *Cont) { - const auto *CDataPtr = getContainerData(State, Cont); - if (!CDataPtr) - return nullptr; - - return CDataPtr->getEnd(); -} - -ProgramStateRef createContainerBegin(ProgramStateRef State, - const MemRegion *Cont, const Expr *E, - QualType T, const LocationContext *LCtx, - unsigned BlockCount) { - // Only create if it does not exist - const auto *CDataPtr = getContainerData(State, Cont); - if (CDataPtr && CDataPtr->getBegin()) - return State; - - auto &SymMgr = State->getSymbolManager(); - const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, - "begin"); - State = assumeNoOverflow(State, Sym, 4); - - if (CDataPtr) { - const auto CData = CDataPtr->newBegin(Sym); - return setContainerData(State, Cont, CData); - } - - const auto CData = ContainerData::fromBegin(Sym); - return setContainerData(State, Cont, CData); -} - -ProgramStateRef createContainerEnd(ProgramStateRef State, const MemRegion *Cont, - const Expr *E, QualType T, - const LocationContext *LCtx, - unsigned BlockCount) { - // Only create if it does not exist - const auto *CDataPtr = getContainerData(State, Cont); - if (CDataPtr && CDataPtr->getEnd()) - return State; - - auto &SymMgr = State->getSymbolManager(); - const SymbolConjured *Sym = SymMgr.conjureSymbol(E, LCtx, T, BlockCount, - "end"); - State = assumeNoOverflow(State, Sym, 4); - - if (CDataPtr) { - const auto CData = CDataPtr->newEnd(Sym); - return setContainerData(State, Cont, CData); - } - - const auto CData = ContainerData::fromEnd(Sym); - return setContainerData(State, Cont, CData); -} - -const ContainerData *getContainerData(ProgramStateRef State, - const MemRegion *Cont) { - return State->get<ContainerMap>(Cont); -} - -ProgramStateRef setContainerData(ProgramStateRef State, const MemRegion *Cont, - const ContainerData &CData) { - return State->set<ContainerMap>(Cont, CData); -} - -const IteratorPosition *getIteratorPosition(ProgramStateRef State, - const SVal &Val) { - if (auto Reg = Val.getAsRegion()) { - Reg = Reg->getMostDerivedObjectRegion(); - 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; -} - -ProgramStateRef setIteratorPosition(ProgramStateRef State, const SVal &Val, - const IteratorPosition &Pos) { - if (auto Reg = Val.getAsRegion()) { - Reg = Reg->getMostDerivedObjectRegion(); - 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 removeIteratorPosition(ProgramStateRef State, const SVal &Val) { - if (auto Reg = Val.getAsRegion()) { - Reg = Reg->getMostDerivedObjectRegion(); - return State->remove<IteratorRegionMap>(Reg); - } else if (const auto Sym = Val.getAsSymbol()) { - return State->remove<IteratorSymbolMap>(Sym); - } else if (const auto LCVal = Val.getAs<nonloc::LazyCompoundVal>()) { - return State->remove<IteratorRegionMap>(LCVal->getRegion()); - } - return nullptr; -} - -ProgramStateRef relateSymbols(ProgramStateRef State, SymbolRef Sym1, - SymbolRef Sym2, bool Equal) { - auto &SVB = State->getStateManager().getSValBuilder(); - - // FIXME: This code should be reworked as follows: - // 1. Subtract the operands using evalBinOp(). - // 2. Assume that the result doesn't overflow. - // 3. Compare the result to 0. - // 4. Assume the result of the comparison. - const auto comparison = - SVB.evalBinOp(State, BO_EQ, nonloc::SymbolVal(Sym1), - nonloc::SymbolVal(Sym2), SVB.getConditionType()); - - assert(comparison.getAs<DefinedSVal>() && - "Symbol comparison must be a `DefinedSVal`"); - - auto NewState = State->assume(comparison.castAs<DefinedSVal>(), Equal); - if (!NewState) - return nullptr; - - if (const auto CompSym = comparison.getAsSymbol()) { - assert(isa<SymIntExpr>(CompSym) && - "Symbol comparison must be a `SymIntExpr`"); - assert(BinaryOperator::isComparisonOp( - cast<SymIntExpr>(CompSym)->getOpcode()) && - "Symbol comparison must be a comparison"); - return assumeNoOverflow(NewState, cast<SymIntExpr>(CompSym)->getLHS(), 2); - } - - return NewState; -} - -bool hasLiveIterators(ProgramStateRef State, const MemRegion *Cont) { - auto RegionMap = State->get<IteratorRegionMap>(); - for (const auto Reg : RegionMap) { - if (Reg.second.getContainer() == Cont) - return true; - } - - auto SymbolMap = State->get<IteratorSymbolMap>(); - for (const auto Sym : SymbolMap) { - if (Sym.second.getContainer() == Cont) - return true; - } - - return false; -} - -bool isBoundThroughLazyCompoundVal(const Environment &Env, - const MemRegion *Reg) { - for (const auto Binding: Env) { - if (const auto LCVal = Binding.second.getAs<nonloc::LazyCompoundVal>()) { - if (LCVal->getRegion() == Reg) - return true; - } - } - - return false; -} - -// This function tells the analyzer's engine that symbols produced by our -// checker, most notably iterator positions, are relatively small. -// A distance between items in the container should not be very large. -// By assuming that it is within around 1/8 of the address space, -// we can help the analyzer perform operations on these symbols -// without being afraid of integer overflows. -// FIXME: Should we provide it as an API, so that all checkers could use it? -ProgramStateRef assumeNoOverflow(ProgramStateRef State, SymbolRef Sym, - long Scale) { - SValBuilder &SVB = State->getStateManager().getSValBuilder(); - BasicValueFactory &BV = SVB.getBasicValueFactory(); - - QualType T = Sym->getType(); - assert(T->isSignedIntegerOrEnumerationType()); - APSIntType AT = BV.getAPSIntType(T); - - ProgramStateRef NewState = State; - - llvm::APSInt Max = AT.getMaxValue() / AT.getValue(Scale); - SVal IsCappedFromAbove = - SVB.evalBinOpNN(State, BO_LE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Max), SVB.getConditionType()); - if (auto DV = IsCappedFromAbove.getAs<DefinedSVal>()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - llvm::APSInt Min = -Max; - SVal IsCappedFromBelow = - SVB.evalBinOpNN(State, BO_GE, nonloc::SymbolVal(Sym), - nonloc::ConcreteInt(Min), SVB.getConditionType()); - if (auto DV = IsCappedFromBelow.getAs<DefinedSVal>()) { - NewState = NewState->assume(*DV, true); - if (!NewState) - return State; - } - - return NewState; -} - -template <typename Condition, typename Process> -ProgramStateRef processIteratorPositions(ProgramStateRef State, Condition Cond, - Process Proc) { - auto &RegionMapFactory = State->get_context<IteratorRegionMap>(); - auto RegionMap = State->get<IteratorRegionMap>(); - bool Changed = false; - for (const auto Reg : RegionMap) { - if (Cond(Reg.second)) { - RegionMap = RegionMapFactory.add(RegionMap, Reg.first, Proc(Reg.second)); - Changed = true; - } - } - - if (Changed) - State = State->set<IteratorRegionMap>(RegionMap); - - auto &SymbolMapFactory = State->get_context<IteratorSymbolMap>(); - auto SymbolMap = State->get<IteratorSymbolMap>(); - Changed = false; - for (const auto Sym : SymbolMap) { - if (Cond(Sym.second)) { - SymbolMap = SymbolMapFactory.add(SymbolMap, Sym.first, Proc(Sym.second)); - Changed = true; - } - } - - if (Changed) - State = State->set<IteratorSymbolMap>(SymbolMap); - - return State; -} - -ProgramStateRef invalidateAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont) { - auto MatchCont = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont; - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, MatchCont, Invalidate); -} - -ProgramStateRef -invalidateAllIteratorPositionsExcept(ProgramStateRef State, - const MemRegion *Cont, SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto MatchContAndCompare = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont && - !compare(State, Pos.getOffset(), Offset, Opc); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, MatchContAndCompare, Invalidate); -} - -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto Compare = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), Offset, Opc); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, Compare, Invalidate); -} - -ProgramStateRef invalidateIteratorPositions(ProgramStateRef State, - SymbolRef Offset1, - BinaryOperator::Opcode Opc1, - SymbolRef Offset2, - BinaryOperator::Opcode Opc2) { - auto Compare = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), Offset1, Opc1) && - compare(State, Pos.getOffset(), Offset2, Opc2); - }; - auto Invalidate = [&](const IteratorPosition &Pos) { - return Pos.invalidate(); - }; - return processIteratorPositions(State, Compare, Invalidate); -} - -ProgramStateRef reassignAllIteratorPositions(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont) { - auto MatchCont = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont; - }; - auto ReAssign = [&](const IteratorPosition &Pos) { - return Pos.reAssign(NewCont); - }; - return processIteratorPositions(State, MatchCont, ReAssign); -} - -ProgramStateRef reassignAllIteratorPositionsUnless(ProgramStateRef State, - const MemRegion *Cont, - const MemRegion *NewCont, - SymbolRef Offset, - BinaryOperator::Opcode Opc) { - auto MatchContAndCompare = [&](const IteratorPosition &Pos) { - return Pos.getContainer() == Cont && - !compare(State, Pos.getOffset(), Offset, Opc); - }; - auto ReAssign = [&](const IteratorPosition &Pos) { - return Pos.reAssign(NewCont); - }; - return processIteratorPositions(State, MatchContAndCompare, ReAssign); -} - -// This function rebases symbolic expression `OldSym + Int` to `NewSym + Int`, -// `OldSym - Int` to `NewSym - Int` and `OldSym` to `NewSym` in any iterator -// position offsets where `CondSym` is true. -ProgramStateRef rebaseSymbolInIteratorPositionsIf( - ProgramStateRef State, SValBuilder &SVB, SymbolRef OldSym, - SymbolRef NewSym, SymbolRef CondSym, BinaryOperator::Opcode Opc) { - auto LessThanEnd = [&](const IteratorPosition &Pos) { - return compare(State, Pos.getOffset(), CondSym, Opc); - }; - auto RebaseSymbol = [&](const IteratorPosition &Pos) { - return Pos.setTo(rebaseSymbol(State, SVB, Pos.getOffset(), OldSym, - NewSym)); - }; - return processIteratorPositions(State, LessThanEnd, RebaseSymbol); -} - -// This function rebases symbolic expression `OldExpr + Int` to `NewExpr + Int`, -// `OldExpr - Int` to `NewExpr - Int` and `OldExpr` to `NewExpr` in expression -// `OrigExpr`. -SymbolRef rebaseSymbol(ProgramStateRef State, SValBuilder &SVB, - SymbolRef OrigExpr, SymbolRef OldExpr, - SymbolRef NewSym) { - auto &SymMgr = SVB.getSymbolManager(); - auto Diff = SVB.evalBinOpNN(State, BO_Sub, nonloc::SymbolVal(OrigExpr), - nonloc::SymbolVal(OldExpr), - SymMgr.getType(OrigExpr)); - - const auto DiffInt = Diff.getAs<nonloc::ConcreteInt>(); - if (!DiffInt) - return OrigExpr; - - return SVB.evalBinOpNN(State, BO_Add, *DiffInt, nonloc::SymbolVal(NewSym), - SymMgr.getType(OrigExpr)).getAsSymbol(); -} - -bool isZero(ProgramStateRef State, const NonLoc &Val) { - auto &BVF = State->getBasicVals(); - return compare(State, Val, - nonloc::ConcreteInt(BVF.getValue(llvm::APSInt::get(0))), - BO_EQ); -} - -bool isPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { - const auto *Cont = Pos.getContainer(); - const auto *CData = getContainerData(State, Cont); - if (!CData) - return false; - - const auto End = CData->getEnd(); - if (End) { - if (isEqual(State, Pos.getOffset(), End)) { - return true; - } - } - - return false; -} - -bool isAheadOfRange(ProgramStateRef State, const IteratorPosition &Pos) { - const auto *Cont = Pos.getContainer(); - const auto *CData = getContainerData(State, Cont); - if (!CData) - return false; - - const auto Beg = CData->getBegin(); - if (Beg) { - if (isLess(State, Pos.getOffset(), Beg)) { - return true; - } - } - - return false; -} - -bool isBehindPastTheEnd(ProgramStateRef State, const IteratorPosition &Pos) { - const auto *Cont = Pos.getContainer(); - const auto *CData = getContainerData(State, Cont); - if (!CData) - return false; - - const auto End = CData->getEnd(); - if (End) { - if (isGreater(State, Pos.getOffset(), End)) { - return true; - } - } - - return false; -} - -bool isLess(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { - return compare(State, Sym1, Sym2, BO_LT); -} - -bool isGreater(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { - return compare(State, Sym1, Sym2, BO_GT); -} - -bool isEqual(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2) { - return compare(State, Sym1, Sym2, BO_EQ); -} - -bool compare(ProgramStateRef State, SymbolRef Sym1, SymbolRef Sym2, - BinaryOperator::Opcode Opc) { - return compare(State, nonloc::SymbolVal(Sym1), nonloc::SymbolVal(Sym2), Opc); -} - -bool compare(ProgramStateRef State, NonLoc NL1, NonLoc NL2, - BinaryOperator::Opcode Opc) { - auto &SVB = State->getStateManager().getSValBuilder(); - - const auto comparison = - SVB.evalBinOp(State, Opc, NL1, NL2, SVB.getConditionType()); - - assert(comparison.getAs<DefinedSVal>() && - "Symbol comparison must be a `DefinedSVal`"); - - return !State->assume(comparison.castAs<DefinedSVal>(), false); -} - -} // namespace - -void ento::registerIteratorModeling(CheckerManager &mgr) { - mgr.registerChecker<IteratorChecker>(); -} - -bool ento::shouldRegisterIteratorModeling(const LangOptions &LO) { - return true; -} - -#define REGISTER_CHECKER(name) \ - void ento::register##name(CheckerManager &Mgr) { \ - auto *checker = Mgr.getChecker<IteratorChecker>(); \ - checker->ChecksEnabled[IteratorChecker::CK_##name] = true; \ - checker->CheckNames[IteratorChecker::CK_##name] = \ - Mgr.getCurrentCheckerName(); \ - } \ - \ - bool ento::shouldRegister##name(const LangOptions &LO) { return true; } - -REGISTER_CHECKER(IteratorRangeChecker) -REGISTER_CHECKER(MismatchedIteratorChecker) -REGISTER_CHECKER(InvalidatedIteratorChecker) -REGISTER_CHECKER(DebugIteratorModeling) |
