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