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 98 /** 99 * Bookmark tied to a specific node 100 * @constructor 101 * @param {!string} nodeId 102 * @param {!Element} bookmarkNode 103 * 104 * @implements {ops.StepsCache.Bookmark} 105 */ 106 function NodeBookmark(nodeId, bookmarkNode) { 107 var self = this; 108 this.nodeId = nodeId; 109 this.steps = -1; 110 this.node = bookmarkNode; 111 this.nextBookmark = null; 112 this.previousBookmark = null; 113 114 /** 115 * @param {!core.PositionIterator} iterator 116 * @return {undefined} 117 */ 118 this.setIteratorPosition = function(iterator) { 119 iterator.setPositionBeforeElement(bookmarkNode); 120 restoreBookmarkPosition(self.steps, iterator); 121 }; 122 } 123 124 /** 125 * Bookmark indicating the first walkable position in the document 126 * @constructor 127 * @param {!string} nodeId 128 * @param {!number} steps 129 * @param {!Node} rootNode 130 * 131 * @implements {ops.StepsCache.Bookmark} 132 */ 133 function RootBookmark(nodeId, steps, rootNode) { 134 var self = this; 135 this.nodeId = nodeId; 136 this.steps = steps; 137 this.node = rootNode; 138 this.nextBookmark = null; 139 this.previousBookmark = null; 140 141 /** 142 * @param {!core.PositionIterator} iterator 143 * @return {undefined} 144 */ 145 this.setIteratorPosition = function (iterator) { 146 iterator.setUnfilteredPosition(rootNode, 0); 147 restoreBookmarkPosition(self.steps, iterator); 148 }; 149 } 150 151 /** 152 * Return a summary string of the supplied bookmark node id(s) 153 * @param {!ops.StepsCache.Bookmark} bookmark1 154 * @param {?ops.StepsCache.Bookmark=} bookmark2 155 * @return {!string} 156 */ 157 function inspectBookmarks(bookmark1, bookmark2) { 158 var parts = "[" + bookmark1.nodeId; 159 if (bookmark2) { 160 parts += " => " + bookmark2.nodeId; 161 } 162 return parts + "]"; 163 } 164 165 /** 166 * Returns true if the specified bookmark is undamaged 167 * @param {!ops.StepsCache.Bookmark} bookmark 168 * @return {!boolean} 169 */ 170 function isUndamagedBookmark(bookmark) { 171 return lastUndamagedCacheStep === undefined 172 || bookmark === basePoint 173 || bookmark.steps <= lastUndamagedCacheStep; 174 } 175 176 /** 177 * Run a series of verification checks against the complete cache to ensure it is operating 178 * correctly. Note, this is VERY expensive, and should only be done when attempting to diagnose 179 * caching problems 180 * @return {undefined} 181 */ 182 function verifyCache() { 183 if (ops.StepsCache.ENABLE_CACHE_VERIFICATION !== true) { 184 return; 185 } 186 187 var bookmark = basePoint, 188 previousBookmark, 189 nextBookmark, 190 documentPosition, 191 loopCheck = new core.LoopWatchDog(0, 100000), 192 /**@type{!Object.<!string, !string>}*/ 193 stepToDomPointNodeIds = {}; 194 195 while (bookmark) { 196 loopCheck.check(); 197 previousBookmark = bookmark.previousBookmark; 198 if (previousBookmark) { 199 // Make sure previous => current chain is intact 200 runtime.assert(previousBookmark.nextBookmark === bookmark, 201 "Broken bookmark link to previous @" + inspectBookmarks(previousBookmark, bookmark)); 202 } else { 203 // If there is no previous, ensure this is the basePoint bookmark 204 runtime.assert(bookmark === basePoint, "Broken bookmark link @" + inspectBookmarks(bookmark)); 205 runtime.assert(isUndamagedBookmark(basePoint), "Base point is damaged @" + inspectBookmarks(bookmark)); 206 } 207 nextBookmark = bookmark.nextBookmark; 208 if (nextBookmark) { 209 // Make sure current => next chain is intact 210 runtime.assert(nextBookmark.previousBookmark === bookmark, 211 "Broken bookmark link to next @" + inspectBookmarks(bookmark, nextBookmark)); 212 } 213 214 if (isUndamagedBookmark(bookmark)) { 215 runtime.assert(domUtils.containsNode(rootElement, bookmark.node), 216 "Disconnected node is being reported as undamaged @" + inspectBookmarks(bookmark)); 217 if (previousBookmark) { 218 documentPosition = bookmark.node.compareDocumentPosition(previousBookmark.node); 219 /*jslint bitwise:true*/ 220 runtime.assert(documentPosition === 0 || (documentPosition & DOCUMENT_POSITION_PRECEDING) !== 0, 221 "Bookmark order with previous does not reflect DOM order @" + inspectBookmarks(previousBookmark, bookmark)); 222 /*jslint bitwise:false*/ 223 } 224 if (nextBookmark) { 225 if (domUtils.containsNode(rootElement, nextBookmark.node)) { 226 documentPosition = bookmark.node.compareDocumentPosition(nextBookmark.node); 227 /*jslint bitwise:true*/ 228 runtime.assert(documentPosition === 0 || (documentPosition & DOCUMENT_POSITION_FOLLOWING) !== 0, 229 "Bookmark order with next does not reflect DOM order @" + inspectBookmarks(bookmark, nextBookmark)); 230 /*jslint bitwise:false*/ 231 } 232 } 233 } 234 235 bookmark = bookmark.nextBookmark; 236 } 237 238 Object.keys(stepToDomPoint).forEach(function(step) { 239 var domPointBookmark = stepToDomPoint[step]; 240 if (lastUndamagedCacheStep === undefined || step <= lastUndamagedCacheStep) { 241 runtime.assert(domPointBookmark.steps <= step, "Bookmark step of " + domPointBookmark.steps + 242 " exceeds cached step lookup for " + step + " @" + inspectBookmarks(domPointBookmark)); 243 } 244 245 runtime.assert(stepToDomPointNodeIds.hasOwnProperty(domPointBookmark.nodeId) === false, 246 "Bookmark " + inspectBookmarks(domPointBookmark) + " appears twice in cached step lookup at steps " + 247 stepToDomPointNodeIds[domPointBookmark.nodeId] + " and " + step); 248 stepToDomPointNodeIds[domPointBookmark.nodeId] = step; 249 }); 250 } 251 252 /** 253 * Returns the closest quantized step at or before the requested step 254 * @param {!number} steps 255 * @return {!number} 256 */ 257 function getBucket(steps) { 258 return Math.floor(steps / bucketSize) * bucketSize; 259 } 260 261 /** 262 * Returns the closest quantized step at or just after the requested step 263 * @param {!number} steps 264 * @return {!number} 265 */ 266 function getDestinationBucket(steps) { 267 return Math.ceil(steps / bucketSize) * bucketSize; 268 } 269 270 /** 271 * @param {!Element} node 272 * @return {undefined} 273 */ 274 function clearNodeId(node) { 275 node.removeAttributeNS(coordinatens, "nodeId"); 276 } 277 278 /** 279 * @param {!Node} node 280 * @return {!string} 281 */ 282 function getNodeId(node) { 283 var id = ""; 284 if (node.nodeType === Node.ELEMENT_NODE) { 285 id = /**@type{!Element}*/(node).getAttributeNS(coordinatens, "nodeId") || ""; 286 } 287 return id; 288 } 289 290 /** 291 * @param {!Element} node 292 * @return {!string} 293 */ 294 function setNodeId(node) { 295 var nodeId = nextNodeId.toString(); 296 node.setAttributeNS(coordinatens, "nodeId", nodeId); 297 nextNodeId += 1; 298 return nodeId; 299 } 300 301 /** 302 * The element might have been cloned from another part of the document and have a stale or duplicate 303 * nodeId 304 * @param {!Node} node 305 * @param {!ops.StepsCache.Bookmark} bookmark 306 * @return {!boolean} True if the bookmark is actually for the supplied node 307 */ 308 function isValidBookmarkForNode(node, bookmark) { 309 return bookmark.node === node; 310 } 311 312 /** 313 * Fetches (or creates) a bookmark for the specified node. 314 * 315 * @param {!Element} node 316 * @return {!ops.StepsCache.Bookmark} 317 */ 318 function getNodeBookmark(node) { 319 var nodeId = getNodeId(node) || setNodeId(node), 320 existingBookmark; 321 existingBookmark = nodeToBookmark[nodeId]; 322 if (!existingBookmark) { 323 existingBookmark = nodeToBookmark[nodeId] = new NodeBookmark(nodeId, node); 324 } else if (!isValidBookmarkForNode(node, existingBookmark)) { 325 runtime.log("Cloned node detected. Creating new bookmark"); 326 nodeId = setNodeId(node); 327 existingBookmark = nodeToBookmark[nodeId] = new NodeBookmark(nodeId, node); 328 } 329 return existingBookmark; 330 } 331 332 /** 333 * Returns the closest undamaged bookmark before or at the specified step 334 * @param {!number} steps 335 * @return {!ops.StepsCache.Bookmark} 336 */ 337 function getClosestBookmark(steps) { 338 var cacheBucket, 339 cachePoint, 340 loopGuard = new core.LoopWatchDog(0, 10000); 341 342 // This function promises to return an undamaged bookmark at all times. 343 // Easiest way to ensure this is don't allow requests to damaged sections 344 // of the cache. 345 if (lastUndamagedCacheStep !== undefined && steps > lastUndamagedCacheStep) { 346 steps = lastUndamagedCacheStep; 347 } 348 cacheBucket = getBucket(steps); 349 350 while (!cachePoint && cacheBucket >= 0) { 351 cachePoint = stepToDomPoint[cacheBucket]; 352 cacheBucket -= bucketSize; 353 } 354 355 cachePoint = cachePoint || basePoint; 356 while (cachePoint.nextBookmark && cachePoint.nextBookmark.steps <= steps) { 357 loopGuard.check(); 358 cachePoint = cachePoint.nextBookmark; 359 } 360 runtime.assert(steps === -1 || cachePoint.steps <= steps, 361 "Bookmark @" + inspectBookmarks(cachePoint) + " at step " + cachePoint.steps + 362 " exceeds requested step of " + steps); 363 return cachePoint; 364 } 365 366 /** 367 * Returns the closest undamaged bookmark before (or equal to) the supplied bookmark 368 * @param {!ops.StepsCache.Bookmark} bookmark 369 * @return {!ops.StepsCache.Bookmark} 370 */ 371 function getUndamagedBookmark(bookmark) { 372 // Based on logic in the repairCacheUpToStep, a damaged bookmark is guaranteed to have it's 373 // steps moved beyond the damage point. This makes it simple to check if the bookmark is 374 // in the damaged region, and return the last undamaged one if it is. 375 if (lastUndamagedCacheStep !== undefined && bookmark.steps > lastUndamagedCacheStep) { 376 bookmark = getClosestBookmark(lastUndamagedCacheStep); 377 } 378 return bookmark; 379 } 380 381 /** 382 * Remove a bookmark from the cache chain 383 * @param {!ops.StepsCache.Bookmark} currentBookmark 384 * @return {undefined} 385 */ 386 function removeBookmark(currentBookmark) { 387 if (currentBookmark.previousBookmark) { 388 currentBookmark.previousBookmark.nextBookmark = currentBookmark.nextBookmark; 389 } 390 391 if (currentBookmark.nextBookmark) { 392 currentBookmark.nextBookmark.previousBookmark = currentBookmark.previousBookmark; 393 } 394 } 395 396 /** 397 * Returns true if the newBookmark is already directly on or after the previous bookmark 398 * @param {!ops.StepsCache.Bookmark} previousBookmark 399 * @param {!ops.StepsCache.Bookmark} newBookmark 400 * @return {!boolean} 401 */ 402 function isAlreadyInOrder(previousBookmark, newBookmark) { 403 return previousBookmark === newBookmark || previousBookmark.nextBookmark === newBookmark; 404 } 405 406 /** 407 * Insert a bookmark into the cache chain just after the previous bookmark 408 * @param {!ops.StepsCache.Bookmark} previousBookmark 409 * @param {!ops.StepsCache.Bookmark} newBookmark 410 * @return {undefined} 411 */ 412 function insertBookmark(previousBookmark, newBookmark) { 413 var nextBookmark; 414 // Check if the newBookmark is already in the chain at the correct location. Don't bother updating 415 // if it is in place. 416 if (!isAlreadyInOrder(previousBookmark, newBookmark)) { 417 if (previousBookmark.steps === newBookmark.steps) { 418 // It is valid for multiple bookmarks to share the same step. 419 // In this case, step order becomes ambiguous so DOM order is now required to determine the 420 // correct insertion point 421 /*jslint bitwise:true*/ 422 while ((newBookmark.node.compareDocumentPosition(previousBookmark.node) & DOCUMENT_POSITION_FOLLOWING) !== 0 423 && previousBookmark !== basePoint) { 424 // if the previous bookmark FOLLOWS the new bookmark, navigate back one 425 previousBookmark = /**@type{!ops.StepsCache.Bookmark}*/(previousBookmark.previousBookmark); 426 } 427 /*jslint bitwise:false*/ 428 } 429 430 if (!isAlreadyInOrder(previousBookmark, newBookmark)) { 431 // Removing the existing item first helps prevent infinite-loops from being created in the event of 432 // some type of undiscovered cache bug. 433 removeBookmark(newBookmark); 434 // Assign this value before we override it just below 435 nextBookmark = previousBookmark.nextBookmark; 436 437 newBookmark.nextBookmark = previousBookmark.nextBookmark; 438 newBookmark.previousBookmark = previousBookmark; 439 previousBookmark.nextBookmark = newBookmark; 440 if (nextBookmark) { 441 nextBookmark.previousBookmark = newBookmark; 442 } 443 } 444 } 445 } 446 447 /** 448 * Signal that all bookmarks up to the specified step have been iterated over and are up-to-date. This allows 449 * removed nodes and invalid bookmarks to be removed from the cache. This function will return the closest 450 * undamaged bookmark just at or prior to the supplied step. 451 * @param {!number} currentIteratorStep 452 * @return {!ops.StepsCache.Bookmark} 453 */ 454 function repairCacheUpToStep(currentIteratorStep) { 455 var damagedBookmark, 456 undamagedBookmark, 457 nextBookmark, 458 stepsBucket; 459 460 if (lastUndamagedCacheStep !== undefined && lastUndamagedCacheStep < currentIteratorStep) { 461 // The step indicates where in the document re-iteration has covered. This function 462 // is called every time a bookmark is updated, and the lastUndamagedCacheStep is updated 463 // after every call. This means that all bookmarks between the undamagedBookmark and the current step 464 // have not been updated, so they are either: 465 // a) no longer in the document and should be removed 466 // or b) are no longer before this step and should be pushed back into the damaged region 467 468 undamagedBookmark = getClosestBookmark(lastUndamagedCacheStep); // Get the last undamaged bookmark 469 damagedBookmark = undamagedBookmark.nextBookmark; // Don't need to check the undamaged bookmark however 470 471 while (damagedBookmark && damagedBookmark.steps <= currentIteratorStep) { 472 nextBookmark = damagedBookmark.nextBookmark; 473 stepsBucket = getDestinationBucket(damagedBookmark.steps); 474 // A damaged bookmark is not valid in the stepToDomPoint. In order to minimise update load though 475 // we don't remove them all at once. Each bookmark is checked vs. the damage point first before use, 476 // so in order to guarantee we never return a damaged bookmark, we only need to remove damaged 477 // bookmarks before the damage point. 478 479 if (stepToDomPoint[stepsBucket] === damagedBookmark) { 480 // stepToDomPoint is a sparsely populated cache. For damaged bookmarks, the 481 // safest thing to do is to remove them entirely from view 482 delete stepToDomPoint[stepsBucket]; 483 } 484 if (!domUtils.containsNode(rootElement, damagedBookmark.node)) { 485 // Node no longer exists in the document. Discard the bookmark as well 486 removeBookmark(damagedBookmark); 487 delete nodeToBookmark[damagedBookmark.nodeId]; 488 } else { 489 // Move the damaged bookmark clearly past the undamaged step 490 // If this appears later in the sequence, the step number will be corrected then 491 damagedBookmark.steps = currentIteratorStep + 1; 492 } 493 damagedBookmark = nextBookmark; 494 } 495 496 // Have now recovered the cache up to the supplied step. All bookmarks up to this 497 // step are guaranteed to be up-to-date. 498 lastUndamagedCacheStep = currentIteratorStep; 499 } else { 500 undamagedBookmark = getClosestBookmark(currentIteratorStep); 501 } 502 return undamagedBookmark; 503 } 504 505 /** 506 * Cache the current step, using the supplied node as the anchor 507 * @param {!number} steps Current steps offset from position 0 508 * @param {!Node} node 509 * @return {undefined} 510 */ 511 this.updateBookmark = function(steps, node) { 512 var previousCacheBucket, 513 newCacheBucket = getDestinationBucket(steps), 514 existingCachePoint, 515 bookmark, 516 closestPriorBookmark; 517 518 closestPriorBookmark = repairCacheUpToStep(steps); 519 // Note, the node bookmark must be updated after the repair as if steps < lastUndamagedCacheStep 520 // the repair will assume any nodes after lastUndamagedCacheStep are damaged. 521 bookmark = getNodeBookmark(/**@type{!HTMLElement}*/(node)); 522 if (bookmark.steps !== steps) { 523 previousCacheBucket = getDestinationBucket(bookmark.steps); 524 if (previousCacheBucket !== newCacheBucket && stepToDomPoint[previousCacheBucket] === bookmark) { 525 delete stepToDomPoint[previousCacheBucket]; 526 } 527 bookmark.steps = steps; 528 } 529 insertBookmark(closestPriorBookmark, bookmark); 530 existingCachePoint = stepToDomPoint[newCacheBucket]; 531 // E.g., steps <= 500 are valid for a request starting at 500 and counting forward 532 if (!existingCachePoint || bookmark.steps > existingCachePoint.steps) { 533 // The current node & offset are closer to the cache bucket boundary than the existing entry was 534 stepToDomPoint[newCacheBucket] = bookmark; 535 } 536 verifyCache(); 537 }; 538 539 /** 540 * Set the iterator to the closest known position before or at the requested step, returning the number of steps 541 * from position 0. 542 * @param {!number} steps 543 * @param {!core.PositionIterator} iterator 544 * @return {!number} Corresponding step for the current iterator position 545 */ 546 this.setToClosestStep = function (steps, iterator) { 547 var cachePoint; 548 verifyCache(); 549 cachePoint = getClosestBookmark(steps); 550 cachePoint.setIteratorPosition(iterator); 551 return cachePoint.steps; 552 }; 553 554 /** 555 * Finds the nearest ancestor node that has an associated bookmark 556 * @param {!Node} node 557 * @return {?ops.StepsCache.Bookmark} 558 */ 559 function findBookmarkedAncestor(node) { 560 var currentNode = node, 561 nodeId, 562 bookmark = null; 563 564 while (!bookmark && currentNode && currentNode !== rootElement) { 565 nodeId = getNodeId(currentNode); 566 if (nodeId) { 567 // Take care as a nodeId may be bookmarked in another translator, but not this particular instance 568 // Keep crawling up the hierarchy until a node is found with a node id AND bookmark in this translator 569 bookmark = nodeToBookmark[nodeId]; 570 if (bookmark && !isValidBookmarkForNode(currentNode, bookmark)) { 571 runtime.log("Cloned node detected. Creating new bookmark"); 572 bookmark = null; 573 clearNodeId(/**@type{!Element}*/(currentNode)); 574 } 575 } 576 currentNode = currentNode.parentNode; 577 } 578 return bookmark; 579 } 580 581 /** 582 * Set the iterator to the closest known position before or at the requested node & offset, returning the number 583 * of steps from position 0. 584 * @param {!Node} node 585 * @param {!number} offset 586 * @param {!core.PositionIterator} iterator 587 * @return {!number} Corresponding step for the current iterator position 588 */ 589 this.setToClosestDomPoint = function (node, offset, iterator) { 590 var /**@type{?ops.StepsCache.Bookmark}*/ 591 bookmark, 592 b, 593 /**@type{string|number}*/ 594 key; 595 596 verifyCache(); 597 if (node === rootElement && offset === 0) { 598 bookmark = basePoint; 599 } else if (node === rootElement && offset === rootElement.childNodes.length) { 600 bookmark = basePoint; 601 for (key in stepToDomPoint) { 602 if (stepToDomPoint.hasOwnProperty(key)) { 603 b = stepToDomPoint[key]; 604 if (b.steps > bookmark.steps) { 605 bookmark = b; 606 } 607 } 608 } 609 } else { 610 bookmark = findBookmarkedAncestor(node.childNodes.item(offset) || node); 611 if (!bookmark) { 612 // No immediate bookmark was found, so crawl backwards using the iterator and try and find a known position 613 iterator.setUnfilteredPosition(node, offset); 614 while (!bookmark && iterator.previousNode()) { 615 bookmark = findBookmarkedAncestor(iterator.getCurrentNode()); 616 } 617 } 618 } 619 620 bookmark = getUndamagedBookmark(bookmark || basePoint); 621 bookmark.setIteratorPosition(iterator); 622 return bookmark.steps; 623 }; 624 625 /** 626 * Mark all steps beyond inflectionStep as no longer accurate. Note, if a negative value 627 * is passed in it is treated as a -1, and the whole cache will be cleared. 628 * @param {!number} inflectionStep 629 * @return {undefined} 630 */ 631 this.damageCacheAfterStep = function(inflectionStep) { 632 if (inflectionStep < 0) { 633 // Truncate negative steps to be 0. Saves some badness from occurring if a negative is passed in. 634 inflectionStep = -1; 635 } 636 if (lastUndamagedCacheStep === undefined) { 637 lastUndamagedCacheStep = inflectionStep; 638 } else if (inflectionStep < lastUndamagedCacheStep) { 639 lastUndamagedCacheStep = inflectionStep; 640 } 641 verifyCache(); 642 }; 643 644 function init() { 645 var rootElementId = getNodeId(rootElement) || setNodeId(rootElement); 646 basePoint = new RootBookmark(rootElementId, 0, rootElement); 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 }());