u-nesting-d2 0.7.2

//! Robustness fuzz harness.
//!
//! Discovered in the hyphen dogfooding triage of ISSUE-u-nesting-20260714
//! (`robustness-panic-abort` #5 and `metaheuristic-quality` #3): the drafts
//! flagged two *code-level* risks that could not be reproduced by hand —
//!
//!   1. a pathological polygon (self-intersecting / collinear / duplicate
//!      vertices) reaching the NFP ear-clipping / union path and panicking
//!      (fatal under the old `panic = "abort"`), and
//!   2. the NFP-guided BLF placer emitting *overlapping* placements because it
//!      silently drops a collision constraint on `compute_nfp` `Err`, clamps a
//!      piece to the boundary without re-verifying, and backs its internal
//!      overlap test with a SAT check that is only valid for convex polygons.
//!
//! These properties are the honest way to close those risks: rather than assert
//! "we could not trigger it", we fuzz the public `solve` surface and check the
//! output against an **independent** oracle.
//!
//! - Panic-safety is proven by construction: any input that reaches `solve`
//!   returns `Ok`/`Err` — never a panic/abort (a panic fails the proptest).
//! - No-overlap is checked with `i_overlay` boolean intersection area, which —
//!   unlike the internal SAT predicate — is correct for **concave** pieces, so a
//!   real overlap in the concave case (#3's precise concern) would be caught.

use std::collections::HashMap;

use i_overlay::core::fill_rule::FillRule;
use i_overlay::core::overlay_rule::OverlayRule;
use i_overlay::float::single::SingleFloatOverlay;
use proptest::prelude::*;
use u_nesting_d2::{Boundary2D, Config, Geometry2D, Nester2D, SolveResult, Solver, Strategy};

/// Shoelace area of a closed ring (sign-agnostic).
fn ring_area(ring: &[(f64, f64)]) -> f64 {
    let n = ring.len();
    if n < 3 {
        return 0.0;
    }
    let mut acc = 0.0;
    for i in 0..n {
        let (x0, y0) = ring[i];
        let (x1, y1) = ring[(i + 1) % n];
        acc += x0 * y1 - x1 * y0;
    }
    (acc * 0.5).abs()
}

/// Robust overlap area of two simple polygons via an `i_overlay` boolean
/// intersection. Correct for concave inputs (the SAT predicate the library uses
/// internally is only reliable for convex shapes). Ignoring interior holes of
/// the intersection only *over*-estimates the area, so a real overlap can never
/// be hidden — the test stays sound.
fn intersection_area(a: &[(f64, f64)], b: &[(f64, f64)]) -> f64 {
    let subj: Vec<[f64; 2]> = a.iter().map(|&(x, y)| [x, y]).collect();
    let clip: Vec<[f64; 2]> = b.iter().map(|&(x, y)| [x, y]).collect();
    let shapes = subj.overlay(&[clip], OverlayRule::Intersect, FillRule::NonZero);

    let mut area = 0.0;
    for shape in &shapes {
        if let Some(outer) = shape.first() {
            let ring: Vec<(f64, f64)> = outer.iter().map(|&[x, y]| (x, y)).collect();
            area += ring_area(&ring);
        }
    }
    area
}

/// A star-shaped ring: `radii.len()` vertices at equal angular steps, each at its
/// own radius. Angular monotonicity makes it a *simple* (non-self-intersecting)
/// polygon by construction, and it is genuinely **concave** whenever the radii
/// differ — exactly the shape class the internal SAT overlap test cannot handle.
fn star_ring(radii: &[f64]) -> Vec<(f64, f64)> {
    let n = radii.len();
    (0..n)
        .map(|i| {
            let ang = std::f64::consts::TAU * (i as f64) / (n as f64);
            (radii[i] * ang.cos(), radii[i] * ang.sin())
        })
        .collect()
}

/// Assert that no two placements in `result` overlap, reconstructing each
/// piece's on-sheet footprint with the library's own transform and checking
/// every pair with the independent `i_overlay` oracle.
fn assert_no_overlap(pieces: &[(String, Geometry2D)], result: &SolveResult<f64>, eps: f64) {
    let map: HashMap<&str, &Geometry2D> = pieces.iter().map(|(id, g)| (id.as_str(), g)).collect();

    let placed: Vec<Vec<(f64, f64)>> = result
        .placements
        .iter()
        .map(|p| {
            let g = map[p.geometry_id.as_str()];
            let rot = p.rotation.first().copied().unwrap_or(0.0);
            g.transformed_exterior(p.position[0], p.position[1], rot)
        })
        .collect();

    for i in 0..placed.len() {
        for j in (i + 1)..placed.len() {
            let overlap = intersection_area(&placed[i], &placed[j]);
            assert!(
                overlap < eps,
                "placements {i} and {j} overlap by area {overlap} (> {eps})"
            );
        }
    }
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(200))]

    /// Arbitrary vertex lists — most are self-intersecting, collinear, or
    /// zero-area — fed through the full `solve` pipeline for the two fast,
    /// deterministic strategies. The contract is only that `solve` *returns*:
    /// pathological rings must be rejected as `Err`, never abort the process.
    #[test]
    fn solve_never_panics_on_arbitrary_polygon(
        verts in prop::collection::vec((-500.0f64..500.0, -500.0f64..500.0), 3..10),
        strat in prop::sample::select(vec![Strategy::BottomLeftFill, Strategy::NfpGuided]),
        spacing in 0.0f64..20.0,
        margin in 0.0f64..10.0,
    ) {
        let g = Geometry2D::new("p").with_polygon(verts).with_quantity(3);
        let boundary = Boundary2D::rectangle(1000.0, 1000.0);
        let config = Config::default()
            .with_strategy(strat)
            .with_spacing(spacing)
            .with_margin(margin);

        // Ok or Err are both acceptable; a panic is not.
        let _ = Nester2D::new(config).solve(&[g], &boundary);
    }
}

proptest! {
    // NFP placement dominates this file's runtime; 40 cases with shrinking give
    // solid coverage while keeping CI minutes in check (per the resource policy).
    #![proptest_config(ProptestConfig::with_cases(40))]

    /// Random axis-aligned rectangles (convex) placed with BLF/NFP must produce a
    /// non-overlapping layout. A `spacing` gap guarantees the true intersection
    /// area is zero, so any positive area is a genuine defect.
    #[test]
    fn placement_has_no_overlap_convex(
        dims in prop::collection::vec((10.0f64..200.0, 10.0f64..200.0), 2..6),
        strat in prop::sample::select(vec![Strategy::BottomLeftFill, Strategy::NfpGuided]),
    ) {
        let pieces: Vec<(String, Geometry2D)> = dims
            .iter()
            .enumerate()
            .map(|(i, &(w, h))| {
                let id = format!("r{i}");
                (id.clone(), Geometry2D::rectangle(id, w, h).with_quantity(2))
            })
            .collect();
        let geoms: Vec<Geometry2D> = pieces.iter().map(|(_, g)| g.clone()).collect();
        let boundary = Boundary2D::rectangle(1000.0, 5000.0);

        let result = Nester2D::new(Config::default().with_strategy(strat).with_spacing(2.0))
            .solve(&geoms, &boundary)
            .expect("convex rectangles are always valid input");

        assert_no_overlap(&pieces, &result, 1e-6);
    }
}

proptest! {
    #![proptest_config(ProptestConfig::with_cases(40))]

    /// The concave case #3 is specifically about: star-shaped (simple, concave)
    /// pieces where the internal SAT overlap test is unreliable. The independent
    /// `i_overlay` oracle checks the real output. A `spacing` gap again makes the
    /// expected intersection area zero.
    #[test]
    fn placement_has_no_overlap_concave(
        stars in prop::collection::vec(
            prop::collection::vec(20.0f64..120.0, 5..9),
            2..5,
        ),
        strat in prop::sample::select(vec![Strategy::BottomLeftFill, Strategy::NfpGuided]),
    ) {
        let pieces: Vec<(String, Geometry2D)> = stars
            .iter()
            .enumerate()
            .map(|(i, radii)| {
                let id = format!("s{i}");
                let ring = star_ring(radii);
                (id.clone(), Geometry2D::new(id).with_polygon(ring).with_quantity(2))
            })
            .collect();
        let geoms: Vec<Geometry2D> = pieces.iter().map(|(_, g)| g.clone()).collect();
        let boundary = Boundary2D::rectangle(1000.0, 5000.0);

        // A degenerate star (all-equal radii rounding to collinear runs) may be
        // rejected; only the accepted layouts carry the no-overlap obligation.
        if let Ok(result) = Nester2D::new(Config::default().with_strategy(strat).with_spacing(2.0))
            .solve(&geoms, &boundary)
        {
            // Concave boolean ops carry more FP noise than the convex case; a
            // real overlap (with a 2-unit spacing gap) is orders of magnitude
            // larger than this floor.
            assert_no_overlap(&pieces, &result, 1e-2);
        }
    }
}