/src/mozilla-central/dom/base/TreeWalker.cpp

Source (jump to first uncovered line)
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
/* vim: set ts=4 et sw=4 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Implementation of DOM Traversal's TreeWalker
 */

#include "mozilla/dom/TreeWalker.h"

#include "nsIContent.h"
#include "nsError.h"
#include "nsINode.h"
#include "nsContentUtils.h"
#include "mozilla/dom/NodeFilterBinding.h"
#include "mozilla/dom/TreeWalkerBinding.h"

namespace mozilla {
namespace dom {

/*
 * Factories, constructors and destructors
 */

TreeWalker::TreeWalker(nsINode *aRoot,
                       uint32_t aWhatToShow,
                       NodeFilter* aFilter) :
    nsTraversal(aRoot, aWhatToShow, aFilter),
    mCurrentNode(aRoot)
{
}

TreeWalker::~TreeWalker()
{
    /* destructor code */
}

/*
 * nsISupports and cycle collection stuff
 */

NS_IMPL_CYCLE_COLLECTION(TreeWalker, mFilter, mCurrentNode, mRoot)

// QueryInterface implementation for TreeWalker
NS_INTERFACE_MAP_BEGIN_CYCLE_COLLECTION(TreeWalker)
    NS_INTERFACE_MAP_ENTRY(nsISupports)
NS_INTERFACE_MAP_END

// Have to pass in dom::TreeWalker because a11y has an a11y::TreeWalker that
// passes TreeWalker so refcount logging would get confused on the name
// collision.
NS_IMPL_CYCLE_COLLECTING_ADDREF(dom::TreeWalker)
NS_IMPL_CYCLE_COLLECTING_RELEASE(dom::TreeWalker)

void
TreeWalker::SetCurrentNode(nsINode& aNode, ErrorResult& aResult)
{
    aResult = nsContentUtils::CheckSameOrigin(mRoot, &aNode);
    if (aResult.Failed()) {
        return;
    }

    mCurrentNode = &aNode;
}

already_AddRefed<nsINode>
TreeWalker::ParentNode(ErrorResult& aResult)
{
    nsCOMPtr<nsINode> node = mCurrentNode;

    while (node && node != mRoot) {
        node = node->GetParentNode();

        if (node) {
            int16_t filtered = TestNode(node, aResult);
            if (aResult.Failed()) {
                return nullptr;
            }
            if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
                mCurrentNode = node;
                return node.forget();
            }
        }
    }

    return nullptr;
}

already_AddRefed<nsINode>
TreeWalker::FirstChild(ErrorResult& aResult)
{
    return FirstChildInternal(false, aResult);
}

already_AddRefed<nsINode>
TreeWalker::LastChild(ErrorResult& aResult)
{
    return FirstChildInternal(true, aResult);
}

already_AddRefed<nsINode>
TreeWalker::PreviousSibling(ErrorResult& aResult)
{
    return NextSiblingInternal(true, aResult);
}

already_AddRefed<nsINode>
TreeWalker::NextSibling(ErrorResult& aResult)
{
    return NextSiblingInternal(false, aResult);
}

already_AddRefed<nsINode>
TreeWalker::PreviousNode(ErrorResult& aResult)
{
    nsCOMPtr<nsINode> node = mCurrentNode;

    while (node != mRoot) {
        while (nsINode *previousSibling = node->GetPreviousSibling()) {
            node = previousSibling;

            int16_t filtered = TestNode(node, aResult);
            if (aResult.Failed()) {
                return nullptr;
            }

            nsINode *lastChild;
            while (filtered != NodeFilter_Binding::FILTER_REJECT &&
                   (lastChild = node->GetLastChild())) {
                node = lastChild;
                filtered = TestNode(node, aResult);
                if (aResult.Failed()) {
                    return nullptr;
                }
            }

            if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
                mCurrentNode = node;
                return node.forget();
            }
        }

        if (node == mRoot) {
            break;
        }

        node = node->GetParentNode();
        if (!node) {
            break;
        }

        int16_t filtered = TestNode(node, aResult);
        if (aResult.Failed()) {
            return nullptr;
        }

        if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
            mCurrentNode = node;
            return node.forget();
        }
    }

    return nullptr;
}

already_AddRefed<nsINode>
TreeWalker::NextNode(ErrorResult& aResult)
{
    int16_t filtered = NodeFilter_Binding::FILTER_ACCEPT; // pre-init for inner loop

    nsCOMPtr<nsINode> node = mCurrentNode;

    while (1) {

        nsINode *firstChild;
        while (filtered != NodeFilter_Binding::FILTER_REJECT &&
               (firstChild = node->GetFirstChild())) {
            node = firstChild;

            filtered = TestNode(node, aResult);
            if (aResult.Failed()) {
                return nullptr;
            }

            if (filtered ==  NodeFilter_Binding::FILTER_ACCEPT) {
                // Node found
                mCurrentNode = node;
                return node.forget();
            }
        }

        nsINode *sibling = nullptr;
        nsINode *temp = node;
        do {
            if (temp == mRoot)
                break;

            sibling = temp->GetNextSibling();
            if (sibling)
                break;

            temp = temp->GetParentNode();
        } while (temp);

        if (!sibling)
            break;

        node = sibling;

        // Found a sibling. Either ours or ancestor's
        filtered = TestNode(node, aResult);
        if (aResult.Failed()) {
            return nullptr;
        }

        if (filtered ==  NodeFilter_Binding::FILTER_ACCEPT) {
            // Node found
            mCurrentNode = node;
            return node.forget();
        }
    }

    return nullptr;
}

/*
 * TreeWalker helper functions
 */

/*
 * Implements FirstChild and LastChild which only vary in which direction
 * they search.
 * @param aReversed Controls whether we search forwards or backwards
 * @param aResult   Whether we threw or not.
 * @returns         The desired node. Null if no child is found
 */
already_AddRefed<nsINode>
TreeWalker::FirstChildInternal(bool aReversed, ErrorResult& aResult)
{
    nsCOMPtr<nsINode> node = aReversed ? mCurrentNode->GetLastChild()
                                       : mCurrentNode->GetFirstChild();

    while (node) {
        int16_t filtered = TestNode(node, aResult);
        if (aResult.Failed()) {
            return nullptr;
        }

        switch (filtered) {
            case NodeFilter_Binding::FILTER_ACCEPT:
                // Node found
                mCurrentNode = node;
                return node.forget();
            case NodeFilter_Binding::FILTER_SKIP: {
                    nsINode *child = aReversed ? node->GetLastChild()
                                               : node->GetFirstChild();
                    if (child) {
                        node = child;
                        continue;
                    }
                    break;
                }
            case NodeFilter_Binding::FILTER_REJECT:
                // Keep searching
                break;
        }

        do {
            nsINode *sibling = aReversed ? node->GetPreviousSibling()
                                         : node->GetNextSibling();
            if (sibling) {
                node = sibling;
                break;
            }

            nsINode *parent = node->GetParentNode();

            if (!parent || parent == mRoot || parent == mCurrentNode) {
                return nullptr;
            }

            node = parent;

        } while (node);
    }

    return nullptr;
}

/*
 * Implements NextSibling and PreviousSibling which only vary in which
 * direction they search.
 * @param aReversed Controls whether we search forwards or backwards
 * @param aResult   Whether we threw or not.
 * @returns         The desired node. Null if no child is found
 */
already_AddRefed<nsINode>
TreeWalker::NextSiblingInternal(bool aReversed, ErrorResult& aResult)
{
    nsCOMPtr<nsINode> node = mCurrentNode;

    if (node == mRoot) {
        return nullptr;
    }

    while (1) {
        nsINode* sibling = aReversed ? node->GetPreviousSibling()
                                     : node->GetNextSibling();

        while (sibling) {
            node = sibling;

            int16_t filtered = TestNode(node, aResult);
            if (aResult.Failed()) {
                return nullptr;
            }

            if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
                // Node found
                mCurrentNode = node;
                return node.forget();
            }

            // If rejected or no children, try a sibling
            if (filtered == NodeFilter_Binding::FILTER_REJECT ||
                !(sibling = aReversed ? node->GetLastChild()
                                      : node->GetFirstChild())) {
                sibling = aReversed ? node->GetPreviousSibling()
                                    : node->GetNextSibling();
            }
        }

        node = node->GetParentNode();

        if (!node || node == mRoot) {
            return nullptr;
        }

        // Is parent transparent in filtered view?
        int16_t filtered = TestNode(node, aResult);
        if (aResult.Failed()) {
            return nullptr;
        }
        if (filtered == NodeFilter_Binding::FILTER_ACCEPT) {
            return nullptr;
        }
    }
}

bool
TreeWalker::WrapObject(JSContext *aCx, JS::Handle<JSObject*> aGivenProto, JS::MutableHandle<JSObject*> aReflector)
{
    return TreeWalker_Binding::Wrap(aCx, this, aGivenProto, aReflector);
}

} // namespace dom
} // namespace mozilla

Coverage Report

Created: 2018-09-25 14:53

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