Fix reverse sort in xpath_parser #251

tompng · 2025-04-30T18:21:46Z

The code below was failing with REXML::XPathParser#sort': undefined method '-@' for an instance of Array

d = REXML::Document.new("<a><b><c/><d/><x/></b><b><e/><x/></b></a>")
matches = REXML::XPath.match(d, "a/b/x/preceding-sibling::node()")
# Before: error
# After: [<e/>, <d/>, <c/>]

This pull request will fix it.

naitoh · 2025-05-01T15:45:50Z

Thanks.
However, there may be other problems, since more <d/> tags would increase the number of <c/> and <b/> tags.

After

$ irb
> $LOAD_PATH.unshift(File.expand_path("lib"))
> require 'rexml'
> REXML::XPath.match(REXML::Document.new("<a><b/><c/><d/></a>"), "/a/d/preceding::node()")
=> [<c/>, <b/>]
> REXML::XPath.match(REXML::Document.new("<a><b/><c/><d/><d/></a>"), "/a/d/preceding::node()")
=> [<d/>, <c/>, <c/>, <b/>, <b/>]
> REXML::XPath.match(REXML::Document.new("<a><b/><c/><d/><d/><d/></a>"), "/a/d/preceding::node()")
=> [<d/>, <d/>, <d/>, <c/>, <c/>, <c/>, <b/>, <b/>, <b/>]
> REXML::XPath.match(REXML::Document.new("<a><b/><c/><d/><d/><d/><d/></a>"), "/a/d/preceding::node()")
=> [<d/>, <d/>, <d/>, <d/>, <d/>, <d/>, <c/>, <c/>, <c/>, <c/>, <b/>, <b/>, <b/>, <b/>]

tompng · 2025-05-01T19:55:43Z

I think the duplicated match result is not related to this change.
To avoid adding a test case of questionable duplicated match result, I changed the test to use preceding-sibling.

d = REXML::Document.new("<a><b><c/><d/><x/></b><b><e/><x/></b></a>")
matches = REXML::XPath.match(d, "a/b/x/preceding-sibling::node()")
# Before: REXML::XPathParser#sort': undefined method '-@' for an instance of Array
# After: [<e/>, <d/>, <c/>]

naitoh · 2025-05-02T00:30:29Z

I think the duplicated match result is not related to this change.

I agree.
Thanks.

To avoid adding a test case of questionable duplicated match result, I changed the test to use preceding-sibling.

But, the response order is reversed from nokogiri and libxml, python(lxml).

@kou
Do you think the rexml responses is in the correct order? 🤔

$ irb -rnokogiri
> puts Nokogiri::HTML("<a><b><c/><d/><x/></b><b><e/><x/></b></a>").xpath( "//a/b/x/preceding-sibling::node()")
<c></c>
<d></d>
<e></e>

$ irb -rlibxml
> puts LibXML::XML::Document.string("<a><b><c/><d/><x/></b><b><e/><x/></b></a>").find("//a/b/x/preceding-sibling::node()").to_a
<c/>
<d/>
<e/>

https://programiz.pro/ide/python

from lxml import etree
print(etree.fromstring("<a><b><c/><d/><x/></b><b><e/><x/></b></a>").xpath('//a/b/x/preceding-sibling::node()'))

[<Element c at 0x7887f2cc7580>, <Element d at 0x7887f2cc75c0>, <Element e at 0x7887f2cc7600>]

https://scrapinghub.github.io/xpath-playground/

https://www.w3.org/TR/2017/REC-xpath-31-20170321/#doc-xpath31-ReverseAxis

the preceding-sibling axis contains the context node's preceding siblings, those children of the context node's parent that occur before the context node in document order;

I don't think it specifically states that the order should be reversed.

kou · 2025-05-02T02:42:04Z

But, the response order is reversed from nokogiri and libxml, python(lxml).

All of them are bindings of libxml2. So it's natural that all of them have the same behavior. :-)

Do you think the rexml responses is in the correct order? 🤔

Yes.

match returns a "node-set" that is unordered.

https://www.w3.org/TR/1999/REC-xpath-19991116/#section-Introduction

node-set (an unordered collection of nodes without duplicates)

FYI: Most implementations use XPath 1.0 not XPath 2.0, 3.1, ... REXML also uses XPath 1.0.

naitoh · 2025-05-02T03:13:13Z

But, the response order is reversed from nokogiri and libxml, python(lxml).

All of them are bindings of libxml2. So it's natural that all of them have the same behavior. :-)

Oh!
I see.

Do you think the rexml responses is in the correct order? 🤔

Yes.

match returns a "node-set" that is unordered.

https://www.w3.org/TR/1999/REC-xpath-19991116/#section-Introduction

node-set (an unordered collection of nodes without duplicates)

FYI: Most implementations use XPath 1.0 not XPath 2.0, 3.1, ... REXML also uses XPath 1.0.

Thanks.
I see.

@tompng
Can you update this PR's description?

tompng · 2025-05-02T15:14:33Z

@naitoh Updated 👍

naitoh · 2025-05-03T00:21:38Z

Thanks!

… for multiple node ## Why? See: ruby#251 (comment) - XPath : a/d/preceding::* => ["d", "c", "b"] ```xml <a> <b/>  <c/>  <d/>  <d/>  <e/> <f/> </a> ``` - XPath : a/d/following::* => ["d", "e", "f"] ```xml <a> <b/> <c/> <d/>  <d/>  <e/>  <f/>  </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  </b> <b> <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "x", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  </b> <b> <e/>  <x/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "x", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  <e/>  <x/>  </b> </a> ```

… for multiple node ## Why? See: ruby#251 (comment) - XPath : a/d/preceding::* => ["d", "c", "b"] ```xml <a> <b/>  <c/>  <d/>  <d/>  <e/> <f/> </a> ``` - XPath : a/d/following::* => ["d", "e", "f"] ```xml <a> <b/> <c/> <d/>  <d/>  <e/>  <f/>  </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  </b> <b> <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "x", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  </b> <b> <e/>  <x/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "x", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  <e/>  <x/>  </b> </a> ``` - XPath : //a/x/following-sibling:*[1] => ["w", "x", "y", "z"] ```xml <div> <div> <a/> <-- self --> <w/> <-- //a/x/following-sibling:*[1] --> </div> <a/> <-- self --> <x/> <-- //a/x/following-sibling:*[1] --> <a/> <-- self --> <y/> <-- //a/x/following-sibling:*[1] --> <a/> <-- self --> <z/> <-- //a/x/following-sibling:*[1] --> </div> ```

… for multiple node ## Why? See: ruby#251 (comment) - XPath : a/d/preceding::* => ["d", "c", "b"] ```xml <a> <b/>  <c/>  <d/>  <d/>  <e/> <f/> </a> ``` - XPath : a/d/following::* => ["d", "e", "f"] ```xml <a> <b/> <c/> <d/>  <d/>  <e/>  <f/>  </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  </b> <b> <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "x", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  </b> <b> <e/>  <x/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "x", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  <e/>  <x/>  </b> </a> ``` - XPath : //a/following-sibling:*[1] => ["w", "x", "y", "z"] ```xml <div> <div> <a/> <-- self --> <w/> <-- //a/following-sibling:*[1] --> </div> <a/> <-- self --> <x/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <y/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <z/> <-- //a/following-sibling:*[1] --> </div> ```

…ing, preceding-sibling ## Why? See: ruby#251 (comment) - XPath : a/d/preceding::* => ["d", "c", "b"] ```xml <a> <b/>  <c/>  <d/>  <d/>  <e/> <f/> </a> ``` - XPath : a/d/following::* => ["d", "e", "f"] ```xml <a> <b/> <c/> <d/>  <d/>  <e/>  <f/>  </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  </b> <b> <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "x", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  </b> <b> <e/>  <x/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "x", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  <e/>  <x/>  </b> </a> ``` - XPath : //a/following-sibling:*[1] => ["w", "x", "y", "z"] ```xml <div> <div> <a/> <-- self --> <w/> <-- //a/following-sibling:*[1] --> </div> <a/> <-- self --> <x/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <y/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <z/> <-- //a/following-sibling:*[1] --> </div> ```

…ing, preceding-sibling (#255) ## Why? See: #251 (comment) ## Expected values - XPath : a/d/preceding::* => ["d", "c", "b"] ```xml <a> <b/>  <c/>  <d/>  <d/>  <e/> <f/> </a> ``` - XPath : a/d/following::* => ["d", "e", "f"] ```xml <a> <b/> <c/> <d/>  <d/>  <e/>  <f/>  </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  </b> <b> <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/following-sibling:* => ["c", "d", "x", "e"] ```xml <a> <b> <x/>  <c/>  <d/>  <x/>  <e/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  </b> <b> <e/>  <x/>  </b> </a> ``` - XPath : a/b/x/preceding-sibling::* => ["e", "x", "d", "c"] ```xml <a> <b> <c/>  <d/>  <x/>  <e/>  <x/>  </b> </a> ``` - XPath : //a/following-sibling:*[1] => ["w", "x", "y", "z"] ```xml <div> <div> <a/> <-- self --> <w/> <-- //a/following-sibling:*[1] --> </div> <a/> <-- self --> <x/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <y/> <-- //a/following-sibling:*[1] --> <a/> <-- self --> <z/> <-- //a/following-sibling:*[1] --> </div> ```

Fix reverse sort in xpath_parser

cb0c9d2

Test xpathparser sort with preceding-sibling

d5f5f83

naitoh merged commit de6f40e into ruby:master May 3, 2025
67 checks passed

tompng deleted the fix_xpath_reverse_sort branch May 3, 2025 05:16

naitoh mentioned this pull request May 4, 2025

Fix duplicate responses in XPath following, following-sibling, preceding, preceding-sibling #255

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Fix reverse sort in xpath_parser #251

Fix reverse sort in xpath_parser #251

Uh oh!

tompng commented Apr 30, 2025 •

edited

Loading

Uh oh!

naitoh commented May 1, 2025 •

edited

Loading

Uh oh!

tompng commented May 1, 2025

Uh oh!

naitoh commented May 2, 2025 •

edited

Loading

Uh oh!

kou commented May 2, 2025

Uh oh!

naitoh commented May 2, 2025

Uh oh!

tompng commented May 2, 2025

Uh oh!

Uh oh!

naitoh commented May 3, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

Fix reverse sort in xpath_parser #251

Fix reverse sort in xpath_parser #251

Uh oh!

Conversation

tompng commented Apr 30, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

naitoh commented May 1, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

After

Uh oh!

tompng commented May 1, 2025

Uh oh!

naitoh commented May 2, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kou commented May 2, 2025

Uh oh!

naitoh commented May 2, 2025

Uh oh!

tompng commented May 2, 2025

Uh oh!

Uh oh!

naitoh commented May 3, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

tompng commented Apr 30, 2025 •

edited

Loading

naitoh commented May 1, 2025 •

edited

Loading

naitoh commented May 2, 2025 •

edited

Loading