michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: /* vim: set ts=4 et sw=4 tw=80: */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0:  * Implementation of DOM Traversal's nsIDOMTreeWalker
michael@0:  */
michael@0: 
michael@0: #include "mozilla/dom/TreeWalker.h"
michael@0: 
michael@0: #include "nsIContent.h"
michael@0: #include "nsIDOMNode.h"
michael@0: #include "nsError.h"
michael@0: #include "nsINode.h"
michael@0: #include "nsContentUtils.h"
michael@0: #include "mozilla/dom/TreeWalkerBinding.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace dom {
michael@0: 
michael@0: /*
michael@0:  * Factories, constructors and destructors
michael@0:  */
michael@0: 
michael@0: TreeWalker::TreeWalker(nsINode *aRoot,
michael@0:                        uint32_t aWhatToShow,
michael@0:                        const NodeFilterHolder &aFilter) :
michael@0:     nsTraversal(aRoot, aWhatToShow, aFilter),
michael@0:     mCurrentNode(aRoot)
michael@0: {
michael@0: }
michael@0: 
michael@0: TreeWalker::~TreeWalker()
michael@0: {
michael@0:     /* destructor code */
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * nsISupports and cycle collection stuff
michael@0:  */
michael@0: 
michael@0: NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)
michael@0: 
michael@0: // QueryInterface implementation for TreeWalker
michael@0: NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
michael@0:     NS_INTERFACE_MAP_ENTRY(nsIDOMTreeWalker)
michael@0:     NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsIDOMTreeWalker)
michael@0: NS_INTERFACE_MAP_END
michael@0: 
michael@0: // Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
michael@0: // passes TreeWalker so refcount logging would get confused on the name
michael@0: // collision.
michael@0: NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
michael@0: NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)
michael@0: 
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * nsIDOMTreeWalker Getters/Setters
michael@0:  */
michael@0: 
michael@0: /* readonly attribute nsIDOMNode root; */
michael@0: NS_IMETHODIMP TreeWalker::GetRoot(nsIDOMNode * *aRoot)
michael@0: {
michael@0:     NS_ADDREF(*aRoot = Root()->AsDOMNode());
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: /* readonly attribute unsigned long whatToShow; */
michael@0: NS_IMETHODIMP TreeWalker::GetWhatToShow(uint32_t *aWhatToShow)
michael@0: {
michael@0:     *aWhatToShow = WhatToShow();
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: /* readonly attribute nsIDOMNodeFilter filter; */
michael@0: NS_IMETHODIMP TreeWalker::GetFilter(nsIDOMNodeFilter * *aFilter)
michael@0: {
michael@0:     NS_ENSURE_ARG_POINTER(aFilter);
michael@0: 
michael@0:     *aFilter = mFilter.ToXPCOMCallback().take();
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: /* attribute nsIDOMNode currentNode; */
michael@0: NS_IMETHODIMP TreeWalker::GetCurrentNode(nsIDOMNode * *aCurrentNode)
michael@0: {
michael@0:     if (mCurrentNode) {
michael@0:         return CallQueryInterface(mCurrentNode, aCurrentNode);
michael@0:     }
michael@0: 
michael@0:     *aCurrentNode = nullptr;
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: NS_IMETHODIMP TreeWalker::SetCurrentNode(nsIDOMNode * aCurrentNode)
michael@0: {
michael@0:     NS_ENSURE_TRUE(aCurrentNode, NS_ERROR_DOM_NOT_SUPPORTED_ERR);
michael@0:     NS_ENSURE_TRUE(mRoot, NS_ERROR_UNEXPECTED);
michael@0: 
michael@0:     nsCOMPtr<nsINode> node = do_QueryInterface(aCurrentNode);
michael@0:     NS_ENSURE_TRUE(node, NS_ERROR_UNEXPECTED);
michael@0: 
michael@0:     ErrorResult rv;
michael@0:     SetCurrentNode(*node, rv);
michael@0:     return rv.ErrorCode();
michael@0: }
michael@0: 
michael@0: void
michael@0: TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult)
michael@0: {
michael@0:     aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
michael@0:     if (aResult.Failed()) {
michael@0:         return;
michael@0:     }
michael@0: 
michael@0:     mCurrentNode = &aNode;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * nsIDOMTreeWalker functions
michael@0:  */
michael@0: 
michael@0: /* nsIDOMNode parentNode (); */
michael@0: NS_IMETHODIMP TreeWalker::ParentNode(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::ParentNode, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::ParentNode(ErrorResult& aResult)
michael@0: {
michael@0:     nsCOMPtr<nsINode> node = mCurrentNode;
michael@0: 
michael@0:     while (node && node != mRoot) {
michael@0:         node = node->GetParentNode();
michael@0: 
michael@0:         if (node) {
michael@0:             int16_t filtered = TestNode(node, aResult);
michael@0:             if (aResult.Failed()) {
michael@0:                 return nullptr;
michael@0:             }
michael@0:             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:                 mCurrentNode = node;
michael@0:                 return node.forget();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode firstChild (); */
michael@0: NS_IMETHODIMP TreeWalker::FirstChild(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::FirstChild, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::FirstChild(ErrorResult& aResult)
michael@0: {
michael@0:     return FirstChildInternal(false, aResult);
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode lastChild (); */
michael@0: NS_IMETHODIMP TreeWalker::LastChild(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::LastChild, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::LastChild(ErrorResult& aResult)
michael@0: {
michael@0:     return FirstChildInternal(true, aResult);
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode previousSibling (); */
michael@0: NS_IMETHODIMP TreeWalker::PreviousSibling(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::PreviousSibling, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::PreviousSibling(ErrorResult& aResult)
michael@0: {
michael@0:     return NextSiblingInternal(true, aResult);
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode nextSibling (); */
michael@0: NS_IMETHODIMP TreeWalker::NextSibling(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::NextSibling, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::NextSibling(ErrorResult& aResult)
michael@0: {
michael@0:     return NextSiblingInternal(false, aResult);
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode previousNode (); */
michael@0: NS_IMETHODIMP TreeWalker::PreviousNode(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::PreviousNode, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::PreviousNode(ErrorResult& aResult)
michael@0: {
michael@0:     nsCOMPtr<nsINode> node = mCurrentNode;
michael@0: 
michael@0:     while (node != mRoot) {
michael@0:         while (nsINode *previousSibling = node->GetPreviousSibling()) {
michael@0:             node = previousSibling;
michael@0: 
michael@0:             int16_t filtered = TestNode(node, aResult);
michael@0:             if (aResult.Failed()) {
michael@0:                 return nullptr;
michael@0:             }
michael@0: 
michael@0:             nsINode *lastChild;
michael@0:             while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
michael@0:                    (lastChild = node->GetLastChild())) {
michael@0:                 node = lastChild;
michael@0:                 filtered = TestNode(node, aResult);
michael@0:                 if (aResult.Failed()) {
michael@0:                     return nullptr;
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:                 mCurrentNode = node;
michael@0:                 return node.forget();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         if (node == mRoot) {
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         node = node->GetParentNode();
michael@0:         if (!node) {
michael@0:             break;
michael@0:         }
michael@0: 
michael@0:         int16_t filtered = TestNode(node, aResult);
michael@0:         if (aResult.Failed()) {
michael@0:             return nullptr;
michael@0:         }
michael@0: 
michael@0:         if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:             mCurrentNode = node;
michael@0:             return node.forget();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /* nsIDOMNode nextNode (); */
michael@0: NS_IMETHODIMP TreeWalker::NextNode(nsIDOMNode **_retval)
michael@0: {
michael@0:     return ImplNodeGetter(&TreeWalker::NextNode, _retval);
michael@0: }
michael@0: 
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::NextNode(ErrorResult& aResult)
michael@0: {
michael@0:     int16_t filtered = nsIDOMNodeFilter::FILTER_ACCEPT; // pre-init for inner loop
michael@0: 
michael@0:     nsCOMPtr<nsINode> node = mCurrentNode;
michael@0: 
michael@0:     while (1) {
michael@0: 
michael@0:         nsINode *firstChild;
michael@0:         while (filtered != nsIDOMNodeFilter::FILTER_REJECT &&
michael@0:                (firstChild = node->GetFirstChild())) {
michael@0:             node = firstChild;
michael@0: 
michael@0:             filtered = TestNode(node, aResult);
michael@0:             if (aResult.Failed()) {
michael@0:                 return nullptr;
michael@0:             }
michael@0: 
michael@0:             if (filtered ==  nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:                 // Node found
michael@0:                 mCurrentNode = node;
michael@0:                 return node.forget();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         nsINode *sibling = nullptr;
michael@0:         nsINode *temp = node;
michael@0:         do {
michael@0:             if (temp == mRoot)
michael@0:                 break;
michael@0: 
michael@0:             sibling = temp->GetNextSibling();
michael@0:             if (sibling)
michael@0:                 break;
michael@0: 
michael@0:             temp = temp->GetParentNode();
michael@0:         } while (temp);
michael@0: 
michael@0:         if (!sibling)
michael@0:             break;
michael@0: 
michael@0:         node = sibling;
michael@0: 
michael@0:         // Found a sibling. Either ours or ancestor's
michael@0:         filtered = TestNode(node, aResult);
michael@0:         if (aResult.Failed()) {
michael@0:             return nullptr;
michael@0:         }
michael@0: 
michael@0:         if (filtered ==  nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:             // Node found
michael@0:             mCurrentNode = node;
michael@0:             return node.forget();
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * TreeWalker helper functions
michael@0:  */
michael@0: 
michael@0: /*
michael@0:  * Implements FirstChild and LastChild which only vary in which direction
michael@0:  * they search.
michael@0:  * @param aReversed Controls whether we search forwards or backwards
michael@0:  * @param aResult   Whether we threw or not.
michael@0:  * @returns         The desired node. Null if no child is found
michael@0:  */
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::FirstChildInternal(bool aReversed, ErrorResult& aResult)
michael@0: {
michael@0:     nsCOMPtr<nsINode> node = aReversed ? mCurrentNode->GetLastChild()
michael@0:                                        : mCurrentNode->GetFirstChild();
michael@0: 
michael@0:     while (node) {
michael@0:         int16_t filtered = TestNode(node, aResult);
michael@0:         if (aResult.Failed()) {
michael@0:             return nullptr;
michael@0:         }
michael@0: 
michael@0:         switch (filtered) {
michael@0:             case nsIDOMNodeFilter::FILTER_ACCEPT:
michael@0:                 // Node found
michael@0:                 mCurrentNode = node;
michael@0:                 return node.forget();
michael@0:             case nsIDOMNodeFilter::FILTER_SKIP: {
michael@0:                     nsINode *child = aReversed ? node->GetLastChild()
michael@0:                                                : node->GetFirstChild();
michael@0:                     if (child) {
michael@0:                         node = child;
michael@0:                         continue;
michael@0:                     }
michael@0:                     break;
michael@0:                 }
michael@0:             case nsIDOMNodeFilter::FILTER_REJECT:
michael@0:                 // Keep searching
michael@0:                 break;
michael@0:         }
michael@0: 
michael@0:         do {
michael@0:             nsINode *sibling = aReversed ? node->GetPreviousSibling()
michael@0:                                          : node->GetNextSibling();
michael@0:             if (sibling) {
michael@0:                 node = sibling;
michael@0:                 break;
michael@0:             }
michael@0: 
michael@0:             nsINode *parent = node->GetParentNode();
michael@0: 
michael@0:             if (!parent || parent == mRoot || parent == mCurrentNode) {
michael@0:                 return nullptr;
michael@0:             }
michael@0: 
michael@0:             node = parent;
michael@0: 
michael@0:         } while (node);
michael@0:     }
michael@0: 
michael@0:     return nullptr;
michael@0: }
michael@0: 
michael@0: /*
michael@0:  * Implements NextSibling and PreviousSibling which only vary in which
michael@0:  * direction they search.
michael@0:  * @param aReversed Controls whether we search forwards or backwards
michael@0:  * @param aResult   Whether we threw or not.
michael@0:  * @returns         The desired node. Null if no child is found
michael@0:  */
michael@0: already_AddRefed<nsINode>
michael@0: TreeWalker::NextSiblingInternal(bool aReversed, ErrorResult& aResult)
michael@0: {
michael@0:     nsCOMPtr<nsINode> node = mCurrentNode;
michael@0: 
michael@0:     if (node == mRoot) {
michael@0:         return nullptr;
michael@0:     }
michael@0: 
michael@0:     while (1) {
michael@0:         nsINode* sibling = aReversed ? node->GetPreviousSibling()
michael@0:                                      : node->GetNextSibling();
michael@0: 
michael@0:         while (sibling) {
michael@0:             node = sibling;
michael@0: 
michael@0:             int16_t filtered = TestNode(node, aResult);
michael@0:             if (aResult.Failed()) {
michael@0:                 return nullptr;
michael@0:             }
michael@0: 
michael@0:             if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:                 // Node found
michael@0:                 mCurrentNode = node;
michael@0:                 return node.forget();
michael@0:             }
michael@0: 
michael@0:             // If rejected or no children, try a sibling
michael@0:             if (filtered == nsIDOMNodeFilter::FILTER_REJECT ||
michael@0:                 !(sibling = aReversed ? node->GetLastChild()
michael@0:                                       : node->GetFirstChild())) {
michael@0:                 sibling = aReversed ? node->GetPreviousSibling()
michael@0:                                     : node->GetNextSibling();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         node = node->GetParentNode();
michael@0: 
michael@0:         if (!node || node == mRoot) {
michael@0:             return nullptr;
michael@0:         }
michael@0: 
michael@0:         // Is parent transparent in filtered view?
michael@0:         int16_t filtered = TestNode(node, aResult);
michael@0:         if (aResult.Failed()) {
michael@0:             return nullptr;
michael@0:         }
michael@0:         if (filtered == nsIDOMNodeFilter::FILTER_ACCEPT) {
michael@0:             return nullptr;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: JSObject*
michael@0: TreeWalker::WrapObject(JSContext *cx)
michael@0: {
michael@0:     return TreeWalkerBinding::Wrap(cx, this);
michael@0: }
michael@0: 
michael@0: } // namespace dom
michael@0: } // namespace mozilla