solverforge_solver/heuristic/selector/
mimic.rs

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

solverforge_solver/heuristic/selector/
mimic.rs
