Add a way to make builds with one job deterministic

[gnzlbg]

Currently cargo build -j 1 builds crates, that can be built in parallel, in random order:

This is very painful when trying write a cargotest for a complex situation involving multiple crates:

#[cargo_test]
fn deterministic_builds() {
    let p = project()
        .file(
            "a/Cargo.toml",
            r#"
            [package]
            name = "a"
            version = "0.0.1"
            authors = []
        "#,
        )
        .file(
            "a/src/lib.rs",
            r#"
            pub fn a() {}
        "#,
        )
        .file(
            "b/Cargo.toml",
            r#"
            [package]
            name = "b"
            version = "0.0.1"
            authors = []
        "#,
        )
        .file(
            "b/src/lib.rs",
            r#"
            pub fn b() {}
        "#,
        )
        .file(
            "c/Cargo.toml",
            r#"
            [package]
            name = "c"
            version = "0.0.1"
            authors = []
        "#,
        )
        .file(
            "c/src/lib.rs",
            r#"
            pub fn c() {}
        "#,
        )
        .file(
            "d/Cargo.toml",
            r#"
            [package]
            name = "d"
            version = "0.0.1"
            authors = []
        "#,
        )
        .file(
            "d/src/lib.rs",
            r#"
            pub fn d() {}
        "#,
        )
        .file(
            "Cargo.toml",
            r#"
            [package]
            name = "foo"
            version = "0.0.1"
            authors = []

            [dependencies]
            a = { path = "a" }
            b = { path = "b" }
            c = { path = "c" }
            d = { path = "d" }
        "#,
        )
        .file(
            "src/lib.rs",
            r#"
            extern crate a;
            extern crate b;
            extern crate c;
            extern crate d;
            pub use a::a;
            pub use b::b;
            pub use c::c;
            pub use d::d;
        "#,
        )
        .build();

    p.cargo("build")
        .arg("--verbose")
        .arg("-j")
        .arg("1")
        .with_stderr(
            "\
[COMPILING] a v0.0.1 ([CWD]/a)
[RUNNING] `rustc --crate-name a [..]
[COMPILING] b v0.0.1 ([CWD]/b)
[RUNNING] `rustc --crate-name b [..]
[COMPILING] c v0.0.1 ([CWD]/c)
[RUNNING] `rustc --crate-name c [..]
[COMPILING] d v0.0.1 ([CWD]/d)
[RUNNING] `rustc --crate-name d [..]
[COMPILING] foo v0.0.1 ([CWD])
[RUNNING] `rustc --crate-name foo [..]
[FINISHED] dev [unoptimized + debuginfo] target(s) in [..]
",
        )
        .run();
}

(this test will pass, 1 every 24 times!).

Maybe... we should even make -j 1 being deterministic be the default... Issues about this have been filled in the past #2607 .

[gnzlbg]

@alexcrichton could you point me to the places in the code where the jobs are passed to the executor ?

[alexcrichton]

Most of it's related to this file I believe

[epage]

I suspect #11032 fixed this. Can someone confirm?

[weihanglo]

No. I've updated the test case in the PR description and verified against. It is still not deterministic. DependencyQueue is backed by HashMap so I guess it doesn't really change.