Spatial Navigation should avoid unwanted calculation while deciding focus candidate.
authorcommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 5 Aug 2013 13:09:19 +0000 (13:09 +0000)
committercommit-queue@webkit.org <commit-queue@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 5 Aug 2013 13:09:19 +0000 (13:09 +0000)
https://bugs.webkit.org/show_bug.cgi?id=117265

Patch by Abhijeet Kandalkar <abhijeet.k@samsung.com> on 2013-08-05
Reviewed by Antonio Gomes.

Source/WebCore:

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.

Test: fast/spatial-navigation/snav-search-optimization.html

* page/FocusController.cpp:
(WebCore::FocusController::findFocusCandidateInContainer):
(WebCore::FocusController::advanceFocusDirectionally):
* page/Page.cpp:
(WebCore::Page::Page):
* page/Page.h:
(WebCore::Page::setLastSpatialNavigationCandidateCount):
(WebCore::Page::lastSpatialNavigationCandidateCount):
* page/SpatialNavigation.cpp:
(WebCore::isValidCandidate):
* page/SpatialNavigation.h:
* testing/Internals.cpp:
(WebCore::Internals::lastSpatialNavigationCandidateCount):
* testing/Internals.h:
* testing/Internals.idl:

LayoutTests:

Added testcases to count how many target nodes were tested before choosing a final target.

* fast/spatial-navigation/snav-search-optimization-expected.txt: Added.
* fast/spatial-navigation/snav-search-optimization.html: Added.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@153704 268f45cc-cd09-0410-ab3c-d52691b4dbfc

12 files changed:
LayoutTests/ChangeLog
LayoutTests/fast/spatial-navigation/snav-search-optimization-expected.txt [new file with mode: 0644]
LayoutTests/fast/spatial-navigation/snav-search-optimization.html [new file with mode: 0644]
Source/WebCore/ChangeLog
Source/WebCore/page/FocusController.cpp
Source/WebCore/page/Page.cpp
Source/WebCore/page/Page.h
Source/WebCore/page/SpatialNavigation.cpp
Source/WebCore/page/SpatialNavigation.h
Source/WebCore/testing/Internals.cpp
Source/WebCore/testing/Internals.h
Source/WebCore/testing/Internals.idl

index 1574f6d..8c2ae20 100644 (file)
@@ -1,3 +1,15 @@
+2013-08-05  Abhijeet Kandalkar  <abhijeet.k@samsung.com>
+
+        Spatial Navigation should avoid unwanted calculation while deciding focus candidate.
+        https://bugs.webkit.org/show_bug.cgi?id=117265
+
+        Reviewed by Antonio Gomes.
+
+        Added testcases to count how many target nodes were tested before choosing a final target.
+
+        * fast/spatial-navigation/snav-search-optimization-expected.txt: Added.
+        * fast/spatial-navigation/snav-search-optimization.html: Added.
+
 2013-08-05  Mihai Tica  <mitica@adobe.com>
 
         [CSS Background Blending] Specifying background-image and background-color with opaque
diff --git a/LayoutTests/fast/spatial-navigation/snav-search-optimization-expected.txt b/LayoutTests/fast/spatial-navigation/snav-search-optimization-expected.txt
new file mode 100644 (file)
index 0000000..a8aea2f
--- /dev/null
@@ -0,0 +1,13 @@
+1      2       3
+4      
+       6
+7      8       9
+PASS internals.lastSpatialNavigationCandidateCount() is 9
+PASS internals.lastSpatialNavigationCandidateCount() is 6
+PASS internals.lastSpatialNavigationCandidateCount() is 2
+PASS internals.lastSpatialNavigationCandidateCount() is 9
+PASS internals.lastSpatialNavigationCandidateCount() is 6
+PASS internals.lastSpatialNavigationCandidateCount() is 2
+PASS internals.lastSpatialNavigationCandidateCount() is 5
+PASS internals.lastSpatialNavigationCandidateCount() is 2
+
diff --git a/LayoutTests/fast/spatial-navigation/snav-search-optimization.html b/LayoutTests/fast/spatial-navigation/snav-search-optimization.html
new file mode 100644 (file)
index 0000000..4938a2b
--- /dev/null
@@ -0,0 +1,101 @@
+<html>
+  <!--
+    This test ensures the optimization done in searching logic to find best candidate focusable node with minimum iterations.
+
+    * Pre-conditions:
+    1) TestRunner support for SNav enable/disable.
+
+    * Navigation steps:
+    1) Loads this page, focus goes to "2".
+    2) lastSpatialNavigationCandidateCount() returns the number of nodes actually considered to determine best candidate focusable node,
+       along the most recent navigation direction.
+  -->
+<head>
+    <script src="../js/resources/js-test-pre.js"></script>
+    <script src="resources/spatial-navigation-utils.js"></script>
+    <script type="application/javascript">
+
+    var resultMap = [
+        ["DONE", "DONE"]
+    ];
+
+    if (window.testRunner) {
+        testRunner.dumpAsText();
+        testRunner.setSpatialNavigationEnabled(true);
+        testRunner.overridePreference("WebKitTabToLinksPreferenceKey", 1);
+        testRunner.waitUntilDone();
+    }
+
+    function runTest()
+    {
+        initTest(resultMap, additionalTest);
+    }
+
+    function additionalTest()
+    {
+        document.getElementById("2").focus();
+        eventSender.keyDown("downArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "9");
+        eventSender.keyDown("downArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "6");
+        eventSender.keyDown("downArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "2");
+        eventSender.keyDown("rightArrow");
+        eventSender.keyDown("upArrow");
+        eventSender.keyDown("leftArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "9");
+        eventSender.keyDown("leftArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "6");
+        eventSender.keyDown("leftArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "2");
+        eventSender.keyDown("upArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "5");
+        eventSender.keyDown("upArrow");
+        shouldBe("internals.lastSpatialNavigationCandidateCount()", "2");
+        testCompleted();
+    }
+
+    function testCompleted()
+    {
+        if (window.testRunner)
+            testRunner.notifyDone();
+    }
+
+    window.onload = runTest;
+
+    </script>
+    <script src="js/resources/js-test-post.js"></script>
+</head>
+<body id="some-content" xmlns="http://www.w3.org/1999/xhtml">
+    <table style="text-align: left; margin-left: auto; margin-right: auto;" border="1" cellpadding="2" cellspacing="1">
+    <tbody>
+        <tr>
+            <td style="vertical-align: top; text-align: center;"><a id="1" href="a">1</a></td>
+            <td style="vertical-align: top; text-align: center;"><a id="2" href="a">2</a></td>
+            <td style="vertical-align: top; text-align: center;"><a id="3" href="a">3</a></td>
+        </tr>
+        <tr>
+            <td style="text-align: center;"><a id="4" href="a">4</a></td>
+            <td><br><iframe width='100' height='100' src="data:text/html,
+                       <table style='text-align: center; margin-left: auto; margin-right: auto;'>
+                       <tbody>
+                       <tr>
+            <td style='text-align: center;'><a id='5' href='a'>5</a></td>
+                       </tr>
+                       </tbody>
+                       </table>">
+                       </iframe>
+                       </td>
+            <td style="text-align: center;"><a id="6" href="a">6</a></td>
+        </tr>
+        <tr>
+            <td style="vertical-align: top; text-align: center;"><a id="7" href="a">7</a></td>
+            <td style="vertical-align: top; text-align: center;"><a id="8" href="a">8</a></td>
+            <td style="vertical-align: top; text-align: center;"><a id="9" href="a">9</a></td>
+        </tr>
+    </tbody>
+    </table>
+    <div id="console"></div>
+</body>
+</html>
+
index 4c9ee41..7b115ba 100644 (file)
@@ -1,3 +1,32 @@
+2013-08-05  Abhijeet Kandalkar  <abhijeet.k@samsung.com>
+
+        Spatial Navigation should avoid unwanted calculation while deciding focus candidate.
+        https://bugs.webkit.org/show_bug.cgi?id=117265
+
+        Reviewed by Antonio Gomes.
+
+        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.
+
+        Test: fast/spatial-navigation/snav-search-optimization.html
+
+        * page/FocusController.cpp:
+        (WebCore::FocusController::findFocusCandidateInContainer):
+        (WebCore::FocusController::advanceFocusDirectionally):
+        * page/Page.cpp:
+        (WebCore::Page::Page):
+        * page/Page.h:
+        (WebCore::Page::setLastSpatialNavigationCandidateCount):
+        (WebCore::Page::lastSpatialNavigationCandidateCount):
+        * page/SpatialNavigation.cpp:
+        (WebCore::isValidCandidate):
+        * page/SpatialNavigation.h:
+        * testing/Internals.cpp:
+        (WebCore::Internals::lastSpatialNavigationCandidateCount):
+        * testing/Internals.h:
+        * testing/Internals.idl:
+
 2013-08-05  Mihai Tica  <mitica@adobe.com>
 
         [CSS Background Blending] Specifying background-image and background-color
index bc83e7f..cef2195 100644 (file)
@@ -766,6 +766,7 @@ void FocusController::findFocusCandidateInContainer(Node* container, const Layou
     current.focusableNode = focusedNode;
     current.visibleNode = focusedNode;
 
+    unsigned candidateCount = 0;
     for (; element; element = (element->isFrameOwnerElement() || canScrollInDirection(element, direction))
         ? ElementTraversal::nextSkippingChildren(element, container)
         : ElementTraversal::next(element, container)) {
@@ -779,9 +780,20 @@ void FocusController::findFocusCandidateInContainer(Node* container, const Layou
         if (candidate.isNull())
             continue;
 
+        if (!isValidCandidate(direction, current, candidate))
+            continue;
+
+        candidateCount++;
         candidate.enclosingScrollableBox = container;
         updateFocusCandidateIfNeeded(direction, current, candidate, closest);
     }
+
+    // The variable 'candidateCount' keeps track of the number of nodes traversed in a given container.
+    // If we have more than one container in a page then the total number of nodes traversed is equal to the sum of nodes traversed in each container.
+    if (focusedFrame() && focusedFrame()->document()) {
+        candidateCount += focusedFrame()->document()->page()->lastSpatialNavigationCandidateCount();
+        focusedFrame()->document()->page()->setLastSpatialNavigationCandidateCount(candidateCount);
+    }
 }
 
 bool FocusController::advanceFocusDirectionallyInContainer(Node* container, const LayoutRect& startingRect, FocusDirection direction, KeyboardEvent* event)
@@ -868,7 +880,7 @@ bool FocusController::advanceFocusDirectionally(FocusDirection direction, Keyboa
 
     if (container->isDocumentNode())
         toDocument(container)->updateLayoutIgnorePendingStylesheets();
-        
+
     // Figure out the starting rect.
     LayoutRect startingRect;
     if (focusedElement) {
@@ -882,6 +894,9 @@ bool FocusController::advanceFocusDirectionally(FocusDirection direction, Keyboa
         }
     }
 
+    if (focusedFrame() && focusedFrame()->document())
+        focusedDocument->page()->setLastSpatialNavigationCandidateCount(0);
+
     bool consumed = false;
     do {
         consumed = advanceFocusDirectionallyInContainer(container, startingRect, direction, event);
index b4c963a..ad70238 100644 (file)
@@ -187,6 +187,7 @@ Page::Page(PageClients& pageClients)
     , m_scriptedAnimationsSuspended(false)
     , m_pageThrottler(PageThrottler::create(this))
     , m_console(PageConsole::create(this))
+    , m_lastSpatialNavigationCandidatesCount(0) // NOTE: Only called from Internals for Spatial Navigation testing.
     , m_framesHandlingBeforeUnloadEvent(0)
 {
     ASSERT(m_editorClient);
index d95565a..af5ccd9 100644 (file)
@@ -409,6 +409,8 @@ public:
     void incrementFrameHandlingBeforeUnloadEventCount();
     void decrementFrameHandlingBeforeUnloadEventCount();
     bool isAnyFrameHandlingBeforeUnloadEvent();
+    void setLastSpatialNavigationCandidateCount(unsigned count) { m_lastSpatialNavigationCandidatesCount = count; }
+    unsigned lastSpatialNavigationCandidateCount() const { return m_lastSpatialNavigationCandidatesCount; }
 
 private:
     void initGroup();
@@ -546,7 +548,8 @@ private:
 
     HashSet<String> m_seenPlugins;
     HashSet<String> m_seenMediaEngines;
-    
+
+    unsigned m_lastSpatialNavigationCandidatesCount;
     unsigned m_framesHandlingBeforeUnloadEvent;
 };
 
index 12dea12..7c0362b 100644 (file)
@@ -620,6 +620,28 @@ bool areElementsOnSameLine(const FocusCandidate& firstCandidate, const FocusCand
     return true;
 }
 
+// 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.
+bool isValidCandidate(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
+{
+    LayoutRect currentRect = current.rect;
+    LayoutRect candidateRect = candidate.rect;
+
+    switch (direction) {
+    case FocusDirectionLeft:
+        return candidateRect.x() < currentRect.maxX();
+    case FocusDirectionUp:
+        return candidateRect.y() < currentRect.maxY();
+    case FocusDirectionRight:
+        return candidateRect.maxX() > currentRect.x();
+    case FocusDirectionDown:
+        return candidateRect.maxY() > currentRect.y();
+    default:
+        ASSERT_NOT_REACHED();
+    }
+    return false;
+}
+
 void distanceDataForNode(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
 {
     if (areElementsOnSameLine(current, candidate)) {
index 5fb6fa5..152eaca 100644 (file)
@@ -136,6 +136,7 @@ bool canScrollInDirection(const Node* container, FocusDirection);
 bool canScrollInDirection(const Frame*, FocusDirection);
 bool canBeScrolledIntoView(FocusDirection, const FocusCandidate&);
 bool areElementsOnSameLine(const FocusCandidate& firstCandidate, const FocusCandidate& secondCandidate);
+bool isValidCandidate(FocusDirection, const FocusCandidate&, FocusCandidate&);
 void distanceDataForNode(FocusDirection, const FocusCandidate& current, FocusCandidate& candidate);
 Node* scrollableEnclosingBoxOrParentFrameForNodeInDirection(FocusDirection, Node*);
 LayoutRect nodeRectInAbsoluteCoordinates(Node*, bool ignoreBorder = false);
index eefc902..4d689c0 100644 (file)
@@ -393,6 +393,16 @@ Node* Internals::parentTreeScope(Node* node, ExceptionCode& ec)
     return parentTreeScope ? parentTreeScope->rootNode() : 0;
 }
 
+unsigned Internals::lastSpatialNavigationCandidateCount(ExceptionCode& ec) const
+{
+    if (!contextDocument() || !contextDocument()->page()) {
+        ec = INVALID_ACCESS_ERR;
+        return 0;
+    }
+
+    return contextDocument()->page()->lastSpatialNavigationCandidateCount();
+}
+
 unsigned Internals::numberOfActiveAnimations() const
 {
     Frame* contextFrame = frame();
index 25ba449..d4dc240 100644 (file)
@@ -94,6 +94,9 @@ public:
     String shadowPseudoId(Element*, ExceptionCode&);
     void setShadowPseudoId(Element*, const String&, ExceptionCode&);
 
+    // Spatial Navigation testing.
+    unsigned lastSpatialNavigationCandidateCount(ExceptionCode&) const;
+
     // CSS Animation testing.
     unsigned numberOfActiveAnimations() const;
     bool animationsAreSuspended(Document*, ExceptionCode&) const;
index 9622e50..98aeff8 100644 (file)
@@ -54,6 +54,9 @@
     [RaisesException] Node treeScopeRootNode(Node node);
     [RaisesException] Node parentTreeScope(Node node);
 
+    // Spatial Navigation testing
+    [RaisesException] unsigned long lastSpatialNavigationCandidateCount();
+
     // CSS Animation testing.
     unsigned long numberOfActiveAnimations();
     [RaisesException] void suspendAnimations(Document document);