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