eschac 0.1.0

//! **Move generation.**

use crate::array_vec::*;
use crate::bitboard::*;
use crate::board::*;
use crate::lookup::*;
use crate::san::*;
use crate::setup::*;
use crate::uci::*;

use std::iter::ExactSizeIterator;
use std::iter::FusedIterator;

/// **A chess position.**
///
/// ## Game's state
///
/// This type records the following information:
/// - the position of pieces on the board
/// - the color to play
/// - the available castling rights
/// - the optional en passant target square (even if taking is not possible)
///
/// ## Validity & Legality
///
/// This type can only represent "valid" chess positions. Valid positions include but are not
/// limited to legal chess positions (i.e. positions that can be reached from a sequence of legal
/// moves starting on the initial position). It is neither computably feasible nor desirable to
/// reject all illegal positions. eschac will only reject illegal positions when chess rules can't
/// be applied unambiguously or when doing so enables some code optimisation. See
/// [`IllegalPositionReason`] for details about rejected positions.
///
/// ## Move generation & play
///
/// The [`legal_moves`](Position::legal_moves) method generates the list of all legal moves on the
/// position. [`UciMove::to_move`] and [`San::to_move`] can also be used to convert chess notation
/// to playable moves.
///
/// Playing a move is done through a copy-make interface. [`legal_moves`](Position::legal_moves)
/// returns a sequence of [`Move`] objects. Moves hold a reference to the position from where they
/// were computed. They can be played without further checks and without potential panics using
/// [`Move::make`].
///
/// ## En passant & Equality
///
/// The en passant target square is set when the [`Position`] is obtained after playing a double
/// pawn advance, even when there is no pawn to take or when taking is not legal. In that case,
/// [`remove_en_passant_target_square`](Position::remove_en_passant_target_square) can be used to
/// remove the target square from the record. As a consequence, [`Eq`] is not defined in accordance
/// with the FIDE laws of chess.
///
/// ## Ordering
//
/// The order on [`Position`] is defined only for use in data structures. Hence its only
/// requirement is to be efficient while respecting the [`Ord`] trait protocol. It should not be
/// considered stable.
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Position {
    setup: Setup,
    lookup: InitialisedLookup,
}

const MAX_LEGAL_MOVES: usize = 218;

impl std::fmt::Debug for Position {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
        f.debug_tuple("Position")
            .field(&self.as_setup().to_string())
            .finish()
    }
}

impl Position {
    /// Returns the initial position of a chess game.
    ///
    /// i.e. `rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq -`
    #[inline]
    pub fn new() -> Self {
        Self {
            setup: Setup {
                w: Bitboard(0x000000000000FFFF),
                p_b_q: Bitboard(0x2CFF00000000FF2C),
                n_b_k: Bitboard(0x7600000000000076),
                r_q_k: Bitboard(0x9900000000000099),
                turn: Color::White,
                castling_rights: CastlingRights::full(),
                en_passant: OptionSquare::None,
            },
            lookup: InitialisedLookup::init(),
        }
    }

    /// Tries to read a valid position from a text record.
    ///
    /// This is a shortcut for parsing and validating a [`Setup`]:
    /// ```
    /// # use eschac::setup::Setup;
    /// # |s: &str| -> Option<eschac::position::Position> {
    /// s.parse::<Setup>().ok().and_then(|pos| pos.validate().ok())
    /// # };
    /// ```
    #[inline]
    pub fn from_text_record(s: &str) -> Option<Self> {
        s.parse::<Setup>().ok().and_then(|pos| pos.validate().ok())
    }

    /// Returns all the legal moves on the position.
    #[inline]
    pub fn legal_moves<'l>(&'l self) -> Moves<'l> {
        fn aux(position: &Position, visitor: &mut Moves) {
            position.generate_moves(visitor);
        }
        let mut visitor = Moves {
            position: self,
            is_check: false,
            en_passant_is_legal: false,
            array: ArrayVec::new(),
        };
        aux(self, &mut visitor);
        visitor
    }

    /// Counts the legal moves on the position.
    ///
    /// This is equivalent but faster than:
    /// ```
    /// # use eschac::position::Position;
    /// # |position: &Position| -> usize {
    /// position.legal_moves().len()
    /// # };
    /// ```
    #[inline]
    pub fn count_legal_moves(&self) -> usize {
        struct VisitorImpl {
            len: usize,
        }
        impl VisitorImpl {
            fn new() -> Self {
                Self { len: 0 }
            }
        }
        impl Visitor for VisitorImpl {
            #[inline]
            fn is_check(&mut self) {}
            #[inline]
            fn en_passant_is_legal(&mut self) {}
            #[inline]
            fn moves<I>(&mut self, iter: I)
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                self.len += iter.len();
            }
        }
        fn aux(position: &Position, visitor: &mut VisitorImpl) {
            position.generate_moves(visitor);
        }
        let mut visitor = VisitorImpl::new();
        aux(self, &mut visitor);
        visitor.len
    }

    /// Discards the optional en passant target square.
    ///
    /// This function is useful to check for position equality, notably when implementing FIDE's
    /// draw by repetition rules. Note that this function will remove the en passant target square
    /// even if taking en passant is legal. If this is not desirable, it is the caller's
    /// responsibility to rule out the legality of en passant before calling this function.
    #[inline]
    pub fn remove_en_passant_target_square(&mut self) {
        self.setup.en_passant = OptionSquare::None;
    }

    /// Returns the occupancy of a square.
    #[inline]
    pub fn get(&self, square: Square) -> Option<Piece> {
        self.setup.get(square)
    }

    /// Returns the color whose turn it is to play.
    #[inline]
    pub fn turn(&self) -> Color {
        self.setup.turn()
    }

    /// Returns `true` if castling is available for the given color and side.
    #[inline]
    pub fn castling_rights(&self, color: Color, side: CastlingSide) -> bool {
        self.setup.castling_rights(color, side)
    }

    /// Returns the en passant target square if it exists.
    ///
    /// Note that if an en passant target square exists, it does not mean that taking en passant is
    /// legal or even pseudo-legal.
    #[inline]
    pub fn en_passant_target_square(&self) -> Option<Square> {
        self.setup.en_passant_target_square()
    }

    /// Discards the castling rights for the given color and side.
    #[inline]
    pub fn remove_castling_rights(&mut self, color: Color, side: CastlingSide) {
        self.setup.set_castling_rights(color, side, false);
    }

    /// Borrows the position as a [`Setup`].
    #[inline]
    pub fn as_setup(&self) -> &Setup {
        &self.setup
    }

    /// Converts a position to a [`Setup`], allowing to edit the position without enforcing its
    /// legality.
    #[inline]
    pub fn into_setup(self) -> Setup {
        self.setup
    }

    /// Tries to pass the turn to the other color, failing if it would leave the king in check.
    ///
    /// When possible, this inverts the color to play and removes the en passant square if it
    /// exists.
    pub fn pass(&self) -> Option<Self> {
        let d = self.lookup;
        let setup = &self.setup;
        let blockers = setup.p_b_q | setup.n_b_k | setup.r_q_k;
        let k = setup.n_b_k & setup.r_q_k;
        let q = setup.p_b_q & setup.r_q_k;
        let b = setup.p_b_q & setup.n_b_k;
        let n = setup.n_b_k ^ b ^ k;
        let r = setup.r_q_k ^ q ^ k;
        let p = setup.p_b_q ^ b ^ q;
        let (us, them) = match setup.turn {
            Color::White => (setup.w, blockers ^ setup.w),
            Color::Black => (blockers ^ setup.w, setup.w),
        };
        let king_square = (us & k).next().unwrap();
        let checkers = them
            & (d.pawn_attack(setup.turn, king_square) & p
                | d.knight(king_square) & n
                | d.bishop(king_square, blockers) & (q | b)
                | d.rook(king_square, blockers) & (q | r));
        checkers.is_empty().then(|| Self {
            setup: Setup {
                turn: !setup.turn,
                en_passant: OptionSquare::None,
                ..setup.clone()
            },
            lookup: d,
        })
    }

    /// Returns the mirror image of the position (see [`Setup::mirror`]).
    #[inline]
    pub fn mirror(&self) -> Self {
        Self {
            setup: self.setup.mirror(),
            lookup: self.lookup,
        }
    }

    /// Returns the number of possible chess games for a given number of moves.
    ///
    /// This function is intended for benchmarking and is written as a simple recursion without any
    /// caching.
    pub fn perft(&self, depth: usize) -> u128 {
        fn aux(position: &Position, depth: usize) -> u128 {
            match depth.checked_sub(1) {
                None => position.count_legal_moves() as u128,
                Some(depth) => position
                    .legal_moves()
                    .into_iter()
                    .map(|m| aux(&m.make(), depth))
                    .sum(),
            }
        }
        match depth.checked_sub(1) {
            None => 1,
            Some(depth) => aux(self, depth),
        }
    }

    pub(crate) fn move_from_uci<'l>(&'l self, uci: UciMove) -> Result<Move<'l>, InvalidUciMove> {
        struct VisitorImpl<const ROLE: u8> {
            role: Role,
            from: Bitboard,
            to: Bitboard,
            found: Option<RawMove>,
        }
        impl<const ROLE: u8> VisitorImpl<ROLE> {
            #[inline]
            fn new(role: Role, from: Bitboard, to: Bitboard) -> Self {
                Self {
                    role,
                    from,
                    to,
                    found: None,
                }
            }
        }
        impl<const ROLE: u8> Visitor for VisitorImpl<ROLE> {
            #[inline]
            fn roles(&self, role: Role) -> bool {
                role as u8 == ROLE
            }
            #[inline]
            fn from(&self) -> Bitboard {
                self.from
            }
            #[inline]
            fn to(&self) -> Bitboard {
                self.to
            }
            #[inline]
            fn is_check(&mut self) {}
            #[inline]
            fn en_passant_is_legal(&mut self) {}
            #[inline]
            fn moves<I>(&mut self, iter: I)
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                iter.for_each(|raw| {
                    debug_assert!(raw.role() as u8 == ROLE);
                    debug_assert!(self.from.contains(raw.from()));
                    debug_assert!(self.to.contains(raw.to()));
                    if raw.role == self.role {
                        debug_assert!(self.found.is_none());
                        self.found = Some(raw);
                    }
                });
            }
        }
        let UciMove {
            from,
            to,
            promotion,
        } = uci;
        let role = self.setup.get_role(from).ok_or(InvalidUciMove::Illegal)?;
        #[inline]
        fn aux<'l, const ROLE: u8>(
            position: &'l Position,
            role: Role,
            from: Square,
            to: Square,
        ) -> Result<Move<'l>, InvalidUciMove> {
            let mut visitor = VisitorImpl::<ROLE>::new(role, from.bitboard(), to.bitboard());
            position.generate_moves(&mut visitor);
            let raw = visitor.found.ok_or(InvalidUciMove::Illegal)?;
            Ok(Move { position, raw })
        }
        let promotion = if role == Role::Pawn {
            promotion.unwrap_or(Role::Pawn)
        } else if promotion.is_some() {
            return Err(InvalidUciMove::Illegal);
        } else {
            role
        };
        match role {
            Role::Pawn => aux::<1>(self, promotion, from, to),
            Role::Knight => aux::<2>(self, promotion, from, to),
            Role::Bishop => aux::<3>(self, promotion, from, to),
            Role::Rook => aux::<4>(self, promotion, from, to),
            Role::Queen => aux::<5>(self, promotion, from, to),
            Role::King => aux::<6>(self, promotion, from, to),
        }
    }

    pub(crate) fn move_from_san<'l>(&'l self, san: &San) -> Result<Move<'l>, InvalidSan> {
        struct VisitorImpl<const ROLE: u8> {
            role: Role,
            from: Bitboard,
            to: Bitboard,
            found: Option<RawMove>,
            found_other: bool,
        }
        impl<const ROLE: u8> VisitorImpl<ROLE> {
            #[inline]
            fn new(role: Role, from: Bitboard, to: Bitboard) -> Self {
                Self {
                    role,
                    from,
                    to,
                    found: None,
                    found_other: false,
                }
            }
        }
        impl<const ROLE: u8> Visitor for VisitorImpl<ROLE> {
            #[inline]
            fn roles(&self, role: Role) -> bool {
                role as u8 == ROLE
            }
            #[inline]
            fn from(&self) -> Bitboard {
                self.from
            }
            #[inline]
            fn to(&self) -> Bitboard {
                self.to
            }
            #[inline]
            fn is_check(&mut self) {}
            #[inline]
            fn en_passant_is_legal(&mut self) {}
            #[inline]
            fn moves<I>(&mut self, iter: I)
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                iter.for_each(|raw| {
                    debug_assert!(raw.role() as u8 == ROLE);
                    debug_assert!(self.from.contains(raw.from()));
                    debug_assert!(self.to.contains(raw.to()));
                    if raw.role == self.role {
                        match self.found {
                            Some(_) => self.found_other = true,
                            None => self.found = Some(raw),
                        }
                    }
                });
            }
        }
        let (role, promotion, from, to) = match san.inner {
            SanInner::Castle(CastlingSide::Short) => (
                Role::King,
                Role::King,
                Square::new(File::E, self.turn().home_rank()).bitboard(),
                Square::new(File::G, self.turn().home_rank()).bitboard(),
            ),
            SanInner::Castle(CastlingSide::Long) => (
                Role::King,
                Role::King,
                Square::new(File::E, self.turn().home_rank()).bitboard(),
                Square::new(File::C, self.turn().home_rank()).bitboard(),
            ),
            SanInner::Normal {
                role,
                target,
                file,
                rank,
                promotion,
                ..
            } => (
                role,
                if role == Role::Pawn {
                    promotion.unwrap_or(Role::Pawn)
                } else if promotion.is_some() {
                    return Err(InvalidSan::Illegal);
                } else {
                    role
                },
                file.map_or(!Bitboard::new(), |file| file.bitboard())
                    & rank.map_or(!Bitboard::new(), |rank| rank.bitboard()),
                target.bitboard(),
            ),
        };
        #[inline]
        fn aux<'l, const ROLE: u8>(
            position: &'l Position,
            role: Role,
            from: Bitboard,
            to: Bitboard,
        ) -> Result<Move<'l>, InvalidSan> {
            let mut visitor = VisitorImpl::<ROLE>::new(role, from, to);
            position.generate_moves(&mut visitor);
            match visitor.found {
                None => Err(InvalidSan::Illegal),
                Some(raw) => match visitor.found_other {
                    true => Err(InvalidSan::Ambiguous),
                    false => Ok(Move { position, raw }),
                },
            }
        }
        match role {
            Role::Pawn => aux::<1>(self, promotion, from, to),
            Role::Knight => aux::<2>(self, promotion, from, to),
            Role::Bishop => aux::<3>(self, promotion, from, to),
            Role::Rook => aux::<4>(self, promotion, from, to),
            Role::Queen => aux::<5>(self, promotion, from, to),
            Role::King => aux::<6>(self, promotion, from, to),
        }
    }
}

/// A legal move.
#[derive(Clone, Copy)]
pub struct Move<'l> {
    position: &'l Position,
    raw: RawMove,
}

impl<'l> Move<'l> {
    /// Returns the position after playing the move.
    ///
    /// This sets the en passant square after a double pawn advance, even when there is no pawn to
    /// capture or when capturing is not legal.
    pub fn make(self) -> Position {
        let mut position = self.position.clone();
        unsafe { position.play_unchecked(self.raw) };
        position
    }

    /// Returns the position the move is played on.
    #[inline]
    pub fn position(self) -> &'l Position {
        self.position
    }

    /// Returns the type of piece that moves.
    #[inline]
    pub fn role(self) -> Role {
        self.raw.role()
    }

    /// Returns the origin square of the move.
    #[inline]
    pub fn from(self) -> Square {
        self.raw.from()
    }

    /// Returns the target square of the move.
    #[inline]
    pub fn to(self) -> Square {
        self.raw.to()
    }

    /// Returns the type of piece that the pawn is promoted to, if the move is a promotion.
    #[inline]
    pub fn promotion(self) -> Option<Role> {
        self.raw.promotion()
    }

    /// Returns `true` if the move is a capture.
    #[inline]
    pub fn is_capture(self) -> bool {
        self.raw.kind == MoveType::EnPassant
            || !((self.position.setup.p_b_q
                | self.position.setup.n_b_k
                | self.position.setup.r_q_k)
                & self.to().bitboard())
            .is_empty()
    }

    /// Returns the type of piece that is captured, if the move is a capture.
    #[inline]
    pub fn captured(self) -> Option<Role> {
        match self.raw.kind {
            MoveType::EnPassant => Some(Role::Pawn),
            _ => self.position.setup.get_role(self.raw.to),
        }
    }

    /// Returns the UCI notation of the move.
    #[inline]
    pub fn to_uci(self) -> UciMove {
        self.raw.uci()
    }

    /// Returns the standard algebraic notation of the move.
    pub fn to_san(self) -> San {
        struct VisitorImpl<const ROLE: u8> {
            to: Bitboard,
            candidates: Bitboard,
        }
        impl<const ROLE: u8> VisitorImpl<ROLE> {
            #[inline]
            fn new(to: Square) -> Self {
                Self {
                    to: to.bitboard(),
                    candidates: Bitboard::new(),
                }
            }
        }
        impl<const ROLE: u8> Visitor for VisitorImpl<ROLE> {
            #[inline]
            fn roles(&self, role: Role) -> bool {
                role as u8 == ROLE
            }
            #[inline]
            fn to(&self) -> Bitboard {
                self.to
            }
            #[inline]
            fn is_check(&mut self) {}
            #[inline]
            fn en_passant_is_legal(&mut self) {}
            #[inline]
            fn moves<I>(&mut self, iter: I)
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                iter.for_each(|raw| {
                    debug_assert!(raw.role() as u8 == ROLE);
                    debug_assert!(self.to.contains(raw.to()));
                    self.candidates.insert(raw.from);
                });
            }
        }
        San {
            inner: match self.raw.kind {
                MoveType::CastleShort => SanInner::Castle(CastlingSide::Short),
                MoveType::CastleLong => SanInner::Castle(CastlingSide::Long),
                MoveType::PawnAdvance
                | MoveType::PawnAdvancePromotion
                | MoveType::PawnDoubleAdvance => SanInner::Normal {
                    role: Role::Pawn,
                    file: None,
                    rank: None,
                    capture: false,
                    target: self.to(),
                    promotion: self.promotion(),
                },
                MoveType::PawnAttack | MoveType::PawnAttackPromotion | MoveType::EnPassant => {
                    SanInner::Normal {
                        role: Role::Pawn,
                        file: Some(self.from().file()),
                        rank: None,
                        capture: true,
                        target: self.to(),
                        promotion: self.promotion(),
                    }
                }
                _ => {
                    fn aux<const ROLE: u8>(m: &Move) -> SanInner {
                        let mut visitor = VisitorImpl::<ROLE>::new(m.to());
                        m.position().generate_moves(&mut visitor);
                        let candidates = visitor.candidates;
                        let (file, rank) = if candidates == m.from().bitboard() {
                            (None, None)
                        } else if candidates & m.from().file().bitboard() == m.from().bitboard() {
                            (Some(m.from().file()), None)
                        } else if candidates & m.from().rank().bitboard() == m.from().bitboard() {
                            (None, Some(m.from().rank()))
                        } else {
                            (Some(m.from().file()), Some(m.from().rank()))
                        };
                        SanInner::Normal {
                            role: m.role(),
                            file,
                            rank,
                            capture: m.is_capture(),
                            target: m.to(),
                            promotion: None,
                        }
                    }
                    match self.role() {
                        Role::Pawn => aux::<1>(&self),
                        Role::Knight => aux::<2>(&self),
                        Role::Bishop => aux::<3>(&self),
                        Role::Rook => aux::<4>(&self),
                        Role::Queen => aux::<5>(&self),
                        Role::King => aux::<6>(&self),
                    }
                }
            },
            suffix: {
                let pos = self.make();
                let mut visitor = MateCollector::new();
                pos.generate_moves(&mut visitor);
                visitor.is_check.then(|| match visitor.is_mate {
                    true => SanSuffix::Checkmate,
                    false => SanSuffix::Check,
                })
            },
        }
    }
}

/// A list of legal moves on the same position.
///
/// It can be obtained using the [`Position::legal_moves`] method. This type is an iterator over
/// [`Move`] objects.
pub struct Moves<'l> {
    position: &'l Position,
    is_check: bool,
    en_passant_is_legal: bool,
    array: ArrayVec<RawMove, MAX_LEGAL_MOVES>,
}

impl<'l> Moves<'l> {
    /// Returns the position on which the moves are played.
    #[inline]
    pub fn position(&self) -> &Position {
        self.position
    }

    /// Iterates over the moves.
    #[inline]
    pub fn iter(&'l self) -> MovesIter<'l> {
        MovesIter {
            position: self.position,
            iter: (&self.array).into_iter(),
        }
    }

    /// Returns the number of moves in the list.
    #[inline]
    pub fn len(&self) -> usize {
        self.array.len()
    }

    /// Returns `true` if en passant is legal.
    #[inline]
    pub fn en_passant_is_legal(&self) -> bool {
        self.en_passant_is_legal
    }

    /// Returns `true` if the king is in check.
    #[inline]
    pub fn is_check(&self) -> bool {
        self.is_check
    }

    /// Returns the move at the given index, if it exists.
    #[inline]
    pub fn get(&self, index: usize) -> Option<Move<'l>> {
        self.array.get(index).copied().map(|raw| Move {
            position: self.position,
            raw,
        })
    }

    /// Sorts the moves in the list.
    ///
    /// See [`slice::sort_unstable_by`] for potential panics.
    #[inline]
    pub fn sort_by<F>(&mut self, mut compare: F)
    where
        F: FnMut(Move, Move) -> std::cmp::Ordering,
    {
        self.array.as_slice_mut().sort_unstable_by(|a, b| {
            compare(
                Move {
                    position: self.position,
                    raw: *a,
                },
                Move {
                    position: self.position,
                    raw: *b,
                },
            )
        });
    }
}

/// An iterator over legal moves.
pub struct MovesIter<'l> {
    position: &'l Position,
    iter: ArrayVecIter<'l, RawMove, MAX_LEGAL_MOVES>,
}
impl<'l> Iterator for MovesIter<'l> {
    type Item = Move<'l>;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|raw| Move {
            position: self.position,
            raw,
        })
    }
}
impl<'l> FusedIterator for MovesIter<'l> {}
impl<'l> ExactSizeIterator for MovesIter<'l> {
    #[inline]
    fn len(&self) -> usize {
        self.iter.len()
    }
}
impl<'l> IntoIterator for &'l Moves<'l> {
    type Item = Move<'l>;
    type IntoIter = MovesIter<'l>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

/// An iterator over legal moves.
pub struct MovesIntoIter<'l> {
    position: &'l Position,
    iter: ArrayVecIntoIter<RawMove, MAX_LEGAL_MOVES>,
}
impl<'l> Iterator for MovesIntoIter<'l> {
    type Item = Move<'l>;
    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        self.iter.next().map(|raw| Move {
            position: self.position,
            raw,
        })
    }
    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}
impl<'l> FusedIterator for MovesIntoIter<'l> {}
impl<'l> ExactSizeIterator for MovesIntoIter<'l> {
    #[inline]
    fn len(&self) -> usize {
        self.iter.len()
    }
}
impl<'l> IntoIterator for Moves<'l> {
    type Item = Move<'l>;
    type IntoIter = MovesIntoIter<'l>;
    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        MovesIntoIter {
            position: self.position,
            iter: self.array.into_iter(),
        }
    }
}

#[derive(Clone, Copy)]
pub(crate) struct RawMove {
    kind: MoveType,
    role: Role,
    from: Square,
    to: Square,
}

#[derive(Clone, Copy, PartialEq, Eq)]
#[repr(u8)]
enum MoveType {
    CastleShort,
    CastleLong,
    KingMove,
    PieceMove,
    PawnAdvance,
    PawnAttack,
    PawnAdvancePromotion,
    PawnAttackPromotion,
    PawnDoubleAdvance,
    EnPassant,
}

impl RawMove {
    #[inline]
    fn from(&self) -> Square {
        self.from
    }
    #[inline]
    fn to(&self) -> Square {
        self.to
    }
    #[inline]
    fn role(&self) -> Role {
        match self.kind {
            MoveType::CastleShort | MoveType::CastleLong | MoveType::KingMove => Role::King,
            MoveType::PieceMove => self.role,
            MoveType::PawnAdvance
            | MoveType::PawnAttack
            | MoveType::PawnAdvancePromotion
            | MoveType::PawnAttackPromotion
            | MoveType::PawnDoubleAdvance
            | MoveType::EnPassant => Role::Pawn,
        }
    }
    #[inline]
    fn promotion(&self) -> Option<Role> {
        match self.kind {
            MoveType::PawnAdvancePromotion | MoveType::PawnAttackPromotion => Some(self.role),
            _ => None,
        }
    }
    #[inline]
    fn uci(&self) -> UciMove {
        UciMove {
            from: self.from(),
            to: self.to(),
            promotion: self.promotion(),
        }
    }
}

trait Visitor {
    #[inline]
    fn roles(&self, _role: Role) -> bool {
        true
    }
    #[inline]
    fn from(&self) -> Bitboard {
        !Bitboard::new()
    }
    #[inline]
    fn to(&self) -> Bitboard {
        !Bitboard::new()
    }

    fn is_check(&mut self);
    fn en_passant_is_legal(&mut self);
    fn moves<I>(&mut self, iter: I)
    where
        I: Iterator<Item = RawMove> + ExactSizeIterator;
}

impl<'l> Visitor for Moves<'l> {
    #[inline]
    fn is_check(&mut self) {
        self.is_check = true;
    }
    #[inline]
    fn en_passant_is_legal(&mut self) {
        self.en_passant_is_legal = true;
    }
    #[inline]
    fn moves<I>(&mut self, iter: I)
    where
        I: Iterator<Item = RawMove> + ExactSizeIterator,
    {
        iter.for_each(|raw| unsafe { self.array.push_unchecked(raw) });
    }
}

impl Position {
    /// SAFETY: The position must be valid.
    pub(crate) unsafe fn from_setup(setup: Setup) -> Self {
        Self {
            setup,
            lookup: InitialisedLookup::init(),
        }
    }

    fn generate_moves<T>(&self, visitor: &mut T)
    where
        T: Visitor,
    {
        let global_mask_from = visitor.from();
        let global_mask_to = visitor.to();

        let Setup {
            w,
            p_b_q,
            n_b_k,
            r_q_k,
            turn,
            en_passant,
            castling_rights,
        } = self.setup;
        let d = self.lookup;

        let blockers = p_b_q | n_b_k | r_q_k;
        let (us, them) = match turn {
            Color::White => (w, blockers ^ w),
            Color::Black => (blockers ^ w, w),
        };

        let k = n_b_k & r_q_k;
        let q = p_b_q & r_q_k;
        let b = p_b_q & n_b_k;
        let n = n_b_k ^ b ^ k;
        let r = r_q_k ^ q ^ k;
        let p = p_b_q ^ b ^ q;
        let ours = ByRole([p & us, n & us, b & us, r & us, q & us, k & us]);
        let theirs = ByRole([
            p & them,
            n & them,
            (q | b) & them,
            (q | r) & them,
            q & them,
            k & them,
        ]);
        let king_square = unsafe {
            // SAFETY: the position is legal
            ours.king().first().unwrap_unchecked()
        };

        let forward = turn.forward();

        let x = d.bishop(king_square, blockers);
        let y = d.rook(king_square, blockers);
        let checkers = d.pawn_attack(turn, king_square) & theirs.pawn()
            | d.knight(king_square) & theirs.knight()
            | x & theirs.bishop()
            | y & theirs.rook();
        let blockers_x_ray = blockers & !(x | y);
        let pinned = (d.bishop(king_square, blockers_x_ray) & theirs.bishop()
            | d.rook(king_square, blockers_x_ray) & theirs.rook())
        .map(|sq| d.segment(king_square, sq))
        .reduce_or();

        if visitor.roles(Role::King) && global_mask_from.contains(king_square) {
            let attacked = {
                let blockers = blockers ^ ours.king();
                theirs
                    .king()
                    .map(|sq| d.king(sq))
                    .chain(theirs.bishop().map(|sq| d.bishop(sq, blockers)))
                    .chain(theirs.rook().map(|sq| d.rook(sq, blockers)))
                    .chain(theirs.knight().map(|sq| d.knight(sq)))
                    .chain(std::iter::once(
                        theirs.pawn().trans(!forward).trans(Direction::East),
                    ))
                    .chain(std::iter::once(
                        theirs.pawn().trans(!forward).trans(Direction::West),
                    ))
                    .reduce_or()
            };
            // king moves
            visitor.moves(
                (global_mask_to & d.king(king_square) & !us & !attacked).map(|to| RawMove {
                    kind: MoveType::KingMove,
                    from: king_square,
                    to,
                    role: Role::King,
                }),
            );
            // castling
            if castling_rights.get(turn, CastlingSide::Short) {
                let (x, y) = match turn {
                    Color::White => (Bitboard(0x0000000000000070), Bitboard(0x0000000000000060)),
                    Color::Black => (Bitboard(0x7000000000000000), Bitboard(0x6000000000000000)),
                };
                if (attacked & x | blockers & y).is_empty() {
                    let from = king_square;
                    let to = unsafe {
                        from.trans_unchecked(Direction::East)
                            .trans_unchecked(Direction::East)
                    };
                    if global_mask_to.contains(to) {
                        visitor.moves(std::iter::once(RawMove {
                            kind: MoveType::CastleShort,
                            from,
                            to,
                            role: Role::King,
                        }))
                    }
                }
            }
            if castling_rights.get(turn, CastlingSide::Long) {
                let (x, y) = match turn {
                    Color::White => (Bitboard(0x000000000000001C), Bitboard(0x000000000000000E)),
                    Color::Black => (Bitboard(0x1C00000000000000), Bitboard(0x0E00000000000000)),
                };
                if (attacked & x | blockers & y).is_empty() {
                    let from = king_square;
                    let to = unsafe {
                        from.trans_unchecked(Direction::West)
                            .trans_unchecked(Direction::West)
                    };
                    if global_mask_to.contains(to) {
                        visitor.moves(std::iter::once(RawMove {
                            kind: MoveType::CastleLong,
                            from,
                            to,
                            role: Role::King,
                        }))
                    }
                }
            }
        }

        if checkers.len() > 1 {
            visitor.is_check();
            return;
        }

        let checker = checkers.first();
        let block_check = checker
            .map(|checker| d.segment(king_square, checker))
            .unwrap_or(Bitboard(!0));
        let target_mask = global_mask_to & block_check;

        // pawns
        if visitor.roles(Role::Pawn) {
            let kside = match turn {
                Color::White => Direction::NorthEast,
                Color::Black => Direction::SouthEast,
            };
            let qside = match turn {
                Color::White => Direction::NorthWest,
                Color::Black => Direction::SouthWest,
            };
            let third_rank = match turn {
                Color::White => Rank::Third,
                Color::Black => Rank::Sixth,
            };
            let adv = (global_mask_from & ours.pawn() & (!pinned | king_square.file().bitboard()))
                .trans(forward)
                & !blockers;
            let promotion = turn.promotion_rank().bitboard();
            // pawn advances
            {
                let targets = adv & target_mask;
                visitor.moves((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAdvance,
                    from: unsafe { to.trans_unchecked(!forward) },
                    to,
                    role: Role::Pawn,
                }));
                visitor.moves(WithPromotion::new((targets & promotion).map(|to| {
                    RawMove {
                        kind: MoveType::PawnAdvancePromotion,
                        from: unsafe { to.trans_unchecked(!forward) },
                        to,
                        role: Role::Pawn,
                    }
                })));
            }
            // pawn attacks kingside
            {
                let targets =
                    (global_mask_from & ours.pawn() & (!pinned | d.ray(king_square, kside)))
                        .trans(kside)
                        & them
                        & target_mask;
                visitor.moves((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAttack,
                    from: unsafe { to.trans_unchecked(!kside) },
                    to,
                    role: Role::Pawn,
                }));
                visitor.moves(WithPromotion::new((targets & promotion).map(|to| {
                    RawMove {
                        kind: MoveType::PawnAttackPromotion,
                        from: unsafe { to.trans_unchecked(!kside) },
                        to,
                        role: Role::Pawn,
                    }
                })));
            }
            // pawn attacks queenside
            {
                let targets =
                    (global_mask_from & ours.pawn() & (!pinned | d.ray(king_square, qside)))
                        .trans(qside)
                        & them
                        & target_mask;
                visitor.moves((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAttack,
                    from: unsafe { to.trans_unchecked(!qside) },
                    to,
                    role: Role::Pawn,
                }));
                visitor.moves(WithPromotion::new((targets & promotion).map(|to| {
                    RawMove {
                        kind: MoveType::PawnAttackPromotion,
                        from: unsafe { to.trans_unchecked(!qside) },
                        to,
                        role: Role::Pawn,
                    }
                })));
            }
            // pawn double advances
            visitor.moves(
                ((adv & third_rank.bitboard()).trans(forward) & !blockers & target_mask).map(
                    |to| RawMove {
                        kind: MoveType::PawnDoubleAdvance,
                        from: unsafe { to.trans_unchecked(!forward).trans_unchecked(!forward) },
                        to,
                        role: Role::Pawn,
                    },
                ),
            );
            // en passant
            if let Some(to) = en_passant.try_into_square() {
                if global_mask_to.contains(to) {
                    let capture_square = unsafe {
                        // SAFETY: the position is legal
                        to.trans_unchecked(!forward)
                    };
                    if block_check.contains(to)
                        || checker.is_none_or(|checker| checker == capture_square)
                    {
                        let candidates = d.pawn_attack(!turn, to) & ours.pawn();
                        let blockers = blockers ^ capture_square.bitboard();
                        let pinned = pinned
                            | (d.rook(king_square, blockers & !(d.rook(king_square, blockers)))
                                & theirs.rook())
                            .map(|sq| d.segment(king_square, sq))
                            .reduce_or();
                        (global_mask_from & candidates & (!pinned | d.segment(king_square, to)))
                            .for_each(|from| {
                                visitor.en_passant_is_legal();
                                visitor.moves(std::iter::once(RawMove {
                                    kind: MoveType::EnPassant,
                                    from,
                                    to,
                                    role: Role::Pawn,
                                }))
                            })
                    }
                }
            }
        }

        // pieces not pinned
        {
            let aux = |visitor: &mut T, role| {
                for from in global_mask_from & *ours.get(role) & !pinned {
                    visitor.moves(
                        (d.targets(role, from, blockers) & !us & target_mask).map(|to| RawMove {
                            kind: MoveType::PieceMove,
                            from,
                            to,
                            role,
                        }),
                    )
                }
            };
            if visitor.roles(Role::Knight) {
                aux(visitor, Role::Knight)
            }
            if visitor.roles(Role::Bishop) {
                aux(visitor, Role::Bishop)
            }
            if visitor.roles(Role::Rook) {
                aux(visitor, Role::Rook)
            }
            if visitor.roles(Role::Queen) {
                aux(visitor, Role::Queen)
            }
        }

        if checker.is_some() {
            visitor.is_check();
            return;
        }

        // pinned pieces
        {
            let aux = |visitor: &mut T, role| {
                for from in global_mask_from & *ours.get(role) & pinned {
                    visitor.moves(
                        (global_mask_to
                            & d.targets(role, from, blockers)
                            & !us
                            & d.line(king_square, from))
                        .map(|to| RawMove {
                            kind: MoveType::PieceMove,
                            from,
                            to,
                            role,
                        }),
                    )
                }
            };
            if visitor.roles(Role::Bishop) {
                aux(visitor, Role::Bishop)
            }
            if visitor.roles(Role::Rook) {
                aux(visitor, Role::Rook)
            }
            if visitor.roles(Role::Queen) {
                aux(visitor, Role::Queen)
            }
        }
    }

    #[inline]
    unsafe fn play_unchecked(&mut self, m: RawMove) {
        let Self { setup, .. } = self;

        setup.en_passant = OptionSquare::None;

        let RawMove {
            kind,
            from,
            to,
            role,
        } = m;

        match kind {
            MoveType::CastleShort => aux_play_castle(setup, CastlingSide::Short),
            MoveType::CastleLong => aux_play_castle(setup, CastlingSide::Long),
            MoveType::KingMove => aux_play_normal(setup, Role::King, from, to),
            MoveType::PieceMove => aux_play_normal(setup, role, from, to),
            MoveType::PawnAdvance => aux_play_pawn_advance(setup, Role::Pawn, from, to),
            MoveType::PawnAttack => aux_play_normal(setup, Role::Pawn, from, to),
            MoveType::PawnAdvancePromotion => aux_play_pawn_advance(setup, role, from, to),
            MoveType::PawnAttackPromotion => aux_play_normal(setup, role, from, to),
            MoveType::PawnDoubleAdvance => {
                aux_play_pawn_advance(setup, Role::Pawn, from, to);
                setup.en_passant = OptionSquare::new(Some(Square::new(
                    from.file(),
                    match setup.turn {
                        Color::White => Rank::Third,
                        Color::Black => Rank::Sixth,
                    },
                )));
            }
            MoveType::EnPassant => {
                let direction = !setup.turn.forward();
                let x = (unsafe { to.trans_unchecked(direction) }).bitboard();
                setup.p_b_q ^= x;
                setup.w &= !x;
                aux_play_pawn_advance(setup, Role::Pawn, from, to);
            }
        }

        setup.turn = !setup.turn;
    }
}

struct WithPromotion<I: Iterator<Item = RawMove> + ExactSizeIterator + FusedIterator> {
    inner: I,
    cur: std::mem::MaybeUninit<RawMove>,
    role: Role,
}
impl<I> WithPromotion<I>
where
    I: Iterator<Item = RawMove> + ExactSizeIterator + FusedIterator,
{
    #[inline]
    fn new(inner: I) -> Self {
        Self {
            inner,
            cur: std::mem::MaybeUninit::uninit(),
            role: Role::King,
        }
    }
}
impl<I> Iterator for WithPromotion<I>
where
    I: Iterator<Item = RawMove> + ExactSizeIterator + FusedIterator,
{
    type Item = RawMove;
    #[inline]
    fn next(&mut self) -> Option<RawMove> {
        if self.role == Role::King {
            self.cur.write(self.inner.next()?);
            self.role = Role::Knight;
        }
        let raw = unsafe { self.cur.assume_init() };
        let res = RawMove {
            role: self.role,
            ..raw
        };
        self.role = unsafe { Role::transmute((self.role as u8).unchecked_add(1)) };
        Some(res)
    }
    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = self.len();
        (len, Some(len))
    }
}
impl<I> FusedIterator for WithPromotion<I> where
    I: Iterator<Item = RawMove> + ExactSizeIterator + FusedIterator
{
}
impl<I> ExactSizeIterator for WithPromotion<I>
where
    I: Iterator<Item = RawMove> + ExactSizeIterator + FusedIterator,
{
    #[inline]
    fn len(&self) -> usize {
        unsafe { self.inner.len().unchecked_mul(4) }
    }
}

#[inline]
fn aux_play_normal(setup: &mut Setup, role: Role, from: Square, target: Square) {
    let from = from.bitboard();
    let to = target.bitboard();
    let mask = !(from | to);
    setup.w &= mask;
    setup.p_b_q &= mask;
    setup.n_b_k &= mask;
    setup.r_q_k &= mask;
    if target == Square::new(File::H, setup.turn.promotion_rank()) {
        setup
            .castling_rights
            .unset(!setup.turn, CastlingSide::Short);
    }
    if target == Square::new(File::A, setup.turn.promotion_rank()) {
        setup.castling_rights.unset(!setup.turn, CastlingSide::Long);
    }
    match role {
        Role::King => {
            setup.n_b_k |= to;
            setup.r_q_k |= to;
            setup.castling_rights.unset(setup.turn, CastlingSide::Short);
            setup.castling_rights.unset(setup.turn, CastlingSide::Long);
        }
        Role::Queen => {
            setup.p_b_q |= to;
            setup.r_q_k |= to;
        }
        Role::Bishop => {
            setup.p_b_q |= to;
            setup.n_b_k |= to;
        }
        Role::Knight => {
            setup.n_b_k |= to;
        }
        Role::Rook => {
            setup.r_q_k |= to;
            if from == Square::new(File::H, setup.turn.home_rank()).bitboard() {
                setup.castling_rights.unset(setup.turn, CastlingSide::Short);
            }
            if from == Square::new(File::A, setup.turn.home_rank()).bitboard() {
                setup.castling_rights.unset(setup.turn, CastlingSide::Long);
            }
        }
        Role::Pawn => {
            setup.p_b_q |= to;
        }
    }
    if setup.turn == Color::White {
        setup.w |= to;
    }
}

#[inline]
fn aux_play_pawn_advance(setup: &mut Setup, role: Role, from: Square, to: Square) {
    let from = from.bitboard();
    let to = to.bitboard();
    match role {
        Role::King => unreachable!(),
        Role::Queen => {
            setup.p_b_q ^= from | to;
            setup.r_q_k |= to;
        }
        Role::Bishop => {
            setup.p_b_q ^= from | to;
            setup.n_b_k |= to;
        }
        Role::Knight => {
            setup.p_b_q ^= from;
            setup.n_b_k |= to;
        }
        Role::Rook => {
            setup.p_b_q ^= from;
            setup.r_q_k |= to;
        }
        Role::Pawn => setup.p_b_q ^= from | to,
    }
    if setup.turn == Color::White {
        setup.w ^= from | to;
    }
}

#[inline]
fn aux_play_castle(setup: &mut Setup, side: CastlingSide) {
    let rank = setup.turn.home_rank();
    let (king_flip, rook_flip) = match side {
        CastlingSide::Short => (
            Square::new(File::E, rank).bitboard() | Square::new(File::G, rank).bitboard(),
            Square::new(File::H, rank).bitboard() | Square::new(File::F, rank).bitboard(),
        ),
        CastlingSide::Long => (
            Square::new(File::E, rank).bitboard() | Square::new(File::C, rank).bitboard(),
            Square::new(File::A, rank).bitboard() | Square::new(File::D, rank).bitboard(),
        ),
    };

    if setup.turn == Color::White {
        setup.w ^= king_flip | rook_flip;
    }
    setup.n_b_k ^= king_flip;
    setup.r_q_k ^= king_flip | rook_flip;

    setup.castling_rights.unset(setup.turn, CastlingSide::Short);
    setup.castling_rights.unset(setup.turn, CastlingSide::Long);
}

struct MateCollector {
    is_check: bool,
    is_mate: bool,
}
impl MateCollector {
    #[inline]
    fn new() -> Self {
        Self {
            is_check: false,
            is_mate: true,
        }
    }
}
impl Visitor for MateCollector {
    #[inline]
    fn is_check(&mut self) {
        self.is_check = true;
    }
    #[inline]
    fn en_passant_is_legal(&mut self) {}
    #[inline]
    fn moves<I>(&mut self, iter: I)
    where
        I: Iterator<Item = RawMove> + ExactSizeIterator,
    {
        self.is_mate &= iter.len() == 0;
    }
}