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#[derive(Clone, Debug, PartialEq, Eq)]
73pub struct MoveTabuSignature {
74    pub scope: MoveTabuScope,
75    pub entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]>,
76    pub destination_value_tokens: SmallVec<[ScopedValueTabuToken; 2]>,
77    pub move_id: MoveIdentity,
78    pub undo_move_id: MoveIdentity,
79}
80
81impl MoveTabuSignature {
82    pub fn new(scope: MoveTabuScope, move_id: MoveIdentity, undo_move_id: MoveIdentity) -> Self {
83        Self {
84            scope,
85            entity_tokens: SmallVec::new(),
86            destination_value_tokens: SmallVec::new(),
87            move_id,
88            undo_move_id,
89        }
90    }
91
92    pub fn with_entity_tokens<I>(mut self, entity_tokens: I) -> Self
93    where
94        I: IntoIterator<Item = ScopedEntityTabuToken>,
95    {
96        self.entity_tokens = entity_tokens.into_iter().collect();
97        self
98    }
99
100    pub fn with_destination_value_tokens<I>(mut self, destination_value_tokens: I) -> Self
101    where
102        I: IntoIterator<Item = ScopedValueTabuToken>,
103    {
104        self.destination_value_tokens = destination_value_tokens.into_iter().collect();
105        self
106    }
107}
108
109pub(crate) fn encode_usize(value: usize) -> u64 {
110    value as u64
111}
112
113pub(crate) fn encode_option_usize(value: Option<usize>) -> u64 {
114    value.map_or(NONE_ID, encode_usize)
115}
116
117/// Encodes a dynamic list element by its canonical declared source key.
118///
119/// XOR is intentionally a bijection over `u64`: distinct source keys stay
120/// distinct without allocating or depending on `Debug` formatting.
121pub(crate) const fn encode_runtime_dynamic_list_source(source_key: usize) -> u64 {
122    TABU_VALUE_RUNTIME_DYNAMIC_LIST_SOURCE ^ source_key as u64
123}
124
125pub(crate) fn hash_str(value: &str) -> u64 {
126    let mut hasher = DefaultHasher::new();
127    value.hash(&mut hasher);
128    hasher.finish()
129}
130
131struct DebugHashBuffer(SmallVec<[u8; 32]>);
132
133impl Write for DebugHashBuffer {
134    fn write_str(&mut self, value: &str) -> std::fmt::Result {
135        self.0.extend_from_slice(value.as_bytes());
136        Ok(())
137    }
138}
139
140pub(crate) fn hash_debug<T: Debug>(value: &T) -> u64 {
141    let mut formatted = DebugHashBuffer(SmallVec::new());
142    write!(&mut formatted, "{value:?}").expect("formatting into an in-memory buffer cannot fail");
143    let mut hasher = DefaultHasher::new();
144    std::str::from_utf8(&formatted.0)
145        .expect("Debug formatting must produce UTF-8")
146        .hash(&mut hasher);
147    hasher.finish()
148}
149
150pub(crate) fn encode_option_debug<T: Debug>(value: Option<&T>) -> u64 {
151    value.map_or(NONE_ID, hash_debug)
152}
153
154pub(crate) const TABU_OP_SWAP: u64 = 0xF000_0000_0000_0001;
155pub(crate) const TABU_OP_PILLAR_SWAP: u64 = 0xF000_0000_0000_0002;
156pub(crate) const TABU_OP_LIST_SWAP: u64 = 0xF000_0000_0000_0003;
157pub(crate) const TABU_OP_LIST_REVERSE: u64 = 0xF000_0000_0000_0004;
158pub(crate) const TABU_OP_LIST_PERMUTE: u64 = 0xF000_0000_0000_0005;
159pub(crate) const TABU_OP_LIST_MULTI_SWAP: u64 = 0xF000_0000_0000_0006;
160
161pub(crate) fn scoped_move_identity(
162    scope: MoveTabuScope,
163    operation_id: u64,
164    components: impl IntoIterator<Item = u64>,
165) -> MoveIdentity {
166    let mut identity = smallvec![
167        operation_id,
168        encode_usize(scope.descriptor_index),
169        hash_str(scope.variable_name),
170    ];
171    identity.extend(components);
172    identity
173}
174
175pub(crate) fn ordered_coordinate_pair(first: (u64, u64), second: (u64, u64)) -> [(u64, u64); 2] {
176    if first <= second {
177        [first, second]
178    } else {
179        [second, first]
180    }
181}
182
183pub(crate) fn append_canonical_usize_slice_pair(
184    identity: &mut MoveIdentity,
185    left: &[usize],
186    right: &[usize],
187) {
188    let (first, second) = if left <= right {
189        (left, right)
190    } else {
191        (right, left)
192    };
193    identity.push(encode_usize(first.len()));
194    identity.push(encode_usize(second.len()));
195    identity.extend(first.iter().map(|&idx| encode_usize(idx)));
196    identity.push(NONE_ID);
197    identity.extend(second.iter().map(|&idx| encode_usize(idx)));
198}
199
200fn append_unique_tokens<T>(target: &mut SmallVec<[T; 2]>, tokens: &[T])
201where
202    T: Copy + PartialEq,
203{
204    for &token in tokens {
205        if !target.contains(&token) {
206            target.push(token);
207        }
208    }
209}
210
211pub(crate) fn compose_sequential_tabu_signature(
212    prefix: &'static str,
213    left: &MoveTabuSignature,
214    right: &MoveTabuSignature,
215) -> MoveTabuSignature {
216    let mut entity_tokens = left.entity_tokens.clone();
217    append_unique_tokens(&mut entity_tokens, &right.entity_tokens);
218
219    let mut destination_value_tokens = left.destination_value_tokens.clone();
220    append_unique_tokens(
221        &mut destination_value_tokens,
222        &right.destination_value_tokens,
223    );
224
225    let mut move_id = smallvec![hash_str(prefix)];
226    move_id.extend(left.move_id.iter().copied());
227    move_id.extend(right.move_id.iter().copied());
228
229    let mut undo_move_id = smallvec![hash_str(prefix)];
230    undo_move_id.extend(right.undo_move_id.iter().copied());
231    undo_move_id.extend(left.undo_move_id.iter().copied());
232
233    let scope = if left.scope == right.scope {
234        left.scope
235    } else {
236        MoveTabuScope::new(left.scope.descriptor_index, prefix)
237    };
238
239    MoveTabuSignature::new(scope, move_id, undo_move_id)
240        .with_entity_tokens(entity_tokens)
241        .with_destination_value_tokens(destination_value_tokens)
242}
243
244#[cfg(test)]
245mod tests {
246    use std::collections::hash_map::DefaultHasher;
247    use std::hash::{Hash, Hasher};
248
249    use super::hash_debug;
250
251    fn allocated_hash_debug<T: std::fmt::Debug>(value: &T) -> u64 {
252        let mut hasher = DefaultHasher::new();
253        format!("{value:?}").hash(&mut hasher);
254        hasher.finish()
255    }
256
257    #[test]
258    fn stack_debug_hash_matches_allocating_identity() {
259        assert_eq!(hash_debug(&42_usize), allocated_hash_debug(&42_usize));
260        assert_eq!(
261            hash_debug(&("a\nlonger value", vec![1_u8, 2, 3])),
262            allocated_hash_debug(&("a\nlonger value", vec![1_u8, 2, 3]))
263        );
264    }
265}
solverforge_solver/heuristic/move/metadata.rs

solverforge_solver/heuristic/move/
metadata.rs
