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}