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