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.

1 files changed, 199 insertions, 0 deletions

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)
+    }
+  }
+}