1227223 - Write a version of ForEachNode() that does a post-order traversal

Status: RESOLVED DUPLICATE of bug 1227224

(Core :: Panning and Zooming, defect)

Description

[Botond Ballo [:botond]]

The tree traversal algorithm ForEachNode() currently does a pre-order traversal of the tree, meaning that it visits the children of a node after the node itself.

Some traversal use cases, however, require a post-order traversal, where the children of the node are visited before the node itself. An example is APZCTreeManager::ClearTree(), where the action clears the links between a node and its children, making the children unreachable after a node has been visited.

We should add a version of ForEachNode() that does such a post-order traversal.

Comment 1

[Kevin Wern]

Attachment: Add ForEachNodePostOrder to TreeTraversal algorithms

Consider this a draft, because I'm not sure what the traversal flag behavior should be, seeing that the action should be performed on all a node's children before the node itself is ever evaluated.

Comment 2

[Kevin Wern]

Hey Botond, sorry I've been MIA for a while--I'm gonna start picking off these bugs.  A few questions:

- What should the TraversalFlag behavior be here?
- I don't have permission to assign myself to a bug, is it possible for me to get that permission?
- I'd like to start using MozReview. Is there a way to use a git repository or do I have to use Mercurial? I read that the latter is the case; however, I attempted to upload a diff where I was prompted and it didn't work (to the 'gecko' repository, got an error back about TreeTraversal.h not existing).  It seems there are a lot of variables as to why it isn't working, so I figured I'd just ask you about it.

Comment 3

[Botond Ballo [:botond]]

Thanks for your continued interest!

(In reply to Kevin Wern from comment #2)
> - I don't have permission to assign myself to a bug, is it possible for me
> to get that permission?

It's a general permission to edit the metadata fields of bugs, called 'editbugs'. I hooked you up with it. Use it wisely :)

Comment 4

[Botond Ballo [:botond]]

(In reply to Kevin Wern from comment #2)
> - I'd like to start using MozReview. Is there a way to use a git repository
> or do I have to use Mercurial? I read that the latter is the case; however,
> I attempted to upload a diff where I was prompted and it didn't work (to the
> 'gecko' repository, got an error back about TreeTraversal.h not existing). 
> It seems there are a lot of variables as to why it isn't working, so I
> figured I'd just ask you about it.

My understanding is MozReview does not work with git yet, so you need to use Mercurial to use it.

Instructions for using MozReview can be found here [2]. Please give those a try, and let me know if anything goes wrong!

[1] https://www.mozilla.org/en-US/about/governance/policies/commit/
[2] http://mozilla-version-control-tools.readthedocs.org/en/latest/mozreview-user.html

Comment 5

[Botond Ballo [:botond]]

(In reply to Botond Ballo [:botond] from comment #4)
> [1] https://www.mozilla.org/en-US/about/governance/policies/commit/

(Ignore that. I originally thought having Level 1 commit access is required to use MozReview but it's not. That said, you should feel free to apply for Level 1 commit access regardless; I'm happy to vouch for you.)

Comment 6

[Botond Ballo [:botond]]

Comment on attachment 8702412 [details] [diff] [review]
Add ForEachNodePostOrder to TreeTraversal algorithms

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

::: gfx/layers/TreeTraversal.h
@@ +157,5 @@
> +    return;
> +  }
> +
> +  std::stack<Node*> stack;
> +  std::stack<Node*> currentParentPath;

We can simplify the implementation significantly if we make the function recursive:

{
  if (!aRoot) {
    return;
  }

  for (Node* child = aRoot->GetLastChild();
       child;
       child = child->GetPrevSibling()) {
    ForEachNodePostOrder(child);
  }

  aAction(aRoot);
}

I think I would prefer that, to having two stacks.

::: gfx/layers/apz/src/APZCTreeManager.cpp
@@ +1313,3 @@
>    // 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.

Please adjust this comment.

@@ +1316,1 @@
>    ForEachNode(mRootNode.get(),

This should be ForEachNodePostOrder().

Comment 7

[Kevin Wern]

Attachment: 0001-Bug-1227223-Add-ForEachNodePostOrder-to-TreeTraversa.patch

Changed implementation, comments, and typo. Had to update test to expect last-to-first traversal instead of first-to-last.

Comment 8

[Kevin Wern]

(In reply to Botond Ballo [:botond] from comment #5)
> (In reply to Botond Ballo [:botond] from comment #4)
> > [1] https://www.mozilla.org/en-US/about/governance/policies/commit/
> 
> (Ignore that. I originally thought having Level 1 commit access is required
> to use MozReview but it's not. That said, you should feel free to apply for
> Level 1 commit access regardless; I'm happy to vouch for you.)

I filed bug 1236097 to apply for Level 1 commit access.

I noticed the editbug permission change too.  Thanks so much!

Comment 9

[Botond Ballo [:botond]]

Comment on attachment 8703217 [details] [diff] [review]
0001-Bug-1227223-Add-ForEachNodePostOrder-to-TreeTraversa.patch

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

Thanks! r+ with the added comment.

(In reply to Kevin Wern from comment #7)
> Changed implementation, comments, and typo. Had to update test to expect
> last-to-first traversal instead of first-to-last.

This is actually the order we want, given that the navigation methods exposed by the node are GetLastChild() and GetPrevSibling(). Later, when we use these algorithms to traverse trees that also expose GetFirstChild()/GetNextSibling() methods, we'll need to adjust these algorithms to allow specifying the order among siblings. We can deal with that when it comes up.

::: gfx/layers/TreeTraversal.h
@@ +150,5 @@
>    }
>  }
>  
> +template <typename Node, typename Action>
> +void ForEachNodePostOrder(Node* aRoot, const Action& aAction)

Please add a comment saying that this is similar to ForEachNode but does a post-order traversal, and amend the comment above ForEachNode to mention that it does a pre-order traversal.

Comment 10

[Botond Ballo [:botond]]

Comment on attachment 8703217 [details] [diff] [review]
0001-Bug-1227223-Add-ForEachNodePostOrder-to-TreeTraversa.patch

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

A Try push is showing gtests failing:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=2b63865cf1b1&selectedJob=14990310

Comment 11

[Botond Ballo [:botond]]

The problem is that HitTestingTreeNodes are still being leaked in APZCTreeManager::ClearTree().

Even though the children of a node are now destroyed before the parent, among the children, a node is destroyed before the previous node. By the time ForEachNodePostOrder() calls child->GetPrevSibling(), 'child' has already been destroyed, and thus its prev-sibling pointer cleared. Therefore, the previous sibling (and its siblings and children) are leaked.

Comment 12

[Botond Ballo [:botond]]

We could work around this by modifying the loop to call child->GetPrevSibling() and save the result, before recursing on 'child'. 

However, this is starting to feel like we're making tweaks to what is meant to be _generic_ algorithm, to cater to a particular use case (tearing down the tree as we traverse it).

As the vast majority of operations we perform on trees preserve the tree structure, I'm happy to say that preserving the tree structure is a requirement for using the algorithms in TreeTraversal.h; we can then keep ForEachNodePostOrder() as-is (and keep it around for future uses), but not use it in ClearTree().

Let me know what you think about this.

Comment 13

[Kevin Wern]

Attachment: Add ForEachNodePostOrder to TreeTraversal algorithms (ClearTree usage removed)

Comment changes, plus typo fix.

Comment 14

[Kevin Wern]

Whoops. I should have caught the leak possibility when I was reworking that logic.

On child traversal order:
> This is actually the order we want, given that the navigation methods exposed by the node are 
> GetLastChild() and GetPrevSibling(). Later, when we use these algorithms to traverse trees that also 
> expose GetFirstChild()/GetNextSibling() methods, we'll need to adjust these algorithms to allow 
> specifying the order among siblings. We can deal with that when it comes up.

The current depth-first traversals (DepthFirstSearch and ForEachNode) parse children first to last, because for each group of child nodes, the last node to be pushed is the first child, which is then operated on in the next iteration of the loop.  Are you saying that the other algorithms *should* reflect the ordering of ForEachNodePostOrder and BreadthFirstSearch (last to first)?  Because right now, that is not the case.  (I guess it might not matter that much, seeing that we are looking to be able to specify either eventually)

As for what to do for this error, I agree saving each node is not the best solution.  However, I'm not sure we should add this algorithm unless there is a probable or existing case where it can be useful with this restriction.  I'm not familiar enough with this code to know for sure.

If there isn't such a case, maybe we can revisit the stack implementation and see if it can be simplified (even the original solution would probably work for deletion) or figure out a way to visit each child node in reverse in recursive solution.  Like the save solution, the latter seems to be pushing the boundaries of 'generic,' though; on the other hand, the former might not be generic, but it at least reflects how some past algorithms traverse children.

For now, I attached a patch with the algorithm and test only.  Let me know what you think.

Comment 15

[Botond Ballo [:botond]]

I've thought about this some more, and here's my summary of the situation:

  - Recursive and stack-based implementations give rise to different
    orders of processing among siblings: 

     - In a recursive implementation, siblings are visited in the order 
       provided by the accessor (e.g. if using GetLastChild/GetPrevSibling, 
       they are visited last-to-first).

     - In a stack-based implementation, siblings are visited in reverse
       of the order provided by the accessor (e.g. if using GetLastChild/
       GetPrevSibling, they are visited first-to-last).

  - Most of our use cases so far do not care about the traversal order
    between siblings, but there is one (ClearTree()) that does.

Here's what I suggest:

  - Let's put this patch on hold for now, and leave ClearTree() as is.

  - As we go on to convert other code to use the traversal algorithms,
    (such as in bug 1227224, bug 1227231, and bug 1227233), let's keep
    an eye out for whether those places care about the traversal order
    between siblings. If we some that do, we'll revise our algorithms
    to allow specifying that order, and if we do that, we can come back
    to ClearTree() and update it.

Kevin, how does that sound?

Comment 16

[Kevin Wern]

Makes sense to me.  I'll work on those three.

Comment 17

[Botond Ballo [:botond]]

Comment on attachment 8703496 [details] [diff] [review]
Add ForEachNodePostOrder to TreeTraversal algorithms (ClearTree usage removed)

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

Clearing review flag for now, until we revisit this patch.

Comment 18

[Botond Ballo [:botond]]

Having fixed bug 1227224, here are my updated thoughts on this bug:

  - We have added a post-order version of ForEachNode in bug 1227224.

  - Given the direction suggested in bug 1227224 comment 5, where we
    only support traversing siblings in the order provided by the node
    accessors (so for HitTestingTreeNode, only last -> first),
    ClearTree() is not a good fit for our algorithms, so we should
    leave it as is.

Kevin, let me know if this sounds reasonable to you.

Comment 19

[Kevin Wern]

Sounds good.  Seeing we already created ForEachNodePostOrder in bug 1227224, we don't need anything in my patch anymore.

Maybe there are more potential call sites for post-order traversal, but I think that's outside the scope of this bug.

Comment 20

[Botond Ballo [:botond]]

(In reply to Kevin Wern from comment #19)
> Sounds good.  Seeing we already created ForEachNodePostOrder in bug 1227224,
> we don't need anything in my patch anymore.

Cool! I'm going to close this as a dupe of bug 1227224, then.

> Maybe there are more potential call sites for post-order traversal, but I
> think that's outside the scope of this bug.

I think we've now converted all loops over the hit testing tree to use the algorithms (except that in ClearTree() we only do the gathering in the algorithm, not the actual clearing).

When we start converting loops over other data structures (Layer tree, LayerMetrics tree), we'll probably encounter use cases for post-order traversal, and we can convert those then.