a slighly uncanny `UndefRefError` with default-empty SortedSet

[exaexa]

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

[StephenVavasis]

I have created pull request 970 to fix the issue. The issue arises because the balanced tree data structure underlying SortedSet, SortedDict, and SortedMultiDict always has two sentinel data items in the tree, before-start and after-end. These sentinels are declared as data nodes, and data nodes contain a key and, in the case of SortedDict and SortedMultiDict, a value. However, because Julia does not support "default constructors", I don't know of a way to create a default key or default value of the right types if only the types are known but no objects of the type are present. So the code, upon creating an initially empty tree, fills these sentinels with uninitialized fields (which is possible in julia because "new" is allowed to partially initialize a struct). Upon the first insertion into the data structure, the key and value from the first inserted item are copied into the sentinels so that they are properly formed data items. This approach means that the rest of the code must not try to dereference the key or values in the sentinels of an empty tree. Unfortunately, I forgot about this edge case in one of the constructors. Pull request 970 now checks for this special case in the offending constructor and terminates the constructor at an earlier point if it detects that the tree is empty.

…

________________________________ From: Mirek Kratochvil ***@***.***> Sent: Saturday, May 2, 2026 9:39 PM To: JuliaCollections/DataStructures.jl ***@***.***> Cc: Subscribed ***@***.***> Subject: [JuliaCollections/DataStructures.jl] a slighly uncanny `UndefRefError` with default-empty SortedSet (Issue #969) [https://avatars.githubusercontent.com/u/271543?s=20&v=4]exaexa created an issue (JuliaCollections/DataStructures.jl#969)<#969> 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<https://github.com/stelmo> the original discoverer — Reply to this email directly, view it on GitHub<#969>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB4EJB2UA67GY4FNJ4K4CJT4YZFF7AVCNFSM6AAAAACYOPCJTCVHI2DSMVQWIX3LMV43ASLTON2WKOZUGM3DSOBTHEYDSOA>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[StephenVavasis]

My pull request #970 has failed two of the Github checks. I don't know what these checks do so I don't know how to fix this.

[exaexa]

@StephenVavasis oh great thanks for all the info!

The failed checks look like required code coverage, looks like that codepath is not tested: https://app.codecov.io/gh/JuliaCollections/DataStructures.jl/pull/970?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=checks&utm_campaign=pr+comments&utm_term=JuliaCollections

(note: here https://github.com/JuliaCollections/DataStructures.jl/pull/970/changes#diff-a483f51c6448ee1b535bba625d753f3bdc11643d30446ba9100694d9c0d5f1e0R310 you test SortedDict, perhaps the codepath is specific to SortedSet ?)

[StephenVavasis]

Good catch, thanks! I changed the test set as you suggested. Now there is only one check failing. Do you have any more suggestions?

…

________________________________ From: Mirek Kratochvil ***@***.***> Sent: Sunday, May 3, 2026 2:56 PM To: JuliaCollections/DataStructures.jl ***@***.***> Cc: Stephen Vavasis ***@***.***>; Mention ***@***.***> Subject: Re: [JuliaCollections/DataStructures.jl] a slighly uncanny `UndefRefError` with default-empty SortedSet (Issue #969) [https://outlook.office.com/mail/inbox/id/AAkALgAAAAAAHYQDEapmEc2byACqAC%2FEWg0AVhtaCiB2n0monB7NrPRPNgAFOvPOygAA?nativeVersion=1.2026.421.500]exaexa left a comment (JuliaCollections/DataStructures.jl#969)<#969 (comment)> @StephenVavasis<https://github.com/StephenVavasis> oh great thanks for all the info! The failed checks look like required code coverage, looks like that codepath is not tested: https://app.codecov.io/gh/JuliaCollections/DataStructures.jl/pull/970?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=checks&utm_campaign=pr+comments&utm_term=JuliaCollections (note: here https://github.com/JuliaCollections/DataStructures.jl/pull/970/changes#diff-a483f51c6448ee1b535bba625d753f3bdc11643d30446ba9100694d9c0d5f1e0R310 you test SortedDict, perhaps the codepath is specific to SortedSet ?) — Reply to this email directly, view it on GitHub<#969 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB4EJB3H4XDFEQ476IBXZQD4Y46ZHAVCNFSM6AAAAACYOPCJTCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHM2DGNRWGIYTSNZQGE>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you were mentioned.Message ID: ***@***.***>

[exaexa]

well see the link: https://app.codecov.io/gh/JuliaCollections/DataStructures.jl/pull/970/indirect-changes
that condition shortcircuited another condition, so that one is now untested

[StephenVavasis]

That is mysterious since the red-black tree code is entirely disjoint from the sorted-containers code. I have not worked on the red-black code, so I don't know how to fix this. If some other subscriber to the list knows how the red-black code works, maybe they can look at this. Or maybe one of the maintainers can override this failed check?

…

________________________________ From: Mirek Kratochvil ***@***.***> Sent: Sunday, May 3, 2026 3:16 PM To: JuliaCollections/DataStructures.jl ***@***.***> Cc: Stephen Vavasis ***@***.***>; Mention ***@***.***> Subject: Re: [JuliaCollections/DataStructures.jl] a slighly uncanny `UndefRefError` with default-empty SortedSet (Issue #969) [https://outlook.office.com/mail/inbox/id/AAkALgAAAAAAHYQDEapmEc2byACqAC%2FEWg0AVhtaCiB2n0monB7NrPRPNgAFOvPWwgAA?nativeVersion=1.2026.421.500]exaexa left a comment (JuliaCollections/DataStructures.jl#969)<#969 (comment)> well see the link: https://app.codecov.io/gh/JuliaCollections/DataStructures.jl/pull/970/indirect-changes that condition shortcircuited another condition, so that one is now untested — Reply to this email directly, view it on GitHub<#969 (comment)>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AB4EJBYVQET23JORR2WGBWT4Y5BDXAVCNFSM6AAAAACYOPCJTCVHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHM2DGNRWGI2TONBRGU>. Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>. You are receiving this because you were mentioned.Message ID: ***@***.***>