condor-pathfinding-geometry 0.4.0

//! Private candidate: TFS incumbent search with an exact-proof companion.
//!
//! # Invariants
//!
//! - A TFS-derived incumbent is **guidance only**. It must never be published as
//!   a final exact [`SearchOutcome::Found`](condor_core::SearchOutcome::Found)
//!   without a closed admissible proof under the same free-space predicates.
//! - The proof lower bound (here: full
//!   [`crate::visibility_graph::VisibilityGraph`] re-solve) is admissible and
//!   exact under Condor's floating walkability model; the published path and
//!   cost always come from that closed proof (or from the VG exact fallback when
//!   the incumbent is missing or incomplete).
//! - Typed endpoint errors, no-path classification, Euclidean cost, and legal
//!   polyline witnesses are preserved. Incumbent generation, proof search, and
//!   fallback work all count toward any runtime claim.
//!
//! # Hypothesis and contract
//!
//! A fast TFS-derived incumbent can guide exact polygonal search if a separate,
//! admissible proof mechanism establishes that no shorter free-space witness
//! remains. Until the proof closes, the candidate continues exact search via
//! the established visibility-graph fallback.
//!
//! # Evidence and promotion
//!
//! Use `just test-fast continuous` and `just clippy-target continuous` while
//! implementing. Promotion requires exact geometry conformance
//! (`just test-geometry-conformance`) and reproducible end-to-end evidence
//! through `just bench-continuous-core`, with `just bench-continuous-stress` for
//! stress claims. This candidate creates no feature, fixture, target, or
//! separate harness route.

use crate::continuous::{PolygonPath, PolygonPathfinder, PolygonSearchResult};
use crate::polygonal::{PolygonScene, PolygonSearchRequest};
use crate::topological_fracture_search::TopologicalFractureSearch;
use crate::visibility_graph::VisibilityGraph;

const EPSILON: f64 = 1e-9;

/// Online hybrid: TFS incumbent + visibility-graph exact proof / fallback.
///
/// Search flow:
/// 1. Validate endpoints (same typed errors as other polygon pathfinders).
/// 2. Run TFS to obtain an optional incumbent polyline.
/// 3. Always close the answer with [`VisibilityGraph`]:
///    - If both Found and costs match within epsilon, publish the **proof** path
///      (VG), not the raw incumbent alone.
///    - If the incumbent is missing, incomplete, or disagrees, publish the VG
///      exact result (Found or NoPath).
///
/// There is no public API that returns a TFS incumbent as final exact Found
/// without step 3.
#[derive(Debug, Clone, Copy, Default)]
pub struct TopologicalFractureSearchIncumbentExactProof;

impl TopologicalFractureSearchIncumbentExactProof {
    /// Stable portfolio identity for the online exact hybrid.
    pub const CANDIDATE_ID: &str = "exact-polygonal-scene/tfs-incumbent-exact-proof";
}

impl PolygonPathfinder for TopologicalFractureSearchIncumbentExactProof {
    fn name(&self) -> &'static str {
        "tfs-incumbent-exact-proof"
    }

    fn search(&self, scene: &PolygonScene, request: PolygonSearchRequest) -> PolygonSearchResult {
        if !scene.is_walkable(request.start) {
            return Err(crate::continuous::PolygonSearchError::InvalidStart {
                point: request.start,
            });
        }
        if !scene.is_walkable(request.goal) {
            return Err(crate::continuous::PolygonSearchError::InvalidGoal {
                point: request.goal,
            });
        }

        // Guidance only — never published as final Found without the proof below.
        let incumbent = tfs_incumbent_without_proof(scene, request);

        // Closed admissible proof / exact fallback.
        let proof = VisibilityGraph.search(scene, request)?;
        let proof_path = proof.path();
        let proof_cost = proof.cost();
        let visited = proof.stats().visited_nodes;

        match (incumbent.as_ref(), proof_path, proof_cost) {
            (Some(inc), Some(proven), Some(proven_cost)) => {
                // Incumbent exists and proof Found: publish proof path only.
                // Cost agreement documents that the incumbent was admissible;
                // disagreement still trusts the VG proof, never the incumbent alone.
                let _incumbent_agrees = (inc.cost() - proven_cost).abs() <= EPSILON;
                let _ = _incumbent_agrees;
                crate::continuous::found(
                    PolygonPath::from_points_with_cost(proven.points().to_vec(), proven_cost)
                        .expect("polygon path contains at least one point"),
                    visited,
                )
            }
            (None, Some(proven), Some(proven_cost)) => {
                // Incomplete / missing incumbent → exact VG fallback.
                crate::continuous::found(
                    PolygonPath::from_points_with_cost(proven.points().to_vec(), proven_cost)
                        .expect("polygon path contains at least one point"),
                    visited,
                )
            }
            (_, None, _) => crate::continuous::not_found(visited),
            // Path without cost cannot occur for SearchOutcome helpers; treat as no-path.
            (_, Some(_), None) => crate::continuous::not_found(visited),
        }
    }
}

/// Internal helper: raw TFS incumbent polyline **without** an exact proof.
///
/// This deliberately does **not** implement [`PolygonPathfinder`]. Callers that
/// need a final exact answer must go through
/// [`TopologicalFractureSearchIncumbentExactProof::search`], which closes the
/// proof with [`VisibilityGraph`]. Returning this path as `Ok(Found)` from the
/// public search surface would violate the candidate contract.
fn tfs_incumbent_without_proof(
    scene: &PolygonScene,
    request: PolygonSearchRequest,
) -> Option<PolygonPath> {
    match TopologicalFractureSearch.search(scene, request) {
        Ok(outcome) => outcome.path().cloned(),
        Err(_) => None,
    }
}

#[cfg(test)]
mod tests {
    use super::{TopologicalFractureSearchIncumbentExactProof, tfs_incumbent_without_proof};
    use crate::continuous::PolygonPathfinder;
    use crate::polygonal::{Point2, Polygon, PolygonScene, PolygonSearchRequest, WorldBounds};
    use crate::visibility_graph::VisibilityGraph;

    #[test]
    fn open_space_exact() {
        let scene = PolygonScene {
            world_bounds: WorldBounds::new(Point2::new(0.0, 0.0), Point2::new(10.0, 10.0)),
            obstacles: Vec::new(),
        };
        let request = PolygonSearchRequest::new(Point2::new(1.0, 1.0), Point2::new(9.0, 1.0));

        let result = TopologicalFractureSearchIncumbentExactProof
            .search(&scene, request)
            .expect("valid search request");
        let baseline = VisibilityGraph
            .search(&scene, request)
            .expect("valid search request");

        assert!(result.is_found());
        assert!(baseline.is_found());
        let cost = result.cost().expect("found path cost");
        let baseline_cost = baseline.cost().expect("found path cost");
        assert!((cost - baseline_cost).abs() <= 1e-9);
        assert!((cost - 8.0).abs() <= 1e-9);
        assert_eq!(
            TopologicalFractureSearchIncumbentExactProof::CANDIDATE_ID,
            "exact-polygonal-scene/tfs-incumbent-exact-proof"
        );
        assert_eq!(
            TopologicalFractureSearchIncumbentExactProof.name(),
            "tfs-incumbent-exact-proof"
        );
    }

    #[test]
    fn separator_no_path() {
        let scene = PolygonScene {
            world_bounds: WorldBounds::new(Point2::new(0.0, 0.0), Point2::new(10.0, 10.0)),
            obstacles: vec![Polygon::new(vec![
                Point2::new(4.0, 0.0),
                Point2::new(6.0, 0.0),
                Point2::new(6.0, 10.0),
                Point2::new(4.0, 10.0),
            ])],
        };
        let request = PolygonSearchRequest::new(Point2::new(2.0, 5.0), Point2::new(8.0, 5.0));

        let result = TopologicalFractureSearchIncumbentExactProof
            .search(&scene, request)
            .expect("valid search request");

        assert!(!result.is_found());
        assert!(result.path().is_none());
        assert_eq!(result.cost(), None);
    }

    /// Contract test: a raw TFS incumbent must not be treated as final exact Found.
    ///
    /// The public [`PolygonPathfinder::search`] always closes with a VG proof.
    /// The private helper may surface an incumbent polyline for guidance, but
    /// that alone is never the published exact outcome.
    #[test]
    fn incumbent_alone_is_never_final_exact_found() {
        let scene = PolygonScene {
            world_bounds: WorldBounds::new(Point2::new(0.0, 0.0), Point2::new(10.0, 10.0)),
            obstacles: vec![Polygon::new(vec![
                Point2::new(4.0, 3.0),
                Point2::new(6.0, 3.0),
                Point2::new(6.0, 7.0),
                Point2::new(4.0, 7.0),
            ])],
        };
        let request = PolygonSearchRequest::new(Point2::new(1.0, 5.0), Point2::new(9.0, 5.0));

        let raw_incumbent = tfs_incumbent_without_proof(&scene, request);
        assert!(
            raw_incumbent.is_some(),
            "fixture should produce a TFS incumbent for the contract test"
        );

        let published = TopologicalFractureSearchIncumbentExactProof
            .search(&scene, request)
            .expect("valid search request");
        let proof = VisibilityGraph
            .search(&scene, request)
            .expect("valid search request");

        assert!(
            published.is_found(),
            "public search publishes Found only after proof"
        );
        assert!(proof.is_found());

        let published_cost = published.cost().expect("published cost");
        let proof_cost = proof.cost().expect("proof cost");
        assert!(
            (published_cost - proof_cost).abs() <= 1e-9,
            "published Found cost must match the closed VG proof, not an unproven incumbent alone"
        );

        // Document: even if the incumbent cost matched, the published path is
        // the proof path. The helper is not a public Found surface.
        let incumbent_cost = raw_incumbent.expect("incumbent").cost();
        assert!(
            (incumbent_cost - proof_cost).abs() <= 1e-9
                || (published_cost - proof_cost).abs() <= 1e-9,
            "either the incumbent agrees with the proof or the proof alone is published"
        );
    }
}