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 gui, runtime*/
 26 
 27 /**
 28  * This class attempts to implement undo/redo behaviour identical
 29  * to how LibreOffice behaves.
 30  *
 31  * State iteration rules are:
 32  * - Multiple text inserts in the same direction are treated as one state
 33  * - Multiple text removes in the same direction are treated as one state
 34  * - An Undo state always consumes all trailing cursor move operations
 35  * - An edit operation cannot follow non-edit operations. A state can
 36  *      start with non-edit operations if it contains no further edit ops.
 37  * @constructor
 38  */
 39 gui.UndoStateRules = function UndoStateRules() {
 40     "use strict";
 41 
 42     /**
 43      * Return the first element from the end of the array that matches the supplied predicate.
 44      * Each subsequent call to previous will return the next element from the end of the array
 45      * that matches the predicate.
 46      * @constructor
 47      * @param {!Array.<!ops.Operation>} array
 48      * @param {!function(!ops.Operation):!boolean} predicate
 49      */
 50     function ReverseIterator(array, predicate) {
 51         var index = array.length;
 52 
 53         /**
 54          * Return the previous element in the array that matches the predicate
 55          * @return {?ops.Operation} Returns null when no more elements in the array match the predicate
 56          */
 57         this.previous = function () {
 58             for (index = index - 1; index >= 0; index -= 1) {
 59                 if (predicate(array[index])) {
 60                     return array[index];
 61                 }
 62             }
 63             return null;
 64         };
 65     }
 66 
 67     /**
 68      * @param {!ops.Operation} op
 69      * @return {string}
 70      */
 71     function getOpType(op) {
 72         return op.spec().optype;
 73     }
 74 
 75     /**
 76      * @param {!ops.Operation} op
 77      * @return {number|undefined}
 78      */
 79     function getOpPosition(op) {
 80         var key = "position",
 81             spec = op.spec(),
 82             value;
 83         if (spec.hasOwnProperty(key)) {
 84             value = /**@type{number}*/(spec[key]);
 85         }
 86         return value;
 87     }
 88 
 89     /**
 90      * Returns true if the supplied operation
 91      * is considered an editing operation.
 92      * @param {!ops.Operation} op
 93      * @return {!boolean} Returns true if the supplied op is an edit operation
 94      */
 95     function isEditOperation(op) {
 96         return op.isEdit;
 97     }
 98     this.isEditOperation = isEditOperation;
 99 
100     /**
101      * Returns true if the supplied optype is allowed to
102      * aggregate multiple operations in a single undo or redo state
103      * @param {!ops.Operation} op
104      * @return {!boolean}
105      */
106     function canAggregateOperation(op) {
107         switch (getOpType(op)) {
108         case "RemoveText":
109         case "InsertText":
110             return true;
111         default:
112             return false;
113         }
114     }
115 
116     /**
117      * Returns true if the newly supplied operation is continuing
118      * in the same direction of travel as the recent edit operations
119      * @param {!ops.Operation} thisOp
120      * @param {!ops.Operation} lastEditOp
121      * @param {!ops.Operation} secondLastEditOp
122      * @return {!boolean}
123      */
124     function isSameDirectionOfTravel(thisOp, lastEditOp, secondLastEditOp) {
125         // Note, the operations in the recent queue are most
126         // recent to least recent. As such, the direction order
127         // should be thisPos => existing2 => existing1
128         var thisPosition = getOpPosition(thisOp),
129             lastPosition = getOpPosition(lastEditOp),
130             secondLastPosition = getOpPosition(secondLastEditOp),
131             diffLastToSecondLast = lastPosition - secondLastPosition,
132             diffThisToLast = thisPosition - lastPosition;
133         // Next, the tricky part... determining the direction of travel
134         // Each aggregate operation can have two directions of travel:
135         // RemoveText:
136         // - delete via backspace - direction will be -1 as cursor moves back
137         // - delete via delete key - direction will be 0 as cursor doesn't move
138         // InsertText:
139         // - prepend text - direction will be 0 as cursor doesn't move
140         // - append text - direction will be 1 as cursor moves forward
141 
142         return diffThisToLast === diffLastToSecondLast;
143     }
144 
145     /**
146      * Returns true if the two operations are considered adjacent.
147      * @param {!ops.Operation} thisOp
148      * @param {!ops.Operation} lastEditOp
149      * @return {!boolean}
150      */
151     function isAdjacentOperation(thisOp, lastEditOp) {
152         var positionDifference = getOpPosition(thisOp) - getOpPosition(lastEditOp);
153         // RemoveText:
154         // - delete via backspace - direction will be -1 as cursor moves back
155         // - delete via delete key - direction will be 0 as cursor doesn't move
156         // InsertText:
157         // - prepend text - direction will be 0 as cursor doesn't move
158         // - append text - direction will be 1 as cursor moves forward
159         return positionDifference === 0 || Math.abs(positionDifference) === 1;
160     }
161 
162     /**
163      *
164      * @param {!ops.Operation} thisOp
165      * @param {!ops.Operation} lastEditOp
166      * @param {?ops.Operation} secondLastEditOp
167      * @return {!boolean}
168      */
169     function continuesOperations(thisOp, lastEditOp, secondLastEditOp) {
170         if (!secondLastEditOp) {
171             // No previous edit operations, so can't calculate a direction of travel.
172             // Just check new op is adjacent to existing op
173             return isAdjacentOperation(thisOp, lastEditOp);
174         }
175         return isSameDirectionOfTravel(thisOp, lastEditOp, secondLastEditOp);
176     }
177 
178     /**
179      * Returns true if thisOp can be grouped together with the most recent edit operations.
180      *
181      * For an operation to be considered continuous it must:
182      * - Be of a type that supports aggregation (e.g., insert text or remove text)
183      * - Be of the same type as the most recent edit operation
184      * - Be considered adjacent (and in the same direction as) the most recent edit operation
185      *
186      * @param {!ops.Operation} thisOp
187      * @param {!Array.<!ops.Operation>} recentOperations
188      * @return {!boolean}
189      */
190     function continuesMostRecentEditOperation(thisOp, recentOperations) {
191         var thisOpType = getOpType(thisOp),
192             editOpsFinder = new ReverseIterator(recentOperations, isEditOperation),
193             lastEditOp = editOpsFinder.previous();
194 
195         runtime.assert(Boolean(lastEditOp), "No edit operations found in state");
196         if (thisOpType === getOpType(/**@type{!ops.Operation}*/(lastEditOp))) {
197             // Operation type is identical, so check if these operations are continuous
198             return continuesOperations(thisOp, /**@type{!ops.Operation}*/(lastEditOp), editOpsFinder.previous());
199         }
200         return false;
201     }
202 
203     /**
204      * Returns true if thisOp can be grouped together with the most recent edit operations group.
205      *
206      * For an operation to be considered continuous it must:
207      * - Be of a type that supports aggregation (e.g., insert text or remove text)
208      * - Be continuous with the most recent edit operation of the same type in the most recent operations group
209      *   (see isContinuousWithExistingOperation for the definition of "continuous")
210      *
211      * @param {!ops.Operation} thisOp
212      * @param {!Array.<!ops.Operation>} recentOperations
213      * @return {!boolean}
214      */
215     function continuesMostRecentEditGroup(thisOp, recentOperations) {
216         var thisOpType = getOpType(thisOp),
217             editOpsFinder = new ReverseIterator(recentOperations, isEditOperation),
218             candidateOp = editOpsFinder.previous(),
219             lastEditOp,
220             secondLastEditOp = null,
221             inspectedGroupsCount,
222             groupId;
223 
224         runtime.assert(Boolean(candidateOp), "No edit operations found in state");
225         groupId = candidateOp.group;
226         runtime.assert(groupId !== undefined, "Operation has no group");
227         inspectedGroupsCount = 1; // Need to keep track of how many edit groups have been inspected
228 
229         // Check if the current operation continues any operation in the latest group
230         while (candidateOp && candidateOp.group === groupId) {
231             if (thisOpType === getOpType(candidateOp)) {
232                 // A matching edit operation was found in the most recent edit group
233                 lastEditOp = candidateOp;
234                 break;
235             }
236             candidateOp = editOpsFinder.previous();
237         }
238 
239         if (lastEditOp) {
240             // Now try and find a second operation of the same type in either of the most recent two edit groups
241             candidateOp = editOpsFinder.previous();
242             while (candidateOp) {
243                 if (candidateOp.group !== groupId) {
244                     if (inspectedGroupsCount === 2) {
245                         // No second compatible op was found within two edit groups, so abandon searching for more
246                         // and check continuity against lastEditOp only
247                         break;
248                     }
249                     groupId = candidateOp.group;
250                     inspectedGroupsCount += 1;
251                 }
252                 if (thisOpType === getOpType(candidateOp)) {
253                     // Found an operation of the same type within the last two edit groups on the stack
254                     secondLastEditOp = candidateOp;
255                     break;
256                 }
257                 candidateOp = editOpsFinder.previous();
258             }
259             return continuesOperations(thisOp, /**@type{!ops.Operation}*/(lastEditOp), secondLastEditOp);
260         }
261         return false;
262     }
263 
264     /**
265      * Returns true if the provided operation is part of the existing
266      * set of operations according to the undo rules
267      * @param {!ops.Operation} operation
268      * @param {!Array.<!ops.Operation>} recentOperations
269      * @return {!boolean}
270      */
271     function isPartOfOperationSet(operation, recentOperations) {
272         var areOperationsGrouped = operation.group !== undefined, // Expect groups to be consistently used (if in use at all)
273             lastOperation;
274         if (!isEditOperation(operation)) {
275             // Non-edit operations always get appended to the existing undo state
276             // this covers things such as move cursor ops
277             return true;
278         }
279         if (recentOperations.length === 0) {
280             // This is the first operation of a pristine state
281             return true;
282         }
283         lastOperation = recentOperations[recentOperations.length - 1];
284         if (areOperationsGrouped && operation.group === lastOperation.group) {
285             // Operation groups match, so these were queued as a group
286             return true;
287         }
288         if (canAggregateOperation(operation) && recentOperations.some(isEditOperation)) {
289             // The are existing edit operations. Check if the current op can be combined with existing operations
290             // E.g., multiple insert text or remove text ops
291             if (areOperationsGrouped) {
292                 return continuesMostRecentEditGroup(operation, recentOperations);
293             }
294             return continuesMostRecentEditOperation(operation, recentOperations);
295         }
296         // The following are all true at this point:
297         // - new operation is an edit operation (check 1)
298         // - existing undo state has at least one existing operation (check 2)
299         // - new operation is not part of most recent operation group (check 3)
300         // - new operation is not continuous with the existing edit operations (check 4 + 5)
301         return false;
302     }
303     this.isPartOfOperationSet = isPartOfOperationSet;
304 };
305