Overview

Depends is a powerful Rust library for efficient, flexible incremental computation between arbitrary data.

The goal of the library is to provide the smallest possible API to produce high-performance, reliable, declarative dependency graph structures.

Key Features

Depends is:

Efficient: Designed to only recompute data affected by changes, significantly increasing performance.
Flexible: Easily establish dependencies on any arbitrary Rust types.
Declarative: Serialize run-time graphs to/from Graphviz specifications.
Testable: Build complex applications by composing small, testable units of logic.

This library is built with versatility in mind, ideal for domains where data from a variety of inputs frequently changes and computations need to be updated accordingly.

Key Concepts

Depends is built around several key concepts from graph theory and functional programming. Understanding these concepts will help you make the most of the library.

A Directed Acyclic Graph, or DAG, is a concept from graph theory. It's a collection of nodes and directed edges, where each edge has an orientation (it goes from one node to another), and there are no cycles (you cannot start at a node, follow the directed edges, and return to the starting node).

In Depends, the computation graph you define is a DAG. Each node in the graph represents a piece of data, and each edge represents a transformation of data from one node to another.

Input Nodes and Derived Nodes

The nodes in the Depends DAG are of two types:

Input Nodes: These are the leaves of the graph. They represent data inputs that come from outside the graph. These are often values provided by the user or from some external source.
Derived Nodes: These nodes represent data that's computed within the graph. A derived node's value is a function of the values of its dependencies (the nodes that have edges leading to it).

The Root node is a special derived node where the graph's output is read from. Graphs should only ever be resolved from the root node.

Purity and Determinism

A function is said to be pure if it always produces the same output when given the same input, and it has no side effects. That is, it doesn't alter any state outside the function or depend on any state that could change between function calls.

In Depends, it's essential that each transformation is a pure and deterministic function of its dependencies. This is what allows Depends to safely perform incremental computation. When the dependencies of a node haven't changed, Depends knows it doesn't need to re-compute that node. This guarantee of purity is a key to Depends's efficiency.

Getting Started

This guide is broken down in to three sections:

Values: Strongly typed data owned by a node in a graph.
Nodes: A wrapper for a value controlling its access and tracking dependencies.
Graphs: A collection of nodes and edges.

Let's walk through some simple code examples and core concepts of Depends!

Values

A Value is a stateful unit of data held within a dependency graph node. During execution, values will be prompted to recalculate their state if their dependencies change their values.

A Value is required to declare how it can be:

Hashed: Provide a single unique integer for its state (or indicate it can't be hashed).
Cleaned: Declare how to clean any transient state.

Use the #[derive(Value)] macro to make a struct compatible with the dependency graph.

use depends::derives::Value;

#[derive(Value, Hash)]
struct YourStruct {
    // ... your fields go here
}

The default behaviour of this type is to:

Hash all fields.
Not clean any transient state.

Hashing

All values in a dependency graph must provide a hash (a unique identifier) for their state, or indicate they can't be hashed. This is used to determine if whether a value has changed since the last time it was observed.

There are three ways to define a value's hashing behaviour:

1. Default: Requires the type to implement the Hash trait.

// This type implements `Hash`, therefore it can use the default behaviour.
#[derive(Value, Hash)]
struct DefaultBehaviour {
    data: i32,
}

2. Custom Hash: Annotate a field with the #[depends(hash)] attribute to manually manage the hashing behaviour.

// This node manually manages its hash value.
#[derive(Value)]
struct CustomHashStruct {
    // You could increment a counter here, for example.
    #[depends(hash)]
    hash_value: usize,
    // ... other fields go here.
}

3. Unhashable: Mark values that can't be hashed with the #[depends(unhashable)] attribute. This type will always appear dirty to any dependents, causing them to always recalculate their own state.

// This node will _always_ be considered dirty to its dependents.
#[derive(Value)]
#[depends(unhashable)]
struct UnhashableStruct {
    // ... your fields go here.
}

It's unlikely you'll need to use the unhashable attribute and this can greatly reduce the efficiency of computations. Most nodes can use a custom hash field instead.

Cleaning

By default, values in the Depends dependency graph do not perform any cleanup between graph calculations. This means any transient state being tracked will remain.

If you need to perform cleanup on a value, you can specify the #[depends(custom_clean)] attribute.

struct Post {
    id: i64,
    // ... your fields go here
}

// This node allows dependencies to iterate only values which have changed
// since the graph was last resolved.
#[derive(Value, Default)]
#[depends(custom_clean)]
struct Posts {
    // Keep track of all the posts we've seen.
    all_posts: HashMap<i64, Post>,
    // Track which data has changed since the last time we resolved this
    // node. Don't worry about how we populate this for now.
    changed_post_ids: Vec<i64>,
    #[depends(hash)]
    generation: usize,
}

impl Clean for Posts {
    fn clean(&mut self) {
        // We _must_ clean up any temporary state used to track changes.
        self.changed_post_ids.clear();
    }
}

impl Posts {
    // This public method can be called by any dependency of `Posts` to
    // iterate only the new/changed values.
    pub fn iter_changed(&self) -> impl Iterator<Item = &Post> + '_ {
        self.changed_post_ids.iter().map(|key| &self.all_posts[key])
    }
}

When this attribute is used, you are required to implement the Clean trait for the struct. The Clean trait contains a single method, clean, which should be implemented to reset any transient state being tracked by your struct.

This enables you to manually control the cleanup process between computations, ensuring that your transient state is always correctly managed.

Correct cleanup is vital to maintain the accuracy and efficiency of your computations.

Nodes

In a graph, a node represents a discrete unit of data or computation. In the context of the Depends library, nodes hold and manage a Value of a specific type. They can either be:

Input Nodes: Nodes which derive their Value's state from outside the graph.
Derived Nodes: Nodes which derive their Value's state from other nodes they depend on.

Input Nodes

In the context of a computation graph, Input Nodes are nodes that have no dependencies. These are commonly referred to as leaf nodes and their values are sourced from outside the graph.

UpdateInput

To facilitate a Value being used in an input node we need to implement the UpdateInput trait.

The simplest implementation can be seen below:

#[derive(Value, Hash)]
pub struct SomeNumber {
    pub value: i32,
}

impl UpdateInput for SomeNumber {
    type Update = i32;

    fn update_mut(&mut self, update: Self::Update) {
        // Simply replace the value with the update.
        self.value = update;
    }
}

It's now possible to create an InputNode from this data and interact with it by passing in updates:

// `input` is an `Rc`, so can be cloned and passed to dependents.
let input = InputNode::new(SomeNumber { value: 2 });

// The `update` method allows us to change the value of the node. It will
// fail if the node is currently being read/written to.
input.update(6).unwrap();

// The `value` method allows us to read the value of the node.
assert_eq!(input.value().unwrap().value, 6);

Complex Input Nodes

Often we'll want nodes to contain complex data structures and present efficient interfaces to any dependents.

Let's take the example we used earlier to demonstrate how to clean a node:

struct Post {
    id: i64,
    // ... your fields go here
}

// This node allows dependencies to iterate only values which have changed
// since the graph was last resolved.
#[derive(Value, Default)]
#[depends(custom_clean)]
struct Posts {
    // Keep track of all the posts we've seen.
    all_posts: HashMap<i64, Post>,
    // Track which data has changed since the last time we resolved this
    // node. Don't worry about how we populate this for now.
    changed_post_ids: Vec<i64>,
    #[depends(hash)]
    generation: usize,
}

impl Clean for Posts {
    fn clean(&mut self) {
        // We _must_ clean up any temporary state used to track changes.
        self.changed_post_ids.clear();
    }
}

impl Posts {
    // This public method can be called by any dependency of `Posts` to
    // iterate only the new/changed values.
    pub fn iter_changed(&self) -> impl Iterator<Item = &Post> + '_ {
        self.changed_post_ids.iter().map(|key| &self.all_posts[key])
    }
}

We can add the implementation of UpdateInput to this struct:

impl UpdateInput for Posts {
    // The type of data this node receives from _outside_ the graph.
    type Update = Post;

    fn update_mut(&mut self, post: Self::Update) {
        // Add the post ID to the list of changed posts.
        self.changed_post_ids.push(post.id);

        // Add the post to the map of posts.
        self.all_posts.insert(post.id, post);

        // Increment the generation counter.
        self.generation += 1;
    }
}

We're now able to provide Posts to an InputNode.

// We can now create an `InputNode` from our `Posts` struct.
let posts = InputNode::new(Posts::default());

// `posts` is an `Rc`, so after cloning it in to a graph, we can still
// get shared access to it.
posts.update(Post { id: 42 }).unwrap();

let value = posts.value().unwrap();
let changed: Vec<_> = value.iter_changed().collect();

assert_eq!(changed.len(), 1);
assert_eq!(changed[0].id, 42);

Derived Nodes

Derived nodes calculate their internal value from other values in the graph.

Any struct which derives Value can be used as a Derived Node. In order to create a derived node, however, we'll need to define:

An Operation: How to transform other nodes and values in to the derived node's internal value.
Dependencies: The required values of the operation. Implicitly, dependencies specify edges in the computation graph.

Let's look at these in more detail.

Operations

An Operation describes the dependencies of a Derived Node, and how those dependencies are used to update the internal Value.

In Depends, you define an Operation by implementing the UpdateDerived trait for a struct. This struct, marked with #[derive(Operation)], symbolizes the operation itself.

Here is an example of an Operation that squares a number:

#[derive(Value, Hash)]
pub struct SomeNumber {
    pub value: i32,
}

#[derive(Operation)]
pub struct Square;

impl UpdateDerived for Square {
    // `SingleRef` is short-hand for a shared reference to a single
    // dependency of type `SomeNumber`.
    type Input<'a> = SingleRef<'a, SomeNumber>;
    // `TargetMut` is short-hand for a mutable reference to `SomeNumber`.
    type Target<'a> = TargetMut<'a, SomeNumber>;

    fn update_derived(
        input: Self::Input<'_>,
        mut target: Self::Target<'_>,
    ) -> Result<(), EarlyExit> {
        target.value = input.value.pow(2);
        Ok(())
    }
}

Square is an Operation that takes a SingleRef to SomeNumber as input, and a TargetMut of SomeNumber as its target.

The update_derived method describes how to use the dependencies (the input) to update the internal value of the derived node (the target).

This operation will take a number and square it. In practice, operations can be any function that transforms the inputs into a new state for the target.

Early Exit

For some graphs, it may be desirable to exit early from an operation. This can be achieved by returning Err(EarlyExit) from the update_derived method.

#[derive(Operation)]
pub struct CheckAllIsOk;

impl UpdateDerived for CheckAllIsOk {
    type Input<'a> = SingleRef<'a, SomeNumber>;
    type Target<'a> = TargetMut<'a, SomeNumber>;

    fn update_derived(
        input: Self::Input<'_>,
        mut target: Self::Target<'_>,
    ) -> Result<(), EarlyExit> {
        if input.value >= 100 {
            return Err(EarlyExit::new("Things are a bit too spicy!"));
        }
        target.value = input.value;
        Ok(())
    }
}

This is particularly useful if you want to short-circuit a costly computation when it's clear that the result is no longer relevant.

Early exit will be triggered by the first value which returns an Err, therefore ordering is important.

Be aware that nodes after the node which prompts the exit will not receive data during the execution, and will miss any transient state (that which will be cleaned) which is cleared up by the time they are next updated.

Dependencies

In most real-world applications, you'll have nodes that depend on multiple other nodes. Depends allows you to define complex dependencies using the Dependencies derive macro.

Here's an example where an operation depends on two numbers and multiplies them:

// Outline the inner types of two nodes we wish to depend on.
#[derive(Dependencies)]
pub struct TwoNumbers {
    pub left: SomeNumber,
    pub right: SomeNumber,
}

#[derive(Operation)]
pub struct Multiply;

impl UpdateDerived for Multiply {
    // [TwoNumbersRef] is generated by the [Dependencies] macro, and
    // represents read-references to nodes containing the declared types.
    type Input<'a> = TwoNumbersRef<'a> where Self: 'a;
    type Target<'a> = TargetMut<'a, SomeNumber> where Self: 'a;

    fn update_derived(
        TwoNumbersRef { left, right }: TwoNumbersRef<'_>,
        mut target: TargetMut<'_, SomeNumber>,
    ) -> Result<(), EarlyExit> {
        target.value = left.value * right.value;
        Ok(())
    }
}

By marking TwoNumbers with #[derive(Dependencies)], you tell Depends that TwoNumbers is a set of dependencies. The Dependencies derive macro generates two new types for you: TwoNumbersDep and TwoNumbersRef.

Here's a table that shows the equivalent types for single and multiple dependencies:

	Dependency<A>	TwoNumbers
Constructor	`Dependency::<A>::new(a: A)`	`TwoNumbers::init(a: A, b: B)`
Initialised Type	`Dependency<A>`	`TwoNumbersDep<A, B>`
Reference Type	`SingleRef<'a, A>`	`TwoNumbersRef<'a>`

This table describes the equivalent constructors, initialised types, and reference types for single (Dependency<A>) and multiple dependencies (TwoNumbers). You can use TwoNumbersRef<'a> with any operation that requires two NumberValues. This allows you to build complex, flexible dependency graphs.

Checking Specific Dependency State

There are situations where it's useful to know which specific dependencies have caused update_mut to be called. For this reason, the is_dirty method is available on each dependency reference.

#[derive(Value, Hash)]
pub struct StuffToBuy {
    amount: i32,
    last_purchase_time: i64,
}

#[derive(Operation)]
pub struct CheckBankBalance;

#[derive(Dependencies)]
pub struct TimeAndMoney {
    pub time: i64,
    pub money: i32,
}

impl UpdateDerived for CheckBankBalance {
    type Input<'a> = TimeAndMoneyRef<'a> where Self: 'a;
    type Target<'a> = TargetMut<'a, StuffToBuy> where Self: 'a;

    fn update_derived(
        TimeAndMoneyRef { time, money }: Self::Input<'_>,
        mut target: Self::Target<'_>,
    ) -> Result<(), EarlyExit> {
        // Is dirty is a trait implemented on all dependencies to indicate
        // that the inner value of this node has changed since last observed.
        if !money.is_dirty() {
            // Time's always changing, we don't need to check it.
            return Ok(());
        }
        // It's been a while since we've bought anything and we've just been
        // paid.
        if time.value() - target.value().last_purchase_time > 24 * 60 * 60 {
            target.value_mut().last_purchase_time = *time.value();
            target.value_mut().amount = money.value() / 10;
        }
        Ok(())
    }
}

The most common is example is time. It's expected that no node uses methods such as Utc::now(), as this is a side-effect which will result in non-deterministic behaviour.

Instead, you should 'set' the time for the graph by providing it as an Input Node and creating edges to the nodes which require it.

Graphs

After defining our dependencies, operations and values, we're finally ready to construct a graph and resolve its output!

let input_1 = InputNode::new(SomeNumber { value: 6 });
let input_2 = InputNode::new(SomeNumber { value: 7 });

// Derived is the root node of this graph.
let derived = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&input_1), Rc::clone(&input_2)),
    Multiply,
    SomeNumber::default(),
);

// We'll need to create a visitor to resolve the graph. This keeps track
// of which nodes have been visited during depth-first traversal.
let mut visitor = GraphvizVisitor::new();

{
    // Let's put output in a scope so that all shared-references are dropped.
    let output = derived.resolve_root(&mut visitor).unwrap();
    assert_eq!(output.value, 42);
}
// Update one of the inputs.
input_1.update(60).unwrap();
{
    let output = derived.resolve_root(&mut visitor).unwrap();
    // The output should be updated on-demand.
    assert_eq!(output.value, 420);
}

Whilst the graph we've built so far is modest, and in no way justifies use of a dependency graph, we've demonstrated the basic building blocks of Depends. For applications which are likely to grow in complexity, this framework will allow us to maintain confidence in the correctness of our code.

Visualising with Graphviz

By enabling the graphviz feature, we can get a Graphviz representation of the graph:

// Use the special GraphvizVisitor to track the graph structure.
let mut visitor = GraphvizVisitor::new();

// Use `resolve` to _avoid_ clearing the visitor.
derived.resolve(&mut visitor).unwrap();

assert_eq!(
    visitor.render().unwrap(),
    r#"
digraph Dag {
  node_0 [label="SomeNumber"];
  node_1 [label="SomeNumber"];
  node_2 [label="SomeNumber"];
  node_0 -> node_2 [label="Multiply", class="TwoNumbersDep"];
  node_1 -> node_2 [label="Multiply", class="TwoNumbersDep"];
}
"#
    .trim()
);

This dot file format can be used with any Graphviz rendering tool to produce the following graph:

It's also possible to build graphs in Depends from the dot format. We'll show that off in a later chapter of this book.

Raising the Stakes

Now that we've got a basic understanding of how to structure logic with Depends, let's start ramping up the complexity.

We can use the special DiagnosticsVisitor and resolve to identify when nodes have their internal value calculated.

let a = InputNode::new(SomeNumber { value: 1 });
let b = InputNode::new(SomeNumber { value: 2 });
let c = InputNode::new(SomeNumber { value: 3 });
let d = InputNode::new(SomeNumber { value: 4 });
let e = InputNode::new(SomeNumber { value: 2 });

let a_times_b = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&a), Rc::clone(&b)),
    Multiply,
    SomeNumber::default(),
);

let d_minus_c = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&d), Rc::clone(&c)),
    Subtract,
    SomeNumber::default(),
);

let d_squared = DerivedNode::new(
    Dependency::new(Rc::clone(&d)),
    Square,
    SomeNumber::default(),
);

let e_squared = DerivedNode::new(
    Dependency::new(Rc::clone(&e)),
    Square,
    SomeNumber::default(),
);

let a_times_b_plus_c_minus_d = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&a_times_b), Rc::clone(&d_minus_c)),
    Add,
    SomeNumber::default(),
);

let times_e_squared = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&a_times_b_plus_c_minus_d), Rc::clone(&e_squared)),
    Multiply,
    SomeNumber::default(),
);

let minus_d_squared = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&times_e_squared), Rc::clone(&d_squared)),
    // Check out the `examples` directory to see the implementation of
    // these new operations.
    Subtract,
    SomeNumber::default(),
);

let cube_and_change_type = DerivedNode::new(
    Dependency::new(Rc::clone(&minus_d_squared)),
    Cube,
    // The graph can be constructed from all sorts of types.
    AnotherNumber::default(),
);

// This visitor will track how many derived nodes have their input
// recalculated.
let mut visitor = DiagnosticVisitor::new();

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

// We calculated all derived nodes.
assert_eq!(visitor.recalculated.len(), 8);

We've now created this pretty gnarly graph:

Incremental Computation

Let's demonstrate incremental computation in action. Suppose now we wanted to update the value of node e.

// Since we didn't `resolve_root` last time, clear the visitor manually.
visitor.clear();

// Updating E will only update the nodes which depend on it.
e.update(3).unwrap();

// Resolve our root node.
let output = cube_and_change_type.resolve(&mut visitor).unwrap();
assert_eq!(output.value, 1331);

// We've _visited_ all nodes.
assert_eq!(visitor.visitor.len(), 13);
// But only _recomputed_ the ones which are dependent on `e`.
// (Input nodes do not count towards this total).
assert_eq!(visitor.recalculated.len(), 4);

So, only 4 derived nodes were recomputed that time, saving us from all those costly math operations! A graphical representation of how this looks is below. The red nodes dirty or recomputed. The amber nodes provided cached values to their dependents. The green nodes were unchanged.

What would happen if we were to swap the values of a and b?

// Let's swap the values of `a` and `b`.
a.update(2).unwrap();
b.update(1).unwrap();

// The end result hasn't changed. 1 * 2 == 2 * 1.
let output = cube_and_change_type.resolve(&mut visitor).unwrap();
assert_eq!(output.value, 1331);

// Only 1 node was recalculated this time.
assert_eq!(visitor.recalculated.len(), 1);

We can see that only a single node had to be recalculated this time. Despite the node multiplying a and b being recalculated, its hash value remained the same. This resulted in its dependent nodes not considering their dependencies dirty, therefore returning cached values.

Organizing nodes to effectively cache values of nodes further up the dependency path can lead to significant performance gains, particularly in large dependency graphs with costly calculations.

A graphical representation of this is below.

Note that each Visitor will have its own Hasher, so using a different visitor will cause all nodes to be dirty. For best results, use a single visitor for the lifetime of a graph.

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.

Reducing More Boilerplate

Writing code to manually construct a dependency graph, connecting nodes to their dependencies, can quickly become tedious and error-prone, particularly for larger graphs. As shown in the example, each node and connection must be explicitly defined and linked, leading to a significant amount of boilerplate code.

let a = InputNode::new(SomeNumber { value: 1 });
let b = InputNode::new(SomeNumber { value: 2 });
let c = InputNode::new(SomeNumber { value: 3 });
let d = InputNode::new(SomeNumber { value: 4 });
let e = InputNode::new(SomeNumber { value: 2 });

let a_times_b = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&a), Rc::clone(&b)),
    Multiply,
    SomeNumber::default(),
);

let d_minus_c = DerivedNode::new(
    TwoNumbers::init(Rc::clone(&d), Rc::clone(&c)),
    Subtract,
    SomeNumber::default(),
);

...

Graphviz Deserialization

To simplify this process, there's the Graph derive macro. This takes a Graphviz definition of the graph, and generates the code to construct it.

// This is the graph generated by the previous example with slightly more
// descriptive node names.
#[derive(Graph)]
#[depends(
    digraph MyDag {
        a [label="SomeNumber"];
        b [label="SomeNumber"];
        c [label="SomeNumber"];
        d [label="SomeNumber"];
        e [label="SomeNumber"];
        a_times_b [label="SomeNumber"];
        a -> a_times_b [label="Multiply", class="TwoNumbersDep"];
        b -> a_times_b [label="Multiply", class="TwoNumbersDep"];
        d_minus_c [label="SomeNumber"];
        d -> d_minus_c [label="Subtract", class="TwoNumbersDep"];
        c -> d_minus_c [label="Subtract", class="TwoNumbersDep"];
        d_squared [label="SomeNumber"];
        d -> d_squared [label="Square"];
        e_squared [label="SomeNumber"];
        e -> e_squared [label="Square"];
        a_times_b_plus_c_minus_d [label="SomeNumber"];
        a_times_b -> a_times_b_plus_c_minus_d [label="Add", class="TwoNumbersDep"];
        d_minus_c -> a_times_b_plus_c_minus_d [label="Add", class="TwoNumbersDep"];
        times_e_squared [label="SomeNumber"];
        a_times_b_plus_c_minus_d -> times_e_squared [label="Multiply", class="TwoNumbersDep"];
        e_squared -> times_e_squared [label="Multiply", class="TwoNumbersDep"];
        minus_d_squared [label="SomeNumber"];
        times_e_squared -> minus_d_squared [label="Subtract", class="TwoNumbersDep"];
        d_squared -> minus_d_squared [label="Subtract", class="TwoNumbersDep"];
        cube_and_change_type [label="AnotherNumber"];
        minus_d_squared -> cube_and_change_type [label="Cube"];
    }
)]
pub struct DagCreator;

The macro generates the type MyDag<R>, similarly to the previous example. This graph can be created by passing the initial values for each of the nodes to the method attached to DagCreator.

// Provide initial values for all of the nodes.
let my_dag = DagCreator::create_my_dag(
    SomeNumber { value: 1 },
    SomeNumber { value: 2 },
    SomeNumber { value: 3 },
    SomeNumber { value: 4 },
    SomeNumber { value: 2 },
    SomeNumber::default(),
    SomeNumber::default(),
    SomeNumber::default(),
    SomeNumber::default(),
    SomeNumber::default(),
    SomeNumber::default(),
    SomeNumber::default(),
    AnotherNumber::default(),
);

let mut visitor = HashSetVisitor::new();

// The graph implements `Resolve`
{
    let output = my_dag.resolve_root(&mut visitor).unwrap();
    assert_eq!(output.value, -64);
}

// There are accessor methods to update inputs
my_dag.update_e(3).unwrap();

let output = my_dag.resolve_root(&mut visitor).unwrap();
assert_eq!(output.value, 1331);

Send-ability

Another benefit of using the Graph derive macro is that it will safely implement Send with unsafe for the given graph. This is a requirement for use in most async environments, such as Tokio.

Despite the fact that it uses Rc and RefCell internally, the Graph is safe to Send because it gives no access to the Rc types created, and moves all of them at once when being sent to another thread.

An example of this can be seen below:

// We can move the graph to other threads, despite the fact that it holds
// `Rc`s. This is safe because they are private, never cloned until dropped
// and always sent at the _same_ time.
let (my_dag, mut visitor) = std::thread::spawn(|| {
    // The graph provides a safe API for updating all input nodes.
    my_dag.update_c(10).unwrap();
    my_dag.update_b(6).unwrap();
    {
        let output = my_dag.resolve_root(&mut visitor).unwrap();
        assert_eq!(output.value, -4096);
    }
    (my_dag, visitor)
})
    .join()
    .unwrap();

my_dag.update_a(3).unwrap();

let output = my_dag.resolve_root(&mut visitor).unwrap();
assert_eq!(output.value, 778688);

Incremental Computation with Depends