1/*
2 * Copyright (C) 2006, 2007 Apple Inc. All rights reserved.
3 * Copyright (C) 2008 Nuanti Ltd.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include "config.h"
28#include "core/page/FocusController.h"
29
30#include "core/HTMLNames.h"
31#include "core/accessibility/AXObjectCache.h"
32#include "core/dom/Document.h"
33#include "core/dom/Element.h"
34#include "core/dom/ElementTraversal.h"
35#include "core/dom/NodeTraversal.h"
36#include "core/dom/Range.h"
37#include "core/dom/shadow/ElementShadow.h"
38#include "core/dom/shadow/ShadowRoot.h"
39#include "core/editing/Editor.h"
40#include "core/editing/FrameSelection.h"
41#include "core/editing/htmlediting.h" // For firstPositionInOrBeforeNode
42#include "core/events/Event.h"
43#include "core/frame/FrameView.h"
44#include "core/frame/LocalDOMWindow.h"
45#include "core/frame/LocalFrame.h"
46#include "core/html/HTMLAreaElement.h"
47#include "core/html/HTMLImageElement.h"
48#include "core/html/HTMLPlugInElement.h"
49#include "core/html/HTMLShadowElement.h"
50#include "core/html/HTMLTextFormControlElement.h"
51#include "core/page/Chrome.h"
52#include "core/page/ChromeClient.h"
53#include "core/page/EventHandler.h"
54#include "core/page/FrameTree.h"
55#include "core/page/Page.h"
56#include "core/frame/Settings.h"
57#include "core/page/SpatialNavigation.h"
58#include "core/rendering/HitTestResult.h"
59#include "core/rendering/RenderLayer.h"
60#include <limits>
61
62namespace blink {
63
64using namespace HTMLNames;
65
66static inline bool isShadowInsertionPointFocusScopeOwner(Node& node)
67{
68    return isActiveShadowInsertionPoint(node) && toHTMLShadowElement(node).olderShadowRoot();
69}
70
71// FIXME: Some of Node* return values and Node* arguments should be Element*.
72
73FocusNavigationScope::FocusNavigationScope(TreeScope* treeScope)
74    : m_rootTreeScope(treeScope)
75{
76    ASSERT(treeScope);
77}
78
79Node* FocusNavigationScope::rootNode() const
80{
81    return &m_rootTreeScope->rootNode();
82}
83
84Element* FocusNavigationScope::owner() const
85{
86    Node* root = rootNode();
87    if (root->isShadowRoot()) {
88        ShadowRoot* shadowRoot = toShadowRoot(root);
89        return shadowRoot->isYoungest() ? shadowRoot->host() : shadowRoot->shadowInsertionPointOfYoungerShadowRoot();
90    }
91    // FIXME: Figure out the right thing for OOPI here.
92    if (Frame* frame = root->document().frame())
93        return frame->deprecatedLocalOwner();
94    return 0;
95}
96
97FocusNavigationScope FocusNavigationScope::focusNavigationScopeOf(Node* node)
98{
99    ASSERT(node);
100    Node* root = node;
101    for (Node* n = node; n; n = n->parentNode())
102        root = n;
103    // The result is not always a ShadowRoot nor a DocumentNode since
104    // a starting node is in an orphaned tree in composed shadow tree.
105    return FocusNavigationScope(&root->treeScope());
106}
107
108FocusNavigationScope FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(Node* node)
109{
110    ASSERT(node);
111    if (isShadowHost(node))
112        return FocusNavigationScope::ownedByShadowHost(node);
113    ASSERT(isShadowInsertionPointFocusScopeOwner(*node));
114    return FocusNavigationScope::ownedByShadowInsertionPoint(toHTMLShadowElement(node));
115}
116
117FocusNavigationScope FocusNavigationScope::ownedByShadowHost(Node* node)
118{
119    ASSERT(isShadowHost(node));
120    return FocusNavigationScope(toElement(node)->shadow()->youngestShadowRoot());
121}
122
123FocusNavigationScope FocusNavigationScope::ownedByIFrame(HTMLFrameOwnerElement* frame)
124{
125    ASSERT(frame && frame->contentFrame() && frame->contentFrame()->isLocalFrame());
126    return FocusNavigationScope(toLocalFrame(frame->contentFrame())->document());
127}
128
129FocusNavigationScope FocusNavigationScope::ownedByShadowInsertionPoint(HTMLShadowElement* shadowInsertionPoint)
130{
131    ASSERT(isShadowInsertionPointFocusScopeOwner(*shadowInsertionPoint));
132    return FocusNavigationScope(shadowInsertionPoint->olderShadowRoot());
133}
134
135static inline void dispatchEventsOnWindowAndFocusedNode(Document* document, bool focused)
136{
137    // If we have a focused node we should dispatch blur on it before we blur the window.
138    // If we have a focused node we should dispatch focus on it after we focus the window.
139    // https://bugs.webkit.org/show_bug.cgi?id=27105
140
141    // Do not fire events while modal dialogs are up.  See https://bugs.webkit.org/show_bug.cgi?id=33962
142    if (Page* page = document->page()) {
143        if (page->defersLoading())
144            return;
145    }
146
147    if (!focused && document->focusedElement()) {
148        RefPtrWillBeRawPtr<Element> focusedElement(document->focusedElement());
149        focusedElement->setFocus(false);
150        focusedElement->dispatchBlurEvent(0);
151        if (focusedElement == document->focusedElement()) {
152            focusedElement->dispatchFocusOutEvent(EventTypeNames::focusout, 0);
153            if (focusedElement == document->focusedElement())
154                focusedElement->dispatchFocusOutEvent(EventTypeNames::DOMFocusOut, 0);
155        }
156    }
157
158    if (LocalDOMWindow* window = document->domWindow())
159        window->dispatchEvent(Event::create(focused ? EventTypeNames::focus : EventTypeNames::blur));
160    if (focused && document->focusedElement()) {
161        RefPtrWillBeRawPtr<Element> focusedElement(document->focusedElement());
162        focusedElement->setFocus(true);
163        focusedElement->dispatchFocusEvent(0, FocusTypePage);
164        if (focusedElement == document->focusedElement()) {
165            document->focusedElement()->dispatchFocusInEvent(EventTypeNames::focusin, 0, FocusTypePage);
166            if (focusedElement == document->focusedElement())
167                document->focusedElement()->dispatchFocusInEvent(EventTypeNames::DOMFocusIn, 0, FocusTypePage);
168        }
169    }
170}
171
172static inline bool hasCustomFocusLogic(Element* element)
173{
174    return element->isHTMLElement() && toHTMLElement(element)->hasCustomFocusLogic();
175}
176
177#if ENABLE(ASSERT)
178static inline bool isNonFocusableShadowHost(Node* node)
179{
180    ASSERT(node);
181    if (!node->isElementNode())
182        return false;
183    Element* element = toElement(node);
184    return !element->isFocusable() && isShadowHost(element) && !hasCustomFocusLogic(element);
185}
186#endif
187
188static inline bool isNonKeyboardFocusableShadowHost(Node* node)
189{
190    ASSERT(node);
191    if (!node->isElementNode())
192        return false;
193    Element* element = toElement(node);
194    return !element->isKeyboardFocusable() && isShadowHost(element) && !hasCustomFocusLogic(element);
195}
196
197static inline bool isKeyboardFocusableShadowHost(Node* node)
198{
199    ASSERT(node);
200    if (!node->isElementNode())
201        return false;
202    Element* element = toElement(node);
203    return element->isKeyboardFocusable() && isShadowHost(element) && !hasCustomFocusLogic(element);
204}
205
206static inline bool isNonFocusableFocusScopeOwner(Node* node)
207{
208    ASSERT(node);
209    return isNonKeyboardFocusableShadowHost(node) || isShadowInsertionPointFocusScopeOwner(*node);
210}
211
212static inline int adjustedTabIndex(Node* node)
213{
214    ASSERT(node);
215    return isNonFocusableFocusScopeOwner(node) ? 0 : node->tabIndex();
216}
217
218static inline bool shouldVisit(Node* node)
219{
220    ASSERT(node);
221    return (node->isElementNode() && toElement(node)->isKeyboardFocusable()) || isNonFocusableFocusScopeOwner(node);
222}
223
224FocusController::FocusController(Page* page)
225    : m_page(page)
226    , m_isActive(false)
227    , m_isFocused(false)
228    , m_isChangingFocusedFrame(false)
229{
230}
231
232PassOwnPtrWillBeRawPtr<FocusController> FocusController::create(Page* page)
233{
234    return adoptPtrWillBeNoop(new FocusController(page));
235}
236
237void FocusController::setFocusedFrame(PassRefPtrWillBeRawPtr<Frame> frame)
238{
239    ASSERT(!frame || frame->page() == m_page);
240    if (m_focusedFrame == frame || m_isChangingFocusedFrame)
241        return;
242
243    m_isChangingFocusedFrame = true;
244
245    RefPtrWillBeRawPtr<LocalFrame> oldFrame = (m_focusedFrame && m_focusedFrame->isLocalFrame()) ? toLocalFrame(m_focusedFrame.get()) : 0;
246
247    RefPtrWillBeRawPtr<LocalFrame> newFrame = (frame && frame->isLocalFrame()) ? toLocalFrame(frame.get()) : 0;
248
249    m_focusedFrame = frame.get();
250
251    // Now that the frame is updated, fire events and update the selection focused states of both frames.
252    if (oldFrame && oldFrame->view()) {
253        oldFrame->selection().setFocused(false);
254        oldFrame->domWindow()->dispatchEvent(Event::create(EventTypeNames::blur));
255    }
256
257    if (newFrame && newFrame->view() && isFocused()) {
258        newFrame->selection().setFocused(true);
259        newFrame->domWindow()->dispatchEvent(Event::create(EventTypeNames::focus));
260    }
261
262    m_isChangingFocusedFrame = false;
263
264    m_page->chrome().client().focusedFrameChanged(newFrame.get());
265}
266
267void FocusController::focusDocumentView(PassRefPtrWillBeRawPtr<Frame> frame)
268{
269    ASSERT(!frame || frame->page() == m_page);
270    if (m_focusedFrame == frame)
271        return;
272
273    RefPtrWillBeRawPtr<LocalFrame> focusedFrame = (m_focusedFrame && m_focusedFrame->isLocalFrame()) ? toLocalFrame(m_focusedFrame.get()) : 0;
274    if (focusedFrame && focusedFrame->view()) {
275        RefPtrWillBeRawPtr<Document> document = focusedFrame->document();
276        Element* focusedElement = document ? document->focusedElement() : 0;
277        if (focusedElement) {
278            focusedElement->dispatchBlurEvent(0);
279            if (focusedElement == document->focusedElement()) {
280                focusedElement->dispatchFocusOutEvent(EventTypeNames::focusout, 0);
281                if (focusedElement == document->focusedElement())
282                    focusedElement->dispatchFocusOutEvent(EventTypeNames::DOMFocusOut, 0);
283            }
284        }
285    }
286
287    RefPtrWillBeRawPtr<LocalFrame> newFocusedFrame = (frame && frame->isLocalFrame()) ? toLocalFrame(frame.get()) : 0;
288    if (newFocusedFrame && newFocusedFrame->view()) {
289        RefPtrWillBeRawPtr<Document> document = newFocusedFrame->document();
290        Element* focusedElement = document ? document->focusedElement() : 0;
291        if (focusedElement) {
292            focusedElement->dispatchFocusEvent(0, FocusTypePage);
293            if (focusedElement == document->focusedElement()) {
294                document->focusedElement()->dispatchFocusInEvent(EventTypeNames::focusin, 0, FocusTypePage);
295                if (focusedElement == document->focusedElement())
296                    document->focusedElement()->dispatchFocusInEvent(EventTypeNames::DOMFocusIn, 0, FocusTypePage);
297            }
298        }
299    }
300
301    setFocusedFrame(frame);
302}
303
304Frame* FocusController::focusedOrMainFrame() const
305{
306    if (Frame* frame = focusedFrame())
307        return frame;
308
309    // FIXME: This is a temporary hack to ensure that we return a LocalFrame, even when the mainFrame is remote.
310    // FocusController needs to be refactored to deal with RemoteFrames cross-process focus transfers.
311    for (Frame* frame = m_page->mainFrame()->tree().top(); frame; frame = frame->tree().traverseNext()) {
312        if (frame->isLocalRoot())
313            return frame;
314    }
315
316    return m_page->mainFrame();
317}
318
319void FocusController::setFocused(bool focused)
320{
321    if (isFocused() == focused)
322        return;
323
324    m_isFocused = focused;
325
326    if (!m_isFocused && focusedOrMainFrame()->isLocalFrame())
327        toLocalFrame(focusedOrMainFrame())->eventHandler().stopAutoscroll();
328
329    if (!m_focusedFrame)
330        setFocusedFrame(m_page->mainFrame());
331
332    // setFocusedFrame above might reject to update m_focusedFrame, or
333    // m_focusedFrame might be changed by blur/focus event handlers.
334    if (m_focusedFrame && m_focusedFrame->isLocalFrame() && toLocalFrame(m_focusedFrame.get())->view()) {
335        toLocalFrame(m_focusedFrame.get())->selection().setFocused(focused);
336        dispatchEventsOnWindowAndFocusedNode(toLocalFrame(m_focusedFrame.get())->document(), focused);
337    }
338}
339
340Node* FocusController::findFocusableNodeDecendingDownIntoFrameDocument(FocusType type, Node* node)
341{
342    // The node we found might be a HTMLFrameOwnerElement, so descend down the tree until we find either:
343    // 1) a focusable node, or
344    // 2) the deepest-nested HTMLFrameOwnerElement.
345    while (node && node->isFrameOwnerElement()) {
346        HTMLFrameOwnerElement* owner = toHTMLFrameOwnerElement(node);
347        if (!owner->contentFrame() || !owner->contentFrame()->isLocalFrame())
348            break;
349        Node* foundNode = findFocusableNode(type, FocusNavigationScope::ownedByIFrame(owner), 0);
350        if (!foundNode)
351            break;
352        ASSERT(node != foundNode);
353        node = foundNode;
354    }
355    return node;
356}
357
358bool FocusController::setInitialFocus(FocusType type)
359{
360    bool didAdvanceFocus = advanceFocus(type, true);
361
362    // If focus is being set initially, accessibility needs to be informed that system focus has moved
363    // into the web area again, even if focus did not change within WebCore. PostNotification is called instead
364    // of handleFocusedUIElementChanged, because this will send the notification even if the element is the same.
365    if (focusedOrMainFrame()->isLocalFrame()) {
366        Document* document = toLocalFrame(focusedOrMainFrame())->document();
367        if (AXObjectCache* cache = document->existingAXObjectCache())
368            cache->postNotification(document, AXObjectCache::AXFocusedUIElementChanged, true);
369    }
370
371    return didAdvanceFocus;
372}
373
374bool FocusController::advanceFocus(FocusType type, bool initialFocus)
375{
376    switch (type) {
377    case FocusTypeForward:
378    case FocusTypeBackward:
379        return advanceFocusInDocumentOrder(type, initialFocus);
380    case FocusTypeLeft:
381    case FocusTypeRight:
382    case FocusTypeUp:
383    case FocusTypeDown:
384        return advanceFocusDirectionally(type);
385    default:
386        ASSERT_NOT_REACHED();
387    }
388
389    return false;
390}
391
392bool FocusController::advanceFocusInDocumentOrder(FocusType type, bool initialFocus)
393{
394    // FIXME: Focus advancement won't work with externally rendered frames until after
395    // inter-frame focus control is moved out of Blink.
396    if (!focusedOrMainFrame()->isLocalFrame())
397        return false;
398    LocalFrame* frame = toLocalFrame(focusedOrMainFrame());
399    ASSERT(frame);
400    Document* document = frame->document();
401
402    Node* currentNode = document->focusedElement();
403    // FIXME: Not quite correct when it comes to focus transitions leaving/entering the WebView itself
404    bool caretBrowsing = frame->settings() && frame->settings()->caretBrowsingEnabled();
405
406    if (caretBrowsing && !currentNode)
407        currentNode = frame->selection().start().deprecatedNode();
408
409    document->updateLayoutIgnorePendingStylesheets();
410
411    RefPtrWillBeRawPtr<Node> node = findFocusableNodeAcrossFocusScope(type, FocusNavigationScope::focusNavigationScopeOf(currentNode ? currentNode : document), currentNode);
412
413    if (!node) {
414        // We didn't find a node to focus, so we should try to pass focus to Chrome.
415        if (!initialFocus && m_page->chrome().canTakeFocus(type)) {
416            document->setFocusedElement(nullptr);
417            setFocusedFrame(nullptr);
418            m_page->chrome().takeFocus(type);
419            return true;
420        }
421
422        // Chrome doesn't want focus, so we should wrap focus.
423        if (!m_page->mainFrame()->isLocalFrame())
424            return false;
425        node = findFocusableNodeRecursively(type, FocusNavigationScope::focusNavigationScopeOf(m_page->deprecatedLocalMainFrame()->document()), 0);
426        node = findFocusableNodeDecendingDownIntoFrameDocument(type, node.get());
427
428        if (!node)
429            return false;
430    }
431
432    ASSERT(node);
433
434    if (node == document->focusedElement())
435        // Focus wrapped around to the same node.
436        return true;
437
438    if (!node->isElementNode())
439        // FIXME: May need a way to focus a document here.
440        return false;
441
442    Element* element = toElement(node);
443    if (element->isFrameOwnerElement() && (!isHTMLPlugInElement(*element) || !element->isKeyboardFocusable())) {
444        // We focus frames rather than frame owners.
445        // FIXME: We should not focus frames that have no scrollbars, as focusing them isn't useful to the user.
446        HTMLFrameOwnerElement* owner = toHTMLFrameOwnerElement(element);
447        if (!owner->contentFrame())
448            return false;
449
450        document->setFocusedElement(nullptr);
451        setFocusedFrame(owner->contentFrame());
452        return true;
453    }
454
455    // FIXME: It would be nice to just be able to call setFocusedElement(node)
456    // here, but we can't do that because some elements (e.g. HTMLInputElement
457    // and HTMLTextAreaElement) do extra work in their focus() methods.
458    Document& newDocument = element->document();
459
460    if (&newDocument != document) {
461        // Focus is going away from this document, so clear the focused node.
462        document->setFocusedElement(nullptr);
463    }
464
465    setFocusedFrame(newDocument.frame());
466
467    if (caretBrowsing) {
468        Position position = firstPositionInOrBeforeNode(element);
469        VisibleSelection newSelection(position, position, DOWNSTREAM);
470        frame->selection().setSelection(newSelection);
471    }
472
473    element->focus(false, type);
474    return true;
475}
476
477Node* FocusController::findFocusableNodeAcrossFocusScope(FocusType type, FocusNavigationScope scope, Node* currentNode)
478{
479    ASSERT(!currentNode || !isNonFocusableShadowHost(currentNode));
480    Node* found;
481    if (currentNode && type == FocusTypeForward && isKeyboardFocusableShadowHost(currentNode)) {
482        Node* foundInInnerFocusScope = findFocusableNodeRecursively(type, FocusNavigationScope::ownedByShadowHost(currentNode), 0);
483        found = foundInInnerFocusScope ? foundInInnerFocusScope : findFocusableNodeRecursively(type, scope, currentNode);
484    } else {
485        found = findFocusableNodeRecursively(type, scope, currentNode);
486    }
487
488    // If there's no focusable node to advance to, move up the focus scopes until we find one.
489    while (!found) {
490        Node* owner = scope.owner();
491        if (!owner)
492            break;
493        scope = FocusNavigationScope::focusNavigationScopeOf(owner);
494        if (type == FocusTypeBackward && isKeyboardFocusableShadowHost(owner)) {
495            found = owner;
496            break;
497        }
498        found = findFocusableNodeRecursively(type, scope, owner);
499    }
500    found = findFocusableNodeDecendingDownIntoFrameDocument(type, found);
501    return found;
502}
503
504Node* FocusController::findFocusableNodeRecursively(FocusType type, FocusNavigationScope scope, Node* start)
505{
506    // Starting node is exclusive.
507    Node* found = findFocusableNode(type, scope, start);
508    if (!found)
509        return 0;
510    if (type == FocusTypeForward) {
511        if (!isNonFocusableFocusScopeOwner(found))
512            return found;
513        Node* foundInInnerFocusScope = findFocusableNodeRecursively(type, FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(found), 0);
514        return foundInInnerFocusScope ? foundInInnerFocusScope : findFocusableNodeRecursively(type, scope, found);
515    }
516    ASSERT(type == FocusTypeBackward);
517    if (isKeyboardFocusableShadowHost(found)) {
518        Node* foundInInnerFocusScope = findFocusableNodeRecursively(type, FocusNavigationScope::ownedByShadowHost(found), 0);
519        return foundInInnerFocusScope ? foundInInnerFocusScope : found;
520    }
521    if (isNonFocusableFocusScopeOwner(found)) {
522        Node* foundInInnerFocusScope = findFocusableNodeRecursively(type, FocusNavigationScope::ownedByNonFocusableFocusScopeOwner(found), 0);
523        return foundInInnerFocusScope ? foundInInnerFocusScope :findFocusableNodeRecursively(type, scope, found);
524    }
525    return found;
526}
527
528Node* FocusController::findFocusableNode(FocusType type, FocusNavigationScope scope, Node* node)
529{
530    return type == FocusTypeForward ? nextFocusableNode(scope, node) : previousFocusableNode(scope, node);
531}
532
533Node* FocusController::findNodeWithExactTabIndex(Node* start, int tabIndex, FocusType type)
534{
535    // Search is inclusive of start
536    for (Node* node = start; node; node = type == FocusTypeForward ? NodeTraversal::next(*node) : NodeTraversal::previous(*node)) {
537        if (shouldVisit(node) && adjustedTabIndex(node) == tabIndex)
538            return node;
539    }
540    return 0;
541}
542
543static Node* nextNodeWithGreaterTabIndex(Node* start, int tabIndex)
544{
545    // Search is inclusive of start
546    int winningTabIndex = std::numeric_limits<short>::max() + 1;
547    Node* winner = 0;
548    for (Node* node = start; node; node = NodeTraversal::next(*node)) {
549        int currentTabIndex = adjustedTabIndex(node);
550        if (shouldVisit(node) && currentTabIndex > tabIndex && currentTabIndex < winningTabIndex) {
551            winner = node;
552            winningTabIndex = currentTabIndex;
553        }
554    }
555
556    return winner;
557}
558
559static Node* previousNodeWithLowerTabIndex(Node* start, int tabIndex)
560{
561    // Search is inclusive of start
562    int winningTabIndex = 0;
563    Node* winner = 0;
564    for (Node* node = start; node; node = NodeTraversal::previous(*node)) {
565        int currentTabIndex = adjustedTabIndex(node);
566        if ((shouldVisit(node) || isNonKeyboardFocusableShadowHost(node)) && currentTabIndex < tabIndex && currentTabIndex > winningTabIndex) {
567            winner = node;
568            winningTabIndex = currentTabIndex;
569        }
570    }
571    return winner;
572}
573
574Node* FocusController::nextFocusableNode(FocusNavigationScope scope, Node* start)
575{
576    if (start) {
577        int tabIndex = adjustedTabIndex(start);
578        // If a node is excluded from the normal tabbing cycle, the next focusable node is determined by tree order
579        if (tabIndex < 0) {
580            for (Node* node = NodeTraversal::next(*start); node; node = NodeTraversal::next(*node)) {
581                if (shouldVisit(node) && adjustedTabIndex(node) >= 0)
582                    return node;
583            }
584        } else {
585            // First try to find a node with the same tabindex as start that comes after start in the scope.
586            if (Node* winner = findNodeWithExactTabIndex(NodeTraversal::next(*start), tabIndex, FocusTypeForward))
587                return winner;
588        }
589        if (!tabIndex)
590            // We've reached the last node in the document with a tabindex of 0. This is the end of the tabbing order.
591            return 0;
592    }
593
594    // Look for the first node in the scope that:
595    // 1) has the lowest tabindex that is higher than start's tabindex (or 0, if start is null), and
596    // 2) comes first in the scope, if there's a tie.
597    if (Node* winner = nextNodeWithGreaterTabIndex(scope.rootNode(), start ? adjustedTabIndex(start) : 0))
598        return winner;
599
600    // There are no nodes with a tabindex greater than start's tabindex,
601    // so find the first node with a tabindex of 0.
602    return findNodeWithExactTabIndex(scope.rootNode(), 0, FocusTypeForward);
603}
604
605Node* FocusController::previousFocusableNode(FocusNavigationScope scope, Node* start)
606{
607    Node* last = 0;
608    for (Node* node = scope.rootNode(); node; node = node->lastChild())
609        last = node;
610    ASSERT(last);
611
612    // First try to find the last node in the scope that comes before start and has the same tabindex as start.
613    // If start is null, find the last node in the scope with a tabindex of 0.
614    Node* startingNode;
615    int startingTabIndex;
616    if (start) {
617        startingNode = NodeTraversal::previous(*start);
618        startingTabIndex = adjustedTabIndex(start);
619    } else {
620        startingNode = last;
621        startingTabIndex = 0;
622    }
623
624    // However, if a node is excluded from the normal tabbing cycle, the previous focusable node is determined by tree order
625    if (startingTabIndex < 0) {
626        for (Node* node = startingNode; node; node = NodeTraversal::previous(*node)) {
627            if (shouldVisit(node) && adjustedTabIndex(node) >= 0)
628                return node;
629        }
630    } else {
631        if (Node* winner = findNodeWithExactTabIndex(startingNode, startingTabIndex, FocusTypeBackward))
632            return winner;
633    }
634
635    // There are no nodes before start with the same tabindex as start, so look for a node that:
636    // 1) has the highest non-zero tabindex (that is less than start's tabindex), and
637    // 2) comes last in the scope, if there's a tie.
638    startingTabIndex = (start && startingTabIndex) ? startingTabIndex : std::numeric_limits<short>::max();
639    return previousNodeWithLowerTabIndex(last, startingTabIndex);
640}
641
642static bool relinquishesEditingFocus(Node *node)
643{
644    ASSERT(node);
645    ASSERT(node->hasEditableStyle());
646    return node->document().frame() && node->rootEditableElement();
647}
648
649static void clearSelectionIfNeeded(LocalFrame* oldFocusedFrame, LocalFrame* newFocusedFrame, Node* newFocusedNode)
650{
651    if (!oldFocusedFrame || !newFocusedFrame)
652        return;
653
654    if (oldFocusedFrame->document() != newFocusedFrame->document())
655        return;
656
657    FrameSelection& selection = oldFocusedFrame->selection();
658    if (selection.isNone())
659        return;
660
661    bool caretBrowsing = oldFocusedFrame->settings()->caretBrowsingEnabled();
662    if (caretBrowsing)
663        return;
664
665    Node* selectionStartNode = selection.selection().start().deprecatedNode();
666    if (selectionStartNode == newFocusedNode || selectionStartNode->isDescendantOf(newFocusedNode))
667        return;
668
669    if (!enclosingTextFormControl(selectionStartNode))
670        return;
671
672    if (selectionStartNode->isInShadowTree() && selectionStartNode->shadowHost() == newFocusedNode)
673        return;
674
675    selection.clear();
676}
677
678bool FocusController::setFocusedElement(Element* element, PassRefPtrWillBeRawPtr<Frame> newFocusedFrame, FocusType type)
679{
680    RefPtrWillBeRawPtr<LocalFrame> oldFocusedFrame = toLocalFrame(focusedFrame());
681    RefPtrWillBeRawPtr<Document> oldDocument = oldFocusedFrame ? oldFocusedFrame->document() : 0;
682
683    Element* oldFocusedElement = oldDocument ? oldDocument->focusedElement() : 0;
684    if (element && oldFocusedElement == element)
685        return true;
686
687    // FIXME: Might want to disable this check for caretBrowsing
688    if (oldFocusedElement && oldFocusedElement->isRootEditableElement() && !relinquishesEditingFocus(oldFocusedElement))
689        return false;
690
691    m_page->chrome().client().willSetInputMethodState();
692
693    RefPtrWillBeRawPtr<Document> newDocument = nullptr;
694    if (element)
695        newDocument = &element->document();
696    else if (newFocusedFrame && newFocusedFrame->isLocalFrame())
697        newDocument = toLocalFrame(newFocusedFrame.get())->document();
698
699    if (newDocument && oldDocument == newDocument && newDocument->focusedElement() == element)
700        return true;
701
702    clearSelectionIfNeeded(oldFocusedFrame.get(), toLocalFrame(newFocusedFrame.get()), element);
703
704    if (oldDocument && oldDocument != newDocument)
705        oldDocument->setFocusedElement(nullptr);
706
707    if (newFocusedFrame && !newFocusedFrame->page()) {
708        setFocusedFrame(nullptr);
709        return false;
710    }
711    setFocusedFrame(newFocusedFrame);
712
713    // Setting the focused node can result in losing our last reft to node when JS event handlers fire.
714    RefPtrWillBeRawPtr<Element> protect ALLOW_UNUSED = element;
715    if (newDocument) {
716        bool successfullyFocused = newDocument->setFocusedElement(element, type);
717        if (!successfullyFocused)
718            return false;
719    }
720
721    return true;
722}
723
724void FocusController::setActive(bool active)
725{
726    if (m_isActive == active)
727        return;
728
729    m_isActive = active;
730
731    Frame* frame = focusedOrMainFrame();
732    if (frame->isLocalFrame())
733        toLocalFrame(frame)->selection().pageActivationChanged();
734}
735
736static void updateFocusCandidateIfNeeded(FocusType type, const FocusCandidate& current, FocusCandidate& candidate, FocusCandidate& closest)
737{
738    ASSERT(candidate.visibleNode->isElementNode());
739    ASSERT(candidate.visibleNode->renderer());
740
741    // Ignore iframes that don't have a src attribute
742    if (frameOwnerElement(candidate) && (!frameOwnerElement(candidate)->contentFrame() || candidate.rect.isEmpty()))
743        return;
744
745    // Ignore off screen child nodes of containers that do not scroll (overflow:hidden)
746    if (candidate.isOffscreen && !canBeScrolledIntoView(type, candidate))
747        return;
748
749    distanceDataForNode(type, current, candidate);
750    if (candidate.distance == maxDistance())
751        return;
752
753    if (candidate.isOffscreenAfterScrolling && candidate.alignment < Full)
754        return;
755
756    if (closest.isNull()) {
757        closest = candidate;
758        return;
759    }
760
761    LayoutRect intersectionRect = intersection(candidate.rect, closest.rect);
762    if (!intersectionRect.isEmpty() && !areElementsOnSameLine(closest, candidate)
763        && intersectionRect == candidate.rect) {
764        // If 2 nodes are intersecting, do hit test to find which node in on top.
765        LayoutUnit x = intersectionRect.x() + intersectionRect.width() / 2;
766        LayoutUnit y = intersectionRect.y() + intersectionRect.height() / 2;
767        if (!candidate.visibleNode->document().page()->mainFrame()->isLocalFrame())
768            return;
769        HitTestResult result = candidate.visibleNode->document().page()->deprecatedLocalMainFrame()->eventHandler().hitTestResultAtPoint(IntPoint(x, y), HitTestRequest::ReadOnly | HitTestRequest::Active | HitTestRequest::IgnoreClipping);
770        if (candidate.visibleNode->contains(result.innerNode())) {
771            closest = candidate;
772            return;
773        }
774        if (closest.visibleNode->contains(result.innerNode()))
775            return;
776    }
777
778    if (candidate.alignment == closest.alignment) {
779        if (candidate.distance < closest.distance)
780            closest = candidate;
781        return;
782    }
783
784    if (candidate.alignment > closest.alignment)
785        closest = candidate;
786}
787
788void FocusController::findFocusCandidateInContainer(Node& container, const LayoutRect& startingRect, FocusType type, FocusCandidate& closest)
789{
790    Element* focusedElement = (focusedFrame() && toLocalFrame(focusedFrame())->document()) ? toLocalFrame(focusedFrame())->document()->focusedElement() : 0;
791
792    Element* element = ElementTraversal::firstWithin(container);
793    FocusCandidate current;
794    current.rect = startingRect;
795    current.focusableNode = focusedElement;
796    current.visibleNode = focusedElement;
797
798    for (; element; element = (element->isFrameOwnerElement() || canScrollInDirection(element, type))
799        ? ElementTraversal::nextSkippingChildren(*element, &container)
800        : ElementTraversal::next(*element, &container)) {
801        if (element == focusedElement)
802            continue;
803
804        if (!element->isKeyboardFocusable() && !element->isFrameOwnerElement() && !canScrollInDirection(element, type))
805            continue;
806
807        FocusCandidate candidate = FocusCandidate(element, type);
808        if (candidate.isNull())
809            continue;
810
811        candidate.enclosingScrollableBox = &container;
812        updateFocusCandidateIfNeeded(type, current, candidate, closest);
813    }
814}
815
816bool FocusController::advanceFocusDirectionallyInContainer(Node* container, const LayoutRect& startingRect, FocusType type)
817{
818    if (!container)
819        return false;
820
821    LayoutRect newStartingRect = startingRect;
822
823    if (startingRect.isEmpty())
824        newStartingRect = virtualRectForDirection(type, nodeRectInAbsoluteCoordinates(container));
825
826    // Find the closest node within current container in the direction of the navigation.
827    FocusCandidate focusCandidate;
828    findFocusCandidateInContainer(*container, newStartingRect, type, focusCandidate);
829
830    if (focusCandidate.isNull()) {
831        // Nothing to focus, scroll if possible.
832        // NOTE: If no scrolling is performed (i.e. scrollInDirection returns false), the
833        // spatial navigation algorithm will skip this container.
834        return scrollInDirection(container, type);
835    }
836
837    HTMLFrameOwnerElement* frameElement = frameOwnerElement(focusCandidate);
838    // If we have an iframe without the src attribute, it will not have a contentFrame().
839    // We ASSERT here to make sure that
840    // updateFocusCandidateIfNeeded() will never consider such an iframe as a candidate.
841    ASSERT(!frameElement || frameElement->contentFrame());
842    if (frameElement && frameElement->contentFrame()->isLocalFrame()) {
843        if (focusCandidate.isOffscreenAfterScrolling) {
844            scrollInDirection(&focusCandidate.visibleNode->document(), type);
845            return true;
846        }
847        // Navigate into a new frame.
848        LayoutRect rect;
849        Element* focusedElement = toLocalFrame(focusedOrMainFrame())->document()->focusedElement();
850        if (focusedElement && !hasOffscreenRect(focusedElement))
851            rect = nodeRectInAbsoluteCoordinates(focusedElement, true /* ignore border */);
852        toLocalFrame(frameElement->contentFrame())->document()->updateLayoutIgnorePendingStylesheets();
853        if (!advanceFocusDirectionallyInContainer(toLocalFrame(frameElement->contentFrame())->document(), rect, type)) {
854            // The new frame had nothing interesting, need to find another candidate.
855            return advanceFocusDirectionallyInContainer(container, nodeRectInAbsoluteCoordinates(focusCandidate.visibleNode, true), type);
856        }
857        return true;
858    }
859
860    if (canScrollInDirection(focusCandidate.visibleNode, type)) {
861        if (focusCandidate.isOffscreenAfterScrolling) {
862            scrollInDirection(focusCandidate.visibleNode, type);
863            return true;
864        }
865        // Navigate into a new scrollable container.
866        LayoutRect startingRect;
867        Element* focusedElement = toLocalFrame(focusedOrMainFrame())->document()->focusedElement();
868        if (focusedElement && !hasOffscreenRect(focusedElement))
869            startingRect = nodeRectInAbsoluteCoordinates(focusedElement, true);
870        return advanceFocusDirectionallyInContainer(focusCandidate.visibleNode, startingRect, type);
871    }
872    if (focusCandidate.isOffscreenAfterScrolling) {
873        Node* container = focusCandidate.enclosingScrollableBox;
874        scrollInDirection(container, type);
875        return true;
876    }
877
878    // We found a new focus node, navigate to it.
879    Element* element = toElement(focusCandidate.focusableNode);
880    ASSERT(element);
881
882    element->focus(false, type);
883    return true;
884}
885
886bool FocusController::advanceFocusDirectionally(FocusType type)
887{
888    // FIXME: Directional focus changes don't yet work with RemoteFrames.
889    if (!focusedOrMainFrame()->isLocalFrame())
890        return false;
891    LocalFrame* curFrame = toLocalFrame(focusedOrMainFrame());
892    ASSERT(curFrame);
893
894    Document* focusedDocument = curFrame->document();
895    if (!focusedDocument)
896        return false;
897
898    Element* focusedElement = focusedDocument->focusedElement();
899    Node* container = focusedDocument;
900
901    if (container->isDocumentNode())
902        toDocument(container)->updateLayoutIgnorePendingStylesheets();
903
904    // Figure out the starting rect.
905    LayoutRect startingRect;
906    if (focusedElement) {
907        if (!hasOffscreenRect(focusedElement)) {
908            container = scrollableEnclosingBoxOrParentFrameForNodeInDirection(type, focusedElement);
909            startingRect = nodeRectInAbsoluteCoordinates(focusedElement, true /* ignore border */);
910        } else if (isHTMLAreaElement(*focusedElement)) {
911            HTMLAreaElement& area = toHTMLAreaElement(*focusedElement);
912            container = scrollableEnclosingBoxOrParentFrameForNodeInDirection(type, area.imageElement());
913            startingRect = virtualRectForAreaElementAndDirection(area, type);
914        }
915    }
916
917    bool consumed = false;
918    do {
919        consumed = advanceFocusDirectionallyInContainer(container, startingRect, type);
920        startingRect = nodeRectInAbsoluteCoordinates(container, true /* ignore border */);
921        container = scrollableEnclosingBoxOrParentFrameForNodeInDirection(type, container);
922        if (container && container->isDocumentNode())
923            toDocument(container)->updateLayoutIgnorePendingStylesheets();
924    } while (!consumed && container);
925
926    return consumed;
927}
928
929void FocusController::trace(Visitor* visitor)
930{
931    visitor->trace(m_page);
932    visitor->trace(m_focusedFrame);
933}
934
935} // namespace blink
936