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 = std::move(parentIterators);
101   mCurrent = &aContent;
102   return true;
103 }
104 
105 template <typename ChildIterator>
106 template <typename TreeIterator<ChildIterator>::Direction aDirection>
Advance()107 inline void TreeIterator<ChildIterator>::Advance() {
108   MOZ_ASSERT(mCurrent);
109   const bool startAtBeginning = aDirection == Direction::Forward;
110   ChildIterator children(mCurrent, startAtBeginning);
111   if (nsIContent* first = GetNextChild<aDirection>(children)) {
112     mCurrent = first;
113     mParentIterators.AppendElement(std::move(children));
114     return;
115   }
116 
117   AdvanceSkippingChildren<aDirection>();
118 }
119 
120 template <typename ChildIterator>
GetNext()121 inline nsIContent* TreeIterator<ChildIterator>::GetNext() {
122   Advance<Direction::Forward>();
123   return GetCurrent();
124 }
125 
126 template <typename ChildIterator>
GetPrev()127 inline nsIContent* TreeIterator<ChildIterator>::GetPrev() {
128   Advance<Direction::Backwards>();
129   return GetCurrent();
130 }
131 
132 template <typename ChildIterator>
GetNextSkippingChildren()133 inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() {
134   AdvanceSkippingChildren<Direction::Forward>();
135   return GetCurrent();
136 }
137 
138 template <typename ChildIterator>
GetPrevSkippingChildren()139 inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() {
140   AdvanceSkippingChildren<Direction::Backwards>();
141   return GetCurrent();
142 }
143 
144 }  // namespace dom
145 }  // namespace mozilla
146 
147 #endif
148