src/third_party/WebKit/Source/core/page/SpatialNavigation.cpp

   1 /*
   2  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
   3  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  23  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  24  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  */
  28
  29 #include "config.h"
  30 #include "core/page/SpatialNavigation.h"
  31
  32 #include "core/HTMLNames.h"
  33 #include "core/frame/FrameView.h"
  34 #include "core/frame/LocalFrame.h"
  35 #include "core/frame/Settings.h"
  36 #include "core/html/HTMLAreaElement.h"
  37 #include "core/html/HTMLFrameOwnerElement.h"
  38 #include "core/html/HTMLImageElement.h"
  39 #include "core/page/FrameTree.h"
  40 #include "core/page/Page.h"
  41 #include "core/rendering/RenderLayer.h"
  42 #include "platform/geometry/IntRect.h"
  43
  44 namespace blink {
  45
  46 using namespace HTMLNames;
  47
  48 static RectsAlignment alignmentForRects(FocusType, const LayoutRect&, const LayoutRect&, const LayoutSize& viewSize);
  49 static bool areRectsFullyAligned(FocusType, const LayoutRect&, const LayoutRect&);
  50 static bool areRectsPartiallyAligned(FocusType, const LayoutRect&, const LayoutRect&);
  51 static bool areRectsMoreThanFullScreenApart(FocusType, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
  52 static bool isRectInDirection(FocusType, const LayoutRect&, const LayoutRect&);
  53 static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
  54 static LayoutRect rectToAbsoluteCoordinates(LocalFrame* initialFrame, const LayoutRect&);
  55 static bool isScrollableNode(const Node*);
  56
  57 FocusCandidate::FocusCandidate(Node* node, FocusType type)
  58     : visibleNode(nullptr)
  59     , focusableNode(nullptr)
  60     , enclosingScrollableBox(nullptr)
  61     , distance(maxDistance())
  62     , alignment(None)
  63     , isOffscreen(true)
  64     , isOffscreenAfterScrolling(true)
  65 {
  66     ASSERT(node);
  67     ASSERT(node->isElementNode());
  68
  69     if (isHTMLAreaElement(*node)) {
  70         HTMLAreaElement& area = toHTMLAreaElement(*node);
  71         HTMLImageElement* image = area.imageElement();
  72         if (!image || !image->renderer())
  73             return;
  74
  75         visibleNode = image;
  76         rect = virtualRectForAreaElementAndDirection(area, type);
  77     } else {
  78         if (!node->renderer())
  79             return;
  80
  81         visibleNode = node;
  82         rect = nodeRectInAbsoluteCoordinates(node, true /* ignore border */);
  83     }
  84
  85     focusableNode = node;
  86     isOffscreen = hasOffscreenRect(visibleNode);
  87     isOffscreenAfterScrolling = hasOffscreenRect(visibleNode, type);
  88 }
  89
  90 bool isSpatialNavigationEnabled(const LocalFrame* frame)
  91 {
  92     return (frame && frame->settings() && frame->settings()->spatialNavigationEnabled());
  93 }
  94
  95 static RectsAlignment alignmentForRects(FocusType type, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
  96 {
  97     // If we found a node in full alignment, but it is too far away, ignore it.
  98     if (areRectsMoreThanFullScreenApart(type, curRect, targetRect, viewSize))
  99         return None;
 100
 101     if (areRectsFullyAligned(type, curRect, targetRect))
 102         return Full;
 103
 104     if (areRectsPartiallyAligned(type, curRect, targetRect))
 105         return Partial;
 106
 107     return None;
 108 }
 109
 110 static inline bool isHorizontalMove(FocusType type)
 111 {
 112     return type == FocusTypeLeft || type == FocusTypeRight;
 113 }
 114
 115 static inline LayoutUnit start(FocusType type, const LayoutRect& rect)
 116 {
 117     return isHorizontalMove(type) ? rect.y() : rect.x();
 118 }
 119
 120 static inline LayoutUnit middle(FocusType type, const LayoutRect& rect)
 121 {
 122     LayoutPoint center(rect.center());
 123     return isHorizontalMove(type) ? center.y(): center.x();
 124 }
 125
 126 static inline LayoutUnit end(FocusType type, const LayoutRect& rect)
 127 {
 128     return isHorizontalMove(type) ? rect.maxY() : rect.maxX();
 129 }
 130
 131 // This method checks if rects |a| and |b| are fully aligned either vertically or
 132 // horizontally. In general, rects whose central point falls between the top or
 133 // bottom of each other are considered fully aligned.
 134 // Rects that match this criteria are preferable target nodes in move focus changing
 135 // operations.
 136 // * a = Current focused node's rect.
 137 // * b = Focus candidate node's rect.
 138 static bool areRectsFullyAligned(FocusType type, const LayoutRect& a, const LayoutRect& b)
 139 {
 140     LayoutUnit aStart, bStart, aEnd, bEnd;
 141
 142     switch (type) {
 143     case FocusTypeLeft:
 144         aStart = a.x();
 145         bEnd = b.x();
 146         break;
 147     case FocusTypeRight:
 148         aStart = b.x();
 149         bEnd = a.x();
 150         break;
 151     case FocusTypeUp:
 152         aStart = a.y();
 153         bEnd = b.y();
 154         break;
 155     case FocusTypeDown:
 156         aStart = b.y();
 157         bEnd = a.y();
 158         break;
 159     default:
 160         ASSERT_NOT_REACHED();
 161         return false;
 162     }
 163
 164     if (aStart < bEnd)
 165         return false;
 166
 167     aStart = start(type, a);
 168     bStart = start(type, b);
 169
 170     LayoutUnit aMiddle = middle(type, a);
 171     LayoutUnit bMiddle = middle(type, b);
 172
 173     aEnd = end(type, a);
 174     bEnd = end(type, b);
 175
 176     // Picture of the totally aligned logic:
 177     //
 178     //     Horizontal    Vertical        Horizontal     Vertical
 179     //  ****************************  *****************************
 180     //  *  _          *   _ _ _ _  *  *         _   *      _ _    *
 181     //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *
 182     //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *
 183     //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *
 184     //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *
 185     //  *             *    |_|_|   *  *             *   |_|_|_|_| *
 186     //  *             *            *  *             *             *
 187     //  ****************************  *****************************
 188
 189     return (bMiddle >= aStart && bMiddle <= aEnd) // (1)
 190         || (aMiddle >= bStart && aMiddle <= bEnd); // (2)
 191 }
 192
 193 // This method checks if rects |a| and |b| are partially aligned either vertically or
 194 // horizontally. In general, rects whose either of edges falls between the top or
 195 // bottom of each other are considered partially-aligned.
 196 // This is a separate set of conditions from "fully-aligned" and do not include cases
 197 // that satisfy the former.
 198 // * a = Current focused node's rect.
 199 // * b = Focus candidate node's rect.
 200 static bool areRectsPartiallyAligned(FocusType type, const LayoutRect& a, const LayoutRect& b)
 201 {
 202     LayoutUnit aStart  = start(type, a);
 203     LayoutUnit bStart  = start(type, b);
 204     LayoutUnit aEnd = end(type, a);
 205     LayoutUnit bEnd = end(type, b);
 206
 207     // Picture of the partially aligned logic:
 208     //
 209     //    Horizontal       Vertical
 210     // ********************************
 211     // *  _            *   _ _ _      *
 212     // * |_|           *  |_|_|_|     *
 213     // * |_|.... _     *      . .     *
 214     // * |_|    |_|    *      . .     *
 215     // * |_|....|_|    *      ._._ _  *
 216     // *        |_|    *      |_|_|_| *
 217     // *        |_|    *              *
 218     // *               *              *
 219     // ********************************
 220     //
 221     // ... and variants of the above cases.
 222     return (bStart >= aStart && bStart <= aEnd)
 223         || (bEnd >= aStart && bEnd <= aEnd);
 224 }
 225
 226 static bool areRectsMoreThanFullScreenApart(FocusType type, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
 227 {
 228     ASSERT(isRectInDirection(type, curRect, targetRect));
 229
 230     switch (type) {
 231     case FocusTypeLeft:
 232         return curRect.x() - targetRect.maxX() > viewSize.width();
 233     case FocusTypeRight:
 234         return targetRect.x() - curRect.maxX() > viewSize.width();
 235     case FocusTypeUp:
 236         return curRect.y() - targetRect.maxY() > viewSize.height();
 237     case FocusTypeDown:
 238         return targetRect.y() - curRect.maxY() > viewSize.height();
 239     default:
 240         ASSERT_NOT_REACHED();
 241         return true;
 242     }
 243 }
 244
 245 // Return true if rect |a| is below |b|. False otherwise.
 246 // For overlapping rects, |a| is considered to be below |b|
 247 // if both edges of |a| are below the respective ones of |b|
 248 static inline bool below(const LayoutRect& a, const LayoutRect& b)
 249 {
 250     return a.y() >= b.maxY()
 251         || (a.y() >= b.y() && a.maxY() > b.maxY());
 252 }
 253
 254 // Return true if rect |a| is on the right of |b|. False otherwise.
 255 // For overlapping rects, |a| is considered to be on the right of |b|
 256 // if both edges of |a| are on the right of the respective ones of |b|
 257 static inline bool rightOf(const LayoutRect& a, const LayoutRect& b)
 258 {
 259     return a.x() >= b.maxX()
 260         || (a.x() >= b.x() && a.maxX() > b.maxX());
 261 }
 262
 263 static bool isRectInDirection(FocusType type, const LayoutRect& curRect, const LayoutRect& targetRect)
 264 {
 265     switch (type) {
 266     case FocusTypeLeft:
 267         return rightOf(curRect, targetRect);
 268     case FocusTypeRight:
 269         return rightOf(targetRect, curRect);
 270     case FocusTypeUp:
 271         return below(curRect, targetRect);
 272     case FocusTypeDown:
 273         return below(targetRect, curRect);
 274     default:
 275         ASSERT_NOT_REACHED();
 276         return false;
 277     }
 278 }
 279
 280 // Checks if |node| is offscreen the visible area (viewport) of its container
 281 // document. In case it is, one can scroll in direction or take any different
 282 // desired action later on.
 283 bool hasOffscreenRect(Node* node, FocusType type)
 284 {
 285     // Get the FrameView in which |node| is (which means the current viewport if |node|
 286     // is not in an inner document), so we can check if its content rect is visible
 287     // before we actually move the focus to it.
 288     FrameView* frameView = node->document().view();
 289     if (!frameView)
 290         return true;
 291
 292     ASSERT(!frameView->needsLayout());
 293
 294     LayoutRect containerViewportRect = frameView->visibleContentRect();
 295     // We want to select a node if it is currently off screen, but will be
 296     // exposed after we scroll. Adjust the viewport to post-scrolling position.
 297     // If the container has overflow:hidden, we cannot scroll, so we do not pass direction
 298     // and we do not adjust for scrolling.
 299     switch (type) {
 300     case FocusTypeLeft:
 301         containerViewportRect.setX(containerViewportRect.x() - ScrollableArea::pixelsPerLineStep());
 302         containerViewportRect.setWidth(containerViewportRect.width() + ScrollableArea::pixelsPerLineStep());
 303         break;
 304     case FocusTypeRight:
 305         containerViewportRect.setWidth(containerViewportRect.width() + ScrollableArea::pixelsPerLineStep());
 306         break;
 307     case FocusTypeUp:
 308         containerViewportRect.setY(containerViewportRect.y() - ScrollableArea::pixelsPerLineStep());
 309         containerViewportRect.setHeight(containerViewportRect.height() + ScrollableArea::pixelsPerLineStep());
 310         break;
 311     case FocusTypeDown:
 312         containerViewportRect.setHeight(containerViewportRect.height() + ScrollableArea::pixelsPerLineStep());
 313         break;
 314     default:
 315         break;
 316     }
 317
 318     RenderObject* render = node->renderer();
 319     if (!render)
 320         return true;
 321
 322     LayoutRect rect(render->absoluteClippedOverflowRect());
 323     if (rect.isEmpty())
 324         return true;
 325
 326     return !containerViewportRect.intersects(rect);
 327 }
 328
 329 bool scrollInDirection(LocalFrame* frame, FocusType type)
 330 {
 331     ASSERT(frame);
 332
 333     if (frame && canScrollInDirection(frame->document(), type)) {
 334         LayoutUnit dx = 0;
 335         LayoutUnit dy = 0;
 336         switch (type) {
 337         case FocusTypeLeft:
 338             dx = - ScrollableArea::pixelsPerLineStep();
 339             break;
 340         case FocusTypeRight:
 341             dx = ScrollableArea::pixelsPerLineStep();
 342             break;
 343         case FocusTypeUp:
 344             dy = - ScrollableArea::pixelsPerLineStep();
 345             break;
 346         case FocusTypeDown:
 347             dy = ScrollableArea::pixelsPerLineStep();
 348             break;
 349         default:
 350             ASSERT_NOT_REACHED();
 351             return false;
 352         }
 353
 354         frame->view()->scrollBy(IntSize(dx, dy));
 355         return true;
 356     }
 357     return false;
 358 }
 359
 360 bool scrollInDirection(Node* container, FocusType type)
 361 {
 362     ASSERT(container);
 363     if (container->isDocumentNode())
 364         return scrollInDirection(toDocument(container)->frame(), type);
 365
 366     if (!container->renderBox())
 367         return false;
 368
 369     if (canScrollInDirection(container, type)) {
 370         LayoutUnit dx = 0;
 371         LayoutUnit dy = 0;
 372         switch (type) {
 373         case FocusTypeLeft:
 374             dx = - std::min<LayoutUnit>(ScrollableArea::pixelsPerLineStep(), container->renderBox()->scrollLeft());
 375             break;
 376         case FocusTypeRight:
 377             ASSERT(container->renderBox()->scrollWidth() > (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
 378             dx = std::min<LayoutUnit>(ScrollableArea::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
 379             break;
 380         case FocusTypeUp:
 381             dy = - std::min<LayoutUnit>(ScrollableArea::pixelsPerLineStep(), container->renderBox()->scrollTop());
 382             break;
 383         case FocusTypeDown:
 384             ASSERT(container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
 385             dy = std::min<LayoutUnit>(ScrollableArea::pixelsPerLineStep(), container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
 386             break;
 387         default:
 388             ASSERT_NOT_REACHED();
 389             return false;
 390         }
 391
 392         container->renderBox()->scrollByRecursively(IntSize(dx, dy));
 393         return true;
 394     }
 395
 396     return false;
 397 }
 398
 399 static void deflateIfOverlapped(LayoutRect& a, LayoutRect& b)
 400 {
 401     if (!a.intersects(b) || a.contains(b) || b.contains(a))
 402         return;
 403
 404     LayoutUnit deflateFactor = -fudgeFactor();
 405
 406     // Avoid negative width or height values.
 407     if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
 408         a.inflate(deflateFactor);
 409
 410     if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
 411         b.inflate(deflateFactor);
 412 }
 413
 414 bool isScrollableNode(const Node* node)
 415 {
 416     ASSERT(!node->isDocumentNode());
 417
 418     if (!node)
 419         return false;
 420
 421     if (RenderObject* renderer = node->renderer())
 422         return renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea() && node->hasChildren();
 423
 424     return false;
 425 }
 426
 427 Node* scrollableEnclosingBoxOrParentFrameForNodeInDirection(FocusType type, Node* node)
 428 {
 429     ASSERT(node);
 430     Node* parent = node;
 431     do {
 432         // FIXME: Spatial navigation is broken for OOPI.
 433         if (parent->isDocumentNode())
 434             parent = toDocument(parent)->frame()->deprecatedLocalOwner();
 435         else
 436             parent = parent->parentOrShadowHostNode();
 437     } while (parent && !canScrollInDirection(parent, type) && !parent->isDocumentNode());
 438
 439     return parent;
 440 }
 441
 442 bool canScrollInDirection(const Node* container, FocusType type)
 443 {
 444     ASSERT(container);
 445     if (container->isDocumentNode())
 446         return canScrollInDirection(toDocument(container)->frame(), type);
 447
 448     if (!isScrollableNode(container))
 449         return false;
 450
 451     switch (type) {
 452     case FocusTypeLeft:
 453         return (container->renderer()->style()->overflowX() != OHIDDEN && container->renderBox()->scrollLeft() > 0);
 454     case FocusTypeUp:
 455         return (container->renderer()->style()->overflowY() != OHIDDEN && container->renderBox()->scrollTop() > 0);
 456     case FocusTypeRight:
 457         return (container->renderer()->style()->overflowX() != OHIDDEN && container->renderBox()->scrollLeft() + container->renderBox()->clientWidth() < container->renderBox()->scrollWidth());
 458     case FocusTypeDown:
 459         return (container->renderer()->style()->overflowY() != OHIDDEN && container->renderBox()->scrollTop() + container->renderBox()->clientHeight() < container->renderBox()->scrollHeight());
 460     default:
 461         ASSERT_NOT_REACHED();
 462         return false;
 463     }
 464 }
 465
 466 bool canScrollInDirection(const LocalFrame* frame, FocusType type)
 467 {
 468     if (!frame->view())
 469         return false;
 470     ScrollbarMode verticalMode;
 471     ScrollbarMode horizontalMode;
 472     frame->view()->calculateScrollbarModesForLayoutAndSetViewportRenderer(horizontalMode, verticalMode);
 473     if ((type == FocusTypeLeft || type == FocusTypeRight) && ScrollbarAlwaysOff == horizontalMode)
 474         return false;
 475     if ((type == FocusTypeUp || type == FocusTypeDown) &&  ScrollbarAlwaysOff == verticalMode)
 476         return false;
 477     LayoutSize size = frame->view()->contentsSize();
 478     LayoutSize offset = frame->view()->scrollOffset();
 479     LayoutRect rect = frame->view()->visibleContentRect(IncludeScrollbars);
 480
 481     switch (type) {
 482     case FocusTypeLeft:
 483         return offset.width() > 0;
 484     case FocusTypeUp:
 485         return offset.height() > 0;
 486     case FocusTypeRight:
 487         return rect.width() + offset.width() < size.width();
 488     case FocusTypeDown:
 489         return rect.height() + offset.height() < size.height();
 490     default:
 491         ASSERT_NOT_REACHED();
 492         return false;
 493     }
 494 }
 495
 496 static LayoutRect rectToAbsoluteCoordinates(LocalFrame* initialFrame, const LayoutRect& initialRect)
 497 {
 498     LayoutRect rect = initialRect;
 499     for (Frame* frame = initialFrame; frame; frame = frame->tree().parent()) {
 500         if (!frame->isLocalFrame())
 501             continue;
 502         // FIXME: Spatial navigation is broken for OOPI.
 503         Element* element = frame->deprecatedLocalOwner();
 504         if (element) {
 505             for (; element; element = element->offsetParent())
 506                 rect.move(element->offsetLeft(), element->offsetTop());
 507             rect.move((-toLocalFrame(frame)->view()->scrollOffset()));
 508         }
 509     }
 510     return rect;
 511 }
 512
 513 LayoutRect nodeRectInAbsoluteCoordinates(Node* node, bool ignoreBorder)
 514 {
 515     ASSERT(node && node->renderer() && !node->document().view()->needsLayout());
 516
 517     if (node->isDocumentNode())
 518         return frameRectInAbsoluteCoordinates(toDocument(node)->frame());
 519     LayoutRect rect = rectToAbsoluteCoordinates(node->document().frame(), node->boundingBox());
 520
 521     // For authors that use border instead of outline in their CSS, we compensate by ignoring the border when calculating
 522     // the rect of the focused element.
 523     if (ignoreBorder) {
 524         rect.move(node->renderer()->style()->borderLeftWidth(), node->renderer()->style()->borderTopWidth());
 525         rect.setWidth(rect.width() - node->renderer()->style()->borderLeftWidth() - node->renderer()->style()->borderRightWidth());
 526         rect.setHeight(rect.height() - node->renderer()->style()->borderTopWidth() - node->renderer()->style()->borderBottomWidth());
 527     }
 528     return rect;
 529 }
 530
 531 LayoutRect frameRectInAbsoluteCoordinates(LocalFrame* frame)
 532 {
 533     return rectToAbsoluteCoordinates(frame, frame->view()->visibleContentRect());
 534 }
 535
 536 // This method calculates the exitPoint from the startingRect and the entryPoint into the candidate rect.
 537 // The line between those 2 points is the closest distance between the 2 rects.
 538 // Takes care of overlapping rects, defining points so that the distance between them
 539 // is zero where necessary
 540 void entryAndExitPointsForDirection(FocusType type, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint)
 541 {
 542     switch (type) {
 543     case FocusTypeLeft:
 544         exitPoint.setX(startingRect.x());
 545         if (potentialRect.maxX() < startingRect.x())
 546             entryPoint.setX(potentialRect.maxX());
 547         else
 548             entryPoint.setX(startingRect.x());
 549         break;
 550     case FocusTypeUp:
 551         exitPoint.setY(startingRect.y());
 552         if (potentialRect.maxY() < startingRect.y())
 553             entryPoint.setY(potentialRect.maxY());
 554         else
 555             entryPoint.setY(startingRect.y());
 556         break;
 557     case FocusTypeRight:
 558         exitPoint.setX(startingRect.maxX());
 559         if (potentialRect.x() > startingRect.maxX())
 560             entryPoint.setX(potentialRect.x());
 561         else
 562             entryPoint.setX(startingRect.maxX());
 563         break;
 564     case FocusTypeDown:
 565         exitPoint.setY(startingRect.maxY());
 566         if (potentialRect.y() > startingRect.maxY())
 567             entryPoint.setY(potentialRect.y());
 568         else
 569             entryPoint.setY(startingRect.maxY());
 570         break;
 571     default:
 572         ASSERT_NOT_REACHED();
 573     }
 574
 575     switch (type) {
 576     case FocusTypeLeft:
 577     case FocusTypeRight:
 578         if (below(startingRect, potentialRect)) {
 579             exitPoint.setY(startingRect.y());
 580             if (potentialRect.maxY() < startingRect.y())
 581                 entryPoint.setY(potentialRect.maxY());
 582             else
 583                 entryPoint.setY(startingRect.y());
 584         } else if (below(potentialRect, startingRect)) {
 585             exitPoint.setY(startingRect.maxY());
 586             if (potentialRect.y() > startingRect.maxY())
 587                 entryPoint.setY(potentialRect.y());
 588             else
 589                 entryPoint.setY(startingRect.maxY());
 590         } else {
 591             exitPoint.setY(max(startingRect.y(), potentialRect.y()));
 592             entryPoint.setY(exitPoint.y());
 593         }
 594         break;
 595     case FocusTypeUp:
 596     case FocusTypeDown:
 597         if (rightOf(startingRect, potentialRect)) {
 598             exitPoint.setX(startingRect.x());
 599             if (potentialRect.maxX() < startingRect.x())
 600                 entryPoint.setX(potentialRect.maxX());
 601             else
 602                 entryPoint.setX(startingRect.x());
 603         } else if (rightOf(potentialRect, startingRect)) {
 604             exitPoint.setX(startingRect.maxX());
 605             if (potentialRect.x() > startingRect.maxX())
 606                 entryPoint.setX(potentialRect.x());
 607             else
 608                 entryPoint.setX(startingRect.maxX());
 609         } else {
 610             exitPoint.setX(max(startingRect.x(), potentialRect.x()));
 611             entryPoint.setX(exitPoint.x());
 612         }
 613         break;
 614     default:
 615         ASSERT_NOT_REACHED();
 616     }
 617 }
 618
 619 bool areElementsOnSameLine(const FocusCandidate& firstCandidate, const FocusCandidate& secondCandidate)
 620 {
 621     if (firstCandidate.isNull() || secondCandidate.isNull())
 622         return false;
 623
 624     if (!firstCandidate.visibleNode->renderer() || !secondCandidate.visibleNode->renderer())
 625         return false;
 626
 627     if (!firstCandidate.rect.intersects(secondCandidate.rect))
 628         return false;
 629
 630     if (isHTMLAreaElement(*firstCandidate.focusableNode) || isHTMLAreaElement(*secondCandidate.focusableNode))
 631         return false;
 632
 633     if (!firstCandidate.visibleNode->renderer()->isRenderInline() || !secondCandidate.visibleNode->renderer()->isRenderInline())
 634         return false;
 635
 636     if (firstCandidate.visibleNode->renderer()->containingBlock() != secondCandidate.visibleNode->renderer()->containingBlock())
 637         return false;
 638
 639     return true;
 640 }
 641
 642 void distanceDataForNode(FocusType type, const FocusCandidate& current, FocusCandidate& candidate)
 643 {
 644     if (areElementsOnSameLine(current, candidate)) {
 645         if ((type == FocusTypeUp && current.rect.y() > candidate.rect.y()) || (type == FocusTypeDown && candidate.rect.y() > current.rect.y())) {
 646             candidate.distance = 0;
 647             candidate.alignment = Full;
 648             return;
 649         }
 650     }
 651
 652     LayoutRect nodeRect = candidate.rect;
 653     LayoutRect currentRect = current.rect;
 654     deflateIfOverlapped(currentRect, nodeRect);
 655
 656     if (!isRectInDirection(type, currentRect, nodeRect))
 657         return;
 658
 659     LayoutPoint exitPoint;
 660     LayoutPoint entryPoint;
 661     entryAndExitPointsForDirection(type, currentRect, nodeRect, exitPoint, entryPoint);
 662
 663     LayoutUnit xAxis = exitPoint.x() - entryPoint.x();
 664     LayoutUnit yAxis = exitPoint.y() - entryPoint.y();
 665
 666     LayoutUnit navigationAxisDistance;
 667     LayoutUnit orthogonalAxisDistance;
 668
 669     switch (type) {
 670     case FocusTypeLeft:
 671     case FocusTypeRight:
 672         navigationAxisDistance = xAxis.abs();
 673         orthogonalAxisDistance = yAxis.abs();
 674         break;
 675     case FocusTypeUp:
 676     case FocusTypeDown:
 677         navigationAxisDistance = yAxis.abs();
 678         orthogonalAxisDistance = xAxis.abs();
 679         break;
 680     default:
 681         ASSERT_NOT_REACHED();
 682         return;
 683     }
 684
 685     double euclidianDistancePow2 = (xAxis * xAxis + yAxis * yAxis).toDouble();
 686     LayoutRect intersectionRect = intersection(currentRect, nodeRect);
 687     double overlap = (intersectionRect.width() * intersectionRect.height()).toDouble();
 688
 689     // Distance calculation is based on http://www.w3.org/TR/WICD/#focus-handling
 690     candidate.distance = sqrt(euclidianDistancePow2) + navigationAxisDistance+ orthogonalAxisDistance * 2 - sqrt(overlap);
 691
 692     LayoutSize viewSize = candidate.visibleNode->document().page()->deprecatedLocalMainFrame()->view()->visibleContentRect().size();
 693     candidate.alignment = alignmentForRects(type, currentRect, nodeRect, viewSize);
 694 }
 695
 696 bool canBeScrolledIntoView(FocusType type, const FocusCandidate& candidate)
 697 {
 698     ASSERT(candidate.visibleNode && candidate.isOffscreen);
 699     LayoutRect candidateRect = candidate.rect;
 700     for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
 701         LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
 702         if (!candidateRect.intersects(parentRect)) {
 703             if (((type == FocusTypeLeft || type == FocusTypeRight) && parentNode->renderer()->style()->overflowX() == OHIDDEN)
 704                 || ((type == FocusTypeUp || type == FocusTypeDown) && parentNode->renderer()->style()->overflowY() == OHIDDEN))
 705                 return false;
 706         }
 707         if (parentNode == candidate.enclosingScrollableBox)
 708             return canScrollInDirection(parentNode, type);
 709     }
 710     return true;
 711 }
 712
 713 // The starting rect is the rect of the focused node, in document coordinates.
 714 // Compose a virtual starting rect if there is no focused node or if it is off screen.
 715 // The virtual rect is the edge of the container or frame. We select which
 716 // edge depending on the direction of the navigation.
 717 LayoutRect virtualRectForDirection(FocusType type, const LayoutRect& startingRect, LayoutUnit width)
 718 {
 719     LayoutRect virtualStartingRect = startingRect;
 720     switch (type) {
 721     case FocusTypeLeft:
 722         virtualStartingRect.setX(virtualStartingRect.maxX() - width);
 723         virtualStartingRect.setWidth(width);
 724         break;
 725     case FocusTypeUp:
 726         virtualStartingRect.setY(virtualStartingRect.maxY() - width);
 727         virtualStartingRect.setHeight(width);
 728         break;
 729     case FocusTypeRight:
 730         virtualStartingRect.setWidth(width);
 731         break;
 732     case FocusTypeDown:
 733         virtualStartingRect.setHeight(width);
 734         break;
 735     default:
 736         ASSERT_NOT_REACHED();
 737     }
 738
 739     return virtualStartingRect;
 740 }
 741
 742 LayoutRect virtualRectForAreaElementAndDirection(HTMLAreaElement& area, FocusType type)
 743 {
 744     ASSERT(area.imageElement());
 745     // Area elements tend to overlap more than other focusable elements. We flatten the rect of the area elements
 746     // to minimize the effect of overlapping areas.
 747     LayoutRect rect = virtualRectForDirection(type, rectToAbsoluteCoordinates(area.document().frame(), area.computeRect(area.imageElement()->renderer())), 1);
 748     return rect;
 749 }
 750
 751 HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
 752 {
 753     return candidate.isFrameOwnerElement() ? toHTMLFrameOwnerElement(candidate.visibleNode) : nullptr;
 754 };
 755
 756 } // namespace blink