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