solverforge_solver/heuristic/move/
metadata.rs

1use std::collections::hash_map::DefaultHasher;
2use std::fmt::{Debug, Write};
3use std::hash::{Hash, Hasher};
4
5use smallvec::{smallvec, SmallVec};
6
7pub const NONE_ID: u64 = u64::MAX;
8/// Canonical tag for a dynamic list element's declared source key.
9///
10/// Runtime list moves must never hash the debug wrapper (`Dynamic(…)`): it is
11/// an implementation detail and would make an otherwise identical dynamic
12/// declaration use a different tabu identity from its source stream. The
13/// move scope already carries the descriptor and variable identity, so this
14/// tag only distinguishes the dynamic source-key representation inside that
15/// declared slot.
16pub(crate) const TABU_VALUE_RUNTIME_DYNAMIC_LIST_SOURCE: u64 = 0xD1A5_7EED_0000_0001;
17pub type MoveIdentity = SmallVec<[u64; 8]>;
18
19/// Canonical tabu metadata for one move candidate.
20///
21/// The canonical local-search path uses this structure to drive all tabu
22/// dimensions from one source of truth:
23/// - `entity_tokens` for entity tabu
24/// - `destination_value_tokens` for value tabu
25/// - `move_id` for exact move tabu
26/// - `undo_move_id` for reverse-move tabu
27///
28/// Exact-move identities intentionally stay as ordered raw components rather
29/// than pre-hashed scalars so exact and reverse memories retain their original
30/// structure.
31#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
32pub struct MoveTabuScope {
33    pub descriptor_index: usize,
34    pub variable_name: &'static str,
35}
36
37impl MoveTabuScope {
38    pub const fn new(descriptor_index: usize, variable_name: &'static str) -> Self {
39        Self {
40            descriptor_index,
41            variable_name,
42        }
43    }
44
45    pub const fn entity_token(self, entity_id: u64) -> ScopedEntityTabuToken {
46        ScopedEntityTabuToken {
47            scope: self,
48            entity_id,
49        }
50    }
51
52    pub const fn value_token(self, value_id: u64) -> ScopedValueTabuToken {
53        ScopedValueTabuToken {
54            scope: self,
55            value_id,
56        }
57    }
58}
59
60#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
61pub struct ScopedEntityTabuToken {
62    pub scope: MoveTabuScope,
63    pub entity_id: u64,
64}
65
66#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
67pub struct ScopedValueTabuToken {
68    pub scope: MoveTabuScope,
69    pub value_id: u64,
70}
71
72/// The undo identity of a move: either the move identity itself (the move
73/// undoes to the same id it carries) or an explicit distinct reverse id.
74///
75/// Self-undoing moves store one identity instead of two equal ones; the
76/// reverse view resolves to the stored move id.
77#[derive(Clone, Debug, PartialEq, Eq)]
78pub enum MoveUndoIdentity {
79    SameAsMoveId,
80    Explicit(MoveIdentity),
81}
82
83#[derive(Clone, Debug, PartialEq, Eq)]
84pub struct MoveTabuSignature {
85    pub scope: MoveTabuScope,
86    pub entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]>,
87    pub destination_value_tokens: SmallVec<[ScopedValueTabuToken; 2]>,
88    pub move_id: MoveIdentity,
89    pub undo_move_id: MoveUndoIdentity,
90}
91
92impl MoveTabuSignature {
93    /// A move whose undo identity equals its move identity.
94    pub fn new_self_undoing(scope: MoveTabuScope, move_id: MoveIdentity) -> Self {
95        Self {
96            scope,
97            entity_tokens: SmallVec::new(),
98            destination_value_tokens: SmallVec::new(),
99            move_id,
100            undo_move_id: MoveUndoIdentity::SameAsMoveId,
101        }
102    }
103
104    /// A move whose reverse identity is spelled out (distinct undo id).
105    pub fn new(scope: MoveTabuScope, move_id: MoveIdentity, undo_move_id: MoveIdentity) -> Self {
106        Self {
107            scope,
108            entity_tokens: SmallVec::new(),
109            destination_value_tokens: SmallVec::new(),
110            move_id,
111            undo_move_id: MoveUndoIdentity::Explicit(undo_move_id),
112        }
113    }
114
115    /// The reverse identity this move records when it is accepted.
116    pub fn undo_id(&self) -> &MoveIdentity {
117        match &self.undo_move_id {
118            MoveUndoIdentity::SameAsMoveId => &self.move_id,
119            MoveUndoIdentity::Explicit(id) => id,
120        }
121    }
122
123    pub fn with_entity_tokens<I>(mut self, entity_tokens: I) -> Self
124    where
125        I: IntoIterator<Item = ScopedEntityTabuToken>,
126    {
127        self.entity_tokens = entity_tokens.into_iter().collect();
128        self
129    }
130
131    pub fn with_destination_value_tokens<I>(mut self, destination_value_tokens: I) -> Self
132    where
133        I: IntoIterator<Item = ScopedValueTabuToken>,
134    {
135        self.destination_value_tokens = destination_value_tokens.into_iter().collect();
136        self
137    }
138}
139
140pub(crate) fn encode_usize(value: usize) -> u64 {
141    value as u64
142}
143
144pub(crate) fn encode_option_usize(value: Option<usize>) -> u64 {
145    value.map_or(NONE_ID, encode_usize)
146}
147
148/// Encodes a dynamic list element by its canonical declared source key.
149///
150/// XOR is intentionally a bijection over `u64`: distinct source keys stay
151/// distinct without allocating or depending on `Debug` formatting.
152pub(crate) const fn encode_runtime_dynamic_list_source(source_key: usize) -> u64 {
153    TABU_VALUE_RUNTIME_DYNAMIC_LIST_SOURCE ^ source_key as u64
154}
155
156pub(crate) fn hash_str(value: &str) -> u64 {
157    // FNV-1a over the UTF-8 bytes: allocation-free and SipHash-free, so the
158    // immutable static variable-name prefix of a tabu identity composes
159    // without a `DefaultHasher` per pull. Opaque token values only ever
160    // compare against tokens produced by this same function.
161    let mut hash = 0xcbf2_9ce4_8422_2325u64;
162    for byte in value.as_bytes() {
163        hash ^= u64::from(*byte);
164        hash = hash.wrapping_mul(0x0000_0100_0000_01b3);
165    }
166    hash
167}
168
169struct DebugHashBuffer(SmallVec<[u8; 32]>);
170
171impl Write for DebugHashBuffer {
172    fn write_str(&mut self, value: &str) -> std::fmt::Result {
173        self.0.extend_from_slice(value.as_bytes());
174        Ok(())
175    }
176}
177
178pub(crate) fn hash_debug<T: Debug>(value: &T) -> u64 {
179    let mut formatted = DebugHashBuffer(SmallVec::new());
180    write!(&mut formatted, "{value:?}").expect("formatting into an in-memory buffer cannot fail");
181    let mut hasher = DefaultHasher::new();
182    std::str::from_utf8(&formatted.0)
183        .expect("Debug formatting must produce UTF-8")
184        .hash(&mut hasher);
185    hasher.finish()
186}
187
188pub(crate) fn encode_option_debug<T: Debug>(value: Option<&T>) -> u64 {
189    value.map_or(NONE_ID, hash_debug)
190}
191
192pub(crate) const TABU_OP_SWAP: u64 = 0xF000_0000_0000_0001;
193pub(crate) const TABU_OP_PILLAR_SWAP: u64 = 0xF000_0000_0000_0002;
194pub(crate) const TABU_OP_LIST_SWAP: u64 = 0xF000_0000_0000_0003;
195pub(crate) const TABU_OP_LIST_REVERSE: u64 = 0xF000_0000_0000_0004;
196pub(crate) const TABU_OP_LIST_PERMUTE: u64 = 0xF000_0000_0000_0005;
197pub(crate) const TABU_OP_LIST_MULTI_SWAP: u64 = 0xF000_0000_0000_0006;
198
199pub(crate) fn scoped_move_identity(
200    scope: MoveTabuScope,
201    operation_id: u64,
202    components: impl IntoIterator<Item = u64>,
203) -> MoveIdentity {
204    let mut identity = smallvec![
205        operation_id,
206        encode_usize(scope.descriptor_index),
207        hash_str(scope.variable_name),
208    ];
209    identity.extend(components);
210    identity
211}
212
213pub(crate) fn ordered_coordinate_pair(first: (u64, u64), second: (u64, u64)) -> [(u64, u64); 2] {
214    if first <= second {
215        [first, second]
216    } else {
217        [second, first]
218    }
219}
220
221pub(crate) fn append_canonical_usize_slice_pair(
222    identity: &mut MoveIdentity,
223    left: &[usize],
224    right: &[usize],
225) {
226    let (first, second) = if left <= right {
227        (left, right)
228    } else {
229        (right, left)
230    };
231    identity.push(encode_usize(first.len()));
232    identity.push(encode_usize(second.len()));
233    identity.extend(first.iter().map(|&idx| encode_usize(idx)));
234    identity.push(NONE_ID);
235    identity.extend(second.iter().map(|&idx| encode_usize(idx)));
236}
237
238fn append_unique_tokens<T>(target: &mut SmallVec<[T; 2]>, tokens: &[T])
239where
240    T: Copy + PartialEq,
241{
242    for &token in tokens {
243        if !target.contains(&token) {
244            target.push(token);
245        }
246    }
247}
248
249pub(crate) fn compose_sequential_tabu_signature(
250    prefix: &'static str,
251    left: &MoveTabuSignature,
252    right: &MoveTabuSignature,
253) -> MoveTabuSignature {
254    let mut entity_tokens = left.entity_tokens.clone();
255    append_unique_tokens(&mut entity_tokens, &right.entity_tokens);
256
257    let mut destination_value_tokens = left.destination_value_tokens.clone();
258    append_unique_tokens(
259        &mut destination_value_tokens,
260        &right.destination_value_tokens,
261    );
262
263    let mut move_id = smallvec![hash_str(prefix)];
264    move_id.extend(left.move_id.iter().copied());
265    move_id.extend(right.move_id.iter().copied());
266
267    let mut undo_move_id = smallvec![hash_str(prefix)];
268    undo_move_id.extend(right.undo_id().iter().copied());
269    undo_move_id.extend(left.undo_id().iter().copied());
270
271    let scope = if left.scope == right.scope {
272        left.scope
273    } else {
274        MoveTabuScope::new(left.scope.descriptor_index, prefix)
275    };
276
277    MoveTabuSignature::new(scope, move_id, undo_move_id)
278        .with_entity_tokens(entity_tokens)
279        .with_destination_value_tokens(destination_value_tokens)
280}
281
282#[cfg(test)]
283mod tests {
284    use std::collections::hash_map::DefaultHasher;
285    use std::hash::{Hash, Hasher};
286
287    use super::hash_debug;
288
289    fn allocated_hash_debug<T: std::fmt::Debug>(value: &T) -> u64 {
290        let mut hasher = DefaultHasher::new();
291        format!("{value:?}").hash(&mut hasher);
292        hasher.finish()
293    }
294
295    #[test]
296    fn stack_debug_hash_matches_allocating_identity() {
297        assert_eq!(hash_debug(&42_usize), allocated_hash_debug(&42_usize));
298        assert_eq!(
299            hash_debug(&("a\nlonger value", vec![1_u8, 2, 3])),
300            allocated_hash_debug(&("a\nlonger value", vec![1_u8, 2, 3]))
301        );
302    }
303}
solverforge_solver/heuristic/move/metadata.rs

solverforge_solver/heuristic/move/
metadata.rs
