Closed Bug 1227224 Opened 4 years ago Closed 4 years ago

Use a tree traversal algorithm in APZCTreeManager::FindTargetNode() and GetAPZCAtPoint()

Categories

(Core :: Panning and Zooming, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla47
Tracking Status
firefox45 --- affected
firefox47 --- fixed

People

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

References

Details

Attachments

(1 file, 3 obsolete files)

These are two places in APZCTreeManager where we still use a manual loop to traverse a tree.
Assignee: nobody → kevin.m.wern
Hey, Botond. Both functions require a depth-first traversal with children visited in reverse.  I added functionality which does that (currently separate, but ideally I'd like to merge that with DepthFirstSearch and have a flag passed in to specify order), but GetAPZCAtPoint is making it difficult to keep the algorithm generic.

Basically, GetAPZCAtPoint has a few additional oddities:
- Children of nodes not meeting search criteria (the point is not in the clip or hitting a child layer) are skipped.
- The condition criteria is changed with each iteration (aHitTestingPoint is transformed, and a result flag is used).
- Multiple points can meet the correct criteria, but the deepest matching node should be returned.

The first I would probably solve using a flag like skipChildrenOnFalse, but the other two seem impossible to accommodate with how DepthFirstSearch is structured.  Because the search inherently eliminates previously searched nodes and can only change state in sequence (with capture clause variables), the conditions require contradicting traversal orders. The deepest-matching requirement would need post-order traversal to return the deepest matching node; the changing criteria requires pre-order traversal for correct transformation/casting of the search point from parent to child in each step.

Let me know what you think the best option is here.  I think if there is a correct way to transform the search point from the original to each node's layer without the interim transformations, that would make a solution possible.

Draft patch with the rest coming in a bit.
Flags: needinfo?(botond)
Add function DepthFirstSearchReverse, which traverses child nodes from
last to first. Create corresponding tests and refactor FindTargetNode
to use new function.

Review commit: https://reviewboard.mozilla.org/r/30241/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/30241/
Attachment #8706098 - Flags: review?(botond)
(In reply to Kevin Wern from comment #1)
> GetAPZCAtPoint is making it difficult to keep the algorithm generic.
> 
> Basically, GetAPZCAtPoint has a few additional oddities:
> - Children of nodes not meeting search criteria (the point is not in the
> clip or hitting a child layer) are skipped.
> - The condition criteria is changed with each iteration (aHitTestingPoint is
> transformed, and a result flag is used).
> - Multiple points can meet the correct criteria, but the deepest matching
> node should be returned.
> 
> The first I would probably solve using a flag like skipChildrenOnFalse, but
> the other two seem impossible to accommodate with how DepthFirstSearch is
> structured.  Because the search inherently eliminates previously searched
> nodes and can only change state in sequence (with capture clause variables),
> the conditions require contradicting traversal orders. The deepest-matching
> requirement would need post-order traversal to return the deepest matching
> node; the changing criteria requires pre-order traversal for correct
> transformation/casting of the search point from parent to child in each step.
> 
> Let me know what you think the best option is here.  I think if there is a
> correct way to transform the search point from the original to each node's
> layer without the interim transformations, that would make a solution
> possible.

You're right that this is a tricky case.

Here are some thoughts:

  - We already have an algorithm (ForEachNode) where the action invoked
    on each node can influence how the search proceeds (by returning a
    TraversalFlag). Currently we have two flags: 'Continue', which means
    "continue the traversal as normal", and 'Skip', which means "skip 
    the children of the current node". We can envision a third flag, 
    'Abort', which would mean "stop the traversal entirely".

  - With such an 'Abort' flag in place, a "search" algorithm just becomes
    a special case of a "traversal" algorithm: to do a search, you could
    invoke the traversal algorithm with an action that returns 'Abort'
    if a matching node is found, and saves the result node in a state
    variable (which can then be examined by the caller).

  - The problem of having to do something both before visiting the
    children, and after, is one we're likely to run into again from time
    to time. I think we can address it by having our traversal algorithm
    take two actions, one called before the recursion and one called 
    after. Pre-order and post-order traversals would then become
    special cases of this (pre-order would have an empty "after" action,
    while post-order would have an empty "before" action).

    Note that the two actions can share state. For example, if they're 
    both lambdas, they can both capture the same variable(s) by 
    reference. Alternatively, they can be two methods of the same class.

    If we do this, we could support whichever TraversalFlags make sense
    for either action: 'Continue', 'Skip', or 'Abort' for the "before"
    action, and 'Continue' or 'Abort' for the "after" action. 
    (Technically, 'Abort' for the "before" action is redundant, because
    it could return 'Skip', and save some state that causes the "after"
    action to return 'Abort', but it's probably convenient to let the
    "before" action return 'Abort' too.)

So, my concrete suggestions are:

  - Generalize ForEachNode() to take two actions as described above.
    For convenience, we can provide helper methods, perhaps called
    ForEachNodePreOrder() and ForEachNodePostPorder(), which just
    take one action, and delegate to ForEachNode() (using an empty
    action as the second action).

  - Express the traversal in GetAPZCAtPoint() in terms of the
    general (two-action) version of ForEachNode(). I think this
    should be possible.

  - (Optional) Express DepthFirstSearch() in terms of ForEachNode().
    We have some flexibility in which of the versions (PreOrder,
    PostOrder, general) have a corresponding DepthFirstSearch()
    version - I'll leave that up to you. If we write a two-action
    version (that delegates to the two-action ForEachNode()), we can
    use it it GetAPZCAtPoint() instead of using ForEachNode()
    directly.

Let me know what you think.
Flags: needinfo?(botond)
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

https://reviewboard.mozilla.org/r/30241/#review27127

This generally looks good, but GetTargetNode() needs a post-order traversal, while this implementation of DepthFirstSearchReverse() does a pre-order traversal.
Attachment #8706098 - Flags: review?(botond)
Regarding traversal order among siblings:

  - Recall that HitTestingTreeNode has GetLastChild/GetPrevSibling methods, 
    while the other trees we're looking to use these algorithms on have both 
    GetFirstChild/GetNextSibling and GetLastChild/GetPrevSibling methods.

  - I'd like to propose that the algorithms can only traverse siblings in the 
    order(s) provided by the accessor methods. That is, HitTestingTreeNodes 
    should only be traversed last-to-first, while for the other trees, we
    should have the option of last-to-first or first-to-last.

  - For the latter case, where we have both sets of accessors, I think we can 
    generalize over the two orders _outside_ of the algorithm implementation. 
    (I'm thinking here of having something like an "iterator", which provides 
    just one interface to the algorithm - say FirstChild/NextSibling - but
    depending on how you construct the iterator, that can map to either
    FirstChild/NextSibling or LastChild/PrevSibling on the underlying node).

  - Therefore, the algorithms only need to have one implementation when it 
    comes to traversal order among siblings. That implementation should be
    the recursive one, because this is what traverses the nodes in the order
    provided by the accessors. (As opposed to the stack-based implementation,
    which gives us the reverse of that order.)

  - As all our previous traversals were recursive loops, by definition they
    all used the order provided by the accessors, so having the algorithms
    do that will allow them to preserve the previous behaviour.

  - If we ever want to traverse HitTestingTreeNodes first-to-last,
    HitTestingTreeNode would need to expose GetFirstChild/GetNextSibling
    methods.

I think this approach would be a nice way to avoid a proliferation of too many variants of the algorithms (PostOrderForward, PostOrderReverse, etc.).
(In reply to Botond Ballo [:botond] from comment #5)
>   - For the latter case, where we have both sets of accessors, I think we can 
>     generalize over the two orders _outside_ of the algorithm implementation. 
>     (I'm thinking here of having something like an "iterator", which provides 
>     just one interface to the algorithm - say FirstChild/NextSibling - but
>     depending on how you construct the iterator, that can map to either
>     FirstChild/NextSibling or LastChild/PrevSibling on the underlying node).

To be clear, I'm not proposing implementing this iterator abstraction in this bug. I just brought it up to demonstrate how having the algorithms be recursive can be sufficient for all sibling-order needs.
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/30241/diff/1-2/
Attachment #8706098 - Attachment description: MozReview Request: Bug 1227224 - Create DepthFirstSearchReverse and refactor FindTargetNode r?botond → MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond
Attachment #8706098 - Flags: review?(botond)
Hey, Botond.  Sorry it took me a while to get to this.  I've been pretty busy, and this was a tricky patch as-is.

Anyway, a few comments on what you said:

> Express DepthFirstSearch() in terms of ForEachNode().
> We have some flexibility in which of the versions (PreOrder,
> PostOrder, general) have a corresponding DepthFirstSearch()
> version - I'll leave that up to you. If we write a two-action
> version (that delegates to the two-action ForEachNode()), we can
> use it it GetAPZCAtPoint() instead of using ForEachNode()
> directly.

I'd like to do this, but it seems pretty unintuitive to require the Traversal flags when using the search algorithms. My only idea to combat this, in this upcoming patch, is to do something like:

DepthFirstSeach(node, condition) {
    Node *result;
    ForEachNode(node,
        [&condition, &result] (Node *aNode)
        {
            if (condition(aNode)){
                result = aNode;
                TraversalFlag::Abort;
            }
            else {
                TraversalFlag::Continue;
            }
        }
    );
}

Which works effectively, as seen in the patch, but we lose the ability to skip in the abstraction.  I think it'd be fair, though, to require a user use ForEachNode directly to customize that.

>  - Therefore, the algorithms only need to have one implementation when it 
>    comes to traversal order among siblings. That implementation should be
>    the recursive one, because this is what traverses the nodes in the order
>    provided by the accessors. (As opposed to the stack-based implementation,
>    which gives us the reverse of that order.)
> 
>  - As all our previous traversals were recursive loops, by definition they
>    all used the order provided by the accessors, so having the algorithms
>    do that will allow them to preserve the previous behaviour.

There are implementations we'll need to change then, because all the depth-first traversal in TreeTraversal.h used the stack implementation.  I changed that in this patch, but I still have to look over all the instances where ForEachNode and DepthFirstSearch are called to see if it affects anything. If I remember correctly, nothing really cared about traversal order, with the exception of Clear methods that are still up in the air.

Also, the recursive implementation makes exiting after TraversalFlag::Abort is received a lot less friendly. Let me know what you think of those changes. There are a few wrappers and implementation changes I made to still respect the original ForEachNode callers.

The iterator abstraction sounds like a good idea. I don't know if there is a way to abstract away post-order vs pre-order, so we'll probably still need those.

Anyway, let me know what you think.
Sorry, a few amendments

(In reply to Kevin Wern from comment #8)
> DepthFirstSeach(node, condition) {
>     Node *result;
>     ForEachNode(node,
>         [&condition, &result] (Node *aNode)
>         {
>             if (condition(aNode)){
>                 result = aNode;
>                 TraversalFlag::Abort;
>             }
>             else {
>                 TraversalFlag::Continue;
>             }
>         }
>     );
> }

Should have a return statement at the end:
DepthFirstSeach(node, condition) {
    Node *result;
    ForEachNode(node,
        [&condition, &result] (Node *aNode)
        {
            if (condition(aNode)){
                result = aNode;
                TraversalFlag::Abort;
            }
            else {
                TraversalFlag::Continue;
            }
        }
    );
    return result;
}

> The iterator abstraction sounds like a good idea. I don't know if there is a
> way to abstract away post-order vs pre-order, so we'll probably still need
> those.

Should be "...we'll probably need distinct functions/flags for those."
Attachment #8706098 - Flags: review?(botond)
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

https://reviewboard.mozilla.org/r/30241/#review29007

Thanks, Kevin! This looks pretty good.

Due to the tricky nature of GetAPZCAtPoint(), I'd like :kats to have a look at the changes to that function as well. However, first please address the comments I've written, and then we'll ask him to look at the updated version.

::: gfx/layers/TreeTraversal.h:36
(Diff revision 2)
> +static auto ForEachNodeInternal(Node* aRoot, const PreAction& aPreAction, const PostAction& aPostAction, bool &abort) ->

You can put this 'bool' into the return value (by replacing the 'void' in the EnableIf with 'bool').

::: gfx/layers/TreeTraversal.h:60
(Diff revision 2)
> +    result = aPostAction(aRoot);

It's not obvious whether the post-action should be run if the pre-action returns TraversalFlag::Skip. Whatever choice we make should be documented clearly.

The current choice (not running it) is convenient for GetAPZCAtPoint(); we can keep it like this for now, and revisit this choice if it ends up being inconvenient for future call sites.

::: gfx/layers/TreeTraversal.h:96
(Diff revision 2)
> + * ForEachNode instances to be called externally. The first is for two actions

I think we can unify these with the ForEachNodeInternal versions:

  - For the 'void' version, they are already the same.

  - For the 'TraversalFlag' version, now that the
    'bool' is in the return value, we can just
    have it that way in the external (only) version.
    We can document that a return value of true means
    the traversal was aborted; some callers might
    find that information useful!

::: gfx/layers/TreeTraversal.h:122
(Diff revision 2)
> +auto ForEachNode(Node* aRoot, const PreAction& aPreAction) ->

Please state clearly in the comment that this does a pre-order traversal, and that a ForEachNodePostOrder function (which I suggested adding in a comment below) is available if a post-order traversal is desired.

::: gfx/layers/TreeTraversal.h:182
(Diff revision 2)
>    if (!aRoot) {

You can omit this check, as ForEachNode has it.

::: gfx/layers/TreeTraversal.h:189
(Diff revision 2)
> -         child;
> +      [&aCondition, &result](Node* aNode)

This code currently trips up a static analysis check that we have that prevents a lambda from capturing a raw pointer to a type that is reference counted.

This would be somewhat annoying to work around (we'd have to assume that Node is reference-counted, and make 'result' a RefPtr<Node>), but in a case like this where the variable is captured by reference,  the static analysis check doesn't actually have any value; I explain why in bug 1242789, which I filed to relax the check.

Assuming that bug gets fixed, we don't need to make any change here (but we do need to wait for that to land before we can land this).

::: gfx/layers/TreeTraversal.h:210
(Diff revision 2)
>    if (!aRoot) {

You can omit this.

::: gfx/layers/TreeTraversal.h:217
(Diff revision 2)
> -    Node* node = stack.top();
> +      [](Node* aNode){ return TraversalFlag::Continue; },

Might as well add ForEachNodePostOrder and use it here.

::: gfx/layers/apz/src/APZCTreeManager.cpp:1496
(Diff revision 2)
> -  RefPtr<HitTestingTreeNode> target = FindTargetNode(mRootNode, aGuid, aComparator);
> +  RefPtr<HitTestingTreeNode> target = RefPtr<HitTestingTreeNode>(DepthFirstSearchPostOrder(mRootNode.get(),

You shouldn't need this explicit constructor call. Just

  RefPtr<HitTestingTreeNode> target = DepthFirstSearchPostOrder(...)
  
should work.

::: gfx/layers/apz/src/APZCTreeManager.cpp:1643
(Diff revision 2)
> +  bool childrenTraversed;

No one sets this variable. I don't think we need it (since the post-action is not called if the pre-action returns TraversalFlag::Skip).

::: gfx/layers/apz/src/APZCTreeManager.cpp:1652
(Diff revision 2)
> -        aHitTestPoint.x, aHitTestPoint.y, node);
> +            copyHitTestPoint.x, copyHitTestPoint.y, aNode);

Several lines in this function do not compile if APZCTM_LOG is enabled.

::: gfx/layers/apz/src/APZCTreeManager.cpp:1659
(Diff revision 2)
> -      ParentLayerPoint childPoint = ViewAs<ParentLayerPixel>(hitTestPointForChildLayers.ref(),
> +	  ParentLayerPoint placeholder;

Please use spaces only for indentation, no tabs. If you use tabs, the code will appear differently to different people based on their tab width.

(Most editors can be configured to automatically insert spaces when the 'Tab' key is pressed. I'd encourage you to set that up for editing Mozilla code. If you're having trouble doing that for a particular editor, let me know which one and I can try to help you out.)

::: gfx/layers/apz/src/APZCTreeManager.cpp:1660
(Diff revision 2)
> -        PixelCastJustification::MovingDownToChildren);
> +	  hitTestPoints.push(placeholder);

Given that the post-action is not called if the pre-action returns TraversalFlag::Skip, why do you need to add a placeholder here?
(In reply to Botond Ballo [:botond] from comment #10)
> This code currently trips up a static analysis check that we have that
> prevents a lambda from capturing a raw pointer to a type that is reference
> counted.
> 
> This would be somewhat annoying to work around (we'd have to assume that
> Node is reference-counted, and make 'result' a RefPtr<Node>), but in a case
> like this where the variable is captured by reference,  the static analysis
> check doesn't actually have any value; I explain why in bug 1242789, which I
> filed to relax the check.
> 
> Assuming that bug gets fixed, we don't need to make any change here (but we
> do need to wait for that to land before we can land this).

Setting dependency to reflect this.
Depends on: 1242789
(In reply to Kevin Wern from comment #8)
> > Express DepthFirstSearch() in terms of ForEachNode().
> > We have some flexibility in which of the versions (PreOrder,
> > PostOrder, general) have a corresponding DepthFirstSearch()
> > version - I'll leave that up to you. If we write a two-action
> > version (that delegates to the two-action ForEachNode()), we can
> > use it it GetAPZCAtPoint() instead of using ForEachNode()
> > directly.
> 
> I'd like to do this, but it seems pretty unintuitive to require the
> Traversal flags when using the search algorithms. My only idea to combat
> this, in this upcoming patch, is to do something like:
> 
> DepthFirstSeach(node, condition) {
>     Node *result;
>     ForEachNode(node,
>         [&condition, &result] (Node *aNode)
>         {
>             if (condition(aNode)){
>                 result = aNode;
>                 TraversalFlag::Abort;
>             }
>             else {
>                 TraversalFlag::Continue;
>             }
>         }
>     );
> }
> 
> Which works effectively, as seen in the patch, but we lose the ability to
> skip in the abstraction.  I think it'd be fair, though, to require a user
> use ForEachNode directly to customize that.

Agreed. Feel free to leave this change for a subsequent patch, we're changing enough things in this one.

> 
> >  - Therefore, the algorithms only need to have one implementation when it 
> >    comes to traversal order among siblings. That implementation should be
> >    the recursive one, because this is what traverses the nodes in the order
> >    provided by the accessors. (As opposed to the stack-based implementation,
> >    which gives us the reverse of that order.)
> > 
> >  - As all our previous traversals were recursive loops, by definition they
> >    all used the order provided by the accessors, so having the algorithms
> >    do that will allow them to preserve the previous behaviour.
> 
> There are implementations we'll need to change then, because all the
> depth-first traversal in TreeTraversal.h used the stack implementation.  I
> changed that in this patch, but I still have to look over all the instances
> where ForEachNode and DepthFirstSearch are called to see if it affects
> anything. If I remember correctly, nothing really cared about traversal
> order, with the exception of Clear methods that are still up in the air.

I believe all existing call sites are fine, but please do look over them as well; it never hurts to have an extra pair of eyes on the code. Thanks!

> Also, the recursive implementation makes exiting after TraversalFlag::Abort
> is received a lot less friendly. Let me know what you think of those
> changes. There are a few wrappers and implementation changes I made to still
> respect the original ForEachNode callers.

I suggested changing the 'bool' out-parameter to a return value instead. I think the result is reasonably nice that way.

> The iterator abstraction sounds like a good idea. I don't know if there is a
> way to abstract away post-order vs pre-order, so we'll probably still need
> those.

I look at having two actions as being a generalization of post-order and pre-order; the actual post-order and pre-order functions are small wrappers around the two-action function. I think this is good enough.
https://reviewboard.mozilla.org/r/30241/#review29093

::: gfx/layers/apz/src/APZCTreeManager.cpp:1689
(Diff revision 2)
> +  AsyncPanZoomController* result = resultNode->GetNearestContainingApzcWithSameLayersId();

resultNode can be null here, causing this to crash.

We could add a null check, but I think even better would be to move these lines into the 'if (*aOutHitResult != HitNothing)' block below.
Mentor: botond
(In reply to Botond Ballo [:botond] from comment #11)
> (In reply to Botond Ballo [:botond] from comment #10)
> > This code currently trips up a static analysis check that we have that
> > prevents a lambda from capturing a raw pointer to a type that is reference
> > counted.
> > 
> > This would be somewhat annoying to work around (we'd have to assume that
> > Node is reference-counted, and make 'result' a RefPtr<Node>), but in a case
> > like this where the variable is captured by reference,  the static analysis
> > check doesn't actually have any value; I explain why in bug 1242789, which I
> > filed to relax the check.
> > 
> > Assuming that bug gets fixed, we don't need to make any change here (but we
> > do need to wait for that to land before we can land this).
> 
> Setting dependency to reflect this.

Things are looking good on this front!
Hey, I made the changes you mentioned, I just can't seem to push to reviewboard anymore.  I'm looking into the issue...
(In reply to Kevin Wern from comment #15)
> Hey, I made the changes you mentioned, I just can't seem to push to
> reviewboard anymore.  I'm looking into the issue...

This is a known issue - MozReview has been temporarily restricted to accepting pushes from people with Level 3 commit access only, due to technical difficulties (tracked by bug 1244835). 

Please feel free to export the commmit to a patch file and upload it as an attachment to the bug instead.
Attachment #8706098 - Attachment is obsolete: true
Attachment #8715649 - Flags: review?(botond)
Quick fix to ForEachNode logic (accidentally included PostAction in TraversalFlag::Continue branch)
Attachment #8715649 - Attachment is obsolete: true
Attachment #8715649 - Flags: review?(botond)
Attachment #8715659 - Flags: review?(botond)
Remove other instance of old copyHitTestPoint (sorry for microrevisions)
Attachment #8715659 - Attachment is obsolete: true
Attachment #8715659 - Flags: review?(botond)
Attachment #8715671 - Flags: review?(botond)
A few quick comments:

(a) Including the aPostAction in the TraversalFlag::Continue branch was a brackets mistake on my part. I think it makes more sense to think that only a node's children are omitted when TraversalFlag::Skip is returned.  This is why the placeholder code later on didn't make much sense.  I think doing it this way is a bit less confusing than considering that a node could be 'half' traversed when skipped.

(b) I tried to look up how to enable APZCTM_LOG but couldn't find anything.  I noticed the reason is that the variable names were wrong, so I'm 99.9% sure that is fixed--unless there is a second issue.  I had written that portion before I decided a stack was necessary for the HitTestPoints.
(In reply to Kevin Wern from comment #20)
> (b) I tried to look up how to enable APZCTM_LOG but couldn't find anything. 

Sorry, I should have mentioned that. You enable it by commenting out this line [1] and uncommenting the line below it.

> I noticed the reason is that the variable names were wrong, so I'm 99.9%
> sure that is fixed--unless there is a second issue.

Yep, it was just the names.

[1] https://dxr.mozilla.org/mozilla-central/rev/584870f1cbc5d060a57e147ce249f736956e2b62/gfx/layers/apz/src/APZCTreeManager.cpp#37
(In reply to Botond Ballo [:botond] from comment #21)
> > I noticed the reason is that the variable names were wrong, so I'm 99.9%
> > sure that is fixed--unless there is a second issue.
> 
> Yep, it was just the names.

However, some names are still incorrect: in the post-action, 'hitTestPointForChildLayers' and 'node' are not declared.
(In reply to Botond Ballo [:botond] from comment #22)
> (In reply to Botond Ballo [:botond] from comment #21)
> > > I noticed the reason is that the variable names were wrong, so I'm 99.9%
> > > sure that is fixed--unless there is a second issue.
> > 
> > Yep, it was just the names.
> 
> However, some names are still incorrect: in the post-action,
> 'hitTestPointForChildLayers' and 'node' are not declared.

Actually, 3 of the 4 APZCTM_LOG calls in GetAPZCAtPoint() still do not compile; please try enabling APZCTM_LOG as described in comment 21 and get them to compile. Thanks!
The patch also doesn't pass the APZ gtests: APZEventRegionsTester.HitRegionImmediateResponse crashes in debug mode due to the assertion in HitTestingTreeNode::HitTest firing.
(In reply to Botond Ballo [:botond] from comment #24)
> The patch also doesn't pass the APZ gtests:
> APZEventRegionsTester.HitRegionImmediateResponse crashes in debug mode due
> to the assertion in HitTestingTreeNode::HitTest firing.

The problem is that if in the pre-action IsOutsideClip() returned true, then in the post-action we don't want to do a hit-test at all. One of the nice features of not invoking the post-action if the pre-action returns TraversalFlag::Skip, is that it solves this problem.

This way, we have to use a flag for the pre-action to communicate to the post-action that it shouldn't do the hit test.
(In reply to Botond Ballo [:botond] from comment #25)
> (In reply to Botond Ballo [:botond] from comment #24)
> > The patch also doesn't pass the APZ gtests:
> > APZEventRegionsTester.HitRegionImmediateResponse crashes in debug mode due
> > to the assertion in HitTestingTreeNode::HitTest firing.
> 
> The problem is that if in the pre-action IsOutsideClip() returned true, then
> in the post-action we don't want to do a hit-test at all. One of the nice
> features of not invoking the post-action if the pre-action returns
> TraversalFlag::Skip, is that it solves this problem.
> 
> This way, we have to use a flag for the pre-action to communicate to the
> post-action that it shouldn't do the hit test.

Yeah, I'm thinking that I should roll back to what I had previously. Even though itt was a mistake originally, it does turn out better.  If the user wants to skip only child nodes, they can change the state of the post action or otherwise have it return the skip flag. It's just more flexible. I'll fix that (and all the log errors) in a bit.

And thanks for directing me to the log flag.  I made the mistake of trying to look through the wiki (or for command line flags) rather than the code itself...
(In reply to Botond Ballo [:botond] from comment #13)
> https://reviewboard.mozilla.org/r/30241/#review29093
> 
> ::: gfx/layers/apz/src/APZCTreeManager.cpp:1689
> (Diff revision 2)
> > +  AsyncPanZoomController* result = resultNode->GetNearestContainingApzcWithSameLayersId();
> 
> resultNode can be null here, causing this to crash.
> 
> We could add a null check, but I think even better would be to move these
> lines into the 'if (*aOutHitResult != HitNothing)' block below.

This has not been addressed in the updated patch.
Comment on attachment 8715671 [details] [diff] [review]
Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

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

I pointed out a few issues that need to be addressed in comment 23, comment 25, and comment 27. Otherwise this looks pretty good, thanks!

::: gfx/layers/TreeTraversal.h
@@ +171,5 @@
>   */
>  template <typename Node, typename Condition>
>  Node* DepthFirstSearch(Node* aRoot, const Condition& aCondition)
>  {
> +  Node *result = nullptr;

nit: Node*

@@ +180,5 @@
> +        if (aCondition(aNode)) {
> +          result = aNode;
> +          return TraversalFlag::Abort;
> +        }
> +        else {

nit: Since the 'if' returns, the "return TraversalFlag::Continue" can come directly after, it doesn't need an 'else'.

@@ +197,2 @@
>  {
> +  Node *result = nullptr;

(same here)

@@ +203,5 @@
> +        if (aCondition(aNode)) {
> +          result = aNode;
> +          return TraversalFlag::Abort;
> +        }
> +        else {

(and here)
Attachment #8715671 - Flags: review?(botond) → feedback+
(In reply to Kevin Wern from comment #26)
> I'll fix that (and all the log errors) in a bit.

Thanks! Note that MozReview submissions for all users are now back online.
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/30241/diff/2-3/
Attachment #8706098 - Attachment is obsolete: false
Attachment #8706098 - Flags: review?(botond)
Hey, just made the fixes you mentioned.  Passed all the gtests and build with APZCTM_LOG enabled.

Thanks for reviewing everything!
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

https://reviewboard.mozilla.org/r/30241/#review30663

Thanks, Kevin! Just a few minor comments remaining:

::: gfx/layers/TreeTraversal.h:30
(Diff revisions 2 - 3)
> - * Has an extra argument to trigger abort when TraversalFlag::Abort
> + * Returns true if traversal aborted, false if continued normally.

Please mention in the comment that if the pre-action returns TraversalFlag::Skip for a node, the post-action is not executed for that node.

::: gfx/layers/apz/src/APZCTreeManager.cpp:1657
(Diff revisions 2 - 3)
> +        APZCTM_LOG("Testing ParentLayer point %s (Layer %s) against node %p\n",

This log message is now a bit misleading, because it's separated from the HitTest call that it pertains to by the processing of the descendants of this node.

I would suggest modifying it like so:

  APZCTM_LOG("Transformed ParentLayer point %s to layer %s\n",
      Stringify(hitTestPoints.top()).c_str(),
      hitTestPointForChildLayers ? Stringify(hitTestPointForChildLayers.ref()).c_str() : "nil");

::: gfx/layers/apz/src/APZCTreeManager.cpp:1670
(Diff revisions 2 - 3)
>          HitTestResult hitResult = aNode->HitTest(hitTestPoints.top());

and then down here adding:

  APZCTM_LOG("Testing ParentLayer point %s against node %p\n",
      Stringify(hitTestPoints.top()).c_str(), aNode);
Attachment #8706098 - Flags: review?(botond)
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/30241/diff/3-4/
Attachment #8706098 - Flags: review?(botond)
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

https://reviewboard.mozilla.org/r/30241/#review30911

Looking, good thanks!
Attachment #8706098 - Flags: review?(botond) → review+
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

As mentioned in comment 10, let's ask :kats to have a look at the changes to GetAPZCAtPoint() as well, just due to the tricky nature of that code.
Attachment #8706098 - Flags: feedback?(bugmail.mozilla)
https://reviewboard.mozilla.org/r/30241/#review31063

::: gfx/layers/TreeTraversal.h:30
(Diff revision 4)
> - * |Node| should have methods GetLastChild() and GetPrevSibling().
> + * Returns true if traversal aborted, false if continued normally. If
> + * TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
> + * is not performed.

This comment seems inaccurate. If aPreAction returns Skip, it looks like the code will skip recursing on the children, but it will still do run aPostAction. This comment also disagrees with the comment on line 20 of this file.

::: gfx/layers/TreeTraversal.h:58
(Diff revision 4)
> +  
> +    result = aPostAction(aRoot);
> +   

Some trailing whitespace here and in other places in this file

::: gfx/layers/apz/src/APZCTreeManager.cpp:1652
(Diff revision 4)
> -      continue;
> +          return TraversalFlag::Skip;

This Skip return value changes the semantics of the code, if I'm not mistaken - the old code would "continue" here, which means it would skip both the recursion and the post-action. In the new code "Skip" will only skip the recursion, but still run the post-action. It seems like this code is assuming the "Skip" will skip the post-action but that's not what happens (see my previous comment).

::: gfx/layers/apz/src/APZCTreeManager.cpp:1684
(Diff revision 4)
> -      return result;
> +      MOZ_ASSERT(resultNode);

indent of this block should be 2 spaces, not 4
Attachment #8706098 - Flags: feedback?(bugmail.mozilla) → feedback-
Botond pointed out that I misread the code - sorry!

(In reply to Kartikaya Gupta (email:kats@mozilla.com) from comment #37)
> > - * |Node| should have methods GetLastChild() and GetPrevSibling().
> > + * Returns true if traversal aborted, false if continued normally. If
> > + * TraversalFlag::Skip is returned in |aPreAction|, then |aPostAction|
> > + * is not performed.
> 
> This comment seems inaccurate. If aPreAction returns Skip, it looks like the
> code will skip recursing on the children, but it will still do run
> aPostAction. This comment also disagrees with the comment on line 20 of this
> file.

Ignore this, but please update the comment on line 20 to clarify it will skip the post-action as well.

> ::: gfx/layers/apz/src/APZCTreeManager.cpp:1652
> (Diff revision 4)
> > -      continue;
> > +          return TraversalFlag::Skip;
> 
> This Skip return value changes the semantics of the code, if I'm not
> mistaken - the old code would "continue" here, which means it would skip
> both the recursion and the post-action. In the new code "Skip" will only
> skip the recursion, but still run the post-action. It seems like this code
> is assuming the "Skip" will skip the post-action but that's not what happens
> (see my previous comment).

Ignore this, the code is fine.
Attachment #8706098 - Flags: feedback- → feedback+
Comment on attachment 8706098 [details]
MozReview Request: Bug 1227224 - Create DepthFirstSearchPostOrder and extend ForEachNode functionality r?botond

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/30241/diff/4-5/
Attachment #8706098 - Flags: feedback+
(In reply to Botond Ballo [:botond] from comment #40)
> Try push:
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=8559964e13fe

The static analysis checks are failing because the patch hasn't been rebased on top of bug 1242789 yet.

Trying again with the patch rebased: https://treeherder.mozilla.org/#/jobs?repo=try&revision=fbf4eca704e1
(In reply to Botond Ballo [:botond] from comment #41)
> Trying again with the patch rebased:
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=fbf4eca704e1

Actually, might as well rebase to the latest m-c: https://treeherder.mozilla.org/#/jobs?repo=try&revision=ba3b0b7c56d8
(In reply to Botond Ballo [:botond] from comment #42)
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=ba3b0b7c56d8

Looking good!
https://hg.mozilla.org/mozilla-central/rev/bc4389602879
Status: NEW → RESOLVED
Closed: 4 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla47
Kevin, thanks for your great work here, and your patience in getting this to the finish line!

If you're interested in continuing to work on tree traversals, I think some of the most interesting bits (supporting different tree data structures) are still ahead of us in bug 1227231 and bug 1227233.
Duplicate of this bug: 1227223
You need to log in before you can comment on or make changes to this bug.