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