JuliaCollections / JuliaCollections/DataStructures.jl
a slighly uncanny `UndefRefError` with default-empty SortedSet
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 745
- Forks
- 261
- PR merge metrics
- No merged PRs in 30d
Description
Hello!
while debugging one certain package (ConstraintTrees.jl) we found the following surprise with 0.19.4:
julia> union(SortedSet(Symbol[:x,:y]),SortedSet(Any[]))
SortedSet{Symbol, Base.Order.ForwardOrdering} with 2 elements:
:x
:y
julia> union(SortedSet(Any[]),SortedSet(Symbol[:x,:y])) # this triggered our tests
ERROR: UndefRefError: access to undefined reference
Stacktrace:
[1] getproperty
@ ./Base.jl:49 [inlined]
[2] DataStructures.BalancedTree23{…}(::Val{…}, iterable::Base.Generator{…}, ord::Base.Order.ForwardOrdering, allowdups::Bool)
@ DataStructures ~/.julia/packages/DataStructures/9m6yb/src/balanced_tree.jl:1053
[3] SortedSet
@ ~/.julia/packages/DataStructures/9m6yb/src/sorted_set.jl:82 [inlined]
[4] packcopy
@ ~/.julia/packages/DataStructures/9m6yb/src/sorted_set.jl:697 [inlined]
[5] union(m1::SortedSet{Any, Base.Order.ForwardOrdering}, others::SortedSet{Symbol, Base.Order.ForwardOrdering})
@ DataStructures ~/.julia/packages/DataStructures/9m6yb/src/sorted_set.jl:360
[6] top-level scope
@ REPL[18]:1
Some type information was truncated. Use `show(err)` to see complete types.
julia> union(SortedSet(),SortedSet()) # simplest reproducer
ERROR: UndefRefError: access to undefined reference
Stacktrace:
[1] getproperty
@ ./Base.jl:49 [inlined]
[2] DataStructures.BalancedTree23{…}(::Val{…}, iterable::Base.Generator{…}, ord::Base.Order.ForwardOrdering, allowdups::Bool)
@ DataStructures ~/.julia/packages/DataStructures/9m6yb/src/balanced_tree.jl:1053
[3] SortedSet
@ ~/.julia/packages/DataStructures/9m6yb/src/sorted_set.jl:82 [inlined]
[4] union(s1::SortedSet{Any, Base.Order.ForwardOrdering}, others::SortedSet{Any, Base.Order.ForwardOrdering})
@ DataStructures ~/.julia/packages/DataStructures/9m6yb/src/sorted_set.jl:378
[5] top-level scope
@ REPL[19]:1
Some type information was truncated. Use `show(err)` to see complete types.
This was triggered by ConstraintTrees testing code and we can confirm that this "worked" originally in DataStructures 0.18-ish. Notably, other sets (OrderedSet) do not seem to have the issue.
I thought I'd leave a note here just in case this would point to a bigger issue somewhere (UndefRefError sounded scary). I looked at the changelogs but there's no notice of this being undefined behavior or so. I hope I didn't miss some obvious warning somewhere.
(also thanks for making DataStructures! I ❤️ the ordered ones!)
cc @stelmo the original discoverer
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the minimal union(SortedSet(), SortedSet()) reproduction and inspect sorted_set.jl at lines 82, 360, 378, and 697, then follow the constructor in balanced_tree.jl at line 1053. Compare the empty and non-empty union cases and the reported OrderedSet behavior. Done means empty SortedSet unions no longer raise UndefRefError and the shown non-empty unions still work.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100