CustomElementUpgradeSorter puts elements in shadow-including tree order.

third_party/WebKit/Source/core/dom/custom/CustomElementUpgradeSorter.h

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CustomElementUpgradeSorter_h
+#define CustomElementUpgradeSorter_h
+
+#include "core/CoreExport.h"
+#include "platform/heap/Handle.h"
+
+namespace blink {
+
+class Element;
+class Node;
+
+// Does a shadow-including tree order sort of a subset of elements.
+// https://dom.spec.whatwg.org/#concept-shadow-including-tree-order
+class CORE_EXPORT CustomElementUpgradeSorter {
+    STACK_ALLOCATED();
+public:
+    CustomElementUpgradeSorter();
+
+    // Record an element of interest. The DOM tree must not be
+    // modified between calls to add and the call to sorted.
+    void add(Element*);
+
+    // Adds shadow-including descendents of parent to result in
+    // shadow-including tree order. This operation is destroys the
+    // state of this sorter; after calling sorted, you must not call
+    // add or sorted again with this object.
+    void sorted(HeapVector<Member<Element>>* result, Node* parent);
+
+private:
+    using ChildSet = HeapHashSet<Member<Node>>;
+    using ParentChildMap = HeapHashMap<Member<Node>, ChildSet>;
+
+    void visit(
+        HeapVector<Member<Element>>* result,
+        ChildSet&,
+        const ChildSet::iterator&);
+
+    Member<HeapHashSet<Member<Element>>> m_elements;
+
+    // This is the subset of the tree, from root node (usually
+    // document) through elements and shadow roots, to candidates.
+    Member<ParentChildMap> m_parentChildMap;
+};
+
+} // namespace blink
+
+#endif // CustomElementUpgradeSorter_h