A long-term vision for cargo, applied to dependency resolution.

Cargo is the bundled package manager and build tool for Rust. In practice it is the user interface of Rust. Its stellar ergonomics have made it one of the critical selling points of Rust overall. Most "why I fell in love with Rust" testimonials include praise for Cargo. Cargo is a one-stop shop providing a unified experience from adding a dependency, through identifying available versions, resolving a set of transitive dependencies, to building and testing the actual artifacts. Following Conway's law this unified experience is backed by a monolithic code base. User facing improvements often involve changes across many different modules. Furthermore code often accidentally relies on details of how other parts the code work. Attempts to break up the monolith often get stymied by the number of implicit details that need to be public for the existing code to work correctly.

Eventually cargo should be a thin wrapper wiring together independently tested and maintained crates for doing the internal logic. This goal is most helpful because the ever-growing cargo monolith continuously gets harder to maintain and develop. But also, many cargo plug-ins or wrappers are fundamentally "work as if cargo had slightly different functionality" which would be much easier to develop and maintain if the portions of cargo's functionality they want to preserve were available as independent libraries. At this time this goal appears impossibly far off. But this is the kind of work where the goal will seem impossible until suddenly it's almost done. The only thing we can do is find components that can be split out and do so. I am working on the resolver.

The dependency resolver solves the NP-Hard problem of taking a list of direct dependencies and index of all available crates and returning an exact list of versions that should be built. This functionality is exposed in cargo's interface as generating/updating a lock file. There are many ways two crate versions can be incompatible. The current resolver relies on concrete datatypes from other modules in cargo to determine if a set of versions have any of these problems. It is therefore difficult to abstract and separate the existing resolver from the code base. On the other hand, because the problem is NP-Hard it is not easy to tell what code changes break loadbearing performance or correctness guarantees. Which makes any change to the current resolver in situ extremely treacherous. Nonetheless, big changes are required: there is lots of new functionality that will affect the resolver and the existing resolver's error messages are terrible.

Who could be affected.

The previous section mixed together the interests of various different customers that I'd like to try and tease apart here. I'm only gonna focus on those affected by the resolver changes, other work on library-ification may benefit other users.

The Cargo Team

As the official maintainers of Cargo the ongoing costs of a monolith most directly affect this team. Build and testing times continue to get worse with no easy way to only run the things that are needed for the changes that are being made. Changes often accidentally discover implicit dependencies between disparate parts of the code base. If your PR happen to touch the resolver, well that is "where changes go to die".

Developers of cargo wrapers or pugins

Often extensions to cargo only want to change small aspects of cargo's behavior. Perhaps build normally but package the resulting artifact in some way. Or build as if cargo knew how to pull dependencies from another source of truth. Or build as if libraries with known CVE's were not available. The monolith and implicit dependencies make it extremely difficult to maintain parts of cargoes behavior without including and modifying large amounts of its code. The Rust ecosystem could have better tooling if it was less work to develop.

Cargo Users

This is the largest group of people and I wish it were easy to point to how this would improve their lives. When the project is finished and the new resolver is in place they will get significantly better error messages when their dependencies are incompatible. But there also important second-order effects. They will appreciate the new Cargo or pugin functionality or made feasible by a split up code base.

Other languages' package managers

Several other languages have build tooling that uses libraries developed in this project. The main package manager for Gleam, an alternative package manager for Elm, and largest by far the uv package manager for Python all rely on the pubgrub crate. Many changes needed by these other languages are mutually beneficial with this Cargo effort.

Some crates that can be split off from the resolver.

In this section I'm going to describe places where we can (or have) split up the current monolith that is the "resolver" for better testability. I'm gonna work from the individual pieces up to cargo itself.

Conceptually these crates rely on previous crates for their functionality. Each one needs to be usable before the next can be started. However finalizing designs before there are users is always fraught. So waiting until everything is perfect before first user experience in cargo is undesirable. suggestions for how to get early experimentation while these abstractions are being developed would deeply be appreciated.

pubgrub

This crate is under heavy development. It provides a high-performance Rust implementation of the state-of-the-art PubGrub algorithm. The PubGrub algorithm was developed for Pub the package manager for Dart. What makes this algorithm stand out among its peers is that it both works directly with the version requirements understood by the user and gets many of the high-performance proof generation functionalities of SAT-based provers. Specifically, unlike the existing cargo resolver, it can tell you why there is no solution to a set of requirements and that explanation will be directly referencing the requirements.

Expected needed changes:

• Add "constraining dependencies". An alternative form of dependencies that is explicit in the conda ecosystem, and very versatile for expressing performance hints in other ecosystems. For cargo it can be used to hint that if a particular version of the crate is selected then the features selected need to be for the same version of the crate. Currently this is enforced by the feature having a = requirement on the crate. However if the crate is selected first, it can require a linear scan to find the feature with a compatible requirement. If the crate had a "constraint" on its features the algorithm can look up the correct version of the features directly. (Week)
• Add "weak dependencies". The ability for a package to depend on a second package but only if a third package is also selected. This would allow directly modeling Cargoes "Weak feature" syntax in the dependency resolver. This fixes https://github.com/rust-lang/cargo/issues/10801, but given that that is already a bug it is not a blocker for using pubgrub in cargo. (Week)
• Improvements to the API so the above additions do not make things overwhelming, and so that adding new kinds of dependencies do not require breaking change. (Week)
• Allow a user to record where a constraint came from, for example a file and line number, so that the error message can link directly to sources. (Week)
• Concentrated work on error messages. The current error messages are "correct" but not particularly interpretable by humans.
  • Add tests that the data in the error messages are correct. The error message should constitute a proof that there is no solution. It should be possible to check that each step of that proof follows from its arguments. This would make it easier to change the output without risking our guarantee of correctness. (Week)
  • Snapshot testing of error messages. Even if the error messages are correct that doesn't mean they're interpretable by humans; that can only be judged by using human eyeballs. We should have tests that show the exact impact of any change on the readability of the error messages. (Week)
  • Use the "Simplification" code in the algorithm. A constraint like "0 or 1 or 2 or 3 … or 14 or 15" can be expressed more clearly as ">=0 and <=15". Using this in error messages makes a huge difference to readability. Using this directly in the algorithm (where that can be done preserving correctness) can improve performance and obviate the need for special error handling code. (Month)
  • Extend systems for merging facts. There are common patterns where inputs discovered at different times can be expressed as one fact. Currently there is deduction for consecutive versions of a package that have the same dependency statement. This should be extended to other similar patterns, like consecutive versions of a package being unavailable for the same reason. (cc https://github.com/astral-sh/uv/issues/2519) This can massively improve the error message and resolver performance. (Week)
  • The uv Project has done extensive work on their error messages, we should work to include this improvement upstream. (Month)

semver

This is an existing and stable crate. It defines what can be used as a version in cargo and how version requirements can be specified. As one of the few pieces of cargo functionality to be separately version from the very beginning, it's a shining example of the benefits of the long-term vision. It has been maintained and versioned separately from cargo, allowing it to transition through several implementation strategies, and maintainers, and experiment with supporting formats from other ecosystems. Meanwhile it is universally used by all tools that need to handle versions in rust. I do not expect significant changes to be required to support the other steps in this project.

semver-pubgrub

This crate is under heavy development. This crate takes a semver requirement and adds methods that compute negation and intersection as needed by the pubgrub algorithm. These operations require a separate crate because of how the rust ecosystem (as codified by the semver crate) handles pre-releases. 1.2.3-alpha is larger than 1.0.0 but also does not match >=1.0.0. Therefore <1.0.0 is not the negation of >=1.0.0 because 1.2.3-alpha matches neither of them. A type that can correctly represent Not(>=1.0.0) will have different size and performance characteristics than the existing users of the semver crate expect. This crate is usable on its own for anyone who wants to do set operations on rust version requirements, but I think in practice that may be the same as people who want to use the pubgrub crate.

Expected needed changes:

• While this crate is already technically correct it needs improvements to its display formatting to make them understandable to users. Specifically no matter how a requirement was constructed if it matches the same things as a canonical requirement like ^1.0.0 then that should be its display. Similarly, if a requirement cannot match prereleases, then it's display should not involve them. In cases where no canonical requirement is equivalent, the display should look like a collection of canonical requirements and there should be a way to round-trip the string back to the full format. (Month)
• While fuzz testing is in place, it needs to be expanded to be "mutant-proof". Such that common changes/typos to the code will trigger a test failure. A lighter weight Property based version of the fuzz tests need to be constructed that can be run routinely. And appropriate CI needs to be put in place to assure that this is all being maintained. (The more the better.)

Risks and externalities:

• As a second independent implementation of semver matching algorithm this may help clarify the intended semantics of the recently accepted "update –precise to prerelease" RFC.

crates-benchmark-importer (name to be improved as functionality changes)

This crate is currently under private development. This project provides a lowering from cargo to pubgrubs semantics. This allows for testing if optimizations (in pubgrub or in the lowering) actually improve resolution time for real existing crates. It is also growing tools for testing that the lowering actually preserves the semantics cargo expects. Versions on crates.io can have several kinds of dependencies that are not directly modeled in pubgrub. Specifically they can set the "links" attribute, have optional dependencies, or activate optional dependencies of their crates. In addition cargo will sometimes build the same package at more than one version which is not directly supported in pubgrub.

Expected needed changes:

• Tests that compare the results to a sat solver. (Week)
• Tests that compare the results to cargo as a lib. (If this is technically possible with cargos api.) (Week + #Bugfix)
• More ability to run test cases outside of scanning all of crates.io. (Week)
• Fuzz/property based Inputs to tests. (Month)
• Better tools for minimizing input files for failing tests. (Week)
• Better tools for translating test files into the exact format used by the pubgrub crate. (Week)
• Running index scan in parallel. (Week)
• Better CLI for index scan, with a better progress bar. (Week)
• Stop the Solana ecosystem from dominating the runtime of the index scan. either by fixing the performance problem they induce or by suggesting fixes to the crates that avoid triggering that performance problem and filtering the older versions out of the sample. (Don't know)

Risks and externalities:

• This libraries should be sufficient to build a "Transitive dependencies of a crate" website. A website in which you put in your crates.io dependencies and uses the HTTP sparse index to do dependency resolution and tell you A lock file that would be induced. This is a long requested feature for crates.io, but not safe server-side and without this project on implementable client-side.
• Cargoes test suite for backtracking induced by the interactions between features is limited to some hand constructed example cases. It is entirely possible that differential testing will find bugs in the existing resolver. Fixing these bugs in the existing resolver may add additional time or may not be possible. If it is not possible, testing the correctness of the rest of this project will become significantly more difficult.

full-cargo-resolver-replacement (name to be chosen as development starts)

This crate is currently hypothetical. A full resolver for cargo will need to handle many things that cannot be observed on crates.io. Including:

• Path and Git dependencies.
• Packages that come from different sources/registries.
• 3 kinds of package replacement.
• Interacting with existing lock files.

It would be really nice if all of this complexity can be modeled without directly depending on the rest of cargo. This separation would allow for clear documentations about all the things that can (and more importantly the things that cannot) influence resolution.

TODO: Risks

• Not detailed enough understanding to construct timeline.
• This may end up having to be a separate module in cargo if this is too much to develop a stable API of.

cargo

This is where the existing resolver lives. The ultimate goal is to replace the existing resolver with this new stack of abstractions.

Plan of stabilization (once new crates are ready):

1. Add code checking that resolutions constructed by the existing resolver are accepted by the pubgrub resolver. And that if the existing resolver Cannot construct a resolution then pubgrub also cannot construct a resolution. (Month + #Bugfix)
2. Add a nightly feature for using pubgrub. When they nightly feature is activated resolve using pubgrub and check that the result is accepted by the existing resolver. And that if pubgrub does not find a resolution neither does the existing resolver. (Week + #Bugfix)
3. Work to get cargoes test suite to pass in both modes. (Week)
4. Encourage outside testing of the new nightly feature.
5. Stabilize printing the error message generated from pubgrub when both resolvers failed. (Week)
6. Stabilize using the resolution generated by pubgrub, while still verifying that works with the old resolver. (Week)
7. Remove the old resolver. (Week)
8. Remove data structures and caches needed for the old resolver that are redundant with pubgrub. (Week)
9. Change the internal abstractions intended for the old resolver to look more like pubgrub's interface. (Week)
10. Bump the lock file version and implement functionality that was not possible on the old resolver. Like https://github.com/rust-lang/cargo/issues/10801
11. Add a "backtracking mode" for the msrv aware resolver. (Current resolver error messages too bad to consider this feature.)
12. Add other sources of filtering to the resolver's error messages.

TODO: Notes on:

• If we had to drop?

• If we had more help?

• Incromentel Deliverabls?

• A high level Risks & Challenges section. Talk about different issues/headwinds, the impact/challenge it presents, and if any mitigations can be done.

• Overall timeline:

  • what are the mile stones?
  • how long shuld they take?