The PuzzleStack
Status: Implemented | 2023
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 reloadSTACK_CHANGE_STATE
: Changes to answers or clues. Can be ignored by anyPlayGrid
orEditGrid
widgetsSTACK_CHANGE_METADATA
: Changes to puzzle metadata (such as the title). Can be ignored by most UI elementsSTACK_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() functionIf
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.
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-nullPuzzleStack::current
must always be non-null, and be part of the stackPuzzleStack::copy
must always be a private copy of the puzzle at current. It is not exposed anywhere else and kept pristine for storing history