Conditional types incorrect for complex types

[ostrowr]

TypeScript Version: 3.7.2

I'm seeing incorrect behavior when I extend a computed type that's more than a few levels deep. When I explicitly define the type, I don't see the same behavior. I'm guessing that complex types are getting implicitly cast to any in this circumstance – tsc should probably either instantiate the correct type or cast them to unknown with a warning when they're too big.

This is admittedly a contrived example but I've run into similar issues when, for example, developing https://github.com/ostrowr/ts-json-validator

Search Terms:
depth, conditional types, extends, implicit any

Expected behavior:
shouldBeFalse and correctlyFalseWhenExpanded are both false (see code snippet below)

Actual behavior:
shouldBeFalse is True (i.e. 6 == 5 in my contrived version of Peano arithmetic)

Related Issues:

• Conditional types are incorrectly narrowed  #30152 (maybe related)
• [API Question] Is there a type resolution depth limit difference between compiling and running the language service? #29511 (discussion around implicit casts to any)

Code

type Natural = { prev: Natural }
type Zero = { prev: never }

type Equals<A extends Natural, B extends Natural> =
    A extends B ?
        B extends A ?
        true :
        false : 
    false

type S<T extends Natural> = { prev: T }

type One = S<Zero>
type Two = S<One>
type Three = S<Two>
type Four = S<Three>
type Five = S<Four>
type FiveByHand = { // this is the exact same type as Five, just manually expanded
    prev: {
        prev: {
            prev: {
                prev: {
                    prev: {
                        prev: never;
                    };
                };
            };
        };
    };
}
type Six = S<Five>
type SixByHand = { // this is the exact same type as Six, just manually expanded
    prev: {
        prev: {
            prev: {
                prev: {
                    prev: {
                        prev: {
                            prev: never;
                        };
                    };
                };
            };
        };
    };
}
type correctlyFalseForShallowTypes = Equals<Four, Five> // type: false
type correctlyTrue = Equals<Four, Four> // type: true
type shouldBeFalse = Equals<Five, Six> // type: true (should be false!)
type correctlyFalseWhenExpanded = Equals<FiveByHand, SixByHand> // type: false (as expected)

Output

"use strict";

Compiler Options

{
  "compilerOptions": {
    "noImplicitAny": true,
    "strictNullChecks": true,
    "strictFunctionTypes": true,
    "strictPropertyInitialization": true,
    "strictBindCallApply": true,
    "noImplicitThis": true,
    "noImplicitReturns": true,
    "useDefineForClassFields": false,
    "alwaysStrict": true,
    "allowUnreachableCode": false,
    "allowUnusedLabels": false,
    "downlevelIteration": false,
    "noEmitHelpers": false,
    "noLib": false,
    "noStrictGenericChecks": false,
    "noUnusedLocals": false,
    "noUnusedParameters": false,
    "esModuleInterop": true,
    "preserveConstEnums": false,
    "removeComments": false,
    "skipLibCheck": false,
    "checkJs": false,
    "allowJs": false,
    "declaration": true,
    "experimentalDecorators": false,
    "emitDecoratorMetadata": false,
    "target": "ES2017",
    "module": "ESNext"
  }
}

Playground Link: Provided

[rusev]

I think there is 5 level limit on recursive types.

This Build 2018 presentation is the source of my understanding. Though, might not be the case anymore after 3.7.*.

[ostrowr]

Whatever the limit is, I think TS should never implicitly cast something to any when --noImplicitAny is set

[RyanCavanaugh]

The limitation described in the Build talk is still accurate.

This isn't an "implicit casting to any"; it's a recursion guard to prevent literally infinite computation. If S<T> needs to compare itself to S<S<T>> to determine assignability, and then S<S<T>> needs to compare itself to S<S<S<T>>>, then S<S<S<T>>> needs to compare itself to S<S<S<S<T>>>>, then S<S<S<S<T>>>> needs to compare itself to S<S<S<S<S<T>>>>>, at that point the checking stops and it's assumed that the answer is "yes". This case actually does come up in practice quite a bit; if your model is dependent on this checking going arbitrarily deep, then effectively you're asking for the compiler to sometimes freeze forever checking S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<T>>>>>>>>>>>>>>>>>>>>>>>>> against S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<T>>>>>>>>>>>>>>>>>>>>>>>>>> (which in turn will check S<SS<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<T>>>>>>>>>>>>>>>>>>>>>>>>>>>.

[ostrowr]

Thanks, that makes sense – but I'm still a little wary of silently assuming the answer is "yes." Is it possible to issue a warning instead, or is it difficult to evaluate whether we're in this situation?

[ostrowr]

I believe this is actually fixed by #46599 – thanks!

This change means we'll do less work to detect and stop infinitely generated types, but will check manually nested types to any depth. Previously we couldn't distinguish between the two.

This is awesome. So, no longer a design limitation :)