Perf regression: conditional type assignability

[amcasey]

Repro

npm install @types/react

index.ts

type Stuff<T> =
    T extends keyof JSX.IntrinsicElements
        ? JSX.IntrinsicElements[T]
        : any;

function F<T, U>(p1: Stuff<T>, p2: Stuff<U>) {
    p1 = p2; // Error
}

tsc index.ts --noEmit --skipLibCheck --extendedDiagnostifcs

Effect

Check time increased from ~0.5s in b2d1f53 to ~7.0s in 2643e65 (aka #30639).

Repro is reduced from a variance check of React's ComponentProps.

[amcasey]

FYI @andrewbranch, since it looks like the same PR caused #43249.

[weswigham]

Well, y'see, now we try to see if Stuff<?> is related to Stuff<?> by relating the branch types - where we get slow during that is when we're seeing if Stuff<?> is assignable to the (writing) constraint of the true branch, which is a check if Stuff<?> is assignable to SVGProps<SVGSymbolElement> & ClassAttributes<HTMLObjectElement> & ObjectHTMLAttributes<HTMLObjectElement> & ClassAttributes<HTMLAnchorElement> & AnchorHTMLAttributes<HTMLAnchorElement> & ClassAttributes<HTMLElement> & HTMLAttributes<HTMLElement> & ClassAttributes<HTMLAreaElement> & AreaHTMLAttributes<HTMLAreaElement> & ClassAttributes<HTMLAudioElement> & AudioHTMLAttributes<HTMLAudioElement> & ClassAttributes<HTMLBaseElement> & BaseHTMLAttributes<HTMLBaseElement> & BlockquoteHTMLAttributes<HTMLElement> & ClassAttributes<HTMLBodyElement> & HTMLAttributes<HTMLBodyElement> & ClassAttributes<HTMLBRElement> & HTMLAttributes<HTMLBRElement> & ClassAttributes<HTMLButtonElement> & ButtonHTMLAttributes<HTMLButtonElement> & ClassAttributes<HTMLCanvasElement> & CanvasHTMLAttributes<HTMLCanvasElement> & ClassAttributes<HTMLTableColElement> & ColHTMLAttributes<HTMLTableColElement> & ColgroupHTMLAttributes<HTMLTableColElement> & ClassAttributes<HTMLDataListElement> & HTMLAttributes<HTMLDataListElement> & DelHTMLAttributes<HTMLElement> & DetailsHTMLAttributes<HTMLElement> & ClassAttributes<HTMLDialogElement> & DialogHTMLAttributes<HTMLDialogElement> & ClassAttributes<HTMLDivElement> & HTMLAttributes<HTMLDivElement> & ClassAttributes<HTMLDListElement> & HTMLAttributes<HTMLDListElement> & ClassAttributes<HTMLEmbedElement> & EmbedHTMLAttributes<HTMLEmbedElement> & ClassAttributes<HTMLFieldSetElement> & FieldsetHTMLAttributes<HTMLFieldSetElement> & ClassAttributes<HTMLFormElement> & FormHTMLAttributes<HTMLFormElement> & ClassAttributes<HTMLHeadingElement> & HTMLAttributes<HTMLHeadingElement> & ClassAttributes<HTMLHeadElement> & HTMLAttributes<HTMLHeadElement> & ClassAttributes<HTMLHRElement> & HTMLAttributes<HTMLHRElement> & ClassAttributes<HTMLHtmlElement> & HtmlHTMLAttributes<HTMLHtmlElement> & ClassAttributes<HTMLIFrameElement> & IframeHTMLAttributes<HTMLIFrameElement> & ClassAttributes<HTMLImageElement> & ImgHTMLAttributes<HTMLImageElement> & ClassAttributes<HTMLInputElement> & InputHTMLAttributes<HTMLInputElement> & ClassAttributes<HTMLModElement> & InsHTMLAttributes<HTMLModElement> & KeygenHTMLAttributes<HTMLElement> & ClassAttributes<HTMLLabelElement> & LabelHTMLAttributes<HTMLLabelElement> & ClassAttributes<HTMLLegendElement> & HTMLAttributes<HTMLLegendElement> & ClassAttributes<HTMLLIElement> & LiHTMLAttributes<HTMLLIElement> & ClassAttributes<HTMLLinkElement> & LinkHTMLAttributes<HTMLLinkElement> & ClassAttributes<HTMLMapElement> & MapHTMLAttributes<HTMLMapElement> & MenuHTMLAttributes<HTMLElement> & ClassAttributes<HTMLMetaElement> & MetaHTMLAttributes<HTMLMetaElement> & MeterHTMLAttributes<HTMLElement> & ClassAttributes<HTMLOListElement> & OlHTMLAttributes<HTMLOListElement> & ClassAttributes<HTMLOptGroupElement> & OptgroupHTMLAttributes<HTMLOptGroupElement> & ClassAttributes<HTMLOptionElement> & OptionHTMLAttributes<HTMLOptionElement> & OutputHTMLAttributes<HTMLElement> & ClassAttributes<HTMLParagraphElement> & HTMLAttributes<HTMLParagraphElement> & ClassAttributes<HTMLParamElement> & ParamHTMLAttributes<HTMLParamElement> & ClassAttributes<HTMLPreElement> & HTMLAttributes<HTMLPreElement> & ClassAttributes<HTMLProgressElement> & ProgressHTMLAttributes<HTMLProgressElement> & ClassAttributes<HTMLQuoteElement> & QuoteHTMLAttributes<HTMLQuoteElement> & ClassAttributes<HTMLScriptElement> & ScriptHTMLAttributes<HTMLScriptElement> & ClassAttributes<HTMLSelectElement> & SelectHTMLAttributes<HTMLSelectElement> & ClassAttributes<HTMLSourceElement> & SourceHTMLAttributes<HTMLSourceElement> & ClassAttributes<HTMLSpanElement> & HTMLAttributes<HTMLSpanElement> & ClassAttributes<HTMLStyleElement> & StyleHTMLAttributes<HTMLStyleElement> & ClassAttributes<HTMLTableElement> & TableHTMLAttributes<HTMLTableElement> & ClassAttributes<HTMLTableSectionElement> & HTMLAttributes<HTMLTableSectionElement> & ClassAttributes<HTMLTableDataCellElement> & TdHTMLAttributes<HTMLTableDataCellElement> & ClassAttributes<HTMLTextAreaElement> & TextareaHTMLAttributes<HTMLTextAreaElement> & ClassAttributes<HTMLTableHeaderCellElement> & ThHTMLAttributes<HTMLTableHeaderCellElement> & TimeHTMLAttributes<HTMLElement> & ClassAttributes<HTMLTitleElement> & HTMLAttributes<HTMLTitleElement> & ClassAttributes<HTMLTableRowElement> & HTMLAttributes<HTMLTableRowElement> & ClassAttributes<HTMLTrackElement> & TrackHTMLAttributes<HTMLTrackElement> & ClassAttributes<HTMLUListElement> & HTMLAttributes<HTMLUListElement> & ClassAttributes<HTMLVideoElement> & VideoHTMLAttributes<HTMLVideoElement> & ClassAttributes<HTMLWebViewElement> & WebViewHTMLAttributes<HTMLWebViewElement> & SVGProps<SVGSVGElement> & SVGProps<SVGElement> & SVGProps<SVGCircleElement> & SVGProps<SVGClipPathElement> & SVGProps<SVGDefsElement> & SVGProps<SVGDescElement> & SVGProps<SVGEllipseElement> & SVGProps<SVGFEBlendElement> & SVGProps<SVGFEColorMatrixElement> & SVGProps<SVGFEComponentTransferElement> & SVGProps<SVGFECompositeElement> & SVGProps<SVGFEConvolveMatrixElement> & SVGProps<SVGFEDiffuseLightingElement> & SVGProps<SVGFEDisplacementMapElement> & SVGProps<SVGFEDistantLightElement> & SVGProps<SVGFEFloodElement> & SVGProps<SVGFEFuncAElement> & SVGProps<SVGFEFuncBElement> & SVGProps<SVGFEFuncGElement> & SVGProps<SVGFEFuncRElement> & SVGProps<SVGFEGaussianBlurElement> & SVGProps<SVGFEImageElement> & SVGProps<SVGFEMergeElement> & SVGProps<SVGFEMergeNodeElement> & SVGProps<SVGFEMorphologyElement> & SVGProps<SVGFEOffsetElement> & SVGProps<SVGFEPointLightElement> & SVGProps<SVGFESpecularLightingElement> & SVGProps<SVGFESpotLightElement> & SVGProps<SVGFETileElement> & SVGProps<SVGFETurbulenceElement> & SVGProps<SVGFilterElement> & SVGProps<SVGForeignObjectElement> & SVGProps<SVGGElement> & SVGProps<SVGImageElement> & SVGProps<SVGLineElement> & SVGProps<SVGLinearGradientElement> & SVGProps<SVGMarkerElement> & SVGProps<SVGMaskElement> & SVGProps<SVGMetadataElement> & SVGProps<SVGPathElement> & SVGProps<SVGPatternElement> & SVGProps<SVGPolygonElement> & SVGProps<SVGPolylineElement> & SVGProps<SVGRadialGradientElement> & SVGProps<SVGRectElement> & SVGProps<SVGStopElement> & SVGProps<SVGSwitchElement> & SVGProps<SVGTextElement> & SVGProps<SVGTextPathElement> & SVGProps<SVGTSpanElement> & SVGProps<SVGUseElement> & SVGProps<SVGViewElement>
IE: An intersection of every possible props object. Unfortunately, the first thing we then do is decompose that target elementwise, and we check if Stuff<?> is assignable to every element of that intersection. You'd think that'd fail real fast right (since a union of all props types being assigned to a single props type can't possibly work out)? Well... it doesn't. In fact, every comparison returns Maybe (except for the obvious exact match, which returns True)! This should come as a surprise - how is DetailedHTMLProps<AnchorHTMLAttributes<HTMLAnchorElement>, HTMLAnchorElement> maybe assignable to SVGProps<SVGSymbolElement>? Turtles. Our isDeeplyNestedType check is a bit... dumb? If the same type appears on the source side 5 times, source expanding flags are permanently set, same on the target side. Problem is, just breaking down the source and target side takes us 5 steps! So while we're decomposing the target, the source is static for 5 invocations, making the flag get set, then while we're decomposing the source side, the target is static for 5 invocations! By their powers combined, this makes a comparison that should have been marked as a False and thus a pretty fast early bail into a Maybe - and this repeats for all subsequent comparisons. If you simply increase the allowed repitition count in isDeeplyNestedType from 5 to 6, you cut away 80-90% of the compilation time!

[weswigham]

So, there's a quick and dirty "fix" - increasing the constant allowed dupe count in isDeeplyNestedType to 6 doesn't break anything noticeable, and fixes this perf issue. However, there's a more fundamental issue with how we're tracking source and target recursion that we could fix instead that I think would be more appropriate.

[weswigham]

And whatddoyouknow, I've already opened a PR with the fix 4 months ago to fix a different issue: #41821

[merlinnot]

Hi, I stumbled upon this issue when looking for a cause of a very slow compilation performance when using an open source project of mine. Let me know if an additional reproduction of slow performance with conditional types would help, I could share that easily. Thanks for working on fixing this!