Resolver deps returns duplicates

[ehuss]

Problem
The Resolver::deps method returns duplicate deps in situations where a dependency is depended upon with different features in different places. For example, here is what the cargo metadata command does to deduplicate these. Normal build graphs (here) just chew on the duplicates, but is otherwise unaffected.

Would it be possible for these to be de-duplicated in the Resolver? Otherwise, any code calling that method will need to deal with the duplicates.

Steps
I wrote a test in the resolver-tests crate to demonstrate what I mean. I'm not sure if there is a better way to write these kinds of tests. The dep graph looks like this:

root
├── a
│   └── manyfeat (with feat1)
│       └── bitflags
├── b
│   └── manyfeat (with feat2)
│       └── bitflags
└── c
    └── manyfeat (with feat3)
        └── bitflags

#[test]
fn duplicated_deps() {
    let mut manyfeat1 = dep("manyfeat");
    manyfeat1.set_features(vec!["f1"]);
    let mut manyfeat2 = dep("manyfeat");
    manyfeat2.set_features(vec!["f2"]);
    let mut manyfeat3 = dep("manyfeat");
    manyfeat3.set_features(vec!["f3"]);

    use std::collections::BTreeMap;
    let mut features: BTreeMap<&str, Vec<&str>> = BTreeMap::new();
    features.insert("f1", vec![]);
    features.insert("f2", vec![]);
    features.insert("f3", vec![]);
    let manyfeat_id = "manyfeat".to_pkgid();
    let manyfeat = cargo::core::Summary::new(
        manyfeat_id,
        vec![dep("bitflags")],
        &features,
        None::<&String>,
        false,
    )
    .unwrap();

    let input = vec![
        pkg!(("A", "0.0.0") => [manyfeat1]),
        pkg!(("B", "0.0.0") => [manyfeat2]),
        pkg!(("C", "0.0.0") => [manyfeat3]),
        pkg!(("bitflags", "0.0.0")),
        manyfeat,
    ];

    let reg = registry(input);
    let res =
        resolver_tests::resolve_with_config_raw(vec![dep("A"), dep("B"), dep("C")], &reg, None)
            .unwrap();
    println!("{:?}", res);
    for (dep_id, deps) in res.deps(manyfeat_id) {
        for dep in deps {
            println!("{} -> {} kind = {:?}", manyfeat_id, dep_id, dep.kind());
        }
    }
}

Running cargo test -- --nocapture you can see that this will print:

graph: Graph {
  - A v0.0.0 (registry `https://example.com/`)
    - manyfeat v1.0.0 (registry `https://example.com/`)
  - B v0.0.0 (registry `https://example.com/`)
    - manyfeat v1.0.0 (registry `https://example.com/`)
  - C v0.0.0 (registry `https://example.com/`)
    - manyfeat v1.0.0 (registry `https://example.com/`)
  - bitflags v0.0.0 (registry `https://example.com/`)
  - manyfeat v1.0.0 (registry `https://example.com/`)
    - bitflags v0.0.0 (registry `https://example.com/`)
  - root v1.0.0 (registry `https://example.com/`)
    - A v0.0.0 (registry `https://example.com/`)
    - B v0.0.0 (registry `https://example.com/`)
    - C v0.0.0 (registry `https://example.com/`)
}

features: {
  manyfeat v1.0.0 (registry `https://example.com/`): ["f1", "f2", "f3"]
}
manyfeat v1.0.0 (registry `https://example.com/`) -> bitflags v0.0.0 (registry `https://example.com/`) kind = Normal
manyfeat v1.0.0 (registry `https://example.com/`) -> bitflags v0.0.0 (registry `https://example.com/`) kind = Normal
manyfeat v1.0.0 (registry `https://example.com/`) -> bitflags v0.0.0 (registry `https://example.com/`) kind = Normal

Notice that the bitflags dependency appears 3 times. I would expect it to appear once.

Possible Solution(s)
I'm not sure how these duplicates appear, but it would be nice if the duplicate edges weren't added to the graph. If that is not possible, maybe a separate pass to de-duplicate the results? I'm not sure where to begin looking for why this happens. I'm guessing somewhere feature unification happens, and the dependencies are merged without de-duplicating the edges?

cc @Eh2406

[Eh2406]

I had some time to do some digging. I was confused how a hashmap can have duplicate keys... That is not what is happening. The graph shape is correct. In retrospect that was clere from the dbg of res that you had. What is happening is that the edge data is a vec (incase you have a deb and a real dependency on the same package) and we are adding a spurious duplicate.

maybe a separate pass to de-duplicate the results?

The graph is constructed from the parents graph, here could be a good place to deduplicate. But that just begs the question how did it end up duplicated in parents graph?

Looks like we push the dep to the vec every time we activate here. I think the best solution is to replace the vec with a data structure that does not allow duplicates. I will experiment with a HashSet for now. I think we can only have a so many deps on the same package in one cargo.toml so a struct with a field for all the possibilities may save us an allocation.