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