# Undo

Source: https://zafnok.github.io/shuyi-engine/learn/tutorial/05-undo/

A puzzle needs undo: one wrong push, and the level can't be won. This step adds it, in two
parts. The game needs a new action, since "undo" isn't one of the engine's six. And it needs to
remember what happened, which is where commands pay off again.

![After a push and an undo, the box and the player are back where they started, and the help line names the undo key.](https://zafnok.github.io/shuyi-engine/tutorial-tries/undone/before.png)

| File | What changes |
| ---- | ------------ |
| `crates/game/src/action.rs` | New: the game's own actions |
| `crates/game/files/keymap.ron` | A key and a button for Undo |
| `crates/game/src/board.rs` | Keeps a history, and takes back moves |
| `lib.rs`, `title.rs`, `stages.rs`, `tests/it/main.rs` | `UiAction` becomes `Action` |
| `shuyi.ron` | Says `action.rs` is allowed to name a key |
| `crates/game/files/en.ron` | The help line mentions undo |
| `crates/game/tests/board.rs` | A test of undo |

## The game's own actions

So far, your game has used `UiAction`, the engine's six ready-made moves. A game that wants more
writes its own list. Make `crates/game/src/action.rs`:

```rust
//! What a player can ask for: `UiAction`'s six moves and Undo, every one
//! rebindable, their default keys and buttons in `files/keymap.ron`.

use serde::{Deserialize, Serialize};
use shuyi::assets::keymap::{ActionSet, Chord, Key, UiAction};

/// Everything a player can ask for.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
pub enum Action {
    /// Walk up, or move a menu's focus up.
    Up,
    /// Walk down, or move a menu's focus down.
    Down,
    /// Walk left.
    Left,
    /// Walk right.
    Right,
    /// Choose a menu item.
    Confirm,
    /// Go back.
    Cancel,
    /// Take back the last move.
    Undo,
}

/// The keys every keymap has on top of its own: plain `Escape` cancels.
const FIXED_KEYS: [(Chord, Action); 1] = [(Chord::plain(Key::Escape), Action::Cancel)];

impl ActionSet for Action {
    /// No two actions share a key.
    type Group = ();

    const ALL: &'static [Self] = &[
        Self::Up,
        Self::Down,
        Self::Left,
        Self::Right,
        Self::Confirm,
        Self::Cancel,
        Self::Undo,
    ];

    fn name(self) -> &'static str {
        match self {
            Self::Up => "Up",
            Self::Down => "Down",
            Self::Left => "Left",
            Self::Right => "Right",
            Self::Confirm => "Confirm",
            Self::Cancel => "Cancel",
            Self::Undo => "Undo",
        }
    }

    /// The four moves and Undo repeat while held.
    fn is_repeatable(self) -> bool {
        !matches!(self, Self::Confirm | Self::Cancel)
    }

    /// Every action must keep a key: the game can't be played without one.
    fn is_required(self) -> bool {
        true
    }

    fn is_rebindable(self) -> bool {
        true
    }

    fn group(self) {}

    /// What it means to the engine's widgets: Undo means nothing to them.
    fn ui(self) -> Option<UiAction> {
        match self {
            Self::Up => Some(UiAction::Up),
            Self::Down => Some(UiAction::Down),
            Self::Left => Some(UiAction::Left),
            Self::Right => Some(UiAction::Right),
            Self::Confirm => Some(UiAction::Confirm),
            Self::Cancel => Some(UiAction::Cancel),
            Self::Undo => None,
        }
    }

    fn fixed_keys() -> &'static [(Chord, Self)] {
        &FIXED_KEYS
    }
}

```

This looks long, but it's nearly all a list of facts about seven things. The enum lists the
actions, keeping the same six names, so the keymap and the title still read the same. Then
`ActionSet` is the trait the engine uses to learn about them:

- `ALL` is every action, in order, and `name` gives each one's name in the keymap file.
- `is_repeatable` says whether it repeats while held. `!matches!(self, Self::Confirm | Self::Cancel)`
  reads as "this is not Confirm or Cancel": you wouldn't want a held key to confirm ten times.
- `is_required` and `is_rebindable` say the player can change each key, but can't leave one without
  a key at all.
- `group` is for actions allowed to share a key. There are none, so it's `()`.
- `ui` says what each means to the engine's own menus. That's how menus keep working with your own
  actions: your `Confirm` is their `Confirm`, and `Undo` means nothing to them.
- `fixed_keys` gives keys no player can move: Escape always cancels.

> **Rust:** in an `impl`, `Self` is the type it's for, so `Self::Up` is `Action::Up`. `&'static
> [Self]` is a borrowed list of `Action` that lasts for the whole program.

> **Shuyi:** the one file that may name a key by hand is this one, for that fixed Escape. In
> `shuyi.ron`, tell the key check about it, with this line in `check_keys`:
> `key_files: ["crates/game/src/action.rs"],`

Now, swap the type everywhere. Add `pub mod action;` to `lib.rs`, with
`use crate::action::Action;` below its other `use` lines. (`crate` means "this crate's own code".)
Then, replace `UiAction` with `Action` in `lib.rs`, `title.rs`, `stages.rs`, `board.rs`, and
`tests/it/main.rs`. Your editor's find-and-replace is the tool for this. Each of those files also
needs `use crate::action::Action;`, or in the test, `use game::action::Action;`. The compiler
will list each one it can't find.

This is that generic from step 1 paying off: `BasicData<Action, stages::Own>` is the same form,
filled in differently, and the whole engine now works with your actions.

Give Undo its default key in `files/keymap.ron`, inside the `keys` of the layout, and its button
in the same file's `pad`, as `"Undo": ["West"],`:

```ron
                "Undo": ["u"],
```

In the board, every action now counts, so `actions` gets simpler:

```rust
    /// Every action of the game.
    fn actions(&self) -> Option<Vec<Action>> {
        Some(Action::ALL.to_vec())
    }
```

And your help line, in `en.ron`:

```ron
    // The board.
    "board.help": "{Cursor} walk · {Undo} undo · {Cancel} back",
    "board.help.won": "Solved! {Undo} undo · {Cancel} back",
```

Here's what never naming a key buys you. Change the key in the keymap, and the words follow:

In `crates/game/files/keymap.ron`:

```diff
- "Undo": ["u"],
+ "Undo": ["r"],
```

![The help line says u undo.](https://zafnok.github.io/shuyi-engine/tutorial-tries/undo-key/before.png)

![The help line says r undo: the words follow the keymap.](https://zafnok.github.io/shuyi-engine/tutorial-tries/undo-key/after.png)

## History

How would you write undo? You could save a copy of the whole state on every move. In a small
puzzle, that would work. There's a neater way.

> **Shuyi:** a **`History`** is the state a level started in, and every command since. That's all
> it holds, because that's all you need: since the rules always give the same result for the same
> commands, you can get any earlier moment by starting again from the beginning and replaying.
> This property has a name, **determinism**, and it's why rules may have no clock, no floats, and
> no `HashSet`. It's also how replays, bug reports and online play work.

The board keeps a history beside the puzzle:

```rust
/// The board screen.
#[derive(Debug)]
pub struct Board {
    /// The level's name.
    name: String,
    /// The rules' state.
    pub puzzle: Puzzle,
    /// The level's first state and every command since.
    pub history: History<Puzzle>,
}
```

In `Board::new`, start it from the first state, with `history: History::new(puzzle.clone()),` before
the `puzzle,` line. `.clone()` makes a copy: the history keeps its first state forever, while the
puzzle goes on to change. You need `use shuyi::core::History;` at the top.

> **Rust:** **ownership**. Each value in Rust has one owner, and handing a value to a function hands
> over ownership: you can't use it again afterwards. So if `History::new` was given `puzzle` itself,
> the next line couldn't use it. `clone` makes a second one. Here the compiler's error would tell you
> "value used after being moved", and that's what it means. You'll meet that error sooner or later, so
> now you know how to read it.

It records only the commands the rules accepted, so a walk into a wall is no move:

```rust
    /// Sends `command` to the rules. A refused one changes nothing.
    fn send(&mut self, command: Command) {
        if self.puzzle.apply(&command).is_ok() {
            self.history.push(command);
        }
    }
```

Undo rewinds it, replaying every command but the last. The rules are deterministic, so this always
gives the same state:

```rust
    /// Takes back the last move, if there is one.
    fn undo(&mut self) {
        if let Some(last) = self.history.len().checked_sub(1)
            && let Ok(puzzle) = self.history.rewind_to(last)
        {
            self.puzzle = puzzle;
        }
    }
```

> **Rust:** `checked_sub(1)` subtracts, and gives `None` if the answer would go below zero, as it
> would here with no moves made. `if let ... && let ...` needs both to succeed, so the body runs only
> if there's a move to take back, and the rewind worked. Pressing undo at the start just does nothing.

And the board's `update` calls it:

```rust
    fn update(&mut self, _: &mut Ctx<Data>, input: &FrameInput<Action>) -> Transition<Data> {
        for &action in &input.actions {
            match action {
                Action::Up => self.send(Command::Step(Dir::Up)),
                Action::Down => self.send(Command::Step(Dir::Down)),
                Action::Left => self.send(Command::Step(Dir::Left)),
                Action::Right => self.send(Command::Step(Dir::Right)),
                Action::Undo => self.undo(),
                Action::Cancel => return Transition::Pop,
                Action::Confirm => {}
            }
        }
        Transition::None
    }
```

Notice that this `match` lists every action, with no `_` arm. So if you add an eighth action later,
the compiler will send you here to decide what it does. A catch-all would have quietly ignored it.

To see how the undo depends on that number, take back two moves at a time:

In `crates/game/src/board.rs`:

```diff
- self.history.len().checked_sub(1)
+ self.history.len().checked_sub(2)
```

![After two steps and one undo, the player has gone back one step.](https://zafnok.github.io/shuyi-engine/tutorial-tries/undo-two/before.png)

![After two steps and one undo, the player has gone back both, to where they started.](https://zafnok.github.io/shuyi-engine/tutorial-tries/undo-two/after.png)

## The test

```rust
#[test]
fn undo_takes_back_a_push_and_nothing_before_the_start() {
    let mut h = on_board();
    let start = board(&h).puzzle.clone();
    h.keys("Right");
    assert_ne!(board(&h).puzzle, start);
    h.keys("u");
    assert_eq!(board(&h).puzzle, start);
    h.keys("u");
    assert_eq!(board(&h).puzzle, start);
}
```

This is a neat test: it keeps a copy of the first state, and after a push and an undo, the whole state
must equal it, with `assert_eq!`. That's only possible since `Puzzle` derives `PartialEq`. The second
`h.keys("u")` checks that undoing at the start is harmless.

## What you learned

- **Rust:** ownership and `clone`, `crate::`, and `checked_sub`.
- **Game idea:** determinism, and how replaying commands can rebuild any moment.
- **Shuyi:** `ActionSet`, and `History`.

[Chapter 3](https://zafnok.github.io/shuyi-engine/learn/book/actions/index.md#actions-of-a-game-s-own) has more on a game's own actions, and
[chapter 6](https://zafnok.github.io/shuyi-engine/learn/book/rules-as-commands/index.md#history-and-undo) on history. Next: one level isn't a
game.