Add the clang library to the repo (with some of my changes, too).

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);
+}
+