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