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/Node.h"
     32 #include "core/dom/NodeTraversal.h"
     33 
     34 namespace WebCore {
     35 namespace 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).
     39 const unsigned traversalSortCutoff = 10000;
     40 
     41 static 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 
     47 static 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() && toAttr(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 
    138 void 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 = toAttr(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 
    180 static 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 
    193 void 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 
    233 void 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 
    247 Node* 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 
    256 Node* NodeSet::anyNode() const
    257 {
    258     if (isEmpty())
    259         return 0;
    260 
    261     return m_nodes.at(0).get();
    262 }
    263 
    264 }
    265 }
    266