solverforge_solver/heuristic/selector/
mimic.rs

1/* Mimic selectors for synchronized selection across multiple selectors.
2
3Mimic selectors enable multiple selectors to select the same element in lockstep.
4This is essential for:
5- Nearby selection: Get the "origin" entity that was already selected
6- Coordinated moves: Ensure multiple parts of a move reference the same entity
7
8# Architecture
9
10- [`MimicRecordingEntitySelector`]: Wraps a child selector and records each selected entity
11- [`MimicReplayingEntitySelector`]: Replays the entity recorded by a recording selector
12*/
13
14use std::cell::Cell;
15use std::fmt::Debug;
16use std::ptr::NonNull;
17
18use solverforge_core::domain::PlanningSolution;
19use solverforge_scoring::Director;
20
21use super::entity::{EntityReference, EntitySelector};
22
23/* Shared state between recording and replaying selectors.
24
25Uses `Cell` for interior mutability — no locking overhead since all access
26is sequential single-threaded (record first, replay after).
27*/
28#[derive(Debug, Default, Clone, Copy)]
29struct MimicState {
30    // Whether hasNext has been called on the recorder.
31    has_next_recorded: bool,
32    // The result of the last hasNext call.
33    has_next: bool,
34    // Whether next has been called on the recorder.
35    next_recorded: bool,
36    // The last recorded entity reference.
37    recorded_entity: Option<EntityReference>,
38}
39
40/* Heap-allocated shared mimic state with manual reference counting.
41
42Replaces `Arc<RwLock<MimicState>>` with zero-overhead shared access:
43- No atomic operations (non-atomic refcount)
44- No locking (Cell instead of RwLock)
45- All access is sequential single-threaded
46*/
47struct SharedMimicState {
48    state: Cell<MimicState>,
49    refcount: Cell<usize>,
50}
51
52/// Handle for sharing mimic state between recording and replaying selectors.
53///
54/// Uses a manually reference-counted heap allocation with `Cell` for interior
55/// mutability. No `Arc`, no `RwLock` — all access is sequential single-threaded.
56pub struct MimicRecorder {
57    ptr: NonNull<SharedMimicState>,
58    // Identifier for debugging.
59    id: String,
60}
61
62impl MimicRecorder {
63    pub fn new(id: impl Into<String>) -> Self {
64        let shared = Box::new(SharedMimicState {
65            state: Cell::new(MimicState::default()),
66            refcount: Cell::new(1),
67        });
68        Self {
69            ptr: NonNull::from(Box::leak(shared)),
70            id: id.into(),
71        }
72    }
73
74    #[inline]
75    fn shared(&self) -> &SharedMimicState {
76        // SAFETY: ptr is always valid while any MimicRecorder referencing it exists
77        // (maintained by Clone incrementing refcount and Drop decrementing/deallocating).
78        unsafe { self.ptr.as_ref() }
79    }
80
81    // Records a has_next result.
82    fn record_has_next(&self, has_next: bool) {
83        self.shared().state.set(MimicState {
84            has_next_recorded: true,
85            has_next,
86            next_recorded: false,
87            recorded_entity: None,
88        });
89    }
90
91    // Records a next result.
92    fn record_next(&self, entity: EntityReference) {
93        self.shared().state.set(MimicState {
94            has_next_recorded: true,
95            has_next: true,
96            next_recorded: true,
97            recorded_entity: Some(entity),
98        });
99    }
100
101    pub fn get_has_next(&self) -> Option<bool> {
102        let state = self.shared().state.get();
103        if state.has_next_recorded {
104            Some(state.has_next)
105        } else {
106            None
107        }
108    }
109
110    pub fn get_recorded_entity(&self) -> Option<EntityReference> {
111        let state = self.shared().state.get();
112        if state.next_recorded {
113            state.recorded_entity
114        } else {
115            None
116        }
117    }
118
119    pub fn id(&self) -> &str {
120        &self.id
121    }
122
123    /// Resets the state for a new iteration.
124    pub fn reset(&self) {
125        self.shared().state.set(MimicState::default());
126    }
127}
128
129impl Clone for MimicRecorder {
130    fn clone(&self) -> Self {
131        let shared = self.shared();
132        shared.refcount.set(shared.refcount.get() + 1);
133        Self {
134            ptr: self.ptr,
135            id: self.id.clone(),
136        }
137    }
138}
139
140impl Drop for MimicRecorder {
141    fn drop(&mut self) {
142        let shared = self.shared();
143        let rc = shared.refcount.get() - 1;
144        if rc == 0 {
145            // SAFETY: last reference — deallocate. The pointer was created via
146            // Box::leak in `new()`, so reconstructing the Box is valid.
147            unsafe {
148                drop(Box::from_raw(self.ptr.as_ptr()));
149            }
150        } else {
151            shared.refcount.set(rc);
152        }
153    }
154}
155
156impl Debug for MimicRecorder {
157    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
158        f.debug_struct("MimicRecorder")
159            .field("id", &self.id)
160            .field("state", &self.shared().state.get())
161            .finish()
162    }
163}
164
165/* SAFETY: MimicRecorder is used single-threaded within a solver step.
166The shared state is accessed sequentially: record first, replay after.
167Send is needed because EntitySelector requires Send.
168*/
169unsafe impl Send for MimicRecorder {}
170unsafe impl Sync for MimicRecorder {}
171
172/// An entity selector that records each selected entity for replay by other selectors.
173///
174/// This is used to synchronize selection across multiple selectors. The recording
175/// selector wraps a child selector and broadcasts each selected entity to all
176/// replaying selectors that share the same recorder.
177///
178/// # Zero-Erasure Design
179///
180/// The child entity selector `ES` is stored as a concrete generic type parameter,
181/// eliminating virtual dispatch overhead when iterating over entities.
182pub struct MimicRecordingEntitySelector<S, ES> {
183    // The child selector that actually selects entities (zero-erasure).
184    child: ES,
185    // The recorder that broadcasts selections.
186    recorder: MimicRecorder,
187    // Marker for solution type.
188    _phantom: std::marker::PhantomData<fn() -> S>,
189}
190
191impl<S, ES> MimicRecordingEntitySelector<S, ES> {
192    pub fn new(child: ES, recorder: MimicRecorder) -> Self {
193        Self {
194            child,
195            recorder,
196            _phantom: std::marker::PhantomData,
197        }
198    }
199
200    pub fn recorder(&self) -> MimicRecorder {
201        self.recorder.clone()
202    }
203}
204
205impl<S: PlanningSolution, ES: Debug> Debug for MimicRecordingEntitySelector<S, ES> {
206    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
207        f.debug_struct("MimicRecordingEntitySelector")
208            .field("child", &self.child)
209            .field("recorder_id", &self.recorder.id)
210            .finish()
211    }
212}
213
214impl<S, ES> EntitySelector<S> for MimicRecordingEntitySelector<S, ES>
215where
216    S: PlanningSolution,
217    ES: EntitySelector<S>,
218{
219    fn iter<'a, D: Director<S>>(
220        &'a self,
221        score_director: &'a D,
222    ) -> impl Iterator<Item = EntityReference> + 'a {
223        // Reset for new iteration
224        self.recorder.reset();
225
226        let child_iter = self.child.iter(score_director);
227        RecordingIterator {
228            inner: child_iter,
229            recorder: &self.recorder,
230        }
231    }
232
233    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
234        self.child.size(score_director)
235    }
236
237    fn is_never_ending(&self) -> bool {
238        self.child.is_never_ending()
239    }
240}
241
242// Iterator that records each entity as it's yielded.
243struct RecordingIterator<'a, I> {
244    inner: I,
245    recorder: &'a MimicRecorder,
246}
247
248impl<'a, I: Iterator<Item = EntityReference>> Iterator for RecordingIterator<'a, I> {
249    type Item = EntityReference;
250
251    fn next(&mut self) -> Option<Self::Item> {
252        let next = self.inner.next();
253        match next {
254            Some(entity) => {
255                self.recorder.record_next(entity);
256                Some(entity)
257            }
258            None => {
259                self.recorder.record_has_next(false);
260                None
261            }
262        }
263    }
264}
265
266/// An entity selector that replays the last entity recorded by a recording selector.
267///
268/// This selector always yields exactly one entity (the last one recorded) or no entities
269/// if the recording selector hasn't recorded anything yet.
270pub struct MimicReplayingEntitySelector {
271    // The recorder to replay from.
272    recorder: MimicRecorder,
273}
274
275impl MimicReplayingEntitySelector {
276    pub fn new(recorder: MimicRecorder) -> Self {
277        Self { recorder }
278    }
279}
280
281impl Debug for MimicReplayingEntitySelector {
282    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
283        f.debug_struct("MimicReplayingEntitySelector")
284            .field("recorder_id", &self.recorder.id)
285            .finish()
286    }
287}
288
289impl<S: PlanningSolution> EntitySelector<S> for MimicReplayingEntitySelector {
290    fn iter<'a, D: Director<S>>(
291        &'a self,
292        _score_director: &'a D,
293    ) -> impl Iterator<Item = EntityReference> + 'a {
294        ReplayingIterator {
295            recorder: &self.recorder,
296            returned: false,
297        }
298    }
299
300    fn size<D: Director<S>>(&self, _score_director: &D) -> usize {
301        // At most one entity is returned
302        if self.recorder.get_recorded_entity().is_some() {
303            1
304        } else {
305            0
306        }
307    }
308
309    fn is_never_ending(&self) -> bool {
310        false
311    }
312}
313
314// Iterator that replays a single recorded entity.
315struct ReplayingIterator<'a> {
316    recorder: &'a MimicRecorder,
317    returned: bool,
318}
319
320impl<'a> Iterator for ReplayingIterator<'a> {
321    type Item = EntityReference;
322
323    fn next(&mut self) -> Option<Self::Item> {
324        if self.returned {
325            return None;
326        }
327
328        // Check if something was recorded
329        match self.recorder.get_recorded_entity() {
330            Some(entity) => {
331                self.returned = true;
332                Some(entity)
333            }
334            None => {
335                // Check has_next to provide better error handling
336                match self.recorder.get_has_next() {
337                    Some(false) => None, // Recording selector exhausted
338                    Some(true) => panic!(
339                        "MimicReplayingEntitySelector: Recording selector's hasNext() was true \
340                         but next() was never called. Ensure the recording selector's iterator \
341                         is advanced before using the replaying selector."
342                    ),
343                    None => panic!(
344                        "MimicReplayingEntitySelector: No recording found. \
345                         The recording selector must be iterated before the replaying selector."
346                    ),
347                }
348            }
349        }
350    }
351}
352
353#[cfg(test)]
354mod tests {
355    use super::*;
356    use crate::heuristic::selector::entity::FromSolutionEntitySelector;
357    use crate::test_utils::create_simple_nqueens_director;
358
359    #[test]
360    fn test_mimic_recording_selector() {
361        let director = create_simple_nqueens_director(3);
362
363        // Verify column values match indices
364        let solution = director.working_solution();
365        for (i, queen) in solution.queens.iter().enumerate() {
366            assert_eq!(queen.column, i as i64);
367        }
368
369        let recorder = MimicRecorder::new("test");
370        let child = FromSolutionEntitySelector::new(0);
371        let recording = MimicRecordingEntitySelector::new(child, recorder);
372
373        let entities: Vec<_> = recording.iter(&director).collect();
374        assert_eq!(entities.len(), 3);
375        assert_eq!(entities[0], EntityReference::new(0, 0));
376        assert_eq!(entities[1], EntityReference::new(0, 1));
377        assert_eq!(entities[2], EntityReference::new(0, 2));
378    }
379
380    #[test]
381    fn test_mimic_replaying_selector() {
382        let director = create_simple_nqueens_director(3);
383
384        let recorder = MimicRecorder::new("test");
385        let child = FromSolutionEntitySelector::new(0);
386        let recording = MimicRecordingEntitySelector::new(child, recorder.clone());
387        let replaying = MimicReplayingEntitySelector::new(recorder);
388
389        // Iterate through recording selector
390        let mut recording_iter = recording.iter(&director);
391
392        // First entity recorded
393        let first = recording_iter.next().unwrap();
394        assert_eq!(first, EntityReference::new(0, 0));
395
396        // Replaying should yield the same entity
397        let replayed: Vec<_> = replaying.iter(&director).collect();
398        assert_eq!(replayed.len(), 1);
399        assert_eq!(replayed[0], EntityReference::new(0, 0));
400
401        // Move to second entity
402        let second = recording_iter.next().unwrap();
403        assert_eq!(second, EntityReference::new(0, 1));
404
405        // Replaying should now yield the second entity
406        let replayed: Vec<_> = replaying.iter(&director).collect();
407        assert_eq!(replayed.len(), 1);
408        assert_eq!(replayed[0], EntityReference::new(0, 1));
409    }
410
411    #[test]
412    fn test_mimic_synchronized_iteration() {
413        let director = create_simple_nqueens_director(3);
414
415        let recorder = MimicRecorder::new("test");
416        let child = FromSolutionEntitySelector::new(0);
417        let recording = MimicRecordingEntitySelector::new(child, recorder.clone());
418        let replaying = MimicReplayingEntitySelector::new(recorder);
419
420        // Simulate how this would be used in a move selector:
421        // For each recorded entity, get the replayed entity
422        for recorded in recording.iter(&director) {
423            let replayed: Vec<_> = replaying.iter(&director).collect();
424            assert_eq!(replayed.len(), 1);
425            assert_eq!(replayed[0], recorded);
426        }
427    }
428
429    #[test]
430    fn test_mimic_empty_selector() {
431        let director = create_simple_nqueens_director(0);
432
433        let recorder = MimicRecorder::new("test");
434        let child = FromSolutionEntitySelector::new(0);
435        let recording = MimicRecordingEntitySelector::new(child, recorder.clone());
436        let replaying = MimicReplayingEntitySelector::new(recorder);
437
438        // Recording selector is empty
439        let entities: Vec<_> = recording.iter(&director).collect();
440        assert_eq!(entities.len(), 0);
441
442        // Replaying should also be empty
443        let replayed: Vec<_> = replaying.iter(&director).collect();
444        assert_eq!(replayed.len(), 0);
445    }
446}
solverforge_solver/heuristic/selector/mimic.rs

solverforge_solver/heuristic/selector/
mimic.rs
