dom/base/TreeWalker.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=4 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 /*
   8  * Implementation of DOM Traversal's TreeWalker
   9  */
  10
  11 #include "mozilla/dom/TreeWalker.h"
  12
  13 #include "nsIContent.h"
  14 #include "nsError.h"
  15 #include "nsINode.h"
  16 #include "nsContentUtils.h"
  17 #include "mozilla/dom/NodeFilterBinding.h"
  18 #include "mozilla/dom/TreeWalkerBinding.h"
  19
  20 namespace mozilla::dom {
  21
  22 /*
  23  * Factories, constructors and destructors
  24  */
  25
  26 TreeWalker::TreeWalker(nsINode* aRoot, uint32_t aWhatToShow,
  27                        NodeFilter* aFilter)
  28     : nsTraversal(aRoot, aWhatToShow, aFilter), mCurrentNode(aRoot) {}
  29
  30 TreeWalker::~TreeWalker() { /* destructor code */
  31 }
  32
  33 /*
  34  * nsISupports and cycle collection stuff
  35  */
  36
  37 NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)
  38
  39 // QueryInterface implementation for TreeWalker
  40 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
  41   NS_INTERFACE_MAP_ENTRY(nsISupports)
  42 NS_INTERFACE_MAP_END
  43
  44 // Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
  45 // passes TreeWalker so refcount logging would get confused on the name
  46 // collision.
  47 NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
  48 NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)
  49
  50 void TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult) {
  51   aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
  52   if (aResult.Failed()) {
  53     return;
  54   }
  55
  56   mCurrentNode = &aNode;
  57 }
  58
  59 already_AddRefed<nsINode> TreeWalker::ParentNode(ErrorResult& aResult) {
  60   nsCOMPtr<nsINode> node = mCurrentNode;
  61
  62   while (node && node != mRoot) {
  63     node = node->GetParentNode();
  64
  65     if (node) {
  66       int16_t filtered = TestNode(node, aResult);
  67       if (aResult.Failed()) {
  68         return nullptr;
  69       }
  70       if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
  71         mCurrentNode = node;
  72         return node.forget();
  73       }
  74     }
  75   }
  76
  77   return nullptr;
  78 }
  79
  80 already_AddRefed<nsINode> TreeWalker::FirstChild(ErrorResult& aResult) {
  81   return FirstChildInternal(false, aResult);
  82 }
  83
  84 already_AddRefed<nsINode> TreeWalker::LastChild(ErrorResult& aResult) {
  85   return FirstChildInternal(true, aResult);
  86 }
  87
  88 already_AddRefed<nsINode> TreeWalker::PreviousSibling(ErrorResult& aResult) {
  89   return NextSiblingInternal(true, aResult);
  90 }
  91
  92 already_AddRefed<nsINode> TreeWalker::NextSibling(ErrorResult& aResult) {
  93   return NextSiblingInternal(false, aResult);
  94 }
  95
  96 already_AddRefed<nsINode> TreeWalker::PreviousNode(ErrorResult& aResult) {
  97   nsCOMPtr<nsINode> node = mCurrentNode;
  98
  99   while (node != mRoot) {
 100     while (nsINode* previousSibling = node->GetPreviousSibling()) {
 101       node = previousSibling;
 102
 103       int16_t filtered = TestNode(node, aResult);
 104       if (aResult.Failed()) {
 105         return nullptr;
 106       }
 107
 108       nsINode* lastChild;
 109       while (filtered != NodeFilter_Binding::FILTER_REJECT &&
 110              (lastChild = node->GetLastChild())) {
 111         node = lastChild;
 112         filtered = TestNode(node, aResult);
 113         if (aResult.Failed()) {
 114           return nullptr;
 115         }
 116       }
 117
 118       if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 119         mCurrentNode = node;
 120         return node.forget();
 121       }
 122     }
 123
 124     if (node == mRoot) {
 125       break;
 126     }
 127
 128     node = node->GetParentNode();
 129     if (!node) {
 130       break;
 131     }
 132
 133     int16_t filtered = TestNode(node, aResult);
 134     if (aResult.Failed()) {
 135       return nullptr;
 136     }
 137
 138     if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 139       mCurrentNode = node;
 140       return node.forget();
 141     }
 142   }
 143
 144   return nullptr;
 145 }
 146
 147 already_AddRefed<nsINode> TreeWalker::NextNode(ErrorResult& aResult) {
 148   int16_t filtered =
 149       NodeFilter_Binding::FILTER_ACCEPT;  // pre-init for inner loop
 150
 151   nsCOMPtr<nsINode> node = mCurrentNode;
 152
 153   while (1) {
 154     nsINode* firstChild;
 155     while (filtered != NodeFilter_Binding::FILTER_REJECT &&
 156            (firstChild = node->GetFirstChild())) {
 157       node = firstChild;
 158
 159       filtered = TestNode(node, aResult);
 160       if (aResult.Failed()) {
 161         return nullptr;
 162       }
 163
 164       if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 165         // Node found
 166         mCurrentNode = node;
 167         return node.forget();
 168       }
 169     }
 170
 171     nsINode* sibling = nullptr;
 172     nsINode* temp = node;
 173     do {
 174       if (temp == mRoot) break;
 175
 176       sibling = temp->GetNextSibling();
 177       if (sibling) break;
 178
 179       temp = temp->GetParentNode();
 180     } while (temp);
 181
 182     if (!sibling) break;
 183
 184     node = sibling;
 185
 186     // Found a sibling. Either ours or ancestor's
 187     filtered = TestNode(node, aResult);
 188     if (aResult.Failed()) {
 189       return nullptr;
 190     }
 191
 192     if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 193       // Node found
 194       mCurrentNode = node;
 195       return node.forget();
 196     }
 197   }
 198
 199   return nullptr;
 200 }
 201
 202 /*
 203  * TreeWalker helper functions
 204  */
 205
 206 /*
 207  * Implements FirstChild and LastChild which only vary in which direction
 208  * they search.
 209  * @param aReversed Controls whether we search forwards or backwards
 210  * @param aResult   Whether we threw or not.
 211  * @returns         The desired node. Null if no child is found
 212  */
 213 already_AddRefed<nsINode> TreeWalker::FirstChildInternal(bool aReversed,
 214                                                          ErrorResult& aResult) {
 215   nsCOMPtr<nsINode> node =
 216       aReversed ? mCurrentNode->GetLastChild() : mCurrentNode->GetFirstChild();
 217
 218   while (node) {
 219     int16_t filtered = TestNode(node, aResult);
 220     if (aResult.Failed()) {
 221       return nullptr;
 222     }
 223
 224     switch (filtered) {
 225       case NodeFilter_Binding::FILTER_ACCEPT:
 226         // Node found
 227         mCurrentNode = node;
 228         return node.forget();
 229       case NodeFilter_Binding::FILTER_SKIP: {
 230         nsINode* child =
 231             aReversed ? node->GetLastChild() : node->GetFirstChild();
 232         if (child) {
 233           node = child;
 234           continue;
 235         }
 236         break;
 237       }
 238       case NodeFilter_Binding::FILTER_REJECT:
 239         // Keep searching
 240         break;
 241     }
 242
 243     do {
 244       nsINode* sibling =
 245           aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
 246       if (sibling) {
 247         node = sibling;
 248         break;
 249       }
 250
 251       nsINode* parent = node->GetParentNode();
 252
 253       if (!parent || parent == mRoot || parent == mCurrentNode) {
 254         return nullptr;
 255       }
 256
 257       node = parent;
 258
 259     } while (node);
 260   }
 261
 262   return nullptr;
 263 }
 264
 265 /*
 266  * Implements NextSibling and PreviousSibling which only vary in which
 267  * direction they search.
 268  * @param aReversed Controls whether we search forwards or backwards
 269  * @param aResult   Whether we threw or not.
 270  * @returns         The desired node. Null if no child is found
 271  */
 272 already_AddRefed<nsINode> TreeWalker::NextSiblingInternal(
 273     bool aReversed, ErrorResult& aResult) {
 274   nsCOMPtr<nsINode> node = mCurrentNode;
 275
 276   if (node == mRoot) {
 277     return nullptr;
 278   }
 279
 280   while (1) {
 281     nsINode* sibling =
 282         aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
 283
 284     while (sibling) {
 285       node = sibling;
 286
 287       int16_t filtered = TestNode(node, aResult);
 288       if (aResult.Failed()) {
 289         return nullptr;
 290       }
 291
 292       if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 293         // Node found
 294         mCurrentNode = node;
 295         return node.forget();
 296       }
 297
 298       // If rejected or no children, try a sibling
 299       if (filtered == NodeFilter_Binding::FILTER_REJECT ||
 300           !(sibling =
 301                 aReversed ? node->GetLastChild() : node->GetFirstChild())) {
 302         sibling =
 303             aReversed ? node->GetPreviousSibling() : node->GetNextSibling();
 304       }
 305     }
 306
 307     node = node->GetParentNode();
 308
 309     if (!node || node == mRoot) {
 310       return nullptr;
 311     }
 312
 313     // Is parent transparent in filtered view?
 314     int16_t filtered = TestNode(node, aResult);
 315     if (aResult.Failed()) {
 316       return nullptr;
 317     }
 318     if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
 319       return nullptr;
 320     }
 321   }
 322 }
 323
 324 bool TreeWalker::WrapObject(JSContext* aCx, JS::Handle<JSObject*> aGivenProto,
 325                             JS::MutableHandle<JSObject*> aReflector) {
 326   return TreeWalker_Binding::Wrap(aCx, this, aGivenProto, aReflector);
 327 }
 328
 329 }  // namespace mozilla::dom