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;