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 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 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 "HTMLSelectElement.h"
39#include "IntRect.h"
40#include "Node.h"
41#include "Page.h"
42#include "RenderInline.h"
43#include "RenderLayer.h"
44#include "Settings.h"
45
46namespace WebCore {
47
48static bool areRectsFullyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
49static bool areRectsPartiallyAligned(FocusDirection, const LayoutRect&, const LayoutRect&);
50static bool areRectsMoreThanFullScreenApart(FocusDirection, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize);
51static bool isRectInDirection(FocusDirection, const LayoutRect&, const LayoutRect&);
52static void deflateIfOverlapped(LayoutRect&, LayoutRect&);
53static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect&);
54static void entryAndExitPointsForDirection(FocusDirection, const LayoutRect& startingRect, const LayoutRect& potentialRect, LayoutPoint& exitPoint, LayoutPoint& entryPoint);
55static bool isScrollableNode(const Node*);
56
57FocusCandidate::FocusCandidate(Node* node, FocusDirection direction)
58 : visibleNode(nullptr)
59 , focusableNode(nullptr)
60 , enclosingScrollableBox(nullptr)
61 , distance(maxDistance())
62 , alignment(None)
63 , isOffscreen(true)
64 , isOffscreenAfterScrolling(true)
65{
66 ASSERT(is<Element>(node));
67
68 if (is<HTMLAreaElement>(*node)) {
69 HTMLAreaElement& area = downcast<HTMLAreaElement>(*node);
70 HTMLImageElement* image = area.imageElement();
71 if (!image || !image->renderer())
72 return;
73
74 visibleNode = image;
75 rect = virtualRectForAreaElementAndDirection(&area, direction);
76 } else {
77 if (!node->renderer())
78 return;
79
80 visibleNode = node;
81 rect = nodeRectInAbsoluteCoordinates(node, true /* ignore border */);
82 }
83
84 focusableNode = node;
85 isOffscreen = hasOffscreenRect(visibleNode);
86 isOffscreenAfterScrolling = hasOffscreenRect(visibleNode, direction);
87}
88
89bool isSpatialNavigationEnabled(const Frame* frame)
90{
91 return (frame && frame->settings().spatialNavigationEnabled());
92}
93
94static RectsAlignment alignmentForRects(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
95{
96 // If we found a node in full alignment, but it is too far away, ignore it.
97 if (areRectsMoreThanFullScreenApart(direction, curRect, targetRect, viewSize))
98 return None;
99
100 if (areRectsFullyAligned(direction, curRect, targetRect))
101 return Full;
102
103 if (areRectsPartiallyAligned(direction, curRect, targetRect))
104 return Partial;
105
106 return None;
107}
108
109static inline bool isHorizontalMove(FocusDirection direction)
110{
111 return direction == FocusDirectionLeft || direction == FocusDirectionRight;
112}
113
114static inline LayoutUnit start(FocusDirection direction, const LayoutRect& rect)
115{
116 return isHorizontalMove(direction) ? rect.y() : rect.x();
117}
118
119static inline LayoutUnit middle(FocusDirection direction, const LayoutRect& rect)
120{
121 LayoutPoint center(rect.center());
122 return isHorizontalMove(direction) ? center.y(): center.x();
123}
124
125static inline LayoutUnit end(FocusDirection direction, const LayoutRect& rect)
126{
127 return isHorizontalMove(direction) ? rect.maxY() : rect.maxX();
128}
129
130// This method checks if rects |a| and |b| are fully aligned either vertically or
131// horizontally. In general, rects whose central point falls between the top or
132// bottom of each other are considered fully aligned.
133// Rects that match this criteria are preferable target nodes in move focus changing
134// operations.
135// * a = Current focused node's rect.
136// * b = Focus candidate node's rect.
137static bool areRectsFullyAligned(FocusDirection direction, const LayoutRect& a, const LayoutRect& b)
138{
139 LayoutUnit aStart, bStart, aEnd, bEnd;
140
141 switch (direction) {
142 case FocusDirectionLeft:
143 aStart = a.x();
144 bEnd = b.maxX();
145 break;
146 case FocusDirectionRight:
147 aStart = b.x();
148 bEnd = a.maxX();
149 break;
150 case FocusDirectionUp:
151 aStart = a.y();
152 bEnd = b.y();
153 break;
154 case FocusDirectionDown:
155 aStart = b.y();
156 bEnd = a.y();
157 break;
158 default:
159 ASSERT_NOT_REACHED();
160 return false;
161 }
162
163 if (aStart < bEnd)
164 return false;
165
166 aStart = start(direction, a);
167 bStart = start(direction, b);
168
169 LayoutUnit aMiddle = middle(direction, a);
170 LayoutUnit bMiddle = middle(direction, b);
171
172 aEnd = end(direction, a);
173 bEnd = end(direction, b);
174
175 // Picture of the totally aligned logic:
176 //
177 // Horizontal Vertical Horizontal Vertical
178 // **************************** *****************************
179 // * _ * _ _ _ _ * * _ * _ _ *
180 // * |_| _ * |_|_|_|_| * * _ |_| * |_|_| *
181 // * |_|....|_| * . * * |_|....|_| * . *
182 // * |_| |_| (1) . * * |_| |_| (2) . *
183 // * |_| * _._ * * |_| * _ _._ _ *
184 // * * |_|_| * * * |_|_|_|_| *
185 // * * * * * *
186 // **************************** *****************************
187
188 // Horizontal Vertical Horizontal Vertical
189 // **************************** *****************************
190 // * _......_ * _ _ _ _ * * _ * _ _ _ _ *
191 // * |_| |_| * |_|_|_|_| * * |_| _ * |_|_|_|_| *
192 // * |_| |_| * . * * |_| |_| * . *
193 // * |_| (3) . * * |_|....|_| (4) . *
194 // * * ._ _ * * * _ _. *
195 // * * |_|_| * * * |_|_| *
196 // * * * * * *
197 // **************************** *****************************
198
199 return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)
200 || (aMiddle >= bStart && aMiddle <= bEnd) // (2)
201 || (bStart == aStart) // (3)
202 || (bEnd == aEnd)); // (4)
203}
204
205// This method checks if |start| and |dest| have a partial intersection, either
206// horizontally or vertically.
207// * a = Current focused node's rect.
208// * b = Focus candidate node's rect.
209static bool areRectsPartiallyAligned(FocusDirection direction, const LayoutRect& a, const LayoutRect& b)
210{
211 LayoutUnit aStart = start(direction, a);
212 LayoutUnit bStart = start(direction, b);
213 LayoutUnit bMiddle = middle(direction, b);
214 LayoutUnit aEnd = end(direction, a);
215 LayoutUnit bEnd = end(direction, b);
216
217 // Picture of the partially aligned logic:
218 //
219 // Horizontal Vertical
220 // ********************************
221 // * _ * _ _ _ *
222 // * |_| * |_|_|_| *
223 // * |_|.... _ * . . *
224 // * |_| |_| * . . *
225 // * |_|....|_| * ._._ _ *
226 // * |_| * |_|_|_| *
227 // * |_| * *
228 // * * *
229 // ********************************
230 //
231 // ... and variants of the above cases.
232 return ((bStart >= aStart && bStart <= aEnd)
233 || (bMiddle >= aStart && bMiddle <= aEnd)
234 || (bEnd >= aStart && bEnd <= aEnd));
235}
236
237static bool areRectsMoreThanFullScreenApart(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect, const LayoutSize& viewSize)
238{
239 ASSERT(isRectInDirection(direction, curRect, targetRect));
240
241 switch (direction) {
242 case FocusDirectionLeft:
243 return curRect.x() - targetRect.maxX() > viewSize.width();
244 case FocusDirectionRight:
245 return targetRect.x() - curRect.maxX() > viewSize.width();
246 case FocusDirectionUp:
247 return curRect.y() - targetRect.maxY() > viewSize.height();
248 case FocusDirectionDown:
249 return targetRect.y() - curRect.maxY() > viewSize.height();
250 default:
251 ASSERT_NOT_REACHED();
252 return true;
253 }
254}
255
256// Return true if rect |a| is below |b|. False otherwise.
257static inline bool below(const LayoutRect& a, const LayoutRect& b)
258{
259 return a.y() > b.maxY();
260}
261
262// Return true if rect |a| is on the right of |b|. False otherwise.
263static inline bool rightOf(const LayoutRect& a, const LayoutRect& b)
264{
265 return a.x() > b.maxX();
266}
267
268static bool isRectInDirection(FocusDirection direction, const LayoutRect& curRect, const LayoutRect& targetRect)
269{
270 switch (direction) {
271 case FocusDirectionLeft:
272 return targetRect.maxX() <= curRect.x();
273 case FocusDirectionRight:
274 return targetRect.x() >= curRect.maxX();
275 case FocusDirectionUp:
276 return targetRect.maxY() <= curRect.y();
277 case FocusDirectionDown:
278 return targetRect.y() >= curRect.maxY();
279 default:
280 ASSERT_NOT_REACHED();
281 return false;
282 }
283}
284
285// Checks if |node| is offscreen the visible area (viewport) of its container
286// document. In case it is, one can scroll in direction or take any different
287// desired action later on.
288bool hasOffscreenRect(Node* node, FocusDirection direction)
289{
290 // Get the FrameView in which |node| is (which means the current viewport if |node|
291 // is not in an inner document), so we can check if its content rect is visible
292 // before we actually move the focus to it.
293 FrameView* frameView = node->document().view();
294 if (!frameView)
295 return true;
296
297 ASSERT(!frameView->needsLayout());
298
299 LayoutRect containerViewportRect = frameView->visibleContentRect();
300 // We want to select a node if it is currently off screen, but will be
301 // exposed after we scroll. Adjust the viewport to post-scrolling position.
302 // If the container has overflow:hidden, we cannot scroll, so we do not pass direction
303 // and we do not adjust for scrolling.
304 switch (direction) {
305 case FocusDirectionLeft:
306 containerViewportRect.setX(containerViewportRect.x() - Scrollbar::pixelsPerLineStep());
307 containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
308 break;
309 case FocusDirectionRight:
310 containerViewportRect.setWidth(containerViewportRect.width() + Scrollbar::pixelsPerLineStep());
311 break;
312 case FocusDirectionUp:
313 containerViewportRect.setY(containerViewportRect.y() - Scrollbar::pixelsPerLineStep());
314 containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
315 break;
316 case FocusDirectionDown:
317 containerViewportRect.setHeight(containerViewportRect.height() + Scrollbar::pixelsPerLineStep());
318 break;
319 default:
320 break;
321 }
322
323 RenderObject* render = node->renderer();
324 if (!render)
325 return true;
326
327 LayoutRect rect(render->absoluteClippedOverflowRect());
328 if (rect.isEmpty())
329 return true;
330
331 return !containerViewportRect.intersects(rect);
332}
333
334bool scrollInDirection(Frame* frame, FocusDirection direction)
335{
336 ASSERT(frame);
337
338 if (frame && canScrollInDirection(frame->document(), direction)) {
339 LayoutUnit dx;
340 LayoutUnit dy;
341 switch (direction) {
342 case FocusDirectionLeft:
343 dx = - Scrollbar::pixelsPerLineStep();
344 break;
345 case FocusDirectionRight:
346 dx = Scrollbar::pixelsPerLineStep();
347 break;
348 case FocusDirectionUp:
349 dy = - Scrollbar::pixelsPerLineStep();
350 break;
351 case FocusDirectionDown:
352 dy = Scrollbar::pixelsPerLineStep();
353 break;
354 default:
355 ASSERT_NOT_REACHED();
356 return false;
357 }
358
359 frame->view()->scrollBy(IntSize(dx, dy));
360 return true;
361 }
362 return false;
363}
364
365bool scrollInDirection(Node* container, FocusDirection direction)
366{
367 ASSERT(container);
368 if (is<Document>(*container))
369 return scrollInDirection(downcast<Document>(*container).frame(), direction);
370
371 if (!container->renderBox())
372 return false;
373
374 if (canScrollInDirection(container, direction)) {
375 LayoutUnit dx;
376 LayoutUnit dy;
377 switch (direction) {
378 case FocusDirectionLeft:
379 dx = - std::min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollLeft());
380 break;
381 case FocusDirectionRight:
382 ASSERT(container->renderBox()->scrollWidth() > (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
383 dx = std::min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
384 break;
385 case FocusDirectionUp:
386 dy = - std::min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollTop());
387 break;
388 case FocusDirectionDown:
389 ASSERT(container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
390 dy = std::min<LayoutUnit>(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
391 break;
392 default:
393 ASSERT_NOT_REACHED();
394 return false;
395 }
396
397 container->renderBox()->enclosingLayer()->scrollByRecursively(IntSize(dx, dy));
398 return true;
399 }
400
401 return false;
402}
403
404static void deflateIfOverlapped(LayoutRect& a, LayoutRect& b)
405{
406 if (!a.intersects(b) || a.contains(b) || b.contains(a))
407 return;
408
409 LayoutUnit deflateFactor = -fudgeFactor();
410
411 // Avoid negative width or height values.
412 if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))
413 a.inflate(deflateFactor);
414
415 if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))
416 b.inflate(deflateFactor);
417}
418
419bool isScrollableNode(const Node* node)
420{
421 if (!node)
422 return false;
423 ASSERT(!node->isDocumentNode());
424 auto* renderer = node->renderer();
425 return is<RenderBox>(renderer) && downcast<RenderBox>(*renderer).canBeScrolledAndHasScrollableArea() && node->hasChildNodes();
426}
427
428Node* scrollableEnclosingBoxOrParentFrameForNodeInDirection(FocusDirection direction, Node* node)
429{
430 ASSERT(node);
431 Node* parent = node;
432 do {
433 if (is<Document>(*parent))
434 parent = downcast<Document>(*parent).document().frame()->ownerElement();
435 else
436 parent = parent->parentNode();
437 } while (parent && !canScrollInDirection(parent, direction) && !is<Document>(*parent));
438
439 return parent;
440}
441
442bool canScrollInDirection(const Node* container, FocusDirection direction)
443{
444 ASSERT(container);
445
446 if (is<HTMLSelectElement>(*container))
447 return false;
448
449 if (is<Document>(*container))
450 return canScrollInDirection(downcast<Document>(*container).frame(), direction);
451
452 if (!isScrollableNode(container))
453 return false;
454
455 switch (direction) {
456 case FocusDirectionLeft:
457 return (container->renderer()->style().overflowX() != Overflow::Hidden && container->renderBox()->scrollLeft() > 0);
458 case FocusDirectionUp:
459 return (container->renderer()->style().overflowY() != Overflow::Hidden && container->renderBox()->scrollTop() > 0);
460 case FocusDirectionRight:
461 return (container->renderer()->style().overflowX() != Overflow::Hidden && container->renderBox()->scrollLeft() + container->renderBox()->clientWidth() < container->renderBox()->scrollWidth());
462 case FocusDirectionDown:
463 return (container->renderer()->style().overflowY() != Overflow::Hidden && container->renderBox()->scrollTop() + container->renderBox()->clientHeight() < container->renderBox()->scrollHeight());
464 default:
465 ASSERT_NOT_REACHED();
466 return false;
467 }
468}
469
470bool canScrollInDirection(const Frame* frame, FocusDirection direction)
471{
472 if (!frame->view())
473 return false;
474 ScrollbarMode verticalMode;
475 ScrollbarMode horizontalMode;
476 frame->view()->calculateScrollbarModesForLayout(horizontalMode, verticalMode);
477 if ((direction == FocusDirectionLeft || direction == FocusDirectionRight) && ScrollbarAlwaysOff == horizontalMode)
478 return false;
479 if ((direction == FocusDirectionUp || direction == FocusDirectionDown) && ScrollbarAlwaysOff == verticalMode)
480 return false;
481 LayoutSize size = frame->view()->totalContentsSize();
482 LayoutPoint scrollPosition = frame->view()->scrollPosition();
483 LayoutRect rect = frame->view()->unobscuredContentRectIncludingScrollbars();
484
485 // FIXME: wrong in RTL documents.
486 switch (direction) {
487 case FocusDirectionLeft:
488 return scrollPosition.x() > 0;
489 case FocusDirectionUp:
490 return scrollPosition.y() > 0;
491 case FocusDirectionRight:
492 return rect.width() + scrollPosition.x() < size.width();
493 case FocusDirectionDown:
494 return rect.height() + scrollPosition.y() < size.height();
495 default:
496 ASSERT_NOT_REACHED();
497 return false;
498 }
499}
500
501// FIXME: This is completely broken. This should be deleted and callers should be calling ScrollView::contentsToWindow() instead.
502static LayoutRect rectToAbsoluteCoordinates(Frame* initialFrame, const LayoutRect& initialRect)
503{
504 LayoutRect rect = initialRect;
505 for (Frame* frame = initialFrame; frame; frame = frame->tree().parent()) {
506 if (Element* element = frame->ownerElement()) {
507 do {
508 rect.move(LayoutUnit(element->offsetLeft()), LayoutUnit(element->offsetTop()));
509 } while ((element = element->offsetParent()));
510 rect.moveBy((-frame->view()->scrollPosition()));
511 }
512 }
513 return rect;
514}
515
516LayoutRect nodeRectInAbsoluteCoordinates(Node* node, bool ignoreBorder)
517{
518 ASSERT(node && node->renderer() && !node->document().view()->needsLayout());
519
520 if (is<Document>(*node))
521 return frameRectInAbsoluteCoordinates(downcast<Document>(*node).frame());
522
523 LayoutRect rect;
524 if (RenderObject* renderer = node->renderer())
525 rect = rectToAbsoluteCoordinates(node->document().frame(), renderer->absoluteBoundingBoxRect());
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
537LayoutRect 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.
544void 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(std::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(std::max(startingRect.x(), potentialRect.x()));
591 entryPoint.setX(exitPoint.x());
592 }
593 break;
594 default:
595 ASSERT_NOT_REACHED();
596 }
597}
598
599bool 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 (is<HTMLAreaElement>(*firstCandidate.focusableNode) || is<HTMLAreaElement>(*secondCandidate.focusableNode))
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// Consider only those nodes as candidate which are exactly in the focus-direction.
623// e.g. If we are moving down then the nodes that are above current focused node should be considered as invalid.
624bool isValidCandidate(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
625{
626 LayoutRect currentRect = current.rect;
627 LayoutRect candidateRect = candidate.rect;
628
629 switch (direction) {
630 case FocusDirectionLeft:
631 return candidateRect.x() < currentRect.maxX();
632 case FocusDirectionUp:
633 return candidateRect.y() < currentRect.maxY();
634 case FocusDirectionRight:
635 return candidateRect.maxX() > currentRect.x();
636 case FocusDirectionDown:
637 return candidateRect.maxY() > currentRect.y();
638 default:
639 ASSERT_NOT_REACHED();
640 }
641 return false;
642}
643
644void distanceDataForNode(FocusDirection direction, const FocusCandidate& current, FocusCandidate& candidate)
645{
646 if (areElementsOnSameLine(current, candidate)) {
647 if ((direction == FocusDirectionUp && current.rect.y() > candidate.rect.y()) || (direction == FocusDirectionDown && candidate.rect.y() > current.rect.y())) {
648 candidate.distance = 0;
649 candidate.alignment = Full;
650 return;
651 }
652 }
653
654 LayoutRect nodeRect = candidate.rect;
655 LayoutRect currentRect = current.rect;
656 deflateIfOverlapped(currentRect, nodeRect);
657
658 if (!isRectInDirection(direction, currentRect, nodeRect))
659 return;
660
661 LayoutPoint exitPoint;
662 LayoutPoint entryPoint;
663 LayoutUnit sameAxisDistance;
664 LayoutUnit otherAxisDistance;
665 entryAndExitPointsForDirection(direction, currentRect, nodeRect, exitPoint, entryPoint);
666
667 switch (direction) {
668 case FocusDirectionLeft:
669 sameAxisDistance = exitPoint.x() - entryPoint.x();
670 otherAxisDistance = absoluteValue(exitPoint.y() - entryPoint.y());
671 break;
672 case FocusDirectionUp:
673 sameAxisDistance = exitPoint.y() - entryPoint.y();
674 otherAxisDistance = absoluteValue(exitPoint.x() - entryPoint.x());
675 break;
676 case FocusDirectionRight:
677 sameAxisDistance = entryPoint.x() - exitPoint.x();
678 otherAxisDistance = absoluteValue(entryPoint.y() - exitPoint.y());
679 break;
680 case FocusDirectionDown:
681 sameAxisDistance = entryPoint.y() - exitPoint.y();
682 otherAxisDistance = absoluteValue(entryPoint.x() - exitPoint.x());
683 break;
684 default:
685 ASSERT_NOT_REACHED();
686 return;
687 }
688
689 float x = (entryPoint.x() - exitPoint.x()) * (entryPoint.x() - exitPoint.x());
690 float y = (entryPoint.y() - exitPoint.y()) * (entryPoint.y() - exitPoint.y());
691
692 float euclidianDistance = sqrt(x + y);
693
694 // Loosely based on http://www.w3.org/TR/WICD/#focus-handling
695 // df = dotDist + dx + dy + 2 * (xdisplacement + ydisplacement) - sqrt(Overlap)
696
697 float distance = euclidianDistance + sameAxisDistance + 2 * otherAxisDistance;
698 candidate.distance = roundf(distance);
699 LayoutSize viewSize = candidate.visibleNode->document().page()->mainFrame().view()->visibleContentRect().size();
700 candidate.alignment = alignmentForRects(direction, currentRect, nodeRect, viewSize);
701}
702
703bool canBeScrolledIntoView(FocusDirection direction, const FocusCandidate& candidate)
704{
705 ASSERT(candidate.visibleNode && candidate.isOffscreen);
706 LayoutRect candidateRect = candidate.rect;
707 for (Node* parentNode = candidate.visibleNode->parentNode(); parentNode; parentNode = parentNode->parentNode()) {
708 if (!parentNode->renderer())
709 continue;
710 LayoutRect parentRect = nodeRectInAbsoluteCoordinates(parentNode);
711 if (!candidateRect.intersects(parentRect)) {
712 if (((direction == FocusDirectionLeft || direction == FocusDirectionRight) && parentNode->renderer()->style().overflowX() == Overflow::Hidden)
713 || ((direction == FocusDirectionUp || direction == FocusDirectionDown) && parentNode->renderer()->style().overflowY() == Overflow::Hidden))
714 return false;
715 }
716 if (parentNode == candidate.enclosingScrollableBox)
717 return canScrollInDirection(parentNode, direction);
718 }
719 return true;
720}
721
722// The starting rect is the rect of the focused node, in document coordinates.
723// Compose a virtual starting rect if there is no focused node or if it is off screen.
724// The virtual rect is the edge of the container or frame. We select which
725// edge depending on the direction of the navigation.
726LayoutRect virtualRectForDirection(FocusDirection direction, const LayoutRect& startingRect, LayoutUnit width)
727{
728 LayoutRect virtualStartingRect = startingRect;
729 switch (direction) {
730 case FocusDirectionLeft:
731 virtualStartingRect.setX(virtualStartingRect.maxX() - width);
732 virtualStartingRect.setWidth(width);
733 break;
734 case FocusDirectionUp:
735 virtualStartingRect.setY(virtualStartingRect.maxY() - width);
736 virtualStartingRect.setHeight(width);
737 break;
738 case FocusDirectionRight:
739 virtualStartingRect.setWidth(width);
740 break;
741 case FocusDirectionDown:
742 virtualStartingRect.setHeight(width);
743 break;
744 default:
745 ASSERT_NOT_REACHED();
746 }
747
748 return virtualStartingRect;
749}
750
751LayoutRect virtualRectForAreaElementAndDirection(HTMLAreaElement* area, FocusDirection direction)
752{
753 ASSERT(area);
754 ASSERT(area->imageElement());
755 // Area elements tend to overlap more than other focusable elements. We flatten the rect of the area elements
756 // to minimize the effect of overlapping areas.
757 LayoutRect rect = virtualRectForDirection(direction, rectToAbsoluteCoordinates(area->document().frame(), area->computeRect(area->imageElement()->renderer())), 1);
758 return rect;
759}
760
761HTMLFrameOwnerElement* frameOwnerElement(FocusCandidate& candidate)
762{
763 return candidate.isFrameOwnerElement() ? downcast<HTMLFrameOwnerElement>(candidate.visibleNode) : nullptr;
764}
765
766} // namespace WebCore
767