Bug 1249730 - make TreeWalker bi-directional, r=yzen
authorAlexander Surkov <surkov.alexander@gmail.com>
Mon, 07 Mar 2016 16:43:27 -0500
changeset 327010 17a2a03c4fe3cd5e158bf0ad8e9db8b4782668ee
parent 327009 42356eefad43dc866381ae63c1297fc0069a8c3a
child 327011 7f7f0a43f051424dbdc87db33a9947f7b87e8c89
push id1146
push userCallek@gmail.com
push dateMon, 25 Jul 2016 16:35:44 +0000
treeherdermozilla-release@a55778f9cd5a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersyzen
bugs1249730
milestone47.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 1249730 - make TreeWalker bi-directional, r=yzen
accessible/base/TreeWalker.cpp
accessible/base/TreeWalker.h
accessible/generic/DocAccessible.h
--- a/accessible/base/TreeWalker.cpp
+++ b/accessible/base/TreeWalker.cpp
@@ -19,62 +19,79 @@ using namespace mozilla::a11y;
 ////////////////////////////////////////////////////////////////////////////////
 // TreeWalker
 ////////////////////////////////////////////////////////////////////////////////
 
 TreeWalker::
   TreeWalker(Accessible* aContext) :
   mDoc(aContext->Document()), mContext(aContext), mAnchorNode(nullptr),
   mARIAOwnsIdx(0),
-  mChildFilter(nsIContent::eSkipPlaceholderContent), mFlags(0)
+  mChildFilter(nsIContent::eSkipPlaceholderContent), mFlags(0),
+  mPhase(eAtStart)
 {
   mChildFilter |= mContext->NoXBLKids() ?
     nsIContent::eAllButXBL : nsIContent::eAllChildren;
 
   mAnchorNode = mContext->IsDoc() ?
     mDoc->DocumentNode()->GetRootElement() : mContext->GetContent();
 
-  if (mAnchorNode) {
-    PushState(mAnchorNode);
-  }
-
   MOZ_COUNT_CTOR(TreeWalker);
 }
 
 TreeWalker::
   TreeWalker(Accessible* aContext, nsIContent* aAnchorNode, uint32_t aFlags) :
   mDoc(aContext->Document()), mContext(aContext), mAnchorNode(aAnchorNode),
   mARIAOwnsIdx(0),
-  mChildFilter(nsIContent::eSkipPlaceholderContent), mFlags(aFlags)
+  mChildFilter(nsIContent::eSkipPlaceholderContent), mFlags(aFlags),
+  mPhase(eAtStart)
 {
   MOZ_ASSERT(aAnchorNode, "No anchor node for the accessible tree walker");
   MOZ_ASSERT(mDoc->GetAccessibleOrContainer(aAnchorNode) == mContext,
              "Unexpected anchor node was given");
 
   mChildFilter |= mContext->NoXBLKids() ?
     nsIContent::eAllButXBL : nsIContent::eAllChildren;
 
-  PushState(aAnchorNode);
-
   MOZ_COUNT_CTOR(TreeWalker);
 }
 
 TreeWalker::~TreeWalker()
 {
   MOZ_COUNT_DTOR(TreeWalker);
 }
 
 ////////////////////////////////////////////////////////////////////////////////
 // TreeWalker: private
 
 Accessible*
 TreeWalker::Next()
 {
   if (mStateStack.IsEmpty()) {
-    return mDoc->ARIAOwnedAt(mContext, mARIAOwnsIdx++);
+    if (mPhase == eAtEnd) {
+      return nullptr;
+    }
+
+    if (mPhase == eAtDOM || mPhase == eAtARIAOwns) {
+      mPhase = eAtARIAOwns;
+      Accessible* child = mDoc->ARIAOwnedAt(mContext, mARIAOwnsIdx);
+      if (child) {
+        mARIAOwnsIdx++;
+        return child;
+      }
+      mPhase = eAtEnd;
+      return nullptr;
+    }
+
+    if (!mAnchorNode) {
+      mPhase = eAtEnd;
+      return nullptr;
+    }
+
+    mPhase = eAtDOM;
+    PushState(mAnchorNode, true);
   }
 
   dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
   while (top) {
     while (nsIContent* childNode = top->GetNextChild()) {
       bool skipSubtree = false;
       Accessible* child = nullptr;
       if (mFlags & eWalkCache) {
@@ -91,17 +108,17 @@ TreeWalker::Next()
         if (child->IsRelocated()) {
           continue;
         }
         return child;
       }
 
       // Walk down into subtree to find accessibles.
       if (!skipSubtree && childNode->IsElement()) {
-        top = PushState(childNode);
+        top = PushState(childNode, true);
       }
     }
     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)
@@ -109,31 +126,113 @@ TreeWalker::Next()
 
   nsINode* contextNode = mContext->GetNode();
   while (mAnchorNode != contextNode) {
     nsINode* parentNode = mAnchorNode->GetFlattenedTreeParent();
     if (!parentNode || !parentNode->IsElement())
       return nullptr;
 
     nsIContent* parent = parentNode->AsElement();
-    top = PushState(parent);
+    top = PushState(parent, true);
     if (top->Seek(mAnchorNode)) {
       mAnchorNode = parent;
       return Next();
     }
 
     // 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 Next();
 }
 
+Accessible*
+TreeWalker::Prev()
+{
+  if (mStateStack.IsEmpty()) {
+    if (mPhase == eAtStart || mPhase == eAtDOM) {
+      mPhase = eAtStart;
+      return nullptr;
+    }
+
+    if (mPhase == eAtEnd) {
+      mARIAOwnsIdx = mDoc->ARIAOwnedCount(mContext);
+      mPhase = eAtARIAOwns;
+    }
+
+    if (mPhase == eAtARIAOwns) {
+      if (mARIAOwnsIdx > 0) {
+        return mDoc->ARIAOwnedAt(mContext, --mARIAOwnsIdx);
+      }
+
+      if (!mAnchorNode) {
+        mPhase = eAtStart;
+        return nullptr;
+      }
+
+      mPhase = eAtDOM;
+      PushState(mAnchorNode, false);
+    }
+  }
+
+  dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
+  while (top) {
+    while (nsIContent* childNode = top->GetPreviousChild()) {
+      bool skipSubtree = false;
+
+      // No accessible creation on the way back.
+      Accessible* child = mDoc->GetAccessible(childNode);
+
+      // Ignore the accessible and its subtree if it was repositioned by means of
+      // aria-owns.
+      if (child) {
+        if (child->IsRelocated()) {
+          continue;
+        }
+        return child;
+      }
+
+      // Walk down into subtree to find accessibles.
+      if (!skipSubtree && childNode->IsElement()) {
+        top = PushState(childNode, true);
+      }
+    }
+    top = PopState();
+  }
+
+  // Move to a previous node relative the anchor node within the context
+  // subtree if asked.
+  if (mFlags != eWalkContextTree) {
+    mPhase = eAtStart;
+    return nullptr;
+  }
+
+  nsINode* contextNode = mContext->GetNode();
+  while (mAnchorNode != contextNode) {
+    nsINode* parentNode = mAnchorNode->GetFlattenedTreeParent();
+    if (!parentNode || !parentNode->IsElement()) {
+      return nullptr;
+    }
+
+    nsIContent* parent = parentNode->AsElement();
+    top = PushState(parent, true);
+    if (top->Seek(mAnchorNode)) {
+      mAnchorNode = parent;
+      return Prev();
+    }
+
+    mAnchorNode = parent;
+  }
+
+  mPhase = eAtStart;
+  return nullptr;
+}
+
 dom::AllChildrenIterator*
 TreeWalker::PopState()
 {
   size_t length = mStateStack.Length();
   mStateStack.RemoveElementAt(length - 1);
   return mStateStack.IsEmpty() ? nullptr : &mStateStack[mStateStack.Length() - 1];
 }
--- a/accessible/base/TreeWalker.h
+++ b/accessible/base/TreeWalker.h
@@ -45,53 +45,63 @@ public:
    * @param aAnchorNode [in] the node the search will be prepared relative to
    * @param aFlags   [in] flags (see enum above)
    */
   TreeWalker(Accessible* aContext, nsIContent* aAnchorNode, uint32_t aFlags = 0);
 
   ~TreeWalker();
 
   /**
-   * Return the next accessible.
+   * Return the next/prev 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* Next();
+  Accessible* Prev();
 
 private:
   TreeWalker();
   TreeWalker(const TreeWalker&);
   TreeWalker& operator =(const TreeWalker&);
 
   /**
    * 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.
    */
-  dom::AllChildrenIterator* PushState(nsIContent* aContent)
+  dom::AllChildrenIterator* PushState(nsIContent* aContent,
+                                      bool aStartAtBeginning)
   {
     return mStateStack.AppendElement(
-      dom::AllChildrenIterator(aContent, mChildFilter));
+      dom::AllChildrenIterator(aContent, mChildFilter, aStartAtBeginning));
   }
 
   /**
    * Pop state from stack.
    */
   dom::AllChildrenIterator* PopState();
 
   DocAccessible* mDoc;
   Accessible* mContext;
   nsIContent* mAnchorNode;
 
   AutoTArray<dom::AllChildrenIterator, 20> mStateStack;
   uint32_t mARIAOwnsIdx;
 
   int32_t mChildFilter;
   uint32_t mFlags;
+
+  enum Phase {
+    eAtStart,
+    eAtDOM,
+    eAtARIAOwns,
+    eAtEnd
+  };
+  Phase mPhase;
 };
 
 } // namespace a11y
 } // namespace mozilla
 
 #endif // mozilla_a11y_TreeWalker_h_
--- a/accessible/generic/DocAccessible.h
+++ b/accessible/generic/DocAccessible.h
@@ -286,16 +286,21 @@ public:
   Accessible* ARIAOwnedAt(Accessible* aParent, uint32_t aIndex) const
   {
     nsTArray<RefPtr<Accessible> >* children = mARIAOwnsHash.Get(aParent);
     if (children) {
       return children->SafeElementAt(aIndex);
     }
     return nullptr;
   }
+  uint32_t ARIAOwnedCount(Accessible* aParent) const
+  {
+    nsTArray<RefPtr<Accessible> >* children = mARIAOwnsHash.Get(aParent);
+    return children ? children->Length() : 0;
+  }
 
   /**
    * Return true if the given ID is referred by relation attribute.
    *
    * @note Different elements may share the same ID if they are hosted inside
    *       XBL bindings. Be careful the result of this method may be  senseless
    *       while it's called for XUL elements (where XBL is used widely).
    */