Closed Bug 1227233 Opened 4 years ago Closed 3 years ago

Use tree traversal algorithms for loops over the LayerMetrics tree

Categories

(Core :: Panning and Zooming, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla52
Tracking Status
firefox45 --- affected
firefox52 --- fixed

People

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

References

Details

(Keywords: arch, Whiteboard: gfx-noted)

Attachments

(1 file)

The generic tree traversal algorithms in gfx/layers/TreeTraversal.h could be used for some loops over the LayerMetrics tree. For some examples, see bug 1171312 comment 3.

To do this, the algorithms will have to be extended a bit to deal with the fact that the LayerMetrics tree is traversed "by value" (in contrast to the Layer and HitTesting trees which are traversed "by pointer").
Assignee: nobody → kevin.m.wern
Mentor: botond
Hey Kevin, I notice this bug is assigned to you. Do you have plans to work on it?
Hey, Botond!

Yes, I was going to pick up this bug soon. I could have an initial patch sometime by the end of this week?  I assume it involves adding two more iterator classes for forward and reverse sibling lists by value, then refactoring the Layer metrics algorithms.

Let me know if there's any additional info you think would be helpful.
LayerMetrics*
Cool! There is no rush, I mostly just wanted to see whether or not the bug should be made available for others to work on.

I'll post some technical suggestions soon, needinfoing myself so I don't forget.
Flags: needinfo?(botond)
(In reply to Kevin Wern from comment #2)
> I assume it involves adding two more
> iterator classes for forward and reverse sibling lists by value, then
> refactoring the Layer metrics algorithms.

Just adding new iterator classes won't be enough, because the algorithms currently have signatures like this:

  template <typename Iterator, typename Node, typename PreAction>
  void ForEachNode(Node* aRoot, const PreAction& aPreAction)

For the LayerMetrics tree, the root node will be an object of type LayerMetricsWrapper passed around by value, rather than by pointer, which will not match |Node*| for any value of |Node| (because it's not a pointer type).

What we might be able to get away with, is to remove the pointer from the signature, like so:

  template <typename Iterator, typename Node, typename PreAction>
  void ForEachNode(Node aRoot, const PreAction& aPreAction)

and then have calls over e.g. the Layer tree instantiate this with |Node = Layer*|, while calls over the LayerMetrics tree would instantiate this with |Node = LayerMetricsWrapper|.

I haven't thought about this in enough detail to be confident that we won't run into a snag anywhere, but you're welcome to give it a try and see if it works. If it does, it'd be a pretty clean solution!
Flags: needinfo?(botond)
Hey, Botond!

Just sent a patch. Sorry it took longer than expected.

The trick that you mentioned worked--for most cases--but I had to create a separate function (BreadthFirstSearchValue()) that returns Maybe<Node>. I would normally avoid this kind of extension and ignore the places that need this (or use ForEachNode), but in this case, I feel it is valuable with LayerManager::GetRootScrollableLayerId()'s textbook implementation of a breadth first search. The result is much more readable.

There was one other value-traversal instance that I decided not to refactor (the end of ContainerRender()). I just thought the library solution (doing ForEachNode but returning TreeTraversal::Abort when the current node doesn't have any children, in addition to when the condition is met) clouds a lot of the meaning that is instantly apparent as it stands.

Let me know what you think.
Comment on attachment 8794567 [details]
Bug 1227233: Increase scope of TreeTraversal.h to by-value traversal

https://reviewboard.mozilla.org/r/80510/#review79800

Thanks, Kevin! I'm glad to see the overall approach worked!

I have a few comments:

> I had to create a separate function (BreadthFirstSearchValue()) that returns Maybe<Node>. 
> I would normally avoid this kind of extension and ignore the places that need this (or 
> use ForEachNode), but in this case, I feel it is valuable with 
> LayerManager::GetRootScrollableLayerId()'s textbook implementation of a breadth first 
> search. The result is much more readable.

One of the reasons LayerMetricsWrapper works as a replacement for what is usually a pointer type is that, like a pointer type, it can represent a null value. Specifically, a default-constructed LayerMetricsWrapper is considered to be null (internally represented as mLayer == nullptr), and this nullness can be checked by calling IsValid() on it.

Pointers also have the property that, if T is a pointer type, T() will be a nullptr value of that pointer type.

Putting these together, we can add a requirement on Node that (1) it be capable of representing a null value, and (2) Node() creates such a null value. Pointers and LayerMetricsWrapper both satisfy these requirements out of the box.

We can then have a single BreadthFirstSearch() implementation which returns Node() if no result was found, and the call site in GetRootScrollableLayerId() can return something like |result.IsValid() ? result.Metrics().GetScrollId() : NULL_SCROLL_ID|.

::: gfx/layers/TreeTraversal.h:62
(Diff revision 1)
>      template <typename Node>
> -    static Node* FirstChild(Node* n) {
> +    static Node FirstChild(Node n) {
>        return n->GetLastChild();
>      }
>  };
> +class ForwardIteratorByValue

We can avoid these new Iterator classes by overloading the methods of the existing Iterator classes as follows:

  class ForwardIterator {
    ...
    template <typename Node>
    static Node* NextSibling(Node* n) {
      return n->GetNextSibling();
    }
    
    template <typename Node>
    static Node NextSibling(Node n) {
      return n.GetNextSibling();
    }
    ...
  };

When passed a node type which is not a pointer, such as LayerMetricsWrapper, only the second overload will be a match, and it will be chosen.

When passed a node type which is a pointer, such as Layer*, both overloads will be a match, but the first one will be a better match because it's more specialized (a T* argument is considered more specialized than a T argument).

::: gfx/layers/TreeTraversal.h:278
(Diff revision 1)
>   * Do a pre-order, depth-first search of the tree rooted at |aRoot|, and
>   * return the first visited node that satisfies |aCondition|, or nullptr
>   * if no such node was found.
>   *
> - * See ForEachNode() for the requirements on |Iterator| and |Node|
> + * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
> + * definition, but in addition to those, |Node| must be a pointer.

We can use the Node() technique to allow value types for Node in the DepthFirstSearch functions as well.

::: gfx/layers/apz/src/APZCTreeManager.cpp:571
(Diff revision 1)
> -                                      const gfx::Matrix4x4& aAncestorTransform,
> -                                      HitTestingTreeNode* aParent,
> -                                      HitTestingTreeNode* aNextSibling)
>  {
>    mTreeLock.AssertCurrentThreadOwns();
> +  std::stack<gfx::TreeAutoIndent*> indents;

I've heard mixed feedback about using ForEachNode in cases where we have to introduce stacks. The stacks are a slight performance hit (because their contents are dynamically allocated), so unless there's a clear readability win to counterbalance that, we probably shouldn't do it.

In this case (UpdateHitTestingTree), let's ask Kats what he thinks.
Attachment #8794567 - Flags: review?(botond)
Comment on attachment 8794567 [details]
Bug 1227233: Increase scope of TreeTraversal.h to by-value traversal

https://reviewboard.mozilla.org/r/80510/#review79818

::: gfx/layers/composite/AsyncCompositionManager.cpp
(Diff revision 1)
> -
> -  for (LayerMetricsWrapper child = aSubtreeRoot.GetFirstChild();
> -       child;
> -       child = child.GetNextSibling())
> -  {
> -    // Do not recurse into RefLayers, since our initial aSubtreeRoot is the

Please preserve this comment.
(In reply to Botond Ballo [:botond] from comment #8)
> ::: gfx/layers/apz/src/APZCTreeManager.cpp:571
> (Diff revision 1)
> > -                                      const gfx::Matrix4x4& aAncestorTransform,
> > -                                      HitTestingTreeNode* aParent,
> > -                                      HitTestingTreeNode* aNextSibling)
> >  {
> >    mTreeLock.AssertCurrentThreadOwns();
> > +  std::stack<gfx::TreeAutoIndent*> indents;
> 
> I've heard mixed feedback about using ForEachNode in cases where we have to
> introduce stacks. The stacks are a slight performance hit (because their
> contents are dynamically allocated), so unless there's a clear readability
> win to counterbalance that, we probably shouldn't do it.
> 
> In this case (UpdateHitTestingTree), let's ask Kats what he thinks.

ni?kats for this.

By the way, if we do end up using ForEachNode in UpdateHitTestingTree, we can inline the formerly-recursive overload of UpdateHitTestingTree into the other overload, since the only reason we had a two overloads to begin with is that one was recursive.
Flags: needinfo?(bugmail)
The new UpdateHitTestingTree code seems readable enough to me, I don't have objections on that front. I wouldn't necessarily say it's a readability *win* necessarily but it does clean up some of the arguments which is nice.
Flags: needinfo?(bugmail)
(In reply to Kartikaya Gupta (email:kats@mozilla.com) from comment #11)
> The new UpdateHitTestingTree code seems readable enough to me, I don't have
> objections on that front. I wouldn't necessarily say it's a readability
> *win* necessarily but it does clean up some of the arguments which is nice.

Ok, thanks. We can keep the conversion of UpdateHitTestingTree to ForEachNode in the patch, then.

Kevin, one other suggestion: LayerManager::GetRootContentLayer() contains a traversal which is not a traversal of the LayerMetrics tree per se, but could cleanly be expressed as one (basically, a BFS to find the first the first LayerMetricsWrapper for which Metrics().IsRootContent() is true).
Comment on attachment 8794567 [details]
Bug 1227233: Increase scope of TreeTraversal.h to by-value traversal

https://reviewboard.mozilla.org/r/80510/#review81440

Thanks! Just a minor comment remaining:

::: gfx/layers/TreeTraversal.h:195
(Diff revisions 1 - 2)
>   * first visited node that satisfies |aCondition|, or nullptr if no such node
>   * was found.
>   *
>   * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
> - * definition, but in addition to those, |Node| must be a pointer. For
> - * returning a value, see BreadthFirstSearchValue().
> + * definition, but in addition to those, |Node| must be able to express a null
> + * value.

Mention that Node() should create the null value.

::: gfx/layers/TreeTraversal.h:231
(Diff revisions 1 - 2)
>   * return the first visited node that satisfies |aCondition|, or nullptr
>   * if no such node was found.
>   *
>   * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
> - * definition, but in addition to those, |Node| must be a pointer.
> + * definition, but in addition to those, |Node| must be able to express a null
> + * value.

Likewise.

::: gfx/layers/TreeTraversal.h:257
(Diff revisions 1 - 2)
>  /*
>   * Perform a post-order, depth-first search starting at aRoot.
>   *
>   * |Iterator| and |Node| have all the same requirements seen in ForEachNode()'s
> - * definition, but in addition to those, |Node| must be a pointer.
> + * definition, but in addition to those, |Node| must be able to express a null
> + * value.

Likewise.
Attachment #8794567 - Flags: review?(botond) → review+
Meanwhile, I've pushed the patch to Try:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=01cedc0887cc
(In reply to Botond Ballo [:botond] from comment #15)
> Meanwhile, I've pushed the patch to Try:
> 
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=01cedc0887cc

It looks like Address Sanitizer detected a memory leak caused by the patch.
I believe it's caused solely by using pointers to new gfx::TreeAutoIndent, rather than values. I don't know why I did that.

I'm making that change, along with the comment changes you mentioned, then pushing to try.

I couldn't find anything outside of that one obvious issue.
Good catch, thanks!

Unfortunately, copying around TreeAutoIndent by value breaks the logging code that uses it. You can see this if you turn on the "apz.printtree" pref which enables this logging, with your patch applied.

What happens is this:

  - When you do |indents.push(gfx::TreeAutoIndent(mApzcTreeLog))|, you construct 
    a temporary TreeAutoIndent object. Its constructor calls TreeLog::IncreaseIndent().

  - stack::push() copies the temporary object into the stack, using TreeAutoIndent's
    copt constructor. Since we haven't explicitly defined TreeAutoIndent's copy
    constructor, the compiler generates an implicit one which just copies the fields.
    Notably, the copy constructor does not call TreeLog::IncreaseIndent().

  - The temporary object is then destroyed, and its destructor calls 
    TreeLog::DecreaseIndent().

  - When the value on the stack is popped, its destructor calls TreeLog::DecreaseIndent()
    again.

So, for every object we push, we end up increasing the indent only once, but decreasing it twice. As a result, TreeLog::mDepth will decrease "below zero", which really means wrapping around to (2^32 - 1) since it's unsigned. We then try to print that many spaces to indent the next line of the log, which doesn't go too well :)

Defining a copy constructor for TreeAutoIndent that calls TreeLog::IncreaseIndent() should fix this. (Might as well define an assignment operator while you're at it, or declare it as deleted.)
Oh, and we might also want to add a MOZ_ASSERT(mDepth > 0) to TreeLog::DecreaseIndent().
Ah yes. I think that's what happened, because I remember having this setup and Firefox would crash on startup with apz.printtree on. I fixed it by moving to this implementation, then I guess this issue slipped my mind.
Looking good, thanks!
Pushed by bballo@mozilla.com:
https://hg.mozilla.org/integration/autoland/rev/fd5aadb06d74
Increase scope of TreeTraversal.h to by-value traversal r=botond
https://hg.mozilla.org/mozilla-central/rev/fd5aadb06d74
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla52
Blocks: 1369929
You need to log in before you can comment on or make changes to this bug.