routik-solver 0.1.0

//! Property tests over the public solver API.
//!
//! Two generators feed the same checks:
//! * `valid_instance` — finite, sane CVRPTW instances. The full invariant oracle
//!   runs (capacity, time windows, depot-due, route/total metrics) plus a
//!   determinism check.
//! * `degenerate_instance` — adversarial inputs (zero/`u32::MAX` capacity and
//!   demand, inverted/NaN windows, NaN/inf coordinates, negative/NaN/inf matrix
//!   entries). Here we assert only that the solver **never panics** and that the
//!   *structural* invariants hold; float checks are gated on a finite matrix.
//!
//! Budgets are deliberately tiny so the whole suite runs in seconds. Case counts
//! are overridable with the `PROPTEST_CASES` env var.

use proptest::prelude::*;

/// Case count for a suite, overridable with `PROPTEST_CASES` (so CI stays fast
/// but a soak run can crank it up).
fn cases(default: u32) -> u32 {
    std::env::var("PROPTEST_CASES")
        .ok()
        .and_then(|s| s.parse().ok())
        .unwrap_or(default)
}

use crate::matrix::{HaversineMatrix, ProvidedMatrix};
use crate::model::{Coord, Problem, Stop, StopId, TimeWindow, Vehicle, VehicleId};
use crate::objective::Objective;
use crate::testkit::{AnyMatrix, check_solution_invariants};
use crate::{Budget, SolveError, SolverConfig, solve};

/// How a generated instance's matrix should be built (kept `Debug`/`Clone` so
/// proptest can print and shrink it; the live `AnyMatrix` is built in the body).
#[derive(Debug, Clone)]
enum MatrixSpec {
    Haversine {
        speed: f64,
    },
    Provided {
        distances: Vec<Vec<f64>>,
        times: Vec<Vec<f64>>,
    },
}

/// Build the live matrix and report whether it is finite + non-negative (so the
/// oracle knows whether its float checks are meaningful).
fn build_matrix(problem: &Problem, spec: &MatrixSpec) -> (AnyMatrix, bool) {
    match spec {
        MatrixSpec::Haversine { speed } => {
            let finite =
                speed.is_finite() && *speed > 0.0 && problem.coords().iter().all(coord_finite);
            (
                AnyMatrix::Haversine(HaversineMatrix::from_problem(problem, *speed)),
                finite,
            )
        }
        MatrixSpec::Provided { distances, times } => {
            let finite = distances
                .iter()
                .chain(times.iter())
                .flatten()
                .all(|v| v.is_finite() && *v >= 0.0);
            let m = ProvidedMatrix::new(distances.clone(), times.clone())
                .expect("generator sizes the matrix to location_count()");
            (AnyMatrix::Provided(m), finite)
        }
    }
}

fn coord_finite(c: &Coord) -> bool {
    c.lat.is_finite() && c.lon.is_finite()
}

/// A tiny, deterministic, iteration-only config.
fn config_strategy() -> impl Strategy<Value = SolverConfig> {
    (
        any::<u64>(),
        0.0f64..1_000.0,
        0.0f64..1_000.0,
        0.0f64..1_000.0,
        1u64..1_500,
        1usize..=2,
    )
        .prop_map(|(seed, w_d, w_v, w_t, iters, restarts)| SolverConfig {
            seed,
            objective: Objective {
                distance: w_d,
                vehicles: w_v,
                time: w_t,
            },
            budget: Budget::iterations(iters),
            restarts,
            initial_temperature: None,
            final_temperature: None,
        })
}

/// An `n×n` matrix spec sized to `location_count`, entries drawn from `value`.
fn provided_spec(
    n: usize,
    value: impl Strategy<Value = f64> + Clone + 'static,
) -> impl Strategy<Value = MatrixSpec> {
    let square = |v: BoxedStrategy<f64>| {
        proptest::collection::vec(proptest::collection::vec(v, n..=n), n..=n)
    };
    (square(value.clone().boxed()), square(value.boxed()))
        .prop_map(|(distances, times)| MatrixSpec::Provided { distances, times })
}

// ---------------------------------------------------------------------------
// Valid instances
// ---------------------------------------------------------------------------

fn valid_stop(i: usize) -> impl Strategy<Value = Stop> {
    let coord = (-89.0f64..89.0, -179.0f64..179.0).prop_map(|(lat, lon)| Coord::new(lat, lon));
    let window = prop_oneof![
        2 => Just(None),
        1 => (0.0f64..50.0, 0.0f64..50.0)
            .prop_map(|(start, len)| Some(TimeWindow { start, end: start + len })),
    ];
    (coord, 0u32..=100, 0.0f64..5.0, window).prop_map(move |(coord, demand, service_time, tw)| {
        Stop {
            id: StopId(i as u32),
            coord,
            demand,
            time_window: tw,
            service_time,
        }
    })
}

fn valid_instance() -> impl Strategy<Value = (Problem, MatrixSpec, SolverConfig)> {
    let stops = (0usize..=15).prop_flat_map(|n| {
        let per_stop: Vec<_> = (0..n).map(valid_stop).collect();
        per_stop
    });
    let vehicles = proptest::collection::vec(1u32..=500, 1..=6).prop_map(|caps| {
        caps.into_iter()
            .enumerate()
            .map(|(i, capacity)| Vehicle {
                id: VehicleId(i as u32),
                capacity,
            })
            .collect::<Vec<_>>()
    });
    let depot = (-89.0f64..89.0, -179.0f64..179.0).prop_map(|(lat, lon)| Coord::new(lat, lon));
    let depot_window = prop_oneof![
        2 => Just(None),
        1 => (0.0f64..5.0, 100.0f64..5_000.0)
            .prop_map(|(start, end)| Some(TimeWindow { start, end })),
    ];

    (stops, vehicles, depot, depot_window)
        .prop_map(|(stops, vehicles, depot, depot_window)| Problem {
            depot,
            stops,
            vehicles,
            depot_window,
        })
        .prop_flat_map(|problem| {
            let n = problem.location_count();
            let matrix = prop_oneof![
                (10.0f64..120.0).prop_map(|speed| MatrixSpec::Haversine { speed }),
                provided_spec(n, 0.0f64..1_000.0),
            ];
            (Just(problem), matrix, config_strategy())
        })
}

// ---------------------------------------------------------------------------
// Degenerate instances
// ---------------------------------------------------------------------------

/// A free f64: finite-ish, but NaN / ±inf a fraction of the time.
fn nasty_f64() -> impl Strategy<Value = f64> + Clone {
    prop_oneof![
        6 => -1_000.0f64..1_000.0,
        1 => Just(0.0),
        1 => Just(f64::NAN),
        1 => Just(f64::INFINITY),
        1 => Just(f64::NEG_INFINITY),
    ]
}

fn degenerate_stop(i: usize) -> impl Strategy<Value = Stop> {
    let coord = (nasty_f64(), nasty_f64()).prop_map(|(lat, lon)| Coord::new(lat, lon));
    let demand = prop_oneof![
        3 => 0u32..=u32::MAX,
        1 => Just(0u32),
        1 => Just(u32::MAX),
    ];
    let service = prop_oneof![
        4 => -10.0f64..10.0,
        1 => Just(f64::NAN),
    ];
    let window = prop_oneof![
        2 => Just(None),
        1 => (nasty_f64(), nasty_f64()).prop_map(|(start, end)| Some(TimeWindow { start, end })),
    ];
    (coord, demand, service, window).prop_map(move |(coord, demand, service_time, tw)| Stop {
        id: StopId(i as u32),
        coord,
        demand,
        time_window: tw,
        service_time,
    })
}

fn degenerate_instance() -> impl Strategy<Value = (Problem, MatrixSpec, SolverConfig)> {
    let stops = (0usize..=12).prop_flat_map(|n| (0..n).map(degenerate_stop).collect::<Vec<_>>());
    let caps = prop_oneof![
        2 => 0u32..=u32::MAX,
        1 => Just(0u32),
        1 => Just(u32::MAX),
    ];
    let vehicles = proptest::collection::vec(caps, 0..=5).prop_map(|caps| {
        caps.into_iter()
            .enumerate()
            .map(|(i, capacity)| Vehicle {
                id: VehicleId(i as u32),
                capacity,
            })
            .collect::<Vec<_>>()
    });
    let depot = (nasty_f64(), nasty_f64()).prop_map(|(lat, lon)| Coord::new(lat, lon));
    let depot_window = prop_oneof![
        2 => Just(None),
        1 => (nasty_f64(), nasty_f64()).prop_map(|(start, end)| Some(TimeWindow { start, end })),
    ];

    (stops, vehicles, depot, depot_window)
        .prop_map(|(stops, vehicles, depot, depot_window)| Problem {
            depot,
            stops,
            vehicles,
            depot_window,
        })
        .prop_flat_map(|problem| {
            let n = problem.location_count();
            let speed = prop_oneof![
                4 => -50.0f64..120.0,
                1 => Just(0.0),
                1 => Just(f64::NAN),
            ];
            let matrix = prop_oneof![
                speed.prop_map(|speed| MatrixSpec::Haversine { speed }),
                provided_spec(n, nasty_f64()),
            ];
            (Just(problem), matrix, config_strategy())
        })
}

proptest! {
    #![proptest_config(ProptestConfig { cases: cases(128), ..ProptestConfig::default() })]

    /// Valid instances: solve succeeds, every returned route honours capacity and
    /// time windows, and metrics add up.
    #[test]
    fn valid_solution_respects_all_invariants(
        (problem, spec, config) in valid_instance()
    ) {
        let (matrix, finite) = build_matrix(&problem, &spec);
        prop_assert!(finite, "valid generator must produce a finite matrix");
        let sol = solve(&problem, &matrix, &config).expect("≥1 vehicle ⇒ Ok");
        check_solution_invariants(&problem, &matrix, &sol, true);
    }

    /// Same inputs, same seed ⇒ byte-identical solution.
    #[test]
    fn solve_is_deterministic(
        (problem, spec, config) in valid_instance()
    ) {
        let (matrix, _) = build_matrix(&problem, &spec);
        let a = solve(&problem, &matrix, &config).expect("≥1 vehicle ⇒ Ok");
        let b = solve(&problem, &matrix, &config).expect("≥1 vehicle ⇒ Ok");
        prop_assert_eq!(a, b);
    }
}

proptest! {
    #![proptest_config(ProptestConfig { cases: cases(256), ..ProptestConfig::default() })]

    /// Degenerate instances: the solver never panics; with no vehicles it returns
    /// `NoVehicles`, otherwise it returns a solution whose structural invariants
    /// hold (float checks gated on a finite matrix).
    #[test]
    fn degenerate_input_never_panics_and_holds_invariants(
        (problem, spec, config) in degenerate_instance()
    ) {
        let (matrix, finite) = build_matrix(&problem, &spec);
        match solve(&problem, &matrix, &config) {
            Ok(sol) => check_solution_invariants(&problem, &matrix, &sol, finite),
            Err(SolveError::NoVehicles) => prop_assert!(problem.vehicles.is_empty()),
        }
    }
}