#
cargo/core/resolver/
resolve.rs

    1use cargo_util_schemas::core::PartialVersion;
    2use cargo_util_schemas::manifest::RustVersion;
    3
    4use super::encode::Metadata;
    5use crate::core::dependency::DepKind;
    6use crate::core::{Dependency, PackageId, PackageIdSpec, PackageIdSpecQuery, Summary, Target};
    7use crate::util::errors::CargoResult;
    8use crate::util::interning::InternedString;
    9use crate::util::Graph;
    10use std::borrow::Borrow;
    11use std::collections::{HashMap, HashSet};
    12use std::fmt;
    13
    14/// Represents a fully-resolved package dependency graph. Each node in the graph
    15/// is a package and edges represent dependencies between packages.
    16///
    17/// Each instance of `Resolve` also understands the full set of features used
    18/// for each package.
    19pub struct Resolve {
    20    /// A graph, whose vertices are packages and edges are dependency specifications
    21    /// from `Cargo.toml`. We need a `HashSet` here because the same package
    22    /// might be present in both `[dependencies]` and `[build-dependencies]`.
    23    graph: Graph<PackageId, HashSet<Dependency>>,
    24    /// Replacements from the `[replace]` table.
    25    replacements: HashMap<PackageId, PackageId>,
    26    /// Inverted version of `replacements`.
    27    reverse_replacements: HashMap<PackageId, PackageId>,
    28    /// Features enabled for a given package.
    29    features: HashMap<PackageId, Vec<InternedString>>,
    30    /// Checksum for each package. A SHA256 hash of the `.crate` file used to
    31    /// validate the correct crate file is used. This is `None` for sources
    32    /// that do not use `.crate` files, like path or git dependencies.
    33    checksums: HashMap<PackageId, Option<String>>,
    34    /// "Unknown" metadata. This is a collection of extra, unrecognized data
    35    /// found in the `[metadata]` section of `Cargo.lock`, preserved for
    36    /// forwards compatibility.
    37    metadata: Metadata,
    38    /// `[patch]` entries that did not match anything, preserved in
    39    /// `Cargo.lock` as the `[[patch.unused]]` table array. Tracking unused
    40    /// patches helps prevent Cargo from being forced to re-update the
    41    /// registry every time it runs, and keeps the resolve in a locked state
    42    /// so it doesn't re-resolve the unused entries.
    43    unused_patches: Vec<PackageId>,
    44    /// A map from packages to a set of their public dependencies
    45    public_dependencies: HashMap<PackageId, HashSet<PackageId>>,
    46    /// Version of the `Cargo.lock` format, see
    47    /// `cargo::core::resolver::encode` for more.
    48    version: ResolveVersion,
    49    summaries: HashMap<PackageId, Summary>,
    50}
    51
    52/// A version to indicate how a `Cargo.lock` should be serialized.
    53///
    54/// When creating a new lockfile, the version in [`ResolveVersion::default`] is used.
    55/// If an old version of lockfile already exists, it will stay as-is.
    56///
    57/// It's important that if a new version is added that this is not updated
    58/// until *at least* the support for the version is in the stable release of Rust.
    59///
    60/// This resolve version will be used for all new lock files, for example
    61/// those generated by `cargo update` (update everything) or building after
    62/// a `cargo new` (where no lock file previously existed). This is also used
    63/// for *updated* lock files such as when a dependency is added or when a
    64/// version requirement changes. In this situation Cargo's updating the lock
    65/// file anyway so it takes the opportunity to bump the lock file version
    66/// forward.
    67///
    68/// It's theorized that we can add more here over time to track larger changes
    69/// to the `Cargo.lock` format, but we've yet to see how that strategy pans out.
    70#[derive(PartialEq, Eq, Clone, Copy, Debug, PartialOrd, Ord)]
    71pub enum ResolveVersion {
    72    /// Historical baseline for when this abstraction was added.
    73    V1,
    74    /// A more compact format, more amenable to avoiding source-control merge
    75    /// conflicts. The `dependencies` arrays are compressed and checksums are
    76    /// listed inline.
    77    ///
    78    /// * Introduced in 2019 in version 1.38.
    79    /// * New lockfiles use V2 by default from 1.41 to 1.52.
    80    V2,
    81    /// A format that explicitly lists a `version` at the top of the file as
    82    /// well as changing how git dependencies are encoded. Dependencies with
    83    /// `branch = "master"` are no longer encoded the same way as those without
    84    /// branch specifiers.
    85    ///
    86    /// * Introduced in 2020 in version 1.47.
    87    /// * New lockfiles use V3 by default from in 1.53 to 1.82.
    88    V3,
    89    /// `SourceId` URL serialization is aware of URL encoding. For example,
    90    /// `?branch=foo bar` is now encoded as `?branch=foo+bar` and can be decoded
    91    /// back and forth correctly.
    92    ///
    93    /// * Introduced in 2024 in version 1.78.
    94    /// * New lockfiles use V4 by default starting in 1.83.
    95    V4,
    96    /// Unstable. Will collect a certain amount of changes and then go.
    97    ///
    98    /// Changes made:
    99    V5,
    100}
    101
    102impl ResolveVersion {
    103    /// Gets the default lockfile version.
    104    ///
    105    /// This is intended to be private.
    106    /// You shall use [`ResolveVersion::with_rust_version`] always.
    107    ///
    108    /// Update this and the description of enum variants of [`ResolveVersion`]
    109    /// when we're changing the default lockfile version.
    110    fn default() -> ResolveVersion {
    111        ResolveVersion::V4
    112    }
    113
    114    /// The maximum version of lockfile made into the stable channel.
    115    ///
    116    /// Any version larger than this needs `-Znext-lockfile-bump` to enable.
    117    ///
    118    /// Update this when you're going to stabilize a new lockfile format.
    119    pub fn max_stable() -> ResolveVersion {
    120        ResolveVersion::V4
    121    }
    122
    123    /// Gets the default lockfile version for the given Rust version.
    124    pub fn with_rust_version(rust_version: Option<&RustVersion>) -> Self {
    125        let Some(rust_version) = rust_version else {
    126            return ResolveVersion::default();
    127        };
    128
    129        let rust = |major, minor| -> RustVersion {
    130            PartialVersion {
    131                major,
    132                minor: Some(minor),
    133                patch: None,
    134                pre: None,
    135                build: None,
    136            }
    137            .try_into()
    138            .unwrap()
    139        };
    140
    141        if rust_version >= &rust(1, 83) {
    142            ResolveVersion::V4
    143        } else if rust_version >= &rust(1, 53) {
    144            ResolveVersion::V3
    145        } else if rust_version >= &rust(1, 41) {
    146            ResolveVersion::V2
    147        } else {
    148            ResolveVersion::V1
    149        }
    150    }
    151}
    152
    153impl Resolve {
    154    pub fn new(
    155        graph: Graph<PackageId, HashSet<Dependency>>,
    156        replacements: HashMap<PackageId, PackageId>,
    157        features: HashMap<PackageId, Vec<InternedString>>,
    158        checksums: HashMap<PackageId, Option<String>>,
    159        metadata: Metadata,
    160        unused_patches: Vec<PackageId>,
    161        version: ResolveVersion,
    162        summaries: HashMap<PackageId, Summary>,
    163    ) -> Resolve {
    164        let reverse_replacements = replacements.iter().map(|(&p, &r)| (r, p)).collect();
    165        let public_dependencies = graph
    166            .iter()
    167            .map(|p| {
    168                let public_deps = graph
    169                    .edges(p)
    170                    .filter(|(_, deps)| {
    171                        deps.iter()
    172                            .any(|d| d.kind() == DepKind::Normal && d.is_public())
    173                    })
    174                    .map(|(dep_package, _)| *dep_package)
    175                    .collect::<HashSet<PackageId>>();
    176
    177                (*p, public_deps)
    178            })
    179            .collect();
    180
    181        Resolve {
    182            graph,
    183            replacements,
    184            features,
    185            checksums,
    186            metadata,
    187            unused_patches,
    188            reverse_replacements,
    189            public_dependencies,
    190            version,
    191            summaries,
    192        }
    193    }
    194
    195    /// Resolves one of the paths from the given dependent package up to
    196    /// the root.
    197    pub fn path_to_top<'a>(
    198        &'a self,
    199        pkg: &'a PackageId,
    200    ) -> Vec<(&'a PackageId, Option<&'a HashSet<Dependency>>)> {
    201        self.graph.path_to_top(pkg)
    202    }
    203
    204    pub fn register_used_patches<'a>(&mut self, patches: impl Iterator<Item = &'a Summary>) {
    205        for summary in patches {
    206            if !self.graph.contains(&summary.package_id()) {
    207                self.unused_patches.push(summary.package_id())
    208            };
    209        }
    210    }
    211
    212    pub fn merge_from(&mut self, previous: &Resolve) -> CargoResult<()> {
    213        // Given a previous instance of resolve, it should be forbidden to ever
    214        // have a checksums which *differ*. If the same package ID has differing
    215        // checksums, then something has gone wrong such as:
    216        //
    217        // * Something got seriously corrupted
    218        // * A "mirror" isn't actually a mirror as some changes were made
    219        // * A replacement source wasn't actually a replacement, some changes
    220        //   were made
    221        //
    222        // In all of these cases, we want to report an error to indicate that
    223        // something is awry. Normal execution (esp just using crates.io) should
    224        // never run into this.
    225        for (id, cksum) in previous.checksums.iter() {
    226            if let Some(mine) = self.checksums.get(id) {
    227                if mine == cksum {
    228                    continue;
    229                }
    230
    231                // If the previous checksum wasn't calculated, the current
    232                // checksum is `Some`. This may indicate that a source was
    233                // erroneously replaced or was replaced with something that
    234                // desires stronger checksum guarantees than can be afforded
    235                // elsewhere.
    236                if cksum.is_none() {
    237                    anyhow::bail!(
    238                        "\
    239checksum for `{}` was not previously calculated, but a checksum could now \
    240be calculated
    241
    242this could be indicative of a few possible situations:
    243
    244    * the source `{}` did not previously support checksums,
    245      but was replaced with one that does
    246    * newer Cargo implementations know how to checksum this source, but this
    247      older implementation does not
    248    * the lock file is corrupt
    249",
    250                        id,
    251                        id.source_id()
    252                    )
    253
    254                // If our checksum hasn't been calculated, then it could mean
    255                // that future Cargo figured out how to checksum something or
    256                // more realistically we were overridden with a source that does
    257                // not have checksums.
    258                } else if mine.is_none() {
    259                    anyhow::bail!(
    260                        "\
    261checksum for `{}` could not be calculated, but a checksum is listed in \
    262the existing lock file
    263
    264this could be indicative of a few possible situations:
    265
    266    * the source `{}` supports checksums,
    267      but was replaced with one that doesn't
    268    * the lock file is corrupt
    269
    270unable to verify that `{0}` is the same as when the lockfile was generated
    271",
    272                        id,
    273                        id.source_id()
    274                    )
    275
    276                // If the checksums aren't equal, and neither is None, then they
    277                // must both be Some, in which case the checksum now differs.
    278                // That's quite bad!
    279                } else {
    280                    anyhow::bail!(
    281                        "\
    282checksum for `{}` changed between lock files
    283
    284this could be indicative of a few possible errors:
    285
    286    * the lock file is corrupt
    287    * a replacement source in use (e.g., a mirror) returned a different checksum
    288    * the source itself may be corrupt in one way or another
    289
    290unable to verify that `{0}` is the same as when the lockfile was generated
    291",
    292                        id
    293                    );
    294                }
    295            }
    296        }
    297
    298        // Be sure to just copy over any unknown metadata.
    299        self.metadata = previous.metadata.clone();
    300
    301        // Preserve the lockfile encoding where possible to avoid lockfile churn
    302        self.version = previous.version;
    303
    304        Ok(())
    305    }
    306
    307    pub fn contains<Q: ?Sized>(&self, k: &Q) -> bool
    308    where
    309        PackageId: Borrow<Q>,
    310        Q: Ord + Eq,
    311    {
    312        self.graph.contains(k)
    313    }
    314
    315    pub fn sort(&self) -> Vec<PackageId> {
    316        self.graph.sort()
    317    }
    318
    319    pub fn iter(&self) -> impl Iterator<Item = PackageId> + '_ {
    320        self.graph.iter().cloned()
    321    }
    322
    323    pub fn len(&self) -> usize {
    324        self.graph.len()
    325    }
    326
    327    pub fn deps(&self, pkg: PackageId) -> impl Iterator<Item = (PackageId, &HashSet<Dependency>)> {
    328        self.deps_not_replaced(pkg)
    329            .map(move |(id, deps)| (self.replacement(id).unwrap_or(id), deps))
    330    }
    331
    332    pub fn deps_not_replaced(
    333        &self,
    334        pkg: PackageId,
    335    ) -> impl Iterator<Item = (PackageId, &HashSet<Dependency>)> {
    336        self.graph.edges(&pkg).map(|(id, deps)| (*id, deps))
    337    }
    338
    339    // Only edges that are transitive, filtering out edges between a crate and its dev-dependency
    340    // since that doesn't count for cycles.
    341    pub fn transitive_deps_not_replaced(
    342        &self,
    343        pkg: PackageId,
    344    ) -> impl Iterator<Item = (PackageId, &Dependency)> {
    345        self.graph.edges(&pkg).filter_map(|(id, deps)| {
    346            deps.iter()
    347                .find(|d| d.is_transitive())
    348                .map(|transitive_dep| (*id, transitive_dep))
    349        })
    350    }
    351
    352    pub fn replacement(&self, pkg: PackageId) -> Option<PackageId> {
    353        self.replacements.get(&pkg).cloned()
    354    }
    355
    356    pub fn replacements(&self) -> &HashMap<PackageId, PackageId> {
    357        &self.replacements
    358    }
    359
    360    pub fn features(&self, pkg: PackageId) -> &[InternedString] {
    361        self.features.get(&pkg).map(|v| &**v).unwrap_or(&[])
    362    }
    363
    364    /// This is only here for legacy support, it will be removed when
    365    /// switching to the new feature resolver.
    366    pub fn features_clone(&self) -> HashMap<PackageId, Vec<InternedString>> {
    367        self.features.clone()
    368    }
    369
    370    pub fn is_public_dep(&self, pkg: PackageId, dep: PackageId) -> bool {
    371        self.public_dependencies
    372            .get(&pkg)
    373            .map(|public_deps| public_deps.contains(&dep))
    374            .unwrap_or_else(|| panic!("Unknown dependency {:?} for package {:?}", dep, pkg))
    375    }
    376
    377    pub fn query(&self, spec: &str) -> CargoResult<PackageId> {
    378        PackageIdSpec::query_str(spec, self.iter())
    379    }
    380
    381    pub fn specs_to_ids(&self, specs: &[PackageIdSpec]) -> CargoResult<Vec<PackageId>> {
    382        specs.iter().map(|s| s.query(self.iter())).collect()
    383    }
    384
    385    pub fn unused_patches(&self) -> &[PackageId] {
    386        &self.unused_patches
    387    }
    388
    389    pub fn checksums(&self) -> &HashMap<PackageId, Option<String>> {
    390        &self.checksums
    391    }
    392
    393    pub fn metadata(&self) -> &Metadata {
    394        &self.metadata
    395    }
    396
    397    pub fn extern_crate_name_and_dep_name(
    398        &self,
    399        from: PackageId,
    400        to: PackageId,
    401        to_target: &Target,
    402    ) -> CargoResult<(InternedString, Option<InternedString>)> {
    403        let empty_set: HashSet<Dependency> = HashSet::new();
    404        let deps = if from == to {
    405            &empty_set
    406        } else {
    407            self.dependencies_listed(from, to)
    408        };
    409
    410        let target_crate_name = || (to_target.crate_name(), None);
    411        let mut name_pairs = deps.iter().map(|d| {
    412            d.explicit_name_in_toml()
    413                .map(|s| (s.as_str().replace("-", "_"), Some(s)))
    414                .unwrap_or_else(target_crate_name)
    415        });
    416        let (extern_crate_name, dep_name) = name_pairs.next().unwrap_or_else(target_crate_name);
    417        for (n, _) in name_pairs {
    418            anyhow::ensure!(
    419                n == extern_crate_name,
    420                "the crate `{}` depends on crate `{}` multiple times with different names",
    421                from,
    422                to,
    423            );
    424        }
    425        Ok((extern_crate_name.into(), dep_name))
    426    }
    427
    428    fn dependencies_listed(&self, from: PackageId, to: PackageId) -> &HashSet<Dependency> {
    429        // We've got a dependency on `from` to `to`, but this dependency edge
    430        // may be affected by [replace]. If the `to` package is listed as the
    431        // target of a replacement (aka the key of a reverse replacement map)
    432        // then we try to find our dependency edge through that. If that fails
    433        // then we go down below assuming it's not replaced.
    434        //
    435        // Note that we don't treat `from` as if it's been replaced because
    436        // that's where the dependency originates from, and we only replace
    437        // targets of dependencies not the originator.
    438        if let Some(replace) = self.reverse_replacements.get(&to) {
    439            if let Some(deps) = self.graph.edge(&from, replace) {
    440                return deps;
    441            }
    442        }
    443        match self.graph.edge(&from, &to) {
    444            Some(ret) => ret,
    445            None => panic!("no Dependency listed for `{}` => `{}`", from, to),
    446        }
    447    }
    448
    449    /// Returns the version of the encoding that's being used for this lock
    450    /// file.
    451    pub fn version(&self) -> ResolveVersion {
    452        self.version
    453    }
    454
    455    pub fn set_version(&mut self, version: ResolveVersion) {
    456        self.version = version;
    457    }
    458
    459    pub fn summary(&self, pkg_id: PackageId) -> &Summary {
    460        &self.summaries[&pkg_id]
    461    }
    462}
    463
    464impl PartialEq for Resolve {
    465    fn eq(&self, other: &Resolve) -> bool {
    466        macro_rules! compare {
    467            ($($fields:ident)* | $($ignored:ident)*) => {
    468                let Resolve { $($fields,)* $($ignored: _,)* } = self;
    469                $($fields == &other.$fields)&&*
    470            }
    471        }
    472        compare! {
    473            // fields to compare
    474            graph replacements reverse_replacements features
    475            checksums metadata unused_patches public_dependencies summaries
    476            |
    477            // fields to ignore
    478            version
    479        }
    480    }
    481}
    482
    483impl fmt::Debug for Resolve {
    484    fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
    485        writeln!(fmt, "graph: {:?}", self.graph)?;
    486        writeln!(fmt, "\nfeatures: {{")?;
    487        for (pkg, features) in &self.features {
    488            writeln!(fmt, "  {}: {:?}", pkg, features)?;
    489        }
    490        write!(fmt, "}}")
    491    }
    492}