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 file,
5  * You can obtain one at http://mozilla.org/MPL/2.0/. */
6 
7 #ifndef TreeIterator_h
8 #define TreeIterator_h
9 
10 #include "mozilla/Attributes.h"
11 #include "nsIContent.h"
12 
13 /**
14  * A generic pre-order tree iterator on top of ChildIterator.
15  *
16  * See ChildIterator.h for the kind of iterators you can use as the template
17  * argument for this class.
18  */
19 
20 namespace mozilla {
21 namespace dom {
22 
23 template <typename ChildIterator>
24 class MOZ_STACK_CLASS TreeIterator {
25   enum class Direction {
26     Forward,
27     Backwards,
28   };
29 
30   template <Direction aDirection>
GetNextChild(ChildIterator & aIter)31   nsIContent* GetNextChild(ChildIterator& aIter) {
32     return aDirection == Direction::Forward ? aIter.GetNextChild()
33                                             : aIter.GetPreviousChild();
34   }
35 
36   template <Direction>
37   inline void Advance();
38   template <Direction>
39   inline void AdvanceSkippingChildren();
40 
41  public:
TreeIterator(nsIContent & aRoot)42   explicit TreeIterator(nsIContent& aRoot) : mRoot(aRoot), mCurrent(&aRoot) {}
43 
GetCurrent()44   nsIContent* GetCurrent() const { return mCurrent; }
45 
46   // Note that this keeps the iterator state consistent in case of failure.
47   inline bool Seek(nsIContent&);
48   inline nsIContent* GetNext();
49   inline nsIContent* GetNextSkippingChildren();
50   inline nsIContent* GetPrev();
51   inline nsIContent* GetPrevSkippingChildren();
52 
53  private:
54   using IteratorArray = AutoTArray<ChildIterator, 30>;
55 
56   nsIContent& mRoot;
57   nsIContent* mCurrent;
58   IteratorArray mParentIterators;
59 };
60 
61 template <typename ChildIterator>
62 template <typename TreeIterator<ChildIterator>::Direction aDirection>
AdvanceSkippingChildren()63 inline void TreeIterator<ChildIterator>::AdvanceSkippingChildren() {
64   while (true) {
65     if (MOZ_UNLIKELY(mParentIterators.IsEmpty())) {
66       mCurrent = nullptr;
67       return;
68     }
69 
70     if (nsIContent* nextSibling =
71             GetNextChild<aDirection>(mParentIterators.LastElement())) {
72       mCurrent = nextSibling;
73       return;
74     }
75     mParentIterators.RemoveLastElement();
76   }
77 }
78 
79 template <typename ChildIterator>
Seek(nsIContent & aContent)80 inline bool TreeIterator<ChildIterator>::Seek(nsIContent& aContent) {
81   IteratorArray parentIterators;
82   nsIContent* current = &aContent;
83   while (current != &mRoot) {
84     nsIContent* parent = ChildIterator::GetParent(*current);
85     if (!parent) {
86       return false;
87     }
88 
89     ChildIterator children(parent);
90     if (!children.Seek(current)) {
91       return false;
92     }
93 
94     parentIterators.AppendElement(std::move(children));
95     current = parent;
96   }
97 
98   parentIterators.Reverse();
99 
100   mParentIterators.Clear();
101   mParentIterators.SwapElements(parentIterators);
102   mCurrent = &aContent;
103   return true;
104 }
105 
106 template <typename ChildIterator>
107 template <typename TreeIterator<ChildIterator>::Direction aDirection>
Advance()108 inline void TreeIterator<ChildIterator>::Advance() {
109   MOZ_ASSERT(mCurrent);
110   const bool startAtBeginning = aDirection == Direction::Forward;
111   ChildIterator children(mCurrent, startAtBeginning);
112   if (nsIContent* first = GetNextChild<aDirection>(children)) {
113     mCurrent = first;
114     mParentIterators.AppendElement(std::move(children));
115     return;
116   }
117 
118   AdvanceSkippingChildren<aDirection>();
119 }
120 
121 template <typename ChildIterator>
GetNext()122 inline nsIContent* TreeIterator<ChildIterator>::GetNext() {
123   Advance<Direction::Forward>();
124   return GetCurrent();
125 }
126 
127 template <typename ChildIterator>
GetPrev()128 inline nsIContent* TreeIterator<ChildIterator>::GetPrev() {
129   Advance<Direction::Backwards>();
130   return GetCurrent();
131 }
132 
133 template <typename ChildIterator>
GetNextSkippingChildren()134 inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() {
135   AdvanceSkippingChildren<Direction::Forward>();
136   return GetCurrent();
137 }
138 
139 template <typename ChildIterator>
GetPrevSkippingChildren()140 inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() {
141   AdvanceSkippingChildren<Direction::Backwards>();
142   return GetCurrent();
143 }
144 
145 }  // namespace dom
146 }  // namespace mozilla
147 
148 #endif
149