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