Skip to main content

critpath_core/
analysis.rs

1//! Earliest and latest times over a build graph.
2//!
3//! This is the part of the tool that does not depend on how many executors a build gets: the
4//! critical path length, and how much room every unit beside it has. Section 4 of [`docs/model.md`](https://github.com/eventvoid/cargo-critpath/blob/main/docs/model.md)
5//! defines what is computed here and section 7 lists the invariants the tests cite.
6
7use crate::graph::{BuildGraph, EdgeKind, UnitId};
8use crate::millis::Millis;
9
10/// Earliest and latest times for every unit of one graph, and the critical path through it.
11///
12/// Produced by [`analyze`]. An identifier from a different graph is not detected: identifiers are
13/// dense indices, so a foreign one reads as `None` only when it points past the end, and otherwise
14/// returns another unit's numbers. Do not mix identifiers between graphs.
15///
16/// ```
17/// use critpath_core::{analyze, EdgeKind, GraphBuilder, Millis, Unit, UnitKind};
18///
19/// let mut builder = GraphBuilder::new();
20/// let lib = builder.add_unit(Unit {
21///     package: "leaf".to_owned(),
22///     version: "1.0.0".to_owned(),
23///     target: "leaf".to_owned(),
24///     kind: UnitKind::Lib,
25///     total: Millis::new(800),
26///     metadata_at: Some(Millis::new(600)),
27///     requires_full_closure: false,
28/// })?;
29/// let bin = builder.add_unit(Unit {
30///     package: "app".to_owned(),
31///     version: "1.0.0".to_owned(),
32///     target: "app".to_owned(),
33///     kind: UnitKind::Bin,
34///     total: Millis::new(200),
35///     metadata_at: None,
36///     requires_full_closure: true,
37/// })?;
38/// builder.add_edge(lib, bin, EdgeKind::Metadata)?;
39/// let graph = builder.build()?;
40///
41/// let analysis = analyze(&graph);
42/// // The edge offers metadata at 600, but a binary has to link, so it waits for all 800.
43/// assert_eq!(analysis.earliest_start(bin), Some(Millis::new(800)));
44/// assert_eq!(analysis.critical_path_len(), Millis::new(1_000));
45/// assert_eq!(analysis.critical_path(), &[lib, bin]);
46/// # Ok::<(), critpath_core::GraphError>(())
47/// ```
48#[derive(Clone, Debug)]
49pub struct Analysis {
50    earliest_start: Vec<Millis>,
51    earliest_finish: Vec<Millis>,
52    latest_finish: Vec<Millis>,
53    /// What each unit adds to the reported critical path, and `None` for a unit not on it.
54    contribution: Vec<Option<Millis>>,
55    path: Vec<UnitId>,
56    critical_path_len: Millis,
57    total_work: Millis,
58}
59
60/// The constraint that decided a unit's earliest start, and which unit imposed it.
61///
62/// `Metadata` means the path traverses the producer at its metadata offset; `Full` means it
63/// traverses the producer's whole duration. A closure requirement is recorded as `Full`, because
64/// that is what it demands, whatever kind the intervening edges had.
65#[derive(Clone, Copy)]
66struct Reason {
67    producer: UnitId,
68    kind: EdgeKind,
69}
70
71impl Analysis {
72    /// The critical path length: how long the build takes with as many executors as it wants.
73    ///
74    /// Zero for an empty graph. Never depends on the executor count or on a scheduling policy
75    /// (I10), which is why it is the number to lead with.
76    #[must_use]
77    pub fn critical_path_len(&self) -> Millis {
78        self.critical_path_len
79    }
80
81    /// One longest path, from a unit with no dependencies to the unit that finishes last.
82    ///
83    /// Empty for an empty graph. Where several paths are equally long, the reported one is fixed by
84    /// identifier order so that output is reproducible (I1).
85    ///
86    /// Consecutive units need not be joined by an edge: a unit that requires its whole closure is
87    /// preceded on the path by the unit in that closure which held it back, which section 3.1 of
88    /// [`docs/model.md`](https://github.com/eventvoid/cargo-critpath/blob/main/docs/model.md) shows need not be a direct dependency.
89    #[must_use]
90    pub fn critical_path(&self) -> &[UnitId] {
91        &self.path
92    }
93
94    /// The total work the analysed graph holds: the sum of every unit's duration.
95    #[must_use]
96    pub fn total_work(&self) -> Millis {
97        self.total_work
98    }
99
100    /// The earliest a unit could start, or `None` if the index is outside this analysis.
101    ///
102    /// An identifier belonging to a different graph is not detected. Identifiers are dense
103    /// indices, so a foreign one reads as `None` only when it happens to point past the end, and
104    /// otherwise names a different unit. Do not mix identifiers between graphs.
105    #[must_use]
106    pub fn earliest_start(&self, id: UnitId) -> Option<Millis> {
107        self.earliest_start.get(id.index()).copied()
108    }
109
110    /// The earliest a unit could finish, or `None` if the index is outside this analysis.
111    #[must_use]
112    pub fn earliest_finish(&self, id: UnitId) -> Option<Millis> {
113        self.earliest_finish.get(id.index()).copied()
114    }
115
116    /// The latest a unit may finish without lengthening the critical path, or `None` if the index is
117    /// outside this analysis.
118    #[must_use]
119    pub fn latest_finish(&self, id: UnitId) -> Option<Millis> {
120        self.latest_finish.get(id.index()).copied()
121    }
122
123    /// How much later than its earliest finish a unit may finish, or `None` if the index is outside
124    /// this analysis.
125    ///
126    /// Zero exactly for the units that cannot move at all (I9). Note that this is room in the
127    /// *finish* time: lengthening a pipelined producer by its slack is safe, but so is lengthening
128    /// it further, because a consumer released by metadata never waited for the finish anyway.
129    #[must_use]
130    pub fn slack(&self, id: UnitId) -> Option<Millis> {
131        let latest = self.latest_finish(id)?;
132        let earliest = self.earliest_finish(id)?;
133        Some(latest.saturating_sub(earliest))
134    }
135
136    /// Whether a unit has no slack at all, so that delaying it lengthens the whole build.
137    ///
138    /// True for every unit of [`critical_path`](Self::critical_path), and also for units on any
139    /// other equally long path.
140    #[must_use]
141    pub fn is_critical(&self, id: UnitId) -> bool {
142        self.slack(id) == Some(Millis::ZERO)
143    }
144
145    /// What a unit adds to the length of [`critical_path`](Self::critical_path).
146    ///
147    /// A unit traversed over a metadata edge adds only its metadata offset, because that is all the
148    /// path waited for; otherwise it adds its whole duration. The contributions of the units on the
149    /// path sum to exactly [`critical_path_len`](Self::critical_path_len), which makes them the
150    /// right quantity to rank candidates for change by.
151    ///
152    /// `None` for a unit that is not on the reported path, and for an index outside this analysis.
153    /// A unit off the path adds nothing to it, but that does not mean the build would not
154    /// notice its absence: check [`is_critical`](Self::is_critical) for units on an equally long
155    /// path elsewhere.
156    #[must_use]
157    pub fn critical_contribution(&self, id: UnitId) -> Option<Millis> {
158        self.contribution.get(id.index()).copied().flatten()
159    }
160}
161
162/// Computes earliest times, the critical path, and slack, in `O(V + E)`.
163///
164/// One pass forward in topological order and one back, each visiting every edge once. Nothing here
165/// consults an executor count.
166///
167/// See [`Analysis`] for an example.
168#[must_use]
169pub fn analyze(graph: &BuildGraph) -> Analysis {
170    let count = graph.len();
171    let (earliest_start, earliest_finish, reason) = forward_pass(graph, count);
172    let (critical_path_len, attaining) = latest_finisher(graph, &earliest_finish);
173    let latest_finish = backward_pass(graph, count, critical_path_len, &earliest_finish);
174    let (path, contribution) = recover_path(graph, count, attaining, &reason);
175
176    Analysis {
177        earliest_start,
178        earliest_finish,
179        latest_finish,
180        contribution,
181        path,
182        critical_path_len,
183        total_work: graph.total_work(),
184    }
185}
186
187/// Earliest start and finish for every unit, with the constraint that decided each start.
188fn forward_pass(
189    graph: &BuildGraph,
190    count: usize,
191) -> (Vec<Millis>, Vec<Millis>, Vec<Option<Reason>>) {
192    let mut earliest_start = vec![Millis::ZERO; count];
193    let mut earliest_finish = vec![Millis::ZERO; count];
194    let mut reason: Vec<Option<Reason>> = vec![None; count];
195    // The latest finish anywhere in a unit's transitive dependency closure, with the unit attaining
196    // it. This is `maxFullEft` of docs/model.md 3.1, kept as a recurrence over direct dependencies
197    // so that no closure is ever materialised.
198    let mut closure_finish: Vec<Option<Candidate>> = vec![None; count];
199
200    for &id in graph.topological_order() {
201        let Some(unit) = graph.unit(id) else {
202            continue;
203        };
204        let deps = graph.dependencies(id).unwrap_or(&[]);
205
206        let mut closure: Option<Candidate> = None;
207        for dep in deps {
208            let index = dep.unit.index();
209            let dep_finish = earliest_finish.get(index).copied().unwrap_or(Millis::ZERO);
210            take_later(&mut closure, dep_finish, dep.unit);
211            if let Some(inherited) = closure_finish.get(index).copied().flatten() {
212                take_later(&mut closure, inherited.time, inherited.unit);
213            }
214        }
215        if let Some(slot) = closure_finish.get_mut(id.index()) {
216            *slot = closure;
217        }
218
219        let start = if unit.requires_full_closure {
220            // Nothing this unit needs may still be running when it starts, so it waits for the
221            // last finish anywhere behind it, whatever the intervening edges asked for.
222            closure.map(|c| {
223                (
224                    c.time,
225                    Reason {
226                        producer: c.unit,
227                        kind: EdgeKind::Full,
228                    },
229                )
230            })
231        } else {
232            let mut best: Option<(Millis, Reason)> = None;
233            for dep in deps {
234                let Some(producer) = graph.unit(dep.unit) else {
235                    continue;
236                };
237                let offset = release_offset(producer.total, producer.metadata_at, dep.kind);
238                let dep_start = earliest_start
239                    .get(dep.unit.index())
240                    .copied()
241                    .unwrap_or(Millis::ZERO);
242                let release = dep_start.saturating_add(offset);
243                let better = match best {
244                    None => true,
245                    Some((time, current)) => {
246                        release > time || (release == time && dep.unit < current.producer)
247                    }
248                };
249                if better {
250                    best = Some((
251                        release,
252                        Reason {
253                            producer: dep.unit,
254                            kind: dep.kind,
255                        },
256                    ));
257                }
258            }
259            best
260        };
261
262        let (start, why) = match start {
263            Some((start, why)) => (start, Some(why)),
264            None => (Millis::ZERO, None),
265        };
266        if let Some(slot) = earliest_start.get_mut(id.index()) {
267            *slot = start;
268        }
269        if let Some(slot) = earliest_finish.get_mut(id.index()) {
270            *slot = start.saturating_add(unit.total);
271        }
272        if let Some(slot) = reason.get_mut(id.index()) {
273            *slot = why;
274        }
275    }
276
277    (earliest_start, earliest_finish, reason)
278}
279
280/// The latest finish for every unit that does not lengthen the critical path.
281///
282/// The mirror of [`forward_pass`]: one visit per edge in reverse topological order. The closure
283/// rule has to be applied here too, or a unit that a linker somewhere is waiting for would be
284/// reported as movable.
285fn backward_pass(
286    graph: &BuildGraph,
287    count: usize,
288    critical_path_len: Millis,
289    earliest_finish: &[Millis],
290) -> Vec<Millis> {
291    let mut latest_finish = vec![critical_path_len; count];
292    // The earliest latest-start of any unit that requires this unit's closure, whether or not it is
293    // a direct dependent. The mirror of `maxFullEft`, and derived the same way.
294    let mut closure_cap: Vec<Option<Millis>> = vec![None; count];
295
296    for &id in graph.topological_order().iter().rev() {
297        let Some(unit) = graph.unit(id) else {
298            continue;
299        };
300
301        let mut cap: Option<Millis> = None;
302        let mut bound = critical_path_len;
303        for dep in graph.dependents(id).unwrap_or(&[]) {
304            let Some(consumer) = graph.unit(dep.unit) else {
305                continue;
306            };
307            let consumer_latest_finish = latest_finish
308                .get(dep.unit.index())
309                .copied()
310                .unwrap_or(critical_path_len);
311            let consumer_latest_start = consumer_latest_finish.saturating_sub(consumer.total);
312
313            if consumer.requires_full_closure {
314                // This unit is in the consumer's closure, so it has to be finished before the
315                // consumer starts. Anything requiring the consumer's closure requires this unit's
316                // too, but its deadline is never the tighter one -- the consumer has to fit in
317                // between -- so it does not have to be carried across separately.
318                take_earlier(&mut cap, consumer_latest_start);
319            } else {
320                // A closure requirement further downstream reaches through this consumer.
321                if let Some(inherited) = closure_cap.get(dep.unit.index()).copied().flatten() {
322                    take_earlier(&mut cap, inherited);
323                }
324                let offset = release_offset(unit.total, unit.metadata_at, dep.kind);
325                // The consumer waits for `offset` of this unit, so this unit may run on for the
326                // remaining `total - offset` after that: a pipelined producer may finish after its
327                // consumer has already started.
328                let slack_past_release = unit.total.saturating_sub(offset);
329                bound = bound.min(consumer_latest_start.saturating_add(slack_past_release));
330            }
331        }
332        if let Some(cap) = cap {
333            bound = bound.min(cap);
334        }
335
336        if let Some(slot) = closure_cap.get_mut(id.index()) {
337            *slot = cap;
338        }
339        // A unit can always finish at its earliest possible time without delaying anything, so its
340        // deadline is never earlier than that. The two coincide except when the critical path has
341        // saturated, where subtracting from the clamped total would otherwise produce a deadline
342        // that cannot be met.
343        let floor = earliest_finish
344            .get(id.index())
345            .copied()
346            .unwrap_or(Millis::ZERO);
347        if let Some(slot) = latest_finish.get_mut(id.index()) {
348            *slot = bound.max(floor);
349        }
350    }
351
352    latest_finish
353}
354
355/// Traces the critical path back from the unit that finishes last, and prices each step.
356fn recover_path(
357    graph: &BuildGraph,
358    count: usize,
359    attaining: Option<UnitId>,
360    reason: &[Option<Reason>],
361) -> (Vec<UnitId>, Vec<Option<Millis>>) {
362    let mut contribution: Vec<Option<Millis>> = vec![None; count];
363    let mut path = Vec::new();
364
365    let Some(attaining) = attaining else {
366        return (path, contribution);
367    };
368    if let Some(unit) = graph.unit(attaining) {
369        if let Some(slot) = contribution.get_mut(attaining.index()) {
370            // Nothing on the path waits for the last unit, so all of it counts.
371            *slot = Some(unit.total);
372        }
373    }
374
375    let mut current = attaining;
376    // Each step moves strictly backwards in topological order, so `count` steps cannot be exceeded;
377    // the bound is here so that a defect elsewhere cannot turn into a hang.
378    for _ in 0..count {
379        path.push(current);
380        let Some(why) = reason.get(current.index()).copied().flatten() else {
381            break;
382        };
383        if let Some(producer) = graph.unit(why.producer) {
384            if let Some(slot) = contribution.get_mut(why.producer.index()) {
385                *slot = Some(release_offset(
386                    producer.total,
387                    producer.metadata_at,
388                    why.kind,
389                ));
390            }
391        }
392        current = why.producer;
393    }
394    path.reverse();
395
396    (path, contribution)
397}
398
399/// How much of a producer a consumer has to wait for.
400///
401/// A metadata edge from a unit that emits no metadata is rejected when the graph is built, so the
402/// fallback is unreachable; it waits for the whole unit rather than assuming an offset of zero,
403/// because guessing low here would understate every path through the unit.
404fn release_offset(total: Millis, metadata_at: Option<Millis>, kind: EdgeKind) -> Millis {
405    match kind {
406        EdgeKind::Metadata => metadata_at.unwrap_or(total),
407        EdgeKind::Full => total,
408    }
409}
410
411/// A time and the unit responsible for it.
412#[derive(Clone, Copy)]
413struct Candidate {
414    time: Millis,
415    unit: UnitId,
416}
417
418/// Keeps the later time, and on a tie the lower identifier, so the choice never depends on the
419/// order the candidates arrived in.
420fn take_later(best: &mut Option<Candidate>, time: Millis, unit: UnitId) {
421    let better = match best {
422        None => true,
423        Some(current) => time > current.time || (time == current.time && unit < current.unit),
424    };
425    if better {
426        *best = Some(Candidate { time, unit });
427    }
428}
429
430/// Keeps the earlier of two deadlines.
431fn take_earlier(best: &mut Option<Millis>, time: Millis) {
432    *best = Some(match *best {
433        None => time,
434        Some(current) => current.min(time),
435    });
436}
437
438/// The critical path length and the lowest-numbered unit attaining it.
439fn latest_finisher(graph: &BuildGraph, earliest_finish: &[Millis]) -> (Millis, Option<UnitId>) {
440    let mut best: Option<Candidate> = None;
441    for (id, _) in graph.units() {
442        let finish = earliest_finish
443            .get(id.index())
444            .copied()
445            .unwrap_or(Millis::ZERO);
446        take_later(&mut best, finish, id);
447    }
448    match best {
449        Some(best) => (best.time, Some(best.unit)),
450        None => (Millis::ZERO, None),
451    }
452}