[analyzer] CastValueChecker: Model inheritance

[Charusso]

Summary

The key is CXXRecordDecl::isDerivedFrom().

[Charusso]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

215

That could be helpful, but I am not sure.

243–244

Previously possible false positives happened because we kept flow the modeling.

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

46

Probably a consistent way of MemRegion handling is more appropriate.

[NoQ]

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h

24

Ty(Ty) is the idiom here.

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

152

Counterexample:

struct A {};
struct B : A {};
struct C : A, B {};

Downcast from C to B should succeed, even though they have a common ancestor A (which has the same CXXRecordDecl but currently isn't the same object within C, but can be, if B declares A as a virtual base).

200

Omg lol nice. Did you try to figure out how do other people normally do it?

[NoQ]

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

46

Pointer casts are quite a can of worms. I suggest ignoring it for now and dealing with it as needed. I.e., your code looks good... for now.

[Szelethus]

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

46

*cries in pointer chasing*

[Charusso]

• Fix.

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h

24

Good to know, thanks!

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

152

So, even it is some kind of anti-pattern as a warning arrive immediately, now I allow B to C downcasts. Could you explain me more about that virtual idea, please? Based on this possible use-case in my mind two classes are on the same level as every of their bases/vbases are equals.

200

There is no function for that in ADT/StringExtras.h + grep did not help, so I realized it is a common way to match vowels. Do you know a better solution?

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

153

Using a flag here is unnecessary because you're returning true without doing anything else whenever the flag is set.

So, basically, your code says "if at least one current base is different from at least one previous base, the cast succeeds".

In particular, this function would return true whenever CurrentRD and PreviousRD are from completely unrelated class hierarchies. It sounds like whatever isSucceededDowncast() was supposed to do, it's not doing it right.

200

I just realized that this is actually incorrect and the correct solution is pretty hard to implement because the actual "a vs. an" rule deals with sounds, not letters. Eg.:

Clang is an "LLVM native" C/C++/Objective-C compiler

has an "an" because it's read as "an el-el-vee-am".

[NoQ]

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

152

Could you explain me more about that virtual idea, please?

In the following variation:

struct A {};
struct B : virtual A {};
struct C : A, B {};

we have C contain only one instance of A: the layout of B within C would merely refer to the instance of A within C instead of making its own copy. In particular, the constructor of B within the constructor of C would not initialize C's instance of A because the constructor of C will invoke the constructor of A directly (cf. D61816).

[Charusso]

• Try to do the math.
• Create a consistent dynamic type API.

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

152

That is a cool example, thanks you!

200

That is a cool idea, I will adjust StringExtras.h after that patch, for now please let us use that simple heuristic.

[Szelethus]

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

48

Hmm, I think this function answers the question, at least in the standard library sense, whether Y std::is_base_of of X, whereas "is derived from?" is another term that is used by clang and seems to not allow equality of types. Should we rename this to isBaseOf?

[Charusso]

• When we have no information whether the cast succeeds or not we assume both.
• CastVisitor is the new facility which decides whether the assumptions are appropriate.
• Removed the vowels-related string-formatting.
• Moved the API changes to D68199.
• The math is still WIP.

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

48

I have left the equality by a mistake. It is wanted to be a wrapper of isDerivedFrom(), which does not allow equality. Thanks for the notice!

[NoQ]

In D67079#1687577, @Charusso wrote:

• CastVisitor is the new facility which decides whether the assumptions are appropriate.
• The math is still WIP.

You need the math to decide whether delaying the decision to a visitor is the right approach.

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

Why is (isa<B>(a) && isa<C>(a)) deemed possible in the first test but not in the second test? o_o

[Charusso]

In D67079#1688648, @NoQ wrote:

In D67079#1687577, @Charusso wrote:

• CastVisitor is the new facility which decides whether the assumptions are appropriate.
• The math is still WIP.

You need the math to decide whether delaying the decision to a visitor is the right approach.

Yes, Soon(tm).

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

In test_downcast() we assume that a is a record type of D where D is a B and D is a C. However in test_downcast_infeasible() if a is not a record type of D is cannot be both B and C at the same time. That is the purpose of CastVisitor.

[NoQ]

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

I mean, it contradicts to how the program *actually* works, so we should either not do that, or provide a reeeeeaaaaaallly compelling explanation of why we do this (as in "Extraordinary Claims Require Extraordinary Evidence").

[Charusso]

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

Are you sure it does not model the program? I have an Apple class and I have a Pen class, until it is not defining an ApplePen class it is a false assumption to say they are defining an ApplePen class. I wanted to prefetch that information before the modeling starts, but it was an impossible challenge for me, so I have picked that CastVisitor-based post-elimination idea. In the real world I have removed only two false assumptions with the visitor from 1200 reports of LLVM so an ApplePen is very rare (https://www.youtube.com/watch?v=Ct6BUPvE2sM).

[NoQ]

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

I'm sure that the possibility of taking a true branch in if (x) only depends on the value of x, not on the contents of the branch.

[NoQ]

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

I.e., i see the point that you're trying to make (roughly), but it still requires extraordinary evindence and the way you've written the test clearly demonstrates why it needs an extraordinary evidence.

What you were trying to say is "imagine there's no class D, then we probably shouldn't consider the situation that it exists". But in this test the class exists, and you've just written a test about it, and then you're telling me that it doesn't exist. Which is exactly the problem with not considering that D exists. And this is exactly why choosing such approach requires a discussion.

One reason why i doubt the visitor-based solution is that the existence of D is not a path-sensitive fact; it either exists or not, it is irrelevant whether it was mentioned in the current path. Therefore scanning all classes in the translation unit, as opposed to classes mentioned on the current path, seems more precise.

[Charusso]

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

25–27

Well, that is a better idea, yes. I really like your observation about if (x), thanks for them! During the Summer I have learnt a lot, but a lot about the issue of the one translation unit, so that is why I was very afraid of using it. Let us give it a try.

[Charusso]

• Use the TU's Decls instead of the gathered casts' Decls.
• The math is still missing.

[Charusso]

• Rebase.

[Charusso]

• Rebase properly.

[Charusso]

Well, the rebase is a little-bit weird, sorry for the inconvenience.

clang/include/clang/StaticAnalyzer/Core/BugReporter/BugReporterVisitors.h

 #define LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H
 
 #include "clang/Analysis/ProgramPoint.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/StringRef.h"
 #include <memory>
 
 namespace clang {
 
 class BinaryOperator;
 class CFGBlock;
 class DeclRefExpr;
PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
                                    PathSensitiveBugReport &BR) override;
 
   void finalizeVisitor(BugReporterContext &BRC, const ExplodedNode *EndPathNode,
                        PathSensitiveBugReport &BR) override;
 };
 
 
 /// The visitor detects NoteTags and displays the event notes they contain.
-class TagVisitor : public BugReporterVisitor {
+class TagVisitor final : public BugReporterVisitor {
 public:
   void Profile(llvm::FoldingSetNodeID &ID) const override;
 
   PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
                                    BugReporterContext &BRC,
                                    PathSensitiveBugReport &R) override;
 };
 
+/// It detects evaluated casts and suppresses false assumption based reports.
+class CastVisitor final : public BugReporterVisitor {
+  using RegionSetTy = llvm::SmallSet<const MemRegion *, 32>;
+  RegionSetTy RegionSet;
+
+public:
+  static void *getTag();
+
+  PathDiagnosticPieceRef VisitNode(const ExplodedNode *N,
+                                   BugReporterContext &BRC,
+                                   PathSensitiveBugReport &R) override;
+
+  void finalizeVisitor(BugReporterContext &BRC, const ExplodedNode *N,
+                       PathSensitiveBugReport &BR) override;
+
+  void Profile(llvm::FoldingSetNodeID &ID) const override;
+};
+
 } // namespace ento
 
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_BUGREPORTER_BUGREPORTERVISITORS_H

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicCastInfo.h

-//===- DynamicCastInfo.h - Runtime cast information -------------*- 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
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H
-#define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H
-
-#include "clang/AST/Type.h"
-
-namespace clang {
-namespace ento {
-
-class DynamicCastInfo {
-public:
-  enum CastResult { Success, Failure };
-
-  DynamicCastInfo(QualType from, QualType to, CastResult resultKind)
-      : From(from), To(to), ResultKind(resultKind) {}
-
-  QualType from() const { return From; }
-  QualType to() const { return To; }
-
-  bool equals(QualType from, QualType to) const {
-    return From == from && To == to;
-  }
-
-  bool succeeds() const { return ResultKind == CastResult::Success; }
-  bool fails() const { return ResultKind == CastResult::Failure; }
-
-  bool operator==(const DynamicCastInfo &RHS) const {
-    return From == RHS.From && To == RHS.To;
-  }
-  bool operator<(const DynamicCastInfo &RHS) const {
-    return From < RHS.From && To < RHS.To;
-  }
-
-  void Profile(llvm::FoldingSetNodeID &ID) const {
-    ID.Add(From);
-    ID.Add(To);
-    ID.AddInteger(ResultKind);
-  }
-
-private:
-  QualType From, To;
-  CastResult ResultKind;
-};
-
-} // namespace ento
-} // namespace clang
-
-#endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICCASTINFO_H

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h

 //  or do type checking.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPE_H
 #define LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPE_H
 
 #include "clang/AST/Type.h"
-#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicCastInfo.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/ADT/Optional.h"
 #include <utility>
 
 namespace clang {
 namespace ento {
 
+/// \returns Whether the record of type \p X is derived from the record of type
+/// \p Y.
+bool isDerivedFrom(QualType X, QualType Y);
+
+/// \returns Whether the record of type \p X is equal to the record of type \p
+/// Y or one record is derived from the other record.
+bool isOneEqualOrDerivedFromOther(QualType X, QualType Y);
+
+/// \returns Whether an infeasible cast found.
+bool isInfeasibleCastFound(ProgramStateRef State, const MemRegion *MR);
+
 /// Get dynamic type information for the region \p MR.
 const DynamicTypeInfo *getDynamicTypeInfo(ProgramStateRef State,
                                           const MemRegion *MR);
 
-/// Get raw dynamic type information for the region \p MR.
-const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State,
+/// Get the stored dynamic type information for the region \p MR.
+const DynamicTypeInfo *getStoredDynamicTypeInfo(ProgramStateRef State,
                                                 const MemRegion *MR);
 
-/// Get dynamic cast information from \p CastFromTy to \p CastToTy of \p MR.
-const DynamicCastInfo *getDynamicCastInfo(ProgramStateRef State,
-                                          const MemRegion *MR,
-                                          QualType CastFromTy,
-                                          QualType CastToTy);
+/// Get dynamic type information of the failed cast for the region \p MR.
+/// The cast failed whether the current casting to \p CastToTy has a record type
+/// which derives from a previously stored cast's record type.
+const DynamicTypeInfo *getFailedCastInfo(ProgramStateRef State,
 
 /// Set dynamic type information of the region; return the new state.
 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
                                    const DynamicTypeInfo *NewTy);
 
 /// Set dynamic type information of the region; return the new state.
 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
                                    QualType NewTy, bool CanBeSubClassed = true);
 
 /// Set dynamic type and cast information of the region; return the new state.
-ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State,
-                                          const MemRegion *MR,
-                                          QualType CastFromTy,
-                                          QualType CastToTy,
-                                          bool IsCastSucceeds);
+/// It stores the largest set what is the record of the given type \p CastToTy
+/// cannot be, and what is the most-derived class which the record could be.
+/// It also stores the succeeded casts.
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
+                                   QualType CastToTy, bool CastSucceeds,
+                                   const DynamicTypeInfo *CastInfo);
 
 /// Removes the dead type informations from \p State.
 ProgramStateRef removeDeadTypes(ProgramStateRef State, SymbolReaper &SR);
 
 /// Removes the dead cast informations from \p State.
 ProgramStateRef removeDeadCasts(ProgramStateRef State, SymbolReaper &SR);
 
 void printDynamicTypeInfoJson(raw_ostream &Out, ProgramStateRef State,
                               const char *NL = "\n", unsigned int Space = 0,
                               bool IsDot = false);
 
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPE_H

clang/include/clang/StaticAnalyzer/Core/PathSensitive/DynamicTypeInfo.h

 
 /// Stores the currently inferred strictest bound on the runtime type
 /// of a region in a given state along the analysis path.
 class DynamicTypeInfo {
 public:
   DynamicTypeInfo() : Ty(QualType()) {}
 
   DynamicTypeInfo(QualType Ty, bool CanBeASubClass = true)
       : Ty(Ty), CanBeASubClass(CanBeASubClass) {}
 
   /// Returns false if the type information is precise (the type 'DynTy' is
   /// the only type in the lattice), true otherwise.
   bool canBeASubClass() const { return CanBeASubClass; }
 
   /// Returns the currently inferred upper bound on the runtime type.
   QualType getType() const { return Ty; }
 
   bool operator==(const DynamicTypeInfo &RHS) const {
     return Ty == RHS.Ty && CanBeASubClass == RHS.CanBeASubClass;
   }
+  bool operator<(const DynamicTypeInfo &RHS) const { return Ty < RHS.Ty; }
 
   void Profile(llvm::FoldingSetNodeID &ID) const {
     ID.Add(Ty);
     ID.AddBoolean(CanBeASubClass);
   }
 
 private:
   QualType Ty;
   bool CanBeASubClass;
 };
 
 } // namespace ento
 } // namespace clang
 
 #endif // LLVM_CLANG_STATICANALYZER_CORE_PATHSENSITIVE_DYNAMICTYPEINFO_H

clang/lib/StaticAnalyzer/Checkers/CastValueChecker.cpp

 //===- CastValueChecker - Model implementation of custom RTTIs --*- 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 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.
-//
 //===----------------------------------------------------------------------===//
 
 #include "clang/AST/DeclTemplate.h"
 #include "clang/StaticAnalyzer/Checkers/BuiltinCheckerRegistration.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/CheckerContext.h"
void evalGetAs(const CallEvent &Call, DefinedOrUnknownSVal DV,
                  CheckerContext &C) const;
   void evalIsa(const CallEvent &Call, DefinedOrUnknownSVal DV,
                CheckerContext &C) const;
   void evalIsaAndNonNull(const CallEvent &Call, DefinedOrUnknownSVal DV,
                          CheckerContext &C) const;
 };
 } // namespace
 
-static bool isInfeasibleCast(const DynamicCastInfo *CastInfo,
-                             bool CastSucceeds) {
-  if (!CastInfo)
+// Dynamic type: Denote 'r' the 'MemoryRegion' which we try to cast. We store
+//   the most derived record type information in the 'DynamicTypeMap' for the
+//   given 'r'. We store the record types which the given 'r' cannot be casted
+//   to in 'FailedCastMap'. Every 'MemoryRegion' is typeless from the checker's
+//   point of view, because it waits for a cast expression to denote the object
+//   with an appropriate type.
+//   Denote 'S(r)' a 'MemoryRegion' 'r' entry in 'DynamicTypeMap', and
+//   denote 'F(r)' a 'MemoryRegion' 'r' entry in 'FailedCastMap'.
+//
+// Record: For the given 'MemoryRegion' 'r' we obtain the records from the AST
+//   using the cast expression's and the object's static types and also the
+//   dynamically known types using 'S(r)' and 'F(r)'.
+//
+// Inheritance: for two given records 'X' and 'Y' let us call 'X' inherits from
+//   'Y' if there exists at least one directed path from 'X' to 'Y'.
+//   Denote it by 'X -> Y'.
+//
+// Related records: for two given records 'X' and 'Y' let us call them related
+//   if either X = Y, or 'X' inherits from 'Y', or 'Y' inherits from 'X'.
+//   Denote it by 'X <-> Y'. ('X <-> Y' <=> 'X -> Y' ∧ 'X <- Y'.)
+//
+// Cast: for two given related records 'X' and 'Y' (X <-> Y) we define two
+//   types of casts: the downcast: 'X -> Y', and the upcast: 'X <- Y'.
+//
+// Succeeded-cast path: For the given static type of a given MemoryRegion 'r'
+//   we try to chain the succeeded casts to form a directed path from the
+//   static type to the most derived record type information in 'S(r)'.
+//
+// An 'X -> Y' downcast/upcast succeeds for an 'r' 'MemoryRegion' iff
+// - 'X <-> Y' and,
+// - 'Y' ∉ 'F(r)' and:
+//   - If ∄S(r): it succeeds as a first entry.
+//   - If ∃S(r):
+//     - If ∃'S(r) <-> Y': it succeeds as the succeeded-cast path continues.
+//     - If ∄'S(r) <-> Y': we could assume that it succeeds as 'Y' could create
+//                         a succeeded-cast path later during the execution.
+//
+// Here the known static types are \p CastFromTy and \p CastToTy. The 'S(r)'
+// entry is \p SucceededCastInfo and the 'F(r)' entry is \p FailedCastInfo.
+static Optional<bool> isSuccededCast(const DynamicTypeInfo *SucceededCastInfo,
+                                     const DynamicTypeInfo *FailedCastInfo,
+                                     QualType CastFromTy, QualType CastToTy) {
+  if (FailedCastInfo || !isOneEqualOrDerivedFromOther(CastFromTy, CastToTy))
     return false;
 
-  return CastSucceeds ? CastInfo->fails() : CastInfo->succeeds();
+  if (!SucceededCastInfo)
+    return true;
+
+  if (isOneEqualOrDerivedFromOther(SucceededCastInfo->getType(), CastToTy))
+    return true;
+
+  return None;
+}
+
+namespace {
+struct CastContext {
+  CastContext(ProgramStateRef State, const MemRegion *MR, QualType CastFromTy,
+              QualType CastToTy, bool Assumption, bool IsCheckedCast) {
+    const DynamicTypeInfo *SucceededCastInfo =
+        getStoredDynamicTypeInfo(State, MR);
+
+    const DynamicTypeInfo *FailedCastInfo =
+        getFailedCastInfo(State, MR, CastToTy);
+
+    // We assume that every checked cast (cast<>) succeeds.
+    bool IsAlwaysSucceeds =
+        IsCheckedCast || CastFromTy->getPointeeCXXRecordDecl() ==
+                             CastToTy->getPointeeCXXRecordDecl();
+
+    if (IsAlwaysSucceeds) {
+      CastSucceeds = true;
+      IsKnownCast = true;
+    } else if (Optional<bool> TempCastSucceeds = isSuccededCast(
+                   SucceededCastInfo, FailedCastInfo, CastFromTy, CastToTy)) {
+      CastSucceeds = Assumption && *TempCastSucceeds;
+      IsKnownCast = (CastSucceeds && SucceededCastInfo &&
+                     isDerivedFrom(SucceededCastInfo->getType(), CastToTy)) ||
+                    (!CastSucceeds && FailedCastInfo &&
+                     isDerivedFrom(FailedCastInfo->getType(), CastToTy));
+    } else {
+      CastSucceeds = Assumption;
+      IsKnownCast = false;
+    }
+
+    CastInfo = CastSucceeds ? SucceededCastInfo : FailedCastInfo;
   }
 
-static const NoteTag *getNoteTag(CheckerContext &C,
-                                 const DynamicCastInfo *CastInfo,
-                                 QualType CastToTy, const Expr *Object,
-                                 bool CastSucceeds, bool IsKnownCast) {
+  bool CastSucceeds, IsKnownCast;
+  const DynamicTypeInfo *CastInfo;
+};
+} // namespace
+
+static const NoteTag *getNoteTag(CheckerContext &C, const Expr *Object,
+                                 QualType CastToTy, CastContext &CastCtx) {
+  QualType KnownCastToTy;
+  if (CastCtx.CastInfo && CastCtx.IsKnownCast)
+    KnownCastToTy = CastCtx.CastInfo->getType();
+
   std::string CastToName =
-      CastInfo ? CastInfo->to()->getPointeeCXXRecordDecl()->getNameAsString()
-               : CastToTy->getPointeeCXXRecordDecl()->getNameAsString();
+      CastCtx.CastInfo && CastCtx.IsKnownCast
+          ? KnownCastToTy->getPointeeCXXRecordDecl()->getNameAsString()
   Object = Object->IgnoreParenImpCasts();
 
   return C.getNoteTag(
       [=]() -> std::string {
         SmallString<128> Msg;
         llvm::raw_svector_ostream Out(Msg);
 
-        if (!IsKnownCast)
+        if (!CastCtx.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 '")
+          Out << (CastCtx.IsKnownCast ? "Field '" : "field '")
               << ME->getMemberDecl()->getNameAsString() << '\'';
         } else {
-          Out << (IsKnownCast ? "The object" : "the object");
+          Out << (CastCtx.IsKnownCast ? "The object" : "the object");
         }
 
-        Out << ' ' << (CastSucceeds ? "is a" : "is not a") << " '" << CastToName
-            << '\'';
+        Out << ' ' << (CastCtx.CastSucceeds ? "is" : "is not") << " a '"
+            << CastToName << '\'';
 
         return Out.str();
       },
-      /*IsPrunable=*/true);
+      /*IsPrunable=*/!CastCtx.CastSucceeds);
 }
 
 //===----------------------------------------------------------------------===//
 // Main logic to evaluate a cast.
 //===----------------------------------------------------------------------===//
 
 static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
                                     ASTContext &ACtx) {
static QualType alignReferenceTypes(QualType toAlign, QualType alignTowards,
   llvm_unreachable("Must align towards a reference type!");
 }
 
 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)
+  if (!State) {
+    C.generateSink(C.getState(), C.getPredecessor());
     return;
+  }
 
   const Expr *Object;
   QualType CastFromTy;
   QualType CastToTy = Call.getResultType();
 
   if (Call.getNumArgs() > 0) {
     Object = Call.getArgExpr(0);
     CastFromTy = Call.parameters()[0]->getType();
   } else {
     Object = cast<CXXInstanceCall>(&Call)->getCXXThisExpr();
     CastFromTy = Object->getType();
     if (CastToTy->isPointerType()) {
       if (!CastFromTy->isPointerType())
         return;
     } else {
       if (!CastFromTy->isReferenceType())
         return;
 
       CastFromTy = alignReferenceTypes(CastFromTy, CastToTy, C.getASTContext());
     }
   }
 
   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;
-  }
+  CastContext CastCtx(State, MR, CastFromTy, CastToTy,
+                      /*Assumption=*/IsNonNullReturn, IsCheckedCast);
 
-  // Store the type and the cast information.
-  bool IsKnownCast = CastInfo || IsCheckedCast || CastFromTy == CastToTy;
-  if (!IsKnownCast || IsCheckedCast)
-    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
-                                      CastSucceeds);
+  State = setDynamicTypeInfo(State, MR, CastToTy, CastCtx.CastSucceeds,
+                             CastCtx.CastInfo);
 
-  SVal V = CastSucceeds ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)
-                        : C.getSValBuilder().makeNull();
+  SVal V = CastCtx.CastSucceeds
+               ? C.getSValBuilder().evalCast(DV, CastToTy, CastFromTy)
+
   C.addTransition(
       State->BindExpr(Call.getOriginExpr(), C.getLocationContext(), V, false),
-      getNoteTag(C, CastInfo, CastToTy, Object, CastSucceeds, IsKnownCast));
+      getNoteTag(C, Object, CastToTy, CastCtx));
 }
 
 static void addInstanceOfTransition(const CallEvent &Call,
                                     DefinedOrUnknownSVal DV,
                                     ProgramStateRef State, CheckerContext &C,
                                     bool IsInstanceOf) {
   const FunctionDecl *FD = Call.getDecl()->getAsFunction();
-  QualType CastFromTy = Call.parameters()[0]->getType();
+  QualType CastFromTy = Call.parameters()[0]->getType().getCanonicalType();
   QualType CastToTy = FD->getTemplateSpecializationArgs()->get(0).getAsType();
+
   if (CastFromTy->isPointerType())
     CastToTy = C.getASTContext().getPointerType(CastToTy);
   else if (CastFromTy->isReferenceType())
     CastToTy = alignReferenceTypes(CastToTy, CastFromTy, C.getASTContext());
   else
     return;
 
   const MemRegion *MR = DV.getAsRegion();
-  const DynamicCastInfo *CastInfo =
-      getDynamicCastInfo(State, MR, CastFromTy, CastToTy);
-
-  bool CastSucceeds;
-  if (CastInfo)
-    CastSucceeds = IsInstanceOf && CastInfo->succeeds();
-  else
-    CastSucceeds = IsInstanceOf || CastFromTy == CastToTy;
-
-  if (isInfeasibleCast(CastInfo, CastSucceeds)) {
-    C.generateSink(State, C.getPredecessor());
-    return;
-  }
+  CastContext CastCtx(State, MR, CastFromTy, CastToTy,
+                      /*Assumption=*/IsInstanceOf, /*IsCheckedCast=*/false);
 
-  // Store the type and the cast information.
-  bool IsKnownCast = CastInfo || CastFromTy == CastToTy;
-  if (!IsKnownCast)
-    State = setDynamicTypeAndCastInfo(State, MR, CastFromTy, CastToTy,
-                                      IsInstanceOf);
+  State = setDynamicTypeInfo(State, MR, CastToTy, CastCtx.CastSucceeds,
+                             CastCtx.CastInfo);
 
   C.addTransition(
       State->BindExpr(Call.getOriginExpr(), C.getLocationContext(),
-                      C.getSValBuilder().makeTruthVal(CastSucceeds)),
-      getNoteTag(C, CastInfo, CastToTy, Call.getArgExpr(0), CastSucceeds,
-                 IsKnownCast));
+                      C.getSValBuilder().makeTruthVal(CastCtx.CastSucceeds)),
+      getNoteTag(C, Call.getArgExpr(0), CastToTy, CastCtx));
 }
 
 //===----------------------------------------------------------------------===//
 // Evaluating cast, dyn_cast, cast_or_null, dyn_cast_or_null.
 //===----------------------------------------------------------------------===//
 
 static void evalNonNullParamNonNullReturn(const CallEvent &Call,
                                           DefinedOrUnknownSVal DV,
bool CastValueChecker::evalCall(const CallEvent &Call,
 
   Optional<DefinedOrUnknownSVal> DV;
 
   switch (Kind) {
   case CallKind::Function: {
     // We only model casts from pointers to pointers or from references
     // to references. Other casts are most likely specialized and we
     // cannot model them.
-    QualType ParamT = Call.parameters()[0]->getType();
-    QualType ResultT = Call.getResultType();
-    if (!(ParamT->isPointerType() && ResultT->isPointerType()) &&
-        !(ParamT->isReferenceType() && ResultT->isReferenceType()))
+    QualType ParamTy = Call.parameters()[0]->getType();
+    QualType ResultTy = Call.getResultType();
+    if (!(ParamTy->isPointerType() && ResultTy->isPointerType()) &&
+        !(ParamTy->isReferenceType() && ResultTy->isReferenceType()))
       return false;
 
     DV = Call.getArgSVal(0).getAs<DefinedOrUnknownSVal>();
     break;
   }
   case CallKind::InstanceOf: {
     // We need to obtain the only template argument to determinte the type.
     const FunctionDecl *FD = Call.getDecl()->getAsFunction();

clang/lib/StaticAnalyzer/Checkers/DynamicTypePropagation.cpp

void DynamicTypePropagation::checkPostObjCMessage(const ObjCMethodCall &M,
   if (ResultType.isNull())
     return;
 
   const MemRegion *RetRegion = M.getReturnValue().getAsRegion();
   ExplodedNode *Pred = C.getPredecessor();
   // 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 && !getRawDynamicTypeInfo(State, RetRegion)) {
+  if (RetRegion && !getStoredDynamicTypeInfo(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.
     State = setDynamicTypeInfo(State, RetRegion, ResultType,
                                /*CanBeSubClassed=*/true);
     Pred = C.addTransition(State);
   }
 

clang/lib/StaticAnalyzer/Core/BugReporter.cpp

while (BugPathInfo *BugPath = BugGraph.getNextBugPath()) {
     // Register refutation visitors first, if they mark the bug invalid no
     // further analysis is required
     R->addVisitor(std::make_unique<LikelyFalsePositiveSuppressionBRVisitor>());
 
     // Register additional node visitors.
     R->addVisitor(std::make_unique<NilReceiverBRVisitor>());
     R->addVisitor(std::make_unique<ConditionBRVisitor>());
     R->addVisitor(std::make_unique<TagVisitor>());
+    R->addVisitor(std::make_unique<CastVisitor>());
 
     BugReporterContext BRC(Reporter);
 
     // Run all visitors on a given graph, once.
     std::unique_ptr<VisitorsDiagnosticsTy> visitorNotes =
         generateVisitorsDiagnostics(R, ErrorNode, BRC);
 
     if (R->isValid()) {

clang/lib/StaticAnalyzer/Core/BugReporterVisitors.cpp

 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/DynamicType.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState_Fwd.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SMTConv.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SValBuilder.h"
 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
PathDiagnosticLocation Loc =
         PathDiagnosticLocation::create(PP, BRC.getSourceManager());
     auto Piece = std::make_shared<PathDiagnosticEventPiece>(Loc, *Msg);
     Piece->setPrunable(T->isPrunable());
     return Piece;
   }
 
   return nullptr;
 }
+
+//===----------------------------------------------------------------------===//
+// Implementation of CastVisitor.
+//===----------------------------------------------------------------------===//
+
+void CastVisitor::Profile(llvm::FoldingSetNodeID &ID) const {
+  ID.AddPointer(getTag());
+}
+
+void *CastVisitor::getTag() {
+  static int Tag = 0;
+  return static_cast<void *>(&Tag);
+}
+
+PathDiagnosticPieceRef CastVisitor::VisitNode(const ExplodedNode *N,
+                                              BugReporterContext &BRC,
+                                              PathSensitiveBugReport &R) {
+  ProgramPoint PP = N->getLocation();
+  if (!dyn_cast_or_null<NoteTag>(PP.getTag()))
+    return nullptr;
+
+  auto PS = PP.getAs<PostStmt>();
+  if (!PS)
+    return nullptr;
+
+  ProgramStateRef State = N->getState();
+  const LocationContext *LCtx = N->getLocationContext();
+  CallEventRef<> Call = BRC.getStateManager().getCallEventManager().getCall(
+      PS->getStmt(), State, LCtx);
+  if (!Call)
+    return nullptr;
+
+  DefinedOrUnknownSVal DV = UnknownVal();
+  if (Call->getNumArgs() == 1) {
+    DV = Call->getArgSVal(0).castAs<DefinedOrUnknownSVal>();
+  } else if (const auto *InstanceCall = dyn_cast<CXXInstanceCall>(Call)) {
+    DV = InstanceCall->getCXXThisVal().castAs<DefinedOrUnknownSVal>();
+  } else {
+    return nullptr;
+  }
+
+  RegionSet.insert(DV.getAsRegion());
+  return nullptr;
+}
+
+void CastVisitor::finalizeVisitor(BugReporterContext &BRC,
+                                  const ExplodedNode *N,
+                                  PathSensitiveBugReport &BR) {
+  bool IsFalsePositive = false;
+  ProgramStateRef State = N->getState();
+
+  for (const MemRegion *MR : RegionSet) {
+    if ((IsFalsePositive = isInfeasibleCastFound(State, MR)))
+      break;
+  }
+
+  if (IsFalsePositive)
+    BR.markInvalid(getTag(), nullptr);
+}

clang/lib/StaticAnalyzer/Core/DynamicType.cpp

 #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 set factory of dynamic cast informations as type informations.
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(CastSet, clang::ento::DynamicTypeInfo)
 
-/// A map from symbols to cast informations.
-REGISTER_MAP_WITH_PROGRAMSTATE(DynamicCastMap, const clang::ento::MemRegion *,
+/// A map from symbols to succeeded cast informations.
+REGISTER_MAP_WITH_PROGRAMSTATE(SucceededCastMap, const clang::ento::MemRegion *,
+                               CastSet)
+
+/// A map from symbols to failed cast informations.
+REGISTER_MAP_WITH_PROGRAMSTATE(FailedCastMap, const clang::ento::MemRegion *,
                                CastSet)
 
 namespace clang {
 namespace ento {
 
 static const MemRegion *getSimplifiedRegion(const MemRegion *MR) {
   return MR->StripCasts();
 }
 
+bool isDerivedFrom(QualType X, QualType Y) {
+  const CXXRecordDecl *XRD = X->getPointeeCXXRecordDecl();
+  const CXXRecordDecl *YRD = Y->getPointeeCXXRecordDecl();
+
+  if (!XRD || !YRD)
+    return false;
+
+  return XRD->isDerivedFrom(YRD);
+}
+
+bool isOneEqualOrDerivedFromOther(QualType X, QualType Y) {
+  if (X->getPointeeCXXRecordDecl() == Y->getPointeeCXXRecordDecl())
+    return true;
+
+  return isDerivedFrom(X, Y) || isDerivedFrom(Y, X);
+}
+
+bool isInfeasibleCastFound(ProgramStateRef State, const MemRegion *MR) {
+  const CastSet *SucceededSet = State->get<SucceededCastMap>().lookup(MR);
+  if (!SucceededSet)
+    return false;
+
+  for (const DynamicTypeInfo &I : *SucceededSet) {
+    for (const DynamicTypeInfo &J : *SucceededSet) {
+      // Pick two disjunct records (there is no direct path between them).
+      if (!isOneEqualOrDerivedFromOther(I.getType(), J.getType())) {
+        for (const DynamicTypeInfo &K : *SucceededSet) {
+          // If the picked two records have a common descendant the cast is
+          // feasible into that descendant record.
+          if (isDerivedFrom(K.getType(), I.getType()) &&
+              isDerivedFrom(K.getType(), J.getType())) {
+            return false;
+          }
+        }
+        // If the picked two records does not have a common descendant the cast
+        // is infeasible as the object could not be casted into both of them.
+        return true;
+      }
+    }
+  }
+
+  return false;
+}
+
 const DynamicTypeInfo *getDynamicTypeInfo(ProgramStateRef State,
                                           const MemRegion *MR) {
   MR = getSimplifiedRegion(MR);
 
   // 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 new DynamicTypeInfo(TR->getLocationType(), /*CanBeSub=*/false);
 
   if (const auto *SR = dyn_cast<SymbolicRegion>(MR))
     return new DynamicTypeInfo(SR->getSymbol()->getType());
 
   return nullptr;
 }
 
-const DynamicTypeInfo *getRawDynamicTypeInfo(ProgramStateRef State,
+const DynamicTypeInfo *getStoredDynamicTypeInfo(ProgramStateRef State,
                                                 const MemRegion *MR) {
+  if (!MR)
+    return nullptr;
+
+  MR = getSimplifiedRegion(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);
+const DynamicTypeInfo *getFailedCastInfo(ProgramStateRef State,
+  if (!MR)
+    return nullptr;
+
+  MR = getSimplifiedRegion(MR);
+  const auto *Lookup = State->get<FailedCastMap>().lookup(MR);
   if (!Lookup)
     return nullptr;
 
-  for (const DynamicCastInfo &Cast : *Lookup)
-    if (Cast.equals(CastFromTy, CastToTy))
+  for (const DynamicTypeInfo &Cast : *Lookup) {
+    QualType FailedCastTy = Cast.getType();
+    if (FailedCastTy->getPointeeCXXRecordDecl() ==
+            CastToTy->getPointeeCXXRecordDecl() ||
+        isDerivedFrom(CastToTy, FailedCastTy)) {
       return &Cast;
+    }
+  }
 
   return nullptr;
 }
 
 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
                                    const DynamicTypeInfo *NewTy) {
   assert((NewTy->getType()->isAnyPointerType() ||
           NewTy->getType()->isReferenceType()) &&
          "DynamicTypeInfo should always be a pointer.");
   MR = getSimplifiedRegion(MR);
   State = State->set<DynamicTypeMap>(MR, *NewTy);
   assert(State);
   return State;
 }
 
 ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
                                    QualType NewTy, bool CanBeSubClassed) {
   return setDynamicTypeInfo(State, MR,
                             new DynamicTypeInfo(NewTy, CanBeSubClassed));
 }
 
-ProgramStateRef setDynamicTypeAndCastInfo(ProgramStateRef State,
-                                          const MemRegion *MR,
-                                          QualType CastFromTy,
-                                          QualType CastToTy,
-                                          bool CastSucceeds) {
+ProgramStateRef setDynamicTypeInfo(ProgramStateRef State, const MemRegion *MR,
+                                   QualType CastToTy, bool CastSucceeds,
+                                   const DynamicTypeInfo *CastInfo) {
   if (!MR)
     return State;
 
-  if (CastSucceeds) {
-    assert((CastToTy->isAnyPointerType() || CastToTy->isReferenceType()) &&
-           "DynamicTypeInfo should always be a pointer.");
-    State = State->set<DynamicTypeMap>(MR, CastToTy);
-  }
-
-  DynamicCastInfo::CastResult ResultKind =
-      CastSucceeds ? DynamicCastInfo::CastResult::Success
-                   : DynamicCastInfo::CastResult::Failure;
-
+  MR = getSimplifiedRegion(MR);
   CastSet::Factory &F = State->get_context<CastSet>();
+  const CastSet *TempSet;
+  TempSet = CastSucceeds ? State->get<SucceededCastMap>(MR)
+                         : State->get<FailedCastMap>(MR);
 
-  const CastSet *TempSet = State->get<DynamicCastMap>(MR);
   CastSet Set = TempSet ? *TempSet : F.getEmptySet();
+  Set = F.add(Set, CastToTy);
 
-  Set = F.add(Set, {CastFromTy, CastToTy, ResultKind});
-  State = State->set<DynamicCastMap>(MR, Set);
+  if (CastSucceeds) {
+    // If there is no 'CastInfo' or the 'CastToTy' is a downcast store it.
+    // Downcast gives more precision what is the current most derived class.
+    if (!CastInfo || isDerivedFrom(CastToTy, CastInfo->getType())) {
+      State = setDynamicTypeInfo(State, MR, CastToTy);
+    }
+  } else {
+    // Upcast gives more precision what is the largest set the class cannot be.
+    if (CastInfo && isDerivedFrom(CastInfo->getType(), CastToTy)) {
+      Set = F.remove(Set, *CastInfo);
+    }
+  }
 
+  State = CastSucceeds ? State->set<SucceededCastMap>(MR, Set)
+                       : State->set<FailedCastMap>(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);
+      State = State->remove<FailedCastMap>(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);
+  return removeDead(State, State->get<FailedCastMap>(), 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 (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>();
+template <typename MapTy>
+static void printCastsJson(raw_ostream &Out, ProgramStateRef State,
+                           const MapTy &Map, const char *NL, unsigned int Space,
   if (Map.isEmpty()) {
     Out << "null," << NL;
     return;
   }
 
   ++Space;
   Out << '[' << NL;
-  for (DynamicCastMapTy::iterator I = Map.begin(); I != Map.end(); ++I) {
+  for (typename MapTy::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;
+      Indent(Out, Space, IsDot);
       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") << "\" }";
+        Out << '\"' << SI->getType().getAsString() << '\"';
 
         if (std::next(SI) != Set.end())
-          Out << ',';
-        Out << NL;
+          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);
+
+  Indent(Out, Space, IsDot) << "\"succeeded_casts\": ";
+  printCastsJson(Out, State, State->get<SucceededCastMap>(), NL, Space, IsDot);
+
+  Indent(Out, Space, IsDot) << "\"failed_casts\": ";
+  printCastsJson(Out, State, State->get<FailedCastMap>(), NL, Space, IsDot);
 }
 
 } // namespace ento
 } // namespace clang

clang/test/Analysis/cast-value-hierarchy-failures-set.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
+// RUN:  -verify %s 2>&1 | FileCheck %s
+
+// expected-no-diagnostics
+
+#include "Inputs/llvm.h"
+
+using namespace llvm;
+
+void clang_analyzer_printState();
+
+struct A {};     // A
+struct B : A {}; // `-B
+struct C : B {}; //   `-C
+struct D : C {}; //     `-D
+
+void test_downcast(const A *a) {
+  if (isa<C>(a))
+    return;
+
+  clang_analyzer_printState();
+  // CHECK:    "failed_casts": [
+  // CHECK-NEXT: { "region": "SymRegion{reg_$0<const struct A * a>}", "casts": [
+  // CHECK-NEXT:   "struct C *"
+  // CHECK-NEXT: ]}
+
+  // A failed upcast gives more precision what the type cannot be.
+  if (isa<B>(a))
+    return;
+
+  clang_analyzer_printState();
+  // CHECK:    "failed_casts": [
+  // CHECK-NEXT: { "region": "SymRegion{reg_$0<const struct A * a>}", "casts": [
+  // CHECK-NEXT:   "struct B *"
+  // CHECK-NEXT: ]}
+
+  // A failed downcast does not give more information.
+  if (isa<D>(a))
+    return;
+
+  clang_analyzer_printState();
+  // CHECK:    "failed_casts": [
+  // CHECK-NEXT: { "region": "SymRegion{reg_$0<const struct A * a>}", "casts": [
+  // CHECK-NEXT:   "struct B *"
+  // CHECK-NEXT: ]}
+}

clang/test/Analysis/cast-value-hierarchy-fp-suppression.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
+// RUN:  -verify %s
+
+#include "Inputs/llvm.h"
+
+using namespace llvm;
+
+void clang_analyzer_warnIfReached();
+
+struct A {};             //   A
+struct B : virtual A {}; //  / \.
+struct C : virtual A {}; // B   C
+struct D : B, C {};      //  \ /
+                         //   D
+
+void test_downcast(const A *a) {
+  if (isa<B>(a))
+    if (isa<C>(a))
+      if (isa<D>(a))
+        clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void test_downcast_infeasible(const A *a) {
+  if (isa<B>(a))
+    if (isa<C>(a))
+      clang_analyzer_warnIfReached(); // no-warning
+}

clang/test/Analysis/cast-value-hierarchy-succeeds.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
+// RUN:  -verify %s 2>&1 | FileCheck %s
+
+// expected-no-diagnostics
+
+#include "Inputs/llvm.h"
+
+using namespace llvm;
+
+void clang_analyzer_printState();
+
+struct A {};     // A
+struct B : A {}; // `-B
+struct C : B {}; //   `-C
+struct D : C {}; //     `-D
+
+void test_downcast(const A *a) {
+  clang_analyzer_printState();
+  // CHECK: "dynamic_types": null
+
+  if (!isa<C>(a))
+    return;
+
+  clang_analyzer_printState();
+  // CHECK:      "dynamic_types": [
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct A * a>}", "dyn_type": "struct C", "sub_classable": true }
+
+  if (!isa<D>(a))
+    return;
+
+  // A succeeded cast gives more precision what is the most-derived class.
+  clang_analyzer_printState();
+  // CHECK:      "dynamic_types": [
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct A * a>}", "dyn_type": "struct D", "sub_classable": true }
+
+  if (!isa<B>(a))
+    return;
+
+  // A succeeded upcast does not give more information.
+  clang_analyzer_printState();
+  // CHECK:      "dynamic_types": [
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct A * a>}", "dyn_type": "struct D", "sub_classable": true }
+}

clang/test/Analysis/cast-value-hierarchy.cpp

+// RUN: %clang_analyze_cc1 \
+// RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
+// RUN:  -verify %s
+
+#include "Inputs/llvm.h"
+
+using namespace llvm;
+
+void clang_analyzer_warnIfReached();
+                    //   X
+struct X {};        //  / \.
+struct Y : X {};    // Y-. \.
+struct Z : X, Y {}; //    `-Z
+// expected-warning@-1 {{direct base 'X' is inaccessible due to ambiguity:\n    struct Z -> struct X\n    struct Z -> struct Y -> struct X}}
+
+void test_triangle_feasible(const X *x) {
+  if (isa<Y>(x))
+    if (isa<Z>(x))
+      clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void test_triangle_infeasible(const X *x) {
+  if (!isa<Y>(x))
+    if (isa<Z>(x))
+      clang_analyzer_warnIfReached(); // no-warning
+}
+
+struct A {};             //   A
+struct B : virtual A {}; //  / \.
+struct C : virtual A {}; // B   C
+struct D : B, C {};      //  \ / \.
+struct E : C {};         //   D   E
+
+void test_failures_set(const A *a) {
+  if (isa<B>(a) || isa<C>(a))
+    if (isa<D>(a))
+      clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+}
+
+void test_faiures_set_infeasible(const A *a) {
+  if (!isa<B>(a) && isa<C>(a))
+    if (isa<D>(a))
+      clang_analyzer_warnIfReached(); // no-warning
+}
+
+void test_downcast(const A *a) {
+  if (isa<B>(a)) {
+    if (isa<D>(a))
+      clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+  }
+}
+
+void test_downcast_infeasible(const A *a) {
+  if (isa<B>(a))
+    if (isa<C>(a))
+      clang_analyzer_warnIfReached(); // no-warning
+}
+
+void test_upcast(const A *a) {
+  if (isa<D>(a) && isa<B>(a)) {
+    clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+
+    if (isa<C>(a))
+      clang_analyzer_warnIfReached(); // expected-warning {{REACHABLE}}
+  }
+}
+
+void test_downcast_chaining_infeasible(const A *a) {
+  if (isa<B>(a) && !isa<C>(a))
+    if (isa<D>(a) || isa<E>(a))
+      clang_analyzer_warnIfReached(); // no-warning
+}

clang/test/Analysis/cast-value-notes.cpp

 // RUN: %clang_analyze_cc1 \
 // RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
 // RUN:  -analyzer-output=text -verify %s
 
 #include "Inputs/llvm.h"
 
 namespace clang {
 struct Shape {
   template <typename T>
   const T *castAs() const;
 
   template <typename T>
   const T *getAs() const;
 };
-class Triangle : public Shape {};
-class Circle : public Shape {};
+struct Triangle : Shape {};
+struct Circle : Shape {};
 } // namespace clang
 
 using namespace llvm;
 using namespace clang;
 
 void evalReferences(const Shape &S) {
   const auto &C = dyn_cast<Circle>(S);
   // expected-note@-1 {{Assuming 'S' is not a 'Circle'}}
   // expected-note@-2 {{Dereference of null pointer}}
   // expected-warning@-3 {{Dereference of null pointer}}
 }
 
 void evalNonNullParamNonNullReturnReference(const Shape &S) {
   // Unmodeled cast from reference to pointer.
   const auto *C = dyn_cast_or_null<Circle>(S);
   // expected-note@-1 {{'C' initialized here}}
 
   if (!dyn_cast_or_null<Circle>(C)) {
     // expected-note@-1 {{'C' is a 'Circle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
-  if (dyn_cast_or_null<Triangle>(C)) {
-    // expected-note@-1 {{Assuming 'C' is not a 'Triangle'}}
-    // expected-note@-2 {{Taking false branch}}
-    return;
-  }
-
   if (isa<Triangle>(C)) {
     // expected-note@-1 {{'C' is not a 'Triangle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
   if (isa<Circle>(C)) {
     // expected-note@-1 {{'C' is a 'Circle'}}
     // expected-note@-2 {{Taking true branch}}
 
     (void)(1 / !C);
     // expected-note@-1 {{'C' is non-null}}
     // expected-note@-2 {{Division by zero}}
     // expected-warning@-3 {{Division by zero}}
   }
 }
 
 void evalNonNullParamNonNullReturn(const Shape *S) {
   const auto *C = cast<Circle>(S);
   // expected-note@-1 {{'S' is a 'Circle'}}
   // expected-note@-2 {{'C' initialized here}}
 
-  if (!isa<Triangle>(C)) {
-    // expected-note@-1 {{Assuming 'C' is a 'Triangle'}}
-    // expected-note@-2 {{Taking false branch}}
-    return;
-  }
-
-  if (!isa<Triangle>(C)) {
-    // expected-note@-1 {{'C' is a 'Triangle'}}
+  if (isa<Triangle>(C)) {
+    // expected-note@-1 {{'C' is not a 'Triangle'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
   (void)(1 / !C);
   // expected-note@-1 {{'C' is non-null}}
   // expected-note@-2 {{Division by zero}}
   // expected-warning@-3 {{Division by zero}}

clang/test/Analysis/cast-value-state-dump.cpp

 // RUN: %clang_analyze_cc1 \
 // RUN:  -analyzer-checker=core,apiModeling.llvm.CastValue,debug.ExprInspection\
 // RUN:  -analyzer-output=text -verify %s 2>&1 | FileCheck %s
 
 #include "Inputs/llvm.h"
 
 void clang_analyzer_printState();
 
 namespace clang {
 struct Shape {};
-class Triangle : public Shape {};
-class Circle : public Shape {};
-class Square : public Shape {};
+struct Circle : Shape {};
+struct Square : Shape {};
+struct Octagram : Shape {};
 } // namespace clang
 
 using namespace llvm;
 using namespace clang;
 
 void evalNonNullParamNonNullReturn(const Shape *S) {
+  if (isa<Octagram>(S)) {
+    // expected-note@-1 {{Assuming 'S' is not a 'Octagram'}}
+    // expected-note@-2 {{Taking false branch}}
+    return;
+  }
+
   const auto *C = dyn_cast_or_null<Circle>(S);
   // expected-note@-1 {{Assuming 'S' is a 'Circle'}}
   // expected-note@-2 {{'C' initialized here}}
 
-  // FIXME: We assumed that 'S' is a 'Circle' therefore it is not a 'Square'.
   if (dyn_cast_or_null<Square>(S)) {
-    // expected-note@-1 {{Assuming 'S' is not a 'Square'}}
+    // expected-note@-1 {{'S' is not a 'Square'}}
     // expected-note@-2 {{Taking false branch}}
     return;
   }
 
   clang_analyzer_printState();
 
   // CHECK:      "dynamic_types": [
-  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct clang::Shape * S>}", "dyn_type": "const class clang::Circle", "sub_classable": true }
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct clang::Shape * S>}", "dyn_type": "const struct clang::Circle", "sub_classable": true }
   // CHECK-NEXT: ],
-  // CHECK-NEXT: "dynamic_casts": [
-  // CHECK:        { "region": "SymRegion{reg_$0<const struct clang::Shape * S>}", "casts": [
-  // CHECK-NEXT:     { "from": "const struct clang::Shape *", "to": "const class clang::Circle *", "kind": "success" },
-  // CHECK-NEXT:     { "from": "const struct clang::Shape *", "to": "const class clang::Square *", "kind": "fail" }
+  // CHECK-NEXT: "succeeded_casts": [
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct clang::Shape * S>}", "casts": [
+  // CHECK-NEXT:     "const struct clang::Circle *"
   // CHECK-NEXT:   ]}
+  // CHECK-NEXT: ],
+  // CHECK-NEXT: "failed_casts": [
+  // CHECK-NEXT:   { "region": "SymRegion{reg_$0<const struct clang::Shape * S>}", "casts": [
+  // CHECK-NEXT:     "const struct clang::Square *", "struct clang::Octagram *"
+  // CHECK-NEXT:   ]}
+  // CHECK-NEXT: ],
 
   (void)(1 / !C);
   // expected-note@-1 {{'C' is non-null}}
   // expected-note@-2 {{Division by zero}}
   // expected-warning@-3 {{Division by zero}}
 }
 

clang/test/Analysis/expr-inspection.c

 // CHECK-NEXT:     { "lctx_id": 1, "location_context": "#0 Call", "calling": "foo", "location": null, "items": [
 // CHECK-NEXT:       { "stmt_id": {{[0-9]+}}, "pretty": "clang_analyzer_printState", "value": "&code{clang_analyzer_printState}" }
 // CHECK-NEXT:     ]}
 // CHECK-NEXT:   ]},
 // CHECK-NEXT:   "constraints": [
 // CHECK-NEXT:     { "symbol": "reg_$0<int x>", "range": "{ [-2147483648, 13] }" }
 // CHECK-NEXT:   ],
 // CHECK-NEXT:   "dynamic_types": null,
-// CHECK-NEXT:   "dynamic_casts": null,
+// CHECK-NEXT:   "succeeded_casts": null,
+// CHECK-NEXT:   "failed_casts": null,
 // CHECK-NEXT:   "constructing_objects": null,
 // CHECK-NEXT:   "checker_messages": null
 // CHECK-NEXT: }
-