Changing generic weight of `tyGenericParam` (#22143)

This is in reference to a [feature
request](https://github.com/nim-lang/Nim/issues/22142) that I posted.

I'm making this PR to demonstrate the suggested change and expect that
this should be scrutinized

---------

Co-authored-by: Bung <crc32@qq.com>
Co-authored-by: Andreas Rumpf <rumpf_a@web.de>

11 files changed, 237 insertions, 89 deletions

diff --git a/compiler/sigmatch.nim b/compiler/sigmatch.nim
index 2dfab4d17..afbff1b38 100644
--- a/compiler/sigmatch.nim
+++ b/compiler/sigmatch.nim
@@ -213,8 +213,7 @@ proc sumGeneric(t: PType): int =
       inc result
     of tyBool, tyChar, tyEnum, tyObject, tyPointer, tyVoid,
         tyString, tyCstring, tyInt..tyInt64, tyFloat..tyFloat128,
-        tyUInt..tyUInt64, tyCompositeTypeClass, tyBuiltInTypeClass,
-        tyGenericParam:
+        tyUInt..tyUInt64, tyCompositeTypeClass, tyBuiltInTypeClass:
       inc result
       break
     of tyGenericBody:
@@ -233,6 +232,12 @@ proc sumGeneric(t: PType): int =
       t = t.elementType
       if t.kind == tyEmpty: break
       inc result
+    of tyGenericParam:
+      if t.len > 0:
+        t = t.skipModifier
+      else:
+        inc result
+        break
     of tyUntyped, tyTyped: break
     of tyGenericInvocation, tyTuple, tyAnd:
       result += ord(t.kind == tyAnd)
@@ -451,37 +456,40 @@ proc handleFloatRange(f, a: PType): TTypeRelation =
       else: result = isIntConv
     else: result = isNone
 
-proc getObjectType(f: PType): PType =
+proc reduceToBase(f: PType): PType =
   #[
-    Returns a type that is f's effective typeclass. This is usually just one level deeper
-    in the hierarchy of generality for a type. `object`, `ref object`, `enum` and user defined
-    tyObjects are common return values.
+    Returns the lowest order (most general) type that that is compatible with the input.
+    E.g.
+    A[T] = ptr object ... A -> ptr object
+    A[N: static[int]] = array[N, int] ... A -> array
   ]#
   case f.kind:
+  of tyGenericParam:
+    if f.len <= 0 or f.skipModifier == nil:
+      result = f
+    else:
+      result = reduceToBase(f.skipModifier)
   of tyGenericInvocation:
-    result = getObjectType(f.baseClass)
+    result = reduceToBase(f.baseClass)
   of tyCompositeTypeClass, tyAlias:
     if not f.hasElementType or f.elementType == nil:
       result = f
     else:
-      result = getObjectType(f.elementType)
+      result = reduceToBase(f.elementType)
   of tyGenericInst:
-    result = getObjectType(f.skipModifier)
+    result = reduceToBase(f.skipModifier)
   of tyGenericBody:
-    result = getObjectType(f.typeBodyImpl)
-
+    result = reduceToBase(f.typeBodyImpl)
   of tyUserTypeClass:
     if f.isResolvedUserTypeClass:
       result = f.base  # ?? idk if this is right
     else:
       result = f.skipModifier
   of tyStatic, tyOwned, tyVar, tyLent, tySink:
-    result = getObjectType(f.base)
+    result = reduceToBase(f.base)
   of tyInferred:
     # This is not true "After a candidate type is selected"
-    result = getObjectType(f.base)
-  of tyTyped, tyUntyped, tyFromExpr:
-    result = f
+    result = reduceToBase(f.base)
   of tyRange:
     result = f.elementType
   else:
@@ -1244,7 +1252,7 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
       result = typeRel(c, f.base, aOrig, flags + {trNoCovariance})
     subtypeCheck()
   of tyArray:
-    a = getObjectType(a)
+    a = reduceToBase(a)
     case a.kind
     of tyArray:
       var fRange = f.indexType
@@ -1370,7 +1378,7 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
     let effectiveArgType = if useTypeLoweringRuleInTypeClass:
         a
       else:
-        getObjectType(a)
+        reduceToBase(a)
     if effectiveArgType.kind == tyObject:
       if sameObjectTypes(f, effectiveArgType):
         result = isEqual
@@ -1400,7 +1408,7 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
             # set constructors are a bit special...
             result = isNone
   of tyPtr, tyRef:
-    a = getObjectType(a)
+    a = reduceToBase(a)
     if a.kind == f.kind:
       # ptr[R, T] can be passed to ptr[T], but not the other way round:
       if a.len < f.len: return isNone
@@ -1691,7 +1699,7 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
     considerPreviousT:
       let target = f.genericHead
       let targetKind = target.kind
-      var effectiveArgType = getObjectType(a)
+      var effectiveArgType = reduceToBase(a)
       effectiveArgType = effectiveArgType.skipTypes({tyBuiltInTypeClass})
       if targetKind == effectiveArgType.kind:
         if effectiveArgType.isEmptyContainer:
@@ -1785,7 +1793,7 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
         # check if 'T' has a constraint as in 'proc p[T: Constraint](x: T)'
         if f.len > 0 and f[0].kind != tyNone:
           let oldInheritancePenalty = c.inheritancePenalty
-          result = typeRel(c, f[0], a, flags + {trDontBind,trBindGenericParam})
+          result = typeRel(c, f[0], a, flags + {trDontBind, trBindGenericParam})
           if doBindGP and result notin {isNone, isGeneric}:
             let concrete = concreteType(c, a, f)
             if concrete == nil: return isNone
@@ -1811,10 +1819,11 @@ proc typeRel(c: var TCandidate, f, aOrig: PType,
           a.sym.transitionGenericParamToType()
           a.flags.excl tfWildcard
         elif doBind:
-          # The mechanics of `doBind` being a flag that also denotes sig cmp via
-          # negation is potentially problematic. `IsNone` is appropriate for
-          # preventing illegal bindings, but it is not necessarily appropriate
-          # before the bindings have been finalized.
+          # careful: `trDontDont` (set by `checkGeneric`) is not always respected in this call graph.
+          # typRel having two different modes (binding and non-binding) can make things harder to
+          # reason about and maintain. Refactoring typeRel to not be responsible for setting, or 
+          # at least validating, bindings can have multiple benefits. This is debatable. I'm not 100% sure.
+          # A design that allows a proper complexity analysis of types like `tyOr` would be ideal.
           concrete = concreteType(c, a, f)
           if concrete == nil:
             return isNone
@@ -2368,9 +2377,9 @@ proc paramTypesMatch*(m: var TCandidate, f, a: PType,
       # roll back the side effects of the unification algorithm.
       let c = m.c
       var
-        x = newCandidate(c, m.callee)
-        y = newCandidate(c, m.callee)
-        z = newCandidate(c, m.callee)
+        x = newCandidate(c, m.callee)  # potential "best"
+        y = newCandidate(c, m.callee)  # potential competitor with x
+        z = newCandidate(c, m.callee)  # buffer for copies of m
       x.calleeSym = m.calleeSym
       y.calleeSym = m.calleeSym
       z.calleeSym = m.calleeSym
diff --git a/doc/manual.md b/doc/manual.md
index 0e167be04..f2c8edd1f 100644
--- a/doc/manual.md
+++ b/doc/manual.md
@@ -2635,7 +2635,9 @@ of the argument.
    range.
 3. Generic match: `f` is a generic type and `a` matches, for
    instance `a` is `int` and `f` is a generic (constrained) parameter
-   type (like in `[T]` or `[T: int|char]`).
+   type (like in `[T]` or `[T: int|char]`). Constraints given an alias (as in `T`)
+   shall be used to define `f`, when `f` is composed of `T`, following simple variable
+   substitution.
 4. Subrange or subtype match: `a` is a `range[T]` and `T`
    matches `f` exactly. Or: `a` is a subtype of `f`.
 5. Integral conversion match: `a` is convertible to `f` and `f` and `a`
@@ -2647,9 +2649,8 @@ of the argument.
 There are two major methods of selecting the best matching candidate, namely
 counting and disambiguation. Counting takes precedence to disambiguation. In counting,
 each parameter is given a category and the number of parameters in each category is counted.
-The categories are listed above and are in order of precedence. For example, if
-a candidate with one exact match is compared to a candidate with multiple generic matches
-and zero exact matches, the candidate with an exact match will win.
+For example, if a candidate with one exact match is compared to a candidate with multiple
+generic matches and zero exact matches, the candidate with an exact match will win.
 
 In the following, `count(p, m)` counts the number of matches of the matching category `m`
 for the routine `p`.
@@ -2669,10 +2670,12 @@ algorithm returns true:
   return "ambiguous"
   ```
 
-When counting is ambiguous, disambiguation begins. Parameters are iterated
-by position and these parameter pairs are compared for their type relation. The general goal
-of this comparison is to determine which parameter is more specific. The types considered are
-not of the inputs from the callsite, but of the competing candidates' parameters.
+When counting is ambiguous, disambiguation begins. Disambiguation also has two stages, first a
+hierarchical type relation comparison, and if that is inconclusive, a complexity comparison.
+Where counting relates the type of the operand to the formal parameter, disambiguation relates the
+formal parameters with each other to find the most competitive choice.
+Parameters are iterated by position and these parameter pairs are compared for their type
+relation. The general goal of this comparison is to determine which parameter is least general.
 
 
 Some examples:
@@ -2692,7 +2695,6 @@ Some examples:
   ```
 
 
-If this algorithm returns "ambiguous" further disambiguation is performed:
 If the argument `a` matches both the parameter type `f` of `p`
 and `g` of `q` via a subtyping relation, the inheritance depth is taken
 into account:
@@ -2734,6 +2736,23 @@ matches) is preferred:
   gen(ri) # "ref T"
   ```
 
+Type variables match
+----------------------
+
+When overload resolution is considering candidates, the type variable's definition
+is not overlooked as it is used to define the formal parameter's type via variable substitution.
+
+For example:
+```nim
+type A
+proc p[T: A](param: T)
+proc p[T: object](param: T)
+```
+
+These signatures are not ambiguous for an instance of `A` even though the formal parameters match ("T" == "T").
+Instead `T` is treated as a variable in that (`T` ?= `T`) depending on the bound type of `T` at the time of
+overload resolution.
+
 
 Overloading based on 'var T'
 --------------------------------------
@@ -5424,6 +5443,7 @@ Generics are Nim's means to parametrize procs, iterators or types with
 `type parameters`:idx:. Depending on the context, the brackets are used either to
 introduce type parameters or to instantiate a generic proc, iterator, or type.
 
+
 The following example shows how a generic binary tree can be modeled:
 
   ```nim  test = "nim c $1"
diff --git a/tests/concepts/t976.nim b/tests/concepts/t976.nim
new file mode 100644
index 000000000..776d53827
--- /dev/null
+++ b/tests/concepts/t976.nim
@@ -0,0 +1,57 @@
+discard """
+  output: '''
+Printable
+'''
+joinable: false
+"""
+
+#[
+  The converter is a proper example of a confounding variable
+  Moved to an isolated file
+]#
+
+type
+  Obj1[T] = object
+      v: T
+converter toObj1[T](t: T): Obj1[T] =
+  return Obj1[T](v: t)
+block t976:
+  type
+    int1 = distinct int
+    int2 = distinct int
+    int1g = concept x
+      x is int1
+    int2g = concept x
+      x is int2
+
+  proc take[T: int1g](value: int1) =
+    when T is int2:
+      static: error("killed in take(int1)")
+
+  proc take[T: int2g](vale: int2) =
+    when T is int1:
+      static: error("killed in take(int2)")
+
+  var i1: int1 = 1.int1
+  var i2: int2 = 2.int2
+
+  take[int1](i1)
+  take[int2](i2)
+
+  template reject(e) =
+    static: assert(not compiles(e))
+
+  reject take[string](i2)
+  reject take[int1](i2)
+
+  # bug #6249
+  type
+      Obj2 = ref object
+      PrintAble = concept x
+          $x is string
+
+  proc `$`[T](nt: Obj1[T]): string =
+      when T is PrintAble: result = "Printable"
+      else: result = "Non Printable"
+
+  echo Obj2()
\ No newline at end of file
diff --git a/tests/concepts/tconcepts_issues.nim b/tests/concepts/tconcepts_issues.nim
index 83f3085c3..1d5e415dd 100644
--- a/tests/concepts/tconcepts_issues.nim
+++ b/tests/concepts/tconcepts_issues.nim
@@ -1,7 +1,6 @@
 discard """
   output: '''
 20.0 USD
-Printable
 true
 true
 true
@@ -78,55 +77,6 @@ block t3414:
   let s2 = s1.find(10)
 
 
-
-type
-  Obj1[T] = object
-      v: T
-converter toObj1[T](t: T): Obj1[T] =
-  return Obj1[T](v: t)
-block t976:
-  type
-    int1 = distinct int
-    int2 = distinct int
-    int1g = concept x
-      x is int1
-    int2g = concept x
-      x is int2
-
-  proc take[T: int1g](value: int1) =
-    when T is int2:
-      static: error("killed in take(int1)")
-
-  proc take[T: int2g](vale: int2) =
-    when T is int1:
-      static: error("killed in take(int2)")
-
-  var i1: int1 = 1.int1
-  var i2: int2 = 2.int2
-
-  take[int1](i1)
-  take[int2](i2)
-
-  template reject(e) =
-    static: assert(not compiles(e))
-
-  reject take[string](i2)
-  reject take[int1](i2)
-
-  # bug #6249
-  type
-      Obj2 = ref object
-      PrintAble = concept x
-          $x is string
-
-  proc `$`[T](nt: Obj1[T]): string =
-      when T is PrintAble: result = "Printable"
-      else: result = "Non Printable"
-
-  echo Obj2()
-
-
-
 block t1128:
   type
     TFooContainer[T] = object
diff --git a/tests/macros/tgetimpl.nim b/tests/macros/tgetimpl.nim
index e215d2696..ab33131b0 100644
--- a/tests/macros/tgetimpl.nim
+++ b/tests/macros/tgetimpl.nim
@@ -50,8 +50,6 @@ static:
     doAssert isSameOwner(poo, dummyproc) == false
   wrappedScope()
 
-#---------------------------------------------------------------
-
 macro check_gen_proc(ex: typed): (bool, bool) =
   let lenChoice = bindsym"len"
   var is_equal = false 
diff --git a/tests/overload/issue22142/tfail_implicit_ambiguous.nim b/tests/overload/issue22142/tfail_implicit_ambiguous.nim
new file mode 100644
index 000000000..2586e0877
--- /dev/null
+++ b/tests/overload/issue22142/tfail_implicit_ambiguous.nim
@@ -0,0 +1,10 @@
+discard """
+  errormsg: "ambiguous call"
+"""
+type
+  A[T] = object
+  C = object
+
+proc test[T: A](param: T): bool = false
+proc test(param: A): bool = true
+doAssert test(A[C]()) == true  # previously would pass
diff --git a/tests/overload/issue22142/tfail_nested_pointers.nim b/tests/overload/issue22142/tfail_nested_pointers.nim
new file mode 100644
index 000000000..1603d98cb
--- /dev/null
+++ b/tests/overload/issue22142/tfail_nested_pointers.nim
@@ -0,0 +1,12 @@
+discard """
+  errormsg: "ambiguous call"
+"""
+
+type
+  A[T] = object
+  C = object
+    x:int
+proc p[T: A[ptr]](x:ptr[T]):bool = false
+proc p(x: ptr[A[ptr]]):bool = true
+var a: A[ptr[C]]
+doAssert p(a.addr) == true
diff --git a/tests/overload/issue22142/tfail_object_is_generic.nim b/tests/overload/issue22142/tfail_object_is_generic.nim
new file mode 100644
index 000000000..b46795bd5
--- /dev/null
+++ b/tests/overload/issue22142/tfail_object_is_generic.nim
@@ -0,0 +1,16 @@
+discard """
+  errormsg: "ambiguous call"
+"""
+
+#[
+As of the time of writing `object` needs some special
+treament in order to be considered "generic" in the right
+context when used implicitly
+]#
+
+type
+  C = object
+
+proc test[T: object](param: T): bool = false
+proc test(param: object): bool = true  
+doAssert test(C()) == true  # previously would pass
diff --git a/tests/overload/issue22142/tfail_typeclass_var_invar.nim b/tests/overload/issue22142/tfail_typeclass_var_invar.nim
new file mode 100644
index 000000000..07db65fef
--- /dev/null
+++ b/tests/overload/issue22142/tfail_typeclass_var_invar.nim
@@ -0,0 +1,9 @@
+discard """
+  errormsg: "ambiguous call"
+"""
+
+type C = object
+proc test[T: ptr](param: var T): bool = false
+proc test(param: var ptr): bool = true
+var d: ptr[C]
+doAssert test(d) == true  # previously would pass
diff --git a/tests/overload/issue22142/tissue22142_shouldpass.nim b/tests/overload/issue22142/tissue22142_shouldpass.nim
new file mode 100644
index 000000000..90d4efe51
--- /dev/null
+++ b/tests/overload/issue22142/tissue22142_shouldpass.nim
@@ -0,0 +1,68 @@
+type
+  A[T] = object of RootObj
+  B[T] = object
+  C = object
+    x:int
+
+# change (previously true)
+block:
+  proc test[J;H: A[J];T: B[H]](param: T): bool = false
+  proc test[T](param: B[T]): bool = true
+  doAssert test(B[A[int]]()) == false
+block:  # object is more specific then `T`
+  proc p[H:object;T:ptr[H]](param:T):bool = false
+  proc p[T](param:ptr[T]):bool= true
+  var l: ptr[C]
+  doAssert p(l) == false
+block:
+  proc p[T:A[object]](param:T):bool = false
+  proc p[T](param: A[T]):bool= true
+  doAssert p(A[C]()) == false
+block:
+  proc test[H;T: A[H]](param: T): bool = false
+  proc test(param: A): bool = true
+  doAssert test(A[C]()) == false
+
+# change (previously ambiguous)
+block:
+  proc p[T](a: A[T]): bool = false
+  proc p[T: object](a: T): bool = true
+  doAssert p(A[int]()) == false
+block:  # A is more specific than `object`
+  proc test[T: A](param: T): bool = false
+  proc test[T: object](param: T): bool = true
+  doAssert test(A[int]()) == false
+block:
+  proc test[T: A](param: T): bool = false
+  proc test(param: object): bool = true
+  doAssert test(A[int]()) == false
+block:
+  proc test[H;T: A[H]](param: T): bool = false
+  proc test(param: object): bool = true
+  doAssert test(A[C]()) == false
+block:
+  proc test[H;T: A[B[H]]](param: T): bool = false
+  proc test[T: object](param: T): bool = true
+  doAssert test(A[B[int]]()) == false
+block:
+  #[
+  This was referenced in the nim compiler source (`sumGeneric`) as a case
+  that was supposed to not be ambiguous, yet it was
+  ]#
+  proc test[J;H:A[J]; T: A[H]](param: T): bool = false
+  proc test[H;T: A[H]](param: T): bool = true
+  doAssert test(A[A[C]]()) == false
+block:
+  proc test[J;T:A[J]](param: A[T]): bool = false
+  proc test[T](param: A[T]): bool = true
+  doAssert test(A[A[C]]()) == false
+block:
+  proc test[T](param: A[T]): bool = false
+  proc test[T: object](param: A[T]): bool = true
+  doAssert test(A[C]()) == true
+
+
+block: #anti-regression (object is more specific then `T`)
+  proc test[J;T:A[J]](param: A[T]): bool = false
+  proc test(param: A[A[object]]): bool = true
+  doAssert test(A[A[C]]()) == true
\ No newline at end of file
diff --git a/tests/overload/tor_isnt_better.nim b/tests/overload/tor_isnt_better.nim
index ce92009d0..be1ad67bf 100644
--- a/tests/overload/tor_isnt_better.nim
+++ b/tests/overload/tor_isnt_better.nim
@@ -7,7 +7,6 @@ block: # PR #22261
   proc d(x: int | D[SomeInteger]):bool= true
   doAssert d(D[5]()) == false
 
-
 block: # bug #8568
 #[
   Since PR #22261 and amendment has been made. Since D is a subset of D | E but