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