I have to replicate cargo's dependency resolution algorithm in a different programming language but I could not find documentation explaining how cargo build the dependency tree.
My current implementation is:
Download crate index file from cargo.io
Get list of dependencies, and its version requirements and store into a table crate X requirements
For each dependency, find in the index the crate version that satisfies the requirements
For each dependency, repeat the process, recursively, while accumulating the requirements on the "crate X requirements" for the next iteration
This algorithm is not producing the same output as running cargo, and is also finding several conflicts.
hax10
May 18, 2023, 1:40pm
2
The source code for Cargo has a good description of the algorithm in its comments:
2 Likes
jofas
May 18, 2023, 1:47pm
3
Cargo's resolver is very complex. AFAIK the resolver is not documented completely and coherently in a single document. As @hax10 pointed out, you probably should look into the resolver module. You can find the source code here:
//! Resolution of the entire dependency graph for a crate.
//!
//! This module implements the core logic in taking the world of crates and
//! constraints and creating a resolved graph with locked versions for all
//! crates and their dependencies. This is separate from the registry module
//! which is more worried about discovering crates from various sources, this
//! module just uses the Registry trait as a source to learn about crates from.
//!
//! Actually solving a constraint graph is an NP-hard problem. This algorithm
//! is basically a nice heuristic to make sure we get roughly the best answer
//! most of the time. The constraints that we're working with are:
//!
//! 1. Each crate can have any number of dependencies. Each dependency can
//! declare a version range that it is compatible with.
//! 2. Crates can be activated with multiple version (e.g., show up in the
//! dependency graph twice) so long as each pairwise instance have
//! semver-incompatible versions.
//!
//! The algorithm employed here is fairly simple, we simply do a DFS, activating
//! the "newest crate" (highest version) first and then going to the next
show original
and I'd use the developer version of the documentation, as it contains private items and submodules which may be of interest to you:
2 Likes
Yes. I did check the documentation, but it is not very helpful IMHO.
Tried browsing around the code as well, but I could not track the process across the different source files.
There was an effort to move Cargo to the PubGrub dependency resolution algorithm precisely because the current method has a lot of edge cases. I'm not sure of the current status though. GitHub - pubgrub-rs/pubgrub: PubGrub version solving algorithm implemented in Rust
1 Like
system
August 17, 2023, 8:48am
6
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.