[Bug #21449] Fix Set#divide{|a,b|} using Union-find structure#13680
Merged
tompng merged 2 commits intoruby:masterfrom Jun 23, 2025
Merged
[Bug #21449] Fix Set#divide{|a,b|} using Union-find structure#13680tompng merged 2 commits intoruby:masterfrom
tompng merged 2 commits intoruby:masterfrom
Conversation
Implements Union-find structure with path compression.
Since divide{|a,b|} calls the given block n**2 times in the worst case, there is no need to implement union-by-rank or union-by-size optimization.
jeremyevans
reviewed
Jun 23, 2025
Contributor
jeremyevans
left a comment
There was a problem hiding this comment.
Thank you for finding and fixing this.
Comment on lines
+888
to
+889
| if (RTEST(rb_yield_values(2, item1, item2)) && | ||
| RTEST(rb_yield_values(2, item2, item1))) { |
Contributor
There was a problem hiding this comment.
This is probably vulnerable to the same type of bug as https://bugs.ruby-lang.org/issues/21306, since the block could get access to the items array and shrink it while you are iterating.
Member
Author
There was a problem hiding this comment.
items is a snapshot of set_i_to_a(set)
Since union-find uses index, and items is used in the latter part of this function, item needs to be unmodified.
To avoid items and other internal arrays to be modified through ObjectSpace, I changed these in 99c5bf4
- Freeze items
rb_ary_freeze(items)before using it - Use ALLOCV_N instead of ruby array that stores index.
…vide Internal arrays can be modified from yielded block through ObjectSpace. Freeze readonly array, use ALLOCV_N instead of mutable array.
jeremyevans
approved these changes
Jun 23, 2025
Contributor
jeremyevans
left a comment
There was a problem hiding this comment.
Awesome! Thank you again for fixing this.
headius
added a commit
to headius/jruby
that referenced
this pull request
Nov 17, 2025
Based on code from CRuby by Tomoya Ishida: ruby/ruby#13680
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
2 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Implement
Set#divideby union-find structure with path compression.https://en.wikipedia.org/wiki/Disjoint-set_data_structure
Since
divide{|a,b|}calls the given blockn**2times in the worst case, there is no need to implement union-by-rank or union-by-size optimization.