False positive cyclic dependencies when building for different targets

[jstuczyn]

Problem

If particular crate depends on crate A and crate B, such that if imported together, they would cause cyclic dependency, but crate B is only imported on specific target, for example wasm32, cargo will error out regardless of that target restriction.

Steps

1. Create brand new crate foo with the following:

❯ tree
.
└── foo
    ├── Cargo.lock
    ├── Cargo.toml
    └── src
        └── lib.rs

2. Include some dependencies that might cause cyclic problems if imported together, but keep one of them locked behind specific build target. For the sake of this example, I'm including the ones that caused problems to me personally. I would assume there would be more of them. Note that in "real world", my issue was caused by the problematic dependency being pulled indirectly through different crate.

Sample Cargo.toml:

[package]
name = "foo"
version = "0.1.0"
edition = "2018"

[dependencies]
reqwest = "0.11.4"
sqlx = { version = "0.5.5", features = [ "runtime-tokio-rustls", "offline" ]}

[target.'cfg(target_arch = "wasm32")'.dependencies]
getrandom = { version = "0.2", features = ["js"] }

3. Try to build it explicitly for an x86 target: cargo build --target x86_64-unknown-linux-gnu. In my case I received the following cyclic dependency error:

cargo build --target x86_64-unknown-linux-gnu
    Updating crates.io index
error: cyclic package dependency: package `ahash v0.7.4` depends on itself. Cycle:
package `ahash v0.7.4`
    ... which is depended on by `hashbrown v0.11.2`
    ... which is depended on by `indexmap v1.7.0`
    ... which is depended on by `serde_json v1.0.64`
    ... which is depended on by `wasm-bindgen v0.2.74`
    ... which is depended on by `js-sys v0.3.51`
    ... which is depended on by `getrandom v0.2.3`
    ... which is depended on by `ahash v0.7.4`

4. If getrandom dependency is removed, everything builds without errors.

Notes

The issue was tested to present on the following versions:
❯ cargo version
cargo 1.53.0 (4369396 2021-04-27)

❯ cargo version
cargo 1.54.0-beta (5ae8d74 2021-06-22)

❯ cargo version
1.55.0-nightly (27277d9 2021-07-16)

[ehuss]

I believe this is expected behavior and a legitimate cycle. When cargo builds the lockfile, it builds it for all target platforms concurrently (essentially ignoring the target restrictions). This is so that the lock file is the same no matter what platform you build on.

In this case, the feature unification results in the cycle as shown.

[ehuss]

Closing as I believe this is an actual cycle. If you have more information, feel free to re-open.

[ehuss]

I'm going to reopen, as I think this is more of an issue than I first considered, and possibly easier to fix than rewriting the resolver 😆 .

Here is a demo using cargo's testsuite:

use cargo_test_support::registry::{Dependency, Package};

#[cargo_test]
fn target_specific_cycle() {
    // Demonstration of dependency cycle that is probably a false positive.
    //
    // Alone, each member works fine. It is only when they are combined in a
    // workspace where it fails. Separately their dependency trees are:
    //
    // member-x86 v1.0.0
    // ├── ahash v1.0.0
    // │   └── getrandom v1.0.0
    // └── serde_json v1.0.0 features:indexmap
    //     └── indexmap v1.0.0
    //         └── ahash v1.0.0  (*)
    //
    // member-wasm v1.0.0
    // └── getrandom v1.0.0 features:js,wasm-bindgen
    //     └── wasm-bindgen v1.0.0
    //         └── serde_json v1.0.0
    //
    // But when in the same workspace, the resolver wants to treat it as-if
    // all targets are built concurrently:
    //
    // error: cyclic package dependency: package `ahash v1.0.0` depends on itself. Cycle:
    // package `ahash v1.0.0`
    //     ... which satisfies dependency `ahash = "^1.0"` of package `indexmap v1.0.0`
    //     ... which satisfies dependency `indexmap = "^1.0"` of package `serde_json v1.0.0`
    //     ... which satisfies dependency `serde_json = "^1.0"` of package `wasm-bindgen v1.0.0`
    //     ... which satisfies dependency `wasm-bindgen = "^1.0"` of package `getrandom v1.0.0`
    //     ... which satisfies dependency `getrandom = "^1.0"` of package `ahash v1.0.0`
    //
    // This cycle doesn't make sense. When building the wasm target, we're not
    // even including ahash. When building for x86, there is no dependency
    // edge to wasm-bindgen.
    Package::new("ahash", "1.0.0")
        .dep("getrandom", "1.0")
        .publish();

    Package::new("getrandom", "1.0.0")
        .add_dep(
            Dependency::new("wasm-bindgen", "1.0")
                .optional(true)
                .target("wasm32-unknown-unknown"),
        )
        .feature("js", &["wasm-bindgen"])
        .publish();

    Package::new("wasm-bindgen", "1.0.0")
        .dep("serde_json", "1.0")
        .publish();

    Package::new("serde_json", "1.0.0")
        .add_dep(Dependency::new("indexmap", "1.0").optional(true))
        .publish();

    Package::new("indexmap", "1.0.0")
        .dep("ahash", "1.0")
        .publish();

    let p = project()
        .file(
            "Cargo.toml",
            r#"
                [workspace]
                members = ["member-x86", "member-wasm"]
            "#,
        )
        .file(
            "member-x86/Cargo.toml",
            r#"
                [package]
                name = "member-x86"
                version = "1.0.0"

                [dependencies]
                ahash = "1.0"
                serde_json = { version = "1.0", features = ["indexmap"] }
            "#,
        )
        .file("member-x86/src/lib.rs", "")
        .file(
            "member-wasm/Cargo.toml",
            r#"
                [package]
                name = "member-wasm"
                version = "1.0.0"

                [dependencies]
                getrandom = { version = "1.0", features = ["js"] }
            "#,
        )
        .file("member-wasm/src/lib.rs", "")
        .build();

    p.cargo("generate-lockfile").run();
}

We discussed it amongst the team, and we think it may be feasible to push the cycle check to a later stage. However, there is a concern of exactly where to put it. If it is put too late, then some legitimate cycles for other platforms may not get detected. There are also some questions about catching cycles due to targets, and catching cycles due to features. The cycle detection could be moved to the new resolver (after #5565/#8832 are closed which will transition all feature resolving to the new resolver). Another possible place is in unit-graph generation.

Also, there is some risk that some parts of cargo are not resilient to cycles in the dependency graph. We think, since dev-dependency cycles are a thing, that shouldn't be too much of a problem. However, it is a risk.

I'm also wondering if this is essentially the same as #8734.

[maxcountryman]

Are there any workarounds to this? (I have this exact cycle.)