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
|
package scala
package reflect
package internal
package tpe
import scala.collection.{ generic }
import generic.Clearable
private[internal] trait TypeConstraints {
self: SymbolTable =>
import definitions._
/** A log of type variable with their original constraints. Used in order
* to undo constraints in the case of isSubType/isSameType failure.
*/
private lazy val _undoLog = new UndoLog
def undoLog = _undoLog
import TypeConstraints.UndoPair
class UndoLog extends Clearable {
type UndoPairs = List[UndoPair[TypeVar, TypeConstraint]]
//OPT this method is public so we can do `manual inlining`
var log: UndoPairs = List()
// register with the auto-clearing cache manager
perRunCaches.recordCache(this)
/** Undo all changes to constraints to type variables up to `limit`. */
//OPT this method is public so we can do `manual inlining`
def undoTo(limit: UndoPairs) {
assertCorrectThread()
while ((log ne limit) && log.nonEmpty) {
val UndoPair(tv, constr) = log.head
tv.constr = constr
log = log.tail
}
}
/** No sync necessary, because record should only
* be called from within an undo or undoUnless block,
* which is already synchronized.
*/
private[reflect] def record(tv: TypeVar) = {
log ::= UndoPair(tv, tv.constr.cloneInternal)
}
def clear() {
if (settings.debug)
self.log("Clearing " + log.size + " entries from the undoLog.")
log = Nil
}
// `block` should not affect constraints on typevars
def undo[T](block: => T): T = {
val before = log
try block
finally undoTo(before)
}
}
/** @PP: Unable to see why these apparently constant types should need vals
* in every TypeConstraint, I lifted them out.
*/
private lazy val numericLoBound = IntTpe
private lazy val numericHiBound = intersectionType(List(ByteTpe, CharTpe), ScalaPackageClass)
/** A class expressing upper and lower bounds constraints of type variables,
* as well as their instantiations.
*/
class TypeConstraint(lo0: List[Type], hi0: List[Type], numlo0: Type, numhi0: Type, avoidWidening0: Boolean = false) {
def this(lo0: List[Type], hi0: List[Type]) = this(lo0, hi0, NoType, NoType)
def this(bounds: TypeBounds) = this(List(bounds.lo), List(bounds.hi))
def this() = this(List(), List())
/* Syncnote: Type constraints are assumed to be used from only one
* thread. They are not exposed in api.Types and are used only locally
* in operations that are exposed from types. Hence, no syncing of any
* variables should be necessary.
*/
/** Guard these lists against AnyClass and NothingClass appearing,
* else loBounds.isEmpty will have different results for an empty
* constraint and one with Nothing as a lower bound. [Actually
* guarding addLoBound/addHiBound somehow broke raw types so it
* only guards against being created with them.]
*/
private var lobounds = lo0 filterNot typeIsNothing
private var hibounds = hi0 filterNot typeIsAny
private var numlo = numlo0
private var numhi = numhi0
private var avoidWidening = avoidWidening0
def loBounds: List[Type] = if (numlo == NoType) lobounds else numlo :: lobounds
def hiBounds: List[Type] = if (numhi == NoType) hibounds else numhi :: hibounds
def avoidWiden: Boolean = avoidWidening
def addLoBound(tp: Type, isNumericBound: Boolean = false) {
// For some reason which is still a bit fuzzy, we must let Nothing through as
// a lower bound despite the fact that Nothing is always a lower bound. My current
// supposition is that the side-effecting type constraint accumulation mechanism
// depends on these subtype tests being performed to make forward progress when
// there are mutually recursive type vars.
// See pos/t6367 and pos/t6499 for the competing test cases.
val mustConsider = tp.typeSymbol match {
case NothingClass => true
case _ => !(lobounds contains tp)
}
if (mustConsider) {
if (isNumericBound && isNumericValueType(tp)) {
if (numlo == NoType || isNumericSubType(numlo, tp))
numlo = tp
else if (!isNumericSubType(tp, numlo))
numlo = numericLoBound
}
else lobounds ::= tp
}
}
def checkWidening(tp: Type) {
if(tp.isStable) avoidWidening = true
else tp match {
case HasTypeMember(_, _) => avoidWidening = true
case _ =>
}
}
def addHiBound(tp: Type, isNumericBound: Boolean = false) {
// My current test case only demonstrates the need to let Nothing through as
// a lower bound, but I suspect the situation is symmetrical.
val mustConsider = tp.typeSymbol match {
case AnyClass => true
case _ => !(hibounds contains tp)
}
if (mustConsider) {
checkWidening(tp)
if (isNumericBound && isNumericValueType(tp)) {
if (numhi == NoType || isNumericSubType(tp, numhi))
numhi = tp
else if (!isNumericSubType(numhi, tp))
numhi = numericHiBound
}
else hibounds ::= tp
}
}
def instWithinBounds = instValid && isWithinBounds(inst)
def isWithinBounds(tp: Type): Boolean = (
lobounds.forall(_ <:< tp)
&& hibounds.forall(tp <:< _)
&& (numlo == NoType || (numlo weak_<:< tp))
&& (numhi == NoType || (tp weak_<:< numhi))
)
var inst: Type = NoType // @M reduce visibility?
def instValid = (inst ne null) && (inst ne NoType)
def cloneInternal = {
val tc = new TypeConstraint(lobounds, hibounds, numlo, numhi, avoidWidening)
tc.inst = inst
tc
}
override def toString = {
val boundsStr = {
val lo = loBounds filterNot typeIsNothing match {
case Nil => ""
case tp :: Nil => " >: " + tp
case tps => tps.mkString(" >: (", ", ", ")")
}
val hi = hiBounds filterNot typeIsAny match {
case Nil => ""
case tp :: Nil => " <: " + tp
case tps => tps.mkString(" <: (", ", ", ")")
}
lo + hi
}
if (inst eq NoType) boundsStr
else boundsStr + " _= " + inst.safeToString
}
}
/** Solve constraint collected in types `tvars`.
*
* @param tvars All type variables to be instantiated.
* @param tparams The type parameters corresponding to `tvars`
* @param variances The variances of type parameters; need to reverse
* solution direction for all contravariant variables.
* @param upper When `true` search for max solution else min.
*/
def solve(tvars: List[TypeVar], tparams: List[Symbol], variances: List[Variance], upper: Boolean, depth: Depth): Boolean = {
def solveOne(tvar: TypeVar, tparam: Symbol, variance: Variance) {
if (tvar.constr.inst == NoType) {
val up = if (variance.isContravariant) !upper else upper
tvar.constr.inst = null
val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo
//Console.println("solveOne0(tv, tp, v, b)="+(tvar, tparam, variance, bound))
var cyclic = bound contains tparam
foreach3(tvars, tparams, variances)((tvar2, tparam2, variance2) => {
val ok = (tparam2 != tparam) && (
(bound contains tparam2)
|| up && (tparam2.info.bounds.lo =:= tparam.tpeHK)
|| !up && (tparam2.info.bounds.hi =:= tparam.tpeHK)
)
if (ok) {
if (tvar2.constr.inst eq null) cyclic = true
solveOne(tvar2, tparam2, variance2)
}
})
if (!cyclic) {
if (up) {
if (bound.typeSymbol != AnyClass) {
debuglog(s"$tvar addHiBound $bound.instantiateTypeParams($tparams, $tvars)")
tvar addHiBound bound.instantiateTypeParams(tparams, tvars)
}
for (tparam2 <- tparams)
tparam2.info.bounds.lo.dealias match {
case TypeRef(_, `tparam`, _) =>
debuglog(s"$tvar addHiBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
tvar addHiBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
case _ =>
}
} else {
if (bound.typeSymbol != NothingClass && bound.typeSymbol != tparam) {
debuglog(s"$tvar addLoBound $bound.instantiateTypeParams($tparams, $tvars)")
tvar addLoBound bound.instantiateTypeParams(tparams, tvars)
}
for (tparam2 <- tparams)
tparam2.info.bounds.hi.dealias match {
case TypeRef(_, `tparam`, _) =>
debuglog(s"$tvar addLoBound $tparam2.tpeHK.instantiateTypeParams($tparams, $tvars)")
tvar addLoBound tparam2.tpeHK.instantiateTypeParams(tparams, tvars)
case _ =>
}
}
}
tvar.constr.inst = NoType // necessary because hibounds/lobounds may contain tvar
//println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen)))
val newInst = (
if (up) {
if (depth.isAnyDepth) glb(tvar.constr.hiBounds)
else glb(tvar.constr.hiBounds, depth)
}
else {
if (depth.isAnyDepth) lub(tvar.constr.loBounds)
else lub(tvar.constr.loBounds, depth)
}
)
debuglog(s"$tvar setInst $newInst")
tvar setInst newInst
//Console.println("solving "+tvar+" "+up+" "+(if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds)+((if (up) (tvar.constr.hiBounds) else tvar.constr.loBounds) map (_.widen))+" = "+tvar.constr.inst)//@MDEBUG
}
}
// println("solving "+tvars+"/"+tparams+"/"+(tparams map (_.info)))
foreach3(tvars, tparams, variances)(solveOne)
def logBounds(tv: TypeVar) = log {
val what = if (!tv.instValid) "is invalid" else s"does not conform to bounds: ${tv.constr}"
s"Inferred type for ${tv.originString} (${tv.inst}) $what"
}
tvars forall (tv => tv.instWithinBounds || util.andFalse(logBounds(tv)))
}
}
private[internal] object TypeConstraints {
// UndoPair is declared in companion object to not hold an outer pointer reference
final case class UndoPair[TypeVar <: SymbolTable#TypeVar,
TypeConstraint <: TypeConstraints#TypeConstraint](tv: TypeVar, tConstraint: TypeConstraint)
}
|
