Skip to main content

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}