Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include "mozilla/DebugOnly.h"
8 : #include "nsISupports.h"
9 : #include "nsIDOMNodeList.h"
10 : #include "nsIContentIterator.h"
11 : #include "nsRange.h"
12 : #include "nsIContent.h"
13 : #include "nsCOMPtr.h"
14 : #include "nsTArray.h"
15 : #include "nsContentUtils.h"
16 : #include "nsINode.h"
17 : #include "nsCycleCollectionParticipant.h"
18 :
19 : using mozilla::DebugOnly;
20 :
21 : // couple of utility static functs
22 :
23 : ///////////////////////////////////////////////////////////////////////////
24 : // NodeToParentOffset: returns the node's parent and offset.
25 : //
26 :
27 : static nsINode*
28 0 : NodeToParentOffset(nsINode* aNode, int32_t* aOffset)
29 : {
30 0 : *aOffset = 0;
31 :
32 0 : nsINode* parent = aNode->GetParentNode();
33 :
34 0 : if (parent) {
35 0 : *aOffset = parent->IndexOf(aNode);
36 0 : NS_WARNING_ASSERTION(*aOffset >= 0, "bad offset");
37 : }
38 :
39 0 : return parent;
40 : }
41 :
42 : ///////////////////////////////////////////////////////////////////////////
43 : // NodeIsInTraversalRange: returns true if content is visited during
44 : // the traversal of the range in the specified mode.
45 : //
46 : static bool
47 0 : NodeIsInTraversalRange(nsINode* aNode, bool aIsPreMode,
48 : nsINode* aStartContainer, int32_t aStartOffset,
49 : nsINode* aEndContainer, int32_t aEndOffset)
50 : {
51 0 : if (NS_WARN_IF(!aStartContainer) || NS_WARN_IF(!aEndContainer) ||
52 0 : NS_WARN_IF(!aNode)) {
53 0 : return false;
54 : }
55 :
56 : // If a leaf node contains an end point of the traversal range, it is
57 : // always in the traversal range.
58 0 : if (aNode == aStartContainer || aNode == aEndContainer) {
59 0 : if (aNode->IsNodeOfType(nsINode::eDATA_NODE)) {
60 0 : return true; // text node or something
61 : }
62 0 : if (!aNode->HasChildren()) {
63 0 : MOZ_ASSERT(aNode != aStartContainer || !aStartOffset,
64 : "aStartContainer doesn't have children and not a data node, "
65 : "aStartOffset should be 0");
66 0 : MOZ_ASSERT(aNode != aEndContainer || !aEndOffset,
67 : "aEndContainer doesn't have children and not a data node, "
68 : "aEndOffset should be 0");
69 0 : return true;
70 : }
71 : }
72 :
73 0 : nsINode* parent = aNode->GetParentNode();
74 0 : if (!parent) {
75 0 : return false;
76 : }
77 :
78 0 : int32_t indx = parent->IndexOf(aNode);
79 0 : NS_WARNING_ASSERTION(indx != -1, "bad indx");
80 :
81 0 : if (!aIsPreMode) {
82 0 : ++indx;
83 : }
84 :
85 0 : return nsContentUtils::ComparePoints(aStartContainer, aStartOffset,
86 0 : parent, indx) <= 0 &&
87 0 : nsContentUtils::ComparePoints(aEndContainer, aEndOffset,
88 0 : parent, indx) >= 0;
89 : }
90 :
91 :
92 :
93 : /*
94 : * A simple iterator class for traversing the content in "close tag" order
95 : */
96 : class nsContentIterator : public nsIContentIterator
97 : {
98 : public:
99 : NS_DECL_CYCLE_COLLECTING_ISUPPORTS
100 0 : NS_DECL_CYCLE_COLLECTION_CLASS(nsContentIterator)
101 :
102 : explicit nsContentIterator(bool aPre);
103 :
104 : // nsIContentIterator interface methods ------------------------------
105 :
106 : virtual nsresult Init(nsINode* aRoot) override;
107 :
108 : virtual nsresult Init(nsIDOMRange* aRange) override;
109 :
110 : virtual void First() override;
111 :
112 : virtual void Last() override;
113 :
114 : virtual void Next() override;
115 :
116 : virtual void Prev() override;
117 :
118 : virtual nsINode* GetCurrentNode() override;
119 :
120 : virtual bool IsDone() override;
121 :
122 : virtual nsresult PositionAt(nsINode* aCurNode) override;
123 :
124 : protected:
125 : virtual ~nsContentIterator();
126 :
127 : // Recursively get the deepest first/last child of aRoot. This will return
128 : // aRoot itself if it has no children.
129 : nsINode* GetDeepFirstChild(nsINode* aRoot,
130 : nsTArray<int32_t>* aIndexes = nullptr);
131 : nsIContent* GetDeepFirstChild(nsIContent* aRoot,
132 : nsTArray<int32_t>* aIndexes = nullptr);
133 : nsINode* GetDeepLastChild(nsINode* aRoot,
134 : nsTArray<int32_t>* aIndexes = nullptr);
135 : nsIContent* GetDeepLastChild(nsIContent* aRoot,
136 : nsTArray<int32_t>* aIndexes = nullptr);
137 :
138 : // Get the next/previous sibling of aNode, or its parent's, or grandparent's,
139 : // etc. Returns null if aNode and all its ancestors have no next/previous
140 : // sibling.
141 : nsIContent* GetNextSibling(nsINode* aNode,
142 : nsTArray<int32_t>* aIndexes = nullptr);
143 : nsIContent* GetPrevSibling(nsINode* aNode,
144 : nsTArray<int32_t>* aIndexes = nullptr);
145 :
146 : nsINode* NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
147 : nsINode* PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes = nullptr);
148 :
149 : // WARNING: This function is expensive
150 : nsresult RebuildIndexStack();
151 :
152 : void MakeEmpty();
153 :
154 : virtual void LastRelease();
155 :
156 : nsCOMPtr<nsINode> mCurNode;
157 : nsCOMPtr<nsINode> mFirst;
158 : nsCOMPtr<nsINode> mLast;
159 : nsCOMPtr<nsINode> mCommonParent;
160 :
161 : // used by nsContentIterator to cache indices
162 : AutoTArray<int32_t, 8> mIndexes;
163 :
164 : // used by nsSubtreeIterator to cache indices. Why put them in the base
165 : // class? Because otherwise I have to duplicate the routines GetNextSibling
166 : // etc across both classes, with slight variations for caching. Or
167 : // alternately, create a base class for the cache itself and have all the
168 : // cache manipulation go through a vptr. I think this is the best space and
169 : // speed combo, even though it's ugly.
170 : int32_t mCachedIndex;
171 : // another note about mCachedIndex: why should the subtree iterator use a
172 : // trivial cached index instead of the mre robust array of indicies (which is
173 : // what the basic content iterator uses)? The reason is that subtree
174 : // iterators do not do much transitioning between parents and children. They
175 : // tend to stay at the same level. In fact, you can prove (though I won't
176 : // attempt it here) that they change levels at most n+m times, where n is the
177 : // height of the parent hierarchy from the range start to the common
178 : // ancestor, and m is the the height of the parent hierarchy from the range
179 : // end to the common ancestor. If we used the index array, we would pay the
180 : // price up front for n, and then pay the cost for m on the fly later on.
181 : // With the simple cache, we only "pay as we go". Either way, we call
182 : // IndexOf() once for each change of level in the hierarchy. Since a trivial
183 : // index is much simpler, we use it for the subtree iterator.
184 :
185 : bool mIsDone;
186 : bool mPre;
187 :
188 : private:
189 :
190 : // no copies or assigns FIX ME
191 : nsContentIterator(const nsContentIterator&);
192 : nsContentIterator& operator=(const nsContentIterator&);
193 :
194 : };
195 :
196 :
197 : /******************************************************
198 : * repository cruft
199 : ******************************************************/
200 :
201 : already_AddRefed<nsIContentIterator>
202 0 : NS_NewContentIterator()
203 : {
204 0 : nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(false);
205 0 : return iter.forget();
206 : }
207 :
208 :
209 : already_AddRefed<nsIContentIterator>
210 0 : NS_NewPreContentIterator()
211 : {
212 0 : nsCOMPtr<nsIContentIterator> iter = new nsContentIterator(true);
213 0 : return iter.forget();
214 : }
215 :
216 :
217 : /******************************************************
218 : * XPCOM cruft
219 : ******************************************************/
220 :
221 0 : NS_IMPL_CYCLE_COLLECTING_ADDREF(nsContentIterator)
222 0 : NS_IMPL_CYCLE_COLLECTING_RELEASE_WITH_LAST_RELEASE(nsContentIterator,
223 : LastRelease())
224 :
225 0 : NS_INTERFACE_MAP_BEGIN(nsContentIterator)
226 0 : NS_INTERFACE_MAP_ENTRY(nsIContentIterator)
227 0 : NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIContentIterator)
228 0 : NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION(nsContentIterator)
229 0 : NS_INTERFACE_MAP_END
230 :
231 0 : NS_IMPL_CYCLE_COLLECTION(nsContentIterator,
232 : mCurNode,
233 : mFirst,
234 : mLast,
235 : mCommonParent)
236 :
237 : void
238 0 : nsContentIterator::LastRelease()
239 : {
240 0 : mCurNode = nullptr;
241 0 : mFirst = nullptr;
242 0 : mLast = nullptr;
243 0 : mCommonParent = nullptr;
244 0 : }
245 :
246 : /******************************************************
247 : * constructor/destructor
248 : ******************************************************/
249 :
250 0 : nsContentIterator::nsContentIterator(bool aPre) :
251 : // don't need to explicitly initialize |nsCOMPtr|s, they will automatically
252 : // be nullptr
253 0 : mCachedIndex(0), mIsDone(false), mPre(aPre)
254 : {
255 0 : }
256 :
257 :
258 0 : nsContentIterator::~nsContentIterator()
259 : {
260 0 : }
261 :
262 :
263 : /******************************************************
264 : * Init routines
265 : ******************************************************/
266 :
267 :
268 : nsresult
269 0 : nsContentIterator::Init(nsINode* aRoot)
270 : {
271 0 : if (NS_WARN_IF(!aRoot)) {
272 0 : return NS_ERROR_NULL_POINTER;
273 : }
274 :
275 0 : mIsDone = false;
276 0 : mIndexes.Clear();
277 :
278 0 : if (mPre) {
279 0 : mFirst = aRoot;
280 0 : mLast = GetDeepLastChild(aRoot);
281 0 : NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
282 : } else {
283 0 : mFirst = GetDeepFirstChild(aRoot);
284 0 : NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
285 0 : mLast = aRoot;
286 : }
287 :
288 0 : mCommonParent = aRoot;
289 0 : mCurNode = mFirst;
290 0 : RebuildIndexStack();
291 0 : return NS_OK;
292 : }
293 :
294 : nsresult
295 0 : nsContentIterator::Init(nsIDOMRange* aDOMRange)
296 : {
297 0 : if (NS_WARN_IF(!aDOMRange)) {
298 0 : return NS_ERROR_INVALID_ARG;
299 : }
300 0 : nsRange* range = static_cast<nsRange*>(aDOMRange);
301 :
302 0 : mIsDone = false;
303 :
304 : // get common content parent
305 0 : mCommonParent = range->GetCommonAncestor();
306 0 : if (NS_WARN_IF(!mCommonParent)) {
307 0 : return NS_ERROR_FAILURE;
308 : }
309 :
310 : // get the start node and offset
311 0 : int32_t startIndx = range->StartOffset();
312 0 : NS_WARNING_ASSERTION(startIndx >= 0, "bad startIndx");
313 0 : nsINode* startNode = range->GetStartContainer();
314 0 : if (NS_WARN_IF(!startNode)) {
315 0 : return NS_ERROR_FAILURE;
316 : }
317 :
318 : // get the end node and offset
319 0 : int32_t endIndx = range->EndOffset();
320 0 : NS_WARNING_ASSERTION(endIndx >= 0, "bad endIndx");
321 0 : nsINode* endNode = range->GetEndContainer();
322 0 : if (NS_WARN_IF(!endNode)) {
323 0 : return NS_ERROR_FAILURE;
324 : }
325 :
326 0 : bool startIsData = startNode->IsNodeOfType(nsINode::eDATA_NODE);
327 :
328 : // short circuit when start node == end node
329 0 : if (startNode == endNode) {
330 : // Check to see if we have a collapsed range, if so, there is nothing to
331 : // iterate over.
332 : //
333 : // XXX: CharacterDataNodes (text nodes) are currently an exception, since
334 : // we always want to be able to iterate text nodes at the end points
335 : // of a range.
336 :
337 0 : if (!startIsData && startIndx == endIndx) {
338 0 : MakeEmpty();
339 0 : return NS_OK;
340 : }
341 :
342 0 : if (startIsData) {
343 : // It's a character data node.
344 0 : mFirst = startNode->AsContent();
345 0 : mLast = mFirst;
346 0 : mCurNode = mFirst;
347 :
348 0 : DebugOnly<nsresult> rv = RebuildIndexStack();
349 0 : NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
350 0 : return NS_OK;
351 : }
352 : }
353 :
354 : // Find first node in range.
355 :
356 0 : nsIContent* cChild = nullptr;
357 :
358 : // Valid start indices are 0 <= startIndx <= childCount. That means if start
359 : // node has no children, only offset 0 is valid.
360 0 : if (!startIsData && uint32_t(startIndx) < startNode->GetChildCount()) {
361 0 : cChild = startNode->GetChildAt(startIndx);
362 0 : NS_WARNING_ASSERTION(cChild, "GetChildAt returned null");
363 : }
364 :
365 0 : if (!cChild) {
366 : // No children (possibly a <br> or text node), or index is after last child.
367 :
368 0 : if (mPre) {
369 : // XXX: In the future, if start offset is after the last
370 : // character in the cdata node, should we set mFirst to
371 : // the next sibling?
372 :
373 : // Normally we would skip the start node because the start node is outside
374 : // of the range in pre mode. However, if startIndx == 0, it means the node
375 : // has no children, and the node may be <br> or something. We don't skip
376 : // the node in this case in order to address bug 1215798.
377 0 : if (!startIsData && startIndx) {
378 0 : mFirst = GetNextSibling(startNode);
379 0 : NS_WARNING_ASSERTION(mFirst, "GetNextSibling returned null");
380 :
381 : // Does mFirst node really intersect the range? The range could be
382 : // 'degenerate', i.e., not collapsed but still contain no content.
383 0 : if (mFirst &&
384 0 : NS_WARN_IF(!NodeIsInTraversalRange(mFirst, mPre, startNode,
385 : startIndx, endNode, endIndx))) {
386 0 : mFirst = nullptr;
387 : }
388 : } else {
389 0 : mFirst = startNode->AsContent();
390 : }
391 : } else {
392 : // post-order
393 0 : if (NS_WARN_IF(!startNode->IsContent())) {
394 : // What else can we do?
395 0 : mFirst = nullptr;
396 : } else {
397 0 : mFirst = startNode->AsContent();
398 : }
399 : }
400 : } else {
401 0 : if (mPre) {
402 0 : mFirst = cChild;
403 : } else {
404 : // post-order
405 0 : mFirst = GetDeepFirstChild(cChild);
406 0 : NS_WARNING_ASSERTION(mFirst, "GetDeepFirstChild returned null");
407 :
408 : // Does mFirst node really intersect the range? The range could be
409 : // 'degenerate', i.e., not collapsed but still contain no content.
410 :
411 0 : if (mFirst &&
412 0 : !NodeIsInTraversalRange(mFirst, mPre, startNode, startIndx,
413 0 : endNode, endIndx)) {
414 0 : mFirst = nullptr;
415 : }
416 : }
417 : }
418 :
419 :
420 : // Find last node in range.
421 :
422 0 : bool endIsData = endNode->IsNodeOfType(nsINode::eDATA_NODE);
423 :
424 0 : if (endIsData || !endNode->HasChildren() || endIndx == 0) {
425 0 : if (mPre) {
426 0 : if (NS_WARN_IF(!endNode->IsContent())) {
427 : // Not much else to do here...
428 0 : mLast = nullptr;
429 : } else {
430 : // If the end node is an empty element and the end offset is 0,
431 : // the last element should be the previous node (i.e., shouldn't
432 : // include the end node in the range).
433 0 : if (!endIsData && !endNode->HasChildren() && !endIndx) {
434 0 : mLast = PrevNode(endNode);
435 0 : NS_WARNING_ASSERTION(mLast, "PrevNode returned null");
436 0 : if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
437 : startNode, startIndx,
438 : endNode, endIndx))) {
439 0 : mLast = nullptr;
440 : }
441 : } else {
442 0 : mLast = endNode->AsContent();
443 : }
444 : }
445 : } else {
446 : // post-order
447 : //
448 : // XXX: In the future, if end offset is before the first character in the
449 : // cdata node, should we set mLast to the prev sibling?
450 :
451 0 : if (!endIsData) {
452 0 : mLast = GetPrevSibling(endNode);
453 0 : NS_WARNING_ASSERTION(mLast, "GetPrevSibling returned null");
454 :
455 0 : if (!NodeIsInTraversalRange(mLast, mPre,
456 : startNode, startIndx,
457 : endNode, endIndx)) {
458 0 : mLast = nullptr;
459 : }
460 : } else {
461 0 : mLast = endNode->AsContent();
462 : }
463 : }
464 : } else {
465 0 : int32_t indx = endIndx;
466 :
467 0 : cChild = endNode->GetChildAt(--indx);
468 :
469 0 : if (NS_WARN_IF(!cChild)) {
470 : // No child at offset!
471 0 : NS_NOTREACHED("nsContentIterator::nsContentIterator");
472 0 : return NS_ERROR_FAILURE;
473 : }
474 :
475 0 : if (mPre) {
476 0 : mLast = GetDeepLastChild(cChild);
477 0 : NS_WARNING_ASSERTION(mLast, "GetDeepLastChild returned null");
478 :
479 0 : if (NS_WARN_IF(!NodeIsInTraversalRange(mLast, mPre,
480 : startNode, startIndx,
481 : endNode, endIndx))) {
482 0 : mLast = nullptr;
483 : }
484 : } else {
485 : // post-order
486 0 : mLast = cChild;
487 : }
488 : }
489 :
490 : // If either first or last is null, they both have to be null!
491 :
492 0 : if (!mFirst || !mLast) {
493 0 : mFirst = nullptr;
494 0 : mLast = nullptr;
495 : }
496 :
497 0 : mCurNode = mFirst;
498 0 : mIsDone = !mCurNode;
499 :
500 0 : if (!mCurNode) {
501 0 : mIndexes.Clear();
502 : } else {
503 0 : DebugOnly<nsresult> rv = RebuildIndexStack();
504 0 : NS_WARNING_ASSERTION(NS_SUCCEEDED(rv), "RebuildIndexStack failed");
505 : }
506 :
507 0 : return NS_OK;
508 : }
509 :
510 :
511 : /******************************************************
512 : * Helper routines
513 : ******************************************************/
514 : // WARNING: This function is expensive
515 : nsresult
516 0 : nsContentIterator::RebuildIndexStack()
517 : {
518 : // Make sure we start at the right indexes on the stack! Build array up
519 : // to common parent of start and end. Perhaps it's too many entries, but
520 : // that's far better than too few.
521 : nsINode* parent;
522 : nsINode* current;
523 :
524 0 : mIndexes.Clear();
525 0 : current = mCurNode;
526 0 : if (!current) {
527 0 : return NS_OK;
528 : }
529 :
530 0 : while (current != mCommonParent) {
531 0 : parent = current->GetParentNode();
532 :
533 0 : if (NS_WARN_IF(!parent)) {
534 0 : return NS_ERROR_FAILURE;
535 : }
536 :
537 0 : mIndexes.InsertElementAt(0, parent->IndexOf(current));
538 :
539 0 : current = parent;
540 : }
541 :
542 0 : return NS_OK;
543 : }
544 :
545 : void
546 0 : nsContentIterator::MakeEmpty()
547 : {
548 0 : mCurNode = nullptr;
549 0 : mFirst = nullptr;
550 0 : mLast = nullptr;
551 0 : mCommonParent = nullptr;
552 0 : mIsDone = true;
553 0 : mIndexes.Clear();
554 0 : }
555 :
556 : nsINode*
557 0 : nsContentIterator::GetDeepFirstChild(nsINode* aRoot,
558 : nsTArray<int32_t>* aIndexes)
559 : {
560 0 : if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
561 0 : return aRoot;
562 : }
563 : // We can't pass aRoot itself to the full GetDeepFirstChild, because that
564 : // will only take nsIContent and aRoot might be a document. Pass aRoot's
565 : // child, but be sure to preserve aIndexes.
566 0 : if (aIndexes) {
567 0 : aIndexes->AppendElement(0);
568 : }
569 0 : return GetDeepFirstChild(aRoot->GetFirstChild(), aIndexes);
570 : }
571 :
572 : nsIContent*
573 0 : nsContentIterator::GetDeepFirstChild(nsIContent* aRoot,
574 : nsTArray<int32_t>* aIndexes)
575 : {
576 0 : if (NS_WARN_IF(!aRoot)) {
577 0 : return nullptr;
578 : }
579 :
580 0 : nsIContent* node = aRoot;
581 0 : nsIContent* child = node->GetFirstChild();
582 :
583 0 : while (child) {
584 0 : if (aIndexes) {
585 : // Add this node to the stack of indexes
586 0 : aIndexes->AppendElement(0);
587 : }
588 0 : node = child;
589 0 : child = node->GetFirstChild();
590 : }
591 :
592 0 : return node;
593 : }
594 :
595 : nsINode*
596 0 : nsContentIterator::GetDeepLastChild(nsINode* aRoot,
597 : nsTArray<int32_t>* aIndexes)
598 : {
599 0 : if (NS_WARN_IF(!aRoot) || !aRoot->HasChildren()) {
600 0 : return aRoot;
601 : }
602 : // We can't pass aRoot itself to the full GetDeepLastChild, because that will
603 : // only take nsIContent and aRoot might be a document. Pass aRoot's child,
604 : // but be sure to preserve aIndexes.
605 0 : if (aIndexes) {
606 0 : aIndexes->AppendElement(aRoot->GetChildCount() - 1);
607 : }
608 0 : return GetDeepLastChild(aRoot->GetLastChild(), aIndexes);
609 : }
610 :
611 : nsIContent*
612 0 : nsContentIterator::GetDeepLastChild(nsIContent* aRoot,
613 : nsTArray<int32_t>* aIndexes)
614 : {
615 0 : if (NS_WARN_IF(!aRoot)) {
616 0 : return nullptr;
617 : }
618 :
619 0 : nsIContent* node = aRoot;
620 0 : int32_t numChildren = node->GetChildCount();
621 :
622 0 : while (numChildren) {
623 0 : nsIContent* child = node->GetChildAt(--numChildren);
624 :
625 0 : if (aIndexes) {
626 : // Add this node to the stack of indexes
627 0 : aIndexes->AppendElement(numChildren);
628 : }
629 0 : numChildren = child->GetChildCount();
630 0 : node = child;
631 : }
632 :
633 0 : return node;
634 : }
635 :
636 : // Get the next sibling, or parent's next sibling, or grandpa's next sibling...
637 : nsIContent*
638 0 : nsContentIterator::GetNextSibling(nsINode* aNode,
639 : nsTArray<int32_t>* aIndexes)
640 : {
641 0 : if (NS_WARN_IF(!aNode)) {
642 0 : return nullptr;
643 : }
644 :
645 0 : nsINode* parent = aNode->GetParentNode();
646 0 : if (NS_WARN_IF(!parent)) {
647 0 : return nullptr;
648 : }
649 :
650 0 : int32_t indx = 0;
651 :
652 0 : NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
653 : "ContentIterator stack underflow");
654 0 : if (aIndexes && !aIndexes->IsEmpty()) {
655 : // use the last entry on the Indexes array for the current index
656 0 : indx = (*aIndexes)[aIndexes->Length()-1];
657 : } else {
658 0 : indx = mCachedIndex;
659 : }
660 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
661 :
662 : // reverify that the index of the current node hasn't changed.
663 : // not super cheap, but a lot cheaper than IndexOf(), and still O(1).
664 : // ignore result this time - the index may now be out of range.
665 0 : nsIContent* sib = parent->GetChildAt(indx);
666 0 : if (sib != aNode) {
667 : // someone changed our index - find the new index the painful way
668 0 : indx = parent->IndexOf(aNode);
669 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
670 : }
671 :
672 : // indx is now canonically correct
673 0 : if ((sib = parent->GetChildAt(++indx))) {
674 : // update index cache
675 0 : if (aIndexes && !aIndexes->IsEmpty()) {
676 0 : aIndexes->ElementAt(aIndexes->Length()-1) = indx;
677 : } else {
678 0 : mCachedIndex = indx;
679 : }
680 : } else {
681 0 : if (parent != mCommonParent) {
682 0 : if (aIndexes) {
683 : // pop node off the stack, go up one level and return parent or fail.
684 : // Don't leave the index empty, especially if we're
685 : // returning nullptr. This confuses other parts of the code.
686 0 : if (aIndexes->Length() > 1) {
687 0 : aIndexes->RemoveElementAt(aIndexes->Length()-1);
688 : }
689 : }
690 : }
691 :
692 : // ok to leave cache out of date here if parent == mCommonParent?
693 0 : sib = GetNextSibling(parent, aIndexes);
694 : }
695 :
696 0 : return sib;
697 : }
698 :
699 : // Get the prev sibling, or parent's prev sibling, or grandpa's prev sibling...
700 : nsIContent*
701 0 : nsContentIterator::GetPrevSibling(nsINode* aNode,
702 : nsTArray<int32_t>* aIndexes)
703 : {
704 0 : if (NS_WARN_IF(!aNode)) {
705 0 : return nullptr;
706 : }
707 :
708 0 : nsINode* parent = aNode->GetParentNode();
709 0 : if (NS_WARN_IF(!parent)) {
710 0 : return nullptr;
711 : }
712 :
713 0 : int32_t indx = 0;
714 :
715 0 : NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
716 : "ContentIterator stack underflow");
717 0 : if (aIndexes && !aIndexes->IsEmpty()) {
718 : // use the last entry on the Indexes array for the current index
719 0 : indx = (*aIndexes)[aIndexes->Length()-1];
720 : } else {
721 0 : indx = mCachedIndex;
722 : }
723 :
724 : // reverify that the index of the current node hasn't changed
725 : // ignore result this time - the index may now be out of range.
726 0 : nsIContent* sib = parent->GetChildAt(indx);
727 0 : if (sib != aNode) {
728 : // someone changed our index - find the new index the painful way
729 0 : indx = parent->IndexOf(aNode);
730 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
731 : }
732 :
733 : // indx is now canonically correct
734 0 : if (indx > 0 && (sib = parent->GetChildAt(--indx))) {
735 : // update index cache
736 0 : if (aIndexes && !aIndexes->IsEmpty()) {
737 0 : aIndexes->ElementAt(aIndexes->Length()-1) = indx;
738 : } else {
739 0 : mCachedIndex = indx;
740 : }
741 0 : } else if (parent != mCommonParent) {
742 0 : if (aIndexes && !aIndexes->IsEmpty()) {
743 : // pop node off the stack, go up one level and try again.
744 0 : aIndexes->RemoveElementAt(aIndexes->Length()-1);
745 : }
746 0 : return GetPrevSibling(parent, aIndexes);
747 : }
748 :
749 0 : return sib;
750 : }
751 :
752 : nsINode*
753 0 : nsContentIterator::NextNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
754 : {
755 0 : nsINode* node = aNode;
756 :
757 : // if we are a Pre-order iterator, use pre-order
758 0 : if (mPre) {
759 : // if it has children then next node is first child
760 0 : if (node->HasChildren()) {
761 0 : nsIContent* firstChild = node->GetFirstChild();
762 0 : MOZ_ASSERT(firstChild);
763 :
764 : // update cache
765 0 : if (aIndexes) {
766 : // push an entry on the index stack
767 0 : aIndexes->AppendElement(0);
768 : } else {
769 0 : mCachedIndex = 0;
770 : }
771 :
772 0 : return firstChild;
773 : }
774 :
775 : // else next sibling is next
776 0 : return GetNextSibling(node, aIndexes);
777 : }
778 :
779 : // post-order
780 0 : nsINode* parent = node->GetParentNode();
781 0 : if (NS_WARN_IF(!parent)) {
782 0 : MOZ_ASSERT(parent, "The node is the root node but not the last node");
783 0 : mIsDone = true;
784 0 : return node;
785 : }
786 0 : nsIContent* sibling = nullptr;
787 0 : int32_t indx = 0;
788 :
789 : // get the cached index
790 0 : NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
791 : "ContentIterator stack underflow");
792 0 : if (aIndexes && !aIndexes->IsEmpty()) {
793 : // use the last entry on the Indexes array for the current index
794 0 : indx = (*aIndexes)[aIndexes->Length()-1];
795 : } else {
796 0 : indx = mCachedIndex;
797 : }
798 :
799 : // reverify that the index of the current node hasn't changed. not super
800 : // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
801 : // this time - the index may now be out of range.
802 0 : if (indx >= 0) {
803 0 : sibling = parent->GetChildAt(indx);
804 : }
805 0 : if (sibling != node) {
806 : // someone changed our index - find the new index the painful way
807 0 : indx = parent->IndexOf(node);
808 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
809 : }
810 :
811 : // indx is now canonically correct
812 0 : sibling = parent->GetChildAt(++indx);
813 0 : if (sibling) {
814 : // update cache
815 0 : if (aIndexes && !aIndexes->IsEmpty()) {
816 : // replace an entry on the index stack
817 0 : aIndexes->ElementAt(aIndexes->Length()-1) = indx;
818 : } else {
819 0 : mCachedIndex = indx;
820 : }
821 :
822 : // next node is sibling's "deep left" child
823 0 : return GetDeepFirstChild(sibling, aIndexes);
824 : }
825 :
826 : // else it's the parent, update cache
827 0 : if (aIndexes) {
828 : // Pop an entry off the index stack. Don't leave the index empty,
829 : // especially if we're returning nullptr. This confuses other parts of the
830 : // code.
831 0 : if (aIndexes->Length() > 1) {
832 0 : aIndexes->RemoveElementAt(aIndexes->Length()-1);
833 : }
834 : } else {
835 : // this might be wrong, but we are better off guessing
836 0 : mCachedIndex = 0;
837 : }
838 :
839 0 : return parent;
840 : }
841 :
842 : nsINode*
843 0 : nsContentIterator::PrevNode(nsINode* aNode, nsTArray<int32_t>* aIndexes)
844 : {
845 0 : nsINode* node = aNode;
846 :
847 : // if we are a Pre-order iterator, use pre-order
848 0 : if (mPre) {
849 0 : nsINode* parent = node->GetParentNode();
850 0 : if (NS_WARN_IF(!parent)) {
851 0 : MOZ_ASSERT(parent, "The node is the root node but not the first node");
852 0 : mIsDone = true;
853 0 : return aNode;
854 : }
855 0 : nsIContent* sibling = nullptr;
856 0 : int32_t indx = 0;
857 :
858 : // get the cached index
859 0 : NS_ASSERTION(!aIndexes || !aIndexes->IsEmpty(),
860 : "ContentIterator stack underflow");
861 0 : if (aIndexes && !aIndexes->IsEmpty()) {
862 : // use the last entry on the Indexes array for the current index
863 0 : indx = (*aIndexes)[aIndexes->Length()-1];
864 : } else {
865 0 : indx = mCachedIndex;
866 : }
867 :
868 : // reverify that the index of the current node hasn't changed. not super
869 : // cheap, but a lot cheaper than IndexOf(), and still O(1). ignore result
870 : // this time - the index may now be out of range.
871 0 : if (indx >= 0) {
872 0 : sibling = parent->GetChildAt(indx);
873 0 : NS_WARNING_ASSERTION(sibling, "GetChildAt returned null");
874 : }
875 :
876 0 : if (sibling != node) {
877 : // someone changed our index - find the new index the painful way
878 0 : indx = parent->IndexOf(node);
879 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
880 : }
881 :
882 : // indx is now canonically correct
883 0 : if (indx && (sibling = parent->GetChildAt(--indx))) {
884 : // update cache
885 0 : if (aIndexes && !aIndexes->IsEmpty()) {
886 : // replace an entry on the index stack
887 0 : aIndexes->ElementAt(aIndexes->Length()-1) = indx;
888 : } else {
889 0 : mCachedIndex = indx;
890 : }
891 :
892 : // prev node is sibling's "deep right" child
893 0 : return GetDeepLastChild(sibling, aIndexes);
894 : }
895 :
896 : // else it's the parent, update cache
897 0 : if (aIndexes && !aIndexes->IsEmpty()) {
898 : // pop an entry off the index stack
899 0 : aIndexes->RemoveElementAt(aIndexes->Length()-1);
900 : } else {
901 : // this might be wrong, but we are better off guessing
902 0 : mCachedIndex = 0;
903 : }
904 0 : return parent;
905 : }
906 :
907 : // post-order
908 0 : int32_t numChildren = node->GetChildCount();
909 0 : NS_WARNING_ASSERTION(numChildren >= 0, "no children");
910 :
911 : // if it has children then prev node is last child
912 0 : if (numChildren) {
913 0 : nsIContent* lastChild = node->GetLastChild();
914 0 : NS_WARNING_ASSERTION(lastChild, "GetLastChild returned null");
915 0 : numChildren--;
916 :
917 : // update cache
918 0 : if (aIndexes) {
919 : // push an entry on the index stack
920 0 : aIndexes->AppendElement(numChildren);
921 : } else {
922 0 : mCachedIndex = numChildren;
923 : }
924 :
925 0 : return lastChild;
926 : }
927 :
928 : // else prev sibling is previous
929 0 : return GetPrevSibling(node, aIndexes);
930 : }
931 :
932 : /******************************************************
933 : * ContentIterator routines
934 : ******************************************************/
935 :
936 : void
937 0 : nsContentIterator::First()
938 : {
939 0 : if (mFirst) {
940 0 : mozilla::DebugOnly<nsresult> rv = PositionAt(mFirst);
941 0 : NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
942 : }
943 :
944 0 : mIsDone = mFirst == nullptr;
945 0 : }
946 :
947 :
948 : void
949 0 : nsContentIterator::Last()
950 : {
951 : // Note that mLast can be nullptr if MakeEmpty() is called in Init() since
952 : // at that time, Init() returns NS_OK.
953 0 : if (!mLast) {
954 0 : MOZ_ASSERT(mIsDone);
955 0 : return;
956 : }
957 :
958 0 : mozilla::DebugOnly<nsresult> rv = PositionAt(mLast);
959 0 : NS_ASSERTION(NS_SUCCEEDED(rv), "Failed to position iterator!");
960 :
961 0 : mIsDone = mLast == nullptr;
962 : }
963 :
964 :
965 : void
966 0 : nsContentIterator::Next()
967 : {
968 0 : if (mIsDone || NS_WARN_IF(!mCurNode)) {
969 0 : return;
970 : }
971 :
972 0 : if (mCurNode == mLast) {
973 0 : mIsDone = true;
974 0 : return;
975 : }
976 :
977 0 : mCurNode = NextNode(mCurNode, &mIndexes);
978 : }
979 :
980 :
981 : void
982 0 : nsContentIterator::Prev()
983 : {
984 0 : if (NS_WARN_IF(mIsDone) || NS_WARN_IF(!mCurNode)) {
985 0 : return;
986 : }
987 :
988 0 : if (mCurNode == mFirst) {
989 0 : mIsDone = true;
990 0 : return;
991 : }
992 :
993 0 : mCurNode = PrevNode(mCurNode, &mIndexes);
994 : }
995 :
996 :
997 : bool
998 0 : nsContentIterator::IsDone()
999 : {
1000 0 : return mIsDone;
1001 : }
1002 :
1003 :
1004 : // Keeping arrays of indexes for the stack of nodes makes PositionAt
1005 : // interesting...
1006 : nsresult
1007 0 : nsContentIterator::PositionAt(nsINode* aCurNode)
1008 : {
1009 0 : if (NS_WARN_IF(!aCurNode)) {
1010 0 : return NS_ERROR_NULL_POINTER;
1011 : }
1012 :
1013 0 : nsINode* newCurNode = aCurNode;
1014 0 : nsINode* tempNode = mCurNode;
1015 :
1016 0 : mCurNode = aCurNode;
1017 : // take an early out if this doesn't actually change the position
1018 0 : if (mCurNode == tempNode) {
1019 0 : mIsDone = false; // paranoia
1020 0 : return NS_OK;
1021 : }
1022 :
1023 : // Check to see if the node falls within the traversal range.
1024 :
1025 0 : nsINode* firstNode = mFirst;
1026 0 : nsINode* lastNode = mLast;
1027 0 : int32_t firstOffset = 0, lastOffset = 0;
1028 :
1029 0 : if (firstNode && lastNode) {
1030 0 : if (mPre) {
1031 0 : firstNode = NodeToParentOffset(mFirst, &firstOffset);
1032 0 : NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
1033 0 : NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1034 :
1035 0 : if (lastNode->GetChildCount()) {
1036 0 : lastOffset = 0;
1037 : } else {
1038 0 : lastNode = NodeToParentOffset(mLast, &lastOffset);
1039 0 : NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
1040 0 : NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
1041 0 : ++lastOffset;
1042 : }
1043 : } else {
1044 0 : uint32_t numChildren = firstNode->GetChildCount();
1045 :
1046 0 : if (numChildren) {
1047 0 : firstOffset = numChildren;
1048 0 : NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1049 : } else {
1050 0 : firstNode = NodeToParentOffset(mFirst, &firstOffset);
1051 0 : NS_WARNING_ASSERTION(firstNode, "NodeToParentOffset returned null");
1052 0 : NS_WARNING_ASSERTION(firstOffset >= 0, "bad firstOffset");
1053 : }
1054 :
1055 0 : lastNode = NodeToParentOffset(mLast, &lastOffset);
1056 0 : NS_WARNING_ASSERTION(lastNode, "NodeToParentOffset returned null");
1057 0 : NS_WARNING_ASSERTION(lastOffset >= 0, "bad lastOffset");
1058 0 : ++lastOffset;
1059 : }
1060 : }
1061 :
1062 : // The end positions are always in the range even if it has no parent. We
1063 : // need to allow that or 'iter->Init(root)' would assert in Last() or First()
1064 : // for example, bug 327694.
1065 0 : if (mFirst != mCurNode && mLast != mCurNode &&
1066 0 : (NS_WARN_IF(!firstNode) || NS_WARN_IF(!lastNode) ||
1067 0 : NS_WARN_IF(!NodeIsInTraversalRange(mCurNode, mPre,
1068 : firstNode, firstOffset,
1069 : lastNode, lastOffset)))) {
1070 0 : mIsDone = true;
1071 0 : return NS_ERROR_FAILURE;
1072 : }
1073 :
1074 : // We can be at ANY node in the sequence. Need to regenerate the array of
1075 : // indexes back to the root or common parent!
1076 0 : AutoTArray<nsINode*, 8> oldParentStack;
1077 0 : AutoTArray<int32_t, 8> newIndexes;
1078 :
1079 : // Get a list of the parents up to the root, then compare the new node with
1080 : // entries in that array until we find a match (lowest common ancestor). If
1081 : // no match, use IndexOf, take the parent, and repeat. This avoids using
1082 : // IndexOf() N times on possibly large arrays. We still end up doing it a
1083 : // fair bit. It's better to use Clone() if possible.
1084 :
1085 : // we know the depth we're down (though we may not have started at the top).
1086 0 : oldParentStack.SetCapacity(mIndexes.Length() + 1);
1087 :
1088 : // We want to loop mIndexes.Length() + 1 times here, because we want to make
1089 : // sure we include mCommonParent in the oldParentStack, for use in the next
1090 : // for loop, and mIndexes only has entries for nodes from tempNode up through
1091 : // an ancestor of tempNode that's a child of mCommonParent.
1092 0 : for (int32_t i = mIndexes.Length() + 1; i > 0 && tempNode; i--) {
1093 : // Insert at head since we're walking up
1094 0 : oldParentStack.InsertElementAt(0, tempNode);
1095 :
1096 0 : nsINode* parent = tempNode->GetParentNode();
1097 :
1098 0 : if (NS_WARN_IF(!parent)) {
1099 : // this node has no parent, and thus no index
1100 0 : break;
1101 : }
1102 :
1103 0 : if (parent == mCurNode) {
1104 : // The position was moved to a parent of the current position. All we
1105 : // need to do is drop some indexes. Shortcut here.
1106 0 : mIndexes.RemoveElementsAt(mIndexes.Length() - oldParentStack.Length(),
1107 0 : oldParentStack.Length());
1108 0 : mIsDone = false;
1109 0 : return NS_OK;
1110 : }
1111 0 : tempNode = parent;
1112 : }
1113 :
1114 : // Ok. We have the array of old parents. Look for a match.
1115 0 : while (newCurNode) {
1116 0 : nsINode* parent = newCurNode->GetParentNode();
1117 :
1118 0 : if (NS_WARN_IF(!parent)) {
1119 : // this node has no parent, and thus no index
1120 0 : break;
1121 : }
1122 :
1123 0 : int32_t indx = parent->IndexOf(newCurNode);
1124 0 : NS_WARNING_ASSERTION(indx >= 0, "bad indx");
1125 :
1126 : // insert at the head!
1127 0 : newIndexes.InsertElementAt(0, indx);
1128 :
1129 : // look to see if the parent is in the stack
1130 0 : indx = oldParentStack.IndexOf(parent);
1131 0 : if (indx >= 0) {
1132 : // ok, the parent IS on the old stack! Rework things. We want
1133 : // newIndexes to replace all nodes equal to or below the match. Note
1134 : // that index oldParentStack.Length() - 1 is the last node, which is one
1135 : // BELOW the last index in the mIndexes stack. In other words, we want
1136 : // to remove elements starting at index (indx + 1).
1137 0 : int32_t numToDrop = oldParentStack.Length() - (1 + indx);
1138 0 : if (numToDrop > 0) {
1139 0 : mIndexes.RemoveElementsAt(mIndexes.Length() - numToDrop, numToDrop);
1140 : }
1141 0 : mIndexes.AppendElements(newIndexes);
1142 :
1143 0 : break;
1144 : }
1145 0 : newCurNode = parent;
1146 : }
1147 :
1148 : // phew!
1149 :
1150 0 : mIsDone = false;
1151 0 : return NS_OK;
1152 : }
1153 :
1154 : nsINode*
1155 0 : nsContentIterator::GetCurrentNode()
1156 : {
1157 0 : if (mIsDone) {
1158 0 : return nullptr;
1159 : }
1160 :
1161 0 : NS_ASSERTION(mCurNode, "Null current node in an iterator that's not done!");
1162 :
1163 0 : return mCurNode;
1164 : }
1165 :
1166 :
1167 :
1168 :
1169 :
1170 : /*====================================================================================*/
1171 : /*====================================================================================*/
1172 :
1173 :
1174 :
1175 :
1176 :
1177 :
1178 : /******************************************************
1179 : * nsContentSubtreeIterator
1180 : ******************************************************/
1181 :
1182 :
1183 : /*
1184 : * A simple iterator class for traversing the content in "top subtree" order
1185 : */
1186 : class nsContentSubtreeIterator : public nsContentIterator
1187 : {
1188 : public:
1189 0 : nsContentSubtreeIterator() : nsContentIterator(false) {}
1190 :
1191 : NS_DECL_ISUPPORTS_INHERITED
1192 0 : NS_DECL_CYCLE_COLLECTION_CLASS_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1193 :
1194 : // nsContentIterator overrides ------------------------------
1195 :
1196 : virtual nsresult Init(nsINode* aRoot) override;
1197 :
1198 : virtual nsresult Init(nsIDOMRange* aRange) override;
1199 :
1200 : virtual void Next() override;
1201 :
1202 : virtual void Prev() override;
1203 :
1204 : virtual nsresult PositionAt(nsINode* aCurNode) override;
1205 :
1206 : // Must override these because we don't do PositionAt
1207 : virtual void First() override;
1208 :
1209 : // Must override these because we don't do PositionAt
1210 : virtual void Last() override;
1211 :
1212 : protected:
1213 0 : virtual ~nsContentSubtreeIterator() {}
1214 :
1215 : // Returns the highest inclusive ancestor of aNode that's in the range
1216 : // (possibly aNode itself). Returns null if aNode is null, or is not itself
1217 : // in the range. A node is in the range if (node, 0) comes strictly after
1218 : // the range endpoint, and (node, node.length) comes strictly before it, so
1219 : // the range's start and end nodes will never be considered "in" it.
1220 : nsIContent* GetTopAncestorInRange(nsINode* aNode);
1221 :
1222 : // no copy's or assigns FIX ME
1223 : nsContentSubtreeIterator(const nsContentSubtreeIterator&);
1224 : nsContentSubtreeIterator& operator=(const nsContentSubtreeIterator&);
1225 :
1226 : virtual void LastRelease() override;
1227 :
1228 : RefPtr<nsRange> mRange;
1229 :
1230 : // these arrays all typically are used and have elements
1231 : AutoTArray<nsIContent*, 8> mEndNodes;
1232 : AutoTArray<int32_t, 8> mEndOffsets;
1233 : };
1234 :
1235 0 : NS_IMPL_ADDREF_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1236 0 : NS_IMPL_RELEASE_INHERITED(nsContentSubtreeIterator, nsContentIterator)
1237 :
1238 0 : NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator)
1239 0 : NS_INTERFACE_MAP_END_INHERITING(nsContentIterator)
1240 :
1241 0 : NS_IMPL_CYCLE_COLLECTION_INHERITED(nsContentSubtreeIterator, nsContentIterator,
1242 : mRange)
1243 :
1244 : void
1245 0 : nsContentSubtreeIterator::LastRelease()
1246 : {
1247 0 : mRange = nullptr;
1248 0 : nsContentIterator::LastRelease();
1249 0 : }
1250 :
1251 : /******************************************************
1252 : * repository cruft
1253 : ******************************************************/
1254 :
1255 : already_AddRefed<nsIContentIterator>
1256 0 : NS_NewContentSubtreeIterator()
1257 : {
1258 0 : nsCOMPtr<nsIContentIterator> iter = new nsContentSubtreeIterator();
1259 0 : return iter.forget();
1260 : }
1261 :
1262 :
1263 :
1264 : /******************************************************
1265 : * Init routines
1266 : ******************************************************/
1267 :
1268 :
1269 : nsresult
1270 0 : nsContentSubtreeIterator::Init(nsINode* aRoot)
1271 : {
1272 0 : return NS_ERROR_NOT_IMPLEMENTED;
1273 : }
1274 :
1275 :
1276 : nsresult
1277 0 : nsContentSubtreeIterator::Init(nsIDOMRange* aRange)
1278 : {
1279 0 : MOZ_ASSERT(aRange);
1280 :
1281 0 : mIsDone = false;
1282 :
1283 0 : mRange = static_cast<nsRange*>(aRange);
1284 :
1285 : // get the start node and offset, convert to nsINode
1286 0 : mCommonParent = mRange->GetCommonAncestor();
1287 0 : nsINode* startContainer = mRange->GetStartContainer();
1288 0 : int32_t startOffset = mRange->StartOffset();
1289 0 : nsINode* endContainer = mRange->GetEndContainer();
1290 0 : int32_t endOffset = mRange->EndOffset();
1291 0 : MOZ_ASSERT(mCommonParent && startContainer && endContainer);
1292 : // Bug 767169
1293 0 : MOZ_ASSERT(uint32_t(startOffset) <= startContainer->Length() &&
1294 : uint32_t(endOffset) <= endContainer->Length());
1295 :
1296 : // short circuit when start node == end node
1297 0 : if (startContainer == endContainer) {
1298 0 : nsINode* child = startContainer->GetFirstChild();
1299 :
1300 0 : if (!child || startOffset == endOffset) {
1301 : // Text node, empty container, or collapsed
1302 0 : MakeEmpty();
1303 0 : return NS_OK;
1304 : }
1305 : }
1306 :
1307 : // cache ancestors
1308 0 : nsContentUtils::GetAncestorsAndOffsets(endContainer->AsDOMNode(), endOffset,
1309 0 : &mEndNodes, &mEndOffsets);
1310 :
1311 0 : nsIContent* firstCandidate = nullptr;
1312 0 : nsIContent* lastCandidate = nullptr;
1313 :
1314 : // find first node in range
1315 0 : int32_t offset = mRange->StartOffset();
1316 :
1317 0 : nsINode* node = nullptr;
1318 0 : if (!startContainer->GetChildCount()) {
1319 : // no children, start at the node itself
1320 0 : node = startContainer;
1321 : } else {
1322 0 : nsIContent* child = startContainer->GetChildAt(offset);
1323 0 : if (!child) {
1324 : // offset after last child
1325 0 : node = startContainer;
1326 : } else {
1327 0 : firstCandidate = child;
1328 : }
1329 : }
1330 :
1331 0 : if (!firstCandidate) {
1332 : // then firstCandidate is next node after node
1333 0 : firstCandidate = GetNextSibling(node);
1334 :
1335 0 : if (!firstCandidate) {
1336 0 : MakeEmpty();
1337 0 : return NS_OK;
1338 : }
1339 : }
1340 :
1341 0 : firstCandidate = GetDeepFirstChild(firstCandidate);
1342 :
1343 : // confirm that this first possible contained node is indeed contained. Else
1344 : // we have a range that does not fully contain any node.
1345 :
1346 : bool nodeBefore, nodeAfter;
1347 0 : MOZ_ALWAYS_SUCCEEDS(
1348 : nsRange::CompareNodeToRange(firstCandidate, mRange, &nodeBefore, &nodeAfter));
1349 :
1350 0 : if (nodeBefore || nodeAfter) {
1351 0 : MakeEmpty();
1352 0 : return NS_OK;
1353 : }
1354 :
1355 : // cool, we have the first node in the range. Now we walk up its ancestors
1356 : // to find the most senior that is still in the range. That's the real first
1357 : // node.
1358 0 : mFirst = GetTopAncestorInRange(firstCandidate);
1359 :
1360 : // now to find the last node
1361 0 : offset = mRange->EndOffset();
1362 0 : int32_t numChildren = endContainer->GetChildCount();
1363 :
1364 0 : if (offset > numChildren) {
1365 : // Can happen for text nodes
1366 0 : offset = numChildren;
1367 : }
1368 0 : if (!offset || !numChildren) {
1369 0 : node = endContainer;
1370 : } else {
1371 0 : lastCandidate = endContainer->GetChildAt(--offset);
1372 0 : NS_ASSERTION(lastCandidate,
1373 : "tree traversal trouble in nsContentSubtreeIterator::Init");
1374 : }
1375 :
1376 0 : if (!lastCandidate) {
1377 : // then lastCandidate is prev node before node
1378 0 : lastCandidate = GetPrevSibling(node);
1379 : }
1380 :
1381 0 : if (!lastCandidate) {
1382 0 : MakeEmpty();
1383 0 : return NS_OK;
1384 : }
1385 :
1386 0 : lastCandidate = GetDeepLastChild(lastCandidate);
1387 :
1388 : // confirm that this last possible contained node is indeed contained. Else
1389 : // we have a range that does not fully contain any node.
1390 :
1391 0 : MOZ_ALWAYS_SUCCEEDS(
1392 : nsRange::CompareNodeToRange(lastCandidate, mRange, &nodeBefore, &nodeAfter));
1393 :
1394 0 : if (nodeBefore || nodeAfter) {
1395 0 : MakeEmpty();
1396 0 : return NS_OK;
1397 : }
1398 :
1399 : // cool, we have the last node in the range. Now we walk up its ancestors to
1400 : // find the most senior that is still in the range. That's the real first
1401 : // node.
1402 0 : mLast = GetTopAncestorInRange(lastCandidate);
1403 :
1404 0 : mCurNode = mFirst;
1405 :
1406 0 : return NS_OK;
1407 : }
1408 :
1409 : /****************************************************************
1410 : * nsContentSubtreeIterator overrides of ContentIterator routines
1411 : ****************************************************************/
1412 :
1413 : // we can't call PositionAt in a subtree iterator...
1414 : void
1415 0 : nsContentSubtreeIterator::First()
1416 : {
1417 0 : mIsDone = mFirst == nullptr;
1418 :
1419 0 : mCurNode = mFirst;
1420 0 : }
1421 :
1422 : // we can't call PositionAt in a subtree iterator...
1423 : void
1424 0 : nsContentSubtreeIterator::Last()
1425 : {
1426 0 : mIsDone = mLast == nullptr;
1427 :
1428 0 : mCurNode = mLast;
1429 0 : }
1430 :
1431 :
1432 : void
1433 0 : nsContentSubtreeIterator::Next()
1434 : {
1435 0 : if (mIsDone || !mCurNode) {
1436 0 : return;
1437 : }
1438 :
1439 0 : if (mCurNode == mLast) {
1440 0 : mIsDone = true;
1441 0 : return;
1442 : }
1443 :
1444 0 : nsINode* nextNode = GetNextSibling(mCurNode);
1445 0 : NS_ASSERTION(nextNode, "No next sibling!?! This could mean deadlock!");
1446 :
1447 0 : int32_t i = mEndNodes.IndexOf(nextNode);
1448 0 : while (i != -1) {
1449 : // as long as we are finding ancestors of the endpoint of the range,
1450 : // dive down into their children
1451 0 : nextNode = nextNode->GetFirstChild();
1452 0 : NS_ASSERTION(nextNode, "Iterator error, expected a child node!");
1453 :
1454 : // should be impossible to get a null pointer. If we went all the way
1455 : // down the child chain to the bottom without finding an interior node,
1456 : // then the previous node should have been the last, which was
1457 : // was tested at top of routine.
1458 0 : i = mEndNodes.IndexOf(nextNode);
1459 : }
1460 :
1461 0 : mCurNode = nextNode;
1462 :
1463 : // This shouldn't be needed, but since our selection code can put us
1464 : // in a situation where mLast is in generated content, we need this
1465 : // to stop the iterator when we've walked past past the last node!
1466 0 : mIsDone = mCurNode == nullptr;
1467 : }
1468 :
1469 :
1470 : void
1471 0 : nsContentSubtreeIterator::Prev()
1472 : {
1473 : // Prev should be optimized to use the mStartNodes, just as Next
1474 : // uses mEndNodes.
1475 0 : if (mIsDone || !mCurNode) {
1476 0 : return;
1477 : }
1478 :
1479 0 : if (mCurNode == mFirst) {
1480 0 : mIsDone = true;
1481 0 : return;
1482 : }
1483 :
1484 : // If any of these function calls return null, so will all succeeding ones,
1485 : // so mCurNode will wind up set to null.
1486 0 : nsINode* prevNode = GetDeepFirstChild(mCurNode);
1487 :
1488 0 : prevNode = PrevNode(prevNode);
1489 :
1490 0 : prevNode = GetDeepLastChild(prevNode);
1491 :
1492 0 : mCurNode = GetTopAncestorInRange(prevNode);
1493 :
1494 : // This shouldn't be needed, but since our selection code can put us
1495 : // in a situation where mFirst is in generated content, we need this
1496 : // to stop the iterator when we've walked past past the first node!
1497 0 : mIsDone = mCurNode == nullptr;
1498 : }
1499 :
1500 :
1501 : nsresult
1502 0 : nsContentSubtreeIterator::PositionAt(nsINode* aCurNode)
1503 : {
1504 0 : NS_ERROR("Not implemented!");
1505 :
1506 0 : return NS_ERROR_NOT_IMPLEMENTED;
1507 : }
1508 :
1509 : /****************************************************************
1510 : * nsContentSubtreeIterator helper routines
1511 : ****************************************************************/
1512 :
1513 : nsIContent*
1514 0 : nsContentSubtreeIterator::GetTopAncestorInRange(nsINode* aNode)
1515 : {
1516 0 : if (!aNode || !aNode->GetParentNode()) {
1517 0 : return nullptr;
1518 : }
1519 :
1520 : // aNode has a parent, so it must be content.
1521 0 : nsIContent* content = aNode->AsContent();
1522 :
1523 : // sanity check: aNode is itself in the range
1524 : bool nodeBefore, nodeAfter;
1525 0 : nsresult res = nsRange::CompareNodeToRange(aNode, mRange,
1526 0 : &nodeBefore, &nodeAfter);
1527 0 : NS_ASSERTION(NS_SUCCEEDED(res) && !nodeBefore && !nodeAfter,
1528 : "aNode isn't in mRange, or something else weird happened");
1529 0 : if (NS_FAILED(res) || nodeBefore || nodeAfter) {
1530 0 : return nullptr;
1531 : }
1532 :
1533 0 : while (content) {
1534 0 : nsIContent* parent = content->GetParent();
1535 : // content always has a parent. If its parent is the root, however --
1536 : // i.e., either it's not content, or it is content but its own parent is
1537 : // null -- then we're finished, since we don't go up to the root.
1538 : //
1539 : // We have to special-case this because CompareNodeToRange treats the root
1540 : // node differently -- see bug 765205.
1541 0 : if (!parent || !parent->GetParentNode()) {
1542 0 : return content;
1543 : }
1544 0 : MOZ_ALWAYS_SUCCEEDS(
1545 : nsRange::CompareNodeToRange(parent, mRange, &nodeBefore, &nodeAfter));
1546 :
1547 0 : if (nodeBefore || nodeAfter) {
1548 0 : return content;
1549 : }
1550 0 : content = parent;
1551 : }
1552 :
1553 0 : MOZ_CRASH("This should only be possible if aNode was null");
1554 : }
|
