Typescript: conditional types type A is not assignable to type B

[emmanueltouzery]

TypeScript Version: 2.9.0-dev.20180324

Search Terms:
conditional types, is not assignable to type

Code

export class Option<T> {
    toVector(): Vector<T> {
        return <any>undefined;
    }
}

interface Seq<T> {
    tail(): Option<Seq<T>>;
}

class Vector<T> implements Seq<T> {

    tail(): Option<Vector<T>> {
        return <any>undefined;
    }

     // the next line breaks the compilation
    partition2<U extends T>(predicate:(v:T)=>v is U): [Vector<U>,Vector<Exclude<T,U>>];
    partition2(predicate:(x:T)=>boolean): [Vector<T>,Vector<T>];
    partition2<U extends T>(predicate:(v:T)=>boolean): [Vector<U>,Vector<any>] {
        return <any>undefined;
    }
}

Expected behavior:
it should compile without errors

Actual behavior:
doesn't compile (when built with --strict). If you comment the first overload for partition2 (which uses conditional types), then it builds OK.

The build error is:

t.ts(13,5): error TS2416: Property 'tail' in type 'Vector<T>' is not assignable to the same property in base type 'Seq<T>'.
  Type '() => Option<Vector<T>>' is not assignable to type '() => Option<Seq<T>>'.
    Type 'Option<Vector<T>>' is not assignable to type 'Option<Seq<T>>'.
      Types of property 'toVector' are incompatible.
        Type '() => Vector<Vector<T>>' is not assignable to type '() => Vector<Seq<T>>'.
          Type 'Vector<Vector<T>>' is not assignable to type 'Vector<Seq<T>>'.
            Types of property 'tail' are incompatible.
              Type '() => Option<Vector<Vector<T>>>' is not assignable to type '() => Option<Vector<Seq<T>>>'.
                Type 'Option<Vector<Vector<T>>>' is not assignable to type 'Option<Vector<Seq<T>>>'.
                  Types of property 'toVector' are incompatible.
                    Type '() => Vector<Vector<Vector<T>>>' is not assignable to type '() => Vector<Vector<Seq<T>>>'.
                      Type 'Vector<Vector<Vector<T>>>' is not assignable to type 'Vector<Vector<Seq<T>>>'.
                        Types of property 'tail' are incompatible.
                          Type '() => Option<Vector<Vector<Vector<T>>>>' is not assignable to type '() => Option<Vector<Vector<Seq<T>>>>'.
                            Type 'Option<Vector<Vector<Vector<T>>>>' is not assignable to type 'Option<Vector<Vector<Seq<T>>>>'.
                              Types of property 'toVector' are incompatible.
                                Type '() => Vector<Vector<Vector<Vector<T>>>>' is not assignable to type '() => Vector<Vector<Vector<Seq<T>>>>'.
                                  Type 'Vector<Vector<Vector<Vector<T>>>>' is not assignable to type 'Vector<Vector<Vector<Seq<T>>>>'.
                                    Types of property 'tail' are incompatible.
                                      Type '() => Option<Vector<Vector<Vector<Vector<T>>>>>' is not assignable to type '() => Option<Vector<Vector<Vector<Seq<T>>>>>'.
                                        Type 'Option<Vector<Vector<Vector<Vector<T>>>>>' is not assignable to type 'Option<Vector<Vector<Vector<Seq<T>>>>>'.
                                          Types of property 'toVector' are incompatible.
                                            Type '() => Vector<Vector<Vector<Vector<Vector<T>>>>>' is not assignable to type '() => Vector<Vector<Vector<Vector<Seq<T>>>>>'.
                                              Type 'Vector<Vector<Vector<Vector<Vector<T>>>>>' is not assignable to type 'Vector<Vector<Vector<Vector<Seq<T>>>>>'.
                                                Type 'Vector<Vector<Vector<Seq<T>>>>' is not assignable to type 'Vector<Vector<Vector<Vector<T>>>>'.

I've first posted a question on stackoverflow:
https://stackoverflow.com/questions/49468849/type-a-is-not-assignable-to-type-b-with-typescript-2-8-conditional-types

And the consensus there was that this is a typescript bug. I've tried to search for duplicates but didn't find anything for which I could be sure that it's the same issue...

A comment from another stackoverflow user:

The conditional type is definitely causing something weird to happen in the type checker. The type checker seems to be trying to verify that Vector is assignable to Seq, chasing down an infinite regress, bailing out, and failing.

[jcalz]

Here's what looks like a minimal reproduction to me:

interface A<T> {
    bat: B<A<T>>;
}

interface B<T> extends A<T> {
//        ^ error reported here
    bat: B<B<T>>;

    // comment out next line to remove error
    boom: T extends any ? true : true
}

The boom property of B causes the type checker to go into what looks like an infinite regress trying to verify that B<T> extends A<T> even though that's a given. It then bails out (which is good) with a failure (which is less good).

[ahejlsberg]

This is a subtle one!

The core issue is that we're missing a type relationship for conditional types: ~Two conditional types T1 extends U1 ? X1 : Y1 and T2 extends U2 ? X2 : Y2 should be considered related if X1 | Y1 is related to X2 | Y2. In other words, the types are related if every possible outcome of the first type is related to every possible outcome of the second type.~ Two conditional types T1 extends U1 ? X1 : Y1 and T2 extends U2 ? X2 : Y2 should be considered related if one or both of T1 and T2 is related to the other, U1 and U2 are identical types, X1 is related to X2, and Y1 is related to Y2. This is a slight relaxation of an already existing relationship that required T1 and T2 to be identical.

Because we're missing this relationship, when, in --strictFunctionTypes mode, we measure variance for type parameters of generic class and interface types, any type parameter referenced in a conditional type ends up being considered invariant, and that's what's causing the errors.

It's an easy fix, I will have a PR up soon.