1/*
2 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
15 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
16 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
17 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
18 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
19 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
20 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
21 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#include "config.h"
27#include "XPathNodeSet.h"
28
29#include "Attr.h"
30#include "Element.h"
31#include "NodeTraversal.h"
32
33namespace WebCore {
34namespace XPath {
35
36// When a node set is large, sorting it by traversing the whole document is better (we can
37// assume that we aren't dealing with documents that we cannot even traverse in reasonable time).
38const unsigned traversalSortCutoff = 10000;
39
40static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
41{
42 ASSERT(parents.size() >= depth + 1);
43 return parents[parents.size() - 1 - depth];
44}
45
46static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*>>& parentMatrix, bool mayContainAttributeNodes)
47{
48 ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
49 unsigned minDepth = UINT_MAX;
50 for (unsigned i = from; i < to; ++i) {
51 unsigned depth = parentMatrix[i].size() - 1;
52 if (minDepth > depth)
53 minDepth = depth;
54 }
55
56 // Find the common ancestor.
57 unsigned commonAncestorDepth = minDepth;
58 Node* commonAncestor;
59 while (true) {
60 commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
61 if (commonAncestorDepth == 0)
62 break;
63
64 bool allEqual = true;
65 for (unsigned i = from + 1; i < to; ++i) {
66 if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
67 allEqual = false;
68 break;
69 }
70 }
71 if (allEqual)
72 break;
73
74 --commonAncestorDepth;
75 }
76
77 if (commonAncestorDepth == minDepth) {
78 // One of the nodes is the common ancestor => it is the first in document order.
79 // Find it and move it to the beginning.
80 for (unsigned i = from; i < to; ++i)
81 if (commonAncestor == parentMatrix[i][0]) {
82 parentMatrix[i].swap(parentMatrix[from]);
83 if (from + 2 < to)
84 sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
85 return;
86 }
87 }
88
89 if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
90 // The attribute nodes and namespace nodes of an element occur before the children of the element.
91 // The namespace nodes are defined to occur before the attribute nodes.
92 // The relative order of namespace nodes is implementation-dependent.
93 // The relative order of attribute nodes is implementation-dependent.
94 unsigned sortedEnd = from;
95 // FIXME: namespace nodes are not implemented.
96 for (unsigned i = sortedEnd; i < to; ++i) {
97 Node* node = parentMatrix[i][0];
98 if (is<Attr>(*node) && downcast<Attr>(*node).ownerElement() == commonAncestor)
99 parentMatrix[i].swap(parentMatrix[sortedEnd++]);
100 }
101 if (sortedEnd != from) {
102 if (to - sortedEnd > 1)
103 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
104 return;
105 }
106 }
107
108 // Children nodes of the common ancestor induce a subdivision of our node-set.
109 // Sort it according to this subdivision, and recursively sort each group.
110 HashSet<Node*> parentNodes;
111 for (unsigned i = from; i < to; ++i)
112 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
113
114 unsigned previousGroupEnd = from;
115 unsigned groupEnd = from;
116 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
117 // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.
118 if (parentNodes.contains(n)) {
119 for (unsigned i = groupEnd; i < to; ++i)
120 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
121 parentMatrix[i].swap(parentMatrix[groupEnd++]);
122
123 if (groupEnd - previousGroupEnd > 1)
124 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
125
126 ASSERT(previousGroupEnd != groupEnd);
127 previousGroupEnd = groupEnd;
128#ifndef NDEBUG
129 parentNodes.remove(n);
130#endif
131 }
132 }
133
134 ASSERT(parentNodes.isEmpty());
135}
136
137void NodeSet::sort() const
138{
139 if (m_isSorted)
140 return;
141
142 unsigned nodeCount = m_nodes.size();
143 if (nodeCount < 2) {
144 m_isSorted = true;
145 return;
146 }
147
148 if (nodeCount > traversalSortCutoff) {
149 traversalSort();
150 return;
151 }
152
153 bool containsAttributeNodes = false;
154
155 Vector<Vector<Node*>> parentMatrix(nodeCount);
156 for (unsigned i = 0; i < nodeCount; ++i) {
157 Vector<Node*>& parentsVector = parentMatrix[i];
158 Node* node = m_nodes[i].get();
159 parentsVector.append(node);
160 if (is<Attr>(*node)) {
161 node = downcast<Attr>(*node).ownerElement();
162 parentsVector.append(node);
163 containsAttributeNodes = true;
164 }
165 while ((node = node->parentNode()))
166 parentsVector.append(node);
167 }
168 sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
169
170 // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.
171 Vector<RefPtr<Node>> sortedNodes;
172 sortedNodes.reserveInitialCapacity(nodeCount);
173 for (unsigned i = 0; i < nodeCount; ++i)
174 sortedNodes.append(parentMatrix[i][0]);
175
176 m_nodes = WTFMove(sortedNodes);
177 m_isSorted = true;
178}
179
180static Node* findRootNode(Node* node)
181{
182 if (is<Attr>(*node))
183 node = downcast<Attr>(*node).ownerElement();
184 if (node->isConnected())
185 node = &node->document();
186 else {
187 while (Node* parent = node->parentNode())
188 node = parent;
189 }
190 return node;
191}
192
193void NodeSet::traversalSort() const
194{
195 HashSet<Node*> nodes;
196 bool containsAttributeNodes = false;
197
198 unsigned nodeCount = m_nodes.size();
199 ASSERT(nodeCount > 1);
200 for (auto& node : m_nodes) {
201 nodes.add(node.get());
202 if (node->isAttributeNode())
203 containsAttributeNodes = true;
204 }
205
206 Vector<RefPtr<Node>> sortedNodes;
207 sortedNodes.reserveInitialCapacity(nodeCount);
208
209 for (Node* node = findRootNode(m_nodes.first().get()); node; node = NodeTraversal::next(*node)) {
210 if (nodes.contains(node))
211 sortedNodes.append(node);
212
213 if (!containsAttributeNodes || !is<Element>(*node))
214 continue;
215
216 Element& element = downcast<Element>(*node);
217 if (!element.hasAttributes())
218 continue;
219
220 for (const Attribute& attribute : element.attributesIterator()) {
221 RefPtr<Attr> attr = element.attrIfExists(attribute.name());
222 if (attr && nodes.contains(attr.get()))
223 sortedNodes.append(attr);
224 }
225 }
226
227 ASSERT(sortedNodes.size() == nodeCount);
228 m_nodes = WTFMove(sortedNodes);
229 m_isSorted = true;
230}
231
232Node* NodeSet::firstNode() const
233{
234 if (isEmpty())
235 return nullptr;
236
237 sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
238 return m_nodes.at(0).get();
239}
240
241Node* NodeSet::anyNode() const
242{
243 if (isEmpty())
244 return nullptr;
245
246 return m_nodes.at(0).get();
247}
248
249}
250}
251