Skip to content

Recursive conditional types #40002

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
ahejlsberg merged 12 commits into from
Aug 16, 2020
Merged

Recursive conditional types #40002

Changes from 1 commit
Commits
Show all changes
12 commits
Select commit Hold shift + click to select a range
419e8d6
Support recursive conditional types
ahejlsberg Aug 8, 2020
beab30a
Accept new API baselines
ahejlsberg Aug 8, 2020
c24cacc
Accept new baselines
ahejlsberg Aug 8, 2020
5a45585
Simplify recursive type tracking in type inference
ahejlsberg Aug 10, 2020
4f8dc24
Accept new baselines
ahejlsberg Aug 10, 2020
dd64bf8
Add tests
ahejlsberg Aug 11, 2020
7c4d923
Accept new baselines
ahejlsberg Aug 11, 2020
6c11cf4
Revise recursion tracking in type inference
ahejlsberg Aug 13, 2020
5b45f42
Revise tests
ahejlsberg Aug 13, 2020
fed0e8c
Accept new baselines
ahejlsberg Aug 13, 2020
199d568
Add more tests
ahejlsberg Aug 16, 2020
324b3fb
Accept new baselines
ahejlsberg Aug 16, 2020
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
Prev Previous commit
Next Next commit
Revise recursion tracking in type inference
  • Loading branch information
@ahejlsberg
ahejlsberg committed Aug 13, 2020
commit 6c11cf462e975ade7cebae80675b609345bea514
64 changes: 41 additions & 23 deletions src/compiler/checker.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18201,15 +18201,24 @@ namespace ts {
return false;
}

function getRecursionIdentity(type: Type) {
// Types with constituents that could circularly reference the type have a recursion identity. The recursion
// identity is some object that is common to instantiations of the type with the same origin.
function getRecursionIdentity(type: Type): object | undefined {
if (type.flags & TypeFlags.Object && !isObjectOrArrayLiteralType(type)) {
if (type.symbol) {
// We track all object types that have an associated symbol (representing the origin of the type)
if (getObjectFlags(type) && ObjectFlags.Reference && (type as TypeReference).node) {
// Deferred type references are tracked through their associated AST node. This gives us finer
// granularity than using their associated target because each manifest type reference has a
// unique AST node.
return (type as TypeReference).node;
}
if (type.symbol && !(getObjectFlags(type) & ObjectFlags.Anonymous && type.symbol.flags & SymbolFlags.Class)) {
// We track all object types that have an associated symbol (representing the origin of the type), but
// exclude the static side of classes from this check since it shares its symbol with the instance side.
return type.symbol;
}
if (getObjectFlags(type) && ObjectFlags.Reference && (type as TypeReference).node || isTupleType(type)) {
// Deferred type references and tuple types are tracked through their target type
return (type as TypeReference).target;
if (isTupleType(type)) {
// Tuple types are tracked through their target type
return type.target;
}
}
if (type.flags & TypeFlags.IndexedAccess) {
Copy link
Member

@weswigham weswigham Aug 11, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Huh, and this doesn't affect the user baselines or DT?

Copy link
Member Author

@ahejlsberg ahejlsberg Aug 16, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No. Previously conditional types couldn't be recursive, so they weren't included here. But for that same reason we have no tests that could be affected by this.

Expand Down Expand Up @@ -19283,7 +19292,9 @@ namespace ts {
let inferencePriority = InferencePriority.MaxValue;
let allowComplexConstraintInference = true;
let visited: ESMap<string, number>;
let targetStack: Type[];
let sourceStack: object[];
let targetStack: object[];
let expandingFlags = ExpandingFlags.None;
inferFromTypes(originalSource, originalTarget);

function inferFromTypes(source: Type, target: Type): void {
Expand Down Expand Up @@ -19406,7 +19417,7 @@ namespace ts {
// Infer to the simplified version of an indexed access, if possible, to (hopefully) expose more bare type parameters to the inference engine
const simplified = getSimplifiedType(target, /*writing*/ false);
if (simplified !== target) {
invokeWithDepthLimit(source, simplified, inferFromTypes);
invokeOnce(source, simplified, inferFromTypes);
}
else if (target.flags & TypeFlags.IndexedAccess) {
const indexType = getSimplifiedType((target as IndexedAccessType).indexType, /*writing*/ false);
Expand All @@ -19415,7 +19426,7 @@ namespace ts {
if (indexType.flags & TypeFlags.Instantiable) {
const simplified = distributeIndexOverObjectType(getSimplifiedType((target as IndexedAccessType).objectType, /*writing*/ false), indexType, /*writing*/ false);
if (simplified && simplified !== target) {
invokeWithDepthLimit(source, simplified, inferFromTypes);
invokeOnce(source, simplified, inferFromTypes);
}
}
}
Expand Down Expand Up @@ -19443,7 +19454,7 @@ namespace ts {
inferFromTypes((<IndexedAccessType>source).indexType, (<IndexedAccessType>target).indexType);
}
else if (target.flags & TypeFlags.Conditional) {
invokeWithDepthLimit(<ConditionalType>source, <ConditionalType>target, inferToConditionalType);
invokeOnce(source, target, inferToConditionalType);
}
else if (target.flags & TypeFlags.UnionOrIntersection) {
inferToMultipleTypes(source, (<UnionOrIntersectionType>target).types, target.flags);
Expand Down Expand Up @@ -19476,7 +19487,7 @@ namespace ts {
source = apparentSource;
}
if (source.flags & (TypeFlags.Object | TypeFlags.Intersection)) {
invokeWithDepthLimit(source, target, inferFromObjectTypes);
invokeOnce(source, target, inferFromObjectTypes);
}
}
if (source.flags & TypeFlags.Simplifiable) {
Expand All @@ -19494,7 +19505,7 @@ namespace ts {
priority = savePriority;
}

function invokeWithDepthLimit(source: Type, target: Type, action: (source: Type, target: Type) => void) {
function invokeOnce(source: Type, target: Type, action: (source: Type, target: Type) => void) {
const key = source.id + "," + target.id;
const status = visited && visited.get(key);
if (status !== undefined) {
Expand All @@ -19504,17 +19515,24 @@ namespace ts {
(visited || (visited = new Map<string, number>())).set(key, InferencePriority.Circularity);
const saveInferencePriority = inferencePriority;
inferencePriority = InferencePriority.MaxValue;
// It is possible for recursion to originate in generative types that create infinitely deep instantiations,
// with unique identities, for example 'type RecArray<T> = T | Array<RecArray<T>>'. We explore up to five
// nested instantiations of such types using the same isDeeplyNestedType check as recursiveTypeRelatedTo.
(targetStack || (targetStack = [])).push(target);
if (!isDeeplyNestedType(target, targetStack, targetStack.length)) {
// We stop inferring and report a circularity if we encounter duplicate recursion identities on both
// the source side and the target side.
const saveExpandingFlags = expandingFlags;
const sourceIdentity = getRecursionIdentity(source);
const targetIdentity = getRecursionIdentity(target);
if (sourceIdentity && contains(sourceStack, sourceIdentity)) expandingFlags |= ExpandingFlags.Source;
if (targetIdentity && contains(targetStack, targetIdentity)) expandingFlags |= ExpandingFlags.Target;
if (expandingFlags !== ExpandingFlags.Both) {
if (sourceIdentity) (sourceStack || (sourceStack = [])).push(sourceIdentity);
if (targetIdentity) (targetStack || (targetStack = [])).push(targetIdentity);
Comment on lines +19526 to +19527
Copy link
Member

@DanielRosenwasser DanielRosenwasser Aug 14, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Suggested change
if (sourceIdentity) (sourceStack || (sourceStack = [])).push(sourceIdentity);
if (targetIdentity) (targetStack || (targetStack = [])).push(targetIdentity);
if (sourceIdentity) (sourceStack ||= []).push(sourceIdentity);
if (targetIdentity) (targetStack ||= []).push(targetIdentity);

Copy link
Member Author

@ahejlsberg ahejlsberg Aug 16, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'm going to leave it for now. We have lots of occurrences of that pattern, so maybe another PR to clean them all up.

action(source, target);
if (targetIdentity) targetStack.pop();
if (sourceIdentity) sourceStack.pop();
}
else {
inferencePriority = InferencePriority.Circularity;
}
targetStack.pop();
expandingFlags = saveExpandingFlags;
visited.set(key, inferencePriority);
inferencePriority = Math.min(inferencePriority, saveInferencePriority);
}
Expand Down Expand Up @@ -19710,12 +19728,12 @@ namespace ts {
return false;
}

function inferToConditionalType(source: ConditionalType, target: ConditionalType) {
function inferToConditionalType(source: Type, target: ConditionalType) {
if (source.flags & TypeFlags.Conditional) {
inferFromTypes(source.checkType, target.checkType);
inferFromTypes(source.extendsType, target.extendsType);
inferFromTypes(getTrueTypeFromConditionalType(source), getTrueTypeFromConditionalType(target));
inferFromTypes(getFalseTypeFromConditionalType(source), getFalseTypeFromConditionalType(target));
inferFromTypes((<ConditionalType>source).checkType, target.checkType);
inferFromTypes((<ConditionalType>source).extendsType, target.extendsType);
inferFromTypes(getTrueTypeFromConditionalType(<ConditionalType>source), getTrueTypeFromConditionalType(target));
inferFromTypes(getFalseTypeFromConditionalType(<ConditionalType>source), getFalseTypeFromConditionalType(target));
}
else {
const savePriority = priority;
Expand Down