tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

TreeWalker.cpp (9479B)

      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 "ARIAMap.h"
      9 #include "nsAccessibilityService.h"
     10 #include "DocAccessible.h"
     11 
     12 #include "mozilla/dom/ChildIterator.h"
     13 #include "mozilla/dom/Element.h"
     14 
     15 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      !aria::IsValidARIAHidden(mDoc)) {
    329    mDoc->RelocateARIAOwnedIfNeeded(aNode);
    330    return GetAccService()->CreateAccessible(aNode, mContext, aSkipSubtree);
    331  }
    332 
    333  return nullptr;
    334 }
    335 
    336 dom::AllChildrenIterator* TreeWalker::PopState() {
    337  mStateStack.RemoveLastElement();
    338  return mStateStack.IsEmpty() ? nullptr : &mStateStack.LastElement();
    339 }
    340 
    341 }  // namespace mozilla::a11y