critpath_core/transform.rs
1//! Counterfactual transformations: hypothetical edits to a graph, each producing a new graph.
2//!
3//! A transformation answers "what if". It does not compute a saving and does not decide whether a
4//! change is worth making; it produces the graph the change would give, so that the metrics can be
5//! recomputed on it and the two sets of numbers compared by the caller.
6//!
7//! Every result is built through [`GraphBuilder`], so a transformed graph is validated and acyclic
8//! exactly like an original one. Identifiers are therefore **not** carried across: the new graph
9//! hands out its own, and [`Applied`] holds the map from the old ones to the new.
10
11use core::fmt;
12use core::num::NonZeroU64;
13
14use crate::error::GraphError;
15use crate::graph::{BuildGraph, GraphBuilder, Unit, UnitId, UnitKind};
16use crate::millis::Millis;
17
18/// What the first part of a split unit is called, appended to the original target name.
19const PART_A: &str = " (part a)";
20/// What the second part of a split unit is called, appended to the original target name.
21const PART_B: &str = " (part b)";
22
23/// Which part of a split unit each of its dependents is assumed to need.
24///
25/// Splitting a crate cannot be modelled exactly, because which half a dependent actually needs is
26/// not knowable without performing the split. The two variants bracket that unknown rather than
27/// guessing at it.
28///
29/// The bracket is often degenerate: at a division fraction of one half the two parts finish at the
30/// same instant, so which dependent attaches to which part cannot move any downstream start time
31/// and the two answers coincide exactly. That is a property of the model, not a defect, and it is
32/// why the dependent assumption is not the only thing a reported interval should be swept over.
33#[derive(Clone, Copy, Debug, PartialEq, Eq)]
34#[non_exhaustive]
35pub enum SplitDependents {
36 /// Each dependent needs exactly one part, and it is the part that finishes first: the one
37 /// carrying less of the work, or part a when the two are equal. The best a split could do.
38 ///
39 /// Both parts inherit the same incoming edges and so can start at the same moment, which means
40 /// the smaller part reaches both its metadata and its end no later than the larger one.
41 /// Attaching every dependent to it therefore minimises every downstream start time at once,
42 /// whether an edge waits for metadata or for the whole part. No other assignment gives a
43 /// shorter critical path, which is what makes this a bound rather than one guess among many.
44 ///
45 /// It is not a plausible refactor: a part that nothing depends on would not be written. It is
46 /// the limit that a plausible refactor cannot beat.
47 Optimistic,
48 /// Every dependent still needs both parts. The split buys nothing structurally, and only the
49 /// pipelining boundary moves.
50 Pessimistic,
51}
52
53/// A hypothetical edit to a build graph.
54#[derive(Clone, Debug, PartialEq, Eq)]
55#[non_exhaustive]
56pub enum Transform {
57 /// Divide one unit into two, as splitting a crate in a refactor would.
58 ///
59 /// The first part receives `numerator / denominator` of the unit's work, rounded to nearest,
60 /// and the second receives the remainder, so the two parts sum to exactly the original weight.
61 /// `overhead` is then added to each part, because two crates re-parse shared imports and each
62 /// pays a fixed per-crate cost.
63 ///
64 /// A part's `metadata_at` is scaled by that part's share of the denominator and then clamped
65 /// so that it never exceeds the part's own total. The clamp is reachable through rounding
66 /// alone: a unit of 999ms that emits metadata at 999ms, divided at one half, gives parts of
67 /// 500ms and 499ms while both metadata times round to 500ms, and the second is clamped to
68 /// 499ms. `overhead` is added to the total but not to `metadata_at`, so the metadata boundary
69 /// of a part is the earliest the split could plausibly reach.
70 ///
71 /// Both parts inherit every incoming edge with its original kind, along with `kind` and
72 /// `requires_full_closure`. Where the outgoing edges go is decided by `dependents`:
73 /// [`SplitDependents::Pessimistic`] gives every dependent an edge from both parts, and
74 /// [`SplitDependents::Optimistic`] gives each dependent one edge, from the part that finishes
75 /// first.
76 ///
77 /// A build script cannot be split: one invocation of one program is not divisible, and
78 /// `numerator` may not exceed `denominator`.
79 SplitUnit {
80 /// The unit to divide.
81 unit: UnitId,
82 /// The numerator of the fraction of the work the first part receives.
83 numerator: u64,
84 /// The denominator of that fraction.
85 denominator: NonZeroU64,
86 /// Which part each dependent is assumed to need.
87 dependents: SplitDependents,
88 /// The fixed cost each part pays for being a separate crate.
89 overhead: Millis,
90 },
91 /// Remove one dependency edge, as deleting a `use` of one crate from another would.
92 ///
93 /// Only the edge goes; both units stay, even if one of them is left with nothing depending on
94 /// it. Removing a unit is [`Transform::RemoveUnits`].
95 RemoveEdge {
96 /// The producer the edge leaves.
97 from: UnitId,
98 /// The consumer the edge arrives at.
99 to: UnitId,
100 },
101 /// Remove units, as dropping a dependency or turning off a feature would.
102 ///
103 /// Removing a unit also removes everything that existed only to serve it. Precisely: let a
104 /// *root* be a unit that had no dependents in the **original** graph, which is what the build
105 /// was asked to produce. After the named units are removed, every surviving unit that can no
106 /// longer reach a surviving root by following dependents is removed as well. Reachability is
107 /// reflexive, so a surviving root reaches itself and always survives.
108 ///
109 /// Naming a unit twice is not an error, and removing every unit gives a valid empty graph.
110 RemoveUnits {
111 /// The units to remove.
112 units: Vec<UnitId>,
113 },
114}
115
116/// What became of one unit of the original graph.
117///
118/// Match with a wildcard arm, or use [`Mapped::primary`] and [`Mapped::secondary`]: a later
119/// transformation may map a unit in a way that does not exist yet.
120#[derive(Clone, Copy, Debug, PartialEq, Eq)]
121#[non_exhaustive]
122pub enum Mapped {
123 /// The unit survived unchanged, under a new identifier.
124 Kept(UnitId),
125 /// The unit was divided in two.
126 Split {
127 /// The part that received `numerator / denominator` of the work.
128 first: UnitId,
129 /// The part that received the remainder.
130 second: UnitId,
131 },
132 /// The unit is not in the new graph.
133 Removed,
134}
135
136impl Mapped {
137 /// The new identifier that best stands for the original unit, or `None` if it was removed.
138 ///
139 /// For a split, this is the first part.
140 #[must_use]
141 pub const fn primary(self) -> Option<UnitId> {
142 match self {
143 Self::Kept(id) => Some(id),
144 Self::Split { first, .. } => Some(first),
145 _ => None,
146 }
147 }
148
149 /// The second new identifier, for a mapping that produced two units.
150 #[must_use]
151 pub const fn secondary(self) -> Option<UnitId> {
152 match self {
153 Self::Split { second, .. } => Some(second),
154 _ => None,
155 }
156 }
157
158 /// Whether the unit is absent from the new graph.
159 #[must_use]
160 pub const fn is_removed(self) -> bool {
161 matches!(self, Self::Removed)
162 }
163}
164
165/// The graph a transformation produced, and where each original unit went.
166///
167/// The new graph is a different graph, so identifiers from the original are meaningless in it.
168/// Anything that wants to talk about the same unit before and after — a comparison of critical
169/// paths, a report that names the crate it just moved — has to go through the mapping.
170#[derive(Clone, Debug)]
171pub struct Applied {
172 graph: BuildGraph,
173 /// One entry per unit of the original graph, in original identifier order.
174 mapping: Vec<(UnitId, Mapped)>,
175}
176
177impl Applied {
178 /// The transformed graph.
179 #[must_use]
180 pub fn graph(&self) -> &BuildGraph {
181 &self.graph
182 }
183
184 /// The transformed graph, given up by value.
185 #[must_use]
186 pub fn into_graph(self) -> BuildGraph {
187 self.graph
188 }
189
190 /// What became of `original`, or `None` if the index is outside the graph that was transformed.
191 ///
192 /// An identifier from a different graph is not detected; see [`crate::BuildGraph`].
193 #[must_use]
194 pub fn mapped(&self, original: UnitId) -> Option<Mapped> {
195 self.mapping
196 .get(original.index())
197 .map(|&(_, mapped)| mapped)
198 }
199
200 /// Every unit of the original graph and what became of it, in original identifier order.
201 pub fn mapping(&self) -> impl ExactSizeIterator<Item = (UnitId, Mapped)> + '_ {
202 self.mapping.iter().copied()
203 }
204}
205
206/// A transformation that could not be applied, and why.
207///
208/// Every variant names the units involved, because the caller is usually acting on a unit a user
209/// picked out of a report and needs to say which one was refused.
210#[derive(Clone, Debug, PartialEq, Eq)]
211#[non_exhaustive]
212pub enum TransformError {
213 /// A transformation named a unit that is not in the graph it was applied to.
214 UnknownUnit {
215 /// The identifier that does not belong to this graph.
216 unit: UnitId,
217 /// How many units the graph does contain.
218 units: usize,
219 },
220 /// A transformation tried to split a unit that is not divisible.
221 UnsplittableKind {
222 /// The unit that cannot be split.
223 unit: UnitId,
224 /// What sort of work it performs.
225 kind: UnitKind,
226 },
227 /// A split asked for more work than the unit contains.
228 FractionAboveOne {
229 /// The unit that would have been split.
230 unit: UnitId,
231 /// The numerator that was asked for.
232 numerator: u64,
233 /// The denominator it was over.
234 denominator: NonZeroU64,
235 },
236 /// An edge removal named an edge the graph does not have.
237 MissingEdge {
238 /// The producer the edge was supposed to leave.
239 from: UnitId,
240 /// The consumer it was supposed to arrive at.
241 to: UnitId,
242 },
243 /// The graph the transformation produced did not validate.
244 Rebuild {
245 /// Why the produced graph was rejected.
246 source: GraphError,
247 },
248}
249
250impl From<GraphError> for TransformError {
251 fn from(source: GraphError) -> Self {
252 Self::Rebuild { source }
253 }
254}
255
256impl fmt::Display for TransformError {
257 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
258 match self {
259 Self::UnknownUnit { unit, units } => write!(
260 f,
261 "unit {unit} is not part of this graph, which holds {units} units; \
262 identifiers are only valid for the graph that handed them out, \
263 so take the identifier from the graph being transformed"
264 ),
265 Self::UnsplittableKind { unit, kind } => write!(
266 f,
267 "unit {unit} is a {kind} and cannot be split, \
268 because one run of one build script is a single indivisible step; \
269 split one of the library units instead, \
270 or shorten the build script by other means"
271 ),
272 Self::FractionAboveOne {
273 unit,
274 numerator,
275 denominator,
276 } => write!(
277 f,
278 "the division fraction {numerator}/{denominator} for unit {unit} is more than the \
279 whole unit, which would leave the second part with negative work; \
280 choose a numerator no larger than the denominator"
281 ),
282 Self::MissingEdge { from, to } => write!(
283 f,
284 "there is no edge from unit {from} to unit {to}, so it cannot be removed; \
285 list the dependencies of unit {to} and name one of those, \
286 remembering that an edge runs from the producer to the consumer"
287 ),
288 Self::Rebuild { source } => write!(
289 f,
290 "the graph this transformation produced did not validate: {source}"
291 ),
292 }
293 }
294}
295
296impl std::error::Error for TransformError {
297 fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
298 match self {
299 Self::Rebuild { source } => Some(source),
300 _ => None,
301 }
302 }
303}
304
305/// The units nothing depends on: what the build was asked to produce.
306///
307/// Returned in ascending identifier order.
308///
309/// ```
310/// use critpath_core::{roots, EdgeKind, GraphBuilder, Millis, Unit, UnitKind};
311///
312/// let mut builder = GraphBuilder::new();
313/// let lib = builder.add_unit(Unit {
314/// package: "leaf".to_owned(),
315/// version: "1.0.0".to_owned(),
316/// target: "leaf".to_owned(),
317/// kind: UnitKind::Lib,
318/// total: Millis::new(800),
319/// metadata_at: Some(Millis::new(600)),
320/// requires_full_closure: false,
321/// })?;
322/// let bin = builder.add_unit(Unit {
323/// package: "app".to_owned(),
324/// version: "1.0.0".to_owned(),
325/// target: "app".to_owned(),
326/// kind: UnitKind::Bin,
327/// total: Millis::new(200),
328/// metadata_at: None,
329/// requires_full_closure: true,
330/// })?;
331/// builder.add_edge(lib, bin, EdgeKind::Full)?;
332/// let graph = builder.build()?;
333///
334/// // Something depends on the library; nothing depends on the binary.
335/// assert_eq!(roots(&graph), vec![bin]);
336/// # Ok::<(), critpath_core::GraphError>(())
337/// ```
338#[must_use]
339pub fn roots(graph: &BuildGraph) -> Vec<UnitId> {
340 graph
341 .units()
342 .filter(|&(id, _)| is_root(graph, id))
343 .map(|(id, _)| id)
344 .collect()
345}
346
347/// Applies `transform` to `graph`, leaving `graph` untouched.
348///
349/// Each transformation copies the graph once, visiting every unit and edge a constant number of
350/// times. Handing the edges to [`GraphBuilder`] puts each one into an ordered map, so the cost is
351/// `O(V + E log E)`, of which validating the result is `O(V + E)`.
352///
353/// # Errors
354///
355/// [`TransformError::UnknownUnit`] if the transformation names an index outside the graph,
356/// [`TransformError::UnsplittableKind`] and [`TransformError::FractionAboveOne`] if a split is
357/// impossible or asks for more than the whole unit, [`TransformError::MissingEdge`] if an edge
358/// removal names an edge that is not there, and [`TransformError::Rebuild`] if the produced graph
359/// is rejected, which for a split of a graph already at [`crate::MAX_UNITS`] means there is no
360/// room for the extra unit.
361///
362/// ```
363/// use core::num::NonZeroU64;
364/// use critpath_core::{
365/// apply, GraphBuilder, Millis, SplitDependents, Transform, Unit, UnitKind,
366/// };
367///
368/// let mut builder = GraphBuilder::new();
369/// let heavy = builder.add_unit(Unit {
370/// package: "heavy".to_owned(),
371/// version: "1.0.0".to_owned(),
372/// target: "heavy".to_owned(),
373/// kind: UnitKind::Lib,
374/// total: Millis::new(1_000),
375/// metadata_at: Some(Millis::new(700)),
376/// requires_full_closure: false,
377/// })?;
378/// let graph = builder.build()?;
379///
380/// let applied = apply(
381/// &graph,
382/// &Transform::SplitUnit {
383/// unit: heavy,
384/// numerator: 1,
385/// denominator: NonZeroU64::new(2).ok_or("2 is not zero")?,
386/// dependents: SplitDependents::Pessimistic,
387/// overhead: Millis::new(50),
388/// },
389/// )?;
390///
391/// // 1000ms divided in half is 500ms in each part, and each part pays the 50ms overhead.
392/// assert_eq!(applied.graph().len(), 2);
393/// assert_eq!(applied.graph().total_work(), Millis::new(1_100));
394/// # Ok::<(), Box<dyn std::error::Error>>(())
395/// ```
396pub fn apply(graph: &BuildGraph, transform: &Transform) -> Result<Applied, TransformError> {
397 match transform {
398 Transform::SplitUnit {
399 unit,
400 numerator,
401 denominator,
402 dependents,
403 overhead,
404 } => split_unit(
405 graph,
406 *unit,
407 *numerator,
408 *denominator,
409 *dependents,
410 *overhead,
411 ),
412 Transform::RemoveEdge { from, to } => remove_edge(graph, *from, *to),
413 Transform::RemoveUnits { units } => remove_units(graph, units),
414 }
415}
416
417fn split_unit(
418 graph: &BuildGraph,
419 unit: UnitId,
420 numerator: u64,
421 denominator: NonZeroU64,
422 dependents: SplitDependents,
423 overhead: Millis,
424) -> Result<Applied, TransformError> {
425 let original = graph.unit(unit).ok_or(TransformError::UnknownUnit {
426 unit,
427 units: graph.len(),
428 })?;
429 if matches!(
430 original.kind,
431 UnitKind::BuildScriptCompile | UnitKind::BuildScriptRun
432 ) {
433 return Err(TransformError::UnsplittableKind {
434 unit,
435 kind: original.kind,
436 });
437 }
438 if numerator > denominator.get() {
439 return Err(TransformError::FractionAboveOne {
440 unit,
441 numerator,
442 denominator,
443 });
444 }
445
446 // The second part is the remainder rather than a second rounded multiplication, so that the
447 // two parts sum to exactly the original weight and a split moves work without inventing any.
448 let first_work = original.total.scaled(numerator, denominator);
449 let second_work = original.total.saturating_sub(first_work);
450 let second_share = denominator.get().saturating_sub(numerator);
451
452 let part = |work: Millis, share: u64, suffix: &str| {
453 let total = work.saturating_add(overhead);
454 Unit {
455 package: original.package.clone(),
456 // The parts are hypothetical, so they are named after the unit they came from. No
457 // crate by this name exists.
458 target: format!("{}{suffix}", original.target),
459 version: original.version.clone(),
460 kind: original.kind,
461 total,
462 // Rounding can push a scaled metadata time past the part that carries it, and a unit
463 // that emits metadata after it has finished is not a graph the builder accepts.
464 metadata_at: original
465 .metadata_at
466 .map(|at| at.scaled(share, denominator).min(total)),
467 requires_full_closure: original.requires_full_closure,
468 }
469 };
470 let first_unit = part(first_work, numerator, PART_A);
471 let second_unit = part(second_work, second_share, PART_B);
472
473 // Under the optimistic assumption every dependent needs one part, and it is the part that
474 // finishes first. Both parts inherit the same incoming edges, so they can start at the same
475 // moment, and the one carrying less work then reaches both its metadata and its end no later
476 // than the other. Attaching every dependent to it therefore minimises every downstream start
477 // time at once, whatever kind each edge is, which is what makes this a bound rather than one
478 // arbitrary assignment among many.
479 let dependents_take_first = first_unit.total <= second_unit.total;
480
481 let mut builder = GraphBuilder::with_capacity(graph.len().saturating_add(1));
482 let mut mapping = Vec::with_capacity(graph.len());
483 let mut parts = None;
484 for (old, existing) in graph.units() {
485 if old == unit {
486 // The parts take the position the original held, so the order of everything else is
487 // preserved.
488 let first = builder.add_unit(first_unit.clone())?;
489 let second = builder.add_unit(second_unit.clone())?;
490 parts = Some((first, second));
491 mapping.push((old, Mapped::Split { first, second }));
492 } else {
493 let new = builder.add_unit(existing.clone())?;
494 mapping.push((old, Mapped::Kept(new)));
495 }
496 }
497 let Some((first, second)) = parts else {
498 return Err(TransformError::UnknownUnit {
499 unit,
500 units: graph.len(),
501 });
502 };
503
504 let units = graph.len();
505 for (consumer, _) in graph.units() {
506 for dep in graph.dependencies(consumer).unwrap_or(&[]) {
507 if consumer == unit {
508 // Both parts inherit every incoming edge: the work they share came from one crate,
509 // and nothing says which part of it needed which dependency.
510 let from = translate(&mapping, dep.unit, units)?;
511 builder.add_edge(from, first, dep.kind)?;
512 builder.add_edge(from, second, dep.kind)?;
513 } else if dep.unit == unit {
514 let to = translate(&mapping, consumer, units)?;
515 match dependents {
516 SplitDependents::Pessimistic => {
517 builder.add_edge(first, to, dep.kind)?;
518 builder.add_edge(second, to, dep.kind)?;
519 }
520 SplitDependents::Optimistic => {
521 let from = if dependents_take_first { first } else { second };
522 builder.add_edge(from, to, dep.kind)?;
523 }
524 }
525 } else {
526 let from = translate(&mapping, dep.unit, units)?;
527 let to = translate(&mapping, consumer, units)?;
528 builder.add_edge(from, to, dep.kind)?;
529 }
530 }
531 }
532
533 Ok(Applied {
534 graph: builder.build()?,
535 mapping,
536 })
537}
538
539fn remove_edge(graph: &BuildGraph, from: UnitId, to: UnitId) -> Result<Applied, TransformError> {
540 for id in [from, to] {
541 if graph.unit(id).is_none() {
542 return Err(TransformError::UnknownUnit {
543 unit: id,
544 units: graph.len(),
545 });
546 }
547 }
548
549 let present = graph
550 .dependencies(to)
551 .unwrap_or(&[])
552 .iter()
553 .any(|dep| dep.unit == from);
554 if !present {
555 return Err(TransformError::MissingEdge { from, to });
556 }
557
558 rebuild(graph, &vec![true; graph.len()], Some((from, to)))
559}
560
561fn remove_units(graph: &BuildGraph, targets: &[UnitId]) -> Result<Applied, TransformError> {
562 let mut survives = vec![true; graph.len()];
563 for &target in targets {
564 match survives.get_mut(target.index()) {
565 Some(slot) => *slot = false,
566 None => {
567 return Err(TransformError::UnknownUnit {
568 unit: target,
569 units: graph.len(),
570 })
571 }
572 }
573 }
574
575 // A unit is worth building only if something the build was asked to produce still needs it.
576 // The roots are taken from the original graph, because removing a unit does not turn whatever
577 // it depended on into a thing the build was asked for.
578 let mut reaches_root = vec![false; graph.len()];
579 let mut pending: Vec<UnitId> = Vec::new();
580 for (id, _) in graph.units() {
581 if is_root(graph, id) && survives.get(id.index()).copied().unwrap_or(false) {
582 if let Some(slot) = reaches_root.get_mut(id.index()) {
583 *slot = true;
584 }
585 pending.push(id);
586 }
587 }
588 while let Some(id) = pending.pop() {
589 for dep in graph.dependencies(id).unwrap_or(&[]) {
590 if !survives.get(dep.unit.index()).copied().unwrap_or(false) {
591 continue;
592 }
593 if let Some(slot) = reaches_root.get_mut(dep.unit.index()) {
594 if !*slot {
595 *slot = true;
596 pending.push(dep.unit);
597 }
598 }
599 }
600 }
601
602 rebuild(graph, &reaches_root, None)
603}
604
605/// Copies the units `keep` marks, in their original relative order, and every edge whose two ends
606/// both survive and which `drop_edge` does not name.
607fn rebuild(
608 graph: &BuildGraph,
609 keep: &[bool],
610 drop_edge: Option<(UnitId, UnitId)>,
611) -> Result<Applied, TransformError> {
612 let mut builder = GraphBuilder::with_capacity(graph.len());
613 let mut mapping = Vec::with_capacity(graph.len());
614 for (old, existing) in graph.units() {
615 if keep.get(old.index()).copied().unwrap_or(false) {
616 let new = builder.add_unit(existing.clone())?;
617 mapping.push((old, Mapped::Kept(new)));
618 } else {
619 mapping.push((old, Mapped::Removed));
620 }
621 }
622
623 for (consumer, _) in graph.units() {
624 for dep in graph.dependencies(consumer).unwrap_or(&[]) {
625 if drop_edge == Some((dep.unit, consumer)) {
626 continue;
627 }
628 let (Some(from), Some(to)) = (kept(&mapping, dep.unit), kept(&mapping, consumer))
629 else {
630 continue;
631 };
632 builder.add_edge(from, to, dep.kind)?;
633 }
634 }
635
636 Ok(Applied {
637 graph: builder.build()?,
638 mapping,
639 })
640}
641
642/// Whether nothing depends on `id`.
643fn is_root(graph: &BuildGraph, id: UnitId) -> bool {
644 match graph.dependents(id) {
645 Some(dependents) => dependents.is_empty(),
646 None => false,
647 }
648}
649
650/// The new identifier of a unit that survived unchanged.
651fn kept(mapping: &[(UnitId, Mapped)], old: UnitId) -> Option<UnitId> {
652 match mapping.get(old.index()) {
653 Some(&(_, Mapped::Kept(new))) => Some(new),
654 _ => None,
655 }
656}
657
658/// As [`kept`], reporting the identifier that could not be translated rather than dropping it.
659fn translate(
660 mapping: &[(UnitId, Mapped)],
661 old: UnitId,
662 units: usize,
663) -> Result<UnitId, TransformError> {
664 kept(mapping, old).ok_or(TransformError::UnknownUnit { unit: old, units })
665}