Repository navigation
Add an unsatisfiability check method to SpecifierSet #940
Description
This is a follow up to #776 which failed to progress due to the nuances of Python package version specifiers making it not clear if it's possibly to "reasonably" simplify SpecifierSets.
However, in a lot of cases for resolution what's more important is knowing whether a specifier set is unsatisfiable or not, for example:
- Unsatisfiable:
<1,>2 - Satisfiable:
>1.5,!=3.*
As a resolver if you know a specifier set is unsatisfiable you can skip collecting the versions available, which can potentially save you a lot of time as you may need to do network requests or build source trees to determine the versions available for a package.
This would ideally be part of packaging as accurately following PEP 440 to determine unsatisfiability is highly non-trivial.
As long as there is no objection I plan to raise a PR shortly, I have done most the work to implement this already, I am ironing out some final test cases around extreme edge cases (such as arbitrary equality).
P.S. This also follows #897 as it should now be true that if SpecifierSet({expr1}) is unsatisfiable, so is SpecifierSet({expr1},{expr2}), this is an important invariant for resolvers, and without it determining the unsatisfiability doesn't allow you to make any further logical inferences.
Activity
akhmerov commentedon Oct 11, 2025
Even a minimal version that would return unsatisfiable/maybe satisfiable/satisfiable would be useful for checking whether to remove version-dependent code. A few of my projects have:
Checking if
SpecifierSet("<min_version")is in principle compatible this with project dependencies would allow to easily find which of these code paths can be safely removed.notatallshaw commentedon Mar 9, 2026
@henryiii I was working on this feature over the weekend and I wanted to run my ideas by you given you're the most likely to review.
Implementing this feature seems best achieved by representing specifiers as intervals and then resolving those intervals. This is how uv represents specifiers so it is not novel, and is well documented on SAT theory.
However, this basically means reimplementing PEP 440 semantics in a different way. Given this, I wondered if it made sense to move regular filtering over to this interval approach, but I faced two problems:
Give this my plan was to:
No rush to respond, it will be at least a few weeks before I raise a PR.
henryiii commentedon Mar 9, 2026
I'm very much in favor of intervals; the feature I'd really like is to be able to compute the intersection; with that, you can ask questions like "is Python 3.9.x supported", for any value of
x, or "what is the minimum value of Python supported". Currently, that's a lot harder to do.The plan sounds pretty reasonable, just two thoughts: First, new methods don't get much usage very quickly - most users expect to support a range of libraries, so they can't jump on the new method (and lots of packages don't move fast enough). If it was used inside pip or someone else that embeds packaging, that would help it get exposure, but just a new method isn't likely to get a ton of exposure. But we might have enough users where it would get picked up somewhere. Moving an existing method or two to use it would have a much larger impact.
The other is that using it to replace the internals gives it a ton of exposure, both from our test suite, and the downstream testing. I think having a PR that does that, even if we don't land it for a version, would help in testing out (and it would be very interesting to measure performance too).
Given that, I think this is a reasonable plan, but the "rip out the internals" alternative would be okay too. I think if we could get to pass the current tests without modification, that would be very comforting. Though if we went that route, I think it should target 26.2, so as to not risk affecting Python 3.8 users that have frozen their libs, so maybe that's another way of saying the current plan is better. :)
notatallshaw commentedon Mar 9, 2026
I like the idea of maintaining but not merging a PR that replaces all the logic, so we can validate tests, performance, and downstream.
And then having another PR where we implement all the machinery and just use for this one method to start off with, once merged the diff between main and the PR that replaces all the logic will be a lot smaller.
I still need to spend a lot of time on reviewing this code, and understanding if I'm not missing obvious simplifications. But hopefully I'll post something in a couple of weeks.
notatallshaw commentedon Mar 21, 2026
This is probably also needed for resolver optimizations in pip, I'm going to experiment with different APIs and different resolver approaches over the next few weeks to see what makes the most sense to provide directly from packaging.