Expose edges in solution

[konstin]

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 (astral-sh/uv#4187).

[Eh2406]

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]

@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]

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]

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]

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.