Compile-Time Topological Sort Exceeds Recursion Depth in C++

Hello

I'm implementing a compile-time topological sort algorithm using C++ template metaprogramming. The algorithm is designed to sort a graph of dependencies between different systems in a game engine, but it could be used to sort any directed acyclic graph (DAG).

The graph is represented as a tuple of SystemNode objects, each of which represents a system and its dependencies. The algorithm sorts these nodes in a way that each node appears before its dependencies in the sorted list.

Breakdown

1. GraphWithDegrees_t: This is the starting point of the algorithm. It takes a tuple of SystemNode objects and converts each node into a NodeWithDegree object, which is a node that also includes its degree (the number of nodes that depend on it). The degree of each node is calculated by the CountDependencies struct.

2. TopologicalSort: This is the main part of the algorithm. It's a recursive struct that performs the topological sort. It works as follows:

   • Extracts all nodes with a degree of zero (i.e., nodes that no other nodes depend on). These nodes are added to the ExtractedSystems tuple, which holds the sorted nodes.

   • Collects the dependencies of the zero-degree nodes. This is done to know which nodes' degrees need to be decremented in the next step.

   • Removes the zero-degree nodes from the original tuple.

   • Decrements the degree of any nodes that depended on the removed nodes. This is done by checking if a node is in the dependencies collected in the previous step.

   • Recursively calls TopologicalSort with the updated tuple and the ExtractedSystems tuple.

   • When the tuple is empty (i.e., all nodes have been sorted), the recursion ends and the ExtractedSystems tuple is returned as the result.

3. ExtractZeroDegree_t and RemoveZeroDegree_t: These structs are used to extract and remove zero-degree nodes from a tuple. They work by recursively iterating over the tuple and adding/removing nodes to/from a new tuple based on their degree.

4. DecrementDegrees_t: This struct is used to decrement the degree of nodes that depend on a given set of nodes. It works by recursively iterating over the tuple and decrementing the degree of any nodes that are in the Dependencies tuple.

5. AddSystemsToTuple_t: This struct is used to add the zero-degree nodes to the ExtractedSystems tuple. It works by recursively iterating over the tuple of zero-degree nodes and adding each node to the ExtractedSystems tuple.

Problem

The problem I'm facing is that the algorithm works fine for up to 15 types, but with 16 types, it exceeds the maximum recursion depth. I believe the recursion depth should be O(M), where M is the maximum degree count, so I'm not sure why it's failing with 16 types.

My questions are:

1. Why does this algorithm exceed the maximum recursion depth with 16
   types?
2. How can I modify it to handle more types?
3. Given the complexity of this approach, would it be advisable to
   adopt a simpler approach to achieve the same result? If so, what
   alternatives could be recommended?

Please take me easy, I'm new here

Source Code

You can also reproduce the probelm here: https://godbolt.org/z/T8cohdasr.

#include <tuple>
#include <iostream>
#include <type_traits>
#include <string_view>
template<typename SystemType, typename... DependencyTypes>
class SystemNode;
template<typename SystemType, typename... DependencyTypes>
class SystemNode<SystemType, std::tuple<DependencyTypes...>>
{
public:
using system = SystemType;
using dependencies = std::tuple<DependencyTypes...>;
};
template <typename System, typename Dependencies, size_t Degree>
struct NodeWithDegree 
{
using system = System;
using dependencies = Dependencies;
static constexpr size_t degree = Degree;
};
template <typename Node, size_t Degree>
struct ToNodeWithDegree
{
using type = NodeWithDegree<typename Node::system, typename Node::dependencies, Degree>;
};
template <typename Node, size_t Degree>
using ToNodeWithDegree_t = typename ToNodeWithDegree<Node, Degree>::type;
template <typename T, typename Tuple>
struct Contains;
template <typename T, typename... Us>
struct Contains<T, std::tuple<Us...>> : std::disjunction<std::is_same<T, Us>...> {};
template <typename T, typename... Us>
constexpr size_t Contains_v = Contains<T, Us...>::value;
template <typename Node, typename Nodes>
struct CountDependencies;
template <typename Node, typename First, typename... Rest>
struct CountDependencies<Node, std::tuple<First, Rest...>>
{
static constexpr size_t value = 
Contains_v<typename Node::system, typename First::dependencies> 
+ CountDependencies<Node, std::tuple<Rest...>>::value;
};
template <typename Node>
struct CountDependencies<Node, std::tuple<>>
{
static constexpr size_t value = 0;
};
template <typename... Nodes>
struct GraphWithDegrees
{
template<typename Node>
static constexpr size_t CountDependencies_v = CountDependencies<Node, std::tuple<Nodes...>>::value;
using type = std::tuple<ToNodeWithDegree_t<Nodes, CountDependencies_v<Nodes>>...>;
};
template <typename... Nodes>
using GraphWithDegrees_t = typename GraphWithDegrees<Nodes...>::type;
template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
struct ExtractZeroDegree;
template <typename FirstNode, typename... RestNodes, typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<ZeroDegreeNodes...>>
{
using type = std::conditional_t<
FirstNode::degree == 0,
typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes..., FirstNode>>::type,
typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes...>>::type
>;
};
template <typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<>, std::tuple<ZeroDegreeNodes...>>
{
using type = std::tuple<ZeroDegreeNodes...>; 
};
template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
using ExtractZeroDegree_t = typename ExtractZeroDegree<NodesWithDegrees, ZeroDegreeNodes>::type;
template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
struct RemoveZeroDegree;
template <typename FirstNode, typename... RestNodes, typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<NonZeroDegreeNodes...>>
{
using type = std::conditional_t<
FirstNode::degree == 0,
typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes...>>::type,
typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes..., FirstNode>>::type
>;
};
template <typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<>, std::tuple<NonZeroDegreeNodes...>>
{
using type = std::tuple<NonZeroDegreeNodes...>; 
};
template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
using RemoveZeroDegree_t = typename RemoveZeroDegree<NodesWithDegrees, NonZeroDegreeNodes>::type;
template <typename T, typename Tuple>
struct Prepend;
template <typename T, typename... Ts>
struct Prepend<T, std::tuple<Ts...>>
{
using type = std::tuple<T, Ts...>;
};
template <typename T, typename Tuple>
using Prepend_t = typename Prepend<T, Tuple>::type;
template <typename T, typename Tuple>
struct AddUnique;
template <typename T>
struct AddUnique<T, std::tuple<>>
{
using type = std::tuple<T>;
};
template <typename T, typename First, typename... Rest>
struct AddUnique<T, std::tuple<First, Rest...>>
{
using type = std::conditional_t<
std::is_same_v<T, First>,
std::tuple<First, Rest...>,
Prepend_t<First, typename AddUnique<T, std::tuple<Rest...>>::type>
>;
};
template <typename T, typename Tuple>
using AddUnique_t = typename AddUnique<T, Tuple>::type;
template <typename Tuple1, typename Tuple2>
struct AddUniqueElements;
template <typename First, typename... Rest, typename Tuple2>
struct AddUniqueElements<std::tuple<First, Rest...>, Tuple2>
{
using type = typename AddUniqueElements<std::tuple<Rest...>, AddUnique_t<First, Tuple2>>::type;
};
template <typename Tuple2>
struct AddUniqueElements<std::tuple<>, Tuple2>
{
using type = Tuple2;
};
template <typename Tuple1, typename Tuple2>
using AddUniqueElements_t = typename AddUniqueElements<Tuple1, Tuple2>::type;
template <typename Nodes>
struct CollectDependencies;
template <typename FirstNode, typename... RestNodes>
struct CollectDependencies<std::tuple<FirstNode, RestNodes...>>
{
using type = AddUniqueElements_t<
typename FirstNode::dependencies,
typename CollectDependencies<std::tuple<RestNodes...>>::type
>;
};
template <>
struct CollectDependencies<std::tuple<>>
{
using type = std::tuple<>;
};
template <typename... Nodes>
using CollectDependencies_t = typename CollectDependencies<Nodes...>::type;
template <typename NodesWithDegrees, typename Dependencies>
struct DecrementDegrees;
template <typename FirstNode, typename... RestNodes, typename... Dependencies>
struct DecrementDegrees<std::tuple<FirstNode, RestNodes...>, std::tuple<Dependencies...>>
{
using type = std::conditional_t<
Contains_v<typename FirstNode::system, std::tuple<Dependencies...>>,
Prepend_t<
NodeWithDegree<
typename FirstNode::system, 
typename FirstNode::dependencies, 
FirstNode::degree - 1
>, 
typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
>,
Prepend_t<
FirstNode, 
typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
>
>;
};
template <typename... Dependencies>
struct DecrementDegrees<std::tuple<>, std::tuple<Dependencies...>>
{
using type = std::tuple<>; 
};
template <typename NodesWithDegrees, typename Dependencies>
using DecrementDegrees_t = typename DecrementDegrees<NodesWithDegrees, Dependencies>::type;
template <typename NodesWithDegrees, typename ExtractedSystems>
struct AddSystemsToTuple;
template <typename FirstNode, typename... RestNodes, typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<FirstNode, RestNodes...>, std::tuple<ExtractedSystems...>>
{
using nextTuple = std::tuple<RestNodes...>;
using newExtractedSystems = std::tuple<typename FirstNode::system, ExtractedSystems...>;
using type = typename AddSystemsToTuple<nextTuple, newExtractedSystems>::type;
};
template <typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<>, std::tuple<ExtractedSystems...>>
{
using type = std::tuple<ExtractedSystems...>;
};
template <typename NodesWithDegrees, typename ExtractedSystems>
using AddSystemsToTuple_t = typename AddSystemsToTuple<NodesWithDegrees, ExtractedSystems>::type;
template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
struct TopologicalSort
{
using ZeroDegreeSystems = ExtractZeroDegree_t<SystemsWithDegrees>;
using NewExtractedSystems = AddSystemsToTuple_t<ZeroDegreeSystems, ExtractedSystems>;
using Dependencies = CollectDependencies_t<ZeroDegreeSystems>;
using RemainingSystems = RemoveZeroDegree_t<SystemsWithDegrees>;
using DecrementRemainingSystems = DecrementDegrees_t<RemainingSystems, Dependencies>;
using type = typename TopologicalSort<DecrementRemainingSystems, NewExtractedSystems>::type;
};
template <typename ExtractedSystems>
struct TopologicalSort<std::tuple<>, ExtractedSystems>
{
using type = ExtractedSystems;
};
template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
using TopologicalSort_t = typename TopologicalSort<SystemsWithDegrees, ExtractedSystems>::type;
template <typename T>
constexpr auto type_name() noexcept {
std::string_view name = "Error: unsupported compiler", prefix, suffix;
#ifdef __clang__
name = __PRETTY_FUNCTION__;
prefix = "auto type_name() [T = ";
suffix = "]";
#elif defined(__GNUC__)
name = __PRETTY_FUNCTION__;
prefix = "constexpr auto type_name() [with T = ";
suffix = "]";
#elif defined(_MSC_VER)
name = __FUNCSIG__;
prefix = "auto __cdecl type_name<";
suffix = ">(void) noexcept";
#else
static_assert(false, "Unsupported compiler!");
#endif
name.remove_prefix(prefix.size());
name.remove_suffix(suffix.size());
return name;
}
template <typename T>
void printSystem()
{
std::cout << type_name<T>() << '\n';
}
struct System1 {};
struct System2 {};
struct System3 {};
struct System4 {};
struct System5 {};
struct System6 {};
struct System7 {};
struct System8 {};
struct System9 {};
struct System10 {};
struct System11 {};
struct System12 {};
struct System13 {};
struct System14 {};
struct System15 {};
struct System16 {};
struct System17 {};
struct System18 {};
struct System19 {};
struct System20 {};
using Node1 = SystemNode<System1, std::tuple<>>;
using Node2 = SystemNode<System2, std::tuple<System1>>;
using Node3 = SystemNode<System3, std::tuple<System2>>;
using Node4 = SystemNode<System4, std::tuple<System3>>;
using Node5 = SystemNode<System5, std::tuple<System4>>;
using Node6 = SystemNode<System6, std::tuple<System5>>;
using Node7 = SystemNode<System7, std::tuple<System6>>;
using Node8 = SystemNode<System8, std::tuple<System7>>;
using Node9 = SystemNode<System9, std::tuple<System8>>;
using Node10 = SystemNode<System10, std::tuple<System9>>;
using Node11 = SystemNode<System11, std::tuple<System10>>;
using Node12 = SystemNode<System12, std::tuple<System11>>;
using Node13 = SystemNode<System13, std::tuple<System12>>;
using Node14 = SystemNode<System14, std::tuple<System13>>;
using Node15 = SystemNode<System15, std::tuple<System14>>;
using Node16 = SystemNode<System16, std::tuple<System15>>;
using Node17 = SystemNode<System17, std::tuple<System16>>;
using Node18 = SystemNode<System18, std::tuple<System17>>;
using Node19 = SystemNode<System19, std::tuple<System18>>;
using Node20 = SystemNode<System20, std::tuple<System19>>;
int main()
{
using tuple = GraphWithDegrees_t<
Node10, Node9, Node8, Node7, Node6, Node5, Node4, Node3, Node2, Node1, 
Node11, Node12, Node13, Node14, Node15, Node16, Node17, Node18, Node19, Node20
>;
using SortedTuple = TopologicalSort_t<tuple>;
printSystem<SortedTuple>();
return 0;
}

Output:

terminate called after throwing an instance of 'std::bad_alloc'
what():  std::bad_alloc```
</details>
# 答案1
**得分**: 4
您的编译器出现了内部错误/内存不足的情况。这并不是某种任意的嵌套模板实例化限制。
我在本地机器上成功编译了一个包含20个节点的版本。在使用gcc编译时大约需要20秒，使用clang编译时大约需要30秒。
然后我将节点数量增加到了50。编译过程使我的计算机（诚然，按今天的标准来看不是很强大）变得非常慢，大约20分钟后我中止了它。
因此，在实际应用中，将模板元编程推到如此远的程度可能并不是一个好主意。
<details>
<summary>英文:</summary>
Your compiler has an internal error/out of memory condition. It is not some kind of arbitrary nested template instantiation limit.
I was able to compile a version with 20 nodes on my machine locally. It took about 20 seconds with gcc and about 30 seconds with clang.
I then increased the number of nodes to 50. The compilation brought my computer (admittedly not very beefy by today&#39;s standards) to a crawl and I killed it after 20 minutes or so.
So in practice it&#39;s probably not a good idea to push template metaprogramming that far.
</details>