Split libAnalysis into two libraries: libAnalysis and libChecker.

(1) libAnalysis is a generic analysis library that can be used by
    Sema.  It defines the CFG, basic dataflow analysis primitives, and
    inexpensive flow-sensitive analyses (e.g. LiveVariables).

(2) libChecker contains the guts of the static analyzer, incuding the
    path-sensitive analysis engine and domain-specific checks.

Now any clients that want to use the frontend to build their own tools
don't need to link in the entire static analyzer.

This change exposes various obvious cleanups that can be made to the
layout of files and headers in libChecker.  More changes pending.  :)

This change also exposed a layering violation between AnalysisContext
and MemRegion.  BlockInvocationContext shouldn't explicitly know about
BlockDataRegions.  For now I've removed the BlockDataRegion* from
BlockInvocationContext (removing context-sensitivity; although this
wasn't used yet).  We need to have a better way to extend
BlockInvocationContext (and any LocationContext) to add
context-sensitivty.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@94406 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 250 insertions, 0 deletions

diff --git a/lib/Checker/Store.cpp b/lib/Checker/Store.cpp
new file mode 100644
index 0000000000..98b86a9f46
--- /dev/null
+++ b/lib/Checker/Store.cpp
@@ -0,0 +1,250 @@
+//== Store.cpp - Interface for maps from Locations to Values ----*- C++ -*--==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defined the types Store and StoreManager.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Checker/PathSensitive/Store.h"
+#include "clang/Checker/PathSensitive/GRState.h"
+#include "clang/AST/CharUnits.h"
+
+using namespace clang;
+
+StoreManager::StoreManager(GRStateManager &stateMgr)
+  : ValMgr(stateMgr.getValueManager()), StateMgr(stateMgr),
+    MRMgr(ValMgr.getRegionManager()) {}
+
+const MemRegion *StoreManager::MakeElementRegion(const MemRegion *Base,
+                                              QualType EleTy, uint64_t index) {
+  SVal idx = ValMgr.makeArrayIndex(index);
+  return MRMgr.getElementRegion(EleTy, idx, Base, ValMgr.getContext());
+}
+
+// FIXME: Merge with the implementation of the same method in MemRegion.cpp
+static bool IsCompleteType(ASTContext &Ctx, QualType Ty) {
+  if (const RecordType *RT = Ty->getAs<RecordType>()) {
+    const RecordDecl *D = RT->getDecl();
+    if (!D->getDefinition(Ctx))
+      return false;
+  }
+
+  return true;
+}
+
+const MemRegion *StoreManager::CastRegion(const MemRegion *R, QualType CastToTy) {
+
+  ASTContext& Ctx = StateMgr.getContext();
+
+  // Handle casts to Objective-C objects.
+  if (CastToTy->isObjCObjectPointerType())
+    return R->StripCasts();
+
+  if (CastToTy->isBlockPointerType()) {
+    // FIXME: We may need different solutions, depending on the symbol
+    // involved.  Blocks can be casted to/from 'id', as they can be treated
+    // as Objective-C objects.  This could possibly be handled by enhancing
+    // our reasoning of downcasts of symbolic objects.
+    if (isa<CodeTextRegion>(R) || isa<SymbolicRegion>(R))
+      return R;
+
+    // We don't know what to make of it.  Return a NULL region, which
+    // will be interpretted as UnknownVal.
+    return NULL;
+  }
+
+  // Now assume we are casting from pointer to pointer. Other cases should
+  // already be handled.
+  QualType PointeeTy = CastToTy->getAs<PointerType>()->getPointeeType();
+  QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
+
+  // Handle casts to void*.  We just pass the region through.
+  if (CanonPointeeTy.getLocalUnqualifiedType() == Ctx.VoidTy)
+    return R;
+
+  // Handle casts from compatible types.
+  if (R->isBoundable())
+    if (const TypedRegion *TR = dyn_cast<TypedRegion>(R)) {
+      QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
+      if (CanonPointeeTy == ObjTy)
+        return R;
+    }
+
+  // Process region cast according to the kind of the region being cast.
+  switch (R->getKind()) {
+    case MemRegion::CXXThisRegionKind:
+    case MemRegion::GenericMemSpaceRegionKind:
+    case MemRegion::StackLocalsSpaceRegionKind:
+    case MemRegion::StackArgumentsSpaceRegionKind:
+    case MemRegion::HeapSpaceRegionKind:
+    case MemRegion::UnknownSpaceRegionKind:
+    case MemRegion::GlobalsSpaceRegionKind: {
+      assert(0 && "Invalid region cast");
+      break;
+    }
+    
+    case MemRegion::FunctionTextRegionKind:
+    case MemRegion::BlockTextRegionKind:
+    case MemRegion::BlockDataRegionKind: {
+      // CodeTextRegion should be cast to only a function or block pointer type,
+      // although they can in practice be casted to anything, e.g, void*, char*,
+      // etc.  
+      // Just return the region.
+      return R;
+    }
+
+    case MemRegion::StringRegionKind:
+      // FIXME: Need to handle arbitrary downcasts.
+    case MemRegion::SymbolicRegionKind:
+    case MemRegion::AllocaRegionKind:
+    case MemRegion::CompoundLiteralRegionKind:
+    case MemRegion::FieldRegionKind:
+    case MemRegion::ObjCIvarRegionKind:
+    case MemRegion::VarRegionKind:
+    case MemRegion::CXXObjectRegionKind:
+      return MakeElementRegion(R, PointeeTy);
+
+    case MemRegion::ElementRegionKind: {
+      // If we are casting from an ElementRegion to another type, the
+      // algorithm is as follows:
+      //
+      // (1) Compute the "raw offset" of the ElementRegion from the
+      //     base region.  This is done by calling 'getAsRawOffset()'.
+      //
+      // (2a) If we get a 'RegionRawOffset' after calling
+      //      'getAsRawOffset()', determine if the absolute offset
+      //      can be exactly divided into chunks of the size of the
+      //      casted-pointee type.  If so, create a new ElementRegion with
+      //      the pointee-cast type as the new ElementType and the index
+      //      being the offset divded by the chunk size.  If not, create
+      //      a new ElementRegion at offset 0 off the raw offset region.
+      //
+      // (2b) If we don't a get a 'RegionRawOffset' after calling
+      //      'getAsRawOffset()', it means that we are at offset 0.
+      //
+      // FIXME: Handle symbolic raw offsets.
+
+      const ElementRegion *elementR = cast<ElementRegion>(R);
+      const RegionRawOffset &rawOff = elementR->getAsRawOffset();
+      const MemRegion *baseR = rawOff.getRegion();
+
+      // If we cannot compute a raw offset, throw up our hands and return
+      // a NULL MemRegion*.
+      if (!baseR)
+        return NULL;
+
+      CharUnits off = CharUnits::fromQuantity(rawOff.getByteOffset());
+
+      if (off.isZero()) {
+        // Edge case: we are at 0 bytes off the beginning of baseR.  We
+        // check to see if type we are casting to is the same as the base
+        // region.  If so, just return the base region.
+        if (const TypedRegion *TR = dyn_cast<TypedRegion>(baseR)) {
+          QualType ObjTy = Ctx.getCanonicalType(TR->getValueType(Ctx));
+          QualType CanonPointeeTy = Ctx.getCanonicalType(PointeeTy);
+          if (CanonPointeeTy == ObjTy)
+            return baseR;
+        }
+
+        // Otherwise, create a new ElementRegion at offset 0.
+        return MakeElementRegion(baseR, PointeeTy);
+      }
+
+      // We have a non-zero offset from the base region.  We want to determine
+      // if the offset can be evenly divided by sizeof(PointeeTy).  If so,
+      // we create an ElementRegion whose index is that value.  Otherwise, we
+      // create two ElementRegions, one that reflects a raw offset and the other
+      // that reflects the cast.
+
+      // Compute the index for the new ElementRegion.
+      int64_t newIndex = 0;
+      const MemRegion *newSuperR = 0;
+
+      // We can only compute sizeof(PointeeTy) if it is a complete type.
+      if (IsCompleteType(Ctx, PointeeTy)) {
+        // Compute the size in **bytes**.
+        CharUnits pointeeTySize = Ctx.getTypeSizeInChars(PointeeTy);
+
+        // Is the offset a multiple of the size?  If so, we can layer the
+        // ElementRegion (with elementType == PointeeTy) directly on top of
+        // the base region.
+        if (off % pointeeTySize == 0) {
+          newIndex = off / pointeeTySize;
+          newSuperR = baseR;
+        }
+      }
+
+      if (!newSuperR) {
+        // Create an intermediate ElementRegion to represent the raw byte.
+        // This will be the super region of the final ElementRegion.
+        newSuperR = MakeElementRegion(baseR, Ctx.CharTy, off.getQuantity());
+      }
+
+      return MakeElementRegion(newSuperR, PointeeTy, newIndex);
+    }
+  }
+
+  assert(0 && "unreachable");
+  return 0;
+}
+
+
+/// CastRetrievedVal - Used by subclasses of StoreManager to implement
+///  implicit casts that arise from loads from regions that are reinterpreted
+///  as another region.
+SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R,
+                                    QualType castTy, bool performTestOnly) {
+  
+  if (castTy.isNull())
+    return V;
+  
+  ASTContext &Ctx = ValMgr.getContext();
+
+  if (performTestOnly) {  
+    // Automatically translate references to pointers.
+    QualType T = R->getValueType(Ctx);
+    if (const ReferenceType *RT = T->getAs<ReferenceType>())
+      T = Ctx.getPointerType(RT->getPointeeType());
+    
+    assert(ValMgr.getContext().hasSameUnqualifiedType(castTy, T));
+    return V;
+  }
+  
+  if (const Loc *L = dyn_cast<Loc>(&V))
+    return ValMgr.getSValuator().EvalCastL(*L, castTy);
+  else if (const NonLoc *NL = dyn_cast<NonLoc>(&V))
+    return ValMgr.getSValuator().EvalCastNL(*NL, castTy);
+  
+  return V;
+}
+
+const GRState *StoreManager::InvalidateRegions(const GRState *state,
+                                               const MemRegion * const *I,
+                                               const MemRegion * const *End,
+                                               const Expr *E,
+                                               unsigned Count,
+                                               InvalidatedSymbols *IS) {
+  for ( ; I != End ; ++I)
+    state = InvalidateRegion(state, *I, E, Count, IS);
+  
+  return state;
+}
+
+//===----------------------------------------------------------------------===//
+// Common getLValueXXX methods.
+//===----------------------------------------------------------------------===//
+
+/// getLValueCompoundLiteral - Returns an SVal representing the lvalue
+///   of a compound literal.  Within RegionStore a compound literal
+///   has an associated region, and the lvalue of the compound literal
+///   is the lvalue of that region.
+SVal StoreManager::getLValueCompoundLiteral(const CompoundLiteralExpr* CL,
+                                            const LocationContext *LC) {
+  return loc::MemRegionVal(MRMgr.getCompoundLiteralRegion(CL, LC));
+}