Expand description
Schedule simulation and counterfactual analysis over a weighted build DAG.
This crate knows nothing about Cargo, rustc, files, or JSON. It takes a graph of weighted
compilation units joined by dependency edges, and answers two kinds of question about it:
how long the build must take, and what a change to the graph would do to that number.
Using it for a build system other than Cargo means writing an adapter that produces a
BuildGraph; nothing in here has to change.
The model, its invariants, and its known systematic errors are documented in docs/model.md
in the repository.
Structs§
- Analysis
- Earliest and latest times for every unit of one graph, and the critical path through it.
- Applied
- The graph a transformation produced, and where each original unit went.
- Build
Graph - A validated, acyclic build graph.
- Dep
- One end of an edge, together with what the edge requires.
- Graph
Builder - Accumulates units and edges, then validates them into a
BuildGraph. - Millis
- A duration in whole milliseconds.
- Schedule
- When every unit ran, on a fixed number of executors under a fixed policy.
- Unit
- One indivisible piece of scheduled work.
- UnitId
- A handle to a unit within one graph.
Enums§
- Edge
Kind - What a consumer needs from a producer before it can start.
- Graph
Error - A graph that could not be constructed, and why.
- Mapped
- What became of one unit of the original graph.
- Policy
- Which unit a scheduler picks when several are ready and one executor is free.
- Split
Dependents - Which part of a split unit each of its dependents is assumed to need.
- Transform
- A hypothetical edit to a build graph.
- Transform
Error - A transformation that could not be applied, and why.
- Unit
Kind - What sort of work a unit performs.
Constants§
- MAX_
UNITS - The largest number of units a graph can hold.
Functions§
- analyze
- Computes earliest times, the critical path, and slack, in
O(V + E). - apply
- Applies
transformtograph, leavinggraphuntouched. - area_
bound - The area bound: no schedule on
executorsexecutors can beat the total work divided between them, rounded up because a makespan is a whole number of milliseconds. - lower_
bound - The larger of the critical path and the area bound: no schedule on
executorsexecutors can finish sooner, whatever policy it follows. - roots
- The units nothing depends on: what the build was asked to produce.
- simulate
- Simulates a build on
executorsexecutors.