Bug 78588 – Focus navigation should traverse nodes in reified DOM tree order.

• Component: DOM
• Status: RESOLVED FIXED

[Hayato Ito]

The spec is here:
 https://dvcs.w3.org/hg/webcomponents/raw-file/tip/spec/shadow/index.html#focus-navigation

[Hayato Ito]

Created attachment 132994 [details]
wip. depends on reified tree traversal APIs.

[Hayato Ito]

I did a micro benchmark using the DOM tree included the newly added LayoutTest for Focus navigation.

The result is:

Before this patch:
Pressing Tab (or Shift-Tab) in 10000 times.
 took 3837.2ms. navigateFocusFoward
 took 4641.6s. navigateFocusBackward


After this patch:
Pressing Tab (or Shift-Tab) in 10000 times.
 took 4614.4ms. navigateFocusFoward
 took 5403.8ms. navigateFocusBackward

It becomes 1.2 times slower.
I guess the main reason is ReifiedTreeTraversal APIs (See https://bugs.webkit.org/show_bug.cgi?id=79197#c33).

It might be unfair to compare before/after since the example DOM tree uses a lot of ShadowHosts.

Since FocusNavigation is only invoked by user's interactive action, pressing <tab> key, we don't have to worry about its performance too much.

[Hayato Ito]

Created attachment 133988 [details]
Shadow DOM navigation

[Hayato Ito]

It seems I've removed trailing white spaces accidentally from some files.
If it is not desired, I am happy to recover trailing white spaces.

[Dimitri Glazkov (Google)]

Comment on attachment 133988 [details]
Shadow DOM navigation

View in context: https://bugs.webkit.org/attachment.cgi?id=133988&action=review

My head hurts from reviewing this code. I need to take a break. I promise I'll give it another stab tomorrow.

I feel a bit iffy about freely copying FocusScope. It's fine for now, since it's just a ptr holder. However, adding more data members to the class will have unpleasant side effects of suddenly copying too much stuff.

Also, it would probably be good to put back those trimmed whitespaces.

> Source/WebCore/ChangeLog:24
> +        After finding a *psuedo* focusable element in current focus scope, it tries to resolve a focused element recursively,

*psuedo* -> *pseudo*

> Source/WebCore/page/FocusController.cpp:96
> +FocusScope FocusScope::focusScopeIncluding(Node* node)

focusScopeOf?

> Source/WebCore/page/FocusController.cpp:105
> +FocusScope FocusScope::focusScopeInsideOf(Node* node)

focusScopeOfShadow?

> Source/WebCore/page/FocusController.cpp:391
> +Node* FocusController::findFocusableNodeDeeply(FocusDirection direction, FocusScope scope, Node* start, KeyboardEvent* event)

Deeply -> Recursively?

[Hayato Ito]

Created attachment 134229 [details]
update

[Hayato Ito]

(In reply to comment #5)

> My head hurts from reviewing this code. I need to take a break. I promise I'll give it another stab tomorrow.

Yeah, the algorithm looks complex, but I hope it is not so complicated. The Shadow DOM spec added just a couple of lines about focus navigation, but it is not so easy to implement that exactly. :)

I might add some comments on each functions of FocusController on ChangeLog later. That might be helpful.

> I feel a bit iffy about freely copying FocusScope. It's fine for now, since it's just a ptr holder. However, adding more data members to the class will have unpleasant side effects of suddenly copying too much stuff.

I agree. It's fine for now I think.

> 
> Also, it would probably be good to put back those trimmed whitespaces.

Done. I've restored trimmed white spaces.


View in context: https://bugs.webkit.org/attachment.cgi?id=133988&action=review

>> Source/WebCore/ChangeLog:24
>> +        After finding a *psuedo* focusable element in current focus scope, it tries to resolve a focused element recursively,
> 
> *psuedo* -> *pseudo*

Done.

>> Source/WebCore/page/FocusController.cpp:96
>> +FocusScope FocusScope::focusScopeIncluding(Node* node)
> 
> focusScopeOf?

Done.

>> Source/WebCore/page/FocusController.cpp:105
>> +FocusScope FocusScope::focusScopeInsideOf(Node* node)
> 
> focusScopeOfShadow?

Since FocusScope::FocusScopeOf(Node*) is already used, I'd like to avoid the name of focusScopeOfXXX. It might be confusing since they have different behaviors. So I named it focusScopeOwnedByXXX().

>> Source/WebCore/page/FocusController.cpp:391
>> +Node* FocusController::findFocusableNodeDeeply(FocusDirection direction, FocusScope scope, Node* start, KeyboardEvent* event)
> 
> Deeply -> Recursively?

Done.

[Dimitri Glazkov (Google)]

Comment on attachment 134229 [details]
update

View in context: https://bugs.webkit.org/attachment.cgi?id=134229&action=review

> Source/WebCore/page/FocusController.cpp:298
> +    RefPtr<Node> node = findFocusableNodeAcrossFocusScope(direction, currentNode ? FocusScope::focusScopeOf(currentNode) : FocusScope::focusScopeOf(document), currentNode, event);

The argument looks like it should be written: FocusScope::focusScopeOf(currentNode ? currentNode : document).

> Source/WebCore/page/FocusController.cpp:372
> +        if (foundInInnerFocusScope)
> +            found = foundInInnerFocusScope;
> +        else
> +            found = findFocusableNodeRecursively(direction, scope, currentNode, event);

Also looks like it could be an inline if.

> Source/WebCore/page/FocusController.cpp:394
> +    // start node is exclusive.

Capitalize first word, since it's a sentence.

> Source/WebCore/page/FocusController.cpp:404
> +        if (foundInInnerFocusScope)
> +            return foundInInnerFocusScope;
> +        return findFocusableNodeRecursively(direction, scope, found, event);

I think you hate inline ifs :P

[Hayato Ito]

Thank you for the review. Let me land this patch after addressing your comments.
I'll make some some 'if' statements 'inline' since it's webkit way.

(In reply to comment #8)
> (From update of attachment 134229 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=134229&action=review
> 
> > Source/WebCore/page/FocusController.cpp:298
> > +    RefPtr<Node> node = findFocusableNodeAcrossFocusScope(direction, currentNode ? FocusScope::focusScopeOf(currentNode) : FocusScope::focusScopeOf(document), currentNode, event);
> 
> The argument looks like it should be written: FocusScope::focusScopeOf(currentNode ? currentNode : document).
> 
> > Source/WebCore/page/FocusController.cpp:372
> > +        if (foundInInnerFocusScope)
> > +            found = foundInInnerFocusScope;
> > +        else
> > +            found = findFocusableNodeRecursively(direction, scope, currentNode, event);
> 
> Also looks like it could be an inline if.
> 
> > Source/WebCore/page/FocusController.cpp:394
> > +    // start node is exclusive.
> 
> Capitalize first word, since it's a sentence.
> 
> > Source/WebCore/page/FocusController.cpp:404
> > +        if (foundInInnerFocusScope)
> > +            return foundInInnerFocusScope;
> > +        return findFocusableNodeRecursively(direction, scope, found, event);
> 
> I think you hate inline ifs :P

[Hayato Ito]

Created attachment 134492 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 134492 [details]
Patch for landing

Clearing flags on attachment: 134492

Committed r112500: <http://trac.webkit.org/changeset/112500>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Csaba Osztrogonác]

Reopen, because it made tests assert: (at least on GTK and on Qt)

STDERR: ASSERTION FAILED: crossed == NotCrossed
STDERR: ../../Source/WebCore/dom/ReifiedTreeTraversal.cpp(221) : static WebCore::Node* WebCore::ReifiedTreeTraversal::parentNodeOrBackToInsertionPoint(const WebCore::Node*, WebCore::ReifiedTreeTraversal::CrossedUpperBoundary&)

[Hayato Ito]

Thank you for letting me know it. Let me check. I might roll out.

(In reply to comment #13)
> Reopen, because it made tests assert: (at least on GTK and on Qt)
> 
> STDERR: ASSERTION FAILED: crossed == NotCrossed
> STDERR: ../../Source/WebCore/dom/ReifiedTreeTraversal.cpp(221) : static WebCore::Node* WebCore::ReifiedTreeTraversal::parentNodeOrBackToInsertionPoint(const WebCore::Node*, WebCore::ReifiedTreeTraversal::CrossedUpperBoundary&)

[Hayato Ito]

I am rolling out in https://bugs.webkit.org/show_bug.cgi?id=82576.

I could not repro the ASSERTION fail on chromium port, but I could find the cause by taking a look at code around the failed assertion.

Let me roll out at first, land a fix for assertion, and re-land this patch.

(In reply to comment #14)
> Thank you for letting me know it. Let me check. I might roll out.
> 
> (In reply to comment #13)
> > Reopen, because it made tests assert: (at least on GTK and on Qt)
> > 
> > STDERR: ASSERTION FAILED: crossed == NotCrossed
> > STDERR: ../../Source/WebCore/dom/ReifiedTreeTraversal.cpp(221) : static WebCore::Node* WebCore::ReifiedTreeTraversal::parentNodeOrBackToInsertionPoint(const WebCore::Node*, WebCore::ReifiedTreeTraversal::CrossedUpperBoundary&)

[Hayato Ito]

Created attachment 134527 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 134527 [details]
Patch for landing

Clearing flags on attachment: 134527

Committed r112511: <http://trac.webkit.org/changeset/112511>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Chris Dumez]

The LayoutTests/fast/dom/shadow/focus-navigation.html in this patch is not going to work on GTK or EFL ports. The reason for that is that those ports don't wrap around when pressing tab and the active element is the last one.

So, the following will not work:
Should move from input-E-0 to input-A-1 in forward
PASS

On GTK/EFL ports, it will go to "body", not input-A-1.

The following test for example takes into consideration the different wrapping behavior in different ports:
LayoutTests/fast/events/tab-imagemap.html

I'm working on enabling Shadow DOM for EFL port (Bug 87732) but I need to skip this test because of this different wrapping behavior.