Skip to content

typechecking does not terminate on contrived recursive type #27073

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
fictitious opened this issue Sep 13, 2018 · 4 comments
Closed

typechecking does not terminate on contrived recursive type #27073

fictitious opened this issue Sep 13, 2018 · 4 comments
Labels
Bug A bug in TypeScript
Milestone

Comments

@fictitious
Copy link

TypeScript Version: 3.1.0-dev.20180913

Search Terms:

typechecking infinite recursion

Code

export type DirectoryBase = {name: string}

export type DirectoryEntries = {readonly [n in string]: Directory};

export type Directory = DirectoryBase & {entries: DirectoryEntries};

export type ExactDirectory<E extends DirectoryEntries> = DirectoryBase & {entries: E};


export type Accessor<D extends Directory> = 
    D extends Directory ? {[K in keyof D['entries']]: Accessor<D['entries'][K]>} : {};


// intersection and conditional type are necessary to exhibit the problem
export type BadAccessor<D extends Directory> = {

} & (D extends Directory ? {[K in keyof D['entries']]: Accessor<D['entries'][K]>} : {});



function f<E extends DirectoryEntries, C extends Directory>(accessor: Accessor<C>): void {

    const a1 = accessor as Accessor<ExactDirectory<E>>; // ok, error as expected

    const a2 = accessor as BadAccessor<ExactDirectory<E>>; // boom
}

Expected behavior:

compilation error is reported

Actual behavior:

apparently, compilation does not terminate

Playground Link: nope WARNING pasting the above code to the playground freezes the playground UI, and because it remembers the code you are stuck forever. Browsers start warning about unresponsive page after a while.

Related Issues:
might be the same as #27066 but observed behavior is different

@mattmccutchen
Copy link
Contributor

Possible duplicate of #26314?

@RyanCavanaugh RyanCavanaugh added the Bug A bug in TypeScript label Sep 14, 2018
@RyanCavanaugh RyanCavanaugh added this to the Future milestone Sep 14, 2018
@RyanCavanaugh
Copy link
Member

I'm assuming "contrived" here means this what at least somewhat constructed instead of being "found" in real code - let me know if that's not the case. With Turing completeness sometimes comes nontermination 🤷‍♂️

@fictitious
Copy link
Author

It was constructed in the process of writing code, and that code was supposed to become real. "Contrived" in this context means "expressing some constraints which would be useful to enforce in client code".

The thing is, some usages of such a type are typechecked just fine, and I found only one case so far where it's problematic, and I can bypass this one easily because it happened in the implementation code where I could just use type assertion as any, so it's not that important.

@jakebailey
Copy link
Member

I've been poking around old ancient issues; this looks to have been fixed in TS 3.3 (with an exact bisect to #29338).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Bug A bug in TypeScript
Projects
None yet
Development

No branches or pull requests

4 participants