chess/formats/
fen.rs

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

chess/formats/
fen.rs
