regression: assertion `left == right` failed but it depends on library-unstable details

[BoxyUwU]

• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/chubei.project_euler/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/bbarker.bevy_serde_macros/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/tommarek.MPCHomeControl/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/lht102.coding-problems-practice/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/gh/rainhead.rust-anagrams/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/atrocious_sort-0.1.2/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/gaffer-0.2.0/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/hopscotch-0.1.1/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/proxmox-api-0.1.1/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/rwini-0.1.1/log.txt
• https://crater-reports.s3.amazonaws.com/beta-1.81-2/beta-2024-07-26/reg/workpool-0.2.1/log.txt

[INFO] [stdout] thread 'tests::test_primie_factorization' panicked at src/lib.rs:132:9:
[INFO] [stdout] assertion `left == right` failed
[INFO] [stdout]   left: [PrimeFactor { prime: 2, power: 2 }, PrimeFactor { prime: 5, power: 3 }]
[INFO] [stdout]  right: [PrimeFactor { prime: 5, power: 3 }, PrimeFactor { prime: 2, power: 2 }]

[workingjubilee]

It is probably the case that these include incorrect sort algorithm impls.

I am bringing these to the attention of @orlp and @Voultapher if they wish to inspect the regressions further.

• coding-problems-practice has a now-failing-tests solution, but it actually is still correct according to the original problem.
  • the tests seem to rely on sort_unstable_by having sorted things a certain way, as it only sorts by frequency, not by frequency and then natural order as the tests seem to imply is required: https://github.com/lht102/coding-problems-practice/blob/5b22b46182abe6d0617d087e6b8a0fa22f2edada/leetcode/src/00451_sort_characters_by_frequency/solution.rs#L10-L27
  • however, the original problem specifically mentions that it's okay to get either "eert" or "eetr": https://leetcode.com/problems/sort-characters-by-frequency/description/
• hopscotch has an ord_correct test that is now failing, and while I can't find the sort call, it feels likely the answer is wrong or sort may be implicitly called by quickcheck: https://github.com/plaidfinch/hopscotch/blob/54483dabb3252f00f73432984b42bd00f7471466/tests/hopscotch.rs#L136-L146

[workingjubilee]

I think I am wrong for some most, actually.

• anagrams: uses a HashTrieMap, then asserts on an iter-then-collect-to-vec, a somewhat notorious hazard. https://github.com/rainhead/rust-anagrams/blob/d42b99a1c5d3465d65a6ded34aff0857a0e52bfe/src/lib.rs#L35-L41
• atrocious_sort: appears to be failing in a sort, yes, but is specifically failing on sleep_sort only. did we change something about concurrency? https://github.com/Chromfalke/AtrociousSort/blob/main/src/algorithms/sleep_sort.rs
• bevy_serde_macros
  • seems to be asserting on serialization/deserialization being handled a certain way, but now some whitespace is in the keys?
• gaffer
  • No sorting appears to occur in https://github.com/survemobility/gaffer/blob/fd1cc240414bb5ee61c840538e0ed4f83e5d58dd/tests/integration.rs or the rest of the library at a glance, so I believe that's instead a concurrency bug?
  • Other initial hypothesis is that the library is doing panic recovery. Perhaps some other library in its dep tree is sorting but then panic recovery occurs? survemobility/gaffer@f238bae
• proxmox-api: seems to be another case of asserting after iterating over a hashmap: https://github.com/datdenkikniet/proxmox-api/blob/7d7540839371e3a58837b049997fe5fb8816d0cf/proxmox-api/src/types/multi.rs#L241-L255 actually see orlp's comment.
• rwini: another case of asserting on the iteration of a hashmap!
  • https://github.com/zerodegress/rwini-rs/blob/master/src/data/ini.rs
  • https://github.com/zerodegress/rwini-rs/blob/b7a098fe1e2785bd859a1753ace77c8662d2ebde/src/parser/mod.rs#L42-L66
• workpool: another case where it's less clear and seems likely to be a concurrency issue? https://github.com/ggriffiniii/lateral/blob/469c20d70b2d36b8bc5726281cb98989f4423bec/workpool/src/pool/dynamic_pool.rs#L504-L515

bevy_serde_macros

assertion `left == right` failed
[INFO] [stdout]   left: {" Component3": Array [Array [Number(1), Object {"target": Number(0), "test_enum": Object {"ATest": String("test")}}]], " Component1": Array [Array [Number(0), Null], Array [Number(1), Null]], " Component2": Array [Array [Number(1), Object {"target": Number(0)}]]}
[INFO] [stdout]  right: {"Component3": Array [Array [Number(1), Object {"target": Number(0), "test_enum": Object {"ATest": String("test")}}]], "Component2": Array [Array [Number(1), Object {"target": Number(0)}]], "Component1": Array [Array [Number(0), Null], Array [Number(1), Null]]}

Either way, these do not seem to be directly from the sort changes.

[Voultapher]

coding-problems-practice has a now-failing-tests solution, but it actually is still correct according to the original problem.
the tests seem to rely on sort_unstable_by having sorted things a certain way,

sort_unstable* is unstable as the name says and the new implementation is deterministic as the previous one was, but it produces a different equal element ordering than the one before, so a test that relies on one specific order but uses sort_unstable is only valid for one version of Rust.

however, the original problem specifically mentions that it's okay to get either "eert" or "eetr"

I think the correct way to test that would be to do stable sort or assert_matches!(val, "eert" | "eetr").

[Voultapher]

atrocious_sort: appears to be failing in a sort, yes, but is specifically failing on sleep_sort only. did we change something about concurrency? https://github.com/Chromfalke/AtrociousSort/blob/main/src/algorithms/sleep_sort.rs

Looking at the implementation, it sleeps for milliseconds, I fail to see how that could ever work reliably. The OS can decide to wake the threads up at some later point in time, sleep does not guarantee a fixed wakeup time. Plus it doesn't use latches, so it's spawn + sleep before the next thread is spawned. IMO that implementation is just plain broken.

[Voultapher]

I'm a little surprised by how many instances there are of relying on the order of hashmaps, the order is randomized with the default hasher. Looking at the linked code they seem to be using the default hasher, how come these tests ever reliably work during local development? What am I missing here?

[Voultapher]

gaffer
Other initial hypothesis is that the library is doing panic recovery. Perhaps some other library in its dep tree is sorting but then panic recovery occurs? survemobility/gaffer@f238bae

I suspect it's just racy. I checked the project out locally and ran cargo t, on my initial run I got:

test source::test::queued_resets_recurring ... FAILED

failures:

---- source::test::queued_resets_recurring stdout ----
thread 'source::test::queued_resets_recurring' panicked at src/source.rs:320:9:
assertion `left == right` failed
  left: [Tester(3), Tester(2), Tester(1)]
 right: [Tester(2)]


failures:
    source::test::queued_resets_recurring

test result: FAILED. 36 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.02s

Which is a completely different test, and the one in the crater run passed. Second run all tests pass.

[orlp]

@workingjubilee I find the proxmox-api case very strange: https://github.com/datdenkikniet/proxmox-api/blob/7d7540839371e3a58837b049997fe5fb8816d0cf/proxmox-api/src/types/multi.rs#L241-L255

Note that the portion of the serde output that was changed is actually a BTreeMap, not a HashMap.

[workingjubilee]

@orlp Thanks for catching that! I retract my comments re: "iterating over a hashmap" for that library, but it still seems very odd.

[workingjubilee]

Somewhat shockingly, the Project Euler code is also operating with a hashmap: https://github.com/chubei/project_euler/blob/d100bed4c6b7c417276ccba051567c53ed869d40/src/lib.rs#L39-L48

I really expected that one to be due to sorting issues...

I'm a little surprised by how many instances there are of relying on the order of hashmaps, the order is randomized with the default hasher. Looking at the linked code they seem to be using the default hasher, how come these tests ever reliably work during local development? What am I missing here?

There is a certain sort of person who only ever writes and runs a test once.

I do not mean to accuse, but if they only ran the test a few times, it is possible the hashes happened to work out for them. Even if the hashing perfectly randomizes the keys, if you assert on the order of only 2 items, then it comes up as a coinflip either way. It's reasonable for that to pass 2-4 times in a row if you are lucky.