[analyzer] Add support for C++ dynamic_cast.

Simulate the C++ dynamic_cast in the analyzer.

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

4 files changed, 326 insertions, 8 deletions

diff --git a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
index d0edba175b..5315f4b742 100644
--- a/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
+++ b/include/clang/StaticAnalyzer/Core/PathSensitive/Store.h
@@ -120,9 +120,18 @@ public:
   virtual SVal ArrayToPointer(Loc Array) = 0;
 
   /// Evaluates DerivedToBase casts.
-  virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) {
-    return UnknownVal();
-  }
+  virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType) = 0;
+
+  /// \brief Evaluates C++ dynamic_cast cast.
+  /// The callback may result in the following 3 scenarios:
+  ///  - Successful cast (ex: derived is subclass of base).
+  ///  - Failed cast (ex: derived is definitely not a subclass of base).
+  ///  - We don't know (base is a symbolic region and we don't have 
+  ///    enough info to determine if the cast will succeed at run time).
+  /// The function returns an SVal representing the derived class; it's
+  /// valid only if Failed flag is set to false.
+  virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,
+                                 bool &Failed) = 0;
 
   class CastResult {
     ProgramStateRef state;
diff --git a/lib/StaticAnalyzer/Core/ExprEngineC.cpp b/lib/StaticAnalyzer/Core/ExprEngineC.cpp
index 5ec3bc749e..5070e9d111 100644
--- a/lib/StaticAnalyzer/Core/ExprEngineC.cpp
+++ b/lib/StaticAnalyzer/Core/ExprEngineC.cpp
@@ -283,8 +283,50 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
         Bldr.generateNode(CastE, Pred, state);
         continue;
       }
-        // Various C++ casts that are not handled yet.
-      case CK_Dynamic:
+      // Handle C++ dyn_cast.
+      case CK_Dynamic: {
+        ProgramStateRef state = Pred->getState();
+        const LocationContext *LCtx = Pred->getLocationContext();
+        SVal val = state->getSVal(Ex, LCtx);
+
+        // Compute the type of the result.
+        QualType resultType = CastE->getType();
+        if (CastE->isLValue())
+          resultType = getContext().getPointerType(resultType);
+
+        bool Failed = false;
+
+        // Check if the value being cast evaluates to 0.
+        if (val.isZeroConstant())
+          Failed = true;
+        // Else, evaluate the cast.
+        else
+          val = getStoreManager().evalDynamicCast(val, T, Failed);
+
+        if (Failed) {
+          // If the cast fails, conjure symbol constrained to 0.
+          DefinedOrUnknownSVal NewSym = svalBuilder.getConjuredSymbolVal(NULL,
+                                 CastE, LCtx, resultType,
+                                 currentBuilderContext->getCurrentBlockCount());
+          DefinedOrUnknownSVal Constraint = svalBuilder.evalEQ(state,
+                                 NewSym, svalBuilder.makeZeroVal(resultType));
+          state = state->assume(Constraint, true);
+          state = state->BindExpr(CastE, LCtx, NewSym);
+        } else {
+          // If we don't know if the cast succeeded, conjure a new symbol.
+          if (val.isUnknown()) {
+            DefinedOrUnknownSVal NewSym = svalBuilder.getConjuredSymbolVal(NULL,
+                                 CastE, LCtx, resultType,
+                                 currentBuilderContext->getCurrentBlockCount());
+            state = state->BindExpr(CastE, LCtx, NewSym);
+          } else 
+            // Else, bind to the derived region value.
+            state = state->BindExpr(CastE, LCtx, val);
+        }
+        Bldr.generateNode(CastE, Pred, state);
+        continue;
+      }
+      // Various C++ casts that are not handled yet.
       case CK_ToUnion:
       case CK_BaseToDerived:
       case CK_NullToMemberPointer:
@@ -300,9 +342,8 @@ void ExprEngine::VisitCast(const CastExpr *CastE, const Expr *Ex,
         if (CastE->isLValue())
           resultType = getContext().getPointerType(resultType);
         const LocationContext *LCtx = Pred->getLocationContext();
-        SVal result =
-	  svalBuilder.getConjuredSymbolVal(NULL, CastE, LCtx, resultType,
-                               currentBuilderContext->getCurrentBlockCount());
+        SVal result = svalBuilder.getConjuredSymbolVal(NULL, CastE, LCtx,
+                    resultType, currentBuilderContext->getCurrentBlockCount());
         ProgramStateRef state = Pred->getState()->BindExpr(CastE, LCtx,
                                                                result);
         Bldr.generateNode(CastE, Pred, state);
diff --git a/lib/StaticAnalyzer/Core/RegionStore.cpp b/lib/StaticAnalyzer/Core/RegionStore.cpp
index 1619e6bc64..8fb7e88b38 100644
--- a/lib/StaticAnalyzer/Core/RegionStore.cpp
+++ b/lib/StaticAnalyzer/Core/RegionStore.cpp
@@ -229,6 +229,16 @@ public:
   /// For DerivedToBase casts, create a CXXBaseObjectRegion and return it.
   virtual SVal evalDerivedToBase(SVal derived, QualType basePtrType);
 
+  /// \brief Evaluates C++ dynamic_cast cast.
+  /// The callback may result in the following 3 scenarios:
+  ///  - Successful cast (ex: derived is subclass of base).
+  ///  - Failed cast (ex: derived is definitely not a subclass of base).
+  ///  - We don't know (base is a symbolic region and we don't have 
+  ///    enough info to determine if the cast will succeed at run time).
+  /// The function returns an SVal representing the derived class; it's
+  /// valid only if Failed flag is set to false.
+  virtual SVal evalDynamicCast(SVal base, QualType derivedPtrType,bool &Failed);
+
   StoreRef getInitialStore(const LocationContext *InitLoc) {
     return StoreRef(RBFactory.getEmptyMap().getRootWithoutRetain(), *this);
   }
@@ -877,6 +887,79 @@ SVal RegionStoreManager::evalDerivedToBase(SVal derived, QualType baseType) {
   return loc::MemRegionVal(baseReg);
 }
 
+SVal RegionStoreManager::evalDynamicCast(SVal base, QualType derivedType,
+                                         bool &Failed) {
+  Failed = false;
+
+  loc::MemRegionVal *baseRegVal = dyn_cast<loc::MemRegionVal>(&base);
+  if (!baseRegVal)
+    return UnknownVal();
+  const MemRegion *BaseRegion = baseRegVal->stripCasts();
+
+  // Assume the derived class is a pointer to a CXX record.
+  // TODO: Note, we do not model reference types: a bad_cast exception is thrown
+  // when a cast of reference fails, but we just return an UnknownVal.
+  if (!derivedType->isPointerType())
+    return UnknownVal();
+  derivedType = derivedType->getPointeeType();
+  assert(!derivedType.isNull());
+  const CXXRecordDecl *DerivedDecl = derivedType->getAsCXXRecordDecl();
+  if (!DerivedDecl && !derivedType->isVoidType())
+    return UnknownVal();
+
+  // Drill down the CXXBaseObject chains, which represent upcasts (casts from
+  // derived to base).
+  const MemRegion *SR = BaseRegion;
+  while (const TypedRegion *TSR = dyn_cast_or_null<TypedRegion>(SR)) {
+    QualType BaseType = TSR->getLocationType()->getPointeeType();
+    assert(!BaseType.isNull());
+    const CXXRecordDecl *SRDecl = BaseType->getAsCXXRecordDecl();
+    if (!SRDecl)
+      return UnknownVal();
+
+    // If found the derived class, the cast succeeds.
+    if (SRDecl == DerivedDecl)
+      return loc::MemRegionVal(TSR);
+
+    // If the region type is a subclass of the derived type.
+    if (!derivedType->isVoidType() && SRDecl->isDerivedFrom(DerivedDecl)) {
+      // This occurs in two cases.
+      // 1) We are processing an upcast.
+      // 2) We are processing a downcast but we jumped directly from the
+      // ancestor to a child of the cast value, so conjure the
+      // appropriate region to represent value (the intermediate node).
+      return loc::MemRegionVal(MRMgr.getCXXBaseObjectRegion(DerivedDecl,
+                                                            BaseRegion));
+    }
+
+    // If super region is not a parent of derived class, the cast definitely
+    // fails.
+    if (!derivedType->isVoidType() &&
+        DerivedDecl->isProvablyNotDerivedFrom(SRDecl)) {
+      Failed = true;
+      return UnknownVal();
+    }
+
+    if (const CXXBaseObjectRegion *R = dyn_cast<CXXBaseObjectRegion>(TSR))
+      // Drill down the chain to get the derived classes.
+      SR = R->getSuperRegion();
+    else {
+      // We reached the bottom of the hierarchy.
+
+      // If this is a cast to void*, return the region.
+      if (derivedType->isVoidType())
+        return loc::MemRegionVal(TSR);
+
+      // We did not find the derived class. We we must be casting the base to
+      // derived, so the cast should fail.
+      Failed = true;
+      return UnknownVal();
+    }
+  }
+
+  return UnknownVal();
+}
+
 //===----------------------------------------------------------------------===//
 // Loading values from regions.
 //===----------------------------------------------------------------------===//
diff --git a/test/Analysis/dynamic-cast.cpp b/test/Analysis/dynamic-cast.cpp
new file mode 100644
index 0000000000..0d0c80fc12
--- /dev/null
+++ b/test/Analysis/dynamic-cast.cpp
@@ -0,0 +1,185 @@
+// RUN: %clang_cc1 -triple i386-apple-darwin10 -analyze -analyzer-checker=core -verify %s
+
+class A {
+public:
+    virtual void f(){};
+
+};
+class B : public A{
+public:
+  int m;
+};
+class C : public A{};
+
+class BB: public B{};
+
+// A lot of the tests below have the if statement in them, which forces the
+// analyzer to explore both path - when the result is 0 and not. This makes
+// sure that we definitely know that the result is non-0 (as the result of
+// the cast).
+int testDynCastFromRadar() {
+    B aa;
+    A *a = &aa;
+    const int* res = 0;
+    B *b = dynamic_cast<B*>(a);
+    static const int i = 5;
+    if(b) {
+        res = &i;
+    } else {
+        res = 0;
+    }
+    return *res; // no warning
+}
+
+int testBaseToBase1() {
+  B b;
+  B *pb = &b;
+  B *pbb = dynamic_cast<B*>(pb);
+  const int* res = 0;
+  static const int i = 5;
+  if (pbb) {
+      res = &i;
+  } else {
+      res = 0;
+  }
+  return *res; // no warning
+}
+
+int testMultipleLevelsOfSubclassing1() {
+  BB bb;
+  B *pb = &bb;
+  A *pa = pb;
+  B *b = dynamic_cast<B*>(pa);
+  const int* res = 0;
+  static const int i = 5;
+  if (b) {
+      res = &i;
+  } else {
+      res = 0;
+  }
+  return *res; // no warning
+}
+
+int testMultipleLevelsOfSubclassing2() {
+  BB bb;
+  A *pbb = &bb;
+  B *b = dynamic_cast<B*>(pbb);
+  BB *s = dynamic_cast<BB*>(b);
+  const int* res = 0;
+  static const int i = 5;
+  if (s) {
+      res = &i;
+  } else {
+      res = 0;
+  }
+  return *res; // no warning
+}
+
+int testMultipleLevelsOfSubclassing3() {
+  BB bb;
+  A *pbb = &bb;
+  B *b = dynamic_cast<B*>(pbb);
+  return b->m; // no warning
+}
+
+int testLHS() {
+    B aa;
+    A *a = &aa;
+    return (dynamic_cast<B*>(a))->m;
+}
+
+int testLHS2() {
+    B aa;
+    A *a = &aa;
+    return (*dynamic_cast<B*>(a)).m;
+}
+
+int testDynCastUnknown2(class A *a) {
+  B *b = dynamic_cast<B*>(a);
+  return b->m; // no warning
+}
+
+int testDynCastUnknown(class A *a) {
+  B *b = dynamic_cast<B*>(a);
+  const int* res = 0;
+  static const int i = 5;
+  if (b) {
+    res = &i;
+  } else {
+    res = 0;
+  }
+  return *res; // expected-warning {{Dereference of null pointer}}
+}
+
+int testDynCastFail2() {
+  C c;
+  A *pa = &c;
+  B *b = dynamic_cast<B*>(pa);
+  return b->m; // expected-warning {{dereference of a null pointer}}
+}
+
+int testLHSFail() {
+    C c;
+    A *a = &c;
+    return (*dynamic_cast<B*>(a)).m; // expected-warning {{Dereference of null pointer}}
+}
+
+int testBaseToDerivedFail() {
+  A a;
+  B *b = dynamic_cast<B*>(&a);
+  return b->m; // expected-warning {{dereference of a null pointer}}
+}
+
+int testConstZeroFail() {
+  B *b = dynamic_cast<B*>((A *)0);
+  return b->m; // expected-warning {{dereference of a null pointer}}
+}
+
+int testConstZeroFail2() {
+  A *a = 0;
+  B *b = dynamic_cast<B*>(a);
+  return b->m; // expected-warning {{dereference of a null pointer}}
+}
+
+int testUpcast() {
+  B b;
+  A *a = dynamic_cast<A*>(&b);
+  const int* res = 0;
+  static const int i = 5;
+  if (a) {
+      res = &i;
+  } else {
+      res = 0;
+  }
+  return *res; // no warning
+}
+
+int testCastToVoidStar() {
+  A a;
+  void *b = dynamic_cast<void*>(&a);
+  const int* res = 0;
+  static const int i = 5;
+  if (b) {
+      res = &i;
+  } else {
+      res = 0;
+  }
+  return *res; // no warning
+}
+
+int testReference() {
+  A a;
+  B &b = dynamic_cast<B&>(a);
+  return b.m; // no warning
+}
+
+// False negatives.
+
+// Symbolic regions are not typed, so we cannot deduce that the cast will
+// always fail in this case.
+int testDynCastFail1(class C *c) {
+  B *b = 0;
+  b = dynamic_cast<B*>(c);
+  return b->m;
+}
+