jenkins-bot has submitted this change and it was merged. (
https://gerrit.wikimedia.org/r/368587 )
Change subject: VisualDiff: Refactor for historical diffs
......................................................................
VisualDiff: Refactor for historical diffs
Make computeDiff and associated functions more generic, so
they can be used for the document diff and the internal
list diff.
Change-Id: Idf7f694080f8f633147dd861ea0180140f16c1d8
---
M src/dm/ve.dm.VisualDiff.js
M src/ui/elements/ve.ui.DiffElement.js
2 files changed, 265 insertions(+), 138 deletions(-)
Approvals:
jenkins-bot: Verified
Jforrester: Looks good to me, approved
diff --git a/src/dm/ve.dm.VisualDiff.js b/src/dm/ve.dm.VisualDiff.js
index 8104d02..a2c006e 100644
--- a/src/dm/ve.dm.VisualDiff.js
+++ b/src/dm/ve.dm.VisualDiff.js
@@ -34,7 +34,11 @@
this.freezeInternalListIndices( this.oldDoc );
this.freezeInternalListIndices( this.newDoc );
- this.computeDiff();
+ this.diff = {
+ docDiff: this.computeDiff( this.oldDocChildren,
this.newDocChildren ),
+ internalListDiff: this.getInternalListDiffInfo()
+ };
+
};
/**
@@ -84,91 +88,97 @@
};
/**
- * Get the diff between the two documents, in two steps: (1) Compare the
children
- * of the old and new document nodes and record any pair where the old child
and
+ * Get the diff between the two trees, in two steps: (1) Compare the children
+ * of the old and new root nodes and record any pair where the old child and
* new child are identical. (If an old child is identical to two new children,
it
* will be paired with the first one only.) (2) If any children of the old or
new
- * document nodes remain unpaired, decide whether they are an old child that
has
+ * root nodes remain unpaired, decide whether they are an old child that has
* been removed, a new child that has been inserted, or a pair in which the old
* child was changed into the new child.
+ *
+ * @param {Array} oldRootChildren Children of the old root node
+ * @param {Array} newRootChildren Children of the new root node
+ * @returns {Object} Object containing diff information
*/
-ve.dm.VisualDiff.prototype.computeDiff = function () {
+ve.dm.VisualDiff.prototype.computeDiff = function ( oldRootChildren,
newRootChildren ) {
var i, ilen, j, jlen,
- oldDocChildrenToDiff = [],
- newDocChildrenToDiff = [];
+ oldRootChildrenToDiff = [],
+ newRootChildrenToDiff = [],
+ diff = {
+ rootChildrenOldToNew: {},
+ rootChildrenNewToOld: {},
+ rootChildrenRemove: [],
+ rootChildrenInsert: []
+ };
- this.diff = {
- docChildrenOldToNew: {},
- docChildrenNewToOld: {},
- docChildrenRemove: [],
- docChildrenInsert: [],
- internalListDiff: this.getInternalListDiffInfo()
- };
+ // STEP 1: Find identical root-node children
- // STEP 1: Find identical document-node children
+ for ( i = 0, ilen = oldRootChildren.length; i < ilen; i++ ) {
+ for ( j = 0, jlen = newRootChildren.length; j < jlen; j++ ) {
+ if ( !diff.rootChildrenNewToOld.hasOwnProperty( j ) &&
+ this.compareRootChildren( oldRootChildren[ i ],
newRootChildren[ j ] ) ) {
- for ( i = 0, ilen = this.oldDocChildren.length; i < ilen; i++ ) {
- for ( j = 0, jlen = this.newDocChildren.length; j < jlen; j++ )
{
- if ( !this.diff.docChildrenNewToOld.hasOwnProperty( j )
&&
- this.compareDocChildren( this.oldDocChildren[ i
], this.newDocChildren[ j ] ) ) {
-
- this.diff.docChildrenOldToNew[ i ] = j;
- this.diff.docChildrenNewToOld[ j ] = i;
+ diff.rootChildrenOldToNew[ i ] = j;
+ diff.rootChildrenNewToOld[ j ] = i;
break;
}
// If no new nodes equalled the old node, add it to
nodes to diff
if ( j === jlen - 1 ) {
- oldDocChildrenToDiff.push( i );
+ oldRootChildrenToDiff.push( i );
}
}
}
for ( j = 0; j < jlen; j++ ) {
- if ( !this.diff.docChildrenNewToOld.hasOwnProperty( j ) ) {
- newDocChildrenToDiff.push( j );
+ if ( !diff.rootChildrenNewToOld.hasOwnProperty( j ) ) {
+ newRootChildrenToDiff.push( j );
}
}
- // STEP 2: Find removed, inserted and modified document-node children
+ // STEP 2: Find removed, inserted and modified root-node children
- if ( oldDocChildrenToDiff.length !== 0 || newDocChildrenToDiff.length
!== 0 ) {
+ if ( oldRootChildrenToDiff.length !== 0 || newRootChildrenToDiff.length
!== 0 ) {
- if ( oldDocChildrenToDiff.length === 0 ) {
+ if ( oldRootChildrenToDiff.length === 0 ) {
// Everything new is an insert
- this.diff.docChildrenInsert = newDocChildrenToDiff;
+ diff.rootChildrenInsert = newRootChildrenToDiff;
- } else if ( newDocChildrenToDiff.length === 0 ) {
+ } else if ( newRootChildrenToDiff.length === 0 ) {
// Everything old is a remove
- this.diff.docChildrenRemove = oldDocChildrenToDiff;
+ diff.rootChildrenRemove = oldRootChildrenToDiff;
} else {
// Find out which remaining docChildren are removed,
inserted or modified
- this.findModifiedDocChildren( oldDocChildrenToDiff,
newDocChildrenToDiff );
+ this.findModifiedRootChildren(
+ oldRootChildrenToDiff, newRootChildrenToDiff,
oldRootChildren, newRootChildren, diff
+ );
}
}
+
+ return diff;
};
/**
- * Compare the linear data for two nodes
+ * Compare the linear data for two root-child nodes
*
- * @param {ve.dm.Node} oldDocChild Child of the old document node
- * @param {ve.dm.Node} newDocChild Child of the new document node
+ * @param {ve.dm.Node} oldRootChild Child of the old root node
+ * @param {ve.dm.Node} newRootChild Child of the new root node
* @return {boolean} The linear data is the same
*/
-ve.dm.VisualDiff.prototype.compareDocChildren = function ( oldDocChild,
newDocChild ) {
+ve.dm.VisualDiff.prototype.compareRootChildren = function ( oldRootChild,
newRootChild ) {
var i, ilen, oldData, newData, oldStore, newStore;
- if ( oldDocChild.length !== newDocChild.length ||
!oldDocChild.isDiffComparable( newDocChild ) ) {
+ if ( oldRootChild.length !== newRootChild.length ||
!oldRootChild.isDiffComparable( newRootChild ) ) {
return false;
}
- oldData = this.oldDoc.getData( oldDocChild.getOuterRange() );
- newData = this.newDoc.getData( newDocChild.getOuterRange() );
+ oldData = this.oldDoc.getData( oldRootChild.getOuterRange() );
+ newData = this.newDoc.getData( newRootChild.getOuterRange() );
if ( JSON.stringify( oldData ) === JSON.stringify( newData ) ) {
return true;
@@ -190,8 +200,8 @@
};
/**
- * Diff each child of the old document node against each child of the new
- * document; but if the differs decide that an old child is similar enough to a
+ * Diff each child of the old root node against each child of the new root
+ * node; but if the differs decide that an old child is similar enough to a
* new child, record these as a change from the old child to the new child and
* don't diff any more children against either child.
*
@@ -199,40 +209,39 @@
* similar to two of the new children), but diffing every old child against
* every new child could have a heavy performance cost.
*
- * @param {Array} oldDocChildren The children of the old document with no
- * identical partners in the new document
- * @param {Array} newDocChildren The children of the new document with no
- * identical partners in the old document
+ * @param {Array} oldIndices Indices of the old root children diff
+ * @param {Array} newIndices Indices of the new root children diff
+ * @param {Array} oldRootChildren Children of the old root node
+ * @param {Array} newRootChildren Children of the new root node
+ * @param {Object} diff Object that will contain information about the diff
*/
-ve.dm.VisualDiff.prototype.findModifiedDocChildren = function (
oldDocChildren, newDocChildren ) {
- var diff, i, j,
- ilen = oldDocChildren.length,
- jlen = newDocChildren.length;
+ve.dm.VisualDiff.prototype.findModifiedRootChildren = function ( oldIndices,
newIndices, oldRootChildren, newRootChildren, diff ) {
+ var diffResults, i, j,
+ ilen = oldIndices.length,
+ jlen = newIndices.length;
for ( i = 0; i < ilen; i++ ) {
for ( j = 0; j < jlen; j++ ) {
- if ( oldDocChildren[ i ] !== null && newDocChildren[ j
] !== null ) {
+ if ( oldIndices[ i ] !== null && newIndices[ j ] !==
null ) {
- // Try to diff the nodes. If they are too
different, diff will be false
- diff = this.getDocChildDiff(
- this.oldDocChildren[ oldDocChildren[ i
] ],
- this.newDocChildren[ newDocChildren[ j
] ]
- );
+ diffResults = this.getDocChildDiff(
oldRootChildren[ oldIndices[ i ] ], newRootChildren[ newIndices[ j ] ] );
- if ( diff ) {
- this.diff.docChildrenOldToNew[
oldDocChildren[ i ] ] = {
- node: newDocChildren[ j ],
- diff: diff,
+ if ( diffResults ) {
+ diff.rootChildrenOldToNew[ oldIndices[
i ] ] = {
+ node: newIndices[ j ],
+ diff: diffResults,
// TODO: Neaten this
- correspondingNodes:
this.treeDiffer.Differ.prototype.getCorrespondingNodes( diff.treeDiff,
diff.oldTree.orderedNodes.length, diff.newTree.orderedNodes.length )
+ correspondingNodes:
this.treeDiffer.Differ.prototype.getCorrespondingNodes(
+ diffResults.treeDiff,
diffResults.oldTree.orderedNodes.length, diffResults.newTree.orderedNodes.length
+ )
};
- this.diff.docChildrenNewToOld[
newDocChildren[ j ] ] = {
- node: oldDocChildren[ i ]
+ diff.rootChildrenNewToOld[ newIndices[
j ] ] = {
+ node: oldIndices[ i ]
};
- oldDocChildren[ i ] = null;
- newDocChildren[ j ] = null;
+ oldIndices[ i ] = null;
+ newIndices[ j ] = null;
break;
}
@@ -243,20 +252,20 @@
// Any nodes remaining in the 'toDiff' arrays are removes and inserts
for ( i = 0; i < ilen; i++ ) {
- if ( oldDocChildren[ i ] !== null ) {
- this.diff.docChildrenRemove.push( oldDocChildren[ i ] );
+ if ( oldIndices[ i ] !== null ) {
+ diff.rootChildrenRemove.push( oldIndices[ i ] );
}
}
for ( j = 0; j < jlen; j++ ) {
- if ( newDocChildren[ j ] !== null ) {
- this.diff.docChildrenInsert.push( newDocChildren[ j ] );
+ if ( newIndices[ j ] !== null ) {
+ diff.rootChildrenInsert.push( newIndices[ j ] );
}
}
};
/**
- * Get the diff between a child of the old coument node and a child of the new
+ * Get the diff between a child of the old document node and a child of the new
* document node. There are three steps: (1) Do a tree diff to find the minimal
* transactions between the old child and the new child. Allowed transactions
* are: remove a node, insert a node, or change an old node to a new node. (The
@@ -446,86 +455,204 @@
* @return {Object} Internal list diff object
*/
ve.dm.VisualDiff.prototype.getInternalListDiffInfo = function () {
- var i, ilen, diff, internalListDiffGroup,
- group, groupIndexOrder, nodeIndex, item,
+ var i, ilen, j, jlen, diff, item, group,
+ newItems, oldItems, nodeIndices,
oldDocNodeGroups =
this.oldDoc.getInternalList().getNodeGroups(),
newDocNodeGroups =
this.newDoc.getInternalList().getNodeGroups(),
- retainedInternalListItems = {},
- removedInternalListItems = {},
- internalListDiffInfo = [];
+ oldDocInternalListItems,
+ newDocInternalListItems,
+ groups = [],
+ internalListDiffInfo = {};
- // Find all nodes referenced by the new document's internal list
+ function getInternalListItemsToDiff( indexOrder, nodes ) {
+ var i, ilen, nodeIndex,
+ internalListItems = {
+ toDiff: [],
+ indices: []
+ };
+
+ for ( i = 0, ilen = indexOrder.length; i < ilen; i++ ) {
+ nodeIndex = indexOrder[ i ];
+ if ( nodeIndex !== null ) {
+ internalListItems.toDiff.push( nodes[ nodeIndex
] );
+ internalListItems.indices.push( {
+ indexOrder: i,
+ nodeIndex: nodeIndex
+ } );
+ }
+ }
+
+ return internalListItems;
+ }
+
+ function getInternalListItems( indexOrder, nodes, action ) {
+ var i, ilen, nodeIndex, internalListItems = [];
+
+ for ( i = 0, ilen = indexOrder.length; i < ilen; i++ ) {
+ nodeIndex = indexOrder[ i ];
+ if ( nodeIndex !== null ) {
+ internalListItems.push( {
+ diff: action,
+ indexOrder: i,
+ nodeIndex: nodeIndex
+ } );
+ }
+ }
+
+ return internalListItems;
+ }
+
+ function containsDiff( diffObject ) {
+ var i;
+
+ for ( i in diffObject ) {
+ if ( typeof diffObject[ i ] !== 'number' ) {
+ return true;
+ }
+ }
+
+ return false;
+ }
+
+ // Find all groups common to old and new docs
+ // Also find inserted groups
for ( group in newDocNodeGroups ) {
- groupIndexOrder = newDocNodeGroups[ group ].indexOrder;
- internalListDiffInfo[ group ] = [];
- for ( i = 0, ilen = groupIndexOrder.length; i < ilen; i++ ) {
- nodeIndex = groupIndexOrder[ i ];
- retainedInternalListItems[ nodeIndex ] = true;
- internalListDiffInfo[ group ].push( {
- indexOrder: i,
- nodeIndex: nodeIndex,
- removed: false
+ if ( group in oldDocNodeGroups ) {
+ groups.push( {
+ group: group,
+ action: 'diff'
} );
- internalListDiffInfo[ group ].changes = false; //
Becomes true later if there are changes
+ } else {
+ groups.push( {
+ group: group,
+ action: 'insert'
+ } );
}
}
- // Find all nodes referenced by the old document's internal list
+ // Find removed groups
for ( group in oldDocNodeGroups ) {
- groupIndexOrder = oldDocNodeGroups[ group ].indexOrder;
- for ( i = 0; i < groupIndexOrder.length - 1; i++ ) {
- nodeIndex = groupIndexOrder[ i ];
- if ( retainedInternalListItems[ nodeIndex ] ) {
- continue;
- }
- // TODO: Work out what should happen if the whole list
group was removed
- if ( internalListDiffInfo[ group ] === undefined ) {
- internalListDiffInfo[ group ] = [];
- internalListDiffInfo[ group ].changes = false;
// Becomes true later
- }
- internalListDiffInfo[ group ].push( {
- indexOrder: i,
- nodeIndex: nodeIndex,
- removed: true
+ if ( !( group in newDocNodeGroups ) ) {
+ groups.push( {
+ group: group,
+ action: 'remove'
} );
- removedInternalListItems[ nodeIndex ] = group;
}
}
- for ( group in internalListDiffInfo ) {
- internalListDiffGroup = internalListDiffInfo[ group ].sort(
function ( a, b ) {
- if ( a.indexOrder === b.indexOrder ) {
- return a.removed ? 1 : -1;
- }
- return a.indexOrder > b.indexOrder ? 1 : -1;
- } );
- for ( i = 0, ilen = internalListDiffGroup.length; i < ilen; i++
) {
- item = internalListDiffGroup[ i ];
- if ( item.nodeIndex >
this.oldDocInternalListNode.children.length - 1 ) {
- // Item was inserted
- item.diff = 1;
- internalListDiffGroup.changes = true;
- } else if ( item.nodeIndex in removedInternalListItems
) {
- // Item was removed
- item.diff = -1;
- internalListDiffGroup.changes = true;
- } else {
- // Item corresponds to the item in the old
document's internal list with
- // the same index. They could be the same or
changed.
- diff = this.getDocChildDiff(
- this.oldDocInternalListNode.children[
item.nodeIndex ],
- this.newDocInternalListNode.children[
item.nodeIndex ],
- 0
+ // TODO: Work out how to calculate moves; for now, keep in the same
order
+ // as new doc, with removes at the end
+
+ // Diff the internal list items for each group
+ for ( i = 0, ilen = groups.length; i < ilen; i++ ) {
+ group = groups[ i ];
+ switch ( group.action ) {
+ case 'diff':
+
+ // Get old and new doc internal list items for
this group
+ oldDocInternalListItems =
getInternalListItemsToDiff(
+ oldDocNodeGroups[ group.group
].indexOrder,
+ this.oldDocInternalListNode.children
);
- if ( diff.diffInfo && diff.diffInfo.length > 0
) {
- // Item was changed from an old item
- item.diff = diff;
- internalListDiffGroup.changes = true;
- } else {
- // Item is unchanged
- item.diff = 0;
+ newDocInternalListItems =
getInternalListItemsToDiff(
+ newDocNodeGroups[ group.group
].indexOrder,
+ this.newDocInternalListNode.children
+ );
+
+ // Diff internal list items
+ diff = this.computeDiff(
+ oldDocInternalListItems.toDiff,
+ newDocInternalListItems.toDiff,
+ this.internalListDiff
+ );
+
+ // Check there actually are any changes
+ if (
+ ( diff.rootChildrenRemove.length > 0 ||
diff.rootChildrenInsert.length > 0 ) ||
+ ( containsDiff(
diff.rootChildrenOldToNew ) )
+ ) {
+
+ // There are changes.
+ // Mark each new doc internal list item
as unchanged, changed or inserted
+ newItems =
newDocInternalListItems.indices;
+ nodeIndices = {}; // For finding
removed internalListItems
+ for ( j = 0, jlen = newItems.length; j
< jlen; j++ ) {
+ item = newItems[ j ];
+ if ( typeof
diff.rootChildrenNewToOld[ item.indexOrder ] === 'number' ) {
+
+ // Item hasn't changed
+ item.diff = 0;
+ nodeIndices[
item.nodeIndex ] = true;
+
+ } else if (
diff.rootChildrenNewToOld[ item.indexOrder ] === undefined ) {
+
+ // Item was inserted
+ item.diff = 1;
+ nodeIndices[
item.nodeIndex ] = true;
+
+ } else {
+
+ // Item has changed
+ // (The diff object is
stored in rootChildrenOldToNew)
+ item.diff =
diff.rootChildrenOldToNew[
+
diff.rootChildrenNewToOld[ item.indexOrder ].node
+ ].diff;
+ nodeIndices[
item.nodeIndex ] = true;
+
+ }
+ }
+
+ // Add all removed items and mark as
removed
+ oldItems =
oldDocInternalListItems.indices;
+ for ( j = 0, jlen = oldItems.length; j
< jlen; j++ ) {
+ item = oldItems[ j ];
+ if ( !( item.nodeIndex in
nodeIndices ) ) {
+
+ // Item was removed
+ item.diff = -1;
+ newItems.push( item );
+
+ }
+ }
+
+ // Sort internal list items by index
order
+ internalListDiffInfo[ group.group ] =
newItems.sort( function ( a, b ) {
+ if ( a.indexOrder ===
b.indexOrder ) {
+
+ // When index order is
the same, put removed item first
+ return a.diff === -1 ?
-1 : 1;
+
+ }
+ return a.indexOrder >
b.indexOrder ? 1 : -1;
+ } );
+
+ internalListDiffInfo[ group.group
].changes = true;
}
- }
+
+ break;
+
+ case 'insert':
+
+ // Get new doc internal list items for this
group and mark as inserted
+ internalListDiffInfo[ group.group ] =
getInternalListItems(
+ newDocNodeGroups[ group.group
].indexOrder,
+ this.newDocInternalListNode.children,
+ 1
+ );
+ internalListDiffInfo[ group.group ].changes =
true;
+ break;
+
+ case 'remove':
+
+ // Get old doc internal list items for this
group and mark as removed
+ internalListDiffInfo[ group.group ] =
getInternalListItems(
+ oldDocNodeGroups[ group.group
].indexOrder,
+ this.oldDocInternalListNode.children,
+ -1
+ );
+ internalListDiffInfo[ group.group ].changes =
true;
+ break;
+
}
}
diff --git a/src/ui/elements/ve.ui.DiffElement.js
b/src/ui/elements/ve.ui.DiffElement.js
index 92e2a9c..e52a4c1 100644
--- a/src/ui/elements/ve.ui.DiffElement.js
+++ b/src/ui/elements/ve.ui.DiffElement.js
@@ -34,10 +34,10 @@
this.oldDocInternalListNode = visualDiff.oldDocInternalListNode;
// Diff
- this.oldToNew = diff.docChildrenOldToNew;
- this.newToOld = diff.docChildrenNewToOld;
- this.insert = diff.docChildrenInsert;
- this.remove = diff.docChildrenRemove;
+ this.oldToNew = diff.docDiff.rootChildrenOldToNew;
+ this.newToOld = diff.docDiff.rootChildrenNewToOld;
+ this.insert = diff.docDiff.rootChildrenInsert;
+ this.remove = diff.docDiff.rootChildrenRemove;
this.internalListDiff = diff.internalListDiff;
this.$overlays = $( '<div>' ).addClass( 've-ui-diffElement-overlays' );
--
To view, visit https://gerrit.wikimedia.org/r/368587
To unsubscribe, visit https://gerrit.wikimedia.org/r/settings
Gerrit-MessageType: merged
Gerrit-Change-Id: Idf7f694080f8f633147dd861ea0180140f16c1d8
Gerrit-PatchSet: 5
Gerrit-Project: VisualEditor/VisualEditor
Gerrit-Branch: master
Gerrit-Owner: Tchanders <thalia.e.c...@googlemail.com>
Gerrit-Reviewer: Esanders <esand...@wikimedia.org>
Gerrit-Reviewer: Jforrester <jforres...@wikimedia.org>
Gerrit-Reviewer: Tchanders <thalia.e.c...@googlemail.com>
Gerrit-Reviewer: jenkins-bot <>
_______________________________________________
MediaWiki-commits mailing list
MediaWiki-commits@lists.wikimedia.org
https://lists.wikimedia.org/mailman/listinfo/mediawiki-commits
