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

Show file tree
Hide file tree
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
Next Next commit
Support recursive conditional types
  • Loading branch information
@ahejlsberg
ahejlsberg committed Aug 8, 2020
commit 419e8d6eb56f1a14b912118baba61ef009f9341e
154 changes: 68 additions & 86 deletions src/compiler/checker.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -13809,19 +13809,19 @@ namespace ts {
if (!(inferredExtendsType.flags & TypeFlags.AnyOrUnknown) && (checkType.flags & TypeFlags.Any || !isTypeAssignableTo(getPermissiveInstantiation(checkType), getPermissiveInstantiation(inferredExtendsType)))) {
// Return union of trueType and falseType for 'any' since it matches anything
if (checkType.flags & TypeFlags.Any) {
(extraTypes || (extraTypes = [])).push(instantiateTypeWithoutDepthIncrease(root.trueType, combinedMapper || mapper));
(extraTypes || (extraTypes = [])).push(instantiateType(getTypeFromTypeNode(root.node.trueType), combinedMapper || mapper));
}
// If falseType is an immediately nested conditional type that isn't distributive or has an
// identical checkType, switch to that type and loop.
const falseType = root.falseType;
const falseType = getTypeFromTypeNode(root.node.falseType);
if (falseType.flags & TypeFlags.Conditional) {
const newRoot = (<ConditionalType>falseType).root;
if (newRoot.node.parent === root.node && (!newRoot.isDistributive || newRoot.checkType === root.checkType)) {
root = newRoot;
continue;
}
}
result = instantiateTypeWithoutDepthIncrease(falseType, mapper);
result = instantiateType(falseType, mapper);
break;
}
// Return trueType for a definitely true extends check. We check instantiations of the two
Expand All @@ -13830,7 +13830,7 @@ namespace ts {
// type Foo<T extends { x: any }> = T extends { x: string } ? string : number
// doesn't immediately resolve to 'string' instead of being deferred.
if (inferredExtendsType.flags & TypeFlags.AnyOrUnknown || isTypeAssignableTo(getRestrictiveInstantiation(checkType), getRestrictiveInstantiation(inferredExtendsType))) {
result = instantiateTypeWithoutDepthIncrease(root.trueType, combinedMapper || mapper);
result = instantiateType(getTypeFromTypeNode(root.node.trueType), combinedMapper || mapper);
break;
}
}
Expand All @@ -13850,15 +13850,15 @@ namespace ts {
}

function getTrueTypeFromConditionalType(type: ConditionalType) {
return type.resolvedTrueType || (type.resolvedTrueType = instantiateType(type.root.trueType, type.mapper));
return type.resolvedTrueType || (type.resolvedTrueType = instantiateType(getTypeFromTypeNode(type.root.node.trueType), type.mapper));
}

function getFalseTypeFromConditionalType(type: ConditionalType) {
return type.resolvedFalseType || (type.resolvedFalseType = instantiateType(type.root.falseType, type.mapper));
return type.resolvedFalseType || (type.resolvedFalseType = instantiateType(getTypeFromTypeNode(type.root.node.falseType), type.mapper));
}

function getInferredTrueTypeFromConditionalType(type: ConditionalType) {
return type.resolvedInferredTrueType || (type.resolvedInferredTrueType = type.combinedMapper ? instantiateType(type.root.trueType, type.combinedMapper) : getTrueTypeFromConditionalType(type));
return type.resolvedInferredTrueType || (type.resolvedInferredTrueType = type.combinedMapper ? instantiateType(getTypeFromTypeNode(type.root.node.trueType), type.combinedMapper) : getTrueTypeFromConditionalType(type));
}

function getInferTypeParameters(node: ConditionalTypeNode): TypeParameter[] | undefined {
Expand All @@ -13885,8 +13885,6 @@ namespace ts {
node,
checkType,
extendsType: getTypeFromTypeNode(node.extendsType),
trueType: getTypeFromTypeNode(node.trueType),
falseType: getTypeFromTypeNode(node.falseType),
isDistributive: !!(checkType.flags & TypeFlags.TypeParameter),
inferTypeParameters: getInferTypeParameters(node),
outerTypeParameters,
Expand Down Expand Up @@ -14877,17 +14875,6 @@ namespace ts {
return result;
}

/**
* This can be used to avoid the penalty on instantiation depth for types which result from immediate
* simplification. It essentially removes the depth increase done in `instantiateType`.
*/
function instantiateTypeWithoutDepthIncrease(type: Type, mapper: TypeMapper | undefined) {
instantiationDepth--;
const result = instantiateType(type, mapper);
instantiationDepth++;
return result;
}

function instantiateTypeWorker(type: Type, mapper: TypeMapper): Type {
const flags = type.flags;
if (flags & TypeFlags.TypeParameter) {
Expand Down Expand Up @@ -18199,56 +18186,44 @@ namespace ts {
// has expanded into `[A<NonNullable<NonNullable<NonNullable<NonNullable<NonNullable<T>>>>>>]`
// in such cases we need to terminate the expansion, and we do so here.
function isDeeplyNestedType(type: Type, stack: Type[], depth: number): boolean {
// We track all object types that have an associated symbol (representing the origin of the type)
if (depth >= 5 && type.flags & TypeFlags.Object) {
if (!isObjectOrArrayLiteralType(type)) {
const symbol = type.symbol;
if (symbol) {
let count = 0;
for (let i = 0; i < depth; i++) {
const t = stack[i];
if (t.flags & TypeFlags.Object && t.symbol === symbol) {
count++;
if (count >= 5) return true;
}
}
}
}
if (getObjectFlags(type) && ObjectFlags.Reference && !!(type as TypeReference).node) {
const root = (type as TypeReference).target;
if (depth >= 5) {
const identity = getRecursionIdentity(type);
if (identity) {
let count = 0;
for (let i = 0; i < depth; i++) {
const t = stack[i];
if (getObjectFlags(t) && ObjectFlags.Reference && !!(t as TypeReference).node && (t as TypeReference).target === root) {
if (getRecursionIdentity(stack[i]) === identity) {
count++;
if (count >= 5) return true;
}
}
}
}
if (depth >= 5 && type.flags & TypeFlags.IndexedAccess) {
const root = getRootObjectTypeFromIndexedAccessChain(type);
let count = 0;
for (let i = 0; i < depth; i++) {
const t = stack[i];
if (getRootObjectTypeFromIndexedAccessChain(t) === root) {
count++;
if (count >= 5) return true;
}
}
}
return false;
}

/**
* Gets the leftmost object type in a chain of indexed accesses, eg, in A[P][Q], returns A
*/
function getRootObjectTypeFromIndexedAccessChain(type: Type) {
let t = type;
while (t.flags & TypeFlags.IndexedAccess) {
t = (t as IndexedAccessType).objectType;
function getRecursionIdentity(type: Type) {
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)
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;
}
}
return t;
if (type.flags & TypeFlags.IndexedAccess) {
// Identity is the leftmost object type in a chain of indexed accesses, eg, in A[P][Q] it is A
do {
type = (type as IndexedAccessType).objectType;
} while (type.flags & TypeFlags.IndexedAccess);
return type;
}
if (type.flags & TypeFlags.Conditional) {
// The root object represents the origin of the conditional type
return (type as ConditionalType).root;
Copy link
Copy Markdown
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
Copy Markdown
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.

}
return undefined;
}

function isPropertyIdenticalTo(sourceProp: Symbol, targetProp: Symbol): boolean {
Expand Down Expand Up @@ -19153,9 +19128,7 @@ namespace ts {
function isTypeParameterAtTopLevel(type: Type, typeParameter: TypeParameter): boolean {
return !!(type === typeParameter ||
type.flags & TypeFlags.UnionOrIntersection && some((<UnionOrIntersectionType>type).types, t => isTypeParameterAtTopLevel(t, typeParameter)) ||
type.flags & TypeFlags.Conditional && (
isTypeParameterAtTopLevel(getTrueTypeFromConditionalType(<ConditionalType>type), typeParameter) ||
isTypeParameterAtTopLevel(getFalseTypeFromConditionalType(<ConditionalType>type), typeParameter)));
type.flags & TypeFlags.Conditional && (getTrueTypeFromConditionalType(<ConditionalType>type) === typeParameter || getFalseTypeFromConditionalType(<ConditionalType>type) === typeParameter));
}

/** Create an object with properties named in the string literal type. Every property has type `any` */
Expand Down Expand Up @@ -19311,7 +19284,7 @@ namespace ts {
let propagationType: Type;
let inferencePriority = InferencePriority.MaxValue;
let allowComplexConstraintInference = true;
let objectTypeComparisonDepth = 0;
let targetStackDepth = 0;
const targetStack: Type[] = [];
inferFromTypes(originalSource, originalTarget);

Expand Down Expand Up @@ -19471,18 +19444,8 @@ namespace ts {
inferFromTypes((<IndexedAccessType>source).objectType, (<IndexedAccessType>target).objectType);
inferFromTypes((<IndexedAccessType>source).indexType, (<IndexedAccessType>target).indexType);
}
else if (source.flags & TypeFlags.Conditional && target.flags & TypeFlags.Conditional) {
inferFromTypes((<ConditionalType>source).checkType, (<ConditionalType>target).checkType);
inferFromTypes((<ConditionalType>source).extendsType, (<ConditionalType>target).extendsType);
inferFromTypes(getTrueTypeFromConditionalType(<ConditionalType>source), getTrueTypeFromConditionalType(<ConditionalType>target));
inferFromTypes(getFalseTypeFromConditionalType(<ConditionalType>source), getFalseTypeFromConditionalType(<ConditionalType>target));
}
else if (target.flags & TypeFlags.Conditional) {
const savePriority = priority;
priority |= contravariant ? InferencePriority.ContravariantConditional : 0;
const targetTypes = [getTrueTypeFromConditionalType(<ConditionalType>target), getFalseTypeFromConditionalType(<ConditionalType>target)];
inferToMultipleTypes(source, targetTypes, target.flags);
priority = savePriority;
invokeWithDepthLimit(<ConditionalType>source, <ConditionalType>target, inferToConditionalType);
}
else if (target.flags & TypeFlags.UnionOrIntersection) {
inferToMultipleTypes(source, (<UnionOrIntersectionType>target).types, target.flags);
Expand Down Expand Up @@ -19739,6 +19702,22 @@ namespace ts {
return false;
}

function inferToConditionalType(source: ConditionalType, 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));
}
else {
const savePriority = priority;
priority |= contravariant ? InferencePriority.ContravariantConditional : 0;
const targetTypes = [getTrueTypeFromConditionalType(target), getFalseTypeFromConditionalType(target)];
inferToMultipleTypes(source, targetTypes, target.flags);
priority = savePriority;
}
}

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
Expand All @@ -19749,30 +19728,33 @@ namespace ts {
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)) {
if (getObjectFlags(target) & ObjectFlags.Reference && (target as TypeReference).node) {
// Don't set the circularity flag for re-encountered recursive type references just because we're already exploring them
return;
// 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;
}
inferencePriority = InferencePriority.Circularity;
return;
}
targetStack[objectTypeComparisonDepth] = target;
objectTypeComparisonDepth++;
if (isDeeplyNestedType(target, targetStack, objectTypeComparisonDepth)) {
inferencePriority = InferencePriority.Circularity;
objectTypeComparisonDepth--;
return;
}
(symbolOrTypeStack || (symbolOrTypeStack = [])).push(symbolOrType);
inferFromObjectTypesWorker(source, target);
invokeWithDepthLimit(source, target, inferFromObjectTypesWorker);
symbolOrTypeStack.pop();
objectTypeComparisonDepth--;
}
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))) {
Expand Down
2 changes: 0 additions & 2 deletions src/compiler/types.ts
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -5292,8 +5292,6 @@ namespace ts {
node: ConditionalTypeNode;
checkType: Type;
extendsType: Type;
trueType: Type;
falseType: Type;
isDistributive: boolean;
inferTypeParameters?: TypeParameter[];
outerTypeParameters?: TypeParameter[];
Expand Down