| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org> | 2 * Copyright (C) 2005 Frerich Raabe <raabe@kde.org> |
| 3 * Copyright (C) 2006, 2009 Apple Inc. All rights reserved. | 3 * Copyright (C) 2006, 2009 Apple Inc. All rights reserved. |
| 4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> | 4 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org> |
| 5 * | 5 * |
| 6 * Redistribution and use in source and binary forms, with or without | 6 * Redistribution and use in source and binary forms, with or without |
| 7 * modification, are permitted provided that the following conditions | 7 * modification, are permitted provided that the following conditions |
| 8 * are met: | 8 * are met: |
| 9 * | 9 * |
| 10 * 1. Redistributions of source code must retain the above copyright | 10 * 1. Redistributions of source code must retain the above copyright |
| (...skipping 23 matching lines...) Expand all Loading... |
| 34 #include "core/dom/Element.h" | 34 #include "core/dom/Element.h" |
| 35 #include "core/dom/NodeTraversal.h" | 35 #include "core/dom/NodeTraversal.h" |
| 36 #include "core/xml/XPathParser.h" | 36 #include "core/xml/XPathParser.h" |
| 37 #include "core/xml/XPathUtil.h" | 37 #include "core/xml/XPathUtil.h" |
| 38 | 38 |
| 39 namespace blink { | 39 namespace blink { |
| 40 namespace XPath { | 40 namespace XPath { |
| 41 | 41 |
| 42 Step::Step(Axis axis, const NodeTest& nodeTest) | 42 Step::Step(Axis axis, const NodeTest& nodeTest) |
| 43 : m_axis(axis) | 43 : m_axis(axis) |
| 44 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest))) | 44 , m_nodeTest(new NodeTest(nodeTest)) |
| 45 { | 45 { |
| 46 } | 46 } |
| 47 | 47 |
| 48 Step::Step(Axis axis, const NodeTest& nodeTest, WillBeHeapVector<OwnPtrWillBeMem
ber<Predicate> >& predicates) | 48 Step::Step(Axis axis, const NodeTest& nodeTest, HeapVector<Member<Predicate> >&
predicates) |
| 49 : m_axis(axis) | 49 : m_axis(axis) |
| 50 , m_nodeTest(adoptPtrWillBeNoop(new NodeTest(nodeTest))) | 50 , m_nodeTest(new NodeTest(nodeTest)) |
| 51 { | 51 { |
| 52 m_predicates.swap(predicates); | 52 m_predicates.swap(predicates); |
| 53 } | 53 } |
| 54 | 54 |
| 55 Step::~Step() | 55 Step::~Step() |
| 56 { | 56 { |
| 57 } | 57 } |
| 58 | 58 |
| 59 void Step::trace(Visitor* visitor) | 59 void Step::trace(Visitor* visitor) |
| 60 { | 60 { |
| 61 visitor->trace(m_nodeTest); | 61 visitor->trace(m_nodeTest); |
| 62 visitor->trace(m_predicates); | 62 visitor->trace(m_predicates); |
| 63 ParseNode::trace(visitor); | 63 ParseNode::trace(visitor); |
| 64 } | 64 } |
| 65 | 65 |
| 66 void Step::optimize() | 66 void Step::optimize() |
| 67 { | 67 { |
| 68 // Evaluate predicates as part of node test if possible to avoid building | 68 // Evaluate predicates as part of node test if possible to avoid building |
| 69 // unnecessary NodeSets. | 69 // unnecessary NodeSets. |
| 70 // E.g., there is no need to build a set of all "foo" nodes to evaluate | 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. | 71 // "foo[@bar]", we can check the predicate while enumerating. |
| 72 // This optimization can be applied to predicates that are not context node | 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 | 73 // list sensitive, or to first predicate that is only context position |
| 74 // sensitive, e.g. foo[position() mod 2 = 0]. | 74 // sensitive, e.g. foo[position() mod 2 = 0]. |
| 75 WillBeHeapVector<OwnPtrWillBeMember<Predicate> > remainingPredicates; | 75 HeapVector<Member<Predicate> > remainingPredicates; |
| 76 for (size_t i = 0; i < m_predicates.size(); ++i) { | 76 for (size_t i = 0; i < m_predicates.size(); ++i) { |
| 77 OwnPtrWillBeRawPtr<Predicate> predicate(m_predicates[i].release()); | 77 Predicate* predicate = m_predicates[i]; |
| 78 if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredic
ates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates
.isEmpty()) { | 78 if ((!predicate->isContextPositionSensitive() || nodeTest().mergedPredic
ates().isEmpty()) && !predicate->isContextSizeSensitive() && remainingPredicates
.isEmpty()) { |
| 79 nodeTest().mergedPredicates().append(predicate.release()); | 79 nodeTest().mergedPredicates().append(predicate); |
| 80 } else { | 80 } else { |
| 81 remainingPredicates.append(predicate.release()); | 81 remainingPredicates.append(predicate); |
| 82 } | 82 } |
| 83 } | 83 } |
| 84 swap(remainingPredicates, m_predicates); | 84 swap(remainingPredicates, m_predicates); |
| 85 } | 85 } |
| 86 | 86 |
| 87 void optimizeStepPair(Step* first, Step* second, bool& dropSecondStep) | 87 bool optimizeStepPair(Step* first, Step* second) |
| 88 { | 88 { |
| 89 dropSecondStep = false; | |
| 90 | |
| 91 if (first->m_axis == Step::DescendantOrSelfAxis | 89 if (first->m_axis == Step::DescendantOrSelfAxis |
| 92 && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest | 90 && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest |
| 93 && !first->m_predicates.size() | 91 && !first->m_predicates.size() |
| 94 && !first->nodeTest().mergedPredicates().size()) { | 92 && !first->nodeTest().mergedPredicates().size()) { |
| 95 | 93 |
| 96 ASSERT(first->nodeTest().data().isEmpty()); | 94 ASSERT(first->nodeTest().data().isEmpty()); |
| 97 ASSERT(first->nodeTest().namespaceURI().isEmpty()); | 95 ASSERT(first->nodeTest().namespaceURI().isEmpty()); |
| 98 | 96 |
| 99 // Optimize the common case of "//" AKA | 97 // Optimize the common case of "//" AKA |
| 100 // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest. | 98 // /descendant-or-self::node()/child::NodeTest to /descendant::NodeTest. |
| 101 if (second->m_axis == Step::ChildAxis && second->predicatesAreContextLis
tInsensitive()) { | 99 if (second->m_axis == Step::ChildAxis && second->predicatesAreContextLis
tInsensitive()) { |
| 102 first->m_axis = Step::DescendantAxis; | 100 first->m_axis = Step::DescendantAxis; |
| 103 first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second
->nodeTest().data(), second->nodeTest().namespaceURI()); | 101 first->nodeTest() = Step::NodeTest(second->nodeTest().kind(), second
->nodeTest().data(), second->nodeTest().namespaceURI()); |
| 104 swap(second->nodeTest().mergedPredicates(), first->nodeTest().merged
Predicates()); | 102 swap(second->nodeTest().mergedPredicates(), first->nodeTest().merged
Predicates()); |
| 105 swap(second->m_predicates, first->m_predicates); | 103 swap(second->m_predicates, first->m_predicates); |
| 106 first->optimize(); | 104 first->optimize(); |
| 107 dropSecondStep = true; | 105 return true; |
| 108 } | 106 } |
| 109 } | 107 } |
| 108 return false; |
| 110 } | 109 } |
| 111 | 110 |
| 112 bool Step::predicatesAreContextListInsensitive() const | 111 bool Step::predicatesAreContextListInsensitive() const |
| 113 { | 112 { |
| 114 for (size_t i = 0; i < m_predicates.size(); ++i) { | 113 for (size_t i = 0; i < m_predicates.size(); ++i) { |
| 115 Predicate* predicate = m_predicates[i].get(); | 114 Predicate* predicate = m_predicates[i].get(); |
| 116 if (predicate->isContextPositionSensitive() || predicate->isContextSizeS
ensitive()) | 115 if (predicate->isContextPositionSensitive() || predicate->isContextSizeS
ensitive()) |
| 117 return false; | 116 return false; |
| 118 } | 117 } |
| 119 | 118 |
| 120 for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) { | 119 for (size_t i = 0; i < nodeTest().mergedPredicates().size(); ++i) { |
| 121 Predicate* predicate = nodeTest().mergedPredicates()[i].get(); | 120 Predicate* predicate = nodeTest().mergedPredicates()[i].get(); |
| 122 if (predicate->isContextPositionSensitive() || predicate->isContextSizeS
ensitive()) | 121 if (predicate->isContextPositionSensitive() || predicate->isContextSizeS
ensitive()) |
| 123 return false; | 122 return false; |
| 124 } | 123 } |
| 125 | 124 |
| 126 return true; | 125 return true; |
| 127 } | 126 } |
| 128 | 127 |
| 129 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet
& nodes) const | 128 void Step::evaluate(EvaluationContext& evaluationContext, Node* context, NodeSet
& nodes) const |
| 130 { | 129 { |
| 131 evaluationContext.position = 0; | 130 evaluationContext.position = 0; |
| 132 | 131 |
| 133 nodesInAxis(evaluationContext, context, nodes); | 132 nodesInAxis(evaluationContext, context, nodes); |
| 134 | 133 |
| 135 // Check predicates that couldn't be merged into node test. | 134 // Check predicates that couldn't be merged into node test. |
| 136 for (unsigned i = 0; i < m_predicates.size(); i++) { | 135 for (unsigned i = 0; i < m_predicates.size(); i++) { |
| 137 Predicate* predicate = m_predicates[i].get(); | 136 Predicate* predicate = m_predicates[i].get(); |
| 138 | 137 |
| 139 OwnPtrWillBeRawPtr<NodeSet> newNodes(NodeSet::create()); | 138 NodeSet* newNodes = NodeSet::create(); |
| 140 if (!nodes.isSorted()) | 139 if (!nodes.isSorted()) |
| 141 newNodes->markSorted(false); | 140 newNodes->markSorted(false); |
| 142 | 141 |
| 143 for (unsigned j = 0; j < nodes.size(); j++) { | 142 for (unsigned j = 0; j < nodes.size(); j++) { |
| 144 Node* node = nodes[j]; | 143 Node* node = nodes[j]; |
| 145 | 144 |
| 146 evaluationContext.node = node; | 145 evaluationContext.node = node; |
| 147 evaluationContext.size = nodes.size(); | 146 evaluationContext.size = nodes.size(); |
| 148 evaluationContext.position = j + 1; | 147 evaluationContext.position = j + 1; |
| 149 if (predicate->evaluate(evaluationContext)) | 148 if (predicate->evaluate(evaluationContext)) |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 232 } | 231 } |
| 233 | 232 |
| 234 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node,
Step::Axis axis, const Step::NodeTest& nodeTest) | 233 static inline bool nodeMatches(EvaluationContext& evaluationContext, Node* node,
Step::Axis axis, const Step::NodeTest& nodeTest) |
| 235 { | 234 { |
| 236 if (!nodeMatchesBasicTest(node, axis, nodeTest)) | 235 if (!nodeMatchesBasicTest(node, axis, nodeTest)) |
| 237 return false; | 236 return false; |
| 238 | 237 |
| 239 // Only the first merged predicate may depend on position. | 238 // Only the first merged predicate may depend on position. |
| 240 ++evaluationContext.position; | 239 ++evaluationContext.position; |
| 241 | 240 |
| 242 const WillBeHeapVector<OwnPtrWillBeMember<Predicate> >& mergedPredicates = n
odeTest.mergedPredicates(); | 241 const HeapVector<Member<Predicate> >& mergedPredicates = nodeTest.mergedPred
icates(); |
| 243 for (unsigned i = 0; i < mergedPredicates.size(); i++) { | 242 for (unsigned i = 0; i < mergedPredicates.size(); i++) { |
| 244 Predicate* predicate = mergedPredicates[i].get(); | 243 Predicate* predicate = mergedPredicates[i].get(); |
| 245 | 244 |
| 246 evaluationContext.node = node; | 245 evaluationContext.node = node; |
| 247 // No need to set context size - we only get here when evaluating | 246 // No need to set context size - we only get here when evaluating |
| 248 // predicates that do not depend on it. | 247 // predicates that do not depend on it. |
| 249 if (!predicate->evaluate(evaluationContext)) | 248 if (!predicate->evaluate(evaluationContext)) |
| 250 return false; | 249 return false; |
| 251 } | 250 } |
| 252 | 251 |
| (...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 431 nodes.markSorted(false); | 430 nodes.markSorted(false); |
| 432 return; | 431 return; |
| 433 } | 432 } |
| 434 } | 433 } |
| 435 ASSERT_NOT_REACHED(); | 434 ASSERT_NOT_REACHED(); |
| 436 } | 435 } |
| 437 | 436 |
| 438 } | 437 } |
| 439 | 438 |
| 440 } | 439 } |
| OLD | NEW |