1 /* 2 * Copyright (C) 2007 Alexey Proskuryakov <ap (at) 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 34 namespace blink { 35 namespace 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). 40 const unsigned traversalSortCutoff = 10000; 41 42 typedef WillBeHeapVector<RawPtrWillBeMember<Node> > NodeSetVector; 43 44 PassOwnPtrWillBeRawPtr<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 53 static inline Node* parentWithDepth(unsigned depth, const NodeSetVector& parents) 54 { 55 ASSERT(parents.size() >= depth + 1); 56 return parents[parents.size() - 1 - depth]; 57 } 58 59 static 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 156 void 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 199 static 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 212 void 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 250 void 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 264 Node* 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 275 Node* NodeSet::anyNode() const 276 { 277 if (isEmpty()) 278 return 0; 279 280 return m_nodes.at(0).get(); 281 } 282 283 } 284 } 285