1 files changed, 276 insertions, 0 deletions
diff --git a/gfx/layers/TreeTraversal.h b/gfx/layers/TreeTraversal.h
new file mode 100644
index 0000000000..4c02a4e5b5
--- /dev/null
+++ b/gfx/layers/TreeTraversal.h
@@ -0,0 +1,276 @@
+/* -*- 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/. */
+
+#ifndef mozilla_layers_TreeTraversal_h
+#define mozilla_layers_TreeTraversal_h
+
+#include <queue>
+#include <type_traits>
+
+namespace mozilla {
+namespace layers {
+
+/*
+ * Returned by |aPostAction| and |aPreAction| in ForEachNode, indicates
+ * the behavior to follow either action:
+ *
+ * TraversalFlag::Skip - the node's children are not traversed. If this
+ * flag is returned by |aPreAction|, |aPostAction| is skipped for the
+ * current node, as well.
+ * TraversalFlag::Continue - traversal continues normally.
+ * TraversalFlag::Abort - traversal stops immediately.
+ */
+enum class TraversalFlag { Skip, Continue, Abort };
+
+/*
+ * Iterator types to be specified in traversal function calls:
+ *
+ * ForwardIterator - for nodes using GetFirstChild() and GetNextSibling()
+ * ReverseIterator - for nodes using GetLastChild() and GetPrevSibling()
+ */
+class ForwardIterator {
+ public:
+  template <typename Node>
+  static Node* FirstChild(Node* n) {
+    return n->GetFirstChild();
+  }
+  template <typename Node>
+  static Node* NextSibling(Node* n) {
+    return n->GetNextSibling();
+  }
+  template <typename Node>
+  static Node FirstChild(Node n) {
+    return n.GetFirstChild();
+  }
+  template <typename Node>
+  static Node NextSibling(Node n) {
+    return n.GetNextSibling();
+  }
+};
+class ReverseIterator {
+ public:
+  template <typename Node>
+  static Node* FirstChild(Node* n) {
+    return n->GetLastChild();
+  }
+  template <typename Node>
+  static Node* NextSibling(Node* n) {
+    return n->GetPrevSibling();
+  }
+  template <typename Node>
+  static Node FirstChild(Node n) {
+    return n.GetLastChild();
+  }
+  template <typename Node>
+  static Node NextSibling(Node n) {
+    return n.GetPrevSibling();
+  }
+};
+
+/*
+ * Do a depth-first traversal of the tree rooted at |aRoot|, performing
+ * |aPreAction| before traversal of children and |aPostAction| after.
+ *
+ * Returns true if traversal aborted, false if continued normally. If
+ * TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
+ * is not performed.
+ *
+ * |Iterator| should have static methods named NextSibling() and FirstChild()
+ * that accept an argument of type Node. For convenience, classes
+ * |ForwardIterator| and |ReverseIterator| are provided which implement these
+ * methods as GetNextSibling()/GetFirstChild() and
+ * GetPrevSibling()/GetLastChild(), respectively.
+ */
+template <typename Iterator, typename Node, typename PreAction,
+          typename PostAction>
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
+                        const PostAction& aPostAction)
+    -> std::enable_if_t<
+        std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag> &&
+            std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>,
+        bool> {
+  if (!aRoot) {
+    return false;
+  }
+
+  TraversalFlag result = aPreAction(aRoot);
+
+  if (result == TraversalFlag::Abort) {
+    return true;
+  }
+
+  if (result == TraversalFlag::Continue) {
+    for (Node child = Iterator::FirstChild(aRoot); child;
+         child = Iterator::NextSibling(child)) {
+      bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
+      if (abort) {
+        return true;
+      }
+    }
+
+    result = aPostAction(aRoot);
+
+    if (result == TraversalFlag::Abort) {
+      return true;
+    }
+  }
+
+  return false;
+}
+
+/*
+ * Do a depth-first traversal of the tree rooted at |aRoot|, performing
+ * |aPreAction| before traversal of children and |aPostAction| after.
+ */
+template <typename Iterator, typename Node, typename PreAction,
+          typename PostAction>
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction,
+                        const PostAction& aPostAction)
+    -> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void> &&
+                            std::is_same_v<decltype(aPostAction(aRoot)), void>,
+                        void> {
+  if (!aRoot) {
+    return;
+  }
+
+  aPreAction(aRoot);
+
+  for (Node child = Iterator::FirstChild(aRoot); child;
+       child = Iterator::NextSibling(child)) {
+    ForEachNode<Iterator>(child, aPreAction, aPostAction);
+  }
+
+  aPostAction(aRoot);
+}
+
+/*
+ * ForEachNode pre-order traversal, using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PreAction>
+auto ForEachNode(Node aRoot, const PreAction& aPreAction) -> std::enable_if_t<
+    std::is_same_v<decltype(aPreAction(aRoot)), TraversalFlag>, bool> {
+  return ForEachNode<Iterator>(
+      aRoot, aPreAction, [](Node aNode) { return TraversalFlag::Continue; });
+}
+
+/*
+ * ForEachNode pre-order, not using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PreAction>
+auto ForEachNode(Node aRoot, const PreAction& aPreAction)
+    -> std::enable_if_t<std::is_same_v<decltype(aPreAction(aRoot)), void>,
+                        void> {
+  ForEachNode<Iterator>(aRoot, aPreAction, [](Node aNode) {});
+}
+
+/*
+ * ForEachNode post-order traversal, using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PostAction>
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
+    -> std::enable_if_t<
+        std::is_same_v<decltype(aPostAction(aRoot)), TraversalFlag>, bool> {
+  return ForEachNode<Iterator>(
+      aRoot, [](Node aNode) { return TraversalFlag::Continue; }, aPostAction);
+}
+
+/*
+ * ForEachNode post-order, not using TraversalFlag.
+ */
+template <typename Iterator, typename Node, typename PostAction>
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction)
+    -> std::enable_if_t<std::is_same_v<decltype(aPostAction(aRoot)), void>,
+                        void> {
+  ForEachNode<Iterator>(
+      aRoot, [](Node aNode) {}, aPostAction);
+}
+
+/*
+ * Do a breadth-first search of the tree rooted at |aRoot|, and return the
+ * first visited node that satisfies |aCondition|, or nullptr if no such node
+ * was found.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node()
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node BreadthFirstSearch(Node aRoot, const Condition& aCondition) {
+  if (!aRoot) {
+    return Node();
+  }
+
+  std::queue<Node> queue;
+  queue.push(aRoot);
+  while (!queue.empty()) {
+    Node node = queue.front();
+    queue.pop();
+
+    if (aCondition(node)) {
+      return node;
+    }
+
+    for (Node child = Iterator::FirstChild(node); child;
+         child = Iterator::NextSibling(child)) {
+      queue.push(child);
+    }
+  }
+
+  return Node();
+}
+
+/*
+ * Do a pre-order, depth-first search of the tree rooted at |aRoot|, and
+ * return the first visited node that satisfies |aCondition|, or nullptr
+ * if no such node was found.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node().
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node DepthFirstSearch(Node aRoot, const Condition& aCondition) {
+  Node result = Node();
+
+  ForEachNode<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
+    if (aCondition(aNode)) {
+      result = aNode;
+      return TraversalFlag::Abort;
+    }
+
+    return TraversalFlag::Continue;
+  });
+
+  return result;
+}
+
+/*
+ * Perform a post-order, depth-first search starting at aRoot.
+ *
+ * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
+ * definition, but in addition to those, |Node| must be able to express a null
+ * value, returned from Node().
+ */
+template <typename Iterator, typename Node, typename Condition>
+Node DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition) {
+  Node result = Node();
+
+  ForEachNodePostOrder<Iterator>(aRoot, [&aCondition, &result](Node aNode) {
+    if (aCondition(aNode)) {
+      result = aNode;
+      return TraversalFlag::Abort;
+    }
+
+    return TraversalFlag::Continue;
+  });
+
+  return result;
+}
+
+}  // namespace layers
+}  // namespace mozilla
+
+#endif  // mozilla_layers_TreeTraversal_h