src/third_party/WebKit/Source/core/xml/XPathNodeSet.cpp

   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
  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 : NodeTraversal::startsAt(findRootNode(m_nodes.first().get()))) {
 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 }