Stackoverflow in type_check function with generic record

[Balint66]

Hello there!

I wanted to implement a record based on java8's Optional class, when I stumbled upon an interesting bug.

Here is the code that gives the error, when I called:

local record Optional<T>
    value: T | nil
    isPresent: function(Optional<T>) : boolean
    ifPresent: (function(Optional<T>, function( T):nil):nil)
    filter: (function(Optional<T>, function(T):boolean):Optional<T>)
    map: (function(function(T): Optional<any>): Optional<any>)
    orElse: (function(Optional<T>, T): T)
    orElseGet: (function(Optional<T>, function():T): T)
    orElseError: (function(Optional<T>, string): T | nil)
    of: (function(Optional<T>, T): Optional<T>)
    ofNilable: (function(Optional<T>, T | nil): Optional<T>)
end

function Optional:of<T>(value: T): Optional<T>
    return setmetatable({value=value} as Optional<T>, {__index = self})
end

I've tried to call it like so:

local Empty = Optional:of(nil)
local Test = Optional:of(10)

At both cases, it gives an error like this:

Error Error executing command
      ...    /usr/share/lua/5.4/tl.lua:6317: stack overflow
      ... stack traceback:
      ...       /usr/share/lua/5.4/tl.lua:6317: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:6319: in function </usr/share/lua/5.4/tl.lua:6276>
      ...       (...tail calls...)
      ...       ...     (skipping 99967 levels)
      ...       /usr/share/lua/5.4/tl.lua:3116: in local 'fn'
      ...       /usr/share/lua/5.4/tl.lua:3293: in function </usr/share/lua/5.4/tl.lua:3273>
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/tl.lua:9015: in function 'tl.type_check'
      ...       (...tail calls...)
      ...       /usr/share/lua/5.4/cyan/commands/check-gen.lua:75: in local 'process_file'
      ...       /usr/share/lua/5.4/cyan/commands/check-gen.lua:104: in field 'exec'
      ...       /usr/share/lua/5.4/cyan/cli.lua:148: in function </usr/share/lua/5.4/cyan/cli.lua:147>
      ...       [C]: in function 'xpcall'
      ...       /usr/share/lua/5.4/cyan/cli.lua:147: in main chunk
      ...       [C]: in function 'require'
      ...       /usr/lib/luarocks/rocks-5.4/cyan/0.1.0-1/bin/cyan:2: in main chunk
      ...       [C]: in ?

The relevant code is this one:

 elseif t1.typename == "union" then
         for _, t in ipairs(t1.types) do
            if not is_a(t, t2, for_equality) then
               return false, terr(t1, "got %s, expected %s", t1, t2)
            end
         end
         return true

My temporary solution to make my code build is to ignore typevars when testing the unions, then the second and indeed, only one left type is tested is nil, that always returns null.

So, my guess is that T somehow resolves to the union of T and nil, that will recurse forever.

[hishamhm]

Ah, this looks like a bug that is fixed (or partially fixed) inside this long PR, because during my testing some of the behavior changes if you rename <T> to <U> in the definition of :of (though it doesn't really fix it on master). This is a tricky one to fix!

Be mindful though, that as far as Teal is concerned, T | nil is not a more specific type than T, since every type accepts nil.

[Balint66]

Thanks for the fast reply!

Actually, I know that T | nil is not more specific than T, it's there for readability and for those who are not used to Lua and has some other language background because who would guess that T as a specific type could be nilable? Where did my integer go?.

I'll have a fast look at the PR, although I tried to rename my generic variable in :of from T to K U is used elsewhere in the file, so just wanted to be extra safe here, but it produced the same error for me.

I'll report back as soon as I can.

[Balint66]

Just checked, and the same error come up with the PR and with the changed generic type name.

[hishamhm]

Actually, I know that T | nil is not more specific than T, it's there for readability and for those who are not used to Lua and has some other language background

My general advice is against that since it can be misleading, especially for those coming from other backgrounds. If they see a T | nil here and a T there, they'll assume that the latter cannot be nil, which isn't true.

Just checked, and the same error come up with the PR and with the changed generic type name.

Yeah, I tried something similar and ran into the same bug. Thanks for confirming. I do know that parts of that PR do improve things and I'll try to extract them and merge them in (even without variadic type variables), and hopefully I can address the issue while doing that.

[hishamhm]

This should be fixed in the latest master! Please let me know if you run into other similar crashes.