voronoi-go 1.0.1

//! The rules, and the board they act on.
//!
//! [`Game`] is the whole of what a headless consumer needs: the stones, the
//! alive zone, the Voronoi diagram, capture resolution, and the delta history
//! that makes every change reversible. Nothing else is in here — no clocks, no
//! players, no komi, no result. Scoring stops at [`Game::territory`], and what a
//! ruleset layers on top of that is the caller's business.
//!
//! A game does end here, though: two passes in a row and it stops taking turns.
//! [`GameStatus`] is that fact and [`GameOverError`] is what a turn played onto
//! an ended game answers. Ending is not scoring — an ended board still answers
//! every query it answered before, and one [`Game::undo_move`] un-ends it.
//!
//! # How a move is made
//!
//! [`Game::try_move`] takes a position that is already placeable and does not
//! snap: an unplaceable position is [`StonePlayError::NotPlaceable`], and a
//! caller that wants the nearest legal position asks
//! [`Game::nearest_living_move`] for it first. Snapping inside the move would
//! quietly turn a mis-aimed click into a different move, which is a decision for
//! whoever is holding the pointer.
//!
//! Resolving a move's captures needs the stone **already on the board**, so
//! [`Game::try_move`] places it as a [`Commit::Transient`] change, asks what
//! died, takes the placement back, and re-applies the whole move as one
//! [`Commit::Turn`] delta carrying the capture list. That is what keeps a move a
//! single delta, and therefore reversible with one [`Game::undo_move`].
//!
//! The placement is taken back by a guard's `Drop`, not by a call written after
//! the question — see `Game::with_transient_stone`. A move that fails half way
//! through would otherwise leave a stone on the board that was never played, and
//! a caught error would hand back a board quietly unfit to keep playing on.
//!
//! # Changes are deltas, and a pop is the exact inverse
//!
//! [`Game::apply_delta`] and [`Game::pop_delta`] are the only things that change
//! the board. A pop undoes an apply step for step in reverse order, down to the
//! bits of the alive zone's segments — `docs/design.md` § "Undo is bit-exact"
//! states the guarantee and the tests below pin it.
//!
//! Four details of that pairing look like bugs and are not:
//!
//! - **A popped stone is deleted, not captured.** It never existed, so it is not
//!   recorded as a capture and no forced eye is left where it stood.
//! - **The status is re-derived, not stored per delta.** Whether the game has
//!   ended, or stands one pass away from it, is a fact about the last two
//!   committed turns, so a pop reads it back off history rather than restoring a
//!   saved copy. That is also what un-ends an ended game.
//! - **Capture counts always credit the placer.** Safe only because
//!   self-capture is illegal and a pass never captures. Both must stay true.
//! - **The Voronoi diagram is dropped on change, never rebuilt on change.** It
//!   is a pure function of the stones, so the first read rebuilds it and no
//!   answer moves; a search that walks through positions it never inspects would
//!   otherwise pay for a triangulation per position.
//!
//! # The cut cache is invalidated from both ends of a delta
//!
//! [`Game`] owns a [`Connectivity`] and, on every change, drops the cached cut
//! statuses around each stone whose presence on the board changed — the placed
//! stone and every captured or restored one. It happens from **both**
//! [`Game::apply_delta`] and [`Game::pop_delta`], and is **not** gated on
//! [`Commit`]: a transient change must not leave a status behind that outlives
//! it.

mod history;
mod validate;

use std::collections::{BTreeMap, BTreeSet};
use std::sync::OnceLock;

use thiserror::Error;

use crate::alive_zone::DeadZoneError;
use crate::connectivity::{BoardEdge, Connectivity, CutError, CutKind};
use crate::geometry::point_is_on_board;
use crate::voronoi::GroupIter;
use crate::{AliveZone, Color, GameDelta, PerColor, Point, Stone, StoneId, Voronoi};

use history::{AppliedDelta, History};

pub use history::Commit;
pub use validate::BoardError;

/// How far along a game is.
///
/// A game ends on two passes in a row and on nothing else. Ending it stops
/// turns: [`Game::try_move`], [`Game::pass`] and [`Game::apply_delta`] all
/// answer [`GameOverError`] and change nothing. It stops nothing else — every
/// query still answers, and [`Game::undo_move`] takes the second pass back and
/// puts the game back to [`GameStatus::NextPassEnds`].
///
/// Ending is not scoring. What the territory is worth once the turns stop is
/// the caller's; this crate stops at [`Game::territory`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum GameStatus {
    /// Moves and passes are both accepted.
    Playing,
    /// The last committed turn was a pass, so the next one would be the second
    /// in a row and would end the game. Moves are still accepted, and a move
    /// disarms it.
    NextPassEnds,
    /// Two passes in a row have been committed. No further turns.
    Ended,
}

impl GameStatus {
    /// Whether the game has stopped taking turns.
    #[must_use]
    pub const fn has_ended(self) -> bool {
        matches!(self, Self::Ended)
    }
}

/// A turn played onto a game that has already ended.
///
/// The game is left exactly as it was. Answered by [`Game::try_move`],
/// [`Game::pass`] and [`Game::apply_delta`], and by nothing else: an ended game
/// is not a closed object, only one that has stopped taking turns. Queries all
/// still answer, and [`Game::undo_move`] takes the last pass back.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
#[error("the game ended on two passes and takes no further turns")]
pub struct GameOverError;

/// A delta the board cannot account for.
///
/// None of these is reachable by playing: [`Game::try_move`] builds its own
/// deltas and they are correct by construction. They are reachable by handing
/// [`Game::apply_delta`] a delta from somewhere else — a replay of a corrupt
/// log, or a peer that has drifted — and each says exactly which part of it the
/// board disagrees with.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum DeltaError {
    /// The delta places a stone whose id is already in play. Ids are issued
    /// once and never reused, so this means two different stones claim one id.
    #[error("stone {stone} is already on the board")]
    StoneExists {
        /// The id claimed twice.
        stone: StoneId,
    },

    /// The delta captures a stone that is not on the board.
    #[error("stone {stone} is not on the board and cannot be captured")]
    NoSuchStone {
        /// The stone.
        stone: StoneId,
    },

    /// The delta captures the same stone twice, which would credit two captures
    /// for one stone and leave the board unable to give it back.
    #[error("stone {stone} is captured twice by the same delta")]
    CapturedTwice {
        /// The stone.
        stone: StoneId,
    },

    /// The delta captures without placing anything. A pass never captures, and
    /// capture counts credit the placer, so there would be nobody to credit.
    #[error("a delta that places no stone cannot capture one")]
    PassCaptures,

    /// The delta places a stone whose centre is not a position on this board.
    ///
    /// The board rectangle, not the alive zone: a delta is not re-judged for
    /// placeability, because it carries its own record of a turn that was legal
    /// when it was played. This is the weaker statement that its stone is
    /// somewhere at all — see `docs/design.md` § "A position is a point on the
    /// board" for why the rules state that explicitly instead of leaving it to
    /// the geometry to notice.
    #[error("stone {stone}'s centre ({}, {}) is not on the board", .position.x, .position.y)]
    OffBoard {
        /// The stone the delta places.
        stone: StoneId,
        /// Where it claims to be.
        position: Point,
    },

    /// The alive zone could not carve or reclaim the dead zone the delta needs.
    #[error(transparent)]
    DeadZone(#[from] DeadZoneError),

    /// The game has ended, so there is no turn for the delta to be part of and
    /// nothing hypothetical worth asking about either. Nothing is applied.
    #[error(transparent)]
    GameOver(#[from] GameOverError),
}

/// Why a stone could not be played.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Error)]
pub enum StonePlayError {
    /// No stone centre may sit at this position: it is off the board, inset by
    /// a stone radius, or inside another stone's dead zone.
    ///
    /// This is also the answer for something that is not a position at all — a
    /// coordinate that is not a number, or one too large for any board. There is
    /// no separate variant for it because there is no separate answer: no stone
    /// centre may sit there either, and a caller that has produced one wants to
    /// hear the same thing. `docs/design.md` § "A position is a point on the
    /// board" is where that domain is written down.
    ///
    /// [`Game::try_move`] does not snap. [`Game::nearest_living_move`] is how a
    /// caller turns an arbitrary position into one this accepts.
    #[error("no stone may be placed at ({}, {})", .position.x, .position.y)]
    NotPlaceable {
        /// Where the caller tried to play.
        position: Point,
    },

    /// The placement would take only the mover's own stones. Self-capture is
    /// illegal, and the board is left exactly as it was.
    #[error("a {color:?} stone at ({}, {}) would capture only {color:?}'s own stones", .position.x, .position.y)]
    SelfCapture {
        /// Where the caller tried to play.
        position: Point,
        /// Whose move it was.
        color: Color,
    },

    /// The game has ended, so there is no move to make. The board is left
    /// exactly as it was, and [`Game::undo_move`] is the way back to a game that
    /// takes moves.
    #[error(transparent)]
    GameOver(#[from] GameOverError),

    /// The board could not apply the move's delta. Not reachable by playing —
    /// see [`DeltaError`].
    #[error(transparent)]
    Delta(#[from] DeltaError),
}

/// What capture resolution found once the stone was on the board.
#[derive(Clone, Debug, PartialEq)]
enum Resolution {
    /// The stones the move takes, possibly none of them.
    Captures(Vec<Stone>),
    /// The move takes only the mover's own stones, so it is illegal.
    SelfCapture,
}

/// A game of Voronoi Go: the board, the rules, and the history to undo them.
///
/// Every board change goes through [`Game::apply_delta`] and comes back off
/// through [`Game::pop_delta`]. [`Game::try_move`], [`Game::pass`] and
/// [`Game::undo_move`] are the three a player makes; everything else here is a
/// query.
///
/// # Invariants
///
/// Checked by [`Game::validate`], which runs after every change under
/// `cfg(debug_assertions)`:
///
/// - The alive zone holds all of its own invariants.
/// - Every stone on the board has exactly one dead zone carved for it, and no
///   captured stone has one.
/// - The turn number is the number of committed deltas in history, and the
///   status is the one the last two committed deltas imply.
/// - The capture counts are the ones history adds up to.
#[derive(Clone, Debug)]
pub struct Game {
    /// Width and height of the board.
    board_size: f64,
    /// Committed turns played so far, which is also the next stone's id.
    turn: u32,
    /// How many stones each player has taken.
    captures: PerColor<u32>,
    /// How far along the game is, as the last two committed turns imply.
    status: GameStatus,
    /// Bumped on every board change, transient ones included, so a caller can
    /// tell whether anything it derived is stale.
    revision: u64,
    /// The stones in play, ascending by id — never a hash map, because a
    /// training loop has to be reproducible.
    stones: BTreeMap<StoneId, Stone>,
    /// The stones taken off, kept so a pop can put them back.
    captured: BTreeMap<StoneId, Stone>,
    /// Everything applied and not yet popped.
    history: History,
    /// Where a stone may still be placed.
    zone: AliveZone,
    /// The diagram over [`Game::stones`], built on first read and dropped
    /// whenever the board changes.
    voronoi: OnceLock<Voronoi>,
    /// [`Game::stones`] as the flat slice the geometry wants, on the same terms
    /// as the diagram: built on first read, dropped whenever the board changes.
    ///
    /// A cut query needs it on a cache miss and not otherwise, and a caller
    /// asking about one pair at a time — which is how the cut queries are meant
    /// to be used — would otherwise pay for a copy of the whole board per
    /// question.
    stone_list: OnceLock<Vec<Stone>>,
    /// Cut statuses, invalidated around every stone whose presence changes.
    connectivity: Connectivity,
}

impl Game {
    /// An empty board `board_size` units square.
    #[must_use]
    pub fn new(board_size: f64) -> Self {
        Self {
            board_size,
            turn: 0,
            captures: PerColor::new(0, 0),
            status: GameStatus::Playing,
            revision: 0,
            stones: BTreeMap::new(),
            captured: BTreeMap::new(),
            history: History::default(),
            zone: AliveZone::new(board_size),
            voronoi: OnceLock::new(),
            stone_list: OnceLock::new(),
            connectivity: Connectivity::new(board_size),
        }
    }

    /// A board with `deltas` played onto it as committed turns, in order.
    ///
    /// This is how a game is rebuilt from its log. Deltas carry their own
    /// capture lists, so a replay reproduces the captures — and the forced eyes
    /// they leave — without re-deriving life and death.
    ///
    /// # Errors
    ///
    /// The first delta the board cannot account for, with nothing after it
    /// applied. See [`DeltaError`] — including
    /// [`DeltaError::GameOver`] for a log that carries on
    /// past two passes in a row, which is a log of a game that had already
    /// ended.
    pub fn replay(
        board_size: f64,
        deltas: impl IntoIterator<Item = GameDelta>,
    ) -> Result<Self, DeltaError> {
        let mut game = Self::new(board_size);
        for delta in deltas {
            game.apply_delta(delta, Commit::Turn)?;
        }
        Ok(game)
    }

    // ── Board queries ────────────────────────────────────────────────────────

    /// Width and height of the board.
    #[must_use]
    pub const fn board_size(&self) -> f64 {
        self.board_size
    }

    /// Committed turns played so far.
    #[must_use]
    pub const fn turn(&self) -> u32 {
        self.turn
    }

    /// Whose turn it is. Black moves on even turns.
    #[must_use]
    pub const fn pending_color(&self) -> Color {
        if self.turn % 2 == 0 {
            Color::Black
        } else {
            Color::White
        }
    }

    /// The id the next stone will take.
    ///
    /// At most one stone is placed per turn, so this is the turn number.
    #[must_use]
    pub const fn next_stone_id(&self) -> StoneId {
        StoneId::new(self.turn)
    }

    /// How many stones each player has captured.
    #[must_use]
    pub const fn captures(&self) -> PerColor<u32> {
        self.captures
    }

    /// How far along the game is.
    ///
    /// [`GameStatus::Ended`] once two passes in a row have been committed, and
    /// from then on [`Game::try_move`], [`Game::pass`] and
    /// [`Game::apply_delta`] all refuse. Nothing else does: the queries here all
    /// still answer, and [`Game::undo_move`] takes the last pass back.
    ///
    /// What an ended game is *worth* is still the caller's — this crate scores
    /// nothing beyond [`Game::territory`].
    #[must_use]
    pub const fn status(&self) -> GameStatus {
        self.status
    }

    /// Counts every board change, transient ones included.
    ///
    /// It only ever increases, so a caller can memoize anything derived from
    /// the board against it and know an undo cannot resurrect a stale entry.
    #[must_use]
    pub const fn revision(&self) -> u64 {
        self.revision
    }

    /// The stones in play, ascending by id.
    pub fn stones(&self) -> impl ExactSizeIterator<Item = Stone> + '_ {
        self.stones.values().copied()
    }

    /// How many stones are in play.
    #[must_use]
    pub fn stone_count(&self) -> usize {
        self.stones.len()
    }

    /// The stone with this id, if it is still in play.
    #[must_use]
    pub fn stone(&self, id: StoneId) -> Option<Stone> {
        self.stones.get(&id).copied()
    }

    /// The stone placed on the last committed turn, if that turn was not a
    /// pass.
    ///
    /// A transient placement is not a played stone and is skipped.
    #[must_use]
    pub fn last_placed_stone(&self) -> Option<Stone> {
        self.history
            .last_committed()
            .and_then(|delta| delta.new_stone)
    }

    /// The committed turns, oldest first — everything needed to replay this
    /// game into a fresh board of the same size.
    pub fn deltas(&self) -> impl Iterator<Item = &GameDelta> {
        self.history.committed()
    }

    /// Where a stone may still be placed.
    #[must_use]
    pub const fn alive_zone(&self) -> &AliveZone {
        &self.zone
    }

    /// The placeable position nearest `position`, or `None` when the board is
    /// full.
    ///
    /// A position that is already placeable is its own answer. This is the
    /// snapping [`Game::try_move`] deliberately does not do.
    #[must_use]
    pub fn nearest_living_move(&self, position: Point) -> Option<Point> {
        self.zone.closest_point(position)
    }

    /// The Voronoi diagram over the stones in play.
    ///
    /// Built on the first read after a change and kept until the next one. It
    /// is a pure function of the stones, so building it lazily changes no
    /// answer — it only stops a search paying for positions it never looks at.
    #[must_use]
    pub fn voronoi(&self) -> &Voronoi {
        self.voronoi.get_or_init(|| {
            Voronoi::new(self.board_size, stone_list(&self.stone_list, &self.stones))
        })
    }

    /// Every group on the board, black's before white's.
    pub fn groups(&self) -> GroupIter<'_> {
        self.voronoi().iter()
    }

    /// Whether an enemy pair can be wedged between two of this board's stones.
    ///
    /// [`CutKind::TooFar`] when the two are further apart than
    /// [`MAX_PAIR_CUT_DISTANCE`](crate::connectivity::MAX_PAIR_CUT_DISTANCE),
    /// which is **not** a verdict in either direction: past that distance the
    /// search could report a connection that is not there, so the rules decline
    /// rather than guess. The limit is public so a caller can see which pairs
    /// are answerable before asking.
    ///
    /// `&mut self` because measuring a pair means asking where an enemy would
    /// have to stand, which means carving a dead zone into the alive zone and
    /// taking it straight back out — and because the answers are cached. Neither
    /// changes the position: the zone comes back bit for bit, and
    /// [`Game::revision`] does not move.
    ///
    /// # Errors
    ///
    /// [`CutError::NoSuchStone`] when either id names no stone in play,
    /// [`CutError::SameStone`] for a stone against itself, and
    /// [`CutError::DifferentColors`] for two colours — none of which is a
    /// question about a connection.
    ///
    /// # Examples
    ///
    /// Three answers, and the third is a refusal rather than a verdict:
    ///
    /// ```
    /// use voronoi_go::{CutKind, Game, Point, StoneId};
    /// use voronoi_go::connectivity::MAX_PAIR_CUT_DISTANCE;
    ///
    /// let mut game = Game::new(18.0);
    /// game.try_move(Point::new(4.0, 4.0))?;   // black, id 0
    /// game.try_move(Point::new(14.0, 14.0))?; // white, id 1
    /// game.try_move(Point::new(4.0, 12.0))?;  // black, id 2
    ///
    /// // The two black stones are 8 units apart, well past the limit, so the
    /// // rules decline to judge rather than risk a false "uncuttable".
    /// assert!(8.0 > MAX_PAIR_CUT_DISTANCE);
    /// assert_eq!(
    ///     game.pair_cuttable(StoneId::new(0), StoneId::new(2))?,
    ///     CutKind::TooFar
    /// );
    ///
    /// // Two colours is not a question about a connection at all.
    /// assert!(game.pair_cuttable(StoneId::new(0), StoneId::new(1)).is_err());
    /// # Ok::<(), Box<dyn std::error::Error>>(())
    /// ```
    pub fn pair_cuttable(&mut self, a: StoneId, b: StoneId) -> Result<CutKind, CutError> {
        let first = self.stone(a).ok_or(CutError::NoSuchStone { stone: a })?;
        let second = self.stone(b).ok_or(CutError::NoSuchStone { stone: b })?;
        // Borrowed field by field: the memo and the map on one side, the zone
        // and the cache on the other, so a cache hit copies nothing at all.
        let stones = stone_list(&self.stone_list, &self.stones);
        self.connectivity
            .pair_cuttable(&mut self.zone, stones, first, second)
    }

    /// The same question about one of this board's stones and a board edge.
    ///
    /// [`CutKind::TooFar`] when the stone is further from that edge than
    /// [`MAX_BOUNDARY_CUT_DISTANCE`](crate::connectivity::MAX_BOUNDARY_CUT_DISTANCE).
    ///
    /// # Errors
    ///
    /// [`CutError::NoSuchStone`] when the id names no stone in play. Nothing
    /// else here can be malformed — every stone has all four edges.
    pub fn boundary_cuttable(
        &mut self,
        stone: StoneId,
        edge: BoardEdge,
    ) -> Result<CutKind, CutError> {
        let placed = self.stone(stone).ok_or(CutError::NoSuchStone { stone })?;
        let stones = stone_list(&self.stone_list, &self.stones);
        Ok(self
            .connectivity
            .boundary_cuttable(&mut self.zone, stones, placed, edge))
    }

    /// The board area each player controls.
    ///
    /// The whole board is `board_size * board_size`, and the two shares sum to
    /// it once there is at least one stone. Komi, and what to do with the
    /// difference, belong to the caller.
    #[must_use]
    pub fn territory(&self) -> PerColor<f64> {
        let voronoi = self.voronoi();
        PerColor::new(
            voronoi.player_area(Color::Black),
            voronoi.player_area(Color::White),
        )
    }

    /// Every stone of `color` whose group no longer touches playable space.
    ///
    /// This is the capture rule itself: a group is alive while its territory
    /// still meets the alive zone, and dead the moment it does not.
    #[must_use]
    pub fn dead_stones(&self, color: Color) -> Vec<Stone> {
        self.voronoi()
            .groups(color)
            .iter()
            .filter(|group| !self.zone.cell_is_alive(group.rings()))
            .flat_map(|group| group.stones().iter().copied())
            .collect()
    }

    // ── Turns ────────────────────────────────────────────────────────────────

    /// Plays a stone of the colour to move at `position`, taking whatever it
    /// captures, and answers the delta it committed.
    ///
    /// `position` must already be placeable —
    /// [`Game::nearest_living_move`] is how a caller makes it so. The stone is
    /// placed as a transient change first, because what a move captures cannot
    /// be known until it is on the board; the whole move is then committed as
    /// one delta, so one [`Game::undo_move`] takes it back.
    ///
    /// # Errors
    ///
    /// - [`StonePlayError::GameOver`] if the game has ended on two passes.
    /// - [`StonePlayError::NotPlaceable`] if no stone centre may sit there.
    /// - [`StonePlayError::SelfCapture`] if the move would take only the
    ///   mover's own stones. A move that takes enemy stones is legal even when
    ///   it would otherwise have been a self-capture — the enemy is checked
    ///   first, and dies first.
    ///
    /// The board is left exactly as it was, to the bit, in every case.
    ///
    /// # Examples
    ///
    /// A rejected move is a refusal, not a correction. Snapping is a separate
    /// call, so a training loop always knows whether its policy produced a legal
    /// move:
    ///
    /// ```
    /// use voronoi_go::{Game, Point, StonePlayError};
    ///
    /// let mut game = Game::new(18.0);
    /// game.try_move(Point::new(4.0, 4.0))?;
    ///
    /// // A second stone cannot sit on top of the first.
    /// let taken = Point::new(4.0, 4.0);
    /// assert!(matches!(
    ///     game.try_move(taken),
    ///     Err(StonePlayError::NotPlaceable { .. })
    /// ));
    ///
    /// // Ask for the nearest legal position, then play that.
    /// let snapped = game.nearest_living_move(taken).expect("board is not full");
    /// assert_ne!(snapped, taken);
    /// game.try_move(snapped)?;
    /// # Ok::<(), StonePlayError>(())
    /// ```
    pub fn try_move(&mut self, position: Point) -> Result<GameDelta, StonePlayError> {
        self.ensure_playing()?;

        if !self.zone.is_placeable(position) {
            return Err(StonePlayError::NotPlaceable { position });
        }

        let stone = Stone::new(self.next_stone_id(), self.pending_color(), position);

        // Capture resolution needs the stone on the board, so put it there
        // without committing a turn and take it straight back off.
        let resolution = self.with_transient_stone(stone, Self::resolve_captures)?;

        let dead = match resolution {
            Resolution::SelfCapture => {
                return Err(StonePlayError::SelfCapture {
                    position,
                    color: stone.color,
                });
            }
            Resolution::Captures(dead) => dead,
        };

        let mut captured: Vec<StoneId> = dead.iter().map(|stone| stone.id).collect();
        captured.sort_unstable();

        let delta = GameDelta::capture(stone, captured);
        self.apply_delta(delta.clone(), Commit::Turn)?;
        Ok(delta)
    }

    /// Passes the turn, and answers the delta it committed.
    ///
    /// A pass is a committed delta like any other, so it can be undone. The
    /// second one in a row ends the game — [`Game::status`] is where that is
    /// read, and what an ended game is worth is still the caller's.
    ///
    /// # Errors
    ///
    /// [`GameOverError`] if the game has already ended. It takes two passes to
    /// end a game and a third is not a turn.
    pub fn pass(&mut self) -> Result<GameDelta, GameOverError> {
        self.ensure_playing()?;

        let delta = GameDelta::pass();
        // A pass places no stone and captures none, so there is nothing left
        // here for the board to disagree with.
        let applied = self.apply_delta(delta.clone(), Commit::Turn);
        debug_assert!(applied.is_ok(), "a pass cannot fail to apply");
        Ok(delta)
    }

    /// Takes back the last change, and answers the delta it undid.
    ///
    /// `None` when there is nothing to undo. The board comes back bit for bit,
    /// including the alive zone's internal structure.
    ///
    /// Allowed on an ended game, and the one thing that is: undoing the second
    /// of the two passes is what puts a game back to taking turns.
    pub fn undo_move(&mut self) -> Option<GameDelta> {
        self.pop_delta()
    }

    /// `Ok` while the game is still taking turns.
    ///
    /// The whole of the ending rule on the writing side: every path that
    /// commits a turn or changes the board goes through here first, so an ended
    /// game cannot be moved on by any route a caller has.
    fn ensure_playing(&self) -> Result<(), GameOverError> {
        match self.status {
            GameStatus::Playing | GameStatus::NextPassEnds => Ok(()),
            GameStatus::Ended => Err(GameOverError),
        }
    }

    /// The status the committed turns imply.
    ///
    /// Two passes in a row is an ended game, one is a game a pass away from it,
    /// and anything else is a game in play. Derived rather than stored per
    /// delta, so a pop that removes a pass un-ends the game without history
    /// having to carry a copy of what the status was before it.
    fn derived_status(&self) -> GameStatus {
        let mut recent = self.history.committed().rev();
        let last = recent.next().is_some_and(GameDelta::is_pass);
        let previous = recent.next().is_some_and(GameDelta::is_pass);

        match (previous, last) {
            (true, true) => GameStatus::Ended,
            (_, true) => GameStatus::NextPassEnds,
            (_, false) => GameStatus::Playing,
        }
    }

    /// Puts `stone` on the board without committing a turn, asks `question`, and
    /// takes the placement back.
    ///
    /// The whole of "what does this move capture?" — the question needs the
    /// stone already on the board, because a group's life is a fact about the
    /// position the stone is *in*.
    ///
    /// **The rollback is structural, not a convention.** It hangs off a guard's
    /// `Drop`, so every way out of `question` — a value, an unwinding panic —
    /// goes through the same pop. A `pop_delta` written after the call is
    /// skipped by exactly the case that matters, and what it leaves behind is
    /// not a transient error but a board carrying a stone that was never played:
    /// history holds an uncommitted delta, the alive zone has a dead zone carved
    /// for it, and the next move fails with the id already in use. This is the
    /// same hazard [`AliveZone::with_temp_circle`] solves, solved the same way —
    /// see `docs/design.md` § "The transient placement must unwind".
    ///
    /// `question` is handed `&Self` rather than `&mut Self`, so it cannot change
    /// history and the delta the guard pops is provably the one that was pushed.
    ///
    /// # Errors
    ///
    /// [`DeltaError`], if the board cannot account for the placement. Nothing is
    /// applied and `question` is never asked.
    fn with_transient_stone<T>(
        &mut self,
        stone: Stone,
        question: impl FnOnce(&Self) -> T,
    ) -> Result<T, DeltaError> {
        /// Takes the transient placement back when it goes out of scope.
        struct Rollback<'game> {
            /// The board to take it back off.
            game: &'game mut Game,
        }

        impl Drop for Rollback<'_> {
            fn drop(&mut self) {
                // Deliberately unasserted. This runs while a panic may be
                // unwinding, and a panic raised inside a drop during an unwind
                // aborts the process — which is the one outcome this guard
                // exists to prevent. There is nothing to assert anyway: the
                // delta was pushed a few lines above and the closure was handed
                // a shared borrow, so it cannot have gone anywhere.
                let _ = self.game.pop_delta();
            }
        }

        self.apply_delta(GameDelta::placement(stone), Commit::Transient)?;

        // A reborrow, not a move: the guard keeps hold of the board, so its
        // `Drop` still runs however `question` leaves.
        let guard = Rollback { game: self };
        Ok(question(&*guard.game))
    }

    /// What the stone just placed captures, or that it captures only its own.
    ///
    /// The stone must already be on the board — [`Game::try_move`] places it as
    /// a transient change for exactly this. The opponent is asked first, and
    /// only when nothing of theirs died is the mover's own colour asked: a
    /// non-empty answer to that second question *is* the self-capture.
    fn resolve_captures(&self) -> Resolution {
        let mover = self.pending_color();

        let enemy = self.dead_stones(mover.opposite());
        if !enemy.is_empty() {
            return Resolution::Captures(enemy);
        }

        let own = self.dead_stones(mover);
        if own.is_empty() {
            Resolution::Captures(Vec::new())
        } else {
            Resolution::SelfCapture
        }
    }

    // ── Deltas ───────────────────────────────────────────────────────────────

    /// Applies a delta to the board.
    ///
    /// `commit` says whether this is a turn of the game or a hypothetical the
    /// caller intends to take back; see [`Commit`]. Either way the delta lands
    /// on history, the Voronoi memo is dropped, and the revision moves.
    ///
    /// # Errors
    ///
    /// [`DeltaError::GameOver`] if the game has ended, whatever `commit` says:
    /// a hypothetical that cannot be played is not worth asking about either,
    /// and the board of an ended game has to stay the board that ended.
    ///
    /// Otherwise [`DeltaError`], if the delta names a stone the board cannot
    /// account for. Every such check runs before anything is mutated, so a
    /// rejected delta leaves the board untouched.
    pub fn apply_delta(&mut self, delta: GameDelta, commit: Commit) -> Result<(), DeltaError> {
        self.ensure_playing()?;
        self.check(&delta)?;

        let mut removed_forced_eyes = Vec::new();
        if let Some(stone) = delta.new_stone {
            self.stones.insert(stone.id, stone);
            self.zone.remove_circle(stone.id, stone.position)?;
            // The new stone's dead zone swallows every forced eye it covers;
            // which ones is the only thing a pop cannot re-derive.
            removed_forced_eyes = self.zone.remove_forced_eyes_near_point(stone.position);
        }

        for id in &delta.captured_stone_ids {
            let stone = self
                .stones
                .remove(id)
                .ok_or(DeltaError::NoSuchStone { stone: *id })?;
            self.captured.insert(*id, stone);
            // A captured stone's own position stays playable even though its
            // neighbours' dead zones cover it.
            self.zone.add_forced_eye(stone.position);
            self.zone.reclaim_circle(*id)?;
        }

        // Self-capture is illegal and a pass never captures, so every capture
        // belongs to whoever placed the stone.
        if let Some(stone) = delta.new_stone {
            self.captures[stone.color] += delta.captured_stone_ids.len() as u32;
        }

        match commit {
            Commit::Turn => self.turn += 1,
            Commit::Transient => {}
        }

        // Every stone whose presence on the board changed takes the cut statuses
        // around it with it. Not gated on `commit`: a transient placement that
        // is about to be popped must not leave a status behind that outlives it.
        if let Some(stone) = delta.new_stone {
            self.connectivity.invalidate_near(stone.position);
        }
        for id in &delta.captured_stone_ids {
            if let Some(captured) = self.captured.get(id) {
                self.connectivity.invalidate_near(captured.position);
            }
        }

        // Dropped rather than rebuilt: the first read after this builds them.
        self.voronoi = OnceLock::new();
        self.stone_list = OnceLock::new();
        self.history.push(AppliedDelta {
            delta,
            commit,
            removed_forced_eyes,
        });
        // Read back off history rather than set from the delta in hand, so that
        // this and the pop below are the same statement and cannot drift.
        self.status = self.derived_status();
        self.revision += 1;
        self.debug_validate();
        Ok(())
    }

    /// Takes back the most recently applied delta, and answers it.
    ///
    /// The exact inverse of [`Game::apply_delta`], step for step in reverse
    /// order. `None` when there is nothing to take back.
    ///
    /// The stone the delta placed is **deleted**, not recorded as captured, and
    /// leaves no forced eye behind: it never existed.
    pub fn pop_delta(&mut self) -> Option<GameDelta> {
        let AppliedDelta {
            delta,
            commit,
            removed_forced_eyes,
        } = self.history.pop()?;

        match commit {
            Commit::Turn => self.turn = self.turn.saturating_sub(1),
            Commit::Transient => {}
        }

        // The mirror of the apply: history has just changed, so the status
        // follows it. Popping the second of two passes is what un-ends a game.
        self.status = self.derived_status();

        for id in &delta.captured_stone_ids {
            let Some(stone) = self.captured.remove(id) else {
                continue;
            };
            self.stones.insert(*id, stone);
            // Carving the same centre again recomputes bit-identical crossings
            // and finds the segments that survived the reclaim, which is what
            // makes this an exact inverse rather than an equivalent one.
            let carved = self.zone.remove_circle(*id, stone.position);
            debug_assert!(carved.is_ok(), "a restored stone's dead zone was carved");
            self.zone.remove_forced_eye(stone.position);
        }

        if let Some(stone) = delta.new_stone {
            let count = delta.captured_stone_ids.len() as u32;
            self.captures[stone.color] = self.captures[stone.color].saturating_sub(count);

            self.stones.remove(&stone.id);
            let reclaimed = self.zone.reclaim_circle(stone.id);
            debug_assert!(reclaimed.is_ok(), "the popped stone's dead zone was carved");
        }

        for eye in removed_forced_eyes {
            self.zone.add_forced_eye(eye);
        }

        // The mirror of `apply_delta`: the stone that has just been taken back
        // off, and every stone the undone captures put back.
        if let Some(stone) = delta.new_stone {
            self.connectivity.invalidate_near(stone.position);
        }
        for id in &delta.captured_stone_ids {
            if let Some(restored) = self.stones.get(id) {
                self.connectivity.invalidate_near(restored.position);
            }
        }

        self.voronoi = OnceLock::new();
        self.stone_list = OnceLock::new();
        self.revision += 1;
        self.debug_validate();
        Some(delta)
    }

    /// Everything about a delta that has to be true before any of it is
    /// applied.
    fn check(&self, delta: &GameDelta) -> Result<(), DeltaError> {
        match delta.new_stone {
            Some(stone) if !point_is_on_board(stone.position, self.board_size) => {
                return Err(DeltaError::OffBoard {
                    stone: stone.id,
                    position: stone.position,
                });
            }
            Some(stone)
                if self.stones.contains_key(&stone.id) || self.zone.has_circle(stone.id) =>
            {
                return Err(DeltaError::StoneExists { stone: stone.id });
            }
            None if !delta.captured_stone_ids.is_empty() => {
                return Err(DeltaError::PassCaptures);
            }
            Some(_) | None => {}
        }

        let mut seen = BTreeSet::new();
        for id in &delta.captured_stone_ids {
            if !self.stones.contains_key(id) {
                return Err(DeltaError::NoSuchStone { stone: *id });
            }
            if !seen.insert(*id) {
                return Err(DeltaError::CapturedTwice { stone: *id });
            }
        }

        Ok(())
    }
}

/// The stones as a flat slice, built once per position and kept until the board
/// changes.
///
/// A free function rather than a method on purpose: a `&self` method would
/// borrow the whole board, and every caller here needs the alive zone or the cut
/// cache mutably at the same time. Taking the two fields separately is what lets
/// the borrow checker see that they are disjoint.
fn stone_list<'a>(
    memo: &'a OnceLock<Vec<Stone>>,
    stones: &BTreeMap<StoneId, Stone>,
) -> &'a [Stone] {
    memo.get_or_init(|| stones.values().copied().collect())
}

#[cfg(test)]
mod tests;