It's basically Hindley-Milner.

[FeepingCreature]

On Friday, 24 March 2023 at 09:30:30 UTC, FeepingCreature wrote:
> You're misunderstanding the problem.
>
> When you call a template function, DMD (and C++) performs IFTI, 
> implicit function template instantiation. This requires 
> *reverse-engineering* a type T that fulfills the requirement 
> for the function call.

It's important to understand that IFTI does something *completely 
different* than normal type inference: it does *backwards* type 
inference. It's more similar to [Hindley-Milner] than D's normal 
"forward" type resolution.

For instance, if you write a template like this:

```
void foo(T)(void delegate(T) dg) { }
foo((int i) {});
```

Then the compiler infers `T` as `int` by recursing on the 
expression "`void delegate(T)` = `void delegate(int)`". It takes 
the explicit template parameters and calling parameter types and 
uses them as nodes in an algebraic system, that it can use to 
*solve for* the template parameter types.

Or if you write a template like this:

```
T foo(T)(T a, T b) { }
foo(2, 3.5);
```

Then the compiler starts with two algebraic expressions: `int : 
T` and `double : T` (`:` meaning "is convertible to"), which it 
solves by *unifying* `int` and `double` into `double`.

It is important to understand that `T` here is a **free 
variable**, not yet a type; the point is to *assign it* a type. 
So we cannot instantiate a template with `T`, because we can only 
instantiate templates with concrete types.

Finally, in our example:

```
alias A(T) = B!T;
void foo(T)(A!T) {}
foo(B!int);
```

The compiler starts with an expression `B!int = A!T`, and is 
trying to solve for T.

It looks at `A!T`, and it thinks: "hm, the other term could be a 
template instantiation of the template `A` with something." But 
`B!T` is a template instantiation of `B`, not `A`, so it fails to 
match.

If we insert the missing step, what the compiler should do is: 
"Ah, `B` is a 'trivial alias' (like `using` in C++), so I can 
*syntactically substitute* it with its content", and create the 
new expression `B!int = B!T`. Then it can resolve this by noting 
that *the concrete type* `B!int` is an instance of `B` with the 
type `int`, and thus gain the new expression `T = int`, which 
solves the algebraic system.

[Hindley-Milner]: 
https://en.wikipedia.org/wiki/Hindley%E2%80%93Milner_type_system