Babble is a free-flow collaborative text-editor designed to exercise the Joyce framework. To get an idea how Joyce would perform in the real word we needed an application complex enough to exercise the whole framework but familiar enough to a general audience that the contributions of the framework are well highlighted; particularly fluid collaboration, selective undo/redo and automatic storage.
When 'opening' a file in Babble, Joyce will discover the collaborative group for the document and synchronise the changes made while the local state was offline:
Edits from collaborators can be "tagged": on mouse-over we can display context information about the edit:
If concurrent edits conflict, Babble will apply one edit and highlight it with an alarming red shading. If one of the conflicting edits is local, Babble always displays the local edit. It is a key principle of Joyce that the user should feel in control of his local state; that local edits should not be sacrificed for remote ones unless specifically instructed.
Selective undo/redo is triggered through the history editor. Actions are arranged in to editor according to edit point and dependencies. In the figure below the action in the secod column has a dependency to the action in the first. Selecting the first-column action also highlights the second-column actions and the modifications that both the actions made are highlighted in the content display. In this way the user can visulise the extent of a prospective undo.
Since this representation can be confusing in a large document we can also filter the history editor to the 'local history' - the history at the current caret position:
Text editors are usually built around a linear character buffer that is addressed using character coordinates from 0 (before the first character) to N (after the last character given N-1 characters in the buffer). Two operations modify this buffer: insert(p, c), that inserts character c at position p, and delete(p, n) that removes a range of n characters starting at position p. Shared text editors are usually built around the same structure but use operational transform to transform remote inserts and deletes such that their local effect is the same as their effect at their source. Essentially, the transforms translate the edit points of inserts and the edit point and spans of deletes from the remote state into the local one by transforming the incoming operation against the operations that have applied to the local state. This gives good performance in distributed, real-time editing but is complex to implement, especially if multi-synchrony and undo-redo are required, intrinsic qualities of Joyce applications.
Babble borrows the idea of translating edit points from OT but uses a more systematic approach that meets the requirements of the Joyce framework. Our representation of a text buffer is more complex than a simple character array but allows us to capture the dependencies between edits and allows us to show, hide, recombine and re-order editing operations as directed by Joyce (for example during selective undo/redo or collaboration).
The representation is in three parts:
- The content: a linear text buffer similar to the structure used by non-concurrent and OT editors. However, with the exception of snapshotting and undo (see below) characters are only ever inserted into the buffer, not removed.
- The mask: a collection of character position intervals that indicate text that has been deleted. Masked text is not displayed and therefore cannot be edited (the cursor cannot be placed in the masked content).
- The history: a hierarchical collection of character position intervals that records the operations that have been applied to the content in terms of the range of characters affected.
The actions defined by Babble are:
- Insert(p, s): insert the string s in the content at position p.
- Delete(p, a): insert a mask of length a in the mask structure.
|-D2------------|
v |
|-I2--| |
v v
|-I1--------| |-D1--|
A B p s t u q r C D E F G
Babble's replay mechanism is derived from OT but retains a systematic operational history and is far simpler to implement that OT. We say that that every Insert operation creates a scope over the content inserted: a 1D co-ordinate space from 0 to the number of characters inserted. Subsequent insertions within this scope are always recorded in this co-ordinate space regardless of any mutations to the original insertion. For example, say we have the initial scope:
A B C D E F G H
|---------------|
0 +0 8
This is a scope of 8 characters across which there is a shift of 0. The shifts in a scope are used to record how the original scope has been mutated by subsequent insert operations. If we insert 'pqr' between B and C:
I(2, 'pqr')
|-----|
A B p q r C D E F G H
|--- -----------|
0 |-----| +3 11
+0
The original scope has been split and the shift after the split incremented by the number of characters inserted. If an insertion is made between E and F, Babble transforms the edit point of the insertion according to the start and shift of the intersected region:
I(2, 'pqr') I((8-0-3), 'stu') = I(5, 'stu')
|--------| |--------|
A B p q r C D E s t u F G H
|----- -------- -------|
0 |--------| +3 |--------| +6 14
+0 +0
The process is recursive; if an insert is made between q and r:
I( (4-2-0), 'wxy') = I(2, 'wxy')
|-------|
v
|------------------| |--------|
A B p q w x y r C D E s t u F G H
|----- -------- -------|
0 +0 |----- -----| +3 |--------| +6 14
+0 |-------| +3 +0
+0
J time M
||
A B C D E F G H || A B C D E F G H
|---------------| || |---------------|
+0 || +0
||
I(2, 'pqr') || I(3, 'stu')
||
A B p q r C D E F G H || A B C s t u D E F G H
|--- -----------| || |----- ---------|
+0 |-----| +3 || +0 |-----| +3
+0 || +0
\/
Now if M's change propagates to J Babble detects that the intersected scope is not the same as the remote scope (via the follows constraint) and shifts the insertion by the width of the intersected scopes until the correct scope is reached:
I(3, stu) (I(6, stu) after transform.)
|-----| |-----|
A B p q r C s t u D E F G H
|--- - ---------|
|-----| |-----|
=====>|
Edit point is shifted until it
reached the right scope.
If the spans of concurrent actions overlap those actions are deemed to be in conflict. Babble does not try to resolve conflicts - it does not know about the linguistic context the conflicting actions were made in. Babble will simply pick one action to apply to the state and highlight the content introduced or removed by that action with a red shading (above). If one of the conflicting actions is local Babble will always apply the local action. Following from the previous example:
J time M
D(8, 3) || I(10, 'wxy')
= D( (8-6-0), 3) || = I(10-6, 'wxy')
= D(2, 3) mustfollow I(3, stu) || = I(4, 'wxy')
||
||
D(2, 3) ||
|-------| ||
v || I(4, 'wxy')
|-----| |-----| || |-----|
A B p q r C s t u D E F G H || A B p q r C s t u D w x y D E F G H
|--- - ---------| ||
|-----| |-----| ||
<=========
propagate
I(4, 'wxy')
|-----|
X
D(2, 3) ||
|-------| ||
v ||
|-----| |-----| ||
A B p q r C s t u D E F G H ||
|--- - ---------| ||
|-----| |-----| \/
After transform the incoming action conflicts with a local action. It will not be applied but the content inserted ("stu") will be highlighted.
A B C D E F G H
|---------------|
+0
Inserting between B & C...
I(2, pqr)
|-----|
A B p q r C D E F G H
|--- -----------|
|-----| +3
+0
Inserting between D & E...
I(4, stu) (after transform)
|-----| |-----|
A B p q r C D s t u E F G H
|--- --- -------|
|-----| |-----| +6
+0 +0
Undo the last insertion. The compensation action removes the content and scope...
I(2, pqr)
|-----|
A B p q r C D E F G H
|--- -----------|
|-----| +3
+0
Insert between C & D:
I(5, wxy) (after transform)
|-----| |-----|
A B p q r C w x y D E F G H
|--- - ---------|
|-----| |-----| +6
+0 +0
Redo I(4, stu). The action is transformed against the current state & replayed in the appropriate place.
I(4, stu) (replayed against current state)
|-----| |-----| |-----|
A B p q r C w x y D s t u E F G H
|--- - - -------|
|-----| |-----| |-----| +9