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(15)..LogIndex(15),
        " - a data structure for versioned text".chars(),
    );
    session.iter_ops().collect()
};

// ... while Bob fixes a typo.
let ops_b: Vec<Op<AuthorId, char>> = {
    let mut session = cfold_b.session("bob");
    session.insert_after(Some(LogIndex(10)), 'o');
    session.iter_ops().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.
LogIndex	An index in the log of the chronofold.
Op	An operation is the unit of change in the distributed context.
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

Traits

Author

A trait alias to reduce redundancy in type declarations.