Eips is the *efficient intention-preserving sequence*: a
sequence <abbr title="conflict-free replicated data type">CRDT</abbr>
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][Eips] doesn’t store items
directly, but rather translates between [*local changes*][`LocalChange`] that
use integer indices, and [*remote changes*][`RemoteChange`] that use stable
IDs, enabling the items themselves to be stored in any list-like structure,
like a simple [growable array][Vec] or [counted B-tree][btree-vec]. 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][design] for a detailed explanation of the design and
implementation of Eips, including benchmarks measuring its performance and
memory use.
[design]: https://github.com/taylordotfish/eips/blob/master/doc/design.md
Crate features
--------------
When the crate feature `serde` is enabled, [`RemoteChange`] \(and types it
contains) will implement [Serde][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.
[btree-vec]: https://docs.rs/btree-vec
[`insert`]: Eips::insert
[`remove`]: Eips::remove
[`mv`]: Eips::mv
[`apply_change`]: Eips::apply_change