Awesome
This repository is deprecated
... in favor of different packages for each future CRDT algorithm.
Right now, this means that most of this code has been moved into the ListDocumentModel package and the differential ternary search tree has beeb moved into the DTST package.
Logootish
The Logootish CRDT algorithm used by the Matrix Notepad. See the documentation
on the Notepad wiki
for information about the algorithm and the TypeDoc
Currently, this is only used in matrix-notepad, but the code is generic
enough that it could be used in any collaboration system. At the moment, this
only contains an implementation of an algorithm that I call AnchorLogoot.
Based on https://github.com/krasimir/webpack-library-starter
Design Philosophy
This algorithm, in contrast to others such as
Automerge or
Y.js is both data and network agnostic. This
means that the ListDocumentModel contained here can be used for any ordered
list that allows duplication, such as a string, array, or a rich text data
type. This does mean that it's up to you to perform operations on whatever
your data model is, but it's quite easy. However, if you want to save the state
(in IndexedDB or wherever), you will have to implement this yourself. If you
are interested in using this in your own project, please submit an issue to
request that I clear up the documentation. I'm focusing on making the Nodepad
work, so docs here are not at the top of my priority list.
The logootish-js codebase was forked out of
Matrix Notepad and, shortly thereafter,
converted to TypeScript. This is by far the most complex and important part of
the Notepad.
Currently, logootish-js only supports the ListDocumentModel type. Other
CRDT building blocks will be added in the future.
ListDocumentModel
Note that the Wiki contains information for the over-Matrix protocol used to transfer Logootish operations. That is not part of this library.
The ListDocumentModel contains a mapping of Logootish (custom algorithm)
positions to text positions in the local document. It is capable of
bi-directional mappings. The Logoot equivalent of a local insertion is
determined through the insertLocal method and the Logoot equivalent of a
local removal is determined through the removeLocal function. The local
operations that must be performed for a given Logoot operation are determined
by the insertLogoot and removeLogoot methods, respectively.
Conflict resolution is mostly implemented, but mark operations need to be fixed
(issues #11 and #12) before that's ready for normal usage. A new algorithm has
been created known as "Anchor Logoot." This is not compatible with previous
versions below 0.4.0. Currently, conflict creation is experimental and is
only implemented in the model. Mark operations are not created yet.
Performance
Most of my time has been spent making this work in the first place. Because of that, it's a bit slow, but there are a few areas where it can be easily sped up (see the issues). I also have my CI generating flamegraph(s), such as the one here.
Installation
# Grab the repo
git clone https://github.com/KB1RD/logootish-js.git
# Install packages
yarn install
# Build everything
yarn run build
yarn run build:docs
# Run tests (currently broken)
yarn run test
yarn run test:watch
yarn run test:cover
Usage
Unfortunately, the last update broke most of the examples I had here. I will eventually put new usage examples here and describe the architecture.