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 72ffca5..9c6a1d3 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
index 66b83e7..8146f36 100644 (file)
@@ -85,6 +85,7 @@ AccessibilityNodeObject::AccessibilityNodeObject(Node* node)
     : AccessibilityObject()
     , m_ariaRole(UnknownRole)
     , m_childrenDirty(false)
+    , m_subtreeDirty(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);
+    
+    // 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()) {
-        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.
@@ -148,8 +155,13 @@ void AccessibilityNodeObject::childrenChanged()
             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);
+            
+            // 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.
-    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();
@@ -344,6 +372,9 @@ void AccessibilityNodeObject::insertChild(AccessibilityObject* child, unsigned i
         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)
@@ -368,6 +399,8 @@ void AccessibilityNodeObject::addChildren()
     
     for (Node* child = m_node->firstChild(); child; child = child->nextSibling())
         addChild(axObjectCache()->getOrCreate(child));
+    
+    m_subtreeDirty = false;
 }
 
 bool AccessibilityNodeObject::canHaveChildren() const
@@ -1059,6 +1092,9 @@ Element* AccessibilityNodeObject::mouseButtonListener(MouseButtonListenerResultF
 
 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;
index 37d6eb0..587af73 100644 (file)
@@ -146,6 +146,7 @@ protected:
 
     AccessibilityRole m_ariaRole;
     bool m_childrenDirty;
+    bool m_subtreeDirty;
     mutable AccessibilityRole m_roleForMSAA;
 #ifndef NDEBUG
     bool m_initialized;
index d2bcf3b..460a986 100644 (file)
@@ -86,6 +86,7 @@ AccessibilityObject::AccessibilityObject()
     , m_haveChildren(false)
     , m_role(UnknownRole)
     , m_lastKnownIsIgnoredValue(DefaultBehavior)
+    , m_isIgnoredFromParentData(AccessibilityIsIgnoredFromParentData())
 #if PLATFORM(GTK)
     , m_wrapper(nullptr)
 #endif
@@ -3097,13 +3098,15 @@ bool AccessibilityObject::isDOMHidden() const
 
 AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
 {
-    if (isARIAHidden())
+    bool useParentData = !m_isIgnoredFromParentData.isNull();
+    
+    if (useParentData ? m_isIgnoredFromParentData.isARIAHidden : isARIAHidden())
         return IgnoreObject;
     
     if (ignoredFromARIAModalPresence())
         return IgnoreObject;
     
-    if (isPresentationalChildOfAriaRole())
+    if (useParentData ? m_isIgnoredFromParentData.isPresentationalChildOfAriaRole : isPresentationalChildOfAriaRole())
         return IgnoreObject;
     
     return accessibilityPlatformIncludesObject();
@@ -3295,4 +3298,23 @@ void AccessibilityObject::ariaOwnsElements(AccessibilityChildrenVector& axObject
     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
index 4058736..bd64906 100644 (file)
@@ -285,6 +285,24 @@ struct AccessibilityTextUnderElementMode {
         , 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,
@@ -822,7 +840,9 @@ public:
     virtual bool hasChildren() const { return m_haveChildren; }
     virtual void updateChildrenIfNecessary();
     virtual void setNeedsToUpdateChildren() { }
+    virtual void setNeedsToUpdateSubtree() { }
     virtual void clearChildren();
+    virtual bool needsToUpdateChildren() const { return false; }
 #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&)>&);
     
+    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;
+    AccessibilityIsIgnoredFromParentData m_isIgnoredFromParentData;
+    
+    void setIsIgnoredFromParentData(AccessibilityIsIgnoredFromParentData& data) { m_isIgnoredFromParentData = data; }
 
     virtual bool computeAccessibilityIsIgnored() const { return true; }
 
index e277477..74a6d1b 100644 (file)
@@ -2982,7 +2982,7 @@ void AccessibilityRenderObject::addImageMapChildren()
 void AccessibilityRenderObject::updateChildrenIfNecessary()
 {
     if (needsToUpdateChildren())
-        clearChildren();        
+        clearChildren();
     
     AccessibilityObject::updateChildrenIfNecessary();
 }
@@ -3207,6 +3207,8 @@ void AccessibilityRenderObject::addChildren()
     for (RefPtr<AccessibilityObject> obj = firstChild(); obj; obj = obj->nextSibling())
         addChild(obj.get());
     
+    m_subtreeDirty = false;
+    
     addHiddenChildren();
     addAttachmentChildren();
     addImageMapChildren();
index cccb39e..21227b6 100644 (file)
@@ -202,7 +202,6 @@ public:
 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;
     
@@ -228,6 +227,8 @@ private:
     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;