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