Closed Bug 1227231 Opened 7 years ago Closed 7 years ago

Use tree traversal algorithms for loops over the layer tree

Categories

(Core :: Panning and Zooming, defect)

Product:
Core
Component:
Panning and Zooming
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED
Milestone:
mozilla49
Tracking Flags:
Tracking Status
firefox45 --- affected
firefox49 --- fixed

People

(Reporter: botond, Assigned: kevin.m.wern, Mentored)

References

Details

(Keywords: arch, Whiteboard: gfx-noted)

Attachments

(1 file, 1 obsolete file)

MozReview Request: Bug 1227231: Use generic tree traversal algorithms for loops over Layer trees. r=botond
58 bytes, text/x-review-board-request
botond
: review+
Details 
The generic tree traversal algorithms in gfx/layers/TreeTraversal.h could be used for some loops over the Layer tree. For some examples, see bug 1171312 comment 3.
Assignee: nobody → kevin.m.wern
Mentor: botond
Keywords: arch
Whiteboard: gfx-noted
Started looking at this bug.  Let me know if there's any info you think would be helpful.
Flags: needinfo?(botond)
(In reply to Kevin Wern from comment #1)
> Started looking at this bug.  

Cool!

> Let me know if there's any info you think would be helpful.

So the important difference between the layer tree and the hit testing tree is that, while nodes in the hit testing tree only expose GetLastChild/GetPrevSibling methods, nodes in the layer tree also expose GetFirstChild/GetNextSibling methods (and these are the ones used most often).

Our algorithms are currently hard-coded to use GetLastChild/GetPrevSibling. It would be good to generalize them so we don't need two versions.

In bug 1227224 comment 5, I hinted at a technique for accomplishing this generalization: by using an "iterator" to encapsulate the method of navigating between nodes.

Here's how that might look more concretely:

  - Give the algorithms a new template type parameter, call it Iterator.

  - The traversal operations can become static methods on the Iterator
    type: instead of calling 'node->GetPrevSibling()', the algorithm
    would call 'Iterator::NextSibling(node)', and instead of calling
    'node->GetLastChild()', the algorithm would call 
    'Iterator::FirstChild(node)'.

  - Introduce two concrete types, ForwardIterator and ReverseIterator,
    with static methods matching the above calls. ForwardIterator would
    call GetFirstChild()/GetNextSibling(), while ReverseIterator would
    call GetLastChild()/GetPrevSibling().

  - When we want a loop using GetFirstChild/GetNextSibling, pass in
    ForwardIterator as the argument for the Iterator parameter. When
    we want a loop using GetLastChild/GetPrevSibling, pass in 
    ReverseIterator.

How does that sound?
Flags: needinfo?(botond)
Sounds good, changes are coming in right now.
Create an Iterator type with classes ForwardIterator and ReverseIterator,
having GetFirstChild/GetNextSibling and GetLastChild/GetPrevSibling
methods, respectively. Specify the iterator type for each call to
ForEachNode. With this, we can support trees with forward and reverse
sibling structures.

Additionally, apply these algorithms to all Layer recursive traversals,
where applicable. Update tests to ensure both directions yield expected
results.

Review commit: https://reviewboard.mozilla.org/r/39179/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/39179/
Attachment #8729807 - Flags: review?(botond)
https://treeherder.mozilla.org/#/jobs?repo=try&revision=0071ca7301f4

I ran a try run a while ago (https://treeherder.mozilla.org/#/jobs?repo=try&revision=0173075ae0f6) for an earlier changeset (current changeset minus tests and comment tweaks) that seems good. Hopefully, the results will match.

There were a few failures, but they were all linked to bugs or environment errors.
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/1-2/
Just had to remove a redundant refcounter (defined in base and derived TestNodes).

Try run is here:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=cec0c81b1611
Attachment #8729807 - Flags: review?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

https://reviewboard.mozilla.org/r/39179/#review36451

Thanks for the patch, Kevin! Thanks in particular for taking the initiative to convert some loops over the Layer tree other than the ones I've mentioned!

I haven't looked at the tests yet, but I looked at everything else. There are a few correctness issues, and a few minor style issues, but otherwise it lookds pretty good.

::: gfx/layers/LayerTreeInvalidation.cpp:106
(Diff revision 2)
>   * 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)

Even though this function is still technically recursive, it no longer does recursion beyond one level (because mask layers don't have children), so I'd prefer renaming it to NotifySubdocumentInvalidation.

::: gfx/layers/LayerTreeInvalidation.cpp:110
(Diff revision 2)
>  static void
>  NotifySubdocumentInvalidationRecursive(Layer* aLayer, NotifySubDocInvalidationFunc aCallback)
>  {
> -  aLayer->ClearInvalidRect();
> -  ContainerLayer* container = aLayer->AsContainerLayer();
> +  ForEachNode<ForwardIterator>(
> +      aLayer,
> +      [&aCallback] (Layer* l)

- Since |aCallback| is passed by value, let's 
  capture it by value as well.
  
- Please avoid one-letter variable names, and
  call the argument "layer" instead. This comment
  applies throughout the patch.

::: gfx/layers/LayerTreeInvalidation.cpp:122
(Diff revision 2)
> -  for (size_t i = 0; i < aLayer->GetAncestorMaskLayerCount(); i++) {
> -    Layer* maskLayer = aLayer->GetAncestorMaskLayerAt(i);
> +        for (size_t i = 0; i < l->GetAncestorMaskLayerCount(); i++) {
> +          Layer* maskLayer = l->GetAncestorMaskLayerAt(i);
> -    NotifySubdocumentInvalidationRecursive(maskLayer, aCallback);
> +          NotifySubdocumentInvalidationRecursive(maskLayer, aCallback);
> -  }
> +        }
> -
> -  if (!container) {
> +        if (!container) {

As only ContainerLayers have children anyways, we can omit this (and get rid of the 'container' variable in the pre-action altogether), and instead just null-check 'container' in the post-action.

That also means we can have the actions return void instead TraversalFlag.

::: gfx/layers/LayerTreeInvalidation.cpp:612
(Diff revision 2)
> -  for (size_t i = 0; i < aLayer->GetAncestorMaskLayerCount(); i++) {
> -    ClearInvalidations(aLayer->GetAncestorMaskLayerAt(i));
> +          for (size_t i = 0; i < l->GetAncestorMaskLayerCount(); i++) {
> +            ClearInvalidations(l->GetAncestorMaskLayerAt(i));
> -  }
> +          }
>  
> -  ContainerLayer* container = aLayer->AsContainerLayer();
> +          ContainerLayer* container = l->AsContainerLayer();
> -  if (!container) {
> +          if (!container) {

As with NotifySubdocumentInvalidations(), we can get rid of this check (and the 'container' variable) because only ContainerLayers have children to visit in the first place.

::: gfx/layers/Layers.cpp:1335
(Diff revision 2)
> -  for (Layer* l = GetFirstChild(); l; l = l->GetNextSibling()) {
> +  ForEachNode<ForwardIterator>(
> +      (Layer*) this,
> +      [this, &aToSort](Layer* l)
> +      {
> -    ContainerLayer* container = l->AsContainerLayer();
> +        ContainerLayer* container = l->AsContainerLayer();
> -    if (container && container->Extend3DContext() &&
> +        if (l == this || (container && container->Extend3DContext() &&

(I'm a bit on the fence about whether using ForEachNode in a case like this (where we have to special-case the start node) is a readability win, but we can go with it for now.)

::: gfx/layers/RenderTrace.cpp:31
(Diff revision 2)
>  }
>  
>  void RenderTraceLayers(Layer *aLayer, const char *aColor, const gfx::Matrix4x4 aRootTransform, bool aReset) {
> -  if (!aLayer)
> -    return;
> -
> +  ForEachNode<ForwardIterator>(
> +      aLayer,
> +      [&colorId] (Layer *l)

We have an opportunity to do a bit more cleanup here:

  - Make |colorId| a local variable in RenderTraceLayers(), rather than
    a namespace-scope variable. Continue capturing it by reference.
    
  - Get rid of the |colorId = 0| assignment at the end (as now we'll
    get a new |colorId| variable for the next call to RenderTraceLayers()).
    
  - Get rid of the |aReset| parameter altogether.

::: gfx/layers/TreeTraversal.h
(Diff revision 2)
>  /*
>   * 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().

Instead of removing this comment altogether, let's re-phrase it to express the new requirements: "|Iterator| should have static methods named NextSibling() and FirstChild() that accept an argument of type Node\*. For convenience, classes are |ForwardIterator| and |ReverseIterator| are provided which implement these methods as GetNextSibling()/GetFirstChild() and GetPrevSibling()/GetLastChild(), respectively, for any Node type that supports these operations."

It's probably sufficient to say this once, in the comment above the first ForEachNode() function, and then for other functions (like BreadthFirstSearch()) just say "see ForEachNode() for the requirements on |Iterator| and |Node|".

::: gfx/layers/basic/BasicLayerManager.cpp:495
(Diff revision 2)
>  static void
>  ApplyDoubleBuffering(Layer* aLayer, const IntRect& aVisibleRect)
>  {
> -  BasicImplData* data = ToData(aLayer);
> -  if (data->IsHidden())
> -    return;
> +  ForEachNode<ForwardIterator>(
> +      aLayer,
> +      [&aLayer, &aVisibleRect](Layer* l) {

Capture |aLayer| by value, it's just a pointer and we don't modify it.

::: gfx/layers/basic/BasicLayerManager.cpp:543
(Diff revision 2)
> -      // We need to double-buffer this container.
> +            // We need to double-buffer this container.
> -      data->SetOperator(CompositionOp::OP_SOURCE);
> +            data->SetOperator(CompositionOp::OP_SOURCE);
> -      container->ForceIntermediateSurface();
> +            container->ForceIntermediateSurface();
> +            return TraversalFlag::Skip;
> -    } else {
> +          } else {
> -      // Tell the children to clip to their visible regions so our assumption
> +            return TraversalFlag::Continue;

Unfortunately, this doesn't work as written: the recursive call needs to be passed |newVisibleRect| as its |aVisibleRect| argument.

I think we have two options:

  - Use a stack, the way we did in GetApzcAtPoint().
  - Leave this function alone.

I leave the choice up to you. If you choose the first option, please preserve the comment ("Tell the children to clip ...") somewhere.

::: gfx/layers/composite/AsyncCompositionManager.cpp:84
(Diff revision 2)
>              bool aWillResolvePlugins,
>              bool& aDidResolvePlugins)
>  {
> -  if (RefLayer* ref = aLayer->AsRefLayer()) {
> +  ForEachNode<ForwardIterator>(
> +      aLayer,
> +      [&aReady, &aTargetConfig, &aCompositor, &aHasRemote, aWillResolvePlugins, &aDidResolvePlugins](Layer* l)

This is probably a good place to use a reference capture-default, [&].

::: gfx/layers/composite/AsyncCompositionManager.cpp:396
(Diff revision 2)
>                                                     const ScreenMargin& aFixedLayerMargins,
> -                                                   bool aTransformAffectsLayerClip)
> +                                                   bool aTransformAffectsRootLayerClip)
> +{
> +  ForEachNodePostOrder<ForwardIterator>(
> +      aLayer,
> +      [aTransformScrollId, &aTransformedSubtreeRoot, &aPreviousTransformForRoot, &aCurrentTransformForRoot, &aFixedLayerMargins, aTransformAffectsRootLayerClip] (Layer* l)

I don't think this is correct. In the case where needsAsyncTransformUnapplied is true, we don't want to visit the children, but since we're using a post-order traversal, we visit the children unconditionally.

I think we need to:

  - Use a pre-order traversal.
  - If needsAsyncTransformUnapplied is false, return TraversalFlag::Continue
    (as the patch currently does).
  - In the remainder of the action, return TraversalFlag::Skip.

Also, this is another good place to use a reference capture-default.

::: gfx/layers/composite/AsyncCompositionManager.cpp:661
(Diff revision 2)
> -    }
> +          }
> -    default:
> +          default:
> -      NS_WARNING("Unhandled animated property");
> +            NS_WARNING("Unhandled animated property");
> -    }
> +          }
> -  }
> +        }
> -
> +        return TraversalFlag::Continue;

You can omit the return statement (recall, we support actions that return void).

::: gfx/layers/composite/AsyncCompositionManager.cpp
(Diff revision 2)
>  
> -    Matrix transform = shadowTransform.As2D();
> +          Matrix transform = shadowTransform.As2D();
> -    if (transform.IsTranslation() && !shadowTransform.IsIdentity()) {
> +          if (transform.IsTranslation() && !shadowTransform.IsIdentity()) {
> -      Point translation = transform.GetTranslation();
> +            Point translation = transform.GetTranslation();
> -      mLayerTransformRecorder.RecordTransform(aLayer, translation);
> +            mLayerTransformRecorder.RecordTransform(l, translation);
> -      return;

Why is the |return| removed? I think it needs to be kept to preserve the behaviour.

::: gfx/layers/composite/AsyncCompositionManager.cpp:813
(Diff revision 2)
>  
> -  LayerToParentLayerMatrix4x4 oldTransform = aLayer->GetTransformTyped() *
> +  ForEachNodePostOrder<ForwardIterator>(
> +      aLayer,
> +      [this, &aOutFoundRoot, &aClipDeferredToParent, &appliedTransform] (Layer* l)
> +      {
> +        Maybe<ParentLayerIntRect> clipDeferredFromChildren;

We have a similar problem here, as in ApplyDoubleBuffering(): for a given node, the value that the recursive calls put into |aClipDeferredToParent| needs to be picked up as |clipDeferredFromChildren| in the action for that node. (It's a bit different from ApplyDoubleBuffering(), in that the direction of communication is child -> parent rather than parent -> child).

The options are similar:

 - Use a stack to facilitate the communication.
 - Leave this function alone.

::: gfx/layers/composite/LayerManagerComposite.cpp:1240
(Diff revision 2)
> -    Matrix4x4 transform = aTransform;
> +          Matrix4x4 transform = aTransform;
> -    if (container->UseIntermediateSurface()) {
> +          if (container->UseIntermediateSurface()) {
> -      transform = aLayer->GetEffectiveTransform();
> +            transform = l->GetEffectiveTransform();
> -      transform = aTransform * transform;
> +            transform = aTransform * transform;
> -    }
> +          }
> -    for (Layer* child = aLayer->GetFirstChild(); child;
> +          return TraversalFlag::Continue;

I don't think this is quite correct - the original function returns after recursing over the children, while with this change we would go on to call the post-action for this node.

I think doing a pre-order traversal, and returning TraversalFlag::Skip in all cases except the recursive one, will preserve the behaviour.

(Note the similarity to AlignFixedAndStickyLayers. In general, if we *either* recurse *or* do other processing, we can use a pre-order traversal.)

::: gfx/layers/ipc/LayerTransactionParent.cpp:785
(Diff revision 2)
>  }
>  
>  static AsyncPanZoomController*
>  GetAPZCForViewID(Layer* aLayer, FrameMetrics::ViewID aScrollID)
>  {
> -  for (uint32_t i = 0; i < aLayer->GetFrameMetricsCount(); i++) {
> +  AsyncPanZoomController *resultApzc = nullptr;

nit: * goes with the type

::: gfx/layers/ipc/LayerTransactionParent.cpp:796
(Diff revision 2)
> +          if (l->GetFrameMetrics(i).GetScrollId() == aScrollID) {
> +            resultApzc = l->GetAsyncPanZoomController(i);
> +            return TraversalFlag::Abort;
> -    }
> +          }
> -  }
> +        }
> -  ContainerLayer* container = aLayer->AsContainerLayer();
> +        ContainerLayer* container = l->AsContainerLayer();

You can just unconditionally return Continue, as only ContainerLayers have children.
https://reviewboard.mozilla.org/r/39179/#review37101

The tests look good as well. Thanks for keeping them up to date! Just a few minor comments:

::: gfx/tests/gtest/TestTreeTraversal.cpp:13
(Diff revision 2)
>  
>  enum class SearchNodeType {Needle, Hay};
>  enum class ForEachNodeType {Continue, Skip};
>  
>  template <class T>
>  class TestNode {

Call this TestNodeBase.

::: gfx/tests/gtest/TestTreeTraversal.cpp:57
(Diff revision 2)
> +  private:
> +    void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
> +    void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
> +    void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
> +    RefPtr<TestNodeForward<T>> mSiblingNode;
> +    RefPtr<TestNodeForward<T>> mLastChildNode;

Why do you need to track the last child for TestNodeForward?

::: gfx/tests/gtest/TestTreeTraversal.cpp:183
(Diff revision 2)
>  {
>    return mType;
>  }
>  
>  typedef TestNode<SearchNodeType> SearchTestNode;
>  typedef TestNode<ForEachNodeType> ForEachTestNode;

I suspect these typedefs are no longer used.
Kats suggested writing some micro-benchmarks to verify that using a traversal algorithm instead of a manual loop doesn't regress performance. I filed bug 1258460 for this. Kevin, if you're interested in doing this as a follow-up, please feel free to take that bug.
Hey Kevin, how is this going? You did some really good work here, and we're not far from landing it. Let me know if you're stuck on anything, I'm happy to help!
Flags: needinfo?(kevin.m.wern)
Hey, sorry for falling off--I was actually going to get to it this weekend, or next week at the latest.  Up until Monday I had a bunch of moving deadlines at work, so that had to take priority.  If I knew initially that it was going to extend this long, I would have let you know earlier that I was still planning to work on it.

I read through the code review previously and don't remember finding anything that would be a road block, but I'll let you know if I run into any issues.
Flags: needinfo?(kevin.m.wern)
Cool, thanks! No rush, just wanted to make sure you weren't stuck.
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/2-3/
Attachment #8729807 - Flags: review?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/3-4/
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

https://reviewboard.mozilla.org/r/39179/#review46781

Thanks, Kevin! A few remaining issues:

::: gfx/layers/LayerTreeInvalidation.cpp:113
(Diff revisions 2 - 4)
>    ForEachNode<ForwardIterator>(
>        aLayer,
> -      [&aCallback] (Layer* l)
> +      [aCallback] (Layer* layer)
>        {
> -        l->ClearInvalidRect();
> -        ContainerLayer* container = l->AsContainerLayer();
> +        layer->ClearInvalidRect();
> +        ContainerLayer* container = layer->AsContainerLayer();

This variable can be removed altogether.

::: gfx/layers/LayerTreeInvalidation.cpp:126
(Diff revisions 2 - 4)
> -        return TraversalFlag::Continue;
>        },
> -      [&aCallback] (Layer* l)
> +      [aCallback] (Layer* layer)
>        {
> -        ContainerLayer* container = l->AsContainerLayer();
> +        ContainerLayer* container = layer->AsContainerLayer();
> +        MOZ_ASSERT(container != nullptr);

Now that we're not returning TraversalFlag::Skip for layers that are not ContainerLayers, the post-action will be called for all layers, so we can't assume it's a ContainerLayer; we have to check:

  if (ContainerLayer\* container = layer->AsContainerLayer()) {
    aCallback(container, container->GetLocalVisibleRegion().ToUnknownRegion());
  }
  
This is what I meant, in my original comment, by "null-check 'container' in the post-action"; sorry if it wasn't clear.

::: gfx/layers/basic/BasicLayerManager.cpp:499
(Diff revisions 2 - 4)
> +  std::stack<IntRect> visibleRectStack;
> +  visibleRectStack.push(aVisibleRect);
> +
>    ForEachNode<ForwardIterator>(
>        aLayer,
> -      [&aLayer, &aVisibleRect](Layer* l) {
> +      [&aLayer, &visibleRectStack](Layer* layer) {

Capture aLayer by value.

::: gfx/layers/basic/BasicLayerManager.cpp:530
(Diff revisions 2 - 4)
>              }
>              newVisibleRect.IntersectRect(newVisibleRect, cr);
>            }
>          }
>  
> +        visibleRectStack.push(newVisibleRect);

There are three return paths from this pre-action: two return Skip, one returns Continue.

We should only push the new visible rect onto the stack in the Continue case, because for the Skip cases, the post-action that would pop it off will not be called.

::: gfx/layers/composite/AsyncCompositionManager.cpp:417
(Diff revisions 2 - 4)
>          }
>  
>          // 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.
> +        // layer will apply to its subtree.        

This line only contains whitespace changes.

::: gfx/layers/composite/AsyncCompositionManager.cpp:438
(Diff revisions 2 - 4)
>          // 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::Continue;

We should be returning Skip here. 

(If you look at the original logic, we're looping over children _only_ when needsAsyncTransformUnapplied is false).

::: gfx/layers/composite/AsyncCompositionManager.cpp:811
(Diff revisions 2 - 4)
>  {
>    bool appliedTransform = false;
> +  std::stack<Maybe<ParentLayerIntRect>> stackDeferredClips;
> +  stackDeferredClips.push(aClipDeferredToParent);
>  
> -  ForEachNodePostOrder<ForwardIterator>(
> +  ForEachNode<ForwardIterator>(

We need to keep the bulk of the work in the post-action. (Observe that in the original code, we recurse on children before doing anything else.)

The interaction with the stack would work like this:

  - The pre-action pushes an empty clip rect onto the stack.

  - The post-action looks at the top of the stack, uses that value
    in place of |clipDeferredFromChildren|, and pops it off.

  - Where we currently populate |aClipDeferredToParent|, populate
    it into the new top of the stack (which was pushed by the
    pre-action of the parent, rather than the pre-action of the
    current node, and will be looked at by the post-action of the
    parent).
    
  - The |aClipDeferredToParent| parameter of 
    ApplyAsyncContentTransformToTree() can be removed entirely, as 
    its only purpose was for passing the information up during 
    recursion (the only non-recursive call site passes an empty clip).

::: gfx/layers/composite/LayerManagerComposite.cpp:1242
(Diff revisions 2 - 4)
> -            transform = l->GetEffectiveTransform();
> +            transform = layer->GetEffectiveTransform();
>              transform = aTransform * transform;
>            }
>            return TraversalFlag::Continue;
>          }
>          return TraversalFlag::Skip;

I assume you meant to remove this return

::: gfx/layers/composite/LayerManagerComposite.cpp:1247
(Diff revisions 2 - 4)
> -      {
>          // Only painted layers can be incomplete
> -        PaintedLayer* paintedLayer = l->AsPaintedLayer();
> +        PaintedLayer* paintedLayer = layer->AsPaintedLayer();
> -        ContainerLayer* container = l->AsContainerLayer();
>          if (!paintedLayer || !container) {
>            return TraversalFlag::Continue;

We want to be returning Skip here (the original code does not recurse here).

::: gfx/layers/composite/LayerManagerComposite.cpp:1279
(Diff revisions 2 - 4)
>            // the high precision region.
>            if (!composer) {
>              SubtractTransformedRegion(aLowPrecisionScreenRegion, incompleteRegion, transformToScreen);
>            }
>          }
>          return TraversalFlag::Continue;

Same here, we want to return Skip.

::: gfx/tests/gtest/TestTreeTraversal.cpp:57
(Diff revisions 2 - 4)
>    private:
>      void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
>      void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
>      void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
>      RefPtr<TestNodeForward<T>> mSiblingNode;
>      RefPtr<TestNodeForward<T>> mLastChildNode;

I don't think this field is necessary in TestNodeForward.
Attachment #8729807 - Flags: review?(botond)
Hey sorry, I should have mentioned that this is a WIP (I use mozreview's diff a lot to get a fresh perspective--it's a lot of code!).  I did a try run and was going to fix some issues, as the browser crashes almost immediately--but I also wanted to keep you in the loop on my progress.

Thank you so much for your feedback! Working on your comments as we speak (figuratively).
(In reply to Kevin Wern from comment #17)
> Hey sorry, I should have mentioned that this is a WIP (I use mozreview's
> diff a lot to get a fresh perspective--it's a lot of code!).

Note that, if your intention is to post a patch without flagging it for review, you can clear the reviewer field in ReviewBoard before publishing the review request. (You can then add it back when you're ready to have the patch reviewed.)
(In reply to Botond Ballo [:botond] from comment #16)
> ::: gfx/layers/basic/BasicLayerManager.cpp:499
> (Diff revisions 2 - 4)
> > +  std::stack<IntRect> visibleRectStack;
> > +  visibleRectStack.push(aVisibleRect);
> > +
> >    ForEachNode<ForwardIterator>(
> >        aLayer,
> > -      [&aLayer, &aVisibleRect](Layer* l) {
> > +      [&aLayer, &visibleRectStack](Layer* layer) {
> 
> Capture aLayer by value.

I just realized, you may get a static analysis failure if you do this, due to bug 1201275 not being fixed yet. In that case, feel free to continue capturing by reference.
(In reply to Botond Ballo [:botond] from comment #19)
> (In reply to Botond Ballo [:botond] from comment #16)
> > ::: gfx/layers/basic/BasicLayerManager.cpp:499
> > (Diff revisions 2 - 4)
> > > +  std::stack<IntRect> visibleRectStack;
> > > +  visibleRectStack.push(aVisibleRect);
> > > +
> > >    ForEachNode<ForwardIterator>(
> > >        aLayer,
> > > -      [&aLayer, &aVisibleRect](Layer* l) {
> > > +      [&aLayer, &visibleRectStack](Layer* layer) {
> > 
> > Capture aLayer by value.
> 
> I just realized, you may get a static analysis failure if you do this, due
> to bug 1201275 not being fixed yet. In that case, feel free to continue
> capturing by reference.

Yeah, I got an error related to that, so keeping it capture by reference.

(In reply to Botond Ballo [:botond] from comment #16)
> ::: gfx/tests/gtest/TestTreeTraversal.cpp:57
> (Diff revisions 2 - 4)
> >    private:
> >      void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
> >      void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
> >      void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
> >      RefPtr<TestNodeForward<T>> mSiblingNode;
> >      RefPtr<TestNodeForward<T>> mLastChildNode;
> 
> I don't think this field is necessary in TestNodeForward.

I thought I replied to the original comment on MozReview, but maybe it got overwritten by the patch submission?  The last child is used  when adding a new child--otherwise AddChild would have to traverse the entire linked list each time to find the last child.  The thought was it would be cleaner to keep a private pointer to the last child.  Though maybe it's not as readable?  I'd appreciate your thoughts on that--obviously, the performance was not really a consideration when choosing to do it this way.

Anyway, everything else is done other than that, so let me know your what your thoughts are and I'll get the updated patch in tonight.
Flags: needinfo?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/4-5/
Attachment #8729807 - Flags: review?(botond)
Includes the change to TestNodeForward. I did a Try run yesterday with a similar patch (excludes TestNodeBase changes) and ran into a few failures:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=9bfc95716c33&selectedJob=20276004

Any idea where to start here?
(In reply to Kevin Wern from comment #20)
> (In reply to Botond Ballo [:botond] from comment #16)
> > ::: gfx/tests/gtest/TestTreeTraversal.cpp:57
> > (Diff revisions 2 - 4)
> > >    private:
> > >      void SetNextSibling(RefPtr<TestNodeForward<T>> aNode);
> > >      void SetLastChild(RefPtr<TestNodeForward<T>> aNode);
> > >      void SetFirstChild(RefPtr<TestNodeForward<T>> aNode);
> > >      RefPtr<TestNodeForward<T>> mSiblingNode;
> > >      RefPtr<TestNodeForward<T>> mLastChildNode;
> > 
> > I don't think this field is necessary in TestNodeForward.
> 
> I thought I replied to the original comment on MozReview, but maybe it got
> overwritten by the patch submission?  The last child is used  when adding a
> new child--otherwise AddChild would have to traverse the entire linked list
> each time to find the last child.  The thought was it would be cleaner to
> keep a private pointer to the last child.  Though maybe it's not as
> readable?  I'd appreciate your thoughts on that--obviously, the performance
> was not really a consideration when choosing to do it this way.

My bad, I missed that it's required for efficient adding of a new child. It's fine to keep, then. (Maybe add a comment mentioning what it's for?)
Flags: needinfo?(botond)
Attachment #8729807 - Flags: review?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

https://reviewboard.mozilla.org/r/39179/#review47309

::: gfx/layers/LayerTreeInvalidation.cpp:125
(Diff revisions 4 - 5)
>        },
>        [aCallback] (Layer* layer)
>        {
>          ContainerLayer* container = layer->AsContainerLayer();
> -        MOZ_ASSERT(container != nullptr);
> +        if(container != nullptr) {
> -        aCallback(container, container->GetLocalVisibleRegion().ToUnknownRegion());
> +            aCallback(container, container->GetLocalVisibleRegion().ToUnknownRegion());

Just a couple style nits:
  - space between 'if' and '('
  - if statement body only idented one level (2 spaces)
  - style guide says the check should have the form 'if (container)'

::: gfx/layers/Layers.cpp:1332
(Diff revisions 4 - 5)
>  void
>  ContainerLayer::Collect3DContextLeaves(nsTArray<Layer*>& aToSort)
>  {
>    ForEachNode<ForwardIterator>(
>        (Layer*) this,
> -      [this, &aToSort](Layer* layer)
> +      [this, &aToSort](Layer* l)

The one-letter variable name snuck back in here for some reason.

::: gfx/layers/composite/AsyncCompositionManager.cpp:956
(Diff revision 5)
> -        // If our parent layer has a perspective transform, we want to apply
> +              // 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).
> +              // our scroll clip to it instead of to this layer (see bug 1168263).
> -        // A layer with a perspective transform shouldn't have multiple
> +              // A layer with a perspective transform shouldn't have multiple
> -        // children with FrameMetrics, nor a child with multiple FrameMetrics.
> +              // children with FrameMetrics, nor a child with multiple FrameMetrics.
> -        MOZ_ASSERT(!aClipDeferredToParent);
> -        aClipDeferredToParent = Some(clip);
> +              MOZ_ASSERT(!stackDeferredClips.top());
> +              stackDeferredClips.push(Some(clip));

Since we're pushing a clip onto the stack in the pre-action, we don't want to push another clip here - we just want to populate the clip pushed by the parent:

stackDeferredClips.top() = Some(clip);

Note that stack::top() returns a reference, so this works.

(You could also do |stackDeferredClips.top().emplace(clip)|, which is slightly more efficient as it doesn't construct a temporary Maybe.)
Note that this patch will need a rebase as some of the code it touches has changed slightly since the time you started working on it. (For example, the use of |clipDeferedFromChildren| in AsyncCompositionManager::ApplyAsyncContentTransformToTree() has moved to a different place.)

If you're adventurous, you can attempt to do the rebase. If not, I can do it before landing the patch.
(In reply to Kevin Wern from comment #22)
> I did a Try run yesterday with a
> similar patch (excludes TestNodeBase changes) and ran into a few failures:
> 
> https://treeherder.mozilla.org/#/
> jobs?repo=try&revision=9bfc95716c33&selectedJob=20276004
> 
> Any idea where to start here?

The first thing to do is to do a Try push without your patch, so that we can tell apart failures caused by your patch from unrelated failures:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=0bc7b473332c
(In reply to Botond Ballo [:botond] from comment #26)
> (In reply to Kevin Wern from comment #22)
> > I did a Try run yesterday with a
> > similar patch (excludes TestNodeBase changes) and ran into a few failures:
> > 
> > https://treeherder.mozilla.org/#/
> > jobs?repo=try&revision=9bfc95716c33&selectedJob=20276004
> > 
> > Any idea where to start here?
> 
> The first thing to do is to do a Try push without your patch, so that we can
> tell apart failures caused by your patch from unrelated failures:
> 
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=0bc7b473332c

It looks like all of the failures occur without your patch, too, so you're off the hook! :)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/5-6/
Attachment #8729807 - Flags: review?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

https://reviewboard.mozilla.org/r/39179/#review47615

Looks good, thanks!

All that remains to be done now is the rebase. Let me know if you'd like to give that a try.
Attachment #8729807 - Flags: review?(botond) → review+
I would love to do that, seeing that I have another patch to DOM with the same issue and would benefit from learning how to do this in Hg.  I tried last night and the merge was interrupted (hg showed a diff tool that I was unfamiliar with) and I think that lost my changes locally.  Worst case, I can pull the changes to a new/rewound repo, but is there an easier way?  And is there a better way to merge than what is used by default?

I'm used to git normally, processing changes with either diffmerge or just the standard text diff.
Flags: needinfo?(botond)
I'll describe how I do it:

  - First, add the following to your .hgrc file:
    
      [ui]
      merge = internal:merge3

    This tells hg to place 3-way conflict markers in the file whenever
    there is a merge conflict. I describe what those look like below.

  - "hg pull" from mozilla-central to get the latest code

  - "hg rebase --source <your commit> --dest <latest m-c head>"

    This will perform the rebase, inserting conflict markers as
    necessary, and it will tell you which files have conflicts.

  - Go through the files that have conflicts. Search for "<<<",
    which indicates the beginning of a conflict.

    Here's what a conflict will look like:

      <<<<<<<
      Some Code
      |||||||
      Some Code
      =======
      Some Code
      >>>>>>>

    The code between |||| and ==== is the code before your patch
    (an old revision of m-c).
    The code between ==== and >>>> is the code after your patch.
    Finally, the code between <<<< and |||| is the latest m-c.

    You want the merge the changes you made, and the changes
    that happened to m-c in the meantime. Once you figure out
    what the combined code should be, replace the entire conflict
    block with it.

    Do this for each conflict in the file.

  - Once all files with conflicts have their conflicts resolved,
    run "hg resolve --mark" to tell hg that you've fixed the
    conflicts, and then "hg rebase --continue" to finish the
    rebase (this last command should be a no-op since you're
    only rebasing one commit - in the general case it's to tell
    hg to go on and rebase the next commit when you're rebasing
    multiple commits - but you still need to run it to get hg
    into the correct state).

Note that you need Mercurial 3.2 to use internal:merge3; if you have an older Mercurial, it's worth upgrading just for that. (The alternative is "internal:merge", which omits the section between |||| and ====. I find that section very useful to have.)

Finally, note that the choice of merge tool, like the choice of editor, is a matter of taste. I like internal:merge3, but I know others who prefer GUI tools. If you prefer a GUI tool, by all means use one (generally, by replacing "internal:merge3" in the config file with a command that runs the GUI tool).
Flags: needinfo?(botond)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/6-7/
Thanks for the help with the rebase! It was definitely...an adventure.

Try run:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=cdde8415b7a9&selectedJob=20507847
https://reviewboard.mozilla.org/r/39179/#review48159

Thanks - the rebase looks good! Just a couple of nits:

::: gfx/layers/Layers.cpp:575
(Diff revisions 6 - 7)
>        {
>          layer->ApplyPendingUpdatesForThisTransaction();
> +      },
> +      [] (Layer *layer)
> +      {
> +        if (!layer->GetParent())

The reason we had this |!layer->GetParent()| check here when ApplyPendingUpdatesToSubtree() was recursive, was so that ClearPendingScrollInfoUpdate() is only called once, for the top-level call, not for recursive calls.

Now that we are using ForEachNode instead, this can be expressed more simply by calling ClearPendingScrollInfoUpdate() unconditionally after the ForEachNode call.

Also, there was a comment here ("Once we're done recursing through the whole tree, ..."). Please preserve it.

::: gfx/layers/composite/AsyncCompositionManager.cpp:423
(Diff revision 7)
> -                                true /* descendants' clip rects are always affected */);
> -    }
> -    return;
> -  }
> +        }
>  
> +        /* Descendants' clip rectangels are always affected */

nit: typo ("rectangels")

::: gfx/layers/ipc/CompositorBridgeParent.cpp:1175
(Diff revision 7)
>  /* static */ void
>  CompositorBridgeParent::SetShadowProperties(Layer* aLayer)
>  {
> -  if (Layer* maskLayer = aLayer->GetMaskLayer()) {
> +  ForEachNode<ForwardIterator>(
> +      aLayer,
> +      [] (Layer *l)

nit: one-character variable name
(In reply to Kevin Wern from comment #33)
> Thanks for the help with the rebase! It was definitely...an adventure.

(I have a fun rebase coming up, too, when I'm going to rebase my patches in bug 1267438 on top of this patch :)).
(In reply to Botond Ballo [:botond] from comment #35)
> (I have a fun rebase coming up, too, when I'm going to rebase my patches in
> bug 1267438 on top of this patch :)).

Actually, I ended up landing bug 1267438 first, which means this will need to be rebased on top of that, too. I can do that rebase, though, you don't need to :)
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/39179/diff/7-8/
Comment on attachment 8729807 [details]
MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer trees r=botond

https://reviewboard.mozilla.org/r/39179/#review48907

::: gfx/layers/Layers.cpp:576
(Diff revisions 7 - 8)
> -        }
>        });
> +
> +      // Once we're done recursing through the whole tree, clear the pending
> +      // updates from the manager.
> +      layer->Manager()->ClearPendingScrollInfoUpdate();

Now that this call is outside the ForEachNode() call, it should just be:

Manager()->ClearPendingScrollInfoUpdate();

(and only indented one level). I'll fix this during my rebase.
Attachment #8729807 - Flags: review+
Create an Iterator type with classes ForwardIterator and ReverseIterator,
having GetFirstChild/GetNextSibling and GetLastChild/GetPrevSibling
methods, respectively. Specify the iterator type for each call to
ForEachNode. With this, we can support trees with forward and reverse
sibling structures.

Additionally, apply these algorithms to all Layer recursive traversals,
where applicable. Update tests to ensure both directions yield expected
results.

Review commit: https://reviewboard.mozilla.org/r/52039/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/52039/
Attachment #8751492 - Flags: review?(botond)
Attachment #8729807 - Attachment is obsolete: true
^ Rebased patch on top of bug 1267438.

In addition to fixing the issue described in comment 38, I made one enhancement: I removed the |aLayer| parameter of AlignFixedAndStickyLayers, as it was only distinct from |aTransformedSubtreeRoots| for recursive calls.
(In reply to Botond Ballo [:botond] from comment #38)
> Comment on attachment 8729807 [details]
> MozReview Request: Bug 1227231: Modify tree traversal algorithms for Layer
> trees r=botond
> 
> https://reviewboard.mozilla.org/r/39179/#review48907
> 
> ::: gfx/layers/Layers.cpp:576
> (Diff revisions 7 - 8)
> > -        }
> >        });
> > +
> > +      // Once we're done recursing through the whole tree, clear the pending
> > +      // updates from the manager.
> > +      layer->Manager()->ClearPendingScrollInfoUpdate();
> 
> Now that this call is outside the ForEachNode() call, it should just be:
> 
> Manager()->ClearPendingScrollInfoUpdate();
> 
> (and only indented one level). I'll fix this during my rebase.

Awesome! Thank you so much!

Sorry about the absent-mindedness there--work ended up still being crazier than I anticipated...
Comment on attachment 8751492 [details]
MozReview Request: Bug 1227231: Use generic tree traversal algorithms for loops over Layer trees. r=botond

Try push looks good!

This is ready to land, but I'd like to wait until bug 1267438 merges to mozilla-central (to be sure that it doesn't get backed out again), before landing this.
Attachment #8751492 - Flags: review?(botond) → review+
All right, bug 1267438 has merged to m-c. Let's land this before it bit-rots further!
https://hg.mozilla.org/mozilla-central/rev/09c5d774bd83
Status: NEW → RESOLVED
Closed: 7 years ago
status-firefox49: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla49
Kevin, I just wanted to say thanks again for your awesome work here!
Blocks: 1283236
You need to log in before you can comment on or make changes to this bug.