The PuzzleStack

Status: implemented

The puzzle stack is used to keep track of mutations to a puzzle. It will be used for both the game and the editor. It mostly handles undo/redo, but also is used to let a UI know when to update itself. Since the actual puzzle, guesses, and state are all stateless and they don’t have a change signal. It solves the problem of sharing changes between all the different stages in the Edit dialog. It is also used in the Game itself for undo/redo.

There are two types of puzzle stacks: PUZZLE_STACK_PLAY and PUZZLE_STACK_EDIT. These are for the game and editor, respectively. They have similar behavior. The big change between the two is that PLAY will only track changes to the guesses, and will never expect changes to the crossword. For EDIT, all changes are valid.

Stages will push changes onto the stack every time their Puzzle changes, along with a hint as to the nature of the change. The PuzzleStack does not catch changes to the state that don’t effect the puzzle. So moving the cursor around doesn’t change the puzzle stack.

Note: The PuzzleStack object is different from EditPuzzleStack, which is a widget used by the autofill dialog

Motivation

One of the big challenges with the crossword editor is that small changes to the grid can have big ramifications elsewhere. So changing the size of the crossword can completely change the grid, and changing the grid, can renumber / reorder the clues. As a result, we use heuristics to try to update the crossword from stage to stage, and count on undo/redo from having changes be too destructive.

Changes

Every change has a type associated with it:

STACK_CHANGE_PUZZLE: A new puzzle was created, or a change to the puzzle dimensions happened. This means that all UI elements should rebuild their widgets.
STACK_CHANGE_GRID: Changes to the grid shape happened, which could lead to the clue count having changed. Anything that counts on the number of clues needs to reload
STACK_CHANGE_STATE: Changes to answers or clues. Can be ignored by any PlayGrid or EditGrid widgets
STACK_CHANGE_METADATA: Changes to puzzle metadata (such as the title). Can be ignored by most UI elements
STACK_CHANGE_GUESS: Changes to user guesses. Only used in play mode

Change Data

For many UI elements, some additional information is needed in order to fully restore the state. It could be a XwordState, or information about the widget status. Given that, we allow every caller to store some additional state on each frame that can be recalled using a unique key. To implement this, we create a singleton GObject per each stage to use as a simple un-typed hash.

The API

typedef enum _PuzzleStackType
{
  PUZZLE_STACK_PLAY,
  PUZZLE_STACK_EDIT,
} PuzzleStackType;

typedef enum _PuzzleStackStage
{
  EDIT_STAGE_GRID,     /* Fill in the grid with letters */
  EDIT_STAGE_CLUES,    /* Add clues to the puzzle */
  EDIT_STAGE_STYLE,    /* Customize the puzzle through any style changes*/
  EDIT_STAGE_METADATA, /* Set metadata for the puzzle */
} PuzzleStackStage;

typedef enum _PuzzleStackChangeType
{
  STACK_CHANGE_PUZZLE,
  STACK_CHANGE_GRID,
  STACK_CHANGE_STATE,
  STACK_CHANGE_METADATA,
  STACK_CHANGE_GUESS,
} PuzzleStackChangeType;

PuzzleStack          *puzzle_stack_new             (IPuzPuzzle            *initial_puzzle);
void                  puzzle_stack_push_change     (PuzzleStack           *puzzle_stack,
                                                    PuzzleStackChangeType  type,
                                                    IPuzPuzzle            *puzzle);
void                  puzzle_stack_set_data        (PuzzleStack           *puzzle_stack,
                                                    const gchar           *data_hint,
                                                    gpointer               data,
                                                    GDestroyNotify         clear_func);
gpointer              puzzle_stack_get_data        (PuzzleStack           *puzzle_stack,
                                                    const gchar           *data_hint);
IPuzPuzzle           *puzzle_stack_get_puzzle      (PuzzleStack           *puzzle_stack);
PuzzleStackChangeType puzzle_stack_get_change_type (PuzzleStack           *puzzle_stack);
gboolean              puzzle_stack_can_undo        (PuzzleStack           *puzzle_stack);
gboolean              puzzle_stack_can_redo        (PuzzleStack           *puzzle_stack);
void                  puzzle_stack_undo            (PuzzleStack           *puzzle_stack);
void                  puzzle_stack_redo            (PuzzleStack           *puzzle_stack);

and the signal:

void changed (PuzzleStack           *self,
              gboolean               new_frame,
              PuzzleStackChangeType  type);

The changed signal is emitted when the stack changes. new_frame is TRUE if a fresh puzzle change has occurred as opposed to going backwards and forwards through the history. This is useful so that the caller can decide to set new data as opposed to reading existing data.

Using the API

This API is deceptively complex and can have surprising interactions. As a rule of thumb any code manipulating the puzzles should make any changes to it and update its local state prior to pushing the puzzle onto the stack. Then, in the ::changed handler, it should do one of two things:

If new_frame is TRUE, load the puzzle and set it’s current internal state onto the stack using the set_data() function
If new_frame is FALSE, load the internal state from the get_data() function.

Internal Structure

The stack is stored as a GList going backwards at time. The HEAD of the list, stored at PuzzleStack::stack, contains the full list and is the most recent change. PuzzleStack::current points to the current location with the list in the undo/redo history. PuzzleStack::copy is a private deep copy of the puzzle contained within the current frame.

See this diagram for a visualization of this structure. This structure could represent a puzzle after a few changes.

PuzzleStack Structure
Example PuzzleStack after a few operations

In this example, the following steps have happened:

The user has selected a puzzle type in the editor and it loaded a template. The editor has created a new puzzle stack and loaded a copy of the template into it.
The user then made a change to the grid by placing a letter
The user made another change to the grid by placing another letter
The user then pressed C-z to undo that second letter placement.

Memory Management

The PuzzleStack has a ref for each puzzle in it. It is recommended that users of the PuzzleStack keep a ref to the stack, and not a ref to any individual puzzle within. Also, because the puzzle can and will get swapped, you shouldn’t store a puzzle with the data. Instead, XwordState hydrate/dehydrate is provided to store a state without an associated puzzle.

Invariants

It’s possible (though not useful) to have a puzzle-stack without a puzzle set. The only valid push to push a new puzzle onto it. Other changes aren’t allowed
Once you push a new puzzle onto a puzzle-stack, any old history/puzzles are lost.
Internal invariants. These are enforced in PuzzleStack:assert_invariants()
- PuzzleStack::stack must always be non-null
- PuzzleStack::current must always be non-null, and be part of the stack
- PuzzleStack::copy must always be a private copy of the puzzle at current. It is not exposed anywhere else and kept pristine for storing history