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}