bugzilla.mozilla.org has resumed normal operation. Attachments prior to 2014 will be unavailable for a few days. This is tracked in Bug 1475801.
Please report any other irregularities here.

Allow calling ForEachNode() with an action returning void

RESOLVED FIXED in Firefox 45

Status

()

Core
Graphics: Layers
RESOLVED FIXED
3 years ago
3 years ago

People

(Reporter: botond, Assigned: Kevin Wern, Mentored)

Tracking

unspecified
mozilla45
Points:
---

Firefox Tracking Flags

(firefox45 fixed)

Details

Attachments

(2 attachments)

(Reporter)

Description

3 years ago
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.
(Reporter)

Comment 1

3 years ago
Assigning to Kevin, as he expressed interest in this in bug 1199798 comment 40.
Assignee: nobody → kevin.m.wern
Mentor: botond
(Reporter)

Comment 2

3 years ago
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
(Assignee)

Comment 3

3 years ago
Created attachment 8690651 [details] [diff] [review]
Allow ForEachNode action to return void

I also added a test for a function returning void.  This is a really neat trick!
Attachment #8690651 - Flags: review?(botond)
(Assignee)

Updated

3 years ago
Attachment #8690651 - Attachment description: Allow ForEachNode action to return NULL → Allow ForEachNode action to return void
(Reporter)

Comment 4

3 years ago
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?
Attachment #8690651 - Flags: review?(botond) → review+
(Assignee)

Comment 5

3 years ago
Created attachment 8690904 [details] [diff] [review]
Refactor instances of ForEachNode that return only TraversalFlag::Continue
Attachment #8690904 - Flags: review?(botond)
(Reporter)

Comment 6

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

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

Thanks!
Attachment #8690904 - Flags: review?(botond) → review+
(Reporter)

Comment 8

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

Looks good! Landed on inbound.

Comment 10

3 years ago
bugherder
https://hg.mozilla.org/mozilla-central/rev/6dcbb6dd88dc
https://hg.mozilla.org/mozilla-central/rev/18a0a55c668d
Status: NEW → RESOLVED
Last Resolved: 3 years ago
status-firefox45: --- → fixed
Resolution: --- → FIXED
Target Milestone: --- → mozilla45
You need to log in before you can comment on or make changes to this bug.