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/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;
}
