stdx-crdt
API
Generated with
stdx-crdt/stdx.crdt

stdx.crdt

package stdx.crdt

Members list

Packages

package stdx.crdt.causalGraph
package stdx.crdt.list.fugue
package stdx.crdt.mutable

Type members

Experimental classlikes

class Branch[T](val snapshot: ArrayBuffer[T], var version: ArrayBuffer[LV])

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
trait DebugConfiguration

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
object DebugLevel

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
DebugLevel.type
final class DeleteOp[T](val pos: Number) extends ListOp[T]

Attributes

Experimental
true
Supertypes
trait ListOp[T]
class Object
trait Matchable
class Any
class DocCursor(var idx: Number, var endPos: Number)

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
class EditContext(val items: ArrayBuffer[Item], val delTargets: Map[OpId, OpId], val itemsByLv: Map[OpId, Item | Null], var curVersion: IndexedSeq[LV])

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
object HLC

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
HLC.type
final class InsertOp[T](val pos: Number, val content: T) extends ListOp[T]

Attributes

Experimental
true
Supertypes
trait ListOp[T]
class Object
trait Matchable
class Any
class Item(val opId: OpId, var curState: ItemState, var endState: ItemState, val originLeft: OpId, val rightParent: OpId)

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
object ItemState

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
ItemState.type
sealed trait ListOp[T]

Operations either insert new content at some position (index), or delete the item at some position.

Operations either insert new content at some position (index), or delete the item at some position.

Note the positions are normal array / string indexes, indexing into what the document looked like when the operation was created (at its parent version).

Operations also have an ID (agent,seq pair) and a list of parent versions. In this implementation, the ID and parents are stored separately - in the causal graph.

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
Known subtypes
class DeleteOp[T]
class InsertOp[T]
class ListOpLog[T](val ops: OpsList[T], val cg: CausalGraph)

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
sealed trait Logger2

Attributes

Companion
object
Experimental
true
Supertypes
class Object
trait Matchable
class Any
object Logger2

Attributes

Companion
trait
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
Logger2.type
object OpId

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
OpId.type
class OpsList[T]()

Attributes

Experimental
true
Supertypes
class Object
trait Matchable
class Any
object TimeMethod

Attributes

Companion
trait
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Self type
TimeMethod.type
trait TimeMethod

Attributes

Companion
object
Experimental
true
Supertypes
class Object
trait Matchable
class Any
Known subtypes
final case class VectorClock()

Attributes

Experimental
true
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all

Types

type DebugLevel = High | Medium | Low
opaque type HLC
opaque type ItemState
type Number = Long
opaque type OpId

Value members

Experimental methods

def advance1[T](ctx: EditContext, oplog: ListOpLog[T], opId: OpId): Unit

Attributes

Experimental
true
def apply1[T](ctx: EditContext, snapshot: ArrayBuffer[T] | Null, oplog: ListOpLog[T], opId: OpId): Unit

Attributes

Experimental
true
def assert(expr: Boolean, msg: Option[String] = ...): Unit

Attributes

Experimental
true
def assertEq[T](a: T, b: T, msg: Option[String] = ...): Unit

Attributes

Experimental
true
def checkout[T](oplog: ListOpLog[T]): Branch[T]

Attributes

Experimental
true
def checkoutSimple[T](oplog: ListOpLog[T]): ArrayBuffer[T]

Attributes

Experimental
true
def checkoutSimpleString(oplog: ListOpLog[String]): String

Attributes

Experimental
true
def createEmptyBranch[T](): Branch[T]

Attributes

Experimental
true
def createOpLog[T](): ListOpLog[T]

Attributes

Experimental
true
def debugPrintCtx[T](ctx: EditContext, oplog: ListOpLog[T]): String

Attributes

Experimental
true
def findByCurPos(ctx: EditContext, targetPos: Number): DocCursor

Attributes

Experimental
true
def findItemIdx(ctx: EditContext, needle: OpId): Int

Attributes

Experimental
true
def getLatestVersion[T](oplog: ListOpLog[T]): IndexedSeq[RawVersion]

Attributes

Experimental
true
def integrate(ctx: EditContext, cg: CausalGraph, newItem: Item, cursor: DocCursor): Unit

This function is called when we process insert operations to find (via a scan) the correct location in the item list to insert the new item. The location is passed back to the caller via the (modified) cursor.

This function is called when we process insert operations to find (via a scan) the correct location in the item list to insert the new item. The location is passed back to the caller via the (modified) cursor.

Some history:

This algorithm started its life in Yjs, written by Kevin Jahns. I adapted that approach for reference-crdts. Then modified & improved it in place to make YjsMod.

Then an almost identical algorithm was invented by Matthew Weidner and Kleppmann and called Fugue. The fugue paper proves many nice properties about this algorithm - in particular, it proves that it has excellent interleaving behaviour:

https://arxiv.org/abs/2305.00583

Meanwhile, Greg Little and Micheal Toomim wrote a seperate sequence CRDT algorithm called Sync9. Sync9 predated fugue by a couple of years. It was formulated a different way (using trees), but it turns out the ordering behaviour between sync9 and fugue is identical.

It also turns out that Fugue has one little problem in its interleaving behaviour, which was fixed by Weidner and named FugueMax. My YjsMod algorithm is (I think) identical to FugueMax, and that's what I've implemented here.

Anyway, the long and short of it is: This function implements the YjsMod / FugueMax CRDT - which is coincidentally very similar to Toomim & Little's Sync9.

Attributes

Experimental
true
def itemWidth(state: ItemState): Number

Attributes

Experimental
true
def localDelete[T](oplog: ListOpLog[T], agent: String, pos: Number, len: Number = ...): Unit

Attributes

Experimental
true
def localInsert[T](oplog: ListOpLog[T], agent: String, _pos: Number, content: T*): Unit

Attributes

Experimental
true
def mergeChangesIntoBranch[T](branch: Branch[T], oplog: ListOpLog[T])(mergeVersion: IndexedSeq[LV] = ...): Unit

Attributes

Experimental
true
def mergeOplogInto[T](dest: ListOpLog[T], src: ListOpLog[T]): Unit

This function adds everything in the src oplog to dest

This function adds everything in the src oplog to dest

Attributes

Experimental
true
def pushOp[T](oplog: ListOpLog[T], id: RawVersion, parents: ArrayBuffer[RawVersion], `type`: "ins" | "del", pos: Number, content: T | Null): Boolean

Add an operation to the oplog. Content is required if the operation is an insert.

Add an operation to the oplog. Content is required if the operation is an insert.

Attributes

Experimental
true
def retreat1[T](ctx: EditContext, oplog: ListOpLog[T], opId: OpId): Unit

Attributes

Experimental
true
def traverseAndApply[T](ctx: EditContext, oplog: ListOpLog[T], snapshot: ArrayBuffer[T] | Null, fromOp: OpId = ...)(toOp: LV = ...): Unit

Traverse and apply the operations in the oplog.

Traverse and apply the operations in the oplog.

This function runs the core merging logic, traversing the graph of changes and modifying 2 structures along the way:

  • The ctx.items will have fugue style items inserted, and their state changed.
  • The passed in data array (document snapshot) will be modified.

Value parameters

ctx

The (in memory) editing context with fugue items at some state

fromOp

The index of the first operation to traverse over

oplog

The log of operations we're applying

snapshot

The document snapshot to modify. When the function returns, this contains the final document state.

toOp

The bound on the indexes to traverse over

Attributes

Experimental
true
Generated with