| /* |
| * Copyright (C) 2007 Alexey Proskuryakov <[email protected]> |
| * Copyright (C) 2012-2025 Apple Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions |
| * are met: |
| * |
| * 1. Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * 2. Redistributions in binary form must reproduce the above copyright |
| * notice, this list of conditions and the following disclaimer in the |
| * documentation and/or other materials provided with the distribution. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. |
| * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, |
| * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF |
| * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "config.h" |
| #include "XPathNodeSet.h" |
| |
| #include "Attr.h" |
| #include "Attribute.h" |
| #include "Document.h" |
| #include "ElementInlines.h" |
| #include "NodeTraversal.h" |
| |
| namespace WebCore::XPath { |
| |
| // When a node set is large, sorting it by traversing the whole document is better (we can |
| // assume that we aren't dealing with documents that we cannot even traverse in reasonable time). |
| const unsigned traversalSortCutoff = 10000; |
| |
| static inline Node* parentWithDepth(unsigned depth, const Vector<Ref<Node>>& parents) |
| { |
| ASSERT(parents.size() >= depth + 1); |
| return parents[parents.size() - 1 - depth].ptr(); |
| } |
| |
| static void sortBlock(unsigned from, unsigned to, Vector<Vector<Ref<Node>>>& parentMatrix, bool mayContainAttributeNodes) |
| { |
| ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort. |
| unsigned minDepth = UINT_MAX; |
| for (unsigned i = from; i < to; ++i) { |
| unsigned depth = parentMatrix[i].size() - 1; |
| if (minDepth > depth) |
| minDepth = depth; |
| } |
| |
| // Find the common ancestor. |
| unsigned commonAncestorDepth = minDepth; |
| RefPtr<Node> commonAncestor; |
| while (true) { |
| commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]); |
| if (commonAncestorDepth == 0) |
| break; |
| |
| bool allEqual = true; |
| for (unsigned i = from + 1; i < to; ++i) { |
| if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) { |
| allEqual = false; |
| break; |
| } |
| } |
| if (allEqual) |
| break; |
| |
| --commonAncestorDepth; |
| } |
| |
| if (commonAncestorDepth == minDepth) { |
| // One of the nodes is the common ancestor => it is the first in document order. |
| // Find it and move it to the beginning. |
| for (unsigned i = from; i < to; ++i) |
| if (commonAncestor.get() == parentMatrix[i][0].ptr()) { |
| parentMatrix[i].swap(parentMatrix[from]); |
| if (from + 2 < to) |
| sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes); |
| return; |
| } |
| } |
| |
| if (mayContainAttributeNodes && commonAncestor->isElementNode()) { |
| // The attribute nodes and namespace nodes of an element occur before the children of the element. |
| // The namespace nodes are defined to occur before the attribute nodes. |
| // The relative order of namespace nodes is implementation-dependent. |
| // The relative order of attribute nodes is implementation-dependent. |
| unsigned sortedEnd = from; |
| // FIXME: namespace nodes are not implemented. |
| for (unsigned i = sortedEnd; i < to; ++i) { |
| if (RefPtr attr = dynamicDowncast<Attr>(parentMatrix[i][0].get()); attr && attr->ownerElement() == commonAncestor) |
| parentMatrix[i].swap(parentMatrix[sortedEnd++]); |
| } |
| if (sortedEnd != from) { |
| if (to - sortedEnd > 1) |
| sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes); |
| return; |
| } |
| } |
| |
| // Children nodes of the common ancestor induce a subdivision of our node-set. |
| // Sort it according to this subdivision, and recursively sort each group. |
| HashSet<Ref<Node>> parentNodes; |
| for (unsigned i = from; i < to; ++i) |
| parentNodes.add(*parentWithDepth(commonAncestorDepth + 1, parentMatrix[i])); |
| |
| unsigned previousGroupEnd = from; |
| unsigned groupEnd = from; |
| for (RefPtr node = commonAncestor->firstChild(); node; node = node->nextSibling()) { |
| // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning. |
| if (parentNodes.contains(*node)) { |
| for (unsigned i = groupEnd; i < to; ++i) |
| if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == node) |
| parentMatrix[i].swap(parentMatrix[groupEnd++]); |
| |
| if (groupEnd - previousGroupEnd > 1) |
| sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes); |
| |
| ASSERT(previousGroupEnd != groupEnd); |
| previousGroupEnd = groupEnd; |
| #if ASSERT_ENABLED |
| parentNodes.remove(*node); |
| #endif |
| } |
| } |
| |
| ASSERT(parentNodes.isEmpty()); |
| } |
| |
| void NodeSet::sort() const |
| { |
| if (m_isSorted) |
| return; |
| |
| unsigned nodeCount = m_nodes.size(); |
| if (nodeCount < 2) { |
| m_isSorted = true; |
| return; |
| } |
| |
| if (nodeCount > traversalSortCutoff) { |
| traversalSort(); |
| return; |
| } |
| |
| bool containsAttributeNodes = false; |
| |
| Vector<Vector<Ref<Node>>> parentMatrix(nodeCount); |
| for (unsigned i = 0; i < nodeCount; ++i) { |
| auto& parentsVector = parentMatrix[i]; |
| RefPtr node = m_nodes[i].ptr(); |
| parentsVector.append(*node); |
| if (RefPtr attr = dynamicDowncast<Attr>(*node)) { |
| ASSERT(attr->ownerElement()); |
| if ((node = attr->ownerElement())) { |
| parentsVector.append(*node); |
| containsAttributeNodes = true; |
| } |
| } |
| while ((node = node->parentNode())) |
| parentsVector.append(*node); |
| } |
| sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes); |
| |
| // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed. |
| Vector<Ref<Node>> sortedNodes; |
| sortedNodes.reserveInitialCapacity(nodeCount); |
| for (unsigned i = 0; i < nodeCount; ++i) |
| sortedNodes.append(WTF::move(parentMatrix[i][0])); |
| |
| m_nodes = WTF::move(sortedNodes); |
| m_isSorted = true; |
| } |
| |
| static inline RefPtr<Node> findRootNode(Node* node) |
| { |
| RefPtr<Node> current = node; |
| if (RefPtr attr = dynamicDowncast<Attr>(*current)) |
| current = attr->ownerElement(); |
| if (current->isConnected()) |
| return current->protectedDocument(); |
| for (RefPtr parent = current->parentNode(); parent; parent = current->parentNode()) |
| current = WTF::move(parent); |
| return current; |
| } |
| |
| void NodeSet::traversalSort() const |
| { |
| HashSet<Ref<Node>> nodes; |
| bool containsAttributeNodes = false; |
| |
| unsigned nodeCount = m_nodes.size(); |
| ASSERT(nodeCount > 1); |
| for (auto& node : m_nodes) { |
| nodes.add(node.copyRef()); |
| if (is<Attr>(node.get())) |
| containsAttributeNodes = true; |
| } |
| |
| Vector<Ref<Node>> sortedNodes; |
| sortedNodes.reserveInitialCapacity(nodeCount); |
| |
| for (RefPtr node = findRootNode(m_nodes.first().ptr()); node; node = NodeTraversal::next(*node)) { |
| if (nodes.contains(*node)) |
| sortedNodes.append(*node); |
| |
| if (!containsAttributeNodes) |
| continue; |
| |
| RefPtr element = dynamicDowncast<Element>(*node); |
| if (!element || !element->hasAttributes()) |
| continue; |
| |
| for (auto& attribute : element->attributes()) { |
| RefPtr attr = element->attrIfExists(attribute.name()); |
| if (attr && nodes.contains(*attr)) |
| sortedNodes.append(*attr); |
| } |
| } |
| |
| ASSERT(sortedNodes.size() == nodeCount); |
| m_nodes = WTF::move(sortedNodes); |
| m_isSorted = true; |
| } |
| |
| Node* NodeSet::firstNode() const |
| { |
| if (isEmpty()) |
| return nullptr; |
| |
| sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful. |
| return m_nodes.at(0).ptr(); |
| } |
| |
| Node* NodeSet::anyNode() const |
| { |
| if (isEmpty()) |
| return nullptr; |
| |
| return m_nodes.at(0).ptr(); |
| } |
| |
| } // namespace WebCore::XPath |
