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(new NodeTest(nodeTest))
  45 {
  46 }
  47
  48 Step::Step(Axis axis, const NodeTest& nodeTest, HeapVector<Member<Predicate>>& predicates)
  49     : m_axis(axis)
  50     , m_nodeTest(new NodeTest(nodeTest))
  51 {
  52     m_predicates.swap(predicates);
  53 }
  54
  55 Step::~Step()
  56 {
  57 }
  58
  59 DEFINE_TRACE(Step)
  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     HeapVector<Member<Predicate>> remainingPredicates;
  76     for (size_t i = 0; i < m_predicates.size(); ++i) {
  77         Predicate* predicate = m_predicates[i];
  78         if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredicates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates.isEmpty()) {
  79             nodeTest().mergedPredicates().append(predicate);
  80         } else {
  81             remainingPredicates.append(predicate);
  82         }
  83     }
  84     swap(remainingPredicates, m_predicates);
  85 }
  86
  87 bool optimizeStepPair(Step* first, Step* second)
  88 {
  89     if (first->m_axis == Step::DescendantOrSelfAxis
  90         && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
  91         && !first->m_predicates.size()
  92         && !first->nodeTest().mergedPredicates().size()) {
  93
  94         ASSERT(first->nodeTest().data().isEmpty());
  95         ASSERT(first->nodeTest().namespaceURI().isEmpty());
  96
  97         // Optimize the common case of "//" AKA
  98         // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest.
  99         if (second->m_axis == Step::ChildAxis && second->predicatesAreContextListInsensitive()) {
 100             first->m_axis = Step::DescendantAxis;
 101             first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second->nodeTest().data(), second->nodeTest().namespaceURI());
 102             swap(second->nodeTest().mergedPredicates(), first->nodeTest().mergedPredicates());
 103             swap(second->m_predicates, first->m_predicates);
 104             first->optimize();
 105             return true;
 106         }
 107     }
 108     return false;
 109 }
 110
 111 bool Step::predicatesAreContextListInsensitive() const
 112 {
 113     for (size_t i = 0; i < m_predicates.size(); ++i) {
 114         Predicate* predicate = m_predicates[i].get();
 115         if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
 116             return false;
 117     }
 118
 119     for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) {
 120         Predicate* predicate = nodeTest().mergedPredicates()[i].get();
 121         if (predicate->isContextPositionSensitive() || predicate->isContextSizeSensitive())
 122             return false;
 123     }
 124
 125     return true;
 126 }
 127
 128 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
 129 {
 130     evaluationContext.position = 0;
 131
 132     nodesInAxis(evaluationContext, context, nodes);
 133
 134     // Check predicates that couldn't be merged into node test.
 135     for (unsigned i = 0; i < m_predicates.size(); i++) {
 136         Predicate* predicate = m_predicates[i].get();
 137
 138         NodeSet* newNodes = NodeSet::create();
 139         if (!nodes.isSorted())
 140             newNodes->markSorted(false);
 141
 142         for (unsigned j = 0; j < nodes.size(); j++) {
 143             Node* node = nodes[j];
 144
 145             evaluationContext.node = node;
 146             evaluationContext.size = nodes.size();
 147             evaluationContext.position = j + 1;
 148             if (predicate->evaluate(evaluationContext))
 149                 newNodes->append(node);
 150         }
 151
 152         nodes.swap(*newNodes);
 153     }
 154 }
 155
 156 #if ENABLE(ASSERT)
 157 static inline Node::NodeType primaryNodeType(Step::Axis axis)
 158 {
 159     switch (axis) {
 160     case Step::AttributeAxis:
 161         return Node::ATTRIBUTE_NODE;
 162     default:
 163         return Node::ELEMENT_NODE;
 164     }
 165 }
 166 #endif
 167
 168 // Evaluate NodeTest without considering merged predicates.
 169 static inline bool nodeMatchesBasicTest(Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
 170 {
 171     switch (nodeTest.kind()) {
 172     case Step::NodeTest::TextNodeTest: {
 173         Node::NodeType type = node->nodeType();
 174         return type == Node::TEXT_NODE || type == Node::CDATA_SECTION_NODE;
 175     }
 176     case Step::NodeTest::CommentNodeTest:
 177         return node->nodeType() == Node::COMMENT_NODE;
 178     case Step::NodeTest::ProcessingInstructionNodeTest: {
 179         const AtomicString& name = nodeTest.data();
 180         return node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name);
 181     }
 182     case Step::NodeTest::AnyNodeTest:
 183         return true;
 184     case Step::NodeTest::NameTest: {
 185         const AtomicString& name = nodeTest.data();
 186         const AtomicString& namespaceURI = nodeTest.namespaceURI();
 187
 188         if (axis == Step::AttributeAxis) {
 189             Attr* attr = toAttr(node);
 190
 191             // In XPath land, namespace nodes are not accessible on the
 192             // attribute axis.
 193             if (attr->namespaceURI() == XMLNSNames::xmlnsNamespaceURI)
 194                 return false;
 195
 196             if (name == starAtom)
 197                 return namespaceURI.isEmpty() || attr->namespaceURI() == namespaceURI;
 198
 199             return attr->localName() == name && attr->namespaceURI() == namespaceURI;
 200         }
 201
 202         // Node test on the namespace axis is not implemented yet, the caller
 203         // has a check for it.
 204         ASSERT(axis != Step::NamespaceAxis);
 205
 206         // For other axes, the principal node type is element.
 207         ASSERT(primaryNodeType(axis) == Node::ELEMENT_NODE);
 208         if (!node->isElementNode())
 209             return false;
 210         Element& element = toElement(*node);
 211
 212         if (name == starAtom)
 213             return namespaceURI.isEmpty() || namespaceURI == element.namespaceURI();
 214
 215         if (element.document().isHTMLDocument()) {
 216             if (element.isHTMLElement()) {
 217                 // Paths without namespaces should match HTML elements in HTML
 218                 // documents despite those having an XHTML namespace. Names are
 219                 // compared case-insensitively.
 220                 return equalIgnoringCase(element.localName(), name) && (namespaceURI.isNull() || namespaceURI == element.namespaceURI());
 221             }
 222             // An expression without any prefix shouldn't match no-namespace
 223             // nodes (because HTML5 says so).
 224             return element.hasLocalName(name) && namespaceURI == element.namespaceURI() && !namespaceURI.isNull();
 225         }
 226         return element.hasLocalName(name) && namespaceURI == element.namespaceURI();
 227     }
 228     }
 229     ASSERT_NOT_REACHED();
 230     return false;
 231 }
 232
 233 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node, Step::Axis axis, const Step::NodeTest& nodeTest)
 234 {
 235     if (!nodeMatchesBasicTest(node, axis, nodeTest))
 236         return false;
 237
 238     // Only the first merged predicate may depend on position.
 239     ++evaluationContext.position;
 240
 241     const HeapVector<Member<Predicate>>& mergedPredicates = nodeTest.mergedPredicates();
 242     for (unsigned i = 0; i < mergedPredicates.size(); i++) {
 243         Predicate* predicate = mergedPredicates[i].get();
 244
 245         evaluationContext.node = node;
 246         // No need to set context size - we only get here when evaluating
 247         // predicates that do not depend on it.
 248         if (!predicate->evaluate(evaluationContext))
 249             return false;
 250     }
 251
 252     return true;
 253 }
 254
 255 // Result nodes are ordered in axis order. Node test (including merged
 256 // predicates) is applied.
 257 void Step::nodesInAxis(EvaluationContext& evaluationContext, Node* context, NodeSet& nodes) const
 258 {
 259     ASSERT(nodes.isEmpty());
 260     switch (m_axis) {
 261     case ChildAxis:
 262         // In XPath model, attribute nodes do not have children.
 263         if (context->isAttributeNode())
 264             return;
 265
 266         for (Node* n = context->firstChild(); n; n = n->nextSibling()) {
 267             if (nodeMatches(evaluationContext, n, ChildAxis, nodeTest()))
 268                 nodes.append(n);
 269         }
 270         return;
 271
 272     case DescendantAxis:
 273         // In XPath model, attribute nodes do not have children.
 274         if (context->isAttributeNode())
 275             return;
 276
 277         for (Node& n : NodeTraversal::descendantsOf(*context)) {
 278             if (nodeMatches(evaluationContext, &n, DescendantAxis, nodeTest()))
 279                 nodes.append(&n);
 280         }
 281         return;
 282
 283     case ParentAxis:
 284         if (context->isAttributeNode()) {
 285             Element* n = toAttr(context)->ownerElement();
 286             if (nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
 287                 nodes.append(n);
 288         } else {
 289             ContainerNode* n = context->parentNode();
 290             if (n && nodeMatches(evaluationContext, n, ParentAxis, nodeTest()))
 291                 nodes.append(n);
 292         }
 293         return;
 294
 295     case AncestorAxis: {
 296         Node* n = context;
 297         if (context->isAttributeNode()) {
 298             n = toAttr(context)->ownerElement();
 299             if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
 300                 nodes.append(n);
 301         }
 302         for (n = n->parentNode(); n; n = n->parentNode()) {
 303             if (nodeMatches(evaluationContext, n, AncestorAxis, nodeTest()))
 304                 nodes.append(n);
 305         }
 306         nodes.markSorted(false);
 307         return;
 308     }
 309
 310     case FollowingSiblingAxis:
 311         if (context->nodeType() == Node::ATTRIBUTE_NODE)
 312             return;
 313
 314         for (Node* n = context->nextSibling(); n; n = n->nextSibling()) {
 315             if (nodeMatches(evaluationContext, n, FollowingSiblingAxis, nodeTest()))
 316                 nodes.append(n);
 317         }
 318         return;
 319
 320     case PrecedingSiblingAxis:
 321         if (context->nodeType() == Node::ATTRIBUTE_NODE)
 322             return;
 323
 324         for (Node* n = context->previousSibling(); n; n = n->previousSibling()) {
 325             if (nodeMatches(evaluationContext, n, PrecedingSiblingAxis, nodeTest()))
 326                 nodes.append(n);
 327         }
 328         nodes.markSorted(false);
 329         return;
 330
 331     case FollowingAxis:
 332         if (context->isAttributeNode()) {
 333             for (Node& p : NodeTraversal::startsAfter(*toAttr(context)->ownerElement())) {
 334                 if (nodeMatches(evaluationContext, &p, FollowingAxis, nodeTest()))
 335                     nodes.append(&p);
 336             }
 337         } else {
 338             for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
 339                 for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
 340                     if (nodeMatches(evaluationContext, n, FollowingAxis, nodeTest()))
 341                         nodes.append(n);
 342                     for (Node& c : NodeTraversal::descendantsOf(*n)) {
 343                         if (nodeMatches(evaluationContext, &c, FollowingAxis, nodeTest()))
 344                             nodes.append(&c);
 345                     }
 346                 }
 347             }
 348         }
 349         return;
 350
 351     case PrecedingAxis: {
 352         if (context->isAttributeNode())
 353             context = toAttr(context)->ownerElement();
 354
 355         Node* n = context;
 356         while (ContainerNode* parent = n->parentNode()) {
 357             for (n = NodeTraversal::previous(*n); n != parent; n = NodeTraversal::previous(*n)) {
 358                 if (nodeMatches(evaluationContext, n, PrecedingAxis, nodeTest()))
 359                     nodes.append(n);
 360             }
 361             n = parent;
 362         }
 363         nodes.markSorted(false);
 364         return;
 365     }
 366
 367     case AttributeAxis: {
 368         if (!context->isElementNode())
 369             return;
 370
 371         Element* contextElement = toElement(context);
 372         // Avoid lazily creating attribute nodes for attributes that we do not
 373         // need anyway.
 374         if (nodeTest().kind() == NodeTest::NameTest && nodeTest().data() != starAtom) {
 375             RefPtrWillBeRawPtr<Attr> attr = contextElement->getAttributeNodeNS(nodeTest().namespaceURI(), nodeTest().data());
 376             // In XPath land, namespace nodes are not accessible on the attribute axis.
 377             if (attr && attr->namespaceURI() != XMLNSNames::xmlnsNamespaceURI) {
 378                 // Still need to check merged predicates.
 379                 if (nodeMatches(evaluationContext, attr.get(), AttributeAxis, nodeTest()))
 380                     nodes.append(attr.release());
 381             }
 382             return;
 383         }
 384
 385         AttributeCollection attributes = contextElement->attributes();
 386         for (auto& attribute : attributes) {
 387             RefPtrWillBeRawPtr<Attr> attr = contextElement->ensureAttr(attribute.name());
 388             if (nodeMatches(evaluationContext, attr.get(), AttributeAxis, nodeTest()))
 389                 nodes.append(attr.release());
 390         }
 391         return;
 392     }
 393
 394     case NamespaceAxis:
 395         // XPath namespace nodes are not implemented.
 396         return;
 397
 398     case SelfAxis:
 399         if (nodeMatches(evaluationContext, context, SelfAxis, nodeTest()))
 400             nodes.append(context);
 401         return;
 402
 403     case DescendantOrSelfAxis:
 404         if (nodeMatches(evaluationContext, context, DescendantOrSelfAxis, nodeTest()))
 405             nodes.append(context);
 406         // In XPath model, attribute nodes do not have children.
 407         if (context->isAttributeNode())
 408             return;
 409
 410         for (Node& n : NodeTraversal::descendantsOf(*context)) {
 411             if (nodeMatches(evaluationContext, &n, DescendantOrSelfAxis, nodeTest()))
 412                 nodes.append(&n);
 413         }
 414         return;
 415
 416     case AncestorOrSelfAxis: {
 417         if (nodeMatches(evaluationContext, context, AncestorOrSelfAxis, nodeTest()))
 418             nodes.append(context);
 419         Node* n = context;
 420         if (context->isAttributeNode()) {
 421             n = toAttr(context)->ownerElement();
 422             if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
 423                 nodes.append(n);
 424         }
 425         for (n = n->parentNode(); n; n = n->parentNode()) {
 426             if (nodeMatches(evaluationContext, n, AncestorOrSelfAxis, nodeTest()))
 427                 nodes.append(n);
 428         }
 429         nodes.markSorted(false);
 430         return;
 431     }
 432     }
 433     ASSERT_NOT_REACHED();
 434 }
 435
 436 }
 437
 438 }