1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/base/src/TreeWalker.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,460 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +/* vim: set ts=4 et sw=4 tw=80: */
1.6 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +/*
1.11 + * Implementation of DOM Traversal's nsIDOMTreeWalker
1.12 + */
1.13 +
1.14 +#include "mozilla/dom/TreeWalker.h"
1.15 +
1.16 +#include "nsIContent.h"
1.17 +#include "nsIDOMNode.h"
1.18 +#include "nsError.h"
1.19 +#include "nsINode.h"
1.20 +#include "nsContentUtils.h"
1.21 +#include "mozilla/dom/TreeWalkerBinding.h"
1.22 +
1.23 +namespace mozilla {
1.24 +namespace dom {
1.25 +
1.26 +/*
1.27 + * Factories, constructors and destructors
1.28 + */
1.29 +
1.30 +TreeWalker::TreeWalker(nsINode *aRoot,
1.31 + uint32_t aWhatToShow,
1.32 + const NodeFilterHolder &aFilter) :
1.33 + nsTraversal(aRoot, aWhatToShow, aFilter),
1.34 + mCurrentNode(aRoot)
1.35 +{
1.36 +}
1.37 +
1.38 +TreeWalker::~TreeWalker()
1.39 +{
1.40 + /* destructor code */
1.41 +}
1.42 +
1.43 +/*
1.44 + * nsISupports and cycle collection stuff
1.45 + */
1.46 +
1.47 +NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)
1.48 +
1.49 +// QueryInterface implementation for TreeWalker
1.50 +NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
1.51 + NS_INTERFACE_MAP_ENTRY(nsIDOMTreeWalker)
1.52 + NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIDOMTreeWalker)
1.53 +NS_INTERFACE_MAP_END
1.54 +
1.55 +// Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
1.56 +// passes TreeWalker so refcount logging would get confused on the name
1.57 +// collision.
1.58 +NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
1.59 +NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)
1.60 +
1.61 +
1.62 +
1.63 +/*
1.64 + * nsIDOMTreeWalker Getters/Setters
1.65 + */
1.66 +
1.67 +/* readonly attribute nsIDOMNode root; */
1.68 +NS_IMETHODIMP TreeWalker::GetRoot(nsIDOMNode * *aRoot)
1.69 +{
1.70 + NS_ADDREF(*aRoot = Root()->AsDOMNode());
1.71 + return NS_OK;
1.72 +}
1.73 +
1.74 +/* readonly attribute unsigned long whatToShow; */
1.75 +NS_IMETHODIMP TreeWalker::GetWhatToShow(uint32_t *aWhatToShow)
1.76 +{
1.77 + *aWhatToShow = WhatToShow();
1.78 + return NS_OK;
1.79 +}
1.80 +
1.81 +/* readonly attribute nsIDOMNodeFilter filter; */
1.82 +NS_IMETHODIMP TreeWalker::GetFilter(nsIDOMNodeFilter * *aFilter)
1.83 +{
1.84 + NS_ENSURE_ARG_POINTER(aFilter);
1.85 +
1.86 + *aFilter = mFilter.ToXPCOMCallback().take();
1.87 +
1.88 + return NS_OK;
1.89 +}
1.90 +
1.91 +/* attribute nsIDOMNode currentNode; */
1.92 +NS_IMETHODIMP TreeWalker::GetCurrentNode(nsIDOMNode * *aCurrentNode)
1.93 +{
1.94 + if (mCurrentNode) {
1.95 + return CallQueryInterface(mCurrentNode, aCurrentNode);
1.96 + }
1.97 +
1.98 + *aCurrentNode = nullptr;
1.99 +
1.100 + return NS_OK;
1.101 +}
1.102 +NS_IMETHODIMP TreeWalker::SetCurrentNode(nsIDOMNode * aCurrentNode)
1.103 +{
1.104 + NS_ENSURE_TRUE(aCurrentNode, NS_ERROR_DOM_NOT_SUPPORTED_ERR);
1.105 + NS_ENSURE_TRUE(mRoot, NS_ERROR_UNEXPECTED);
1.106 +
1.107 + nsCOMPtr<nsINode> node = do_QueryInterface(aCurrentNode);
1.108 + NS_ENSURE_TRUE(node, NS_ERROR_UNEXPECTED);
1.109 +
1.110 + ErrorResult rv;
1.111 + SetCurrentNode(*node, rv);
1.112 + return rv.ErrorCode();
1.113 +}
1.114 +
1.115 +void
1.116 +TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult)
1.117 +{
1.118 + aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
1.119 + if (aResult.Failed()) {
1.120 + return;
1.121 + }
1.122 +
1.123 + mCurrentNode = &aNode;
1.124 +}
1.125 +
1.126 +/*
1.127 + * nsIDOMTreeWalker functions
1.128 + */
1.129 +
1.130 +/* nsIDOMNode parentNode (); */
1.131 +NS_IMETHODIMP TreeWalker::ParentNode(nsIDOMNode **_retval)
1.132 +{
1.133 + return ImplNodeGetter(&TreeWalker::ParentNode, _retval);
1.134 +}
1.135 +
1.136 +already_AddRefed<nsINode>
1.137 +TreeWalker::ParentNode(ErrorResult& aResult)
1.138 +{
1.139 + nsCOMPtr<nsINode> node = mCurrentNode;
1.140 +
1.141 + while (node && node != mRoot) {
1.142 + node = node->GetParentNode();
1.143 +
1.144 + if (node) {
1.145 + int16_t filtered = TestNode(node, aResult);
1.146 + if (aResult.Failed()) {
1.147 + return nullptr;
1.148 + }
1.149 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.150 + mCurrentNode = node;
1.151 + return node.forget();
1.152 + }
1.153 + }
1.154 + }
1.155 +
1.156 + return nullptr;
1.157 +}
1.158 +
1.159 +/* nsIDOMNode firstChild (); */
1.160 +NS_IMETHODIMP TreeWalker::FirstChild(nsIDOMNode **_retval)
1.161 +{
1.162 + return ImplNodeGetter(&TreeWalker::FirstChild, _retval);
1.163 +}
1.164 +
1.165 +already_AddRefed<nsINode>
1.166 +TreeWalker::FirstChild(ErrorResult& aResult)
1.167 +{
1.168 + return FirstChildInternal(false, aResult);
1.169 +}
1.170 +
1.171 +/* nsIDOMNode lastChild (); */
1.172 +NS_IMETHODIMP TreeWalker::LastChild(nsIDOMNode **_retval)
1.173 +{
1.174 + return ImplNodeGetter(&TreeWalker::LastChild, _retval);
1.175 +}
1.176 +
1.177 +already_AddRefed<nsINode>
1.178 +TreeWalker::LastChild(ErrorResult& aResult)
1.179 +{
1.180 + return FirstChildInternal(true, aResult);
1.181 +}
1.182 +
1.183 +/* nsIDOMNode previousSibling (); */
1.184 +NS_IMETHODIMP TreeWalker::PreviousSibling(nsIDOMNode **_retval)
1.185 +{
1.186 + return ImplNodeGetter(&TreeWalker::PreviousSibling, _retval);
1.187 +}
1.188 +
1.189 +already_AddRefed<nsINode>
1.190 +TreeWalker::PreviousSibling(ErrorResult& aResult)
1.191 +{
1.192 + return NextSiblingInternal(true, aResult);
1.193 +}
1.194 +
1.195 +/* nsIDOMNode nextSibling (); */
1.196 +NS_IMETHODIMP TreeWalker::NextSibling(nsIDOMNode **_retval)
1.197 +{
1.198 + return ImplNodeGetter(&TreeWalker::NextSibling, _retval);
1.199 +}
1.200 +
1.201 +already_AddRefed<nsINode>
1.202 +TreeWalker::NextSibling(ErrorResult& aResult)
1.203 +{
1.204 + return NextSiblingInternal(false, aResult);
1.205 +}
1.206 +
1.207 +/* nsIDOMNode previousNode (); */
1.208 +NS_IMETHODIMP TreeWalker::PreviousNode(nsIDOMNode **_retval)
1.209 +{
1.210 + return ImplNodeGetter(&TreeWalker::PreviousNode, _retval);
1.211 +}
1.212 +
1.213 +already_AddRefed<nsINode>
1.214 +TreeWalker::PreviousNode(ErrorResult& aResult)
1.215 +{
1.216 + nsCOMPtr<nsINode> node = mCurrentNode;
1.217 +
1.218 + while (node != mRoot) {
1.219 + while (nsINode *previousSibling = node->GetPreviousSibling()) {
1.220 + node = previousSibling;
1.221 +
1.222 + int16_t filtered = TestNode(node, aResult);
1.223 + if (aResult.Failed()) {
1.224 + return nullptr;
1.225 + }
1.226 +
1.227 + nsINode *lastChild;
1.228 + while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
1.229 + (lastChild = node->GetLastChild())) {
1.230 + node = lastChild;
1.231 + filtered = TestNode(node, aResult);
1.232 + if (aResult.Failed()) {
1.233 + return nullptr;
1.234 + }
1.235 + }
1.236 +
1.237 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.238 + mCurrentNode = node;
1.239 + return node.forget();
1.240 + }
1.241 + }
1.242 +
1.243 + if (node == mRoot) {
1.244 + break;
1.245 + }
1.246 +
1.247 + node = node->GetParentNode();
1.248 + if (!node) {
1.249 + break;
1.250 + }
1.251 +
1.252 + int16_t filtered = TestNode(node, aResult);
1.253 + if (aResult.Failed()) {
1.254 + return nullptr;
1.255 + }
1.256 +
1.257 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.258 + mCurrentNode = node;
1.259 + return node.forget();
1.260 + }
1.261 + }
1.262 +
1.263 + return nullptr;
1.264 +}
1.265 +
1.266 +/* nsIDOMNode nextNode (); */
1.267 +NS_IMETHODIMP TreeWalker::NextNode(nsIDOMNode **_retval)
1.268 +{
1.269 + return ImplNodeGetter(&TreeWalker::NextNode, _retval);
1.270 +}
1.271 +
1.272 +already_AddRefed<nsINode>
1.273 +TreeWalker::NextNode(ErrorResult& aResult)
1.274 +{
1.275 + int16_t filtered = nsIDOMNodeFilter::FILTER_ACCEPT; // pre-init for inner loop
1.276 +
1.277 + nsCOMPtr<nsINode> node = mCurrentNode;
1.278 +
1.279 + while (1) {
1.280 +
1.281 + nsINode *firstChild;
1.282 + while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
1.283 + (firstChild = node->GetFirstChild())) {
1.284 + node = firstChild;
1.285 +
1.286 + filtered = TestNode(node, aResult);
1.287 + if (aResult.Failed()) {
1.288 + return nullptr;
1.289 + }
1.290 +
1.291 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.292 + // Node found
1.293 + mCurrentNode = node;
1.294 + return node.forget();
1.295 + }
1.296 + }
1.297 +
1.298 + nsINode *sibling = nullptr;
1.299 + nsINode *temp = node;
1.300 + do {
1.301 + if (temp == mRoot)
1.302 + break;
1.303 +
1.304 + sibling = temp->GetNextSibling();
1.305 + if (sibling)
1.306 + break;
1.307 +
1.308 + temp = temp->GetParentNode();
1.309 + } while (temp);
1.310 +
1.311 + if (!sibling)
1.312 + break;
1.313 +
1.314 + node = sibling;
1.315 +
1.316 + // Found a sibling. Either ours or ancestor's
1.317 + filtered = TestNode(node, aResult);
1.318 + if (aResult.Failed()) {
1.319 + return nullptr;
1.320 + }
1.321 +
1.322 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.323 + // Node found
1.324 + mCurrentNode = node;
1.325 + return node.forget();
1.326 + }
1.327 + }
1.328 +
1.329 + return nullptr;
1.330 +}
1.331 +
1.332 +/*
1.333 + * TreeWalker helper functions
1.334 + */
1.335 +
1.336 +/*
1.337 + * Implements FirstChild and LastChild which only vary in which direction
1.338 + * they search.
1.339 + * @param aReversed Controls whether we search forwards or backwards
1.340 + * @param aResult Whether we threw or not.
1.341 + * @returns The desired node. Null if no child is found
1.342 + */
1.343 +already_AddRefed<nsINode>
1.344 +TreeWalker::FirstChildInternal(bool aReversed, ErrorResult& aResult)
1.345 +{
1.346 + nsCOMPtr<nsINode> node = aReversed ? mCurrentNode->GetLastChild()
1.347 + : mCurrentNode->GetFirstChild();
1.348 +
1.349 + while (node) {
1.350 + int16_t filtered = TestNode(node, aResult);
1.351 + if (aResult.Failed()) {
1.352 + return nullptr;
1.353 + }
1.354 +
1.355 + switch (filtered) {
1.356 + case nsIDOMNodeFilter::FILTER_ACCEPT:
1.357 + // Node found
1.358 + mCurrentNode = node;
1.359 + return node.forget();
1.360 + case nsIDOMNodeFilter::FILTER_SKIP: {
1.361 + nsINode *child = aReversed ? node->GetLastChild()
1.362 + : node->GetFirstChild();
1.363 + if (child) {
1.364 + node = child;
1.365 + continue;
1.366 + }
1.367 + break;
1.368 + }
1.369 + case nsIDOMNodeFilter::FILTER_REJECT:
1.370 + // Keep searching
1.371 + break;
1.372 + }
1.373 +
1.374 + do {
1.375 + nsINode *sibling = aReversed ? node->GetPreviousSibling()
1.376 + : node->GetNextSibling();
1.377 + if (sibling) {
1.378 + node = sibling;
1.379 + break;
1.380 + }
1.381 +
1.382 + nsINode *parent = node->GetParentNode();
1.383 +
1.384 + if (!parent || parent == mRoot || parent == mCurrentNode) {
1.385 + return nullptr;
1.386 + }
1.387 +
1.388 + node = parent;
1.389 +
1.390 + } while (node);
1.391 + }
1.392 +
1.393 + return nullptr;
1.394 +}
1.395 +
1.396 +/*
1.397 + * Implements NextSibling and PreviousSibling which only vary in which
1.398 + * direction they search.
1.399 + * @param aReversed Controls whether we search forwards or backwards
1.400 + * @param aResult Whether we threw or not.
1.401 + * @returns The desired node. Null if no child is found
1.402 + */
1.403 +already_AddRefed<nsINode>
1.404 +TreeWalker::NextSiblingInternal(bool aReversed, ErrorResult& aResult)
1.405 +{
1.406 + nsCOMPtr<nsINode> node = mCurrentNode;
1.407 +
1.408 + if (node == mRoot) {
1.409 + return nullptr;
1.410 + }
1.411 +
1.412 + while (1) {
1.413 + nsINode* sibling = aReversed ? node->GetPreviousSibling()
1.414 + : node->GetNextSibling();
1.415 +
1.416 + while (sibling) {
1.417 + node = sibling;
1.418 +
1.419 + int16_t filtered = TestNode(node, aResult);
1.420 + if (aResult.Failed()) {
1.421 + return nullptr;
1.422 + }
1.423 +
1.424 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.425 + // Node found
1.426 + mCurrentNode = node;
1.427 + return node.forget();
1.428 + }
1.429 +
1.430 + // If rejected or no children, try a sibling
1.431 + if (filtered == nsIDOMNodeFilter::FILTER_REJECT ||
1.432 + !(sibling = aReversed ? node->GetLastChild()
1.433 + : node->GetFirstChild())) {
1.434 + sibling = aReversed ? node->GetPreviousSibling()
1.435 + : node->GetNextSibling();
1.436 + }
1.437 + }
1.438 +
1.439 + node = node->GetParentNode();
1.440 +
1.441 + if (!node || node == mRoot) {
1.442 + return nullptr;
1.443 + }
1.444 +
1.445 + // Is parent transparent in filtered view?
1.446 + int16_t filtered = TestNode(node, aResult);
1.447 + if (aResult.Failed()) {
1.448 + return nullptr;
1.449 + }
1.450 + if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
1.451 + return nullptr;
1.452 + }
1.453 + }
1.454 +}
1.455 +
1.456 +JSObject*
1.457 +TreeWalker::WrapObject(JSContext *cx)
1.458 +{
1.459 + return TreeWalkerBinding::Wrap(cx, this);
1.460 +}
1.461 +
1.462 +} // namespace dom
1.463 +} // namespace mozilla
