accessible/base/nsAccessiblePivot.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "nsAccessiblePivot.h"
   8
   9 #include "HyperTextAccessible.h"
  10 #include "nsAccUtils.h"
  11 #include "States.h"
  12
  13 using namespace mozilla::a11y;
  14
  15
  16 /**
  17  * An object that stores a given traversal rule during the pivot movement.
  18  */
  19 class RuleCache
  20 {
  21 public:
  22   RuleCache(nsIAccessibleTraversalRule* aRule) : mRule(aRule),
  23                                                  mAcceptRoles(nullptr) { }
  24   ~RuleCache () {
  25     if (mAcceptRoles)
  26       nsMemory::Free(mAcceptRoles);
  27   }
  28
  29   nsresult ApplyFilter(Accessible* aAccessible, uint16_t* aResult);
  30
  31 private:
  32   nsCOMPtr<nsIAccessibleTraversalRule> mRule;
  33   uint32_t* mAcceptRoles;
  34   uint32_t mAcceptRolesLength;
  35   uint32_t mPreFilter;
  36 };
  37
  38 ////////////////////////////////////////////////////////////////////////////////
  39 // nsAccessiblePivot
  40
  41 nsAccessiblePivot::nsAccessiblePivot(Accessible* aRoot) :
  42   mRoot(aRoot), mModalRoot(nullptr), mPosition(nullptr),
  43   mStartOffset(-1), mEndOffset(-1)
  44 {
  45   NS_ASSERTION(aRoot, "A root accessible is required");
  46 }
  47
  48 nsAccessiblePivot::~nsAccessiblePivot()
  49 {
  50 }
  51
  52 ////////////////////////////////////////////////////////////////////////////////
  53 // nsISupports
  54
  55 NS_IMPL_CYCLE_COLLECTION(nsAccessiblePivot, mRoot, mPosition, mObservers)
  56
  57 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(nsAccessiblePivot)
  58   NS_INTERFACE_MAP_ENTRY(nsIAccessiblePivot)
  59   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIAccessiblePivot)
  60 NS_INTERFACE_MAP_END
  61
  62 NS_IMPL_CYCLE_COLLECTING_ADDREF(nsAccessiblePivot)
  63 NS_IMPL_CYCLE_COLLECTING_RELEASE(nsAccessiblePivot)
  64
  65 ////////////////////////////////////////////////////////////////////////////////
  66 // nsIAccessiblePivot
  67
  68 NS_IMETHODIMP
  69 nsAccessiblePivot::GetRoot(nsIAccessible** aRoot)
  70 {
  71   NS_ENSURE_ARG_POINTER(aRoot);
  72
  73   NS_IF_ADDREF(*aRoot = mRoot);
  74
  75   return NS_OK;
  76 }
  77
  78 NS_IMETHODIMP
  79 nsAccessiblePivot::GetPosition(nsIAccessible** aPosition)
  80 {
  81   NS_ENSURE_ARG_POINTER(aPosition);
  82
  83   NS_IF_ADDREF(*aPosition = mPosition);
  84
  85   return NS_OK;
  86 }
  87
  88 NS_IMETHODIMP
  89 nsAccessiblePivot::SetPosition(nsIAccessible* aPosition)
  90 {
  91   nsRefPtr<Accessible> secondPosition;
  92
  93   if (aPosition) {
  94     secondPosition = do_QueryObject(aPosition);
  95     if (!secondPosition || !IsDescendantOf(secondPosition, GetActiveRoot()))
  96       return NS_ERROR_INVALID_ARG;
  97   }
  98
  99   // Swap old position with new position, saves us an AddRef/Release.
 100   mPosition.swap(secondPosition);
 101   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
 102   mStartOffset = mEndOffset = -1;
 103   NotifyOfPivotChange(secondPosition, oldStart, oldEnd,
 104                       nsIAccessiblePivot::REASON_NONE, false);
 105
 106   return NS_OK;
 107 }
 108
 109 NS_IMETHODIMP
 110 nsAccessiblePivot::GetModalRoot(nsIAccessible** aModalRoot)
 111 {
 112   NS_ENSURE_ARG_POINTER(aModalRoot);
 113
 114   NS_IF_ADDREF(*aModalRoot = mModalRoot);
 115
 116   return NS_OK;
 117 }
 118
 119 NS_IMETHODIMP
 120 nsAccessiblePivot::SetModalRoot(nsIAccessible* aModalRoot)
 121 {
 122   nsRefPtr<Accessible> modalRoot;
 123
 124   if (aModalRoot) {
 125     modalRoot = do_QueryObject(aModalRoot);
 126     if (!modalRoot || !IsDescendantOf(modalRoot, mRoot))
 127       return NS_ERROR_INVALID_ARG;
 128   }
 129
 130   mModalRoot.swap(modalRoot);
 131
 132   return NS_OK;
 133 }
 134
 135 NS_IMETHODIMP
 136 nsAccessiblePivot::GetStartOffset(int32_t* aStartOffset)
 137 {
 138   NS_ENSURE_ARG_POINTER(aStartOffset);
 139
 140   *aStartOffset = mStartOffset;
 141
 142   return NS_OK;
 143 }
 144
 145 NS_IMETHODIMP
 146 nsAccessiblePivot::GetEndOffset(int32_t* aEndOffset)
 147 {
 148   NS_ENSURE_ARG_POINTER(aEndOffset);
 149
 150   *aEndOffset = mEndOffset;
 151
 152   return NS_OK;
 153 }
 154
 155 NS_IMETHODIMP
 156 nsAccessiblePivot::SetTextRange(nsIAccessibleText* aTextAccessible,
 157                                 int32_t aStartOffset, int32_t aEndOffset,
 158                                 bool aIsFromUserInput, uint8_t aArgc)
 159 {
 160   NS_ENSURE_ARG(aTextAccessible);
 161
 162   // Check that start offset is smaller than end offset, and that if a value is
 163   // smaller than 0, both should be -1.
 164   NS_ENSURE_TRUE(aStartOffset <= aEndOffset &&
 165                  (aStartOffset >= 0 || (aStartOffset != -1 && aEndOffset != -1)),
 166                  NS_ERROR_INVALID_ARG);
 167
 168   nsRefPtr<Accessible> acc(do_QueryObject(aTextAccessible));
 169   if (!acc)
 170     return NS_ERROR_INVALID_ARG;
 171
 172   HyperTextAccessible* newPosition = acc->AsHyperText();
 173   if (!newPosition || !IsDescendantOf(newPosition, GetActiveRoot()))
 174     return NS_ERROR_INVALID_ARG;
 175
 176   // Make sure the given offsets don't exceed the character count.
 177   int32_t charCount = newPosition->CharacterCount();
 178
 179   if (aEndOffset > charCount)
 180     return NS_ERROR_FAILURE;
 181
 182   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
 183   mStartOffset = aStartOffset;
 184   mEndOffset = aEndOffset;
 185
 186   nsRefPtr<Accessible> oldPosition = mPosition.forget();
 187   mPosition = newPosition;
 188
 189   NotifyOfPivotChange(oldPosition, oldStart, oldEnd,
 190                       nsIAccessiblePivot::REASON_TEXT,
 191                       (aArgc > 0) ? aIsFromUserInput : true);
 192
 193   return NS_OK;
 194 }
 195
 196 // Traversal functions
 197
 198 NS_IMETHODIMP
 199 nsAccessiblePivot::MoveNext(nsIAccessibleTraversalRule* aRule,
 200                             nsIAccessible* aAnchor, bool aIncludeStart,
 201                             bool aIsFromUserInput, uint8_t aArgc, bool* aResult)
 202 {
 203   NS_ENSURE_ARG(aResult);
 204   NS_ENSURE_ARG(aRule);
 205
 206   *aResult = false;
 207
 208   Accessible* root = GetActiveRoot();
 209   nsRefPtr<Accessible> anchor =
 210     (aArgc > 0) ? do_QueryObject(aAnchor) : mPosition;
 211   if (anchor && (anchor->IsDefunct() || !IsDescendantOf(anchor, root)))
 212     return NS_ERROR_NOT_IN_TREE;
 213
 214   nsresult rv = NS_OK;
 215   Accessible* accessible =
 216     SearchForward(anchor, aRule, (aArgc > 1) ? aIncludeStart : false, &rv);
 217   NS_ENSURE_SUCCESS(rv, rv);
 218
 219   if (accessible)
 220     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_NEXT,
 221                                  (aArgc > 2) ? aIsFromUserInput : true);
 222
 223   return NS_OK;
 224 }
 225
 226 NS_IMETHODIMP
 227 nsAccessiblePivot::MovePrevious(nsIAccessibleTraversalRule* aRule,
 228                                 nsIAccessible* aAnchor,
 229                                 bool aIncludeStart, bool aIsFromUserInput,
 230                                 uint8_t aArgc, bool* aResult)
 231 {
 232   NS_ENSURE_ARG(aResult);
 233   NS_ENSURE_ARG(aRule);
 234
 235   *aResult = false;
 236
 237   Accessible* root = GetActiveRoot();
 238   nsRefPtr<Accessible> anchor =
 239     (aArgc > 0) ? do_QueryObject(aAnchor) : mPosition;
 240   if (anchor && (anchor->IsDefunct() || !IsDescendantOf(anchor, root)))
 241     return NS_ERROR_NOT_IN_TREE;
 242
 243   nsresult rv = NS_OK;
 244   Accessible* accessible =
 245     SearchBackward(anchor, aRule, (aArgc > 1) ? aIncludeStart : false, &rv);
 246   NS_ENSURE_SUCCESS(rv, rv);
 247
 248   if (accessible)
 249     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_PREV,
 250                                  (aArgc > 2) ? aIsFromUserInput : true);
 251
 252   return NS_OK;
 253 }
 254
 255 NS_IMETHODIMP
 256 nsAccessiblePivot::MoveFirst(nsIAccessibleTraversalRule* aRule,
 257                              bool aIsFromUserInput,
 258                              uint8_t aArgc, bool* aResult)
 259 {
 260   NS_ENSURE_ARG(aResult);
 261   NS_ENSURE_ARG(aRule);
 262
 263   Accessible* root = GetActiveRoot();
 264   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
 265
 266   nsresult rv = NS_OK;
 267   Accessible* accessible = SearchForward(root, aRule, true, &rv);
 268   NS_ENSURE_SUCCESS(rv, rv);
 269
 270   if (accessible)
 271     *aResult = MovePivotInternal(accessible, nsIAccessiblePivot::REASON_FIRST,
 272                                  (aArgc > 0) ? aIsFromUserInput : true);
 273
 274   return NS_OK;
 275 }
 276
 277 NS_IMETHODIMP
 278 nsAccessiblePivot::MoveLast(nsIAccessibleTraversalRule* aRule,
 279                             bool aIsFromUserInput,
 280                             uint8_t aArgc, bool* aResult)
 281 {
 282   NS_ENSURE_ARG(aResult);
 283   NS_ENSURE_ARG(aRule);
 284
 285   Accessible* root = GetActiveRoot();
 286   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
 287
 288   *aResult = false;
 289   nsresult rv = NS_OK;
 290   Accessible* lastAccessible = root;
 291   Accessible* accessible = nullptr;
 292
 293   // First go to the last accessible in pre-order
 294   while (lastAccessible->HasChildren())
 295     lastAccessible = lastAccessible->LastChild();
 296
 297   // Search backwards from last accessible and find the last occurrence in the doc
 298   accessible = SearchBackward(lastAccessible, aRule, true, &rv);
 299   NS_ENSURE_SUCCESS(rv, rv);
 300
 301   if (accessible)
 302     *aResult = MovePivotInternal(accessible, nsAccessiblePivot::REASON_LAST,
 303                                  (aArgc > 0) ? aIsFromUserInput : true);
 304
 305   return NS_OK;
 306 }
 307
 308 NS_IMETHODIMP
 309 nsAccessiblePivot::MoveNextByText(TextBoundaryType aBoundary,
 310                                   bool aIsFromUserInput, uint8_t aArgc,
 311                                   bool* aResult)
 312 {
 313   NS_ENSURE_ARG(aResult);
 314
 315   *aResult = false;
 316
 317   int32_t tempStart = mStartOffset, tempEnd = mEndOffset;
 318   Accessible* tempPosition = mPosition;
 319   Accessible* root = GetActiveRoot();
 320   while (true) {
 321     Accessible* curPosition = tempPosition;
 322     HyperTextAccessible* text = nullptr;
 323     // Find the nearest text node using a preorder traversal starting from
 324     // the current node.
 325     if (!(text = tempPosition->AsHyperText())) {
 326       text = SearchForText(tempPosition, false);
 327       if (!text)
 328         return NS_OK;
 329       if (text != curPosition)
 330         tempStart = tempEnd = -1;
 331       tempPosition = text;
 332     }
 333
 334     // If the search led to the parent of the node we started on (e.g. when
 335     // starting on a text leaf), start the text movement from the end of that
 336     // node, otherwise we just default to 0.
 337     if (tempEnd == -1)
 338       tempEnd = text == curPosition->Parent() ?
 339                 text->GetChildOffset(curPosition) : 0;
 340
 341     // If there's no more text on the current node, try to find the next text
 342     // node; if there isn't one, bail out.
 343     if (tempEnd == static_cast<int32_t>(text->CharacterCount())) {
 344       if (tempPosition == root)
 345         return NS_OK;
 346
 347       // If we're currently sitting on a link, try move to either the next
 348       // sibling or the parent, whichever is closer to the current end
 349       // offset. Otherwise, do a forward search for the next node to land on
 350       // (we don't do this in the first case because we don't want to go to the
 351       // subtree).
 352       Accessible* sibling = tempPosition->NextSibling();
 353       if (tempPosition->IsLink()) {
 354         if (sibling && sibling->IsLink()) {
 355           tempStart = tempEnd = -1;
 356           tempPosition = sibling;
 357         } else {
 358           tempStart = tempPosition->StartOffset();
 359           tempEnd = tempPosition->EndOffset();
 360           tempPosition = tempPosition->Parent();
 361         }
 362       } else {
 363         tempPosition = SearchForText(tempPosition, false);
 364         if (!tempPosition)
 365           return NS_OK;
 366         tempStart = tempEnd = -1;
 367       }
 368       continue;
 369     }
 370
 371     AccessibleTextBoundary startBoundary, endBoundary;
 372     switch (aBoundary) {
 373       case CHAR_BOUNDARY:
 374         startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
 375         endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
 376         break;
 377       case WORD_BOUNDARY:
 378         startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
 379         endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
 380         break;
 381       default:
 382         return NS_ERROR_INVALID_ARG;
 383     }
 384
 385     nsAutoString unusedText;
 386     int32_t newStart = 0, newEnd = 0, currentEnd = tempEnd;
 387     text->TextAtOffset(tempEnd, endBoundary, &newStart, &tempEnd, unusedText);
 388     text->TextBeforeOffset(tempEnd, startBoundary, &newStart, &newEnd, unusedText);
 389     int32_t potentialStart = newEnd == tempEnd ? newStart : newEnd;
 390     tempStart = potentialStart > tempStart ? potentialStart : currentEnd;
 391
 392     // The offset range we've obtained might have embedded characters in it,
 393     // limit the range to the start of the first occurrence of an embedded
 394     // character.
 395     Accessible* childAtOffset = nullptr;
 396     for (int32_t i = tempStart; i < tempEnd; i++) {
 397       childAtOffset = text->GetChildAtOffset(i);
 398       if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset)) {
 399         tempEnd = i;
 400         break;
 401       }
 402     }
 403     // If there's an embedded character at the very start of the range, we
 404     // instead want to traverse into it. So restart the movement with
 405     // the child as the starting point.
 406     if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset) &&
 407         tempStart == static_cast<int32_t>(childAtOffset->StartOffset())) {
 408       tempPosition = childAtOffset;
 409       tempStart = tempEnd = -1;
 410       continue;
 411     }
 412
 413     *aResult = true;
 414
 415     Accessible* startPosition = mPosition;
 416     int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
 417     mPosition = tempPosition;
 418     mStartOffset = tempStart;
 419     mEndOffset = tempEnd;
 420     NotifyOfPivotChange(startPosition, oldStart, oldEnd,
 421                         nsIAccessiblePivot::REASON_TEXT,
 422                         (aArgc > 0) ? aIsFromUserInput : true);
 423     return NS_OK;
 424   }
 425 }
 426
 427 NS_IMETHODIMP
 428 nsAccessiblePivot::MovePreviousByText(TextBoundaryType aBoundary,
 429                                       bool aIsFromUserInput, uint8_t aArgc,
 430                                       bool* aResult)
 431 {
 432   NS_ENSURE_ARG(aResult);
 433
 434   *aResult = false;
 435
 436   int32_t tempStart = mStartOffset, tempEnd = mEndOffset;
 437   Accessible* tempPosition = mPosition;
 438   Accessible* root = GetActiveRoot();
 439   while (true) {
 440     Accessible* curPosition = tempPosition;
 441     HyperTextAccessible* text;
 442     // Find the nearest text node using a reverse preorder traversal starting
 443     // from the current node.
 444     if (!(text = tempPosition->AsHyperText())) {
 445       text = SearchForText(tempPosition, true);
 446       if (!text)
 447         return NS_OK;
 448       if (text != curPosition)
 449         tempStart = tempEnd = -1;
 450       tempPosition = text;
 451     }
 452
 453     // If the search led to the parent of the node we started on (e.g. when
 454     // starting on a text leaf), start the text movement from the end of that
 455     // node, otherwise we just default to 0.
 456     if (tempStart == -1) {
 457       if (tempPosition != curPosition)
 458         tempStart = text == curPosition->Parent() ?
 459                     text->GetChildOffset(curPosition) : text->CharacterCount();
 460       else
 461         tempStart = 0;
 462     }
 463
 464     // If there's no more text on the current node, try to find the previous
 465     // text node; if there isn't one, bail out.
 466     if (tempStart == 0) {
 467       if (tempPosition == root)
 468         return NS_OK;
 469
 470       // If we're currently sitting on a link, try move to either the previous
 471       // sibling or the parent, whichever is closer to the current end
 472       // offset. Otherwise, do a forward search for the next node to land on
 473       // (we don't do this in the first case because we don't want to go to the
 474       // subtree).
 475       Accessible* sibling = tempPosition->PrevSibling();
 476       if (tempPosition->IsLink()) {
 477         if (sibling && sibling->IsLink()) {
 478           HyperTextAccessible* siblingText = sibling->AsHyperText();
 479           tempStart = tempEnd = siblingText ?
 480                                 siblingText->CharacterCount() : -1;
 481           tempPosition = sibling;
 482         } else {
 483           tempStart = tempPosition->StartOffset();
 484           tempEnd = tempPosition->EndOffset();
 485           tempPosition = tempPosition->Parent();
 486         }
 487       } else {
 488         HyperTextAccessible* tempText = SearchForText(tempPosition, true);
 489         if (!tempText)
 490           return NS_OK;
 491         tempPosition = tempText;
 492         tempStart = tempEnd = tempText->CharacterCount();
 493       }
 494       continue;
 495     }
 496
 497     AccessibleTextBoundary startBoundary, endBoundary;
 498     switch (aBoundary) {
 499       case CHAR_BOUNDARY:
 500         startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
 501         endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
 502         break;
 503       case WORD_BOUNDARY:
 504         startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
 505         endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
 506         break;
 507       default:
 508         return NS_ERROR_INVALID_ARG;
 509     }
 510
 511     nsAutoString unusedText;
 512     int32_t newStart = 0, newEnd = 0, currentStart = tempStart, potentialEnd = 0;
 513     text->TextBeforeOffset(tempStart, startBoundary, &newStart, &newEnd, unusedText);
 514     if (newStart < tempStart)
 515       tempStart = newEnd >= currentStart ? newStart : newEnd;
 516     else // XXX: In certain odd cases newStart is equal to tempStart
 517       text->TextBeforeOffset(tempStart - 1, startBoundary, &newStart,
 518                              &tempStart, unusedText);
 519     text->TextAtOffset(tempStart, endBoundary, &newStart, &potentialEnd,
 520                        unusedText);
 521     tempEnd = potentialEnd < tempEnd ? potentialEnd : currentStart;
 522
 523     // The offset range we've obtained might have embedded characters in it,
 524     // limit the range to the start of the last occurrence of an embedded
 525     // character.
 526     Accessible* childAtOffset = nullptr;
 527     for (int32_t i = tempEnd - 1; i >= tempStart; i--) {
 528       childAtOffset = text->GetChildAtOffset(i);
 529       if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset)) {
 530         tempStart = childAtOffset->EndOffset();
 531         break;
 532       }
 533     }
 534     // If there's an embedded character at the very end of the range, we
 535     // instead want to traverse into it. So restart the movement with
 536     // the child as the starting point.
 537     if (childAtOffset && nsAccUtils::IsEmbeddedObject(childAtOffset) &&
 538         tempEnd == static_cast<int32_t>(childAtOffset->EndOffset())) {
 539       tempPosition = childAtOffset;
 540       tempStart = tempEnd = childAtOffset->AsHyperText()->CharacterCount();
 541       continue;
 542     }
 543
 544     *aResult = true;
 545
 546     Accessible* startPosition = mPosition;
 547     int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
 548     mPosition = tempPosition;
 549     mStartOffset = tempStart;
 550     mEndOffset = tempEnd;
 551
 552     NotifyOfPivotChange(startPosition, oldStart, oldEnd,
 553                         nsIAccessiblePivot::REASON_TEXT,
 554                         (aArgc > 0) ? aIsFromUserInput : true);
 555     return NS_OK;
 556   }
 557 }
 558
 559 NS_IMETHODIMP
 560 nsAccessiblePivot::MoveToPoint(nsIAccessibleTraversalRule* aRule,
 561                                int32_t aX, int32_t aY, bool aIgnoreNoMatch,
 562                                bool aIsFromUserInput, uint8_t aArgc,
 563                                bool* aResult)
 564 {
 565   NS_ENSURE_ARG_POINTER(aResult);
 566   NS_ENSURE_ARG_POINTER(aRule);
 567
 568   *aResult = false;
 569
 570   Accessible* root = GetActiveRoot();
 571   NS_ENSURE_TRUE(root && !root->IsDefunct(), NS_ERROR_NOT_IN_TREE);
 572
 573   RuleCache cache(aRule);
 574   Accessible* match = nullptr;
 575   Accessible* child = root->ChildAtPoint(aX, aY, Accessible::eDeepestChild);
 576   while (child && root != child) {
 577     uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
 578     nsresult rv = cache.ApplyFilter(child, &filtered);
 579     NS_ENSURE_SUCCESS(rv, rv);
 580
 581     // Ignore any matching nodes that were below this one
 582     if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE)
 583       match = nullptr;
 584
 585     // Match if no node below this is a match
 586     if ((filtered & nsIAccessibleTraversalRule::FILTER_MATCH) && !match) {
 587       int32_t childX, childY, childWidth, childHeight;
 588       child->GetBounds(&childX, &childY, &childWidth, &childHeight);
 589       // Double-check child's bounds since the deepest child may have been out
 590       // of bounds. This assures we don't return a false positive.
 591       if (aX >= childX && aX < childX + childWidth &&
 592           aY >= childY && aY < childY + childHeight)
 593         match = child;
 594     }
 595
 596     child = child->Parent();
 597   }
 598
 599   if (match || !aIgnoreNoMatch)
 600     *aResult = MovePivotInternal(match, nsIAccessiblePivot::REASON_POINT,
 601                                  (aArgc > 0) ? aIsFromUserInput : true);
 602
 603   return NS_OK;
 604 }
 605
 606 // Observer functions
 607
 608 NS_IMETHODIMP
 609 nsAccessiblePivot::AddObserver(nsIAccessiblePivotObserver* aObserver)
 610 {
 611   NS_ENSURE_ARG(aObserver);
 612
 613   mObservers.AppendElement(aObserver);
 614
 615   return NS_OK;
 616 }
 617
 618 NS_IMETHODIMP
 619 nsAccessiblePivot::RemoveObserver(nsIAccessiblePivotObserver* aObserver)
 620 {
 621   NS_ENSURE_ARG(aObserver);
 622
 623   return mObservers.RemoveElement(aObserver) ? NS_OK : NS_ERROR_FAILURE;
 624 }
 625
 626 // Private utility methods
 627
 628 bool
 629 nsAccessiblePivot::IsDescendantOf(Accessible* aAccessible, Accessible* aAncestor)
 630 {
 631   if (!aAncestor || aAncestor->IsDefunct())
 632     return false;
 633
 634   // XXX Optimize with IsInDocument() when appropriate. Blocked by bug 759875.
 635   Accessible* accessible = aAccessible;
 636   do {
 637     if (accessible == aAncestor)
 638       return true;
 639   } while ((accessible = accessible->Parent()));
 640
 641   return false;
 642 }
 643
 644 bool
 645 nsAccessiblePivot::MovePivotInternal(Accessible* aPosition,
 646                                      PivotMoveReason aReason,
 647                                      bool aIsFromUserInput)
 648 {
 649   nsRefPtr<Accessible> oldPosition = mPosition.forget();
 650   mPosition = aPosition;
 651   int32_t oldStart = mStartOffset, oldEnd = mEndOffset;
 652   mStartOffset = mEndOffset = -1;
 653
 654   return NotifyOfPivotChange(oldPosition, oldStart, oldEnd, aReason,
 655                              aIsFromUserInput);
 656 }
 657
 658 Accessible*
 659 nsAccessiblePivot::AdjustStartPosition(Accessible* aAccessible,
 660                                        RuleCache& aCache,
 661                                        uint16_t* aFilterResult,
 662                                        nsresult* aResult)
 663 {
 664   Accessible* matched = aAccessible;
 665   *aResult = aCache.ApplyFilter(aAccessible, aFilterResult);
 666
 667   if (aAccessible != mRoot && aAccessible != mModalRoot) {
 668     for (Accessible* temp = aAccessible->Parent();
 669          temp && temp != mRoot && temp != mModalRoot; temp = temp->Parent()) {
 670       uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
 671       *aResult = aCache.ApplyFilter(temp, &filtered);
 672       NS_ENSURE_SUCCESS(*aResult, nullptr);
 673       if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
 674         *aFilterResult = filtered;
 675         matched = temp;
 676       }
 677     }
 678   }
 679
 680   if (aAccessible == mPosition && mStartOffset != -1 && mEndOffset != -1) {
 681     HyperTextAccessible* text = aAccessible->AsHyperText();
 682     if (text) {
 683       matched = text->GetChildAtOffset(mStartOffset);
 684     }
 685   }
 686
 687   return matched;
 688 }
 689
 690 Accessible*
 691 nsAccessiblePivot::SearchBackward(Accessible* aAccessible,
 692                                   nsIAccessibleTraversalRule* aRule,
 693                                   bool aSearchCurrent,
 694                                   nsresult* aResult)
 695 {
 696   *aResult = NS_OK;
 697
 698   // Initial position could be unset, in that case return null.
 699   if (!aAccessible)
 700     return nullptr;
 701
 702   RuleCache cache(aRule);
 703   uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
 704   Accessible* accessible = AdjustStartPosition(aAccessible, cache,
 705                                                &filtered, aResult);
 706   NS_ENSURE_SUCCESS(*aResult, nullptr);
 707
 708   if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
 709     return accessible;
 710   }
 711
 712   Accessible* root = GetActiveRoot();
 713   while (accessible != root) {
 714     Accessible* parent = accessible->Parent();
 715     int32_t idxInParent = accessible->IndexInParent();
 716     while (idxInParent > 0) {
 717       if (!(accessible = parent->GetChildAt(--idxInParent)))
 718         continue;
 719
 720       *aResult = cache.ApplyFilter(accessible, &filtered);
 721       NS_ENSURE_SUCCESS(*aResult, nullptr);
 722
 723       Accessible* lastChild = nullptr;
 724       while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
 725              (lastChild = accessible->LastChild())) {
 726         parent = accessible;
 727         accessible = lastChild;
 728         idxInParent = accessible->IndexInParent();
 729         *aResult = cache.ApplyFilter(accessible, &filtered);
 730         NS_ENSURE_SUCCESS(*aResult, nullptr);
 731       }
 732
 733       if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
 734         return accessible;
 735     }
 736
 737     if (!(accessible = parent))
 738       break;
 739
 740     *aResult = cache.ApplyFilter(accessible, &filtered);
 741     NS_ENSURE_SUCCESS(*aResult, nullptr);
 742
 743     if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
 744       return accessible;
 745   }
 746
 747   return nullptr;
 748 }
 749
 750 Accessible*
 751 nsAccessiblePivot::SearchForward(Accessible* aAccessible,
 752                                  nsIAccessibleTraversalRule* aRule,
 753                                  bool aSearchCurrent,
 754                                  nsresult* aResult)
 755 {
 756   *aResult = NS_OK;
 757
 758   // Initial position could be not set, in that case begin search from root.
 759   Accessible* root = GetActiveRoot();
 760   Accessible* accessible = (!aAccessible) ? root : aAccessible;
 761
 762   RuleCache cache(aRule);
 763
 764   uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
 765   accessible = AdjustStartPosition(accessible, cache, &filtered, aResult);
 766   NS_ENSURE_SUCCESS(*aResult, nullptr);
 767   if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH))
 768     return accessible;
 769
 770   while (true) {
 771     Accessible* firstChild = nullptr;
 772     while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
 773            (firstChild = accessible->FirstChild())) {
 774       accessible = firstChild;
 775       *aResult = cache.ApplyFilter(accessible, &filtered);
 776       NS_ENSURE_SUCCESS(*aResult, nullptr);
 777
 778       if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
 779         return accessible;
 780     }
 781
 782     Accessible* sibling = nullptr;
 783     Accessible* temp = accessible;
 784     do {
 785       if (temp == root)
 786         break;
 787
 788       sibling = temp->NextSibling();
 789
 790       if (sibling)
 791         break;
 792     } while ((temp = temp->Parent()));
 793
 794     if (!sibling)
 795       break;
 796
 797     accessible = sibling;
 798     *aResult = cache.ApplyFilter(accessible, &filtered);
 799     NS_ENSURE_SUCCESS(*aResult, nullptr);
 800
 801     if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)
 802       return accessible;
 803   }
 804
 805   return nullptr;
 806 }
 807
 808 HyperTextAccessible*
 809 nsAccessiblePivot::SearchForText(Accessible* aAccessible, bool aBackward)
 810 {
 811   Accessible* root = GetActiveRoot();
 812   Accessible* accessible = aAccessible;
 813   while (true) {
 814     Accessible* child = nullptr;
 815
 816     while ((child = (aBackward ? accessible->LastChild() :
 817                                  accessible->FirstChild()))) {
 818       accessible = child;
 819       if (child->IsHyperText())
 820         return child->AsHyperText();
 821     }
 822
 823     Accessible* sibling = nullptr;
 824     Accessible* temp = accessible;
 825     do {
 826       if (temp == root)
 827         break;
 828
 829       if (temp != aAccessible && temp->IsHyperText())
 830         return temp->AsHyperText();
 831
 832       sibling = aBackward ? temp->PrevSibling() : temp->NextSibling();
 833
 834       if (sibling)
 835         break;
 836     } while ((temp = temp->Parent()));
 837
 838     if (!sibling)
 839       break;
 840
 841     accessible = sibling;
 842     if (accessible->IsHyperText())
 843       return accessible->AsHyperText();
 844   }
 845
 846   return nullptr;
 847 }
 848
 849
 850 bool
 851 nsAccessiblePivot::NotifyOfPivotChange(Accessible* aOldPosition,
 852                                        int32_t aOldStart, int32_t aOldEnd,
 853                                        int16_t aReason, bool aIsFromUserInput)
 854 {
 855   if (aOldPosition == mPosition &&
 856       aOldStart == mStartOffset && aOldEnd == mEndOffset)
 857     return false;
 858
 859   nsTObserverArray<nsCOMPtr<nsIAccessiblePivotObserver> >::ForwardIterator iter(mObservers);
 860   while (iter.HasMore()) {
 861     nsIAccessiblePivotObserver* obs = iter.GetNext();
 862     obs->OnPivotChanged(this, aOldPosition, aOldStart, aOldEnd, aReason,
 863                         aIsFromUserInput);
 864   }
 865
 866   return true;
 867 }
 868
 869 nsresult
 870 RuleCache::ApplyFilter(Accessible* aAccessible, uint16_t* aResult)
 871 {
 872   *aResult = nsIAccessibleTraversalRule::FILTER_IGNORE;
 873
 874   if (!mAcceptRoles) {
 875     nsresult rv = mRule->GetMatchRoles(&mAcceptRoles, &mAcceptRolesLength);
 876     NS_ENSURE_SUCCESS(rv, rv);
 877     rv = mRule->GetPreFilter(&mPreFilter);
 878     NS_ENSURE_SUCCESS(rv, rv);
 879   }
 880
 881   if (mPreFilter) {
 882     uint64_t state = aAccessible->State();
 883
 884     if ((nsIAccessibleTraversalRule::PREFILTER_INVISIBLE & mPreFilter) &&
 885         (state & states::INVISIBLE))
 886       return NS_OK;
 887
 888     if ((nsIAccessibleTraversalRule::PREFILTER_OFFSCREEN & mPreFilter) &&
 889         (state & states::OFFSCREEN))
 890       return NS_OK;
 891
 892     if ((nsIAccessibleTraversalRule::PREFILTER_NOT_FOCUSABLE & mPreFilter) &&
 893         !(state & states::FOCUSABLE))
 894       return NS_OK;
 895
 896     if (nsIAccessibleTraversalRule::PREFILTER_ARIA_HIDDEN & mPreFilter) {
 897       nsIContent* content = aAccessible->GetContent();
 898       if (content &&
 899           nsAccUtils::HasDefinedARIAToken(content, nsGkAtoms::aria_hidden) &&
 900           !content->AttrValueIs(kNameSpaceID_None, nsGkAtoms::aria_hidden,
 901                                 nsGkAtoms::_false, eCaseMatters)) {
 902         *aResult |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
 903         return NS_OK;
 904       }
 905     }
 906
 907     if ((nsIAccessibleTraversalRule::PREFILTER_TRANSPARENT & mPreFilter) &&
 908         !(state & states::OPAQUE1)) {
 909       nsIFrame* frame = aAccessible->GetFrame();
 910       if (frame->StyleDisplay()->mOpacity == 0.0f) {
 911         *aResult |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
 912         return NS_OK;
 913       }
 914     }
 915   }
 916
 917   if (mAcceptRolesLength > 0) {
 918     uint32_t accessibleRole = aAccessible->Role();
 919     bool matchesRole = false;
 920     for (uint32_t idx = 0; idx < mAcceptRolesLength; idx++) {
 921       matchesRole = mAcceptRoles[idx] == accessibleRole;
 922       if (matchesRole)
 923         break;
 924     }
 925     if (!matchesRole)
 926       return NS_OK;
 927   }
 928
 929   return mRule->Match(aAccessible, aResult);
 930 }