Crate eips 

Eips is the efficient intention-preserving sequence: a sequence CRDT with worst-case non-amortized logarithmic-time operations, minimal memory usage, and no issues with interleaving concurrent insertions or duplicating moved elements as seen in some other CRDTs.

Features

• No interleaving of characters when multiple users insert text at the same position, even when text is typed in reverse (by typing a letter, moving the cursor back one, typing the next letter, etc.)
• Support for move operations. Items can be moved within the sequence and will not be duplicated if multiple users try to move the same item concurrently.
• Insertions, deletions, moves, and accesses are worst-case non-amortized O(log h), where h is the total number of items ever inserted in the document.
• Constant item size. Memory use per item is fixed, even as editing history grows; the same applies to the number of bytes needed to communicate changes to other clients.
• Resistance to malicious actors. Eips has no pathological cases that could suddenly decrease performance—time complexity is strictly logarithmic, and space complexity strictly linear—and malicious input can’t cause Eips to crash.
• Data-agnostic design: the CRDT structure doesn’t store items directly, but rather translates between local changes that use integer indices, and remote changes that use stable IDs, enabling the items themselves to be stored in any list-like structure, like a simple growable array or counted B-tree. This also speeds up local operations like searching, as tombstones don’t cause a performance penalty.
• Simple API. An edit begins by calling insert, remove, or mv, which instead of mutating the document directly, returns a remote change object describing the operation. Once the object is passed to apply_change, and sent to any network-connected peers, the edit is complete.

Requirements

• As with many sequence CRDTs, Eips assumes changes are delivered in causal order.
• Clients must be capable of generating unique IDs. If each client already has a unique client ID, a common approach is to use (client-id, counter) pairs, where counter is a simple per-client increasing integer. UUIDs may be used in cases where this isn’t possible.

Design

See this document for a detailed explanation of the design and implementation of Eips, including benchmarks measuring its performance and memory use.

Crate features

When the crate feature serde is enabled, RemoteChange (and types it contains) will implement Serde’s Serialize and Deserialize traits.

This crate can be used in no_std contexts by disabling the std feature with default-features = false. In this case, at least one of allocator-fallback or allocator_api (unstable) must be enabled.

Re-exports

pub use change::LocalChange;

pub use change::RemoteChange;

pub use options::EipsOptions;

pub use options::Options;

Modules

change

Types representing remote and local changes.

error

Error types.

iter

Iterators.

options

Options for Eips.

Structs

Eips

An intention-preserving sequence CRDT.

Traits

Id

The trait that ID types must implement.