Changing statement order in generics can cause type mismatches

[haxscramper]

Changing statement order in simpleTreeDiff causes compilation error. I'm not entirely sure if this is a bug, or some insanely convoluted generic interaction, but since the behavior of the compiler wildly differs only based on the order of generic instantiations it is probably a bug.

Example

import std/[tables, hashes]

type
  NodeId*[L] = object
    isSource: bool
    index: Table[NodeId[L], seq[NodeId[L]]]

func hash*[L](id: NodeId[L]): Hash = discard
func `==`[L](a, b: NodeId[L]): bool = discard

proc makeIndex*[T, L](tree: T) =
  var parent = NodeId[L]()
  var tmp: Table[NodeId[L], seq[NodeId[L]]]
  tmp[parent] = @[parent]

proc simpleTreeDiff*[T, L](source, target: T) =
  # Swapping these two lines makes error disappear
  var m: Table[NodeId[L], NodeId[L]]
  makeIndex[T, L](target)

var tmp: Table[string, seq[string]] # removing this forward declaration also removes error

proc diff(x1, x2: string): auto =
  simpleTreeDiff[int, string](12, 12)

Current Output

/usercode/in.nim(29, 17) template/generic instantiation of `simpleTreeDiff` from here
/usercode/in.nim(24, 21) template/generic instantiation of `makeIndex` from here
/usercode/in.nim(18, 15) template/generic instantiation of `[]=` from here
/playground/nim/lib/pure/collections/tableimpl.nim(58, 21) template/generic instantiation of `rawGet` from here
/playground/nim/lib/pure/collections/hashcommon.nim(60, 48) Error: type mismatch: got <string, NodeId[system.string, system.string]>

Expected Output

No compilation errors

Additional

I added static: echo typeof ... in tables.[]= to printf-debug instantiation. Concreted code now is (module runnable example and documentation):

proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) =
  static:
    echo "proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) ="
    echo "  typeof(A) ", typeof(A)
    echo "  typeof(B) ", typeof(B)
    echo "  typeof(t) ", typeof(t)
    echo "  typeof(t.data) ", typeof(t.data)

  putImpl(enlarge)

And it produces different results based on order of the statements in code above or whether var tmp: Table[string, seq[string]] is present. When I try to compile example it outputs

proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) =
  typeof(A) NodeId[system.string]
  typeof(B) seq[NodeId[system.string]]
  typeof(t) Table[NodeId[system.string], seq[NodeId[system.string]]]
  typeof(t.data) KeyValuePairSeq[system.string, seq[string]]

When I remove var tmp: Table[string, seq[string]] compilations succeeds, printing out

proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) =
  typeof(A) NodeId[system.string]
  typeof(B) seq[NodeId[system.string]]
  typeof(t) Table[NodeId[system.string], seq[NodeId[system.string]]]
  typeof(t.data) KeyValuePairSeq[NodeId[system.string], seq[NodeId[system.string]]]

Which is what one could expect (t.data generic parameters are the same as in table itself).

Nim version

$ nim -v
Nim Compiler Version 1.4.0 [Linux: amd64]
Compiled at 2020-10-16
Copyright (c) 2006-2020 by Andreas Rumpf

git hash: bdcd87afca238a0a7b2c70971827cf9172817b12
active boot switches: -d:release -d:danger

[timotheecour]

• seems like duplicate of generics caching buggy and order-sensitive #13572 ?
• this is pervasive, HeapQueue is also affected by this, see in-order iteration of HeapQueue timotheecour/Nim#373 (comment)
• ditto with all table-like types since they rely on hashes.

IMO we should always allow passing the relevant hash/comparator to algorithms, it's explicit and more flexible, in particular doesn't affect unrelated code (if different hash/comparator is needed), as done in C++, D and other languages. This can be done in a backward compatible way and zero-cost way, avoiding a function pointer overhead even without lto

[haxscramper]

Good to know that this at least somewhat known issue. Even though it might be considered duplicate I would still prefer to leave it open, since this is a particularly tricky to reproduce, so more examples would be nice to have.

Is there any way currently to deal with this right now? Or I need to somehow instantiate needed generics earlier (by explicitly stating this limitation in documentation and carefully watching order of imports each time?).

PS: I'm also in favor of passing hash/==/< explicitly to implementation.

[SirOlaf]

Was fixed in #22828