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