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