[analyzer] CastValueChecker: Store the dynamic types and casts

Summary:
This patch introduces `DynamicCastInfo` similar to `DynamicTypeInfo` which
is stored in `CastSets` which are storing the dynamic cast informations of
objects based on memory regions. It could be used to store and check the
casts and prevent infeasible paths.

Reviewed By: NoQ

Differential Revision: https://reviews.llvm.org/D66325

llvm-svn: 369605

6 files changed, 404 insertions, 211 deletions

diff --git a/clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp b/clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp
index 9cf1b0a020a..e7472ab156b 100644
--- a/clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp
@@ -6,7 +6,13 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// This defines CastValueChecker which models casts of custom RTTIs.
+//  This defines CastValueChecker which models casts of custom RTTIs.
+//
+// TODO list:
+// - It only allows one succesful cast between two types however in the wild
+//   the object could be casted to multiple types.
+// - It needs to check the most likely type information from the dynamic type
+//   map to increase precision of dynamic casting.
 //
 //===----------------------------------------------------------------------===//
 
@@ -15,6 +21,7 @@
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
 #include "llvm/ADT/Optional.h"
 #include <utility>
 
@@ -23,219 +30,281 @@ using namespace ento;
 
 namespace {
 class CastValueChecker : public Checker<eval::Call> {
-  enum class CastKind { Function, Method };
+  enum class CallKind { Function, Method };
 
   using CastCheck =
-      std::function<void(const CastValueChecker *, const CallExpr *,
+      std::function<void(const CastValueChecker *, const CallEvent &Call,
                          DefinedOrUnknownSVal, CheckerContext &)>;
 
-  using CheckKindPair = std::pair<CastCheck, CastKind>;
-
 public:
   // We have five cases to evaluate a cast:
-  // 1) The parameter is non-null, the return value is non-null
-  // 2) The parameter is non-null, the return value is null
-  // 3) The parameter is null, the return value is null
+  // 1) The parameter is non-null, the return value is non-null.
+  // 2) The parameter is non-null, the return value is null.
+  // 3) The parameter is null, the return value is null.
   // cast: 1;  dyn_cast: 1, 2;  cast_or_null: 1, 3;  dyn_cast_or_null: 1, 2, 3.
   //
-  // 4) castAs: has no parameter, the return value is non-null.
-  // 5) getAs:  has no parameter, the return value is null or non-null.
+  // 4) castAs: Has no parameter, the return value is non-null.
+  // 5) getAs:  Has no parameter, the return value is null or non-null.
   bool evalCall(const CallEvent &Call, CheckerContext &C) const;
+  void checkDeadSymbols(SymbolReaper &SR, CheckerContext &C) const;
 
 private:
   // These are known in the LLVM project. The pairs are in the following form:
   // {{{namespace, call}, argument-count}, {callback, kind}}
-  const CallDescriptionMap<CheckKindPair> CDM = {
+  const CallDescriptionMap<std::pair<CastCheck, CallKind>> CDM = {
       {{{"llvm", "cast"}, 1},
-       {&CastValueChecker::evalCast, CastKind::Function}},
+       {&CastValueChecker::evalCast, CallKind::Function}},
       {{{"llvm", "dyn_cast"}, 1},
-       {&CastValueChecker::evalDynCast, CastKind::Function}},
+       {&CastValueChecker::evalDynCast, CallKind::Function}},
       {{{"llvm", "cast_or_null"}, 1},
-       {&CastValueChecker::evalCastOrNull, CastKind::Function}},
+       {&CastValueChecker::evalCastOrNull, CallKind::Function}},
       {{{"llvm", "dyn_cast_or_null"}, 1},
-       {&CastValueChecker::evalDynCastOrNull, CastKind::Function}},
+       {&CastValueChecker::evalDynCastOrNull, CallKind::Function}},
       {{{"clang", "castAs"}, 0},
-       {&CastValueChecker::evalCastAs, CastKind::Method}},
+       {&CastValueChecker::evalCastAs, CallKind::Method}},
       {{{"clang", "getAs"}, 0},
-       {&CastValueChecker::evalGetAs, CastKind::Method}}};
+       {&CastValueChecker::evalGetAs, CallKind::Method}}};
 
-  void evalCast(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
                 CheckerContext &C) const;
-  void evalDynCast(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalDynCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
                    CheckerContext &C) const;
-  void evalCastOrNull(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
                       CheckerContext &C) const;
-  void evalDynCastOrNull(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalDynCastOrNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
                          CheckerContext &C) const;
-  void evalCastAs(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalCastAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
                   CheckerContext &C) const;
-  void evalGetAs(const CallExpr *CE, DefinedOrUnknownSVal DV,
+  void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
                  CheckerContext &C) const;
 };
 } // namespace
 
-static std::string getCastName(const Expr *Cast) {
-  QualType Ty = Cast->getType();
-  if (const CXXRecordDecl *RD = Ty->getAsCXXRecordDecl())
-    return RD->getNameAsString();
+static QualType getRecordType(QualType Ty) {
+  Ty = Ty.getCanonicalType();
+
+  if (Ty->isPointerType())
+    Ty = Ty->getPointeeType();
+
+  if (Ty->isReferenceType())
+    Ty = Ty.getNonReferenceType();
 
-  return Ty->getPointeeCXXRecordDecl()->getNameAsString();
+  return Ty.getUnqualifiedType();
 }
 
-static const NoteTag *getCastTag(bool IsNullReturn, const CallExpr *CE,
-                                 CheckerContext &C,
-                                 bool IsCheckedCast = false) {
-  Optional<std::string> CastFromName = (CE->getNumArgs() > 0)
-                                           ? getCastName(CE->getArg(0))
-                                           : Optional<std::string>();
-  std::string CastToName = getCastName(CE);
+static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
+                             bool CastSucceeds) {
+  if (!CastInfo)
+    return false;
+
+  return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
+}
+
+static const NoteTag *getNoteTag(CheckerContext &C,
+                                 const DynamicCastInfo *CastInfo,
+                                 QualType CastToTy, const Expr *Object,
+                                 bool CastSucceeds, bool IsKnownCast) {
+  std::string CastToName =
+      CastInfo ? CastInfo->to()->getAsCXXRecordDecl()->getNameAsString()
+               : CastToTy->getAsCXXRecordDecl()->getNameAsString();
+  Object = Object->IgnoreParenImpCasts();
 
   return C.getNoteTag(
-      [CastFromName, CastToName, IsNullReturn,
-       IsCheckedCast](BugReport &) -> std::string {
+      [=] {
         SmallString<128> Msg;
         llvm::raw_svector_ostream Out(Msg);
 
-        Out << (!IsCheckedCast ? "Assuming dynamic cast " : "Checked cast ");
-        if (CastFromName)
-          Out << "from '" << *CastFromName << "' ";
+        if (!IsKnownCast)
+          Out << "Assuming ";
+
+        if (const auto *DRE = dyn_cast<DeclRefExpr>(Object)) {
+          Out << '\'' << DRE->getDecl()->getNameAsString() << '\'';
+        } else if (const auto *ME = dyn_cast<MemberExpr>(Object)) {
+          Out << (IsKnownCast ? "Field '" : "field '")
+              << ME->getMemberDecl()->getNameAsString() << '\'';
+        } else {
+          Out << (IsKnownCast ? "The object" : "the object");
+        }
 
-        Out << "to '" << CastToName << "' "
-            << (!IsNullReturn ? "succeeds" : "fails");
+        Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
+            << '\'';
 
         return Out.str();
       },
       /*IsPrunable=*/true);
 }
 
-static ProgramStateRef getState(bool IsNullReturn,
-                                DefinedOrUnknownSVal ReturnDV,
-                                const CallExpr *CE, ProgramStateRef State,
-                                CheckerContext &C) {
-  return State->BindExpr(
-      CE, C.getLocationContext(),
-      IsNullReturn ? C.getSValBuilder().makeNull() : ReturnDV, false);
+//===----------------------------------------------------------------------===//
+// Main logic to evaluate a cast.
+//===----------------------------------------------------------------------===//
+
+static void addCastTransition(const CallEvent &Call, DefinedOrUnknownSVal DV,
+                              CheckerContext &C, bool IsNonNullParam,
+                              bool IsNonNullReturn,
+                              bool IsCheckedCast = false) {
+  ProgramStateRef State = C.getState()->assume(DV, IsNonNullParam);
+  if (!State)
+    return;
+
+  const Expr *Object;
+  QualType CastFromTy;
+  QualType CastToTy = getRecordType(Call.getResultType());
+
+  if (Call.getNumArgs() > 0) {
+    Object = Call.getArgExpr(0);
+    CastFromTy = getRecordType(Call.parameters()[0]->getType());
+  } else {
+    Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();
+    CastFromTy = getRecordType(Object->getType());
+  }
+
+  const MemRegion *MR = DV.getAsRegion();
+  const DynamicCastInfo *CastInfo =
+      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
+
+  // We assume that every checked cast succeeds.
+  bool CastSucceeds = IsCheckedCast || CastFromTy == CastToTy;
+  if (!CastSucceeds) {
+    if (CastInfo)
+      CastSucceeds = IsNonNullReturn && CastInfo->succeeds();
+    else
+      CastSucceeds = IsNonNullReturn;
+  }
+
+  // Check for infeasible casts.
+  if (isInfeasibleCast(CastInfo, CastSucceeds)) {
+    C.generateSink(State, C.getPredecessor());
+    return;
+  }
+
+  // Store the type and the cast information.
+  bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy;
+  if (!IsKnownCast || IsCheckedCast)
+    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
+                                      Call.getResultType(), CastSucceeds);
+
+  SVal V = CastSucceeds ? DV : C.getSValBuilder().makeNull();
+  C.addTransition(
+      State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),
+      getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
 }
 
 //===----------------------------------------------------------------------===//
 // Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
 //===----------------------------------------------------------------------===//
 
-static void evalNonNullParamNonNullReturn(const CallExpr *CE,
+static void evalNonNullParamNonNullReturn(const CallEvent &Call,
                                           DefinedOrUnknownSVal DV,
                                           CheckerContext &C,
                                           bool IsCheckedCast = false) {
-  bool IsNullReturn = false;
-  if (ProgramStateRef State = C.getState()->assume(DV, true))
-    C.addTransition(getState(IsNullReturn, DV, CE, State, C),
-                    getCastTag(IsNullReturn, CE, C, IsCheckedCast));
+  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
+                    /*IsNonNullReturn=*/true, IsCheckedCast);
 }
 
-static void evalNonNullParamNullReturn(const CallExpr *CE,
+static void evalNonNullParamNullReturn(const CallEvent &Call,
                                        DefinedOrUnknownSVal DV,
                                        CheckerContext &C) {
-  bool IsNullReturn = true;
-  if (ProgramStateRef State = C.getState()->assume(DV, true))
-    C.addTransition(getState(IsNullReturn, DV, CE, State, C),
-                    getCastTag(IsNullReturn, CE, C));
+  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
+                    /*IsNonNullReturn=*/false);
 }
 
-static void evalNullParamNullReturn(const CallExpr *CE, DefinedOrUnknownSVal DV,
+static void evalNullParamNullReturn(const CallEvent &Call,
+                                    DefinedOrUnknownSVal DV,
                                     CheckerContext &C) {
   if (ProgramStateRef State = C.getState()->assume(DV, false))
-    C.addTransition(getState(/*IsNullReturn=*/true, DV, CE, State, C),
+    C.addTransition(State->BindExpr(Call.getOriginExpr(),
+                                    C.getLocationContext(),
+                                    C.getSValBuilder().makeNull(), false),
                     C.getNoteTag("Assuming null pointer is passed into cast",
                                  /*IsPrunable=*/true));
 }
 
-void CastValueChecker::evalCast(const CallExpr *CE, DefinedOrUnknownSVal DV,
+void CastValueChecker::evalCast(const CallEvent &Call, DefinedOrUnknownSVal DV,
                                 CheckerContext &C) const {
-  evalNonNullParamNonNullReturn(CE, DV, C, /*IsCheckedCast=*/true);
+  evalNonNullParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
 }
 
-void CastValueChecker::evalDynCast(const CallExpr *CE, DefinedOrUnknownSVal DV,
+void CastValueChecker::evalDynCast(const CallEvent &Call,
+                                   DefinedOrUnknownSVal DV,
                                    CheckerContext &C) const {
-  evalNonNullParamNonNullReturn(CE, DV, C);
-  evalNonNullParamNullReturn(CE, DV, C);
+  evalNonNullParamNonNullReturn(Call, DV, C);
+  evalNonNullParamNullReturn(Call, DV, C);
 }
 
-void CastValueChecker::evalCastOrNull(const CallExpr *CE,
+void CastValueChecker::evalCastOrNull(const CallEvent &Call,
                                       DefinedOrUnknownSVal DV,
                                       CheckerContext &C) const {
-  evalNonNullParamNonNullReturn(CE, DV, C);
-  evalNullParamNullReturn(CE, DV, C);
+  evalNonNullParamNonNullReturn(Call, DV, C);
+  evalNullParamNullReturn(Call, DV, C);
 }
 
-void CastValueChecker::evalDynCastOrNull(const CallExpr *CE,
+void CastValueChecker::evalDynCastOrNull(const CallEvent &Call,
                                          DefinedOrUnknownSVal DV,
                                          CheckerContext &C) const {
-  evalNonNullParamNonNullReturn(CE, DV, C);
-  evalNonNullParamNullReturn(CE, DV, C);
-  evalNullParamNullReturn(CE, DV, C);
+  evalNonNullParamNonNullReturn(Call, DV, C);
+  evalNonNullParamNullReturn(Call, DV, C);
+  evalNullParamNullReturn(Call, DV, C);
 }
 
 //===----------------------------------------------------------------------===//
 // Evaluating castAs, getAs.
 //===----------------------------------------------------------------------===//
 
-static void evalZeroParamNonNullReturn(const CallExpr *CE,
+static void evalZeroParamNonNullReturn(const CallEvent &Call,
                                        DefinedOrUnknownSVal DV,
                                        CheckerContext &C,
                                        bool IsCheckedCast = false) {
-  bool IsNullReturn = false;
-  if (ProgramStateRef State = C.getState()->assume(DV, true))
-    C.addTransition(getState(IsNullReturn, DV, CE, C.getState(), C),
-                    getCastTag(IsNullReturn, CE, C, IsCheckedCast));
+  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
+                    /*IsNonNullReturn=*/true, IsCheckedCast);
 }
 
-static void evalZeroParamNullReturn(const CallExpr *CE, DefinedOrUnknownSVal DV,
+static void evalZeroParamNullReturn(const CallEvent &Call,
+                                    DefinedOrUnknownSVal DV,
                                     CheckerContext &C) {
-  bool IsNullReturn = true;
-  if (ProgramStateRef State = C.getState()->assume(DV, true))
-    C.addTransition(getState(IsNullReturn, DV, CE, C.getState(), C),
-                    getCastTag(IsNullReturn, CE, C));
+  addCastTransition(Call, DV, C, /*IsNonNullParam=*/true,
+                    /*IsNonNullReturn=*/false);
 }
 
-void CastValueChecker::evalCastAs(const CallExpr *CE, DefinedOrUnknownSVal DV,
+void CastValueChecker::evalCastAs(const CallEvent &Call,
+                                  DefinedOrUnknownSVal DV,
                                   CheckerContext &C) const {
-  evalZeroParamNonNullReturn(CE, DV, C, /*IsCheckedCast=*/true);
+  evalZeroParamNonNullReturn(Call, DV, C, /*IsCheckedCast=*/true);
 }
 
-void CastValueChecker::evalGetAs(const CallExpr *CE, DefinedOrUnknownSVal DV,
+void CastValueChecker::evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
                                  CheckerContext &C) const {
-  evalZeroParamNonNullReturn(CE, DV, C);
-  evalZeroParamNullReturn(CE, DV, C);
+  evalZeroParamNonNullReturn(Call, DV, C);
+  evalZeroParamNullReturn(Call, DV, C);
 }
 
+//===----------------------------------------------------------------------===//
+// Main logic to evaluate a call.
+//===----------------------------------------------------------------------===//
+
 bool CastValueChecker::evalCall(const CallEvent &Call,
                                 CheckerContext &C) const {
   const auto *Lookup = CDM.lookup(Call);
   if (!Lookup)
     return false;
 
-  // If we cannot obtain the call's class we cannot be sure how to model it.
-  QualType ResultTy = Call.getResultType();
-  if (!ResultTy->getPointeeCXXRecordDecl())
+  // We need to obtain the record type of the call's result to model it.
+  if (!getRecordType(Call.getResultType())->isRecordType())
     return false;
 
   const CastCheck &Check = Lookup->first;
-  CastKind Kind = Lookup->second;
-
-  const auto *CE = cast<CallExpr>(Call.getOriginExpr());
+  CallKind Kind = Lookup->second;
   Optional<DefinedOrUnknownSVal> DV;
 
   switch (Kind) {
-  case CastKind::Function: {
-    // If we cannot obtain the arg's class we cannot be sure how to model it.
-    QualType ArgTy = Call.parameters()[0]->getType();
-    if (!ArgTy->getAsCXXRecordDecl() && !ArgTy->getPointeeCXXRecordDecl())
+  case CallKind::Function: {
+    // We need to obtain the record type of the call's parameter to model it.
+    if (!getRecordType(Call.parameters()[0]->getType())->isRecordType())
       return false;
 
     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
     break;
   }
-  case CastKind::Method:
-    // If we cannot obtain the 'InstanceCall' we cannot be sure how to model it.
+  case CallKind::Method:
     const auto *InstanceCall = dyn_cast<CXXInstanceCall>(&Call);
     if (!InstanceCall)
       return false;
@@ -247,10 +316,15 @@ bool CastValueChecker::evalCall(const CallEvent &Call,
   if (!DV)
     return false;
 
-  Check(this, CE, *DV, C);
+  Check(this, Call, *DV, C);
   return true;
 }
 
+void CastValueChecker::checkDeadSymbols(SymbolReaper &SR,
+                                        CheckerContext &C) const {
+  C.addTransition(removeDeadCasts(C.getState(), SR));
+}
+
 void ento::registerCastValueChecker(CheckerManager &Mgr) {
   Mgr.registerChecker<CastValueChecker>();
 }
diff --git a/clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp b/clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp
index f5a968bde37..f2d1d018914 100644
--- a/clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp
+++ b/clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp
@@ -20,16 +20,16 @@
 //
 //===----------------------------------------------------------------------===//
 
-#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/AST/ParentMap.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/Builtins.h"
+#include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
 #include "clang/StaticAnalyzer/Core/Checker.h"
 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 
 using namespace clang;
@@ -113,14 +113,7 @@ public:
 
 void DynamicTypePropagation::checkDeadSymbols(SymbolReaper &SR,
                                               CheckerContext &C) const {
-  ProgramStateRef State = C.getState();
-  DynamicTypeMapTy TypeMap = State->get<DynamicTypeMap>();
-  for (DynamicTypeMapTy::iterator I = TypeMap.begin(), E = TypeMap.end();
-       I != E; ++I) {
-    if (!SR.isLiveRegion(I->first)) {
-      State = State->remove<DynamicTypeMap>(I->first);
-    }
-  }
+  ProgramStateRef State = removeDeadTypes(C.getState(), SR);
 
   MostSpecializedTypeArgsMapTy TyArgMap =
       State->get<MostSpecializedTypeArgsMap>();
@@ -882,7 +875,7 @@ void DynamicTypePropagation::checkPostObjCMessage(const ObjCMethodCall &M,
   // When there is an entry available for the return symbol in DynamicTypeMap,
   // the call was inlined, and the information in the DynamicTypeMap is should
   // be precise.
-  if (RetRegion && !State->get<DynamicTypeMap>(RetRegion)) {
+  if (RetRegion && !getRawDynamicTypeInfo(State, RetRegion)) {
     // TODO: we have duplicated information in DynamicTypeMap and
     // MostSpecializedTypeArgsMap. We should only store anything in the later if
     // the stored data differs from the one stored in the former.
diff --git a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
index 0affa8be557..05bc94c7c98 100644
--- a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
+++ b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt
@@ -16,7 +16,7 @@ add_clang_library(clangStaticAnalyzerCore
   CommonBugCategories.cpp
   ConstraintManager.cpp
   CoreEngine.cpp
-  DynamicTypeMap.cpp
+  DynamicType.cpp
   Environment.cpp
   ExplodedGraph.cpp
   ExprEngine.cpp
diff --git a/clang/lib/StaticAnalyzer/Core/DynamicType.cpp b/clang/lib/StaticAnalyzer/Core/DynamicType.cpp
new file mode 100644
index 00000000000..a9e281ec9e5
--- /dev/null
+++ b/clang/lib/StaticAnalyzer/Core/DynamicType.cpp
@@ -0,0 +1,223 @@
+//===- DynamicType.cpp - Dynamic type related APIs --------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines APIs that track and query dynamic type information. This
+//  information can be used to devirtualize calls during the symbolic execution
+//  or do type checking.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
+#include "clang/Basic/JsonSupport.h"
+#include "clang/Basic/LLVM.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
+#include "llvm/Support/Casting.h"
+#include "llvm/Support/raw_ostream.h"
+#include <cassert>
+
+/// The GDM component containing the dynamic type info. This is a map from a
+/// symbol to its most likely type.
+REGISTER_MAP_WITH_PROGRAMSTATE(DynamicTypeMap, const clang::ento::MemRegion *,
+                               clang::ento::DynamicTypeInfo)
+
+/// A set factory of dynamic cast informations.
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicCastInfo)
+
+/// A map from symbols to cast informations.
+REGISTER_MAP_WITH_PROGRAMSTATE(DynamicCastMap, const clang::ento::MemRegion *,
+                               CastSet)
+
+namespace clang {
+namespace ento {
+
+DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR) {
+  MR = MR->StripCasts();
+
+  // Look up the dynamic type in the GDM.
+  if (const DynamicTypeInfo *DTI = State->get<DynamicTypeMap>(MR))
+    return *DTI;
+
+  // Otherwise, fall back to what we know about the region.
+  if (const auto *TR = dyn_cast<TypedRegion>(MR))
+    return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false);
+
+  if (const auto *SR = dyn_cast<SymbolicRegion>(MR)) {
+    SymbolRef Sym = SR->getSymbol();
+    return DynamicTypeInfo(Sym->getType());
+  }
+
+  return {};
+}
+
+const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State,
+                                             const MemRegion *MR) {
+  return State->get<DynamicTypeMap>(MR);
+}
+
+const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State,
+                                          const MemRegion *MR,
+                                          QualType CastFromTy,
+                                          QualType CastToTy) {
+  const auto *Lookup = State->get<DynamicCastMap>().lookup(MR);
+  if (!Lookup)
+    return nullptr;
+
+  for (const DynamicCastInfo &Cast : *Lookup)
+    if (Cast.equals(CastFromTy, CastToTy))
+      return &Cast;
+
+  return nullptr;
+}
+
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
+                                   DynamicTypeInfo NewTy) {
+  State = State->set<DynamicTypeMap>(MR->StripCasts(), NewTy);
+  assert(State);
+  return State;
+}
+
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
+                                   QualType NewTy, bool CanBeSubClassed) {
+  return setDynamicTypeInfo(State, MR, DynamicTypeInfo(NewTy, CanBeSubClassed));
+}
+
+ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State,
+                                          const MemRegion *MR,
+                                          QualType CastFromTy,
+                                          QualType CastToTy, QualType ResultTy,
+                                          bool CastSucceeds) {
+  if (CastSucceeds)
+    State = State->set<DynamicTypeMap>(MR, ResultTy);
+
+  DynamicCastInfo::CastResult ResultKind =
+      CastSucceeds ? DynamicCastInfo::CastResult::Success
+                   : DynamicCastInfo::CastResult::Failure;
+
+  CastSet::Factory &F = State->get_context<CastSet>();
+
+  const CastSet *TempSet = State->get<DynamicCastMap>(MR);
+  CastSet Set = TempSet ? *TempSet : F.getEmptySet();
+
+  Set = F.add(Set, {CastFromTy, CastToTy, ResultKind});
+  State = State->set<DynamicCastMap>(MR, Set);
+
+  assert(State);
+  return State;
+}
+
+template <typename MapTy>
+ProgramStateRef removeDead(ProgramStateRef State, const MapTy &Map,
+                           SymbolReaper &SR) {
+  for (const auto &Elem : Map)
+    if (!SR.isLiveRegion(Elem.first))
+      State = State->remove<DynamicCastMap>(Elem.first);
+
+  return State;
+}
+
+ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR) {
+  return removeDead(State, State->get<DynamicTypeMap>(), SR);
+}
+
+ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR) {
+  return removeDead(State, State->get<DynamicCastMap>(), SR);
+}
+
+static void printDynamicTypesJson(raw_ostream &Out, ProgramStateRef State,
+                                  const char *NL, unsigned int Space,
+                                  bool IsDot) {
+  Indent(Out, Space, IsDot) << "\"dynamic_types\": ";
+
+  const DynamicTypeMapTy &Map = State->get<DynamicTypeMap>();
+  if (Map.isEmpty()) {
+    Out << "null," << NL;
+    return;
+  }
+
+  ++Space;
+  Out << '[' << NL;
+  for (DynamicTypeMapTy::iterator I = Map.begin(); I != Map.end(); ++I) {
+    const MemRegion *MR = I->first;
+    const DynamicTypeInfo &DTI = I->second;
+    Indent(Out, Space, IsDot)
+        << "{ \"region\": \"" << MR << "\", \"dyn_type\": ";
+    if (!DTI.isValid()) {
+      Out << "null";
+    } else {
+      Out << '\"' << DTI.getType()->getPointeeType().getAsString()
+          << "\", \"sub_classable\": "
+          << (DTI.canBeASubClass() ? "true" : "false");
+    }
+    Out << " }";
+
+    if (std::next(I) != Map.end())
+      Out << ',';
+    Out << NL;
+  }
+
+  --Space;
+  Indent(Out, Space, IsDot) << "]," << NL;
+}
+
+static void printDynamicCastsJson(raw_ostream &Out, ProgramStateRef State,
+                                  const char *NL, unsigned int Space,
+                                  bool IsDot) {
+  Indent(Out, Space, IsDot) << "\"dynamic_casts\": ";
+
+  const DynamicCastMapTy &Map = State->get<DynamicCastMap>();
+  if (Map.isEmpty()) {
+    Out << "null," << NL;
+    return;
+  }
+
+  ++Space;
+  Out << '[' << NL;
+  for (DynamicCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) {
+    const MemRegion *MR = I->first;
+    const CastSet &Set = I->second;
+
+    Indent(Out, Space, IsDot) << "{ \"region\": \"" << MR << "\", \"casts\": ";
+    if (Set.isEmpty()) {
+      Out << "null ";
+    } else {
+      ++Space;
+      Out << '[' << NL;
+      for (CastSet::iterator SI = Set.begin(); SI != Set.end(); ++SI) {
+        Indent(Out, Space, IsDot)
+            << "{ \"from\": \"" << SI->from().getAsString() << "\", \"to\": \""
+            << SI->to().getAsString() << "\", \"kind\": \""
+            << (SI->succeeds() ? "success" : "fail") << "\" }";
+
+        if (std::next(SI) != Set.end())
+          Out << ',';
+        Out << NL;
+      }
+      --Space;
+      Indent(Out, Space, IsDot) << ']';
+    }
+    Out << '}';
+
+    if (std::next(I) != Map.end())
+      Out << ',';
+    Out << NL;
+  }
+
+  --Space;
+  Indent(Out, Space, IsDot) << "]," << NL;
+}
+
+void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State,
+                              const char *NL, unsigned int Space, bool IsDot) {
+  printDynamicTypesJson(Out, State, NL, Space, IsDot);
+  printDynamicCastsJson(Out, State, NL, Space, IsDot);
+}
+
+} // namespace ento
+} // namespace clang
diff --git a/clang/lib/StaticAnalyzer/Core/DynamicTypeMap.cpp b/clang/lib/StaticAnalyzer/Core/DynamicTypeMap.cpp
deleted file mode 100644
index 79424452240..00000000000
--- a/clang/lib/StaticAnalyzer/Core/DynamicTypeMap.cpp
+++ /dev/null
@@ -1,97 +0,0 @@
-//===- DynamicTypeMap.cpp - Dynamic Type Info related APIs ----------------===//
-//
-// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
-// See https://llvm.org/LICENSE.txt for license information.
-// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
-//
-//===----------------------------------------------------------------------===//
-//
-//  This file defines APIs that track and query dynamic type information. This
-//  information can be used to devirtualize calls during the symbolic execution
-//  or do type checking.
-//
-//===----------------------------------------------------------------------===//
-
-#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
-#include "clang/Basic/JsonSupport.h"
-#include "clang/Basic/LLVM.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h"
-#include "llvm/Support/Casting.h"
-#include "llvm/Support/raw_ostream.h"
-#include <cassert>
-
-namespace clang {
-namespace ento {
-
-DynamicTypeInfo getDynamicTypeInfo(ProgramStateRef State,
-                                   const MemRegion *Reg) {
-  Reg = Reg->StripCasts();
-
-  // Look up the dynamic type in the GDM.
-  const DynamicTypeInfo *GDMType = State->get<DynamicTypeMap>(Reg);
-  if (GDMType)
-    return *GDMType;
-
-  // Otherwise, fall back to what we know about the region.
-  if (const auto *TR = dyn_cast<TypedRegion>(Reg))
-    return DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false);
-
-  if (const auto *SR = dyn_cast<SymbolicRegion>(Reg)) {
-    SymbolRef Sym = SR->getSymbol();
-    return DynamicTypeInfo(Sym->getType());
-  }
-
-  return {};
-}
-
-ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *Reg,
-                                   DynamicTypeInfo NewTy) {
-  Reg = Reg->StripCasts();
-  ProgramStateRef NewState = State->set<DynamicTypeMap>(Reg, NewTy);
-  assert(NewState);
-  return NewState;
-}
-
-void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State,
-                              const char *NL, unsigned int Space, bool IsDot) {
-  Indent(Out, Space, IsDot) << "\"dynamic_types\": ";
-
-  const DynamicTypeMapTy &DTM = State->get<DynamicTypeMap>();
-  if (DTM.isEmpty()) {
-    Out << "null," << NL;
-    return;
-  }
-
-  ++Space;
-  Out << '[' << NL;
-  for (DynamicTypeMapTy::iterator I = DTM.begin(); I != DTM.end(); ++I) {
-    const MemRegion *MR = I->first;
-    const DynamicTypeInfo &DTI = I->second;
-    Out << "{ \"region\": \"" << MR << "\", \"dyn_type\": ";
-    if (DTI.isValid()) {
-      Out << '\"' << DTI.getType()->getPointeeType().getAsString()
-          << "\", \"sub_classable\": "
-          << (DTI.canBeASubClass() ? "true" : "false");
-    } else {
-      Out << "null"; // Invalid type info
-    }
-    Out << "}";
-
-    if (std::next(I) != DTM.end())
-      Out << ',';
-    Out << NL;
-  }
-
-  --Space;
-  Indent(Out, Space, IsDot) << "]," << NL;
-}
-
-void *ProgramStateTrait<DynamicTypeMap>::GDMIndex() {
-  static int index = 0;
-  return &index;
-}
-
-} // namespace ento
-} // namespace clang
diff --git a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
index a1ca0b1b84b..f50d82de3b2 100644
--- a/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
+++ b/clang/lib/StaticAnalyzer/Core/ProgramState.cpp
@@ -15,7 +15,7 @@
 #include "clang/Basic/JsonSupport.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeMap.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
 #include "llvm/Support/raw_ostream.h"