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).
In addition, the [Eips Lesser Network Exception][elne] and [Eips Peer-to-Peer
Exception][eppe] apply to Eips. These exceptions are additional permissions
under section 7 of the GNU AGPL, version 3; as such, if you modify Eips, you
may choose whether to extend them to your modified version. For more
information about these exceptions, see [this repository][ex-repo].
[elne]: licenses/Eips-Lesser-Network-Exception
[eppe]: licenses/Eips-Peer-to-Peer-Exception
[ex-repo]: https://codeberg.org/taylordotfish/eips-exceptions
Please note that you do not have to license your project under the AGPL if you
use Eips. Your project can be licensed under any AGPLv3-compatible license,
including nearly all permissive licenses such as MIT or Apache 2.0. The terms
of the AGPL will apply only to the combination of your project with Eips (e.g.,
source code must be provided along with any compiled binaries); any portion of
your project that does not depend on Eips may be used without adherence to the
AGPL.
Contributing
------------
By contributing to Eips, you agree that your contribution may be used according
to the terms of Eips’s license, including the Eips Lesser Network Exception and
Eips Peer-to-Peer Exception.
[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