solverforge_solver/
solver.rs

1// Solver implementation.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5use std::sync::atomic::AtomicBool;
6use std::time::Duration;
7
8use solverforge_config::SolverConfig;
9use solverforge_core::domain::PlanningSolution;
10use solverforge_scoring::Director;
11
12use crate::phase::Phase;
13use crate::scope::ProgressCallback;
14use crate::scope::SolverScope;
15use crate::stats::SolverStats;
16use crate::termination::Termination;
17
18/* Result of a solve operation containing solution and telemetry.
19
20This is the canonical return type for `Solver::solve()`. It provides
21both the optimized solution and comprehensive statistics about the
22solving process.
23*/
24#[derive(Debug)]
25pub struct SolveResult<S: PlanningSolution> {
26    // The best solution found during solving.
27    pub solution: S,
28    // The canonical best score for the solve.
29    pub best_score: S::Score,
30    // Solver statistics including steps, moves evaluated, and acceptance rates.
31    pub stats: SolverStats,
32}
33
34impl<S: PlanningSolution> SolveResult<S> {
35    pub fn solution(&self) -> &S {
36        &self.solution
37    }
38
39    pub fn into_solution(self) -> S {
40        self.solution
41    }
42
43    pub fn best_score(&self) -> &S::Score {
44        &self.best_score
45    }
46
47    pub fn stats(&self) -> &SolverStats {
48        &self.stats
49    }
50
51    pub fn step_count(&self) -> u64 {
52        self.stats.step_count
53    }
54
55    pub fn moves_evaluated(&self) -> u64 {
56        self.stats.moves_evaluated
57    }
58
59    pub fn moves_accepted(&self) -> u64 {
60        self.stats.moves_accepted
61    }
62}
63
64/// The main solver that optimizes planning solutions.
65///
66/// Uses macro-generated tuple implementations for phases, preserving
67/// concrete types through the entire pipeline (zero-erasure architecture).
68///
69/// # Type Parameters
70/// * `'t` - Lifetime of the termination flag reference
71/// * `P` - Tuple of phases to execute
72/// * `T` - Termination condition (use `Option<ConcreteTermination>`)
73/// * `S` - Solution type
74/// * `D` - Score director type
75/// * `ProgressCb` - Progress callback type (default `()`)
76pub struct Solver<'t, P, T, S, D, ProgressCb = ()> {
77    phases: P,
78    termination: T,
79    terminate: Option<&'t AtomicBool>,
80    config: Option<SolverConfig>,
81    time_limit: Option<Duration>,
82    // Callback invoked when the solver should publish progress.
83    progress_callback: ProgressCb,
84    _phantom: PhantomData<fn(S, D)>,
85}
86
87impl<P: Debug, T: Debug, S, D, ProgressCb> Debug for Solver<'_, P, T, S, D, ProgressCb> {
88    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
89        f.debug_struct("Solver")
90            .field("phases", &self.phases)
91            .field("termination", &self.termination)
92            .finish()
93    }
94}
95
96impl<P, S, D> Solver<'static, P, NoTermination, S, D, ()>
97where
98    S: PlanningSolution,
99{
100    pub fn new(phases: P) -> Self {
101        Solver {
102            phases,
103            termination: NoTermination,
104            terminate: None,
105            config: None,
106            time_limit: None,
107            progress_callback: (),
108            _phantom: PhantomData,
109        }
110    }
111
112    pub fn with_termination<T>(self, termination: T) -> Solver<'static, P, Option<T>, S, D, ()> {
113        Solver {
114            phases: self.phases,
115            termination: Some(termination),
116            terminate: self.terminate,
117            config: self.config,
118            time_limit: self.time_limit,
119            progress_callback: self.progress_callback,
120            _phantom: PhantomData,
121        }
122    }
123}
124
125impl<'t, P, T, S, D, ProgressCb> Solver<'t, P, T, S, D, ProgressCb>
126where
127    S: PlanningSolution,
128{
129    /// Sets the external termination flag.
130    ///
131    /// The solver will check this flag periodically and terminate early if set.
132    pub fn with_terminate(self, terminate: &'t AtomicBool) -> Solver<'t, P, T, S, D, ProgressCb> {
133        Solver {
134            phases: self.phases,
135            termination: self.termination,
136            terminate: Some(terminate),
137            config: self.config,
138            time_limit: self.time_limit,
139            progress_callback: self.progress_callback,
140            _phantom: PhantomData,
141        }
142    }
143
144    pub fn with_time_limit(mut self, limit: Duration) -> Self {
145        self.time_limit = Some(limit);
146        self
147    }
148
149    pub fn with_config(mut self, config: SolverConfig) -> Self {
150        self.config = Some(config);
151        self
152    }
153
154    /// Sets a callback to be invoked for exact solver progress and best-solution updates.
155    ///
156    /// Transitions the callback type parameter to the concrete closure type.
157    pub fn with_progress_callback<F>(self, callback: F) -> Solver<'t, P, T, S, D, F> {
158        Solver {
159            phases: self.phases,
160            termination: self.termination,
161            terminate: self.terminate,
162            config: self.config,
163            time_limit: self.time_limit,
164            progress_callback: callback,
165            _phantom: PhantomData,
166        }
167    }
168
169    pub fn config(&self) -> Option<&SolverConfig> {
170        self.config.as_ref()
171    }
172}
173
174// Marker type indicating no termination.
175#[derive(Debug, Clone, Copy, Default)]
176pub struct NoTermination;
177
178/// Marker trait for termination types that can be used in Solver.
179pub trait MaybeTermination<
180    S: PlanningSolution,
181    D: Director<S>,
182    ProgressCb: ProgressCallback<S> = (),
183>: Send
184{
185    // Checks if the solver should terminate.
186    fn should_terminate(&self, solver_scope: &SolverScope<'_, S, D, ProgressCb>) -> bool;
187
188    /* Installs in-phase termination limits on the solver scope.
189
190    This allows `Termination` conditions (step count, move count, etc.) to fire
191    inside the phase step loop, not only between phases (T1 fix).
192
193    The default implementation is a no-op. Override for terminations that
194    express a concrete limit via a scope field.
195    */
196    fn install_inphase_limits(&self, _solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {}
197}
198
199impl<S, D, ProgressCb, T> MaybeTermination<S, D, ProgressCb> for Option<T>
200where
201    S: PlanningSolution,
202    D: Director<S>,
203    ProgressCb: ProgressCallback<S>,
204    T: Termination<S, D, ProgressCb>,
205{
206    fn should_terminate(&self, solver_scope: &SolverScope<'_, S, D, ProgressCb>) -> bool {
207        match self {
208            Some(t) => t.is_terminated(solver_scope),
209            None => false,
210        }
211    }
212
213    fn install_inphase_limits(&self, solver_scope: &mut SolverScope<'_, S, D, ProgressCb>) {
214        if let Some(t) = self {
215            t.install_inphase_limits(solver_scope);
216        }
217    }
218}
219
220impl<S, D, ProgressCb> MaybeTermination<S, D, ProgressCb> for NoTermination
221where
222    S: PlanningSolution,
223    D: Director<S>,
224    ProgressCb: ProgressCallback<S>,
225{
226    fn should_terminate(&self, _solver_scope: &SolverScope<'_, S, D, ProgressCb>) -> bool {
227        false
228    }
229
230    // install_inphase_limits: no-op (default)
231}
232
233impl<S, D, ProgressCb> Termination<S, D, ProgressCb> for NoTermination
234where
235    S: PlanningSolution,
236    D: Director<S>,
237    ProgressCb: ProgressCallback<S>,
238{
239    fn is_terminated(&self, _solver_scope: &SolverScope<'_, S, D, ProgressCb>) -> bool {
240        false
241    }
242}
243
244macro_rules! impl_solver {
245    ($($idx:tt: $P:ident),+) => {
246        impl<'t, S, D, T, ProgressCb, $($P),+> Solver<'t, ($($P,)+), T, S, D, ProgressCb>
247        where
248            S: PlanningSolution,
249            D: Director<S>,
250            T: MaybeTermination<S, D, ProgressCb>,
251            ProgressCb: ProgressCallback<S>,
252            $($P: Phase<S, D, ProgressCb>,)+
253        {
254            /// Solves using the provided score director.
255            ///
256            /// Returns a `SolveResult` containing the best solution found
257            /// and comprehensive solver statistics.
258            pub fn solve(self, score_director: D) -> SolveResult<S> {
259                let Solver {
260                    mut phases,
261                    termination,
262                    terminate,
263                    time_limit,
264                    progress_callback,
265                    ..
266                } = self;
267
268                let mut solver_scope = SolverScope::new_with_callback(
269                    score_director,
270                    progress_callback,
271                    terminate,
272                );
273                if let Some(limit) = time_limit {
274                    solver_scope.set_time_limit(limit);
275                }
276                solver_scope.start_solving();
277                let initial_score = solver_scope.calculate_score();
278                let initial_solution = solver_scope.score_director().clone_working_solution();
279                solver_scope.set_best_solution(initial_solution, initial_score);
280
281                // Install in-phase termination limits so phases can check them
282                // inside their step loops (T1: StepCountTermination, MoveCountTermination, etc.)
283                termination.install_inphase_limits(&mut solver_scope);
284
285                // Execute phases with termination checking
286                $(
287                    if !check_termination(&termination, &solver_scope) {
288                        tracing::debug!(
289                            "Starting phase {} ({})",
290                            $idx,
291                            phases.$idx.phase_type_name()
292                        );
293                        phases.$idx.solve(&mut solver_scope);
294                        tracing::debug!(
295                            "Finished phase {} ({}) with score {:?}",
296                            $idx,
297                            phases.$idx.phase_type_name(),
298                            solver_scope.best_score()
299                        );
300                    }
301                )+
302
303                // Extract solution and stats before consuming scope
304                let (solution, best_score, stats) = solver_scope.take_solution_and_stats();
305                SolveResult {
306                    solution,
307                    best_score,
308                    stats,
309                }
310            }
311        }
312    };
313}
314
315fn check_termination<S, D, ProgressCb, T>(
316    termination: &T,
317    solver_scope: &SolverScope<'_, S, D, ProgressCb>,
318) -> bool
319where
320    S: PlanningSolution,
321    D: Director<S>,
322    ProgressCb: ProgressCallback<S>,
323    T: MaybeTermination<S, D, ProgressCb>,
324{
325    if solver_scope.is_terminate_early() {
326        return true;
327    }
328    termination.should_terminate(solver_scope)
329}
330
331macro_rules! impl_solver_with_director {
332    ($($idx:tt: $P:ident),+) => {
333        impl<'t, S, T, ProgressCb, $($P),+> Solver<'t, ($($P,)+), T, S, (), ProgressCb>
334        where
335            S: PlanningSolution,
336            T: Send,
337            ProgressCb: Send + Sync,
338        {
339            /// Solves using a provided score director.
340            pub fn solve_with_director<D>(self, director: D) -> SolveResult<S>
341            where
342                D: Director<S>,
343                ProgressCb: ProgressCallback<S>,
344                T: MaybeTermination<S, D, ProgressCb>,
345                $($P: Phase<S, D, ProgressCb>,)+
346            {
347                let solver: Solver<'t, ($($P,)+), T, S, D, ProgressCb> = Solver {
348                    phases: self.phases,
349                    termination: self.termination,
350                    terminate: self.terminate,
351                    config: self.config,
352                    time_limit: self.time_limit,
353                    progress_callback: self.progress_callback,
354                    _phantom: PhantomData,
355                };
356                solver.solve(director)
357            }
358        }
359    };
360}
361
362impl_solver_with_director!(0: P0);
363impl_solver_with_director!(0: P0, 1: P1);
364impl_solver_with_director!(0: P0, 1: P1, 2: P2);
365impl_solver_with_director!(0: P0, 1: P1, 2: P2, 3: P3);
366impl_solver_with_director!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4);
367impl_solver_with_director!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5);
368impl_solver_with_director!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5, 6: P6);
369impl_solver_with_director!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5, 6: P6, 7: P7);
370
371impl_solver!(0: P0);
372impl_solver!(0: P0, 1: P1);
373impl_solver!(0: P0, 1: P1, 2: P2);
374impl_solver!(0: P0, 1: P1, 2: P2, 3: P3);
375impl_solver!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4);
376impl_solver!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5);
377impl_solver!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5, 6: P6);
378impl_solver!(0: P0, 1: P1, 2: P2, 3: P3, 4: P4, 5: P5, 6: P6, 7: P7);
solverforge_solver/solver.rs

solverforge_solver/
solver.rs
