spatnav: Allow focus move to a close-by not-fully-aligned node over a distant but fully-aligned nod…

Source/core/page/SpatialNavigation.cpp

 /*
  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
  *
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
@@ skipping 27 matching lines @@
 #include "core/html/HTMLImageElement.h"
 #include "core/page/FrameTree.h"
 #include "core/page/Page.h"
 #include "core/rendering/RenderLayer.h"
 #include "platform/geometry/IntRect.h"
 
 namespace blink {
 
 using namespace HTMLNames;
 
-static RectsAlignment alignmentForRects(FocusType, const LayoutRect&, const LayoutRect&, const LayoutSize& viewSize);
-static bool areRectsFullyAligned(FocusType, const LayoutRect&, const LayoutRect&);
-static bool areRectsPartiallyAligned(FocusType, const LayoutRect&, const LayoutRect&);
-static bool areRectsMoreThanFullScreenApart(FocusType, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
 static bool isRectInDirection(FocusType, const LayoutRect&, const LayoutRect&);
 static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
 static LayoutRect rectToAbsoluteCoordinates(LocalFrame* initialFrame, const LayoutRect&);
 static bool isScrollableNode(const Node*);
 
 FocusCandidate::FocusCandidate(Node* node, FocusType type)
     : visibleNode(nullptr)
     , focusableNode(nullptr)
     , enclosingScrollableBox(nullptr)
     , distance(maxDistance())
-    , alignment(None)
     , isOffscreen(true)
     , isOffscreenAfterScrolling(true)
 {
     ASSERT(node);
     ASSERT(node->isElementNode());
 
     if (isHTMLAreaElement(*node)) {
         HTMLAreaElement& area = toHTMLAreaElement(*node);
         HTMLImageElement* image = area.imageElement();
         if (!image || !image->renderer())
@@ skipping 12 matching lines @@
     focusableNode = node;
     isOffscreen = hasOffscreenRect(visibleNode);
     isOffscreenAfterScrolling = hasOffscreenRect(visibleNode, type);
 }
 
 bool isSpatialNavigationEnabled(const LocalFrame* frame)
 {
     return (frame && frame->settings() && frame->settings()->spatialNavigationEnabled());
 }
 
-static RectsAlignment alignmentForRects(FocusType type, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
+static bool areRectsNotAligned(FocusType type, const LayoutRect& a, const LayoutRect& b)

[fs, 2015/01/12 12:07:23]

Not the most obvious name IMHO. Maybe rectsIntersectOnOrthogonalAxis or
something instead? (I.e. drop the negation from the name - and impl. - and add
it to the call-site instead.)

[c.shu, 2015/01/12 18:03:38]

will do.

 {
-    // If we found a node in full alignment, but it is too far away, ignore it.
-    if (areRectsMoreThanFullScreenApart(type, curRect, targetRect, viewSize))
-        return None;
-
-    if (areRectsFullyAligned(type, curRect, targetRect))
-        return Full;
-
-    if (areRectsPartiallyAligned(type, curRect, targetRect))
-        return Partial;
-
-    return None;
-}
-
-static inline bool isHorizontalMove(FocusType type)
-{
-    return type == FocusTypeLeft || type == FocusTypeRight;
-}
-
-static inline LayoutUnit start(FocusType type, const LayoutRect& rect)
-{
-    return isHorizontalMove(type) ? rect.y() : rect.x();
-}
-
-static inline LayoutUnit middle(FocusType type, const LayoutRect& rect)
-{
-    LayoutPoint center(rect.center());
-    return isHorizontalMove(type) ? center.y(): center.x();
-}
-
-static inline LayoutUnit end(FocusType type, const LayoutRect& rect)
-{
-    return isHorizontalMove(type) ? rect.maxY() : rect.maxX();
-}
-
-// This method checks if rects |a| and |b| are fully aligned either vertically or
-// horizontally. In general, rects whose central point falls between the top or
-// bottom of each other are considered fully aligned.
-// Rects that match this criteria are preferable target nodes in move focus changing
-// operations.
-// * a = Current focused node's rect.
-// * b = Focus candidate node's rect.
-static bool areRectsFullyAligned(FocusType type, const LayoutRect& a, const LayoutRect& b)
-{
-    LayoutUnit aStart, bStart, aEnd, bEnd;
-
     switch (type) {
     case FocusTypeLeft:
-        aStart = a.x();
-        bEnd = b.x();
-        break;
     case FocusTypeRight:
-        aStart = b.x();
-        bEnd = a.x();
-        break;
+        return a.maxY() <= b.y() || a.y() >= b.maxY();
     case FocusTypeUp:
-        aStart = a.y();
-        bEnd = b.y();
-        break;
     case FocusTypeDown:
-        aStart = b.y();
-        bEnd = a.y();
-        break;
-    default:
-        ASSERT_NOT_REACHED();
-        return false;
-    }
-
-    if (aStart < bEnd)
-        return false;
-
-    aStart = start(type, a);
-    bStart = start(type, b);
-
-    LayoutUnit aMiddle = middle(type, a);
-    LayoutUnit bMiddle = middle(type, b);
-
-    aEnd = end(type, a);
-    bEnd = end(type, b);
-
-    // Picture of the totally aligned logic:
-    //
-    //     Horizontal    Vertical        Horizontal     Vertical
-    //  ****************************  *****************************
-    //  *  _          *   _ _ _ _  *  *         _   *      _ _    *
-    //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *
-    //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *
-    //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *
-    //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *
-    //  *             *    |_|_|   *  *             *   |_|_|_|_| *
-    //  *             *            *  *             *             *
-    //  ****************************  *****************************
-
-    return (bMiddle >= aStart && bMiddle <= aEnd) // (1)
-        || (aMiddle >= bStart && aMiddle <= bEnd); // (2)
-}
-
-// This method checks if rects |a| and |b| are partially aligned either vertically or
-// horizontally. In general, rects whose either of edges falls between the top or
-// bottom of each other are considered partially-aligned.
-// This is a separate set of conditions from "fully-aligned" and do not include cases
-// that satisfy the former.
-// * a = Current focused node's rect.
-// * b = Focus candidate node's rect.
-static bool areRectsPartiallyAligned(FocusType type, const LayoutRect& a, const LayoutRect& b)
-{
-    LayoutUnit aStart  = start(type, a);
-    LayoutUnit bStart  = start(type, b);
-    LayoutUnit aEnd = end(type, a);
-    LayoutUnit bEnd = end(type, b);
-
-    // Picture of the partially aligned logic:
-    //
-    //    Horizontal       Vertical
-    // ********************************
-    // *  _            *   _ _ _      *
-    // * |_|           *  |_|_|_|     *
-    // * |_|.... _     *      . .     *
-    // * |_|    |_|    *      . .     *
-    // * |_|....|_|    *      ._._ _  *
-    // *        |_|    *      |_|_|_| *
-    // *        |_|    *              *
-    // *               *              *
-    // ********************************
-    //
-    // ... and variants of the above cases.
-    return (bStart >= aStart && bStart <= aEnd)
-        || (bEnd >= aStart && bEnd <= aEnd);
-}
-
-static bool areRectsMoreThanFullScreenApart(FocusType type, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
-{
-    ASSERT(isRectInDirection(type, curRect, targetRect));
-
-    switch (type) {
-    case FocusTypeLeft:
-        return curRect.x() - targetRect.maxX() > viewSize.width();
-    case FocusTypeRight:
-        return targetRect.x() - curRect.maxX() > viewSize.width();
-    case FocusTypeUp:
-        return curRect.y() - targetRect.maxY() > viewSize.height();
-    case FocusTypeDown:
-        return targetRect.y() - curRect.maxY() > viewSize.height();
+        return a.maxX() <= b.x() || a.x() >= b.maxX();
     default:
         ASSERT_NOT_REACHED();
         return true;
     }
 }
 
 // Return true if rect |a| is below |b|. False otherwise.
 // For overlapping rects, |a| is considered to be below |b|
 // if both edges of |a| are below the respective ones of |b|
 static inline bool below(const LayoutRect& a, const LayoutRect& b)
@@ skipping 388 matching lines @@
         return false;
 
     return true;
 }
 
 void distanceDataForNode(FocusType type, const FocusCandidate& current, FocusCandidate& candidate)
 {
     if (areElementsOnSameLine(current, candidate)) {
         if ((type == FocusTypeUp && current.rect.y() > candidate.rect.y()) || (type == FocusTypeDown && candidate.rect.y() > current.rect.y())) {
             candidate.distance = 0;
-            candidate.alignment = Full;
             return;
         }
     }
 
     LayoutRect nodeRect = candidate.rect;
     LayoutRect currentRect = current.rect;
     deflateIfOverlapped(currentRect, nodeRect);
 
     if (!isRectInDirection(type, currentRect, nodeRect))
         return;
 
     LayoutPoint exitPoint;
     LayoutPoint entryPoint;
     entryAndExitPointsForDirection(type, currentRect, nodeRect, exitPoint, entryPoint);
 
-    LayoutUnit xAxis = exitPoint.x() - entryPoint.x();
-    LayoutUnit yAxis = exitPoint.y() - entryPoint.y();
+    LayoutUnit xAxis = (exitPoint.x() - entryPoint.x()).abs();
+    LayoutUnit yAxis = (exitPoint.y() - entryPoint.y()).abs();
 
     LayoutUnit navigationAxisDistance;
-    LayoutUnit orthogonalAxisDistance;
+    LayoutUnit weightedOrthogonalAxisDistance;
+
+    // Weights are put to the orthogonal axis distance calculation so more aligned candidate
+    // would have advantage over partially- or not-aligned elements. The weight for left/right
+    // direction is given a higher value to allow navigation on common horizonally-aligned
+    // elements. Note the hardcoded values are based on tests and experiments.
+    // The not-aligned node is also given a penalty as the orthogonal distance could be 0.
+    const int orthogonalWeightForLeftRight = 30;
+    const int orthogonalWeightForUpDown = 2;
 
     switch (type) {
     case FocusTypeLeft:
     case FocusTypeRight:
-        navigationAxisDistance = xAxis.abs();
-        orthogonalAxisDistance = yAxis.abs();
+        navigationAxisDistance = xAxis;
+        if (areRectsNotAligned(type, currentRect, nodeRect))
+            yAxis += currentRect.height() / 2;

[fs, 2015/01/12 12:07:23]

Why mutate the yAxis value here? Shouldn't you just add this to the weighted
value? Similarly below. The additional bias also strike as potentially fairly
large/small - i.e. why is this value a "good choice"?

[c.shu, 2015/01/12 18:03:38]

The weight has no impact on 0. That's why I have to add a penalty on yAxis. This
happens in the alignnotalign test. The returns of entryAndExitPointsforDirection
are always 0 if the edges of the candidate rect and current rect are aligned,
not matter if the candidate is on the same side or the other side of current
node. I thought the height of the currentrect is better than a hardcoded one,
but not sure.

[fs, 2015/01/13 09:26:04]

I get the part about 0, but why not for instance (yAxis + bias) * ... rather
than mutation of yAxis (which affects the computation of the 'real' distance
too.)
Quite possible. FTR, what I'm trying to avoid is a "turn the knobs and hope
it'll be fine" kind of situation.

+        weightedOrthogonalAxisDistance = yAxis * orthogonalWeightForLeftRight;
         break;
     case FocusTypeUp:
     case FocusTypeDown:
-        navigationAxisDistance = yAxis.abs();
-        orthogonalAxisDistance = xAxis.abs();
+        navigationAxisDistance = yAxis;
+        if (areRectsNotAligned(type, currentRect, nodeRect))
+            xAxis += currentRect.width() / 2;
+        weightedOrthogonalAxisDistance = xAxis * orthogonalWeightForUpDown;
         break;
     default:
         ASSERT_NOT_REACHED();
         return;
     }
 
     double euclidianDistancePow2 = (xAxis * xAxis + yAxis * yAxis).toDouble();
     LayoutRect intersectionRect = intersection(currentRect, nodeRect);
     double overlap = (intersectionRect.width() * intersectionRect.height()).toDouble();
 
     // Distance calculation is based on http://www.w3.org/TR/WICD/#focus-handling
-    candidate.distance = sqrt(euclidianDistancePow2) + navigationAxisDistance+ orthogonalAxisDistance * 2 - sqrt(overlap);
-
-    LayoutSize viewSize = LayoutSize(candidate.visibleNode->document().page()->deprecatedLocalMainFrame()->view()->visibleContentRect().size());
-    candidate.alignment = alignmentForRects(type, currentRect, nodeRect, viewSize);
+    candidate.distance = sqrt(euclidianDistancePow2) + navigationAxisDistance + weightedOrthogonalAxisDistance - sqrt(overlap);
 }
 
 bool canBeScrolledIntoView(FocusType type, const FocusCandidate& candidate)
 {
     ASSERT(candidate.visibleNode && candidate.isOffscreen);
     LayoutRect candidateRect = candidate.rect;
     for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
         LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
         if (!candidateRect.intersects(parentRect)) {
             if (((type == FocusTypeLeft || type == FocusTypeRight) && parentNode->renderer()->style()->overflowX() == OHIDDEN)
@@ skipping 43 matching lines @@
     LayoutRect rect = virtualRectForDirection(type, rectToAbsoluteCoordinates(area.document().frame(), area.computeRect(area.imageElement()->renderer())), 1);
     return rect;
 }
 
 HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
 {
     return candidate.isFrameOwnerElement() ? toHTMLFrameOwnerElement(candidate.visibleNode) : nullptr;
 };
 
 } // namespace blink