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 

    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)