1226920 - Allow calling ForEachNode() with an action returning void

Status: RESOLVED FIXED

(Core :: Graphics: Layers, defect)

Description

[Botond Ballo [:botond]]

Currently, the ForEachNode() tree traversal algorithm takes an action that must return a value of type TraversalFlag. This is to support use cases where we want to traverse a tree but skip some subtrees; the algorithm checks the return value of the action, and skips the subtree rooted at the node on which the action was called if the return value is TraversalFlag::Skip.

However, we often want to traverse the entire tree, and it would be nice if in those cases, the action could just have a return type of void instead of TraversalFlag.

Comment 1

[Botond Ballo [:botond]]

Assigning to Kevin, as he expressed interest in this in bug 1199798 comment 40.

Comment 2

[Botond Ballo [:botond]]

One way to do this would be to have a second algorithm with a different name that expects an action that returns void.

However, it would be nicer if we just had one name (ForEachNode), and automatically figured out what is the correct thing to do based on the return type of the action.

We can accomplish this using the EnableIf facility [1]. This facility allows overloading a template function in such a way that different overloads are called for different classes of types (discriminated by a compile-time checked condition) even though the overloads otherwise have the same signature.

It's used like this:

  Let's say you had a template function Foo:

    template <typename T>
    ReturnType 
    Foo(T aParameter);

  You could split it into two overloads like so:

    template <typename T>
    typename EnableIf<condition1, ReturnType>::Type
    Foo(T aParameter);

    template <typename T>
    typename EnableIf<condition2, ReturnType>::Type
    Foo(T aParameter);

  where condition1 and condition2 are compile-time checked conditions
  involving T. If T satisfies condition1, the first overload is called.
  If T satisfies condition2, the second overload is called. (If T
  satisfies both conditions, the call is ambiguous. Generally you want
  the conditions to be mutually exclusive).

To see a real-life example use of EnableIf in Mozilla code, you can look at the various overloads of the ToJSValue() function [2].

We can apply this technique to ForEachNode, with the two conditions being "Action's return type is void" and "Action's return type is TraversalFlag".

To express these conditions, we can use the IsSame type trait [3]. IsSame<type1, type2>::value evaluates to true (at compile time) if type1 and type2 are the same type. In our case, we want to use "the return type of Action" as one of the types, and void (respectively, TraversalFlag), as the other.

To express "the return type of Action", we can use the decltype operator, which evaluates the type of any expression at compile time (without evaluating the expression at runtime). In our case, given that ForEachNode has parameters aAction which is an instance of Action, and aNode which is of the type Action takes as argument, we can write decltype(aAction(aNode)) to get the return type of Action.

There is one small wrinkle in this: the parameters (aAction and aRoot) aren't in scope yet when the return type is parsed in its usual position. To work around this, we can use a C++11 feature called "late-specified return types". Instead of writing the usual:

  ReturnType Function(parameters) { ... }

we can write:
  
  auto Function(parameters) -> ReturnType { ... }

Written this way, the parameters are now in scope when the return type is parsed, and so they can be used in the return type.

Having overloaded ForEachNode in this way, we just need to implement the two overloads. One option is to duplicate the implementation and just adjust the place where the action is called. Another option is to have the "returns void" implementation delegate to the "returns TraversalFlag" implementation by wrapping the incoming action into a lambda that calls it and then returns TraversalFlag::Continue. I'll leave it up to you which you prefer.

Hope this makes sense! If you have any questions, feel free to ask and I'm happy to clarify some more.

[1] https://dxr.mozilla.org/mozilla-central/rev/abbd213422a560f1180c4ec6e3bf4792c2ea81ba/mfbt/TypeTraits.h#1124
[2] https://dxr.mozilla.org/mozilla-central/rev/abbd213422a560f1180c4ec6e3bf4792c2ea81ba/dom/bindings/ToJSValue.h#142
[3] https://dxr.mozilla.org/mozilla-central/rev/abbd213422a560f1180c4ec6e3bf4792c2ea81ba/mfbt/TypeTraits.h#552

Comment 3

[Kevin Wern]

Attachment: Allow ForEachNode action to return void

I also added a test for a function returning void.  This is a really neat trick!

Comment 4

[Botond Ballo [:botond]]

Comment on attachment 8690651 [details] [diff] [review]
Allow ForEachNode action to return void

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

Looks good, thanks! (And thanks for adding a test!)

As a follow-up, could you change the lambdas in APZCTreeManager that always return TraversalFlag::Continue to return void instead?

Comment 5

[Kevin Wern]

Attachment: Refactor instances of ForEachNode that return only TraversalFlag::Continue

Comment 6

[Botond Ballo [:botond]]

Comment on attachment 8690904 [details] [diff] [review]
Refactor instances of ForEachNode that return only TraversalFlag::Continue

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

Thanks!

Comment 7

[Botond Ballo [:botond]]

Pushed both patches to Try:

https://treeherder.mozilla.org/#/jobs?repo=try&revision=e5bb8c298b35

Comment 8

[Botond Ballo [:botond]]

(In reply to Botond Ballo [:botond] from comment #7)
> https://treeherder.mozilla.org/#/jobs?repo=try&revision=e5bb8c298b35

Looks good! Landed on inbound.

Comment 9

[Pulsebot]

https://hg.mozilla.org/integration/mozilla-inbound/rev/6dcbb6dd88dc
https://hg.mozilla.org/integration/mozilla-inbound/rev/18a0a55c668d

Comment 10

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/6dcbb6dd88dc
https://hg.mozilla.org/mozilla-central/rev/18a0a55c668d