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