sokoban-elements 0.2.1

mod errors;
mod plus_id;

use std::str::FromStr;

use ahash::AHashMap;
use errors::SokobanPlusInputKind;
pub use errors::{SokobanPlusSyntaxError, SokobanPlusSyntaxErrorKind};
use itertools::Itertools;
pub use plus_id::PlusID;
use regex::Regex;

use crate::{BoxID, GoalID};

/// Data for `Sokoban+` variant of game rules.
///
/// # `Sokoban+` rules
///
/// `Sokoban+` is slightly modified variant of game rules that changes game victory conditions.
///
/// In addition to [regular game piece identifiers](crate::BoxID), boxes and goals get additional
/// identifier, called `Sokoban+ ID`. This identifier can be a number, a color or any other kind a
/// of "tag".
///
/// Game objective then becomes the following: board is considered solved only when each box is
/// paired with goal and paired box and goal have the same `Sokoban+ ID`.
///
/// For example, any goal tagged with `Sokoban+ ID` of `9` must be paired with any box also tagged
/// as `9`.
///
/// Multiple boxes and goals may share same `Sokoban+ ID`, but the number of boxes with one
/// `Sokoban+ ID` must be equal to the number of goals with that same `Sokoban+ ID`.
///
/// Not all boxes and goals must have `Sokoban+ ID`. Box that doesn't have `Sokoban+ ID`, may be
/// paired with any goal that also doesn't have it.
///
/// For example:
///
/// | game piece ID | box Sokoban+ ID | goal Sokoban+ ID |
/// | ------------- | --------------- | ---------------- |
/// | 0             | Some(42)        | Some(42)         |
/// | 1             | None            | Some(24)         |
/// | 2             | None            | None             |
/// | 3             | Some(24)        | None             |
///
/// - box `0` must be paired with goal `0`
/// - box `1` must be paired with either goal `2` or goal `3`
/// - box `2` must be paired with either goal `2` or goal `3`
/// - box `3` must be paired with goal `1`
///
/// `Sokoban+` IDs for boxes and goals are defined by two sequences of integers called `boxorder`
/// and `goalorder`. `SokobanPlus` abstracts away working directly with `boxorder` and `goalorder`.
/// Instead, it provides API for
///
/// - [parsing Sokoban+ IDs](SokobanPlus::parsed()) from strings
/// - editing [`PlusID`](crate::PlusID) of individual game pieces directly
/// - exporting `boxorder` and `goalorder` back into strings
/// - exporting `boxorder` and `goalorder` as sequences of `Option<PlusID>`
///
/// `SokobanPlus` assignments are keyed to [`BoxID`] and [`GoalID`], which are reassigned by
/// scanning the board after editing. Mirroring, rotating, resizing, or trimming a board can
/// therefore silently invalidate its Sokoban+ data.
///
/// # Examples
///
/// `boxorder` and `goalorder` serialization / deserialization:
///
/// ```rust
/// use sokoban_elements::*;
///
/// # fn main() -> Result<(), SokobanPlusSyntaxError> {
/// let sokoban_plus = SokobanPlus::parsed("1 4 3 5", "5 3 4 1")?;
///
/// let boxorder = sokoban_plus.boxorder();
/// let goalorder = sokoban_plus.goalorder();
///
/// assert_eq!(boxorder, "1 4 3 5");
/// assert_eq!(goalorder, "5 3 4 1");
/// #     Ok(())
/// # }
/// ```
///
/// editing `Sokoban+ IDs`:
///
/// ```rust
/// use sokoban_elements::*;
///
/// # fn main() -> Result<(), PieceIdError> {
/// let mut sokoban_plus = SokobanPlus::new();
///
/// let box_id = BoxID::from(1_u8);
/// let plus_id = Some(PlusID::new(42)?);
///
/// sokoban_plus.set_box_plus_id(box_id, plus_id);
/// #     Ok(())
/// # }
/// ```
///
/// # Serde
///
/// With the `serde` feature, `SokobanPlus` is a pair of dense arrays with one slot per piece and
/// `null` where a piece has no `Sokoban+ ID`:
///
/// ```json
/// { "boxorder": [1, null, null, 2], "goalorder": [2, null, null, 1] }
/// ```
///
/// This deliberately does *not* reuse the textual [`boxorder()`](SokobanPlus::boxorder()) /
/// [`goalorder()`](SokobanPlus::goalorder()) forms, even though those round trip losslessly too.
/// The text encodes "no `Sokoban+ ID`" as the marker value `0`, and reading it back therefore
/// depends on which marker convention the reader picks - see
/// [`parsed_legacy()`](SokobanPlus::parsed_legacy()). The array form has no marker at all: absence
/// is `null` and every number is an ordinary ID, so the wire format carries no parse mode decision.
///
/// That is what a consumer in another language gets for free. Deserializing the array yields
/// `Option<Sokoban+ ID>` per piece directly, while the text would leave every such client
/// reimplementing this crate's marker rules - which is fragile.
///
/// Both fields may be omitted, trailing `null`s are never written, and unknown fields are rejected.
/// Deserialization goes through [`set_box_plus_id()`](SokobanPlus::set_box_plus_id()) /
/// [`set_goal_plus_id()`](SokobanPlus::set_goal_plus_id()), so piece indexes are bound checked
/// against [`BoxID`](crate::BoxID) and [`GoalID`](crate::GoalID).
#[derive(Debug, Clone, PartialEq, Default)]
pub struct SokobanPlus {
    boxorder:  AHashMap<u16, u16>,
    goalorder: AHashMap<u16, u16>,
}

impl SokobanPlus {
    const EXPLICIT_NO_PLUS_ID: u16 = 0;
    const LEGACY_EXPLICIT_NO_PLUS_ID: u16 = 99;

    /// Constructs "empty" `Sokoban+` instance where no boxes and no goals have `Sokoban+ ID`.
    pub fn new() -> Self {
        Self {
            boxorder:  AHashMap::default(),
            goalorder: AHashMap::default(),
        }
    }

    /// Parses serialized `Sokoban+` data.
    ///
    /// Each parsed [`PlusID`](crate::PlusID) must be integer in range `[0, PlusID::MAX]`. Other
    /// than that, parser doesn't enforce validation on `Sokoban+` data. It is perfectly fine to
    /// parse `boxorder` and `goalorder` that specify incomplete `Sokoban+ IDs`.
    ///
    /// For example, it will successfully parse `boxorder` and/or `goalorder` which define more
    /// `Sokoban+ IDs` than there are boxes on the board, or more IDs for boxes than IDs for goals.
    ///
    /// The validity of `SokobanPlus` is relevant only when it is used to start puzzle solving
    /// session. This crate doesn't implement puzzle solving, so it doesn't implement solving rules
    /// either. And part of those rules are conditions on validity of `Sokoban+` data. Therefore,
    /// this crate doesn't check validity of `SokobanPlus` at any time.
    ///
    /// # Grammar
    ///
    /// `Sokoban+ IDs` for some puzzle are expressed as two sequences of integers called `boxorder`
    /// and `goalorder`.
    ///
    /// - if zero is present in either `boxorder` or `goalorder`, it marks a box/goal that has no
    ///   `Sokoban+ ID`
    /// - if `boxorder` or `goalorder` contains less `Sokoban+ IDs` than there are boxes/goals on
    ///   game board, then remaining game pieces get no `Sokoban+ ID` - as if they'd been marked
    ///   with `0`
    ///
    /// For example, `boxorder = "13 24 0 122 1"` maps `Sokoban+` IDs for game with 7 boxes as
    /// following:
    ///
    /// | box ID | Sokoban+ ID |
    /// | ------ | ----------- |
    /// | 0      | Some(13)    |
    /// | 1      | Some(24)    |
    /// | 2      | None        |
    /// | 3      | Some(122)   |
    /// | 4      | Some(1)     |
    /// | 5      | None        |
    /// | 6      | None        |
    ///
    /// `boxorder` and `goalorder` may explicitly state that some piece doesn't have `Sokoban+ ID`
    /// using value `0` or omitting `Sokoban+ ID` for trailing positions. For example, following
    /// sequences:
    ///
    /// - `boxorder = "42 0 0 24"`
    /// - `goalorder = "42 24"`
    ///
    /// assign `Sokoban+ IDs` like this:
    ///
    /// | box/goal ID | box Sokoban+ ID | goal Sokoban+ ID |
    /// | ----------- | --------------- | ---------------- |
    /// | 0           | Some(42)        | Some(42)         |
    /// | 1           | None            | Some(24)         |
    /// | 2           | None            | None             |
    /// | 3           | Some(24)        | None             |
    ///
    /// Note that [type implementing Sokoban+ ID](crate::PlusID) doesn't allow value `0`. Instead of
    /// using value `0`, `SokobanPlus` uses `None`.
    ///
    /// `99` is an ordinary `Sokoban+ ID` here. Some old puzzles used it as a second "no
    /// `Sokoban+ ID`" marker; to read those, use
    /// [`parsed_legacy()`](SokobanPlus::parsed_legacy()).
    pub fn parsed(boxorder: &str, goalorder: &str) -> Result<Self, SokobanPlusSyntaxError> {
        Self::parsed_impl(boxorder, goalorder, true)
    }

    /// Same as [`parsed()`](SokobanPlus::parsed()), but with legacy behavior.
    ///
    /// For historical reasons, `Sokoban+` requires treating ID number `99` specially. In some old
    /// puzzles, `99` was used to represent `this piece doesn't have a Sokoban+ ID` value.
    ///
    /// For example, when parse by this method, these `Sokoban+` sequences:
    ///
    /// - `boxorder= 42 99 99 24`
    /// - `goalorder = 42 24`
    ///
    /// are interpreted as following:
    ///
    /// | box/goal ID | box Sokoban+ ID | goal Sokoban+ ID |
    /// | ----------- | --------------- | ---------------- |
    /// | 0           | Some(42)        | Some(42)         |
    /// | 1           | None            | Some(24)         |
    /// | 2           | None            | None             |
    /// | 3           | Some(24)        | None             |
    ///
    /// This optional legacy behavior may be selected only when parsing `boxorder` and `goalorder`.
    ///
    /// Editing `SokobanPlus` and exporting to `boxorder` and `goalorder` will not treat `99`
    /// specially:
    ///
    /// ```rust
    /// use sokoban_elements::*;
    ///
    /// # fn main() -> Result<(), PieceIdError> {
    /// let mut sokoban_plus = SokobanPlus::new();
    ///
    /// let box0 = BoxID::from(0_u8);
    /// let box1 = BoxID::from(1_u8);
    /// let plus_id = Some(PlusID::try_from(99_u16)?);
    ///
    /// sokoban_plus.set_box_plus_id(box0, None);
    /// sokoban_plus.set_box_plus_id(box1, plus_id);
    ///
    /// assert_eq!(sokoban_plus.get_box_plus_id(box0), None);
    /// assert_eq!(sokoban_plus.get_box_plus_id(box1), plus_id);
    ///
    /// let boxorder = sokoban_plus.boxorder();
    /// assert_eq!(boxorder, "0 99");
    /// #     Ok(())
    /// # }
    /// ```
    ///
    /// Therefore, to set [`PlusID`](crate::PlusID) of a piece to "doesn't have Sokoban+ ID" value,
    /// use `None`, not `99`. Setting it to `99` will designate `Sokoban+ ID` of 99 to given piece
    /// ID.
    pub fn parsed_legacy(boxorder: &str, goalorder: &str) -> Result<Self, SokobanPlusSyntaxError> {
        Self::parsed_impl(boxorder, goalorder, false)
    }

    #[expect(clippy::map_err_ignore)]
    fn parsed_impl(
        boxorder: &str, goalorder: &str, treat_99_as_plus_id: bool,
    ) -> Result<Self, SokobanPlusSyntaxError> {
        let boxorder =
            Self::parse_ids(boxorder, SokobanPlusInputKind::Boxorder, treat_99_as_plus_id)?;
        let goalorder =
            Self::parse_ids(goalorder, SokobanPlusInputKind::Goalorder, treat_99_as_plus_id)?;

        if boxorder.is_empty() && goalorder.is_empty() {
            return Ok(Self::new());
        }

        let mut retv = SokobanPlus::new();

        let mut process_ids = |data: Vec<Option<PlusID>>,
                               input_kind: SokobanPlusInputKind|
         -> Result<(), SokobanPlusSyntaxError> {
            for (idx, plus_id) in data.iter().enumerate() {
                if input_kind == SokobanPlusInputKind::Boxorder {
                    let box_id = BoxID::try_from(idx).map_err(|_| {
                        SokobanPlusSyntaxError::new(
                            0,
                            input_kind,
                            SokobanPlusSyntaxErrorKind::TooManyPlusIDs,
                            None,
                        )
                    })?;
                    retv.set_box_plus_id(box_id, *plus_id);
                } else {
                    let goal_id = GoalID::try_from(idx).map_err(|_| {
                        SokobanPlusSyntaxError::new(
                            0,
                            input_kind,
                            SokobanPlusSyntaxErrorKind::TooManyPlusIDs,
                            None,
                        )
                    })?;
                    retv.set_goal_plus_id(goal_id, *plus_id);
                }
            }

            Ok(())
        };

        process_ids(boxorder, SokobanPlusInputKind::Boxorder)?;
        process_ids(goalorder, SokobanPlusInputKind::Goalorder)?;

        Ok(retv)
    }

    /// Exports `Sokoban+ IDs` of boxes as the textual `boxorder` sequence.
    ///
    /// The sequence is dense: one position for each box from `0` up to the last box that has a
    /// `Sokoban+ ID`, with `0` in every position whose box has none. Boxes past that one are
    /// omitted entirely - per the [grammar](SokobanPlus::parsed()), a missing trailing position
    /// already means "no `Sokoban+ ID`". [`SokobanPlus::new()`] exports as the empty string.
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sokoban_elements::*;
    ///
    /// # fn main() -> Result<(), SokobanPlusSyntaxError> {
    /// let sokoban_plus = SokobanPlus::parsed("1 0 0 2", "")?;
    ///
    /// assert_eq!(sokoban_plus.boxorder(), "1 0 0 2");
    /// assert_eq!(sokoban_plus.goalorder(), "");
    /// #     Ok(())
    /// # }
    /// ```
    ///
    /// # Round trip
    ///
    /// `SokobanPlus::parsed(&sokoban_plus.boxorder(), &sokoban_plus.goalorder())` reproduces
    /// `sokoban_plus`. The invariant is on the value, not on the string: because trailing
    /// positions are omitted, re-exporting may produce a shorter string than was parsed.
    ///
    /// Reading the exported text back with [`parsed_legacy()`](SokobanPlus::parsed_legacy())
    /// instead is lossy for a [`PlusID`](crate::PlusID) of `99`, which that method reads as "no
    /// `Sokoban+ ID`".
    pub fn boxorder(&self) -> String {
        let data = Self::pieces_order(&self.boxorder);
        Self::print(&data)
    }

    /// Exports `Sokoban+ IDs` of goals as the textual `goalorder` sequence.
    ///
    /// See [`boxorder()`](SokobanPlus::boxorder()), which is its counterpart for boxes and
    /// documents the shape of both sequences.
    pub fn goalorder(&self) -> String {
        let data = Self::pieces_order(&self.goalorder);
        Self::print(&data)
    }

    /// `true` if there are no `Sokoban+ IDs` assigned to any boxes or goals.
    pub fn is_empty(&self) -> bool { self.boxorder.is_empty() && self.goalorder.is_empty() }

    /// `Sokoban+ IDs` assigned to boxes, as one dense slot per box: [`None`] where a box has no ID.
    ///
    /// The typed counterpart of [`boxorder()`](SokobanPlus::boxorder()), and the same expansion:
    /// interior gaps are padded, boxes past the last one that has an ID are omitted, and the result
    /// is independent of hash map iteration order. Where the textual form has to spell "no
    /// `Sokoban+ ID`" as a marker value, this one says [`None`] - so a reader needs to know nothing
    /// about the `0` / `99` conventions to decode it. That is why the serde wire format is built
    /// from this method rather than from the text.
    ///
    /// Position in the returned [`Vec`] is the box's [`BoxID`](crate::BoxID).
    ///
    /// # Examples
    ///
    /// ```rust
    /// use sokoban_elements::*;
    ///
    /// # fn main() -> Result<(), SokobanPlusSyntaxError> {
    /// let sokoban_plus = SokobanPlus::parsed("1 0 0 2", "2 1")?;
    ///
    /// assert_eq!(
    ///     sokoban_plus.box_plus_ids(),
    ///     vec![PlusID::new(1).ok(), None, None, PlusID::new(2).ok()]
    /// );
    /// assert_eq!(
    ///     sokoban_plus.goal_plus_ids(),
    ///     vec![PlusID::new(2).ok(), PlusID::new(1).ok()]
    /// );
    /// # Ok(())
    /// # }
    /// ```
    pub fn box_plus_ids(&self) -> Vec<Option<PlusID>> { Self::plus_ids(&self.boxorder) }

    /// `Sokoban+ IDs` assigned to goals, as one dense slot per goal.
    ///
    /// See [`box_plus_ids()`](SokobanPlus::box_plus_ids()), which is its counterpart for boxes and
    /// documents the shape of both.
    pub fn goal_plus_ids(&self) -> Vec<Option<PlusID>> { Self::plus_ids(&self.goalorder) }

    /// `Sokoban+ ID` assigned to a box, or [`None`] if it has none.
    pub fn get_box_plus_id(&self, box_id: BoxID) -> Option<PlusID> {
        self.boxorder
            .get(&box_id.into())
            .map(|val| PlusID::try_from(*val).ok())?
    }

    /// `Sokoban+ ID` assigned to a goal, or [`None`] if it has none.
    pub fn get_goal_plus_id(&self, goal_id: GoalID) -> Option<PlusID> {
        self.goalorder
            .get(&goal_id.into())
            .map(|val| PlusID::try_from(*val).ok())?
    }

    /// Sets `Sokoban+ ID` of a box, or clears it if [`None`] is given.
    pub fn set_box_plus_id(&mut self, box_id: BoxID, box_plus_id: Option<PlusID>) {
        if let Some(plus_id) = box_plus_id {
            self.boxorder.insert(box_id.into(), plus_id.into());
        } else {
            self.boxorder.remove(&box_id.into());
        }
    }

    /// Sets `Sokoban+ ID` of a goal, or clears it if [`None`] is given.
    pub fn set_goal_plus_id(&mut self, goal_id: GoalID, goal_plus_id: Option<PlusID>) {
        if let Some(plus_id) = goal_plus_id {
            self.goalorder.insert(goal_id.into(), plus_id.into());
        } else {
            self.goalorder.remove(&goal_id.into());
        }
    }

    /// There is no writer counterpart to [`parsed_legacy()`](SokobanPlus::parsed_legacy()):
    /// `boxorder` and `goalorder` are always written with `0` as the "no `Sokoban+ ID`" marker,
    /// never `99`. `print()` maps both `0` and a real [`PlusID`](crate::PlusID) of `99` to `"99"`
    /// and is therefore lossy for legacy Sokoban+.
    ///
    /// This behavior is by design - we want to allow intentional reading of legacy `Sokoban+` but
    /// newer writing it.
    fn print(data: &[u16]) -> String { data.iter().join(" ") }

    /// Expands a sparse map of `Sokoban+ IDs` into the dense sequence the textual `boxorder` /
    /// `goalorder` forms are made of, using [`EXPLICIT_NO_PLUS_ID`](Self::EXPLICIT_NO_PLUS_ID) for
    /// every piece that has no ID.
    ///
    /// Gaps must be padded, including interior ones: emitting only the values that are present
    /// would shift every later piece down and silently renumber it. Pieces past the last one that
    /// has an ID are omitted - per the [grammar](SokobanPlus::parsed()), a missing trailing
    /// position already means "no `Sokoban+ ID`".
    ///
    /// [`plus_ids()`](Self::plus_ids()) performs the same expansion in typed form, and the two are
    /// kept separate on purpose - see the `# Serde` section on [`SokobanPlus`] - so a change to one
    /// has to be mirrored in the other.
    fn pieces_order(data: &AHashMap<u16, u16>) -> Vec<u16> {
        match data.keys().max() {
            None => Vec::new(),
            Some(max_key) => {
                (0..=*max_key)
                    .map(|key| data.get(&key).copied().unwrap_or(Self::EXPLICIT_NO_PLUS_ID))
                    .collect()
            }
        }
    }

    /// Expands a sparse id map into a dense sequence, [`None`] for every unset piece.
    ///
    /// The typed twin of [`pieces_order()`](Self::pieces_order()): same padding of interior gaps,
    /// same omission of the trailing unset run, and just as independent of `AHashMap` iteration
    /// order. It carries no marker value, so it needs none of that method's `0` / `99` conventions.
    fn plus_ids(data: &AHashMap<u16, u16>) -> Vec<Option<PlusID>> {
        match data.keys().max() {
            None => Vec::new(),
            // `set_box_plus_id()` / `set_goal_plus_id()` and parsing are the only insertion points
            // and all of them go through a `PlusID`, so no stored value can be out of range and
            // `try_from` cannot fail here. `.ok()` is how `get_box_plus_id()` treats the same
            // value.
            Some(max_key) => {
                (0..=*max_key)
                    .map(|key| {
                        data.get(&key)
                            .and_then(|value| PlusID::try_from(*value).ok())
                    })
                    .collect()
            }
        }
    }

    /// Parses a textual sequence of `Sokoban+ IDs` into a dense vector, one slot per piece, with
    /// [`None`] where a piece has no ID.
    fn parse_ids(
        data: &str, kind: SokobanPlusInputKind, treat_99_as_plus_id: bool,
    ) -> Result<Vec<Option<PlusID>>, SokobanPlusSyntaxError> {
        let Ok(re) = Regex::new(r"[ \t,:;]+") else {
            unreachable!("internal bug, failed to create Regex instance from valid regex")
        };

        let mut retv: Vec<Option<PlusID>> = Vec::default();

        let mut last_end = 0;

        // Find all matches of the separator regex in the haystack
        for mat in re.find_iter(data) {
            let start = mat.start();
            let end = mat.end();

            // The text between the last match end and the current match start is a part of Sokoban+
            // ID
            if last_end != start {
                // println!("- Part: \"{}\" at position {}", part, last_end);
                retv.push(Self::parse_and_normalize_plus_id(
                    &data[last_end..start],
                    kind,
                    treat_99_as_plus_id,
                    last_end,
                )?);
            }

            // Update the last_end to the end of the current match (the separator)
            last_end = end;
        }

        // After the loop, the remaining text from the last_end to the end of the haystack is the
        // last part
        if last_end < data.len() {
            retv.push(Self::parse_and_normalize_plus_id(
                &data[last_end..],
                kind,
                treat_99_as_plus_id,
                last_end,
            )?);
        }

        Ok(retv)
    }

    /// Parses a single `Sokoban+ ID` from a string and normalizes it according to the rules of
    /// `Sokoban+` parsing.
    fn parse_and_normalize_plus_id(
        data: &str, input_kind: SokobanPlusInputKind, treat_99_as_plus_id: bool, pos: usize,
    ) -> Result<Option<PlusID>, SokobanPlusSyntaxError> {
        let raw_plus_id: u16 = u16::from_str(data).map_err(|e| {
            SokobanPlusSyntaxError::new(
                pos,
                input_kind,
                SokobanPlusSyntaxErrorKind::ParseIntError,
                Some(e),
            )
        })?;

        let normalized_raw_plus_id =
            if raw_plus_id == Self::LEGACY_EXPLICIT_NO_PLUS_ID && !treat_99_as_plus_id {
                Self::EXPLICIT_NO_PLUS_ID
            } else {
                raw_plus_id
            };

        if normalized_raw_plus_id == Self::EXPLICIT_NO_PLUS_ID {
            Ok(None)
        } else {
            match PlusID::new(normalized_raw_plus_id) {
                Ok(new_plus_id) => Ok(Some(new_plus_id)),
                Err(_) => {
                    unreachable!(
                        "internal bug, failed to create PlusID instance from already validated u16"
                    )
                }
            }
        }
    }
}

#[cfg(feature = "serde")]
mod serde_impl {
    use serde::de::Error as _;
    use serde::{Deserialize, Deserializer, Serialize, Serializer};

    use super::SokobanPlus;
    use crate::{BoxID, GoalID, PlusID};

    /// Wire format of [`SokobanPlus`]: one dense slot per piece, `null` where a piece has no
    /// `Sokoban+ ID`.
    #[derive(Serialize, Deserialize)]
    #[serde(rename = "SokobanPlus", deny_unknown_fields)]
    struct SokobanPlusRepr {
        #[serde(default)]
        boxorder: Vec<Option<PlusID>>,

        #[serde(default)]
        goalorder: Vec<Option<PlusID>>,
    }

    impl Serialize for SokobanPlus {
        fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
            // The wire format *is* the dense typed expansion, so this is the public accessor and
            // not a second copy of it.
            SokobanPlusRepr {
                boxorder:  self.box_plus_ids(),
                goalorder: self.goal_plus_ids(),
            }
            .serialize(serializer)
        }
    }

    impl<'de> Deserialize<'de> for SokobanPlus {
        fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
            let repr = SokobanPlusRepr::deserialize(deserializer)?;

            let mut retv = SokobanPlus::new();

            // Going through the setters keeps piece indexes bound checked by `BoxID` / `GoalID`,
            // exactly like parsing the textual form does.
            for (position, plus_id) in repr.boxorder.into_iter().enumerate() {
                if plus_id.is_some() {
                    let box_id = BoxID::try_from(position).map_err(D::Error::custom)?;
                    retv.set_box_plus_id(box_id, plus_id);
                }
            }

            for (position, plus_id) in repr.goalorder.into_iter().enumerate() {
                if plus_id.is_some() {
                    let goal_id = GoalID::try_from(position).map_err(D::Error::custom)?;
                    retv.set_goal_plus_id(goal_id, plus_id);
                }
            }

            Ok(retv)
        }
    }
}

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

    #[test]
    fn it_can_be_constructed_from_boxorder_and_goalorder() -> Result<(), SokobanPlusSyntaxError> {
        let sokoban_plus = SokobanPlus::parsed("1 2 3 4 5 6", "6 5 4 3 2 1")?;

        assert_eq!(sokoban_plus.boxorder(), "1 2 3 4 5 6");
        assert_eq!(sokoban_plus.goalorder(), "6 5 4 3 2 1");

        Ok(())
    }

    #[test]
    fn it_correctly_persists_sokoban_plus_ids() -> Result<(), SokobanPlusSyntaxError> {
        let sokoban_plus = SokobanPlus::parsed("1 1 1 2 2 3", "0 3 2 2 1 1 1")?;

        assert_eq!(sokoban_plus.boxorder.get(&0), Some(&1));
        assert_eq!(sokoban_plus.boxorder.get(&1), Some(&1));
        assert_eq!(sokoban_plus.boxorder.get(&2), Some(&1));
        assert_eq!(sokoban_plus.boxorder.get(&3), Some(&2));
        assert_eq!(sokoban_plus.boxorder.get(&4), Some(&2));
        assert_eq!(sokoban_plus.boxorder.get(&5), Some(&3));
        assert_eq!(sokoban_plus.boxorder.get(&6), None);

        assert_eq!(sokoban_plus.goalorder.get(&0), None);
        assert_eq!(sokoban_plus.goalorder.get(&1), Some(&3));
        assert_eq!(sokoban_plus.goalorder.get(&2), Some(&2));
        assert_eq!(sokoban_plus.goalorder.get(&3), Some(&2));
        assert_eq!(sokoban_plus.goalorder.get(&4), Some(&1));
        assert_eq!(sokoban_plus.goalorder.get(&5), Some(&1));
        assert_eq!(sokoban_plus.goalorder.get(&6), Some(&1));

        Ok(())
    }

    /// Only [`parsed_legacy()`](SokobanPlus::parsed_legacy()) reads `99` as "no `Sokoban+ ID`";
    /// [`parsed()`](SokobanPlus::parsed()) treats it as an ordinary ID.
    #[test]
    fn it_can_handle_legacy_default_plus_id() -> Result<(), SokobanPlusSyntaxError> {
        let sokoban_plus = SokobanPlus::parsed_legacy("99 99 3", "99 3 99")?;
        assert_eq!(sokoban_plus.boxorder.get(&0), None);
        assert_eq!(sokoban_plus.boxorder.get(&1), None);
        assert_eq!(sokoban_plus.boxorder.get(&2), Some(&3));
        assert_eq!(sokoban_plus.boxorder.get(&3), None);

        assert_eq!(sokoban_plus.goalorder.get(&0), None);
        assert_eq!(sokoban_plus.goalorder.get(&1), Some(&3));
        assert_eq!(sokoban_plus.goalorder.get(&2), None);
        assert_eq!(sokoban_plus.goalorder.get(&3), None);

        let sokoban_plus = SokobanPlus::parsed("99 99 3", "99 3 99")?;
        assert_eq!(sokoban_plus.boxorder.get(&0), Some(&99));
        assert_eq!(sokoban_plus.boxorder.get(&1), Some(&99));
        assert_eq!(sokoban_plus.boxorder.get(&2), Some(&3));
        assert_eq!(sokoban_plus.boxorder.get(&3), None);

        assert_eq!(sokoban_plus.goalorder.get(&0), Some(&99));
        assert_eq!(sokoban_plus.goalorder.get(&1), Some(&3));
        assert_eq!(sokoban_plus.goalorder.get(&2), Some(&99));
        assert_eq!(sokoban_plus.goalorder.get(&3), None);

        Ok(())
    }

    /// `99` used to be lost by the default parser, making the text round trip lossy for it.
    #[test]
    fn when_a_plus_id_is_99_it_round_trips() -> Result<(), Box<dyn std::error::Error>> {
        let mut sokoban_plus = SokobanPlus::new();
        sokoban_plus.set_box_plus_id(BoxID::from(1_u8), Some(PlusID::try_from(99_u16)?));

        assert_eq!(sokoban_plus.boxorder(), "0 99");
        assert_eq!(SokobanPlus::parsed(&sokoban_plus.boxorder(), "")?, sokoban_plus);

        // Reading it as a legacy sequence is the one way to lose it, and that is now opt in.
        assert!(SokobanPlus::parsed_legacy(&sokoban_plus.boxorder(), "")?.is_empty());

        Ok(())
    }

    #[test]
    fn it_allows_being_created_from_blank_strings() -> Result<(), SokobanPlusSyntaxError> {
        let result = SokobanPlus::parsed("", "")?;
        assert!(result.is_empty());
        Ok(())
    }

    #[test]
    fn it_setter_doesnt_treat_99_specially() -> Result<(), PieceIdError> {
        let mut sokoban_plus = SokobanPlus::default();

        let piece_id = BoxID::from(2_u8);
        let plus_id = Some(PlusID::try_from(99_u16)?);

        sokoban_plus.set_box_plus_id(piece_id, plus_id);

        assert_eq!(sokoban_plus.boxorder.get(&2), Some(&99));

        Ok(())
    }

    #[test]
    fn it_prints_correct_boxorder_and_goalorder() -> Result<(), PieceIdError> {
        let mut sokoban_plus = SokobanPlus::new();

        let box_id = BoxID::from(1_u8);
        let other_box_id = BoxID::from(4_u8);
        let goal_id = GoalID::from(3_u8);
        let plus_id = Some(PlusID::try_from(42_u16)?);
        let other_plus_id = Some(PlusID::try_from(7_u16)?);

        sokoban_plus.set_box_plus_id(box_id, plus_id);
        sokoban_plus.set_box_plus_id(other_box_id, other_plus_id);
        sokoban_plus.set_goal_plus_id(goal_id, plus_id);

        let boxorder = sokoban_plus.boxorder();
        let goalorder = sokoban_plus.goalorder();

        // Leading and interior gaps are padded, pieces past the last `Sokoban+ ID` are omitted.
        assert_eq!(boxorder, "0 42 0 0 7");
        assert_eq!(goalorder, "0 0 0 42");

        Ok(())
    }

    /// An interior gap must be padded with the explicit "no `Sokoban+ ID`" marker. Emitting only
    /// the values that are present shifts every later piece down by the size of the gap, silently
    /// renumbering boxes.
    #[test]
    fn it_pads_interior_gaps_in_boxorder_and_goalorder() -> Result<(), SokobanPlusSyntaxError> {
        let sokoban_plus = SokobanPlus::parsed("1 0 0 2", "0 1 0 2 0")?;

        assert_eq!(sokoban_plus.boxorder(), "1 0 0 2");
        assert_eq!(sokoban_plus.goalorder(), "0 1 0 2");

        Ok(())
    }

    /// The round trip invariant is on the value, not on the string: trailing "no `Sokoban+ ID`"
    /// positions are omitted by design, so re-printed text may be shorter than what was parsed.
    #[test]
    fn it_round_trips_through_boxorder_and_goalorder() -> Result<(), SokobanPlusSyntaxError> {
        let cases = [
            ("1 2 3", "3 2 1"),       // no gaps
            ("0 0 1 2", "1 2"),       // leading gap
            ("1 0 0 2", "2 0 0 1"),   // interior gap
            ("1 2 0 0", "0 0 2 1"),   // trailing gap
            ("0 1 0 2 0", "0 2 0 1"), // leading, interior and trailing gap
            ("", "1 2"),              // one side empty
            ("", ""),                 // both sides empty
        ];

        for (boxorder, goalorder) in cases {
            let sokoban_plus = SokobanPlus::parsed(boxorder, goalorder)?;
            let reparsed =
                SokobanPlus::parsed(&sokoban_plus.boxorder(), &sokoban_plus.goalorder())?;

            assert_eq!(reparsed, sokoban_plus, "failed for {boxorder:?} / {goalorder:?}");
        }

        Ok(())
    }

    /// Clearing a `Sokoban+ ID` removes the piece from the map (see
    /// [`set_box_plus_id()`](SokobanPlus::set_box_plus_id())), so the printed sequence must keep a
    /// slot for it.
    #[test]
    fn when_a_plus_id_is_cleared_the_later_pieces_keep_their_positions() -> Result<(), PieceIdError>
    {
        let mut sokoban_plus = SokobanPlus::new();

        sokoban_plus.set_box_plus_id(BoxID::from(0_u8), Some(PlusID::try_from(1_u16)?));
        sokoban_plus.set_box_plus_id(BoxID::from(1_u8), Some(PlusID::try_from(2_u16)?));
        sokoban_plus.set_box_plus_id(BoxID::from(2_u8), Some(PlusID::try_from(3_u16)?));

        sokoban_plus.set_box_plus_id(BoxID::from(1_u8), None);

        assert_eq!(sokoban_plus.boxorder(), "1 0 3");
        assert_eq!(sokoban_plus.get_box_plus_id(BoxID::from(2_u8)), PlusID::new(3).ok());

        Ok(())
    }

    #[test]
    fn when_there_are_no_plus_ids_the_order_is_blank() -> Result<(), PieceIdError> {
        let mut sokoban_plus = SokobanPlus::new();

        assert_eq!(sokoban_plus.boxorder(), "");
        assert_eq!(sokoban_plus.goalorder(), "");

        sokoban_plus.set_box_plus_id(BoxID::from(0_u8), Some(PlusID::try_from(1_u16)?));

        assert_eq!(sokoban_plus.boxorder(), "1");
        assert_eq!(sokoban_plus.goalorder(), "");

        Ok(())
    }

    #[cfg(feature = "serde")]
    mod serde {
        use std::error::Error;

        use super::*;

        fn round_tripped(sokoban_plus: &SokobanPlus) -> Result<SokobanPlus, Box<dyn Error>> {
            let json = serde_json::to_string(sokoban_plus)?;

            Ok(serde_json::from_str::<SokobanPlus>(&json)?)
        }

        #[test]
        fn it_round_trips_through_json() -> Result<(), Box<dyn Error>> {
            let sokoban_plus = SokobanPlus::parsed("1 4 3 5", "5 3 4 1")?;

            let parsed = round_tripped(&sokoban_plus)?;
            assert_eq!(parsed, sokoban_plus);
            assert_eq!(parsed.boxorder(), "1 4 3 5");
            assert_eq!(parsed.goalorder(), "5 3 4 1");

            Ok(())
        }

        #[test]
        fn it_serializes_as_dense_arrays() -> Result<(), Box<dyn Error>> {
            let mut sokoban_plus = SokobanPlus::new();
            sokoban_plus.set_box_plus_id(BoxID::from(0_u8), Some(PlusID::new(1)?));
            sokoban_plus.set_box_plus_id(BoxID::from(3_u8), Some(PlusID::new(2)?));

            assert_eq!(
                serde_json::to_string(&sokoban_plus)?,
                r#"{"boxorder":[1,null,null,2],"goalorder":[]}"#
            );

            Ok(())
        }

        /// A dropped interior gap shifts every later ID. The textual form pads them (see
        /// `it_pads_interior_gaps_in_boxorder_and_goalorder`), but nothing routes the array form
        /// through the textual one, and these tests only run under `--all-features` - so the array
        /// form needs a guard of its own.
        #[test]
        fn it_preserves_interior_gaps() -> Result<(), Box<dyn Error>> {
            let mut sokoban_plus = SokobanPlus::new();
            sokoban_plus.set_box_plus_id(BoxID::from(0_u8), Some(PlusID::new(1)?));
            sokoban_plus.set_box_plus_id(BoxID::from(3_u8), Some(PlusID::new(2)?));

            let parsed = round_tripped(&sokoban_plus)?;

            assert_eq!(parsed, sokoban_plus);
            assert_eq!(parsed.get_box_plus_id(BoxID::from(3_u8)), PlusID::new(2).ok());
            assert_eq!(parsed.get_box_plus_id(BoxID::from(1_u8)), None);

            Ok(())
        }

        /// `99` is a "no ID" marker only for readers that opt into it, via
        /// [`parsed_legacy()`](SokobanPlus::parsed_legacy()). The array form has no marker, so it
        /// always carries `99` as the ordinary [`PlusID`] it is.
        #[test]
        fn it_preserves_a_plus_id_of_99() -> Result<(), Box<dyn Error>> {
            let mut sokoban_plus = SokobanPlus::new();
            sokoban_plus.set_box_plus_id(BoxID::from(1_u8), Some(PlusID::new(99)?));

            let parsed = round_tripped(&sokoban_plus)?;

            assert_eq!(parsed, sokoban_plus);
            assert_eq!(parsed.get_box_plus_id(BoxID::from(1_u8)), PlusID::new(99).ok());

            Ok(())
        }

        #[test]
        fn when_sokoban_plus_is_empty_it_round_trips() -> Result<(), Box<dyn Error>> {
            let sokoban_plus = SokobanPlus::new();

            assert_eq!(
                serde_json::to_string(&sokoban_plus)?,
                r#"{"boxorder":[],"goalorder":[]}"#
            );
            assert!(round_tripped(&sokoban_plus)?.is_empty());

            Ok(())
        }

        #[test]
        fn when_orders_are_absent_they_default_to_empty() -> Result<(), Box<dyn Error>> {
            let sokoban_plus: SokobanPlus = serde_json::from_str("{}")?;

            assert!(sokoban_plus.is_empty());

            Ok(())
        }

        /// Output must not depend on `AHashMap` iteration order.
        #[test]
        fn it_serializes_deterministically() -> Result<(), Box<dyn Error>> {
            let sokoban_plus = SokobanPlus::parsed("1 4 3 5 0 2", "5 3 4 1 2 0")?;

            assert_eq!(
                serde_json::to_string(&sokoban_plus)?,
                serde_json::to_string(&sokoban_plus)?
            );

            Ok(())
        }

        #[test]
        fn it_rejects_a_plus_id_of_zero() {
            let result = serde_json::from_str::<SokobanPlus>(r#"{"boxorder": [1, 0]}"#);

            assert!(result.is_err());
        }

        /// Only the last slot holds an ID, so the piece index is the only thing that can be
        /// rejected here.
        #[test]
        fn it_rejects_piece_indexes_out_of_range() -> Result<(), Box<dyn Error>> {
            fn boxorder_of_len(len: usize) -> String {
                let mut slots = std::iter::repeat_n("null", len - 1).chain(std::iter::once("1"));

                format!(r#"{{"boxorder": [{}]}}"#, slots.join(","))
            }

            let largest_legal = usize::from(BoxID::MAX) + 1;

            let sokoban_plus: SokobanPlus = serde_json::from_str(&boxorder_of_len(largest_legal))?;
            assert_eq!(
                sokoban_plus.get_box_plus_id(BoxID::try_from(BoxID::MAX)?),
                PlusID::new(1).ok()
            );

            let result = serde_json::from_str::<SokobanPlus>(&boxorder_of_len(largest_legal + 1));
            let err = result.expect_err("index past BoxID::MAX must be rejected");
            assert!(
                err.to_string()
                    .contains(&(usize::from(BoxID::MAX) + 1).to_string())
            );

            Ok(())
        }

        #[test]
        fn it_rejects_unknown_fields() {
            let result = serde_json::from_str::<SokobanPlus>(r#"{"boxes": [1, 2]}"#);

            assert!(result.is_err());
        }
    }
}