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 39namespace blink { 40namespace XPath { 41 42Step::Step(Axis axis, const NodeTest& nodeTest) 43 : m_axis(axis) 44 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest))) 45{ 46} 47 48Step::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 55Step::~Step() 56{ 57} 58 59void Step::trace(Visitor* visitor) 60{ 61 visitor->trace(m_nodeTest); 62 visitor->trace(m_predicates); 63 ParseNode::trace(visitor); 64} 65 66void 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 87void 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 112bool 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 129void 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) 158static 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. 170static 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 234static 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. 258void 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} 441