solverforge_solver/phase/construction/

phase.rs

// Construction heuristic phase implementation.

use std::any::Any;
use std::fmt::Debug;
use std::marker::PhantomData;

use solverforge_core::domain::PlanningSolution;
use solverforge_core::score::Score;
use solverforge_scoring::{Director, RecordingDirector};
use tracing::info;

use crate::heuristic::r#move::Move;
use crate::phase::construction::{
    BestFitForager, ConstructionForager, EntityPlacer, FirstFeasibleForager, FirstFitForager,
};
use crate::phase::control::{
    settle_construction_interrupt, should_interrupt_evaluation, StepInterrupt,
};
use crate::phase::Phase;
use crate::scope::ProgressCallback;
use crate::scope::{PhaseScope, SolverScope, StepScope};

/// Construction heuristic phase that builds an initial solution.
///
/// This phase iterates over uninitialized entities and assigns values
/// to their planning variables using a greedy approach.
///
/// # Type Parameters
/// * `S` - The planning solution type
/// * `M` - The move type
/// * `P` - The entity placer type
/// * `Fo` - The forager type
pub struct ConstructionHeuristicPhase<S, M, P, Fo>
where
    S: PlanningSolution,
    M: Move<S>,
    P: EntityPlacer<S, M>,
    Fo: ConstructionForager<S, M>,
{
    placer: P,
    forager: Fo,
    _phantom: PhantomData<fn() -> (S, M)>,
}

impl<S, M, P, Fo> ConstructionHeuristicPhase<S, M, P, Fo>
where
    S: PlanningSolution,
    M: Move<S>,
    P: EntityPlacer<S, M>,
    Fo: ConstructionForager<S, M>,
{
    pub fn new(placer: P, forager: Fo) -> Self {
        Self {
            placer,
            forager,
            _phantom: PhantomData,
        }
    }
}

impl<S, M, P, Fo> Debug for ConstructionHeuristicPhase<S, M, P, Fo>
where
    S: PlanningSolution,
    M: Move<S>,
    P: EntityPlacer<S, M> + Debug,
    Fo: ConstructionForager<S, M> + Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("ConstructionHeuristicPhase")
            .field("placer", &self.placer)
            .field("forager", &self.forager)
            .finish()
    }
}

impl<S, D, BestCb, M, P, Fo> Phase<S, D, BestCb> for ConstructionHeuristicPhase<S, M, P, Fo>
where
    S: PlanningSolution,
    D: Director<S>,
    BestCb: ProgressCallback<S>,
    M: Move<S> + 'static,
    P: EntityPlacer<S, M>,
    Fo: ConstructionForager<S, M> + 'static,
{
    fn solve(&mut self, solver_scope: &mut SolverScope<S, D, BestCb>) {
        let mut phase_scope = PhaseScope::new(solver_scope, 0);
        let phase_index = phase_scope.phase_index();

        info!(
            event = "phase_start",
            phase = "Construction Heuristic",
            phase_index = phase_index,
        );

        // Get all placements (entities that need values assigned)
        let mut placements = self
            .placer
            .get_placements(phase_scope.score_director())
            .into_iter();
        let mut pending_placement = None;

        loop {
            // Construction must complete — only stop for external flag or time limit,
            // never for step/move count limits (those are for local search).
            if phase_scope
                .solver_scope_mut()
                .should_terminate_construction()
            {
                break;
            }

            let mut placement = match pending_placement.take().or_else(|| placements.next()) {
                Some(placement) => placement,
                None => break,
            };

            // Record move evaluations at call-site (Option C: maintains trait purity)
            // BestFitForager evaluates ALL moves in the placement
            let moves_in_placement = placement.moves.len() as u64;

            let mut step_scope = StepScope::new(&mut phase_scope);

            // Use forager to pick the best move index for this placement
            let selected_idx = match select_move_index(&self.forager, &placement, &mut step_scope) {
                ConstructionSelection::Selected(selected_idx) => selected_idx,
                ConstructionSelection::Interrupted => {
                    match settle_construction_interrupt(&mut step_scope) {
                        StepInterrupt::Restart => {
                            pending_placement = Some(placement);
                            continue;
                        }
                        StepInterrupt::TerminatePhase => break,
                    }
                }
            };

            // Record all moves as evaluated, with one accepted if selection succeeded
            for i in 0..moves_in_placement {
                let accepted = selected_idx == Some(i as usize);
                step_scope
                    .phase_scope_mut()
                    .solver_scope_mut()
                    .stats_mut()
                    .record_move(accepted);
            }

            if let Some(idx) = selected_idx {
                // Take ownership of the move
                let m = placement.take_move(idx);

                // Execute the move
                m.do_move(step_scope.score_director_mut());

                // Calculate and record the step score
                let step_score = step_scope.calculate_score();
                step_scope.set_step_score(step_score);
            }

            step_scope.complete();
        }

        // Update best solution at end of phase
        phase_scope.update_best_solution();

        let best_score = phase_scope
            .solver_scope()
            .best_score()
            .map(|s| format!("{}", s))
            .unwrap_or_else(|| "none".to_string());

        let duration = phase_scope.elapsed();
        let steps = phase_scope.step_count();
        let speed = if duration.as_secs_f64() > 0.0 {
            (steps as f64 / duration.as_secs_f64()) as u64
        } else {
            0
        };
        let stats = phase_scope.solver_scope().stats();

        info!(
            event = "phase_end",
            phase = "Construction Heuristic",
            phase_index = phase_index,
            duration_ms = duration.as_millis() as u64,
            steps = steps,
            moves_evaluated = stats.moves_evaluated,
            moves_accepted = stats.moves_accepted,
            score_calculations = stats.score_calculations,
            speed = speed,
            score = best_score,
        );
    }

    fn phase_type_name(&self) -> &'static str {
        "ConstructionHeuristic"
    }
}

enum ConstructionSelection {
    Selected(Option<usize>),
    Interrupted,
}

fn select_move_index<S, D, BestCb, M, Fo>(
    forager: &Fo,
    placement: &crate::phase::construction::Placement<S, M>,
    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
) -> ConstructionSelection
where
    S: PlanningSolution,
    S::Score: Score,
    D: Director<S>,
    BestCb: ProgressCallback<S>,
    M: Move<S> + 'static,
    Fo: ConstructionForager<S, M> + 'static,
{
    let erased = forager as &dyn Any;

    if erased.is::<FirstFitForager<S, M>>() {
        return select_first_fit_index(placement, step_scope);
    }
    if erased.is::<BestFitForager<S, M>>() {
        return select_best_fit_index(placement, step_scope);
    }
    if erased.is::<FirstFeasibleForager<S, M>>() {
        return select_first_feasible_index(placement, step_scope);
    }

    ConstructionSelection::Selected(
        forager.pick_move_index(placement, step_scope.score_director_mut()),
    )
}

fn select_first_fit_index<S, D, BestCb, M>(
    placement: &crate::phase::construction::Placement<S, M>,
    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
) -> ConstructionSelection
where
    S: PlanningSolution,
    D: Director<S>,
    BestCb: ProgressCallback<S>,
    M: Move<S> + 'static,
{
    for (idx, m) in placement.moves.iter().enumerate() {
        if should_interrupt_evaluation(step_scope, idx) {
            return ConstructionSelection::Interrupted;
        }
        if m.is_doable(step_scope.score_director()) {
            return ConstructionSelection::Selected(Some(idx));
        }
    }
    ConstructionSelection::Selected(None)
}

fn select_best_fit_index<S, D, BestCb, M>(
    placement: &crate::phase::construction::Placement<S, M>,
    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
) -> ConstructionSelection
where
    S: PlanningSolution,
    S::Score: Score,
    D: Director<S>,
    BestCb: ProgressCallback<S>,
    M: Move<S> + 'static,
{
    let mut best_idx: Option<usize> = None;
    let mut best_score: Option<S::Score> = None;

    for (idx, m) in placement.moves.iter().enumerate() {
        if should_interrupt_evaluation(step_scope, idx) {
            return ConstructionSelection::Interrupted;
        }
        if !m.is_doable(step_scope.score_director()) {
            continue;
        }

        let score = {
            let mut recording = RecordingDirector::new(step_scope.score_director_mut());
            m.do_move(&mut recording);
            let score = recording.calculate_score();
            recording.undo_changes();
            score
        };

        let is_better = match &best_score {
            None => true,
            Some(best) => score > *best,
        };
        if is_better {
            best_idx = Some(idx);
            best_score = Some(score);
        }
    }

    ConstructionSelection::Selected(best_idx)
}

fn select_first_feasible_index<S, D, BestCb, M>(
    placement: &crate::phase::construction::Placement<S, M>,
    step_scope: &mut StepScope<'_, '_, '_, S, D, BestCb>,
) -> ConstructionSelection
where
    S: PlanningSolution,
    S::Score: Score,
    D: Director<S>,
    BestCb: ProgressCallback<S>,
    M: Move<S> + 'static,
{
    let mut fallback_idx: Option<usize> = None;
    let mut fallback_score: Option<S::Score> = None;

    for (idx, m) in placement.moves.iter().enumerate() {
        if should_interrupt_evaluation(step_scope, idx) {
            return ConstructionSelection::Interrupted;
        }
        if !m.is_doable(step_scope.score_director()) {
            continue;
        }

        let score = {
            let mut recording = RecordingDirector::new(step_scope.score_director_mut());
            m.do_move(&mut recording);
            let score = recording.calculate_score();
            recording.undo_changes();
            score
        };

        if score.is_feasible() {
            return ConstructionSelection::Selected(Some(idx));
        }

        let is_better = match &fallback_score {
            None => true,
            Some(best) => score > *best,
        };
        if is_better {
            fallback_idx = Some(idx);
            fallback_score = Some(score);
        }
    }

    ConstructionSelection::Selected(fallback_idx)
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::any::TypeId;
    use std::sync::atomic::{AtomicUsize, Ordering};
    use std::sync::{Arc, Condvar, Mutex};

    use solverforge_core::domain::SolutionDescriptor;
    use solverforge_core::score::SoftScore;
    use solverforge_scoring::Director;

    use crate::heuristic::selector::EntityReference;
    use crate::heuristic::selector::{FromSolutionEntitySelector, StaticValueSelector};
    use crate::manager::{
        Solvable, SolverEvent, SolverLifecycleState, SolverManager, SolverRuntime,
        SolverTerminalReason,
    };
    use crate::phase::construction::{
        BestFitForager, FirstFitForager, Placement, QueuedEntityPlacer,
    };
    use crate::test_utils::{
        create_simple_nqueens_director, get_queen_row, set_queen_row, NQueensSolution,
    };

    fn create_placer(
        values: Vec<i64>,
    ) -> QueuedEntityPlacer<
        NQueensSolution,
        i64,
        FromSolutionEntitySelector,
        StaticValueSelector<NQueensSolution, i64>,
    > {
        let es = FromSolutionEntitySelector::new(0);
        let vs = StaticValueSelector::new(values);
        QueuedEntityPlacer::new(es, vs, get_queen_row, set_queen_row, 0, "row")
    }

    #[derive(Clone, Debug)]
    struct BlockingPoint {
        state: Arc<(Mutex<BlockingPointState>, Condvar)>,
    }

    #[derive(Debug)]
    struct BlockingPointState {
        blocked: bool,
        released: bool,
    }

    impl BlockingPoint {
        fn new() -> Self {
            Self {
                state: Arc::new((
                    Mutex::new(BlockingPointState {
                        blocked: false,
                        released: false,
                    }),
                    Condvar::new(),
                )),
            }
        }

        fn block(&self) {
            let (lock, condvar) = &*self.state;
            let mut state = lock.lock().unwrap();
            state.blocked = true;
            condvar.notify_all();
            while !state.released {
                state = condvar.wait(state).unwrap();
            }
        }

        fn wait_until_blocked(&self) {
            let (lock, condvar) = &*self.state;
            let mut state = lock.lock().unwrap();
            while !state.blocked {
                state = condvar.wait(state).unwrap();
            }
        }

        fn release(&self) {
            let (lock, condvar) = &*self.state;
            let mut state = lock.lock().unwrap();
            state.released = true;
            condvar.notify_all();
        }
    }

    #[derive(Clone, Debug)]
    struct BlockingEvaluationGate {
        block_at: usize,
        seen: Arc<AtomicUsize>,
        blocker: BlockingPoint,
    }

    impl BlockingEvaluationGate {
        fn new(block_at: usize) -> Self {
            Self {
                block_at,
                seen: Arc::new(AtomicUsize::new(0)),
                blocker: BlockingPoint::new(),
            }
        }

        fn on_evaluation(&self) {
            let seen = self.seen.fetch_add(1, Ordering::SeqCst) + 1;
            if seen == self.block_at {
                self.blocker.block();
            }
        }

        fn wait_until_blocked(&self) {
            self.blocker.wait_until_blocked();
        }

        fn release(&self) {
            self.blocker.release();
        }
    }

    #[derive(Clone, Debug)]
    struct ConstructionPauseEntity {
        value: Option<i64>,
    }

    #[derive(Clone, Debug)]
    struct ConstructionPauseSolution {
        entities: Vec<ConstructionPauseEntity>,
        score: Option<SoftScore>,
        eval_gate: Option<BlockingEvaluationGate>,
    }

    impl ConstructionPauseSolution {
        fn new(eval_gate: Option<BlockingEvaluationGate>) -> Self {
            Self {
                entities: vec![ConstructionPauseEntity { value: None }],
                score: None,
                eval_gate,
            }
        }
    }

    impl PlanningSolution for ConstructionPauseSolution {
        type Score = SoftScore;

        fn score(&self) -> Option<Self::Score> {
            self.score
        }

        fn set_score(&mut self, score: Option<Self::Score>) {
            self.score = score;
        }
    }

    #[derive(Clone, Debug)]
    struct ConstructionPauseDirector {
        working_solution: ConstructionPauseSolution,
        descriptor: SolutionDescriptor,
    }

    impl ConstructionPauseDirector {
        fn new(solution: ConstructionPauseSolution) -> Self {
            Self {
                working_solution: solution,
                descriptor: SolutionDescriptor::new(
                    "ConstructionPauseSolution",
                    TypeId::of::<ConstructionPauseSolution>(),
                ),
            }
        }
    }

    impl Director<ConstructionPauseSolution> for ConstructionPauseDirector {
        fn working_solution(&self) -> &ConstructionPauseSolution {
            &self.working_solution
        }

        fn working_solution_mut(&mut self) -> &mut ConstructionPauseSolution {
            &mut self.working_solution
        }

        fn calculate_score(&mut self) -> SoftScore {
            let score = SoftScore::of(
                self.working_solution
                    .entities
                    .iter()
                    .filter_map(|entity| entity.value)
                    .sum(),
            );
            self.working_solution.set_score(Some(score));
            score
        }

        fn solution_descriptor(&self) -> &SolutionDescriptor {
            &self.descriptor
        }

        fn clone_working_solution(&self) -> ConstructionPauseSolution {
            self.working_solution.clone()
        }

        fn before_variable_changed(&mut self, _descriptor_index: usize, _entity_index: usize) {}

        fn after_variable_changed(&mut self, _descriptor_index: usize, _entity_index: usize) {}

        fn entity_count(&self, descriptor_index: usize) -> Option<usize> {
            (descriptor_index == 0).then_some(self.working_solution.entities.len())
        }

        fn total_entity_count(&self) -> Option<usize> {
            Some(self.working_solution.entities.len())
        }
    }

    #[derive(Clone, Debug)]
    struct ConstructionPauseMove {
        entity_index: usize,
        entity_indices: [usize; 1],
        value: i64,
        doable: bool,
        eval_gate: Option<BlockingEvaluationGate>,
    }

    impl ConstructionPauseMove {
        fn new(
            entity_index: usize,
            value: i64,
            doable: bool,
            eval_gate: Option<BlockingEvaluationGate>,
        ) -> Self {
            Self {
                entity_index,
                entity_indices: [entity_index],
                value,
                doable,
                eval_gate,
            }
        }
    }

    impl Move<ConstructionPauseSolution> for ConstructionPauseMove {
        fn is_doable<D: Director<ConstructionPauseSolution>>(&self, _score_director: &D) -> bool {
            if let Some(gate) = &self.eval_gate {
                gate.on_evaluation();
            }
            self.doable
        }

        fn do_move<D: Director<ConstructionPauseSolution>>(&self, score_director: &mut D) {
            score_director.working_solution_mut().entities[self.entity_index].value =
                Some(self.value);
        }

        fn descriptor_index(&self) -> usize {
            0
        }

        fn entity_indices(&self) -> &[usize] {
            &self.entity_indices
        }

        fn variable_name(&self) -> &str {
            "value"
        }
    }

    #[derive(Clone, Debug)]
    struct ConstructionPausePlacer {
        eval_gate: Option<BlockingEvaluationGate>,
    }

    impl ConstructionPausePlacer {
        fn new(eval_gate: Option<BlockingEvaluationGate>) -> Self {
            Self { eval_gate }
        }
    }

    impl EntityPlacer<ConstructionPauseSolution, ConstructionPauseMove> for ConstructionPausePlacer {
        fn get_placements<D: Director<ConstructionPauseSolution>>(
            &self,
            score_director: &D,
        ) -> Vec<Placement<ConstructionPauseSolution, ConstructionPauseMove>> {
            score_director
                .working_solution()
                .entities
                .iter()
                .enumerate()
                .filter_map(|(entity_index, entity)| {
                    if entity.value.is_some() {
                        return None;
                    }

                    let moves = (0..65)
                        .map(|value| {
                            ConstructionPauseMove::new(
                                entity_index,
                                value as i64,
                                value == 64,
                                (value == 0).then(|| self.eval_gate.clone()).flatten(),
                            )
                        })
                        .collect();

                    Some(Placement::new(EntityReference::new(0, entity_index), moves))
                })
                .collect()
        }
    }

    impl Solvable for ConstructionPauseSolution {
        fn solve(self, runtime: SolverRuntime<Self>) {
            let eval_gate = self.eval_gate.clone();
            let mut solver_scope = SolverScope::new_with_callback(
                ConstructionPauseDirector::new(self),
                (),
                None,
                Some(runtime),
            );

            solver_scope.start_solving();

            let mut phase = ConstructionHeuristicPhase::new(
                ConstructionPausePlacer::new(eval_gate),
                FirstFitForager::new(),
            );
            phase.solve(&mut solver_scope);

            let mut current_score = solver_scope.current_score().copied();
            let best_score = if let Some(best_score) = solver_scope.best_score().copied() {
                best_score
            } else {
                let score = solver_scope.calculate_score();
                current_score.get_or_insert(score);
                score
            };

            let telemetry = solver_scope.stats().snapshot();
            let solution = solver_scope.score_director().clone_working_solution();

            if runtime.is_cancel_requested() {
                runtime.emit_cancelled(current_score, Some(best_score), telemetry);
            } else {
                runtime.emit_completed(
                    solution,
                    current_score,
                    best_score,
                    telemetry,
                    SolverTerminalReason::Completed,
                );
            }
        }
    }

    #[test]
    fn test_construction_first_fit() {
        let director = create_simple_nqueens_director(4);
        let mut solver_scope = SolverScope::new(director);
        solver_scope.start_solving();

        let values: Vec<i64> = (0..4).collect();
        let placer = create_placer(values);
        let forager = FirstFitForager::new();
        let mut phase = ConstructionHeuristicPhase::new(placer, forager);

        phase.solve(&mut solver_scope);

        let solution = solver_scope.working_solution();
        assert_eq!(solution.queens.len(), 4);
        for queen in &solution.queens {
            assert!(queen.row.is_some(), "Queen should have a row assigned");
        }

        assert!(solver_scope.best_solution().is_some());
        // Verify stats were recorded
        assert!(solver_scope.stats().moves_evaluated > 0);
    }

    #[test]
    fn test_construction_best_fit() {
        let director = create_simple_nqueens_director(4);
        let mut solver_scope = SolverScope::new(director);
        solver_scope.start_solving();

        let values: Vec<i64> = (0..4).collect();
        let placer = create_placer(values);
        let forager = BestFitForager::new();
        let mut phase = ConstructionHeuristicPhase::new(placer, forager);

        phase.solve(&mut solver_scope);

        let solution = solver_scope.working_solution();
        for queen in &solution.queens {
            assert!(queen.row.is_some(), "Queen should have a row assigned");
        }

        assert!(solver_scope.best_solution().is_some());
        assert!(solver_scope.best_score().is_some());

        // BestFitForager evaluates all moves: 4 entities * 4 values = 16 moves
        assert_eq!(solver_scope.stats().moves_evaluated, 16);
    }

    #[test]
    fn test_construction_empty_solution() {
        let director = create_simple_nqueens_director(0);
        let mut solver_scope = SolverScope::new(director);
        solver_scope.start_solving();

        let values: Vec<i64> = vec![];
        let placer = create_placer(values);
        let forager = FirstFitForager::new();
        let mut phase = ConstructionHeuristicPhase::new(placer, forager);

        phase.solve(&mut solver_scope);

        // No moves should be evaluated for empty solution
        assert_eq!(solver_scope.stats().moves_evaluated, 0);
    }

    #[test]
    fn test_construction_resume_retries_interrupted_placement() {
        static MANAGER: SolverManager<ConstructionPauseSolution> = SolverManager::new();

        let (uninterrupted_job_id, mut uninterrupted_receiver) = MANAGER
            .solve(ConstructionPauseSolution::new(None))
            .expect("uninterrupted job should start");

        let uninterrupted_value = match uninterrupted_receiver
            .blocking_recv()
            .expect("uninterrupted completed event")
        {
            SolverEvent::Completed { metadata, solution } => {
                assert_eq!(metadata.lifecycle_state, SolverLifecycleState::Completed);
                assert_eq!(solution.entities[0].value, Some(64));
                assert_eq!(solution.score(), Some(SoftScore::of(64)));
                solution.entities[0].value
            }
            other => panic!("unexpected event: {other:?}"),
        };

        MANAGER
            .delete(uninterrupted_job_id)
            .expect("delete uninterrupted job");

        let gate = BlockingEvaluationGate::new(1);
        let (job_id, mut receiver) = MANAGER
            .solve(ConstructionPauseSolution::new(Some(gate.clone())))
            .expect("paused job should start");

        gate.wait_until_blocked();
        MANAGER.pause(job_id).expect("pause should be accepted");

        match receiver.blocking_recv().expect("pause requested event") {
            SolverEvent::PauseRequested { metadata } => {
                assert_eq!(
                    metadata.lifecycle_state,
                    SolverLifecycleState::PauseRequested
                );
            }
            other => panic!("unexpected event: {other:?}"),
        }

        gate.release();

        let paused_snapshot_revision = match receiver.blocking_recv().expect("paused event") {
            SolverEvent::Paused { metadata } => {
                assert_eq!(metadata.lifecycle_state, SolverLifecycleState::Paused);
                metadata
                    .snapshot_revision
                    .expect("paused snapshot revision")
            }
            other => panic!("unexpected event: {other:?}"),
        };

        let paused_snapshot = MANAGER
            .get_snapshot(job_id, Some(paused_snapshot_revision))
            .expect("paused snapshot");
        assert_eq!(paused_snapshot.solution.entities[0].value, None);

        MANAGER.resume(job_id).expect("resume should be accepted");

        match receiver.blocking_recv().expect("resumed event") {
            SolverEvent::Resumed { metadata } => {
                assert_eq!(metadata.lifecycle_state, SolverLifecycleState::Solving);
            }
            other => panic!("unexpected event: {other:?}"),
        }

        match receiver.blocking_recv().expect("completed event") {
            SolverEvent::Completed { metadata, solution } => {
                assert_eq!(metadata.lifecycle_state, SolverLifecycleState::Completed);
                assert_eq!(solution.entities[0].value, uninterrupted_value);
                assert_eq!(solution.score(), Some(SoftScore::of(64)));
            }
            other => panic!("unexpected event: {other:?}"),
        }

        MANAGER.delete(job_id).expect("delete resumed job");
    }
}