1171312 - Introduce generic tree traversal algorithms

Status: RESOLVED FIXED

(Core :: Graphics: Layers, defect)

Description

[Botond Ballo [:botond]]

We have several tree structures in layers and APZ code that are very similar: 
  - Layer tree
  - LayerMetrics tree
  - HitTestingNode tree (formerly the APZC tree)

We do a *lot* of operations on these trees that have the following form:

  For a particular traversal order,
    - find the first node that matches a condition, OR
    - do something to each node, OR
    - do something to each node, accumulating a result
  or something similar.

Currently we invariably hand-code the traversal in each place, leading to a lot of code duplication.

I think we should define a set of generic tree traversal algorithms, and reuse them for operations that have the above form. This would decouple the traversal (generic) from the operation being done at each node (specific), eliminating a lot of duplication and reducing the possibilities for error.

Especially now that we can use C++11 lambdas, this can be done without undue boilerplate.

Comment 1

[Botond Ballo [:botond]]

This might make a good mentored bug for someone who has some previous experience with C++ templates.

Comment 2

[Tim Stullich [:tstullich]]

Hi,
If this bug has not been taken by anyone I would like to take it up. I have some experience with C++ templates, but perhaps less with C++11 lambdas. Hopefully that won't be too big of an issue.

Comment 3

[Botond Ballo [:botond]]

Thanks for your interest, Tim! I assigned the bug to you.

This is a pretty open-ended bug, so it's partly up to you where and how far you want to take it.

Here are some of the things we could generalize over:

  - The different tree structures (Layer, LayerMetricsWrapper, HitTestingTreeNode)
    and the interface they provide for navigating from a node to its children. For 
    example, the navigation methods of Layer and HitTestingTreeNode return pointers 
    to the nodes in question, while the navigation methods in LayerMetricsWrapper
    return the nodes by value.

  - The order of the traversal, as in breadth-first, depth-first, etc.

  - The order in which children of a node are visited. Layer and LayerMetrics have
    both GetFirstChild/GetNextSibling and GetLastChild/GetPrevSibling methods,
    facilitating both back-to-front and front-to-back traversal. HitTestingTreeNode
    only has GetLastChild/GetPrevSibling methods (because hit testing is done 
    front-to-back).

  - Whether the traversal stops after a condition is met (as in a search of the 
    tree), and whether it returns or accumulates a result.

Of course, we don't have to do this all at once! My preference is to make small, incremental changes, committing the code frequently. (This avoids large patches bit-rotting over time.)

That said, here are some starting points for you:

  - Make sure you have an up-to-date build. Instructions for building are here [1].

  - Make sure you understand the structure of the trees in question. They are all 
    n-ary trees, meaning nodes can have any number of children. Rather than 
    representing them by storing pointers to all of the children in a node, each 
    node stores a pointer to its first child, and to its next sibling (or last 
    child and previous sibling, or both).

    The definitions of the tree structures can be found here:

      Layer: [2]
      LayerMetricsWrapper: [3]
      HitTestingTreeNode: [4]

    Note that these classes contain a lot of things that are irrelevant for the
    purposes of this bug. The only relevant part is the navigation methods:
    GetFirstChild, GetLastChild, GetNextSibling, GetPrevSibling, GetParent.

  - Look at some of the existing code that traverses the trees. Here are some
    examples:

      HitTestingTreeNode: [5], [6], [7]
      LayerMetricsWrapper: [8], [9], [10]
      Layer: [11], [12], [13]

    As you can see, there is quite a variety. Think about how these different
    instances of traversals could fit into a unified traversal framework.

  - A concrete starting point might be the BreadhFirstSearch() method I added
    recently [14], which currently has two callers: [15] and [16]. There are
    two improvements we can immediately make to it:

      (1) The callers don't currently use lambdas. This was due to a bug in 
          our static analysis plugin which was triggering false-positive errors
          if we tried to use lambdas there. The bug has recently been fixed, so
          we can change the callers to use lambdas. This would be a good
          opportunity for you to become familiar with lambdas :)
      
      (2) We should move the function to a header file where it can be re-used
          by other code. I would suggest adding a new header, 
          gfx/layers/TreeTraversal.h.

    These could be your first concrete code changes. We can then follow them up
    by transitioning other existing traversals to use this function, tweaking the
    interface to make it more general, adding additional traversal functions, and 
    so on.

I know this was a long braindump. You'll probably have questions. Ask them here, or find me on IRC (my nick is 'botond' and #apz is a good channel to find me in).


[1] https://developer.mozilla.org/en-US/docs/Simple_Firefox_build
[2] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/Layers.h?rev=91d6e262b662#738
[3] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/LayerMetricsWrapper.h?rev=91d6e262b662#14
[4] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/HitTestingTreeNode.h?rev=91d6e262b662#22
[5] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#124
[6] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#1076
[7] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#1458
[8] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/composite/AsyncCompositionManager.cpp?rev=91d6e262b662#532
[9] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/composite/AsyncCompositionManager.cpp?rev=91d6e262b662#923
[10] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/composite/ContainerLayerComposite.cpp?rev=91d6e262b662#52
[11] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/composite/AsyncCompositionManager.cpp?rev=91d6e262b662#550
[12] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/Layers.cpp?rev=91d6e262b662#88
[13] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/composite/AsyncCompositionManager.cpp?rev=91d6e262b662#67
[14] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#1538
[15] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#1585
[16] http://mxr.mozilla.org/mozilla-central/source/gfx/layers/apz/src/APZCTreeManager.cpp?rev=91d6e262b662#1604

Comment 4

[Tim Stullich [:tstullich]]

Hey Botond,
Thank you for your response. This is a very in-depth write-up and I will try and work my way through it today and this weekend, in order to get some ideas on how to get started on this problem. Will you be online over the weekend on IRC in case there are some issues I will run into? I have a current build as of last night and I will try and keep it up-to-date as I go along.

Comment 5

[Botond Ballo [:botond]]

(In reply to Tim Stullich from comment #4)
> Will you be online over the
> weekend on IRC in case there are some issues I will run into?

I'll try to be online when I can. Look for the IRC nick 'botond|home'.

If you don't see me online, post your questions in a comment here and I'll answer them when I can.

Comment 6

[Tim Stullich [:tstullich]]

Hi Botond,
I read through some of the code and I am trying to make sense of some of things I am seeing. Hopefully you can answer me these questions:
1. Looking at the function definition of the BreadthFirstSearch() where is the Condition class defined? I tried to look up the definition for it but I am unsure whether or not it exists.
2. Is the Node* type also defined anywhere or is it also part of a prototype for this new I am going to work on?
3. Should these templated routines be housed within APCZTreeManager or should the functionality be decoupled in its own generic class?
If you could help to clarify this for, it would go a long way. Thanks :-)

Comment 7

[Botond Ballo [:botond]]

(In reply to Tim Stullich from comment #6)
> 1. Looking at the function definition of the BreadthFirstSearch() where is
> the Condition class defined? I tried to look up the definition for it but I
> am unsure whether or not it exists.

Condition is a template parameter of BreadthFirstSearch(). The concrete type it represents depends on the instantiation; for the two current call sites, it's the local classes RootForLayersIdMatcher and RootContentForLayersIdMatcher (defined inside the functions FindRootApzcForLayersId() and FindRootContentApzcForLayersId(), respectively).

(By the way, it is these local classes that I am proposing be replaced by lambdas. After that change, the type of Condition would be an (unnamed) lambda type in each case.)

> 2. Is the Node* type also defined anywhere or is it also part of a prototype
> for this new I am going to work on?

Node is also a template parameter of BreadthFirstSearch(). The current call sites both instantiate it as HitTestingTreeNode. Future call sites could also instantiate it as Layer. (Trying to instantiate it with LayerMetricsWrapper won't currently work, because LayerMetricsWrapper's navigation methods return by value, while BreadthFirstSearch() currently expects them to return pointers.)

> 3. Should these templated routines be housed within APCZTreeManager or
> should the functionality be decoupled in its own generic class?

I think the traversal algorithms would work best as non-member functions. In terms of a file to keep them in, I suggested above creating a new header gfx/layers/TreeTraversal.h.

Let me know if that clarifies things!

Comment 8

[Tim Stullich [:tstullich]]

Yes, that clears things up a lot. Thank you!

Comment 9

[Tim Stullich [:tstullich]]

After some work on this bug I came up with two more questions:
1. Since some Trees traverse their nodes by passing nodes by reference and others by pointers, should I create two separate functions that will be able to handle both cases but perform the same routine or should the tree traversal methods be changed in a way such that they conform to one form of passing in their nodes?
2. Since the HitTestingTree nodes should only be traversed front-to-back, should I create separate functions for this data type as well?
Solutions to these questions could potentially make the code quite redundant, so I am trying to come up with a way to make the templates as generic as possible so that code reuse can be avoided.

Comment 10

[Botond Ballo [:botond]]

Great questions!

(In reply to Tim Stullich from comment #9)
> 1. Since some Trees traverse their nodes by passing nodes by reference and
> others by pointers, should I create two separate functions that will be able
> to handle both cases but perform the same routine or should the tree
> traversal methods be changed in a way such that they conform to one form of
> passing in their nodes?

On the one hand, we want to avoid duplicating code, so we don't want two separate functions.

On the other hand, the navigation methods of the various tree classes have the interface that they have for a reason:

  - Layer and HitTestingTreeNode are heavyweight objects allocated on the heap.
    This is why they are passed around by pointer. If we tried to pass them by
    value (or rather, by reference, as they are heavyweight and we don't want
    to be copying them), we'd run into the problem that a reference to one of 
    these types cannot represent "null" (i.e. "there is no node here"). We need
    to represent that, because e.g. GetFirstChild() on a leaf node still needs
    to return *something* (currently it returns a null pointer).

    Note that LayerMetricsWrapper doesn't have this problem, as it has a special
    value that represents "null".

  - LayerMetricsWrapper is a lightweight object allocated on the stack. That is
    why it's passed by value. If we tried to pass it by pointer, we'd run into
    object lifetime issues.

Therefore, we don't want to change the navigation interfaces of these classes, either.

Problems of this sort often come up with templates, and are often solved using a technique called "traits". You can read about traits here [1].

That said, we don't have to solve this problem right away. We can start by only considering Layer and HitTestingTreeNode for now (and thus have the algorithm assume the navigation methods return pointers), and come back later to generalize it to work with LayerMetricsWrapper too.

> 2. Since the HitTestingTree nodes should only be traversed front-to-back,
> should I create separate functions for this data type as well?

Similar to the above, we don't want to have separate functions. Different traversal orders can be handled with traits, too, with the difference that the caller will have to pass something in to indicate the desired traversal order, as that can't be determined from the type of the node. Again, we can leave this for later.

Here's what I suggest doing for now:

  - Limit the algorithm to working with Layer and HitTestingTreeNode only

  - Limit the algorithm to doing front-to-back traversals (i.e. using
    GetLastChild / GetPrevSibling)

and therefore only transition call sites that meet these criteria.

Once we've done that, we can lift both of these limitations in follow-up changes that introduce traits.

How does that sound?

[1] http://accu.org/index.php/journals/442

Comment 11

[Tim Stullich [:tstullich]]

Yeah, that sounds great! I will try and see if I can get something substantial by the end of this weekend. Is there a way to post code that I would like to have reviewed but do not want to submit as a patch right away? I hope that question makes sense.

Comment 12

[Botond Ballo [:botond]]

Yes! You can choose between two options:

  (1) Post the patch as an attachmennt to the bug, and flag me for 'feedback'.

  (2) If you're adventurous, you can try using our fancy new review system, 
      MozReview [1].

[1] http://mozilla-version-control-tools.readthedocs.org/en/latest/mozreview-user.html

Comment 13

[Tim Stullich [:tstullich]]

Sounds good. I have used Review Board at another company so this looks pretty familiar to me. I will try and submit a review through there.

Comment 14

[Tim Stullich [:tstullich]]

Hey Botond,
I tried setting up my environment to work with MozReview, but I am not sure I can actually use it. There is a step that requires you to have a Mozilla LDAP account and I am not sure I actually have one of those.

Comment 15

[Botond Ballo [:botond]]

(In reply to Tim Stullich from comment #14)
> I tried setting up my environment to work with MozReview, but I am not sure
> I can actually use it. There is a step that requires you to have a Mozilla
> LDAP account and I am not sure I actually have one of those.

You're right, using MozReview requires having Level 1 commit access. I forgot about that.

You're welcome to apply for Level 1 commit access (see https://www.mozilla.org/en-US/about/governance/policies/commit/). I can vouch for you.

In the meantime, please use the first method (uploading attachments) to post patches.

Comment 16

[Tim Stullich [:tstullich]]

Attachment: First patch to tree traversal algorithms

This is my first patch. It's rather small but since we want to make incremental updates to this I feel like it's a good start.

Comment 17

[Botond Ballo [:botond]]

Comment on attachment 8636167 [details] [diff] [review]
First patch to tree traversal algorithms

Review of attachment 8636167 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks - this generally looks good!

However, as part of this patch, please also remove the BreadthFirstSearch() function from APZCTreeManager.cpp, and change its callers to call the version in this file instead. That makes sure we're actually exercising this code.

::: gfx/layers/TreeTraversal.h
@@ +19,5 @@
> + * was found.
> + *
> + * |Node| should have methods GetLastChild() and GetPrevSibling().
> + */
> +template <typename Node, typename F>

Please give the second template parameter a descriptive name, such as |Condition|.

@@ +20,5 @@
> + *
> + * |Node| should have methods GetLastChild() and GetPrevSibling().
> + */
> +template <typename Node, typename F>
> +static const Node* BreadthFirstSearch(const Node* aRoot, F &aLambdaCondition)

- 'static' on a function should only be used for functions defined in a .cpp file
  that we want to keep private to that .cpp file. It should not be used for 
  functions defined in header files.

  (If you're interested in what 'static' on a function does on a more technical 
  level, it gives the function internal linkage, which means each translation unit 
  that defines the function will get its own copy of the function that's not visible 
  to other translation units. In the case of a function private to a .cpp file, it's
  only defined in one translation unit anyways, and it's the "not visible to other
  translation units" part that we're after. In the case of a function defined in a
  header file, which presumably will be included from multiple translation units, 
  we don't want to have multiple copies of the function, as that causes code bloat.)

- F can be, but doesn't have to be, a lambda type, so rather than calling the variable 
  |aLambdaCondition|, I'd call it just |aCondition|.

  Also, the convention in this codebase is to place the '&' next to the type, not
  next to the variable name.

These comments apply to DepthFirstSearch() as well.

Comment 18

[Tim Stullich [:tstullich]]

Hey Botond,
Thanks for the quick response. I will try and get those changes worked in for my next patch. I'll contact you if anything gets in the way.

Comment 19

[Tim Stullich [:tstullich]]

Attachment: A second patch that addresses the changes made in the first review

Created a second patch that hopefully addresses all of the suggested changes.

Comment 20

[Tim Stullich [:tstullich]]

Attachment: treetraversal3.patch

The third patch where each commit should have been folded into one. I am not sure if it picked up all of the changes, although my files show up in that sense. I may have rebased this incorrectly...

Comment 21

[Tim Stullich [:tstullich]]

Hey Botond,
I just got my level 1 commit access. I am able to push to mozreview now. Should I open a review there or just keep the currently submitted patch under review as is?

Comment 22

[Botond Ballo [:botond]]

Comment on attachment 8636356 [details] [diff] [review]
treetraversal3.patch

Review of attachment 8636356 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks, this looks great!

The only thing that's missing is that APZCTreeManager.cpp needs to include TreeTraversal.h. Your previous patch had that, so this is probably a change that got lost while you were folding the two patches into one.

Comment 23

[Tim Stullich [:tstullich]]

Attachment: treetraversalfinal.patch

This should be the final patch hopefully. I have been having some trouble with histedit so if this does not quite work out I will try and find a way to permanently fix this.

Comment 24

[Tim Stullich [:tstullich]]

Attachment: treetraversal4.patch

This patch should have all of the correct changes now. After some issues with histedit all of the changes should be presented.

Comment 25

[Botond Ballo [:botond]]

Comment on attachment 8636865 [details] [diff] [review]
treetraversal4.patch

Review of attachment 8636865 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!

I submitted the patch to the Try server to make sure it builds on all platforms and passes tests: 
https://treeherder.mozilla.org/#/jobs?repo=try&revision=187c59ab703d

Comment 26

[Tim Stullich [:tstullich]]

Awesome! Let's hope the tests pass. I'll also set the status of this bug to ASSIGNED.

Comment 27

[Botond Ballo [:botond]]

For future reference, here is the simple version control workflow I recommend:

  <make changes to your working directory>
  hg commit
  <post changeset for review, either using MozReview or using 'hg export' to get a patch file>
  <to address review comments, make more changes to your working directory>
  hg commit --amend    # this folds the changes you just made into the commit
  <post updated changeset for review>
  <rinse and repeat>

Comment 28

[Tim Stullich [:tstullich]]

Yeah, that sounds like a plan. I will do that from now on. I just got way too hung up on trying to make things work correctly that parts of my code got last. In the future I will post things to MozReview as well now that I am able to.

Comment 29

[Tim Stullich [:tstullich]]

Looks like all of the tests pass according to the link:
https://treeherder.mozilla.org/#/jobs?repo=try&revision=187c59ab703d
What is the next step from here?

Comment 30

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/9b9fc13b4e1b

Comment 31

[Botond Ballo [:botond]]

(In reply to Tim Stullich [:tstullich] from comment #29)
> Looks like all of the tests pass according to the link:
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=187c59ab703d
> What is the next step from here?

I reworded the commit message a bit and pushed the patch to our integration branch, mozilla-inbound. From there it will automatically be merged to mozilla-central within the next day or so.

I'm also marking the bug as 'leave-open', because by default the merge to mozilla-central automatically closes the bug, but we want to land additional patches here.

In the mean time, you should feel free to get started on the next patch. Some ideas:

   - Change the callers of BreadthFirstSearch() to use lambdas for the condition.

   - Look at other loops over HitTestingTreeNode trees in APZCTreeManager.cpp,
     and see if any of them can use BreadthFirstSearch() or DepthFirstSearch(),
     or if not, what changes would have to made to the traversal algorithms so
     they could.

Comment 32

[Tim Stullich [:tstullich]]

Sounds good. I will try and get started on that as soon as I can.

Comment 33

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/9b9fc13b4e1b

Comment 34

[Botond Ballo [:botond]]

Hi Tim,

Have you had a chance to think about the next steps for this bug?

Comment 35

[Botond Ballo [:botond]]

I'm going to close this bug, and file a new bug for follow-up work.

Comment 36

[Botond Ballo [:botond]]

(In reply to Botond Ballo [:botond] from comment #35)
> I'm going to close this bug, and file a new bug for follow-up work.

I filed bug 1199798 for the follow-up work. Tim, if you're interesting in doing some of that work, please feel free to assign yourself to that bug. For now I'm leaving it unassigned to give someone else who might come along sooner a chance to work on it.