Dependency Graph Store

To do incremental building, we need to keep track of all files, tasks, their dependencies, and task outputs, in a dependency graph. This will be the responsibility of the Store data structure. Context implementations will use methods on Store to query and mutate the dependency graph. In other words, Store encapsulates the dependency graph.

However, writing a dependency graph data structure is outside of the scope of this tutorial, so we will be using the pie_graph library which we prepared exactly for this use case. The graph from this library is a directed acyclic graph (DAG), meaning that edges are directed and there may be no cycles in edges, as that would prohibit topological orderings.

Add the pie_graph dependency to pie/Cargo.toml:

Store basics

Add the store module to pie/src/lib.rs:

This module is private, as users of the library should not interact with the store. Only Context implementations will use the store.

Create the pie/src/store.rs file and add the following to get started:

use std::path::{Path, PathBuf};

use pie_graph::{DAG, Node};

use crate::dependency::{Dependency, FileDependency, TaskDependency};
use crate::Task;

/// Stores files and tasks, and their dependencies, in a DAG (directed acyclic graph). Provides operations to mutate
/// and query this graph.
pub struct Store<T, O> {
  graph: DAG<NodeData<T, O>, Dependency<T, O>>,
}

#[derive(Debug)]
enum NodeData<T, O> {
  File(PathBuf),
  Task {
    task: T,
    output: Option<O>,
  },
}

impl<T: Task> Default for Store<T, T::Output> {
  fn default() -> Self {
    Self {
      graph: DAG::default(),
    }
  }
}

The Store is generic over tasks T and their outputs O, like we have done before with Dependency.

The DAG type from pie_graph represents a DAG with nodes and edges, and data attached to those nodes and edges. The nodes in our graph are either files or tasks, and the edges are dependencies.

The first generic argument to DAG is the type of data to attach to nodes, which is NodeData<T, O> in our case. Because nodes can be files or tasks, NodeData<T, O> enumerates these, storing the path for files, and the task along with its output for tasks. We store file paths as PathBuf, which is the owned version of Path (similar to String being the owned version of str). The task output is stored as Option<O> because we can add a task to the graph without having executed it, so we don’t have its output yet.

The second argument is the type of data to attach to edges, which is Dependency<T, O>, using the Dependency enum we defined earlier.

We implement Default for the store to initialize it.

Graph nodes

A node in DAG is represented by a Node, which is a transparent identifier (sometimes called a handle) that points to the node and its data. We can create nodes in the graph, and then query attached data (NodeData) given a node. So DAG allows us to go from Node to a PathBuf and task T through attached NodeData.

However, we want each unique file and task to be represented by a single unique node in the graph. We need this for incrementality so that if the build system encounters the same task twice, we can find the corresponding task node in the graph the second time, check if it is consistent, and return its output if it is.

To ensure unique nodes, we need to maintain the reverse mapping from PathBuf and T to Node ourselves, which we will do with HashMaps. This is also the reason for the Eq and Hash trait bounds on the Task trait, so we can use them as keys in HashMaps.

Change pie/src/store.rs to add hash maps to map between these things:

To prevent accidentally using a file node as a task node, and vice versa, change pie/src/store.rs to add specific types of nodes:

The FileNode and TaskNode types are newtypes that wrap a Node into a specific type of node. The Borrow implementations will make subsequent code a bit more concise by automatically converting &FileNode and &TaskNodes to &Nodes.

Now we will add methods create nodes and to query their attached data. Add the following code to pie/src/store.rs:

impl<T: Task> Store<T, T::Output> {
  /// Gets the file node for `path`, or creates a file node by adding it to the dependency graph.
  pub fn get_or_create_file_node(&mut self, path: impl AsRef<Path>) -> FileNode {
    let path = path.as_ref();
    if let Some(file_node) = self.file_to_node.get(path) {
      *file_node
    } else {
      let node = self.graph.add_node(NodeData::File(path.to_path_buf()));
      let node = FileNode(node);
      self.file_to_node.insert(path.to_path_buf(), node);
      node
    }
  }
  /// Gets the path for `node`.
  ///
  /// # Panics
  ///
  /// Panics if `node` was not found in the dependency graph.
  #[allow(dead_code)]
  pub fn get_file_path(&self, node: &FileNode) -> &PathBuf {
    let Some(NodeData::File(path)) = self.graph.get_node_data(node) else {
      panic!("BUG: node {:?} was not found in the dependency graph", node);
    };
    path
  }

  /// Gets the task node for `task`, or creates a task node by adding it to the dependency graph.
  pub fn get_or_create_task_node(&mut self, task: &T) -> TaskNode {
    if let Some(node) = self.task_to_node.get(task) {
      *node
    } else {
      let node = self.graph.add_node(NodeData::Task {
        task: task.clone(),
        output: None,
      });
      let node = TaskNode(node);
      self.task_to_node.insert(task.clone(), node);
      node
    }
  }
  /// Gets the task for `node`.
  ///
  /// # Panics
  ///
  /// Panics if `node` was not found in the dependency graph.
  pub fn get_task(&self, node: &TaskNode) -> &T {
    let Some(NodeData::Task { task, .. }) = self.graph.get_node_data(node) else {
      panic!("BUG: node {:?} was not found in the dependency graph", node);
    };
    task
  }
}

The get_or_create_file_node method creates file nodes. When we want to go from a file path (using impl AsRef<Path>) to a FileNode, either we have already added this file path to the graph and want to get the FileNode for it, or we have not yet added it to the graph yet and should add it. The former is handled by the if branch in get_or_create_file_node, where we just retrieve the FileNode from the file_to_node hash map. The latter is handled by the else branch where we add the node to the graph with graph.add_node which attaches the NodeData::File data to the node, and then returns a FileNode which we insert into the file_to_node map.

The get_file_path method does the inverse. We get the attached data given a node, and extract the file path from it.

Note that we are using panic! here to indicate that invalid usage of this method is an unrecoverable programming error that should not occur. Returning an Option<&PathBuf> makes no sense here, as the caller of this method has no way to recover from this. Because this is not an end-user-facing API (store module is private), we control all the calls to this method, and thus we are responsible for using these methods in a valid way. Therefore, when we call these methods, we should document why it is valid (if this is not immediately obvious), and we need to test whether we really use it in a valid way.

We’re also documenting the panics in a # Panics section in the documentation comment, as is common practice in Rust.

We implement similar methods for task nodes in get_or_create_task_node and get_task.

Task outputs

When we do not need to execute a task because it is consistent, we still need to return its output. Therefore, we store the task output in NodeData::Task and add methods to query and manipulate task outputs. Add the following code to pie/src/store.rs:

impl<T: Task> Store<T, T::Output> {
  /// Checks whether task `node` has an output. Returns `false` if `node` does not have an output.
  ///
  /// # Panics
  ///
  /// Panics if `node` was not found in the dependency graph.
  pub fn task_has_output(&self, node: &TaskNode) -> bool {
    let Some(NodeData::Task { output, .. }) = self.graph.get_node_data(node) else {
      panic!("BUG: node {:?} was not found in the dependency graph", node);
    };
    output.is_some()
  }
  /// Gets the output for task `node`.
  ///
  /// # Panics
  ///
  /// Panics if `node` was not found in the dependency graph, or if the task has no output.
  pub fn get_task_output(&self, node: &TaskNode) -> &T::Output {
    let Some(NodeData::Task { output: Some(output), .. }) = self.graph.get_node_data(node) else {
      panic!("BUG: node {:?} was not found in the dependency graph, or does not have an output", node);
    };
    output
  }
  /// Sets the output for task `node` to `new_output`.
  ///
  /// # Panics
  ///
  /// Panics if task `node` was not found in the dependency graph.
  pub fn set_task_output(&mut self, node: &TaskNode, new_output: T::Output) {
    let Some(NodeData::Task { output, .. }) = self.graph.get_node_data_mut(node) else {
      panic!("BUG: node {:?} was not found in the dependency graph", node);
    };
    output.replace(new_output);
  }
}

The task_has_output, get_task_output, and set_task_output methods manipulate task outputs in NodeData::Task.

Again, we are using panics here to indicate unrecoverable programming errors.

Dependencies

Now we need methods to query and manipulate dependencies. The edges in the graph are dependencies between tasks and files. Tasks can depend on other tasks and files, but there are no dependencies between files. An edge does not have its own dedicated representation, and is simply represented by two nodes: the source node and the destination node of the edge.

Add the following code to pie/src/store.rs:

impl<T: Task> Store<T, T::Output> {
  /// Get all dependencies of task `src`.
  ///
  /// # Panics
  ///
  /// Panics in development builds if `src` was not found in the dependency graph.
  pub fn get_dependencies_of_task<'a>(&'a self, src: &'a TaskNode) -> impl Iterator<Item=&'a Dependency<T, T::Output>> + 'a {
    debug_assert!(self.graph.contains_node(src), "BUG: node {:?} was not found in the dependency graph", src);
    self.graph.get_outgoing_edge_data(src)
  }
  /// Add a file require `dependency` from task `src` to file `dst`.
  ///
  /// # Panics
  ///
  /// Panics if `src` or `dst` were not found in the dependency graph, or if a cycle is created by adding this dependency.
  pub fn add_file_require_dependency(&mut self, src: &TaskNode, dst: &FileNode, dependency: FileDependency) {
    match self.graph.add_edge(src, dst, Dependency::RequireFile(dependency)) {
      Err(pie_graph::Error::NodeMissing) => panic!("BUG: source node {:?} or destination node {:?} was not found in the dependency graph", src, dst),
      Err(pie_graph::Error::CycleDetected) => panic!("BUG: cycle detected when adding file dependency from {:?} to {:?}", src, dst),
      _ => {},
    }
  }
  /// Adds a task require `dependency` from task `src` to task `dst`.
  ///
  /// # Errors
  ///
  /// Returns `Err(())` if adding this dependency to the graph creates a cycle.
  ///
  /// # Panics
  ///
  /// Panics if `src` or `dst` were not found in the dependency graph.
  pub fn add_task_require_dependency(&mut self, src: &TaskNode, dst: &TaskNode, dependency: TaskDependency<T, T::Output>) -> Result<(), ()> {
    match self.graph.add_edge(src, dst, Dependency::RequireTask(dependency)) {
      Err(pie_graph::Error::NodeMissing) => panic!("BUG: source node {:?} or destination node {:?} was not found in the dependency graph", src, dst),
      Err(pie_graph::Error::CycleDetected) => Err(()),
      _ => Ok(()),
    }
  }
}

The get_dependencies_of_task method gets the dependencies (edge data of outgoing edges) of a task, and returns it as an iterator (which is empty if task has no dependencies). This method needs explicit lifetime annotations due to the signature of get_outgoing_edge_data and the way we return an iterator using impl Iterator<.... We’re using debug_assert! here to trigger a panic indicating an unrecoverable programming error only in development mode, because this check is too expensive to run in release (optimized) mode.

The add_file_require_dependency method adds a file dependency. Adding an edge to the graph can result in cycles, which are not allowed in a directed acyclic graph (DAG). Therefore, graph.add_edge can return an Err indicating that there is a cycle. In case of files, this cannot happen because files do not have outgoing dependencies, and the API enforces this by never taking a FileNode as a source (src) of an edge.

Tasks can depend on other tasks, so they can create cycles. In add_task_require_dependency, we propagate the cycle detected error (by returning Err(())) to the caller because the caller has more information to create an error message for the user that made a cyclic task dependency.

Resetting tasks

Finally, when we determine that a task is inconsistent and needs to be executed, we first need to remove its output and remove its outgoing dependencies, as those will interfere with incrementality when not removed. We do NOT want to remove incoming dependencies, as that would remove dependencies from other tasks to this task, which breaks incrementality, so we can’t just remove and re-add the task to the graph. Add the reset_task method that does this to pie/src/store.rs:

impl<T: Task> Store<T, T::Output> {
  /// Reset task `src`, removing its output and removing all its outgoing dependencies.
  ///
  /// # Panics
  ///
  /// Panics if task `src` was not found in the dependency graph.
  pub fn reset_task(&mut self, src: &TaskNode) {
    if let Some(NodeData::Task { output, .. }) = self.graph.get_node_data_mut(src) {
      *output = None;
    } else {
      panic!("BUG: node {:?} was not found in the dependency graph", src);
    }
    self.graph.remove_outgoing_edges_of_node(src);
  }
}

This will reset the task output back to None, and remove all outgoing edges (dependencies).

Tests

Now we’ve implemented everything we need for implementing the top-down context, but first we will write some tests.

Testing file mapping

Add the following code to pie/src/store.rs for testing the file mapping:

#[cfg(test)]
mod test {
  use crate::Context;
  use crate::stamp::{FileStamper, OutputStamper};

  use super::*;

  /// Task that returns its owned string. Never executed, just used for testing the store.
  #[derive(Clone, PartialEq, Eq, Hash, Debug)]
  struct StringConstant(String);

  impl StringConstant {
    pub fn new(string: impl Into<String>) -> Self { Self(string.into()) }
  }

  impl Task for StringConstant {
    type Output = String;
    fn execute<C: Context<Self>>(&self, _context: &mut C) -> Self::Output {
      self.0.clone()
    }
  }

  #[test]
  fn test_file_mapping() {
    let mut store: Store<StringConstant, String> = Store::default();

    let path_a = PathBuf::from("hello.txt");
    let node_a = store.get_or_create_file_node(&path_a);
    assert_eq!(node_a, store.get_or_create_file_node(&path_a)); // Same node
    assert_eq!(&path_a, store.get_file_path(&node_a)); // Same file path

    let path_b = PathBuf::from("world.txt");
    let node_b = store.get_or_create_file_node(&path_b);
    assert_eq!(node_b, store.get_or_create_file_node(&path_b));
    assert_eq!(&path_b, store.get_file_path(&node_b));

    assert_ne!(node_a, node_b); // Different nodes
  }

  #[test]
  #[should_panic]
  fn test_file_mapping_panics() {
    let mut fake_store: Store<StringConstant, String> = Store::default();
    let fake_node = fake_store.get_or_create_file_node("hello.txt");
    let store: Store<StringConstant, String> = Store::default();
    store.get_file_path(&fake_node);
  }
}

We create a simple task StringConstant because we need a Task implementation to test Store, as Store is generic over a Task type. We will never execute it because Store does not execute tasks.

Test test_file_mapping checks whether the file node mapping works as expected:

• get_or_create_file_node calls with the same path should produce the same FileNode.
• get_or_create_file_node calls with different paths should produce different FileNodes.

This works because "hello.txt" and "world.txt" are different paths, thus their Eq and Hash implementations ensure they get separate spots in the file_to_node hash map.

Test test_file_mapping_panics triggers the panic in get_file_path by creating a FileNode with a “fake store”, and then using that rogue file node in another store. While it is unlikely that we will make this mistake when using Store, it is good to confirm that this panics.

Testing task mapping

Test the task mapping by inserting the following code into the test module (before the last }):

  #[test]
  fn test_task_mapping() {
    let mut store = Store::default();

    let task_a = StringConstant::new("Hello");
    let node_a = store.get_or_create_task_node(&task_a);
    assert_eq!(node_a, store.get_or_create_task_node(&task_a)); // Same node
    assert_eq!(&task_a, store.get_task(&node_a)); // Same task

    let task_b = StringConstant::new("World");
    let node_b = store.get_or_create_task_node(&task_b);
    assert_eq!(node_b, store.get_or_create_task_node(&task_b));
    assert_eq!(&task_b, store.get_task(&node_b));

    assert_ne!(node_a, node_b); // Different nodes
  }

  #[test]
  #[should_panic]
  fn test_task_mapping_panics() {
    let mut fake_store = Store::default();
    let fake_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let store: Store<StringConstant, String> = Store::default();
    store.get_task(&fake_node);
  }

We test this in the same way as the file mapping. Again, this works because StringConstant("Hello") and StringConstant("World") are different due to their derived Eq and Hash implementations, which make them different due to the strings being different. Likewise, StringConstant::new("Hello") and StringConstant::new("Hello") are equal even if they are created with 2 separate invocations of new.

These (in)equalities might seem quite obvious, but it is important to keep in mind because incrementality can only work if we can identify equal tasks at a later time, so that we can check their dependencies and return their cached output when those dependencies are consistent. Later on we will also see that this is important for soundness of the incremental build system.

Testing task outputs

Test task outputs by inserting the following code into the test module:

  #[test]
  fn test_task_outputs() {
    let mut store = Store::default();
    let output_a = "Hello".to_string();
    let task_a = StringConstant::new(&output_a);
    let node_a = store.get_or_create_task_node(&task_a);

    let output_b = "World".to_string();
    let task_b = StringConstant::new(&output_b);
    let node_b = store.get_or_create_task_node(&task_b);

    // Assert that tasks have no output by default.
    assert!(!store.task_has_output(&node_a));
    assert!(!store.task_has_output(&node_b));

    // Set output for task A, assert that A has that output but B is unchanged.
    store.set_task_output(&node_a, output_a.clone());
    assert!(store.task_has_output(&node_a));
    assert_eq!(store.get_task_output(&node_a), &output_a);
    assert!(!store.task_has_output(&node_b));

    // Set output for task B, assert that B has that output but A is unchanged.
    store.set_task_output(&node_b, output_b.clone());
    assert!(store.task_has_output(&node_a));
    assert_eq!(store.get_task_output(&node_a), &output_a);
    assert!(store.task_has_output(&node_b));
    assert_eq!(store.get_task_output(&node_b), &output_b);
  }

  #[test]
  #[should_panic]
  fn test_task_has_output_panics() {
    let mut fake_store = Store::default();
    let fake_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let store: Store<StringConstant, String> = Store::default();
    store.task_has_output(&fake_node);
  }

  #[test]
  #[should_panic]
  fn test_get_task_output_panics() {
    let mut store = Store::default();
    let node = store.get_or_create_task_node(&StringConstant::new("Hello"));
    store.get_task_output(&node);
  }

  #[test]
  #[should_panic]
  fn test_set_task_output_panics() {
    let mut fake_store = Store::default();
    let fake_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let mut store: Store<StringConstant, String> = Store::default();
    store.set_task_output(&fake_node, "Hello".to_string());
  }

Test test_task_outputs ensures that:

• task_has_output only returns true if given task has an output,
• and that get_task_output returns the output set by set_task_output for given task.

Test test_get_task_output_panics triggers a panic when we call get_task_output for a task that has no output, which is an invalid usage of Store that is more likely to happen than the other panics.

Testing dependencies

Test dependencies by inserting the following code into the test module:

  #[test]
  fn test_dependencies() {
    let mut store = Store::default();
    let output_a = "Hello".to_string();
    let task_a = StringConstant::new(output_a.clone());
    let node_a = store.get_or_create_task_node(&task_a);
    let output_b = "World".to_string();
    let task_b = StringConstant::new(output_b.clone());
    let node_b = store.get_or_create_task_node(&task_b);
    let path_c = PathBuf::from("hello.txt");
    let node_c = store.get_or_create_file_node(&path_c);

    assert_eq!(store.get_dependencies_of_task(&node_a).next(), None);
    assert_eq!(store.get_dependencies_of_task(&node_b).next(), None);

    // Add file dependency from task A to file C.
    let file_dependency_a2c = FileDependency::new(&path_c, FileStamper::Exists).unwrap();
    store.add_file_require_dependency(&node_a, &node_c, file_dependency_a2c.clone());
    let deps_of_a: Vec<_> = store.get_dependencies_of_task(&node_a).cloned().collect();
    assert_eq!(deps_of_a.get(0), Some(&Dependency::RequireFile(file_dependency_a2c.clone())));
    assert_eq!(deps_of_a.get(1), None);
    assert_eq!(store.get_dependencies_of_task(&node_b).next(), None);

    // Add task dependency from task B to task A.
    let task_dependency_b2a = TaskDependency::new(task_a.clone(), OutputStamper::Equals, output_a.clone());
    let result = store.add_task_require_dependency(&node_b, &node_a, task_dependency_b2a.clone());
    assert_eq!(result, Ok(()));
    let deps_of_a: Vec<_> = store.get_dependencies_of_task(&node_a).cloned().collect();
    assert_eq!(deps_of_a.get(0), Some(&Dependency::RequireFile(file_dependency_a2c.clone())));
    assert_eq!(deps_of_a.get(1), None);
    let deps_of_b: Vec<_> = store.get_dependencies_of_task(&node_b).cloned().collect();
    assert_eq!(deps_of_b.get(0), Some(&Dependency::RequireTask(task_dependency_b2a.clone())));
    assert_eq!(deps_of_b.get(1), None);

    // Add file dependency from task B to file C.
    let file_dependency_b2c = FileDependency::new(&path_c, FileStamper::Exists).unwrap();
    store.add_file_require_dependency(&node_b, &node_c, file_dependency_b2c.clone());
    let deps_of_a: Vec<_> = store.get_dependencies_of_task(&node_a).cloned().collect();
    assert_eq!(deps_of_a.get(0), Some(&Dependency::RequireFile(file_dependency_a2c.clone())));
    assert_eq!(deps_of_a.get(1), None);
    let deps_of_b: Vec<_> = store.get_dependencies_of_task(&node_b).cloned().collect();
    assert_eq!(deps_of_b.get(0), Some(&Dependency::RequireTask(task_dependency_b2a.clone())));
    assert_eq!(deps_of_b.get(1), Some(&Dependency::RequireFile(file_dependency_b2c.clone())));
    assert_eq!(deps_of_b.get(2), None);

    // Add task dependency from task A to task B, creating a cycle.
    let task_dependency_a2b = TaskDependency::new(task_a.clone(), OutputStamper::Equals, output_a.clone());
    let result = store.add_task_require_dependency(&node_a, &node_b, task_dependency_a2b);
    assert_eq!(result, Err(())); // Creates a cycle: error
  }

  #[test]
  #[should_panic]
  fn test_get_dependencies_of_task_panics() {
    let mut fake_store = Store::default();
    let fake_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let store: Store<StringConstant, String> = Store::default();
    let _ = store.get_dependencies_of_task(&fake_node);
  }

  #[test]
  #[should_panic]
  fn test_add_file_require_dependency_panics() {
    let mut fake_store = Store::default();
    let fake_file_node = fake_store.get_or_create_file_node("hello.txt");
    let fake_task_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let mut store: Store<StringConstant, String> = Store::default();
    let dependency = FileDependency::new("hello.txt", FileStamper::Exists).unwrap();
    store.add_file_require_dependency(&fake_task_node, &fake_file_node, dependency);
  }

  #[test]
  #[should_panic]
  fn test_add_task_require_dependency_panics() {
    let mut fake_store = Store::default();
    let output = "Hello".to_string();
    let task = StringConstant::new(&output);
    let fake_task_node = fake_store.get_or_create_task_node(&task);
    let mut store: Store<StringConstant, String> = Store::default();
    let dependency = TaskDependency::new(task, OutputStamper::Equals, output);
    let _ = store.add_task_require_dependency(&fake_task_node, &fake_task_node, dependency);
  }

The test_dependencies test is a bit more involved because it ensures that:

• get_dependencies_of_task returns the dependencies of given task. If the task has no dependencies, the iterator is empty. We test if an iterator is empty by getting the first element of the iterator with .next() and assert that it is None.
• get_dependencies_of_task returns the dependencies of given task in the order in which they were added, which will be important for soundness later. The graph library returns dependencies in insertion order.
• add_task_require_dependency adds a dependency to the correct task.
• creating a cycle with add_task_require_dependency results in it returning Err(()).

Note that the StringConstant task does not actually create file or task dependencies, but since Store never executes a task, we can pretend that it does in tests.

Testing task reset

Finally, test task reset by inserting the following code into the test module:

  #[test]
  fn test_reset() {
    let mut store = Store::default();
    let output_a = "Hello".to_string();
    let task_a = StringConstant::new(output_a.clone());
    let task_a_node = store.get_or_create_task_node(&task_a);
    let output_b = "World".to_string();
    let task_b = StringConstant::new(output_b.clone());
    let task_b_node = store.get_or_create_task_node(&task_b);
    let path = PathBuf::from("hello.txt");
    let file_node = store.get_or_create_file_node(&path);

    // Set outputs for task A and B.
    store.set_task_output(&task_a_node, output_a.clone());
    assert!(store.task_has_output(&task_a_node));
    assert_eq!(store.get_task_output(&task_a_node), &output_a);
    store.set_task_output(&task_b_node, output_b.clone());
    assert!(store.task_has_output(&task_b_node));
    assert_eq!(store.get_task_output(&task_b_node), &output_b);

    // Add file dependency for task A and B.
    let file_dependency = FileDependency::new(&path, FileStamper::Exists).unwrap();
    store.add_file_require_dependency(&task_a_node, &file_node, file_dependency.clone());
    let deps_of_a: Vec<_> = store.get_dependencies_of_task(&task_a_node).cloned().collect();
    assert_eq!(deps_of_a.get(0), Some(&Dependency::RequireFile(file_dependency.clone())));
    assert_eq!(deps_of_a.get(1), None);
    store.add_file_require_dependency(&task_b_node, &file_node, file_dependency.clone());
    let deps_of_b: Vec<_> = store.get_dependencies_of_task(&task_b_node).cloned().collect();
    assert_eq!(deps_of_b.get(0), Some(&Dependency::RequireFile(file_dependency.clone())));
    assert_eq!(deps_of_b.get(1), None);

    // Reset only task A.
    store.reset_task(&task_a_node);
    // Assert that task A is reset.
    assert!(!store.task_has_output(&task_a_node));
    assert_eq!(store.get_dependencies_of_task(&task_a_node).next(), None);
    // Assert that task B is unchanged.
    assert!(store.task_has_output(&task_b_node));
    assert_eq!(store.get_task_output(&task_b_node), &output_b);
    let deps_of_b: Vec<_> = store.get_dependencies_of_task(&task_b_node).cloned().collect();
    assert_eq!(deps_of_b.get(0), Some(&Dependency::RequireFile(file_dependency.clone())));
    assert_eq!(deps_of_b.get(1), None);
  }

  #[test]
  #[should_panic]
  fn test_reset_task_panics() {
    let mut fake_store = Store::default();
    let fake_node = fake_store.get_or_create_task_node(&StringConstant::new("Hello"));
    let mut store: Store<StringConstant, String> = Store::default();
    store.reset_task(&fake_node);
  }

Here, we ensure that a task with an output and dependencies, does not have an output and dependencies after a reset, while leaving another task untouched.

Confirm that the store implementation works with cargo test.