Constructive Traces

Constructive traces are a method of Build System Rebuilders. However, it’s really best thought of as being a continuous spectrum of how deeply transitive dependencies are considered when determining if a task needs to be rebuilt.

  • constructive trace: stores resulting value as well. Enables cloud builds
    • applicative build systems can compute full hashes of all dependencies and retrieve from server in a single call.
    • in practice, many cloud build systems store hashes of values and have a second content addressable store that maps hash to value.
    • time to verify key depends on amount of transitive dependencies
  • deep constructive traces: ignores intermediate dependencies
    • shallow builds: cache hit of inputs means final result is up to date.
    • tasks must be deterministic
    • cannot support early cutoff (ie incremental builds)

deep constructive traces are merely constructive traces that consider n=infinity levels of transitive dependencies. constructive traces are the special case of n=1. deep constructive traces can pick any n to regain some early cutoff at the cost of more expensive shallow builds. Any n > 1 requires determinstic builds