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 "core/xml/XPathNodeSet.h"
28
29 #include "core/dom/Attr.h"
30 #include "core/dom/Document.h"
31 #include "core/dom/Element.h"
32 #include "core/dom/NodeTraversal.h"
33
34 namespace WebCore {
35 namespace XPath {
36
37 // When a node set is large, sorting it by traversing the whole document is
38 // better (we can assume that we aren't dealing with documents that we cannot
39 // even traverse in reasonable time).
40 const unsigned traversalSortCutoff = 10000;
41
42 typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector;
43
create(const NodeSet & other)44 PassOwnPtrWillBeRawPtr<NodeSet> NodeSet::create(const NodeSet& other)
45 {
46 OwnPtrWillBeRawPtr<NodeSet> nodeSet = NodeSet::create();
47 nodeSet->m_isSorted = other.m_isSorted;
48 nodeSet->m_subtreesAreDisjoint = other.m_subtreesAreDisjoint;
49 nodeSet->m_nodes.appendVector(other.m_nodes);
50 return nodeSet.release();
51 }
52
parentWithDepth(unsigned depth,const NodeSetVector & parents)53 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents)
54 {
55 ASSERT(parents.size() >= depth + 1);
56 return parents[parents.size() - 1 - depth];
57 }
58
sortBlock(unsigned from,unsigned to,WillBeHeapVector<NodeSetVector> & parentMatrix,bool mayContainAttributeNodes)59 static void sortBlock(unsigned from, unsigned to, WillBeHeapVector<NodeSetVector>& parentMatrix, bool mayContainAttributeNodes)
60 {
61 // Should not call this function with less that two nodes to sort.
62 ASSERT(from + 1 < to);
63 unsigned minDepth = UINT_MAX;
64 for (unsigned i = from; i < to; ++i) {
65 unsigned depth = parentMatrix[i].size() - 1;
66 if (minDepth > depth)
67 minDepth = depth;
68 }
69
70 // Find the common ancestor.
71 unsigned commonAncestorDepth = minDepth;
72 Node* commonAncestor;
73 while (true) {
74 commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
75 if (commonAncestorDepth == 0)
76 break;
77
78 bool allEqual = true;
79 for (unsigned i = from + 1; i < to; ++i) {
80 if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
81 allEqual = false;
82 break;
83 }
84 }
85 if (allEqual)
86 break;
87
88 --commonAncestorDepth;
89 }
90
91 if (commonAncestorDepth == minDepth) {
92 // One of the nodes is the common ancestor => it is the first in
93 // document order. Find it and move it to the beginning.
94 for (unsigned i = from; i < to; ++i) {
95 if (commonAncestor == parentMatrix[i][0]) {
96 parentMatrix[i].swap(parentMatrix[from]);
97 if (from + 2 < to)
98 sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
99 return;
100 }
101 }
102 }
103
104 if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
105 // The attribute nodes and namespace nodes of an element occur before
106 // the children of the element. The namespace nodes are defined to occur
107 // before the attribute nodes. The relative order of namespace nodes is
108 // implementation-dependent. The relative order of attribute nodes is
109 // implementation-dependent.
110 unsigned sortedEnd = from;
111 // FIXME: namespace nodes are not implemented.
112 for (unsigned i = sortedEnd; i < to; ++i) {
113 Node* n = parentMatrix[i][0];
114 if (n->isAttributeNode() && toAttr(n)->ownerElement() == commonAncestor)
115 parentMatrix[i].swap(parentMatrix[sortedEnd++]);
116 }
117 if (sortedEnd != from) {
118 if (to - sortedEnd > 1)
119 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
120 return;
121 }
122 }
123
124 // Children nodes of the common ancestor induce a subdivision of our
125 // node-set. Sort it according to this subdivision, and recursively sort
126 // each group.
127 WillBeHeapHashSet<RawPtrWillBeMember<Node> > parentNodes;
128 for (unsigned i = from; i < to; ++i)
129 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
130
131 unsigned previousGroupEnd = from;
132 unsigned groupEnd = from;
133 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
134 // If parentNodes contains the node, perform a linear search to move its
135 // children in the node-set to the beginning.
136 if (parentNodes.contains(n)) {
137 for (unsigned i = groupEnd; i < to; ++i) {
138 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
139 parentMatrix[i].swap(parentMatrix[groupEnd++]);
140 }
141
142 if (groupEnd - previousGroupEnd > 1)
143 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
144
145 ASSERT(previousGroupEnd != groupEnd);
146 previousGroupEnd = groupEnd;
147 #ifndef NDEBUG
148 parentNodes.remove(n);
149 #endif
150 }
151 }
152
153 ASSERT(parentNodes.isEmpty());
154 }
155
sort() const156 void NodeSet::sort() const
157 {
158 if (m_isSorted)
159 return;
160
161 unsigned nodeCount = m_nodes.size();
162 if (nodeCount < 2) {
163 const_cast<bool&>(m_isSorted) = true;
164 return;
165 }
166
167 if (nodeCount > traversalSortCutoff) {
168 traversalSort();
169 return;
170 }
171
172 bool containsAttributeNodes = false;
173
174 WillBeHeapVector<NodeSetVector> parentMatrix(nodeCount);
175 for (unsigned i = 0; i < nodeCount; ++i) {
176 NodeSetVector& parentsVector = parentMatrix[i];
177 Node* n = m_nodes[i].get();
178 parentsVector.append(n);
179 if (n->isAttributeNode()) {
180 n = toAttr(n)->ownerElement();
181 parentsVector.append(n);
182 containsAttributeNodes = true;
183 }
184 while ((n = n->parentNode()))
185 parentsVector.append(n);
186 }
187 sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
188
189 // It is not possible to just assign the result to m_nodes, because some
190 // nodes may get dereferenced and destroyed.
191 WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes;
192 sortedNodes.reserveInitialCapacity(nodeCount);
193 for (unsigned i = 0; i < nodeCount; ++i)
194 sortedNodes.append(parentMatrix[i][0]);
195
196 const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
197 }
198
findRootNode(Node * node)199 static Node* findRootNode(Node* node)
200 {
201 if (node->isAttributeNode())
202 node = toAttr(node)->ownerElement();
203 if (node->inDocument()) {
204 node = &node->document();
205 } else {
206 while (Node* parent = node->parentNode())
207 node = parent;
208 }
209 return node;
210 }
211
traversalSort() const212 void NodeSet::traversalSort() const
213 {
214 WillBeHeapHashSet<RawPtrWillBeMember<Node> > nodes;
215 bool containsAttributeNodes = false;
216
217 unsigned nodeCount = m_nodes.size();
218 ASSERT(nodeCount > 1);
219 for (unsigned i = 0; i < nodeCount; ++i) {
220 Node* node = m_nodes[i].get();
221 nodes.add(node);
222 if (node->isAttributeNode())
223 containsAttributeNodes = true;
224 }
225
226 WillBeHeapVector<RefPtrWillBeMember<Node> > sortedNodes;
227 sortedNodes.reserveInitialCapacity(nodeCount);
228
229 for (Node* n = findRootNode(m_nodes.first().get()); n; n = NodeTraversal::next(*n)) {
230 if (nodes.contains(n))
231 sortedNodes.append(n);
232
233 if (!containsAttributeNodes || !n->isElementNode())
234 continue;
235
236 Element* element = toElement(n);
237 if (!element->hasAttributes())
238 continue;
239
240 AttributeCollection attributes = element->attributes();
241 AttributeCollection::const_iterator end = attributes.end();
242 for (AttributeCollection::const_iterator it = attributes.begin(); it != end; ++it) {
243 RefPtrWillBeRawPtr<Attr> attr = element->attrIfExists(it->name());
244 if (attr && nodes.contains(attr.get()))
245 sortedNodes.append(attr);
246 }
247 }
248
249 ASSERT(sortedNodes.size() == nodeCount);
250 const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
251 }
252
reverse()253 void NodeSet::reverse()
254 {
255 if (m_nodes.isEmpty())
256 return;
257
258 unsigned from = 0;
259 unsigned to = m_nodes.size() - 1;
260 while (from < to) {
261 m_nodes[from].swap(m_nodes[to]);
262 ++from;
263 --to;
264 }
265 }
266
firstNode() const267 Node* NodeSet::firstNode() const
268 {
269 if (isEmpty())
270 return 0;
271
272 // FIXME: fully sorting the node-set just to find its first node is
273 // wasteful.
274 sort();
275 return m_nodes.at(0).get();
276 }
277
anyNode() const278 Node* NodeSet::anyNode() const
279 {
280 if (isEmpty())
281 return 0;
282
283 return m_nodes.at(0).get();
284 }
285
286 }
287 }
288