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