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