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