Reducing Boilerplate

Whilst it's common for dependency graph frameworks to use Trait Objects to combine multiple types in to a graph-like structure, Depends uses generic type-system trickery. Specifically, GATs.

Whilst this has low-level performance benefits, particularly for graphs with many edges, the cost is that types can become quite verbose.

Let's have a look at the type of the root node in the previous example:

// Oh dear lord...
Rc<
    DerivedNode<
        Dependency<
            Rc<
                DerivedNode<
                    TwoNumbersDep<
                        DerivedNode<
                            TwoNumbersDep<
                                DerivedNode<
                                    TwoNumbersDep<
                                        DerivedNode<
                                            TwoNumbersDep<
                                                InputNode<SomeNumber>,
                                                InputNode<SomeNumber>,
                                            >,
                                            Multiply,
                                            SomeNumber,
                                        >,
                                        DerivedNode<
                                            TwoNumbersDep<
                                                InputNode<SomeNumber>,
                                                InputNode<SomeNumber>,
                                            >,
                                            Subtract,
                                            SomeNumber,
                                        >,
                                    >,
                                    Add,
                                    SomeNumber,
                                >,
                                DerivedNode<
                                    Dependency<Rc<InputNode<SomeNumber>>>,
                                    Square,
                                    SomeNumber,
                                >,
                            >,
                            Multiply,
                            SomeNumber,
                        >,
                        // Even rustfmt gave up on us!
                        DerivedNode<Dependency<Rc<InputNode<SomeNumber>>>, Square, SomeNumber>,
                    >,
                    Subtract,
                    SomeNumber,
                >,
            >,
        >,
        Cube,
        AnotherNumber,
    >,
>

That's got a bit out of hand! We're experiencing the same issue that Futures have. By retaining the strict type information, the code is now the type. Every time we change the code, we change the type of the graph. This clearly presents a maintenance issue.

See Fasterthanlime's excellent in-depth article on futures for more on this particular topic.

Impl Trait to the rescue

Thankfully, Rust has a solution for this: impl Trait.

Instead of tracking the concrete type of the root node, we only need to specify the behaviour we want it to exhibit.

Furthermore, by only explicitly storing the root and input nodes, we eliminate the need to keep track of all intermediate derived node types. This approach drastically reduces the amount of boilerplate code, simplifying our program and making it more maintainable, while still preserving the performance benefits and safety guarantees of Rust's type system.

The end result is we can create a graph to store this struct like so:

struct Graph<R> {
    // Keep references to the input nodes so they can be updated.
    a: Rc<InputNode<SomeNumber>>,
    b: Rc<InputNode<SomeNumber>>,
    c: Rc<InputNode<SomeNumber>>,
    d: Rc<InputNode<SomeNumber>>,
    e: Rc<InputNode<SomeNumber>>,
    // Keep a reference to the root node so it can be resolved.
    cube_and_change_type: R
}

impl<R> Graph<R>
where
    // R must be a node which resolves to a reference to AnotherNumber.
    R: for<'a> Resolve<Output<'a> = NodeRef<'a, AnotherNumber>>,
{
    // We can only call this constructor with a root node which
    // resolves to the correct type.
    pub fn new(
        a: Rc<InputNode<SomeNumber>>,
        b: Rc<InputNode<SomeNumber>>,
        c: Rc<InputNode<SomeNumber>>,
        d: Rc<InputNode<SomeNumber>>,
        e: Rc<InputNode<SomeNumber>>,
        cube_and_change_type: R,
    ) -> Self {
        Self {
            a,
            b,
            c,
            d,
            e,
            cube_and_change_type,
        }
    }
}

Using that in practice then becomes:

// Create a new graph.
let graph = Graph::new(a, b, c, d, e, cube_and_change_type);

// We can now interact with the inputs and root node.
graph.b.update(-1).unwrap();

let output = graph.cube_and_change_type.resolve(&mut visitor).unwrap();
assert_eq!(output.value, -15625);

Note we can't create the graph inside one of its methods, as it must be able to infer a generic paramter R from the arguments provided. A helper function

fn create_graph(...) -> Graph<impl Resolve<...>>

can be useful here.