accessible/base/TreeWalker.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "TreeWalker.h"
   7
   8 #include "nsAccessibilityService.h"
   9 #include "DocAccessible.h"
  10
  11 #include "mozilla/dom/ChildIterator.h"
  12 #include "mozilla/dom/Element.h"
  13
  14 using namespace mozilla;
  15 using namespace mozilla::a11y;
  16
  17 ////////////////////////////////////////////////////////////////////////////////
  18 // TreeWalker
  19 ////////////////////////////////////////////////////////////////////////////////
  20
  21 TreeWalker::TreeWalker(LocalAccessible* aContext)
  22     : mDoc(aContext->Document()),
  23       mContext(aContext),
  24       mAnchorNode(nullptr),
  25       mARIAOwnsIdx(0),
  26       mChildFilter(nsIContent::eSkipPlaceholderContent),
  27       mFlags(0),
  28       mPhase(eAtStart) {
  29   mChildFilter |= nsIContent::eAllChildren;
  30
  31   mAnchorNode = mContext->IsDoc() ? mDoc->DocumentNode()->GetRootElement()
  32                                   : mContext->GetContent();
  33
  34   MOZ_COUNT_CTOR(TreeWalker);
  35 }
  36
  37 TreeWalker::TreeWalker(LocalAccessible* aContext, nsIContent* aAnchorNode,
  38                        uint32_t aFlags)
  39     : mDoc(aContext->Document()),
  40       mContext(aContext),
  41       mAnchorNode(aAnchorNode),
  42       mARIAOwnsIdx(0),
  43       mChildFilter(nsIContent::eSkipPlaceholderContent),
  44       mFlags(aFlags),
  45       mPhase(eAtStart) {
  46   MOZ_ASSERT(mFlags & eWalkCache,
  47              "This constructor cannot be used for tree creation");
  48   MOZ_ASSERT(aAnchorNode, "No anchor node for the accessible tree walker");
  49
  50   mChildFilter |= nsIContent::eAllChildren;
  51
  52   MOZ_COUNT_CTOR(TreeWalker);
  53 }
  54
  55 TreeWalker::TreeWalker(DocAccessible* aDocument, nsIContent* aAnchorNode)
  56     : mDoc(aDocument),
  57       mContext(nullptr),
  58       mAnchorNode(aAnchorNode),
  59       mARIAOwnsIdx(0),
  60       mChildFilter(nsIContent::eSkipPlaceholderContent |
  61                    nsIContent::eAllChildren),
  62       mFlags(eWalkCache),
  63       mPhase(eAtStart) {
  64   MOZ_ASSERT(aAnchorNode, "No anchor node for the accessible tree walker");
  65   MOZ_COUNT_CTOR(TreeWalker);
  66 }
  67
  68 TreeWalker::~TreeWalker() { MOZ_COUNT_DTOR(TreeWalker); }
  69
  70 LocalAccessible* TreeWalker::Scope(nsIContent* aAnchorNode) {
  71   Reset();
  72
  73   mAnchorNode = aAnchorNode;
  74
  75   mFlags |= eScoped;
  76
  77   bool skipSubtree = false;
  78   LocalAccessible* acc = AccessibleFor(aAnchorNode, 0, &skipSubtree);
  79   if (acc) {
  80     mPhase = eAtEnd;
  81     return acc;
  82   }
  83
  84   return skipSubtree ? nullptr : Next();
  85 }
  86
  87 bool TreeWalker::Seek(nsIContent* aChildNode) {
  88   MOZ_ASSERT(aChildNode, "Child cannot be null");
  89
  90   Reset();
  91
  92   if (mAnchorNode == aChildNode) {
  93     return true;
  94   }
  95
  96   nsIContent* childNode = nullptr;
  97   nsINode* parentNode = aChildNode;
  98   do {
  99     childNode = parentNode->AsContent();
 100     parentNode = childNode->GetFlattenedTreeParent();
 101
 102     // Handle the special case of XBL binding child under a shadow root.
 103     if (parentNode && parentNode->IsShadowRoot()) {
 104       parentNode = childNode->GetFlattenedTreeParent();
 105       if (parentNode == mAnchorNode) {
 106         return true;
 107       }
 108       continue;
 109     }
 110
 111     if (!parentNode || !parentNode->IsElement()) {
 112       return false;
 113     }
 114
 115     // If ARIA owned child.
 116     LocalAccessible* child = mDoc->GetAccessible(childNode);
 117     if (child && child->IsRelocated()) {
 118       MOZ_ASSERT(
 119           !(mFlags & eScoped),
 120           "Walker should not be scoped when seeking into relocated children");
 121       if (child->LocalParent() != mContext) {
 122         return false;
 123       }
 124
 125       LocalAccessible* ownedChild = nullptr;
 126       while ((ownedChild = mDoc->ARIAOwnedAt(mContext, mARIAOwnsIdx++)) &&
 127              ownedChild != child) {
 128         ;
 129       }
 130
 131       MOZ_ASSERT(ownedChild, "A child has to be in ARIA owned elements");
 132       mPhase = eAtARIAOwns;
 133       return true;
 134     }
 135
 136     // Look in DOM.
 137     dom::AllChildrenIterator* iter =
 138         PrependState(parentNode->AsElement(), true);
 139     if (!iter->Seek(childNode)) {
 140       return false;
 141     }
 142
 143     if (parentNode == mAnchorNode) {
 144       mPhase = eAtDOM;
 145       return true;
 146     }
 147   } while (true);
 148
 149   MOZ_ASSERT_UNREACHABLE("because the do-while loop never breaks");
 150 }
 151
 152 LocalAccessible* TreeWalker::Next() {
 153   if (mStateStack.IsEmpty()) {
 154     if (mPhase == eAtEnd) {
 155       return nullptr;
 156     }
 157
 158     if (mPhase == eAtDOM || mPhase == eAtARIAOwns) {
 159       if (!(mFlags & eScoped)) {
 160         mPhase = eAtARIAOwns;
 161         LocalAccessible* child = mDoc->ARIAOwnedAt(mContext, mARIAOwnsIdx);
 162         if (child) {
 163           mARIAOwnsIdx++;
 164           return child;
 165         }
 166       }
 167       MOZ_ASSERT(!(mFlags & eScoped) || mPhase != eAtARIAOwns,
 168                  "Don't walk relocated children in scoped mode");
 169       mPhase = eAtEnd;
 170       return nullptr;
 171     }
 172
 173     if (!mAnchorNode) {
 174       mPhase = eAtEnd;
 175       return nullptr;
 176     }
 177
 178     mPhase = eAtDOM;
 179     PushState(mAnchorNode, true);
 180   }
 181
 182   dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
 183   while (top) {
 184     while (nsIContent* childNode = top->GetNextChild()) {
 185       bool skipSubtree = false;
 186       LocalAccessible* child = AccessibleFor(childNode, mFlags, &skipSubtree);
 187       if (child) {
 188         return child;
 189       }
 190
 191       // Walk down the subtree if allowed.
 192       if (!skipSubtree && childNode->IsElement()) {
 193         top = PushState(childNode, true);
 194       }
 195     }
 196     top = PopState();
 197   }
 198
 199   // If we traversed the whole subtree of the anchor node. Move to next node
 200   // relative anchor node within the context subtree if asked.
 201   if (mFlags != eWalkContextTree) {
 202     // eWalkCache flag presence indicates that the search is scoped to the
 203     // anchor (no ARIA owns stuff).
 204     if (mFlags & eWalkCache) {
 205       mPhase = eAtEnd;
 206       return nullptr;
 207     }
 208     return Next();
 209   }
 210
 211   nsINode* contextNode = mContext->GetNode();
 212   while (mAnchorNode != contextNode) {
 213     nsINode* parentNode = mAnchorNode->GetFlattenedTreeParent();
 214     if (!parentNode || !parentNode->IsElement()) return nullptr;
 215
 216     nsIContent* parent = parentNode->AsElement();
 217     top = PushState(parent, true);
 218     if (top->Seek(mAnchorNode)) {
 219       mAnchorNode = parent;
 220       return Next();
 221     }
 222
 223     // XXX We really should never get here, it means we're trying to find an
 224     // accessible for a dom node where iterating over its parent's children
 225     // doesn't return it. However this sometimes happens when we're asked for
 226     // the nearest accessible to place holder content which we ignore.
 227     mAnchorNode = parent;
 228   }
 229
 230   return Next();
 231 }
 232
 233 LocalAccessible* TreeWalker::Prev() {
 234   if (mStateStack.IsEmpty()) {
 235     if (mPhase == eAtStart || mPhase == eAtDOM) {
 236       mPhase = eAtStart;
 237       return nullptr;
 238     }
 239
 240     if (mPhase == eAtEnd) {
 241       if (mFlags & eScoped) {
 242         mPhase = eAtDOM;
 243       } else {
 244         mPhase = eAtARIAOwns;
 245         mARIAOwnsIdx = mDoc->ARIAOwnedCount(mContext);
 246       }
 247     }
 248
 249     if (mPhase == eAtARIAOwns) {
 250       MOZ_ASSERT(!(mFlags & eScoped),
 251                  "Should not walk relocated children in scoped mode");
 252       if (mARIAOwnsIdx > 0) {
 253         return mDoc->ARIAOwnedAt(mContext, --mARIAOwnsIdx);
 254       }
 255
 256       if (!mAnchorNode) {
 257         mPhase = eAtStart;
 258         return nullptr;
 259       }
 260
 261       mPhase = eAtDOM;
 262       PushState(mAnchorNode, false);
 263     }
 264   }
 265
 266   dom::AllChildrenIterator* top = &mStateStack[mStateStack.Length() - 1];
 267   while (top) {
 268     while (nsIContent* childNode = top->GetPreviousChild()) {
 269       // No accessible creation on the way back.
 270       bool skipSubtree = false;
 271       LocalAccessible* child =
 272           AccessibleFor(childNode, eWalkCache, &skipSubtree);
 273       if (child) {
 274         return child;
 275       }
 276
 277       // Walk down into subtree to find accessibles.
 278       if (!skipSubtree && childNode->IsElement()) {
 279         top = PushState(childNode, false);
 280       }
 281     }
 282     top = PopState();
 283   }
 284
 285   // Move to a previous node relative the anchor node within the context
 286   // subtree if asked.
 287   if (mFlags != eWalkContextTree) {
 288     mPhase = eAtStart;
 289     return nullptr;
 290   }
 291
 292   nsINode* contextNode = mContext->GetNode();
 293   while (mAnchorNode != contextNode) {
 294     nsINode* parentNode = mAnchorNode->GetFlattenedTreeParent();
 295     if (!parentNode || !parentNode->IsElement()) {
 296       return nullptr;
 297     }
 298
 299     nsIContent* parent = parentNode->AsElement();
 300     top = PushState(parent, true);
 301     if (top->Seek(mAnchorNode)) {
 302       mAnchorNode = parent;
 303       return Prev();
 304     }
 305
 306     mAnchorNode = parent;
 307   }
 308
 309   mPhase = eAtStart;
 310   return nullptr;
 311 }
 312
 313 LocalAccessible* TreeWalker::AccessibleFor(nsIContent* aNode, uint32_t aFlags,
 314                                            bool* aSkipSubtree) {
 315   // Ignore the accessible and its subtree if it was repositioned by means
 316   // of aria-owns.
 317   LocalAccessible* child = mDoc->GetAccessible(aNode);
 318   if (child) {
 319     if (child->IsRelocated()) {
 320       *aSkipSubtree = true;
 321       return nullptr;
 322     }
 323     return child;
 324   }
 325
 326   // Create an accessible if allowed.
 327   if (!(aFlags & eWalkCache) && mContext->IsAcceptableChild(aNode)) {
 328     // We may have ARIA owned element in the dependent attributes map, but the
 329     // element may be not allowed for this ARIA owns relation, if the relation
 330     // crosses out XBL anonymous content boundaries. In this case we won't
 331     // create an accessible object for it, when aria-owns is processed, which
 332     // may make the element subtree inaccessible. To avoid that let's create
 333     // an accessible object now, and later, if allowed, move it in the tree,
 334     // when aria-owns relation is processed.
 335     if (mDoc->RelocateARIAOwnedIfNeeded(aNode) && !aNode->IsXULElement()) {
 336       *aSkipSubtree = true;
 337       return nullptr;
 338     }
 339     return GetAccService()->CreateAccessible(aNode, mContext, aSkipSubtree);
 340   }
 341
 342   return nullptr;
 343 }
 344
 345 dom::AllChildrenIterator* TreeWalker::PopState() {
 346   mStateStack.RemoveLastElement();
 347   return mStateStack.IsEmpty() ? nullptr : &mStateStack.LastElement();
 348 }