[cfe-dev] Symbolic Extents

[Jordy Rose]

The start of work on symbolic extents. I wanted to ask what the best way
to handle this was. It seems we should have a general EvaluateSymExpr
method somewhere that simplifies a SymExpr as much as possible, which is
what the getKnownExtent() method (see patch) would eventually be doing. Or
perhaps EvaluateSVal, to handle ConcreteInts as well.

It's also going to soon become helpful to ask for the minimum or maximum
value of a SymExpr -- knowing the upper bound on an array size would
certainly be better than no information at all. What should the API for
that be?

(One goal of mine is to be able to model that the length of argv is argc.)

Jordy
-------------- next part --------------
Index: include/clang/Checker/PathSensitive/Store.h
===================================================================
--- include/clang/Checker/PathSensitive/Store.h	(revision 106771)
+++ include/clang/Checker/PathSensitive/Store.h	(working copy)
@@ -181,6 +181,11 @@
     return llvm::Optional<SVal>();
   }
 
+  virtual const llvm::APSInt *getKnownExtent(const GRState *state,
+                                             const MemRegion *R) {
+    return NULL;
+  }
+
   /// EnterStackFrame - Let the StoreManager to do something when execution
   /// engine is about to execute into a callee.
   virtual const GRState *EnterStackFrame(const GRState *state,
Index: lib/Checker/RegionStore.cpp
===================================================================
--- lib/Checker/RegionStore.cpp	(revision 106771)
+++ lib/Checker/RegionStore.cpp	(working copy)
@@ -384,6 +384,21 @@
       return Optional<SVal>();
   }
 
+  const llvm::APSInt *getKnownExtent(const GRState *state, const MemRegion *R) {
+    Optional<SVal> V = getExtent(state, R);
+    if (!V)
+      return NULL;
+
+    if (nonloc::ConcreteInt *Int = dyn_cast<nonloc::ConcreteInt>(&V))
+      return &Int->getValue();
+
+    if (SymbolRef Sym = V->getAsSymbol())
+      return state->getSymVal(Sym);
+
+    // FIXME: This should eventually try to evaluate symbolic expressions.
+    return NULL;
+  }
+
   DefinedOrUnknownSVal getSizeInElements(const GRState *state,
                                          const MemRegion* R, QualType EleTy);
 
@@ -773,15 +788,11 @@
       return UnknownVal();
 
     case MemRegion::SymbolicRegionKind: {
-      const SVal *Size = state->get<RegionExtents>(R);
+      const llvm::APSInt *Size = getKnownExtent(state, R);
       if (!Size)
         return UnknownVal();
-      const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(Size);
-      if (!CI)
-        return UnknownVal();
 
-      CharUnits RegionSize =
-        CharUnits::fromQuantity(CI->getValue().getSExtValue());
+      CharUnits RegionSize = CharUnits::fromQuantity(Size->getSExtValue());
       CharUnits EleSize = getContext().getTypeSizeInChars(EleTy);
       assert(RegionSize % EleSize == 0);
 
Index: lib/Checker/CastSizeChecker.cpp
===================================================================
--- lib/Checker/CastSizeChecker.cpp	(revision 106771)
+++ lib/Checker/CastSizeChecker.cpp	(working copy)
@@ -44,7 +44,8 @@
 
   QualType ToPointeeTy = ToPTy->getPointeeType();
 
-  const MemRegion *R = C.getState()->getSVal(E).getAsRegion();
+  const GRState *state = C.getState();
+  const MemRegion *R = state->getSVal(E).getAsRegion();
   if (R == 0)
     return;
 
@@ -52,17 +53,13 @@
   if (SR == 0)
     return;
 
-  llvm::Optional<SVal> V = 
-                    C.getEngine().getStoreManager().getExtent(C.getState(), SR);
-  if (!V)
+  StoreManager &StoreMgr = C.getEngine().getStoreManager();
+  const llvm::APSInt *Extent = StoreMgr.getKnownExtent(state, SR);
+  if (!Extent)
     return;
 
-  const nonloc::ConcreteInt *CI = dyn_cast<nonloc::ConcreteInt>(V);
-  if (!CI)
-    return;
-
-  CharUnits RegionSize = CharUnits::fromQuantity(CI->getValue().getSExtValue());
-  CharUnits TypeSize = C.getASTContext().getTypeSizeInChars(ToPointeeTy);
+  CharUnits RegionSize = CharUnits::fromQuantity(Extent->getSExtValue());
+  CharUnits TypeSize = Ctx.getTypeSizeInChars(ToPointeeTy);
   
   // void, and a few other un-sizeable types
   if (TypeSize.isZero())
Index: test/Analysis/outofbound.c
===================================================================
--- test/Analysis/outofbound.c	(revision 106771)
+++ test/Analysis/outofbound.c	(working copy)
@@ -3,6 +3,7 @@
 typedef __typeof(sizeof(int)) size_t;
 void *malloc(size_t);
 void *calloc(size_t, size_t);
+void free(void *);
 
 char f1() {
   char* s = "abcd";
@@ -43,3 +44,13 @@
   p[3] = '.'; // no-warning
   p[4] = '!'; // expected-warning{{out-of-bound}}
 }
+
+void symbolic1(size_t a) {
+  char *buf = (char*) malloc(a);
+  if (a == 1) {
+    buf[1] = 'b'; // expected-warning {{out-of-bound}}
+  } else {
+    buf[1] = 'b'; // no-warning
+  }
+  free(buf);
+}