Reviewed by Darin.
http://bugs.webkit.org/show_bug.cgi?id=12497
Implement XPath result ordering.
WebCore:
XPath::NodeVector typedef is replaced with a real XPath::NodeSet class that knows how
to sort itself, and can remember whether it has been already sorted.
* CMakeLists.txt:
* WebCore.pro:
* WebCore.xcodeproj/project.pbxproj:
* WebCoreSources.bkl:
Added XPathNodeSet files.
* xml/XPathExpression.cpp: Fixed includes.
* xml/XPathFunctions.cpp:
(WebCore::XPath::FunId::evaluate): Mark the resulting node-set as unsorted.
(WebCore::XPath::FunLocalName::evaluate): Replacing NodeVector with NodeSet.
(WebCore::XPath::FunNamespaceURI::evaluate): Ditto.
(WebCore::XPath::FunName::evaluate): Ditto.
(WebCore::XPath::FunCount::evaluate): Ditto.
(WebCore::XPath::FunSum::evaluate): Ditto.
* xml/XPathNodeSet.cpp: Added.
(WebCore::XPath::parentWithDepth):
(WebCore::XPath::sortBlock):
(WebCore::XPath::NodeSet::sort): Sort the node-set in document order.
(WebCore::XPath::NodeSet::reverse): Reverse the order (useful for making axes such as
parent or ancestor sorted).
(WebCore::XPath::NodeSet::firstNode): Returns the first node in document order; currently
implemented via fully sorting the node-set, but this can obviously be optimized.
(WebCore::XPath::NodeSet::anyNode): Added for symmetry with firstNode().
* xml/XPathNodeSet.h: Added.
(WebCore::XPath::NodeSet::NodeSet):
(WebCore::XPath::NodeSet::operator=):
(WebCore::XPath::NodeSet::size):
(WebCore::XPath::NodeSet::isEmpty):
(WebCore::XPath::NodeSet::operator[]):
(WebCore::XPath::NodeSet::reserveCapacity):
(WebCore::XPath::NodeSet::clear):
(WebCore::XPath::NodeSet::swap):
(WebCore::XPath::NodeSet::append):
(WebCore::XPath::NodeSet::markSorted):
(WebCore::XPath::NodeSet::isSorted):
Most of these methods just call Vector counterparts.
* xml/XPathParser.cpp: Updated the copyright notice.
* xml/XPathPath.cpp:
(WebCore::XPath::Filter::evaluate): Replacing NodeVector with NodeSet.
(WebCore::XPath::Path::evaluate): Ditto.
(WebCore::XPath::LocationPath::evaluate): Replacing NodeVector with NodeSet. This function
always marks the result as unsorted, because it is hard to tell whether a step breaks node order.
Identifying and implementing special cases when it is not necessary to do so is an important
future optimization.
* xml/XPathPath.h: Replacing NodeVector with NodeSet.
* xml/XPathPredicate.cpp:
(WebCore::XPath::EqTestOp::compare): Replacing NodeVector with NodeSet.
(WebCore::XPath::Union::evaluate): Replacing NodeVector with NodeSet. Currently, Union just
marks the result as unordered; we can consider using merge sort to avoid this.
* xml/XPathResult.cpp:
(WebCore::XPathResult::XPathResult): Replacing NodeVector with NodeSet.
(WebCore::XPathResult::singleNodeValue): Ditto.
(WebCore::XPathResult::snapshotLength): Ditto.
(WebCore::XPathResult::iterateNext): Ditto.
(WebCore::XPathResult::snapshotItem): Ditto.
(WebCore::XPathResult::convertTo): Ditto. Sort the result when requested to.
* xml/XPathResult.h: Replacing NodeVector with NodeSet.
* xml/XPathStep.cpp:
(WebCore::XPath::Step::evaluate): If the input is not sorted, mark the output as such, too.
(WebCore::XPath::Step::nodesInAxis): Fixed a number of bugs when enumerating with an
attribute context node.
(WebCore::XPath::Step::nodeTestMatches): Replacing NodeVector with NodeSet.
* xml/XPathStep.h: Ditto.
* xml/XPathUtil.cpp:
(WebCore::XPath::isValidContextNode): XPath data model doesn't put attribute data into child
nodes, so passing such node as a context could cause problems.
* xml/XPathUtil.h: Removed NodeVector typedef.
* xml/XPathValue.cpp:
(WebCore::XPath::Value::Value):
(WebCore::XPath::Value::toNodeSet):
(WebCore::XPath::Value::toBoolean):
(WebCore::XPath::Value::toNumber):
(WebCore::XPath::Value::toString):
* xml/XPathValue.h:
(WebCore::XPath::Value::):
(WebCore::XPath::Value::isNodeSet):
Replacing NodeVector with NodeSet.
LayoutTests:
* fast/xpath/document-order-expected.txt: Added.
* fast/xpath/document-order.html: Added.
* fast/xpath/text-nodes-expected.txt:
* fast/xpath/text-nodes.html:
* fast/xpath/4XPath/Core/test_step-expected.txt:
Updated results for tests that now pass.
* fast/xpath/xpath-test-pre.js: Added.
* fast/xpath/4XPath/Core/test.js:
Moved checkSnapshot() to a separate file.
* fast/xpath/4XPath/Core/test_core_functions.html:
* fast/xpath/4XPath/Core/test_location_path.html:
* fast/xpath/4XPath/Core/test_nodeset_expr.html:
* fast/xpath/4XPath/Core/test_parser.html:
* fast/xpath/4XPath/Core/test_predicate_list.html:
* fast/xpath/4XPath/Core/test_step.html:
Load xpath-test-pre.js for checkSnapshot().
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@20345 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 1abffc7..59737fc 100644
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,30 @@
+2007-03-20 Alexey Proskuryakov <ap@webkit.org>
+
+ Reviewed by Darin.
+
+ http://bugs.webkit.org/show_bug.cgi?id=12497
+ Implement XPath result ordering.
+
+ * fast/xpath/document-order-expected.txt: Added.
+ * fast/xpath/document-order.html: Added.
+
+ * fast/xpath/text-nodes-expected.txt:
+ * fast/xpath/text-nodes.html:
+ * fast/xpath/4XPath/Core/test_step-expected.txt:
+ Updated results for tests that now pass.
+
+ * fast/xpath/xpath-test-pre.js: Added.
+ * fast/xpath/4XPath/Core/test.js:
+ Moved checkSnapshot() to a separate file.
+
+ * fast/xpath/4XPath/Core/test_core_functions.html:
+ * fast/xpath/4XPath/Core/test_location_path.html:
+ * fast/xpath/4XPath/Core/test_nodeset_expr.html:
+ * fast/xpath/4XPath/Core/test_parser.html:
+ * fast/xpath/4XPath/Core/test_predicate_list.html:
+ * fast/xpath/4XPath/Core/test_step.html:
+ Load xpath-test-pre.js for checkSnapshot().
+
2007-03-19 Alexey Proskuryakov <ap@webkit.org>
Reviewed by Darin.
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test.js b/LayoutTests/fast/xpath/4XPath/Core/test.js
index a0d7bea..194ee44 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test.js
+++ b/LayoutTests/fast/xpath/4XPath/Core/test.js
@@ -60,19 +60,3 @@
LCHILDREN = [LANG.getElementsByTagName("foo")[0], LANG.getElementsByTagName("foo")[1], LANG.getElementsByTagName("f\xf6\xf8")[0]];
LCHILD1 = LCHILDREN[0];
LCHILD2 = LCHILDREN[1];
-
-function checkSnapshot(comment, actual, expected) {
- if (actual.snapshotLength != expected.length) {
- testFailed(comment + " incorrect length (expected " + expected.length + ", actual " + actual.snapshotLength + ")");
- return;
- }
-
- for (i = 0; i < actual.snapshotLength; ++i) {
- if (actual.snapshotItem(i) != expected[i]) {
- testFailed(comment + " item " + i + " incorrect (expected " + expected[i].nodeName + ", actual " + actual.snapshotItem(i).nodeName + ")");
- return;
- }
- }
-
- testPassed(comment);
-}
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_core_functions.html b/LayoutTests/fast/xpath/4XPath/Core/test_core_functions.html
index 739b8fc..ff0f83b 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_core_functions.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_core_functions.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_location_path.html b/LayoutTests/fast/xpath/4XPath/Core/test_location_path.html
index 38634d2..d06d1c6 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_location_path.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_location_path.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_nodeset_expr.html b/LayoutTests/fast/xpath/4XPath/Core/test_nodeset_expr.html
index e94a32fe..bd0c447 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_nodeset_expr.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_nodeset_expr.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_parser.html b/LayoutTests/fast/xpath/4XPath/Core/test_parser.html
index 3c49923..82339e5 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_parser.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_parser.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_predicate_list.html b/LayoutTests/fast/xpath/4XPath/Core/test_predicate_list.html
index a8c1caf..5852b04 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_predicate_list.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_predicate_list.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_step-expected.txt b/LayoutTests/fast/xpath/4XPath/Core/test_step-expected.txt
index 9c94b2a..feb2e80 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_step-expected.txt
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_step-expected.txt
@@ -1,5 +1,5 @@
PASS ancestor::*
-FAIL ancestor-or-self::* item 0 incorrect (expected ROOT, actual CHILD1)
+PASS ancestor-or-self::*
PASS descendant-or-self::*
PASS child::GCHILD[position()=1]
PASS child::GCHILD[1]
diff --git a/LayoutTests/fast/xpath/4XPath/Core/test_step.html b/LayoutTests/fast/xpath/4XPath/Core/test_step.html
index 62f3c34..e90cb1d 100644
--- a/LayoutTests/fast/xpath/4XPath/Core/test_step.html
+++ b/LayoutTests/fast/xpath/4XPath/Core/test_step.html
@@ -4,6 +4,7 @@
<link rel="stylesheet" href="../../../js/resources/js-test-style.css">
<script src="../../../js/resources/js-test-pre.js"></script>
<script src="test.js"></script>
+<script src="../../xpath-test-pre.js"></script>
</head>
<body>
<div id="console"></div>
diff --git a/LayoutTests/fast/xpath/document-order-expected.txt b/LayoutTests/fast/xpath/document-order-expected.txt
new file mode 100644
index 0000000..5fe3954
--- /dev/null
+++ b/LayoutTests/fast/xpath/document-order-expected.txt
@@ -0,0 +1,31 @@
+PASS ancestor::* (context = attr1)
+PASS ancestor::* (context = GCHILD11)
+PASS ancestor::node() (context = attr1)
+PASS ancestor::node() (context = GCHILD11)
+PASS preceding::node() (context = attr4)
+PASS preceding::node() (context = CHILD2)
+PASS preceding::node() (context = GCHILD12)
+PASS following::node() (context = attr1)
+PASS following::node() (context = CHILD1)
+PASS following::node() (context = GCHILD11)
+PASS following::node() (context = CHILD2)
+PASS //CHILD | //@attr1
+PASS //CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31
+PASS (//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[3]
+PASS (//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[position() = last()]
+PASS //CHILD[2]/GCHILD | //CHILD[1]/GCHILD
+PASS doc.evaluate("string(//*[@name='GCHILD12'] | //CHILD | //@attr1 | //@attr31)", doc, null, XPathResult.STRING_TYPE, null).stringValue is "TEXT1"
+PASS descendant::node() (context = attr1)
+PASS child::node() (context = attr1)
+PASS parent::node() (context = attr1)
+PASS following-sibling::node() (context = attr1)
+PASS preceding-sibling::node() (context = attr4)
+PASS attribute::node() (context = attr1)
+PASS self::node() (context = attr1)
+PASS self::* (context = attr1)
+PASS descendant-or-self::node() (context = attr1)
+PASS ancestor-or-self::node() (context = attr1)
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
diff --git a/LayoutTests/fast/xpath/document-order.html b/LayoutTests/fast/xpath/document-order.html
new file mode 100644
index 0000000..10f89fb
--- /dev/null
+++ b/LayoutTests/fast/xpath/document-order.html
@@ -0,0 +1,173 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="../js/resources/js-test-style.css">
+<script src="../js/resources/js-test-pre.js"></script>
+<script src="xpath-test-pre.js"></script>
+</head>
+<body>
+<div id="console"></div>
+
+<script>
+doc = (new DOMParser).parseFromString(
+ '<doc>' +
+ '<CHILD attr1="val1" attr31="31">' +
+ '<GCHILD name="GCHILD11"/>' +
+ '<GCHILD name="GCHILD12"/>' +
+ 'TEXT1' +
+ '</CHILD>' +
+ '<CHILD attr4="4">' +
+ '<GCHILD name="GCHILD21"/>' +
+ '</CHILD>' +
+ '</doc>',
+ 'application/xml');
+
+CHILD1 = doc.getElementsByTagName("CHILD")[0];
+CHILD2 = doc.getElementsByTagName("CHILD")[1];
+attr1 = CHILD1.getAttributeNode("attr1");
+attr31 = CHILD1.getAttributeNode("attr31");
+attr4 = CHILD2.getAttributeNode("attr4");
+GCHILD11 = doc.getElementsByTagName("GCHILD")[0];
+GCHILD12 = doc.getElementsByTagName("GCHILD")[1];
+GCHILD21 = doc.getElementsByTagName("GCHILD")[2];
+TEXT1 = GCHILD12.nextSibling;
+
+
+result = doc.evaluate("ancestor::*", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("ancestor::* (context = attr1)",
+ result,
+ [doc.documentElement, CHILD1]);
+
+result = doc.evaluate("ancestor::*", GCHILD11, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("ancestor::* (context = GCHILD11)",
+ result,
+ [doc.documentElement, CHILD1]);
+
+result = doc.evaluate("ancestor::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("ancestor::node() (context = attr1)",
+ result,
+ [doc, doc.documentElement, CHILD1]);
+
+result = doc.evaluate("ancestor::node()", GCHILD11, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("ancestor::node() (context = GCHILD11)",
+ result,
+ [doc, doc.documentElement, CHILD1]);
+
+result = doc.evaluate("preceding::node()", attr4, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("preceding::node() (context = attr4)",
+ result,
+ [CHILD1, GCHILD11, GCHILD12, TEXT1]);
+
+result = doc.evaluate("preceding::node()", CHILD2, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("preceding::node() (context = CHILD2)",
+ result,
+ [CHILD1, GCHILD11, GCHILD12, TEXT1]);
+
+result = doc.evaluate("preceding::node()", GCHILD12, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("preceding::node() (context = GCHILD12)",
+ result,
+ [GCHILD11]);
+
+result = doc.evaluate("following::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("following::node() (context = attr1)",
+ result,
+ [GCHILD11, GCHILD12, TEXT1, CHILD2, GCHILD21]);
+
+result = doc.evaluate("following::node()", CHILD1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("following::node() (context = CHILD1)",
+ result,
+ [CHILD2, GCHILD21]);
+
+result = doc.evaluate("following::node()", GCHILD11, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("following::node() (context = GCHILD11)",
+ result,
+ [GCHILD12, TEXT1, CHILD2, GCHILD21]);
+
+result = doc.evaluate("following::node()", CHILD2, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("following::node() (context = CHILD2)",
+ result,
+ []);
+
+result = doc.evaluate("//CHILD | //@attr1", doc, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("//CHILD | //@attr1",
+ result,
+ [CHILD1, attr1, CHILD2]);
+
+result = doc.evaluate("//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31", doc, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31",
+ result,
+ [CHILD1, attr1, attr31, GCHILD12, CHILD2]);
+
+result = doc.evaluate("(//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[3]", doc, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("(//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[3]",
+ result,
+ [attr31]);
+
+result = doc.evaluate("(//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[position() = last()]", doc, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("(//CHILD | //@attr1 | //*[@name='GCHILD12'] | //@attr31)[position() = last()]",
+ result,
+ [CHILD2]);
+
+result = doc.evaluate("//CHILD[2]/GCHILD | //CHILD[1]/GCHILD", doc, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("//CHILD[2]/GCHILD | //CHILD[1]/GCHILD",
+ result,
+ [GCHILD11, GCHILD12, GCHILD21]);
+
+shouldBe('doc.evaluate("string(//*[@name=\'GCHILD12\'] | //CHILD | //@attr1 | //@attr31)", doc, null, XPathResult.STRING_TYPE, null).stringValue', '"TEXT1"');
+
+result = doc.evaluate("descendant::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("descendant::node() (context = attr1)",
+ result,
+ []);
+
+result = doc.evaluate("child::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("child::node() (context = attr1)",
+ result,
+ []);
+
+result = doc.evaluate("parent::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("parent::node() (context = attr1)",
+ result,
+ [CHILD1]);
+
+result = doc.evaluate("following-sibling::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("following-sibling::node() (context = attr1)",
+ result,
+ []);
+
+result = doc.evaluate("preceding-sibling::node()", attr4, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("preceding-sibling::node() (context = attr4)",
+ result,
+ []);
+
+result = doc.evaluate("attribute::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("attribute::node() (context = attr1)",
+ result,
+ []);
+
+result = doc.evaluate("self::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("self::node() (context = attr1)",
+ result,
+ [attr1]);
+
+result = doc.evaluate("self::*", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("self::* (context = attr1)",
+ result,
+ []);
+
+result = doc.evaluate("descendant-or-self::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("descendant-or-self::node() (context = attr1)",
+ result,
+ [attr1]);
+
+result = doc.evaluate("ancestor-or-self::node()", attr1, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, null);
+checkSnapshot("ancestor-or-self::node() (context = attr1)",
+ result,
+ [doc, doc.documentElement, CHILD1, attr1]);
+
+var successfullyParsed = true;
+
+</script>
+<script src="../js/resources/js-test-post.js"></script>
+</body>
+</html>
diff --git a/LayoutTests/fast/xpath/text-nodes-expected.txt b/LayoutTests/fast/xpath/text-nodes-expected.txt
index 49880e8..a3cb54d 100644
--- a/LayoutTests/fast/xpath/text-nodes-expected.txt
+++ b/LayoutTests/fast/xpath/text-nodes-expected.txt
@@ -4,9 +4,9 @@
descendant::*, [object Element]: ""
descendant::node(), [object Element]: "a b c"
descendant::node()[2], [object Element]: "b"
-ancestor-or-self::node(), b: "b null null null"
+ancestor-or-self::node(), b: "null null null b"
ancestor-or-self::*, b: "null null"
-ancestor-or-self::node(), a: "a null null null"
+ancestor-or-self::node(), a: "null null null a"
ancestor-or-self::*, a: "null null"
following::node(), [object Element]: ""
following::node(), a: "b c"
@@ -18,9 +18,9 @@
following-sibling::node(), b: "c"
preceding::node(), b: "a"
preceding-sibling::node(), b: "a"
-preceding::node(), c: "b a"
-preceding::text(), c: "b a"
-preceding-sibling::node(), c: "b a"
-preceding-sibling::text(), c: "b a"
+preceding::node(), c: "a b"
+preceding::text(), c: "a b"
+preceding-sibling::node(), c: "a b"
+preceding-sibling::text(), c: "a b"
self::node(), b: "b"
diff --git a/LayoutTests/fast/xpath/text-nodes.html b/LayoutTests/fast/xpath/text-nodes.html
index 10ce9f3..96a9e38 100644
--- a/LayoutTests/fast/xpath/text-nodes.html
+++ b/LayoutTests/fast/xpath/text-nodes.html
@@ -30,9 +30,9 @@
test("descendant::*", elem);
test("descendant::node()", elem);
test("descendant::node()[2]", elem);
- test("ancestor-or-self::node()", bText); // the order of result nodes is incorrect in this test
+ test("ancestor-or-self::node()", bText);
test("ancestor-or-self::*", bText);
- test("ancestor-or-self::node()", aText); // the order of result nodes is incorrect in this test
+ test("ancestor-or-self::node()", aText);
test("ancestor-or-self::*", aText);
test("following::node()", elem);
test("following::node()", aText);
@@ -44,10 +44,10 @@
test("following-sibling::node()", bText);
test("preceding::node()", bText);
test("preceding-sibling::node()", bText);
- test("preceding::node()", cText); // the order of result nodes is incorrect in this test
- test("preceding::text()", cText); // the order of result nodes is incorrect in this test
- test("preceding-sibling::node()", cText); // the order of result nodes is incorrect in this test
- test("preceding-sibling::text()", cText); // the order of result nodes is incorrect in this test
+ test("preceding::node()", cText);
+ test("preceding::text()", cText);
+ test("preceding-sibling::node()", cText);
+ test("preceding-sibling::text()", cText);
test("self::node()", bText);
var successfullyParsed = true;
diff --git a/LayoutTests/fast/xpath/xpath-test-pre.js b/LayoutTests/fast/xpath/xpath-test-pre.js
new file mode 100644
index 0000000..604965e
--- /dev/null
+++ b/LayoutTests/fast/xpath/xpath-test-pre.js
@@ -0,0 +1,15 @@
+function checkSnapshot(comment, actual, expected) {
+ if (actual.snapshotLength != expected.length) {
+ testFailed(comment + " incorrect length (expected " + expected.length + ", actual " + actual.snapshotLength + ")");
+ return;
+ }
+
+ for (i = 0; i < actual.snapshotLength; ++i) {
+ if (actual.snapshotItem(i) != expected[i]) {
+ testFailed(comment + " item " + i + " incorrect (expected " + expected[i].nodeName + ", actual " + actual.snapshotItem(i).nodeName + ")");
+ return;
+ }
+ }
+
+ testPassed(comment);
+}
diff --git a/WebCore/CMakeLists.txt b/WebCore/CMakeLists.txt
index 7479b30..b50c66e 100644
--- a/WebCore/CMakeLists.txt
+++ b/WebCore/CMakeLists.txt
@@ -1206,6 +1206,7 @@
xml/XPathExpressionNode.cpp
xml/XPathFunctions.cpp
xml/XPathNamespace.cpp
+ xml/XPathNodeSet.cpp
xml/XPathNSResolver.cpp
xml/XPathParser.cpp
xml/XPathPath.cpp
diff --git a/WebCore/ChangeLog b/WebCore/ChangeLog
index def9b3f..5b9eb02 100644
--- a/WebCore/ChangeLog
+++ b/WebCore/ChangeLog
@@ -1,3 +1,103 @@
+2007-03-20 Alexey Proskuryakov <ap@webkit.org>
+
+ Reviewed by Darin.
+
+ http://bugs.webkit.org/show_bug.cgi?id=12497
+ Implement XPath result ordering.
+
+ XPath::NodeVector typedef is replaced with a real XPath::NodeSet class that knows how
+ to sort itself, and can remember whether it has been already sorted.
+
+ * CMakeLists.txt:
+ * WebCore.pro:
+ * WebCore.xcodeproj/project.pbxproj:
+ * WebCoreSources.bkl:
+ Added XPathNodeSet files.
+
+ * xml/XPathExpression.cpp: Fixed includes.
+
+ * xml/XPathFunctions.cpp:
+ (WebCore::XPath::FunId::evaluate): Mark the resulting node-set as unsorted.
+ (WebCore::XPath::FunLocalName::evaluate): Replacing NodeVector with NodeSet.
+ (WebCore::XPath::FunNamespaceURI::evaluate): Ditto.
+ (WebCore::XPath::FunName::evaluate): Ditto.
+ (WebCore::XPath::FunCount::evaluate): Ditto.
+ (WebCore::XPath::FunSum::evaluate): Ditto.
+
+ * xml/XPathNodeSet.cpp: Added.
+ (WebCore::XPath::parentWithDepth):
+ (WebCore::XPath::sortBlock):
+ (WebCore::XPath::NodeSet::sort): Sort the node-set in document order.
+ (WebCore::XPath::NodeSet::reverse): Reverse the order (useful for making axes such as
+ parent or ancestor sorted).
+ (WebCore::XPath::NodeSet::firstNode): Returns the first node in document order; currently
+ implemented via fully sorting the node-set, but this can obviously be optimized.
+ (WebCore::XPath::NodeSet::anyNode): Added for symmetry with firstNode().
+
+ * xml/XPathNodeSet.h: Added.
+ (WebCore::XPath::NodeSet::NodeSet):
+ (WebCore::XPath::NodeSet::operator=):
+ (WebCore::XPath::NodeSet::size):
+ (WebCore::XPath::NodeSet::isEmpty):
+ (WebCore::XPath::NodeSet::operator[]):
+ (WebCore::XPath::NodeSet::reserveCapacity):
+ (WebCore::XPath::NodeSet::clear):
+ (WebCore::XPath::NodeSet::swap):
+ (WebCore::XPath::NodeSet::append):
+ (WebCore::XPath::NodeSet::markSorted):
+ (WebCore::XPath::NodeSet::isSorted):
+ Most of these methods just call Vector counterparts.
+
+ * xml/XPathParser.cpp: Updated the copyright notice.
+
+ * xml/XPathPath.cpp:
+ (WebCore::XPath::Filter::evaluate): Replacing NodeVector with NodeSet.
+ (WebCore::XPath::Path::evaluate): Ditto.
+ (WebCore::XPath::LocationPath::evaluate): Replacing NodeVector with NodeSet. This function
+ always marks the result as unsorted, because it is hard to tell whether a step breaks node order.
+ Identifying and implementing special cases when it is not necessary to do so is an important
+ future optimization.
+
+ * xml/XPathPath.h: Replacing NodeVector with NodeSet.
+ * xml/XPathPredicate.cpp:
+ (WebCore::XPath::EqTestOp::compare): Replacing NodeVector with NodeSet.
+ (WebCore::XPath::Union::evaluate): Replacing NodeVector with NodeSet. Currently, Union just
+ marks the result as unordered; we can consider using merge sort to avoid this.
+
+ * xml/XPathResult.cpp:
+ (WebCore::XPathResult::XPathResult): Replacing NodeVector with NodeSet.
+ (WebCore::XPathResult::singleNodeValue): Ditto.
+ (WebCore::XPathResult::snapshotLength): Ditto.
+ (WebCore::XPathResult::iterateNext): Ditto.
+ (WebCore::XPathResult::snapshotItem): Ditto.
+ (WebCore::XPathResult::convertTo): Ditto. Sort the result when requested to.
+
+ * xml/XPathResult.h: Replacing NodeVector with NodeSet.
+
+ * xml/XPathStep.cpp:
+ (WebCore::XPath::Step::evaluate): If the input is not sorted, mark the output as such, too.
+ (WebCore::XPath::Step::nodesInAxis): Fixed a number of bugs when enumerating with an
+ attribute context node.
+ (WebCore::XPath::Step::nodeTestMatches): Replacing NodeVector with NodeSet.
+ * xml/XPathStep.h: Ditto.
+
+ * xml/XPathUtil.cpp:
+ (WebCore::XPath::isValidContextNode): XPath data model doesn't put attribute data into child
+ nodes, so passing such node as a context could cause problems.
+
+ * xml/XPathUtil.h: Removed NodeVector typedef.
+
+ * xml/XPathValue.cpp:
+ (WebCore::XPath::Value::Value):
+ (WebCore::XPath::Value::toNodeSet):
+ (WebCore::XPath::Value::toBoolean):
+ (WebCore::XPath::Value::toNumber):
+ (WebCore::XPath::Value::toString):
+ * xml/XPathValue.h:
+ (WebCore::XPath::Value::):
+ (WebCore::XPath::Value::isNodeSet):
+ Replacing NodeVector with NodeSet.
+
2007-03-21 Mark Rowe <mrowe@apple.com>
Build fix.
diff --git a/WebCore/WebCore.pro b/WebCore/WebCore.pro
index c835955..4ecd6b1 100644
--- a/WebCore/WebCore.pro
+++ b/WebCore/WebCore.pro
@@ -694,6 +694,7 @@
xml/XPathExpressionNode.cpp \
xml/XPathFunctions.cpp \
xml/XPathNamespace.cpp \
+ xml/XPathNodeSet.cpp \
xml/XPathNSResolver.cpp \
xml/XPathParser.cpp \
xml/XPathPath.cpp \
diff --git a/WebCore/WebCore.xcodeproj/project.pbxproj b/WebCore/WebCore.xcodeproj/project.pbxproj
index 0c1c2c3..26c1992 100644
--- a/WebCore/WebCore.xcodeproj/project.pbxproj
+++ b/WebCore/WebCore.xcodeproj/project.pbxproj
@@ -2898,6 +2898,8 @@
E1E6EEA40B628DA8005F2F70 /* JSHTMLSelectElement.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E1E6EEA30B628DA8005F2F70 /* JSHTMLSelectElement.cpp */; };
E1E6EEA80B628DB3005F2F70 /* JSHTMLSelectElement.h in Headers */ = {isa = PBXBuildFile; fileRef = E1E6EEA70B628DB3005F2F70 /* JSHTMLSelectElement.h */; };
E1EBBBD40AAC9B87001FE8E2 /* CSSCharsetRule.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E1EBBBD30AAC9B87001FE8E2 /* CSSCharsetRule.cpp */; };
+ E1EC299F0BB04C6B00EA187B /* XPathNodeSet.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E1EC299D0BB04C6B00EA187B /* XPathNodeSet.cpp */; };
+ E1EC29A00BB04C6B00EA187B /* XPathNodeSet.h in Headers */ = {isa = PBXBuildFile; fileRef = E1EC299E0BB04C6B00EA187B /* XPathNodeSet.h */; };
E1F0424609839389006694EA /* xmlhttprequest.cpp in Sources */ = {isa = PBXBuildFile; fileRef = E1F0424409839389006694EA /* xmlhttprequest.cpp */; };
E1F0424709839389006694EA /* xmlhttprequest.h in Headers */ = {isa = PBXBuildFile; fileRef = E1F0424509839389006694EA /* xmlhttprequest.h */; };
ED048ABC0833F132006E1E67 /* textAreaResizeCorner.tiff in Resources */ = {isa = PBXBuildFile; fileRef = ED048ABB0833F132006E1E67 /* textAreaResizeCorner.tiff */; };
@@ -6109,6 +6111,8 @@
E1E6EEA30B628DA8005F2F70 /* JSHTMLSelectElement.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = JSHTMLSelectElement.cpp; sourceTree = "<group>"; };
E1E6EEA70B628DB3005F2F70 /* JSHTMLSelectElement.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.h; path = JSHTMLSelectElement.h; sourceTree = "<group>"; };
E1EBBBD30AAC9B87001FE8E2 /* CSSCharsetRule.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = CSSCharsetRule.cpp; sourceTree = "<group>"; };
+ E1EC299D0BB04C6B00EA187B /* XPathNodeSet.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = XPathNodeSet.cpp; sourceTree = "<group>"; };
+ E1EC299E0BB04C6B00EA187B /* XPathNodeSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = XPathNodeSet.h; sourceTree = "<group>"; };
E1F0424409839389006694EA /* xmlhttprequest.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = xmlhttprequest.cpp; sourceTree = "<group>"; };
E1F0424509839389006694EA /* xmlhttprequest.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = xmlhttprequest.h; sourceTree = "<group>"; };
ED048ABB0833F132006E1E67 /* textAreaResizeCorner.tiff */ = {isa = PBXFileReference; lastKnownFileType = image.tiff; path = textAreaResizeCorner.tiff; sourceTree = "<group>"; };
@@ -9278,6 +9282,8 @@
1AB7FC510A8B92EC00D9D37B /* XPathGrammar.y */,
1AB7FC520A8B92EC00D9D37B /* XPathNamespace.cpp */,
1AB7FC530A8B92EC00D9D37B /* XPathNamespace.h */,
+ E1EC299D0BB04C6B00EA187B /* XPathNodeSet.cpp */,
+ E1EC299E0BB04C6B00EA187B /* XPathNodeSet.h */,
1AB7FC540A8B92EC00D9D37B /* XPathNSResolver.cpp */,
1AB7FC550A8B92EC00D9D37B /* XPathNSResolver.h */,
1AB7FC560A8B92EC00D9D37B /* XPathNSResolver.idl */,
@@ -11244,6 +11250,7 @@
93F9B7750BA5FDDD00854064 /* JSEntityReference.h in Headers */,
93F9B7A10BA6032600854064 /* JSCDATASection.h in Headers */,
06FC442E0BAE5A9E0090EDE1 /* JavaScriptStatistics.h in Headers */,
+ E1EC29A00BB04C6B00EA187B /* XPathNodeSet.h in Headers */,
);
runOnlyForDeploymentPostprocessing = 0;
};
@@ -12613,6 +12620,7 @@
93F9B7740BA5FDDC00854064 /* JSEntityReference.cpp in Sources */,
93F9B7A00BA6032600854064 /* JSCDATASection.cpp in Sources */,
06FC442D0BAE5A9E0090EDE1 /* JavaScriptStatistics.cpp in Sources */,
+ E1EC299F0BB04C6B00EA187B /* XPathNodeSet.cpp in Sources */,
);
runOnlyForDeploymentPostprocessing = 0;
};
diff --git a/WebCore/WebCoreSources.bkl b/WebCore/WebCoreSources.bkl
index 0f88a03..17ebafe 100644
--- a/WebCore/WebCoreSources.bkl
+++ b/WebCore/WebCoreSources.bkl
@@ -502,8 +502,9 @@
xml/XPathExpression.cpp
xml/XPathExpressionNode.cpp
xml/XPathFunctions.cpp
- xml/XPathNSResolver.cpp
xml/XPathNamespace.cpp
+ xml/XPathNodeSet.cpp
+ xml/XPathNSResolver.cpp
xml/XPathParser.cpp
xml/XPathPath.cpp
xml/XPathPredicate.cpp
diff --git a/WebCore/xml/XPathExpression.cpp b/WebCore/xml/XPathExpression.cpp
index 9231001..e59a2c6 100644
--- a/WebCore/xml/XPathExpression.cpp
+++ b/WebCore/xml/XPathExpression.cpp
@@ -29,15 +29,15 @@
#if ENABLE(XPATH)
-#include "PlatformString.h"
#include "Document.h"
+#include "ExceptionCode.h"
#include "Node.h"
+#include "PlatformString.h"
+#include "XPathExpressionNode.h"
#include "XPathNSResolver.h"
#include "XPathParser.h"
#include "XPathResult.h"
-#include "ExceptionCode.h"
-
-#include "XPathExpressionNode.h"
+#include "XPathUtil.h"
namespace WebCore {
diff --git a/WebCore/xml/XPathFunctions.cpp b/WebCore/xml/XPathFunctions.cpp
index c5003d7..0fd6365 100644
--- a/WebCore/xml/XPathFunctions.cpp
+++ b/WebCore/xml/XPathFunctions.cpp
@@ -33,6 +33,7 @@
#include "Document.h"
#include "NamedAttrMap.h"
#include "XMLNames.h"
+#include "XPathUtil.h"
#include "XPathValue.h"
#include <wtf/MathExtras.h>
@@ -262,15 +263,13 @@
Value FunId::evaluate() const
{
- // FIXME: this algorithm does not produce an ordered node-set, as it should.
-
Value a = arg(0)->evaluate();
Vector<UChar> idList; // A whitespace-separated list of IDs
- if (a.isNodeVector()) {
- const NodeVector& nodes = a.toNodeVector();
+ if (a.isNodeSet()) {
+ const NodeSet& nodes = a.toNodeSet();
for (size_t i = 0; i < nodes.size(); ++i) {
- String str = stringValue(nodes[i].get());
+ String str = stringValue(nodes[i]);
idList.append(str.characters(), str.length());
idList.append(' ');
}
@@ -280,7 +279,7 @@
}
Document* contextDocument = evaluationContext().node->document();
- NodeVector result;
+ NodeSet result;
HashSet<Node*> resultSet;
size_t startPos = 0;
@@ -305,6 +304,8 @@
startPos = endPos;
}
+ result.markSorted(false);
+
return result;
}
@@ -313,10 +314,12 @@
Node* node = 0;
if (argCount() > 0) {
Value a = arg(0)->evaluate();
- if (!a.isNodeVector() || a.toNodeVector().size() == 0)
+ if (!a.isNodeSet())
return "";
-
- node = a.toNodeVector()[0].get();
+
+ node = a.toNodeSet().firstNode();
+ if (!node)
+ return "";
}
if (!node)
@@ -330,10 +333,12 @@
Node* node = 0;
if (argCount() > 0) {
Value a = arg(0)->evaluate();
- if (!a.isNodeVector() || a.toNodeVector().size() == 0)
+ if (!a.isNodeSet())
return "";
- node = a.toNodeVector()[0].get();
+ node = a.toNodeSet().firstNode();
+ if (!node)
+ return "";
}
if (!node)
@@ -347,10 +352,12 @@
Node* node = 0;
if (argCount() > 0) {
Value a = arg(0)->evaluate();
- if (!a.isNodeVector() || a.toNodeVector().size() == 0)
+ if (!a.isNodeSet())
return "";
- node = a.toNodeVector()[0].get();
+ node = a.toNodeSet().firstNode();
+ if (!node)
+ return "";
}
if (!node)
@@ -364,10 +371,10 @@
{
Value a = arg(0)->evaluate();
- if (!a.isNodeVector())
+ if (!a.isNodeSet())
return 0.0;
- return a.toNodeVector().size();
+ return a.toNodeSet().size();
}
Value FunString::evaluate() const
@@ -570,14 +577,16 @@
Value FunSum::evaluate() const
{
Value a = arg(0)->evaluate();
- if (!a.isNodeVector())
+ if (!a.isNodeSet())
return 0.0;
double sum = 0.0;
- NodeVector nodes = a.toNodeVector();
-
+ const NodeSet& nodes = a.toNodeSet();
+ // To be really compliant, we should sort the node-set, as floating point addition is not associative.
+ // However, this is unlikely to ever become a practical issue, and sorting is slow.
+
for (unsigned i = 0; i < nodes.size(); i++)
- sum += Value(stringValue(nodes[i].get())).toNumber();
+ sum += Value(stringValue(nodes[i])).toNumber();
return sum;
}
diff --git a/WebCore/xml/XPathNodeSet.cpp b/WebCore/xml/XPathNodeSet.cpp
new file mode 100644
index 0000000..e29c096
--- /dev/null
+++ b/WebCore/xml/XPathNodeSet.cpp
@@ -0,0 +1,206 @@
+/*
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "config.h"
+
+#if ENABLE(XPATH)
+#include "XPathNodeSet.h"
+
+#include "Attr.h"
+#include "Element.h"
+#include "Node.h"
+
+namespace WebCore {
+namespace XPath {
+
+static inline Node* parentWithDepth(unsigned depth, const Vector<Node*>& parents)
+{
+ ASSERT(parents.size() >= depth + 1);
+ return parents[parents.size() - 1 - depth];
+}
+
+static void sortBlock(unsigned from, unsigned to, Vector<Vector<Node*> >& parentMatrix, bool mayContainAttributeNodes)
+{
+ ASSERT(from + 1 < to); // Should not call this function with less that two nodes to sort.
+ unsigned minDepth = UINT_MAX;
+ for (unsigned i = from; i < to; ++i) {
+ unsigned depth = parentMatrix[i].size() - 1;
+ if (minDepth > depth)
+ minDepth = depth;
+ }
+
+ // Find the common ancestor.
+ unsigned commonAncestorDepth = minDepth;
+ Node* commonAncestor;
+ while (true) {
+ commonAncestor = parentWithDepth(commonAncestorDepth, parentMatrix[from]);
+ if (commonAncestorDepth == 0)
+ break;
+
+ bool allEqual = true;
+ for (unsigned i = from + 1; i < to; ++i) {
+ if (commonAncestor != parentWithDepth(commonAncestorDepth, parentMatrix[i])) {
+ allEqual = false;
+ break;
+ }
+ }
+ if (allEqual)
+ break;
+
+ --commonAncestorDepth;
+ }
+
+ if (commonAncestorDepth == minDepth) {
+ // One of the nodes is the common ancestor => it is the first in document order.
+ // Find it and move it to the beginning.
+ for (unsigned i = from; i < to; ++i)
+ if (commonAncestor == parentMatrix[i][0]) {
+ parentMatrix[i].swap(parentMatrix[from]);
+ if (from + 2 < to)
+ sortBlock(from + 1, to, parentMatrix, mayContainAttributeNodes);
+ return;
+ }
+ }
+
+ if (mayContainAttributeNodes && commonAncestor->isElementNode()) {
+ // The attribute nodes and namespace nodes of an element occur before the children of the element.
+ // The namespace nodes are defined to occur before the attribute nodes.
+ // The relative order of namespace nodes is implementation-dependent.
+ // The relative order of attribute nodes is implementation-dependent.
+ unsigned sortedEnd = from;
+ // FIXME: namespace nodes are not implemented.
+ for (unsigned i = sortedEnd; i < to; ++i) {
+ Node* n = parentMatrix[i][0];
+ if (n->isAttributeNode() && static_cast<Attr*>(n)->ownerElement() == commonAncestor)
+ parentMatrix[i].swap(parentMatrix[sortedEnd++]);
+ }
+ if (sortedEnd != from) {
+ if (to - sortedEnd > 1)
+ sortBlock(sortedEnd, to, parentMatrix, mayContainAttributeNodes);
+ return;
+ }
+ }
+
+ // Children nodes of the common ancestor induce a subdivision of our node-set.
+ // Sort it according to this subdivision, and recursively sort each group.
+ HashSet<Node*> parentNodes;
+ for (unsigned i = from; i < to; ++i)
+ parentNodes.add(parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]));
+
+ unsigned previousGroupEnd = from;
+ unsigned groupEnd = from;
+ for (Node* n = commonAncestor->firstChild(); n; n = n->nextSibling()) {
+ // If parentNodes contains the node, perform a linear search to move its children in the node-set to the beginning.
+ if (parentNodes.contains(n)) {
+ for (unsigned i = groupEnd; i < to; ++i)
+ if (parentWithDepth(commonAncestorDepth + 1, parentMatrix[i]) == n)
+ parentMatrix[i].swap(parentMatrix[groupEnd++]);
+
+ if (groupEnd - previousGroupEnd > 1)
+ sortBlock(previousGroupEnd, groupEnd, parentMatrix, mayContainAttributeNodes);
+
+ ASSERT(previousGroupEnd != groupEnd);
+ previousGroupEnd = groupEnd;
+#ifndef NDEBUG
+ parentNodes.remove(n);
+#endif
+ }
+ }
+
+ ASSERT(parentNodes.isEmpty());
+}
+
+void NodeSet::sort() const
+{
+ if (m_isSorted)
+ return;
+
+ unsigned nodeCount = m_nodes.size();
+ if (nodeCount < 2) {
+ const_cast<bool&>(m_isSorted) = true;
+ return;
+ }
+
+ bool containsAttributeNodes = false;
+
+ Vector<Vector<Node*> > parentMatrix(nodeCount);
+ for (unsigned i = 0; i < nodeCount; ++i) {
+ Vector<Node*>& parentsVector = parentMatrix[i];
+ Node* n = m_nodes[i].get();
+ parentsVector.append(n);
+ if (n->isAttributeNode()) {
+ n = static_cast<Attr*>(n)->ownerElement();
+ parentsVector.append(n);
+ containsAttributeNodes = true;
+ }
+ while ((n = n->parent()))
+ parentsVector.append(n);
+ }
+ sortBlock(0, nodeCount, parentMatrix, containsAttributeNodes);
+
+ // It is not possible to just assign the result to m_nodes, because some nodes may get dereferenced and destroyed.
+ Vector<RefPtr<Node> > sortedNodes;
+ sortedNodes.reserveCapacity(nodeCount);
+ for (unsigned i = 0; i < nodeCount; ++i)
+ sortedNodes.append(parentMatrix[i][0]);
+
+ const_cast<Vector<RefPtr<Node> >& >(m_nodes).swap(sortedNodes);
+}
+
+void NodeSet::reverse()
+{
+ if (m_nodes.isEmpty())
+ return;
+
+ unsigned from = 0;
+ unsigned to = m_nodes.size() - 1;
+ while (from < to) {
+ m_nodes[from].swap(m_nodes[to]);
+ ++from;
+ --to;
+ }
+}
+
+Node* NodeSet::firstNode() const
+{
+ if (isEmpty())
+ return 0;
+
+ sort(); // FIXME: fully sorting the node-set just to find its first node is wasteful.
+ return m_nodes.at(0).get();
+}
+
+Node* NodeSet::anyNode() const
+{
+ if (isEmpty())
+ return 0;
+
+ return m_nodes.at(0).get();
+}
+
+}
+}
+
+#endif // ENABLE(XPATH)
diff --git a/WebCore/xml/XPathNodeSet.h b/WebCore/xml/XPathNodeSet.h
new file mode 100644
index 0000000..e24b844
--- /dev/null
+++ b/WebCore/xml/XPathNodeSet.h
@@ -0,0 +1,82 @@
+/*
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
+ * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
+ * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
+ * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef XPathNodeSet_h
+#define XPathNodeSet_h
+
+#if ENABLE(XPATH)
+
+#include <wtf/Vector.h>
+#include <wtf/Forward.h>
+
+#include "Node.h"
+
+namespace WebCore {
+
+ namespace XPath {
+
+ class NodeSet {
+ public:
+
+ NodeSet() : m_isSorted(true) {}
+ NodeSet(const NodeSet& other) : m_isSorted(other.m_isSorted), m_nodes(other.m_nodes) {}
+ NodeSet& operator=(const NodeSet& other) { m_isSorted = other.m_isSorted; m_nodes = other.m_nodes; return *this; }
+
+ size_t size() const { return m_nodes.size(); }
+ bool isEmpty() const { return !m_nodes.size(); }
+ Node* operator[](unsigned i) const { return m_nodes.at(i).get(); }
+ void reserveCapacity(size_t newCapacity) { m_nodes.reserveCapacity(newCapacity); }
+ void clear() { m_nodes.resize(0); }
+ void swap(NodeSet& other) { std::swap(m_isSorted, other.m_isSorted); m_nodes.swap(other.m_nodes); }
+
+ // NodeSet itself does not verify that nodes in it are unique.
+ void append(Node* node) { m_nodes.append(node); }
+ void append(PassRefPtr<Node> node) { m_nodes.append(node); }
+ void append(const NodeSet& nodeSet) { m_nodes.append(nodeSet.m_nodes); }
+
+ // Returns the set's first node in document order, or 0 if the set is empty.
+ Node* firstNode() const;
+
+ // Returns 0 if the set is empty.
+ Node* anyNode() const;
+
+ // NodeSet itself doesn't check if it is contains sorted data - the caller should tell it if it does not.
+ void markSorted(bool isSorted) { m_isSorted = isSorted; }
+ bool isSorted() const { return m_isSorted; }
+
+ void sort() const;
+
+ void reverse();
+
+ private:
+ bool m_isSorted;
+ Vector<RefPtr<Node> > m_nodes;
+ };
+
+ }
+}
+
+#endif // ENABLE(XPATH)
+#endif // XPathNodeSet_h
diff --git a/WebCore/xml/XPathParser.cpp b/WebCore/xml/XPathParser.cpp
index 96e1b8b..0e1fbec 100644
--- a/WebCore/xml/XPathParser.cpp
+++ b/WebCore/xml/XPathParser.cpp
@@ -1,6 +1,7 @@
/*
* Copyright 2005 Maksim Orlovich <maksim@kde.org>
* Copyright (C) 2006 Apple Computer, Inc.
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
diff --git a/WebCore/xml/XPathPath.cpp b/WebCore/xml/XPathPath.cpp
index 162e676..35445ba 100644
--- a/WebCore/xml/XPathPath.cpp
+++ b/WebCore/xml/XPathPath.cpp
@@ -1,6 +1,7 @@
/*
* Copyright 2005 Frerich Raabe <raabe@kde.org>
* Copyright (C) 2006 Apple Computer, Inc.
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -52,19 +53,20 @@
{
Value v = m_expr->evaluate();
- if (!v.isNodeVector())
+ if (!v.isNodeSet())
return v;
- NodeVector nodes = v.toNodeVector();
+ NodeSet nodes = v.toNodeSet();
+ nodes.sort();
EvaluationContext& evaluationContext = Expression::evaluationContext();
for (unsigned i = 0; i < m_predicates.size(); i++) {
- NodeVector newNodes;
+ NodeSet newNodes;
evaluationContext.size = nodes.size();
evaluationContext.position = 0;
for (unsigned j = 0; j < nodes.size(); j++) {
- Node* node = nodes[j].get();
+ Node* node = nodes[j];
evaluationContext.node = node;
++evaluationContext.position;
@@ -97,35 +99,36 @@
if (m_absolute && context->nodeType() != Node::DOCUMENT_NODE)
context = context->ownerDocument();
- NodeVector startNodes;
+ NodeSet startNodes;
startNodes.append(context);
return evaluate(startNodes);
}
-Value LocationPath::evaluate(const NodeVector& startNodes) const
+Value LocationPath::evaluate(const NodeSet& startNodes) const
{
- NodeVector inDOMNodes = startNodes;
+ NodeSet nodes = startNodes;
for (unsigned i = 0; i < m_steps.size(); i++) {
Step* step = m_steps[i];
- NodeVector outDOMNodes;
- HashSet<Node*> outDOMNodesSet;
+ NodeSet newNodes;
+ HashSet<Node*> newNodesSet;
- for (unsigned j = 0; j < inDOMNodes.size(); j++) {
- NodeVector matches = step->evaluate(inDOMNodes[j].get());
+ for (unsigned j = 0; j < nodes.size(); j++) {
+ NodeSet matches = step->evaluate(nodes[j]);
for (size_t nodeIndex = 0; nodeIndex < matches.size(); ++nodeIndex) {
- Node* node = matches[nodeIndex].get();
- if (outDOMNodesSet.add(node).second)
- outDOMNodes.append(node);
+ Node* node = matches[nodeIndex];
+ if (newNodesSet.add(node).second)
+ newNodes.append(node);
}
}
- inDOMNodes.swap(outDOMNodes);
+ nodes.swap(newNodes);
}
- return inDOMNodes;
+ nodes.markSorted(false);
+ return nodes;
}
void LocationPath::optimizeStepPair(unsigned index)
@@ -182,7 +185,7 @@
Value Path::evaluate() const
{
- return m_path->evaluate(m_filter->evaluate().toNodeVector());
+ return m_path->evaluate(m_filter->evaluate().toNodeSet());
}
}
diff --git a/WebCore/xml/XPathPath.h b/WebCore/xml/XPathPath.h
index b19130a..d12d562 100644
--- a/WebCore/xml/XPathPath.h
+++ b/WebCore/xml/XPathPath.h
@@ -30,7 +30,7 @@
#if ENABLE(XPATH)
#include "XPathExpressionNode.h"
-#include "XPathUtil.h"
+#include "XPathNodeSet.h"
int xpathyyparse(void*);
@@ -60,7 +60,7 @@
void setAbsolute(bool value) { m_absolute = value; }
virtual Value evaluate() const;
- Value evaluate(const NodeVector& startNodes) const;
+ Value evaluate(const NodeSet& startNodes) const;
void appendStep(Step* step);
void insertFirstStep(Step* step);
diff --git a/WebCore/xml/XPathPredicate.cpp b/WebCore/xml/XPathPredicate.cpp
index b31d2dd..8e819ed 100644
--- a/WebCore/xml/XPathPredicate.cpp
+++ b/WebCore/xml/XPathPredicate.cpp
@@ -1,6 +1,7 @@
/*
* Copyright 2005 Frerich Raabe <raabe@kde.org>
* Copyright (C) 2006 Apple Computer, Inc.
+ * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -32,6 +33,7 @@
#include "Node.h"
#include "XPathFunctions.h"
+#include "XPathUtil.h"
#include "XPathValue.h"
#include <math.h>
@@ -108,16 +110,16 @@
bool EqTestOp::compare(const Value& lhs, const Value& rhs) const
{
- if (lhs.isNodeVector()) {
- const NodeVector& lhsVector = lhs.toNodeVector();
- if (rhs.isNodeVector()) {
+ if (lhs.isNodeSet()) {
+ const NodeSet& lhsSet = lhs.toNodeSet();
+ if (rhs.isNodeSet()) {
// If both objects to be compared are node-sets, then the comparison will be true if and only if
// there is a node in the first node-set and a node in the second node-set such that the result of
// performing the comparison on the string-values of the two nodes is true.
- const NodeVector& rhsVector = rhs.toNodeVector();
- for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
- for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
- if (compare(stringValue(lhsVector[lindex].get()), stringValue(rhsVector[rindex].get())))
+ const NodeSet& rhsSet = rhs.toNodeSet();
+ for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
+ for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
+ if (compare(stringValue(lhsSet[lindex]), stringValue(rhsSet[rindex])))
return true;
return false;
}
@@ -125,8 +127,8 @@
// If one object to be compared is a node-set and the other is a number, then the comparison will be true
// if and only if there is a node in the node-set such that the result of performing the comparison on the number
// to be compared and on the result of converting the string-value of that node to a number using the number function is true.
- for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
- if (compare(Value(stringValue(lhsVector[lindex].get())).toNumber(), rhs))
+ for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
+ if (compare(Value(stringValue(lhsSet[lindex])).toNumber(), rhs))
return true;
return false;
}
@@ -134,8 +136,8 @@
// If one object to be compared is a node-set and the other is a string, then the comparison will be true
// if and only if there is a node in the node-set such that the result of performing the comparison on
// the string-value of the node and the other string is true.
- for (unsigned lindex = 0; lindex < lhsVector.size(); ++lindex)
- if (compare(stringValue(lhsVector[lindex].get()), rhs))
+ for (unsigned lindex = 0; lindex < lhsSet.size(); ++lindex)
+ if (compare(stringValue(lhsSet[lindex]), rhs))
return true;
return false;
}
@@ -147,17 +149,17 @@
}
ASSERT(0);
}
- if (rhs.isNodeVector()) {
- const NodeVector& rhsVector = rhs.toNodeVector();
+ if (rhs.isNodeSet()) {
+ const NodeSet& rhsSet = rhs.toNodeSet();
if (lhs.isNumber()) {
- for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
- if (compare(lhs, Value(stringValue(rhsVector[rindex].get())).toNumber()))
+ for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
+ if (compare(lhs, Value(stringValue(rhsSet[rindex])).toNumber()))
return true;
return false;
}
if (lhs.isString()) {
- for (unsigned rindex = 0; rindex < rhsVector.size(); ++rindex)
- if (compare(lhs, stringValue(rhsVector[rindex].get())))
+ for (unsigned rindex = 0; rindex < rhsSet.size(); ++rindex)
+ if (compare(lhs, stringValue(rhsSet[rindex])))
return true;
return false;
}
@@ -166,7 +168,7 @@
ASSERT(0);
}
- // Neither side is a NodeVector.
+ // Neither side is a NodeSet.
switch (m_opcode) {
case OP_EQ:
case OP_NE:
@@ -232,26 +234,27 @@
Value Union::evaluate() const
{
- // FIXME: This algorithm doesn't return nodes in document order, as it should.
Value lhs = subExpr(0)->evaluate();
Value rhs = subExpr(1)->evaluate();
- if (!lhs.isNodeVector() || !rhs.isNodeVector())
- return NodeVector();
+ if (!lhs.isNodeSet() || !rhs.isNodeSet())
+ return NodeSet();
- NodeVector lhsNodes = lhs.toNodeVector();
- NodeVector rhsNodes = rhs.toNodeVector();
- NodeVector result = lhsNodes;
+ NodeSet result = lhs.toNodeSet();
+ const NodeSet& rhsNodes = rhs.toNodeSet();
HashSet<Node*> nodes;
for (size_t i = 0; i < result.size(); ++i)
- nodes.add(result[i].get());
+ nodes.add(result[i]);
for (size_t i = 0; i < rhsNodes.size(); ++i) {
- Node* node = rhsNodes[i].get();
+ Node* node = rhsNodes[i];
if (nodes.add(node).second)
result.append(node);
}
-
+
+ // It is also possible to use merge sort to avoid making the result unsorted;
+ // but this would waste the time in cases when order is not important.
+ result.markSorted(false);
return result;
}
diff --git a/WebCore/xml/XPathResult.cpp b/WebCore/xml/XPathResult.cpp
index 9a5e8d7..daea517 100644
--- a/WebCore/xml/XPathResult.cpp
+++ b/WebCore/xml/XPathResult.cpp
@@ -63,10 +63,10 @@
case Value::StringValue:
m_resultType = STRING_TYPE;
return;
- case Value::NodeVectorValue:
+ case Value::NodeSetValue:
m_resultType = UNORDERED_NODE_ITERATOR_TYPE;
m_nodeSetPosition = 0;
- m_nodeSet = m_value.toNodeVector();
+ m_nodeSet = m_value.toNodeSet();
m_invalidIteratorState = false;
return;
}
@@ -97,16 +97,31 @@
m_value = m_value.toBoolean();
break;
case UNORDERED_NODE_ITERATOR_TYPE:
- case ORDERED_NODE_ITERATOR_TYPE:
case UNORDERED_NODE_SNAPSHOT_TYPE:
- case ORDERED_NODE_SNAPSHOT_TYPE:
case ANY_UNORDERED_NODE_TYPE:
- case FIRST_ORDERED_NODE_TYPE:
- if (!m_value.isNodeVector()) {
+ case FIRST_ORDERED_NODE_TYPE: // This is correct - singleNodeValue() will take care of ordering.
+ if (!m_value.isNodeSet()) {
ec = TYPE_ERR;
return;
}
m_resultType = type;
+ break;
+ case ORDERED_NODE_ITERATOR_TYPE:
+ if (!m_value.isNodeSet()) {
+ ec = TYPE_ERR;
+ return;
+ }
+ m_nodeSet.sort();
+ m_resultType = type;
+ break;
+ case ORDERED_NODE_SNAPSHOT_TYPE:
+ if (!m_value.isNodeSet()) {
+ ec = TYPE_ERR;
+ return;
+ }
+ m_value.toNodeSet().sort();
+ m_resultType = type;
+ break;
}
}
@@ -149,11 +164,11 @@
return 0;
}
- NodeVector nodes = m_value.toNodeVector();
- if (nodes.size () == 0)
- return 0;
-
- return nodes[0].get();
+ const NodeSet& nodes = m_value.toNodeSet();
+ if (resultType() == FIRST_ORDERED_NODE_TYPE)
+ return nodes.firstNode();
+ else
+ return nodes.anyNode();
}
void XPathResult::invalidateIteratorState()
@@ -183,7 +198,7 @@
return 0;
}
- return m_value.toNodeVector().size();
+ return m_value.toNodeSet().size();
}
Node* XPathResult::iterateNext(ExceptionCode& ec)
@@ -201,7 +216,7 @@
if (m_nodeSetPosition + 1 > m_nodeSet.size())
return 0;
- Node* node = m_nodeSet[m_nodeSetPosition].get();
+ Node* node = m_nodeSet[m_nodeSetPosition];
m_nodeSetPosition++;
@@ -215,11 +230,11 @@
return 0;
}
- NodeVector nodes = m_value.toNodeVector();
+ NodeSet nodes = m_value.toNodeSet();
if (index >= nodes.size())
return 0;
- return nodes[index].get();
+ return nodes[index];
}
}
diff --git a/WebCore/xml/XPathResult.h b/WebCore/xml/XPathResult.h
index b825082..fdea41a 100644
--- a/WebCore/xml/XPathResult.h
+++ b/WebCore/xml/XPathResult.h
@@ -78,7 +78,7 @@
private:
XPath::Value m_value;
unsigned m_nodeSetPosition;
- XPath::NodeVector m_nodeSet;
+ XPath::NodeSet m_nodeSet; // FIXME: why duplicate the node set stored in m_value?
unsigned short m_resultType;
bool m_invalidIteratorState;
RefPtr<EventTargetNode> m_eventTarget;
diff --git a/WebCore/xml/XPathStep.cpp b/WebCore/xml/XPathStep.cpp
index d03cac6..57f5335 100644
--- a/WebCore/xml/XPathStep.cpp
+++ b/WebCore/xml/XPathStep.cpp
@@ -34,6 +34,7 @@
#include "NamedAttrMap.h"
#include "XPathNSResolver.h"
#include "XPathParser.h"
+#include "XPathUtil.h"
namespace WebCore {
namespace XPath {
@@ -58,9 +59,9 @@
deleteAllValues(m_predicates);
}
-NodeVector Step::evaluate(Node* context) const
+NodeSet Step::evaluate(Node* context) const
{
- NodeVector nodes = nodesInAxis(context);
+ NodeSet nodes = nodesInAxis(context);
nodes = nodeTestMatches(nodes);
EvaluationContext& evaluationContext = Expression::evaluationContext();
@@ -68,11 +69,14 @@
for (unsigned i = 0; i < m_predicates.size(); i++) {
Predicate* predicate = m_predicates[i];
- NodeVector newNodes;
+ NodeSet newNodes;
+ if (!nodes.isSorted())
+ newNodes.markSorted(false);
+
evaluationContext.size = nodes.size();
evaluationContext.position = 1;
for (unsigned j = 0; j < nodes.size(); j++) {
- Node* node = nodes[j].get();
+ Node* node = nodes[j];
Expression::evaluationContext().node = node;
EvaluationContext backupCtx = evaluationContext;
@@ -88,32 +92,48 @@
return nodes;
}
-NodeVector Step::nodesInAxis(Node* context) const
+NodeSet Step::nodesInAxis(Node* context) const
{
- NodeVector nodes;
+ NodeSet nodes;
switch (m_axis) {
case ChildAxis:
+ if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
+ return nodes;
+
for (Node* n = context->firstChild(); n; n = n->nextSibling())
nodes.append(n);
return nodes;
- case DescendantAxis:
+ case DescendantAxis:
+ if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
+ return nodes;
+
for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
nodes.append(n);
return nodes;
- case ParentAxis: {
- Node* parent = context->parentNode();
- if (parent)
- nodes.append(parent);
+ case ParentAxis:
+ if (context->isAttributeNode())
+ nodes.append(static_cast<Attr*>(context)->ownerElement());
+ else {
+ Node* parent = context->parentNode();
+ if (parent)
+ nodes.append(parent);
+ }
+ return nodes;
+ case AncestorAxis: {
+ Node* n = context;
+ if (context->isAttributeNode()) {
+ n = static_cast<Attr*>(context)->ownerElement();
+ nodes.append(n);
+ }
+ for (n = n->parentNode(); n; n = n->parentNode())
+ nodes.append(n);
+ nodes.reverse();
return nodes;
}
- case AncestorAxis:
- for (Node* n = context->parentNode(); n; n = n->parentNode())
- nodes.append(n);
- return nodes;
case FollowingSiblingAxis:
if (context->nodeType() == Node::ATTRIBUTE_NODE ||
context->nodeType() == Node::XPATH_NAMESPACE_NODE)
- return NodeVector();
+ return nodes;
for (Node* n = context->nextSibling(); n; n = n->nextSibling())
nodes.append(n);
@@ -121,21 +141,32 @@
case PrecedingSiblingAxis:
if (context->nodeType() == Node::ATTRIBUTE_NODE ||
context->nodeType() == Node::XPATH_NAMESPACE_NODE)
- return NodeVector();
+ return nodes;
for (Node* n = context->previousSibling(); n; n = n->previousSibling())
nodes.append(n);
+
+ nodes.reverse();
return nodes;
- case FollowingAxis:
- for (Node *p = context; !isRootDomNode(p); p = p->parentNode()) {
- for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
- nodes.append(n);
- for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
- nodes.append(c);
+ case FollowingAxis:
+ if (context->isAttributeNode()) {
+ Node* p = static_cast<Attr*>(context)->ownerElement();
+ while ((p = p->traverseNextNode()))
+ nodes.append(p);
+ } else {
+ for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
+ for (Node* n = p->nextSibling(); n; n = n->nextSibling()) {
+ nodes.append(n);
+ for (Node* c = n->firstChild(); c; c = c->traverseNextNode(n))
+ nodes.append(c);
+ }
}
}
return nodes;
case PrecedingAxis:
+ if (context->isAttributeNode())
+ context = static_cast<Attr*>(context)->ownerElement();
+
for (Node* p = context; !isRootDomNode(p); p = p->parentNode()) {
for (Node* n = p->previousSibling(); n ; n = n->previousSibling()) {
nodes.append(n);
@@ -143,63 +174,77 @@
nodes.append(c);
}
}
+ nodes.markSorted(false);
return nodes;
case AttributeAxis: {
if (context->nodeType() != Node::ELEMENT_NODE)
- return NodeVector();
+ return nodes;
NamedAttrMap* attrs = context->attributes();
if (!attrs)
return nodes;
for (unsigned long i = 0; i < attrs->length(); ++i)
- nodes.append (attrs->item(i));
+ nodes.append(attrs->item(i));
return nodes;
}
case NamespaceAxis:
// XPath namespace nodes are not implemented yet.
- return NodeVector();
+ return nodes;
case SelfAxis:
nodes.append(context);
return nodes;
case DescendantOrSelfAxis:
nodes.append(context);
+ if (context->isAttributeNode()) // In XPath model, attribute nodes do not have children.
+ return nodes;
+
for (Node* n = context->firstChild(); n; n = n->traverseNextNode(context))
nodes.append(n);
return nodes;
- case AncestorOrSelfAxis:
+ case AncestorOrSelfAxis: {
nodes.append(context);
- for (Node* n = context->parentNode(); n; n = n->parentNode())
+ Node* n = context;
+ if (context->isAttributeNode()) {
+ n = static_cast<Attr*>(context)->ownerElement();
nodes.append(n);
+ }
+ for (n = n->parentNode(); n; n = n->parentNode())
+ nodes.append(n);
+
+ nodes.reverse();
return nodes;
+ }
}
ASSERT_NOT_REACHED();
- return NodeVector();
+ return nodes;
}
-NodeVector Step::nodeTestMatches(const NodeVector& nodes) const
+NodeSet Step::nodeTestMatches(const NodeSet& nodes) const
{
- NodeVector matches;
+ NodeSet matches;
+ if (!nodes.isSorted())
+ matches.markSorted(false);
switch (m_nodeTest.kind()) {
case NodeTest::TextNodeTest:
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
if ((node->nodeType() == Node::TEXT_NODE || node->nodeType() == Node::CDATA_SECTION_NODE))
matches.append(node);
}
return matches;
case NodeTest::CommentNodeTest:
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
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();
+ Node* node = nodes[i];
const String& name = m_nodeTest.data();
if (node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE && (name.isEmpty() || node->nodeName() == name))
matches.append(node);
@@ -207,7 +252,7 @@
return matches;
case NodeTest::ElementNodeTest:
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
if (node->isElementNode())
matches.append(node);
}
@@ -218,7 +263,7 @@
const String& name = m_nodeTest.data();
if (name == "*") {
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
if (node->nodeType() == primaryNodeType(m_axis) &&
(m_namespaceURI.isEmpty() || m_namespaceURI == node->namespaceURI()))
matches.append(node);
@@ -232,7 +277,7 @@
return matches;
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
if (node->nodeName() == name) {
matches.append(node);
@@ -245,7 +290,7 @@
// Node test on the namespace axis is not implemented yet
} else {
for (unsigned i = 0; i < nodes.size(); i++) {
- Node* node = nodes[i].get();
+ Node* node = nodes[i];
// We use tagQName here because we don't want the element name in uppercase
// like we get with HTML elements.
@@ -261,7 +306,7 @@
}
}
ASSERT_NOT_REACHED();
- return NodeVector();
+ return matches;
}
Node::NodeType Step::primaryNodeType(Axis axis) const
diff --git a/WebCore/xml/XPathStep.h b/WebCore/xml/XPathStep.h
index 8758867..59b3b0d 100644
--- a/WebCore/xml/XPathStep.h
+++ b/WebCore/xml/XPathStep.h
@@ -31,7 +31,7 @@
#include "Node.h"
#include "XPathExpressionNode.h"
-#include "XPathUtil.h"
+#include "XPathNodeSet.h"
namespace WebCore {
@@ -70,7 +70,7 @@
Step(Axis, const NodeTest& nodeTest, const String& namespaceURI, const Vector<Predicate*>& predicates = Vector<Predicate*>());
~Step();
- NodeVector evaluate(Node* context) const;
+ NodeSet evaluate(Node* context) const;
Axis axis() const { return m_axis; }
NodeTest nodeTest() const { return m_nodeTest; }
@@ -86,8 +86,8 @@
private:
void parseNodeTest(const String&);
- NodeVector nodesInAxis(Node* context) const;
- NodeVector nodeTestMatches(const NodeVector& nodes) const;
+ NodeSet nodesInAxis(Node* context) const;
+ NodeSet nodeTestMatches(const NodeSet& nodes) const;
String namespaceFromNodetest(const String& nodeTest) const;
Node::NodeType primaryNodeType(Axis) const;
diff --git a/WebCore/xml/XPathUtil.cpp b/WebCore/xml/XPathUtil.cpp
index c0cb812..a7cd21f 100644
--- a/WebCore/xml/XPathUtil.cpp
+++ b/WebCore/xml/XPathUtil.cpp
@@ -74,7 +74,8 @@
node->nodeType() == Node::PROCESSING_INSTRUCTION_NODE ||
node->nodeType() == Node::COMMENT_NODE ||
node->nodeType() == Node::DOCUMENT_NODE ||
- node->nodeType() == Node::XPATH_NAMESPACE_NODE);
+ node->nodeType() == Node::XPATH_NAMESPACE_NODE) &&
+ !(node->nodeType() == Node::TEXT_NODE && node->parentNode() && node->parentNode()->isAttributeNode());
}
}
diff --git a/WebCore/xml/XPathUtil.h b/WebCore/xml/XPathUtil.h
index bbab9fe..30f21ae 100644
--- a/WebCore/xml/XPathUtil.h
+++ b/WebCore/xml/XPathUtil.h
@@ -38,8 +38,6 @@
namespace XPath {
- typedef Vector<RefPtr<Node> > NodeVector;
-
/* @return whether the given node is the root node */
bool isRootDomNode(Node*);
diff --git a/WebCore/xml/XPathValue.cpp b/WebCore/xml/XPathValue.cpp
index 0a06773..d35231c 100644
--- a/WebCore/xml/XPathValue.cpp
+++ b/WebCore/xml/XPathValue.cpp
@@ -25,11 +25,13 @@
*/
#include "config.h"
+#include "XPathValue.h"
#if ENABLE(XPATH)
-#include "XPathValue.h"
#include "Node.h"
+#include "XPathUtil.h"
+
#include <wtf/MathExtras.h>
#include <math.h>
@@ -42,13 +44,13 @@
}
Value::Value(Node* value)
- : m_type(NodeVectorValue)
+ : m_type(NodeSetValue)
{
- m_nodeVector.append(value);
+ m_nodeSet.append(value);
}
-Value::Value(const NodeVector& value)
- : m_type(NodeVectorValue), m_nodeVector(value)
+Value::Value(const NodeSet& value)
+ : m_type(NodeSetValue), m_nodeSet(value)
{
}
@@ -82,16 +84,16 @@
{
}
-const NodeVector &Value::toNodeVector() const
+const NodeSet& Value::toNodeSet() const
{
- return m_nodeVector;
+ return m_nodeSet;
}
bool Value::toBoolean() const
{
switch (m_type) {
- case NodeVectorValue:
- return !m_nodeVector.isEmpty();
+ case NodeSetValue:
+ return !m_nodeSet.isEmpty();
case BooleanValue:
return m_bool;
case NumberValue:
@@ -106,7 +108,7 @@
double Value::toNumber() const
{
switch (m_type) {
- case NodeVectorValue:
+ case NodeSetValue:
return Value(toString()).toNumber();
case NumberValue:
return m_number;
@@ -127,10 +129,10 @@
String Value::toString() const
{
switch (m_type) {
- case NodeVectorValue:
- if (m_nodeVector.isEmpty())
+ case NodeSetValue:
+ if (m_nodeSet.isEmpty())
return "";
- return stringValue(m_nodeVector[0].get());
+ return stringValue(m_nodeSet.firstNode());
case StringValue:
return m_string;
case NumberValue:
diff --git a/WebCore/xml/XPathValue.h b/WebCore/xml/XPathValue.h
index aeeb021..1076ba3 100644
--- a/WebCore/xml/XPathValue.h
+++ b/WebCore/xml/XPathValue.h
@@ -30,7 +30,7 @@
#if ENABLE(XPATH)
#include "PlatformString.h"
-#include "XPathUtil.h"
+#include "XPathNodeSet.h"
namespace WebCore {
@@ -38,11 +38,11 @@
class Value {
public:
- enum Type { NodeVectorValue, BooleanValue, NumberValue, StringValue };
+ enum Type { NodeSetValue, BooleanValue, NumberValue, StringValue };
Value();
Value(Node*);
- Value(const NodeVector&);
+ Value(const NodeSet&);
Value(bool);
Value(unsigned);
Value(unsigned long);
@@ -52,19 +52,19 @@
Type type() const { return m_type; }
- bool isNodeVector() const { return m_type == NodeVectorValue; }
+ bool isNodeSet() const { return m_type == NodeSetValue; }
bool isBoolean() const { return m_type == BooleanValue; }
bool isNumber() const { return m_type == NumberValue; }
bool isString() const { return m_type == StringValue; }
- const NodeVector& toNodeVector() const;
+ const NodeSet& toNodeSet() const;
bool toBoolean() const;
double toNumber() const;
String toString() const;
private:
Type m_type;
- NodeVector m_nodeVector;
+ NodeSet m_nodeSet;
bool m_bool;
double m_number;
String m_string;
