Generated should not be supported for things with a shadow
[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
33 namespace WebCore {
34 namespace 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).
38 const unsigned traversalSortCutoff = 10000;
39
40 static 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
46 static 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* n = parentMatrix[i][0];
98             if (n->isAttributeNode() && static_cast<Attr*>(n)->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
137 void NodeSet::sort() const
138 {
139     if (m_isSorted)
140         return;
141
142     unsigned nodeCount = m_nodes.size();
143     if (nodeCount < 2) {
144         const_cast<bool&>(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* n = m_nodes[i].get();
159         parentsVector.append(n);
160         if (n->isAttributeNode()) {
161             n = static_cast<Attr*>(n)->ownerElement();
162             parentsVector.append(n);
163             containsAttributeNodes = true;
164         }
165         while ((n = n->parentNode()))
166             parentsVector.append(n);
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     const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
177 }
178
179 static Node* findRootNode(Node* node)
180 {
181     if (node->isAttributeNode())
182         node = static_cast<Attr*>(node)->ownerElement();
183     if (node->inDocument())
184         node = node->document();
185     else {
186         while (Node* parent = node->parentNode())
187             node = parent;
188     }
189     return node;
190 }
191
192 void NodeSet::traversalSort() const
193 {
194     HashSet<Node*> nodes;
195     bool containsAttributeNodes = false;
196
197     unsigned nodeCount = m_nodes.size();
198     ASSERT(nodeCount > 1);
199     for (unsigned i = 0; i < nodeCount; ++i) {
200         Node* node = m_nodes[i].get();
201         nodes.add(node);
202         if (node->isAttributeNode())
203             containsAttributeNodes = true;
204     }
205
206     Vector<RefPtr<Node> > sortedNodes;
207     sortedNodes.reserveInitialCapacity(nodeCount);
208
209     for (Node* n = findRootNode(m_nodes.first().get()); n; n = n->traverseNextNode()) {
210         if (nodes.contains(n))
211             sortedNodes.append(n);
212
213         if (!containsAttributeNodes || !n->isElementNode())
214             continue;
215
216         Element* element = toElement(n);
217         if (!element->hasAttributes())
218             continue;
219
220         unsigned attributeCount = element->attributeCount();
221         for (unsigned i = 0; i < attributeCount; ++i) {
222             RefPtr<Attr> attr = element->attrIfExists(element->attributeItem(i)->name());
223             if (attr && nodes.contains(attr.get()))
224                 sortedNodes.append(attr);
225         }
226     }
227
228     ASSERT(sortedNodes.size() == nodeCount);
229     const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
230 }
231
232 void NodeSet::reverse()
233 {
234     if (m_nodes.isEmpty())
235         return;
236
237     unsigned from = 0;
238     unsigned to = m_nodes.size() - 1;
239     while (from < to) {
240         m_nodes[from].swap(m_nodes[to]);
241         ++from;
242         --to;
243     }
244 }
245
246 Node* NodeSet::firstNode() const
247 {
248     if (isEmpty())
249         return 0;
250
251     sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
252     return m_nodes.at(0).get();
253 }
254
255 Node* NodeSet::anyNode() const
256 {
257     if (isEmpty())
258         return 0;
259
260     return m_nodes.at(0).get();
261 }
262
263 }
264 }