dom/base/ShadowIncludingTreeIterator.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
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /**
   8  * Implementation of
   9  * https://dom.spec.whatwg.org/#concept-shadow-including-tree-order in iterator
  10  * form.  This can and should be used to avoid recursion on the stack and lots
  11  * of function calls during shadow-including tree iteration.
  12  */
  13
  14 #ifndef mozilla_dom_ShadowIncludingTreeIterator_h
  15 #define mozilla_dom_ShadowIncludingTreeIterator_h
  16
  17 #include "nsINode.h"
  18 #include "nsTArray.h"
  19 #include "mozilla/dom/Element.h"
  20 #include "mozilla/dom/ShadowRoot.h"
  21
  22 namespace mozilla::dom {
  23
  24 class ShadowIncludingTreeIterator {
  25  public:
  26   /**
  27    * Initialize an iterator with aRoot.  After that it can be iterated with a
  28    * range-based for loop.  At the moment, that's the only supported form of use
  29    * for this iterator.
  30    */
  31   explicit ShadowIncludingTreeIterator(nsINode& aRoot) : mCurrent(&aRoot) {
  32     mRoots.AppendElement(&aRoot);
  33   }
  34
  35 #ifdef DEBUG
  36   ~ShadowIncludingTreeIterator() {
  37     MOZ_ASSERT(
  38         !mMutationGuard.Mutated(0),
  39         "Don't mutate the DOM while using a ShadowIncludingTreeIterator");
  40   }
  41 #endif  // DEBUG
  42
  43   // Basic support for range-based for loops.  This will modify the iterator as
  44   // it goes.
  45   ShadowIncludingTreeIterator& begin() { return *this; }
  46
  47   std::nullptr_t end() const { return nullptr; }
  48
  49   bool operator!=(std::nullptr_t) const { return !!mCurrent; }
  50
  51   explicit operator bool() const { return !!mCurrent; }
  52
  53   void operator++() { Next(); }
  54
  55   void SkipChildren() {
  56     MOZ_ASSERT(mCurrent, "Shouldn't be at end");
  57     mCurrent = mCurrent->GetNextNonChildNode(mRoots.LastElement());
  58     WalkOutOfShadowRootsIfNeeded();
  59   }
  60
  61   nsINode* operator*() { return mCurrent; }
  62
  63  private:
  64   void Next() {
  65     MOZ_ASSERT(mCurrent, "Don't call Next() after we have no current node");
  66
  67     // We walk shadow roots immediately after their shadow host.
  68     if (Element* element = Element::FromNode(mCurrent)) {
  69       if (ShadowRoot* shadowRoot = element->GetShadowRoot()) {
  70         mCurrent = shadowRoot;
  71         mRoots.AppendElement(shadowRoot);
  72         return;
  73       }
  74     }
  75
  76     mCurrent = mCurrent->GetNextNode(mRoots.LastElement());
  77     WalkOutOfShadowRootsIfNeeded();
  78   }
  79
  80   void WalkOutOfShadowRootsIfNeeded() {
  81     while (!mCurrent) {
  82       // Nothing left under this root.  Keep trying to pop the stack until we
  83       // find a node or run out of stack.
  84       nsINode* root = mRoots.PopLastElement();
  85       if (mRoots.IsEmpty()) {
  86         // No more roots to step out of; we're done.  mCurrent is already set to
  87         // null.
  88         return;
  89       }
  90       mCurrent =
  91           ShadowRoot::FromNode(root)->Host()->GetNextNode(mRoots.LastElement());
  92     }
  93   }
  94
  95   // The current node we're at.
  96   nsINode* mCurrent;
  97
  98   // Stack of roots that we're inside of right now.  An empty stack can only
  99   // happen when mCurrent is null (and hence we are done iterating).
 100   //
 101   // The default array size here is picked based on gut feeling.  We want at
 102   // least 1, since we will always add something to it in our constructor.
 103   // Having a few more entries probably makes sense, because this is commonly
 104   // used in cases when we know we have custom elements, and hence likely have
 105   // shadow DOMs.  But the exact value "4" was just picked because it sounded
 106   // not too big, not too small.  Feel free to replace it with something else
 107   // based on actual data.
 108   CopyableAutoTArray<nsINode*, 4> mRoots;
 109
 110 #ifdef DEBUG
 111   // Make sure no one mutates the DOM while we're walking over it.
 112   nsMutationGuard mMutationGuard;
 113 #endif  // DEBUG
 114 };
 115
 116 }  // namespace mozilla::dom
 117
 118 #endif  // mozilla_dom_ShadowIncludingTreeIterator_h