voronoi_go/clipping/

validate.rs

//! The structural check that turns a malformed segment list into a test
//! failure instead of a hang.
//!
//! Several algorithms walk a shape's list until they reach a particular
//! terminator. If the list is broken they never reach it, and the symptom is a
//! process that stops responding rather than one that reports an error. The
//! bounded walks catch that at the point of use; this catches it at the point of
//! damage, which is where it can still be diagnosed.
//!
//! [`ClippingGraph::validate`] runs after **every** mutating operation under
//! `cfg(debug_assertions)`, and the alive zone's own validation delegates to it.
//! The one exception is the inside of a compound operation, where the check
//! would be quadratic and says nothing the check at the end of it does not —
//! [`ClippingGraph::defer_validation`] is where that is written down.

use std::collections::BTreeSet;

use thiserror::Error;

use super::graph::ClippingGraph;
use super::segment::SegId;
use super::shape::{Closure, ShapeId};

/// Something the clipping structure guarantees, found not to hold.
///
/// Every variant is a bug in whatever last mutated the structure. None of them
/// is reachable from user input: a move that cannot be played is rejected long
/// before it reaches this layer.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum StructureError {
    /// A list links to a segment that is not in the arena.
    #[error("shape {shape:?} links to segment {segment:?}, which is not in the arena")]
    DanglingSegment {
        /// The shape whose list holds the broken link.
        shape: ShapeId,
        /// The segment that is not there.
        segment: SegId,
    },

    /// A segment appears in the list of a shape that does not own it.
    #[error("segment {segment:?} is in shape {shape:?}'s list but belongs to {owner:?}")]
    WrongParent {
        /// The shape whose list it turned up in.
        shape: ShapeId,
        /// The segment.
        segment: SegId,
        /// The shape it says it belongs to.
        owner: ShapeId,
    },

    /// The same segment is reachable from two shapes' heads.
    #[error("segment {segment:?} is in more than one shape's list")]
    SegmentInTwoLists {
        /// The segment.
        segment: SegId,
    },

    /// `a.next == b` without `b.prev == a`, or the mirror of that.
    #[error("segments {from:?} and {to:?} do not agree about the link between them")]
    AsymmetricLink {
        /// The segment whose `next` points at `to`.
        from: SegId,
        /// The segment whose `prev` should point back at `from`.
        to: SegId,
    },

    /// Walking from a shape's head did not return to it within the shape's
    /// recorded segment count — the list has a cycle that misses the head, or
    /// the count is wrong.
    #[error("walking shape {shape:?}'s list did not return to its head within {bound} segments")]
    WalkOverran {
        /// The shape.
        shape: ShapeId,
        /// The count the walk was bounded by.
        bound: usize,
    },

    /// A shape's recorded segment count is not the length of its list.
    #[error("shape {shape:?} records {recorded} segments but its list holds {walked}")]
    CountMismatch {
        /// The shape.
        shape: ShapeId,
        /// What it says.
        recorded: usize,
        /// What the walk found.
        walked: usize,
    },

    /// Offsets do not ascend round the list, allowing for one wraparound — and
    /// for an open shape, allowing for it only at the wrap itself.
    #[error("shape {shape:?}'s segment offsets are not in order")]
    OffsetsOutOfOrder {
        /// The shape.
        shape: ShapeId,
    },

    /// A segment's recorded offset is not the offset of the point it starts at.
    #[error("segment {segment:?}'s offset is not the offset of its start point")]
    OffsetDisagreesWithPoint {
        /// The segment.
        segment: SegId,
    },

    /// A live segment is missing from the shared-start index.
    #[error("segment {segment:?} is not indexed under the point it starts at")]
    MissingFromIndex {
        /// The segment.
        segment: SegId,
    },

    /// The shared-start index refers to a segment that is not in the arena.
    #[error("the shared-start index refers to segment {segment:?}, which is not in the arena")]
    DanglingIndexEntry {
        /// The segment that is not there.
        segment: SegId,
    },

    /// The shared-start index files a segment under a point it does not start
    /// at.
    #[error("segment {segment:?} is indexed under a point it does not start at")]
    MisfiledIndexEntry {
        /// The segment.
        segment: SegId,
    },

    /// The shared-start index lists the same segment twice under one point.
    #[error("the shared-start index lists segment {segment:?} twice under one point")]
    DuplicateIndexEntry {
        /// The segment.
        segment: SegId,
    },

    /// A point is in the shared-start index with nothing starting there.
    #[error("the shared-start index holds a point with no segments")]
    EmptyIndexEntry,

    /// A segment is alive in the arena but no shape's list reaches it.
    #[error("segment {segment:?} is alive but no shape's list reaches it")]
    UnreachableSegment {
        /// The segment.
        segment: SegId,
    },

    /// The index holds a different number of segments from the arena.
    #[error("the shared-start index holds {indexed} segments but {live} are alive")]
    IndexSizeMismatch {
        /// How many the index holds.
        indexed: usize,
        /// How many are in the arena.
        live: usize,
    },

    /// A segment is marked as covered by a shape that no longer exists, which
    /// would keep it invisible for ever.
    #[error("segment {segment:?} is covered by shape {shape:?}, which no longer exists")]
    CoveredByMissingShape {
        /// The segment.
        segment: SegId,
        /// The shape that is gone.
        shape: ShapeId,
    },

    /// A shape is marked as covering part of its own outline.
    #[error("shape {shape:?} covers part of its own outline")]
    ShapeCoversItself {
        /// The shape.
        shape: ShapeId,
    },
}

impl ClippingGraph {
    /// Checks every invariant the structure is supposed to hold.
    ///
    /// Specifically: that each shape's list is circular and `prev`/`next`
    /// symmetric, that walking it from the head returns to the head in exactly
    /// the recorded number of steps, that offsets ascend round it allowing for
    /// one wraparound, that every segment belongs to the shape whose list it is
    /// in and agrees with the point it starts at, that nothing is marked as
    /// covered by a shape that has gone, and that the segment arena and the
    /// shared-start index describe the same set of segments **in both
    /// directions**.
    ///
    /// # Errors
    ///
    /// Returns the first invariant found not to hold. Any of them means an
    /// earlier mutation left the structure corrupt.
    pub fn validate(&self) -> Result<(), StructureError> {
        let mut reachable: BTreeSet<SegId> = BTreeSet::new();
        for shape in self.shapes.keys() {
            self.validate_shape(*shape, &mut reachable)?;
        }

        // The other direction: nothing alive may be stranded outside every
        // list. Together with the walks above, the segment arena and the set of
        // reachable segments are then the same set.
        for (id, _) in self.arena.iter() {
            if !reachable.contains(&id) {
                return Err(StructureError::UnreachableSegment { segment: id });
            }
        }

        self.validate_index()
    }

    /// Walks one shape's list, checking everything that is true of a segment
    /// and of its place in the list. Records every segment it reaches.
    fn validate_shape(
        &self,
        shape_id: ShapeId,
        reachable: &mut BTreeSet<SegId>,
    ) -> Result<(), StructureError> {
        let Some(shape) = self.shapes.get(&shape_id) else {
            return Ok(());
        };
        let Some(head) = shape.head else {
            if shape.count != 0 {
                return Err(StructureError::CountMismatch {
                    shape: shape_id,
                    recorded: shape.count,
                    walked: 0,
                });
            }
            return Ok(());
        };

        let mut current = head;
        let mut walked = 0_usize;
        let mut decreases = 0_usize;
        let mut decrease_is_the_wrap = false;

        loop {
            let segment = self
                .arena
                .get(current)
                .ok_or(StructureError::DanglingSegment {
                    shape: shape_id,
                    segment: current,
                })?;

            if segment.parent != shape_id {
                return Err(StructureError::WrongParent {
                    shape: shape_id,
                    segment: current,
                    owner: segment.parent,
                });
            }
            if !reachable.insert(current) {
                return Err(StructureError::SegmentInTwoLists { segment: current });
            }
            self.validate_links(shape_id, current)?;

            // Compared by bits, because the offset is a pure function of the
            // point and recomputing it must land on the very same value.
            // Anything else means the point was changed underneath the offset,
            // or the segment was filed on the wrong shape.
            if segment.start.to_bits() != shape.kind.point_to_offset(segment.point).to_bits() {
                return Err(StructureError::OffsetDisagreesWithPoint { segment: current });
            }
            if !self
                .shared_starts
                .segments(segment.point)
                .contains(&current)
            {
                return Err(StructureError::MissingFromIndex { segment: current });
            }

            for covering in &segment.overlapping {
                if *covering == shape_id {
                    return Err(StructureError::ShapeCoversItself { shape: shape_id });
                }
                if !self.shapes.contains_key(covering) {
                    return Err(StructureError::CoveredByMissingShape {
                        segment: current,
                        shape: *covering,
                    });
                }
            }

            walked += 1;
            if walked > shape.count {
                return Err(StructureError::WalkOverran {
                    shape: shape_id,
                    bound: shape.count,
                });
            }

            let next_start = self
                .arena
                .get(segment.next)
                .map_or(segment.start, |next| next.start);
            let wraps = segment.next == head;
            if segment.start > next_start {
                decreases += 1;
                decrease_is_the_wrap = wraps;
            }

            current = segment.next;
            if wraps {
                break;
            }
        }

        if walked != shape.count {
            return Err(StructureError::CountMismatch {
                shape: shape_id,
                recorded: shape.count,
                walked,
            });
        }
        // Offsets ascend all the way round, dropping back only once — at the
        // wrap. An open shape's list does not wrap in the parameter, so the one
        // drop has to be the link from its tail back to its head, which is what
        // keeps the head holding the lowest offset.
        if decreases > 1 {
            return Err(StructureError::OffsetsOutOfOrder { shape: shape_id });
        }
        if matches!(shape.closure, Closure::Open) && decreases == 1 && !decrease_is_the_wrap {
            return Err(StructureError::OffsetsOutOfOrder { shape: shape_id });
        }

        Ok(())
    }

    /// Checks that the segment's neighbours point back at it.
    fn validate_links(&self, shape_id: ShapeId, current: SegId) -> Result<(), StructureError> {
        let segment = self
            .arena
            .get(current)
            .ok_or(StructureError::DanglingSegment {
                shape: shape_id,
                segment: current,
            })?;

        let next = self
            .arena
            .get(segment.next)
            .ok_or(StructureError::DanglingSegment {
                shape: shape_id,
                segment: segment.next,
            })?;
        if next.prev != current {
            return Err(StructureError::AsymmetricLink {
                from: current,
                to: segment.next,
            });
        }

        let previous = self
            .arena
            .get(segment.prev)
            .ok_or(StructureError::DanglingSegment {
                shape: shape_id,
                segment: segment.prev,
            })?;
        if previous.next != current {
            return Err(StructureError::AsymmetricLink {
                from: segment.prev,
                to: current,
            });
        }

        Ok(())
    }

    /// Checks the shared-start index against the arena: every entry names a
    /// live segment, filed under the point that segment starts at, exactly
    /// once, and the two hold the same number of segments.
    fn validate_index(&self) -> Result<(), StructureError> {
        for (key, segments) in self.shared_starts.iter() {
            let [_, ..] = segments else {
                return Err(StructureError::EmptyIndexEntry);
            };
            let mut distinct = BTreeSet::new();
            for id in segments {
                if !distinct.insert(*id) {
                    return Err(StructureError::DuplicateIndexEntry { segment: *id });
                }
                let segment = self
                    .arena
                    .get(*id)
                    .ok_or(StructureError::DanglingIndexEntry { segment: *id })?;
                if segment.point.key() != key {
                    return Err(StructureError::MisfiledIndexEntry { segment: *id });
                }
            }
        }

        let indexed = self.shared_starts.len();
        if indexed != self.arena.len() {
            return Err(StructureError::IndexSizeMismatch {
                indexed,
                live: self.arena.len(),
            });
        }

        Ok(())
    }

    /// Panics if the structure is corrupt, in a debug build.
    ///
    /// Called at the end of every mutating operation. In a release build the
    /// check compiles away, and while a compound mutation is in progress it is
    /// deferred — see [`ClippingGraph::defer_validation`].
    pub(super) fn debug_validate(&self) {
        if cfg!(debug_assertions) && self.deferred == 0 {
            if let Err(error) = self.validate() {
                panic!("the clipping structure is corrupt: {error}");
            }
        }
    }

    /// Suspends the per-mutation check until the matching
    /// [`ClippingGraph::resume_validation`].
    ///
    /// One carve is a shape, a few segment insertions per shape already on the
    /// board, and a covered run marked on each of them — every one of which is a
    /// mutating operation that checks the *whole* structure. That makes a carve
    /// quadratic in the size of the board for no added coverage: the caller
    /// validates in full the moment the compound operation is complete, and
    /// until then the structure is mid-edit rather than settled.
    ///
    /// What is given up is the resolution of the report — damage is attributed
    /// to the carve rather than to the insertion within it. Nothing goes
    /// unchecked, and the deferral cannot outlive one operation:
    /// [`AliveZone::compound`](crate::AliveZone) resumes from a guard's `Drop`.
    pub(crate) fn defer_validation(&mut self) {
        if cfg!(debug_assertions) {
            self.deferred += 1;
        }
    }

    /// Ends one [`ClippingGraph::defer_validation`]. Deliberately does not
    /// validate: the caller does, once, with everything it owns restored too.
    pub(crate) fn resume_validation(&mut self) {
        if cfg!(debug_assertions) {
            self.deferred = self.deferred.saturating_sub(1);
        }
    }

    /// Whether the per-mutation check is deferred right now.
    ///
    /// Only the tests ask, and what they ask about is the guard: every deferral
    /// is resumed from a `Drop`, so this is false everywhere else.
    #[cfg(test)]
    pub(crate) const fn validation_is_deferred(&self) -> bool {
        self.deferred > 0
    }
}

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

    use super::StructureError;
    use crate::Point;
    use crate::clipping::{ClippingGraph, SegId, ShapeId, ShapeKind};

    const BOARD: f64 = 20.0;

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

    /// A graph with a stone's dead zone clipped against the left edge, so that
    /// there is a real structure to break.
    fn populated() -> (ClippingGraph, ShapeId, ShapeId) {
        let mut graph = ClippingGraph::new(BOARD);
        let edge = graph.shape_ids().next().unwrap();
        let center = p(2.0, 10.0);
        let zone = graph.add_dead_zone(center);
        let circle = ShapeKind::dead_zone(center).circle().unwrap();

        let crossing = graph.intersect(edge, circle).unwrap();
        let edge_covered = graph.insert_or_get_existing(edge, crossing.entry).unwrap();
        let zone_uncovered = graph.insert_or_get_existing(zone, crossing.entry).unwrap();
        let edge_uncovered = graph.insert_or_get_existing(edge, crossing.exit).unwrap();
        let zone_covered = graph.insert_or_get_existing(zone, crossing.exit).unwrap();
        graph.add_overlapping(edge_covered, edge_uncovered, zone);
        graph.add_overlapping(zone_covered, zone_uncovered, edge);

        assert!(graph.validate().is_ok());
        (graph, edge, zone)
    }

    fn head_of(graph: &ClippingGraph, shape: ShapeId) -> SegId {
        graph.shape(shape).unwrap().head().unwrap()
    }

    #[test]
    fn a_healthy_structure_validates() {
        let (graph, _, _) = populated();
        assert_eq!(graph.validate(), Ok(()));
    }

    #[test]
    fn an_asymmetric_link_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let second = graph.segment(head).unwrap().next();
        let third = graph.segment(second).unwrap().next();

        // `head.next` now skips a segment, but nothing's `prev` was updated.
        graph.arena.get_mut(head).unwrap().next = third;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::AsymmetricLink { .. })
        ));
    }

    #[test]
    fn a_self_loop_part_way_round_the_list_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let second = graph.segment(head).unwrap().next();

        // The walk would spin here for ever. Symmetry is what makes a circular
        // list come back round at all, so this is caught as the broken link it
        // is, before the bound is ever reached.
        graph.arena.get_mut(second).unwrap().next = second;
        graph.arena.get_mut(second).unwrap().prev = second;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::AsymmetricLink { .. })
        ));
    }

    #[test]
    fn a_count_larger_than_the_list_is_caught() {
        let (mut graph, edge, _) = populated();
        graph.shapes.get_mut(&edge).unwrap().count += 1;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::CountMismatch { .. })
        ));
    }

    #[test]
    fn a_count_smaller_than_the_list_is_caught() {
        let (mut graph, edge, _) = populated();
        graph.shapes.get_mut(&edge).unwrap().count -= 1;

        // The count is what every walk is bounded by, so a count that is too
        // small is the same failure as a list that never terminates.
        assert!(matches!(
            graph.validate(),
            Err(StructureError::WalkOverran { .. })
        ));
    }

    #[test]
    fn offsets_out_of_order_are_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let second = graph.segment(head).unwrap().next();
        let third = graph.segment(second).unwrap().next();
        let fourth = graph.segment(third).unwrap().next();

        // Swap two neighbours' places in the list without moving their offsets,
        // which is exactly what a mis-aimed insertion would do. Every link
        // stays symmetric; only the ordering breaks.
        graph.arena.get_mut(head).unwrap().next = third;
        graph.arena.get_mut(third).unwrap().prev = head;
        graph.arena.get_mut(third).unwrap().next = second;
        graph.arena.get_mut(second).unwrap().prev = third;
        graph.arena.get_mut(second).unwrap().next = fourth;
        graph.arena.get_mut(fourth).unwrap().prev = second;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::OffsetsOutOfOrder { .. })
        ));
    }

    #[test]
    fn an_open_shape_whose_head_is_not_its_lowest_offset_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let second = graph.segment(head).unwrap().next();

        // Rotate the head forwards. The list is still perfectly circular; it is
        // only the edge's openness that this breaks, because the wrap link now
        // falls in the middle of the run of offsets.
        graph.shapes.get_mut(&edge).unwrap().head = Some(second);

        assert!(matches!(
            graph.validate(),
            Err(StructureError::OffsetsOutOfOrder { .. })
        ));
    }

    #[test]
    fn a_segment_missing_from_the_index_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let point = graph.segment(head).unwrap().point();

        graph.shared_starts.remove(point, head);

        assert!(matches!(
            graph.validate(),
            Err(StructureError::MissingFromIndex { .. })
        ));
    }

    #[test]
    fn an_index_entry_pointing_at_nothing_is_caught() {
        let (mut graph, _, _) = populated();
        graph.shared_starts.add(p(3.0, 3.0), SegId::new(4_000));

        assert!(matches!(
            graph.validate(),
            Err(StructureError::DanglingIndexEntry { .. })
        ));
    }

    #[test]
    fn an_index_entry_filed_under_the_wrong_point_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.shared_starts.add(p(3.0, 3.0), head);

        assert!(matches!(
            graph.validate(),
            Err(StructureError::MisfiledIndexEntry { .. })
        ));
    }

    #[test]
    fn a_segment_no_shape_can_reach_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        let second = graph.segment(head).unwrap().next();
        let third = graph.segment(second).unwrap().next();

        // Unlink one segment without deleting it.
        graph.arena.get_mut(head).unwrap().next = third;
        graph.arena.get_mut(third).unwrap().prev = head;
        graph.shapes.get_mut(&edge).unwrap().count -= 1;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::UnreachableSegment { .. })
        ));
    }

    #[test]
    fn a_segment_in_the_wrong_shapes_list_is_caught() {
        let (mut graph, edge, zone) = populated();
        let head = head_of(&graph, edge);
        graph.arena.get_mut(head).unwrap().parent = zone;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::WrongParent { .. })
        ));
    }

    #[test]
    fn an_offset_that_does_not_match_its_point_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.arena.get_mut(head).unwrap().start += 1.0;

        assert!(matches!(
            graph.validate(),
            Err(StructureError::OffsetDisagreesWithPoint { .. })
        ));
    }

    #[test]
    fn a_cover_by_a_shape_that_has_gone_is_caught() {
        let (mut graph, _, zone) = populated();
        // Take the dead zone away without letting the edge forget it first.
        graph.shapes.remove(&zone);

        assert!(matches!(
            graph.validate(),
            Err(StructureError::CoveredByMissingShape { .. })
        ));
    }

    #[test]
    fn a_shape_covering_itself_is_caught() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.arena.get_mut(head).unwrap().overlapping.insert(edge);

        assert!(matches!(
            graph.validate(),
            Err(StructureError::ShapeCoversItself { .. })
        ));
    }

    #[test]
    #[cfg(debug_assertions)]
    #[should_panic(expected = "the clipping structure is corrupt")]
    fn a_mutation_on_a_corrupt_structure_panics() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.shapes.get_mut(&edge).unwrap().count += 1;

        // The next mutating operation validates, and finds the damage.
        graph.delete_segment(head);
    }

    #[test]
    #[cfg(debug_assertions)]
    fn a_deferred_mutation_does_not_check_and_the_damage_is_still_there() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.shapes.get_mut(&edge).unwrap().count += 1;

        // The same mutation the test above panics on, inside a deferral. It has
        // to return: the check is what the deferral suspends.
        graph.defer_validation();
        graph.delete_segment(head);
        graph.resume_validation();

        // Nothing was swallowed — the deferral moves the check, and an explicit
        // one still finds what the per-mutation check would have.
        assert!(graph.validate().is_err());
    }

    #[test]
    #[cfg(debug_assertions)]
    fn deferrals_nest_so_an_inner_resume_cannot_turn_the_check_back_on() {
        let (mut graph, edge, _) = populated();
        let head = head_of(&graph, edge);
        graph.shapes.get_mut(&edge).unwrap().count += 1;

        graph.defer_validation();
        graph.defer_validation();
        graph.resume_validation();

        // The outer deferral is still open, so the mutation that panics with
        // the check on returns instead.
        graph.delete_segment(head);

        graph.resume_validation();
        assert_eq!(graph.deferred, 0, "the deferrals balanced out");
    }
}