Expose edges in solution

pubgrub-rs / pubgrub

PubGrub version solving algorithm implemented in Rust

https://pubgrub-rs.github.io/pubgrub/pubgrub/

Mozilla Public License 2.0

337 stars 29 forks source link

Expose edges in solution #233

Open konstin opened 2 weeks ago

konstin commented 2 weeks ago

extract_solution -> SelectedDependencies should allow users to query the edges between the selected package versions. In uv, we currently need to access the incompatibilities directly to get this information (https://github.com/astral-sh/uv/issues/4187).

Eh2406 commented 2 weeks ago

I don't have enough context to interpret that issue.

What do you end up using this information for?
Why can't it be reconstructed from dp.get_dependencies (whatever your internal equivalent is)?
What API would would make sense to user? incompatibilities are not part of our public API, it's going to require a lot of explanation to describe how an arbitrary incompatibilities relates to something a user provided.

konstin commented 2 weeks ago

@charliermarsh can probably give you more details, but we need them to annotated requirements.txt with the source of a requirement and to show dependencies in our lockfile uv.lock, both through the intermediary of a petgraph graph. We don't implement get_dependencies, we call add_incompatibility_from_dependencies manually; We can reconstruct it, but since pubgrub already knows the graph we should be able to read it out instead of reconstructing it on our side.

Eh2406 commented 2 weeks ago

We can reconstruct it, but since pubgrub already knows the graph we should be able to read it out instead of reconstructing it on our side.

pubgrub does not know the graph. It analyzes the problem as a "set of simultaneous constraints" not as a "graph". Wherever the code lives it is going to be "reconstructing" the graph from the output and some source of dependencies. It is probably worth us implementing a helper method that takes a solution and a dependency provider and reconstructs the graph, but you would need to adapt it to your resolution loop. Alternatively if it can be constructed by iterating over all incompatibilities that are user provided dependencies we could add a method to state. That would probably look very similar to the code you've already written. How hard would it be to upstream?

charliermarsh commented 2 weeks ago

Candidly I don't mind what we do today (iterate over the incompatibilities to build up a graph), though I recognize that it's an implementation detail of PubGrub.

We extract the dependencies and packages here: https://github.com/astral-sh/uv/blob/b3a99d9ff927b34f06aa40c63ea89551d1c246f7/crates/uv-resolver/src/resolver/mod.rs#L1508. We just look for FromDependencyOf incompatibilities.

Then we build it into a petgraph here: https://github.com/astral-sh/uv/blob/b3a99d9ff927b34f06aa40c63ea89551d1c246f7/crates/uv-resolver/src/resolution/graph.rs#L66.

(I may merge these steps in the future, they're distinct for historical-ish reasons.)

Eh2406 commented 2 weeks ago

Ironically, today in my work trying to model cargoes resolver with pubgrub I minimized a clear example of cyclic package dependencys which requires looking at pubgrub's output as a graph. The fates have definitely decided that now is the time for us to be thinking about this issue.