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 "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                 Node* n = static_cast<Attr*>(context)->ownerElement();

   259                 if (nodeMatches(n, ParentAxis, m_nodeTest))

   260                     nodes.append(n);

   261             } else {

   262                 Node* 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 (Node* parent = n->parent()) {

   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)