michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* vim: set ts=2 et sw=2 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include "nsAccessiblePivot.h"
michael@0: 
michael@0: #include "HyperTextAccessible.h"
michael@0: #include "nsAccUtils.h"
michael@0: #include "States.h"
michael@0: 
michael@0: using namespace mozilla::a11y;
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * An object that stores a given traversal rule during 
michael@0:  */
michael@0: class RuleCache
michael@0: {
michael@0: public:
michael@0:   RuleCache(nsIAccessibleTraversalRule* aRule) : mRule(aRule),
michael@0:                                                  mAcceptRoles(nullptr) { }
michael@0:   ~RuleCache () {
michael@0:     if (mAcceptRoles)
michael@0:       nsMemory::Free(mAcceptRoles);
michael@0:   }
michael@0: 
michael@0:   nsresult ApplyFilter(Accessible* aAccessible, uint16_t* aResult);
michael@0: 
michael@0: private:
michael@0:   nsCOMPtr<nsIAccessibleTraversalRule> mRule;
michael@0:   uint32_t* mAcceptRoles;
michael@0:   uint32_t mAcceptRolesLength;
michael@0:   uint32_t mPreFilter;
michael@0: };
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: // nsAccessiblePivot
michael@0: 
michael@0: nsAccessiblePivot::nsAccessiblePivot(Accessible* aRoot) :
michael@0:   mRoot(aRoot), mModalRoot(nullptr), mPosition(nullptr),
michael@0:   mStartOffset(-1), mEndOffset(-1)
michael@0: {
michael@0:   NS_ASSERTION(aRoot, "A root accessible is required");
michael@0: }
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: // nsISupports
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTION(nsAccessiblePivot, mRoot, mPosition, mObservers)
michael@0: 
michael@0: NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsAccessiblePivot)
michael@0:   NS_INTERFACE_MAP_ENTRY(nsIAccessiblePivot)
michael@0:   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIAccessiblePivot)
michael@0: NS_INTERFACE_MAP_END
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTING_ADDREF(nsAccessiblePivot)
michael@0: NS_IMPL_CYCLE_COLLECTING_RELEASE(nsAccessiblePivot)
michael@0: 
michael@0: ////////////////////////////////////////////////////////////////////////////////
michael@0: // nsIAccessiblePivot
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::GetRoot(nsIAccessible** aRoot)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aRoot);
michael@0: 
michael@0:   NS_IF_ADDREF(*aRoot = mRoot);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::GetPosition(nsIAccessible** aPosition)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aPosition);
michael@0: 
michael@0:   NS_IF_ADDREF(*aPosition = mPosition);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::SetPosition(nsIAccessible* aPosition)
michael@0: {
michael@0:   nsRefPtr<Accessible> secondPosition;
michael@0: 
michael@0:   if (aPosition) {
michael@0:     secondPosition = do_QueryObject(aPosition);
michael@0:     if (!secondPosition || !IsDescendantOf(secondPosition, GetActiveRoot()))
michael@0:       return NS_ERROR_INVALID_ARG;
michael@0:   }
michael@0: 
michael@0:   // Swap old position with new position, saves us an AddRef/Release.
michael@0:   mPosition.swap(secondPosition);
michael@0:   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
michael@0:   mStartOffset = mEndOffset = -1;
michael@0:   NotifyOfPivotChange(secondPosition, oldStart, oldEnd,
michael@0:                       nsIAccessiblePivot::REASON_NONE);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::GetModalRoot(nsIAccessible** aModalRoot)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aModalRoot);
michael@0: 
michael@0:   NS_IF_ADDREF(*aModalRoot = mModalRoot);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::SetModalRoot(nsIAccessible* aModalRoot)
michael@0: {
michael@0:   nsRefPtr<Accessible> modalRoot;
michael@0: 
michael@0:   if (aModalRoot) {
michael@0:     modalRoot = do_QueryObject(aModalRoot);
michael@0:     if (!modalRoot || !IsDescendantOf(modalRoot, mRoot))
michael@0:       return NS_ERROR_INVALID_ARG;
michael@0:   }
michael@0: 
michael@0:   mModalRoot.swap(modalRoot);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::GetStartOffset(int32_t* aStartOffset)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aStartOffset);
michael@0: 
michael@0:   *aStartOffset = mStartOffset;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::GetEndOffset(int32_t* aEndOffset)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aEndOffset);
michael@0: 
michael@0:   *aEndOffset = mEndOffset;
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::SetTextRange(nsIAccessibleText* aTextAccessible,
michael@0:                                 int32_t aStartOffset, int32_t aEndOffset)
michael@0: {
michael@0:   NS_ENSURE_ARG(aTextAccessible);
michael@0: 
michael@0:   // Check that start offset is smaller than end offset, and that if a value is
michael@0:   // smaller than 0, both should be -1.
michael@0:   NS_ENSURE_TRUE(aStartOffset <= aEndOffset &&
michael@0:                  (aStartOffset >= 0 || (aStartOffset != -1 && aEndOffset != -1)),
michael@0:                  NS_ERROR_INVALID_ARG);
michael@0: 
michael@0:   nsRefPtr<Accessible> acc(do_QueryObject(aTextAccessible));
michael@0:   if (!acc)
michael@0:     return NS_ERROR_INVALID_ARG;
michael@0: 
michael@0:   HyperTextAccessible* newPosition = acc->AsHyperText();
michael@0:   if (!newPosition || !IsDescendantOf(newPosition, GetActiveRoot()))
michael@0:     return NS_ERROR_INVALID_ARG;
michael@0: 
michael@0:   // Make sure the given offsets don't exceed the character count.
michael@0:   int32_t charCount = newPosition->CharacterCount();
michael@0: 
michael@0:   if (aEndOffset > charCount)
michael@0:     return NS_ERROR_FAILURE;
michael@0: 
michael@0:   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
michael@0:   mStartOffset = aStartOffset;
michael@0:   mEndOffset = aEndOffset;
michael@0: 
michael@0:   nsRefPtr<Accessible> oldPosition = mPosition.forget();
michael@0:   mPosition = newPosition;
michael@0: 
michael@0:   NotifyOfPivotChange(oldPosition, oldStart, oldEnd,
michael@0:                       nsIAccessiblePivot::REASON_TEXT);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: // Traversal functions
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MoveNext(nsIAccessibleTraversalRule* aRule,
michael@0:                             nsIAccessible* aAnchor, bool aIncludeStart,
michael@0:                             uint8_t aArgc, bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0:   NS_ENSURE_ARG(aRule);
michael@0: 
michael@0:   *aResult = false;
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   nsRefPtr<Accessible> anchor =
michael@0:     (aArgc > 0) ? do_QueryObject(aAnchor) : mPosition;
michael@0:   if (anchor && (anchor->IsDefunct() || !IsDescendantOf(anchor, root)))
michael@0:     return NS_ERROR_NOT_IN_TREE;
michael@0: 
michael@0:   nsresult rv = NS_OK;
michael@0:   Accessible* accessible =
michael@0:     SearchForward(anchor, aRule, (aArgc > 1) ? aIncludeStart : false, &rv);
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   if (accessible)
michael@0:     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_NEXT);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MovePrevious(nsIAccessibleTraversalRule* aRule,
michael@0:                                 nsIAccessible* aAnchor,
michael@0:                                 bool aIncludeStart,
michael@0:                                 uint8_t aArgc, bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0:   NS_ENSURE_ARG(aRule);
michael@0: 
michael@0:   *aResult = false;
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   nsRefPtr<Accessible> anchor =
michael@0:     (aArgc > 0) ? do_QueryObject(aAnchor) : mPosition;
michael@0:   if (anchor && (anchor->IsDefunct() || !IsDescendantOf(anchor, root)))
michael@0:     return NS_ERROR_NOT_IN_TREE;
michael@0: 
michael@0:   nsresult rv = NS_OK;
michael@0:   Accessible* accessible =
michael@0:     SearchBackward(anchor, aRule, (aArgc > 1) ? aIncludeStart : false, &rv);
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   if (accessible)
michael@0:     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_PREV);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MoveFirst(nsIAccessibleTraversalRule* aRule, bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0:   NS_ENSURE_ARG(aRule);
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
michael@0: 
michael@0:   nsresult rv = NS_OK;
michael@0:   Accessible* accessible = SearchForward(root, aRule, true, &rv);
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   if (accessible)
michael@0:     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_FIRST);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MoveLast(nsIAccessibleTraversalRule* aRule,
michael@0:                             bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0:   NS_ENSURE_ARG(aRule);
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
michael@0: 
michael@0:   *aResult = false;
michael@0:   nsresult rv = NS_OK;
michael@0:   Accessible* lastAccessible = root;
michael@0:   Accessible* accessible = nullptr;
michael@0: 
michael@0:   // First go to the last accessible in pre-order
michael@0:   while (lastAccessible->HasChildren())
michael@0:     lastAccessible = lastAccessible->LastChild();
michael@0: 
michael@0:   // Search backwards from last accessible and find the last occurrence in the doc
michael@0:   accessible = SearchBackward(lastAccessible, aRule, true, &rv);
michael@0:   NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:   if (accessible)
michael@0:     *aResult = MovePivotInternal(accessible, nsAccessiblePivot::REASON_LAST);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MoveNextByText(TextBoundaryType aBoundary, bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0: 
michael@0:   *aResult = false;
michael@0: 
michael@0:   int32_t tempStart = mStartOffset, tempEnd = mEndOffset;
michael@0:   Accessible* tempPosition = mPosition;
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   while (true) {
michael@0:     Accessible* curPosition = tempPosition;
michael@0:     HyperTextAccessible* text = nullptr;
michael@0:     // Find the nearest text node using a preorder traversal starting from
michael@0:     // the current node.
michael@0:     if (!(text = tempPosition->AsHyperText())) {
michael@0:       text = SearchForText(tempPosition, false);
michael@0:       if (!text)
michael@0:         return NS_OK;
michael@0:       if (text != curPosition)
michael@0:         tempStart = tempEnd = -1;
michael@0:       tempPosition = text;
michael@0:     }
michael@0: 
michael@0:     // If the search led to the parent of the node we started on (e.g. when
michael@0:     // starting on a text leaf), start the text movement from the end of that
michael@0:     // node, otherwise we just default to 0.
michael@0:     if (tempEnd == -1)
michael@0:       tempEnd = text == curPosition->Parent() ?
michael@0:                 text->GetChildOffset(curPosition) : 0;
michael@0: 
michael@0:     // If there's no more text on the current node, try to find the next text
michael@0:     // node; if there isn't one, bail out.
michael@0:     if (tempEnd == text->CharacterCount()) {
michael@0:       if (tempPosition == root)
michael@0:         return NS_OK;
michael@0: 
michael@0:       // If we're currently sitting on a link, try move to either the next
michael@0:       // sibling or the parent, whichever is closer to the current end
michael@0:       // offset. Otherwise, do a forward search for the next node to land on
michael@0:       // (we don't do this in the first case because we don't want to go to the
michael@0:       // subtree).
michael@0:       Accessible* sibling = tempPosition->NextSibling();
michael@0:       if (tempPosition->IsLink()) {
michael@0:         if (sibling && sibling->IsLink()) {
michael@0:           tempStart = tempEnd = -1;
michael@0:           tempPosition = sibling;
michael@0:         } else {
michael@0:           tempStart = tempPosition->StartOffset();
michael@0:           tempEnd = tempPosition->EndOffset();
michael@0:           tempPosition = tempPosition->Parent();
michael@0:         }
michael@0:       } else {
michael@0:         tempPosition = SearchForText(tempPosition, false);
michael@0:         if (!tempPosition)
michael@0:           return NS_OK;
michael@0:         tempStart = tempEnd = -1;
michael@0:       }
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     AccessibleTextBoundary startBoundary, endBoundary;
michael@0:     switch (aBoundary) {
michael@0:       case CHAR_BOUNDARY:
michael@0:         startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
michael@0:         endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
michael@0:         break;
michael@0:       case WORD_BOUNDARY:
michael@0:         startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
michael@0:         endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
michael@0:         break;
michael@0:       default:
michael@0:         return NS_ERROR_INVALID_ARG;
michael@0:     }
michael@0: 
michael@0:     nsAutoString unusedText;
michael@0:     int32_t newStart = 0, newEnd = 0, currentEnd = tempEnd;
michael@0:     text->TextAtOffset(tempEnd, endBoundary, &newStart, &tempEnd, unusedText);
michael@0:     text->TextBeforeOffset(tempEnd, startBoundary, &newStart, &newEnd, unusedText);
michael@0:     int32_t potentialStart = newEnd == tempEnd ? newStart : newEnd;
michael@0:     tempStart = potentialStart > tempStart ? potentialStart : currentEnd;
michael@0: 
michael@0:     // The offset range we've obtained might have embedded characters in it,
michael@0:     // limit the range to the start of the first occurrence of an embedded
michael@0:     // character.
michael@0:     Accessible* childAtOffset = nullptr;
michael@0:     for (int32_t i = tempStart; i < tempEnd; i++) {
michael@0:       childAtOffset = text->GetChildAtOffset(i);
michael@0:       if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset)) {
michael@0:         tempEnd = i;
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0:     // If there's an embedded character at the very start of the range, we
michael@0:     // instead want to traverse into it. So restart the movement with
michael@0:     // the child as the starting point.
michael@0:     if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset) &&
michael@0:         tempStart == childAtOffset->StartOffset()) {
michael@0:       tempPosition = childAtOffset;
michael@0:       tempStart = tempEnd = -1;
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     *aResult = true;
michael@0: 
michael@0:     Accessible* startPosition = mPosition;
michael@0:     int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
michael@0:     mPosition = tempPosition;
michael@0:     mStartOffset = tempStart;
michael@0:     mEndOffset = tempEnd;
michael@0:     NotifyOfPivotChange(startPosition, oldStart, oldEnd,
michael@0:                         nsIAccessiblePivot::REASON_TEXT);
michael@0:     return NS_OK;
michael@0:   }
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MovePreviousByText(TextBoundaryType aBoundary, bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG(aResult);
michael@0: 
michael@0:   *aResult = false;
michael@0: 
michael@0:   int32_t tempStart = mStartOffset, tempEnd = mEndOffset;
michael@0:   Accessible* tempPosition = mPosition;
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   while (true) {
michael@0:     Accessible* curPosition = tempPosition;
michael@0:     HyperTextAccessible* text;
michael@0:     // Find the nearest text node using a reverse preorder traversal starting
michael@0:     // from the current node.
michael@0:     if (!(text = tempPosition->AsHyperText())) {
michael@0:       text = SearchForText(tempPosition, true);
michael@0:       if (!text)
michael@0:         return NS_OK;
michael@0:       if (text != curPosition)
michael@0:         tempStart = tempEnd = -1;
michael@0:       tempPosition = text;
michael@0:     }
michael@0: 
michael@0:     // If the search led to the parent of the node we started on (e.g. when
michael@0:     // starting on a text leaf), start the text movement from the end of that
michael@0:     // node, otherwise we just default to 0.
michael@0:     if (tempStart == -1) {
michael@0:       if (tempPosition != curPosition)
michael@0:         tempStart = text == curPosition->Parent() ?
michael@0:                     text->GetChildOffset(curPosition) : text->CharacterCount();
michael@0:       else
michael@0:         tempStart = 0;
michael@0:     }
michael@0: 
michael@0:     // If there's no more text on the current node, try to find the previous
michael@0:     // text node; if there isn't one, bail out.
michael@0:     if (tempStart == 0) {
michael@0:       if (tempPosition == root)
michael@0:         return NS_OK;
michael@0: 
michael@0:       // If we're currently sitting on a link, try move to either the previous
michael@0:       // sibling or the parent, whichever is closer to the current end
michael@0:       // offset. Otherwise, do a forward search for the next node to land on
michael@0:       // (we don't do this in the first case because we don't want to go to the
michael@0:       // subtree).
michael@0:       Accessible* sibling = tempPosition->PrevSibling();
michael@0:       if (tempPosition->IsLink()) {
michael@0:         if (sibling && sibling->IsLink()) {
michael@0:           HyperTextAccessible* siblingText = sibling->AsHyperText();
michael@0:           tempStart = tempEnd = siblingText ?
michael@0:                                 siblingText->CharacterCount() : -1;
michael@0:           tempPosition = sibling;
michael@0:         } else {
michael@0:           tempStart = tempPosition->StartOffset();
michael@0:           tempEnd = tempPosition->EndOffset();
michael@0:           tempPosition = tempPosition->Parent();
michael@0:         }
michael@0:       } else {
michael@0:         HyperTextAccessible* tempText = SearchForText(tempPosition, true);
michael@0:         if (!tempText)
michael@0:           return NS_OK;
michael@0:         tempPosition = tempText;
michael@0:         tempStart = tempEnd = tempText->CharacterCount();
michael@0:       }
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     AccessibleTextBoundary startBoundary, endBoundary;
michael@0:     switch (aBoundary) {
michael@0:       case CHAR_BOUNDARY:
michael@0:         startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
michael@0:         endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
michael@0:         break;
michael@0:       case WORD_BOUNDARY:
michael@0:         startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
michael@0:         endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
michael@0:         break;
michael@0:       default:
michael@0:         return NS_ERROR_INVALID_ARG;
michael@0:     }
michael@0: 
michael@0:     nsAutoString unusedText;
michael@0:     int32_t newStart = 0, newEnd = 0, currentStart = tempStart, potentialEnd = 0;
michael@0:     text->TextBeforeOffset(tempStart, startBoundary, &newStart, &newEnd, unusedText);
michael@0:     if (newStart < tempStart)
michael@0:       tempStart = newEnd >= currentStart ? newStart : newEnd;
michael@0:     else // XXX: In certain odd cases newStart is equal to tempStart
michael@0:       text->TextBeforeOffset(tempStart - 1, startBoundary, &newStart,
michael@0:                              &tempStart, unusedText);
michael@0:     text->TextAtOffset(tempStart, endBoundary, &newStart, &potentialEnd,
michael@0:                        unusedText);
michael@0:     tempEnd = potentialEnd < tempEnd ? potentialEnd : currentStart;
michael@0: 
michael@0:     // The offset range we've obtained might have embedded characters in it,
michael@0:     // limit the range to the start of the last occurrence of an embedded
michael@0:     // character.
michael@0:     Accessible* childAtOffset = nullptr;
michael@0:     for (int32_t i = tempEnd - 1; i >= tempStart; i--) {
michael@0:       childAtOffset = text->GetChildAtOffset(i);
michael@0:       if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset)) {
michael@0:         tempStart = childAtOffset->EndOffset();
michael@0:         break;
michael@0:       }
michael@0:     }
michael@0:     // If there's an embedded character at the very end of the range, we
michael@0:     // instead want to traverse into it. So restart the movement with
michael@0:     // the child as the starting point.
michael@0:     if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset) &&
michael@0:         tempEnd == childAtOffset->EndOffset()) {
michael@0:       tempPosition = childAtOffset;
michael@0:       tempStart = tempEnd = childAtOffset->AsHyperText()->CharacterCount();
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     *aResult = true;
michael@0: 
michael@0:     Accessible* startPosition = mPosition;
michael@0:     int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
michael@0:     mPosition = tempPosition;
michael@0:     mStartOffset = tempStart;
michael@0:     mEndOffset = tempEnd;
michael@0: 
michael@0:     NotifyOfPivotChange(startPosition, oldStart, oldEnd,
michael@0:                         nsIAccessiblePivot::REASON_TEXT);
michael@0:     return NS_OK;
michael@0:   }
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::MoveToPoint(nsIAccessibleTraversalRule* aRule,
michael@0:                                int32_t aX, int32_t aY, bool aIgnoreNoMatch,
michael@0:                                bool* aResult)
michael@0: {
michael@0:   NS_ENSURE_ARG_POINTER(aResult);
michael@0:   NS_ENSURE_ARG_POINTER(aRule);
michael@0: 
michael@0:   *aResult = false;
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
michael@0: 
michael@0:   RuleCache cache(aRule);
michael@0:   Accessible* match = nullptr;
michael@0:   Accessible* child = root->ChildAtPoint(aX, aY, Accessible::eDeepestChild);
michael@0:   while (child && root != child) {
michael@0:     uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
michael@0:     nsresult rv = cache.ApplyFilter(child, &filtered);
michael@0:     NS_ENSURE_SUCCESS(rv, rv);
michael@0: 
michael@0:     // Ignore any matching nodes that were below this one
michael@0:     if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE)
michael@0:       match = nullptr;
michael@0: 
michael@0:     // Match if no node below this is a match
michael@0:     if ((filtered & nsIAccessibleTraversalRule::FILTER_MATCH) && !match) {
michael@0:       int32_t childX, childY, childWidth, childHeight;
michael@0:       child->GetBounds(&childX, &childY, &childWidth, &childHeight);
michael@0:       // Double-check child's bounds since the deepest child may have been out
michael@0:       // of bounds. This assures we don't return a false positive.
michael@0:       if (aX >= childX && aX < childX + childWidth &&
michael@0:           aY >= childY && aY < childY + childHeight)
michael@0:         match = child;
michael@0:     }
michael@0: 
michael@0:     child = child->Parent();
michael@0:   }
michael@0: 
michael@0:   if (match || !aIgnoreNoMatch)
michael@0:     *aResult = MovePivotInternal(match, nsIAccessiblePivot::REASON_POINT);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: // Observer functions
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::AddObserver(nsIAccessiblePivotObserver* aObserver)
michael@0: {
michael@0:   NS_ENSURE_ARG(aObserver);
michael@0: 
michael@0:   mObservers.AppendElement(aObserver);
michael@0: 
michael@0:   return NS_OK;
michael@0: }
michael@0: 
michael@0: NS_IMETHODIMP
michael@0: nsAccessiblePivot::RemoveObserver(nsIAccessiblePivotObserver* aObserver)
michael@0: {
michael@0:   NS_ENSURE_ARG(aObserver);
michael@0: 
michael@0:   return mObservers.RemoveElement(aObserver) ? NS_OK : NS_ERROR_FAILURE;
michael@0: }
michael@0: 
michael@0: // Private utility methods
michael@0: 
michael@0: bool
michael@0: nsAccessiblePivot::IsDescendantOf(Accessible* aAccessible, Accessible* aAncestor)
michael@0: {
michael@0:   if (!aAncestor || aAncestor->IsDefunct())
michael@0:     return false;
michael@0: 
michael@0:   // XXX Optimize with IsInDocument() when appropriate. Blocked by bug 759875.
michael@0:   Accessible* accessible = aAccessible;
michael@0:   do {
michael@0:     if (accessible == aAncestor)
michael@0:       return true;
michael@0:   } while ((accessible = accessible->Parent()));
michael@0: 
michael@0:   return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsAccessiblePivot::MovePivotInternal(Accessible* aPosition,
michael@0:                                      PivotMoveReason aReason)
michael@0: {
michael@0:   nsRefPtr<Accessible> oldPosition = mPosition.forget();
michael@0:   mPosition = aPosition;
michael@0:   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
michael@0:   mStartOffset = mEndOffset = -1;
michael@0: 
michael@0:   return NotifyOfPivotChange(oldPosition, oldStart, oldEnd, aReason);
michael@0: }
michael@0: 
michael@0: Accessible*
michael@0: nsAccessiblePivot::AdjustStartPosition(Accessible* aAccessible,
michael@0:                                        RuleCache& aCache,
michael@0:                                        uint16_t* aFilterResult,
michael@0:                                        nsresult* aResult)
michael@0: {
michael@0:   Accessible* matched = aAccessible;
michael@0:   *aResult = aCache.ApplyFilter(aAccessible, aFilterResult);
michael@0: 
michael@0:   if (aAccessible != mRoot && aAccessible != mModalRoot) {
michael@0:     for (Accessible* temp = aAccessible->Parent();
michael@0:          temp && temp != mRoot && temp != mModalRoot; temp = temp->Parent()) {
michael@0:       uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
michael@0:       *aResult = aCache.ApplyFilter(temp, &filtered);
michael@0:       NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0:       if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
michael@0:         *aFilterResult = filtered;
michael@0:         matched = temp;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   return matched;
michael@0: }
michael@0: 
michael@0: Accessible*
michael@0: nsAccessiblePivot::SearchBackward(Accessible* aAccessible,
michael@0:                                   nsIAccessibleTraversalRule* aRule,
michael@0:                                   bool aSearchCurrent,
michael@0:                                   nsresult* aResult)
michael@0: {
michael@0:   *aResult = NS_OK;
michael@0: 
michael@0:   // Initial position could be unset, in that case return null.
michael@0:   if (!aAccessible)
michael@0:     return nullptr;
michael@0: 
michael@0:   RuleCache cache(aRule);
michael@0:   uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
michael@0:   Accessible* accessible = AdjustStartPosition(aAccessible, cache,
michael@0:                                                &filtered, aResult);
michael@0:   NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0: 
michael@0:   if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
michael@0:     return accessible;
michael@0:   }
michael@0: 
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   while (accessible != root) {
michael@0:     Accessible* parent = accessible->Parent();
michael@0:     int32_t idxInParent = accessible->IndexInParent();
michael@0:     while (idxInParent > 0) {
michael@0:       if (!(accessible = parent->GetChildAt(--idxInParent)))
michael@0:         continue;
michael@0: 
michael@0:       *aResult = cache.ApplyFilter(accessible, &filtered);
michael@0:       NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0: 
michael@0:       Accessible* lastChild = nullptr;
michael@0:       while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
michael@0:              (lastChild = accessible->LastChild())) {
michael@0:         parent = accessible;
michael@0:         accessible = lastChild;
michael@0:         idxInParent = accessible->IndexInParent();
michael@0:         *aResult = cache.ApplyFilter(accessible, &filtered);
michael@0:         NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0:       }
michael@0: 
michael@0:       if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
michael@0:         return accessible;
michael@0:     }
michael@0: 
michael@0:     if (!(accessible = parent))
michael@0:       break;
michael@0: 
michael@0:     *aResult = cache.ApplyFilter(accessible, &filtered);
michael@0:     NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0: 
michael@0:     if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
michael@0:       return accessible;
michael@0:   }
michael@0: 
michael@0:   return nullptr;
michael@0: }
michael@0: 
michael@0: Accessible*
michael@0: nsAccessiblePivot::SearchForward(Accessible* aAccessible,
michael@0:                                  nsIAccessibleTraversalRule* aRule,
michael@0:                                  bool aSearchCurrent,
michael@0:                                  nsresult* aResult)
michael@0: {
michael@0:   *aResult = NS_OK;
michael@0: 
michael@0:   // Initial position could be not set, in that case begin search from root.
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   Accessible* accessible = (!aAccessible) ? root : aAccessible;
michael@0: 
michael@0:   RuleCache cache(aRule);
michael@0: 
michael@0:   uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
michael@0:   accessible = AdjustStartPosition(accessible, cache, &filtered, aResult);
michael@0:   NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0:   if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH))
michael@0:     return accessible;
michael@0: 
michael@0:   while (true) {
michael@0:     Accessible* firstChild = nullptr;
michael@0:     while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
michael@0:            (firstChild = accessible->FirstChild())) {
michael@0:       accessible = firstChild;
michael@0:       *aResult = cache.ApplyFilter(accessible, &filtered);
michael@0:       NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0: 
michael@0:       if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
michael@0:         return accessible;
michael@0:     }
michael@0: 
michael@0:     Accessible* sibling = nullptr;
michael@0:     Accessible* temp = accessible;
michael@0:     do {
michael@0:       if (temp == root)
michael@0:         break;
michael@0: 
michael@0:       sibling = temp->NextSibling();
michael@0: 
michael@0:       if (sibling)
michael@0:         break;
michael@0:     } while ((temp = temp->Parent()));
michael@0: 
michael@0:     if (!sibling)
michael@0:       break;
michael@0: 
michael@0:     accessible = sibling;
michael@0:     *aResult = cache.ApplyFilter(accessible, &filtered);
michael@0:     NS_ENSURE_SUCCESS(*aResult, nullptr);
michael@0: 
michael@0:     if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
michael@0:       return accessible;
michael@0:   }
michael@0: 
michael@0:   return nullptr;
michael@0: }
michael@0: 
michael@0: HyperTextAccessible*
michael@0: nsAccessiblePivot::SearchForText(Accessible* aAccessible, bool aBackward)
michael@0: {
michael@0:   Accessible* root = GetActiveRoot();
michael@0:   Accessible* accessible = aAccessible;
michael@0:   while (true) {
michael@0:     Accessible* child = nullptr;
michael@0: 
michael@0:     while ((child = (aBackward ? accessible->LastChild() :
michael@0:                                  accessible->FirstChild()))) {
michael@0:       accessible = child;
michael@0:       if (child->IsHyperText())
michael@0:         return child->AsHyperText();
michael@0:     }
michael@0: 
michael@0:     Accessible* sibling = nullptr;
michael@0:     Accessible* temp = accessible;
michael@0:     do {
michael@0:       if (temp == root)
michael@0:         break;
michael@0: 
michael@0:       if (temp != aAccessible && temp->IsHyperText())
michael@0:         return temp->AsHyperText();
michael@0: 
michael@0:       sibling = aBackward ? temp->PrevSibling() : temp->NextSibling();
michael@0: 
michael@0:       if (sibling)
michael@0:         break;
michael@0:     } while ((temp = temp->Parent()));
michael@0: 
michael@0:     if (!sibling)
michael@0:       break;
michael@0: 
michael@0:     accessible = sibling;
michael@0:     if (accessible->IsHyperText())
michael@0:       return accessible->AsHyperText();
michael@0:   }
michael@0: 
michael@0:   return nullptr;
michael@0: }
michael@0: 
michael@0: 
michael@0: bool
michael@0: nsAccessiblePivot::NotifyOfPivotChange(Accessible* aOldPosition,
michael@0:                                        int32_t aOldStart, int32_t aOldEnd,
michael@0:                                        int16_t aReason)
michael@0: {
michael@0:   if (aOldPosition == mPosition &&
michael@0:       aOldStart == mStartOffset && aOldEnd == mEndOffset)
michael@0:     return false;
michael@0: 
michael@0:   nsTObserverArray<nsCOMPtr<nsIAccessiblePivotObserver> >::ForwardIterator iter(mObservers);
michael@0:   while (iter.HasMore()) {
michael@0:     nsIAccessiblePivotObserver* obs = iter.GetNext();
michael@0:     obs->OnPivotChanged(this, aOldPosition, aOldStart, aOldEnd, aReason);
michael@0:   }
michael@0: 
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: RuleCache::ApplyFilter(Accessible* aAccessible, uint16_t* aResult)
michael@0: {
michael@0:   *aResult = nsIAccessibleTraversalRule::FILTER_IGNORE;
michael@0: 
michael@0:   if (!mAcceptRoles) {
michael@0:     nsresult rv = mRule->GetMatchRoles(&mAcceptRoles, &mAcceptRolesLength);
michael@0:     NS_ENSURE_SUCCESS(rv, rv);
michael@0:     rv = mRule->GetPreFilter(&mPreFilter);
michael@0:     NS_ENSURE_SUCCESS(rv, rv);
michael@0:   }
michael@0: 
michael@0:   if (mPreFilter) {
michael@0:     uint64_t state = aAccessible->State();
michael@0: 
michael@0:     if ((nsIAccessibleTraversalRule::PREFILTER_INVISIBLE & mPreFilter) &&
michael@0:         (state & states::INVISIBLE))
michael@0:       return NS_OK;
michael@0: 
michael@0:     if ((nsIAccessibleTraversalRule::PREFILTER_OFFSCREEN & mPreFilter) &&
michael@0:         (state & states::OFFSCREEN))
michael@0:       return NS_OK;
michael@0: 
michael@0:     if ((nsIAccessibleTraversalRule::PREFILTER_NOT_FOCUSABLE & mPreFilter) &&
michael@0:         !(state & states::FOCUSABLE))
michael@0:       return NS_OK;
michael@0: 
michael@0:     if (nsIAccessibleTraversalRule::PREFILTER_ARIA_HIDDEN & mPreFilter) {
michael@0:       nsIContent* content = aAccessible->GetContent();
michael@0:       if (content &&
michael@0:           nsAccUtils::HasDefinedARIAToken(content, nsGkAtoms::aria_hidden) &&
michael@0:           !content->AttrValueIs(kNameSpaceID_None, nsGkAtoms::aria_hidden,
michael@0:                                 nsGkAtoms::_false, eCaseMatters)) {
michael@0:         *aResult |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
michael@0:         return NS_OK;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     if ((nsIAccessibleTraversalRule::PREFILTER_TRANSPARENT & mPreFilter) &&
michael@0:         !(state & states::OPAQUE1)) {
michael@0:       nsIFrame* frame = aAccessible->GetFrame();
michael@0:       if (frame->StyleDisplay()->mOpacity == 0.0f) {
michael@0:         *aResult |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
michael@0:         return NS_OK;
michael@0:       }
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   if (mAcceptRolesLength > 0) {
michael@0:     uint32_t accessibleRole = aAccessible->Role();
michael@0:     bool matchesRole = false;
michael@0:     for (uint32_t idx = 0; idx < mAcceptRolesLength; idx++) {
michael@0:       matchesRole = mAcceptRoles[idx] == accessibleRole;
michael@0:       if (matchesRole)
michael@0:         break;
michael@0:     }
michael@0:     if (!matchesRole)
michael@0:       return NS_OK;
michael@0:   }
michael@0: 
michael@0:   return mRule->Match(aAccessible, aResult);
michael@0: }