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