Skip to content

Old repository for the Matrix Notepad algorithm. Use @anchor-logoot/listdocumentmodel instead.

License

Notifications You must be signed in to change notification settings

anchor-logoot/logootish-js

Repository files navigation

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

GitHub release (latest SemVer) Matrix GitHub Workflow Status (branch) GitHub

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

Notepad Wiki TypeDoc

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.