Dynamic Dependencies

Now that we’ve implemented stamps, we can implement dynamic dependencies and their consistency checking. A dependency is inconsistent if after stamping, the new stamp is different from the old stamp. Therefore, dependencies need to keep track of their stamper and their previous stamp. To that end, we will implement the FileDependency and TaskDependency types with methods for consistency checking. We will also implement a Dependency type that abstracts over FileDependency and TaskDependency, which we will need for the dependency graph implementation in the next chapter.

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

Users of the library will not construct dependencies. They will create dependencies (and choose stampers) via Context methods. However, dependencies will be used in the public API for debug logging later, so we make the module public.

File dependencies

Create the pie/src/dependency.rs file and add:

use std::fmt::Debug;
use std::fs::File;
use std::io;
use std::path::PathBuf;

use crate::{Context, Task};
use crate::fs::open_if_file;
use crate::stamp::{FileStamp, FileStamper, OutputStamp, OutputStamper};

#[derive(Clone, Eq, PartialEq, Debug)]
pub struct FileDependency {
  path: PathBuf,
  stamper: FileStamper,
  stamp: FileStamp,
}

impl FileDependency {
  /// Creates a new file dependency with `path` and `stamper`, returning:
  /// - `Ok(file_dependency)` normally,
  /// - `Err(e)` if stamping failed.
  #[allow(dead_code)]
  pub fn new(path: impl Into<PathBuf>, stamper: FileStamper) -> Result<Self, io::Error> {
    let path = path.into();
    let stamp = stamper.stamp(&path)?;
    let dependency = FileDependency { path, stamper, stamp };
    Ok(dependency)
  }
  /// Creates a new file dependency with `path` and `stamper`, returning:
  /// - `Ok((file_dependency, Some(file)))` if a file exists at given path,
  /// - `Ok((file_dependency, None))` if no file exists at given path (but a directory could exist at given path),
  /// - `Err(e)` if stamping or opening the file failed.
  pub fn new_with_file(path: impl Into<PathBuf>, stamper: FileStamper) -> Result<(Self, Option<File>), io::Error> {
    let path = path.into();
    let stamp = stamper.stamp(&path)?;
    let file = open_if_file(&path)?;
    let dependency = FileDependency { path, stamper, stamp };
    Ok((dependency, file))
  }

  /// Returns the path of this dependency.
  #[allow(dead_code)]
  pub fn path(&self) -> &PathBuf { &self.path }
  /// Returns the stamper of this dependency.
  #[allow(dead_code)]
  pub fn stamper(&self) -> &FileStamper { &self.stamper }
  /// Returns the stamp of this dependency.
  #[allow(dead_code)]
  pub fn stamp(&self) -> &FileStamp { &self.stamp }

  /// Checks whether this file dependency is inconsistent, returning:
  /// - `Ok(Some(stamp))` if this dependency is inconsistent (with `stamp` being the new stamp of the dependency),
  /// - `Ok(None)` if this dependency is consistent,
  /// - `Err(e)` if there was an error checking this dependency for consistency.
  pub fn is_inconsistent(&self) -> Result<Option<FileStamp>, io::Error> {
    let new_stamp = self.stamper.stamp(&self.path)?;
    if new_stamp == self.stamp {
      Ok(None)
    } else {
      Ok(Some(new_stamp))
    }
  }
}

A FileDependency stores the path the dependency is about, the stamper used to create a stamp for this dependency, and the stamp that was created at the time the file dependency was made. The FileDependency::new_with_file function also returns the opened file if it exists, so that users of this function can read from the file without having to open it again. We add getter methods to get parts of the file dependency without allowing mutation. Since we will use those getter methods later, we annotate them with #[allow(dead_code)] to disable unused warnings.

A file dependency is inconsistent when the stored stamp is not equal to a stamp that we create at the time of checking, implemented in FileDependency::is_inconsistent. For example, if we created a file dependency (with modified stamper) for a file that was modified yesterday, then modify the file, and then call is_inconsistent on the file dependency, it would return Some(new_stamp) indicating that the dependency is inconsistent.

We implement an is_inconsistent method here instead of an is_consistent method, so that we can return the changed stamp when the dependency is inconsistent, which we will use for debug logging purposes later.

Creating and checking a file dependency can fail due to file operations failing (for example, cannot access the file), so we propagate those errors.

Task dependencies

Task dependencies are implemented in a similar way. Add to pie/src/dependency.rs:

#[derive(Clone, Eq, PartialEq, Debug)]
pub struct TaskDependency<T, O> {
  task: T,
  stamper: OutputStamper,
  stamp: OutputStamp<O>,
}

impl<T: Task> TaskDependency<T, T::Output> {
  /// Creates a new `task` dependency with `stamper` and `output`.
  pub fn new(task: T, stamper: OutputStamper, output: T::Output) -> Self {
    let stamp = stamper.stamp(output);
    Self { task, stamper, stamp }
  }

  /// Returns the task of this dependency.
  #[allow(dead_code)]
  pub fn task(&self) -> &T { &self.task }
  /// Returns the stamper of this dependency.
  #[allow(dead_code)]
  pub fn stamper(&self) -> &OutputStamper { &self.stamper }
  /// Returns the stamp of this dependency.
  #[allow(dead_code)]
  pub fn stamp(&self) -> &OutputStamp<T::Output> { &self.stamp }

  /// Checks whether this task dependency is inconsistent, returning:
  /// - `Some(stamp)` if this dependency is inconsistent (with `stamp` being the new stamp of the dependency),
  /// - `None` if this dependency is consistent.
  pub fn is_inconsistent<C: Context<T>>(&self, context: &mut C) -> Option<OutputStamp<T::Output>> {
    let output = context.require_task(&self.task);
    let new_stamp = self.stamper.stamp(output);
    if new_stamp == self.stamp {
      None
    } else {
      Some(new_stamp)
    }
  }
}

A TaskDependency stores the task the dependency is about, along with its stamper and stamp that is created when the dependency is created. Task dependencies are generic over the type of tasks T, and their type of outputs O. We also add immutable getters here.

A task dependency is inconsistent if, after recursively checking it, its stamp has changed, implemented in TaskDependency::is_inconsistent. Usually, this will be using the Equals task output stamper, so a task dependency is usually inconsistent when the output of the task changes. Because we need to recursively check the task, TaskDependency::is_inconsistent requires a context to be passed in. Again, there is more mutual recursion here.

This recursive consistency checking is one of the core ideas that make programmatic incremental build systems possible. But why is this so important? Why do we need recursive checking? Well, we want our build system to be sound, meaning that we must execute all tasks that are affected by a change. When we do not execute a task that is affected by a change, we are unsound, and introduce an incrementality bug!

Because of dynamic dependencies, a change in a leaf in the dependency tree may affect a task at the root. For example, a compilation task depends on a task that reads a configuration file, which depends on the configuration file. A change to a configuration file (leaf) affects a task that reads the configuration file, which in turn affects the compilation task (root). Therefore, we need to recursively check the dependency tree in order to execute all tasks affected by changes.

A different way to think about this, is to think about the invariant of the dependency consistency checking. The invariant is that a dependency is consistent if and only if the subtree of that dependency is consistent, and the dependency itself is consistent. The easiest way to adhere to this invariant, is recursive checking.

A final note about recursive checking is that tasks can be executed during it, and executing task can lead to new dynamic dependencies. However, recursive checking handles this without problems because these dependencies are created through the Context, which in turn will call is_inconsistent when needed.

Dependency enum

Finally, we create a Dependency enum that abstracts over these two kinds of dependencies. Add to pie/src/dependency.rs:

#[derive(Clone, Eq, PartialEq, Debug)]
pub enum Dependency<T, O> {
  RequireFile(FileDependency),
  RequireTask(TaskDependency<T, O>),
}

#[derive(Clone, Eq, PartialEq, Debug)]
pub enum Inconsistency<O> {
  File(FileStamp),
  Task(OutputStamp<O>),
}

impl<T: Task> Dependency<T, T::Output> {
  /// Checks whether this dependency is inconsistent, returning:
  /// - `Ok(Some(stamp))` if the dependency is inconsistent (with `stamp` being the new stamp of the dependency),
  /// - `Ok(None)` if the dependency is consistent,
  /// - `Err(e)` if there was an error checking the dependency for consistency.
  pub fn is_inconsistent<C: Context<T>>(&self, context: &mut C) -> Result<Option<Inconsistency<T::Output>>, io::Error> {
    let option = match self {
      Dependency::RequireFile(d) => d.is_inconsistent()?
        .map(|s| Inconsistency::File(s)),
      Dependency::RequireTask(d) => d.is_inconsistent(context)
        .map(|s| Inconsistency::Task(s)),
    };
    Ok(option)
  }
}

Dependency just merges the two kinds of dependencies and provides an is_inconsistent method that calls the corresponding method. We return the changed stamp here as well for debug logging later. We wrap the changed stamp in an Inconsistency enum, and map to the correct variant if there is an inconsistency.

Because Dependency can store a TaskDependency, we need to propagate the T and O generics. Likewise, Inconsistency propagates the O generic for OutputStamp.

Tests

As usual, we write some tests to confirm the behaviour. Add tests to pie/src/dependency.rs:

#[cfg(test)]
mod test {
  use std::fs::write;
  use std::io::{self, Read};

  use dev_shared::{create_temp_file, write_until_modified};

  use crate::context::non_incremental::NonIncrementalContext;

  use super::*;

  /// Task that reads file at given path and returns it contents as a string.
  #[derive(Clone, PartialEq, Eq, Hash, Debug)]
  struct ReadStringFromFile(PathBuf);

  impl Task for ReadStringFromFile {
    type Output = String;
    fn execute<C: Context<Self>>(&self, context: &mut C) -> Self::Output {
      let mut string = String::new();
      let file = context.require_file(&self.0).expect("failed to require file");
      if let Some(mut file) = file {
        file.read_to_string(&mut string).expect("failed to read from file");
      };
      string
    }
  }

  #[test]
  fn test_file_dependency_consistency() -> Result<(), io::Error> {
    let mut context = NonIncrementalContext;

    let temp_file = create_temp_file()?;
    write(&temp_file, "test1")?;

    let file_dependency = FileDependency::new(temp_file.path(), FileStamper::Modified)?;
    let dependency: Dependency<ReadStringFromFile, String> = Dependency::RequireFile(file_dependency.clone());
    assert!(file_dependency.is_inconsistent()?.is_none());
    assert!(dependency.is_inconsistent(&mut context)?.is_none());

    // Change the file, changing the stamp the stamper will create next time, making the file dependency inconsistent.
    write_until_modified(&temp_file, "test2")?;
    assert!(file_dependency.is_inconsistent()?.is_some());
    assert!(dependency.is_inconsistent(&mut context)?.is_some());

    Ok(())
  }

  #[test]
  fn test_task_dependency_consistency() -> Result<(), io::Error> {
    let mut context = NonIncrementalContext;

    let temp_file = create_temp_file()?;
    write(&temp_file, "test1")?;
    let task = ReadStringFromFile(temp_file.path().to_path_buf());
    let output = context.require_task(&task);

    let task_dependency = TaskDependency::new(task.clone(), OutputStamper::Equals, output);
    let dependency = Dependency::RequireTask(task_dependency.clone());
    assert!(task_dependency.is_inconsistent(&mut context).is_none());
    assert!(dependency.is_inconsistent(&mut context)?.is_none());

    // Change the file, causing the task to return a different output, changing the stamp the stamper will create next
    // time, making the task dependency inconsistent.
    write_until_modified(&temp_file, "test2")?;
    assert!(task_dependency.is_inconsistent(&mut context).is_some());
    assert!(dependency.is_inconsistent(&mut context)?.is_some());

    Ok(())
  }
}

We test a file dependency by asserting that is_inconsistent returns Some after changing the file.

Testing task dependencies requires a bit more work. We create task ReadStringFromFile that reads a string from a file, and then returns that string as output. We require the task to get its output ("test1"), and create a task dependency with it. Then, we change the file and check consistency of the task dependency. That recursively requires the task, the context will execute the task, and the task now returns ("test2"). Since we use the Equals output stamper, and "test1" does not equal "test2", the dependency is inconsistent and returns a stamp containing "test2".

Note that we are both testing the specific dependencies (FileDependency and TaskDependency), and the general Dependency.

Run cargo test to confirm everything still works. You will get some warnings about unused things, but that is ok as we will use them in the next section.