8000 Improve performance of maybe stack in recursiveTypeRelatedTo by jakebailey · Pull Request #55224 · microsoft/TypeScript · GitHub
[go: up one dir, main page]
Skip to content

Improve performance of maybe stack in recursiveTypeRelatedTo #55224

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.

Sign up for GitHub

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

Merged
jakebailey merged 10 commits into from
Aug 3, 2023
Merged

Improve performance of maybe stack in recursiveTypeRelatedTo #55224

Changes from all commits
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
0009999
Improve performance of maybe stack in recursiveTypeRelatedTo
jakebailey Aug 1, 2023
a703f48
Maybe improve perf
jakebailey Aug 1, 2023
9e0cf58
Cleanup and docs
jakebailey Aug 1, 2023
0907e76
Remove commented out code
jakebailey Aug 1, 2023
c31d069
Re-add debug check on push, it's fast enough
jakebailey Aug 1, 2023
42d68cb
Pass the value to stop after rather than calling each time
jakebailey Aug 1, 2023
b1ceaf2
Merge branch 'main' into fix-54939
jakebailey Aug 3, 2023
6e3f4c5
Remove abstraction per Anders' feedback
jakebailey Aug 3, 2023
b59f2b6
Remove reference to popping from comment
jakebailey Aug 3, 2023
6156ade
Make parameter required
jakebailey Aug 3, 2023
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
39 changes: 29 additions & 10 deletions src/compiler/checker.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20361,6 +20361,7 @@ export function createTypeChecker(host: TypeCheckerHost): TypeChecker {
let errorInfo: DiagnosticMessageChain | undefined;
let relatedInfo: [DiagnosticRelatedInformation, ...DiagnosticRelatedInformation[]] | undefined;
let maybeKeys: string[];
let maybeKeysSet: Set<string>;
let sourceStack: Type[];
let targetStack: Type[];
let maybeCount = 0;
Expand Down Expand Up @@ -21237,27 +21238,32 @@ export function createTypeChecker(host: TypeCheckerHost): TypeChecker {
}
if (!maybeKeys) {
maybeKeys = [];
maybeKeysSet = new Set();
sourceStack = [];
targetStack = [];
}
else {
// If source and target are already being compared, consider them related with assumptions
if (maybeKeysSet.has(id)) {
return Ternary.Maybe;
}

// A key that starts with "*" is an indication that we have type references that reference constrained
// type parameters. For such keys we also check against the key we would have gotten if all type parameters
// were unconstrained.
const broadestEquivalentId = id.startsWith("*") ? getRelationKey(source, target, intersectionState, relation, /*ignoreConstraints*/ true) : undefined;
for (let i = 0; i < maybeCount; i++) {
// If source and target are already being compared, consider them related with assumptions
if (id === maybeKeys[i] || broadestEquivalentId && broadestEquivalentId === maybeKeys[i]) {
return Ternary.Maybe;
}
if (broadestEquivalentId && maybeKeysSet.has(broadestEquivalentId)) {
return Ternary.Maybe;
}

if (sourceDepth === 100 || targetDepth === 100) {
overflow = true;
return Ternary.False;
}
}
const maybeStart = maybeCount;
maybeKeys[maybeCount] = id;
maybeKeysSet.add(id);
maybeCount++;
const saveExpandingFlags = expandingFlags;
if (recursionFlags & RecursionFlags.Source) {
Expand Down Expand Up @@ -21313,20 +21319,33 @@ export function createTypeChecker(host: TypeCheckerHost): TypeChecker {
if (result === Ternary.True || result === Ternary.Maybe) {
// If result is definitely true, record all maybe keys as having succeeded. Also, record Ternary.Maybe
// results as having succeeded once we reach depth 0, but never record Ternary.Unknown results.
for (let i = maybeStart; i < maybeCount; i++) {
relation.set(maybeKeys[i], RelationComparisonResult.Succeeded | propagatingVarianceFlags);
}
resetMaybeStack(/*markAllAsSucceeded*/ true);
}
else {
resetMaybeStack(/*markAllAsSucceeded*/ false);
}
maybeCount = maybeStart;
}
// Note: it's intentional that we don't reset in the else case;
// we leave them on the stack such that when we hit depth zero
// above, we can report all of them as successful.
}
else {
// A false result goes straight into global cache (when something is false under
// assumptions it will also be false without assumptions)
relation.set(id, (reportErrors ? RelationComparisonResult.Reported : 0) | RelationComparisonResult.Failed | propagatingVarianceFlags);
maybeCount = maybeStart;
resetMaybeStack(/*markAllAsSucceeded*/ false);
}
return result;

function resetMaybeStack(markAllAsSucceeded: boolean) {
for (let i = maybeStart; i < maybeCount; i++) {
maybeKeysSet.delete(maybeKeys[i]);
if (markAllAsSucceeded) {
relation.set(maybeKeys[i], RelationComparisonResult.Succeeded | propagatingVarianceFlags);
}
}
maybeCount = maybeStart;
}
}

function structuredTypeRelatedTo(source: Type, target: Type, reportErrors: boolean, intersectionState: IntersectionState): Ternary {
Expand Down
0