Decides if a scheduled task is already up to date or not.
-
dirty bit: file system modified time, actual dirty bit, etc.
- can be minimal, but difficult to support early cutoff
- useful to reduce memory consumption
-
verifying traces: hash dependencies. Rebuild if changed.
- for suspending schedulers with dynamic dependencies, often the build steps are performed in order to check if a key needs to be rebuilt.
-
verifying step traces: instead of hashing dependencies, store built+changed time for each key and list of dependency keys (without hashes)
- stores less data than verifying traces
- allows values to be considered equal without being bit-for-bit equal
-
slightly different early cutoff semantics
- if a subset of target is built, changed, then reverted, verifying traces do not rebuild but verifying step traces will.
- Constructive Traces
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
Rebuild strategy | Topological scheduler | Restarting scheduler | Suspending scheduler |
---|---|---|---|
dirty bit | make | excel | |
verifying traces | ninja | shake | |
constructive traces | cloudbuild | bazel | cloud shake |
deep constructive traces | buck | nix |