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 "NodeTraversal.h" 32 33namespace WebCore { 34namespace XPath { 35 36// When a node set is large, sorting it by traversing the whole document is better (we can 37// assume that we aren't dealing with documents that we cannot even traverse in reasonable time). 38const unsigned traversalSortCutoff = 10000; 39 40static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents) 41{ 42 ASSERT(parents.size() >= depth + 1); 43 return parents[parents.size() - 1 - depth]; 44} 45 46static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*>>& parentMatrix, bool mayContainAttributeNodes) 47{ 48 ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort. 49 unsigned minDepth = UINT_MAX; 50 for (unsigned i = from; i < to; ++i) { 51 unsigned depth = parentMatrix[i].size() - 1; 52 if (minDepth > depth) 53 minDepth = depth; 54 } 55 56 // Find the common ancestor. 57 unsigned commonAncestorDepth = minDepth; 58 Node* commonAncestor; 59 while (true) { 60 commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]); 61 if (commonAncestorDepth == 0) 62 break; 63 64 bool allEqual = true; 65 for (unsigned i = from + 1; i < to; ++i) { 66 if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) { 67 allEqual = false; 68 break; 69 } 70 } 71 if (allEqual) 72 break; 73 74 --commonAncestorDepth; 75 } 76 77 if (commonAncestorDepth == minDepth) { 78 // One of the nodes is the common ancestor => it is the first in document order. 79 // Find it and move it to the beginning. 80 for (unsigned i = from; i < to; ++i) 81 if (commonAncestor == parentMatrix[i][0]) { 82 parentMatrix[i].swap(parentMatrix[from]); 83 if (from + 2 < to) 84 sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes); 85 return; 86 } 87 } 88 89 if (mayContainAttributeNodes && commonAncestor->isElementNode()) { 90 // The attribute nodes and namespace nodes of an element occur before the children of the element. 91 // The namespace nodes are defined to occur before the attribute nodes. 92 // The relative order of namespace nodes is implementation-dependent. 93 // The relative order of attribute nodes is implementation-dependent. 94 unsigned sortedEnd = from; 95 // FIXME: namespace nodes are not implemented. 96 for (unsigned i = sortedEnd; i < to; ++i) { 97 Node* n = parentMatrix[i][0]; 98 if (n->isAttributeNode() && toAttr(n)->ownerElement() == commonAncestor) 99 parentMatrix[i].swap(parentMatrix[sortedEnd++]); 100 } 101 if (sortedEnd != from) { 102 if (to - sortedEnd > 1) 103 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes); 104 return; 105 } 106 } 107 108 // Children nodes of the common ancestor induce a subdivision of our node-set. 109 // Sort it according to this subdivision, and recursively sort each group. 110 HashSet<Node*> parentNodes; 111 for (unsigned i = from; i < to; ++i) 112 parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i])); 113 114 unsigned previousGroupEnd = from; 115 unsigned groupEnd = from; 116 for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) { 117 // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning. 118 if (parentNodes.contains(n)) { 119 for (unsigned i = groupEnd; i < to; ++i) 120 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n) 121 parentMatrix[i].swap(parentMatrix[groupEnd++]); 122 123 if (groupEnd - previousGroupEnd > 1) 124 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes); 125 126 ASSERT(previousGroupEnd != groupEnd); 127 previousGroupEnd = groupEnd; 128#ifndef NDEBUG 129 parentNodes.remove(n); 130#endif 131 } 132 } 133 134 ASSERT(parentNodes.isEmpty()); 135} 136 137void NodeSet::sort() const 138{ 139 if (m_isSorted) 140 return; 141 142 unsigned nodeCount = m_nodes.size(); 143 if (nodeCount < 2) { 144 m_isSorted = true; 145 return; 146 } 147 148 if (nodeCount > traversalSortCutoff) { 149 traversalSort(); 150 return; 151 } 152 153 bool containsAttributeNodes = false; 154 155 Vector<Vector<Node*>> parentMatrix(nodeCount); 156 for (unsigned i = 0; i < nodeCount; ++i) { 157 Vector<Node*>& parentsVector = parentMatrix[i]; 158 Node* n = m_nodes[i].get(); 159 parentsVector.append(n); 160 if (n->isAttributeNode()) { 161 n = toAttr(n)->ownerElement(); 162 parentsVector.append(n); 163 containsAttributeNodes = true; 164 } 165 while ((n = n->parentNode())) 166 parentsVector.append(n); 167 } 168 sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes); 169 170 // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed. 171 Vector<RefPtr<Node>> sortedNodes; 172 sortedNodes.reserveInitialCapacity(nodeCount); 173 for (unsigned i = 0; i < nodeCount; ++i) 174 sortedNodes.append(parentMatrix[i][0]); 175 176 m_nodes = WTF::move(sortedNodes); 177 m_isSorted = true; 178} 179 180static Node* findRootNode(Node* node) 181{ 182 if (node->isAttributeNode()) 183 node = toAttr(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 for (const Attribute& attribute : element->attributesIterator()) { 222 RefPtr<Attr> attr = element->attrIfExists(attribute.name()); 223 if (attr && nodes.contains(attr.get())) 224 sortedNodes.append(attr); 225 } 226 } 227 228 ASSERT(sortedNodes.size() == nodeCount); 229 m_nodes = WTF::move(sortedNodes); 230 m_isSorted = true; 231} 232 233Node* NodeSet::firstNode() const 234{ 235 if (isEmpty()) 236 return nullptr; 237 238 sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful. 239 return m_nodes.at(0).get(); 240} 241 242Node* NodeSet::anyNode() const 243{ 244 if (isEmpty()) 245 return nullptr; 246 247 return m_nodes.at(0).get(); 248} 249 250} 251} 252