AX: Improve performance of addChildren()/childrenChanged()
authorn_wang@apple.com <n_wang@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 29 Apr 2017 18:55:18 +0000 (18:55 +0000)
committern_wang@apple.com <n_wang@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 29 Apr 2017 18:55:18 +0000 (18:55 +0000)
https://bugs.webkit.org/show_bug.cgi?id=171443

Reviewed by Chris Fleizach.

There's a lot of unnecessary work happening when childrenChanged() is being called.
Some of the improvements here:
1. When childrenChanged() is being called on some element, we are marking its parent
   chain dirty. However, in the addChild() method we are then clearing each child of
   that 'dirty' parent, eventually making the entire tree dirty.
   Added a m_subTreeDirty flag and using the needsToUpdateChildren() check to make sure
   we are only clearing the right chain without updating the unchanged siblings.
2. In the addChild() method we are calling accessibilityIsIgnored() on each child and that
   might lead to going up the parent chain again to get necessary information.
   Since we are already traversing the tree from top to bottom to add children, added a
   struct to store the information and pass it to the child so to avoid unnecessary traversal.
3. Reduced the amount work of ARIA text controls perform when updating its parents in childrenChanged()
   so that we don't update a big portion of the tree while typing.

No new tests since this didn't change any functionality.

* accessibility/AccessibilityNodeObject.cpp:
(WebCore::AccessibilityNodeObject::AccessibilityNodeObject):
(WebCore::AccessibilityNodeObject::childrenChanged):
(WebCore::AccessibilityNodeObject::insertChild):
(WebCore::AccessibilityNodeObject::addChildren):
(WebCore::AccessibilityNodeObject::isDescendantOfBarrenParent):
* accessibility/AccessibilityNodeObject.h:
* accessibility/AccessibilityObject.cpp:
(WebCore::AccessibilityObject::AccessibilityObject):
(WebCore::AccessibilityObject::defaultObjectInclusion):
(WebCore::AccessibilityObject::setIsIgnoredFromParentDataForChild):
* accessibility/AccessibilityObject.h:
(WebCore::AccessibilityIsIgnoredFromParentData::AccessibilityIsIgnoredFromParentData):
(WebCore::AccessibilityIsIgnoredFromParentData::isNull):
(WebCore::AccessibilityObject::setNeedsToUpdateSubTree):
(WebCore::AccessibilityObject::needsToUpdateChildren):
(WebCore::AccessibilityObject::setIsIgnoredFromParentData):
* accessibility/AccessibilityRenderObject.cpp:
(WebCore::AccessibilityRenderObject::updateChildrenIfNecessary):
(WebCore::AccessibilityRenderObject::addChildren):
* accessibility/AccessibilityRenderObject.h:
(WebCore::AccessibilityRenderObject::setRenderObject):
(WebCore::AccessibilityRenderObject::needsToUpdateChildren): Deleted.

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@215975 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WebCore/ChangeLog
Source/WebCore/accessibility/AccessibilityNodeObject.cpp
Source/WebCore/accessibility/AccessibilityNodeObject.h
Source/WebCore/accessibility/AccessibilityObject.cpp
Source/WebCore/accessibility/AccessibilityObject.h
Source/WebCore/accessibility/AccessibilityRenderObject.cpp
Source/WebCore/accessibility/AccessibilityRenderObject.h

index 72ffca51c495aff44d5e897ab58470cf201ddbef..9c6a1d32c1a86210ae48adefa0fed1467bb44f78 100644 (file)
@@ -1,3 +1,50 @@
+2017-04-29  Nan Wang  <n_wang@apple.com>
+
+        AX: Improve performance of addChildren()/childrenChanged()
+        https://bugs.webkit.org/show_bug.cgi?id=171443
+
+        Reviewed by Chris Fleizach.
+
+        There's a lot of unnecessary work happening when childrenChanged() is being called.
+        Some of the improvements here:
+        1. When childrenChanged() is being called on some element, we are marking its parent
+           chain dirty. However, in the addChild() method we are then clearing each child of
+           that 'dirty' parent, eventually making the entire tree dirty. 
+           Added a m_subTreeDirty flag and using the needsToUpdateChildren() check to make sure
+           we are only clearing the right chain without updating the unchanged siblings.
+        2. In the addChild() method we are calling accessibilityIsIgnored() on each child and that 
+           might lead to going up the parent chain again to get necessary information. 
+           Since we are already traversing the tree from top to bottom to add children, added a 
+           struct to store the information and pass it to the child so to avoid unnecessary traversal.
+        3. Reduced the amount work of ARIA text controls perform when updating its parents in childrenChanged() 
+           so that we don't update a big portion of the tree while typing.
+
+        No new tests since this didn't change any functionality. 
+
+        * accessibility/AccessibilityNodeObject.cpp:
+        (WebCore::AccessibilityNodeObject::AccessibilityNodeObject):
+        (WebCore::AccessibilityNodeObject::childrenChanged):
+        (WebCore::AccessibilityNodeObject::insertChild):
+        (WebCore::AccessibilityNodeObject::addChildren):
+        (WebCore::AccessibilityNodeObject::isDescendantOfBarrenParent):
+        * accessibility/AccessibilityNodeObject.h:
+        * accessibility/AccessibilityObject.cpp:
+        (WebCore::AccessibilityObject::AccessibilityObject):
+        (WebCore::AccessibilityObject::defaultObjectInclusion):
+        (WebCore::AccessibilityObject::setIsIgnoredFromParentDataForChild):
+        * accessibility/AccessibilityObject.h:
+        (WebCore::AccessibilityIsIgnoredFromParentData::AccessibilityIsIgnoredFromParentData):
+        (WebCore::AccessibilityIsIgnoredFromParentData::isNull):
+        (WebCore::AccessibilityObject::setNeedsToUpdateSubTree):
+        (WebCore::AccessibilityObject::needsToUpdateChildren):
+        (WebCore::AccessibilityObject::setIsIgnoredFromParentData):
+        * accessibility/AccessibilityRenderObject.cpp:
+        (WebCore::AccessibilityRenderObject::updateChildrenIfNecessary):
+        (WebCore::AccessibilityRenderObject::addChildren):
+        * accessibility/AccessibilityRenderObject.h:
+        (WebCore::AccessibilityRenderObject::setRenderObject):
+        (WebCore::AccessibilityRenderObject::needsToUpdateChildren): Deleted.
+
 2017-04-29  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Move WebCore CPUTime to WTF and implement it in all the platforms
 2017-04-29  Yusuke Suzuki  <utatane.tea@gmail.com>
 
         Move WebCore CPUTime to WTF and implement it in all the platforms
index 66b83e7831d760d223d77edcac153a1e943dcacb..8146f368646f7690866d051ad674113bb7459165 100644 (file)
@@ -85,6 +85,7 @@ AccessibilityNodeObject::AccessibilityNodeObject(Node* node)
     : AccessibilityObject()
     , m_ariaRole(UnknownRole)
     , m_childrenDirty(false)
     : AccessibilityObject()
     , m_ariaRole(UnknownRole)
     , m_childrenDirty(false)
+    , m_subtreeDirty(false)
     , m_roleForMSAA(UnknownRole)
 #ifndef NDEBUG
     , m_initialized(false)
     , m_roleForMSAA(UnknownRole)
 #ifndef NDEBUG
     , m_initialized(false)
@@ -129,13 +130,19 @@ void AccessibilityNodeObject::childrenChanged()
     if (!cache)
         return;
     cache->postNotification(this, document(), AXObjectCache::AXChildrenChanged);
     if (!cache)
         return;
     cache->postNotification(this, document(), AXObjectCache::AXChildrenChanged);
+    
+    // Should make the sub tree dirty so that everything below will be updated correctly.
+    this->setNeedsToUpdateSubtree();
+    bool shouldStopUpdatingParent = false;
 
     // Go up the accessibility parent chain, but only if the element already exists. This method is
     // called during render layouts, minimal work should be done. 
     // If AX elements are created now, they could interrogate the render tree while it's in a funky state.
     // At the same time, process ARIA live region changes.
     for (AccessibilityObject* parent = this; parent; parent = parent->parentObjectIfExists()) {
 
     // Go up the accessibility parent chain, but only if the element already exists. This method is
     // called during render layouts, minimal work should be done. 
     // If AX elements are created now, they could interrogate the render tree while it's in a funky state.
     // At the same time, process ARIA live region changes.
     for (AccessibilityObject* parent = this; parent; parent = parent->parentObjectIfExists()) {
-        parent->setNeedsToUpdateChildren();
+        if (!shouldStopUpdatingParent)
+            parent->setNeedsToUpdateChildren();
+        
 
         // These notifications always need to be sent because screenreaders are reliant on them to perform. 
         // In other words, they need to be sent even when the screen reader has not accessed this live region since the last update.
 
         // These notifications always need to be sent because screenreaders are reliant on them to perform. 
         // In other words, they need to be sent even when the screen reader has not accessed this live region since the last update.
@@ -148,8 +155,13 @@ void AccessibilityNodeObject::childrenChanged()
             cache->postLiveRegionChangeNotification(parent);
         
         // If this element is an ARIA text control, notify the AT of changes.
             cache->postLiveRegionChangeNotification(parent);
         
         // If this element is an ARIA text control, notify the AT of changes.
-        if (parent->isNonNativeTextControl())
+        if (parent->isNonNativeTextControl()) {
             cache->postNotification(parent, parent->document(), AXObjectCache::AXValueChanged);
             cache->postNotification(parent, parent->document(), AXObjectCache::AXValueChanged);
+            
+            // Do not let the parent that's above the editable ancestor update its children
+            // since we already notify the AT of changes.
+            shouldStopUpdatingParent = true;
+        }
     }
 }
 
     }
 }
 
@@ -333,8 +345,24 @@ void AccessibilityNodeObject::insertChild(AccessibilityObject* child, unsigned i
     // If the parent is asking for this child's children, then either it's the first time (and clearing is a no-op),
     // or its visibility has changed. In the latter case, this child may have a stale child cached.
     // This can prevent aria-hidden changes from working correctly. Hence, whenever a parent is getting children, ensure data is not stale.
     // If the parent is asking for this child's children, then either it's the first time (and clearing is a no-op),
     // or its visibility has changed. In the latter case, this child may have a stale child cached.
     // This can prevent aria-hidden changes from working correctly. Hence, whenever a parent is getting children, ensure data is not stale.
-    child->clearChildren();
+    // Only clear the child's children when we know it's in the updating chain in order to avoid unnecessary work.
+    if (child->needsToUpdateChildren() || m_subtreeDirty) {
+        child->clearChildren();
+        // Pass m_subtreeDirty flag down to the child so that children cache gets reset properly.
+        if (m_subtreeDirty)
+            child->setNeedsToUpdateSubtree();
+    } else {
+        // For some reason the grand children might be detached so that we need to regenerate the
+        // children list of this child.
+        for (const auto& grandChild : child->children(false)) {
+            if (grandChild->isDetachedFromParent()) {
+                child->clearChildren();
+                break;
+            }
+        }
+    }
     
     
+    setIsIgnoredFromParentDataForChild(child);
     if (child->accessibilityIsIgnored()) {
         const auto& children = child->children();
         size_t length = children.size();
     if (child->accessibilityIsIgnored()) {
         const auto& children = child->children();
         size_t length = children.size();
@@ -344,6 +372,9 @@ void AccessibilityNodeObject::insertChild(AccessibilityObject* child, unsigned i
         ASSERT(child->parentObject() == this);
         m_children.insert(index, child);
     }
         ASSERT(child->parentObject() == this);
         m_children.insert(index, child);
     }
+    
+    // Reset the child's m_isIgnoredFromParentData since we are done adding that child and its children.
+    child->clearIsIgnoredFromParentData();
 }
 
 void AccessibilityNodeObject::addChild(AccessibilityObject* child)
 }
 
 void AccessibilityNodeObject::addChild(AccessibilityObject* child)
@@ -368,6 +399,8 @@ void AccessibilityNodeObject::addChildren()
     
     for (Node* child = m_node->firstChild(); child; child = child->nextSibling())
         addChild(axObjectCache()->getOrCreate(child));
     
     for (Node* child = m_node->firstChild(); child; child = child->nextSibling())
         addChild(axObjectCache()->getOrCreate(child));
+    
+    m_subtreeDirty = false;
 }
 
 bool AccessibilityNodeObject::canHaveChildren() const
 }
 
 bool AccessibilityNodeObject::canHaveChildren() const
@@ -1059,6 +1092,9 @@ Element* AccessibilityNodeObject::mouseButtonListener(MouseButtonListenerResultF
 
 bool AccessibilityNodeObject::isDescendantOfBarrenParent() const
 {
 
 bool AccessibilityNodeObject::isDescendantOfBarrenParent() const
 {
+    if (!m_isIgnoredFromParentData.isNull())
+        return m_isIgnoredFromParentData.isDescendantOfBarrenParent;
+    
     for (AccessibilityObject* object = parentObject(); object; object = object->parentObject()) {
         if (!object->canHaveChildren())
             return true;
     for (AccessibilityObject* object = parentObject(); object; object = object->parentObject()) {
         if (!object->canHaveChildren())
             return true;
index 37d6eb01f40fec0b1daf5e4523ec920b666b2d0a..587af7369d62c7981acffa91463afe87bfc837fe 100644 (file)
@@ -146,6 +146,7 @@ protected:
 
     AccessibilityRole m_ariaRole;
     bool m_childrenDirty;
 
     AccessibilityRole m_ariaRole;
     bool m_childrenDirty;
+    bool m_subtreeDirty;
     mutable AccessibilityRole m_roleForMSAA;
 #ifndef NDEBUG
     bool m_initialized;
     mutable AccessibilityRole m_roleForMSAA;
 #ifndef NDEBUG
     bool m_initialized;
index d2bcf3b6448bf885caf450d4ed1c98b1cb2e30dc..460a986e0e686ccdb26db0aadcb09289bb607f00 100644 (file)
@@ -86,6 +86,7 @@ AccessibilityObject::AccessibilityObject()
     , m_haveChildren(false)
     , m_role(UnknownRole)
     , m_lastKnownIsIgnoredValue(DefaultBehavior)
     , m_haveChildren(false)
     , m_role(UnknownRole)
     , m_lastKnownIsIgnoredValue(DefaultBehavior)
+    , m_isIgnoredFromParentData(AccessibilityIsIgnoredFromParentData())
 #if PLATFORM(GTK)
     , m_wrapper(nullptr)
 #endif
 #if PLATFORM(GTK)
     , m_wrapper(nullptr)
 #endif
@@ -3097,13 +3098,15 @@ bool AccessibilityObject::isDOMHidden() const
 
 AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
 {
 
 AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
 {
-    if (isARIAHidden())
+    bool useParentData = !m_isIgnoredFromParentData.isNull();
+    
+    if (useParentData ? m_isIgnoredFromParentData.isARIAHidden : isARIAHidden())
         return IgnoreObject;
     
     if (ignoredFromARIAModalPresence())
         return IgnoreObject;
     
         return IgnoreObject;
     
     if (ignoredFromARIAModalPresence())
         return IgnoreObject;
     
-    if (isPresentationalChildOfAriaRole())
+    if (useParentData ? m_isIgnoredFromParentData.isPresentationalChildOfAriaRole : isPresentationalChildOfAriaRole())
         return IgnoreObject;
     
     return accessibilityPlatformIncludesObject();
         return IgnoreObject;
     
     return accessibilityPlatformIncludesObject();
@@ -3295,4 +3298,23 @@ void AccessibilityObject::ariaOwnsElements(AccessibilityChildrenVector& axObject
     ariaElementsFromAttribute(axObjects, aria_ownsAttr);
 }
 
     ariaElementsFromAttribute(axObjects, aria_ownsAttr);
 }
 
+void AccessibilityObject::setIsIgnoredFromParentDataForChild(AccessibilityObject* child)
+{
+    if (!child || child->parentObject() != this)
+        return;
+    
+    AccessibilityIsIgnoredFromParentData result = AccessibilityIsIgnoredFromParentData(this);
+    if (!m_isIgnoredFromParentData.isNull()) {
+        result.isARIAHidden = m_isIgnoredFromParentData.isARIAHidden || equalLettersIgnoringASCIICase(child->getAttribute(aria_hiddenAttr), "true");
+        result.isPresentationalChildOfAriaRole = m_isIgnoredFromParentData.isPresentationalChildOfAriaRole || ariaRoleHasPresentationalChildren();
+        result.isDescendantOfBarrenParent = m_isIgnoredFromParentData.isDescendantOfBarrenParent || !canHaveChildren();
+    } else {
+        result.isARIAHidden = child->isARIAHidden();
+        result.isPresentationalChildOfAriaRole = child->isPresentationalChildOfAriaRole();
+        result.isDescendantOfBarrenParent = child->isDescendantOfBarrenParent();
+    }
+    
+    child->setIsIgnoredFromParentData(result);
+}
+
 } // namespace WebCore
 } // namespace WebCore
index 40587361a5aa3d28ec0582ba1e5d875180c84fef..bd649069be90bbc5817332dcbe947b74a59ca2c7 100644 (file)
@@ -285,6 +285,24 @@ struct AccessibilityTextUnderElementMode {
         , ignoredChildNode(ignored)
         { }
 };
         , ignoredChildNode(ignored)
         { }
 };
+
+// Use this struct to store the isIgnored data that depends on the parents, so that in addChildren()
+// we avoid going up the parent chain for each element while traversing the tree with useful information already.
+struct AccessibilityIsIgnoredFromParentData {
+    AccessibilityObject* parent;
+    bool isARIAHidden;
+    bool isPresentationalChildOfAriaRole;
+    bool isDescendantOfBarrenParent;
+    
+    AccessibilityIsIgnoredFromParentData(AccessibilityObject* parent = nullptr)
+        : parent(parent)
+        , isARIAHidden(false)
+        , isPresentationalChildOfAriaRole(false)
+        , isDescendantOfBarrenParent(false)
+        { }
+    
+    bool isNull() const { return !parent; }
+};
     
 enum AccessibilityOrientation {
     AccessibilityOrientationVertical,
     
 enum AccessibilityOrientation {
     AccessibilityOrientationVertical,
@@ -822,7 +840,9 @@ public:
     virtual bool hasChildren() const { return m_haveChildren; }
     virtual void updateChildrenIfNecessary();
     virtual void setNeedsToUpdateChildren() { }
     virtual bool hasChildren() const { return m_haveChildren; }
     virtual void updateChildrenIfNecessary();
     virtual void setNeedsToUpdateChildren() { }
+    virtual void setNeedsToUpdateSubtree() { }
     virtual void clearChildren();
     virtual void clearChildren();
+    virtual bool needsToUpdateChildren() const { return false; }
 #if PLATFORM(COCOA)
     virtual void detachFromParent();
 #else
 #if PLATFORM(COCOA)
     virtual void detachFromParent();
 #else
@@ -1078,12 +1098,18 @@ public:
     
     static const AccessibilityObject* matchedParent(const AccessibilityObject&, bool includeSelf, const std::function<bool(const AccessibilityObject&)>&);
     
     
     static const AccessibilityObject* matchedParent(const AccessibilityObject&, bool includeSelf, const std::function<bool(const AccessibilityObject&)>&);
     
+    void clearIsIgnoredFromParentData() { m_isIgnoredFromParentData = AccessibilityIsIgnoredFromParentData(); }
+    void setIsIgnoredFromParentDataForChild(AccessibilityObject*);
+    
 protected:
     AXID m_id;
     AccessibilityChildrenVector m_children;
     mutable bool m_haveChildren;
     AccessibilityRole m_role;
     AccessibilityObjectInclusion m_lastKnownIsIgnoredValue;
 protected:
     AXID m_id;
     AccessibilityChildrenVector m_children;
     mutable bool m_haveChildren;
     AccessibilityRole m_role;
     AccessibilityObjectInclusion m_lastKnownIsIgnoredValue;
+    AccessibilityIsIgnoredFromParentData m_isIgnoredFromParentData;
+    
+    void setIsIgnoredFromParentData(AccessibilityIsIgnoredFromParentData& data) { m_isIgnoredFromParentData = data; }
 
     virtual bool computeAccessibilityIsIgnored() const { return true; }
 
 
     virtual bool computeAccessibilityIsIgnored() const { return true; }
 
index e277477e120505dd2af6814de2aac5ded7db9561..74a6d1b42a0bec447f9a58f2e2148dd9a975226c 100644 (file)
@@ -2982,7 +2982,7 @@ void AccessibilityRenderObject::addImageMapChildren()
 void AccessibilityRenderObject::updateChildrenIfNecessary()
 {
     if (needsToUpdateChildren())
 void AccessibilityRenderObject::updateChildrenIfNecessary()
 {
     if (needsToUpdateChildren())
-        clearChildren();        
+        clearChildren();
     
     AccessibilityObject::updateChildrenIfNecessary();
 }
     
     AccessibilityObject::updateChildrenIfNecessary();
 }
@@ -3207,6 +3207,8 @@ void AccessibilityRenderObject::addChildren()
     for (RefPtr<AccessibilityObject> obj = firstChild(); obj; obj = obj->nextSibling())
         addChild(obj.get());
     
     for (RefPtr<AccessibilityObject> obj = firstChild(); obj; obj = obj->nextSibling())
         addChild(obj.get());
     
+    m_subtreeDirty = false;
+    
     addHiddenChildren();
     addAttachmentChildren();
     addImageMapChildren();
     addHiddenChildren();
     addAttachmentChildren();
     addImageMapChildren();
index cccb39ebed1d726981db314a31e6f8ff24083f99..21227b64352096c4a103d8480cf676fade04e915 100644 (file)
@@ -202,7 +202,6 @@ public:
 protected:
     explicit AccessibilityRenderObject(RenderObject*);
     void setRenderObject(RenderObject* renderer) { m_renderer = renderer; }
 protected:
     explicit AccessibilityRenderObject(RenderObject*);
     void setRenderObject(RenderObject* renderer) { m_renderer = renderer; }
-    bool needsToUpdateChildren() const { return m_childrenDirty; }
     ScrollableArea* getScrollableAreaIfScrollable() const override;
     void scrollTo(const IntPoint&) const override;
     
     ScrollableArea* getScrollableAreaIfScrollable() const override;
     void scrollTo(const IntPoint&) const override;
     
@@ -228,6 +227,8 @@ private:
     Element* rootEditableElementForPosition(const Position&) const;
     bool nodeIsTextControl(const Node*) const;
     void setNeedsToUpdateChildren() override { m_childrenDirty = true; }
     Element* rootEditableElementForPosition(const Position&) const;
     bool nodeIsTextControl(const Node*) const;
     void setNeedsToUpdateChildren() override { m_childrenDirty = true; }
+    bool needsToUpdateChildren() const override { return m_childrenDirty; }
+    void setNeedsToUpdateSubtree() override { m_subtreeDirty = true; }
     Path elementPath() const override;
     
     bool isTabItemSelected() const;
     Path elementPath() const override;
     
     bool isTabItemSelected() const;