Cargo resolver picks two versions of a crate, even when one is enough

[omid]

Problem

Diesel 2 (rc.0) depends on uuid >=0.7.0, <2.0.0 and my app depends on uuid =0.8.2 because some other deps depend on that.

Cargo resolver always pick two versions of uuid, 0.8.2 and 1.0.0. (in my case)

It's the same if I remove the =, also the same if I remove uuid dep from my app and only some other deps depend on uuid 0.8.2.

Test scenario to cover this case:

#[cargo_test]
fn uuid_test() {
    Package::new("uuid", "0.8.2").publish();
    Package::new("uuid", "1.0.0").publish();
    Package::new("diesel", "2.0.0")
        .dep("uuid", ">=0.7.0, <2.0.0")
        .publish();

    let p = project()
        .file(
            "Cargo.toml",
            r#"
            [package]
            name = "foo"
            version = "1.0.0"

            [dependencies]
            diesel = "2.0"
            uuid = "0.8.2"
            "#,
        )
        .file("src/lib.rs", "")
        .build();

    p.cargo("tree -i uuid").with_stdout_contains("uuid v0.8.2").run();
}

Steps

1. Create a new project
2. Add the following deps:

diesel = {version = "2.0.0-rc.0", features = ["uuid"]}
uuid = "=0.8.2"

3. Run cargo tree -i uuid

Possible Solution(s)

No response

Notes

No response

Version

cargo 1.60.0 (d1fd9fe 2022-03-01)
release: 1.60.0
commit-hash: d1fd9fe2c40a1a56af9132b5c92ab963ac7ae422
commit-date: 2022-03-01
host: x86_64-unknown-linux-gnu

[epage]

From the explanation of the resolver

//! 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
//! option. The heuristics we employ are:
//!
//! * Never try to activate a crate version which is incompatible. This means we
//!   only try crates which will actually satisfy a dependency and we won't ever
//!   try to activate a crate that's semver compatible with something else
//!   activated (as we're only allowed to have one) nor try to activate a crate
//!   that has the same links attribute as something else
//!   activated.
//! * Always try to activate the highest version crate first. The default
//!   dependency in Cargo (e.g., when you write `foo = "0.1.2"`) is
//!   semver-compatible, so selecting the highest version possible will allow us
//!   to hopefully satisfy as many dependencies at once.

So this seems to match up with the expected heuristics of the resolver (activates the higher version and then finds that a lower version is needed which is fine because its semver incompatible).

I found unexpected cases like this is common when going outside the common path dependency declaration path. I'd recommend reporting this to Diesel so they can weigh out if they still want to go this route for 2.0.

I'm not a resolver expert to say if anything can be done shorter term. Longer term, we are looking at changing out the algorithm for PubGrub solver though I have no idea if that will improve this situation. @Eh2406 would be more likely to know the answer for both cases.

[Eh2406]

Cargoes resolver optimizes for each dependency edge getting the largest version within its requirements. As such this is working as intended.

However this is known to be insufficiently flexible. Public/private dependencies would allow you to control this exactly (and only) where it matters, however progress on that is rather stalled. Someday I would like to experiment with some more flexible syntax for adding requirements to the generation of the lock file. One rather crude option, that probably get some 80% of the use cases, would be a --at-most-one=uuid flag. But this is barely in the design phase.

The existing resolver is collapsing under its own complexity. It is technically possible to add these sorts of features to it, but I have not succeeded in doing so. The PubGrub solver itself will make some of these problems easier, but more importantly will be a more organized and up-to-date code base to start from.

Is having this duplication actually causing you problems for your use case?
There is one very hacky way to get what you need, the resolver prefers versions that are already in the lock file. Remove all your dependencies except uuid =0.8.2, generate a lock file. Then add your other dependencies (Diesel), and generate a lock file. This may get you a lock file in the shape you need.

[epage]

Is having this duplication actually causing you problems for your use case?

I'm assuming the use case is similar to sqlx where they want integration with types from other crates without worrying about breaking changes unrelated to the types they integrate with. See sqlx's discussion on the topic.

[omid]

Thanks

Is having this duplication actually causing you problems for your use case?

Yes, exactly as @epage said.

There is one very hacky way to get what you need, the resolver prefers versions that are already in the lock file. Remove all your dependencies except uuid =0.8.2, generate a lock file. Then add your other dependencies (Diesel), and generate a lock file. This may get you a lock file in the shape you need.

I haven't tried it, but as you said, it's very hacky. And I guess it will install the latest as soon as I run cargo update.
I could achieve my goal with this command (in my case): cargo update -p uuid:1.0.0 --precise=0.8.2

[weiznich]

I found unexpected cases like this is common when going outside the common path dependency declaration path. I'd recommend reporting this to Diesel so they can weigh out if they still want to go this route for 2.0.

I'm well aware of this fact. The problem is I do not see a good solution to this problem. So my question at the cargo team is the following: What's the correct way to handle this?

I see the following bad options:

• Use distinct feature flags for different versions, which is bad because it leads to code duplication (each feature requires it's own duplication) and a unbounded number of feature flags which cannot be tested on CI
• Support a compatible version range, which is bad because of the reasons explained above
• Drop support for old versions, which is bad because it drops support for otherwise compatible code
• Do not support external types at all, which is bad because no support for anything else than std at all.

Maybe you can comment officially on how to solve this? I feel this issue is holding back the ecosystem at all, as it makes it really hard to provide integration for other crates. I understand that this is not an easy problem to solve, but I really would like to see a canonical solution here. Especially as this problem is known for quite a bit of time.

[epage]

A couple of solutions from sqlx that weren't on your list

• Implement type support externally, using newtypes to work around orphan rules
• Implement the types yourself

On top of those is how the potential for relaxing orphan rules could change what solution is chosen. This shows the problem, and potential solutions, are wider than just cargo. We need to look at this holistically.

[jplatte]

I don't really think a smarter solver can fully solve this issue. If you have just one bit of integration code for the uuid crate, it can only apply to one specific version within given crate graph. Now if multiple crates in the dependency graph want this integration for different versions of uuid, that won't work.

This is already a problem if two crates specify uuid deps that have to be different, something like uuid = "=0.8.1" and uuid = "=0.8.2" and individually expect your crate to integrate with uuid 0.8.x. It's not a problem in practice of course, but I think trying to use different bounds from those that work well today is just going to cause more trouble than it's worth, regardless of how smart Cargo's solver is.

[epage]

Forgot to mention, another weakness in this solution is it assumes the types being integrated will never have a significant breaking change. For the most part, they are pretty simple, so it should be rare, but if is a risk.

[omid]

@jplatte sure there will be some conflicts here and there. That's understandable, and some cases are unsolvable.
Let's say, the current algorithm (and MaximumVersionsFirst) can solve 90% of situations. A smarter way can solve 90% of the remaining 10% cases!

I'm not familiar with the source code and the algorithms. But I would say, the main part of resolver works fine. Just the time we sort by MaximumVersionsFirst has issues and I think the default should be the MostPopularVersionFirst and in case some versions has the same popularity, then we can follow MaximumVersionsFirst.

[weiznich]

• Implement type support externally, using newtypes to work around orphan rules
• Implement the types yourself

Neither of this are great either if you want to provide actual integration.

On top of those is how the potential for relaxing orphan rules could change what solution is chosen. This shows the problem, and potential solutions, are wider than just cargo. We need to look at this holistically.

I remember that some persons talked about a similar proposal years back, so that just seems not to be moving at all. Sorry if that sounds harsh, but I feel that this is holding back the ecosystem more and more.

I think one way to address the fundamental problem that there are always cases where you cannot solve version constraints is the following approach:

• Allow crates to declare what's a public dependency (== types are exposed), and what's an internal dependency (crate is only used internally)
• For internal dependencies the current behaviour is sufficient and probably even desired, as you likely want to use the newest version of something anyway.
• For public version you can assume that the user requested compatibility. So either it's possible to find one common version there or not and cargo presents an error about that.

[Eh2406]

You are not wrong that this is holding back the ecosystem. And that none of these ideas are new.
Your suggestion is the Public/private dependencies RFC, and that will help. But the resolver for that is not yet ready. The current implementation has exponential blowup on such a high percentage of synthetic cases that it is hard to say for confidence if it's even correct.

[epage]

I can understand the frustration with any of the routes for this to move forward. A big challenge right now is that the cargo team in particular is limited in availability both to implement and to mentor on tasks. That combined with the current resolver complexity makes it difficult for cargo to be able to move forward with a solution at this time.

[weiznich]

A big challenge right now is that the cargo team in particular is limited in availability both to implement and to mentor on tasks. That combined with the current resolver complexity makes it difficult for cargo to be able to move forward with a solution at this time.

I'm well aware of this and I didn't plan to blame anyone here. It's just as you've already written quite frustrating to see this long standing issue here without any signs of moving, while observing at the "same" time changes to cargo's resolver algorithm that broke diesel a while back.

That written: If there is anything actionable here I'm happy to hear that, maybe I can find some time later this year to work on this.

[joshtriplett]

Another possibility would be for uuid to publish a version 0.8.3 that depends on uuid 1.0.0 and uses the same underlying type, which would eliminate the compatibility issue.

Long-term, I'm hoping in lang we can find a way to allow a separate diesel-uuid crate that can provide trait impls without having to be part of either diesel or uuid.

Meanwhile, I would suggest just supporting the latest semver-major version of uuid.

[ehuss]

I'm going to close as a duplicate of #9029, and of the work on public/private dependencies (#6129) which may provide an avenue to place "at most one" constraints. I understand that none of the workarounds are particularly great, though.

[weiznich]

@joshtriplett Just supporting the latest semvar-major version is not necessarily a solution, as this would require a breaking diesel release whenever one of the dependency crates releases a new major version, even if the relevant part of their API remains the same.

[joshtriplett]

@weiznich That's part of why I'm suggesting that uuid might want to release a version in the 0.8 series that provides compatibility with the 1.0 series.

If you don't want to go that route, then you may need to use feature flags.