1 /**
  2  * Copyright (C) 2010-2014 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, core, ops, Node*/
 26 
 27 (function() {
 28     "use strict";
 29     // Multiple cached translators may exist in the same runtime. Therefore, each node id should
 30     // be globally unique, so they can be safely re-used by multiple translators
 31     var /**@type{number}*/
 32         nextNodeId = 0;
 33 
 34     /**
 35      * Implementation of a step to DOM point lookup cache.
 36      *
 37      * A cache point ("bookmark") is created each time updateBookmark is called, saving the number of steps from the root
 38      * node to the bookmarked node. This cached point is linked to the node via a unique identifier.
 39      *
 40      * The cache works by tracking "damage" to it's bookmarks (via steps inserted & removal). As re-iteration over the
 41      * damaged sections occur, the bookmarks are updated, and the damage repaired.
 42      *
 43      * A visual example of the cache during various states is as follows:
 44      * legend: -=good bookmark, x=damaged bookmark, !=indeterminate bookmark, ?=requested step,
 45      *          @=current iterator position
 46      * 
 47      * [--------------] <-- cache before steps change
 48      * [----x!!!!!!!!!] <-- damage occurs (e.g., a step is deleted) which means all bookmarks after the damage point are
 49      *                      now indeterminate as their step location is now outdated
 50      * [----xxxxxxxxxx] <-- trailing bookmarks now considered "damaged", and will not be used until they can be repaired
 51      * [---@xxxx?xxxxx] <-- when a bookmark is requested for step in the damaged region, the last undamaged bookmark will
 52      *                      be returned instead. The consumer of this interface already knows additional iteration may
 53      *                      be necessary to reach the desired step count, so this case is no different than if the cache
 54      *                      was unprimed.
 55      * [------@xxxxxxx] <-- as re-iteration over the doc occurs, bookmark positions are updated and the damage start
 56      *                      point is moved along to the next damaged node
 57      *
 58      * This cache depends on OdtStepsTranslator.handleStepsInserted & handleStepsRemoved being called at the step of change,
 59      * along with information about the region that has changed. The cache is able to cope with nodes being cloned, as
 60      * long as the position of change is correctly reported.
 61      *
 62      * However, this implementation will NOT cope with nodes being re-ordered, even if a change event is reported.
 63      * This is because the cache relies on the nodes order remaining fixed as long as they are in the DOM.
 64      * If node reordering is desired, it can be achieved through cloning the node into the new position and removing
 65      * the original node (the clone will be detected and rectified).
 66      *
 67      * @constructor
 68      * @param {!Element} rootElement
 69      * @param {!number} bucketSize  Minimum number of steps between cache points
 70      * @param {!function(!number, !core.PositionIterator):undefined} restoreBookmarkPosition Fine-tune the iterator position after
 71      *      it is set to a specific bookmark location.
 72      */
 73     ops.StepsCache = function StepsCache(rootElement, bucketSize, restoreBookmarkPosition) {
 74         var coordinatens = "urn:webodf:names:steps",
 75             // Note, our coding standards usually require a key of !string for a dictionary.
 76             // As I'm often assigning numbers as well (which JS quite happily converts for me)
 77             // using both types saves me a lot of extra typing
 78             /**@type{!Object.<(!string|!number), !ops.StepsCache.Bookmark>}*/
 79             stepToDomPoint = {},
 80             /**@type{!Object.<!string, !ops.StepsCache.Bookmark>}*/
 81             nodeToBookmark = {},
 82             domUtils = new core.DomUtils(),
 83             /**@type{!RootBookmark}*/
 84             basePoint,
 85             /**@type{!number|undefined}*/
 86             lastUndamagedCacheStep,
 87             /**
 88              * @const
 89              * @type {!number}
 90              */
 91             DOCUMENT_POSITION_FOLLOWING = Node.DOCUMENT_POSITION_FOLLOWING,
 92             /**
 93              * @const
 94              * @type {!number}
 95              */
 96             DOCUMENT_POSITION_PRECEDING = Node.DOCUMENT_POSITION_PRECEDING,
 97             verifyCache;
 98 
 99         /**
100          * Bookmark tied to a specific node
101          * @constructor
102          * @param {!string} nodeId
103          * @param {!Element} bookmarkNode
104          *
105          * @implements {ops.StepsCache.Bookmark}
106          */
107         function NodeBookmark(nodeId, bookmarkNode) {
108             var self = this;
109             this.nodeId = nodeId;
110             this.steps = -1;
111             this.node = bookmarkNode;
112             this.nextBookmark = null;
113             this.previousBookmark = null;
114 
115             /**
116              * @param {!core.PositionIterator} iterator
117              * @return {undefined}
118              */
119             this.setIteratorPosition = function(iterator) {
120                 iterator.setPositionBeforeElement(bookmarkNode);
121                 restoreBookmarkPosition(self.steps, iterator);
122             };
123         }
124 
125         /**
126          * Bookmark indicating the first walkable position in the document
127          * @constructor
128          * @param {!string} nodeId
129          * @param {!number} steps
130          * @param {!Node} rootNode
131          *
132          * @implements {ops.StepsCache.Bookmark}
133          */
134         function RootBookmark(nodeId, steps, rootNode) {
135             var self = this;
136             this.nodeId = nodeId;
137             this.steps = steps;
138             this.node = rootNode;
139             this.nextBookmark = null;
140             this.previousBookmark = null;
141 
142             /**
143              * @param {!core.PositionIterator} iterator
144              * @return {undefined}
145              */
146             this.setIteratorPosition = function (iterator) {
147                 iterator.setUnfilteredPosition(rootNode, 0);
148                 restoreBookmarkPosition(self.steps, iterator);
149             };
150         }
151 
152         /**
153          * Return a summary string of the supplied bookmark node id(s)
154          * @param {!ops.StepsCache.Bookmark} bookmark1
155          * @param {?ops.StepsCache.Bookmark=} bookmark2
156          * @return {!string}
157          */
158         function inspectBookmarks(bookmark1, bookmark2) {
159             var parts = "[" + bookmark1.nodeId;
160             if (bookmark2) {
161                 parts += " => " + bookmark2.nodeId;
162             }
163             return parts + "]";
164         }
165 
166         /**
167          * Returns true if the specified bookmark is undamaged
168          * @param {!ops.StepsCache.Bookmark} bookmark
169          * @return {!boolean}
170          */
171         function isUndamagedBookmark(bookmark) {
172             return lastUndamagedCacheStep === undefined
173                 || bookmark === basePoint
174                 || bookmark.steps <= lastUndamagedCacheStep;
175         }
176 
177         /**
178          * Run a series of verification checks against the complete cache to ensure it is operating
179          * correctly. Note, this is VERY expensive, and should only be done when attempting to diagnose
180          * caching problems
181          * @return {undefined}
182          */
183         function verifyCacheImpl() {
184             var bookmark = basePoint,
185                 previousBookmark,
186                 nextBookmark,
187                 documentPosition,
188                 loopCheck = new core.LoopWatchDog(0, 100000),
189                 /**@type{!Object.<!string, !string>}*/
190                 stepToDomPointNodeIds = {};
191 
192             while (bookmark) {
193                 loopCheck.check();
194                 previousBookmark = bookmark.previousBookmark;
195                 if (previousBookmark) {
196                     // Make sure previous => current chain is intact
197                     runtime.assert(previousBookmark.nextBookmark === bookmark,
198                         "Broken bookmark link to previous @" + inspectBookmarks(previousBookmark, bookmark));
199                 } else {
200                     // If there is no previous, ensure this is the basePoint bookmark
201                     runtime.assert(bookmark === basePoint, "Broken bookmark link @" + inspectBookmarks(bookmark));
202                     runtime.assert(isUndamagedBookmark(basePoint), "Base point is damaged @" + inspectBookmarks(bookmark));
203                 }
204                 nextBookmark = bookmark.nextBookmark;
205                 if (nextBookmark) {
206                     // Make sure current => next chain is intact
207                     runtime.assert(nextBookmark.previousBookmark === bookmark,
208                         "Broken bookmark link to next @" + inspectBookmarks(bookmark, nextBookmark));
209                 }
210 
211                 if (isUndamagedBookmark(bookmark)) {
212                     runtime.assert(domUtils.containsNode(rootElement, bookmark.node),
213                         "Disconnected node is being reported as undamaged @" + inspectBookmarks(bookmark));
214                     if (previousBookmark) {
215                         documentPosition = bookmark.node.compareDocumentPosition(previousBookmark.node);
216                         /*jslint bitwise:true*/
217                         runtime.assert(documentPosition === 0 || (documentPosition & DOCUMENT_POSITION_PRECEDING) !== 0,
218                             "Bookmark order with previous does not reflect DOM order @" + inspectBookmarks(previousBookmark, bookmark));
219                         /*jslint bitwise:false*/
220                     }
221                     if (nextBookmark) {
222                         if (domUtils.containsNode(rootElement, nextBookmark.node)) {
223                             documentPosition = bookmark.node.compareDocumentPosition(nextBookmark.node);
224                             /*jslint bitwise:true*/
225                             runtime.assert(documentPosition === 0 || (documentPosition & DOCUMENT_POSITION_FOLLOWING) !== 0,
226                                 "Bookmark order with next does not reflect DOM order @" + inspectBookmarks(bookmark, nextBookmark));
227                             /*jslint bitwise:false*/
228                         }
229                     }
230                 }
231 
232                 bookmark = bookmark.nextBookmark;
233             }
234 
235             Object.keys(stepToDomPoint).forEach(function(step) {
236                 var domPointBookmark = stepToDomPoint[step];
237                 if (lastUndamagedCacheStep === undefined || step <= lastUndamagedCacheStep) {
238                     runtime.assert(domPointBookmark.steps <= step, "Bookmark step of " + domPointBookmark.steps +
239                         " exceeds cached step lookup for " + step + " @" + inspectBookmarks(domPointBookmark));
240                 }
241 
242                 runtime.assert(stepToDomPointNodeIds.hasOwnProperty(domPointBookmark.nodeId) === false,
243                         "Bookmark " + inspectBookmarks(domPointBookmark) + " appears twice in cached step lookup at steps " +
244                         stepToDomPointNodeIds[domPointBookmark.nodeId] + " and " + step);
245                 stepToDomPointNodeIds[domPointBookmark.nodeId] = step;
246             });
247         }
248 
249         /**
250          * Returns the closest quantized step at or before the requested step
251          * @param {!number} steps
252          * @return {!number}
253          */
254         function getBucket(steps) {
255             return Math.floor(steps / bucketSize) * bucketSize;
256         }
257 
258         /**
259          * Returns the closest quantized step at or just after the requested step
260          * @param {!number} steps
261          * @return {!number}
262          */
263         function getDestinationBucket(steps) {
264             return Math.ceil(steps / bucketSize) * bucketSize;
265         }
266 
267         /**
268          * @param {!Element} node
269          * @return {undefined}
270          */
271         function clearNodeId(node) {
272             node.removeAttributeNS(coordinatens, "nodeId");
273         }
274 
275         /**
276          * @param {!Node} node
277          * @return {!string}
278          */
279         function getNodeId(node) {
280             var id = "";
281             if (node.nodeType === Node.ELEMENT_NODE) {
282                 id = /**@type{!Element}*/(node).getAttributeNS(coordinatens, "nodeId") || "";
283             }
284             return id;
285         }
286 
287         /**
288          * @param {!Element} node
289          * @return {!string}
290          */
291         function setNodeId(node) {
292             var nodeId = nextNodeId.toString();
293             node.setAttributeNS(coordinatens, "nodeId", nodeId);
294             nextNodeId += 1;
295             return nodeId;
296         }
297 
298         /**
299          * The element might have been cloned from another part of the document and have a stale or duplicate
300          * nodeId
301          * @param {!Node} node
302          * @param {!ops.StepsCache.Bookmark} bookmark
303          * @return {!boolean} True if the bookmark is actually for the supplied node
304          */
305         function isValidBookmarkForNode(node, bookmark) {
306             return bookmark.node === node;
307         }
308 
309         /**
310          * Fetches (or creates) a bookmark for the specified node.
311          *
312          * @param {!Element} node
313          * @return {!ops.StepsCache.Bookmark}
314          */
315         function getNodeBookmark(node) {
316             var nodeId = getNodeId(node) || setNodeId(node),
317                 existingBookmark;
318             existingBookmark = nodeToBookmark[nodeId];
319             if (!existingBookmark) {
320                 existingBookmark = nodeToBookmark[nodeId] = new NodeBookmark(nodeId, node);
321             } else if (!isValidBookmarkForNode(node, existingBookmark)) {
322                 runtime.log("Cloned node detected. Creating new bookmark");
323                 nodeId = setNodeId(node);
324                 existingBookmark = nodeToBookmark[nodeId] = new NodeBookmark(nodeId, node);
325             }
326             return existingBookmark;
327         }
328 
329         /**
330          * Returns the closest undamaged bookmark before or at the specified step
331          * @param {!number} steps
332          * @return {!ops.StepsCache.Bookmark}
333          */
334         function getClosestBookmark(steps) {
335             var cacheBucket,
336                 cachePoint,
337                 loopGuard = new core.LoopWatchDog(0, 10000);
338 
339             // This function promises to return an undamaged bookmark at all times.
340             // Easiest way to ensure this is don't allow requests to damaged sections
341             // of the cache.
342             if (lastUndamagedCacheStep !== undefined && steps > lastUndamagedCacheStep) {
343                 steps = lastUndamagedCacheStep;
344             }
345             cacheBucket = getBucket(steps);
346 
347             while (!cachePoint && cacheBucket >= 0) {
348                 cachePoint = stepToDomPoint[cacheBucket];
349                 cacheBucket -= bucketSize;
350             }
351 
352             cachePoint = cachePoint || basePoint;
353             while (cachePoint.nextBookmark && cachePoint.nextBookmark.steps <= steps) {
354                 loopGuard.check();
355                 cachePoint = cachePoint.nextBookmark;
356             }
357             runtime.assert(steps === -1 || cachePoint.steps <= steps,
358                     "Bookmark @" + inspectBookmarks(cachePoint) + " at step " + cachePoint.steps +
359                     " exceeds requested step of " + steps);
360             return cachePoint;
361         }
362 
363         /**
364          * Returns the closest undamaged bookmark before (or equal to) the supplied bookmark
365          * @param {!ops.StepsCache.Bookmark} bookmark
366          * @return {!ops.StepsCache.Bookmark}
367          */
368         function getUndamagedBookmark(bookmark) {
369             // Based on logic in the repairCacheUpToStep, a damaged bookmark is guaranteed to have it's
370             // steps moved beyond the damage point. This makes it simple to check if the bookmark is
371             // in the damaged region, and return the last undamaged one if it is.
372             if (lastUndamagedCacheStep !== undefined && bookmark.steps > lastUndamagedCacheStep) {
373                 bookmark = getClosestBookmark(lastUndamagedCacheStep);
374             }
375             return bookmark;
376         }
377 
378         /**
379          * Remove a bookmark from the cache chain
380          * @param {!ops.StepsCache.Bookmark} currentBookmark
381          * @return {undefined}
382          */
383         function removeBookmark(currentBookmark) {
384             if (currentBookmark.previousBookmark) {
385                 currentBookmark.previousBookmark.nextBookmark = currentBookmark.nextBookmark;
386             }
387 
388             if (currentBookmark.nextBookmark) {
389                 currentBookmark.nextBookmark.previousBookmark = currentBookmark.previousBookmark;
390             }
391         }
392 
393         /**
394          * Returns true if the newBookmark is already directly on or after the previous bookmark
395          * @param {!ops.StepsCache.Bookmark} previousBookmark
396          * @param {!ops.StepsCache.Bookmark} newBookmark
397          * @return {!boolean}
398          */
399         function isAlreadyInOrder(previousBookmark, newBookmark) {
400             return previousBookmark === newBookmark || previousBookmark.nextBookmark === newBookmark;
401         }
402 
403         /**
404          * Insert a bookmark into the cache chain just after the previous bookmark
405          * @param {!ops.StepsCache.Bookmark} previousBookmark
406          * @param {!ops.StepsCache.Bookmark} newBookmark
407          * @return {undefined}
408          */
409         function insertBookmark(previousBookmark, newBookmark) {
410             var nextBookmark;
411             // Check if the newBookmark is already in the chain at the correct location. Don't bother updating
412             // if it is in place.
413             if (!isAlreadyInOrder(previousBookmark, newBookmark)) {
414                 if (previousBookmark.steps === newBookmark.steps) {
415                     // It is valid for multiple bookmarks to share the same step.
416                     // In this case, step order becomes ambiguous so DOM order is now required to determine the
417                     // correct insertion point
418                     /*jslint bitwise:true*/
419                     while ((newBookmark.node.compareDocumentPosition(previousBookmark.node) & DOCUMENT_POSITION_FOLLOWING) !== 0
420                             && previousBookmark !== basePoint) {
421                         // if the previous bookmark FOLLOWS the new bookmark, navigate back one
422                         previousBookmark = /**@type{!ops.StepsCache.Bookmark}*/(previousBookmark.previousBookmark);
423                     }
424                     /*jslint bitwise:false*/
425                 }
426 
427                 if (!isAlreadyInOrder(previousBookmark, newBookmark)) {
428                     // Removing the existing item first helps prevent infinite-loops from being created in the event of
429                     // some type of undiscovered cache bug.
430                     removeBookmark(newBookmark);
431                     // Assign this value before we override it just below
432                     nextBookmark = previousBookmark.nextBookmark;
433 
434                     newBookmark.nextBookmark = previousBookmark.nextBookmark;
435                     newBookmark.previousBookmark = previousBookmark;
436                     previousBookmark.nextBookmark = newBookmark;
437                     if (nextBookmark) {
438                         nextBookmark.previousBookmark = newBookmark;
439                     }
440                 }
441             }
442         }
443 
444         /**
445          * Signal that all bookmarks up to the specified step have been iterated over and are up-to-date. This allows
446          * removed nodes and invalid bookmarks to be removed from the cache. This function will return the closest
447          * undamaged bookmark just at or prior to the supplied step.
448          * @param {!number} currentIteratorStep
449          * @return {!ops.StepsCache.Bookmark}
450          */
451         function repairCacheUpToStep(currentIteratorStep) {
452             var damagedBookmark,
453                 undamagedBookmark,
454                 nextBookmark,
455                 stepsBucket;
456 
457             if (lastUndamagedCacheStep !== undefined && lastUndamagedCacheStep < currentIteratorStep) {
458                 // The step indicates where in the document re-iteration has covered. This function
459                 // is called every time a bookmark is updated, and the lastUndamagedCacheStep is updated
460                 // after every call. This means that all bookmarks between the undamagedBookmark and the current step
461                 // have not been updated, so they are either:
462                 // a) no longer in the document and should be removed
463                 // or b) are no longer before this step and should be pushed back into the damaged region
464 
465                 undamagedBookmark = getClosestBookmark(lastUndamagedCacheStep); // Get the last undamaged bookmark
466                 damagedBookmark = undamagedBookmark.nextBookmark; // Don't need to check the undamaged bookmark however
467 
468                 while (damagedBookmark && damagedBookmark.steps <= currentIteratorStep) {
469                     nextBookmark = damagedBookmark.nextBookmark;
470                     stepsBucket = getDestinationBucket(damagedBookmark.steps);
471                     // A damaged bookmark is not valid in the stepToDomPoint. In order to minimise update load though
472                     // we don't remove them all at once. Each bookmark is checked vs. the damage point first before use,
473                     // so in order to guarantee we never return a damaged bookmark, we only need to remove damaged
474                     // bookmarks before the damage point.
475 
476                     if (stepToDomPoint[stepsBucket] === damagedBookmark) {
477                         // stepToDomPoint is a sparsely populated cache. For damaged bookmarks, the
478                         // safest thing to do is to remove them entirely from view
479                         delete stepToDomPoint[stepsBucket];
480                     }
481                     if (!domUtils.containsNode(rootElement, damagedBookmark.node)) {
482                         // Node no longer exists in the document. Discard the bookmark as well
483                         removeBookmark(damagedBookmark);
484                         delete nodeToBookmark[damagedBookmark.nodeId];
485                     } else {
486                         // Move the damaged bookmark clearly past the undamaged step
487                         // If this appears later in the sequence, the step number will be corrected then
488                         damagedBookmark.steps = currentIteratorStep + 1;
489                     }
490                     damagedBookmark = nextBookmark;
491                 }
492 
493                 // Have now recovered the cache up to the supplied step. All bookmarks up to this
494                 // step are guaranteed to be up-to-date.
495                 lastUndamagedCacheStep = currentIteratorStep;
496             } else {
497                 undamagedBookmark = getClosestBookmark(currentIteratorStep);
498             }
499             return undamagedBookmark;
500         }
501 
502         /**
503          * Cache the current step, using the supplied node as the anchor
504          * @param {!number} steps Current steps offset from position 0
505          * @param {!Node} node
506          * @return {undefined}
507          */
508         this.updateBookmark = function(steps, node) {
509             var previousCacheBucket,
510                 newCacheBucket = getDestinationBucket(steps),
511                 existingCachePoint,
512                 bookmark,
513                 closestPriorBookmark;
514 
515             closestPriorBookmark = repairCacheUpToStep(steps);
516             // Note, the node bookmark must be updated after the repair as if steps < lastUndamagedCacheStep
517             // the repair will assume any nodes after lastUndamagedCacheStep are damaged.
518             bookmark = getNodeBookmark(/**@type{!HTMLElement}*/(node));
519             if (bookmark.steps !== steps) {
520                 previousCacheBucket = getDestinationBucket(bookmark.steps);
521                 if (previousCacheBucket !== newCacheBucket && stepToDomPoint[previousCacheBucket] === bookmark) {
522                     delete stepToDomPoint[previousCacheBucket];
523                 }
524                 bookmark.steps = steps;
525             }
526             insertBookmark(closestPriorBookmark, bookmark);
527             existingCachePoint = stepToDomPoint[newCacheBucket];
528             // E.g., steps <= 500 are valid for a request starting at 500 and counting forward
529             if (!existingCachePoint || bookmark.steps > existingCachePoint.steps) {
530                 // The current node & offset are closer to the cache bucket boundary than the existing entry was
531                 stepToDomPoint[newCacheBucket] = bookmark;
532             }
533             verifyCache();
534         };
535 
536         /**
537          * Set the iterator to the closest known position before or at the requested step, returning the number of steps
538          * from position 0.
539          * @param {!number} steps
540          * @param {!core.PositionIterator} iterator
541          * @return {!number} Corresponding step for the current iterator position
542          */
543         this.setToClosestStep = function (steps, iterator) {
544             var cachePoint;
545             verifyCache();
546             cachePoint = getClosestBookmark(steps);
547             cachePoint.setIteratorPosition(iterator);
548             return cachePoint.steps;
549         };
550 
551         /**
552          * Finds the nearest ancestor node that has an associated bookmark
553          * @param {!Node} node
554          * @return {?ops.StepsCache.Bookmark}
555          */
556         function findBookmarkedAncestor(node) {
557             var currentNode = node,
558                 nodeId,
559                 bookmark = null;
560 
561             while (!bookmark && currentNode && currentNode !== rootElement) {
562                 nodeId = getNodeId(currentNode);
563                 if (nodeId) {
564                     // Take care as a nodeId may be bookmarked in another translator, but not this particular instance
565                     // Keep crawling up the hierarchy until a node is found with a node id AND bookmark in this translator
566                     bookmark = nodeToBookmark[nodeId];
567                     if (bookmark && !isValidBookmarkForNode(currentNode, bookmark)) {
568                         runtime.log("Cloned node detected. Creating new bookmark");
569                         bookmark = null;
570                         clearNodeId(/**@type{!Element}*/(currentNode));
571                     }
572                 }
573                 currentNode = currentNode.parentNode;
574             }
575             return bookmark;
576         }
577 
578         /**
579          * Set the iterator to the closest known position before or at the requested node & offset, returning the number
580          * of steps from position 0.
581          * @param {!Node} node
582          * @param {!number} offset
583          * @param {!core.PositionIterator} iterator
584          * @return {!number} Corresponding step for the current iterator position
585          */
586         this.setToClosestDomPoint = function (node, offset, iterator) {
587             var /**@type{?ops.StepsCache.Bookmark}*/
588                 bookmark,
589                 b,
590                 /**@type{string|number}*/
591                 key;
592 
593             verifyCache();
594             if (node === rootElement && offset === 0) {
595                 bookmark = basePoint;
596             } else if (node === rootElement && offset === rootElement.childNodes.length) {
597                 bookmark = basePoint;
598                 for (key in stepToDomPoint) {
599                     if (stepToDomPoint.hasOwnProperty(key)) {
600                         b = stepToDomPoint[key];
601                         if (b.steps > bookmark.steps) {
602                             bookmark = b;
603                         }
604                     }
605                 }
606             } else {
607                 bookmark = findBookmarkedAncestor(node.childNodes.item(offset) || node);
608                 if (!bookmark) {
609                     // No immediate bookmark was found, so crawl backwards using the iterator and try and find a known position
610                     iterator.setUnfilteredPosition(node, offset);
611                     while (!bookmark && iterator.previousNode()) {
612                         bookmark = findBookmarkedAncestor(iterator.getCurrentNode());
613                     }
614                 }
615             }
616 
617             bookmark = getUndamagedBookmark(bookmark || basePoint);
618             bookmark.setIteratorPosition(iterator);
619             return bookmark.steps;
620         };
621 
622         /**
623          * Mark all steps beyond inflectionStep as no longer accurate. Note, if a negative value
624          * is passed in it is treated as a -1, and the whole cache will be cleared.
625          * @param {!number} inflectionStep
626          * @return {undefined}
627          */
628         this.damageCacheAfterStep = function(inflectionStep) {
629             if (inflectionStep < 0) {
630                 // Truncate negative steps to be 0. Saves some badness from occurring if a negative is passed in.
631                 inflectionStep = -1;
632             }
633             if (lastUndamagedCacheStep === undefined) {
634                 lastUndamagedCacheStep = inflectionStep;
635             } else if (inflectionStep < lastUndamagedCacheStep) {
636                 lastUndamagedCacheStep = inflectionStep;
637             }
638             verifyCache();
639         };
640 
641         function init() {
642             var rootElementId = getNodeId(rootElement) || setNodeId(rootElement);
643             basePoint = new RootBookmark(rootElementId, 0, rootElement);
644             /*jslint emptyblock:true*/
645             verifyCache = ops.StepsCache.ENABLE_CACHE_VERIFICATION ? verifyCacheImpl : function() { };
646             /*jslint emptyblock:false*/
647         }
648         init();
649     };
650 
651     /**
652      * Enable or disable cache verification operation after every modification. VERY SLOW.
653      * This is primarily used in testing or during interactive diagnostics
654      * @type {!boolean}
655      */
656     ops.StepsCache.ENABLE_CACHE_VERIFICATION = false;
657 
658     /*jslint emptyblock: true, unparam: true*/
659     /**
660      * @interface
661      */
662     ops.StepsCache.Bookmark = function Bookmark() { };
663 
664     /**
665      * @type {!string}
666      */
667     ops.StepsCache.Bookmark.prototype.nodeId;
668 
669     /**
670      * @type {!Node}
671      */
672     ops.StepsCache.Bookmark.prototype.node;
673 
674     /**
675      * @type {!number}
676      */
677     ops.StepsCache.Bookmark.prototype.steps;
678 
679     /**
680      * @type {?ops.StepsCache.Bookmark}
681      */
682     ops.StepsCache.Bookmark.prototype.previousBookmark;
683 
684     /**
685      * @type {?ops.StepsCache.Bookmark}
686      */
687     ops.StepsCache.Bookmark.prototype.nextBookmark;
688 
689     /**
690      * @param {!core.PositionIterator} iterator
691      * @return {undefined}
692      */
693     ops.StepsCache.Bookmark.prototype.setIteratorPosition = function(iterator) { };
694 }());