Skip to main content

critpath_core/
graph.rs

1//! The build graph: weighted compilation units joined by dependency edges.
2
3use core::fmt;
4use std::collections::{BTreeMap, VecDeque};
5
6use crate::error::GraphError;
7use crate::millis::Millis;
8
9/// The largest number of units a graph can hold.
10///
11/// Identifiers are 32 bits so that a graph of a few thousand units stays compact, and the limit is
12/// checked rather than allowed to wrap.
13pub const MAX_UNITS: usize = u32::MAX as usize - 1;
14
15/// A handle to a unit within one graph.
16///
17/// Identifiers are only meaningful for the graph that produced them, and mixing them is **not**
18/// detected once a graph is built: they are dense indices, so an identifier from another graph
19/// either points past the end or silently names a different unit. [`GraphBuilder::add_edge`] does
20/// reject an out-of-range identifier as [`GraphError::UnknownUnit`], but that is a bounds check
21/// rather than a provenance check.
22#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
23pub struct UnitId(u32);
24
25impl UnitId {
26    /// The identifier as a zero-based index.
27    #[must_use]
28    pub const fn index(self) -> usize {
29        self.0 as usize
30    }
31}
32
33impl fmt::Display for UnitId {
34    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35        write!(f, "{}", self.0)
36    }
37}
38
39/// What sort of work a unit performs.
40///
41/// The simulator does not read this; it exists so that output can describe a unit and so that
42/// transformations can refuse to do something meaningless, such as splitting a build script. More
43/// variants may be added, so callers must not assume the set is closed.
44#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
45#[non_exhaustive]
46pub enum UnitKind {
47    /// A library that other units compile against.
48    Lib,
49    /// A procedural macro, which must be fully built and loaded before a dependent can use it.
50    ProcMacro,
51    /// An executable.
52    Bin,
53    /// A test or benchmark binary.
54    Test,
55    /// Compiling a build script into an executable.
56    BuildScriptCompile,
57    /// Running a build script that has already been compiled.
58    BuildScriptRun,
59    /// Anything else.
60    Other,
61}
62
63impl UnitKind {
64    /// A short stable name, used in machine-readable output.
65    #[must_use]
66    pub const fn as_str(self) -> &'static str {
67        match self {
68            Self::Lib => "lib",
69            Self::ProcMacro => "proc-macro",
70            Self::Bin => "bin",
71            Self::Test => "test",
72            Self::BuildScriptCompile => "build-script-compile",
73            Self::BuildScriptRun => "build-script-run",
74            Self::Other => "other",
75        }
76    }
77}
78
79impl fmt::Display for UnitKind {
80    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
81        f.write_str(self.as_str())
82    }
83}
84
85/// One indivisible piece of scheduled work.
86#[derive(Clone, Debug, PartialEq, Eq)]
87pub struct Unit {
88    /// The package the unit belongs to.
89    pub package: String,
90    /// The package's version.
91    pub version: String,
92    /// The target within the package, such as a library or binary name.
93    pub target: String,
94    /// What sort of work this is.
95    pub kind: UnitKind,
96    /// How long the whole unit takes.
97    pub total: Millis,
98    /// How far into the unit its metadata becomes available, if it produces any.
99    ///
100    /// `Some` exactly when other units can begin against this one's metadata rather than waiting
101    /// for it to finish. Must not exceed `total`.
102    pub metadata_at: Option<Millis>,
103    /// Whether this unit needs every unit it transitively depends on to be completely finished.
104    ///
105    /// True for anything that links: an executable, a test, a procedural macro, a dynamic or static
106    /// library. Such a unit cannot start until its whole transitive dependency closure is done, not
107    /// merely its immediate dependencies, because a linker needs object code that pipelining does
108    /// not guarantee to exist yet.
109    pub requires_full_closure: bool,
110}
111
112/// What a consumer needs from a producer before it can start.
113#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
114pub enum EdgeKind {
115    /// The producer's metadata is enough.
116    Metadata,
117    /// The producer must have finished completely.
118    Full,
119}
120
121impl EdgeKind {
122    /// A short stable name, used in machine-readable output.
123    #[must_use]
124    pub const fn as_str(self) -> &'static str {
125        match self {
126            Self::Metadata => "metadata",
127            Self::Full => "full",
128        }
129    }
130
131    /// Whether this kind releases its consumer no earlier than `other` does.
132    #[must_use]
133    const fn is_at_least_as_strong_as(self, other: Self) -> bool {
134        matches!(self, Self::Full) || matches!(other, Self::Metadata)
135    }
136}
137
138impl fmt::Display for EdgeKind {
139    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
140        f.write_str(self.as_str())
141    }
142}
143
144/// One end of an edge, together with what the edge requires.
145#[derive(Clone, Copy, Debug, PartialEq, Eq)]
146pub struct Dep {
147    /// The unit at the other end.
148    pub unit: UnitId,
149    /// What the edge requires.
150    pub kind: EdgeKind,
151}
152
153/// A validated, acyclic build graph.
154///
155/// Construct one with [`GraphBuilder`]. Once built, a graph is immutable and known to be acyclic,
156/// so traversals need no cycle guard.
157///
158/// ```
159/// use critpath_core::{EdgeKind, GraphBuilder, Millis, Unit, UnitKind};
160///
161/// let mut builder = GraphBuilder::new();
162/// let lib = builder.add_unit(Unit {
163///     package: "leaf".to_owned(),
164///     version: "1.0.0".to_owned(),
165///     target: "leaf".to_owned(),
166///     kind: UnitKind::Lib,
167///     total: Millis::new(800),
168///     metadata_at: Some(Millis::new(600)),
169///     requires_full_closure: false,
170/// })?;
171/// let bin = builder.add_unit(Unit {
172///     package: "app".to_owned(),
173///     version: "1.0.0".to_owned(),
174///     target: "app".to_owned(),
175///     kind: UnitKind::Bin,
176///     total: Millis::new(200),
177///     metadata_at: None,
178///     requires_full_closure: true,
179/// })?;
180/// builder.add_edge(lib, bin, EdgeKind::Full)?;
181///
182/// let graph = builder.build()?;
183/// assert_eq!(graph.len(), 2);
184/// assert_eq!(graph.total_work(), Millis::new(1_000));
185/// # Ok::<(), critpath_core::GraphError>(())
186/// ```
187#[derive(Clone, Debug)]
188pub struct BuildGraph {
189    units: Vec<Unit>,
190    /// Offsets into `deps`, one per unit plus a trailing total.
191    dep_start: Vec<u32>,
192    /// Incoming edges, grouped by consumer.
193    deps: Vec<Dep>,
194    /// Offsets into `rdeps`, one per unit plus a trailing total.
195    rdep_start: Vec<u32>,
196    /// Outgoing edges, grouped by producer.
197    rdeps: Vec<Dep>,
198    topo: Vec<UnitId>,
199    total_work: Millis,
200}
201
202impl BuildGraph {
203    /// How many units the graph holds.
204    #[must_use]
205    pub fn len(&self) -> usize {
206        self.units.len()
207    }
208
209    /// Whether the graph holds no units.
210    #[must_use]
211    pub fn is_empty(&self) -> bool {
212        self.units.is_empty()
213    }
214
215    /// How many edges the graph holds, after duplicates have been merged.
216    #[must_use]
217    pub fn edge_count(&self) -> usize {
218        self.deps.len()
219    }
220
221    /// The sum of every unit's duration, which is the total work a build must perform.
222    #[must_use]
223    pub fn total_work(&self) -> Millis {
224        self.total_work
225    }
226
227    /// The unit `id` refers to, or `None` if the index is outside this graph.
228    ///
229    /// An identifier belonging to a different graph is not detected: identifiers are dense
230    /// indices, so a foreign one reads as `None` only when it points past the end, and otherwise
231    /// names a different unit. Do not mix identifiers between graphs.
232    #[must_use]
233    pub fn unit(&self, id: UnitId) -> Option<&Unit> {
234        self.units.get(id.index())
235    }
236
237    /// Every unit, in identifier order.
238    pub fn units(&self) -> impl ExactSizeIterator<Item = (UnitId, &Unit)> + '_ {
239        self.units
240            .iter()
241            .enumerate()
242            .map(|(i, u)| (UnitId(i as u32), u))
243    }
244
245    /// The units `id` depends on, or `None` if the index is outside this graph.
246    #[must_use]
247    pub fn dependencies(&self, id: UnitId) -> Option<&[Dep]> {
248        Self::slice(&self.deps, &self.dep_start, id)
249    }
250
251    /// The units that depend on `id`, or `None` if the index is outside this graph.
252    #[must_use]
253    pub fn dependents(&self, id: UnitId) -> Option<&[Dep]> {
254        Self::slice(&self.rdeps, &self.rdep_start, id)
255    }
256
257    /// Every unit in an order that places each dependency before its dependents.
258    #[must_use]
259    pub fn topological_order(&self) -> &[UnitId] {
260        &self.topo
261    }
262
263    fn slice<'a>(edges: &'a [Dep], starts: &[u32], id: UnitId) -> Option<&'a [Dep]> {
264        let from = *starts.get(id.index())? as usize;
265        let to = *starts.get(id.index().checked_add(1)?)? as usize;
266        edges.get(from..to)
267    }
268}
269
270/// Accumulates units and edges, then validates them into a [`BuildGraph`].
271///
272/// Identifiers are handed out in insertion order, so an adapter that wants a canonical unit order
273/// inserts in that order. The graph never reorders units, so identifiers stay meaningful to the
274/// code that built it.
275#[derive(Clone, Debug, Default)]
276pub struct GraphBuilder {
277    units: Vec<Unit>,
278    /// Keyed on `(consumer, producer)` so that iteration is ordered and duplicates collapse.
279    edges: BTreeMap<(u32, u32), EdgeKind>,
280}
281
282impl GraphBuilder {
283    /// An empty builder.
284    #[must_use]
285    pub fn new() -> Self {
286        Self::default()
287    }
288
289    /// An empty builder with room for `units` units already reserved.
290    #[must_use]
291    pub fn with_capacity(units: usize) -> Self {
292        Self {
293            units: Vec::with_capacity(units),
294            edges: BTreeMap::new(),
295        }
296    }
297
298    /// Adds a unit and returns its identifier.
299    ///
300    /// # Errors
301    ///
302    /// [`GraphError::UnitLimitExceeded`] if the graph would exceed [`MAX_UNITS`].
303    pub fn add_unit(&mut self, unit: Unit) -> Result<UnitId, GraphError> {
304        if self.units.len() >= MAX_UNITS {
305            return Err(GraphError::UnitLimitExceeded { limit: MAX_UNITS });
306        }
307        let id = UnitId(self.units.len() as u32);
308        self.units.push(unit);
309        Ok(id)
310    }
311
312    /// Records that `to` depends on `from`.
313    ///
314    /// Adding the same pair twice keeps whichever kind releases the consumer later, because
315    /// keeping the weaker of two stated constraints would make the analysis optimistic.
316    ///
317    /// # Errors
318    ///
319    /// [`GraphError::UnknownUnit`] if either index is outside this builder, which is a bounds check
320    /// and not a check of where the identifier came from, and [`GraphError::SelfDependency`] if they
321    /// are the same unit.
322    pub fn add_edge(&mut self, from: UnitId, to: UnitId, kind: EdgeKind) -> Result<(), GraphError> {
323        for id in [from, to] {
324            if id.index() >= self.units.len() {
325                return Err(GraphError::UnknownUnit {
326                    id,
327                    units: self.units.len(),
328                });
329            }
330        }
331        if from == to {
332            return Err(GraphError::SelfDependency { unit: from });
333        }
334
335        self.edges
336            .entry((to.0, from.0))
337            .and_modify(|existing| {
338                if kind.is_at_least_as_strong_as(*existing) {
339                    *existing = kind;
340                }
341            })
342            .or_insert(kind);
343        Ok(())
344    }
345
346    /// Validates the accumulated units and edges.
347    ///
348    /// # Errors
349    ///
350    /// [`GraphError::MetadataAfterCompletion`] if a unit emits metadata after it finishes,
351    /// [`GraphError::MetadataEdgeFromOpaqueUnit`] if a metadata edge leaves a unit that emits no
352    /// metadata, and [`GraphError::Cycle`] if the dependencies are not acyclic.
353    pub fn build(self) -> Result<BuildGraph, GraphError> {
354        let count = self.units.len();
355
356        for (i, unit) in self.units.iter().enumerate() {
357            if let Some(metadata_at) = unit.metadata_at {
358                if metadata_at > unit.total {
359                    return Err(GraphError::MetadataAfterCompletion {
360                        unit: UnitId(i as u32),
361                        metadata_at,
362                        total: unit.total,
363                    });
364                }
365            }
366        }
367
368        for (&(consumer, producer), &kind) in &self.edges {
369            if kind == EdgeKind::Metadata {
370                let emits = self
371                    .units
372                    .get(producer as usize)
373                    .is_some_and(|u| u.metadata_at.is_some());
374                if !emits {
375                    return Err(GraphError::MetadataEdgeFromOpaqueUnit {
376                        producer: UnitId(producer),
377                        consumer: UnitId(consumer),
378                    });
379                }
380            }
381        }
382
383        let mut in_degree = vec![0u32; count];
384        let mut out_degree = vec![0u32; count];
385        for &(consumer, producer) in self.edges.keys() {
386            if let Some(d) = in_degree.get_mut(consumer as usize) {
387                *d = d.saturating_add(1);
388            }
389            if let Some(d) = out_degree.get_mut(producer as usize) {
390                *d = d.saturating_add(1);
391            }
392        }
393
394        // Incoming edges, grouped by consumer. `self.edges` is keyed on `(consumer, producer)`, so
395        // iterating it in order visits every edge of consumer 0, then every edge of consumer 1, and
396        // so on. Pushing sequentially therefore lands each edge exactly where the prefix sums of
397        // the in-degrees say it belongs.
398        let dep_start = prefix_sums(&in_degree);
399        let deps: Vec<Dep> = self
400            .edges
401            .iter()
402            .map(|(&(_, producer), &kind)| Dep {
403                unit: UnitId(producer),
404                kind,
405            })
406            .collect();
407
408        // Outgoing edges, grouped by producer. Iteration order does not group by producer, so these
409        // are placed through a moving cursor per producer.
410        let rdep_start = prefix_sums(&out_degree);
411        let mut cursor = rdep_start.clone();
412        let mut rdeps = vec![
413            Dep {
414                unit: UnitId(0),
415                kind: EdgeKind::Full,
416            };
417            self.edges.len()
418        ];
419        for (&(consumer, producer), &kind) in &self.edges {
420            let Some(slot) = cursor.get_mut(producer as usize) else {
421                continue;
422            };
423            let at = *slot as usize;
424            *slot = slot.saturating_add(1);
425            if let Some(cell) = rdeps.get_mut(at) {
426                *cell = Dep {
427                    unit: UnitId(consumer),
428                    kind,
429                };
430            }
431        }
432
433        let topo = topological_order(count, &in_degree, &rdep_start, &rdeps);
434        if topo.len() < count {
435            return Err(GraphError::Cycle {
436                units: find_cycle(count, &topo, &dep_start, &deps),
437            });
438        }
439
440        let total_work = self.units.iter().map(|u| u.total).sum();
441
442        Ok(BuildGraph {
443            units: self.units,
444            dep_start,
445            deps,
446            rdep_start,
447            rdeps,
448            topo,
449            total_work,
450        })
451    }
452}
453
454/// Offsets of each group in a compressed adjacency list, plus a trailing total.
455fn prefix_sums(degrees: &[u32]) -> Vec<u32> {
456    let mut starts = Vec::with_capacity(degrees.len().saturating_add(1));
457    let mut running = 0u32;
458    for degree in degrees {
459        starts.push(running);
460        running = running.saturating_add(*degree);
461    }
462    starts.push(running);
463    starts
464}
465
466/// Kahn's algorithm, seeded in ascending identifier order so the result is deterministic.
467fn topological_order(
468    count: usize,
469    in_degree: &[u32],
470    rdep_start: &[u32],
471    rdeps: &[Dep],
472) -> Vec<UnitId> {
473    let mut remaining = in_degree.to_vec();
474    let mut order = Vec::with_capacity(count);
475    let mut queue: VecDeque<u32> = (0..count)
476        .filter(|&i| remaining.get(i).copied() == Some(0))
477        .map(|i| i as u32)
478        .collect();
479
480    while let Some(node) = queue.pop_front() {
481        order.push(UnitId(node));
482        let from = *rdep_start.get(node as usize).unwrap_or(&0) as usize;
483        let to = rdep_start
484            .get((node as usize).saturating_add(1))
485            .copied()
486            .unwrap_or(0) as usize;
487        for dep in rdeps.get(from..to).unwrap_or(&[]) {
488            if let Some(d) = remaining.get_mut(dep.unit.index()) {
489                *d = d.saturating_sub(1);
490                if *d == 0 {
491                    queue.push_back(dep.unit.0);
492                }
493            }
494        }
495    }
496
497    order
498}
499
500/// Walks backwards along dependencies among the units Kahn's algorithm could not place, which is
501/// exactly the set that lies on or behind a cycle, until a unit repeats.
502fn find_cycle(count: usize, placed: &[UnitId], dep_start: &[u32], deps: &[Dep]) -> Vec<UnitId> {
503    let mut stuck = vec![true; count];
504    for id in placed {
505        if let Some(slot) = stuck.get_mut(id.index()) {
506            *slot = false;
507        }
508    }
509
510    let Some(start) = (0..count).find(|&i| stuck.get(i).copied() == Some(true)) else {
511        return Vec::new();
512    };
513
514    let mut on_path = vec![usize::MAX; count];
515    let mut path: Vec<u32> = Vec::new();
516    let mut current = start as u32;
517
518    loop {
519        if let Some(&position) = on_path.get(current as usize) {
520            if position != usize::MAX {
521                let mut cycle: Vec<UnitId> = path
522                    .get(position..)
523                    .unwrap_or(&[])
524                    .iter()
525                    .map(|&n| UnitId(n))
526                    .collect();
527                // The walk followed edges from consumer to dependency; reverse it so the reported
528                // order runs from a dependency to the unit that depends on it.
529                cycle.reverse();
530                return cycle;
531            }
532        }
533        if let Some(slot) = on_path.get_mut(current as usize) {
534            *slot = path.len();
535        }
536        path.push(current);
537
538        let from = *dep_start.get(current as usize).unwrap_or(&0) as usize;
539        let to = dep_start
540            .get((current as usize).saturating_add(1))
541            .copied()
542            .unwrap_or(0) as usize;
543        let next = deps
544            .get(from..to)
545            .unwrap_or(&[])
546            .iter()
547            .filter(|d| stuck.get(d.unit.index()).copied() == Some(true))
548            .map(|d| d.unit.0)
549            .min();
550
551        match next {
552            Some(n) => current = n,
553            // Cannot happen for a unit Kahn's algorithm left in place, but returning what was
554            // found is better than looping.
555            None => return path.iter().map(|&n| UnitId(n)).collect(),
556        }
557    }
558}