1 files changed, 204 insertions, 0 deletions
diff --git a/lib/StaticAnalyzer/Core/FlatStore.cpp b/lib/StaticAnalyzer/Core/FlatStore.cpp
new file mode 100644
index 0000000..99a5ead
--- /dev/null
+++ b/lib/StaticAnalyzer/Core/FlatStore.cpp
@@ -0,0 +1,204 @@
+//=== FlatStore.cpp - Flat region-based store model -------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/GRState.h"
+#include "llvm/ADT/ImmutableIntervalMap.h"
+#include "llvm/Support/ErrorHandling.h"
+
+using namespace clang;
+using namespace ento;
+using llvm::Interval;
+
+// The actual store type.
+typedef llvm::ImmutableIntervalMap<SVal> BindingVal;
+typedef llvm::ImmutableMap<const MemRegion *, BindingVal> RegionBindings;
+
+namespace {
+class FlatStoreManager : public StoreManager {
+  RegionBindings::Factory RBFactory;
+  BindingVal::Factory BVFactory;
+
+public:
+  FlatStoreManager(GRStateManager &mgr) 
+    : StoreManager(mgr), 
+      RBFactory(mgr.getAllocator()), 
+      BVFactory(mgr.getAllocator()) {}
+
+  SVal Retrieve(Store store, Loc L, QualType T);
+  StoreRef Bind(Store store, Loc L, SVal val);
+  StoreRef Remove(Store St, Loc L);
+  StoreRef BindCompoundLiteral(Store store, const CompoundLiteralExpr* cl,
+                            const LocationContext *LC, SVal v);
+
+  StoreRef getInitialStore(const LocationContext *InitLoc) {
+    return StoreRef(RBFactory.getEmptyMap().getRoot(), *this);
+  }
+
+  SubRegionMap *getSubRegionMap(Store store) {
+    return 0;
+  }
+
+  SVal ArrayToPointer(Loc Array);
+  StoreRef removeDeadBindings(Store store, const StackFrameContext *LCtx,
+                              SymbolReaper& SymReaper,
+                          llvm::SmallVectorImpl<const MemRegion*>& RegionRoots){
+    return StoreRef(store, *this);
+  }
+
+  StoreRef BindDecl(Store store, const VarRegion *VR, SVal initVal);
+
+  StoreRef BindDeclWithNoInit(Store store, const VarRegion *VR);
+
+  typedef llvm::DenseSet<SymbolRef> InvalidatedSymbols;
+  
+  StoreRef invalidateRegions(Store store, const MemRegion * const *I,
+                             const MemRegion * const *E, const Expr *Ex,
+                             unsigned Count, InvalidatedSymbols *IS,
+                             bool invalidateGlobals,
+                             InvalidatedRegions *Regions);
+
+  void print(Store store, llvm::raw_ostream& Out, const char* nl, 
+             const char *sep);
+  void iterBindings(Store store, BindingsHandler& f);
+
+private:
+  static RegionBindings getRegionBindings(Store store) {
+    return RegionBindings(static_cast<const RegionBindings::TreeTy*>(store));
+  }
+
+  class RegionInterval {
+  public:
+    const MemRegion *R;
+    Interval I;
+    RegionInterval(const MemRegion *r, int64_t s, int64_t e) : R(r), I(s, e){}
+  };
+
+  RegionInterval RegionToInterval(const MemRegion *R);
+
+  SVal RetrieveRegionWithNoBinding(const MemRegion *R, QualType T);
+};
+} // end anonymous namespace
+
+StoreManager *ento::CreateFlatStoreManager(GRStateManager &StMgr) {
+  return new FlatStoreManager(StMgr);
+}
+
+SVal FlatStoreManager::Retrieve(Store store, Loc L, QualType T) {
+  const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
+  RegionInterval RI = RegionToInterval(R);
+  // FIXME: FlatStore should handle regions with unknown intervals.
+  if (!RI.R)
+    return UnknownVal();
+
+  RegionBindings B = getRegionBindings(store);
+  const BindingVal *BV = B.lookup(RI.R);
+  if (BV) {
+    const SVal *V = BVFactory.lookup(*BV, RI.I);
+    if (V)
+      return *V;
+    else
+      return RetrieveRegionWithNoBinding(R, T);
+  }
+  return RetrieveRegionWithNoBinding(R, T);
+}
+
+SVal FlatStoreManager::RetrieveRegionWithNoBinding(const MemRegion *R,
+                                                   QualType T) {
+  if (R->hasStackNonParametersStorage())
+    return UndefinedVal();
+  else
+    return svalBuilder.getRegionValueSymbolVal(cast<TypedRegion>(R));
+}
+
+StoreRef FlatStoreManager::Bind(Store store, Loc L, SVal val) {
+  const MemRegion *R = cast<loc::MemRegionVal>(L).getRegion();
+  RegionBindings B = getRegionBindings(store);
+  const BindingVal *V = B.lookup(R);
+
+  BindingVal BV = BVFactory.getEmptyMap();
+  if (V)
+    BV = *V;
+
+  RegionInterval RI = RegionToInterval(R);
+  // FIXME: FlatStore should handle regions with unknown intervals.
+  if (!RI.R)
+    return StoreRef(B.getRoot(), *this);
+  BV = BVFactory.add(BV, RI.I, val);
+  B = RBFactory.add(B, RI.R, BV);
+  return StoreRef(B.getRoot(), *this);
+}
+
+StoreRef FlatStoreManager::Remove(Store store, Loc L) {
+  return StoreRef(store, *this);
+}
+
+StoreRef FlatStoreManager::BindCompoundLiteral(Store store,
+                                            const CompoundLiteralExpr* cl,
+                                            const LocationContext *LC,
+                                            SVal v) {
+  return StoreRef(store, *this);
+}
+
+SVal FlatStoreManager::ArrayToPointer(Loc Array) {
+  return Array;
+}
+
+StoreRef FlatStoreManager::BindDecl(Store store, const VarRegion *VR, 
+                                    SVal initVal) {
+  return Bind(store, svalBuilder.makeLoc(VR), initVal);
+}
+
+StoreRef FlatStoreManager::BindDeclWithNoInit(Store store, const VarRegion *VR){
+  return StoreRef(store, *this);
+}
+
+StoreRef FlatStoreManager::invalidateRegions(Store store,
+                                             const MemRegion * const *I,
+                                             const MemRegion * const *E,
+                                             const Expr *Ex, unsigned Count,
+                                             InvalidatedSymbols *IS,
+                                             bool invalidateGlobals,
+                                             InvalidatedRegions *Regions) {
+  assert(false && "Not implemented");
+  return StoreRef(store, *this);
+}
+
+void FlatStoreManager::print(Store store, llvm::raw_ostream& Out, 
+                             const char* nl, const char *sep) {
+}
+
+void FlatStoreManager::iterBindings(Store store, BindingsHandler& f) {
+}
+
+FlatStoreManager::RegionInterval 
+FlatStoreManager::RegionToInterval(const MemRegion *R) { 
+  switch (R->getKind()) {
+  case MemRegion::VarRegionKind: {
+    QualType T = cast<VarRegion>(R)->getValueType();
+    int64_t Size = Ctx.getTypeSize(T);
+    return RegionInterval(R, 0, Size-1);
+  }
+
+  case MemRegion::ElementRegionKind: 
+  case MemRegion::FieldRegionKind: {
+    RegionOffset Offset = R->getAsOffset();
+    // We cannot compute offset for all regions, for example, elements
+    // with symbolic offsets.
+    if (!Offset.getRegion())
+      return RegionInterval(0, 0, 0);
+    int64_t Start = Offset.getOffset();
+    int64_t Size = Ctx.getTypeSize(cast<TypedRegion>(R)->getValueType());
+    return RegionInterval(Offset.getRegion(), Start, Start+Size);
+  }
+
+  default:
+    llvm_unreachable("Region kind unhandled.");
+    return RegionInterval(0, 0, 0);
+  }
+}