Update CStringChecker to take advantage of the new metadata symbols and region change callback. Now does basic tracking of string length for general regions. Currently this is still only used for modeling strlen().

llvm-svn: 111081

1 files changed, 245 insertions, 87 deletions

diff --git a/clang/lib/Checker/CStringChecker.cpp b/clang/lib/Checker/CStringChecker.cpp
index d2e921bc5cf..bf3316fbdab 100644
--- a/clang/lib/Checker/CStringChecker.cpp
+++ b/clang/lib/Checker/CStringChecker.cpp
@@ -15,6 +15,7 @@
 #include "GRExprEngineExperimentalChecks.h"
 #include "clang/Checker/BugReporter/BugType.h"
 #include "clang/Checker/PathSensitive/CheckerVisitor.h"
+#include "clang/Checker/PathSensitive/GRStateTrait.h"
 #include "llvm/ADT/StringSwitch.h"
 
 using namespace clang;
@@ -28,6 +29,15 @@ public:
   static void *getTag() { static int tag; return &tag; }
 
   bool EvalCallExpr(CheckerContext &C, const CallExpr *CE);
+  void PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS);
+  void MarkLiveSymbols(const GRState *state, SymbolReaper &SR);
+  void EvalDeadSymbols(CheckerContext &C, SymbolReaper &SR);
+  bool WantsRegionChangeUpdate(const GRState *state);
+
+  const GRState *EvalRegionChanges(const GRState *state,
+                                   const MemRegion * const *Begin,
+                                   const MemRegion * const *End,
+                                   bool*);
 
   typedef void (CStringChecker::*FnCheck)(CheckerContext &, const CallExpr *);
 
@@ -46,7 +56,9 @@ public:
   std::pair<const GRState*, const GRState*>
   AssumeZero(CheckerContext &C, const GRState *state, SVal V, QualType Ty);
 
-  SVal GetCStringLength(CheckerContext &C, const GRState *state,
+  SVal GetCStringLengthForRegion(CheckerContext &C, const GRState *&state,
+                                 const Expr *Ex, const MemRegion *MR);
+  SVal GetCStringLength(CheckerContext &C, const GRState *&state,
                         const Expr *Ex, SVal Buf);
 
   bool SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
@@ -67,8 +79,21 @@ public:
   void EmitOverlapBug(CheckerContext &C, const GRState *state,
                       const Stmt *First, const Stmt *Second);
 };
+
+class CStringLength {
+public:
+  typedef llvm::ImmutableMap<const MemRegion *, SVal> EntryMap;
+};
 } //end anonymous namespace
 
+namespace clang {
+  template <>
+  struct GRStateTrait<CStringLength> 
+    : public GRStatePartialTrait<CStringLength::EntryMap> {
+    static void *GDMIndex() { return CStringChecker::getTag(); }
+  };
+}
+
 void clang::RegisterCStringChecker(GRExprEngine &Eng) {
   Eng.registerCheck(new CStringChecker());
 }
@@ -382,7 +407,26 @@ void CStringChecker::EmitOverlapBug(CheckerContext &C, const GRState *state,
   C.EmitReport(report);
 }
 
-SVal CStringChecker::GetCStringLength(CheckerContext &C, const GRState *state,
+SVal CStringChecker::GetCStringLengthForRegion(CheckerContext &C,
+                                               const GRState *&state,
+                                               const Expr *Ex,
+                                               const MemRegion *MR) {
+  // If there's a recorded length, go ahead and return it.
+  const SVal *Recorded = state->get<CStringLength>(MR);
+  if (Recorded)
+    return *Recorded;
+  
+  // Otherwise, get a new symbol and update the state.
+  unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
+  ValueManager &ValMgr = C.getValueManager();
+  QualType SizeTy = ValMgr.getContext().getSizeType();
+  SVal Strlen = ValMgr.getMetadataSymbolVal(getTag(), MR, Ex, SizeTy, Count);
+  
+  state = state->set<CStringLength>(MR, Strlen);
+  return Strlen;
+}
+
+SVal CStringChecker::GetCStringLength(CheckerContext &C, const GRState *&state,
                                       const Expr *Ex, SVal Buf) {
   const MemRegion *MR = Buf.getAsRegion();
   if (!MR) {
@@ -390,8 +434,7 @@ SVal CStringChecker::GetCStringLength(CheckerContext &C, const GRState *state,
     // C string. In the context of locations, the only time we can issue such
     // a warning is for labels.
     if (loc::GotoLabel *Label = dyn_cast<loc::GotoLabel>(&Buf)) {
-      ExplodedNode *N = C.GenerateSink(state);
-      if (N) {
+      if (ExplodedNode *N = C.GenerateNode(state)) {
         if (!BT_NotCString)
           BT_NotCString = new BuiltinBug("API",
             "Argument is not a null-terminated string.");
@@ -413,86 +456,65 @@ SVal CStringChecker::GetCStringLength(CheckerContext &C, const GRState *state,
       return UndefinedVal();
     }
 
-    // If it's not a region and not a label, it may be a constant location,
-    // or it may be unknown. Just conjure a value as usual (see end of method).
-
-  } else {
-    // If we have a region, strip casts from it and see if we can figure out
-    // its length. For anything we can't figure out, just conjure a value as
-    // usual (see end of method).
-    MR = MR->StripCasts();
-
-    switch (MR->getKind()) {
-    case MemRegion::StringRegionKind: {
-      ValueManager &ValMgr = C.getValueManager();
-      ASTContext &Ctx = ValMgr.getContext();
-      const StringLiteral *Str = cast<StringRegion>(MR)->getStringLiteral();
-
-      // Non-constant string literals may have been changed, so only return a
-      // known value if we know the literal is constant.
-      if (Str->getType().isConstant(Ctx)) {
-        QualType SizeTy = Ctx.getSizeType();
-        return ValMgr.makeIntVal(Str->getByteLength(), SizeTy);        
-      }
+    // If it's not a region and not a label, give up.
+    return UnknownVal();
+  }
 
-      // FIXME: Handle the non-constant case. For now, just treat it like any
-      // other initialized region.
-      // FALL-THROUGH
+  // If we have a region, strip casts from it and see if we can figure out
+  // its length. For anything we can't figure out, just return UnknownVal.
+  MR = MR->StripCasts();
+
+  switch (MR->getKind()) {
+  case MemRegion::StringRegionKind: {
+    // Modifying the contents of string regions is undefined [C99 6.4.5p6],
+    // so we can assume that the byte length is the correct C string length.
+    ValueManager &ValMgr = C.getValueManager();
+    QualType SizeTy = ValMgr.getContext().getSizeType();
+    const StringLiteral *Str = cast<StringRegion>(MR)->getStringLiteral();
+    return ValMgr.makeIntVal(Str->getByteLength(), SizeTy);
+  }
+  case MemRegion::SymbolicRegionKind:
+  case MemRegion::AllocaRegionKind:
+  case MemRegion::VarRegionKind:
+  case MemRegion::FieldRegionKind:
+  case MemRegion::ObjCIvarRegionKind:
+    return GetCStringLengthForRegion(C, state, Ex, MR);
+  case MemRegion::CompoundLiteralRegionKind:
+    // FIXME: Can we track this? Is it necessary?
+    return UnknownVal();
+  case MemRegion::ElementRegionKind:
+    // FIXME: How can we handle this? It's not good enough to subtract the
+    // offset from the base string length; consider "123\x00567" and &a[5].
+    return UnknownVal();
+  default:
+    // Other regions (mostly non-data) can't have a reliable C string length.
+    // In this case, an error is emitted and UndefinedVal is returned.
+    // The caller should always be prepared to handle this case.
+    if (ExplodedNode *N = C.GenerateNode(state)) {
+      if (!BT_NotCString)
+        BT_NotCString = new BuiltinBug("API",
+          "Argument is not a null-terminated string.");
+
+      llvm::SmallString<120> buf;
+      llvm::raw_svector_ostream os(buf);
+
+      os << "Argument to byte string function is ";
+
+      if (SummarizeRegion(os, C.getASTContext(), MR))
+        os << ", which is not a null-terminated string";
+      else
+        os << "not a null-terminated string";
+
+      // Generate a report for this bug.
+      EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
+                                                        os.str(), N);
+
+      report->addRange(Ex->getSourceRange());
+      C.EmitReport(report);        
     }
-    case MemRegion::SymbolicRegionKind:
-    case MemRegion::AllocaRegionKind:
-    case MemRegion::VarRegionKind:
-    case MemRegion::FieldRegionKind:
-    case MemRegion::ObjCIvarRegionKind:
-      // FIXME: These need to be tracked!
-      break;
-    case MemRegion::CompoundLiteralRegionKind:
-      // FIXME: Can we track this? Is it necessary?
-      break;
-    case MemRegion::ElementRegionKind:
-      // FIXME: How can we handle this? It's not good enough to subtract the
-      // offset from the base string length; consider "123\x00567" and &a[5].
-      break;
-    default: {
-      // Other regions (mostly non-data) can't have a reliable C string length.
-      // In this case, an error is emitted and UndefinedVal is returned.
-      // The caller should always be prepared to handle this case.
-      ExplodedNode *N = C.GenerateSink(state);
-      if (N) {
-        if (!BT_NotCString)
-          BT_NotCString = new BuiltinBug("API",
-            "Argument is not a null-terminated string.");
-
-        llvm::SmallString<120> buf;
-        llvm::raw_svector_ostream os(buf);
-
-        os << "Argument to byte string function is ";
-
-        if (SummarizeRegion(os, C.getASTContext(), MR)) {
-          os << ", which is not a null-terminated string";
-        } else {
-          os << "not a null-terminated string";
-        }
-
-        // Generate a report for this bug.
-        EnhancedBugReport *report = new EnhancedBugReport(*BT_NotCString,
-                                                          os.str(), N);
 
-        report->addRange(Ex->getSourceRange());
-        C.EmitReport(report);        
-      }
-
-      return UndefinedVal();
-    }
-    }
+    return UndefinedVal();
   }
-
-  // If we can't track a certain region's C string length, or if we can't get a
-  // region from the SVal, conjure a value, for use in later constraints.
-  unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
-  ValueManager &ValMgr = C.getValueManager();
-  QualType SizeTy = ValMgr.getContext().getSizeType();
-  return ValMgr.getConjuredSymbolVal(getTag(), Ex, SizeTy, Count);
 }
 
 bool CStringChecker::SummarizeRegion(llvm::raw_ostream& os, ASTContext& Ctx,
@@ -664,19 +686,29 @@ void CStringChecker::EvalStrlen(CheckerContext &C, const CallExpr *CE) {
   state = CheckNonNull(C, state, Arg, ArgVal);
 
   if (state) {
-    // Figure out what the length is, making sure the argument is a C string
-    // (or something similar to a C string). If the argument is valid, the
-    // length will be defined, and we can then set the return value.
     SVal StrLen = GetCStringLength(C, state, Arg, ArgVal);
-    if (!StrLen.isUndef()) {
-      state = state->BindExpr(CE, StrLen);
-      C.addTransition(state);
+
+    // If the argument isn't a valid C string, there's no valid state to
+    // transition to.
+    if (StrLen.isUndef())
+      return;
+
+    // If GetCStringLength couldn't figure out the length, conjure a return
+    // value, so it can be used in constraints, at least.
+    if (StrLen.isUnknown()) {
+      ValueManager &ValMgr = C.getValueManager();
+      unsigned Count = C.getNodeBuilder().getCurrentBlockCount();
+      StrLen = ValMgr.getConjuredSymbolVal(NULL, CE, CE->getType(), Count);
     }
+
+    // Bind the return value.
+    state = state->BindExpr(CE, StrLen);
+    C.addTransition(state);
   }
 }
 
 //===----------------------------------------------------------------------===//
-// The driver method.
+// The driver method, and other Checker callbacks.
 //===----------------------------------------------------------------------===//
 
 bool CStringChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) {
@@ -710,3 +742,129 @@ bool CStringChecker::EvalCallExpr(CheckerContext &C, const CallExpr *CE) {
   (this->*EvalFunction)(C, CE);
   return true;
 }
+
+void CStringChecker::PreVisitDeclStmt(CheckerContext &C, const DeclStmt *DS) {
+  // Record string length for char a[] = "abc";
+  const GRState *state = C.getState();
+
+  for (DeclStmt::const_decl_iterator I = DS->decl_begin(), E = DS->decl_end();
+       I != E; ++I) {
+    const VarDecl *D = dyn_cast<VarDecl>(*I);
+    if (!D)
+      continue;
+
+    // FIXME: Handle array fields of structs.
+    if (!D->getType()->isArrayType())
+      continue;
+
+    const Expr *Init = D->getInit();
+    if (!Init)
+      continue;
+    if (!isa<StringLiteral>(Init))
+      continue;
+
+    Loc VarLoc = state->getLValue(D, C.getPredecessor()->getLocationContext());
+    const MemRegion *MR = VarLoc.getAsRegion();
+    if (!MR)
+      continue;
+
+    SVal StrVal = state->getSVal(Init);
+    assert(StrVal.isValid() && "Initializer string is unknown or undefined");
+    DefinedOrUnknownSVal StrLen
+      = cast<DefinedOrUnknownSVal>(GetCStringLength(C, state, Init, StrVal));
+
+    state = state->set<CStringLength>(MR, StrLen);
+  }
+
+  C.addTransition(state);
+}
+
+bool CStringChecker::WantsRegionChangeUpdate(const GRState *state) {
+  CStringLength::EntryMap Entries = state->get<CStringLength>();
+  return !Entries.isEmpty();
+}
+
+const GRState *CStringChecker::EvalRegionChanges(const GRState *state,
+                                                 const MemRegion * const *Begin,
+                                                 const MemRegion * const *End,
+                                                 bool *) {
+  CStringLength::EntryMap Entries = state->get<CStringLength>();
+  if (Entries.isEmpty())
+    return state;
+
+  llvm::SmallPtrSet<const MemRegion *, 8> Invalidated;
+  llvm::SmallPtrSet<const MemRegion *, 32> SuperRegions;
+
+  // First build sets for the changed regions and their super-regions.
+  for ( ; Begin != End; ++Begin) {
+    const MemRegion *MR = *Begin;
+    Invalidated.insert(MR);
+
+    SuperRegions.insert(MR);
+    while (const SubRegion *SR = dyn_cast<SubRegion>(MR)) {
+      MR = SR->getSuperRegion();
+      SuperRegions.insert(MR);
+    }
+  }
+
+  CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
+
+  // Then loop over the entries in the current state.
+  for (CStringLength::EntryMap::iterator I = Entries.begin(),
+       E = Entries.end(); I != E; ++I) {
+    const MemRegion *MR = I.getKey();
+
+    // Is this entry for a super-region of a changed region?
+    if (SuperRegions.count(MR)) {
+      Entries = F.Remove(Entries, MR);
+      continue;
+    }
+
+    // Is this entry for a sub-region of a changed region?
+    const MemRegion *Super = MR;
+    while (const SubRegion *SR = dyn_cast<SubRegion>(Super)) {
+      Super = SR->getSuperRegion();
+      if (Invalidated.count(Super)) {
+        Entries = F.Remove(Entries, MR);
+        break;
+      }
+    }
+  }
+
+  return state->set<CStringLength>(Entries);
+}
+
+void CStringChecker::MarkLiveSymbols(const GRState *state, SymbolReaper &SR) {
+  // Mark all symbols in our string length map as valid.
+  CStringLength::EntryMap Entries = state->get<CStringLength>();
+
+  for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
+       I != E; ++I) {
+    SVal Len = I.getData();
+    if (SymbolRef Sym = Len.getAsSymbol())
+      SR.markInUse(Sym);
+  }
+}
+
+void CStringChecker::EvalDeadSymbols(CheckerContext &C, SymbolReaper &SR) {
+  if (!SR.hasDeadSymbols())
+    return;
+
+  const GRState *state = C.getState();
+  CStringLength::EntryMap Entries = state->get<CStringLength>();
+  if (Entries.isEmpty())
+    return;
+
+  CStringLength::EntryMap::Factory &F = state->get_context<CStringLength>();
+  for (CStringLength::EntryMap::iterator I = Entries.begin(), E = Entries.end();
+       I != E; ++I) {
+    SVal Len = I.getData();
+    if (SymbolRef Sym = Len.getAsSymbol()) {
+      if (SR.isDead(Sym))
+        Entries = F.Remove(Entries, I.getKey());
+    }
+  }
+
+  state = state->set<CStringLength>(Entries);
+  C.GenerateNode(state);
+}