stack overflow in recursive type alias + lookup type

[HerringtonDarkholme]

Extracted from #14833

TypeScript Version: 2.2.1 / nightly (2.2.0-dev.201xxxxx)

Code

type Foo<T extends "true", B> = { "true": Foo<T, Foo<T, B>> }[T];
let f: Foo<"true", {}> = null!;

Expected behavior:
An error reporting cyclic dependency.

Actual behavior:

Throw RangeError: Maximum call stack size exceeded

[hediet]

But without this, TypeScript's type system is most probably not turing complete any more :(

[RyanCavanaugh]

We should just detect ahead of time whether or not a given type relation check will eventually halt

[HerringtonDarkholme]

I've seen similar bug in Scala since 2.8 and fixed in 2.11 or so. Other (industry) languages also prioritize consistency over power.

To achieve type system consistence we need to, sadly, abstain from Turing completeness.

@hediet Your proof is very amazing and smart!

[HerringtonDarkholme]

Another piece of strange code, it compiles but should not.

type Foo<T extends "true"> = { "true": Foo<'false'> }[T]; // should report error on 'false'
let f: Foo<"true"> = null!;

[mattdsteele]

@RyanCavanaugh Just an FYI, #14837 (comment) literally made me laugh out loud. Cheers! 🎉