Assertion failure in subtype for TypeVar in Union

[martinholters]

julia> T1 = Val{Val{Val{Union{Int8,Int16,Int32,Int64,UInt8,UInt16}}}};

julia> T2 = Val{Val{Val{Union{Int8,Int16,Int32,Int64,UInt8, S}}}} where S
Val{Val{Val{Union{Int16, Int32, Int64, Int8, S, UInt8}}}} where S

julia> T1 <: T2
julia: src/subtype.c:108: statestack_get: Assertion `i >= 0 && i < sizeof(st->stack) * 8' failed.

signal (6): Aborted
while loading no file, in expression starting on line 0
gsignal at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
abort at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
unknown function (ip: 0x7f0e9a551e46)
__assert_fail at /lib/x86_64-linux-gnu/libc.so.6 (unknown line)
statestack_get at src/subtype.c:108 [inlined]
pick_union_element at src/subtype.c:285 [inlined]
subtype at src/subtype.c:692
forall_exists_equal at src/subtype.c:845
subtype at src/subtype.c:824
forall_exists_equal at src/subtype.c:855
subtype at src/subtype.c:824
forall_exists_equal at src/subtype.c:845
subtype at src/subtype.c:824
subtype_unionall at src/subtype.c:466
exists_subtype at src/subtype.c:867 [inlined]
forall_exists_subtype at src/subtype.c:895
jl_subtype_env at src/subtype.c:948
jl_f_issubtype at src/builtins.c:286
jl_call_fptr_internal at src/julia_internal.h:326 [inlined]
jl_call_method_internal at src/julia_internal.h:345 [inlined]
jl_apply_generic at src/gf.c:2225
do_call at src/interpreter.c:75
eval at src/interpreter.c:242
# ...

With assertions disabled, this just segfaults. (Discovered while working on https://github.com/JuliaLang/julia/pull/20626/files#r108347856)

[martinholters]

Not that I am seriously suggesting this as a fix, but

--- a/src/subtype.c
+++ b/src/subtype.c
@@ -42,7 +42,7 @@ extern "C" {
 typedef struct {
     int depth;
     int more;
-    uint32_t stack[10];  // stack of bits represented as a bit vector
+    uint32_t stack[100];  // stack of bits represented as a bit vector
 } jl_unionstate_t;
 
 // Linked list storing the type variable environment. A new jl_varbinding_t

fixes this issue, the disabled test of #21192, and all the cases reported in #20103. But presumable, somewhere depth/more should be reset but aren't, leading to an excessive use of stack? (Note that this does not fix #21332 which seems to be an infinite recursion and will exhaust whatever limit.)

[JeffBezanson]

We might as well make that change as a stopgap. It's not wrong.

[martinholters]

In the hope of finding some time, I'll try (again) to pinpoint the underlying cause here. If I don't succeed in the next days, I'll submit a PR with above patch.

Also note #20103 (comment) - the fixes of #20103 are mostly already present in master, not due to this patch.

[martinholters]

Looks like I can't get my mental picture of what the code should do to match what the actually code does. My understanding is that if pick_union_element is called for the same union u, the depth of the stack will be the same. But in the loop of forall_exists_equal, only Lunions.depth is reset to 0, while in subtype called from it, pick_union_element may be called (and the present case, is called) on both types. Hence, during the loop Runion.depth keeps growing. In my mental model, subtype would need to store the depth values upon entry and restore them when returning. However, this is such a grave difference to what is being done now, I haven't even dared trying this... Hence #21416.

[vtjnash]

The forall predicate needs to keep track of all tests that it has already done, and all tests that it still needs to do in order to verify that those two unions are not identical. This causes an exponential explosion in the number of combinations that need to be tested, especially since we can't detect what the value(s) and constraints on S might be until it has scanned the entire type (in this case, to discover that it doesn't have any other constraints).

Perhaps we should change the abort into a "subtype too complex" exception? or add the ability to malloc a larger table as-needed?

[KristofferC]

The original example works now.

[JeffBezanson]

Closing in favor of #27101.