Skip to content

Commit d20f192

Browse files
ahejlsbergahejlsberg
authored
Order variance computation by associated type symbol (microsoft/typescript-go#4820)
1 parent 8bcca18 commit d20f192

14 files changed

Lines changed: 539 additions & 51 deletions

‎tsc/internal/checker/checker.go‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -542,6 +542,11 @@ type WideningContext struct {
542542
widenedTypes map[*Type]*Type
543543
}
544544

545+
type VarianceStackEntry struct {
546+
symbol *ast.Symbol
547+
typeParameters []*Type
548+
}
549+
545550
const maxSerializationLevel = 2
546551

547552
type Program interface {
@@ -786,7 +791,7 @@ type Checker struct {
786791
typeofType *Type
787792
typeResolutions []TypeResolution
788793
resolutionStart int
789-
inVarianceComputation bool
794+
varianceStack []VarianceStackEntry
790795
apparentArgumentCount *int
791796
lastGetCombinedNodeFlagsNode *ast.Node
792797
lastGetCombinedNodeFlagsResult ast.NodeFlags

‎tsc/internal/checker/relater.go‎

Lines changed: 89 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1354,62 +1354,102 @@ func (c *Checker) getVariancesWorker(symbol *ast.Symbol, typeParameters []*Type)
13541354
popFn()
13551355
}()
13561356
}
1357-
oldVarianceComputation := c.inVarianceComputation
1358-
saveResolutionStart := c.resolutionStart
1359-
if !c.inVarianceComputation {
1360-
c.inVarianceComputation = true
1361-
c.resolutionStart = len(c.typeResolutions)
1362-
}
1363-
links.variances = []VarianceFlags{}
1364-
variances := make([]VarianceFlags, len(typeParameters))
1365-
for i, tp := range typeParameters {
1366-
modifiers := c.getTypeParameterModifiers(tp)
1367-
var variance VarianceFlags
1368-
switch {
1369-
case modifiers&ast.ModifierFlagsOut != 0:
1370-
if modifiers&ast.ModifierFlagsIn != 0 {
1371-
variance = VarianceFlagsInvariant
1372-
} else {
1373-
variance = VarianceFlagsCovariant
1374-
}
1375-
case modifiers&ast.ModifierFlagsIn != 0:
1376-
variance = VarianceFlagsContravariant
1377-
default:
1378-
saveReliabilityFlags := c.reliabilityFlags
1379-
c.reliabilityFlags = 0
1380-
// We first compare instantiations where the type parameter is replaced with
1381-
// marker types that have a known subtype relationship. From this we can infer
1382-
// invariance, covariance, contravariance or bivariance.
1383-
typeWithSuper := c.createMarkerType(symbol, tp, c.markerSuperType)
1384-
typeWithSub := c.createMarkerType(symbol, tp, c.markerSubType)
1385-
variance = core.IfElse(c.isTypeAssignableTo(typeWithSub, typeWithSuper), VarianceFlagsCovariant, 0) |
1386-
core.IfElse(c.isTypeAssignableTo(typeWithSuper, typeWithSub), VarianceFlagsContravariant, 0)
1387-
// If the instantiations appear to be related bivariantly it may be because the
1388-
// type parameter is independent (i.e. it isn't witnessed anywhere in the generic
1389-
// type). To determine this we compare instantiations where the type parameter is
1390-
// replaced with marker types that are known to be unrelated.
1391-
if variance == VarianceFlagsBivariant && c.isTypeAssignableTo(c.createMarkerType(symbol, tp, c.markerOtherType), typeWithSuper) {
1392-
variance = VarianceFlagsIndependent
1357+
stackIndex := c.getVarianceStackIndex(symbol)
1358+
if stackIndex < 0 {
1359+
saveResolutionStart := c.resolutionStart
1360+
if len(c.varianceStack) == 0 {
1361+
c.resolutionStart = len(c.typeResolutions)
1362+
}
1363+
c.varianceStack = append(c.varianceStack, VarianceStackEntry{symbol, typeParameters})
1364+
variances := make([]VarianceFlags, len(typeParameters))
1365+
for i, tp := range typeParameters {
1366+
modifiers := c.getTypeParameterModifiers(tp)
1367+
var variance VarianceFlags
1368+
switch {
1369+
case modifiers&ast.ModifierFlagsOut != 0:
1370+
if modifiers&ast.ModifierFlagsIn != 0 {
1371+
variance = VarianceFlagsInvariant
1372+
} else {
1373+
variance = VarianceFlagsCovariant
1374+
}
1375+
case modifiers&ast.ModifierFlagsIn != 0:
1376+
variance = VarianceFlagsContravariant
1377+
default:
1378+
saveReliabilityFlags := c.reliabilityFlags
1379+
c.reliabilityFlags = 0
1380+
// We first compare instantiations where the type parameter is replaced with
1381+
// marker types that have a known subtype relationship. From this we can infer
1382+
// invariance, covariance, contravariance or bivariance.
1383+
typeWithSuper := c.createMarkerType(symbol, tp, c.markerSuperType)
1384+
typeWithSub := c.createMarkerType(symbol, tp, c.markerSubType)
1385+
variance = core.IfElse(c.isTypeAssignableTo(typeWithSub, typeWithSuper), VarianceFlagsCovariant, 0) |
1386+
core.IfElse(c.isTypeAssignableTo(typeWithSuper, typeWithSub), VarianceFlagsContravariant, 0)
1387+
// If the instantiations appear to be related bivariantly it may be because the
1388+
// type parameter is independent (i.e. it isn't witnessed anywhere in the generic
1389+
// type). To determine this we compare instantiations where the type parameter is
1390+
// replaced with marker types that are known to be unrelated.
1391+
if variance == VarianceFlagsBivariant && c.isTypeAssignableTo(c.createMarkerType(symbol, tp, c.markerOtherType), typeWithSuper) {
1392+
variance = VarianceFlagsIndependent
1393+
}
1394+
if c.reliabilityFlags&RelationComparisonResultReportsUnmeasurable != 0 {
1395+
variance |= VarianceFlagsUnmeasurable
1396+
}
1397+
if c.reliabilityFlags&RelationComparisonResultReportsUnreliable != 0 {
1398+
variance |= VarianceFlagsUnreliable
1399+
}
1400+
c.reliabilityFlags = saveReliabilityFlags
13931401
}
1394-
if c.reliabilityFlags&RelationComparisonResultReportsUnmeasurable != 0 {
1395-
variance |= VarianceFlagsUnmeasurable
1402+
// If variance computation was restarted due to a circularity we may have already
1403+
// computed variances for this generic type. If so, we exit early.
1404+
if len(links.variances) != 0 {
1405+
break
13961406
}
1397-
if c.reliabilityFlags&RelationComparisonResultReportsUnreliable != 0 {
1398-
variance |= VarianceFlagsUnreliable
1407+
variances[i] = variance
1408+
}
1409+
// Store the results unless a restarted computation has already stored them.
1410+
if len(links.variances) == 0 {
1411+
links.variances = variances
1412+
}
1413+
c.varianceStack = c.varianceStack[:len(c.varianceStack)-1]
1414+
if len(c.varianceStack) == 0 {
1415+
c.resolutionStart = saveResolutionStart
1416+
}
1417+
} else {
1418+
// We've detected a circularity. Since we may compute different variances depending on where
1419+
// we enter a circularity, we find the generic type with the "smallest" symbol in the circular
1420+
// region of the variance stack and restart the computation from there if necessary. This
1421+
// ensures stable results for circular generic types.
1422+
minIndex := stackIndex
1423+
for i := stackIndex + 1; i < len(c.varianceStack); i++ {
1424+
if c.compareSymbols(c.varianceStack[i].symbol, c.varianceStack[minIndex].symbol) < 0 {
1425+
minIndex = i
13991426
}
1400-
c.reliabilityFlags = saveReliabilityFlags
14011427
}
1402-
variances[i] = variance
1403-
}
1404-
if !oldVarianceComputation {
1405-
c.inVarianceComputation = false
1406-
c.resolutionStart = saveResolutionStart
1428+
if minIndex > stackIndex {
1429+
saveVarianceStack := c.varianceStack
1430+
c.varianceStack = nil
1431+
c.getVariancesWorker(saveVarianceStack[minIndex].symbol, saveVarianceStack[minIndex].typeParameters)
1432+
c.varianceStack = saveVarianceStack
1433+
}
1434+
// Store an empty slice to mark that we can't compute variances for this type. We treat type
1435+
// parameters as co-variant in this case.
1436+
if len(links.variances) == 0 {
1437+
links.variances = []VarianceFlags{}
1438+
}
14071439
}
1408-
links.variances = variances
14091440
}
14101441
return links.variances
14111442
}
14121443

1444+
func (c *Checker) getVarianceStackIndex(symbol *ast.Symbol) int {
1445+
for i, entry := range c.varianceStack {
1446+
if entry.symbol == symbol {
1447+
return i
1448+
}
1449+
}
1450+
return -1
1451+
}
1452+
14131453
func (c *Checker) createMarkerType(symbol *ast.Symbol, source *Type, target *Type) *Type {
14141454
mapper := newSimpleTypeMapper(source, target)
14151455
t := c.getDeclaredTypeOfSymbol(symbol)
@@ -3930,8 +3970,8 @@ func (r *Relater) typeArgumentsRelatedTo(sources []*Type, targets []*Type, varia
39303970
related = r.c.compareTypesIdentical(s, t)
39313971
}
39323972
} else {
3933-
// Propagate unreliable variance flag
3934-
if r.c.inVarianceComputation && varianceFlags&VarianceFlagsUnreliable != 0 {
3973+
// Propagate unreliable variance flag in variance computations
3974+
if len(r.c.varianceStack) != 0 && varianceFlags&VarianceFlagsUnreliable != 0 {
39353975
r.c.instantiateType(s, r.c.reportUnreliableMapper)
39363976
}
39373977
if variance == VarianceFlagsCovariant {

‎tsc/testdata/baselines/reference/compiler/circularVariance1.errors.txt‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
circularVariance1.ts(18,1): error TS2322: Type 'Foo<unknown>' is not assignable to type 'Foo<string>'.
2+
Type 'unknown' is not assignable to type 'string'.
3+
circularVariance1.ts(23,1): error TS2322: Type 'Bar<string>' is not assignable to type 'Bar<unknown>'.
4+
Type 'unknown' is not assignable to type 'string'.
5+
6+
7+
==== circularVariance1.ts (2 errors) ====
8+
// https://github.com/microsoft/typescript-go/pull/4820
9+
10+
type Bar<U> = (x: Baz<U[]>) => void;
11+
12+
type Baz<V> = {
13+
value: Foo<V[]>;
14+
}
15+
16+
type Foo<T> = {
17+
x: T;
18+
f: Bar<T>;
19+
}
20+
21+
declare let foo1: Foo<unknown>;
22+
declare let foo2: Foo<string>;
23+
24+
foo1 = foo2;
25+
foo2 = foo1; // Error
26+
~~~~
27+
!!! error TS2322: Type 'Foo<unknown>' is not assignable to type 'Foo<string>'.
28+
!!! error TS2322: Type 'unknown' is not assignable to type 'string'.
29+
30+
declare let bar1: Bar<unknown>;
31+
declare let bar2: Bar<string>;
32+
33+
bar1 = bar2; // Error
34+
~~~~
35+
!!! error TS2322: Type 'Bar<string>' is not assignable to type 'Bar<unknown>'.
36+
!!! error TS2322: Type 'unknown' is not assignable to type 'string'.
37+
bar2 = bar1;
38+

‎tsc/testdata/baselines/reference/compiler/circularVariance1.symbols‎

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
//// [tests/cases/compiler/circularVariance1.ts] ////
2+
3+
=== circularVariance1.ts ===
4+
// https://github.com/microsoft/typescript-go/pull/4820
5+
6+
type Bar<U> = (x: Baz<U[]>) => void;
7+
>Bar : Symbol(Bar, Decl(circularVariance1.ts, 0, 0))
8+
>U : Symbol(U, Decl(circularVariance1.ts, 2, 9))
9+
>x : Symbol(x, Decl(circularVariance1.ts, 2, 15))
10+
>Baz : Symbol(Baz, Decl(circularVariance1.ts, 2, 36))
11+
>U : Symbol(U, Decl(circularVariance1.ts, 2, 9))
12+
13+
type Baz<V> = {
14+
>Baz : Symbol(Baz, Decl(circularVariance1.ts, 2, 36))
15+
>V : Symbol(V, Decl(circularVariance1.ts, 4, 9))
16+
17+
value: Foo<V[]>;
18+
>value : Symbol(value, Decl(circularVariance1.ts, 4, 15))
19+
>Foo : Symbol(Foo, Decl(circularVariance1.ts, 6, 1))
20+
>V : Symbol(V, Decl(circularVariance1.ts, 4, 9))
21+
}
22+
23+
type Foo<T> = {
24+
>Foo : Symbol(Foo, Decl(circularVariance1.ts, 6, 1))
25+
>T : Symbol(T, Decl(circularVariance1.ts, 8, 9))
26+
27+
x: T;
28+
>x : Symbol(x, Decl(circularVariance1.ts, 8, 15))
29+
>T : Symbol(T, Decl(circularVariance1.ts, 8, 9))
30+
31+
f: Bar<T>;
32+
>f : Symbol(f, Decl(circularVariance1.ts, 9, 9))
33+
>Bar : Symbol(Bar, Decl(circularVariance1.ts, 0, 0))
34+
>T : Symbol(T, Decl(circularVariance1.ts, 8, 9))
35+
}
36+
37+
declare let foo1: Foo<unknown>;
38+
>foo1 : Symbol(foo1, Decl(circularVariance1.ts, 13, 11))
39+
>Foo : Symbol(Foo, Decl(circularVariance1.ts, 6, 1))
40+
41+
declare let foo2: Foo<string>;
42+
>foo2 : Symbol(foo2, Decl(circularVariance1.ts, 14, 11))
43+
>Foo : Symbol(Foo, Decl(circularVariance1.ts, 6, 1))
44+
45+
foo1 = foo2;
46+
>foo1 : Symbol(foo1, Decl(circularVariance1.ts, 13, 11))
47+
>foo2 : Symbol(foo2, Decl(circularVariance1.ts, 14, 11))
48+
49+
foo2 = foo1; // Error
50+
>foo2 : Symbol(foo2, Decl(circularVariance1.ts, 14, 11))
51+
>foo1 : Symbol(foo1, Decl(circularVariance1.ts, 13, 11))
52+
53+
declare let bar1: Bar<unknown>;
54+
>bar1 : Symbol(bar1, Decl(circularVariance1.ts, 19, 11))
55+
>Bar : Symbol(Bar, Decl(circularVariance1.ts, 0, 0))
56+
57+
declare let bar2: Bar<string>;
58+
>bar2 : Symbol(bar2, Decl(circularVariance1.ts, 20, 11))
59+
>Bar : Symbol(Bar, Decl(circularVariance1.ts, 0, 0))
60+
61+
bar1 = bar2; // Error
62+
>bar1 : Symbol(bar1, Decl(circularVariance1.ts, 19, 11))
63+
>bar2 : Symbol(bar2, Decl(circularVariance1.ts, 20, 11))
64+
65+
bar2 = bar1;
66+
>bar2 : Symbol(bar2, Decl(circularVariance1.ts, 20, 11))
67+
>bar1 : Symbol(bar1, Decl(circularVariance1.ts, 19, 11))
68+

‎tsc/testdata/baselines/reference/compiler/circularVariance1.types‎

Lines changed: 58 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,58 @@
1+
//// [tests/cases/compiler/circularVariance1.ts] ////
2+
3+
=== circularVariance1.ts ===
4+
// https://github.com/microsoft/typescript-go/pull/4820
5+
6+
type Bar<U> = (x: Baz<U[]>) => void;
7+
>Bar : Bar<U>
8+
>x : Baz<U[]>
9+
10+
type Baz<V> = {
11+
>Baz : Baz<V>
12+
13+
value: Foo<V[]>;
14+
>value : Foo<V[]>
15+
}
16+
17+
type Foo<T> = {
18+
>Foo : Foo<T>
19+
20+
x: T;
21+
>x : T
22+
23+
f: Bar<T>;
24+
>f : Bar<T>
25+
}
26+
27+
declare let foo1: Foo<unknown>;
28+
>foo1 : Foo<unknown>
29+
30+
declare let foo2: Foo<string>;
31+
>foo2 : Foo<string>
32+
33+
foo1 = foo2;
34+
>foo1 = foo2 : Foo<string>
35+
>foo1 : Foo<unknown>
36+
>foo2 : Foo<string>
37+
38+
foo2 = foo1; // Error
39+
>foo2 = foo1 : Foo<unknown>
40+
>foo2 : Foo<string>
41+
>foo1 : Foo<unknown>
42+
43+
declare let bar1: Bar<unknown>;
44+
>bar1 : Bar<unknown>
45+
46+
declare let bar2: Bar<string>;
47+
>bar2 : Bar<string>
48+
49+
bar1 = bar2; // Error
50+
>bar1 = bar2 : Bar<string>
51+
>bar1 : Bar<unknown>
52+
>bar2 : Bar<string>
53+
54+
bar2 = bar1;
55+
>bar2 = bar1 : Bar<unknown>
56+
>bar2 : Bar<string>
57+
>bar1 : Bar<unknown>
58+

‎tsc/testdata/baselines/reference/compiler/circularVariance2.errors.txt‎

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
circularVariance2.ts(17,1): error TS2322: Type 'Bar<string>' is not assignable to type 'Bar<unknown>'.
2+
Type 'unknown' is not assignable to type 'string'.
3+
circularVariance2.ts(24,1): error TS2322: Type 'Foo<unknown>' is not assignable to type 'Foo<string>'.
4+
Type 'unknown' is not assignable to type 'string'.
5+
6+
7+
==== circularVariance2.ts (2 errors) ====
8+
// https://github.com/microsoft/typescript-go/pull/4820
9+
10+
type Bar<U> = (x: Baz<U[]>) => void;
11+
12+
type Baz<V> = {
13+
value: Foo<V[]>;
14+
}
15+
16+
type Foo<T> = {
17+
x: T;
18+
f: Bar<T>;
19+
}
20+
21+
declare let bar1: Bar<unknown>;
22+
declare let bar2: Bar<string>;
23+
24+
bar1 = bar2; // Error
25+
~~~~
26+
!!! error TS2322: Type 'Bar<string>' is not assignable to type 'Bar<unknown>'.
27+
!!! error TS2322: Type 'unknown' is not assignable to type 'string'.
28+
bar2 = bar1;
29+
30+
declare let foo1: Foo<unknown>;
31+
declare let foo2: Foo<string>;
32+
33+
foo1 = foo2;
34+
foo2 = foo1; // Error
35+
~~~~
36+
!!! error TS2322: Type 'Foo<unknown>' is not assignable to type 'Foo<string>'.
37+
!!! error TS2322: Type 'unknown' is not assignable to type 'string'.
38+

0 commit comments

Comments
 (0)