//! **Move generation.**

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

use core::convert::Infallible;
use core::iter::{ExactSizeIterator, FusedIterator};
use core::ops::ControlFlow;

/// **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 list of [`Move<'l>`](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.
#[must_use]
#[derive(Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct Position(Setup);

const PAWN: u8 = Role::Pawn as u8;
const KNIGHT: u8 = Role::Knight as u8;
const BISHOP: u8 = Role::Bishop as u8;
const ROOK: u8 = Role::Rook as u8;
const QUEEN: u8 = Role::Queen as u8;
const KING: u8 = Role::King as u8;

macro_rules! map_role {
    ($f:ident, $role:ident, $($x:expr),+) => (
        match $role {
            Role::Pawn => $f::<PAWN>($($x),+),
            Role::Knight => $f::<KNIGHT>($($x),+),
            Role::Bishop => $f::<BISHOP>($($x),+),
            Role::Rook => $f::<ROOK>($($x),+),
            Role::Queen => $f::<QUEEN>($($x),+),
            Role::King => $f::<KING>($($x),+),
        }
    )
}

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 {
            bitboards: [
                Bitboard(0x2CFF00000000FF2C),
                Bitboard(0x7600000000000076),
                Bitboard(0x9900000000000099),
                Bitboard(0x000000000000FFFF),
            ],
            turn: Color::White,
            castling_rights: CastlingRights::full(),
            en_passant: OptionSquare::None,
        })
    }

    /// Returns the list of legal moves from the position.
    #[inline]
    pub fn legal_moves<'l>(&'l self) -> Moves<'l> {
        Moves::compute(self)
    }

    /// Returns the number of legal moves from the position.
    #[must_use]
    #[inline]
    pub fn count_legal_moves(&self) -> usize {
        struct MoveGenImpl {
            len: usize,
        }
        impl MoveGenImpl {
            fn new() -> Self {
                Self { len: 0 }
            }
        }
        impl MoveGen<Infallible> for MoveGenImpl {
            fn extend<I>(&mut self, iter: I) -> ControlFlow<Infallible>
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                self.len += iter.len();
                ControlFlow::Continue(())
            }
        }
        let mut moves = MoveGenImpl::new();
        let ControlFlow::Continue(()) = self.generate_moves(&mut moves);
        moves.len
    }

    /// Returns `true` if the king is in check.
    #[must_use]
    pub fn is_check(&self) -> bool {
        struct MoveGenImpl;
        impl MoveGen<()> for MoveGenImpl {
            #[inline]
            fn roles(&self, _role: Role) -> bool {
                false
            }
            #[inline]
            fn from(&self) -> Bitboard {
                Bitboard::new()
            }
            #[inline]
            fn to(&self) -> Bitboard {
                Bitboard::new()
            }
            #[inline]
            fn is_check(&mut self) -> ControlFlow<()> {
                ControlFlow::Break(())
            }
        }
        self.generate_moves(&mut MoveGenImpl).is_break()
    }

    /// Returns `true` if there is no legal move on the position.
    #[must_use]
    pub fn is_mate(&self) -> bool {
        self.count_legal_moves() == 0
    }

    /// Returns `true` if taking en passant is legal on the position.
    #[must_use]
    pub fn en_passant_is_legal(&self) -> bool {
        if self.as_setup().en_passant == OptionSquare::None {
            return false;
        }
        struct MoveGenImpl {
            to: Bitboard,
        }
        impl MoveGen<()> for MoveGenImpl {
            #[inline]
            fn roles(&self, role: Role) -> bool {
                match role {
                    Role::Pawn => true,
                    _ => false,
                }
            }
            #[inline]
            fn from(&self) -> Bitboard {
                !Bitboard::new()
            }
            #[inline]
            fn to(&self) -> Bitboard {
                self.to
            }
            #[inline]
            fn en_passant_is_legal(&mut self) -> ControlFlow<()> {
                ControlFlow::Break(())
            }
        }
        let mut moves = MoveGenImpl {
            to: self.as_setup().en_passant.bitboard(),
        };
        self.generate_moves(&mut moves).is_break()
    }

    /// Removes the en passant target square, if any.
    ///
    /// 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.0.en_passant = OptionSquare::None;
    }

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

    /// Converts the position to the [`Setup`] type.
    #[inline]
    pub fn as_setup(&self) -> &Setup {
        &self.0
    }

    /// Converts the position to the [`Setup`] type.
    #[inline]
    pub fn into_setup(self) -> Setup {
        self.0
    }

    /// Returns the position after after passing the turn to the other color,
    /// and `None` if the king in check. On success, this inverts the color to
    /// play and discards the en passant square.
    pub fn pass(&self) -> Option<Self> {
        let Setup {
            bitboards: [p_b_q, n_b_k, r_q_k, w],
            turn,
            en_passant: _,
            castling_rights: _,
        } = self.0;
        let blockers = p_b_q | n_b_k | r_q_k;
        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 (us, them) = match turn {
            Color::White => (w, blockers ^ w),
            Color::Black => (blockers ^ w, w),
        };
        let king_square = (us & k).next().unwrap();
        let checkers = them
            & (lookup::pawn_attack(turn, king_square) & p
                | lookup::knight(king_square) & n
                | lookup::bishop(king_square, blockers) & (q | b)
                | lookup::rook(king_square, blockers) & (q | r));
        checkers.is_empty().then(|| {
            Self(Setup {
                turn: !turn,
                en_passant: OptionSquare::None,
                ..self.0.clone()
            })
        })
    }

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

    /// 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 MoveGenImpl<const ROLE: u8> {
            role: Role,
            from: Bitboard,
            to: Bitboard,
        }
        impl<const ROLE: u8> MoveGenImpl<ROLE> {
            #[inline]
            fn new(role: Role, from: Bitboard, to: Bitboard) -> Self {
                Self { role, from, to }
            }
        }
        impl<const ROLE: u8> MoveGen<RawMove> for MoveGenImpl<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 extend<I>(&mut self, iter: I) -> ControlFlow<RawMove>
            where
                I: Iterator<Item = RawMove> + ExactSizeIterator,
            {
                for raw in iter {
                    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 {
                        return ControlFlow::Break(raw);
                    }
                }
                ControlFlow::Continue(())
            }
        }
        let UciMove {
            from,
            to,
            promotion,
        } = uci;
        let role = self.0.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 moves = MoveGenImpl::<ROLE>::new(role, from.bitboard(), to.bitboard());
            let raw = position
                .generate_moves(&mut moves)
                .break_value()
                .ok_or(InvalidUciMove::Illegal)?;
            Ok(unsafe { Move::new_unchecked(position, raw) })
        }
        let promotion = if role == Role::Pawn {
            promotion.unwrap_or(Role::Pawn)
        } else if promotion.is_some() {
            return Err(InvalidUciMove::Illegal);
        } else {
            role
        };
        map_role!(aux, role, self, promotion, from, to)
    }

    pub(crate) fn move_from_san<'l>(&'l self, san: &San) -> Result<Move<'l>, InvalidSan> {
        struct MoveGenImpl<const ROLE: u8> {
            role: Role,
            from: Bitboard,
            to: Bitboard,
            found: Option<RawMove>,
            found_other: bool,
        }
        impl<const ROLE: u8> MoveGenImpl<ROLE> {
            #[inline]
            fn new(role: Role, from: Bitboard, to: Bitboard) -> Self {
                Self {
                    role,
                    from,
                    to,
                    found: None,
                    found_other: false,
                }
            }
        }
        impl<const ROLE: u8> MoveGen<Infallible> for MoveGenImpl<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 extend<I>(&mut self, iter: I) -> ControlFlow<Infallible>
            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),
                        }
                    }
                });
                ControlFlow::Continue(())
            }
        }
        let (role, promotion, from, to) = match san.inner {
            SanInner::Castle(CastlingSide::Short) => (
                Role::King,
                Role::King,
                Square::from_coords(File::E, self.0.turn().home_rank()).bitboard(),
                Square::from_coords(File::G, self.0.turn().home_rank()).bitboard(),
            ),
            SanInner::Castle(CastlingSide::Long) => (
                Role::King,
                Role::King,
                Square::from_coords(File::E, self.0.turn().home_rank()).bitboard(),
                Square::from_coords(File::C, self.0.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 moves = MoveGenImpl::<ROLE>::new(role, from, to);
            let ControlFlow::Continue(()) = position.generate_moves(&mut moves);
            match moves.found {
                None => Err(InvalidSan::Illegal),
                Some(raw) => match moves.found_other {
                    true => Err(InvalidSan::Ambiguous),
                    false => Ok(unsafe { Move::new_unchecked(position, raw) }),
                },
            }
        }
        map_role!(aux, role, self, promotion, from, to)
    }
}

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

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

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

impl RawMove {
    #[inline]
    pub fn from(&self) -> Square {
        self.from
    }
    #[inline]
    pub fn to(&self) -> Square {
        self.to
    }
    #[inline]
    pub 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]
    pub fn promotion(&self) -> Option<Role> {
        match self.kind {
            MoveType::PawnAdvancePromotion | MoveType::PawnAttackPromotion => Some(self.role),
            _ => None,
        }
    }
    #[inline]
    pub fn uci(&self) -> UciMove {
        UciMove {
            from: self.from(),
            to: self.to(),
            promotion: self.promotion(),
        }
    }
}

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

    #[inline]
    fn is_check(&mut self) -> ControlFlow<S> {
        ControlFlow::Continue(())
    }
    #[inline]
    fn en_passant_is_legal(&mut self) -> ControlFlow<S> {
        ControlFlow::Continue(())
    }
    fn extend<I>(&mut self, _iter: I) -> ControlFlow<S>
    where
        I: Iterator<Item = RawMove> + ExactSizeIterator,
    {
        ControlFlow::Continue(())
    }
}

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

    pub(crate) fn generate_moves<S, T>(&self, moves: &mut T) -> ControlFlow<S>
    where
        T: MoveGen<S>,
    {
        let global_mask_from = moves.from();
        let global_mask_to = moves.to();

        let Setup {
            bitboards: [p_b_q, n_b_k, r_q_k, w],
            turn,
            en_passant,
            castling_rights,
        } = self.0;

        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 = lookup::bishop(king_square, blockers);
        let y = lookup::rook(king_square, blockers);
        let checkers = lookup::pawn_attack(turn, king_square) & theirs.pawn()
            | lookup::knight(king_square) & theirs.knight()
            | x & theirs.bishop()
            | y & theirs.rook();

        if moves.roles(Role::King) && global_mask_from.contains(king_square) {
            let attacked = {
                let blockers = blockers ^ ours.king();
                theirs
                    .king()
                    .map(|sq| lookup::king(sq))
                    .chain(theirs.bishop().map(|sq| lookup::bishop(sq, blockers)))
                    .chain(theirs.rook().map(|sq| lookup::rook(sq, blockers)))
                    .chain(theirs.knight().map(|sq| lookup::knight(sq)))
                    .chain(core::iter::once(
                        theirs.pawn().trans(!forward).trans(Direction::East),
                    ))
                    .chain(core::iter::once(
                        theirs.pawn().trans(!forward).trans(Direction::West),
                    ))
                    .reduce_or()
            };
            // king moves
            moves.extend(
                (global_mask_to & lookup::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) {
                        moves.extend(core::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) {
                        moves.extend(core::iter::once(RawMove {
                            kind: MoveType::CastleLong,
                            from,
                            to,
                            role: Role::King,
                        }))?;
                    }
                }
            }
        }

        if checkers.len() > 1 {
            moves.is_check()?;
            return ControlFlow::Continue(());
        }

        let blockers_x_ray = blockers & !(x | y);
        let pinned = ((lookup::bishop(king_square, blockers_x_ray) & theirs.bishop())
            | (lookup::rook(king_square, blockers_x_ray) & theirs.rook()))
        .map(|sq| lookup::segment(king_square, sq))
        .reduce_or();

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

        // pawns
        if moves.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;
                moves.extend((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAdvance,
                    from: unsafe { to.trans_unchecked(!forward) },
                    to,
                    role: Role::Pawn,
                }))?;
                moves.extend(MoveAndPromote::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 | lookup::ray(king_square, kside)))
                        .trans(kside)
                        & them
                        & target_mask;
                moves.extend((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAttack,
                    from: unsafe { to.trans_unchecked(!kside) },
                    to,
                    role: Role::Pawn,
                }))?;
                moves.extend(MoveAndPromote::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 | lookup::ray(king_square, qside)))
                        .trans(qside)
                        & them
                        & target_mask;
                moves.extend((targets & !promotion).map(|to| RawMove {
                    kind: MoveType::PawnAttack,
                    from: unsafe { to.trans_unchecked(!qside) },
                    to,
                    role: Role::Pawn,
                }))?;
                moves.extend(MoveAndPromote::new((targets & promotion).map(|to| {
                    RawMove {
                        kind: MoveType::PawnAttackPromotion,
                        from: unsafe { to.trans_unchecked(!qside) },
                        to,
                        role: Role::Pawn,
                    }
                })))?;
            }
            // pawn double advances
            moves.extend(
                ((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 = lookup::pawn_attack(!turn, to) & ours.pawn();
                        let blockers = blockers ^ capture_square.bitboard();
                        let pinned = pinned
                            | (lookup::rook(
                                king_square,
                                blockers & !(lookup::rook(king_square, blockers)),
                            ) & theirs.rook())
                            .map(|sq| lookup::segment(king_square, sq))
                            .reduce_or();
                        for from in global_mask_from
                            & candidates
                            & (!pinned | lookup::segment(king_square, to))
                        {
                            moves.en_passant_is_legal()?;
                            moves.extend(core::iter::once(RawMove {
                                kind: MoveType::EnPassant,
                                from,
                                to,
                                role: Role::Pawn,
                            }))?;
                        }
                    }
                }
            }
        }

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

        if checker.is_some() {
            moves.is_check()?;
            return ControlFlow::Continue(());
        }

        // pinned pieces
        {
            let aux = |moves: &mut T, role, role_mask| {
                for from in global_mask_from & pinned & role_mask & *ours.get(role) {
                    moves.extend(
                        (global_mask_to & !us & pinned & lookup::line(king_square, from)).map(
                            |to| RawMove {
                                kind: MoveType::PieceMove,
                                from,
                                to,
                                role,
                            },
                        ),
                    )?;
                }
                ControlFlow::Continue(())
            };
            if moves.roles(Role::Bishop) {
                aux(moves, Role::Bishop, lookup::bishop_lines(king_square))?;
            }
            if moves.roles(Role::Rook) {
                aux(moves, Role::Rook, lookup::rook_lines(king_square))?;
            }
            if moves.roles(Role::Queen) {
                aux(moves, Role::Queen, !Bitboard::new())?;
            }
        }

        ControlFlow::Continue(())
    }

    #[inline]
    pub(crate) 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::from_coords(
                    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();
                let [p_b_q, _, _, w] = &mut setup.bitboards;
                *p_b_q ^= x;
                *w &= !x;
                aux_play_pawn_advance(setup, Role::Pawn, from, to);
            }
        }

        setup.turn = !setup.turn;
    }
}

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

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

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

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

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

pub(crate) struct MateMoveGenImpl {
    pub is_check: bool,
    pub is_mate: bool,
}
impl MateMoveGenImpl {
    #[inline]
    pub fn new() -> Self {
        Self {
            is_check: false,
            is_mate: true,
        }
    }
}
impl MoveGen<Infallible> for MateMoveGenImpl {
    #[inline]
    fn is_check(&mut self) -> ControlFlow<Infallible> {
        self.is_check = true;
        ControlFlow::Continue(())
    }
    #[inline]
    fn extend<I>(&mut self, iter: I) -> ControlFlow<Infallible>
    where
        I: Iterator<Item = RawMove> + ExactSizeIterator,
    {
        self.is_mate &= iter.len() == 0;
        ControlFlow::Continue(())
    }
}

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