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