DAG#

Problem Statement#

In Version 0, we explored how to utilise templates to compose operations at compile-time, along with the pros and cons of virtual vs templates.

Ultimately, this library is about C++ and templating. virtual is akin to inheritance, and its patterns can be found in other languages. Hence, focus on the compile-time variant!

Suppose we want to compose N operations:

using Pipeline = A<B<C<D<E<>>>>>;

Immediately, two problems are apparent:

1. Poor Ergonomics: The nesting of classes in template arguments is extremely prone to human error. Adding or removing a node requires careful matching of the angle brackets!
2. Obscured Data Flow: In a simple pipeline like this, reading left-to-right is simple enough. But eventually, when multiple control paths are introduced, the nested structure obscures the data flow.

Hence, what we really want is an intuitive interface:

using Pipeline = Graph<A<>, B<>, C<>, D<>, E<>>;

This clearly expresses: “data flows through A, then B, then…”

Using a more complex example: Suppose we have a Router with different Routes (akin to a switch in C++)

using HandleFoo = Graph<A<>, B<>>;
using HandleBar = Graph<C<>, D<>>;

using Pipeline = Graph<Router<
  Route<EventFoo, HandleFoo>,
  Route<EventBar, HandleBar>
  >,
  E<>
>;

using HandleFoo = A<B<>>;
using HandleBar = C<D<>>;

// TBH I do not even know how to express it with nested templates LOL.
// The Router needs to somehow wrap the Routes, AND chain to E<>...
using Pipeline = Router<
  Route<EventFoo, HandleFoo>,
  Route<EventBar, HandleBar>
>; // where do I even put E<>?

Template Rebinding#

The core challenge is converting the flattened list of lists Graph<A<>, B<>, ...> (note the tree-like recursion!) into the nested A<B<...>> at compile-time.

This is achieved through template rebinding! It’s a fairly common metaprogramming technique (found in Boost libraries too!) that recursively transforms type hierarchies.

Understanding the Node Structure#

A Node (or Stage) in the Graph/Pipeline is merely a struct with a process method.

First, let’s look at (simplified) nodes:

struct Successor {};

template <typename Then = Successor>
struct PassThrough : Then {
  template <typename... Args>
  auto process(Args&&... args) {
    return Then::process(std::forward<Args>(args)...);
  }
};

struct Sink {
  template <typename... Args>
  void process(Args&&...) {
    return;
  }
};

Each (internal) node:

• Takes a template parameter Then representing the next node in the chain.
• Inherits from Then to form a chain of types.
• Implements process() which delegates to the next node via Then::process().

Nodes can be classified into two categories:

• Internal Nodes: Class templates deriving from Successor (e.g., PassThrough<>).
• Terminal Nodes: Plain classes that do NOT derive from Successor (e.g., Sink).

namespace meta {

template <typename T>
concept Internal = std::is_class_v<T> && std::is_base_of_v<Successor, T>;

template <typename T>
concept Terminal = std::is_class_v<T> && !std::is_base_of_v<Successor, T>;

template <typename T>
concept NodeLike = Internal<T> || Terminal<T>;

} // namespace meta

Rebind#

The Rebind template performs a search-and-replace operation on type hierarchies:

template <typename Pattern, typename Replacement, typename Target>
using Rebind = typename detail::RebindImpl<Pattern, Replacement, Target>::Type;

In plain English (:>): “In Target (a Class Template), find all occurrences of Pattern and replace them with Replacement.”

Rebind Implementation#

The rebinding works through template specialisation:

// Base case: Target doesn't match Pattern, return as-is.
template <typename Pattern, typename Replacement, typename Target>
struct RebindImpl {
  using Type = Target;
};

// Match found: Replace Pattern with Replacement.
template <typename Pattern, typename Replacement>
struct RebindImpl<Pattern, Replacement, Pattern> {
  using Type = Replacement;
};

// Recursive case: Target is a class template, recurse into its arguments.
template <typename Pattern,
          typename Replacement,
          template <typename...> class Target,
          typename... Args>
struct RebindImpl<Pattern, Replacement, Target<Args...>> {
  using Type = Target<typename RebindImpl<Pattern, Replacement, Args>::Type...>;
};

When Target is a template instantiation like: PassThrough<Successor>, we decompose it into:

• The template itself: PassThrough.
• Its arguments: Successor.

We then recursively apply Rebind to each argument, rebuilding the type with transformed arguments.

Building the Graph#

The Graph implementation then uses Rebind to chain nodes together:

template <typename... Nodes>
struct Graph : GraphImpl<Nodes...>::Type {
  // Implementation inherits from the fully constructed graph
};

Looking at GraphImpl which contains the core logic:

template <typename... Nodes>
struct GraphImpl;

// Base case: Graph is a single, terminal node.
template <typename Leaf>
struct GraphImpl<Leaf> {
  using Type = Leaf;
};

// Recursive case: Process Head, recurse on Tail.
template <typename Head, typename... Tail>
struct GraphImpl<Head, Tail...> {
  // Magic happens here!
  // We rebind the ::Type of this Node (Head) to that of the Rebind-ed Tail.
  using Type = Rebind<Successor, typename GraphImpl<Tail...>::Type, Head>;
};

Step-by-Step Trace#

Tracing Graph<A<>, B<>, Sink> (showing default template arguments explicitly as A<Successor>, B<Successor>):

1. Process Head A<Successor> with Tail B<Successor>, Sink.

// Pattern = Successor
// Replacement = GraphImpl<B<Successor>, Sink>::Type (i.e., rest of the graph)
// Target = A<Successor>
GraphImpl<A<Successor>, B<Successor>, Sink>::Type
  = Rebind<Successor, GraphImpl<B<Successor>, Sink>::Type, A<Successor>>

At this point, we need to evaluate GraphImpl<B<Successor>, Sink>::Type.

2. Recurse into Tail. Process Head B<Successor> with Tail Sink:

GraphImpl<B<Successor>, Sink>::Type
  = Rebind<Successor, GraphImpl<Sink>::Type, B<Successor>>
  = Rebind<Successor, Sink, B<Successor>> // Base case: GraphImpl<Sink>::Type = Sink

3. Apply Rebind:

Rebind<Successor, Sink, B<Successor>>

This matches the recursive case earlier! B<Successor> is our Target, a class template with arguments.

Decomposing:

• Template: B
• Arguments: Successor

Now, recursively rebind the arguments:

B<typename RebindImpl<Successor, Sink, Successor>::Type...>
  = B<Sink> // Pattern matched! Successor replaced with Sink

4. Unwinding from innermost to outermost Rebind:

GraphImpl<A<Successor>, B<Successor>, Sink>::Type
  = Rebind<Successor, B<Sink>, A<Successor>>

Again, this matches the recursive case. Decomposing A<Successor>:

• Template: A
• Arguments: Successor

Recursively rebind:

A<typename RebindImpl<Successor, B<Sink>, Successor>::Type...>
  = A<B<Sink>> // Pattern match! Successor replaced with B<Sink>

Visualising the Stack:

Input:  Graph<A<>, B<>, Sink>
        |
Step 1: GraphImpl recurse, process rightmost first
        Sink (terminal, base case)
        |
Step 2: B<> gets its Successor replaced with Sink
        B<Successor> -> B<Sink>
        |
Step 3: A<> gets its Successor replaced with B<Sink>
        A<Successor> -> A<B<Sink>>
        |
Output: A<B<Sink>>

How/Why this Works#

This works for a multitude of reasons:

1. Default Template Arguments: Internal nodes default their Then parameter to Successor, giving us a consistent placeholder to Rebind.
2. Recursive Rebinding: Rebind then traverses the entire type hierarchy, finding and replacing all Successor placeholders at any depth.
3. Right-to-Left Construction: The recursion then unwinds, processing the nodes from innermost-to-outermost (i.e., right-to-left, tail-to-head), building the nested structure naturally.

Extended Example with Router#

I haven’t explained Router yet (at least, not fully! :D). Speedrunning!

Router is a little special in that it is composed of Nodes.

template <auto EventV, typename Node>
struct Route : Node {
  // Route inherits from Node
};

template <typename... Routes>
struct Router : Routes... {
  // Router inherits from all Routes
};

So, Router itself does not have a Then parameter. It only inherits from its Routes. To make Router chainable in a Graph, we then give each Route a Then parameter, by giving it a Graph as its Node argument:

using HandleFoo = Graph<A<>, B<>>;  // A<B<Successor>> - still open for chaining!
using HandleBar = Graph<C<>, D<>>;  // C<D<Successor>>

using Pipeline = Graph<
  PassThrough<>,
  Router<
    Route<EventFoo, HandleFoo>,  // Route inherits from A<B<Successor>>, inheriting Then parameter!
    Route<EventBar, HandleBar>   // Route inherits from C<D<Successor>>
  >,
  Sink  // Terminal
>;

When rebinding:

1. GraphImpl<Router<...>, Sink>::Type.
2. Router<...> is a class template with arguments.
3. The Rebind invocation looks like:

Rebind<Successor, Sink,
      Router<
        Route<EventFoo, A<B<Successor>>>,
        Route<EventBar, C<D<Successor>>>
        >
      >

4. Which then produces the nested structure:

Router<
  Route<EventFoo, A<B<Sink>>>,
  Route<EventBar, C<D<Sink>>>
>

Rebind traverses into the Router’s template arguments (the Routes), and within each Route’s template arguments (the Nodes), finds and replaces all Successor placeholders recursively!

Conclusion#

Template rebinding transforms an intuitive, flat syntax into a the nested type hierarchy. By leverage C++‘s template metaprogramming extensively, we get:

• Ergonomic API: Graph<A<>, B<>, C<>> is clear and maintainable.
• Zero Cost: No runtime overhead (as explained in V0).
• Type Safety: Invalid node combinations are caught by the Compiler, rather than failing at runtime, possibly catastrophically.
• Composability: Functional-Programming-like!

All made possible by Rebind!