Building asynchronous `future` callback chain from compile-time dependency graph (DAG)

The easiest way is to start from the entry node of the graph, as if you were writing the code by hand. In order to solve the join problem, you can not use a recursive solution, you need to have a topological ordering of your graph, and then build the graph according to the ordering.

This gives the guarantee that when you build a node all of its predecessors have already been created.

To achieve this goal we can use a DFS, with reverse postordering.

Once you have a topological sorting, you can forget the original node IDs, and refer to nodes with their number in the list. In order to do that you need create a compile time map that allows to retrieve the node predecessors using the node index in the topological sorting instead of the node original node index.


EDIT: Following up on how to implement topological sorting at compile time, I refactored this answer.

To be on the same page I will assume that your graph looks like this:

struct mygraph
{
     template<int Id>
     static constexpr auto successors(node_id<Id>) ->
        list< node_id<> ... >; //List of successors for the input node

     template<int Id>
     static constexpr auto predecessors(node_id<Id>) ->
        list< node_id<> ... >; //List of predecessors for the input node

     //Get the task associated with the given node.
     template<int Id>
     static constexpr auto task(node_id<Id>);

     using entry_node = node_id<0>;
};

Step 1: topological sort

The basic ingredient that you need is a compile time set of node-ids. In TMP a set is also a list, simply because in set<Ids...> the order of the Ids matters. This means that you can use the same data structure to encode the information on whether a node as been visited AND the resulting ordering at the same time.

/** Topological sort using DFS with reverse-postordering **/
template<class Graph>
struct topological_sort
{
private:
    struct visit;

    // If we reach a node that we already visited, do nothing.
    template<int Id, int ... Is>
    static constexpr auto visit_impl( node_id<Id>,
                                      set<Is...> visited,
                                      std::true_type )
    {
        return visited;
    }

    // This overload kicks in when node has not been visited yet.
    template<int Id, int ... Is>
    static constexpr auto visit_impl( node_id<Id> node,
                                      set<Is...> visited,
                                      std::false_type )
    {
        // Get the list of successors for the current node
        constexpr auto succ = Graph::successors(node);

        // Reverse postordering: we call insert *after* visiting the successors
        // This will call "visit" on each successor, updating the
        // visited set after each step.
        // Then we insert the current node in the set.
        // Notice that if the graph is cyclic we end up in an infinite
        // recursion here.
        return fold( succ,
                     visited,
                     visit() ).insert(node);

        // Conventional DFS would be:
        // return fold( succ, visited.insert(node), visit() );
    }

    struct visit
    {
        // Dispatch to visit_impl depending on the result of visited.contains(node)
        // Note that "contains" returns a type convertible to
        // integral_constant<bool,x>
        template<int Id, int ... Is>
        constexpr auto operator()( set<Is...> visited, node_id<Id> node ) const
        {
            return visit_impl(node, visited, visited.contains(node) );
        }
    };

public:
    template<int StartNodeId>
    static constexpr auto compute( node_id<StartNodeId> node )
    {
        // Start visiting from the entry node
        // The set of visited nodes is initially empty.
        // "as_list" converts set<Is ... > to list< node_id<Is> ... >.
        return reverse( visit()( set<>{}, node ).as_list() );
    }
};

This algorithm with the graph from your last example (assuming A = node_id<0>, B = node_id<1>, etc.), produces list<A,B,C,D,E,F>.

Step 2: graph map

This is simply an adapter that modifies the Id of each node in your graph according to a given ordering. So assuming that previous steps returned list<C,D,A,B>, this graph_map would map the index 0 to C, index 1 to D, etc.

template<class Graph, class List>
class graph_map
{   
    // Convert a node_id from underlying graph.
    // Use a function-object so that it can be passed to algorithms.
    struct from_underlying
    { 
        template<int I>
        constexpr auto operator()(node_id<I> id) 
        { return node_id< find(id, List{}) >{}; }
    };

    struct to_underlying
    { 
        template<int I>
        constexpr auto operator()(node_id<I> id) 
        { return get<I>(List{}); }
    };

public:        
    template<int Id>
    static constexpr auto successors( node_id<Id> id )
    {
        constexpr auto orig_id = to_underlying()(id);
        constexpr auto orig_succ = Graph::successors( orig_id );
        return transform( orig_succ, from_underlying() );
    }

    template<int Id>
    static constexpr auto predecessors( node_id<Id> id )
    {
        constexpr auto orig_id = to_underlying()(id);
        constexpr auto orig_succ = Graph::predecessors( orig_id );
        return transform( orig_succ, from_underlying() );
    }

    template<int Id>
    static constexpr auto task( node_id<Id> id )
    {
        return Graph::task( to_underlying()(id) );
    }

    using entry_node = decltype( from_underlying()( typename Graph::entry_node{} ) );
};

Step 3: assemble the result

We can now iterate over each node id in order. Thanks to the way we built the graph map, we know that all the predecessors of I have a node id which is less than I, for every possible node I.

// Returns a tuple<> of futures
template<class GraphMap, class ... Ts>
auto make_cont( std::tuple< future<Ts> ... > && pred )
{
     // The next node to work with is N:
     constexpr auto current_node = node_id< sizeof ... (Ts) >();

     // Get a list of all the predecessors for the current node.
     auto indices = GraphMap::predecessors( current_node );

     // "select" is some magic function that takes a tuple of Ts
     // and an index_sequence, and returns a tuple of references to the elements 
     // from the input tuple that are in the indices list. 
     auto futures = select( pred, indices );

     // Assuming you have an overload of when_all that takes a tuple,
     // otherwise use C++17 apply.
     auto join = when_all( futures );

     // Note: when_all with an empty parameter list returns a future< tuple<> >,
     // which is always ready.
     // In general this has to be a shared_future, but you can avoid that
     // by checking if this node has only one successor.
     auto next = join.then( GraphMap::task( current_node ) ).share();

     // Return a new tuple of futures, pushing the new future at the back.
     return std::tuple_cat( std::move(pred),
                            std::make_tuple(std::move(next)) );         
}


// Returns a tuple of futures, you can take the last element if you
// know that your DAG has only one leaf, or do some additional 
// processing to extract only the leaf nodes.
template<class Graph>
auto make_callback_chain()
{
    constexpr auto entry_node = typename Graph::entry_node{};

    constexpr auto sorted_list = 
         topological_sort<Graph>::compute( entry_node );

    using map = graph_map< Graph, decltype(sorted_list) >;

    // Note: we are not really using the "index" in the functor here, 
    // we only want to call make_cont once for each node in the graph
    return fold( sorted_list, 
                 std::make_tuple(), //Start with an empty tuple
                 []( auto && tuple, auto index )
                 {
                     return make_cont<map>(std::move(tuple));
                 } );
}

Full live demo

Leave a Comment