Bug 1227231: Use generic tree traversal algorithms for loops over Layer trees. r=botond draft
authorKevin Wern <kevin.m.wern@gmail.com>
Thu, 10 Mar 2016 01:20:40 -0800
changeset 366107 016d3c37e0679df7037dacd3366d3fa7748d0703
parent 366106 ad59be79e6ed560146566bc76d802460844e1ec3
child 366108 4a34dad4b8f1593e503a6788df7780e453b93d48
push id17894
push userbballo@mozilla.com
push dateWed, 11 May 2016 23:59:13 +0000
reviewersbotond
bugs1227231
milestone49.0a1
Bug 1227231: Use generic tree traversal algorithms for loops over Layer trees. r=botond Create an Iterator type with classes ForwardIterator and ReverseIterator, having GetFirstChild/GetNextSibling and GetLastChild/GetPrevSibling methods, respectively. Specify the iterator type for each call to ForEachNode. With this, we can support trees with forward and reverse sibling structures. Additionally, apply these algorithms to all Layer recursive traversals, where applicable. Update tests to ensure both directions yield expected results. MozReview-Commit-ID: iYpX22XHTa
gfx/layers/LayerTreeInvalidation.cpp
gfx/layers/Layers.cpp
gfx/layers/RenderTrace.cpp
gfx/layers/TreeTraversal.h
gfx/layers/apz/src/APZCTreeManager.cpp
gfx/layers/basic/BasicLayerManager.cpp
gfx/layers/composite/AsyncCompositionManager.cpp
gfx/layers/composite/AsyncCompositionManager.h
gfx/layers/composite/LayerManagerComposite.cpp
gfx/layers/ipc/CompositorBridgeParent.cpp
gfx/layers/ipc/LayerTransactionParent.cpp
gfx/tests/gtest/TestTreeTraversal.cpp
--- a/gfx/layers/LayerTreeInvalidation.cpp
+++ b/gfx/layers/LayerTreeInvalidation.cpp
@@ -19,16 +19,17 @@
 #include "nsDataHashtable.h"            // for nsDataHashtable
 #include "nsDebug.h"                    // for NS_ASSERTION
 #include "nsHashKeys.h"                 // for nsPtrHashKey
 #include "nsISupportsImpl.h"            // for Layer::AddRef, etc
 #include "nsRect.h"                     // for IntRect
 #include "nsTArray.h"                   // for AutoTArray, nsTArray_Impl
 #include "mozilla/layers/ImageHost.h"
 #include "mozilla/layers/LayerManagerComposite.h"
+#include "TreeTraversal.h"              // for ForEachNode
 
 using namespace mozilla::gfx;
 
 namespace mozilla {
 namespace layers {
 
 struct LayerPropertiesBase;
 UniquePtr<LayerPropertiesBase> CloneLayerTreePropertiesInternal(Layer* aRoot, bool aIsMask = false);
@@ -97,38 +98,38 @@ AddRegion(nsIntRegion& aDest, const nsIn
 }
 
 /**
  * Walks over this layer, and all descendant layers.
  * If any of these are a ContainerLayer that reports invalidations to a PresShell,
  * then report that the entire bounds have changed.
  */
 static void
-NotifySubdocumentInvalidationRecursive(Layer* aLayer, NotifySubDocInvalidationFunc aCallback)
+NotifySubdocumentInvalidation(Layer* aLayer, NotifySubDocInvalidationFunc aCallback)
 {
-  aLayer->ClearInvalidRect();
-  ContainerLayer* container = aLayer->AsContainerLayer();
-
-  if (aLayer->GetMaskLayer()) {
-    NotifySubdocumentInvalidationRecursive(aLayer->GetMaskLayer(), aCallback);
-  }
-  for (size_t i = 0; i < aLayer->GetAncestorMaskLayerCount(); i++) {
-    Layer* maskLayer = aLayer->GetAncestorMaskLayerAt(i);
-    NotifySubdocumentInvalidationRecursive(maskLayer, aCallback);
-  }
-
-  if (!container) {
-    return;
-  }
-
-  for (Layer* child = container->GetFirstChild(); child; child = child->GetNextSibling()) {
-    NotifySubdocumentInvalidationRecursive(child, aCallback);
-  }
-
-  aCallback(container, container->GetLocalVisibleRegion().ToUnknownRegion());
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [aCallback] (Layer* layer)
+      {
+        layer->ClearInvalidRect();
+        if (layer->GetMaskLayer()) {
+          NotifySubdocumentInvalidation(layer->GetMaskLayer(), aCallback);
+        }
+        for (size_t i = 0; i < layer->GetAncestorMaskLayerCount(); i++) {
+          Layer* maskLayer = layer->GetAncestorMaskLayerAt(i);
+          NotifySubdocumentInvalidation(maskLayer, aCallback);
+        }
+      },
+      [aCallback] (Layer* layer)
+      {
+        ContainerLayer* container = layer->AsContainerLayer();
+        if (container) {
+          aCallback(container, container->GetLocalVisibleRegion().ToUnknownRegion());
+        }
+      });
 }
 
 struct LayerPropertiesBase : public LayerProperties
 {
   explicit LayerPropertiesBase(Layer* aLayer)
     : mLayer(aLayer)
     , mMaskLayer(nullptr)
     , mVisibleRegion(mLayer->GetLocalVisibleRegion().ToUnknownRegion())
@@ -341,17 +342,17 @@ struct ContainerLayerProperties : public
         // |child| is new, or was reordered to a higher index
         invalidateChildsCurrentArea = true;
       }
       if (invalidateChildsCurrentArea) {
         aGeometryChanged = true;
         AddTransformedRegion(result, child->GetLocalVisibleRegion().ToUnknownRegion(),
                              GetTransformForInvalidation(child));
         if (aCallback) {
-          NotifySubdocumentInvalidationRecursive(child, aCallback);
+          NotifySubdocumentInvalidation(child, aCallback);
         } else {
           ClearInvalidations(child);
         }
       }
       childrenChanged |= invalidateChildsCurrentArea;
     }
 
     // Process remaining removed children.
@@ -583,42 +584,40 @@ CloneLayerTreePropertiesInternal(Layer* 
 LayerProperties::CloneFrom(Layer* aRoot)
 {
   return CloneLayerTreePropertiesInternal(aRoot);
 }
 
 /* static */ void
 LayerProperties::ClearInvalidations(Layer *aLayer)
 {
-  aLayer->ClearInvalidRect();
-  if (aLayer->GetMaskLayer()) {
-    ClearInvalidations(aLayer->GetMaskLayer());
-  }
-  for (size_t i = 0; i < aLayer->GetAncestorMaskLayerCount(); i++) {
-    ClearInvalidations(aLayer->GetAncestorMaskLayerAt(i));
-  }
+  ForEachNode<ForwardIterator>(
+        aLayer,
+        [] (Layer* layer)
+        {
+          layer->ClearInvalidRect();
+          if (layer->GetMaskLayer()) {
+            ClearInvalidations(layer->GetMaskLayer());
+          }
+          for (size_t i = 0; i < layer->GetAncestorMaskLayerCount(); i++) {
+            ClearInvalidations(layer->GetAncestorMaskLayerAt(i));
+          }
 
-  ContainerLayer* container = aLayer->AsContainerLayer();
-  if (!container) {
-    return;
-  }
-
-  for (Layer* child = container->GetFirstChild(); child; child = child->GetNextSibling()) {
-    ClearInvalidations(child);
-  }
+        }
+      );
 }
 
 nsIntRegion
 LayerPropertiesBase::ComputeDifferences(Layer* aRoot, NotifySubDocInvalidationFunc aCallback,
                                         bool* aGeometryChanged = nullptr)
 {
   NS_ASSERTION(aRoot, "Must have a layer tree to compare against!");
   if (mLayer != aRoot) {
     if (aCallback) {
-      NotifySubdocumentInvalidationRecursive(aRoot, aCallback);
+      NotifySubdocumentInvalidation(aRoot, aCallback);
     } else {
       ClearInvalidations(aRoot);
     }
     IntRect result = TransformRect(aRoot->GetLocalVisibleRegion().ToUnknownRegion().GetBounds(),
                                      aRoot->GetLocalTransform());
     result = result.Union(OldTransformedBounds());
     if (aGeometryChanged != nullptr) {
       *aGeometryChanged = true;
--- a/gfx/layers/Layers.cpp
+++ b/gfx/layers/Layers.cpp
@@ -38,16 +38,17 @@
 #include "mozilla/layers/PersistentBufferProvider.h"
 #include "mozilla/layers/ShadowLayers.h"  // for ShadowableLayer
 #include "nsAString.h"
 #include "nsCSSValue.h"                 // for nsCSSValue::Array, etc
 #include "nsPrintfCString.h"            // for nsPrintfCString
 #include "nsStyleStruct.h"              // for nsTimingFunction, etc
 #include "protobuf/LayerScopePacket.pb.h"
 #include "mozilla/Compression.h"
+#include "TreeTraversal.h"              // for ForEachNode
 
 uint8_t gLayerManagerLayerBuilder;
 
 namespace mozilla {
 namespace layers {
 
 FILE*
 FILEOrDefault(FILE* aFile)
@@ -511,33 +512,33 @@ Layer::SetAnimations(const AnimationArra
   }
 
   Mutated();
 }
 
 void
 Layer::StartPendingAnimations(const TimeStamp& aReadyTime)
 {
-  bool updated = false;
-  for (size_t animIdx = 0, animEnd = mAnimations.Length();
-       animIdx < animEnd; animIdx++) {
-    Animation& anim = mAnimations[animIdx];
-    if (anim.startTime().IsNull()) {
-      anim.startTime() = aReadyTime - anim.initialCurrentTime();
-      updated = true;
-    }
-  }
-
-  if (updated) {
-    Mutated();
-  }
-
-  for (Layer* child = GetFirstChild(); child; child = child->GetNextSibling()) {
-    child->StartPendingAnimations(aReadyTime);
-  }
+  ForEachNode<ForwardIterator>(
+      this,
+      [&aReadyTime](Layer *layer)
+      {
+        bool updated = false;
+        for (size_t animIdx = 0, animEnd = layer->mAnimations.Length();
+             animIdx < animEnd; animIdx++) {
+          Animation& anim = layer->mAnimations[animIdx];
+          if (anim.startTime().IsNull()) {
+            anim.startTime() = aReadyTime - anim.initialCurrentTime();
+            updated = true;
+          }
+        }
+        if (updated) {
+          layer->Mutated();
+        }
+      });
 }
 
 void
 Layer::SetAsyncPanZoomController(uint32_t aIndex, AsyncPanZoomController *controller)
 {
   MOZ_ASSERT(aIndex < GetScrollMetadataCount());
   mApzcs[aIndex] = controller;
 }
@@ -558,25 +559,26 @@ void
 Layer::ScrollMetadataChanged()
 {
   mApzcs.SetLength(GetScrollMetadataCount());
 }
 
 void
 Layer::ApplyPendingUpdatesToSubtree()
 {
-  ApplyPendingUpdatesForThisTransaction();
-  for (Layer* child = GetFirstChild(); child; child = child->GetNextSibling()) {
-    child->ApplyPendingUpdatesToSubtree();
-  }
-  if (!GetParent()) {
-    // Once we're done recursing through the whole tree, clear the pending
-    // updates from the manager.
-    Manager()->ClearPendingScrollInfoUpdate();
-  }
+  ForEachNode<ForwardIterator>(
+      this,
+      [] (Layer *layer)
+      {
+        layer->ApplyPendingUpdatesForThisTransaction();
+      });
+
+  // Once we're done recursing through the whole tree, clear the pending
+  // updates from the manager.
+  Manager()->ClearPendingScrollInfoUpdate();
 }
 
 bool
 Layer::IsOpaqueForVisibility()
 {
   return GetEffectiveOpacity() == 1.0f &&
          GetEffectiveMixBlendMode() == CompositionOp::OP_OVER;
 }
@@ -1332,25 +1334,31 @@ ContainerLayer::HasMultipleChildren()
 }
 
 /**
  * Collect all leaf descendants of the current 3D context.
  */
 void
 ContainerLayer::Collect3DContextLeaves(nsTArray<Layer*>& aToSort)
 {
-  for (Layer* l = GetFirstChild(); l; l = l->GetNextSibling()) {
-    ContainerLayer* container = l->AsContainerLayer();
-    if (container && container->Extend3DContext() &&
-        !container->UseIntermediateSurface()) {
-      container->Collect3DContextLeaves(aToSort);
-    } else {
-      aToSort.AppendElement(l);
-    }
-  }
+  ForEachNode<ForwardIterator>(
+      (Layer*) this,
+      [this, &aToSort](Layer* layer)
+      {
+        ContainerLayer* container = layer->AsContainerLayer();
+        if (layer == this || (container && container->Extend3DContext() &&
+            !container->UseIntermediateSurface())) {
+          return TraversalFlag::Continue;
+        }
+        else {
+          aToSort.AppendElement(layer);
+          return TraversalFlag::Skip;
+        }
+      }
+  );
 }
 
 void
 ContainerLayer::SortChildrenBy3DZOrder(nsTArray<Layer*>& aArray)
 {
   AutoTArray<Layer*, 10> toSort;
 
   for (Layer* l = GetFirstChild(); l; l = l->GetNextSibling()) {
--- a/gfx/layers/RenderTrace.cpp
+++ b/gfx/layers/RenderTrace.cpp
@@ -3,58 +3,52 @@
  * 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/. */
 
 #include "RenderTrace.h"
 
 // If rendertrace is off let's no compile this code
 #ifdef MOZ_RENDERTRACE
 #include "Layers.h"
+#include "TreeTraversal.h"              // for ForEachNode
 
 
 namespace mozilla {
 namespace layers {
 
-static int colorId = 0;
-
 static gfx::Matrix4x4 GetRootTransform(Layer *aLayer) {
   gfx::Matrix4x4 layerTrans = aLayer->GetTransform();
   layerTrans.ProjectTo2D();
   if (aLayer->GetParent() != nullptr) {
     return GetRootTransform(aLayer->GetParent()) * layerTrans;
   }
   return layerTrans;
 }
 
-void RenderTraceLayers(Layer *aLayer, const char *aColor, const gfx::Matrix4x4 aRootTransform, bool aReset) {
-  if (!aLayer)
-    return;
-
-  gfx::Matrix4x4 trans = aRootTransform * aLayer->GetTransform();
-  trans.ProjectTo2D();
-  gfx::IntRect clipRect = aLayer->GetLocalVisibleRegion().GetBounds();
-  Rect rect(clipRect.x, clipRect.y, clipRect.width, clipRect.height);
-  trans.TransformBounds(rect);
+void RenderTraceLayers(Layer *aLayer, const char *aColor, const gfx::Matrix4x4 aRootTransform) {
+  int colorId = 0;
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&colorId] (Layer *layer)
+      {
+        gfx::Matrix4x4 trans = aRootTransform * layer->GetTransform();
+        trans.ProjectTo2D();
+        gfx::IntRect clipRect = layer->GetLocalVisibleRegion().GetBounds();
+        Rect rect(clipRect.x, clipRect.y, clipRect.width, clipRect.height);
+        trans.TransformBounds(rect);
 
-  if (strcmp(aLayer->Name(), "ContainerLayer") != 0 &&
-      strcmp(aLayer->Name(), "ContainerLayerComposite") != 0) {
-    printf_stderr("%s RENDERTRACE %u rect #%02X%s %i %i %i %i\n",
-      aLayer->Name(), (int)PR_IntervalNow(),
-      colorId, aColor,
-      (int)rect.x, (int)rect.y, (int)rect.width, (int)rect.height);
-  }
-
-  colorId++;
-
-  for (Layer* child = aLayer->GetFirstChild();
-        child; child = child->GetNextSibling()) {
-    RenderTraceLayers(child, aColor, aRootTransform, false);
-  }
-
-  if (aReset) colorId = 0;
+        if (strcmp(layer->Name(), "ContainerLayer") != 0 &&
+            strcmp(layer->Name(), "ContainerLayerComposite") != 0) {
+          printf_stderr("%s RENDERTRACE %u rect #%02X%s %i %i %i %i\n",
+            layer->Name(), (int)PR_IntervalNow(),
+            colorId, aColor,
+            (int)rect.x, (int)rect.y, (int)rect.width, (int)rect.height);
+        }
+        colorId++;
+      });
 }
 
 void RenderTraceInvalidateStart(Layer *aLayer, const char *aColor, const gfx::IntRect aRect) {
   gfx::Matrix4x4 trans = GetRootTransform(aLayer);
   gfx::Rect rect(aRect.x, aRect.y, aRect.width, aRect.height);
   trans.TransformBounds(rect);
 
   printf_stderr("%s RENDERTRACE %u fillrect #%s %i %i %i %i\n",
--- a/gfx/layers/TreeTraversal.h
+++ b/gfx/layers/TreeTraversal.h
@@ -21,43 +21,80 @@ namespace layers {
  * 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* NextSibling(Node* n) {
+      return n->GetNextSibling();
+    }
+    template <typename Node>
+    static Node* FirstChild(Node* n) {
+      return n->GetFirstChild();
+    }
+};
+class ReverseIterator
+{
+  public:
+    template <typename Node>
+    static Node* NextSibling(Node* n) {
+      return n->GetPrevSibling();
+    }
+    template <typename Node>
+    static Node* FirstChild(Node* n) {
+      return n->GetLastChild();
+    }
+};
+
+/*
  * 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 Node, typename PreAction, typename PostAction>
+template <typename Iterator, typename Node, typename PreAction, typename PostAction>
 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 = aRoot->GetLastChild();
+    for (Node* child = Iterator::FirstChild(aRoot);
          child;
-         child = child->GetPrevSibling()) {
-      bool abort = ForEachNode(child, aPreAction, aPostAction);
+         child = Iterator::NextSibling(child)) {
+      bool abort = ForEachNode<Iterator>(child, aPreAction, aPostAction);
       if (abort) {
         return true;
       }
     }
 
     result = aPostAction(aRoot);
 
     if (result == TraversalFlag::Abort) {
@@ -67,145 +104,147 @@ 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 Node, typename PreAction, typename PostAction>
+template <typename Iterator, typename Node, typename PreAction, typename PostAction>
 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 = aRoot->GetLastChild();
+  for (Node* child = Iterator::FirstChild(aRoot);
        child;
-       child = child->GetPrevSibling()) {
-    ForEachNode(child, aPreAction, aPostAction);
+       child = Iterator::NextSibling(child)) {
+    ForEachNode<Iterator>(child, aPreAction, aPostAction);
   }
 
   aPostAction(aRoot);
 }
 
 /*
  * ForEachNode pre-order traversal, using TraversalFlag.
  */
-template <typename Node, typename PreAction>
+template <typename Iterator, typename Node, typename PreAction>
 auto ForEachNode(Node* aRoot, const PreAction& aPreAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), TraversalFlag>::value, bool>::Type
 {
-  return ForEachNode(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 Node, typename PreAction>
+template <typename Iterator, typename Node, typename PreAction>
 auto ForEachNode(Node* aRoot, const PreAction& aPreAction) ->
 typename EnableIf<IsSame<decltype(aPreAction(aRoot)), void>::value, void>::Type
 {
-  ForEachNode(aRoot, aPreAction, [](Node* aNode){});
+  ForEachNode<Iterator>(aRoot, aPreAction, [](Node* aNode){});
 }
 
 /*
  * ForEachNode post-order traversal, using TraversalFlag.
  */
-template <typename Node, typename PostAction>
+template <typename Iterator, typename Node, typename PostAction>
 auto ForEachNodePostOrder(Node* aRoot, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPostAction(aRoot)), TraversalFlag>::value, bool>::Type
 {
-  return ForEachNode(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 Node, typename PostAction>
+template <typename Iterator, typename Node, typename PostAction>
 auto ForEachNodePostOrder(Node* aRoot, const PostAction& aPostAction) ->
 typename EnableIf<IsSame<decltype(aPostAction(aRoot)), void>::value, void>::Type
 {
-  ForEachNode(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.
  *
- * |Node| should have methods GetLastChild() and GetPrevSibling().
+ * See ForEachNode() for the requirements on |Iterator| and |Node|
  */
-template <typename Node, typename Condition>
+template <typename Iterator, typename Node, typename Condition>
 Node* BreadthFirstSearch(Node* aRoot, const Condition& aCondition)
 {
   if (!aRoot) {
     return nullptr;
   }
 
   std::queue<Node*> queue;
   queue.push(aRoot);
   while (!queue.empty()) {
     Node* node = queue.front();
     queue.pop();
 
     if (aCondition(node)) {
       return node;
     }
 
-    for (Node* child = node->GetLastChild();
+    for (Node* child = Iterator::FirstChild(node);
          child;
-         child = child->GetPrevSibling()) {
+         child = Iterator::NextSibling(child)) {
       queue.push(child);
     }
   }
 
   return nullptr;
 }
 
 /*
  * 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.
  *
- * |Node| should have methods GetLastChild() and GetPrevSibling().
+ * See ForEachNode() for the requirements on |Iterator| and |Node|
  */
-template <typename Node, typename Condition>
+template <typename Iterator, typename Node, typename Condition>
 Node* DepthFirstSearch(Node* aRoot, const Condition& aCondition)
 {
   Node* result = nullptr;
 
-  ForEachNode(aRoot,
+  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.
+ *
+ * See ForEachNode() for the requirements on |Iterator| and |Node|
  */
-template <typename Node, typename Condition>
+template <typename Iterator, typename Node, typename Condition>
 Node* DepthFirstSearchPostOrder(Node* aRoot, const Condition& aCondition)
 {
   Node* result = nullptr;
 
-  ForEachNodePostOrder(aRoot,
+  ForEachNodePostOrder<Iterator>(aRoot,
       [&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
@@ -25,17 +25,17 @@
 #include "mozilla/mozalloc.h"           // for operator new
 #include "mozilla/TouchEvents.h"
 #include "mozilla/Preferences.h"        // for Preferences
 #include "mozilla/EventStateManager.h"  // for WheelPrefs
 #include "nsDebug.h"                    // for NS_WARNING
 #include "nsPoint.h"                    // for nsIntPoint
 #include "nsThreadUtils.h"              // for NS_IsMainThread
 #include "OverscrollHandoffState.h"     // for OverscrollHandoffState
-#include "TreeTraversal.h"              // for generic tree traveral algorithms
+#include "TreeTraversal.h"              // for ForEachNode, BreadthFirstSearch, etc
 #include "LayersLogging.h"              // for Stringify
 #include "Units.h"                      // for ParentlayerPixel
 #include "GestureEventListener.h"       // for GestureEventListener::setLongTapEnabled
 #include "UnitTransforms.h"             // for ViewAs
 
 #define ENABLE_APZCTM_LOGGING 0
 // #define ENABLE_APZCTM_LOGGING 1
 
@@ -161,17 +161,17 @@ APZCTreeManager::UpdateHitTestingTree(Co
   // completely different place. In scenario (a) we would want to destroy the APZC while
   // walking the layer tree and noticing that the layer/APZC is no longer there. But if
   // we do that then we run into a problem in scenario (b) because we might encounter that
   // layer later during the walk. To handle both of these we have to 'remember' that the
   // layer was not found, and then do the destroy only at the end of the tree walk after
   // we are sure that the layer was removed and not just transplanted elsewhere. Doing that
   // as part of a recursive tree walk is hard and so maintaining a list and removing
   // APZCs that are still alive is much simpler.
-  ForEachNode(mRootNode.get(),
+  ForEachNode<ReverseIterator>(mRootNode.get(),
       [&state] (HitTestingTreeNode* aNode)
       {
         state.mNodesToDestroy.AppendElement(aNode);
       });
   mRootNode = nullptr;
 
   if (aRoot) {
     mApzcTreeLog << "[start]\n";
@@ -1260,17 +1260,17 @@ APZCTreeManager::UpdateZoomConstraints(c
     APZCTM_LOG("Recording constraints %s for guid %s\n",
       Stringify(aConstraints.value()).c_str(), Stringify(aGuid).c_str());
     mZoomConstraints[aGuid] = aConstraints.ref();
   } else {
     APZCTM_LOG("Removing constraints for guid %s\n", Stringify(aGuid).c_str());
     mZoomConstraints.erase(aGuid);
   }
   if (node && aConstraints) {
-    ForEachNode(node.get(),
+    ForEachNode<ReverseIterator>(node.get(),
         [&aConstraints, &node, this](HitTestingTreeNode* aNode)
         {
           if (aNode != node) {
             if (AsyncPanZoomController* childApzc = aNode->GetApzc()) {
               // We can have subtrees with their own zoom constraints or separate layers
               // id - leave these alone.
               if (childApzc->HasNoParentWithSameLayersId() ||
                   this->mZoomConstraints.find(childApzc->GetGuid()) != this->mZoomConstraints.end()) {
@@ -1307,17 +1307,17 @@ APZCTreeManager::FlushRepaintsToClearScr
   // know which APZC got hit! This leads to a circular dependency; the only way
   // to get out of it is to make sure that the untransform for all the possible
   // matched APZCs is the same. It is simplest to ensure that by flushing the
   // pending repaint requests, which makes all of the untransforms empty (and
   // therefore equal).
   MutexAutoLock lock(mTreeLock);
   mTreeLock.AssertCurrentThreadOwns();
 
-  ForEachNode(mRootNode.get(),
+  ForEachNode<ReverseIterator>(mRootNode.get(),
       [](HitTestingTreeNode* aNode)
       {
         if (aNode->IsPrimaryHolder()) {
           MOZ_ASSERT(aNode->GetApzc());
           aNode->GetApzc()->FlushRepaintForNewInputBlock();
         }
       });
 }
@@ -1351,17 +1351,17 @@ APZCTreeManager::ClearTree()
 
   MutexAutoLock lock(mTreeLock);
 
   // Collect the nodes into a list, and then destroy each one.
   // We can't destroy them as we collect them, because ForEachNode()
   // does a pre-order traversal of the tree, and Destroy() nulls out
   // the fields needed to reach the children of the node.
   nsTArray<RefPtr<HitTestingTreeNode>> nodesToDestroy;
-  ForEachNode(mRootNode.get(),
+  ForEachNode<ReverseIterator>(mRootNode.get(),
       [&nodesToDestroy](HitTestingTreeNode* aNode)
       {
         nodesToDestroy.AppendElement(aNode);
       });
 
   for (size_t i = 0; i < nodesToDestroy.Length(); i++) {
     nodesToDestroy[i]->Destroy();
   }
@@ -1570,17 +1570,17 @@ APZCTreeManager::GetTargetAPZC(const Scr
   return apzc.forget();
 }
 
 already_AddRefed<HitTestingTreeNode>
 APZCTreeManager::GetTargetNode(const ScrollableLayerGuid& aGuid,
                                GuidComparator aComparator)
 {
   mTreeLock.AssertCurrentThreadOwns();
-  RefPtr<HitTestingTreeNode> target = DepthFirstSearchPostOrder(mRootNode.get(),
+  RefPtr<HitTestingTreeNode> target = DepthFirstSearchPostOrder<ReverseIterator>(mRootNode.get(),
       [&aGuid, &aComparator](HitTestingTreeNode* node)
       {
         bool matches = false;
         if (node->GetApzc()) {
           if (aComparator) {
             matches = aComparator(aGuid, node->GetApzc()->GetGuid());
           } else {
             matches = node->GetApzc()->Matches(aGuid);
@@ -1701,17 +1701,17 @@ APZCTreeManager::SetLongTapEnabled(bool 
     NewRunnableFunction(GestureEventListener::SetLongTapEnabled, aLongTapEnabled));
 }
 
 RefPtr<HitTestingTreeNode>
 APZCTreeManager::FindScrollNode(const AsyncDragMetrics& aDragMetrics)
 {
   MutexAutoLock lock(mTreeLock);
 
-  return DepthFirstSearch(mRootNode.get(),
+  return DepthFirstSearch<ReverseIterator>(mRootNode.get(),
       [&aDragMetrics](HitTestingTreeNode* aNode) {
         return aNode->MatchesScrollDragMetrics(aDragMetrics);
       });
 }
 
 AsyncPanZoomController*
 APZCTreeManager::GetAPZCAtPoint(HitTestingTreeNode* aNode,
                                 const ParentLayerPoint& aHitTestPoint,
@@ -1722,17 +1722,17 @@ APZCTreeManager::GetAPZCAtPoint(HitTesti
 
   // This walks the tree in depth-first, reverse order, so that it encounters
   // APZCs front-to-back on the screen.
   HitTestingTreeNode* resultNode;
   HitTestingTreeNode* root = aNode;
   std::stack<ParentLayerPoint> hitTestPoints;
   hitTestPoints.push(aHitTestPoint);
 
-  ForEachNode(root,
+  ForEachNode<ReverseIterator>(root,
       [&hitTestPoints](HitTestingTreeNode* aNode) {
         if (aNode->IsOutsideClip(hitTestPoints.top())) {
           // If the point being tested is outside the clip region for this node
           // then we don't need to test against this node or any of its children.
           // Just skip it and move on.
           APZCTM_LOG("Point %f %f outside clip for node %p\n",
             hitTestPoints.top().x, hitTestPoints.top().y, aNode);
           return TraversalFlag::Skip;
@@ -1803,32 +1803,32 @@ APZCTreeManager::GetAPZCAtPoint(HitTesti
   return nullptr;
 }
 
 AsyncPanZoomController*
 APZCTreeManager::FindRootApzcForLayersId(uint64_t aLayersId) const
 {
   mTreeLock.AssertCurrentThreadOwns();
 
-  HitTestingTreeNode* resultNode = BreadthFirstSearch(mRootNode.get(),
+  HitTestingTreeNode* resultNode = BreadthFirstSearch<ReverseIterator>(mRootNode.get(),
       [aLayersId](HitTestingTreeNode* aNode) {
         AsyncPanZoomController* apzc = aNode->GetApzc();
         return apzc
             && apzc->GetLayersId() == aLayersId
             && apzc->IsRootForLayersId();
       });
   return resultNode ? resultNode->GetApzc() : nullptr;
 }
 
 AsyncPanZoomController*
 APZCTreeManager::FindRootContentApzcForLayersId(uint64_t aLayersId) const
 {
   mTreeLock.AssertCurrentThreadOwns();
 
-  HitTestingTreeNode* resultNode = BreadthFirstSearch(mRootNode.get(),
+  HitTestingTreeNode* resultNode = BreadthFirstSearch<ReverseIterator>(mRootNode.get(),
       [aLayersId](HitTestingTreeNode* aNode) {
         AsyncPanZoomController* apzc = aNode->GetApzc();
         return apzc
             && apzc->GetLayersId() == aLayersId
             && apzc->IsRootContent();
       });
   return resultNode ? resultNode->GetApzc() : nullptr;
 }
@@ -1839,25 +1839,25 @@ APZCTreeManager::FindRootContentOrRootAp
   mTreeLock.AssertCurrentThreadOwns();
 
   // Note: this is intended to find the same "root" that would be found
   // by AsyncCompositionManager::ApplyAsyncContentTransformToTree inside
   // the MOZ_ANDROID_APZ block. That is, it should find the RCD node if there
   // is one, or the root APZC if there is not.
   // Since BreadthFirstSearch is a pre-order search, we first do a search for
   // the RCD, and then if we don't find one, we do a search for the root APZC.
-  HitTestingTreeNode* resultNode = BreadthFirstSearch(mRootNode.get(),
+  HitTestingTreeNode* resultNode = BreadthFirstSearch<ReverseIterator>(mRootNode.get(),
       [](HitTestingTreeNode* aNode) {
         AsyncPanZoomController* apzc = aNode->GetApzc();
         return apzc && apzc->IsRootContent();
       });
   if (resultNode) {
     return resultNode->GetApzc();
   }
-  resultNode = BreadthFirstSearch(mRootNode.get(),
+  resultNode = BreadthFirstSearch<ReverseIterator>(mRootNode.get(),
       [](HitTestingTreeNode* aNode) {
         AsyncPanZoomController* apzc = aNode->GetApzc();
         return (apzc != nullptr);
       });
   return resultNode ? resultNode->GetApzc() : nullptr;
 }
 
 /* The methods GetScreenToApzcTransform() and GetApzcToGeckoTransform() return
--- a/gfx/layers/basic/BasicLayerManager.cpp
+++ b/gfx/layers/basic/BasicLayerManager.cpp
@@ -1,16 +1,17 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
  * 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/. */
 
 #include <stdint.h>                     // for uint32_t
 #include <stdlib.h>                     // for rand, RAND_MAX
 #include <sys/types.h>                  // for int32_t
+#include <stack>                        // for stack
 #include "BasicContainerLayer.h"        // for BasicContainerLayer
 #include "BasicLayersImpl.h"            // for ToData, BasicReadbackLayer, etc
 #include "GeckoProfiler.h"              // for PROFILER_LABEL
 #include "ImageContainer.h"             // for ImageFactory
 #include "Layers.h"                     // for Layer, ContainerLayer, etc
 #include "ReadbackLayer.h"              // for ReadbackLayer
 #include "ReadbackProcessor.h"          // for ReadbackProcessor
 #include "RenderTrace.h"                // for RenderTraceLayers, etc
@@ -39,16 +40,18 @@
 #include "nsAutoPtr.h"                  // for nsRefPtr
 #include "nsCOMPtr.h"                   // for already_AddRefed
 #include "nsDebug.h"                    // for NS_ASSERTION, etc
 #include "nsISupportsImpl.h"            // for gfxContext::Release, etc
 #include "nsPoint.h"                    // for nsIntPoint
 #include "nsRect.h"                     // for mozilla::gfx::IntRect
 #include "nsRegion.h"                   // for nsIntRegion, etc
 #include "nsTArray.h"                   // for AutoTArray
+#include "TreeTraversal.h"              // for ForEachNode
+
 class nsIWidget;
 
 namespace mozilla {
 namespace layers {
 
 using namespace mozilla::gfx;
 
 /**
@@ -480,66 +483,81 @@ MarkLayersHidden(Layer* aLayer, const In
  * all layers to the same coordinate system (the "root coordinate system").
  * MarkLayersHidden must be called before calling this.
  * @param aVisibleRect the rectangle of aLayer that is visible (i.e. not
  * clipped and in the dirty rect), in the root coordinate system.
  */
 static void
 ApplyDoubleBuffering(Layer* aLayer, const IntRect& aVisibleRect)
 {
-  BasicImplData* data = ToData(aLayer);
-  if (data->IsHidden())
-    return;
+  std::stack<IntRect> visibleRectStack;
+  visibleRectStack.push(aVisibleRect);
 
-  IntRect newVisibleRect(aVisibleRect);
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&aLayer, &visibleRectStack](Layer* layer) {
+        BasicImplData* data = ToData(layer);
+        if (layer != aLayer) {
+          data->SetClipToVisibleRegion(true);
+        }
+        if (data->IsHidden()) {
+          return TraversalFlag::Skip;
+        }
+
+        IntRect newVisibleRect(visibleRectStack.top());
 
-  {
-    const Maybe<ParentLayerIntRect>& clipRect = aLayer->GetLocalClipRect();
-    if (clipRect) {
-      IntRect cr = clipRect->ToUnknownRect();
-      // clipRect is in the container's coordinate system. Get it into the
-      // global coordinate system.
-      if (aLayer->GetParent()) {
-        Matrix tr;
-        if (aLayer->GetParent()->GetEffectiveTransform().CanDraw2D(&tr)) {
-          NS_ASSERTION(!ThebesMatrix(tr).HasNonIntegerTranslation(),
-                       "Parent can only have an integer translation");
-          cr += nsIntPoint(int32_t(tr._31), int32_t(tr._32));
+        {
+          const Maybe<ParentLayerIntRect>& clipRect = layer->GetLocalClipRect();
+          if (clipRect) {
+            IntRect cr = clipRect->ToUnknownRect();
+            // clipRect is in the container's coordinate system. Get it into the
+            // global coordinate system.
+            if (layer->GetParent()) {
+              Matrix tr;
+              if (layer->GetParent()->GetEffectiveTransform().CanDraw2D(&tr)) {
+                NS_ASSERTION(!ThebesMatrix(tr).HasNonIntegerTranslation(),
+                             "Parent can only have an integer translation");
+                cr += nsIntPoint(int32_t(tr._31), int32_t(tr._32));
+              } else {
+                NS_ERROR("Parent can only have an integer translation");
+              }
+            }
+            newVisibleRect.IntersectRect(newVisibleRect, cr);
+          }
+        }
+
+        BasicContainerLayer* container =
+          static_cast<BasicContainerLayer*>(layer->AsContainerLayer());
+        // Layers that act as their own backbuffers should be drawn to the destination
+        // using OP_SOURCE to ensure that alpha values in a transparent window are
+        // cleared. This can also be faster than OP_OVER.
+        if (!container) {
+          data->SetOperator(CompositionOp::OP_SOURCE);
+          data->SetDrawAtomically(true);
+          return TraversalFlag::Skip;
         } else {
-          NS_ERROR("Parent can only have an integer translation");
+          if (container->UseIntermediateSurface() ||
+              !container->ChildrenPartitionVisibleRegion(newVisibleRect)) {
+            // We need to double-buffer this container.
+            data->SetOperator(CompositionOp::OP_SOURCE);
+            container->ForceIntermediateSurface();
+            return TraversalFlag::Skip;
+          } else {
+            visibleRectStack.push(newVisibleRect);
+            return TraversalFlag::Continue;
+          }
         }
+
+      },
+      [&visibleRectStack](Layer* layer)
+      {
+        visibleRectStack.pop();
+        return TraversalFlag::Continue;
       }
-      newVisibleRect.IntersectRect(newVisibleRect, cr);
-    }
-  }
-
-  BasicContainerLayer* container =
-    static_cast<BasicContainerLayer*>(aLayer->AsContainerLayer());
-  // Layers that act as their own backbuffers should be drawn to the destination
-  // using OP_SOURCE to ensure that alpha values in a transparent window are
-  // cleared. This can also be faster than OP_OVER.
-  if (!container) {
-    data->SetOperator(CompositionOp::OP_SOURCE);
-    data->SetDrawAtomically(true);
-  } else {
-    if (container->UseIntermediateSurface() ||
-        !container->ChildrenPartitionVisibleRegion(newVisibleRect)) {
-      // We need to double-buffer this container.
-      data->SetOperator(CompositionOp::OP_SOURCE);
-      container->ForceIntermediateSurface();
-    } else {
-      // Tell the children to clip to their visible regions so our assumption
-      // that they don't paint outside their visible regions is valid!
-      for (Layer* child = aLayer->GetFirstChild(); child;
-           child = child->GetNextSibling()) {
-        ToData(child)->SetClipToVisibleRegion(true);
-        ApplyDoubleBuffering(child, newVisibleRect);
-      }
-    }
-  }
+  );
 }
 
 void
 BasicLayerManager::EndTransaction(DrawPaintedLayerCallback aCallback,
                                   void* aCallbackData,
                                   EndTransactionFlags aFlags)
 {
   mInTransaction = false;
--- a/gfx/layers/composite/AsyncCompositionManager.cpp
+++ b/gfx/layers/composite/AsyncCompositionManager.cpp
@@ -38,17 +38,17 @@
 #include "UnitTransforms.h"             // for TransformTo
 #include "gfxPrefs.h"
 #if defined(MOZ_WIDGET_ANDROID)
 # include <android/log.h>
 # include "AndroidBridge.h"
 #endif
 #include "GeckoProfiler.h"
 #include "FrameUniformityData.h"
-#include "TreeTraversal.h"
+#include "TreeTraversal.h"              // for ForEachNode, BreadthFirstSearch
 #include "VsyncSource.h"
 
 struct nsCSSValueSharedList;
 
 namespace mozilla {
 namespace layers {
 
 using namespace mozilla::gfx;
@@ -74,52 +74,53 @@ static void
 WalkTheTree(Layer* aLayer,
             bool& aReady,
             const TargetConfig& aTargetConfig,
             CompositorBridgeParent* aCompositor,
             bool& aHasRemote,
             bool aWillResolvePlugins,
             bool& aDidResolvePlugins)
 {
-  if (RefLayer* ref = aLayer->AsRefLayer()) {
-    aHasRemote = true;
-    if (const CompositorBridgeParent::LayerTreeState* state = CompositorBridgeParent::GetIndirectShadowTree(ref->GetReferentId())) {
-      if (Layer* referent = state->mRoot) {
-        if (!ref->GetLocalVisibleRegion().IsEmpty()) {
-          dom::ScreenOrientationInternal chromeOrientation = aTargetConfig.orientation();
-          dom::ScreenOrientationInternal contentOrientation = state->mTargetConfig.orientation();
-          if (!IsSameDimension(chromeOrientation, contentOrientation) &&
-              ContentMightReflowOnOrientationChange(aTargetConfig.naturalBounds())) {
-            aReady = false;
+
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&](Layer* layer)
+      {
+        if (RefLayer* ref = layer->AsRefLayer()) {
+          aHasRemote = true;
+          if (const CompositorBridgeParent::LayerTreeState* state = CompositorBridgeParent::GetIndirectShadowTree(ref->GetReferentId())) {
+            if (Layer* referent = state->mRoot) {
+              if (!ref->GetLocalVisibleRegion().IsEmpty()) {
+                dom::ScreenOrientationInternal chromeOrientation = aTargetConfig.orientation();
+                dom::ScreenOrientationInternal contentOrientation = state->mTargetConfig.orientation();
+                if (!IsSameDimension(chromeOrientation, contentOrientation) &&
+                    ContentMightReflowOnOrientationChange(aTargetConfig.naturalBounds())) {
+                  aReady = false;
+                }
+              }
+
+              if (OP == Resolve) {
+                ref->ConnectReferentLayer(referent);
+      #if defined(XP_WIN) || defined(MOZ_WIDGET_GTK)
+                if (aCompositor && aWillResolvePlugins) {
+                  aDidResolvePlugins |=
+                    aCompositor->UpdatePluginWindowState(ref->GetReferentId());
+                }
+      #endif
+              } else {
+                ref->DetachReferentLayer(referent);
+                WalkTheTree<OP>(referent, aReady, aTargetConfig,
+                                aCompositor, aHasRemote, aWillResolvePlugins,
+                                aDidResolvePlugins);
+              }
+            }
           }
         }
-
-        if (OP == Resolve) {
-          ref->ConnectReferentLayer(referent);
-#if defined(XP_WIN) || defined(MOZ_WIDGET_GTK)
-          if (aCompositor && aWillResolvePlugins) {
-            aDidResolvePlugins |=
-              aCompositor->UpdatePluginWindowState(ref->GetReferentId());
-          }
-#endif
-        } else {
-          ref->DetachReferentLayer(referent);
-          WalkTheTree<OP>(referent, aReady, aTargetConfig,
-                          aCompositor, aHasRemote, aWillResolvePlugins,
-                          aDidResolvePlugins);
-        }
-      }
-    }
-  }
-  for (Layer* child = aLayer->GetFirstChild();
-       child; child = child->GetNextSibling()) {
-    WalkTheTree<OP>(child, aReady, aTargetConfig,
-                    aCompositor, aHasRemote, aWillResolvePlugins,
-                    aDidResolvePlugins);
-  }
+        return TraversalFlag::Continue;
+      });
 }
 
 AsyncCompositionManager::AsyncCompositionManager(LayerManagerComposite* aManager)
   : mLayerManager(aManager)
   , mIsFirstPaint(true)
   , mLayersUpdated(false)
   , mPaintSyncId(0)
   , mReadyForCompose(true)
@@ -417,124 +418,124 @@ IsFixedOrSticky(Layer* aLayer)
   }
   if (aLayer->GetIsStickyPosition()) {
     return Some(aLayer->GetStickyScrollContainerId());
   }
   return Nothing();
 }
 
 void
-AsyncCompositionManager::AlignFixedAndStickyLayers(Layer* aLayer,
-                                                   Layer* aTransformedSubtreeRoot,
+AsyncCompositionManager::AlignFixedAndStickyLayers(Layer* aTransformedSubtreeRoot,
                                                    FrameMetrics::ViewID aTransformScrollId,
                                                    const LayerToParentLayerMatrix4x4& aPreviousTransformForRoot,
                                                    const LayerToParentLayerMatrix4x4& aCurrentTransformForRoot,
                                                    const ScreenMargin& aFixedLayerMargins,
                                                    ClipPartsCache* aClipPartsCache)
 {
-  bool needsAsyncTransformUnapplied = false;
-  if (Maybe<FrameMetrics::ViewID> fixedTo = IsFixedOrSticky(aLayer)) {
-    needsAsyncTransformUnapplied = AsyncTransformShouldBeUnapplied(aLayer,
-        *fixedTo, aTransformedSubtreeRoot, aTransformScrollId);
-  }
+  ForEachNode<ForwardIterator>(
+      aTransformedSubtreeRoot,
+      [&] (Layer* layer)
+      {
+        bool needsAsyncTransformUnapplied = false;
+        if (Maybe<FrameMetrics::ViewID> fixedTo = IsFixedOrSticky(layer)) {
+          needsAsyncTransformUnapplied = AsyncTransformShouldBeUnapplied(layer,
+              *fixedTo, aTransformedSubtreeRoot, aTransformScrollId);
+        }
 
-  // We want to process all the fixed and sticky descendants of
-  // aTransformedSubtreeRoot. Once we do encounter such a descendant, we don't
-  // need to recurse any deeper because the adjustment to the fixed or sticky
-  // layer will apply to its subtree.
-  if (!needsAsyncTransformUnapplied) {
-    for (Layer* child = aLayer->GetFirstChild(); child; child = child->GetNextSibling()) {
-      AlignFixedAndStickyLayers(child, aTransformedSubtreeRoot, aTransformScrollId,
-                                aPreviousTransformForRoot,
-                                aCurrentTransformForRoot, aFixedLayerMargins,
-                                aClipPartsCache);
-    }
-    return;
-  }
+        // We want to process all the fixed and sticky descendants of
+        // aTransformedSubtreeRoot. Once we do encounter such a descendant, we don't
+        // need to recurse any deeper because the adjustment to the fixed or sticky
+        // layer will apply to its subtree.
+        if (!needsAsyncTransformUnapplied) {
+          return TraversalFlag::Continue;
+        }
 
-  // Insert a translation so that the position of the anchor point is the same
-  // before and after the change to the transform of aTransformedSubtreeRoot.
+        // Insert a translation so that the position of the anchor point is the same
+        // before and after the change to the transform of aTransformedSubtreeRoot.
 
-  // Accumulate the transforms between this layer and the subtree root layer.
-  Matrix4x4 ancestorTransform;
-  AccumulateLayerTransforms(aLayer->GetParent(), aTransformedSubtreeRoot,
-                            ancestorTransform);
+        // Accumulate the transforms between this layer and the subtree root layer.
+        Matrix4x4 ancestorTransform;
+        AccumulateLayerTransforms(layer->GetParent(), aTransformedSubtreeRoot,
+                                  ancestorTransform);
 
-  // Calculate the cumulative transforms between the subtree root with the
-  // old transform and the current transform.
-  Matrix4x4 oldCumulativeTransform = ancestorTransform * aPreviousTransformForRoot.ToUnknownMatrix();
-  Matrix4x4 newCumulativeTransform = ancestorTransform * aCurrentTransformForRoot.ToUnknownMatrix();
-  if (newCumulativeTransform.IsSingular()) {
-    return;
-  }
+        // Calculate the cumulative transforms between the subtree root with the
+        // old transform and the current transform.
+        Matrix4x4 oldCumulativeTransform = ancestorTransform * aPreviousTransformForRoot.ToUnknownMatrix();
+        Matrix4x4 newCumulativeTransform = ancestorTransform * aCurrentTransformForRoot.ToUnknownMatrix();
+        if (newCumulativeTransform.IsSingular()) {
+          return TraversalFlag::Skip;
+        }
 
-  // Add in the layer's local transform, if it isn't already included in
-  // |aPreviousTransformForRoot| and |aCurrentTransformForRoot| (this happens
-  // when the fixed/sticky layer is itself the transformed subtree root).
-  Matrix4x4 localTransform;
-  GetBaseTransform(aLayer, &localTransform);
-  if (aLayer != aTransformedSubtreeRoot) {
-    oldCumulativeTransform = localTransform * oldCumulativeTransform;
-    newCumulativeTransform = localTransform * newCumulativeTransform;
-  }
+        // Add in the layer's local transform, if it isn't already included in
+        // |aPreviousTransformForRoot| and |aCurrentTransformForRoot| (this happens
+        // when the fixed/sticky layer is itself the transformed subtree root).
+        Matrix4x4 localTransform;
+        GetBaseTransform(layer, &localTransform);
+        if (layer != aTransformedSubtreeRoot) {
+          oldCumulativeTransform = localTransform * oldCumulativeTransform;
+          newCumulativeTransform = localTransform * newCumulativeTransform;
+        }
 
-  // Now work out the translation necessary to make sure the layer doesn't
-  // move given the new sub-tree root transform.
+        // Now work out the translation necessary to make sure the layer doesn't
+        // move given the new sub-tree root transform.
+
+        // Get the layer's fixed anchor point, in the layer's local coordinate space
+        // (before any cumulative transform is applied).
+        LayerPoint anchor = layer->GetFixedPositionAnchor();
 
-  // Get the layer's fixed anchor point, in the layer's local coordinate space
-  // (before any cumulative transform is applied).
-  LayerPoint anchor = aLayer->GetFixedPositionAnchor();
-
-  // Offset the layer's anchor point to make sure fixed position content
-  // respects content document fixed position margins.
-  LayerPoint offsetAnchor = anchor + GetLayerFixedMarginsOffset(aLayer, aFixedLayerMargins);
+        // Offset the layer's anchor point to make sure fixed position content
+        // respects content document fixed position margins.
+        LayerPoint offsetAnchor = anchor + GetLayerFixedMarginsOffset(layer, aFixedLayerMargins);
 
-  // Additionally transform the anchor to compensate for the change
-  // from the old cumulative transform to the new cumulative transform. We do
-  // this by using the old transform to take the offset anchor back into
-  // subtree root space, and then the inverse of the new cumulative transform
-  // to bring it back to layer space.
-  LayerPoint transformedAnchor = ViewAs<LayerPixel>(
-      newCumulativeTransform.Inverse() *
-      (oldCumulativeTransform * offsetAnchor.ToUnknownPoint()));
+        // Additionally transform the anchor to compensate for the change
+        // from the old cumulative transform to the new cumulative transform. We do
+        // this by using the old transform to take the offset anchor back into
+        // subtree root space, and then the inverse of the new cumulative transform
+        // to bring it back to layer space.
+        LayerPoint transformedAnchor = ViewAs<LayerPixel>(
+            newCumulativeTransform.Inverse() *
+            (oldCumulativeTransform * offsetAnchor.ToUnknownPoint()));
+
+        // We want to translate the layer by the difference between |transformedAnchor|
+        // and |anchor|. To achieve this, we will add a translation to the layer's
+        // transform. This translation will apply on top of the layer's local
+        // transform, but |anchor| and |transformedAnchor| are in a coordinate space
+        // where the local transform isn't applied yet, so apply it and then subtract
+        // to get the desired translation.
+        auto localTransformTyped = ViewAs<LayerToParentLayerMatrix4x4>(localTransform);
+        ParentLayerPoint translation = TransformBy(localTransformTyped, transformedAnchor)
+                                     - TransformBy(localTransformTyped, anchor);
 
-  // We want to translate the layer by the difference between |transformedAnchor|
-  // and |anchor|. To achieve this, we will add a translation to the layer's
-  // transform. This translation will apply on top of the layer's local
-  // transform, but |anchor| and |transformedAnchor| are in a coordinate space
-  // where the local transform isn't applied yet, so apply it and then subtract
-  // to get the desired translation.
-  auto localTransformTyped = ViewAs<LayerToParentLayerMatrix4x4>(localTransform);
-  ParentLayerPoint translation = TransformBy(localTransformTyped, transformedAnchor)
-                               - TransformBy(localTransformTyped, anchor);
+        if (layer->GetIsStickyPosition()) {
+          // For sticky positioned layers, the difference between the two rectangles
+          // defines a pair of translation intervals in each dimension through which
+          // the layer should not move relative to the scroll container. To
+          // accomplish this, we limit each dimension of the |translation| to that
+          // part of it which overlaps those intervals.
+          const LayerRect& stickyOuter = layer->GetStickyScrollRangeOuter();
+          const LayerRect& stickyInner = layer->GetStickyScrollRangeInner();
 
-  if (aLayer->GetIsStickyPosition()) {
-    // For sticky positioned layers, the difference between the two rectangles
-    // defines a pair of translation intervals in each dimension through which
-    // the layer should not move relative to the scroll container. To
-    // accomplish this, we limit each dimension of the |translation| to that
-    // part of it which overlaps those intervals.
-    const LayerRect& stickyOuter = aLayer->GetStickyScrollRangeOuter();
-    const LayerRect& stickyInner = aLayer->GetStickyScrollRangeInner();
+          // TODO: There's a unit mismatch here, as |translation| is in ParentLayer
+          //       space while |stickyOuter| and |stickyInner| are in Layer space.
+          translation.y = IntervalOverlap(translation.y, stickyOuter.y, stickyOuter.YMost()) -
+                          IntervalOverlap(translation.y, stickyInner.y, stickyInner.YMost());
+          translation.x = IntervalOverlap(translation.x, stickyOuter.x, stickyOuter.XMost()) -
+                          IntervalOverlap(translation.x, stickyInner.x, stickyInner.XMost());
+        }
 
-    // TODO: There's a unit mismatch here, as |translation| is in ParentLayer
-    //       space while |stickyOuter| and |stickyInner| are in Layer space.
-    translation.y = IntervalOverlap(translation.y, stickyOuter.y, stickyOuter.YMost()) -
-                    IntervalOverlap(translation.y, stickyInner.y, stickyInner.YMost());
-    translation.x = IntervalOverlap(translation.x, stickyOuter.x, stickyOuter.XMost()) -
-                    IntervalOverlap(translation.x, stickyInner.x, stickyInner.XMost());
-  }
+        // Finally, apply the translation to the layer transform. Note that in cases
+        // where the async transform on |aTransformedSubtreeRoot| affects this layer's
+        // clip rect, we need to apply the same translation to said clip rect, so
+        // that the effective transform on the clip rect takes it back to where it was
+        // originally, had there been no async scroll.
+        TranslateShadowLayer(layer, ThebesPoint(translation.ToUnknownPoint()),
+            true, aClipPartsCache);
 
-  // Finally, apply the translation to the layer transform. Note that in cases
-  // where the async transform on |aTransformedSubtreeRoot| affects this layer's
-  // clip rect, we need to apply the same translation to said clip rect, so
-  // that the effective transform on the clip rect takes it back to where it was
-  // originally, had there been no async scroll.
-  TranslateShadowLayer(aLayer, ThebesPoint(translation.ToUnknownPoint()),
-      true, aClipPartsCache);
+        return TraversalFlag::Skip;
+      });
 }
 
 static void
 SampleValue(float aPortion, Animation& aAnimation, StyleAnimationValue& aStart,
             StyleAnimationValue& aEnd, Animatable* aValue, Layer* aLayer)
 {
   StyleAnimationValue interpolatedValue;
   NS_ASSERTION(aStart.GetUnit() == aEnd.GetUnit() ||
@@ -574,119 +575,118 @@ SampleValue(float aPortion, Animation& a
   InfallibleTArray<TransformFunction> functions;
   functions.AppendElement(TransformMatrix(transform));
   *aValue = functions;
 }
 
 static bool
 SampleAnimations(Layer* aLayer, TimeStamp aPoint)
 {
-  AnimationArray& animations = aLayer->GetAnimations();
-  InfallibleTArray<AnimData>& animationData = aLayer->GetAnimationData();
-
   bool activeAnimations = false;
 
-  // Process in order, since later animations override earlier ones.
-  for (size_t i = 0, iEnd = animations.Length(); i < iEnd; ++i) {
-    Animation& animation = animations[i];
-    AnimData& animData = animationData[i];
-
-    activeAnimations = true;
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&activeAnimations, &aPoint] (Layer* layer)
+      {
+        AnimationArray& animations = layer->GetAnimations();
+        InfallibleTArray<AnimData>& animationData = layer->GetAnimationData();
 
-    MOZ_ASSERT(!animation.startTime().IsNull(),
-               "Failed to resolve start time of pending animations");
-    TimeDuration elapsedDuration =
-      (aPoint - animation.startTime()).MultDouble(animation.playbackRate());
-    // Skip animations that are yet to start.
-    //
-    // Currently, this should only happen when the refresh driver is under test
-    // control and is made to produce a time in the past or is restored from
-    // test control causing it to jump backwards in time.
-    //
-    // Since activeAnimations is true, this could mean we keep compositing
-    // unnecessarily during the delay, but so long as this only happens while
-    // the refresh driver is under test control that should be ok.
-    if (elapsedDuration.ToSeconds() < 0) {
-      continue;
-    }
+        // Process in order, since later animations override earlier ones.
+        for (size_t i = 0, iEnd = animations.Length(); i < iEnd; ++i) {
+          Animation& animation = animations[i];
+          AnimData& animData = animationData[i];
+
+          activeAnimations = true;
 
-    TimingParams timing;
-    timing.mDuration.emplace(animation.duration());
-    // Currently animations run on the compositor have their delay factored
-    // into their start time, hence the delay is effectively zero.
-    timing.mDelay = TimeDuration(0);
-    timing.mIterations = animation.iterations();
-    timing.mIterationStart = animation.iterationStart();
-    timing.mDirection =
-      static_cast<dom::PlaybackDirection>(animation.direction());
-    // Animations typically only run on the compositor during their active
-    // interval but if we end up sampling them outside that range (for
-    // example, while they are waiting to be removed) we currently just
-    // assume that we should fill.
-    timing.mFill = dom::FillMode::Both;
-    timing.mFunction =
-      AnimationUtils::TimingFunctionToComputedTimingFunction(
-        animation.easingFunction());
+          MOZ_ASSERT(!animation.startTime().IsNull(),
+                     "Failed to resolve start time of pending animations");
+          TimeDuration elapsedDuration =
+            (aPoint - animation.startTime()).MultDouble(animation.playbackRate());
+          // Skip animations that are yet to start.
+          //
+          // Currently, this should only happen when the refresh driver is under test
+          // control and is made to produce a time in the past or is restored from
+          // test control causing it to jump backwards in time.
+          //
+          // Since activeAnimations is true, this could mean we keep compositing
+          // unnecessarily during the delay, but so long as this only happens while
+          // the refresh driver is under test control that should be ok.
+          if (elapsedDuration.ToSeconds() < 0) {
+            continue;
+          }
 
-    ComputedTiming computedTiming =
-      dom::KeyframeEffectReadOnly::GetComputedTimingAt(
-        Nullable<TimeDuration>(elapsedDuration), timing);
-
-    MOZ_ASSERT(!computedTiming.mProgress.IsNull(),
-               "iteration progress should not be null");
+          TimingParams timing;
+          timing.mDuration.emplace(animation.duration());
+          // Currently animations run on the compositor have their delay factored
+          // into their start time, hence the delay is effectively zero.
+          timing.mDelay = TimeDuration(0);
+          timing.mIterations = animation.iterations();
+          timing.mIterationStart = animation.iterationStart();
+          timing.mDirection =
+            static_cast<dom::PlaybackDirection>(animation.direction());
+          // Animations typically only run on the compositor during their active
+          // interval but if we end up sampling them outside that range (for
+          // example, while they are waiting to be removed) we currently just
+          // assume that we should fill.
+          timing.mFill = dom::FillMode::Both;
+          timing.mFunction =
+            AnimationUtils::TimingFunctionToComputedTimingFunction(
+              animation.easingFunction());
 
-    uint32_t segmentIndex = 0;
-    size_t segmentSize = animation.segments().Length();
-    AnimationSegment* segment = animation.segments().Elements();
-    while (segment->endPortion() < computedTiming.mProgress.Value() &&
-           segmentIndex < segmentSize - 1) {
-      ++segment;
-      ++segmentIndex;
-    }
+          ComputedTiming computedTiming =
+            dom::KeyframeEffectReadOnly::GetComputedTimingAt(
+              Nullable<TimeDuration>(elapsedDuration), timing);
+
+          MOZ_ASSERT(!computedTiming.mProgress.IsNull(),
+                     "iteration progress should not be null");
 
-    double positionInSegment =
-      (computedTiming.mProgress.Value() - segment->startPortion()) /
-      (segment->endPortion() - segment->startPortion());
+          uint32_t segmentIndex = 0;
+          size_t segmentSize = animation.segments().Length();
+          AnimationSegment* segment = animation.segments().Elements();
+          while (segment->endPortion() < computedTiming.mProgress.Value() &&
+                 segmentIndex < segmentSize - 1) {
+            ++segment;
+            ++segmentIndex;
+          }
 
-    double portion =
-      ComputedTimingFunction::GetPortion(animData.mFunctions[segmentIndex],
-                                         positionInSegment,
-                                         computedTiming.mBeforeFlag);
+          double positionInSegment =
+            (computedTiming.mProgress.Value() - segment->startPortion()) /
+            (segment->endPortion() - segment->startPortion());
+
+          double portion =
+            ComputedTimingFunction::GetPortion(animData.mFunctions[segmentIndex],
+                                               positionInSegment,
+                                           computedTiming.mBeforeFlag);
 
-    // interpolate the property
-    Animatable interpolatedValue;
-    SampleValue(portion, animation, animData.mStartValues[segmentIndex],
-                animData.mEndValues[segmentIndex], &interpolatedValue, aLayer);
-    LayerComposite* layerComposite = aLayer->AsLayerComposite();
-    switch (animation.property()) {
-    case eCSSProperty_opacity:
-    {
-      layerComposite->SetShadowOpacity(interpolatedValue.get_float());
-      break;
-    }
-    case eCSSProperty_transform:
-    {
-      Matrix4x4 matrix = interpolatedValue.get_ArrayOfTransformFunction()[0].get_TransformMatrix().value();
-      if (ContainerLayer* c = aLayer->AsContainerLayer()) {
-        matrix.PostScale(c->GetInheritedXScale(), c->GetInheritedYScale(), 1);
-      }
-      layerComposite->SetShadowBaseTransform(matrix);
-      layerComposite->SetShadowTransformSetByAnimation(true);
-      break;
-    }
-    default:
-      NS_WARNING("Unhandled animated property");
-    }
-  }
-
-  for (Layer* child = aLayer->GetFirstChild(); child;
-       child = child->GetNextSibling()) {
-    activeAnimations |= SampleAnimations(child, aPoint);
-  }
-
+          // interpolate the property
+          Animatable interpolatedValue;
+          SampleValue(portion, animation, animData.mStartValues[segmentIndex],
+                      animData.mEndValues[segmentIndex], &interpolatedValue, layer);
+          LayerComposite* layerComposite = layer->AsLayerComposite();
+          switch (animation.property()) {
+          case eCSSProperty_opacity:
+          {
+            layerComposite->SetShadowOpacity(interpolatedValue.get_float());
+            break;
+          }
+          case eCSSProperty_transform:
+          {
+            Matrix4x4 matrix = interpolatedValue.get_ArrayOfTransformFunction()[0].get_TransformMatrix().value();
+            if (ContainerLayer* c = layer->AsContainerLayer()) {
+              matrix.PostScale(c->GetInheritedXScale(), c->GetInheritedYScale(), 1);
+            }
+            layerComposite->SetShadowBaseTransform(matrix);
+            layerComposite->SetShadowTransformSetByAnimation(true);
+            break;
+          }
+          default:
+            NS_WARNING("Unhandled animated property");
+          }
+        }
+      });
   return activeAnimations;
 }
 
 static bool
 SampleAPZAnimations(const LayerMetricsWrapper& aLayer, TimeStamp aSampleTime)
 {
   bool activeAnimations = false;
   for (LayerMetricsWrapper child = aLayer.GetFirstChild(); child;
@@ -703,38 +703,38 @@ SampleAPZAnimations(const LayerMetricsWr
 }
 
 void
 AsyncCompositionManager::RecordShadowTransforms(Layer* aLayer)
 {
   MOZ_ASSERT(gfxPrefs::CollectScrollTransforms());
   MOZ_ASSERT(CompositorBridgeParent::IsInCompositorThread());
 
-  for (Layer* child = aLayer->GetFirstChild();
-      child; child = child->GetNextSibling()) {
-      RecordShadowTransforms(child);
-  }
+  ForEachNodePostOrder<ForwardIterator>(
+      aLayer,
+      [this] (Layer* layer)
+      {
+        for (uint32_t i = 0; i < layer->GetScrollMetadataCount(); i++) {
+          AsyncPanZoomController* apzc = layer->GetAsyncPanZoomController(i);
+          if (!apzc) {
+            continue;
+          }
+          gfx::Matrix4x4 shadowTransform = layer->AsLayerComposite()->GetShadowBaseTransform();
+          if (!shadowTransform.Is2D()) {
+            continue;
+          }
 
-  for (uint32_t i = 0; i < aLayer->GetScrollMetadataCount(); i++) {
-    AsyncPanZoomController* apzc = aLayer->GetAsyncPanZoomController(i);
-    if (!apzc) {
-      continue;
-    }
-    gfx::Matrix4x4 shadowTransform = aLayer->AsLayerComposite()->GetShadowBaseTransform();
-    if (!shadowTransform.Is2D()) {
-      continue;
-    }
-
-    Matrix transform = shadowTransform.As2D();
-    if (transform.IsTranslation() && !shadowTransform.IsIdentity()) {
-      Point translation = transform.GetTranslation();
-      mLayerTransformRecorder.RecordTransform(aLayer, translation);
-      return;
-    }
-  }
+          Matrix transform = shadowTransform.As2D();
+          if (transform.IsTranslation() && !shadowTransform.IsIdentity()) {
+            Point translation = transform.GetTranslation();
+            mLayerTransformRecorder.RecordTransform(layer, translation);
+            return;
+          }
+        }
+      });
 }
 
 static AsyncTransformComponentMatrix
 AdjustForClip(const AsyncTransformComponentMatrix& asyncTransform, Layer* aLayer)
 {
   AsyncTransformComponentMatrix result = asyncTransform;
 
   // Container layers start at the origin, but they are clipped to where they
@@ -778,17 +778,17 @@ ExpandRootClipRect(Layer* aLayer, const 
 static void
 MoveScrollbarForLayerMargin(Layer* aRoot, FrameMetrics::ViewID aRootScrollId,
                             const ScreenMargin& aFixedLayerMargins)
 {
   // See bug 1223928 comment 9 - once we can detect the RCD with just the
   // isRootContent flag on the metrics, we can probably move this code into
   // ApplyAsyncTransformToScrollbar rather than having it as a separate
   // adjustment on the layer tree.
-  Layer* scrollbar = BreadthFirstSearch(aRoot,
+  Layer* scrollbar = BreadthFirstSearch<ReverseIterator>(aRoot,
     [aRootScrollId](Layer* aNode) {
       return (aNode->GetScrollbarDirection() == Layer::HORIZONTAL &&
               aNode->GetScrollbarTargetContainerId() == aRootScrollId);
     });
   if (scrollbar) {
     // Shift the horizontal scrollbar down into the new space exposed by the
     // dynamic toolbar hiding. Technically we should also scale the vertical
     // scrollbar a bit to expand into the new space but it's not as noticeable
@@ -806,266 +806,272 @@ MoveScrollbarForLayerMargin(Layer* aRoot
     }
   }
 }
 #endif
 
 bool
 AsyncCompositionManager::ApplyAsyncContentTransformToTree(Layer *aLayer,
                                                           bool* aOutFoundRoot,
-                                                          Maybe<ParentLayerIntRect>& aClipDeferredToParent,
                                                           ClipPartsCache& aClipPartsCache)
 {
-  Maybe<ParentLayerIntRect> clipDeferredFromChildren;
   bool appliedTransform = false;
-  for (Layer* child = aLayer->GetFirstChild();
-      child; child = child->GetNextSibling()) {
-    appliedTransform |=
-      ApplyAsyncContentTransformToTree(child, aOutFoundRoot,
-          clipDeferredFromChildren, aClipPartsCache);
-  }
+  std::stack<Maybe<ParentLayerIntRect>> stackDeferredClips;
 
-  LayerToParentLayerMatrix4x4 oldTransform = aLayer->GetTransformTyped() *
-      AsyncTransformMatrix();
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&stackDeferredClips] (Layer* layer)
+      {
+        stackDeferredClips.push(Maybe<ParentLayerIntRect>());
+      },
+      [this, &aOutFoundRoot, &stackDeferredClips, &appliedTransform, &aClipPartsCache] (Layer* layer)
+      {
+        Maybe<ParentLayerIntRect> clipDeferredFromChildren = stackDeferredClips.top();
+        stackDeferredClips.pop();
+        LayerToParentLayerMatrix4x4 oldTransform = layer->GetTransformTyped() *
+            AsyncTransformMatrix();
 
-  AsyncTransformComponentMatrix combinedAsyncTransform;
-  bool hasAsyncTransform = false;
-  ScreenMargin fixedLayerMargins;
+        AsyncTransformComponentMatrix combinedAsyncTransform;
+        bool hasAsyncTransform = false;
+        ScreenMargin fixedLayerMargins;
 
-  // Each layer has multiple clips:
-  //  - Its local clip, which is fixed to the layer contents, i.e. it moves
-  //    with those async transforms which the layer contents move with.
-  //  - Its scrolled clip, which moves with all async transforms.
-  //  - For each ScrollMetadata on the layer, a scroll clip. This includes
-  //    the composition bounds and any other clips induced by layout. This
-  //    moves with async transforms from ScrollMetadatas above it.
-  // In this function, these clips are combined into two shadow clip parts:
-  //  - The fixed clip, which consists of the local clip only, initially
-  //    transformed by all async transforms.
-  //  - The scrolled clip, which consists of the other clips, transformed by
-  //    the appropriate transforms.
-  // These two parts are kept separate for now, because for fixed layers, we
-  // need to adjust the fixed clip (to cancel out some async transforms).
-  // The parts are kept in a cache which is cleared at the beginning of every
-  // composite.
-  // The final shadow clip for the layer is the intersection of the (possibly
-  // adjusted) fixed clip and the scrolled clip.
-  ClipParts& clipParts = aClipPartsCache[aLayer];
-  clipParts.mFixedClip = aLayer->GetClipRect();
-  clipParts.mScrolledClip = aLayer->GetScrolledClipRect();
+        // Each layer has multiple clips:
+        //  - Its local clip, which is fixed to the layer contents, i.e. it moves
+        //    with those async transforms which the layer contents move with.
+        //  - Its scrolled clip, which moves with all async transforms.
+        //  - For each ScrollMetadata on the layer, a scroll clip. This includes
+        //    the composition bounds and any other clips induced by layout. This
+        //    moves with async transforms from ScrollMetadatas above it.
+        // In this function, these clips are combined into two shadow clip parts:
+        //  - The fixed clip, which consists of the local clip only, initially
+        //    transformed by all async transforms.
+        //  - The scrolled clip, which consists of the other clips, transformed by
+        //    the appropriate transforms.
+        // These two parts are kept separate for now, because for fixed layers, we
+        // need to adjust the fixed clip (to cancel out some async transforms).
+        // The parts are kept in a cache which is cleared at the beginning of every
+        // composite.
+        // The final shadow clip for the layer is the intersection of the (possibly
+        // adjusted) fixed clip and the scrolled clip.
+        ClipParts& clipParts = aClipPartsCache[layer];
+        clipParts.mFixedClip = layer->GetClipRect();
+        clipParts.mScrolledClip = layer->GetScrolledClipRect();
 
-  // If we are a perspective transform ContainerLayer, apply the clip deferred
-  // from our child (if there is any) before we iterate over our frame metrics,
-  // because this clip is subject to all async transforms of this layer.
-  // Since this clip came from the a scroll clip on the child, it becomes part
-  // of our scrolled clip.
-  clipParts.mScrolledClip = IntersectMaybeRects(
-      clipDeferredFromChildren, clipParts.mScrolledClip);
+        // If we are a perspective transform ContainerLayer, apply the clip deferred
+        // from our child (if there is any) before we iterate over our frame metrics,
+        // because this clip is subject to all async transforms of this layer.
+        // Since this clip came from the a scroll clip on the child, it becomes part
+        // of our scrolled clip.
+        clipParts.mScrolledClip = IntersectMaybeRects(
+            clipDeferredFromChildren, clipParts.mScrolledClip);
 
-  // The transform of a mask layer is relative to the masked layer's parent
-  // layer. So whenever we apply an async transform to a layer, we need to
-  // apply that same transform to the layer's own mask layer.
-  // A layer can also have "ancestor" mask layers for any rounded clips from
-  // its ancestor scroll frames. A scroll frame mask layer only needs to be
-  // async transformed for async scrolls of this scroll frame's ancestor
-  // scroll frames, not for async scrolls of this scroll frame itself.
-  // In the loop below, we iterate over scroll frames from inside to outside.
-  // At each iteration, this array contains the layer's ancestor mask layers
-  // of all scroll frames inside the current one.
-  nsTArray<Layer*> ancestorMaskLayers;
+        // The transform of a mask layer is relative to the masked layer's parent
+        // layer. So whenever we apply an async transform to a layer, we need to
+        // apply that same transform to the layer's own mask layer.
+        // A layer can also have "ancestor" mask layers for any rounded clips from
+        // its ancestor scroll frames. A scroll frame mask layer only needs to be
+        // async transformed for async scrolls of this scroll frame's ancestor
+        // scroll frames, not for async scrolls of this scroll frame itself.
+        // In the loop below, we iterate over scroll frames from inside to outside.
+        // At each iteration, this array contains the layer's ancestor mask layers
+        // of all scroll frames inside the current one.
+        nsTArray<Layer*> ancestorMaskLayers;
 
-  // The layer's scrolled clip can have an ancestor mask layer as well,
-  // which is moved by all async scrolls on this layer.
-  if (const Maybe<LayerClip>& scrolledClip = aLayer->GetScrolledClip()) {
-    if (scrolledClip->GetMaskLayerIndex()) {
-      ancestorMaskLayers.AppendElement(
-          aLayer->GetAncestorMaskLayerAt(*scrolledClip->GetMaskLayerIndex()));
-    }
-  }
+        // The layer's scrolled clip can have an ancestor mask layer as well,
+        // which is moved by all async scrolls on this layer.
+        if (const Maybe<LayerClip>& scrolledClip = layer->GetScrolledClip()) {
+          if (scrolledClip->GetMaskLayerIndex()) {
+            ancestorMaskLayers.AppendElement(
+                layer->GetAncestorMaskLayerAt(*scrolledClip->GetMaskLayerIndex()));
+          }
+        }
 
-  for (uint32_t i = 0; i < aLayer->GetScrollMetadataCount(); i++) {
-    AsyncPanZoomController* controller = aLayer->GetAsyncPanZoomController(i);
-    if (!controller) {
-      continue;
-    }
+        for (uint32_t i = 0; i < layer->GetScrollMetadataCount(); i++) {
+          AsyncPanZoomController* controller = layer->GetAsyncPanZoomController(i);
+          if (!controller) {
+            continue;
+          }
 
-    hasAsyncTransform = true;
+          hasAsyncTransform = true;
 
-    AsyncTransform asyncTransformWithoutOverscroll =
-        controller->GetCurrentAsyncTransform(AsyncPanZoomController::RESPECT_FORCE_DISABLE);
-    AsyncTransformComponentMatrix overscrollTransform =
-        controller->GetOverscrollTransform(AsyncPanZoomController::RESPECT_FORCE_DISABLE);
-    AsyncTransformComponentMatrix asyncTransform =
-        AsyncTransformComponentMatrix(asyncTransformWithoutOverscroll)
-      * overscrollTransform;
+          AsyncTransform asyncTransformWithoutOverscroll =
+              controller->GetCurrentAsyncTransform(AsyncPanZoomController::RESPECT_FORCE_DISABLE);
+          AsyncTransformComponentMatrix overscrollTransform =
+              controller->GetOverscrollTransform(AsyncPanZoomController::RESPECT_FORCE_DISABLE);
+          AsyncTransformComponentMatrix asyncTransform =
+              AsyncTransformComponentMatrix(asyncTransformWithoutOverscroll)
+            * overscrollTransform;
 
-    if (!aLayer->IsScrollInfoLayer()) {
-      controller->MarkAsyncTransformAppliedToContent();
-    }
+          if (!layer->IsScrollInfoLayer()) {
+            controller->MarkAsyncTransformAppliedToContent();
+          }
 
-    const ScrollMetadata& scrollMetadata = aLayer->GetScrollMetadata(i);
-    const FrameMetrics& metrics = scrollMetadata.GetMetrics();
+          const ScrollMetadata& scrollMetadata = layer->GetScrollMetadata(i);
+          const FrameMetrics& metrics = scrollMetadata.GetMetrics();
 
 #if defined(MOZ_ANDROID_APZ)
-    // If we find a metrics which is the root content doc, use that. If not, use
-    // the root layer. Since this function recurses on children first we should
-    // only end up using the root layer if the entire tree was devoid of a
-    // root content metrics. This is a temporary solution; in the long term we
-    // should not need the root content metrics at all. See bug 1201529 comment
-    // 6 for details.
-    if (!(*aOutFoundRoot)) {
-      *aOutFoundRoot = metrics.IsRootContent() ||       /* RCD */
-            (aLayer->GetParent() == nullptr &&          /* rootmost metrics */
-             i + 1 >= aLayer->GetScrollMetadataCount());
-      if (*aOutFoundRoot) {
-        mRootScrollableId = metrics.GetScrollId();
-        CSSToLayerScale geckoZoom = metrics.LayersPixelsPerCSSPixel().ToScaleFactor();
-        if (mIsFirstPaint) {
-          LayerIntPoint scrollOffsetLayerPixels = RoundedToInt(metrics.GetScrollOffset() * geckoZoom);
-          mContentRect = metrics.GetScrollableRect();
-          SetFirstPaintViewport(scrollOffsetLayerPixels,
-                                geckoZoom,
-                                mContentRect);
-        } else {
-          ParentLayerPoint scrollOffset = controller->GetCurrentAsyncScrollOffset(
-              AsyncPanZoomController::RESPECT_FORCE_DISABLE);
-          // Compute the painted displayport in document-relative CSS pixels.
-          CSSRect displayPort(metrics.GetCriticalDisplayPort().IsEmpty() ?
-              metrics.GetDisplayPort() :
-              metrics.GetCriticalDisplayPort());
-          displayPort += metrics.GetScrollOffset();
-          SyncFrameMetrics(scrollOffset,
-              geckoZoom * asyncTransformWithoutOverscroll.mScale,
-              metrics.GetScrollableRect(), displayPort, geckoZoom, mLayersUpdated,
-              mPaintSyncId, fixedLayerMargins);
-          mFixedLayerMargins = fixedLayerMargins;
-          mLayersUpdated = false;
-        }
-        mIsFirstPaint = false;
-        mPaintSyncId = 0;
-      }
-    }
+          // If we find a metrics which is the root content doc, use that. If not, use
+          // the root layer. Since this function recurses on children first we should
+          // only end up using the root layer if the entire tree was devoid of a
+          // root content metrics. This is a temporary solution; in the long term we
+          // should not need the root content metrics at all. See bug 1201529 comment
+          // 6 for details.
+          if (!(*aOutFoundRoot)) {
+            *aOutFoundRoot = metrics.IsRootContent() ||       /* RCD */
+                  (layer->GetParent() == nullptr &&          /* rootmost metrics */
+                   i + 1 >= layer->GetScrollMetadataCount());
+            if (*aOutFoundRoot) {
+              mRootScrollableId = metrics.GetScrollId();
+              CSSToLayerScale geckoZoom = metrics.LayersPixelsPerCSSPixel().ToScaleFactor();
+              if (mIsFirstPaint) {
+                LayerIntPoint scrollOffsetLayerPixels = RoundedToInt(metrics.GetScrollOffset() * geckoZoom);
+                mContentRect = metrics.GetScrollableRect();
+                SetFirstPaintViewport(scrollOffsetLayerPixels,
+                                      geckoZoom,
+                                      mContentRect);
+              } else {
+                ParentLayerPoint scrollOffset = controller->GetCurrentAsyncScrollOffset(
+                    AsyncPanZoomController::RESPECT_FORCE_DISABLE);
+                // Compute the painted displayport in document-relative CSS pixels.
+                CSSRect displayPort(metrics.GetCriticalDisplayPort().IsEmpty() ?
+                    metrics.GetDisplayPort() :
+                    metrics.GetCriticalDisplayPort());
+                displayPort += metrics.GetScrollOffset();
+                SyncFrameMetrics(scrollOffset,
+                    geckoZoom * asyncTransformWithoutOverscroll.mScale,
+                    metrics.GetScrollableRect(), displayPort, geckoZoom, mLayersUpdated,
+                    mPaintSyncId, fixedLayerMargins);
+                mFixedLayerMargins = fixedLayerMargins;
+                mLayersUpdated = false;
+              }
+              mIsFirstPaint = false;
+              mPaintSyncId = 0;
+            }
+          }
 #else
-    // Non-Android platforms still care about this flag being cleared after
-    // the first call to TransformShadowTree().
-    mIsFirstPaint = false;
+          // Non-Android platforms still care about this flag being cleared after
+          // the first call to TransformShadowTree().
+          mIsFirstPaint = false;
 #endif
 
-    // Transform the current local clips by this APZC's async transform. If we're
-    // using containerful scrolling, then the clip is not part of the scrolled
-    // frame and should not be transformed.
-    if (!scrollMetadata.UsesContainerScrolling()) {
-      MOZ_ASSERT(asyncTransform.Is2D());
-      if (clipParts.mFixedClip) {
-        clipParts.mFixedClip = Some(TransformBy(asyncTransform, *clipParts.mFixedClip));
-      }
-      if (clipParts.mScrolledClip) {
-        clipParts.mScrolledClip = Some(TransformBy(asyncTransform, *clipParts.mScrolledClip));
-      }
-    }
-    // Note: we don't set the layer's shadow clip rect property yet;
-    // AlignFixedAndStickyLayers will use the clip parts from the clip parts
-    // cache.
+          // Transform the current local clips by this APZC's async transform. If we're
+          // using containerful scrolling, then the clip is not part of the scrolled
+          // frame and should not be transformed.
+          if (!scrollMetadata.UsesContainerScrolling()) {
+            MOZ_ASSERT(asyncTransform.Is2D());
+            if (clipParts.mFixedClip) {
+              clipParts.mFixedClip = Some(TransformBy(asyncTransform, *clipParts.mFixedClip));
+            }
+            if (clipParts.mScrolledClip) {
+              clipParts.mScrolledClip = Some(TransformBy(asyncTransform, *clipParts.mScrolledClip));
+            }
+          }
+          // Note: we don't set the layer's shadow clip rect property yet;
+          // AlignFixedAndStickyLayers will use the clip parts from the clip parts
+          // cache.
 
-    combinedAsyncTransform *= asyncTransform;
+          combinedAsyncTransform *= asyncTransform;
 
-    // For the purpose of aligning fixed and sticky layers, we disregard
-    // the overscroll transform as well as any OMTA transform when computing the
-    // 'aCurrentTransformForRoot' parameter. This ensures that the overscroll
-    // and OMTA transforms are not unapplied, and therefore that the visual
-    // effects apply to fixed and sticky layers. We do this by using
-    // GetTransform() as the base transform rather than GetLocalTransform(),
-    // which would include those factors.
-    LayerToParentLayerMatrix4x4 transformWithoutOverscrollOrOmta =
-        aLayer->GetTransformTyped()
-      * CompleteAsyncTransform(
-          AdjustForClip(asyncTransformWithoutOverscroll, aLayer));
+          // For the purpose of aligning fixed and sticky layers, we disregard
+          // the overscroll transform as well as any OMTA transform when computing the
+          // 'aCurrentTransformForRoot' parameter. This ensures that the overscroll
+          // and OMTA transforms are not unapplied, and therefore that the visual
+          // effects apply to fixed and sticky layers. We do this by using
+          // GetTransform() as the base transform rather than GetLocalTransform(),
+          // which would include those factors.
+          LayerToParentLayerMatrix4x4 transformWithoutOverscrollOrOmta =
+              layer->GetTransformTyped()
+            * CompleteAsyncTransform(
+                AdjustForClip(asyncTransformWithoutOverscroll, layer));
 
-    // Since fixed/sticky layers are relative to their nearest scrolling ancestor,
-    // we use the ViewID from the bottommost scrollable metrics here.
-    AlignFixedAndStickyLayers(aLayer, aLayer, metrics.GetScrollId(), oldTransform,
-                              transformWithoutOverscrollOrOmta, fixedLayerMargins,
-                              &aClipPartsCache);
+          // Since fixed/sticky layers are relative to their nearest scrolling ancestor,
+          // we use the ViewID from the bottommost scrollable metrics here.
+          AlignFixedAndStickyLayers(layer, metrics.GetScrollId(), oldTransform,
+                                    transformWithoutOverscrollOrOmta, fixedLayerMargins,
+                                    &aClipPartsCache);
 
-    // Combine the scrolled portion of the local clip with the ancestor
-    // scroll clip. This is not included in the async transform above, since
-    // the ancestor clip should not move with this APZC.
-    if (scrollMetadata.HasScrollClip()) {
-      ParentLayerIntRect clip = scrollMetadata.ScrollClip().GetClipRect();
-      if (aLayer->GetParent() && aLayer->GetParent()->GetTransformIsPerspective()) {
-        // If our parent layer has a perspective transform, we want to apply
-        // our scroll clip to it instead of to this layer (see bug 1168263).
-        // A layer with a perspective transform shouldn't have multiple
-        // children with FrameMetrics, nor a child with multiple FrameMetrics.
-        // (A child with multiple FrameMetrics would mean that there's *another*
-        // scrollable element between the one with the CSS perspective and the
-        // transformed element. But you'd have to use preserve-3d on the inner
-        // scrollable element in order to have the perspective apply to the
-        // transformed child, and preserve-3d is not supported on scrollable
-        // elements, so this case can't occur.)
-        MOZ_ASSERT(!aClipDeferredToParent);
-        aClipDeferredToParent = Some(clip);
-      } else {
-        clipParts.mScrolledClip = IntersectMaybeRects(Some(clip), clipParts.mScrolledClip);
-      }
-    }
+          // Combine the local clip with the ancestor scrollframe clip. This is not
+          // included in the async transform above, since the ancestor clip should not
+          // move with this APZC.
+          if (scrollMetadata.HasScrollClip()) {
+            ParentLayerIntRect clip = scrollMetadata.ScrollClip().GetClipRect();
+            if (layer->GetParent() && layer->GetParent()->GetTransformIsPerspective()) {
+              // If our parent layer has a perspective transform, we want to apply
+              // our scroll clip to it instead of to this layer (see bug 1168263).
+              // A layer with a perspective transform shouldn't have multiple
+              // children with FrameMetrics, nor a child with multiple FrameMetrics.
+              // (A child with multiple FrameMetrics would mean that there's *another*
+              // scrollable element between the one with the CSS perspective and the
+              // transformed element. But you'd have to use preserve-3d on the inner
+              // scrollable element in order to have the perspective apply to the
+              // transformed child, and preserve-3d is not supported on scrollable
+              // elements, so this case can't occur.)
+              MOZ_ASSERT(!stackDeferredClips.top());
+              stackDeferredClips.top().emplace(clip);
+            } else {
+              clipParts.mScrolledClip = IntersectMaybeRects(Some(clip),
+                  clipParts.mScrolledClip);
+            }
+          }
 
-    // Do the same for the ancestor mask layers: ancestorMaskLayers contains
-    // the ancestor mask layers for scroll frames *inside* the current scroll
-    // frame, so these are the ones we need to shift by our async transform.
-    for (Layer* ancestorMaskLayer : ancestorMaskLayers) {
-      SetShadowTransform(ancestorMaskLayer,
-          ancestorMaskLayer->GetLocalTransformTyped() * asyncTransform);
-    }
+          // Do the same for the ancestor mask layers: ancestorMaskLayers contains
+          // the ancestor mask layers for scroll frames *inside* the current scroll
+          // frame, so these are the ones we need to shift by our async transform.
+          for (Layer* ancestorMaskLayer : ancestorMaskLayers) {
+            SetShadowTransform(ancestorMaskLayer,
+                ancestorMaskLayer->GetLocalTransformTyped() * asyncTransform);
+          }
 
-    // Append the ancestor mask layer for this scroll frame to ancestorMaskLayers.
-    if (scrollMetadata.HasScrollClip()) {
-      const LayerClip& scrollClip = scrollMetadata.ScrollClip();
-      if (scrollClip.GetMaskLayerIndex()) {
-        size_t maskLayerIndex = scrollClip.GetMaskLayerIndex().value();
-        Layer* ancestorMaskLayer = aLayer->GetAncestorMaskLayerAt(maskLayerIndex);
-        ancestorMaskLayers.AppendElement(ancestorMaskLayer);
-      }
-    }
-  }
+          // Append the ancestor mask layer for this scroll frame to ancestorMaskLayers.
+          if (scrollMetadata.HasScrollClip()) {
+            const LayerClip& scrollClip = scrollMetadata.ScrollClip();
+            if (scrollClip.GetMaskLayerIndex()) {
+              size_t maskLayerIndex = scrollClip.GetMaskLayerIndex().value();
+              Layer* ancestorMaskLayer = layer->GetAncestorMaskLayerAt(maskLayerIndex);
+              ancestorMaskLayers.AppendElement(ancestorMaskLayer);
+            }
+          }
+        }
 
-  bool clipChanged = (hasAsyncTransform || clipDeferredFromChildren ||
-                      aLayer->GetScrolledClipRect());
-  if (clipChanged) {
-    // Intersect the two clip parts and apply them to the layer.
-    // During ApplyAsyncContentTransformTree on an ancestor layer,
-    // AlignFixedAndStickyLayers may overwrite this with a new clip it
-    // computes from the clip parts, but if that doesn't happen, this
-    // is the layer's final clip rect.
-    aLayer->AsLayerComposite()->SetShadowClipRect(clipParts.Intersect());
-  }
+        bool clipChanged = (hasAsyncTransform || clipDeferredFromChildren ||
+                            layer->GetScrolledClipRect());
+        if (clipChanged) {
+          // Intersect the two clip parts and apply them to the layer.
+          // During ApplyAsyncContentTransformTree on an ancestor layer,
+          // AlignFixedAndStickyLayers may overwrite this with a new clip it
+          // computes from the clip parts, but if that doesn't happen, this
+          // is the layer's final clip rect.
+          layer->AsLayerComposite()->SetShadowClipRect(clipParts.Intersect());
+        }
 
-  if (hasAsyncTransform) {
-    // Apply the APZ transform on top of GetLocalTransform() here (rather than
-    // GetTransform()) in case the OMTA code in SampleAnimations already set a
-    // shadow transform; in that case we want to apply ours on top of that one
-    // rather than clobber it.
-    SetShadowTransform(aLayer,
-        aLayer->GetLocalTransformTyped()
-      * AdjustForClip(combinedAsyncTransform, aLayer));
+        if (hasAsyncTransform) {
+          // Apply the APZ transform on top of GetLocalTransform() here (rather than
+          // GetTransform()) in case the OMTA code in SampleAnimations already set a
+          // shadow transform; in that case we want to apply ours on top of that one
+          // rather than clobber it.
+          SetShadowTransform(layer,
+              layer->GetLocalTransformTyped()
+            * AdjustForClip(combinedAsyncTransform, layer));
 
-    // Do the same for the layer's own mask layer, if it has one.
-    if (Layer* maskLayer = aLayer->GetMaskLayer()) {
-      SetShadowTransform(maskLayer,
-          maskLayer->GetLocalTransformTyped() * combinedAsyncTransform);
-    }
+          // Do the same for the layer's own mask layer, if it has one.
+          if (Layer* maskLayer = layer->GetMaskLayer()) {
+            SetShadowTransform(maskLayer,
+                maskLayer->GetLocalTransformTyped() * combinedAsyncTransform);
+          }
 
-    appliedTransform = true;
-  }
+          appliedTransform = true;
+        }
+
+        ExpandRootClipRect(layer, fixedLayerMargins);
 
-  ExpandRootClipRect(aLayer, fixedLayerMargins);
+        if (layer->GetScrollbarDirection() != Layer::NONE) {
+          ApplyAsyncTransformToScrollbar(layer);
+        }
+      });
 
-  if (aLayer->GetScrollbarDirection() != Layer::NONE) {
-    ApplyAsyncTransformToScrollbar(aLayer);
-  }
   return appliedTransform;
 }
 
 static bool
 LayerIsScrollbarTarget(const LayerMetricsWrapper& aTarget, Layer* aScrollbar)
 {
   AsyncPanZoomController* apzc = aTarget.GetApzc();
   if (!apzc) {
@@ -1416,17 +1422,17 @@ AsyncCompositionManager::TransformScroll
   if (mContentRect.height * userZoom.scale < metrics.GetCompositionBounds().height) {
     underZoomScale.height = (mContentRect.height * userZoom.scale) /
       metrics.GetCompositionBounds().height;
   }
   oldTransform.PreScale(underZoomScale.width, underZoomScale.height, 1);
 
   // Make sure fixed position layers don't move away from their anchor points
   // when we're asynchronously panning or zooming
-  AlignFixedAndStickyLayers(aLayer, aLayer, metrics.GetScrollId(), oldTransform,
+  AlignFixedAndStickyLayers(aLayer, metrics.GetScrollId(), oldTransform,
                             aLayer->GetLocalTransformTyped(),
                             fixedLayerMargins, nullptr);
 
   ExpandRootClipRect(aLayer, fixedLayerMargins);
 }
 
 void
 AsyncCompositionManager::GetFrameUniformity(FrameUniformityData* aOutData)
@@ -1466,19 +1472,17 @@ AsyncCompositionManager::TransformShadow
     // an async pan zoom controller (which means that it is rendered
     // async using Gecko). If this fails, fall back to transforming the
     // primary scrollable layer.  "Failing" here means that we don't
     // find a frame that is async scrollable.  Note that the fallback
     // code also includes Fennec which is rendered async.  Fennec uses
     // its own platform-specific async rendering that is done partially
     // in Gecko and partially in Java.
     bool foundRoot = false;
-    Maybe<ParentLayerIntRect> clipDeferredFromChildren;
-    if (ApplyAsyncContentTransformToTree(root, &foundRoot, clipDeferredFromChildren,
-                                         clipPartsCache)) {
+    if (ApplyAsyncContentTransformToTree(root, &foundRoot, clipPartsCache)) {
 #if defined(MOZ_ANDROID_APZ)
       MOZ_ASSERT(foundRoot);
       if (foundRoot && mFixedLayerMargins != ScreenMargin()) {
         MoveScrollbarForLayerMargin(root, mRootScrollableId, mFixedLayerMargins);
       }
 #endif
     } else {
       AutoTArray<Layer*,1> scrollableLayers;
--- a/gfx/layers/composite/AsyncCompositionManager.h
+++ b/gfx/layers/composite/AsyncCompositionManager.h
@@ -134,23 +134,21 @@ public:
 
   typedef std::map<Layer*, ClipParts> ClipPartsCache;
 private:
   void TransformScrollableLayer(Layer* aLayer);
   // Return true if an AsyncPanZoomController content transform was
   // applied for |aLayer|. |*aOutFoundRoot| is set to true on Android only, if
   // one of the metrics on one of the layers was determined to be the "root"
   // and its state was synced to the Java front-end. |aOutFoundRoot| must be
-  // non-null. As the function recurses over the layer tree, a layer may
-  // populate |aClipDeferredToParent| a clip rect it wants to set on its parent.
+  // non-null.
   // |aClipPartsCache| is used to cache components of clips on descendant
   // layers that may be needed while processing ancestor layers.
   bool ApplyAsyncContentTransformToTree(Layer* aLayer,
                                         bool* aOutFoundRoot,
-                                        Maybe<ParentLayerIntRect>& aClipDeferredToParent,
                                         ClipPartsCache& aClipPartsCache);
   /**
    * Update the shadow transform for aLayer assuming that is a scrollbar,
    * so that it stays in sync with the content that is being scrolled by APZ.
    */
   void ApplyAsyncTransformToScrollbar(Layer* aLayer);
 
   void SetFirstPaintViewport(const LayerIntPoint& aOffset,
@@ -189,17 +187,17 @@ private:
    * zooming.
    * aTransformAffectsLayerClip indicates whether the transform on
    * aTransformedSubtreeRoot affects aLayer's clip rects, so we know
    * whether we need to perform a corresponding unadjustment to keep
    * the clip rect fixed.
    * aClipPartsCache optionally maps layers to separate fixed and scrolled
    * clips, so we can only adjust the fixed portion.
    */
-  void AlignFixedAndStickyLayers(Layer* aLayer, Layer* aTransformedSubtreeRoot,
+  void AlignFixedAndStickyLayers(Layer* aTransformedSubtreeRoot,
                                  FrameMetrics::ViewID aTransformScrollId,
                                  const LayerToParentLayerMatrix4x4& aPreviousTransformForRoot,
                                  const LayerToParentLayerMatrix4x4& aCurrentTransformForRoot,
                                  const ScreenMargin& aFixedLayerMargins,
                                  ClipPartsCache* aClipPartsCache);
 
   /**
    * DRAWING PHASE ONLY
--- a/gfx/layers/composite/LayerManagerComposite.cpp
+++ b/gfx/layers/composite/LayerManagerComposite.cpp
@@ -64,16 +64,17 @@
 #endif
 #ifdef MOZ_WIDGET_GONK
 #include "nsScreenManagerGonk.h"
 #include "nsWindow.h"
 #endif
 #include "GeckoProfiler.h"
 #include "TextRenderer.h"               // for TextRenderer
 #include "mozilla/layers/CompositorBridgeParent.h"
+#include "TreeTraversal.h"              // for ForEachNode
 
 class gfxContext;
 
 namespace mozilla {
 namespace layers {
 
 class ImageLayer;
 
@@ -83,21 +84,22 @@ using namespace mozilla::gl;
 static LayerComposite*
 ToLayerComposite(Layer* aLayer)
 {
   return static_cast<LayerComposite*>(aLayer->ImplData());
 }
 
 static void ClearSubtree(Layer* aLayer)
 {
-  ToLayerComposite(aLayer)->CleanupResources();
-  for (Layer* child = aLayer->GetFirstChild(); child;
-       child = child->GetNextSibling()) {
-    ClearSubtree(child);
-  }
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [] (Layer* layer)
+      {
+        ToLayerComposite(layer)->CleanupResources();
+      });
 }
 
 void
 LayerManagerComposite::ClearCachedResources(Layer* aSubtree)
 {
   MOZ_ASSERT(!aSubtree || aSubtree->Manager() == this);
   Layer* subtree = aSubtree ? aSubtree : mRoot.get();
   if (!subtree) {
@@ -787,26 +789,24 @@ LayerManagerComposite::PopGroupForLayerE
   gfx::Rect clipRectF(aClipRect.x, aClipRect.y, aClipRect.width, aClipRect.height);
   mCompositor->DrawQuad(Rect(Point(0, 0), Size(mTwoPassTmpTarget->GetSize())), clipRectF, effectChain, 1.,
                         Matrix4x4());
 }
 
 // Used to clear the 'mLayerComposited' flag at the beginning of each Render().
 static void
 ClearLayerFlags(Layer* aLayer) {
-  if (!aLayer) {
-    return;
-  }
-  if (aLayer->AsLayerComposite()) {
-    aLayer->AsLayerComposite()->SetLayerComposited(false);
-  }
-  for (Layer* child = aLayer->GetFirstChild(); child;
-       child = child->GetNextSibling()) {
-    ClearLayerFlags(child);
-  }
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [] (Layer* layer)
+      {
+        if (layer->AsLayerComposite()) {
+          layer->AsLayerComposite()->SetLayerComposited(false);
+        }
+      });
 }
 
 void
 LayerManagerComposite::Render(const nsIntRegion& aInvalidRegion, const nsIntRegion& aOpaqueRegion)
 {
   PROFILER_LABEL("LayerManagerComposite", "Render",
     js::ProfileEntry::Category::GRAPHICS);
 
@@ -1203,73 +1203,74 @@ SubtractTransformedRegion(nsIntRegion& a
 }
 
 /* static */ void
 LayerManagerComposite::ComputeRenderIntegrityInternal(Layer* aLayer,
                                                       nsIntRegion& aScreenRegion,
                                                       nsIntRegion& aLowPrecisionScreenRegion,
                                                       const Matrix4x4& aTransform)
 {
-  if (aLayer->GetOpacity() <= 0.f ||
-      (aScreenRegion.IsEmpty() && aLowPrecisionScreenRegion.IsEmpty())) {
-    return;
-  }
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [&aScreenRegion, &aLowPrecisionScreenRegion, &aTransform] (Layer* layer)
+      {
+        if (layer->GetOpacity() <= 0.f ||
+            (aScreenRegion.IsEmpty() && aLowPrecisionScreenRegion.IsEmpty())) {
+          return TraversalFlag::Skip;
+        }
 
-  // If the layer's a container, recurse into all of its children
-  ContainerLayer* container = aLayer->AsContainerLayer();
-  if (container) {
-    // Accumulate the transform of intermediate surfaces
-    Matrix4x4 transform = aTransform;
-    if (container->UseIntermediateSurface()) {
-      transform = aLayer->GetEffectiveTransform();
-      transform = aTransform * transform;
-    }
-    for (Layer* child = aLayer->GetFirstChild(); child;
-         child = child->GetNextSibling()) {
-      ComputeRenderIntegrityInternal(child, aScreenRegion, aLowPrecisionScreenRegion, transform);
-    }
-    return;
-  }
-
-  // Only painted layers can be incomplete
-  PaintedLayer* paintedLayer = aLayer->AsPaintedLayer();
-  if (!paintedLayer) {
-    return;
-  }
+        // If the layer's a container, recurse into all of its children
+        ContainerLayer* container = layer->AsContainerLayer();
+        if (container) {
+          // Accumulate the transform of intermediate surfaces
+          Matrix4x4 transform = aTransform;
+          if (container->UseIntermediateSurface()) {
+            transform = layer->GetEffectiveTransform();
+            transform = aTransform * transform;
+          }
+          return TraversalFlag::Continue;
+        }
 
-  // See if there's any incomplete rendering
-  nsIntRegion incompleteRegion = aLayer->GetLocalVisibleRegion().ToUnknownRegion();
-  incompleteRegion.Sub(incompleteRegion, paintedLayer->GetValidRegion());
+        // Only painted layers can be incomplete
+        PaintedLayer* paintedLayer = layer->AsPaintedLayer();
+        if (!paintedLayer || !container) {
+          return TraversalFlag::Skip;
+        }
+        // See if there's any incomplete rendering
+        nsIntRegion incompleteRegion = layer->GetLocalVisibleRegion().ToUnknownRegion();
+        incompleteRegion.Sub(incompleteRegion, paintedLayer->GetValidRegion());
 
-  if (!incompleteRegion.IsEmpty()) {
-    // Calculate the transform to get between screen and layer space
-    Matrix4x4 transformToScreen = aLayer->GetEffectiveTransform();
-    transformToScreen = aTransform * transformToScreen;
+        if (!incompleteRegion.IsEmpty()) {
+          // Calculate the transform to get between screen and layer space
+          Matrix4x4 transformToScreen = layer->GetEffectiveTransform();
+          transformToScreen = aTransform * transformToScreen;
 
-    SubtractTransformedRegion(aScreenRegion, incompleteRegion, transformToScreen);
+          SubtractTransformedRegion(aScreenRegion, incompleteRegion, transformToScreen);
 
-    // See if there's any incomplete low-precision rendering
-    TiledContentHost* composer = nullptr;
-    LayerComposite* shadow = aLayer->AsLayerComposite();
-    if (shadow) {
-      composer = shadow->GetCompositableHost()->AsTiledContentHost();
-      if (composer) {
-        incompleteRegion.Sub(incompleteRegion, composer->GetValidLowPrecisionRegion());
-        if (!incompleteRegion.IsEmpty()) {
-          SubtractTransformedRegion(aLowPrecisionScreenRegion, incompleteRegion, transformToScreen);
+          // See if there's any incomplete low-precision rendering
+          TiledContentHost* composer = nullptr;
+          LayerComposite* shadow = layer->AsLayerComposite();
+          if (shadow) {
+            composer = shadow->GetCompositableHost()->AsTiledContentHost();
+            if (composer) {
+              incompleteRegion.Sub(incompleteRegion, composer->GetValidLowPrecisionRegion());
+              if (!incompleteRegion.IsEmpty()) {
+                SubtractTransformedRegion(aLowPrecisionScreenRegion, incompleteRegion, transformToScreen);
+              }
+            }
+          }
+
+          // If we can't get a valid low precision region, assume it's the same as
+          // the high precision region.
+          if (!composer) {
+            SubtractTransformedRegion(aLowPrecisionScreenRegion, incompleteRegion, transformToScreen);
+          }
         }
-      }
-    }
-
-    // If we can't get a valid low precision region, assume it's the same as
-    // the high precision region.
-    if (!composer) {
-      SubtractTransformedRegion(aLowPrecisionScreenRegion, incompleteRegion, transformToScreen);
-    }
-  }
+        return TraversalFlag::Skip;
+      });
 }
 
 #ifdef MOZ_WIDGET_ANDROID
 static float
 GetDisplayportCoverage(const CSSRect& aDisplayPort,
                        const Matrix4x4& aTransformToScreen,
                        const IntRect& aScreenRect)
 {
--- a/gfx/layers/ipc/CompositorBridgeParent.cpp
+++ b/gfx/layers/ipc/CompositorBridgeParent.cpp
@@ -12,16 +12,17 @@
 #include "LayerTransactionParent.h"     // for LayerTransactionParent
 #include "RenderTrace.h"                // for RenderTraceLayers
 #include "base/message_loop.h"          // for MessageLoop
 #include "base/process.h"               // for ProcessId
 #include "base/task.h"                  // for CancelableTask, etc
 #include "base/thread.h"                // for Thread
 #include "gfxContext.h"                 // for gfxContext
 #include "gfxPlatform.h"                // for gfxPlatform
+#include "TreeTraversal.h"              // for ForEachNode
 #ifdef MOZ_WIDGET_GTK
 #include "gfxPlatformGtk.h"             // for gfxPlatform
 #endif
 #include "gfxPrefs.h"                   // for gfxPrefs
 #include "mozilla/AutoRestore.h"        // for AutoRestore
 #include "mozilla/ClearOnShutdown.h"    // for ClearOnShutdown
 #include "mozilla/DebugOnly.h"          // for DebugOnly
 #include "mozilla/dom/ContentParent.h"
@@ -1164,36 +1165,37 @@ CompositorBridgeParent::ScheduleComposit
   mCompositorScheduler->ScheduleComposition();
 }
 
 // Go down the composite layer tree, setting properties to match their
 // content-side counterparts.
 /* static */ void
 CompositorBridgeParent::SetShadowProperties(Layer* aLayer)
 {
-  if (Layer* maskLayer = aLayer->GetMaskLayer()) {
-    SetShadowProperties(maskLayer);
-  }
-  for (size_t i = 0; i < aLayer->GetAncestorMaskLayerCount(); i++) {
-    SetShadowProperties(aLayer->GetAncestorMaskLayerAt(i));
-  }
-
-  // FIXME: Bug 717688 -- Do these updates in LayerTransactionParent::RecvUpdate.
-  LayerComposite* layerComposite = aLayer->AsLayerComposite();
-  // Set the layerComposite's base transform to the layer's base transform.
-  layerComposite->SetShadowBaseTransform(aLayer->GetBaseTransform());
-  layerComposite->SetShadowTransformSetByAnimation(false);
-  layerComposite->SetShadowVisibleRegion(aLayer->GetVisibleRegion());
-  layerComposite->SetShadowClipRect(aLayer->GetClipRect());
-  layerComposite->SetShadowOpacity(aLayer->GetOpacity());
-
-  for (Layer* child = aLayer->GetFirstChild();
-      child; child = child->GetNextSibling()) {
-    SetShadowProperties(child);
-  }
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [] (Layer *layer)
+      {
+        if (Layer* maskLayer = layer->GetMaskLayer()) {
+          SetShadowProperties(maskLayer);
+        }
+        for (size_t i = 0; i < layer->GetAncestorMaskLayerCount(); i++) {
+          SetShadowProperties(layer->GetAncestorMaskLayerAt(i));
+        }
+
+        // FIXME: Bug 717688 -- Do these updates in LayerTransactionParent::RecvUpdate.
+        LayerComposite* layerComposite = layer->AsLayerComposite();
+        // Set the layerComposite's base transform to the layer's base transform.
+        layerComposite->SetShadowBaseTransform(layer->GetBaseTransform());
+        layerComposite->SetShadowTransformSetByAnimation(false);
+        layerComposite->SetShadowVisibleRegion(layer->GetVisibleRegion());
+        layerComposite->SetShadowClipRect(layer->GetClipRect());
+        layerComposite->SetShadowOpacity(layer->GetOpacity());
+      }
+    );
 }
 
 void
 CompositorBridgeParent::CompositeToTarget(DrawTarget* aTarget, const gfx::IntRect* aRect)
 {
   profiler_tracing("Paint", "Composite", TRACING_INTERVAL_START);
   PROFILER_LABEL("CompositorBridgeParent", "Composite",
     js::ProfileEntry::Category::GRAPHICS);
--- a/gfx/layers/ipc/LayerTransactionParent.cpp
+++ b/gfx/layers/ipc/LayerTransactionParent.cpp
@@ -35,16 +35,17 @@
 #include "nsCoord.h"                    // for NSAppUnitsToFloatPixels
 #include "nsDebug.h"                    // for NS_RUNTIMEABORT
 #include "nsDeviceContext.h"            // for AppUnitsPerCSSPixel
 #include "nsISupportsImpl.h"            // for Layer::Release, etc
 #include "nsLayoutUtils.h"              // for nsLayoutUtils
 #include "nsMathUtils.h"                // for NS_round
 #include "nsPoint.h"                    // for nsPoint
 #include "nsTArray.h"                   // for nsTArray, nsTArray_Impl, etc
+#include "TreeTraversal.h"              // for ForEachNode
 #include "GeckoProfiler.h"
 #include "mozilla/layers/TextureHost.h"
 #include "mozilla/layers/AsyncCompositionManager.h"
 
 typedef std::vector<mozilla::layers::EditReply> EditReplyVector;
 
 using mozilla::layout::RenderFrameParent;
 
@@ -792,31 +793,30 @@ LayerTransactionParent::RecvGetAnimation
 
   *aTransform = transform;
   return true;
 }
 
 static AsyncPanZoomController*
 GetAPZCForViewID(Layer* aLayer, FrameMetrics::ViewID aScrollID)
 {
-  for (uint32_t i = 0; i < aLayer->GetScrollMetadataCount(); i++) {
-    if (aLayer->GetFrameMetrics(i).GetScrollId() == aScrollID) {
-      return aLayer->GetAsyncPanZoomController(i);
-    }
-  }
-  ContainerLayer* container = aLayer->AsContainerLayer();
-  if (container) {
-    for (Layer* l = container->GetFirstChild(); l; l = l->GetNextSibling()) {
-      AsyncPanZoomController* c = GetAPZCForViewID(l, aScrollID);
-      if (c) {
-        return c;
-      }
-    }
-  }
-  return nullptr;
+  AsyncPanZoomController* resultApzc = nullptr;
+  ForEachNode<ForwardIterator>(
+      aLayer,
+      [aScrollID, &resultApzc] (Layer* layer)
+      {
+        for (uint32_t i = 0; i < layer->GetScrollMetadataCount(); i++) {
+          if (layer->GetFrameMetrics(i).GetScrollId() == aScrollID) {
+            resultApzc = layer->GetAsyncPanZoomController(i);
+            return TraversalFlag::Abort;
+          }
+        }
+        return TraversalFlag::Continue;
+      });
+  return resultApzc;
 }
 
 bool
 LayerTransactionParent::RecvSetAsyncScrollOffset(const FrameMetrics::ViewID& aScrollID,
                                                  const float& aX, const float& aY)
 {
   if (mDestroyed || !layer_manager() || layer_manager()->IsDestroyed()) {
     return false;
--- a/gfx/tests/gtest/TestTreeTraversal.cpp
+++ b/gfx/tests/gtest/TestTreeTraversal.cpp
@@ -5,139 +5,282 @@
 
 using namespace mozilla::layers;
 using namespace mozilla;
 
 enum class SearchNodeType {Needle, Hay};
 enum class ForEachNodeType {Continue, Skip};
 
 template <class T>
-class TestNode {
+class TestNodeBase {
   public:
-    NS_INLINE_DECL_REFCOUNTING(TestNode<T>);
-    explicit TestNode(T aType, int aExpectedTraversalRank = -1);
-    TestNode<T>* GetLastChild();
-    TestNode<T>* GetPrevSibling();
-    void SetPrevSibling(RefPtr<TestNode<T>> aNode);
-    void AddChild(RefPtr<TestNode<T>> aNode);
+    explicit TestNodeBase(T aType, int aExpectedTraversalRank = -1);
     void SetActualTraversalRank(int aRank);
     int GetExpectedTraversalRank();
     int GetActualTraversalRank();
     T GetType();
   private:
-    RefPtr<TestNode<T>> mPreviousNode;
-    RefPtr<TestNode<T>> mLastChildNode;
     int mExpectedTraversalRank;
     int mActualTraversalRank;
     T mType;
-    ~TestNode<T>() {};
+  protected:
+    ~TestNodeBase<T>() {};
+};
+
+template <class T>
+class TestNodeReverse : public TestNodeBase<T> {
+  public:
+    NS_INLINE_DECL_REFCOUNTING(TestNodeReverse<T>);
+    explicit TestNodeReverse(T aType, int aExpectedTraversalRank = -1);
+    void AddChild(RefPtr<TestNodeReverse<T>> aNode);
+    TestNodeReverse<T>* GetLastChild();
+    TestNodeReverse<T>* GetPrevSibling();
+  private:
+    void SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode);
+    void SetLastChild(RefPtr<TestNodeReverse<T>> aNode);
+    RefPtr<TestNodeReverse<T>> mSiblingNode;
+    RefPtr<TestNodeReverse<T>> mLastChildNode;
+    ~TestNodeReverse<T>() {};
 };
 
 template <class T>
-TestNode<T>::TestNode(T aType, int aExpectedTraversalRank) : 
-  mExpectedTraversalRank(aExpectedTraversalRank),
-  mActualTraversalRank(-1),
-  mType(aType)
+class TestNodeForward : public TestNodeBase<T> {
+  public:
+    NS_INLINE_DECL_REFCOUNTING(TestNodeForward<T>);
+    explicit TestNodeForward(T aType, int aExpectedTraversalRank = -1);
+    void AddChild(RefPtr<TestNodeForward<T>> aNode);
+    TestNodeForward<T>* GetFirstChild();
+    TestNodeForward<T>* GetNextSibling();
+  private:
+    void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
+    void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
+    void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
+    RefPtr<TestNodeForward<T>> mSiblingNode = nullptr;
+    RefPtr<TestNodeForward<T>> mFirstChildNode = nullptr;
+    // Track last child to facilitate appending children
+    RefPtr<TestNodeForward<T>> mLastChildNode = nullptr;
+    ~TestNodeForward<T>() {};
+};
+
+template <class T>
+TestNodeReverse<T>::TestNodeReverse(T aType, int aExpectedTraversalRank) :
+  TestNodeBase<T>(aType, aExpectedTraversalRank)
 {
+
 }
 
 template <class T>
-void TestNode<T>::AddChild(RefPtr<TestNode<T>> aNode)
+void TestNodeReverse<T>::SetLastChild(RefPtr<TestNodeReverse<T>> aNode)
 {
-  aNode->SetPrevSibling(mLastChildNode);
   mLastChildNode = aNode;
 }
 
 template <class T>
-void TestNode<T>::SetPrevSibling(RefPtr<TestNode<T>> aNode)
+void TestNodeReverse<T>::AddChild(RefPtr<TestNodeReverse<T>> aNode)
 {
-  mPreviousNode = aNode;
+  aNode->SetPrevSibling(mLastChildNode);
+  SetLastChild(aNode);
 }
 
 template <class T>
-TestNode<T>* TestNode<T>::GetLastChild()
+void TestNodeReverse<T>::SetPrevSibling(RefPtr<TestNodeReverse<T>> aNode)
+{
+  mSiblingNode = aNode;
+}
+
+template <class T>
+TestNodeReverse<T>* TestNodeReverse<T>::GetLastChild()
 {
   return mLastChildNode;
 }
 
 template <class T>
-TestNode<T>* TestNode<T>::GetPrevSibling()
+TestNodeReverse<T>* TestNodeReverse<T>::GetPrevSibling()
+{
+  return mSiblingNode;
+}
+
+template <class T>
+TestNodeForward<T>::TestNodeForward(T aType, int aExpectedTraversalRank) :
+  TestNodeBase<T>(aType, aExpectedTraversalRank)
+{
+
+}
+
+template <class T>
+void TestNodeForward<T>::AddChild(RefPtr<TestNodeForward<T>> aNode)
 {
-  return mPreviousNode;
+  if (mFirstChildNode == nullptr) {
+    SetFirstChild(aNode);
+    SetLastChild(aNode);
+  }
+  else {
+    mLastChildNode->SetNextSibling(aNode);
+    SetLastChild(aNode);
+  }
+}
+
+template <class T>
+void TestNodeForward<T>::SetLastChild(RefPtr<TestNodeForward<T>> aNode)
+{
+  mLastChildNode = aNode;
 }
 
 template <class T>
-int TestNode<T>::GetActualTraversalRank()
+void TestNodeForward<T>::SetFirstChild(RefPtr<TestNodeForward<T>> aNode)
+{
+  mFirstChildNode = aNode;
+}
+
+template <class T>
+void TestNodeForward<T>::SetNextSibling(RefPtr<TestNodeForward<T>> aNode)
+{
+  mSiblingNode = aNode;
+}
+
+template <class T>
+TestNodeForward<T>* TestNodeForward<T>::GetFirstChild()
+{
+  return mFirstChildNode;
+}
+
+template <class T>
+TestNodeForward<T>* TestNodeForward<T>::GetNextSibling()
+{
+  return mSiblingNode;
+}
+
+template <class T>
+TestNodeBase<T>::TestNodeBase(T aType, int aExpectedTraversalRank):
+    mExpectedTraversalRank(aExpectedTraversalRank),
+    mActualTraversalRank(-1),
+    mType(aType)
+{
+}
+
+template <class T>
+int TestNodeBase<T>::GetActualTraversalRank()
 {
   return mActualTraversalRank;
 }
 
 template <class T>
-void TestNode<T>::SetActualTraversalRank(int aRank)
+void TestNodeBase<T>::SetActualTraversalRank(int aRank)
 {
   mActualTraversalRank = aRank;
 }
 
 template <class T>
-int TestNode<T>::GetExpectedTraversalRank()
+int TestNodeBase<T>::GetExpectedTraversalRank()
 {
   return mExpectedTraversalRank;
 }
 
 template <class T>
-T TestNode<T>::GetType()
+T TestNodeBase<T>::GetType()
 {
   return mType;
 }
 
-typedef TestNode<SearchNodeType> SearchTestNode;
-typedef TestNode<ForEachNodeType> ForEachTestNode;
+typedef TestNodeReverse<SearchNodeType> SearchTestNodeReverse;
+typedef TestNodeReverse<ForEachNodeType> ForEachTestNodeReverse;
+typedef TestNodeForward<SearchNodeType> SearchTestNodeForward;
+typedef TestNodeForward<ForEachNodeType> ForEachTestNodeForward;
 
 TEST(TreeTraversal, DepthFirstSearchNull)
 {
-  RefPtr<SearchTestNode> nullNode;
-  RefPtr<SearchTestNode> result = DepthFirstSearch(nullNode.get(),
-      [](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> nullNode;
+  RefPtr<SearchTestNodeReverse> result = DepthFirstSearch<layers::ReverseIterator>(nullNode.get(),
+      [](SearchTestNodeReverse* aNode)
       {
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
 }
 
 TEST(TreeTraversal, DepthFirstSearchValueExists)
 {
   int visitCount = 0;
   size_t expectedNeedleTraversalRank = 7;
-  RefPtr<SearchTestNode> needleNode;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  RefPtr<SearchTestNodeForward> needleNode;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (size_t i = 0; i < 10; i++)
   {
     if (i == expectedNeedleTraversalRank) {
-      needleNode = new SearchTestNode(SearchNodeType::Needle, i);
+      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
       nodeList.push_back(needleNode);
     } else if (i < expectedNeedleTraversalRank) {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
     } else {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
     }
   }
 
-  RefPtr<SearchTestNode> root = nodeList[0];
+  RefPtr<SearchTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[4]);
+  nodeList[1]->AddChild(nodeList[2]);
+  nodeList[1]->AddChild(nodeList[3]);
+  nodeList[4]->AddChild(nodeList[5]);
+  nodeList[4]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+      << "Returned node does not match expected value (something odd happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueExistsReverse)
+{
+  int visitCount = 0;
+  size_t expectedNeedleTraversalRank = 7;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (size_t i = 0; i < 10; i++)
+  {
+    if (i == expectedNeedleTraversalRank) {
+      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+      nodeList.push_back(needleNode);
+    } else if (i < expectedNeedleTraversalRank) {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+    } else {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+    }
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[4]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[1]->AddChild(nodeList[2]);
   nodeList[4]->AddChild(nodeList[6]);
   nodeList[4]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
-  RefPtr<SearchTestNode> foundNode = DepthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
@@ -148,61 +291,101 @@ TEST(TreeTraversal, DepthFirstSearchValu
 
   ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
   ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
       << "Returned node does not match expected value (something odd happened).";
 }
 
 TEST(TreeTraversal, DepthFirstSearchRootIsNeedle)
 {
-  RefPtr<SearchTestNode> root = new SearchTestNode(SearchNodeType::Needle, 0);
-  RefPtr<SearchTestNode> childNode1= new SearchTestNode(SearchNodeType::Hay);
-  RefPtr<SearchTestNode> childNode2 = new SearchTestNode(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
   int visitCount = 0;
-  RefPtr<SearchTestNode> result = DepthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> result = DepthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
   ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
       << "Search starting at needle did not return needle.";
   ASSERT_EQ(childNode1->GetExpectedTraversalRank(),
-      childNode1->GetActualTraversalRank()) 
+      childNode1->GetActualTraversalRank())
       << "Search starting at needle continued past needle.";
   ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
-      childNode2->GetActualTraversalRank()) 
+      childNode2->GetActualTraversalRank())
       << "Search starting at needle continued past needle.";
 }
 
 TEST(TreeTraversal, DepthFirstSearchValueDoesNotExist)
 {
   int visitCount = 0;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (int i = 0; i < 10; i++)
   {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
   }
 
-  RefPtr<SearchTestNode> root = nodeList[0];
+  RefPtr<SearchTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[4]);
+  nodeList[1]->AddChild(nodeList[2]);
+  nodeList[1]->AddChild(nodeList[3]);
+  nodeList[4]->AddChild(nodeList[5]);
+  nodeList[4]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearch<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (int i = 0; i < 10; i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode.get(), nullptr)
+      << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchValueDoesNotExistReverse)
+{
+  int visitCount = 0;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (int i = 0; i < 10; i++)
+  {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[4]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[1]->AddChild(nodeList[2]);
   nodeList[4]->AddChild(nodeList[6]);
   nodeList[4]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
 
-  RefPtr<SearchTestNode> foundNode = DepthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (int i = 0; i < 10; i++)
   {
@@ -212,56 +395,105 @@ TEST(TreeTraversal, DepthFirstSearchValu
   }
 
   ASSERT_EQ(foundNode.get(), nullptr)
       << "Search found something that should not exist.";
 }
 
 TEST(TreeTraversal, DepthFirstSearchPostOrderNull)
 {
-  RefPtr<SearchTestNode> nullNode;
-  RefPtr<SearchTestNode> result = DepthFirstSearchPostOrder(nullNode.get(),
-      [](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> nullNode;
+  RefPtr<SearchTestNodeReverse> result = DepthFirstSearchPostOrder<layers::ReverseIterator>(nullNode.get(),
+      [](SearchTestNodeReverse* aNode)
       {
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
 }
 
 TEST(TreeTraversal, DepthFirstSearchPostOrderValueExists)
 {
   int visitCount = 0;
   size_t expectedNeedleTraversalRank = 7;
-  RefPtr<SearchTestNode> needleNode;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  RefPtr<SearchTestNodeForward> needleNode;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (size_t i = 0; i < 10; i++)
   {
     if (i == expectedNeedleTraversalRank) {
-      needleNode = new SearchTestNode(SearchNodeType::Needle, i);
+      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
       nodeList.push_back(needleNode);
     } else if (i < expectedNeedleTraversalRank) {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
     } else {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
     }
   }
 
-  RefPtr<SearchTestNode> root = nodeList[9];
+  RefPtr<SearchTestNodeForward> root = nodeList[9];
+  nodeList[9]->AddChild(nodeList[2]);
+  nodeList[9]->AddChild(nodeList[8]);
+  nodeList[2]->AddChild(nodeList[0]);
+  nodeList[2]->AddChild(nodeList[1]);
+  nodeList[8]->AddChild(nodeList[6]);
+  nodeList[8]->AddChild(nodeList[7]);
+  nodeList[6]->AddChild(nodeList[5]);
+  nodeList[5]->AddChild(nodeList[3]);
+  nodeList[5]->AddChild(nodeList[4]);
+
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearchPostOrder<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+      << "Returned node does not match expected value (something odd happened).";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueExistsReverse)
+{
+  int visitCount = 0;
+  size_t expectedNeedleTraversalRank = 7;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (size_t i = 0; i < 10; i++)
+  {
+    if (i == expectedNeedleTraversalRank) {
+      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+      nodeList.push_back(needleNode);
+    } else if (i < expectedNeedleTraversalRank) {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+    } else {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+    }
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[9];
   nodeList[9]->AddChild(nodeList[8]);
   nodeList[9]->AddChild(nodeList[2]);
   nodeList[2]->AddChild(nodeList[1]);
   nodeList[2]->AddChild(nodeList[0]);
   nodeList[8]->AddChild(nodeList[7]);
   nodeList[8]->AddChild(nodeList[6]);
   nodeList[6]->AddChild(nodeList[5]);
   nodeList[5]->AddChild(nodeList[4]);
   nodeList[5]->AddChild(nodeList[3]);
 
-  RefPtr<SearchTestNode> foundNode = DepthFirstSearchPostOrder(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
@@ -272,22 +504,22 @@ TEST(TreeTraversal, DepthFirstSearchPost
 
   ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
   ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
       << "Returned node does not match expected value (something odd happened).";
 }
 
 TEST(TreeTraversal, DepthFirstSearchPostOrderRootIsNeedle)
 {
-  RefPtr<SearchTestNode> root = new SearchTestNode(SearchNodeType::Needle, 0);
-  RefPtr<SearchTestNode> childNode1= new SearchTestNode(SearchNodeType::Hay);
-  RefPtr<SearchTestNode> childNode2 = new SearchTestNode(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
   int visitCount = 0;
-  RefPtr<SearchTestNode> result = DepthFirstSearchPostOrder(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> result = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
   ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
       << "Search starting at needle did not return needle.";
@@ -297,35 +529,74 @@ TEST(TreeTraversal, DepthFirstSearchPost
   ASSERT_EQ(childNode2->GetExpectedTraversalRank(),
       childNode2->GetActualTraversalRank())
       << "Search starting at needle continued past needle.";
 }
 
 TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExist)
 {
   int visitCount = 0;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (int i = 0; i < 10; i++)
   {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
   }
 
-  RefPtr<SearchTestNode> root = nodeList[9];
+  RefPtr<SearchTestNodeForward> root = nodeList[9];
+  nodeList[9]->AddChild(nodeList[2]);
+  nodeList[9]->AddChild(nodeList[8]);
+  nodeList[2]->AddChild(nodeList[0]);
+  nodeList[2]->AddChild(nodeList[1]);
+  nodeList[8]->AddChild(nodeList[6]);
+  nodeList[8]->AddChild(nodeList[7]);
+  nodeList[6]->AddChild(nodeList[5]);
+  nodeList[5]->AddChild(nodeList[3]);
+  nodeList[5]->AddChild(nodeList[4]);
+
+  RefPtr<SearchTestNodeForward> foundNode = DepthFirstSearchPostOrder<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (int i = 0; i < 10; i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode.get(), nullptr)
+      << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, DepthFirstSearchPostOrderValueDoesNotExistReverse)
+{
+  int visitCount = 0;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (int i = 0; i < 10; i++)
+  {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[9];
   nodeList[9]->AddChild(nodeList[8]);
   nodeList[9]->AddChild(nodeList[2]);
   nodeList[2]->AddChild(nodeList[1]);
   nodeList[2]->AddChild(nodeList[0]);
   nodeList[8]->AddChild(nodeList[7]);
   nodeList[8]->AddChild(nodeList[6]);
   nodeList[6]->AddChild(nodeList[5]);
   nodeList[5]->AddChild(nodeList[4]);
   nodeList[5]->AddChild(nodeList[3]);
 
-  RefPtr<SearchTestNode> foundNode = DepthFirstSearchPostOrder(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = DepthFirstSearchPostOrder<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (int i = 0; i < 10; i++)
   {
@@ -335,33 +606,33 @@ TEST(TreeTraversal, DepthFirstSearchPost
   }
 
   ASSERT_EQ(foundNode.get(), nullptr)
       << "Search found something that should not exist.";
 }
 
 TEST(TreeTraversal, BreadthFirstSearchNull)
 {
-  RefPtr<SearchTestNode> nullNode;
-  RefPtr<SearchTestNode> result = BreadthFirstSearch(nullNode.get(),
-      [](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> nullNode;
+  RefPtr<SearchTestNodeReverse> result = BreadthFirstSearch<layers::ReverseIterator>(nullNode.get(),
+      [](SearchTestNodeReverse* aNode)
       {
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result.get(), nullptr) << "Null root did not return null search result.";
 }
 
 TEST(TreeTraversal, BreadthFirstSearchRootIsNeedle)
 {
-  RefPtr<SearchTestNode> root = new SearchTestNode(SearchNodeType::Needle, 0);
-  RefPtr<SearchTestNode> childNode1= new SearchTestNode(SearchNodeType::Hay);
-  RefPtr<SearchTestNode> childNode2 = new SearchTestNode(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> root = new SearchTestNodeReverse(SearchNodeType::Needle, 0);
+  RefPtr<SearchTestNodeReverse> childNode1= new SearchTestNodeReverse(SearchNodeType::Hay);
+  RefPtr<SearchTestNodeReverse> childNode2 = new SearchTestNodeReverse(SearchNodeType::Hay);
   int visitCount = 0;
-  RefPtr<SearchTestNode> result = BreadthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> result = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
   ASSERT_EQ(result, root) << "Search starting at needle did not return needle.";
   ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
       << "Search starting at needle did not return needle.";
@@ -372,43 +643,92 @@ TEST(TreeTraversal, BreadthFirstSearchRo
       childNode2->GetActualTraversalRank())
       << "Search starting at needle continued past needle.";
 }
 
 TEST(TreeTraversal, BreadthFirstSearchValueExists)
 {
   int visitCount = 0;
   size_t expectedNeedleTraversalRank = 7;
-  RefPtr<SearchTestNode> needleNode;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  RefPtr<SearchTestNodeForward> needleNode;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (size_t i = 0; i < 10; i++)
   {
     if (i == expectedNeedleTraversalRank) {
-      needleNode = new SearchTestNode(SearchNodeType::Needle, i);
+      needleNode = new SearchTestNodeForward(SearchNodeType::Needle, i);
       nodeList.push_back(needleNode);
     } else if (i < expectedNeedleTraversalRank) {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
     } else {
-      nodeList.push_back(new SearchTestNode(SearchNodeType::Hay));
+      nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay));
     }
   }
 
-  RefPtr<SearchTestNode> root = nodeList[0];
+  RefPtr<SearchTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[2]);
+  nodeList[1]->AddChild(nodeList[3]);
+  nodeList[1]->AddChild(nodeList[4]);
+  nodeList[2]->AddChild(nodeList[5]);
+  nodeList[2]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+  RefPtr<SearchTestNodeForward> foundNode = BreadthFirstSearch<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
+  ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
+      << "Returned node does not match expected value (something odd happened).";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueExistsReverse)
+{
+  int visitCount = 0;
+  size_t expectedNeedleTraversalRank = 7;
+  RefPtr<SearchTestNodeReverse> needleNode;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (size_t i = 0; i < 10; i++)
+  {
+    if (i == expectedNeedleTraversalRank) {
+      needleNode = new SearchTestNodeReverse(SearchNodeType::Needle, i);
+      nodeList.push_back(needleNode);
+    } else if (i < expectedNeedleTraversalRank) {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+    } else {
+      nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay));
+    }
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[2]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[4]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[2]->AddChild(nodeList[6]);
   nodeList[2]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
-  RefPtr<SearchTestNode> foundNode = BreadthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
@@ -420,160 +740,287 @@ TEST(TreeTraversal, BreadthFirstSearchVa
   ASSERT_EQ(foundNode, needleNode) << "Search did not return expected node.";
   ASSERT_EQ(foundNode->GetType(), SearchNodeType::Needle)
       << "Returned node does not match expected value (something odd happened).";
 }
 
 TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExist)
 {
   int visitCount = 0;
-  std::vector<RefPtr<SearchTestNode>> nodeList;
+  std::vector<RefPtr<SearchTestNodeForward>> nodeList;
   for (int i = 0; i < 10; i++)
   {
-    nodeList.push_back(new SearchTestNode(SearchNodeType::Hay, i));
+    nodeList.push_back(new SearchTestNodeForward(SearchNodeType::Hay, i));
   }
 
-  RefPtr<SearchTestNode> root = nodeList[0];
+  RefPtr<SearchTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[2]);
+  nodeList[1]->AddChild(nodeList[3]);
+  nodeList[1]->AddChild(nodeList[4]);
+  nodeList[2]->AddChild(nodeList[5]);
+  nodeList[2]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+
+  RefPtr<SearchTestNodeForward> foundNode = BreadthFirstSearch<layers::ForwardIterator>(root.get(),
+      [&visitCount](SearchTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == SearchNodeType::Needle;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+      ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+          nodeList[i]->GetActualTraversalRank())
+          << "Node at index " << i << " was hit out of order.";
+  }
+
+  ASSERT_EQ(foundNode.get(), nullptr)
+      << "Search found something that should not exist.";
+}
+
+TEST(TreeTraversal, BreadthFirstSearchValueDoesNotExistReverse)
+{
+  int visitCount = 0;
+  std::vector<RefPtr<SearchTestNodeReverse>> nodeList;
+  for (int i = 0; i < 10; i++)
+  {
+    nodeList.push_back(new SearchTestNodeReverse(SearchNodeType::Hay, i));
+  }
+
+  RefPtr<SearchTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[2]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[4]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[2]->AddChild(nodeList[6]);
   nodeList[2]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
 
-  RefPtr<SearchTestNode> foundNode = BreadthFirstSearch(root.get(),
-      [&visitCount](SearchTestNode* aNode)
+  RefPtr<SearchTestNodeReverse> foundNode = BreadthFirstSearch<layers::ReverseIterator>(root.get(),
+      [&visitCount](SearchTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == SearchNodeType::Needle;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
-      ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(), 
+      ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
           nodeList[i]->GetActualTraversalRank())
           << "Node at index " << i << " was hit out of order.";
   }
 
-  ASSERT_EQ(foundNode.get(), nullptr) 
+  ASSERT_EQ(foundNode.get(), nullptr)
       << "Search found something that should not exist.";
 }
 
 TEST(TreeTraversal, ForEachNodeNullStillRuns)
 {
-  RefPtr<ForEachTestNode> nullNode;
-  ForEachNode(nullNode.get(),
-    [](ForEachTestNode* aNode)
+  RefPtr<ForEachTestNodeReverse> nullNode;
+  ForEachNode<layers::ReverseIterator>(nullNode.get(),
+    [](ForEachTestNodeReverse* aNode)
     {
       return TraversalFlag::Continue;
     });
 }
 
 TEST(TreeTraversal, ForEachNodeAllEligible)
 {
-  std::vector<RefPtr<ForEachTestNode>> nodeList;
+  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
   int visitCount = 0;
   for (int i = 0; i < 10; i++)
   {
-    nodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue,i));
+    nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue,i));
   }
 
-  RefPtr<ForEachTestNode> root = nodeList[0];
+  RefPtr<ForEachTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[4]);
+  nodeList[1]->AddChild(nodeList[2]);
+  nodeList[1]->AddChild(nodeList[3]);
+  nodeList[4]->AddChild(nodeList[5]);
+  nodeList[4]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+
+  ForEachNode<layers::ForwardIterator>(root.get(),
+      [&visitCount](ForEachTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == ForEachNodeType::Continue
+            ? TraversalFlag::Continue : TraversalFlag::Skip;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+}
+
+TEST(TreeTraversal, ForEachNodeAllEligibleReverse)
+{
+  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
+  int visitCount = 0;
+  for (int i = 0; i < 10; i++)
+  {
+    nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue,i));
+  }
+
+  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[4]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[1]->AddChild(nodeList[2]);
   nodeList[4]->AddChild(nodeList[6]);
   nodeList[4]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
 
-  ForEachNode(root.get(),
-      [&visitCount](ForEachTestNode* aNode)
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&visitCount](ForEachTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == ForEachNodeType::Continue
             ? TraversalFlag::Continue : TraversalFlag::Skip;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
-    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(), 
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
         nodeList[i]->GetActualTraversalRank())
         << "Node at index " << i << " was hit out of order.";
   }
 }
 
 TEST(TreeTraversal, ForEachNodeSomeIneligibleNodes)
 {
-  std::vector<RefPtr<ForEachTestNode>> expectedVisitedNodeList;
-  std::vector<RefPtr<ForEachTestNode>> expectedSkippedNodeList;
+  std::vector<RefPtr<ForEachTestNodeForward>> expectedVisitedNodeList;
+  std::vector<RefPtr<ForEachTestNodeForward>> expectedSkippedNodeList;
   int visitCount = 0;
-  
-  expectedVisitedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue, 0));
-  expectedVisitedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Skip, 1));
-  expectedVisitedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue, 2));
-  expectedVisitedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Skip, 3));
+
+  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, 0));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, 1));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, 2));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, 3));
 
-  expectedSkippedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue));
-  expectedSkippedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue));
-  expectedSkippedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Skip));
-  expectedSkippedNodeList.push_back(new ForEachTestNode(ForEachNodeType::Skip));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip));
 
-  RefPtr<ForEachTestNode> root = expectedVisitedNodeList[0];
-  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
+  RefPtr<ForEachTestNodeForward> root = expectedVisitedNodeList[0];
   expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
-  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
+  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
   expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
+  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
   expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
+  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
   expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
-  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
 
-  ForEachNode(root.get(),
-      [&visitCount](ForEachTestNode* aNode)
+  ForEachNode<layers::ForwardIterator>(root.get(),
+      [&visitCount](ForEachTestNodeForward* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == ForEachNodeType::Continue
             ? TraversalFlag::Continue : TraversalFlag::Skip;
       });
 
   for (size_t i = 0; i < expectedVisitedNodeList.size(); i++)
   {
-    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(), 
+    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
         expectedVisitedNodeList[i]->GetActualTraversalRank())
         << "Node at index " << i << " was hit out of order.";
   }
-  
+
   for (size_t i = 0; i < expectedSkippedNodeList.size(); i++)
-  { 
+  {
+    ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
+        expectedSkippedNodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << "was not expected to be hit.";
+  }
+}
+
+TEST(TreeTraversal, ForEachNodeSomeIneligibleNodesReverse)
+{
+  std::vector<RefPtr<ForEachTestNodeReverse>> expectedVisitedNodeList;
+  std::vector<RefPtr<ForEachTestNodeReverse>> expectedSkippedNodeList;
+  int visitCount = 0;
+
+  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, 0));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, 1));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, 2));
+  expectedVisitedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, 3));
+
+  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip));
+  expectedSkippedNodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip));
+
+  RefPtr<ForEachTestNodeReverse> root = expectedVisitedNodeList[0];
+  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[2]);
+  expectedVisitedNodeList[0]->AddChild(expectedVisitedNodeList[1]);
+  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[1]);
+  expectedVisitedNodeList[1]->AddChild(expectedSkippedNodeList[0]);
+  expectedVisitedNodeList[2]->AddChild(expectedVisitedNodeList[3]);
+  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[3]);
+  expectedVisitedNodeList[3]->AddChild(expectedSkippedNodeList[2]);
+
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&visitCount](ForEachTestNodeReverse* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == ForEachNodeType::Continue
+            ? TraversalFlag::Continue : TraversalFlag::Skip;
+      });
+
+  for (size_t i = 0; i < expectedVisitedNodeList.size(); i++)
+  {
+    ASSERT_EQ(expectedVisitedNodeList[i]->GetExpectedTraversalRank(),
+        expectedVisitedNodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+
+  for (size_t i = 0; i < expectedSkippedNodeList.size(); i++)
+  {
     ASSERT_EQ(expectedSkippedNodeList[i]->GetExpectedTraversalRank(),
         expectedSkippedNodeList[i]->GetActualTraversalRank())
         << "Node at index " << i << "was not expected to be hit.";
   }
 }
 
 TEST(TreeTraversal, ForEachNodeIneligibleRoot)
 {
   int visitCount = 0;
 
-  RefPtr<ForEachTestNode> root = new ForEachTestNode(ForEachNodeType::Skip, 0);
-  RefPtr<ForEachTestNode> childNode1 = new ForEachTestNode(ForEachNodeType::Continue);
-  RefPtr<ForEachTestNode> chlidNode2 = new ForEachTestNode(ForEachNodeType::Skip);
+  RefPtr<ForEachTestNodeReverse> root = new ForEachTestNodeReverse(ForEachNodeType::Skip, 0);
+  RefPtr<ForEachTestNodeReverse> childNode1 = new ForEachTestNodeReverse(ForEachNodeType::Continue);
+  RefPtr<ForEachTestNodeReverse> chlidNode2 = new ForEachTestNodeReverse(ForEachNodeType::Skip);
 
-  ForEachNode(root.get(),
-      [&visitCount](ForEachTestNode* aNode)
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&visitCount](ForEachTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == ForEachNodeType::Continue
             ? TraversalFlag::Continue : TraversalFlag::Skip;
       });
 
   ASSERT_EQ(root->GetExpectedTraversalRank(), root->GetActualTraversalRank())
@@ -582,78 +1029,120 @@ TEST(TreeTraversal, ForEachNodeIneligibl
       << "Eligible child was still hit.";
   ASSERT_EQ(chlidNode2->GetExpectedTraversalRank(), chlidNode2->GetActualTraversalRank())
       << "Ineligible child was still hit.";
 }
 
 TEST(TreeTraversal, ForEachNodeLeavesIneligible)
 {
 
-  std::vector<RefPtr<ForEachTestNode>> nodeList;
+  std::vector<RefPtr<ForEachTestNodeForward>> nodeList;
   int visitCount = 0;
   for (int i = 0; i < 10; i++)
   {
     if (i == 1 || i == 9) {
-      nodeList.push_back(new ForEachTestNode(ForEachNodeType::Skip, i));
+      nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Skip, i));
     } else {
-      nodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue, i));
+      nodeList.push_back(new ForEachTestNodeForward(ForEachNodeType::Continue, i));
     }
   }
 
-  RefPtr<ForEachTestNode> root = nodeList[0];
+  RefPtr<ForEachTestNodeForward> root = nodeList[0];
+  nodeList[0]->AddChild(nodeList[1]);
+  nodeList[0]->AddChild(nodeList[2]);
+  nodeList[2]->AddChild(nodeList[3]);
+  nodeList[2]->AddChild(nodeList[4]);
+  nodeList[4]->AddChild(nodeList[5]);
+  nodeList[4]->AddChild(nodeList[6]);
+  nodeList[6]->AddChild(nodeList[7]);
+  nodeList[7]->AddChild(nodeList[8]);
+  nodeList[7]->AddChild(nodeList[9]);
+
+  ForEachNode<layers::ForwardIterator>(root.get(),
+      [&visitCount](ForEachTestNodeForward* aNode)
+      {
+        aNode->SetActualTraversalRank(visitCount);
+        visitCount++;
+        return aNode->GetType() == ForEachNodeType::Continue
+            ? TraversalFlag::Continue : TraversalFlag::Skip;
+      });
+
+  for (size_t i = 0; i < nodeList.size(); i++)
+  {
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
+        nodeList[i]->GetActualTraversalRank())
+        << "Node at index " << i << " was hit out of order.";
+  }
+}
+
+TEST(TreeTraversal, ForEachNodeLeavesIneligibleReverse)
+{
+
+  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
+  int visitCount = 0;
+  for (int i = 0; i < 10; i++)
+  {
+    if (i == 1 || i == 9) {
+      nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Skip, i));
+    } else {
+      nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue, i));
+    }
+  }
+
+  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[2]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[2]->AddChild(nodeList[4]);
   nodeList[2]->AddChild(nodeList[3]);
   nodeList[4]->AddChild(nodeList[6]);
   nodeList[4]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
-  ForEachNode(root.get(),
-      [&visitCount](ForEachTestNode* aNode)
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&visitCount](ForEachTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
         return aNode->GetType() == ForEachNodeType::Continue
             ? TraversalFlag::Continue : TraversalFlag::Skip;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
-    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(), 
+    ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),
         nodeList[i]->GetActualTraversalRank())
         << "Node at index " << i << " was hit out of order.";
   }
 }
 
 TEST(TreeTraversal, ForEachNodeLambdaReturnsVoid)
 {
-  std::vector<RefPtr<ForEachTestNode>> nodeList;
+  std::vector<RefPtr<ForEachTestNodeReverse>> nodeList;
   int visitCount = 0;
   for (int i = 0; i < 10; i++)
   {
-    nodeList.push_back(new ForEachTestNode(ForEachNodeType::Continue,i));
+    nodeList.push_back(new ForEachTestNodeReverse(ForEachNodeType::Continue,i));
   }
 
-  RefPtr<ForEachTestNode> root = nodeList[0];
+  RefPtr<ForEachTestNodeReverse> root = nodeList[0];
   nodeList[0]->AddChild(nodeList[4]);
   nodeList[0]->AddChild(nodeList[1]);
   nodeList[1]->AddChild(nodeList[3]);
   nodeList[1]->AddChild(nodeList[2]);
   nodeList[4]->AddChild(nodeList[6]);
   nodeList[4]->AddChild(nodeList[5]);
   nodeList[6]->AddChild(nodeList[7]);
   nodeList[7]->AddChild(nodeList[9]);
   nodeList[7]->AddChild(nodeList[8]);
 
 
-  ForEachNode(root.get(),
-      [&visitCount](ForEachTestNode* aNode)
+  ForEachNode<layers::ReverseIterator>(root.get(),
+      [&visitCount](ForEachTestNodeReverse* aNode)
       {
         aNode->SetActualTraversalRank(visitCount);
         visitCount++;
       });
 
   for (size_t i = 0; i < nodeList.size(); i++)
   {
     ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(),