/* NSC -- new Scala compiler * Copyright 2005-2013 LAMP/EPFL * @author Martin Odersky */ package scala.tools.nsc package typechecker import scala.collection.{ mutable, immutable } import scala.util.control.ControlThrowable import symtab.Flags._ import scala.reflect.internal.Depth /** This trait contains methods related to type parameter inference. * * @author Martin Odersky * @version 1.0 */ trait Infer extends Checkable { self: Analyzer => import global._ import definitions._ import typeDebug.ptBlock import typeDebug.str.parentheses import typingStack.{ printTyping } /** The formal parameter types corresponding to `formals`. * If `formals` has a repeated last parameter, a list of * (numArgs - numFormals + 1) copies of its type is appended * to the other formals. By-name types are replaced with their * underlying type. * * @param removeByName allows keeping ByName parameters. Used in NamesDefaults. * @param removeRepeated allows keeping repeated parameter (if there's one argument). Used in NamesDefaults. */ def formalTypes(formals: List[Type], numArgs: Int, removeByName: Boolean = true, removeRepeated: Boolean = true): List[Type] = { val numFormals = formals.length val formals1 = if (removeByName) formals mapConserve dropByName else formals val expandLast = ( (removeRepeated || numFormals != numArgs) && isVarArgTypes(formals1) ) def lastType = formals1.last.dealiasWiden.typeArgs.head def expanded(n: Int) = (1 to n).toList map (_ => lastType) if (expandLast) formals1.init ::: expanded(numArgs - numFormals + 1) else formals1 } /** Sorts the alternatives according to the given comparison function. * Returns a list containing the best alternative as well as any which * the best fails to improve upon. */ private def bestAlternatives(alternatives: List[Symbol])(isBetter: (Symbol, Symbol) => Boolean): List[Symbol] = { def improves(sym1: Symbol, sym2: Symbol) = ( (sym2 eq NoSymbol) || sym2.isError || (sym2 hasAnnotation BridgeClass) || isBetter(sym1, sym2) ) alternatives sortWith improves match { case best :: rest if rest.nonEmpty => best :: rest.filterNot(alt => improves(best, alt)) case bests => bests } } // we must not allow CyclicReference to be thrown when sym.info is called // in checkAccessible, because that would mark the symbol erroneous, which it // is not. But if it's a true CyclicReference then macro def will report it. // See comments to TypeSigError for an explanation of this special case. // [Eugene] is there a better way? private object CheckAccessibleMacroCycle extends TypeCompleter { val tree = EmptyTree override def complete(sym: Symbol) = () } /** A fresh type variable with given type parameter as origin. */ def freshVar(tparam: Symbol): TypeVar = TypeVar(tparam) class NoInstance(msg: String) extends Throwable(msg) with ControlThrowable { } private class DeferredNoInstance(getmsg: () => String) extends NoInstance("") { override def getMessage(): String = getmsg() } private def ifNoInstance[T](f: String => T): PartialFunction[Throwable, T] = { case x: NoInstance => f(x.getMessage) } /** Map every TypeVar to its constraint.inst field. * throw a NoInstance exception if a NoType or WildcardType is encountered. */ object instantiate extends TypeMap { private var excludedVars = immutable.Set[TypeVar]() private def applyTypeVar(tv: TypeVar): Type = tv match { case TypeVar(origin, constr) if !constr.instValid => throw new DeferredNoInstance(() => s"no unique instantiation of type variable $origin could be found") case _ if excludedVars(tv) => throw new NoInstance("cyclic instantiation") case TypeVar(_, constr) => excludedVars += tv try apply(constr.inst) finally excludedVars -= tv } def apply(tp: Type): Type = tp match { case WildcardType | BoundedWildcardType(_) | NoType => throw new NoInstance("undetermined type") case tv: TypeVar if !tv.untouchable => applyTypeVar(tv) case _ => mapOver(tp) } } @inline final def falseIfNoInstance(body: => Boolean): Boolean = try body catch { case _: NoInstance => false } /** Is type fully defined, i.e. no embedded anytypes or wildcards in it? */ private[typechecker] def isFullyDefined(tp: Type): Boolean = tp match { case WildcardType | BoundedWildcardType(_) | NoType => false case NoPrefix | ThisType(_) | ConstantType(_) => true case TypeRef(pre, _, args) => isFullyDefined(pre) && (args forall isFullyDefined) case SingleType(pre, _) => isFullyDefined(pre) case RefinedType(ts, _) => ts forall isFullyDefined case TypeVar(_, constr) if constr.inst == NoType => false case _ => falseIfNoInstance({ instantiate(tp) ; true }) } /** 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. * @throws NoInstance */ def solvedTypes(tvars: List[TypeVar], tparams: List[Symbol], variances: List[Variance], upper: Boolean, depth: Depth): List[Type] = { if (tvars.isEmpty) Nil else { printTyping("solving for " + parentheses((tparams, tvars).zipped map ((p, tv) => s"${p.name}: $tv"))) // !!! What should be done with the return value of "solve", which is at present ignored? // The historical commentary says "no panic, it's good enough to just guess a solution, // we'll find out later whether it works", meaning don't issue an error here when types // don't conform to bounds. That means you can never trust the results of implicit search. // For an example where this was not being heeded, SI-2421. solve(tvars, tparams, variances, upper, depth) tvars map instantiate } } def skipImplicit(tp: Type) = tp match { case mt: MethodType if mt.isImplicit => mt.resultType case _ => 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. * This method seems to be performance critical. */ def normalize(tp: Type): Type = tp match { case PolyType(_, restpe) => logResult(sm"""|Normalizing PolyType in infer: | was: $restpe | now""")(normalize(restpe)) case mt @ MethodType(_, restpe) if mt.isImplicit => normalize(restpe) case mt @ MethodType(_, restpe) if !mt.isDependentMethodType => if (phase.erasedTypes) FunctionClass(mt.params.length).tpe else functionType(mt.paramTypes, normalize(restpe)) case NullaryMethodType(restpe) => normalize(restpe) case ExistentialType(tparams, qtpe) => newExistentialType(tparams, normalize(qtpe)) case _ => tp // @MAT aliases already handled by subtyping } private lazy val stdErrorClass = rootMirror.RootClass.newErrorClass(tpnme.ERROR) private lazy val stdErrorValue = stdErrorClass.newErrorValue(nme.ERROR) /** The context-dependent inferencer part */ abstract class Inferencer extends InferencerContextErrors with InferCheckable { def context: Context import InferErrorGen._ /* -- Error Messages --------------------------------------------------- */ def setError[T <: Tree](tree: T): T = { // SI-7388, one can incur a cycle calling sym.toString // (but it'd be nicer if that weren't so) def name = { val sym = tree.symbol val nameStr = try sym.toString catch { case _: CyclicReference => sym.nameString } newTermName(s"") } def errorClass = if (context.reportErrors) context.owner.newErrorClass(name.toTypeName) else stdErrorClass def errorValue = if (context.reportErrors) context.owner.newErrorValue(name) else stdErrorValue def errorSym = if (tree.isType) errorClass else errorValue if (tree.hasSymbolField) tree setSymbol errorSym tree setType ErrorType } def getContext = context def explainTypes(tp1: Type, tp2: Type) = { if (context.reportErrors) withDisambiguation(List(), tp1, tp2)(global.explainTypes(tp1, tp2)) } // When filtering sym down to the accessible alternatives leaves us empty handed. private def checkAccessibleError(tree: Tree, sym: Symbol, pre: Type, site: Tree): Tree = { if (settings.debug) { Console.println(context) Console.println(tree) Console.println("" + pre + " " + sym.owner + " " + context.owner + " " + context.outer.enclClass.owner + " " + sym.owner.thisType + (pre =:= sym.owner.thisType)) } ErrorUtils.issueTypeError(AccessError(tree, sym, pre, context.enclClass.owner, if (settings.check.isDefault) analyzer.lastAccessCheckDetails else ptBlock("because of an internal error (no accessible symbol)", "sym.ownerChain" -> sym.ownerChain, "underlyingSymbol(sym)" -> underlyingSymbol(sym), "pre" -> pre, "site" -> site, "tree" -> tree, "sym.accessBoundary(sym.owner)" -> sym.accessBoundary(sym.owner), "context.owner" -> context.owner, "context.outer.enclClass.owner" -> context.outer.enclClass.owner ) ))(context) setError(tree) } /* -- Tests & Checks---------------------------------------------------- */ /** Check that `sym` is defined and accessible as a member of * tree `site` with type `pre` in current context. * @PP: In case it's not abundantly obvious to anyone who might read * this, the method does a lot more than "check" these things, as does * nearly every method in the compiler, so don't act all shocked. * This particular example "checks" its way to assigning both the * symbol and type of the incoming tree, in addition to forcing lots * of symbol infos on its way to transforming java raw types (but * only of terms - why?) * * Note: pre is not refchecked -- moreover, refchecking the resulting tree may not refcheck pre, * since pre may not occur in its type (callers should wrap the result in a TypeTreeWithDeferredRefCheck) */ def checkAccessible(tree: Tree, sym: Symbol, pre: Type, site: Tree): Tree = { def malformed(ex: MalformedType, instance: Type): Type = { val what = if (ex.msg contains "malformed type") "is malformed" else s"contains a ${ex.msg}" val message = s"\n because its instance type $instance $what" val error = AccessError(tree, sym, pre, context.enclClass.owner, message) ErrorUtils.issueTypeError(error)(context) ErrorType } def accessible = sym filter (alt => context.isAccessible(alt, pre, site.isInstanceOf[Super])) match { case NoSymbol if sym.isJavaDefined && context.unit.isJava => sym // don't try to second guess Java; see #4402 case sym1 => sym1 } // XXX So... what's this for exactly? if (context.unit.exists) context.unit.depends += sym.enclosingTopLevelClass if (sym.isError) tree setSymbol sym setType ErrorType else accessible match { case NoSymbol => checkAccessibleError(tree, sym, pre, site) case sym if context.owner.isTermMacro && (sym hasFlag LOCKED) => throw CyclicReference(sym, CheckAccessibleMacroCycle) case sym => val sym1 = if (sym.isTerm) sym.cookJavaRawInfo() else sym // xform java rawtypes into existentials val owntype = ( try pre memberType sym1 catch { case ex: MalformedType => malformed(ex, pre memberType underlyingSymbol(sym)) } ) tree setSymbol sym1 setType ( pre match { case _: SuperType => owntype map (tp => if (tp eq pre) site.symbol.thisType else tp) case _ => owntype } ) } } /** "Compatible" means conforming after conversions. * "Raising to a thunk" is not implicit; therefore, for purposes of applicability and * specificity, an arg type `A` is considered compatible with cbn formal parameter type `=>A`. * For this behavior, the type `pt` must have cbn params preserved; for instance, `formalTypes(removeByName = false)`. * * `isAsSpecific` no longer prefers A by testing applicability to A for both m(A) and m(=>A) * since that induces a tie between m(=>A) and m(=>A,B*) [SI-3761] */ private def isCompatible(tp: Type, pt: Type): Boolean = { def isCompatibleByName(tp: Type, pt: Type): Boolean = ( isByNameParamType(pt) && !isByNameParamType(tp) && isCompatible(tp, dropByName(pt)) ) def isCompatibleSam(tp: Type, pt: Type): Boolean = (definitions.isFunctionType(tp) || tp.isInstanceOf[MethodType] || tp.isInstanceOf[PolyType]) && { val samFun = typer.samToFunctionType(pt) (samFun ne NoType) && isCompatible(tp, samFun) } val tp1 = normalize(tp) ( (tp1 weak_<:< pt) || isCoercible(tp1, pt) || isCompatibleByName(tp, pt) || isCompatibleSam(tp, pt) ) } def isCompatibleArgs(tps: List[Type], pts: List[Type]) = (tps corresponds pts)(isCompatible) def isWeaklyCompatible(tp: Type, pt: Type): Boolean = { def isCompatibleNoParamsMethod = tp match { case MethodType(Nil, restpe) => isCompatible(restpe, pt) case _ => false } ( pt.typeSymbol == UnitClass // can perform unit coercion || isCompatible(tp, pt) || isCompatibleNoParamsMethod // can perform implicit () instantiation ) } /* 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 = context.withImplicitsDisabled(isWeaklyCompatible(tp, pt)) // Overridden at the point of instantiation, where inferView is visible. def isCoercible(tp: Type, pt: Type): Boolean = false /* -- Type instantiation------------------------------------------------ */ /** Replace any (possibly bounded) wildcard types in type `tp` * by existentially bound variables. */ def makeFullyDefined(tp: Type): Type = { var tparams: List[Symbol] = Nil def addTypeParam(bounds: TypeBounds): Type = { val tparam = context.owner.newExistential(newTypeName("_"+tparams.size), context.tree.pos.focus) setInfo bounds tparams ::= tparam tparam.tpe } val tp1 = tp map { case WildcardType => addTypeParam(TypeBounds.empty) case BoundedWildcardType(bounds) => addTypeParam(bounds) case t => t } if (tp eq tp1) tp else existentialAbstraction(tparams.reverse, tp1) } def ensureFullyDefined(tp: Type): Type = if (isFullyDefined(tp)) tp else makeFullyDefined(tp) /** Return inferred type arguments of polymorphic expression, given * type vars, its type parameters and result type and a prototype `pt`. * If the type variables cannot be instantiated such that the type * conforms to `pt`, return null. */ private def exprTypeArgs(tvars: List[TypeVar], tparams: List[Symbol], restpe: Type, pt: Type, useWeaklyCompatible: Boolean): List[Type] = { def restpeInst = restpe.instantiateTypeParams(tparams, tvars) def conforms = if (useWeaklyCompatible) isWeaklyCompatible(restpeInst, pt) else isCompatible(restpeInst, pt) // If the restpe is an implicit method, and the expected type is fully defined // optimize type variables wrt to the implicit formals only; ignore the result type. // See test pos/jesper.scala def variance = restpe match { case mt: MethodType if mt.isImplicit && isFullyDefined(pt) => MethodType(mt.params, AnyTpe) case _ => restpe } def solve() = solvedTypes(tvars, tparams, tparams map varianceInType(variance), upper = false, lubDepth(restpe :: pt :: Nil)) if (conforms) try solve() catch { case _: NoInstance => null } else null } /** Overload which allocates fresh type vars. * The other one exists because apparently inferExprInstance needs access to the typevars * after the call, and it's wasteful to return a tuple and throw it away almost every time. */ private def exprTypeArgs(tparams: List[Symbol], restpe: Type, pt: Type, useWeaklyCompatible: Boolean): List[Type] = exprTypeArgs(tparams map freshVar, tparams, restpe, pt, useWeaklyCompatible) /** Return inferred proto-type arguments of function, given * its type and value parameters and result type, and a * prototype `pt` 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. */ def protoTypeArgs(tparams: List[Symbol], formals: List[Type], restpe: Type, pt: Type): List[Type] = { // Map type variable to its instance, or, if `variance` is variant, // to its upper or lower bound def instantiateToBound(tvar: TypeVar, variance: Variance): Type = { 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 assert(tvar.constr.inst != tvar, tvar.origin) instantiate(tvar.constr.inst) } if (tvar.constr.instValid) instantiate(tvar.constr.inst) else if (loBounds.nonEmpty && variance.isContravariant) setInst(lower) else if (hiBounds.nonEmpty && (variance.isPositive || loBounds.nonEmpty && upper <:< lower)) setInst(upper) else WildcardType } val tvars = tparams map freshVar if (isConservativelyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt)) map2(tparams, tvars)((tparam, tvar) => try instantiateToBound(tvar, varianceInTypes(formals)(tparam)) catch { case ex: NoInstance => WildcardType } ) else tvars map (_ => WildcardType) } /** [Martin] Can someone comment this please? I have no idea what it's for * and the code is not exactly readable. */ object AdjustedTypeArgs { val Result = mutable.LinkedHashMap type Result = mutable.LinkedHashMap[Symbol, Option[Type]] def unapply(m: Result): Some[(List[Symbol], List[Type])] = Some(toLists( (m collect {case (p, Some(a)) => (p, a)}).unzip )) object Undets { def unapply(m: Result): Some[(List[Symbol], List[Type], List[Symbol])] = Some(toLists{ val (ok, nok) = m.map{case (p, a) => (p, a.getOrElse(null))}.partition(_._2 ne null) val (okArgs, okTparams) = ok.unzip (okArgs, okTparams, nok.keys) }) } object AllArgsAndUndets { def unapply(m: Result): Some[(List[Symbol], List[Type], List[Type], List[Symbol])] = Some(toLists{ val (ok, nok) = m.map{case (p, a) => (p, a.getOrElse(null))}.partition(_._2 ne null) val (okArgs, okTparams) = ok.unzip (okArgs, okTparams, m.values.map(_.getOrElse(NothingTpe)), nok.keys) }) } private def toLists[A1, A2](pxs: (Iterable[A1], Iterable[A2])) = (pxs._1.toList, pxs._2.toList) private def toLists[A1, A2, A3](pxs: (Iterable[A1], Iterable[A2], Iterable[A3])) = (pxs._1.toList, pxs._2.toList, pxs._3.toList) private def toLists[A1, A2, A3, A4](pxs: (Iterable[A1], Iterable[A2], Iterable[A3], Iterable[A4])) = (pxs._1.toList, pxs._2.toList, pxs._3.toList, pxs._4.toList) } /** Retract arguments that were inferred to Nothing because inference failed. Correct types for repeated params. * * We detect Nothing-due-to-failure by only retracting a parameter if either: * - it occurs in an invariant/contravariant position in `restpe` * - `restpe == WildcardType` * * Retracted parameters are mapped to None. * TODO: * - make sure the performance hit of storing these in a map is acceptable (it's going to be a small map in 90% of the cases, I think) * - refactor further up the callstack so that we don't have to do this post-factum adjustment? * * Rewrite for repeated param types: Map T* entries to Seq[T]. * @return map from tparams to inferred arg, if inference was successful, tparams that map to None are considered left undetermined * type parameters that are inferred as `scala.Nothing` and that are not covariant in `restpe` are taken to be undetermined */ def adjustTypeArgs(tparams: List[Symbol], tvars: List[TypeVar], targs: List[Type], restpe: Type = WildcardType): AdjustedTypeArgs.Result = { val buf = AdjustedTypeArgs.Result.newBuilder[Symbol, Option[Type]] foreach3(tparams, tvars, targs) { (tparam, tvar, targ) => val retract = ( targ.typeSymbol == NothingClass // only retract Nothings && (restpe.isWildcard || !varianceInType(restpe)(tparam).isPositive) // don't retract covariant occurrences ) buf += ((tparam, if (retract) None else Some( if (targ.typeSymbol == RepeatedParamClass) targ.baseType(SeqClass) else if (targ.typeSymbol == JavaRepeatedParamClass) targ.baseType(ArrayClass) // this infers Foo.type instead of "object Foo" (see also widenIfNecessary) else if (targ.typeSymbol.isModuleClass || tvar.constr.avoidWiden) targ else targ.widen ) )) } buf.result() } /** Return inferred type arguments, given type parameters, formal parameters, * argument types, result type and expected result type. * If this is not possible, throw a `NoInstance` exception. * Undetermined type arguments are represented by `definitions.NothingTpe`. * No check that inferred parameters conform to their bounds is made here. * * @param fn the function for reporting, may be empty * @param tparams the type parameters of the method * @param formals the value parameter types of the method * @param restpe the result type of the method * @param argtpes the argument types of the application * @param pt the expected return type of the application * @return @see adjustTypeArgs * * @throws NoInstance */ def methTypeArgs(fn: Tree, tparams: List[Symbol], formals: List[Type], restpe: Type, argtpes: List[Type], pt: Type): AdjustedTypeArgs.Result = { val tvars = tparams map freshVar if (!sameLength(formals, argtpes)) throw new NoInstance("parameter lists differ in length") val restpeInst = restpe.instantiateTypeParams(tparams, tvars) // first check if typevars can be fully defined from the expected type. // The return value isn't used so I'm making it obvious that this side // effects, because a function called "isXXX" is not the most obvious // side effecter. isConservativelyCompatible(restpeInst, pt) // Return value unused with the following explanation: // // 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 the // search for an implicit from restpe => pt fails due to ambiguity. // See #347. 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. map2(argtpes, formals) { (argtpe, formal) => val tp1 = argtpe.deconst.instantiateTypeParams(tparams, tvars) val pt1 = formal.instantiateTypeParams(tparams, tvars) // Note that isCompatible side-effects: subtype checks involving typevars // are recorded in the typevar's bounds (see TypeConstraint) if (!isCompatible(tp1, pt1)) { throw new DeferredNoInstance(() => "argument expression's type is not compatible with formal parameter type" + foundReqMsg(tp1, pt1)) } } val targs = solvedTypes(tvars, tparams, tparams map varianceInTypes(formals), upper = false, lubDepth(formals) max lubDepth(argtpes)) // Can warn about inferring Any/AnyVal as long as they don't appear // explicitly anywhere amongst the formal, argument, result, or expected type. // ...or lower bound of a type param, since they're asking for it. def canWarnAboutAny = { val loBounds = tparams map (_.info.bounds.lo) def containsAny(t: Type) = (t contains AnyClass) || (t contains AnyValClass) val hasAny = pt :: restpe :: formals ::: argtpes ::: loBounds exists (_.dealiasWidenChain exists containsAny) !hasAny } if (settings.warnInferAny && context.reportErrors && !fn.isEmpty && canWarnAboutAny) { targs.foreach(_.typeSymbol match { case sym @ (AnyClass | AnyValClass) => reporter.warning(fn.pos, s"a type was inferred to be `${sym.name}`; this may indicate a programming error.") case _ => }) } adjustTypeArgs(tparams, tvars, targs, restpe) } /** One must step carefully when assessing applicability due to * complications from varargs, tuple-conversion, named arguments. * This method is used to filter out inapplicable methods, * its behavior slightly configurable based on what stage of * overloading resolution we're at. * * This method has boolean parameters, which is usually suboptimal * but I didn't work out a better way. They don't have defaults, * and the method's scope is limited. */ private[typechecker] def isApplicableBasedOnArity(tpe: Type, argsCount: Int, varargsStar: Boolean, tuplingAllowed: Boolean): Boolean = followApply(tpe) match { case OverloadedType(pre, alts) => // followApply may return an OverloadedType (tpe is a value type with multiple `apply` methods) alts exists (alt => isApplicableBasedOnArity(pre memberType alt, argsCount, varargsStar, tuplingAllowed)) case _ => val paramsCount = tpe.params.length // simpleMatch implies we're not using defaults val simpleMatch = paramsCount == argsCount val varargsTarget = isVarArgsList(tpe.params) // varargsMatch implies we're not using defaults, as varargs and defaults are mutually exclusive def varargsMatch = varargsTarget && (paramsCount - 1) <= argsCount // another reason why auto-tupling is a bad idea: it can hide the use of defaults, so must rule those out explicitly def tuplingMatch = tuplingAllowed && eligibleForTupleConversion(paramsCount, argsCount, varargsTarget) // varargs and defaults are mutually exclusive, so not using defaults if `varargsTarget` // we're not using defaults if there are (at least as many) arguments as parameters (not using exact match to allow for tupling) def notUsingDefaults = varargsTarget || paramsCount <= argsCount // A varargs star call, e.g. (x, y:_*) can only match a varargs method // with the same number of parameters. See SI-5859 for an example of what // would fail were this not enforced before we arrived at isApplicable. if (varargsStar) varargsTarget && simpleMatch else simpleMatch || varargsMatch || (tuplingMatch && notUsingDefaults) } private[typechecker] def followApply(tp: Type): Type = tp match { case _ if tp.isError => tp // SI-8228, `ErrorType nonPrivateMember nme.apply` returns an member with an erroneous type! case NullaryMethodType(restp) => val restp1 = followApply(restp) if (restp1 eq restp) tp else restp1 case _ => //OPT cut down on #closures by special casing non-overloaded case // was: tp.nonPrivateMember(nme.apply) filter (_.isPublic) tp nonPrivateMember nme.apply match { case NoSymbol => tp case sym if !sym.isOverloaded && sym.isPublic => OverloadedType(tp, sym.alternatives) case sym => OverloadedType(tp, sym.filter(_.isPublic).alternatives) } } /** * 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]): (List[Type], Array[Int], Boolean) = { val argPos = Array.fill(argtpes.length)(-1) var positionalAllowed, namesOK = true var index = 0 val argtpes1 = argtpes map { case NamedType(name, tp) => // a named argument var res = tp val pos = params.indexWhere(p => paramMatchesName(p, name) && !p.isSynthetic) if (pos == -1) { if (positionalAllowed) { // treat assignment as positional argument argPos(index) = index res = UnitTpe // TODO: this is a bit optimistic, the name may not refer to a mutable variable... } else // unknown parameter name namesOK = false } else if (argPos.contains(pos)) { // parameter specified twice namesOK = false } else { if (index != pos) 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) } /** True if the given parameter list can accept a tupled argument list, * and the argument list can be tupled (based on its length.) */ def eligibleForTupleConversion(paramsCount: Int, argsCount: Int, varargsTarget: Boolean): Boolean = { def canSendTuple = argsCount match { case 0 => !varargsTarget // avoid () to (()) conversion - SI-3224 case 1 => false // can't tuple a single argument case n => n <= MaxTupleArity // <= 22 arguments } def canReceiveTuple = paramsCount match { case 1 => true case 2 => varargsTarget case _ => false } canSendTuple && canReceiveTuple } def eligibleForTupleConversion(formals: List[Type], argsCount: Int): Boolean = formals match { case p :: Nil => eligibleForTupleConversion(1, argsCount, varargsTarget = isScalaRepeatedParamType(p)) case _ :: p :: Nil if isScalaRepeatedParamType(p) => eligibleForTupleConversion(2, argsCount, varargsTarget = true) case _ => false } /** The type of an argument list after being coerced to a tuple. * @pre: the argument list is eligible for tuple conversion. */ private def typeAfterTupleConversion(argtpes: List[Type]): Type = ( if (argtpes.isEmpty) UnitTpe // aka "Tuple0" else tupleType(argtpes map { case NamedType(name, tp) => UnitTpe // not a named arg - only assignments here case RepeatedType(tp) => tp // but probably shouldn't be tupling a call containing :_* case tp => tp }) ) /** If the argument list needs to be tupled for the parameter list, * a list containing the type of the tuple. Otherwise, the original * argument list. */ def tupleIfNecessary(formals: List[Type], argtpes: List[Type]): List[Type] = { if (eligibleForTupleConversion(formals, argtpes.size)) typeAfterTupleConversion(argtpes) :: Nil else argtpes } private def isApplicableToMethod(undetparams: List[Symbol], mt: MethodType, argtpes0: List[Type], pt: Type): Boolean = { val formals = formalTypes(mt.paramTypes, argtpes0.length, removeByName = false) def missingArgs = missingParams[Type](argtpes0, mt.params, x => Some(x) collect { case NamedType(n, _) => n }) def argsTupled = tupleIfNecessary(mt.paramTypes, argtpes0) def argsPlusDefaults = missingArgs match { case (args, _) if args forall (_.hasDefault) => argtpes0 ::: makeNamedTypes(args) case _ => argsTupled } // If args eq the incoming arg types, fail; otherwise recurse with these args. def tryWithArgs(args: List[Type]) = ( (args ne argtpes0) && isApplicableToMethod(undetparams, mt, args, pt) // used to be isApplicable(undetparams, mt, args, pt), knowing mt: MethodType ) def tryInstantiating(args: List[Type]) = falseIfNoInstance { val restpe = mt resultType args val AdjustedTypeArgs.Undets(okparams, okargs, leftUndet) = methTypeArgs(EmptyTree, undetparams, formals, restpe, args, pt) val restpeInst = restpe.instantiateTypeParams(okparams, okargs) // #2665: must use weak conformance, not regular one (follow the monomorphic case above) exprTypeArgs(leftUndet, restpeInst, pt, useWeaklyCompatible = true) match { case null => false case _ => isWithinBounds(NoPrefix, NoSymbol, okparams, okargs) } } def typesCompatible(args: List[Type]) = undetparams match { case Nil => isCompatibleArgs(args, formals) && isWeaklyCompatible(mt resultType args, pt) case _ => tryInstantiating(args) } // when using named application, the vararg param has to be specified exactly once def reorderedTypesCompatible = checkNames(argtpes0, mt.params) match { case (_, _, false) => false // names are not ok case (_, pos, _) if !allArgsArePositional(pos) && !sameLength(formals, mt.params) => false // different length lists and all args not positional case (args, pos, _) => typesCompatible(reorderArgs(args, pos)) } compareLengths(argtpes0, formals) match { case 0 if containsNamedType(argtpes0) => reorderedTypesCompatible // right number of args, wrong order case 0 => typesCompatible(argtpes0) // fast track if no named arguments are used case x if x > 0 => tryWithArgs(argsTupled) // too many args, try tupling case _ => tryWithArgs(argsPlusDefaults) // too few args, try adding defaults or tupling } } /** Is there an instantiation of free type variables `undetparams` such that * function type `ftpe` is applicable to `argtpes0` and its result conform to `pt`? * * @param ftpe the type of the function (often a MethodType) * @param argtpes0 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). */ 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(_, qtpe) => isApplicable(undetparams, qtpe, argtpes0, pt) case mt @ MethodType(_, _) => isApplicableToMethod(undetparams, mt, argtpes0, pt) case NullaryMethodType(restpe) => isApplicable(undetparams, restpe, argtpes0, pt) case PolyType(tparams, restpe) => createFromClonedSymbols(tparams, restpe)((tps1, res1) => isApplicable(tps1 ::: undetparams, res1, argtpes0, pt)) case ErrorType => true case _ => false } ) /** * Are arguments of the given types applicable to `ftpe`? Type argument inference * is tried twice: firstly with the given expected type, and secondly with `WildcardType`. */ // Todo: Try to make isApplicable always safe (i.e. not cause TypeErrors). // The chance of TypeErrors should be reduced through context errors private[typechecker] def isApplicableSafe(undetparams: List[Symbol], ftpe: Type, argtpes0: List[Type], pt: Type): Boolean = { def applicableExpectingPt(pt: Type): Boolean = { val silent = context.makeSilent(reportAmbiguousErrors = false) val result = newTyper(silent).infer.isApplicable(undetparams, ftpe, argtpes0, pt) if (silent.reporter.hasErrors && !pt.isWildcard) applicableExpectingPt(WildcardType) // second try else result } applicableExpectingPt(pt) } /** Is type `ftpe1` strictly more specific than type `ftpe2` * when both are alternatives in an overloaded function? * @see SLS (sec:overloading-resolution) */ def isAsSpecific(ftpe1: Type, ftpe2: Type): Boolean = { def checkIsApplicable(argtpes: List[Type]) = isApplicable(Nil, ftpe2, argtpes, WildcardType) def bothAreVarargs = isVarArgsList(ftpe1.params) && isVarArgsList(ftpe2.params) def onRight = ftpe2 match { case OverloadedType(pre, alts) => alts forall (alt => isAsSpecific(ftpe1, pre memberType alt)) case et: ExistentialType => et.withTypeVars(isAsSpecific(ftpe1, _)) case mt @ MethodType(_, restpe) => !mt.isImplicit || isAsSpecific(ftpe1, restpe) case NullaryMethodType(res) => isAsSpecific(ftpe1, res) case PolyType(tparams, NullaryMethodType(restpe)) => isAsSpecific(ftpe1, PolyType(tparams, restpe)) case PolyType(tparams, mt @ MethodType(_, restpe)) => !mt.isImplicit || isAsSpecific(ftpe1, PolyType(tparams, restpe)) case _ => isAsSpecificValueType(ftpe1, ftpe2, Nil, Nil) } ftpe1 match { case OverloadedType(pre, alts) => alts exists (alt => isAsSpecific(pre memberType alt, ftpe2)) case et: ExistentialType => isAsSpecific(et.skolemizeExistential, ftpe2) case NullaryMethodType(restpe) => isAsSpecific(restpe, ftpe2) case mt @ MethodType(_, restpe) if mt.isImplicit => isAsSpecific(restpe, ftpe2) case mt @ MethodType(_, _) if bothAreVarargs => checkIsApplicable(mt.paramTypes mapConserve repeatedToSingle) case mt @ MethodType(params, _) if params.nonEmpty => checkIsApplicable(mt.paramTypes) case PolyType(tparams, NullaryMethodType(restpe)) => isAsSpecific(PolyType(tparams, restpe), ftpe2) case PolyType(tparams, mt @ MethodType(_, restpe)) if mt.isImplicit => isAsSpecific(PolyType(tparams, restpe), ftpe2) case PolyType(_, mt @ MethodType(params, _)) if params.nonEmpty => checkIsApplicable(mt.paramTypes) case ErrorType => true case _ => onRight } } private def isAsSpecificValueType(tpe1: Type, tpe2: Type, undef1: List[Symbol], undef2: List[Symbol]): Boolean = tpe1 match { case PolyType(tparams1, rtpe1) => isAsSpecificValueType(rtpe1, tpe2, undef1 ::: tparams1, undef2) case _ => tpe2 match { case PolyType(tparams2, rtpe2) => isAsSpecificValueType(tpe1, rtpe2, undef1, undef2 ::: tparams2) case _ => existentialAbstraction(undef1, tpe1) <:< existentialAbstraction(undef2, tpe2) } } /** 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 ne sym2) && (sym1 ne 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 eq NoSymbol) || isProperSubClassOrObject(sym1.safeOwner, 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 isAsSpecific 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) specificCount + subClassCount > 0 } } private def covariantReturnOverride(ftpe1: Type, ftpe2: Type): Boolean = ftpe1 match { case MethodType(_, rtpe1) => ftpe2 match { case MethodType(_, rtpe2) => rtpe1 <:< rtpe2 || rtpe2.typeSymbol == ObjectClass case _ => false } case _ => false } /** error if arguments not within bounds. */ def checkBounds(tree: Tree, pre: Type, owner: Symbol, tparams: List[Symbol], targs: List[Type], prefix: String): Boolean = { def issueBoundsError() = { NotWithinBounds(tree, prefix, targs, tparams, Nil) ; false } def issueKindBoundErrors(errs: List[String]) = { KindBoundErrors(tree, prefix, targs, tparams, errs) ; false } //@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 def check() = checkKindBounds(tparams, targs, pre, owner) match { case Nil => isWithinBounds(pre, owner, tparams, targs) || issueBoundsError() case errs => (targs contains WildcardType) || issueKindBoundErrors(errs) } targs.exists(_.isErroneous) || tparams.exists(_.isErroneous) || check() } def checkKindBounds(tparams: List[Symbol], targs: List[Type], pre: Type, owner: Symbol): List[String] = { checkKindBounds0(tparams, targs, pre, owner, explainErrors = true) map { case (targ, tparam, kindErrors) => kindErrors.errorMessage(targ, tparam) } } /** Substitute 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) { printTyping(tree, s"inferring arg instance based on pt0=$strictPt, pt1=$lenientPt") var targs = exprTypeArgs(undetparams, tree.tpe, strictPt, useWeaklyCompatible = false) if ((targs eq null) || !(tree.tpe.subst(undetparams, targs) <:< strictPt)) targs = exprTypeArgs(undetparams, tree.tpe, lenientPt, useWeaklyCompatible = false) substExpr(tree, undetparams, targs, lenientPt) printTyping(tree, s"infer arg instance from pt0=$strictPt, pt1=$lenientPt; targs=$targs") } /** Infer type arguments `targs` for `tparams` of polymorphic expression in `tree`, given prototype `pt`. * * Substitute `tparams` to `targs` in `tree`, after adjustment by `adjustTypeArgs`, returning the type parameters that were not determined * If passed, infers against specified type `treeTp` instead of `tree.tp`. */ def inferExprInstance(tree: Tree, tparams: List[Symbol], pt: Type = WildcardType, treeTp0: Type = null, keepNothings: Boolean = true, useWeaklyCompatible: Boolean = false): List[Symbol] = { val treeTp = if (treeTp0 eq null) tree.tpe else treeTp0 // can't refer to tree in default for treeTp0 val tvars = tparams map freshVar val targs = exprTypeArgs(tvars, tparams, treeTp, pt, useWeaklyCompatible) def infer_s = map3(tparams, tvars, targs)((tparam, tvar, targ) => s"$tparam=$tvar/$targ") mkString "," printTyping(tree, s"infer expr instance from pt=$pt, $infer_s") // SI-7899 inferring by-name types is unsound def targsStrict = if (targs eq null) null else targs mapConserve dropByName if (keepNothings || (targs eq null)) { //@M: adjustTypeArgs fails if targs==null, neg/t0226 substExpr(tree, tparams, targsStrict, pt) List() } else { val AdjustedTypeArgs.Undets(okParams, okArgs, leftUndet) = adjustTypeArgs(tparams, tvars, targsStrict) def solved_s = map2(okParams, okArgs)((p, a) => s"$p=$a") mkString "," def undet_s = leftUndet match { case Nil => "" case ps => ps.mkString(", undet=", ",", "") } printTyping(tree, s"infer solved $solved_s$undet_s") substExpr(tree, okParams, okArgs, pt) leftUndet } } /** Substitute free type variables `undetparams` of polymorphic argument * expression `tree` to `targs`, Error if `targs` is null. */ private def substExpr(tree: Tree, undetparams: List[Symbol], targs: List[Type], pt: Type) { if (targs eq null) { if (!tree.tpe.isErroneous && !pt.isErroneous) PolymorphicExpressionInstantiationError(tree, undetparams, pt) } else { new TreeTypeSubstituter(undetparams, targs).traverse(tree) notifyUndetparamsInferred(undetparams, targs) } } /** Substitute free type variables `undetparams` of application * `fn(args)`, given prototype `pt`. * * @param fn fn: the function that needs to be instantiated. * @param undetparams the parameters that need to be determined * @param args the actual arguments supplied in the call. * @param pt0 the expected type of the function application * @return The type parameters that remain uninstantiated, * and that thus have not been substituted. */ def inferMethodInstance(fn: Tree, undetparams: List[Symbol], args: List[Tree], pt0: Type): List[Symbol] = fn.tpe match { case mt @ MethodType(params0, _) => try { val pt = if (pt0.typeSymbol == UnitClass) WildcardType else pt0 val formals = formalTypes(mt.paramTypes, args.length) val argtpes = tupleIfNecessary(formals, args map (x => elimAnonymousClass(x.tpe.deconst))) val restpe = fn.tpe.resultType(argtpes) val AdjustedTypeArgs.AllArgsAndUndets(okparams, okargs, allargs, leftUndet) = methTypeArgs(fn, undetparams, formals, restpe, argtpes, pt) if (checkBounds(fn, NoPrefix, NoSymbol, undetparams, allargs, "inferred ")) { val treeSubst = new TreeTypeSubstituter(okparams, okargs) treeSubst traverseTrees fn :: args notifyUndetparamsInferred(okparams, okargs) leftUndet match { case Nil => Nil case xs => // #3890 val xs1 = treeSubst.typeMap mapOver xs if (xs ne xs1) new TreeSymSubstTraverser(xs, xs1) traverseTrees fn :: args xs1 } } else Nil } catch ifNoInstance { msg => NoMethodInstanceError(fn, args, msg); List() } } /** Substitute free type variables `undetparams` of type constructor * `tree` in pattern, given prototype `pt`. * * @param tree the constructor that needs to be instantiated * @param undetparams the undetermined type parameters * @param pt0 the expected result type of the instance */ def inferConstructorInstance(tree: Tree, undetparams: List[Symbol], pt0: Type) { val pt = abstractTypesToBounds(pt0) val ptparams = freeTypeParamsOfTerms(pt) val ctorTp = tree.tpe val resTp = ctorTp.finalResultType debuglog("infer constr inst "+ tree +"/"+ undetparams +"/ pt= "+ pt +" pt0= "+ pt0 +" resTp: "+ resTp) /* Compute type arguments for undetermined params */ def inferFor(pt: Type): Option[List[Type]] = { val tvars = undetparams map freshVar val resTpV = resTp.instantiateTypeParams(undetparams, tvars) if (resTpV <:< pt) { try { // debuglog("TVARS "+ (tvars map (_.constr))) // look at the argument types of the primary constructor corresponding to the pattern val variances = if (ctorTp.paramTypes.isEmpty) undetparams map varianceInType(ctorTp) else undetparams map varianceInTypes(ctorTp.paramTypes) // Note: this is the only place where solvedTypes (or, indirectly, solve) is called // with upper = true. val targs = solvedTypes(tvars, undetparams, variances, upper = true, lubDepth(resTp :: pt :: Nil)) // checkBounds(tree, NoPrefix, NoSymbol, undetparams, targs, "inferred ") // no checkBounds here. If we enable it, test bug602 fails. // TODO: reinstate checkBounds, return params that fail to meet their bounds to undetparams Some(targs) } catch ifNoInstance { msg => debuglog("NO INST "+ ((tvars, tvars map (_.constr)))) NoConstructorInstanceError(tree, resTp, pt, msg) None } } else { debuglog("not a subtype: "+ resTpV +" WildcardType))) flatMap { targs => val ctorTpInst = tree.tpe.instantiateTypeParams(undetparams, targs) val resTpInst = skipImplicit(ctorTpInst.finalResultType) val ptvars = ptparams map { // since instantiateTypeVar wants to modify the skolem that corresponds to the method's type parameter, // and it uses the TypeVar's origin to locate it, deskolemize the existential skolem to the method tparam skolem // (the existential skolem was created by adaptConstrPattern to introduce the type slack necessary to soundly deal with variant type parameters) case skolem if skolem.isGADTSkolem => freshVar(skolem.deSkolemize.asInstanceOf[TypeSymbol]) case p => freshVar(p) } val ptV = pt.instantiateTypeParams(ptparams, ptvars) if (isPopulated(resTpInst, ptV)) { ptvars foreach instantiateTypeVar debuglog("isPopulated "+ resTpInst +", "+ ptV +" vars= "+ ptvars) Some(targs) } else None } } else None inferFor(pt) orElse inferForApproxPt match { case Some(targs) => new TreeTypeSubstituter(undetparams, targs).traverse(tree) notifyUndetparamsInferred(undetparams, targs) case _ => def not = if (isFullyDefined(pt)) "" else "not " devWarning(s"failed inferConstructorInstance for $tree: ${tree.tpe} undet=$undetparams, pt=$pt (${not}fully defined)") ConstrInstantiationError(tree, resTp, pt) } } def instBounds(tvar: TypeVar): TypeBounds = { val tparam = tvar.origin.typeSymbol val instType = toOrigin(tvar.constr.inst) val TypeBounds(lo, hi) = tparam.info.bounds val (loBounds, hiBounds) = if (isFullyDefined(instType)) (List(instType), List(instType)) else (tvar.constr.loBounds, tvar.constr.hiBounds) TypeBounds( lub(lo :: loBounds map toOrigin), glb(hi :: hiBounds map toOrigin) ) } 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 (_ => Variance.Covariant), upper = false, Depth.AnyDepth) } // this is quite nasty: it destructively changes the info of the syms of e.g., method type params // (see #3692, where the type param T's bounds were set to > : T <: T, so that parts looped) // the changes are rolled back by restoreTypeBounds, but might be unintentionally observed in the mean time def instantiateTypeVar(tvar: TypeVar) { val tparam = tvar.origin.typeSymbol val TypeBounds(lo0, hi0) = tparam.info.bounds val tb @ TypeBounds(lo1, hi1) = instBounds(tvar) val enclCase = context.enclosingCaseDef def enclCase_s = enclCase.toString.replaceAll("\\n", " ").take(60) if (enclCase.savedTypeBounds.nonEmpty) log( sm"""|instantiateTypeVar with nonEmpty saved type bounds { | enclosing $enclCase_s | saved ${enclCase.savedTypeBounds} | tparam ${tparam.shortSymbolClass} ${tparam.defString} |}""") if (lo1 <:< hi1) { if (lo1 <:< lo0 && hi0 <:< hi1) // bounds unimproved log(s"redundant bounds: discarding TypeBounds($lo1, $hi1) for $tparam, no improvement on TypeBounds($lo0, $hi0)") else if (tparam == lo1.typeSymbolDirect || tparam == hi1.typeSymbolDirect) log(s"cyclical bounds: discarding TypeBounds($lo1, $hi1) for $tparam because $tparam appears as bounds") else { enclCase pushTypeBounds tparam tparam setInfo logResult(s"updated bounds: $tparam from ${tparam.info} to")(tb) } } else log(s"inconsistent bounds: discarding TypeBounds($lo1, $hi1)") } /** Type intersection of simple type tp1 with general type tp2. * 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 filterNot (tp1 <:< _), decls2) case _ => tp2 } intersectionType(List(tp1, reduced2)) } } def inferTypedPattern(tree0: Tree, pattp: Type, pt0: Type, canRemedy: Boolean): Type = { val pt = abstractTypesToBounds(pt0) val ptparams = freeTypeParamsOfTerms(pt) val tpparams = freeTypeParamsOfTerms(pattp) def ptMatchesPattp = pt matchesPattern pattp.widen def pattpMatchesPt = pattp matchesPattern pt /* If we can absolutely rule out a match we can fail early. * This is the case if the scrutinee has no unresolved type arguments * and is a "final type", meaning final + invariant in all type parameters. */ if (pt.isFinalType && ptparams.isEmpty && !ptMatchesPattp) { IncompatibleScrutineeTypeError(tree0, pattp, pt) return ErrorType } checkCheckable(tree0, pattp, pt, inPattern = true, canRemedy) if (pattp <:< pt) () else { debuglog("free type params (1) = " + tpparams) var tvars = tpparams map freshVar var tp = pattp.instantiateTypeParams(tpparams, tvars) if ((tp <:< pt) && isInstantiatable(tvars)) () else { tvars = tpparams map freshVar tp = pattp.instantiateTypeParams(tpparams, tvars) debuglog("free type params (2) = " + ptparams) val ptvars = ptparams map freshVar val pt1 = pt.instantiateTypeParams(ptparams, ptvars) // See ticket #2486 for an example of code which would incorrectly // fail if we didn't allow for pattpMatchesPt. if (isPopulated(tp, pt1) && isInstantiatable(tvars ++ ptvars) || pattpMatchesPt) ptvars foreach instantiateTypeVar else { PatternTypeIncompatibleWithPtError1(tree0, pattp, pt) return ErrorType } } tvars foreach instantiateTypeVar invalidateTreeTpeCaches(tree0, tvars.map(_.origin.typeSymbol)) } /* If the scrutinee has free type parameters but the pattern does not, * we have to flip the arguments so the expected type is treated as more * general when calculating the intersection. See run/bug2755.scala. */ if (tpparams.isEmpty && ptparams.nonEmpty) intersect(pattp, pt) else intersect(pt, pattp) } def inferModulePattern(pat: Tree, pt: Type) = if ((pat.symbol ne null) && pat.symbol.isModule && !(pat.tpe <:< pt)) { val ptparams = freeTypeParamsOfTerms(pt) debuglog("free type params (2) = " + ptparams) val ptvars = ptparams map freshVar val pt1 = pt.instantiateTypeParams(ptparams, ptvars) if (pat.tpe <:< pt1) ptvars foreach instantiateTypeVar else PatternTypeIncompatibleWithPtError2(pat, pt1, pt) } object toOrigin extends TypeMap { def apply(tp: Type): Type = tp match { case TypeVar(origin, _) => origin case _ => mapOver(tp) } } object approximateAbstracts extends TypeMap { def apply(tp: Type): Type = tp.dealiasWiden match { case TypeRef(pre, sym, _) if sym.isAbstractType => WildcardType case _ => mapOver(tp) } } /** Collects type parameters referred to in a type. */ def freeTypeParamsOfTerms(tp: Type): List[Symbol] = { // An inferred type which corresponds to an unknown type // constructor creates a file/declaration order-dependent crasher // situation, the behavior of which depends on the state at the // time the typevar is created. Until we can deal with these // properly, we can avoid it by ignoring type parameters which // have type constructors amongst their bounds. See SI-4070. def isFreeTypeParamOfTerm(sym: Symbol) = ( sym.isAbstractType && sym.owner.isTerm ) // Intentionally *not* using `Type#typeSymbol` here, which would normalize `tp` // and collect symbols from the result type of any resulting `PolyType`s, which // are not free type parameters of `tp`. // // Contrast with `isFreeTypeParamNoSkolem`. val syms = tp collect { case TypeRef(_, sym, _) if isFreeTypeParamOfTerm(sym) => sym } syms.distinct } /* -- Overload Resolution ---------------------------------------------- */ /** Assign `tree` the symbol and type of the alternative which * matches prototype `pt`, 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): Tree = { val c = context class InferTwice(pre: Type, alts: List[Symbol]) extends c.TryTwice { def tryOnce(isSecondTry: Boolean): Unit = { val alts0 = alts filter (alt => isWeaklyCompatible(pre memberType alt, pt)) val alts1 = if (alts0.isEmpty) alts else alts0 val bests = bestAlternatives(alts1) { (sym1, sym2) => val tp1 = pre memberType sym1 val tp2 = pre memberType sym2 ( (tp2 eq ErrorType) || isWeaklyCompatible(tp1, pt) && !isWeaklyCompatible(tp2, pt) || isStrictlyMoreSpecific(tp1, tp2, sym1, sym2) ) } // todo: missing test case for bests.isEmpty bests match { case best :: Nil => tree setSymbol best setType (pre memberType best) case best :: competing :: _ if alts0.nonEmpty => // SI-6912 Don't give up and leave an OverloadedType on the tree. // Originally I wrote this as `if (secondTry) ... `, but `tryTwice` won't attempt the second try // unless an error is issued. We're not issuing an error, in the assumption that it would be // spurious in light of the erroneous expected type if (pt.isErroneous) setError(tree) else AmbiguousExprAlternativeError(tree, pre, best, competing, pt, isSecondTry) case _ => if (bests.isEmpty || alts0.isEmpty) NoBestExprAlternativeError(tree, pt, isSecondTry) } } } tree.tpe match { case OverloadedType(pre, alts) => (new InferTwice(pre, alts)).apply() ; tree case _ => tree } } // Checks against the name of the parameter and also any @deprecatedName. private def paramMatchesName(param: Symbol, name: Name) = param.name == name || param.deprecatedParamName.exists(_ == name) private def containsNamedType(argtpes: List[Type]): Boolean = argtpes match { case Nil => false case NamedType(_, _) :: _ => true case _ :: rest => containsNamedType(rest) } private def namesOfNamedArguments(argtpes: List[Type]) = argtpes collect { case NamedType(name, _) => name } /** Given a list of argument types and eligible method overloads, whittle the * list down to the methods which should be considered for specificity * testing, taking into account here: * - named arguments at the call site (keep only methods with name-matching parameters) * - if multiple methods are eligible, drop any methods which take default arguments * - drop any where arity cannot match under any conditions (allowing for * overloaded applies, varargs, and tupling conversions) * This method is conservative; it can tolerate some varieties of false positive, * but no false negatives. * * @param eligible the overloaded method symbols * @param argtpes the argument types at the call site * @param varargsStar true if the call site has a `: _*` attached to the last argument */ private def overloadsToConsiderBySpecificity(eligible: List[Symbol], argtpes: List[Type], varargsStar: Boolean): List[Symbol] = { // TODO spec: this namesMatch business is not spec'ed, and is the wrong fix for SI-4592 // we should instead clarify what the spec means by "typing each argument with an undefined expected type". // What does typing a named argument entail when we don't know what the valid parameter names are? // (Since we're doing overload resolution, there are multiple alternatives that can define different names.) // Luckily, the next step checks applicability to the individual alternatives, so it knows whether an assignment is: // 1) a valid named argument // 2) a well-typed assignment // 3) an error (e.g., rhs does not refer to a variable) // // For now, the logic is: // If there are any foo=bar style arguments, and any of the overloaded // methods has a parameter named `foo`, then only those methods are considered when we must disambiguate. def namesMatch = namesOfNamedArguments(argtpes) match { case Nil => Nil case names => eligible filter (m => names forall (name => m.info.params exists (p => paramMatchesName(p, name)))) } if (eligible.isEmpty || eligible.tail.isEmpty) eligible else namesMatch match { case namesMatch if namesMatch.nonEmpty => namesMatch // TODO: this has no basis in the spec, remove! case _ => // If there are multiple applicable alternatives, drop those using default arguments. // This is done indirectly by checking applicability based on arity in `isApplicableBasedOnArity`. // If defaults are required in the application, the arities won't match up exactly. // TODO: should we really allow tupling here?? (If we don't, this is the only call-site with `tuplingAllowed = true`) eligible filter (alt => isApplicableBasedOnArity(alt.tpe, argtpes.length, varargsStar, tuplingAllowed = true)) } } /** Assign `tree` the type of an alternative which is applicable * to `argtpes`, 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 argtpes0 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. * * @pre tree.tpe is an OverloadedType. */ def inferMethodAlternative(tree: Tree, undetparams: List[Symbol], argtpes0: List[Type], pt0: Type): Unit = { // This potentially makes up to four attempts: tryOnce may execute // with and without views enabled, and bestForExpectedType will try again // with pt = WildcardType if it fails with pt != WildcardType. val c = context class InferMethodAlternativeTwice extends c.TryTwice { private[this] val OverloadedType(pre, alts) = tree.tpe private[this] var varargsStar = false private[this] val argtpes = argtpes0 mapConserve { case RepeatedType(tp) => varargsStar = true ; tp case tp => tp } private def followType(sym: Symbol) = followApply(pre memberType sym) // separate method to help the inliner private def isAltApplicable(pt: Type)(alt: Symbol) = context inSilentMode { isApplicable(undetparams, followType(alt), argtpes, pt) && !context.reporter.hasErrors } private def rankAlternatives(sym1: Symbol, sym2: Symbol) = isStrictlyMoreSpecific(followType(sym1), followType(sym2), sym1, sym2) private def bestForExpectedType(pt: Type, isLastTry: Boolean): Unit = { val applicable = overloadsToConsiderBySpecificity(alts filter isAltApplicable(pt), argtpes, varargsStar) val ranked = bestAlternatives(applicable)(rankAlternatives) ranked match { case best :: competing :: _ => AmbiguousMethodAlternativeError(tree, pre, best, competing, argtpes, pt, isLastTry) // ambiguous case best :: Nil => tree setSymbol best setType (pre memberType best) // success case Nil if pt.isWildcard => NoBestMethodAlternativeError(tree, argtpes, pt, isLastTry) // failed case Nil => bestForExpectedType(WildcardType, isLastTry) // failed, but retry with WildcardType } } private[this] val pt = if (pt0.typeSymbol == UnitClass) WildcardType else pt0 def tryOnce(isLastTry: Boolean): Unit = { debuglog(s"infer method alt ${tree.symbol} with alternatives ${alts map pre.memberType} argtpes=$argtpes pt=$pt") bestForExpectedType(pt, isLastTry) } } (new InferMethodAlternativeTwice).apply() } /** Assign `tree` the type of all polymorphic alternatives * which have the same number of type parameters as does `argtypes` * with all argtypes are within the corresponding type parameter bounds. * If no such polymorphic alternative exist, error. */ def inferPolyAlternatives(tree: Tree, argtypes: List[Type]): Unit = { val OverloadedType(pre, alts) = tree.tpe // Alternatives with a matching length type parameter list val matchingLength = tree.symbol filter (alt => sameLength(alt.typeParams, argtypes)) def allMonoAlts = alts forall (_.typeParams.isEmpty) def errorKind = matchingLength match { case NoSymbol if allMonoAlts => PolyAlternativeErrorKind.NoParams // no polymorphic method alternative case NoSymbol => PolyAlternativeErrorKind.WrongNumber // wrong number of tparams case _ => PolyAlternativeErrorKind.ArgsDoNotConform // didn't conform to bounds } def fail() = PolyAlternativeError(tree, argtypes, matchingLength, errorKind) def finish(sym: Symbol, tpe: Type) = tree setSymbol sym setType tpe // Alternatives which conform to bounds def checkWithinBounds(sym: Symbol) = sym.alternatives match { case Nil if argtypes.exists(_.isErroneous) => case Nil => fail() case alt :: Nil => finish(alt, pre memberType alt) case alts @ (hd :: _) => log(s"Attaching AntiPolyType-carrying overloaded type to $sym") // Multiple alternatives which are within bounds; spin up an // overloaded type which carries an "AntiPolyType" as a prefix. val tparams = new AsSeenFromMap(pre, hd.owner) mapOver hd.typeParams val bounds = tparams map (_.tpeHK) // see e.g., #1236 val tpe = PolyType(tparams, OverloadedType(AntiPolyType(pre, bounds), alts)) finish(sym setInfo tpe, tpe) } matchingLength.alternatives match { case Nil => fail() case alt :: Nil => finish(alt, pre memberType alt) case _ => checkWithinBounds(matchingLength filter (alt => isWithinBounds(pre, alt.owner, alt.typeParams, argtypes))) } } } }