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