Re: Type instantiation for `==` func

[LeuGim]

@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.

Re: Type instantiation for `==` func

[LeuGim]

> 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.

Re: Type instantiation for `==` func

[e]

So, digging deeper, the place where the generic instantiation is losing is


while curr != nil or stack.len > 0:

Run

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:

Run

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.

Re: Type instantiation for `==` func

[LeuGim]

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.

Re: Type instantiation for `==` func

[tim_st]

There is a len func func len*[K,V](root: BBTree[K,V]): int = ... but the 
compiler doesn't match it similiar to this issue 
[https://github.com/nim-lang/Nim/issues/9606](https://github.com/nim-lang/Nim/issues/9606)
 . I tried the code by explicitly call filename.len to force the correct match, 
but still other errors appear, if it's that obvious, please show your working 
solution.

Re: Type instantiation for `==` func

[tim_st]

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


Run

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 :(

Re: Type instantiation for `==` func

[e]

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.

Re: Type instantiation for `==` func

[tim_st]

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)


Run

Re: Type instantiation for `==` func

[e]

Sure, here are the relevant bits:


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 node

Run


func isSubset*[K,U,V](tree1: BBTree[K,U], tree2: BBTree[K,V]): bool =

Run

You can find the complete repo at 
[github](https://github.com/dcurrie/nim-bbtree)

Re: Type instantiation for `==` func

[mratsim]

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?