*** empty log message ***

4 files changed, 927 insertions, 0 deletions

diff --git a/sources/scala/tools/nsc/typechecker/ConstantFolder.scala b/sources/scala/tools/nsc/typechecker/ConstantFolder.scala
new file mode 100755
index 0000000000..3971167d0c
--- /dev/null
+++ b/sources/scala/tools/nsc/typechecker/ConstantFolder.scala
@@ -0,0 +1,185 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id$
+package scala.tools.nsc.typechecker;
+
+abstract class ConstantFolder {
+
+  val global: Global;
+  import global._;
+  import definitions._;
+
+  private val NoValue = new Object();
+
+  /** If tree is a constant operation, replace with result. */
+  def apply(tree: Tree): Tree = {
+    val newvalue = tree match {
+      case Apply(Select(Literal(x), op), List(Literal(y))) => foldBinop(op, x, y)
+      case Select(Literal(x), op) => foldUnop(op, x)
+      case _ => NoValue
+    }
+    if (newvalue != NoValue) Literal(newvalue) else tree
+  }
+
+  /** If tree is a constant value that can be converted to type `pt', perform the conversion */
+  def apply(tree: Tree, pt: Type): Tree = {
+    val newvalue = tree match {
+      case Literal(value) => foldTyped(value, pt)
+      case _ => NoValue
+    }
+    if (newvalue != NoValue) Literal(newvalue) else tree
+  }
+
+  private def foldUnop(op: Name, value: Any): Any = Pair(op, value) match {
+    case Pair(nme.ZNOT, x: boolean) => !x
+
+    case Pair(nme.NOT , x: int    ) => ~x
+    case Pair(nme.NOT , x: long   ) => ~x
+
+    case Pair(nme.ADD , x: int    ) => +x
+    case Pair(nme.ADD , x: long   ) => +x
+    case Pair(nme.ADD , x: float  ) => +x
+    case Pair(nme.ADD , x: double ) => +x
+
+    case Pair(nme.SUB , x: int    ) => -x
+    case Pair(nme.SUB , x: long   ) => -x
+    case Pair(nme.SUB , x: float  ) => -x
+    case Pair(nme.SUB , x: double ) => -x
+
+    case _ => NoValue
+  }
+
+  private def foldBinop(op: Name, lvalue: Any, rvalue: Any): Any = Triple(op, lvalue, rvalue) match {
+    case Triple(nme.ZOR , x: boolean, y: boolean) => x | y
+    case Triple(nme.OR, , x: boolean, y: boolean) => x | y
+    case Triple(nme.OR  , x: int    , y: int    ) => x | y
+    case Triple(nme.OR  , x: long   , y: long   ) => x | y
+
+    case Triple(nme.XOR , x: boolean, y: boolean) => x ^ y
+    case Triple(nme.XOR , x: int    , y: int    ) => x ^ y
+    case Triple(nme.XOR , x: long   , y: long   ) => x ^ y
+
+    case Triple(nme.ZAND, x: boolean, y: boolean) => x & y
+    case Triple(nme.AND , x: boolean, y: boolean) => x & y
+    case Triple(nme.AND , x: int    , y: int    ) => x & y
+    case Triple(nme.AND , x: long   , y: long   ) => x & y
+
+    case Triple(nme.LSL , x: int    , y: int    ) => x << y
+    case Triple(nme.LSL , x: long   , y: int    ) => x << y
+    case Triple(nme.LSL , x: long   , y: long   ) => x << y
+
+    case Triple(nme.LSR , x: int    , y: int    ) => x >>> y
+    case Triple(nme.LSR , x: long   , y: int    ) => x >>> y
+    case Triple(nme.LSR , x: long   , y: long   ) => x >>> y
+
+    case Triple(nme.ASR , x: int    , y: int    ) => x >> y
+    case Triple(nme.ASR , x: long   , y: int    ) => x >> y
+    case Triple(nme.ASR , x: long   , y: long   ) => x >> y
+
+    case Triple(nme.EQ  , x: boolean, y: boolean) => x == y
+    case Triple(nme.EQ  , x: int    , y: int    ) => x == y
+    case Triple(nme.EQ  , x: long   , y: long   ) => x == y
+    case Triple(nme.EQ  , x: float  , y: float  ) => x == y
+    case Triple(nme.EQ  , x: double , y: double ) => x == y
+
+    case Triple(nme.NE  , x: boolean, y: boolean) => x != y
+    case Triple(nme.NE  , x: int    , y: int    ) => x != y
+    case Triple(nme.NE  , x: long   , y: long   ) => x != y
+    case Triple(nme.NE  , x: float  , y: float  ) => x != y
+    case Triple(nme.NE  , x: double , y: double ) => x != y
+
+    case Triple(nme.LT  , x: int    , y: int    ) => x < y
+    case Triple(nme.LT  , x: long   , y: long   ) => x < y
+    case Triple(nme.LT  , x: float  , y: float  ) => x < y
+    case Triple(nme.LT  , x: double , y: double ) => x < y
+
+    case Triple(nme.GT  , x: int    , y: int    ) => x > y
+    case Triple(nme.GT  , x: long   , y: long   ) => x > y
+    case Triple(nme.GT  , x: float  , y: float  ) => x > y
+    case Triple(nme.GT  , x: double , y: double ) => x > y
+
+    case Triple(nme.LE  , x: int    , y: int    ) => x <= y
+    case Triple(nme.LE  , x: long   , y: long   ) => x <= y
+    case Triple(nme.LE  , x: float  , y: float  ) => x <= y
+    case Triple(nme.LE  , x: double , y: double ) => x <= y
+
+    case Triple(nme.GE  , x: int    , y: int    ) => x >= y
+    case Triple(nme.GE  , x: long   , y: long   ) => x >= y
+    case Triple(nme.GE  , x: float  , y: float  ) => x >= y
+    case Triple(nme.GE  , x: double , y: double ) => x >= y
+
+    case Triple(nme.ADD , x: int    , y: int    ) => x + y
+    case Triple(nme.ADD , x: long   , y: long   ) => x + y
+    case Triple(nme.ADD , x: float  , y: float  ) => x + y
+    case Triple(nme.ADD , x: double , y: double ) => x + y
+    case Triple(nme.ADD , x: String , y: String ) => x + y
+
+    case Triple(nme.SUB , x: int    , y: int    ) => x - y
+    case Triple(nme.SUB , x: long   , y: long   ) => x - y
+    case Triple(nme.SUB , x: float  , y: float  ) => x - y
+    case Triple(nme.SUB , x: double , y: double ) => x - y
+
+    case Triple(nme.MUL , x: int    , y: int    ) => x * y
+    case Triple(nme.MUL , x: long   , y: long   ) => x * y
+    case Triple(nme.MUL , x: float  , y: float  ) => x * y
+    case Triple(nme.MUL , x: double , y: double ) => x * y
+
+    case Triple(nme.DIV , x: int    , y: int    ) => x / y
+    case Triple(nme.DIV , x: long   , y: long   ) => x / y
+    case Triple(nme.DIV , x: float  , y: float  ) => x / y
+    case Triple(nme.DIV , x: double , y: double ) => x / y
+
+    case Triple(nme.MOD , x: int    , y: int    ) => x % y
+    case Triple(nme.MOD , x: long   , y: long   ) => x % y
+    case Triple(nme.MOD , x: float  , y: float  ) => x % y
+    case Triple(nme.MOD , x: double , y: double ) => x % y
+
+    case _ => NoValue
+  }
+
+  /** Widen constant value to conform to given type */
+  private def foldTyped(value: Any, pt: Type): Any = {
+    val target = pt.symbol;
+    value match {
+      case x: byte =>
+	if (target == ShortClass) x.asInstanceOf[short]
+	else if (target == CharClass) x.asInstanceOf[char]
+	else if (target == IntClass) x.asInstanceOf[int]
+	else if (target == LongClass) x.asInstanceOf[long]
+	else if (target == FloatClass) x.asInstanceOf[float]
+	else if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x: short =>
+	if (target == IntClass) x.asInstanceOf[int]
+	else if (target == LongClass) x.asInstanceOf[long]
+	else if (target == FloatClass) x.asInstanceOf[float]
+	else if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x: char =>
+	if (target == IntClass) x.asInstanceOf[int]
+	else if (target == LongClass) x.asInstanceOf[long]
+	else if (target == FloatClass) x.asInstanceOf[float]
+	else if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x: int =>
+	if (target == ByteClass && -128 <= x && x <= 127) x.asInstanceOf[byte]
+	else if (target == ShortClass && -32768 <= x && x <= 32767) x.asInstanceOf[short]
+	else if (target == CharClass && 0 <= x && x <= 65535) x.asInstanceOf[char]
+	else if (target == LongClass) x.asInstanceOf[long]
+	else if (target == FloatClass) x.asInstanceOf[float]
+	else if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x: long =>
+	if (target == FloatClass) x.asInstanceOf[float]
+	else if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x: float =>
+	if (target == DoubleClass) x.asInstanceOf[double]
+	else NoValue
+      case x =>
+	NoValue
+    }
+  }
+}
diff --git a/sources/scala/tools/nsc/typechecker/EtaExpansion.scala b/sources/scala/tools/nsc/typechecker/EtaExpansion.scala
new file mode 100644
index 0000000000..4c8052563c
--- /dev/null
+++ b/sources/scala/tools/nsc/typechecker/EtaExpansion.scala
@@ -0,0 +1,70 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id$
+package scala.tools.nsc.typechecker;
+
+import collection.mutable.ListBuffer;
+import symtab.Flags._;
+
+class EtaExpansion: Analyzer {
+
+  import global._;
+  import posAssigner.atPos;
+
+  /** Expand partial function applications of type `type'.
+   *
+   *  p.f(es_1)...(es_n)
+   *     ==>  {
+   *            private synthetic val eta$f    = p.f   // if p is not stable
+   *            ...
+   *            private synthetic val eta$e_i = e_i    // if e_i is not stable
+   *             ...
+   *
+   *            (ps_1 => ... => ps_m => eta$f([es_1])...([es_m])(ps_1)...(ps_m))
+   *          }
+   *  tree is already attributed
+   */
+  def etaExpand(tree: Tree, tpe: Type): Tree = {
+    var cnt = 0;
+    def freshName() = { cnt = cnt + 1; newTermName("eta$" + cnt) }
+    val defs = new ListBuffer[Tree];
+
+    /** Append to `defs' value definitions for all non-stable subexpressions
+     *  of the function application `tree' */
+    def liftoutPrefix(tree: Tree): Tree = {
+      def liftout(tree: Tree): Tree =
+	if (treeInfo.isPureExpr(tree)) tree
+	else {
+	  val vname: Name = freshName();
+	  defs += ValDef(SYNTHETIC, vname, TypeTree(), tree);
+	  Ident(vname)
+	}
+      tree match {
+	case Apply(fn, args) =>
+          copy.Apply(tree, liftoutPrefix(fn), args mapConserve liftout);
+	case TypeApply(fn, args) =>
+          copy.TypeApply(tree, liftoutPrefix(fn), args)
+	case Select(qual, name) =>
+          copy.Select(tree, liftout(qual), name)
+        case Ident(name) =>
+          tree
+      }
+    }
+
+    /** Eta-expand lifted tree */
+    def expand(tree: Tree, tpe: Type): Tree = tpe match {
+      case MethodType(formals, restpe) =>
+        val params = formals map (formal =>
+          ValDef(SYNTHETIC | PARAM, freshName(), TypeTree().setType(formal), EmptyTree));
+        val args = params map (param => Ident(param.name));
+        Function(params, expand(Apply(tree, args), restpe))
+      case _ =>
+        tree
+    }
+
+    val tree1 = liftoutPrefix(tree);
+    atPos(tree.pos)(Block(defs.toList, expand(tree1, tpe)))
+  }
+}
diff --git a/sources/scala/tools/nsc/typechecker/Infer.scala b/sources/scala/tools/nsc/typechecker/Infer.scala
new file mode 100755
index 0000000000..513cb9cc31
--- /dev/null
+++ b/sources/scala/tools/nsc/typechecker/Infer.scala
@@ -0,0 +1,602 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id$
+package scala.tools.nsc.typechecker;
+
+class Infer: Analyzer {
+  import symtab.Flags._;
+  import global._;
+  import definitions._;
+  import posAssigner.atPos;
+  import scala.collection.mutable.ListBuffer;
+
+/* -- Type parameter inference utility functions -------------------------------------- */
+
+  /** The formal parameter types corresponding to `formals'.
+   *  If `formals' has a repeated last parameter, a list of
+   *  (nargs - params.length + 1) copies of its type is returned. */
+  def formalTypes(formals: List[Type], nargs: int): List[Type] =
+    if (!formals.isEmpty && (formals.last.symbol == RepeatedParamClass)) {
+      val ft = formals.last.typeArgs.head;
+      formals.init ::: (for (val i <- List.range(formals.length - 1, nargs)) yield ft)
+    } else formals;
+
+  /** A fresh type varable with given type parameter as origin. */
+  def freshVar(tparam: Symbol): TypeVar = new TypeVar(tparam.tpe, new TypeConstraint);
+
+  private class NoInstance(msg: String) extends RuntimeException(msg);
+
+  private class DeferredNoInstance(getmsg: () => String) extends NoInstance("") {
+    override def getMessage(): String = getmsg()
+  }
+
+  private object instantiateMap extends TypeMap {
+    def apply(t: Type): Type = instantiate(t)
+  }
+
+  /** map every TypeVar to its constraint.inst field.
+   *  throw a NoInstance exception if a NoType or WildcardType is encountered.
+   *  @throws   NoInstance
+   */
+  def instantiate(tp: Type): Type = tp match {
+    case WildcardType | NoType =>
+      throw new NoInstance("undetermined type");
+    case TypeVar(origin, constr) =>
+      if (constr.inst != NoType) instantiate(constr.inst)
+      else throw new DeferredNoInstance(() =>
+	"no unique instantiation of type variable " + origin + " could be found");
+    case _ =>
+      instantiateMap.mapOver(tp)
+  }
+
+  /** Is type fully defined, i.e. no embedded anytypes or wildcards in it? */
+  def isFullyDefined(tp: Type): boolean = try {
+    instantiate(tp); true
+  } catch {
+    case ex: NoInstance => false
+  }
+
+  /** Do type arguments `targs' conform to formal parameters `tparams'? */
+  private def isWithinBounds(tparams: List[Symbol], targs: List[Type]): boolean = {
+    val bounds = tparams map (.info.subst(tparams, targs).bounds);
+    List.map2(bounds, targs)((bound, targ) => bound containsType targ) forall (x => x)
+  }
+
+  /** 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
+   */
+  private def solve(tvars: List[TypeVar], tparams: List[Symbol], variances: List[int],
+		    upper: boolean): List[Type] = {
+    val config = tvars zip (tparams zip variances);
+
+    def solveOne(tvar: TypeVar, tparam: Symbol, variance: int): unit =
+      if (tvar.constr.inst == NoType) {
+	val up = if (variance != CONTRAVARIANT) upper else !upper;
+	tvar.constr.inst = null;
+	val bound: Type = if (up) tparam.info.bounds.hi else tparam.info.bounds.lo;
+	var cyclic = false;
+	for (val Pair(tvar2, Pair(tparam2, variance2)) <- config) {
+	  if ((bound contains tparam2) ||
+	      up && (tparam2.info.bounds.lo =:= tparam.tpe) ||
+	      !up && (tparam2.info.bounds.hi =:= tparam.tpe)) {
+	    if (tvar2.constr.inst == null) cyclic = true;
+	    solveOne(tvar2, tparam2, variance2);
+          }
+	}
+	if (!cyclic) {
+	  if (up) {
+	    if (bound.symbol != AnyClass) {
+	      tvar.constr.hibounds =
+		bound.subst(tparams, tvars) :: tvar.constr.hibounds;
+	      for (val tparam2 <- tparams)
+		if (tparam2.info.bounds.lo =:= tparam.tpe)
+		  tvar.constr.hibounds =
+		    tparam2.tpe.subst(tparams, tvars) :: tvar.constr.hibounds;
+	    }
+	  } else {
+	    if (bound.symbol != AllClass) {
+	      tvar.constr.lobounds =
+		bound.subst(tparams, tvars) :: tvar.constr.lobounds;
+	      for (val tparam2 <- tparams)
+		if (tparam2.info.bounds.hi =:= tparam.tpe)
+		  tvar.constr.lobounds =
+		    tparam2.tpe.subst(tparams, tvars) :: tvar.constr.lobounds;
+	    }
+	  }
+	  tvar.constr.inst = if (up) glb(tvar.constr.hibounds) else lub(tvar.constr.lobounds)
+	}
+      }
+
+    for (val Pair(tvar, Pair(tparam, variance)) <- config) solveOne(tvar, tparam, variance);
+    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.
+   */
+  private def normalize(tp: Type): Type = skipImplicit(tp) match {
+    case MethodType(formals, restpe) => functionType(formals, normalize(restpe))
+    case PolyType(List(), restpe) => normalize(restpe);
+    case _ => tp
+  }
+
+  class TreeSubstituter(tparams: List[Symbol], targs: List[Type]) extends Traverser {
+    val typeSubst = new SubstTypeMap(tparams, targs);
+    override def traverse(tree: Tree): unit = {
+      if (tree.tpe != null) tree.tpe = typeSubst(tree.tpe);
+      super.traverse(tree)
+    }
+  }
+
+  /** The context-dependent inferencer part */
+  class Inferencer(context: Context) {
+
+    /* -- Error Messages ----------------------------------------------------- */
+
+    def setError[T <: Tree](tree: T): T = {
+      val name = newTermName("<error: " + tree + ">");
+      if (tree.hasSymbol)
+	tree.setSymbol(
+	  if (tree.isType) context.owner.newErrorClass(name.toTypeName)
+	  else context.owner.newErrorValue(name));
+      tree.setType(ErrorType)
+    }
+
+    def decode(name: Name): String =
+      (if (name.isTypeName) "type " else "value ") + name.decode;
+
+    def treeSymTypeMsg(tree: Tree): String =
+      if (tree.symbol == 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.tpe.paramSectionCount > 0) "" else " of type ") +
+        tree.tpe;
+
+    def overloadErrorMsg(pre: Type, sym1: Symbol, sym2: Symbol): String =
+      "ambiguous reference to overloaded definition,\n" +
+      "both " + sym1 + ": " + pre.memberType(sym1) + "\n" +
+      "and  " + sym2 + ": " + pre.memberType(sym2) + "\nmatch";
+
+    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);
+
+    def foundReqMsg(found: Type, req: Type): String =
+      ";\n found   : " + found.toLongString + "\n required: " + req;
+
+    def error(pos: int, msg: String): unit =
+      context.unit.error(pos, msg);
+
+    def errorTree(tree: Tree, msg: String): Tree = {
+      error(tree.pos, msg);
+      setError(tree)
+    }
+
+    def typeError(pos: int, found: Type, req: Type): unit =
+      if (!found.isError && !req.isError) {
+	error(pos,
+          "type mismatch" + foundReqMsg(found, req) +
+   	  (if (!(found.resultType eq found) && isCompatible(found.resultType, req))
+	    "\n possible cause: missing arguments for method or constructor"
+	   else ""));
+	if (settings.explaintypes.value)
+	  explainTypes(found, req);
+      }
+
+    def typeErrorTree(tree: Tree, found: Type, req: Type): Tree = {
+      typeError(tree.pos, found, req);
+      setError(tree)
+    }
+
+    /* -- Views --------------------------------------------------------------- */
+
+    def availableViews(argtp: Type): List[Type] = List(); // for now
+    def bestView(argtp: Type, pt: Type): Symbol = NoSymbol; // for now
+    def bestView(argtp: Type, name: Name): Symbol = NoSymbol; // for now
+
+    object inferView extends Inferencer(context) {
+      override def availableViews(argtp: Type): List[Type] = List()
+    }
+
+    /* -- Tests & Checks-------------------------------------------------------- */
+
+    /** Is `sym' accessible as a member of tree `site' with type `pre' in current context?
+     */
+    private def isAccessible(sym: Symbol, pre: Type, site: Tree): boolean = {
+
+      /** Are we inside definition of `owner'? */
+      def accessWithin(owner: Symbol): boolean = {
+	var c = context;
+	while (c != NoContext && c.owner != owner) c = c.outer.enclClass;
+	c != NoContext;
+      }
+
+      /** Is `clazz' a subclass of an enclosing class? */
+      def isSubClassOfEnclosing(clazz: Symbol): boolean = {
+	var c = context;
+	while (c != NoContext && !clazz.isSubClass(c.owner)) c = c.outer.enclClass;
+	c != NoContext;
+      }
+
+      pre == NoPrefix
+      ||
+      (!sym.hasFlag(PRIVATE | PROTECTED))
+      ||
+      accessWithin(sym.owner)
+      ||
+      (!sym.hasFlag(PRIVATE) &&
+       (site.isInstanceOf[Super] ||
+	(pre.widen.symbol.isSubClass(sym.owner) && isSubClassOfEnclosing(pre.widen.symbol))))
+    }
+
+    /** Check that `sym' is defined and accessible as a member of tree `site' with type `pre'
+     *  in current context. */
+    def checkAccessible(tree: Tree, sym: Symbol, pre: Type, site: Tree): Tree =
+      if (sym.isError) {
+	tree setSymbol sym setType ErrorType
+      } else if (sym.owner.hasFlag(INCONSTRUCTOR) && !sym.isTypeParameter && site.isInstanceOf[This]) {
+	errorTree(tree, "" + sym + " cannot be accessed from constructor");
+      } else {
+	val sym1 = sym filter (alt => isAccessible(alt, pre, site));
+	if (sym1 == NoSymbol) {
+	  errorTree(tree, sym.toString() + " cannot be accessed in " + pre.widen)
+	} else {
+	  tree setSymbol sym1 setType pre.memberType(sym1)
+	}
+      }
+
+
+    def isCompatible(tp: Type, pt: Type): boolean = {
+      val tp1 = normalize(tp);
+      (tp1 <:< pt)/* ||
+      (availableViews(tp1) exists (view =>
+	inferView.isApplicable(List(), view.methtpe, List(tp1), pt)))*/
+    }
+
+    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 `pt'.
+     *  If no minimal type variables exist that make the
+     *  instantiated type a subtype of `pt', return null.
+     */
+    private def exprTypeArgs(tparams: List[Symbol], restpe: Type, pt: Type): List[Type] = {
+      val tvars = tparams map freshVar;
+      if (isCompatible(restpe.subst(tparams, tvars), pt)) {
+	try {
+	  solve(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 `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 covariant/contravariant,
+       *  to its upper/lower bound; */
+      def instantiateToBound(tvar: TypeVar, variance: int): Type = try {
+	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);
+	  instantiate(tvar.constr.inst)
+	} else if ((variance & CONTRAVARIANT) != 0 && !tvar.constr.lobounds.isEmpty) {
+	  tvar.constr.inst = lub(tvar.constr.lobounds);
+	  instantiate(tvar.constr.inst)
+	} else {
+	  WildcardType
+	}
+      } catch {
+	case ex: NoInstance => WildcardType
+      }
+      val tvars = tparams map freshVar;
+      if (isCompatible(restpe.subst(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 `NoInstance' 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 `restpe' are taken to be uninstantiated.
+    *                            Maps all those type arguments to their corresponding type
+    *                            parameters).
+    */
+    private 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 (!isCompatible(restpe.subst(tparams, tvars), pt)) {
+	throw new DeferredNoInstance(() =>
+	  "result type " + normalize(restpe) + " is incompatible with expected type " + pt)
+      }
+      for (val 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.subst(tparams, tvars),
+			  formal.subst(tparams, tvars))) {
+	  if (settings.explaintypes.value)
+	    explainTypes(argtpe.deconst.subst(tparams, tvars), formal.subst(tparams, tvars));
+	  throw new DeferredNoInstance(() =>
+	    "argument expression's type is not compatible with formal parameter type" +
+	    foundReqMsg(argtpe.deconst.subst(tparams, tvars), formal.subst(tparams, tvars)))
+	}
+	()
+      }
+      val targs = solve(tvars, tparams, tparams map varianceInTypes(formals), false);
+      List.map2(tparams, targs) ((tparam, targ) =>
+	if (targ.symbol == AllClass && (varianceInType(restpe)(tparam) & COVARIANT) == 0) {
+	  uninstantiated += tparam;
+	  tparam.tpe
+	} else targ)
+    }
+
+
+    /** Is there an instantiation of free type variables `undetparams' such that
+     *  function type `ftpe' is applicable to `argtpes' and its result conform to `pt'? */
+    def isApplicable(undetparams: List[Symbol], ftpe: Type, argtpes: List[Type], pt: Type): boolean =
+      ftpe match {
+	case MethodType(formals0, restpe) =>
+	  val formals = formalTypes(formals0, argtpes.length);
+	  if (undetparams.isEmpty) {
+	    formals.length == argtpes.length &&
+	    isCompatible(argtpes, formals) &&
+	    isCompatible(restpe, pt)
+	  } else {
+	    try {
+	      val uninstantiated = new ListBuffer[Symbol];
+	      val targs = methTypeArgs(undetparams, formals, restpe, argtpes, pt, uninstantiated);
+	      isWithinBounds(undetparams, targs) &&
+	      exprTypeArgs(uninstantiated.toList, restpe.subst(undetparams, targs), pt) != null
+	    } catch {
+	      case ex: NoInstance => false
+	    }
+	  }
+	case PolyType(tparams, restpe) =>
+	  val tparams1 = tparams map (.cloneSymbol);
+	  isApplicable(tparams1 ::: undetparams, restpe.substSym(tparams, tparams1), argtpes, pt)
+	case ErrorType =>
+	  true
+	case _ =>
+	  false
+      }
+
+    /** Does type `ftpe1' specialize type `ftpe2'
+     *  when both are alternatives in an overloaded function? */
+    def specializes(ftpe1: Type, ftpe2: Type): boolean = ftpe1 match {
+      case MethodType(formals, _) =>
+	isApplicable(List(), ftpe2, formals, WildcardType)
+      case PolyType(tparams, MethodType(formals, _)) =>
+	isApplicable(List(), ftpe2, formals, WildcardType)
+      case ErrorType =>
+	true
+      case _ =>
+	false
+    }
+
+    /** error if arguments not within bounds. */
+    def checkBounds(pos: int, tparams: List[Symbol], targs: List[Type], prefix: String): unit =
+      if (!isWithinBounds(tparams, targs)) {
+	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 (.info.subst(tparams, targs).bounds);
+          List.map2(targs, bounds)((targ, bound) => explainTypes(bound.lo, targ));
+          List.map2(targs, bounds)((targ, bound) => explainTypes(targ, bound.hi));
+          ()
+        }
+      }
+
+    /** 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 `AnyType'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): unit = {
+      var targs = exprTypeArgs(undetparams, tree.tpe, strictPt);
+      if (targs == null) targs = exprTypeArgs(undetparams, tree.tpe, lenientPt);
+      substExpr(tree, undetparams, targs, lenientPt)
+    }
+
+    /** Substitite free type variables `undetparams; of polymorphic expression `tree',
+     *  given prototype `pt'. */
+    def inferExprInstance(tree: Tree, undetparams: List[Symbol], pt: Type): unit =
+      substExpr(tree, undetparams, exprTypeArgs(undetparams, tree.tpe, pt), pt);
+
+    /** Substitite 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): unit =
+      if (targs == null) {
+	error(tree.pos, "polymorphic expression cannot be instantiated to expected type" +
+	      foundReqMsg(PolyType(undetparams, skipImplicit(tree.tpe)), pt));
+      } else {
+	checkBounds(tree.pos, undetparams, targs, "inferred ");
+	new TreeSubstituter(undetparams, targs).traverse(tree);
+      }
+
+    /** Substitite free type variables `undetparams' of application `fn(args)', given prototype `pt'.
+     *  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(formals, restpe) =>
+	try {
+	  val argtpes = args map (.tpe.deconst);
+	  val uninstantiated = new ListBuffer[Symbol];
+	  val targs = methTypeArgs(
+	    undetparams, formalTypes(formals, argtpes.length), restpe, argtpes, pt, uninstantiated);
+	  checkBounds(fn.pos, undetparams, targs, "inferred ");
+	  val treeSubst = new TreeSubstituter(undetparams, targs);
+	  treeSubst.traverse(fn);
+	  treeSubst.traverseTrees(args);
+	  uninstantiated.toList;
+	} catch {
+	  case ex: NoInstance =>
+	    errorTree(fn,
+	      "no type parameters for " +
+	      applyErrorMsg(
+		fn, " exist so that it can be applied to arguments ",
+		args map (.tpe.widen), WildcardType) +
+	      "\n --- because ---\n" + ex.getMessage());
+	    List()
+	}
+    }
+
+    /** Substitite free type variables `undetparams' of type constructor `tree' in pattern,
+     *  given prototype `pt'. */
+    def inferConstructorInstance(tree: Tree, undetparams: List[Symbol], pt: Type): unit = {
+      val tvars = undetparams map freshVar;
+      val restpe = skipImplicit(tree.tpe.resultType);
+      if (restpe.subst(undetparams, tvars) <:< pt)
+	try {
+	  val targs = solve(tvars, undetparams, undetparams map varianceInType(restpe), true);
+          checkBounds(tree.pos, undetparams, targs, "inferred ");
+	  new TreeSubstituter(undetparams, targs).traverse(tree)
+	} catch {
+	  case ex: NoInstance =>
+            errorTree(tree, "constructor of type " + restpe +
+		      " can be instantiated in more than one way to expected type " + pt +
+		      "\n --- because ---\n" + ex.getMessage());
+	}
+      else
+        errorTree(tree, "constructor cannot be instantiated to expected type" +
+                  foundReqMsg(restpe, pt))
+    }
+
+    /* -- 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.
+     *  Error if no or several such alternatives exist.
+     */
+    def inferExprAlternative(tree: Tree, pt: Type): unit = {
+      val pre = tree.symbol.info.prefix;
+      val alts = tree.symbol.alternatives filter (alt =>
+	isCompatible(pre.memberType(alt), pt));
+      def improves(sym1: Symbol, sym2: Symbol): boolean =
+	sym2 == NoSymbol ||
+	((sym1.owner isSubClass sym2.owner) &&
+	 {val tp1 = pre.memberType(sym1);
+	  val tp2 = pre.memberType(sym2);
+	  tp2 == ErrorType ||
+	  !inferView.isCompatible(tp2, pt) && inferView.isCompatible(tp1, pt) ||
+	  (tp2.paramSectionCount > 0) && (tp1.paramSectionCount == 0 || specializes(tp1, tp2))
+	});
+      val best = ((NoSymbol: Symbol) /: alts) ((best, alt) =>
+	if (improves(alt, best)) alt else best);
+      val competing = alts dropWhile (alt => best == alt || improves(best, alt));
+      if (best == NoSymbol) {
+	typeErrorTree(tree, tree.symbol.tpe, pt)
+      } else if (!competing.isEmpty) {
+	errorTree(tree, overloadErrorMsg(pre, best, competing.head) + "expected type " + pt)
+      } else {
+	tree.setSymbol(best).setType(pre.memberType(best))
+      }
+    }
+
+    /** 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, 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 = {
+      val pre = tree.symbol.info.prefix;
+      val alts = tree.symbol.alternatives filter (alt =>
+	isApplicable(undetparams, pre.memberType(alt), argtpes, pt));
+      def improves(sym1: Symbol, sym2: Symbol) = {
+	sym2 == NoSymbol ||
+	((sym1.owner isSubClass sym2.owner) &&
+	 specializes(pre.memberType(sym1), pre.memberType(sym2)))
+      }
+      val best = ((NoSymbol: Symbol) /: alts) ((best, alt) =>
+	if (improves(alt, best)) alt else best);
+      val competing = alts 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) {
+	errorTree(tree,
+          overloadErrorMsg(pre, best, competing.head) +
+	  "argument types " + argtpes.mkString("(", ",", ")") +
+	  (if (pt == WildcardType) "" else " and expected result type " + pt))
+      } else {
+	tree.setSymbol(best).setType(pre.memberType(best))
+      }
+    }
+
+    /** Assign `tree' the type of unique polymorphic alternative with `nparams'
+     *  as the number of type parameters, if it exists.
+     *  If several or none such polymorphic alternatives exist, error.
+     */
+    def inferPolyAlternative(tree: Tree, nparams: int): unit = {
+      val pre = tree.symbol.info.prefix;
+      val alts = tree.symbol.alternatives filter (alt =>
+	alt.info.typeParams.length == nparams);
+      if (alts.isEmpty) {
+	errorTree(tree,
+	  if (tree.symbol.alternatives exists (alt => alt.info.typeParams.length > 0))
+	    "wrong number of type parameters for " + treeSymTypeMsg(tree)
+	  else treeSymTypeMsg(tree) + " does not take type parameters")
+      } else if (!alts.tail.isEmpty) {
+	errorTree(tree,
+          overloadErrorMsg(pre, alts.head, alts.tail.head) +
+	  " polymorphic function with " + nparams + " parameters")
+      } else {
+	tree.setSymbol(alts.head).setType(pre.memberType(alts.head))
+      }
+    }
+  }
+}
diff --git a/sources/scala/tools/nsc/typechecker/Variances.scala b/sources/scala/tools/nsc/typechecker/Variances.scala
new file mode 100755
index 0000000000..10f40fca54
--- /dev/null
+++ b/sources/scala/tools/nsc/typechecker/Variances.scala
@@ -0,0 +1,70 @@
+/* NSC -- new scala compiler
+ * Copyright 2005 LAMP/EPFL
+ * @author  Martin Odersky
+ */
+// $Id$
+package scala.tools.nsc.typechecker;
+
+/** Variances form a lattice, 0 <= COVARIANT <= Variances, 0 <= CONTRAVARIANT <= Variances
+ */
+class Variances: Analyzer {
+
+  import global._;
+  import symtab.Flags._;
+
+  /** Flip between covariant and contravariant */
+  private def flip(v: int): int = {
+    if (v == COVARIANT) CONTRAVARIANT;
+    else if (v == CONTRAVARIANT) COVARIANT;
+    else v
+  }
+
+  /** Map everything below Variances to 0 */
+  private def cut(v: int): int =
+    if (v == Variances) v else 0;
+
+  /** Compute variance of type parameter `tparam' in types of all symbols `sym'. */
+  def varianceInSyms(syms: List[Symbol])(tparam: Symbol): int =
+    (Variances /: syms) ((v, sym) => v & varianceInSym(sym)(tparam));
+
+  /** Compute variance of type parameter `tparam' in type of symbol `sym'. */
+  def varianceInSym(sym: Symbol)(tparam: Symbol): int =
+    if (sym.isAliasType) cut(varianceInType(sym.info)(tparam))
+    else varianceInType(sym.info)(tparam);
+
+  /** Compute variance of type parameter `tparam' in all types `tps'. */
+  def varianceInTypes(tps: List[Type])(tparam: Symbol): int =
+    (Variances /: tps) ((v, tp) => v & varianceInType(tp)(tparam));
+
+  /** Compute variance of type parameter `tparam' in all type arguments
+   *  `tps' which correspond to formal type parameters `tparams'. */
+  def varianceInArgs(tps: List[Type], tparams: List[Symbol])(tparam: Symbol): int = {
+    var v: int = Variances;
+    for (val Pair(tp, tparam) <- tps zip tparams) {
+      val v1 = varianceInType(tp)(tparam);
+      v = v & (if (tparam.hasFlag(COVARIANT)) v1
+	       else if (tparam.hasFlag(CONTRAVARIANT)) flip(v1)
+	       else cut(v1))
+    }
+    v
+  }
+
+  /** Compute variance of type parameter `tparam' in type `tp'. */
+  def varianceInType(tp: Type)(tparam: Symbol): int = tp match {
+    case ErrorType | WildcardType | NoType | NoPrefix | ThisType(_) | ConstantType(_, _) =>
+      Variances
+    case SingleType(pre, sym) =>
+      cut(varianceInType(pre)(tparam))
+    case TypeRef(pre, sym, args) =>
+      if (sym == tparam) COVARIANT
+      else varianceInType(pre)(tparam) & varianceInArgs(args, sym.typeParams)(tparam)
+    case TypeBounds(lo, hi) =>
+      flip(varianceInType(lo)(tparam)) & varianceInType(hi)(tparam)
+    case RefinedType(parents, defs) =>
+      varianceInTypes(parents)(tparam) & varianceInSyms(defs.toList)(tparam)
+    case MethodType(formals, restpe) =>
+      flip(varianceInTypes(formals)(tparam)) & varianceInType(restpe)(tparam)
+    case PolyType(tparams, restpe) =>
+      flip(varianceInSyms(tparams)(tparam)) & varianceInType(restpe)(tparam)
+  }
+}