I want to speak to what I see as one of the biggest risks to this PEP, which is: we don’t yet have a robust, well-proven tool that can produce the kinds of resolutions that this lockfile is designed around – i.e., a tool that both (1) does not require a resolution at install-time, and (2) can handle disjoint dependency graphs.
(I mean no disrespect here, and authors of other tools should correct me if I misrepresent their work.)
To skip ahead: I would love to see a real-world implementation of the Package Locking proposal prior to a decision on the PEP. And, as someone that wants this proposal to succeed, I’m happy to put my money where my mouth is by implementing it in uv once we have rough consensus on the schema.
(N.B. What follows is a longer explanation on why I consider this is so important – skip to the end if you find this uninteresting.)
Without a working implementation, we run the risk of standardizing something that doesn’t actually work. And I think that risk is non-trivial. We, as an ecosystem, are still figuring out how to resolve for these Package Locking environments – at least, in the form envisioned by the PEP. I’m not surprised that @frostming called it “impossible or extremely difficult to do correctly”.
Concretely, this proposal draws on a few references:
-
mousebender, which performs File Locking but not Package Locking.
-
PDM, which does generate a Package Locking resolution (with marker propagation), but has limited support for resolving disjoint dependency graphs. For example, PDM can resolve this:
anyio > 3 ; sys_platform == 'darwin'
But it cannot resolve this:
anyio > 3 ; sys_platform == 'darwin'
anyio < 3 ; sys_platform == 'win32'
Which leads to:
ERROR: Unable to find a resolution for anyio
because of the following conflicts:
anyio<3; sys_platform == "win32" (from project)
anyio>3; sys_platform == "darwin" (from project)
That second set of requirements represents a step up in difficulty. (In uv, we refer to this general setup as “forking”, since we fork the resolver based on the disjoint markers and then unify those forks later on.)
-
Poetry, which supports the cases described above, but writes out a list of resolved packages without any markers, and then performs a resolution at install time.
Based on my own experience, I think it will be non-trivial for Poetry to migrate from the current solution to the PEP proposal. (I apologize if I’m off-base here, I don’t feel fully comfortable commenting on other tools but I’m doing my best to describe the state of the landscape.) My understanding is that Poetry’s current approach has a higher tolerance for error, since it doesn’t need to guarantee that a single resolution is produced for every possible environment – only that a resolution is available for every possible environment. This too represents a step up in difficulty.
-
uv, where we’re working on a resolver that can solve these disjoint dependency graphs (as in the anyio case above), without requiring a resolution at install time. And those goals are well-aligned with the motivations of the Package Locking proposals.
We’ve built this, it’s public, and early adopters are using it, but it hasn’t been “announced” or proven in the wild – so it likely has its own problems! It is capable of resolving highly complex dependency graphs with hundreds of package nodes… but we don’t yet know where it will fall over. Just last week, we shipped a bunch of significant changes to the lockfile format based on new information from early testing.
In building uv’s universal resolver, we’ve also had to confront a bunch of hard problems that we didn’t anticipate in advance. Here’s an example…
In order to generate these kinds of resolutions (especially when “forking” is required, as in the anyio case), you need to do a lot of algebra on marker expressions.
For example:
- If A is required by B and C, but with different markers, A’s marker should be the OR of them. Straightforward enough…
- But you also need to be able to identify when two sets of markers are disjoint (as in the
anyio case above). I believe this is actually an NP-complete problem, equivalent to SAT (checking if A and B are disjoint is equivalent to checking if A and B is not satisfiable).
We started off doing these manipulations naively (just OR and AND), then made a series of changes to perform marker normalization and simplification (1, 2, 3, 4).
Even with all of that, for complex cases like “Transformers with all extras enabled”, we ended up with marker expressions that weighed in at 10s of KBs per dependency (5). They were just ridiculously long. In the end, Ibraheem (from our team) implemented an entire SMT solver (6) to support robust simplification of marker expressions and disjointness checks. It’s a hard problem!
I’m happy to talk more about the marker problem (maybe we’re over-thinking it), but I mostly intend for it to serve as an example of something that we didn’t anticipate ahead of time…
My feeling from the above is that this isn’t yet a solved problem. So I’m wary of standardizing on an output format for something that we’re still trying to understand…
For me, the solution is to ensure that we have at least one working implementation prior to a decision. (I recognize, of course, that this is not my call.)
If we can pass uv’s current test suite with the proposed format, and continue to pass whatever additional tests we add over time once the resolver is released, I would have far more confidence in whatever we decide on here. And I’m personally willing to put in the time to see that through.