Constant time dynamic cast (#1250)

* Constant time dynamic cast.

* Use getClassInfo virtual function.
Fix problem because of instanciation of specializations was in wrong order for clang.

* Improve comments.

* Improve comment.

* Ensure s_first is defined before kClassInfo, to ensure construction ordering.

4 files changed, 185 insertions, 52 deletions

diff --git a/source/slang/slang-syntax-base-defs.h b/source/slang/slang-syntax-base-defs.h
index afec117ca..60e888b56 100644
--- a/source/slang/slang-syntax-base-defs.h
+++ b/source/slang/slang-syntax-base-defs.h
@@ -6,9 +6,8 @@
 
 ABSTRACT_SYNTAX_CLASS(NodeBase, RefObject)
     // A helper to access the corresponding class on a concrete instance
-    RAW(
-    virtual SyntaxClass<NodeBase> getClass() = 0;
-    )
+    RAW(virtual const SyntaxClassBase::ClassInfo& getClassInfo() const = 0;)
+    RAW(SyntaxClass<NodeBase> getClass() { return SyntaxClass<NodeBase>(&getClassInfo()); } )
 END_SYNTAX_CLASS()
 
 // Base class for all nodes representing actual syntax
diff --git a/source/slang/slang-syntax.cpp b/source/slang/slang-syntax.cpp
index c05f9aa0f..cc2cf46a1 100644
--- a/source/slang/slang-syntax.cpp
+++ b/source/slang/slang-syntax.cpp
@@ -8,6 +8,9 @@
 
 namespace Slang
 {
+    // We want this first, before the kClassInfo variables so it is constructed before anything else. 
+    /* static*/ SyntaxClassBase::ClassInfo* SyntaxClassBase::ClassInfo::s_first = nullptr;
+
     // BasicExpressionType
 
     bool BasicExpressionType::EqualsImpl(Type * type)
@@ -32,19 +35,19 @@ namespace Slang
 
 #define ABSTRACT_SYNTAX_CLASS(NAME, BASE)   \
     template<>                              \
-    SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<NAME>::kClassInfo = { #NAME, &SyntaxClassBase::Impl<BASE>::kClassInfo, nullptr };
+    SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<NAME>::kClassInfo(#NAME, nullptr, &SyntaxClassBase::Impl<BASE>::kClassInfo);
 
 #define SYNTAX_CLASS(NAME, BASE)                                                \
-    void NAME::accept(NAME::Visitor* visitor, void* extra)                      \
-    { visitor->dispatch_##NAME(this, extra); }                                  \
     template<>                                                                  \
     void* SyntaxClassBase::Impl<NAME>::createFunc() { return new NAME(); }      \
-    SyntaxClass<NodeBase> NAME::getClass() { return Slang::getClass<NAME>(); }  \
     template<>                                                                  \
-    SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<NAME>::kClassInfo = { #NAME, &SyntaxClassBase::Impl<BASE>::kClassInfo, &SyntaxClassBase::Impl<NAME>::createFunc };
-
+    SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<NAME>::kClassInfo( #NAME, &SyntaxClassBase::Impl<NAME>::createFunc, &SyntaxClassBase::Impl<BASE>::kClassInfo); \
+    void NAME::accept(NAME::Visitor* visitor, void* extra)                      \
+    { visitor->dispatch_##NAME(this, extra); }                                  \
+    const SyntaxClassBase::ClassInfo& NAME::getClassInfo() const { return SyntaxClassBase::Impl<NAME>::kClassInfo; }  
+    
 template<>
-SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<RefObject>::kClassInfo = { "RefObject", nullptr, nullptr };
+SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl<RefObject>::kClassInfo("RefObject", nullptr, nullptr);
 
 ABSTRACT_SYNTAX_CLASS(NodeBase, RefObject);
 ABSTRACT_SYNTAX_CLASS(SyntaxNodeBase, NodeBase);
@@ -71,26 +74,114 @@ ABSTRACT_SYNTAX_CLASS(GlobalGenericParamSubstitution, Substitutions);
 #include "slang-val-defs.h"
 #include "slang-object-meta-end.h"
 
-bool SyntaxClassBase::isSubClassOfImpl(SyntaxClassBase const& super) const
+SyntaxClassBase::ClassInfo::ClassInfo(const char* name, CreateFunc createFunc, const ClassInfo* superClass):
+    m_name(name),
+    m_createFunc(createFunc),
+    m_superClass(superClass),
+    m_next(s_first)
+{
+    m_classId = 0;
+    m_childrenEndClassId = 0;
+
+    s_first = this;
+}
+
+
+
+static uint32_t _calcRangeRec(const SyntaxClassBase::ClassInfo* classInfo, const Dictionary<const SyntaxClassBase::ClassInfo*, List<const SyntaxClassBase::ClassInfo*> >& childMap, uint32_t index)
 {
-    SyntaxClassBase::ClassInfo const* info = classInfo;
+    classInfo->m_classId = index++;
+    // Do the calc range for all the children
+    auto list = childMap.TryGetValue(classInfo);
+
+    if (list)
+    {
+        for (auto child : *list)
+        {
+            index = _calcRangeRec(child, childMap, index);
+        }
+    }
+
+    classInfo->m_childrenEndClassId = index;
+    return index;
+}
+
+bool SyntaxClassBase::ClassInfo::isSubClassOfSlow(const ThisType& super) const
+{
+    SyntaxClassBase::ClassInfo const* info = this;
     while (info)
     {
-        if (info == super.classInfo)
+        if (info == &super)
             return true;
+        info = info->m_superClass;
+    }
+    return false;
+}
 
-        info = info->baseClass;
+static bool _checkSubClassRange()
+{
+    typedef SyntaxClassBase::ClassInfo ClassInfo;
+
+    List<const ClassInfo*> list;
+    for (const ClassInfo* type = ClassInfo::s_first; type; type = type->m_next)
+    {
+        list.add(type);
     }
 
-    return false;
+    for (Index i = 0; i < list.getCount(); ++i)
+    {
+        for (Index j = 0; j < list.getCount(); ++j)
+        {
+            auto a = list[i];
+            auto b = list[j];
+            if (a->isSubClassOf(*b) != a->isSubClassOfSlow(*b))
+            {
+                return false;
+            }
+        }
+    }
+
+    return true;
 }
 
-NodeBase* _dynamicCastImpl(NodeBase* node, SyntaxClassBase const& toClass)
+
+/* static */SlangResult SyntaxClassBase::ClassInfo::initRanges()
 {
-    if(!node) return nullptr;
-    if(node->getClass().isSubClassOfImpl(toClass))
-        return node;
-    return nullptr;
+    // Remove the warning about not referenced
+    SLANG_UNUSED(&_checkSubClassRange);
+
+    // TODO(JS):
+    // Note that the calculating of the ranges could be done more efficiently by adding to an array of struct { super, class }, sorting, by super classs
+    // and using a dictionary to map from class it's first in list of super class use. This works for now though.
+  
+    // We want to produce a map from a node that holds all of it's children
+    Dictionary<const ThisType*, List<const ThisType*> > childMap;
+
+    const List<const ThisType*> emptyList;
+
+    {
+         for (const ThisType* type = s_first; type; type = type->m_next)
+         {
+             if (type->m_superClass)
+             {
+                 // Add to that item
+                 List<const ThisType*>* list = childMap.TryGetValueOrAdd(type->m_superClass, emptyList);
+                 if (!list)
+                 {
+                     list = childMap.TryGetValue(type->m_superClass);
+                 }
+                 SLANG_ASSERT(list);
+                 list->add(type);
+             }
+         }
+    }
+
+    // We want to recursively work out a range
+    _calcRangeRec(&SyntaxClassBase::Impl<RefObject>::kClassInfo, childMap, 1);
+
+    SLANG_ASSERT(_checkSubClassRange());
+
+    return SLANG_OK;
 }
 
 
diff --git a/source/slang/slang-syntax.h b/source/slang/slang-syntax.h
index 6177b894d..660cdb2d5 100644
--- a/source/slang/slang-syntax.h
+++ b/source/slang/slang-syntax.h
@@ -463,14 +463,37 @@ namespace Slang
         // Run-time type representation for syntax nodes
         struct ClassInfo
         {
-            // Textual class name, for debugging
-            char const* name;
+            typedef ClassInfo ThisType;
 
-            // Base class for runtime queries
-            ClassInfo const*  baseClass;
-
-            // Callback to use when creating instances
-            CreateFunc createFunc;
+                /// A constant time implementation of isSubClassOf
+            SLANG_FORCE_INLINE bool isSubClassOf(const ThisType& super) const
+            {
+                // We include super.m_classId, because it's a subclass of itself.
+                return m_classId >= super.m_classId && m_classId < super.m_childrenEndClassId;
+            }
+                /// Will produce the same result as isSubClassOf, but more slowly by traversing the m_superClass
+                /// Works without initRange being called. 
+            bool isSubClassOfSlow(const ThisType& super) const;
+
+                /// This function must have been called before any dynamic casting will work (via the m_classId/m_childrenEndClassId.
+                /// It sets up the m_rangeStart/m_rangeEnd values to make.
+                /// Is called within the creation of Session
+            static SlangResult initRanges();
+
+                /// Ctor
+            ClassInfo(const char* name, CreateFunc createFunc, const ClassInfo* superClass);
+
+                /// The id for this class. The children of this class are in the range of m_classId + 1 to (but not including) m_childrenEndId.
+            mutable uint32_t m_classId;
+                /// Non inclusive end of range of children.
+            mutable uint32_t m_childrenEndClassId;        
+
+            const ClassInfo* m_superClass;          ///< The super class of this class, or nullptr if has no super class. 
+            const char* m_name;                     ///< Textual class name, for debugging 
+            CreateFunc m_createFunc;                ///< Callback to use when creating instances
+            
+            ClassInfo* m_next;                      ///< Next in list starting from s_first
+            static ClassInfo* s_first;
         };
 
         SyntaxClassBase()
@@ -485,13 +508,13 @@ namespace Slang
             auto ci = classInfo;
             if (!ci) return nullptr;
 
-            auto cf = ci->createFunc;
+            auto cf = ci->m_createFunc;
             if (!cf) return nullptr;
 
             return cf();
         }
 
-        bool isSubClassOfImpl(SyntaxClassBase const& super) const;
+        SLANG_FORCE_INLINE bool isSubClassOfImpl(SyntaxClassBase const& super) const { return classInfo->isSubClassOf(*super.classInfo); }
 
         ClassInfo const* classInfo = nullptr;
 
@@ -549,23 +572,18 @@ namespace Slang
         return SyntaxClass<T>::getClass();
     }
 
-    NodeBase* _dynamicCastImpl(NodeBase* node, SyntaxClassBase const& toClass);
-
     template<typename T>
-    T* dynamicCast(NodeBase* node)
-    {
-        return (T*) _dynamicCastImpl(node, getClass<T>());
-    }
+    SLANG_FORCE_INLINE T* dynamicCast(NodeBase* node);
 
     template<typename T>
-    const T* dynamicCast(const NodeBase* node) { return dynamicCast<T>(const_cast<NodeBase*>(node)); }
+    SLANG_FORCE_INLINE const T* dynamicCast(const NodeBase* node);
 
     template<typename T>
-    T* as(NodeBase* node) { return dynamicCast<T>(node); }
+    SLANG_FORCE_INLINE T* as(NodeBase* node);
 
     template<typename T>
-    const T* as(const NodeBase* node) { return dynamicCast<T>(const_cast<NodeBase*>(node)); }
-
+    SLANG_FORCE_INLINE const T* as(const NodeBase* node);
+    
     struct SubstitutionSet
     {
         RefPtr<Substitutions> substitutions;
@@ -1305,7 +1323,7 @@ namespace Slang
 #define SYNTAX_CLASS(NAME, BASE, ...)                                   \
     class NAME : public BASE {                                          \
     virtual void accept(NAME::Visitor* visitor, void* extra) override;  \
-    public: virtual SyntaxClass<NodeBase> getClass() override;          \
+    public: virtual const SyntaxClassBase::ClassInfo& getClassInfo() const override;          \
     public: /* ... */
 #include "slang-expr-defs.h"
 #include "slang-decl-defs.h"
@@ -1570,6 +1588,30 @@ namespace Slang
         /// Get the module that a declaration is associated with, if any.
     Module* getModule(Decl* decl);
 
+    template<typename T>
+    SLANG_FORCE_INLINE T* dynamicCast(NodeBase* node)
+    {
+        return (node && node->getClassInfo().isSubClassOf(SyntaxClassBase::Impl<T>::kClassInfo)) ? static_cast<T*>(node) : nullptr; 
+    }
+
+    template<typename T>
+    SLANG_FORCE_INLINE const T* dynamicCast(const NodeBase* node)
+    {
+        return (node && node->getClassInfo().isSubClassOf(SyntaxClassBase::Impl<T>::kClassInfo)) ? static_cast<const T*>(node) : nullptr;
+    }
+
+    template<typename T>
+    SLANG_FORCE_INLINE T* as(NodeBase* node)
+    {
+        return (node && node->getClassInfo().isSubClassOf(SyntaxClassBase::Impl<T>::kClassInfo)) ? static_cast<T*>(node) : nullptr;
+    }
+
+    template<typename T>
+    SLANG_FORCE_INLINE const T* as(const NodeBase* node)
+    {
+        return (node && node->getClassInfo().isSubClassOf(SyntaxClassBase::Impl<T>::kClassInfo)) ? static_cast<const T*>(node) : nullptr;
+    }
+
 } // namespace Slang
 
 #endif
diff --git a/source/slang/slang.cpp b/source/slang/slang.cpp
index 08c996fd2..6c1a59ea4 100644
--- a/source/slang/slang.cpp
+++ b/source/slang/slang.cpp
@@ -116,20 +116,21 @@ void Session::init()
     // Set all the shared library function pointers to nullptr
     ::memset(m_sharedLibraryFunctions, 0, sizeof(m_sharedLibraryFunctions));
 
+    {
+        static auto res = SyntaxClassBase::ClassInfo::initRanges();
+    }
+
     // Initialize the lookup table of syntax classes:
 
-    #define SYNTAX_CLASS(NAME, BASE) \
-        mapNameToSyntaxClass.Add(getNamePool()->getName(#NAME), getClass<NAME>());
-
-#include "slang-object-meta-begin.h"
-#include "slang-syntax-base-defs.h"
-#include "slang-expr-defs.h"
-#include "slang-decl-defs.h"
-#include "slang-modifier-defs.h"
-#include "slang-stmt-defs.h"
-#include "slang-type-defs.h"
-#include "slang-val-defs.h"
-#include "slang-object-meta-end.h"
+    // We can just iterate over the class pointers.
+    // NOTE! That this adds the names of the abstract classes too(!)
+    {
+        const SyntaxClassBase::ClassInfo* info = SyntaxClassBase::ClassInfo::s_first;
+        for (; info; info = info->m_next)
+        {
+            mapNameToSyntaxClass.Add(getNamePool()->getName(info->m_name), SyntaxClass<Slang::RefObject>(info));
+        }
+    }
 
     // Make sure our source manager is initialized
     builtinSourceManager.initialize(nullptr, nullptr);