Move compiler and compiler tests to compiler dir

4 files changed, 2513 insertions, 0 deletions

diff --git a/compiler/src/strawman/collections/CollectionStrawMan1.scala b/compiler/src/strawman/collections/CollectionStrawMan1.scala
new file mode 100644
index 000000000..c127757ad
--- /dev/null
+++ b/compiler/src/strawman/collections/CollectionStrawMan1.scala
@@ -0,0 +1,405 @@
+package strawman.collections
+
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+
+/** A strawman architecture for new collections. It contains some
+ *  example collection classes and methods with the intent to expose
+ *  some key issues. It would be good to compare this to other
+ *  implementations of the same functionality, to get an idea of the
+ *  strengths and weaknesses of different collection architectures.
+ *
+ *  For a test file, see tests/run/CollectionTests.scala.
+ */
+object CollectionStrawMan1 {
+
+  /* ------------ Base Traits -------------------------------- */
+
+  /** Replaces TraversableOnce */
+  trait CanIterate[+A] {
+    def iterator: Iterator[A]
+  }
+
+  /** Base trait for instances that can construct a collection from an iterator */
+  trait FromIterator[+C[X] <: Iterable[X]] {
+    def fromIterator[B](it: Iterator[B]): C[B]
+  }
+
+  /** Base trait for companion objects of collections */
+  trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterator[C] {
+    def empty[X]: C[X] = fromIterator(Iterator.empty)
+    def apply[A](xs: A*): C[A] = fromIterator(Iterator(xs: _*))
+  }
+
+  /** Base trait for generic collections */
+  trait Iterable[+A] extends CanIterate[A] with FromIterator[Iterable]
+
+  /** Base trait for sequence collections */
+  trait Seq[+A] extends Iterable[A] with FromIterator[Seq] {
+    def apply(i: Int): A
+    def length: Int
+  }
+
+  /* ------------ Operations ----------------------------------- */
+
+  /** Operations returning types unrelated to current collection */
+  trait Ops[A] extends Any {
+    def iterator: Iterator[A]
+    def foreach(f: A => Unit): Unit = iterator.foreach(f)
+    def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op)
+    def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op)
+    def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p)
+    def isEmpty: Boolean = !iterator.hasNext
+    def head: A = iterator.next
+    def view: View[A] = new View(iterator)
+    def to[C[X] <: Iterable[X]](fi: FromIterator[C]): C[A] = fi.fromIterator(iterator)
+  }
+
+  /** Transforms returning same collection type */
+  trait MonoTransforms[A, Repr] extends Any {
+    protected def iter: Iterator[A]
+    protected def fromIter(it: => Iterator[A]): Repr
+    def partition(p: A => Boolean): (Repr, Repr) = {
+      val (xs, ys) = iter.partition(p)
+      (fromIter(xs), fromIter(ys))
+    }
+    def drop(n: Int): Repr = fromIter(iter.drop(n))
+  }
+
+  /** Transforms returning same collection type constructor */
+  trait PolyTransforms[A, C[X]] extends Any {
+    protected def iter: Iterator[A]
+    protected def fromIter[B](it: => Iterator[B]): C[B]
+    def map[B](f: A => B): C[B] = fromIter(iter.map(f))
+    def flatMap[B](f: A => CanIterate[B]): C[B] = fromIter(iter.flatMap(f(_)))
+    def ++[B >: A](xs: CanIterate[B]): C[B] = fromIter(iter ++ xs)
+    def zip[B](xs: CanIterate[B]): C[(A, B)] = fromIter(iter.zip(xs.iterator))
+  }
+
+  /** Transforms that only apply to Seq */
+  trait MonoTransformsOfSeqs[A, Repr] extends Any with MonoTransforms[A, Repr] {
+    def reverse: Repr = fromIter(iter.reverse)
+  }
+
+  /** Implementation of Ops for all generic collections */
+  implicit class IterableOps[A](val c: Iterable[A])
+  extends AnyVal with Ops[A] {
+    def iterator = c.iterator
+  }
+
+  /** Implementation of MonoTransforms for all generic collections */
+  implicit class IterableMonoTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterator[C])
+  extends AnyVal with MonoTransforms[A, C[A]] {
+    protected def iter = c.iterator
+    protected def fromIter(it: => Iterator[A]): C[A] = c.fromIterator(it)
+  }
+
+  /** Implementation of PolyTransforms for all generic collections */
+  implicit class IterablePolyTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterator[C])
+  extends AnyVal with PolyTransforms[A, C] {
+    protected def iter = c.iterator
+    protected def fromIter[B](it: => Iterator[B]) = c.fromIterator(it)
+  }
+
+  /** Implementation of MonoTransformsForSeqs for all generic collections */
+  implicit class SeqMonoTransforms[A, C[X] <: Seq[X]](val c: Seq[A] with FromIterator[C])
+  extends AnyVal with MonoTransformsOfSeqs[A, C[A]] {
+    protected def iter = c.iterator
+    protected def fromIter(it: => Iterator[A]) = c.fromIterator(it)
+  }
+
+  /* --------- Concrete collection types ------------------------------- */
+
+  /** Concrete collection type: List */
+  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] = List.fromIterator(it)
+    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 = ???
+  }
+
+  object List extends IterableFactory[List] {
+    def fromIterator[B](it: Iterator[B]): List[B] = it match {
+      case it: ListIterator[B] => it.toList
+      case _ => if (it.hasNext) Cons(it.next, fromIterator(it)) else Nil
+    }
+  }
+
+  class ListIterator[+A](xs: List[A]) extends Iterator[A] {
+    private[this] var current = xs
+    def hasNext = !current.isEmpty
+    def next = { val r = current.head; current = current.tail; r }
+    def toList = current
+  }
+
+  /** Concrete collection type: ArrayBuffer */
+  class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int) extends Seq[A] with FromIterator[ArrayBuffer] {
+    def this() = this(new Array[AnyRef](16), 0)
+    private var elems: Array[AnyRef] = initElems
+    private var start = 0
+    private var limit = initLength
+    def apply(i: Int) = elems(start + i).asInstanceOf[A]
+    def length = limit - start
+    def iterator = new ArrayBufferIterator[A](elems, start, length)
+    def fromIterator[B](it: Iterator[B]): ArrayBuffer[B] =
+      ArrayBuffer.fromIterator(it)
+    def +=(elem: A): this.type = {
+      if (limit == elems.length) {
+        if (start > 0) {
+          Array.copy(elems, start, elems, 0, length)
+          limit -= start
+          start = 0
+        }
+        else {
+          val newelems = new Array[AnyRef](limit * 2)
+          Array.copy(elems, 0, newelems, 0, limit)
+          elems = newelems
+        }
+      }
+      elems(limit) = elem.asInstanceOf[AnyRef]
+      limit += 1
+      this
+    }
+    def trimStart(n: Int): Unit = start += (n max 0)
+    override def toString = s"ArrayBuffer(${elems.slice(start, limit).mkString(", ")})"
+  }
+
+  object ArrayBuffer extends IterableFactory[ArrayBuffer] {
+    def fromIterator[B](it: Iterator[B]): ArrayBuffer[B] = it match {
+      case Iterator.Concat(fst: ArrayBufferIterator[_], snd: ArrayBufferIterator[_]) =>
+        val elems = new Array[AnyRef](fst.remaining + snd.remaining)
+        Array.copy(fst.elems, fst.start, elems, 0, fst.remaining)
+        Array.copy(snd.elems, snd.start, elems, fst.remaining, snd.remaining)
+        new ArrayBuffer(elems, elems.length)
+      case it @ Iterator.Partition(underlying, _, buf, _) =>
+        while (underlying.hasNext) it.distribute()
+        buf.asInstanceOf[ArrayBuffer[B]]
+      case it if it.remaining >= 0 =>
+        val elems = new Array[AnyRef](it.remaining)
+        for (i <- 0 until elems.length) elems(i) = it.next.asInstanceOf[AnyRef]
+        new ArrayBuffer[B](elems, elems.length)
+      case _ =>
+        val buf = new ArrayBuffer[B]
+        while (it.hasNext) buf += it.next
+        buf
+    }
+  }
+
+  class ArrayBufferIterator[A](val elems: Array[AnyRef], initStart: Int, length: Int) extends RandomAccessIterator[A] {
+    val limit = length
+    def apply(n: Int) = elems(initStart + n).asInstanceOf[A]
+  }
+
+  /** Concrete collection type: View */
+  class View[+A](it: => Iterator[A]) extends CanIterate[A] {
+    def iterator = it
+  }
+
+  implicit class ViewOps[A](val v: View[A]) extends AnyVal with Ops[A] {
+    def iterator = v.iterator
+    def cache = to(ArrayBuffer).view
+  }
+
+  implicit class ViewMonoTransforms[A](val v: View[A])
+  extends AnyVal with MonoTransforms[A, View[A]] {
+    protected def iter = v.iterator
+    protected def fromIter(it: => Iterator[A]): View[A] = new View(it)
+  }
+
+  implicit class ViewPolyTransforms[A](val v: View[A])
+  extends AnyVal with PolyTransforms[A, View] {
+    protected def iter = v.iterator
+    protected def fromIter[B](it: => Iterator[B]) = new View(it)
+  }
+
+  /** Concrete collection type: String */
+  implicit class StringOps(val s: String) extends AnyVal with Ops[Char] {
+    def iterator: Iterator[Char] = new RandomAccessIterator[Char] {
+      override val limit = s.length
+      def apply(n: Int) = s.charAt(n)
+    }
+  }
+
+  implicit class StringMonoTransforms(val s: String)
+  extends AnyVal with MonoTransformsOfSeqs[Char, String] {
+    protected def iter = StringOps(s).iterator
+    protected def fromIter(it: => Iterator[Char]) = {
+      val sb = new StringBuilder
+      for (ch <- it) sb.append(ch)
+      sb.toString
+    }
+  }
+
+  implicit class StringPolyTransforms(val s: String)
+  extends AnyVal with PolyTransforms[Char, Seq] {
+    protected def iter = StringOps(s).iterator
+    protected def fromIter[B](it: => Iterator[B]) = List.fromIterator(it)
+    def map(f: Char => Char): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def flatMap(f: Char => String) = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def ++(xs: CanIterate[Char]): String = {
+      val sb = new StringBuilder(s)
+      for (ch <- xs.iterator) sb.append(ch)
+      sb.toString
+    }
+    def ++(xs: String): String = s + xs
+  }
+
+/* ---------- Iterators --------------------------------------------------- */
+
+  /** A core Iterator class */
+  trait Iterator[+A] extends CanIterate[A] { self =>
+    def hasNext: Boolean
+    def next: A
+    def iterator = this
+    def foldLeft[B](z: B)(op: (B, A) => B): B =
+      if (hasNext) foldLeft(op(z, next))(op) else z
+    def foldRight[B](z: B)(op: (A, B) => B): B =
+      if (hasNext) op(next, foldRight(z)(op)) else z
+    def foreach(f: A => Unit): Unit =
+      while (hasNext) f(next)
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next)) return i
+        i += 1
+      }
+      -1
+    }
+    def map[B](f: A => B): Iterator[B] = Iterator.Map(this, f)
+    def flatMap[B](f: A => CanIterate[B]): Iterator[B] = Iterator.FlatMap(this, f)
+    def ++[B >: A](xs: CanIterate[B]): Iterator[B] = Iterator.Concat(this, xs.iterator)
+    def partition(p: A => Boolean): (Iterator[A], Iterator[A]) = {
+      val lookaheadTrue, lookaheadFalse = new ArrayBuffer[A]
+      (Iterator.Partition(this, p, lookaheadTrue, lookaheadFalse),
+       Iterator.Partition[A](this, !p(_), lookaheadFalse, lookaheadTrue))
+    }
+    def drop(n: Int): Iterator[A] = Iterator.Drop(this, n)
+    def zip[B](that: CanIterate[B]): Iterator[(A, B)] = Iterator.Zip(this, that.iterator)
+    def reverse: Iterator[A] = {
+      var elems: List[A] = Nil
+      while (hasNext) elems = Cons(next, elems)
+      elems.iterator
+    }
+
+    /** If this iterator results from applying a transfomation to another iterator,
+     *  that other iterator, otherwise the iterator itself.
+     */
+    def underlying: Iterator[_] = this
+
+    /** If the number of elements still to be returned by this iterator is known,
+     *  that number, otherwise -1.
+     */
+    def remaining = -1
+  }
+
+  object Iterator {
+    val empty: Iterator[Nothing] = new Iterator[Nothing] {
+      def hasNext = false
+      def next = ???
+      override def remaining = 0
+    }
+    def apply[A](xs: A*): Iterator[A] = new RandomAccessIterator[A] {
+      override val limit = xs.length
+      def apply(n: Int) = xs(n)
+    }
+    def nextOnEmpty = throw new NoSuchElementException("next on empty iterator")
+
+    case class Map[A, B](override val underlying: Iterator[A], f: A => B) extends Iterator[B] {
+      def hasNext = underlying.hasNext
+      def next = f(underlying.next)
+      override def remaining = underlying.remaining
+    }
+    case class FlatMap[A, B](override val underlying: Iterator[A], f: A => CanIterate[B]) extends Iterator[B] {
+      private var myCurrent: Iterator[B] = Iterator.empty
+      private def current = {
+        while (!myCurrent.hasNext && underlying.hasNext)
+          myCurrent = f(underlying.next).iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next = current.next
+    }
+    case class Concat[A](override val underlying: Iterator[A], other: Iterator[A]) extends Iterator[A] {
+      private var myCurrent = underlying
+      private def current = {
+        if (!myCurrent.hasNext && myCurrent.eq(underlying)) myCurrent = other
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next = current.next
+      override def remaining =
+        if (underlying.remaining >= 0 && other.remaining >= 0)
+          underlying.remaining + other.remaining
+        else -1
+    }
+    case class Partition[A](override val underlying: Iterator[A], p: A => Boolean, lookahead: ArrayBuffer[A], dual: ArrayBuffer[A]) extends Iterator[A] {
+      def distribute() = {
+        val elem = underlying.next
+        (if (p(elem)) lookahead else dual) += elem
+      }
+      final def hasNext: Boolean =
+        !lookahead.isEmpty || underlying.hasNext && { distribute(); hasNext }
+      final def next =
+        if (hasNext) {
+          val r = lookahead.head
+          lookahead.trimStart(1)
+          r
+        } else Iterator.nextOnEmpty
+    }
+    case class Drop[A](override val underlying: Iterator[A], n: Int) extends Iterator[A] {
+      var toSkip = n
+      def hasNext: Boolean = underlying.hasNext && (
+        toSkip == 0 || { underlying.next; toSkip -= 1; hasNext })
+      def next = if (hasNext) underlying.next else nextOnEmpty
+      override def remaining = (underlying.remaining - toSkip) max -1
+    }
+    case class Zip[A, B](override val underlying: Iterator[A], other: Iterator[B]) extends Iterator[(A, B)] {
+      def hasNext = underlying.hasNext && other.hasNext
+      def next = (underlying.next, other.next)
+      override def remaining = underlying.remaining min other.remaining
+    }
+    case class Reverse[A](override val underlying: RandomAccessIterator[A]) extends RandomAccessIterator[A] {
+      def apply(n: Int) = underlying.apply(underlying.limit - 1 - n)
+      def limit = underlying.remaining
+    }
+  }
+
+  trait RandomAccessIterator[+A] extends Iterator[A] { self =>
+    def apply(n: Int): A
+    def limit: Int
+    var start = 0
+    override def remaining = (limit - start) max 0
+    def hasNext = start < limit
+    def next: A = { val r = this(start); start += 1; r }
+    override def drop(n: Int): Iterator[A] = { start += (n max 0); this }
+    override def reverse: Iterator[A] = new Iterator.Reverse(this)
+  }
+}
+
diff --git a/compiler/src/strawman/collections/CollectionStrawMan4.scala b/compiler/src/strawman/collections/CollectionStrawMan4.scala
new file mode 100644
index 000000000..7e8de2c82
--- /dev/null
+++ b/compiler/src/strawman/collections/CollectionStrawMan4.scala
@@ -0,0 +1,541 @@
+package strawman.collections
+
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+import annotation.unchecked.uncheckedVariance
+import annotation.tailrec
+
+/** A strawman architecture for new collections. It contains some
+ *  example collection classes and methods with the intent to expose
+ *  some key issues. It would be good to compare this to other
+ *  implementations of the same functionality, to get an idea of the
+ *  strengths and weaknesses of different collection architectures.
+ *
+ *  For a test file, see tests/run/CollectionTests.scala.
+ *
+ *  Strawman4 is like strawman1, but built over views instead of by-name iterators
+ */
+object CollectionStrawMan4 {
+
+  /* ------------ Base Traits -------------------------------- */
+
+  /** Iterator can be used only once */
+  trait IterableOnce[+A] {
+    def iterator: Iterator[A]
+  }
+
+  /** Base trait for instances that can construct a collection from an iterable */
+  trait FromIterable[+C[X] <: Iterable[X]] {
+    def fromIterable[B](v: Iterable[B]): C[B]
+  }
+
+  /** Base trait for companion objects of collections */
+  trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] {
+    def empty[X]: C[X] = fromIterable(View.Empty)
+    def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*))
+  }
+
+  /** Base trait for generic collections */
+  trait Iterable[+A] extends IterableOnce[A] with FromIterable[Iterable] {
+    def view: View[A] = View.fromIterator(iterator) // view is overridden, cannot be defined in ops
+    def knownLength: Int = -1
+  }
+
+  /** Base trait for sequence collections */
+  trait Seq[+A] extends Iterable[A] with FromIterable[Seq] {
+    def apply(i: Int): A
+    def length: Int
+  }
+
+  /** Base trait for collection builders */
+  trait Builder[-A, +To] {
+    def +=(x: A): this.type
+    def result: To
+
+    def ++=(xs: IterableOnce[A]): this.type = {
+      xs.iterator.foreach(+=)
+      this
+    }
+  }
+
+  /* ------------ Operations ----------------------------------- */
+
+  /** Operations returning types unrelated to current collection */
+  trait Ops[A] extends Any {
+    def iterator: Iterator[A]
+    def foreach(f: A => Unit): Unit = iterator.foreach(f)
+    def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op)
+    def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op)
+    def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p)
+    def isEmpty: Boolean = !iterator.hasNext
+    def head: A = iterator.next
+  }
+
+  /** Transforms returning same collection type */
+  trait MonoTransforms[A, Repr] extends Any {
+    protected def coll: Iterable[A]
+    protected def fromIterable(it: Iterable[A]): Repr
+    def filter(p: A => Boolean): Repr = fromIterable(View.Filter(coll, p))
+    def partition(p: A => Boolean): (Repr, Repr) = {
+      val pn = View.Partition(coll, p)
+      (fromIterable(pn.left), fromIterable(pn.right))
+    }
+    def drop(n: Int): Repr = fromIterable(View.Drop(coll, n))
+    def to[C[X] <: Iterable[X]](fv: FromIterable[C]): C[A] = fv.fromIterable(coll)
+  }
+
+  trait PolyTransforms[A, C[X]] extends Any {
+    protected def coll: Iterable[A]
+    protected def fromIterable[B](it: Iterable[B]): C[B]
+    def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))
+    def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f))
+    def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs))
+    def zip[B](xs: IterableOnce[B]): C[(A, B)] = fromIterable(View.Zip(coll, xs))
+  }
+
+  /** Transforms that only apply to Seq */
+  trait MonoTransformsOfSeqs[A, Repr] extends Any with MonoTransforms[A, Repr] {
+    def reverse: Repr = fromIterable(View.Reverse(coll))
+  }
+
+  /** Implementation of Ops for all generic collections */
+  implicit class IterableOps[A](val c: Iterable[A])
+  extends AnyVal with Ops[A] {
+    def iterator = c.iterator
+  }
+
+  /** Implementation of MonoTransforms for all generic collections */
+  implicit class IterableMonoTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterable[C])
+  extends AnyVal with MonoTransforms[A, C[A]] {
+    protected def coll = c
+    protected def fromIterable(it: Iterable[A]): C[A] = c.fromIterable(it)
+  }
+
+  /** Implementation of PolyTransforms for all generic collections */
+  implicit class IterablePolyTransforms[A, C[X] <: Iterable[X]](val c: Iterable[A] with FromIterable[C])
+  extends AnyVal with PolyTransforms[A, C] {
+    protected def coll = c
+    protected def fromIterable[B](it: Iterable[B]): C[B] = c.fromIterable(it)
+  }
+
+  /** Implementation of MonoTransformsForSeqs for all generic collections */
+  implicit class SeqMonoTransforms[A, C[X] <: Seq[X]](val c: Seq[A] with FromIterable[C])
+  extends AnyVal with MonoTransformsOfSeqs[A, C[A]] {
+    protected def coll = c
+    protected def fromIterable(it: Iterable[A]): C[A] = c.fromIterable(it)
+  }
+
+  /* --------- Concrete collection types ------------------------------- */
+
+  /** Concrete collection type: List */
+  sealed trait List[+A] extends Seq[A] with FromIterable[List] { self =>
+    def isEmpty: Boolean
+    def head: A
+    def tail: List[A]
+    def iterator = new Iterator[A] {
+      private[this] var current = self
+      def hasNext = !current.isEmpty
+      def next = { val r = current.head; current = current.tail; r }
+    }
+    def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c)
+    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
+    def ++:[B >: A](prefix: List[B]): List[B] =
+      if (prefix.isEmpty) this
+      else Cons(prefix.head, prefix.tail ++: this)
+  }
+
+  case class Cons[+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally
+  extends List[A] {
+    def isEmpty = false
+    def head = x
+    def tail = next
+  }
+
+  case object Nil extends List[Nothing] {
+    def isEmpty = true
+    def head = ???
+    def tail = ???
+  }
+
+  object List extends IterableFactory[List] {
+    def fromIterator[B](it: Iterator[B]): List[B] =
+      if (it.hasNext) Cons(it.next, fromIterator(it)) else Nil
+    def fromIterable[B](c: Iterable[B]): List[B] = c match {
+      case View.Concat(xs, ys: List[B]) =>
+        fromIterable(xs) ++: ys
+      case View.Drop(xs: List[B], n) =>
+        @tailrec def loop(xs: List[B], n: Int): List[B] =
+          if (n > 0) loop(xs.tail, n - 1) else xs
+        loop(xs, n)
+      case c: List[B] => c
+      case _ => fromIterator(c.iterator)
+    }
+  }
+
+  /** Concrete collection type: ListBuffer */
+  class ListBuffer[A] extends Seq[A] with FromIterable[ListBuffer] with Builder[A, List[A]] {
+    private var first, last: List[A] = Nil
+    private var aliased = false
+    def iterator = first.iterator
+    def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll)
+    def apply(i: Int) = first.apply(i)
+    def length = first.length
+
+    private def copyElems(): Unit = {
+      val buf = ListBuffer.fromIterable(result)
+      first = buf.first
+      last = buf.last
+      aliased = false
+    }
+    def result = {
+      aliased = true
+      first
+    }
+    def +=(elem: A) = {
+      if (aliased) copyElems()
+      val last1 = Cons(elem, Nil)
+      last match {
+        case last: Cons[A] => last.next = last1
+        case _ => first = last1
+      }
+      last = last1
+      this
+    }
+    override def toString: String =
+      if (first.isEmpty) "ListBuffer()"
+      else {
+        val b = new StringBuilder("ListBuffer(").append(first.head)
+        first.tail.foldLeft(b)(_.append(", ").append(_)).append(")").toString
+      }
+  }
+
+  object ListBuffer extends IterableFactory[ListBuffer] {
+    def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = coll match {
+      case pd @ View.Partitioned(partition: View.Partition[B] @unchecked) =>
+        partition.distribute(new ListBuffer[B]())
+        new ListBuffer[B] ++= pd.forced.get
+      case _ =>
+        new ListBuffer[B] ++= coll
+    }
+  }
+
+  /** Concrete collection type: ArrayBuffer */
+  class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int)
+  extends Seq[A] with FromIterable[ArrayBuffer] with Builder[A, ArrayBuffer[A]] {
+    def this() = this(new Array[AnyRef](16), 0)
+    private var elems: Array[AnyRef] = initElems
+    private var start = 0
+    private var end = initLength
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+    def length = end - start
+    override def knownLength = length
+    override def view = new ArrayBufferView(elems, start, end)
+    def iterator = view.iterator
+    def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] =
+      ArrayBuffer.fromIterable(it)
+    def +=(elem: A): this.type = {
+      if (end == elems.length) {
+        if (start > 0) {
+          Array.copy(elems, start, elems, 0, length)
+          end -= start
+          start = 0
+        }
+        else {
+          val newelems = new Array[AnyRef](end * 2)
+          Array.copy(elems, 0, newelems, 0, end)
+          elems = newelems
+        }
+      }
+      elems(end) = elem.asInstanceOf[AnyRef]
+      end += 1
+      this
+    }
+    def result = this
+    def trimStart(n: Int): Unit = start += (n max 0)
+    override def toString = s"ArrayBuffer(${elems.slice(start, end).mkString(", ")})"
+  }
+
+  object ArrayBuffer extends IterableFactory[ArrayBuffer] {
+    def fromIterable[B](c: Iterable[B]): ArrayBuffer[B] = c match {
+      case View.Concat(fst: ArrayBuffer[B], snd: ArrayBuffer[B]) =>
+        val elems = new Array[AnyRef](fst.length + snd.length)
+        Array.copy(fst.elems, fst.start, elems, 0, fst.length)
+        Array.copy(snd.elems, snd.start, elems, fst.length, snd.length)
+        new ArrayBuffer(elems, elems.length)
+      case pd @ View.Partitioned(partition: View.Partition[B] @unchecked) =>
+        partition.distribute(new ArrayBuffer[B]())
+        pd.forced.get.asInstanceOf[ArrayBuffer[B]]
+      case c if c.knownLength >= 0 =>
+        val elems = new Array[AnyRef](c.knownLength)
+        val it = c.iterator
+        for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef]
+        new ArrayBuffer[B](elems, elems.length)
+      case _ =>
+        val buf = new ArrayBuffer[B]
+        val it = c.iterator
+        while (it.hasNext) buf += it.next()
+        buf
+    }
+  }
+
+  class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends RandomAccessView[A] {
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+  }
+
+  /** Concrete collection type: String */
+  implicit class StringOps(val s: String) extends AnyVal with Ops[Char] {
+    def iterator: Iterator[Char] = new StringView(s).iterator
+  }
+
+  implicit class StringMonoTransforms(val s: String)
+  extends AnyVal with MonoTransformsOfSeqs[Char, String] {
+    protected def coll: Iterable[Char] = StringView(s)
+    protected def fromIterable(it: Iterable[Char]): String = {
+      val sb = new StringBuilder
+      for (ch <- it) sb.append(ch)
+      sb.toString
+    }
+  }
+
+  implicit class StringPolyTransforms(val s: String)
+  extends AnyVal with PolyTransforms[Char, Seq] {
+    protected def coll = StringView(s)
+    protected def fromIterable[B](it: Iterable[B]): Seq[B] = List.fromIterable(it)
+    def map(f: Char => Char): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def flatMap(f: Char => String) = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def ++(xs: IterableOnce[Char]): String = {
+      val sb = new StringBuilder(s)
+      for (ch <- xs.iterator) sb.append(ch)
+      sb.toString
+    }
+    def ++(xs: String): String = s + xs
+  }
+
+  case class StringView(s: String) extends RandomAccessView[Char] {
+    val start = 0
+    val end = s.length
+    def apply(n: Int) = s.charAt(n)
+  }
+
+  /* ------------ Views --------------------------------------- */
+
+  /** A lazy iterable */
+  trait View[+A] extends Iterable[A] with FromIterable[View] {
+    override def view = this
+    override def fromIterable[B](c: Iterable[B]) = c match {
+      case c: View[B] => c
+      case _ => View.fromIterator(c.iterator)
+    }
+  }
+
+  /** Iterator defined in terms of indexing a range */
+  trait RandomAccessView[+A] extends View[A] {
+    def start: Int
+    def end: Int
+    def apply(i: Int): A
+    def iterator: Iterator[A] = new Iterator[A] {
+      private var current = start
+      def hasNext = current < end
+      def next: A = {
+        val r = apply(current)
+        current += 1
+        r
+      }
+    }
+    override def knownLength = end - start max 0
+  }
+
+  object View {
+    def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] {
+      def iterator = it
+    }
+    case object Empty extends View[Nothing] {
+      def iterator = Iterator.empty
+      override def knownLength = 0
+    }
+    case class Elems[A](xs: A*) extends View[A] {
+      def iterator = Iterator(xs: _*)
+      override def knownLength = xs.length
+    }
+    case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] {
+      def iterator = underlying.iterator.filter(p)
+    }
+    case class Partition[A](val underlying: Iterable[A], p: A => Boolean) {
+      val left, right = Partitioned(this)
+      // `distribute` makes up for the lack of generic push-based functionality.
+      // It forces both halves of the partition with a given builder.
+      def distribute(bf: => Builder[A, Iterable[A]]) = {
+        val lb, rb = bf
+        val it = underlying.iterator
+        while (it.hasNext) {
+          val x = it.next()
+          (if (p(x)) lb else rb) += x
+        }
+        left.forced = Some(lb.result)
+        right.forced = Some(rb.result)
+      }
+    }
+    case class Partitioned[A](partition: Partition[A]) extends View[A] {
+      private var myForced: Option[Iterable[A]] = None
+      def forced: Option[Iterable[A]] = myForced
+      private[View] def forced_=(x: Option[Iterable[A]]): Unit = myForced = x
+      def underlying = partition.underlying
+      def iterator = forced match {
+        case Some(c) => c.iterator
+        case None =>
+          underlying.iterator.filter(
+            if (this eq partition.left) partition.p else !partition.p(_))
+      }
+    }
+    case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] {
+      def iterator = underlying.iterator.drop(n)
+      override def knownLength =
+        if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1
+    }
+    case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] {
+      def iterator = underlying.iterator.map(f)
+      override def knownLength = underlying.knownLength
+    }
+    case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] {
+      def iterator = underlying.iterator.flatMap(f)
+    }
+    case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] {
+      def iterator = underlying.iterator ++ other
+      override def knownLength = other match {
+        case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 =>
+          underlying.knownLength + other.knownLength
+        case _ =>
+          -1
+      }
+    }
+    case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] {
+      def iterator = underlying.iterator.zip(other)
+      override def knownLength = other match {
+        case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 =>
+          underlying.knownLength min other.knownLength
+        case _ =>
+          -1
+      }
+    }
+    case class Reverse[A](underlying: Iterable[A]) extends View[A] {
+      def iterator = {
+        var xs: List[A] = Nil
+        val it = underlying.iterator
+        while (it.hasNext) xs = Cons(it.next(), xs)
+        xs.iterator
+      }
+      override def knownLength = underlying.knownLength
+    }
+  }
+
+/* ---------- Iterators ---------------------------------------------------*/
+
+  /** A core Iterator class */
+  trait Iterator[+A] extends IterableOnce[A] { self =>
+    def hasNext: Boolean
+    def next(): A
+    def iterator = this
+    def foldLeft[B](z: B)(op: (B, A) => B): B =
+      if (hasNext) foldLeft(op(z, next))(op) else z
+    def foldRight[B](z: B)(op: (A, B) => B): B =
+      if (hasNext) op(next(), foldRight(z)(op)) else z
+    def foreach(f: A => Unit): Unit =
+      while (hasNext) f(next())
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next())) return i
+        i += 1
+      }
+      -1
+    }
+    def filter(p: A => Boolean): Iterator[A] = new Iterator[A] {
+      private var hd: A = _
+      private var hdDefined: Boolean = false
+
+      def hasNext: Boolean = hdDefined || {
+        do {
+          if (!self.hasNext) return false
+          hd = self.next()
+        } while (!p(hd))
+        hdDefined = true
+        true
+      }
+
+      def next() =
+        if (hasNext) {
+          hdDefined = false
+          hd
+        }
+        else Iterator.empty.next()
+    }
+
+    def map[B](f: A => B): Iterator[B] = new Iterator[B] {
+      def hasNext = self.hasNext
+      def next() = f(self.next())
+    }
+
+    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = Iterator.empty
+      private def current = {
+        while (!myCurrent.hasNext && self.hasNext)
+          myCurrent = f(self.next()).iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def ++[B >: A](xs: IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = self
+      private var first = true
+      private def current = {
+        if (!myCurrent.hasNext && first) {
+          myCurrent = xs.iterator
+          first = false
+        }
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def drop(n: Int): Iterator[A] = {
+      var i = 0
+      while (i < n && hasNext) {
+        next()
+        i += 1
+      }
+      this
+    }
+    def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] {
+      val thatIterator = that.iterator
+      def hasNext = self.hasNext && thatIterator.hasNext
+      def next() = (self.next(), thatIterator.next())
+    }
+  }
+
+  object Iterator {
+    val empty: Iterator[Nothing] = new Iterator[Nothing] {
+      def hasNext = false
+      def next = throw new NoSuchElementException("next on empty iterator")
+    }
+    def apply[A](xs: A*): Iterator[A] = new RandomAccessView[A] {
+      val start = 0
+      val end = xs.length
+      def apply(n: Int) = xs(n)
+    }.iterator
+  }
+}
+
diff --git a/compiler/src/strawman/collections/CollectionStrawMan5.scala b/compiler/src/strawman/collections/CollectionStrawMan5.scala
new file mode 100644
index 000000000..5d04c2c98
--- /dev/null
+++ b/compiler/src/strawman/collections/CollectionStrawMan5.scala
@@ -0,0 +1,522 @@
+package strawman.collections
+
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+import annotation.unchecked.uncheckedVariance
+import annotation.tailrec
+
+/** A strawman architecture for new collections. It contains some
+ *  example collection classes and methods with the intent to expose
+ *  some key issues. It would be good to compare this to other
+ *  implementations of the same functionality, to get an idea of the
+ *  strengths and weaknesses of different collection architectures.
+ *
+ *  For a test file, see tests/run/CollectionTests.scala.
+ *
+ *  Strawman5 is like strawman4, but using inheritance through ...Like traits
+ *  instead of decorators.
+ *
+ *   Advantage: Much easier to specialize. See partition for strict (buildable) collections
+ *   or drop for Lists.
+ *
+ *   Disadvantage: More "weird" types in base traits; some awkwardness with
+ *   @uncheckedVariance.
+ */
+object CollectionStrawMan5 {
+
+  /* ------------ Base Traits -------------------------------- */
+
+  /** Iterator can be used only once */
+  trait IterableOnce[+A] {
+    def iterator: Iterator[A]
+  }
+
+  /** Base trait for instances that can construct a collection from an iterable */
+  trait FromIterable[+C[X] <: Iterable[X]] {
+    def fromIterable[B](it: Iterable[B]): C[B]
+  }
+
+  /** Base trait for companion objects of collections */
+  trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] {
+    def empty[X]: C[X] = fromIterable(View.Empty)
+    def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*))
+  }
+
+  /** Base trait for generic collections */
+  trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] {
+    protected def coll: Iterable[A] = this
+    def knownLength: Int = -1
+  }
+
+  /** Base trait for sequence collections */
+  trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] {
+    def apply(i: Int): A
+    def length: Int
+  }
+
+  /** Base trait for strict collections */
+  trait Buildable[+A, +To <: Iterable[A]] extends Iterable[A] {
+    protected[this] def newBuilder: Builder[A, To]
+    override def partition(p: A => Boolean): (To, To) = {
+      val l, r = newBuilder
+      iterator.foreach(x => (if (p(x)) l else r) += x)
+      (l.result, r.result)
+    }
+    // one might also override other transforms here to avoid generating
+    // iterators if it helps efficiency.
+  }
+
+  /** Base trait for collection builders */
+  trait Builder[-A, +To] {
+    def +=(x: A): this.type
+    def result: To
+
+    def ++=(xs: IterableOnce[A]): this.type = {
+      xs.iterator.foreach(+=)
+      this
+    }
+  }
+
+  /* ------------ Operations ----------------------------------- */
+
+  /** Base trait for Iterable operations
+   *
+   *  VarianceNote
+   *  ============
+   *
+   *  We require that for all child classes of Iterable the variance of
+   *  the child class and the variance of the `C` parameter passed to `IterableLike`
+   *  are the same. We cannot express this since we lack variance polymorphism. That's
+   *  why we have to resort at some places to write `C[A @uncheckedVariance]`.
+   *
+   */
+  trait IterableLike[+A, +C[X] <: Iterable[X]]
+    extends FromIterable[C]
+       with IterableOps[A]
+       with IterableMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
+       with IterablePolyTransforms[A, C] {
+    protected[this] def fromLikeIterable(coll: Iterable[A]): C[A] = fromIterable(coll)
+  }
+
+  /** Base trait for Seq operations */
+  trait SeqLike[+A, +C[X] <: Seq[X]]
+  extends IterableLike[A, C] with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
+
+  trait IterableOps[+A] extends Any {
+    def iterator: Iterator[A]
+    def foreach(f: A => Unit): Unit = iterator.foreach(f)
+    def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op)
+    def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op)
+    def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p)
+    def isEmpty: Boolean = !iterator.hasNext
+    def head: A = iterator.next
+    def view: View[A] = View.fromIterator(iterator)
+  }
+
+  trait IterableMonoTransforms[+A, +Repr] extends Any {
+    protected def coll: Iterable[A]
+    protected[this] def fromLikeIterable(coll: Iterable[A]): Repr
+    def filter(p: A => Boolean): Repr = fromLikeIterable(View.Filter(coll, p))
+    def partition(p: A => Boolean): (Repr, Repr) = {
+      val pn = View.Partition(coll, p)
+      (fromLikeIterable(pn.left), fromLikeIterable(pn.right))
+    }
+    def drop(n: Int): Repr = fromLikeIterable(View.Drop(coll, n))
+    def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
+      // variance seems sound because `to` could just as well have been added
+      // as a decorator. We should investigate this further to be sure.
+      fi.fromIterable(coll)
+  }
+
+  trait IterablePolyTransforms[+A, +C[A]] extends Any {
+    protected def coll: Iterable[A]
+    def fromIterable[B](coll: Iterable[B]): C[B]
+    def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))
+    def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f))
+    def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs))
+    def zip[B](xs: IterableOnce[B]): C[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs))
+       // sound bcs of VarianceNote
+  }
+
+  trait SeqMonoTransforms[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] {
+    def reverse: Repr = {
+      var xs: List[A] = Nil
+      var it = coll.iterator
+      while (it.hasNext) xs = new Cons(it.next, xs)
+      fromLikeIterable(xs)
+    }
+  }
+
+  /* --------- Concrete collection types ------------------------------- */
+
+  /** Concrete collection type: List */
+  sealed trait List[+A] extends Seq[A] with SeqLike[A, List] with Buildable[A, List[A]] { self =>
+    def isEmpty: Boolean
+    def head: A
+    def tail: List[A]
+    def iterator = new Iterator[A] {
+      private[this] var current = self
+      def hasNext = !current.isEmpty
+      def next = { val r = current.head; current = current.tail; r }
+    }
+    def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c)
+    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
+    protected[this] def newBuilder = new ListBuffer[A]
+    def ++:[B >: A](prefix: List[B]): List[B] =
+      if (prefix.isEmpty) this
+      else Cons(prefix.head, prefix.tail ++: this)
+    override def ++[B >: A](xs: IterableOnce[B]): List[B] = xs match {
+      case xs: List[B] => this ++: xs
+      case _ => super.++(xs)
+    }
+    @tailrec final override def drop(n: Int) =
+      if (n > 0) tail.drop(n - 1) else this
+  }
+
+  case class Cons[+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally
+  extends List[A] {
+    override def isEmpty = false
+    override def head = x
+    def tail = next
+  }
+
+  case object Nil extends List[Nothing] {
+    override def isEmpty = true
+    override def head = ???
+    def tail = ???
+  }
+
+  object List extends IterableFactory[List] {
+    def fromIterable[B](coll: Iterable[B]): List[B] = coll match {
+      case coll: List[B] => coll
+      case _ => ListBuffer.fromIterable(coll).result
+    }
+  }
+
+  /** Concrete collection type: ListBuffer */
+  class ListBuffer[A] extends Seq[A] with SeqLike[A, ListBuffer] with Builder[A, List[A]] {
+    private var first, last: List[A] = Nil
+    private var aliased = false
+    def iterator = first.iterator
+    def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll)
+    def apply(i: Int) = first.apply(i)
+    def length = first.length
+
+    private def copyElems(): Unit = {
+      val buf = ListBuffer.fromIterable(result)
+      first = buf.first
+      last = buf.last
+      aliased = false
+    }
+    def result = {
+      aliased = true
+      first
+    }
+    def +=(elem: A) = {
+      if (aliased) copyElems()
+      val last1 = Cons(elem, Nil)
+      last match {
+        case last: Cons[A] => last.next = last1
+        case _ => first = last1
+      }
+      last = last1
+      this
+    }
+    override def toString: String =
+      if (first.isEmpty) "ListBuffer()"
+      else {
+        val b = new StringBuilder("ListBuffer(").append(first.head)
+        first.tail.foldLeft(b)(_.append(", ").append(_)).append(")").toString
+      }
+  }
+
+  object ListBuffer extends IterableFactory[ListBuffer] {
+    def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = new ListBuffer[B] ++= coll
+  }
+
+  /** Concrete collection type: ArrayBuffer */
+  class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int)
+  extends Seq[A] with SeqLike[A, ArrayBuffer] with Builder[A, ArrayBuffer[A]] {
+    def this() = this(new Array[AnyRef](16), 0)
+    private var elems: Array[AnyRef] = initElems
+    private var start = 0
+    private var end = initLength
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+    def length = end - start
+    override def knownLength = length
+    override def view = new ArrayBufferView(elems, start, end)
+    def iterator = view.iterator
+    def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] =
+      ArrayBuffer.fromIterable(it)
+    def +=(elem: A): this.type = {
+      if (end == elems.length) {
+        if (start > 0) {
+          Array.copy(elems, start, elems, 0, length)
+          end -= start
+          start = 0
+        }
+        else {
+          val newelems = new Array[AnyRef](end * 2)
+          Array.copy(elems, 0, newelems, 0, end)
+          elems = newelems
+        }
+      }
+      elems(end) = elem.asInstanceOf[AnyRef]
+      end += 1
+      this
+    }
+    def result = this
+    def trimStart(n: Int): Unit = start += (n max 0)
+    override def ++[B >: A](xs: IterableOnce[B]): ArrayBuffer[B] = xs match {
+      case xs: ArrayBuffer[B] =>
+        val elems = new Array[AnyRef](length + xs.length)
+        Array.copy(this.elems, this.start, elems, 0, this.length)
+        Array.copy(xs.elems, xs.start, elems, this.length, xs.length)
+        new ArrayBuffer(elems, elems.length)
+      case _ => super.++(xs)
+    }
+
+    override def toString = s"ArrayBuffer(${elems.slice(start, end).mkString(", ")})"
+  }
+
+  object ArrayBuffer extends IterableFactory[ArrayBuffer] {
+    def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] =
+      if (coll.knownLength >= 0) {
+        val elems = new Array[AnyRef](coll.knownLength)
+        val it = coll.iterator
+        for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef]
+        new ArrayBuffer[B](elems, elems.length)
+      }
+      else {
+        val buf = new ArrayBuffer[B]
+        val it = coll.iterator
+        while (it.hasNext) buf += it.next()
+        buf
+      }
+  }
+
+  class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends RandomAccessView[A] {
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+  }
+
+  /** Concrete collection type: String */
+  implicit class StringOps(val s: String)
+  extends AnyVal with IterableOps[Char]
+     with SeqMonoTransforms[Char, String]
+     with IterablePolyTransforms[Char, List] {
+    protected def coll = new StringView(s)
+    def iterator = coll.iterator
+    protected def fromLikeIterable(coll: Iterable[Char]): String = {
+      val sb = new StringBuilder
+      for (ch <- coll) sb.append(ch)
+      sb.toString
+    }
+    def fromIterable[B](coll: Iterable[B]): List[B] = List.fromIterable(coll)
+    def map(f: Char => Char): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def flatMap(f: Char => String): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb.append(f(ch))
+      sb.toString
+    }
+    def ++(xs: IterableOnce[Char]): String = {
+      val sb = new StringBuilder(s)
+      for (ch <- xs.iterator) sb.append(ch)
+      sb.toString
+    }
+    def ++(xs: String): String = s + xs
+  }
+
+  case class StringView(s: String) extends RandomAccessView[Char] {
+    val start = 0
+    val end = s.length
+    def apply(n: Int) = s.charAt(n)
+  }
+
+/* ---------- Views -------------------------------------------------------*/
+
+  /** Concrete collection type: View */
+  trait View[+A] extends Iterable[A] with IterableLike[A, View] {
+    override def view = this
+    override def fromIterable[B](c: Iterable[B]): View[B] = c match {
+      case c: View[B] => c
+      case _ => View.fromIterator(c.iterator)
+    }
+  }
+
+  /** View defined in terms of indexing a range */
+  trait RandomAccessView[+A] extends View[A] {
+    def start: Int
+    def end: Int
+    def apply(i: Int): A
+    def iterator: Iterator[A] = new Iterator[A] {
+      private var current = start
+      def hasNext = current < end
+      def next: A = {
+        val r = apply(current)
+        current += 1
+        r
+      }
+    }
+    override def knownLength = end - start max 0
+  }
+
+  object View {
+    def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] {
+      def iterator = it
+    }
+    case object Empty extends View[Nothing] {
+      def iterator = Iterator.empty
+      override def knownLength = 0
+    }
+    case class Elems[A](xs: A*) extends View[A] {
+      def iterator = Iterator(xs: _*)
+      override def knownLength = xs.length
+    }
+    case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] {
+      def iterator = underlying.iterator.filter(p)
+    }
+    case class Partition[A](val underlying: Iterable[A], p: A => Boolean) {
+      val left = Partitioned(this, true)
+      val right = Partitioned(this, false)
+    }
+    case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] {
+      def iterator = partition.underlying.iterator.filter(x => partition.p(x) == cond)
+    }
+    case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] {
+      def iterator = underlying.iterator.drop(n)
+      override def knownLength =
+        if (underlying.knownLength >= 0) underlying.knownLength - n max 0 else -1
+    }
+    case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] {
+      def iterator = underlying.iterator.map(f)
+      override def knownLength = underlying.knownLength
+    }
+    case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] {
+      def iterator = underlying.iterator.flatMap(f)
+    }
+    case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] {
+      def iterator = underlying.iterator ++ other
+      override def knownLength = other match {
+        case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 =>
+          underlying.knownLength + other.knownLength
+        case _ =>
+          -1
+      }
+    }
+    case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] {
+      def iterator = underlying.iterator.zip(other)
+      override def knownLength = other match {
+        case other: Iterable[_] if underlying.knownLength >= 0 && other.knownLength >= 0 =>
+          underlying.knownLength min other.knownLength
+        case _ =>
+          -1
+      }
+    }
+  }
+
+/* ---------- Iterators ---------------------------------------------------*/
+
+  /** A core Iterator class */
+  trait Iterator[+A] extends IterableOnce[A] { self =>
+    def hasNext: Boolean
+    def next(): A
+    def iterator = this
+    def foldLeft[B](z: B)(op: (B, A) => B): B =
+      if (hasNext) foldLeft(op(z, next))(op) else z
+    def foldRight[B](z: B)(op: (A, B) => B): B =
+      if (hasNext) op(next(), foldRight(z)(op)) else z
+    def foreach(f: A => Unit): Unit =
+      while (hasNext) f(next())
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next())) return i
+        i += 1
+      }
+      -1
+    }
+    def filter(p: A => Boolean): Iterator[A] = new Iterator[A] {
+      private var hd: A = _
+      private var hdDefined: Boolean = false
+
+      def hasNext: Boolean = hdDefined || {
+        do {
+          if (!self.hasNext) return false
+          hd = self.next()
+        } while (!p(hd))
+        hdDefined = true
+        true
+      }
+
+      def next() =
+        if (hasNext) {
+          hdDefined = false
+          hd
+        }
+        else Iterator.empty.next()
+    }
+
+    def map[B](f: A => B): Iterator[B] = new Iterator[B] {
+      def hasNext = self.hasNext
+      def next() = f(self.next())
+    }
+
+    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = Iterator.empty
+      private def current = {
+        while (!myCurrent.hasNext && self.hasNext)
+          myCurrent = f(self.next()).iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def ++[B >: A](xs: IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = self
+      private var first = true
+      private def current = {
+        if (!myCurrent.hasNext && first) {
+          myCurrent = xs.iterator
+          first = false
+        }
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def drop(n: Int): Iterator[A] = {
+      var i = 0
+      while (i < n && hasNext) {
+        next()
+        i += 1
+      }
+      this
+    }
+    def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] {
+      val thatIterator = that.iterator
+      def hasNext = self.hasNext && thatIterator.hasNext
+      def next() = (self.next(), thatIterator.next())
+    }
+  }
+
+  object Iterator {
+    val empty: Iterator[Nothing] = new Iterator[Nothing] {
+      def hasNext = false
+      def next = throw new NoSuchElementException("next on empty iterator")
+    }
+    def apply[A](xs: A*): Iterator[A] = new RandomAccessView[A] {
+      val start = 0
+      val end = xs.length
+      def apply(n: Int) = xs(n)
+    }.iterator
+  }
+}
diff --git a/compiler/src/strawman/collections/CollectionStrawMan6.scala b/compiler/src/strawman/collections/CollectionStrawMan6.scala
new file mode 100644
index 000000000..50de63488
--- /dev/null
+++ b/compiler/src/strawman/collections/CollectionStrawMan6.scala
@@ -0,0 +1,1045 @@
+package strawman.collections
+
+import Predef.{augmentString => _, wrapString => _, _}
+import scala.reflect.ClassTag
+import annotation.unchecked.uncheckedVariance
+import annotation.tailrec
+
+class LowPriority {
+  import CollectionStrawMan6._
+
+  /** Convert array to iterable via view. Lower priority than ArrayOps */
+  implicit def arrayToView[T](xs: Array[T]): ArrayView[T] = new ArrayView[T](xs)
+
+  /** Convert string to iterable via view. Lower priority than StringOps */
+  implicit def stringToView(s: String): StringView = new StringView(s)
+}
+
+/** A strawman architecture for new collections. It contains some
+ *  example collection classes and methods with the intent to expose
+ *  some key issues. It would be good to compare this to odether
+ *  implementations of the same functionality, to get an idea of the
+ *  strengths and weaknesses of different collection architectures.
+ *
+ *  For a test file, see tests/run/CollectionTests.scala.
+ *
+ *  Strawman6 is like strawman5, and adds lazy lists (i.e. lazie streams), arrays
+ *  and some utilitity methods (take, tail, mkString, toArray). Also, systematically
+ *  uses builders for all strict collections.
+ *
+ *  Types covered in this strawman:
+ *
+ *  1. Collection base types:
+ *
+ *         IterableOnce, Iterable, Seq, LinearSeq, View, IndexedView
+ *
+ *  2. Collection creator base types:
+ *
+ *         FromIterable, IterableFactory, Buildable, Builder
+ *
+ *  3. Types that bundle operations:
+ *
+ *         IterableOps, IterableMonoTransforms, IterablePolyTransforms, IterableLike
+ *         SeqMonoTransforms, SeqLike
+ *
+ *  4. Concrete collection types:
+ *
+ *         List, LazyList, ListBuffer, ArrayBuffer, ArrayBufferView, StringView, ArrayView
+ *
+ *  5. Decorators for existing types
+ *
+ *         StringOps, ArrayOps
+ *
+ *  6. Related non collection types:
+ *
+ *         Iterator, StringBuilder
+ *
+ *  Operations covered in this strawman:
+ *
+ *   1. Abstract operations, or expected to be overridden:
+ *
+ *      For iterables:
+ *
+ *         iterator, fromIterable, fromIterableWithSameElemType, knownLength, className
+ *
+ *      For sequences:
+ *
+ *         apply, length
+ *
+ *      For buildables:
+ *
+ *         newBuilder
+ *
+ *      For builders:
+ *
+ *         +=, result
+ *
+ *   2. Utility methods, might be overridden for performance:
+ *
+ *      Operations returning not necessarily a collection:
+ *
+ *         foreach, foldLeft, foldRight, indexWhere, isEmpty, head, size, mkString
+ *
+ *      Operations returning a collection of a fixed type constructor:
+ *
+ *         view, to, toArray, copyToArray
+ *
+ *      Type-preserving generic transforms:
+ *
+ *         filter, partition, take, drop, tail, reverse
+ *
+ *      Generic transforms returning collections of different element types:
+ *
+ *         map, flatMap, ++, zip
+ */
+object CollectionStrawMan6 extends LowPriority {
+
+  /* ------------ Base Traits -------------------------------- */
+
+  /** Iterator can be used only once */
+  trait IterableOnce[+A] {
+    def iterator: Iterator[A]
+  }
+
+  /** Base trait for instances that can construct a collection from an iterable */
+  trait FromIterable[+C[X] <: Iterable[X]] {
+    def fromIterable[B](it: Iterable[B]): C[B]
+  }
+
+  /** Base trait for companion objects of collections */
+  trait IterableFactory[+C[X] <: Iterable[X]] extends FromIterable[C] {
+    def empty[X]: C[X] = fromIterable(View.Empty)
+    def apply[A](xs: A*): C[A] = fromIterable(View.Elems(xs: _*))
+  }
+
+  /** Base trait for generic collections */
+  trait Iterable[+A] extends IterableOnce[A] with IterableLike[A, Iterable] {
+    /** The collection itself */
+    protected def coll: this.type = this
+  }
+
+  /** A trait representing indexable collections with finite length */
+  trait ArrayLike[+A] extends Any {
+    def length: Int
+    def apply(i: Int): A
+  }
+
+  /** Base trait for sequence collections */
+  trait Seq[+A] extends Iterable[A] with SeqLike[A, Seq] with ArrayLike[A]
+
+  /** Base trait for linearly accessed sequences that have efficient `head` and
+   *  `tail` operations.
+   *  Known subclasses: List, LazyList
+   */
+  trait LinearSeq[+A] extends Seq[A] with LinearSeqLike[A, LinearSeq] { self =>
+
+    /** To be overridden in implementations: */
+    def isEmpty: Boolean
+    def head: A
+    def tail: LinearSeq[A]
+
+    /** `iterator` is overridden in terms of `head` and `tail` */
+    def iterator = new Iterator[A] {
+      private[this] var current: Seq[A] = self
+      def hasNext = !current.isEmpty
+      def next = { val r = current.head; current = current.tail; r }
+    }
+
+    /** `length is defined in terms of `iterator` */
+    def length: Int = iterator.length
+
+    /** `apply` is defined in terms of `drop`, which is in turn defined in
+     *  terms of `tail`.
+     */
+    override def apply(n: Int): A = {
+      if (n < 0) throw new IndexOutOfBoundsException(n.toString)
+      val skipped = drop(n)
+      if (skipped.isEmpty) throw new IndexOutOfBoundsException(n.toString)
+      skipped.head
+    }
+  }
+
+  type IndexedSeq[+A] = Seq[A] { def view: IndexedView[A] }
+
+  /** Base trait for strict collections that can be built using a builder.
+   *  @param  A    the element type of the collection
+   *  @param Repr  the type of the underlying collection
+   */
+  trait Buildable[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr]  {
+
+    /** Creates a new builder. */
+    protected[this] def newBuilder: Builder[A, Repr]
+
+    /** Optimized, push-based version of `partition`. */
+    override def partition(p: A => Boolean): (Repr, Repr) = {
+      val l, r = newBuilder
+      coll.iterator.foreach(x => (if (p(x)) l else r) += x)
+      (l.result, r.result)
+    }
+
+    // one might also override other transforms here to avoid generating
+    // iterators if it helps efficiency.
+  }
+
+  /** Base trait for collection builders */
+  trait Builder[-A, +To] { self =>
+
+    /** Append an element */
+    def +=(x: A): this.type
+
+    /** Result collection consisting of all elements appended so far. */
+    def result: To
+
+    /** Bulk append. Can be overridden if specialized implementations are available. */
+    def ++=(xs: IterableOnce[A]): this.type = {
+      xs.iterator.foreach(+=)
+      this
+    }
+
+    /** A builder resulting from this builder my mapping the result using `f`. */
+    def mapResult[NewTo](f: To => NewTo) = new Builder[A, NewTo] {
+      def +=(x: A): this.type = { self += x; this }
+      override def ++=(xs: IterableOnce[A]): this.type = { self ++= xs; this }
+      def result: NewTo = f(self.result)
+    }
+  }
+
+  /* ------------ Operations ----------------------------------- */
+
+  /** Base trait for Iterable operations
+   *
+   *  VarianceNote
+   *  ============
+   *
+   *  We require that for all child classes of Iterable the variance of
+   *  the child class and the variance of the `C` parameter passed to `IterableLike`
+   *  are the same. We cannot express this since we lack variance polymorphism. That's
+   *  why we have to resort at some places to write `C[A @uncheckedVariance]`.
+   *
+   */
+  trait IterableLike[+A, +C[X] <: Iterable[X]]
+    extends FromIterable[C]
+       with IterableOps[A]
+       with IterableMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
+       with IterablePolyTransforms[A, C] {
+
+    /** Create a collection of type `C[A]` from the elements of `coll`, which has
+     *  the same element type as this collection. Overridden in StringOps and ArrayOps.
+     */
+    protected[this] def fromIterableWithSameElemType(coll: Iterable[A]): C[A] = fromIterable(coll)
+  }
+
+  /** Base trait for Seq operations */
+  trait SeqLike[+A, +C[X] <: Seq[X]]
+  extends IterableLike[A, C]
+     with SeqMonoTransforms[A, C[A @uncheckedVariance]] // sound bcs of VarianceNote
+
+  /** Base trait for linear Seq operations */
+  trait LinearSeqLike[+A, +C[X] <: LinearSeq[X]] extends SeqLike[A, C] {
+
+    /** Optimized version of `drop` that avoids copying
+     *  Note: `drop` is defined here, rather than in a trait like `LinearSeqMonoTransforms`,
+     *  because the `...MonoTransforms` traits make no assumption about the type of `Repr`
+     *  whereas we need to assume here that `Repr` is the same as the underlying
+     *  collection type.
+     */
+    override def drop(n: Int): C[A @uncheckedVariance] = { // sound bcs of VarianceNote
+      def loop(n: Int, s: Iterable[A]): C[A] =
+        if (n <= 0) s.asInstanceOf[C[A]]
+           // implicit contract to guarantee success of asInstanceOf:
+           //   (1) coll is of type C[A]
+           //   (2) The tail of a LinearSeq is of the same type as the type of the sequence itself
+           // it's surprisingly tricky/ugly to turn this into actual types, so we
+           // leave this contract implicit.
+        else loop(n - 1, s.tail)
+      loop(n, coll)
+    }
+  }
+
+  /** Operations over iterables. No operation defined here is generic in the
+   *  type of the underlying collection.
+   */
+  trait IterableOps[+A] extends Any {
+    protected def coll: Iterable[A]
+    private def iterator = coll.iterator
+
+    /** Apply `f` to each element for tis side effects */
+    def foreach(f: A => Unit): Unit = iterator.foreach(f)
+
+    /** Fold left */
+    def foldLeft[B](z: B)(op: (B, A) => B): B = iterator.foldLeft(z)(op)
+
+    /** Fold right */
+    def foldRight[B](z: B)(op: (A, B) => B): B = iterator.foldRight(z)(op)
+
+    /** The index of the first element in this collection for which `p` holds. */
+    def indexWhere(p: A => Boolean): Int = iterator.indexWhere(p)
+
+    /** Is the collection empty? */
+    def isEmpty: Boolean = !iterator.hasNext
+
+    /** The first element of the collection. */
+    def head: A = iterator.next()
+
+    /** The number of elements in this collection, if it can be cheaply computed,
+     *  -1 otherwise. Cheaply usually means: Not requiring a collection traversal.
+     */
+    def knownSize: Int = -1
+
+    /** The number of elements in this collection. Does not terminate for
+     *  infinite collections.
+     */
+    def size: Int = if (knownSize >= 0) knownSize else iterator.length
+
+    /** A view representing the elements of this collection. */
+    def view: View[A] = View.fromIterator(iterator)
+
+     /** Given a collection factory `fi` for collections of type constructor `C`,
+     *  convert this collection to one of type `C[A]`. Example uses:
+     *
+     *      xs.to(List)
+     *      xs.to(ArrayBuffer)
+     */
+    def to[C[X] <: Iterable[X]](fi: FromIterable[C]): C[A @uncheckedVariance] =
+      // variance seems sound because `to` could just as well have been added
+      // as a decorator. We should investigate this further to be sure.
+      fi.fromIterable(coll)
+
+    /** Convert collection to array. */
+    def toArray[B >: A: ClassTag]: Array[B] =
+      if (knownSize >= 0) copyToArray(new Array[B](knownSize), 0)
+      else ArrayBuffer.fromIterable(coll).toArray[B]
+
+    /** Copy all elements of this collection to array `xs`, starting at `start`. */
+    def copyToArray[B >: A](xs: Array[B], start: Int = 0): xs.type = {
+      var i = start
+      val it = iterator
+      while (it.hasNext) {
+        xs(i) = it.next()
+        i += 1
+      }
+      xs
+    }
+
+    /** The class name of this collection. To be used for converting to string.
+     *  Collections generally print like this:
+     *
+     *       <className>(elem_1, ..., elem_n)
+     */
+    def className = getClass.getName
+
+    /** A string showing all elements of this collection, separated by string `sep`. */
+    def mkString(sep: String): String = {
+      var first: Boolean = true
+      val b = new StringBuilder()
+      foreach { elem =>
+        if (!first) b ++= sep
+        first = false
+        b ++= String.valueOf(elem)
+      }
+      b.result
+    }
+
+    override def toString = s"$className(${mkString(", ")})"
+  }
+
+  /** Type-preserving transforms over iterables.
+   *  Operations defined here return in their result iterables of the same type
+   *  as the one they are invoked on.
+   */
+  trait IterableMonoTransforms[+A, +Repr] extends Any {
+    protected def coll: Iterable[A]
+    protected[this] def fromIterableWithSameElemType(coll: Iterable[A]): Repr
+
+    /** All elements satisfying predicate `p` */
+    def filter(p: A => Boolean): Repr = fromIterableWithSameElemType(View.Filter(coll, p))
+
+    /** A pair of, first, all elements that satisfy prediacte `p` and, second,
+     *  all elements that do not. Interesting because it splits a collection in two.
+     *
+     *  The default implementation provided here needs to traverse the collection twice.
+     *  Strict collections have an overridden version of `partition` in `Buildable`,
+     *  which requires only a single traversal.
+     */
+    def partition(p: A => Boolean): (Repr, Repr) = {
+      val pn = View.Partition(coll, p)
+      (fromIterableWithSameElemType(pn.left), fromIterableWithSameElemType(pn.right))
+    }
+
+    /** A collection containing the first `n` elements of this collection. */
+    def take(n: Int): Repr = fromIterableWithSameElemType(View.Take(coll, n))
+
+    /** The rest of the collection without its `n` first elements. For
+     *  linear, immutable collections this should avoid making a copy.
+     */
+    def drop(n: Int): Repr = fromIterableWithSameElemType(View.Drop(coll, n))
+
+    /** The rest of the collection without its first element. */
+    def tail: Repr = drop(1)
+  }
+
+  /** Transforms over iterables that can return collections of different element types.
+   */
+  trait IterablePolyTransforms[+A, +C[A]] extends Any {
+    protected def coll: Iterable[A]
+    def fromIterable[B](coll: Iterable[B]): C[B]
+
+    /** Map */
+    def map[B](f: A => B): C[B] = fromIterable(View.Map(coll, f))
+
+    /** Flatmap */
+    def flatMap[B](f: A => IterableOnce[B]): C[B] = fromIterable(View.FlatMap(coll, f))
+
+    /** Concatenation */
+    def ++[B >: A](xs: IterableOnce[B]): C[B] = fromIterable(View.Concat(coll, xs))
+
+    /** Zip. Interesting because it requires to align to source collections. */
+    def zip[B](xs: IterableOnce[B]): C[(A @uncheckedVariance, B)] = fromIterable(View.Zip(coll, xs))
+       // sound bcs of VarianceNote
+  }
+
+  /** Type-preserving transforms over sequences. */
+  trait SeqMonoTransforms[+A, +Repr] extends Any with IterableMonoTransforms[A, Repr] {
+    def reverse: Repr = coll.view match {
+      case v: IndexedView[A] => fromIterableWithSameElemType(v.reverse)
+      case _ =>
+        var xs: List[A] = Nil
+        var it = coll.iterator
+        while (it.hasNext) xs = it.next() :: xs
+        fromIterableWithSameElemType(xs)
+    }
+  }
+
+  /* --------- Concrete collection types ------------------------------- */
+
+  /** Concrete collection type: List */
+  sealed trait List[+A]
+  extends LinearSeq[A]
+     with SeqLike[A, List]
+     with Buildable[A, List[A]] {
+
+    def fromIterable[B](c: Iterable[B]): List[B] = List.fromIterable(c)
+
+    protected[this] def newBuilder = new ListBuffer[A].mapResult(_.toList)
+
+    /** Prepend element */
+    def :: [B >: A](elem: B): List[B] =  new ::(elem, this)
+
+    /** Prepend operation that avoids copying this list */
+    def ++:[B >: A](prefix: List[B]): List[B] =
+      if (prefix.isEmpty) this
+      else prefix.head :: prefix.tail ++: this
+
+    /** When concatenating with another list `xs`, avoid copying `xs` */
+    override def ++[B >: A](xs: IterableOnce[B]): List[B] = xs match {
+      case xs: List[B] => this ++: xs
+      case _ => super.++(xs)
+    }
+
+    override def className = "List"
+  }
+
+  case class :: [+A](x: A, private[collections] var next: List[A @uncheckedVariance]) // sound because `next` is used only locally
+  extends List[A] {
+    override def isEmpty = false
+    override def head = x
+    override def tail = next
+  }
+
+  case object Nil extends List[Nothing] {
+    override def isEmpty = true
+    override def head = ???
+    override def tail = ???
+  }
+
+  object List extends IterableFactory[List] {
+    def fromIterable[B](coll: Iterable[B]): List[B] = coll match {
+      case coll: List[B] => coll
+      case _ => ListBuffer.fromIterable(coll).toList
+    }
+  }
+
+  /** Concrete collection type: ListBuffer */
+  class ListBuffer[A]
+  extends Seq[A]
+     with SeqLike[A, ListBuffer]
+     with Buildable[A, ListBuffer[A]]
+     with Builder[A, ListBuffer[A]] {
+
+    private var first, last: List[A] = Nil
+    private var aliased = false
+    private var len = 0
+
+    def iterator = first.iterator
+
+    def fromIterable[B](coll: Iterable[B]) = ListBuffer.fromIterable(coll)
+
+    def apply(i: Int) = first.apply(i)
+
+    def length = len
+    override def knownSize = len
+
+    protected[this] def newBuilder = new ListBuffer[A]
+
+    private def copyElems(): Unit = {
+      val buf = ListBuffer.fromIterable(result)
+      first = buf.first
+      last = buf.last
+      aliased = false
+    }
+
+    /** Convert to list; avoids copying where possible. */
+    def toList = {
+      aliased = true
+      first
+    }
+
+    def +=(elem: A) = {
+      if (aliased) copyElems()
+      val last1 = elem :: Nil
+      last match {
+        case last: ::[A] => last.next = last1
+        case _ => first = last1
+      }
+      last = last1
+      len += 1
+      this
+    }
+
+    def result = this
+
+    override def className = "ListBuffer"
+  }
+
+  object ListBuffer extends IterableFactory[ListBuffer] {
+    def fromIterable[B](coll: Iterable[B]): ListBuffer[B] = new ListBuffer[B] ++= coll
+  }
+
+  /** Concrete collection type: ArrayBuffer */
+  class ArrayBuffer[A] private (initElems: Array[AnyRef], initLength: Int)
+  extends Seq[A]
+     with SeqLike[A, ArrayBuffer]
+     with Buildable[A, ArrayBuffer[A]]
+     with Builder[A, ArrayBuffer[A]] {
+
+    def this() = this(new Array[AnyRef](16), 0)
+
+    private var elems: Array[AnyRef] = initElems
+    private var start = 0
+    private var end = initLength
+
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+
+    def length = end - start
+    override def knownSize = length
+
+    override def view = new ArrayBufferView(elems, start, end)
+
+    def iterator = view.iterator
+
+    def fromIterable[B](it: Iterable[B]): ArrayBuffer[B] =
+      ArrayBuffer.fromIterable(it)
+
+    protected[this] def newBuilder = new ArrayBuffer[A]
+
+    def +=(elem: A): this.type = {
+      if (end == elems.length) {
+        if (start > 0) {
+          Array.copy(elems, start, elems, 0, length)
+          end -= start
+          start = 0
+        }
+        else {
+          val newelems = new Array[AnyRef](end * 2)
+          Array.copy(elems, 0, newelems, 0, end)
+          elems = newelems
+        }
+      }
+      elems(end) = elem.asInstanceOf[AnyRef]
+      end += 1
+      this
+    }
+
+    def result = this
+
+    /** New operation: destructively drop elements at start of buffer. */
+    def trimStart(n: Int): Unit = start += (n max 0)
+
+    /** Overridden to use array copying for efficiency where possible. */
+    override def ++[B >: A](xs: IterableOnce[B]): ArrayBuffer[B] = xs match {
+      case xs: ArrayBuffer[B] =>
+        val elems = new Array[AnyRef](length + xs.length)
+        Array.copy(this.elems, this.start, elems, 0, this.length)
+        Array.copy(xs.elems, xs.start, elems, this.length, xs.length)
+        new ArrayBuffer(elems, elems.length)
+      case _ => super.++(xs)
+    }
+
+    override def take(n: Int) = {
+      val elems = new Array[AnyRef](n min length)
+      Array.copy(this.elems, this.start, elems, 0, elems.length)
+      new ArrayBuffer(elems, elems.length)
+    }
+
+    override def className = "ArrayBuffer"
+  }
+
+  object ArrayBuffer extends IterableFactory[ArrayBuffer] {
+
+    /** Avoid reallocation of buffer if length is known. */
+    def fromIterable[B](coll: Iterable[B]): ArrayBuffer[B] =
+      if (coll.knownSize >= 0) {
+        val elems = new Array[AnyRef](coll.knownSize)
+        val it = coll.iterator
+        for (i <- 0 until elems.length) elems(i) = it.next().asInstanceOf[AnyRef]
+        new ArrayBuffer[B](elems, elems.length)
+      }
+      else new ArrayBuffer[B] ++= coll
+  }
+
+  class ArrayBufferView[A](val elems: Array[AnyRef], val start: Int, val end: Int) extends IndexedView[A] {
+    def length = end - start
+    def apply(n: Int) = elems(start + n).asInstanceOf[A]
+    override def className = "ArrayBufferView"
+  }
+
+  class LazyList[+A](expr: => LazyList.Evaluated[A])
+  extends LinearSeq[A] with SeqLike[A, LazyList] {
+    private[this] var evaluated = false
+    private[this] var result: LazyList.Evaluated[A] = _
+
+    def force: LazyList.Evaluated[A] = {
+      if (!evaluated) {
+        result = expr
+        evaluated = true
+      }
+      result
+    }
+
+    override def isEmpty = force.isEmpty
+    override def head = force.get._1
+    override def tail = force.get._2
+
+    def #:: [B >: A](elem: => B): LazyList[B] = new LazyList(Some((elem, this)))
+
+    def fromIterable[B](c: Iterable[B]): LazyList[B] = LazyList.fromIterable(c)
+
+    override def className = "LazyList"
+
+    override def toString =
+      if (evaluated)
+        result match {
+          case None => "Empty"
+          case Some((hd, tl)) => s"$hd #:: $tl"
+        }
+      else "LazyList(?)"
+  }
+
+  object LazyList extends IterableFactory[LazyList] {
+
+    type Evaluated[+A] = Option[(A, LazyList[A])]
+
+    object Empty extends LazyList[Nothing](None)
+
+    object #:: {
+      def unapply[A](s: LazyList[A]): Evaluated[A] = s.force
+    }
+
+    def fromIterable[B](coll: Iterable[B]): LazyList[B] = coll match {
+      case coll: LazyList[B] => coll
+      case _ => fromIterator(coll.iterator)
+    }
+
+    def fromIterator[B](it: Iterator[B]): LazyList[B] =
+      new LazyList(if (it.hasNext) Some(it.next(), fromIterator(it)) else None)
+  }
+
+  // ------------------ Decorators to add collection ops to existing types -----------------------
+
+  /** Decorator to add collection operations to strings.
+   */
+  implicit class StringOps(val s: String)
+  extends AnyVal with IterableOps[Char]
+     with SeqMonoTransforms[Char, String]
+     with IterablePolyTransforms[Char, List]
+     with Buildable[Char, String]
+     with ArrayLike[Char] {
+
+    protected def coll = new StringView(s)
+    def iterator = coll.iterator
+
+    protected def fromIterableWithSameElemType(coll: Iterable[Char]): String = {
+      val sb = new StringBuilder
+      for (ch <- coll) sb += ch
+      sb.result
+    }
+
+    def fromIterable[B](coll: Iterable[B]): List[B] = List.fromIterable(coll)
+
+    protected[this] def newBuilder = new StringBuilder
+
+    def length = s.length
+    def apply(i: Int) = s.charAt(i)
+
+    override def knownSize = s.length
+
+    override def className = "String"
+
+    /** Overloaded version of `map` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
+    def map(f: Char => Char): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb += f(ch)
+      sb.result
+    }
+
+    /** Overloaded version of `flatMap` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
+    def flatMap(f: Char => String): String = {
+      val sb = new StringBuilder
+      for (ch <- s) sb ++= f(ch)
+      sb.result
+    }
+
+    /** Overloaded version of `++` that gives back a string, where the inherited
+     *  version gives back a sequence.
+     */
+    def ++(xs: IterableOnce[Char]): String = {
+      val sb = new StringBuilder() ++= s
+      for (ch <- xs.iterator) sb += ch
+      sb.result
+    }
+
+    /** Another overloaded version of `++`. */
+    def ++(xs: String): String = s + xs
+  }
+
+  class StringBuilder extends Builder[Char, String] {
+    private val sb = new java.lang.StringBuilder
+
+    def += (x: Char) = { sb.append(x); this }
+
+    /** Overloaded version of `++=` that takes a string */
+    def ++= (s: String) = { sb.append(s); this }
+
+    def result = sb.toString
+
+    override def toString = result
+  }
+
+  case class StringView(s: String) extends IndexedView[Char] {
+    def length = s.length
+    def apply(n: Int) = s.charAt(n)
+    override def className = "StringView"
+  }
+
+  /** Decorator to add collection operations to arrays.
+   */
+  implicit class ArrayOps[A](val xs: Array[A])
+  extends AnyVal with IterableOps[A]
+     with SeqMonoTransforms[A, Array[A]]
+     with Buildable[A, Array[A]]
+     with ArrayLike[A] {
+
+    protected def coll = new ArrayView(xs)
+    def iterator = coll.iterator
+
+    def length = xs.length
+    def apply(i: Int) = xs.apply(i)
+
+    override def view = new ArrayView(xs)
+
+    def elemTag: ClassTag[A] = ClassTag(xs.getClass.getComponentType)
+
+    protected def fromIterableWithSameElemType(coll: Iterable[A]): Array[A] = coll.toArray[A](elemTag)
+
+    def fromIterable[B: ClassTag](coll: Iterable[B]): Array[B] = coll.toArray[B]
+
+    protected[this] def newBuilder = new ArrayBuffer[A].mapResult(_.toArray(elemTag))
+
+    override def knownSize = xs.length
+
+    override def className = "Array"
+
+    def map[B: ClassTag](f: A => B): Array[B] = fromIterable(View.Map(coll, f))
+    def flatMap[B: ClassTag](f: A => IterableOnce[B]): Array[B] = fromIterable(View.FlatMap(coll, f))
+    def ++[B >: A : ClassTag](xs: IterableOnce[B]): Array[B] = fromIterable(View.Concat(coll, xs))
+    def zip[B: ClassTag](xs: IterableOnce[B]): Array[(A, B)] = fromIterable(View.Zip(coll, xs))
+  }
+
+  case class ArrayView[A](xs: Array[A]) extends IndexedView[A] {
+    def length = xs.length
+    def apply(n: Int) = xs(n)
+    override def className = "ArrayView"
+  }
+
+  /* ---------- Views -------------------------------------------------------*/
+
+  /** Concrete collection type: View */
+  trait View[+A] extends Iterable[A] with IterableLike[A, View] {
+    override def view = this
+
+    /** Avoid copying if source collection is already a view. */
+    override def fromIterable[B](c: Iterable[B]): View[B] = c match {
+      case c: View[B] => c
+      case _ => View.fromIterator(c.iterator)
+    }
+    override def className = "View"
+  }
+
+  /** This object reifies operations on views as case classes */
+  object View {
+    def fromIterator[A](it: => Iterator[A]): View[A] = new View[A] {
+      def iterator = it
+    }
+
+    /** The empty view */
+    case object Empty extends View[Nothing] {
+      def iterator = Iterator.empty
+      override def knownSize = 0
+    }
+
+    /** A view with given elements */
+    case class Elems[A](xs: A*) extends View[A] {
+      def iterator = Iterator(xs: _*)
+      override def knownSize = xs.length // should be: xs.knownSize, but A*'s are not sequences in this strawman.
+    }
+
+    /** A view that filters an underlying collection. */
+    case class Filter[A](val underlying: Iterable[A], p: A => Boolean) extends View[A] {
+      def iterator = underlying.iterator.filter(p)
+    }
+
+    /** A view that partitions an underlying collection into two views */
+    case class Partition[A](val underlying: Iterable[A], p: A => Boolean) {
+
+      /** The view consisting of all elements of the underlying collection
+       *  that satisfy `p`.
+       */
+      val left = Partitioned(this, true)
+
+      /** The view consisting of all elements of the underlying collection
+       *  that do not satisfy `p`.
+       */
+      val right = Partitioned(this, false)
+    }
+
+    /** A view representing one half of a partition. */
+    case class Partitioned[A](partition: Partition[A], cond: Boolean) extends View[A] {
+      def iterator = partition.underlying.iterator.filter(x => partition.p(x) == cond)
+    }
+
+    /** A view that drops leading elements of the underlying collection. */
+    case class Drop[A](underlying: Iterable[A], n: Int) extends View[A] {
+      def iterator = underlying.iterator.drop(n)
+      protected val normN = n max 0
+      override def knownSize =
+        if (underlying.knownSize >= 0) (underlying.knownSize - normN) max 0 else -1
+    }
+
+    /** A view that takes leading elements of the underlying collection. */
+    case class Take[A](underlying: Iterable[A], n: Int) extends View[A] {
+      def iterator = underlying.iterator.take(n)
+      protected val normN = n max 0
+      override def knownSize =
+        if (underlying.knownSize >= 0) underlying.knownSize min normN else -1
+    }
+
+    /** A view that maps elements of the underlying collection. */
+    case class Map[A, B](underlying: Iterable[A], f: A => B) extends View[B] {
+      def iterator = underlying.iterator.map(f)
+      override def knownSize = underlying.knownSize
+    }
+
+    /** A view that flatmaps elements of the underlying collection. */
+    case class FlatMap[A, B](underlying: Iterable[A], f: A => IterableOnce[B]) extends View[B] {
+      def iterator = underlying.iterator.flatMap(f)
+    }
+
+    /** A view that concatenates elements of the underlying collection with the elements
+     *  of another collection or iterator.
+     */
+    case class Concat[A](underlying: Iterable[A], other: IterableOnce[A]) extends View[A] {
+      def iterator = underlying.iterator ++ other
+      override def knownSize = other match {
+        case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 =>
+          underlying.knownSize + other.knownSize
+        case _ =>
+          -1
+      }
+    }
+
+    /** A view that zips elements of the underlying collection with the elements
+     *  of another collection or iterator.
+     */
+    case class Zip[A, B](underlying: Iterable[A], other: IterableOnce[B]) extends View[(A, B)] {
+      def iterator = underlying.iterator.zip(other)
+      override def knownSize = other match {
+        case other: Iterable[_] if underlying.knownSize >= 0 && other.knownSize >= 0 =>
+          underlying.knownSize min other.knownSize
+        case _ =>
+          -1
+      }
+    }
+  }
+
+  /** View defined in terms of indexing a range */
+  trait IndexedView[+A] extends View[A] with ArrayLike[A] { self =>
+
+    def iterator: Iterator[A] = new Iterator[A] {
+      private var current = 0
+      def hasNext = current < self.length
+      def next: A = {
+        val r = apply(current)
+        current += 1
+        r
+      }
+    }
+
+    override def take(n: Int): IndexedView[A] = new IndexedView.Take(this, n)
+    override def drop(n: Int): IndexedView[A] = new IndexedView.Drop(this, n)
+    override def map[B](f: A => B): IndexedView[B] = new IndexedView.Map(this, f)
+    def reverse: IndexedView[A] = new IndexedView.Reverse(this)
+  }
+
+  object IndexedView {
+
+    class Take[A](underlying: IndexedView[A], n: Int)
+    extends View.Take(underlying, n) with IndexedView[A] {
+      override def iterator = super.iterator // needed to avoid "conflicting overrides" error
+      def length = underlying.length min normN
+      def apply(i: Int) = underlying.apply(i)
+    }
+
+    class Drop[A](underlying: IndexedView[A], n: Int)
+    extends View.Take(underlying, n) with IndexedView[A] {
+      override def iterator = super.iterator
+      def length = (underlying.length - normN) max 0
+      def apply(i: Int) = underlying.apply(i + normN)
+    }
+
+    class Map[A, B](underlying: IndexedView[A], f: A => B)
+    extends View.Map(underlying, f) with IndexedView[B] {
+      override def iterator = super.iterator
+      def length = underlying.length
+      def apply(n: Int) = f(underlying.apply(n))
+    }
+
+    case class Reverse[A](underlying: IndexedView[A]) extends IndexedView[A] {
+      def length = underlying.length
+      def apply(i: Int) = underlying.apply(length - 1 - i)
+    }
+  }
+
+/* ---------- Iterators ---------------------------------------------------*/
+
+  /** A core Iterator class */
+  trait Iterator[+A] extends IterableOnce[A] { self =>
+    def hasNext: Boolean
+    def next(): A
+    def iterator = this
+    def foldLeft[B](z: B)(op: (B, A) => B): B =
+      if (hasNext) foldLeft(op(z, next))(op) else z
+    def foldRight[B](z: B)(op: (A, B) => B): B =
+      if (hasNext) op(next(), foldRight(z)(op)) else z
+    def foreach(f: A => Unit): Unit =
+      while (hasNext) f(next())
+    def indexWhere(p: A => Boolean): Int = {
+      var i = 0
+      while (hasNext) {
+        if (p(next())) return i
+        i += 1
+      }
+      -1
+    }
+    def length = {
+      var len = 0
+      while (hasNext) { len += 1; next() }
+      len
+    }
+    def filter(p: A => Boolean): Iterator[A] = new Iterator[A] {
+      private var hd: A = _
+      private var hdDefined: Boolean = false
+
+      def hasNext: Boolean = hdDefined || {
+        do {
+          if (!self.hasNext) return false
+          hd = self.next()
+        } while (!p(hd))
+        hdDefined = true
+        true
+      }
+
+      def next() =
+        if (hasNext) {
+          hdDefined = false
+          hd
+        }
+        else Iterator.empty.next()
+    }
+    def map[B](f: A => B): Iterator[B] = new Iterator[B] {
+      def hasNext = self.hasNext
+      def next() = f(self.next())
+    }
+
+    def flatMap[B](f: A => IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = Iterator.empty
+      private def current = {
+        while (!myCurrent.hasNext && self.hasNext)
+          myCurrent = f(self.next()).iterator
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def ++[B >: A](xs: IterableOnce[B]): Iterator[B] = new Iterator[B] {
+      private var myCurrent: Iterator[B] = self
+      private var first = true
+      private def current = {
+        if (!myCurrent.hasNext && first) {
+          myCurrent = xs.iterator
+          first = false
+        }
+        myCurrent
+      }
+      def hasNext = current.hasNext
+      def next() = current.next()
+    }
+    def take(n: Int): Iterator[A] = new Iterator[A] {
+      private var i = 0
+      def hasNext = self.hasNext && i < n
+      def next =
+        if (hasNext) {
+          i += 1
+          self.next()
+        }
+        else Iterator.empty.next()
+    }
+    def drop(n: Int): Iterator[A] = {
+      var i = 0
+      while (i < n && hasNext) {
+        next()
+        i += 1
+      }
+      this
+    }
+    def zip[B](that: IterableOnce[B]): Iterator[(A, B)] = new Iterator[(A, B)] {
+      val thatIterator = that.iterator
+      def hasNext = self.hasNext && thatIterator.hasNext
+      def next() = (self.next(), thatIterator.next())
+    }
+  }
+
+  object Iterator {
+    val empty: Iterator[Nothing] = new Iterator[Nothing] {
+      def hasNext = false
+      def next = throw new NoSuchElementException("next on empty iterator")
+    }
+    def apply[A](xs: A*): Iterator[A] = new IndexedView[A] {
+      val length = xs.length
+      def apply(n: Int) = xs(n)
+    }.iterator
+  }
+}