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