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
34namespace WebCore {
35namespace 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).
39const unsigned traversalSortCutoff = 10000;
40
41static 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
47static 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() && static_cast<Attr*>(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
138void NodeSet::sort() const
139{
140    if (m_isSorted)
141        return;
142
143    unsigned nodeCount = m_nodes.size();
144    if (nodeCount < 2) {
145        const_cast<bool&>(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 = static_cast<Attr*>(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    const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
178}
179
180static Node* findRootNode(Node* node)
181{
182    if (node->isAttributeNode())
183        node = static_cast<Attr*>(node)->ownerElement();
184    if (node->inDocument())
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 (unsigned i = 0; i < nodeCount; ++i) {
201        Node* node = m_nodes[i].get();
202        nodes.add(node);
203        if (node->isAttributeNode())
204            containsAttributeNodes = true;
205    }
206
207    Vector<RefPtr<Node> > sortedNodes;
208    sortedNodes.reserveInitialCapacity(nodeCount);
209
210    for (Node* n = findRootNode(m_nodes.first().get()); n; n = NodeTraversal::next(n)) {
211        if (nodes.contains(n))
212            sortedNodes.append(n);
213
214        if (!containsAttributeNodes || !n->isElementNode())
215            continue;
216
217        Element* element = toElement(n);
218        if (!element->hasAttributes())
219            continue;
220
221        unsigned attributeCount = element->attributeCount();
222        for (unsigned i = 0; i < attributeCount; ++i) {
223            RefPtr<Attr> attr = element->attrIfExists(element->attributeItem(i)->name());
224            if (attr && nodes.contains(attr.get()))
225                sortedNodes.append(attr);
226        }
227    }
228
229    ASSERT(sortedNodes.size() == nodeCount);
230    const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
231}
232
233void NodeSet::reverse()
234{
235    if (m_nodes.isEmpty())
236        return;
237
238    unsigned from = 0;
239    unsigned to = m_nodes.size() - 1;
240    while (from < to) {
241        m_nodes[from].swap(m_nodes[to]);
242        ++from;
243        --to;
244    }
245}
246
247Node* NodeSet::firstNode() const
248{
249    if (isEmpty())
250        return 0;
251
252    sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
253    return m_nodes.at(0).get();
254}
255
256Node* NodeSet::anyNode() const
257{
258    if (isEmpty())
259        return 0;
260
261    return m_nodes.at(0).get();
262}
263
264}
265}
266