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