From 6e9f407ad42ce635528b30f21366f903903a3682 Mon Sep 17 00:00:00 2001 From: jsmall-nvidia Date: Fri, 28 Feb 2020 09:21:19 -0500 Subject: 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. --- source/slang/slang-syntax.cpp | 125 ++++++++++++++++++++++++++++++++++++------ 1 file changed, 108 insertions(+), 17 deletions(-) (limited to 'source/slang/slang-syntax.cpp') 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::kClassInfo = { #NAME, &SyntaxClassBase::Impl::kClassInfo, nullptr }; + SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl::kClassInfo(#NAME, nullptr, &SyntaxClassBase::Impl::kClassInfo); #define SYNTAX_CLASS(NAME, BASE) \ - void NAME::accept(NAME::Visitor* visitor, void* extra) \ - { visitor->dispatch_##NAME(this, extra); } \ template<> \ void* SyntaxClassBase::Impl::createFunc() { return new NAME(); } \ - SyntaxClass NAME::getClass() { return Slang::getClass(); } \ template<> \ - SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl::kClassInfo = { #NAME, &SyntaxClassBase::Impl::kClassInfo, &SyntaxClassBase::Impl::createFunc }; - + SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl::kClassInfo( #NAME, &SyntaxClassBase::Impl::createFunc, &SyntaxClassBase::Impl::kClassInfo); \ + void NAME::accept(NAME::Visitor* visitor, void* extra) \ + { visitor->dispatch_##NAME(this, extra); } \ + const SyntaxClassBase::ClassInfo& NAME::getClassInfo() const { return SyntaxClassBase::Impl::kClassInfo; } + template<> -SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl::kClassInfo = { "RefObject", nullptr, nullptr }; +SyntaxClassBase::ClassInfo const SyntaxClassBase::Impl::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 >& 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 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 > childMap; + + const List emptyList; + + { + for (const ThisType* type = s_first; type; type = type->m_next) + { + if (type->m_superClass) + { + // Add to that item + List* 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::kClassInfo, childMap, 1); + + SLANG_ASSERT(_checkSubClassRange()); + + return SLANG_OK; } -- cgit v1.2.3