infer.scala

JAVA 语言的函数式编程扩展

/* NSC -- new Scala compiler
 * Copyright 2005-2008 LAMP/EPFL
 * @author  Martin Odersky
 */
// $Id: Infer.scala 14561 2008-04-09 09:57:10Z odersky $

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)