Sort order inconsistent on 32-bit archs

[strophy]

I'm trying to package https://github.com/tweag/nickel which depends on pubgrub. One of the tests uses pubgrub to verify that certain output indicating a package resolution error will occur in the case of bad input. This test consistently fails under Alpine Linux 3.22 on all 32 bit architectures I'm trying to package for: x86, armv7 and armhf

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ Snapshot Summary ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Snapshot file: package/tests/snapshots/integration__package__tests__integration__inputs__path__conflicting-index-deps__Nickel-pkg.ncl.snap
Snapshot: package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl
Source: package/tests/integration.rs:266
────────────────────────────────────────────────────────────────────────────────
test package/tests/integration/inputs/path/path-to-index-dep/Nickel-pkg.ncl               ... ok
Expression: e.to_string()
────────────────────────────────────────────────────────────────────────────────
-old snapshot
+new results
────────────┬───────────────────────────────────────────────────────────────────
    1     1 │ package version resolution failed:
    2       │-Because 'Path <filtered> depends on github:example/leaf 0.1.0 and top-level package 0.1.0 depends on 'Path <filtered> top-level package 0.1.0 depends on github:example/leaf 0.1.0.
    3       │-And because top-level package 0.1.0 depends on github:example/leaf 0.1.1, top-level package 0.1.0 is forbidden.
          2 │+Because 'Path <filtered> depends on github:example/leaf 0.1.0 and top-level package 0.1.0 depends on github:example/leaf 0.1.1, top-level package 0.1.0, 'Path <filtered> * are incompatible.
          3 │+And because top-level package 0.1.0 depends on 'Path <filtered> top-level package 0.1.0 is forbidden.
────────────┴───────────────────────────────────────────────────────────────────
Stopped on the first failure. Run `cargo insta test` to run all snapshots.
thread '<unnamed>' panicked at /home/buildozer/.cargo/registry/src/index.crates.io-1949cf8c6b5b557f/insta-1.43.2/src/runtime.rs:694:13:
snapshot assertion for 'package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl' failed in line 266
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
test package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl          ... FAILED
Already have a cache entry at "/tmp/.tmpxu7Ted/cache_dir/git-packages/44b1c226afdc6220892c242f6b05c9c654aa6065/"
test package/tests/integration/inputs/path/duplicate-path/Nickel-pkg.ncl                  ... ok
test package/tests/integration/inputs/path/git-path-dep/Nickel-pkg.ncl                    ... ok
failures:
---- package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl ----
test panicked: snapshot assertion for 'package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl' failed in line 266
failures:
    package/tests/integration/inputs/path/conflicting-index-deps/Nickel-pkg.ncl
test result: FAILED. 14 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 2.32s
error: test failed, to rerun pass `-p nickel-lang-package --test integration`

While the content of the message effectively carries the same meaning, the different sort order causes the test to fail. Is this simply a case of this not being a well-written test, or not a reasonable thing to test? Or is there something fundamentally different in pubgrub regarding how 32-bit builds sort the dependencies when trying to resolve them?

Ref: tweag/nickel#2372

[konstin]

Can you provide a standalone example that reproduces this?

I haven't seen any differences between 64-bit and 32-bit error messages before. Is the order nickel inserts packages and dependencies the same between 64-bit and 32-bit?

[jneem]

I haven't found the time to make a standalone example, but I did trace our test case. The first difference in the debug logs comes after pubgrub calls DependencyProvider::get_dependencies, which returns 2 different dependencies. On 32-bit, the logs go like:

current_decision_level: DecisionLevel(1)
package_assignments:
Id::<Package>(0) = 'top-level package': decision range: DecisionLevel(0)..DecisionLevel(1)
derivations:
  DecisionLevel(0), cause: Id::<String>>(0)
,assignments_intersection: Decision: level 1, v = 0.1.0	
Id::<Package>(1) = 'github:example/leaf': decision range: DecisionLevel(1)..DecisionLevel(1)
derivations:
  DecisionLevel(1), cause: Id::<String>>(1)
,assignments_intersection: Derivations term: 0.1.1	
Id::<Package>(2) = ''Path ../single-index-dep': decision range: DecisionLevel(1)..DecisionLevel(1)
derivations:
  DecisionLevel(1), cause: Id::<String>>(2)
,assignments_intersection: Derivations term: *

On 64-bit, they go like

current_decision_level: DecisionLevel(1)
package_assignments:
Id::<Package>(0) = 'top-level package': decision range: DecisionLevel(0)..DecisionLevel(1)
derivations:
  DecisionLevel(0), cause: Id::<String>>(0)
,assignments_intersection: Decision: level 1, v = 0.1.0	
Id::<Package>(1) = ''Path ../single-index-dep': decision range: DecisionLevel(1)..DecisionLevel(1)
derivations:
  DecisionLevel(1), cause: Id::<String>>(1)
,assignments_intersection: Derivations term: *	
Id::<Package>(2) = 'github:example/leaf': decision range: DecisionLevel(1)..DecisionLevel(1)
derivations:
  DecisionLevel(1), cause: Id::<String>>(2)
,assignments_intersection: Derivations term: 0.1.1

After that, the traces diverge quite a bit (on 32-bit, pubgrub calls DependencyProvider::prioritize on the github dependency, while on 64-bit it calls prioritize on the path dependency first).

I didn't look further, because I noticed that the dependency constraints in pubgrub::Dependencies are stored in a hash map, so I guess the order is not really defined?

[konstin]

That makes it clearer!

The problem is that while the default HashMap changes iteration order on each use, FxHashMap has a stable iteration order - except when switching target.

The code below visualizes this:

cargo run --target i686-unknown-linux-gnu
cargo run --target x86_64-unknown-linux-gnu

use rustc_hash::FxHashMap;
use std::collections::HashMap;

fn main() {
    let mut x: FxHashMap<usize, String> = FxHashMap::default();
    for i in 0..80 {
        x.insert(i, i.to_string());
    }
    let mut acc = String::new();
    for (_, v) in &x {
        acc.push_str(v);
    }
    println!("{}", acc);

    let mut x = HashMap::new();
    for i in 0..80 {
        x.insert(i, i.to_string());
    }
    let mut acc = String::new();
    for (_, v) in &x {
        acc.push_str(v);
    }
    println!("{}", acc);
}

I think fixing that is a breaking change? @Eh2406 @mpizenberg

[konstin]

It seems the nickel implementation currently depends on pubgrub's internal (fallback) priority tracking. Does the resolution become stable with a prioritize that has a distinct value for each package?

[mpizenberg]

Yes, as @konstin said, we chose stable hash maps, but it seems they are only stable on a give platform, and not across them. Using your own prioritization, which would also be stable on different platforms would "solve" your issue I guess. Or alternatively have different test vectors for different platforms @strophy ?

I don’t think we are specifically tied to the current prioritization either, as it doesn’t change correctness of the results. It will change performance characteristics though, so that might be surprising for people keeping the default prioritization if it gets slower. Are there people aware of other hash maps with good performance (and low collision) that would be stable even on different platforms?

[strophy]

@mpizenberg as a packager this issue isn't a showstopper because it doesn't actually affect usability, my solution is to simply disable the test. I'll leave it to @jneem to possibly implement different test vectors if pubgrub authors decide this instability across platforms we have identified here isn't worth a breaking change, or change in performance characteristics.