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