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
|
package dotty.tools
package dotc
package typer
import core._
import ast._
import Contexts._, Types._, Flags._, Denotations._, Names._, StdNames._, NameOps._, Symbols._
import Trees._
import Constants._
import Scopes._
import ProtoTypes._
import annotation.unchecked
import util.Positions._
import util.{Stats, SimpleMap}
import util.common._
import Decorators._
import Uniques._
import ErrorReporting.{errorType, InfoString}
import config.Printers._
import collection.mutable
trait Inferencing { this: Checking =>
import tpd._
/** 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, according to the given force degree,
* but only if 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.clearTyperState
val result = new IsFullyDefinedAccumulator(force)(nestedCtx).process(tp)
if (result) nestedCtx.typerState.commit()
result
}
/** The fully defined type, where all type variables are forced.
* Throws an error if type contains wildcards.
*/
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
/** The accumulator which forces type variables using the policy encoded in `force`
* and returns whether the type is fully defined. Two phases:
* 1st Phase: Try to stantiate covariant and non-variant type variables to
* their lower bound. Record whether succesful.
* 2nd Phase: If first phase was succesful, instantiate all remaining type variables
* to their upper bound.
*/
private class IsFullyDefinedAccumulator(force: ForceDegree.Value)(implicit ctx: Context) extends TypeAccumulator[Boolean] {
private def instantiate(tvar: TypeVar, fromBelow: Boolean): Type = {
val inst = tvar.instantiate(fromBelow)
typr.println(i"forced instantiation of ${tvar.origin} = $inst")
inst
}
private var toMaximize: Boolean = false
def apply(x: Boolean, tp: Type): Boolean = tp.dealias match {
case _: WildcardType =>
false
case tvar: TypeVar if !tvar.isInstantiated =>
if (force == ForceDegree.none) false
else {
val minimize =
variance >= 0 && !(
force == ForceDegree.noBottom &&
isBottomType(ctx.typeComparer.approximation(tvar.origin, fromBelow = true)))
if (minimize) instantiate(tvar, fromBelow = true)
else toMaximize = true
foldOver(x, tvar)
}
case tp =>
foldOver(x, tp)
}
private class UpperInstantiator(implicit ctx: Context) extends TypeAccumulator[Unit] {
def apply(x: Unit, tp: Type): Unit = {
tp match {
case tvar: TypeVar if !tvar.isInstantiated =>
instantiate(tvar, fromBelow = false)
case _ =>
}
foldOver(x, tp)
}
}
def process(tp: Type): Boolean = {
val res = apply(true, tp)
if (res && toMaximize) new UpperInstantiator().apply((), tp)
res
}
}
def isBottomType(tp: Type)(implicit ctx: Context) =
tp == defn.NothingType || tp == defn.NullType
/** Recursively widen and also follow type declarations and type aliases. */
def widenForMatchSelector(tp: Type)(implicit ctx: Context): Type = tp.widen match {
case tp: TypeRef if !tp.symbol.isClass => widenForMatchSelector(tp.info.bounds.hi)
case tp => tp
}
/** Following type aliases and stripping refinements and annotations, if one arrives at a
* class type reference where the class has a companion module, a reference to
* that companion module. Otherwise NoType
*/
def companionRef(tp: Type)(implicit ctx: Context): Type = tp.underlyingClassRef match {
case tp: TypeRef =>
val companion = tp.classSymbol.companionModule
if (companion.exists)
companion.valRef.asSeenFrom(tp.prefix, companion.symbol.owner)
else NoType
case _ => NoType
}
/** Ensure that the first type in a list of parent types Ps points to a non-trait class.
* If that's not already the case, add one. The added class type CT is determined as follows.
* First, let C be the unique class such that
* - there is a parent P_i such that P_i derives from C, and
* - for every class D: If some parent P_j, j <= i derives from D, then C derives from D.
* Then, let CT be the smallest type which
* - has C as its class symbol, and
* - for all parents P_i: If P_i derives from C then P_i <:< CT.
*/
def ensureFirstIsClass(parents: List[Type])(implicit ctx: Context): List[Type] = {
def realClassParent(cls: Symbol): ClassSymbol =
if (!cls.isClass) defn.ObjectClass
else if (!(cls is Trait)) cls.asClass
else cls.asClass.classParents match {
case parentRef :: _ => realClassParent(parentRef.symbol)
case nil => defn.ObjectClass
}
def improve(candidate: ClassSymbol, parent: Type): ClassSymbol = {
val pcls = realClassParent(parent.classSymbol)
if (pcls derivesFrom candidate) pcls else candidate
}
parents match {
case p :: _ if p.classSymbol.isRealClass => parents
case _ =>
val pcls = (defn.ObjectClass /: parents)(improve)
typr.println(i"ensure first is class $parents%, % --> ${parents map (_ baseTypeWithArgs pcls)}%, %")
val ptype = ctx.typeComparer.glb(
defn.ObjectType :: (parents map (_ baseTypeWithArgs pcls)))
ptype :: parents
}
}
/** Ensure that first parent tree refers to a real class. */
def ensureFirstIsClass(parents: List[Tree], pos: Position)(implicit ctx: Context): List[Tree] = parents match {
case p :: ps if p.tpe.classSymbol.isRealClass => parents
case _ =>
// add synthetic class type
val first :: _ = ensureFirstIsClass(parents.tpes)
TypeTree(checkFeasible(first, pos, i"\n in inferred parent $first")).withPos(pos) :: parents
}
/** 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)(implicit ctx: Context): Unit = {
val constraint = ctx.typerState.constraint
val qualifies = (tvar: TypeVar) => tree contains tvar.owningTree
def interpolate() = Stats.track("interpolateUndetVars") {
val tp = tree.tpe.widen
constr.println(s"interpolate undet vars in ${tp.show}, pos = ${tree.pos}, mode = ${ctx.mode}, undets = ${constraint.uninstVars map (tvar => s"${tvar.show}@${tvar.owningTree.pos}")}")
constr.println(s"qualifying undet vars: ${constraint.uninstVars filter qualifies map (tvar => s"$tvar / ${tvar.show}")}, constraint: ${constraint.show}")
val vs = tp.variances(qualifies)
var changed = false
vs foreachBinding { (tvar, v) =>
if (v != 0) {
typr.println(s"interpolate ${if (v == 1) "co" else "contra"}variant ${tvar.show} in ${tp.show}")
tvar.instantiate(fromBelow = v == 1)
changed = true
}
}
if (changed) // instantiations might have uncovered new typevars to interpolate
interpolateUndetVars(tree)
else
for (tvar <- constraint.uninstVars)
if (!(vs contains tvar) && qualifies(tvar)) {
typr.println(s"instantiating non-occurring ${tvar.show} in ${tp.show}")
tvar.instantiate(fromBelow = true)
}
}
if (constraint.uninstVars exists qualifies) interpolate()
}
/** 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)(implicit ctx: Context): Option[TypeVar] = Stats.track("maximizeType") {
val vs = tp.variances(alwaysTrue)
var result: Option[TypeVar] = None
vs foreachBinding { (tvar, v) =>
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
}
}
/** 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
}
|
