Crate cola

cola is a Conflict-free Replicated Data Type (CRDT) for real-time collaborative editing of plain text documents.

CRDTs can be roughly divided into two categories: state-based and operation-based. cola falls in the latter category.

The basic idea behind an Operation-based CRDT – also known as a Commutative Replicated Data Type or CmRDT – is to design the core data structure and the operations applied to it in such a way that they commute, so that the order in which they’re applied at each peer doesn’t matter.

Commutativity makes the final state of the data structure only a function of its initial state and the set of operations applied to it, but not of the order in which they were applied. This ensures that once all peers have received all operations from all other peers they’re guaranteed to converge to the same final state.

In cola, the core data structure which represents the state of the document at each peer is the Replica, and the operations which the peers exchange to communicate their local edits are Insertions and Deletions.

If you’re new to this crate, reading the documentations of the Replica struct and its methods would be a good place to start.

For a deeper dive into cola’s design and implementation you can check out this blog post.

Example usage

use std::ops::Range;

use cola::{Deletion, Replica, ReplicaId};

struct Document {
    buffer: String,
    crdt: Replica,
}

struct Insertion {
    text: String,
    crdt: cola::Insertion,
}

impl Document {
    fn new<S: Into<String>>(text: S, replica_id: ReplicaId) -> Self {
        let buffer = text.into();
        let crdt = Replica::new(replica_id, buffer.len());
        Document { buffer, crdt }
    }

    fn fork(&self, new_replica_id: ReplicaId) -> Self {
        let crdt = self.crdt.fork(new_replica_id);
        Document { buffer: self.buffer.clone(), crdt }
    }

    fn insert<S: Into<String>>(
        &mut self,
        insert_at: usize,
        text: S,
    ) -> Insertion {
        let text = text.into();
        self.buffer.insert_str(insert_at, &text);
        let insertion = self.crdt.inserted(insert_at, text.len());
        Insertion { text, crdt: insertion }
    }

    fn delete(&mut self, range: Range<usize>) -> Deletion {
        self.buffer.replace_range(range.clone(), "");
        self.crdt.deleted(range)
    }

    fn integrate_insertion(&mut self, insertion: Insertion) {
        if let Some(offset) =
            self.crdt.integrate_insertion(&insertion.crdt)
        {
            self.buffer.insert_str(offset, &insertion.text);
        }
    }

    fn integrate_deletion(&mut self, deletion: Deletion) {
        let ranges = self.crdt.integrate_deletion(&deletion);
        for range in ranges.into_iter().rev() {
            self.buffer.replace_range(range, "");
        }
    }
}

fn main() {
    let mut peer_1 = Document::new("Hello, world", 1);
    let mut peer_2 = peer_1.fork(2);

    let delete_comma = peer_1.delete(5..6);
    let insert_exclamation = peer_2.insert(12, "!");

    peer_1.integrate_insertion(insert_exclamation);
    peer_2.integrate_deletion(delete_comma);

    assert_eq!(peer_1.buffer, "Hello world!");
    assert_eq!(peer_2.buffer, "Hello world!");
}

Feature flags

• encode: enables the encode and decode methods on Replica (disabled by default);

• serde: enables the Serialize and Deserialize impls for Insertion, Deletion and EncodedReplica (disabled by default).

Structs

Anchor

A stable reference to a position in a Replica.

BackloggedDeletions

An iterator over the backlogged deletions that are ready to be applied to a Replica.

BackloggedInsertions

An iterator over the backlogged insertions that are ready to be applied to a Replica.

Deletion

A deletion in CRDT coordinates.

EncodedReplica

A Replica encoded into a compact binary format suitable for transmission over the network.

Insertion

An insertion in CRDT coordinates.

Replica

A CRDT for text.

Text

A range of text inserted into a Replica.

Enums

AnchorBias

A bias to use when creating an Anchor.

DecodeError

The type of error that can occur when decodeing an EncodedReplica.

Type Aliases

Length

The length of a piece of text according to some user-defined metric.

ProtocolVersion

The version of the protocol cola uses to represent EncodedReplicas and CrdtEdits.

ReplicaId

A unique identifier for a Replica.