diff options
Diffstat (limited to 'chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp')
| -rw-r--r-- | chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp | 452 |
1 files changed, 248 insertions, 204 deletions
diff --git a/chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp b/chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp index 4687257be64..43d71ddd0f2 100644 --- a/chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp +++ b/chromium/third_party/WebKit/Source/core/xml/XPathStep.cpp @@ -28,7 +28,7 @@ #include "config.h" #include "core/xml/XPathStep.h" -#include "XMLNSNames.h" +#include "core/XMLNSNames.h" #include "core/dom/Attr.h" #include "core/dom/Document.h" #include "core/dom/Element.h" @@ -41,13 +41,13 @@ namespace XPath { Step::Step(Axis axis, const NodeTest& nodeTest) : m_axis(axis) - , m_nodeTest(nodeTest) + , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest))) { } -Step::Step(Axis axis, const NodeTest& nodeTest, Vector<OwnPtr<Predicate> >& predicates) +Step::Step(Axis axis, const NodeTest& nodeTest, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates) : m_axis(axis) - , m_nodeTest(nodeTest) + , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest))) { m_predicates.swap(predicates); } @@ -56,16 +56,27 @@ Step::~Step() { } +void Step::trace(Visitor* visitor) +{ + visitor->trace(m_nodeTest); + visitor->trace(m_predicates); + ParseNode::trace(visitor); +} + void Step::optimize() { - // Evaluate predicates as part of node test if possible to avoid building unnecessary NodeSets. - // E.g., there is no need to build a set of all "foo" nodes to evaluate "foo[@bar]", we can check the predicate while enumerating. - // This optimization can be applied to predicates that are not context node list sensitive, or to first predicate that is only context position sensitive, e.g. foo[position() mod 2 = 0]. - Vector<OwnPtr<Predicate> > remainingPredicates; + // Evaluate predicates as part of node test if possible to avoid building + // unnecessary NodeSets. + // E.g., there is no need to build a set of all "foo" nodes to evaluate + // "foo[@bar]", we can check the predicate while enumerating. + // This optimization can be applied to predicates that are not context node + // list sensitive, or to first predicate that is only context position + // sensitive, e.g. foo[position() mod 2 = 0]. + WillBeHeapVector<OwnPtrWillBeMember<Predicate> > remainingPredicates; for (size_t i = 0; i < m_predicates.size(); ++i) { - OwnPtr<Predicate> predicate(m_predicates[i].release()); - if ((!predicate->isContextPositionSensitive() || m_nodeTest.mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) { - m_nodeTest.mergedPredicates().append(predicate.release()); + OwnPtrWillBeRawPtr<Predicate> predicate(m_predicates[i].release()); + if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) { + nodeTest().mergedPredicates().append(predicate.release()); } else { remainingPredicates.append(predicate.release()); } @@ -78,18 +89,19 @@ void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep) dropSecondStep = false; if (first->m_axis == Step::DescendantOrSelfAxis - && first->m_nodeTest.kind() == Step::NodeTest::AnyNodeTest + && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest && !first->m_predicates.size() - && !first->m_nodeTest.mergedPredicates().size()) { + && !first->nodeTest().mergedPredicates().size()) { - ASSERT(first->m_nodeTest.data().isEmpty()); - ASSERT(first->m_nodeTest.namespaceURI().isEmpty()); + ASSERT(first->nodeTest().data().isEmpty()); + ASSERT(first->nodeTest().namespaceURI().isEmpty()); - // Optimize the common case of "//" AKA /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest. + // Optimize the common case of "//" AKA + // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest. if (second->m_axis == Step::ChildAxis && second->predicatesAreContextListInsensitive()) { first->m_axis = Step::DescendantAxis; - first->m_nodeTest = Step::NodeTest(second->m_nodeTest.kind(), second->m_nodeTest.data(), second->m_nodeTest.namespaceURI()); - swap(second->m_nodeTest.mergedPredicates(), first->m_nodeTest.mergedPredicates()); + first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second->nodeTest().data(), second->nodeTest().namespaceURI()); + swap(second->nodeTest().mergedPredicates(), first->nodeTest().mergedPredicates()); swap(second->m_predicates, first->m_predicates); first->optimize(); dropSecondStep = true; @@ -105,8 +117,8 @@ bool Step::predicatesAreContextListInsensitive() const return false; } - for (size_t i = 0; i < m_nodeTest.mergedPredicates().size(); ++i) { - Predicate* predicate = m_nodeTest.mergedPredicates()[i].get(); + for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) { + Predicate* predicate = nodeTest().mergedPredicates()[i].get(); if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive()) return false; } @@ -125,9 +137,9 @@ void Step::evaluate(Node* context, NodeSet& nodes) const for (unsigned i = 0; i < m_predicates.size(); i++) { Predicate* predicate = m_predicates[i].get(); - NodeSet newNodes; + OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create()); if (!nodes.isSorted()) - newNodes.markSorted(false); + newNodes->markSorted(false); for (unsigned j = 0; j < nodes.size(); j++) { Node* node = nodes[j]; @@ -136,23 +148,21 @@ void Step::evaluate(Node* context, NodeSet& nodes) const evaluationContext.size = nodes.size(); evaluationContext.position = j + 1; if (predicate->evaluate()) - newNodes.append(node); + newNodes->append(node); } - nodes.swap(newNodes); + nodes.swap(*newNodes); } } -#if !ASSERT_DISABLED +#if ASSERT_ENABLED static inline Node::NodeType primaryNodeType(Step::Axis axis) { switch (axis) { - case Step::AttributeAxis: - return Node::ATTRIBUTE_NODE; - case Step::NamespaceAxis: - return Node::XPATH_NAMESPACE_NODE; - default: - return Node::ELEMENT_NODE; + case Step::AttributeAxis: + return Node::ATTRIBUTE_NODE; + default: + return Node::ELEMENT_NODE; } } #endif @@ -161,54 +171,62 @@ static inline Node::NodeType primaryNodeType(Step::Axis axis) static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest) { switch (nodeTest.kind()) { - case Step::NodeTest::TextNodeTest: - return node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE; - case Step::NodeTest::CommentNodeTest: - return node->nodeType() == Node::COMMENT_NODE; - case Step::NodeTest::ProcessingInstructionNodeTest: { - const AtomicString& name = nodeTest.data(); - return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name); - } - case Step::NodeTest::AnyNodeTest: - return true; - case Step::NodeTest::NameTest: { - const AtomicString& name = nodeTest.data(); - const AtomicString& namespaceURI = nodeTest.namespaceURI(); - - if (axis == Step::AttributeAxis) { - ASSERT(node->isAttributeNode()); - - // In XPath land, namespace nodes are not accessible on the attribute axis. - if (node->namespaceURI() == XMLNSNames::xmlnsNamespaceURI) - return false; + case Step::NodeTest::TextNodeTest: { + Node::NodeType type = node->nodeType(); + return type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE; + } + case Step::NodeTest::CommentNodeTest: + return node->nodeType() == Node::COMMENT_NODE; + case Step::NodeTest::ProcessingInstructionNodeTest: { + const AtomicString& name = nodeTest.data(); + return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name); + } + case Step::NodeTest::AnyNodeTest: + return true; + case Step::NodeTest::NameTest: { + const AtomicString& name = nodeTest.data(); + const AtomicString& namespaceURI = nodeTest.namespaceURI(); + + if (axis == Step::AttributeAxis) { + ASSERT(node->isAttributeNode()); + + // In XPath land, namespace nodes are not accessible on the + // attribute axis. + if (node->namespaceURI() == XMLNSNames::xmlnsNamespaceURI) + return false; - if (name == starAtom) - return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI; + if (name == starAtom) + return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI; - return node->localName() == name && node->namespaceURI() == namespaceURI; - } + return node->localName() == name && node->namespaceURI() == namespaceURI; + } - // Node test on the namespace axis is not implemented yet, the caller has a check for it. - ASSERT(axis != Step::NamespaceAxis); + // Node test on the namespace axis is not implemented yet, the caller + // has a check for it. + ASSERT(axis != Step::NamespaceAxis); - // For other axes, the principal node type is element. - ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE); - if (node->nodeType() != Node::ELEMENT_NODE) - return false; + // For other axes, the principal node type is element. + ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE); + if (!node->isElementNode()) + return false; + Element& element = toElement(*node); - if (name == starAtom) - return namespaceURI.isEmpty() || namespaceURI == node->namespaceURI(); + if (name == starAtom) + return namespaceURI.isEmpty() || namespaceURI == element.namespaceURI(); - if (node->document().isHTMLDocument()) { - if (node->isHTMLElement()) { - // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace. Names are compared case-insensitively. - return equalIgnoringCase(toElement(node)->localName(), name) && (namespaceURI.isNull() || namespaceURI == node->namespaceURI()); - } - // An expression without any prefix shouldn't match no-namespace nodes (because HTML5 says so). - return toElement(node)->hasLocalName(name) && namespaceURI == node->namespaceURI() && !namespaceURI.isNull(); + if (element.document().isHTMLDocument()) { + if (element.isHTMLElement()) { + // Paths without namespaces should match HTML elements in HTML + // documents despite those having an XHTML namespace. Names are + // compared case-insensitively. + return equalIgnoringCase(element.localName(), name) && (namespaceURI.isNull() || namespaceURI == element.namespaceURI()); } - return toElement(node)->hasLocalName(name) && namespaceURI == node->namespaceURI(); + // An expression without any prefix shouldn't match no-namespace + // nodes (because HTML5 says so). + return element.hasLocalName(name) && namespaceURI == element.namespaceURI() && !namespaceURI.isNull(); } + return element.hasLocalName(name) && namespaceURI == element.namespaceURI(); + } } ASSERT_NOT_REACHED(); return false; @@ -224,12 +242,13 @@ static inline bool nodeMatches(Node* node, Step::Axis axis, const Step::NodeTest // Only the first merged predicate may depend on position. ++evaluationContext.position; - const Vector<OwnPtr<Predicate> >& mergedPredicates = nodeTest.mergedPredicates(); + const WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& mergedPredicates = nodeTest.mergedPredicates(); for (unsigned i = 0; i < mergedPredicates.size(); i++) { Predicate* predicate = mergedPredicates[i].get(); evaluationContext.node = node; - // No need to set context size - we only get here when evaluating predicates that do not depend on it. + // No need to set context size - we only get here when evaluating + // predicates that do not depend on it. if (!predicate->evaluate()) return false; } @@ -237,167 +256,192 @@ static inline bool nodeMatches(Node* node, Step::Axis axis, const Step::NodeTest return true; } -// Result nodes are ordered in axis order. Node test (including merged predicates) is applied. +// Result nodes are ordered in axis order. Node test (including merged +// predicates) is applied. void Step::nodesInAxis(Node* context, NodeSet& nodes) const { ASSERT(nodes.isEmpty()); switch (m_axis) { - case ChildAxis: - if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children. - return; - - for (Node* n = context->firstChild(); n; n = n->nextSibling()) - if (nodeMatches(n, ChildAxis, m_nodeTest)) - nodes.append(n); + case ChildAxis: + // In XPath model, attribute nodes do not have children. + if (context->isAttributeNode()) return; - case DescendantAxis: - if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children. - return; - for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) - if (nodeMatches(n, DescendantAxis, m_nodeTest)) - nodes.append(n); - return; - case ParentAxis: - if (context->isAttributeNode()) { - Element* n = toAttr(context)->ownerElement(); - if (nodeMatches(n, ParentAxis, m_nodeTest)) - nodes.append(n); - } else { - ContainerNode* n = context->parentNode(); - if (n && nodeMatches(n, ParentAxis, m_nodeTest)) - nodes.append(n); - } - return; - case AncestorAxis: { - Node* n = context; - if (context->isAttributeNode()) { - n = toAttr(context)->ownerElement(); - if (nodeMatches(n, AncestorAxis, m_nodeTest)) - nodes.append(n); - } - for (n = n->parentNode(); n; n = n->parentNode()) - if (nodeMatches(n, AncestorAxis, m_nodeTest)) - nodes.append(n); - nodes.markSorted(false); + for (Node* n = context->firstChild(); n; n = n->nextSibling()) { + if (nodeMatches(n, ChildAxis, nodeTest())) + nodes.append(n); + } + return; + + case DescendantAxis: + // In XPath model, attribute nodes do not have children. + if (context->isAttributeNode()) return; + + for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) { + if (nodeMatches(n, DescendantAxis, nodeTest())) + nodes.append(n); } - case FollowingSiblingAxis: - if (context->nodeType() == Node::ATTRIBUTE_NODE || - context->nodeType() == Node::XPATH_NAMESPACE_NODE) - return; + return; - for (Node* n = context->nextSibling(); n; n = n->nextSibling()) - if (nodeMatches(n, FollowingSiblingAxis, m_nodeTest)) - nodes.append(n); + case ParentAxis: + if (context->isAttributeNode()) { + Element* n = toAttr(context)->ownerElement(); + if (nodeMatches(n, ParentAxis, nodeTest())) + nodes.append(n); + } else { + ContainerNode* n = context->parentNode(); + if (n && nodeMatches(n, ParentAxis, nodeTest())) + nodes.append(n); + } + return; + + case AncestorAxis: { + Node* n = context; + if (context->isAttributeNode()) { + n = toAttr(context)->ownerElement(); + if (nodeMatches(n, AncestorAxis, nodeTest())) + nodes.append(n); + } + for (n = n->parentNode(); n; n = n->parentNode()) { + if (nodeMatches(n, AncestorAxis, nodeTest())) + nodes.append(n); + } + nodes.markSorted(false); + return; + } + + case FollowingSiblingAxis: + if (context->nodeType() == Node::ATTRIBUTE_NODE) return; - case PrecedingSiblingAxis: - if (context->nodeType() == Node::ATTRIBUTE_NODE || - context->nodeType() == Node::XPATH_NAMESPACE_NODE) - return; - for (Node* n = context->previousSibling(); n; n = n->previousSibling()) - if (nodeMatches(n, PrecedingSiblingAxis, m_nodeTest)) - nodes.append(n); + for (Node* n = context->nextSibling(); n; n = n->nextSibling()) { + if (nodeMatches(n, FollowingSiblingAxis, nodeTest())) + nodes.append(n); + } + return; - nodes.markSorted(false); + case PrecedingSiblingAxis: + if (context->nodeType() == Node::ATTRIBUTE_NODE) return; - case FollowingAxis: - if (context->isAttributeNode()) { - Node* p = toAttr(context)->ownerElement(); - while ((p = NodeTraversal::next(*p))) { - if (nodeMatches(p, FollowingAxis, m_nodeTest)) - nodes.append(p); - } - } else { - for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) { - for (Node* n = p->nextSibling(); n; n = n->nextSibling()) { - if (nodeMatches(n, FollowingAxis, m_nodeTest)) - nodes.append(n); - for (Node* c = n->firstChild(); c; c = NodeTraversal::next(*c, n)) - if (nodeMatches(c, FollowingAxis, m_nodeTest)) - nodes.append(c); - } - } + + for (Node* n = context->previousSibling(); n; n = n->previousSibling()) { + if (nodeMatches(n, PrecedingSiblingAxis, nodeTest())) + nodes.append(n); + } + nodes.markSorted(false); + return; + + case FollowingAxis: + if (context->isAttributeNode()) { + Node* p = toAttr(context)->ownerElement(); + while ((p = NodeTraversal::next(*p))) { + if (nodeMatches(p, FollowingAxis, nodeTest())) + nodes.append(p); } - return; - case PrecedingAxis: { - if (context->isAttributeNode()) - context = toAttr(context)->ownerElement(); - - Node* n = context; - while (ContainerNode* parent = n->parentNode()) { - for (n = NodeTraversal::previous(*n); n != parent; n = NodeTraversal::previous(*n)) - if (nodeMatches(n, PrecedingAxis, m_nodeTest)) + } else { + for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) { + for (Node* n = p->nextSibling(); n; n = n->nextSibling()) { + if (nodeMatches(n, FollowingAxis, nodeTest())) nodes.append(n); - n = parent; - } - nodes.markSorted(false); - return; - } - case AttributeAxis: { - if (!context->isElementNode()) - return; - - Element* contextElement = toElement(context); - - // Avoid lazily creating attribute nodes for attributes that we do not need anyway. - if (m_nodeTest.kind() == NodeTest::NameTest && m_nodeTest.data() != starAtom) { - RefPtr<Node> n = contextElement->getAttributeNodeNS(m_nodeTest.namespaceURI(), m_nodeTest.data()); - if (n && n->namespaceURI() != XMLNSNames::xmlnsNamespaceURI) { // In XPath land, namespace nodes are not accessible on the attribute axis. - if (nodeMatches(n.get(), AttributeAxis, m_nodeTest)) // Still need to check merged predicates. - nodes.append(n.release()); + for (Node* c = n->firstChild(); c; c = NodeTraversal::next(*c, n)) { + if (nodeMatches(c, FollowingAxis, nodeTest())) + nodes.append(c); + } } - return; } + } + return; - if (!contextElement->hasAttributes()) - return; + case PrecedingAxis: { + if (context->isAttributeNode()) + context = toAttr(context)->ownerElement(); - for (unsigned i = 0; i < contextElement->attributeCount(); ++i) { - RefPtr<Attr> attr = contextElement->ensureAttr(contextElement->attributeItem(i)->name()); - if (nodeMatches(attr.get(), AttributeAxis, m_nodeTest)) - nodes.append(attr.release()); + Node* n = context; + while (ContainerNode* parent = n->parentNode()) { + for (n = NodeTraversal::previous(*n); n != parent; n = NodeTraversal::previous(*n)) { + if (nodeMatches(n, PrecedingAxis, nodeTest())) + nodes.append(n); } - return; + n = parent; } - case NamespaceAxis: - // XPath namespace nodes are not implemented yet. + nodes.markSorted(false); + return; + } + + case AttributeAxis: { + if (!context->isElementNode()) return; - case SelfAxis: - if (nodeMatches(context, SelfAxis, m_nodeTest)) - nodes.append(context); + + Element* contextElement = toElement(context); + // Avoid lazily creating attribute nodes for attributes that we do not + // need anyway. + if (nodeTest().kind() == NodeTest::NameTest && nodeTest().data() != starAtom) { + RefPtrWillBeRawPtr<Node> n = contextElement->getAttributeNodeNS(nodeTest().namespaceURI(), nodeTest().data()); + // In XPath land, namespace nodes are not accessible on the attribute axis. + if (n && n->namespaceURI() != XMLNSNames::xmlnsNamespaceURI) { + // Still need to check merged predicates. + if (nodeMatches(n.get(), AttributeAxis, nodeTest())) + nodes.append(n.release()); + } return; - case DescendantOrSelfAxis: - if (nodeMatches(context, DescendantOrSelfAxis, m_nodeTest)) - nodes.append(context); - if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children. - return; - - for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) - if (nodeMatches(n, DescendantOrSelfAxis, m_nodeTest)) - nodes.append(n); + } + + if (!contextElement->hasAttributes()) return; - case AncestorOrSelfAxis: { - if (nodeMatches(context, AncestorOrSelfAxis, m_nodeTest)) - nodes.append(context); - Node* n = context; - if (context->isAttributeNode()) { - n = toAttr(context)->ownerElement(); - if (nodeMatches(n, AncestorOrSelfAxis, m_nodeTest)) - nodes.append(n); - } - for (n = n->parentNode(); n; n = n->parentNode()) - if (nodeMatches(n, AncestorOrSelfAxis, m_nodeTest)) - nodes.append(n); - nodes.markSorted(false); + AttributeCollection attributes = contextElement->attributes(); + AttributeCollection::const_iterator end = attributes.end(); + for (AttributeCollection::const_iterator it = attributes.begin(); it != end; ++it) { + RefPtrWillBeRawPtr<Attr> attr = contextElement->ensureAttr(it->name()); + if (nodeMatches(attr.get(), AttributeAxis, nodeTest())) + nodes.append(attr.release()); + } + return; + } + + case NamespaceAxis: + // XPath namespace nodes are not implemented. + return; + + case SelfAxis: + if (nodeMatches(context, SelfAxis, nodeTest())) + nodes.append(context); + return; + + case DescendantOrSelfAxis: + if (nodeMatches(context, DescendantOrSelfAxis, nodeTest())) + nodes.append(context); + // In XPath model, attribute nodes do not have children. + if (context->isAttributeNode()) return; + + for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) { + if (nodeMatches(n, DescendantOrSelfAxis, nodeTest())) + nodes.append(n); + } + return; + + case AncestorOrSelfAxis: { + if (nodeMatches(context, AncestorOrSelfAxis, nodeTest())) + nodes.append(context); + Node* n = context; + if (context->isAttributeNode()) { + n = toAttr(context)->ownerElement(); + if (nodeMatches(n, AncestorOrSelfAxis, nodeTest())) + nodes.append(n); } + for (n = n->parentNode(); n; n = n->parentNode()) { + if (nodeMatches(n, AncestorOrSelfAxis, nodeTest())) + nodes.append(n); + } + nodes.markSorted(false); + return; + } } ASSERT_NOT_REACHED(); } - } + } |