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 
28 #if ENABLE(XPATH)
29 #include "XPathNodeSet.h"
30 
31 #include "Attr.h"
32 #include "Element.h"
33 #include "Node.h"
34 
35 namespace WebCore {
36 namespace XPath {
37 
parentWithDepth(unsigned depth,const Vector<Node * > & parents)38 static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
39 {
40     ASSERT(parents.size() >= depth + 1);
41     return parents[parents.size() - 1 - depth];
42 }
43 
sortBlock(unsigned from,unsigned to,Vector<Vector<Node * >> & parentMatrix,bool mayContainAttributeNodes)44 static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)
45 {
46     ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
47     unsigned minDepth = UINT_MAX;
48     for (unsigned i = from; i < to; ++i) {
49         unsigned depth = parentMatrix[i].size() - 1;
50         if (minDepth > depth)
51             minDepth = depth;
52     }
53 
54     // Find the common ancestor.
55     unsigned commonAncestorDepth = minDepth;
56     Node* commonAncestor;
57     while (true) {
58         commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
59         if (commonAncestorDepth == 0)
60             break;
61 
62         bool allEqual = true;
63         for (unsigned i = from + 1; i < to; ++i) {
64             if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
65                 allEqual = false;
66                 break;
67             }
68         }
69         if (allEqual)
70             break;
71 
72         --commonAncestorDepth;
73     }
74 
75     if (commonAncestorDepth == minDepth) {
76         // One of the nodes is the common ancestor => it is the first in document order.
77         // Find it and move it to the beginning.
78         for (unsigned i = from; i < to; ++i)
79             if (commonAncestor == parentMatrix[i][0]) {
80                 parentMatrix[i].swap(parentMatrix[from]);
81                 if (from + 2 < to)
82                     sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
83                 return;
84             }
85     }
86 
87     if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
88         // The attribute nodes and namespace nodes of an element occur before the children of the element.
89         // The namespace nodes are defined to occur before the attribute nodes.
90         // The relative order of namespace nodes is implementation-dependent.
91         // The relative order of attribute nodes is implementation-dependent.
92         unsigned sortedEnd = from;
93         // FIXME: namespace nodes are not implemented.
94         for (unsigned i = sortedEnd; i < to; ++i) {
95             Node* n = parentMatrix[i][0];
96             if (n->isAttributeNode() && static_cast<Attr*>(n)->ownerElement() == commonAncestor)
97                 parentMatrix[i].swap(parentMatrix[sortedEnd++]);
98         }
99         if (sortedEnd != from) {
100             if (to - sortedEnd > 1)
101                 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
102             return;
103         }
104     }
105 
106     // Children nodes of the common ancestor induce a subdivision of our node-set.
107     // Sort it according to this subdivision, and recursively sort each group.
108     HashSet<Node*> parentNodes;
109     for (unsigned i = from; i < to; ++i)
110         parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
111 
112     unsigned previousGroupEnd = from;
113     unsigned groupEnd = from;
114     for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
115         // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.
116         if (parentNodes.contains(n)) {
117             for (unsigned i = groupEnd; i < to; ++i)
118                 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
119                     parentMatrix[i].swap(parentMatrix[groupEnd++]);
120 
121             if (groupEnd - previousGroupEnd > 1)
122                 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
123 
124             ASSERT(previousGroupEnd != groupEnd);
125             previousGroupEnd = groupEnd;
126 #ifndef NDEBUG
127             parentNodes.remove(n);
128 #endif
129         }
130     }
131 
132     ASSERT(parentNodes.isEmpty());
133 }
134 
sort() const135 void NodeSet::sort() const
136 {
137     if (m_isSorted)
138         return;
139 
140     unsigned nodeCount = m_nodes.size();
141     if (nodeCount < 2) {
142         const_cast<bool&>(m_isSorted) = true;
143         return;
144     }
145 
146     bool containsAttributeNodes = false;
147 
148     Vector<Vector<Node*> > parentMatrix(nodeCount);
149     for (unsigned i = 0; i < nodeCount; ++i) {
150         Vector<Node*>& parentsVector = parentMatrix[i];
151         Node* n = m_nodes[i].get();
152         parentsVector.append(n);
153         if (n->isAttributeNode()) {
154             n = static_cast<Attr*>(n)->ownerElement();
155             parentsVector.append(n);
156             containsAttributeNodes = true;
157         }
158         while ((n = n->parentNode()))
159             parentsVector.append(n);
160     }
161     sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
162 
163     // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.
164     Vector<RefPtr<Node> > sortedNodes;
165     sortedNodes.reserveInitialCapacity(nodeCount);
166     for (unsigned i = 0; i < nodeCount; ++i)
167         sortedNodes.append(parentMatrix[i][0]);
168 
169     const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);
170 }
171 
reverse()172 void NodeSet::reverse()
173 {
174     if (m_nodes.isEmpty())
175         return;
176 
177     unsigned from = 0;
178     unsigned to = m_nodes.size() - 1;
179     while (from < to) {
180         m_nodes[from].swap(m_nodes[to]);
181         ++from;
182         --to;
183     }
184 }
185 
firstNode() const186 Node* NodeSet::firstNode() const
187 {
188     if (isEmpty())
189         return 0;
190 
191     sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
192     return m_nodes.at(0).get();
193 }
194 
anyNode() const195 Node* NodeSet::anyNode() const
196 {
197     if (isEmpty())
198         return 0;
199 
200     return m_nodes.at(0).get();
201 }
202 
203 }
204 }
205 
206 #endif // ENABLE(XPATH)
207