Eips
====
Eips is the *efficient intention-preserving sequence*: a
[sequence CRDT](https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#Sequence_CRDTs)
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.
Documentation
-------------
[Documentation is available on docs.rs.](https://docs.rs/eips)
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]: doc/design.md
Demo
----
The [test-cli](test-cli) directory contains an interactive program that
demonstrates the functionality of Eips.
License
-------
Eips is licensed under version 3 of the GNU Affero General Public License, or
(at your option) any later version. See [LICENSE](LICENSE).
Contributing
------------
By contributing to Eips, you agree that your contribution may be used according
to the terms of Eips’s license.
[btree-vec]: https://github.com/taylordotfish/btree-vec
[`insert`]: https://docs.rs/eips/0.2/eips/struct.Eips.html#method.insert
[`remove`]: https://docs.rs/eips/0.2/eips/struct.Eips.html#method.remove
[`mv`]: https://docs.rs/eips/0.2/eips/struct.Eips.html#method.mv
[`apply_change`]: https://docs.rs/eips/0.2/eips/struct.Eips.html#method.apply_change
[Eips]: https://docs.rs/eips/0.2/eips/struct.Eips.html
[`LocalChange`]: https://docs.rs/eips/0.2/eips/change/enum.LocalChange.html
[`RemoteChange`]: https://docs.rs/eips/0.2/eips/change/struct.RemoteChange.html
[Vec]: https://doc.rust-lang.org/stable/std/vec/struct.Vec.html