Introduction

Aper is a Rust library for representing data that can be read and written to by multiple users in real time.

Use-cases of Aper include managing the state of an application with real-time collaboration features and synchronizing the game state of a multiplayer game.

The core aper library implements the underlying data structures and algorithms, but is agnostic to the actual mechanism for transfering data on a network. The crates aper-yew and aper-serve provide a client and server implementation aimed at synchronizing state across multiple WebAssembly clients using WebSockets.

How it works

For Aper to synchronize state, it must be represented as a state machine. This means that:

  1. It implements the StateMachine trait, which has one type argument (Transition) and one method: apply(t: Transition).
  2. All changes to its internal state flow through this apply method.
  3. Updates to state are entirely deterministic. They may depend on the current state and any data that is contained in the transition value, and nothing else.

#1 is enforced by Rust's type system, but it's your responsibility to satisfy #2 and #3. In particular, accessing the current time, non-determistic random number generators, or external data in apply is a violation of #3.

Keeping State in Sync

In principle, the way that Aper keeps state in sync is pretty simple: when a client connects, they receive a full copy of the latest copy of the state. Thereafter, they receive a real-time stream of Transitions. Every client receives the same transitions in the same order, so their states are updated in lockstep. This is why it's important that apply is deterministic. If it were not, states could become divergent even if they received the same transition stream.

Note that for this model to work, the client can't immediately apply a transition to its local state, because the client doesn't know whether another client is sending the server a transition at the same time. The client has two options:

  • Wait to receive its own transition back from the server, and accept the latency associated with it. Depending on the use-case, a few hundred milliseconds of latency might be tolerable and the simpler model is easier to reason about.
  • Keep two copies of the state, called optimist and pessimist, as
    well as a FIFO queue stash of local transitions. As local transitions fire, push them to stash and proactively apply them to optimist. optimist is used to render the view, so local transitions appear automatically. When the server sends a transition, check if it is the next transition in our stash. If so, pop it from the stash and apply it to pessimist. Otherwise, we apply the server-sent transition to pessimist, then clone it and apply every transition in the stash to the clone. This clone becomes the new value of optimist, and the old value is discarded.

Aper implements both of these approaches.

Managing State

In this section, we will look at the core aper crate and how it represents data. Once we have a solid handle on how data is represented, we will turn to synchronizing it across the network in the next section.

Building a state machine

To solidify the concept of state machines, let's start with a simple example. Here's a simple data structure representing a counter. It stores an integer and gives us methods to modify it.

struct Counter {value: i64}

impl Counter {
    pub fn add(&mut self, i: i64) {
        self.value += i;
    }

    pub fn subtract(&mut self, i: i64) {
        self.value -= i;
    }

    pub fn reset(&mut self, i: i64) {
        self.value = 0;
    }
}

fn main() {}

By inspecting the code, you can see that Counter satisfies condition #3 of a state machine in Aper: its updates are deterministic. It does not, however, satisfy conditions #1 and #2: it does not implement StateMachine, and methods other than apply mutate the state.

(By the way, a good way to check if #2 is satisfied is to look for which methods take &mut self. In an Aper state machine, only apply should need a mutable reference to self.)

We can turn Counter into a state machine like this:

use aper::{StateMachine, Transition};
use serde::{Serialize, Deserialize};

#[derive(Serialize, Deserialize, Debug, Clone)]
struct Counter {value: i64}

#[derive(Transition, Serialize, Deserialize, Debug, Clone, PartialEq)]
enum CounterTransition {
   Add(i64),
   Subtract(i64),
   Reset,
}

impl StateMachine for Counter {
    type Transition = CounterTransition;

    fn apply(&mut self, event: CounterTransition) {
        match event {
            CounterTransition::Add(i) => {
                self.value += i;
            }
            CounterTransition::Subtract(i) => {
                self.value -= i;
            }
            CounterTransition::Reset => {
                self.value = 0;
            }
        }
    }
}
fn main() {}

Now, any attempt to modify the state of the counter must flow through apply as a CounterTransition. We could use CounterTransition's constructors directly, but the idiomatic approach that Aper encourages is to implement methods with the same signatures as our original modifiers but that return the Transition type:

use aper::{StateMachine, Transition};
use serde::{Serialize, Deserialize};

#[derive(Serialize, Deserialize, Debug, Clone)]
struct Counter {value: i64}

#[derive(Transition, Serialize, Deserialize, Debug, Clone, PartialEq)]
enum CounterTransition {
   Add(i64),
   Subtract(i64),
   Reset,
}

impl Counter {
    pub fn add(&self, i: i64) -> CounterTransition {
        CounterTransition::Add(i)
    }

    pub fn subtract(&self, i: i64) -> CounterTransition {
        CounterTransition::Subtract(i)
    }

    pub fn reset(&self, i: i64) -> CounterTransition {
        CounterTransition::Reset
    }
}
fn main() {}

Notice how these no longer require a mutable reference to self, since they do not actually make any changes, they just return an object representing the change. In fact, in this case they don't even read from self, but that would be allowed and comes in handy when we deal with more complex update logic.

I started by showing you how to implement your own state machine because I wanted you to see that it isn't scary, but implementing state machines from scratch isn't the only way to use Aper. In the next few sections, I'll show you how to build state machines by composing together primitives that Aper provides.

Constants and Atoms

Another way to build state machines is by combining other state machines. Aper ships with some built-in state machines which provide common patterns for managing state.

The simplest state machine is a Constant. It's a state machine whose transition has no exposed constructor, and therefore which can never be modified once it's created. It takes an initial value, and then stubbornly keeps that state for the rest of its life.

use aper::data_structures::Constant;

fn main() {
    // Construct a constant representing an i64.
    let int_constant = Constant::new(5);
    assert_eq!(&5, int_constant.value());

    // Construct a constant representing a String.
    let string_constant = Constant::new("Hi Aper".to_string());

    assert_eq!("Hi Aper", string_constant.value().as_str());
}

An Atom is similar to a Constant, except that it has a transition called ReplaceAtom.

It represents a value that can only be changed by replacing it entirely.

use aper::data_structures::Atom;
use aper::StateMachine;

fn main() {
    let mut atom = Atom::new(5);

    // Construct a new `ReplaceAtom` transition.
    let transition = atom.replace(6);

    // Remember, calling `.replace` does not actually change any
    // state -- only a call to `.apply` can do that.
    assert_eq!(&5, atom.value());
    
    atom.apply(transition);

    // Now the change takes effect.
    assert_eq!(&6, atom.value());
}

Derive macro

In the last section, we were introduced to the Atom state machine. If networks were infinitely fast, Atom might be the only state machine we ever needed: every time a user changed the state, we'd just send the new entire state to every other user and be done with it.

In practice, the reason we can't do this is that without infinitely fast networks, it's possible for different users to make conflicting changes. For example, let's say we represented a to-do list item as a state machine by wrapping it in an Atom:

use aper::data_structures::Atom;

struct ToDoListItem {
    done: bool,
    label: String,
}

type ToDoListAtom = Atom<ToDoListItem>;

Imagine that you and I are using a shared to-do list app that took this approach to representing state. Suppose we both modified this item at the same time: you marked it as done, and I fixed a typo in the label. Your edit hits the server first, so the server's state is briefly updated with the item marked as done. But my transition was sent at the same time as yours, and because an Atom update carries with it the entire value, it includes the old state of done. When my edit is applied, it has the effect of undoing yours. How rude.

To avoid this, we can push Atoms deeper down into the data structure. Aper facilitates this with a derive macro:

use aper::StateMachine;
use aper::data_structures::Atom;
use serde::{Serialize, Deserialize};

#[derive(StateMachine, Serialize, Deserialize, Debug, Clone, PartialEq)]
struct ToDoListItem {
    done: Atom<bool>,
    label: Atom<String>,
}

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: Atom::new(label),
        }
    }
}

Now, we can represent these same transitions in a way that they don't conflict.

use aper::StateMachine;
use aper::data_structures::Atom;
use serde::{Serialize, Deserialize};

#[derive(StateMachine, Serialize, Deserialize, Debug, Clone, PartialEq)]
struct ToDoListItem {
    done: Atom<bool>,
    label: Atom<String>,
}

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: Atom::new(label),
        }
    }
}

fn main() {
    let mut item = ToDoListItem::new("Buy gorceries".to_string());

    assert_eq!("Buy gorceries", item.label().value());
    assert_eq!(&false, item.done().value());

    let mark_done = item.map_done(|d| d.replace(true));
    let fix_typo = item.map_label(|d| d.replace("Buy groceries".to_string()));

    // Unlike with `ToDoListAtom`, the order in which the transitions 
    // are applied here does not matter.
    item.apply(mark_done);
    item.apply(fix_typo);

    assert_eq!("Buy groceries", item.label().value());
    assert_eq!(&true, item.done().value());
}

The methods map_done and map_label are generated by the derive macro by prepending map_ to each field. They take a single argument, which is a function from the type of that field (e.g. Atom<bool>) to a type of that field's transition (ReplaceAtom<bool>). They return a transition that can be applied to the parent struct (ToDoListItem), which combines the transition you constructed in the map with an indication of which field of the parent struct it is to be applied to.

To better understand this approach, it might be good to understand what we can't do. For one thing, we can't apply the field's ReplaceAtom transition directly to the ToDoListItem struct that contains it:

fn main() {
    let mut item = ToDoListItem::new("Buy gorceries".to_string());

    let mark_done = item.done().replace(true);

    // This will fail to compile because `done()` exposes a non-mutable
    // borrow of the Atom, but `apply()` requires a mutable borrow.
    item.done().apply(mark_done);
}

Nor can we apply the Atom's state change directly to the ToDoListItem:

fn main() {
    let mut item = ToDoListItem::new("Buy gorceries".to_string());

    let mark_done = item.done().replace(true);

    // This will fail to compile because `mark_done` is a
    // `ReplaceAtom<bool>` but `item.apply()` expects a
    // `ToDoListItemTransition`.
    item.apply(mark_done);
}

Lists

Another built-in data structure is the List. Lists are ordered sequence that you can iterate over, and arbitrarily insert/remove from. The values in a list are themselves state machines (if you never want to modify the inner state of values on a list, you can use Constant as a wrapper around the values.)

Let's use the ToDoListItem from the last section to create a ToDoList

use aper::data_structures::List;
use aper::StateMachine;
use aper::data_structures::Atom;
use serde::{Serialize, Deserialize};
use std::default::Default;

#[derive(StateMachine, Serialize, Deserialize, Debug, Clone, PartialEq)]
struct ToDoListItem {
    done: Atom<bool>,
    label: Atom<String>,
}

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: Atom::new(label),
        }
    }
}

fn main() {
	let mut to_do_list: List<ToDoListItem> = List::default();

	// Initially, the list is empty. We need to add things to it.

	// Append generates and returns an identifier which we can later
	// use to identify the record.
	// The methods `append`, `prepend`, and `insert` of `List`
	// return a `(id, transition)` pair, where the `id` can be used
	// to refer to the element after it has been inserted.
	let (dog_food_id, dog_food_transition) = to_do_list.append(
			ToDoListItem::new("Get dog food".to_string())
	);

	to_do_list.apply(dog_food_transition);

	let (lunch_id, lunch_transition) = to_do_list.append(
			ToDoListItem::new("Make lunch".to_string())
	);

	to_do_list.apply(lunch_transition);

	let emphasize_dog_food = to_do_list.map_item(dog_food_id,
		|it| it.map_label(|lbl| lbl.replace("Get DOG FOOD!".to_string()
		)));

	to_do_list.apply(emphasize_dog_food);

	let mark_lunch_done = to_do_list.map_item(lunch_id,
		|it| it.map_done(|done| done.replace(true)));
}

If this method of calling map_* seems tedious or doesn't quite “click”, don't worry. Later, when we actually implement the UI, we will see a design patter that allows us to eliminate the need for map_* methods.

Designing with state machines

When working with state machines, situations often come up where there are multiple ways to represent the same state. We saw this already with the ToDoListItem example, where the state could be either:

  1. A single Atom of a ToDoListItem struct with primitive types for fields, or
  2. A struct of two Atom fields, with each atom containing a primitive type, implementing StateMachine through the derive macro.

Both approaches are functionally equivalent when it comes to representing data at rest. They differ only in how merges are handled when (in this case) multiple fields are modified at the same time. For the to-do list example, we decided that #2 was the right approach, but there may be other data types for which #1 is the best approach.

This points to an important aspect of Aper that is central to its design philosophy. Aper's focus is on helping you to express the semantics of merging concurrent modifications to the same data structure. The underlying data structures Aper provides are just a means to that end.

Implementing a new state machine

So far, aside from the opening example, we've created state machines by composing primitive, pre-built state machines and using the derive macro. For total flexibility, you can also implement your own. This may be useful when you want to implement a shared data structure that can't be expressed efficiently with Aper's built-in data structures, or when your program state involves complex update logic. A great example of the latter is games, in which the games rules determine how state is updated.

To demonstrate this, let's implement a state machine representing the game Tic Tac Toe.

Tic Tac Toe has two players, X and O, which we can represent as an enum:

use serde::{Serialize, Deserialize};

#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum Player { X, O }

There are three possible states to a tic tac toe game:

  1. The game is underway and waiting on a particular player to play next.
  2. The game has ended with a winner.
  3. The game has ended in a tie, because the board is filled but no player has won.

We will represent all three of these with the GameStatus struct:

use serde::{Serialize, Deserialize};
#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum Player { X, O }

#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum GameStatus {
    /// Indicates that the game is ongoing and the provided
    /// player is next.
    NextPlayer(Player),

    /// Indicates that the game has been won by the given player.
    Won(Player),

    /// Indicates that the game has ended in a tie.
    Tie,
}

The board is a 3x3 grid. For simplicity, let's flatten this into an array with 9 entries. Each grid space can either be an X, an O, or empty. We can thus represent each grid cell as an Option<Player>.

The board cells correspond to indices in the flattened grid as follows:

0 | 1 | 2
--+---+--
3 | 4 | 5
--+---+--
6 | 7 | 8

Combining the GameStatus with the grid, we have a game state that looks like this:

use serde::{Serialize, Deserialize};
#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum Player { X, O }

#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum GameStatus {
    /// Indicates that the game is ongoing and the provided
    /// player is next.
    NextPlayer(Player),

    /// Indicates that the game has been won by the given player.
    Won(Player),

    /// Indicates that the game has ended in a tie.
    Tie,
}

#[derive(Serialize, Deserialize, Clone, Debug)]
struct TicTacToe {
    /// The current state of the board as a flattened 3x3 grid.
    board: [Option<Player>; 9],

    /// The next player to play, or `None` if the game has ended.
    status: GameStatus,
}

Next, we need to implement some of the game logic. We need to be able to construct a new game, and also to be able to check if a player has won or if the game has ended in a tie.

use serde::{Serialize, Deserialize};
#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum Player { X, O }

#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum GameStatus {
    /// Indicates that the game is ongoing and the provided
    /// player is next.
    NextPlayer(Player),

    /// Indicates that the game has been won by the given player.
    Won(Player),

    /// Indicates that the game has ended in a tie.
    Tie,
}

#[derive(Serialize, Deserialize, Clone, Debug)]
struct TicTacToe {
    /// The current state of the board as a flattened 3x3 grid.
    board: [Option<Player>; 9],

    /// The next player to play, or `None` if the game has ended.
    status: GameStatus,
}

impl TicTacToe {
    pub fn new() -> TicTacToe {
        TicTacToe {
            // Start with an empty board.
            board: [None; 9],
            // We'll default to player `O` going first.
            status: GameStatus::NextPlayer(Player::O),
        }
    }

    /// Given an array of three grid indices, check whether
    /// the same player has a mark in all three. If so, return
    /// the value of that player. Otherwise, return `None`.
    fn check_seq(&self, seq: &[usize; 3]) -> Option<Player> {
        let v1 = self.board[seq[0]]?;
        let v2 = self.board[seq[1]]?;
        let v3 = self.board[seq[2]]?;

        if (v1 == v2) && (v2 == v3) {
            Some(v1)
        } else {
            None
        }
    }

    /// Return the value of the player who has won if the
    /// game has ended, or else return `None`.
    fn winner(&self) -> Option<Player> {
        // To win tic tac toe, a player must occupy every
        // cell in either a column, row, or diagonal. There
        // are eight sets of three cells we need to check.
        let seq_to_check: [[usize; 3]; 8] = [
            // Three rows.
            [0, 1, 2],
            [3, 4, 5],
            [6, 7, 8],
            // Three columns.
            [0, 3, 6],
            [1, 4, 7],
            [2, 5, 8],
            // Two diagonals.
            [0, 4, 8],
            [2, 4, 6],
        ];

        for seq in &seq_to_check {
            let result = self.check_seq(seq);
            if result.is_some() {
                return result;
            }
        }

        None
    }

    /// Return `true` if the game has ended in a tie because
    /// there are no empty grid cells available to play.
    fn tie(&self) -> bool {
        self.board.iter().all(|d| d.is_some())
    }
}

The last step is to make TicTacToe a valid StateMachine. We'll start by creating the transition type, TicTacToeMove. Usually transition types are enums, but they don't have to be. In the case of Tic Tac Toe, there's only one type of move a player can make: to make their mark in an available grid space. We represent this one-and-only play with a TicTacToeMove struct, referencing the cell in play by the same flattened numbering scheme we used to implement the grid as a flat list.

use serde::{Serialize, Deserialize};
use aper::Transition;
#[derive(Transition, Serialize, Deserialize, Clone, Debug, PartialEq)]
struct TicTacToeMove(usize);

Finally, we can implement StateMachine for TicTacToe, using TicTacToeMove as the transition.

use serde::{Serialize, Deserialize};
#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum Player { X, O }

#[derive(Clone, Copy, Serialize, Deserialize, Debug, PartialEq)]
enum GameStatus {
    /// Indicates that the game is ongoing and the provided
    /// player is next.
    NextPlayer(Player),

    /// Indicates that the game has been won by the given player.
    Won(Player),

    /// Indicates that the game has ended in a tie.
    Tie,
}

#[derive(Serialize, Deserialize, Clone, Debug)]
struct TicTacToe {
    /// The current state of the board as a flattened 3x3 grid.
    board: [Option<Player>; 9],

    /// The next player to play, or `None` if the game has ended.
    status: GameStatus,
}
impl TicTacToe {
    pub fn new() -> TicTacToe {
        TicTacToe {
            // Start with an empty board.
            board: [None; 9],
            // We'll default to player `O` going first.
            status: GameStatus::NextPlayer(Player::O),
        }
    }

    /// Given an array of three grid indices, check whether
    /// the same player has a mark in all three. If so, return
    /// the value of that player. Otherwise, return `None`.
    fn check_seq(&self, seq: &[usize; 3]) -> Option<Player> {
        let v1 = self.board[seq[0]]?;
        let v2 = self.board[seq[1]]?;
        let v3 = self.board[seq[2]]?;

        if (v1 == v2) && (v2 == v3) {
            Some(v1)
        } else {
            None
        }
    }

    /// Return the value of the player who has won if the
    /// game has ended, or else return `None`.
    fn winner(&self) -> Option<Player> {
        // To win tic tac toe, a player must occupy every
        // cell in either a column, row, or diagonal. There
        // are eight sets of three cells we need to check.
        let seq_to_check: [[usize; 3]; 8] = [
            // Three rows.
            [0, 1, 2],
            [3, 4, 5],
            [6, 7, 8],
            // Three columns.
            [0, 3, 6],
            [1, 4, 7],
            [2, 5, 8],
            // Two diagonals.
            [0, 4, 8],
            [2, 4, 6],
        ];

        for seq in &seq_to_check {
            let result = self.check_seq(seq);
            if result.is_some() {
                return result;
            }
        }

        None
    }

    /// Return `true` if the game has ended in a tie because
    /// there are no empty grid cells available to play.
    fn tie(&self) -> bool {
        self.board.iter().all(|d| d.is_some())
    }
}
#[derive(Transition, Serialize, Deserialize, Clone, Debug, PartialEq)]
struct TicTacToeMove(usize);

use aper::{StateMachine, Transition};

impl StateMachine for TicTacToe {
    type Transition = TicTacToeMove;
    
    fn apply(&mut self, play: TicTacToeMove) {
        let this_player = if let GameStatus::NextPlayer(this_player)
                = self.status {
            this_player
        } else {
            // The game has already ended, don't accept another play.
            return;
        };
        let TicTacToeMove(play_index) = play;
        if self.board[play_index].is_some() {
            // Can't play over something that has already been played!
            return;
        }
        // Insert this play into the board.
        self.board[play_index] = Some(this_player);
        
        // Check if the game has ended.
        if let Some(winner) = self.winner() {
            self.status = GameStatus::Won(winner);
            return;
        } else if self.tie() {
            self.status = GameStatus::Tie;
            return;
        }

        // Update the next player.
        if Player::X == this_player {
            self.status = GameStatus::NextPlayer(Player::O);
        } else {
            self.status = GameStatus::NextPlayer(Player::X);
        }
    }
}