sokoban-elements 0.2.1

// Regenerate grammar:
//
// ```
// peginator-cli --railroad src/saved_game/grammar.peg > doc/img/saved_game_text_grammar.svg
// peginator-cli src/saved_game/grammar.peg | rustfmt +nightly > src/saved_game/grammar.rs
// ```
//
// Grammar is similar to following [pegsh](http://phrogz.net/js/pegsh/) grammar:
//
// ```
// grammar = (jump / pusher_selection / steps)+
// jump = "[" moves* "]"
// pusher_selection = "{" moves "}"
// steps = (moves / pushes)+
// moves = [dewnsulr\*]+
// pushes = [SRENWUDL]+
// ```

use itertools::Itertools;
use peginator::PegParser;

use super::grammar::{SavedGame as SavedGameGrammar, Section};
use super::{
    SavedGameSyntaxError, SavedGameSyntaxErrorKind, hexoban_move_characters,
    octoban_move_characters, sokoban_move_characters, trioban_move_characters,
};
use crate::rle::Rle;
use crate::{Direction, SolvingMode, Step, Tessellation};

pub struct Parser {}

impl Parser {
    pub const LOWER_L: char = 'l';
    pub const UPPER_L: char = 'L';

    pub const LOWER_U: char = 'u';
    pub const UPPER_U: char = 'U';

    pub const LOWER_R: char = 'r';
    pub const UPPER_R: char = 'R';

    pub const LOWER_D: char = 'd';
    pub const UPPER_D: char = 'D';

    pub const LOWER_W: char = 'w';
    pub const UPPER_W: char = 'W';

    pub const LOWER_E: char = 'e';
    pub const UPPER_E: char = 'E';

    pub const LOWER_N: char = 'n';
    pub const UPPER_N: char = 'N';

    pub const LOWER_S: char = 's';
    pub const UPPER_S: char = 'S';

    pub const CURRENT_POSITION: char = '*';
    pub const JUMP_BEGIN: char = '[';
    pub const JUMP_END: char = ']';
    pub const PUSHER_CHANGE_BEGIN: char = '{';
    pub const PUSHER_CHANGE_END: char = '}';

    pub const RLE_GROUP_START: char = Rle::GROUP_START;
    pub const RLE_GROUP_END: char = Rle::GROUP_END;
    pub const RLE_EOL: char = Rle::EOL;

    /// Is character one of move-without-pushing-a-box characters?
    ///
    /// Not all tessellations use or recognize all push step characters. This
    /// method recognizes them all, no matter what tessellation.
    pub const fn is_move_char(ch: char) -> bool {
        (ch == Self::LOWER_L)
            || (ch == Self::LOWER_U)
            || (ch == Self::LOWER_R)
            || (ch == Self::LOWER_D)
            || (ch == Self::LOWER_W)
            || (ch == Self::LOWER_E)
            || (ch == Self::LOWER_N)
            || (ch == Self::LOWER_S)
    }

    /// Is character one of move-with-pushing-a-box characters?
    ///
    /// Not all tessellations use or recognize all push step characters. This
    /// method recognizes them all, no matter what tessellation.
    pub const fn is_push_char(ch: char) -> bool {
        (ch == Self::UPPER_L)
            || (ch == Self::UPPER_U)
            || (ch == Self::UPPER_R)
            || (ch == Self::UPPER_D)
            || (ch == Self::UPPER_W)
            || (ch == Self::UPPER_E)
            || (ch == Self::UPPER_N)
            || (ch == Self::UPPER_S)
    }

    /// Is character one of save game markers?
    ///
    /// `SavedGame` markers are:
    ///
    /// - jump sequence begin and end marker
    /// - pusher selection sequence begin and end marker
    /// - marker for current move in save game replay
    pub const fn is_saved_game_marker(ch: char) -> bool {
        (ch == Self::JUMP_BEGIN)
            || (ch == Self::JUMP_END)
            || (ch == Self::PUSHER_CHANGE_BEGIN)
            || (ch == Self::PUSHER_CHANGE_END)
            || (ch == Self::CURRENT_POSITION)
    }

    pub fn print(steps: &[Step], tessellation: Tessellation, solving_mode: SolvingMode) -> String {
        let key_jump: u8 = 1;
        let key_pusher_change: u8 = 2;
        let key_other: u8 = 3;
        let mut contains_any_jumps = false;

        let moves_str: String = steps
            .iter()
            .chunk_by(|step| {
                match **step {
                    Step::Jump(_) => key_jump,
                    Step::PusherChange(_) => key_pusher_change,
                    _ => key_other,
                }
            })
            .into_iter()
            .map(|(key, group)| {
                let s: String = group
                    .copied()
                    .map(|s| {
                        Self::direction_to_char(
                            tessellation,
                            s.direction(),
                            matches!(s, Step::PushOrPull(_)),
                        )
                        .unwrap_or_else(|| {
                            unreachable!(
                                "Bug: failed to convert already validated Step direction \
                                    {:?} for tessellation {:?} into character representation.",
                                s.direction(),
                                tessellation
                            )
                        })
                    })
                    .collect();

                if key == key_jump {
                    contains_any_jumps = true;
                    format!("{}{}{}", Self::JUMP_BEGIN, s, Self::JUMP_END)
                } else if key == key_pusher_change {
                    format!("{}{}{}", Self::PUSHER_CHANGE_BEGIN, s, Self::PUSHER_CHANGE_END)
                } else {
                    s
                }
            })
            .collect();

        let first_is_jump = if steps.is_empty() {
            false
        } else {
            matches!(steps[0], Step::Jump(_))
        };

        if solving_mode == SolvingMode::Reverse && !first_is_jump {
            // Reverse saved games must start with jump, even if it is empty one
            format!("{}{}{}", Self::JUMP_BEGIN, Self::JUMP_END, moves_str)
        } else {
            moves_str
        }
    }

    /// Returns [`Step`] sequence, is parsed savegame reverse and position of
    /// current move marker.
    pub fn parse(
        input: &str, tessellation: Tessellation,
    ) -> Result<(Vec<Step>, bool, usize), SavedGameSyntaxError> {
        let decoded = Rle::decode(input, true).map_err(|e| {
            SavedGameSyntaxError::new_with_source(
                SavedGameSyntaxErrorKind::RleDecodingFailed,
                Some(e),
                None,
            )
        })?;

        let result = SavedGameGrammar::parse(&decoded).map_err(|e| {
            SavedGameSyntaxError::new_with_source(
                SavedGameSyntaxErrorKind::ParsingFailed,
                Some(e),
                Some(&decoded),
            )
        })?;

        let mut retv: Vec<Step> = vec![];
        let mut is_reverse = false;

        for section in result.sections {
            match section {
                Section::Steps(data) => {
                    Self::process_moves(tessellation, data.as_str(), &mut retv)?;
                }
                Section::Jump(data) => {
                    Self::process_jump(tessellation, data.as_str(), &mut retv)?;
                    is_reverse = true;
                }
                Section::PusherSelection(data) => {
                    Self::process_pusher_selection(tessellation, data.as_str(), &mut retv)?;
                }
            }
        }

        Ok((retv, is_reverse, Self::current_move_marker_index(input)))
    }

    fn direction_to_char(
        tessellation: Tessellation, direction: Direction, is_box_pushed: bool,
    ) -> Option<char> {
        match tessellation {
            Tessellation::Sokoban => {
                sokoban_move_characters::direction_to_char(direction, is_box_pushed)
            }
            Tessellation::Hexoban => {
                hexoban_move_characters::direction_to_char(direction, is_box_pushed)
            }
            Tessellation::Trioban => {
                trioban_move_characters::direction_to_char(direction, is_box_pushed)
            }
            Tessellation::Octoban => {
                Some(octoban_move_characters::direction_to_char(direction, is_box_pushed))
            }
        }
    }

    fn char_to_direction(
        tessellation: Tessellation, move_char: char,
    ) -> Result<Direction, SavedGameSyntaxError> {
        match tessellation {
            Tessellation::Sokoban => sokoban_move_characters::char_to_direction(move_char),
            Tessellation::Hexoban => hexoban_move_characters::char_to_direction(move_char),
            Tessellation::Trioban => trioban_move_characters::char_to_direction(move_char),
            Tessellation::Octoban => octoban_move_characters::char_to_direction(move_char),
        }
        .ok_or(SavedGameSyntaxError::new(
            SavedGameSyntaxErrorKind::InvalidStepCharacter {
                tessellation,
                input: move_char,
            },
        ))
    }

    fn process_moves(
        tessellation: Tessellation, data: &str, dest: &mut Vec<Step>,
    ) -> Result<bool, SavedGameSyntaxError> {
        for chr in data.chars() {
            if chr != Self::CURRENT_POSITION && !chr.is_whitespace() {
                let direction = Self::char_to_direction(tessellation, chr)?;
                dest.push(if chr.is_uppercase() {
                    Step::PushOrPull(direction)
                } else {
                    Step::Move(direction)
                });
            }
        }

        Ok(true)
    }

    fn process_jump(
        tessellation: Tessellation, data: &str, dest: &mut Vec<Step>,
    ) -> Result<bool, SavedGameSyntaxError> {
        for chr in data.chars() {
            if chr != Self::CURRENT_POSITION && !chr.is_whitespace() {
                let direction = Self::char_to_direction(tessellation, chr)?;
                dest.push(Step::Jump(direction));
            }
        }
        Ok(true)
    }

    fn process_pusher_selection(
        tessellation: Tessellation, data: &str, dest: &mut Vec<Step>,
    ) -> Result<bool, SavedGameSyntaxError> {
        for chr in data.chars() {
            if chr != Self::CURRENT_POSITION && !chr.is_whitespace() {
                let direction = Self::char_to_direction(tessellation, chr)?;
                dest.push(Step::PusherChange(direction));
            }
        }

        Ok(true)
    }

    fn current_move_marker_index(input: &str) -> usize {
        input
            .chars()
            .filter(|c| {
                Self::is_move_char(*c) || Self::is_push_char(*c) || *c == Self::CURRENT_POSITION
            })
            .enumerate()
            .find(|p| p.1 == Self::CURRENT_POSITION)
            .unwrap_or((0, ' '))
            .0
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_parses_saved_game_string() -> Result<(), SavedGameSyntaxError> {
        let input = "[drlu]rulD[]{lurd}";
        let (parsed, _, _) = Parser::parse(input, Tessellation::Sokoban)?;

        for (idx, direction) in [
            Direction::Down,
            Direction::Right,
            Direction::Left,
            Direction::Up,
        ]
        .iter()
        .enumerate()
        {
            let step = parsed[idx];
            let is_jump = matches!(step, Step::Jump(_));

            assert_eq!(step.direction(), *direction);
            assert!(is_jump);
        }

        for (idx, direction) in [Direction::Right, Direction::Up, Direction::Left]
            .iter()
            .enumerate()
        {
            let step = parsed[idx + 4];
            let is_move = matches!(step, Step::Move(_));

            assert_eq!(step.direction(), *direction);
            assert!(is_move);
        }

        let step = parsed[7];
        let is_push = matches!(step, Step::PushOrPull(_));

        assert_eq!(step.direction(), Direction::Down);
        assert!(is_push);

        for (idx, direction) in [
            Direction::Left,
            Direction::Up,
            Direction::Right,
            Direction::Down,
        ]
        .iter()
        .enumerate()
        {
            let step = parsed[idx + 8];
            let is_pusher_change = matches!(step, Step::PusherChange(_));

            assert_eq!(step.direction(), *direction);
            assert!(is_pusher_change);
        }

        Ok(())
    }

    #[test]
    fn it_correctly_finds_current_move_position() -> Result<(), SavedGameSyntaxError> {
        let input = "[drlu]rul*D[]{lurd}";
        let (_, _, current_idx) = Parser::parse(input, Tessellation::Sokoban)?;
        assert_eq!(current_idx, 7);

        let input = "[drlu]\t\r    rul*D[]{lurd}";
        let (_, _, current_idx) = Parser::parse(input, Tessellation::Sokoban)?;
        assert_eq!(current_idx, 7);

        Ok(())
    }

    #[test]
    fn it_forbids_pushes_in_jumps() {
        let input = "[lurD]";
        let parse_result = Parser::parse(input, Tessellation::Sokoban);
        assert!(parse_result.is_err());
    }

    #[test]
    fn it_forbids_pushes_in_pusher_selection() {
        let input = "{lurD}";
        let parse_result = Parser::parse(input, Tessellation::Sokoban);
        assert!(parse_result.is_err());
    }

    #[test]
    fn it_ignores_spaces_in_input() -> Result<(), SavedGameSyntaxError> {
        let input = "\t\r   l \t u\t\r rd \t\r\t\r";
        let (parsed, _, _) = Parser::parse(input, Tessellation::Sokoban)?;

        for (idx, direction) in [
            Direction::Left,
            Direction::Up,
            Direction::Right,
            Direction::Down,
        ]
        .iter()
        .enumerate()
        {
            let step = parsed[idx];
            assert_eq!(step.direction(), *direction);
        }

        Ok(())
    }
}