Skip to main content

cargo_critpath/
input.rs

1//! Assembling the matched halves into a graph, and everything a report needs to say where it came
2//! from.
3
4use std::collections::{BTreeMap, BTreeSet};
5
6use critpath_core::{BuildGraph, EdgeKind, GraphBuilder, Millis, Unit, UnitId, UnitKind};
7
8use crate::error::{ParseError, UnitDescription};
9use crate::metadata::PackageIndex;
10use crate::timings::{TimingReport, TimingUnit};
11use crate::units::{self, MatchMethod};
12use crate::verbose::{Invocation, Role, VerboseLog};
13
14/// How serious a diagnostic is.
15///
16/// Only `Warning` is produced today: anything bad enough to stop the analysis is refused as a
17/// [`crate::ParseError`] instead. The type is open so that a severity can be added without a
18/// breaking release, and a caller must tolerate one it does not know.
19#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
20#[non_exhaustive]
21pub enum Severity {
22    /// Something the reader should know, which did not stop the analysis.
23    Warning,
24}
25
26/// Something worth telling the reader about the input, which was not bad enough to refuse.
27#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
28#[non_exhaustive]
29pub struct Diagnostic {
30    /// How serious it is.
31    pub severity: Severity,
32    /// A stable kebab-case identifier, which is the field to match on.
33    pub code: &'static str,
34    /// Prose, which may change in any release.
35    pub message: String,
36}
37
38/// Which of the report's `unblocked_*` fields a pair came from.
39#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
40pub enum UnblockedSource {
41    /// The producer finished.
42    Completion,
43    /// The producer emitted its metadata.
44    Metadata,
45}
46
47/// One pair the timing report claims a dependency between.
48#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
49#[non_exhaustive]
50pub struct UnblockedPair {
51    /// The unit that unblocked the other.
52    pub producer: UnitId,
53    /// The unit that was unblocked.
54    pub consumer: UnitId,
55    /// What the producer had to do for it.
56    pub source: UnblockedSource,
57}
58
59/// The result of checking the report's `unblocked_*` fields against the graph the log gave.
60#[derive(Clone, Debug, PartialEq, Eq)]
61#[non_exhaustive]
62pub struct UnblockedCheck {
63    /// How many pairs the report recorded.
64    pub total: usize,
65    /// How many of them the graph agrees are dependencies.
66    pub confirmed: usize,
67    /// The ones it does not, which is a defect in the parser rather than in Cargo.
68    pub unconfirmed: Vec<UnblockedPair>,
69}
70
71impl UnblockedCheck {
72    /// Whether every pair the report recorded is a dependency the graph has.
73    #[must_use]
74    pub fn is_consistent(&self) -> bool {
75        self.unconfirmed.is_empty()
76    }
77}
78
79/// Where a build's numbers came from.
80///
81/// Every field the timing report does not state is `None` rather than guessed. `cargo_version` is
82/// one of those: the report's header names the `rustc` version and not Cargo's, so a caller that
83/// knows it should fill this in.
84#[derive(Clone, Debug, PartialEq, Eq, Default)]
85#[non_exhaustive]
86pub struct BuildMeta {
87    /// The Cargo version, which the timing report does not state.
88    pub cargo_version: Option<String>,
89    /// The `rustc` version, from the timing report's header.
90    pub rustc_version: Option<String>,
91    /// The host triple.
92    pub host: Option<String>,
93    /// The target triple.
94    pub target: Option<String>,
95    /// The profile the build used.
96    pub profile: Option<String>,
97    /// The `-j` the build ran with.
98    pub jobs: Option<u32>,
99    /// The machine's processor count.
100    pub cpus: Option<u32>,
101    /// The peak number of units Cargo actually had in flight, which can exceed `jobs` because a
102    /// build-script execution takes no compile token.
103    pub observed_max_concurrency: Option<u32>,
104    /// Units in the build.
105    pub units_total: usize,
106    /// Of those, units that were reused from the cache. Always zero, since a build with any is
107    /// refused.
108    pub units_fresh: usize,
109    /// The last unit's end minus the first unit's start.
110    pub compilation_span: Millis,
111    /// Cargo's own total for the build.
112    pub reported_total: Option<Millis>,
113    /// The reported total minus the compilation span: fetching, resolution, and anything else
114    /// outside the unit model. Reported rather than folded in.
115    pub excluded_prefix: Millis,
116    /// The targets the build was asked for, as the report's header displays them.
117    pub targets: Option<String>,
118    /// When the build started, exactly as the report wrote it.
119    pub build_start: Option<String>,
120}
121
122/// One build, ready to analyse.
123#[derive(Clone, Debug)]
124#[non_exhaustive]
125pub struct BuildInput {
126    /// The graph the two inputs agreed on.
127    pub graph: BuildGraph,
128    /// Where its numbers came from.
129    pub build: BuildMeta,
130    /// How each unit's two halves were recognised as the same unit, by unit identifier. A build
131    /// whose entries are all exact was identified rather than deduced.
132    pub matched_by: Vec<MatchMethod>,
133    /// The pairs the timing report claims are dependencies, for [`check_unblocked`].
134    ///
135    /// [`check_unblocked`]: BuildInput::check_unblocked
136    pub unblocked: Vec<UnblockedPair>,
137    /// Anything worth telling the reader that did not stop the analysis.
138    pub diagnostics: Vec<Diagnostic>,
139}
140
141impl BuildInput {
142    /// Checks the timing report's `unblocked_*` fields against the graph the verbose log gave.
143    ///
144    /// The fields are not the dependency graph — they record only the unit that happened to be each
145    /// unit's *last* blocker, which covered 51% of the real edges on a measured 28-unit build — but
146    /// every pair in them must still be a dependency. That makes them an independent check on the
147    /// matcher and the edge rules, from data the parser did not use to build the graph.
148    ///
149    /// A pair is confirmed when the graph has the edge, or when the consumer requires its whole
150    /// closure and the producer is somewhere in it. The second case is not a concession: Cargo's own
151    /// job queue materialises exactly those closure edges for a unit that needs upstream object
152    /// files, and this model expresses them as a property of the consumer instead.
153    #[must_use]
154    pub fn check_unblocked(&self) -> UnblockedCheck {
155        let mut pairs = self.unblocked.clone();
156        // Grouped by consumer so that each closure is computed once.
157        pairs.sort();
158
159        let mut confirmed = 0usize;
160        let mut unconfirmed = Vec::new();
161        let mut closure_of: Option<(UnitId, BTreeSet<UnitId>)> = None;
162
163        for pair in &pairs {
164            let direct = self
165                .graph
166                .dependencies(pair.consumer)
167                .is_some_and(|deps| deps.iter().any(|d| d.unit == pair.producer));
168            if direct {
169                confirmed = confirmed.saturating_add(1);
170                continue;
171            }
172            let needs_closure = self
173                .graph
174                .unit(pair.consumer)
175                .is_some_and(|u| u.requires_full_closure);
176            if needs_closure {
177                let cached = match &closure_of {
178                    Some((consumer, set)) if *consumer == pair.consumer => set,
179                    _ => {
180                        closure_of = Some((pair.consumer, self.closure(pair.consumer)));
181                        match &closure_of {
182                            Some((_, set)) => set,
183                            None => continue,
184                        }
185                    }
186                };
187                if cached.contains(&pair.producer) {
188                    confirmed = confirmed.saturating_add(1);
189                    continue;
190                }
191            }
192            unconfirmed.push(*pair);
193        }
194
195        UnblockedCheck {
196            total: pairs.len(),
197            confirmed,
198            unconfirmed,
199        }
200    }
201
202    /// Every unit the given one transitively depends on.
203    fn closure(&self, unit: UnitId) -> BTreeSet<UnitId> {
204        let mut seen = BTreeSet::new();
205        let mut stack: Vec<UnitId> = self
206            .graph
207            .dependencies(unit)
208            .unwrap_or_default()
209            .iter()
210            .map(|d| d.unit)
211            .collect();
212        while let Some(next) = stack.pop() {
213            if !seen.insert(next) {
214                continue;
215            }
216            for dep in self.graph.dependencies(next).unwrap_or_default() {
217                stack.push(dep.unit);
218            }
219        }
220        seen
221    }
222}
223
224/// Everything a matched unit needs before it becomes a node.
225struct Assembled<'a> {
226    invocation: &'a Invocation,
227    timing: &'a TimingUnit,
228    method: MatchMethod,
229}
230
231/// Builds the graph from a matched verbose log and timing report.
232pub(crate) fn assemble(
233    log: &VerboseLog,
234    report: &TimingReport,
235    packages: Option<&PackageIndex>,
236) -> Result<BuildInput, ParseError> {
237    if report.units.is_empty() {
238        return Err(ParseError::EmptyBuild);
239    }
240    let pairings = units::pair(log, report, packages)?;
241
242    let mut assembled: Vec<Assembled<'_>> = Vec::with_capacity(pairings.len());
243    for pairing in &pairings {
244        let (Some(invocation), Some(timing)) = (
245            log.invocations.get(pairing.invocation),
246            report.units.get(pairing.unit),
247        ) else {
248            continue;
249        };
250        assembled.push(Assembled {
251            invocation,
252            timing,
253            method: pairing.method,
254        });
255    }
256
257    // Invariant I1: the graph must be reproducible, so units enter it in an order derived from
258    // their identity rather than from the order Cargo happened to start them. The compilation hash
259    // is the tie-break of last resort, because two instances of one package can agree on everything
260    // else.
261    assembled.sort_by(|a, b| {
262        a.timing
263            .package
264            .cmp(&b.timing.package)
265            .then_with(|| a.timing.version.cmp(&b.timing.version))
266            .then_with(|| a.timing.target.label().cmp(b.timing.target.label()))
267            .then_with(|| a.invocation.kind.as_str().cmp(b.invocation.kind.as_str()))
268            .then_with(|| a.invocation.metadata_hash.cmp(&b.invocation.metadata_hash))
269            .then_with(|| a.timing.index.cmp(&b.timing.index))
270    });
271
272    let mut diagnostics: Vec<Diagnostic> = Vec::new();
273    let mut builder = GraphBuilder::with_capacity(assembled.len());
274    let mut matched_by = Vec::with_capacity(assembled.len());
275    let mut ids = Vec::with_capacity(assembled.len());
276
277    for entry in &assembled {
278        // Sections appear for pipelined units, but it is the compiler invocation that decides
279        // whether anything may start against this unit early, so the log has the last word.
280        let metadata_at = if entry.invocation.pipelined {
281            entry.timing.metadata_at
282        } else {
283            None
284        };
285        let id = builder.add_unit(Unit {
286            package: entry.timing.package.clone(),
287            version: entry.timing.version.clone(),
288            target: entry.timing.target.label().to_owned(),
289            kind: entry.invocation.kind,
290            total: entry.timing.duration,
291            metadata_at,
292            requires_full_closure: entry.invocation.requires_full_closure,
293        })?;
294        ids.push(id);
295        matched_by.push(entry.method);
296    }
297
298    add_dependency_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
299    add_build_script_edges(&assembled, &ids, &mut builder, &mut diagnostics)?;
300
301    let graph = builder.build()?;
302    let unblocked = unblocked_pairs(&assembled, &ids);
303    report_inexact_matches(&matched_by, &mut diagnostics);
304
305    Ok(BuildInput {
306        graph,
307        build: meta(report),
308        matched_by,
309        unblocked,
310        diagnostics,
311    })
312}
313
314/// Edges named by `--extern`, which is every dependency Cargo passes to the compiler.
315fn add_dependency_edges(
316    assembled: &[Assembled<'_>],
317    ids: &[UnitId],
318    builder: &mut GraphBuilder,
319    diagnostics: &mut Vec<Diagnostic>,
320) -> Result<(), ParseError> {
321    let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
322    for (entry, id) in assembled.iter().zip(ids.iter()) {
323        if let Some(hash) = &entry.invocation.extra_filename {
324            by_artifact.insert(hash.as_str(), *id);
325        }
326    }
327
328    for (entry, consumer) in assembled.iter().zip(ids.iter()) {
329        for dependency in &entry.invocation.externs {
330            let Some(hash) = &dependency.producer else {
331                diagnostics.push(Diagnostic {
332                    severity: Severity::Warning,
333                    code: "extern-without-artifact-hash",
334                    message: format!(
335                        "{} names `{}` through an artifact with no compilation hash, so it is not \
336                         one of this build's units and no edge was added for it",
337                        label(entry),
338                        dependency.name
339                    ),
340                });
341                continue;
342            };
343            let Some(producer) = by_artifact.get(hash.as_str()).copied() else {
344                return Err(ParseError::UnresolvedDependency {
345                    consumer: Box::new(describe(entry)),
346                    dependency: dependency.name.clone(),
347                    producer: hash.clone(),
348                });
349            };
350            let kind = downgrade(
351                dependency.edge,
352                producer,
353                assembled,
354                ids,
355                entry,
356                diagnostics,
357            );
358            builder.add_edge(producer, *consumer, kind)?;
359        }
360    }
361    Ok(())
362}
363
364/// A metadata edge whose producer emits no metadata cannot be honoured, and the core rejects it.
365/// Treating it as a full edge is the conservative reading; treating it as satisfied immediately
366/// would be optimistic, which is the direction that must never be taken silently.
367fn downgrade(
368    kind: EdgeKind,
369    producer: UnitId,
370    assembled: &[Assembled<'_>],
371    ids: &[UnitId],
372    consumer: &Assembled<'_>,
373    diagnostics: &mut Vec<Diagnostic>,
374) -> EdgeKind {
375    if kind != EdgeKind::Metadata {
376        return kind;
377    }
378    let emits = ids
379        .iter()
380        .position(|id| *id == producer)
381        .and_then(|at| assembled.get(at))
382        .is_some_and(|entry| entry.invocation.pipelined && entry.timing.metadata_at.is_some());
383    if emits {
384        return EdgeKind::Metadata;
385    }
386    diagnostics.push(Diagnostic {
387        severity: Severity::Warning,
388        code: "metadata-edge-without-metadata",
389        message: format!(
390            "{} was given a dependency as metadata, but the timing report records no metadata \
391             moment for it, so the edge was treated as needing the whole dependency; \
392             the critical path this produces is an upper bound rather than an estimate",
393            label(consumer)
394        ),
395    });
396    EdgeKind::Full
397}
398
399/// Cargo's three-unit build-script pattern, which no `--extern` names: compiling the script, running
400/// it, and the package's own units waiting on the run.
401fn add_build_script_edges(
402    assembled: &[Assembled<'_>],
403    ids: &[UnitId],
404    builder: &mut GraphBuilder,
405    diagnostics: &mut Vec<Diagnostic>,
406) -> Result<(), ParseError> {
407    let mut by_artifact: BTreeMap<&str, UnitId> = BTreeMap::new();
408    for (entry, id) in assembled.iter().zip(ids.iter()) {
409        if let Some(hash) = &entry.invocation.extra_filename {
410            by_artifact.insert(hash.as_str(), *id);
411        }
412    }
413
414    for (entry, run) in assembled.iter().zip(ids.iter()) {
415        if entry.invocation.role != Role::BuildScriptRun {
416            continue;
417        }
418        // The run executes out of `build/<package>-<hash>`, and that hash is the compiled script's
419        // own `-C extra-filename`, so the compile-to-run edge is stated by the log rather than
420        // guessed from a name.
421        let Some(hash) = &entry.invocation.run_artifact else {
422            return Err(ParseError::UnresolvedDependency {
423                consumer: Box::new(describe(entry)),
424                dependency: "its compiled build script".to_owned(),
425                producer: "<no compilation hash in the execution path>".to_owned(),
426            });
427        };
428        let Some(compile) = by_artifact.get(hash.as_str()).copied() else {
429            return Err(ParseError::UnresolvedDependency {
430                consumer: Box::new(describe(entry)),
431                dependency: "its compiled build script".to_owned(),
432                producer: hash.clone(),
433            });
434        };
435        builder.add_edge(compile, *run, EdgeKind::Full)?;
436
437        // Everything else Cargo built for the same package instance waits for the run. Features
438        // separate two instances of one package at one version; where they do not, the fallback
439        // widens to the whole package and says so, because a missing edge understates the critical
440        // path and a spurious one does not.
441        let mut dependents = package_units(assembled, ids, entry, true);
442        if dependents.is_empty() {
443            dependents = package_units(assembled, ids, entry, false);
444            if !dependents.is_empty() {
445                diagnostics.push(Diagnostic {
446                    severity: Severity::Warning,
447                    code: "build-script-instance-ambiguous",
448                    message: format!(
449                        "the build script of {} shares no feature set with any of that package's \
450                         compilations, so every one of them was made to wait for it; \
451                         if the package is built twice with different features this is stricter \
452                         than the real build",
453                        label(entry)
454                    ),
455                });
456            }
457        }
458        for dependent in dependents {
459            builder.add_edge(*run, dependent, EdgeKind::Full)?;
460        }
461    }
462    Ok(())
463}
464
465/// The compilations belonging to the same package instance as a build-script execution.
466fn package_units(
467    assembled: &[Assembled<'_>],
468    ids: &[UnitId],
469    run: &Assembled<'_>,
470    match_features: bool,
471) -> Vec<UnitId> {
472    assembled
473        .iter()
474        .zip(ids.iter())
475        .filter(|(entry, _)| {
476            entry.invocation.kind != UnitKind::BuildScriptCompile
477                && entry.invocation.kind != UnitKind::BuildScriptRun
478                && entry.timing.package == run.timing.package
479                && entry.timing.version == run.timing.version
480                && (!match_features || entry.timing.features == run.timing.features)
481        })
482        .map(|(_, id)| *id)
483        .collect()
484}
485
486/// The report's `unblocked_*` fields, translated into unit identifiers.
487fn unblocked_pairs(assembled: &[Assembled<'_>], ids: &[UnitId]) -> Vec<UnblockedPair> {
488    let mut by_index: BTreeMap<usize, UnitId> = BTreeMap::new();
489    for (entry, id) in assembled.iter().zip(ids.iter()) {
490        by_index.insert(entry.timing.index, *id);
491    }
492
493    let mut pairs = Vec::new();
494    for (entry, producer) in assembled.iter().zip(ids.iter()) {
495        for (indices, source) in [
496            (&entry.timing.unblocked, UnblockedSource::Completion),
497            (&entry.timing.unblocked_rmeta, UnblockedSource::Metadata),
498        ] {
499            for index in indices.iter() {
500                if let Some(consumer) = by_index.get(index).copied() {
501                    pairs.push(UnblockedPair {
502                        producer: *producer,
503                        consumer,
504                        source,
505                    });
506                }
507            }
508        }
509    }
510    pairs.sort();
511    pairs.dedup();
512    pairs
513}
514
515fn report_inexact_matches(methods: &[MatchMethod], diagnostics: &mut Vec<Diagnostic>) {
516    let ordered = methods.iter().filter(|m| **m == MatchMethod::StartOrder);
517    let count = ordered.count();
518    if count > 0 {
519        diagnostics.push(Diagnostic {
520            severity: Severity::Warning,
521            code: "units-matched-by-order",
522            message: format!(
523                "{count} unit(s) could not be told apart from another unit of the same package, \
524                 version and feature set, so each was paired with a timing entry by start order; \
525                 they differ only in weight, and swapping two of them would move work between two \
526                 identical compilations"
527            ),
528        });
529    }
530}
531
532fn meta(report: &TimingReport) -> BuildMeta {
533    BuildMeta {
534        cargo_version: None,
535        rustc_version: report.rustc_version.clone(),
536        host: report.host.clone(),
537        target: report.target.clone(),
538        profile: report.profile.clone(),
539        jobs: report.jobs,
540        cpus: report.cpus,
541        observed_max_concurrency: report.max_concurrency,
542        units_total: report.total_units,
543        units_fresh: report.fresh_units,
544        compilation_span: report.compilation_span(),
545        reported_total: report.reported_total,
546        excluded_prefix: report.excluded_prefix(),
547        targets: report.targets.clone(),
548        build_start: report.build_start.clone(),
549    }
550}
551
552fn label(entry: &Assembled<'_>) -> String {
553    format!(
554        "{} {} ({})",
555        entry.timing.package,
556        entry.timing.version,
557        entry.timing.target.label()
558    )
559}
560
561fn describe(entry: &Assembled<'_>) -> UnitDescription {
562    UnitDescription {
563        package: entry.timing.package.clone(),
564        version: entry.timing.version.clone(),
565        target: entry.timing.target.label().to_owned(),
566        position: entry.timing.position.saturating_add(1),
567    }
568}