My first Nim library, so newbie warning... The library is a persistent balanced tree data structure that can be used as a map or a set. It's mostly working and tested, but I ran into trouble trying to make a generic == to match the built-in Nim set equality operator. Since the comparison is on keys only (type K), the type of the values does not need to match (U and V here).
So, this works...
func `<=`*[K,U,V](s1: BBTree[K,U], s2: BBTree[K,V]): bool {.inline.} =
result = isSubset(s1, s2)but this gives Error: cannot instantiate: 'V'
func `==`*[K,U,V](s1: BBTree[K,U], s2: BBTree[K,V]): bool {.inline.} =
result = isSubset(s1, s2) and len(s1) == len(s2)Note that the type declarations are identical. Even if I make the bodies of the two functions identical, Nim still gives an instantiation error for the second one. Is there something special about == that is preventing this from working?
I don't see a reason why it would fail to compile.
Can you also add your BBTree and isSubSet type declaration so that we can reproduce a minimal working example?
type
BBTree*[K,V] = ref object # BBTree is a generic type with keys and values of types K, V
## `BBTree` is an opaque immutable type.
left: BBTree[K,V] # left subtree; may be nil
right: BBTree[K,V] # right subtree; may be nil
size: int # the size of the (sub-)tree rooted in this node
key: K # the search key; must suppprt the generic ``cmp`` proc
val: V # the data value associated with the key, and stored in a nodefunc isSubset*[K,U,V](tree1: BBTree[K,U], tree2: BBTree[K,V]): bool =You can find the complete repo at github
Seems like a compiler bug. Workaround:
func `==`*(s1: BBTree, s2: BBTree): bool {.inline.} =
## Returns true if both `s1` and `s2` have the same keys and set size.
result = isSubset(s1, s2) and len(s1) == len(s2)
Having thought about this for a while, I am not advocating for a fix. I was hesitant to define the == func at all since it is comparing keys but not values, It is called set-equal? in MIT/Scheme wttree, not equal?. I only considered adding it to make the unit tests line up with other Nim set library unit tests. For that purpose, I've defined =?= instead .
It's reasonable for Nim to refuse to consider this func a true == if it can't unify U and V given a reasonable definition of equal, I just don't understand what language mechanism is preventing it.
I replaced some generic parameters in your code with untyped templates and then always new errors appeared in procs that were called from the proc that showed the error, so it seems you have somewere the real bug, but the compiler can't show you the correct place (I've seen this behaviour before when generics are used in code I have written). I couldnt find out the exact place because nim and nimsuggest got into endless loops at 100% cpu when replacing the second proc with untyped template.
The following shows that normally your generic type idea works (and I think it's a good idea how you have written your code):
type GenericType[K, V] = object
key: K
value: V
func values*[K,V,T](t1: GenericType[K,V], t2: GenericType[K,T]): tuple[v1: V, v2: T] =
result = (t1.value, t2.value)
when isMainModule:
var t1: GenericType[string, int]
var t2: GenericType[string, char]
t1.key = "abc"
t1.value = 1
t2.key = "abc"
t2.value = '1'
var v = values(t1, t2)
echo v.v1
echo v.v2
So for now I can only suggest when you use generics test your procs as soon as possible, because generic procs are often checked very late by the compiler which means that some incorrect procs only error when they are actually called in the code :(
But error message clearly says that you have no len procedure for BBTree. Just define it. Or maybe you meant to use size field in BBtree for that. You may after all rename == to whatever else (some ^&%) and see the error message not changing - it has nothing to do with the function's name, just with its content.
Even if I make the bodies of the two functions identical, Nim still gives an instantiation error for the second one.
No, it doesn't.
while curr != nil or stack.len > 0:So, the compiler can't infer a type for nil. It hadn't occurred to me to look for !=. If I replace that line with
while (not curr.isNil) or stack.len > 0:and do the same thing in several other places, the problem goes away. So, it does have to do the function's name, and the semantics of == and !=.
No compiler bug.
Thanks for your help.
if it's that obvious
What looks obvious is that error is not because of procedure's name (==) - you may test it with changing it to some different name.
len - yes, it's in the library, I didn't see the librarythen, tried the snippet from the original post.
Trying the library itself, errors are identical for <= and ==.
I don't see connection to your issue.
@e:
To make it work node != nil in contains (bbtree.nim#612) needs to be changed to not node.isNil. It's used from both == and <=, error messages hint to that.