Improve recursion depth checks - #46599
Conversation
Sorry, something went wrong.
|
TypeScript Bot (@typescript-bot) perf test faster |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the extended test suite on this PR at 86185ad. You can monitor the build here. |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the parallelized Definitely Typed test suite on this PR at 86185ad. You can monitor the build here. |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the abridged perf test suite on this PR at 86185ad. You can monitor the build here. Update: The results are in! |
Sorry, something went wrong.
|
TypeScript Bot (@typescript-bot) user test this inline |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the inline community code test suite on this PR at 86185ad. You can monitor the build here. Update: The results are in! |
Sorry, something went wrong.
|
Anders Hejlsberg (@ahejlsberg) |
Sorry, something went wrong.
|
Anders Hejlsberg (@ahejlsberg) Comparison Report - main..46599
System
Hosts
Scenarios
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sorry, something went wrong.
|
TypeScript Bot (@typescript-bot) perf test faster |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the parallelized Definitely Typed test suite on this PR at 52e10d3. You can monitor the build here. |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the abridged perf test suite on this PR at 52e10d3. You can monitor the build here. Update: The results are in! |
Sorry, something went wrong.
|
Heya Anders Hejlsberg (@ahejlsberg), I've started to run the inline community code test suite on this PR at 52e10d3. You can monitor the build here. Update: The results are in! |
Sorry, something went wrong.
|
Anders Hejlsberg (@ahejlsberg) Comparison Report - main..46599
System
Hosts
Scenarios
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Sorry, something went wrong.
|
Anders Hejlsberg (@ahejlsberg) |
Sorry, something went wrong.
|
TypeScript Bot (@typescript-bot) perf test faster |
Sorry, something went wrong.
| return getTypeReferenceId(source as TypeReference, typeParameters) + "," + getTypeReferenceId(target as TypeReference, typeParameters) + postFix; | ||
| } | ||
| return source.id + "," + target.id + postFix; | ||
| return isTypeReferenceWithGenericArguments(source) && isTypeReferenceWithGenericArguments(target) ? |
There was a problem hiding this comment.
I've been wondering this for awhile and worked on a change for a bit, but can/should we expand this detailed id generation to generic type-alias'd types as well (and not just type references), so type alias relations can also benefit from the broadest-equivalent-id check?
Sorry, something went wrong.
Wesley Wigham (weswigham)
left a comment
There was a problem hiding this comment.
I like the structure of this - the broadestEquivalentId check is ultimately an approximation; ideally we'd be able to note all relations that are strictly a specialization of an ongoing relation check and know to bail, but the id comparison is a pretty cheap way to check something close to that and hits the very common example of recursion during variance computations. Thus, any changes that make us pick up more equivalent ids in a cheap way is generally welcome. The depth detection changes are a bit more worrysome - doesn't the id-increasing check mean that repeated usages of the exact same type id no longer count as "deeply nested"? I guess the assumption there is that deep nesting that isn't generative in some way must form a cycle at some point which will be detected. Still - definitely has the potential to convert some "quietly works" code into "loudly breaks with a stack depth error" code.
Sorry, something went wrong.
Actually no, we still include identical type IDs in the count. We only skip counting when we see a lower type ID. My comments aren't exactly clear on that, I'll revise. |
Sorry, something went wrong.
|
Oh, I know, but we could have a check sequence like 1,2,1,1,1,1,... and previously we'd have marked it as deep (5x repeated 1), whereas because of the 2, now we won't. |
Sorry, something went wrong.
|
Actually, we will mark that as deep because we always compare against the previous type ID, not the highest type ID. |
Sorry, something went wrong.
|
Oh, so I see. I guess that means 1,2,3,4,3,2,1 won't be marked as deep (the last 3,2,1 won't be counted), but 1,2,3,4,1,2,3 will (4 -> 1 won't count, but 1->2 and 2->3 will), even though it's just a reordering of the same types. |
Sorry, something went wrong.
|
TypeScript Bot (@typescript-bot) cherry-pick this to release-4.5 |
Sorry, something went wrong.
|
Heya Daniel Rosenwasser (@DanielRosenwasser), I've started to run the task to cherry-pick this into release-4.5 on this PR at 9df07a8. You can monitor the build here. |
Sorry, something went wrong.
|
Hey Daniel Rosenwasser (@DanielRosenwasser), I've opened #46974 for you. |
Sorry, something went wrong.
Component commits: ddc106b Decrease recursion depth limit to 3 + smarter check for recursion 86185ad Accept new baselines 52e10d3 Always set last type id 5f37d89 Keep indexed access recursion depth check 9df07a8 Less expensive and corrected check for broadest equivalent keys Co-authored-by: Anders Hejlsberg <andersh@microsoft.com>
* Decrease recursion depth limit to 3 + smarter check for recursion * Accept new baselines * Always set last type id * Keep indexed access recursion depth check * Less expensive and corrected check for broadest equivalent keys
|
Hi, I want to point a small regression that I believe has been introduced by this PR 😕 Alas I haven't been able to isolate a MNWE after 1 day trying to extract code from my project and reaching 200 lines in the non so minimal and still working example 😞 TLDR: This project builds in TS4.5.2 but doesn't in TS 4.5.3 (nor in 4.5.5). We are building recursive type but controlling the recursion through a type Depths = [-1, 0, 1, 2] (ensuring Depths[D] = D-1), then the type looks like (over simplified) type Nested<T, D extends number = 3> = D extends -1 ? T : Nested<T, Depths[D]>. The D parameter ensures that type recursion stops… Of course, the actual type is much more crazy. It models an "interview" which is a sequence of questions (asked to an oracle), where each question expects a typed answer (T is a representation of this type (e.g. "boolean", "string[]"), and A is the actual corresponding type (e.g. boolean, Array<string>); the QUESTION parameter is meta-data mapping the questions' URI to their type). An interview may contains several questions in a row (hence the recursion), and the depth is used to make sure the type works. The type itself does build in TS 4.5.3, but then the way we use it (through yet some other layers of complication) breaks… I don't really consider this as a bug. Feels more like a very corner case… Plus haven't been able to get a MWNE to study… But I guess you might want to hear about it 😊 |
Sorry, something went wrong.
This PR improves relationship checking for recursive types in a number of ways:
The change to computing equivalent IDs improves type checking performance by 2-5%. Our performance test suites don't contain examples of infinitely generated types, so the depth check changes show no effect there. However, several Definitely Typed packages see dramatic improvement. For example, redux-immutable, react-lazylog, and yup all see at least a 50% reduction in check time.