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
|
package dotty.tools.dotc.core
import Types._, Contexts._, Symbols._, Flags._
import collection.mutable
object TypeComparers {
type Constraints = Map[PolyParam, TypeBounds]
class TypeComparer()(implicit val ctx: Context) extends DotClass {
var constraints = ctx.constraints
private var pendingSubTypes: mutable.Set[(Type, Type)] = null
private var recCount = 0
def addConstraint(param: PolyParam, bounds: TypeBounds): Boolean = {
val newbounds = constraints(param) & bounds
constraints = constraints.updated(param, newbounds)
isSubType(newbounds.lo, newbounds.hi)
}
def isSubType(tp1: Type, tp2: Type): Boolean =
if (tp1 == NoType || tp2 == NoType) false
else if (tp1 eq tp2) true
else {
val cs = constraints
try {
recCount += 1
val result =
if (recCount < LogPendingSubTypesThreshold) firstTry(tp1, tp2)
else monitoredIsSubType(tp1, tp2)
recCount -= 1
if (!result) constraints = cs
result
} catch {
case ex: Throwable =>
recCount -= 1
constraints = cs
throw ex
}
}
def monitoredIsSubType(tp1: Type, tp2: Type) = {
if (pendingSubTypes == null)
pendingSubTypes = new mutable.HashSet[(Type, Type)]
val p = (tp1, tp2)
!pendingSubTypes(p) && {
try {
pendingSubTypes += p
firstTry(tp1, tp2)
} finally {
pendingSubTypes -= p
}
}
}
def firstTry(tp1: Type, tp2: Type): Boolean = ctx.traceIndented(s"$tp1 <:< $tp2") {
tp2 match {
case tp2: NamedType =>
tp1 match {
case tp1: NamedType =>
val sym1 = tp1.symbol
val sym2 = tp2.symbol
val pre1 = tp1.prefix
val pre2 = tp2.prefix
if (sym1 == sym2) (
ctx.erasedTypes
|| (sym1.owner is Package)
|| isSubType(pre1, pre2))
else (
tp1.name == tp2.name && isSubType(pre1, pre2)
|| sym2.isClass && {
val base = tp1.baseType(sym2)
(base ne tp1) && isSubType(base, tp2)
}
|| thirdTryNamed(tp1, tp2))
case _ =>
secondTry(tp1, tp2)
}
case WildcardType | ErrorType =>
true
case tp2: PolyParam if constraints contains tp2 =>
addConstraint(tp2, TypeBounds.lower(tp1))
case _ =>
secondTry(tp1, tp2)
}
}
def secondTry(tp1: Type, tp2: Type): Boolean = tp1 match {
case WildcardType | ErrorType =>
true
case tp1: PolyParam if constraints contains tp1 =>
addConstraint(tp1, TypeBounds.upper(tp2))
case _ =>
thirdTry(tp1, tp2)
}
def thirdTryNamed(tp1: Type, tp2: NamedType): Boolean = tp2.info match {
case TypeBounds(lo, _) =>
isSubType(tp1, lo)
case _ =>
val cls2 = tp2.symbol
( cls2 == defn.SingletonClass && tp1.isStable
|| cls2 == defn.NotNullClass && tp1.isNotNull
|| (defn.hkTraits contains cls2) && isSubTypeHK(tp1, tp2)
|| fourthTry(tp1, tp2)
)
}
def thirdTry(tp1: Type, tp2: Type): Boolean = tp2 match {
case tp2: NamedType =>
thirdTryNamed(tp1, tp2)
case tp2: RefinedType =>
isSubType(tp1, tp2.parent) &&
isSubType(tp1.member(tp2.refinedName).info, tp2.refinedInfo)
case AndType(tp21, tp22) =>
isSubType(tp1, tp21) && isSubType(tp1, tp22)
case OrType(tp21, tp22) =>
isSubType(tp1, tp21) || isSubType(tp1, tp22)
case tp2 @ MethodType(_, formals1) =>
tp1 match {
case tp1 @ MethodType(_, formals2) =>
tp1.signature == tp2.signature &&
matchingParams(formals1, formals2, tp1.isJava, tp2.isJava) &&
tp1.isImplicit == tp2.isImplicit && // needed?
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ =>
false
}
case tp2: PolyType =>
tp1 match {
case tp1: PolyType =>
tp1.signature == tp2.signature &&
(tp1.paramBounds corresponds tp2.paramBounds)((b1, b2) =>
isSameType(b1, b2.subst(tp2, tp1))) &&
isSubType(tp1.resultType, tp2.resultType.subst(tp2, tp1))
case _ =>
false
}
case tp2 @ ExprType(restpe1) =>
tp1 match {
case tp1 @ ExprType(restpe2) =>
isSubType(restpe1, restpe2)
case _ =>
false
}
case TypeBounds(lo2, hi2) =>
tp1 match {
case TypeBounds(lo1, hi1) =>
isSubType(lo2, lo1) && isSubType(hi1, hi2)
case tp1: ClassInfo =>
val tt = tp1.typeConstructor // was typeTemplate
isSubType(lo2, tt) && isSubType(tt, hi2)
case _ =>
false
}
/* needed?
case ClassInfo(pre2, denot2) =>
tp1 match {
case ClassInfo(pre1, denot1) =>
(denot1 eq denot2) && isSubType(pre2, pre1) // !!! or isSameType?
}
*/
case _ =>
fourthTry(tp1, tp2)
}
def fourthTry(tp1: Type, tp2: Type): Boolean = tp1 match {
case tp1: TypeRef =>
( (tp1 eq defn.NothingType)
|| (tp1 eq defn.NullType) && tp2.typeSymbol.isNonValueClass
|| !tp1.symbol.isClass && isSubType(tp1.info.bounds.hi, tp2)
)
case tp1: SingletonType =>
isSubType(tp1.underlying, tp2)
case tp1: RefinedType =>
isSubType(tp1.parent, tp2)
case AndType(tp11, tp12) =>
isSubType(tp11, tp2) || isSubType(tp12, tp2)
case OrType(tp11, tp12) =>
isSubType(tp11, tp2) && isSubType(tp12, tp2)
case _ =>
false
}
/* not needed
def isSubArgs(tps1: List[Type], tps2: List[Type], tparams: List[TypeSymbol]): Boolean = tparams match {
case tparam :: tparams1 =>
val variance = tparam.variance
val t1 = tps1.head
val t2 = tps2.head
(variance > 0 || isSubType(t2, t1)) &&
(variance < 0 || isSubType(t1, t2)) &&
isSubArgs(tps1.tail, tps2.tail, tparams1)
case _ =>
assert(tps1.isEmpty && tps2.isEmpty)
true
}
*/
/** Is `tp1` a subtype of a type `tp2` of the form
* `scala.HigerKindedN[xBetween_1[Lo_1, Hi_1], ..., xBetween_n[Lo_n, Hi_n]]`?
* This is the case if `tp1` has `n` type parameters and
* for all `0 <= i < n`, the i'th type parameter's bounds are contained in
* `Lo_i..Hi_i` and its variance corresponds to the xBetween_i class.
*/
def isSubTypeHK(tp1: Type, tp2: Type): Boolean = {
val tparams = tp1.typeParams
val hkArgs = tp2.typeArgs
(hkArgs.length == tparams.length) && {
val base = ctx.newSkolemSingleton(tp1)
(hkArgs, tparams).zipped.forall { (hkArg, tparam) =>
val lo2 :: hi2 :: Nil = hkArg.typeArgs
val TypeBounds(lo1, hi1) = base.memberInfo(tparam)
lo2 <:< lo1 && hi1 <:< hi2 &&
defn.hkBoundsClass(tparam.variance) == hkArg.typeSymbol
}
}
}
/** A function implementing `tp1` matches `tp2`. */
final def matchesType(tp1: Type, tp2: Type, alwaysMatchSimple: Boolean): Boolean = tp1 match {
case tp1: MethodType =>
tp2 match {
case tp2: MethodType =>
tp1.isImplicit == tp2.isImplicit &&
matchingParams(tp1.paramTypes, tp2.paramTypes, tp1.isJava, tp2.isJava) &&
matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple)
case tp2: ExprType =>
tp1.paramNames.isEmpty &&
matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
case _ =>
false
}
case tp1: ExprType =>
tp2 match {
case tp2: MethodType =>
tp2.paramNames.isEmpty &&
matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
case tp2: ExprType =>
matchesType(tp1.resultType, tp2.resultType, alwaysMatchSimple)
case _ =>
false // was: matchesType(tp1.resultType, tp2, alwaysMatchSimple)
}
case tp1: PolyType =>
tp2 match {
case tp2: PolyType =>
sameLength(tp1.paramNames, tp2.paramNames) &&
matchesType(tp1.resultType, tp2.resultType.subst(tp2, tp1), alwaysMatchSimple)
case _ =>
false
}
case _ =>
tp2 match {
case _: MethodType | _: PolyType =>
false
case tp2: ExprType =>
false // was: matchesType(tp1, tp2.resultType, alwaysMatchSimple)
case _ =>
alwaysMatchSimple || isSameType(tp1, tp2)
}
}
/** Are `syms1` and `syms2` parameter lists with pairwise equivalent types? */
private def matchingParams(formals1: List[Type], formals2: List[Type], isJava1: Boolean, isJava2: Boolean): Boolean = formals1 match {
case formal1 :: rest1 =>
formals2 match {
case formal2 :: rest2 =>
( isSameType(formal1, formal2)
|| isJava1 && formal2 == defn.ObjectType && formal1 == defn.AnyType
|| isJava2 && formal1 == defn.ObjectType && formal2 == defn.AnyType
) && matchingParams(rest1, rest2, isJava1, isJava2)
case nil =>
false
}
case nil =>
formals2.isEmpty
}
def isSameType(tp1: Type, tp2: Type): Boolean =
if (tp1 == NoType || tp2 == NoType) false
else if (tp1 eq tp2) true
else isSubType(tp1, tp2) && isSubType(tp2, tp1)
}
}
|
