bug 1041070 - fix O(N^2) runtime of tree update r=surkov
authorTrevor Saunders <trev.saunders@gmail.com>
Tue, 02 Sep 2014 14:54:04 -0400
changeset 232450 6525c7ee1f50addf145723c976dc353e4be9a00c
parent 232449 f72b6d7ece75f3824d6322dc011a41ef5c049c2d
child 232451 97febbb46ef483c73f29bd4a0296074d1e28bfa1
push id4187
push userbhearsum@mozilla.com
push dateFri, 28 Nov 2014 15:29:12 +0000
treeherdermozilla-beta@f23cc6a30c11 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssurkov
bugs1041070
milestone35.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
bug 1041070 - fix O(N^2) runtime of tree update r=surkov
accessible/generic/Accessible-inl.h
accessible/generic/Accessible.cpp
accessible/generic/Accessible.h
accessible/generic/DocAccessible.cpp
accessible/html/HTMLImageMapAccessible.cpp
--- a/accessible/generic/Accessible-inl.h
+++ b/accessible/generic/Accessible-inl.h
@@ -62,12 +62,20 @@ Accessible::HasNumericValue() const
 
 inline void
 Accessible::ScrollTo(uint32_t aHow) const
 {
   if (mContent)
     nsCoreUtils::ScrollTo(mDoc->PresShell(), mContent, aHow);
 }
 
+inline bool
+Accessible::UpdateChildren()
+{
+  AutoTreeMutation mut(this);
+  InvalidateChildren();
+  return EnsureChildren();
+}
+
 } // namespace a11y
 } // namespace mozilla
 
 #endif
--- a/accessible/generic/Accessible.cpp
+++ b/accessible/generic/Accessible.cpp
@@ -1931,30 +1931,34 @@ Accessible::BindToParent(Accessible* aPa
       NS_ERROR("Binding to the same parent!");
       return;
     }
   }
 
   mParent = aParent;
   mIndexInParent = aIndexInParent;
 
-  mParent->InvalidateChildrenGroupInfo();
+#ifdef DEBUG
+  AssertInMutatingSubtree();
+#endif
 
   // Note: this is currently only used for richlistitems and their children.
   if (mParent->HasNameDependentParent() || mParent->IsXULListItem())
     mContextFlags |= eHasNameDependentParent;
   else
     mContextFlags &= ~eHasNameDependentParent;
 }
 
 // Accessible protected
 void
 Accessible::UnbindFromParent()
 {
-  mParent->InvalidateChildrenGroupInfo();
+#ifdef DEBUG
+  AssertInMutatingSubtree();
+#endif
   mParent = nullptr;
   mIndexInParent = -1;
   mIndexOfEmbeddedChild = -1;
   mGroupInfo = nullptr;
   mContextFlags &= ~eHasNameDependentParent;
 }
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -2653,16 +2657,31 @@ Accessible::StaticAsserts() const
   static_assert(eLastAccType <= (1 << kTypeBits) - 1,
                 "Accessible::mType was oversized by eLastAccType!");
   static_assert(eLastContextFlag <= (1 << kContextFlagsBits) - 1,
                 "Accessible::mContextFlags was oversized by eLastContextFlag!");
   static_assert(eLastAccGenericType <= (1 << kGenericTypesBits) - 1,
                 "Accessible::mGenericType was oversized by eLastAccGenericType!");
 }
 
+void
+Accessible::AssertInMutatingSubtree() const
+{
+  if (IsDoc() || IsApplication())
+    return;
+
+  const Accessible *acc = this;
+  while (!acc->IsDoc() && !(acc->mStateFlags & eSubtreeMutating)) {
+    acc = acc->Parent();
+    if (!acc)
+      return;
+  }
+
+  MOZ_ASSERT(acc->mStateFlags & eSubtreeMutating);
+}
 
 ////////////////////////////////////////////////////////////////////////////////
 // KeyBinding class
 
 // static
 uint32_t
 KeyBinding::AccelModifier()
 {
--- a/accessible/generic/Accessible.h
+++ b/accessible/generic/Accessible.h
@@ -368,21 +368,17 @@ public:
    * Set the ARIA role map entry for a new accessible.
    */
   void SetRoleMapEntry(nsRoleMapEntry* aRoleMapEntry)
     { mRoleMapEntry = aRoleMapEntry; }
 
   /**
    * Update the children cache.
    */
-  inline bool UpdateChildren()
-  {
-    InvalidateChildren();
-    return EnsureChildren();
-  }
+  bool UpdateChildren();
 
   /**
    * Cache children if necessary. Return true if the accessible is defunct.
    */
   bool EnsureChildren();
 
   /**
    * Set the child count to -1 (unknown) and null out cached child pointers.
@@ -943,17 +939,18 @@ protected:
    */
   enum StateFlags {
     eIsDefunct = 1 << 0, // accessible is defunct
     eIsNotInDocument = 1 << 1, // accessible is not in document
     eSharedNode = 1 << 2, // accessible shares DOM node from another accessible
     eNotNodeMapEntry = 1 << 3, // accessible shouldn't be in document node map
     eHasNumericValue = 1 << 4, // accessible has a numeric value
     eGroupInfoDirty = 1 << 5, // accessible needs to update group info
-    eIgnoreDOMUIEvent = 1 << 6, // don't process DOM UI events for a11y events
+    eSubtreeMutating = 1 << 6, // subtree is being mutated
+    eIgnoreDOMUIEvent = 1 << 7, // don't process DOM UI events for a11y events
 
     eLastStateFlag = eIgnoreDOMUIEvent
   };
 
   /**
    * Flags used for contextual information about the accessible.
    */
   enum ContextFlags {
@@ -1059,34 +1056,36 @@ protected:
   nsCOMPtr<nsIContent> mContent;
   DocAccessible* mDoc;
 
   nsRefPtr<Accessible> mParent;
   nsTArray<nsRefPtr<Accessible> > mChildren;
   int32_t mIndexInParent;
 
   static const uint8_t kChildrenFlagsBits = 2;
-  static const uint8_t kStateFlagsBits = 7;
+  static const uint8_t kStateFlagsBits = 8;
   static const uint8_t kContextFlagsBits = 1;
   static const uint8_t kTypeBits = 6;
   static const uint8_t kGenericTypesBits = 13;
 
   /**
    * Keep in sync with ChildrenFlags, StateFlags, ContextFlags, and AccTypes.
    */
   uint32_t mChildrenFlags : kChildrenFlagsBits;
   uint32_t mStateFlags : kStateFlagsBits;
   uint32_t mContextFlags : kContextFlagsBits;
   uint32_t mType : kTypeBits;
   uint32_t mGenericTypes : kGenericTypesBits;
 
   void StaticAsserts() const;
+  void AssertInMutatingSubtree() const;
 
   friend class DocAccessible;
   friend class xpcAccessible;
+  friend class AutoTreeMutation;
 
   nsAutoPtr<mozilla::a11y::EmbeddedObjCollector> mEmbeddedObjCollector;
   int32_t mIndexOfEmbeddedChild;
   friend class EmbeddedObjCollector;
 
   nsAutoPtr<AccGroupInfo> mGroupInfo;
   friend class AccGroupInfo;
 
@@ -1160,12 +1159,41 @@ public:
 private:
   void ToPlatformFormat(nsAString& aValue) const;
   void ToAtkFormat(nsAString& aValue) const;
 
   uint32_t mKey;
   uint32_t mModifierMask;
 };
 
+/**
+ * This class makes sure required tasks are done before and after tree
+ * mutations. Currently this only includes group info invalidation. You must
+ * have an object of this class on the stack when calling methods that mutate
+ * the accessible tree.
+ */
+class AutoTreeMutation
+{
+public:
+  AutoTreeMutation(Accessible* aRoot, bool aInvalidationRequired = true) :
+    mInvalidationRequired(aInvalidationRequired), mRoot(aRoot)
+  {
+    MOZ_ASSERT(!(mRoot->mStateFlags & Accessible::eSubtreeMutating));
+    mRoot->mStateFlags |= Accessible::eSubtreeMutating;
+  }
+  ~AutoTreeMutation()
+  {
+    if (mInvalidationRequired)
+      mRoot->InvalidateChildrenGroupInfo();
+
+    MOZ_ASSERT(mRoot->mStateFlags & Accessible::eSubtreeMutating);
+    mRoot->mStateFlags &= ~Accessible::eSubtreeMutating;
+  }
+
+  bool mInvalidationRequired;
+private:
+  Accessible* mRoot;
+};
+
 } // namespace a11y
 } // namespace mozilla
 
 #endif
--- a/accessible/generic/DocAccessible.cpp
+++ b/accessible/generic/DocAccessible.cpp
@@ -478,17 +478,23 @@ DocAccessible::Shutdown()
     mVirtualCursor = nullptr;
   }
 
   mPresShell->SetDocAccessible(nullptr);
   mPresShell = nullptr;  // Avoid reentrancy
 
   mDependentIDsHash.Clear();
   mNodeToAccessibleMap.Clear();
-  ClearCache(mAccessibleCache);
+
+  {
+    // We're about to get rid of all of our children so there won't be anything
+    // to invalidate.
+    AutoTreeMutation mut(this, false);
+    ClearCache(mAccessibleCache);
+  }
 
   HyperTextAccessibleWrap::Shutdown();
 
   GetAccService()->NotifyOfDocumentShutdown(kungFuDeathGripDoc);
 }
 
 nsIFrame*
 DocAccessible::GetFrame() const
@@ -1313,18 +1319,20 @@ DocAccessible::ProcessInvalidationList()
       Accessible* container = GetContainerAccessible(content);
       if (container) {
         container->UpdateChildren();
         accessible = GetAccessible(content);
       }
     }
 
     // Make sure the subtree is created.
-    if (accessible)
+    if (accessible) {
+      AutoTreeMutation mut(accessible);
       CacheChildrenInSubtree(accessible);
+    }
   }
 
   mInvalidationList.Clear();
 }
 
 Accessible*
 DocAccessible::GetAccessibleEvenIfNotInMap(nsINode* aNode) const
 {
@@ -1420,17 +1428,19 @@ DocAccessible::DoInitialUpdate()
   // miss the notification (since content tree change notifications are ignored
   // prior to initial update). Make sure the content element is valid.
   nsIContent* contentElm = nsCoreUtils::GetRoleContent(mDocumentNode);
   if (mContent != contentElm) {
     mContent = contentElm;
     SetRoleMapEntry(aria::GetRoleMap(mContent));
   }
 
-  // Build initial tree.
+  // Build initial tree.  Since its the initial tree there's no group info to
+  // invalidate.
+  AutoTreeMutation mut(this, false);
   CacheChildrenInSubtree(this);
 
   // Fire reorder event after the document tree is constructed. Note, since
   // this reorder event is processed by parent document then events targeted to
   // this document may be fired prior to this reorder event. If this is
   // a problem then consider to keep event processing per tab document.
   if (!IsRoot()) {
     nsRefPtr<AccReorderEvent> reorderEvent = new AccReorderEvent(Parent());
@@ -1654,16 +1664,19 @@ DocAccessible::ProcessContentInserted(Ac
         // there is no HTML body element.
       }
 
       // XXX: Invalidate parent-child relations for container accessible and its
       // children because there's no good way to find insertion point of new child
       // accessibles into accessible tree. We need to invalidate children even
       // there's no inserted accessibles in the end because accessible children
       // are created while parent recaches child accessibles.
+      // XXX Group invalidation here may be redundant with invalidation in
+      // UpdateTree.
+      AutoTreeMutation mut(aContainer);
       aContainer->InvalidateChildren();
       CacheChildrenInSubtree(aContainer);
     }
 
     UpdateTree(aContainer, aInsertedContent->ElementAt(idx), true);
   }
 }
 
@@ -1686,16 +1699,17 @@ DocAccessible::UpdateTree(Accessible* aC
     else
       logging::MsgEntry("child accessible: null");
 
     logging::MsgEnd();
   }
 #endif
 
   nsRefPtr<AccReorderEvent> reorderEvent = new AccReorderEvent(aContainer);
+  AutoTreeMutation mut(aContainer);
 
   if (child) {
     updateFlags |= UpdateTreeInternal(child, aIsInsert, reorderEvent);
   } else {
     if (aIsInsert) {
       TreeWalker walker(aContainer, aChildNode, TreeWalker::eWalkCache);
 
       while ((child = walker.NextChild()))
--- a/accessible/html/HTMLImageMapAccessible.cpp
+++ b/accessible/html/HTMLImageMapAccessible.cpp
@@ -80,33 +80,34 @@ HTMLImageMapAccessible::UpdateChildAreas
 {
   nsImageFrame* imageFrame = do_QueryFrame(mContent->GetPrimaryFrame());
 
   // If image map is not initialized yet then we trigger one time more later.
   nsImageMap* imageMapObj = imageFrame->GetExistingImageMap();
   if (!imageMapObj)
     return;
 
-  bool doReorderEvent = false;
+  bool treeChanged = false;
+  AutoTreeMutation mut(this);
   nsRefPtr<AccReorderEvent> reorderEvent = new AccReorderEvent(this);
 
   // Remove areas that are not a valid part of the image map anymore.
   for (int32_t childIdx = mChildren.Length() - 1; childIdx >= 0; childIdx--) {
     Accessible* area = mChildren.ElementAt(childIdx);
     if (area->GetContent()->GetPrimaryFrame())
       continue;
 
     if (aDoFireEvents) {
       nsRefPtr<AccHideEvent> event = new AccHideEvent(area, area->GetContent());
       mDoc->FireDelayedEvent(event);
       reorderEvent->AddSubMutationEvent(event);
-      doReorderEvent = true;
     }
 
     RemoveChild(area);
+    treeChanged = true;
   }
 
   // Insert new areas into the tree.
   uint32_t areaElmCount = imageMapObj->AreaCount();
   for (uint32_t idx = 0; idx < areaElmCount; idx++) {
     nsIContent* areaContent = imageMapObj->GetAreaAt(idx);
 
     Accessible* area = mChildren.SafeElementAt(idx);
@@ -118,24 +119,28 @@ HTMLImageMapAccessible::UpdateChildAreas
         mDoc->UnbindFromDocument(area);
         break;
       }
 
       if (aDoFireEvents) {
         nsRefPtr<AccShowEvent> event = new AccShowEvent(area, areaContent);
         mDoc->FireDelayedEvent(event);
         reorderEvent->AddSubMutationEvent(event);
-        doReorderEvent = true;
       }
+
+      treeChanged = true;
     }
   }
 
   // Fire reorder event if needed.
-  if (doReorderEvent)
+  if (treeChanged && aDoFireEvents)
     mDoc->FireDelayedEvent(reorderEvent);
+
+  if (!treeChanged)
+    mut.mInvalidationRequired = false;
 }
 
 Accessible*
 HTMLImageMapAccessible::GetChildAccessibleFor(const nsINode* aNode) const
 {
   uint32_t length = mChildren.Length();
   for (uint32_t i = 0; i < length; i++) {
     Accessible* area = mChildren[i];