From 72ec01c5f6d23405f30614d63fafa048279ca13d Mon Sep 17 00:00:00 2001 From: Arseny Kapoulkine Date: Sat, 18 Oct 2014 15:28:02 +0000 Subject: XPath: Extend the descendant-or-self optimization Use descendant-or-self::node() transformation for self, descendant and descendant-or-self axis. Self axis should be semi-frequent; descendant axes should not really be used with // but if they ever are the complexity of the step becomes quadratic so it's better to optimize this if possible. git-svn-id: https://pugixml.googlecode.com/svn/trunk@1063 99668b35-9821-0410-8761-19e4c4f06640 --- src/pugixml.cpp | 9 +++++++-- tests/test_xpath_paths.cpp | 15 +++++++++++++++ 2 files changed, 22 insertions(+), 2 deletions(-) diff --git a/src/pugixml.cpp b/src/pugixml.cpp index 71c3f5d..1d9dcfe 100644 --- a/src/pugixml.cpp +++ b/src/pugixml.cpp @@ -9613,12 +9613,17 @@ PUGI__NS_BEGIN // Replace descendant-or-self::node()/child::foo with descendant::foo // The former is a full form of //foo, the latter is much faster since it executes the node test immediately + // Do a similar kind of replacement for self/descendant/descendant-or-self axes // Note that we only replace positionally invariant steps (//foo[1] != /descendant::foo[1]) - if (_type == ast_step && _axis == axis_child && _left && + if (_type == ast_step && (_axis == axis_child || _axis == axis_self || _axis == axis_descendant || _axis == axis_descendant_or_self) && _left && _left->_type == ast_step && _left->_axis == axis_descendant_or_self && _left->_test == nodetest_type_node && !_left->_right && is_posinv_step()) { - _axis = axis_descendant; + if (_axis == axis_child || _axis == axis_descendant) + _axis = axis_descendant; + else + _axis = axis_descendant_or_self; + _left = _left->_left; } diff --git a/tests/test_xpath_paths.cpp b/tests/test_xpath_paths.cpp index 4528acd..b6f53c7 100644 --- a/tests/test_xpath_paths.cpp +++ b/tests/test_xpath_paths.cpp @@ -531,6 +531,21 @@ TEST_XML(xpath_paths_descendant_optimize, "") +{ + CHECK_XPATH_NODESET(doc, STR("//.")) % 1 % 2 % 3 % 4 % 5 % 6 % 7 % 8; + CHECK_XPATH_NODESET(doc, STR("//descendant::*")) % 2 % 3 % 4 % 5 % 6 % 7 % 8; + CHECK_XPATH_NODESET(doc, STR("//descendant-or-self::*")) % 2 % 3 % 4 % 5 % 6 % 7 % 8; + + CHECK_XPATH_NODESET(doc, STR("//..")) % 1 % 2 % 3 % 6; + CHECK_XPATH_NODESET(doc, STR("//ancestor::*")) % 2 % 3 % 6; + CHECK_XPATH_NODESET(doc, STR("//ancestor-or-self::*")) % 2 % 3 % 4 % 5 % 6 % 7 % 8; + CHECK_XPATH_NODESET(doc, STR("//preceding-sibling::*")) % 3 % 4 % 5; + CHECK_XPATH_NODESET(doc, STR("//following-sibling::*")) % 5 % 6 % 8; + CHECK_XPATH_NODESET(doc, STR("//preceding::*")) % 3 % 4 % 5 % 6 % 7; + CHECK_XPATH_NODESET(doc, STR("//following::*")) % 5 % 6 % 7 % 8; +} + TEST_XML(xpath_paths_descendant_optimize_last, "") { CHECK_XPATH_NODESET(doc, STR("//para[last()]")) % 6 % 7 % 8; -- cgit v1.2.3