src/third_party/WebKit/Source/core/page/FocusController.cpp

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