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