Reviewed by Darin.
A partial fix for http://bugs.webkit.org/show_bug.cgi?id=13021
XPath can be very slow
* xml/XPathExpression.cpp:
(WebCore::XPathExpression::evaluate): Cache evaluationContext in a local variable.
* xml/XPathExpressionNode.cpp:
(WebCore::XPath::Expression::evaluationContext):
* xml/XPathExpressionNode.h:
(WebCore::XPath::Expression::addSubExpression):
(WebCore::XPath::Expression::subExprCount):
(WebCore::XPath::Expression::subExpr):
* xml/XPathFunctions.cpp:
* xml/XPathFunctions.h:
(WebCore::XPath::Function::setName):
(WebCore::XPath::Function::arg):
(WebCore::XPath::Function::argCount):
(WebCore::XPath::Function::name):
Made one-liners critical for performance inline.
* xml/XPathGrammar.y: Fully parse NodeTests, so that strings are no longer passed for what is
essentially an enum. Use LocationPath accessors to add steps, instead of directly manipulating
internal data members.
* xml/XPathParser.cpp:
(WebCore::XPath::Parser::parseStatement):
(WebCore::XPath::Parser::registerNodeTest):
(WebCore::XPath::Parser::deleteNodeTest):
* xml/XPathParser.h:
Added support methods for changes in XPathGrammar.y.
* xml/XPathPath.cpp:
(WebCore::XPath::Filter::evaluate): Cache evaluationContext in a local variable. Use swap() to avoid
performing vector assignments.
(WebCore::XPath::LocationPath::evaluate): Use swap() to avoid performing vector assignments.
(WebCore::XPath::LocationPath::optimizeStepPair): This new method is called during LocationPath construction,
to simplify the path as it's being built. Currently, the only optimized case is "//*" - it is a basis for
important operations that cannot be efficiently written in XPath 1.0, but can be optimized with a little bit
of XPath 2.0.
(WebCore::XPath::LocationPath::appendStep): A new accessor that modifies m_steps and calls optimizeStepPair().
(WebCore::XPath::LocationPath::insertFirstStep): Ditto.
* xml/XPathPath.h:
(WebCore::XPath::LocationPath::setAbsolute): A new accessor.
* xml/XPathStep.h:
(WebCore::XPath::Step::NodeTest::):
(WebCore::XPath::Step::NodeTest::NodeTest):
(WebCore::XPath::Step::NodeTest::kind):
(WebCore::XPath::Step::NodeTest::data):
Step::NodeTest is a new sub-class that represents a fully parsed NodeTest.
(WebCore::XPath::Step::axis):
(WebCore::XPath::Step::nodeTest):
(WebCore::XPath::Step::nodeTestData):
(WebCore::XPath::Step::namespaceURI):
(WebCore::XPath::Step::predicates):
(WebCore::XPath::Step::setAxis):
(WebCore::XPath::Step::setNodeTest):
(WebCore::XPath::Step::setNodeTestData):
(WebCore::XPath::Step::setNamespaceURI):
(WebCore::XPath::Step::setPredicates):
New accessors that let optimizeStepPair() manipulate Step data.
* xml/XPathStep.cpp:
(WebCore::XPath::Step::Step): Use the new NodeTest class.
(WebCore::XPath::Step::evaluate): Cache evaluationContext in a local variable. Use swap() to avoid
performing unneeded vector assignments.
(WebCore::XPath::Step::nodesInAxis): Cosmetic changes.
(WebCore::XPath::Step::nodeTestMatches): Use NodeTest instead of parsing the test from string each time.
Added a partial implementation of XPath 2.0 element() node test.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@20102 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 862676b..6f83107 100644
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,14 @@
+2007-03-11 Alexey Proskuryakov <ap@webkit.org>
+
+ Reviewed by Darin.
+
+ http://bugs.webkit.org/show_bug.cgi?id=13021
+ XPath can be very slow
+
+ * fast/xpath/4XPath/Core/test_location_path-expected.txt:
+ * fast/xpath/4XPath/Core/test_parser-expected.txt:
+ These tests now pass, as "//*" now happens to produce correct node order.
+
2007-03-10 Alexey Proskuryakov <ap@webkit.org>
Reviewed by Darin.
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_location_path-expected.txt b/LayoutTests/fast/xpath/4XPath/Core/test_location_path-expected.txt
index 441a645..288bb03 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_location_path-expected.txt
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_location_path-expected.txt
@@ -1,4 +1,4 @@
-FAIL //* item 2 incorrect (expected GCHILD, actual CHILD2)
+PASS //*
PASS */*
PASS /
PASS /child::*
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_parser-expected.txt b/LayoutTests/fast/xpath/4XPath/Core/test_parser-expected.txt
index 8aa7b8b..41075c5 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_parser-expected.txt
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_parser-expected.txt
@@ -2,7 +2,7 @@
PASS /child::*
PASS /*/*
PASS /child::*/*/child::GCHILD
-FAIL //* item 2 incorrect (expected GCHILD, actual CHILD2)
+PASS //*
PASS //GCHILD
PASS //@attr1
PASS x:GCHILD
diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
index 081ceb5..e279f49 100644
--- a/WebCore/ChangeLog
+++ b/WebCore/ChangeLog
@@ -1,3 +1,77 @@
+2007-03-11 Alexey Proskuryakov <ap@webkit.org>
+
+ Reviewed by Darin.
+
+ A partial fix for http://bugs.webkit.org/show_bug.cgi?id=13021
+ XPath can be very slow
+
+ * xml/XPathExpression.cpp:
+ (WebCore::XPathExpression::evaluate): Cache evaluationContext in a local variable.
+
+ * xml/XPathExpressionNode.cpp:
+ (WebCore::XPath::Expression::evaluationContext):
+ * xml/XPathExpressionNode.h:
+ (WebCore::XPath::Expression::addSubExpression):
+ (WebCore::XPath::Expression::subExprCount):
+ (WebCore::XPath::Expression::subExpr):
+ * xml/XPathFunctions.cpp:
+ * xml/XPathFunctions.h:
+ (WebCore::XPath::Function::setName):
+ (WebCore::XPath::Function::arg):
+ (WebCore::XPath::Function::argCount):
+ (WebCore::XPath::Function::name):
+ Made one-liners critical for performance inline.
+
+ * xml/XPathGrammar.y: Fully parse NodeTests, so that strings are no longer passed for what is
+ essentially an enum. Use LocationPath accessors to add steps, instead of directly manipulating
+ internal data members.
+
+ * xml/XPathParser.cpp:
+ (WebCore::XPath::Parser::parseStatement):
+ (WebCore::XPath::Parser::registerNodeTest):
+ (WebCore::XPath::Parser::deleteNodeTest):
+ * xml/XPathParser.h:
+ Added support methods for changes in XPathGrammar.y.
+
+ * xml/XPathPath.cpp:
+ (WebCore::XPath::Filter::evaluate): Cache evaluationContext in a local variable. Use swap() to avoid
+ performing vector assignments.
+ (WebCore::XPath::LocationPath::evaluate): Use swap() to avoid performing vector assignments.
+ (WebCore::XPath::LocationPath::optimizeStepPair): This new method is called during LocationPath construction,
+ to simplify the path as it's being built. Currently, the only optimized case is "//*" - it is a basis for
+ important operations that cannot be efficiently written in XPath 1.0, but can be optimized with a little bit
+ of XPath 2.0.
+ (WebCore::XPath::LocationPath::appendStep): A new accessor that modifies m_steps and calls optimizeStepPair().
+ (WebCore::XPath::LocationPath::insertFirstStep): Ditto.
+ * xml/XPathPath.h:
+ (WebCore::XPath::LocationPath::setAbsolute): A new accessor.
+
+ * xml/XPathStep.h:
+ (WebCore::XPath::Step::NodeTest::):
+ (WebCore::XPath::Step::NodeTest::NodeTest):
+ (WebCore::XPath::Step::NodeTest::kind):
+ (WebCore::XPath::Step::NodeTest::data):
+ Step::NodeTest is a new sub-class that represents a fully parsed NodeTest.
+ (WebCore::XPath::Step::axis):
+ (WebCore::XPath::Step::nodeTest):
+ (WebCore::XPath::Step::nodeTestData):
+ (WebCore::XPath::Step::namespaceURI):
+ (WebCore::XPath::Step::predicates):
+ (WebCore::XPath::Step::setAxis):
+ (WebCore::XPath::Step::setNodeTest):
+ (WebCore::XPath::Step::setNodeTestData):
+ (WebCore::XPath::Step::setNamespaceURI):
+ (WebCore::XPath::Step::setPredicates):
+ New accessors that let optimizeStepPair() manipulate Step data.
+
+ * xml/XPathStep.cpp:
+ (WebCore::XPath::Step::Step): Use the new NodeTest class.
+ (WebCore::XPath::Step::evaluate): Cache evaluationContext in a local variable. Use swap() to avoid
+ performing unneeded vector assignments.
+ (WebCore::XPath::Step::nodesInAxis): Cosmetic changes.
+ (WebCore::XPath::Step::nodeTestMatches): Use NodeTest instead of parsing the test from string each time.
+ Added a partial implementation of XPath 2.0 element() node test.
+
2007-03-10 Alexey Proskuryakov <ap@webkit.org>
Reviewed by Darin.
diff --git a/WebCore/xml/XPathExpression.cpp b/WebCore/xml/XPathExpression.cpp
index a17324f..9231001 100644
--- a/WebCore/xml/XPathExpression.cpp
+++ b/WebCore/xml/XPathExpression.cpp
@@ -71,9 +71,10 @@
? contextNode->ownerDocument()
: static_cast<EventTargetNode*>(contextNode);
- Expression::evaluationContext().node = contextNode;
- Expression::evaluationContext().size = 1;
- Expression::evaluationContext().position = 1;
+ EvaluationContext& evaluationContext = Expression::evaluationContext();
+ evaluationContext.node = contextNode;
+ evaluationContext.size = 1;
+ evaluationContext.position = 1;
RefPtr<XPathResult> result = new XPathResult(eventTarget, m_topExpression->evaluate());
if (type != XPathResult::ANY_TYPE) {
diff --git a/WebCore/xml/XPathExpressionNode.cpp b/WebCore/xml/XPathExpressionNode.cpp
index c37aa6b..88e349e 100644
--- a/WebCore/xml/XPathExpressionNode.cpp
+++ b/WebCore/xml/XPathExpressionNode.cpp
@@ -35,7 +35,7 @@
namespace WebCore {
namespace XPath {
-EvaluationContext &Expression::evaluationContext()
+EvaluationContext& Expression::evaluationContext()
{
static EvaluationContext evaluationContext;
return evaluationContext;
@@ -50,28 +50,6 @@
deleteAllValues(m_subExpressions);
}
-void Expression::addSubExpression(Expression* expr)
-{
- m_subExpressions.append(expr);
-}
-
-unsigned Expression::subExprCount() const
-{
- return m_subExpressions.size();
-}
-
-Expression* Expression::subExpr(unsigned i)
-{
- ASSERT(i < subExprCount());
- return m_subExpressions[i];
-}
-
-const Expression* Expression::subExpr(unsigned i) const
-{
- ASSERT(i < subExprCount());
- return m_subExpressions[i];
-}
-
}
}
diff --git a/WebCore/xml/XPathExpressionNode.h b/WebCore/xml/XPathExpressionNode.h
index c9ac08c..6a483f1 100644
--- a/WebCore/xml/XPathExpressionNode.h
+++ b/WebCore/xml/XPathExpressionNode.h
@@ -65,12 +65,12 @@
virtual Value evaluate() const = 0;
- void addSubExpression(Expression*);
+ void addSubExpression(Expression* expr) { m_subExpressions.append(expr); }
protected:
- unsigned subExprCount() const;
- Expression* subExpr(unsigned);
- const Expression* subExpr(unsigned) const;
+ unsigned subExprCount() const { return m_subExpressions.size(); }
+ Expression* subExpr(unsigned i) { return m_subExpressions[i]; }
+ const Expression* subExpr(unsigned i) const { return m_subExpressions[i]; }
private:
Vector<Expression*> m_subExpressions;
diff --git a/WebCore/xml/XPathFunctions.cpp b/WebCore/xml/XPathFunctions.cpp
index 259699b..a4d5bff 100644
--- a/WebCore/xml/XPathFunctions.cpp
+++ b/WebCore/xml/XPathFunctions.cpp
@@ -250,31 +250,6 @@
addSubExpression(*it);
}
-void Function::setName(const String& name)
-{
- m_name = name;
-}
-
-Expression* Function::arg(int i)
-{
- return subExpr(i);
-}
-
-const Expression* Function::arg(int i) const
-{
- return subExpr(i);
-}
-
-unsigned int Function::argCount() const
-{
- return subExprCount();
-}
-
-String Function::name() const
-{
- return m_name;
-}
-
Value FunLast::evaluate() const
{
return Expression::evaluationContext().size;
diff --git a/WebCore/xml/XPathFunctions.h b/WebCore/xml/XPathFunctions.h
index 819c5a8..f22d3ef 100644
--- a/WebCore/xml/XPathFunctions.h
+++ b/WebCore/xml/XPathFunctions.h
@@ -38,13 +38,13 @@
class Function : public Expression {
public:
void setArguments(const Vector<Expression*>&);
- void setName(const String&);
+ void setName(const String& name) { m_name = name; }
protected:
- Expression* arg(int pos);
- const Expression* arg(int pos) const;
- unsigned int argCount() const;
- String name() const;
+ Expression* arg(int pos) { return subExpr(pos); }
+ const Expression* arg(int pos) const { return subExpr(pos); }
+ unsigned int argCount() const { return subExprCount(); }
+ String name() const { return m_name; }
private:
String m_name;
diff --git a/WebCore/xml/XPathGrammar.y b/WebCore/xml/XPathGrammar.y
index 38678d3..bcaa0ab 100644
--- a/WebCore/xml/XPathGrammar.y
+++ b/WebCore/xml/XPathGrammar.y
@@ -55,6 +55,7 @@
%union
{
Step::Axis axis;
+ Step::NodeTest* nodeTest;
NumericOp::Opcode numop;
EqTestOp::Opcode eqop;
String* str;
@@ -89,7 +90,7 @@
%type <step> Step
%type <axis> AxisSpecifier
%type <step> DescendantOrSelf
-%type <str> NodeTest
+%type <nodeTest> NodeTest
%type <expr> Predicate
%type <predList> OptionalPredicateList
%type <predList> PredicateList
@@ -122,12 +123,12 @@
LocationPath:
RelativeLocationPath
{
- $$->m_absolute = false;
+ $$->setAbsolute(false);
}
|
AbsoluteLocationPath
{
- $$->m_absolute = true;
+ $$->setAbsolute(true);
}
;
@@ -146,7 +147,7 @@
DescendantOrSelf RelativeLocationPath
{
$$ = $2;
- $$->m_steps.insert(0, $1);
+ $$->insertFirstStep($1);
PARSER->unregisterParseNode($1);
}
;
@@ -155,21 +156,21 @@
Step
{
$$ = new LocationPath;
- $$->m_steps.append($1);
+ $$->appendStep($1);
PARSER->unregisterParseNode($1);
PARSER->registerParseNode($$);
}
|
RelativeLocationPath '/' Step
{
- $$->m_steps.append($3);
+ $$->appendStep($3);
PARSER->unregisterParseNode($3);
}
|
RelativeLocationPath DescendantOrSelf Step
{
- $$->m_steps.append($2);
- $$->m_steps.append($3);
+ $$->appendStep($2);
+ $$->appendStep($3);
PARSER->unregisterParseNode($2);
PARSER->unregisterParseNode($3);
}
@@ -183,7 +184,7 @@
PARSER->deletePredicateVector($2);
} else
$$ = new Step(Step::ChildAxis, *$1);
- PARSER->deleteString($1);
+ PARSER->deleteNodeTest($1);
PARSER->registerParseNode($$);
}
|
@@ -197,10 +198,10 @@
}
if ($2) {
- $$ = new Step(Step::ChildAxis, localName, namespaceURI, *$2);
+ $$ = new Step(Step::ChildAxis, Step::NodeTest(Step::NodeTest::NameTest, localName), namespaceURI, *$2);
PARSER->deletePredicateVector($2);
} else
- $$ = new Step(Step::ChildAxis, localName, namespaceURI);
+ $$ = new Step(Step::ChildAxis, Step::NodeTest(Step::NodeTest::NameTest, localName), namespaceURI);
PARSER->deleteString($1);
PARSER->registerParseNode($$);
}
@@ -212,7 +213,7 @@
PARSER->deletePredicateVector($3);
} else
$$ = new Step($1, *$2);
- PARSER->deleteString($2);
+ PARSER->deleteNodeTest($2);
PARSER->registerParseNode($$);
}
|
@@ -226,10 +227,10 @@
}
if ($3) {
- $$ = new Step($1, localName, namespaceURI, *$3);
+ $$ = new Step($1, Step::NodeTest(Step::NodeTest::NameTest, localName), namespaceURI, *$3);
PARSER->deletePredicateVector($3);
} else
- $$ = new Step($1, localName, namespaceURI);
+ $$ = new Step($1, Step::NodeTest(Step::NodeTest::NameTest, localName), namespaceURI);
PARSER->deleteString($2);
PARSER->registerParseNode($$);
}
@@ -249,20 +250,30 @@
NodeTest:
NODETYPE '(' ')'
{
- $$ = new String(*$1 + "()");
+ if (*$1 == "node")
+ $$ = new Step::NodeTest(Step::NodeTest::AnyNodeTest);
+ else if (*$1 == "text")
+ $$ = new Step::NodeTest(Step::NodeTest::TextNodeTest);
+ else if (*$1 == "comment")
+ $$ = new Step::NodeTest(Step::NodeTest::CommentNodeTest);
+
PARSER->deleteString($1);
- PARSER->registerString($$);
+ PARSER->registerNodeTest($$);
}
|
PI '(' ')'
+ {
+ $$ = new Step::NodeTest(Step::NodeTest::ProcessingInstructionNodeTest);
+ PARSER->deleteString($1);
+ PARSER->registerNodeTest($$);
+ }
|
PI '(' LITERAL ')'
{
- String s = *$1 + " " + *$3;
- $$ = new String(s.stripWhiteSpace());
+ $$ = new Step::NodeTest(Step::NodeTest::ProcessingInstructionNodeTest, $3->stripWhiteSpace());
PARSER->deleteString($1);
PARSER->deleteString($3);
- PARSER->registerString($$);
+ PARSER->registerNodeTest($$);
}
;
@@ -301,7 +312,7 @@
DescendantOrSelf:
SLASHSLASH
{
- $$ = new Step(Step::DescendantOrSelfAxis, "node()");
+ $$ = new Step(Step::DescendantOrSelfAxis, Step::NodeTest(Step::NodeTest::AnyNodeTest));
PARSER->registerParseNode($$);
}
;
@@ -309,13 +320,13 @@
AbbreviatedStep:
'.'
{
- $$ = new Step(Step::SelfAxis, "node()");
+ $$ = new Step(Step::SelfAxis, Step::NodeTest(Step::NodeTest::AnyNodeTest));
PARSER->registerParseNode($$);
}
|
DOTDOT
{
- $$ = new Step(Step::ParentAxis, "node()");
+ $$ = new Step(Step::ParentAxis, Step::NodeTest(Step::NodeTest::AnyNodeTest));
PARSER->registerParseNode($$);
}
;
@@ -411,7 +422,7 @@
|
FilterExpr '/' RelativeLocationPath
{
- $3->m_absolute = true;
+ $3->setAbsolute(true);
$$ = new Path(static_cast<Filter*>($1), $3);
PARSER->unregisterParseNode($1);
PARSER->unregisterParseNode($3);
@@ -420,8 +431,8 @@
|
FilterExpr DescendantOrSelf RelativeLocationPath
{
- $3->m_steps.insert(0, $2);
- $3->m_absolute = true;
+ $3->insertFirstStep($2);
+ $3->setAbsolute(true);
$$ = new Path(static_cast<Filter*>($1), $3);
PARSER->unregisterParseNode($1);
PARSER->unregisterParseNode($2);
diff --git a/WebCore/xml/XPathParser.cpp b/WebCore/xml/XPathParser.cpp
index 1abb45c..96e1b8b 100644
--- a/WebCore/xml/XPathParser.cpp
+++ b/WebCore/xml/XPathParser.cpp
@@ -494,6 +494,9 @@
deleteAllValues(m_strings);
m_strings.clear();
+ deleteAllValues(m_nodeTests);
+ m_nodeTests.clear();
+
m_topExpr = 0;
if (m_gotNamespaceError)
@@ -508,6 +511,7 @@
ASSERT(m_expressionVectors.size() == 0);
ASSERT(m_predicateVectors.size() == 0);
ASSERT(m_strings.size() == 0);
+ ASSERT(m_nodeTests.size() == 0);
m_parseNodes.clear();
Expression* result = m_topExpr;
@@ -600,6 +604,27 @@
delete s;
}
+void Parser::registerNodeTest(Step::NodeTest* t)
+{
+ if (t == 0)
+ return;
+
+ ASSERT(!m_nodeTests.contains(t));
+
+ m_nodeTests.add(t);
+}
+
+void Parser::deleteNodeTest(Step::NodeTest* t)
+{
+ if (t == 0)
+ return;
+
+ ASSERT(m_nodeTests.contains(t));
+
+ m_nodeTests.remove(t);
+ delete t;
+}
+
}
}
diff --git a/WebCore/xml/XPathParser.h b/WebCore/xml/XPathParser.h
index e13874f..8d6da3f 100644
--- a/WebCore/xml/XPathParser.h
+++ b/WebCore/xml/XPathParser.h
@@ -86,6 +86,9 @@
void registerString(String*);
void deleteString(String*);
+ void registerNodeTest(Step::NodeTest*);
+ void deleteNodeTest(Step::NodeTest*);
+
private:
bool isOperatorContext() const;
@@ -117,6 +120,7 @@
HashSet<Vector<Predicate*>*> m_predicateVectors;
HashSet<Vector<Expression*>*> m_expressionVectors;
HashSet<String*> m_strings;
+ HashSet<Step::NodeTest*> m_nodeTests;
};
}
diff --git a/WebCore/xml/XPathPath.cpp b/WebCore/xml/XPathPath.cpp
index ff2859b..162e676 100644
--- a/WebCore/xml/XPathPath.cpp
+++ b/WebCore/xml/XPathPath.cpp
@@ -55,25 +55,27 @@
if (!v.isNodeVector())
return v;
- NodeVector inNodes = v.toNodeVector(), outNodes;
+ NodeVector nodes = v.toNodeVector();
+
+ EvaluationContext& evaluationContext = Expression::evaluationContext();
for (unsigned i = 0; i < m_predicates.size(); i++) {
- outNodes.clear();
- Expression::evaluationContext().size = inNodes.size();
- Expression::evaluationContext().position = 0;
+ NodeVector newNodes;
+ evaluationContext.size = nodes.size();
+ evaluationContext.position = 0;
- for (unsigned j = 0; j < inNodes.size(); j++) {
- Node* node = inNodes[j].get();
+ for (unsigned j = 0; j < nodes.size(); j++) {
+ Node* node = nodes[j].get();
- Expression::evaluationContext().node = node;
- ++Expression::evaluationContext().position;
+ evaluationContext.node = node;
+ ++evaluationContext.position;
if (m_predicates[i]->evaluate())
- outNodes.append(node);
+ newNodes.append(node);
}
- inNodes = outNodes;
+ nodes.swap(newNodes);
}
- return outNodes;
+ return nodes;
}
LocationPath::LocationPath()
@@ -120,12 +122,52 @@
}
}
- inDOMNodes = outDOMNodes;
+ inDOMNodes.swap(outDOMNodes);
}
return inDOMNodes;
}
+void LocationPath::optimizeStepPair(unsigned index)
+{
+ Step* first = m_steps[index];
+
+ if (first->axis() == Step::DescendantOrSelfAxis
+ && first->nodeTest().kind() == Step::NodeTest::AnyNodeTest
+ && first->predicates().size() == 0) {
+
+ Step* second = m_steps[index + 1];
+ if (second->axis() == Step::ChildAxis
+ && second->namespaceURI().isEmpty()
+ && second->nodeTest().kind() == Step::NodeTest::NameTest
+ && second->nodeTest().data() == "*") {
+
+ // Optimize the common case of "//*" AKA descendant-or-self::node()/child::*.
+ first->setAxis(Step::DescendantAxis);
+ second->setAxis(Step::SelfAxis);
+ second->setNodeTest(Step::NodeTest::ElementNodeTest);
+ ASSERT(second->nodeTest().data().isEmpty());
+ }
+ }
+}
+
+void LocationPath::appendStep(Step* step)
+{
+ m_steps.append(step);
+
+ unsigned stepCount = m_steps.size();
+ if (stepCount > 1)
+ optimizeStepPair(stepCount - 2);
+}
+
+void LocationPath::insertFirstStep(Step* step)
+{
+ m_steps.insert(0, step);
+
+ if (m_steps.size() > 1)
+ optimizeStepPair(0);
+}
+
Path::Path(Filter* filter, LocationPath* path)
: m_filter(filter),
m_path(path)
diff --git a/WebCore/xml/XPathPath.h b/WebCore/xml/XPathPath.h
index e4f8906..b19130a 100644
--- a/WebCore/xml/XPathPath.h
+++ b/WebCore/xml/XPathPath.h
@@ -57,15 +57,19 @@
public:
LocationPath();
virtual ~LocationPath();
+ void setAbsolute(bool value) { m_absolute = value; }
virtual Value evaluate() const;
Value evaluate(const NodeVector& startNodes) const;
+ void appendStep(Step* step);
+ void insertFirstStep(Step* step);
+
private:
+ void optimizeStepPair(unsigned index);
+
Vector<Step*> m_steps;
bool m_absolute;
-
- friend int ::xpathyyparse(void*);
};
class Path : public Expression
diff --git a/WebCore/xml/XPathStep.cpp b/WebCore/xml/XPathStep.cpp
index 81d9bb2..b33972a 100644
--- a/WebCore/xml/XPathStep.cpp
+++ b/WebCore/xml/XPathStep.cpp
@@ -38,14 +38,14 @@
namespace WebCore {
namespace XPath {
-Step::Step(Axis axis, const String& nodeTest, const Vector<Predicate*>& predicates)
+Step::Step(Axis axis, const NodeTest& nodeTest, const Vector<Predicate*>& predicates)
: m_axis(axis)
, m_nodeTest(nodeTest)
, m_predicates(predicates)
{
}
-Step::Step(Axis axis, const String& nodeTest, const String& namespaceURI, const Vector<Predicate*>& predicates)
+Step::Step(Axis axis, const NodeTest& nodeTest, const String& namespaceURI, const Vector<Predicate*>& predicates)
: m_axis(axis)
, m_nodeTest(nodeTest)
, m_namespaceURI(namespaceURI)
@@ -60,31 +60,32 @@
NodeVector Step::evaluate(Node* context) const
{
- NodeVector inNodes = nodesInAxis(context), outNodes;
- inNodes = nodeTestMatches(inNodes);
+ NodeVector nodes = nodesInAxis(context);
+ nodes = nodeTestMatches(nodes);
- outNodes = inNodes;
+ EvaluationContext& evaluationContext = Expression::evaluationContext();
+
for (unsigned i = 0; i < m_predicates.size(); i++) {
Predicate* predicate = m_predicates[i];
- outNodes.clear();
- Expression::evaluationContext().size = inNodes.size();
- Expression::evaluationContext().position = 1;
- for (unsigned j = 0; j < inNodes.size(); j++) {
- Node* node = inNodes[j].get();
+ NodeVector newNodes;
+ evaluationContext.size = nodes.size();
+ evaluationContext.position = 1;
+ for (unsigned j = 0; j < nodes.size(); j++) {
+ Node* node = nodes[j].get();
Expression::evaluationContext().node = node;
- EvaluationContext backupCtx = Expression::evaluationContext();
+ EvaluationContext backupCtx = evaluationContext;
if (predicate->evaluate())
- outNodes.append(node);
+ newNodes.append(node);
- Expression::evaluationContext() = backupCtx;
- ++Expression::evaluationContext().position;
+ evaluationContext = backupCtx;
+ ++evaluationContext.position;
}
- inNodes = outNodes;
+ nodes.swap(newNodes);
}
- return outNodes;
+ return nodes;
}
NodeVector Step::nodesInAxis(Node* context) const
@@ -155,10 +156,9 @@
nodes.append (attrs->item(i));
return nodes;
}
- case NamespaceAxis: {
+ case NamespaceAxis:
// XPath namespace nodes are not implemented yet.
return NodeVector();
- }
case SelfAxis:
nodes.append(context);
return nodes;
@@ -173,7 +173,7 @@
nodes.append(n);
return nodes;
}
-
+ ASSERT_NOT_REACHED();
return NodeVector();
}
@@ -182,86 +182,91 @@
{
NodeVector matches;
- if (m_nodeTest == "*") {
- for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
- if (node->nodeType() == primaryNodeType(m_axis) &&
- (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI()))
- matches.append(node);
- }
- return matches;
- } else if (m_nodeTest == "text()") {
- HashSet<Node*> nodeSet;
- for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
- if ((node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE)) {
- nodeSet.add(node);
- if (!nodeSet.contains(node->previousSibling())) // See <http://www.w3.org/TR/DOM-Level-3-XPath/xpath.html#TextNodes>
- matches.append(node);
- }
- }
- return matches;
- } else if (m_nodeTest == "comment()") {
- for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
- if (node->nodeType() == Node::COMMENT_NODE)
- matches.append(node);
- }
- return matches;
- } else if (m_nodeTest.startsWith("processing-instruction")) {
- String param;
-
- const int space = m_nodeTest.find(' ');
- if (space > -1)
- param = m_nodeTest.substring(space + 1);
-
- for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
-
- if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE &&
- (param.isEmpty() || node->nodeName() == param))
- matches.append(node);
- }
- return matches;
- } else if (m_nodeTest == "node()")
- return nodes;
- else {
- if (m_axis == AttributeAxis) {
- // In XPath land, namespace nodes are not accessible
- // on the attribute axis.
- if (m_nodeTest == "xmlns")
- return matches;
-
+ switch (m_nodeTest.kind()) {
+ case NodeTest::TextNodeTest: {
+ HashSet<Node*> nodeSet;
for (unsigned i = 0; i < nodes.size(); i++) {
Node* node = nodes[i].get();
-
- if (node->nodeName() == m_nodeTest) {
- matches.append(node);
- break; // There can only be one.
+ if ((node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE)) {
+ nodeSet.add(node);
+ if (!nodeSet.contains(node->previousSibling())) // See <http://www.w3.org/TR/DOM-Level-3-XPath/xpath.html#TextNodes>
+ matches.append(node);
}
}
-
- return matches;
- } else if (m_axis == NamespaceAxis) {
- // Node test on the namespace axis is not implemented yet
- } else {
- for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
-
- // We use tagQName here because we don't want the element name in uppercase
- // like we get with HTML elements.
- // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
- if (node->nodeType() == Node::ELEMENT_NODE
- && static_cast<Element*>(node)->tagQName().localName() == m_nodeTest
- && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI()))
- matches.append(node);
- }
-
return matches;
}
- }
+ case NodeTest::CommentNodeTest:
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+ if (node->nodeType() == Node::COMMENT_NODE)
+ matches.append(node);
+ }
+ return matches;
+ case NodeTest::ProcessingInstructionNodeTest:
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+ const String& name = m_nodeTest.data();
+ if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name))
+ matches.append(node);
+ }
+ return matches;
+ case NodeTest::ElementNodeTest:
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+ if (node->isElementNode())
+ matches.append(node);
+ }
+ return matches;
+ case NodeTest::AnyNodeTest:
+ return nodes;
+ case NodeTest::NameTest: {
+ const String& name = m_nodeTest.data();
+ if (name == "*") {
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+ if (node->nodeType() == primaryNodeType(m_axis) &&
+ (m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI()))
+ matches.append(node);
+ }
+ return matches;
+ }
+ if (m_axis == AttributeAxis) {
+ // In XPath land, namespace nodes are not accessible
+ // on the attribute axis.
+ if (name == "xmlns")
+ return matches;
- return matches;
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+
+ if (node->nodeName() == name) {
+ matches.append(node);
+ break; // There can only be one.
+ }
+ }
+
+ return matches;
+ } else if (m_axis == NamespaceAxis) {
+ // Node test on the namespace axis is not implemented yet
+ } else {
+ for (unsigned i = 0; i < nodes.size(); i++) {
+ Node* node = nodes[i].get();
+
+ // We use tagQName here because we don't want the element name in uppercase
+ // like we get with HTML elements.
+ // Paths without namespaces should match HTML elements in HTML documents despite those having an XHTML namespace.
+ if (node->nodeType() == Node::ELEMENT_NODE
+ && static_cast<Element*>(node)->tagQName().localName() == name
+ && ((node->isHTMLElement() && node->document()->isHTMLDocument() && m_namespaceURI.isNull()) || m_namespaceURI == node->namespaceURI()))
+ matches.append(node);
+ }
+
+ return matches;
+ }
+ }
+ }
+ ASSERT_NOT_REACHED();
+ return NodeVector();
}
Node::NodeType Step::primaryNodeType(Axis axis) const
diff --git a/WebCore/xml/XPathStep.h b/WebCore/xml/XPathStep.h
index 65a7101..8758867 100644
--- a/WebCore/xml/XPathStep.h
+++ b/WebCore/xml/XPathStep.h
@@ -48,21 +48,52 @@
ParentAxis, PrecedingAxis, PrecedingSiblingAxis,
SelfAxis
};
+
+ class NodeTest {
+ public:
+ enum Kind {
+ TextNodeTest, CommentNodeTest, ProcessingInstructionNodeTest, AnyNodeTest, NameTest,
+ ElementNodeTest // XPath 2.0
+ };
+
+ NodeTest(Kind kind, const String& data = String()) : m_kind(kind), m_data(data) {}
+
+ Kind kind() const { return m_kind; }
+ const String data() const { return m_data; }
+
+ private:
+ Kind m_kind;
+ String m_data;
+ };
- Step(Axis, const String& nodeTest, const Vector<Predicate*>& predicates = Vector<Predicate*>());
- Step(Axis, const String& nodeTest, const String& namespaceURI, const Vector<Predicate*>& predicates = Vector<Predicate*>());
+ Step(Axis, const NodeTest& nodeTest, const Vector<Predicate*>& predicates = Vector<Predicate*>());
+ Step(Axis, const NodeTest& nodeTest, const String& namespaceURI, const Vector<Predicate*>& predicates = Vector<Predicate*>());
~Step();
NodeVector evaluate(Node* context) const;
-
+
+ Axis axis() const { return m_axis; }
+ NodeTest nodeTest() const { return m_nodeTest; }
+ const String& nodeTestData() const { return m_nodeTestData; }
+ const String& namespaceURI() const { return m_namespaceURI; }
+ const Vector<Predicate*>& predicates() const { return m_predicates; }
+
+ void setAxis(Axis axis) { m_axis = axis; }
+ void setNodeTest(NodeTest nodeTest) { m_nodeTest = nodeTest; }
+ void setNodeTestData(const String& nodeTestData) { m_nodeTestData = nodeTestData; }
+ void setNamespaceURI(const String& namespaceURI) { m_namespaceURI = namespaceURI; }
+ void setPredicates(const Vector<Predicate*>& predicates) { m_predicates = predicates; }
+
private:
+ void parseNodeTest(const String&);
NodeVector nodesInAxis(Node* context) const;
NodeVector nodeTestMatches(const NodeVector& nodes) const;
String namespaceFromNodetest(const String& nodeTest) const;
Node::NodeType primaryNodeType(Axis) const;
Axis m_axis;
- String m_nodeTest;
+ NodeTest m_nodeTest;
+ String m_nodeTestData;
String m_namespaceURI;
Vector<Predicate*> m_predicates;
};
