Bug 117265 – Spatial Navigation should avoid unwanted calculation while deciding focus candidate.

• Status: RESOLVED
• Resolution: FIXED
• Component: New Bugs

[Abhijeet Kandalkar]

Spatial Navigation should consider only those nodes as candidate which are exactly in the focus-direction.
e.g. If we are moving down then the nodes that are above CURRENT focused node should be considered as invalid.

           1
      5          4

 Left      2       Right


           3

If '2' is a current focused node and focus direction is DOWN, then '1','5','4' should be consider as invalid since they are above(UP) the '2'.

Current implementation, first consider '1', calculate all offsets and data needed to decide best candidate and then discard it.Similar procedure for '4' and '5'.It is better to discard them in first stage so that we can save extra calculation needed to determine best candidate.

[Abhijeet Kandalkar]

Working on current optimization and will update fix soon.

[Abhijeet Kandalkar]

Created attachment 203905 [details]
117265.patch 

Spatial Navigation should consider only those nodes as candidate which are exactly in the focus-direction.
e.g. If we are moving down then the nodes that are above CURRENT focused node should be considered as invalid.
Added isValidCandidate() which checks whether node is exactly in the focus-direction,if it is not it start iteration
with next node and avoid extra calculation.

[Antonio Gomes]

Comment on attachment 203905 [details]
117265.patch 

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

we can test it with "Internals" interface: for example, as per target calculation, expose a counter that holds how many target nodes were tested before having a final target.

> page/SpatialNavigation.cpp:630
> +            result = true;

just return true right way.

[Antonio Gomes]

Comment on attachment 203905 [details]
117265.patch 

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

> ChangeLog:12
> +        Changes added is only optimization to the logic of searching best focused candidate node.All existing layout test case

Nit: Changes added *are* only *optimizations*. Space before "All"

> ChangeLog:13
> +        are working fine with this change.So, no need to add extra layout test.

Nit: space before "So"

[Abhijeet Kandalkar]

Created attachment 204146 [details]
Updated patch

Added changes as per comments given by Antonio

[WebKit Commit Bot]

Attachment 204146 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'LayoutTests/ChangeLog', u'LayoutTests/fast/spatial-navigation/snav-search-optimization-expected.txt', u'LayoutTests/fast/spatial-navigation/snav-search-optimization.html', u'Source/WebCore/ChangeLog', u'Source/WebCore/page/FocusController.cpp', u'Source/WebCore/page/FocusController.h', u'Source/WebCore/page/SpatialNavigation.cpp', u'Source/WebCore/page/SpatialNavigation.h', u'Source/WebCore/testing/Internals.cpp', u'Source/WebCore/testing/Internals.h', u'Source/WebCore/testing/Internals.idl']" exit_code: 1
Source/WebCore/testing/Internals.h:97:  Should have a space between // and comment  [whitespace/comments] [4]
Source/WebCore/page/SpatialNavigation.h:145:  The parameter name "candidate" adds no information, so it should be removed.  [readability/parameter_name] [5]
Total errors found: 2 in 11 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Abhijeet Kandalkar]

Created attachment 204149 [details]
Updated patch-1

Added changes as per comments given by Antonio and fixed webkit coding style checks.

[Antonio Gomes]

Comment on attachment 204149 [details]
Updated patch-1

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

> LayoutTests/fast/spatial-navigation/snav-search-optimization.html:6
> +    1) DRT support for SNav enable/disable.

DRT = TestRunner now

> LayoutTests/fast/spatial-navigation/snav-search-optimization.html:38
> +        shouldBe("internals.numberOfProcessedNodes(document)", "4");         //current focused node is 5 and navigation direction is DOWN

I think you should also test that the currently focused node is '5'. Same the the below checks...

> Source/WebCore/testing/Internals.cpp:393
> +unsigned Internals::numberOfProcessedNodes(Document* document, ExceptionCode& ec) const
> +{

since you are passing a "document" you should also have a test involving inner frame.

Specially becaused an inner frame's focusController is different from its parents.

> Source/WebCore/testing/Internals.h:98
> +    unsigned numberOfProcessedNodes(Document*, ExceptionCode&) const;

It is a way too generic name. r- due to that.

Who is reading this code "focusController->numberOfProcessedNodes" will never imagine it is related to Spatial Nav.

maybe lastSpatialNavigationCandidatesCount or something like this.

> Source/WebCore/page/SpatialNavigation.cpp:630
> +            result = true;

return true directly here. Same for the other clauses below.

[Abhijeet Kandalkar]

Created attachment 206329 [details]
Updated patch-2

Updated changes as per comments given by Antonio.

[Antonio Gomes]

Comment on attachment 206329 [details]
Updated patch-2

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

Almost there... r- for now.

> LayoutTests/fast/spatial-navigation/snav-search-optimization.html:3
> +    This test ensures the optimization done in seaching logic to find best candidate focusable node with minimum iterations.

seaRching

> LayoutTests/fast/spatial-navigation/snav-search-optimization.html:52
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "9"); // Focused node is 2 and navigation direction is DOWN. Only 1,3,4,5,6,7,8,9,iframe are considered as valid candidate.
> +        eventSender.keyDown("downArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "6"); // Focused node is 5 and navigation direction is DOWN. Only 4,6,7,8,9,iframe are considered as valid candidate.
> +        eventSender.keyDown("downArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "2"); // Focused node is 8 and navigation direction is DOWN. Only 7,9 are considered as valid candidate.
> +        eventSender.keyDown("rightArrow");
> +        eventSender.keyDown("upArrow");
> +        eventSender.keyDown("leftArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "9"); // Focused node is 6 and navigation direction is LEFT. Only 1,2,3,4,5,7,8,9,iframe are considered as valid candidate.
> +        eventSender.keyDown("leftArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "6"); // Focused node is 5 and navigation direction is LEFT. Only 1,2,4,7,8,iframe are considered as valid candidate.
> +        eventSender.keyDown("leftArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "2"); // Focused node is 4 and navigation direction is LEFT. Only 1,7 are considered as valid candidate.
> +        eventSender.keyDown("upArrow");
> +        shouldBe("internals.lastSpatialNavigationCandidateCount()", "5"); // Focused node is 4 and navigation direction is UP. Only 1,2,3,iframe,6 are considered as valid candidate.

I am not sure if these comments are valid. I would omit them.

Additionally, why should the iframe itself be considered a focus candidate?

> Source/WebCore/page/FocusController.cpp:794
> +    if (focusedFrame() && focusedFrame()->document()) {
> +        candidateCount += focusedFrame()->document()->page()->lastSpatialNavigationCandidateCount();
> +        focusedFrame()->document()->page()->setLastSpatialNavigationCandidateCount(candidateCount);
> +    }

could you explain this block? maybe a comment in the code..

> Source/WebCore/page/Page.h:547
> +    unsigned m_lastSpatialNavigationCandidatesCount;

please add a comment like

// NOTE: Only called from Internals for testing.

> Source/WebCore/page/SpatialNavigation.cpp:628
> +        if (candidateRect.x() < currentRect.maxX())

return candidateRect.x() < currentRect.maxX();

[Abhijeet Kandalkar]

Created attachment 207984 [details]
Updated patch-3

Additionally, why should the iframe itself be considered a focus candidate?

1. node->isKeyboardFocusable(event) if node is IFrame returns true.
2. If we have Iframes in html page then Navigation alogorithm considers it as focusable element.

    if (HTMLFrameOwnerElement* frameElement = frameOwnerElement(focusCandidate)) {
       // consider Iframe as container and search best candidate node in Iframe(container). 
    }

[Abhijeet Kandalkar]

Created attachment 208002 [details]
Updated patch-4

Please refer latest "Updated patch-4" changes.

[WebKit Commit Bot]

Comment on attachment 208002 [details]
Updated patch-4

Clearing flags on attachment: 208002

Committed r153704: <http://trac.webkit.org/changeset/153704>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.