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
Simplify recursive type tracking in type inference
  • Loading branch information
@ahejlsberg
ahejlsberg committed Aug 10, 2020
commit 5a45585b99cad062262f0d793573ed8b156ab1aa
63 changes: 17 additions & 46 deletions src/compiler/checker.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -19278,14 +19278,12 @@ namespace ts {
}

function inferTypes(inferences: InferenceInfo[], originalSource: Type, originalTarget: Type, priority: InferencePriority = 0, contravariant = false) {
let symbolOrTypeStack: (Symbol | Type)[];
let visited: ESMap<string, number>;
let bivariant = false;
let propagationType: Type;
let inferencePriority = InferencePriority.MaxValue;
let allowComplexConstraintInference = true;
let targetStackDepth = 0;
const targetStack: Type[] = [];
let visited: ESMap<string, number>;
let targetStack: Type[];
inferFromTypes(originalSource, originalTarget);

function inferFromTypes(source: Type, target: Type): void {
Expand Down Expand Up @@ -19408,7 +19406,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) {
invokeOnce(source, simplified, inferFromTypes);
invokeWithDepthLimit(source, simplified, inferFromTypes);
}
else if (target.flags & TypeFlags.IndexedAccess) {
const indexType = getSimplifiedType((target as IndexedAccessType).indexType, /*writing*/ false);
Expand All @@ -19417,7 +19415,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) {
invokeOnce(source, simplified, inferFromTypes);
invokeWithDepthLimit(source, simplified, inferFromTypes);
}
}
}
Expand Down Expand Up @@ -19478,7 +19476,7 @@ namespace ts {
source = apparentSource;
}
if (source.flags & (TypeFlags.Object | TypeFlags.Intersection)) {
invokeOnce(source, target, inferFromObjectTypes);
invokeWithDepthLimit(source, target, inferFromObjectTypes);
}
}
if (source.flags & TypeFlags.Simplifiable) {
Expand All @@ -19496,7 +19494,7 @@ namespace ts {
priority = savePriority;
}

function invokeOnce(source: Type, target: Type, action: (source: Type, target: Type) => void) {
function invokeWithDepthLimit(source: Type, target: Type, action: (source: Type, target: Type) => void) {
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.

This is pretty much the inference equivalent of recursiveTypeRelatedTo at this point.

const key = source.id + "," + target.id;
const status = visited && visited.get(key);
if (status !== undefined) {
Expand All @@ -19506,7 +19504,17 @@ namespace ts {
(visited || (visited = new Map<string, number>())).set(key, InferencePriority.Circularity);
const saveInferencePriority = inferencePriority;
inferencePriority = InferencePriority.MaxValue;
action(source, target);
// 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)) {
action(source, target);
}
else {
inferencePriority = InferencePriority.Circularity;
}
targetStack.pop();
visited.set(key, inferencePriority);
inferencePriority = Math.min(inferencePriority, saveInferencePriority);
}
Expand Down Expand Up @@ -19719,43 +19727,6 @@ namespace ts {
}

function inferFromObjectTypes(source: Type, target: Type) {
// If we are already processing another target type with the same associated symbol (such as
// an instantiation of the same generic type), we do not explore this target as it would yield
// no further inferences. We exclude the static side of classes from this check since it shares
// its symbol with the instance side which would lead to false positives.
const isNonConstructorObject = target.flags & TypeFlags.Object &&
!(getObjectFlags(target) & ObjectFlags.Anonymous && target.symbol && target.symbol.flags & SymbolFlags.Class);
const symbolOrType = getObjectFlags(target) & ObjectFlags.Reference && (target as TypeReference).node ? getNormalizedType(target, /*writing*/ false) : isNonConstructorObject ? isTupleType(target) ? target.target : target.symbol : undefined;
if (symbolOrType) {
if (contains(symbolOrTypeStack, symbolOrType)) {
// Don't set the circularity flag for re-encountered recursive type references just because we're already exploring them
if (!(getObjectFlags(target) & ObjectFlags.Reference && (target as TypeReference).node)) {
inferencePriority = InferencePriority.Circularity;
}
return;
}
(symbolOrTypeStack || (symbolOrTypeStack = [])).push(symbolOrType);
invokeWithDepthLimit(source, target, inferFromObjectTypesWorker);
symbolOrTypeStack.pop();
}
else {
inferFromObjectTypesWorker(source, target);
}
}

function invokeWithDepthLimit(source: Type, target: Type, action: (source: Type, target: Type) => void) {
targetStack[targetStackDepth] = target;
targetStackDepth++;
if (!isDeeplyNestedType(target, targetStack, targetStackDepth)) {
action(source, target);
}
else {
inferencePriority = InferencePriority.Circularity;
}
targetStackDepth--;
}

function inferFromObjectTypesWorker(source: Type, target: Type) {
if (getObjectFlags(source) & ObjectFlags.Reference && getObjectFlags(target) & ObjectFlags.Reference && (
(<TypeReference>source).target === (<TypeReference>target).target || isArrayType(source) && isArrayType(target))) {
// If source and target are references to the same generic type, infer from type arguments
Expand Down