Weird conflicting behavior with generic functions in generic types?

[MaximumADHD]

Initial Problem

So I have a generic typed implementation of a binary search tree: https://gist.github.com/MaximumADHD/10ff7eaeeca558ae2b8ceec22350c44f

The type seems to work fine within the module itself, but problems start happening when I import and embed the type into other types:

--!strict

local BST = require(workspace.BST)
local data: { BST.Class<number> } = {}

for i, dummy in data do
	dummy:Add(0)
end

Type Error: (6,1) Type '{ @metatable BinarySearchTree, {| _compare: (number, number) -> number, _root: Node<number>? |} }' could not be converted into '{ @metatable BinarySearchTree, {| _compare: (number, number) -> number, _root: Node<number>? |} }'
caused by:
Type 'BinarySearchTree' from 'game.Workspace.BST' could not be converted into 'BinarySearchTree' from 'game.Workspace.BST'
caused by:
Property 'Add' is not compatible. Type '({ @metatable BinarySearchTree, {| _compare: (a, a) -> number, _root: Node<a>? |} }, a) -> boolean' could not be converted into '<T>({ @metatable BinarySearchTree, {| _compare: (T, T) -> number, _root: Node<T>? |} }, T) -> boolean'; different number of generic type parameters

Comparing the two functions types, it seems the function isn't being treated as a generic correctly?

({ @metatable BinarySearchTree, {| _compare: (a, a) -> number, _root: Node<a>? |} }, a) -> boolean <T>({ @metatable BinarySearchTree, {| _compare: (T, T) -> number, _root: Node<T>? |} }, T) -> boolean

---

Possible root issue?

While I was trying to work around this bug, I noticed the following type definition is invalid:

type BST<T> = {
	Add: <T>(self: BST<T>, value: T) -> boolean,
	Remove: <T>(self: BST<T>, value: T) -> (),
	Iter: <T>(self: BST<T>, value: T) -> () -> T?,
	Front: <T>(self: BST<T>) -> T?,
	Back: <T>(self: BST<T>) -> T?,
	ToArray: <T>(self: BST<T>) -> {T},
	Clear: <T>(self: BST<T>) -> (),
}

However, it's fine to add a generic function to a generic type as long as the arguments don't include generics?

type Generic<T> = {
	Test: <T>() -> ()
}

I tried adding this Test function to my workaround and started seeing a similar different number of generic type parameters error:

I'm a little stumped on what the exact problem is, but I hope this repro is enough to track it down.

[Aeroverra]

I spent way too much time on this. Glad I finally found this post.

I think generics are nowhere near production ready.

[TrulyChxse]

I think that the generics are at this point really inconsistent, I can't see anything that could lead to this, so I'm interested if anyone else figures out.

[vegorov-rbx]

To explain one of the parts:

type BST<T> = {
	Add: <T>(self: BST<T>, value: T) -> boolean,
	Remove: <T>(self: BST<T>, value: T) -> (),
	Iter: <T>(self: BST<T>, value: T) -> () -> T?,
	Front: <T>(self: BST<T>) -> T?,
	Back: <T>(self: BST<T>) -> T?,
	ToArray: <T>(self: BST<T>) -> {T},
	Clear: <T>(self: BST<T>) -> (),
}

This is invalid because <T> on a function type introduces a different local T generic type, so it says that Add function has to work with any type T, not just the outer T that the BST type is being defined with. Because outer and inner Ts are different, it creates an infinite recursion in instantiation of BST with potentially different types.

It should just be just:

type BST<T> = {
	Add: (self: BST<T>, value: T) -> boolean,
	...
}

Or if functions are intended to be generic over one of the parameters:

type BST<T> = {
	Add: <U>(self: BST<T>, value: U) -> boolean, -- even if function is generic over U, we still use BST<T>
	...
}

I know this doesn't help with the original problem, but I wanted to address this part.

[andyfriesen]

I think this is the minimal repro:

--!strict

local BinarySearchTree = {}
BinarySearchTree.__index = BinarySearchTree

export type Class = typeof(setmetatable({}, BinarySearchTree))

function BinarySearchTree.Add<T>(self: Class, value: T)
end

local data: { Class } = {}

for i, dummy in data do
	dummy:Add(0)
end

We get this error

Type Error: (14,2) Type 'Class' could not be converted into 'Class'
caused by:
  Type 'BinarySearchTree' from 'game.Workspace.Script' could not be converted into 'BinarySearchTree' from 'game.Workspace.Script'
caused by:
  Property 'Add' is not compatible. Type '(Class, a) -> ()' could not be converted into '<T>(Class, T) -> ()'; different number of generic type parameters```