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 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 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 "FrameTree.h"
33#include "FrameView.h"
34#include "HTMLAreaElement.h"
35#include "HTMLImageElement.h"
36#include "HTMLMapElement.h"
37#include "HTMLNames.h"
38#include "IntRect.h"
39#include "MainFrame.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 bool areRectsFullyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
49static bool areRectsPartiallyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
50static bool areRectsMoreThanFullScreenApart(FocusDirection, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
51static bool isRectInDirection(FocusDirection, const LayoutRect&, const LayoutRect&);
52static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
53static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect&);
54static void entryAndExitPointsForDirection(FocusDirection, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint);
55static bool isScrollableNode(const Node*);
56
57FocusCandidate::FocusCandidate(Node* node, FocusDirection direction)
58    : visibleNode(0)
59    , focusableNode(0)
60    , enclosingScrollableBox(0)
61    , distance(maxDistance())
62    , alignment(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
90bool isSpatialNavigationEnabled(const Frame* frame)
91{
92    return (frame && frame->settings().spatialNavigationEnabled());
93}
94
95static 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
110static inline bool isHorizontalMove(FocusDirection direction)
111{
112    return direction == FocusDirectionLeft || direction == FocusDirectionRight;
113}
114
115static inline LayoutUnit start(FocusDirection direction, const LayoutRect& rect)
116{
117    return isHorizontalMove(direction) ? rect.y() : rect.x();
118}
119
120static inline LayoutUnit middle(FocusDirection direction, const LayoutRect& rect)
121{
122    LayoutPoint center(rect.center());
123    return isHorizontalMove(direction) ? center.y(): center.x();
124}
125
126static 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.
138static 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.
210static 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            || (bMiddle >= aStart && bMiddle <= aEnd)
235            || (bEnd >= aStart && bEnd <= aEnd));
236}
237
238static 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.
258static 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.
264static inline bool rightOf(const LayoutRect& a, const LayoutRect& b)
265{
266    return a.x() > b.maxX();
267}
268
269static 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.
289bool 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() - Scrollbar::pixelsPerLineStep());
308        containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
309        break;
310    case FocusDirectionRight:
311        containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
312        break;
313    case FocusDirectionUp:
314        containerViewportRect.setY(containerViewportRect.y() - Scrollbar::pixelsPerLineStep());
315        containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
316        break;
317    case FocusDirectionDown:
318        containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::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
335bool 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 = - Scrollbar::pixelsPerLineStep();
345            break;
346        case FocusDirectionRight:
347            dx = Scrollbar::pixelsPerLineStep();
348            break;
349        case FocusDirectionUp:
350            dy = - Scrollbar::pixelsPerLineStep();
351            break;
352        case FocusDirectionDown:
353            dy = Scrollbar::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
366bool 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>(Scrollbar::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>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
385            break;
386        case FocusDirectionUp:
387            dy = - std::min<LayoutUnit>(Scrollbar::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>(Scrollbar::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()->enclosingLayer()->scrollByRecursively(IntSize(dx, dy));
399        return true;
400    }
401
402    return false;
403}
404
405static 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
420bool 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
433Node* 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->parentNode();
442    } while (parent && !canScrollInDirection(parent, direction) && !parent->isDocumentNode());
443
444    return parent;
445}
446
447bool canScrollInDirection(const Node* container, FocusDirection direction)
448{
449    ASSERT(container);
450
451    if (isHTMLSelectElement(container))
452        return false;
453
454    if (container->isDocumentNode())
455        return canScrollInDirection(toDocument(container)->frame(), direction);
456
457    if (!isScrollableNode(container))
458        return false;
459
460    switch (direction) {
461    case FocusDirectionLeft:
462        return (container->renderer()->style().overflowX() != OHIDDEN && container->renderBox()->scrollLeft() > 0);
463    case FocusDirectionUp:
464        return (container->renderer()->style().overflowY() != OHIDDEN && container->renderBox()->scrollTop() > 0);
465    case FocusDirectionRight:
466        return (container->renderer()->style().overflowX() != OHIDDEN && container->renderBox()->scrollLeft() + container->renderBox()->clientWidth() < container->renderBox()->scrollWidth());
467    case FocusDirectionDown:
468        return (container->renderer()->style().overflowY() != OHIDDEN && container->renderBox()->scrollTop() + container->renderBox()->clientHeight() < container->renderBox()->scrollHeight());
469    default:
470        ASSERT_NOT_REACHED();
471        return false;
472    }
473}
474
475bool canScrollInDirection(const Frame* frame, FocusDirection direction)
476{
477    if (!frame->view())
478        return false;
479    ScrollbarMode verticalMode;
480    ScrollbarMode horizontalMode;
481    frame->view()->calculateScrollbarModesForLayout(horizontalMode, verticalMode);
482    if ((direction == FocusDirectionLeft || direction == FocusDirectionRight) && ScrollbarAlwaysOff == horizontalMode)
483        return false;
484    if ((direction == FocusDirectionUp || direction == FocusDirectionDown) &&  ScrollbarAlwaysOff == verticalMode)
485        return false;
486    LayoutSize size = frame->view()->totalContentsSize();
487    LayoutSize offset = frame->view()->scrollOffset();
488    LayoutRect rect = frame->view()->unobscuredContentRectIncludingScrollbars();
489
490    switch (direction) {
491    case FocusDirectionLeft:
492        return offset.width() > 0;
493    case FocusDirectionUp:
494        return offset.height() > 0;
495    case FocusDirectionRight:
496        return rect.width() + offset.width() < size.width();
497    case FocusDirectionDown:
498        return rect.height() + offset.height() < size.height();
499    default:
500        ASSERT_NOT_REACHED();
501        return false;
502    }
503}
504
505static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect& initialRect)
506{
507    LayoutRect rect = initialRect;
508    for (Frame* frame = initialFrame; frame; frame = frame->tree().parent()) {
509        if (Element* element = frame->ownerElement()) {
510            do {
511                rect.move(element->offsetLeft(), element->offsetTop());
512            } while ((element = element->offsetParent()));
513            rect.move((-frame->view()->scrollOffset()));
514        }
515    }
516    return rect;
517}
518
519LayoutRect nodeRectInAbsoluteCoordinates(Node* node, bool ignoreBorder)
520{
521    ASSERT(node && node->renderer() && !node->document().view()->needsLayout());
522
523    if (node->isDocumentNode())
524        return frameRectInAbsoluteCoordinates(toDocument(node)->frame());
525    LayoutRect rect = rectToAbsoluteCoordinates(node->document().frame(), node->boundingBox());
526
527    // For authors that use border instead of outline in their CSS, we compensate by ignoring the border when calculating
528    // the rect of the focused element.
529    if (ignoreBorder) {
530        rect.move(node->renderer()->style().borderLeftWidth(), node->renderer()->style().borderTopWidth());
531        rect.setWidth(rect.width() - node->renderer()->style().borderLeftWidth() - node->renderer()->style().borderRightWidth());
532        rect.setHeight(rect.height() - node->renderer()->style().borderTopWidth() - node->renderer()->style().borderBottomWidth());
533    }
534    return rect;
535}
536
537LayoutRect frameRectInAbsoluteCoordinates(Frame* frame)
538{
539    return rectToAbsoluteCoordinates(frame, frame->view()->visibleContentRect());
540}
541
542// This method calculates the exitPoint from the startingRect and the entryPoint into the candidate rect.
543// The line between those 2 points is the closest distance between the 2 rects.
544void entryAndExitPointsForDirection(FocusDirection direction, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint)
545{
546    switch (direction) {
547    case FocusDirectionLeft:
548        exitPoint.setX(startingRect.x());
549        entryPoint.setX(potentialRect.maxX());
550        break;
551    case FocusDirectionUp:
552        exitPoint.setY(startingRect.y());
553        entryPoint.setY(potentialRect.maxY());
554        break;
555    case FocusDirectionRight:
556        exitPoint.setX(startingRect.maxX());
557        entryPoint.setX(potentialRect.x());
558        break;
559    case FocusDirectionDown:
560        exitPoint.setY(startingRect.maxY());
561        entryPoint.setY(potentialRect.y());
562        break;
563    default:
564        ASSERT_NOT_REACHED();
565    }
566
567    switch (direction) {
568    case FocusDirectionLeft:
569    case FocusDirectionRight:
570        if (below(startingRect, potentialRect)) {
571            exitPoint.setY(startingRect.y());
572            entryPoint.setY(potentialRect.maxY());
573        } else if (below(potentialRect, startingRect)) {
574            exitPoint.setY(startingRect.maxY());
575            entryPoint.setY(potentialRect.y());
576        } else {
577            exitPoint.setY(std::max(startingRect.y(), potentialRect.y()));
578            entryPoint.setY(exitPoint.y());
579        }
580        break;
581    case FocusDirectionUp:
582    case FocusDirectionDown:
583        if (rightOf(startingRect, potentialRect)) {
584            exitPoint.setX(startingRect.x());
585            entryPoint.setX(potentialRect.maxX());
586        } else if (rightOf(potentialRect, startingRect)) {
587            exitPoint.setX(startingRect.maxX());
588            entryPoint.setX(potentialRect.x());
589        } else {
590            exitPoint.setX(std::max(startingRect.x(), potentialRect.x()));
591            entryPoint.setX(exitPoint.x());
592        }
593        break;
594    default:
595        ASSERT_NOT_REACHED();
596    }
597}
598
599bool areElementsOnSameLine(const FocusCandidate& firstCandidate, const FocusCandidate& secondCandidate)
600{
601    if (firstCandidate.isNull() || secondCandidate.isNull())
602        return false;
603
604    if (!firstCandidate.visibleNode->renderer() || !secondCandidate.visibleNode->renderer())
605        return false;
606
607    if (!firstCandidate.rect.intersects(secondCandidate.rect))
608        return false;
609
610    if (isHTMLAreaElement(firstCandidate.focusableNode) || isHTMLAreaElement(secondCandidate.focusableNode))
611        return false;
612
613    if (!firstCandidate.visibleNode->renderer()->isRenderInline() || !secondCandidate.visibleNode->renderer()->isRenderInline())
614        return false;
615
616    if (firstCandidate.visibleNode->renderer()->containingBlock() != secondCandidate.visibleNode->renderer()->containingBlock())
617        return false;
618
619    return true;
620}
621
622// Consider only those nodes as candidate which are exactly in the focus-direction.
623// e.g. If we are moving down then the nodes that are above current focused node should be considered as invalid.
624bool isValidCandidate(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
625{
626    LayoutRect currentRect = current.rect;
627    LayoutRect candidateRect = candidate.rect;
628
629    switch (direction) {
630    case FocusDirectionLeft:
631        return candidateRect.x() < currentRect.maxX();
632    case FocusDirectionUp:
633        return candidateRect.y() < currentRect.maxY();
634    case FocusDirectionRight:
635        return candidateRect.maxX() > currentRect.x();
636    case FocusDirectionDown:
637        return candidateRect.maxY() > currentRect.y();
638    default:
639        ASSERT_NOT_REACHED();
640    }
641    return false;
642}
643
644void distanceDataForNode(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
645{
646    if (areElementsOnSameLine(current, candidate)) {
647        if ((direction == FocusDirectionUp && current.rect.y() > candidate.rect.y()) || (direction == FocusDirectionDown && candidate.rect.y() > current.rect.y())) {
648            candidate.distance = 0;
649            candidate.alignment = Full;
650            return;
651        }
652    }
653
654    LayoutRect nodeRect = candidate.rect;
655    LayoutRect currentRect = current.rect;
656    deflateIfOverlapped(currentRect, nodeRect);
657
658    if (!isRectInDirection(direction, currentRect, nodeRect))
659        return;
660
661    LayoutPoint exitPoint;
662    LayoutPoint entryPoint;
663    LayoutUnit sameAxisDistance = 0;
664    LayoutUnit otherAxisDistance = 0;
665    entryAndExitPointsForDirection(direction, currentRect, nodeRect, exitPoint, entryPoint);
666
667    switch (direction) {
668    case FocusDirectionLeft:
669        sameAxisDistance = exitPoint.x() - entryPoint.x();
670        otherAxisDistance = absoluteValue(exitPoint.y() - entryPoint.y());
671        break;
672    case FocusDirectionUp:
673        sameAxisDistance = exitPoint.y() - entryPoint.y();
674        otherAxisDistance = absoluteValue(exitPoint.x() - entryPoint.x());
675        break;
676    case FocusDirectionRight:
677        sameAxisDistance = entryPoint.x() - exitPoint.x();
678        otherAxisDistance = absoluteValue(entryPoint.y() - exitPoint.y());
679        break;
680    case FocusDirectionDown:
681        sameAxisDistance = entryPoint.y() - exitPoint.y();
682        otherAxisDistance = absoluteValue(entryPoint.x() - exitPoint.x());
683        break;
684    default:
685        ASSERT_NOT_REACHED();
686        return;
687    }
688
689    float x = (entryPoint.x() - exitPoint.x()) * (entryPoint.x() - exitPoint.x());
690    float y = (entryPoint.y() - exitPoint.y()) * (entryPoint.y() - exitPoint.y());
691
692    float euclidianDistance = sqrt(x + y);
693
694    // Loosely based on http://www.w3.org/TR/WICD/#focus-handling
695    // df = dotDist + dx + dy + 2 * (xdisplacement + ydisplacement) - sqrt(Overlap)
696
697    float distance = euclidianDistance + sameAxisDistance + 2 * otherAxisDistance;
698    candidate.distance = roundf(distance);
699    LayoutSize viewSize = candidate.visibleNode->document().page()->mainFrame().view()->visibleContentRect().size();
700    candidate.alignment = alignmentForRects(direction, currentRect, nodeRect, viewSize);
701}
702
703bool canBeScrolledIntoView(FocusDirection direction, const FocusCandidate& candidate)
704{
705    ASSERT(candidate.visibleNode && candidate.isOffscreen);
706    LayoutRect candidateRect = candidate.rect;
707    for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
708        LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
709        if (!candidateRect.intersects(parentRect)) {
710            if (((direction == FocusDirectionLeft || direction == FocusDirectionRight) && parentNode->renderer()->style().overflowX() == OHIDDEN)
711                || ((direction == FocusDirectionUp || direction == FocusDirectionDown) && parentNode->renderer()->style().overflowY() == OHIDDEN))
712                return false;
713        }
714        if (parentNode == candidate.enclosingScrollableBox)
715            return canScrollInDirection(parentNode, direction);
716    }
717    return true;
718}
719
720// The starting rect is the rect of the focused node, in document coordinates.
721// Compose a virtual starting rect if there is no focused node or if it is off screen.
722// The virtual rect is the edge of the container or frame. We select which
723// edge depending on the direction of the navigation.
724LayoutRect virtualRectForDirection(FocusDirection direction, const LayoutRect& startingRect, LayoutUnit width)
725{
726    LayoutRect virtualStartingRect = startingRect;
727    switch (direction) {
728    case FocusDirectionLeft:
729        virtualStartingRect.setX(virtualStartingRect.maxX() - width);
730        virtualStartingRect.setWidth(width);
731        break;
732    case FocusDirectionUp:
733        virtualStartingRect.setY(virtualStartingRect.maxY() - width);
734        virtualStartingRect.setHeight(width);
735        break;
736    case FocusDirectionRight:
737        virtualStartingRect.setWidth(width);
738        break;
739    case FocusDirectionDown:
740        virtualStartingRect.setHeight(width);
741        break;
742    default:
743        ASSERT_NOT_REACHED();
744    }
745
746    return virtualStartingRect;
747}
748
749LayoutRect virtualRectForAreaElementAndDirection(HTMLAreaElement* area, FocusDirection direction)
750{
751    ASSERT(area);
752    ASSERT(area->imageElement());
753    // Area elements tend to overlap more than other focusable elements. We flatten the rect of the area elements
754    // to minimize the effect of overlapping areas.
755    LayoutRect rect = virtualRectForDirection(direction, rectToAbsoluteCoordinates(area->document().frame(), area->computeRect(area->imageElement()->renderer())), 1);
756    return rect;
757}
758
759HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
760{
761    return candidate.isFrameOwnerElement() ? toHTMLFrameOwnerElement(candidate.visibleNode) : nullptr;
762};
763
764} // namespace WebCore
765