chess/formats/
fen.rs

1use core::{
2    fmt,
3    num::NonZeroU32,
4    ops::{Deref, DerefMut},
5    str::FromStr,
6};
7
8use crate::{
9    board::{self, Bitboard, Board, Piece, Player, PlayerTable},
10    finite::Empty as _,
11    position::{Castles, EnPassant, Parts, Position, Side},
12    square::{File, Rank, Square},
13};
14
15use super::{StrInput as Input, prelude::*};
16
17#[derive(Debug, thiserror::Error)]
18pub enum Error {
19    #[error("invalid FEN: {0}")]
20    Invalid(String),
21}
22
23pub type Result<T, E = Error> = core::result::Result<T, E>;
24
25// There's a choice to be made whether to require in-between whitespace or not,
26// we accept "compact" FEN without it. The "board" parser finishes once the
27// 64 squares are filled, so it won't "swallow" the turn parser's input.
28
29#[derive(
30    Clone, Copy, Debug, DeserializeFromStr, Eq, Ord, PartialEq, PartialOrd, SerializeDisplay,
31)]
32pub struct Fen(pub Position);
33
34impl Deref for Fen {
35    type Target = Position;
36
37    fn deref(&self) -> &Position {
38        &self.0
39    }
40}
41
42impl DerefMut for Fen {
43    fn deref_mut(&mut self) -> &mut Position {
44        &mut self.0
45    }
46}
47
48impl fmt::Display for Fen {
49    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
50        f.write_str(&self.0.fen())
51    }
52}
53
54impl FromStr for Fen {
55    type Err = Error;
56
57    fn from_str(text: &str) -> Result<Self> {
58        fen.parse(text).map_err(|_| Error::Invalid(text.to_string()))
59    }
60}
61
62impl From<Position> for Fen {
63    fn from(position: Position) -> Self {
64        Self(position)
65    }
66}
67
68impl From<Fen> for Position {
69    fn from(fen: Fen) -> Self {
70        fen.0
71    }
72}
73
74pub fn fen(input: &mut Input<'_>) -> ModalResult<Fen> {
75    let parts = parts.parse_next(input)?;
76    let position = parts.validate().map_err(|_| backtrack())?;
77    Ok(Fen(position))
78}
79
80// Lenient - missing suffix fields are filled with default values.
81// Missing castling rights are treated like "-", not inferred as KQkq.
82pub fn parts(input: &mut Input<'_>) -> ModalResult<Parts> {
83    backtrack_err(preceded(multispace0, position)).parse_next(input)
84}
85
86fn position(input: &mut Input<'_>) -> ModalResult<Parts> {
87    let board = board.parse_next(input)?;
88    let fields = fields.parse_next(input)?;
89    let castles = resolve_castles(board, fields.castle_rights).ok_or_else(backtrack)?;
90    Ok(Parts {
91        board,
92        turn: fields.turn,
93        castles,
94        en_passant: fields.en_passant,
95        reversible: fields.reversible,
96        round: fields.round,
97    })
98}
99
100impl Position {
101    pub fn from_fen(text: &str) -> Result<Self> {
102        let fen: Fen = text.parse()?;
103        Ok(fen.into())
104    }
105}
106
107impl Parts {
108    pub fn from_fen(text: &str) -> Result<Parts> {
109        parts.parse(text).map_err(|_| Error::Invalid(text.to_string()))
110    }
111}
112
113impl Parts {
114    pub fn apparent_fen(&self) -> String {
115        format!("{} {}", self.board.fen(), self.turn.fen())
116    }
117
118    pub fn fen(&self) -> String {
119        format!(
120            "{} {} {} {} {}",
121            self.apparent_fen(),
122            self.castles.fen(),
123            en_passant_square(self.en_passant),
124            self.reversible,
125            self.round
126        )
127    }
128
129    pub fn chess_fen(&self) -> Option<String> {
130        self.castles.chess_compatible().then(|| {
131            format!(
132                "{} {} {} {} {}",
133                self.apparent_fen(),
134                self.castles.chess_fen(),
135                en_passant_square(self.en_passant),
136                self.reversible,
137                self.round
138            )
139        })
140    }
141
142    pub fn shredder_fen(&self) -> String {
143        format!(
144            "{} {} {} {} {}",
145            self.apparent_fen(),
146            self.castles.shredder_fen(),
147            en_passant_square(self.en_passant),
148            self.reversible,
149            self.round
150        )
151    }
152}
153
154impl Position {
155    pub fn apparent_fen(&self) -> String {
156        format!("{} {}", self.board().fen(), self.turn().fen(),)
157    }
158
159    pub fn fen(&self) -> String {
160        self.parts().fen()
161    }
162
163    pub fn chess_fen(&self) -> Option<String> {
164        self.parts().chess_fen()
165    }
166
167    pub fn shredder_fen(&self) -> String {
168        self.parts().shredder_fen()
169    }
170
171    pub fn transposition_fen(&self) -> String {
172        format!(
173            "{} {} {}",
174            self.apparent_fen(),
175            self.castles().fen(),
176            en_passant_square(self.en_passant()),
177        )
178    }
179}
180
181impl Board {
182    pub fn fen(self) -> String {
183        let mut fen = String::new();
184
185        for rank in Rank::iter_rev() {
186            if rank != Rank::Eight {
187                fen.push('/');
188            }
189
190            let mut empty = 0;
191            for file in File::iter() {
192                let square = Square::new(file, rank);
193                if let Some(piece) = self.get(square) {
194                    if empty > 0 {
195                        fen.push(char::from_digit(empty, 10).unwrap());
196                        empty = 0;
197                    }
198                    fen.push(piece.char());
199                } else {
200                    empty += 1;
201                }
202            }
203            if empty > 0 {
204                fen.push(char::from_digit(empty, 10).unwrap());
205            }
206        }
207
208        fen
209    }
210}
211
212impl Player {
213    pub fn fen(self) -> char {
214        match self {
215            Player::Black => 'b',
216            Player::White => 'w',
217        }
218    }
219}
220
221impl Castles {
222    pub fn fen(self) -> String {
223        if self.chess_compatible() { self.chess_fen() } else { self.shredder_fen() }
224    }
225
226    pub fn chess_fen(self) -> String {
227        use Player::*;
228        use Side::*;
229
230        let mut fen = String::new();
231        if self.has(White, King) {
232            fen.push('K');
233        }
234        if self.has(White, Queen) {
235            fen.push('Q');
236        }
237        if self.has(Black, King) {
238            fen.push('k');
239        }
240        if self.has(Black, Queen) {
241            fen.push('q');
242        }
243        if fen.is_empty() {
244            fen.push('-');
245        }
246        fen
247    }
248
249    pub fn shredder_fen(self) -> String {
250        use Player::*;
251        use Side::*;
252
253        let mut fen = String::new();
254        for (player, side) in [(White, King), (White, Queen), (Black, King), (Black, Queen)] {
255            if let Some(file) = self.get(player, side) {
256                let letter = if player.is_white() { file.upper() } else { file.lower() };
257                fen.push(letter);
258            }
259        }
260        if fen.is_empty() {
261            fen.push('-');
262        }
263        fen
264    }
265}
266
267pub fn board(input: &mut Input<'_>) -> ModalResult<Board> {
268    let mut parts = board::Parts::default();
269    for rank in Rank::iter_rev() {
270        if rank != Rank::Eight {
271            '/'.parse_next(input)?;
272        }
273
274        parts |= board_row(rank).parse_next(input)?;
275    }
276    Board::new(parts).map_err(|_| backtrack())
277}
278
279fn board_row(rank: Rank) -> impl FnMut(&mut Input<'_>) -> ModalResult<board::Parts> {
280    move |input| {
281        let mut row = board::Parts::default();
282        let mut files = File::cursor();
283        loop {
284            if files.done() {
285                return Ok(row);
286            }
287
288            let char = board_fen_char.parse_next(input)?;
289            match char {
290                i @ '1'..='8' => {
291                    if !files.skip(i as u8 - b'0') {
292                        return Err(backtrack());
293                    }
294                }
295                piece => {
296                    let Some(file) = files.next() else {
297                        return Err(backtrack());
298                    };
299                    let square = Bitboard::from(Square::new(file, rank));
300                    let piece = Piece::panicky_from_char(piece);
301                    row.players[piece.player] |= square;
302                    row.roles[piece.role] |= square;
303                }
304            }
305        }
306    }
307}
308
309struct Fields {
310    turn: Player,
311    castle_rights: CastleRights,
312    en_passant: Option<EnPassant>,
313    reversible: u32,
314    round: NonZeroU32,
315}
316
317fn fields(input: &mut Input<'_>) -> ModalResult<Fields> {
318    // Missing suffix fields are defaulted. Once a field separator is present,
319    // cut_err prevents malformed field content from backtracking into "missing".
320    let counters = opt_field((reversible, opt_field(round)));
321    let suffix = opt_field((turn, opt_field((castle_rights, opt_field((en_passant, counters))))))
322        .parse_next(input)?;
323
324    let mut fields = Fields {
325        turn: Player::White,
326        castle_rights: CastleRights::empty(),
327        en_passant: None,
328        reversible: 0,
329        round: NonZeroU32::MIN,
330    };
331
332    let Some((turn, suffix)) = suffix else {
333        return Ok(fields);
334    };
335    fields.turn = turn;
336
337    let Some((castle_rights, suffix)) = suffix else {
338        return Ok(fields);
339    };
340    fields.castle_rights = castle_rights;
341
342    let Some((en_passant, suffix)) = suffix else {
343        return Ok(fields);
344    };
345    fields.en_passant = en_passant;
346
347    let Some((reversible, round)) = suffix else {
348        return Ok(fields);
349    };
350    fields.reversible = reversible;
351
352    if let Some(round) = round {
353        fields.round = round;
354    }
355
356    Ok(fields)
357}
358
359fn en_passant_square(en_passant: Option<EnPassant>) -> String {
360    en_passant.map_or_else(|| "-".to_string(), |square| Square::from(square).to_string())
361}
362
363fn board_fen_char(input: &mut Input<'_>) -> ModalResult<char> {
364    one_of(|c| "12345678pnbrkqPNBRKQ".contains(c)).parse_next(input)
365}
366
367fn turn(input: &mut Input<'_>) -> ModalResult<Player> {
368    one_of(|c| "bw".contains(c))
369        .map(|c| match c {
370            'b' => Player::Black,
371            'w' => Player::White,
372            _ => unreachable!(),
373        })
374        .parse_next(input)
375}
376
377type CastleRights = PlayerTable<Vec<CastleRight>>;
378
379#[derive(Clone, Copy, Eq, PartialEq)]
380enum CastleRight {
381    File(File),
382    Side(Side),
383}
384
385impl From<File> for CastleRight {
386    fn from(file: File) -> Self {
387        Self::File(file)
388    }
389}
390
391impl From<Side> for CastleRight {
392    fn from(side: Side) -> Self {
393        Self::Side(side)
394    }
395}
396
397fn resolve_castles(board: Board, rights: CastleRights) -> Option<Castles> {
398    let mut castles = Castles::empty();
399
400    for player in Player::iter() {
401        let rights = rights.get_ref(player);
402        if rights.is_empty() {
403            continue;
404        }
405
406        let king = board.king_of(player)?;
407        for &right in rights.iter() {
408            // Determine the side and file of the castle right.
409            // The side is determined in terms of the king's position.
410            // For the file:
411            //   - For Shredder FEN, the file is directly named
412            //   - For standard chess FEN, K/Q/k/q would directly answer both,
413            //     but we also want to support X-FEN, where we need to determine
414            //     the file from the backrank.
415            let (side, file) = match right {
416                CastleRight::File(file) => (Side::of_rook(king, file), file),
417                CastleRight::Side(side) => (side, x_fen_rook(board, player, king, side)?),
418            };
419            // Castle rights must be on different sides of the king
420            if castles.has(player, side) {
421                return None;
422            }
423            castles.set(player, side, file);
424        }
425    }
426
427    Some(castles)
428}
429
430// Resolve an X-FEN K/Q/k/q right to a rook file.
431// The right names the outermost same-colored rook on that side of the king.
432fn x_fen_rook(board: Board, player: Player, king: Square, side: Side) -> Option<File> {
433    let backrank_rooks = board
434        .rooks()
435        .intersection(board.player(player))
436        .intersection(Bitboard::from_rank(player.backrank()));
437    match side {
438        Side::King => backrank_rooks.intersection(king.east()).last(),
439        Side::Queen => backrank_rooks.intersection(king.west()).first(),
440    }
441    .map(Square::file)
442}
443
444fn castle_rights(input: &mut Input<'_>) -> ModalResult<CastleRights> {
445    alt(('-'.value(CastleRights::empty()), some_castles)).parse_next(input)
446}
447
448fn some_castles(input: &mut Input<'_>) -> ModalResult<CastleRights> {
449    use Player::*;
450
451    let mut rights = PlayerTable::default();
452    rights[White] = opt(player_castles(White)).parse_next(input)?.unwrap_or_default();
453    rights[Black] = opt(player_castles(Black)).parse_next(input)?.unwrap_or_default();
454
455    if rights.is_empty() {
456        return Err(backtrack());
457    }
458
459    Ok(rights)
460}
461
462fn player_castles<'i>(
463    player: Player,
464) -> impl FnMut(&mut Input<'i>) -> ModalResult<Vec<CastleRight>> {
465    move |input: &mut Input<'i>| {
466        let mut castle_letter = castle_letter(player);
467        let first = castle_letter.parse_next(input)?;
468        let mut rights = vec![first];
469
470        if let Some(second) = opt(&mut castle_letter).parse_next(input)? {
471            if first == second {
472                return Err(backtrack());
473            }
474            rights.push(second);
475        }
476
477        Ok(rights)
478    }
479}
480
481fn castle_letter<'i>(player: Player) -> impl FnMut(&mut Input<'i>) -> ModalResult<CastleRight> {
482    move |input: &mut Input<'i>| {
483        let letters = if player.is_black() { "abcdefghkq" } else { "ABCDEFGHKQ" };
484        one_of(|c| letters.contains(c))
485            .map(|letter: char| match letter.to_ascii_lowercase() {
486                'k' => Side::King.into(),
487                'q' => Side::Queen.into(),
488                'a'..='h' => File::panicky_from_char(letter).into(),
489                _ => unreachable!(),
490            })
491            .parse_next(input)
492    }
493}
494
495fn file(input: &mut Input<'_>) -> ModalResult<File> {
496    one_of(|c| "abcdefgh".contains(c)).map(File::panicky_from_char).parse_next(input)
497}
498
499fn en_passant(input: &mut Input<'_>) -> ModalResult<Option<EnPassant>> {
500    alt((
501        '-'.value(None),
502        terminated(file, '3').map(|file| Some(Square::new(file, Rank::Three).try_into().unwrap())),
503        terminated(file, '6').map(|file| Some(Square::new(file, Rank::Six).try_into().unwrap())),
504    ))
505    .parse_next(input)
506}
507
508fn reversible(input: &mut Input<'_>) -> ModalResult<u32> {
509    dec_uint.parse_next(input)
510}
511
512fn round(input: &mut Input<'_>) -> ModalResult<NonZeroU32> {
513    dec_uint.verify_map(NonZeroU32::new).parse_next(input)
514}
515
516fn opt_field<'i, O>(
517    parser: impl Parser<Input<'i>, O, ContextMode>,
518) -> impl Parser<Input<'i>, Option<O>, ContextMode> {
519    opt(preceded(space1, cut_err(parser)))
520}
521
522#[test]
523fn board_fen_example() {
524    use File::*;
525    use Player::*;
526    use Rank::*;
527    use Side::*;
528
529    // println!("{:?}", board_fen.parse("rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR").unwrap());
530    // println!(
531    //     "{:?}",
532    //     board_fen.parse_next(&mut "rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNRxxx").unwrap()
533    // );
534
535    let fen = "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq e3 1 3";
536    let position = parts.parse(fen).unwrap();
537    assert_eq!(position.turn, Black);
538    assert!(position.castles.has(Black, King));
539    assert!(position.castles.has(Black, Queen));
540    assert!(position.castles.has(White, King));
541    assert!(position.castles.has(White, Queen));
542    assert_eq!(position.en_passant.map(Into::into), Some(Square::new(E, Three)));
543    assert_eq!(position.reversible, 1);
544    assert_eq!(u32::from(position.round), 3);
545    assert_eq!(
546        position.validate().unwrap().fen(),
547        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq - 1 3"
548    );
549    assert_eq!(
550        Position::from_fen(fen).unwrap().fen(),
551        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq - 1 3"
552    );
553
554    let partial_fen = "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq e3";
555    let position = parts.parse(partial_fen).unwrap();
556    assert_eq!(position.turn, Black);
557    assert!(position.castles.has(Black, King));
558    assert!(position.castles.has(Black, Queen));
559    assert!(position.castles.has(White, King));
560    assert!(position.castles.has(White, Queen));
561    assert_eq!(position.en_passant.map(Into::into), Some(Square::new(E, Three)));
562    assert_eq!(position.reversible, 0);
563    assert_eq!(u32::from(position.round), 1);
564    assert_eq!(
565        position.validate().unwrap().fen(),
566        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq - 0 1"
567    );
568    assert_eq!(
569        Position::from_fen(partial_fen).unwrap().fen(),
570        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR b KQkq - 0 1"
571    );
572
573    let board_fen = "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR";
574    let position = parts.parse(board_fen).unwrap();
575    assert_eq!(position.turn, White);
576    assert!(!position.castles.has(Black, King));
577    assert!(!position.castles.has(Black, Queen));
578    assert!(!position.castles.has(White, King));
579    assert!(!position.castles.has(White, Queen));
580    assert_eq!(position.en_passant, None);
581    assert_eq!(position.reversible, 0);
582    assert_eq!(u32::from(position.round), 1);
583    assert_eq!(
584        position.validate().unwrap().fen(),
585        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR w - - 0 1"
586    );
587    assert_eq!(
588        Position::from_fen(board_fen).unwrap().fen(),
589        "rnbqkbnr/pp1ppppp/8/2p5/4P3/5N2/PPPP1PPP/RNBQKBNR w - - 0 1"
590    );
591}
592
593#[test]
594fn parse_shredder_castling() {
595    use File::*;
596    use Player::*;
597    use Side::*;
598
599    let fen = "bqnb1rkr/pp3ppp/3ppn2/2p5/5P2/P2P4/NPP1P1PP/BQ1BNRKR w HFhf - 2 9";
600    let position = Position::from_fen(fen).unwrap();
601    assert_eq!(position.castles().get(White, King), Some(H));
602    assert_eq!(position.castles().get(White, Queen), Some(F));
603    assert_eq!(position.castles().get(Black, King), Some(H));
604    assert_eq!(position.castles().get(Black, Queen), Some(F));
605    assert_eq!(position.fen(), fen);
606    assert_eq!(
607        position.transposition_fen(),
608        "bqnb1rkr/pp3ppp/3ppn2/2p5/5P2/P2P4/NPP1P1PP/BQ1BNRKR w HFhf -"
609    );
610}
611
612#[test]
613fn parse_x_fen_castling() {
614    use File::*;
615    use Player::*;
616    use Side::*;
617
618    let fen = "bbqnnrkr/pppppppp/8/8/8/8/PPPPPPPP/BBQNNRKR w KQkq - 0 1";
619    let position = Position::from_fen(fen).unwrap();
620
621    assert_eq!(position.castles().get(White, King), Some(H));
622    assert_eq!(position.castles().get(White, Queen), Some(F));
623    assert_eq!(position.castles().get(Black, King), Some(H));
624    assert_eq!(position.castles().get(Black, Queen), Some(F));
625    assert_eq!(position.fen(), "bbqnnrkr/pppppppp/8/8/8/8/PPPPPPPP/BBQNNRKR w HFhf - 0 1");
626}
627
628#[test]
629fn write_chess_and_shredder_castling() {
630    use File::*;
631    use Player::*;
632    use Side::*;
633
634    let mut castles = Castles::empty();
635    castles.set(White, King, H);
636    castles.set(White, Queen, F);
637    castles.set(Black, King, H);
638    castles.set(Black, Queen, F);
639
640    assert_eq!(castles.chess_fen(), "KQkq");
641    assert_eq!(castles.shredder_fen(), "HFhf");
642    assert_eq!(castles.fen(), "HFhf");
643    assert_eq!(Castles::chess().fen(), "KQkq");
644    assert_eq!(Castles::empty().fen(), "-");
645    assert_eq!(Castles::empty().chess_fen(), "-");
646    assert_eq!(Castles::empty().shredder_fen(), "-");
647}
648
649#[test]
650fn resolve_x_fen_castling() {
651    use File::*;
652    use Player::*;
653    use Side::*;
654
655    let board = Board::freestyle(crate::Scharnagl::new(0).unwrap());
656    let rights = castle_rights.parse("KQkq").unwrap();
657    let castles = resolve_castles(board, rights).unwrap();
658
659    assert_eq!(castles.get(White, King), Some(H));
660    assert_eq!(castles.get(White, Queen), Some(F));
661    assert_eq!(castles.get(Black, King), Some(H));
662    assert_eq!(castles.get(Black, Queen), Some(F));
663}
664
665#[test]
666fn resolve_shredder_castling() {
667    use File::*;
668    use Player::*;
669    use Side::*;
670
671    let board = Board::freestyle(crate::Scharnagl::new(0).unwrap());
672    let rights = castle_rights.parse("HFhf").unwrap();
673    let castles = resolve_castles(board, rights).unwrap();
674
675    assert_eq!(castles.get(White, King), Some(H));
676    assert_eq!(castles.get(White, Queen), Some(F));
677    assert_eq!(castles.get(Black, King), Some(H));
678    assert_eq!(castles.get(Black, Queen), Some(F));
679}
680
681#[test]
682fn reject_duplicate_castling_files() {
683    let fen = "bqnb1rkr/pp3ppp/3ppn2/2p5/5P2/P2P4/NPP1P1PP/BQ1BNRKR w HH - 2 9";
684    assert!(Parts::from_fen(fen).is_err());
685}
686
687#[test]
688fn reject_more_than_two_castling_files_per_player() {
689    let fen = "bqnb1rkr/pp3ppp/3ppn2/2p5/5P2/P2P4/NPP1P1PP/BQ1BNRKR w HFAh - 2 9";
690    assert!(Parts::from_fen(fen).is_err());
691}
692
693#[test]
694fn parse_exactly_one_board_rank() {
695    assert!(board_row(Rank::Eight).parse("rnbqkbnr").is_ok());
696    assert!(board_row(Rank::Eight).parse("8").is_ok());
697}
698
699#[test]
700fn reject_invalid_board_row_width() {
701    assert!(board_row(Rank::Eight).parse("7").is_err());
702    assert!(board_row(Rank::Eight).parse("9").is_err());
703    assert!(board_row(Rank::Eight).parse("rnbqkbnrr").is_err());
704    assert!(board_row(Rank::Eight).parse("8r").is_err());
705}
706
707#[test]
708fn reject_invalid_board_rank_width() {
709    assert!(Parts::from_fen("8/8/8/8/8/8/8/8 w - - 0 1").is_ok());
710    assert!(Parts::from_fen("8/8/8/8/8/8/8/7 w - - 0 1").is_err());
711    assert!(Parts::from_fen("8/8/8/8/8/8/8/9 w - - 0 1").is_err());
712    assert!(Parts::from_fen("8/8/8/8/8/8/8/8r w - - 0 1").is_err());
713}
chess/formats/fen.rs

chess/formats/
fen.rs
