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

Operations and Delta
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

kindone / text-versioncontrol Goto Github PK