Bug 1171312 introduced some basic generic tree traversal algorithms for use in Layers/APZ code. There is a lot of room to extend the algorithms and make them more general, as described in bug 1171312 comment 3. This would make a good mentored bug for someone who has previous experience with C++ templates.

Hey, Botond. I'd be interested in taking on this bug. I read through the previous comment thread, and I'm going to look into the two points you mentioned in Bug 1171312 comment 31. Is there anything else I should know to bring myself up-to-date?

(In reply to kevin.m.wern from comment #1) > Hey, Botond. > > I'd be interested in taking on this bug. Cool! I assigned the bug to you. > I read through the previous > comment thread, and I'm going to look into the two points you mentioned in > Bug 1171312 comment 31. Is there anything else I should know to bring > myself up-to-date? The first suggestion in that comment (change the callers of BreadthFirstSearch() to use lambdas) was already done in bug 1201277. The second one (try to transition other loops over the hit testing tree in APZCTreeManager to use the generic traversal algorithm) is probably a good starting point. My only other advice is to keep in mind the bigger picture described in bug 1171312 comment 3 (with clarifications in bug 1171312 comment 10), but it sounds like you already read all that :)

kevin.m.wern are you still actively working on this? If not I would like the opportunity to work on it and would appreciate if someone could assign me to it.

Hey, sorry, I'm still actively working. I got kinda busy for a bit.

I added two functions. A few things that I'm not sure of: - With ApplyChangeToAllNodes, passing an array into the context of the function can allow it to act as an aggregator as well as a mutator. I'm not sure if that is okay or if there should be an explicit split in functionality there. - ApplyChangeToAllNodesInSubtree was useful really for only one function (), I'm not sure if it's too narrow of a situation. If that's the case, maybe the two functions could be combined into a single function with an optional condition. - I changed the previous to functions to not return const pointers, as in this case I feel the object calling the functions owns the node anyway and sometimes wants to mutate the result, although in all honesty I've never thought of the convention outside of a class. Maybe we can overload the functions if we feel it's necessary. Let me know what you think or if there's anything else I can add.

Just looked over my comment and wanted to clarify a few things: > With ApplyChangeToAllNodes, passing an array into the context of the function can allow it to act as an aggregator as well as a mutator. By "the function," I mean the lambda function that is passed in as an argument; by context, I mean the capture clause. > ApplyChangeToAllNodesInSubtree was useful really for only one function () I was going to look up the name of the function and insert it at the parens there. I was referring to UpdateZoomConstraints > I changed the previous to functions Should be "two functions". I hope you got the gist of what I was saying anyway, but I thought messing up some of the details might make it confusing.

Thanks, Kevin! I'm at a conference this week and probably won't have time to look at it while I'm here, but I'll definitely look at it next week.

Comment on attachment 8675612 [details] [diff] [review] APZ tree traversal generalizations By the way, the convention for using flags to request a review is to set the review flag to '?', and then enter the email of the reviewer. The reviewer then sets the flag to '+' (or '-') after reviewing the patch. There's also no need to needinfo the reviewer in this case.

Comment on attachment 8675612 [details] [diff] [review] APZ tree traversal generalizations Review of attachment 8675612 [details] [diff] [review]: ----------------------------------------------------------------- I haven't looked at ApplyChangeToAllNodeSubtreesWithCondition and its call site yet, but I've looked at the rest and it generally looks good! A few comments on code style that apply throughout the patch: - For variables of pointer or reference type, the convention is to place the * or & goes beside the type name, not the variable name. - When a statement spans multiple lines, the convention is to indent subsequent lines by two levels of indentation (that is, four spaces) relative to the first line. That means that passing a lambda looks like this: Function(arg1, arg2, [captures](args) // four spaces relative to previous line { body }); I also realized there's a pre-existing difference between the traversal done by the functions in TreeTraversal.h and the traversal done by the manual loops in APZCTreeManager.cpp (the latter handles the case where the root node has siblings). I filed bug 1218618 for that; we'll need to address it before transitioning over more call sites. I'll review the rest of the patch tomorrow. ::: gfx/layers/TreeTraversal.h @@ +20,5 @@ > * > * |Node| should have methods GetLastChild() and GetPrevSibling(). > */ > template <typename Node, typename Condition> > +Node* BreadthFirstSearch(Node* aRoot, const Condition& aCondition) We may at some point need to call this function with a pointer to a const node (e.g. because we're in a function where that's what we have), but that might just work (as the function will be instantiated with e.g. 'Node = const HitTestingTreeNode'). @@ +81,5 @@ > return nullptr; > } > > +template <typename Node, typename Action> > +void ApplyChangeToAllNodes(Node *aRoot, const Action &aAction) I'd call this function ForEachNode. This terminology is consistent with the standard library algorithm std::for_each(), which takes a pair of iterators denoting a range of elements, and a function, and calls the function for each element in the range. Also, please add a comment describing what this function does, similar to BreadthFirstSearch and DepthFirstSearch. ::: gfx/layers/apz/src/APZCTreeManager.cpp @@ +169,5 @@ > + nsTArray<nsRefPtr<HitTestingTreeNode>> *nodesToDestroy = &state.mNodesToDestroy; > + ApplyChangeToAllNodes(mRootNode.get(), > + [nodesToDestroy](HitTestingTreeNode *aNode) > + { > + if (aNode) { You don't need to check that the node is not null: ApplyChangeToAllNodes() will not call the action on null nodes. @@ +1239,4 @@ > } > > void > +APZCTreeManager::FlushRepaints(HitTestingTreeNode* aNode) As this function is no longer recursive and only has one caller, just inline it into FlushRepaintsToClearScreemToGeckoTransform(). @@ +1254,4 @@ > } > > void > +APZCTreeManager::FlushPendingRepaint(HitTestingTreeNode* aNode, uint64_t aLayersId) Likewise, inline this into FlushApzRepaints(). @@ +1638,5 @@ > { > mTreeLock.AssertCurrentThreadOwns(); > > + return DepthFirstSearch(aNode, > + [aDragMetrics](HitTestingTreeNode *aNode) { Capture |aDragMetrics| by reference so we don't copy it.

Comment on attachment 8675612 [details] [diff] [review] APZ tree traversal generalizations Review of attachment 8675612 [details] [diff] [review]: ----------------------------------------------------------------- ::: gfx/layers/TreeTraversal.h @@ +105,5 @@ > + } > +} > + > +template <typename Node, typename Action, typename Condition> > +void ApplyChangeToAllNodeSubtreesWithCondition(Node *aRoot, const Action &aAction, const Condition &aCondition) I think we can simplify this function by combining the action and the condition into a single function, which indicates whether or not traversal should continue into a subtree via its return value. For example, we could have an enumeration like the following: enum class TraversalFlag { Skip, Continue }; and require that the function return a value of this type. If the function return TraversalFlag::Skip, we do not recurse into the subtree rooted at that node, otherwise we do. I'm also going to suggest that, for now, we combine ApplyChangeToAllNodes (which I've recommended renaming to ForEachNode) and this function into one, so that even call sites that never want to skip a subtree pass in a lambda that just always returns TraversalFlag::Continue. (As a follow-up we might be able to do some template magic to allow lambdas that don't return anything, and interpret them as if they always returned TraversalFlag::Continue, but let's keep things simple for now.) What do you think?

(In reply to Botond Ballo [:botond] from comment #9) > I also realized there's a pre-existing difference between the traversal done > by the functions in TreeTraversal.h and the traversal done by the manual > loops in APZCTreeManager.cpp (the latter handles the case where the root > node has siblings). I filed bug 1218618 for that; we'll need to address it > before transitioning over more call sites. Based on the discussion in that bug, we can go ahead and transition call sites to the tree traversal algorithms that don't handle the case where the root node has siblings, because trees structured like that no longer arise to begin with.

I made all the changes you mentioned. I like the TraversalFlag as a solution, but in the comment for ApplyChangesForEachNode, I clarify the resulting behavior because in some cases the user might want to exclude the node which results in a TraversalFlag::Skip in addition to its children. Also, for future reference, what would be the best way to test these and other APZ changes? I've been using the mochitests mainly.

Comment on attachment 8681675 [details] [diff] [review] APZ tree traversal generalizations (revised with TraversalFlag) Review of attachment 8681675 [details] [diff] [review]: ----------------------------------------------------------------- Thanks, Kevin, this is turning out to be really neat! Just a few minor comments remaining. ::: gfx/layers/TreeTraversal.h @@ +13,4 @@ > #include <queue> > #include <stack> > > +enum class TraversalFlag { Skip, Continue }; Please add a comment documenting what the two values mean. @@ +95,5 @@ > + * skip the node itself, the logic returning TraversalFlag::Skip should be > + * performed before the node is manipulated in any way. > + */ > +template <typename Node, typename Action> > +void ApplyChangeForEachNode(Node* aRoot, const Action& aAction) I think just "ForEachNode" gets the point across. ::: gfx/layers/apz/src/APZCTreeManager.cpp @@ +166,4 @@ > // we are sure that the layer was removed and not just transplanted elsewhere. Doing that > // as part of a recursive tree walk is hard and so maintaining a list and removing > // APZCs that are still alive is much simpler. > + nsTArray<nsRefPtr<HitTestingTreeNode>>* nodesToDestroy = &state.mNodesToDestroy; You can avoid introducing this variable by having the lambda capture |state| by reference. @@ +167,5 @@ > // as part of a recursive tree walk is hard and so maintaining a list and removing > // APZCs that are still alive is much simpler. > + nsTArray<nsRefPtr<HitTestingTreeNode>>* nodesToDestroy = &state.mNodesToDestroy; > + ApplyChangeForEachNode(mRootNode.get(), > + [nodesToDestroy] (HitTestingTreeNode* aNode) -> TraversalFlag For lambdas with a single return statement, the compiler can deduce the return type without having to declare it here. This applies to several of the other lambdas as well. @@ +1203,4 @@ > mZoomConstraints.erase(aGuid); > } > if (node && aConstraints) { > + mTreeLock.AssertCurrentThreadOwns(); You can omit this line, as the lock is acquired at the top of this function. @@ +1204,5 @@ > } > if (node && aConstraints) { > + mTreeLock.AssertCurrentThreadOwns(); > + ApplyChangeForEachNode(node.get(), > + [aConstraints, this](HitTestingTreeNode* aNode) -> TraversalFlag Indentation, and capture aConstraints by reference. @@ +1209,5 @@ > + { > + AsyncPanZoomController* childApzc = aNode->GetApzc(); > + if (childApzc != NULL && (childApzc->HasNoParentWithSameLayersId() > + || this->mZoomConstraints.find(childApzc->GetGuid()) != this->mZoomConstraints.end())) { > + return TraversalFlag::Skip; You can leave this as originally structured, and preserve the comment: if (AsyncPanZoomController* childApzc = aNode->GetApzc()) { // We can have subtrees with their own zoom constraints or separate layers // id - leave those alone. if (childApzc->HasNoParentWithSameLayersId() || this->mZoomConstraints.find(childApzc->GetGuid()) != this->mZoomConstraints.end()) { return TraversalFlag::Skip; } } @@ +1626,4 @@ > { > mTreeLock.AssertCurrentThreadOwns(); > > + return DepthFirstSearch(aNode, As this function is no longer recursive, we can inline it into the caller (the other overload of FindScrollNode()). @@ +1626,5 @@ > { > mTreeLock.AssertCurrentThreadOwns(); > > + return DepthFirstSearch(aNode, > + [&aDragMetrics](HitTestingTreeNode* aNode) { Indentation

(In reply to kevin.m.wern from comment #13) > Also, for future reference, what would be the best way to test these and > other APZ changes? I've been using the mochitests mainly. These changes have some indirect test coverage in the form of the APZ gtests [1], which exercise various parts of APZ code including APZCTreeManager. To run the gtests, run './mach gtest' to run all of them, or './mach gtest <testname>' (e.g. './mach gtest APZHitTestingTester.HitTesting1') to run one. It might make sense to write some gtests for the tree traversal algorithms directly. Such tests would declare a simple tree data structure with the required methods (GetPrevSibling() and such), create some example trees, call the algorithms on them, and then assert that the right nodes were visited in the right order. If you think you might be interested in writing some tests like this, let me know and I can give some more specific guidance. [1] https://dxr.mozilla.org/mozilla-central/rev/96377bdbcdf3e444a22aeaa677da696243b00d98/gfx/layers/apz/test/gtest/TestAsyncPanZoomController.cpp

I'd definitely be interested in writing TreeTraversal tests. Whatever guidance you could give in this respect would be appreciated.

Comment on attachment 8683018 [details] [diff] [review] APZ tree traversal generalizations (revised with comments, name change, etc.) Review of attachment 8683018 [details] [diff] [review]: ----------------------------------------------------------------- Looks great, thanks! I'll fire off a Try run.

(In reply to Botond Ballo [:botond] from comment #18) > I'll fire off a Try run. https://treeherder.mozilla.org/#/jobs?repo=try&revision=434a712af7b6

(In reply to kevin.m.wern from comment #17) > I'd definitely be interested in writing TreeTraversal tests. Whatever > guidance you could give in this respect would be appreciated. Here's what I would suggest doing: - Add a new file gfx/tests/gtest/TestTreeTraversal.cpp. - Add the new file to the list of files in gfx/tests/gtest/moz.build, in the first UNIFIED_SOURCES array. - In TestTreeTraversal.cpp, write some gtests that do what I described in comment 15. You can look at an existing gtest file like TestRegion.cpp to see what to include, and what a test case looks like, and such. - Try to run your tests and see if they pass. As an example, if you have a test declared like so: TEST(TreeTraversal, DepthFirstSearch) { ... } you would run it like so: ./mach gtest TreeTraversal.DepthFirstSearch Here, "TreeTraversal" is a name you pick for your group of tests, and "DepthFirstSearch" is the name of a specific test. You can run all tests in the group "TreeTraversal" like so: ./mach gtest 'TreeTraversal.*' (The single quotes are important, otherwise the shell tries to expand the *) Let me know if you run into any issues, or would like some more details.

Comment on attachment 8683018 [details] [diff] [review] APZ tree traversal generalizations (revised with comments, name change, etc.) Review of attachment 8683018 [details] [diff] [review]: ----------------------------------------------------------------- (In reply to Botond Ballo [:botond] from comment #19) > (In reply to Botond Ballo [:botond] from comment #18) > > I'll fire off a Try run. > > https://treeherder.mozilla.org/#/jobs?repo=try&revision=434a712af7b6 The Try run is showing that the changes introduce some leaks of HitTestingTreeNode and related objects. We need to fix this before we can land this patch.

(In reply to Botond Ballo [:botond] from comment #21) > The Try run is showing that the changes introduce some leaks of > HitTestingTreeNode and related objects. We need to fix this before we can > land this patch. I bisected the changes in the patch, and found that the leak is caused by the change to ClearTree(). We went from collecting all the nodes into a list, and then calling Destroy() on each node, to calling Destroy() as we're walking the tree. The problem is that Destroy() clears the mPrevSibling and mLastChild pointers of the node, and ForEachNode() calls the action (which calls Destroy()) before walking the node's children, so we end up only destroying the root node. Basically, we've run into a case where it matters whether the children of a node are visited before the node itself ("post-order traversal") or after the node ("pre-order traversal"). ForEachNode() currently does pre-order, but this particular call site needs post-order. For now, I would recommend leaving ForEachNode() unchanged, and changing ClearTree() to collect the nodes into a list (it can still use ForEachNode() for that) and then destroy each node, the way it was doing before. We can then consider adding a post-order version of ForEachNode() as part of the follow-up work.

I'll give the testing stuff a shot, as well.

Comment on attachment 8683620 [details] [diff] [review] APZ tree traversal generalizations (reverted some ClearTree logic) Review of attachment 8683620 [details] [diff] [review]: ----------------------------------------------------------------- Thanks! New Try run: https://treeherder.mozilla.org/#/jobs?repo=try&revision=5b28079ee485 ::: gfx/layers/apz/src/APZCTreeManager.cpp @@ +1281,2 @@ > nsTArray<nsRefPtr<HitTestingTreeNode>> nodesToDestroy; > + ForEachNode(mRootNode.get(), Please add a comment saying that we can't call Destroy() in the action of ForEachNode() because ForEachNode() does a pre-order traversal and Destroy() clears the node's pointers to children.

(In reply to Botond Ballo [:botond] from comment #25) > New Try run: > https://treeherder.mozilla.org/#/jobs?repo=try&revision=5b28079ee485 Whoops, I rebased that incorrectly (nsRefPtr got renamed to RefPtr since we started on this). Let's Try that again: https://treeherder.mozilla.org/#/jobs?repo=try&revision=5b28079ee485

Comment on attachment 8683620 [details] [diff] [review] APZ tree traversal generalizations (reverted some ClearTree logic) Review of attachment 8683620 [details] [diff] [review]: ----------------------------------------------------------------- > https://treeherder.mozilla.org/#/jobs?repo=try&revision=5b28079ee485 Looks good! I'll add the comment I requested in comment 25 locally and land the patch.

Marking bug as leave-open as we plan to do some follow-up work in this bug (tests, and possibly further extensions to and adding more uses of the algorithms).

I had to move <queue> and <stack> out of the namespace scope to get TreeTraversal.h properly included in the tests. Before this change, including TreeTraversal.h also affected other std namespace usages that were not linked to the global scope (some instances of std::string).

Comment on attachment 8684883 [details] [diff] [review] Tests for tree traversal algorithms Review of attachment 8684883 [details] [diff] [review]: ----------------------------------------------------------------- ::: gfx/layers/TreeTraversal.h @@ +36,4 @@ > return nullptr; > } > > + ::std::queue<Node*> queue; Did you need to change |std| to |::std| to fix a compiler error (after moving the #includes to global scope), or is this just a stylistic choice? ::: gfx/tests/gtest/moz.build @@ +28,5 @@ > # Test works but it doesn't assert anything > #'gfxTextRunPerfTest.cpp', > # Bug 1179287 - PGO bustage on Linux > #'TestTiledLayerBuffer.cpp', > + 'TestVsync.cpp' Please leave the terminating comma. The moz.build syntax allows it, and we like to use it so a new addition at the end doesn't require modifying the previous line, keeping the output of |hg blame| neater.

Comment on attachment 8684883 [details] [diff] [review] Tests for tree traversal algorithms Review of attachment 8684883 [details] [diff] [review]: ----------------------------------------------------------------- Great work, Kevin! This is a nice test suite. Just a few comments: ::: gfx/tests/gtest/TestTreeTraversal.cpp @@ +22,5 @@ > + int GetActualTraversalRank(); > + T GetType(); > + private: > + TestNode* mPreviousNode; > + TestNode* mLastChildNode; Currently you're not deleting the nodes you create anywhere. I would suggest making these fields (and also the local variables in your test functions) have type RefPtr<TestNode>, so they will be deleted automatically when the test finishes. @@ +39,5 @@ > +{ > +} > + > +template <class T> > +TestNode<T>::TestNode(T aType) : You can eliminate this constructor by making the |aExpectedTraversalRank| parameter of the other constructor have a default argument of -1. @@ +123,5 @@ > + if (i == expectedNeedleTraversalRank) { > + needleNode = new SearchTestNode(SearchNodeType::Needle, i); > + nodeList.push_back(needleNode); > + } > + else if (i < expectedNeedleTraversalRank) { Formatting nit: 'else' and 'else if' go on the same line as the closing brace of the previous 'if'. @@ +153,5 @@ > + > + for (size_t i = 0; i < nodeList.size(); i++) > + { > + ASSERT_EQ(nodeList[i]->GetExpectedTraversalRank(), > + nodeList[i]->GetActualTraversalRank()) nit: indent subsequent lines of the assert by two levels (four spaces) @@ +207,5 @@ > + nodeList[7]->AddChild(nodeList[8]); > + nodeList[7]->AddChild(nodeList[9]); > + > + > + SearchTestNode *foundNode = DepthFirstSearch(root, nit: SearchTestNode* foundNode @@ +217,5 @@ > + }); > + > + for (int i = 0; i < 10; i++) > + { > + if (i < visitCount) { This condition should always be true, as visitCount should be 10 after the search. (You can assert this before the loop.)

I decided to remove the global :: from std::queue, et al. When I originally did a grep search, I saw other instances where the ::std convention was used. It wasn't required to get the tests to run. Additionally, the visitCount < 10 was an artifact from when I was writing the tests. I removed it from other loops but forgot that one. I don't think there is really a need for it to be asserted outside the loop. Let me know what you think.

Comment on attachment 8687547 [details] [diff] [review] Create tests for TreeTraversal.h (revised) Review of attachment 8687547 [details] [diff] [review]: ----------------------------------------------------------------- Thanks! I had to mark the TestNode constructor as 'explicit' to appease the static analysis plugin. Try push with that change: https://treeherder.mozilla.org/#/jobs?repo=try&revision=ae5654fadea6

(In reply to Botond Ballo [:botond] from comment #35) > Try push with that change: > https://treeherder.mozilla.org/#/jobs?repo=try&revision=ae5654fadea6 Looks good, landed on inbound.

Kevin, I just wanted to say again, thanks for doing some really great work here! Some people have already started to use the tree traversal algorithms in new code (e.g. see the part 3 patch in bug 1223928). If you're interested in working on extending the tree traversal algorithms further, there are several directions we can explore: - Removing the requirement that the action passed to ForEachNode() return TraversalFlag::Continue if it wants to traverse the entire tree. This can be accomplished with a bit of template magic. - Writing a version of ForEachNode() that does a post-order traversal and using it in APZCTreeManager::ClearTree(). - Transitioning some of the remaining loops over trees in APZCTreeManager (like the ones in FindTargetNode() and GetAPZCAtPoint()) to use the traversal algorithms. - Transitioning some of the loops over Layer trees (such as the ones mentioned in bug 1171312 comment 3) to use the traversal algorithms, extending the algorithms as necessary to support this. - Transitioning some of the loops over LayerMetrics trees (such as the ones mentioned in bug 1171312 comment 3) to use the traversal algorithms, extending the algorithms as necessary to support this. This is probably the trickiest bit, as the LayerMetrics loops are "by value" instead of "by pointer", and so we'd have to employ some tricks to generalize over that (I mention the "traits" technique that can be used for this in bug 1171312 comment 10). If any of these sound interesting, let me know and we can discuss it further.

I'd be interested in tackling the traversal action change.

Whoops, didn't mean to set the needinfo flag.

(In reply to kevin.m.wern from comment #40) > I'd be interested in tackling the traversal action change. Sounds good! I'm going to file a new bug for it, so we don't put too many things into one bug.

I'm closing this bug as fixed. I filed a meta bug, bug 1226919, to track all work on the tree traversal algorithms; further work will happen in new bugs hanging off of that one.

(In reply to Botond Ballo [:botond] from comment #42) > (In reply to kevin.m.wern from comment #40) > > I'd be interested in tackling the traversal action change. > > Sounds good! I'm going to file a new bug for it, so we don't put too many > things into one bug. I filed bug 1226920 for this. I'll post more details there.

I also filed bugs for the remaining items in comment 39 (bug 1227223, bug 1227224, bug 1227231, bug 1227233). Kevin, if you're interested in any of them, feel free to assign yourself to one and we can discuss it more there.