Skip to main content

Crate critpath_core

Crate critpath_core 

Source
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.
BuildGraph
A validated, acyclic build graph.
Dep
One end of an edge, together with what the edge requires.
GraphBuilder
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§

EdgeKind
What a consumer needs from a producer before it can start.
GraphError
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.
SplitDependents
Which part of a split unit each of its dependents is assumed to need.
Transform
A hypothetical edit to a build graph.
TransformError
A transformation that could not be applied, and why.
UnitKind
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 transform to graph, leaving graph untouched.
area_bound
The area bound: no schedule on executors executors 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 executors executors 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 executors executors.