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 
     28 #if ENABLE(XPATH)
     29 #include "XPathNodeSet.h"
     30 
     31 #include "Attr.h"
     32 #include "Element.h"
     33 #include "Node.h"
     34 
     35 namespace WebCore {
     36 namespace XPath {
     37 
     38 static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
     39 {
     40     ASSERT(parents.size() >= depth + 1);
     41     return parents[parents.size() - 1 - depth];
     42 }
     43 
     44 static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)
     45 {
     46     ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
     47     unsigned minDepth = UINT_MAX;
     48     for (unsigned i = from; i < to; ++i) {
     49         unsigned depth = parentMatrix[i].size() - 1;
     50         if (minDepth > depth)
     51             minDepth = depth;
     52     }
     53 
     54     // Find the common ancestor.
     55     unsigned commonAncestorDepth = minDepth;
     56     Node* commonAncestor;
     57     while (true) {
     58         commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
     59         if (commonAncestorDepth == 0)
     60             break;
     61 
     62         bool allEqual = true;
     63         for (unsigned i = from + 1; i < to; ++i) {
     64             if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
     65                 allEqual = false;
     66                 break;
     67             }
     68         }
     69         if (allEqual)
     70             break;
     71 
     72         --commonAncestorDepth;
     73     }
     74 
     75     if (commonAncestorDepth == minDepth) {
     76         // One of the nodes is the common ancestor => it is the first in document order.
     77         // Find it and move it to the beginning.
     78         for (unsigned i = from; i < to; ++i)
     79             if (commonAncestor == parentMatrix[i][0]) {
     80                 parentMatrix[i].swap(parentMatrix[from]);
     81                 if (from + 2 < to)
     82                     sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
     83                 return;
     84             }
     85     }
     86 
     87     if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
     88         // The attribute nodes and namespace nodes of an element occur before the children of the element.
     89         // The namespace nodes are defined to occur before the attribute nodes.
     90         // The relative order of namespace nodes is implementation-dependent.
     91         // The relative order of attribute nodes is implementation-dependent.
     92         unsigned sortedEnd = from;
     93         // FIXME: namespace nodes are not implemented.
     94         for (unsigned i = sortedEnd; i < to; ++i) {
     95             Node* n = parentMatrix[i][0];
     96             if (n->isAttributeNode() && static_cast<Attr*>(n)->ownerElement() == commonAncestor)
     97                 parentMatrix[i].swap(parentMatrix[sortedEnd++]);
     98         }
     99         if (sortedEnd != from) {
    100             if (to - sortedEnd > 1)
    101                 sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
    102             return;
    103         }
    104     }
    105 
    106     // Children nodes of the common ancestor induce a subdivision of our node-set.
    107     // Sort it according to this subdivision, and recursively sort each group.
    108     HashSet<Node*> parentNodes;
    109     for (unsigned i = from; i < to; ++i)
    110         parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
    111 
    112     unsigned previousGroupEnd = from;
    113     unsigned groupEnd = from;
    114     for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
    115         // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.
    116         if (parentNodes.contains(n)) {
    117             for (unsigned i = groupEnd; i < to; ++i)
    118                 if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
    119                     parentMatrix[i].swap(parentMatrix[groupEnd++]);
    120 
    121             if (groupEnd - previousGroupEnd > 1)
    122                 sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
    123 
    124             ASSERT(previousGroupEnd != groupEnd);
    125             previousGroupEnd = groupEnd;
    126 #ifndef NDEBUG
    127             parentNodes.remove(n);
    128 #endif
    129         }
    130     }
    131 
    132     ASSERT(parentNodes.isEmpty());
    133 }
    134 
    135 void NodeSet::sort() const
    136 {
    137     if (m_isSorted)
    138         return;
    139 
    140     unsigned nodeCount = m_nodes.size();
    141     if (nodeCount < 2) {
    142         const_cast<bool&>(m_isSorted) = true;
    143         return;
    144     }
    145 
    146     bool containsAttributeNodes = false;
    147 
    148     Vector<Vector<Node*> > parentMatrix(nodeCount);
    149     for (unsigned i = 0; i < nodeCount; ++i) {
    150         Vector<Node*>& parentsVector = parentMatrix[i];
    151         Node* n = m_nodes[i].get();
    152         parentsVector.append(n);
    153         if (n->isAttributeNode()) {
    154             n = static_cast<Attr*>(n)->ownerElement();
    155             parentsVector.append(n);
    156             containsAttributeNodes = true;
    157         }
    158         while ((n = n->parent()))
    159             parentsVector.append(n);
    160     }
    161     sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
    162 
    163     // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.
    164     Vector<RefPtr<Node> > sortedNodes;
    165     sortedNodes.reserveInitialCapacity(nodeCount);
    166     for (unsigned i = 0; i < nodeCount; ++i)
    167         sortedNodes.append(parentMatrix[i][0]);
    168 
    169     const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);
    170 }
    171 
    172 void NodeSet::reverse()
    173 {
    174     if (m_nodes.isEmpty())
    175         return;
    176 
    177     unsigned from = 0;
    178     unsigned to = m_nodes.size() - 1;
    179     while (from < to) {
    180         m_nodes[from].swap(m_nodes[to]);
    181         ++from;
    182         --to;
    183     }
    184 }
    185 
    186 Node* NodeSet::firstNode() const
    187 {
    188     if (isEmpty())
    189         return 0;
    190 
    191     sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
    192     return m_nodes.at(0).get();
    193 }
    194 
    195 Node* NodeSet::anyNode() const
    196 {
    197     if (isEmpty())
    198         return 0;
    199 
    200     return m_nodes.at(0).get();
    201 }
    202 
    203 }
    204 }
    205 
    206 #endif // ENABLE(XPATH)
    207