condor/

polygonal.rs

//! Polygonal scene types (re-export) plus root-owned embedded pack loaders.
//!
//! # Facade role
//!
//! | Surface | Owner |
//! | --- | --- |
//! | Geometry substrate (`Point2`, `Polygon`, `PolygonScene`, …) | `condor-pathfinding-geometry` (`condor_geometry`) |
//! | Exact / continuous solvers (`VisibilityGraph`, `ContinuousShortestPathMap`, …) | geometry crate; re-exported at the facade crate root |
//! | Embedded pack kinds, TOML manifests, loaders, oracle validation | **this facade module** (root-owned adapter) |
//! | Structured load errors | [`crate::error`] (root-owned) |
//!
//! # Geometry contract
//!
//! - [`PolygonScene::is_walkable`]: a point is inside world bounds and not strictly
//!   inside any obstacle interior. Obstacle boundary points (non-sealed) count
//!   as free space.
//! - [`PolygonScene::segment_is_walkable`]: every sample of the open segment
//!   (endpoints, edge intersections, interval midpoints) must be traversable.
//! - **Sealed edges**: obstacle edges that lie on the world boundary are
//!   non-traversable. Endpoints on sealed edges fail
//!   [`PolygonScene::validate`] / `validate_source` / `validate_goal` even when
//!   they pass the looser point predicate used by some online checks.
//!
//! # Pack loading
//!
//! Geometry validates bounds, simple polygons, and endpoint traversability.
//! Facade loaders then enforce pack oracles (exact path cost or structural
//! no-path proofs) against that runtime geometry via [`ArtifactLoadError`].

use serde::Deserialize;

use crate::{ArtifactDataError, ArtifactLoadError};

const MANIFEST: &str = include_str!("polygonal/packs/starter.toml");
const STRESS_MANIFEST: &str = include_str!("polygonal/packs/stress.toml");
const EPSILON: f64 = 1e-9;

/// Which embedded polygon scene pack a multi-pack loader should open.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PolygonScenePackKind {
    /// Starter continuous pack (`polygon-scene-pack-v0-alpha`).
    Starter,
    /// Condor-owned continuous stress pack (`polygon-scene-stress-pack-v0-alpha`).
    Stress,
}

impl PolygonScenePackKind {
    /// Stable pack identifier stored in the TOML manifest.
    #[must_use]
    pub const fn pack_id(self) -> &'static str {
        match self {
            Self::Starter => "polygon-scene-pack-v0-alpha",
            Self::Stress => "polygon-scene-stress-pack-v0-alpha",
        }
    }

    /// Stable logical/report manifest identity for the embedded fixture.
    #[must_use]
    pub const fn manifest_path(self) -> &'static str {
        match self {
            Self::Starter => "fixtures/polygon_scene_pack_v0.toml",
            Self::Stress => "fixtures/polygon_scene_stress_pack_v0.toml",
        }
    }

    /// Loads and validates the embedded pack for this kind.
    ///
    /// # Errors
    ///
    /// Returns [`ArtifactLoadError`] when the manifest is malformed or a scene
    /// violates its geometry or oracle contract.
    pub fn load(self) -> Result<PolygonScenePack, ArtifactLoadError> {
        match self {
            Self::Starter => load_polygon_scene_pack(),
            Self::Stress => load_polygon_scene_stress_pack(),
        }
    }
}

pub use condor_geometry::{
    Point2, Polygon, PolygonEndpoint, PolygonScene, PolygonSearchRequest, PolygonValidationError,
    WorldBounds,
};

/// Axis of a full-width/height obstacle that separates start from goal.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SeparationAxis {
    /// Obstacle spans the world vertically and splits left/right free space.
    Vertical,
    /// Obstacle spans the world horizontally and splits below/above free space.
    Horizontal,
}

/// Structural certificate that no continuous free-space path exists.
///
/// Used by fixture oracles; solvers still prove no-path by search exhaustion.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum NoPathProof {
    /// Obstacle touches both opposite world boundaries on `axis` and endpoints
    /// lie on opposite sides of that separator.
    BoundarySeparator {
        obstacle_index: usize,
        axis: SeparationAxis,
    },
}

/// Expected search outcome attached to a polygon benchmark fixture.
#[derive(Debug, Clone, PartialEq)]
pub enum PolygonSceneOracle {
    /// Reachable: witness polyline must be walkable and match `expected_cost` within epsilon.
    ExactPathCost {
        expected_cost: f64,
        witness_path: Vec<Point2>,
    },
    /// Unreachable: structural separator proof checked at load time.
    NoPath { proof: NoPathProof },
}

/// One validated polygon benchmark scene with request and oracle metadata.
#[derive(Debug, Clone, PartialEq)]
pub struct PolygonSceneFixture {
    pub scene_id: String,
    pub family: String,
    pub scene: PolygonScene,
    pub request: PolygonSearchRequest,
    pub oracle: PolygonSceneOracle,
}

impl PolygonSceneFixture {
    /// Criterion / report slice: `"reachable"` or `"no-path"`.
    #[must_use]
    pub fn benchmark_slice(&self) -> &'static str {
        match self.oracle {
            PolygonSceneOracle::ExactPathCost { .. } => "reachable",
            PolygonSceneOracle::NoPath { .. } => "no-path",
        }
    }

    /// Stable path fragment `{slice}/{family}/{scene_id}` for report grouping.
    #[must_use]
    pub fn benchmark_path(&self) -> String {
        format!(
            "{}/{}/{}",
            self.benchmark_slice(),
            self.family,
            self.scene_id
        )
    }

    /// Full benchmark id `{algorithm}/{benchmark_path}` for capture reports.
    #[must_use]
    pub fn benchmark_id(&self, algorithm: &str) -> String {
        format!("{algorithm}/{}", self.benchmark_path())
    }

    /// Human-readable reason string for scorecards and catalog exports.
    #[must_use]
    pub fn benchmark_reason(&self) -> String {
        let obstacle_count = self.scene.obstacles.len();
        let obstacle_label = if obstacle_count == 1 {
            "polygon obstacle"
        } else {
            "polygon obstacles"
        };

        match self.oracle {
            PolygonSceneOracle::ExactPathCost { .. } => {
                format!("Exact continuous scene with {obstacle_count} {obstacle_label}")
            }
            PolygonSceneOracle::NoPath { .. } => {
                format!("Continuous separator scene with {obstacle_count} {obstacle_label}")
            }
        }
    }
}

/// Loaded polygon benchmark pack: identity, format version, and validated fixtures.
#[derive(Debug, Clone, PartialEq)]
pub struct PolygonScenePack {
    pub pack_id: String,
    pub format_version: u32,
    pub scenes: Vec<PolygonSceneFixture>,
}

/// Loads the embedded starter polygon scene pack (`polygon-scene-pack-v0-alpha`).
///
/// # Errors
///
/// Returns [`ArtifactLoadError`] when the manifest or any fixture fails validation.
pub fn load_polygon_scene_pack() -> Result<PolygonScenePack, ArtifactLoadError> {
    load_polygon_scene_pack_from_str(MANIFEST).map_err(ArtifactLoadError::polygon)
}

/// Loads the embedded continuous stress pack (`polygon-scene-stress-pack-v0-alpha`).
///
/// # Errors
///
/// Returns [`ArtifactLoadError`] when the manifest or any fixture fails validation.
pub fn load_polygon_scene_stress_pack() -> Result<PolygonScenePack, ArtifactLoadError> {
    load_polygon_scene_pack_from_str(STRESS_MANIFEST).map_err(ArtifactLoadError::polygon)
}

fn load_polygon_scene_pack_from_str(manifest: &str) -> Result<PolygonScenePack, ArtifactDataError> {
    let pack: PolygonScenePackManifest = toml::from_str(manifest)?;
    if pack.format_version != 1 {
        return Err(ArtifactDataError::unsupported_version(
            "polygon scene pack",
            pack.format_version,
        ));
    }

    if pack.pack_id.trim().is_empty() {
        return Err(ArtifactDataError::empty_identifier(
            "polygon scene pack",
            "pack_id",
        ));
    }

    let scenes = pack
        .scenes
        .into_iter()
        .map(build_fixture)
        .collect::<Result<Vec<_>, _>>()?;

    Ok(PolygonScenePack {
        pack_id: pack.pack_id,
        format_version: pack.format_version,
        scenes,
    })
}

#[derive(Debug, Deserialize)]
struct PolygonScenePackManifest {
    pack_id: String,
    format_version: u32,
    scenes: Vec<PolygonSceneSpec>,
}

#[derive(Debug, Deserialize)]
struct PolygonSceneSpec {
    scene_id: String,
    family: String,
    world_bounds: [f64; 4],
    start: [f64; 2],
    goal: [f64; 2],
    #[serde(default)]
    obstacles: Vec<PolygonSpec>,
    oracle_kind: String,
    expected_cost: Option<f64>,
    witness_path: Option<Vec<[f64; 2]>>,
    proof_kind: Option<String>,
    proof_obstacle_index: Option<usize>,
    proof_axis: Option<String>,
}

#[derive(Debug, Deserialize)]
struct PolygonSpec {
    vertices: Vec<[f64; 2]>,
}

fn build_fixture(spec: PolygonSceneSpec) -> Result<PolygonSceneFixture, ArtifactDataError> {
    if spec.family.trim().is_empty() {
        return Err(ArtifactDataError::missing_required_field(
            spec.scene_id.clone(),
            "family",
        ));
    }

    let scene = PolygonScene {
        world_bounds: WorldBounds::new(
            Point2::new(spec.world_bounds[0], spec.world_bounds[1]),
            Point2::new(spec.world_bounds[2], spec.world_bounds[3]),
        ),
        obstacles: spec
            .obstacles
            .into_iter()
            .map(|polygon| {
                Polygon::new(
                    polygon
                        .vertices
                        .into_iter()
                        .map(|vertex| Point2::new(vertex[0], vertex[1]))
                        .collect(),
                )
            })
            .collect(),
    };
    let request = PolygonSearchRequest::new(
        Point2::new(spec.start[0], spec.start[1]),
        Point2::new(spec.goal[0], spec.goal[1]),
    );

    scene.validate(request)?;

    let oracle = match spec.oracle_kind.as_str() {
        "exact-path-cost" => {
            let expected_cost = spec.expected_cost.ok_or_else(|| {
                ArtifactDataError::missing_required_field(spec.scene_id.clone(), "expected_cost")
            })?;
            let witness_path = spec
                .witness_path
                .ok_or_else(|| {
                    ArtifactDataError::missing_required_field(spec.scene_id.clone(), "witness_path")
                })?
                .into_iter()
                .map(|point| Point2::new(point[0], point[1]))
                .collect();

            PolygonSceneOracle::ExactPathCost {
                expected_cost,
                witness_path,
            }
        }
        "no-path" => {
            let proof_kind = spec.proof_kind.as_deref().ok_or_else(|| {
                ArtifactDataError::missing_required_field(spec.scene_id.clone(), "proof_kind")
            })?;
            let obstacle_index = spec.proof_obstacle_index.ok_or_else(|| {
                ArtifactDataError::missing_required_field(
                    spec.scene_id.clone(),
                    "proof_obstacle_index",
                )
            })?;
            let axis = match spec.proof_axis.as_deref() {
                Some("vertical") => SeparationAxis::Vertical,
                Some("horizontal") => SeparationAxis::Horizontal,
                Some(other) => {
                    return Err(ArtifactDataError::invalid_value(
                        spec.scene_id.clone(),
                        "proof_axis",
                        crate::ArtifactContractLocation::NONE,
                        other,
                    ));
                }
                None => {
                    return Err(ArtifactDataError::missing_required_field(
                        spec.scene_id.clone(),
                        "proof_axis",
                    ));
                }
            };

            let proof = match proof_kind {
                "boundary-separator" => NoPathProof::BoundarySeparator {
                    obstacle_index,
                    axis,
                },
                other => {
                    return Err(ArtifactDataError::invalid_value(
                        spec.scene_id.clone(),
                        "proof_kind",
                        crate::ArtifactContractLocation::NONE,
                        other,
                    ));
                }
            };

            PolygonSceneOracle::NoPath { proof }
        }
        other => {
            return Err(ArtifactDataError::invalid_value(
                spec.scene_id.clone(),
                "oracle_kind",
                crate::ArtifactContractLocation::NONE,
                other,
            ));
        }
    };

    validate_oracle(&scene, request, &oracle, spec.scene_id.as_str())?;

    Ok(PolygonSceneFixture {
        scene_id: spec.scene_id,
        family: spec.family,
        scene,
        request,
        oracle,
    })
}

fn validate_oracle(
    scene: &PolygonScene,
    request: PolygonSearchRequest,
    oracle: &PolygonSceneOracle,
    scene_id: &str,
) -> Result<(), ArtifactDataError> {
    match oracle {
        PolygonSceneOracle::ExactPathCost {
            expected_cost,
            witness_path,
        } => validate_exact_path_oracle(scene, request, *expected_cost, witness_path, scene_id),
        PolygonSceneOracle::NoPath { proof } => {
            validate_no_path_proof(scene, request, *proof, scene_id)
        }
    }
}

fn validate_exact_path_oracle(
    scene: &PolygonScene,
    request: PolygonSearchRequest,
    expected_cost: f64,
    witness_path: &[Point2],
    scene_id: &str,
) -> Result<(), ArtifactDataError> {
    if witness_path.len() < 2 {
        return Err(ArtifactDataError::invalid_value(
            scene_id,
            "witness_path",
            crate::ArtifactContractLocation::NONE,
            witness_path.len(),
        ));
    }

    if witness_path.first() != Some(&request.start) {
        return Err(ArtifactDataError::inconsistent_data(
            scene_id,
            "witness_path/start",
            crate::ArtifactContractLocation::index(0),
            format!("{:?}", witness_path.first()),
        ));
    }

    if witness_path.last() != Some(&request.goal) {
        return Err(ArtifactDataError::inconsistent_data(
            scene_id,
            "witness_path/goal",
            crate::ArtifactContractLocation::index(witness_path.len() - 1),
            format!("{:?}", witness_path.last()),
        ));
    }

    for pair in witness_path.windows(2) {
        validate_polyline_segment(scene, pair[0], pair[1], scene_id)?;
    }

    let actual_cost = polyline_length(witness_path);
    if (actual_cost - expected_cost).abs() > EPSILON {
        return Err(ArtifactDataError::inconsistent_data(
            scene_id,
            "witness_path/expected_cost",
            crate::ArtifactContractLocation::NONE,
            actual_cost,
        ));
    }

    Ok(())
}

fn validate_no_path_proof(
    scene: &PolygonScene,
    request: PolygonSearchRequest,
    proof: NoPathProof,
    scene_id: &str,
) -> Result<(), ArtifactDataError> {
    match proof {
        NoPathProof::BoundarySeparator {
            obstacle_index,
            axis,
        } => {
            let obstacle = scene.obstacles.get(obstacle_index).ok_or_else(|| {
                ArtifactDataError::invalid_reference(
                    scene_id,
                    "proof_obstacle_index",
                    crate::ArtifactContractLocation::index(obstacle_index),
                    obstacle_index,
                )
            })?;
            let (min_x, max_x, min_y, max_y) = polygon_bounds(obstacle.vertices());

            match axis {
                SeparationAxis::Vertical => {
                    if (min_y - scene.world_bounds.min.y).abs() > EPSILON
                        || (max_y - scene.world_bounds.max.y).abs() > EPSILON
                    {
                        return Err(ArtifactDataError::inconsistent_data(
                            scene_id,
                            "proof_axis/world_bounds",
                            crate::ArtifactContractLocation::index(obstacle_index),
                            "vertical",
                        ));
                    }

                    let start_left = request.start.x < min_x;
                    let goal_left = request.goal.x < min_x;
                    let start_right = request.start.x > max_x;
                    let goal_right = request.goal.x > max_x;
                    if !((start_left && goal_right) || (start_right && goal_left)) {
                        return Err(ArtifactDataError::inconsistent_data(
                            scene_id,
                            "proof_axis/start_goal",
                            crate::ArtifactContractLocation::index(obstacle_index),
                            "vertical",
                        ));
                    }
                }
                SeparationAxis::Horizontal => {
                    if (min_x - scene.world_bounds.min.x).abs() > EPSILON
                        || (max_x - scene.world_bounds.max.x).abs() > EPSILON
                    {
                        return Err(ArtifactDataError::inconsistent_data(
                            scene_id,
                            "proof_axis/world_bounds",
                            crate::ArtifactContractLocation::index(obstacle_index),
                            "horizontal",
                        ));
                    }

                    let start_below = request.start.y < min_y;
                    let goal_below = request.goal.y < min_y;
                    let start_above = request.start.y > max_y;
                    let goal_above = request.goal.y > max_y;
                    if !((start_below && goal_above) || (start_above && goal_below)) {
                        return Err(ArtifactDataError::inconsistent_data(
                            scene_id,
                            "proof_axis/start_goal",
                            crate::ArtifactContractLocation::index(obstacle_index),
                            "horizontal",
                        ));
                    }
                }
            }

            Ok(())
        }
    }
}

fn validate_polyline_segment(
    scene: &PolygonScene,
    start: Point2,
    end: Point2,
    scene_id: &str,
) -> Result<(), ArtifactDataError> {
    if !scene.segment_is_walkable(start, end) {
        return Err(ArtifactDataError::inconsistent_data(
            scene_id,
            "witness_path",
            crate::ArtifactContractLocation::NONE,
            format!("{:?}->{:?}", start, end),
        ));
    }

    Ok(())
}

fn polyline_length(path: &[Point2]) -> f64 {
    path.windows(2)
        .map(|pair| pair[0].distance_to(pair[1]))
        .sum()
}

fn polygon_bounds(vertices: &[Point2]) -> (f64, f64, f64, f64) {
    let min_x = vertices
        .iter()
        .map(|vertex| vertex.x)
        .fold(f64::INFINITY, f64::min);
    let max_x = vertices
        .iter()
        .map(|vertex| vertex.x)
        .fold(f64::NEG_INFINITY, f64::max);
    let min_y = vertices
        .iter()
        .map(|vertex| vertex.y)
        .fold(f64::INFINITY, f64::min);
    let max_y = vertices
        .iter()
        .map(|vertex| vertex.y)
        .fold(f64::NEG_INFINITY, f64::max);
    (min_x, max_x, min_y, max_y)
}

#[cfg(test)]
mod tests {
    use super::{PolygonValidationError, load_polygon_scene_pack_from_str};
    use crate::{ArtifactContractError, ArtifactContractLocation, ArtifactDataError};

    #[test]
    fn rejects_self_intersecting_obstacles() {
        let manifest = r#"
pack_id = "polygon-scene-pack-v0-alpha"
format_version = 1

[[scenes]]
scene_id = "self-intersecting"
family = "invalid"
world_bounds = [0.0, 0.0, 10.0, 10.0]
start = [1.0, 1.0]
goal = [9.0, 1.0]
oracle_kind = "exact-path-cost"
expected_cost = 8.0
witness_path = [[1.0, 1.0], [9.0, 1.0]]

[[scenes.obstacles]]
vertices = [[2.0, 7.0], [4.0, 2.0], [8.0, 7.0], [2.0, 4.0], [8.0, 4.0]]
"#;

        let error = load_polygon_scene_pack_from_str(manifest).unwrap_err();
        assert!(matches!(
            error,
            ArtifactDataError::PolygonValidation(PolygonValidationError::SelfIntersection {
                obstacle_index: 0,
                first_edge_start_index: 0,
                second_edge_start_index: 2,
            })
        ));
    }

    #[test]
    fn rejects_overlapping_obstacles() {
        let manifest = r#"
pack_id = "polygon-scene-pack-v0-alpha"
format_version = 1

[[scenes]]
scene_id = "overlapping-obstacles"
family = "invalid"
world_bounds = [0.0, 0.0, 10.0, 10.0]
start = [1.0, 1.0]
goal = [9.0, 1.0]
oracle_kind = "exact-path-cost"
expected_cost = 8.0
witness_path = [[1.0, 1.0], [9.0, 1.0]]

[[scenes.obstacles]]
vertices = [[2.0, 2.0], [5.0, 2.0], [5.0, 5.0], [2.0, 5.0]]

[[scenes.obstacles]]
vertices = [[4.0, 3.0], [7.0, 3.0], [7.0, 6.0], [4.0, 6.0]]
"#;

        let error = load_polygon_scene_pack_from_str(manifest).unwrap_err();
        assert!(
            error.to_string().contains("must be disjoint"),
            "unexpected error: {error}"
        );
    }

    #[test]
    fn rejects_invalid_exact_path_cost_oracles() {
        let manifest = r#"
pack_id = "polygon-scene-pack-v0-alpha"
format_version = 1

[[scenes]]
scene_id = "wrong-cost"
family = "invalid"
world_bounds = [0.0, 0.0, 10.0, 10.0]
start = [1.0, 1.0]
goal = [9.0, 1.0]
oracle_kind = "exact-path-cost"
expected_cost = 7.0
witness_path = [[1.0, 1.0], [9.0, 1.0]]
"#;

        let error = load_polygon_scene_pack_from_str(manifest).unwrap_err();
        assert!(matches!(
            error,
            ArtifactDataError::Contract(contract)
                if *contract == ArtifactContractError::InconsistentData {
                artifact: "wrong-cost".into(),
                field: "witness_path/expected_cost".into(),
                location: ArtifactContractLocation::NONE,
                value: "8".into(),
            }
        ));
    }

    #[test]
    fn rejects_invalid_boundary_separator_proofs() {
        let manifest = r#"
pack_id = "polygon-scene-pack-v0-alpha"
format_version = 1

[[scenes]]
scene_id = "bad-proof"
family = "invalid"
world_bounds = [0.0, 0.0, 10.0, 10.0]
start = [2.0, 5.0]
goal = [8.0, 5.0]
oracle_kind = "no-path"
proof_kind = "boundary-separator"
proof_obstacle_index = 1
proof_axis = "vertical"

[[scenes.obstacles]]
vertices = [[4.0, 0.0], [6.0, 0.0], [6.0, 10.0], [4.0, 10.0]]
"#;

        let error = load_polygon_scene_pack_from_str(manifest).unwrap_err();
        assert!(matches!(
            error,
            ArtifactDataError::Contract(contract)
                if *contract == ArtifactContractError::InvalidReference {
                artifact: "bad-proof".into(),
                field: "proof_obstacle_index".into(),
                location: ArtifactContractLocation::index(1),
                value: "1".into(),
            }
        ));
    }
}