- Allow making ElementRegions with complex offsets (expressions or symbols) for the purpose of bounds-checking.

- Rewrite GRState::AssumeInBound to actually do that checking, and to use the normal constraint path.
- Remove ConstraintManager::AssumeInBound.
- Teach RegionStore and FlatStore to ignore those regions for now.

llvm-svn: 111116

8 files changed, 85 insertions, 46 deletions

diff --git a/clang/include/clang/Checker/PathSensitive/ConstraintManager.h b/clang/include/clang/Checker/PathSensitive/ConstraintManager.h
index ce7d1b38171..97535f55bfb 100644
--- a/clang/include/clang/Checker/PathSensitive/ConstraintManager.h
+++ b/clang/include/clang/Checker/PathSensitive/ConstraintManager.h
@@ -34,9 +34,6 @@ public:
   virtual const GRState *Assume(const GRState *state, DefinedSVal Cond,
                                 bool Assumption) = 0;
 
-  virtual const GRState *AssumeInBound(const GRState *state, DefinedSVal Idx,
-                                       DefinedSVal UpperBound, bool Assumption) = 0;
-
   std::pair<const GRState*, const GRState*> AssumeDual(const GRState *state,
                                                        DefinedSVal Cond) {
     return std::make_pair(Assume(state, Cond, true),
diff --git a/clang/include/clang/Checker/PathSensitive/GRState.h b/clang/include/clang/Checker/PathSensitive/GRState.h
index 36a9c8ce193..141ccece26e 100644
--- a/clang/include/clang/Checker/PathSensitive/GRState.h
+++ b/clang/include/clang/Checker/PathSensitive/GRState.h
@@ -618,9 +618,42 @@ inline const GRState *GRState::AssumeInBound(DefinedOrUnknownSVal Idx,
   if (Idx.isUnknown() || UpperBound.isUnknown())
     return this;
 
-  ConstraintManager &CM = *getStateManager().ConstraintMgr;
-  return CM.AssumeInBound(this, cast<DefinedSVal>(Idx),
-                           cast<DefinedSVal>(UpperBound), Assumption);
+  // Build an expression for 0 <= Idx < UpperBound.
+  // This is the same as Idx + MIN < UpperBound + MIN, if overflow is allowed.
+  // FIXME: This should probably be part of SValuator.
+  GRStateManager &SM = getStateManager();
+  ValueManager &VM = SM.getValueManager();
+  SValuator &SV = VM.getSValuator();
+  ASTContext &Ctx = VM.getContext();
+
+  // Get the offset: the minimum value of the array index type.
+  BasicValueFactory &BVF = VM.getBasicValueFactory();
+  // FIXME: This should be using ValueManager::ArrayIndexTy...somehow.
+  QualType IndexTy = Ctx.IntTy;
+  nonloc::ConcreteInt Min = BVF.getMinValue(IndexTy);
+
+  // Adjust the index.
+  SVal NewIdx = SV.EvalBinOpNN(this, BinaryOperator::Add,
+                               cast<NonLoc>(Idx), Min, IndexTy);
+  if (NewIdx.isUnknownOrUndef())
+    return this;
+
+  // Adjust the upper bound.
+  SVal NewBound = SV.EvalBinOpNN(this, BinaryOperator::Add,
+                                 cast<NonLoc>(UpperBound), Min, IndexTy);
+  if (NewBound.isUnknownOrUndef())
+    return this;
+
+  // Build the actual comparison.
+  SVal InBound = SV.EvalBinOpNN(this, BinaryOperator::LT,
+                                cast<NonLoc>(NewIdx), cast<NonLoc>(NewBound),
+                                Ctx.IntTy);
+  if (InBound.isUnknownOrUndef())
+    return this;
+
+  // Finally, let the constraint manager take care of it.
+  ConstraintManager &CM = SM.getConstraintManager();
+  return CM.Assume(this, cast<DefinedSVal>(InBound), Assumption);
 }
 
 inline const GRState *GRState::bindLoc(SVal LV, SVal V) const {
diff --git a/clang/lib/Checker/FlatStore.cpp b/clang/lib/Checker/FlatStore.cpp
index 7c986a71df5..21fa422166f 100644
--- a/clang/lib/Checker/FlatStore.cpp
+++ b/clang/lib/Checker/FlatStore.cpp
@@ -90,8 +90,9 @@ StoreManager *clang::CreateFlatStoreManager(GRStateManager &StMgr) {
 SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
   const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
   RegionInterval RI = RegionToInterval(R);
-
-  assert(RI.R && "should handle regions with unknown interval");
+  // FIXME: FlatStore should handle regions with unknown intervals.
+  if (!RI.R)
+    return UnknownVal();
 
   RegionBindings B = getRegionBindings(store);
   const BindingVal *BV = B.lookup(RI.R);
@@ -123,7 +124,9 @@ Store FlatStoreManager::Bind(Store store, Loc L, SVal val) {
     BV = *V;
 
   RegionInterval RI = RegionToInterval(R);
-  assert(RI.R && "should handle regions with unknown interval");
+  // FIXME: FlatStore should handle regions with unknown intervals.
+  if (!RI.R)
+    return B.getRoot();
   BV = BVFactory.Add(BV, RI.I, val);
   B = RBFactory.Add(B, RI.R, BV);
   return B.getRoot();
diff --git a/clang/lib/Checker/RegionStore.cpp b/clang/lib/Checker/RegionStore.cpp
index b6ea696c4e1..1c74c3f3a31 100644
--- a/clang/lib/Checker/RegionStore.cpp
+++ b/clang/lib/Checker/RegionStore.cpp
@@ -44,7 +44,7 @@ private:
   uint64_t Offset;
 
   explicit BindingKey(const MemRegion *r, uint64_t offset, Kind k)
-    : P(r, (unsigned) k), Offset(offset) { assert(r); }
+    : P(r, (unsigned) k), Offset(offset) {}
 public:
 
   bool isDefault() const { return P.getInt() == Default; }
@@ -72,6 +72,10 @@ public:
     return P.getOpaqueValue() == X.P.getOpaqueValue() &&
            Offset == X.Offset;
   }
+
+  operator bool() const {
+    return getRegion() != NULL;
+  }
 };
 } // end anonymous namespace
 
@@ -1604,17 +1608,18 @@ BindingKey BindingKey::Make(const MemRegion *R, Kind k) {
   if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
     const RegionRawOffset &O = ER->getAsArrayOffset();
 
-    if (O.getRegion())
-      return BindingKey(O.getRegion(), O.getByteOffset(), k);
-
     // FIXME: There are some ElementRegions for which we cannot compute
-    // raw offsets yet, including regions with symbolic offsets.
+    // raw offsets yet, including regions with symbolic offsets. These will be
+    // ignored by the store.
+    return BindingKey(O.getRegion(), O.getByteOffset(), k);
   }
 
   return BindingKey(R, 0, k);
 }
 
 RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K, SVal V) {
+  if (!K)
+    return B;
   return RBFactory.Add(B, K, V);
 }
 
@@ -1624,6 +1629,8 @@ RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R,
 }
 
 const SVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) {
+  if (!K)
+    return NULL;
   return B.lookup(K);
 }
 
@@ -1634,6 +1641,8 @@ const SVal *RegionStoreManager::Lookup(RegionBindings B,
 }
 
 RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) {
+  if (!K)
+    return B;
   return RBFactory.Remove(B, K);
 }
 
diff --git a/clang/lib/Checker/SimpleConstraintManager.cpp b/clang/lib/Checker/SimpleConstraintManager.cpp
index 321381b045a..cc26a12ea4f 100644
--- a/clang/lib/Checker/SimpleConstraintManager.cpp
+++ b/clang/lib/Checker/SimpleConstraintManager.cpp
@@ -296,28 +296,4 @@ const GRState *SimpleConstraintManager::AssumeSymRel(const GRState *state,
   } // end switch
 }
 
-const GRState *SimpleConstraintManager::AssumeInBound(const GRState *state,
-                                                      DefinedSVal Idx,
-                                                      DefinedSVal UpperBound,
-                                                      bool Assumption) {
-
-  // Only support ConcreteInt for now.
-  if (!(isa<nonloc::ConcreteInt>(Idx) && isa<nonloc::ConcreteInt>(UpperBound)))
-    return state;
-
-  const llvm::APSInt& Zero = state->getBasicVals().getZeroWithPtrWidth(false);
-  llvm::APSInt IdxV = cast<nonloc::ConcreteInt>(Idx).getValue();
-  // IdxV might be too narrow.
-  if (IdxV.getBitWidth() < Zero.getBitWidth())
-    IdxV.extend(Zero.getBitWidth());
-  // UBV might be too narrow, too.
-  llvm::APSInt UBV = cast<nonloc::ConcreteInt>(UpperBound).getValue();
-  if (UBV.getBitWidth() < Zero.getBitWidth())
-    UBV.extend(Zero.getBitWidth());
-
-  bool InBound = (Zero <= IdxV) && (IdxV < UBV);
-  bool isFeasible = Assumption ? InBound : !InBound;
-  return isFeasible ? state : NULL;
-}
-
 }  // end of namespace clang
diff --git a/clang/lib/Checker/SimpleConstraintManager.h b/clang/lib/Checker/SimpleConstraintManager.h
index 45057e64f31..96811b3e36e 100644
--- a/clang/lib/Checker/SimpleConstraintManager.h
+++ b/clang/lib/Checker/SimpleConstraintManager.h
@@ -43,10 +43,6 @@ public:
                               BinaryOperator::Opcode op,
                               const llvm::APSInt& Int);
 
-  const GRState *AssumeInBound(const GRState *state, DefinedSVal Idx,
-                               DefinedSVal UpperBound,
-                               bool Assumption);
-
 protected:
 
   //===------------------------------------------------------------------===//
diff --git a/clang/lib/Checker/Store.cpp b/clang/lib/Checker/Store.cpp
index e0e2c3ad7d3..7c80eed0ead 100644
--- a/clang/lib/Checker/Store.cpp
+++ b/clang/lib/Checker/Store.cpp
@@ -284,10 +284,6 @@ SVal StoreManager::getLValueElement(QualType elementType, SVal Offset,
   if (Base.isUnknownOrUndef() || isa<loc::ConcreteInt>(Base))
     return Base;
 
-  // Only handle integer offsets... for now.
-  if (!isa<nonloc::ConcreteInt>(Offset))
-    return UnknownVal();
-
   const MemRegion* BaseRegion = cast<loc::MemRegionVal>(Base).getRegion();
 
   // Pointer of any type can be cast and used as array base.
@@ -316,6 +312,19 @@ SVal StoreManager::getLValueElement(QualType elementType, SVal Offset,
     return UnknownVal();
 
   const llvm::APSInt& BaseIdxI = cast<nonloc::ConcreteInt>(BaseIdx).getValue();
+
+  // Only allow non-integer offsets if the base region has no offset itself.
+  // FIXME: This is a somewhat arbitrary restriction. We should be using
+  // SValuator here to add the two offsets without checking their types.
+  if (!isa<nonloc::ConcreteInt>(Offset)) {
+    if (isa<ElementRegion>(BaseRegion->StripCasts()))
+      return UnknownVal();
+
+    return loc::MemRegionVal(MRMgr.getElementRegion(elementType, Offset,
+                                                    ElemR->getSuperRegion(),
+                                                    Ctx));
+  }
+
   const llvm::APSInt& OffI = cast<nonloc::ConcreteInt>(Offset).getValue();
   assert(BaseIdxI.isSigned());
 
diff --git a/clang/test/Analysis/outofbound.c b/clang/test/Analysis/outofbound.c
index 529f0e77b26..ed51dc6ac06 100644
--- a/clang/test/Analysis/outofbound.c
+++ b/clang/test/Analysis/outofbound.c
@@ -79,3 +79,19 @@ void alloca_region(int a) {
     x[5] = 5; // expected-warning{{out-of-bound}}
   }
 }
+
+int symbolic_index(int a) {
+  int x[2] = {1, 2};
+  if (a == 2) {
+    return x[a]; // expected-warning{{out-of-bound}}
+  }
+  return 0;
+}
+
+int symbolic_index2(int a) {
+  int x[2] = {1, 2};
+  if (a < 0) {
+    return x[a]; // expected-warning{{out-of-bound}}
+  }
+  return 0;
+}