[Draft] LLVM ExtensibleRTTI with implict static IDs and no CRTP

ExtensibleRTTI.patch

From 657708494fd1a26b745f4ea7f06ac32620970694 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Stefan=20Gr=C3=A4nitz?= <stefan.graenitz@gmail.com>
Date: Thu, 25 Feb 2021 17:35:09 +0100
Subject: [PATCH] LLVM ExtensibleRTTI with implict static IDs and no CRTP

---
 llvm/include/llvm/Support/Casting.h           |  16 +-
 llvm/include/llvm/Support/ExtensibleRTTI.h    | 147 +++++++++++-------
 llvm/lib/Support/ExtensibleRTTI.cpp           |   7 +-
 llvm/unittests/Support/ExtensibleRTTITest.cpp |  33 ++--
 4 files changed, 125 insertions(+), 78 deletions(-)

diff --git a/llvm/include/llvm/Support/Casting.h b/llvm/include/llvm/Support/Casting.h
index d6f7793d5df0..3b0aa1a6ac05 100644
--- a/llvm/include/llvm/Support/Casting.h
+++ b/llvm/include/llvm/Support/Casting.h
@@ -15,6 +15,7 @@
 #define LLVM_SUPPORT_CASTING_H
 
 #include "llvm/Support/Compiler.h"
+#include "llvm/Support/ExtensibleRTTI.h"
 #include "llvm/Support/type_traits.h"
 #include <cassert>
 #include <memory>
@@ -61,7 +62,20 @@ struct isa_impl {
 
 /// Always allow upcasts, and perform no dynamic check for them.
 template <typename To, typename From>
-struct isa_impl<To, From, std::enable_if_t<std::is_base_of<To, From>::value>> {
+struct isa_impl<
+    To, From,
+    std::enable_if_t<std::is_base_of<ExtensibleRTTIRoot, To>::value>> {
+  static inline bool doit(const From &Val) {
+    return ExtensibleRTTI<To>::classof(&Val);
+  }
+};
+
+/// Always allow upcasts, and perform no dynamic check for them.
+template <typename To, typename From>
+struct isa_impl<
+    To, From,
+    std::enable_if_t<std::is_base_of<To, From>::value &&
+                     !std::is_base_of<ExtensibleRTTIRoot, To>::value>> {
   static inline bool doit(const From &) { return true; }
 };
 
diff --git a/llvm/include/llvm/Support/ExtensibleRTTI.h b/llvm/include/llvm/Support/ExtensibleRTTI.h
index 6b8510ce759f..ad8290005b66 100644
--- a/llvm/include/llvm/Support/ExtensibleRTTI.h
+++ b/llvm/include/llvm/Support/ExtensibleRTTI.h
@@ -25,28 +25,26 @@
 // E.g.
 //
 //   @code{.cpp}
-//   class MyBaseClass : public RTTIExtends<MyBaseClass, RTTIRoot> {
-//   public:
-//     static char ID;
+//   class MyBaseClass : public ExtensibleRTTIRoot {
+//     const ExtensibleRTTI<MyBaseClass> _{this};
+//    public:
 //     virtual void foo() = 0;
 //   };
 //
-//   class MyDerivedClass1 : public RTTIExtends<MyDerivedClass1, MyBaseClass> {
+//   class MyDerivedClass1 : public MyBaseClass {
+//     const ExtensibleRTTI<MyDerivedClass1> _{this};
 //   public:
-//     static char ID;
+//     using ParentT = MyBaseClass;
 //     void foo() override {}
 //   };
 //
-//   class MyDerivedClass2 : public RTTIExtends<MyDerivedClass2, MyBaseClass> {
+//   class MyDerivedClass2 : public MyBaseClass {
+//     const ExtensibleRTTI<MyDerivedClass2> _{this};
 //   public:
-//     static char ID;
+//     using ParentT = MyBaseClass;
 //     void foo() override {}
 //   };
 //
-//   char MyBaseClass::ID = 0;
-//   char MyDerivedClass1::ID = 0;
-//   char MyDerivedClass2:: ID = 0;
-//
 //   void fn() {
 //     std::unique_ptr<MyBaseClass> B = llvm::make_unique<MyDerivedClass1>();
 //     llvm::outs() << isa<MyBaseClass>(B) << "\n"; // Outputs "1".
@@ -63,71 +61,100 @@
 
 namespace llvm {
 
-template <typename ThisT, typename ParentT> class RTTIExtends;
+template <typename ThisT> class ExtensibleRTTI;
 
-/// Base class for the extensible RTTI hierarchy.
-///
-/// This class defines virtual methods, dynamicClassID and isA, that enable
-/// type comparisons.
-class RTTIRoot {
-public:
-  virtual ~RTTIRoot() = default;
+namespace detail {
+namespace rtti {
 
-  /// Returns the class ID for this type.
-  static const void *classID() { return &ID; }
+template <typename ThisT> class TypeInfoImpl;
+
+class TypeInfo {
+public:
+  virtual bool derives(const TypeInfo &To) const = 0;
+  virtual ~TypeInfo() {}
+};
 
-  /// Returns the class ID for the dynamic type of this RTTIRoot instance.
-  virtual const void *dynamicClassID() const = 0;
+template <typename... Ts> using CheckExists = void;
 
-  /// Returns true if this class's ID matches the given class ID.
-  virtual bool isA(const void *const ClassID) const {
-    return ClassID == classID();
+// Helper class to walk up the inheritance chain. We end up in this first
+// variant once the encountered type T contains no nested ParentT. There is
+// no further base class to forward the request to.
+template <typename T, typename Enabler = void> class DetectParent {
+public:
+  static bool forward_isa(const TypeInfo &From, const TypeInfo &To) {
+    return false;
   }
+};
 
-  /// Check whether this instance is a subclass of QueryT.
-  template <typename QueryT>
-  bool isA() const { return isA(QueryT::classID()); }
+// Second variant of the inheritance chain walker. We keep walking as long as
+// the encountered types define a nested ParentT.
+template <typename T> class DetectParent<T, CheckExists<typename T::ParentT>> {
+  using TypeInfoParent = TypeInfoImpl<typename T::ParentT>;
 
-private:
-  virtual void anchor();
+public:
+  static bool forward_isa(const TypeInfo &From, const TypeInfo &To) {
+    return static_cast<const TypeInfoParent &>(From).isA(To);
+  }
+};
 
-  static char ID;
+// Creates one static instance of itself for each ExtensibleRTTI class.
+template <typename ThisT> class TypeInfoImpl : public TypeInfo {
+public:
+  static const TypeInfoImpl<ThisT> Self;
+
+  // Virtual function for resolution of the dynamic type.
+  // ExtensibleRTTI::classof() calls it via a base class pointer.
+  bool derives(const TypeInfo &To) const override { return isA(To); }
+
+  // Non-virtual function called with:
+  //   * the dynamically resolved type info from derives()
+  //   * any statically resolved base class type info from forward_isa()
+  //     in the DetectParent helper
+  bool isA(const TypeInfo &To) const {
+    return &Self == &To || DetectParent<ThisT>::forward_isa(*this, To);
+  }
 };
 
-/// Inheritance utility for extensible RTTI.
-///
-/// Supports single inheritance only: A class can only have one
-/// ExtensibleRTTI-parent (i.e. a parent for which the isa<> test will work),
-/// though it can have many non-ExtensibleRTTI parents.
-///
-/// RTTIExtents uses CRTP so the first template argument to RTTIExtends is the
-/// newly introduced type, and the *second* argument is the parent class.
-///
-/// class MyType : public RTTIExtends<MyType, RTTIRoot> {
-/// public:
-///   static char ID;
-/// };
-///
-/// class MyDerivedType : public RTTIExtends<MyDerivedType, MyType> {
-/// public:
-///   static char ID;
-/// };
-///
-template <typename ThisT, typename ParentT>
-class RTTIExtends : public ParentT {
+// Static members of template classes are defined in the header.
+// TODO: Measure the overhead in terms of compile time and binary size.
+template <typename ThisT> const TypeInfoImpl<ThisT> TypeInfoImpl<ThisT>::Self{};
+
+} // namespace rtti
+} // namespace detail
+
+// The base class of a ExtensibleRTTI class hierarchy must derive from this.
+class ExtensibleRTTIRoot {
+  virtual void anchor() const;
+
 public:
-  // Inherit constructors from ParentT.
-  using ParentT::ParentT;
+  virtual ~ExtensibleRTTIRoot() {}
 
-  static const void *classID() { return &ThisT::ID; }
+private:
+  // Pointer to the static type info of the derived type.
+  detail::rtti::TypeInfo *Info{nullptr};
+
+  // Upon construction, we call this for each class in the inheritance chain,
+  // that has the ExtensibleRTTI member variable. The most derived class will
+  // call it last. This is the type info we assume for the object's entire
+  // lifetime.
+  void setExtensibleRTTI(const detail::rtti::TypeInfo &Info) {
+    this->Info = const_cast<detail::rtti::TypeInfo *>(&Info);
+  }
 
-  const void *dynamicClassID() const override { return &ThisT::ID; }
+  template <typename ThisT> friend class ExtensibleRTTI;
+};
 
-  bool isA(const void *const ClassID) const override {
-    return ClassID == classID() || ParentT::isA(ClassID);
+// Any derived class of a ExtensibleRTTI class hierarchy must contain a member
+// of this type + a nested type definition ParentT.
+template <typename ThisT> class ExtensibleRTTI {
+public:
+  ExtensibleRTTI(ThisT *Owner) {
+    Owner->setExtensibleRTTI(detail::rtti::TypeInfoImpl<ThisT>::Self);
   }
 
-  static bool classof(const RTTIRoot *R) { return R->isA<ThisT>(); }
+  static bool classof(const ExtensibleRTTIRoot *From) {
+    return From->Info->derives(detail::rtti::TypeInfoImpl<ThisT>::Self);
+  }
 };
 
 } // end namespace llvm
diff --git a/llvm/lib/Support/ExtensibleRTTI.cpp b/llvm/lib/Support/ExtensibleRTTI.cpp
index 1c98d1bb8feb..8017479cc584 100644
--- a/llvm/lib/Support/ExtensibleRTTI.cpp
+++ b/llvm/lib/Support/ExtensibleRTTI.cpp
@@ -9,5 +9,8 @@
 
 #include "llvm/Support/ExtensibleRTTI.h"
 
-void llvm::RTTIRoot::anchor() {}
-char llvm::RTTIRoot::ID = 0;
+namespace llvm {
+
+void ExtensibleRTTIRoot::anchor() const {}
+
+} // namespace llvm
diff --git a/llvm/unittests/Support/ExtensibleRTTITest.cpp b/llvm/unittests/Support/ExtensibleRTTITest.cpp
index 84d2a6f1ae45..6c86fe82518c 100644
--- a/llvm/unittests/Support/ExtensibleRTTITest.cpp
+++ b/llvm/unittests/Support/ExtensibleRTTITest.cpp
@@ -16,31 +16,34 @@ using namespace llvm;
 
 namespace {
 
-class MyBaseType : public RTTIExtends<MyBaseType, RTTIRoot> {
-public:
-  static char ID;
+class MyBaseType : public ExtensibleRTTIRoot {
+private:
+  const ExtensibleRTTI<MyBaseType> _{this};
 };
 
-class MyDerivedType : public RTTIExtends<MyDerivedType, MyBaseType> {
+class MyDerivedType : public MyBaseType {
 public:
-  static char ID;
+  using ParentT = MyBaseType;
+
+private:
+  const ExtensibleRTTI<MyDerivedType> _{this};
 };
 
-class MyOtherDerivedType : public RTTIExtends<MyOtherDerivedType, MyBaseType> {
+class MyOtherDerivedType : public MyBaseType {
 public:
-  static char ID;
+  using ParentT = MyBaseType;
+
+private:
+  const ExtensibleRTTI<MyOtherDerivedType> _{this};
 };
 
-class MyDeeperDerivedType
-    : public RTTIExtends<MyDeeperDerivedType, MyDerivedType> {
+class MyDeeperDerivedType : public MyDerivedType {
 public:
-  static char ID;
-};
+  using ParentT = MyDerivedType;
 
-char MyBaseType::ID = 0;
-char MyDerivedType::ID = 0;
-char MyOtherDerivedType::ID = 0;
-char MyDeeperDerivedType::ID = 0;
+private:
+  const ExtensibleRTTI<MyDeeperDerivedType> _{this};
+};
 
 TEST(ExtensibleRTTI, isa) {
   MyBaseType B;
-- 
2.28.0