TypeScript: [Performance] Adding just one more method causes check time to jump from 2s to 100+s

@AnyhowStep nowadays we issue a Type instantiation is excessively deep and possibly infinite. error and terminate pretty quickly on the code given here, yeah? So this has been “fixed” by one of our other limiters - at least we acknowledge our own limitations now.

In this example the types under consideration are… complex:

What seems to be going on is that every FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>> we encounter as we descend through the comparison expands - namely it becomes a IFluentMapper<T> & T - and since there’s no “base case” there as we keep descending on generic types - we’ll look at a IFluentMapper<IFluentMapper<T> & T> & IFluentMapper<T> & T, then a IFluentMapper<IFluentMapper<IFluentMapper<T> & T> & IFluentMapper<T> & T> & IFluentMapper<IFluentMapper<T> & T> & IFluentMapper<T> & T and so on until we hit a depth limiter, then crawl back out and continue down another branch doing the same. That depth limit is pretty high, and gets expontentiated in comparison time when the comparison is re-performed multiple times with different type parameters (as each copy of derived has unique type parameters).

Fixing this may require something similar to an insight I has while working on https://github.com/microsoft/TypeScript/pull/31633 - namely that while we’re measuring weather IFoo<T> is assignable to IFoo<U>, asking if IFoo<Q> is assignable to IFoo<J> should already be assumed to be true, assuming Q is related to J as T is related to U.

Okay, even shorter repro, removing rename<>(),

Playground

type UnionToIntersection<U> = (
    (
        U extends any ? (k: U) => void : never
    ) extends (
        (k: infer I) => void
    ) ? I : never
);

interface Mapper<HandledInputT, OutputT> {
    (name : string, mixed : HandledInputT) : OutputT,
}
type AnyMapper = (
    Mapper<any, any>
);
type SafeMapper<OutputT> = (
    Mapper<unknown, OutputT>
);

type AnySafeMapper = (
    SafeMapper<any>
);
interface ExpectedInput<T> {
    __expectedInput? : [T],
}
interface MappableInput<T> {
    __mappableInput? : [T],
}
type OutputOf<F extends AnyMapper> = (
    ReturnType<F>
);
type ExpectedInputOfImpl<F extends AnyMapper> = (
    F extends Mapper<infer T, any> ?
    (
        unknown extends T ?
        (
            F extends ExpectedInput<infer T> ?
            [T] :
            F extends MappableInput<infer T> ?
            [T] :
            [OutputOf<F>]
        ) :
        [T]
    ) :
    never
);
type ExpectedInputOf<F extends AnyMapper> = (
    Extract<
        UnionToIntersection<ExpectedInputOfImpl<F>>,
        [any]
    >[0]
);
type MappableInputOfImpl<F extends AnyMapper> = (
    F extends Mapper<infer T, any> ?
    (
        unknown extends T ?
        (
            F extends MappableInput<infer T> ?
            [T] :
            F extends ExpectedInput<infer T> ?
            [T] :
            [OutputOf<F>]
        ) :
        [T]
    ) :
    never
);
type MappableInputOf<F extends AnyMapper> = (
    Extract<
        UnionToIntersection<MappableInputOfImpl<F>>,
        [any]
    >[0]
);
interface Optional {
    __optional : true,
}
type IsOptional<F extends AnySafeMapper> = (
    F extends Optional ?
    (
        undefined extends MappableInputOf<F> ?
        true :
        false
    ) :
    false
);

type IsExpectedInputOptional<F extends AnySafeMapper> = (
    IsOptional<F> extends true ?
    (
        undefined extends ExpectedInputOf<F> ?
        true :
        false
    ) :
    false
);

type DeriveMapper<
    SrcKeyT extends string,
    DstKeyT extends string,
    F extends AnySafeMapper
> = (
    & SafeMapper<
        { [dst in DstKeyT] : OutputOf<F> }
    >
    & ExpectedInput<
        IsExpectedInputOptional<F> extends true ?
        { [src in SrcKeyT]? : ExpectedInputOf<F> } :
        { [src in SrcKeyT] : ExpectedInputOf<F> }
    >
    & MappableInput<
        IsOptional<F> extends true ?
        { [src in SrcKeyT]? : MappableInputOf<F> } :
        { [src in SrcKeyT] : MappableInputOf<F> }
    >
);

type FluentMapper<F extends AnySafeMapper> = (
    & IFluentMapper<F>
    & F
);
interface IFluentMapper<F extends AnySafeMapper> {
    derive<
        SrcKeyT extends string,
        DstKeyT extends string
    > (
        srcKey : SrcKeyT,
        dstKey : DstKeyT
    ) : (
        FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>>
    );

    //Uncomment this block to warm yourself up during winter
    //*
    derive2<
        SrcKeyT extends string,
        DstKeyT extends string
    > (
        srcKey : SrcKeyT,
        dstKey : DstKeyT
    ) : (
        FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>>
    );
    //*/
    //Uncomment this block to warm yourself up during winter
    //*
    derive3<
        SrcKeyT extends string,
        DstKeyT extends string
    > (
        srcKey : SrcKeyT,
        dstKey : DstKeyT
    ) : (
        FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>>
    );
    //*/
    //Uncomment this block to warm yourself up during winter
    //*
    derive4<
        SrcKeyT extends string,
        DstKeyT extends string
    > (
        srcKey : SrcKeyT,
        dstKey : DstKeyT
    ) : (
        FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>>
    );
    //*/
}

declare function derive<
    SrcKeyT extends string,
    DstKeyT extends string,
    F extends AnySafeMapper
> (
    srcKey : SrcKeyT,
    dstKey : DstKeyT,
    f : F
) : (
    DeriveMapper<SrcKeyT, DstKeyT, F>
);
/**
    MODIFIES THE FUNCTION `f`!
    DOES NOT RETURN A NEW FUNCTION.
*/
function fluentMapper<F extends AnySafeMapper> (f : F) : FluentMapper<F> {
    const result : FluentMapper<F> = f as any;

    //Comment out the `as any` to see it freak out.
    result.derive = (<
        SrcKeyT extends string,
        DstKeyT extends string
    > (
        srcKey : SrcKeyT,
        dstKey : DstKeyT
    ) : (
        FluentMapper<DeriveMapper<SrcKeyT, DstKeyT, F>>
    ) => {
        return fluentMapper(derive(srcKey, dstKey, f)) /**/as any;
    }) /**/as any;
    return result;
}

Files:           131
Lines:         38675
Nodes:        172620
Identifiers:   57549
Symbols:       84830
Types:         36126
Memory used: 128812K
I/O read:      0.01s
I/O write:     0.03s
Parse time:    0.45s
Bind time:     0.28s
Check time:    5.84s
Emit time:     0.48s
Total time:    7.04s

Comment out both as any parts,

Playground

Now, it takes forever.