eg-walker-reference
API
Generated with
eg-walker-reference/eg_walker_reference

eg_walker_reference

package eg_walker_reference

Members list

Packages

package eg_walker_reference.causalGraph

Type members

Classlikes

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

Attributes

Supertypes
class Object
trait Matchable
class Any
final case class Changes[T](cgDiff: PartialSerializedCG, missingOps: ArrayBuffer[ListOp[T]])

Attributes

Companion
object
Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object Changes

Attributes

Companion
class
Supertypes
trait Product
trait Mirror
class Object
trait Matchable
class Any
Self type
Changes.type
trait DebugConfiguration

Attributes

Supertypes
class Object
trait Matchable
class Any
object DebugLevel

Attributes

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

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait ListOp[T]
class Object
trait Matchable
class Any
Show all
class DocCursor(var idx: Number, var endPos: Number)

Attributes

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: ArrayBuffer[LV])

Attributes

Supertypes
class Object
trait Matchable
class Any
final case class InsertOp[T](pos: Number, content: T) extends ListOp[T]

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
trait ListOp[T]
class Object
trait Matchable
class Any
Show all
class Item(val opId: OpId, var curState: ItemState, var endState: ItemState, val originLeft: OpId, val rightParent: OpId)

Attributes

Supertypes
class Object
trait Matchable
class Any
object ItemState

Attributes

Supertypes
class Object
trait Matchable
class Any
Self type
ItemState.type
object ListOp

Attributes

Companion
trait
Supertypes
trait Sum
trait Mirror
class Object
trait Matchable
class Any
Self type
ListOp.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

Companion
object
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

Supertypes
class Object
trait Matchable
class Any
sealed trait Logger2

Attributes

Companion
object
Supertypes
class Object
trait Matchable
class Any
object Logger2

Attributes

Companion
trait
Supertypes
class Object
trait Matchable
class Any
Self type
Logger2.type
final case class MissingChanges[T](entries: PartialSerializedCG, missingOps: ArrayBuffer[ListOp[T]])

Attributes

Supertypes
trait Serializable
trait Product
trait Equals
class Object
trait Matchable
class Any
Show all
object OpId

Attributes

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

Attributes

Supertypes
class Object
trait Matchable
class Any

Types

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

Value members

Concrete methods

def advance1[T](ctx: EditContext, oplog: ListOpLog[T], opId: OpId): Unit
def apply1[T](ctx: EditContext, snapshot: ArrayBuffer[T] | Null, oplog: ListOpLog[T], opId: OpId): Unit
def assert(expr: Boolean, msg: Option[String] = ...): Unit
def assertEq[T](a: T, b: T, msg: Option[String] = ...): Unit
def checkout[T](oplog: ListOpLog[T]): Branch[T]
def checkoutSimple[T](oplog: ListOpLog[T]): ArrayBuffer[T]
def checkoutSimpleString(oplog: ListOpLog[String]): String
def createEmptyBranch[T](): Branch[T]
def createOpLog[T](): ListOpLog[T]
def debugPrintCtx[T](ctx: EditContext, oplog: ListOpLog[T]): String
def findByCurPos(ctx: EditContext, targetPos: Number): DocCursor
def findItemIdx(ctx: EditContext, needle: OpId): Int
def getLatestVersion[T](oplog: ListOpLog[T]): ArrayBuffer[RawVersion]
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

def integrateChanges[T](me: ListOpLog[T], changes: Changes[T]): Unit
def itemWidth(state: ItemState): Number
def localDelete[T](oplog: ListOpLog[T], agent: String, pos: Number, len: Number = ...): Unit

local delete

local delete

Attributes

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

Attributes

def mergeChangesIntoBranch[T](branch: Branch[T], oplog: ListOpLog[T])(mergeVersion: ArrayBuffer[LV] = ...): Unit
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

def produceChanges[T](me: ListOpLog[T], versionSummary: VersionSummary): (Changes[T], VersionSummary | Null)
def produceMissing[T](me: ListOpLog[T], missingSummary: VersionSummary): Changes[T]
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

def retreat1[T](ctx: EditContext, oplog: ListOpLog[T], opId: OpId): Unit
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

Generated with