path: root/src/compiler/scala/tools/nsc/typechecker/Infer.scala

/* NSC -- new Scala compiler
 * Copyright 2005-2008 LAMP/EPFL
 * @author  Martin Odersky
 */
// $Id$

package scala.tools.nsc.typechecker
import scala.tools.nsc.util.{Position, NoPosition}
import scala.collection.mutable.ListBuffer
import symtab.Flags._

/** This trait ...
 *
 *  @author Martin Odersky
 *  @version 1.0
 */
trait Infer {
  self: Analyzer =>
  import global._
  import definitions._
  import posAssigner.atPos

  // statistics
  var normM = 0
  var normP = 0
  var normO = 0

  private final val inferInfo = false

/* -- Type parameter inference utility functions --------------------------- */

  private def assertNonCyclic(tvar: TypeVar) =
    assert(tvar.constr.inst != tvar, tvar.origin)

  def isVarArgs(formals: List[Type]) =
    !formals.isEmpty && (formals.last.typeSymbol == RepeatedParamClass)

  /** 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.
   *
   *  @param formals ...
   *  @param nargs ...
   */
  def formalTypes(formals: List[Type], nargs: Int): List[Type] = {
    val formals1 = formals map {
      case TypeRef(_, sym, List(arg)) if (sym == ByNameParamClass) => arg
      case formal => formal
    }
    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) List(atPos(pos)(gen.mkTuple(actuals))) else actuals

  /** A fresh type varable with given type parameter as origin.
   *
   *  @param tparam ...
   *  @return       ...
   */
  private def freshVar(tparam: Symbol): TypeVar =
    new TypeVar(tparam.tpe, new TypeConstraint)  //@M TODO: might be affected by change to tpe in Symbol

  //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)

  /*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
   */
  private def solvedTypes(tvars: List[TypeVar], tparams: List[Symbol],
                          variances: List[Int], upper: Boolean): 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)) {
//    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)
    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.
   *
   *  @param tp ...
   *  @return   ...
   */
  def normalize(tp: Type): Type = skipImplicit(tp) match {
    case MethodType(formals, restpe) if (!restpe.isDependent) =>
      if (util.Statistics.enabled) normM += 1
      functionType(formals, 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 --------------------------------------------------- */

    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) =
      "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 (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
     */
    private def withDisambiguation[T](tp1: Type, tp2: Type)(op: => T): T = {

      def explainName(sym: Symbol) = {
        if (!sym.name.toString.endsWith(")") && !inIDE) {
          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 && t1.toString == t2.toString
      } {
        val name = sym1.name
        explainName(sym1)
        explainName(sym2)
        if (sym1.owner == sym2.owner && !inIDE) sym2.name = newTypeName("(some other)"+sym2.name)
        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.
     *
     *  @param tree ...
     *  @param sym  ...
     *  @param pre  ...
     *  @param site ...
     *  @return     ...
     */
    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)

        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 = withoutMalformedChecks(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 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(formals, _) =>
        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(tp, pt)
    }

    def isWeaklyCompatible(tp: Type, pt: Type): Boolean =
      pt.typeSymbol == UnitClass || isCompatible(tp, pt)

    def isCoercible(tp: Type, pt: Type): Boolean = false

    def isCompatible(tps: List[Type], pts: List[Type]): Boolean =
      List.map2(tps, pts)((tp, pt) => isCompatible(tp, pt)) forall (x => x)

    /* -- Type instantiation------------------------------------------------ */

    /** 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 {
          solvedTypes(tvars, tparams, tparams map varianceInType(restpe), false)
        } 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 {
        //Console.println("instantiate "+tvar+tvar.constr+" variance = "+variance);//DEBUG
        if (tvar.constr.inst != NoType) {
          instantiate(tvar.constr.inst)
        } else if ((variance & COVARIANT) != 0 && !tvar.constr.hibounds.isEmpty) {
          tvar.constr.inst = glb(tvar.constr.hibounds)
          assertNonCyclic(tvar)//debug
          instantiate(tvar.constr.inst)
        } else if ((variance & CONTRAVARIANT) != 0 && !tvar.constr.lobounds.isEmpty) {
          tvar.constr.inst = lub(tvar.constr.lobounds)
          assertNonCyclic(tvar)//debug
          instantiate(tvar.constr.inst)
        } else if (!tvar.constr.hibounds.isEmpty && !tvar.constr.lobounds.isEmpty &&
                   glb(tvar.constr.hibounds) <:< lub(tvar.constr.lobounds)) {
          tvar.constr.inst = glb(tvar.constr.hibounds)
          assertNonCyclic(tvar)//debug
          instantiate(tvar.constr.inst)
        } else {
          WildcardType
        }
      } catch {
        case ex: NoInstance => WildcardType
      }
      val tvars = tparams map freshVar
      if (isWeaklyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt))
        List.map2(tparams, tvars) ((tparam, tvar) =>
          instantiateToBound(tvar, varianceInTypes(formals)(tparam)))
      else
        tvars map (tvar => WildcardType)
    }

    /** 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.AllClass.tpe'.
    *  No check that inferred parameters conform to their bounds is made here.
    *
    *  @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
    */
    // bq: was private, but need it for unapply checking
    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 (formals.length != argtpes.length) {
        throw new NoInstance("parameter lists differ in length")
      }
      // check first whether type variables can be fully defined from
      // expected result type.
      if (!isWeaklyCompatible(restpe.instantiateTypeParams(tparams, tvars), pt)) {
//      just wait and instantiate form 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) =>
        if (!isCompatible(argtpe.deconst.instantiateTypeParams(tparams, tvars),
                          formal.instantiateTypeParams(tparams, tvars))) {
          if (settings.explaintypes.value)
            explainTypes(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)))
        }
        ()
      }
      val targs = solvedTypes(tvars, tparams, tparams map varianceInTypes(formals), false)
//      val res =
      List.map2(tparams, targs) {(tparam, targ) =>
        if (targ.typeSymbol == AllClass && (varianceInType(restpe)(tparam) & COVARIANT) == 0) {
          uninstantiated += tparam
          tparam.tpe  //@M TODO: might be affected by change to tpe in Symbol
        } else if (targ.typeSymbol == RepeatedParamClass) {
          targ.baseType(SeqClass)
        } else {
          targ.widen
        }
      }
//      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
    }

    /** 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        ...
     *  @param argtpes     ...
     *  @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(formals0, _) =>
          val formals = formalTypes(formals0, argtpes0.length)
          val argtpes = actualTypes(argtpes0, formals.length)
          val restpe = ftpe.resultType(argtpes)
          if (undetparams.isEmpty) {
            (formals.length == argtpes.length &&
             isCompatible(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
            }
          }
        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 isMoreSpecific(ftpe1: Type, ftpe2: Type): Boolean = ftpe1 match {
      case OverloadedType(pre, alts) =>
        alts exists (alt => isMoreSpecific(pre.memberType(alt), ftpe2))
      case et: ExistentialType =>
        et.withTypeVars(isStrictlyMoreSpecific(_, ftpe2))
      case MethodType(formals @ (x :: xs), _) =>
        isApplicable(List(), ftpe2, formals, WildcardType)
      case PolyType(_, MethodType(formals @ (x :: xs), _)) =>
        isApplicable(List(), ftpe2, formals, WildcardType)
      case ErrorType =>
        true
      case _ =>
        ftpe2 match {
          case OverloadedType(pre, alts) =>
            alts forall (alt => isMoreSpecific(ftpe1, pre.memberType(alt)))
          case et: ExistentialType =>
            et.withTypeVars(isStrictlyMoreSpecific(ftpe1, _))
          case MethodType(_, _) | PolyType(_, MethodType(_, _)) =>
            true
          case _ =>
            isMoreSpecificValueType(ftpe1, ftpe2, List(), List())
        }
    }

    def isStrictlyMoreSpecific(ftpe1: Type, ftpe2: Type): Boolean =
      ftpe1.isError || isMoreSpecific(ftpe1, ftpe2) &&
      (!isMoreSpecific(ftpe2, ftpe1) ||
       !ftpe1.isInstanceOf[OverloadedType] && ftpe2.isInstanceOf[OverloadedType] ||
       phase.erasedTypes && covariantReturnOverride(ftpe1, ftpe2))

    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 isMoreSpecificValueType(tpe1: Type, tpe2: Type, undef1: List[Symbol], undef2: List[Symbol]): Boolean = (tpe1, tpe2) match {
      case (PolyType(tparams1, rtpe1), _) =>
        isMoreSpecificValueType(rtpe1, tpe2, undef1 ::: tparams1, undef2)
      case (_, PolyType(tparams2, rtpe2)) =>
        isMoreSpecificValueType(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 + "the 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))) {
          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)]) = {
// NOTE: 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 == AllClass) (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 {
        assert((a0 ne b0) && (a0.owner ne b0.owner));
        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) => //println("check: "+(tparam, targ))
        val (arityMismatches, varianceMismatches, stricterBounds) =
          checkKindBoundsHK(targ.typeParams, targ.typeSymbolDirect, tparam, tparam.owner) // NOTE: *not* targ.typeSymbol, which normalizes
            // NOTE 2: must use the typeParams of the type targ, not the typeParams of the symbol of targ!!

        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, undetparams: List[Symbol], pt: Type) {
      if (inferInfo)
        println("infer expr instance "+tree+"\n"+
                "  undetparams = "+undetparams+"\n"+
                "  pt = "+pt)
      substExpr(tree, undetparams, exprTypeArgs(undetparams, tree.tpe, pt), pt)
    }

    /** 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], pt: Type): List[Symbol] = fn.tpe match {
      case MethodType(formals0, _) =>
        if (inferInfo)
          println("infer method instance "+fn+"\n"+
                  "  undetparams = "+undetparams+"\n"+
                  "  args = "+args+"\n"+
                  "  pt = "+pt)
        try {
          val formals = formalTypes(formals0, 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 ")
          //Console.println("UNAPPLY subst type "+undetparams+" to "+targs+" in "+fn+" ( "+args+ ")")
          val treeSubst = new TreeTypeSubstituter(undetparams, targs)
          treeSubst.traverse(fn)
          treeSubst.traverseTrees(args)
          //Console.println("UNAPPLY gives "+fn+" ( "+args+ "), argtpes = "+argtpes+", pt = "+pt)
          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, List.mapConserve(parents)(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)
//          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 fuly defined: " + pt); instError }
    }

    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 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)
        if (!(lo <:< hi)) {
          if (settings.debug.value) log("inconsistent: "+tparam+" "+lo+" "+hi)
        } else 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)
        }
      }
    }

    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 == AllClass || sym == AllRefClass)
              error(pos, "this type cannot be used in a type pattern")
            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)) {
          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)) {
            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 TypeTraverser {
      private var result: List[Symbol] = _
      protected def includeCondition(sym: Symbol): Boolean

      override def traverse(tp: Type): TypeTraverser = {
        tp.normalize match {
          case TypeRef(_, sym, _) =>
            if (includeCondition(sym) && !result.contains(sym)) result = sym :: result
          case _ =>
        }
        mapOver(tp)
        this
      }

      /** Collect all abstract type symbols referred to by type <code>tp</code>.
       *
       *  @param tp ...
       *  @return   ...
       */
      def collect(tp: Type): List[Symbol] = {
        result = List()
        traverse(tp)
        result
      }
    }

    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
    }

    object typeRefs extends SymCollector {
      protected def includeCondition(sym: Symbol): Boolean = true
    }

    def checkDead(tree: Tree): Tree = {
      if (settings.Xwarndeadcode.value && tree.tpe.typeSymbol == AllClass)
        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 (alt.owner != best.owner && alt.owner.isSubClass(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))
        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)) }
        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, take 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.
     */
    def inferMethodAlternative(tree: Tree, undetparams: List[Symbol], argtpes: List[Type], pt: Type): Unit = tree.tpe match {
      case OverloadedType(pre, alts) =>
        tryTwice {
          if (settings.debug.value) log("infer method alt " + tree.symbol + " with alternatives " + (alts map pre.memberType) + ", argtpes = " + argtpes + ", pt = " + pt)
          val applicable = alts filter (alt => isApplicable(undetparams, followApply(pre.memberType(alt)), argtpes, pt))
          def improves(sym1: Symbol, sym2: Symbol) =
            sym2 == NoSymbol || sym2.isError ||
            isStrictlyMoreSpecific(followApply(pre.memberType(sym1)), followApply(pre.memberType(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))
        }
    }
  }
}