218fca3fb3c825ebd49885f744eab02db95e7cf9
[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 "HTMLFrameOwnerElement.h"
36 #include "IntRect.h"
37 #include "Node.h"
38 #include "Page.h"
39 #include "RenderLayer.h"
40 #include "Settings.h"
41
42 namespace WebCore {
43
44 static long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);
45 static IntRect renderRectRelativeToRootDocument(RenderObject*);
46 static RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&, const IntSize& viewSize);
47 static bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);
48 static bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);
49 static bool areRectsMoreThanFullScreenApart(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect, const IntSize& viewSize);
50 static bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);
51 static void deflateIfOverlapped(IntRect&, IntRect&);
52 static bool checkNegativeCoordsForNode(Node*, const IntRect&);
53 static IntRect rectToAbsoluteCoordinates(Frame* initialFrame, const IntRect& rect);
54 static void entryAndExitPointsForDirection(FocusDirection direction, const IntRect& startingRect, const IntRect& potentialRect, IntPoint& exitPoint, IntPoint& entryPoint);
55
56
57 FocusCandidate::FocusCandidate(Node* n)
58     : node(n)
59     , enclosingScrollableBox(0)
60     , distance(maxDistance())
61     , parentDistance(maxDistance())
62     , alignment(None)
63     , parentAlignment(None)
64     , rect(nodeRectInAbsoluteCoordinates(n, true /* ignore border */))
65 {
66 }
67
68 bool isSpatialNavigationEnabled(const Frame* frame)
69 {
70     return (frame && frame->settings() && frame->settings()->isSpatialNavigationEnabled());
71 }
72
73 void distanceDataForNode(FocusDirection direction, Node* start, FocusCandidate& candidate)
74 {
75     RenderObject* startRender = start->renderer();
76     if (!startRender) {
77         candidate.distance = maxDistance();
78         return;
79     }
80
81     RenderObject* destRender = candidate.node->renderer();
82     if (!destRender) {
83         candidate.distance = maxDistance();
84         return;
85     }
86
87     IntRect curRect = renderRectRelativeToRootDocument(startRender);
88     IntRect targetRect  = renderRectRelativeToRootDocument(destRender);
89
90     // The bounding rectangle of two consecutive nodes can overlap. In such cases,
91     // deflate both.
92     deflateIfOverlapped(curRect, targetRect);
93
94     // If empty rects or negative width or height, bail out.
95     if (curRect.isEmpty() || targetRect.isEmpty()
96      || targetRect.width() <= 0 || targetRect.height() <= 0) {
97         candidate.distance = maxDistance();
98         return;
99     }
100
101     // Negative coordinates can be used if node is scrolled up offscreen.
102     if (!checkNegativeCoordsForNode(start, curRect)) {
103         candidate.distance = maxDistance();
104         return;
105     }
106
107     if (!checkNegativeCoordsForNode(candidate.node, targetRect)) {
108         candidate.distance = maxDistance();
109         return;
110     }
111
112     if (!isRectInDirection(direction, curRect, targetRect)) {
113         candidate.distance = maxDistance();
114         return;
115     }
116
117     // The distance between two nodes is not to be considered alone when evaluating/looking
118     // for the best focus candidate node. Alignment of rects can be also a good point to be
119     // considered in order to make the algorithm to behavior in a more intuitive way.
120     IntSize viewSize = candidate.node->document()->page()->mainFrame()->view()->visibleContentRect().size();
121     candidate.alignment = alignmentForRects(direction, curRect, targetRect, viewSize);
122     candidate.distance = spatialDistance(direction, curRect, targetRect);
123 }
124
125 // FIXME: This function does not behave correctly with transformed frames.
126 static IntRect renderRectRelativeToRootDocument(RenderObject* render)
127 {
128     ASSERT(render && render->node());
129
130     IntRect rect = render->node()->getRect();
131
132     // In cases when the |render|'s associated node is in a scrollable inner
133     // document, we only consider its scrollOffset if it is not offscreen.
134     Node* node = render->node();
135     Document* mainDocument = node->document()->page()->mainFrame()->document();
136     bool considerScrollOffset = !(hasOffscreenRect(node) && node->document() != mainDocument);
137
138     if (considerScrollOffset) {
139         if (FrameView* frameView = render->node()->document()->view())
140             rect.move(-frameView->scrollOffset());
141     }
142
143     // Handle nested frames.
144     for (Frame* frame = render->document()->frame(); frame; frame = frame->tree()->parent()) {
145         if (Element* element = static_cast<Element*>(frame->ownerElement())) {
146             do {
147                 rect.move(element->offsetLeft(), element->offsetTop());
148             } while ((element = element->offsetParent()));
149         }
150     }
151
152     return rect;
153 }
154
155 static RectsAlignment alignmentForRects(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect, const IntSize& viewSize)
156 {
157     // If we found a node in full alignment, but it is too far away, ignore it.
158     if (areRectsMoreThanFullScreenApart(direction, curRect, targetRect, viewSize))
159         return None;
160
161     if (areRectsFullyAligned(direction, curRect, targetRect))
162         return Full;
163
164     if (areRectsPartiallyAligned(direction, curRect, targetRect))
165         return Partial;
166
167     return None;
168 }
169
170 static inline bool isHorizontalMove(FocusDirection direction)
171 {
172     return direction == FocusDirectionLeft || direction == FocusDirectionRight;
173 }
174
175 static inline int start(FocusDirection direction, const IntRect& rect)
176 {
177     return isHorizontalMove(direction) ? rect.y() : rect.x();
178 }
179
180 static inline int middle(FocusDirection direction, const IntRect& rect)
181 {
182     IntPoint center(rect.center());
183     return isHorizontalMove(direction) ? center.y(): center.x();
184 }
185
186 static inline int end(FocusDirection direction, const IntRect& rect)
187 {
188     return isHorizontalMove(direction) ? rect.bottom() : rect.right();
189 }
190
191 // This method checks if rects |a| and |b| are fully aligned either vertically or
192 // horizontally. In general, rects whose central point falls between the top or
193 // bottom of each other are considered fully aligned.
194 // Rects that match this criteria are preferable target nodes in move focus changing
195 // operations.
196 // * a = Current focused node's rect.
197 // * b = Focus candidate node's rect.
198 static bool areRectsFullyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
199 {
200     int aStart, bStart, aEnd, bEnd;
201
202     switch (direction) {
203     case FocusDirectionLeft:
204         aStart = a.x();
205         bEnd = b.right();
206         break;
207     case FocusDirectionRight:
208         aStart = b.x();
209         bEnd = a.right();
210         break;
211     case FocusDirectionUp:
212         aStart = a.y();
213         bEnd = b.y();
214         break;
215     case FocusDirectionDown:
216         aStart = b.y();
217         bEnd = a.y();
218         break;
219     default:
220         ASSERT_NOT_REACHED();
221         return false;
222     }
223
224     if (aStart < bEnd)
225         return false;
226
227     aStart = start(direction, a);
228     bStart = start(direction, b);
229
230     int aMiddle = middle(direction, a);
231     int bMiddle = middle(direction, b);
232
233     aEnd = end(direction, a);
234     bEnd = end(direction, b);
235
236     // Picture of the totally aligned logic:
237     //
238     //     Horizontal    Vertical        Horizontal     Vertical
239     //  ****************************  *****************************
240     //  *  _          *   _ _ _ _  *  *         _   *      _ _    *
241     //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *
242     //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *
243     //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *
244     //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *
245     //  *             *    |_|_|   *  *             *   |_|_|_|_| *
246     //  *             *            *  *             *             *
247     //  ****************************  *****************************
248
249     //     Horizontal    Vertical        Horizontal     Vertical
250     //  ****************************  *****************************
251     //  *  _......_   *   _ _ _ _  *  *  _          *    _ _ _ _  *
252     //  * |_|    |_|  *  |_|_|_|_| *  * |_|     _   *   |_|_|_|_| *
253     //  * |_|    |_|  *  .         *  * |_|    |_|  *           . *
254     //  * |_|        (3) .         *  * |_|....|_| (4)          . *
255     //  *             *  ._ _      *  *             *        _ _. *
256     //  *             *  |_|_|     *  *             *       |_|_| *
257     //  *             *            *  *             *             *
258     //  ****************************  *****************************
259
260     return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)
261             || (aMiddle >= bStart && aMiddle <= bEnd) // (2)
262             || (bStart == aStart) // (3)
263             || (bEnd == aEnd)); // (4)
264 }
265
266 // This method checks if |start| and |dest| have a partial intersection, either
267 // horizontally or vertically.
268 // * a = Current focused node's rect.
269 // * b = Focus candidate node's rect.
270 static bool areRectsPartiallyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)
271 {
272     int aStart  = start(direction, a);
273     int bStart  = start(direction, b);
274     int bMiddle = middle(direction, b);
275     int aEnd = end(direction, a);
276     int bEnd = end(direction, b);
277
278     // Picture of the partially aligned logic:
279     //
280     //    Horizontal       Vertical
281     // ********************************
282     // *  _            *   _ _ _      *
283     // * |_|           *  |_|_|_|     *
284     // * |_|.... _     *      . .     *
285     // * |_|    |_|    *      . .     *
286     // * |_|....|_|    *      ._._ _  *
287     // *        |_|    *      |_|_|_| *
288     // *        |_|    *              *
289     // *               *              *
290     // ********************************
291     //
292     // ... and variants of the above cases.
293     return ((bStart >= aStart && bStart <= aEnd)
294             || (bStart >= aStart && bStart <= aEnd)
295             || (bEnd >= aStart && bEnd <= aEnd)
296             || (bMiddle >= aStart && bMiddle <= aEnd)
297             || (bEnd >= aStart && bEnd <= aEnd));
298 }
299
300 static bool areRectsMoreThanFullScreenApart(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect, const IntSize& viewSize)
301 {
302     ASSERT(isRectInDirection(direction, curRect, targetRect));
303
304     switch (direction) {
305     case FocusDirectionLeft:
306         return curRect.x() - targetRect.right() > viewSize.width();
307     case FocusDirectionRight:
308         return targetRect.x() - curRect.right() > viewSize.width();
309     case FocusDirectionUp:
310         return curRect.y() - targetRect.bottom() > viewSize.height();
311     case FocusDirectionDown:
312         return targetRect.y() - curRect.bottom() > viewSize.height();
313     default:
314         ASSERT_NOT_REACHED();
315         return true;
316     }
317 }
318
319 // Return true if rect |a| is below |b|. False otherwise.
320 static inline bool below(const IntRect& a, const IntRect& b)
321 {
322     return a.y() > b.bottom();
323 }
324
325 // Return true if rect |a| is on the right of |b|. False otherwise.
326 static inline bool rightOf(const IntRect& a, const IntRect& b)
327 {
328     return a.x() > b.right();
329 }
330
331 // * a = Current focused node's rect.
332 // * b = Focus candidate node's rect.
333 static long long spatialDistance(FocusDirection direction, const IntRect& a, const IntRect& b)
334 {
335     int x1 = 0, y1 = 0, x2 = 0, y2 = 0;
336
337     if (direction == FocusDirectionLeft) {
338         // #1  |--|
339         //
340         // #2  |--|  |--|
341         //
342         // #3  |--|
343
344         x1 = a.x();
345         x2 = b.right();
346
347         if (below(a, b)) {
348             // #1 The a rect is below b.
349             y1 = a.y();
350             y2 = b.bottom();
351         } else if (below(b, a)) {
352             // #3 The b rect is below a.
353             y1 = a.bottom();
354             y2 = b.y();
355         } else {
356             // #2 Both b and a share some common y's.
357             y1 = 0;
358             y2 = 0;
359         }
360     } else if (direction == FocusDirectionRight) {
361         //        |--|  #1
362         //
363         //  |--|  |--|  #2
364         //
365         //        |--|  #3
366
367         x1 = a.right();
368         x2 = b.x();
369
370         if (below(a, b)) {
371             // #1 The b rect is above a.
372             y1 = a.y();
373             y2 = b.bottom();
374         } else if (below(b, a)) {
375             // #3 The b rect is below a.
376             y1 = a.bottom();
377             y2 = b.y();
378         } else {
379             // #2 Both b and a share some common y's.
380             y1 = 0;
381             y2 = 0;
382         }
383     } else if (direction == FocusDirectionUp) {
384         //
385         //   #1    #2    #3
386         //
387         //  |--|  |--|  |--|
388         //
389         //        |--|
390
391         y1 = a.y();
392         y2 = b.bottom();
393
394         if (rightOf(a, b)) {
395             // #1 The b rect is to the left of a.
396             x1 = a.x();
397             x2 = b.right();
398         } else if (rightOf(b, a)) {
399             // #3 The b rect is to the right of a.
400             x1 = a.right();
401             x2 = b.x();
402         } else {
403             // #2 Both b and a share some common x's.
404             x1 = 0;
405             x2 = 0;
406         }
407     } else if (direction == FocusDirectionDown) {
408         //        |--|
409         //
410         //  |--|  |--|  |--|
411         //
412         //   #1    #2    #3
413
414         y1 = a.bottom();
415         y2 = b.y();
416
417         if (rightOf(a, b)) {
418             // #1 The b rect is to the left of a.
419             x1 = a.x();
420             x2 = b.right();
421         } else if (rightOf(b, a)) {
422             // #3 The b rect is to the right of a
423             x1 = a.right();
424             x2 = b.x();
425         } else {
426             // #2 Both b and a share some common x's.
427             x1 = 0;
428             x2 = 0;
429         }
430     }
431
432     long long dx = x1 - x2;
433     long long dy = y1 - y2;
434
435     long long distance = (dx * dx) + (dy * dy);
436
437     if (distance < 0)
438         distance *= -1;
439
440     return distance;
441 }
442
443 static bool isRectInDirection(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)
444 {
445     switch (direction) {
446     case FocusDirectionLeft:
447         return targetRect.right() <= curRect.x();
448     case FocusDirectionRight:
449         return targetRect.x() >= curRect.right();
450     case FocusDirectionUp:
451         return targetRect.bottom() <= curRect.y();
452     case FocusDirectionDown:
453         return targetRect.y() >= curRect.bottom();
454     default:
455         ASSERT_NOT_REACHED();
456         return false;
457     }
458 }
459
460 // Checks if |node| is offscreen the visible area (viewport) of its container
461 // document. In case it is, one can scroll in direction or take any different
462 // desired action later on.
463 bool hasOffscreenRect(Node* node, FocusDirection direction)
464 {
465     // Get the FrameView in which |node| is (which means the current viewport if |node|
466     // is not in an inner document), so we can check if its content rect is visible
467     // before we actually move the focus to it.
468     FrameView* frameView = node->document()->view();
469     if (!frameView)
470         return true;
471
472     IntRect containerViewportRect = frameView->visibleContentRect();
473     // We want to select a node if it is currently off screen, but will be
474     // exposed after we scroll. Adjust the viewport to post-scrolling position.
475     // If the container has overflow:hidden, we cannot scroll, so we do not pass direction
476     // and we do not adjust for scrolling.
477     switch (direction) {
478     case FocusDirectionLeft:
479         containerViewportRect.setX(containerViewportRect.x() - Scrollbar::pixelsPerLineStep());
480         containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
481         break;
482     case FocusDirectionRight:
483         containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
484         break;
485     case FocusDirectionUp:
486         containerViewportRect.setY(containerViewportRect.y() - Scrollbar::pixelsPerLineStep());
487         containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
488         break;
489     case FocusDirectionDown:
490         containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
491         break;
492     default:
493         break;
494     }
495
496     RenderObject* render = node->renderer();
497     if (!render)
498         return true;
499
500     IntRect rect(render->absoluteClippedOverflowRect());
501     if (rect.isEmpty())
502         return true;
503
504     return !containerViewportRect.intersects(rect);
505 }
506
507 bool scrollInDirection(Frame* frame, FocusDirection direction)
508 {
509     ASSERT(frame && canScrollInDirection(direction, frame->document()));
510
511     if (frame && canScrollInDirection(direction, frame->document())) {
512         int dx = 0;
513         int dy = 0;
514         switch (direction) {
515         case FocusDirectionLeft:
516             dx = - Scrollbar::pixelsPerLineStep();
517             break;
518         case FocusDirectionRight:
519             dx = Scrollbar::pixelsPerLineStep();
520             break;
521         case FocusDirectionUp:
522             dy = - Scrollbar::pixelsPerLineStep();
523             break;
524         case FocusDirectionDown:
525             dy = Scrollbar::pixelsPerLineStep();
526             break;
527         default:
528             ASSERT_NOT_REACHED();
529             return false;
530         }
531
532         frame->view()->scrollBy(IntSize(dx, dy));
533         return true;
534     }
535     return false;
536 }
537
538 bool scrollInDirection(Node* container, FocusDirection direction)
539 {
540     if (container->isDocumentNode())
541         return scrollInDirection(static_cast<Document*>(container)->frame(), direction);
542
543     if (!container->renderBox())
544         return false;
545
546     if (container && canScrollInDirection(direction, container)) {
547         int dx = 0;
548         int dy = 0;
549         switch (direction) {
550         case FocusDirectionLeft:
551             dx = - min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollLeft());
552             break;
553         case FocusDirectionRight:
554             ASSERT(container->renderBox()->scrollWidth() > (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
555             dx = min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
556             break;
557         case FocusDirectionUp:
558             dy = - min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollTop());
559             break;
560         case FocusDirectionDown:
561             ASSERT(container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
562             dy = min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
563             break;
564         default:
565             ASSERT_NOT_REACHED();
566             return false;
567         }
568
569         container->renderBox()->enclosingLayer()->scrollByRecursively(dx, dy);
570         return true;
571     }
572     return false;
573 }
574
575 void scrollIntoView(Element* element)
576 {
577     // NOTE: Element's scrollIntoView method could had been used here, but
578     // it is preferable to inflate |element|'s bounding rect a bit before
579     // scrolling it for accurate reason.
580     // Element's scrollIntoView method does not provide this flexibility.
581     IntRect bounds = element->getRect();
582     bounds.inflate(fudgeFactor());
583     element->renderer()->enclosingLayer()->scrollRectToVisible(bounds);
584 }
585
586 bool isInRootDocument(Node* node)
587 {
588     if (!node)
589         return false;
590
591     Document* rootDocument = node->document()->page()->mainFrame()->document();
592     return node->document() == rootDocument;
593 }
594
595 static void deflateIfOverlapped(IntRect& a, IntRect& b)
596 {
597     if (!a.intersects(b) || a.contains(b) || b.contains(a))
598         return;
599
600     int deflateFactor = -fudgeFactor();
601
602     // Avoid negative width or height values.
603     if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
604         a.inflate(deflateFactor);
605
606     if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
607         b.inflate(deflateFactor);
608 }
609
610 static bool checkNegativeCoordsForNode(Node* node, const IntRect& curRect)
611 {
612     ASSERT(node || node->renderer());
613
614     if (curRect.x() >= 0 && curRect.y() >= 0)
615         return true;
616
617     bool canBeScrolled = false;
618
619     RenderObject* renderer = node->renderer();
620     for (; renderer; renderer = renderer->parent()) {
621         if (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()) {
622             canBeScrolled = true;
623             break;
624         }
625     }
626
627     return canBeScrolled;
628 }
629
630 bool isScrollableContainerNode(const Node* node)
631 {
632     if (!node)
633         return false;
634
635     if (RenderObject* renderer = node->renderer()) {
636         return (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()
637              && node->hasChildNodes() && !node->isDocumentNode());
638     }
639
640     return false;
641 }
642
643 bool isNodeDeepDescendantOfDocument(Node* node, Document* baseDocument)
644 {
645     if (!node || !baseDocument)
646         return false;
647
648     bool descendant = baseDocument == node->document();
649
650     Element* currentElement = static_cast<Element*>(node);
651     while (!descendant) {
652         Element* documentOwner = currentElement->document()->ownerElement();
653         if (!documentOwner)
654             break;
655
656         descendant = documentOwner->document() == baseDocument;
657         currentElement = documentOwner;
658     }
659
660     return descendant;
661 }
662
663 Node* scrollableEnclosingBoxOrParentFrameForNodeInDirection(FocusDirection direction, Node* node)
664 {
665     ASSERT(node);
666     Node* parent = node;
667     do {
668         if (parent->isDocumentNode())
669             parent = static_cast<Document*>(parent)->document()->frame()->ownerElement();
670         else
671             parent = parent->parentNode();
672     } while (parent && !canScrollInDirection(direction, parent) && !parent->isDocumentNode());
673
674     return parent;
675 }
676
677 bool canScrollInDirection(FocusDirection direction, const Node* container)
678 {
679     ASSERT(container);
680     if (container->isDocumentNode())
681         return canScrollInDirection(direction, static_cast<const Document*>(container)->frame());
682
683     if (!isScrollableContainerNode(container))
684         return false;
685
686     switch (direction) {
687     case FocusDirectionLeft:
688         return (container->renderer()->style()->overflowX() != OHIDDEN && container->renderBox()->scrollLeft() > 0);
689     case FocusDirectionUp:
690         return (container->renderer()->style()->overflowY() != OHIDDEN && container->renderBox()->scrollTop() > 0);
691     case FocusDirectionRight:
692         return (container->renderer()->style()->overflowX() != OHIDDEN && container->renderBox()->scrollLeft() + container->renderBox()->clientWidth() < container->renderBox()->scrollWidth());
693     case FocusDirectionDown:
694         return (container->renderer()->style()->overflowY() != OHIDDEN && container->renderBox()->scrollTop() + container->renderBox()->clientHeight() < container->renderBox()->scrollHeight());
695     default:
696         ASSERT_NOT_REACHED();
697         return false;
698     }
699 }
700
701 bool canScrollInDirection(FocusDirection direction, const Frame* frame)
702 {
703     if (!frame->view())
704         return false;
705     ScrollbarMode verticalMode;
706     ScrollbarMode horizontalMode;
707     frame->view()->calculateScrollbarModesForLayout(horizontalMode, verticalMode);
708     if ((direction == FocusDirectionLeft || direction == FocusDirectionRight) && ScrollbarAlwaysOff == horizontalMode)
709         return false;
710     if ((direction == FocusDirectionUp || direction == FocusDirectionDown) &&  ScrollbarAlwaysOff == verticalMode)
711         return false;
712     IntSize size = frame->view()->contentsSize();
713     IntSize offset = frame->view()->scrollOffset();
714     IntRect rect = frame->view()->visibleContentRect(true);
715
716     switch (direction) {
717     case FocusDirectionLeft:
718         return offset.width() > 0;
719     case FocusDirectionUp:
720         return offset.height() > 0;
721     case FocusDirectionRight:
722         return rect.width() + offset.width() < size.width();
723     case FocusDirectionDown:
724         return rect.height() + offset.height() < size.height();
725     default:
726         ASSERT_NOT_REACHED();
727         return false;
728     }
729 }
730
731 static IntRect rectToAbsoluteCoordinates(Frame* initialFrame, const IntRect& initialRect)
732 {
733     IntRect rect = initialRect;
734     for (Frame* frame = initialFrame; frame; frame = frame->tree()->parent()) {
735         if (Element* element = static_cast<Element*>(frame->ownerElement())) {
736             do {
737                 rect.move(element->offsetLeft(), element->offsetTop());
738             } while ((element = element->offsetParent()));
739             rect.move((-frame->view()->scrollOffset()));
740         }
741     }
742     return rect;
743 }
744
745 IntRect nodeRectInAbsoluteCoordinates(Node* node, bool ignoreBorder)
746 {
747     ASSERT(node && node->renderer());
748
749     if (node->isDocumentNode())
750         return frameRectInAbsoluteCoordinates(static_cast<Document*>(node)->frame());
751     IntRect rect = rectToAbsoluteCoordinates(node->document()->frame(), node->getRect());
752
753     // For authors that use border instead of outline in their CSS, we compensate by ignoring the border when calculating
754     // the rect of the focused element.
755     if (ignoreBorder) {
756         rect.move(node->renderer()->style()->borderLeftWidth(), node->renderer()->style()->borderTopWidth());
757         rect.setWidth(rect.width() - node->renderer()->style()->borderLeftWidth() - node->renderer()->style()->borderRightWidth());
758         rect.setHeight(rect.height() - node->renderer()->style()->borderTopWidth() - node->renderer()->style()->borderBottomWidth());
759     }
760     return rect;
761 }
762
763 IntRect frameRectInAbsoluteCoordinates(Frame* frame)
764 {
765     return rectToAbsoluteCoordinates(frame, frame->view()->visibleContentRect());
766 }
767
768 // This method calculates the exitPoint from the startingRect and the entryPoint into the candidate rect.
769 // The line between those 2 points is the closest distance between the 2 rects.
770 void entryAndExitPointsForDirection(FocusDirection direction, const IntRect& startingRect, const IntRect& potentialRect, IntPoint& exitPoint, IntPoint& entryPoint)
771 {
772     switch (direction) {
773     case FocusDirectionLeft:
774         exitPoint.setX(startingRect.x());
775         entryPoint.setX(potentialRect.right());
776         break;
777     case FocusDirectionUp:
778         exitPoint.setY(startingRect.y());
779         entryPoint.setY(potentialRect.bottom());
780         break;
781     case FocusDirectionRight:
782         exitPoint.setX(startingRect.right());
783         entryPoint.setX(potentialRect.x());
784         break;
785     case FocusDirectionDown:
786         exitPoint.setY(startingRect.bottom());
787         entryPoint.setY(potentialRect.y());
788         break;
789     default:
790         ASSERT_NOT_REACHED();
791     }
792
793     switch (direction) {
794     case FocusDirectionLeft:
795     case FocusDirectionRight:
796         if (below(startingRect, potentialRect)) {
797             exitPoint.setY(startingRect.y());
798             entryPoint.setY(potentialRect.bottom());
799         } else if (below(potentialRect, startingRect)) {
800             exitPoint.setY(startingRect.bottom());
801             entryPoint.setY(potentialRect.y());
802         } else {
803             exitPoint.setY(max(startingRect.y(), potentialRect.y()));
804             entryPoint.setY(exitPoint.y());
805         }
806         break;
807     case FocusDirectionUp:
808     case FocusDirectionDown:
809         if (rightOf(startingRect, potentialRect)) {
810             exitPoint.setX(startingRect.x());
811             entryPoint.setX(potentialRect.right());
812         } else if (rightOf(potentialRect, startingRect)) {
813             exitPoint.setX(startingRect.right());
814             entryPoint.setX(potentialRect.x());
815         } else {
816             exitPoint.setX(max(startingRect.x(), potentialRect.x()));
817             entryPoint.setX(exitPoint.x());
818         }
819         break;
820     default:
821         ASSERT_NOT_REACHED();
822     }
823 }
824
825 void distanceDataForNode(FocusDirection direction, FocusCandidate& current, FocusCandidate& candidate)
826 {
827     if (candidate.isNull())
828         return;
829     if (!candidate.node->renderer())
830         return;
831     IntRect nodeRect = candidate.rect;
832     IntRect currentRect = current.rect;
833     deflateIfOverlapped(currentRect, nodeRect);
834
835     if (!isRectInDirection(direction, currentRect, nodeRect))
836         return;
837
838     IntPoint exitPoint;
839     IntPoint entryPoint;
840     int sameAxisDistance = 0;
841     int otherAxisDistance = 0;
842     entryAndExitPointsForDirection(direction, currentRect, nodeRect, exitPoint, entryPoint);
843
844     switch (direction) {
845     case FocusDirectionLeft:
846         sameAxisDistance = exitPoint.x() - entryPoint.x();
847         otherAxisDistance = abs(exitPoint.y() - entryPoint.y());
848         break;
849     case FocusDirectionUp:
850         sameAxisDistance = exitPoint.y() - entryPoint.y();
851         otherAxisDistance = abs(exitPoint.x() - entryPoint.x());
852         break;
853     case FocusDirectionRight:
854         sameAxisDistance = entryPoint.x() - exitPoint.x();
855         otherAxisDistance = abs(entryPoint.y() - exitPoint.y());
856         break;
857     case FocusDirectionDown:
858         sameAxisDistance = entryPoint.y() - exitPoint.y();
859         otherAxisDistance = abs(entryPoint.x() - exitPoint.x());
860         break;
861     default:
862         ASSERT_NOT_REACHED();
863         return;
864     }
865
866     int x = (entryPoint.x() - exitPoint.x()) * (entryPoint.x() - exitPoint.x());
867     int y = (entryPoint.y() - exitPoint.y()) * (entryPoint.y() - exitPoint.y());
868
869     float euclidianDistance = sqrt((x + y) * 1.0f);
870
871     // Loosely based on http://www.w3.org/TR/WICD/#focus-handling
872     // df = dotDist + dx + dy + 2 * (xdisplacement + ydisplacement) - sqrt(Overlap)
873
874     float distance = euclidianDistance + sameAxisDistance + 2 * otherAxisDistance;
875     candidate.distance = roundf(distance);
876     IntSize viewSize = candidate.node->document()->page()->mainFrame()->view()->visibleContentRect().size();
877     candidate.alignment = alignmentForRects(direction, currentRect, nodeRect, viewSize);
878 }
879
880 bool canBeScrolledIntoView(FocusDirection direction, FocusCandidate& candidate)
881 {
882     ASSERT(candidate.node && hasOffscreenRect(candidate.node));
883     IntRect candidateRect = candidate.rect;
884     for (Node* parentNode = candidate.node->parent(); parentNode; parentNode = parentNode->parent()) {
885         IntRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
886         if (!candidateRect.intersects(parentRect)) {
887             if (((direction == FocusDirectionLeft || direction == FocusDirectionRight) && parentNode->renderer()->style()->overflowX() == OHIDDEN)
888                 || ((direction == FocusDirectionUp || direction == FocusDirectionDown) && parentNode->renderer()->style()->overflowY() == OHIDDEN))
889                 return false;
890         }
891         if (parentNode == candidate.enclosingScrollableBox)
892             return canScrollInDirection(direction, parentNode);
893     }
894     return true;
895 }
896
897 // The starting rect is the rect of the focused node, in document coordinates.
898 // Compose a virtual starting rect if there is no focused node or if it is off screen.
899 // The virtual rect is the edge of the container or frame. We select which
900 // edge depending on the direction of the navigation.
901 IntRect virtualRectForDirection(FocusDirection direction, const IntRect& startingRect)
902 {
903     IntRect virtualStartingRect = startingRect;
904     switch (direction) {
905     case FocusDirectionLeft:
906         virtualStartingRect.setX(virtualStartingRect.right());
907         virtualStartingRect.setWidth(0);
908         break;
909     case FocusDirectionUp:
910         virtualStartingRect.setY(virtualStartingRect.bottom());
911         virtualStartingRect.setHeight(0);
912         break;
913     case FocusDirectionRight:
914         virtualStartingRect.setWidth(0);
915         break;
916     case FocusDirectionDown:
917         virtualStartingRect.setHeight(0);
918         break;
919     default:
920         ASSERT_NOT_REACHED();
921     }
922
923     return virtualStartingRect;
924 }
925
926
927 } // namespace WebCore