routik-solver 0.1.0

//! Fuzzing / property-testing support: an **independent** invariant oracle for
//! solver output, plus an [`arbitrary`]-driven instance builder for cargo-fuzz.
//!
//! The oracle re-derives every checked property from the *public* model
//! ([`Problem`], [`CostMatrix`], [`Solution`]) — it shares no code with the
//! solver's own feasibility module, so it is a genuine cross-check, not a
//! tautology. It is compiled both for the crate's own `proptest` unit tests
//! (`cfg(test)`) and, behind the `fuzzing` feature, for the external cargo-fuzz
//! crate.
//!
//! Solver precondition honoured by every builder here: the cost matrix is sized
//! to `problem.location_count()` (`stops + 1`). A wrong-sized matrix is the API
//! layer's contract to reject (`routik-api::convert::validate`), not the
//! solver's, so we never hand the solver one.

use std::collections::{HashMap, HashSet};

use crate::matrix::{CostMatrix, HaversineMatrix, ProvidedMatrix};
use crate::model::{Problem, Solution, Stop, StopId};

/// A cost matrix that is either straight-line or caller-supplied — lets one
/// generator pick between the two backings while the solver sees a single type.
pub enum AnyMatrix {
    Haversine(HaversineMatrix),
    Provided(ProvidedMatrix),
}

impl CostMatrix for AnyMatrix {
    fn distance(&self, a: crate::model::LocationId, b: crate::model::LocationId) -> f64 {
        match self {
            AnyMatrix::Haversine(m) => m.distance(a, b),
            AnyMatrix::Provided(m) => m.distance(a, b),
        }
    }

    fn time(&self, a: crate::model::LocationId, b: crate::model::LocationId) -> f64 {
        match self {
            AnyMatrix::Haversine(m) => m.time(a, b),
            AnyMatrix::Provided(m) => m.time(a, b),
        }
    }
}

/// Relative-with-floor float comparison. The floor keeps tiny values from
/// failing on rounding; the relative term scales to large distance sums.
fn close(a: f64, b: f64) -> bool {
    if a == b {
        return true; // also catches inf == inf
    }
    let diff = (a - b).abs();
    diff <= 1e-6 * a.abs().max(b.abs()).max(1.0)
}

/// Whether every time-relevant input is finite: service times, stop windows, and
/// the depot window. Coordinates are excluded — they reach the walk only through
/// the matrix, whose finiteness the caller reports separately.
fn time_data_finite(problem: &Problem) -> bool {
    let window_finite = |w: &Option<crate::model::TimeWindow>| {
        w.is_none_or(|tw| tw.start.is_finite() && tw.end.is_finite())
    };
    window_finite(&problem.depot_window)
        && problem
            .stops
            .iter()
            .all(|s| s.service_time.is_finite() && window_finite(&s.time_window))
}

/// Assert every hard invariant the public solver contract guarantees on a
/// returned [`Solution`]. Panics (via `assert!`) with a descriptive message on
/// the first violation — exactly what the fuzzer/proptest runner reports.
///
/// `matrix_is_finite` gates the *float* checks (time windows, depot-due, and the
/// distance/time metrics): they are only meaningful when every matrix entry is
/// finite and non-negative. The *structural* checks (capacity, stop accounting)
/// are always enforced — they hold regardless of the matrix.
///
/// Contract enforced (see [`Solution`] docs): the routes a solution *builds* are
/// each individually valid (within capacity, time-window- and depot-feasible)
/// even when the solution as a whole is infeasible; infeasibility is carried
/// solely by `unassigned`.
pub fn check_solution_invariants<M: CostMatrix>(
    problem: &Problem,
    matrix: &M,
    sol: &Solution,
    matrix_is_finite: bool,
) {
    // Stop id -> (location index in 1..=n, the stop). Generators guarantee unique
    // stop ids (the solver's documented input contract), so this never collides.
    let mut by_id: HashMap<StopId, (usize, &Stop)> = HashMap::with_capacity(problem.stops.len());
    for (i, stop) in problem.stops.iter().enumerate() {
        by_id.insert(stop.id, (i + 1, stop));
    }
    let capacity_of: HashMap<_, _> = problem
        .vehicles
        .iter()
        .map(|v| (v.id, v.capacity))
        .collect();

    // Float checks (time windows, depot-due, route/total metrics) are only
    // meaningful when *all* the arithmetic inputs are finite — not just the matrix
    // but also the depot/stop windows and service times. A NaN/inf anywhere in the
    // time data poisons the walk (e.g. `NaN.max(start)` can rescue an otherwise
    // infeasible stop), and prod never sees such input (`convert::validate` rejects
    // non-finite values). The *structural* checks below run unconditionally.
    let check_floats = matrix_is_finite && time_data_finite(problem);

    // Never more routes than vehicles.
    assert!(
        sol.routes.len() <= problem.vehicles.len(),
        "solution has {} routes but only {} vehicles",
        sol.routes.len(),
        problem.vehicles.len(),
    );

    let mut assigned: HashSet<StopId> = HashSet::new();
    let mut used_vehicles: HashSet<_> = HashSet::new();
    let mut sum_distance = 0.0;
    let mut sum_time = 0.0;

    for route in &sol.routes {
        assert!(
            used_vehicles.insert(route.vehicle_id),
            "vehicle {:?} is used by more than one route",
            route.vehicle_id,
        );
        let capacity = *capacity_of.get(&route.vehicle_id).unwrap_or_else(|| {
            panic!(
                "route references vehicle {:?} not in the fleet",
                route.vehicle_id
            )
        });

        // Re-walk the route from the depot, mirroring the documented time model
        // (early arrival waits; service must *begin* on or before the window end;
        // the return leg must land by the depot due time).
        let depart = problem.depot_open();
        let mut prev = crate::model::LocationId::DEPOT;
        let mut t = depart;
        let mut distance = 0.0;
        let mut load: u64 = 0; // u64 so the oracle never overflows on huge demand

        for stop_id in &route.stop_ids {
            let (loc, stop) = *by_id
                .get(stop_id)
                .unwrap_or_else(|| panic!("route references stop {stop_id:?} not in the problem"));
            assert!(
                assigned.insert(*stop_id),
                "stop {stop_id:?} appears on more than one route",
            );
            let cur = crate::model::LocationId(loc);
            distance += matrix.distance(prev, cur);
            let arrive = t + matrix.time(prev, cur);
            let begin = match stop.time_window {
                Some(tw) => {
                    let begin = arrive.max(tw.start);
                    if check_floats {
                        assert!(
                            begin <= tw.end + 1e-6 * tw.end.abs().max(1.0),
                            "route for vehicle {:?}: stop {stop_id:?} serviced at {begin} \
                             after its window end {}",
                            route.vehicle_id,
                            tw.end,
                        );
                    }
                    begin
                }
                None => arrive,
            };
            t = begin + stop.service_time;
            load += u64::from(stop.demand);
            prev = cur;
        }

        distance += matrix.distance(prev, crate::model::LocationId::DEPOT);
        t += matrix.time(prev, crate::model::LocationId::DEPOT);

        // Capacity: structural, always checked.
        assert!(
            load <= u64::from(capacity),
            "route for vehicle {:?} carries load {load} over capacity {capacity}",
            route.vehicle_id,
        );
        assert_eq!(
            load,
            u64::from(route.load),
            "route for vehicle {:?} reports load {} but carries {load}",
            route.vehicle_id,
            route.load,
        );

        if check_floats {
            let due = problem.depot_due();
            assert!(
                t <= due + 1e-6 * due.abs().max(1.0),
                "route for vehicle {:?} returns to depot at {t} after due {due}",
                route.vehicle_id,
            );
            assert!(
                close(distance, route.distance),
                "route for vehicle {:?}: reported distance {} != recomputed {distance}",
                route.vehicle_id,
                route.distance,
            );
            assert!(
                close(t - depart, route.time),
                "route for vehicle {:?}: reported time {} != recomputed {}",
                route.vehicle_id,
                route.time,
                t - depart,
            );
        }

        sum_distance += route.distance;
        sum_time += route.time;
    }

    if check_floats {
        assert!(
            close(sum_distance, sol.total_distance),
            "total_distance {} != sum of route distances {sum_distance}",
            sol.total_distance,
        );
        assert!(
            close(sum_time, sol.total_time),
            "total_time {} != sum of route times {sum_time}",
            sol.total_time,
        );
    }

    // Stop accounting: assigned and unassigned partition the input stops exactly,
    // with no overlap and nothing invented or dropped.
    let mut unassigned: HashSet<StopId> = HashSet::new();
    for u in &sol.unassigned {
        assert!(
            by_id.contains_key(&u.stop),
            "unassigned stop {:?} is not in the problem",
            u.stop,
        );
        assert!(
            unassigned.insert(u.stop),
            "stop {:?} is reported unassigned twice",
            u.stop,
        );
        assert!(
            !assigned.contains(&u.stop),
            "stop {:?} is both routed and unassigned",
            u.stop,
        );
    }
    assert_eq!(
        assigned.len() + unassigned.len(),
        problem.stops.len(),
        "assigned ({}) + unassigned ({}) != total stops ({})",
        assigned.len(),
        unassigned.len(),
        problem.stops.len(),
    );

    // A feasible solution leaves nothing unassigned.
    if sol.feasible {
        assert!(
            sol.unassigned.is_empty(),
            "solution is marked feasible but reports {} unassigned stops",
            sol.unassigned.len(),
        );
        assert_eq!(
            assigned.len(),
            problem.stops.len(),
            "feasible solution does not route every stop",
        );
    }
}

// ---------------------------------------------------------------------------
// Arbitrary-driven instance builder — cargo-fuzz only (needs the `arbitrary`
// crate, pulled in by the `fuzzing` feature).
// ---------------------------------------------------------------------------

/// A fuzz instance: a problem, a matrix sized to it, a (tiny-budget) config, and
/// whether the matrix is finite + non-negative so the oracle knows which checks
/// it can run.
#[cfg(feature = "fuzzing")]
pub struct FuzzCase {
    pub problem: Problem,
    pub matrix: AnyMatrix,
    pub config: crate::SolverConfig,
    pub matrix_is_finite: bool,
}

#[cfg(feature = "fuzzing")]
mod fuzz_builder {
    use super::{AnyMatrix, FuzzCase};
    use crate::matrix::{HaversineMatrix, ProvidedMatrix};
    use crate::model::{Coord, Problem, Stop, StopId, TimeWindow, Vehicle, VehicleId};
    use crate::objective::Objective;
    use crate::{Budget, SolverConfig};
    use arbitrary::{Arbitrary, Unstructured};

    /// Cap instance size so a single fuzz iteration stays fast; coverage comes
    /// from many iterations, not one giant one.
    const MAX_STOPS: usize = 60;
    const MAX_VEHICLES: usize = 12;

    /// Build a (deliberately adversarial-leaning) instance from raw fuzzer bytes.
    pub fn build(u: &mut Unstructured) -> arbitrary::Result<FuzzCase> {
        let n_stops = u.int_in_range(0..=MAX_STOPS)?;
        let n_vehicles = u.int_in_range(0..=MAX_VEHICLES)?;

        let mut stops = Vec::with_capacity(n_stops);
        for i in 0..n_stops {
            let coord = Coord::new(arb_f64(u)?, arb_f64(u)?);
            let demand = u32::arbitrary(u)?;
            let service_time = arb_f64(u)?;
            let time_window = if bool::arbitrary(u)? {
                Some(TimeWindow {
                    start: arb_f64(u)?,
                    end: arb_f64(u)?,
                })
            } else {
                None
            };
            stops.push(Stop {
                // Unique ids: the solver's input contract.
                id: StopId(i as u32),
                coord,
                demand,
                time_window,
                service_time,
            });
        }

        let vehicles = (0..n_vehicles)
            .map(|i| {
                Ok(Vehicle {
                    id: VehicleId(i as u32),
                    capacity: u32::arbitrary(u)?,
                })
            })
            .collect::<arbitrary::Result<Vec<_>>>()?;

        let depot_window = if bool::arbitrary(u)? {
            Some(TimeWindow {
                start: arb_f64(u)?,
                end: arb_f64(u)?,
            })
        } else {
            None
        };

        let problem = Problem {
            depot: Coord::new(arb_f64(u)?, arb_f64(u)?),
            stops,
            vehicles,
            depot_window,
        };

        let n = problem.location_count();
        let (matrix, matrix_is_finite) = if bool::arbitrary(u)? {
            // Haversine over the (possibly non-finite) coordinates.
            let speed = arb_f64(u)?;
            let finite =
                speed.is_finite() && speed > 0.0 && problem.coords().iter().all(coord_finite);
            (
                AnyMatrix::Haversine(HaversineMatrix::from_problem(&problem, speed)),
                finite,
            )
        } else {
            // A caller-style matrix of arbitrary (incl. non-finite / negative) costs.
            let mut finite = true;
            let mut rows_d = Vec::with_capacity(n);
            let mut rows_t = Vec::with_capacity(n);
            for _ in 0..n {
                let mut rd = Vec::with_capacity(n);
                let mut rt = Vec::with_capacity(n);
                for _ in 0..n {
                    let d = arb_f64(u)?;
                    let t = arb_f64(u)?;
                    finite &= d.is_finite() && d >= 0.0 && t.is_finite() && t >= 0.0;
                    rd.push(d);
                    rt.push(t);
                }
                rows_d.push(rd);
                rows_t.push(rt);
            }
            // `n >= 1` always (depot), so `new` only fails on our own bug.
            let m = ProvidedMatrix::new(rows_d, rows_t).expect("square n×n by construction");
            (AnyMatrix::Provided(m), finite)
        };

        // Tiny, deterministic budget: iterations only, no wall clock.
        let config = SolverConfig {
            seed: u64::arbitrary(u)?,
            objective: Objective {
                distance: arb_weight(u)?,
                vehicles: arb_weight(u)?,
                time: arb_weight(u)?,
            },
            budget: Budget::iterations(u.int_in_range(1..=2_000)?),
            restarts: u.int_in_range(1..=3)?,
            initial_temperature: None,
            final_temperature: None,
        };

        Ok(FuzzCase {
            problem,
            matrix,
            config,
            matrix_is_finite,
        })
    }

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

    /// A raw arbitrary f64, kept in a sane magnitude band but free to be NaN/inf
    /// (a fraction of the time) so the solver meets degenerate floats.
    fn arb_f64(u: &mut Unstructured) -> arbitrary::Result<f64> {
        let pick = u8::arbitrary(u)?;
        Ok(match pick {
            0 => f64::NAN,
            1 => f64::INFINITY,
            2 => f64::NEG_INFINITY,
            3 => 0.0,
            _ => {
                // Bounded magnitude so normal cases dominate the search.
                let v = f64::arbitrary(u)?;
                if v.is_finite() {
                    v.clamp(-1.0e6, 1.0e6)
                } else {
                    v
                }
            }
        })
    }

    /// A finite, non-negative objective weight.
    fn arb_weight(u: &mut Unstructured) -> arbitrary::Result<f64> {
        let v = f64::arbitrary(u)?;
        Ok(if v.is_finite() {
            v.abs().min(1.0e3)
        } else {
            0.0
        })
    }
}

#[cfg(feature = "fuzzing")]
pub use fuzz_builder::build;