metrale_grammar/support/
hash.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2//
3// Hash-combining helpers — port of the genuinely-reusable part of
4// `cpp/support/utils.h`.
5//
6// Skipped from `utils.h` (C++-template machinery with no Rust need):
7//   - `HashByMembers` / `XGRAMMAR_HASH_BY_MEMBERS`: replaced by
8//     `#[derive(Hash)]`.
9//   - `std::hash` specializations for pair/tuple/vector: Rust derives
10//     these.
11//   - `PartialResult` / `Result` / `ResultOk` / `ResultErr` /
12//     `Convert`: replaced by the standard library `Result`.
13//   - `TypedError`, `ThrowVariantError`, `GetMessageFromVariantError`:
14//     replaced by `thiserror`-based error enums.
15//   - `XGRAMMAR_UNREACHABLE`, `EqualByMembers` / `XGRAMMAR_EQUAL_BY_MEMBERS`:
16//     replaced by `unreachable!()` and `#[derive(PartialEq, Eq)]`.
17//
18// Only `HashCombineBinary` / `HashCombine` carry over: they implement
19// the specific boost-derived mixing function xgrammar relies on for
20// structural hashes, which `#[derive(Hash)]` does not reproduce.
21
22/// Mix `value` into `seed` in place.
23///
24/// Faithful to C++ `HashCombineBinary` — the boost `hash_combine`
25/// 64-bit mixing step. Uses wrapping arithmetic to match C++ unsigned
26/// overflow semantics.
27pub fn hash_combine_binary(seed: &mut u64, value: u64) {
28    *seed ^= value
29        .wrapping_add(0x9e3779b97f4a7c15)
30        .wrapping_add(*seed << 6)
31        .wrapping_add(*seed >> 2);
32}
33
34/// Fold a slice of values into a single combined hash, starting from
35/// seed `0`. Faithful to the variadic C++ `HashCombine`.
36pub fn hash_combine(values: &[u64]) -> u64 {
37    let mut seed = 0u64;
38    for &v in values {
39        hash_combine_binary(&mut seed, v);
40    }
41    seed
42}
43
44#[cfg(test)]
45mod tests {
46    use super::*;
47
48    #[test]
49    fn combine_binary_is_deterministic() {
50        let mut a = 0u64;
51        let mut b = 0u64;
52        hash_combine_binary(&mut a, 42);
53        hash_combine_binary(&mut b, 42);
54        assert_eq!(a, b);
55        assert_ne!(a, 0);
56    }
57
58    #[test]
59    fn combine_binary_order_sensitive() {
60        let mut a = 0u64;
61        hash_combine_binary(&mut a, 1);
62        hash_combine_binary(&mut a, 2);
63
64        let mut b = 0u64;
65        hash_combine_binary(&mut b, 2);
66        hash_combine_binary(&mut b, 1);
67
68        assert_ne!(a, b);
69    }
70
71    #[test]
72    fn combine_matches_manual_folding() {
73        let mut seed = 0u64;
74        hash_combine_binary(&mut seed, 7);
75        hash_combine_binary(&mut seed, 8);
76        hash_combine_binary(&mut seed, 9);
77        assert_eq!(hash_combine(&[7, 8, 9]), seed);
78    }
79
80    #[test]
81    fn combine_empty_is_zero() {
82        assert_eq!(hash_combine(&[]), 0);
83    }
84
85    #[test]
86    fn combine_distinguishes_inputs() {
87        assert_ne!(hash_combine(&[1, 2, 3]), hash_combine(&[1, 2, 4]));
88        assert_ne!(hash_combine(&[1, 2]), hash_combine(&[2, 1]));
89    }
90
91    #[test]
92    fn combine_no_overflow_panic() {
93        // Large values must not panic (wrapping arithmetic).
94        let mut seed = u64::MAX;
95        hash_combine_binary(&mut seed, u64::MAX);
96        let _ = hash_combine(&[u64::MAX, u64::MAX, u64::MAX]);
97    }
98}
metrale_grammar/support/hash.rs

metrale_grammar/support/
hash.rs
