1 /**
  2  * Copyright (C) 2013 KO GmbH <copyright@kogmbh.com>
  3  *
  4  * @licstart
  5  * This file is part of WebODF.
  6  *
  7  * WebODF is free software: you can redistribute it and/or modify it
  8  * under the terms of the GNU Affero General Public License (GNU AGPL)
  9  * as published by the Free Software Foundation, either version 3 of
 10  * the License, or (at your option) any later version.
 11  *
 12  * WebODF is distributed in the hope that it will be useful, but
 13  * WITHOUT ANY WARRANTY; without even the implied warranty of
 14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 15  * GNU Affero General Public License for more details.
 16  *
 17  * You should have received a copy of the GNU Affero General Public License
 18  * along with WebODF.  If not, see <http://www.gnu.org/licenses/>.
 19  * @licend
 20  *
 21  * @source: http://www.webodf.org/
 22  * @source: https://github.com/kogmbh/WebODF/
 23  */
 24 
 25 /*global runtime, ops */
 26 
 27 /**
 28  * @constructor
 29  */
 30 ops.OperationTransformMatrix = function OperationTransformMatrix() {
 31     "use strict";
 32 
 33     /* Utility methods */
 34 
 35     /**
 36      * Inverts the range spanned up by the spec's parameter position and length,
 37      * so that position is at the other end of the range and length relative to that.
 38      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
 39      * @return {undefined}
 40      */
 41     function invertMoveCursorSpecRange(moveCursorSpec) {
 42         moveCursorSpec.position = moveCursorSpec.position + moveCursorSpec.length;
 43         moveCursorSpec.length *= -1;
 44     }
 45 
 46     /**
 47      * Inverts the range spanned up by position and length if the length is negative.
 48      * Returns true if an inversion was done, false otherwise.
 49      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
 50      * @return {!boolean}
 51      */
 52     function invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec) {
 53         var isBackwards = (moveCursorSpec.length < 0);
 54 
 55         if (isBackwards) {
 56             invertMoveCursorSpecRange(moveCursorSpec);
 57         }
 58         return isBackwards;
 59     }
 60 
 61     /**
 62      * Returns a list with all attributes in setProperties that refer to styleName
 63      * @param {?odf.Formatting.StyleData} setProperties
 64      * @param {!string} styleName
 65      * @return {!Array.<!string>}
 66      */
 67     function getStyleReferencingAttributes(setProperties, styleName) {
 68         var attributes = [];
 69         /**
 70          * @param {string} attributeName
 71          */
 72         function check(attributeName) {
 73             if (setProperties[attributeName] === styleName) {
 74                 attributes.push(attributeName);
 75             }
 76         }
 77         if (setProperties) {
 78             ['style:parent-style-name', 'style:next-style-name'].forEach(check);
 79         }
 80         return attributes;
 81     }
 82     /**
 83      * @param {?odf.Formatting.StyleData} setProperties
 84      * @param {!string} deletedStyleName
 85      * @return {undefined}
 86      */
 87     function dropStyleReferencingAttributes(setProperties, deletedStyleName) {
 88         /**
 89          * @param {string} attributeName
 90          */
 91         function del(attributeName) {
 92             if (setProperties[attributeName] === deletedStyleName) {
 93                 delete setProperties[attributeName];
 94             }
 95         }
 96         if (setProperties) {
 97             ['style:parent-style-name', 'style:next-style-name'].forEach(del);
 98         }
 99     }
100 
101     /**
102      * Creates a deep copy of the opspec
103      * @param {!Object} opspec
104      * @return {!Object}
105      */
106     function cloneOpspec(opspec) {
107         var result = {};
108 
109         Object.keys(opspec).forEach(function (key) {
110             if (typeof opspec[key] === 'object') {
111                 result[key] = cloneOpspec(opspec[key]);
112             } else {
113                 result[key] = opspec[key];
114             }
115         });
116 
117         return result;
118     }
119 
120     /**
121      * @param {?Object.<string,*>} minorSetProperties
122      * @param {?{attributes:string}} minorRemovedProperties
123      * @param {?Object.<string,*>} majorSetProperties
124      * @param {?{attributes:string}} majorRemovedProperties
125      * @return {!{majorChanged:boolean,minorChanged:boolean}}
126      */
127     function dropOverruledAndUnneededAttributes(minorSetProperties, minorRemovedProperties, majorSetProperties, majorRemovedProperties) {
128         var i, name,
129             majorChanged = false, minorChanged = false,
130             removedPropertyNames,
131             /**@type{!Array.<string>}*/
132             majorRemovedPropertyNames = [];
133         if (majorRemovedProperties && majorRemovedProperties.attributes) {
134             majorRemovedPropertyNames = majorRemovedProperties.attributes.split(',');
135         }
136 
137         // iterate over all properties and see which get overwritten or deleted
138         // by the overruling, so they have to be dropped
139         if (minorSetProperties && (majorSetProperties || majorRemovedPropertyNames.length > 0)) {
140             Object.keys(minorSetProperties).forEach(function (key) {
141                 var value = minorSetProperties[key],
142                     overrulingPropertyValue;
143                 // TODO: support more than one level
144                 if (typeof value !== "object") {
145                     if (majorSetProperties) {
146                         overrulingPropertyValue = majorSetProperties[key];
147                     }
148                     if (overrulingPropertyValue !== undefined) {
149                         // drop overruled
150                         delete minorSetProperties[key];
151                         minorChanged = true;
152 
153                         // major sets to same value?
154                         if (overrulingPropertyValue === value) {
155                             // drop major as well
156                             delete majorSetProperties[key];
157                             majorChanged = true;
158                         }
159                     } else if (majorRemovedPropertyNames.indexOf(key) !== -1) {
160                         // drop overruled
161                         delete minorSetProperties[key];
162                         minorChanged = true;
163                     }
164                 }
165             });
166         }
167 
168         // iterate over all overruling removed properties and drop any duplicates from
169         // the removed property names
170         if (minorRemovedProperties && minorRemovedProperties.attributes && (majorSetProperties || majorRemovedPropertyNames.length > 0)) {
171             removedPropertyNames = minorRemovedProperties.attributes.split(',');
172             for (i = 0; i < removedPropertyNames.length; i += 1) {
173                 name = removedPropertyNames[i];
174                 if ((majorSetProperties && majorSetProperties[name] !== undefined) ||
175                         (majorRemovedPropertyNames && majorRemovedPropertyNames.indexOf(name) !== -1)) {
176                     // drop
177                     removedPropertyNames.splice(i, 1);
178                     i -= 1;
179                     minorChanged = true;
180                 }
181             }
182             // set back
183             if (removedPropertyNames.length > 0) {
184                 minorRemovedProperties.attributes = removedPropertyNames.join(',');
185             } else {
186                 delete minorRemovedProperties.attributes;
187             }
188         }
189 
190         return {
191             majorChanged: majorChanged,
192             minorChanged: minorChanged
193         };
194     }
195 
196     /**
197      * Estimates if there are any properties set in the given properties object.
198      * @param {!odf.Formatting.StyleData} properties
199      * @return {!boolean}
200      */
201     function hasProperties(properties) {
202         var /**@type{string}*/
203             key;
204 
205         for (key in properties) {
206             if (properties.hasOwnProperty(key)) {
207                 return true;
208             }
209         }
210         return false;
211     }
212 
213     /**
214      * Estimates if there are any properties set in the given properties object.
215      * @param {!{attributes:string}} properties
216      * @return {!boolean}
217      */
218     function hasRemovedProperties(properties) {
219         var /**@type{string}*/
220             key;
221 
222         for (key in properties) {
223             if (properties.hasOwnProperty(key)) {
224                 // handle empty 'attribute' as not existing
225                 if (key !== 'attributes' || properties.attributes.length > 0) {
226                     return true;
227                 }
228             }
229         }
230         return false;
231     }
232 
233     /**
234      * @param {?odf.Formatting.StyleData} minorSet
235      * @param {?Object.<string,{attributes:string}>} minorRem
236      * @param {?odf.Formatting.StyleData} majorSet
237      * @param {?Object.<string,{attributes:string}>} majorRem
238      * @param {!string} propertiesName
239      * @return {?{majorChanged:boolean,minorChanged:boolean}}
240      */
241     function dropOverruledAndUnneededProperties(minorSet, minorRem, majorSet, majorRem, propertiesName) {
242         var minorSP = /**@type{?odf.Formatting.StyleData}*/(minorSet ? minorSet[propertiesName] : null),
243             minorRP = minorRem ? minorRem[propertiesName] : null,
244             majorSP = /**@type{?odf.Formatting.StyleData}*/(majorSet ? majorSet[propertiesName] : null),
245             majorRP = majorRem ? majorRem[propertiesName] : null,
246             result;
247 
248         // TODO: also care for nested properties, like there can be e.g. with text:paragraph-properties
249         result = dropOverruledAndUnneededAttributes(minorSP, minorRP, majorSP, majorRP);
250 
251         // remove empty setProperties
252         if (minorSP && !hasProperties(minorSP)) {
253             delete minorSet[propertiesName];
254         }
255         // remove empty removedProperties
256         if (minorRP && !hasRemovedProperties(minorRP)) {
257             delete minorRem[propertiesName];
258         }
259 
260         // remove empty setProperties
261         if (majorSP && !hasProperties(majorSP)) {
262             delete majorSet[propertiesName];
263         }
264         // remove empty removedProperties
265         if (majorRP && !hasRemovedProperties(majorRP)) {
266             delete majorRem[propertiesName];
267         }
268 
269         return result;
270     }
271 
272 
273 
274     /* Transformation methods */
275 
276     /**
277      * @param {!ops.OpAddStyle.Spec} addStyleSpec
278      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpec
279      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
280      */
281     function transformAddStyleRemoveStyle(addStyleSpec, removeStyleSpec) {
282         var setAttributes,
283             helperOpspec,
284             addStyleSpecResult = [addStyleSpec],
285             removeStyleSpecResult = [removeStyleSpec];
286 
287         if (addStyleSpec.styleFamily === removeStyleSpec.styleFamily) {
288             // deleted style brought into use by addstyle op?
289             setAttributes = getStyleReferencingAttributes(addStyleSpec.setProperties, removeStyleSpec.styleName);
290             if (setAttributes.length > 0) {
291                 // just create a updateparagraph style op preceding to us which removes any set style from the paragraph
292                 helperOpspec = {
293                     optype: "UpdateParagraphStyle",
294                     memberid: removeStyleSpec.memberid,
295                     timestamp: removeStyleSpec.timestamp,
296                     styleName: addStyleSpec.styleName,
297                     removedProperties: { attributes: setAttributes.join(',') }
298                 };
299                 removeStyleSpecResult.unshift(helperOpspec);
300             }
301             // in the addstyle op drop any attributes referencing the style deleted
302             dropStyleReferencingAttributes(addStyleSpec.setProperties, removeStyleSpec.styleName);
303         }
304 
305         return {
306             opSpecsA:  addStyleSpecResult,
307             opSpecsB:  removeStyleSpecResult
308         };
309     }
310 
311     /**
312      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpecA
313      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpecB
314      * @param {!boolean} hasAPriority
315      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
316      */
317     function transformApplyDirectStylingApplyDirectStyling(applyDirectStylingSpecA, applyDirectStylingSpecB, hasAPriority) {
318         var majorSpec, minorSpec, majorSpecResult, minorSpecResult,
319             majorSpecEnd, minorSpecEnd, dropResult,
320             originalMajorSpec, originalMinorSpec,
321             helperOpspecBefore, helperOpspecAfter,
322             applyDirectStylingSpecAResult = [applyDirectStylingSpecA],
323             applyDirectStylingSpecBResult = [applyDirectStylingSpecB];
324 
325         // overlapping and any conflicting attributes?
326         if (!(applyDirectStylingSpecA.position + applyDirectStylingSpecA.length <= applyDirectStylingSpecB.position ||
327               applyDirectStylingSpecA.position >= applyDirectStylingSpecB.position + applyDirectStylingSpecB.length)) {
328             // adapt to priority
329             majorSpec = hasAPriority ? applyDirectStylingSpecA : applyDirectStylingSpecB;
330             minorSpec = hasAPriority ? applyDirectStylingSpecB : applyDirectStylingSpecA;
331 
332             // might need original opspecs?
333             if (applyDirectStylingSpecA.position !== applyDirectStylingSpecB.position ||
334                     applyDirectStylingSpecA.length !== applyDirectStylingSpecB.length) {
335                 originalMajorSpec = cloneOpspec(majorSpec);
336                 originalMinorSpec = cloneOpspec(minorSpec);
337             }
338 
339             // for the part that is overlapping reduce setProperties by the overruled properties
340             dropResult = dropOverruledAndUnneededProperties(
341                 minorSpec.setProperties,
342                 null,
343                 majorSpec.setProperties,
344                 null,
345                 'style:text-properties'
346             );
347 
348             if (dropResult.majorChanged || dropResult.minorChanged) {
349                 // split the less-priority op into several ops for the overlapping and non-overlapping ranges
350                 majorSpecResult = [];
351                 minorSpecResult = [];
352 
353                 majorSpecEnd = majorSpec.position + majorSpec.length;
354                 minorSpecEnd = minorSpec.position + minorSpec.length;
355 
356                 // find if there is a part before and if there is a part behind,
357                 // create range-adapted copies of the original opspec, if the spec has changed
358                 if (minorSpec.position < majorSpec.position) {
359                     if (dropResult.minorChanged) {
360                         helperOpspecBefore = cloneOpspec(/**@type{!Object}*/(originalMinorSpec));
361                         helperOpspecBefore.length = majorSpec.position - minorSpec.position;
362                         minorSpecResult.push(helperOpspecBefore);
363 
364                         minorSpec.position = majorSpec.position;
365                         minorSpec.length = minorSpecEnd - minorSpec.position;
366                     }
367                 } else if (majorSpec.position < minorSpec.position) {
368                     if (dropResult.majorChanged) {
369                         helperOpspecBefore = cloneOpspec(/**@type{!Object}*/(originalMajorSpec));
370                         helperOpspecBefore.length = minorSpec.position - majorSpec.position;
371                         majorSpecResult.push(helperOpspecBefore);
372 
373                         majorSpec.position = minorSpec.position;
374                         majorSpec.length = majorSpecEnd - majorSpec.position;
375                     }
376                 }
377                 if (minorSpecEnd > majorSpecEnd) {
378                     if (dropResult.minorChanged) {
379                         helperOpspecAfter = originalMinorSpec;
380                         helperOpspecAfter.position = majorSpecEnd;
381                         helperOpspecAfter.length = minorSpecEnd - majorSpecEnd;
382                         minorSpecResult.push(helperOpspecAfter);
383 
384                         minorSpec.length = majorSpecEnd - minorSpec.position;
385                     }
386                 } else if (majorSpecEnd > minorSpecEnd) {
387                     if (dropResult.majorChanged) {
388                         helperOpspecAfter = originalMajorSpec;
389                         helperOpspecAfter.position = minorSpecEnd;
390                         helperOpspecAfter.length = majorSpecEnd - minorSpecEnd;
391                         majorSpecResult.push(helperOpspecAfter);
392 
393                         majorSpec.length = minorSpecEnd - majorSpec.position;
394                     }
395                 }
396 
397                 // check if there are any changes left and this op has not become a noop
398                 if (majorSpec.setProperties && hasProperties(majorSpec.setProperties)) {
399                     majorSpecResult.push(majorSpec);
400                 }
401                 // check if there are any changes left and this op has not become a noop
402                 if (minorSpec.setProperties && hasProperties(minorSpec.setProperties)) {
403                     minorSpecResult.push(minorSpec);
404                 }
405 
406                 if (hasAPriority) {
407                     applyDirectStylingSpecAResult = majorSpecResult;
408                     applyDirectStylingSpecBResult = minorSpecResult;
409                 } else {
410                     applyDirectStylingSpecAResult = minorSpecResult;
411                     applyDirectStylingSpecBResult = majorSpecResult;
412                 }
413             }
414         }
415 
416         return {
417             opSpecsA:  applyDirectStylingSpecAResult,
418             opSpecsB:  applyDirectStylingSpecBResult
419         };
420     }
421 
422     /**
423      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpec
424      * @param {!ops.OpInsertText.Spec} insertTextSpec
425      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
426      */
427     function transformApplyDirectStylingInsertText(applyDirectStylingSpec, insertTextSpec) {
428         // adapt applyDirectStyling spec to inserted positions
429         if (insertTextSpec.position <= applyDirectStylingSpec.position) {
430             applyDirectStylingSpec.position += insertTextSpec.text.length;
431         } else if (insertTextSpec.position <= applyDirectStylingSpec.position + applyDirectStylingSpec.length) {
432             applyDirectStylingSpec.length += insertTextSpec.text.length;
433         }
434 
435         return {
436             opSpecsA:  [applyDirectStylingSpec],
437             opSpecsB:  [insertTextSpec]
438         };
439     }
440 
441     /**
442      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpec
443      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
444      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
445      */
446     function transformApplyDirectStylingMergeParagraph(applyDirectStylingSpec, mergeParagraphSpec) {
447         var pointA = applyDirectStylingSpec.position,
448             pointB = applyDirectStylingSpec.position + applyDirectStylingSpec.length;
449 
450         // adapt applyDirectStyling spec to merged paragraph
451         if (pointA >= mergeParagraphSpec.sourceStartPosition) {
452             pointA -= 1;
453         }
454         if (pointB >= mergeParagraphSpec.sourceStartPosition) {
455             pointB -= 1;
456         }
457         applyDirectStylingSpec.position = pointA;
458         applyDirectStylingSpec.length = pointB - pointA;
459 
460         return {
461             opSpecsA:  [applyDirectStylingSpec],
462             opSpecsB:  [mergeParagraphSpec]
463         };
464     }
465 
466     /**
467      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpec
468      * @param {!ops.OpRemoveText.Spec} removeTextSpec
469      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
470      */
471     function transformApplyDirectStylingRemoveText(applyDirectStylingSpec, removeTextSpec) {
472         var applyDirectStylingSpecEnd = applyDirectStylingSpec.position + applyDirectStylingSpec.length,
473             removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length,
474             applyDirectStylingSpecResult = [applyDirectStylingSpec],
475             removeTextSpecResult = [removeTextSpec];
476 
477         // transform applyDirectStylingSpec
478         // removed positions by object up to move cursor position?
479         if (removeTextSpecEnd <= applyDirectStylingSpec.position) {
480             // adapt by removed position
481             applyDirectStylingSpec.position -= removeTextSpec.length;
482         // overlapping?
483         } else if (removeTextSpec.position < applyDirectStylingSpecEnd) {
484             // still to select range starting at cursor position?
485             if (applyDirectStylingSpec.position < removeTextSpec.position) {
486                 // still to select range ending at selection?
487                 if (removeTextSpecEnd < applyDirectStylingSpecEnd) {
488                     applyDirectStylingSpec.length -= removeTextSpec.length;
489                 } else {
490                     applyDirectStylingSpec.length = removeTextSpec.position - applyDirectStylingSpec.position;
491                 }
492             // remove overlapping section
493             } else {
494                 // fall at start of removed section
495                 applyDirectStylingSpec.position = removeTextSpec.position;
496                 // still to select range at selection end?
497                 if (removeTextSpecEnd < applyDirectStylingSpecEnd) {
498                     applyDirectStylingSpec.length = applyDirectStylingSpecEnd - removeTextSpecEnd;
499                 } else {
500                     // completely overlapped by other, so becomes no-op
501                     // TODO: once we can address spans, removeTextSpec would need to get a helper op
502                     // to remove the empty span left over
503                     applyDirectStylingSpecResult = [];
504                 }
505             }
506         }
507 
508         return {
509             opSpecsA:  applyDirectStylingSpecResult,
510             opSpecsB:  removeTextSpecResult
511         };
512     }
513 
514     /**
515      * @param {!ops.OpApplyDirectStyling.Spec} applyDirectStylingSpec
516      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
517      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
518      */
519     function transformApplyDirectStylingSplitParagraph(applyDirectStylingSpec, splitParagraphSpec) {
520         // transform applyDirectStylingSpec
521         if (splitParagraphSpec.position < applyDirectStylingSpec.position) {
522             applyDirectStylingSpec.position += 1;
523         } else if (splitParagraphSpec.position < applyDirectStylingSpec.position + applyDirectStylingSpec.length) {
524             applyDirectStylingSpec.length += 1;
525         }
526 
527         return {
528             opSpecsA:  [applyDirectStylingSpec],
529             opSpecsB:  [splitParagraphSpec]
530         };
531     }
532 
533     /**
534      * @param {!ops.OpInsertText.Spec} insertTextSpecA
535      * @param {!ops.OpInsertText.Spec} insertTextSpecB
536      * @param {!boolean} hasAPriority
537      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
538      */
539     function transformInsertTextInsertText(insertTextSpecA, insertTextSpecB, hasAPriority) {
540         if (insertTextSpecA.position < insertTextSpecB.position) {
541             insertTextSpecB.position += insertTextSpecA.text.length;
542         } else if (insertTextSpecA.position > insertTextSpecB.position) {
543             insertTextSpecA.position += insertTextSpecB.text.length;
544         } else {
545             if (hasAPriority) {
546                 insertTextSpecB.position += insertTextSpecA.text.length;
547             } else {
548                 insertTextSpecA.position += insertTextSpecB.text.length;
549             }
550         }
551 
552         return {
553             opSpecsA:  [insertTextSpecA],
554             opSpecsB:  [insertTextSpecB]
555         };
556     }
557 
558     /**
559      * @param {!ops.OpInsertText.Spec} insertTextSpec
560      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
561      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
562      */
563     function transformInsertTextMergeParagraph(insertTextSpec, mergeParagraphSpec) {
564         if (insertTextSpec.position >= mergeParagraphSpec.sourceStartPosition) {
565             insertTextSpec.position -= 1;
566         } else {
567             if (insertTextSpec.position < mergeParagraphSpec.sourceStartPosition) {
568                 mergeParagraphSpec.sourceStartPosition += insertTextSpec.text.length;
569             }
570             if (insertTextSpec.position < mergeParagraphSpec.destinationStartPosition) {
571                 mergeParagraphSpec.destinationStartPosition += insertTextSpec.text.length;
572             }
573         }
574 
575         return {
576             opSpecsA:  [insertTextSpec],
577             opSpecsB:  [mergeParagraphSpec]
578         };
579     }
580 
581     /**
582      * @param {!ops.OpInsertText.Spec} insertTextSpec
583      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
584      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
585      */
586     function transformInsertTextMoveCursor(insertTextSpec, moveCursorSpec) {
587         var isMoveCursorSpecRangeInverted = invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec);
588 
589         // adapt movecursor spec to inserted positions
590         if (insertTextSpec.position < moveCursorSpec.position) {
591             moveCursorSpec.position += insertTextSpec.text.length;
592         } else if (insertTextSpec.position < moveCursorSpec.position + moveCursorSpec.length) {
593             moveCursorSpec.length += insertTextSpec.text.length;
594         }
595 
596         if (isMoveCursorSpecRangeInverted) {
597             invertMoveCursorSpecRange(moveCursorSpec);
598         }
599 
600         return {
601             opSpecsA:  [insertTextSpec],
602             opSpecsB:  [moveCursorSpec]
603         };
604     }
605 
606     /**
607      * @param {!ops.OpInsertText.Spec} insertTextSpec
608      * @param {!ops.OpRemoveText.Spec} removeTextSpec
609      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
610      */
611     function transformInsertTextRemoveText(insertTextSpec, removeTextSpec) {
612         var helperOpspec,
613             removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length,
614             insertTextSpecResult = [insertTextSpec],
615             removeTextSpecResult = [removeTextSpec];
616 
617         // update insertTextSpec
618         // removed before/up to insertion point?
619         if (removeTextSpecEnd <= insertTextSpec.position) {
620             insertTextSpec.position -= removeTextSpec.length;
621         // removed at/behind insertion point
622         } else if (insertTextSpec.position <= removeTextSpec.position) {
623             removeTextSpec.position += insertTextSpec.text.length;
624         // insertion in middle of removed range
625         } else {
626             // we have to split the removal into two ops, before and after the insertion point
627             removeTextSpec.length = insertTextSpec.position - removeTextSpec.position;
628             helperOpspec = {
629                 optype: "RemoveText",
630                 memberid: removeTextSpec.memberid,
631                 timestamp: removeTextSpec.timestamp,
632                 position: insertTextSpec.position + insertTextSpec.text.length,
633                 length: removeTextSpecEnd - insertTextSpec.position
634             };
635             removeTextSpecResult.unshift(helperOpspec); // helperOp first, so its position is not affected by the real op
636             // drop insertion point to begin of removed range
637             // original insertTextSpec.position is used for removeTextSpec changes, so only change now
638             insertTextSpec.position = removeTextSpec.position;
639         }
640 
641         return {
642             opSpecsA:  insertTextSpecResult,
643             opSpecsB:  removeTextSpecResult
644         };
645     }
646 
647     /**
648      * @param {!ops.OpInsertText.Spec} insertTextSpec
649      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
650      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
651      */
652     function transformInsertTextSetParagraphStyle(insertTextSpec, setParagraphStyleSpec) {
653         if (setParagraphStyleSpec.position > insertTextSpec.position) {
654             setParagraphStyleSpec.position += insertTextSpec.text.length;
655         }
656 
657         return {
658             opSpecsA:  [insertTextSpec],
659             opSpecsB:  [setParagraphStyleSpec]
660         };
661     }
662 
663     /**
664      * @param {!ops.OpInsertText.Spec} insertTextSpec
665      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
666      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
667      */
668     function transformInsertTextSplitParagraph(insertTextSpec, splitParagraphSpec) {
669         if (insertTextSpec.position < splitParagraphSpec.sourceParagraphPosition) {
670             splitParagraphSpec.sourceParagraphPosition += insertTextSpec.text.length;
671         }
672 
673         if (insertTextSpec.position <= splitParagraphSpec.position) {
674             splitParagraphSpec.position += insertTextSpec.text.length;
675         } else {
676             insertTextSpec.position += 1;
677         }
678 
679         return {
680             opSpecsA:  [insertTextSpec],
681             opSpecsB:  [splitParagraphSpec]
682         };
683     }
684 
685     /**
686      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpecA
687      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpecB
688      * @param {!boolean} hasAPriority
689      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
690      */
691     function transformMergeParagraphMergeParagraph(mergeParagraphSpecA, mergeParagraphSpecB, hasAPriority) {
692         var specsForB = [mergeParagraphSpecA],
693             specsForA = [mergeParagraphSpecB],
694             priorityOp,
695             styleParagraphFixup,
696             moveCursorA,
697             moveCursorB;
698 
699         if (mergeParagraphSpecA.destinationStartPosition === mergeParagraphSpecB.destinationStartPosition) {
700             // Two merge commands for the same paragraph result in a noop to both sides, as the same
701             // paragraph can only be merged once.
702             specsForB = [];
703             specsForA = [];
704             // If the moveCursor flag is set, the cursor will still need to be adjusted to the right location
705             if (mergeParagraphSpecA.moveCursor) {
706                 moveCursorA = /**@type{!ops.OpMoveCursor.Spec}*/({
707                     optype: "MoveCursor",
708                     memberid: mergeParagraphSpecA.memberid,
709                     timestamp: mergeParagraphSpecA.timestamp,
710                     position: mergeParagraphSpecA.sourceStartPosition - 1
711                 });
712                 specsForB.push(moveCursorA);
713             }
714             if (mergeParagraphSpecB.moveCursor) {
715                 moveCursorB = /**@type{!ops.OpMoveCursor.Spec}*/({
716                     optype: "MoveCursor",
717                     memberid: mergeParagraphSpecB.memberid,
718                     timestamp: mergeParagraphSpecB.timestamp,
719                     position: mergeParagraphSpecB.sourceStartPosition - 1
720                 });
721                 specsForA.push(moveCursorB);
722             }
723 
724             // Determine which merge style wins
725             priorityOp = hasAPriority ? mergeParagraphSpecA : mergeParagraphSpecB;
726             styleParagraphFixup = /**@type{!ops.OpSetParagraphStyle.Spec}*/({
727                 optype: "SetParagraphStyle",
728                 memberid: priorityOp.memberid,
729                 timestamp: priorityOp.timestamp,
730                 position: priorityOp.destinationStartPosition,
731                 styleName: priorityOp.paragraphStyleName
732             });
733             if (hasAPriority) {
734                 specsForB.push(styleParagraphFixup);
735             } else {
736                 specsForA.push(styleParagraphFixup);
737             }
738         } else if (mergeParagraphSpecB.sourceStartPosition === mergeParagraphSpecA.destinationStartPosition) {
739             // Two consecutive paragraphs are being merged. E.g., A <- B <- C.
740             // Use the styleName of the lowest destination paragraph to set the paragraph style (A <- B)
741             mergeParagraphSpecA.destinationStartPosition = mergeParagraphSpecB.destinationStartPosition;
742             mergeParagraphSpecA.sourceStartPosition -= 1;
743             mergeParagraphSpecA.paragraphStyleName = mergeParagraphSpecB.paragraphStyleName;
744         } else if (mergeParagraphSpecA.sourceStartPosition === mergeParagraphSpecB.destinationStartPosition) {
745             // Two consecutive paragraphs are being merged. E.g., A <- B <- C.
746             // Use the styleName of the lowest destination paragraph to set the paragraph style (A <- B)
747             mergeParagraphSpecB.destinationStartPosition = mergeParagraphSpecA.destinationStartPosition;
748             mergeParagraphSpecB.sourceStartPosition -= 1;
749             mergeParagraphSpecB.paragraphStyleName = mergeParagraphSpecA.paragraphStyleName;
750         } else if (mergeParagraphSpecA.destinationStartPosition < mergeParagraphSpecB.destinationStartPosition) {
751             mergeParagraphSpecB.destinationStartPosition -= 1;
752             mergeParagraphSpecB.sourceStartPosition -= 1;
753         } else { // mergeParagraphSpecB.destinationStartPosition < mergeParagraphSpecA.destinationStartPosition
754             mergeParagraphSpecA.destinationStartPosition -= 1;
755             mergeParagraphSpecA.sourceStartPosition -= 1;
756         }
757 
758         return {
759             opSpecsA:  specsForB,
760             opSpecsB:  specsForA
761         };
762     }
763 
764     /**
765      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
766      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
767      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
768      */
769     function transformMergeParagraphMoveCursor(mergeParagraphSpec, moveCursorSpec) {
770         var pointA = moveCursorSpec.position,
771             pointB = moveCursorSpec.position + moveCursorSpec.length,
772             start = Math.min(pointA, pointB),
773             end = Math.max(pointA, pointB);
774 
775         if (start >= mergeParagraphSpec.sourceStartPosition) {
776             start -= 1;
777         }
778         if (end >= mergeParagraphSpec.sourceStartPosition) {
779             end -= 1;
780         }
781 
782         // When updating the cursor spec, ensure the selection direction is preserved.
783         // If the length was previously positive, it should remain positive.
784         if (moveCursorSpec.length >= 0) {
785             moveCursorSpec.position = start;
786             moveCursorSpec.length = end - start;
787         } else {
788             moveCursorSpec.position = end;
789             moveCursorSpec.length = start - end;
790         }
791 
792         return {
793             opSpecsA:  [mergeParagraphSpec],
794             opSpecsB:  [moveCursorSpec]
795         };
796     }
797 
798     /**
799      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
800      * @param {!ops.OpRemoveText.Spec} removeTextSpec
801      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
802      */
803     function transformMergeParagraphRemoveText(mergeParagraphSpec, removeTextSpec) {
804         // RemoveText ops can't cross paragraph boundaries, so only the position needs to be checked
805         if (removeTextSpec.position >= mergeParagraphSpec.sourceStartPosition) {
806             removeTextSpec.position -= 1;
807         } else {
808             if (removeTextSpec.position < mergeParagraphSpec.destinationStartPosition) {
809                 mergeParagraphSpec.destinationStartPosition -= removeTextSpec.length;
810             }
811             if (removeTextSpec.position < mergeParagraphSpec.sourceStartPosition) {
812                 mergeParagraphSpec.sourceStartPosition -= removeTextSpec.length;
813             }
814         }
815 
816         return {
817             opSpecsA:  [mergeParagraphSpec],
818             opSpecsB:  [removeTextSpec]
819         };
820     }
821 
822     /**
823      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
824      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
825      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
826      */
827     function transformMergeParagraphSetParagraphStyle(mergeParagraphSpec, setParagraphStyleSpec) {
828         var opSpecsA = [mergeParagraphSpec],
829             opSpecsB = [setParagraphStyleSpec];
830 
831         // SetParagraphStyle ops can't cross paragraph boundaries
832         if (setParagraphStyleSpec.position > mergeParagraphSpec.sourceStartPosition) {
833             // Paragraph beyond the ones region affected by the merge
834             setParagraphStyleSpec.position -= 1;
835         } else if (setParagraphStyleSpec.position === mergeParagraphSpec.destinationStartPosition
836                     || setParagraphStyleSpec.position === mergeParagraphSpec.sourceStartPosition) {
837             // Attempting to style a merging paragraph
838             setParagraphStyleSpec.position = mergeParagraphSpec.destinationStartPosition;
839             mergeParagraphSpec.paragraphStyleName = setParagraphStyleSpec.styleName;
840         }
841 
842         return {
843             opSpecsA:  opSpecsA,
844             opSpecsB:  opSpecsB
845         };
846     }
847 
848     /**
849      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
850      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
851      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
852      */
853     function transformMergeParagraphSplitParagraph(mergeParagraphSpec, splitParagraphSpec) {
854         var styleSplitParagraph,
855             moveCursorOp,
856             opSpecsA = [mergeParagraphSpec],
857             opSpecsB = [splitParagraphSpec];
858 
859         if (splitParagraphSpec.position < mergeParagraphSpec.destinationStartPosition) {
860             // Split occurs before the merge destination
861             // Splitting a paragraph inserts one step, moving the merge along
862             mergeParagraphSpec.destinationStartPosition += 1;
863             mergeParagraphSpec.sourceStartPosition += 1;
864         } else if (splitParagraphSpec.position >= mergeParagraphSpec.destinationStartPosition
865             && splitParagraphSpec.position < mergeParagraphSpec.sourceStartPosition) {
866             // split occurs within the paragraphs being merged
867             splitParagraphSpec.paragraphStyleName = mergeParagraphSpec.paragraphStyleName;
868             styleSplitParagraph = /**@type{!ops.OpSetParagraphStyle.Spec}*/({
869                 optype: "SetParagraphStyle",
870                 memberid: mergeParagraphSpec.memberid,
871                 timestamp: mergeParagraphSpec.timestamp,
872                 position: mergeParagraphSpec.destinationStartPosition,
873                 styleName: mergeParagraphSpec.paragraphStyleName
874             });
875             opSpecsA.push(styleSplitParagraph);
876             if (splitParagraphSpec.position === mergeParagraphSpec.sourceStartPosition - 1
877                     && mergeParagraphSpec.moveCursor) {
878                 // OdtDocument.getTextNodeAtStep + Spec.moveCursor make it very difficult to control cursor placement
879                 // When a split + merge combines, there is a tricky situation because the split will leave other cursors
880                 // on the last step in the new paragraph.
881                 // When the merge is relocated to attach to the front of the newly inserted paragraph below, the cursor
882                 // will end up at the start of the new paragraph. Workaround this by manually setting the cursor back
883                 // to the appropriate location after the merge completes
884                 moveCursorOp = /**@type{!ops.OpMoveCursor.Spec}*/({
885                     optype: "MoveCursor",
886                     memberid: mergeParagraphSpec.memberid,
887                     timestamp: mergeParagraphSpec.timestamp,
888                     position: splitParagraphSpec.position,
889                     length: 0
890                 });
891                 opSpecsA.push(moveCursorOp);
892             }
893 
894             // SplitParagraph ops effectively create new paragraph boundaries. The user intent
895             // is for the source paragraph to be joined to the END of the dest paragraph. If the
896             // split occurs in the dest paragraph, the source should be joined to the newly created
897             // paragraph instead
898             mergeParagraphSpec.destinationStartPosition = splitParagraphSpec.position + 1;
899             mergeParagraphSpec.sourceStartPosition += 1;
900         } else if (splitParagraphSpec.position >= mergeParagraphSpec.sourceStartPosition) {
901             // Split occurs after the merge source
902             // Merging paragraphs remove one step
903             splitParagraphSpec.position -= 1;
904             splitParagraphSpec.sourceParagraphPosition -= 1;
905         }
906 
907         return {
908             opSpecsA:  opSpecsA,
909             opSpecsB:  opSpecsB
910         };
911     }
912 
913     /**
914      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpecA
915      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpecB
916      * @param {!boolean} hasAPriority
917      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
918      */
919     function transformUpdateParagraphStyleUpdateParagraphStyle(updateParagraphStyleSpecA, updateParagraphStyleSpecB, hasAPriority) {
920         var majorSpec, minorSpec,
921             updateParagraphStyleSpecAResult = [updateParagraphStyleSpecA],
922             updateParagraphStyleSpecBResult = [updateParagraphStyleSpecB];
923 
924         // same style updated by other op?
925         if (updateParagraphStyleSpecA.styleName === updateParagraphStyleSpecB.styleName) {
926             majorSpec = hasAPriority ? updateParagraphStyleSpecA : updateParagraphStyleSpecB;
927             minorSpec = hasAPriority ? updateParagraphStyleSpecB : updateParagraphStyleSpecA;
928 
929             // any properties which are set by other update op need to be dropped
930             dropOverruledAndUnneededProperties(minorSpec.setProperties,
931                 minorSpec.removedProperties, majorSpec.setProperties,
932                 majorSpec.removedProperties, 'style:paragraph-properties');
933             dropOverruledAndUnneededProperties(minorSpec.setProperties,
934                 minorSpec.removedProperties, majorSpec.setProperties,
935                 majorSpec.removedProperties, 'style:text-properties');
936             dropOverruledAndUnneededAttributes(minorSpec.setProperties || null,
937                 /**@type{{attributes: string}}*/(minorSpec.removedProperties) || null,
938                 majorSpec.setProperties || null,
939                 /**@type{{attributes: string}}*/(majorSpec.removedProperties) || null);
940 
941             // check if there are any changes left and the major op has not become a noop
942             if (!(majorSpec.setProperties && hasProperties(majorSpec.setProperties)) &&
943                     !(majorSpec.removedProperties && hasRemovedProperties(majorSpec.removedProperties))) {
944                 // set major spec to noop
945                 if (hasAPriority) {
946                     updateParagraphStyleSpecAResult = [];
947                 } else {
948                     updateParagraphStyleSpecBResult = [];
949                 }
950             }
951             // check if there are any changes left and the minor op has not become a noop
952             if (!(minorSpec.setProperties && hasProperties(minorSpec.setProperties)) &&
953                     !(minorSpec.removedProperties && hasRemovedProperties(minorSpec.removedProperties))) {
954                 // set minor spec to noop 
955                 if (hasAPriority) {
956                     updateParagraphStyleSpecBResult = [];
957                 } else {
958                     updateParagraphStyleSpecAResult = [];
959                 }
960             }
961         }
962 
963         return {
964             opSpecsA:  updateParagraphStyleSpecAResult,
965             opSpecsB:  updateParagraphStyleSpecBResult
966         };
967     }
968 
969     /**
970      * @param {!ops.OpUpdateMetadata.Spec} updateMetadataSpecA
971      * @param {!ops.OpUpdateMetadata.Spec} updateMetadataSpecB
972      * @param {!boolean} hasAPriority
973      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
974      */
975     function transformUpdateMetadataUpdateMetadata(updateMetadataSpecA, updateMetadataSpecB, hasAPriority) {
976         var majorSpec, minorSpec,
977             updateMetadataSpecAResult = [updateMetadataSpecA],
978             updateMetadataSpecBResult = [updateMetadataSpecB];
979 
980         majorSpec = hasAPriority ? updateMetadataSpecA : updateMetadataSpecB;
981         minorSpec = hasAPriority ? updateMetadataSpecB : updateMetadataSpecA;
982 
983         // any properties which are set by other update op need to be dropped
984         dropOverruledAndUnneededAttributes(minorSpec.setProperties || null,
985                             minorSpec.removedProperties || null,
986                             majorSpec.setProperties || null,
987                             majorSpec.removedProperties || null);
988 
989         // check if there are any changes left and the major op has not become a noop
990         if (!(majorSpec.setProperties && hasProperties(majorSpec.setProperties)) &&
991                 !(majorSpec.removedProperties && hasRemovedProperties(majorSpec.removedProperties))) {
992             // set major spec to noop
993             if (hasAPriority) {
994                 updateMetadataSpecAResult = [];
995             } else {
996                 updateMetadataSpecBResult = [];
997             }
998         }
999         // check if there are any changes left and the minor op has not become a noop
1000         if (!(minorSpec.setProperties && hasProperties(minorSpec.setProperties)) &&
1001                 !(minorSpec.removedProperties && hasRemovedProperties(minorSpec.removedProperties))) {
1002             // set minor spec to noop 
1003             if (hasAPriority) {
1004                 updateMetadataSpecBResult = [];
1005             } else {
1006                 updateMetadataSpecAResult = [];
1007             }
1008         }
1009 
1010         return {
1011             opSpecsA:  updateMetadataSpecAResult,
1012             opSpecsB:  updateMetadataSpecBResult
1013         };
1014     }
1015 
1016     /**
1017      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpecA
1018      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpecB
1019      * @param {!boolean} hasAPriority
1020      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1021      */
1022     function transformSetParagraphStyleSetParagraphStyle(setParagraphStyleSpecA, setParagraphStyleSpecB, hasAPriority) {
1023         if (setParagraphStyleSpecA.position === setParagraphStyleSpecB.position) {
1024             if (hasAPriority) {
1025                 setParagraphStyleSpecB.styleName = setParagraphStyleSpecA.styleName;
1026             } else {
1027                 setParagraphStyleSpecA.styleName = setParagraphStyleSpecB.styleName;
1028             }
1029         }
1030 
1031         return {
1032             opSpecsA:  [setParagraphStyleSpecA],
1033             opSpecsB:  [setParagraphStyleSpecB]
1034         };
1035     }
1036 
1037     /**
1038      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1039      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1040      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1041      */
1042     function transformSetParagraphStyleSplitParagraph(setParagraphStyleSpec, splitParagraphSpec) {
1043         var opSpecsA = [setParagraphStyleSpec],
1044             opSpecsB = [splitParagraphSpec],
1045             setParagraphClone;
1046 
1047         if (setParagraphStyleSpec.position > splitParagraphSpec.position) {
1048             setParagraphStyleSpec.position += 1;
1049         } else if (setParagraphStyleSpec.position === splitParagraphSpec.sourceParagraphPosition) {
1050             // When a set paragraph style & split conflict, the set paragraph style always wins
1051 
1052             splitParagraphSpec.paragraphStyleName = setParagraphStyleSpec.styleName;
1053             // The new paragraph that resulted from the already executed split op should be styled with
1054             // the original paragraph style.
1055             setParagraphClone = cloneOpspec(setParagraphStyleSpec);
1056             // A split paragraph op introduces a new paragraph boundary just passed the point where the split occurs
1057             setParagraphClone.position = splitParagraphSpec.position + 1;
1058             opSpecsA.push(setParagraphClone);
1059         }
1060 
1061         return {
1062             opSpecsA:  opSpecsA,
1063             opSpecsB:  opSpecsB
1064         };
1065     }
1066 
1067     /**
1068      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpecA
1069      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpecB
1070      * @param {!boolean} hasAPriority
1071      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1072      */
1073     function transformSplitParagraphSplitParagraph(splitParagraphSpecA, splitParagraphSpecB, hasAPriority) {
1074         var specABeforeB,
1075             specBBeforeA;
1076 
1077         if (splitParagraphSpecA.position < splitParagraphSpecB.position) {
1078             specABeforeB =  true;
1079         } else if (splitParagraphSpecB.position < splitParagraphSpecA.position) {
1080             specBBeforeA = true;
1081         } else if (splitParagraphSpecA.position === splitParagraphSpecB.position) {
1082             if (hasAPriority) {
1083                 specABeforeB =  true;
1084             } else {
1085                 specBBeforeA = true;
1086             }
1087         }
1088 
1089         if (specABeforeB) {
1090             splitParagraphSpecB.position += 1;
1091             if (splitParagraphSpecA.position < splitParagraphSpecB.sourceParagraphPosition) {
1092                 splitParagraphSpecB.sourceParagraphPosition += 1;
1093             } else {
1094                 // Split occurs between specB's split position & it's source paragraph position
1095                 // This means specA introduces a NEW paragraph boundary
1096                 splitParagraphSpecB.sourceParagraphPosition = splitParagraphSpecA.position + 1;
1097             }
1098         } else if (specBBeforeA) {
1099             splitParagraphSpecA.position += 1;
1100             if (splitParagraphSpecB.position < splitParagraphSpecB.sourceParagraphPosition) {
1101                 splitParagraphSpecA.sourceParagraphPosition += 1;
1102             } else {
1103                 // Split occurs between specA's split position & it's source paragraph position
1104                 // This means specB introduces a NEW paragraph boundary
1105                 splitParagraphSpecA.sourceParagraphPosition = splitParagraphSpecB.position + 1;
1106             }
1107         }
1108 
1109         return {
1110             opSpecsA:  [splitParagraphSpecA],
1111             opSpecsB:  [splitParagraphSpecB]
1112         };
1113     }
1114 
1115     /**
1116      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1117      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpec
1118      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1119      */
1120     function transformMoveCursorRemoveCursor(moveCursorSpec, removeCursorSpec) {
1121         var isSameCursorRemoved = (moveCursorSpec.memberid === removeCursorSpec.memberid);
1122 
1123         return {
1124             opSpecsA:  isSameCursorRemoved ? [] : [moveCursorSpec],
1125             opSpecsB:  [removeCursorSpec]
1126         };
1127     }
1128 
1129     /**
1130      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1131      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1132      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1133      */
1134     function transformMoveCursorRemoveText(moveCursorSpec, removeTextSpec) {
1135         var isMoveCursorSpecRangeInverted = invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec),
1136             moveCursorSpecEnd = moveCursorSpec.position + moveCursorSpec.length,
1137             removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length;
1138 
1139         // transform moveCursorSpec
1140         // removed positions by object up to move cursor position?
1141         if (removeTextSpecEnd <= moveCursorSpec.position) {
1142             // adapt by removed position
1143             moveCursorSpec.position -= removeTextSpec.length;
1144         // overlapping?
1145         } else if (removeTextSpec.position < moveCursorSpecEnd) {
1146             // still to select range starting at cursor position?
1147             if (moveCursorSpec.position < removeTextSpec.position) {
1148                 // still to select range ending at selection?
1149                 if (removeTextSpecEnd < moveCursorSpecEnd) {
1150                     moveCursorSpec.length -= removeTextSpec.length;
1151                 } else {
1152                     moveCursorSpec.length = removeTextSpec.position - moveCursorSpec.position;
1153                 }
1154             // remove overlapping section
1155             } else {
1156                 // fall at start of removed section
1157                 moveCursorSpec.position = removeTextSpec.position;
1158                 // still to select range at selection end?
1159                 if (removeTextSpecEnd < moveCursorSpecEnd) {
1160                     moveCursorSpec.length = moveCursorSpecEnd - removeTextSpecEnd;
1161                 } else {
1162                     // completely overlapped by other, so selection gets void
1163                     moveCursorSpec.length = 0;
1164                 }
1165             }
1166         }
1167 
1168         if (isMoveCursorSpecRangeInverted) {
1169             invertMoveCursorSpecRange(moveCursorSpec);
1170         }
1171 
1172         return {
1173             opSpecsA:  [moveCursorSpec],
1174             opSpecsB:  [removeTextSpec]
1175         };
1176     }
1177 
1178     /**
1179      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1180      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1181      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1182      */
1183     function transformMoveCursorSplitParagraph(moveCursorSpec, splitParagraphSpec) {
1184         var isMoveCursorSpecRangeInverted = invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec);
1185 
1186         // transform moveCursorSpec
1187         if (splitParagraphSpec.position < moveCursorSpec.position) {
1188             moveCursorSpec.position += 1;
1189         } else if (splitParagraphSpec.position < moveCursorSpec.position + moveCursorSpec.length) {
1190             moveCursorSpec.length += 1;
1191         }
1192 
1193         if (isMoveCursorSpecRangeInverted) {
1194             invertMoveCursorSpecRange(moveCursorSpec);
1195         }
1196 
1197         return {
1198             opSpecsA:  [moveCursorSpec],
1199             opSpecsB:  [splitParagraphSpec]
1200         };
1201     }
1202 
1203     /**
1204      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpecA
1205      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpecB
1206      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1207      */
1208     function transformRemoveCursorRemoveCursor(removeCursorSpecA, removeCursorSpecB) {
1209         var isSameMemberid = (removeCursorSpecA.memberid === removeCursorSpecB.memberid);
1210 
1211         // if both are removing the same cursor, their transformed counter-ops become noops
1212         return {
1213             opSpecsA:  isSameMemberid ? [] : [removeCursorSpecA],
1214             opSpecsB:  isSameMemberid ? [] : [removeCursorSpecB]
1215         };
1216     }
1217 
1218     /**
1219      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpecA
1220      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpecB
1221      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1222      */
1223     function transformRemoveStyleRemoveStyle(removeStyleSpecA, removeStyleSpecB) {
1224         var isSameStyle = (removeStyleSpecA.styleName === removeStyleSpecB.styleName && removeStyleSpecA.styleFamily === removeStyleSpecB.styleFamily);
1225 
1226         // if both are removing the same style, their transformed counter-ops become noops
1227         return {
1228             opSpecsA:  isSameStyle ? [] : [removeStyleSpecA],
1229             opSpecsB:  isSameStyle ? [] : [removeStyleSpecB]
1230         };
1231     }
1232 
1233     /**
1234      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpec
1235      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1236      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1237      */
1238     function transformRemoveStyleSetParagraphStyle(removeStyleSpec, setParagraphStyleSpec) {
1239         var helperOpspec,
1240             removeStyleSpecResult = [removeStyleSpec],
1241             setParagraphStyleSpecResult = [setParagraphStyleSpec];
1242 
1243         if (removeStyleSpec.styleFamily === "paragraph" && removeStyleSpec.styleName === setParagraphStyleSpec.styleName) {
1244             // transform removeStyleSpec
1245             // just create a setstyle op preceding to us which removes any set style from the paragraph
1246             helperOpspec = {
1247                 optype: "SetParagraphStyle",
1248                 memberid: removeStyleSpec.memberid,
1249                 timestamp: removeStyleSpec.timestamp,
1250                 position: setParagraphStyleSpec.position,
1251                 styleName: ""
1252             };
1253             removeStyleSpecResult.unshift(helperOpspec);
1254 
1255             // transform setParagraphStyleSpec
1256             // instead of setting now remove any existing style from the paragraph
1257             setParagraphStyleSpec.styleName = "";
1258         }
1259 
1260         return {
1261             opSpecsA:  removeStyleSpecResult,
1262             opSpecsB:  setParagraphStyleSpecResult
1263         };
1264     }
1265 
1266     /**
1267      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpec
1268      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpec
1269      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1270      */
1271     function transformRemoveStyleUpdateParagraphStyle(removeStyleSpec, updateParagraphStyleSpec) {
1272         var setAttributes, helperOpspec,
1273             removeStyleSpecResult = [removeStyleSpec],
1274             updateParagraphStyleSpecResult = [updateParagraphStyleSpec];
1275 
1276         if (removeStyleSpec.styleFamily === "paragraph") {
1277             // transform removeStyleSpec
1278             // style brought into use by other op?
1279             setAttributes = getStyleReferencingAttributes(updateParagraphStyleSpec.setProperties, removeStyleSpec.styleName);
1280             if (setAttributes.length > 0) {
1281                 // just create a updateparagraph style op preceding to us which removes any set style from the paragraph
1282                 helperOpspec = {
1283                     optype: "UpdateParagraphStyle",
1284                     memberid: removeStyleSpec.memberid,
1285                     timestamp: removeStyleSpec.timestamp,
1286                     styleName: updateParagraphStyleSpec.styleName,
1287                     removedProperties: { attributes: setAttributes.join(',') }
1288                 };
1289                 removeStyleSpecResult.unshift(helperOpspec);
1290             }
1291 
1292             // transform updateParagraphStyleSpec
1293             // target style to update deleted by removeStyle?
1294             if (removeStyleSpec.styleName === updateParagraphStyleSpec.styleName) {
1295                 // don't touch the dead
1296                 updateParagraphStyleSpecResult = [];
1297             } else {
1298                 // otherwise drop any attributes referencing the style deleted
1299                 dropStyleReferencingAttributes(updateParagraphStyleSpec.setProperties, removeStyleSpec.styleName);
1300             }
1301         }
1302 
1303         return {
1304             opSpecsA:  removeStyleSpecResult,
1305             opSpecsB:  updateParagraphStyleSpecResult
1306         };
1307     }
1308 
1309     /**
1310      * @param {!ops.OpRemoveText.Spec} removeTextSpecA
1311      * @param {!ops.OpRemoveText.Spec} removeTextSpecB
1312      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1313      */
1314     function transformRemoveTextRemoveText(removeTextSpecA, removeTextSpecB) {
1315         var removeTextSpecAEnd = removeTextSpecA.position + removeTextSpecA.length,
1316             removeTextSpecBEnd = removeTextSpecB.position + removeTextSpecB.length,
1317             removeTextSpecAResult = [removeTextSpecA],
1318             removeTextSpecBResult = [removeTextSpecB];
1319 
1320         // B removed positions by object up to As start position?
1321         if (removeTextSpecBEnd <= removeTextSpecA.position) {
1322             // adapt A by removed position
1323             removeTextSpecA.position -= removeTextSpecB.length;
1324         // A removed positions by object up to Bs start position?
1325         } else if (removeTextSpecAEnd <= removeTextSpecB.position) {
1326             // adapt B by removed position
1327             removeTextSpecB.position -= removeTextSpecA.length;
1328         // overlapping?
1329         // (removeTextSpecBEnd <= removeTextSpecA.position above catches non-overlapping from this condition)
1330         } else if (removeTextSpecB.position < removeTextSpecAEnd) {
1331             // A removes in front of B?
1332             if (removeTextSpecA.position < removeTextSpecB.position) {
1333                 // A still to remove range at its end?
1334                 if (removeTextSpecBEnd < removeTextSpecAEnd) {
1335                     removeTextSpecA.length = removeTextSpecA.length - removeTextSpecB.length;
1336                 } else {
1337                     removeTextSpecA.length = removeTextSpecB.position - removeTextSpecA.position;
1338                 }
1339                 // B still to remove range at its end?
1340                 if (removeTextSpecAEnd < removeTextSpecBEnd) {
1341                     removeTextSpecB.position = removeTextSpecA.position;
1342                     removeTextSpecB.length = removeTextSpecBEnd - removeTextSpecAEnd;
1343                 } else {
1344                     // B completely overlapped by other, so it becomes a noop
1345                     removeTextSpecBResult = [];
1346                 }
1347             // B removes in front of or starting at same like A
1348             } else {
1349                 // B still to remove range at its end?
1350                 if (removeTextSpecAEnd < removeTextSpecBEnd) {
1351                     removeTextSpecB.length = removeTextSpecB.length - removeTextSpecA.length;
1352                 } else {
1353                     // B still to remove range at its start?
1354                     if (removeTextSpecB.position < removeTextSpecA.position) {
1355                         removeTextSpecB.length = removeTextSpecA.position - removeTextSpecB.position;
1356                     } else {
1357                         // B completely overlapped by other, so it becomes a noop
1358                         removeTextSpecBResult = [];
1359                     }
1360                 }
1361                 // A still to remove range at its end?
1362                 if (removeTextSpecBEnd < removeTextSpecAEnd) {
1363                     removeTextSpecA.position = removeTextSpecB.position;
1364                     removeTextSpecA.length = removeTextSpecAEnd - removeTextSpecBEnd;
1365                 } else {
1366                     // A completely overlapped by other, so it becomes a noop
1367                     removeTextSpecAResult = [];
1368                 }
1369             }
1370         }
1371         return {
1372             opSpecsA:  removeTextSpecAResult,
1373             opSpecsB:  removeTextSpecBResult
1374         };
1375     }
1376 
1377     /**
1378      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1379      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1380      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1381      */
1382     function transformRemoveTextSetParagraphStyle(removeTextSpec, setParagraphStyleSpec) {
1383         // Removal is done entirely in some preceding paragraph
1384         if (removeTextSpec.position < setParagraphStyleSpec.position) {
1385             setParagraphStyleSpec.position -= removeTextSpec.length;
1386         }
1387 
1388         return {
1389             opSpecsA:  [removeTextSpec],
1390             opSpecsB:  [setParagraphStyleSpec]
1391         };
1392     }
1393 
1394     /**
1395      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1396      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1397      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1398      */
1399     function transformRemoveTextSplitParagraph(removeTextSpec, splitParagraphSpec) {
1400         var removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length,
1401             helperOpspec,
1402             removeTextSpecResult = [removeTextSpec],
1403             splitParagraphSpecResult = [splitParagraphSpec];
1404 
1405         // adapt removeTextSpec
1406         if (splitParagraphSpec.position <= removeTextSpec.position) {
1407             removeTextSpec.position += 1;
1408         } else if (splitParagraphSpec.position < removeTextSpecEnd) {
1409             // we have to split the removal into two ops, before and after the insertion
1410             removeTextSpec.length = splitParagraphSpec.position - removeTextSpec.position;
1411             helperOpspec = {
1412                 optype: "RemoveText",
1413                 memberid: removeTextSpec.memberid,
1414                 timestamp: removeTextSpec.timestamp,
1415                 position: splitParagraphSpec.position + 1,
1416                 length: removeTextSpecEnd - splitParagraphSpec.position
1417             };
1418             removeTextSpecResult.unshift(helperOpspec); // helperOp first, so its position is not affected by the real op
1419         }
1420 
1421         // adapt splitParagraphSpec
1422         if (removeTextSpec.position + removeTextSpec.length <= splitParagraphSpec.position) {
1423             splitParagraphSpec.position -= removeTextSpec.length;
1424         } else if (removeTextSpec.position < splitParagraphSpec.position) {
1425             splitParagraphSpec.position = removeTextSpec.position;
1426         }
1427 
1428         if (removeTextSpec.position + removeTextSpec.length < splitParagraphSpec.sourceParagraphPosition) {
1429             // Removed text is before the source paragraph
1430             splitParagraphSpec.sourceParagraphPosition -= removeTextSpec.length;
1431         }
1432         // removeText ops can't cross over paragraph boundaries, so don't check this case
1433 
1434         return {
1435             opSpecsA:  removeTextSpecResult,
1436             opSpecsB:  splitParagraphSpecResult
1437         };
1438     }
1439 
1440     /**
1441      * Does an OT on the two passed opspecs, where they are not modified at all,
1442      * and so simply returns them in the result arrays.
1443      * @param {!Object} opSpecA
1444      * @param {!Object} opSpecB
1445      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1446      */
1447     function passUnchanged(opSpecA, opSpecB) {
1448         return {
1449             opSpecsA:  [opSpecA],
1450             opSpecsB:  [opSpecB]
1451         };
1452     }
1453 
1454 
1455     var /**
1456          * This is the lower-left half of the sparse NxN matrix with all the
1457          * transformation methods on the possible pairs of ops. As the matrix
1458          * is symmetric, only that half is used. So the user of this matrix has
1459          * to ensure the proper order of opspecs on lookup and on calling the
1460          * picked transformation method.
1461          *
1462          * Each transformation method takes the two opspecs (and optionally
1463          * a flag if the first has a higher priority, in case of tie breaking
1464          * having to be done). The method returns a record with the two
1465          * resulting arrays of ops, with key names "opSpecsA" and "opSpecsB".
1466          * Those arrays could have more than the initial respective opspec
1467          * inside, in case some additional helper opspecs are needed, or be
1468          * empty if the opspec turned into a no-op in the transformation.
1469          * If a transformation is not doable, the method returns "null".
1470          *
1471          * Some operations are added onto the stack only by the master session,
1472          * for example AddMember, RemoveMember, and UpdateMember. These therefore need
1473          * not be transformed against each other, since the master session is the
1474          * only originator of these ops. Therefore, their pairing entries in the
1475          * matrix are missing. They do however require a passUnchanged entry
1476          * with the other ops.
1477          *
1478          * Here the CC signature of each transformation method:
1479          * param {!Object} opspecA
1480          * param {!Object} opspecB
1481          * (param {!boolean} hasAPriorityOverB)  can be left out
1482          * return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1483          *
1484          * Empty cells in this matrix mean there is no such transformation
1485          * possible, and should be handled as if the method returns "null".
1486          *
1487          * @type {!Object.<string,!Object.<string,function(!Object,!Object,boolean=):?{opSpecsA:!Array.<!{optype:string}>, opSpecsB:!Array.<!{optype:string}>}>>}
1488          */
1489         transformations;
1490     transformations = {
1491         "AddCursor": {
1492             "AddCursor":            passUnchanged,
1493             "AddMember":            passUnchanged,
1494             "AddStyle":             passUnchanged,
1495             "ApplyDirectStyling":   passUnchanged,
1496             "InsertText":           passUnchanged,
1497             "MergeParagraph":       passUnchanged,
1498             "MoveCursor":           passUnchanged,
1499             "RemoveCursor":         passUnchanged,
1500             "RemoveMember":         passUnchanged,
1501             "RemoveStyle":          passUnchanged,
1502             "RemoveText":           passUnchanged,
1503             "SetParagraphStyle":    passUnchanged,
1504             "SplitParagraph":       passUnchanged,
1505             "UpdateMember":         passUnchanged,
1506             "UpdateMetadata":       passUnchanged,
1507             "UpdateParagraphStyle": passUnchanged
1508         },
1509         "AddMember": {
1510             "AddStyle":             passUnchanged,
1511             "ApplyDirectStyling":   passUnchanged,
1512             "InsertText":           passUnchanged,
1513             "MergeParagraph":       passUnchanged,
1514             "MoveCursor":           passUnchanged,
1515             "RemoveCursor":         passUnchanged,
1516             "RemoveStyle":          passUnchanged,
1517             "RemoveText":           passUnchanged,
1518             "SetParagraphStyle":    passUnchanged,
1519             "SplitParagraph":       passUnchanged,
1520             "UpdateMetadata":       passUnchanged,
1521             "UpdateParagraphStyle": passUnchanged
1522         },
1523         "AddStyle": {
1524             "AddStyle":             passUnchanged,
1525             "ApplyDirectStyling":   passUnchanged,
1526             "InsertText":           passUnchanged,
1527             "MergeParagraph":       passUnchanged,
1528             "MoveCursor":           passUnchanged,
1529             "RemoveCursor":         passUnchanged,
1530             "RemoveMember":         passUnchanged,
1531             "RemoveStyle":          transformAddStyleRemoveStyle,
1532             "RemoveText":           passUnchanged,
1533             "SetParagraphStyle":    passUnchanged,
1534             "SplitParagraph":       passUnchanged,
1535             "UpdateMember":         passUnchanged,
1536             "UpdateMetadata":       passUnchanged,
1537             "UpdateParagraphStyle": passUnchanged
1538         },
1539         "ApplyDirectStyling": {
1540             "ApplyDirectStyling":   transformApplyDirectStylingApplyDirectStyling,
1541             "InsertText":           transformApplyDirectStylingInsertText,
1542             "MergeParagraph":       transformApplyDirectStylingMergeParagraph,
1543             "MoveCursor":           passUnchanged,
1544             "RemoveCursor":         passUnchanged,
1545             "RemoveMember":         passUnchanged,
1546             "RemoveStyle":          passUnchanged,
1547             "RemoveText":           transformApplyDirectStylingRemoveText,
1548             "SetParagraphStyle":    passUnchanged,
1549             "SplitParagraph":       transformApplyDirectStylingSplitParagraph,
1550             "UpdateMember":         passUnchanged,
1551             "UpdateMetadata":       passUnchanged,
1552             "UpdateParagraphStyle": passUnchanged
1553         },
1554         "InsertText": {
1555             "InsertText":           transformInsertTextInsertText,
1556             "MergeParagraph":       transformInsertTextMergeParagraph,
1557             "MoveCursor":           transformInsertTextMoveCursor,
1558             "RemoveCursor":         passUnchanged,
1559             "RemoveMember":         passUnchanged,
1560             "RemoveStyle":          passUnchanged,
1561             "RemoveText":           transformInsertTextRemoveText,
1562             "SetParagraphStyle":    transformInsertTextSetParagraphStyle,
1563             "SplitParagraph":       transformInsertTextSplitParagraph,
1564             "UpdateMember":         passUnchanged,
1565             "UpdateMetadata":       passUnchanged,
1566             "UpdateParagraphStyle": passUnchanged
1567         },
1568         "MergeParagraph": {
1569             "MergeParagraph":       transformMergeParagraphMergeParagraph,
1570             "MoveCursor":           transformMergeParagraphMoveCursor,
1571             "RemoveCursor":         passUnchanged,
1572             "RemoveMember":         passUnchanged,
1573             "RemoveStyle":          passUnchanged,
1574             "RemoveText":           transformMergeParagraphRemoveText,
1575             "SetParagraphStyle":    transformMergeParagraphSetParagraphStyle,
1576             "SplitParagraph":       transformMergeParagraphSplitParagraph,
1577             "UpdateMember":         passUnchanged,
1578             "UpdateMetadata":       passUnchanged,
1579             "UpdateParagraphStyle": passUnchanged
1580         },
1581         "MoveCursor": {
1582             "MoveCursor":           passUnchanged,
1583             "RemoveCursor":         transformMoveCursorRemoveCursor,
1584             "RemoveMember":         passUnchanged,
1585             "RemoveStyle":          passUnchanged,
1586             "RemoveText":           transformMoveCursorRemoveText,
1587             "SetParagraphStyle":    passUnchanged,
1588             "SplitParagraph":       transformMoveCursorSplitParagraph,
1589             "UpdateMember":         passUnchanged,
1590             "UpdateMetadata":       passUnchanged,
1591             "UpdateParagraphStyle": passUnchanged
1592         },
1593         "RemoveCursor": {
1594             "RemoveCursor":         transformRemoveCursorRemoveCursor,
1595             "RemoveMember":         passUnchanged,
1596             "RemoveStyle":          passUnchanged,
1597             "RemoveText":           passUnchanged,
1598             "SetParagraphStyle":    passUnchanged,
1599             "SplitParagraph":       passUnchanged,
1600             "UpdateMember":         passUnchanged,
1601             "UpdateMetadata":       passUnchanged,
1602             "UpdateParagraphStyle": passUnchanged
1603         },
1604         "RemoveMember": {
1605             "RemoveStyle":          passUnchanged,
1606             "RemoveText":           passUnchanged,
1607             "SetParagraphStyle":    passUnchanged,
1608             "SplitParagraph":       passUnchanged,
1609             "UpdateMetadata":       passUnchanged,
1610             "UpdateParagraphStyle": passUnchanged
1611         },
1612         "RemoveStyle": {
1613             "RemoveStyle":          transformRemoveStyleRemoveStyle,
1614             "RemoveText":           passUnchanged,
1615             "SetParagraphStyle":    transformRemoveStyleSetParagraphStyle,
1616             "SplitParagraph":       passUnchanged,
1617             "UpdateMember":         passUnchanged,
1618             "UpdateMetadata":       passUnchanged,
1619             "UpdateParagraphStyle": transformRemoveStyleUpdateParagraphStyle
1620         },
1621         "RemoveText": {
1622             "RemoveText":           transformRemoveTextRemoveText,
1623             "SetParagraphStyle":    transformRemoveTextSetParagraphStyle,
1624             "SplitParagraph":       transformRemoveTextSplitParagraph,
1625             "UpdateMember":         passUnchanged,
1626             "UpdateMetadata":       passUnchanged,
1627             "UpdateParagraphStyle": passUnchanged
1628         },
1629         "SetParagraphStyle": {
1630             "SetParagraphStyle":    transformSetParagraphStyleSetParagraphStyle,
1631             "SplitParagraph":       transformSetParagraphStyleSplitParagraph,
1632             "UpdateMember":         passUnchanged,
1633             "UpdateMetadata":       passUnchanged,
1634             "UpdateParagraphStyle": passUnchanged
1635         },
1636         "SplitParagraph": {
1637             "SplitParagraph":       transformSplitParagraphSplitParagraph,
1638             "UpdateMember":         passUnchanged,
1639             "UpdateMetadata":       passUnchanged,
1640             "UpdateParagraphStyle": passUnchanged
1641         },
1642         "UpdateMember": {
1643             "UpdateMetadata":       passUnchanged,
1644             "UpdateParagraphStyle": passUnchanged
1645         },
1646         "UpdateMetadata": {
1647             "UpdateMetadata":       transformUpdateMetadataUpdateMetadata,
1648             "UpdateParagraphStyle": passUnchanged
1649         },
1650         "UpdateParagraphStyle": {
1651             "UpdateParagraphStyle": transformUpdateParagraphStyleUpdateParagraphStyle
1652         }
1653     };
1654 
1655     this.passUnchanged = passUnchanged;
1656 
1657     /**
1658      * @param {!Object.<!string,!Object.<!string,!Function>>}  moreTransformations
1659      * @return {undefined}
1660      */
1661     this.extendTransformations = function (moreTransformations) {
1662         Object.keys(moreTransformations).forEach(function (optypeA) {
1663             var moreTransformationsOptypeAMap = moreTransformations[optypeA],
1664                 /**@type{!Object.<string,!Function>}*/
1665                 optypeAMap,
1666                 isExtendingOptypeAMap = transformations.hasOwnProperty(optypeA);
1667 
1668             runtime.log((isExtendingOptypeAMap ? "Extending" : "Adding") + " map for optypeA: " + optypeA);
1669             if (!isExtendingOptypeAMap) {
1670                 transformations[optypeA] = {};
1671             }
1672             optypeAMap = transformations[optypeA];
1673 
1674             Object.keys(moreTransformationsOptypeAMap).forEach(function (optypeB) {
1675                 var isOverwritingOptypeBEntry = optypeAMap.hasOwnProperty(optypeB);
1676                 runtime.assert(optypeA <= optypeB, "Wrong order:" + optypeA + ", " + optypeB);
1677                 runtime.log("  " + (isOverwritingOptypeBEntry ? "Overwriting" : "Adding") + " entry for optypeB: " + optypeB);
1678                 optypeAMap[optypeB] = moreTransformationsOptypeAMap[optypeB];
1679             });
1680         });
1681     };
1682 
1683     /**
1684      * @param {!{optype:string}} opSpecA op with lower priority in case of tie breaking
1685      * @param {!{optype:string}} opSpecB op with higher priority in case of tie breaking
1686      * @return {?{opSpecsA:!Array.<!{optype:string}>,
1687      *            opSpecsB:!Array.<!{optype:string}>}}
1688      */
1689     this.transformOpspecVsOpspec = function (opSpecA, opSpecB) {
1690         var isOptypeAAlphaNumericSmaller = (opSpecA.optype <= opSpecB.optype),
1691             helper, transformationFunctionMap, transformationFunction, result;
1692 
1693 runtime.log("Crosstransforming:");
1694 runtime.log(runtime.toJson(opSpecA));
1695 runtime.log(runtime.toJson(opSpecB));
1696 
1697         // switch order if needed, to match the mirrored part of the matrix
1698         if (!isOptypeAAlphaNumericSmaller) {
1699             helper = opSpecA;
1700             opSpecA = opSpecB;
1701             opSpecB = helper;
1702         }
1703         // look up transformation method
1704         transformationFunctionMap = transformations[opSpecA.optype];
1705         transformationFunction = transformationFunctionMap && transformationFunctionMap[opSpecB.optype];
1706 
1707         // transform
1708         if (transformationFunction) {
1709             result = transformationFunction(opSpecA, opSpecB, !isOptypeAAlphaNumericSmaller);
1710             if (!isOptypeAAlphaNumericSmaller && result !== null) {
1711                 // switch result back
1712                 result = {
1713                     opSpecsA:  result.opSpecsB,
1714                     opSpecsB:  result.opSpecsA
1715                 };
1716             }
1717         } else {
1718             result = null;
1719         }
1720 runtime.log("result:");
1721 if (result) {
1722 runtime.log(runtime.toJson(result.opSpecsA));
1723 runtime.log(runtime.toJson(result.opSpecsB));
1724 } else {
1725 runtime.log("null");
1726 }
1727         return result;
1728     };
1729 };
1730