Repository: rust-lang/cargo (rust)

Issue:
MSRV resolver has surprising behaviour in workspaces with mixed MSRV
### Problem

As state by @epage in https://github.com/rust-lang/cargo/issues/13873#issuecomment-2284833685 , a new issue was preferred for this. The issue is that the new MSRV aware resolver leads to surprising and suboptimal behaviour in a workspace with mixed MSRV:

* https://github.com/rust-lang/cargo/issues/13873#issuecomment-2282698377
* https://github.com/rust-lang/cargo/issues/13873#issuecomment-2284759998
* https://github.com/rust-lang/cargo/issues/13873#issuecomment-2282712218

The issue is that (for whatever reason) you have a workspace where one (or more) of you crates is on a much older MSRV than the rest. Then the MSRV aware resolver will attempt to create a lockfile for all of the workspace based on that *oldest version* even if the dependency in question isn't even used by that old-MSRV crate. In certain cases this can cause there to be no possible solutions to the dependency resolution (as detailed by the comment linked in the third bullet point above).

There are valid reasons to have mixed MSRV, such as the different crates having different MSRV policy. or just that some crates naturally have solver development and don't need to be bumped to a newer MSRV as often as other crates.

I will here describe my use case where I run into this (I cannot speak for the cases where others run into this as what @Darksonn described):

I have a workspace I use to develop a command line program. Having it all the related crates (both the main binary and supporting libraries) all in one workspace makes development much easier, especially during the early phases when everything is evolving rapidly. Some of these crates are generally useful to others as well (file format parsers in my case).

I also have an agressive MSRV policy: only N-2 is guaranteed (but I won't bump MSRV gratuitously just for the sake of it, so actual MSRV can be much further back).

Eventually some of these crates will start to stabilise, especially the "leaf node" supporting crates with simple and clearly defined scope. There is only so many things you need in a library that parses a file format. That means it won't get breaking changes nor get published to crates.io as often. And also that there will be *no reason* to bump MSRV.

Now the problem here is that this leaf node dependency with older MSRV will now drag down the versions of dependencies that get used for my main crate of the workspace (the "flagship" binary crate).

### Steps

1. Have a (virtual?, I don't know if it affects non-virtual as well) workspace with mixed MSRV
2. `CARGO_RESOLVER_INCOMPATIBLE_RUST_VERSIONS=fallback cargo +nightly -Zmsrv-policy generate-lockfile`

### Possible Solution(s)

Possible solutions (and why they are suboptimal):
* I could bump the MSRV and publish releases to crates.io that are nothing but "bump MSRV". This leads to churn and "pointless" releases from the point of view of everyone else.
* I could selectively publish single crates from the workspace (update the MSRV of the dependency crates but don't publish them). It would be error prone:
  * I would need to ensure that I didn't start depending on any "unreleased commits". Sounds like I need a "cargo-reverse-semver-checks"?
  * This would be complicated since I automate publishing from CI using release-plz. Partial publishing is as far as I understand not supported with the automated CI/PR workflow, only when publishing locally from your own computer (which is bad practise).

The better option would seem to me that cargo would consider the entire dependency graph when writing the lock file and look at what dependencies are reachable from what crates, and compute the minimum needed MSRV for each dependency.

### Notes

_No response_

### Version

```text
❯ cargo +nightly version --verbose
cargo 1.82.0-nightly (2f738d617 2024-08-13)
release: 1.82.0-nightly
commit-hash: 2f738d617c6ead388f899802dd1a7fd66858a691
commit-date: 2024-08-13
host: x86_64-unknown-linux-gnu
libgit2: 1.8.1 (sys:0.19.0 vendored)
libcurl: 8.9.0-DEV (sys:0.4.74+curl-8.9.0 vendored ssl:OpenSSL/1.1.1w)
ssl: OpenSSL 1.1.1w  11 Sep 2023
os: Arch Linux Rolling Release [64-bit]
```


Pull request description:
fix(resolve): Improve multi-MSRV workspaces 
### What does this PR try to resolve?

We do this by resolving for a package version that is compatible
with the most number of MSRVs within a workspace.

If a version requirement is just right, every package will get the
highest MSRV-compatible dependency.

If its too high, packages will get MSRV-incompatible dependency
versions.
This will happen regardless of what we do due to the nature of
`"fallback"`.

If its too low, packages with higher MSRVs will get older-than-necessary
dependency versions.
This is similar to the "some with and without MSRV" workspaces.
When locking dependencies, we do report to users when newer MSRV/SemVer
compatible dependencies are available to help guide them to upgrading if
desired.

Fixes #14414

### How should we test and review this PR?

Is this the right behavior?
- This feature is unstable and letting people try it is one way to determine that
- A concern was raised within the Cargo team about new users with workspace member MSRVs all set to latest having someone ask them to lower an MSRV and them dealing with staler-than-required dependencies
  - At this point, there seems to be agreement on #14414 being a problem, the resolver magically fixing this is unlikely to happen for the foreseeable future, and this does fix it with the potential for user confusion.  From my understanding of those conversations, they are mostly in the area of UX, like with #14543.  Rather than blocking on that discussion, this moves forward with the implementation.

### Additional information


Patch:
diff --git a/src/cargo/core/resolver/version_prefs.rs b/src/cargo/core/resolver/version_prefs.rs
index c89c13fdd..61f174049 100644
--- a/src/cargo/core/resolver/version_prefs.rs
+++ b/src/cargo/core/resolver/version_prefs.rs
@@ -21,7 +21,7 @@ pub struct VersionPreferences {
     try_to_use: HashSet<PackageId>,
     prefer_patch_deps: HashMap<InternedString, HashSet<Dependency>>,
     version_ordering: VersionOrdering,
-    max_rust_version: Option<PartialVersion>,
+    rust_versions: Vec<PartialVersion>,
 }
 
 #[derive(Copy, Clone, Default, PartialEq, Eq, Hash, Debug)]
@@ -49,8 +49,8 @@ impl VersionPreferences {
         self.version_ordering = ordering;
     }
 
-    pub fn max_rust_version(&mut self, ver: Option<PartialVersion>) {
-        self.max_rust_version = ver;
+    pub fn rust_versions(&mut self, vers: Vec<PartialVersion>) {
+        self.rust_versions = vers;
     }
 
     /// Sort (and filter) the given vector of summaries in-place
@@ -59,7 +59,7 @@ impl VersionPreferences {
     ///
     /// Sort order:
     /// 1. Preferred packages
-    /// 2. [`VersionPreferences::max_rust_version`]
+    /// 2. Most compatible [`VersionPreferences::rust_versions`]
     /// 3. `first_version`, falling back to [`VersionPreferences::version_ordering`] when `None`
     ///
     /// Filtering:
@@ -85,20 +85,11 @@ impl VersionPreferences {
                 return previous_cmp;
             }
 
-            if let Some(max_rust_version) = &self.max_rust_version {
-                let a_is_compat = a
-                    .rust_version()
-                    .map(|a| a.is_compatible_with(max_rust_version))
-                    .unwrap_or(true);
-                let b_is_compat = b
-                    .rust_version()
-                    .map(|b| b.is_compatible_with(max_rust_version))
-                    .unwrap_or(true);
-                match (a_is_compat, b_is_compat) {
-                    (true, true) => {}   // fallback
-                    (false, false) => {} // fallback
-                    (true, false) => return Ordering::Less,
-                    (false, true) => return Ordering::Greater,
+            if !self.rust_versions.is_empty() {
+                let a_compat_count = self.msrv_compat_count(a);
+                let b_compat_count = self.msrv_compat_count(b);
+                if b_compat_count != a_compat_count {
+                    return b_compat_count.cmp(&a_compat_count);
                 }
             }
 
@@ -112,6 +103,17 @@ impl VersionPreferences {
             let _ = summaries.split_off(1);
         }
     }
+
+    fn msrv_compat_count(&self, summary: &Summary) -> usize {
+        let Some(rust_version) = summary.rust_version() else {
+            return self.rust_versions.len();
+        };
+
+        self.rust_versions
+            .iter()
+            .filter(|max| rust_version.is_compatible_with(max))
+            .count()
+    }
 }
 
 #[cfg(test)]
@@ -236,9 +238,9 @@ mod test {
     }
 
     #[test]
-    fn test_max_rust_version() {
+    fn test_single_rust_version() {
         let mut vp = VersionPreferences::default();
-        vp.max_rust_version(Some("1.50".parse().unwrap()));
+        vp.rust_versions(vec!["1.50".parse().unwrap()]);
 
         let mut summaries = vec![
             summ("foo", "1.2.4", None),
@@ -267,6 +269,38 @@ mod test {
         );
     }
 
+    #[test]
+    fn test_multiple_rust_versions() {
+        let mut vp = VersionPreferences::default();
+        vp.rust_versions(vec!["1.45".parse().unwrap(), "1.55".parse().unwrap()]);
+
+        let mut summaries = vec![
+            summ("foo", "1.2.4", None),
+            summ("foo", "1.2.3", Some("1.60")),
+            summ("foo", "1.2.2", None),
+            summ("foo", "1.2.1", Some("1.50")),
+            summ("foo", "1.2.0", None),
+            summ("foo", "1.1.0", Some("1.40")),
+            summ("foo", "1.0.9", None),
+        ];
+
+        vp.version_ordering(VersionOrdering::MaximumVersionsFirst);
+        vp.sort_summaries(&mut summaries, None);
+        assert_eq!(
+            describe(&summaries),
+            "foo/1.2.4, foo/1.2.2, foo/1.2.0, foo/1.1.0, foo/1.0.9, foo/1.2.1, foo/1.2.3"
+                .to_string()
+        );
+
+        vp.version_ordering(VersionOrdering::MinimumVersionsFirst);
+        vp.sort_summaries(&mut summaries, None);
+        assert_eq!(
+            describe(&summaries),
+            "foo/1.0.9, foo/1.1.0, foo/1.2.0, foo/1.2.2, foo/1.2.4, foo/1.2.1, foo/1.2.3"
+                .to_string()
+        );
+    }
+
     #[test]
     fn test_empty_summaries() {
         let vp = VersionPreferences::default();
diff --git a/src/cargo/core/workspace.rs b/src/cargo/core/workspace.rs
index 28897365b..44066ec7a 100644
--- a/src/cargo/core/workspace.rs
+++ b/src/cargo/core/workspace.rs
@@ -664,7 +664,7 @@ impl<'gctx> Workspace<'gctx> {
 
     /// Get the lowest-common denominator `package.rust-version` within the workspace, if specified
     /// anywhere
-    pub fn rust_version(&self) -> Option<&RustVersion> {
+    pub fn lowest_rust_version(&self) -> Option<&RustVersion> {
         self.members().filter_map(|pkg| pkg.rust_version()).min()
     }
 
diff --git a/src/cargo/ops/cargo_update.rs b/src/cargo/ops/cargo_update.rs
index ce25a951e..0c9b885da 100644
--- a/src/cargo/ops/cargo_update.rs
+++ b/src/cargo/ops/cargo_update.rs
@@ -739,7 +739,7 @@ fn required_rust_version(ws: &Workspace<'_>) -> Option<PartialVersion> {
         return None;
     }
 
-    if let Some(ver) = ws.rust_version() {
+    if let Some(ver) = ws.lowest_rust_version() {
         Some(ver.clone().into_partial())
     } else {
         let rustc = ws.gctx().load_global_rustc(Some(ws)).ok()?;
diff --git a/src/cargo/ops/lockfile.rs b/src/cargo/ops/lockfile.rs
index d865a7186..07985e42a 100644
--- a/src/cargo/ops/lockfile.rs
+++ b/src/cargo/ops/lockfile.rs
@@ -71,7 +71,7 @@ pub fn write_pkg_lockfile(ws: &Workspace<'_>, resolve: &mut Resolve) -> CargoRes
     // out lock file updates as they're otherwise already updated, and changes
     // which don't touch dependencies won't seemingly spuriously update the lock
     // file.
-    let default_version = ResolveVersion::with_rust_version(ws.rust_version());
+    let default_version = ResolveVersion::with_rust_version(ws.lowest_rust_version());
     let current_version = resolve.version();
     let next_lockfile_bump = ws.gctx().cli_unstable().next_lockfile_bump;
     tracing::debug!("lockfile - current: {current_version:?}, default: {default_version:?}");
diff --git a/src/cargo/ops/registry/info/mod.rs b/src/cargo/ops/registry/info/mod.rs
index 39bbb4861..0075e71fa 100644
--- a/src/cargo/ops/registry/info/mod.rs
+++ b/src/cargo/ops/registry/info/mod.rs
@@ -217,6 +217,6 @@ fn try_get_msrv_from_nearest_manifest_or_ws(
     let rust_version = nearest_package.and_then(|p| p.rust_version().map(|v| v.as_partial()));
     // If the nearest manifest does not have a specific Rust version, try to get it from the workspace.
     rust_version
-        .or_else(|| ws.and_then(|ws| ws.rust_version().map(|v| v.as_partial())))
+        .or_else(|| ws.and_then(|ws| ws.lowest_rust_version().map(|v| v.as_partial())))
         .cloned()
 }
diff --git a/src/cargo/ops/resolve.rs b/src/cargo/ops/resolve.rs
index 65b3f2b68..223833ac8 100644
--- a/src/cargo/ops/resolve.rs
+++ b/src/cargo/ops/resolve.rs
@@ -79,6 +79,7 @@ use crate::util::errors::CargoResult;
 use crate::util::CanonicalUrl;
 use anyhow::Context as _;
 use cargo_util::paths;
+use cargo_util_schemas::core::PartialVersion;
 use std::collections::{HashMap, HashSet};
 use tracing::{debug, trace};
 
@@ -357,14 +358,16 @@ pub fn resolve_with_previous<'gctx>(
         version_prefs.version_ordering(VersionOrdering::MinimumVersionsFirst)
     }
     if ws.resolve_honors_rust_version() {
-        let rust_version = if let Some(ver) = ws.rust_version() {
-            ver.clone().into_partial()
-        } else {
+        let mut rust_versions: Vec<_> = ws
+            .members()
+            .filter_map(|p| p.rust_version().map(|rv| rv.as_partial().clone()))
+            .collect();
+        if rust_versions.is_empty() {
             let rustc = ws.gctx().load_global_rustc(Some(ws))?;
-            let rustc_version = rustc.version.clone().into();
-            rustc_version
-        };
-        version_prefs.max_rust_version(Some(rust_version));
+            let rust_version: PartialVersion = rustc.version.clone().into();
+            rust_versions.push(rust_version);
+        }
+        version_prefs.rust_versions(rust_versions);
     }
 
     let avoid_patch_ids = if register_patches {
@@ -422,7 +425,7 @@ pub fn resolve_with_previous<'gctx>(
         &replace,
         registry,
         &version_prefs,
-        ResolveVersion::with_rust_version(ws.rust_version()),
+        ResolveVersion::with_rust_version(ws.lowest_rust_version()),
         Some(ws.gctx()),
     )?;
 
diff --git a/src/doc/src/reference/unstable.md b/src/doc/src/reference/unstable.md
index 0dc370cc7..84c08860e 100644
--- a/src/doc/src/reference/unstable.md
+++ b/src/doc/src/reference/unstable.md
@@ -348,7 +348,9 @@ This was stabilized in 1.79 in [#13608](https://github.com/rust-lang/cargo/pull/
 - `package.edition = "2024"` (only in workspace root)
 
 The resolver will prefer dependencies with a `package.rust-version` that is the same or older than your project's MSRV.
-Your project's MSRV is determined by taking the lowest `package.rust-version` set among your workspace members.
+As the resolver is unable to determine which workspace members will eventually
+depend on a package when it is being selected, we prioritize versions based on
+how many workspace member MSRVs they are compatible with.
 If there is no MSRV set then your toolchain version will be used, allowing it to pick up the toolchain version from pinned in rustup (e.g. `rust-toolchain.toml`).
 
 #### `resolver.incompatible-rust-versions`


Test patch:
diff --git a/tests/testsuite/rust_version.rs b/tests/testsuite/rust_version.rs
index c00ff012e..c36416e64 100644
--- a/tests/testsuite/rust_version.rs
+++ b/tests/testsuite/rust_version.rs
@@ -409,22 +409,36 @@ foo v0.0.1 ([ROOT]/foo)
 
 #[cargo_test]
 fn resolve_with_multiple_rust_versions() {
-    Package::new("only-newer", "1.6.0")
+    Package::new(&format!("shared-only-newer"), "1.65.0")
         .rust_version("1.65.0")
         .file("src/lib.rs", "fn other_stuff() {}")
         .publish();
-    Package::new("newer-and-older", "1.5.0")
-        .rust_version("1.45.0")
-        .file("src/lib.rs", "fn other_stuff() {}")
-        .publish();
-    Package::new("newer-and-older", "1.5.1")
-        .rust_version("1.55.0")
+    for ver in ["1.45.0", "1.55.0", "1.65.0"] {
+        Package::new(&format!("shared-newer-and-older"), ver)
+            .rust_version(ver)
+            .file("src/lib.rs", "fn other_stuff() {}")
+            .publish();
+    }
+    Package::new(&format!("lower-only-newer"), "1.65.0")
+        .rust_version("1.65.0")
         .file("src/lib.rs", "fn other_stuff() {}")
         .publish();
-    Package::new("newer-and-older", "1.6.0")
+    for ver in ["1.45.0", "1.55.0"] {
+        Package::new(&format!("lower-newer-and-older"), ver)
+            .rust_version(ver)
+            .file("src/lib.rs", "fn other_stuff() {}")
+            .publish();
+    }
+    Package::new(&format!("higher-only-newer"), "1.65.0")
         .rust_version("1.65.0")
         .file("src/lib.rs", "fn other_stuff() {}")
         .publish();
+    for ver in ["1.55.0", "1.65.0"] {
+        Package::new(&format!("higher-newer-and-older"), ver)
+            .rust_version(ver)
+            .file("src/lib.rs", "fn other_stuff() {}")
+            .publish();
+    }
 
     let p = project()
         .file(
@@ -441,8 +455,10 @@ fn resolve_with_multiple_rust_versions() {
             rust-version = "1.60.0"
 
             [dependencies]
-            only-newer = "1.0.0"
-            newer-and-older = "1.0.0"
+            higher-only-newer = "1"
+            higher-newer-and-older = "1"
+            shared-only-newer = "1"
+            shared-newer-and-older = "1"
         "#,
         )
         .file("src/main.rs", "fn main() {}")
@@ -457,8 +473,10 @@ fn resolve_with_multiple_rust_versions() {
             rust-version = "1.50.0"
 
             [dependencies]
-            only-newer = "1.0.0"
-            newer-and-older = "1.0.0"
+            lower-only-newer = "1"
+            lower-newer-and-older = "1"
+            shared-only-newer = "1"
+            shared-newer-and-older = "1"
         "#,
         )
         .file("lower/src/main.rs", "fn main() {}")
@@ -470,15 +488,17 @@ fn resolve_with_multiple_rust_versions() {
         .masquerade_as_nightly_cargo(&["msrv-policy"])
         .with_stderr_data(str![[r#"
 [UPDATING] `dummy-registry` index
-[LOCKING] 2 packages to latest compatible versions
+[LOCKING] 6 packages to latest compatible versions
 
 "#]])
         .run();
     p.cargo("tree")
         .with_stdout_data(str![[r#"
 higher v0.0.1 ([ROOT]/foo)
-├── newer-and-older v1.6.0
-└── only-newer v1.6.0
+├── higher-newer-and-older v1.65.0
+├── higher-only-newer v1.65.0
+├── shared-newer-and-older v1.65.0
+└── shared-only-newer v1.65.0
 
 "#]])
         .run();
@@ -489,17 +509,23 @@ higher v0.0.1 ([ROOT]/foo)
         .masquerade_as_nightly_cargo(&["msrv-policy"])
         .with_stderr_data(str![[r#"
 [UPDATING] `dummy-registry` index
-[LOCKING] 2 packages to latest Rust 1.50.0 compatible versions
-[ADDING] newer-and-older v1.5.0 (available: v1.6.0, requires Rust 1.65.0)
-[ADDING] only-newer v1.6.0 (requires Rust 1.65.0)
+[LOCKING] 6 packages to latest Rust 1.50.0 compatible versions
+[ADDING] higher-newer-and-older v1.55.0 (available: v1.65.0, requires Rust 1.65.0)
+[ADDING] higher-only-newer v1.65.0 (requires Rust 1.65.0)
+[ADDING] lower-newer-and-older v1.45.0 (available: v1.55.0, requires Rust 1.55.0)
+[ADDING] lower-only-newer v1.65.0 (requires Rust 1.65.0)
+[ADDING] shared-newer-and-older v1.45.0 (available: v1.65.0, requires Rust 1.65.0)
+[ADDING] shared-only-newer v1.65.0 (requires Rust 1.65.0)
 
 "#]])
         .run();
     p.cargo("tree")
         .with_stdout_data(str![[r#"
 higher v0.0.1 ([ROOT]/foo)
-├── newer-and-older v1.5.0
-└── only-newer v1.6.0
+├── higher-newer-and-older v1.55.0
+├── higher-only-newer v1.65.0
+├── shared-newer-and-older v1.45.0
+└── shared-only-newer v1.65.0
 
 "#]])
         .run();