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