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