Bug 1519193 part 1. Add an iterator that implements "shadow-including tree order" traversal. r=emilio
☠☠ backed out by 487a0df75166 ☠ ☠
authorBoris Zbarsky <bzbarsky@mit.edu>
Fri, 11 Jan 2019 21:56:15 +0000
changeset 453558 aae6e06aa88b
parent 453557 610a3472661a
child 453559 1caa462e7f08
push id35360
push usernbeleuzu@mozilla.com
push dateSat, 12 Jan 2019 09:39:47 +0000
treeherdermozilla-central@cb35977ae7a4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersemilio
bugs1519193
milestone66.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1519193 part 1. Add an iterator that implements "shadow-including tree order" traversal. r=emilio Differential Revision: https://phabricator.services.mozilla.com/D16242
dom/base/ShadowIncludingTreeIterator.h
dom/base/moz.build
new file mode 100644
--- /dev/null
+++ b/dom/base/ShadowIncludingTreeIterator.h
@@ -0,0 +1,113 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/**
+ * Implementation of
+ * https://dom.spec.whatwg.org/#concept-shadow-including-tree-order in iterator
+ * form.  This can and should be used to avoid recursion on the stack and lots
+ * of function calls during shadow-including tree iteration.
+ */
+
+#ifndef mozilla_dom_ShadowIncludingTreeIterator_h
+#define mozilla_dom_ShadowIncludingTreeIterator_h
+
+#include "nsINode.h"
+#include "nsTArray.h"
+#include "mozilla/dom/Element.h"
+#include "mozilla/dom/ShadowRoot.h"
+
+namespace mozilla {
+namespace dom {
+
+class ShadowIncludingTreeIterator {
+ public:
+  /**
+   * Initialize an iterator with aRoot.  After that it can be iterated with a
+   * range-based for loop.  At the moment, that's the only supported form of use
+   * for this iterator.
+   */
+  explicit ShadowIncludingTreeIterator(nsINode& aRoot) : mCurrent(&aRoot) {
+    mRoots.AppendElement(&aRoot);
+  }
+
+#ifdef DEBUG
+  ~ShadowIncludingTreeIterator() {
+    MOZ_ASSERT(
+        !mMutationGuard.Mutated(0),
+        "Don't mutate the DOM while using a ShadowIncludingTreeIterator");
+  }
+#endif  // DEBUG
+
+  // Basic support for range-based for loops.  This will modify the iterator as
+  // it goes.
+  ShadowIncludingTreeIterator& begin() { return *this; }
+
+  ShadowIncludingTreeIterator end() { return ShadowIncludingTreeIterator(); }
+
+  bool operator!=(const ShadowIncludingTreeIterator& aOther) {
+    return mCurrent != aOther.mCurrent;
+  }
+
+  void operator++() { Next(); }
+
+  nsINode* operator*() { return mCurrent; }
+
+ private:
+  // Constructor used only for end() to represent a drained iterator.
+  ShadowIncludingTreeIterator() : mCurrent(nullptr) {}
+
+  void Next() {
+    MOZ_ASSERT(mCurrent, "Don't call Next() after we have no current node");
+
+    // We walk shadow roots immediately after their shadow host.
+    if (Element* element = Element::FromNode(mCurrent)) {
+      if (ShadowRoot* shadowRoot = element->GetShadowRoot()) {
+        mCurrent = shadowRoot;
+        mRoots.AppendElement(shadowRoot);
+        return;
+      }
+    }
+
+    mCurrent = mCurrent->GetNextNode(mRoots.LastElement());
+    while (!mCurrent) {
+      // Nothing left under this root.  Keep trying to pop the stack until we
+      // find a node or run out of stack.
+      nsINode* root = mRoots.PopLastElement();
+      if (mRoots.IsEmpty()) {
+        // No more roots to step out of; we're done.  mCurrent is already set to
+        // null.
+        return;
+      }
+      mCurrent =
+          ShadowRoot::FromNode(root)->Host()->GetNextNode(mRoots.LastElement());
+    }
+  }
+
+  // The current node we're at.
+  nsINode* mCurrent;
+
+  // Stack of roots that we're inside of right now.  An empty stack can only
+  // happen when mCurrent is null (and hence we are done iterating).
+  //
+  // The default array size here is picked based on gut feeling.  We want at
+  // least 1, since we will always add something to it in our constructor.
+  // Having a few more entries probably makes sense, because this is commonly
+  // used in cases when we know we have custom elements, and hence likely have
+  // shadow DOMs.  But the exact value "4" was just picked because it sounded
+  // not too big, not too small.  Feel free to replace it with something else
+  // based on actual data.
+  AutoTArray<nsINode*, 4> mRoots;
+
+#ifdef DEBUG
+  // Make sure no one mutates the DOM while we're walking over it.
+  nsMutationGuard mMutationGuard;
+#endif  // DEBUG
+};
+
+}  // namespace dom
+}  // namespace mozilla
+
+#endif  // mozilla_dom_ShadowIncludingTreeIterator_h
--- a/dom/base/moz.build
+++ b/dom/base/moz.build
@@ -215,16 +215,17 @@ EXPORTS.mozilla.dom += [
     'Pose.h',
     'PostMessageEvent.h',
     'ProcessMessageManager.h',
     'ResponsiveImageSelector.h',
     'SameProcessMessageQueue.h',
     'ScreenLuminance.h',
     'ScreenOrientation.h',
     'Selection.h',
+    'ShadowIncludingTreeIterator.h',
     'ShadowRoot.h',
     'StructuredCloneBlob.h',
     'StructuredCloneHolder.h',
     'StructuredCloneTags.h',
     'StructuredCloneTester.h',
     'StyleSheetList.h',
     'SubtleCrypto.h',
     'SyncMessageSender.h',