cmd/compile: type inference: M does not match map[K]V

[bitfield]

What version of Go are you using (go version)?

devel go1.18-d15481b8c7 Fri Jan 21 01:14:28 2022 +0000

Does this issue reproduce with the latest release?

Yes.

What operating system and processor architecture are you using (go env)?

Go playground (gotip mode)

What did you do?

func Merge[M ~map[K]V, K comparable, V any](ms ...M) M {
	result := M{}
	for _, m := range ms {
		maps.Copy(result, m)
	}
	return result
}

https://go.dev/play/p/q50y-S0xAVm?v=gotip

What did you expect to see?

map[1:true]

What did you see instead?

./prog.go:14:12: M does not match map[K]V

Since M is ~map[K]V by definition, this is confusing me. If I explicitly instantiate maps.Copy to map[K]V, it works:

https://go.dev/play/p/SL4LNhpR3jB?v=gotip

It also works as expected if I define Merge this way:

func Merge[K comparable, V any](ms ...map[K]V) map[K]V {

But I noticed that the functions in maps have a more elegant signature:

func Copy[M ~map[K]V, K comparable, V any](dst, src M) {

And indeed I can use this, until I try to call a generic function with some M.

Shouldn't the compiler be able to infer the instantiating type here? I'm not sure if this is related to #50484 or #50319, but this is neither an interface nor a function type.

[ianlancetaylor]

CC @griesemer @findleyr

That error doesn't look right to me. Or, if it is right, I don't think the error message is very clear.

Here is a standalone version with type parameters renamed to avoid confusion.

package main

import (
	"fmt"
)

func Copy[MC ~map[KC]VC, KC comparable, VC any](dst, src MC) {
	for k, v := range src {
		dst[k] = v
	}
}

func Merge[MM ~map[KM]VM, KM comparable, VM any](ms ...MM) MM {
	result := MM{}
	for _, m := range ms {
		Copy(result, m)
	}
	return result
}

func main() {
	m1 := map[int]bool{1: false}
	m2 := map[int]bool{1: true}
	fmt.Println(Merge(m1, m2))
}

The error I get is

foo.go:16:7: MC does not match map[KC]VC

Function argument type inference should infer that the type argument for MC is the MM. Then constraint type inference should infer the type arguments for KC and VC from the structural constraint in maps.Copy. Then we should check whether MM satisfies the constraints. But the error message is talking about MC, KC, and VC. I'm not sure where that is coming from.

[gopherbot]

Change https://golang.org/cl/380375 mentions this issue: go/types: unify structural types for external type parameters

[findleyr]

Our unification algorithm did not unify the structural type of "external" type parameters (meaning, from another type parameter list), so constraint type inference just sees the opaque MM for MC when unifying with map[KC]VC, and fails.

https://golang.org/cl/380375 naively adds logic to unify with the structural type of external type parameters, if available. All tests pass, including this example, but I'm not sure if my mental model is correct.

At the very least we should improve the error message here. How important do we think it is to support this type of inference for 1.18?

[griesemer]

Thanks, @findleyr for picking this up so quickly. I should have time to look at this tomorrow.

[ianlancetaylor]

As far as I'm concerned we don't have to support this kind of type inference for 1.18, but I'd like to make sure that we understand it. Let me ask this: is that error message coming from type inference, or is it coming when checking whether the type arguments implement the type parameter constraints? Because type inference shouldn't produce that kind of error (and if it does it should ideally say something like "failed to infer types because..."). But I don't understand why constraint checking would produce that error either.

If I understand your comment correctly, I think you are suggesting that we use function argument type argument to infer that the argument for MC is MM. Then we try to apply constraint type checking and fail. And you are suggesting that when applying constraint type checking, if the type argument is itself a type parameter (or contains a type parameter?), and if that type parameter has a structural constraint, then we should consider that structural constraint. That seems plausible but it complicates the algorithm because in the map from type parameters to type arguments we would have to distinguish between the actual type argument and the structure of that type argument. Maybe that is fine.

[findleyr]

This error is coming from constraint type inference, when the interred type argument MM fails to unify with MC. I agree that we should improve the error message.

@ianlancetaylor, I think we're suggesting the same thing? You said:

Function argument type inference should infer that the type argument for MC is the MM. Then constraint type inference should infer the type arguments for KC and VC from the structural constraint in maps.Copy

That second step (constraint type inference) only works if we can look inside MM. Otherwise, we do not see KM or VM. So what I am suggesting is that in order to make this work, we need to consider the structural type of MM. The associated CL does this and works, but inference is very subtle.

[rogpeppe]

Two small remarks. Firstly: this doesn't seem to be about type-inference per-se, because presumably the inferred type in this case would be M, but passing that type explicitly still results in the same error: https://go.dev/play/p/WqgfFqpYvUN?v=gotip

Secondly: it is, in this case possible to work around the issue in at least two ways, either by converting the arguments to map[K]V explicitly (https://go.dev/play/p/QIjvu564hyZ?v=gotip), or by instantiating Copy as Copy[map[K]V] (https://go.dev/play/p/SL4LNhpR3jB?v=gotip)

[findleyr]

@rogpeppe passing [M, K, V] succeeds: https://go.dev/play/p/B6lswPpMIUa?v=gotip

This is about constraint type inference, which is the step that would infer K and V.

[griesemer]

Simplified reproducers:
This version fails due to internal stack overflow, a separate issue (#51158).

func f[M map[K]int, K comparable](m M) {
        f(m)
}

This version is a reduced reproducer of the original problem:

func f[M map[K]int, K comparable](m M) {}

func _[M map[K]int, K comparable](m M) {
	f(m)
}

[gopherbot]

Change https://go.dev/cl/385354 mentions this issue: go/types, types2: unify core types for unbound type parameters

[gopherbot]

Change https://go.dev/cl/385376 mentions this issue: go/types, types2: add additional tests using core types during unification