fb739647cd61b3fd6d5dc83e32f6645b2113b82d
[WebKit-https.git] / Source / WebCore / accessibility / AXObjectCache.cpp
1 /*
2  * Copyright (C) 2008-2019 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
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  * 3.  Neither the name of Apple Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30
31 #if ENABLE(ACCESSIBILITY)
32
33 #include "AXObjectCache.h"
34
35 #include "AXIsolatedObject.h"
36 #include "AXIsolatedTree.h"
37 #include "AXLogger.h"
38 #include "AccessibilityARIAGrid.h"
39 #include "AccessibilityARIAGridCell.h"
40 #include "AccessibilityARIAGridRow.h"
41 #include "AccessibilityAttachment.h"
42 #include "AccessibilityImageMapLink.h"
43 #include "AccessibilityLabel.h"
44 #include "AccessibilityList.h"
45 #include "AccessibilityListBox.h"
46 #include "AccessibilityListBoxOption.h"
47 #include "AccessibilityMathMLElement.h"
48 #include "AccessibilityMediaObject.h"
49 #include "AccessibilityMenuList.h"
50 #include "AccessibilityMenuListOption.h"
51 #include "AccessibilityMenuListPopup.h"
52 #include "AccessibilityProgressIndicator.h"
53 #include "AccessibilityRenderObject.h"
54 #include "AccessibilitySVGElement.h"
55 #include "AccessibilitySVGRoot.h"
56 #include "AccessibilityScrollView.h"
57 #include "AccessibilityScrollbar.h"
58 #include "AccessibilitySlider.h"
59 #include "AccessibilitySpinButton.h"
60 #include "AccessibilityTable.h"
61 #include "AccessibilityTableCell.h"
62 #include "AccessibilityTableColumn.h"
63 #include "AccessibilityTableHeaderContainer.h"
64 #include "AccessibilityTableRow.h"
65 #include "AccessibilityTree.h"
66 #include "AccessibilityTreeItem.h"
67 #include "Document.h"
68 #include "Editing.h"
69 #include "Editor.h"
70 #include "ElementIterator.h"
71 #include "FocusController.h"
72 #include "Frame.h"
73 #include "HTMLAreaElement.h"
74 #include "HTMLCanvasElement.h"
75 #include "HTMLImageElement.h"
76 #include "HTMLInputElement.h"
77 #include "HTMLLabelElement.h"
78 #include "HTMLMediaElement.h"
79 #include "HTMLMeterElement.h"
80 #include "HTMLNames.h"
81 #include "HTMLParserIdioms.h"
82 #include "HTMLTextFormControlElement.h"
83 #include "InlineElementBox.h"
84 #include "MathMLElement.h"
85 #include "Page.h"
86 #include "RenderAttachment.h"
87 #include "RenderLineBreak.h"
88 #include "RenderListBox.h"
89 #include "RenderMathMLOperator.h"
90 #include "RenderMenuList.h"
91 #include "RenderMeter.h"
92 #include "RenderProgress.h"
93 #include "RenderSVGRoot.h"
94 #include "RenderSlider.h"
95 #include "RenderTable.h"
96 #include "RenderTableCell.h"
97 #include "RenderTableRow.h"
98 #include "RenderView.h"
99 #include "RuntimeEnabledFeatures.h"
100 #include "SVGElement.h"
101 #include "ScriptDisallowedScope.h"
102 #include "ScrollView.h"
103 #include "TextBoundaries.h"
104 #include "TextControlInnerElements.h"
105 #include "TextIterator.h"
106
107 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE) && PLATFORM(MAC)
108 #include <pal/spi/cocoa/AccessibilitySupportSPI.h>
109 #include <pal/spi/cocoa/AccessibilitySupportSoftLink.h>
110 #include <pal/spi/mac/HIServicesSPI.h>
111 #endif
112
113 #include <wtf/DataLog.h>
114 #include <wtf/SetForScope.h>
115
116 #if COMPILER(MSVC)
117 // See https://msdn.microsoft.com/en-us/library/1wea5zwe.aspx
118 #pragma warning(disable: 4701)
119 #endif
120
121 namespace WebCore {
122
123 using namespace HTMLNames;
124
125 const AXID InvalidAXID = 0;
126
127 // Post value change notifications for password fields or elements contained in password fields at a 40hz interval to thwart analysis of typing cadence
128 static const Seconds accessibilityPasswordValueChangeNotificationInterval { 25_ms };
129 static const Seconds accessibilityLiveRegionChangedNotificationInterval { 20_ms };
130 static const Seconds accessibilityFocusModalNodeNotificationInterval { 50_ms };
131
132 static bool rendererNeedsDeferredUpdate(const RenderObject& renderer)
133 {
134     ASSERT(!renderer.beingDestroyed());
135     auto& document = renderer.document();
136     return renderer.needsLayout() || document.needsStyleRecalc() || document.inRenderTreeUpdate() || (document.view() && document.view()->layoutContext().isInRenderTreeLayout());
137 }
138
139 static bool nodeAndRendererAreValid(Node* node)
140 {
141     if (!node)
142         return false;
143     
144     auto* renderer = node->renderer();
145     return renderer && !renderer->beingDestroyed();
146 }
147     
148 AccessibilityObjectInclusion AXComputedObjectAttributeCache::getIgnored(AXID id) const
149 {
150     auto it = m_idMapping.find(id);
151     return it != m_idMapping.end() ? it->value.ignored : AccessibilityObjectInclusion::DefaultBehavior;
152 }
153
154 void AXComputedObjectAttributeCache::setIgnored(AXID id, AccessibilityObjectInclusion inclusion)
155 {
156     HashMap<AXID, CachedAXObjectAttributes>::iterator it = m_idMapping.find(id);
157     if (it != m_idMapping.end())
158         it->value.ignored = inclusion;
159     else {
160         CachedAXObjectAttributes attributes;
161         attributes.ignored = inclusion;
162         m_idMapping.set(id, attributes);
163     }
164 }
165
166 AccessibilityReplacedText::AccessibilityReplacedText(const VisibleSelection& selection)
167 {
168     if (AXObjectCache::accessibilityEnabled()) {
169         m_replacedRange.startIndex.value = indexForVisiblePosition(selection.start(), m_replacedRange.startIndex.scope);
170         if (selection.isRange()) {
171             m_replacedText = AccessibilityObject::stringForVisiblePositionRange(selection);
172             m_replacedRange.endIndex.value = indexForVisiblePosition(selection.end(), m_replacedRange.endIndex.scope);
173         } else
174             m_replacedRange.endIndex = m_replacedRange.startIndex;
175     }
176 }
177
178 void AccessibilityReplacedText::postTextStateChangeNotification(AXObjectCache* cache, AXTextEditType type, const String& text, const VisibleSelection& selection)
179 {
180     if (!cache)
181         return;
182     if (!AXObjectCache::accessibilityEnabled())
183         return;
184
185     VisiblePosition position = selection.start();
186     auto* node = highestEditableRoot(position.deepEquivalent(), HasEditableAXRole);
187     if (m_replacedText.length())
188         cache->postTextReplacementNotification(node, AXTextEditTypeDelete, m_replacedText, type, text, position);
189     else
190         cache->postTextStateChangeNotification(node, type, text, position);
191 }
192
193 bool AXObjectCache::gAccessibilityEnabled = false;
194 bool AXObjectCache::gAccessibilityEnhancedUserInterfaceEnabled = false;
195
196 void AXObjectCache::enableAccessibility()
197 {
198     gAccessibilityEnabled = true;
199 }
200
201 void AXObjectCache::disableAccessibility()
202 {
203     gAccessibilityEnabled = false;
204 }
205
206 void AXObjectCache::setEnhancedUserInterfaceAccessibility(bool flag)
207 {
208     gAccessibilityEnhancedUserInterfaceEnabled = flag;
209 #if PLATFORM(MAC)
210     if (flag)
211         enableAccessibility();
212 #endif
213 }
214
215 AXObjectCache::AXObjectCache(Document& document)
216     : m_document(document)
217     , m_pageID(document.pageID())
218     , m_notificationPostTimer(*this, &AXObjectCache::notificationPostTimerFired)
219     , m_passwordNotificationPostTimer(*this, &AXObjectCache::passwordNotificationPostTimerFired)
220     , m_liveRegionChangedPostTimer(*this, &AXObjectCache::liveRegionChangedNotificationPostTimerFired)
221     , m_focusModalNodeTimer(*this, &AXObjectCache::focusModalNodeTimerFired)
222     , m_currentModalNode(nullptr)
223     , m_performCacheUpdateTimer(*this, &AXObjectCache::performCacheUpdateTimerFired)
224 {
225 }
226
227 AXObjectCache::~AXObjectCache()
228 {
229     m_notificationPostTimer.stop();
230     m_liveRegionChangedPostTimer.stop();
231     m_focusModalNodeTimer.stop();
232     m_performCacheUpdateTimer.stop();
233
234     for (const auto& object : m_objects.values())
235         object->detach(AccessibilityDetachmentType::CacheDestroyed);
236
237 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
238     if (m_pageID)
239         AXIsolatedTree::removeTreeForPageID(*m_pageID);
240 #endif
241 }
242
243 void AXObjectCache::findModalNodes()
244 {
245     // Traverse the DOM tree to look for the aria-modal=true nodes.
246     for (Element* element = ElementTraversal::firstWithin(document().rootNode()); element; element = ElementTraversal::nextIncludingPseudo(*element)) {
247         // Must have dialog or alertdialog role
248         if (!nodeHasRole(element, "dialog") && !nodeHasRole(element, "alertdialog"))
249             continue;
250         if (!equalLettersIgnoringASCIICase(element->attributeWithoutSynchronization(aria_modalAttr), "true"))
251             continue;
252
253         m_modalNodesSet.add(element);
254     }
255
256     m_modalNodesInitialized = true;
257 }
258
259 Node* AXObjectCache::currentModalNode()
260 {
261     // There might be multiple nodes with aria-modal=true set.
262     // We use this function to pick the one we want.
263     m_currentModalNode = nullptr;
264     if (m_modalNodesSet.isEmpty())
265         return nullptr;
266
267     // If any of the modal nodes contains the keyboard focus, we want to pick that one.
268     // If not, we want to pick the last visible dialog in the DOM.
269     RefPtr<Element> focusedElement = document().focusedElement();
270     RefPtr<Node> lastVisible;
271     for (auto& node : m_modalNodesSet) {
272         if (isNodeVisible(node)) {
273             if (focusedElement && focusedElement->isDescendantOf(node)) {
274                 m_currentModalNode = node;
275                 break;
276             }
277
278             lastVisible = node;
279         }
280     }
281
282     if (!m_currentModalNode)
283         m_currentModalNode = lastVisible.get();
284
285     return m_currentModalNode;
286 }
287
288 bool AXObjectCache::isNodeVisible(Node* node) const
289 {
290     if (!is<Element>(node))
291         return false;
292     
293     RenderObject* renderer = node->renderer();
294     if (!renderer)
295         return false;
296     const RenderStyle& style = renderer->style();
297     if (style.display() == DisplayType::None || style.visibility() != Visibility::Visible)
298         return false;
299     
300     // We also need to consider aria hidden status.
301     if (!isNodeAriaVisible(node))
302         return false;
303     
304     return true;
305 }
306
307 Node* AXObjectCache::modalNode()
308 {
309     // This function returns the valid aria modal node.
310     if (!m_modalNodesInitialized) {
311         findModalNodes();
312         return currentModalNode();
313     }
314
315     if (m_modalNodesSet.isEmpty())
316         return nullptr;
317
318     // Check the cached current valid aria modal node first.
319     // Usually when one dialog sets aria-modal=true, that dialog is the one we want.
320     if (isNodeVisible(m_currentModalNode))
321         return m_currentModalNode;
322
323     // Recompute the valid aria modal node when m_currentModalNode is null or hidden.
324     return currentModalNode();
325 }
326
327 AccessibilityObject* AXObjectCache::focusedImageMapUIElement(HTMLAreaElement* areaElement)
328 {
329     // Find the corresponding accessibility object for the HTMLAreaElement. This should be
330     // in the list of children for its corresponding image.
331     if (!areaElement)
332         return nullptr;
333     
334     HTMLImageElement* imageElement = areaElement->imageElement();
335     if (!imageElement)
336         return nullptr;
337     
338     AccessibilityObject* axRenderImage = areaElement->document().axObjectCache()->getOrCreate(imageElement);
339     if (!axRenderImage)
340         return nullptr;
341     
342     for (const auto& child : axRenderImage->children()) {
343         if (!is<AccessibilityImageMapLink>(*child))
344             continue;
345
346         if (downcast<AccessibilityImageMapLink>(*child).areaElement() == areaElement)
347             return downcast<AccessibilityImageMapLink>(child.get());
348     }
349     
350     return nullptr;
351 }
352
353 AXCoreObject* AXObjectCache::focusedObject(Document& document)
354 {
355     Element* focusedElement = document.focusedElement();
356     if (is<HTMLAreaElement>(focusedElement))
357         return focusedImageMapUIElement(downcast<HTMLAreaElement>(focusedElement));
358
359     auto* axObjectCache = document.axObjectCache();
360     if (!axObjectCache)
361         return nullptr;
362
363     AXCoreObject* focus = axObjectCache->getOrCreate(focusedElement ? focusedElement : static_cast<Node*>(&document));
364     if (!focus)
365         return nullptr;
366
367     if (focus->shouldFocusActiveDescendant()) {
368         if (auto* descendant = focus->activeDescendant())
369             focus = descendant;
370     }
371
372     // the HTML element, for example, is focusable but has an AX object that is ignored
373     if (focus->accessibilityIsIgnored())
374         focus = focus->parentObjectUnignored();
375
376     return focus;
377 }
378
379 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
380 AXCoreObject* AXObjectCache::isolatedTreeFocusedObject()
381 {
382     if (auto tree = getOrCreateIsolatedTree())
383         return tree->focusedNode().get();
384
385     // Should not get here, couldn't create the IsolatedTree.
386     ASSERT_NOT_REACHED();
387     return nullptr;
388 }
389
390 void AXObjectCache::setIsolatedTreeFocusedObject(Node* focusedNode)
391 {
392     ASSERT(isMainThread());
393     if (!m_pageID)
394         return;
395
396     auto* focus = getOrCreate(focusedNode);
397
398     if (auto tree = AXIsolatedTree::treeForPageID(*m_pageID))
399         tree->setFocusedNodeID(focus ? focus->objectID() : InvalidAXID);
400 }
401 #endif
402
403 AXCoreObject* AXObjectCache::focusedUIElementForPage(const Page* page)
404 {
405     ASSERT(isMainThread());
406     if (!gAccessibilityEnabled)
407         return nullptr;
408
409     // get the focused node in the page
410     Document* focusedDocument = page->focusController().focusedOrMainFrame().document();
411     if (!focusedDocument)
412         return nullptr;
413
414     // Call this before isolated or non-isolated cases so the document is up to do.
415     focusedDocument->updateStyleIfNeeded();
416     
417 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
418     if (isIsolatedTreeEnabled())
419         return isolatedTreeFocusedObject();
420 #endif
421
422     return focusedObject(*focusedDocument);
423 }
424
425 AccessibilityObject* AXObjectCache::get(Widget* widget)
426 {
427     if (!widget)
428         return nullptr;
429         
430     AXID axID = m_widgetObjectMapping.get(widget);
431     ASSERT(!HashTraits<AXID>::isDeletedValue(axID));
432     if (!axID)
433         return nullptr;
434     
435     return m_objects.get(axID);    
436 }
437     
438 AccessibilityObject* AXObjectCache::get(RenderObject* renderer)
439 {
440     if (!renderer)
441         return nullptr;
442     
443     AXID axID = m_renderObjectMapping.get(renderer);
444     ASSERT(!HashTraits<AXID>::isDeletedValue(axID));
445     if (!axID)
446         return nullptr;
447
448     return m_objects.get(axID);    
449 }
450
451 AccessibilityObject* AXObjectCache::get(Node* node)
452 {
453     if (!node)
454         return nullptr;
455
456     AXID renderID = node->renderer() ? m_renderObjectMapping.get(node->renderer()) : 0;
457     ASSERT(!HashTraits<AXID>::isDeletedValue(renderID));
458
459     AXID nodeID = m_nodeObjectMapping.get(node);
460     ASSERT(!HashTraits<AXID>::isDeletedValue(nodeID));
461
462     if (node->renderer() && nodeID && !renderID) {
463         // This can happen if an AccessibilityNodeObject is created for a node that's not
464         // rendered, but later something changes and it gets a renderer (like if it's
465         // reparented).
466         remove(nodeID);
467         return nullptr;
468     }
469
470     if (renderID)
471         return m_objects.get(renderID);
472
473     if (!nodeID)
474         return nullptr;
475
476     return m_objects.get(nodeID);
477 }
478
479 // FIXME: This probably belongs on Node.
480 // FIXME: This should take a const char*, but one caller passes nullAtom().
481 bool nodeHasRole(Node* node, const String& role)
482 {
483     if (!node || !is<Element>(node))
484         return false;
485
486     auto& roleValue = downcast<Element>(*node).attributeWithoutSynchronization(roleAttr);
487     if (role.isNull())
488         return roleValue.isEmpty();
489     if (roleValue.isEmpty())
490         return false;
491
492     return SpaceSplitString(roleValue, true).contains(role);
493 }
494
495 static Ref<AccessibilityObject> createFromRenderer(RenderObject* renderer)
496 {
497     // FIXME: How could renderer->node() ever not be an Element?
498     Node* node = renderer->node();
499
500     // If the node is aria role="list" or the aria role is empty and its a
501     // ul/ol/dl type (it shouldn't be a list if aria says otherwise).
502     if (node && ((nodeHasRole(node, "list") || nodeHasRole(node, "directory"))
503                       || (nodeHasRole(node, nullAtom()) && (node->hasTagName(ulTag) || node->hasTagName(olTag) || node->hasTagName(dlTag)))))
504         return AccessibilityList::create(renderer);
505
506     // aria tables
507     if (nodeHasRole(node, "grid") || nodeHasRole(node, "treegrid") || nodeHasRole(node, "table"))
508         return AccessibilityARIAGrid::create(renderer);
509     if (nodeHasRole(node, "row"))
510         return AccessibilityARIAGridRow::create(renderer);
511     if (nodeHasRole(node, "gridcell") || nodeHasRole(node, "cell") || nodeHasRole(node, "columnheader") || nodeHasRole(node, "rowheader"))
512         return AccessibilityARIAGridCell::create(renderer);
513
514     // aria tree
515     if (nodeHasRole(node, "tree"))
516         return AccessibilityTree::create(renderer);
517     if (nodeHasRole(node, "treeitem"))
518         return AccessibilityTreeItem::create(renderer);
519
520     if (node && is<HTMLLabelElement>(node) && nodeHasRole(node, nullAtom()))
521         return AccessibilityLabel::create(renderer);
522
523 #if PLATFORM(IOS_FAMILY)
524     if (is<HTMLMediaElement>(node) && nodeHasRole(node, nullAtom()))
525         return AccessibilityMediaObject::create(renderer);
526 #endif
527
528     if (is<RenderSVGRoot>(*renderer))
529         return AccessibilitySVGRoot::create(renderer);
530     
531     if (is<SVGElement>(node))
532         return AccessibilitySVGElement::create(renderer);
533
534 #if ENABLE(MATHML)
535     // The mfenced element creates anonymous RenderMathMLOperators which should be treated
536     // as MathML elements and assigned the MathElementRole so that platform logic regarding
537     // inclusion and role mapping is not bypassed.
538     bool isAnonymousOperator = renderer->isAnonymous() && is<RenderMathMLOperator>(*renderer);
539     if (isAnonymousOperator || is<MathMLElement>(node))
540         return AccessibilityMathMLElement::create(renderer, isAnonymousOperator);
541 #endif
542
543     if (is<RenderBoxModelObject>(*renderer)) {
544         RenderBoxModelObject& cssBox = downcast<RenderBoxModelObject>(*renderer);
545         if (is<RenderListBox>(cssBox))
546             return AccessibilityListBox::create(&downcast<RenderListBox>(cssBox));
547         if (is<RenderMenuList>(cssBox))
548             return AccessibilityMenuList::create(&downcast<RenderMenuList>(cssBox));
549
550         // standard tables
551         if (is<RenderTable>(cssBox))
552             return AccessibilityTable::create(&downcast<RenderTable>(cssBox));
553         if (is<RenderTableRow>(cssBox))
554             return AccessibilityTableRow::create(&downcast<RenderTableRow>(cssBox));
555         if (is<RenderTableCell>(cssBox))
556             return AccessibilityTableCell::create(&downcast<RenderTableCell>(cssBox));
557
558         // progress bar
559         if (is<RenderProgress>(cssBox))
560             return AccessibilityProgressIndicator::create(&downcast<RenderProgress>(cssBox));
561
562 #if ENABLE(ATTACHMENT_ELEMENT)
563         if (is<RenderAttachment>(cssBox))
564             return AccessibilityAttachment::create(&downcast<RenderAttachment>(cssBox));
565 #endif
566 #if ENABLE(METER_ELEMENT)
567         if (is<RenderMeter>(cssBox))
568             return AccessibilityProgressIndicator::create(&downcast<RenderMeter>(cssBox));
569 #endif
570
571         // input type=range
572         if (is<RenderSlider>(cssBox))
573             return AccessibilitySlider::create(&downcast<RenderSlider>(cssBox));
574     }
575
576     return AccessibilityRenderObject::create(renderer);
577 }
578
579 static Ref<AccessibilityObject> createFromNode(Node* node)
580 {
581     return AccessibilityNodeObject::create(node);
582 }
583
584 void AXObjectCache::cacheAndInitializeWrapper(AccessibilityObject* newObject, DOMObjectVariant domObject)
585 {
586     ASSERT(newObject);
587     AXID axID = getAXID(newObject);
588     WTF::switchOn(domObject,
589         [&axID, this] (RenderObject* typedValue) { m_renderObjectMapping.set(typedValue, axID); },
590         [&axID, this] (Node* typedValue) { m_nodeObjectMapping.set(typedValue, axID); },
591         [&axID, this] (Widget* typedValue) { m_widgetObjectMapping.set(typedValue, axID); },
592         [] (auto&) { }
593     );
594     m_objects.set(axID, newObject);
595     newObject->init();
596     attachWrapper(newObject);
597 }
598
599 AccessibilityObject* AXObjectCache::getOrCreate(Widget* widget)
600 {
601     if (!widget)
602         return nullptr;
603
604     if (AccessibilityObject* obj = get(widget))
605         return obj;
606     
607     RefPtr<AccessibilityObject> newObj;
608     if (is<ScrollView>(*widget))
609         newObj = AccessibilityScrollView::create(downcast<ScrollView>(widget));
610     else if (is<Scrollbar>(*widget))
611         newObj = AccessibilityScrollbar::create(downcast<Scrollbar>(widget));
612
613     // Will crash later if we have two objects for the same widget.
614     ASSERT(!get(widget));
615
616     // Catch the case if an (unsupported) widget type is used. Only FrameView and ScrollBar are supported now.
617     ASSERT(newObj);
618     if (!newObj)
619         return nullptr;
620
621     cacheAndInitializeWrapper(newObj.get(), widget);
622     return newObj.get();
623 }
624
625 AccessibilityObject* AXObjectCache::getOrCreate(Node* node)
626 {
627     if (!node)
628         return nullptr;
629
630     if (AccessibilityObject* obj = get(node))
631         return obj;
632
633     if (node->renderer())
634         return getOrCreate(node->renderer());
635
636     if (!node->parentElement())
637         return nullptr;
638     
639     // It's only allowed to create an AccessibilityObject from a Node if it's in a canvas subtree.
640     // Or if it's a hidden element, but we still want to expose it because of other ARIA attributes.
641     bool inCanvasSubtree = lineageOfType<HTMLCanvasElement>(*node->parentElement()).first();
642     bool isHidden = isNodeAriaVisible(node);
643
644     bool insideMeterElement = false;
645 #if ENABLE(METER_ELEMENT)
646     insideMeterElement = is<HTMLMeterElement>(*node->parentElement());
647 #endif
648     
649     if (!inCanvasSubtree && !isHidden && !insideMeterElement)
650         return nullptr;
651
652     auto protectedNode = makeRef(*node);
653
654     // Fallback content is only focusable as long as the canvas is displayed and visible.
655     // Update the style before Element::isFocusable() gets called.
656     if (inCanvasSubtree)
657         node->document().updateStyleIfNeeded();
658
659     RefPtr<AccessibilityObject> newObj = createFromNode(node);
660
661     // Will crash later if we have two objects for the same node.
662     ASSERT(!get(node));
663
664     cacheAndInitializeWrapper(newObj.get(), node);
665     newObj->setLastKnownIsIgnoredValue(newObj->accessibilityIsIgnored());
666     // Sometimes asking accessibilityIsIgnored() will cause the newObject to be deallocated, and then
667     // it will disappear when this function is finished, leading to a use-after-free.
668     if (newObj->isDetached())
669         return nullptr;
670     
671     return newObj.get();
672 }
673
674 AccessibilityObject* AXObjectCache::getOrCreate(RenderObject* renderer)
675 {
676     if (!renderer)
677         return nullptr;
678
679     if (AccessibilityObject* obj = get(renderer))
680         return obj;
681
682     RefPtr<AccessibilityObject> newObj = createFromRenderer(renderer);
683
684     // Will crash later if we have two objects for the same renderer.
685     ASSERT(!get(renderer));
686
687     cacheAndInitializeWrapper(newObj.get(), renderer);
688     newObj->setLastKnownIsIgnoredValue(newObj->accessibilityIsIgnored());
689     // Sometimes asking accessibilityIsIgnored() will cause the newObject to be deallocated, and then
690     // it will disappear when this function is finished, leading to a use-after-free.
691     if (newObj->isDetached())
692         return nullptr;
693     
694     return newObj.get();
695 }
696
697 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
698 bool AXObjectCache::clientSupportsIsolatedTree()
699 {
700     if (!RuntimeEnabledFeatures::sharedFeatures().isAccessibilityIsolatedTreeEnabled())
701         return false;
702
703     return _AXGetClientForCurrentRequestUntrusted() == kAXClientTypeVoiceOver;
704 }
705
706 bool AXObjectCache::isIsolatedTreeEnabled()
707 {
708     if (UNLIKELY(_AXGetClientForCurrentRequestUntrusted() == kAXClientTypeWebKitTesting))
709         return true;
710
711     return _AXSIsolatedTreeModeFunctionIsAvailable() && _AXSIsolatedTreeMode_Soft() != AXSIsolatedTreeModeOff && clientSupportsIsolatedTree();
712 }
713
714 #endif
715
716 AXCoreObject* AXObjectCache::rootObject()
717 {
718     if (!gAccessibilityEnabled)
719         return nullptr;
720
721 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
722     if (isIsolatedTreeEnabled())
723         return isolatedTreeRootObject();
724 #endif
725
726     return getOrCreate(m_document.view());
727 }
728
729 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
730
731 void AXObjectCache::initializeSecondaryAXThread()
732 {
733     // Now that we have created our tree, initialize the secondary thread,
734     // so future requests come in on the other thread.
735     if (_AXSIsolatedTreeModeFunctionIsAvailable() && _AXSIsolatedTreeMode_Soft() == AXSIsolatedTreeModeSecondaryThread)
736         _AXUIElementUseSecondaryAXThread(true);
737 }
738
739 RefPtr<AXIsolatedTree> AXObjectCache::getOrCreateIsolatedTree() const
740 {
741     if (!m_pageID)
742         return nullptr;
743
744     auto tree = AXIsolatedTree::treeForPageID(*m_pageID);
745     if (!tree) {
746         tree = Accessibility::retrieveValueFromMainThread<RefPtr<AXIsolatedTree>>([this] () -> RefPtr<AXIsolatedTree> {
747             return generateIsolatedTree(*m_pageID, m_document);
748         });
749         AXObjectCache::initializeSecondaryAXThread();
750     }
751
752     return tree;
753 }
754
755 AXCoreObject* AXObjectCache::isolatedTreeRootObject()
756 {
757     if (auto tree = getOrCreateIsolatedTree())
758         return tree->rootNode().get();
759
760     // Should not get here, couldn't create the IsolatedTree.
761     ASSERT_NOT_REACHED();
762     return nullptr;
763 }
764 #endif
765
766 bool AXObjectCache::canUseSecondaryAXThread()
767 {
768 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE) && PLATFORM(MAC)
769     if (_AXUIElementRequestServicedBySecondaryAXThread())
770         return true;
771
772     // _AXUIElementRequestServicedBySecondaryAXThread returns false for
773     // LayoutTests, but we still want to run LayoutTests using isolated tree on
774     // a secondary thread to simulate the actual execution.
775     return _AXSIsolatedTreeModeFunctionIsAvailable() && _AXSIsolatedTreeMode_Soft() == AXSIsolatedTreeModeSecondaryThread && clientSupportsIsolatedTree();
776 #else
777     return false;
778 #endif
779 }
780
781 AccessibilityObject* AXObjectCache::rootObjectForFrame(Frame* frame)
782 {
783     if (!gAccessibilityEnabled)
784         return nullptr;
785
786     if (!frame)
787         return nullptr;
788     return getOrCreate(frame->view());
789 }    
790     
791 AccessibilityObject* AXObjectCache::getOrCreate(AccessibilityRole role)
792 {
793     RefPtr<AccessibilityObject> obj;
794
795     // will be filled in...
796     switch (role) {
797     case AccessibilityRole::ListBoxOption:
798         obj = AccessibilityListBoxOption::create();
799         break;
800     case AccessibilityRole::ImageMapLink:
801         obj = AccessibilityImageMapLink::create();
802         break;
803     case AccessibilityRole::Column:
804         obj = AccessibilityTableColumn::create();
805         break;            
806     case AccessibilityRole::TableHeaderContainer:
807         obj = AccessibilityTableHeaderContainer::create();
808         break;   
809     case AccessibilityRole::SliderThumb:
810         obj = AccessibilitySliderThumb::create();
811         break;
812     case AccessibilityRole::MenuListPopup:
813         obj = AccessibilityMenuListPopup::create();
814         break;
815     case AccessibilityRole::MenuListOption:
816         obj = AccessibilityMenuListOption::create();
817         break;
818     case AccessibilityRole::SpinButton:
819         obj = AccessibilitySpinButton::create();
820         break;
821     case AccessibilityRole::SpinButtonPart:
822         obj = AccessibilitySpinButtonPart::create();
823         break;
824     default:
825         obj = nullptr;
826     }
827
828     if (!obj)
829         return nullptr;
830
831     cacheAndInitializeWrapper(obj.get());
832     return obj.get();
833 }
834
835 void AXObjectCache::remove(AXID axID)
836 {
837     AXTRACE("AXObjectCache::remove");
838     AXLOG(makeString("AXID ", axID));
839
840     if (!axID)
841         return;
842
843 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
844     if (m_pageID) {
845         if (auto tree = AXIsolatedTree::treeForPageID(*m_pageID))
846             tree->removeNode(axID);
847     }
848 #endif
849
850     auto object = m_objects.take(axID);
851     if (!object)
852         return;
853
854     object->detach(AccessibilityDetachmentType::ElementDestroyed);
855
856     m_idsInUse.remove(axID);
857     ASSERT(m_objects.size() >= m_idsInUse.size());
858 }
859     
860 void AXObjectCache::remove(RenderObject* renderer)
861 {
862     if (!renderer)
863         return;
864     remove(m_renderObjectMapping.take(renderer));
865 }
866
867 void AXObjectCache::remove(Node& node)
868 {
869     if (is<Element>(node)) {
870         m_deferredTextFormControlValue.remove(downcast<Element>(&node));
871         m_deferredAttributeChange.remove(downcast<Element>(&node));
872     }
873     m_deferredChildrenChangedNodeList.remove(&node);
874     m_deferredTextChangedList.remove(&node);
875     // Remove the entry if the new focused node is being removed.
876     m_deferredFocusedNodeChange.removeAllMatching([&node](auto& entry) -> bool {
877         return entry.second == &node;
878     });
879     // Set nullptr to the old focused node if it is being removed.
880     std::for_each(m_deferredFocusedNodeChange.begin(), m_deferredFocusedNodeChange.end(), [&node](auto& entry) {
881         if (entry.first == &node)
882             entry.first = nullptr;
883     });
884
885     removeNodeForUse(node);
886
887     remove(m_nodeObjectMapping.take(&node));
888
889     if (m_currentModalNode == &node)
890         m_currentModalNode = nullptr;
891     m_modalNodesSet.remove(&node);
892
893     remove(node.renderer());
894 }
895
896 void AXObjectCache::remove(Widget* view)
897 {
898     if (!view)
899         return;
900     remove(m_widgetObjectMapping.take(view));
901 }
902     
903     
904 #if !PLATFORM(WIN)
905 AXID AXObjectCache::platformGenerateAXID() const
906 {
907     static AXID lastUsedID = 0;
908
909     // Generate a new ID.
910     AXID objID = lastUsedID;
911     do {
912         ++objID;
913     } while (!objID || HashTraits<AXID>::isDeletedValue(objID) || m_idsInUse.contains(objID));
914
915     lastUsedID = objID;
916
917     return objID;
918 }
919 #endif
920
921 AXID AXObjectCache::getAXID(AccessibilityObject* obj)
922 {
923     // check for already-assigned ID
924     AXID objID = obj->objectID();
925     if (objID) {
926         ASSERT(m_idsInUse.contains(objID));
927         return objID;
928     }
929
930     objID = platformGenerateAXID();
931
932     m_idsInUse.add(objID);
933     obj->setObjectID(objID);
934     
935     return objID;
936 }
937
938 void AXObjectCache::textChanged(Node* node)
939 {
940     textChanged(getOrCreate(node));
941 }
942
943 void AXObjectCache::textChanged(AccessibilityObject* obj)
944 {
945     if (!obj)
946         return;
947
948     bool parentAlreadyExists = obj->parentObjectIfExists();
949     obj->textChanged();
950     postNotification(obj, obj->document(), AXObjectCache::AXTextChanged);
951     if (parentAlreadyExists)
952         obj->notifyIfIgnoredValueChanged();
953 }
954
955 void AXObjectCache::updateCacheAfterNodeIsAttached(Node* node)
956 {
957     // Calling get() will update the AX object if we had an AccessibilityNodeObject but now we need
958     // an AccessibilityRenderObject, because it was reparented to a location outside of a canvas.
959     get(node);
960 }
961
962 void AXObjectCache::handleMenuOpened(Node* node)
963 {
964     if (!node || !node->renderer() || !nodeHasRole(node, "menu"))
965         return;
966     
967     postNotification(getOrCreate(node), &document(), AXMenuOpened);
968 }
969     
970 void AXObjectCache::handleLiveRegionCreated(Node* node)
971 {
972     if (!is<Element>(node) || !node->renderer())
973         return;
974     
975     Element* element = downcast<Element>(node);
976     String liveRegionStatus = element->attributeWithoutSynchronization(aria_liveAttr);
977     if (liveRegionStatus.isEmpty()) {
978         const AtomString& ariaRole = element->attributeWithoutSynchronization(roleAttr);
979         if (!ariaRole.isEmpty())
980             liveRegionStatus = AccessibilityObject::defaultLiveRegionStatusForRole(AccessibilityObject::ariaRoleToWebCoreRole(ariaRole));
981     }
982     
983     if (AccessibilityObject::liveRegionStatusIsEnabled(liveRegionStatus))
984         postNotification(getOrCreate(node), &document(), AXLiveRegionCreated);
985 }
986     
987 void AXObjectCache::childrenChanged(Node* node, Node* newChild)
988 {
989     if (newChild)
990         m_deferredChildrenChangedNodeList.add(newChild);
991
992     childrenChanged(get(node));
993 }
994
995 void AXObjectCache::childrenChanged(RenderObject* renderer, RenderObject* newChild)
996 {
997     if (!renderer)
998         return;
999
1000     if (newChild && newChild->node())
1001         m_deferredChildrenChangedNodeList.add(newChild->node());
1002
1003     childrenChanged(get(renderer));
1004 }
1005
1006 void AXObjectCache::childrenChanged(AXCoreObject* obj)
1007 {
1008     if (!obj)
1009         return;
1010
1011     m_deferredChildrenChangedList.add(obj);
1012 }
1013
1014 void AXObjectCache::notificationPostTimerFired()
1015 {
1016     // During LayoutTests, accessibility may be disabled between the time the notifications are queued and the timer fires.
1017     // Thus check here and return if accessibility is disabled.
1018     if (!accessibilityEnabled())
1019         return;
1020
1021     Ref<Document> protectorForCacheOwner(m_document);
1022     m_notificationPostTimer.stop();
1023
1024     if (!m_document.hasLivingRenderTree())
1025         return;
1026
1027     // In tests, posting notifications has a tendency to immediately queue up other notifications, which can lead to unexpected behavior
1028     // when the notification list is cleared at the end. Instead copy this list at the start.
1029     auto notifications = WTFMove(m_notificationsToPost);
1030
1031     for (const auto& note : notifications) {
1032         AXCoreObject* obj = note.first.get();
1033         if (!obj->objectID())
1034             continue;
1035
1036         if (!obj->axObjectCache())
1037             continue;
1038         
1039 #ifndef NDEBUG
1040         // Make sure none of the render views are in the process of being layed out.
1041         // Notifications should only be sent after the renderer has finished
1042         if (is<AccessibilityRenderObject>(*obj)) {
1043             if (auto* renderer = downcast<AccessibilityRenderObject>(*obj).renderer())
1044                 ASSERT(!renderer->view().frameView().layoutContext().layoutState());
1045         }
1046 #endif
1047
1048         AXNotification notification = note.second;
1049         
1050         // Ensure that this menu really is a menu. We do this check here so that we don't have to create
1051         // the axChildren when the menu is marked as opening.
1052         if (notification == AXMenuOpened) {
1053             obj->updateChildrenIfNecessary();
1054             if (obj->roleValue() != AccessibilityRole::Menu)
1055                 continue;
1056         }
1057         
1058         if (notification == AXChildrenChanged && obj->parentObjectIfExists() && obj->lastKnownIsIgnoredValue() != obj->accessibilityIsIgnored())
1059             childrenChanged(obj->parentObject());
1060
1061         postPlatformNotification(obj, notification);
1062     }
1063
1064 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
1065     updateIsolatedTree(notifications);
1066 #endif
1067 }
1068
1069 void AXObjectCache::passwordNotificationPostTimerFired()
1070 {
1071 #if PLATFORM(COCOA)
1072     m_passwordNotificationPostTimer.stop();
1073
1074     // In tests, posting notifications has a tendency to immediately queue up other notifications, which can lead to unexpected behavior
1075     // when the notification list is cleared at the end. Instead copy this list at the start.
1076     auto notifications = WTFMove(m_passwordNotificationsToPost);
1077
1078     for (auto& notification : notifications)
1079         postTextStateChangePlatformNotification(notification.get(), AXTextEditTypeInsert, " ", VisiblePosition());
1080 #endif
1081 }
1082     
1083 void AXObjectCache::postNotification(RenderObject* renderer, AXNotification notification, PostTarget postTarget, PostType postType)
1084 {
1085     if (!renderer)
1086         return;
1087     
1088     stopCachingComputedObjectAttributes();
1089
1090     // Get an accessibility object that already exists. One should not be created here
1091     // because a render update may be in progress and creating an AX object can re-trigger a layout
1092     RefPtr<AccessibilityObject> object = get(renderer);
1093     while (!object && renderer) {
1094         renderer = renderer->parent();
1095         object = get(renderer); 
1096     }
1097     
1098     if (!renderer)
1099         return;
1100     
1101     postNotification(object.get(), &renderer->document(), notification, postTarget, postType);
1102 }
1103
1104 void AXObjectCache::postNotification(Node* node, AXNotification notification, PostTarget postTarget, PostType postType)
1105 {
1106     if (!node)
1107         return;
1108     
1109     stopCachingComputedObjectAttributes();
1110
1111     // Get an accessibility object that already exists. One should not be created here
1112     // because a render update may be in progress and creating an AX object can re-trigger a layout
1113     RefPtr<AccessibilityObject> object = get(node);
1114     while (!object && node) {
1115         node = node->parentNode();
1116         object = get(node);
1117     }
1118     
1119     if (!node)
1120         return;
1121     
1122     postNotification(object.get(), &node->document(), notification, postTarget, postType);
1123 }
1124
1125 void AXObjectCache::postNotification(AXCoreObject* object, Document* document, AXNotification notification, PostTarget postTarget, PostType postType)
1126 {
1127     AXTRACE("AXObjectCache::postNotification");
1128     AXLOG(std::make_pair(object, notification));
1129
1130     stopCachingComputedObjectAttributes();
1131
1132     if (object && postTarget == TargetObservableParent)
1133         object = object->observableObject();
1134
1135     if (!object && document)
1136         object = get(document->renderView());
1137
1138     if (!object)
1139         return;
1140
1141     if (postType == PostAsynchronously) {
1142         m_notificationsToPost.append(std::make_pair(object, notification));
1143         if (!m_notificationPostTimer.isActive())
1144             m_notificationPostTimer.startOneShot(0_s);
1145     } else {
1146 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
1147         updateIsolatedTree(*object, notification);
1148 #endif
1149
1150         postPlatformNotification(object, notification);
1151     }
1152 }
1153
1154 void AXObjectCache::checkedStateChanged(Node* node)
1155 {
1156     postNotification(node, AXObjectCache::AXCheckedStateChanged);
1157 }
1158
1159 void AXObjectCache::handleMenuItemSelected(Node* node)
1160 {
1161     if (!node)
1162         return;
1163     
1164     if (!nodeHasRole(node, "menuitem") && !nodeHasRole(node, "menuitemradio") && !nodeHasRole(node, "menuitemcheckbox"))
1165         return;
1166     
1167     if (!downcast<Element>(*node).focused() && !equalLettersIgnoringASCIICase(downcast<Element>(*node).attributeWithoutSynchronization(aria_selectedAttr), "true"))
1168         return;
1169     
1170     postNotification(getOrCreate(node), &document(), AXMenuListItemSelected);
1171 }
1172     
1173 void AXObjectCache::deferFocusedUIElementChangeIfNeeded(Node* oldNode, Node* newNode)
1174 {
1175     if (nodeAndRendererAreValid(newNode) && rendererNeedsDeferredUpdate(*newNode->renderer())) {
1176         m_deferredFocusedNodeChange.append({ oldNode, newNode });
1177         if (!newNode->renderer()->needsLayout() && !m_performCacheUpdateTimer.isActive())
1178             m_performCacheUpdateTimer.startOneShot(0_s);
1179     } else
1180         handleFocusedUIElementChanged(oldNode, newNode);
1181 }
1182     
1183 void AXObjectCache::handleFocusedUIElementChanged(Node* oldNode, Node* newNode)
1184 {
1185 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
1186     setIsolatedTreeFocusedObject(newNode);
1187 #endif
1188
1189     handleMenuItemSelected(newNode);
1190     platformHandleFocusedUIElementChanged(oldNode, newNode);
1191 }
1192     
1193 void AXObjectCache::selectedChildrenChanged(Node* node)
1194 {
1195     handleMenuItemSelected(node);
1196     
1197     // postTarget is TargetObservableParent so that you can pass in any child of an element and it will go up the parent tree
1198     // to find the container which should send out the notification.
1199     postNotification(node, AXSelectedChildrenChanged, TargetObservableParent);
1200 }
1201
1202 void AXObjectCache::selectedChildrenChanged(RenderObject* renderer)
1203 {
1204     if (renderer)
1205         handleMenuItemSelected(renderer->node());
1206
1207     // postTarget is TargetObservableParent so that you can pass in any child of an element and it will go up the parent tree
1208     // to find the container which should send out the notification.
1209     postNotification(renderer, AXSelectedChildrenChanged, TargetObservableParent);
1210 }
1211
1212 #ifndef NDEBUG
1213 void AXObjectCache::showIntent(const AXTextStateChangeIntent &intent)
1214 {
1215     switch (intent.type) {
1216     case AXTextStateChangeTypeUnknown:
1217         dataLog("Unknown");
1218         break;
1219     case AXTextStateChangeTypeEdit:
1220         dataLog("Edit::");
1221         break;
1222     case AXTextStateChangeTypeSelectionMove:
1223         dataLog("Move::");
1224         break;
1225     case AXTextStateChangeTypeSelectionExtend:
1226         dataLog("Extend::");
1227         break;
1228     case AXTextStateChangeTypeSelectionBoundary:
1229         dataLog("Boundary::");
1230         break;
1231     }
1232     switch (intent.type) {
1233     case AXTextStateChangeTypeUnknown:
1234         break;
1235     case AXTextStateChangeTypeEdit:
1236         switch (intent.change) {
1237         case AXTextEditTypeUnknown:
1238             dataLog("Unknown");
1239             break;
1240         case AXTextEditTypeDelete:
1241             dataLog("Delete");
1242             break;
1243         case AXTextEditTypeInsert:
1244             dataLog("Insert");
1245             break;
1246         case AXTextEditTypeDictation:
1247             dataLog("DictationInsert");
1248             break;
1249         case AXTextEditTypeTyping:
1250             dataLog("TypingInsert");
1251             break;
1252         case AXTextEditTypeCut:
1253             dataLog("Cut");
1254             break;
1255         case AXTextEditTypePaste:
1256             dataLog("Paste");
1257             break;
1258         case AXTextEditTypeAttributesChange:
1259             dataLog("AttributesChange");
1260             break;
1261         }
1262         break;
1263     case AXTextStateChangeTypeSelectionMove:
1264     case AXTextStateChangeTypeSelectionExtend:
1265     case AXTextStateChangeTypeSelectionBoundary:
1266         switch (intent.selection.direction) {
1267         case AXTextSelectionDirectionUnknown:
1268             dataLog("Unknown::");
1269             break;
1270         case AXTextSelectionDirectionBeginning:
1271             dataLog("Beginning::");
1272             break;
1273         case AXTextSelectionDirectionEnd:
1274             dataLog("End::");
1275             break;
1276         case AXTextSelectionDirectionPrevious:
1277             dataLog("Previous::");
1278             break;
1279         case AXTextSelectionDirectionNext:
1280             dataLog("Next::");
1281             break;
1282         case AXTextSelectionDirectionDiscontiguous:
1283             dataLog("Discontiguous::");
1284             break;
1285         }
1286         switch (intent.selection.direction) {
1287         case AXTextSelectionDirectionUnknown:
1288         case AXTextSelectionDirectionBeginning:
1289         case AXTextSelectionDirectionEnd:
1290         case AXTextSelectionDirectionPrevious:
1291         case AXTextSelectionDirectionNext:
1292             switch (intent.selection.granularity) {
1293             case AXTextSelectionGranularityUnknown:
1294                 dataLog("Unknown");
1295                 break;
1296             case AXTextSelectionGranularityCharacter:
1297                 dataLog("Character");
1298                 break;
1299             case AXTextSelectionGranularityWord:
1300                 dataLog("Word");
1301                 break;
1302             case AXTextSelectionGranularityLine:
1303                 dataLog("Line");
1304                 break;
1305             case AXTextSelectionGranularitySentence:
1306                 dataLog("Sentence");
1307                 break;
1308             case AXTextSelectionGranularityParagraph:
1309                 dataLog("Paragraph");
1310                 break;
1311             case AXTextSelectionGranularityPage:
1312                 dataLog("Page");
1313                 break;
1314             case AXTextSelectionGranularityDocument:
1315                 dataLog("Document");
1316                 break;
1317             case AXTextSelectionGranularityAll:
1318                 dataLog("All");
1319                 break;
1320             }
1321             break;
1322         case AXTextSelectionDirectionDiscontiguous:
1323             break;
1324         }
1325         break;
1326     }
1327     dataLog("\n");
1328 }
1329 #endif
1330
1331 void AXObjectCache::setTextSelectionIntent(const AXTextStateChangeIntent& intent)
1332 {
1333     m_textSelectionIntent = intent;
1334 }
1335     
1336 void AXObjectCache::setIsSynchronizingSelection(bool isSynchronizing)
1337 {
1338     m_isSynchronizingSelection = isSynchronizing;
1339 }
1340
1341 static bool isPasswordFieldOrContainedByPasswordField(AccessibilityObject* object)
1342 {
1343     return object && (object->isPasswordField() || object->isContainedByPasswordField());
1344 }
1345
1346 void AXObjectCache::postTextStateChangeNotification(Node* node, const AXTextStateChangeIntent& intent, const VisibleSelection& selection)
1347 {
1348     if (!node)
1349         return;
1350
1351 #if PLATFORM(COCOA)
1352     stopCachingComputedObjectAttributes();
1353
1354     postTextStateChangeNotification(getOrCreate(node), intent, selection);
1355 #else
1356     postNotification(node->renderer(), AXObjectCache::AXSelectedTextChanged, TargetObservableParent);
1357     UNUSED_PARAM(intent);
1358     UNUSED_PARAM(selection);
1359 #endif
1360 }
1361
1362 void AXObjectCache::postTextStateChangeNotification(const Position& position, const AXTextStateChangeIntent& intent, const VisibleSelection& selection)
1363 {
1364     Node* node = position.deprecatedNode();
1365     if (!node)
1366         return;
1367
1368     stopCachingComputedObjectAttributes();
1369
1370 #if PLATFORM(COCOA)
1371     AccessibilityObject* object = getOrCreate(node);
1372     if (object && object->accessibilityIsIgnored()) {
1373         if (position.atLastEditingPositionForNode()) {
1374             if (AccessibilityObject* nextSibling = object->nextSiblingUnignored(1))
1375                 object = nextSibling;
1376         } else if (position.atFirstEditingPositionForNode()) {
1377             if (AccessibilityObject* previousSibling = object->previousSiblingUnignored(1))
1378                 object = previousSibling;
1379         }
1380     }
1381
1382     postTextStateChangeNotification(object, intent, selection);
1383 #else
1384     postTextStateChangeNotification(node, intent, selection);
1385 #endif
1386 }
1387
1388 void AXObjectCache::postTextStateChangeNotification(AccessibilityObject* object, const AXTextStateChangeIntent& intent, const VisibleSelection& selection)
1389 {
1390     stopCachingComputedObjectAttributes();
1391
1392 #if PLATFORM(COCOA)
1393     if (object) {
1394         if (isPasswordFieldOrContainedByPasswordField(object))
1395             return;
1396
1397         if (auto observableObject = object->observableObject())
1398             object = observableObject;
1399     }
1400
1401     if (!object)
1402         object = rootWebArea();
1403
1404     if (object) {
1405 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
1406         updateIsolatedTree(*object, AXSelectedTextChanged);
1407 #endif
1408
1409         const AXTextStateChangeIntent& newIntent = (intent.type == AXTextStateChangeTypeUnknown || (m_isSynchronizingSelection && m_textSelectionIntent.type != AXTextStateChangeTypeUnknown)) ? m_textSelectionIntent : intent;
1410         postTextStateChangePlatformNotification(object, newIntent, selection);
1411     }
1412 #else
1413     UNUSED_PARAM(object);
1414     UNUSED_PARAM(intent);
1415     UNUSED_PARAM(selection);
1416 #endif
1417
1418     setTextSelectionIntent(AXTextStateChangeIntent());
1419     setIsSynchronizingSelection(false);
1420 }
1421
1422 void AXObjectCache::postTextStateChangeNotification(Node* node, AXTextEditType type, const String& text, const VisiblePosition& position)
1423 {
1424     if (!node || type == AXTextEditTypeUnknown)
1425         return;
1426
1427     stopCachingComputedObjectAttributes();
1428
1429     AccessibilityObject* object = getOrCreate(node);
1430 #if PLATFORM(COCOA)
1431     if (object) {
1432         if (enqueuePasswordValueChangeNotification(object))
1433             return;
1434         object = object->observableObject();
1435     }
1436
1437     if (!object)
1438         object = rootWebArea();
1439
1440     if (!object)
1441         return;
1442
1443 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
1444     updateIsolatedTree(*object, AXValueChanged);
1445 #endif
1446
1447     postTextStateChangePlatformNotification(object, type, text, position);
1448 #else
1449     nodeTextChangePlatformNotification(object, textChangeForEditType(type), position.deepEquivalent().deprecatedEditingOffset(), text);
1450 #endif
1451 }
1452
1453 void AXObjectCache::postTextReplacementNotification(Node* node, AXTextEditType deletionType, const String& deletedText, AXTextEditType insertionType, const String& insertedText, const VisiblePosition& position)
1454 {
1455     if (!node)
1456         return;
1457     if (deletionType != AXTextEditTypeDelete)
1458         return;
1459     if (!(insertionType == AXTextEditTypeInsert || insertionType == AXTextEditTypeTyping || insertionType == AXTextEditTypeDictation || insertionType == AXTextEditTypePaste))
1460         return;
1461
1462     stopCachingComputedObjectAttributes();
1463
1464     AccessibilityObject* object = getOrCreate(node);
1465 #if PLATFORM(COCOA)
1466     if (object) {
1467         if (enqueuePasswordValueChangeNotification(object))
1468             return;
1469         object = object->observableObject();
1470     }
1471
1472     postTextReplacementPlatformNotification(object, deletionType, deletedText, insertionType, insertedText, position);
1473 #else
1474     nodeTextChangePlatformNotification(object, textChangeForEditType(deletionType), position.deepEquivalent().deprecatedEditingOffset(), deletedText);
1475     nodeTextChangePlatformNotification(object, textChangeForEditType(insertionType), position.deepEquivalent().deprecatedEditingOffset(), insertedText);
1476 #endif
1477 }
1478
1479 void AXObjectCache::postTextReplacementNotificationForTextControl(HTMLTextFormControlElement& textControl, const String& deletedText, const String& insertedText)
1480 {
1481     stopCachingComputedObjectAttributes();
1482
1483     AccessibilityObject* object = getOrCreate(&textControl);
1484 #if PLATFORM(COCOA)
1485     if (object) {
1486         if (enqueuePasswordValueChangeNotification(object))
1487             return;
1488         object = object->observableObject();
1489     }
1490
1491     postTextReplacementPlatformNotificationForTextControl(object, deletedText, insertedText, textControl);
1492 #else
1493     nodeTextChangePlatformNotification(object, textChangeForEditType(AXTextEditTypeDelete), 0, deletedText);
1494     nodeTextChangePlatformNotification(object, textChangeForEditType(AXTextEditTypeInsert), 0, insertedText);
1495 #endif
1496 }
1497
1498 bool AXObjectCache::enqueuePasswordValueChangeNotification(AccessibilityObject* object)
1499 {
1500     if (!isPasswordFieldOrContainedByPasswordField(object))
1501         return false;
1502
1503     AccessibilityObject* observableObject = object->observableObject();
1504     if (!observableObject) {
1505         ASSERT_NOT_REACHED();
1506         // return true even though the enqueue didn't happen because this is a password field and caller shouldn't post a notification
1507         return true;
1508     }
1509
1510     m_passwordNotificationsToPost.add(observableObject);
1511     if (!m_passwordNotificationPostTimer.isActive())
1512         m_passwordNotificationPostTimer.startOneShot(accessibilityPasswordValueChangeNotificationInterval);
1513
1514     return true;
1515 }
1516
1517 void AXObjectCache::frameLoadingEventNotification(Frame* frame, AXLoadingEvent loadingEvent)
1518 {
1519     if (!frame)
1520         return;
1521
1522     // Delegate on the right platform
1523     RenderView* contentRenderer = frame->contentRenderer();
1524     if (!contentRenderer)
1525         return;
1526
1527     AccessibilityObject* obj = getOrCreate(contentRenderer);
1528     frameLoadingEventPlatformNotification(obj, loadingEvent);
1529 }
1530
1531 void AXObjectCache::postLiveRegionChangeNotification(AccessibilityObject* object)
1532 {
1533     if (m_liveRegionChangedPostTimer.isActive())
1534         m_liveRegionChangedPostTimer.stop();
1535
1536     if (!m_liveRegionObjectsSet.contains(object))
1537         m_liveRegionObjectsSet.add(object);
1538
1539     m_liveRegionChangedPostTimer.startOneShot(accessibilityLiveRegionChangedNotificationInterval);
1540 }
1541
1542 void AXObjectCache::liveRegionChangedNotificationPostTimerFired()
1543 {
1544     m_liveRegionChangedPostTimer.stop();
1545
1546     if (m_liveRegionObjectsSet.isEmpty())
1547         return;
1548
1549     for (auto& object : m_liveRegionObjectsSet)
1550         postNotification(object.get(), object->document(), AXObjectCache::AXLiveRegionChanged);
1551     m_liveRegionObjectsSet.clear();
1552 }
1553
1554 static AccessibilityObject* firstFocusableChild(AccessibilityObject* obj)
1555 {
1556     if (!obj)
1557         return nullptr;
1558     
1559     for (auto* child = obj->firstChild(); child; child = child->nextSibling()) {
1560         if (child->canSetFocusAttribute())
1561             return child;
1562         if (AccessibilityObject* focusable = firstFocusableChild(child))
1563             return focusable;
1564     }
1565     return nullptr;
1566 }
1567
1568 void AXObjectCache::focusModalNode()
1569 {
1570     if (m_focusModalNodeTimer.isActive())
1571         m_focusModalNodeTimer.stop();
1572     
1573     m_focusModalNodeTimer.startOneShot(accessibilityFocusModalNodeNotificationInterval);
1574 }
1575
1576 void AXObjectCache::focusModalNodeTimerFired()
1577 {
1578     if (!m_currentModalNode)
1579         return;
1580     
1581     // Don't set focus if we are already focusing onto some element within
1582     // the dialog.
1583     if (m_currentModalNode->contains(document().focusedElement()))
1584         return;
1585     
1586     if (AccessibilityObject* currentModalNodeObject = getOrCreate(m_currentModalNode)) {
1587         if (AccessibilityObject* focusable = firstFocusableChild(currentModalNodeObject))
1588             focusable->setFocused(true);
1589     }
1590 }
1591
1592 void AXObjectCache::handleScrollbarUpdate(ScrollView* view)
1593 {
1594     if (!view)
1595         return;
1596     
1597     // We don't want to create a scroll view from this method, only update an existing one.
1598     if (AccessibilityObject* scrollViewObject = get(view)) {
1599         stopCachingComputedObjectAttributes();
1600         scrollViewObject->updateChildrenIfNecessary();
1601     }
1602 }
1603     
1604 void AXObjectCache::handleAriaExpandedChange(Node* node)
1605 {
1606     if (AccessibilityObject* obj = get(node))
1607         obj->handleAriaExpandedChanged();
1608 }
1609     
1610 void AXObjectCache::handleActiveDescendantChanged(Node* node)
1611 {
1612     if (AccessibilityObject* obj = getOrCreate(node))
1613         obj->handleActiveDescendantChanged();
1614 }
1615
1616 void AXObjectCache::handleAriaRoleChanged(Node* node)
1617 {
1618     stopCachingComputedObjectAttributes();
1619
1620     // Don't make an AX object unless it's needed
1621     if (AccessibilityObject* obj = get(node)) {
1622         obj->updateAccessibilityRole();
1623         obj->notifyIfIgnoredValueChanged();
1624     }
1625 }
1626
1627 void AXObjectCache::deferAttributeChangeIfNeeded(const QualifiedName& attrName, Element* element)
1628 {
1629     if (nodeAndRendererAreValid(element) && rendererNeedsDeferredUpdate(*element->renderer()))
1630         m_deferredAttributeChange.add(element, attrName);
1631     else
1632         handleAttributeChange(attrName, element);
1633 }
1634     
1635 bool AXObjectCache::shouldProcessAttributeChange(const QualifiedName& attrName, Element* element)
1636 {
1637     if (!element)
1638         return false;
1639     
1640     // aria-modal ends up affecting sub-trees that are being shown/hidden so it's likely that
1641     // an AT would not have accessed this node yet.
1642     if (attrName == aria_modalAttr)
1643         return true;
1644     
1645     // If an AXObject has yet to be created, then there's no need to process attribute changes.
1646     // Some of these notifications are processed on the parent, so allow that to proceed as well
1647     if (get(element) || get(element->parentNode()))
1648         return true;
1649
1650     return false;
1651 }
1652     
1653 void AXObjectCache::handleAttributeChange(const QualifiedName& attrName, Element* element)
1654 {
1655     if (!shouldProcessAttributeChange(attrName, element))
1656         return;
1657     
1658     if (attrName == roleAttr)
1659         handleAriaRoleChanged(element);
1660     else if (attrName == altAttr || attrName == titleAttr)
1661         textChanged(element);
1662     else if (attrName == forAttr && is<HTMLLabelElement>(*element))
1663         labelChanged(element);
1664     else if (attrName == tabindexAttr)
1665         childrenChanged(element->parentNode(), element);
1666
1667     if (!attrName.localName().string().startsWith("aria-"))
1668         return;
1669
1670     if (attrName == aria_activedescendantAttr)
1671         handleActiveDescendantChanged(element);
1672     else if (attrName == aria_busyAttr)
1673         postNotification(element, AXObjectCache::AXElementBusyChanged);
1674     else if (attrName == aria_valuenowAttr || attrName == aria_valuetextAttr)
1675         postNotification(element, AXObjectCache::AXValueChanged);
1676     else if (attrName == aria_labelAttr || attrName == aria_labeledbyAttr || attrName == aria_labelledbyAttr)
1677         textChanged(element);
1678     else if (attrName == aria_checkedAttr)
1679         checkedStateChanged(element);
1680     else if (attrName == aria_selectedAttr)
1681         selectedChildrenChanged(element);
1682     else if (attrName == aria_expandedAttr)
1683         handleAriaExpandedChange(element);
1684     else if (attrName == aria_hiddenAttr)
1685         childrenChanged(element->parentNode(), element);
1686     else if (attrName == aria_invalidAttr)
1687         postNotification(element, AXObjectCache::AXInvalidStatusChanged);
1688     else if (attrName == aria_modalAttr)
1689         handleModalChange(element);
1690     else if (attrName == aria_currentAttr)
1691         postNotification(element, AXObjectCache::AXCurrentChanged);
1692     else if (attrName == aria_disabledAttr)
1693         postNotification(element, AXObjectCache::AXDisabledStateChanged);
1694     else if (attrName == aria_pressedAttr)
1695         postNotification(element, AXObjectCache::AXPressedStateChanged);
1696     else if (attrName == aria_readonlyAttr)
1697         postNotification(element, AXObjectCache::AXReadOnlyStatusChanged);
1698     else if (attrName == aria_requiredAttr)
1699         postNotification(element, AXObjectCache::AXRequiredStatusChanged);
1700     else
1701         postNotification(element, AXObjectCache::AXAriaAttributeChanged);
1702 }
1703
1704 void AXObjectCache::handleModalChange(Node* node)
1705 {
1706     if (!is<Element>(node))
1707         return;
1708
1709     if (!nodeHasRole(node, "dialog") && !nodeHasRole(node, "alertdialog"))
1710         return;
1711
1712     stopCachingComputedObjectAttributes();
1713
1714     if (!m_modalNodesInitialized)
1715         findModalNodes();
1716
1717     if (equalLettersIgnoringASCIICase(downcast<Element>(*node).attributeWithoutSynchronization(aria_modalAttr), "true")) {
1718         // Add the newly modified node to the modal nodes set, and set it to be the current valid aria modal node.
1719         // We will recompute the current valid aria modal node in modalNode() when this node is not visible.
1720         m_modalNodesSet.add(node);
1721         m_currentModalNode = node;
1722     } else {
1723         // Remove the node from the modal nodes set. There might be other visible modal nodes, so we recompute here.
1724         m_modalNodesSet.remove(node);
1725         currentModalNode();
1726     }
1727
1728     if (m_currentModalNode)
1729         focusModalNode();
1730
1731     startCachingComputedObjectAttributesUntilTreeMutates();
1732 }
1733
1734 void AXObjectCache::labelChanged(Element* element)
1735 {
1736     ASSERT(is<HTMLLabelElement>(*element));
1737     auto correspondingControl = downcast<HTMLLabelElement>(*element).control();
1738     deferTextChangedIfNeeded(correspondingControl.get());
1739 }
1740
1741 void AXObjectCache::recomputeIsIgnored(RenderObject* renderer)
1742 {
1743     if (AccessibilityObject* obj = get(renderer))
1744         obj->notifyIfIgnoredValueChanged();
1745 }
1746
1747 void AXObjectCache::startCachingComputedObjectAttributesUntilTreeMutates()
1748 {
1749     if (!m_computedObjectAttributeCache)
1750         m_computedObjectAttributeCache = makeUnique<AXComputedObjectAttributeCache>();
1751 }
1752
1753 void AXObjectCache::stopCachingComputedObjectAttributes()
1754 {
1755     m_computedObjectAttributeCache = nullptr;
1756 }
1757
1758 VisiblePosition AXObjectCache::visiblePositionForTextMarkerData(TextMarkerData& textMarkerData)
1759 {
1760     if (!isNodeInUse(textMarkerData.node))
1761         return VisiblePosition();
1762     
1763     // FIXME: Accessability should make it clear these are DOM-compliant offsets or store Position objects.
1764     VisiblePosition visiblePos = VisiblePosition(createLegacyEditingPosition(textMarkerData.node, textMarkerData.offset), textMarkerData.affinity);
1765     Position deepPos = visiblePos.deepEquivalent();
1766     if (deepPos.isNull())
1767         return VisiblePosition();
1768     
1769     RenderObject* renderer = deepPos.deprecatedNode()->renderer();
1770     if (!renderer)
1771         return VisiblePosition();
1772     
1773     AXObjectCache* cache = renderer->document().axObjectCache();
1774     if (cache && !cache->m_idsInUse.contains(textMarkerData.axID))
1775         return VisiblePosition();
1776
1777     return visiblePos;
1778 }
1779
1780 CharacterOffset AXObjectCache::characterOffsetForTextMarkerData(TextMarkerData& textMarkerData)
1781 {
1782     if (!isNodeInUse(textMarkerData.node))
1783         return CharacterOffset();
1784     
1785     if (textMarkerData.ignored)
1786         return CharacterOffset();
1787     
1788     CharacterOffset result = CharacterOffset(textMarkerData.node, textMarkerData.characterStartIndex, textMarkerData.characterOffset);
1789     // When we are at a line wrap and the VisiblePosition is upstream, it means the text marker is at the end of the previous line.
1790     // We use the previous CharacterOffset so that it will match the Range.
1791     if (textMarkerData.affinity == UPSTREAM)
1792         return previousCharacterOffset(result, false);
1793     return result;
1794 }
1795
1796 CharacterOffset AXObjectCache::traverseToOffsetInRange(RefPtr<Range>range, int offset, TraverseOption option, bool stayWithinRange)
1797 {
1798     if (!range)
1799         return CharacterOffset();
1800     
1801     bool toNodeEnd = option & TraverseOptionToNodeEnd;
1802     bool validateOffset = option & TraverseOptionValidateOffset;
1803     bool doNotEnterTextControls = option & TraverseOptionDoNotEnterTextControls;
1804     
1805     int offsetInCharacter = 0;
1806     int cumulativeOffset = 0;
1807     int remaining = 0;
1808     int lastLength = 0;
1809     Node* currentNode = nullptr;
1810     bool finished = false;
1811     int lastStartOffset = 0;
1812     
1813     TextIterator iterator(*range, doNotEnterTextControls ? TextIteratorDefaultBehavior : TextIteratorEntersTextControls);
1814     
1815     // When the range has zero length, there might be replaced node or brTag that we need to increment the characterOffset.
1816     if (iterator.atEnd()) {
1817         currentNode = &range->startContainer();
1818         lastStartOffset = range->startOffset();
1819         if (offset > 0 || toNodeEnd) {
1820             if (AccessibilityObject::replacedNodeNeedsCharacter(currentNode) || (currentNode->renderer() && currentNode->renderer()->isBR()))
1821                 cumulativeOffset++;
1822             lastLength = cumulativeOffset;
1823             
1824             // When going backwards, stayWithinRange is false.
1825             // Here when we don't have any character to move and we are going backwards, we traverse to the previous node.
1826             if (!lastLength && toNodeEnd && !stayWithinRange) {
1827                 if (Node* preNode = previousNode(currentNode))
1828                     return traverseToOffsetInRange(rangeForNodeContents(preNode), offset, option);
1829                 return CharacterOffset();
1830             }
1831         }
1832     }
1833     
1834     // Sometimes text contents in a node are split into several iterations, so that iterator.range().startOffset()
1835     // might not be the total character count. Here we use a previousNode object to keep track of that.
1836     Node* previousNode = nullptr;
1837     for (; !iterator.atEnd(); iterator.advance()) {
1838         int currentLength = iterator.text().length();
1839         bool hasReplacedNodeOrBR = false;
1840
1841         Node& node = iterator.range().start.container;
1842         currentNode = &node;
1843         
1844         // When currentLength == 0, we check if there's any replaced node.
1845         // If not, we skip the node with no length.
1846         if (!currentLength) {
1847             Node* childNode = iterator.node();
1848             if (AccessibilityObject::replacedNodeNeedsCharacter(childNode)) {
1849                 cumulativeOffset++;
1850                 currentLength++;
1851                 currentNode = childNode;
1852                 hasReplacedNodeOrBR = true;
1853             } else
1854                 continue;
1855         } else {
1856             // Ignore space, new line, tag node.
1857             if (currentLength == 1) {
1858                 if (isHTMLSpace(iterator.text()[0])) {
1859                     // If the node has BR tag, we want to set the currentNode to it.
1860                     Node* childNode = iterator.node();
1861                     if (childNode && childNode->renderer() && childNode->renderer()->isBR()) {
1862                         currentNode = childNode;
1863                         hasReplacedNodeOrBR = true;
1864                     } else if (auto* shadowHost = currentNode->shadowHost()) {
1865                         // Since we are entering text controls, we should set the currentNode
1866                         // to be the shadow host when there's no content.
1867                         if (nodeIsTextControl(shadowHost) && currentNode->isShadowRoot()) {
1868                             currentNode = shadowHost;
1869                             continue;
1870                         }
1871                     } else if (previousNode && previousNode->isTextNode() && previousNode->isDescendantOf(currentNode) && currentNode->hasTagName(pTag)) {
1872                         // TextIterator is emitting an extra newline after the <p> element. We should
1873                         // ignore that since the extra text node is not in the DOM tree.
1874                         currentNode = previousNode;
1875                         continue;
1876                     } else if (currentNode != previousNode) {
1877                         // We should set the start offset and length for the current node in case this is the last iteration.
1878                         lastStartOffset = 1;
1879                         lastLength = 0;
1880                         continue;
1881                     }
1882                 }
1883             }
1884             cumulativeOffset += currentLength;
1885         }
1886
1887         if (currentNode == previousNode) {
1888             lastLength += currentLength;
1889             lastStartOffset = iterator.range().end.offset - lastLength;
1890         } else {
1891             lastLength = currentLength;
1892             lastStartOffset = hasReplacedNodeOrBR ? 0 : iterator.range().start.offset;
1893         }
1894         
1895         // Break early if we have advanced enough characters.
1896         bool offsetLimitReached = validateOffset ? cumulativeOffset + lastStartOffset >= offset : cumulativeOffset >= offset;
1897         if (!toNodeEnd && offsetLimitReached) {
1898             offsetInCharacter = validateOffset ? std::max(offset - lastStartOffset, 0) : offset - (cumulativeOffset - lastLength);
1899             finished = true;
1900             break;
1901         }
1902         previousNode = currentNode;
1903     }
1904     
1905     if (!finished) {
1906         offsetInCharacter = lastLength;
1907         if (!toNodeEnd)
1908             remaining = offset - cumulativeOffset;
1909     }
1910     
1911     // Sometimes when we are getting the end CharacterOffset of a line range, the TextIterator will emit an extra space at the end
1912     // and make the character count greater than the Range's end offset.
1913     if (toNodeEnd && currentNode->isTextNode() && currentNode == &range->endContainer() && static_cast<int>(range->endOffset()) < lastStartOffset + offsetInCharacter)
1914         offsetInCharacter = range->endOffset() - lastStartOffset;
1915     
1916     return CharacterOffset(currentNode, lastStartOffset, offsetInCharacter, remaining);
1917 }
1918
1919 int AXObjectCache::lengthForRange(Range* range)
1920 {
1921     if (!range)
1922         return -1;
1923     int length = 0;
1924     for (TextIterator it(*range); !it.atEnd(); it.advance()) {
1925         // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)
1926         if (it.text().length())
1927             length += it.text().length();
1928         else {
1929             // locate the node and starting offset for this replaced range
1930             if (AccessibilityObject::replacedNodeNeedsCharacter(it.node()))
1931                 ++length;
1932         }
1933     }
1934     return length;
1935 }
1936
1937 RefPtr<Range> AXObjectCache::rangeForNodeContents(Node* node)
1938 {
1939     if (!node)
1940         return nullptr;
1941     Document* document = &node->document();
1942     if (!document)
1943         return nullptr;
1944     auto range = Range::create(*document);
1945     if (AccessibilityObject::replacedNodeNeedsCharacter(node)) {
1946         // For replaced nodes without children, the node itself is included in the range.
1947         if (range->selectNode(*node).hasException())
1948             return nullptr;
1949     } else {
1950         if (range->selectNodeContents(*node).hasException())
1951             return nullptr;
1952     }
1953     return range;
1954 }
1955     
1956 Optional<SimpleRange> AXObjectCache::rangeMatchesTextNearRange(const SimpleRange& originalRange, const String& matchText)
1957 {
1958     // Create a large enough range for searching the text within.
1959     unsigned textLength = matchText.length();
1960     auto startPosition = visiblePositionForPositionWithOffset(createLegacyEditingPosition(originalRange.start), -textLength);
1961     auto endPosition = visiblePositionForPositionWithOffset(createLegacyEditingPosition(originalRange.start), 2 * textLength);
1962     if (startPosition.isNull())
1963         startPosition = firstPositionInOrBeforeNode(originalRange.start.container.ptr());
1964     if (endPosition.isNull())
1965         endPosition = lastPositionInOrAfterNode(originalRange.end.container.ptr());
1966
1967     auto searchRange = SimpleRange { *makeBoundaryPoint(startPosition), *makeBoundaryPoint(endPosition) };
1968     if (searchRange.collapsed())
1969         return WTF::nullopt;
1970
1971     auto targetOffset = characterCount({ searchRange.start, originalRange.start }, TextIteratorEmitsCharactersBetweenAllVisiblePositions);
1972     return findClosestPlainText(searchRange, matchText, { }, targetOffset);
1973 }
1974
1975 static bool isReplacedNodeOrBR(Node* node)
1976 {
1977     return node && (AccessibilityObject::replacedNodeNeedsCharacter(node) || node->hasTagName(brTag));
1978 }
1979
1980 static bool characterOffsetsInOrder(const CharacterOffset& characterOffset1, const CharacterOffset& characterOffset2)
1981 {
1982     if (characterOffset1.isNull() || characterOffset2.isNull())
1983         return false;
1984     
1985     if (characterOffset1.node == characterOffset2.node)
1986         return characterOffset1.offset <= characterOffset2.offset;
1987     
1988     Node* node1 = characterOffset1.node;
1989     Node* node2 = characterOffset2.node;
1990     if (!node1->isCharacterDataNode() && !isReplacedNodeOrBR(node1) && node1->hasChildNodes())
1991         node1 = node1->traverseToChildAt(characterOffset1.offset);
1992     if (!node2->isCharacterDataNode() && !isReplacedNodeOrBR(node2) && node2->hasChildNodes())
1993         node2 = node2->traverseToChildAt(characterOffset2.offset);
1994     
1995     if (!node1 || !node2)
1996         return false;
1997     
1998     RefPtr<Range> range1 = AXObjectCache::rangeForNodeContents(node1);
1999     RefPtr<Range> range2 = AXObjectCache::rangeForNodeContents(node2);
2000
2001     if (!range2)
2002         return true;
2003     if (!range1)
2004         return false;
2005     auto result = range1->compareBoundaryPoints(Range::START_TO_START, *range2);
2006     if (result.hasException())
2007         return true;
2008     return result.releaseReturnValue() <= 0;
2009 }
2010
2011 static Node* resetNodeAndOffsetForReplacedNode(Node* replacedNode, int& offset, int characterCount)
2012 {
2013     // Use this function to include the replaced node itself in the range we are creating.
2014     auto nodeRange = AXObjectCache::rangeForNodeContents(replacedNode);
2015     if (!nodeRange)
2016         return nullptr;
2017     bool isInNode = static_cast<unsigned>(characterCount) <= WebCore::characterCount(*nodeRange);
2018     offset = replacedNode->computeNodeIndex() + (isInNode ? 0 : 1);
2019     return replacedNode->parentNode();
2020 }
2021
2022 static bool setRangeStartOrEndWithCharacterOffset(Range& range, const CharacterOffset& characterOffset, bool isStart)
2023 {
2024     if (characterOffset.isNull())
2025         return false;
2026     
2027     int offset = characterOffset.startIndex + characterOffset.offset;
2028     Node* node = characterOffset.node;
2029     ASSERT(node);
2030     
2031     bool replacedNodeOrBR = isReplacedNodeOrBR(node);
2032     // For the non text node that has no children, we should create the range with its parent, otherwise the range would be collapsed.
2033     // Example: <div contenteditable="true"></div>, we want the range to include the div element.
2034     bool noChildren = !replacedNodeOrBR && !node->isTextNode() && !node->hasChildNodes();
2035     int characterCount = noChildren ? (isStart ? 0 : 1) : characterOffset.offset;
2036     
2037     if (replacedNodeOrBR || noChildren)
2038         node = resetNodeAndOffsetForReplacedNode(node, offset, characterCount);
2039     
2040     if (!node)
2041         return false;
2042
2043     if (isStart) {
2044         if (range.setStart(*node, offset).hasException())
2045             return false;
2046     } else {
2047         if (range.setEnd(*node, offset).hasException())
2048             return false;
2049     }
2050
2051     return true;
2052 }
2053
2054 RefPtr<Range> AXObjectCache::rangeForUnorderedCharacterOffsets(const CharacterOffset& characterOffset1, const CharacterOffset& characterOffset2)
2055 {
2056     if (characterOffset1.isNull() || characterOffset2.isNull())
2057         return nullptr;
2058     
2059     bool alreadyInOrder = characterOffsetsInOrder(characterOffset1, characterOffset2);
2060     CharacterOffset startCharacterOffset = alreadyInOrder ? characterOffset1 : characterOffset2;
2061     CharacterOffset endCharacterOffset = alreadyInOrder ? characterOffset2 : characterOffset1;
2062     
2063     auto result = Range::create(m_document);
2064     if (!setRangeStartOrEndWithCharacterOffset(result, startCharacterOffset, true))
2065         return nullptr;
2066     if (!setRangeStartOrEndWithCharacterOffset(result, endCharacterOffset, false))
2067         return nullptr;
2068     return result;
2069 }
2070
2071 void AXObjectCache::setTextMarkerDataWithCharacterOffset(TextMarkerData& textMarkerData, const CharacterOffset& characterOffset)
2072 {
2073     if (characterOffset.isNull())
2074         return;
2075     
2076     Node* domNode = characterOffset.node;
2077     if (is<HTMLInputElement>(*domNode) && downcast<HTMLInputElement>(*domNode).isPasswordField()) {
2078         textMarkerData.ignored = true;
2079         return;
2080     }
2081     
2082     RefPtr<AccessibilityObject> obj = this->getOrCreate(domNode);
2083     if (!obj)
2084         return;
2085     
2086     // Convert to visible position.
2087     VisiblePosition visiblePosition = visiblePositionFromCharacterOffset(characterOffset);
2088     int vpOffset = 0;
2089     if (!visiblePosition.isNull()) {
2090         Position deepPos = visiblePosition.deepEquivalent();
2091         vpOffset = deepPos.deprecatedEditingOffset();
2092     }
2093     
2094     textMarkerData.axID = obj.get()->objectID();
2095     textMarkerData.node = domNode;
2096     textMarkerData.characterOffset = characterOffset.offset;
2097     textMarkerData.characterStartIndex = characterOffset.startIndex;
2098     textMarkerData.offset = vpOffset;
2099     textMarkerData.affinity = visiblePosition.affinity();
2100     
2101     this->setNodeInUse(domNode);
2102 }
2103
2104 CharacterOffset AXObjectCache::startOrEndCharacterOffsetForRange(RefPtr<Range> range, bool isStart, bool enterTextControls)
2105 {
2106     if (!range)
2107         return CharacterOffset();
2108     
2109     // When getting the end CharacterOffset at node boundary, we don't want to collapse to the previous node.
2110     if (!isStart && !range->endOffset())
2111         return characterOffsetForNodeAndOffset(range->endContainer(), 0, TraverseOptionIncludeStart);
2112     
2113     // If it's end text marker, we want to go to the end of the range, and stay within the range.
2114     bool stayWithinRange = !isStart;
2115     
2116     Node& endNode = range->endContainer();
2117     if (endNode.isCharacterDataNode() && !isStart)
2118         return traverseToOffsetInRange(rangeForNodeContents(&endNode), range->endOffset(), TraverseOptionValidateOffset);
2119     
2120     Ref<Range> copyRange = *range;
2121     // Change the start of the range, so the character offset starts from node beginning.
2122     int offset = 0;
2123     Node& node = copyRange->startContainer();
2124     if (node.isCharacterDataNode()) {
2125         CharacterOffset nodeStartOffset = traverseToOffsetInRange(rangeForNodeContents(&node), range->startOffset(), TraverseOptionValidateOffset);
2126         if (isStart)
2127             return nodeStartOffset;
2128         copyRange = Range::create(range->ownerDocument(), &range->startContainer(), 0, &range->endContainer(), range->endOffset());
2129         offset += nodeStartOffset.offset;
2130     }
2131     
2132     TraverseOption options = isStart ? TraverseOptionDefault : TraverseOptionToNodeEnd;
2133     if (!enterTextControls)
2134         options = static_cast<TraverseOption>(options | TraverseOptionDoNotEnterTextControls);
2135     return traverseToOffsetInRange(WTFMove(copyRange), offset, options, stayWithinRange);
2136 }
2137
2138 void AXObjectCache::startOrEndTextMarkerDataForRange(TextMarkerData& textMarkerData, RefPtr<Range> range, bool isStart)
2139 {
2140     // This memory must be zero'd so instances of TextMarkerData can be tested for byte-equivalence.
2141     // Warning: This is risky and bad because TextMarkerData is a nontrivial type.
2142     memset(static_cast<void*>(&textMarkerData), 0, sizeof(TextMarkerData));
2143     
2144     CharacterOffset characterOffset = startOrEndCharacterOffsetForRange(range, isStart);
2145     if (characterOffset.isNull())
2146         return;
2147     
2148     setTextMarkerDataWithCharacterOffset(textMarkerData, characterOffset);
2149 }
2150
2151 CharacterOffset AXObjectCache::characterOffsetForNodeAndOffset(Node& node, int offset, TraverseOption option)
2152 {
2153     Node* domNode = &node;
2154     if (!domNode)
2155         return CharacterOffset();
2156     
2157     bool toNodeEnd = option & TraverseOptionToNodeEnd;
2158     bool includeStart = option & TraverseOptionIncludeStart;
2159     
2160     // ignoreStart is used to determine if we should go to previous node or
2161     // stay in current node when offset is 0.
2162     if (!toNodeEnd && (offset < 0 || (!offset && !includeStart))) {
2163         // Set the offset to the amount of characters we need to go backwards.
2164         offset = - offset;
2165         CharacterOffset charOffset = CharacterOffset();
2166         while (offset >= 0 && charOffset.offset <= offset) {
2167             offset -= charOffset.offset;
2168             domNode = previousNode(domNode);
2169             if (domNode) {
2170                 charOffset = characterOffsetForNodeAndOffset(*domNode, 0, TraverseOptionToNodeEnd);
2171             } else
2172                 return CharacterOffset();
2173             if (charOffset.offset == offset)
2174                 break;
2175         }
2176         if (offset > 0)
2177             charOffset = characterOffsetForNodeAndOffset(*charOffset.node, charOffset.offset - offset, TraverseOptionIncludeStart);
2178         return charOffset;
2179     }
2180     
2181     RefPtr<Range> range = rangeForNodeContents(domNode);
2182
2183     // Traverse the offset amount of characters forward and see if there's remaining offsets.
2184     // Keep traversing to the next node when there's remaining offsets.
2185     CharacterOffset characterOffset = traverseToOffsetInRange(range, offset, option);
2186     while (!characterOffset.isNull() && characterOffset.remaining() && !toNodeEnd) {
2187         domNode = nextNode(domNode);
2188         if (!domNode)
2189             return CharacterOffset();
2190         range = rangeForNodeContents(domNode);
2191         characterOffset = traverseToOffsetInRange(range, characterOffset.remaining(), option);
2192     }
2193     
2194     return characterOffset;
2195 }
2196
2197 void AXObjectCache::textMarkerDataForCharacterOffset(TextMarkerData& textMarkerData, const CharacterOffset& characterOffset)
2198 {
2199     // This memory must be zero'd so instances of TextMarkerData can be tested for byte-equivalence.
2200     // Warning: This is risky and bad because TextMarkerData is a nontrivial type.
2201     memset(static_cast<void*>(&textMarkerData), 0, sizeof(TextMarkerData));
2202
2203     setTextMarkerDataWithCharacterOffset(textMarkerData, characterOffset);
2204 }
2205
2206 bool AXObjectCache::shouldSkipBoundary(const CharacterOffset& previous, const CharacterOffset& next)
2207 {
2208     // Match the behavior of VisiblePosition, we should skip the node boundary when there's no visual space or new line character.
2209     if (previous.isNull() || next.isNull())
2210         return false;
2211     
2212     if (previous.node == next.node)
2213         return false;
2214     
2215     if (next.startIndex > 0 || next.offset > 0)
2216         return false;
2217     
2218     CharacterOffset newLine = startCharacterOffsetOfLine(next);
2219     if (next.isEqual(newLine))
2220         return false;
2221     
2222     return true;
2223 }
2224     
2225 void AXObjectCache::textMarkerDataForNextCharacterOffset(TextMarkerData& textMarkerData, const CharacterOffset& characterOffset)
2226 {
2227     CharacterOffset next = characterOffset;
2228     CharacterOffset previous = characterOffset;
2229     bool shouldContinue;
2230     do {
2231         shouldContinue = false;
2232         next = nextCharacterOffset(next, false);
2233         if (shouldSkipBoundary(previous, next))
2234             next = nextCharacterOffset(next, false);
2235         textMarkerDataForCharacterOffset(textMarkerData, next);
2236         
2237         // We should skip next CharactetOffset if it's visually the same.
2238         if (!lengthForRange(rangeForUnorderedCharacterOffsets(previous, next).get()))
2239             shouldContinue = true;
2240         previous = next;
2241     } while (textMarkerData.ignored || shouldContinue);
2242 }
2243
2244 void AXObjectCache::textMarkerDataForPreviousCharacterOffset(TextMarkerData& textMarkerData, const CharacterOffset& characterOffset)
2245 {
2246     CharacterOffset previous = characterOffset;
2247     CharacterOffset next = characterOffset;
2248     bool shouldContinue;
2249     do {
2250         shouldContinue = false;
2251         previous = previousCharacterOffset(previous, false);
2252         textMarkerDataForCharacterOffset(textMarkerData, previous);
2253         
2254         // We should skip previous CharactetOffset if it's visually the same.
2255         if (!lengthForRange(rangeForUnorderedCharacterOffsets(previous, next).get()))
2256             shouldContinue = true;
2257         next = previous;
2258     } while (textMarkerData.ignored || shouldContinue);
2259 }
2260
2261 Node* AXObjectCache::nextNode(Node* node) const
2262 {
2263     if (!node)
2264         return nullptr;
2265     
2266     return NodeTraversal::nextSkippingChildren(*node);
2267 }
2268
2269 Node* AXObjectCache::previousNode(Node* node) const
2270 {
2271     if (!node)
2272         return nullptr;
2273     
2274     // First child of body shouldn't have previous node.
2275     if (node->parentNode() && node->parentNode()->renderer() && node->parentNode()->renderer()->isBody() && !node->previousSibling())
2276         return nullptr;
2277
2278     return NodeTraversal::previousSkippingChildren(*node);
2279 }
2280
2281 VisiblePosition AXObjectCache::visiblePositionFromCharacterOffset(const CharacterOffset& characterOffset)
2282 {
2283     if (characterOffset.isNull())
2284         return VisiblePosition();
2285     
2286     // Create a collapsed range and use that to form a VisiblePosition, so that the case with
2287     // composed characters will be covered.
2288     auto range = rangeForUnorderedCharacterOffsets(characterOffset, characterOffset);
2289     return range ? VisiblePosition(range->startPosition()) : VisiblePosition();
2290 }
2291
2292 CharacterOffset AXObjectCache::characterOffsetFromVisiblePosition(const VisiblePosition& visiblePos)
2293 {
2294     if (visiblePos.isNull())
2295         return CharacterOffset();
2296     
2297     Position deepPos = visiblePos.deepEquivalent();
2298     Node* domNode = deepPos.deprecatedNode();
2299     ASSERT(domNode);
2300     
2301     if (domNode->isCharacterDataNode())
2302         return traverseToOffsetInRange(rangeForNodeContents(domNode), deepPos.deprecatedEditingOffset(), TraverseOptionValidateOffset);
2303     
2304     RefPtr<AccessibilityObject> obj = this->getOrCreate(domNode);
2305     if (!obj)
2306         return CharacterOffset();
2307     
2308     // Use nextVisiblePosition to calculate how many characters we need to traverse to the current position.
2309     VisiblePositionRange visiblePositionRange = obj->visiblePositionRange();
2310     VisiblePosition visiblePosition = visiblePositionRange.start;
2311     int characterOffset = 0;
2312     Position currentPosition = visiblePosition.deepEquivalent();
2313     
2314     VisiblePosition previousVisiblePos;
2315     while (!currentPosition.isNull() && !deepPos.equals(currentPosition)) {
2316         previousVisiblePos = visiblePosition;
2317         visiblePosition = obj->nextVisiblePosition(visiblePosition);
2318         currentPosition = visiblePosition.deepEquivalent();
2319         Position previousPosition = previousVisiblePos.deepEquivalent();
2320         // Sometimes nextVisiblePosition will give the same VisiblePostion,
2321         // we break here to avoid infinite loop.
2322         if (currentPosition.equals(previousPosition))
2323             break;
2324         characterOffset++;
2325         
2326         // When VisiblePostion moves to next node, it will count the leading line break as
2327         // 1 offset, which we shouldn't include in CharacterOffset.
2328         if (currentPosition.deprecatedNode() != previousPosition.deprecatedNode()) {
2329             if (visiblePosition.characterBefore() == '\n')
2330                 characterOffset--;
2331         } else {
2332             // Sometimes VisiblePosition will move multiple characters, like emoji.
2333             if (currentPosition.deprecatedNode()->isCharacterDataNode())
2334                 characterOffset += currentPosition.offsetInContainerNode() - previousPosition.offsetInContainerNode() - 1;
2335         }
2336     }
2337     
2338     // Sometimes when the node is a replaced node and is ignored in accessibility, we get a wrong CharacterOffset from it.
2339     CharacterOffset result = traverseToOffsetInRange(rangeForNodeContents(obj->node()), characterOffset);
2340     if (result.remainingOffset > 0 && !result.isNull() && isRendererReplacedElement(result.node->renderer()))
2341         result.offset += result.remainingOffset;
2342     return result;
2343 }
2344
2345 AccessibilityObject* AXObjectCache::accessibilityObjectForTextMarkerData(TextMarkerData& textMarkerData)
2346 {
2347     if (!isNodeInUse(textMarkerData.node))
2348         return nullptr;
2349     
2350     Node* domNode = textMarkerData.node;
2351     return this->getOrCreate(domNode);
2352 }
2353
2354 Optional<TextMarkerData> AXObjectCache::textMarkerDataForVisiblePosition(const VisiblePosition& visiblePos)
2355 {
2356     if (visiblePos.isNull())
2357         return WTF::nullopt;
2358
2359     Position deepPos = visiblePos.deepEquivalent();
2360     Node* domNode = deepPos.deprecatedNode();
2361     ASSERT(domNode);
2362     if (!domNode)
2363         return WTF::nullopt;
2364
2365     if (is<HTMLInputElement>(*domNode) && downcast<HTMLInputElement>(*domNode).isPasswordField())
2366         return WTF::nullopt;
2367
2368     // If the visible position has an anchor type referring to a node other than the anchored node, we should
2369     // set the text marker data with CharacterOffset so that the offset will correspond to the node.
2370     CharacterOffset characterOffset = characterOffsetFromVisiblePosition(visiblePos);
2371     if (deepPos.anchorType() == Position::PositionIsAfterAnchor || deepPos.anchorType() == Position::PositionIsAfterChildren) {
2372         TextMarkerData textMarkerData;
2373         textMarkerDataForCharacterOffset(textMarkerData, characterOffset);
2374         return textMarkerData;
2375     }
2376
2377     // find or create an accessibility object for this node
2378     AXObjectCache* cache = domNode->document().axObjectCache();
2379     if (!cache)
2380         return WTF::nullopt;
2381     RefPtr<AccessibilityObject> obj = cache->getOrCreate(domNode);
2382
2383     // This memory must be zero'd so instances of TextMarkerData can be tested for byte-equivalence.
2384     // Warning: This is risky and bad because TextMarkerData is a nontrivial type.
2385     TextMarkerData textMarkerData;
2386     memset(static_cast<void*>(&textMarkerData), 0, sizeof(TextMarkerData));
2387     
2388     textMarkerData.axID = obj.get()->objectID();
2389     textMarkerData.node = domNode;
2390     textMarkerData.offset = deepPos.deprecatedEditingOffset();
2391     textMarkerData.affinity = visiblePos.affinity();
2392
2393     textMarkerData.characterOffset = characterOffset.offset;
2394     textMarkerData.characterStartIndex = characterOffset.startIndex;
2395
2396     cache->setNodeInUse(domNode);
2397
2398     return textMarkerData;
2399 }
2400
2401 // This function exits as a performance optimization to avoid a synchronous layout.
2402 Optional<TextMarkerData> AXObjectCache::textMarkerDataForFirstPositionInTextControl(HTMLTextFormControlElement& textControl)
2403 {
2404     if (is<HTMLInputElement>(textControl) && downcast<HTMLInputElement>(textControl).isPasswordField())
2405         return WTF::nullopt;
2406
2407     AXObjectCache* cache = textControl.document().axObjectCache();
2408     if (!cache)
2409         return WTF::nullopt;
2410
2411     RefPtr<AccessibilityObject> obj = cache->getOrCreate(&textControl);
2412     if (!obj)
2413         return WTF::nullopt;
2414
2415     // This memory must be zero'd so instances of TextMarkerData can be tested for byte-equivalence.
2416     // Warning: This is risky and bad because TextMarkerData is a nontrivial type.
2417     TextMarkerData textMarkerData;
2418     memset(static_cast<void*>(&textMarkerData), 0, sizeof(TextMarkerData));
2419     
2420     textMarkerData.axID = obj.get()->objectID();
2421     textMarkerData.node = &textControl;
2422
2423     cache->setNodeInUse(&textControl);
2424
2425     return textMarkerData;
2426 }
2427
2428 CharacterOffset AXObjectCache::nextCharacterOffset(const CharacterOffset& characterOffset, bool ignoreNextNodeStart)
2429 {
2430     if (characterOffset.isNull())
2431         return CharacterOffset();
2432     
2433     // We don't always move one 'character' at a time since there might be composed characters.
2434     unsigned nextOffset = Position::uncheckedNextOffset(characterOffset.node, characterOffset.offset);
2435     CharacterOffset next = characterOffsetForNodeAndOffset(*characterOffset.node, nextOffset);
2436     
2437     // To be consistent with VisiblePosition, we should consider the case that current node end to next node start counts 1 offset.
2438     if (!ignoreNextNodeStart && !next.isNull() && !isReplacedNodeOrBR(next.node) && next.node != characterOffset.node) {
2439         if (auto range = rangeForUnorderedCharacterOffsets(characterOffset, next)) {
2440             auto length = characterCount(*range);
2441             if (length > nextOffset - characterOffset.offset)
2442                 next = characterOffsetForNodeAndOffset(*next.node, 0, TraverseOptionIncludeStart);
2443         }
2444     }
2445     
2446     return next;
2447 }
2448
2449 CharacterOffset AXObjectCache::previousCharacterOffset(const CharacterOffset& characterOffset, bool ignorePreviousNodeEnd)
2450 {
2451     if (characterOffset.isNull())
2452         return CharacterOffset();
2453     
2454     // To be consistent with VisiblePosition, we should consider the case that current node start to previous node end counts 1 offset.
2455     if (!ignorePreviousNodeEnd && !characterOffset.offset)
2456         return characterOffsetForNodeAndOffset(*characterOffset.node, 0);
2457     
2458     // We don't always move one 'character' a time since there might be composed characters.
2459     int previousOffset = Position::uncheckedPreviousOffset(characterOffset.node, characterOffset.offset);
2460     return characterOffsetForNodeAndOffset(*characterOffset.node, previousOffset, TraverseOptionIncludeStart);
2461 }
2462
2463 CharacterOffset AXObjectCache::startCharacterOffsetOfWord(const CharacterOffset& characterOffset, EWordSide side)
2464 {
2465     if (characterOffset.isNull())
2466         return CharacterOffset();
2467     
2468     CharacterOffset c = characterOffset;
2469     if (side == RightWordIfOnBoundary) {
2470         CharacterOffset endOfParagraph = endCharacterOffsetOfParagraph(c);
2471         if (c.isEqual(endOfParagraph))
2472             return c;
2473         
2474         // We should consider the node boundary that splits words. Otherwise VoiceOver won't see it as space.
2475         c = nextCharacterOffset(characterOffset, false);
2476         if (shouldSkipBoundary(characterOffset, c))
2477             c = nextCharacterOffset(c, false);
2478         if (c.isNull())
2479             return characterOffset;
2480     }
2481     
2482     return previousBoundary(c, startWordBoundary);
2483 }
2484
2485 CharacterOffset AXObjectCache::endCharacterOffsetOfWord(const CharacterOffset& characterOffset, EWordSide side)
2486 {
2487     if (characterOffset.isNull())
2488         return CharacterOffset();
2489     
2490     CharacterOffset c = characterOffset;
2491     if (side == LeftWordIfOnBoundary) {
2492         CharacterOffset startOfParagraph = startCharacterOffsetOfParagraph(c);
2493         if (c.isEqual(startOfParagraph))
2494             return c;
2495         
2496         c = previousCharacterOffset(characterOffset);
2497         if (c.isNull())
2498             return characterOffset;
2499     } else {
2500         CharacterOffset endOfParagraph = endCharacterOffsetOfParagraph(characterOffset);
2501         if (characterOffset.isEqual(endOfParagraph))
2502             return characterOffset;
2503     }
2504     
2505     return nextBoundary(c, endWordBoundary);
2506 }
2507
2508 CharacterOffset AXObjectCache::previousWordStartCharacterOffset(const CharacterOffset& characterOffset)
2509 {
2510     if (characterOffset.isNull())
2511         return CharacterOffset();
2512     
2513     CharacterOffset previousOffset = previousCharacterOffset(characterOffset);
2514     if (previousOffset.isNull())
2515         return CharacterOffset();
2516     
2517     return startCharacterOffsetOfWord(previousOffset, RightWordIfOnBoundary);
2518 }
2519
2520 CharacterOffset AXObjectCache::nextWordEndCharacterOffset(const CharacterOffset& characterOffset)
2521 {
2522     if (characterOffset.isNull())
2523         return CharacterOffset();
2524     
2525     CharacterOffset nextOffset = nextCharacterOffset(characterOffset);
2526     if (nextOffset.isNull())
2527         return CharacterOffset();
2528     
2529     return endCharacterOffsetOfWord(nextOffset, LeftWordIfOnBoundary);
2530 }
2531
2532 RefPtr<Range> AXObjectCache::leftWordRange(const CharacterOffset& characterOffset)
2533 {
2534     CharacterOffset start = startCharacterOffsetOfWord(characterOffset, LeftWordIfOnBoundary);
2535     CharacterOffset end = endCharacterOffsetOfWord(start);
2536     return rangeForUnorderedCharacterOffsets(start, end);
2537 }
2538
2539 RefPtr<Range> AXObjectCache::rightWordRange(const CharacterOffset& characterOffset)
2540 {
2541     CharacterOffset start = startCharacterOffsetOfWord(characterOffset, RightWordIfOnBoundary);
2542     CharacterOffset end = endCharacterOffsetOfWord(start);
2543     return rangeForUnorderedCharacterOffsets(start, end);
2544 }
2545
2546 static UChar32 characterForCharacterOffset(const CharacterOffset& characterOffset)
2547 {
2548     if (characterOffset.isNull() || !characterOffset.node->isTextNode())
2549         return 0;
2550     
2551     UChar32 ch = 0;
2552     unsigned offset = characterOffset.startIndex + characterOffset.offset;
2553     if (offset < characterOffset.node->textContent().length()) {
2554 // FIXME: Remove IGNORE_CLANG_WARNINGS macros once one of <rdar://problem/58615489&58615391> is fixed.
2555 IGNORE_CLANG_WARNINGS_BEGIN("conditional-uninitialized")
2556         U16_NEXT(characterOffset.node->textContent(), offset, characterOffset.node->textContent().length(), ch);
2557 IGNORE_CLANG_WARNINGS_END
2558     }
2559     return ch;
2560 }
2561
2562 UChar32 AXObjectCache::characterAfter(const CharacterOffset& characterOffset)
2563 {
2564     return characterForCharacterOffset(nextCharacterOffset(characterOffset));
2565 }
2566
2567 UChar32 AXObjectCache::characterBefore(const CharacterOffset& characterOffset)
2568 {
2569     return characterForCharacterOffset(characterOffset);
2570 }
2571
2572 static bool characterOffsetNodeIsBR(const CharacterOffset& characterOffset)
2573 {
2574     if (characterOffset.isNull())
2575         return false;
2576     
2577     return characterOffset.node->hasTagName(brTag);
2578 }
2579     
2580 static Node* parentEditingBoundary(Node* node)
2581 {
2582     if (!node)
2583         return nullptr;
2584     
2585     Node* documentElement = node->document().documentElement();
2586     if (!documentElement)
2587         return nullptr;
2588     
2589     Node* boundary = node;
2590     while (boundary != documentElement && boundary->nonShadowBoundaryParentNode() && node->hasEditableStyle() == boundary->parentNode()->hasEditableStyle())
2591         boundary = boundary->nonShadowBoundaryParentNode();
2592     
2593     return boundary;
2594 }
2595
2596 CharacterOffset AXObjectCache::nextBoundary(const CharacterOffset& characterOffset, BoundarySearchFunction searchFunction)
2597 {
2598     if (characterOffset.isNull())
2599         return { };
2600
2601     Node* boundary = parentEditingBoundary(characterOffset.node);
2602     if (!boundary)
2603         return { };
2604
2605     RefPtr<Range> searchRange = rangeForNodeContents(boundary);
2606     if (!searchRange)
2607         return { };
2608
2609     Vector<UChar, 1024> string;
2610     unsigned prefixLength = 0;
2611     
2612     if (requiresContextForWordBoundary(characterAfter(characterOffset))) {
2613         auto backwardsScanRange = boundary->document().createRange();
2614         if (!setRangeStartOrEndWithCharacterOffset(backwardsScanRange, characterOffset, false))
2615             return { };
2616         prefixLength = prefixLengthForRange(backwardsScanRange, string);
2617     }
2618     
2619     if (!setRangeStartOrEndWithCharacterOffset(*searchRange, characterOffset, true))
2620         return { };
2621     CharacterOffset end = startOrEndCharacterOffsetForRange(searchRange, false);
2622     
2623     TextIterator it(*searchRange, TextIteratorEmitsObjectReplacementCharacters);
2624     unsigned next = forwardSearchForBoundaryWithTextIterator(it, string, prefixLength, searchFunction);
2625     
2626     if (it.atEnd() && next == string.size())
2627         return end;
2628     
2629     // We should consider the node boundary that splits words.
2630     if (searchFunction == endWordBoundary && next - prefixLength == 1)
2631         return nextCharacterOffset(characterOffset, false);
2632     
2633     // The endSentenceBoundary function will include a line break at the end of the sentence.
2634     if (searchFunction == endSentenceBoundary && string[next - 1] == '\n')
2635         next--;
2636     
2637     if (next > prefixLength)
2638         return characterOffsetForNodeAndOffset(*characterOffset.node, characterOffset.offset + next - prefixLength);
2639     
2640     return characterOffset;
2641 }
2642
2643 // FIXME: Share code with the one in VisibleUnits.cpp.
2644 CharacterOffset AXObjectCache::previousBoundary(const CharacterOffset& characterOffset, BoundarySearchFunction searchFunction, NeedsContextAtParagraphStart needsContextAtParagraphStart)
2645 {
2646     if (characterOffset.isNull())
2647         return CharacterOffset();
2648     
2649     Node* boundary = parentEditingBoundary(characterOffset.node);
2650     if (!boundary)
2651         return CharacterOffset();
2652     
2653     RefPtr<Range> searchRange = rangeForNodeContents(boundary);
2654     Vector<UChar, 1024> string;
2655     unsigned suffixLength = 0;
2656
2657     if (needsContextAtParagraphStart == NeedsContextAtParagraphStart::Yes && startCharacterOffsetOfParagraph(characterOffset).isEqual(characterOffset)) {
2658         auto forwardsScanRange = boundary->document().createRange();
2659         auto endOfCurrentParagraph = endCharacterOffsetOfParagraph(characterOffset);
2660         if (!setRangeStartOrEndWithCharacterOffset(forwardsScanRange, characterOffset, true))
2661             return { };
2662         if (!setRangeStartOrEndWithCharacterOffset(forwardsScanRange, endOfCurrentParagraph, false))
2663             return { };
2664         for (TextIterator forwardsIterator(forwardsScanRange); !forwardsIterator.atEnd(); forwardsIterator.advance())
2665             append(string, forwardsIterator.text());
2666         suffixLength = string.size();
2667     } else if (requiresContextForWordBoundary(characterBefore(characterOffset))) {
2668         auto forwardsScanRange = boundary->document().createRange();
2669         if (forwardsScanRange->setEndAfter(*boundary).hasException())
2670             return { };
2671         if (!setRangeStartOrEndWithCharacterOffset(forwardsScanRange, characterOffset, true))
2672             return { };
2673         suffixLength = suffixLengthForRange(forwardsScanRange, string);
2674     }
2675     
2676     if (!setRangeStartOrEndWithCharacterOffset(*searchRange, characterOffset, false))
2677         return { };
2678     CharacterOffset start = startOrEndCharacterOffsetForRange(searchRange, true);
2679     
2680     SimplifiedBackwardsTextIterator it(*searchRange);
2681     unsigned next = backwardSearchForBoundaryWithTextIterator(it, string, suffixLength, searchFunction);
2682     
2683     if (!next)
2684         return it.atEnd() ? start : characterOffset;
2685     
2686     auto& node = it.atEnd() ? searchRange->startContainer() : it.range().start.container.get();
2687
2688     // SimplifiedBackwardsTextIterator ignores replaced elements.
2689     if (AccessibilityObject::replacedNodeNeedsCharacter(characterOffset.node))
2690         return characterOffsetForNodeAndOffset(*characterOffset.node, 0);
2691     Node* nextSibling = node.nextSibling();
2692     if (&node != characterOffset.node && AccessibilityObject::replacedNodeNeedsCharacter(nextSibling))
2693         return startOrEndCharacterOffsetForRange(rangeForNodeContents(nextSibling), false);
2694
2695     if ((!suffixLength && node.isTextNode() && next <= node.length()) || (node.renderer() && node.renderer()->isBR() && !next)) {
2696         // The next variable contains a usable index into a text node
2697         if (node.isTextNode())
2698             return traverseToOffsetInRange(rangeForNodeContents(&node), next, TraverseOptionValidateOffset);
2699         return characterOffsetForNodeAndOffset(node, next, TraverseOptionIncludeStart);
2700     }
2701     
2702     int characterCount = characterOffset.offset;
2703     if (next < string.size() - suffixLength)
2704         characterCount -= string.size() - suffixLength - next;
2705     // We don't want to go to the previous node if the node is at the start of a new line.
2706     if (characterCount < 0 && (characterOffsetNodeIsBR(characterOffset) || string[string.size() - suffixLength - 1] == '\n'))
2707         characterCount = 0;
2708     return characterOffsetForNodeAndOffset(*characterOffset.node, characterCount, TraverseOptionIncludeStart);
2709 }
2710
2711 CharacterOffset AXObjectCache::startCharacterOffsetOfParagraph(const CharacterOffset& characterOffset, EditingBoundaryCrossingRule boundaryCrossingRule)
2712 {
2713     if (characterOffset.isNull())
2714         return CharacterOffset();
2715     
2716     auto* startNode = characterOffset.node;
2717     
2718     if (isRenderedAsNonInlineTableImageOrHR(startNode))
2719         return startOrEndCharacterOffsetForRange(rangeForNodeContents(startNode), true);
2720     
2721     auto* startBlock = enclosingBlock(startNode);
2722     int offset = characterOffset.startIndex + characterOffset.offset;
2723     auto* highestRoot = highestEditableRoot(firstPositionInOrBeforeNode(startNode));
2724     Position::AnchorType type = Position::PositionIsOffsetInAnchor;
2725     
2726     auto* node = findStartOfParagraph(startNode, highestRoot, startBlock, offset, type, boundaryCrossingRule);
2727     
2728     if (type == Position::PositionIsOffsetInAnchor)
2729         return characterOffsetForNodeAndOffset(*node, offset, TraverseOptionIncludeStart);
2730     
2731     return startOrEndCharacterOffsetForRange(rangeForNodeContents(node), true);
2732 }
2733
2734 CharacterOffset AXObjectCache::endCharacterOffsetOfParagraph(const CharacterOffset& characterOffset, EditingBoundaryCrossingRule boundaryCrossingRule)
2735 {
2736     if (characterOffset.isNull())
2737         return CharacterOffset();
2738     
2739     Node* startNode = characterOffset.node;
2740     if (isRenderedAsNonInlineTableImageOrHR(startNode))
2741         return startOrEndCharacterOffsetForRange(rangeForNodeContents(startNode), false);
2742     
2743     Node* stayInsideBlock = enclosingBlock(startNode);
2744     int offset = characterOffset.startIndex + characterOffset.offset;
2745     Node* highestRoot = highestEditableRoot(firstPositionInOrBeforeNode(startNode));
2746     Position::AnchorType type = Position::PositionIsOffsetInAnchor;
2747     
2748     Node* node = findEndOfParagraph(startNode, highestRoot, stayInsideBlock, offset, type, boundaryCrossingRule);
2749     if (type == Position::PositionIsOffsetInAnchor) {
2750         if (node->isTextNode()) {
2751             CharacterOffset startOffset = startOrEndCharacterOffsetForRange(rangeForNodeContents(node), true);
2752             offset -= startOffset.startIndex;
2753         }
2754         return characterOffsetForNodeAndOffset(*node, offset, TraverseOptionIncludeStart);
2755     }
2756     
2757     return startOrEndCharacterOffsetForRange(rangeForNodeContents(node), false);
2758 }
2759
2760 RefPtr<Range> AXObjectCache::paragraphForCharacterOffset(const CharacterOffset& characterOffset)
2761 {
2762     CharacterOffset start = startCharacterOffsetOfParagraph(characterOffset);
2763     CharacterOffset end = endCharacterOffsetOfParagraph(start);
2764     
2765     return rangeForUnorderedCharacterOffsets(start, end);
2766 }
2767
2768 CharacterOffset AXObjectCache::nextParagraphEndCharacterOffset(const CharacterOffset& characterOffset)
2769 {
2770     // make sure we move off of a paragraph end
2771     CharacterOffset next = nextCharacterOffset(characterOffset);
2772     
2773     // We should skip the following BR node.
2774     if (characterOffsetNodeIsBR(next) && !characterOffsetNodeIsBR(characterOffset))
2775         next = nextCharacterOffset(next);
2776     
2777     return endCharacterOffsetOfParagraph(next);
2778 }
2779
2780 CharacterOffset AXObjectCache::previousParagraphStartCharacterOffset(const CharacterOffset& characterOffset)
2781 {
2782     // make sure we move off of a paragraph start
2783     CharacterOffset previous = previousCharacterOffset(characterOffset);
2784     
2785     // We should skip the preceding BR node.
2786     if (characterOffsetNodeIsBR(previous) && !characterOffsetNodeIsBR(characterOffset))
2787         previous = previousCharacterOffset(previous);
2788     
2789     return startCharacterOffsetOfParagraph(previous);
2790 }
2791
2792 CharacterOffset AXObjectCache::startCharacterOffsetOfSentence(const CharacterOffset& characterOffset)
2793 {
2794     return previousBoundary(characterOffset, startSentenceBoundary, NeedsContextAtParagraphStart::Yes);
2795 }
2796
2797 CharacterOffset AXObjectCache::endCharacterOffsetOfSentence(const CharacterOffset& characterOffset)
2798 {
2799     return nextBoundary(characterOffset, endSentenceBoundary);
2800 }
2801
2802 RefPtr<Range> AXObjectCache::sentenceForCharacterOffset(const CharacterOffset& characterOffset)
2803 {
2804     CharacterOffset start = startCharacterOffsetOfSentence(characterOffset);
2805     CharacterOffset end = endCharacterOffsetOfSentence(start);
2806     return rangeForUnorderedCharacterOffsets(start, end);
2807 }
2808
2809 CharacterOffset AXObjectCache::nextSentenceEndCharacterOffset(const CharacterOffset& characterOffset)
2810 {
2811     // Make sure we move off of a sentence end.
2812     return endCharacterOffsetOfSentence(nextCharacterOffset(characterOffset));
2813 }
2814
2815 CharacterOffset AXObjectCache::previousSentenceStartCharacterOffset(const CharacterOffset& characterOffset)
2816 {
2817     // Make sure we move off of a sentence start.
2818     CharacterOffset previous = previousCharacterOffset(characterOffset);
2819     
2820     // We should skip the preceding BR node.
2821     if (characterOffsetNodeIsBR(previous) && !characterOffsetNodeIsBR(characterOffset))
2822         previous = previousCharacterOffset(previous);
2823     
2824     return startCharacterOffsetOfSentence(previous);
2825 }
2826
2827 LayoutRect AXObjectCache::localCaretRectForCharacterOffset(RenderObject*& renderer, const CharacterOffset& characterOffset)
2828 {
2829     if (characterOffset.isNull()) {
2830         renderer = nullptr;
2831         return IntRect();
2832     }
2833     
2834     Node* node = characterOffset.node;
2835     
2836     renderer = node->renderer();
2837     if (!renderer)
2838         return LayoutRect();
2839     
2840     InlineBox* inlineBox = nullptr;
2841     int caretOffset;
2842     // Use a collapsed range to get the position.
2843     RefPtr<Range> range = rangeForUnorderedCharacterOffsets(characterOffset, characterOffset);
2844     if (!range)
2845         return IntRect();
2846     
2847     Position startPosition = range->startPosition();
2848     startPosition.getInlineBoxAndOffset(DOWNSTREAM, inlineBox, caretOffset);
2849     
2850     if (inlineBox)
2851         renderer = &inlineBox->renderer();
2852     
2853     if (is<RenderLineBreak>(renderer) && downcast<RenderLineBreak>(renderer)->inlineBoxWrapper() != inlineBox)
2854         return IntRect();
2855     
2856     return renderer->localCaretRect(inlineBox, caretOffset);
2857 }
2858
2859 IntRect AXObjectCache::absoluteCaretBoundsForCharacterOffset(const CharacterOffset& characterOffset)
2860 {
2861     RenderBlock* caretPainter = nullptr;
2862     
2863     // First compute a rect local to the renderer at the selection start.
2864     RenderObject* renderer = nullptr;
2865     LayoutRect localRect = localCaretRectForCharacterOffset(renderer, characterOffset);
2866     
2867     localRect = localCaretRectInRendererForRect(localRect, characterOffset.node, renderer, caretPainter);
2868     return absoluteBoundsForLocalCaretRect(caretPainter, localRect);
2869 }
2870
2871 CharacterOffset AXObjectCache::characterOffsetForPoint(const IntPoint &point, AXCoreObject* obj)
2872 {
2873     if (!obj)
2874         return CharacterOffset();
2875     
2876     VisiblePosition vp = obj->visiblePositionForPoint(point);
2877     RefPtr<Range> range = makeRange(vp, vp);
2878     return startOrEndCharacterOffsetForRange(range, true);
2879 }
2880
2881 CharacterOffset AXObjectCache::characterOffsetForPoint(const IntPoint &point)
2882 {
2883     RefPtr<Range> caretRange = m_document.caretRangeFromPoint(LayoutPoint(point));
2884     return startOrEndCharacterOffsetForRange(caretRange, true);
2885 }
2886
2887 CharacterOffset AXObjectCache::characterOffsetForBounds(const IntRect& rect, bool first)
2888 {
2889     if (rect.isEmpty())
2890         return CharacterOffset();
2891     
2892     IntPoint corner = first ? rect.minXMinYCorner() : rect.maxXMaxYCorner();
2893     CharacterOffset characterOffset = characterOffsetForPoint(corner);
2894     
2895     if (rect.contains(absoluteCaretBoundsForCharacterOffset(characterOffset).center()))
2896         return characterOffset;
2897     
2898     // If the initial position is located outside the bounds adjust it incrementally as needed.
2899     CharacterOffset nextCharOffset = nextCharacterOffset(characterOffset, false);
2900     CharacterOffset previousCharOffset = previousCharacterOffset(characterOffset, false);
2901     while (!nextCharOffset.isNull() || !previousCharOffset.isNull()) {
2902         if (rect.contains(absoluteCaretBoundsForCharacterOffset(nextCharOffset).center()))
2903             return nextCharOffset;
2904         if (rect.contains(absoluteCaretBoundsForCharacterOffset(previousCharOffset).center()))
2905             return previousCharOffset;
2906         
2907         nextCharOffset = nextCharacterOffset(nextCharOffset, false);
2908         previousCharOffset = previousCharacterOffset(previousCharOffset, false);
2909     }
2910     
2911     return CharacterOffset();
2912 }
2913
2914 // FIXME: Remove VisiblePosition code after implementing this using CharacterOffset.
2915 CharacterOffset AXObjectCache::endCharacterOffsetOfLine(const CharacterOffset& characterOffset)
2916 {
2917     if (characterOffset.isNull())
2918         return CharacterOffset();
2919     
2920     VisiblePosition vp = visiblePositionFromCharacterOffset(characterOffset);
2921     VisiblePosition endLine = endOfLine(vp);
2922     
2923     return characterOffsetFromVisiblePosition(endLine);
2924 }
2925
2926 CharacterOffset AXObjectCache::startCharacterOffsetOfLine(const CharacterOffset& characterOffset)
2927 {
2928     if (characterOffset.isNull())
2929         return CharacterOffset();
2930     
2931     VisiblePosition vp = visiblePositionFromCharacterOffset(characterOffset);
2932     VisiblePosition startLine = startOfLine(vp);
2933     
2934     return characterOffsetFromVisiblePosition(startLine);
2935 }
2936
2937 CharacterOffset AXObjectCache::characterOffsetForIndex(int index, const AXCoreObject* obj)
2938 {
2939     if (!obj)
2940         return CharacterOffset();
2941     
2942     VisiblePosition vp = obj->visiblePositionForIndex(index);
2943     CharacterOffset validate = characterOffsetFromVisiblePosition(vp);
2944     // In text control, VisiblePosition always gives the before position of a
2945     // BR node, while CharacterOffset will do the opposite.
2946     if (obj->isTextControl() && characterOffsetNodeIsBR(validate))
2947         validate.offset = 1;
2948     
2949     RefPtr<Range> range = obj->elementRange();
2950     CharacterOffset start = startOrEndCharacterOffsetForRange(range, true, true);
2951     CharacterOffset end = startOrEndCharacterOffsetForRange(range, false, true);
2952     CharacterOffset result = start;
2953     for (int i = 0; i < index; i++) {
2954         if (result.isEqual(validate)) {
2955             // Do not include the new line character, always move the offset to the start of next node.
2956             if ((validate.node->isTextNode() || characterOffsetNodeIsBR(validate))) {
2957                 CharacterOffset next = nextCharacterOffset(validate, false);
2958                 if (!next.isNull() && !next.offset && rootAXEditableElement(next.node) == rootAXEditableElement(validate.node))
2959                     result = next;
2960             }
2961             break;
2962         }
2963         
2964         result = nextCharacterOffset(result, false);
2965         if (result.isEqual(end))
2966             break;
2967     }
2968     return result;
2969 }
2970
2971 int AXObjectCache::indexForCharacterOffset(const CharacterOffset& characterOffset, AccessibilityObject* obj)
2972 {
2973     // Create a collapsed range so that we can get the VisiblePosition from it.
2974     RefPtr<Range> range = rangeForUnorderedCharacterOffsets(characterOffset, characterOffset);
2975     if (!range)
2976         return 0;
2977     VisiblePosition vp = range->startPosition();
2978     return obj->indexForVisiblePosition(vp);
2979 }
2980
2981 const Element* AXObjectCache::rootAXEditableElement(const Node* node)
2982 {
2983     const Element* result = node->rootEditableElement();
2984     const Element* element = is<Element>(*node) ? downcast<Element>(node) : node->parentElement();
2985
2986     for (; element; element = element->parentElement()) {
2987         if (nodeIsTextControl(element))
2988             result = element;
2989     }
2990
2991     return result;
2992 }
2993
2994 static void conditionallyAddNodeToFilterList(Node* node, const Document& document, HashSet<Node*>& nodesToRemove)
2995 {
2996     if (node && (!node->isConnected() || &node->document() == &document))
2997         nodesToRemove.add(node);
2998 }
2999     
3000 template<typename T>
3001 static void filterVectorPairForRemoval(const Vector<std::pair<T, T>>& list, const Document& document, HashSet<Node*>& nodesToRemove)
3002 {
3003     for (auto& entry : list) {
3004         conditionallyAddNodeToFilterList(entry.first, document, nodesToRemove);
3005         conditionallyAddNodeToFilterList(entry.second, document, nodesToRemove);
3006     }
3007 }
3008     
3009 template<typename T, typename U>
3010 static void filterMapForRemoval(const HashMap<T, U>& list, const Document& document, HashSet<Node*>& nodesToRemove)
3011 {
3012     for (auto& entry : list)
3013         conditionallyAddNodeToFilterList(entry.key, document, nodesToRemove);
3014 }
3015
3016 template<typename T>
3017 static void filterListForRemoval(const ListHashSet<T>& list, const Document& document, HashSet<Node*>& nodesToRemove)
3018 {
3019     for (auto* node : list)
3020         conditionallyAddNodeToFilterList(node, document, nodesToRemove);
3021 }
3022
3023 void AXObjectCache::prepareForDocumentDestruction(const Document& document)
3024 {
3025     HashSet<Node*> nodesToRemove;
3026     filterListForRemoval(m_textMarkerNodes, document, nodesToRemove);
3027     filterListForRemoval(m_modalNodesSet, document, nodesToRemove);
3028     filterListForRemoval(m_deferredTextChangedList, document, nodesToRemove);
3029     filterListForRemoval(m_deferredChildrenChangedNodeList, document, nodesToRemove);
3030     filterMapForRemoval(m_deferredTextFormControlValue, document, nodesToRemove);
3031     filterMapForRemoval(m_deferredAttributeChange, document, nodesToRemove);
3032     filterVectorPairForRemoval(m_deferredFocusedNodeChange, document, nodesToRemove);
3033
3034     for (auto* node : nodesToRemove)
3035         remove(*node);
3036 }
3037     
3038 bool AXObjectCache::nodeIsTextControl(const Node* node)
3039 {
3040     if (!node)
3041         return false;
3042
3043     const AccessibilityObject* axObject = getOrCreate(const_cast<Node*>(node));
3044     return axObject && axObject->isTextControl();
3045 }
3046
3047 void AXObjectCache::performCacheUpdateTimerFired()
3048 {
3049     // If there's a pending layout, let the layout trigger the AX update.
3050     if (!document().view() || document().view()->needsLayout())
3051         return;
3052     
3053     performDeferredCacheUpdate();
3054 }
3055     
3056 void AXObjectCache::performDeferredCacheUpdate()
3057 {
3058     AXTRACE("AXObjectCache::performDeferredCacheUpdate");
3059     if (m_performingDeferredCacheUpdate)
3060         return;
3061
3062     SetForScope<bool> performingDeferredCacheUpdate(m_performingDeferredCacheUpdate, true);
3063
3064     for (auto* nodeChild : m_deferredChildrenChangedNodeList) {
3065         handleMenuOpened(nodeChild);
3066         handleLiveRegionCreated(nodeChild);
3067     }
3068     m_deferredChildrenChangedNodeList.clear();
3069
3070     for (auto& child : m_deferredChildrenChangedList)
3071         child->childrenChanged();
3072     m_deferredChildrenChangedList.clear();
3073
3074     for (auto* node : m_deferredTextChangedList)
3075         textChanged(node);
3076     m_deferredTextChangedList.clear();
3077
3078     for (auto& element : m_deferredRecomputeIsIgnoredList) {
3079         if (auto* renderer = element.renderer())
3080             recomputeIsIgnored(renderer);
3081     }
3082     m_deferredRecomputeIsIgnoredList.clear();
3083     
3084     for (auto& selectElement : m_deferredSelectedChildredChangedList)
3085         selectedChildrenChanged(&selectElement);
3086     m_deferredSelectedChildredChangedList.clear();
3087
3088     for (auto& deferredFormControlContext : m_deferredTextFormControlValue) {
3089         auto& textFormControlElement = downcast<HTMLTextFormControlElement>(*deferredFormControlContext.key);
3090         postTextReplacementNotificationForTextControl(textFormControlElement, deferredFormControlContext.value, textFormControlElement.innerTextValue());
3091     }
3092     m_deferredTextFormControlValue.clear();
3093
3094     for (auto& deferredAttributeChangeContext : m_deferredAttributeChange)
3095         handleAttributeChange(deferredAttributeChangeContext.value, deferredAttributeChangeContext.key);
3096     m_deferredAttributeChange.clear();
3097     
3098     for (auto& deferredFocusedChangeContext : m_deferredFocusedNodeChange)
3099         handleFocusedUIElementChanged(deferredFocusedChangeContext.first, deferredFocusedChangeContext.second);
3100     m_deferredFocusedNodeChange.clear();
3101
3102     platformPerformDeferredCacheUpdate();
3103 }
3104     
3105 #if ENABLE(ACCESSIBILITY_ISOLATED_TREE)
3106 Ref<AXIsolatedTree> AXObjectCache::generateIsolatedTree(PageIdentifier pageID, Document& document)
3107 {
3108     AXTRACE("AXObjectCache::generateIsolatedTree");
3109     RELEASE_ASSERT(isMainThread());
3110
3111     RefPtr<AXIsolatedTree> tree(AXIsolatedTree::createTreeForPageID(pageID));
3112
3113     // Set the root and focused objects in the isolated tree. For that, we need
3114     // the root and the focused object in the AXObject tree.
3115     auto* axObjectCache = document.axObjectCache();
3116     if (!axObjectCache)
3117         return makeRef(*tree);
3118     tree->setAXObjectCache(axObjectCache);
3119
3120     auto* axRoot = axObjectCache->getOrCreate(document.view());
3121     if (axRoot)
3122         tree->generateSubtree(*axRoot, InvalidAXID, true);
3123
3124     auto* axFocus = axObjectCache->focusedObject(document);
3125     if (axFocus)
3126         tree->setFocusedNodeID(axFocus->objectID());
3127
3128     return makeRef(*tree);
3129 }
3130
3131 void AXObjectCache::updateIsolatedTree(AXCoreObject& object, AXNotification notification)
3132 {
3133     AXTRACE("AXObjectCache::updateIsolatedTree");
3134
3135     if (!isIsolatedTreeEnabled())
3136         return;
3137
3138     AXLOG(std::make_pair(&object, notification));
3139     AXLOG(*this);
3140
3141     if (!m_pageID)
3142         return;
3143
3144     auto tree = AXIsolatedTree::treeForPageID(*m_pageID);
3145     if (!tree)
3146         return;
3147
3148     switch (notification) {
3149     case AXCheckedStateChanged:
3150     case AXSelectedTextChanged:
3151     case AXValueChanged: {
3152         if (object.objectID() != InvalidAXID)
3153             tree->updateNode(object);
3154         break;
3155     }
3156     default:
3157         break;
3158     }
3159 }
3160
3161 // FIXME: should be added to WTF::Vector.
3162 template<typename T, typename F>
3163 static bool appendIfNotContainsMatching(Vector<T>& vector, const T& value, F matches)
3164 {
3165     if (vector.findMatching(matches) != notFound)
3166         return false;
3167     vector.append(value);
3168     return true;
3169 }
3170
3171 void AXObjectCache::updateIsolatedTree(const Vector<std::pair<RefPtr<AXCoreObject>, AXNotification>>& notifications)
3172 {
3173     AXTRACE("AXObjectCache::updateIsolatedTree");
3174
3175     if (!isIsolatedTreeEnabled())
3176         return;
3177
3178     AXLOG(*this);
3179
3180     if (!m_pageID)
3181         return;
3182
3183     auto tree = AXIsolatedTree::treeForPageID(*m_pageID);
3184     if (!tree)
3185         return;
3186
3187     // Filter out multiple notifications for the same object. This avoids
3188     // updating the isolated tree multiple times unnecessarily.
3189     Vector<std::pair<RefPtr<AXCoreObject>, AXNotification>> filteredNotifications;
3190     for (const auto& notification : notifications) {
3191         AXLOG(notification);
3192         if (!notification.first || notification.first->objectID() == InvalidAXID)
3193             continue;
3194
3195         switch (notification.second) {
3196         case AXCheckedStateChanged:
3197         case AXSelectedTextChanged:
3198         case AXValueChanged: {
3199             bool needsUpdate = appendIfNotContainsMatching(filteredNotifications, notification, [&notification] (const std::pair<RefPtr<AXCoreObject>, AXNotification>& note) {
3200                 return note.second == notification.second && note.first.get() == notification.first.get();
3201             });
3202
3203             if (needsUpdate)
3204                 tree->updateNode(*notification.first);
3205             break;
3206         }
3207         case AXChildrenChanged: {
3208             bool needsUpdate = appendIfNotContainsMatching(filteredNotifications, notification, [&notification] (const std::pair<RefPtr<AXCoreObject>, AXNotification>& note) {
3209                 return note.second == notification.second && note.first.get() == notification.first.get();
3210             });
3211
3212             if (needsUpdate)
3213                 tree->updateChildren(*notification.first);
3214             break;
3215         }
3216         default:
3217             break;
3218         }
3219     }
3220 }
3221 #endif
3222
3223 void AXObjectCache::deferRecomputeIsIgnoredIfNeeded(Element* element)
3224 {
3225     if (!nodeAndRendererAreValid(element))
3226         return;
3227     
3228     if (rendererNeedsDeferredUpdate(*element->renderer())) {
3229         m_deferredRecomputeIsIgnoredList.add(element);
3230         return;
3231     }
3232     recomputeIsIgnored(element->renderer());
3233 }
3234
3235 void AXObjectCache::deferRecomputeIsIgnored(Element* element)
3236 {
3237     if (!nodeAndRendererAreValid(element))
3238         return;
3239
3240     m_deferredRecomputeIsIgnoredList.add(element);
3241 }
3242
3243 void AXObjectCache::deferTextChangedIfNeeded(Node* node)
3244 {
3245     if (!nodeAndRendererAreValid(node))
3246         return;
3247
3248     if (rendererNeedsDeferredUpdate(*node->renderer())) {
3249         m_deferredTextChangedList.add(node);
3250         return;
3251     }
3252     textChanged(node);
3253 }
3254
3255 void AXObjectCache::deferSelectedChildrenChangedIfNeeded(Element& selectElement)
3256 {
3257     if (!nodeAndRendererAreValid(&selectElement))
3258         return;
3259
3260     if (rendererNeedsDeferredUpdate(*selectElement.renderer())) {
3261         m_deferredSelectedChildredChangedList.add(&selectElement);
3262         return;
3263     }
3264     selectedChildrenChanged(&selectElement);
3265 }
3266
3267 void AXObjectCache::deferTextReplacementNotificationForTextControl(HTMLTextFormControlElement& formControlElement, const String& previousValue)
3268 {
3269     auto* renderer = formControlElement.renderer();
3270     if (!renderer)
3271         return;
3272     m_deferredTextFormControlValue.add(&formControlElement, previousValue);
3273 }
3274
3275 bool isNodeAriaVisible(Node* node)
3276 {
3277     if (!node)
3278         return false;
3279
3280     // ARIA Node visibility is controlled by aria-hidden
3281     //  1) if aria-hidden=true, the whole subtree is hidden
3282     //  2) if aria-hidden=false, and the object is rendered, there's no effect
3283     //  3) if aria-hidden=false, and the object is NOT rendered, then it must have
3284     //     aria-hidden=false on each parent until it gets to a rendered object
3285     //  3b) a text node inherits a parents aria-hidden value
3286     bool requiresAriaHiddenFalse = !node->renderer();
3287     bool ariaHiddenFalsePresent = false;
3288     for (Node* testNode = node; testNode; testNode = testNode->parentNode()) {
3289         if (is<Element>(*testNode)) {
3290             const AtomString& ariaHiddenValue = downcast<Element>(*testNode).attributeWithoutSynchronization(aria_hiddenAttr);
3291             if (equalLettersIgnoringASCIICase(ariaHiddenValue, "true"))
3292                 return false;
3293             
3294             bool ariaHiddenFalse = equalLettersIgnoringASCIICase(ariaHiddenValue, "false");
3295             if (!testNode->renderer() && !ariaHiddenFalse)
3296                 return false;
3297             if (!ariaHiddenFalsePresent && ariaHiddenFalse)
3298                 ariaHiddenFalsePresent = true;
3299             // We should break early when it gets to a rendered object.
3300             if (testNode->renderer())
3301                 break;
3302         }
3303     }
3304     
3305     return !requiresAriaHiddenFalse || ariaHiddenFalsePresent;
3306 }
3307
3308 AccessibilityObject* AXObjectCache::rootWebArea()
3309 {
3310     auto* root = getOrCreate(m_document.view());
3311     if (!root || !root->isScrollView())
3312         return nullptr;
3313     return root->webAreaObject();
3314 }
3315
3316 AXAttributeCacheEnabler::AXAttributeCacheEnabler(AXObjectCache* cache)
3317     : m_cache(cache)
3318 {
3319     if (m_cache)
3320         m_cache->startCachingComputedObjectAttributesUntilTreeMutates();
3321 }
3322     
3323 AXAttributeCacheEnabler::~AXAttributeCacheEnabler()
3324 {
3325     if (m_cache)
3326         m_cache->stopCachingComputedObjectAttributes();
3327 }
3328
3329 #if !PLATFORM(COCOA)
3330 AXTextChange AXObjectCache::textChangeForEditType(AXTextEditType type)
3331 {
3332     switch (type) {
3333     case AXTextEditTypeCut:
3334     case AXTextEditTypeDelete:
3335         return AXTextDeleted;
3336     case AXTextEditTypeInsert:
3337     case AXTextEditTypeDictation:
3338     case AXTextEditTypeTyping:
3339     case AXTextEditTypePaste:
3340         return AXTextInserted;
3341     case AXTextEditTypeAttributesChange:
3342         return AXTextAttributesChanged;
3343     case AXTextEditTypeUnknown:
3344         break;
3345     }
3346     ASSERT_NOT_REACHED();
3347     return AXTextInserted;
3348 }
3349 #endif
3350     
3351 } // namespace WebCore
3352
3353 #endif // ENABLE(ACCESSIBILITY)