JuliaCollections / JuliaCollections/DataStructures.jl

a slighly uncanny `UndefRefError` with default-empty SortedSet

Open
#969 6 comments 0 reactions 0 assignees View on GitHub

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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.