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