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