Backport of SI-6846.

Squashed commit of the following:

commit 55806cc0e6177820c12a35a18b4f2a12dc07bb39
Author: Paul Phillips <paulp@improving.org>
Date:   Wed Dec 19 07:32:19 2012 -0800

    SI-6846, regression in type constructor inference.

    In 658ba1b4e6 some inference was gained and some was lost.
    In this commit we regain what was lost and gain even more.
    Dealiasing and widening should be fully handled now, as
    illustrated by the test case.
    (cherry picked from commit dbebcd509e4013ce02655a2687b27d0967b3650e)

commit e6ef58447d0f4ef6de956fcc03ee283bb9028c02
Author: Paul Phillips <paulp@improving.org>
Date:   Fri Dec 21 15:11:29 2012 -0800

    Cleaning up type alias usage.

    I determined that many if not most of the calls to .normalize
    have no intent beyond dealiasing the type. In light of this I
    went call site to call site knocking on doors and asking why
    exactly they were calling any of

      .normalize
      .widen.normalize
      .normalize.widen

    and if I didn't like their answers they found themselves
    introduced to 'dropAliasesAndSingleTypes', the recursive widener
    and dealiaser which I concluded is necessary after all.

    Discovered that the object called 'deAlias' actually depends
    upon calling 'normalize', not 'dealias'. Decided this was
    sufficient cause to rename it to 'normalizeAliases'.

    Created dealiasWiden and dealiasWidenChain.

    Dropped dropAliasesAndSingleTypes in favor of methods
    on Type alongside dealias and widen (Type#dealiasWiden).
    These should reduce the number of "hey, the type alias doesn't work" bugs.

    (cherry picked from commit 3bf51189f979eb0dd41744ca844fd12dfdaa0dee)

    Conflicts:
    	src/compiler/scala/tools/nsc/interpreter/CompletionOutput.scala

commit c1d8803cea1523f458730103386d8e14324a9446
Author: Paul Phillips <paulp@improving.org>
Date:   Sat Dec 22 08:13:48 2012 -0800

    Shored up a hidden dealiasing dependency.

    Like the comment says:

    // This way typedNew always returns a dealiased type. This
    // used to happen by accident for instantiations without type
    // arguments due to ad hoc code in typedTypeConstructor, and
    // annotations depended on it (to the extent that they worked,
    // which they did not when given a parameterized type alias
    // which dealiased to an annotation.) typedTypeConstructor
    // dealiases nothing now, but it makes sense for a "new" to
    // always be given a dealiased type.

    PS:
    Simply running the test suite is becoming more difficult all
    the time. Running "ant test" includes time consuming activities
    of niche interest such as all the osgi tests, but test.suite
    manages to miss the continuations tests.
    (cherry picked from commit 422f461578ae0547181afe6d2c0c52ea1071d37b)

commit da4748502792b260161baa10939554564c488051
Author: Paul Phillips <paulp@improving.org>
Date:   Fri Dec 21 12:39:02 2012 -0800

    Fix and simplify typedTypeConstructor.

    Investigating the useful output of devWarning (-Xdev people,
    it's good for you) led back to this comment:

      "normalize to get rid of type aliases"

    You may know that this is not all the normalizing does.
    Normalizing also turns TypeRefs with unapplied arguments
    (type constructors) into PolyTypes. That means that when
    typedParentType would call typedTypeConstructor it would
    find its parent had morphed into a PolyType. Not that it
    noticed; it would blithely continue and unwittingly discard
    the type arguments by way of appliedType (which smoothly
    logged the incident, thank you appliedType.)

    The simplification of typedTypeConstructor:

    There was a whole complicated special treatment of AnyRef
    here which appears to have become unnecessary. Removed special
    treatment and lit a candle for regularity.

    Updated lots of tests regarding newly not-so-special AnyRef.
    (cherry picked from commit 394cc426c1ff1da53146679b4e2995ece52a133e)

commit 1f3c77bacb2fbb3ba9e4ad0a8a733e0f9263b234
Author: Paul Phillips <paulp@improving.org>
Date:   Fri Dec 21 15:06:10 2012 -0800

    Removed dead implementation.

    Another "attractive nuisance" burning off time until I
    realized it was commented out.
    (cherry picked from commit ed40f5cbdf35d09b02898e9c0950b9bd34c1f858)

1 files changed, 40 insertions, 20 deletions

diff --git a/src/reflect/scala/reflect/internal/Types.scala b/src/reflect/scala/reflect/internal/Types.scala
index bfd18f6a43..c2637e6967 100644
--- a/src/reflect/scala/reflect/internal/Types.scala
+++ b/src/reflect/scala/reflect/internal/Types.scala
@@ -593,6 +593,26 @@ trait Types extends api.Types { self: SymbolTable =>
     /** Expands type aliases. */
     def dealias = this
 
+    /** Repeatedly apply widen and dealias until they have no effect.
+     *  This compensates for the fact that type aliases can hide beneath
+     *  singleton types and singleton types can hide inside type aliases.
+     */
+    def dealiasWiden: Type = (
+      if (this ne widen) widen.dealiasWiden
+      else if (this ne dealias) dealias.dealiasWiden
+      else this
+    )
+
+    /** All the types encountered in the course of dealiasing/widening,
+     *  including each intermediate beta reduction step (whereas calling
+     *  dealias applies as many as possible.)
+     */
+    def dealiasWidenChain: List[Type] = this :: (
+      if (this ne widen) widen.dealiasWidenChain
+      else if (this ne betaReduce) betaReduce.dealiasWidenChain
+      else Nil
+    )
+
     def etaExpand: Type = this
 
     /** Performs a single step of beta-reduction on types.
@@ -3173,23 +3193,20 @@ trait Types extends api.Types { self: SymbolTable =>
        *  Checks subtyping of higher-order type vars, and uses variances as defined in the
        *  type parameter we're trying to infer (the result will be sanity-checked later).
        */
-      def unifyFull(tpe: Type) = {
-        // The alias/widen variations are often no-ops.
-        val tpes = (
-          if (isLowerBound) List(tpe, tpe.widen, tpe.dealias, tpe.widen.dealias).distinct
-          else List(tpe)
-        )
-        tpes exists { tp =>
-          val lhs = if (isLowerBound) tp.typeArgs else typeArgs
-          val rhs = if (isLowerBound) typeArgs else tp.typeArgs
-
-          sameLength(lhs, rhs) && {
+      def unifyFull(tpe: Type): Boolean = {
+        def unifySpecific(tp: Type) = {
+          sameLength(typeArgs, tp.typeArgs) && {
+            val lhs = if (isLowerBound) tp.typeArgs else typeArgs
+            val rhs = if (isLowerBound) typeArgs else tp.typeArgs
             // this is a higher-kinded type var with same arity as tp.
             // side effect: adds the type constructor itself as a bound
             addBound(tp.typeConstructor)
             isSubArgs(lhs, rhs, params, AnyDepth)
           }
         }
+        // The type with which we can successfully unify can be hidden
+        // behind singleton types and type aliases.
+        tpe.dealiasWidenChain exists unifySpecific
       }
 
       // There's a <: test taking place right now, where tp is a concrete type and this is a typevar
@@ -3282,7 +3299,7 @@ trait Types extends api.Types { self: SymbolTable =>
       if (constr.instValid) constr.inst
       // get here when checking higher-order subtyping of the typevar by itself
       // TODO: check whether this ever happens?
-      else if (isHigherKinded) typeFun(params, applyArgs(params map (_.typeConstructor)))
+      else if (isHigherKinded) logResult("Normalizing HK $this")(typeFun(params, applyArgs(params map (_.typeConstructor))))
       else super.normalize
     )
     override def typeSymbol = origin.typeSymbol
@@ -3754,7 +3771,7 @@ trait Types extends api.Types { self: SymbolTable =>
   def existentialAbstraction(tparams: List[Symbol], tpe0: Type): Type =
     if (tparams.isEmpty) tpe0
     else {
-      val tpe      = deAlias(tpe0)
+      val tpe      = normalizeAliases(tpe0)
       val tpe1     = new ExistentialExtrapolation(tparams) extrapolate tpe
       var tparams0 = tparams
       var tparams1 = tparams0 filter tpe1.contains
@@ -3768,13 +3785,16 @@ trait Types extends api.Types { self: SymbolTable =>
       newExistentialType(tparams1, tpe1)
     }
 
-  /** Remove any occurrences of type aliases from this type */
-  object deAlias extends TypeMap {
-    def apply(tp: Type): Type = mapOver {
-      tp match {
-        case TypeRef(pre, sym, args) if sym.isAliasType => tp.normalize
-        case _ => tp
-      }
+  /** Normalize any type aliases within this type (@see Type#normalize).
+   *  Note that this depends very much on the call to "normalize", not "dealias",
+   *  so it is no longer carries the too-stealthy name "deAlias".
+   */
+  object normalizeAliases extends TypeMap {
+    def apply(tp: Type): Type = tp match {
+      case TypeRef(_, sym, _) if sym.isAliasType =>
+        def msg = if (tp.isHigherKinded) s"Normalizing type alias function $tp" else s"Dealiasing type alias $tp"
+        mapOver(logResult(msg)(tp.normalize))
+      case _                                     => mapOver(tp)
     }
   }