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