Local version identifiers are not ignored when testing version equality

[SnoopJ]

Platform: Ubuntu 22.04
uv version: 0.1.6 (da3a7ec)

Spill-over from #1853, while checking that --editable gave the intended behavior on that ticket, I discovered that uv seems to be including local version identifiers of candidates when considering a requirement that has no local version identifier

$ uv pip install --find-links https://download.pytorch.org/whl/torch_stable.html "torch==2.0.0+cu118" "torchvision==0.15.1+cu118"
  × No solution found when resolving dependencies:
  ╰─▶ Because torchvision==0.15.1+cu118 depends on torch==2.0.0 and you require torch==2.0.0+cu118, we can conclude that root==0a0.dev0 and torchvision==0.15.1+cu118
      are incompatible.
      And because you require torchvision==0.15.1+cu118, we can conclude that the requirements are unsatisfiable.

The PyPA Version Specifiers standard (and PEP 440 before it) states that:

If the specified version identifier is a public version identifier (no local version label), then the local version label of any candidate versions MUST be ignored when matching versions.

If the specified version identifier is a local version identifier, then the local version labels of candidate versions MUST be considered when matching versions, with the public version identifier being matched as described above, and the local version label being checked for equivalence using a strict string equality comparison.

My understanding of that passage is that torchvision depends on torch==2.0.0 (i.e. it declares its dependency against a public version identifier), so the equality comparison MUST ignore any local version identifier (like +cu118) when considering candidate versions of torch.

As I understand it, the current behavior of uv would be correct if torchvision declared a dependency on torch==2.0.0+… that had a local segment that was not exactly +cu118, but it's doing the wrong thing for the public version identifier.

(As an aside, I'm not sure what root==0a0.dev0 is about? Perhaps some kind of meta-requirement associated with my entire request? I don't think it's related to the failure here, but I do find it confusing in the report)

[charliermarsh]

Thanks! @BurntSushi - do you mind taking a look?

[charliermarsh]

My first thought was something like:

--- a/crates/pep440-rs/src/version.rs
+++ b/crates/pep440-rs/src/version.rs
@@ -564,7 +564,19 @@ impl Version {
         }

         // release is equal, so compare the other parts
-        sortable_tuple(self).cmp(&sortable_tuple(other))
+        match sortable_tuple(self).cmp(&sortable_tuple(other)) {
+            Ordering::Less => return Ordering::Less,
+            Ordering::Equal => {},
+            Ordering::Greater => return Ordering::Greater,
+        }
+
+        // post- and pre-releases are equal, so compare the local
+        match (self.local(), other.local()) {
+            ([], []) => Ordering::Equal,
+            ([], _) => Ordering::Equal,
+            (_, []) => Ordering::Equal,
+            (a, b) => a.cmp(b),
+        }
     }
 }

@@ -2203,7 +2215,7 @@ pub(crate) fn compare_release(this: &[u64], other: &[u64]) -> Ordering {
 /// aN, bN, rcN, <no suffix (final)>, .postN but also, you can have dev/post
 /// releases on beta releases, so we make a three stage ordering: ({dev: 0, a:
 /// 1, b: 2, rc: 3, (): 4, post: 5}, <preN>, <postN or None as smallest>, <devN
-/// or Max as largest>, <local>)
+/// or Max as largest>)
 ///
 /// For post, any number is better than none (so None defaults to None<0),
 /// but for dev, no number is better (so None default to the maximum). For
@@ -2211,10 +2223,10 @@ pub(crate) fn compare_release(this: &[u64], other: &[u64]) -> Ordering {
 /// implementation
 ///
 /// [pep440-suffix-ordering]: https://peps.python.org/pep-0440/#summary-of-permitted-suffixes-and-relative-ordering
-fn sortable_tuple(version: &Version) -> (u64, u64, Option<u64>, u64, &[LocalSegment]) {
+fn sortable_tuple(version: &Version) -> (u64, u64, Option<u64>, u64) {
     match (version.pre(), version.post(), version.dev()) {
         // dev release
-        (None, None, Some(n)) => (0, 0, None, n, version.local()),
+        (None, None, Some(n)) => (0, 0, None, n),
         // alpha release
         (
             Some(PreRelease {
@@ -2223,7 +2235,7 @@ fn sortable_tuple(version: &Version) -> (u64, u64, Option<u64>, u64, &[LocalSegm
             }),
             post,
             dev,
-        ) => (1, n, post, dev.unwrap_or(u64::MAX), version.local()),
+        ) => (1, n, post, dev.unwrap_or(u64::MAX)),
         // beta release
         (
             Some(PreRelease {
@@ -2232,7 +2244,7 @@ fn sortable_tuple(version: &Version) -> (u64, u64, Option<u64>, u64, &[LocalSegm
             }),
             post,
             dev,
-        ) => (2, n, post, dev.unwrap_or(u64::MAX), version.local()),
+        ) => (2, n, post, dev.unwrap_or(u64::MAX)),
         // alpha release
         (
             Some(PreRelease {
@@ -2241,11 +2253,11 @@ fn sortable_tuple(version: &Version) -> (u64, u64, Option<u64>, u64, &[LocalSegm
             }),
             post,
             dev,
-        ) => (3, n, post, dev.unwrap_or(u64::MAX), version.local()),
+        ) => (3, n, post, dev.unwrap_or(u64::MAX)),
         // final release
-        (None, None, None) => (4, 0, None, 0, version.local()),
+        (None, None, None) => (4, 0, None, 0),
         // post release
-        (None, Some(post), dev) => (5, 0, Some(post), dev.unwrap_or(u64::MAX), version.local()),
+        (None, Some(post), dev) => (5, 0, Some(post), dev.unwrap_or(u64::MAX)),
     }
 }

[charliermarsh]

That seems reasonable but I'm hitting an error in the lazy version map, maybe something to do with equal comparators but different hashes...?

[zanieb]

PubGrub requires a "root" package so root is a fake package that requires that the user asks for. I'm confused as it should never appear in errors like this, we usually replace the name. I can look into that part.

[dimbleby]

Only guessing, but I guess that proposed fix is too symmetrical

• ==1.2.3 should allow 1.2.3+local
• ==1.2.3+local should not allow 1.2.3

[charliermarsh]

One temporary workaround using overrides: #1497 (comment)

[BurntSushi]

OK, so I've been looking into this recently, and after a ~day of yak-shaving to get tests working, I've had a chance to dig in a bit more. I was specifically digging into this in the context of #1497, but I believe that issue and this one are at least connected and likely share the same underlying problem.

Indeed, as @dimbleby put it:

==1.2.3 should allow 1.2.3+local
==1.2.3+local should not allow 1.2.3

Today, the latter is true in uv but the former is not. I believe this is a critical part of this issue that makes it somewhat different from how we deal with pre-releases.

This is somewhat subtle, because in our PEP 440 crate, we do actually handle this case correctly:

uv/crates/pep440-rs/src/version_specifier.rs

Lines 413 to 424 in 20253cd

	// "Except where specifically noted below, local version identifiers MUST NOT be permitted
	// in version specifiers, and local version labels MUST be ignored entirely when checking
	// if candidate versions match a given version specifier."
	let (this, other) = if !self.version.local().is_empty() {
	(self.version.clone(), version.clone())
	} else {
	// self is already without local
	(
	self.version.clone().without_local(),
	version.clone().without_local(),
	)
	};

But in our resolver, that contains method (AFAIK) is not actually used. I'm not sure that it can be. The resolver really only speaks about ranges of versions. It doesn't itself understand (again, AFAIK, I'm not yet an expert on our resolution code) that it's not just a range of versions, but a particular kind of constraint whose interpretation depends on not just on the specific operator used in the constraint, but what the version being tested looks like. That is, the relationship isn't symmetric. I'm not sure if resolution can really deal with that notion. AFAIK, our handling of pre-releases doesn't have this asymmetry problem.

With all that said, I did try a couple things to see what happens.

The first thing I tried was to modify candidate selection:

uv/crates/uv-resolver/src/candidate_selector.rs

Lines 169 to 176 in 20253cd

	/// Select the first-matching [`Candidate`] from a set of candidate versions and files,
	/// preferring wheels over source distributions.
	fn select_candidate<'a>(
	versions: impl Iterator<Item = (&'a Version, VersionMapDistHandle<'a>)>,
	package_name: &'a PackageName,
	range: &Range<Version>,
	allow_prerelease: AllowPreRelease,
	) -> Option<Candidate<'a>> {

I modified it by changing the candidate version to always have its local segment stripped. (This is not fully correct since sometimes we do want to compare the local segments, specifically, when the version constraint itself has a local segment in it. But it does fix #1497.) So that means if we find a candidate with version 1.2.3+foo, we will return it as 1.2.3. This ended up not working because it introduces two different distributions in resolution with exactly identical version numbers. While our test suite passes, it's largely because we don't have good coverage for local versions. Once I added a few basic tests, it was easy to see failures manifest as deadlocks. This is because I didn't do anything to handle the conflict of two different distributions with identical versions. I'm still not sure how to handle that.

The second modification I made (which also fixes #1497) was also to candidate selection. In this case however, instead of returning a candidate with the local segment stripped, the candidate is always returned with its actual version, as it is in the status quo. Instead, all I did was change range.contains(version) to range.contains(version.without_local()). That is, our candidate selector becomes more permissive by making ==1.2.3 match 1.2.3+foo while still returning a candidate with its original version, 1.2.3+foo, in tact. While this fixes #1497 and passes our existing test suite, some basic extra testing with local versions also reveals this approach to not work either. In this case, I can't fully explain the test failure (it causes resolution to panic) because I don't understand it enough yet, but at a conceptual level, it makes sense to me that it wouldn't work. Namely, by doing this, we are kind of lying to the resolver by returning a candidate that doesn't actually satisfy the range given. (Well, we want it to, but range.contains(version) will return false while range.contains(version.without_local()) will return true.) So if something else in resolution relies on the fact that the version we return satisfies the range given, then we will have broken an invariant.

In discussion with @charliermarsh a couple days ago, he suggested taking an approach similar to pre-releases where we allow local versions of packages only if the version specifier itself also has a local segment. This would mean that something like uv pip install 'torch==2.1.1' --index-url https://download.pytorch.org/whl/cpu would still fail, but @SnoopJ's command in the OP of this issue should succeed since the versions as given to install contain the local segment. We could in theory make this work by keeping track of any pinned dependencies using local versions in the constraint (similar to what we do for pre-releases) and propagate this information to candidate selection. Then in candidate selection, we could permit only that version to pass through candidate selection. But, in order to avoid lying to the caller, we'd need to strip the local segment from the version. I believe this will run into the same problem as my first approach above: this will end up deadlocking (and perhaps hit other issues) because the version of the candidate returned doesn't actually match the version of the distribution for that version.

However, one key thing with @charliermarsh's approach is that because of the existence of the constraint ==1.2.3+foo, we know that precisely only one version of 1.2.3 can be returned by the candidate selector. So at least in theory, there won't be a conflict between two different distributions with the same version number. But the practical issue of the candidate version mismatching the version of the distribution remains. This could possibly be fixed, but we'd still need to be careful to not let 1.2.3+foo get into the resolver since it will not match ==1.2.3 which may exist elsewhere in the dependency requirements (as is, I believe, the case in this issue).

It almost seems like what we want is some kind of version-wrapper type that permits ignoring local segments for == comparisons. And this version would be returned by candidate selection. But I don't know enough about the resolver to know whether that's a sound approach or not.

For now, I'm going to clean up my packse tests and get those merged. They will be marked as "unsatisfiable" though, even though we probably want at least some of them to be satisfiable. Otherwise I'm not totally clear on how to proceed here. One more expensive avenue to explore here is how pip deals with these cases since pip does work with these local versions. Although it's not a foregone conclusion that pip's approach will mix well with the PubGrub style of resolution.

[charliermarsh]

I'm going to pick this back up, wish me luck.

[charliermarsh]

This will be supported in the next release via #2430.