/* NSC -- new Scala compiler
* Copyright 2005-2009 LAMP/EPFL
* @author Martin Odersky
*/
// $Id$
package scala.tools.nsc
package typechecker
import scala.tools.nsc.util.{Position, NoPosition}
import scala.collection.mutable.ListBuffer
import scala.util.control.ControlException
import symtab.Flags._
/** This trait ...
*
* @author Martin Odersky
* @version 1.0
*/
trait Infer {
self: Analyzer =>
import global._
import definitions._
// statistics
var normM = 0
var normP = 0
var normO = 0
private final val inferInfo = false //@MDEBUG
/* -- Type parameter inference utility functions --------------------------- */
private def assertNonCyclic(tvar: TypeVar) =
assert(tvar.constr.inst != tvar, tvar.origin)
def isVarArgs(formals: List[Type]) = !formals.isEmpty && isRepeatedParamType(formals.last)
/** The formal parameter types corresponding to <code>formals</code>.
* If <code>formals</code> has a repeated last parameter, a list of
* (nargs - params.length + 1) copies of its type is returned.
* By-name types are replaced with their underlying type.
*
* @param formals ...
* @param nargs ...
*/
def formalTypes(formals: List[Type], nargs: Int): List[Type] =
formalTypes(formals, nargs, true)
/** This variant allows keeping ByName parameters. Useed in NamesDefaults. */
def formalTypes(formals: List[Type], nargs: Int, removeByName: Boolean): List[Type] = {
val formals1 = if (removeByName) formals map {
case TypeRef(_, sym, List(arg)) if (sym == ByNameParamClass) => arg
case formal => formal
} else formals
if (isVarArgs(formals1)) {
val ft = formals1.last.normalize.typeArgs.head
formals1.init ::: (for (i <- List.range(formals1.length - 1, nargs)) yield ft)
} else formals1
}
def actualTypes(actuals: List[Type], nformals: Int): List[Type] =
if (nformals == 1 && actuals.length != 1)
List(if (actuals.length == 0) UnitClass.tpe else tupleType(actuals))
else actuals
def actualArgs(pos: Position, actuals: List[Tree], nformals: Int): List[Tree] =
if (nformals == 1 && actuals.length != 1 && actuals.length <= definitions.MaxTupleArity && !phase.erasedTypes)
List(atPos(pos)(gen.mkTuple(actuals))) else actuals
/** A fresh type varable with given type parameter as origin.
*
* @param tparam ...
* @return ...
*/
def freshVar(tparam: Symbol): TypeVar = TypeVar(tparam)
//todo: remove comments around following privates; right now they cause an IllegalAccess
// error when built with scalac
/*private*/ class NoInstance(msg: String) extends RuntimeException(msg) with ControlException
/*private*/ class DeferredNoInstance(getmsg: () => String) extends NoInstance("") {
override def getMessage(): String = getmsg()
}
/** map every TypeVar to its constraint.inst field.
* throw a NoInstance exception if a NoType or WildcardType is encountered.
*
* @param tp ...
* @return ...
* @throws NoInstance
*/
object instantiate extends TypeMap {
private var excludedVars = scala.collection.immutable.Set[TypeVar]()
def apply(tp: Type): Type = tp match {
case WildcardType | NoType =>
throw new NoInstance("undetermined type")
case tv @ TypeVar(origin, constr) =>
if (constr.inst == NoType) {
throw new DeferredNoInstance(() =>
"no unique instantiation of type variable " + origin + " could be found")
} else if (excludedVars contains tv) {
throw new NoInstance("cyclic instantiation")
} else {
excludedVars += tv
val res = apply(constr.inst)
excludedVars -= tv
res
}
case _ =>
mapOver(tp)
}
}
/** Is type fully defined, i.e. no embedded anytypes or wildcards in it?
*
* @param tp ...
* @return ...
*/
private[typechecker] def isFullyDefined(tp: Type): Boolean = tp match {
case WildcardType | NoType =>
false
case NoPrefix | ThisType(_) | ConstantType(_) =>
true
case TypeRef(pre, sym, args) =>
isFullyDefined(pre) && (args.isEmpty || (args forall isFullyDefined))
case SingleType(pre, sym) =>
isFullyDefined(pre)
case RefinedType(ts, decls) =>
ts forall isFullyDefined
case TypeVar(origin, constr) if (constr.inst == NoType) =>
false
case _ =>
try {
instantiate(tp); true
} catch {
case ex: NoInstance => false
}
}
/** Solve constraint collected in types <code>tvars</code>.
*
* @param tvars All type variables to be instantiated.
* @param tparams The type parameters corresponding to <code>tvars</code>
* @param variances The variances of type parameters; need to reverse
* solution direction for all contravariant variables.
* @param upper When <code>true</code> search for max solution else min.
* @throws NoInstance
*/
def solvedTypes(tvars: List[TypeVar], tparams: List[Symbol],
variances: List[Int], upper: Boolean, depth: Int): List[Type] = {
// def boundsString(tvar: TypeVar) =
// "\n "+
// ((tvar.constr.loBounds map (_ + " <: " + tvar.origin.typeSymbol.name)) :::
// (tvar.constr.hiBounds map (tvar.origin.typeSymbol.name + " <: " + _)) mkString ", ")
if (!solve(tvars, tparams, variances, upper, depth)) {
// no panic, it's good enough to just guess a solution, we'll find out
// later whether it works.
// throw new DeferredNoInstance(() =>
// "no solution exists for constraints"+(tvars map boundsString))
}
for (tvar <- tvars)
if (tvar.constr.inst == tvar)
if (tvar.origin.typeSymbol.info eq ErrorType) {
// this can happen if during solving a cyclic type paramater
// such as T <: T gets completed. See #360
tvar.constr.inst = ErrorType
} else assert(false, tvar.origin+" at "+tvar.origin.typeSymbol.owner)
tvars map instantiate
}
def skipImplicit(tp: Type) =
if (tp.isInstanceOf[ImplicitMethodType]) tp.resultType else tp
/** Automatically perform the following conversions on expression types:
* A method type becomes the corresponding function type.
* A nullary method type becomes its result type.
* Implicit parameters are skipped.
*/
def normalize(tp: Type): Type = skipImplicit(tp) match {
case MethodType(params, restpe) if (!restpe.isDependent) =>
if (util.Statistics.enabled) normM += 1
functionType(params map (_.tpe), normalize(restpe))
case PolyType(List(), restpe) =>
if (util.Statistics.enabled) normP += 1
normalize(restpe)
case ExistentialType(tparams, qtpe) =>
ExistentialType(tparams, normalize(qtpe))
case tp1 =>
if (util.Statistics.enabled) normO += 1
tp1 // @MAT aliases already handled by subtyping
}
private val stdErrorClass = RootClass.newErrorClass(nme.ERROR.toTypeName)
private val stdErrorValue = stdErrorClass.newErrorValue(nme.ERROR)
/** The context-dependent inferencer part */
class Inferencer(context: Context) {
/* -- Error Messages --------------------------------------------------- */
private var addendumPos: Position = NoPosition
private var addendum: () => String = _
def setAddendum(pos: Position, msg: () => String) = {
addendumPos = pos
addendum = msg
}
def setError[T <: Tree](tree: T): T = {
if (tree.hasSymbol)
if (context.reportGeneralErrors) {
val name = newTermName("<error: " + tree.symbol + ">")
tree.setSymbol(
if (tree.isType) context.owner.newErrorClass(name.toTypeName)
else context.owner.newErrorValue(name))
} else {
tree.setSymbol(if (tree.isType) stdErrorClass else stdErrorValue)
}
tree.setType(ErrorType)
}
def decode(name: Name): String =
(if (name.isTypeName) "type " else "value ") + name.decode
def treeSymTypeMsg(tree: Tree): String =
if (tree.symbol eq null)
"expression of type " + tree.tpe
else if (tree.symbol.hasFlag(OVERLOADED))
"overloaded method " + tree.symbol + " with alternatives " + tree.tpe
else
tree.symbol.toString() +
(if (tree.symbol.isModule) ""
else if (tree.tpe.paramSectionCount > 0) ": "+tree.tpe
else " of type "+tree.tpe) +
(if (tree.symbol.name == nme.apply) tree.symbol.locationString else "")
def applyErrorMsg(tree: Tree, msg: String, argtpes: List[Type], pt: Type) =
treeSymTypeMsg(tree) + msg + argtpes.mkString("(", ",", ")") +
(if (pt == WildcardType) "" else " with expected result type " + pt)
// todo: use also for other error messages
private def existentialContext(tp: Type) = tp.existentialSkolems match {
case List() => ""
case skolems =>
def disambiguate(ss: List[String]) = ss match {
case List() => ss
case s :: ss1 => s :: (ss1 map (s1 => if (s1 == s) "(some other)"+s1 else s1))
}
" where "+(disambiguate(skolems map (_.existentialToString)) mkString ", ")
}
def foundReqMsg(found: Type, req: Type): String =
withDisambiguation(found, req) {
";\n found : " + found.toLongString + existentialContext(found) +
"\n required: " + req + existentialContext(req)
}
def typeErrorMsg(found: Type, req: Type) = {
//println(found.baseTypeSeq)
"type mismatch" + foundReqMsg(found, req) +
(if ((found.resultApprox ne found) && isWeaklyCompatible(found.resultApprox, req))
"\n possible cause: missing arguments for method or constructor"
else "")
}
def error(pos: Position, msg: String) {
context.error(pos, msg)
}
def errorTree(tree: Tree, msg: String): Tree = {
if (!tree.isErroneous) error(tree.pos, msg)
setError(tree)
}
def typeError(pos: Position, found: Type, req: Type) {
if (!found.isErroneous && !req.isErroneous) {
error(pos,
typeErrorMsg(found, req)+
(if (pos != NoPosition && pos == addendumPos) addendum()
else ""))
if (settings.explaintypes.value) explainTypes(found, req)
}
}
def typeErrorTree(tree: Tree, found: Type, req: Type): Tree = {
typeError(tree.pos, found, req)
setError(tree)
}
def explainTypes(tp1: Type, tp2: Type) =
withDisambiguation(tp1, tp2) { global.explainTypes(tp1, tp2) }
/** If types `tp1' `tp2' contain different type variables with same name
* differentiate the names by including owner information. Also, if the
* type error is because of a conflict between two identically named
* classes and one is in package scala, fully qualify the name so one
* need not deduce why "java.util.Iterator" and "Iterator" don't match.
*/
private def withDisambiguation[T](tp1: Type, tp2: Type)(op: => T): T = {
def explainName(sym: Symbol) = {
if (!sym.name.toString.endsWith(")")) {
sym.name = newTypeName(sym.name.toString+"(in "+sym.owner+")")
}
}
val patches = new ListBuffer[(Symbol, Symbol, Name)]
for {
t1 @ TypeRef(_, sym1, _) <- tp1
t2 @ TypeRef(_, sym2, _) <- tp2
if sym1 != sym2
} {
if (t1.toString == t2.toString) { // type variable collisions
val name = sym1.name
explainName(sym1)
explainName(sym2)
if (sym1.owner == sym2.owner) sym2.name = newTypeName("(some other)"+sym2.name)
patches += ((sym1, sym2, name))
}
else if (sym1.name == sym2.name) { // symbol name collisions where one is in scala._
val name = sym1.name
def scalaQualify(s: Symbol) =
if (s.owner.isScalaPackageClass) s.name = newTypeName("scala." + s.name)
List(sym1, sym2) foreach scalaQualify
patches += ((sym1, sym2, name))
}
}
val result = op
for ((sym1, sym2, name) <- patches) {
sym1.name = name
sym2.name = name
}
result
}
/* -- Tests & Checks---------------------------------------------------- */
/** Check that <code>sym</code> is defined and accessible as a member of
* tree <code>site</code> with type <code>pre</code> in current context.
*/
def checkAccessible(tree: Tree, sym: Symbol, pre: Type, site: Tree): Tree =
if (sym.isError) {
tree setSymbol sym setType ErrorType
} else {
def accessError(explanation: String): Tree =
errorTree(tree, underlying(sym).toString() + " cannot be accessed in " +
(if (sym.isClassConstructor) context.enclClass.owner else pre.widen) +
explanation)
val topClass = context.owner.toplevelClass
if (context.unit != null)
context.unit.depends += sym.toplevelClass
val sym1 = sym filter (alt => context.isAccessible(alt, pre, site.isInstanceOf[Super]))
if (sym1 == NoSymbol) {
if (settings.debug.value) {
Console.println(context)
Console.println(tree)
Console.println("" + pre + " " + sym.owner + " " + context.owner + " " + context.outer.enclClass.owner + " " + sym.owner.thisType + (pre =:= sym.owner.thisType))
}
accessError("")
} else {
// Modify symbol's type so that raw types C
// are converted to existentials C[T] forSome { type T }.
// We can't do this on class loading because it would result
// in infinite cycles.
def cook(sym: Symbol) {
val tpe1 = rawToExistential(sym.tpe)
if (tpe1 ne sym.tpe) {
if (settings.debug.value) println("cooked: "+sym+":"+sym.tpe)
sym.setInfo(tpe1)
}
}
if (sym1.isTerm) {
if (sym1 hasFlag JAVA)
cook(sym1)
else if (sym1 hasFlag OVERLOADED)
for (sym2 <- sym1.alternatives)
if (sym2 hasFlag JAVA)
cook(sym2)
}
//Console.println("check acc " + sym1 + ":" + sym1.tpe + " from " + pre);//DEBUG
var owntype = try{
pre.memberType(sym1)
} catch {
case ex: MalformedType =>
if (settings.debug.value) ex.printStackTrace
val sym2 = underlying(sym1)
val itype = pre.memberType(sym2)
accessError("\n because its instance type "+itype+
(if ("malformed type: "+itype.toString==ex.msg) " is malformed"
else " contains a "+ex.msg))
ErrorType
}
if (pre.isInstanceOf[SuperType])
owntype = owntype.substSuper(pre, site.symbol.thisType)
tree setSymbol sym1 setType owntype
}
}
def isPlausiblyPopulated(tp1: Type, tp2: Type): Boolean = true
def isPlausiblyCompatible(tp: Type, pt: Type): Boolean = tp match {
case PolyType(_, restpe) =>
isPlausiblyCompatible(restpe, pt)
case mt: ImplicitMethodType =>
isPlausiblyCompatible(mt.resultType, pt)
case ExistentialType(tparams, qtpe) =>
isPlausiblyCompatible(qtpe, pt)
case MethodType(params, _) =>
val formals = tp.paramTypes
pt.normalize match {
case TypeRef(pre, sym, args) =>
!sym.isClass || {
val l = args.length - 1
l == formals.length &&
sym == FunctionClass(l) &&
List.forall2(args, formals) (isPlausiblySubType) &&
isPlausiblySubType(tp.resultApprox, args.last)
}
case _ =>
true
}
case _ =>
true
}
private def isPlausiblySubType(tp1: Type, tp2: Type): Boolean = tp1.normalize match {
case TypeRef(_, sym1, _) =>
!sym1.isClass || {
tp2.normalize match {
case TypeRef(_, sym2, _) => !sym2.isClass || (sym1 isSubClass sym2)
case _ => true
}
}
case _ =>
true
}
def isCompatible(tp: Type, pt: Type): Boolean = {
val tp1 = normalize(tp)
(tp1 <:< pt) || isCoercible(tp1, pt)
}
def isCompatibleArg(tp: Type, pt: Type): Boolean = {
val tp1 = normalize(tp)
(tp1 weak_<:< pt) || isCoercible(tp1, pt)
}
def isWeaklyCompatible(tp: Type, pt: Type): Boolean =
pt.typeSymbol == UnitClass || // can perform unit coercion
isCompatible(tp, pt) ||
tp.isInstanceOf[MethodType] && // can perform implicit () instantiation
tp.paramTypes.length == 0 && isCompatible(tp.resultType, pt)
/** Like weakly compatible but don't apply any implicit conversions yet.
* Used when comparing the result type of a method with its prototype.
*/
def isConservativelyCompatible(tp: Type, pt: Type): Boolean = {
val savedImplicitsEnabled = context.implicitsEnabled
context.implicitsEnabled = false
try {
isWeaklyCompatible(tp, pt)
} finally {
context.implicitsEnabled = savedImplicitsEnabled
}
}
def isCoercible(tp: Type, pt: Type): Boolean = false
def isCompatibleArgs(tps: List[Type], pts: List[Type]): Boolean =
List.map2(tps, pts)((tp, pt) => isCompatibleArg(tp, pt)) forall (x => x)
/* -- Type instantiation------------------------------------------------ */
/** Replace any (possibly bounded) wildcard types in type `tp`
* by existentially bound variables.
*/
def makeFullyDefined(tp: Type): Type = {
val tparams = new ListBuffer[Symbol]
def addTypeParam(bounds: TypeBounds): Type = {
val tparam =
context.owner.newAbstractType(context.tree.pos.focus, newTypeName("_"+tparams.size))
.setFlag(EXISTENTIAL)
.setInfo(bounds)
tparams += tparam
tparam.tpe
}
val tp1 = tp map {
case WildcardType =>
addTypeParam(TypeBounds(NothingClass.tpe, AnyClass.tpe))
case BoundedWildcardType(bounds) =>
addTypeParam(bounds)
case t => t
}
existentialAbstraction(tparams.toList, tp1)
}
/** Return inferred type arguments of polymorphic expression, given
* its type parameters and result type and a prototype <code>pt</code>.
* If no minimal type variables exist that make the
* instantiated type a subtype of <code>pt</code>, return null.
*
* @param tparams ...
* @param restpe ...
* @param pt ...
* @return ...
*/
private def exprTypeArgs(tparams: List[Symbol], restpe: Type, pt: Type): List[Type] = {
val tvars = tparams map freshVar
if (isCompatible(restpe.instantiateTypeParams(tparams, tvars), pt)) {
try {
// If the restpe is an implicit method, and the expected type is fully defined
// optimze type varianbles wrt to the implicit formals only; ignore the result type.
// See test pos/jesper.scala
val varianceType = restpe match {
case mt: ImplicitMethodType if isFullyDefined(pt) =>
MethodType(mt.params, AnyClass.tpe)
case _ =>
restpe
}
//println("try to solve "+tvars+" "+tparams)
solvedTypes(tvars, tparams, tparams map varianceInType(varianceType),
false, lubDepth(List(restpe, pt)))
} catch {
case ex: NoInstance => null
}
} else null
}
/** Return inferred proto-type arguments of function, given
* its type and value parameters and result type, and a
* prototype <code>pt</code> for the function result.
* Type arguments need to be either determined precisely by
* the prototype, or they are maximized, if they occur only covariantly
* in the value parameter list.
* If instantiation of a type parameter fails,
* take WildcardType for the proto-type argument.
*
* @param tparams ...
* @param formals ...
* @param restype ...
* @param pt ...
* @return ...
*/
def protoTypeArgs(tparams: List[Symbol], formals: List[Type], restpe: Type,
pt: Type): List[Type] = {
/** Map type variable to its instance, or, if `variance' is covariant/contravariant,
* to its upper/lower bound */
def instantiateToBound(tvar: TypeVar, variance: Int): Type = try {
lazy val hiBounds = tvar.constr.hiBounds
lazy val loBounds = tvar.constr.loBounds
lazy val upper = glb(hiBounds)
lazy val lower = lub(loBounds)
def setInst(tp: Type): Type = {
tvar setInst tp
assertNonCyclic(tvar)//debug
instantiate(tvar.constr.inst)
}
//Console.println("instantiate "+tvar+tvar.constr+" variance = "+variance);//DEBUG
if (tvar.constr.inst != NoType)
instantiate(tvar.constr.inst)
else if ((variance & COVARIANT) != 0 && hiBounds.nonEmpty)
setInst(upper)
else if ((variance & CONTRAVARIANT) != 0 && loBounds.nonEmpty)
setInst(lower)
else if (hiBounds.nonEmpty && loBounds.nonEmpty && upper <:< lower)
setInst(upper)
else
WildcardType
} catch {
case ex: NoInstance => WildcardType
}
val tvars = tparams map freshVar
if (isConservativelyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt))
List.map2(tparams, tvars) ((tparam, tvar) =>
instantiateToBound(tvar, varianceInTypes(formals)(tparam)))
else
tvars map (tvar => WildcardType)
}
/** Retract any Nothing arguments which appear covariantly in result type,
* and treat them as uninstantiated parameters instead.
* Map T* entries to Seq[T].
*/
def adjustTypeArgs(tparams: List[Symbol], targs: List[Type], restpe: Type, uninstantiated: ListBuffer[Symbol]): List[Type] =
List.map2(tparams, targs) {(tparam, targ) =>
if (targ.typeSymbol == NothingClass && (restpe == WildcardType || (varianceInType(restpe)(tparam) & COVARIANT) == 0)) {
uninstantiated += tparam
tparam.tpeHK //@M tparam.tpe was wrong: we only want the type constructor,
// not the type constructor applied to dummy arguments
// see ticket 474 for an example that crashes if we use .tpe instead of .tpeHK)
} else if (targ.typeSymbol == RepeatedParamClass) {
targ.baseType(SeqClass)
} else if (targ.typeSymbol == JavaRepeatedParamClass) {
targ.baseType(ArrayClass)
} else {
targ.widen
}
}
/** Return inferred type arguments, given type parameters, formal parameters,
* argument types, result type and expected result type.
* If this is not possible, throw a <code>NoInstance</code> exception.
* Undetermined type arguments are represented by `definitions.NothingClass.tpe'.
* No check that inferred parameters conform to their bounds is made here.
*
* bq: was private, but need it for unapply checking
*
* @param tparams the type parameters of the method
* @param formals the value parameter types of the method
* @param restp the result type of the method
* @param argtpes the argument types of the application
* @param pt the expected return type of the application
* @param uninstantiated a listbuffer receiving all uninstantiated type parameters
* (type parameters mapped by the constraint solver to `scala.All'
* and not covariant in <code>restpe</code> are taken to be
* uninstantiated. Maps all those type arguments to their
* corresponding type parameters).
* @return ...
* @throws NoInstance
*/
def methTypeArgs(tparams: List[Symbol], formals: List[Type], restpe: Type,
argtpes: List[Type], pt: Type,
uninstantiated: ListBuffer[Symbol]): List[Type] = {
val tvars = tparams map freshVar
if (inferInfo)
println("methTypeArgs tparams = "+tparams+
", formals = "+formals+
", restpe = "+restpe+
", argtpes = "+argtpes+
", pt = "+pt+
", uninstantiated = "+uninstantiated+
", tvars = "+tvars+" "+(tvars map (_.constr)))
if (formals.length != argtpes.length) {
throw new NoInstance("parameter lists differ in length")
}
if (inferInfo) // @MDEBUG
println("methTypeArgs "+
" tparams = "+tparams+"\n"+
" formals = "+formals+"\n"+
" restpe = "+restpe+"\n"+
" restpe_inst = "+restpe.instantiateTypeParams(tparams, tvars)+"\n"+
" argtpes = "+argtpes+"\n"+
" pt = "+pt)
// check first whether type variables can be fully defined from
// expected result type.
if (!isConservativelyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt)) {
// just wait and instantiate from the arguments.
// that way, we can try to apply an implicit conversion afterwards.
// This case could happen if restpe is not fully defined, so that
// search for an implicit from it to pt fails because of an ambiguity.
// See #0347. Therefore, the following two lines are commented out.
// throw new DeferredNoInstance(() =>
// "result type " + normalize(restpe) + " is incompatible with expected type " + pt)
}
for (tvar <- tvars)
if (!isFullyDefined(tvar)) tvar.constr.inst = NoType
// Then define remaining type variables from argument types.
List.map2(argtpes, formals) {(argtpe, formal) =>
//@M isCompatible has side-effect: isSubtype0 will register subtype checks in the tvar's bounds
if (!isCompatibleArg(argtpe.deconst.instantiateTypeParams(tparams, tvars),
formal.instantiateTypeParams(tparams, tvars))) {
throw new DeferredNoInstance(() =>
"argument expression's type is not compatible with formal parameter type" +
foundReqMsg(argtpe.deconst.instantiateTypeParams(tparams, tvars), formal.instantiateTypeParams(tparams, tvars)))
}
()
}
if (inferInfo)
println("solve "+tvars+" "+(tvars map (_.constr)))
val targs = solvedTypes(tvars, tparams, tparams map varianceInTypes(formals),
false, lubDepth(formals) max lubDepth(argtpes))
// val res =
adjustTypeArgs(tparams, targs, restpe, uninstantiated)
// println("meth type args "+", tparams = "+tparams+", formals = "+formals+", restpe = "+restpe+", argtpes = "+argtpes+", underlying = "+(argtpes map (_.widen))+", pt = "+pt+", uninstantiated = "+uninstantiated.toList+", result = "+res) //DEBUG
// res
}
private[typechecker] def followApply(tp: Type): Type = tp match {
case PolyType(List(), restp) =>
val restp1 = followApply(restp)
if (restp1 eq restp) tp else restp1
case _ =>
val appmeth = tp.nonPrivateMember(nme.apply) filter (_.isPublic)
if (appmeth == NoSymbol) tp
else OverloadedType(tp, appmeth.alternatives)
}
def hasExactlyNumParams(tp: Type, n: Int): Boolean = tp match {
case OverloadedType(pre, alts) =>
alts exists (alt => hasExactlyNumParams(pre.memberType(alt), n))
case _ =>
formalTypes(tp.paramTypes, n).length == n
}
/**
* Verifies whether the named application is valid. The logic is very
* similar to the one in NamesDefaults.removeNames.
*
* @return a triple (argtpes1, argPos, namesOk) where
* - argtpes1 the argument types in named application (assignments to
* non-parameter names are treated as assignments, i.e. type Unit)
* - argPos a Function1[Int, Int] mapping arguments from their current
* to the corresponding position in params
* - namesOK is false when there's an invalid use of named arguments
*/
private def checkNames(argtpes: List[Type], params: List[Symbol]) = {
val argPos = (new Array[Int](argtpes.length)) map (x => -1)
var positionalAllowed = true
var namesOK = true
var index = 0
val argtpes1 = argtpes map {
case NamedType(name, tp) => // a named argument
var res = tp
val pos = params.indexWhere(p => p.name == name && !p.hasFlag(SYNTHETIC))
if (pos == -1) {
if (positionalAllowed) { // treat assignment as positional argument
argPos(index) = index
res = UnitClass.tpe
} else // unknown parameter name
namesOK = false
} else if (argPos.contains(pos)) { // parameter specified twice
namesOK = false
} else {
positionalAllowed = false
argPos(index) = pos
}
index += 1
res
case tp => // a positional argument
argPos(index) = index
if (!positionalAllowed)
namesOK = false // positional after named
index += 1
tp
}
(argtpes1, argPos, namesOK)
}
/** Is there an instantiation of free type variables <code>undetparams</code>
* such that function type <code>ftpe</code> is applicable to
* <code>argtpes</code> and its result conform to <code>pt</code>?
*
* @param undetparams ...
* @param ftpe the type of the function (often a MethodType)
* @param argtpes the argument types; a NamedType(name, tp) for named
* arguments. For each NamedType, if `name' does not exist in `ftpe', that
* type is set to `Unit', i.e. the corresponding argument is treated as
* an assignment expression (@see checkNames).
* @param pt ...
* @return ...
*/
private def isApplicable(undetparams: List[Symbol], ftpe: Type,
argtpes0: List[Type], pt: Type): Boolean =
ftpe match {
case OverloadedType(pre, alts) =>
alts exists (alt => isApplicable(undetparams, pre.memberType(alt), argtpes0, pt))
case ExistentialType(tparams, qtpe) =>
isApplicable(undetparams, qtpe, argtpes0, pt)
case MethodType(params, _) =>
def paramType(param: Symbol) = param.tpe match {
case TypeRef(_, sym, List(tpe)) if sym isNonBottomSubClass CodeClass =>
tpe
case tpe =>
tpe
}
val formals = formalTypes(params map paramType, argtpes0.length)
def tryTupleApply: Boolean = {
// if 1 formal, 1 argtpe (a tuple), otherwise unmodified argtpes0
val tupleArgTpe = actualTypes(argtpes0 map {
// no assignment is treated as named argument here
case NamedType(name, tp) => UnitClass.tpe
case tp => tp
}, formals.length)
argtpes0.length != tupleArgTpe.length &&
isApplicable(undetparams, ftpe, tupleArgTpe, pt)
}
def typesCompatible(argtpes: List[Type]) = {
val restpe = ftpe.resultType(argtpes)
if (undetparams.isEmpty) {
isCompatibleArgs(argtpes, formals) && isWeaklyCompatible(restpe, pt)
} else {
try {
val uninstantiated = new ListBuffer[Symbol]
val targs = methTypeArgs(undetparams, formals, restpe, argtpes, pt, uninstantiated)
(exprTypeArgs(uninstantiated.toList, restpe.instantiateTypeParams(undetparams, targs), pt) ne null) &&
isWithinBounds(NoPrefix, NoSymbol, undetparams, targs)
} catch {
case ex: NoInstance => false
}
}
}
// very similar logic to doTypedApply in typechecker
if (argtpes0.length > formals.length) tryTupleApply
else if (argtpes0.length == formals.length) {
if (!argtpes0.exists(_.isInstanceOf[NamedType])) {
// fast track if no named arguments are used
typesCompatible(argtpes0)
} else {
// named arguments are used
val (argtpes1, argPos, namesOK) = checkNames(argtpes0, params)
if (!namesOK) false
// when using named application, the vararg param has to be specified exactly once
else if (!isIdentity(argPos) && (formals.length != params.length)) false
else {
// nb. arguments and names are OK, check if types are compatible
typesCompatible(reorderArgs(argtpes1, argPos))
}
}
} else {
// not enough arguments, check if applicable using defaults
val missing = missingParams[Type](argtpes0, params, {
case NamedType(name, _) => Some(name)
case _ => None
})._1
if (missing.exists(!_.hasFlag(DEFAULTPARAM))) tryTupleApply
else {
val argtpes1 = argtpes0 ::: missing.map {
p => NamedType(p.name, p.tpe) // add defaults as named arguments
}
isApplicable(undetparams, ftpe, argtpes1, pt)
}
}
case PolyType(tparams, restpe) =>
val tparams1 = cloneSymbols(tparams)
isApplicable(tparams1 ::: undetparams, restpe.substSym(tparams, tparams1), argtpes0, pt)
case ErrorType =>
true
case _ =>
false
}
private[typechecker] def isApplicableSafe(undetparams: List[Symbol], ftpe: Type,
argtpes0: List[Type], pt: Type): Boolean = {
val reportAmbiguousErrors = context.reportAmbiguousErrors
context.reportAmbiguousErrors = false
try {
isApplicable(undetparams, ftpe, argtpes0, pt)
} catch {
case ex: TypeError =>
false
} finally {
context.reportAmbiguousErrors = reportAmbiguousErrors
}
}
/** Is type <code>ftpe1</code> strictly more specific than type <code>ftpe2</code>
* when both are alternatives in an overloaded function?
* @see SLS (sec:overloading-resolution)
*
* @param ftpe1 ...
* @param ftpe2 ...
* @return ...
*/
def isAsSpecific(ftpe1: Type, ftpe2: Type): Boolean = ftpe1 match {
case OverloadedType(pre, alts) =>
alts exists (alt => isAsSpecific(pre.memberType(alt), ftpe2))
case et: ExistentialType =>
et.withTypeVars(isAsSpecific(_, ftpe2))
case mt: ImplicitMethodType =>
isAsSpecific(ftpe1.resultType, ftpe2)
case MethodType(params @ (x :: xs), _) =>
var argtpes = params map (_.tpe)
if (isVarArgs(argtpes) && isVarArgs(ftpe2.paramTypes))
argtpes = argtpes map (argtpe =>
if (isRepeatedParamType(argtpe)) argtpe.typeArgs.head else argtpe)
isApplicable(List(), ftpe2, argtpes, WildcardType)
case PolyType(tparams, mt: ImplicitMethodType) =>
isAsSpecific(PolyType(tparams, mt.resultType), ftpe2)
case PolyType(_, MethodType(params @ (x :: xs), _)) =>
isApplicable(List(), ftpe2, params map (_.tpe), WildcardType)
case ErrorType =>
true
case _ =>
ftpe2 match {
case OverloadedType(pre, alts) =>
alts forall (alt => isAsSpecific(ftpe1, pre.memberType(alt)))
case et: ExistentialType =>
et.withTypeVars(isAsSpecific(ftpe1, _))
case mt: ImplicitMethodType =>
isAsSpecific(ftpe1, mt.resultType)
case PolyType(tparams, mt: ImplicitMethodType) =>
isAsSpecific(ftpe1, PolyType(tparams, mt.resultType))
case MethodType(_, _) | PolyType(_, MethodType(_, _)) =>
true
case _ =>
isAsSpecificValueType(ftpe1, ftpe2, List(), List())
}
}
/*
def isStrictlyMoreSpecific(ftpe1: Type, ftpe2: Type): Boolean =
ftpe1.isError || isAsSpecific(ftpe1, ftpe2) &&
(!isAsSpecific(ftpe2, ftpe1) ||
!ftpe1.isInstanceOf[OverloadedType] && ftpe2.isInstanceOf[OverloadedType] ||
phase.erasedTypes && covariantReturnOverride(ftpe1, ftpe2))
*/
/** Is sym1 (or its companion class in case it is a module) a subclass of
* sym2 (or its companion class in case it is a module)?
*/
def isProperSubClassOrObject(sym1: Symbol, sym2: Symbol): Boolean =
sym1 != sym2 && sym1 != NoSymbol && (sym1 isSubClass sym2) ||
sym1.isModuleClass && isProperSubClassOrObject(sym1.linkedClassOfClass, sym2) ||
sym2.isModuleClass && isProperSubClassOrObject(sym1, sym2.linkedClassOfClass)
/** is symbol `sym1` defined in a proper subclass of symbol `sym2`?
*/
def isInProperSubClassOrObject(sym1: Symbol, sym2: Symbol) =
sym2 == NoSymbol || isProperSubClassOrObject(sym1.owner, sym2.owner)
def isStrictlyMoreSpecific(ftpe1: Type, ftpe2: Type, sym1: Symbol, sym2: Symbol): Boolean = {
// ftpe1 / ftpe2 are OverloadedTypes (possibly with one single alternative) if they
// denote the type of an "apply" member method (see "followApply")
ftpe1.isError || {
val specificCount = (if (isAsSpecific(ftpe1, ftpe2)) 1 else 0) -
(if (isAsSpecific(ftpe2, ftpe1) &&
// todo: move to isAsSepecific test
(!ftpe2.isInstanceOf[OverloadedType] || ftpe1.isInstanceOf[OverloadedType]) &&
(!phase.erasedTypes || covariantReturnOverride(ftpe1, ftpe2))) 1 else 0)
val subClassCount = (if (isInProperSubClassOrObject(sym1, sym2)) 1 else 0) -
(if (isInProperSubClassOrObject(sym2, sym1)) 1 else 0)
//println("is more specific? "+sym1+sym1.locationString+"/"+sym2+sym2.locationString+":"+
// specificCount+"/"+subClassCount)
specificCount + subClassCount > 0
}
}
/*
ftpe1.isError || {
if (isAsSpecific(ftpe1, ftpe2))
(!isAsSpecific(ftpe2, ftpe1) ||
isProperSubClassOrObject(sym1.owner, sym2.owner) ||
!ftpe1.isInstanceOf[OverloadedType] && ftpe2.isInstanceOf[OverloadedType] ||
phase.erasedTypes && covariantReturnOverride(ftpe1, ftpe2))
else
!isAsSpecific(ftpe2, ftpe1) &&
isProperSubClassOrObject(sym1.owner, sym2.owner)
}
*/
private def covariantReturnOverride(ftpe1: Type, ftpe2: Type): Boolean = (ftpe1, ftpe2) match {
case (MethodType(_, rtpe1), MethodType(_, rtpe2)) =>
rtpe1 <:< rtpe2 || rtpe2.typeSymbol == ObjectClass
case _ =>
false
}
private def isAsSpecificValueType(tpe1: Type, tpe2: Type, undef1: List[Symbol], undef2: List[Symbol]): Boolean = (tpe1, tpe2) match {
case (PolyType(tparams1, rtpe1), _) =>
isAsSpecificValueType(rtpe1, tpe2, undef1 ::: tparams1, undef2)
case (_, PolyType(tparams2, rtpe2)) =>
isAsSpecificValueType(tpe1, rtpe2, undef1, undef2 ::: tparams2)
case _ =>
existentialAbstraction(undef1, tpe1) <:< existentialAbstraction(undef2, tpe2)
}
/*
/** Is type `tpe1' a strictly better expression alternative than type `tpe2'?
*/
def isStrictlyBetterExpr(tpe1: Type, tpe2: Type) = {
isMethod(tpe2) && !isMethod(tpe1) ||
isNullary(tpe1) && !isNullary(tpe2) ||
isStrictlyBetter(tpe1, tpe2)
}
/** Is type `tpe1' a strictly better alternative than type `tpe2'?
* non-methods are always strictly better than methods
* nullary methods are always strictly better than non-nullary
* if both are non-nullary methods, then tpe1 is strictly better than tpe2 if
* - tpe1 specializes tpe2 and tpe2 does not specialize tpe1
* - tpe1 and tpe2 specialize each other and tpe1 has a strictly better resulttype than
* tpe2
*/
def isStrictlyBetter(tpe1: Type, tpe2: Type) = {
def isNullary(tpe: Type): Boolean = tpe match {
case tp: RewrappingTypeProxy => isNullary(tp.underlying)
case _ => tpe.paramSectionCount == 0 || tpe.paramTypes.isEmpty
}
def isMethod(tpe: Type): Boolean = tpe match {
case tp: RewrappingTypeProxy => isMethod(tp.underlying)
case MethodType(_, _) | PolyType(_, _) => true
case _ => false
}
def hasStrictlyBetterResult =
resultIsBetter(tpe1, tpe2, List(), List()) && !resultIsBetter(tpe2, tpe1, List(), List())
if (!isMethod(tpe1))
isMethod(tpe2) || hasStrictlyBetterResult
isNullary(tpe1) && !isNullary(tpe2) ||
is
else if (isNullary(tpe1))
isMethod(tpe2) && (!isNullary(tpe2) || hasStrictlyBetterResult)
else
specializes(tpe1, tpe2) && (!specializes(tpe2, tpe1) || hasStrictlyBetterResult)
}
*/
/** error if arguments not within bounds. */
def checkBounds(pos: Position, pre: Type, owner: Symbol,
tparams: List[Symbol], targs: List[Type], prefix: String) = {
//@M validate variances & bounds of targs wrt variances & bounds of tparams
//@M TODO: better place to check this?
//@M TODO: errors for getters & setters are reported separately
val kindErrors = checkKindBounds(tparams, targs, pre, owner)
if(!kindErrors.isEmpty) {
error(pos,
prefix + "kinds of the type arguments " + targs.mkString("(", ",", ")") +
" do not conform to the expected kinds of the type parameters "+ tparams.mkString("(", ",", ")") + tparams.head.locationString+ "." +
kindErrors.toList.mkString("\n", ", ", ""))
} else if (!isWithinBounds(pre, owner, tparams, targs)) {
if (!(targs exists (_.isErroneous)) && !(tparams exists (_.isErroneous))) {
//val bounds = instantiatedBounds(pre, owner, tparams, targs)//DEBUG
//println("bounds = "+bounds+", targs = "+targs+", targclasses = "+(targs map (_.getClass))+", parents = "+(targs map (_.parents)))
//println(List.map2(bounds, targs)((bound, targ) => bound containsType targ))
error(pos,
prefix + "type arguments " + targs.mkString("[", ",", "]") +
" do not conform to " + tparams.head.owner + "'s type parameter bounds " +
(tparams map (_.defString)).mkString("[", ",", "]"))
if (settings.explaintypes.value) {
val bounds = tparams map (tp => tp.info.instantiateTypeParams(tparams, targs).bounds)
List.map2(targs, bounds)((targ, bound) => explainTypes(bound.lo, targ))
List.map2(targs, bounds)((targ, bound) => explainTypes(targ, bound.hi))
()
}
}
}
}
/** Check whether <arg>sym1</arg>'s variance conforms to <arg>sym2</arg>'s variance
*
* If <arg>sym2</arg> is invariant, <arg>sym1</arg>'s variance is irrelevant. Otherwise they must be equal.
*/
def variancesMatch(sym1: Symbol, sym2: Symbol): Boolean = (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 checkKindBounds(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): List[String] = {
def transform(tp: Type, clazz: Symbol): Type = tp.asSeenFrom(pre, clazz) // instantiate type params that come from outside the abstract type we're currently checking
// check that the type parameters <arg>hkargs</arg> to a higher-kinded type conform to the expected params <arg>hkparams</arg>
def checkKindBoundsHK(hkargs: List[Symbol], arg: Symbol, param: Symbol, paramowner: Symbol): (List[(Symbol, Symbol)], List[(Symbol, Symbol)], List[(Symbol, Symbol)]) = {
// @M sometimes hkargs != arg.typeParams, the symbol and the type may have very different type parameters
val hkparams = param.typeParams
if(hkargs.length != hkparams.length) {
if(arg == AnyClass || arg == NothingClass) (Nil, Nil, Nil) // Any and Nothing are kind-overloaded
else (List((arg, param)), Nil, Nil)
} else {
val _arityMismatches = new ListBuffer[(Symbol, Symbol)]
val _varianceMismatches = new ListBuffer[(Symbol, Symbol)]
val _stricterBounds = new ListBuffer[(Symbol, Symbol)]
def varianceMismatch(a: Symbol, p: Symbol) { _varianceMismatches += ((a, p)) }
def stricterBound(a: Symbol, p: Symbol) { _stricterBounds += ((a, p)) }
def arityMismatches(as: Iterable[(Symbol, Symbol)]) { _arityMismatches ++= as }
def varianceMismatches(as: Iterable[(Symbol, Symbol)]) { _varianceMismatches ++= as }
def stricterBounds(as: Iterable[(Symbol, Symbol)]) { _stricterBounds ++= as }
for ((hkarg, hkparam) <- hkargs zip hkparams) {
if (hkparam.typeParams.isEmpty) { // base-case: kind *
if (!variancesMatch(hkarg, hkparam))
varianceMismatch(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)
if (!(transform(hkparam.info.instantiateTypeParams(tparams, targs).bounds.substSym(hkparams, hkargs), paramowner) <:< transform(hkarg.info.bounds, owner)))
stricterBound(hkarg, hkparam)
} else {
val (am, vm, sb) = checkKindBoundsHK(hkarg.typeParams, hkarg, hkparam, paramowner)
arityMismatches(am)
varianceMismatches(vm)
stricterBounds(sb)
}
}
(_arityMismatches.toList, _varianceMismatches.toList, _stricterBounds.toList)
}
}
// @M TODO this method is duplicated all over the place (varianceString)
def varStr(s: Symbol): String =
if (s.isCovariant) "covariant"
else if (s.isContravariant) "contravariant"
else "invariant";
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 ""
}
}
val errors = new ListBuffer[String]
(tparams zip targs).foreach{ case (tparam, targ) if (targ.isHigherKinded || !tparam.typeParams.isEmpty) =>
// @M must use the typeParams of the type targ, not the typeParams of the symbol of targ!!
val tparamsHO = targ.typeParams
val (arityMismatches, varianceMismatches, stricterBounds) =
checkKindBoundsHK(tparamsHO, targ.typeSymbolDirect, tparam, tparam.owner) // NOTE: *not* targ.typeSymbol, which normalizes
if (!(arityMismatches.isEmpty && varianceMismatches.isEmpty && stricterBounds.isEmpty)){
errors += (targ+"'s type parameters do not match "+tparam+"'s expected parameters: "+
(for ((a, p) <- arityMismatches)
yield a+qualify(a,p)+ " has "+reporter.countElementsAsString(a.typeParams.length, "type parameter")+", but "+
p+qualify(p,a)+" has "+reporter.countAsString(p.typeParams.length)).toList.mkString(", ") +
(for ((a, p) <- varianceMismatches)
yield a+qualify(a,p)+ " is "+varStr(a)+", but "+
p+qualify(p,a)+" is declared "+varStr(p)).toList.mkString(", ") +
(for ((a, p) <- stricterBounds)
yield a+qualify(a,p)+"'s bounds "+a.info+" are stricter than "+
p+qualify(p,a)+"'s declared bounds "+p.info).toList.mkString(", "))
}
// case (tparam, targ) => println("no check: "+(tparam, targ, tparam.typeParams.isEmpty))
case _ =>
}
errors.toList
}
/** Substitite free type variables `undetparams' of polymorphic argument
* expression `tree', given two prototypes `strictPt', and `lenientPt'.
* `strictPt' is the first attempt prototype where type parameters
* are left unchanged. `lenientPt' is the fall-back prototype where type
* parameters are replaced by `WildcardType's. We try to instantiate
* first to `strictPt' and then, if this fails, to `lenientPt'. If both
* attempts fail, an error is produced.
*/
def inferArgumentInstance(tree: Tree, undetparams: List[Symbol],
strictPt: Type, lenientPt: Type) {
if (inferInfo)
println("infer argument instance "+tree+":"+tree.tpe+"\n"+
" undetparams = "+undetparams+"\n"+
" strict pt = "+strictPt+"\n"+
" lenient pt = "+lenientPt)
var targs = exprTypeArgs(undetparams, tree.tpe, strictPt)
if ((targs eq null) || !(tree.tpe.subst(undetparams, targs) <:< strictPt)) {
targs = exprTypeArgs(undetparams, tree.tpe, lenientPt)
}
substExpr(tree, undetparams, targs, lenientPt)
}
/** Substitute free type variables `undetparams; of polymorphic expression
* <code>tree</code>, given prototype <code>pt</code>.
*
* @param tree ...
* @param undetparams ...
* @param pt ...
*/
def inferExprInstance(tree: Tree, tparams: List[Symbol], pt: Type, keepNothings: Boolean): List[Symbol] = {
if (inferInfo)
println("infer expr instance "+tree+":"+tree.tpe+"\n"+
" tparams = "+tparams+"\n"+
" pt = "+pt)
val targs = exprTypeArgs(tparams, tree.tpe, pt)
val uninstantiated = new ListBuffer[Symbol]
val detargs = if (keepNothings || (targs eq null)) targs //@M: adjustTypeArgs fails if targs==null, neg/t0226
else adjustTypeArgs(tparams, targs, WildcardType, uninstantiated)
val undetparams = uninstantiated.toList
val detparams = tparams filterNot (undetparams contains _)
substExpr(tree, detparams, detargs, pt)
if (inferInfo)
println("inferred expr instance "+tree+", detargs = "+detargs+", undetparams = "+undetparams)
undetparams
}
/** Substitite free type variables `undetparams' of polymorphic argument
* expression <code>tree</code> to `targs', Error if `targs' is null
*
* @param tree ...
* @param undetparams ...
* @param targs ...
* @param pt ...
*/
private def substExpr(tree: Tree, undetparams: List[Symbol],
targs: List[Type], pt: Type) {
if (targs eq null) {
if (!tree.tpe.isErroneous && !pt.isErroneous)
error(tree.pos, "polymorphic expression cannot be instantiated to expected type" +
foundReqMsg(PolyType(undetparams, skipImplicit(tree.tpe)), pt))
} else {
new TreeTypeSubstituter(undetparams, targs).traverse(tree)
}
}
/** Substitite free type variables <code>undetparams</code> of application
* <code>fn(args)</code>, given prototype <code>pt</code>.
*
* @param fn ...
* @param undetparams ...
* @param args ...
* @param pt ...
* @return Return the list of type parameters that remain uninstantiated.
*/
def inferMethodInstance(fn: Tree, undetparams: List[Symbol],
args: List[Tree], pt0: Type): List[Symbol] = fn.tpe match {
case MethodType(params0, _) =>
if (inferInfo)
println("infer method instance "+fn+"\n"+
" undetparams = "+undetparams+"\n"+
" args = "+args+"\n"+
" pt = "+pt0)
try {
val pt = if (pt0.typeSymbol == UnitClass) WildcardType else pt0
val formals = formalTypes(params0 map (_.tpe), args.length)
val argtpes = actualTypes(args map (_.tpe.deconst), formals.length)
val restpe = fn.tpe.resultType(argtpes)
val uninstantiated = new ListBuffer[Symbol]
val targs = methTypeArgs(undetparams, formals, restpe, argtpes, pt, uninstantiated)
checkBounds(fn.pos, NoPrefix, NoSymbol, undetparams, targs, "inferred ")
val treeSubst = new TreeTypeSubstituter(undetparams, targs)
treeSubst.traverse(fn)
treeSubst.traverseTrees(args)
uninstantiated.toList
} catch {
case ex: NoInstance =>
errorTree(fn,
"no type parameters for " +
applyErrorMsg(
fn, " exist so that it can be applied to arguments ",
args map (_.tpe.widen), WildcardType) +
"\n --- because ---\n" + ex.getMessage())
List()
}
}
/** Type with all top-level occurrences of abstract types replaced by their bounds */
def widen(tp: Type): Type = tp match { // @M don't normalize here (compiler loops on pos/bug1090.scala )
case TypeRef(_, sym, _) if sym.isAbstractType =>
widen(tp.bounds.hi)
case TypeRef(_, sym, _) if sym.isAliasType =>
widen(tp.normalize)
case rtp @ RefinedType(parents, decls) =>
copyRefinedType(rtp, parents mapConserve (widen), decls)
case AnnotatedType(_, underlying, _) =>
widen(underlying)
case _ =>
tp
}
/** Substitite free type variables <code>undetparams</code> of type constructor
* <code>tree</code> in pattern, given prototype <code>pt</code>.
*
* @param tree ...
* @param undetparams ...
* @param pt ...
*/
def inferConstructorInstance(tree: Tree, undetparams: List[Symbol], pt0: Type) {
val pt = widen(pt0)
//println("infer constr inst "+tree+"/"+undetparams+"/"+pt0)
var restpe = tree.tpe.finalResultType
var tvars = undetparams map freshVar
/** Compute type arguments for undetermined params and substitute them in given tree.
*/
def computeArgs =
try {
val targs = solvedTypes(tvars, undetparams, undetparams map varianceInType(restpe),
true, lubDepth(List(restpe, pt)))
// checkBounds(tree.pos, NoPrefix, NoSymbol, undetparams, targs, "inferred ")
// no checkBounds here. If we enable it, test bug602 fails.
new TreeTypeSubstituter(undetparams, targs).traverse(tree)
} catch {
case ex: NoInstance =>
errorTree(tree, "constructor of type " + restpe +
" cannot be uniquely instantiated to expected type " + pt +
"\n --- because ---\n" + ex.getMessage())
}
def instError = {
if (settings.debug.value) Console.println("ici " + tree + " " + undetparams + " " + pt)
if (settings.explaintypes.value) explainTypes(restpe.instantiateTypeParams(undetparams, tvars), pt)
errorTree(tree, "constructor cannot be instantiated to expected type" +
foundReqMsg(restpe, pt))
}
if (restpe.instantiateTypeParams(undetparams, tvars) <:< pt) {
computeArgs
} else if (isFullyDefined(pt)) {
if (settings.debug.value) log("infer constr " + tree + ":" + restpe + ", pt = " + pt)
var ptparams = freeTypeParamsOfTerms.collect(pt)
if (settings.debug.value) log("free type params = " + ptparams)
val ptWithWildcards = pt.instantiateTypeParams(ptparams, ptparams map (ptparam => WildcardType))
tvars = undetparams map freshVar
if (restpe.instantiateTypeParams(undetparams, tvars) <:< ptWithWildcards) {
computeArgs
restpe = skipImplicit(tree.tpe.resultType)
if (settings.debug.value) log("new tree = " + tree + ":" + restpe)
val ptvars = ptparams map freshVar
val pt1 = pt.instantiateTypeParams(ptparams, ptvars)
if (isPopulated(restpe, pt1)) {
ptvars foreach instantiateTypeVar
} else { if (settings.debug.value) Console.println("no instance: "); instError }
} else { if (settings.debug.value) Console.println("not a subtype " + restpe.instantiateTypeParams(undetparams, tvars) + " of " + ptWithWildcards); instError }
} else { if (settings.debug.value) Console.println("not fully defined: " + pt); instError }
}
def instBounds(tvar: TypeVar): (Type, Type) = {
val tparam = tvar.origin.typeSymbol
val instType = toOrigin(tvar.constr.inst)
val (loBounds, hiBounds) =
if (instType != NoType && isFullyDefined(instType)) (List(instType), List(instType))
else (tvar.constr.loBounds, tvar.constr.hiBounds)
val lo = lub(tparam.info.bounds.lo :: loBounds map toOrigin)
val hi = glb(tparam.info.bounds.hi :: hiBounds map toOrigin)
(lo, hi)
}
def isInstantiatable(tvars: List[TypeVar]) = {
val tvars1 = tvars map (_.cloneInternal)
// Note: right now it's not clear that solving is complete, or how it can be made complete!
// So we should come back to this and investigate.
solve(tvars1, tvars1 map (_.origin.typeSymbol), tvars1 map (x => COVARIANT), false)
}
def instantiateTypeVar(tvar: TypeVar) {
val tparam = tvar.origin.typeSymbol
if (false &&
tvar.constr.inst != NoType &&
isFullyDefined(tvar.constr.inst) &&
(tparam.info.bounds containsType tvar.constr.inst)) {
context.nextEnclosing(_.tree.isInstanceOf[CaseDef]).pushTypeBounds(tparam)
tparam setInfo tvar.constr.inst
tparam resetFlag DEFERRED
if (settings.debug.value) log("new alias of " + tparam + " = " + tparam.info)
} else {
val (lo, hi) = instBounds(tvar)
if (lo <:< hi) {
if (!((lo <:< tparam.info.bounds.lo) && (tparam.info.bounds.hi <:< hi))) {
context.nextEnclosing(_.tree.isInstanceOf[CaseDef]).pushTypeBounds(tparam)
tparam setInfo mkTypeBounds(lo, hi)
if (settings.debug.value) log("new bounds of " + tparam + " = " + tparam.info)
} else {
if (settings.debug.value) log("redundant: "+tparam+" "+tparam.info+"/"+lo+" "+hi)
}
} else {
if (settings.debug.value) log("inconsistent: "+tparam+" "+lo+" "+hi)
}
}
}
def checkCheckable(pos: Position, tp: Type, kind: String) {
def patternWarning(tp: Type, prefix: String) = {
context.unit.uncheckedWarning(pos, prefix+tp+" in type"+kind+" is unchecked since it is eliminated by erasure")
}
def check(tp: Type, bound: List[Symbol]) {
def isLocalBinding(sym: Symbol) =
sym.isAbstractType &&
((bound contains sym) ||
sym.name == nme.WILDCARD.toTypeName || {
val e = context.scope.lookupEntry(sym.name)
(e ne null) && e.sym == sym && e.owner == context.scope
})
tp match {
case SingleType(pre, _) =>
check(pre, bound)
case TypeRef(pre, sym, args) =>
if (sym.isAbstractType)
patternWarning(tp, "abstract type ")
else if (sym.isAliasType)
check(tp.normalize, bound)
else if (sym == NothingClass || sym == NullClass || sym == AnyValClass)
error(pos, "type "+tp+" cannot be used in a type pattern or isInstanceOf test")
else
for (arg <- args) {
if (sym == ArrayClass) check(arg, bound)
else arg match {
case TypeRef(_, sym, _) if isLocalBinding(sym) =>
;
case _ =>
patternWarning(arg, "non variable type-argument ")
}
}
check(pre, bound)
case RefinedType(parents, decls) =>
if (decls.isEmpty) for (p <- parents) check(p, bound)
else patternWarning(tp, "refinement ")
case ExistentialType(quantified, tp1) =>
check(tp1, bound ::: quantified)
case ThisType(_) =>
;
case NoPrefix =>
;
case _ =>
patternWarning(tp, "type ")
}
}
check(tp, List())
}
/** Type intersection of simple type <code>tp1</code> with general
* type <code>tp2</code>. The result eliminates some redundancies.
*/
def intersect(tp1: Type, tp2: Type): Type = {
if (tp1 <:< tp2) tp1
else if (tp2 <:< tp1) tp2
else {
val reduced2 = tp2 match {
case rtp @ RefinedType(parents2, decls2) =>
copyRefinedType(rtp, parents2 filter (p2 => !(tp1 <:< p2)), decls2)
case _ =>
tp2
}
intersectionType(List(tp1, reduced2))
}
}
def inferTypedPattern(pos: Position, pattp: Type, pt0: Type): Type = {
val pt = widen(pt0)
checkCheckable(pos, pattp, " pattern")
if (!(pattp <:< pt)) {
val tpparams = freeTypeParamsOfTerms.collect(pattp)
if (settings.debug.value) log("free type params (1) = " + tpparams)
var tvars = tpparams map freshVar
var tp = pattp.instantiateTypeParams(tpparams, tvars)
if (!((tp <:< pt) && isInstantiatable(tvars))) {
tvars = tpparams map freshVar
tp = pattp.instantiateTypeParams(tpparams, tvars)
val ptparams = freeTypeParamsOfTerms.collect(pt)
if (settings.debug.value) log("free type params (2) = " + ptparams)
val ptvars = ptparams map freshVar
val pt1 = pt.instantiateTypeParams(ptparams, ptvars)
if (!(isPopulated(tp, pt1) && isInstantiatable(tvars ::: ptvars))) {
// In ticket #2486 we have this example of code which would fail
// here without a change:
//
// class A[T]
// class B extends A[Int]
// class C[T] extends A[T] { def f(t: A[T]) = t match { case x: B => () } }
//
// This reports error: pattern type is incompatible with expected type;
// found : B
// required: A[T]
//
// I am not sure what is the ideal fix, but for the moment I am intercepting
// it at the last minute and applying a looser check before failing.
if (!isPlausiblyCompatible(pattp, pt)) {
error(pos, "pattern type is incompatible with expected type"+foundReqMsg(pattp, pt))
return pattp
}
}
ptvars foreach instantiateTypeVar
}
tvars foreach instantiateTypeVar
}
intersect(pt, pattp)
}
def inferModulePattern(pat: Tree, pt: Type) =
if (!(pat.tpe <:< pt)) {
val ptparams = freeTypeParamsOfTerms.collect(pt)
if (settings.debug.value) log("free type params (2) = " + ptparams)
val ptvars = ptparams map freshVar
val pt1 = pt.instantiateTypeParams(ptparams, ptvars)
if (pat.tpe <:< pt1)
ptvars foreach instantiateTypeVar
else
error(pat.pos, "pattern type is incompatible with expected type"+foundReqMsg(pat.tpe, pt))
}
object toOrigin extends TypeMap {
def apply(tp: Type): Type = tp match {
case TypeVar(origin, _) => origin
case _ => mapOver(tp)
}
}
abstract class SymCollector extends TypeCollector(List[Symbol]()) {
protected def includeCondition(sym: Symbol): Boolean
def traverse(tp: Type) {
tp.normalize match {
case TypeRef(_, sym, _) =>
if (includeCondition(sym) && !result.contains(sym)) result = sym :: result
case _ =>
}
mapOver(tp)
}
}
object approximateAbstracts extends TypeMap {
def apply(tp: Type): Type = tp.normalize match {
case TypeRef(pre, sym, _) if sym.isAbstractType => WildcardType
case _ => mapOver(tp)
}
}
/** A traverser to collect type parameters referred to in a type
*/
object freeTypeParamsOfTerms extends SymCollector {
protected def includeCondition(sym: Symbol): Boolean =
sym.isAbstractType && sym.owner.isTerm
}
/** A traverser to collect type parameters referred to in a type
*/
object freeTypeParametersNoSkolems extends SymCollector {
protected def includeCondition(sym: Symbol): Boolean =
sym.isTypeParameter && sym.owner.isTerm
}
object typeRefs extends SymCollector {
protected def includeCondition(sym: Symbol): Boolean = true
}
def checkDead(tree: Tree): Tree = {
if (settings.Xwarndeadcode.value && tree.tpe != null && tree.tpe.typeSymbol == NothingClass)
context.warning (tree.pos, "dead code following this construct")
tree
}
/* -- Overload Resolution ---------------------------------------------- */
/*
def checkNotShadowed(pos: Position, pre: Type, best: Symbol, eligible: List[Symbol]) =
if (!phase.erasedTypes)
for (alt <- eligible) {
if (isProperSubClassOrObject(alt.owner, best.owner))
error(pos,
"erroneous reference to overloaded definition,\n"+
"most specific definition is: "+best+best.locationString+" of type "+pre.memberType(best)+
",\nyet alternative definition "+alt+alt.locationString+" of type "+pre.memberType(alt)+
"\nis defined in a subclass")
}
*/
/** Assign <code>tree</code> the symbol and type of the alternative which
* matches prototype <code>pt</code>, if it exists.
* If several alternatives match `pt', take parameterless one.
* If no alternative matches `pt', take the parameterless one anyway.
*/
def inferExprAlternative(tree: Tree, pt: Type): Unit = tree.tpe match {
case OverloadedType(pre, alts) => tryTwice {
var alts1 = alts filter (alt => isWeaklyCompatible(pre.memberType(alt), pt))
//println("trying "+alts1+(alts1 map (_.tpe))+(alts1 map (_.locationString))+" for "+pt)
val applicable = alts1
var secondTry = false
if (alts1.isEmpty) {
alts1 = alts
secondTry = true
}
def improves(sym1: Symbol, sym2: Symbol): Boolean =
sym2 == NoSymbol ||
{ val tp1 = pre.memberType(sym1)
val tp2 = pre.memberType(sym2)
(tp2 == ErrorType ||
!global.typer.infer.isWeaklyCompatible(tp2, pt) && global.typer.infer.isWeaklyCompatible(tp1, pt) ||
isStrictlyMoreSpecific(tp1, tp2, sym1, sym2)) }
val best = ((NoSymbol: Symbol) /: alts1) ((best, alt) =>
if (improves(alt, best)) alt else best)
val competing = alts1 dropWhile (alt => best == alt || improves(best, alt))
if (best == NoSymbol) {
if (settings.debug.value) {
tree match {
case Select(qual, _) =>
Console.println("qual: " + qual + ":" + qual.tpe +
" with decls " + qual.tpe.decls +
" with members " + qual.tpe.members +
" with members " + qual.tpe.member(newTermName("$minus")))
case _ =>
}
}
typeErrorTree(tree, tree.symbol.tpe, pt)
} else if (!competing.isEmpty) {
if (secondTry) {
typeErrorTree(tree, tree.symbol.tpe, pt)
} else {
if (!pt.isErroneous)
context.ambiguousError(tree.pos, pre, best, competing.head, "expected type " + pt)
setError(tree)
}
} else {
// val applicable = alts1 filter (alt =>
// global.typer.infer.isWeaklyCompatible(pre.memberType(alt), pt))
// checkNotShadowed(tree.pos, pre, best, applicable)
tree.setSymbol(best).setType(pre.memberType(best))
}
}
}
/** Assign <code>tree</code> the type of an alternative which is applicable
* to <code>argtpes</code>, and whose result type is compatible with `pt'.
* If several applicable alternatives exist, drop the alternatives which use
* default arguments, then select the most specialized one.
* If no applicable alternative exists, and pt != WildcardType, try again
* with pt = WildcardType.
* Otherwise, if there is no best alternative, error.
*
* @param argtpes contains the argument types. If an argument is named, as
* "a = 3", the corresponding type is `NamedType("a", Int)'. If the name
* of some NamedType does not exist in an alternative's parameter names,
* the type is replaces by `Unit', i.e. the argument is treated as an
* assignment expression.
*/
def inferMethodAlternative(tree: Tree, undetparams: List[Symbol],
argtpes: List[Type], pt0: Type): Unit = tree.tpe match {
case OverloadedType(pre, alts) =>
val pt = if (pt0.typeSymbol == UnitClass) WildcardType else pt0
tryTwice {
if (settings.debug.value)
log("infer method alt "+ tree.symbol +" with alternatives "+
(alts map pre.memberType) +", argtpes = "+ argtpes +", pt = "+ pt)
val allApplicable = alts filter (alt =>
isApplicable(undetparams, followApply(pre.memberType(alt)), argtpes, pt))
// if there are multiple, drop those that use a default
// (keep those that use vararg / tupling conversion)
val applicable =
if (allApplicable.length <= 1) allApplicable
else allApplicable filter (alt => {
val mtypes = followApply(alt.tpe) match {
case OverloadedType(_, alts) =>
// for functional values, the `apply' method might be overloaded
alts map (_.tpe)
case t => List(t)
}
mtypes.exists(t => t.paramTypes.length < argtpes.length || // tupling (*)
hasExactlyNumParams(t, argtpes.length)) // same nb or vararg
// (*) more arguments than parameters, but still applicable: tuplig conversion works.
// todo: should not return "false" when paramTypes = (Unit) no argument is given
// (tupling would work)
})
def improves(sym1: Symbol, sym2: Symbol) =
sym2 == NoSymbol || sym2.isError ||
isStrictlyMoreSpecific(followApply(pre.memberType(sym1)),
followApply(pre.memberType(sym2)), sym1, sym2)
val best = ((NoSymbol: Symbol) /: applicable) ((best, alt) =>
if (improves(alt, best)) alt else best)
val competing = applicable.dropWhile(alt => best == alt || improves(best, alt))
if (best == NoSymbol) {
if (pt == WildcardType) {
errorTree(tree, applyErrorMsg(tree, " cannot be applied to ", argtpes, pt))
} else {
inferMethodAlternative(tree, undetparams, argtpes, WildcardType)
}
} else if (!competing.isEmpty) {
if (!(argtpes exists (_.isErroneous)) && !pt.isErroneous)
context.ambiguousError(tree.pos, pre, best, competing.head,
"argument types " + argtpes.mkString("(", ",", ")") +
(if (pt == WildcardType) "" else " and expected result type " + pt))
setError(tree)
()
} else {
// checkNotShadowed(tree.pos, pre, best, applicable)
tree.setSymbol(best).setType(pre.memberType(best))
}
}
case _ =>
}
/** Try inference twice, once without views and once with views,
* unless views are already disabled.
*
* @param infer ...
*/
def tryTwice(infer: => Unit) {
if (context.implicitsEnabled) {
val reportGeneralErrors = context.reportGeneralErrors
context.reportGeneralErrors = false
context.implicitsEnabled = false
try {
infer
} catch {
case ex: CyclicReference =>
throw ex
case ex: TypeError =>
context.reportGeneralErrors = reportGeneralErrors
context.implicitsEnabled = true
infer
}
context.reportGeneralErrors = reportGeneralErrors
context.implicitsEnabled = true
} else infer
}
/** Assign <code>tree</code> the type of unique polymorphic alternative
* with <code>nparams</code> as the number of type parameters, if it exists.
* If several or none such polymorphic alternatives exist, error.
*
* @param tree ...
* @param nparams ...
*/
def inferPolyAlternatives(tree: Tree, argtypes: List[Type]): Unit = tree.tpe match {
case OverloadedType(pre, alts) =>
val sym0 = tree.symbol filter { alt => alt.typeParams.length == argtypes.length }
if (sym0 == NoSymbol) {
error(
tree.pos,
if (alts exists (alt => alt.typeParams.length > 0))
"wrong number of type parameters for " + treeSymTypeMsg(tree)
else treeSymTypeMsg(tree) + " does not take type parameters")
return
}
if (sym0.hasFlag(OVERLOADED)) {
val sym = sym0 filter { alt => isWithinBounds(pre, alt.owner, alt.typeParams, argtypes) }
if (sym == NoSymbol) {
if (!(argtypes exists (_.isErroneous))) {
error(
tree.pos,
"type arguments " + argtypes.mkString("[", ",", "]") +
" conform to the bounds of none of the overloaded alternatives of\n "+sym0+
": "+sym0.info)
return
}
}
if (sym.hasFlag(OVERLOADED)) {
val tparams = new AsSeenFromMap(pre, sym.alternatives.head.owner).mapOver(
sym.alternatives.head.typeParams)
val bounds = tparams map (_.tpe) //@M TODO: might be affected by change to tpe in Symbol
val tpe =
PolyType(tparams,
OverloadedType(AntiPolyType(pre, bounds), sym.alternatives))
sym.setInfo(tpe)
tree.setSymbol(sym).setType(tpe)
} else {
tree.setSymbol(sym).setType(pre.memberType(sym))
}
} else {
tree.setSymbol(sym0).setType(pre.memberType(sym0))
}
}
}
}