bug 1052122 - derecursify TreeWalker::NextChild r=surkov
authorTrevor Saunders <trev.saunders@gmail.com>
Tue, 12 Aug 2014 02:02:28 -0400
changeset 203920 25a373fa9dbfc5339b448252f3b70d21c23a2a65
parent 203919 ee4dabe0e241fb41344c08f71211c75d56277007
child 203921 4cc20221b0f6ed06f4bc124671047ea08d76581a
push id48776
push usertrev.saunders@gmail.com
push dateFri, 05 Sep 2014 21:19:43 +0000
treeherdermozilla-inbound@25a373fa9dbf [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewerssurkov
bugs1052122
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 1052122 - derecursify TreeWalker::NextChild r=surkov
accessible/base/TreeWalker.cpp
accessible/base/TreeWalker.h
accessible/tests/mochitest/text/test_words.html
--- a/accessible/base/TreeWalker.cpp
+++ b/accessible/base/TreeWalker.cpp
@@ -7,135 +7,104 @@
 
 #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();
+    // XXX We really should never get here, it means we're trying to find an
+    // accessible for a dom node where iterating over its parent's children
+    // doesn't return it. However this sometimes happens when we're asked for
+    // the nearest accessible to place holder content which we ignore.
+    mAnchorNode = parent;
   }
 
   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_
--- a/accessible/tests/mochitest/text/test_words.html
+++ b/accessible/tests/mochitest/text/test_words.html
@@ -87,16 +87,18 @@
       // "Hello. Friend, are you here?!"
       testWordCount("div17", 5, kOk);
       testWordAt("div17", 0, "Hello", kTodo);
       testWordAt("div17", 1, "Friend", kTodo);
       testWordAt("div17", 2, "are", kOk);
       testWordAt("div17", 3, "you", kOk);
       testWordAt("div17", 4, "here", kTodo);
 
+      testWords("input_1", ["foo", "bar"]);
+
       SimpleTest.finish();
     }
 
     SimpleTest.waitForExplicitFinish();
     addA11yLoadEvent(doTest);
   </script>
 </head>
 <body>
@@ -120,10 +122,12 @@
   <div id="div11">3.1416</div>
   <div id="div12">4,261.01</div>
   <div id="div13">カタカナ</div>
   <div id="div14">Peter's car</div>
   <div id="div15">N.A.T.O.</div>
   <div id="div16">3+4*5=23</div>
   <div id="div17">Hello. Friend, are you here?!</div>
   </pre>
+  <input id="input_1" type="text" value="foo bar" placeholder="something or other">
+
 </body>
 </html>