Home | History | Annotate | Download | only in xml 
      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/Element.h"
     31 #include "core/dom/NodeTraversal.h"
     32 
     33 namespace WebCore {
     34 namespace 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).
     38 const unsigned traversalSortCutoff = 10000;
     39 
     40 static 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 
     46 static 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 
    137 void NodeSet::sort() const
    138 {
    139     if (m_isSorted)
    140         return;
    141 
    142     unsigned nodeCount = m_nodes.size();
    143     if (nodeCount < 2) {
    144         const_cast<bool&>(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     const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
    177 }
    178 
    179 static Node* findRootNode(Node* node)
    180 {
    181     if (node->isAttributeNode())
    182         node = toAttr(node)->ownerElement();
    183     if (node->inDocument())
    184         node = &node->document();
    185     else {
    186         while (Node* parent = node->parentNode())
    187             node = parent;
    188     }
    189     return node;
    190 }
    191 
    192 void NodeSet::traversalSort() const
    193 {
    194     HashSet<Node*> nodes;
    195     bool containsAttributeNodes = false;
    196 
    197     unsigned nodeCount = m_nodes.size();
    198     ASSERT(nodeCount > 1);
    199     for (unsigned i = 0; i < nodeCount; ++i) {
    200         Node* node = m_nodes[i].get();
    201         nodes.add(node);
    202         if (node->isAttributeNode())
    203             containsAttributeNodes = true;
    204     }
    205 
    206     Vector<RefPtr<Node> > sortedNodes;
    207     sortedNodes.reserveInitialCapacity(nodeCount);
    208 
    209     for (Node* n = findRootNode(m_nodes.first().get()); n; n = NodeTraversal::next(*n)) {
    210         if (nodes.contains(n))
    211             sortedNodes.append(n);
    212 
    213         if (!containsAttributeNodes || !n->isElementNode())
    214             continue;
    215 
    216         Element* element = toElement(n);
    217         if (!element->hasAttributes())
    218             continue;
    219 
    220         unsigned attributeCount = element->attributeCount();
    221         for (unsigned i = 0; i < attributeCount; ++i) {
    222             RefPtr<Attr> attr = element->attrIfExists(element->attributeItem(i)->name());
    223             if (attr && nodes.contains(attr.get()))
    224                 sortedNodes.append(attr);
    225         }
    226     }
    227 
    228     ASSERT(sortedNodes.size() == nodeCount);
    229     const_cast<Vector<RefPtr<Node> >&>(m_nodes).swap(sortedNodes);
    230 }
    231 
    232 void NodeSet::reverse()
    233 {
    234     if (m_nodes.isEmpty())
    235         return;
    236 
    237     unsigned from = 0;
    238     unsigned to = m_nodes.size() - 1;
    239     while (from < to) {
    240         m_nodes[from].swap(m_nodes[to]);
    241         ++from;
    242         --to;
    243     }
    244 }
    245 
    246 Node* NodeSet::firstNode() const
    247 {
    248     if (isEmpty())
    249         return 0;
    250 
    251     sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
    252     return m_nodes.at(0).get();
    253 }
    254 
    255 Node* NodeSet::anyNode() const
    256 {
    257     if (isEmpty())
    258         return 0;
    259 
    260     return m_nodes.at(0).get();
    261 }
    262 
    263 }
    264 }
    265