src/third_party/WebKit/Source/core/xml/XPathStep.cpp

   1 /*
   2  * Copyright (C) 2005 Frerich Raabe <raabe@kde.org>
   3  * Copyright (C) 2006, 2009 Apple Inc. All rights reserved.
   4  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  17  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  18  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  19  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  20  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  21  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  22  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  23  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  25  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26  */
  27
  28 #include "config.h"
  29 #include "core/xml/XPathStep.h"
  30
  31 #include "core/XMLNSNames.h"
  32 #include "core/dom/Attr.h"
  33 #include "core/dom/Document.h"
  34 #include "core/dom/Element.h"
  35 #include "core/dom/NodeTraversal.h"
  36 #include "core/xml/XPathParser.h"
  37 #include "core/xml/XPathUtil.h"
  38
  39 namespace blink {
  40 namespace XPath {
  41
  42 Step::Step(Axis axis, const NodeTest& nodeTest)
  43     : m_axis(axis)
  44     , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
  45 {
  46 }
  47
  48 Step::Step(Axis axis, const NodeTest& nodeTest, WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& predicates)
  49     : m_axis(axis)
  50     , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest)))
  51 {
  52     m_predicates.swap(predicates);
  53 }
  54
  55 Step::~Step()
  56 {
  57 }
  58
  59 void Step::trace(Visitor* visitor)
  60 {
  61     visitor->trace(m_nodeTest);
  62     visitor->trace(m_predicates);
  63     ParseNode::trace(visitor);
  64 }
  65
  66 void Step::optimize()
  67 {
  68     // Evaluate predicates as part of node test if possible to avoid building
  69     // unnecessary NodeSets.
  70     // E.g., there is no need to build a set of all "foo" nodes to evaluate
  71     // "foo[@bar]", we can check the predicate while enumerating.
  72     // This optimization can be applied to predicates that are not context node
  73     // list sensitive, or to first predicate that is only context position
  74     // sensitive, e.g. foo[position() mod 2 = 0].
  75     WillBeHeapVector<OwnPtrWillBeMember<Predicate> > remainingPredicates;
  76     for (size_t i = 0; i < m_predicates.size(); ++i) {
  77         OwnPtrWillBeRawPtr<Predicate> predicate(m_predicates[i].release());
  78         if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) {
  79             nodeTest().mergedPredicates().append(predicate.release());
  80         } else {
  81             remainingPredicates.append(predicate.release());
  82         }
  83     }
  84     swap(remainingPredicates, m_predicates);
  85 }
  86
  87 void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep)
  88 {
  89     dropSecondStep = false;
  90
  91     if (first->m_axis == Step::DescendantOrSelfAxis
  92         && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
  93         && !first->m_predicates.size()
  94         && !first->nodeTest().mergedPredicates().size()) {
  95
  96         ASSERT(first->nodeTest().data().isEmpty());
  97         ASSERT(first->nodeTest().namespaceURI().isEmpty());
  98
  99         // Optimize the common case of "//" AKA
 100         // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest.
 101         if (second->m_axis == Step::ChildAxis && second->predicatesAreContextListInsensitive()) {
 102             first->m_axis = Step::DescendantAxis;
 103             first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second->nodeTest().data(), second->nodeTest().namespaceURI());
 104             swap(second->nodeTest().mergedPredicates(), first->nodeTest().mergedPredicates());
 105             swap(second->m_predicates, first->m_predicates);
 106             first->optimize();
 107             dropSecondStep = true;
 108         }
 109     }
 110 }
 111
 112 bool Step::predicatesAreContextListInsensitive() const
 113 {
 114     for (size_t i = 0; i < m_predicates.size(); ++i) {
 115         Predicate* predicate = m_predicates[i].get();
 116         if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
 117             return false;
 118     }
 119
 120     for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) {
 121         Predicate* predicate = nodeTest().mergedPredicates()[i].get();
 122         if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
 123             return false;
 124     }
 125
 126     return true;
 127 }
 128
 129 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
 130 {
 131     evaluationContext.position = 0;
 132
 133     nodesInAxis(evaluationContext, context, nodes);
 134
 135     // Check predicates that couldn't be merged into node test.
 136     for (unsigned i = 0; i < m_predicates.size(); i++) {
 137         Predicate* predicate = m_predicates[i].get();
 138
 139         OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create());
 140         if (!nodes.isSorted())
 141             newNodes->markSorted(false);
 142
 143         for (unsigned j = 0; j < nodes.size(); j++) {
 144             Node* node = nodes[j];
 145
 146             evaluationContext.node = node;
 147             evaluationContext.size = nodes.size();
 148             evaluationContext.position = j + 1;
 149             if (predicate->evaluate(evaluationContext))
 150                 newNodes->append(node);
 151         }
 152
 153         nodes.swap(*newNodes);
 154     }
 155 }
 156
 157 #if ENABLE(ASSERT)
 158 static inline Node::NodeType primaryNodeType(Step::Axis axis)
 159 {
 160     switch (axis) {
 161     case Step::AttributeAxis:
 162         return Node::ATTRIBUTE_NODE;
 163     default:
 164         return Node::ELEMENT_NODE;
 165     }
 166 }
 167 #endif
 168
 169 // Evaluate NodeTest without considering merged predicates.
 170 static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
 171 {
 172     switch (nodeTest.kind()) {
 173     case Step::NodeTest::TextNodeTest: {
 174         Node::NodeType type = node->nodeType();
 175         return type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE;
 176     }
 177     case Step::NodeTest::CommentNodeTest:
 178         return node->nodeType() == Node::COMMENT_NODE;
 179     case Step::NodeTest::ProcessingInstructionNodeTest: {
 180         const AtomicString& name = nodeTest.data();
 181         return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
 182     }
 183     case Step::NodeTest::AnyNodeTest:
 184         return true;
 185     case Step::NodeTest::NameTest: {
 186         const AtomicString& name = nodeTest.data();
 187         const AtomicString& namespaceURI = nodeTest.namespaceURI();
 188
 189         if (axis == Step::AttributeAxis) {
 190             ASSERT(node->isAttributeNode());
 191
 192             // In XPath land, namespace nodes are not accessible on the
 193             // attribute axis.
 194             if (node->namespaceURI() == XMLNSNames::xmlnsNamespaceURI)
 195                 return false;
 196
 197             if (name == starAtom)
 198                 return namespaceURI.isEmpty() || node->namespaceURI() == namespaceURI;
 199
 200             return node->localName() == name && node->namespaceURI() == namespaceURI;
 201         }
 202
 203         // Node test on the namespace axis is not implemented yet, the caller
 204         // has a check for it.
 205         ASSERT(axis != Step::NamespaceAxis);
 206
 207         // For other axes, the principal node type is element.
 208         ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE);
 209         if (!node->isElementNode())
 210             return false;
 211         Element& element = toElement(*node);
 212
 213         if (name == starAtom)
 214             return namespaceURI.isEmpty() || namespaceURI == element.namespaceURI();
 215
 216         if (element.document().isHTMLDocument()) {
 217             if (element.isHTMLElement()) {
 218                 // Paths without namespaces should match HTML elements in HTML
 219                 // documents despite those having an XHTML namespace. Names are
 220                 // compared case-insensitively.
 221                 return equalIgnoringCase(element.localName(), name) && (namespaceURI.isNull() || namespaceURI == element.namespaceURI());
 222             }
 223             // An expression without any prefix shouldn't match no-namespace
 224             // nodes (because HTML5 says so).
 225             return element.hasLocalName(name) && namespaceURI == element.namespaceURI() && !namespaceURI.isNull();
 226         }
 227         return element.hasLocalName(name) && namespaceURI == element.namespaceURI();
 228     }
 229     }
 230     ASSERT_NOT_REACHED();
 231     return false;
 232 }
 233
 234 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
 235 {
 236     if (!nodeMatchesBasicTest(node, axis, nodeTest))
 237         return false;
 238
 239     // Only the first merged predicate may depend on position.
 240     ++evaluationContext.position;
 241
 242     const WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& mergedPredicates = nodeTest.mergedPredicates();
 243     for (unsigned i = 0; i < mergedPredicates.size(); i++) {
 244         Predicate* predicate = mergedPredicates[i].get();
 245
 246         evaluationContext.node = node;
 247         // No need to set context size - we only get here when evaluating
 248         // predicates that do not depend on it.
 249         if (!predicate->evaluate(evaluationContext))
 250             return false;
 251     }
 252
 253     return true;
 254 }
 255
 256 // Result nodes are ordered in axis order. Node test (including merged
 257 // predicates) is applied.
 258 void Step::nodesInAxis(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
 259 {
 260     ASSERT(nodes.isEmpty());
 261     switch (m_axis) {
 262     case ChildAxis:
 263         // In XPath model, attribute nodes do not have children.
 264         if (context->isAttributeNode())
 265             return;
 266
 267         for (Node* n = context->firstChild(); n; n = n->nextSibling()) {
 268             if (nodeMatches(evaluationContext, n, ChildAxis, nodeTest()))
 269                 nodes.append(n);
 270         }
 271         return;
 272
 273     case DescendantAxis:
 274         // In XPath model, attribute nodes do not have children.
 275         if (context->isAttributeNode())
 276             return;
 277
 278         for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) {
 279             if (nodeMatches(evaluationContext, n, DescendantAxis, nodeTest()))
 280                 nodes.append(n);
 281         }
 282         return;
 283
 284     case ParentAxis:
 285         if (context->isAttributeNode()) {
 286             Element* n = toAttr(context)->ownerElement();
 287             if (nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
 288                 nodes.append(n);
 289         } else {
 290             ContainerNode* n = context->parentNode();
 291             if (n && nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
 292                 nodes.append(n);
 293         }
 294         return;
 295
 296     case AncestorAxis: {
 297         Node* n = context;
 298         if (context->isAttributeNode()) {
 299             n = toAttr(context)->ownerElement();
 300             if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
 301                 nodes.append(n);
 302         }
 303         for (n = n->parentNode(); n; n = n->parentNode()) {
 304             if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
 305                 nodes.append(n);
 306         }
 307         nodes.markSorted(false);
 308         return;
 309     }
 310
 311     case FollowingSiblingAxis:
 312         if (context->nodeType() == Node::ATTRIBUTE_NODE)
 313             return;
 314
 315         for (Node* n = context->nextSibling(); n; n = n->nextSibling()) {
 316             if (nodeMatches(evaluationContext, n, FollowingSiblingAxis, nodeTest()))
 317                 nodes.append(n);
 318         }
 319         return;
 320
 321     case PrecedingSiblingAxis:
 322         if (context->nodeType() == Node::ATTRIBUTE_NODE)
 323             return;
 324
 325         for (Node* n = context->previousSibling(); n; n = n->previousSibling()) {
 326             if (nodeMatches(evaluationContext, n, PrecedingSiblingAxis, nodeTest()))
 327                 nodes.append(n);
 328         }
 329         nodes.markSorted(false);
 330         return;
 331
 332     case FollowingAxis:
 333         if (context->isAttributeNode()) {
 334             for (Node* p = NodeTraversal::next(*toAttr(context)->ownerElement()); p; p = NodeTraversal::next(*p)) {
 335                 if (nodeMatches(evaluationContext, p, FollowingAxis, nodeTest()))
 336                     nodes.append(p);
 337             }
 338         } else {
 339             for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
 340                 for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
 341                     if (nodeMatches(evaluationContext, n, FollowingAxis, nodeTest()))
 342                         nodes.append(n);
 343                     for (Node* c = n->firstChild(); c; c = NodeTraversal::next(*c, n)) {
 344                         if (nodeMatches(evaluationContext, c, FollowingAxis, nodeTest()))
 345                             nodes.append(c);
 346                     }
 347                 }
 348             }
 349         }
 350         return;
 351
 352     case PrecedingAxis: {
 353         if (context->isAttributeNode())
 354             context = toAttr(context)->ownerElement();
 355
 356         Node* n = context;
 357         while (ContainerNode* parent = n->parentNode()) {
 358             for (n = NodeTraversal::previous(*n); n != parent; n = NodeTraversal::previous(*n)) {
 359                 if (nodeMatches(evaluationContext, n, PrecedingAxis, nodeTest()))
 360                     nodes.append(n);
 361             }
 362             n = parent;
 363         }
 364         nodes.markSorted(false);
 365         return;
 366     }
 367
 368     case AttributeAxis: {
 369         if (!context->isElementNode())
 370             return;
 371
 372         Element* contextElement = toElement(context);
 373         // Avoid lazily creating attribute nodes for attributes that we do not
 374         // need anyway.
 375         if (nodeTest().kind() == NodeTest::NameTest && nodeTest().data() != starAtom) {
 376             RefPtrWillBeRawPtr<Node> n = contextElement->getAttributeNodeNS(nodeTest().namespaceURI(), nodeTest().data());
 377             // In XPath land, namespace nodes are not accessible on the attribute axis.
 378             if (n && n->namespaceURI() != XMLNSNames::xmlnsNamespaceURI) {
 379                 // Still need to check merged predicates.
 380                 if (nodeMatches(evaluationContext, n.get(), AttributeAxis, nodeTest()))
 381                     nodes.append(n.release());
 382             }
 383             return;
 384         }
 385
 386         AttributeCollection attributes = contextElement->attributes();
 387         AttributeCollection::iterator end = attributes.end();
 388         for (AttributeCollection::iterator it = attributes.begin(); it != end; ++it) {
 389             RefPtrWillBeRawPtr<Attr> attr = contextElement->ensureAttr(it->name());
 390             if (nodeMatches(evaluationContext, attr.get(), AttributeAxis, nodeTest()))
 391                 nodes.append(attr.release());
 392         }
 393         return;
 394     }
 395
 396     case NamespaceAxis:
 397         // XPath namespace nodes are not implemented.
 398         return;
 399
 400     case SelfAxis:
 401         if (nodeMatches(evaluationContext, context, SelfAxis, nodeTest()))
 402             nodes.append(context);
 403         return;
 404
 405     case DescendantOrSelfAxis:
 406         if (nodeMatches(evaluationContext, context, DescendantOrSelfAxis, nodeTest()))
 407             nodes.append(context);
 408         // In XPath model, attribute nodes do not have children.
 409         if (context->isAttributeNode())
 410             return;
 411
 412         for (Node* n = context->firstChild(); n; n = NodeTraversal::next(*n, context)) {
 413             if (nodeMatches(evaluationContext, n, DescendantOrSelfAxis, nodeTest()))
 414                 nodes.append(n);
 415         }
 416         return;
 417
 418     case AncestorOrSelfAxis: {
 419         if (nodeMatches(evaluationContext, context, AncestorOrSelfAxis, nodeTest()))
 420             nodes.append(context);
 421         Node* n = context;
 422         if (context->isAttributeNode()) {
 423             n = toAttr(context)->ownerElement();
 424             if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
 425                 nodes.append(n);
 426         }
 427         for (n = n->parentNode(); n; n = n->parentNode()) {
 428             if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
 429                 nodes.append(n);
 430         }
 431         nodes.markSorted(false);
 432         return;
 433     }
 434     }
 435     ASSERT_NOT_REACHED();
 436 }
 437
 438 }
 439
 440 }