Crate chronofold

Chronofold

Chronofold is a conflict-free replicated data structure (a.k.a. CRDT) for versioned text.

This crate aims to offer a fast implementation with an easy-to-use Vec-like API. It should be near impossible to shoot yourself in the foot and end up with corrupted or lost data.

Note: We are not there yet! While this implementation should be correct, it is not yet optimized for speed and memory usage. The API might see some changes as we continue to explore different use cases.

This implementation is based on ideas published in the paper “Chronofold: a data structure for versioned text” by Victor Grishchenko and Mikhail Patrakeev. If you look for a formal introduction to what a chronofold is, reading that excellent paper is highly recommended!

Example usage

use chronofold::{Chronofold, LogIndex, Op};

type AuthorId = &'static str;

// Alice creates a chronofold on her machine, makes some initial changes
// and sends a copy to Bob.
let mut cfold_a = Chronofold::<AuthorId, char>::default();
cfold_a.session("alice").extend("Hello chronfold!".chars());
let mut cfold_b = cfold_a.clone();

// Alice adds some more text, ...
let ops_a: Vec<Op<AuthorId, char>> = {
    let mut session = cfold_a.session("alice");
    session.splice(
        LogIndex(16)..LogIndex(16),
        " - a data structure for versioned text".chars(),
    );
    session.iter_ops().map(Op::cloned).collect()
};

// ... while Bob fixes a typo.
let ops_b: Vec<Op<AuthorId, char>> = {
    let mut session = cfold_b.session("bob");
    session.insert_after(LogIndex(11), 'o');
    session.iter_ops().map(Op::cloned).collect()
};

// Now their respective states have diverged.
assert_eq!(
    "Hello chronfold - a data structure for versioned text!",
    format!("{}", cfold_a),
);
assert_eq!("Hello chronofold!", format!("{}", cfold_b));

// As soon as both have seen all ops, their states have converged.
for op in ops_a {
    cfold_b.apply(op).unwrap();
}
for op in ops_b {
    cfold_a.apply(op).unwrap();
}
let final_text = "Hello chronofold - a data structure for versioned text!";
assert_eq!(final_text, format!("{}", cfold_a));
assert_eq!(final_text, format!("{}", cfold_b));

Structs

Chronofold

A conflict-free replicated data structure for versioned sequences.

Iter

An iterator over the elements of a chronofold.

LogIndex

An index in the log of the chronofold.

Op

An operation is the unit of change in the distributed context.

Ops

An iterator over ops representing a chronofold’s changes.

Session

An editing session tied to one author.

Timestamp

An ordered pair of the author’s index and the author.

Version

A vector clock representing the chronofold’s version.

Enums

Change

An entry in the chronofold’s log.

ChronofoldError

Represents errors that can occur when applying an op.

OpPayload

The payload of an operation.

Traits

Author

A trait alias to reduce redundancy in type declarations.

FromLocalValue

IntoLocalValue

Type Aliases

EarliestDeletion