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 = 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 }());