Vendor import of clang trunk r161861:

http://llvm.org/svn/llvm-project/cfe/trunk@161861

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 b0bac33..0000000
--- 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);
-}
-