Conditional types can cause TS to miss incorrect interface extensions

[errendir]

Conditional types can cause TS to miss incorrect interface extensions

TypeScript Version: 2.9.2, 3.0.0-dev.20180630

Search Terms: conditional types, interfaces, extensions, assignability, substitutability, recursive types

Introduction:

I really appreciate the introduction of conditional types in TypeScript. They solve many problems that couldn't be solved before. Just the ReturnType<T> alone is priceless.

Unfortunately I think there is a new class of issues introduced by the presence of conditional types. Those issues relate to the verification whether an interface properly extends another interface.

When interface B<T> is declared as extending interface A (interface B<T> extends A { ... }) and no error is reported in such interface declaration, I expect that for every type T, A<T> will be assignable (substitutable) for B. I don't know if this property of the type system has a name, but it's listed in the language spec (https://github.com/Microsoft/TypeScript/blob/master/doc/spec.md#71-interface-declarations) as:

The this-type (section 3.6.3) of the declared interface must be assignable (section 3.11.4) to each of the base type references.

It appears that when verifying if A<T> is assignable to B TypeScript replaces the type of members with conditional type following the pattern X extends Y ? A : B with A | B. This ensures that only if either type is assignable to the type of the corresponding member of A, B<T> will be assignable to A. However this replacement can be avoided with certain tricks (see the code below). This leads to a situation where the B<T> extends A declaration is verified yet for certain types T the type B<T> is not assignable to A.

Code

type Cryptic = { cryptic: "cryptic" }
type IsCryptic<MaybeCryptic> = MaybeCryptic extends Cryptic ? 1 : 0
const any: any = 0

interface A {
  mustBeZero: 0
}

type Confuse<A> = [A] & A

// This should report the "Interface 'B<T>' incorrectly extends interface 'A'." error
interface B<T> extends A {
  mustBeZero: IsCryptic<Confuse<T>>
}

// The above extension is allowed yet B<T> is not assignable to A for some T:
const incorrect: A = any as B<Cryptic>

In the above example inlining IsCryptic<MaybeCryptic> solves the problem (the expected error is returned by tsc).

A different version of the same issue can be encountered when the type parameter T is constrained in the extending interface.

type Cryptic = { cryptic: "cryptic" }
type IsCryptic<MaybeCryptic> = MaybeCryptic extends Cryptic ? 1 : 0
const any: any = 0

interface A {
  mustBeZero: 0
}

type SomeOtherType = { value: number }

interface B<T extends SomeOtherType> extends A {
  mustBeZero: IsCryptic<T>
}

// The above extension is allowed yet B<SomeOtherType & T> is not assignable to A for some T:
const incorrect: A = any as B<SomeOtherType & Cryptic>

In the above example inlining IsCryptic<MaybeCryptic> does not help.

Here is yet another way to force an interface extension to pass. In this example even the concrete types of the incompatible interfaces are allowed to be assigned. Only the attempt to assign the right members of both types result in an eventual error:

interface RecurseToZero<T> {
  recurse: RecurseToZero<[T,T]>
  mustBeZero: 0
}

interface RecurseToWhat<T> extends RecurseToZero<T> {
  recurse: RecurseToWhat<[T,T]>
  // The type of "mustBeZero" member will be different from 0 only on a certain recursion depth
  mustBeZero: T extends [infer T1, infer T2]
            ? T1 extends [infer T3, infer T4]
            ? T3 extends [infer T5, infer T6]
            ? T5 extends [infer T7, infer T8]
            ? T7 extends [infer T9, infer T10]
              ? 1
              : 0 : 0 : 0 : 0 : 0
}

// The above extension is allowed and the type RecurseToWhat<null> appears to be assignable to RecurseToZero<null>:
declare let a: RecurseToZero<null>
declare let b: RecurseToWhat<null>
a = b

// Yet the above should not be allowed because the type RecurseToWhat<null> is not structurally assignable to RecurseToZero<null>:
a.recurse.recurse.recurse.recurse.mustBeZero = b.recurse.recurse.recurse.recurse.mustBeZero

// This is because on the certain depths of recursion of the RecurseToWhat<T> the type of "mustBeZero" is 1:
type Zero = RecurseToZero<null>["recurse"]["recurse"]["recurse"]["recurse"]["mustBeZero"]
type What = RecurseToWhat<null>["recurse"]["recurse"]["recurse"]["recurse"]["mustBeZero"]
const incorect: Zero = any as What

I believe this particular problem is caused by the way TypeScript compiler avoids infinite assignability checks on recursive types. As far as I could deduce from the code, type checker will avoid verifying the assignability of the same members of the same interfaces more than once. The type arguments of the interfaces will be ignored in order not to loop forever through the ever-growing type argument.

Verifying if RecurseToWhat<T> is assignable to RecurseToZero<T> required verifying if RecurseToWhat<[T,T]> is assignable to RecurseToZero<[T,T]> which in turn requires trying with the [[T,T],[T,T]] type argument and so on. To avoid endless computations TypeScript allows for at most only one level of recursion per member of the interface. This however is not enough now, because due to the conditional types it is possible to make the assignability of RecurseToWhat<T> to RecurseToZero<T> fail only for an arbitrarily complex T.

This particular issue can also be replicated without the use of extending interfaces:

interface RecurseToZeroP<T> {
  recurse: RecurseToZeroP<[T,T]>
  mustBeZero: 0
}

type RecurseToZero = RecurseToZeroP<null>

interface RecurseToWhatP<T> {
  recurse: RecurseToWhatP<[T,T]>
  // The type of "mustBeZero" member will be different from 0 only on a certain recursion depth
  mustBeZero: T extends [infer T1, infer T2]
            ? T1 extends [infer T3, infer T4]
            ? T3 extends [infer T5, infer T6]
            ? T5 extends [infer T7, infer T8]
            ? T7 extends [infer T9, infer T10]
              ? 1
              : 0 : 0 : 0 : 0 : 0
}

type RecurseToWhat = RecurseToWhatP<null>

// The type RecurseToWhat appears to be assignable to RecurseToZero:
declare let a: RecurseToZero
declare let b: RecurseToWhat
a = b

// Yet the above should not be allowed because the type RecurseToWhat is not structurally assignable to RecurseToZero:
a.recurse.recurse.recurse.recurse.mustBeZero = b.recurse.recurse.recurse.recurse.mustBeZero

// This is because on the certain depths of recursion the type of "mustBeZero" is 1
type Zero = RecurseToZero["recurse"]["recurse"]["recurse"]["recurse"]["mustBeZero"]
type What = RecurseToWhat["recurse"]["recurse"]["recurse"]["recurse"]["mustBeZero"]
const incorect: Zero = any as What

Expected behavior:

The declarations interface B<T> extends A { ... }, interface B<T extends SomeOtherType> extends A { ... } and interface RecurseToWhat<T> extends RecurseToZero<T> { ... } should fail with the appropriate error listing the correct path through incompatible members, for example:

Interface 'B<T>' incorrectly extends interface 'A'.
  Types of property 'mustBeZero' are incompatible.
    Type 'IsCryptic<Confuse<T>>' is not assignable to type '0'.
      Type '0 | 1' is not assignable to type '0'.
        Type '1' is not assignable to type '0'.

The last code example should fail on the a = b assignment.

Actual behavior:

All of the interface declarations are parsed without the compile-time error. Only the attempts to actually assign a variable of a certain concrete type of the interface B<T> to A will fail.

In the example 4, the problem goes even further. The two created types (RecurseToZero and RecurseToWhat) seemingly appear to be assignable (RecurseToWhat to RecurseToZero). Only the attempt to assign certain nested members of the corresponding types reveals the error.

Playground Link: link

Related Issues: None to my knowledge. Please link to some if you find them.

Fully structural assignability

Things get more interesting if we change the example 4 to allow two separate paths on each recursion level. In such a situation it seems that the work TypeScript would need to perform in order to find whether the types are actually structurally equivalent could be equivalent to solving a propositional logic satisfiability problem:

enum True { true = "true" }
enum False { false = "false" }

type And<Bool1,Bool2> = Bool1 extends True ? Bool2 extends True ? True : False : False
type Or<Bool1, Bool2> = Bool1 extends True ? True : Bool2 extends True ? True : False
type Not<Bool> = Bool extends False ? True : Bool extends True ? False : never

interface RecurseToFalseP<T> {
  recurseWithTrue: RecurseToFalseP<[T,True]>
  recurseWithFalse: RecurseToFalseP<[T,False]>
  mustBeFalse: False
}

type RecurseToFalse = RecurseToFalseP<null>

interface RecurseToPropsitionP<T> {
  recurseWithTrue: RecurseToPropsitionP<[T,True]>
  recurseWithFalse: RecurseToPropsitionP<[T,False]>
  // The type of "mustBeFalse" member will be different from False only when T represents the assignment satisfying propositional logic statement hardcoded below
  mustBeFalse: T extends [infer R6, infer T7]
            ? R6 extends [infer R5, infer T6]
            ? R5 extends [infer R4, infer T5]
            ? R4 extends [infer R3, infer T4]
            ? R3 extends [infer R2, infer T3]
            ? R2 extends [infer R1, infer T2]
            ? R1 extends [null, infer T1]
              ? And<And<And<Or<And<T1,T2>,Not<Or<T3,T4>>>,T5>,T6>,T7> // propsitional logic with T1, ..., TK variables goes here
              : False : False : False : False : False : False : False
}

type RecurseToPropsition = RecurseToPropsitionP<null>

// The type RecurseToPropsition appears to be assignable to RecurseToZero:
declare let a: RecurseToFalse
declare let b: RecurseToPropsition
a = b

// In order for the TypeScript to find the member path breaking the structural assignability it needs to solve the satisfiability problem for the propsition hardcoded in RecurseToPropsitionP<T>:
a
  .recurseWithTrue.recurseWithTrue
  .recurseWithFalse.recurseWithFalse
  .recurseWithTrue.recurseWithTrue.recurseWithTrue
  .mustBeFalse 
  =
b
  .recurseWithTrue.recurseWithTrue
  .recurseWithFalse.recurseWithFalse
  .recurseWithTrue.recurseWithTrue.recurseWithTrue
  .mustBeFalse

This is a famously NP-complete problem. So if P != NP there is no polynomial way to decide whether two types are structurally equivalent.

[unao]

Not sure what you exactly meant by The above extension is allowed... but incorrect produces an error Type 'B<Cryptic>' is not assignable to type 'A'. Types of property 'mustBeZero' are incompatible. Type '1' is not assignable to type '0'..

Another thing is that type Confuse<A> = [A] & A does not introduce much confusion as it is assignable to both [A] and A. Did you mean [A] | A?

[errendir]

Thanks for your comment. By "The above extension is allowed" I meant that the interface declaration:

interface B<T> extends A {
  mustBeZero: IsCryptic<Confuse<T>>
}

causes no compile-time error. In my opinion it should.

In the line const incorrect: A = any as B<Cryptic>, I attempt to assign object of type B<Cryptic> to A in order to show that the interface declaration of B<T> should not have been allowed. My point is that without the const incorrect: A = any as B<Cryptic> you get the code that compiles, but in my opinion it shouldn't.

The purpose of the type Confuse<A> = [A] & A is to "confuse" TypeScript with regard to what the exact type of the "mustBeZero" member of the B<T> interface is. I am not sure why [A] & A has such an effect on the type checker, but [A] | A doesn't showcase the issue I am trying to describe.

[unao]

One thing which may be connected to what you are describing is DeepReadonly<T>, which was present (or at least candidate for 2.8) but then disappeared.

[RyanCavanaugh]

@DanielRosenwasser