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