Bug 1249730 - make TreeWalker bi-directional, r=yzen
authorAlexander Surkov <surkov.alexander@gmail.com>
Mon, 07 Mar 2016 16:43:27 -0500
changeset 338010 17a2a03c4fe3cd5e158bf0ad8e9db8b4782668ee
parent 338009 42356eefad43dc866381ae63c1297fc0069a8c3a
child 338011 7f7f0a43f051424dbdc87db33a9947f7b87e8c89
push id12405
push usercku@mozilla.com
push dateTue, 08 Mar 2016 03:35:29 +0000
reviewersyzen
bugs1249730
milestone47.0a1
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).
    */