1const PROGRESS_INTERVAL: Duration = Duration::from_secs(1);
2
3#[derive(Debug, Clone, Copy)]
4pub(crate) struct ProgressTick {
5 pub elapsed: Duration,
6 pub step_delta: u64,
7 pub move_delta: u64,
8}
9
10#[derive(Debug, Clone, Copy)]
11struct ProgressPulse {
12 phase_index: usize,
13 phase_type: &'static str,
14 next_deadline: Instant,
15 last_reported_at: Instant,
16 last_step_count: u64,
17 last_move_count: u64,
18}
19
20impl ProgressPulse {
21 fn new(
22 now: Instant,
23 phase_index: usize,
24 phase_type: &'static str,
25 step_count: u64,
26 move_count: u64,
27 ) -> Self {
28 Self {
29 phase_index,
30 phase_type,
31 next_deadline: now + PROGRESS_INTERVAL,
32 last_reported_at: now,
33 last_step_count: step_count,
34 last_move_count: move_count,
35 }
36 }
37
38 fn take_due(
39 &mut self,
40 now: Instant,
41 phase_index: usize,
42 phase_type: &'static str,
43 step_count: u64,
44 move_count: u64,
45 ) -> Option<ProgressTick> {
46 if self.phase_index != phase_index || self.phase_type != phase_type {
47 *self = Self::new(now, phase_index, phase_type, step_count, move_count);
48 return None;
49 }
50 if now < self.next_deadline {
51 return None;
52 }
53 let tick = ProgressTick {
54 elapsed: now.duration_since(self.last_reported_at),
55 step_delta: step_count.saturating_sub(self.last_step_count),
56 move_delta: move_count.saturating_sub(self.last_move_count),
57 };
58 self.last_reported_at = now;
59 self.last_step_count = step_count;
60 self.last_move_count = move_count;
61 while self.next_deadline <= now {
62 self.next_deadline += PROGRESS_INTERVAL;
63 }
64 Some(tick)
65 }
66}
67
68pub struct SolverScope<'t, S: PlanningSolution, D: Director<S>, ProgressCb = ()> {
69 score_director: D,
70 best_solution: Option<S>,
71 current_score: Option<S::Score>,
72 best_score: Option<S::Score>,
73 rng: StdRng,
74 start_time: Option<Instant>,
75 paused_at: Option<Instant>,
76 total_step_count: u64,
77 terminate: Option<&'t AtomicBool>,
78 runtime: Option<SolverRuntime<S>>,
79 publication: Publication,
80 yielded_to_parent: bool,
81 environment_mode: EnvironmentMode,
82 stats: SolverStats,
83 time_limit: Option<Duration>,
84 time_deadline: Option<Instant>,
85 progress_callback: ProgressCb,
86 progress_pulse: Option<ProgressPulse>,
87 terminal_reason: Option<SolverTerminalReason>,
88 last_best_elapsed: Option<Duration>,
89 best_solution_revision: Option<u64>,
90 solution_revision: u64,
91 construction_frontier: ConstructionFrontier,
92 phase_budget: Option<&'t PhaseBudget>,
93 pub inphase_step_count_limit: Option<u64>,
94 pub inphase_move_count_limit: Option<u64>,
95 pub inphase_score_calc_count_limit: Option<u64>,
96 inphase_best_score_limit: Option<S::Score>,
97 phase_termination: Option<ScopedPhaseTermination<S>>,
98}
99
100#[derive(Debug, Clone, Copy, PartialEq, Eq)]
101enum Publication {
102 Enabled,
103 Disabled,
104}
105
106pub(crate) struct PhaseBudget {
107 step_count_limit: Option<u64>,
108 move_count_limit: Option<u64>,
109 score_calc_count_limit: Option<u64>,
110 step_count: AtomicU64,
111 moves_evaluated: AtomicU64,
112 score_calculations: AtomicU64,
113}
114
115impl PhaseBudget {
116 fn from_scope<S, D, ProgressCb>(scope: &SolverScope<'_, S, D, ProgressCb>) -> Self
117 where
118 S: PlanningSolution,
119 D: Director<S>,
120 ProgressCb: ProgressCallback<S>,
121 {
122 Self {
123 step_count_limit: remaining_limit(
124 scope.inphase_step_count_limit,
125 scope.total_step_count,
126 ),
127 move_count_limit: remaining_limit(
128 scope.inphase_move_count_limit,
129 scope.stats.moves_evaluated,
130 ),
131 score_calc_count_limit: remaining_limit(
132 scope.inphase_score_calc_count_limit,
133 scope.stats.score_calculations,
134 ),
135 step_count: AtomicU64::new(0),
136 moves_evaluated: AtomicU64::new(0),
137 score_calculations: AtomicU64::new(0),
138 }
139 }
140
141 fn has_limits(&self) -> bool {
142 self.step_count_limit.is_some()
143 || self.move_count_limit.is_some()
144 || self.score_calc_count_limit.is_some()
145 }
146
147 fn record_step(&self) {
148 self.step_count.fetch_add(1, Ordering::SeqCst);
149 }
150
151 fn record_evaluated_move(&self) {
152 self.moves_evaluated.fetch_add(1, Ordering::SeqCst);
153 }
154
155 fn record_score_calculation(&self) {
156 self.score_calculations.fetch_add(1, Ordering::SeqCst);
157 }
158
159 fn limit_reached(&self) -> bool {
160 limit_reached(self.step_count_limit, self.step_count.load(Ordering::SeqCst))
161 || limit_reached(
162 self.move_count_limit,
163 self.moves_evaluated.load(Ordering::SeqCst),
164 )
165 || limit_reached(
166 self.score_calc_count_limit,
167 self.score_calculations.load(Ordering::SeqCst),
168 )
169 }
170}
171
172#[derive(Clone, Copy)]
173struct ScopedPhaseTermination<S: PlanningSolution> {
174 start_step_count: u64,
175 start_elapsed: Duration,
176 time_limit: Option<Duration>,
177 step_count_limit: Option<u64>,
178 best_score_limit: Option<S::Score>,
179 unimproved_step_count_limit: Option<u64>,
180 unimproved_time_limit: Option<Duration>,
181 best_score: Option<S::Score>,
182 improvement_score: Option<S::Score>,
183 last_improvement_step_count: u64,
184 last_improvement_elapsed: Duration,
185}
186
187impl<S> ScopedPhaseTermination<S>
188where
189 S: PlanningSolution,
190{
191 fn from_config<D, ProgressCb>(
192 scope: &SolverScope<'_, S, D, ProgressCb>,
193 config: &TerminationConfig,
194 ) -> Option<Self>
195 where
196 D: Director<S>,
197 ProgressCb: ProgressCallback<S>,
198 S::Score: ParseableScore,
199 {
200 let best_score_limit = config
201 .best_score_limit
202 .as_deref()
203 .and_then(|score| S::Score::parse(score).ok());
204 let time_limit = config.time_limit();
205 let step_count_limit = config.step_count_limit;
206 let unimproved_step_count_limit = config.unimproved_step_count_limit;
207 let unimproved_time_limit = config.unimproved_time_limit();
208 if time_limit.is_none()
209 && step_count_limit.is_none()
210 && best_score_limit.is_none()
211 && unimproved_step_count_limit.is_none()
212 && unimproved_time_limit.is_none()
213 {
214 return None;
215 }
216 let elapsed = scope.elapsed().unwrap_or_default();
217 let best_score = match (scope.best_score, scope.current_score) {
218 (Some(best), Some(current)) => Some(best.max(current)),
219 (Some(best), None) | (None, Some(best)) => Some(best),
220 (None, None) => None,
221 };
222 Some(Self {
223 start_step_count: scope.total_step_count,
224 start_elapsed: elapsed,
225 time_limit,
226 step_count_limit,
227 best_score_limit,
228 unimproved_step_count_limit,
229 unimproved_time_limit,
230 best_score,
231 improvement_score: scope.current_score.or(scope.best_score),
232 last_improvement_step_count: scope.total_step_count,
233 last_improvement_elapsed: elapsed,
234 })
235 }
236
237 fn is_reached(
238 &self,
239 total_step_count: u64,
240 elapsed: Duration,
241 ) -> bool {
242 let phase_steps = total_step_count.saturating_sub(self.start_step_count);
243 let phase_elapsed = elapsed.saturating_sub(self.start_elapsed);
244 self.time_limit.is_some_and(|limit| phase_elapsed >= limit)
245 || self.step_count_limit.is_some_and(|limit| phase_steps >= limit)
246 || self
247 .best_score_limit
248 .is_some_and(|limit| self.best_score.is_some_and(|score| score >= limit))
249 || self.unimproved_step_count_limit.is_some_and(|limit| {
250 total_step_count.saturating_sub(self.last_improvement_step_count) >= limit
251 })
252 || self.unimproved_time_limit.is_some_and(|limit| {
253 elapsed.saturating_sub(self.last_improvement_elapsed) >= limit
254 })
255 }
256
257 fn record_improvement(&mut self, total_step_count: u64, elapsed: Duration) {
258 self.last_improvement_step_count = total_step_count;
259 self.last_improvement_elapsed = elapsed;
260 }
261
262 fn observe_score(
263 &mut self,
264 score: S::Score,
265 completed_step_count: u64,
266 elapsed: Duration,
267 ) {
268 if self.best_score.is_none_or(|best| score > best) {
269 self.best_score = Some(score);
270 }
271 if self.improvement_score.is_none_or(|best| score > best) {
272 self.improvement_score = Some(score);
273 self.record_improvement(completed_step_count, elapsed);
274 }
275 }
276
277 fn needs_score_observation(&self) -> bool {
278 self.best_score_limit.is_some()
279 || self.unimproved_step_count_limit.is_some()
280 || self.unimproved_time_limit.is_some()
281 }
282}
283
284fn remaining_limit(limit: Option<u64>, used: u64) -> Option<u64> {
285 limit.map(|limit| limit.saturating_sub(used))
286}
287
288fn limit_reached(limit: Option<u64>, used: u64) -> bool {
289 limit.is_some_and(|limit| used >= limit)
290}
291
292#[derive(Clone, Copy)]
293pub(crate) struct SolverScopeChildConfig<'t, S: PlanningSolution> {
294 terminate: Option<&'t AtomicBool>,
295 runtime: Option<SolverRuntime<S>>,
296 environment_mode: EnvironmentMode,
297 time_deadline: Option<Instant>,
298 phase_budget: Option<&'t PhaseBudget>,
299 inphase_step_count_limit: Option<u64>,
300 inphase_move_count_limit: Option<u64>,
301 inphase_score_calc_count_limit: Option<u64>,
302 inphase_best_score_limit: Option<S::Score>,
303}
304
305impl<'t, S: PlanningSolution> SolverScopeChildConfig<'t, S> {
306 pub(crate) fn build_scope<PD>(&self, score_director: PD, seed: u64) -> SolverScope<'t, S, PD>
307 where
308 PD: Director<S>,
309 {
310 let terminate = self
311 .terminate
312 .or_else(|| self.runtime.map(|runtime| runtime.cancel_flag()));
313 let mut scope = SolverScope::new(score_director)
314 .with_terminate(terminate)
315 .with_runtime(self.runtime)
316 .without_publication()
317 .with_environment_mode(self.environment_mode)
318 .with_seed(seed);
319 scope.time_deadline = self.time_deadline;
320 scope.phase_budget = self.phase_budget;
321 if self.phase_budget.is_none() {
322 scope.inphase_step_count_limit = self.inphase_step_count_limit;
323 scope.inphase_move_count_limit = self.inphase_move_count_limit;
324 scope.inphase_score_calc_count_limit = self.inphase_score_calc_count_limit;
325 }
326 scope.inphase_best_score_limit = self.inphase_best_score_limit;
327 scope
328 }
329}
330
331#[derive(Debug, Clone, Copy, PartialEq, Eq)]
332pub(crate) enum PendingControl {
333 Continue,
334 PauseRequested,
335 CancelRequested,
336 ConfigTerminationRequested,
337}
338
339impl<'t, S: PlanningSolution, D: Director<S>> SolverScope<'t, S, D, ()> {
340 pub fn new(score_director: D) -> Self {
341 let construction_frontier = ConstructionFrontier::new();
342 Self {
343 score_director,
344 best_solution: None,
345 current_score: None,
346 best_score: None,
347 rng: StdRng::from_rng(&mut rand::rng()),
348 start_time: None,
349 paused_at: None,
350 total_step_count: 0,
351 terminate: None,
352 runtime: None,
353 publication: Publication::Enabled,
354 yielded_to_parent: false,
355 environment_mode: EnvironmentMode::default(),
356 stats: SolverStats::default(),
357 time_limit: None,
358 time_deadline: None,
359 progress_callback: (),
360 progress_pulse: None,
361 terminal_reason: None,
362 last_best_elapsed: None,
363 best_solution_revision: None,
364 solution_revision: 1,
365 construction_frontier,
366 phase_budget: None,
367 inphase_step_count_limit: None,
368 inphase_move_count_limit: None,
369 inphase_score_calc_count_limit: None,
370 inphase_best_score_limit: None,
371 phase_termination: None,
372 }
373 }
374}
375
376impl<'t, S: PlanningSolution, D: Director<S>, ProgressCb: ProgressCallback<S>>
377 SolverScope<'t, S, D, ProgressCb>
378{
379 pub fn new_with_callback(
380 score_director: D,
381 callback: ProgressCb,
382 terminate: Option<&'t AtomicBool>,
383 runtime: Option<SolverRuntime<S>>,
384 ) -> Self {
385 let construction_frontier = ConstructionFrontier::new();
386 Self {
387 score_director,
388 best_solution: None,
389 current_score: None,
390 best_score: None,
391 rng: StdRng::from_rng(&mut rand::rng()),
392 start_time: None,
393 paused_at: None,
394 total_step_count: 0,
395 terminate,
396 runtime,
397 publication: Publication::Enabled,
398 yielded_to_parent: false,
399 environment_mode: EnvironmentMode::default(),
400 stats: SolverStats::default(),
401 time_limit: None,
402 time_deadline: None,
403 progress_callback: callback,
404 progress_pulse: None,
405 terminal_reason: None,
406 last_best_elapsed: None,
407 best_solution_revision: None,
408 solution_revision: 1,
409 construction_frontier,
410 phase_budget: None,
411 inphase_step_count_limit: None,
412 inphase_move_count_limit: None,
413 inphase_score_calc_count_limit: None,
414 inphase_best_score_limit: None,
415 phase_termination: None,
416 }
417 }
418
419 pub fn with_terminate(mut self, terminate: Option<&'t AtomicBool>) -> Self {
420 self.terminate = terminate;
421 self
422 }
423
424 pub fn with_runtime(mut self, runtime: Option<SolverRuntime<S>>) -> Self {
425 self.runtime = runtime;
426 self
427 }
428
429 pub(crate) fn without_publication(mut self) -> Self {
430 self.publication = Publication::Disabled;
431 self
432 }
433
434 pub(crate) fn yielded_to_parent(&self) -> bool {
435 self.yielded_to_parent
436 }
437
438 pub fn with_environment_mode(mut self, environment_mode: EnvironmentMode) -> Self {
439 self.environment_mode = environment_mode;
440 self
441 }
442
443 pub fn with_seed(mut self, seed: u64) -> Self {
444 self.rng = StdRng::seed_from_u64(seed);
445 self
446 }
447
448 pub(crate) fn child_phase_budget(&self) -> PhaseBudget {
449 PhaseBudget::from_scope(self)
450 }
451
452 pub(crate) fn child_config<'a>(
453 &'a self,
454 phase_budget: Option<&'a PhaseBudget>,
455 ) -> SolverScopeChildConfig<'a, S> {
456 let phase_budget = self
457 .phase_budget
458 .or_else(|| phase_budget.filter(|budget| budget.has_limits()));
459 SolverScopeChildConfig {
460 terminate: self.terminate,
461 runtime: self.runtime,
462 environment_mode: self.environment_mode,
463 time_deadline: self.child_time_deadline(),
464 phase_budget,
465 inphase_step_count_limit: self.inphase_step_count_limit,
466 inphase_move_count_limit: self.inphase_move_count_limit,
467 inphase_score_calc_count_limit: self.inphase_score_calc_count_limit,
468 inphase_best_score_limit: self.inphase_best_score_limit,
469 }
470 }
471
472 pub(crate) fn with_phase_termination<T>(
481 &mut self,
482 config: Option<&TerminationConfig>,
483 work: impl FnOnce(&mut Self) -> T,
484 ) -> T
485 where
486 S::Score: ParseableScore,
487 {
488 let previous = self.phase_termination.take();
489 self.phase_termination =
490 config.and_then(|config| ScopedPhaseTermination::from_config(self, config));
491 let result = work(self);
492 self.phase_termination = previous;
493 result
494 }
495
496 fn phase_termination_reached(&self) -> bool {
497 self.phase_termination.as_ref().is_some_and(|termination| {
498 termination.is_reached(self.total_step_count, self.elapsed().unwrap_or_default())
499 })
500 }
501
502 pub(crate) fn phase_termination_requires_score_observation(&self) -> bool {
503 self.phase_termination
504 .as_ref()
505 .is_some_and(ScopedPhaseTermination::needs_score_observation)
506 }
507
508 fn observe_phase_score(&mut self, score: S::Score, completed_step_count: u64) {
509 let elapsed = self.elapsed().unwrap_or_default();
510 if let Some(termination) = &mut self.phase_termination {
511 termination.observe_score(score, completed_step_count, elapsed);
512 }
513 }
514
515 pub(crate) fn observe_phase_step_score(&mut self, score: S::Score) {
516 self.observe_phase_score(score, self.total_step_count.saturating_add(1));
517 }
518
519 fn child_time_deadline(&self) -> Option<Instant> {
520 self.time_deadline.or_else(|| {
521 self.time_limit.map(|limit| {
522 self.start_time
523 .map(|start| start + limit)
524 .unwrap_or_else(|| Instant::now() + limit)
525 })
526 })
527 }
528
529 pub fn with_progress_callback<F: ProgressCallback<S>>(
530 self,
531 callback: F,
532 ) -> SolverScope<'t, S, D, F> {
533 SolverScope {
534 score_director: self.score_director,
535 best_solution: self.best_solution,
536 current_score: self.current_score,
537 best_score: self.best_score,
538 rng: self.rng,
539 start_time: self.start_time,
540 paused_at: self.paused_at,
541 total_step_count: self.total_step_count,
542 terminate: self.terminate,
543 runtime: self.runtime,
544 publication: self.publication,
545 yielded_to_parent: self.yielded_to_parent,
546 environment_mode: self.environment_mode,
547 stats: self.stats,
548 time_limit: self.time_limit,
549 time_deadline: self.time_deadline,
550 progress_callback: callback,
551 progress_pulse: self.progress_pulse,
552 terminal_reason: self.terminal_reason,
553 last_best_elapsed: self.last_best_elapsed,
554 best_solution_revision: self.best_solution_revision,
555 solution_revision: self.solution_revision,
556 construction_frontier: self.construction_frontier,
557 phase_budget: self.phase_budget,
558 inphase_step_count_limit: self.inphase_step_count_limit,
559 inphase_move_count_limit: self.inphase_move_count_limit,
560 inphase_score_calc_count_limit: self.inphase_score_calc_count_limit,
561 inphase_best_score_limit: self.inphase_best_score_limit,
562 phase_termination: self.phase_termination,
563 }
564 }
565
566 pub fn start_solving(&mut self) {
567 self.start_time = Some(Instant::now());
568 self.paused_at = None;
569 self.total_step_count = 0;
570 self.terminal_reason = None;
571 self.last_best_elapsed = None;
572 self.yielded_to_parent = false;
573 self.best_solution_revision = None;
574 self.solution_revision = 1;
575 self.progress_pulse = None;
576 self.construction_frontier.reset();
577 self.stats.start();
578 }
579
580 pub fn elapsed(&self) -> Option<Duration> {
581 match (self.start_time, self.paused_at) {
582 (Some(start), Some(paused_at)) => Some(paused_at.duration_since(start)),
583 (Some(start), None) => Some(start.elapsed()),
584 _ => None,
585 }
586 }
587
588 pub fn time_since_last_improvement(&self) -> Option<Duration> {
589 let elapsed = self.elapsed()?;
590 let last_best_elapsed = self.last_best_elapsed?;
591 Some(elapsed.saturating_sub(last_best_elapsed))
592 }
593
594 pub fn score_director(&self) -> &D {
595 &self.score_director
596 }
597
598 pub(crate) fn score_director_mut(&mut self) -> &mut D {
599 &mut self.score_director
600 }
601
602 pub fn working_solution(&self) -> &S {
603 self.score_director.working_solution()
604 }
605
606 pub fn mutate<T, F>(&mut self, mutate: F) -> T
607 where
608 F: FnOnce(&mut D) -> T,
609 {
610 self.committed_mutation(mutate)
611 }
612
613 pub fn calculate_score(&mut self) -> S::Score {
614 self.record_score_calculation();
615 let score = self.score_director.calculate_score();
616 self.current_score = Some(score);
617 self.assert_score_consistent("calculate_score", score);
618 score
619 }
620
621 pub(crate) fn assert_score_consistent(&self, context: &str, score: S::Score) {
622 if self.environment_mode != EnvironmentMode::FullAssert {
623 return;
624 }
625 let Some(fresh_score) = self.score_director.fresh_score() else {
626 return;
627 };
628 assert_eq!(
629 score, fresh_score,
630 "score director drift after {context}: cached score {score:?} != fresh score {fresh_score:?}"
631 );
632 }
633
634 pub fn initialize_working_solution_as_best(&mut self) -> S::Score {
635 if self.start_time.is_none() {
636 self.start_solving();
637 }
638 let score = self.calculate_score();
639 let solution = self.score_director.clone_working_solution();
640 self.set_best_solution(solution, score);
641 score
642 }
643
644 pub fn replace_working_solution_and_reinitialize(&mut self, solution: S) -> S::Score {
645 *self.score_director.working_solution_mut() = solution;
646 self.score_director.reset();
647 self.current_score = None;
648 self.best_solution_revision = None;
649 self.solution_revision = 1;
650 self.construction_frontier.reset();
651 self.calculate_score()
652 }
653
654 pub fn best_solution(&self) -> Option<&S> {
655 self.best_solution.as_ref()
656 }
657
658 pub fn best_score(&self) -> Option<&S::Score> {
659 self.best_score.as_ref()
660 }
661
662 pub fn current_score(&self) -> Option<&S::Score> {
663 self.current_score.as_ref()
664 }
665
666 pub(crate) fn is_scalar_slot_completed(&self, slot_id: ConstructionSlotId) -> bool {
667 self.construction_frontier
668 .is_scalar_completed(slot_id, self.solution_revision)
669 }
670
671 pub(crate) fn mark_scalar_slot_completed(&mut self, slot_id: ConstructionSlotId) {
672 self.construction_frontier
673 .mark_scalar_completed(slot_id, self.solution_revision);
674 }
675
676 pub(crate) fn is_group_slot_completed(&self, slot_id: &ConstructionGroupSlotId) -> bool {
677 self.construction_frontier
678 .is_group_completed(slot_id, self.solution_revision)
679 }
680
681 pub(crate) fn mark_group_slot_completed(&mut self, slot_id: ConstructionGroupSlotId) {
682 self.construction_frontier
683 .mark_group_completed(slot_id, self.solution_revision);
684 }
685
686 pub(crate) fn is_list_element_completed(&self, element_id: ConstructionListElementId) -> bool {
687 self.construction_frontier
688 .is_list_completed(element_id, self.solution_revision)
689 }
690
691 pub(crate) fn mark_list_element_completed(&mut self, element_id: ConstructionListElementId) {
692 self.construction_frontier
693 .mark_list_completed(element_id, self.solution_revision);
694 }
695
696 #[cfg(test)]
697 pub(crate) fn solution_revision(&self) -> u64 {
698 self.solution_revision
699 }
700
701 pub(crate) fn apply_committed_move<M>(&mut self, mov: &M)
702 where
703 M: Move<S>,
704 {
705 self.committed_mutation(|score_director| mov.do_move(score_director));
706 }
707
708 pub(crate) fn apply_committed_change<F>(&mut self, change: F)
709 where
710 F: FnOnce(&mut D),
711 {
712 self.committed_mutation(change);
713 }
714
715}