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
34namespace blink {
35namespace 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).
40const unsigned traversalSortCutoff = 10000;
41
42typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector;
43
44PassOwnPtrWillBeRawPtr<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
53static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents)
54{
55    ASSERT(parents.size() >= depth + 1);
56    return parents[parents.size() - 1 - depth];
57}
58
59static 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#if ENABLE(ASSERT)
148            parentNodes.remove(n);
149#endif
150        }
151    }
152
153    ASSERT(parentNodes.isEmpty());
154}
155
156void 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        for (n = n->parentNode(); n; 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
199static 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
212void 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        AttributeCollection attributes = element->attributes();
238        AttributeCollection::iterator end = attributes.end();
239        for (AttributeCollection::iterator it = attributes.begin(); it != end; ++it) {
240            RefPtrWillBeRawPtr<Attr> attr = element->attrIfExists(it->name());
241            if (attr && nodes.contains(attr.get()))
242                sortedNodes.append(attr);
243        }
244    }
245
246    ASSERT(sortedNodes.size() == nodeCount);
247    const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
248}
249
250void NodeSet::reverse()
251{
252    if (m_nodes.isEmpty())
253        return;
254
255    unsigned from = 0;
256    unsigned to = m_nodes.size() - 1;
257    while (from < to) {
258        m_nodes[from].swap(m_nodes[to]);
259        ++from;
260        --to;
261    }
262}
263
264Node* NodeSet::firstNode() const
265{
266    if (isEmpty())
267        return 0;
268
269    // FIXME: fully sorting the node-set just to find its first node is
270    // wasteful.
271    sort();
272    return m_nodes.at(0).get();
273}
274
275Node* NodeSet::anyNode() const
276{
277    if (isEmpty())
278        return 0;
279
280    return m_nodes.at(0).get();
281}
282
283}
284}
285