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