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()63inline 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)80inline 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()107inline 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()121inline nsIContent* TreeIterator<ChildIterator>::GetNext() { 122 Advance<Direction::Forward>(); 123 return GetCurrent(); 124 } 125 126 template <typename ChildIterator> GetPrev()127inline nsIContent* TreeIterator<ChildIterator>::GetPrev() { 128 Advance<Direction::Backwards>(); 129 return GetCurrent(); 130 } 131 132 template <typename ChildIterator> GetNextSkippingChildren()133inline nsIContent* TreeIterator<ChildIterator>::GetNextSkippingChildren() { 134 AdvanceSkippingChildren<Direction::Forward>(); 135 return GetCurrent(); 136 } 137 138 template <typename ChildIterator> GetPrevSkippingChildren()139inline nsIContent* TreeIterator<ChildIterator>::GetPrevSkippingChildren() { 140 AdvanceSkippingChildren<Direction::Backwards>(); 141 return GetCurrent(); 142 } 143 144 } // namespace dom 145 } // namespace mozilla 146 147 #endif 148