Recursive type alias caused undecidable type and crashed the compiler

[sicusa]

In the docs there is a piece of code which demonstrates the recursive alias along with union type:

alias RecArray = Array(Int32) | Array(RecArray)

ary = [] of RecArray
ary.push [1, 2, 3]
ary.push ary
ary #=> [[1, 2, 3], [...]]

With a sudden inspiration I moved the occurrence of union type into the element of RecArray:

alias RecArray = Array(Int32 | Array(RecArray))
ary = [] of RecArray

The element of RecArray can either be of type Int32 or Array(RecArray) according to the recursive alias. Following lines of code all worked as expected:

ary.push [1, 2, 3] # all elements are Int32
ary.push [1, 2, 3, ary] # ary is of type Array(RecArray)

The next line of code, however, crashed the compiler with output Invalid memory access (signal 11) at address 0x7fffee932fc8\n[0x7f5309649496] ???\n[0x7f5308e140ba] ???\n[0x7f530aa91cbe] ???:

ary.push [1, 2, 3, [ary]]

[1, 2, 3, [ary]] is of type Array(Int32 | Array(Array(RecArray))). As far as I can imagine, the compiler has to decide whether this type is equivalent to or included in the type RecArray, i.e., Array(Int32 | Array(RecArray)). Both of them are instance types of Array, so the next step is to compare the types of their elements, i.e., Int32 | Array(Array(RecArray)) and Int32 | Array(RecArray). Eliminating the common parts of Int32 | Array(...), we reduce this problem into comparing Array(RecArray) with RecArray.

Since RecArray can be rewritten as Array(Int32 | Array(RecArray)), this probem can be transformed into comparing Array(Array(Int32 | Array(RecArray))) with Array(Int32 | Array(RecArray)). Eliminating the common parts of Array(...), the compiler now has to check the compatibility of Array(Int32 | Array(RecArray)) and Int32 | Array(RecArray), i.e., Array(Int32 | Array(RecArray)) and Array(RecArray) (since the former type cannot be an Int32).

Eliminating the common parts again, we further reduce this problem into comparing Int32 | Array(RecArray) and RecArray, i.e., Array(RecArray) and RecArray, which is the situation you have seen before.

Because of this infinite loop during the type-check process, the equivalency of RecArray and the type of [1, 2, 3, [ary]] is undecidable. Adding any element that contains Array(RecArray) to ary would crash the compiler.

[asterite]

Duplicate of #3804