Type inference algorithm in compiler differs from spec?

[osdm]

4.12.2 spec says:

Proceeding from left to right, each argument expression e is inferentially typed
...
When a function expression is inferentially typed (section 4.9.3) and a type assigned to a
parameter in that expression references type parameters for which inferences are being made, the
corresponding inferred type arguments to become fixed and no further candidate inferences are
made for them.

But it works differently in compiler. For example:

    function f<T, U>(y: T, f: (x: T) => U, x: T): [T, U] { return [y, f(x)]; }
    interface A { a: A; }
    interface B extends A { b; }

    var a: A, b: B;

    var d = f(b, x => x.a, a); // type [A, A]
    var d2 = f(b, x => x.a, null); // type [B, A]

If "no further candidate inferences were made", then types of d and d2 would be the same. But they are different.

[danquirk]

The spec needs to be updated. Loosely, the inference process is now 2 stages: first make inferences from non-function typed arguments, then do function typed arguments (and fix as necessary).

So in your first example the compiler infers from the 1st and 3rd argument (yielding A and B as candidates), then tries to infer from the 2nd argument (since it is a function type) which requires fixing T to the best common supertype of its current candidate set (which yields A). The second example uses the same process but because of the nulll argument A is not a candidate at the point where T is fixed so T is B.

[osdm]

I guess process is even more complicated.

    function f3<T, U>(y: T, y1: U, p: (z: U) => T, p1: (x: T) => U): [T, U] { return [y, p1(y)]; }
    // the same A, B, a, b as in previous example
    var e3 = f3(a, b, x => x, x => x); // type [A, A]

In this example, if U would be fixed when we would get to the 3rd argument, then it would yield B. But it somehow accounts for 4th argument also, yielding A again. Please, update the spec with actual method.

[JsonFreeman]

Yes, the spec needs to be updated. @osdm The observation you've made about the fourth argument is one that we've only recently discovered ourselves. In your example, it actually does 3 passes over the arguments:

1. Infer from arguments 1 and 2
2. Infer from arguments 1, 2, and 3, and fix U on argument 3
3. Infer from arguments 1, 2, 3 and 4, and fix T on argument 4

However, what you are noticing is that the fixing of argument 3 (from pass 2) does not persist to pass 3. So by the time we are on the 3rd pass and processing argument 4, we've forgotten that we fixed U in argument 3 in the second pass. Fun stuff!

[JsonFreeman]

Essentially, a type parameter can get unfixed after it gets fixed. All it takes is another pass after it got fixed (due to subsequent function arguments that have not been processed yet).

[osdm]

Well, this fun stuff leads to a very funny effect. Let me modify my example a little bit.

    interface A { a: A; }
    interface B extends A { b : B; }

    function func<T, U>(t1: T, u1: U, pf1: (u2: U) => T, pf2: (t2: T) => U): [T, U] { return [t1, pf2(t1)]; }
    var a: A, b: B;
    var result = func(a, b, u2 => u2.b, t2 => t2);

If we look at return type of func that was supplied to result, we would see that both T and U were inferred to be of type A. But this means that u2 should also be of type A. But type A doesn't have a property named "b", so there should be a error. But currently no error is reported, because u2 is really of type B. Could you please add an additional pass to reprocess all contextually typed functions after type inference is complete?

[JsonFreeman]

The fix I have in mind is actually that if we fixed U in the second pass, it stays fixed in the third pass. So in that case, the call would return [A, B] because we would not infer to U in the fourth argument. Then you would get an error because the fourth argument is of type A => A, which is not assignable to A => B.

The effect you described is the whole motivation for fixing in the first place. That's why I think we should not unfix, once we have fixed. I consider it a bug.

[osdm]

Ok, thanks. Will try to implement it in our tool as you described.