Make `Fingerprint::combine_commutative` associative

The previous implementation swapped lower and upper 64-bits of a result
of modular addition, so the function was non-associative.

2 files changed, 18 insertions, 1 deletions

diff --git a/compiler/rustc_data_structures/src/fingerprint.rs b/compiler/rustc_data_structures/src/fingerprint.rs
index c9af35da4bc..18a607f9442 100644
--- a/compiler/rustc_data_structures/src/fingerprint.rs
+++ b/compiler/rustc_data_structures/src/fingerprint.rs
@@ -3,6 +3,9 @@ use rustc_serialize::{Decodable, Encodable};
 use std::convert::TryInto;
 use std::hash::{Hash, Hasher};
 
+#[cfg(test)]
+mod tests;
+
 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Clone, Copy)]
 #[repr(C)]
 pub struct Fingerprint(u64, u64);
@@ -54,7 +57,7 @@ impl Fingerprint {
 
         let c = a.wrapping_add(b);
 
-        Fingerprint((c >> 64) as u64, c as u64)
+        Fingerprint(c as u64, (c >> 64) as u64)
     }
 
     pub fn to_hex(&self) -> String {
diff --git a/compiler/rustc_data_structures/src/fingerprint/tests.rs b/compiler/rustc_data_structures/src/fingerprint/tests.rs
new file mode 100644
index 00000000000..9b0783e33ab
--- /dev/null
+++ b/compiler/rustc_data_structures/src/fingerprint/tests.rs
@@ -0,0 +1,14 @@
+use super::*;
+
+// Check that `combine_commutative` is order independent.
+#[test]
+fn combine_commutative_is_order_independent() {
+    let a = Fingerprint::new(0xf6622fb349898b06, 0x70be9377b2f9c610);
+    let b = Fingerprint::new(0xa9562bf5a2a5303c, 0x67d9b6c82034f13d);
+    let c = Fingerprint::new(0x0d013a27811dbbc3, 0x9a3f7b3d9142ec43);
+    let permutations = [(a, b, c), (a, c, b), (b, a, c), (b, c, a), (c, a, b), (c, b, a)];
+    let f = a.combine_commutative(b).combine_commutative(c);
+    for p in &permutations {
+        assert_eq!(f, p.0.combine_commutative(p.1).combine_commutative(p.2));
+    }
+}