Typescript: 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:

• https://github.com/microsoft/TypeScript/issues/30152 (maybe related)
• https://github.com/microsoft/TypeScript/issues/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?