bug 1052122 - derecursify TreeWalker::NextChild r=surkov
authorTrevor Saunders <trev.saunders@gmail.com>
Tue, 12 Aug 2014 02:02:28 -0400
changeset 223898 a7840102579bb11fa60237349236118d38adb7c2
parent 223897 b9de6514b9940f66ae6b07157216f6222cb91bca
child 223899 7beceadb18b41f4ce05c3dba72f50b3889aca519
push id3979
push userraliiev@mozilla.com
push dateMon, 13 Oct 2014 16:35:44 +0000
treeherdermozilla-beta@30f2cc610691 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssurkov
bugs1052122
milestone34.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 1052122 - derecursify TreeWalker::NextChild r=surkov
accessible/base/TreeWalker.cpp
accessible/base/TreeWalker.h
--- a/accessible/base/TreeWalker.cpp
+++ b/accessible/base/TreeWalker.cpp
@@ -7,135 +7,98 @@
 
 #include "Accessible.h"
 #include "nsAccessibilityService.h"
 #include "DocAccessible.h"
 
 #include "mozilla/dom/ChildIterator.h"
 #include "mozilla/dom/Element.h"
 
+using namespace mozilla;
 using namespace mozilla::a11y;
 
 ////////////////////////////////////////////////////////////////////////////////
-// WalkState
-////////////////////////////////////////////////////////////////////////////////
-
-namespace mozilla {
-namespace a11y {
-
-struct WalkState
-{
-  WalkState(nsIContent *aContent, uint32_t aFilter) :
-    content(aContent), prevState(nullptr), iter(aContent, aFilter) {}
-
-  nsCOMPtr<nsIContent> content;
-  WalkState *prevState;
-  dom::AllChildrenIterator iter;
-};
-
-} // namespace a11y
-} // namespace mozilla
-
-////////////////////////////////////////////////////////////////////////////////
 // TreeWalker
 ////////////////////////////////////////////////////////////////////////////////
 
 TreeWalker::
   TreeWalker(Accessible* aContext, nsIContent* aContent, uint32_t aFlags) :
-  mDoc(aContext->Document()), mContext(aContext),
-  mFlags(aFlags), mState(nullptr)
+  mDoc(aContext->Document()), mContext(aContext), mAnchorNode(aContent),
+  mFlags(aFlags)
 {
   NS_ASSERTION(aContent, "No node for the accessible tree walker!");
 
   mChildFilter = mContext->CanHaveAnonChildren() ?
     nsIContent::eAllChildren : nsIContent::eAllButXBL;
   mChildFilter |= nsIContent::eSkipPlaceholderContent;
 
   if (aContent)
-    mState = new WalkState(aContent, mChildFilter);
+    PushState(aContent);
 
   MOZ_COUNT_CTOR(TreeWalker);
 }
 
 TreeWalker::~TreeWalker()
 {
-  // Clear state stack from memory
-  while (mState)
-    PopState();
-
   MOZ_COUNT_DTOR(TreeWalker);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // TreeWalker: private
 
 Accessible*
-TreeWalker::NextChildInternal(bool aNoWalkUp)
+TreeWalker::NextChild()
 {
-  if (!mState || !mState->content)
+  if (mStateStack.IsEmpty())
     return nullptr;
 
-  while (nsIContent* childNode = mState->iter.GetNextChild()) {
-    bool isSubtreeHidden = false;
-    Accessible* accessible = mFlags & eWalkCache ?
-      mDoc->GetAccessible(childNode) :
-      GetAccService()->GetOrCreateAccessible(childNode, mContext,
-                                             &isSubtreeHidden);
+  dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
+  while (top) {
+    while (nsIContent* childNode = top->GetNextChild()) {
+      bool isSubtreeHidden = false;
+      Accessible* accessible = mFlags & eWalkCache ?
+        mDoc->GetAccessible(childNode) :
+        GetAccService()->GetOrCreateAccessible(childNode, mContext,
+                                               &isSubtreeHidden);
 
-    if (accessible)
-      return accessible;
-
-    // Walk down into subtree to find accessibles.
-    if (!isSubtreeHidden && childNode->IsElement()) {
-      PushState(childNode);
-      accessible = NextChildInternal(true);
       if (accessible)
         return accessible;
-    }
-  }
 
-  // No more children, get back to the parent.
-  nsIContent* anchorNode = mState->content;
-  PopState();
-  if (aNoWalkUp)
-    return nullptr;
+      // Walk down into subtree to find accessibles.
+      if (!isSubtreeHidden && childNode->IsElement())
+        top = PushState(childNode);
+    }
 
-  if (mState)
-    return NextChildInternal(false);
+    top = PopState();
+  }
 
   // If we traversed the whole subtree of the anchor node. Move to next node
   // relative anchor node within the context subtree if possible.
   if (mFlags != eWalkContextTree)
     return nullptr;
 
-  while (anchorNode != mContext->GetNode()) {
-    nsINode* parentNode = anchorNode->GetFlattenedTreeParent();
+  nsINode* contextNode = mContext->GetNode();
+  while (mAnchorNode != contextNode) {
+    nsINode* parentNode = mAnchorNode->GetFlattenedTreeParent();
     if (!parentNode || !parentNode->IsElement())
       return nullptr;
 
-    PushState(parentNode->AsElement());
-    while (nsIContent* childNode = mState->iter.GetNextChild()) {
-      if (childNode == anchorNode)
-        return NextChildInternal(false);
+    nsIContent* parent = parentNode->AsElement();
+    top = mStateStack.AppendElement(dom::AllChildrenIterator(parent,
+                                                             mChildFilter));
+    while (nsIContent* childNode = top->GetNextChild()) {
+      if (childNode == mAnchorNode) {
+        mAnchorNode = parent;
+        return NextChild();
+      }
     }
-    PopState();
-
-    anchorNode = parentNode->AsElement();
   }
 
   return nullptr;
 }
 
-void
+dom::AllChildrenIterator*
 TreeWalker::PopState()
 {
-  WalkState* prevToLastState = mState->prevState;
-  delete mState;
-  mState = prevToLastState;
+  size_t length = mStateStack.Length();
+  mStateStack.RemoveElementAt(length - 1);
+  return mStateStack.IsEmpty() ? nullptr : &mStateStack[mStateStack.Length() - 1];
 }
-
-void
-TreeWalker::PushState(nsIContent* aContent)
-{
-  WalkState* nextToLastState = new WalkState(aContent, mChildFilter);
-  nextToLastState->prevState = mState;
-  mState = nextToLastState;
-}
--- a/accessible/base/TreeWalker.h
+++ b/accessible/base/TreeWalker.h
@@ -3,27 +3,27 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #ifndef mozilla_a11y_TreeWalker_h_
 #define mozilla_a11y_TreeWalker_h_
 
 #include "mozilla/Attributes.h"
 #include <stdint.h>
+#include "mozilla/dom/ChildIterator.h"
+#include "nsCOMPtr.h"
 
 class nsIContent;
 
 namespace mozilla {
 namespace a11y {
 
 class Accessible;
 class DocAccessible;
 
-struct WalkState;
-
 /**
  * This class is used to walk the DOM tree to create accessible tree.
  */
 class TreeWalker MOZ_FINAL
 {
 public:
   enum {
     // used to walk the existing tree of the given node
@@ -45,51 +45,44 @@ public:
 
   /**
    * Return the next child accessible.
    *
    * @note Returned accessible is bound to the document, if the accessible is
    *       rejected during tree creation then the caller should be unbind it
    *       from the document.
    */
-  Accessible* NextChild()
-  {
-    return NextChildInternal(false);
-  }
+  Accessible* NextChild();
 
 private:
   TreeWalker();
   TreeWalker(const TreeWalker&);
   TreeWalker& operator =(const TreeWalker&);
 
   /**
-   * Return the next child accessible.
-   *
-   * @param  aNoWalkUp  [in] specifies the walk direction, true means we
-   *                     shouldn't go up through the tree if we failed find
-   *                     accessible children.
-   */
-  Accessible* NextChildInternal(bool aNoWalkUp);
-
-  /**
    * Create new state for the given node and push it on top of stack.
    *
    * @note State stack is used to navigate up/down the DOM subtree during
    *        accessible children search.
    */
-  void PushState(nsIContent* aNode);
+  dom::AllChildrenIterator* PushState(nsIContent* aContent)
+  {
+    return mStateStack.AppendElement(dom::AllChildrenIterator(aContent,
+                                                              mChildFilter));
+  }
 
   /**
    * Pop state from stack.
    */
-  void PopState();
+  dom::AllChildrenIterator* PopState();
 
   DocAccessible* mDoc;
   Accessible* mContext;
+  nsIContent* mAnchorNode;
+  nsAutoTArray<dom::AllChildrenIterator, 20> mStateStack;
   int32_t mChildFilter;
   uint32_t mFlags;
-  WalkState* mState;
 };
 
 } // namespace a11y
 } // namespace mozilla
 
 #endif // mozilla_a11y_TreeWalker_h_