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