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 (mergeParagraphSpecA.destinationStartPosition < mergeParagraphSpecB.destinationStartPosition) {
737             mergeParagraphSpecB.destinationStartPosition -= 1;
738             mergeParagraphSpecB.sourceStartPosition -= 1;
739         } else { // mergeParagraphSpecB.destinationStartPosition < mergeParagraphSpecA.destinationStartPosition
740             mergeParagraphSpecA.destinationStartPosition -= 1;
741             mergeParagraphSpecA.sourceStartPosition -= 1;
742         }
743 
744         return {
745             opSpecsA:  specsForB,
746             opSpecsB:  specsForA
747         };
748     }
749 
750     /**
751      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
752      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
753      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
754      */
755     function transformMergeParagraphMoveCursor(mergeParagraphSpec, moveCursorSpec) {
756         var pointA = moveCursorSpec.position,
757             pointB = moveCursorSpec.position + moveCursorSpec.length,
758             start = Math.min(pointA, pointB),
759             end = Math.max(pointA, pointB);
760 
761         if (start >= mergeParagraphSpec.sourceStartPosition) {
762             start -= 1;
763         }
764         if (end >= mergeParagraphSpec.sourceStartPosition) {
765             end -= 1;
766         }
767 
768         // When updating the cursor spec, ensure the selection direction is preserved.
769         // If the length was previously positive, it should remain positive.
770         if (moveCursorSpec.length >= 0) {
771             moveCursorSpec.position = start;
772             moveCursorSpec.length = end - start;
773         } else {
774             moveCursorSpec.position = end;
775             moveCursorSpec.length = start - end;
776         }
777 
778         return {
779             opSpecsA:  [mergeParagraphSpec],
780             opSpecsB:  [moveCursorSpec]
781         };
782     }
783 
784     /**
785      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
786      * @param {!ops.OpRemoveText.Spec} removeTextSpec
787      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
788      */
789     function transformMergeParagraphRemoveText(mergeParagraphSpec, removeTextSpec) {
790         // RemoveText ops can't cross paragraph boundaries, so only the position needs to be checked
791         if (removeTextSpec.position >= mergeParagraphSpec.sourceStartPosition) {
792             removeTextSpec.position -= 1;
793         } else {
794             if (removeTextSpec.position < mergeParagraphSpec.destinationStartPosition) {
795                 mergeParagraphSpec.destinationStartPosition -= removeTextSpec.length;
796             }
797             if (removeTextSpec.position < mergeParagraphSpec.sourceStartPosition) {
798                 mergeParagraphSpec.sourceStartPosition -= removeTextSpec.length;
799             }
800         }
801 
802         return {
803             opSpecsA:  [mergeParagraphSpec],
804             opSpecsB:  [removeTextSpec]
805         };
806     }
807 
808     /**
809      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
810      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
811      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
812      */
813     function transformMergeParagraphSetParagraphStyle(mergeParagraphSpec, setParagraphStyleSpec) {
814         var opSpecsA = [mergeParagraphSpec],
815             opSpecsB = [setParagraphStyleSpec];
816 
817         // SetParagraphStyle ops can't cross paragraph boundaries
818         if (setParagraphStyleSpec.position > mergeParagraphSpec.sourceStartPosition) {
819             // Paragraph beyond the ones region affected by the merge
820             setParagraphStyleSpec.position -= 1;
821         } else if (setParagraphStyleSpec.position === mergeParagraphSpec.destinationStartPosition
822                     || setParagraphStyleSpec.position === mergeParagraphSpec.sourceStartPosition) {
823             // Attempting to style a merging paragraph
824             setParagraphStyleSpec.position = mergeParagraphSpec.destinationStartPosition;
825             mergeParagraphSpec.paragraphStyleName = setParagraphStyleSpec.styleName;
826         }
827 
828         return {
829             opSpecsA:  opSpecsA,
830             opSpecsB:  opSpecsB
831         };
832     }
833 
834     /**
835      * @param {!ops.OpMergeParagraph.Spec} mergeParagraphSpec
836      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
837      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
838      */
839     function transformMergeParagraphSplitParagraph(mergeParagraphSpec, splitParagraphSpec) {
840         var styleSplitParagraph,
841             moveCursorOp,
842             opSpecsA = [mergeParagraphSpec],
843             opSpecsB = [splitParagraphSpec];
844 
845         if (splitParagraphSpec.position < mergeParagraphSpec.destinationStartPosition) {
846             // Split occurs before the merge destination
847             // Splitting a paragraph inserts one step, moving the merge along
848             mergeParagraphSpec.destinationStartPosition += 1;
849             mergeParagraphSpec.sourceStartPosition += 1;
850         } else if (splitParagraphSpec.position >= mergeParagraphSpec.destinationStartPosition
851             && splitParagraphSpec.position < mergeParagraphSpec.sourceStartPosition) {
852             // split occurs within the paragraphs being merged
853             splitParagraphSpec.paragraphStyleName = mergeParagraphSpec.paragraphStyleName;
854             styleSplitParagraph = /**@type{!ops.OpSetParagraphStyle.Spec}*/({
855                 optype: "SetParagraphStyle",
856                 memberid: mergeParagraphSpec.memberid,
857                 timestamp: mergeParagraphSpec.timestamp,
858                 position: mergeParagraphSpec.destinationStartPosition,
859                 styleName: mergeParagraphSpec.paragraphStyleName
860             });
861             opSpecsA.push(styleSplitParagraph);
862             if (splitParagraphSpec.position === mergeParagraphSpec.sourceStartPosition - 1
863                     && mergeParagraphSpec.moveCursor) {
864                 // OdtDocument.getTextNodeAtStep + Spec.moveCursor make it very difficult to control cursor placement
865                 // When a split + merge combines, there is a tricky situation because the split will leave other cursors
866                 // on the last step in the new paragraph.
867                 // When the merge is relocated to attach to the front of the newly inserted paragraph below, the cursor
868                 // will end up at the start of the new paragraph. Workaround this by manually setting the cursor back
869                 // to the appropriate location after the merge completes
870                 moveCursorOp = /**@type{!ops.OpMoveCursor.Spec}*/({
871                     optype: "MoveCursor",
872                     memberid: mergeParagraphSpec.memberid,
873                     timestamp: mergeParagraphSpec.timestamp,
874                     position: splitParagraphSpec.position,
875                     length: 0
876                 });
877                 opSpecsA.push(moveCursorOp);
878             }
879 
880             // SplitParagraph ops effectively create new paragraph boundaries. The user intent
881             // is for the source paragraph to be joined to the END of the dest paragraph. If the
882             // split occurs in the dest paragraph, the source should be joined to the newly created
883             // paragraph instead
884             mergeParagraphSpec.destinationStartPosition = splitParagraphSpec.position + 1;
885             mergeParagraphSpec.sourceStartPosition += 1;
886         } else if (splitParagraphSpec.position >= mergeParagraphSpec.sourceStartPosition) {
887             // Split occurs after the merge source
888             // Merging paragraphs remove one step
889             splitParagraphSpec.position -= 1;
890             splitParagraphSpec.sourceParagraphPosition -= 1;
891         }
892 
893         return {
894             opSpecsA:  opSpecsA,
895             opSpecsB:  opSpecsB
896         };
897     }
898 
899     /**
900      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpecA
901      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpecB
902      * @param {!boolean} hasAPriority
903      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
904      */
905     function transformUpdateParagraphStyleUpdateParagraphStyle(updateParagraphStyleSpecA, updateParagraphStyleSpecB, hasAPriority) {
906         var majorSpec, minorSpec,
907             updateParagraphStyleSpecAResult = [updateParagraphStyleSpecA],
908             updateParagraphStyleSpecBResult = [updateParagraphStyleSpecB];
909 
910         // same style updated by other op?
911         if (updateParagraphStyleSpecA.styleName === updateParagraphStyleSpecB.styleName) {
912             majorSpec = hasAPriority ? updateParagraphStyleSpecA : updateParagraphStyleSpecB;
913             minorSpec = hasAPriority ? updateParagraphStyleSpecB : updateParagraphStyleSpecA;
914 
915             // any properties which are set by other update op need to be dropped
916             dropOverruledAndUnneededProperties(minorSpec.setProperties,
917                 minorSpec.removedProperties, majorSpec.setProperties,
918                 majorSpec.removedProperties, 'style:paragraph-properties');
919             dropOverruledAndUnneededProperties(minorSpec.setProperties,
920                 minorSpec.removedProperties, majorSpec.setProperties,
921                 majorSpec.removedProperties, 'style:text-properties');
922             dropOverruledAndUnneededAttributes(minorSpec.setProperties || null,
923                 /**@type{{attributes: string}}*/(minorSpec.removedProperties) || null,
924                 majorSpec.setProperties || null,
925                 /**@type{{attributes: string}}*/(majorSpec.removedProperties) || null);
926 
927             // check if there are any changes left and the major op has not become a noop
928             if (!(majorSpec.setProperties && hasProperties(majorSpec.setProperties)) &&
929                     !(majorSpec.removedProperties && hasRemovedProperties(majorSpec.removedProperties))) {
930                 // set major spec to noop
931                 if (hasAPriority) {
932                     updateParagraphStyleSpecAResult = [];
933                 } else {
934                     updateParagraphStyleSpecBResult = [];
935                 }
936             }
937             // check if there are any changes left and the minor op has not become a noop
938             if (!(minorSpec.setProperties && hasProperties(minorSpec.setProperties)) &&
939                     !(minorSpec.removedProperties && hasRemovedProperties(minorSpec.removedProperties))) {
940                 // set minor spec to noop 
941                 if (hasAPriority) {
942                     updateParagraphStyleSpecBResult = [];
943                 } else {
944                     updateParagraphStyleSpecAResult = [];
945                 }
946             }
947         }
948 
949         return {
950             opSpecsA:  updateParagraphStyleSpecAResult,
951             opSpecsB:  updateParagraphStyleSpecBResult
952         };
953     }
954 
955     /**
956      * @param {!ops.OpUpdateMetadata.Spec} updateMetadataSpecA
957      * @param {!ops.OpUpdateMetadata.Spec} updateMetadataSpecB
958      * @param {!boolean} hasAPriority
959      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
960      */
961     function transformUpdateMetadataUpdateMetadata(updateMetadataSpecA, updateMetadataSpecB, hasAPriority) {
962         var majorSpec, minorSpec,
963             updateMetadataSpecAResult = [updateMetadataSpecA],
964             updateMetadataSpecBResult = [updateMetadataSpecB];
965 
966         majorSpec = hasAPriority ? updateMetadataSpecA : updateMetadataSpecB;
967         minorSpec = hasAPriority ? updateMetadataSpecB : updateMetadataSpecA;
968 
969         // any properties which are set by other update op need to be dropped
970         dropOverruledAndUnneededAttributes(minorSpec.setProperties || null,
971                             minorSpec.removedProperties || null,
972                             majorSpec.setProperties || null,
973                             majorSpec.removedProperties || null);
974 
975         // check if there are any changes left and the major op has not become a noop
976         if (!(majorSpec.setProperties && hasProperties(majorSpec.setProperties)) &&
977                 !(majorSpec.removedProperties && hasRemovedProperties(majorSpec.removedProperties))) {
978             // set major spec to noop
979             if (hasAPriority) {
980                 updateMetadataSpecAResult = [];
981             } else {
982                 updateMetadataSpecBResult = [];
983             }
984         }
985         // check if there are any changes left and the minor op has not become a noop
986         if (!(minorSpec.setProperties && hasProperties(minorSpec.setProperties)) &&
987                 !(minorSpec.removedProperties && hasRemovedProperties(minorSpec.removedProperties))) {
988             // set minor spec to noop 
989             if (hasAPriority) {
990                 updateMetadataSpecBResult = [];
991             } else {
992                 updateMetadataSpecAResult = [];
993             }
994         }
995 
996         return {
997             opSpecsA:  updateMetadataSpecAResult,
998             opSpecsB:  updateMetadataSpecBResult
999         };
1000     }
1001 
1002     /**
1003      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpecA
1004      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpecB
1005      * @param {!boolean} hasAPriority
1006      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1007      */
1008     function transformSetParagraphStyleSetParagraphStyle(setParagraphStyleSpecA, setParagraphStyleSpecB, hasAPriority) {
1009         if (setParagraphStyleSpecA.position === setParagraphStyleSpecB.position) {
1010             if (hasAPriority) {
1011                 setParagraphStyleSpecB.styleName = setParagraphStyleSpecA.styleName;
1012             } else {
1013                 setParagraphStyleSpecA.styleName = setParagraphStyleSpecB.styleName;
1014             }
1015         }
1016 
1017         return {
1018             opSpecsA:  [setParagraphStyleSpecA],
1019             opSpecsB:  [setParagraphStyleSpecB]
1020         };
1021     }
1022 
1023     /**
1024      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1025      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1026      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1027      */
1028     function transformSetParagraphStyleSplitParagraph(setParagraphStyleSpec, splitParagraphSpec) {
1029         var opSpecsA = [setParagraphStyleSpec],
1030             opSpecsB = [splitParagraphSpec],
1031             setParagraphClone;
1032 
1033         if (setParagraphStyleSpec.position > splitParagraphSpec.position) {
1034             setParagraphStyleSpec.position += 1;
1035         } else if (setParagraphStyleSpec.position === splitParagraphSpec.sourceParagraphPosition) {
1036             // When a set paragraph style & split conflict, the set paragraph style always wins
1037 
1038             splitParagraphSpec.paragraphStyleName = setParagraphStyleSpec.styleName;
1039             // The new paragraph that resulted from the already executed split op should be styled with
1040             // the original paragraph style.
1041             setParagraphClone = cloneOpspec(setParagraphStyleSpec);
1042             // A split paragraph op introduces a new paragraph boundary just passed the point where the split occurs
1043             setParagraphClone.position = splitParagraphSpec.position + 1;
1044             opSpecsA.push(setParagraphClone);
1045         }
1046 
1047         return {
1048             opSpecsA:  opSpecsA,
1049             opSpecsB:  opSpecsB
1050         };
1051     }
1052 
1053     /**
1054      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpecA
1055      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpecB
1056      * @param {!boolean} hasAPriority
1057      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1058      */
1059     function transformSplitParagraphSplitParagraph(splitParagraphSpecA, splitParagraphSpecB, hasAPriority) {
1060         var specABeforeB,
1061             specBBeforeA;
1062 
1063         if (splitParagraphSpecA.position < splitParagraphSpecB.position) {
1064             specABeforeB =  true;
1065         } else if (splitParagraphSpecB.position < splitParagraphSpecA.position) {
1066             specBBeforeA = true;
1067         } else if (splitParagraphSpecA.position === splitParagraphSpecB.position) {
1068             if (hasAPriority) {
1069                 specABeforeB =  true;
1070             } else {
1071                 specBBeforeA = true;
1072             }
1073         }
1074 
1075         if (specABeforeB) {
1076             splitParagraphSpecB.position += 1;
1077             if (splitParagraphSpecA.position < splitParagraphSpecB.sourceParagraphPosition) {
1078                 splitParagraphSpecB.sourceParagraphPosition += 1;
1079             } else {
1080                 // Split occurs between specB's split position & it's source paragraph position
1081                 // This means specA introduces a NEW paragraph boundary
1082                 splitParagraphSpecB.sourceParagraphPosition = splitParagraphSpecA.position + 1;
1083             }
1084         } else if (specBBeforeA) {
1085             splitParagraphSpecA.position += 1;
1086             if (splitParagraphSpecB.position < splitParagraphSpecB.sourceParagraphPosition) {
1087                 splitParagraphSpecA.sourceParagraphPosition += 1;
1088             } else {
1089                 // Split occurs between specA's split position & it's source paragraph position
1090                 // This means specB introduces a NEW paragraph boundary
1091                 splitParagraphSpecA.sourceParagraphPosition = splitParagraphSpecB.position + 1;
1092             }
1093         }
1094 
1095         return {
1096             opSpecsA:  [splitParagraphSpecA],
1097             opSpecsB:  [splitParagraphSpecB]
1098         };
1099     }
1100 
1101     /**
1102      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1103      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpec
1104      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1105      */
1106     function transformMoveCursorRemoveCursor(moveCursorSpec, removeCursorSpec) {
1107         var isSameCursorRemoved = (moveCursorSpec.memberid === removeCursorSpec.memberid);
1108 
1109         return {
1110             opSpecsA:  isSameCursorRemoved ? [] : [moveCursorSpec],
1111             opSpecsB:  [removeCursorSpec]
1112         };
1113     }
1114 
1115     /**
1116      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1117      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1118      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1119      */
1120     function transformMoveCursorRemoveText(moveCursorSpec, removeTextSpec) {
1121         var isMoveCursorSpecRangeInverted = invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec),
1122             moveCursorSpecEnd = moveCursorSpec.position + moveCursorSpec.length,
1123             removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length;
1124 
1125         // transform moveCursorSpec
1126         // removed positions by object up to move cursor position?
1127         if (removeTextSpecEnd <= moveCursorSpec.position) {
1128             // adapt by removed position
1129             moveCursorSpec.position -= removeTextSpec.length;
1130         // overlapping?
1131         } else if (removeTextSpec.position < moveCursorSpecEnd) {
1132             // still to select range starting at cursor position?
1133             if (moveCursorSpec.position < removeTextSpec.position) {
1134                 // still to select range ending at selection?
1135                 if (removeTextSpecEnd < moveCursorSpecEnd) {
1136                     moveCursorSpec.length -= removeTextSpec.length;
1137                 } else {
1138                     moveCursorSpec.length = removeTextSpec.position - moveCursorSpec.position;
1139                 }
1140             // remove overlapping section
1141             } else {
1142                 // fall at start of removed section
1143                 moveCursorSpec.position = removeTextSpec.position;
1144                 // still to select range at selection end?
1145                 if (removeTextSpecEnd < moveCursorSpecEnd) {
1146                     moveCursorSpec.length = moveCursorSpecEnd - removeTextSpecEnd;
1147                 } else {
1148                     // completely overlapped by other, so selection gets void
1149                     moveCursorSpec.length = 0;
1150                 }
1151             }
1152         }
1153 
1154         if (isMoveCursorSpecRangeInverted) {
1155             invertMoveCursorSpecRange(moveCursorSpec);
1156         }
1157 
1158         return {
1159             opSpecsA:  [moveCursorSpec],
1160             opSpecsB:  [removeTextSpec]
1161         };
1162     }
1163 
1164     /**
1165      * @param {!ops.OpMoveCursor.Spec} moveCursorSpec
1166      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1167      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1168      */
1169     function transformMoveCursorSplitParagraph(moveCursorSpec, splitParagraphSpec) {
1170         var isMoveCursorSpecRangeInverted = invertMoveCursorSpecRangeOnNegativeLength(moveCursorSpec);
1171 
1172         // transform moveCursorSpec
1173         if (splitParagraphSpec.position < moveCursorSpec.position) {
1174             moveCursorSpec.position += 1;
1175         } else if (splitParagraphSpec.position < moveCursorSpec.position + moveCursorSpec.length) {
1176             moveCursorSpec.length += 1;
1177         }
1178 
1179         if (isMoveCursorSpecRangeInverted) {
1180             invertMoveCursorSpecRange(moveCursorSpec);
1181         }
1182 
1183         return {
1184             opSpecsA:  [moveCursorSpec],
1185             opSpecsB:  [splitParagraphSpec]
1186         };
1187     }
1188 
1189     /**
1190      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpecA
1191      * @param {!ops.OpRemoveCursor.Spec} removeCursorSpecB
1192      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1193      */
1194     function transformRemoveCursorRemoveCursor(removeCursorSpecA, removeCursorSpecB) {
1195         var isSameMemberid = (removeCursorSpecA.memberid === removeCursorSpecB.memberid);
1196 
1197         // if both are removing the same cursor, their transformed counter-ops become noops
1198         return {
1199             opSpecsA:  isSameMemberid ? [] : [removeCursorSpecA],
1200             opSpecsB:  isSameMemberid ? [] : [removeCursorSpecB]
1201         };
1202     }
1203 
1204     /**
1205      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpecA
1206      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpecB
1207      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1208      */
1209     function transformRemoveStyleRemoveStyle(removeStyleSpecA, removeStyleSpecB) {
1210         var isSameStyle = (removeStyleSpecA.styleName === removeStyleSpecB.styleName && removeStyleSpecA.styleFamily === removeStyleSpecB.styleFamily);
1211 
1212         // if both are removing the same style, their transformed counter-ops become noops
1213         return {
1214             opSpecsA:  isSameStyle ? [] : [removeStyleSpecA],
1215             opSpecsB:  isSameStyle ? [] : [removeStyleSpecB]
1216         };
1217     }
1218 
1219     /**
1220      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpec
1221      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1222      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1223      */
1224     function transformRemoveStyleSetParagraphStyle(removeStyleSpec, setParagraphStyleSpec) {
1225         var helperOpspec,
1226             removeStyleSpecResult = [removeStyleSpec],
1227             setParagraphStyleSpecResult = [setParagraphStyleSpec];
1228 
1229         if (removeStyleSpec.styleFamily === "paragraph" && removeStyleSpec.styleName === setParagraphStyleSpec.styleName) {
1230             // transform removeStyleSpec
1231             // just create a setstyle op preceding to us which removes any set style from the paragraph
1232             helperOpspec = {
1233                 optype: "SetParagraphStyle",
1234                 memberid: removeStyleSpec.memberid,
1235                 timestamp: removeStyleSpec.timestamp,
1236                 position: setParagraphStyleSpec.position,
1237                 styleName: ""
1238             };
1239             removeStyleSpecResult.unshift(helperOpspec);
1240 
1241             // transform setParagraphStyleSpec
1242             // instead of setting now remove any existing style from the paragraph
1243             setParagraphStyleSpec.styleName = "";
1244         }
1245 
1246         return {
1247             opSpecsA:  removeStyleSpecResult,
1248             opSpecsB:  setParagraphStyleSpecResult
1249         };
1250     }
1251 
1252     /**
1253      * @param {!ops.OpRemoveStyle.Spec} removeStyleSpec
1254      * @param {!ops.OpUpdateParagraphStyle.Spec} updateParagraphStyleSpec
1255      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1256      */
1257     function transformRemoveStyleUpdateParagraphStyle(removeStyleSpec, updateParagraphStyleSpec) {
1258         var setAttributes, helperOpspec,
1259             removeStyleSpecResult = [removeStyleSpec],
1260             updateParagraphStyleSpecResult = [updateParagraphStyleSpec];
1261 
1262         if (removeStyleSpec.styleFamily === "paragraph") {
1263             // transform removeStyleSpec
1264             // style brought into use by other op?
1265             setAttributes = getStyleReferencingAttributes(updateParagraphStyleSpec.setProperties, removeStyleSpec.styleName);
1266             if (setAttributes.length > 0) {
1267                 // just create a updateparagraph style op preceding to us which removes any set style from the paragraph
1268                 helperOpspec = {
1269                     optype: "UpdateParagraphStyle",
1270                     memberid: removeStyleSpec.memberid,
1271                     timestamp: removeStyleSpec.timestamp,
1272                     styleName: updateParagraphStyleSpec.styleName,
1273                     removedProperties: { attributes: setAttributes.join(',') }
1274                 };
1275                 removeStyleSpecResult.unshift(helperOpspec);
1276             }
1277 
1278             // transform updateParagraphStyleSpec
1279             // target style to update deleted by removeStyle?
1280             if (removeStyleSpec.styleName === updateParagraphStyleSpec.styleName) {
1281                 // don't touch the dead
1282                 updateParagraphStyleSpecResult = [];
1283             } else {
1284                 // otherwise drop any attributes referencing the style deleted
1285                 dropStyleReferencingAttributes(updateParagraphStyleSpec.setProperties, removeStyleSpec.styleName);
1286             }
1287         }
1288 
1289         return {
1290             opSpecsA:  removeStyleSpecResult,
1291             opSpecsB:  updateParagraphStyleSpecResult
1292         };
1293     }
1294 
1295     /**
1296      * @param {!ops.OpRemoveText.Spec} removeTextSpecA
1297      * @param {!ops.OpRemoveText.Spec} removeTextSpecB
1298      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1299      */
1300     function transformRemoveTextRemoveText(removeTextSpecA, removeTextSpecB) {
1301         var removeTextSpecAEnd = removeTextSpecA.position + removeTextSpecA.length,
1302             removeTextSpecBEnd = removeTextSpecB.position + removeTextSpecB.length,
1303             removeTextSpecAResult = [removeTextSpecA],
1304             removeTextSpecBResult = [removeTextSpecB];
1305 
1306         // B removed positions by object up to As start position?
1307         if (removeTextSpecBEnd <= removeTextSpecA.position) {
1308             // adapt A by removed position
1309             removeTextSpecA.position -= removeTextSpecB.length;
1310         // A removed positions by object up to Bs start position?
1311         } else if (removeTextSpecAEnd <= removeTextSpecB.position) {
1312             // adapt B by removed position
1313             removeTextSpecB.position -= removeTextSpecA.length;
1314         // overlapping?
1315         // (removeTextSpecBEnd <= removeTextSpecA.position above catches non-overlapping from this condition)
1316         } else if (removeTextSpecB.position < removeTextSpecAEnd) {
1317             // A removes in front of B?
1318             if (removeTextSpecA.position < removeTextSpecB.position) {
1319                 // A still to remove range at its end?
1320                 if (removeTextSpecBEnd < removeTextSpecAEnd) {
1321                     removeTextSpecA.length = removeTextSpecA.length - removeTextSpecB.length;
1322                 } else {
1323                     removeTextSpecA.length = removeTextSpecB.position - removeTextSpecA.position;
1324                 }
1325                 // B still to remove range at its end?
1326                 if (removeTextSpecAEnd < removeTextSpecBEnd) {
1327                     removeTextSpecB.position = removeTextSpecA.position;
1328                     removeTextSpecB.length = removeTextSpecBEnd - removeTextSpecAEnd;
1329                 } else {
1330                     // B completely overlapped by other, so it becomes a noop
1331                     removeTextSpecBResult = [];
1332                 }
1333             // B removes in front of or starting at same like A
1334             } else {
1335                 // B still to remove range at its end?
1336                 if (removeTextSpecAEnd < removeTextSpecBEnd) {
1337                     removeTextSpecB.length = removeTextSpecB.length - removeTextSpecA.length;
1338                 } else {
1339                     // B still to remove range at its start?
1340                     if (removeTextSpecB.position < removeTextSpecA.position) {
1341                         removeTextSpecB.length = removeTextSpecA.position - removeTextSpecB.position;
1342                     } else {
1343                         // B completely overlapped by other, so it becomes a noop
1344                         removeTextSpecBResult = [];
1345                     }
1346                 }
1347                 // A still to remove range at its end?
1348                 if (removeTextSpecBEnd < removeTextSpecAEnd) {
1349                     removeTextSpecA.position = removeTextSpecB.position;
1350                     removeTextSpecA.length = removeTextSpecAEnd - removeTextSpecBEnd;
1351                 } else {
1352                     // A completely overlapped by other, so it becomes a noop
1353                     removeTextSpecAResult = [];
1354                 }
1355             }
1356         }
1357         return {
1358             opSpecsA:  removeTextSpecAResult,
1359             opSpecsB:  removeTextSpecBResult
1360         };
1361     }
1362 
1363     /**
1364      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1365      * @param {!ops.OpSetParagraphStyle.Spec} setParagraphStyleSpec
1366      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1367      */
1368     function transformRemoveTextSetParagraphStyle(removeTextSpec, setParagraphStyleSpec) {
1369         // Removal is done entirely in some preceding paragraph
1370         if (removeTextSpec.position < setParagraphStyleSpec.position) {
1371             setParagraphStyleSpec.position -= removeTextSpec.length;
1372         }
1373 
1374         return {
1375             opSpecsA:  [removeTextSpec],
1376             opSpecsB:  [setParagraphStyleSpec]
1377         };
1378     }
1379 
1380     /**
1381      * @param {!ops.OpRemoveText.Spec} removeTextSpec
1382      * @param {!ops.OpSplitParagraph.Spec} splitParagraphSpec
1383      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1384      */
1385     function transformRemoveTextSplitParagraph(removeTextSpec, splitParagraphSpec) {
1386         var removeTextSpecEnd = removeTextSpec.position + removeTextSpec.length,
1387             helperOpspec,
1388             removeTextSpecResult = [removeTextSpec],
1389             splitParagraphSpecResult = [splitParagraphSpec];
1390 
1391         // adapt removeTextSpec
1392         if (splitParagraphSpec.position <= removeTextSpec.position) {
1393             removeTextSpec.position += 1;
1394         } else if (splitParagraphSpec.position < removeTextSpecEnd) {
1395             // we have to split the removal into two ops, before and after the insertion
1396             removeTextSpec.length = splitParagraphSpec.position - removeTextSpec.position;
1397             helperOpspec = {
1398                 optype: "RemoveText",
1399                 memberid: removeTextSpec.memberid,
1400                 timestamp: removeTextSpec.timestamp,
1401                 position: splitParagraphSpec.position + 1,
1402                 length: removeTextSpecEnd - splitParagraphSpec.position
1403             };
1404             removeTextSpecResult.unshift(helperOpspec); // helperOp first, so its position is not affected by the real op
1405         }
1406 
1407         // adapt splitParagraphSpec
1408         if (removeTextSpec.position + removeTextSpec.length <= splitParagraphSpec.position) {
1409             splitParagraphSpec.position -= removeTextSpec.length;
1410         } else if (removeTextSpec.position < splitParagraphSpec.position) {
1411             splitParagraphSpec.position = removeTextSpec.position;
1412         }
1413 
1414         if (removeTextSpec.position + removeTextSpec.length < splitParagraphSpec.sourceParagraphPosition) {
1415             // Removed text is before the source paragraph
1416             splitParagraphSpec.sourceParagraphPosition -= removeTextSpec.length;
1417         }
1418         // removeText ops can't cross over paragraph boundaries, so don't check this case
1419 
1420         return {
1421             opSpecsA:  removeTextSpecResult,
1422             opSpecsB:  splitParagraphSpecResult
1423         };
1424     }
1425 
1426     /**
1427      * Does an OT on the two passed opspecs, where they are not modified at all,
1428      * and so simply returns them in the result arrays.
1429      * @param {!Object} opSpecA
1430      * @param {!Object} opSpecB
1431      * @return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1432      */
1433     function passUnchanged(opSpecA, opSpecB) {
1434         return {
1435             opSpecsA:  [opSpecA],
1436             opSpecsB:  [opSpecB]
1437         };
1438     }
1439 
1440 
1441     var /**
1442          * This is the lower-left half of the sparse NxN matrix with all the
1443          * transformation methods on the possible pairs of ops. As the matrix
1444          * is symmetric, only that half is used. So the user of this matrix has
1445          * to ensure the proper order of opspecs on lookup and on calling the
1446          * picked transformation method.
1447          *
1448          * Each transformation method takes the two opspecs (and optionally
1449          * a flag if the first has a higher priority, in case of tie breaking
1450          * having to be done). The method returns a record with the two
1451          * resulting arrays of ops, with key names "opSpecsA" and "opSpecsB".
1452          * Those arrays could have more than the initial respective opspec
1453          * inside, in case some additional helper opspecs are needed, or be
1454          * empty if the opspec turned into a no-op in the transformation.
1455          * If a transformation is not doable, the method returns "null".
1456          *
1457          * Some operations are added onto the stack by the server, for example
1458          * AddMember, RemoveMember, and UpdateMember. These therefore need
1459          * not be transformed against each other, since the server is the
1460          * only originator of these ops. Therefore, their entries in the
1461          * matrix are missing. They do however require a passUnchanged entry
1462          * with other ops.
1463          *
1464          * Here the CC signature of each transformation method:
1465          * param {!Object} opspecA
1466          * param {!Object} opspecB
1467          * (param {!boolean} hasAPriorityOverB)  can be left out
1468          * return {?{opSpecsA:!Array.<!Object>, opSpecsB:!Array.<!Object>}}
1469          *
1470          * Empty cells in this matrix mean there is no such transformation
1471          * possible, and should be handled as if the method returns "null".
1472          *
1473          * @type {!Object.<string,!Object.<string,function(!Object,!Object,boolean=):?{opSpecsA:!Array.<!{optype:string}>, opSpecsB:!Array.<!{optype:string}>}>>}
1474          */
1475         transformations;
1476     transformations = {
1477         "AddCursor": {
1478             "AddCursor":            passUnchanged,
1479             "AddMember":            passUnchanged,
1480             "AddStyle":             passUnchanged,
1481             "ApplyDirectStyling":   passUnchanged,
1482             "InsertText":           passUnchanged,
1483             "MergeParagraph":       passUnchanged,
1484             "MoveCursor":           passUnchanged,
1485             "RemoveCursor":         passUnchanged,
1486             "RemoveMember":         passUnchanged,
1487             "RemoveStyle":          passUnchanged,
1488             "RemoveText":           passUnchanged,
1489             "SetParagraphStyle":    passUnchanged,
1490             "SplitParagraph":       passUnchanged,
1491             "UpdateMember":         passUnchanged,
1492             "UpdateMetadata":       passUnchanged,
1493             "UpdateParagraphStyle": passUnchanged
1494         },
1495         "AddMember": {
1496             "AddStyle":             passUnchanged,
1497             "InsertText":           passUnchanged,
1498             "MergeParagraph":       passUnchanged,
1499             "MoveCursor":           passUnchanged,
1500             "RemoveCursor":         passUnchanged,
1501             "RemoveStyle":          passUnchanged,
1502             "RemoveText":           passUnchanged,
1503             "SetParagraphStyle":    passUnchanged,
1504             "SplitParagraph":       passUnchanged,
1505             "UpdateMetadata":       passUnchanged,
1506             "UpdateParagraphStyle": passUnchanged
1507         },
1508         "AddStyle": {
1509             "AddStyle":             passUnchanged,
1510             "ApplyDirectStyling":   passUnchanged,
1511             "InsertText":           passUnchanged,
1512             "MergeParagraph":       passUnchanged,
1513             "MoveCursor":           passUnchanged,
1514             "RemoveCursor":         passUnchanged,
1515             "RemoveMember":         passUnchanged,
1516             "RemoveStyle":          transformAddStyleRemoveStyle,
1517             "RemoveText":           passUnchanged,
1518             "SetParagraphStyle":    passUnchanged,
1519             "SplitParagraph":       passUnchanged,
1520             "UpdateMember":         passUnchanged,
1521             "UpdateMetadata":       passUnchanged,
1522             "UpdateParagraphStyle": passUnchanged
1523         },
1524         "ApplyDirectStyling": {
1525             "ApplyDirectStyling":   transformApplyDirectStylingApplyDirectStyling,
1526             "InsertText":           transformApplyDirectStylingInsertText,
1527             "MergeParagraph":       transformApplyDirectStylingMergeParagraph,
1528             "MoveCursor":           passUnchanged,
1529             "RemoveCursor":         passUnchanged,
1530             "RemoveStyle":          passUnchanged,
1531             "RemoveText":           transformApplyDirectStylingRemoveText,
1532             "SetParagraphStyle":    passUnchanged,
1533             "SplitParagraph":       transformApplyDirectStylingSplitParagraph,
1534             "UpdateMetadata":       passUnchanged,
1535             "UpdateParagraphStyle": passUnchanged
1536         },
1537         "InsertText": {
1538             "InsertText":           transformInsertTextInsertText,
1539             "MergeParagraph":       transformInsertTextMergeParagraph,
1540             "MoveCursor":           transformInsertTextMoveCursor,
1541             "RemoveCursor":         passUnchanged,
1542             "RemoveMember":         passUnchanged,
1543             "RemoveStyle":          passUnchanged,
1544             "RemoveText":           transformInsertTextRemoveText,
1545             "SetParagraphStyle":    transformInsertTextSetParagraphStyle,
1546             "SplitParagraph":       transformInsertTextSplitParagraph,
1547             "UpdateMember":         passUnchanged,
1548             "UpdateMetadata":       passUnchanged,
1549             "UpdateParagraphStyle": passUnchanged
1550         },
1551         "MergeParagraph": {
1552             "MergeParagraph":       transformMergeParagraphMergeParagraph,
1553             "MoveCursor":           transformMergeParagraphMoveCursor,
1554             "RemoveCursor":         passUnchanged,
1555             "RemoveMember":         passUnchanged,
1556             "RemoveStyle":          passUnchanged,
1557             "RemoveText":           transformMergeParagraphRemoveText,
1558             "SetParagraphStyle":    transformMergeParagraphSetParagraphStyle,
1559             "SplitParagraph":       transformMergeParagraphSplitParagraph,
1560             "UpdateMember":         passUnchanged,
1561             "UpdateMetadata":       passUnchanged,
1562             "UpdateParagraphStyle": passUnchanged
1563         },
1564         "MoveCursor": {
1565             "MoveCursor":           passUnchanged,
1566             "RemoveCursor":         transformMoveCursorRemoveCursor,
1567             "RemoveMember":         passUnchanged,
1568             "RemoveStyle":          passUnchanged,
1569             "RemoveText":           transformMoveCursorRemoveText,
1570             "SetParagraphStyle":    passUnchanged,
1571             "SplitParagraph":       transformMoveCursorSplitParagraph,
1572             "UpdateMember":         passUnchanged,
1573             "UpdateMetadata":       passUnchanged,
1574             "UpdateParagraphStyle": passUnchanged
1575         },
1576         "RemoveCursor": {
1577             "RemoveCursor":         transformRemoveCursorRemoveCursor,
1578             "RemoveMember":         passUnchanged,
1579             "RemoveStyle":          passUnchanged,
1580             "RemoveText":           passUnchanged,
1581             "SetParagraphStyle":    passUnchanged,
1582             "SplitParagraph":       passUnchanged,
1583             "UpdateMember":         passUnchanged,
1584             "UpdateMetadata":       passUnchanged,
1585             "UpdateParagraphStyle": passUnchanged
1586         },
1587         "RemoveMember": {
1588             "RemoveStyle":          passUnchanged,
1589             "RemoveText":           passUnchanged,
1590             "SetParagraphStyle":    passUnchanged,
1591             "SplitParagraph":       passUnchanged,
1592             "UpdateMetadata":       passUnchanged,
1593             "UpdateParagraphStyle": passUnchanged
1594         },
1595         "RemoveStyle": {
1596             "RemoveStyle":          transformRemoveStyleRemoveStyle,
1597             "RemoveText":           passUnchanged,
1598             "SetParagraphStyle":    transformRemoveStyleSetParagraphStyle,
1599             "SplitParagraph":       passUnchanged,
1600             "UpdateMember":         passUnchanged,
1601             "UpdateMetadata":       passUnchanged,
1602             "UpdateParagraphStyle": transformRemoveStyleUpdateParagraphStyle
1603         },
1604         "RemoveText": {
1605             "RemoveText":           transformRemoveTextRemoveText,
1606             "SetParagraphStyle":    transformRemoveTextSetParagraphStyle,
1607             "SplitParagraph":       transformRemoveTextSplitParagraph,
1608             "UpdateMember":         passUnchanged,
1609             "UpdateMetadata":       passUnchanged,
1610             "UpdateParagraphStyle": passUnchanged
1611         },
1612         "SetParagraphStyle": {
1613             "SetParagraphStyle":    transformSetParagraphStyleSetParagraphStyle,
1614             "SplitParagraph":       transformSetParagraphStyleSplitParagraph,
1615             "UpdateMember":         passUnchanged,
1616             "UpdateMetadata":       passUnchanged,
1617             "UpdateParagraphStyle": passUnchanged
1618         },
1619         "SplitParagraph": {
1620             "SplitParagraph":       transformSplitParagraphSplitParagraph,
1621             "UpdateMember":         passUnchanged,
1622             "UpdateMetadata":       passUnchanged,
1623             "UpdateParagraphStyle": passUnchanged
1624         },
1625         "UpdateMember": {
1626             "UpdateMetadata":       passUnchanged,
1627             "UpdateParagraphStyle": passUnchanged
1628         },
1629         "UpdateMetadata": {
1630             "UpdateMetadata":       transformUpdateMetadataUpdateMetadata,
1631             "UpdateParagraphStyle": passUnchanged
1632         },
1633         "UpdateParagraphStyle": {
1634             "UpdateParagraphStyle": transformUpdateParagraphStyleUpdateParagraphStyle
1635         }
1636     };
1637 
1638     this.passUnchanged = passUnchanged;
1639 
1640     /**
1641      * @param {!Object.<!string,!Object.<!string,!Function>>}  moreTransformations
1642      * @return {undefined}
1643      */
1644     this.extendTransformations = function (moreTransformations) {
1645         Object.keys(moreTransformations).forEach(function (optypeA) {
1646             var moreTransformationsOptypeAMap = moreTransformations[optypeA],
1647                 /**@type{!Object.<string,!Function>}*/
1648                 optypeAMap,
1649                 isExtendingOptypeAMap = transformations.hasOwnProperty(optypeA);
1650 
1651             runtime.log((isExtendingOptypeAMap ? "Extending" : "Adding") + " map for optypeA: " + optypeA);
1652             if (!isExtendingOptypeAMap) {
1653                 transformations[optypeA] = {};
1654             }
1655             optypeAMap = transformations[optypeA];
1656 
1657             Object.keys(moreTransformationsOptypeAMap).forEach(function (optypeB) {
1658                 var isOverwritingOptypeBEntry = optypeAMap.hasOwnProperty(optypeB);
1659                 runtime.assert(optypeA <= optypeB, "Wrong order:" + optypeA + ", " + optypeB);
1660                 runtime.log("  " + (isOverwritingOptypeBEntry ? "Overwriting" : "Adding") + " entry for optypeB: " + optypeB);
1661                 optypeAMap[optypeB] = moreTransformationsOptypeAMap[optypeB];
1662             });
1663         });
1664     };
1665 
1666     /**
1667      * TODO: priority could be read from op spec, here be an attribute from-server
1668      * @param {!{optype:string}} opSpecA op with lower priority in case of tie breaking
1669      * @param {!{optype:string}} opSpecB op with higher priority in case of tie breaking
1670      * @return {?{opSpecsA:!Array.<!{optype:string}>,
1671      *            opSpecsB:!Array.<!{optype:string}>}}
1672      */
1673     this.transformOpspecVsOpspec = function (opSpecA, opSpecB) {
1674         var isOptypeAAlphaNumericSmaller = (opSpecA.optype <= opSpecB.optype),
1675             helper, transformationFunctionMap, transformationFunction, result;
1676 
1677 runtime.log("Crosstransforming:");
1678 runtime.log(runtime.toJson(opSpecA));
1679 runtime.log(runtime.toJson(opSpecB));
1680 
1681         // switch order if needed, to match the mirrored part of the matrix
1682         if (!isOptypeAAlphaNumericSmaller) {
1683             helper = opSpecA;
1684             opSpecA = opSpecB;
1685             opSpecB = helper;
1686         }
1687         // look up transformation method
1688         transformationFunctionMap = transformations[opSpecA.optype];
1689         transformationFunction = transformationFunctionMap && transformationFunctionMap[opSpecB.optype];
1690 
1691         // transform
1692         if (transformationFunction) {
1693             result = transformationFunction(opSpecA, opSpecB, !isOptypeAAlphaNumericSmaller);
1694             if (!isOptypeAAlphaNumericSmaller && result !== null) {
1695                 // switch result back
1696                 result = {
1697                     opSpecsA:  result.opSpecsB,
1698                     opSpecsB:  result.opSpecsA
1699                 };
1700             }
1701         } else {
1702             result = null;
1703         }
1704 runtime.log("result:");
1705 if (result) {
1706 runtime.log(runtime.toJson(result.opSpecsA));
1707 runtime.log(runtime.toJson(result.opSpecsB));
1708 } else {
1709 runtime.log("null");
1710 }
1711         return result;
1712     };
1713 };
1714