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