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