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
|
package dotty.tools
package dotc
package typer
import core._
import ast._
import Contexts._, Types._, Flags._, Denotations._, Names._, StdNames._, NameOps._, Symbols._
import Trees._
import annotation.unchecked
import util.Positions._
import util.{Stats, SimpleMap}
import Decorators._
import ErrorReporting.{errorType, InfoString}
import collection.mutable.ListBuffer
object Inferencing {
import tpd._
/** A trait defining an `isCompatible` method. */
trait Compatibility {
/** Is there an implicit conversion from `tp` to `pt`? */
def viewExists(tp: Type, pt: Type)(implicit ctx: Context): Boolean
/** A type `tp` is compatible with a type `pt` if one of the following holds:
* 1. `tp` is a subtype of `pt`
* 2. `pt` is by name parameter type, and `tp` is compatible with its underlying type
* 3. there is an implicit conversion from `tp` to `pt`.
*/
def isCompatible(tp: Type, pt: Type)(implicit ctx: Context): Boolean = (
(tp <:< pt)
|| (pt isRef defn.ByNameParamClass) && (tp <:< pt.typeArgs.head)
|| viewExists(tp, pt))
}
class SelectionProto(name: Name, proto: Type)
extends RefinedType(WildcardType, name)(_ => proto) with ProtoType with Compatibility {
override def viewExists(tp: Type, pt: Type)(implicit ctx: Context): Boolean = false
override def isMatchedBy(tp1: Type)(implicit ctx: Context) = {
def testCompatible(mbrType: Type)(implicit ctx: Context) =
isCompatible(normalize(mbrType), /*(new WildApprox) apply (needed?)*/ proto)
name == nme.WILDCARD || {
val mbr = tp1.member(name)
mbr.exists && mbr.hasAltWith(m => testCompatible(m.info)(ctx.fresh.withExploreTyperState))
}
}
override def toString = "Proto" + super.toString
}
/** Create a selection proto-type, but only one level deep;
* treat constructors specially
*/
def selectionProto(name: Name, tp: Type) =
if (name.isConstructorName) WildcardType
else {
val rtp = tp match {
case tp: ProtoType => WildcardType
case _ => tp
}
new SelectionProto(name, rtp)
}
object AnySelectionProto extends SelectionProto(nme.WILDCARD, WildcardType)
case class FunProto(args: List[untpd.Tree], override val resultType: Type, typer: Typer)(implicit ctx: Context) extends UncachedGroundType with ProtoType {
private var myTypedArgs: List[Tree] = Nil
def isMatchedBy(tp: Type)(implicit ctx: Context) =
typer.isApplicableToTrees(tp, typedArgs, resultType)
def argsAreTyped: Boolean = myTypedArgs.nonEmpty || args.isEmpty
def typedArgs: List[Tree] = {
if (!argsAreTyped)
myTypedArgs = args mapconserve { arg =>
val targ = myTypedArg(arg)
if (targ != null) targ else typer.typed(arg)
}
myTypedArgs
}
private var myTypedArg: SimpleMap[untpd.Tree, Tree] = SimpleMap.Empty
def typedArg(arg: untpd.Tree, formal: Type)(implicit ctx: Context): Tree = {
var targ = myTypedArg(arg)
if (targ == null) {
targ = typer.typedUnadapted(arg, formal)
myTypedArg = myTypedArg.updated(arg, targ)
}
typer.adapt(targ, formal)
}
override def toString = s"FunProto(${args mkString ","} => $resultType)"
}
case class ViewProto(argType: Type, override val resultType: Type)(implicit ctx: Context) extends CachedGroundType with ProtoType {
def isMatchedBy(tp: Type)(implicit ctx: Context) =
ctx.typer.isApplicableToTypes(tp, argType :: Nil, resultType)
override def namedPartsWith(p: NamedType => Boolean)(implicit ctx: Context): Set[NamedType] =
argType.namedPartsWith(p) | resultType.namedPartsWith(p)
override def computeHash = doHash(argType, resultType)
}
case class PolyProto(nargs: Int, override val resultType: Type) extends UncachedGroundType
object AnyFunctionProto extends UncachedGroundType with ProtoType {
def isMatchedBy(tp: Type)(implicit ctx: Context) = true
}
/** The normalized form of a type
* - unwraps polymorphic types, tracking their parameters in the current constraint
* - skips implicit parameters
* - converts non-dependent method types to the corresponding function types
* - dereferences parameterless method types
*/
def normalize(tp: Type)(implicit ctx: Context): Type = Stats.track("normalize") {
tp.widenSingleton match {
case pt: PolyType => normalize(ctx.track(pt).resultType)
case mt: MethodType if !mt.isDependent =>
if (mt.isImplicit) mt.resultType
else defn.FunctionType(mt.paramTypes, mt.resultType)
case et: ExprType => et.resultType
case _ => tp
}
}
/** An enumeration controlling the degree of forcing in "is-dully-defined" checks. */
object ForceDegree extends Enumeration {
val none, // don't force type variables
noBottom, // force type variables, fail if forced to Nothing or Null
all = Value // force type variables, don't fail
}
/** Is type fully defined, meaning the type does not contain wildcard types
* or uninstantiated type variables. As a side effect, this will minimize
* any uninstantiated type variables, provided that
* - the instance type for the variable is not Nothing or Null
* - the overall result of `isFullYDefined` is `true`.
* Variables that are successfully minimized do not count as uninstantiated.
*/
def isFullyDefined(tp: Type, force: ForceDegree.Value)(implicit ctx: Context): Boolean = {
val nestedCtx = ctx.fresh.withNewTyperState
val result = new IsFullyDefinedAccumulator(force)(nestedCtx).traverse(tp)
if (result) nestedCtx.typerState.commit()
result
}
def fullyDefinedType(tp: Type, what: String, pos: Position)(implicit ctx: Context) =
if (isFullyDefined(tp, ForceDegree.all)) tp
else throw new Error(i"internal error: type of $what $tp is not fully defined, pos = $pos") // !!! DEBUG
private class IsFullyDefinedAccumulator(force: ForceDegree.Value)(implicit ctx: Context) extends TypeAccumulator[Boolean] {
def traverse(tp: Type): Boolean = apply(true, tp)
def apply(x: Boolean, tp: Type) = !x || isOK(tp) && foldOver(x, tp)
def isOK(tp: Type): Boolean = tp match {
case _: WildcardType =>
false
case tvar: TypeVar if force != ForceDegree.none && !tvar.isInstantiated =>
val inst = tvar.instantiate(fromBelow = true)
println(i"forced instantiation of ${tvar.origin} = $inst")
(force == ForceDegree.all || inst != defn.NothingType && inst != defn.NullType) && traverse(inst)
case _ =>
true
}
}
def widenForSelector(tp: Type)(implicit ctx: Context): Type = tp.widen match {
case tp: TypeRef if tp.symbol.isAbstractOrAliasType => widenForSelector(tp.bounds.hi)
case tp => tp
}
def checkBounds(args: List[Tree], poly: PolyType, pos: Position)(implicit ctx: Context): Unit = {
}
def checkStable(tp: Type, pos: Position)(implicit ctx: Context): Type = {
if (!tp.isStable)
ctx.error(i"Prefix $tp is not stable", pos)
tp
}
def checkClassTypeWithStablePrefix(tp: Type, pos: Position)(implicit ctx: Context): ClassSymbol = tp.dealias match {
case tp: TypeRef if tp.symbol.isClass =>
checkStable(tp.prefix, pos)
tp.symbol.asClass
case _: TypeVar | _: AnnotatedType =>
checkClassTypeWithStablePrefix(tp.asInstanceOf[TypeProxy].underlying, pos)
case _ =>
ctx.error(i"$tp is not a class type", pos)
defn.ObjectClass
}
def checkInstantiatable(cls: ClassSymbol, pos: Position): Unit = {
???
}
implicit class Infer(val ictx: Context) extends AnyVal {
implicit private def ctx = ictx
private def state = ctx.typerState
/** Add all parameters in given polytype `pt` to the constraint's domain.
* If the constraint contains already some of these parameters in its domain,
* make a copy of the polytype and add the copy's type parameters instead.
* Return either the original polytype, or the copy, if one was made.
* Also, if `owningTree` is non-empty, add a type variable for each parameter.
* @return The tracked polytype, and the list of created type variables.
*/
def track(pt: PolyType, owningTree: untpd.Tree): (PolyType, List[TypeVar]) = {
def howmany = if (owningTree.isEmpty) "no" else "some"
def committable = if (ctx.typerState.isCommittable) "committable" else "uncommittable"
assert(owningTree.isEmpty != ctx.typerState.isCommittable,
s"inconsistent: $howmany typevars were added to $committable constraint ${state.constraint}")
val tracked =
if (state.constraint contains pt) pt.copy(pt.paramNames, pt.paramBounds, pt.resultType)
else pt
val tvars = if (owningTree.isEmpty) Nil else newTypeVars(tracked, owningTree)
state.constraint = state.constraint.add(tracked, tvars)
//if (!owningTree.isEmpty)
// state.constraint = state.constraint.transformed(pt, _.substParams(pt, tvars))
(tracked, tvars)
}
/** Create new type variables for the parameters of a poly type.
* @param pos The position of the new type variables (relevant for
* interpolateUndetVars
*/
private def newTypeVars(pt: PolyType, owningTree: untpd.Tree): List[TypeVar] =
for (n <- (0 until pt.paramNames.length).toList)
yield new TypeVar(PolyParam(pt, n), ctx.typerState, owningTree)
/** Same as `track(pt, EmptyTree)`, but returns just the created polytype */
def track(pt: PolyType): PolyType = track(pt, EmptyTree)._1
/** Interpolate those undetermined type variables in the widened type of this tree
* which are introduced by type application contained in the tree.
* If such a variable appears covariantly in type `tp` or does not appear at all,
* approximate it by its lower bound. Otherwise, if it appears contravariantly
* in type `tp` approximate it by its upper bound.
*/
def interpolateUndetVars(tree: Tree): Unit = Stats.track("interpolateUndetVars") {
val tp = tree.tpe.widen
println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${ctx.typerState.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}")
println(s"qualifying undet vars: ${ctx.typerState.uninstVars filter qualifies map (_.show)}")
println(s"fulltype: $tp") // !!! DEBUG
println(s"constraint: ${ctx.typerState.constraint.show}")
def qualifies(tvar: TypeVar) = tree contains tvar.owningTree
val vs = tp.variances(tvar =>
(ctx.typerState.constraint contains tvar) && qualifies(tvar))
println(s"variances = $vs")
var changed = false
for ((tvar, v) <- vs)
if (v != 0) {
println(s"interpolate ${if (v == 1) "co" else "contra"}variant ${tvar.show} in ${tp.show}")
tvar.instantiate(fromBelow = v == 1)
changed = true
}
if (changed)
interpolateUndetVars(tree)
else
ctx.typerState.constraint.foreachUninstVar { tvar =>
if (!(vs contains tvar) && qualifies(tvar)) {
println(s"instantiating non-occurring $tvar in $tp")
tvar.instantiate(fromBelow = true)
}
}
}
/** Instantiate undetermined type variables to that type `tp` is
* maximized and return None. If this is not possible, because a non-variant
* typevar is not uniquely determined, return that typevar in a Some.
*/
def maximizeType(tp: Type): Option[TypeVar] = Stats.track("maximizeType") {
val vs = tp.variances(tvar => ctx.typerState.constraint contains tvar)
var result: Option[TypeVar] = None
for ((tvar, v) <- vs)
if (v == 1) tvar.instantiate(fromBelow = false)
else if (v == -1) tvar.instantiate(fromBelow = true)
else {
val bounds = ctx.typerState.constraint.bounds(tvar.origin)
if (!(bounds.hi <:< bounds.lo)) result = Some(tvar)
tvar.instantiate(fromBelow = false)
}
result
}
def isSubTypes(actuals: List[Type], formals: List[Type])(implicit ctx: Context): Boolean = formals match {
case formal :: formals1 =>
actuals match {
case actual :: actuals1 => actual <:< formal && isSubTypes(actuals1, formals1)
case _ => false
}
case nil =>
actuals.isEmpty
}
/* not needed right now
def formalParameters[T](mtp: MethodType, actuals: List[T])(isRepeated: T => Boolean)(implicit ctx: Context) =
if (mtp.isVarArgs && !(actuals.nonEmpty && isRepeated(actuals.last))) {
val leading = mtp.paramTypes.init
val repeated = mtp.paramTypes.last.typeArgs.head
val trailing = List.fill(actuals.length - leading.length)(repeated)
leading ++ trailing
}
else mtp.paramTypes
*/
}
}
|