dom/base/TreeIterator.h

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