Skip to content

Commit 9f28418

Browse files
ahejlsbergahejlsberg
committed
Merge pull request microsoft#1180 from Microsoft/recursiveTypeComparison
Improve caching in recursive type comparisons (fixes microsoft#1170)
2 parents acc2550 + b99b040 commit 9f28418

7 files changed

Lines changed: 205 additions & 12 deletions

File tree

‎src/compiler/checker.ts‎

Lines changed: 25 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -3234,9 +3234,9 @@ module ts {
32343234

32353235
// TYPE CHECKING
32363236

3237-
var subtypeRelation: Map<Ternary> = {};
3238-
var assignableRelation: Map<Ternary> = {};
3239-
var identityRelation: Map<Ternary> = {};
3237+
var subtypeRelation: Map<boolean> = {};
3238+
var assignableRelation: Map<boolean> = {};
3239+
var identityRelation: Map<boolean> = {};
32403240

32413241
function isTypeIdenticalTo(source: Type, target: Type): boolean {
32423242
return checkTypeRelatedTo(source, target, identityRelation, /*errorNode*/ undefined);
@@ -3271,14 +3271,15 @@ module ts {
32713271
function checkTypeRelatedTo(
32723272
source: Type,
32733273
target: Type,
3274-
relation: Map<Ternary>,
3274+
relation: Map<boolean>,
32753275
errorNode: Node,
32763276
headMessage?: DiagnosticMessage,
32773277
containingMessageChain?: DiagnosticMessageChain): boolean {
32783278

32793279
var errorInfo: DiagnosticMessageChain;
32803280
var sourceStack: ObjectType[];
32813281
var targetStack: ObjectType[];
3282+
var maybeStack: Map<boolean>[];
32823283
var expandingFlags: number;
32833284
var depth = 0;
32843285
var overflow = false;
@@ -3437,12 +3438,12 @@ module ts {
34373438
var id = source.id + "," + target.id;
34383439
var related = relation[id];
34393440
if (related !== undefined) {
3440-
return related;
3441+
return related ? Ternary.True : Ternary.False;
34413442
}
34423443
if (depth > 0) {
34433444
for (var i = 0; i < depth; i++) {
34443445
// If source and target are already being compared, consider them related with assumptions
3445-
if (source === sourceStack[i] && target === targetStack[i]) {
3446+
if (maybeStack[i][id]) {
34463447
return Ternary.Maybe;
34473448
}
34483449
}
@@ -3454,16 +3455,19 @@ module ts {
34543455
else {
34553456
sourceStack = [];
34563457
targetStack = [];
3458+
maybeStack = [];
34573459
expandingFlags = 0;
34583460
}
34593461
sourceStack[depth] = source;
34603462
targetStack[depth] = target;
3463+
maybeStack[depth] = {};
3464+
maybeStack[depth][id] = true;
34613465
depth++;
34623466
var saveExpandingFlags = expandingFlags;
34633467
if (!(expandingFlags & 1) && isDeeplyNestedGeneric(source, sourceStack)) expandingFlags |= 1;
34643468
if (!(expandingFlags & 2) && isDeeplyNestedGeneric(target, targetStack)) expandingFlags |= 2;
34653469
if (expandingFlags === 3) {
3466-
var result = Ternary.True;
3470+
var result = Ternary.Maybe;
34673471
}
34683472
else {
34693473
var result = propertiesRelatedTo(source, target, reportErrors);
@@ -3482,9 +3486,18 @@ module ts {
34823486
}
34833487
expandingFlags = saveExpandingFlags;
34843488
depth--;
3485-
// Only cache results that are free of assumptions
3486-
if (result !== Ternary.Maybe) {
3487-
relation[id] = result;
3489+
if (result) {
3490+
var maybeCache = maybeStack[depth];
3491+
// If result is definitely true, copy assumptions to global cache, else copy to next level up
3492+
var destinationCache = result === Ternary.True || depth === 0 ? relation : maybeStack[depth - 1];
3493+
for (var p in maybeCache) {
3494+
destinationCache[p] = maybeCache[p];
3495+
}
3496+
}
3497+
else {
3498+
// A false result goes straight into global cache (when something is false under assumptions it
3499+
// will also be false without assumptions)
3500+
relation[id] = false;
34883501
}
34893502
return result;
34903503
}
@@ -5420,7 +5433,7 @@ module ts {
54205433
return typeArgumentsAreAssignable;
54215434
}
54225435

5423-
function checkApplicableSignature(node: CallLikeExpression, args: Node[], signature: Signature, relation: Map<Ternary>, excludeArgument: boolean[], reportErrors: boolean) {
5436+
function checkApplicableSignature(node: CallLikeExpression, args: Node[], signature: Signature, relation: Map<boolean>, excludeArgument: boolean[], reportErrors: boolean) {
54245437
for (var i = 0; i < args.length; i++) {
54255438
var arg = args[i];
54265439
var argType: Type;
@@ -5614,7 +5627,7 @@ module ts {
56145627

56155628
return resolveErrorCall(node);
56165629

5617-
function chooseOverload(candidates: Signature[], relation: Map<Ternary>) {
5630+
function chooseOverload(candidates: Signature[], relation: Map<boolean>) {
56185631
for (var i = 0; i < candidates.length; i++) {
56195632
if (!hasCorrectArity(node, args, candidates[i])) {
56205633
continue;

‎tests/baselines/reference/recursiveTypeComparison.js‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
//// [recursiveTypeComparison.ts]
2+
// Before fix this would take an exceeding long time to complete (#1170)
3+
4+
interface Observable<T> {
5+
// This member can't be of type T, Property<T>, or Observable<anything but T>
6+
needThisOne: Observable<T>;
7+
// Add more to make it slower
8+
expo1: Property<T[]>; // 0.31 seconds in check
9+
expo2: Property<T[]>; // 3.11 seconds
10+
expo3: Property<T[]>; // 82.28 seconds
11+
}
12+
interface Property<T> extends Observable<T> { }
13+
14+
var p: Observable<{}>;
15+
var stuck: Property<number> = p;
16+
17+
18+
//// [recursiveTypeComparison.js]
19+
// Before fix this would take an exceeding long time to complete (#1170)
20+
var p;
21+
var stuck = p;

‎tests/baselines/reference/recursiveTypeComparison.types‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
=== tests/cases/compiler/recursiveTypeComparison.ts ===
2+
// Before fix this would take an exceeding long time to complete (#1170)
3+
4+
interface Observable<T> {
5+
>Observable : Observable<T>
6+
>T : T
7+
8+
// This member can't be of type T, Property<T>, or Observable<anything but T>
9+
needThisOne: Observable<T>;
10+
>needThisOne : Observable<T>
11+
>Observable : Observable<T>
12+
>T : T
13+
14+
// Add more to make it slower
15+
expo1: Property<T[]>; // 0.31 seconds in check
16+
>expo1 : Property<T[]>
17+
>Property : Property<T>
18+
>T : T
19+
20+
expo2: Property<T[]>; // 3.11 seconds
21+
>expo2 : Property<T[]>
22+
>Property : Property<T>
23+
>T : T
24+
25+
expo3: Property<T[]>; // 82.28 seconds
26+
>expo3 : Property<T[]>
27+
>Property : Property<T>
28+
>T : T
29+
}
30+
interface Property<T> extends Observable<T> { }
31+
>Property : Property<T>
32+
>T : T
33+
>Observable : Observable<T>
34+
>T : T
35+
36+
var p: Observable<{}>;
37+
>p : Observable<{}>
38+
>Observable : Observable<T>
39+
40+
var stuck: Property<number> = p;
41+
>stuck : Property<number>
42+
>Property : Property<T>
43+
>p : Observable<{}>
44+

‎tests/baselines/reference/recursiveTypeComparison2.errors.txt‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
tests/cases/compiler/recursiveTypeComparison2.ts(13,80): error TS2304: Cannot find name 'StateValue'.
2+
3+
4+
==== tests/cases/compiler/recursiveTypeComparison2.ts (1 errors) ====
5+
// Before fix this would cause compiler to hang (#1170)
6+
7+
declare module Bacon {
8+
interface Event<T> {
9+
}
10+
interface Error<T> extends Event<T> {
11+
}
12+
interface Observable<T> {
13+
zip<U, V>(other: EventStream<U>, f: (a: T, b: U) => V): EventStream<V>;
14+
slidingWindow(max: number, min?: number): Property<T[]>;
15+
log(): Observable<T>;
16+
combine<U, V>(other: Observable<U>, f: (a: T, b: U) => V): Property<V>;
17+
withStateMachine<U, V>(initState: U, f: (state: U, event: Event<T>) => StateValue<U, V>): EventStream<V>;
18+
~~~~~~~~~~~~~~~~
19+
!!! error TS2304: Cannot find name 'StateValue'.
20+
decode(mapping: Object): Property<any>;
21+
awaiting<U>(other: Observable<U>): Property<boolean>;
22+
endOnError(f?: (value: T) => boolean): Observable<T>;
23+
withHandler(f: (event: Event<T>) => any): Observable<T>;
24+
name(name: string): Observable<T>;
25+
withDescription(...args: any[]): Observable<T>;
26+
}
27+
interface Property<T> extends Observable<T> {
28+
}
29+
interface EventStream<T> extends Observable<T> {
30+
}
31+
interface Bus<T> extends EventStream<T> {
32+
}
33+
var Bus: new <T>() => Bus<T>;
34+
}
35+
36+
var stuck: Bacon.Bus<number> = new Bacon.Bus();

‎tests/baselines/reference/recursiveTypeComparison2.js‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
//// [recursiveTypeComparison2.ts]
2+
// Before fix this would cause compiler to hang (#1170)
3+
4+
declare module Bacon {
5+
interface Event<T> {
6+
}
7+
interface Error<T> extends Event<T> {
8+
}
9+
interface Observable<T> {
10+
zip<U, V>(other: EventStream<U>, f: (a: T, b: U) => V): EventStream<V>;
11+
slidingWindow(max: number, min?: number): Property<T[]>;
12+
log(): Observable<T>;
13+
combine<U, V>(other: Observable<U>, f: (a: T, b: U) => V): Property<V>;
14+
withStateMachine<U, V>(initState: U, f: (state: U, event: Event<T>) => StateValue<U, V>): EventStream<V>;
15+
decode(mapping: Object): Property<any>;
16+
awaiting<U>(other: Observable<U>): Property<boolean>;
17+
endOnError(f?: (value: T) => boolean): Observable<T>;
18+
withHandler(f: (event: Event<T>) => any): Observable<T>;
19+
name(name: string): Observable<T>;
20+
withDescription(...args: any[]): Observable<T>;
21+
}
22+
interface Property<T> extends Observable<T> {
23+
}
24+
interface EventStream<T> extends Observable<T> {
25+
}
26+
interface Bus<T> extends EventStream<T> {
27+
}
28+
var Bus: new <T>() => Bus<T>;
29+
}
30+
31+
var stuck: Bacon.Bus<number> = new Bacon.Bus();
32+
33+
//// [recursiveTypeComparison2.js]
34+
// Before fix this would cause compiler to hang (#1170)
35+
var stuck = new Bacon.Bus();

‎tests/cases/compiler/recursiveTypeComparison.ts‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
// Before fix this would take an exceeding long time to complete (#1170)
2+
3+
interface Observable<T> {
4+
// This member can't be of type T, Property<T>, or Observable<anything but T>
5+
needThisOne: Observable<T>;
6+
// Add more to make it slower
7+
expo1: Property<T[]>; // 0.31 seconds in check
8+
expo2: Property<T[]>; // 3.11 seconds
9+
expo3: Property<T[]>; // 82.28 seconds
10+
}
11+
interface Property<T> extends Observable<T> { }
12+
13+
var p: Observable<{}>;
14+
var stuck: Property<number> = p;

‎tests/cases/compiler/recursiveTypeComparison2.ts‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
// Before fix this would cause compiler to hang (#1170)
2+
3+
declare module Bacon {
4+
interface Event<T> {
5+
}
6+
interface Error<T> extends Event<T> {
7+
}
8+
interface Observable<T> {
9+
zip<U, V>(other: EventStream<U>, f: (a: T, b: U) => V): EventStream<V>;
10+
slidingWindow(max: number, min?: number): Property<T[]>;
11+
log(): Observable<T>;
12+
combine<U, V>(other: Observable<U>, f: (a: T, b: U) => V): Property<V>;
13+
withStateMachine<U, V>(initState: U, f: (state: U, event: Event<T>) => StateValue<U, V>): EventStream<V>;
14+
decode(mapping: Object): Property<any>;
15+
awaiting<U>(other: Observable<U>): Property<boolean>;
16+
endOnError(f?: (value: T) => boolean): Observable<T>;
17+
withHandler(f: (event: Event<T>) => any): Observable<T>;
18+
name(name: string): Observable<T>;
19+
withDescription(...args: any[]): Observable<T>;
20+
}
21+
interface Property<T> extends Observable<T> {
22+
}
23+
interface EventStream<T> extends Observable<T> {
24+
}
25+
interface Bus<T> extends EventStream<T> {
26+
}
27+
var Bus: new <T>() => Bus<T>;
28+
}
29+
30+
var stuck: Bacon.Bus<number> = new Bacon.Bus();

0 commit comments

Comments
 (0)