Replace static_casts with to* functions for document types.
[WebKit-https.git] / Source / WebCore / page / SpatialNavigation.cpp
1 /*
2  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
3  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>
4  *
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in the
14  *    documentation and/or other materials provided with the distribution.
15  *
16  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
23  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
24  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include "SpatialNavigation.h"
31
32 #include "Frame.h"
33 #include "FrameTree.h"
34 #include "FrameView.h"
35 #include "HTMLAreaElement.h"
36 #include "HTMLImageElement.h"
37 #include "HTMLMapElement.h"
38 #include "HTMLNames.h"
39 #include "IntRect.h"
40 #include "Node.h"
41 #include "Page.h"
42 #include "RenderInline.h"
43 #include "RenderLayer.h"
44 #include "Settings.h"
45
46 namespace WebCore {
47
48 static RectsAlignment alignmentForRects(FocusDirection, const LayoutRect&, const LayoutRect&, const LayoutSize& viewSize);
49 static bool areRectsFullyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
50 static bool areRectsPartiallyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
51 static bool areRectsMoreThanFullScreenApart(FocusDirection, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
52 static bool isRectInDirection(FocusDirection, const LayoutRect&, const LayoutRect&);
53 static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
54 static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect&);
55 static void entryAndExitPointsForDirection(FocusDirection, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint);
56 static bool isScrollableNode(const Node*);
57
58 FocusCandidate::FocusCandidate(Node* node, FocusDirection direction)
59     : visibleNode(0)
60     , focusableNode(0)
61     , enclosingScrollableBox(0)
62     , distance(maxDistance())
63     , parentDistance(maxDistance())
64     , alignment(None)
65     , parentAlignment(None)
66     , isOffscreen(true)
67     , isOffscreenAfterScrolling(true)
68 {
69     ASSERT(node);
70     ASSERT(node->isElementNode());
71
72     if (node->hasTagName(HTMLNames::areaTag)) {
73         HTMLAreaElement* area = static_cast<HTMLAreaElement*>(node);
74         HTMLImageElement* image = area->imageElement();
75         if (!image || !image->renderer())
76             return;
77
78         visibleNode = image;
79         rect = virtualRectForAreaElementAndDirection(area, direction);
80     } else {
81         if (!node->renderer())
82             return;
83
84         visibleNode = node;
85         rect = nodeRectInAbsoluteCoordinates(node, true /* ignore border */);
86     }
87
88     focusableNode = node;
89     isOffscreen = hasOffscreenRect(visibleNode);
90     isOffscreenAfterScrolling = hasOffscreenRect(visibleNode, direction);
91 }
92
93 bool isSpatialNavigationEnabled(const Frame* frame)
94 {
95     return (frame && frame->settings() && frame->settings()->spatialNavigationEnabled());
96 }
97
98 static 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
113 static inline bool isHorizontalMove(FocusDirection direction)
114 {
115     return direction == FocusDirectionLeft || direction == FocusDirectionRight;
116 }
117
118 static inline LayoutUnit start(FocusDirection direction, const LayoutRect& rect)
119 {
120     return isHorizontalMove(direction) ? rect.y() : rect.x();
121 }
122
123 static inline LayoutUnit middle(FocusDirection direction, const LayoutRect& rect)
124 {
125     LayoutPoint center(rect.center());
126     return isHorizontalMove(direction) ? center.y(): center.x();
127 }
128
129 static 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.
141 static 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.
213 static 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             || (bEnd >= aStart && bEnd <= aEnd)
238             || (bMiddle >= aStart && bMiddle <= aEnd)
239             || (bEnd >= aStart && bEnd <= aEnd));
240 }
241
242 static bool areRectsMoreThanFullScreenApart(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
243 {
244     ASSERT(isRectInDirection(direction, curRect, targetRect));
245
246     switch (direction) {
247     case FocusDirectionLeft:
248         return curRect.x() - targetRect.maxX() > viewSize.width();
249     case FocusDirectionRight:
250         return targetRect.x() - curRect.maxX() > viewSize.width();
251     case FocusDirectionUp:
252         return curRect.y() - targetRect.maxY() > viewSize.height();
253     case FocusDirectionDown:
254         return targetRect.y() - curRect.maxY() > viewSize.height();
255     default:
256         ASSERT_NOT_REACHED();
257         return true;
258     }
259 }
260
261 // Return true if rect |a| is below |b|. False otherwise.
262 static inline bool below(const LayoutRect& a, const LayoutRect& b)
263 {
264     return a.y() > b.maxY();
265 }
266
267 // Return true if rect |a| is on the right of |b|. False otherwise.
268 static inline bool rightOf(const LayoutRect& a, const LayoutRect& b)
269 {
270     return a.x() > b.maxX();
271 }
272
273 static bool isRectInDirection(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect)
274 {
275     switch (direction) {
276     case FocusDirectionLeft:
277         return targetRect.maxX() <= curRect.x();
278     case FocusDirectionRight:
279         return targetRect.x() >= curRect.maxX();
280     case FocusDirectionUp:
281         return targetRect.maxY() <= curRect.y();
282     case FocusDirectionDown:
283         return targetRect.y() >= curRect.maxY();
284     default:
285         ASSERT_NOT_REACHED();
286         return false;
287     }
288 }
289
290 // Checks if |node| is offscreen the visible area (viewport) of its container
291 // document. In case it is, one can scroll in direction or take any different
292 // desired action later on.
293 bool hasOffscreenRect(Node* node, FocusDirection direction)
294 {
295     // Get the FrameView in which |node| is (which means the current viewport if |node|
296     // is not in an inner document), so we can check if its content rect is visible
297     // before we actually move the focus to it.
298     FrameView* frameView = node->document()->view();
299     if (!frameView)
300         return true;
301
302     ASSERT(!frameView->needsLayout());
303
304     LayoutRect containerViewportRect = frameView->visibleContentRect();
305     // We want to select a node if it is currently off screen, but will be
306     // exposed after we scroll. Adjust the viewport to post-scrolling position.
307     // If the container has overflow:hidden, we cannot scroll, so we do not pass direction
308     // and we do not adjust for scrolling.
309     switch (direction) {
310     case FocusDirectionLeft:
311         containerViewportRect.setX(containerViewportRect.x() - Scrollbar::pixelsPerLineStep());
312         containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
313         break;
314     case FocusDirectionRight:
315         containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
316         break;
317     case FocusDirectionUp:
318         containerViewportRect.setY(containerViewportRect.y() - Scrollbar::pixelsPerLineStep());
319         containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
320         break;
321     case FocusDirectionDown:
322         containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
323         break;
324     default:
325         break;
326     }
327
328     RenderObject* render = node->renderer();
329     if (!render)
330         return true;
331
332     LayoutRect rect(render->absoluteClippedOverflowRect());
333     if (rect.isEmpty())
334         return true;
335
336     return !containerViewportRect.intersects(rect);
337 }
338
339 bool scrollInDirection(Frame* frame, FocusDirection direction)
340 {
341     ASSERT(frame);
342
343     if (frame && canScrollInDirection(frame->document(), direction)) {
344         LayoutUnit dx = 0;
345         LayoutUnit dy = 0;
346         switch (direction) {
347         case FocusDirectionLeft:
348             dx = - Scrollbar::pixelsPerLineStep();
349             break;
350         case FocusDirectionRight:
351             dx = Scrollbar::pixelsPerLineStep();
352             break;
353         case FocusDirectionUp:
354             dy = - Scrollbar::pixelsPerLineStep();
355             break;
356         case FocusDirectionDown:
357             dy = Scrollbar::pixelsPerLineStep();
358             break;
359         default:
360             ASSERT_NOT_REACHED();
361             return false;
362         }
363
364         frame->view()->scrollBy(IntSize(dx, dy));
365         return true;
366     }
367     return false;
368 }
369
370 bool scrollInDirection(Node* container, FocusDirection direction)
371 {
372     ASSERT(container);
373     if (container->isDocumentNode())
374         return scrollInDirection(toDocument(container)->frame(), direction);
375
376     if (!container->renderBox())
377         return false;
378
379     if (canScrollInDirection(container, direction)) {
380         LayoutUnit dx = 0;
381         LayoutUnit dy = 0;
382         switch (direction) {
383         case FocusDirectionLeft:
384             dx = - min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollLeft());
385             break;
386         case FocusDirectionRight:
387             ASSERT(container->renderBox()->scrollWidth() > (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
388             dx = min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
389             break;
390         case FocusDirectionUp:
391             dy = - min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollTop());
392             break;
393         case FocusDirectionDown:
394             ASSERT(container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
395             dy = min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
396             break;
397         default:
398             ASSERT_NOT_REACHED();
399             return false;
400         }
401
402         container->renderBox()->enclosingLayer()->scrollByRecursively(IntSize(dx, dy));
403         return true;
404     }
405
406     return false;
407 }
408
409 static void deflateIfOverlapped(LayoutRect& a, LayoutRect& b)
410 {
411     if (!a.intersects(b) || a.contains(b) || b.contains(a))
412         return;
413
414     LayoutUnit deflateFactor = -fudgeFactor();
415
416     // Avoid negative width or height values.
417     if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
418         a.inflate(deflateFactor);
419
420     if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
421         b.inflate(deflateFactor);
422 }
423
424 bool isScrollableNode(const Node* node)
425 {
426     ASSERT(!node->isDocumentNode());
427
428     if (!node)
429         return false;
430
431     if (RenderObject* renderer = node->renderer())
432         return renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea() && node->hasChildNodes();
433
434     return false;
435 }
436
437 Node* scrollableEnclosingBoxOrParentFrameForNodeInDirection(FocusDirection direction, Node* node)
438 {
439     ASSERT(node);
440     Node* parent = node;
441     do {
442         if (parent->isDocumentNode())
443             parent = toDocument(parent)->document()->frame()->ownerElement();
444         else
445             parent = parent->parentNode();
446     } while (parent && !canScrollInDirection(parent, direction) && !parent->isDocumentNode());
447
448     return parent;
449 }
450
451 bool canScrollInDirection(const Node* container, FocusDirection direction)
452 {
453     ASSERT(container);
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
475 bool 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()->contentsSize();
487     LayoutSize offset = frame->view()->scrollOffset();
488     LayoutRect rect = frame->view()->visibleContentRect(ScrollableArea::IncludeScrollbars);
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
505 static 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 = static_cast<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
519 LayoutRect 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
537 LayoutRect 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.
544 void 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(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(max(startingRect.x(), potentialRect.x()));
591             entryPoint.setX(exitPoint.x());
592         }
593         break;
594     default:
595         ASSERT_NOT_REACHED();
596     }
597 }
598
599 bool 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 (firstCandidate.focusableNode->hasTagName(HTMLNames::areaTag) || secondCandidate.focusableNode->hasTagName(HTMLNames::areaTag))
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 void distanceDataForNode(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
623 {
624     if (areElementsOnSameLine(current, candidate)) {
625         if ((direction == FocusDirectionUp && current.rect.y() > candidate.rect.y()) || (direction == FocusDirectionDown && candidate.rect.y() > current.rect.y())) {
626             candidate.distance = 0;
627             candidate.alignment = Full;
628             return;
629         }
630     }
631
632     LayoutRect nodeRect = candidate.rect;
633     LayoutRect currentRect = current.rect;
634     deflateIfOverlapped(currentRect, nodeRect);
635
636     if (!isRectInDirection(direction, currentRect, nodeRect))
637         return;
638
639     LayoutPoint exitPoint;
640     LayoutPoint entryPoint;
641     LayoutUnit sameAxisDistance = 0;
642     LayoutUnit otherAxisDistance = 0;
643     entryAndExitPointsForDirection(direction, currentRect, nodeRect, exitPoint, entryPoint);
644
645     switch (direction) {
646     case FocusDirectionLeft:
647         sameAxisDistance = exitPoint.x() - entryPoint.x();
648         otherAxisDistance = absoluteValue(exitPoint.y() - entryPoint.y());
649         break;
650     case FocusDirectionUp:
651         sameAxisDistance = exitPoint.y() - entryPoint.y();
652         otherAxisDistance = absoluteValue(exitPoint.x() - entryPoint.x());
653         break;
654     case FocusDirectionRight:
655         sameAxisDistance = entryPoint.x() - exitPoint.x();
656         otherAxisDistance = absoluteValue(entryPoint.y() - exitPoint.y());
657         break;
658     case FocusDirectionDown:
659         sameAxisDistance = entryPoint.y() - exitPoint.y();
660         otherAxisDistance = absoluteValue(entryPoint.x() - exitPoint.x());
661         break;
662     default:
663         ASSERT_NOT_REACHED();
664         return;
665     }
666
667     float x = (entryPoint.x() - exitPoint.x()) * (entryPoint.x() - exitPoint.x());
668     float y = (entryPoint.y() - exitPoint.y()) * (entryPoint.y() - exitPoint.y());
669
670     float euclidianDistance = sqrt(x + y);
671
672     // Loosely based on http://www.w3.org/TR/WICD/#focus-handling
673     // df = dotDist + dx + dy + 2 * (xdisplacement + ydisplacement) - sqrt(Overlap)
674
675     float distance = euclidianDistance + sameAxisDistance + 2 * otherAxisDistance;
676     candidate.distance = roundf(distance);
677     LayoutSize viewSize = candidate.visibleNode->document()->page()->mainFrame()->view()->visibleContentRect().size();
678     candidate.alignment = alignmentForRects(direction, currentRect, nodeRect, viewSize);
679 }
680
681 bool canBeScrolledIntoView(FocusDirection direction, const FocusCandidate& candidate)
682 {
683     ASSERT(candidate.visibleNode && candidate.isOffscreen);
684     LayoutRect candidateRect = candidate.rect;
685     for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
686         LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
687         if (!candidateRect.intersects(parentRect)) {
688             if (((direction == FocusDirectionLeft || direction == FocusDirectionRight) && parentNode->renderer()->style()->overflowX() == OHIDDEN)
689                 || ((direction == FocusDirectionUp || direction == FocusDirectionDown) && parentNode->renderer()->style()->overflowY() == OHIDDEN))
690                 return false;
691         }
692         if (parentNode == candidate.enclosingScrollableBox)
693             return canScrollInDirection(parentNode, direction);
694     }
695     return true;
696 }
697
698 // The starting rect is the rect of the focused node, in document coordinates.
699 // Compose a virtual starting rect if there is no focused node or if it is off screen.
700 // The virtual rect is the edge of the container or frame. We select which
701 // edge depending on the direction of the navigation.
702 LayoutRect virtualRectForDirection(FocusDirection direction, const LayoutRect& startingRect, LayoutUnit width)
703 {
704     LayoutRect virtualStartingRect = startingRect;
705     switch (direction) {
706     case FocusDirectionLeft:
707         virtualStartingRect.setX(virtualStartingRect.maxX() - width);
708         virtualStartingRect.setWidth(width);
709         break;
710     case FocusDirectionUp:
711         virtualStartingRect.setY(virtualStartingRect.maxY() - width);
712         virtualStartingRect.setHeight(width);
713         break;
714     case FocusDirectionRight:
715         virtualStartingRect.setWidth(width);
716         break;
717     case FocusDirectionDown:
718         virtualStartingRect.setHeight(width);
719         break;
720     default:
721         ASSERT_NOT_REACHED();
722     }
723
724     return virtualStartingRect;
725 }
726
727 LayoutRect virtualRectForAreaElementAndDirection(HTMLAreaElement* area, FocusDirection direction)
728 {
729     ASSERT(area);
730     ASSERT(area->imageElement());
731     // Area elements tend to overlap more than other focusable elements. We flatten the rect of the area elements
732     // to minimize the effect of overlapping areas.
733     LayoutRect rect = virtualRectForDirection(direction, rectToAbsoluteCoordinates(area->document()->frame(), area->computeRect(area->imageElement()->renderer())), 1);
734     return rect;
735 }
736
737 HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
738 {
739     return candidate.isFrameOwnerElement() ? static_cast<HTMLFrameOwnerElement*>(candidate.visibleNode) : 0;
740 };
741
742 } // namespace WebCore