[generic] T:seq wrong type inference: can't instantiate proc fun1[T1:seq, T2:seq](a1:T1, a2:T2) with fun1(@[1], @[1.0])

[timotheecour]

when defined(case_ok):
  block:
    proc fun1[T1:seq, T2:seq](a1:T1, a2:T2)=discard
    fun1(@[1], @[1]) #works
  block:
    type T = int|float
    proc fun1[T1:T, T2:T](a1:T1, a2:T2)=discard
    fun1(1, 1.0)

when defined(case1):
  proc fun1[T1:seq, T2:seq](a1:T1, a2:T2)=discard
  fun1(@[1], @[1.0]) #error:
  #[ 
  Error: type mismatch: got <seq[int], seq[float64]>
but expected one of:
proc fun1[T1: seq; T2: seq](a1: T1; a2: T2)
  first type mismatch at position: 2
  required type: T2: seq
  but expression '@[1.0]' is of type: seq[float64]

expression: fun1(@[1], @[1.0])
    fun1(@[1], @[1.0]) #works
   ]#

when defined(case_ok2):
  type B[T] = object
    discard
  type isB = concept x
    x.type is B[x.type.T]

  proc fun1[T1:isB, T2:isB](a1:T1, a2:T2)=discard
  fun1(B[int](), B[int]())
  fun1(B[int](), B[float]())

[LemonBoy]

proc fun1[T1:seq, T2:seq](a1:T1, a2:T2)

is desugared as

proc fun1[T; T1:seq[T], T2:seq[T]](a1:T1, a2:T2)

and due to the bind-once nature of generic parameters you can't have T to be a int and a float at the same time. What you want to do is something like this:

proc fun1[U,V; T1:seq[U], T2:seq[V]](a1:T1, a2:T2)

I'm not completely sure this is a bug.

[Bulat-Ziganshin]

I think that it's more logical to desugar [T1:seq, T2:seq] into [X1,X2, T1:seq[X1], T2:seq[X2]] since user don't asked to use the same type variables in T1 and T2 desugaring. Or it's because both 'seq' are meant to represent the same type? How it will desugar [T1:seq, T2:ref] ?

[timotheecour]

I think that it's more logical to desugar [T1:seq, T2:seq] into [X1,X2, T1:seq[X1], T2:seq[X2]] since user don't asked to use the same type variables in T1 and T2 desugaring

indeed, that should be the way desugar works. If I wanted the same type I would write:
proc fun1[T:seq](a1:T, a2:T)=discard
instead of
proc fun1[T1:seq, T2:seq](a1:T1, a2:T2)=discard

[LemonBoy]

The problem is slightly more complex, the seq type is declared as follows:

  seq*{.magic: "Seq".}[T]  ## Generic type to construct sequences.

and the generic parameters [T1: seq, T2:seq] are of course desugared as (rough translation of the AST) [T1: tySequence[tyGenericParam T]], T2: tySequence[tyGenericParam T]] where the T represents the very same AST node.

The first idea that comes to mind is to extend liftParamType to handle this transform and lift the two "implicit Ts into two anonymous generic parameters but iif the T` is not in the generic parameter list.
I've implemented this strategy and it does work reasonably well for the given test case, I'm attaching the patch below for review (CC @zah since we're in template land)

diff --git a/compiler/semtypes.nim b/compiler/semtypes.nim
index 05a9d9882..199177748 100644
--- a/compiler/semtypes.nim
+++ b/compiler/semtypes.nim
@@ -980,11 +980,38 @@ proc liftParamType(c: PContext, procKind: TSymKind, genericParams: PNode,
     result = addImplicitGeneric(copyType(paramType, getCurrOwner(c), false))
 
   of tyGenericParam:
-    markUsed(c.config, info, paramType.sym, c.graph.usageSym)
-    styleCheckUse(info, paramType.sym)
-    if tfWildcard in paramType.flags:
-      paramType.flags.excl tfWildcard
-      paramType.sym.kind = skType
+    proc copyTree(t: PType, keepId: bool = false): PType =
+      if t == nil: return
+      result = copyType(t, t.owner, keepId)
+      for i in 0..result.sons.high:
+        result.sons[i] = copyTree(result.sons[i], keepId)
+
+    proc inGen(sym: PIdent): bool =
+      for i in countup(0, genericParams.len - 1):
+        if genericParams.sons[i].sym.name.id == sym.id: return true
+      return false
+
+    proc foo(t: PType, closure: RootRef): PType =
+      result = t
+      if t.kind == tyGenericParam and t.sym != nil and
+        not inGen(t.sym.name):
+        result = addImplicitGenericImpl(cast[PContext](closure),
+          copyType(t, t.owner, false), nil)
+
+    result = copyTree(paramType, true)
+    if result.sons.len > 0:
+      result.sons[^1] = mutateType(result.sons[^1], foo, cast[RootRef](c))
+
+    # if mdbg and genericParams != nil:
+    #   echo "Generics"
+    #   for p in genericParams: debug p
+    #   echo "--------"
+
+    markUsed(c.config, info, result.sym, c.graph.usageSym)
+    styleCheckUse(info, result.sym)
+    if tfWildcard in result.flags:
+      result.flags.excl tfWildcard
+      result.sym.kind = skType
 
   else: discard
 
diff --git a/compiler/types.nim b/compiler/types.nim
index 4180d34a7..89bedeff3 100644
--- a/compiler/types.nim
+++ b/compiler/types.nim
@@ -27,7 +27,7 @@ proc base*(t: PType): PType =
 # ------------------- type iterator: ----------------------------------------
 type
   TTypeIter* = proc (t: PType, closure: RootRef): bool {.nimcall.} # true if iteration should stop
-  TTypeMutator* = proc (t: PType, closure: RootRef): PType {.nimcall.} # copy t and mutate it
+  TTypeMutator* = proc (t: PType, closure: RootRef): PType # copy t and mutate it
   TTypePredicate* = proc (t: PType): bool {.nimcall.}
 
 proc iterOverType*(t: PType, iter: TTypeIter, closure: RootRef): bool

[timotheecour]

@LemonBoy why not submit a PR with this? (easier for reviewers to test it out) if not I may submit one (and attribute you of course) to move forward with fixing this

[LemonBoy]

I'm waiting on some feedback about the underlying idea both from the user standpoint and the PL design one.
The patch should be cleaned up and made less memory-heavy if no implicit generic is introduced (copy-on-write should be rather easy to implement), but that's a tiny amount of trivial work and I'll have a go at it as soon as I receive some feedback (and am back at home :)

[zah]

Well, the rationale why bindOnce is the default behaviour for named type classes such as seq is that you can easily switch to the bindMany mode by just putting distinct in front of seq, while describing the bindOnce behaviour more explicitly requires adding extra named generic parameters as shown above.

In any case, this is a tricky language design issue with subtle tradeoffs, but we've already settled on the current rules quite a while ago and there should be a lot of code out there depending on the rules. The bindOnce default is often exploited in proc return types for example:

type Vector[T; N] = object # details omitted for clarity
proc `*`(v: Vector, s: float): Vector = ...

Relevant section from the manual:
https://nim-lang.org/docs/manual.html#generics-type-classes