cargo_resolvediff/
resolve.rs

1// Copyright (C) 2026 by GiGa infosystems
2
3//! Walks the `resolve` graph in an [`IndexedMetadata`] to gather dependency kinds & inclusion
4//! reasons
5
6use crate::Platform;
7use crate::indexed::IndexedMetadata;
8use camino::{Utf8Path, Utf8PathBuf};
9use cargo_metadata::PackageId;
10use color_eyre::Result;
11use semver::Version;
12use serde::Serialize;
13use std::{
14    borrow::Borrow,
15    collections::{BTreeMap, BTreeSet, btree_map},
16    fmt,
17    path::Path,
18};
19
20fn shorten_path_relative_to<'a>(relative: &Utf8Path, path: &'a Utf8Path) -> &'a Utf8Path {
21    if path.starts_with(relative) {
22        path.strip_prefix(relative).expect("checked above")
23    } else {
24        path
25    }
26}
27
28#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
29enum AnyCrateIdent {
30    Local(Utf8PathBuf),
31    CratesIo(String),
32}
33
34impl AnyCrateIdent {
35    fn from_package(relative: &Utf8Path, package: &cargo_metadata::Package) -> Self {
36        if package.source.is_some() {
37            AnyCrateIdent::CratesIo(package.name.to_string())
38        } else {
39            let path = package.manifest_path.parent().expect("ends in /Cargo.toml");
40            AnyCrateIdent::Local(shorten_path_relative_to(relative, path).to_owned())
41        }
42    }
43
44    fn with_version(self, version: &Version) -> SpecificAnyCrateIdent {
45        match self {
46            AnyCrateIdent::CratesIo(name) => SpecificAnyCrateIdent::CratesIo(SpecificCrateIdent {
47                name,
48                version: version.clone(),
49            }),
50            AnyCrateIdent::Local(manifest_path) => SpecificAnyCrateIdent::Local(manifest_path),
51        }
52    }
53}
54
55// A [crates.io] dependency with a specific version
56#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize)]
57pub struct SpecificCrateIdent {
58    pub name: String,
59    pub version: Version,
60}
61
62impl fmt::Debug for SpecificCrateIdent {
63    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
64        write!(f, "SpecificCrateIdent({self})")
65    }
66}
67
68impl fmt::Display for SpecificCrateIdent {
69    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
70        write!(f, "\"{} {}\"", self.name, self.version)
71    }
72}
73
74/// A [crates.io] dependency or a local dependency
75///
76/// (At the moment `git` dependencies get resolved as [crates.io] dependencies even if they are
77/// not)
78#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
79pub enum SpecificAnyCrateIdent {
80    Local(Utf8PathBuf),
81    CratesIo(SpecificCrateIdent),
82}
83
84impl fmt::Display for SpecificAnyCrateIdent {
85    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
86        match self {
87            SpecificAnyCrateIdent::Local(local) => write!(f, "{:?}", local),
88            SpecificAnyCrateIdent::CratesIo(ident) => write!(f, "{}", ident),
89        }
90    }
91}
92
93/// The kind of a dependency regarding when it is built or run
94#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Serialize)]
95pub struct DependencyKind {
96    /// The crate gets executed at some point at build time
97    pub run_at_build: bool,
98    /// The crate is only ever built as a `dev-dependency`
99    pub only_debug_builds: bool,
100}
101
102impl From<cargo_metadata::DependencyKind> for DependencyKind {
103    fn from(dependency_kind: cargo_metadata::DependencyKind) -> Self {
104        match dependency_kind {
105            cargo_metadata::DependencyKind::Normal => DependencyKind::NORMAL,
106            cargo_metadata::DependencyKind::Development => DependencyKind::DEVELOPMENT,
107            cargo_metadata::DependencyKind::Build => DependencyKind::BUILD,
108            kind => panic!("Unsupported dependency kind in `cargo_metadata`: {kind:?}"),
109        }
110    }
111}
112
113impl DependencyKind {
114    /// A dependency that is not run at build and included in release builds
115    pub const NORMAL: Self = DependencyKind {
116        run_at_build: false,
117        only_debug_builds: false,
118    };
119
120    /// A dependency that is not run at build and only included via `dev-dependencies`
121    pub const DEVELOPMENT: Self = DependencyKind {
122        run_at_build: false,
123        only_debug_builds: true,
124    };
125
126    /// A dependency that is run at build time for release builds
127    pub const BUILD: Self = DependencyKind {
128        run_at_build: true,
129        only_debug_builds: false,
130    };
131
132    /// Combine dependency kinds between a parent dependency and its edge to a child.
133    ///
134    /// If either is a build dependency, this sets `run_at_build`, and if either is only included
135    /// in `dev-dependencies`, this sets `only_debug_builds`.
136    pub const fn then(self, next: DependencyKind) -> Self {
137        DependencyKind {
138            run_at_build: self.run_at_build || next.run_at_build,
139            only_debug_builds: self.only_debug_builds || next.only_debug_builds,
140        }
141    }
142
143    /// Combine dependency kinds for a crate version coming from different paths.
144    ///
145    /// If either is a build dependency, this sets `run_at_build`, and `only_debug_builds` is only
146    /// set if both are only reachable via `dev-dependencies`.
147    pub const fn merged_with(self, other: DependencyKind) -> Self {
148        DependencyKind {
149            run_at_build: self.run_at_build || other.run_at_build,
150            only_debug_builds: self.only_debug_builds && other.only_debug_builds,
151        }
152    }
153}
154
155impl fmt::Debug for DependencyKind {
156    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
157        match (self.run_at_build, self.only_debug_builds) {
158            (false, false) => write!(f, "DependencyKind::NORMAL"),
159            (false, true) => write!(f, "DependencyKind::DEBUG"),
160            (true, false) => write!(f, "DependencyKind::BUILD"),
161            (true, true) => write!(f, "DependencyKind::DEBUG.then(DependencyKind::BUILD)"),
162        }
163    }
164}
165
166// NOTE: The intermediate dependencies may be local dependencies due to feature resolution, or path
167// dependencies outside of the workspace.
168/// The reason for the inclusion of a dependency in its specific form.
169#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
170pub struct IncludedDependencyReason {
171    /// The kind of inclusion edge, which is the [`DependencyKind`] of the parent
172    pub kind: DependencyKind,
173    /// The `Cargo.toml` in the workspace that this originated from
174    pub root: Utf8PathBuf,
175    /// The dependency in that `Cargo.toml` that then at some point ends up depending on `parent`
176    /// (if this is `None`, the dependency in the `Cargo.toml` is `parent`)
177    pub intermediate_root_dependency: Option<SpecificAnyCrateIdent>,
178    /// The dependency that directly depended on this crate
179    pub parent: SpecificAnyCrateIdent,
180}
181
182impl fmt::Debug for IncludedDependencyReason {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        write!(f, "IncludedDependencyReason({self})")
185    }
186}
187
188impl fmt::Display for IncludedDependencyReason {
189    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
190        if self.root != "" {
191            write!(f, "{:?}", self.root)?;
192        }
193        if let Some(ref intermediate) = self.intermediate_root_dependency {
194            write!(f, ".{intermediate}")?;
195            if self.parent != *intermediate {
196                write!(f, "...{}", self.parent)?;
197            }
198        }
199        Ok(())
200    }
201}
202
203impl Serialize for IncludedDependencyReason {
204    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
205        self.to_string().serialize(serializer)
206    }
207}
208
209/// The reasons for a dependencies inclusion mapped to a set of platforms.
210///
211/// NOTE: This set may be empty if an [`IndexedMetadata`] was included that didn't filter for a
212/// platform.
213pub type Reasons = BTreeMap<IncludedDependencyReason, BTreeSet<Platform>>;
214
215/// NOTE: Only keeps track of platforms that are explicitly listed in [`IndexedMetadata`]s that
216/// were passed, or alternatively the platforms given to [`Resolved::resolve_for`].
217pub struct IncludedDependencyVersion {
218    pub kind: DependencyKind,
219    pub has_build_rs: bool,
220    pub is_proc_macro: bool,
221    /// The reasons for the inclusion of this crate
222    pub reasons: Reasons,
223    /// The platforms this crate is included for that were filtered for in an [`IndexedMetadata`]
224    pub platforms: BTreeSet<Platform>,
225}
226
227/// The set of included packages, mapping from the crate name to a map from versions to the actual
228/// metadata
229pub type Included = BTreeMap<String, BTreeMap<Version, IncludedDependencyVersion>>;
230
231/// The set of fully resolved information ready for diffing with [`crate::diff::Diff`]
232pub struct Resolved {
233    /// The [`IndexedMetadata`] this is based on
234    pub full_metadata: IndexedMetadata,
235    /// The set of packages that are included in the filtered platforms, or all packages if an
236    /// unfiltered [`IndexedMetadata`] was included
237    pub included: Included,
238    /// The set of filtered packages, or
239    pub filtered: BTreeSet<SpecificCrateIdent>,
240}
241
242impl Resolved {
243    /// Resolve everything only for a given platform given its filtered [`IndexedMetadata`] (or the
244    /// unfiltered metadata if all platforms should be included)
245    fn resolve_platform(metadata: &IndexedMetadata, included: &mut Included) {
246        #[derive(Clone)]
247        enum TodoFrom<'a> {
248            Workspace(&'a Utf8Path),
249            Dependency(IncludedDependencyReason),
250        }
251
252        struct Todo<'a> {
253            kind: DependencyKind,
254            incoming_edge: TodoFrom<'a>,
255            pkg: &'a PackageId,
256        }
257
258        let mut todos = metadata
259            .get_workspace_default_members()
260            .iter()
261            .map(|pkg| {
262                let path = shorten_path_relative_to(
263                    &metadata.workspace_root,
264                    &metadata.packages[pkg].manifest_path,
265                );
266                Todo {
267                    kind: DependencyKind::NORMAL,
268                    incoming_edge: TodoFrom::Workspace(path),
269                    pkg,
270                }
271            })
272            .collect::<Vec<_>>();
273
274        while let Some(todo) = todos.pop() {
275            let package = &metadata.packages[todo.pkg];
276            let node = &metadata.resolve[todo.pkg];
277
278            let package_ident = AnyCrateIdent::from_package(&metadata.workspace_root, package);
279
280            let mut has_build_rs = false;
281            let mut is_proc_macro = false;
282            for target in package.targets.iter().flat_map(|target| &target.kind) {
283                use cargo_metadata::TargetKind;
284
285                match target {
286                    TargetKind::Bench
287                    | TargetKind::Bin
288                    | TargetKind::CDyLib
289                    | TargetKind::DyLib
290                    | TargetKind::Example
291                    | TargetKind::Lib
292                    | TargetKind::RLib
293                    | TargetKind::StaticLib
294                    | TargetKind::Test => (),
295                    TargetKind::CustomBuild => has_build_rs = true,
296                    TargetKind::ProcMacro => is_proc_macro = true,
297                    _ => panic!("Unknown target kind"),
298                }
299            }
300
301            let mut package_kind = todo.kind;
302            if is_proc_macro {
303                package_kind.run_at_build = true;
304            }
305
306            if let AnyCrateIdent::CratesIo(ref name) = package_ident {
307                let version = included
308                    .entry(name.clone())
309                    .or_default()
310                    .entry(package.version.clone());
311                let inserted_new = matches!(version, btree_map::Entry::Vacant(_));
312                let version = version.or_insert_with(|| IncludedDependencyVersion {
313                    kind: package_kind,
314                    has_build_rs,
315                    is_proc_macro,
316                    reasons: BTreeMap::new(),
317                    platforms: BTreeSet::new(),
318                });
319
320                let package_kind = version.kind.merged_with(package_kind);
321                let new_kind = package_kind != version.kind;
322                version.kind = package_kind;
323
324                // NOTE: A new reason isn't a cause to re-explore, as showing _some_ reasons is likely
325                // enough
326                match todo.incoming_edge {
327                    TodoFrom::Workspace(_) => (),
328                    TodoFrom::Dependency(ref reason) => {
329                        let entry = version.reasons.entry(reason.clone()).or_default(); // This gets added even if we don't add a platform
330                        if let Some(platform) = metadata.platform.clone() {
331                            entry.insert(platform);
332                        }
333                    }
334                };
335
336                let new_platform = metadata
337                    .platform
338                    .clone()
339                    .is_some_and(|platform| version.platforms.insert(platform));
340
341                if !(inserted_new || new_kind || new_platform) {
342                    continue;
343                }
344            }
345
346            let dep_parent = package_ident.with_version(&package.version);
347
348            todos.extend(node.deps.iter().filter_map(|dep| {
349                let dep_kind = dep
350                    .dep_kinds
351                    .iter()
352                    .filter(|kind| {
353                        // Dev dependencies of dependencies are not relevant
354                        matches!(todo.incoming_edge, TodoFrom::Workspace(_))
355                            || kind.kind != cargo_metadata::DependencyKind::Development
356                    })
357                    .map(|kind| package_kind.then(kind.kind.into()))
358                    .reduce(DependencyKind::merged_with)?;
359
360                let (root, intermediate_root_dependency) = match todo.incoming_edge {
361                    TodoFrom::Workspace(root) => (root.to_owned(), None),
362                    TodoFrom::Dependency(ref reason) => {
363                        let intermediate_root_dependency = reason
364                            .intermediate_root_dependency
365                            .clone()
366                            .unwrap_or_else(|| dep_parent.clone());
367
368                        (reason.root.clone(), Some(intermediate_root_dependency))
369                    }
370                };
371
372                Some(Todo {
373                    kind: dep_kind,
374                    incoming_edge: TodoFrom::Dependency(IncludedDependencyReason {
375                        kind: package_kind,
376                        root,
377                        intermediate_root_dependency,
378                        parent: dep_parent.clone(),
379                    }),
380                    pkg: &dep.pkg,
381                })
382            }));
383        }
384    }
385
386    /// Resolve everything from a given set of [`IndexedMetadata`]
387    pub fn resolve_from_indexed(
388        included: impl IntoIterator<Item: Borrow<IndexedMetadata>>,
389    ) -> Included {
390        let mut out = Included::new();
391        for included in included {
392            Self::resolve_platform(included.borrow(), &mut out);
393        }
394        out
395    }
396
397    /// Resolve the filtered dependencies from the given [`Included`] data and the set of
398    /// unfiltered [`IndexedMetadata`]
399    pub fn resolve_filtered_from_indexed(
400        included: Included,
401        full_metadata: IndexedMetadata,
402    ) -> Self {
403        assert_eq!(full_metadata.platform, None);
404
405        let mut filtered = BTreeSet::new();
406
407        for pkg in full_metadata.packages.values() {
408            if let AnyCrateIdent::CratesIo(name) =
409                AnyCrateIdent::from_package(&full_metadata.workspace_root, pkg)
410            {
411                let was_included = included
412                    .get(&name)
413                    .is_some_and(|versions| versions.contains_key(&pkg.version));
414                if !was_included {
415                    filtered.insert(SpecificCrateIdent {
416                        name,
417                        version: pkg.version.clone(),
418                    });
419                }
420            }
421        }
422
423        Resolved {
424            full_metadata,
425            included,
426            filtered,
427        }
428    }
429
430    /// Resolve everything for a given root manifest for the given set of platforms
431    pub fn resolve_from_path(
432        root_cargo_toml: &Path,
433        specific_platforms: impl IntoIterator<Item = Platform>,
434        include_all_platforms: bool,
435    ) -> Result<Self> {
436        let mut included = itertools::process_results(
437            specific_platforms
438                .into_iter()
439                .map(|platform| IndexedMetadata::gather(root_cargo_toml, Some(platform))),
440            |iter| Self::resolve_from_indexed(iter),
441        )?;
442
443        let full_metadata = IndexedMetadata::gather(root_cargo_toml, None)?;
444        let out = if include_all_platforms {
445            Self::resolve_platform(&full_metadata, &mut included);
446            Resolved {
447                full_metadata,
448                included,
449                filtered: BTreeSet::new(),
450            }
451        } else {
452            Self::resolve_filtered_from_indexed(included, full_metadata)
453        };
454
455        Ok(out)
456    }
457}
cargo_resolvediff/resolve.rs

cargo_resolvediff/
resolve.rs
