Bug 1227233: Increase scope of TreeTraversal.h to by-value traversal r=botond draft
authorKevin Wern <kevin.m.wern@gmail.com>
Thu, 22 Sep 2016 12:31:26 -0400
changeset 420475 8660afac0ce58796c864ee41e2e30fee94731f2c
parent 415258 c9971be9e98150ef99d4ef80c6f800ec5915b1ac
child 532815 ddca78c51835991e42b14308ec8926e6b242a8b2
push id31204
push userbmo:kevin.m.wern@gmail.com
push dateTue, 04 Oct 2016 06:47:09 +0000
reviewersbotond
bugs1227233
milestone52.0a1
Bug 1227233: Increase scope of TreeTraversal.h to by-value traversal r=botond MozReview-Commit-ID: LOw1k792T10
gfx/2d/Logging.h
gfx/layers/Layers.cpp
gfx/layers/TreeTraversal.h
gfx/layers/apz/src/APZCTreeManager.cpp
gfx/layers/apz/src/APZCTreeManager.h
gfx/layers/composite/AsyncCompositionManager.cpp
--- a/gfx/2d/Logging.h
+++ b/gfx/2d/Logging.h
@@ -638,17 +638,20 @@ public:
       // between now and the first output to the next line.
       mLog.Flush();
       mStartOfLine = true;
     }
     return *this;
   }
 
   void IncreaseIndent() { ++mDepth; }
-  void DecreaseIndent() { --mDepth; }
+  void DecreaseIndent() {
+    --mDepth;
+    MOZ_ASSERT(mDepth >= 0);
+  }
 
   void ConditionOnPrefFunction(bool(*aPrefFunction)()) {
     mConditionedOnPref = true;
     mPrefFunction = aPrefFunction;
   }
 private:
   Log<LOG_DEBUG> mLog;
   std::string mPrefix;
@@ -676,16 +679,24 @@ private:
 };
 
 class TreeAutoIndent
 {
 public:
   explicit TreeAutoIndent(TreeLog& aTreeLog) : mTreeLog(aTreeLog) {
     mTreeLog.IncreaseIndent();
   }
+
+  TreeAutoIndent(const TreeAutoIndent& aTreeAutoIndent) :
+      TreeAutoIndent(aTreeAutoIndent.mTreeLog) {
+    mTreeLog.IncreaseIndent();
+  }
+
+  TreeAutoIndent& operator=(const TreeAutoIndent& aTreeAutoIndent) = delete;
+
   ~TreeAutoIndent() {
     mTreeLog.DecreaseIndent();
   }
 private:
   TreeLog& mTreeLog;
 };
 
 } // namespace gfx
--- a/gfx/layers/Layers.cpp
+++ b/gfx/layers/Layers.cpp
@@ -75,34 +75,30 @@ LayerManager::GetLog()
 
 FrameMetrics::ViewID
 LayerManager::GetRootScrollableLayerId()
 {
   if (!mRoot) {
     return FrameMetrics::NULL_SCROLL_ID;
   }
 
-  nsTArray<LayerMetricsWrapper> queue = { LayerMetricsWrapper(mRoot) };
-  while (queue.Length()) {
-    LayerMetricsWrapper layer = queue[0];
-    queue.RemoveElementAt(0);
+  LayerMetricsWrapper layerMetricsRoot = LayerMetricsWrapper(mRoot);
 
-    const FrameMetrics& frameMetrics = layer.Metrics();
-    if (frameMetrics.IsScrollable()) {
-      return frameMetrics.GetScrollId();
-    }
+  LayerMetricsWrapper rootScrollableLayerMetrics =
+      BreadthFirstSearch<ForwardIterator>(
+          layerMetricsRoot,
+          [](LayerMetricsWrapper aLayerMetrics)
+          {
+            return aLayerMetrics.Metrics().IsScrollable();
+          }
+      );
 
-    LayerMetricsWrapper child = layer.GetFirstChild();
-    while (child) {
-      queue.AppendElement(child);
-      child = child.GetNextSibling();
-    }
-  }
-
-  return FrameMetrics::NULL_SCROLL_ID;
+  return rootScrollableLayerMetrics.IsValid() ?
+      rootScrollableLayerMetrics.Metrics().GetScrollId() :
+      FrameMetrics::NULL_SCROLL_ID;
 }
 
 void
 LayerManager::GetRootScrollableLayers(nsTArray<Layer*>& aArray)
 {
   if (!mRoot) {
     return;
   }
@@ -154,33 +150,24 @@ LayerManager::GetScrollableLayers(nsTArr
 
 LayerMetricsWrapper
 LayerManager::GetRootContentLayer()
 {
   if (!mRoot) {
     return LayerMetricsWrapper();
   }
 
-  nsTArray<Layer*> queue = { mRoot };
-  while (!queue.IsEmpty()) {
-    Layer* layer = queue[0];
-    queue.RemoveElementAt(0);
+  LayerMetricsWrapper root(mRoot);
 
-    for (uint32_t i = 0; i < layer->GetScrollMetadataCount(); i++) {
-      if (layer->GetFrameMetrics(i).IsRootContent()) {
-        return LayerMetricsWrapper(layer, i);
+  return BreadthFirstSearch<ForwardIterator>(root,
+      [](LayerMetricsWrapper aLayerMetrics)
+      {
+        return aLayerMetrics.Metrics().IsRootContent();
       }
-    }
-
-    for (Layer* child = layer->GetFirstChild(); child; child = child->GetNextSibling()) {
-      queue.AppendElement(child);
-    }
-  }
-
-  return LayerMetricsWrapper();
+  );
 }
 
 already_AddRefed<DrawTarget>
 LayerManager::CreateOptimalDrawTarget(const gfx::IntSize &aSize,
                                       SurfaceFormat aFormat)
 {
   return gfxPlatform::GetPlatform()->CreateOffscreenContentDrawTarget(aSize,
                                                                       aFormat);
--- a/gfx/layers/TreeTraversal.h
+++ b/gfx/layers/TreeTraversal.h
@@ -30,68 +30,84 @@ enum class TraversalFlag { Skip, Continu
  *
  * 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();
+    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();
+    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
+ * 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) ->
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), TraversalFlag>::value &&
                   IsSame<decltype(aPostAction(aRoot)),TraversalFlag>::value, bool>::Type
 {
   if (!aRoot) {
     return false;
   }
 
   TraversalFlag result = aPreAction(aRoot);
 
   if (result == TraversalFlag::Abort) {
     return true;
   }
 
   if (result == TraversalFlag::Continue) {
-    for (Node* child = Iterator::FirstChild(aRoot);
+    for (Node child = Iterator::FirstChild(aRoot);
          child;
          child = Iterator::NextSibling(child)) {
       bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
       if (abort) {
         return true;
       }
     }
 
@@ -105,147 +121,153 @@ typename EnableIf<IsSame<decltype(aPreAc
   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) ->
+static auto ForEachNode(Node aRoot, const PreAction& aPreAction, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), void>::value &&
                   IsSame<decltype(aPostAction(aRoot)),void>::value, void>::Type
 {
   if (!aRoot) {
     return;
   }
 
   aPreAction(aRoot);
 
-  for (Node* child = Iterator::FirstChild(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) ->
+auto ForEachNode(Node aRoot, const PreAction& aPreAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), TraversalFlag>::value, bool>::Type
 {
-  return ForEachNode<Iterator>(aRoot, aPreAction, [](Node* aNode){ return TraversalFlag::Continue; });
+  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) ->
+auto ForEachNode(Node aRoot, const PreAction& aPreAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), void>::value, void>::Type
 {
-  ForEachNode<Iterator>(aRoot, aPreAction, [](Node* aNode){});
+  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) ->
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPostAction(aRoot)), TraversalFlag>::value, bool>::Type
 {
-  return ForEachNode<Iterator>(aRoot, [](Node* aNode){ return TraversalFlag::Continue; }, aPostAction);
+  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) ->
+auto ForEachNodePostOrder(Node aRoot, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPostAction(aRoot)), void>::value, void>::Type
 {
-  ForEachNode<Iterator>(aRoot, [](Node* aNode){}, aPostAction);
+  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.
  *
- * See ForEachNode() for the requirements on |Iterator| and |Node|
+ * |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)
+Node BreadthFirstSearch(Node aRoot, const Condition& aCondition)
 {
   if (!aRoot) {
-    return nullptr;
+    return Node();
   }
 
-  std::queue<Node*> queue;
+  std::queue<Node> queue;
   queue.push(aRoot);
   while (!queue.empty()) {
-    Node* node = queue.front();
+    Node node = queue.front();
     queue.pop();
 
     if (aCondition(node)) {
       return node;
     }
 
-    for (Node* child = Iterator::FirstChild(node);
+    for (Node child = Iterator::FirstChild(node);
          child;
          child = Iterator::NextSibling(child)) {
       queue.push(child);
     }
   }
 
-  return nullptr;
+  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.
  *
- * See ForEachNode() for the requirements on |Iterator| and |Node|
+ * |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 DepthFirstSearch(Node aRoot, const Condition& aCondition)
 {
-  Node* result = nullptr;
+  Node result = Node();
 
   ForEachNode<Iterator>(aRoot,
-      [&aCondition, &result](Node* aNode)
+      [&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.
  *
- * See ForEachNode() for the requirements on |Iterator| and |Node|
+ * |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 DepthFirstSearchPostOrder(Node aRoot, const Condition& aCondition)
 {
-  Node* result = nullptr;
+  Node result = Node();
 
   ForEachNodePostOrder<Iterator>(aRoot,
-      [&aCondition, &result](Node* aNode)
+      [&aCondition, &result](Node aNode)
       {
         if (aCondition(aNode)) {
           result = aNode;
           return TraversalFlag::Abort;
         }
 
         return TraversalFlag::Continue;
       });
--- a/gfx/layers/apz/src/APZCTreeManager.cpp
+++ b/gfx/layers/apz/src/APZCTreeManager.cpp
@@ -175,22 +175,75 @@ APZCTreeManager::UpdateHitTestingTree(Co
   ForEachNode<ReverseIterator>(mRootNode.get(),
       [&state] (HitTestingTreeNode* aNode)
       {
         state.mNodesToDestroy.AppendElement(aNode);
       });
   mRootNode = nullptr;
 
   if (aRoot) {
+    std::stack<gfx::TreeAutoIndent> indents;
+    std::stack<gfx::Matrix4x4> ancestorTransforms;
+    HitTestingTreeNode* parent = nullptr;
+    HitTestingTreeNode* next = nullptr;
+
+    // aCompositor is null in gtest scenarios
+    uint64_t layersId = aCompositor ? aCompositor->RootLayerTreeId() : 0;
+    ancestorTransforms.push(Matrix4x4());
+
     mApzcTreeLog << "[start]\n";
     LayerMetricsWrapper root(aRoot);
-    UpdateHitTestingTree(state, root,
-                         // aCompositor is null in gtest scenarios
-                         aCompositor ? aCompositor->RootLayerTreeId() : 0,
-                         Matrix4x4(), nullptr, nullptr);
+    mTreeLock.AssertCurrentThreadOwns();
+
+    ForEachNode<ReverseIterator>(root,
+        [&](LayerMetricsWrapper aLayerMetrics)
+        {
+          mApzcTreeLog << aLayerMetrics.Name() << '\t';
+
+          HitTestingTreeNode* node = PrepareNodeForLayer(aLayerMetrics,
+                aLayerMetrics.Metrics(), layersId, ancestorTransforms.top(),
+                parent, next, state);
+          MOZ_ASSERT(node);
+          AsyncPanZoomController* apzc = node->GetApzc();
+          aLayerMetrics.SetApzc(apzc);
+
+          mApzcTreeLog << '\n';
+
+          // Accumulate the CSS transform between layers that have an APZC.
+          // In the terminology of the big comment above APZCTreeManager::GetScreenToApzcTransform, if
+          // we are at layer M, then aAncestorTransform is NC * OC * PC, and we left-multiply MC and
+          // compute ancestorTransform to be MC * NC * OC * PC. This gets passed down as the ancestor
+          // transform to layer L when we recurse into the children below. If we are at a layer
+          // with an APZC, such as P, then we reset the ancestorTransform to just PC, to start
+          // the new accumulation as we go down.
+          // If a transform is a perspective transform, it's ignored for this purpose
+          // (see bug 1168263).
+          Matrix4x4 currentTransform = aLayerMetrics.TransformIsPerspective() ? Matrix4x4() : aLayerMetrics.GetTransform();
+          if (!apzc) {
+            currentTransform = currentTransform * ancestorTransforms.top();
+          }
+          ancestorTransforms.push(currentTransform);
+
+          // Note that |node| at this point will not have any children, otherwise we
+          // we would have to set next to node->GetFirstChild().
+          MOZ_ASSERT(!node->GetFirstChild());
+          parent = node;
+          next = nullptr;
+          layersId = (aLayerMetrics.AsRefLayer() ? aLayerMetrics.AsRefLayer()->GetReferentId() : layersId);
+          indents.push(gfx::TreeAutoIndent(mApzcTreeLog));
+        },
+        [&](LayerMetricsWrapper aLayerMetrics)
+        {
+          next = parent;
+          parent = parent->GetParent();
+          layersId = next->GetLayersId();
+          ancestorTransforms.pop();
+          indents.pop();
+        });
+
     mApzcTreeLog << "[end]\n";
   }
 
   // We do not support tree structures where the root node has siblings.
   MOZ_ASSERT(!(mRootNode && mRootNode->GetPrevSibling()));
 
   for (size_t i = 0; i < state.mNodesToDestroy.Length(); i++) {
     APZCTM_LOG("Destroying node at %p with APZC %p\n",
@@ -558,67 +611,16 @@ APZCTreeManager::PrepareNodeForLayer(con
   node->SetScrollbarData(aLayer.GetScrollbarTargetContainerId(),
                          aLayer.GetScrollbarDirection(),
                          aLayer.GetScrollbarSize(),
                          aLayer.IsScrollbarContainer());
   node->SetFixedPosData(aLayer.GetFixedPositionScrollContainerId());
   return node;
 }
 
-HitTestingTreeNode*
-APZCTreeManager::UpdateHitTestingTree(TreeBuildingState& aState,
-                                      const LayerMetricsWrapper& aLayer,
-                                      uint64_t aLayersId,
-                                      const gfx::Matrix4x4& aAncestorTransform,
-                                      HitTestingTreeNode* aParent,
-                                      HitTestingTreeNode* aNextSibling)
-{
-  mTreeLock.AssertCurrentThreadOwns();
-
-  mApzcTreeLog << aLayer.Name() << '\t';
-
-  HitTestingTreeNode* node = PrepareNodeForLayer(aLayer,
-        aLayer.Metrics(), aLayersId, aAncestorTransform,
-        aParent, aNextSibling, aState);
-  MOZ_ASSERT(node);
-  AsyncPanZoomController* apzc = node->GetApzc();
-  aLayer.SetApzc(apzc);
-
-  mApzcTreeLog << '\n';
-
-  // Accumulate the CSS transform between layers that have an APZC.
-  // In the terminology of the big comment above APZCTreeManager::GetScreenToApzcTransform, if
-  // we are at layer M, then aAncestorTransform is NC * OC * PC, and we left-multiply MC and
-  // compute ancestorTransform to be MC * NC * OC * PC. This gets passed down as the ancestor
-  // transform to layer L when we recurse into the children below. If we are at a layer
-  // with an APZC, such as P, then we reset the ancestorTransform to just PC, to start
-  // the new accumulation as we go down.
-  // If a transform is a perspective transform, it's ignored for this purpose
-  // (see bug 1168263).
-  Matrix4x4 ancestorTransform = aLayer.TransformIsPerspective() ? Matrix4x4() : aLayer.GetTransform();
-  if (!apzc) {
-    ancestorTransform = ancestorTransform * aAncestorTransform;
-  }
-
-  // Note that |node| at this point will not have any children, otherwise we
-  // we would have to set next to node->GetFirstChild().
-  MOZ_ASSERT(!node->GetFirstChild());
-  aParent = node;
-  HitTestingTreeNode* next = nullptr;
-
-  uint64_t childLayersId = (aLayer.AsRefLayer() ? aLayer.AsRefLayer()->GetReferentId() : aLayersId);
-  for (LayerMetricsWrapper child = aLayer.GetLastChild(); child; child = child.GetPrevSibling()) {
-    gfx::TreeAutoIndent indent(mApzcTreeLog);
-    next = UpdateHitTestingTree(aState, child, childLayersId,
-                                ancestorTransform, aParent, next);
-  }
-
-  return node;
-}
-
 template<typename PanGestureOrScrollWheelInput>
 static bool
 WillHandleInput(const PanGestureOrScrollWheelInput& aPanInput)
 {
   if (!NS_IsMainThread()) {
     return true;
   }
 
--- a/gfx/layers/apz/src/APZCTreeManager.h
+++ b/gfx/layers/apz/src/APZCTreeManager.h
@@ -469,44 +469,16 @@ private:
   HitTestingTreeNode* PrepareNodeForLayer(const LayerMetricsWrapper& aLayer,
                                           const FrameMetrics& aMetrics,
                                           uint64_t aLayersId,
                                           const gfx::Matrix4x4& aAncestorTransform,
                                           HitTestingTreeNode* aParent,
                                           HitTestingTreeNode* aNextSibling,
                                           TreeBuildingState& aState);
 
-  /**
-   * Recursive helper function to build the hit-testing tree. See documentation
-   * in HitTestingTreeNode.h for more details on the shape of the tree.
-   * This function walks the layer tree backwards through siblings and
-   * constructs the hit-testing tree also as a last-child-prev-sibling tree
-   * because that simplifies the hit detection code.
-   *
-   * @param aState The current tree building state.
-   * @param aLayer The (layer, metrics) pair which is the current position in
-   *               the recursive walk of the layer tree. This call builds a
-   *               hit-testing subtree corresponding to the layer subtree rooted
-   *               at aLayer.
-   * @param aLayersId The layers id of the layer in aLayer.
-   * @param aAncestorTransform The accumulated CSS transforms of all the
-   *                           layers from aLayer up (via the parent chain)
-   *                           to the next APZC-bearing layer.
-   * @param aParent The parent of any node built at this level.
-   * @param aNextSibling The next sibling of any node built at this level.
-   * @return The HitTestingTreeNode created at this level. This will always
-   *         be non-null.
-   */
-  HitTestingTreeNode* UpdateHitTestingTree(TreeBuildingState& aState,
-                                           const LayerMetricsWrapper& aLayer,
-                                           uint64_t aLayersId,
-                                           const gfx::Matrix4x4& aAncestorTransform,
-                                           HitTestingTreeNode* aParent,
-                                           HitTestingTreeNode* aNextSibling);
-
   void PrintAPZCInfo(const LayerMetricsWrapper& aLayer,
                      const AsyncPanZoomController* apzc);
 
 protected:
   /* The input queue where input events are held until we know enough to
    * figure out where they're going. Protected so gtests can access it.
    */
   RefPtr<InputQueue> mInputQueue;
--- a/gfx/layers/composite/AsyncCompositionManager.cpp
+++ b/gfx/layers/composite/AsyncCompositionManager.cpp
@@ -742,25 +742,26 @@ SampleAnimations(Layer* aLayer, TimeStam
       });
   return activeAnimations;
 }
 
 static bool
 SampleAPZAnimations(const LayerMetricsWrapper& aLayer, TimeStamp aSampleTime)
 {
   bool activeAnimations = false;
-  for (LayerMetricsWrapper child = aLayer.GetFirstChild(); child;
-        child = child.GetNextSibling()) {
-    activeAnimations |= SampleAPZAnimations(child, aSampleTime);
-  }
 
-  if (AsyncPanZoomController* apzc = aLayer.GetApzc()) {
-    apzc->ReportCheckerboard(aSampleTime);
-    activeAnimations |= apzc->AdvanceAnimations(aSampleTime);
-  }
+  ForEachNodePostOrder<ForwardIterator>(aLayer,
+      [&activeAnimations, &aSampleTime](LayerMetricsWrapper aLayerMetrics)
+      {
+        if (AsyncPanZoomController* apzc = aLayerMetrics.GetApzc()) {
+          apzc->ReportCheckerboard(aSampleTime);
+          activeAnimations |= apzc->AdvanceAnimations(aSampleTime);
+        }
+      }
+  );
 
   return activeAnimations;
 }
 
 void
 AsyncCompositionManager::RecordShadowTransforms(Layer* aLayer)
 {
   MOZ_ASSERT(gfxPrefs::CollectScrollTransforms());
@@ -1301,63 +1302,56 @@ ApplyAsyncTransformToScrollbarForContent
     }
   }
   transform = transform * compensation;
 
   SetShadowTransform(aScrollbar, transform);
 }
 
 static LayerMetricsWrapper
-FindScrolledLayerRecursive(Layer* aScrollbar, const LayerMetricsWrapper& aSubtreeRoot)
-{
-  if (LayerIsScrollbarTarget(aSubtreeRoot, aScrollbar)) {
-    return aSubtreeRoot;
-  }
-
-  for (LayerMetricsWrapper child = aSubtreeRoot.GetFirstChild();
-       child;
-       child = child.GetNextSibling())
-  {
-    // Do not recurse into RefLayers, since our initial aSubtreeRoot is the
-    // root (or RefLayer root) of a single layer space to search.
-    if (child.AsRefLayer()) {
-      continue;
-    }
-
-    LayerMetricsWrapper target = FindScrolledLayerRecursive(aScrollbar, child);
-    if (target) {
-      return target;
-    }
-  }
-  return LayerMetricsWrapper();
-}
-
-static LayerMetricsWrapper
 FindScrolledLayerForScrollbar(Layer* aScrollbar, bool* aOutIsAncestor)
 {
   // First check if the scrolled layer is an ancestor of the scrollbar layer.
   LayerMetricsWrapper root(aScrollbar->Manager()->GetRoot());
   LayerMetricsWrapper prevAncestor(aScrollbar);
+  LayerMetricsWrapper scrolledLayer;
+
   for (LayerMetricsWrapper ancestor(aScrollbar); ancestor; ancestor = ancestor.GetParent()) {
     // Don't walk into remote layer trees; the scrollbar will always be in
     // the same layer space.
     if (ancestor.AsRefLayer()) {
       root = prevAncestor;
       break;
     }
     prevAncestor = ancestor;
 
     if (LayerIsScrollbarTarget(ancestor, aScrollbar)) {
       *aOutIsAncestor = true;
       return ancestor;
     }
   }
 
   // Search the entire layer space of the scrollbar.
-  return FindScrolledLayerRecursive(aScrollbar, root);
+  ForEachNode<ForwardIterator>(
+      root,
+      [&root, &scrolledLayer, &aScrollbar](LayerMetricsWrapper aLayerMetrics)
+      {
+        // Do not recurse into RefLayers, since our initial aSubtreeRoot is the
+        // root (or RefLayer root) of a single layer space to search.
+        if (root != aLayerMetrics && aLayerMetrics.AsRefLayer()) {
+          return TraversalFlag::Skip;
+        }
+        if (LayerIsScrollbarTarget(aLayerMetrics, aScrollbar)) {
+          scrolledLayer = aLayerMetrics;
+          return TraversalFlag::Abort;
+        }
+        return TraversalFlag::Continue;
+      }
+  );
+  return scrolledLayer;
 }
 
 void
 AsyncCompositionManager::ApplyAsyncTransformToScrollbar(Layer* aLayer)
 {
   // If this layer corresponds to a scrollbar, then there should be a layer that
   // is a previous sibling or a parent that has a matching ViewID on its FrameMetrics.
   // That is the content that this scrollbar is for. We pick up the transient