Cargo.lock package order is unstable across different cargo versions

[teor2345]

Problem

When a lockfile contains multiple entries with the same package name and version, but different sources, the order of these packages in the lockfile changes between builds. (Even though the dependencies are exactly the same.)

Since our project commits the lockfile to git, these redundant changes produce commit noise, checkout conflicts, and merge conflicts.

Steps

Stable to nightly:

1. Build ZcashFoundation/zebra@6bb5220 with nightly cargo
2. Run git diff

Nightly to stable:

1. Build ZcashFoundation/zebra@64662a7 with stable cargo
2. Run git diff

Building on a different version changes the lockfile, even though there haven't been any dependency changes.

Note: cargo just needs to do dependency resolution, so a cargo check should work just as well as a build.

Possible Solution(s)

• Sort the lockfile by name, version, and source
• Workaround: warn when a build uses packages with the same name and version from different sources

Notes

Output of cargo version:

cargo +nightly --version
cargo 1.52.0-nightly (90691f2bf 2021-03-16)
cargo +stable --version
cargo 1.51.0 (43b129a20 2021-03-16)

[alexcrichton]

Thanks for the report! Can you clarify a bit, though, to help reproduce this?

I am unable to get Cargo to nondeterministically generate a particular lock file, the ordering of crates in a lock file is always stable given a singular version of Cargo. What I do see, however, is that stable cargo and nightly cargo are producing the different orderings. Is that the behavior you're seeing as well? Or are you seeing the same Cargo produce different versions of a lock file?

[teor2345]

I am unable to get Cargo to nondeterministically generate a particular lock file, the ordering of crates in a lock file is always stable given a singular version of Cargo. What I do see, however, is that stable cargo and nightly cargo are producing the different orderings. Is that the behavior you're seeing as well? Or are you seeing the same Cargo produce different versions of a lock file?

I think you're right, I was confused because:

• the commits and cargo both changed the lockfile, and
• different developers on our team use different cargo versions.

It would be great to have an explicit, deterministic order across cargo versions. But perhaps it's not such a priority if the order only changes between releases, and only for a few crates.

[alexcrichton]

Ok thanks for the info! This is definitely a bug in Cargo and something we strive to not have happen. This is caught up in the larger change for switching the defaults for git dependencies to the HEAD branch instead of a hardcoded master branch.

The PR at fault here is #9133. The change there is that Ord for SourceId changed from being hand-rolled to being derived, and the derived variant is different from the hand-rolled variant. I didn't realize that it would affect situations like this and the lock file.

I'm unfortunately not sure what to do about this change. If we caught this soon after landing I'd say we should revert and fix this before re-landing, but this change has been out for long enough that I don't think it's as feasible to revert any more. At best all I can think of is to hopefully learn from this and ensure that this doesn't happen again in Cargo :(

[teor2345]

I didn't realize that it would affect situations like this and the lock file.

To be fair, this situation should be rare - it was actually a bug in our dependencies where we changed one crate in our workspace, rather than patching them all.

I don't think it's as feasible to revert any more

I think a revert would just create a bunch of new ordering issues.

And I can understand switching to derived Ord - that way, you never forget a new field. (Forgetting fields would definitely cause you ordering issues.)

Thinking about this a bit more...

How can you make sure the ordering doesn't change in future?

• new fields need to be added to the end of any types with derived Ord impls
  • add a comment to those types
  • how do you make sure you dependencies don't change their orders?
• how do you test that encoding/decoding/type changes don't change the order?
  • add some fixed test cases
  • how do you do randomised property testing?

It's really tricky, we had a similar issue recently where we left a new field out of a manual PartialEq impl. proptest didn't pick it up, because the edge case was very low probability. You'd need coverage-guided fuzzing or similar techniques to find it.

It's probably not worth the effort to write a big test harness for these kinds of low-impact, low-probability bugs. But maybe a crater run with a diff would help detect future issues like this? (You might already do that!)

[alexcrichton]

Discussion at today's Cargo meeting concluded that we should:

• Revert Change git dependencies to use HEAD by default  #9133 on beta, restoring the order between stable/beta
• Investigate a fix (now posted as Fix disagreement about lockfile ordering on stable/nightly #9384) and land on nightly to have all three channels agree again

This will mean that if projects have switched to using the beta/nightly lock file format they'll need to switch back (sorry about that!) but hopefully the transition period won't be too large. I've tried to add at least a small test to catch changes to this in the future as well.