Struct cola::Replica

pub struct Replica { /* private fields */ }

A CRDT for text.

Like all other text CRDTs it allows multiple peers on a distributed network to concurrently edit the same text document, making sure that they all converge to the same final state without relying on a central server to coordinate the edits.

However, unlike many other CRDTs, a Replica doesn’t actually store the text contents itself. This allows to decouple the text buffer from the CRDT machinery needed to handle concurrent edits and guarantee convergence.

Put another way, a Replica is a pure CRDT that doesn’t know anything about where the text is actually stored. This is great because it makes it very easy to use it together with any text data structure of your choice: simple Strings, gap buffers, piece tables, ropes, etc.

How to distribute Replicas between peers.

When starting a new collaborative editing session, the first peer initializes its Replica via the new method, encodes it and sends the result to the other peers in the session. If a new peer joins the session later on, one of the peers already in the session can encode their Replica and send it to them.

How to integrate remote edits.

Every time a peer performs an edit on their local buffer they must inform their Replica by calling either inserted or deleted. This produces Insertions and Deletions which can be sent over to the other peers using the network layer of your choice.

When a peer receives a remote Insertion or Deletion they can integrate it into their own Replica by calling either integrate_insertion or integrate_deletion, respectively. The output of those methods tells the peer where in their local buffer they should apply the edit, taking into account all the other edits that have happened concurrently.

Basically, you tell your Replica how your buffer changes, and it tells you how your buffer should change when receiving remote edits.

Implementations

impl Replica

pub fn backlogged_deletions(&mut self) -> BackloggedDeletions<'_>

The integrate_deletion method is not able to immediately produce the offset range(s) to be deleted if the Deletion is itself dependent on some context that the Replica doesn’t yet have. When this happens the Deletion is stored in an internal backlog of edits that can’t be processed yet, but may be in the future.

This method returns an iterator over all the backlogged deletions which are now ready to be applied to your buffer.

The BackloggedDeletions iterator yields the same kind of offset ranges that integrate_deletion would have produced had the Deletion been integrated right away.

It’s very important for the ranges to be deleted in the exact same order in which they were yielded by the iterator. If you don’t your buffer could permanently diverge from the other peers.

Examples

// A buffer with the text "Hello" is replicated between three peers.
let mut replica1 = Replica::new(1, 5);
let mut replica2 = replica1.fork(2);
let mut replica3 = replica2.fork(3);

// Peer 1 inserts " world!" at the end of the buffer, and after
// integrating the insertion peer 2 deletes "world", leaving only
// "Hello!".
let insert_spc_world_excl = replica1.inserted(5, 7);
let _ = replica2.integrate_insertion(&insert_spc_world_excl);
let delete_world = replica2.deleted(5..11);

// Peer 3 receives the deletion, but it can't integrate it right away
// because it doesn't have the context it needs. The deletion is stored
// in the backlog.
let ranges = replica3.integrate_deletion(&delete_world);

assert!(ranges.is_empty());

// After peer 3 receives the " world!" insertion from peer 1 it can
// finally integrate the deletion.
let _ = replica3.integrate_insertion(&insert_spc_world_excl);

let mut deletions = replica3.backlogged_deletions();
assert_eq!(deletions.next(), Some(vec![5..11]));
assert_eq!(deletions.next(), None);

pub fn backlogged_insertions(&mut self) -> BackloggedInsertions<'_>

The integrate_insertion method is not able to immediately produce an offset if the Insertion is itself dependent on some context that the Replica doesn’t yet have. When this happens the Insertion is stored in an internal backlog of edits that can’t be processed yet, but may be in the future.

This method returns an iterator over all the backlogged insertions which are now ready to be applied to your buffer.

The BackloggedInsertions iterator yields (Text, Length) pairs containing the Text to be inserted and the offset at which it should be inserted.

It’s very important for the insertions to be applied in the exact same order in which they were yielded by the iterator. If you don’t your buffer could permanently diverge from the other peers.

Examples

// The buffer at peer 1 is "ab".
let mut replica1 = Replica::new(1, 2);

// A second peer joins the session.
let mut replica2 = replica1.fork(2);

// Peer 1 inserts 'c', 'd' and 'e' at the end of the buffer.
let insert_c = replica1.inserted(2, 1);
let insert_d = replica1.inserted(3, 1);
let insert_e = replica1.inserted(4, 1);

// For some reason, the network layer messes up the order of the edits
// and they get to the second peer in the opposite order. Because each
// edit depends on the previous one, peer 2 can't merge the insertions
// of the 'd' and the 'e' until it sees the 'c'.
let none_e = replica2.integrate_insertion(&insert_e);
let none_d = replica2.integrate_insertion(&insert_d);

assert!(none_e.is_none());
assert!(none_d.is_none());

// Finally, peer 2 receives the 'c' and it's able merge it right away.
let offset_c = replica2.integrate_insertion(&insert_c).unwrap();

assert_eq!(offset_c, 2);

// Peer 2 now has all the context it needs to merge the rest of the
// edits that were previously backlogged.
let mut backlogged = replica2.backlogged_insertions();

assert!(matches!(backlogged.next(), Some((_, 3))));
assert!(matches!(backlogged.next(), Some((_, 4))));

pub fn create_anchor(&self, at_offset: Length, with_bias: AnchorBias) -> Anchor

Creates a new Anchor at the given offset, with the given bias.

You can think of an Anchor as a sticky line cursor that you can attach to a specific position in a text document, and that automatically moves when the text around it changes to make sure that it always refers to the same position.

An offset alone is not enough to create an Anchor because it doesn’t uniquely identify a position in the document. For example, the offset 1 inside "ab" could either refer to the right side of 'a' or to the left side of 'b'. If we insert a 'c' between the two characters, how should the Anchor move?

To resolve this ambiguity, this method requires you to specify an AnchorBias. This tells the Replica whether the Anchor should stick to the left or to the right side of the position at the given offset.

Panics

Panics if the offset is out of bounds (i.e. greater than the current length of your buffer).

Examples

// The buffer is "ab".
let mut replica = Replica::new(1, 2);

// We create two anchors at the same offset but with different biases.
let right_of_a = replica.create_anchor(1, AnchorBias::Left);
let left_of_b = replica.create_anchor(1, AnchorBias::Right);

// Now we insert a 'c' between the two characters.
let _ = replica.inserted(1, 1);

// When we resolve the anchors we see that the first one has stayed at
// the same offset, while the second one has moved to the right.
assert_eq!(replica.resolve_anchor(right_of_a).unwrap(), 1);
assert_eq!(replica.resolve_anchor(left_of_b).unwrap(), 2);

Anchors can still be resolved even if the position they refer to has been deleted. In this case they will resolve to the offset of the closest position that’s still visible.

// The buffer is "Hello world".
let mut replica = Replica::new(1, 11);

let right_of_r = replica.create_anchor(9, AnchorBias::Left);

// " worl" is deleted, the buffer is now "Hellod".
let _ = replica.deleted(5..10);

// The anchor can still be resolved, and it now points to `5`, i.e.
// between the 'o' and the 'd'.
assert_eq!(replica.resolve_anchor(right_of_r).unwrap(), 5);

There are two special cases to be aware of:

• when the offset is zero and the bias is AnchorBias::Left, the returned Anchor will always resolve to zero;

• when the offset is equal to the length of the buffer and the bias is AnchorBias::Right, the returned Anchor will always resolve to the end of the buffer.

let mut replica = Replica::new(1, 5);

// This anchor is to the start of the document, so it will always
// resolve to zero.
let start_of_document = replica.create_anchor(0, AnchorBias::Left);

let _ = replica.inserted(0, 5);
let _ = replica.inserted(0, 5);

assert_eq!(replica.resolve_anchor(start_of_document).unwrap(), 0);

// This anchor is to the end of the document, so it will always
// resolve to the current length of the buffer.
let end_of_document = replica.create_anchor(15, AnchorBias::Right);

let _ = replica.inserted(15, 5);
let _ = replica.inserted(20, 5);

assert_eq!(replica.resolve_anchor(end_of_document).unwrap(), 25);

pub fn decode( id: ReplicaId, encoded: &EncodedReplica ) -> Result<Self, DecodeError>

Available on crate feature encode only.

Creates a new Replica with the given ReplicaId by decoding the contents of the EncodedReplica.

Panics

Panics if the ReplicaId is zero.

Examples

let replica1 = Replica::new(1, 42);

let encoded: EncodedReplica = replica1.encode();

let replica2 = Replica::decode(2, &encoded).unwrap();

assert_eq!(replica2.id(), 2);

pub fn deleted<R>(&mut self, range: R) -> Deletion

where R: RangeBounds<Length>,

Informs the Replica that you have deleted the characters in the given offset range.

This produces a Deletion which can be sent to all the other peers to integrate the deletion into their own Replicas.

Panics

Panics if the start of the range is greater than the end or if the end is out of bounds (i.e. greater than the current length of your buffer).

Examples

// The buffer at peer 1 is "Hello World".
let mut replica1 = Replica::new(1, 11);

// Peer 1 deletes "Hello ".
let deletion: Deletion = replica1.deleted(..6);

pub fn encode(&self) -> EncodedReplica

Available on crate feature encode only.

Encodes the Replica in a custom binary format.

This can be used to send a Replica to another peer over the network. Once they have received the EncodedReplica they can decode it via the decode method.

Note that if you want to collaborate within a single process you can just fork the Replica without having to encode it and decode it again.

pub fn fork(&self, new_id: ReplicaId) -> Self

Creates a new Replica with the given ReplicaId but with the same internal state as this one.

Note that this method should be used when the collaborative session is limited to a single process (e.g. multiple threads working on the same document). If you want to collaborate across different processes or machines you should encode the Replica and send the result to the other peers.

Panics

Panics if the ReplicaId is zero.

Examples

let replica1 = Replica::new(1, 0);
let replica2 = replica1.fork(2);
assert_eq!(replica2.id(), 2)

pub fn id(&self) -> ReplicaId

Returns the id of this Replica.

pub fn inserted(&mut self, at_offset: Length, len: Length) -> Insertion

Informs the Replica that you have inserted len characters at the given offset.

This produces an Insertion which can be sent to all the other peers to integrate the insertion into their own Replicas.

Panics

Panics if the offset is out of bounds (i.e. greater than the current length of your buffer).

Examples

// The buffer at peer 1 is "ab".
let mut replica1 = Replica::new(1, 2);

// Peer 1 inserts two characters between the 'a' and the 'b'.
let insertion: Insertion = replica1.inserted(1, 2);

pub fn integrate_deletion(&mut self, deletion: &Deletion) -> Vec<Range<Length>>

Integrates a remote Deletion into this Replica, returning a sequence of offset Ranges to be deleted from your buffer.

The number of ranges can be:

• zero, if the Deletion has already been integrated by this Replica or if it depends on some context that this Replica doesn’t yet have (see the backlogged_deletions method which handles this case);

• one, if there haven’t been any concurrent insertions (local or remote) within the original range of the deletion;

• more than one, if there have been. In this case the deleted range has been split into multiple smaller ranges that “skip over” the newly inserted text.

The ranges are guaranteed to be sorted in ascending order and to not overlap, i.e. for any two indices i and j where i < j and j < ranges.len() it holds that ranges[i].end < ranges[j].start (and of course that ranges[i].start < ranges[i].end).

Examples

// Peer 1 starts with the text "abcd" and sends it to a second peer.
let mut replica1 = Replica::new(1, 4);

let mut replica2 = replica1.fork(2);

// Peer 1 deletes the "bc" in "abcd".
let deletion = replica1.deleted(1..3);

// Concurrently, peer 2 inserts a single character at start of the
// document.
let _ = replica2.inserted(0, 1);

// Now peer 2 receives the deletion from peer 1. Since the previous
// insertion was outside of the deleted region the latter is still
// contiguous at this peer.
let ranges = replica2.integrate_deletion(&deletion);

assert_eq!(ranges.as_slice(), &[2..4]);

// Same as before..
let mut replica1 = Replica::new(1, 4);
let mut replica2 = replica1.fork(2);

let deletion = replica1.deleted(1..3);

// ..except now peer 2 inserts a single character between the 'b' and
// the 'c'.
let _ = replica2.inserted(2, 1);

// Now peer 2 receives the deletion from peer 1. Since the previous
// insertion was inside the deleted range, the latter has now been
// split into two separate ranges.
let ranges = replica2.integrate_deletion(&deletion);

assert_eq!(ranges.as_slice(), &[1..2, 3..4]);

pub fn integrate_insertion(&mut self, insertion: &Insertion) -> Option<Length>

Integrates a remote Insertion into this Replica, optionally returning the offset at which to insert the Insertion’s Text into your buffer.

A None value can be returned if the Insertion has already been integrated by this Replica or if it depends on some context that this Replica doesn’t yet have (see the backlogged_insertions method which handles this case).

Examples

// Peer 1 starts with the text "ab" and sends it to a second peer.
let mut replica1 = Replica::new(1, 2);

let mut replica2 = replica1.fork(2);

// Peer 1 inserts two characters between the 'a' and the 'b'.
let insertion_1 = replica1.inserted(1, 2);

// Concurrently, peer 2 inserts a character at the start of the
// document.
let insertion_2 = replica2.inserted(0, 1);

// Peer 1 receives this insertion, and since there haven't been any
// concurrent insertions at the start of the document, its offset
// hasn't changed.
let offset_2 = replica1.integrate_insertion(&insertion_2).unwrap();

assert_eq!(offset_2, 0);

// If we try to integrate the same insertion again, we'll get a `None`.
assert!(replica1.integrate_insertion(&insertion_2).is_none());

// Finally, peer 2 receives the first insertion from peer 1. Its text
// should be inserted between the 'a' and the 'b', which is at offset
// 2 at this peer.
let offset_1 = replica2.integrate_insertion(&insertion_1).unwrap();

assert_eq!(offset_1, 2);

pub fn new(id: ReplicaId, len: Length) -> Self

Creates a new Replica with the given ReplicaId from the initial Length of your buffer.

Note that if you have multiple peers working on the same document you should only use this constructor on the first peer, usually the one that starts the collaboration session.

The other peers should get their Replica from another Replica already in the session by either:

a) forking it if the collaboration happens all in the same process (e.g. a text editor with plugins running on separate threads),

b) encodeing it and sending the result over the network if the collaboration is between different processes or machines.

Panics

Panics if the ReplicaId is zero.

Examples

// A text editor initializes a new Replica on the main thread where the
// buffer is "foo".
let replica_main = Replica::new(1, 3);

// It then starts a plugin on a separate thread and wants to give it a
// Replica to keep its buffer synchronized with the one on the main
// thread. It does *not* call `new()` again, but instead forks the
// existing Replica and sends it to the new thread.
let replica_plugin = replica_main.fork(2);

thread::spawn(move || {
    // The plugin can now use its Replica to exchange edits with the
    // main thread.
    println!("{replica_plugin:?}");
});

pub fn resolve_anchor(&self, anchor: Anchor) -> Option<Length>

Resolves the given Anchor to an offset in the document.

This method returns None if the Replica hasn’t yet integrated the insertion containing the Anchor. In all other cases it returns Some(offset), even if the position the Anchor refers to has been deleted.

For more information, see the documentation of Replica::create_anchor() and Anchor.

Examples

let mut peer_1 = Replica::new(1, 10);
let mut peer_2 = peer_1.fork(2);

let insertion_at_2 = peer_2.inserted(10, 10);

let anchor = peer_2.create_anchor(15, AnchorBias::Left);

// The anchor refers to the insertion made at peer 2, which peer 1
// doesn't yet have.
assert_eq!(peer_1.resolve_anchor(anchor), None);

peer_1.integrate_insertion(&insertion_at_2);

// Now that peer 1 has integrated peer 2's insertion, the anchor can be
// resolved.
assert_eq!(peer_1.resolve_anchor(anchor), Some(15));

Trait Implementations

impl Debug for Replica

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.