dom/base/TreeWalker.cpp

   1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
   2 /* vim: set ts=4 et sw=4 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 nsIDOMTreeWalker
   9  */
  10
  11 #include "mozilla/dom/TreeWalker.h"
  12
  13 #include "nsIContent.h"
  14 #include "nsIDOMNode.h"
  15 #include "nsError.h"
  16 #include "nsINode.h"
  17 #include "nsContentUtils.h"
  18 #include "mozilla/dom/TreeWalkerBinding.h"
  19
  20 namespace mozilla {
  21 namespace dom {
  22
  23 /*
  24  * Factories, constructors and destructors
  25  */
  26
  27 TreeWalker::TreeWalker(nsINode *aRoot,
  28                        uint32_t aWhatToShow,
  29                        const NodeFilterHolder &aFilter) :
  30     nsTraversal(aRoot, aWhatToShow, aFilter),
  31     mCurrentNode(aRoot)
  32 {
  33 }
  34
  35 TreeWalker::~TreeWalker()
  36 {
  37     /* destructor code */
  38 }
  39
  40 /*
  41  * nsISupports and cycle collection stuff
  42  */
  43
  44 NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)
  45
  46 // QueryInterface implementation for TreeWalker
  47 NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
  48     NS_INTERFACE_MAP_ENTRY(nsIDOMTreeWalker)
  49     NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIDOMTreeWalker)
  50 NS_INTERFACE_MAP_END
  51
  52 // Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
  53 // passes TreeWalker so refcount logging would get confused on the name
  54 // collision.
  55 NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
  56 NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)
  57
  58
  59
  60 /*
  61  * nsIDOMTreeWalker Getters/Setters
  62  */
  63
  64 /* readonly attribute nsIDOMNode root; */
  65 NS_IMETHODIMP TreeWalker::GetRoot(nsIDOMNode * *aRoot)
  66 {
  67     NS_ADDREF(*aRoot = Root()->AsDOMNode());
  68     return NS_OK;
  69 }
  70
  71 /* readonly attribute unsigned long whatToShow; */
  72 NS_IMETHODIMP TreeWalker::GetWhatToShow(uint32_t *aWhatToShow)
  73 {
  74     *aWhatToShow = WhatToShow();
  75     return NS_OK;
  76 }
  77
  78 /* readonly attribute nsIDOMNodeFilter filter; */
  79 NS_IMETHODIMP TreeWalker::GetFilter(nsIDOMNodeFilter * *aFilter)
  80 {
  81     NS_ENSURE_ARG_POINTER(aFilter);
  82
  83     *aFilter = mFilter.ToXPCOMCallback().take();
  84
  85     return NS_OK;
  86 }
  87
  88 /* attribute nsIDOMNode currentNode; */
  89 NS_IMETHODIMP TreeWalker::GetCurrentNode(nsIDOMNode * *aCurrentNode)
  90 {
  91     if (mCurrentNode) {
  92         return CallQueryInterface(mCurrentNode, aCurrentNode);
  93     }
  94
  95     *aCurrentNode = nullptr;
  96
  97     return NS_OK;
  98 }
  99 NS_IMETHODIMP TreeWalker::SetCurrentNode(nsIDOMNode * aCurrentNode)
 100 {
 101     NS_ENSURE_TRUE(aCurrentNode, NS_ERROR_DOM_NOT_SUPPORTED_ERR);
 102     NS_ENSURE_TRUE(mRoot, NS_ERROR_UNEXPECTED);
 103
 104     nsCOMPtr<nsINode> node = do_QueryInterface(aCurrentNode);
 105     NS_ENSURE_TRUE(node, NS_ERROR_UNEXPECTED);
 106
 107     ErrorResult rv;
 108     SetCurrentNode(*node, rv);
 109     return rv.ErrorCode();
 110 }
 111
 112 void
 113 TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult)
 114 {
 115     aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
 116     if (aResult.Failed()) {
 117         return;
 118     }
 119
 120     mCurrentNode = &aNode;
 121 }
 122
 123 /*
 124  * nsIDOMTreeWalker functions
 125  */
 126
 127 /* nsIDOMNode parentNode (); */
 128 NS_IMETHODIMP TreeWalker::ParentNode(nsIDOMNode **_retval)
 129 {
 130     return ImplNodeGetter(&TreeWalker::ParentNode, _retval);
 131 }
 132
 133 already_AddRefed<nsINode>
 134 TreeWalker::ParentNode(ErrorResult& aResult)
 135 {
 136     nsCOMPtr<nsINode> node = mCurrentNode;
 137
 138     while (node && node != mRoot) {
 139         node = node->GetParentNode();
 140
 141         if (node) {
 142             int16_t filtered = TestNode(node, aResult);
 143             if (aResult.Failed()) {
 144                 return nullptr;
 145             }
 146             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
 147                 mCurrentNode = node;
 148                 return node.forget();
 149             }
 150         }
 151     }
 152
 153     return nullptr;
 154 }
 155
 156 /* nsIDOMNode firstChild (); */
 157 NS_IMETHODIMP TreeWalker::FirstChild(nsIDOMNode **_retval)
 158 {
 159     return ImplNodeGetter(&TreeWalker::FirstChild, _retval);
 160 }
 161
 162 already_AddRefed<nsINode>
 163 TreeWalker::FirstChild(ErrorResult& aResult)
 164 {
 165     return FirstChildInternal(false, aResult);
 166 }
 167
 168 /* nsIDOMNode lastChild (); */
 169 NS_IMETHODIMP TreeWalker::LastChild(nsIDOMNode **_retval)
 170 {
 171     return ImplNodeGetter(&TreeWalker::LastChild, _retval);
 172 }
 173
 174 already_AddRefed<nsINode>
 175 TreeWalker::LastChild(ErrorResult& aResult)
 176 {
 177     return FirstChildInternal(true, aResult);
 178 }
 179
 180 /* nsIDOMNode previousSibling (); */
 181 NS_IMETHODIMP TreeWalker::PreviousSibling(nsIDOMNode **_retval)
 182 {
 183     return ImplNodeGetter(&TreeWalker::PreviousSibling, _retval);
 184 }
 185
 186 already_AddRefed<nsINode>
 187 TreeWalker::PreviousSibling(ErrorResult& aResult)
 188 {
 189     return NextSiblingInternal(true, aResult);
 190 }
 191
 192 /* nsIDOMNode nextSibling (); */
 193 NS_IMETHODIMP TreeWalker::NextSibling(nsIDOMNode **_retval)
 194 {
 195     return ImplNodeGetter(&TreeWalker::NextSibling, _retval);
 196 }
 197
 198 already_AddRefed<nsINode>
 199 TreeWalker::NextSibling(ErrorResult& aResult)
 200 {
 201     return NextSiblingInternal(false, aResult);
 202 }
 203
 204 /* nsIDOMNode previousNode (); */
 205 NS_IMETHODIMP TreeWalker::PreviousNode(nsIDOMNode **_retval)
 206 {
 207     return ImplNodeGetter(&TreeWalker::PreviousNode, _retval);
 208 }
 209
 210 already_AddRefed<nsINode>
 211 TreeWalker::PreviousNode(ErrorResult& aResult)
 212 {
 213     nsCOMPtr<nsINode> node = mCurrentNode;
 214
 215     while (node != mRoot) {
 216         while (nsINode *previousSibling = node->GetPreviousSibling()) {
 217             node = previousSibling;
 218
 219             int16_t filtered = TestNode(node, aResult);
 220             if (aResult.Failed()) {
 221                 return nullptr;
 222             }
 223
 224             nsINode *lastChild;
 225             while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
 226                    (lastChild = node->GetLastChild())) {
 227                 node = lastChild;
 228                 filtered = TestNode(node, aResult);
 229                 if (aResult.Failed()) {
 230                     return nullptr;
 231                 }
 232             }
 233
 234             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
 235                 mCurrentNode = node;
 236                 return node.forget();
 237             }
 238         }
 239
 240         if (node == mRoot) {
 241             break;
 242         }
 243
 244         node = node->GetParentNode();
 245         if (!node) {
 246             break;
 247         }
 248
 249         int16_t filtered = TestNode(node, aResult);
 250         if (aResult.Failed()) {
 251             return nullptr;
 252         }
 253
 254         if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
 255             mCurrentNode = node;
 256             return node.forget();
 257         }
 258     }
 259
 260     return nullptr;
 261 }
 262
 263 /* nsIDOMNode nextNode (); */
 264 NS_IMETHODIMP TreeWalker::NextNode(nsIDOMNode **_retval)
 265 {
 266     return ImplNodeGetter(&TreeWalker::NextNode, _retval);
 267 }
 268
 269 already_AddRefed<nsINode>
 270 TreeWalker::NextNode(ErrorResult& aResult)
 271 {
 272     int16_t filtered = nsIDOMNodeFilter::FILTER_ACCEPT; // pre-init for inner loop
 273
 274     nsCOMPtr<nsINode> node = mCurrentNode;
 275
 276     while (1) {
 277
 278         nsINode *firstChild;
 279         while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
 280                (firstChild = node->GetFirstChild())) {
 281             node = firstChild;
 282
 283             filtered = TestNode(node, aResult);
 284             if (aResult.Failed()) {
 285                 return nullptr;
 286             }
 287
 288             if (filtered ==  nsIDOMNodeFilter::FILTER_ACCEPT) {
 289                 // Node found
 290                 mCurrentNode = node;
 291                 return node.forget();
 292             }
 293         }
 294
 295         nsINode *sibling = nullptr;
 296         nsINode *temp = node;
 297         do {
 298             if (temp == mRoot)
 299                 break;
 300
 301             sibling = temp->GetNextSibling();
 302             if (sibling)
 303                 break;
 304
 305             temp = temp->GetParentNode();
 306         } while (temp);
 307
 308         if (!sibling)
 309             break;
 310
 311         node = sibling;
 312
 313         // Found a sibling. Either ours or ancestor's
 314         filtered = TestNode(node, aResult);
 315         if (aResult.Failed()) {
 316             return nullptr;
 317         }
 318
 319         if (filtered ==  nsIDOMNodeFilter::FILTER_ACCEPT) {
 320             // Node found
 321             mCurrentNode = node;
 322             return node.forget();
 323         }
 324     }
 325
 326     return nullptr;
 327 }
 328
 329 /*
 330  * TreeWalker helper functions
 331  */
 332
 333 /*
 334  * Implements FirstChild and LastChild which only vary in which direction
 335  * they search.
 336  * @param aReversed Controls whether we search forwards or backwards
 337  * @param aResult   Whether we threw or not.
 338  * @returns         The desired node. Null if no child is found
 339  */
 340 already_AddRefed<nsINode>
 341 TreeWalker::FirstChildInternal(bool aReversed, ErrorResult& aResult)
 342 {
 343     nsCOMPtr<nsINode> node = aReversed ? mCurrentNode->GetLastChild()
 344                                        : mCurrentNode->GetFirstChild();
 345
 346     while (node) {
 347         int16_t filtered = TestNode(node, aResult);
 348         if (aResult.Failed()) {
 349             return nullptr;
 350         }
 351
 352         switch (filtered) {
 353             case nsIDOMNodeFilter::FILTER_ACCEPT:
 354                 // Node found
 355                 mCurrentNode = node;
 356                 return node.forget();
 357             case nsIDOMNodeFilter::FILTER_SKIP: {
 358                     nsINode *child = aReversed ? node->GetLastChild()
 359                                                : node->GetFirstChild();
 360                     if (child) {
 361                         node = child;
 362                         continue;
 363                     }
 364                     break;
 365                 }
 366             case nsIDOMNodeFilter::FILTER_REJECT:
 367                 // Keep searching
 368                 break;
 369         }
 370
 371         do {
 372             nsINode *sibling = aReversed ? node->GetPreviousSibling()
 373                                          : node->GetNextSibling();
 374             if (sibling) {
 375                 node = sibling;
 376                 break;
 377             }
 378
 379             nsINode *parent = node->GetParentNode();
 380
 381             if (!parent || parent == mRoot || parent == mCurrentNode) {
 382                 return nullptr;
 383             }
 384
 385             node = parent;
 386
 387         } while (node);
 388     }
 389
 390     return nullptr;
 391 }
 392
 393 /*
 394  * Implements NextSibling and PreviousSibling which only vary in which
 395  * direction they search.
 396  * @param aReversed Controls whether we search forwards or backwards
 397  * @param aResult   Whether we threw or not.
 398  * @returns         The desired node. Null if no child is found
 399  */
 400 already_AddRefed<nsINode>
 401 TreeWalker::NextSiblingInternal(bool aReversed, ErrorResult& aResult)
 402 {
 403     nsCOMPtr<nsINode> node = mCurrentNode;
 404
 405     if (node == mRoot) {
 406         return nullptr;
 407     }
 408
 409     while (1) {
 410         nsINode* sibling = aReversed ? node->GetPreviousSibling()
 411                                      : node->GetNextSibling();
 412
 413         while (sibling) {
 414             node = sibling;
 415
 416             int16_t filtered = TestNode(node, aResult);
 417             if (aResult.Failed()) {
 418                 return nullptr;
 419             }
 420
 421             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
 422                 // Node found
 423                 mCurrentNode = node;
 424                 return node.forget();
 425             }
 426
 427             // If rejected or no children, try a sibling
 428             if (filtered == nsIDOMNodeFilter::FILTER_REJECT ||
 429                 !(sibling = aReversed ? node->GetLastChild()
 430                                       : node->GetFirstChild())) {
 431                 sibling = aReversed ? node->GetPreviousSibling()
 432                                     : node->GetNextSibling();
 433             }
 434         }
 435
 436         node = node->GetParentNode();
 437
 438         if (!node || node == mRoot) {
 439             return nullptr;
 440         }
 441
 442         // Is parent transparent in filtered view?
 443         int16_t filtered = TestNode(node, aResult);
 444         if (aResult.Failed()) {
 445             return nullptr;
 446         }
 447         if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
 448             return nullptr;
 449         }
 450     }
 451 }
 452
 453 JSObject*
 454 TreeWalker::WrapObject(JSContext *cx)
 455 {
 456     return TreeWalkerBinding::Wrap(cx, this);
 457 }
 458
 459 } // namespace dom
 460 } // namespace mozilla