jenkins-bot has submitted this change and it was merged.
Change subject: Rewrite MetaList.onTransact
......................................................................
Rewrite MetaList.onTransact
The previous implementation couldn't deal with transactions that
replaced both data and metadata at the same time (rather than replacing
data while moving metadata around), and extending its approach to
deal with that case would have made it much more complex.
So I rewrote the algorithm from scratch. The previous implementation
scheduled deferred moves for existing items, but immediately processed
insertions and removals. This is problematic for replacements and
maintaining the order in the binary search list. So instead, this new
implementation builds an array representing what the new item list
should be, then processes insertions, removals and moves in the correct
order to achieve that state.
It looks like the previous implementation didn't always work correctly,
which was masked because the test suite passed full=false to
assertItemsMatchMetadata(). This rewrite fixes this.
Also remove setMove/applyMove from MetaItem, because we don't need them
anymore and they're evil anyway; and add isAttached(), because the new
algorithm needs it.
Change-Id: I899d2b3c94c2cfa55823879bca95456750f64382
---
M modules/ve/dm/ve.dm.MetaItem.js
M modules/ve/dm/ve.dm.MetaList.js
M modules/ve/test/dm/ve.dm.MetaList.test.js
3 files changed, 179 insertions(+), 127 deletions(-)
Approvals:
Esanders: Looks good to me, approved
jenkins-bot: Verified
diff --git a/modules/ve/dm/ve.dm.MetaItem.js b/modules/ve/dm/ve.dm.MetaItem.js
index 86a60ce..91657c9 100644
--- a/modules/ve/dm/ve.dm.MetaItem.js
+++ b/modules/ve/dm/ve.dm.MetaItem.js
@@ -129,39 +129,6 @@
};
/**
- * Queue up a change to the item's offset and index.
- * @param {number} offset New offset
- * @param {number} index New index
- */
-ve.dm.MetaItem.prototype.setMove = function ( offset, index ) {
- this.move = {
- 'offset': offset,
- 'index': index
- };
-};
-
-/**
- * Whether or not a move is pending.
- * @returns {boolean} A move is pending
- */
-ve.dm.MetaItem.prototype.isMovePending = function () {
- return this.move !== null;
-};
-
-/**
- * Apply the pending move and clear it.
- * @throws No move pending
- */
-ve.dm.MetaItem.prototype.applyMove = function () {
- if ( this.move === null ) {
- throw new Error( 'No move pending' );
- }
- this.setOffset( this.move.offset );
- this.setIndex( this.move.index );
- this.move = null;
-};
-
-/**
* Attach this item to a MetaList.
* @param {ve.dm.MetaList} list Parent list to attach to
* @param {number} offset Offset of this item in the parent list's document
@@ -187,3 +154,11 @@
this.index = null;
}
};
+
+/**
+ * Check whether this item is attached to a MetaList.
+ * @returns {boolean} Whether item is attached
+ */
+ve.dm.MetaItem.prototype.isAttached = function () {
+ return this.list !== null;
+};
diff --git a/modules/ve/dm/ve.dm.MetaList.js b/modules/ve/dm/ve.dm.MetaList.js
index 4096de4..e4c0ba6 100644
--- a/modules/ve/dm/ve.dm.MetaList.js
+++ b/modules/ve/dm/ve.dm.MetaList.js
@@ -80,122 +80,183 @@
* @emits remove
*/
ve.dm.MetaList.prototype.onTransact = function ( tx, reversed ) {
- var i, j, k, ilen, jlen, klen, ins, rm, itemIndex, item,
- offset = 0, newOffset = 0, index = 0, ops = tx.getOperations(),
- insertedItems = [], removedItems = [];
- // Look for replaceMetadata operations in the transaction and
insert/remove items as appropriate
- // This requires we also inspect retain, replace and replaceMetadata
operations in order to
- // track the offset and index. We track the pre-transaction offset, we
need to do that in
- // order to remove items correctly. This also means inserted items are
initially at the wrong
- // offset, but we translate it later.
+ var i, ilen, j, jlen, k, klen, item, ins, rm, insMeta, rmMeta,
+ numItems = this.items.length,
+ itemIndex = 0, // Current index into this.items
+ offset = 0, // Current pre-transaction offset
+ newOffset = 0, // Current post-transaction offset
+ index = 0, // Current pre-transaction index
+ newIndex = 0, // Current post-transaction index
+ // Array of items that should appear in this.items after we're
done. This includes newly
+ // inserted items as well as existing items that aren't being
removed.
+ // [ { item: ve.dm.MetaItem, offset: offset to move to, index:
index to move to } ]
+ newItems = [],
+ removedItems = [], // Array of items that should be removed
from this.items
+ events = [], // Array of events that we should emit when we're
done
+ ops = tx.getOperations();
+
+ // Go through the transaction operations and plan out where to add,
remove and move items. We
+ // don't actually touch this.items yet, otherwise we 1) get it out of
order which breaks
+ // findItem() and 2) lose information about what the pre-transaction
state of this.items was.
for ( i = 0, ilen = ops.length; i < ilen; i++ ) {
switch ( ops[i].type ) {
case 'retain':
+ // Advance itemIndex through the retain and
update items we encounter along the way
+ for ( ;
+ itemIndex < numItems &&
this.items[itemIndex].offset < offset + ops[i].length;
+ itemIndex++
+ ) {
+ // Plan to move this item to the
post-transaction offset and index
+ newItems.push( {
+ 'item': this.items[itemIndex],
+ 'offset':
this.items[itemIndex].offset + newOffset - offset,
+ 'index':
this.items[itemIndex].offset === offset ?
+ // Adjust index for
insertions or removals that happened at this offset
+ newIndex - index +
this.items[itemIndex].index :
+ // Offset is retained
over completely, don't adjust index
+
this.items[itemIndex].index } );
+ }
+
offset += ops[i].length;
newOffset += ops[i].length;
index = 0;
+ newIndex = 0;
break;
+
+ case 'retainMetadata':
+ // Advance itemIndex through the retain and
update items we encounter along the way
+ for ( ;
+ itemIndex < numItems &&
this.items[itemIndex].offset === offset &&
+ this.items[itemIndex].index <
index + ops[i].length;
+ itemIndex++
+ ) {
+ newItems.push( {
+ 'item': this.items[itemIndex],
+ 'offset': newOffset,
+ 'index':
this.items[itemIndex].index + newIndex - index
+ } );
+ }
+
+ index += ops[i].length;
+ newIndex += ops[i].length;
+ break;
+
case 'replace':
- // if we have metadata replace info we can
calculate the new
- // offset and index directly
- ins = reversed ? ops[i].removeMetadata :
ops[i].insertMetadata;
- rm = reversed ? ops[i].insertMetadata :
ops[i].removeMetadata;
- if ( rm === undefined ) {
- // no impact on metadata.
- /* jshint noempty: false */
- } else if ( ins.length === 0 ) {
- for ( j = 0, jlen = rm.length; j <
jlen; j++ ) {
- if ( rm[j] !== undefined ) {
- for ( k = 0, klen =
rm[j].length; k < klen; k++ ) {
- item =
this.deleteRemovedItem( offset + j, k );
-
removedItems.push( { 'item': item, 'offset': offset + j, 'index': k } );
- }
- }
+ ins = reversed ? ops[i].remove : ops[i].insert;
+ rm = reversed ? ops[i].insert : ops[i].remove;
+ if ( ops[i].removeMetadata !== undefined ) {
+ insMeta = reversed ?
ops[i].removeMetadata : ops[i].insertMetadata;
+ rmMeta = reversed ?
ops[i].insertMetadata : ops[i].removeMetadata;
+
+ // Process removed metadata
+ for ( ;
+ itemIndex < numItems &&
+
this.items[itemIndex].offset < offset + rmMeta.length;
+ itemIndex++
+ ) {
+ removedItems.push(
this.items[itemIndex] );
}
- } else if ( rm.length === 0 ) {
- itemIndex = -Math.pow(2, 53); // INT_MIN
- for ( j = 0, jlen = ins.length; j <
jlen; j++ ) {
- if ( ins[j] !== undefined ) {
- for ( k = 0, klen =
ins[j].length; k < klen; k++ ) {
- item =
ve.dm.metaItemFactory.createFromElement( ins[j][k] );
- // offset is
pre-transaction, but we'll fix it up w/ setMove
-
this.addInsertedItem( offset, itemIndex++, item );
- item.setMove(
newOffset + j, k );
-
insertedItems.push( { 'item': item } );
+
+ // Process inserted metadata
+ for ( j = 0, jlen = insMeta.length; j <
jlen; j++ ) {
+ if ( insMeta[j] ) {
+ for ( k = 0, klen =
insMeta[j].length; k < klen; k++ ) {
+ item =
ve.dm.metaItemFactory.createFromElement( insMeta[j][k] );
+ newItems.push( {
+ 'item':
item,
+
'offset': newOffset + j,
+
'index': k
+ } );
}
}
}
} else {
- // find the first itemIndex - the rest
should be in order after it
- for ( j = 0, jlen = rm.length; j <
jlen; j++ ) {
- if ( rm[j] !== undefined ) {
- itemIndex =
this.findItem( offset + j, 0 );
- break;
- }
- }
- // iterate through all the inserted
metaItems
- for ( j = 0, jlen = ins.length; j <
jlen; j++ ) {
- item = ins[j];
- if ( item !== undefined ) {
- for ( k = 0, klen =
item.length; k < klen; k++ ) {
- // Queue up the
move for later so we don't break the metaItem ordering
-
this.items[itemIndex].setMove( newOffset + j, k );
- itemIndex++;
- }
- }
+ // No metadata handling specified,
which means we just have to deal with offset
+ // adjustments, same as a retain
+ for ( ;
+ itemIndex < numItems &&
+
this.items[itemIndex].offset < offset + rm.length;
+ itemIndex++
+ ) {
+ newItems.push( {
+ 'item':
this.items[itemIndex],
+ 'offset':
this.items[itemIndex].offset + newOffset - offset,
+ 'index':
this.items[itemIndex].index
+ } );
}
}
- offset += reversed ? ops[i].insert.length :
ops[i].remove.length;
- newOffset += reversed ? ops[i].remove.length :
ops[i].insert.length;
- index = 0;
+
+ offset += rm.length;
+ newOffset += ins.length;
break;
- case 'retainMetadata':
- index += ops[i].length;
- break;
+
case 'replaceMetadata':
- ins = reversed ? ops[i].remove : ops[i].insert;
- rm = reversed ? ops[i].insert : ops[i].remove;
- for ( j = 0, jlen = rm.length; j < jlen; j++ ) {
- item = this.deleteRemovedItem( offset,
index + j );
- removedItems.push( { 'item': item,
'offset': offset, 'index': index } );
+ insMeta = reversed ? ops[i].remove :
ops[i].insert;
+ rmMeta = reversed ? ops[i].insert :
ops[i].remove;
+
+ // Process removed items
+ for ( ;
+ itemIndex < numItems &&
this.items[itemIndex].offset === offset &&
+ this.items[itemIndex].index <
index + rmMeta.length;
+ itemIndex++
+ ) {
+ removedItems.push(
this.items[itemIndex] );
}
- for ( j = 0, jlen = ins.length; j < jlen; j++ )
{
- item =
ve.dm.metaItemFactory.createFromElement( ins[j] );
- // offset and index are
pre-transaction, but we'll fix them later
- this.addInsertedItem( offset, index +
j, item );
- insertedItems.push( { 'item': item } );
+
+ // Process inserted items
+ for ( j = 0, jlen = insMeta.length; j < jlen;
j++ ) {
+ item =
ve.dm.metaItemFactory.createFromElement( insMeta[j] );
+ newItems.push( { 'item': item,
'offset': newOffset, 'index': newIndex + j } );
}
- index += rm.length;
+
+ index += rmMeta.length;
+ newIndex += insMeta.length;
break;
}
}
-
- // Translate the offsets of all items, and reindex them too
- // Reindexing is simple because the above ensures the items are already
in the right order
- offset = -1;
- index = 0;
- for ( i = 0, ilen = this.items.length; i < ilen; i++ ) {
- if ( this.items[i].isMovePending() ) {
- // move was calculated from metadata replace info, just
apply it
- this.items[i].applyMove();
- } else {
- // otherwise calculate the new offset from the
transaction
- this.items[i].setOffset( tx.translateOffset(
this.items[i].getOffset(), reversed ) );
- if ( this.items[i].getOffset() === offset ) {
- index++;
- } else {
- index = 0;
- }
- this.items[i].setIndex( index );
- }
- offset = this.items[i].getOffset();
+ // Update the remaining items that the transaction didn't touch or
retain over
+ for ( ; itemIndex < numItems; itemIndex++ ) {
+ newItems.push( {
+ 'item': this.items[itemIndex],
+ 'offset': this.items[itemIndex].offset + newOffset -
offset,
+ 'index': this.items[itemIndex].offset === offset ?
+ newIndex - index + this.items[itemIndex].index :
+ this.items[itemIndex].index
+ } );
}
- for ( i = 0, ilen = insertedItems.length; i < ilen; i++ ) {
- this.emit( 'insert', insertedItems[i].item );
- }
+ // Process the changes, and queue up events. We emit the events at the
end when the MetaList
+ // is back in a consistent state
+
+ // Remove removed items
for ( i = 0, ilen = removedItems.length; i < ilen; i++ ) {
- this.emit( 'remove', removedItems[i].item,
removedItems[i].offset, removedItems[i].index );
+ this.deleteRemovedItem( removedItems[i].offset,
removedItems[i].index );
+ events.push( [
+ 'remove', removedItems[i].item, removedItems[i].offset,
removedItems[i].index
+ ] );
+ }
+
+ // Move moved items (these appear as inserted items that are already
attached)
+ for ( i = 0, ilen = newItems.length; i < ilen; i++ ) {
+ if ( newItems[i].item.isAttached() ) {
+ if ( newItems[i].offset !== newItems[i].item.offset ||
newItems[i].index !== newItems[i].item.index ) {
+ this.deleteRemovedItem(
newItems[i].item.offset, newItems[i].item.index );
+ this.addInsertedItem( newItems[i].offset,
newItems[i].index, newItems[i].item );
+ }
+ }
+ }
+
+ // Insert new items
+ for ( i = 0, ilen = newItems.length; i < ilen; i++ ) {
+ if ( !newItems[i].item.isAttached() ) {
+ this.addInsertedItem( newItems[i].offset,
newItems[i].index, newItems[i].item );
+ events.push( [ 'insert', newItems[i].item ] );
+ }
+ }
+
+ // Emit events
+ for ( i = 0, ilen = events.length; i < ilen; i++ ) {
+ this.emit.apply( this, events[i] );
}
};
diff --git a/modules/ve/test/dm/ve.dm.MetaList.test.js
b/modules/ve/test/dm/ve.dm.MetaList.test.js
index cc8480d..4c9214e 100644
--- a/modules/ve/test/dm/ve.dm.MetaList.test.js
+++ b/modules/ve/test/dm/ve.dm.MetaList.test.js
@@ -56,6 +56,22 @@
'msg': 'Transaction inserting, replacing and
removing text'
},
{
+ 'calls': [
+ [ 'pushRetain', 1 ],
+ [
+ 'pushReplace', doc, 1, 9,
+ [ 'f', 'O', 'O', 'b', 'A', 'R',
'b', 'A', 'Z' ],
+ [
+ undefined,
+ [
ve.dm.example.withMetaMetaData[9][0], ve.dm.example.withMetaMetaData[7][0] ],
+ undefined, undefined,
undefined, [ ve.dm.example.withMetaMetaData[4][0] ],
+ undefined, undefined,
undefined
+ ]
+ ]
+ ],
+ 'msg': 'Transaction replacing text and metadata
at the same time'
+ },
+ {
// delta: 0
'calls': [
[ 'pushRetainMetadata', 1 ],
@@ -115,7 +131,7 @@
];
// HACK: This works because most transactions above don't change the
document length, and the
// ones that do change it cancel out
- QUnit.expect( cases.length*( 4*doc.metadata.getTotalDataLength() + 2 )
);
+ QUnit.expect( cases.length*( 8*doc.metadata.getTotalDataLength() + 2 )
);
for ( i = 0; i < cases.length; i++ ) {
tx = new ve.dm.Transaction();
@@ -127,9 +143,9 @@
list = new ve.dm.MetaList( surface );
// Test both the transaction-via-surface and
transaction-via-document flows
surface.change( tx );
- assertItemsMatchMetadata( assert, doc.metadata, list,
cases[i].msg, false );
+ assertItemsMatchMetadata( assert, doc.metadata, list,
cases[i].msg, true );
doc.rollback( tx );
- assertItemsMatchMetadata( assert, doc.metadata, list,
cases[i].msg + ' (rollback)', false );
+ assertItemsMatchMetadata( assert, doc.metadata, list,
cases[i].msg + ' (rollback)', true );
}
} );
--
To view, visit https://gerrit.wikimedia.org/r/82786
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: I899d2b3c94c2cfa55823879bca95456750f64382
Gerrit-PatchSet: 7
Gerrit-Project: mediawiki/extensions/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Catrope <[email protected]>
Gerrit-Reviewer: Esanders <[email protected]>
Gerrit-Reviewer: jenkins-bot
_______________________________________________
MediaWiki-commits mailing list
[email protected]
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
