voronoi_go/alive_zone/

validate.rs

//! What the alive zone guarantees on top of the clipping structure, and the
//! check that says so.
//!
//! [`AliveZone::validate`] delegates to the clipping layer's own validator and
//! then adds the two things the alive zone itself owns: the map from a stone to
//! the dead zone carved for it, and the forced-eye set. It runs after **every**
//! mutating operation under `cfg(debug_assertions)`, so a bug is reported where
//! the damage was done rather than where a later walk falls over it.

use std::collections::BTreeSet;

use thiserror::Error;

use crate::clipping::{ShapeId, ShapeKind, StructureError};
use crate::{Point, StoneId};

use super::AliveZone;

/// Something the alive zone guarantees, found not to hold.
///
/// Every variant is a bug in whatever last mutated the zone. None of them is
/// reachable from user input: an unplayable move is rejected long before it
/// reaches this layer.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum ZoneError {
    /// The clipping structure underneath is corrupt.
    #[error("the clipping structure is corrupt: {0}")]
    Structure(#[from] StructureError),

    /// A stone's dead zone names a shape that is no longer there.
    #[error("stone {stone}'s dead zone names shape {shape:?}, which is not in the graph")]
    MissingDeadZone {
        /// The stone.
        stone: StoneId,
        /// The shape it names.
        shape: ShapeId,
    },

    /// A stone's dead zone names a shape that is not a dead zone.
    #[error("stone {stone}'s dead zone names shape {shape:?}, which is a board edge")]
    NotADeadZone {
        /// The stone.
        stone: StoneId,
        /// The shape it names.
        shape: ShapeId,
    },

    /// Two stones name the same dead zone, so reclaiming either would take the
    /// other's playable area with it.
    #[error("shape {shape:?} is named as the dead zone of more than one stone")]
    SharedDeadZone {
        /// The shape.
        shape: ShapeId,
    },

    /// A dead zone is clipping the playable area that no stone can name, so
    /// nothing can ever reclaim it.
    ///
    /// A temporary circle is exempt while the
    /// [`with_temp_circle`](AliveZone::with_temp_circle) call that carved it is
    /// still running — the zone names it itself for exactly that long, which is
    /// what lets the check stay this strict everywhere else.
    #[error("shape {shape:?} is a dead zone that no stone names")]
    UnnamedDeadZone {
        /// The shape.
        shape: ShapeId,
    },

    /// A temporary circle names a shape that is not a dead zone in the graph,
    /// so the guard that restores it would have nothing to give back.
    #[error("the temporary circle names shape {shape:?}, which is not a dead zone in the graph")]
    StrandedTempCircle {
        /// The shape it names.
        shape: ShapeId,
    },

    /// A forced eye is filed under a key that is not its own point's.
    #[error("the forced eye at {point:?} is filed under another point's key")]
    MisfiledForcedEye {
        /// The eye.
        point: Point,
    },
}

impl AliveZone {
    /// Checks every invariant the alive zone is supposed to hold.
    ///
    /// The clipping structure first — list circularity, `prev`/`next` symmetry,
    /// offset ordering, and the shared-start index in both directions — then
    /// that stones and dead zones name each other one-for-one, and that every
    /// forced eye is filed under its own point.
    ///
    /// A dead zone carved by a [`AliveZone::with_temp_circle`] call that has not
    /// returned yet counts as named. It has to: the check runs inside that call
    /// as well, and a temporary circle *is* accounted for — by the guard holding
    /// it — for as long as it exists.
    ///
    /// # Errors
    ///
    /// Returns the first invariant found not to hold. Any of them means an
    /// earlier mutation left the zone corrupt.
    pub fn validate(&self) -> Result<(), ZoneError> {
        self.graph.validate()?;

        let mut named: BTreeSet<ShapeId> = BTreeSet::new();
        for shape in &self.temp_circles {
            let shape = *shape;
            let is_dead_zone = self
                .graph
                .shape(shape)
                .is_some_and(|entry| matches!(entry.kind(), ShapeKind::DeadZone(_)));
            if !is_dead_zone {
                return Err(ZoneError::StrandedTempCircle { shape });
            }
            named.insert(shape);
        }

        for (stone, shape) in &self.dead_zones {
            let (stone, shape) = (*stone, *shape);
            let Some(entry) = self.graph.shape(shape) else {
                return Err(ZoneError::MissingDeadZone { stone, shape });
            };
            if !matches!(entry.kind(), ShapeKind::DeadZone(_)) {
                return Err(ZoneError::NotADeadZone { stone, shape });
            }
            if !named.insert(shape) {
                return Err(ZoneError::SharedDeadZone { shape });
            }
        }

        // The other direction. A dead zone nothing names can never be reclaimed,
        // which is exactly the shape a leaked temporary circle would take.
        for (id, shape) in self.graph.shapes() {
            if matches!(shape.kind(), ShapeKind::DeadZone(_)) && !named.contains(&id) {
                return Err(ZoneError::UnnamedDeadZone { shape: id });
            }
        }

        for (key, point) in self.forced_eyes.entries() {
            if point.key() != key {
                return Err(ZoneError::MisfiledForcedEye { point });
            }
        }

        Ok(())
    }

    /// Panics if the zone is corrupt, in a debug build.
    ///
    /// Called at the end of every mutating operation. In a release build the
    /// check compiles away.
    pub(super) fn debug_validate(&self) {
        if cfg!(debug_assertions) {
            if let Err(error) = self.validate() {
                panic!("the alive zone is corrupt: {error}");
            }
        }
    }

    /// Every shape, named by its own geometry, with the exact bits of every
    /// segment offset it carries and what is visible — the comparison a
    /// round trip has to survive.
    ///
    /// Two things are canonicalized away, and both are bookkeeping rather than
    /// structure:
    ///
    /// - **Shape ids.** A reclaimed dead zone that is carved again gets a fresh
    ///   one, so shapes are named by a point on their own outline instead and
    ///   the list is sorted.
    /// - **Where a closed list starts.** The head of a circular list is
    ///   whichever segment happened to be inserted first; deleting it moves the
    ///   head to its successor, so a round trip can leave the list rotated. The
    ///   cyclic order itself is checked by [`AliveZone::validate`], and offsets
    ///   are sorted here.
    ///
    /// Everything else is compared bit for bit. Forced eyes are not part of it:
    /// they are their own set, compared directly.
    #[cfg(test)]
    pub(crate) fn fingerprint(&self) -> Vec<(crate::PointKey, Vec<(u64, bool)>)> {
        let mut shapes: Vec<(crate::PointKey, Vec<(u64, bool)>)> = self
            .graph
            .shape_ids()
            .filter_map(|shape| {
                let kind = self.graph.shape(shape)?.kind();
                let mut segments: Vec<(u64, bool)> = self
                    .graph
                    .node_ids(shape)
                    .into_iter()
                    .filter_map(|id| {
                        let start = self.graph.segment(id)?.start().to_bits();
                        Some((start, self.graph.is_active(id)))
                    })
                    .collect();
                segments.sort_unstable();
                Some((kind.offset_to_point(0.0).key(), segments))
            })
            .collect();
        shapes.sort_unstable();
        shapes
    }
}

#[cfg(test)]
mod tests {
    #![allow(clippy::unwrap_used, clippy::expect_used)]

    use super::ZoneError;
    use crate::alive_zone::AliveZone;
    use crate::clipping::{ShapeId, StructureError};
    use crate::{Point, PointKey, StoneId};

    const BOARD: f64 = 20.0;

    fn p(x: f64, y: f64) -> Point {
        Point::new(x, y)
    }

    /// A shape id that names nothing, made the only way there is: allocate a
    /// shape and take it straight back out again. Shape ids are never reused, so
    /// the id stays dangling.
    fn dangling_shape(zone: &mut AliveZone) -> ShapeId {
        let ghost = zone.graph.add_dead_zone(p(15.0, 15.0));
        let _ = zone.graph.remove_shape(ghost);
        ghost
    }

    fn populated() -> AliveZone {
        let mut zone = AliveZone::new(BOARD);
        zone.remove_circle(StoneId::new(0), p(2.0, 10.0)).unwrap();
        zone.remove_circle(StoneId::new(1), p(3.0, 11.5)).unwrap();
        zone.add_forced_eye(p(9.0, 9.0));
        assert_eq!(zone.validate(), Ok(()));
        zone
    }

    #[test]
    fn a_healthy_zone_validates() {
        assert_eq!(populated().validate(), Ok(()));
    }

    #[test]
    fn corruption_underneath_surfaces_through_the_zone() {
        // The clipping layer tests every way its own structure can break; what
        // matters here is that the zone reports rather than swallows it.
        let error = ZoneError::from(StructureError::EmptyIndexEntry);
        assert!(matches!(error, ZoneError::Structure(_)));
        assert!(error.to_string().starts_with("the clipping structure is"));
    }

    #[test]
    fn a_dead_zone_that_has_gone_is_caught() {
        let mut zone = populated();
        let ghost = dangling_shape(&mut zone);
        zone.dead_zones.insert(StoneId::new(9), ghost);

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::MissingDeadZone { .. })
        ));
    }

    #[test]
    fn a_stone_naming_a_board_edge_is_caught() {
        let mut zone = populated();
        let edge = zone.graph.shape_ids().next().unwrap();
        zone.dead_zones.insert(StoneId::new(9), edge);

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::NotADeadZone { .. })
        ));
    }

    #[test]
    fn two_stones_naming_one_dead_zone_is_caught() {
        let mut zone = populated();
        let shared = *zone.dead_zones.get(&StoneId::new(0)).unwrap();
        zone.dead_zones.insert(StoneId::new(9), shared);

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::SharedDeadZone { .. })
        ));
    }

    #[test]
    fn a_dead_zone_no_stone_names_is_caught() {
        let mut zone = populated();
        // Exactly the shape a leaked temporary circle would take.
        zone.dead_zones.remove(&StoneId::new(0));

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::UnnamedDeadZone { .. })
        ));
    }

    #[test]
    fn a_live_temporary_circle_is_named_by_the_zone_itself() {
        // Carved and named by nothing a stone can reach, and still valid: this
        // is what lets the check stay strict everywhere else.
        let mut zone = populated();
        zone.with_temp_circle(p(9.0, 4.0), |zone| {
            assert_eq!(zone.validate(), Ok(()));
            assert_eq!(zone.temp_circles.len(), 1);
        });
        assert!(zone.temp_circles.is_empty());
        assert_eq!(zone.validate(), Ok(()));
    }

    #[test]
    fn a_temporary_circle_naming_nothing_is_caught() {
        let mut zone = populated();
        let ghost = dangling_shape(&mut zone);
        zone.temp_circles.push(ghost);

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::StrandedTempCircle { .. })
        ));
    }

    #[test]
    fn a_forced_eye_under_the_wrong_key_is_caught() {
        let mut zone = populated();
        zone.forced_eyes
            .by_point
            .insert(PointKey::new(1.0, 1.0), p(4.0, 4.0));

        assert!(matches!(
            zone.validate(),
            Err(ZoneError::MisfiledForcedEye { .. })
        ));
    }

    #[test]
    fn a_panic_out_of_a_compound_operation_puts_the_structure_check_back() {
        // What the guard is for. A carve defers the clipping structure's own
        // per-mutation check for its duration, and a deferral that outlived the
        // operation would silence that check for the rest of the run.
        let mut zone = populated();
        let unwound = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
            zone.compound(|_| panic!("something went wrong mid-carve"));
        }));

        assert!(unwound.is_err());
        assert!(!zone.graph.validation_is_deferred());
    }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "the alive zone is corrupt")]
    fn a_mutation_on_a_corrupt_zone_panics() {
        let mut zone = populated();
        let ghost = dangling_shape(&mut zone);
        zone.dead_zones.insert(StoneId::new(9), ghost);

        // The next mutating operation validates, and finds the damage.
        zone.add_forced_eye(p(1.5, 1.5));
    }
}