After review, the only non-superficial change was to delegate the call
to under(...) to structuralType. Otherwise, update a few stale comments:
 + correct indices in the documentation for tparamsList
 + update smap->substMap in a few places
 + update type parameter syntax in a couple places

I've spent a good amount of time reviewing this code, and it
fundamentally LGTM (though I wish we didn't have to copy the logic from
identical0). However, as demonstrated in #43056, this code is
complicated and not always easy to reason about, particularly in the
context of type checking where not all types may be complete.

To further understand and verify this code I'd like to write more tests,
but that must wait until the rest of the changes in go/types are
imported from dev.go2go.

Change-Id: Iabb9d3a6af988a2e1b3445cde6bc2431a80f8bfe
Reviewed-on: https://go-review.googlesource.com/c/go/+/276692
Run-TryBot: Robert Findley <rfindley@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Robert Findley <rfindley@google.com>
Reviewed-by: Robert Griesemer <gri@golang.org>

…dent

If we have more than 2 arguments, we may have arguments with named and
unnamed types. If that is the case, permutate params and args such that
the arguments with named types are first in the list. This doesn't affect
type inference if all types are taken as is. But when we have inexact
unification enabled (as is the case for function type inference), when
a named type is unified with an unnamed type, unification proceeds with
the underlying type of the named type because otherwise unification would
fail right away. This leads to an asymmetry in type inference: in cases
where arguments of named and unnamed types are passed to parameters with
identical type, different types (named vs underlying) may be inferred
depending on the order of the arguments.
By ensuring that named types are seen first, order dependence is avoided
and unification succeeds where it can.

This CL implements the respectice code but keeps it disabled for now,
pending decision whether we want to address this issue in the first
place.

For #43056.

Change-Id: Ibe3b08ec2afe90a24a8c30cd1875d504bcc2ef39
Reviewed-on: https://go-review.googlesource.com/c/go/+/377894
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>

…dent

If we have more than 2 arguments, we may have arguments with named and
unnamed types. If that is the case, permutate params and args such that
the arguments with named types are first in the list. This doesn't affect
type inference if all types are taken as is. But when we have inexact
unification enabled (as is the case for function type inference), when
a named type is unified with an unnamed type, unification proceeds with
the underlying type of the named type because otherwise unification would
fail right away. This leads to an asymmetry in type inference: in cases
where arguments of named and unnamed types are passed to parameters with
identical type, different types (named vs underlying) may be inferred
depending on the order of the arguments.
By ensuring that named types are seen first, order dependence is avoided
and unification succeeds where it can.

This CL implements the respectice code but keeps it disabled for now,
pending decision whether we want to address this issue in the first
place.

For golang#43056.

Change-Id: Ibe3b08ec2afe90a24a8c30cd1875d504bcc2ef39
Reviewed-on: https://go-review.googlesource.com/c/go/+/377894
Trust: Robert Griesemer <gri@golang.org>
Run-TryBot: Robert Griesemer <gri@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>

If we have more than two function arguments to a generic function,
we may have arguments with named and unnamed types. If that is the
case, permutate params and args such that the arguments with named
types are first in the list. This way, independent of parameter
ordering, the type inference will produce the same result.

This extra step is not explicitly outlined in the spec yet but we
all agree that (parameter) order independence is an invariant that
we should uphold for type inference. As we move towards less
operational and more descriptive rules for type inference, we will
incorporate this property as well.

The actual fix for this bug existed before 1.18 but was not enabled.
This CL merely enables the fix (switches a flag) and adjusts some
tests.

Fixes golang#43056.

Change-Id: Ie4e40cf8438dfd82fa94b78068e4f6f6f53f83e6
Reviewed-on: https://go-review.googlesource.com/c/go/+/413459
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>

When unifying types, we always consider underlying types if inference
would fail otherwise. If a type parameter has a (non-defined) type
inferred and later matches against a defined type, make sure to keep
that defined type instead.

For #43056.

Change-Id: I24e4cd2939df7c8069e505be10914017c1c1c288
Reviewed-on: https://go-review.googlesource.com/c/go/+/464348
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>

When unifying types, we always consider underlying types if inference
would fail otherwise. If a type parameter has a (non-defined) type
inferred and later matches against a defined type, make sure to keep
that defined type instead.

For golang#43056.

Change-Id: I24e4cd2939df7c8069e505be10914017c1c1c288
Reviewed-on: https://go-review.googlesource.com/c/go/+/464348
Reviewed-by: Robert Griesemer <gri@google.com>
TryBot-Result: Gopher Robot <gobot@golang.org>
Reviewed-by: Robert Findley <rfindley@google.com>
Auto-Submit: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>