Cscott has uploaded a new change for review.
https://gerrit.wikimedia.org/r/84442
Change subject: WIP: Implement `ve.dm.Transaction.transpose()` w/ intentions.
......................................................................
WIP: Implement `ve.dm.Transaction.transpose()` w/ intentions.
Transposing two transactions allows you to reorder them. It is the basis
of a Operational Transform implementation for Visual Editor. There is
an extensive test suite ensuring that the result of transposing two
transactions yields consistent results.
This commit adds a functional transpose operation for transactions which
operates on the high level "intention" associated with the transaction,
leaving it to the `ve.dm.Transaction.new*` methods to create operation
sequences which respect document structure.
Change-Id: I9eaefeed15bf22d2bca13ae1a52a7631425c1875
---
M VisualEditor.hooks.php
M VisualEditor.php
M demos/ve/index.php
A modules/ve/dm/ve.dm.Transaction.transpose.js
A modules/ve/test/dm/ve.dm.Transaction.transpose.test.js
M modules/ve/test/index.php
6 files changed, 1,196 insertions(+), 0 deletions(-)
git pull ssh://gerrit.wikimedia.org:29418/mediawiki/extensions/VisualEditor
refs/changes/42/84442/1
diff --git a/VisualEditor.hooks.php b/VisualEditor.hooks.php
index 23dddbc..029f87a 100644
--- a/VisualEditor.hooks.php
+++ b/VisualEditor.hooks.php
@@ -341,6 +341,7 @@
've/test/dm/ve.dm.InternalList.test.js',
've-mw/test/dm/ve.dm.InternalList.test.js',
've/test/dm/ve.dm.Transaction.test.js',
+
've/test/dm/ve.dm.Transaction.transpose.test.js',
've/test/dm/ve.dm.TransactionProcessor.test.js',
've/test/dm/ve.dm.Surface.test.js',
've/test/dm/ve.dm.SurfaceFragment.test.js',
diff --git a/VisualEditor.php b/VisualEditor.php
index b9e950b..cfb1c7e 100644
--- a/VisualEditor.php
+++ b/VisualEditor.php
@@ -288,6 +288,7 @@
've/dm/ve.dm.MetaList.js',
've/dm/ve.dm.TransactionProcessor.js',
've/dm/ve.dm.Transaction.js',
+ 've/dm/ve.dm.Transaction.transpose.js',
've/dm/ve.dm.Surface.js',
've/dm/ve.dm.SurfaceFragment.js',
've/dm/ve.dm.DataString.js',
diff --git a/demos/ve/index.php b/demos/ve/index.php
index 70bb9ba..5206d1c 100644
--- a/demos/ve/index.php
+++ b/demos/ve/index.php
@@ -142,6 +142,7 @@
<script src="../../modules/ve/dm/ve.dm.MetaList.js"></script>
<script
src="../../modules/ve/dm/ve.dm.TransactionProcessor.js"></script>
<script src="../../modules/ve/dm/ve.dm.Transaction.js"></script>
+ <script
src="../../modules/ve/dm/ve.dm.Transaction.transpose.js"></script>
<script src="../../modules/ve/dm/ve.dm.Surface.js"></script>
<script
src="../../modules/ve/dm/ve.dm.SurfaceFragment.js"></script>
<script src="../../modules/ve/dm/ve.dm.DataString.js"></script>
diff --git a/modules/ve/dm/ve.dm.Transaction.transpose.js
b/modules/ve/dm/ve.dm.Transaction.transpose.js
new file mode 100644
index 0000000..25b4659
--- /dev/null
+++ b/modules/ve/dm/ve.dm.Transaction.transpose.js
@@ -0,0 +1,323 @@
+/*!
+ * VisualEditor DataModel Transaction transposition.
+ *
+ * @copyright 2011-2013 VisualEditor Team and others; see AUTHORS.txt
+ * @license The MIT License (MIT); see LICENSE.txt
+ */
+( function ( ve ) {
+
+ /* Private helper functions */
+
+ /*
+ * Position data type.
+ *
+ * Maintain position within data/metadata. Conceptually, metadata
+ * positions precede data positions, so that the data at offset
+ * `n` occurs at position `(n, MAX_INT)`.
+ */
+ function Position(dataPos, metadataPos) {
+ this.data = dataPos || 0;
+ this.meta = metadataPos || 0;
+ }
+ Position.prototype.add = function( d, m ) {
+ if ( d instanceof Position ) {
+ return this.add( d.data, d.meta );
+ }
+ if ( d === 0 ) {
+ return new Position( this.data, this.meta + ( m || 0 )
);
+ }
+ return new Position( this.data + d, ( m || 0 ) );
+ };
+ Position.prototype.subtract = function( d, m ) {
+ if ( d instanceof Position ) {
+ return this.subtract( d.data, d.meta );
+ }
+ return this.add( -d, -m );
+ };
+ Position.prototype.eq = function( d, m ) {
+ if ( d instanceof Position ) {
+ return this.eq( d.data, d.meta );
+ }
+ return this.data === d && this.meta === m;
+ };
+ Position.prototype.lt = function( d, m ) {
+ if ( d instanceof Position ) {
+ return this.lt( d.data, d.meta );
+ }
+ if ( this.data === d ) {
+ return this.meta < ( m || 0 );
+ }
+ return this.data < d;
+ };
+ Position.prototype.toString = function() {
+ return 'Position('+this.data+','+this.meta+')';
+ };
+
+ /*
+ * Helper function for `transposeOne()`.
+ *
+ * We preprocess transactions' operation lists to annotate them with
+ * old position information and mutable insert/remove lists. We
+ * call the result a 'map'.
+ */
+ function mkMap( tx ) {
+ var r = [], oldPos = new Position( 0, 0 ), j, meta, inMeta =
false;
+ // start with sentinel
+ r.push( {
+ op: { type: 'retain', length: 1 },
+ correction: new Position( -1 ),
+ start: new Position( -1 )
+ } );
+ $.each( tx.operations, function( i, op ) {
+ var m = {
+ op: op,
+ start: oldPos
+ };
+ switch ( op.type ) {
+
+ case 'retain':
+ m.correction = new Position( 0 );
+ if ( inMeta ) {
+ inMeta = false;
+ // add sentinel covering "data after
metadata" realignment
+ m.start = oldPos.add( 1 );
+ m.correction = new Position( -1 );
+ r.push( {
+ op: { type: 'retainData' },
+ start: oldPos,
+ correction: new Position( 0 )
+ } );
+ if ( op.length === 1 ) {
+ oldPos = m.start;
+ return;
+ }
+ }
+ oldPos = oldPos.add( op.length );
+ break;
+
+ case 'replace':
+ if ( inMeta ) {
+ throw new Error( 'replace at unaligned
position' );
+ }
+ // combine data and metadata
+ m.remove = [];
+ meta = ( op.removeMetadata === undefined ) ? []
: op.removeMetadata;
+ for ( j = 0; j < op.remove.length; j++ ) {
+ m.remove.push( [ meta[ j ], op.remove[
j ] ] );
+ }
+ m.insert = [];
+ meta = ( op.insertMetadata === undefined ) ? []
: op.insertMetadata;
+ for ( j = 0; j < op.insert.length; j++ ) {
+ m.insert.push( [ meta[ j ], op.insert[
j ] ] );
+ }
+ oldPos = oldPos.add( op.remove.length );
+ break;
+
+ case 'replaceMetadata':
+ if ( !inMeta ) {
+ inMeta = true;
+ // add sentinel
+ r.push( {
+ op: { type: 'retainMetadata',
length: 1 },
+ correction: new Position( 0, -1
),
+ start: oldPos.subtract( 0, 1 )
+ } );
+ }
+ m.remove = op.remove.slice( 0 );
+ m.insert = op.insert.slice( 0 );
+ oldPos = oldPos.add( 0, op.remove.length );
+ break;
+
+ case 'retainMetadata':
+ if ( !inMeta ) {
+ inMeta = true;
+ // add sentinel
+ r.push( {
+ op: { type: 'retainMetadata',
length: 1 },
+ correction: new Position( 0, -1
),
+ start: oldPos.subtract( 0, 1 )
+ } );
+ }
+ m.correction = new Position( 0 );
+ oldPos = oldPos.add( 0, op.length );
+ break;
+
+ default:
+ throw new Error( 'unhandled type: ' + op.type );
+ }
+ r.push( m );
+ } );
+ // add sentinel at end
+ r.push( {
+ op: { type: 'retain', length: 1 },
+ correction: new Position( -1 ),
+ start: oldPos,
+ end: oldPos.add( 1 )
+ } );
+ // link up 'start' and 'end' fields
+ $.each( r, function( i, op ) {
+ if ( i < r.length - 1 ) {
+ op.end = r[ i + 1 ].start;
+ }
+ } );
+ return r;
+ }
+
+ /*
+ * @param {boolean} preferB If true, give position new before given
old `offset`; otherwise give new position after old `offset-1`.
+ */
+ // apply b operations to a to determine how offsets change
+ function translate( pos, bMap ) {
+ var inMeta = false;
+ var i, op, extraData, extraMeta;
+ var oldStart = new Position( 0 ), oldEnd;
+ var newStart = new Position( 0 ), newEnd;
+ var extraData, extraMeta;
+
+ // run through elements completely before pos.
+ extraData = extraMeta = 0;
+ for ( i = 0; i < bMap.length; i++ ) {
+ if ( !bMap[i].end.lt( pos ) ) {
+ break;
+ }
+ op = bMap[i].op;
+ switch ( op.type ) {
+ case 'retainData':
+ extraMeta = 0;
+ break;
+ case 'replace':
+ extraData += op.insert.length -
op.remove.length;
+ break;
+ case 'replaceMetadata':
+ extraMeta += op.insert.length -
op.remove.length;
+ break;
+ default:
+ break;
+ }
+ }
+ // ok, now we're looking at an element which contains pos.
+ // treat replace carefully here.
+ if ( i < bMap.length ) {
+ op = bMap[i].op;
+ // XXX?
+ if ( op.type === 'replace' ) {
+ extraData += op.insert.length -
op.remove.length;
+ } else if ( op.type === 'replaceMetadata' ) {
+ extraMeta += op.insert.length -
op.remove.length;
+ }
+ }
+ return pos.add( extraData, extraMeta );
+ }
+
+ function tweak( xxx ) {
+ // XXX write me
+ // what sorts of fixups need to be made?
+ }
+
+ /*
+ * Helper function for `transpose()`.
+ *
+ * Transposing `a` by `b` is almost the same as transposing `b` by `a`;
we just
+ * break some ties in opposite ways to ensure the results are
consistent.
+ * So we define `transposeOne` here, and then call it twice to create
the
+ * full `transpose` result.
+ *
+ * @param {boolean} preferB If true, perform insertions before a given
`offset` (translated appropriately); otherwise perform insertions after
`offset-1` (translated appropriately).
+ * @returns {ve.dm.Transaction} The new version of `a`
+ */
+ function transposeOne( doc, a, b, preferB ) {
+ var bMap, oldStart, oldEnd, newStart, newEnd, newDoc,
newIntention;
+ var isMeta = false;
+
+ // start by doing common translations.
+ oldStart = oldEnd = new Position( 0 );
+ if ( a.intention[1] instanceof ve.Range ) {
+ oldStart = new Position( a.intention[1].start );
+ oldEnd = new Position( a.intention[1].end );
+ if ( a.intention[2] instanceof ve.Range ) {
+ // refine by metadata pos. (a.intention[1] is
collapsed)
+ oldStart = oldStart.add( 0,
a.intention[2].start );
+ oldEnd = oldEnd.add( 0, a.intention[2].end );
+ isMeta = true;
+ }
+ }
+ if ( oldStart.eq( oldEnd ) && !preferB ) {
+ oldStart = oldEnd =
+ isMeta ? oldStart.add( 0, -1 ) : oldStart.add(
-1 );
+ }
+ // translate
+ bMap = mkMap( b );
+ newStart = translate( oldStart, bMap );
+ newEnd = translate( oldEnd, bMap );
+ if ( oldStart.eq( oldEnd ) && !preferB ) {
+ newStart = newEnd =
+ isMeta ? oldStart.add( 0, 1 ) : oldStart.add( 1
);
+ }
+ // make new arguments.
+ newIntention = a.intention.slice( 0 );
+ if ( a.intention[1] instanceof ve.Range ) {
+ newIntention[1] = a.intention[1].isBackwards() ?
+ new ve.Range( newEnd.data, newStart.data ) :
+ new ve.Range( newStart.data, newEnd.data );
+ if ( a.intention[2] instanceof ve.Range ) {
+ newIntention[2] = a.intention[2].isBackwards() ?
+ new ve.Range( newEnd.meta,
newStart.meta ) :
+ new ve.Range( newStart.meta,
newEnd.meta );
+ }
+ }
+ // create "after b" document.
+ // FIXME: this is expensive. Can we make a lighter-weight
clone?
+ // XXX: do we need to fix up internalList, like ve.dm.example
does?
+ newDoc = new ve.dm.Document( doc.getData( undefined, true ) );
+ // oddball adjustments go here.
+ tweak( newIntention );
+ // create transaction result from new intention
+ return ve.dm.Transaction.newFromIntention( newDoc, newIntention
);
+ }
+
+ /* Public methods */
+
+ /**
+ * @class ve.dm.Transaction
+ */
+
+ /**
+ * Transform this transaction as though the `other` transaction had come
+ * before it.
+ * Returns a pair, `[new_version_of_this, transformed_other]`, such the
the
+ * document resulting from:
+ * ```
+ * doc.commit( other );
+ * doc.commit( new_version_of_this );
+ * ```
+ * is identical to the document which would result from:
+ * ```
+ * doc.commit( this );
+ * doc.commit( transformed_other );
+ * ```
+ * Does not modify this transaction.
+ *
+ * @method
+ * @param {ve.dm.Document} doc The document that both `this` and
`other` were created against.
+ * @param {ve.dm.Transaction} other The transaction to transpose
against.
+ * @returns {ve.dm.Transaction[]} The pair of transposed transactions.
+ */
+ ve.dm.Transaction.prototype.transpose = function ( doc, other ) {
+ // Special case when this is identical to other.
+ if ( ve.compare( this.intention, other.intention ) ) {
+ return [ ve.dm.Transaction.newNoOp( doc ),
+ ve.dm.Transaction.newNoOp( doc ) ];
+ }
+ // Special case when one or the other is a no-op.
+ if ( this.isNoOp() || other.isNoOp() ) {
+ return [ this.copy( doc ), other.copy( doc ) ];
+ }
+ // Create final result by calling `transposeOne` twice.
+ return [
+ transposeOne( doc, this, other, false ),
+ transposeOne( doc, other, this, true )
+ ];
+ };
+
+
+} )( ve );
diff --git a/modules/ve/test/dm/ve.dm.Transaction.transpose.test.js
b/modules/ve/test/dm/ve.dm.Transaction.transpose.test.js
new file mode 100644
index 0000000..a06c00a
--- /dev/null
+++ b/modules/ve/test/dm/ve.dm.Transaction.transpose.test.js
@@ -0,0 +1,868 @@
+/*!
+ * VisualEditor DataModel Transaction transposition tests.
+ *
+ * @copyright 2011-2013 VisualEditor Team and others; see AUTHORS.txt
+ * @license The MIT License (MIT); see LICENSE.txt
+ */
+
+QUnit.module( 've.dm.Transaction.transpose' );
+
+/* Helper methods */
+
+/* Tests */
+
+QUnit.test( 'transpose (simple string changes)', function ( assert ) {
+ // Simple transaction transpose tests
+ var initialContent = [ { type: 'paragraph' } ];
+ var finalContent = [ { type: '/paragraph' } ];
+ function metaMap ( data, withClose ) {
+ var meta = [];
+ $.each( data, function( _, e ) {
+ var el = $( '<meta property=test /> ').attr( 'content',
e );
+ elements.push( {
+ 'type': 'alienMeta',
+ 'attributes': {
+ 'domElements': el.toArray()
+ }
+ } );
+ if ( withClose ) {
+ elements.push( {
+ 'type': '/alienMeta'
+ } );
+ }
+ } );
+ return meta;
+ }
+ function makeDoc( oldValue, useMeta ) {
+ var elements = initialContent;
+ oldValue = oldValue.split( '' );
+ if ( useMeta ) {
+ elements = elements.concat( metaMap( oldValue, true ) );
+ } else {
+ elements = elements.concat( oldValue );
+ }
+ elements.push.apply( elements, finalContent );
+ return ve.dm.example.createExampleDocumentFromObject( 'data',
null, {
+ 'data': elements
+ } );
+ }
+ function fromChange( doc, oldValue, newValue, useMeta ) {
+ var commonStart, commonEnd, removed, inserted, tx;
+ if ( typeof oldValue !== 'string' || typeof newValue !==
'string' ) {
+ throw new Error( 'fromChange not being called
correctly' );
+ }
+ commonStart = 0;
+ while ( commonStart < newValue.length &&
+ newValue.charAt( commonStart ) === oldValue.charAt(
commonStart ) ) {
+ commonStart++;
+ }
+ commonEnd = 0;
+ while ( commonEnd < ( newValue.length - commonStart ) &&
+ commonEnd < ( oldValue.length - commonStart ) &&
+ newValue.charAt( newValue.length - commonEnd - 1 ) ===
+ oldValue.charAt( oldValue.length - commonEnd - 1 )) {
+ commonEnd++;
+ }
+ removed = oldValue.substr( commonStart, oldValue.length -
commonStart - commonEnd );
+ inserted = newValue.substr( commonStart, newValue.length -
commonStart - commonEnd );
+ // make a transaction object
+ if ( useMeta ) {
+ if ( removed.length === 0 ) {
+ return
ve.dm.Transaction.newFromMetadataInsertion(
+ doc, initialContent.length, commonStart,
+ metaMap( inserted )
+ );
+ } else if ( inserted.length === 0 ) {
+ return ve.dm.Transaction.newFromMetadataRemoval(
+ doc, initialContent.length,
+ new ve.Range( commonStart, commonStart
+ removed.length )
+ );
+ } else if ( removed.length === 1 && inserted.length ===
1 ) {
+ return
ve.dm.Transaction.newFromMetadataElementReplacement(
+ doc, initialContent.length, commonStart,
+ metaMap( inserted )[0]
+ );
+ } else {
+ // Intention model doesn't support simultaenous
insert/remove
+ return ve.dm.Transaction.newNoOp( doc );
+ }
+ } else {
+ if ( removed.length === 0 ) {
+ return ve.dm.Transaction.newFromInsertion(
+ doc, initialContent.length +
commonStart, inserted
+ );
+ } else if ( inserted.length === 0 ) {
+ return ve.dm.Transaction.newFromRemoval(
+ doc,
+ new ve.Range(
+ initialContent.length +
commonStart,
+ initialContent.length +
commonStart + removed.length
+ )
+ );
+ } else {
+ // Intention model doesn't support simultaenous
insert/remove
+ return ve.dm.Transaction.newNoOp( doc );
+ }
+ }
+ return tx;
+ }
+ function apply( text, transaction, useMeta ) {
+ var result = '', p = 0, retain = 'retain', replace = 'replace';
+ if ( transaction.isNoOp() ) {
+ return text;
+ }
+ if ( useMeta ) {
+ retain += 'Metadata';
+ replace += 'Metadata';
+ } else {
+ for ( result = ''; result.length <
initialContent.length; )
+ result += '@';
+ text = result + text;
+ for ( result = ''; result.length < finalContent.length;
)
+ result += '@';
+ text += result;
+ result = '';
+ }
+ $.each( transaction.operations, function(_, t) {
+ if ( t.type === retain ) {
+ result += text.substr( p, t.length );
+ p += t.length;
+ } else if ( t.type === replace ) {
+ result += t.insert.join( '' );
+ p += t.remove.length;
+ } else {
+ throw new Error( 'Unexpected transaction
operation: ' + t.type );
+ }
+ } );
+ if ( !useMeta ) {
+ result = result.substring(
+ initialContent.length, result.length -
finalContent.length
+ );
+ }
+ return result;
+ }
+ function stripMeta( operations ) {
+ var r = new ve.dm.Transaction( [ 'bogus' ] );
+ $.each( operations, function( _, op ) {
+ switch ( op.type ) {
+ case 'retainMetadata':
+ r.pushRetain( op.length );
+ break;
+ case 'replaceMetadata':
+ r.pushReplaceInternal( op.remove, op.insert );
+ break;
+ default:
+ break;
+ }
+ } );
+ return r.operations;
+ }
+ function runTest1( _, test ) {
+ var doc, txa, txb, result, to1, to2, aops, bops,
+ desc = test.desc, useMeta = test.useMeta;
+ doc = makeDoc( test.from, useMeta );
+ txa = fromChange( doc, test.from, test.a, useMeta );
+ txb = fromChange( doc, test.from, test.b, useMeta );
+ if ( txa.isNoOp() || txb.isNoOp() ) {
+ // skip this test, not applicable
+ assert.ok( true ); assert.ok( true );
+ assert.ok( true ); assert.ok( true );
+ return;
+ }
+ result = txa.transpose( doc, txb );
+ to1 = apply( apply( test.from, txa, useMeta ), result[1],
useMeta );
+ to2 = apply( apply( test.from, txb, useMeta ), result[0],
useMeta );
+ assert.strictEqual( to1, test.to, desc + ': result after A,
B\'' );
+ assert.strictEqual( to2, test.to, desc + ': result after B,
A\'' );
+ aOps = result[0].getOperations();
+ bOps = result[1].getOperations();
+ if ( useMeta ) {
+ aOps = stripMeta( aOps );
+ bOps = stripMeta( bOps );
+ }
+ assert.deepEqual( aOps, test.aprime, desc + ': operations in
A\'' );
+ assert.deepEqual( bOps, test.bprime, desc + ': operations in
B\'' );
+ }
+ var cases = [
+ {
+ desc: 'Two insertions',
+ from: 'abcdef',
+ a: 'Xabcdef', // [insert "X" @0]
+ b: 'aYbcdef', // [insert "Y" @1]
+ aprime: [ // -> becomes [insert "X" @0]
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 7 }
+ ],
+ bprime: [ // -> becomes [insert "Y" @2]
+ { type: 'retain', length: 2 },
+ { type: 'replace', insert: [ 'Y' ], remove: []
},
+ { type: 'retain', length: 5 }
+ ],
+ to: 'XaYbcdef',
+ symmetric: true
+ },
+ {
+ desc: 'Insert at same spot (1)',
+ from: 'abc',
+ a: 'abcX', // [insert "X" @3]
+ b: 'abcY', // [insert "Y" @3]
+ aprime: [ // -> becomes [insert "X" @4]
+ { type: 'retain', length: 4 },
+ { type: 'replace', insert: [ 'X' ], remove: [] }
+ ],
+ bprime: [ // -> becomes [insert "Y" @3]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'Y' ], remove: []
},
+ { type: 'retain', length: 1 }
+ ],
+ to: 'abcYX' // precedence matters
+ },
+ {
+ desc: 'Insert at same spot (2)',
+ from: 'abcdef',
+ a: 'Xabcdef', // [insert "X" @0]
+ b: 'Yabcdef', // [insert "Y" @0]
+ aprime: [ // -> becomes [insert "X" @1]
+ { type: 'retain', length: 1 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 6 }
+ ],
+ bprime: [ // -> becomes [insert "Y" @0]
+ { type: 'replace', insert: [ 'Y' ], remove: []
},
+ { type: 'retain', length: 7 }
+ ],
+ to: 'YXabcdef' // precedence matters
+ },
+ {
+ desc: 'Two deletions (1)',
+ from: 'abcdef',
+ a: 'bcdef', // [delete 1 chars @0]
+ b: 'acdef', // [delete 1 chars @1]
+ aprime: [ // -> becomes [delete 1 chars @0]
+ { type: 'replace', insert: [], remove: [ 'a' ]
},
+ { type: 'retain', length: 4 }
+ ],
+ bprime: [ // -> becomes [delete 1 chars @0]
+ { type: 'replace', insert: [], remove: [ 'b' ]
},
+ { type: 'retain', length: 4 }
+ ],
+ to: 'cdef',
+ symmetric: true
+ },
+ {
+ desc: 'Two deletions (2)',
+ from: 'abcdef',
+ a: 'cdef', // [delete 2 chars @0]
+ b: 'acdef', // [delete 1 chars @1]
+ aprime: [ // -> becomes [delete 1 chars @0]
+ { type: 'replace', insert: [], remove: [ 'a' ]
},
+ { type: 'retain', length: 4 }
+ ],
+ bprime: [ // -> becomes [no-op]
+ { type: 'retain', length: 4 }
+ ],
+ to: 'cdef',
+ symmetric: true
+ },
+ {
+ desc: 'Two deletions (3)',
+ from: 'abcdef',
+ a: 'bcdef', // [delete 1 chars @0]
+ b: 'acdef', // [delete 1 chars @1]
+ aprime: [ // -> becomes [delete 1 chars @0]
+ { type: 'replace', insert: [], remove: [ 'a' ]
},
+ { type: 'retain', length: 4 }
+ ],
+ bprime: [ // -> becomes [delete 1 chars @0]
+ { type: 'replace', insert: [], remove: [ 'b' ]
},
+ { type: 'retain', length: 4 }
+ ],
+ to: 'cdef',
+ symmetric: true
+ },
+ {
+ desc: 'Two deletions (4)',
+ from: 'abcdef',
+ a: 'ef', // [delete 4 chars @0]
+ b: 'acdef', // [delete 1 chars @1]
+ aprime: [ // -> becomes [delete 3 chars @0]
+ { type: 'replace', insert: [], remove: [ 'a',
'c', 'd' ] },
+ { type: 'retain', length: 2 }
+ ],
+ bprime: [ // -> becomes [no-op]
+ { type: 'retain', length: 2 }
+ ],
+ to: 'ef',
+ symmetric: true
+ },
+ {
+ desc: 'Two deletions (5)',
+ from: 'abcdef',
+ a: 'def', // [delete 3 chars @0]
+ b: 'ab', // [delete 4 chars @2]
+ aprime: [ // -> becomes [delete 2 chars @0]
+ { type: 'replace', insert: [], remove: [ 'a',
'b' ] }
+ ],
+ bprime: [ // -> becomes [delete 3 chars @0]
+ { type: 'replace', insert: [], remove: [ 'd',
'e', 'f' ] }
+ ],
+ to: '',
+ symmetric: true
+ },
+ {
+ desc: 'Insertion and replacement (1)',
+ from: 'abcdef',
+ a: 'Xabcdef', // [insert "X" @0]
+ b: 'abYef', // [replace 2 chars with "Y" @2]
+ aprime: [ // -> becomes [insert "X" @0]
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 5 }
+ ],
+ bprime: [ // -> becomes [replace 2 chars with "Y" @3]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'Y' ], remove: [
'c', 'd' ] },
+ { type: 'retain', length: 2 }
+ ],
+ to: 'XabYef',
+ symmetric: true
+ },
+ {
+ desc: 'Insertion and replacement (2)',
+ from: 'abcdef',
+ a: 'abYef', // [replace 2 chars with "Y" @2]
+ b: 'abXcdef', // [insert "X" @2]
+ aprime: [ // -> becomes [replace 2 chars with "Y" @3]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'Y' ], remove: [
'c', 'd' ] },
+ { type: 'retain', length: 2 }
+ ],
+ bprime: [ // -> becomes [insert "X" @2]
+ { type: 'retain', length: 2 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 3 }
+ ],
+ to: 'abXYef',
+ symmetric: true
+ },
+ {
+ desc: 'Insertion and replacement (3)',
+ from: 'abcdef',
+ a: 'aXbcdef', // [insert "X" @1]
+ b: 'Ydef', // [replace 3 chars with "Y" @0]
+ aprime: [ // -> becomes [insert "X" @0]
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 4 }
+ ],
+ bprime: [ // -> becomes [replace 4 chars with "XY" @0]
+ { type: 'replace', insert: [ 'X', 'Y' ],
remove: [ 'a', 'X', 'b', 'c' ] },
+ { type: 'retain', length: 3 }
+ ],
+ to: 'XYdef'
+ },
+ {
+ desc: 'Insertion and replacement (3) [flipped]',
+ from: 'abcdef',
+ a: 'Ydef', // [replace 3 chars with "Y" @0]
+ b: 'aXbcdef', // [insert "X" @1]
+ aprime: [ // -> becomes [replace 4 chars with "YX" @0]
+ { type: 'replace', insert: [ 'Y', 'X' ],
remove: [ 'a', 'X', 'b', 'c' ] },
+ { type: 'retain', length: 3 }
+ ],
+ bprime: [ // -> becomes [insert "X" @1]
+ { type: 'retain', length: 1 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 3 }
+ ],
+ to: 'YXdef'
+ },
+ {
+ desc: 'Insertion and replacement (4)',
+ from: 'abcdef',
+ a: 'Ydef', // [replace 3 chars with "Y" @0]
+ b: 'aXbcdef', // [insert "X" @1]
+ aprime: [ // -> becomes [replace 4 chars with "YX" @0]
+ { type: 'replace', insert: [ 'Y','X' ], remove:
[ 'a', 'X', 'b', 'c' ] },
+ { type: 'retain', length: 3 }
+ ],
+ bprime: [ // -> becomes [insert "X" @1]
+ { type: 'retain', length: 1 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 3 }
+ ],
+ to: 'YXdef'
+ },
+ {
+ desc: 'Insertion and replacement (4) [flipped]',
+ from: 'abcdef',
+ a: 'aXbcdef', // [insert "X" @1]
+ b: 'Ydef', // [replace 3 chars with "Y" @0]
+ aprime: [ // -> becomes [insert "X" @0]
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 4 }
+ ],
+ bprime: [ // -> becomes [replace 4 chars with "XY" @0]
+ { type: 'replace', insert: [ 'X','Y' ], remove:
[ 'a', 'X', 'b', 'c' ] },
+ { type: 'retain', length: 3 }
+ ],
+ to: 'XYdef'
+ },
+ {
+ desc: 'Insertion and replacement (5)',
+ from: 'abcdef',
+ a: 'abcdXef', // [insert "X" @ 4]
+ b: 'abYef', // [replace 2 chars with "Y" @2]
+ aprime: [ // -> becomes [insert "X" @3]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 2 }
+ ],
+ bprime: [ // -> becomes [replace 2 chars with "Y" @2]
+ { type: 'retain', length: 2 },
+ { type: 'replace', insert: [ 'Y' ], remove: [
'c', 'd' ] },
+ { type: 'retain', length: 3 }
+ ],
+ to: 'abYXef'
+ },
+ {
+ desc: 'Insertion and replacement (5) [flipped]',
+ from: 'abcdef',
+ a: 'abYef', // [replace 2 chars with "Y" @2]
+ b: 'abcdXef', // [insert "X" @ 4]
+ aprime: [ // -> becomes [replace 3 chars with "XY" @2]
+ { type: 'retain', length: 2 },
+ { type: 'replace', insert: [ 'Y' ], remove: [
'c', 'd' ] },
+ { type: 'retain', length: 3 }
+ ],
+ bprime: [ // -> becomes [insert "X" @2]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 2 }
+ ],
+ to: 'abYXef'
+ },
+ {
+ desc: 'Insertion and replacement (6)',
+ from: 'abcdef',
+ a: 'Xabcdef', // [insert "X" @0]
+ b: 'abYef', // [replace 2 chars with "Y" @2]
+ aprime: [ // -> becomes [insert "X" @0]
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 5 }
+ ],
+ bprime: [ // -> becomes [replace 2 chars with "Y" @3]
+ { type: 'retain', length: 3 },
+ { type: 'replace', insert: [ 'Y' ], remove: [
'c', 'd' ] },
+ { type: 'retain', length: 2 }
+ ],
+ to: 'XabYef',
+ symmetric: true
+ },
+ {
+ desc: 'Simultaneous identical changes',
+ from: 'abcdef',
+ a: 'aXcYef', // [replace 3 char with "XcY" @1]
+ b: 'aXcYef', // [replace 3 char with "XcY" @1]
+ aprime: [ // -> becomes no-op
+ ],
+ bprime: [ // -> becomes no-op
+ ],
+ to: 'aXcYef'
+ },
+ {
+ desc: 'Remove while insert',
+ from: 'abcd',
+ a: 'abXcd',
+ b: 'ad',
+ aprime: [
+ { type: 'retain', length: 1 },
+ { type: 'replace', insert: [ 'X' ], remove: []
},
+ { type: 'retain', length: 1 }
+ ],
+ bprime: [
+ { type: 'retain', length: 1 },
+ { type: 'replace', insert: [ 'X' ], remove: [
'b', 'X', 'c' ] },
+ { type: 'retain', length: 1 }
+ ],
+ to: 'aXd',
+ symmetric: true
+ }
+ ];
+ $.each( cases, function( _, test ) {
+ if ( test.symmetric ) {
+ cases.push( {
+ desc: test.desc + ' [flipped]',
+ from: test.from,
+ a: test.b,
+ b: test.a,
+ aprime: test.bprime,
+ bprime: test.aprime,
+ to: test.to
+ } );
+ }
+ });
+ $.each( cases, function( _, test ) {
+ var newTest = ve.copy ( test );
+ newTest.desc += ' [meta]';
+ newTest.useMeta = true;
+ cases.push( newTest );
+ } );
+
+ QUnit.expect( cases.length * 4 );
+ $.each( cases, runTest1 );
+});
+
+QUnit.test( 'transpose (with ve.dm.Document)', function ( assert ) {
+ // Transaction transpose tests with a full ve.dm.Document.
+ var cases,
+ metadataElement = {
+ 'type': 'alienMeta',
+ 'attributes': {
+ 'style': 'comment',
+ 'text': ' inline '
+ }
+ };
+ function runTest2( _, test ) {
+ var doc1, doc2, txa, txb, result, expected;
+ doc1 = ve.dm.example.createExampleDocument( test.doc );
+ doc2 = ve.dm.example.createExampleDocument( test.doc );
+ txa = ve.dm.Transaction[ test.a[0] ].apply(null, [ doc1
].concat( test.a.slice(1) ) );
+ txb = ve.dm.Transaction[ test.b[0] ].apply(null, [ doc2
].concat( test.b.slice(1) ) );
+ if ( test.disabled ) {
+ // make the number of assertions work out correctly
before we bail.
+ assert.ok(true); assert.ok(true); assert.ok(true);
assert.ok(true);
+ return;
+ }
+ result = txa.transpose( doc1, txb );
+ assert.deepEqualWithDomElements( result[0].getOperations(),
test.aprime,
+ test.desc + ': operations in A\'' );
+ assert.deepEqualWithDomElements( result[1].getOperations(),
test.bprime,
+ test.desc + ': operations in B\'' );
+ // apply a, then b' to doc1
+ doc1.commit( txa ); doc1.commit( result[1] );
+ // apply b, then a' to doc2
+ doc2.commit( txb ); doc2.commit( result[0] );
+ // both documents should be identical.
+ assert.equalNodeTree( doc1.getDocumentNode(),
doc2.getDocumentNode(),
+ test.desc + ': results after A,B\' and B,A\' match' );
+ // verify resulting document.
+ expected = ve.dm.example.createExampleDocument( test.doc
).getFullData();
+ test.expected( expected ); // adjust expectations
+ assert.deepEqualWithDomElements( doc1.getFullData(), expected,
test.desc + ': result as expected' );
+ }
+ cases = [
+ {
+ desc: 'Simple insertion',
+ doc: 'data',
+ a: [ 'newFromInsertion', 0, [
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' }
+ ] ],
+ b: [ 'newFromInsertion', 0, [
+ { 'type': 'paragraph' }, 'Y', { 'type':
'/paragraph' }
+ ] ],
+ aprime: [
+ { type: 'retain', length: 3 },
+ { type: 'replace', remove: [], insert: [
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' }
+ ] },
+ { type: 'retain', length: 63 }
+ ],
+ bprime: [
+ { type: 'replace', remove: [], insert: [
+ { 'type': 'paragraph' }, 'Y', { 'type':
'/paragraph' }
+ ] },
+ { type: 'retain', length: 66 }
+ ],
+ expected: function( data ) {
+ ve.batchSplice(data, 0, 0, [
+ { 'type': 'paragraph' }, 'Y', { 'type':
'/paragraph' },
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' }
+ ]);
+ }
+ },
+ {
+ desc: 'Insert and wrap',
+ doc: 'data',
+ a: [ 'newFromWrap', new ve.Range( 1, 4 ),
+ [ { 'type': 'heading', 'attributes': {
'level': 1 } } ],
+ [ { 'type': 'paragraph' } ], [], []
+ ],
+ b: [ 'newFromInsertion', 0, [
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' }
+ ] ],
+ aprime: [
+ { type: 'retain', length: 3 },
+ { type: 'replace', remove: [
+ { 'type': 'heading', 'attributes': {
'level': 1 } }
+ ], insert: [
+ { 'type': 'paragraph' }
+ ] },
+ { type: 'retain', length: 3 },
+ { type: 'replace', remove: [
+ { 'type': '/heading' }
+ ], insert: [
+ { 'type': '/paragraph' }
+ ] },
+ { type: 'retain', length: 58 }
+ ],
+ bprime: [
+ { type: 'replace', remove: [], insert: [
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' }
+ ] },
+ { type: 'retain', length: 63 }
+ ],
+ expected: function( data ) {
+ ve.batchSplice( data, 0, 1, [
+ { 'type': 'paragraph' }, 'X', { 'type':
'/paragraph' },
+ { 'type': 'paragraph' }
+ ]);
+ ve.batchSplice( data, 7, 1, [
+ { 'type': '/paragraph' }
+ ]);
+ },
+ symmetric: true
+ },
+ {
+ desc: 'Insertion with metadata present',
+ disabled: disableMetadataTests,
+ doc: 'withMeta',
+ a: [ 'newFromRemoval', new ve.Range( 1, 4 ) ],
+ b: [ 'newFromRemoval', new ve.Range( 7, 10 ) ],
+ aprime: [
+ { type: 'retain', length: 1 },
+ { type: 'replace', remove: [ 'F', 'o', 'o' ],
insert: [] },
+ { type: 'retain', length: 6 }
+ ],
+ bprime: [
+ { type: 'retain', length: 4 },
+ {
+ type: 'replace',
+ insert: [],
+ insertMetadata: [],
+ remove: [ 'B', 'a', 'z' ],
+ removeMetadata: [
+ [ {
+ type: 'alienMeta',
+ attributes: {
+ 'domElements':
$( '<meta property="foo" content="bar" />' ).toArray()
+ }
+ } ],
+ undefined,
+ [ {
+ type: 'alienMeta',
+ attributes: {
+ 'domElements':
$( '<!-- inline -->' ).toArray()
+ }
+ } ]
+ ]
+ },
+ {
+ type: 'replaceMetadata',
+ remove: [],
+ insert: [
+ {
+ type: 'alienMeta',
+ attributes: {
+ 'domElements':
$( '<meta property="foo" content="bar" />' ).toArray()
+ }
+ },
+ {
+ type: 'alienMeta',
+ attributes: {
+ 'domElements':
$( '<!-- inline -->' ).toArray()
+ }
+ }
+ ]
+ },
+ { type: 'retain', length: 3 }
+ ],
+ expected: function( data ) {
+ ve.batchSplice( data, 19, 1, [] );
+ ve.batchSplice( data, 15, 2, [] );
+ ve.batchSplice( data, 5, 3, [] );
+ },
+ symmetric: true
+ },
+ {
+ desc: 'Metadata insertion/removal',
+ disabled: disableMetadataTests,
+ doc: 'withMeta',
+ a: [ 'newFromMetadataInsertion', 11, 2, [
metadataElement ] ],
+ b: [ 'newFromMetadataRemoval', 11, new ve.Range( 1, 3 )
],
+ aprime: [
+ { 'type': 'retain', 'length': 11 },
+ { 'type': 'retainMetadata', 'length': 1 },
+ {
+ 'type': 'replaceMetadata',
+ 'remove': [],
+ 'insert': [ metadataElement ]
+ },
+ { 'type': 'retainMetadata', 'length': 1 },
+ { 'type': 'retain', 'length': 2 }
+ ],
+ bprime: [
+ { 'type': 'retain', 'length': 11 },
+ { 'type': 'retainMetadata', 'length': 1 },
+ {
+ 'type': 'replaceMetadata',
+ 'remove': [
+
ve.dm.example.createExampleDocument( 'withMeta' ).metadata.getData( 11 )[ 1 ],
+ metadataElement,
+
ve.dm.example.createExampleDocument( 'withMeta' ).metadata.getData( 11 )[ 2 ]
+ ],
+ 'insert': [ metadataElement ]
+ },
+ { 'type': 'retainMetadata', 'length': 1 },
+ { 'type': 'retain', 'length': 2 }
+ ],
+ expected: function( data ) {
+ ve.batchSplice( data, 23, 4, [
+ metadataElement,
+ { 'type': '/alienMeta' }
+ ] );
+ },
+ symmetric: true
+ },
+ {
+ desc: 'Replace over metadata insertion',
+ disabled: disableMetadataTests || true, // we don't
support this yet
+ doc: 'data',
+ a: [ 'newFromMetadataInsertion', 2, 0, [
metadataElement ] ],
+ b: [ 'newFromRemoval', new ve.Range( 1, 4 ) ],
+ aprime: [
+ { 'type': 'retain', 'length': 1 },
+ {
+ 'type': 'replaceMetadata',
+ 'remove': [],
+ 'insert': [ metadataElement ]
+ },
+ { 'type': 'retain', 'length': 59 }
+ ],
+ bprime: [
+ { 'type': 'retain', 'length': 1 },
+ {
+ 'type': 'replace',
+ 'remove': [
+ 'a',
+ ['b', [ ve.dm.example.bold ]],
+ ['c', [ ve.dm.example.italic ]]
+ ],
+ 'removeMetadata': [
+ undefined,
+ [ metadataElement ],
+ undefined
+ ],
+ 'insert': [],
+ 'insertMetadata': []
+ },
+ {
+ 'type': 'replaceMetadata',
+ 'remove': [],
+ 'insert': [ metadataElement ]
+ },
+ { 'type': 'retain', 'length': 59 }
+ ],
+ expected: function( data ) {
+ ve.batchSplice( data, 1, 3, [
+ metadataElement,
+ { 'type': '/alienData' }
+ ] );
+ },
+ symmetric: true
+ }
+ ];
+ $.each( cases, function( _, test ) {
+ if ( test.symmetric && !test.disabled ) {
+ cases.push( {
+ desc: test.desc + ' [flipped]',
+ doc: test.doc,
+ a: test.b,
+ b: test.a,
+ aprime: test.bprime,
+ bprime: test.aprime,
+ expected: test.expected
+ } );
+ }
+ });
+ QUnit.expect( cases.length * 4);
+ $.each( cases, runTest2 );
+});
+
+QUnit.test( 'transpose (n-way)', function ( assert ) {
+ // Do N^2 transposition of N different transactions, taken two
+ // at a time. Verify that the results are consistent.
+ var cases, n = 0;
+ function runTest3( desc, doc, a, b ) {
+ var doc1, doc2, txa, txb, result;
+ doc1 = ve.dm.example.createExampleDocument( doc );
+ doc2 = ve.dm.example.createExampleDocument( doc );
+ txa = ve.dm.Transaction[ a[0] ].apply(null, [ doc1 ].concat(
a.slice(1) ) );
+ txb = ve.dm.Transaction[ b[0] ].apply(null, [ doc2 ].concat(
b.slice(1) ) );
+ result = txa.transpose( doc1, txb );
+ // apply a, then b' to doc1
+ doc1.commit( txa ); doc1.commit( result[1] );
+ // apply b, then a' to doc2
+ doc2.commit( txb ); doc2.commit( result[0] );
+ // both documents should be identical.
+ assert.equalNodeTree(
+ doc1.getDocumentNode(), doc2.getDocumentNode(),
+ desc + ': results after A,B\' and B,A\' match'
+ );
+ }
+
+ cases = [
+ {
+ doc: 'data',
+ transactions: {
+ // insertions at same point
+ 'insert X@0': [
+ 'newFromInsertion', 0,
+ [ { 'type': 'paragraph' }, 'X', {
'type': '/paragraph' } ]
+ ],
+ 'insert Y@0': [
+ 'newFromInsertion', 0,
+ [ { 'type': 'paragraph' }, 'Y', {
'type': '/paragraph' } ]
+ ],
+ // overlapping removals
+ 'remove ab': [
+ 'newFromRemoval', new ve.Range( 1, 3 )
+ ],
+ 'remove bc': [
+ 'newFromRemoval', new ve.Range( 2, 4 )
+ ],
+ // wrap
+ 'convert heading': [
+ 'newFromWrap', new ve.Range( 1, 4 ),
+ [ { 'type': 'heading', 'attributes': {
'level': 1 } } ],
+ [ { 'type': 'paragraph' } ], [], []
+ ],
+ // overlapping attribute change
+ 'change heading attrib': [
+ 'DISABLED', // attrib not yet supported
by transpose
+ 'newFromAttributeChanges', 0, {
'level': 2 }
+ ],
+ // overlapping annotation change
+ 'bold a': [
+ 'DISABLED', // annotation not yet
supported by transpose
+ 'newFromAnnotation', new ve.Range( 1, 2
), 'set',
+ ve.dm.example.createAnnotation(
ve.dm.example.bold )
+ ]
+ }
+ }
+ ];
+ $.each( cases, function( _, c ) {
+ var len = Object.keys( c.transactions ).length;
+ n += len * len;
+ } );
+ QUnit.expect( n );
+ $.each( cases, function( _, c ) {
+ $.each( c.transactions, function( aDesc, a ) {
+ $.each( c.transactions, function( bDesc, b ) {
+ if ( a[0] === 'DISABLED' || b[0] === 'DISABLED'
) {
+ assert.ok( true ); // skip this
transaction
+ } else {
+ runTest3( aDesc + ' <-> ' + bDesc,
c.doc, a, b );
+ }
+ } );
+ } );
+ } );
+});
diff --git a/modules/ve/test/index.php b/modules/ve/test/index.php
index ccb58e8..579a3aa 100644
--- a/modules/ve/test/index.php
+++ b/modules/ve/test/index.php
@@ -87,6 +87,7 @@
<script src="../../ve/dm/ve.dm.MetaList.js"></script>
<script
src="../../ve/dm/ve.dm.TransactionProcessor.js"></script>
<script src="../../ve/dm/ve.dm.Transaction.js"></script>
+ <script
src="../../ve/dm/ve.dm.Transaction.transpose.js"></script>
<script src="../../ve/dm/ve.dm.Surface.js"></script>
<script src="../../ve/dm/ve.dm.SurfaceFragment.js"></script>
<script src="../../ve/dm/ve.dm.DataString.js"></script>
@@ -277,6 +278,7 @@
<script src="dm/ve.dm.InternalList.test.js"></script>
<script src="dm/ve.dm.LinearData.test.js"></script>
<script src="dm/ve.dm.Transaction.test.js"></script>
+ <script src="dm/ve.dm.Transaction.transpose.test.js"></script>
<script src="dm/ve.dm.TransactionProcessor.test.js"></script>
<script src="dm/ve.dm.Surface.test.js"></script>
<script src="dm/ve.dm.SurfaceFragment.test.js"></script>
--
To view, visit https://gerrit.wikimedia.org/r/84442
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: newchange
Gerrit-Change-Id: I9eaefeed15bf22d2bca13ae1a52a7631425c1875
Gerrit-PatchSet: 1
Gerrit-Project: mediawiki/extensions/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Cscott <[email protected]>
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
