Go Generic Inference as LeetCode Problems¶

Go's generic type inference is hard to read if I start from unify.go, infer.go, and call.go directly. A simpler way is to treat it like a small set of LeetCode problems: each problem has a clear input, a target behavior, and a check for whether the model is good enough.

Idea from Yuchen. Text written by AI.

This is not a full explanation of the compiler. It is only a compact scaffold for reading the source later.

Problem 1: Match Two Type Trees¶

Given two type trees:

• template: may contain type parameters such as T
• concrete: contains real types such as int, []string, or *User

Implement unify(template, concrete).

Rules:

1. If both nodes have the same outer shape, compare their children.
2. If the template node is a type parameter, record the answer.
3. If the shapes differ, fail.

Example:

template: []T
concrete: []int
answer:   T = int

The core idea is a lock-step DFS: compare the outer shell first, then recurse into the inside.

Source anchor: (*unifier).nify in unify.go.

Problem 2: Keep Repeated Variables Consistent¶

Now T can appear more than once.

Example:

template: func(T, T)
concrete: func(int, string)
answer:   fail

The first argument says T = int, while the second says T = string. The solver must reject that.

A more useful case:

template: func(T, U), with T == U
concrete: func(int, int)
answer:   T = int, U = int

In the compiler this is not just map[TypeParam]Type. It uses handles, so two type parameters can point to the same inferred state after join.

Source anchor: newUnifier, join, setHandle, at, and set in unify.go.

Problem 3: Support Loose Top-Level Matching¶

Named types make exact matching too strict.

Example:

type MyInt int

In assignment mode, MyInt may match int at the top level, because the underlying type is int. But this looseness does not simply apply everywhere: inside container elements, the compiler switches back toward exact matching.

LeetCode version:

1. Try exact shape matching.
2. If the current mode allows assignment, compare the underlying type.
3. When recursing into element types, tighten the mode again.

Source anchor: unifyMode and the assign handling in unify.go.

Problem 4: Solve Inner Generic Calls Without Polluting Outer State¶

Consider:

func F[T any](x T) {
    G(x)
}

func G[U any](y U) {}

While solving G, the solver should infer U = T. It should not mutate the outer T state by accident.

LeetCode version:

1. The inner solver owns only U.
2. Outer T is treated as a symbolic type.
3. The result is a mapping like U = T.
4. Later substitution can turn it into U = int if outer T = int.

For recursive generic calls, the compiler also renames type parameters so the inner call has fresh identities.

Source anchor: asBoundTypeParam in unify.go and renameTParams in infer.go.

Problem 5: Repeat Until No More Types Can Be Found¶

Some type parameters are not solved by arguments directly.

Example:

func F[T any, U ~[]T, V ~*U](x T) {}

If x is int, then:

pass 1: T = int
pass 2: U = []int
pass 3: V = *[]int

LeetCode version:

1. Start with direct answers from call arguments.
2. Scan unsolved variables.
3. Substitute known answers into constraints.
4. Repeat while progress is made.
5. Stop when all variables are solved or no new answer appears.

This is the fixed-point part of inference.

Source anchor: (*Checker).infer in infer.go.

Summary¶

The useful mental model is small:

1. DFS matches type structure.
2. Handles keep repeated type parameters consistent.
3. Assignment mode allows limited top-level flexibility.
4. Inner generic calls solve against their own variables.
5. Constraint inference repeats until it reaches a fixed point.

That is enough scaffolding before reading the real compiler code.