diff options
Diffstat (limited to 'clang/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp')
| -rw-r--r-- | clang/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp | 603 |
1 files changed, 603 insertions, 0 deletions
diff --git a/clang/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp new file mode 100644 index 0000000..b0bac33 --- /dev/null +++ b/clang/lib/StaticAnalyzer/Checkers/IteratorsChecker.cpp @@ -0,0 +1,603 @@ +//=== 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); +} + |