diff options
Diffstat (limited to 'lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp')
| -rw-r--r-- | lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp | 603 |
1 files changed, 0 insertions, 603 deletions
diff --git a/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp b/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp deleted file mode 100644 index b0bac33db162..000000000000 --- a/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp +++ /dev/null @@ -1,603 +0,0 @@ -//=== IteratorsChecker.cpp - Check for Invalidated Iterators ------*- C++ -*---- -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This defines IteratorsChecker, a number of small checks for conditions -// leading to invalid iterators being used. -// FIXME: Currently only supports 'vector' and 'deque' -// -//===----------------------------------------------------------------------===// - -#include "clang/AST/DeclTemplate.h" -#include "clang/Basic/SourceManager.h" -#include "ClangSACheckers.h" -#include "clang/StaticAnalyzer/Core/Checker.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" -#include "clang/StaticAnalyzer/Core/CheckerManager.h" -#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" -#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h" -#include "clang/AST/DeclCXX.h" -#include "clang/AST/ExprCXX.h" -#include "clang/AST/Type.h" -#include "clang/AST/PrettyPrinter.h" -#include "llvm/ADT/SmallPtrSet.h" -#include "llvm/ADT/StringSwitch.h" - - -using namespace clang; -using namespace ento; - -// This is the state associated with each iterator which includes both the -// kind of state and the instance used to initialize it. -// FIXME: add location where invalidated for better error reporting. -namespace { -class RefState { - enum Kind { BeginValid, EndValid, Invalid, Undefined, Unknown } K; - const void *VR; - -public: - RefState(Kind k, const void *vr) : K(k), VR(vr) {} - - bool isValid() const { return K == BeginValid || K == EndValid; } - bool isInvalid() const { return K == Invalid; } - bool isUndefined() const { return K == Undefined; } - bool isUnknown() const { return K == Unknown; } - const MemRegion *getMemRegion() const { - if (K == BeginValid || K == EndValid) - return(const MemRegion *)VR; - return 0; - } - const MemberExpr *getMemberExpr() const { - if (K == Invalid) - return(const MemberExpr *)VR; - return 0; - } - - bool operator==(const RefState &X) const { - return K == X.K && VR == X.VR; - } - - static RefState getBeginValid(const MemRegion *vr) { - assert(vr); - return RefState(BeginValid, vr); - } - static RefState getEndValid(const MemRegion *vr) { - assert(vr); - return RefState(EndValid, vr); - } - static RefState getInvalid( const MemberExpr *ME ) { - return RefState(Invalid, ME); - } - static RefState getUndefined( void ) { - return RefState(Undefined, 0); - } - static RefState getUnknown( void ) { - return RefState(Unknown, 0); - } - - void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddInteger(K); - ID.AddPointer(VR); - } -}; - -enum RefKind { NoKind, VectorKind, VectorIteratorKind }; - -class IteratorsChecker : - public Checker<check::PreStmt<CXXOperatorCallExpr>, - check::PreStmt<DeclStmt>, - check::PreStmt<CXXMemberCallExpr>, - check::PreStmt<CallExpr> > - { - // Used when parsing iterators and vectors and deques. - BuiltinBug *BT_Invalid, *BT_Undefined, *BT_Incompatible; - -public: - IteratorsChecker() : - BT_Invalid(0), BT_Undefined(0), BT_Incompatible(0) - {} - static void *getTag() { static int tag; return &tag; } - - // Checker entry points. - void checkPreStmt(const CXXOperatorCallExpr *OCE, - CheckerContext &C) const; - - void checkPreStmt(const DeclStmt *DS, - CheckerContext &C) const; - - void checkPreStmt(const CXXMemberCallExpr *MCE, - CheckerContext &C) const; - - void checkPreStmt(const CallExpr *CE, - CheckerContext &C) const; - -private: - ProgramStateRef handleAssign(ProgramStateRef state, - const Expr *lexp, - const Expr *rexp, - const LocationContext *LC) const; - - ProgramStateRef handleAssign(ProgramStateRef state, - const MemRegion *MR, - const Expr *rexp, - const LocationContext *LC) const; - - ProgramStateRef invalidateIterators(ProgramStateRef state, - const MemRegion *MR, - const MemberExpr *ME) const; - - void checkExpr(CheckerContext &C, const Expr *E) const; - - void checkArgs(CheckerContext &C, const CallExpr *CE) const; - - const MemRegion *getRegion(ProgramStateRef state, - const Expr *E, - const LocationContext *LC) const; - - const DeclRefExpr *getDeclRefExpr(const Expr *E) const; -}; - -class IteratorState { -public: - typedef llvm::ImmutableMap<const MemRegion *, RefState> EntryMap; -}; -} //end anonymous namespace - -namespace clang { - namespace ento { - template <> - struct ProgramStateTrait<IteratorState> - : public ProgramStatePartialTrait<IteratorState::EntryMap> { - static void *GDMIndex() { return IteratorsChecker::getTag(); } - }; - } -} - -void ento::registerIteratorsChecker(CheckerManager &mgr) { - mgr.registerChecker<IteratorsChecker>(); -} - -// =============================================== -// Utility functions used by visitor functions -// =============================================== - -// check a templated type for std::vector or std::deque -static RefKind getTemplateKind(const NamedDecl *td) { - const DeclContext *dc = td->getDeclContext(); - const NamespaceDecl *nameSpace = dyn_cast<NamespaceDecl>(dc); - if (!nameSpace || !isa<TranslationUnitDecl>(nameSpace->getDeclContext()) - || nameSpace->getName() != "std") - return NoKind; - - StringRef name = td->getName(); - return llvm::StringSwitch<RefKind>(name) - .Cases("vector", "deque", VectorKind) - .Default(NoKind); -} - -static RefKind getTemplateKind(const DeclContext *dc) { - if (const ClassTemplateSpecializationDecl *td = - dyn_cast<ClassTemplateSpecializationDecl>(dc)) - return getTemplateKind(cast<NamedDecl>(td)); - return NoKind; -} - -static RefKind getTemplateKind(const TypedefType *tdt) { - const TypedefNameDecl *td = tdt->getDecl(); - RefKind parentKind = getTemplateKind(td->getDeclContext()); - if (parentKind == VectorKind) { - return llvm::StringSwitch<RefKind>(td->getName()) - .Cases("iterator", - "const_iterator", - "reverse_iterator", VectorIteratorKind) - .Default(NoKind); - } - return NoKind; -} - -static RefKind getTemplateKind(const TemplateSpecializationType *tsp) { - const TemplateName &tname = tsp->getTemplateName(); - TemplateDecl *td = tname.getAsTemplateDecl(); - if (!td) - return NoKind; - return getTemplateKind(td); -} - -static RefKind getTemplateKind(QualType T) { - if (const TemplateSpecializationType *tsp = - T->getAs<TemplateSpecializationType>()) { - return getTemplateKind(tsp); - } - if (const ElaboratedType *ET = dyn_cast<ElaboratedType>(T)) { - QualType namedType = ET->getNamedType(); - if (const TypedefType *tdt = namedType->getAs<TypedefType>()) - return getTemplateKind(tdt); - if (const TemplateSpecializationType *tsp = - namedType->getAs<TemplateSpecializationType>()) { - return getTemplateKind(tsp); - } - } - return NoKind; -} - -// Iterate through our map and invalidate any iterators that were -// initialized fromt the specified instance MemRegion. -ProgramStateRef IteratorsChecker::invalidateIterators(ProgramStateRef state, - const MemRegion *MR, const MemberExpr *ME) const { - IteratorState::EntryMap Map = state->get<IteratorState>(); - if (Map.isEmpty()) - return state; - - // Loop over the entries in the current state. - // The key doesn't change, so the map iterators won't change. - for (IteratorState::EntryMap::iterator I = Map.begin(), E = Map.end(); - I != E; ++I) { - RefState RS = I.getData(); - if (RS.getMemRegion() == MR) - state = state->set<IteratorState>(I.getKey(), RefState::getInvalid(ME)); - } - - return state; -} - -// Handle assigning to an iterator where we don't have the LValue MemRegion. -ProgramStateRef IteratorsChecker::handleAssign(ProgramStateRef state, - const Expr *lexp, const Expr *rexp, const LocationContext *LC) const { - // Skip the cast if present. - if (const MaterializeTemporaryExpr *M - = dyn_cast<MaterializeTemporaryExpr>(lexp)) - lexp = M->GetTemporaryExpr(); - if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(lexp)) - lexp = ICE->getSubExpr(); - SVal sv = state->getSVal(lexp, LC); - const MemRegion *MR = sv.getAsRegion(); - if (!MR) - return state; - RefKind kind = getTemplateKind(lexp->getType()); - - // If assigning to a vector, invalidate any iterators currently associated. - if (kind == VectorKind) - return invalidateIterators(state, MR, 0); - - // Make sure that we are assigning to an iterator. - if (getTemplateKind(lexp->getType()) != VectorIteratorKind) - return state; - return handleAssign(state, MR, rexp, LC); -} - -// handle assigning to an iterator -ProgramStateRef IteratorsChecker::handleAssign(ProgramStateRef state, - const MemRegion *MR, const Expr *rexp, const LocationContext *LC) const { - // Assume unknown until we find something definite. - state = state->set<IteratorState>(MR, RefState::getUnknown()); - if (const MaterializeTemporaryExpr *M - = dyn_cast<MaterializeTemporaryExpr>(rexp)) - rexp = M->GetTemporaryExpr(); - if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(rexp)) - rexp = ICE->getSubExpr(); - // Need to handle three cases: MemberCall, copy, copy with addition. - if (const CallExpr *CE = dyn_cast<CallExpr>(rexp)) { - // Handle MemberCall. - if (const MemberExpr *ME = dyn_cast<MemberExpr>(CE->getCallee())) { - const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ME->getBase()); - if (!DRE) - return state; - // Verify that the type is std::vector<T>. - if (getTemplateKind(DRE->getType()) != VectorKind) - return state; - // Now get the MemRegion associated with the instance. - const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); - if (!VD) - return state; - const MemRegion *IMR = state->getRegion(VD, LC); - if (!IMR) - return state; - // Finally, see if it is one of the calls that will create - // a valid iterator and mark it if so, else mark as Unknown. - StringRef mName = ME->getMemberDecl()->getName(); - - if (llvm::StringSwitch<bool>(mName) - .Cases("begin", "insert", "erase", true).Default(false)) { - return state->set<IteratorState>(MR, RefState::getBeginValid(IMR)); - } - if (mName == "end") - return state->set<IteratorState>(MR, RefState::getEndValid(IMR)); - - return state->set<IteratorState>(MR, RefState::getUnknown()); - } - } - // Handle straight copy from another iterator. - if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(rexp)) { - if (getTemplateKind(DRE->getType()) != VectorIteratorKind) - return state; - // Now get the MemRegion associated with the instance. - const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); - if (!VD) - return state; - const MemRegion *IMR = state->getRegion(VD, LC); - if (!IMR) - return state; - // Get the RefState of the iterator being copied. - const RefState *RS = state->get<IteratorState>(IMR); - if (!RS) - return state; - // Use it to set the state of the LValue. - return state->set<IteratorState>(MR, *RS); - } - // If we have operator+ or operator- ... - if (const CXXOperatorCallExpr *OCE = dyn_cast<CXXOperatorCallExpr>(rexp)) { - OverloadedOperatorKind Kind = OCE->getOperator(); - if (Kind == OO_Plus || Kind == OO_Minus) { - // Check left side of tree for a valid value. - state = handleAssign( state, MR, OCE->getArg(0), LC); - const RefState *RS = state->get<IteratorState>(MR); - // If found, return it. - if (!RS->isUnknown()) - return state; - // Otherwise return what we find in the right side. - return handleAssign(state, MR, OCE->getArg(1), LC); - } - } - // Fall through if nothing matched. - return state; -} - -// Iterate through the arguments looking for an Invalid or Undefined iterator. -void IteratorsChecker::checkArgs(CheckerContext &C, const CallExpr *CE) const { - for (CallExpr::const_arg_iterator I = CE->arg_begin(), E = CE->arg_end(); - I != E; ++I) { - checkExpr(C, *I); - } -} - -// Get the DeclRefExpr associated with the expression. -const DeclRefExpr *IteratorsChecker::getDeclRefExpr(const Expr *E) const { - // If it is a CXXConstructExpr, need to get the subexpression. - if (const CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(E)) { - if (CE->getNumArgs()== 1) { - CXXConstructorDecl *CD = CE->getConstructor(); - if (CD->isTrivial()) - E = CE->getArg(0); - } - } - if (const MaterializeTemporaryExpr *M = dyn_cast<MaterializeTemporaryExpr>(E)) - E = M->GetTemporaryExpr(); - if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) - E = ICE->getSubExpr(); - // If it isn't one of our types, don't do anything. - if (getTemplateKind(E->getType()) != VectorIteratorKind) - return NULL; - return dyn_cast<DeclRefExpr>(E); -} - -// Get the MemRegion associated with the expresssion. -const MemRegion *IteratorsChecker::getRegion(ProgramStateRef state, - const Expr *E, const LocationContext *LC) const { - const DeclRefExpr *DRE = getDeclRefExpr(E); - if (!DRE) - return NULL; - const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl()); - if (!VD) - return NULL; - // return the MemRegion associated with the iterator - return state->getRegion(VD, LC); -} - -// Check the expression and if it is an iterator, generate a diagnostic -// if the iterator is not valid. -// FIXME: this method can generate new nodes, and subsequent logic should -// use those nodes. We also cannot create multiple nodes at one ProgramPoint -// with the same tag. -void IteratorsChecker::checkExpr(CheckerContext &C, const Expr *E) const { - ProgramStateRef state = C.getState(); - const MemRegion *MR = getRegion(state, E, C.getLocationContext()); - if (!MR) - return; - - // Get the state associated with the iterator. - const RefState *RS = state->get<IteratorState>(MR); - if (!RS) - return; - if (RS->isInvalid()) { - if (ExplodedNode *N = C.addTransition()) { - if (!BT_Invalid) - // FIXME: We are eluding constness here. - const_cast<IteratorsChecker*>(this)->BT_Invalid = new BuiltinBug(""); - - std::string msg; - const MemberExpr *ME = RS->getMemberExpr(); - if (ME) { - std::string name = ME->getMemberNameInfo().getAsString(); - msg = "Attempt to use an iterator made invalid by call to '" + - name + "'"; - } - else { - msg = "Attempt to use an iterator made invalid by copying another " - "container to its container"; - } - - BugReport *R = new BugReport(*BT_Invalid, msg, N); - R->addRange(getDeclRefExpr(E)->getSourceRange()); - C.EmitReport(R); - } - } - else if (RS->isUndefined()) { - if (ExplodedNode *N = C.addTransition()) { - if (!BT_Undefined) - // FIXME: We are eluding constness here. - const_cast<IteratorsChecker*>(this)->BT_Undefined = - new BuiltinBug("Use of iterator that is not defined"); - - BugReport *R = new BugReport(*BT_Undefined, - BT_Undefined->getDescription(), N); - R->addRange(getDeclRefExpr(E)->getSourceRange()); - C.EmitReport(R); - } - } -} - -// =============================================== -// Path analysis visitor functions -// =============================================== - -// For a generic Call, just check the args for bad iterators. -void IteratorsChecker::checkPreStmt(const CallExpr *CE, - CheckerContext &C) const{ - - // FIXME: These checks are to currently work around a bug - // in CheckerManager. - if (isa<CXXOperatorCallExpr>(CE)) - return; - if (isa<CXXMemberCallExpr>(CE)) - return; - - checkArgs(C, CE); -} - -// Handle operator calls. First, if it is operator=, check the argument, -// and handle assigning and set target state appropriately. Otherwise, for -// other operators, check the args for bad iterators and handle comparisons. -void IteratorsChecker::checkPreStmt(const CXXOperatorCallExpr *OCE, - CheckerContext &C) const -{ - const LocationContext *LC = C.getLocationContext(); - ProgramStateRef state = C.getState(); - OverloadedOperatorKind Kind = OCE->getOperator(); - if (Kind == OO_Equal) { - checkExpr(C, OCE->getArg(1)); - state = handleAssign(state, OCE->getArg(0), OCE->getArg(1), LC); - C.addTransition(state); - return; - } - else { - checkArgs(C, OCE); - // If it is a compare and both are iterators, ensure that they are for - // the same container. - if (Kind == OO_EqualEqual || Kind == OO_ExclaimEqual || - Kind == OO_Less || Kind == OO_LessEqual || - Kind == OO_Greater || Kind == OO_GreaterEqual) { - const MemRegion *MR0, *MR1; - MR0 = getRegion(state, OCE->getArg(0), LC); - if (!MR0) - return; - MR1 = getRegion(state, OCE->getArg(1), LC); - if (!MR1) - return; - const RefState *RS0, *RS1; - RS0 = state->get<IteratorState>(MR0); - if (!RS0) - return; - RS1 = state->get<IteratorState>(MR1); - if (!RS1) - return; - if (RS0->getMemRegion() != RS1->getMemRegion()) { - if (ExplodedNode *N = C.addTransition()) { - if (!BT_Incompatible) - const_cast<IteratorsChecker*>(this)->BT_Incompatible = - new BuiltinBug( - "Cannot compare iterators from different containers"); - - BugReport *R = new BugReport(*BT_Incompatible, - BT_Incompatible->getDescription(), N); - R->addRange(OCE->getSourceRange()); - C.EmitReport(R); - } - } - } - } -} - -// Need to handle DeclStmts to pick up initializing of iterators and to mark -// uninitialized ones as Undefined. -void IteratorsChecker::checkPreStmt(const DeclStmt *DS, - CheckerContext &C) const { - const Decl *D = *DS->decl_begin(); - const VarDecl *VD = dyn_cast<VarDecl>(D); - // Only care about iterators. - if (getTemplateKind(VD->getType()) != VectorIteratorKind) - return; - - // Get the MemRegion associated with the iterator and mark it as Undefined. - ProgramStateRef state = C.getState(); - Loc VarLoc = state->getLValue(VD, C.getLocationContext()); - const MemRegion *MR = VarLoc.getAsRegion(); - if (!MR) - return; - state = state->set<IteratorState>(MR, RefState::getUndefined()); - - // if there is an initializer, handle marking Valid if a proper initializer - const Expr *InitEx = VD->getInit(); - if (InitEx) { - // FIXME: This is too syntactic. Since 'InitEx' will be analyzed first - // it should resolve to an SVal that we can check for validity - // *semantically* instead of walking through the AST. - if (const CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(InitEx)) { - if (CE->getNumArgs() == 1) { - const Expr *E = CE->getArg(0); - if (const MaterializeTemporaryExpr *M - = dyn_cast<MaterializeTemporaryExpr>(E)) - E = M->GetTemporaryExpr(); - if (const ImplicitCastExpr *ICE = dyn_cast<ImplicitCastExpr>(E)) - InitEx = ICE->getSubExpr(); - state = handleAssign(state, MR, InitEx, C.getLocationContext()); - } - } - } - C.addTransition(state); -} - - -namespace { struct CalledReserved {}; } -namespace clang { namespace ento { -template<> struct ProgramStateTrait<CalledReserved> - : public ProgramStatePartialTrait<llvm::ImmutableSet<const MemRegion*> > { - static void *GDMIndex() { static int index = 0; return &index; } -}; -}} - -// on a member call, first check the args for any bad iterators -// then, check to see if it is a call to a function that will invalidate -// the iterators -void IteratorsChecker::checkPreStmt(const CXXMemberCallExpr *MCE, - CheckerContext &C) const { - // Check the arguments. - checkArgs(C, MCE); - const MemberExpr *ME = dyn_cast<MemberExpr>(MCE->getCallee()); - if (!ME) - return; - // Make sure we have the right kind of container. - const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(ME->getBase()); - if (!DRE || getTemplateKind(DRE->getType()) != VectorKind) - return; - SVal tsv = C.getState()->getSVal(DRE, C.getLocationContext()); - // Get the MemRegion associated with the container instance. - const MemRegion *MR = tsv.getAsRegion(); - if (!MR) - return; - // If we are calling a function that invalidates iterators, mark them - // appropriately by finding matching instances. - ProgramStateRef state = C.getState(); - StringRef mName = ME->getMemberDecl()->getName(); - if (llvm::StringSwitch<bool>(mName) - .Cases("insert", "reserve", "push_back", true) - .Cases("erase", "pop_back", "clear", "resize", true) - .Default(false)) { - // If there was a 'reserve' call, assume iterators are good. - if (!state->contains<CalledReserved>(MR)) - state = invalidateIterators(state, MR, ME); - } - // Keep track of instances that have called 'reserve' - // note: do this after we invalidate any iterators by calling - // 'reserve' itself. - if (mName == "reserve") - state = state->add<CalledReserved>(MR); - - if (state != C.getState()) - C.addTransition(state); -} - |