Text-VersionControl

Introduction

Text-VersionControl provides version and concurrency control for text editing based on OT(Operational Transformation) and CRDT(Conflict-free Replicated Data Type) ideas. It's for use in real-time, distributed collaborative document editing and history management for text contents.

Getting Started

Install the library by npm install text-versioncontrol --save

Table of Contents

• Operations and Delta
  • Operations
  • Constructing Delta
  • Working with Delta
  • Utility Functions
• SharedString
• History
• Miscellaneous

Operations and Delta

Text-VersionControl utilizes Quill's Delta representation in JSON. It supports Operational Transformation's basic representations(retain, delete, and insert). The delta format also provides attributes and embedded objects for expressing complex content besides simple text.

Operations

• Content can be expressed using insert operations

  {insert: "Hello"}, {insert: "World", attributes: {"color": "red"}}, {insert: {"video": "http://youtube.com/sOdLN"}}

• Operations

  {retain: 5}
  {delete: 2}
  {insert: "Hello World!"}

• Embedded objects can hold a map of string->string.

  {insert: {"img": "file:///img.gif"}}

• Content with attributes

  {insert: "Hello", attributes: {"link": "http://github.com"}}

• Adding attributes

  {retain: 5, attributes: {"link": "http://github.com"}}

• Removing attributes

  {retain: 5, attributes: {"link": null}}

Constructing Delta

new Delta(ops?:Op[])

• Initialize with JSON

  new Delta([{retain: 5}, {delete: 2}, {insert: "Hello World!"}])

• Construct by chaining

  new Delta().retain(5).delete(2).insert("Hello World!")

  • Available method variants

  delta.insert("hello") // simple text content
  delta.insert("world", {"color": "red"}) // text with attributes
  delta.insert({"img": "./ball.gif"})	// embedded content
  delta.insert({"video": "./ball.gif"}, {"w": "300", "h": "600"})	// embedded content with attributes
  delta.retain(5)
  delta.retain(3, {"bold": "true"}) // adding or modifying an attribute
  delta.retain(3, {"bold": null}) // removing an attribute
  delta.delete(2)

Working with Delta

• Examples

  let delta = new Delta().insert("hello").insert(" world").retain(2).retain(3)
  // normalize
  delta = delta.normalize() // == new Delta().insert("hello world").retain(5)
  // slice
  delta.take(1,2) // == new Delta().insert("e")
  // apply or compose
  delta.apply(new Delta().retain(1).delete(4).insert("i")) // == new Delta().insert("hi world")

• normalize

  normalize():Delta

  • Returns: a more compact and equivalent delta by removing redundant or effect-less operations
  • Equivalent to normalizeDeltas(delta)

• take

  take(start:number, end:number):Delta

  • Returns: new delta slicing the original delta by the given range
  • Equivalent to cropContent(delta, start, end)

• apply or compose

  apply(other:Delta):Delta
  compose(other:Delta):Delta

  • Returns: Combination of two deltas into a single flattened delta.
  • Applying a change on a content
  • Combining two changes into one
  • Equivalent to flattenDeltas(delta, other)

• transform

  transform(other:Delta, priority = false):Delta

  • Returns transformed other as if this delta has preceded it
  • priority is used for insert tie-breaking
  • Equivalent to transformDeltas(delta, other, priority)

• invert

  invert(baseContent:Delta):Delta

  • Returns: the inversion of a change when applied on baseContent.

  • In other words, it returns D' where baseContent.apply(D).apply(D') == baseContent holds for content baseContent and change D.

  • Useful for generating an undo change.

  • baseContent is required for correctly inverting addition/removal of attributes

  • equivalent to invertChange(baseConent, delta)

Utility Functions

Text-VersionControl provides utility functions to manipulate deltas

• flattenDeltas(...deltas:Delta[]):Delta
  • Flattens a sequence of multiple deltas into a single equivalent delta
• filterChanges(baseContent:Delta, changes:Delta[], criteria:(idx:number, change:Delta):Delta[]
  • Filters changes that are fulfilling criteria given a base content and sequence of changes. Useful to rule out certain changes while keeping (the effect of) rest of changes intact

SharedString

SharedString forms the core of Text-VersionControl's OT and CRDT functionality. SharedString is a mutable object that can be edited by receiving changes as delta. It can consolidate concurrent, distributed edits by multiple users.

Initialization

ss = SharedString.fromDelta({ops:[{insert:"Hello World"}]})
ss = SharedString.fromString("Hello World")

Applying changes

applyChange(change:Delta, branch:string):Delta

• Edits the content by applying change. This mutates SharedString.

• Returns transformed change as if the change was made in linear fashion

• Multiple users with their own sequence of changes independently can be applied by alternating branch.

  ss.applyChange(changeByAlice, "Alice")
  ss.applyChange(changeByBob, "Bob") // Bob is unaware of Alice's change
  ss.applyChange(changeByAlice2, "Alice") // second edit by Alice, while unaware of Bob's change
  ss.applyChange(changeByCharlie, "Charlie") // Charlie is unaware of Alice's or Bob's changes

  • As long as you keep the order of changes within each branch, the result content will be the same no matter how you order the changes of different branches. This satisfies CRDT characteristics.
  • branch also takes a role as a tiebreaker for concurrent inserts.

• Wildcard branch lets you simulate a checkpoint, where the change is applied as if it's aware of all other changes from different branches

  • The star wildcard branch sees the previous changes of all branches and can be seen by all branches later on

    ss.applyChange(changeByStar, "*")
    ss.applyChange(changeByCharlie, "Charlie") // Charlie is aware of change by '*'

  • The underscore wildcard branch sees the previous changes of all branches but cannot be seen by other branches later on

    ss.applyChange(changeByUnderScore, "_")
    ss.applyChange(changeByCharlie, "Charlie") // Charlie is unaware of change by '_'

Rendering current content

ss.toDelta() // the content seen as if changes in all branches were consolidated
ss.toDelta(branch) // the content visible on specific branch

Other methods

• Clone current state

  ss.clone()

History

History utilizes SharedString to provide higher level functionalities such as snapshot access, append, merge, or rebase. It keeps the content and changes as Delta.

Initialization

new History(name:string, initialContent: Delta | string)

• name here exists for tie-breaking concurrent inserts during merge or rebase.

Applying changes

• By appending at current revision:

  history.append(deltas)

• By merging forked sequence of changes diverged from a base revision:

  history.merge({rev: baseRev, changes: deltasByAlice, branch: "Alice"})

  

  • Returns: MergeResult

    { rev: number, // latest revision after applying merge
     content: Delta, // result content
     reqChanges: Delta[], // request changes (passed changes transformed)
     resChanges: Delta[] } // response changes (base changes)

  • branchName works as the insert tiebreaker by comparing with History's name value

• By rebasing forked sequence of changes diverged from a base revision.

  history.rebase({rev: baseRev, changes: deltasByAlice, branch: "Alice"})

  

  • Returns: MergeResult

    { rev: number, // latest revision after applying rebase
     content: Delta, // result content
     reqChanges: Delta[], // request changes (passed changes)
     resChanges: Delta[] } // response changes (base changes transformed)

  • Unlike merging, rebasing forces new set of changes to be first applied on the base revision, followed by existing changes (transformed) in the history since the base revision. Beware rebasing replaces changes already recorded in the history.

Revisions, snapshots, and changes

• Getting the current revision

  history.getCurrentRev()

• Getting the content

  history.getContent() // content at current revision
  history.getContentAt(rev) // snapshot content at rev

• Getting the changes

  history.getChangeAt(rev) // change made on content at rev
  history.getChangesFrom(rev)
  history.getChangesFromTo(revFrom, revTo)

Miscellaneous

Notes on similarity and difference to Quill's Delta

Text-VersionControl borrows Quill Delta's representation and many of method names but does not behave the same in a few cases. For example, many of the methods of Quill's Delta reorder adjacent delete and insert (which in most cases does not change the effect), but Text-VersionControl's equivalent methods preserve it. See the following examples:

• Result of new Delta().retain(2).delete(2).insert('Hello')

  [{retain: 2}, {insert: 'Hello'}, {delete: 2}] // Quill
  [{retain: 2}, {delete: 2}, {insert: 'Hello'}] // Text-VersionControl

• Result of new Delta([{insert: 'ab'}, {delete: 1}, {insert: 'cd'}]).compose([{retain: 4}]

  [{insert: 'abcd'}, {delete: 1}] // Quill
  [{insert: 'ab'}, {delete: 1}, {insert: 'cd'}] // Text-VersionControl