Skip to main content

cargo_critpath/
units.rs

1//! Pairing each `rustc` invocation with the timing report's entry for the same unit.
2//!
3//! The two inputs describe the same units and share almost no identifiers. The verbose log knows a
4//! unit by its crate name, its source path and its `-C extra-filename`; the timing report knows it
5//! by package name, version, a display string and a feature list. Matching them is the one place
6//! this adapter can be silently wrong, so it is done in stages of decreasing certainty, each stage
7//! records which one succeeded, and anything left over is a refusal rather than a smaller graph.
8
9use std::collections::BTreeMap;
10
11use critpath_core::UnitKind;
12
13use crate::error::{ParseError, UnitDescription};
14use crate::metadata::PackageIndex;
15use crate::timings::{TimingReport, TimingTarget, TimingUnit};
16use crate::verbose::{Invocation, Role, VerboseLog};
17
18/// How a unit's two halves were recognised as the same unit, in decreasing order of certainty.
19///
20/// Exposed because it is the honest answer to "how much do you trust this graph": a build whose
21/// units were all matched by [`Manifest`](MatchMethod::Manifest) or
22/// [`RegistryPath`](MatchMethod::RegistryPath) was identified exactly, and one that needed
23/// [`StartOrder`](MatchMethod::StartOrder) was not.
24#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
25#[non_exhaustive]
26pub enum MatchMethod {
27    /// The source path lay under a package's manifest directory, per `cargo metadata`. Exact.
28    Manifest,
29    /// The source path contained `name-version/`, as a registry or git checkout does. Exact.
30    RegistryPath,
31    /// The unit is a build script, and Cargo gives every build script a
32    /// `target/<profile>/build/<package>-<hash>` directory. Exact.
33    BuildDirectory,
34    /// The `--crate-name` matched a package or target name. Right unless a target was renamed.
35    CrateName,
36    /// The crate's own directory name matched a package name. A heuristic; a package need not be
37    /// named after its directory.
38    Directory,
39    /// Several candidates shared a name and version, and exactly one had the same feature set.
40    Features,
41    /// Several candidates were indistinguishable, so they were paired in the order each side lists
42    /// them. They differ only in weight, since everything else about them is identical.
43    StartOrder,
44    /// Exactly one unit of this kind was left unmatched on each side.
45    SoleCandidate,
46}
47
48impl MatchMethod {
49    /// A short stable name, for diagnostics.
50    #[must_use]
51    pub const fn as_str(self) -> &'static str {
52        match self {
53            Self::Manifest => "manifest",
54            Self::RegistryPath => "registry-path",
55            Self::BuildDirectory => "build-directory",
56            Self::CrateName => "crate-name",
57            Self::Directory => "directory",
58            Self::Features => "features",
59            Self::StartOrder => "start-order",
60            Self::SoleCandidate => "sole-candidate",
61        }
62    }
63
64    /// Whether this method identified the unit rather than deduced it.
65    #[must_use]
66    pub const fn is_exact(self) -> bool {
67        matches!(
68            self,
69            Self::Manifest | Self::RegistryPath | Self::BuildDirectory
70        )
71    }
72}
73
74/// One invocation paired with one timing entry.
75pub(crate) struct Pairing {
76    pub(crate) invocation: usize,
77    pub(crate) unit: usize,
78    pub(crate) method: MatchMethod,
79}
80
81/// The kinds of unit that can only ever match each other.
82#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
83enum Group {
84    /// A library of some sort: the timing report cannot say which.
85    Library,
86    BuildScriptCompile,
87    BuildScriptRun,
88    /// A named target, keyed on the kind Cargo printed, such as `bin`.
89    Named(String),
90}
91
92/// Pairs every invocation with its timing entry, or says exactly which ones it could not.
93pub(crate) fn pair(
94    log: &VerboseLog,
95    report: &TimingReport,
96    packages: Option<&PackageIndex>,
97) -> Result<Vec<Pairing>, ParseError> {
98    let mut index: BTreeMap<(Group, String), Vec<usize>> = BTreeMap::new();
99    for (position, unit) in report.units.iter().enumerate() {
100        let group = group_of_unit(&unit.target);
101        index
102            .entry((group.clone(), normalise(&unit.package)))
103            .or_default()
104            .push(position);
105        if let TimingTarget::Named { name, .. } = &unit.target {
106            let key = (group, normalise(name));
107            let slot = index.entry(key).or_default();
108            if !slot.contains(&position) {
109                slot.push(position);
110            }
111        }
112    }
113
114    // A build-script execution has no source path and no crate name of its own, but the directory
115    // it runs from carries the compiled script's `-C extra-filename`. Resolving that to the
116    // compilation gives the execution the same package, version and features, which is what
117    // separates two versions of one package that both have a build script.
118    let by_artifact: BTreeMap<&str, &Invocation> = log
119        .invocations
120        .iter()
121        .filter(|i| i.role == Role::Compile)
122        .filter_map(|i| Some((i.extra_filename.as_deref()?, i)))
123        .collect();
124
125    let mut claimed = vec![false; report.units.len()];
126    let mut pairings: Vec<Option<Pairing>> = Vec::with_capacity(log.invocations.len());
127
128    for (position, invocation) in log.invocations.iter().enumerate() {
129        let group = group_of_invocation(invocation);
130        let identity = identity_of(invocation, &by_artifact);
131        let mut found = None;
132        for (method, name, version) in candidates(invocation, identity, packages) {
133            let Some(pool) = index.get(&(group.clone(), normalise(&name))) else {
134                continue;
135            };
136            let available: Vec<usize> = pool
137                .iter()
138                .copied()
139                .filter(|&i| claimed.get(i) == Some(&false))
140                .collect();
141            if let Some((unit, refined)) =
142                choose(&available, &report.units, identity, version.as_deref())
143            {
144                found = Some(Pairing {
145                    invocation: position,
146                    unit,
147                    method: refined.unwrap_or(method),
148                });
149                break;
150            }
151        }
152        if let Some(pairing) = &found {
153            if let Some(slot) = claimed.get_mut(pairing.unit) {
154                *slot = true;
155            }
156        }
157        pairings.push(found);
158    }
159
160    // Anything still unmatched: if exactly one invocation and one unit of a kind are left, they are
161    // each other. This is what recovers a target whose name matches nothing, such as a binary in a
162    // package that renamed it.
163    resolve_sole_candidates(log, report, &mut pairings, &mut claimed);
164
165    let in_log: Vec<UnitDescription> = log
166        .invocations
167        .iter()
168        .zip(pairings.iter())
169        .filter(|(_, pairing)| pairing.is_none())
170        .map(|(invocation, _)| {
171            describe_invocation(invocation, identity_of(invocation, &by_artifact), packages)
172        })
173        .collect();
174    let in_report: Vec<UnitDescription> = report
175        .units
176        .iter()
177        .enumerate()
178        .filter(|(i, _)| claimed.get(*i) != Some(&true))
179        .map(|(_, unit)| describe_unit(unit))
180        .collect();
181
182    if !in_log.is_empty() || !in_report.is_empty() {
183        return Err(ParseError::UnmatchedUnits {
184            in_log,
185            in_report,
186            had_metadata: packages.is_some(),
187        });
188    }
189
190    Ok(pairings.into_iter().flatten().collect())
191}
192
193/// Picks one of several candidates.
194///
195/// Returns the chosen unit, and the method that separated it when the name alone did not.
196fn choose(
197    available: &[usize],
198    units: &[TimingUnit],
199    invocation: &Invocation,
200    version: Option<&str>,
201) -> Option<(usize, Option<MatchMethod>)> {
202    if available.is_empty() {
203        return None;
204    }
205    // A version from the source path or the manifest is part of the identity: a candidate with a
206    // different version is a different package, not a worse match.
207    let narrowed: Vec<usize> = match version {
208        Some(version) => {
209            let same: Vec<usize> = available
210                .iter()
211                .copied()
212                .filter(|&i| units.get(i).is_some_and(|u| u.version == version))
213                .collect();
214            if same.is_empty() {
215                return None;
216            }
217            same
218        }
219        None => available.to_vec(),
220    };
221
222    if let [only] = narrowed.as_slice() {
223        return Some((*only, None));
224    }
225
226    // Cargo can build one package twice at one version, for the host and for the target, and the
227    // two instances usually differ in their resolved features.
228    let same_features: Vec<usize> = narrowed
229        .iter()
230        .copied()
231        .filter(|&i| {
232            units
233                .get(i)
234                .is_some_and(|u| u.features == invocation.features)
235        })
236        .collect();
237    if let [only] = same_features.as_slice() {
238        return Some((*only, Some(MatchMethod::Features)));
239    }
240
241    // Otherwise the candidates are indistinguishable: same package, same version, same features.
242    // Both sides list units in start order, so the first unclaimed one is the best available
243    // answer, and the method records that it was not identified.
244    narrowed
245        .first()
246        .map(|&i| (i, Some(MatchMethod::StartOrder)))
247}
248
249fn resolve_sole_candidates(
250    log: &VerboseLog,
251    report: &TimingReport,
252    pairings: &mut [Option<Pairing>],
253    claimed: &mut [bool],
254) {
255    let outstanding: Vec<usize> = pairings
256        .iter()
257        .enumerate()
258        .filter(|(_, pairing)| pairing.is_none())
259        .map(|(i, _)| i)
260        .collect();
261    if outstanding.is_empty() {
262        return;
263    }
264
265    let mut by_group: BTreeMap<Group, (Vec<usize>, Vec<usize>)> = BTreeMap::new();
266    for position in outstanding {
267        if let Some(invocation) = log.invocations.get(position) {
268            by_group
269                .entry(group_of_invocation(invocation))
270                .or_default()
271                .0
272                .push(position);
273        }
274    }
275    for (position, unit) in report.units.iter().enumerate() {
276        if claimed.get(position) == Some(&true) {
277            continue;
278        }
279        by_group
280            .entry(group_of_unit(&unit.target))
281            .or_default()
282            .1
283            .push(position);
284    }
285
286    for (invocations, units) in by_group.into_values() {
287        let ([invocation], [unit]) = (invocations.as_slice(), units.as_slice()) else {
288            continue;
289        };
290        if let Some(slot) = pairings.get_mut(*invocation) {
291            *slot = Some(Pairing {
292                invocation: *invocation,
293                unit: *unit,
294                method: MatchMethod::SoleCandidate,
295            });
296        }
297        if let Some(slot) = claimed.get_mut(*unit) {
298            *slot = true;
299        }
300    }
301}
302
303/// Every name this invocation might be known by, most certain first.
304fn candidates(
305    invocation: &Invocation,
306    identity: &Invocation,
307    packages: Option<&PackageIndex>,
308) -> Vec<(MatchMethod, String, Option<String>)> {
309    let mut out: Vec<(MatchMethod, String, Option<String>)> = Vec::new();
310    let mut push = |method, name: &str, version: Option<String>| {
311        if name.is_empty() {
312            return;
313        }
314        out.push((method, name.to_owned(), version));
315    };
316
317    if let Some((name, version)) = manifest_package(identity, packages) {
318        push(MatchMethod::Manifest, &name, Some(version));
319    }
320    if let Some(package) = &identity.registry_package {
321        push(
322            MatchMethod::RegistryPath,
323            &package.name,
324            Some(package.version.clone()),
325        );
326    }
327    if let Some(package) = &invocation.run_package {
328        push(MatchMethod::BuildDirectory, package, None);
329    }
330    push(MatchMethod::CrateName, &invocation.crate_name, None);
331    if let Some(package) = &identity.directory_package {
332        push(MatchMethod::Directory, package, None);
333    }
334
335    out.dedup_by(|a, b| a.1 == b.1 && a.2 == b.2);
336    out
337}
338
339fn group_of_unit(target: &TimingTarget) -> Group {
340    match target {
341        TimingTarget::Library => Group::Library,
342        TimingTarget::BuildScriptCompile => Group::BuildScriptCompile,
343        TimingTarget::BuildScriptRun => Group::BuildScriptRun,
344        TimingTarget::Named { kind, .. } => Group::Named(kind.clone()),
345        TimingTarget::Other(text) => Group::Named(text.clone()),
346    }
347}
348
349fn group_of_invocation(invocation: &Invocation) -> Group {
350    if invocation.role == Role::BuildScriptRun {
351        return Group::BuildScriptRun;
352    }
353    match invocation.kind {
354        UnitKind::BuildScriptCompile => Group::BuildScriptCompile,
355        UnitKind::Bin => Group::Named("bin".to_owned()),
356        UnitKind::Test => Group::Named("test".to_owned()),
357        // A procedural macro renders as a library in the timing report, which is exactly why the
358        // verbose log is needed to tell them apart.
359        _ => Group::Library,
360    }
361}
362
363/// Package names use dashes and crate names use underscores for the same package.
364fn normalise(name: &str) -> String {
365    name.replace('-', "_")
366}
367
368/// The invocation whose identity applies: a build-script execution borrows its compilation's.
369fn identity_of<'a>(
370    invocation: &'a Invocation,
371    by_artifact: &BTreeMap<&str, &'a Invocation>,
372) -> &'a Invocation {
373    if invocation.role != Role::BuildScriptRun {
374        return invocation;
375    }
376    invocation
377        .run_artifact
378        .as_deref()
379        .and_then(|hash| by_artifact.get(hash).copied())
380        .unwrap_or(invocation)
381}
382
383/// The package a `cargo metadata` index attributes this invocation's source path to.
384fn manifest_package(
385    invocation: &Invocation,
386    packages: Option<&PackageIndex>,
387) -> Option<(String, String)> {
388    if invocation.source_path.is_empty() {
389        return None;
390    }
391    packages?
392        .package_at(&invocation.source_path)
393        .map(|(name, version)| (name.to_owned(), version.to_owned()))
394}
395
396fn describe_invocation(
397    invocation: &Invocation,
398    identity: &Invocation,
399    packages: Option<&PackageIndex>,
400) -> UnitDescription {
401    let (package, version) = manifest_package(identity, packages)
402        .or_else(|| {
403            identity
404                .registry_package
405                .as_ref()
406                .map(|p| (p.name.clone(), p.version.clone()))
407        })
408        .or_else(|| {
409            invocation
410                .run_package
411                .clone()
412                .map(|name| (name, String::new()))
413        })
414        .unwrap_or_else(|| (invocation.crate_name.clone(), String::new()));
415    UnitDescription {
416        package,
417        version,
418        target: invocation.kind.as_str().to_owned(),
419        position: invocation.position.saturating_add(1),
420    }
421}
422
423fn describe_unit(unit: &TimingUnit) -> UnitDescription {
424    UnitDescription {
425        package: unit.package.clone(),
426        version: unit.version.clone(),
427        target: unit.target.label().to_owned(),
428        position: unit.position.saturating_add(1),
429    }
430}