--- 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";
@@ -1258,17 +1258,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()) {
@@ -1305,17 +1305,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();
}
});
}
@@ -1349,17 +1349,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();
}
@@ -1568,17 +1568,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);
@@ -1699,17 +1699,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,
@@ -1720,17 +1720,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;
@@ -1786,32 +1786,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;
}
@@ -1822,25 +1822,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) {
@@ -784,26 +786,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);
@@ -1200,73 +1200,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(),