diff options
Diffstat (limited to 'src')
18 files changed, 400 insertions, 505 deletions
diff --git a/src/compiler/scala/tools/nsc/Global.scala b/src/compiler/scala/tools/nsc/Global.scala index 464fa1ad18..873a5947ed 100644 --- a/src/compiler/scala/tools/nsc/Global.scala +++ b/src/compiler/scala/tools/nsc/Global.scala @@ -341,12 +341,6 @@ class Global(var currentSettings: Settings, var reporter: Reporter) s"[search path for class files: ${classPath.asClassPathString}]" ) - // The current division between scala.reflect.* and scala.tools.nsc.* is pretty - // clunky. It is often difficult to have a setting influence something without having - // to create it on that side. For this one my strategy is a constant def at the file - // where I need it, and then an override in Global with the setting. - override protected val etaExpandKeepsStar = settings.etaExpandKeepsStar.value - def getSourceFile(f: AbstractFile): BatchSourceFile = new BatchSourceFile(f, reader read f) def getSourceFile(name: String): SourceFile = { diff --git a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala index b0815b0008..c7952ffe94 100644 --- a/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala +++ b/src/compiler/scala/tools/nsc/backend/jvm/BCodeBodyBuilder.scala @@ -168,7 +168,7 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { } else if (scalaPrimitives.isArraySet(code)) { val List(a1, a2) = args genLoad(a1, INT) - genLoad(a2) + genLoad(a2, elementType) generatedType = UNIT bc.astore(elementType) } else { @@ -630,7 +630,7 @@ abstract class BCodeBodyBuilder extends BCodeSkelBuilder { generatedType = methodBTypeFromSymbol(fun.symbol).returnType case Apply(fun, List(expr)) if currentRun.runDefinitions.isBox(fun.symbol) => - val nativeKind = tpeTK(expr) + val nativeKind = typeToBType(fun.symbol.firstParam.info) genLoad(expr, nativeKind) val MethodNameAndType(mname, methodType) = srBoxesRuntimeBoxToMethods(nativeKind) bc.invokestatic(srBoxesRunTimeRef.internalName, mname, methodType.descriptor, itf = false, app.pos) diff --git a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala index a3b9df1518..5455111674 100644 --- a/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala +++ b/src/compiler/scala/tools/nsc/settings/ScalaSettings.scala @@ -211,8 +211,6 @@ trait ScalaSettings extends AbsScalaSettings val Yreplclassbased = BooleanSetting ("-Yrepl-class-based", "Use classes to wrap REPL snippets instead of objects") val Yreploutdir = StringSetting ("-Yrepl-outdir", "path", "Write repl-generated classfiles to given output directory (use \"\" to generate a temporary dir)" , "") val YmethodInfer = BooleanSetting ("-Yinfer-argument-types", "Infer types for arguments of overridden methods.") - val etaExpandKeepsStar = BooleanSetting ("-Yeta-expand-keeps-star", "Eta-expand varargs methods to T* rather than Seq[T]. This is a temporary option to ease transition.").withDeprecationMessage(removalIn212) - val inferByName = BooleanSetting ("-Yinfer-by-name", "Allow inference of by-name types. This is a temporary option to ease transition. See SI-7899.").withDeprecationMessage(removalIn212) val YdisableFlatCpCaching = BooleanSetting ("-YdisableFlatCpCaching", "Do not cache flat classpath representation of classpath elements from jars across compiler instances.") val YpartialUnification = BooleanSetting ("-Ypartial-unification", "Enable partial unification in type constructor inference") val Yvirtpatmat = BooleanSetting ("-Yvirtpatmat", "Enable pattern matcher virtualization") @@ -321,8 +319,6 @@ trait ScalaSettings extends AbsScalaSettings val YoptLogInline = StringSetting("-Yopt-log-inline", "package/Class.method", "Print a summary of inliner activity; `_` to print all, prefix match to select.", "") - private def removalIn212 = "This flag is scheduled for removal in 2.12. If you have a case where you need this flag then please report a bug." - object YstatisticsPhases extends MultiChoiceEnumeration { val parser, typer, patmat, erasure, cleanup, jvm = Value } val Ystatistics = { val description = "Print compiler statistics for specific phases" diff --git a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala index 8f0625e58c..fde2f7bb03 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Contexts.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Contexts.scala @@ -1192,6 +1192,27 @@ trait Contexts { self: Analyzer => } res } + + final def lookupCompanionOf(original: Symbol): Symbol = { + lookupScopeEntry(original) match { + case null => NoSymbol + case entry => entry.owner.lookupCompanion(original) + } + } + + /** Search scopes in current and enclosing contexts for the definition of `symbol` */ + private def lookupScopeEntry(symbol: Symbol): ScopeEntry = { + var res: ScopeEntry = null + var ctx = this + while (res == null && ctx.outer != ctx) { + val s = ctx.scope lookupSymbolEntry symbol + if (s != null) + res = s + else + ctx = ctx.outer + } + res + } } //class Context /** A `Context` focussed on an `Import` tree */ diff --git a/src/compiler/scala/tools/nsc/typechecker/EtaExpansion.scala b/src/compiler/scala/tools/nsc/typechecker/EtaExpansion.scala index 97de2b6c85..5f4fa499b6 100644 --- a/src/compiler/scala/tools/nsc/typechecker/EtaExpansion.scala +++ b/src/compiler/scala/tools/nsc/typechecker/EtaExpansion.scala @@ -105,7 +105,7 @@ trait EtaExpansion { self: Analyzer => val origTpe = sym.tpe val isRepeated = definitions.isRepeatedParamType(origTpe) // SI-4176 Don't leak A* in eta-expanded function types. See t4176b.scala - val droppedStarTpe = if (settings.etaExpandKeepsStar) origTpe else dropIllegalStarTypes(origTpe) + val droppedStarTpe = dropIllegalStarTypes(origTpe) val valDef = ValDef(Modifiers(SYNTHETIC | PARAM), sym.name.toTermName, TypeTree(droppedStarTpe), EmptyTree) (valDef, isRepeated) } diff --git a/src/compiler/scala/tools/nsc/typechecker/Infer.scala b/src/compiler/scala/tools/nsc/typechecker/Infer.scala index 0071d66eb9..e8147dbf3a 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Infer.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Infer.scala @@ -936,10 +936,8 @@ trait Infer extends Checkable { def infer_s = map3(tparams, tvars, targs)((tparam, tvar, targ) => s"$tparam=$tvar/$targ") mkString "," printTyping(tree, s"infer expr instance from pt=$pt, $infer_s") - // SI-7899 inferring by-name types is unsound. The correct behaviour is conditional because the hole is - // exploited in Scalaz (Free.scala), as seen in: run/t7899-regression. - def dropByNameIfStrict(tp: Type): Type = if (settings.inferByName) tp else dropByName(tp) - def targsStrict = if (targs eq null) null else targs mapConserve dropByNameIfStrict + // SI-7899 inferring by-name types is unsound + def targsStrict = if (targs eq null) null else targs mapConserve dropByName if (keepNothings || (targs eq null)) { //@M: adjustTypeArgs fails if targs==null, neg/t0226 substExpr(tree, tparams, targsStrict, pt) diff --git a/src/compiler/scala/tools/nsc/typechecker/Namers.scala b/src/compiler/scala/tools/nsc/typechecker/Namers.scala index b445bc5837..395bda234b 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Namers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Namers.scala @@ -220,7 +220,10 @@ trait Namers extends MethodSynthesis { private def inCurrentScope(m: Symbol): Boolean = { if (owner.isClass) owner == m.owner - else m.owner.isClass && context.scope == m.owner.info.decls + else context.scope.lookupSymbolEntry(m) match { + case null => false + case entry => entry.owner eq context.scope + } } /** Enter symbol into context's scope and return symbol itself */ @@ -1953,10 +1956,7 @@ trait Namers extends MethodSynthesis { // use the lower-level scan through the current Context as a fall back. if (!currentRun.compiles(owner)) owner.initialize original.companionSymbol orElse { - ctx.lookup(original.name.companionName, owner).suchThat(sym => - (original.isTerm || sym.hasModuleFlag) && - (sym isCoDefinedWith original) - ) + ctx.lookupCompanionOf(original) } } diff --git a/src/compiler/scala/tools/nsc/typechecker/Typers.scala b/src/compiler/scala/tools/nsc/typechecker/Typers.scala index fc0a0368ab..e017c7d864 100644 --- a/src/compiler/scala/tools/nsc/typechecker/Typers.scala +++ b/src/compiler/scala/tools/nsc/typechecker/Typers.scala @@ -3401,7 +3401,7 @@ trait Typers extends Adaptations with Tags with TypersTracking with PatternTyper // governed by a) the argument types and b) the expected type val args1 = typedArgs(args, forArgMode(fun, mode)) val pts = args1.map(_.tpe.deconst) - val clone = fun.symbol.cloneSymbol + val clone = fun.symbol.cloneSymbol.withoutAnnotations val cloneParams = pts map (pt => clone.newValueParameter(currentUnit.freshTermName()).setInfo(pt)) val resultType = if (isFullyDefined(pt)) pt else ObjectTpe clone.modifyInfo(mt => copyMethodType(mt, cloneParams, resultType)) diff --git a/src/library/scala/collection/immutable/NumericRange.scala b/src/library/scala/collection/immutable/NumericRange.scala index fdf50960a3..ef3fa99971 100644 --- a/src/library/scala/collection/immutable/NumericRange.scala +++ b/src/library/scala/collection/immutable/NumericRange.scala @@ -115,14 +115,14 @@ extends AbstractSeq[T] with IndexedSeq[T] with Serializable { override def min[T1 >: T](implicit ord: Ordering[T1]): T = if (ord eq defaultOrdering(num)) { - if (num.signum(step) > 0) start + if (num.signum(step) > 0) head else last } else super.min(ord) override def max[T1 >: T](implicit ord: Ordering[T1]): T = if (ord eq defaultOrdering(num)) { if (num.signum(step) > 0) last - else start + else head } else super.max(ord) // Motivated by the desire for Double ranges with BigDecimal precision, diff --git a/src/library/scala/collection/immutable/StringLike.scala b/src/library/scala/collection/immutable/StringLike.scala index af8703293f..fce0f073aa 100644 --- a/src/library/scala/collection/immutable/StringLike.scala +++ b/src/library/scala/collection/immutable/StringLike.scala @@ -165,20 +165,14 @@ self => if (toString.endsWith(suffix)) toString.substring(0, toString.length() - suffix.length) else toString - /** Replace all literal occurrences of `literal` with the string `replacement`. - * This is equivalent to [[java.lang.String#replaceAll]] except that both arguments - * are appropriately quoted to avoid being interpreted as metacharacters. + /** Replace all literal occurrences of `literal` with the literal string `replacement`. + * This method is equivalent to [[java.lang.String#replace]]. * * @param literal the string which should be replaced everywhere it occurs * @param replacement the replacement string * @return the resulting string */ - def replaceAllLiterally(literal: String, replacement: String): String = { - val arg1 = Regex.quote(literal) - val arg2 = Regex.quoteReplacement(replacement) - - toString.replaceAll(arg1, arg2) - } + def replaceAllLiterally(literal: String, replacement: String): String = toString.replace(literal, replacement) /** For every line in this string: * diff --git a/src/library/scala/collection/immutable/Vector.scala b/src/library/scala/collection/immutable/Vector.scala index d9d925705f..1093084b9d 100644 --- a/src/library/scala/collection/immutable/Vector.scala +++ b/src/library/scala/collection/immutable/Vector.scala @@ -23,7 +23,7 @@ object Vector extends IndexedSeqFactory[Vector] { ReusableCBF.asInstanceOf[GenericCanBuildFrom[A]] private[immutable] val NIL = new Vector[Nothing](0, 0, 0) override def empty[A]: Vector[A] = NIL - + // Constants governing concat strategy for performance private final val Log2ConcatFaster = 5 private final val TinyAppendFaster = 2 @@ -71,12 +71,7 @@ extends AbstractSeq[A] with CustomParallelizable[A, ParVector[A]] { self => -override def companion: GenericCompanion[Vector] = Vector - - //assert(startIndex >= 0, startIndex+"<0") - //assert(startIndex <= endIndex, startIndex+">"+endIndex) - //assert(focus >= 0, focus+"<0") - //assert(focus <= endIndex, focus+">"+endIndex) + override def companion: GenericCompanion[Vector] = Vector private[immutable] var dirty = false @@ -100,8 +95,6 @@ override def companion: GenericCompanion[Vector] = Vector s } - - // can still be improved override /*SeqLike*/ def reverseIterator: Iterator[A] = new AbstractIterator[A] { private var i = self.length @@ -113,22 +106,18 @@ override def companion: GenericCompanion[Vector] = Vector } else Iterator.empty.next() } - // TODO: reverse - - // TODO: check performance of foreach/map etc. should override or not? // Ideally, clients will inline calls to map all the way down, including the iterator/builder methods. // In principle, escape analysis could even remove the iterator/builder allocations and do it // with local variables exclusively. But we're not quite there yet ... def apply(index: Int): A = { val idx = checkRangeConvert(index) - //println("get elem: "+index + "/"+idx + "(focus:" +focus+" xor:"+(idx^focus)+" depth:"+depth+")") getElem(idx, idx ^ focus) } private def checkRangeConvert(index: Int) = { val idx = index + startIndex - if (0 <= index && idx < endIndex) + if (index >= 0 && idx < endIndex) idx else throw new IndexOutOfBoundsException(index.toString) @@ -137,7 +126,7 @@ override def companion: GenericCompanion[Vector] = Vector // If we have a default builder, there are faster ways to perform some operations @inline private[this] def isDefaultCBF[A, B, That](bf: CanBuildFrom[Vector[A], B, That]): Boolean = (bf eq IndexedSeq.ReusableCBF) || (bf eq collection.immutable.Seq.ReusableCBF) || (bf eq collection.Seq.ReusableCBF) - + // SeqLike api override def updated[B >: A, That](index: Int, elem: B)(implicit bf: CanBuildFrom[Vector[A], B, That]): That = @@ -191,31 +180,36 @@ override def companion: GenericCompanion[Vector] = Vector Vector.empty } - override /*IterableLike*/ def head: A = { + override /*IterableLike*/ + def head: A = { if (isEmpty) throw new UnsupportedOperationException("empty.head") apply(0) } - override /*TraversableLike*/ def tail: Vector[A] = { + override /*TraversableLike*/ + def tail: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.tail") drop(1) } - override /*TraversableLike*/ def last: A = { + override /*TraversableLike*/ + def last: A = { if (isEmpty) throw new UnsupportedOperationException("empty.last") - apply(length-1) + apply(length - 1) } - override /*TraversableLike*/ def init: Vector[A] = { + override /*TraversableLike*/ + def init: Vector[A] = { if (isEmpty) throw new UnsupportedOperationException("empty.init") dropRight(1) } - override /*IterableLike*/ def slice(from: Int, until: Int): Vector[A] = + override /*IterableLike*/ + def slice(from: Int, until: Int): Vector[A] = take(until).drop(from) - override /*IterableLike*/ def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) - + override /*IterableLike*/ + def splitAt(n: Int): (Vector[A], Vector[A]) = (take(n), drop(n)) // concat (suboptimal but avoids worst performance gotchas) override def ++[B >: A, That](that: GenTraversableOnce[B])(implicit bf: CanBuildFrom[Vector[A], B, That]): That = { @@ -227,11 +221,11 @@ override def companion: GenericCompanion[Vector] = Vector val again = if (!that.isTraversableAgain) that.toVector else that.seq again.size match { // Often it's better to append small numbers of elements (or prepend if RHS is a vector) - case n if n <= TinyAppendFaster || n < (this.size >> Log2ConcatFaster) => + case n if n <= TinyAppendFaster || n < (this.size >>> Log2ConcatFaster) => var v: Vector[B] = this for (x <- again) v = v :+ x v.asInstanceOf[That] - case n if this.size < (n >> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => + case n if this.size < (n >>> Log2ConcatFaster) && again.isInstanceOf[Vector[_]] => var v = again.asInstanceOf[Vector[B]] val ri = this.reverseIterator while (ri.hasNext) v = ri.next +: v @@ -243,8 +237,6 @@ override def companion: GenericCompanion[Vector] = Vector else super.++(that.seq) } - - // semi-private api private[immutable] def updateAt[B >: A](index: Int, elem: B): Vector[B] = { @@ -253,11 +245,10 @@ override def companion: GenericCompanion[Vector] = Vector s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, idx, focus ^ idx) // if dirty commit changes; go to new pos and prepare for writing - s.display0(idx & 0x1f) = elem.asInstanceOf[AnyRef] + s.display0(idx & 31) = elem.asInstanceOf[AnyRef] s } - private def gotoPosWritable(oldIndex: Int, newIndex: Int, xor: Int) = if (dirty) { gotoPosWritable1(oldIndex, newIndex, xor) } else { @@ -272,7 +263,7 @@ override def companion: GenericCompanion[Vector] = Vector dirty = true } - private[immutable] def appendFront[B>:A](value: B): Vector[B] = { + private[immutable] def appendFront[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = (startIndex - 1) & ~31 val lo = (startIndex - 1) & 31 @@ -286,61 +277,46 @@ override def companion: GenericCompanion[Vector] = Vector s } else { - val freeSpace = ((1<<5*(depth)) - endIndex) // free space at the right given the current tree-structure depth - val shift = freeSpace & ~((1<<5*(depth-1))-1) // number of elements by which we'll shift right (only move at top level) - val shiftBlocks = freeSpace >>> 5*(depth-1) // number of top-level blocks + val freeSpace = (1 << (5 * depth)) - endIndex // free space at the right given the current tree-structure depth + val shift = freeSpace & ~((1 << (5 * (depth - 1))) - 1) // number of elements by which we'll shift right (only move at top level) + val shiftBlocks = freeSpace >>> (5 * (depth - 1)) // number of top-level blocks - //println("----- appendFront " + value + " at " + (startIndex - 1) + " reached block start") if (shift != 0) { // case A: we can shift right on the top level - debug() - //println("shifting right by " + shiftBlocks + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - if (depth > 1) { val newBlockIndex = blockIndex + shift val newFocus = focus + shift + val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // maybe create pos; prepare for writing s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex + 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - 1 + shift, endIndex + shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(0, shiftBlocks) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // prepare for writing - s.display0(shift-1) = value.asInstanceOf[AnyRef] - s.debug() + s.display0(shift - 1) = value.asInstanceOf[AnyRef] s } } else if (blockIndex < 0) { // case B: we need to move the whole structure - val move = (1 << 5*(depth+1)) - (1 << 5*(depth)) - //println("moving right by " + move + " at level " + (depth-1) + " (had "+freeSpace+" free space)") - + val move = (1 << (5 * (depth + 1))) - (1 << (5 * depth)) val newBlockIndex = blockIndex + move val newFocus = focus + move - val s = new Vector(startIndex - 1 + move, endIndex + move, newBlockIndex) s.initFrom(this) s.dirty = dirty - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) // could optimize: we know it will create a whole branch s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(s.depth == depth+1) s } else { val newBlockIndex = blockIndex @@ -351,31 +327,26 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth) s } - } } else { // empty vector, just insert single element at the back val elems = new Array[AnyRef](32) elems(31) = value.asInstanceOf[AnyRef] - val s = new Vector(31,32,0) + val s = new Vector(31, 32, 0) s.depth = 1 s.display0 = elems s } } - private[immutable] def appendBack[B>:A](value: B): Vector[B] = { -// //println("------- append " + value) -// debug() + private[immutable] def appendBack[B >: A](value: B): Vector[B] = { if (endIndex != startIndex) { val blockIndex = endIndex & ~31 val lo = endIndex & 31 if (endIndex != blockIndex) { - //println("will make writable block (from "+focus+") at: " + blockIndex) val s = new Vector(startIndex, endIndex + 1, blockIndex) s.initFrom(this) s.dirty = dirty @@ -383,41 +354,31 @@ override def companion: GenericCompanion[Vector] = Vector s.display0(lo) = value.asInstanceOf[AnyRef] s } else { - val shift = startIndex & ~((1<<5*(depth-1))-1) - val shiftBlocks = startIndex >>> 5*(depth-1) - - //println("----- appendBack " + value + " at " + endIndex + " reached block end") + val shift = startIndex & ~((1 << (5 * (depth - 1))) - 1) + val shiftBlocks = startIndex >>> (5 * (depth - 1)) if (shift != 0) { - debug() - //println("shifting left by " + shiftBlocks + " at level " + (depth-1) + " (had "+startIndex+" free space)") if (depth > 1) { val newBlockIndex = blockIndex - shift val newFocus = focus - shift + val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift left by n blocks - s.debug() s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - s.debug() - //assert(depth == s.depth) s } else { val newBlockIndex = blockIndex - 32 val newFocus = focus - //assert(newBlockIndex == 0) - //assert(newFocus == 0) - val s = new Vector(startIndex - shift, endIndex + 1 - shift, newBlockIndex) s.initFrom(this) s.dirty = dirty s.shiftTopLevel(shiftBlocks, 0) // shift right by n elements s.gotoPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(32 - shift) = value.asInstanceOf[AnyRef] - s.debug() s } } else { @@ -429,18 +390,13 @@ override def companion: GenericCompanion[Vector] = Vector s.dirty = dirty s.gotoFreshPosWritable(newFocus, newBlockIndex, newFocus ^ newBlockIndex) s.display0(lo) = value.asInstanceOf[AnyRef] - //assert(s.depth == depth+1) might or might not create new level! - if (s.depth == depth+1) { - //println("creating new level " + s.depth + " (had "+0+" free space)") - s.debug() - } s } } } else { val elems = new Array[AnyRef](32) elems(0) = value.asInstanceOf[AnyRef] - val s = new Vector(0,1,0) + val s = new Vector(0, 1, 0) s.depth = 1 s.display0 = elems s @@ -451,39 +407,39 @@ override def companion: GenericCompanion[Vector] = Vector // low-level implementation (needs cleanup, maybe move to util class) private def shiftTopLevel(oldLeft: Int, newLeft: Int) = (depth - 1) match { - case 0 => - display0 = copyRange(display0, oldLeft, newLeft) - case 1 => - display1 = copyRange(display1, oldLeft, newLeft) - case 2 => - display2 = copyRange(display2, oldLeft, newLeft) - case 3 => - display3 = copyRange(display3, oldLeft, newLeft) - case 4 => - display4 = copyRange(display4, oldLeft, newLeft) - case 5 => - display5 = copyRange(display5, oldLeft, newLeft) + case 0 => display0 = copyRange(display0, oldLeft, newLeft) + case 1 => display1 = copyRange(display1, oldLeft, newLeft) + case 2 => display2 = copyRange(display2, oldLeft, newLeft) + case 3 => display3 = copyRange(display3, oldLeft, newLeft) + case 4 => display4 = copyRange(display4, oldLeft, newLeft) + case 5 => display5 = copyRange(display5, oldLeft, newLeft) } private def zeroLeft(array: Array[AnyRef], index: Int): Unit = { - var i = 0; while (i < index) { array(i) = null; i+=1 } + var i = 0 + while (i < index) { + array(i) = null + i += 1 + } } private def zeroRight(array: Array[AnyRef], index: Int): Unit = { - var i = index; while (i < array.length) { array(i) = null; i+=1 } + var i = index + while (i < array.length) { + array(i) = null + i += 1 + } } private def copyLeft(array: Array[AnyRef], right: Int): Array[AnyRef] = { -// if (array eq null) -// println("OUCH!!! " + right + "/" + depth + "/"+startIndex + "/" + endIndex + "/" + focus) - val a2 = new Array[AnyRef](array.length) - java.lang.System.arraycopy(array, 0, a2, 0, right) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, 0, copy, 0, right) + copy } private def copyRight(array: Array[AnyRef], left: Int): Array[AnyRef] = { - val a2 = new Array[AnyRef](array.length) - java.lang.System.arraycopy(array, left, a2, left, a2.length - left) - a2 + val copy = new Array[AnyRef](array.length) + java.lang.System.arraycopy(array, left, copy, left, copy.length - left) + copy } private def preClean(depth: Int) = { @@ -515,38 +471,33 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is at index cutIndex and writable at level 0 private def cleanLeftEdge(cutIndex: Int) = { - if (cutIndex < (1 << 5)) { + if (cutIndex < (1 << 5)) { zeroLeft(display0, cutIndex) - } else - if (cutIndex < (1 << 10)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5)) - } else - if (cutIndex < (1 << 15)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10)) - } else - if (cutIndex < (1 << 20)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15)) - } else - if (cutIndex < (1 << 25)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20)) - } else - if (cutIndex < (1 << 30)) { - zeroLeft(display0, cutIndex & 0x1f) - display1 = copyRight(display1, (cutIndex >>> 5) & 0x1f) - display2 = copyRight(display2, (cutIndex >>> 10) & 0x1f) - display3 = copyRight(display3, (cutIndex >>> 15) & 0x1f) - display4 = copyRight(display4, (cutIndex >>> 20) & 0x1f) - display5 = copyRight(display5, (cutIndex >>> 25)) + } else if (cutIndex < (1 << 10)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, cutIndex >>> 5) + } else if (cutIndex < (1 << 15)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, cutIndex >>> 10) + } else if (cutIndex < (1 << 20)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, cutIndex >>> 15) + } else if (cutIndex < (1 << 25)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, cutIndex >>> 20) + } else if (cutIndex < (1 << 30)) { + zeroLeft(display0, cutIndex & 31) + display1 = copyRight(display1, (cutIndex >>> 5) & 31) + display2 = copyRight(display2, (cutIndex >>> 10) & 31) + display3 = copyRight(display3, (cutIndex >>> 15) & 31) + display4 = copyRight(display4, (cutIndex >>> 20) & 31) + display5 = copyRight(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } @@ -554,49 +505,43 @@ override def companion: GenericCompanion[Vector] = Vector // requires structure is writable and at index cutIndex private def cleanRightEdge(cutIndex: Int) = { - // we're actually sitting one block left if cutIndex lies on a block boundary // this means that we'll end up erasing the whole block!! - if (cutIndex <= (1 << 5)) { + if (cutIndex <= (1 << 5)) { zeroRight(display0, cutIndex) - } else - if (cutIndex <= (1 << 10)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (cutIndex >>> 5)) - } else - if (cutIndex <= (1 << 15)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (cutIndex >>> 10)) - } else - if (cutIndex <= (1 << 20)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (cutIndex >>> 15)) - } else - if (cutIndex <= (1 << 25)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (cutIndex >>> 20)) - } else - if (cutIndex <= (1 << 30)) { - zeroRight(display0, ((cutIndex-1) & 0x1f) + 1) - display1 = copyLeft(display1, (((cutIndex-1) >>> 5) & 0x1f) + 1) - display2 = copyLeft(display2, (((cutIndex-1) >>> 10) & 0x1f) + 1) - display3 = copyLeft(display3, (((cutIndex-1) >>> 15) & 0x1f) + 1) - display4 = copyLeft(display4, (((cutIndex-1) >>> 20) & 0x1f) + 1) - display5 = copyLeft(display5, (cutIndex >>> 25)) + } else if (cutIndex <= (1 << 10)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, cutIndex >>> 5) + } else if (cutIndex <= (1 << 15)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, cutIndex >>> 10) + } else if (cutIndex <= (1 << 20)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, cutIndex >>> 15) + } else if (cutIndex <= (1 << 25)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, cutIndex >>> 20) + } else if (cutIndex <= (1 << 30)) { + zeroRight(display0, ((cutIndex - 1) & 31) + 1) + display1 = copyLeft(display1, (((cutIndex - 1) >>> 5) & 31) + 1) + display2 = copyLeft(display2, (((cutIndex - 1) >>> 10) & 31) + 1) + display3 = copyLeft(display3, (((cutIndex - 1) >>> 15) & 31) + 1) + display4 = copyLeft(display4, (((cutIndex - 1) >>> 20) & 31) + 1) + display5 = copyLeft(display5, cutIndex >>> 25) } else { throw new IllegalArgumentException() } } private def requiredDepth(xor: Int) = { - if (xor < (1 << 5)) 1 + if (xor < (1 << 5)) 1 else if (xor < (1 << 10)) 2 else if (xor < (1 << 15)) 3 else if (xor < (1 << 20)) 4 @@ -609,24 +554,11 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = cutIndex & ~31 val xor = cutIndex ^ (endIndex - 1) val d = requiredDepth(xor) - val shift = (cutIndex & ~((1 << (5*d))-1)) - - //println("cut front at " + cutIndex + ".." + endIndex + " (xor: "+xor+" shift: " + shift + " d: " + d +")") - -/* - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) - s.initFrom(this) - if (s.depth > 1) - s.gotoPos(blockIndex, focus ^ blockIndex) - s.depth = d - s.stabilize(blockIndex-shift) - s.cleanLeftEdge(cutIndex-shift) - s -*/ + val shift = cutIndex & ~((1 << (5 * d)) - 1) // need to init with full display iff going to cutIndex requires swapping block at level >= d - val s = new Vector(cutIndex-shift, endIndex-shift, blockIndex-shift) + val s = new Vector(cutIndex - shift, endIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) @@ -639,25 +571,18 @@ override def companion: GenericCompanion[Vector] = Vector val blockIndex = (cutIndex - 1) & ~31 val xor = startIndex ^ (cutIndex - 1) val d = requiredDepth(xor) - val shift = (startIndex & ~((1 << (5*d))-1)) - -/* - println("cut back at " + startIndex + ".." + cutIndex + " (xor: "+xor+" d: " + d +")") - if (cutIndex == blockIndex + 32) - println("OUCH!!!") -*/ - val s = new Vector(startIndex-shift, cutIndex-shift, blockIndex-shift) + val shift = startIndex & ~((1 << (5 * d)) - 1) + + val s = new Vector(startIndex - shift, cutIndex - shift, blockIndex - shift) s.initFrom(this) s.dirty = dirty s.gotoPosWritable(focus, blockIndex, focus ^ blockIndex) s.preClean(d) - s.cleanRightEdge(cutIndex-shift) + s.cleanRightEdge(cutIndex - shift) s } - } - class VectorIterator[+A](_startIndex: Int, endIndex: Int) extends AbstractIterator[A] with Iterator[A] @@ -680,7 +605,7 @@ extends AbstractIterator[A] if (lo == endLo) { if (blockIndex + lo < endIndex) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStart(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex @@ -707,7 +632,7 @@ extends AbstractIterator[A] } /** A class to build instances of `Vector`. This builder is reusable. */ -final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorPointer[A @uncheckedVariance] { +final class VectorBuilder[A]() extends ReusableBuilder[A, Vector[A]] with VectorPointer[A @uncheckedVariance] { // possible alternative: start with display0 = null, blockIndex = -32, lo = 32 // to avoid allocating initial array if the result will be empty anyways @@ -718,9 +643,9 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP private var blockIndex = 0 private var lo = 0 - def += (elem: A): this.type = { + def +=(elem: A): this.type = { if (lo >= display0.length) { - val newBlockIndex = blockIndex+32 + val newBlockIndex = blockIndex + 32 gotoNextBlockStartWritable(newBlockIndex, blockIndex ^ newBlockIndex) blockIndex = newBlockIndex lo = 0 @@ -730,8 +655,7 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP this } - override def ++=(xs: TraversableOnce[A]): this.type = - super.++=(xs) + override def ++=(xs: TraversableOnce[A]): this.type = super.++=(xs) def result: Vector[A] = { val size = blockIndex + lo @@ -751,10 +675,8 @@ final class VectorBuilder[A]() extends ReusableBuilder[A,Vector[A]] with VectorP } } - - private[immutable] trait VectorPointer[T] { - private[immutable] var depth: Int = _ + private[immutable] var depth: Int = _ private[immutable] var display0: Array[AnyRef] = _ private[immutable] var display1: Array[AnyRef] = _ private[immutable] var display2: Array[AnyRef] = _ @@ -799,98 +721,102 @@ private[immutable] trait VectorPointer[T] { } } - // requires structure is at pos oldIndex = xor ^ index private[immutable] final def getElem(index: Int, xor: Int): T = { - if (xor < (1 << 5)) { // level = 0 - display0(index & 31).asInstanceOf[T] - } else - if (xor < (1 << 10)) { // level = 1 - display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 15)) { // level = 2 - display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 20)) { // level = 3 - display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 25)) { // level = 4 - display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else - if (xor < (1 << 30)) { // level = 5 - display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]]((index >> 20) & 31).asInstanceOf[Array[AnyRef]]((index >> 15) & 31).asInstanceOf[Array[AnyRef]]((index >> 10) & 31).asInstanceOf[Array[AnyRef]]((index >> 5) & 31).asInstanceOf[Array[AnyRef]](index & 31).asInstanceOf[T] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + (display0 + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 10)) { // level = 1 + (display1 + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 15)) { // level = 2 + (display2 + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 20)) { // level = 3 + (display3 + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 25)) { // level = 4 + (display4 + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else if (xor < (1 << 30)) { // level = 5 + (display5 + ((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + ((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + (index & 31).asInstanceOf[T]) + } else { // level = 6 throw new IllegalArgumentException() } } - // go to specific position // requires structure is at pos oldIndex = xor ^ index, // ensures structure is at pos index private[immutable] final def gotoPos(index: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 (could maybe removed) - } else - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start pos + } else if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else { // level = 6 throw new IllegalArgumentException() } } - - // USED BY ITERATOR // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStart(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - display0 = display1((index >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 15)) { // level = 2 - display1 = display2((index >> 10) & 31).asInstanceOf[Array[AnyRef]] + if (xor < (1 << 10)) { // level = 1 + display0 = display1((index >>> 5) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 15)) { // level = 2 + display1 = display2((index >>> 10) & 31).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 - display2 = display3((index >> 15) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 20)) { // level = 3 + display2 = display3((index >>> 15) & 31).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 - display3 = display4((index >> 20) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 25)) { // level = 4 + display3 = display4((index >>> 20) & 31).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 - display4 = display5((index >> 25) & 31).asInstanceOf[Array[AnyRef]] + } else if (xor < (1 << 30)) { // level = 5 + display4 = display5((index >>> 25) & 31).asInstanceOf[Array[AnyRef]] display3 = display4(0).asInstanceOf[Array[AnyRef]] display2 = display3(0).asInstanceOf[Array[AnyRef]] display1 = display2(0).asInstanceOf[Array[AnyRef]] display0 = display1(0).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } @@ -899,73 +825,65 @@ private[immutable] trait VectorPointer[T] { // xor: oldIndex ^ index private[immutable] final def gotoNextBlockStartWritable(index: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 10)) { // level = 1 - if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth+=1} + if (xor < (1 << 10)) { // level = 1 + if (depth == 1) { display1 = new Array(32); display1(0) = display0; depth += 1 } display0 = new Array(32) - display1((index >> 5) & 31) = display0 - } else - if (xor < (1 << 15)) { // level = 2 - if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth+=1} + display1((index >>> 5) & 31) = display0 + } else if (xor < (1 << 15)) { // level = 2 + if (depth == 2) { display2 = new Array(32); display2(0) = display1; depth += 1 } display0 = new Array(32) display1 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - } else - if (xor < (1 << 20)) { // level = 3 - if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + } else if (xor < (1 << 20)) { // level = 3 + if (depth == 3) { display3 = new Array(32); display3(0) = display2; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - } else - if (xor < (1 << 25)) { // level = 4 - if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + } else if (xor < (1 << 25)) { // level = 4 + if (depth == 4) { display4 = new Array(32); display4(0) = display3; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - } else - if (xor < (1 << 30)) { // level = 5 - if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth+=1} + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + } else if (xor < (1 << 30)) { // level = 5 + if (depth == 5) { display5 = new Array(32); display5(0) = display4; depth += 1 } display0 = new Array(32) display1 = new Array(32) display2 = new Array(32) display3 = new Array(32) display4 = new Array(32) - display1((index >> 5) & 31) = display0 - display2((index >> 10) & 31) = display1 - display3((index >> 15) & 31) = display2 - display4((index >> 20) & 31) = display3 - display5((index >> 25) & 31) = display4 - } else { // level = 6 + display1((index >>> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display3((index >>> 15) & 31) = display2 + display4((index >>> 20) & 31) = display3 + display5((index >>> 25) & 31) = display4 + } else { // level = 6 throw new IllegalArgumentException() } } - - // STUFF BELOW USED BY APPEND / UPDATE - private[immutable] final def copyOf(a: Array[AnyRef]) = { - val b = new Array[AnyRef](a.length) - java.lang.System.arraycopy(a, 0, b, 0, a.length) - b + private[immutable] final def copyOf(a: Array[AnyRef]): Array[AnyRef] = { + val copy = new Array[AnyRef](a.length) + java.lang.System.arraycopy(a, 0, copy, 0, a.length) + copy } - private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int) = { - //println("copy and null") + private[immutable] final def nullSlotAndCopy(array: Array[AnyRef], index: Int): Array[AnyRef] = { val x = array(index) array(index) = null copyOf(x.asInstanceOf[Array[AnyRef]]) } - // make sure there is no aliasing // requires structure is at pos index // ensures structure is clean and at pos index and writable at all levels except 0 @@ -977,40 +895,39 @@ private[immutable] trait VectorPointer[T] { display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display5((index >> 25) & 31) = display4 - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display5((index >>> 25) & 31) = display4 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 4 => display4 = copyOf(display4) display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display4((index >> 20) & 31) = display3 - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display4((index >>> 20) & 31) = display3 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 3 => display3 = copyOf(display3) display2 = copyOf(display2) display1 = copyOf(display1) - display3((index >> 15) & 31) = display2 - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display3((index >>> 15) & 31) = display2 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 2 => display2 = copyOf(display2) display1 = copyOf(display1) - display2((index >> 10) & 31) = display1 - display1((index >> 5) & 31) = display0 + display2((index >>> 10) & 31) = display1 + display1((index >>> 5) & 31) = display0 case 1 => display1 = copyOf(display1) - display1((index >> 5) & 31) = display0 + display1((index >>> 5) & 31) = display0 case 0 => } - /// USED IN UPDATE AND APPEND BACK // prepare for writing at an existing position @@ -1020,29 +937,29 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def gotoPosWritable0(newIndex: Int, xor: Int): Unit = (depth - 1) match { case 5 => display5 = copyOf(display5) - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 4 => display4 = copyOf(display4) - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 3 => display3 = copyOf(display3) - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 2 => display2 = copyOf(display2) - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 1 => display1 = copyOf(display1) - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) case 0 => display0 = copyOf(display0) } @@ -1051,64 +968,59 @@ private[immutable] trait VectorPointer[T] { // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { - if (xor < (1 << 5)) { // level = 0 + if (xor < (1 << 5)) { // level = 0 display0 = copyOf(display0) - } else - if (xor < (1 << 10)) { // level = 1 + } else if (xor < (1 << 10)) { // level = 1 display1 = copyOf(display1) - display1((oldIndex >> 5) & 31) = display0 - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31) - } else - if (xor < (1 << 15)) { // level = 2 + display1((oldIndex >>> 5) & 31) = display0 + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 15)) { // level = 2 display1 = copyOf(display1) display2 = copyOf(display2) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 20)) { // level = 3 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 20)) { // level = 3 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 25)) { // level = 4 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 25)) { // level = 4 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else - if (xor < (1 << 30)) { // level = 5 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else if (xor < (1 << 30)) { // level = 5 display1 = copyOf(display1) display2 = copyOf(display2) display3 = copyOf(display3) display4 = copyOf(display4) display5 = copyOf(display5) - display1((oldIndex >> 5) & 31) = display0 - display2((oldIndex >> 10) & 31) = display1 - display3((oldIndex >> 15) & 31) = display2 - display4((oldIndex >> 20) & 31) = display3 - display5((oldIndex >> 25) & 31) = display4 - display4 = nullSlotAndCopy(display5, (newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] - display3 = nullSlotAndCopy(display4, (newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] - display2 = nullSlotAndCopy(display3, (newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] - display1 = nullSlotAndCopy(display2, (newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] - display0 = nullSlotAndCopy(display1, (newIndex >> 5) & 31).asInstanceOf[Array[AnyRef]] - } else { // level = 6 + display1((oldIndex >>> 5) & 31) = display0 + display2((oldIndex >>> 10) & 31) = display1 + display3((oldIndex >>> 15) & 31) = display2 + display4((oldIndex >>> 20) & 31) = display3 + display5((oldIndex >>> 25) & 31) = display4 + display4 = nullSlotAndCopy(display5, (newIndex >>> 25) & 31) + display3 = nullSlotAndCopy(display4, (newIndex >>> 20) & 31) + display2 = nullSlotAndCopy(display3, (newIndex >>> 15) & 31) + display1 = nullSlotAndCopy(display2, (newIndex >>> 10) & 31) + display0 = nullSlotAndCopy(display1, (newIndex >>> 5) & 31) + } else { // level = 6 throw new IllegalArgumentException() } } @@ -1118,117 +1030,83 @@ private[immutable] trait VectorPointer[T] { private[immutable] final def copyRange(array: Array[AnyRef], oldLeft: Int, newLeft: Int) = { val elems = new Array[AnyRef](32) - java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft,oldLeft)) + java.lang.System.arraycopy(array, oldLeft, elems, newLeft, 32 - math.max(newLeft, oldLeft)) elems } - - // USED IN APPEND // create a new block at the bottom level (and possibly nodes on its path) and prepares for writing // requires structure is clean and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable0(oldIndex: Int, newIndex: Int, xor: Int): Unit = { // goto block start pos - if (xor < (1 << 5)) { // level = 0 - //println("XXX clean with low xor") - } else - if (xor < (1 << 10)) { // level = 1 + if (xor < (1 << 5)) { // level = 0 + // we're already at the block start + } else if (xor < (1 << 10)) { // level = 1 if (depth == 1) { display1 = new Array(32) - display1((oldIndex >> 5) & 31) = display0 - depth +=1 + display1((oldIndex >>> 5) & 31) = display0 + depth += 1 } display0 = new Array(32) - } else - if (xor < (1 << 15)) { // level = 2 + } else if (xor < (1 << 15)) { // level = 2 if (depth == 2) { display2 = new Array(32) - display2((oldIndex >> 10) & 31) = display1 - depth +=1 + display2((oldIndex >>> 10) & 31) = display1 + depth += 1 } - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 20)) { // level = 3 + } else if (xor < (1 << 20)) { // level = 3 if (depth == 3) { display3 = new Array(32) - display3((oldIndex >> 15) & 31) = display2 - depth +=1 + display3((oldIndex >>> 15) & 31) = display2 + depth += 1 } - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 25)) { // level = 4 + } else if (xor < (1 << 25)) { // level = 4 if (depth == 4) { display4 = new Array(32) - display4((oldIndex >> 20) & 31) = display3 - depth +=1 + display4((oldIndex >>> 20) & 31) = display3 + depth += 1 } - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else - if (xor < (1 << 30)) { // level = 5 + } else if (xor < (1 << 30)) { // level = 5 if (depth == 5) { display5 = new Array(32) - display5((oldIndex >> 25) & 31) = display4 - depth +=1 + display5((oldIndex >>> 25) & 31) = display4 + depth += 1 } - display4 = display5((newIndex >> 25) & 31).asInstanceOf[Array[AnyRef]] + display4 = display5((newIndex >>> 25) & 31).asInstanceOf[Array[AnyRef]] if (display4 == null) display4 = new Array(32) - display3 = display4((newIndex >> 20) & 31).asInstanceOf[Array[AnyRef]] + display3 = display4((newIndex >>> 20) & 31).asInstanceOf[Array[AnyRef]] if (display3 == null) display3 = new Array(32) - display2 = display3((newIndex >> 15) & 31).asInstanceOf[Array[AnyRef]] + display2 = display3((newIndex >>> 15) & 31).asInstanceOf[Array[AnyRef]] if (display2 == null) display2 = new Array(32) - display1 = display2((newIndex >> 10) & 31).asInstanceOf[Array[AnyRef]] + display1 = display2((newIndex >>> 10) & 31).asInstanceOf[Array[AnyRef]] if (display1 == null) display1 = new Array(32) display0 = new Array(32) - } else { // level = 6 + } else { // level = 6 throw new IllegalArgumentException() } } - // requires structure is dirty and at pos oldIndex, // ensures structure is dirty and at pos newIndex and writable at level 0 private[immutable] final def gotoFreshPosWritable1(oldIndex: Int, newIndex: Int, xor: Int): Unit = { stabilize(oldIndex) gotoFreshPosWritable0(oldIndex, newIndex, xor) } - - - - - // DEBUG STUFF - - private[immutable] def debug(): Unit = { - return -/* - //println("DISPLAY 5: " + display5 + " ---> " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 4: " + display4 + " ---> " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 3: " + display3 + " ---> " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 2: " + display2 + " ---> " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 1: " + display1 + " ---> " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x + "->" +x.asInstanceOf[Array[AnyRef]].mkString("")).mkString(" ") else "null")) - //println("DISPLAY 0: " + display0 + " ---> " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) -*/ - //println("DISPLAY 5: " + (if (display5 ne null) display5.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 4: " + (if (display4 ne null) display4.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 3: " + (if (display3 ne null) display3.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 2: " + (if (display2 ne null) display2.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 1: " + (if (display1 ne null) display1.map(x=> if (x eq null) "." else x.asInstanceOf[Array[AnyRef]].deepMkString("[","","]")).mkString(" ") else "null")) - //println("DISPLAY 0: " + (if (display0 ne null) display0.map(x=> if (x eq null) "." else x.toString).mkString(" ") else "null")) - } - - } - diff --git a/src/library/scala/collection/mutable/FlatHashTable.scala b/src/library/scala/collection/mutable/FlatHashTable.scala index 25cc873b82..8c4115b1dd 100644 --- a/src/library/scala/collection/mutable/FlatHashTable.scala +++ b/src/library/scala/collection/mutable/FlatHashTable.scala @@ -10,6 +10,9 @@ package scala package collection package mutable +import java.lang.Integer.rotateRight +import scala.util.hashing.byteswap32 + /** An implementation class backing a `HashSet`. * * This trait is used internally. It can be mixed in with various collections relying on @@ -415,20 +418,7 @@ private[collection] object FlatHashTable { // so that: protected final def sizeMapBucketSize = 1 << sizeMapBucketBitSize - protected final def improve(hcode: Int, seed: Int) = { - //var h: Int = hcode + ~(hcode << 9) - //h = h ^ (h >>> 14) - //h = h + (h << 4) - //h ^ (h >>> 10) - - val improved= scala.util.hashing.byteswap32(hcode) - - // for the remainder, see SI-5293 - // to ensure that different bits are used for different hash tables, we have to rotate based on the seed - val rotation = seed % 32 - val rotated = (improved >>> rotation) | (improved << (32 - rotation)) - rotated - } + protected final def improve(hcode: Int, seed: Int) = rotateRight(byteswap32(hcode), seed) /** * Elems have type A, but we store AnyRef in the table. Plus we need to deal with diff --git a/src/library/scala/collection/mutable/HashTable.scala b/src/library/scala/collection/mutable/HashTable.scala index 776eafaccc..445217ebef 100644 --- a/src/library/scala/collection/mutable/HashTable.scala +++ b/src/library/scala/collection/mutable/HashTable.scala @@ -12,6 +12,9 @@ package scala package collection package mutable +import java.lang.Integer.rotateRight +import scala.util.hashing.byteswap32 + /** This class can be used to construct data structures that are based * on hashtables. Class `HashTable[A]` implements a hashtable * that maps keys of type `A` to values of the fully abstract @@ -424,11 +427,7 @@ private[collection] object HashTable { * }}} * the rest of the computation is due to SI-5293 */ - protected final def improve(hcode: Int, seed: Int): Int = { - val hash = scala.util.hashing.byteswap32(hcode) - val shift = seed & ((1 << 5) - 1) - (hash >>> shift) | (hash << (32 - shift)) - } + protected final def improve(hcode: Int, seed: Int): Int = rotateRight(byteswap32(hcode), seed) } /** diff --git a/src/library/scala/concurrent/forkjoin/package.scala b/src/library/scala/concurrent/forkjoin/package.scala index 1915e25d7b..889890e30b 100644 --- a/src/library/scala/concurrent/forkjoin/package.scala +++ b/src/library/scala/concurrent/forkjoin/package.scala @@ -25,7 +25,7 @@ package object forkjoin { @deprecated("use java.util.concurrent.ForkJoinTask directly, instead of this alias", "2.12.0") type ForkJoinTask[T] = juc.ForkJoinTask[T] @deprecated("use java.util.concurrent.ForkJoinTask directly, instead of this alias", "2.12.0") - object ForkJoinTask { + object ForkJoinTask extends scala.Serializable { def adapt(runnable: Runnable): ForkJoinTask[_] = juc.ForkJoinTask.adapt(runnable) def adapt[T](callable: juc.Callable[_ <: T]): ForkJoinTask[T] = juc.ForkJoinTask.adapt(callable) def adapt[T](runnable: Runnable, result: T): ForkJoinTask[T] = juc.ForkJoinTask.adapt(runnable, result) @@ -51,7 +51,7 @@ package object forkjoin { @deprecated("use java.util.concurrent.ThreadLocalRandom directly, instead of this alias", "2.12.0") type ThreadLocalRandom = juc.ThreadLocalRandom @deprecated("use java.util.concurrent.ThreadLocalRandom directly, instead of this alias", "2.12.0") - object ThreadLocalRandom { + object ThreadLocalRandom extends scala.Serializable { // For source compatibility, current must declare the empty argument list. // Having no argument list makes more sense since it doesn't have any side effects, // but existing callers will break if they invoked it as `current()`. diff --git a/src/reflect/scala/reflect/internal/Definitions.scala b/src/reflect/scala/reflect/internal/Definitions.scala index fc7e184918..19460af27f 100644 --- a/src/reflect/scala/reflect/internal/Definitions.scala +++ b/src/reflect/scala/reflect/internal/Definitions.scala @@ -537,7 +537,8 @@ trait Definitions extends api.StandardDefinitions { lazy val ScalaSignatureAnnotation = requiredClass[scala.reflect.ScalaSignature] lazy val ScalaLongSignatureAnnotation = requiredClass[scala.reflect.ScalaLongSignature] - lazy val MethodHandle = getClassIfDefined("java.lang.invoke.MethodHandle") + lazy val MethodHandleClass = getClassIfDefined("java.lang.invoke.MethodHandle") + lazy val VarHandleClass = getClassIfDefined("java.lang.invoke.VarHandle") // Option classes lazy val OptionClass: ClassSymbol = requiredClass[Option[_]] @@ -1567,9 +1568,12 @@ trait Definitions extends api.StandardDefinitions { lazy val PartialManifestClass = getTypeMember(ReflectPackage, tpnme.ClassManifest) lazy val ManifestSymbols = Set[Symbol](PartialManifestClass, FullManifestClass, OptManifestClass) + private lazy val PolymorphicSignatureClass = MethodHandleClass.companionModule.info.decl(TypeName("PolymorphicSignature")) - def isPolymorphicSignature(sym: Symbol) = PolySigMethods(sym) - private lazy val PolySigMethods: Set[Symbol] = Set[Symbol](MethodHandle.info.decl(sn.Invoke), MethodHandle.info.decl(sn.InvokeExact)).filter(_.exists) + def isPolymorphicSignature(sym: Symbol) = sym != null && sym.isJavaDefined && { + val owner = sym.safeOwner + (owner == MethodHandleClass || owner == VarHandleClass) && sym.hasAnnotation(PolymorphicSignatureClass) + } lazy val Scala_Java8_CompatPackage = rootMirror.getPackageIfDefined("scala.runtime.java8") } diff --git a/src/reflect/scala/reflect/internal/Scopes.scala b/src/reflect/scala/reflect/internal/Scopes.scala index a7bb127506..32ce02bdd6 100644 --- a/src/reflect/scala/reflect/internal/Scopes.scala +++ b/src/reflect/scala/reflect/internal/Scopes.scala @@ -282,6 +282,34 @@ trait Scopes extends api.Scopes { self: SymbolTable => } } + final def lookupSymbolEntry(sym: Symbol): ScopeEntry = { + var e = lookupEntry(sym.name) + while (e ne null) { + if (e.sym == sym) return e + e = lookupNextEntry(e) + } + null + } + + final def lookupCompanion(original: Symbol): Symbol = { + lookupSymbolEntry(original) match { + case null => + case entry => + var e = lookupEntry(original.name.companionName) + while (e != null) { + // 1) Must be owned by the same Scope, to ensure that in + // `{ class C; { ...; object C } }`, the class is not seen as a comaniopn of the object. + // 2) Must be a class and module symbol, so that `{ class C; def C }` or `{ type T; object T }` are not companions. + def isClassAndModule(sym1: Symbol, sym2: Symbol) = sym1.isClass && sym2.isModule + if ((e.owner eq entry.owner) && (isClassAndModule(original, e.sym) || isClassAndModule(e.sym, original))) { + return if (e.sym.isCoDefinedWith(original)) e.sym else NoSymbol + } + e = lookupNextEntry(e) + } + } + NoSymbol + } + /** lookup a symbol entry matching given name. * @note from Martin: I believe this is a hotspot or will be one * in future versions of the type system. I have reverted the previous diff --git a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala index 08219c0634..de065d0b5d 100644 --- a/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala +++ b/src/reflect/scala/reflect/internal/tpe/TypeMaps.scala @@ -53,14 +53,6 @@ private[internal] trait TypeMaps { } } - // Set to true for A* => Seq[A] - // (And it will only rewrite A* in method result types.) - // This is the pre-existing behavior. - // Or false for Seq[A] => Seq[A] - // (It will rewrite A* everywhere but method parameters.) - // This is the specified behavior. - protected def etaExpandKeepsStar = false - /** Turn any T* types into Seq[T] except when * in method parameter position. */ @@ -74,7 +66,7 @@ private[internal] trait TypeMaps { case TypeRef(_, RepeatedParamClass, arg :: Nil) => seqType(arg) case _ => - if (etaExpandKeepsStar) tp else mapOver(tp) + mapOver(tp) } } diff --git a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala index d5d62b2203..95d6662d14 100644 --- a/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala +++ b/src/reflect/scala/reflect/runtime/JavaUniverseForce.scala @@ -323,7 +323,8 @@ trait JavaUniverseForce { self: runtime.JavaUniverse => definitions.QuasiquoteClass_api_unapply definitions.ScalaSignatureAnnotation definitions.ScalaLongSignatureAnnotation - definitions.MethodHandle + definitions.MethodHandleClass + definitions.VarHandleClass definitions.OptionClass definitions.OptionModule definitions.SomeClass |