-
Notifications
You must be signed in to change notification settings - Fork 1k
/
TypeComparer.scala
2837 lines (2621 loc) · 114 KB
/
TypeComparer.scala
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
package dotty.tools
package dotc
package core
import Types._, Contexts._, Symbols._, Flags._, Names._, NameOps._, Denotations._
import Decorators._
import Phases.gettersPhase
import StdNames.nme
import TypeOps.refineUsingParent
import collection.mutable
import util.Stats
import config.Config
import config.Feature.migrateTo3
import config.Printers.{constr, subtyping, gadts, noPrinter}
import TypeErasure.{erasedLub, erasedGlb}
import TypeApplications._
import Variances.{Variance, variancesConform}
import Constants.Constant
import transform.TypeUtils._
import transform.SymUtils._
import scala.util.control.NonFatal
import typer.ProtoTypes.constrained
import typer.Applications.productSelectorTypes
import reporting.trace
import NullOpsDecorator._
import annotation.constructorOnly
/** Provides methods to compare types.
*/
class TypeComparer(@constructorOnly initctx: Context) extends ConstraintHandling, PatternTypeConstrainer {
import TypeComparer._
Stats.record("TypeComparer")
private var myContext: Context = initctx
def comparerContext: Context = myContext
protected given [DummySoItsADef] as Context = myContext
protected var state: TyperState = null
def constraint: Constraint = state.constraint
def constraint_=(c: Constraint): Unit = state.constraint = c
def init(c: Context): Unit =
myContext = c
state = c.typerState
monitored = false
GADTused = false
recCount = 0
needsGc = false
if Config.checkTypeComparerReset then checkReset()
private var pendingSubTypes: mutable.Set[(Type, Type)] = null
private var recCount = 0
private var monitored = false
private var needsGc = false
private var canCompareAtoms: Boolean = true // used for internal consistency checking
/** Indicates whether the subtype check used GADT bounds */
private var GADTused: Boolean = false
private var myInstance: TypeComparer = this
def currentInstance: TypeComparer = myInstance
/** Is a subtype check in progress? In that case we may not
* permanently instantiate type variables, because the corresponding
* constraint might still be retracted and the instantiation should
* then be reversed.
*/
def subtypeCheckInProgress: Boolean = {
val result = recCount > 0
if (result) {
constr.println("*** needsGC ***")
needsGc = true
}
result
}
/** For statistics: count how many isSubTypes are part of successful comparisons */
private var successCount = 0
private var totalCount = 0
protected val AnyClass = defn.AnyClass
protected val AnyKindClass = defn.AnyKindClass
protected val NothingClass = defn.NothingClass
protected val NullClass = defn.NullClass
protected val ObjectClass = defn.ObjectClass
protected val AnyType = AnyClass.typeRef
protected val AnyKindType = AnyKindClass.typeRef
protected val NothingType = NothingClass.typeRef
override def checkReset() =
super.checkReset()
assert(pendingSubTypes == null || pendingSubTypes.isEmpty)
assert(canCompareAtoms == true)
assert(successCount == 0)
assert(totalCount == 0)
assert(approx == ApproxState.Fresh)
assert(leftRoot == null)
assert(frozenGadt == false)
/** Record that GADT bounds of `sym` were used in a subtype check.
* But exclude constructor type parameters, as these are aliased
* to the corresponding class parameters, which does not constitute
* a true usage of a GADT symbol.
*/
private def GADTusage(sym: Symbol) = {
if (!sym.owner.isConstructor) GADTused = true
true
}
protected def gadtBounds(sym: Symbol)(using Context) = ctx.gadt.bounds(sym)
protected def gadtAddLowerBound(sym: Symbol, b: Type): Boolean = ctx.gadt.addBound(sym, b, isUpper = false)
protected def gadtAddUpperBound(sym: Symbol, b: Type): Boolean = ctx.gadt.addBound(sym, b, isUpper = true)
protected def typeVarInstance(tvar: TypeVar)(using Context): Type = tvar.underlying
// Subtype testing `<:<`
def topLevelSubType(tp1: Type, tp2: Type): Boolean = {
if (tp2 eq NoType) return false
if ((tp2 eq tp1) || (tp2 eq WildcardType)) return true
try isSubType(tp1, tp2)
finally {
monitored = false
if (Config.checkConstraintsSatisfiable)
assert(isSatisfiable, constraint.show)
}
}
def testSubType(tp1: Type, tp2: Type): CompareResult =
GADTused = false
if !topLevelSubType(tp1, tp2) then CompareResult.Fail
else if GADTused then CompareResult.OKwithGADTUsed
else CompareResult.OK
/** The current approximation state. See `ApproxState`. */
private var approx: ApproxState = ApproxState.Fresh
protected def approxState: ApproxState = approx
/** The original left-hand type of the comparison. Gets reset
* every time we compare components of the previous pair of types.
* This type is used for capture conversion in `isSubArgs`.
*/
private [this] var leftRoot: Type = null
/** Are we forbidden from recording GADT constraints? */
private var frozenGadt = false
private inline def inFrozenGadt[T](op: => T): T = {
val savedFrozenGadt = frozenGadt
frozenGadt = true
try op finally frozenGadt = savedFrozenGadt
}
protected def isSubType(tp1: Type, tp2: Type, a: ApproxState): Boolean = {
val savedApprox = approx
val savedLeftRoot = leftRoot
if (a == ApproxState.Fresh) {
this.approx = ApproxState.None
this.leftRoot = tp1
}
else this.approx = a
try recur(tp1, tp2)
catch {
case ex: Throwable => handleRecursive("subtype", i"$tp1 <:< $tp2", ex, weight = 2)
}
finally {
this.approx = savedApprox
this.leftRoot = savedLeftRoot
}
}
def isSubType(tp1: Type, tp2: Type): Boolean = isSubType(tp1, tp2, ApproxState.Fresh)
override protected def isSub(tp1: Type, tp2: Type)(using Context): Boolean = isSubType(tp1, tp2)
/** The inner loop of the isSubType comparison.
* Recursive calls from recur should go to recur directly if the two types
* compared in the callee are essentially the same as the types compared in the
* caller. "The same" means: represent essentially the same sets of values.
* `recur` should not be used to compare components of types. In this case
* one should use `isSubType(_, _)`.
* `recur` should also not be used to compare approximated versions of the original
* types (as when we go from an abstract type to one of its bounds). In that case
* one should use `isSubType(_, _, a)` where `a` defines the kind of approximation.
*
* Note: Logicaly, `recur` could be nested in `isSubType`, which would avoid
* the instance state consisting `approx` and `leftRoot`. But then the implemented
* code would have two extra parameters for each of the many calls that go from
* one sub-part of isSubType to another.
*/
protected def recur(tp1: Type, tp2: Type): Boolean = trace(s"isSubType ${traceInfo(tp1, tp2)} ${approx.show}", subtyping) {
def monitoredIsSubType = {
if (pendingSubTypes == null) {
pendingSubTypes = new mutable.HashSet[(Type, Type)]
report.log(s"!!! deep subtype recursion involving ${tp1.show} <:< ${tp2.show}, constraint = ${state.constraint.show}")
report.log(s"!!! constraint = ${constraint.show}")
//if (ctx.settings.YnoDeepSubtypes.value) {
// new Error("deep subtype").printStackTrace()
//}
assert(!ctx.settings.YnoDeepSubtypes.value)
if (Config.traceDeepSubTypeRecursions && !this.isInstanceOf[ExplainingTypeComparer])
report.log(explained(_.isSubType(tp1, tp2, approx)))
}
// Eliminate LazyRefs before checking whether we have seen a type before
val normalize = new TypeMap {
val DerefLimit = 10
var derefCount = 0
def apply(t: Type) = t match {
case t: LazyRef =>
// Dereference a lazyref to detect underlying matching types, but
// be careful not to get into an infinite recursion. If recursion count
// exceeds `DerefLimit`, approximate with `t` instead.
derefCount += 1
if t.evaluating || derefCount >= DerefLimit then t
else try mapOver(t.ref) finally derefCount -= 1
case tp: TypeVar =>
tp
case _ =>
mapOver(t)
}
}
val p = (normalize(tp1), normalize(tp2))
!pendingSubTypes(p) && {
try {
pendingSubTypes += p
firstTry
}
finally
pendingSubTypes -= p
}
}
def firstTry: Boolean = tp2 match {
case tp2: NamedType =>
def compareNamed(tp1: Type, tp2: NamedType): Boolean =
val ctx = comparerContext
given Context = ctx // optimization for performance
val info2 = tp2.info
info2 match
case info2: TypeAlias =>
if recur(tp1, info2.alias) then return true
if tp2.asInstanceOf[TypeRef].canDropAlias then return false
case _ =>
tp1 match
case tp1: NamedType =>
tp1.info match {
case info1: TypeAlias =>
if recur(info1.alias, tp2) then return true
if tp1.asInstanceOf[TypeRef].canDropAlias then return false
case _ =>
}
val sym2 = tp2.symbol
var sym1 = tp1.symbol
if (sym1.is(ModuleClass) && sym2.is(ModuleVal))
// For convenience we want X$ <:< X.type
// This is safe because X$ self-type is X.type
sym1 = sym1.companionModule
if ((sym1 ne NoSymbol) && (sym1 eq sym2))
ctx.erasedTypes ||
sym1.isStaticOwner ||
isSubPrefix(tp1.prefix, tp2.prefix) ||
thirdTryNamed(tp2)
else
( (tp1.name eq tp2.name)
&& tp1.isMemberRef
&& tp2.isMemberRef
&& isSubPrefix(tp1.prefix, tp2.prefix)
&& tp1.signature == tp2.signature
&& !(sym1.isClass && sym2.isClass) // class types don't subtype each other
) ||
thirdTryNamed(tp2)
case _ =>
secondTry
end compareNamed
// See the documentation of `FromJavaObjectSymbol`
if !ctx.erasedTypes && tp2.isFromJavaObject then
recur(tp1, defn.AnyType)
else
compareNamed(tp1, tp2)
case tp2: ProtoType =>
isMatchedByProto(tp2, tp1)
case tp2: BoundType =>
tp2 == tp1 || secondTry
case tp2: TypeVar =>
recur(tp1, typeVarInstance(tp2))
case tp2: WildcardType =>
def compareWild = tp2.optBounds match {
case TypeBounds(_, hi) => recur(tp1, hi)
case NoType => true
}
compareWild
case tp2: LazyRef =>
!tp2.evaluating && recur(tp1, tp2.ref)
case tp2: AnnotatedType if !tp2.isRefining =>
recur(tp1, tp2.parent)
case tp2: ThisType =>
def compareThis = {
val cls2 = tp2.cls
tp1 match {
case tp1: NamedType if cls2.is(Module) && cls2.eq(tp1.widen.typeSymbol) =>
cls2.isStaticOwner ||
recur(tp1.prefix, cls2.owner.thisType) ||
secondTry
case _ =>
secondTry
}
}
compareThis
case tp2: SuperType =>
def compareSuper = tp1 match {
case tp1: SuperType =>
recur(tp1.thistpe, tp2.thistpe) &&
isSameType(tp1.supertpe, tp2.supertpe)
case _ =>
secondTry
}
compareSuper
case AndType(tp21, tp22) =>
recur(tp1, tp21) && recur(tp1, tp22)
case OrType(tp21, tp22) =>
if (tp21.stripTypeVar eq tp22.stripTypeVar) recur(tp1, tp21)
else secondTry
case TypeErasure.ErasedValueType(tycon1, underlying2) =>
def compareErasedValueType = tp1 match {
case TypeErasure.ErasedValueType(tycon2, underlying1) =>
(tycon1.symbol eq tycon2.symbol) && isSameType(underlying1, underlying2)
case _ =>
secondTry
}
compareErasedValueType
case ConstantType(v2) =>
tp1 match {
case ConstantType(v1) => v1.value == v2.value && recur(v1.tpe, v2.tpe)
case _ => secondTry
}
case tp2: AnyConstantType =>
if (tp2.tpe.exists) recur(tp1, tp2.tpe)
else tp1 match {
case tp1: ConstantType =>
tp2.tpe = tp1
true
case _ =>
secondTry
}
case _: FlexType =>
true
case _ =>
secondTry
}
def secondTry: Boolean = tp1 match {
case tp1: NamedType =>
tp1.info match {
case info1: TypeAlias =>
if (recur(info1.alias, tp2)) return true
if (tp1.prefix.isStable) return tryLiftedToThis1
case _ =>
if (tp1 eq NothingType) return true
}
thirdTry
case tp1: TypeParamRef =>
def flagNothingBound = {
if (!frozenConstraint && tp2.isRef(NothingClass) && state.isGlobalCommittable) {
def msg = s"!!! instantiated to Nothing: $tp1, constraint = ${constraint.show}"
if (Config.failOnInstantiationToNothing) assert(false, msg)
else report.log(msg)
}
true
}
def compareTypeParamRef =
assumedTrue(tp1) ||
isSubTypeWhenFrozen(bounds(tp1).hi, tp2) || {
if (canConstrain(tp1) && !approx.high)
addConstraint(tp1, tp2, fromBelow = false) && flagNothingBound
else thirdTry
}
compareTypeParamRef
case tp1: ThisType =>
val cls1 = tp1.cls
tp2 match {
case tp2: TermRef if cls1.is(Module) && cls1.eq(tp2.widen.typeSymbol) =>
cls1.isStaticOwner ||
recur(cls1.owner.thisType, tp2.prefix) ||
thirdTry
case _ =>
thirdTry
}
case tp1: SkolemType =>
tp2 match {
case tp2: SkolemType if !ctx.phase.isTyper && recur(tp1.info, tp2.info) => true
case _ => thirdTry
}
case tp1: TypeVar =>
recur(typeVarInstance(tp1), tp2)
case tp1: WildcardType =>
def compareWild = tp1.optBounds match {
case bounds: TypeBounds => recur(bounds.lo, tp2)
case _ => true
}
compareWild
case tp1: LazyRef =>
// If `tp1` is in train of being evaluated, don't force it
// because that would cause an assertionError. Return false instead.
// See i859.scala for an example where we hit this case.
!tp1.evaluating && recur(tp1.ref, tp2)
case tp1: AnnotatedType if !tp1.isRefining =>
recur(tp1.parent, tp2)
case AndType(tp11, tp12) =>
if (tp11.stripTypeVar eq tp12.stripTypeVar) recur(tp11, tp2)
else thirdTry
case tp1 @ OrType(tp11, tp12) =>
compareAtoms(tp1, tp2) match
case Some(b) => return b
case None =>
def joinOK = tp2.dealiasKeepRefiningAnnots match {
case tp2: AppliedType if !tp2.tycon.typeSymbol.isClass =>
// If we apply the default algorithm for `A[X] | B[Y] <: C[Z]` where `C` is a
// type parameter, we will instantiate `C` to `A` and then fail when comparing
// with `B[Y]`. To do the right thing, we need to instantiate `C` to the
// common superclass of `A` and `B`.
recur(tp1.join, tp2)
case _ =>
false
}
def containsAnd(tp: Type): Boolean = tp.dealiasKeepRefiningAnnots match
case tp: AndType => true
case OrType(tp1, tp2) => containsAnd(tp1) || containsAnd(tp2)
case _ => false
def widenOK =
(tp2.widenSingletons eq tp2) &&
(tp1.widenSingletons ne tp1) &&
recur(tp1.widenSingletons, tp2)
widenOK
|| joinOK
|| recur(tp11, tp2) && recur(tp12, tp2)
|| containsAnd(tp1) && recur(tp1.join, tp2)
// An & on the left side loses information. Compensate by also trying the join.
// This is less ad-hoc than it looks since we produce joins in type inference,
// and then need to check that they are indeed supertypes of the original types
// under -Ycheck. Test case is i7965.scala.
case tp1: MatchType =>
val reduced = tp1.reduced
if (reduced.exists) recur(reduced, tp2) else thirdTry
case _: FlexType =>
true
case _ =>
thirdTry
}
def thirdTryNamed(tp2: NamedType): Boolean = tp2.info match {
case info2: TypeBounds =>
def compareGADT: Boolean = {
val gbounds2 = gadtBounds(tp2.symbol)
(gbounds2 != null) &&
(isSubTypeWhenFrozen(tp1, gbounds2.lo) ||
(tp1 match {
case tp1: NamedType if ctx.gadt.contains(tp1.symbol) =>
// Note: since we approximate constrained types only with their non-param bounds,
// we need to manually handle the case when we're comparing two constrained types,
// one of which is constrained to be a subtype of another.
// We do not need similar code in fourthTry, since we only need to care about
// comparing two constrained types, and that case will be handled here first.
ctx.gadt.isLess(tp1.symbol, tp2.symbol) && GADTusage(tp1.symbol) && GADTusage(tp2.symbol)
case _ => false
}) ||
narrowGADTBounds(tp2, tp1, approx, isUpper = false)) &&
{ tp1.isRef(NothingClass) || GADTusage(tp2.symbol) }
}
isSubApproxHi(tp1, info2.lo) || compareGADT || tryLiftedToThis2 || fourthTry
case _ =>
val cls2 = tp2.symbol
if (cls2.isClass)
if (cls2.typeParams.isEmpty) {
if (cls2 eq AnyKindClass) return true
if (tp1.isRef(NothingClass)) return true
if (tp1.isLambdaSub) return false
// Note: We would like to replace this by `if (tp1.hasHigherKind)`
// but right now we cannot since some parts of the standard library rely on the
// idiom that e.g. `List <: Any`. We have to bootstrap without scalac first.
if (cls2 eq AnyClass) return true
if (cls2 == defn.SingletonClass && tp1.isStable) return true
return tryBaseType(cls2)
}
else if (cls2.is(JavaDefined)) {
// If `cls2` is parameterized, we are seeing a raw type, so we need to compare only the symbol
val base = nonExprBaseType(tp1, cls2)
if (base.typeSymbol == cls2) return true
}
else if tp1.isLambdaSub && !tp1.isAnyKind then
return recur(tp1, EtaExpansion(tp2))
fourthTry
}
def thirdTry: Boolean = tp2 match {
case tp2 @ AppliedType(tycon2, args2) =>
compareAppliedType2(tp2, tycon2, args2)
case tp2: NamedType =>
thirdTryNamed(tp2)
case tp2: TypeParamRef =>
def compareTypeParamRef =
assumedTrue(tp2) || {
val alwaysTrue =
// The following condition is carefully formulated to catch all cases
// where the subtype relation is true without needing to add a constraint
// It's tricky because we might need to either approximate tp2 by its
// lower bound or else widen tp1 and check that the result is a subtype of tp2.
// So if the constraint is not yet frozen, we do the same comparison again
// with a frozen constraint, which means that we get a chance to do the
// widening in `fourthTry` before adding to the constraint.
if (frozenConstraint) recur(tp1, bounds(tp2).lo)
else isSubTypeWhenFrozen(tp1, tp2)
alwaysTrue ||
frozenConstraint && (tp1 match {
case tp1: TypeParamRef => constraint.isLess(tp1, tp2)
case _ => false
}) || {
if (canConstrain(tp2) && !approx.low)
addConstraint(tp2, tp1.widenExpr, fromBelow = true)
else fourthTry
}
}
compareTypeParamRef
case tp2: RefinedType =>
def compareRefinedSlow: Boolean = {
val name2 = tp2.refinedName
recur(tp1, tp2.parent) &&
(name2 == nme.WILDCARD || hasMatchingMember(name2, tp1, tp2))
}
def compareRefined: Boolean = {
val tp1w = tp1.widen
val skipped2 = skipMatching(tp1w, tp2)
if ((skipped2 eq tp2) || !Config.fastPathForRefinedSubtype)
tp1 match {
case tp1: AndType =>
// Delay calling `compareRefinedSlow` because looking up a member
// of an `AndType` can lead to a cascade of subtyping checks
// This twist is needed to make collection/generic/ParFactory.scala compile
fourthTry || compareRefinedSlow
case tp1: HKTypeLambda =>
// HKTypeLambdas do not have members.
fourthTry
case _ =>
compareRefinedSlow || fourthTry
}
else // fast path, in particular for refinements resulting from parameterization.
isSubRefinements(tp1w.asInstanceOf[RefinedType], tp2, skipped2) &&
recur(tp1, skipped2)
}
compareRefined
case tp2: RecType =>
def compareRec = tp1.safeDealias match {
case tp1: RecType =>
val rthis1 = tp1.recThis
recur(tp1.parent, tp2.parent.substRecThis(tp2, rthis1))
case NoType => false
case _ =>
val tp1stable = ensureStableSingleton(tp1)
recur(fixRecs(tp1stable, tp1stable.widenExpr), tp2.parent.substRecThis(tp2, tp1stable))
}
compareRec
case tp2: HKTypeLambda =>
def compareTypeLambda: Boolean = tp1.stripTypeVar match {
case tp1: HKTypeLambda =>
/* Don't compare bounds of lambdas under language:Scala2, or t2994 will fail.
* The issue is that, logically, bounds should compare contravariantly,
* but that would invalidate a pattern exploited in t2994:
*
* [X0 <: Number] -> Number <:< [X0] -> Any
*
* Under the new scheme, `[X0] -> Any` is NOT a kind that subsumes
* all other bounds. You'd have to write `[X0 >: Any <: Nothing] -> Any` instead.
* This might look weird, but is the only logically correct way to do it.
*
* Note: it would be nice if this could trigger a migration warning, but I
* am not sure how, since the code is buried so deep in subtyping logic.
*/
def boundsOK =
migrateTo3 ||
tp1.typeParams.corresponds(tp2.typeParams)((tparam1, tparam2) =>
isSubType(tparam2.paramInfo.subst(tp2, tp1), tparam1.paramInfo))
val saved = comparedTypeLambdas
comparedTypeLambdas += tp1
comparedTypeLambdas += tp2
val variancesOK = variancesConform(tp1.typeParams, tp2.typeParams)
try variancesOK && boundsOK && isSubType(tp1.resType, tp2.resType.subst(tp2, tp1))
finally comparedTypeLambdas = saved
case _ =>
val tparams1 = tp1.typeParams
if (tparams1.nonEmpty)
return recur(tp1.EtaExpand(tparams1), tp2) || fourthTry
tp2 match {
case EtaExpansion(tycon2) if tycon2.symbol.isClass && tycon2.symbol.is(JavaDefined) =>
recur(tp1, tycon2) || fourthTry
case _ =>
fourthTry
}
}
compareTypeLambda
case OrType(tp21, tp22) =>
compareAtoms(tp1, tp2) match
case Some(b) => return b
case _ =>
// The next clause handles a situation like the one encountered in i2745.scala.
// We have:
//
// x: A | B, x.type <:< A | X where X is a type variable
//
// We should instantiate X to B instead of x.type or A | B. To do this, we widen
// the LHS to A | B and recur *without indicating that this is a lowApprox*. The
// latter point is important since otherwise we would not get to instantiate X.
// If that succeeds, fine. If not we continue and hit the `either` below.
// That second path is important to handle comparisons with unions of singletons,
// as in `1 <:< 1 | 2`.
val tp1w = tp1.widen
if ((tp1w ne tp1) && recur(tp1w, tp2))
return true
val tp1a = tp1.dealiasKeepRefiningAnnots
if (tp1a ne tp1)
// Follow the alias; this might lead to an OrType on the left which needs to be split
return recur(tp1a, tp2)
// Rewrite T1 <: (T211 & T212) | T22 to T1 <: (T211 | T22) and T1 <: (T212 | T22)
// and analogously for T1 <: T21 | (T221 & T222)
// `|' types to the right of <: are problematic, because
// we have to choose one constraint set or another, which might cut off
// solutions. The rewriting delays the point where we have to choose.
tp21 match {
case AndType(tp211, tp212) =>
return recur(tp1, OrType(tp211, tp22)) && recur(tp1, OrType(tp212, tp22))
case _ =>
}
tp22 match {
case AndType(tp221, tp222) =>
return recur(tp1, OrType(tp21, tp221)) && recur(tp1, OrType(tp21, tp222))
case _ =>
}
either(recur(tp1, tp21), recur(tp1, tp22)) || fourthTry
case tp2: MatchType =>
val reduced = tp2.reduced
if (reduced.exists) recur(tp1, reduced) else fourthTry
case tp2: MethodType =>
def compareMethod = tp1 match {
case tp1: MethodType =>
(tp1.signature consistentParams tp2.signature) &&
matchingMethodParams(tp1, tp2) &&
(!tp2.isImplicitMethod || tp1.isImplicitMethod) &&
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ => false
}
compareMethod
case tp2: PolyType =>
def comparePoly = tp1 match {
case tp1: PolyType =>
(tp1.signature consistentParams tp2.signature) &&
matchingPolyParams(tp1, tp2) &&
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ => false
}
comparePoly
case tp2 @ ExprType(restpe2) =>
def compareExpr = tp1 match {
// We allow ()T to be a subtype of => T.
// We need some subtype relationship between them so that e.g.
// def toString and def toString() don't clash when seen
// as members of the same type. And it seems most logical to take
// ()T <:< => T, since everything one can do with a => T one can
// also do with a ()T by automatic () insertion.
case tp1 @ MethodType(Nil) => isSubType(tp1.resultType, restpe2)
case tp1 @ ExprType(restpe1) => isSubType(restpe1, restpe2)
case _ => fourthTry
}
compareExpr
case tp2 @ TypeBounds(lo2, hi2) =>
def compareTypeBounds = tp1 match {
case tp1 @ TypeBounds(lo1, hi1) =>
((lo2 eq NothingType) || isSubType(lo2, lo1)) &&
((hi2 eq AnyType) && !hi1.isLambdaSub || (hi2 eq AnyKindType) || isSubType(hi1, hi2))
case tp1: ClassInfo =>
tp2 contains tp1
case _ =>
false
}
compareTypeBounds
case tp2: AnnotatedType if tp2.isRefining =>
(tp1.derivesAnnotWith(tp2.annot.sameAnnotation) || defn.isBottomType(tp1)) &&
recur(tp1, tp2.parent)
case ClassInfo(pre2, cls2, _, _, _) =>
def compareClassInfo = tp1 match {
case ClassInfo(pre1, cls1, _, _, _) =>
(cls1 eq cls2) && isSubType(pre1, pre2)
case _ =>
false
}
compareClassInfo
case _ =>
fourthTry
}
def tryBaseType(cls2: Symbol) = {
val base = nonExprBaseType(tp1, cls2)
if (base.exists && (base `ne` tp1))
isSubType(base, tp2, if (tp1.isRef(cls2)) approx else approx.addLow) ||
base.isInstanceOf[OrType] && fourthTry
// if base is a disjunction, this might have come from a tp1 type that
// expands to a match type. In this case, we should try to reduce the type
// and compare the redux. This is done in fourthTry
else fourthTry
}
def fourthTry: Boolean = tp1 match {
case tp1: TypeRef =>
tp1.info match {
case TypeBounds(_, hi1) =>
def compareGADT = {
val gbounds1 = gadtBounds(tp1.symbol)
(gbounds1 != null) &&
(isSubTypeWhenFrozen(gbounds1.hi, tp2) ||
narrowGADTBounds(tp1, tp2, approx, isUpper = true)) &&
{ tp2.isAny || GADTusage(tp1.symbol) }
}
isSubType(hi1, tp2, approx.addLow) || compareGADT || tryLiftedToThis1
case _ =>
def isNullable(tp: Type): Boolean = tp.widenDealias match {
case tp: TypeRef => tp.symbol.isNullableClass
case tp: RefinedOrRecType => isNullable(tp.parent)
case tp: AppliedType => isNullable(tp.tycon)
case AndType(tp1, tp2) => isNullable(tp1) && isNullable(tp2)
case OrType(tp1, tp2) => isNullable(tp1) || isNullable(tp2)
case _ => false
}
val sym1 = tp1.symbol
(sym1 eq NothingClass) && tp2.isValueTypeOrLambda ||
(sym1 eq NullClass) && isNullable(tp2)
}
case tp1 @ AppliedType(tycon1, args1) =>
compareAppliedType1(tp1, tycon1, args1)
case tp1: SingletonType =>
def comparePaths = tp2 match
case tp2: TermRef =>
compareAtoms(tp1, tp2, knownSingletons = true).getOrElse(false)
|| { // needed to make from-tasty work. test cases: pos/i1753.scala, pos/t839.scala
tp2.info.widenExpr.dealias match
case tp2i: SingletonType => recur(tp1, tp2i)
case _ => false
}
case _ => false
comparePaths || isSubType(tp1.underlying.widenExpr, tp2, approx.addLow)
case tp1: RefinedType =>
isNewSubType(tp1.parent)
case tp1: RecType =>
isNewSubType(tp1.parent)
case tp1: HKTypeLambda =>
def compareHKLambda = tp1 match {
case EtaExpansion(tycon1) if tycon1.symbol.isClass && tycon1.symbol.is(JavaDefined) =>
// It's a raw type that was mistakenly eta-expanded to a hk-type.
// This can happen because we do not cook types coming from Java sources
recur(tycon1, tp2)
case _ => tp2 match {
case tp2: HKTypeLambda => false // this case was covered in thirdTry
case _ => tp2.typeParams.hasSameLengthAs(tp1.paramRefs) && isSubType(tp1.resultType, tp2.appliedTo(tp1.paramRefs))
}
}
compareHKLambda
case AndType(tp11, tp12) =>
val tp2a = tp2.dealiasKeepRefiningAnnots
if (tp2a ne tp2) // Follow the alias; this might avoid truncating the search space in the either below
return recur(tp1, tp2a)
// Rewrite (T111 | T112) & T12 <: T2 to (T111 & T12) <: T2 and (T112 | T12) <: T2
// and analogously for T11 & (T121 | T122) & T12 <: T2
// `&' types to the left of <: are problematic, because
// we have to choose one constraint set or another, which might cut off
// solutions. The rewriting delays the point where we have to choose.
tp11 match {
case OrType(tp111, tp112) =>
return recur(AndType(tp111, tp12), tp2) && recur(AndType(tp112, tp12), tp2)
case _ =>
}
tp12 match {
case OrType(tp121, tp122) =>
return recur(AndType(tp11, tp121), tp2) && recur(AndType(tp11, tp122), tp2)
case _ =>
}
val tp1norm = simplifyAndTypeWithFallback(tp11, tp12, tp1)
if (tp1 ne tp1norm) recur(tp1norm, tp2)
else either(recur(tp11, tp2), recur(tp12, tp2))
case tp1: MatchType =>
def compareMatch = tp2 match {
case tp2: MatchType =>
isSameType(tp1.scrutinee, tp2.scrutinee) &&
tp1.cases.corresponds(tp2.cases)(isSubType)
case _ => false
}
recur(tp1.underlying, tp2) || compareMatch
case tp1: AnnotatedType if tp1.isRefining =>
isNewSubType(tp1.parent)
case JavaArrayType(elem1) =>
def compareJavaArray = tp2 match {
case JavaArrayType(elem2) => isSubType(elem1, elem2)
case _ => tp2.isAnyRef
}
compareJavaArray
case tp1: ExprType if ctx.phase.id > gettersPhase.id =>
// getters might have converted T to => T, need to compensate.
recur(tp1.widenExpr, tp2)
case _ =>
false
}
/** When called from `pre1.A <:< pre2.A` does `pre1` relate to `pre2` so that
* the subtype test is true? This is the case if `pre1 <:< pre2`, or
* `pre1` and `pre2` are both this-types of related classes. Here, two classes
* are related if each of them has a self type that derives from the other.
*
* This criterion is a bit dubious. I.e. in the test
*
* A.this.T <:< B.this.T
*
* where `T` is the same type, what relationship must exist between A and B
* for the test to be guaranteed true? The problem is we can't tell without additional
* info. One could be an outer this at the point where we do the test, but that
* location is unknown to us.
*
* The conservative choice would be to require A == B, but then some tests involving
* self types fail. Specifically, t360, t361 and pat_iuli fail the pickling test, and
* Namer fails to compile. At line 203, we get
*
* val Deriver : Property.Key[typer.Deriver] = new Property.Key
* ^
* value Deriver in class Namer is not a legal implementation of `Deriver` in class Namer.
* its type dotty.tools.dotc.util.Property.Key[Namer.this.Deriver]
|* does not conform to dotty.tools.dotc.util.Property.Key[Typer.this.Deriver & Namer.this.Deriver]
*/
def isSubPrefix(pre1: Type, pre2: Type): Boolean =
pre1 match
case pre1: ThisType =>
pre2 match
case pre2: ThisType =>
if pre1.cls.classInfo.selfType.derivesFrom(pre2.cls)
&& pre2.cls.classInfo.selfType.derivesFrom(pre1.cls)
then
subtyping.println(i"assume equal prefixes $pre1 $pre2")
return true
case _ =>
case _ =>
isSubType(pre1, pre2)
/** Compare `tycon[args]` with `other := otherTycon[otherArgs]`, via `>:>` if fromBelow is true, `<:<` otherwise
* (we call this relationship `~:~` in the rest of this comment).
*
* This method works by:
*
* 1. Choosing an appropriate type constructor `adaptedTycon`
* 2. Constraining `tycon` such that `tycon ~:~ adaptedTycon`
* 3. Recursing on `adaptedTycon[args] ~:~ other`
*
* So, how do we pick `adaptedTycon`? When `args` and `otherArgs` have the
* same length the answer is simply:
*
* adaptedTycon := otherTycon
*
* But we also handle having `args.length < otherArgs.length`, in which
* case we need to make up a type constructor of the right kind. For
* example, if `fromBelow = false` and we're comparing:
*
* ?F[A] <:< Either[String, B] where `?F <: [X] =>> Any`
*
* we will choose:
*
* adaptedTycon := [X] =>> Either[String, X]
*
* this allows us to constrain:
*
* ?F <: adaptedTycon
*
* and then recurse on:
*
* adaptedTycon[A] <:< Either[String, B]
*
* In general, given:
*
* - k := args.length
* - d := otherArgs.length - k
*
* `adaptedTycon` will be:
*
* [T_0, ..., T_k-1] =>> otherTycon[otherArgs(0), ..., otherArgs(d-1), T_0, ..., T_k-1]
*
* where `T_n` has the same bounds as `otherTycon.typeParams(d+n)`
*
* Historical note: this strategy is known in Scala as "partial unification"
* (even though the type constructor variable isn't actually unified but only
* has one of its bounds constrained), for background see:
* - The infamous SI-2712: https://github.com/scala/bug/issues/2712
* - The PR against Scala 2.12 implementing -Ypartial-unification: https://github.com/scala/scala/pull/5102
* - Some explanations on how this impacts API design: https://gist.github.com/djspiewak/7a81a395c461fd3a09a6941d4cd040f2
*/
def compareAppliedTypeParamRef(tycon: TypeParamRef, args: List[Type], other: AppliedType, fromBelow: Boolean): Boolean =
def directionalIsSubType(tp1: Type, tp2: Type): Boolean =
if fromBelow then isSubType(tp2, tp1) else isSubType(tp1, tp2)
def directionalRecur(tp1: Type, tp2: Type): Boolean =
if fromBelow then recur(tp2, tp1) else recur(tp1, tp2)
val otherTycon = other.tycon
val otherArgs = other.args
val d = otherArgs.length - args.length
d >= 0 && {
val tparams = tycon.typeParams
val remainingTparams = otherTycon.typeParams.drop(d)
variancesConform(remainingTparams, tparams) && {
val adaptedTycon =
if d > 0 then
HKTypeLambda(remainingTparams.map(_.paramName))(
tl => remainingTparams.map(remainingTparam =>
tl.integrate(remainingTparams, remainingTparam.paramInfo).bounds),
tl => otherTycon.appliedTo(
otherArgs.take(d) ++ tl.paramRefs))
else
otherTycon
(assumedTrue(tycon) || directionalIsSubType(tycon, adaptedTycon.ensureLambdaSub)) &&
directionalRecur(adaptedTycon.appliedTo(args), other)
}
}
end compareAppliedTypeParamRef
/** Subtype test for the hk application `tp2 = tycon2[args2]`.
*/
def compareAppliedType2(tp2: AppliedType, tycon2: Type, args2: List[Type]): Boolean = {
val tparams = tycon2.typeParams
if (tparams.isEmpty) return false // can happen for ill-typed programs, e.g. neg/tcpoly_overloaded.scala
/** True if `tp1` and `tp2` have compatible type constructors and their
* corresponding arguments are subtypes relative to their variance (see `isSubArgs`).
*/
def isMatchingApply(tp1: Type): Boolean = tp1 match {
case AppliedType(tycon1, args1) =>
// We intentionally do not dealias `tycon1` or `tycon2` here.
// `TypeApplications#appliedTo` already takes care of dealiasing type
// constructors when this can be done without affecting type
// inference, doing it here would not only prevent code from compiling
// but could also result in the wrong thing being inferred later, for example
// in `tests/run/hk-alias-unification.scala` we end up checking:
//
// Foo[?F, ?T] <:< Foo[[X] =>> (X, String), Int]
//
// Naturally, we'd like to infer:
//
// ?F := [X] => (X, String)
//
// but if we dealias `Foo` then we'll end up trying to check:
//
// ErasedFoo[?F[?T]] <:< ErasedFoo[(Int, String)]
//
// Because of partial unification, this will succeed, but will produce the constraint:
//
// ?F := [X] =>> (Int, X)
//
// Which is not what we wanted!
def loop(tycon1: Type, args1: List[Type]): Boolean = tycon1 match {
case tycon1: TypeParamRef =>
(tycon1 == tycon2 ||
canConstrain(tycon1) && isSubType(tycon1, tycon2)) &&
isSubArgs(args1, args2, tp1, tparams)
case tycon1: TypeRef =>
tycon2 match {
case tycon2: TypeRef =>
val tycon1sym = tycon1.symbol
val tycon2sym = tycon2.symbol
var touchedGADTs = false
var gadtIsInstantiated = false
def byGadtBounds(sym: Symbol, tp: Type, fromAbove: Boolean): Boolean = {
touchedGADTs = true
val b = gadtBounds(sym)
def boundsDescr = if b == null then "null" else b.show
b != null && inFrozenGadt {
if fromAbove then isSubType(b.hi, tp) else isSubType(tp, b.lo)
} && {
gadtIsInstantiated = b.isInstanceOf[TypeAlias]
true
}
}
val res = (
tycon1sym == tycon2sym
&& isSubPrefix(tycon1.prefix, tycon2.prefix)
|| byGadtBounds(tycon1sym, tycon2, fromAbove = true)
|| byGadtBounds(tycon2sym, tycon1, fromAbove = false)
) && {