1 files changed, 331 insertions, 0 deletions
diff --git a/accessible/base/Pivot.cpp b/accessible/base/Pivot.cpp
new file mode 100644
index 0000000000..146d9207cf
--- /dev/null
+++ b/accessible/base/Pivot.cpp
@@ -0,0 +1,331 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * 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/. */
+
+#include "Pivot.h"
+
+#include "AccIterator.h"
+#include "LocalAccessible.h"
+#include "RemoteAccessible.h"
+#include "nsAccUtils.h"
+#include "nsIAccessiblePivot.h"
+
+#include "mozilla/a11y/Accessible.h"
+
+using namespace mozilla;
+using namespace mozilla::a11y;
+
+////////////////////////////////////////////////////////////////////////////////
+// Pivot
+////////////////////////////////////////////////////////////////////////////////
+
+Pivot::Pivot(Accessible* aRoot) : mRoot(aRoot) { MOZ_COUNT_CTOR(Pivot); }
+
+Pivot::~Pivot() { MOZ_COUNT_DTOR(Pivot); }
+
+Accessible* Pivot::AdjustStartPosition(Accessible* aAnchor, PivotRule& aRule,
+                                       uint16_t* aFilterResult) {
+  Accessible* matched = aAnchor;
+  *aFilterResult = aRule.Match(aAnchor);
+
+  if (aAnchor && aAnchor != mRoot) {
+    for (Accessible* temp = aAnchor->Parent(); temp && temp != mRoot;
+         temp = temp->Parent()) {
+      uint16_t filtered = aRule.Match(temp);
+      if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
+        *aFilterResult = filtered;
+        matched = temp;
+      }
+    }
+  }
+
+  return matched;
+}
+
+Accessible* Pivot::SearchBackward(Accessible* aAnchor, PivotRule& aRule,
+                                  bool aSearchCurrent) {
+  // Initial position could be unset, in that case return null.
+  if (!aAnchor) {
+    return nullptr;
+  }
+
+  uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
+
+  Accessible* acc = AdjustStartPosition(aAnchor, aRule, &filtered);
+
+  if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
+    return acc;
+  }
+
+  while (acc && acc != mRoot) {
+    Accessible* parent = acc->Parent();
+#if defined(ANDROID)
+    MOZ_ASSERT(
+        acc->IsLocal() || (acc->IsRemote() && parent->IsRemote()),
+        "Pivot::SearchBackward climbed out of remote subtree in Android!");
+#endif
+    int32_t idxInParent = acc->IndexInParent();
+    while (idxInParent > 0 && parent) {
+      acc = parent->ChildAt(--idxInParent);
+      if (!acc) {
+        continue;
+      }
+
+      filtered = aRule.Match(acc);
+
+      Accessible* lastChild = acc->LastChild();
+      while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
+             lastChild) {
+        parent = acc;
+        acc = lastChild;
+        idxInParent = acc->IndexInParent();
+        filtered = aRule.Match(acc);
+        lastChild = acc->LastChild();
+      }
+
+      if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
+        return acc;
+      }
+    }
+
+    acc = parent;
+    if (!acc) {
+      break;
+    }
+
+    filtered = aRule.Match(acc);
+
+    if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
+      return acc;
+    }
+  }
+
+  return nullptr;
+}
+
+Accessible* Pivot::SearchForward(Accessible* aAnchor, PivotRule& aRule,
+                                 bool aSearchCurrent) {
+  // Initial position could be not set, in that case begin search from root.
+  Accessible* acc = aAnchor ? aAnchor : mRoot;
+
+  uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
+  acc = AdjustStartPosition(acc, aRule, &filtered);
+  if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
+    return acc;
+  }
+
+  while (acc) {
+    Accessible* firstChild = acc->FirstChild();
+    while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
+           firstChild) {
+      acc = firstChild;
+      filtered = aRule.Match(acc);
+
+      if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
+        return acc;
+      }
+      firstChild = acc->FirstChild();
+    }
+
+    Accessible* sibling = nullptr;
+    Accessible* temp = acc;
+    do {
+      if (temp == mRoot) {
+        break;
+      }
+
+      sibling = temp->NextSibling();
+
+      if (sibling) {
+        break;
+      }
+      temp = temp->Parent();
+#if defined(ANDROID)
+      MOZ_ASSERT(
+          acc->IsLocal() || (acc->IsRemote() && temp->IsRemote()),
+          "Pivot::SearchForward climbed out of remote subtree in Android!");
+#endif
+
+    } while (temp);
+
+    if (!sibling) {
+      break;
+    }
+
+    acc = sibling;
+    filtered = aRule.Match(acc);
+    if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
+      return acc;
+    }
+  }
+
+  return nullptr;
+}
+
+Accessible* Pivot::Next(Accessible* aAnchor, PivotRule& aRule,
+                        bool aIncludeStart) {
+  return SearchForward(aAnchor, aRule, aIncludeStart);
+}
+
+Accessible* Pivot::Prev(Accessible* aAnchor, PivotRule& aRule,
+                        bool aIncludeStart) {
+  return SearchBackward(aAnchor, aRule, aIncludeStart);
+}
+
+Accessible* Pivot::First(PivotRule& aRule) {
+  return SearchForward(mRoot, aRule, true);
+}
+
+Accessible* Pivot::Last(PivotRule& aRule) {
+  Accessible* lastAcc = mRoot;
+
+  // First go to the last accessible in pre-order
+  while (lastAcc && lastAcc->HasChildren()) {
+    lastAcc = lastAcc->LastChild();
+  }
+
+  // Search backwards from last accessible and find the last occurrence in the
+  // doc
+  return SearchBackward(lastAcc, aRule, true);
+}
+
+Accessible* Pivot::AtPoint(int32_t aX, int32_t aY, PivotRule& aRule) {
+  Accessible* match = nullptr;
+  Accessible* child =
+      mRoot ? mRoot->ChildAtPoint(aX, aY,
+                                  Accessible::EWhichChildAtPoint::DeepestChild)
+            : nullptr;
+  while (child && (mRoot != child)) {
+    uint16_t filtered = aRule.Match(child);
+
+    // Ignore any matching nodes that were below this one
+    if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
+      match = nullptr;
+    }
+
+    // Match if no node below this is a match
+    if ((filtered & nsIAccessibleTraversalRule::FILTER_MATCH) && !match) {
+      LayoutDeviceIntRect childRect = child->IsLocal()
+                                          ? child->AsLocal()->Bounds()
+                                          : child->AsRemote()->Bounds();
+      // Double-check child's bounds since the deepest child may have been out
+      // of bounds. This assures we don't return a false positive.
+      if (childRect.Contains(aX, aY)) {
+        match = child;
+      }
+    }
+
+    child = child->Parent();
+  }
+
+  return match;
+}
+
+// Role Rule
+
+PivotRoleRule::PivotRoleRule(mozilla::a11y::role aRole)
+    : mRole(aRole), mDirectDescendantsFrom(nullptr) {}
+
+PivotRoleRule::PivotRoleRule(mozilla::a11y::role aRole,
+                             Accessible* aDirectDescendantsFrom)
+    : mRole(aRole), mDirectDescendantsFrom(aDirectDescendantsFrom) {}
+
+uint16_t PivotRoleRule::Match(Accessible* aAcc) {
+  uint16_t result = nsIAccessibleTraversalRule::FILTER_IGNORE;
+
+  if (nsAccUtils::MustPrune(aAcc)) {
+    result |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  if (mDirectDescendantsFrom && (aAcc != mDirectDescendantsFrom)) {
+    // If we've specified mDirectDescendantsFrom, we should ignore
+    // non-direct descendants of from the specified AoP. Because
+    // pivot performs a preorder traversal, the first aAcc
+    // object(s) that don't equal mDirectDescendantsFrom will be
+    // mDirectDescendantsFrom's children. We'll process them, but ignore
+    // their subtrees thereby processing direct descendants of
+    // mDirectDescendantsFrom only.
+    result |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  if (aAcc && aAcc->Role() == mRole) {
+    result |= nsIAccessibleTraversalRule::FILTER_MATCH;
+  }
+
+  return result;
+}
+
+// State Rule
+
+PivotStateRule::PivotStateRule(uint64_t aState) : mState(aState) {}
+
+uint16_t PivotStateRule::Match(Accessible* aAcc) {
+  uint16_t result = nsIAccessibleTraversalRule::FILTER_IGNORE;
+
+  if (nsAccUtils::MustPrune(aAcc)) {
+    result |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  if (aAcc && (aAcc->State() & mState)) {
+    result = nsIAccessibleTraversalRule::FILTER_MATCH |
+             nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  return result;
+}
+
+// LocalAccInSameDocRule
+
+uint16_t LocalAccInSameDocRule::Match(Accessible* aAcc) {
+  LocalAccessible* acc = aAcc ? aAcc->AsLocal() : nullptr;
+  if (!acc) {
+    return nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+  if (acc->IsOuterDoc()) {
+    return nsIAccessibleTraversalRule::FILTER_MATCH |
+           nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+  return nsIAccessibleTraversalRule::FILTER_MATCH;
+}
+
+// Radio Button Name Rule
+
+PivotRadioNameRule::PivotRadioNameRule(const nsString& aName) : mName(aName) {}
+
+uint16_t PivotRadioNameRule::Match(Accessible* aAcc) {
+  uint16_t result = nsIAccessibleTraversalRule::FILTER_IGNORE;
+  RemoteAccessible* remote = aAcc->AsRemote();
+  if (!remote) {
+    // We need the cache to be able to fetch the name attribute below.
+    return result;
+  }
+
+  if (nsAccUtils::MustPrune(aAcc) || aAcc->IsOuterDoc()) {
+    result |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  if (remote->IsHTMLRadioButton()) {
+    nsString currName = remote->GetCachedHTMLNameAttribute();
+    if (!currName.IsEmpty() && mName.Equals(currName)) {
+      result |= nsIAccessibleTraversalRule::FILTER_MATCH;
+    }
+  }
+
+  return result;
+}
+
+// MustPruneSameDocRule
+
+uint16_t MustPruneSameDocRule::Match(Accessible* aAcc) {
+  if (!aAcc) {
+    return nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  if (nsAccUtils::MustPrune(aAcc) || aAcc->IsOuterDoc()) {
+    return nsIAccessibleTraversalRule::FILTER_MATCH |
+           nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
+  }
+
+  return nsIAccessibleTraversalRule::FILTER_MATCH;
+}