The requested package has a dependency on torch, which can’t be met because there is no wheel for the Python version in use. However, the log of the build shows it stepped through many versions of the requested package, >30 of them by my count, with each one failing, to the point there was even a “this is taking longer than usual” message. But since the problem is there is no version of the dependency that will work with the Python version in use, not that there’s a troublesome interplay between the requirements of the target pkg and the dependency pkg, a naive view is one ought to be able to detect that and bail earlier.
Not sure this is the correct category for this thread.
Each installer tool potentially has its own resolution algorithm. Do you think there is something that should be standardized here? If this discussion is about pip specifically, I guess it would be wise to mention it (in the title maybe?).
While the details are probably pip-specific, I think the question actually reflects an underlying issue that people tend not to be aware of what possibilities have to be considered when resolving a list of dependencies. For example, even the post title demonstrates this - “deps that cannot be met”. How can the resolver know that the dependency cannot be met, without checking each possibility. As humans, we can see that the dependency can’t be met (often because “it’s obvious” in some sense), but we’re typically working with information or intuitions that the resolver doesn’t (and sometimes can’t) have access to.
So while there probably isn’t a standards-based question or proposal here, this seems to me to be a legitimate question in the sense of being a “packaging discussion”. (And in fact, packaging standards should really be in the new “Standards” sub-topic, making the main “Packaging” group even more appropriate for general questions ablut packaging like this).
It was, in fact, a pip question because of the context, and I did check the channel guideline which includes "Use this category for discussions relating to anything packaging in Python, including but not limited to:
I’m not assuming this is simple - thus the sort-of-disclaimer at the end “a naive view is one ought to be able to detect that and bail earlier.” Just wondering if there really is a reasonable way to detect something like this. I do get that the troublesome dep might not have been a dep in earlier versions, so there’s probably good reason to scan backwards after all.
This should get better when PyPI does the backfilling for providing metadata separately from distributions. When that is done, pip will no longer need to download lots of wheels or sdists just to resolve dependencies. It won’t reduce the size of the search tree, but it will reduce how fast it is explored.
(pip probably can’t make this decision, this message is not meant to imply pip’s behaviour should be changed)
Personally, I rarely want extensively backsolved packages. I usually don’t actually want some ancient package version that meets the resolver constraints; if I do, I want to be aware of it. The backsolved solution can often be not what you want either. I also want the installing UX of my package to be good and not slow.
In cases where this comes up, I add many >= lower bounds, or use a constraints file to prevent pip or other frontends backsolving (constraints files are especially useful for preventing backsolving of transitive dependencies).
Generally, the biggest problem we see is when pip needs to scan back because it might find a solution using old versions. Combine that with packages that have very frequent releases (botocore is a common offender) and you can end up with a lot of checks to do.
One possible fix is to artificially limit how far back the resolver can go - either by using a constraints file, or an index proxy that selectively hides “older” versions. Neither of these is perfect, not least because they can result in pip not finding a resolution when one does exist outside of the constraints you applied, but they are a way to keep things a little more manageable.
In general, we’ll continue making improvements that reduce the cost of each check we do. Improving the resolver algorithm can mean that we find a working solution in fewer checks, and we’re doing a lot of work on that (both in pip and in resolvelib). But there’s a hard limit here, which is that some global questions simply can’t be answered without checking every release.
The example given in the OP is precisely such an example - torch has published something like 200 versions, and there’s no way of knowing if any of them will work with a given Python version without checking each one. You and I might know that if the latest version doesn’t support Python 3.11, then there’s no chance that an older version will, but the resolver can’t make that assumption. And nor should it - maybe the torch developers haven’t got round to producing a Python 3.11 build for the latest version yet, or maybe there’s an incompatibility that wasn’t a problem in the previous version. The resolver can’t know any of this. So it has to check.
Most importantly, that’s not an implementation problem, nor is it a limitation of a particular resolver algorithm. It’s a fundamental property of the problem that we’re trying to solve, and the only way of fixing it[1] is for the user to provide extra information (such as a constraint that says “there’s no point even looking at torch versions before 2.0.0”).
This is a very reasonable position, and I can say that if someone could come up with a workable UI to constrain this, pip would be happy to look at adding it. The problem is defining what constitutes “extensively backsolved” - some projects create nightly releases, others might have one release per year. Some projects might have a stable version that’s not been updated in many years. There’s no “one size fits all” answer, and having to specify a threshold per project seems impractical for anything but the smallest resolution problems (which are the ones that typically don’t need this).
And the real issue here is if you get the limits wrong, you get pip saying it can’t find a solution when there actually is one that would work. Calling it “user error” doesn’t make it any more pleasant an experience when that happens…
This is honestly the best solution I can think of right now. It’s messy and manual, but it works.
OP’s example is actually rare, it happens mainly because torch doesn’t provide an sdist. For most packages, pip would simply try to compile the sdist to produce a binary that worked for your Python release. pip doesn’t try and backsolve to find an sdist that compiles, it just gives up the first time sdist compilation fails (yes, this means pip could fail to find a solution when there is one).
In my experience, backsolving usually happens because someone somewhere in your dependency tree put an upper bound (and usually for not particularly good reasons). Henry’s guide talks more about this: Should You Use Upper Bound Version Constraints? -
Backsolving that goes back forever and finds no match
In the former case a likely problem (as Henry describes) is that the “successful” match might not give a working setup. The latter case is what the OP refers to which is that backtracking spends a long time looking for something that doesn’t exist.
An upper bound constraint creates the same problem as the OP: if you restrict to cool_proj < A.B then there might be no version of cool_proj that is compatible with python X.Y within that set.
I just wonder if the problem likely boils down to some upper bound constraints on package versions precluding compatibility with a given Python version. If that is the case then in principle there are ways that the information could be precomputed (what is the latest Python version compatible with cool_proj = A.B or what is the earliest version of cool_proj compatible with python X.Y?). In practice that might be complicated because of long transitive dependency chains and retrospective updates etc.
I’m not sure it’s worth doing anything to optimise a failure case like this though. It would be nice if these things were more well defined somehow so that it just worked or failed quickly. The bigger problems though are about the consistency of the requirements database like Henry’s point about backtracking and finding a version that supposedly works but doesn’t really work.
I don’t want to extend this conversation too far, but there’s actually a lot you can do to optimize the latter case.
In many resolutions there is a lot of complexity on choosing which packages to backtrack on, if you can apply some clever SAT solver techniques you can reduce the problem down to foo>1, foo<1 far quicker (in fact, I have and am writing such optimizations for Pip).
The problem with OPs example is it is too simple to optimize, it’s a straight line, you have to check each package and make sure none of it’s dependenies match. There really isn’t anything clever to do.
What Pip can do is just optimize it’s codebase, if someone wants to profile this example I imagine there’s at least some low hanging fruit in terms of speed improvements. Compared to rip I found on my machine Pip is 6x slower (interestingly both when having to download all packages and when just relying on cache), I’m sure some of that difference could be made up if someone was sufficently motivated.