dependency resolver sometimes fails to find valid resolution when optional dependencies have a conflict.

[Eh2406]

Problem

In the resolver conflicts are stored as a list of package versions that cannot be activated the same time. This model is insufficient to describe certain interactions of optional features with requirements that can match multiple major versions. The exact root cause of the problem is not yet clear.

Steps

I have suspected there are issues with this for a long time. But it was only this week that I came across a clear reproducer.

#[test]
/// Minimized from `upstream-ontologist v0.1.37`, although subsequent changes to the index
/// means it's no longer a problem in the wild.
fn test() {
    let reg = registry(vec![
        pkg_dep(
            ("breezyshim", "1.0.0"),
            vec![dep("debversion").with(&["pyo3"])],
        ),
        pkg_dep(("debbugs", "1.0.0"), vec![dep_req("debversion", "^0.4")]),
        pkg_dep(("debversion", "0.3.1"), vec![dep("pyo3").opt()]),
        pkg_dep(
            ("debversion", "0.4.1"),
            vec![dep_req("pyo3", ">=0.22").opt()],
        ),
        pkg(("pyo3", "0.20.3")),
    ]);

    let deps = vec![dep("breezyshim"), dep("debbugs")];
    let mut sat_resolver = SatResolver::new(&reg);
    resolve_and_validated(deps, &reg, &mut sat_resolver).unwrap();
}

Possible Solution(s)

It should be possible to resolve this by directly modeling features as separately tracked entities in the existing resolver. This would however be a lot of work. I suspect this will not get fixed until we switch to a PubGrub based resolver.

[Eh2406]

Thanks to @x-hgg-x for making the test, and confirming that this was a bug. See previous discussion at https://rust-lang.zulipchat.com/#narrow/channel/260232-t-cargo.2FPubGrub/topic/upstream-ontologist.20bug.3F

[x-hgg-x]

Cargo log for the test:

0.000740200s DEBUG resolve: cargo::core::resolver: initial activation: root v1.0.0 (registry `https://example.com/`)
0.000768760s TRACE resolve: cargo::core::resolver: activating root v1.0.0 (registry `https://example.com/`)
0.000831426s TRACE resolve: cargo::core::resolver: root[1]>breezyshim 1 candidates
0.000840639s TRACE resolve: cargo::core::resolver: root[1]>breezyshim trying 1.0.0
0.000860648s TRACE resolve: cargo::core::resolver: activating breezyshim v1.0.0 (registry `https://example.com/`)
0.000889611s TRACE resolve: cargo::core::resolver: root[2]>debbugs 1 candidates
0.000895597s TRACE resolve: cargo::core::resolver: root[2]>debbugs trying 1.0.0
0.000905397s TRACE resolve: cargo::core::resolver: activating debbugs v1.0.0 (registry `https://example.com/`)
0.000928319s TRACE resolve: cargo::core::resolver: debbugs[3]>debversion 1 candidates
0.000935150s TRACE resolve: cargo::core::resolver: debbugs[3]>debversion trying 0.4.1
0.000943048s TRACE resolve: cargo::core::resolver: activating debversion v0.4.1 (registry `https://example.com/`)
0.000958298s TRACE resolve: cargo::core::resolver: breezyshim[4]>debversion 2 candidates
0.000965032s TRACE resolve: cargo::core::resolver: breezyshim[4]>debversion trying 0.4.1
0.000978927s DEBUG resolve: cargo::core::resolver::context: checking if debversion v0.4.1 (registry `https://example.com/`) is already activated
0.000985793s TRACE resolve: cargo::core::resolver: activating debversion v0.4.1 (registry `https://example.com/`)
0.001015292s TRACE resolve: cargo::core::resolver: debversion[5]>pyo3 0 candidates
0.001021515s TRACE resolve: cargo::core::resolver: debversion[5]>pyo3 -- no candidates
0.001029411s TRACE resolve: cargo::core::resolver::conflict_cache: pyo3 = ">=0.22" adding a skip {}
0.001038246s TRACE resolve: cargo::core::resolver: debversion = "*" skip as not solving debversion v0.4.1 (registry `https://example.com/`): {}
0.001049122s DEBUG resolve: cargo::core::resolver: no candidates found

[x-hgg-x]

The line debversion = "*" skip as not solving debversion v0.4.1 seems wrong, since another candidate for debversion = "*" should be remaining.