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, creating an timestamped audit trail of an arbitrary data structure, 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 two type arguments (Transition and Conflict) and one method: apply(&self, 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.
4. If a conflict arises (i.e. if apply returns anything other than Ok(())), the state machine is not mutated.

#1 is enforced by Rust's type system, but it's your responsibility to satisfy the other three. 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 throw away previous states immediately when a local transition happens, because the server might accept a transition from another peer before accepting the one created locally. We need the old state in order to replay the transitions in the right order. In order to do this, the client keeps the entire chain of transitions from the last transition confirm by the server up to the most recent local transition.

Managing State

In this section, we will look at the core aper crate and how it represents data.

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. This is a good heuristic but not a guarantee, since a non-mut self could still use interior mutability.)

We can turn Counter into a state machine like this:

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

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

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

impl StateMachine for Counter {
    type Transition = CounterTransition;
    type Conflict = NeverConflict;

    fn apply(&self, event: &CounterTransition) -> Result<Counter, NeverConflict> {
        match event {
            CounterTransition::Add(i) => {
                Ok(Counter {value: self.value + i})
            }
            CounterTransition::Subtract(i) => {
                Ok(Counter {value: self.value - i})
            }
            CounterTransition::Reset => {
                Ok(Counter {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};
use serde::{Serialize, Deserialize};

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

#[derive(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 = atom.apply(&transition).unwrap();

    // 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, AtomRc};
use serde::{Serialize, Deserialize};

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

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: AtomRc::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, AtomRc};
use serde::{Serialize, Deserialize};

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

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: AtomRc::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 = item.apply(&mark_done).unwrap();
    item = item.apply(&fix_typo).unwrap();

    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 = 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, AtomRc};
use serde::{Serialize, Deserialize};
use std::default::Default;

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

impl ToDoListItem {
    pub fn new(label: String) -> Self {
        ToDoListItem {
            done: Atom::new(false),
            label: AtomRc::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 = to_do_list.apply(&dog_food_transition).unwrap();

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

	to_do_list = to_do_list.apply(&lunch_transition).unwrap();

	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 = to_do_list.apply(&emphasize_dog_food).unwrap();

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

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};
#[derive(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(Serialize, Deserialize, Clone, Debug, PartialEq)]
struct TicTacToeMove(usize);

use aper::{StateMachine};

#[derive(Serialize, Deserialize, Clone, Debug, PartialEq)]
enum TicTacToeConflict {
    GameAlreadyEnded,
    SquareAlreadyFilled,
}

impl StateMachine for TicTacToe {
    type Transition = TicTacToeMove;
    type Conflict = TicTacToeConflict;
    
    fn apply(&self, play: &TicTacToeMove) -> Result<TicTacToe, TicTacToeConflict> {
        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 Err(TicTacToeConflict::GameAlreadyEnded);
        };
        let TicTacToeMove(play_index) = play;
        if self.board[*play_index].is_some() {
            // Can't play over something that has already been played!
            return Err(TicTacToeConflict::SquareAlreadyFilled);
        }
        // Insert this play into the board.
        let mut board = self.board.clone();
        board[*play_index] = Some(this_player);
        
        // Check if the game has ended.
        if let Some(winner) = self.winner() {
            return Ok(TicTacToe {board, status: GameStatus::Won(winner)});
        } else if self.tie() {
            return Ok(TicTacToe {board, status: GameStatus::Tie});
        }

        // Update the next player.
        if Player::X == this_player {
            Ok(TicTacToe {board, status: GameStatus::NextPlayer(Player::O)})
        } else {
            Ok(TicTacToe {board, status: GameStatus::NextPlayer(Player::X)})
        }
    }
}