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
|
/* NSC -- new scala compiler
* Copyright 2005-2011 LAMP/EPFL
* @author Martin Odersky
*/
package scala.reflect
package internal
import scala.collection.{ mutable, immutable }
import scala.tools.util.StringOps.{ countAsString, countElementsAsString }
trait Kinds {
self: SymbolTable =>
import definitions._
private type SymPair = ((Symbol, Symbol)) // ((Argument, Parameter))
case class KindErrors(
arity: List[SymPair] = Nil,
variance: List[SymPair] = Nil,
strictness: List[SymPair] = Nil
) {
def isEmpty = arity.isEmpty && variance.isEmpty && strictness.isEmpty
def arityError(syms: SymPair) = copy(arity = arity :+ syms)
def varianceError(syms: SymPair) = copy(variance = variance :+ syms)
def strictnessError(syms: SymPair) = copy(strictness = strictness :+ syms)
def ++(errs: KindErrors) = KindErrors(
arity ++ errs.arity,
variance ++ errs.variance,
strictness ++ errs.strictness
)
// @M TODO this method is duplicated all over the place (varianceString)
private def varStr(s: Symbol): String =
if (s.isCovariant) "covariant"
else if (s.isContravariant) "contravariant"
else "invariant";
private def qualify(a0: Symbol, b0: Symbol): String = if (a0.toString != b0.toString) "" else {
if((a0 eq b0) || (a0.owner eq b0.owner)) ""
else {
var a = a0; var b = b0
while (a.owner.name == b.owner.name) { a = a.owner; b = b.owner}
if (a.locationString ne "") " (" + a.locationString.trim + ")" else ""
}
}
private def kindMessage(a: Symbol, p: Symbol)(f: (String, String) => String): String =
f(a+qualify(a,p), p+qualify(p,a))
private def strictnessMessage(a: Symbol, p: Symbol) =
kindMessage(a, p)("%s's bounds %s are stricter than %s's declared bounds %s".format(
_, a.info, _, p.info))
private def varianceMessage(a: Symbol, p: Symbol) =
kindMessage(a, p)("%s is %s, but %s is declared %s".format(_, varStr(a), _, varStr(p)))
private def arityMessage(a: Symbol, p: Symbol) =
kindMessage(a, p)("%s has %s, but %s has %s".format(
_, countElementsAsString(a.typeParams.length, "type parameter"),
_, countAsString(p.typeParams.length))
)
def errorMessage(targ: Type, tparam: Symbol): String = (
(targ+"'s type parameters do not match "+tparam+"'s expected parameters: ")
+ (arity map { case (a, p) => arityMessage(a, p) } mkString ", ")
+ (variance map { case (a, p) => varianceMessage(a, p) } mkString ", ")
+ (strictness map { case (a, p) => strictnessMessage(a, p) } mkString ", ")
)
}
val NoKindErrors = KindErrors(Nil, Nil, Nil)
// TODO: this desperately needs to be cleaned up
// plan: split into kind inference and subkinding
// every Type has a (cached) Kind
def kindsConform(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): Boolean =
checkKindBounds0(tparams, targs, pre, owner, false).isEmpty
/** Check whether `sym1`'s variance conforms to `sym2`'s variance.
*
* If `sym2` is invariant, `sym1`'s variance is irrelevant. Otherwise they must be equal.
*/
private def variancesMatch(sym1: Symbol, sym2: Symbol) = (
sym2.variance==0
|| sym1.variance==sym2.variance
)
/** Check well-kindedness of type application (assumes arities are already checked) -- @M
*
* This check is also performed when abstract type members become concrete (aka a "type alias") -- then tparams.length==1
* (checked one type member at a time -- in that case, prefix is the name of the type alias)
*
* Type application is just like value application: it's "contravariant" in the sense that
* the type parameters of the supplied type arguments must conform to the type parameters of
* the required type parameters:
* - their bounds must be less strict
* - variances must match (here, variances are absolute, the variance of a type parameter does not influence the variance of its higher-order parameters)
* - @M TODO: are these conditions correct,sufficient&necessary?
*
* e.g. class Iterable[t, m[+x <: t]] --> the application Iterable[Int, List] is okay, since
* List's type parameter is also covariant and its bounds are weaker than <: Int
*/
def checkKindBounds0(
tparams: List[Symbol],
targs: List[Type],
pre: Type,
owner: Symbol,
explainErrors: Boolean
): List[(Type, Symbol, KindErrors)] = {
// instantiate type params that come from outside the abstract type we're currently checking
def transform(tp: Type, clazz: Symbol): Type =
tp.asSeenFrom(pre, clazz)
def transformedBounds(p: Symbol, o: Symbol) =
transform(p.info.instantiateTypeParams(tparams, targs).bounds, o)
// check that the type parameters hkargs to a higher-kinded type conform to the
// expected params hkparams
def checkKindBoundsHK(
hkargs: List[Symbol],
arg: Symbol,
param: Symbol,
paramowner: Symbol,
underHKParams: List[Symbol],
withHKArgs: List[Symbol]
): KindErrors = {
var kindErrors: KindErrors = NoKindErrors
def bindHKParams(tp: Type) = tp.substSym(underHKParams, withHKArgs)
// @M sometimes hkargs != arg.typeParams, the symbol and the type may
// have very different type parameters
val hkparams = param.typeParams
def kindCheck(cond: Boolean, f: KindErrors => KindErrors) {
if (!cond)
kindErrors = f(kindErrors)
}
if (settings.debug.value) {
log("checkKindBoundsHK expected: "+ param +" with params "+ hkparams +" by definition in "+ paramowner)
log("checkKindBoundsHK supplied: "+ arg +" with params "+ hkargs +" from "+ owner)
log("checkKindBoundsHK under params: "+ underHKParams +" with args "+ withHKArgs)
}
if (!sameLength(hkargs, hkparams)) {
// Any and Nothing are kind-overloaded
if (arg == AnyClass || arg == NothingClass) NoKindErrors
// shortcut: always set error, whether explainTypesOrNot
else return kindErrors.arityError(arg -> param)
}
else foreach2(hkargs, hkparams) { (hkarg, hkparam) =>
if (hkparam.typeParams.isEmpty && hkarg.typeParams.isEmpty) { // base-case: kind *
kindCheck(variancesMatch(hkarg, hkparam), _ varianceError (hkarg -> hkparam))
// instantiateTypeParams(tparams, targs)
// higher-order bounds, may contain references to type arguments
// substSym(hkparams, hkargs)
// these types are going to be compared as types of kind *
//
// Their arguments use different symbols, but are
// conceptually the same. Could also replace the types by
// polytypes, but can't just strip the symbols, as ordering
// is lost then.
val declaredBounds = transformedBounds(hkparam, paramowner)
val declaredBoundsInst = bindHKParams(declaredBounds)
val argumentBounds = transform(hkarg.info.bounds, owner)
kindCheck(declaredBoundsInst <:< argumentBounds, _ strictnessError (hkarg -> hkparam))
debuglog(
"checkKindBoundsHK base case: " + hkparam +
" declared bounds: " + declaredBounds +
" after instantiating earlier hkparams: " + declaredBoundsInst + "\n" +
"checkKindBoundsHK base case: "+ hkarg +
" has bounds: " + argumentBounds
)
}
else {
debuglog("checkKindBoundsHK recursing to compare params of "+ hkparam +" with "+ hkarg)
kindErrors ++= checkKindBoundsHK(
hkarg.typeParams,
hkarg,
hkparam,
paramowner,
underHKParams ++ hkparam.typeParams,
withHKArgs ++ hkarg.typeParams
)
}
if (!explainErrors && !kindErrors.isEmpty)
return kindErrors
}
if (explainErrors) kindErrors
else NoKindErrors
}
if (settings.debug.value && (tparams.nonEmpty || targs.nonEmpty)) log(
"checkKindBounds0(" + tparams + ", " + targs + ", " + pre + ", "
+ owner + ", " + explainErrors + ")"
)
flatMap2(tparams, targs) { (tparam, targ) =>
// Prevent WildcardType from causing kind errors, as typevars may be higher-order
if (targ == WildcardType) Nil else {
// force symbol load for #4205
targ.typeSymbolDirect.info
// @M must use the typeParams of the *type* targ, not of the *symbol* of targ!!
val tparamsHO = targ.typeParams
if (targ.isHigherKinded || tparam.typeParams.nonEmpty) {
// NOTE: *not* targ.typeSymbol, which normalizes
val kindErrors = checkKindBoundsHK(
tparamsHO, targ.typeSymbolDirect, tparam,
tparam.owner, tparam.typeParams, tparamsHO
)
if (kindErrors.isEmpty) Nil else {
if (explainErrors) List((targ, tparam, kindErrors))
// Return as soon as an error is seen if there's nothing to explain.
else return List((NoType, NoSymbol, NoKindErrors))
}
}
else Nil
}
}
}
}
|