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