1 /**
  2  * Copyright (C) 2012 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 Node, NodeFilter, runtime, core*/
 26 
 27 /**
 28  * An iterator that iterators through positions in a DOM tree.
 29  * Positions in the DOM tree are places between nodes and between characters.
 30  * Undesired positions can be avoided by passing a filter to constructor of the
 31  * PositionIterator.
 32  * In the following example '|' designates positions that an unfiltered
 33  * PositionIterator would visit.
 34  *
 35  *  <a>|<b>|<c>|a|b|</c>|a|<a>|</a>|</b>|</a>
 36  *
 37  * Certain positions are considered equivalent in by the PositionIterator.
 38  * Position 0 in a Text node is the same as the position preceding the Text node
 39  * in the parent node. The last position in a Text node is considered equal to
 40  * the subsequent position in the parent node. As such, these two Text node
 41  * positions are ommitted from the PositionIterator's traversal throught the
 42  * DOM. If the PositionIterator is set to a first or last position in a Text
 43  * node, it is instead set the equivalent position in the parent node.
 44  * Omitting the first and last Text node positions serves two functions:
 45  *  - It ensures that the number of iterated steps is independent of how
 46  *    characters are split up over text nodes.
 47  *  - The iterator avoids positions that not distinguised by the API for
 48  *    range and selections purposes.
 49  *
 50  *
 51  * @constructor
 52  * @param {!Node} root
 53  * @param {!number=} whatToShow
 54  * @param {!NodeFilter=} filter
 55  * @param {!boolean=} expandEntityReferences
 56  */
 57 core.PositionIterator = function PositionIterator(root, whatToShow, filter,
 58         expandEntityReferences) {
 59     "use strict";
 60     /*
 61      * Implementation notes.
 62      * The position of the positioniterator is defined by two internal
 63      * variables: walker and currentPos. The walker is an instance of TreeWalker
 64      * which has a member called currentNode of type Node.
 65      * Since the implementation uses a Node and an offset, it is comparable to
 66      * the parameters that go into Range and Selection related functions.
 67      * If the currentNode is a Text node, the variable currentPos gives the
 68      * offset in the node.
 69      * If the currentNode is an Element node, the variable currentPos can only
 70      * have the values 0 or 1. The value 0 means that the iterator is at the
 71      * position just before the currentNode. A value of 1 means that the
 72      * iterator is at the last position inside the currentNode.
 73      */
 74     var self = this,
 75         /**@type{!TreeWalker}*/
 76         walker,
 77         /**@type{!number}*/
 78         currentPos,
 79         /**@type{!function(?Node):!number}*/
 80         nodeFilter,
 81         TEXT_NODE = Node.TEXT_NODE,
 82         ELEMENT_NODE = Node.ELEMENT_NODE,
 83         FILTER_ACCEPT = NodeFilter.FILTER_ACCEPT,
 84         FILTER_REJECT = NodeFilter.FILTER_REJECT;
 85 
 86     /**
 87      * Empty text nodes are not considered to be a valid position for the
 88      * positioniterator. They should be filtered out in all cases.
 89      * @constructor
 90      * @implements NodeFilter
 91      */
 92     function EmptyTextNodeFilter() {
 93         /**
 94          * @param {?Node} node
 95          * @return {!number}
 96          */
 97         this.acceptNode = function (node) {
 98             var text = /**@type{!Text}*/(node);
 99             if (!node || (node.nodeType === TEXT_NODE && text.length === 0)) {
100                 return FILTER_REJECT;
101             }
102             return FILTER_ACCEPT;
103         };
104     }
105     /**
106      * @constructor
107      * @implements NodeFilter
108      * @param {!NodeFilter} filter
109      */
110     function FilteredEmptyTextNodeFilter(filter) {
111         /**
112          * @param {?Node} node
113          * @return {!number}
114          */
115         this.acceptNode = function (node) {
116             var text = /**@type{!Text}*/(node);
117             if (!node || (node.nodeType === TEXT_NODE && text.length === 0)) {
118                 return FILTER_REJECT;
119             }
120             return filter.acceptNode(node);
121         };
122     }
123 
124     /**
125      * @return {!boolean}
126      */
127     this.nextPosition = function () {
128         var currentNode = walker.currentNode,
129             nodeType = currentNode.nodeType,
130             text = /**@type{!Text}*/(currentNode);
131         if (currentNode === root) {
132             return false;
133         }
134         if (currentPos === 0 && nodeType === ELEMENT_NODE) {
135             // step inside an element
136             if (walker.firstChild() === null) {
137                 currentPos = 1;
138             }
139         } else if (nodeType === TEXT_NODE
140                 && currentPos + 1 < text.length) {
141             // advance inside a text node
142             currentPos += 1;
143         } else {
144             if (walker.nextSibling() !== null) {
145                 currentPos = 0;
146             } else if (walker.parentNode()) {
147                 currentPos = 1;
148             } else {
149                 return false;
150             }
151         }
152         return true;
153     };
154     function setAtEnd() {
155         var text = /**@type{!Text}*/(walker.currentNode),
156             type = text.nodeType;
157         if (type === TEXT_NODE) {
158             currentPos = text.length - 1;
159         } else {
160             currentPos = (type === ELEMENT_NODE) ? 1 : 0;
161         }
162     }
163     /**
164      * @return {!boolean}
165      */
166     function previousNode() {
167         if (walker.previousSibling() === null) {
168             if (!walker.parentNode() || walker.currentNode === root) {
169                 walker.firstChild();
170                 return false;
171             }
172             currentPos = 0;
173         } else {
174             setAtEnd();
175         }
176         return true;
177     }
178     /**
179      * Move the iterator to the previous position.
180      * If the iterator is already at the first position, it is not moved and
181      * false is returned instead of true.
182      * @return {!boolean}
183      */
184     this.previousPosition = function () {
185         var moved = true,
186             currentNode = walker.currentNode;
187         if (currentPos === 0) {
188             moved = previousNode();
189         } else if (currentNode.nodeType === TEXT_NODE) {
190             currentPos -= 1;
191         } else if (walker.lastChild() !== null) {
192             setAtEnd();
193         } else if (currentNode === root) {
194             moved = false;
195         } else {
196             currentPos = 0;
197         }
198         return moved;
199     };
200     /**
201      * This function exposes class internals and should be avoided.
202      */
203     this.previousNode = previousNode;
204     /**
205      * Return the container for the current position.
206      * @return {!Element|!Text}
207      */
208     this.container = function () {
209         var n = /**@type{!Element|!Text}*/(walker.currentNode),
210             t = n.nodeType;
211         if (currentPos === 0 && t !== TEXT_NODE) {
212             n = /**@type{!Element|!Text}*/(n.parentNode);
213         }
214         return n;
215     };
216     /**
217      * Return the node to the right of the current iterator position.
218      * If the iterator is placed between two characters in a text node,
219      * the text node will be returned.
220      * If there is no right neighbor in the container node, then null is
221      * returned.
222      * Only filtered nodes will be returned.
223      * @return {?Node}
224      */
225     this.rightNode = function () {
226         var n = walker.currentNode,
227             text = /**@type{!Text}*/(n),
228             nodeType = n.nodeType;
229         if (nodeType === TEXT_NODE && currentPos === text.length) {
230             n = n.nextSibling;
231             while (n && nodeFilter(n) !== FILTER_ACCEPT) {
232                 n = n.nextSibling;
233             }
234         } else if (nodeType === ELEMENT_NODE && currentPos === 1) {
235             n = null;
236         }
237         return n;
238     };
239     /**
240      * Return the node to the left of the current iterator position.
241      * See rightNode().
242      * @return {?Node}
243      */
244     this.leftNode = function () {
245         var n = walker.currentNode;
246         if (currentPos === 0) {
247             n = n.previousSibling;
248             while (n && nodeFilter(n) !== FILTER_ACCEPT) {
249                 n = n.previousSibling;
250             }
251         } else if (n.nodeType === ELEMENT_NODE) {
252             n = n.lastChild;
253             while (n && nodeFilter(n) !== FILTER_ACCEPT) {
254                 n = n.previousSibling;
255             }
256         }
257         return n;
258     };
259     /**
260      * This function exposes class internals and should be avoided.
261      * @return {!Element|!Text}
262      */
263     this.getCurrentNode = function () {
264         var n = /**@type{!Element|!Text}*/(walker.currentNode);
265         return n;
266     };
267     /**
268      * Returns the current position within the container of the iterator.
269      * This function is useful for communication iterator position with
270      * components that do not use a filter.
271      * @return {!number}
272      */
273     this.unfilteredDomOffset = function () {
274         if (walker.currentNode.nodeType === TEXT_NODE) {
275             return currentPos;
276         }
277         var c = 0,
278             n = walker.currentNode;
279         if (currentPos === 1) {
280             n = n.lastChild;
281         } else {
282             n = n.previousSibling;
283         }
284         while (n) {
285             c += 1;
286             n = n.previousSibling;
287         }
288         return c;
289     };
290     /**
291      * Return the previous sibling of the current node
292      * @return {Node}
293      */
294     this.getPreviousSibling = function () {
295         var currentNode = walker.currentNode,
296             sibling = walker.previousSibling();
297 
298         walker.currentNode = currentNode;
299 
300         return sibling;
301     };
302     /**
303      * Return the next sibling of the current node
304      * @return {Node}
305      */
306     this.getNextSibling = function () {
307         var currentNode = walker.currentNode,
308             sibling = walker.nextSibling();
309 
310         walker.currentNode = currentNode;
311 
312         return sibling;
313     };
314 
315     /**
316      * Advance the walker to the first node that is accepted by the node filter
317      * (i.e., nodeFilter(node) === FILTER_ACCEPT)
318      *
319      * @return {!boolean} Returns true if the walker found an accepted node. Otherwise
320      * returns false.
321      */
322     function moveToAcceptedNode() {
323         var node = walker.currentNode,
324             filterResult,
325             moveResult;
326 
327         // Ensure currentNode is not within a rejected subtree by crawling each parent node
328         // up to the root and verifying it is either accepted or skipped by the nodeFilter.
329         // NOTE: The root is deliberately not checked as it is the container iteration happens within.
330         filterResult = nodeFilter(node);
331         if (node !== root) {
332             node = node.parentNode;
333             while (node && node !== root) {
334                 if (nodeFilter(node) === FILTER_REJECT) {
335                     walker.currentNode = node;
336                     filterResult = FILTER_REJECT;
337                 }
338                 node = node.parentNode;
339             }
340         }
341 
342         if (filterResult === FILTER_REJECT) {
343             // Set currentPos to be 1 (or text data.length), so nextPosition will jump to the next sibling or parent
344             currentPos = walker.currentNode.nodeType === TEXT_NODE ? /**@type{!Text}*/(node).length : 1;
345             moveResult = self.nextPosition();
346         } else if (filterResult === FILTER_ACCEPT) {
347             moveResult = true;
348         } else {
349             // filterResult === FILTER_SKIP
350             // FILTER_SKIP indicates children of the current node are acceptable.
351             // currentPos is left unchanged as nextPosition can advance to an accepted child inside the node
352             moveResult = self.nextPosition();
353         }
354         if (moveResult) {
355             runtime.assert(nodeFilter(walker.currentNode) === FILTER_ACCEPT,
356                 "moveToAcceptedNode did not result in walker being on an accepted node");
357         }
358         return moveResult;
359     }
360 
361     /**
362      * Set the current position of the iterator to just before the supplied element.
363      *
364      * Querying the iterator then will return the container of the element and the offset
365      * of the element within it's container (assuming the supplied element is accepted by
366      * the nodeFilter).
367      *
368      * E.g.,
369      * p1.setPositionBeforeElement(span);
370      * p1.container() === span.parentNode
371      * p1.unfilteredDomOffset === positionInParent(span)
372      *
373      * If the element is not accepted by the nodeFilter, the iterator will immediately
374      * move to the next accepted node.
375      *
376      * @param {!Element} element
377      * @return {!boolean} Returns true if the iterator was set to a valid position
378      * (i.e., is currently on a node that is accepted by the nodeFilter)
379      */
380     this.setPositionBeforeElement = function (element) {
381         runtime.assert(Boolean(element), "setPositionBeforeElement called without element");
382         walker.currentNode = element;
383         currentPos = 0;
384 
385         return moveToAcceptedNode();
386     };
387 
388     /**
389      * Set the current position of the iterator to the specified container + offset.
390      *
391      * Querying the iterator will then return the supplied container + offset
392      * (assuming the supplied element is accepted by the nodeFilter).
393      *
394      * E.g.,
395      * p2.setUnfilteredPosition(container, offset);
396      * p2.container() === container
397      * p2.unfilteredDomOffset() === offset;
398      *
399      * If the container is not accepted by the nodeFilter, the iterator will immediately
400      * move to the next accepted node.
401      *
402      * @param {!Node} container
403      * @param {!number} offset offset in unfiltered DOM world. Will immediately advance
404      * the iterator to the numbered child node of the provided container.
405      * @return {!boolean} Returns true if the iterator was set to a valid position
406      * (i.e., is currently on a node that is accepted by the nodeFilter)
407      */
408     this.setUnfilteredPosition = function (container, offset) {
409         var text;
410         runtime.assert(Boolean(container), "PositionIterator.setUnfilteredPosition called without container");
411         walker.currentNode = container;
412         if (container.nodeType === TEXT_NODE) {
413             currentPos = offset;
414             text = /**@type{!Text}*/(container);
415             runtime.assert(offset <= text.length, "Error in setPosition: " +
416                 offset + " > " + text.length);
417             runtime.assert(offset >= 0, "Error in setPosition: " +
418                 offset + " < 0");
419             if (offset === text.length) {
420                 if (walker.nextSibling()) {
421                     currentPos = 0;
422                 } else if (walker.parentNode()) {
423                     currentPos = 1;
424                 } else {
425                     runtime.assert(false, "Error in setUnfilteredPosition: position not valid.");
426                 }
427             }
428         } else if (offset < container.childNodes.length) {
429             // Immediately advance to the child node at that offset to begin iteration.
430             // This is necessary in order to satisfy the most frequent use case where developer will
431             // store the (container, unfilteredDomOffset) from a previous position iterator, and use
432             // this value to resume iteration at the specified point. If we didn't immediately advance
433             // to the next position, the first call to nextPosition would return the input container+offset.
434             walker.currentNode = /**@type{!Node}*/(container.childNodes.item(offset));
435             currentPos = 0;
436         } else {
437             // Either the node has no children or offset === childNodes.length
438 
439             // Set currentPos to 1 to indicate iteration on the currentNode is complete.
440             // This will cause the next call to self.nextPosition() to jump to the next
441             // available sibling or parent
442             currentPos = 1;
443         }
444 
445         return moveToAcceptedNode();
446     };
447     /**
448      * Move the iterator to its last possible position.
449      * This is at the last position in the root node if the iterator.
450      * @return {undefined}
451      */
452     this.moveToEnd = function () {
453         walker.currentNode = root;
454         currentPos = 1;
455     };
456 
457     /**
458      * Places the iterator at the last position inside the given node.
459      * @param {!Node} node
460      * @return {undefined}
461      */
462     this.moveToEndOfNode = function (node) {
463         var text;
464         if (node.nodeType === TEXT_NODE) {
465             text = /**@type{!Text}*/(node);
466             self.setUnfilteredPosition(text, text.length);
467         } else {
468             walker.currentNode = node;
469             currentPos = 1;
470         }
471     };
472 
473     /**
474      * Returns true if the iterator is just to the left of a node. In this position,
475      * calls to container() will return the parent of the node, and unfilteredDomOffset
476      * will return the position of the node within the parent container.
477      *
478      * Calls to unfilteredDomOffset are extremely slow when the iterator is just before a
479      * node, so querying this method can provide warning when a slow offset is necessary.
480      * @return {!boolean}
481      */
482     this.isBeforeNode = function() {
483         return currentPos === 0;
484     };
485 
486     /**
487      * Return the filter that is used in this iterator.
488      * @return {!function(?Node):!number}
489      */
490     this.getNodeFilter = function () {
491         return nodeFilter;
492     };
493 
494     function init() {
495         var f;
496         // a position can never be near an empty TextNode. A NodeFilter is the
497         // easiest way of filtering out these nodes.
498         if (filter) {
499             f = new FilteredEmptyTextNodeFilter(filter);
500         } else {
501             f = new EmptyTextNodeFilter();
502         }
503         // workaround for versions of createTreeWalker that need a function
504         // instead of an object with a function such as IE 9 and older webkits
505         nodeFilter = /**@type {!function(?Node):!number}*/(f.acceptNode);
506         nodeFilter.acceptNode = nodeFilter;
507         whatToShow = whatToShow || NodeFilter.SHOW_ALL;
508         runtime.assert(root.nodeType !== Node.TEXT_NODE, "Internet Explorer doesn't allow tree walker roots to be text nodes");
509         walker = root.ownerDocument.createTreeWalker(root, whatToShow,
510                 nodeFilter, expandEntityReferences);
511 
512         currentPos = 0;
513         if (walker.firstChild() === null) {
514             currentPos = 1;
515         }
516     }
517     init();
518 };
519