Eta expand $apply projected types if needed

It turns out that asSeenFrom can produce types
that get projected with $apply but that are not
higher-kinded. An exampple failure is in Iter3,
andother in scala.collection.immutable.Map (which is
now part of the test suite).

We now detect that situation, and eta expand the
projected type in `derivedSelect`, this will
force a subssequent `lookupRefined` which will give
the desired normalized type.

Also added is a configurable test that checks that
$apply projected tyeps are in fact higher-kinded.

7 files changed, 677 insertions, 16 deletions

diff --git a/src/dotty/tools/dotc/config/Config.scala b/src/dotty/tools/dotc/config/Config.scala
index 97893647c..d66d1ecdb 100644
--- a/src/dotty/tools/dotc/config/Config.scala
+++ b/src/dotty/tools/dotc/config/Config.scala
@@ -71,6 +71,11 @@ object Config {
   /** If this flag is set, take the fast path when comparing same-named type-aliases and types */
   final val fastPathForRefinedSubtype = true
 
+  /** If this flag is set, $apply projections are checked that they apply to a
+   *  higher-kinded type.
+   */
+  final val checkProjections = false
+
   /** When set, use new signature-based matching.
    *  Advantage of doing so: It's supposed to be faster
    *  Disadvantage: It might hide inconsistencies, so while debugging it's better to turn it off
diff --git a/src/dotty/tools/dotc/core/TypeApplications.scala b/src/dotty/tools/dotc/core/TypeApplications.scala
index d6cb3dc15..d7d205be6 100644
--- a/src/dotty/tools/dotc/core/TypeApplications.scala
+++ b/src/dotty/tools/dotc/core/TypeApplications.scala
@@ -155,6 +155,27 @@ class TypeApplications(val self: Type) extends AnyVal {
     case _ => false
   }
 
+  /** True if it can be determined without forcing that the class symbol
+   *  of this application exists and is not a lambda trait.
+   *  Equivalent to
+   *
+   *    self.classSymbol.exists && !self.classSymbol.isLambdaTrait
+   *
+   *  but without forcing anything.
+   */
+  def noHK(implicit ctx: Context): Boolean = self.stripTypeVar match {
+    case self: RefinedType =>
+      self.parent.noHK
+    case self: TypeRef =>
+      (self.denot.exists) && {
+        val sym = self.symbol
+        if (sym.isClass) !sym.isLambdaTrait
+        else sym.isCompleted && self.info.isAlias && self.info.bounds.hi.noHK
+      }
+    case _ =>
+      false
+  }
+
   /** Encode the type resulting from applying this type to given arguments */
   final def appliedTo(args: List[Type])(implicit ctx: Context): Type = /*>|>*/ track("appliedTo") /*<|<*/ {
     def matchParams(tp: Type, tparams: List[TypeSymbol], args: List[Type]): Type = args match {
@@ -510,6 +531,14 @@ class TypeApplications(val self: Type) extends AnyVal {
     if (bound.isHK && !isHK && self.typeSymbol.isClass && typeParams.nonEmpty) EtaExpand
     else self
 
+  /** Eta expand the prefix in front of any refinements. */
+  def EtaExpandCore(implicit ctx: Context): Type = self.stripTypeVar match {
+    case self: RefinedType =>
+      self.derivedRefinedType(self.parent.EtaExpandCore, self.refinedName, self.refinedInfo)
+    case _ =>
+      self.EtaExpand
+  }
+
   /** If `self` is a (potentially partially instantiated) eta expansion of type T, return T,
    *  otherwise NoType. More precisely if `self` is of the form
    *
diff --git a/src/dotty/tools/dotc/core/Types.scala b/src/dotty/tools/dotc/core/Types.scala
index 312d6b290..e545066af 100644
--- a/src/dotty/tools/dotc/core/Types.scala
+++ b/src/dotty/tools/dotc/core/Types.scala
@@ -1487,7 +1487,9 @@ object Types {
       if (prefix eq this.prefix) this
       else {
         val res = prefix.lookupRefined(name)
-        if (res.exists) res else newLikeThis(prefix)
+        if (res.exists) res
+        else if (name == tpnme.hkApply && prefix.noHK) derivedSelect(prefix.EtaExpandCore)
+        else newLikeThis(prefix)
       }
 
     /** Create a NamedType of the same kind as this type, but with a new prefix.
@@ -1725,9 +1727,15 @@ object Types {
   }
 
   object TypeRef {
+    def checkProjection(prefix: Type, name: TypeName)(implicit ctx: Context) =
+      if (name == tpnme.hkApply && prefix.noHK)
+        assert(false, s"bad type : $prefix.$name should not be $$applied")
+
     /** Create type ref with given prefix and name */
-    def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef =
+    def apply(prefix: Type, name: TypeName)(implicit ctx: Context): TypeRef = {
+      if (Config.checkProjections) checkProjection(prefix, name)
       ctx.uniqueNamedTypes.enterIfNew(prefix, name).asInstanceOf[TypeRef]
+    }
 
     /** Create type ref to given symbol */
     def apply(prefix: Type, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
@@ -1736,8 +1744,10 @@ object Types {
     /** Create a non-member type ref  (which cannot be reloaded using `member`),
      *  with given prefix, name, and symbol.
      */
-    def withFixedSym(prefix: Type, name: TypeName, sym: TypeSymbol)(implicit ctx: Context): TypeRef =
+    def withFixedSym(prefix: Type, name: TypeName, sym: TypeSymbol)(implicit ctx: Context): TypeRef = {
+      if (Config.checkProjections) checkProjection(prefix, name)
       unique(new TypeRefWithFixedSym(prefix, name, sym))
+    }
 
     /** Create a type ref referring to given symbol with given name.
      *  This is very similar to TypeRef(Type, Symbol),
@@ -3198,7 +3208,9 @@ object Types {
 
   class MissingType(pre: Type, name: Name)(implicit ctx: Context) extends TypeError(
     i"""cannot resolve reference to type $pre.$name
-       |the classfile defining the type might be missing from the classpath${otherReason(pre)}""".stripMargin)
+       |the classfile defining the type might be missing from the classpath${otherReason(pre)}""".stripMargin) {
+    printStackTrace()
+  }
 
   private def otherReason(pre: Type)(implicit ctx: Context): String = pre match {
     case pre: ThisType if pre.givenSelfType.exists =>
diff --git a/src/dotty/tools/dotc/typer/Checking.scala b/src/dotty/tools/dotc/typer/Checking.scala
index 3847cb5be..8376dd4e9 100644
--- a/src/dotty/tools/dotc/typer/Checking.scala
+++ b/src/dotty/tools/dotc/typer/Checking.scala
@@ -115,18 +115,8 @@ object Checking {
         val parent1 = this(parent)
         val saved = cycleOK
         cycleOK = nestedCycleOK
-
-        /** A derived refined type with two possible tweaks:
-         *  (1) LazyRefs in parents are pulled out,
-         *  (2) #Apply is added if the type is a fully applied type lambda.
-         */
-        def derivedType(p: Type): Type = p match {
-          case p: LazyRef => LazyRef(() => derivedType(p.ref))
-          case _ =>
-            val res = tp.derivedRefinedType(p, name, this(tp.refinedInfo))
-            if (res.isSafeLambda && res.typeParams.isEmpty) res.select(tpnme.Apply) else res
-        }
-        try derivedType(parent1) finally cycleOK = saved
+        try tp.derivedRefinedType(parent1, name, this(tp.refinedInfo))
+        finally cycleOK = saved
       case tp @ TypeRef(pre, name) =>
         try {
           // A prefix is interesting if it might contain (transitively) a reference
diff --git a/tests/pos/GenericTraversableTemplate.scala b/tests/pos/GenericTraversableTemplate.scala
new file mode 100644
index 000000000..cd48cd23f
--- /dev/null
+++ b/tests/pos/GenericTraversableTemplate.scala
@@ -0,0 +1,232 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+
+
+package scala
+package collection
+package generic
+
+import mutable.Builder
+import scala.annotation.migration
+import scala.annotation.unchecked.uncheckedVariance
+import scala.language.higherKinds
+
+/** A template class for companion objects of ``regular`` collection classes
+ *  that represent an unconstrained higher-kinded type.
+ *
+ *  @tparam  A    The type of the collection elements.
+ *  @tparam  CC   The type constructor representing the collection class.
+ *  @author Martin Odersky
+ *  @since 2.8
+ *  @define coll  collection
+ *  @define Coll  CC
+ */
+trait GenericTraversableTemplate[+A, +CC[X] <: GenTraversable[X]] extends HasNewBuilder[A, CC[A] @uncheckedVariance] {
+
+  /** Applies a function `f` to all elements of this $coll.
+   *
+   *  @param  f   the function that is applied for its side-effect to every element.
+   *              The result of function `f` is discarded.
+   *
+   *  @tparam  U  the type parameter describing the result of function `f`.
+   *              This result will always be ignored. Typically `U` is `Unit`,
+   *              but this is not necessary.
+   *
+   *  @usecase def foreach(f: A => Unit): Unit
+   */
+  def foreach[U](f: A => U): Unit
+
+  /** Selects the first element of this $coll.
+   *
+   *  @return  the first element of this $coll.
+   *  @throws `NoSuchElementException` if the $coll is empty.
+   */
+  def head: A
+
+  /** Tests whether this $coll is empty.
+   *
+   *  @return    `true` if the $coll contain no elements, `false` otherwise.
+   */
+  def isEmpty: Boolean
+
+  /** The factory companion object that builds instances of class $Coll.
+   *  (or its `Iterable` superclass where class $Coll is not a `Seq`.)
+   */
+  def companion: GenericCompanion[CC]
+
+  /** The builder that builds instances of type $Coll[A]
+   */
+  protected[this] def newBuilder: Builder[A, CC[A]] = companion.newBuilder[A]
+
+  /** The generic builder that builds instances of $Coll
+   *  at arbitrary element types.
+   */
+  def genericBuilder[B]: Builder[B, CC[B]] = companion.newBuilder[B]
+
+  private def sequential: TraversableOnce[A] = this.asInstanceOf[GenTraversableOnce[A]].seq
+
+  /** Converts this $coll of pairs into two collections of the first and second
+   *  half of each pair.
+   *
+   *    {{{
+   *    val xs = $Coll(
+   *               (1, "one"),
+   *               (2, "two"),
+   *               (3, "three")).unzip
+   *    // xs == ($Coll(1, 2, 3),
+   *    //        $Coll(one, two, three))
+   *    }}}
+   *
+   *  @tparam A1    the type of the first half of the element pairs
+   *  @tparam A2    the type of the second half of the element pairs
+   *  @param asPair an implicit conversion which asserts that the element type
+   *                of this $coll is a pair.
+   *  @return       a pair of ${coll}s, containing the first, respectively second
+   *                half of each element pair of this $coll.
+   */
+  def unzip[A1, A2](implicit asPair: A => (A1, A2)): (CC[A1], CC[A2]) = {
+    val b1 = genericBuilder[A1]
+    val b2 = genericBuilder[A2]
+    for (xy <- sequential) {
+      val (x, y) = asPair(xy)
+      b1 += x
+      b2 += y
+    }
+    (b1.result(), b2.result())
+  }
+
+  /** Converts this $coll of triples into three collections of the first, second,
+   *  and third element of each triple.
+   *
+   *    {{{
+   *    val xs = $Coll(
+   *               (1, "one", '1'),
+   *               (2, "two", '2'),
+   *               (3, "three", '3')).unzip3
+   *    // xs == ($Coll(1, 2, 3),
+   *    //        $Coll(one, two, three),
+   *    //        $Coll(1, 2, 3))
+   *    }}}
+   *
+   *  @tparam A1       the type of the first member of the element triples
+   *  @tparam A2       the type of the second member of the element triples
+   *  @tparam A3       the type of the third member of the element triples
+   *  @param asTriple  an implicit conversion which asserts that the element type
+   *                   of this $coll is a triple.
+   *  @return          a triple of ${coll}s, containing the first, second, respectively
+   *                   third member of each element triple of this $coll.
+   */
+  def unzip3[A1, A2, A3](implicit asTriple: A => (A1, A2, A3)): (CC[A1], CC[A2], CC[A3]) = {
+    val b1 = genericBuilder[A1]
+    val b2 = genericBuilder[A2]
+    val b3 = genericBuilder[A3]
+
+    for (xyz <- sequential) {
+      val (x, y, z) = asTriple(xyz)
+      b1 += x
+      b2 += y
+      b3 += z
+    }
+    (b1.result(), b2.result(), b3.result())
+  }
+
+  /** Converts this $coll of traversable collections into
+   *  a $coll formed by the elements of these traversable
+   *  collections.
+   *
+   *  @tparam B the type of the elements of each traversable collection.
+   *  @param asTraversable an implicit conversion which asserts that the element
+   *          type of this $coll is a `GenTraversable`.
+   *  @return a new $coll resulting from concatenating all element ${coll}s.
+   *
+   *  @usecase def flatten[B]: $Coll[B]
+   *
+   *    @inheritdoc
+   *
+   *    The resulting collection's type will be guided by the
+   *    static type of $coll. For example:
+   *
+   *    {{{
+   *    val xs = List(
+   *               Set(1, 2, 3),
+   *               Set(1, 2, 3)
+   *             ).flatten
+   *    // xs == List(1, 2, 3, 1, 2, 3)
+   *
+   *    val ys = Set(
+   *               List(1, 2, 3),
+   *               List(3, 2, 1)
+   *             ).flatten
+   *    // ys == Set(1, 2, 3)
+   *    }}}
+   */
+  def flatten[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]): CC[B] = {
+    val b = genericBuilder[B]
+    for (xs <- sequential)
+      b ++= asTraversable(xs).seq
+    b.result()
+  }
+
+  /** Transposes this $coll of traversable collections into
+   *  a $coll of ${coll}s.
+   *
+   *    The resulting collection's type will be guided by the
+   *    static type of $coll. For example:
+   *
+   *    {{{
+   *    val xs = List(
+   *               Set(1, 2, 3),
+   *               Set(4, 5, 6)).transpose
+   *    // xs == List(
+   *    //         List(1, 4),
+   *    //         List(2, 5),
+   *    //         List(3, 6))
+   *
+   *    val ys = Vector(
+   *               List(1, 2, 3),
+   *               List(4, 5, 6)).transpose
+   *    // ys == Vector(
+   *    //         Vector(1, 4),
+   *    //         Vector(2, 5),
+   *    //         Vector(3, 6))
+   *    }}}
+   *
+   *  @tparam B the type of the elements of each traversable collection.
+   *  @param  asTraversable an implicit conversion which asserts that the
+   *          element type of this $coll is a `Traversable`.
+   *  @return a two-dimensional $coll of ${coll}s which has as ''n''th row
+   *          the ''n''th column of this $coll.
+   *  @throws `IllegalArgumentException` if all collections in this $coll
+   *          are not of the same size.
+   */
+  @migration("`transpose` throws an `IllegalArgumentException` if collections are not uniformly sized.", "2.9.0")
+  def transpose[B](implicit asTraversable: A => /*<:<!!!*/ GenTraversableOnce[B]): CC[CC[B] @uncheckedVariance] = {
+    if (isEmpty)
+      return genericBuilder[CC[B]].result()
+
+    def fail = throw new IllegalArgumentException("transpose requires all collections have the same size")
+
+    val headSize = asTraversable(head).size
+    val bs: IndexedSeq[Builder[B, CC[B]]] = IndexedSeq.fill(headSize)(genericBuilder[B])
+    for (xs <- sequential) {
+      var i = 0
+      for (x <- asTraversable(xs)) {
+        if (i >= headSize) fail
+        bs(i) += x
+        i += 1
+      }
+      if (i != headSize)
+        fail
+    }
+    val bb = genericBuilder[CC[B]]
+    for (b <- bs) bb += b.result
+    bb.result()
+  }
+}
+
diff --git a/tests/pos/Iter3.scala b/tests/pos/Iter3.scala
new file mode 100644
index 000000000..d0ae79f1f
--- /dev/null
+++ b/tests/pos/Iter3.scala
@@ -0,0 +1,199 @@
+package dotty1.collections
+package immutable
+
+import annotation.unchecked.uncheckedVariance
+
+// Like Iter2, but with non-variant types only.
+object Iter2 {
+
+  trait Iterator[A] extends IterableOnce[A] {
+    def hasNext: Boolean
+    def next: A
+    def iterator = this
+    def foreach(f: A => Unit): Unit = ???
+    def map[B](f: A => B): Iterator[B] = ???
+    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = ???
+    def ++[B >: A](xs: IterableOnce[B]): Iterator[B] = ???
+    def drop(n: Int): Iterator[A] = ???
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next)) return i
+        i += 1
+      }
+      -1
+    }
+    def zip[B](that: Iterator[B]): Iterator[(A, B)] = ???
+  }
+
+  trait IterableOnce[A] {
+    def iterator: Iterator[A]
+    def buildIterator: Iterator[A] = iterator
+  }
+
+  trait FromIterator[C[X] <: Iterable[X]] {
+    def fromIterator[B](it: Iterator[B]): C[B]
+  }
+
+  trait Iterable[IA] extends IterableOnce[IA] with FromIterator[Iterable]
+
+  trait Seq[AA] extends Iterable[AA] with FromIterator[Seq] {
+    def apply(i: Int): AA
+    def length: Int
+  }
+
+  sealed trait List[A] extends Seq[A] with FromIterator[List] {
+    def isEmpty: Boolean
+    def head: A
+    def tail: List[A]
+    def iterator = new ListIterator[A](this)
+    def fromIterator[B](it: Iterator[B]): List[B] = it match {
+      case ListIterator(xs) => xs
+      case _ => if (it.hasNext) Cons(it.next, fromIterator(it)) else Nil.asInstanceOf[List[B]]
+    }
+    def apply(i: Int): A = {
+      require(!isEmpty)
+      if (i == 0) head else tail.apply(i - 1)
+    }
+    def length: Int =
+      if (isEmpty) 0 else 1 + tail.length
+  }
+
+  case class Cons[A](x: A, xs: List[A]) extends List[A] {
+    def isEmpty = false
+    def head = x
+    def tail = xs
+  }
+
+  case object Nil extends List[Nothing] {
+    def isEmpty = true
+    def head = ???
+    def tail = ???
+  }
+
+  class ArrayBuffer[A] private (initElems: Array[AnyRef], initLen: Int) extends Seq[A] with FromIterator[ArrayBuffer] {
+    def this() = this(new Array[AnyRef](16), 0)
+    def this(it: ArrayIterator[A]) = this(it.elems, it.len)
+    private var elems: Array[AnyRef] = initElems
+    private var len = 0
+    def iterator =
+      elems.iterator.take(len).asInstanceOf[Iterator[A]]
+    override def buildIterator =
+      new ArrayIterator(elems, len).asInstanceOf[Iterator[A]]
+    def fromIterator[B](it: Iterator[B]): ArrayBuffer[B] =
+      new ArrayBuffer(ArrayIterator.fromIterator(it))
+    def apply(i: Int) = elems(i).asInstanceOf[A]
+    def length = len
+  }
+
+  implicit class IterableTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] & FromIterator[C]) extends AnyVal {
+    def map[B](f: A => B): C[B] = c.fromIterator(c.buildIterator.map(f))
+    def flatMap[B](f: A => IterableOnce[B]): C[B] = c.fromIterator(c.buildIterator.flatMap(f(_).buildIterator))
+    def ++[B >: A](xs: IterableOnce[B]): C[B] = c.fromIterator(c.buildIterator ++ xs.buildIterator)
+    def drop(n: Int): C[A] = c.fromIterator(c.buildIterator.drop(n))
+    def head: A = c.iterator.next
+    def zip[B](xs: IterableOnce[B]): C[(A, B)] = c.fromIterator(c.iterator.zip(xs.iterator))
+  }
+
+  implicit class SeqTransforms[SA, C[X] <: Seq[X]](val c: Seq[SA] & FromIterator[C]) extends AnyVal {
+    def reverse: C[SA] = {
+      val elems = new Array[AnyRef](c.length)
+      var i = elems.length
+      val it = c.iterator
+      while (it.hasNext) {
+        i -= 1
+        elems(i) = it.next.asInstanceOf[AnyRef]
+      }
+      val xzz = c.fromIterator(ArrayIterator[SA](elems, c.length))
+      xzz
+    }
+    def indexWhere(p: SA => Boolean): Int = c.iterator.indexWhere(p)
+  }
+
+  case class ListIterator[A](xs: List[A]) extends Iterator[A] {
+    private[this] var current: List[A] = xs
+    def hasNext = !current.isEmpty
+    def next = { val res = current.head; current = current.tail; res }
+  }
+
+  case class ArrayIterator[A](elems: Array[AnyRef], len: Int) extends Iterator[A] {
+    import ArrayIterator._
+
+    private def elem(i: Int) = elems(i).asInstanceOf[A]
+
+    private var cur = 0
+
+    def hasNext = cur < len
+    def next = { val res = elem(cur); cur += 1; res }
+
+    override def foreach(f: A => Unit): Unit =
+      for (i <- 0 until len) f(elem(i))
+
+    override def map[B](f: A => B): ArrayIterator[B] = {
+      var mapped = elems
+      for (i <- 0 until len) {
+        val x = elem(i)
+        val y = widen(f(x))
+        if (widen(x) ne y) {
+          if (mapped eq elems) mapped = new Array[AnyRef](len)
+          mapped(i) = y
+        }
+      }
+      if (mapped eq elems) this.asInstanceOf[ArrayIterator[B]]
+      else new ArrayIterator(mapped, len)
+    }
+
+    override def flatMap[B](f: A => IterableOnce[B]): ArrayIterator[B] =
+      flatten(map(f(_).buildIterator))
+
+    override def ++[B >: A](that: IterableOnce[B]): ArrayIterator[B] = {
+      val thatIterator @ ArrayIterator(elems2, len2) = fromIterator(that.iterator)
+      if (len == 0) thatIterator
+      else if (len2 == 0) this.asInstanceOf[ArrayIterator[B]]
+      else {
+        val resLen = len + len2
+        val resElems = new Array[AnyRef](resLen)
+        Array.copy(elems, 0, resElems, 0, len)
+        Array.copy(elems2, 0, resElems, len, len2)
+        new ArrayIterator(resElems, resLen)
+      }
+    }
+  }
+
+  object ArrayIterator {
+    private def widen(x: Any): AnyRef = x.asInstanceOf[AnyRef]
+
+    def fromIterator[A](it: Iterator[A]): ArrayIterator[A] = it match {
+      case it: ArrayIterator[A] => it
+      case _ =>
+        var elems = new Array[AnyRef](32)
+        var len = 0
+        def ensureCapacity() = {
+          while (len > elems.length) {
+            val newElems = new Array[AnyRef](elems.length * 2)
+            Array.copy(elems, 0, newElems, 0, elems.length)
+            elems = newElems
+          }
+        }
+        while (it.hasNext) {
+          len += 1
+          ensureCapacity()
+          elems(len - 1) = widen(it.next)
+        }
+        ArrayIterator(elems, len)
+    }
+
+    def flatten[A](its: ArrayIterator[Iterator[A]]): ArrayIterator[A] = {
+      var arrayIts = its.map(fromIterator)
+      var totalLen = 0
+      arrayIts.foreach(totalLen += _.len)
+      val allElems = new Array[AnyRef](totalLen)
+      var j = 0
+      arrayIts.foreach { it =>
+        Array.copy(it.elems, 0, allElems, j, it.len)
+        j += it.len
+      }
+      new ArrayIterator(allElems, totalLen)
+    }
+  }
+}
diff --git a/tests/pos/Map.scala b/tests/pos/Map.scala
new file mode 100644
index 000000000..5178d5a86
--- /dev/null
+++ b/tests/pos/Map.scala
@@ -0,0 +1,194 @@
+/*                     __                                               *\
+**     ________ ___   / /  ___     Scala API                            **
+**    / __/ __// _ | / /  / _ |    (c) 2003-2013, LAMP/EPFL             **
+**  __\ \/ /__/ __ |/ /__/ __ |    http://scala-lang.org/               **
+** /____/\___/_/ |_/____/_/ | |                                         **
+**                          |/                                          **
+\*                                                                      */
+
+
+package scala
+package collection
+package immutable
+
+import generic._
+
+/**
+ * A generic trait for immutable maps. Concrete classes have to provide
+ * functionality for the abstract methods in `Map`:
+ *
+ * {{{
+ *    def get(key: A): Option[B]
+ *    def iterator: Iterator[(A, B)]
+ *    def + [B1 >: B](kv: (A, B1)): Map[A, B1]
+ *    def -(key: A): Map[A, B]
+ * }}}
+ *
+ * @since 1
+ */
+trait Map[A, +B] extends Iterable[(A, B)]
+//                    with GenMap[A, B]
+                    with scala.collection.Map[A, B]
+                    with MapLike[A, B, Map[A, B]] { self =>
+
+  override def empty: Map[A, B] = Map.empty
+
+  /** Returns this $coll as an immutable map.
+   *
+   *  A new map will not be built; lazy collections will stay lazy.
+   */
+  @deprecatedOverriding("Immutable maps should do nothing on toMap except return themselves cast as a map.",  "2.11.0")
+  override def toMap[T, U](implicit ev: (A, B) <:< (T, U)): immutable.Map[T, U] =
+    self.asInstanceOf[immutable.Map[T, U]]
+
+  override def seq: Map[A, B] = this
+
+  /** The same map with a given default function.
+   *  Note: `get`, `contains`, `iterator`, `keys`, etc are not affected by `withDefault`.
+   *
+   *  Invoking transformer methods (e.g. `map`) will not preserve the default value.
+   *
+   *  @param d     the function mapping keys to values, used for non-present keys
+   *  @return      a wrapper of the map with a default value
+   */
+  def withDefault[B1 >: B](d: A => B1): immutable.Map[A, B1] = new Map.WithDefault[A, B1](this, d)
+
+  /** The same map with a given default value.
+   *  Note: `get`, `contains`, `iterator`, `keys`, etc are not affected by `withDefaultValue`.
+   *
+   *  Invoking transformer methods (e.g. `map`) will not preserve the default value.
+   *
+   *  @param d     default value used for non-present keys
+   *  @return      a wrapper of the map with a default value
+   */
+  def withDefaultValue[B1 >: B](d: B1): immutable.Map[A, B1] = new Map.WithDefault[A, B1](this, x => d)
+
+  /** Add a key/value pair to this map.
+   *  @param    key the key
+   *  @param    value the value
+   *  @return   A new map with the new binding added to this map
+   */
+  override def updated [B1 >: B](key: A, value: B1): Map[A, B1]
+  def + [B1 >: B](kv: (A, B1)): Map[A, B1]
+}
+
+/** $factoryInfo
+ *  @define Coll `immutable.Map`
+ *  @define coll immutable map
+ */
+object Map extends ImmutableMapFactory[Map] {
+
+  /** $mapCanBuildFromInfo */
+  implicit def canBuildFrom[A, B]: CanBuildFrom[Coll, (A, B), Map[A, B]] = new MapCanBuildFrom[A, B]
+
+  def empty[A, B]: Map[A, B] = EmptyMap.asInstanceOf[Map[A, B]]
+
+  class WithDefault[A, +B](underlying: Map[A, B], d: A => B) extends scala.collection.Map.WithDefault[A, B](underlying, d) with Map[A, B] {
+    override def empty = new WithDefault(underlying.empty, d)
+    override def updated[B1 >: B](key: A, value: B1): WithDefault[A, B1] = new WithDefault[A, B1](underlying.updated[B1](key, value), d)
+    override def + [B1 >: B](kv: (A, B1)): WithDefault[A, B1] = updated(kv._1, kv._2)
+    override def - (key: A): WithDefault[A, B] = new WithDefault(underlying - key, d)
+    override def withDefault[B1 >: B](d: A => B1): immutable.Map[A, B1] = new WithDefault[A, B1](underlying, d)
+    override def withDefaultValue[B1 >: B](d: B1): immutable.Map[A, B1] = new WithDefault[A, B1](underlying, x => d)
+  }
+
+  private object EmptyMap extends AbstractMap[Any, Nothing] with Map[Any, Nothing] with Serializable {
+    override def size: Int = 0
+    def get(key: Any): Option[Nothing] = None
+    def iterator: Iterator[(Any, Nothing)] = Iterator.empty
+    override def updated [B1] (key: Any, value: B1): Map[Any, B1] = new Map1(key, value)
+    def + [B1](kv: (Any, B1)): Map[Any, B1] = updated(kv._1, kv._2)
+    def - (key: Any): Map[Any, Nothing] = this
+  }
+
+  class Map1[A, +B](key1: A, value1: B) extends AbstractMap[A, B] with Map[A, B] with Serializable {
+    override def size = 1
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1) else None
+    def iterator = Iterator((key1, value1))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1) new Map1(key1, value)
+      else new Map2(key1, value1, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1) Map.empty else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1))
+    }
+  }
+
+  class Map2[A, +B](key1: A, value1: B, key2: A, value2: B) extends AbstractMap[A, B] with Map[A, B] with Serializable {
+    override def size = 2
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else None
+    def iterator = Iterator((key1, value1), (key2, value2))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1) new Map2(key1, value, key2, value2)
+      else if (key == key2) new Map2(key1, value1, key2, value)
+      else new Map3(key1, value1, key2, value2, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1) new Map1(key2, value2)
+      else if (key == key2) new Map1(key1, value1)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2))
+    }
+  }
+
+  class Map3[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B) extends AbstractMap[A, B] with Map[A, B] with Serializable {
+    override def size = 3
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else if (key == key3) Some(value3)
+      else None
+    def iterator = Iterator((key1, value1), (key2, value2), (key3, value3))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1)      new Map3(key1, value, key2, value2, key3, value3)
+      else if (key == key2) new Map3(key1, value1, key2, value, key3, value3)
+      else if (key == key3) new Map3(key1, value1, key2, value2, key3, value)
+      else new Map4(key1, value1, key2, value2, key3, value3, key, value)
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1)      new Map2(key2, value2, key3, value3)
+      else if (key == key2) new Map2(key1, value1, key3, value3)
+      else if (key == key3) new Map2(key1, value1, key2, value2)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2)); f((key3, value3))
+    }
+  }
+
+  class Map4[A, +B](key1: A, value1: B, key2: A, value2: B, key3: A, value3: B, key4: A, value4: B) extends AbstractMap[A, B] with Map[A, B] with Serializable {
+    override def size = 4
+    def get(key: A): Option[B] =
+      if (key == key1) Some(value1)
+      else if (key == key2) Some(value2)
+      else if (key == key3) Some(value3)
+      else if (key == key4) Some(value4)
+      else None
+    def iterator = Iterator((key1, value1), (key2, value2), (key3, value3), (key4, value4))
+    override def updated [B1 >: B] (key: A, value: B1): Map[A, B1] =
+      if (key == key1)      new Map4(key1, value, key2, value2, key3, value3, key4, value4)
+      else if (key == key2) new Map4(key1, value1, key2, value, key3, value3, key4, value4)
+      else if (key == key3) new Map4(key1, value1, key2, value2, key3, value, key4, value4)
+      else if (key == key4) new Map4(key1, value1, key2, value2, key3, value3, key4, value)
+      else new HashMap + ((key1, value1), (key2, value2), (key3, value3), (key4, value4), (key, value))
+    def + [B1 >: B](kv: (A, B1)): Map[A, B1] = updated(kv._1, kv._2)
+    def - (key: A): Map[A, B] =
+      if (key == key1)      new Map3(key2, value2, key3, value3, key4, value4)
+      else if (key == key2) new Map3(key1, value1, key3, value3, key4, value4)
+      else if (key == key3) new Map3(key1, value1, key2, value2, key4, value4)
+      else if (key == key4) new Map3(key1, value1, key2, value2, key3, value3)
+      else this
+    override def foreach[U](f: ((A, B)) =>  U): Unit = {
+      f((key1, value1)); f((key2, value2)); f((key3, value3)); f((key4, value4))
+    }
+  }
+}
+
+/** Explicit instantiation of the `Map` trait to reduce class file size in subclasses. */
+abstract class AbstractMap[A, +B] extends scala.collection.AbstractMap[A, B] with Map[A, B]