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/Document.h"
     31 #include "core/dom/Element.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
     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 #ifndef NDEBUG
    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         while ((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 = findRootNode(m_nodes.first().get()); n; n = NodeTraversal::next(*n)) {
    230         if (nodes.contains(n))
    231             sortedNodes.append(n);
    232 
    233         if (!containsAttributeNodes || !n->isElementNode())
    234             continue;
    235 
    236         Element* element = toElement(n);
    237         if (!element->hasAttributes())
    238             continue;
    239 
    240         AttributeCollection attributes = element->attributes();
    241         AttributeCollection::const_iterator end = attributes.end();
    242         for (AttributeCollection::const_iterator it = attributes.begin(); it != end; ++it) {
    243             RefPtrWillBeRawPtr<Attr> attr = element->attrIfExists(it->name());
    244             if (attr && nodes.contains(attr.get()))
    245                 sortedNodes.append(attr);
    246         }
    247     }
    248 
    249     ASSERT(sortedNodes.size() == nodeCount);
    250     const_cast<WillBeHeapVector<RefPtrWillBeMember<Node> >&>(m_nodes).swap(sortedNodes);
    251 }
    252 
    253 void NodeSet::reverse()
    254 {
    255     if (m_nodes.isEmpty())
    256         return;
    257 
    258     unsigned from = 0;
    259     unsigned to = m_nodes.size() - 1;
    260     while (from < to) {
    261         m_nodes[from].swap(m_nodes[to]);
    262         ++from;
    263         --to;
    264     }
    265 }
    266 
    267 Node* NodeSet::firstNode() const
    268 {
    269     if (isEmpty())
    270         return 0;
    271 
    272     // FIXME: fully sorting the node-set just to find its first node is
    273     // wasteful.
    274     sort();
    275     return m_nodes.at(0).get();
    276 }
    277 
    278 Node* NodeSet::anyNode() const
    279 {
    280     if (isEmpty())
    281         return 0;
    282 
    283     return m_nodes.at(0).get();
    284 }
    285 
    286 }
    287 }
    288