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"}}

• Important Note: Since v0.9.10, adding and removing attributes using retain is no longer supported, as it overly complicates the implementation and led to inconsistence in design. You can use combination of delete and insert for same effect, if base content is available.

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 its 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

Also, since v0.9.10, Text-VersionControl no longer supports Quill's retain with attributes, which acts as modifying attributes with base content intact.

 ```js
[{retain: 1, attributes: {"b": "true"}}] // Quill's retain with attributes. Base content is unspecified
[{delete: 1}, {insert: "<base content>", attributes: {"b" : "true"}}] // Equivalent delta with Text-VersionControl. Base content should be specified
```

This decision was made because concurrent modification did not fit well with Text-VersionControl's CRDT model.

• Priority of application: If multiple users modify an attribute at the same time, which one should prevail? Modeling this increases the implementation complexity a lot while the benefit is small.
• Undoing a retain with attributes is not a reversible operation