From 1b8b87904b0618f853345619e7ee2656cab80113 Mon Sep 17 00:00:00 2001
From: Arseny Kapoulkine <arseny.kapoulkine@gmail.com>
Date: Mon, 20 Oct 2014 01:00:48 +0000
Subject: XPath: Introduce _first/_any set evaluation modes

Sometimes when evaluating the node set we don't need the entire set and
only need the first element in docorder or any element. In the absence of
iterator support we can still use this information to short-circuit
traversals.

This does not have any effect on straightforward node collection queries,
but frequently improves performance of complex queries with predicates
etc. XMark benchmark gets 15x faster with some queries enjoying 100x
speedup on 10 Mb dataset due to a significant complexity improvement.

git-svn-id: https://pugixml.googlecode.com/svn/trunk@1067 99668b35-9821-0410-8761-19e4c4f06640
---
 tests/test_xpath.cpp       | 22 ++++++++++++++++++++++
 tests/test_xpath_paths.cpp | 22 ++++++++++++++++++++++
 2 files changed, 44 insertions(+)

(limited to 'tests')

diff --git a/tests/test_xpath.cpp b/tests/test_xpath.cpp
index f7da258..2143376 100644
--- a/tests/test_xpath.cpp
+++ b/tests/test_xpath.cpp
@@ -122,6 +122,28 @@ TEST_XML(xpath_sort_attributes, "<node/>")
 	xpath_node_set_tester(reverse_sorted, "reverse sorted order failed") % 5 % 4 % 3;
 }
 
+TEST(xpath_sort_random_medium)
+{
+	xml_document doc;
+	load_document_copy(doc, STR("<node>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("<child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2><child1 attr1='value1' attr2='value2'/><child2 attr1='value1'>test</child2>")
+		STR("</node>"));
+
+	xpath_node_set ns = doc.select_nodes(STR("//node() | //@*"));
+
+	std::vector<xpath_node> nsv(ns.begin(), ns.end());
+	std::random_shuffle(nsv.begin(), nsv.end());
+
+	xpath_node_set copy(&nsv[0], &nsv[0] + nsv.size());
+	copy.sort();
+
+	xpath_node_set_tester tester(copy, "sorted order failed");
+
+	for (unsigned int i = 2; i < 39; ++i) tester % i;
+}
+
 TEST(xpath_sort_random_large)
 {
 	xml_document doc;
diff --git a/tests/test_xpath_paths.cpp b/tests/test_xpath_paths.cpp
index b6f53c7..d791cdf 100644
--- a/tests/test_xpath_paths.cpp
+++ b/tests/test_xpath_paths.cpp
@@ -594,4 +594,26 @@ TEST_XML(xpath_paths_optimize_compare_attribute, "<node id='1' /><node id='2' />
 	CHECK_XPATH_NODESET(doc, STR("node[@xmlns = '3']"));
 }
 
+TEST_XML(xpath_paths_optimize_step_once, "<node><para1><para2/><para3/><para4><para5 attr5=''/></para4></para1><para6/></node>")
+{
+    CHECK_XPATH_BOOLEAN(doc, STR("node//para2/following::*"), true);
+    CHECK_XPATH_BOOLEAN(doc, STR("node//para6/following::*"), false);
+
+    CHECK_XPATH_STRING(doc, STR("name(node//para2/following::*)"), STR("para3"));
+    CHECK_XPATH_STRING(doc, STR("name(node//para6/following::*)"), STR(""));
+
+    CHECK_XPATH_BOOLEAN(doc, STR("node//para1/preceding::*"), false);
+    CHECK_XPATH_BOOLEAN(doc, STR("node//para6/preceding::*"), true);
+
+    CHECK_XPATH_STRING(doc, STR("name(node//para1/preceding::*)"), STR(""));
+    CHECK_XPATH_STRING(doc, STR("name(node//para6/preceding::*)"), STR("para1"));
+
+    CHECK_XPATH_BOOLEAN(doc, STR("node//para6/preceding::para4"), true);
+
+    CHECK_XPATH_BOOLEAN(doc, STR("//@attr5/ancestor-or-self::*"), true);
+    CHECK_XPATH_BOOLEAN(doc, STR("//@attr5/ancestor::*"), true);
+
+    CHECK_XPATH_BOOLEAN(doc, STR("//@attr5/following::para6"), true);
+    CHECK_XPATH_STRING(doc, STR("name(//@attr5/following::para6)"), STR("para6"));
+}
 #endif
-- 
cgit v1.2.3