diff options
-rw-r--r-- | bincompat-forward.whitelist.conf | 53 | ||||
-rw-r--r-- | spec/05-classes-and-objects.md | 1 | ||||
-rw-r--r-- | src/library/scala/collection/immutable/List.scala | 2 | ||||
-rw-r--r-- | src/library/scala/util/Sorting.scala | 712 | ||||
-rw-r--r-- | src/repl/scala/tools/nsc/interpreter/IMain.scala | 48 | ||||
-rw-r--r-- | src/repl/scala/tools/nsc/interpreter/Imports.scala | 24 | ||||
-rw-r--r-- | test/files/run/repl-serialization.check | 25 | ||||
-rw-r--r-- | test/files/run/repl-serialization.scala | 68 | ||||
-rw-r--r-- | test/files/run/t7747-repl.check | 41 | ||||
-rw-r--r-- | test/files/run/t7747-repl.scala | 6 | ||||
-rw-r--r-- | test/junit/scala/util/SortingTest.scala | 69 |
11 files changed, 547 insertions, 502 deletions
diff --git a/bincompat-forward.whitelist.conf b/bincompat-forward.whitelist.conf index 3808083dd3..8fadb65f39 100644 --- a/bincompat-forward.whitelist.conf +++ b/bincompat-forward.whitelist.conf @@ -319,6 +319,59 @@ filter { { matchName="scala.util.Random.scala$util$Random$$nextAlphaNum$1" problemName=MissingMethodProblem + }, + // Nominally private but in practice JVM-visible methods for reworked scala.util.Sorting + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$default$5" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mBc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mFc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mJc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mCc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mSc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$insertionSort" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mZc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mDc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSort$mIc$sp" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$mergeSorted" + problemName=MissingMethodProblem + }, + { + matchName="scala.util.Sorting.scala$util$Sorting$$booleanSort" + problemName=MissingMethodProblem } ] } diff --git a/spec/05-classes-and-objects.md b/spec/05-classes-and-objects.md index 28abe6c3bc..8be792d3cb 100644 --- a/spec/05-classes-and-objects.md +++ b/spec/05-classes-and-objects.md @@ -395,6 +395,7 @@ class C extends A with B { type T <: C } Let $C$ be a class type. The _inheritance closure_ of $C$ is the smallest set $\mathscr{S}$ of types such that +- $C$ is in $\mathscr{S}$. - If $T$ is in $\mathscr{S}$, then every type $T'$ which forms syntactically a part of $T$ is also in $\mathscr{S}$. - If $T$ is a class type in $\mathscr{S}$, then all [parents](#templates) diff --git a/src/library/scala/collection/immutable/List.scala b/src/library/scala/collection/immutable/List.scala index 254f14f13c..82e38d3549 100644 --- a/src/library/scala/collection/immutable/List.scala +++ b/src/library/scala/collection/immutable/List.scala @@ -462,6 +462,7 @@ object List extends SeqFactory[List] { private class SerializationProxy[A](@transient private var orig: List[A]) extends Serializable { private def writeObject(out: ObjectOutputStream) { + out.defaultWriteObject() var xs: List[A] = orig while (!xs.isEmpty) { out.writeObject(xs.head) @@ -473,6 +474,7 @@ object List extends SeqFactory[List] { // Java serialization calls this before readResolve during de-serialization. // Read the whole list and store it in `orig`. private def readObject(in: ObjectInputStream) { + in.defaultReadObject() val builder = List.newBuilder[A] while (true) in.readObject match { case ListSerializeEnd => diff --git a/src/library/scala/util/Sorting.scala b/src/library/scala/util/Sorting.scala index 2e021ad9d9..ee2bdbc4a7 100644 --- a/src/library/scala/util/Sorting.scala +++ b/src/library/scala/util/Sorting.scala @@ -1,6 +1,6 @@ /* __ *\ ** ________ ___ / / ___ Scala API ** -** / __/ __// _ | / / / _ | (c) 2006-2009, Ross Judson ** +** / __/ __// _ | / / / _ | (c) 2006-2015, LAMP/EPFL ** ** __\ \/ /__/ __ |/ /__/ __ | http://scala-lang.org/ ** ** /____/\___/_/ |_/____/_/ | | ** ** |/ ** @@ -9,518 +9,276 @@ package scala package util -import scala.reflect.{ ClassTag, classTag } -import scala.math.{ Ordering, max, min } +import scala.reflect.ClassTag +import scala.math.Ordering -/** The Sorting object provides functions that can sort various kinds of - * objects. You can provide a comparison function, or you can request a sort - * of items that are viewable as [[scala.math.Ordered]]. Some sorts that - * operate directly on a subset of value types are also provided. These - * implementations are derived from those in the Sun JDK. +/** The `Sorting` object provides convenience wrappers for `java.util.Arrays.sort`. + * Methods that defer to `java.util.Arrays.sort` say that they do or under what + * conditions that they do. * - * Note that stability doesn't matter for value types, so use the `quickSort` - * variants for those. `stableSort` is intended to be used with - * objects when the prior ordering should be preserved, where possible. + * `Sorting` also implements a general-purpose quicksort and stable (merge) sort + * for those cases where `java.util.Arrays.sort` could only be used at the cost + * of a large memory penalty. If performance rather than memory usage is the + * primary concern, one may wish to find alternate strategies to use + * `java.util.Arrays.sort` directly e.g. by boxing primitives to use + * a custom ordering on them. + * + * `Sorting` provides methods where you can provide a comparison function, or + * can request a sort of items that are [[scala.math.Ordered]] or that + * otherwise have an implicit or explicit [[scala.math.Ordering]]. + * + * Note also that high-performance non-default sorts for numeric types + * are not provided. If this is required, it is advisable to investigate + * other libraries that cover this use case. * * @author Ross Judson - * @version 1.0 + * @author Adriaan Moors + * @author Rex Kerr + * @version 1.1 */ object Sorting { - /** Quickly sort an array of Doubles. */ - def quickSort(a: Array[Double]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of items with an implicit Ordering. */ - def quickSort[K: Ordering](a: Array[K]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of Ints. */ - def quickSort(a: Array[Int]) { sort1(a, 0, a.length) } - - /** Quickly sort an array of Floats. */ - def quickSort(a: Array[Float]) { sort1(a, 0, a.length) } - - /** Sort an array of K where K is Ordered, preserving the existing order - * where the values are equal. */ - def stableSort[K: ClassTag: Ordering](a: Array[K]) { - stableSort(a, 0, a.length-1, new Array[K](a.length), Ordering[K].lt _) - } + /** Sort an array of Doubles using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Double]): Unit = java.util.Arrays.sort(a) - /** Sorts an array of `K` given an ordering function `f`. - * `f` should return `true` iff its first parameter is strictly less than its second parameter. - */ - def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean) { - stableSort(a, 0, a.length-1, new Array[K](a.length), f) - } + /** Sort an array of Ints using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Int]): Unit = java.util.Arrays.sort(a) - /** Sorts an arbitrary sequence into an array, given a comparison function - * that should return `true` iff parameter one is strictly less than parameter two. - * - * @param a the sequence to be sorted. - * @param f the comparison function. - * @return the sorted sequence of items. - */ - def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = { - val ret = a.toArray - stableSort(ret, f) - ret - } + /** Sort an array of Floats using `java.util.Arrays.sort`. */ + def quickSort(a: Array[Float]): Unit = java.util.Arrays.sort(a) + + private final val qsortThreshold = 16 - /** Sorts an arbitrary sequence of items that are viewable as ordered. */ - def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = - stableSort(a, Ordering[K].lt _) - - /** Stably sorts a sequence of items given an extraction function that will - * return an ordered key from an item. - * - * @param a the sequence to be sorted. - * @param f the comparison function. - * @return the sorted sequence of items. - */ - def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = - stableSort(a)(implicitly[ClassTag[K]], Ordering[M] on f) - - private def sort1[K: Ordering](x: Array[K], off: Int, len: Int) { - val ord = Ordering[K] - import ord._ - - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t - } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - if (x(a) < x(b)) { - if (x(b) < x(c)) b else if (x(a) < x(c)) c else a - } else { - if (x(b) > x(c)) b else if (x(a) > x(c)) c else a - } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && x(j-1) > x(j)) { - swap(j, j-1) - j -= 1 + /** Sort array `a` with quicksort, using the Ordering on its elements. + * This algorithm sorts in place, so no additional memory is used aside from + * what might be required to box individual elements during comparison. + */ + def quickSort[K: Ordering](a: Array[K]): Unit = { + // Must have iN >= i0 or math will fail. Also, i0 >= 0. + def inner(a: Array[K], i0: Int, iN: Int, ord: Ordering[K]): Unit = { + if (iN - i0 < qsortThreshold) insertionSort(a, i0, iN, ord) + else { + var iK = (i0 + iN) >>> 1 // Unsigned div by 2 + // Find index of median of first, central, and last elements + var pL = + if (ord.compare(a(i0), a(iN - 1)) <= 0) + if (ord.compare(a(i0), a(iK)) < 0) + if (ord.compare(a(iN - 1), a(iK)) < 0) iN - 1 else iK + else i0 + else + if (ord.compare(a(i0), a(iK)) < 0) i0 + else + if (ord.compare(a(iN - 1), a(iK)) <= 0) iN - 1 + else iK + val pivot = a(pL) + // pL is the start of the pivot block; move it into the middle if needed + if (pL != iK) { a(pL) = a(iK); a(iK) = pivot; pL = iK } + // Elements equal to the pivot will be in range pL until pR + var pR = pL + 1 + // Items known to be less than pivot are below iA (range i0 until iA) + var iA = i0 + // Items known to be greater than pivot are at or above iB (range iB until iN) + var iB = iN + // Scan through everything in the buffer before the pivot(s) + while (pL - iA > 0) { + val current = a(iA) + ord.compare(current, pivot) match { + case 0 => + // Swap current out with pivot block + a(iA) = a(pL - 1) + a(pL - 1) = current + pL -= 1 + case x if x < 0 => + // Already in place. Just update indicies. + iA += 1 + case _ if iB > pR => + // Wrong side. There's room on the other side, so swap + a(iA) = a(iB - 1) + a(iB - 1) = current + iB -= 1 + case _ => + // Wrong side and there is no room. Swap by rotating pivot block. + a(iA) = a(pL - 1) + a(pL - 1) = a(pR - 1) + a(pR - 1) = current + pL -= 1 + pR -= 1 + iB -= 1 } - i += 1 } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) + // Get anything remaining in buffer after the pivot(s) + while (iB - pR > 0) { + val current = a(iB - 1) + ord.compare(current, pivot) match { + case 0 => + // Swap current out with pivot block + a(iB - 1) = a(pR) + a(pR) = current + pR += 1 + case x if x > 0 => + // Already in place. Just update indices. + iB -= 1 + case _ => + // Wrong side and we already know there is no room. Swap by rotating pivot block. + a(iB - 1) = a(pR) + a(pR) = a(pL) + a(pL) = current + iA += 1 + pL += 1 + pR += 1 } - m = med3(l, m, n) // Mid-size, med of 3 } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - while (b <= c && x(b) <= v) { - if (x(b) equiv v) { - swap(a, b) - a += 1 - } - b += 1 - } - while (c >= b && x(c) >= v) { - if (x(c) equiv v) { - swap(c, d) - d -= 1 - } - c -= 1 - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } + // Use tail recursion on large half (Sedgewick's method) so we don't blow up the stack if pivots are poorly chosen + if (iA - i0 < iN - iB) { + inner(a, i0, iA, ord) // True recursion + inner(a, iB, iN, ord) // Should be tail recursion + } + else { + inner(a, iB, iN, ord) // True recursion + inner(a, i0, iA, ord) // Should be tail recursion } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) } } - sort2(off, len) + inner(a, 0, a.length, implicitly[Ordering[K]]) } - - private def sort1(x: Array[Int], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + private final val mergeThreshold = 32 + + // Ordering[T] might be slow especially for boxed primitives, so use binary search variant of insertion sort + // Caller must pass iN >= i0 or math will fail. Also, i0 >= 0. + private def insertionSort[@specialized T](a: Array[T], i0: Int, iN: Int, ord: Ordering[T]): Unit = { + val n = iN - i0 + if (n < 2) return + if (ord.compare(a(i0), a(i0+1)) > 0) { + val temp = a(i0) + a(i0) = a(i0+1) + a(i0+1) = temp } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - if (x(a) < x(b)) { - if (x(b) < x(c)) b else if (x(a) < x(c)) c else a - } else { - if (x(b) > x(c)) b else if (x(a) > x(c)) c else a - } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j>off && x(j-1) > x(j)) { - swap(j, j-1) - j -= 1 - } - i += 1 + var m = 2 + while (m < n) { + // Speed up already-sorted case by checking last element first + val next = a(i0 + m) + if (ord.compare(next, a(i0+m-1)) < 0) { + var iA = i0 + var iB = i0 + m - 1 + while (iB - iA > 1) { + val ix = (iA + iB) >>> 1 // Use bit shift to get unsigned div by 2 + if (ord.compare(next, a(ix)) < 0) iB = ix + else iA = ix } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - while (b <= c && x(b) <= v) { - if (x(b) == v) { - swap(a, b) - a += 1 - } - b += 1 - } - while (c >= b && x(c) >= v) { - if (x(c) == v) { - swap(c, d) - d -= 1 - } - c -= 1 - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } + val ix = iA + (if (ord.compare(next, a(iA)) < 0) 0 else 1) + var i = i0 + m + while (i > ix) { + a(i) = a(i-1) + i -= 1 } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) + a(ix) = next } + m += 1 } - sort2(off, len) } - - private def sort1(x: Array[Double], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + // Caller is required to pass iN >= i0, else math will fail. Also, i0 >= 0. + private def mergeSort[@specialized T: ClassTag](a: Array[T], i0: Int, iN: Int, ord: Ordering[T], scratch: Array[T] = null): Unit = { + if (iN - i0 < mergeThreshold) insertionSort(a, i0, iN, ord) + else { + val iK = (i0 + iN) >>> 1 // Bit shift equivalent to unsigned math, no overflow + val sc = if (scratch eq null) new Array[T](iK - i0) else scratch + mergeSort(a, i0, iK, ord, sc) + mergeSort(a, iK, iN, ord, sc) + mergeSorted(a, i0, iK, iN, ord, sc) } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) + } + + // Must have 0 <= i0 < iK < iN + private def mergeSorted[@specialized T](a: Array[T], i0: Int, iK: Int, iN: Int, ord: Ordering[T], scratch: Array[T]): Unit = { + // Check to make sure we're not already in order + if (ord.compare(a(iK-1), a(iK)) > 0) { + var i = i0 + val jN = iK - i0 + var j = 0 + while (i < iK) { + scratch (j) = a(i) i += 1 - a += 1 - b += 1 - } - } - def med3(a: Int, b: Int, c: Int) = { - val ab = x(a) compare x(b) - val bc = x(b) compare x(c) - val ac = x(a) compare x(c) - if (ab < 0) { - if (bc < 0) b else if (ac < 0) c else a - } else { - if (bc > 0) b else if (ac > 0) c else a + j += 1 } - } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && (x(j-1) compare x(j)) > 0) { - swap(j, j-1) - j -= 1 - } - i += 1 - } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) - - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - var bv = x(b) compare v - while (b <= c && bv <= 0) { - if (bv == 0) { - swap(a, b) - a += 1 - } - b += 1 - if (b <= c) bv = x(b) compare v - } - var cv = x(c) compare v - while (c >= b && cv >= 0) { - if (cv == 0) { - swap(c, d) - d -= 1 - } - c -= 1 - if (c >= b) cv = x(c) compare v - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } - } - - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) - - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) + var k = i0 + j = 0 + while (i < iN && j < jN) { + if (ord.compare(a(i), scratch(j)) < 0) { a(k) = a(i); i += 1 } + else { a(k) = scratch(j); j += 1 } + k += 1 } + while (j < jN) { a(k) = scratch(j); j += 1; k += 1 } + // Don't need to finish a(i) because it's already in place, k = i } - sort2(off, len) } - - private def sort1(x: Array[Float], off: Int, len: Int) { - def swap(a: Int, b: Int) { - val t = x(a) - x(a) = x(b) - x(b) = t + + // Why would you even do this? + private def booleanSort(a: Array[Boolean]): Unit = { + var i = 0 + var n = 0 + while (i < a.length) { + if (!a(i)) n += 1 + i += 1 } - def vecswap(_a: Int, _b: Int, n: Int) { - var a = _a - var b = _b - var i = 0 - while (i < n) { - swap(a, b) - i += 1 - a += 1 - b += 1 - } + i = 0 + while (i < n) { + a(i) = false + i += 1 } - def med3(a: Int, b: Int, c: Int) = { - val ab = x(a) compare x(b) - val bc = x(b) compare x(c) - val ac = x(a) compare x(c) - if (ab < 0) { - if (bc < 0) b else if (ac < 0) c else a - } else { - if (bc > 0) b else if (ac > 0) c else a - } + while (i < a.length) { + a(i) = true + i += 1 } - def sort2(off: Int, len: Int) { - // Insertion sort on smallest arrays - if (len < 7) { - var i = off - while (i < len + off) { - var j = i - while (j > off && (x(j-1) compare x(j)) > 0) { - swap(j, j-1) - j -= 1 - } - i += 1 - } - } else { - // Choose a partition element, v - var m = off + (len >> 1) // Small arrays, middle element - if (len > 7) { - var l = off - var n = off + len - 1 - if (len > 40) { // Big arrays, pseudomedian of 9 - val s = len / 8 - l = med3(l, l+s, l+2*s) - m = med3(m-s, m, m+s) - n = med3(n-2*s, n-s, n) - } - m = med3(l, m, n) // Mid-size, med of 3 - } - val v = x(m) + } - // Establish Invariant: v* (<v)* (>v)* v* - var a = off - var b = a - var c = off + len - 1 - var d = c - var done = false - while (!done) { - var bv = x(b) compare v - while (b <= c && bv <= 0) { - if (bv == 0) { - swap(a, b) - a += 1 - } - b += 1 - if (b <= c) bv = x(b) compare v - } - var cv = x(c) compare v - while (c >= b && cv >= 0) { - if (cv == 0) { - swap(c, d) - d -= 1 - } - c -= 1 - if (c >= b) cv = x(c) compare v - } - if (b > c) { - done = true - } else { - swap(b, c) - c -= 1 - b += 1 - } - } + // TODO: add upper bound: T <: AnyRef, propagate to callers below (not binary compatible) + // Maybe also rename all these methods to `sort`. + @inline private def sort[T](a: Array[T], ord: Ordering[T]): Unit = a match { + case _: Array[AnyRef] => + // Note that runtime matches are covariant, so could actually be any Array[T] s.t. T is not primitive (even boxed value classes) + if (a.length > 1 && (ord eq null)) throw new NullPointerException("Ordering") + java.util.Arrays.sort(a, ord) + case a: Array[Int] => if (ord eq Ordering.Int) java.util.Arrays.sort(a) else mergeSort[Int](a, 0, a.length, ord) + case a: Array[Double] => mergeSort[Double](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful! + case a: Array[Long] => if (ord eq Ordering.Long) java.util.Arrays.sort(a) else mergeSort[Long](a, 0, a.length, ord) + case a: Array[Float] => mergeSort[Float](a, 0, a.length, ord) // Because not all NaNs are identical, stability is meaningful! + case a: Array[Char] => if (ord eq Ordering.Char) java.util.Arrays.sort(a) else mergeSort[Char](a, 0, a.length, ord) + case a: Array[Byte] => if (ord eq Ordering.Byte) java.util.Arrays.sort(a) else mergeSort[Byte](a, 0, a.length, ord) + case a: Array[Short] => if (ord eq Ordering.Short) java.util.Arrays.sort(a) else mergeSort[Short](a, 0, a.length, ord) + case a: Array[Boolean] => if (ord eq Ordering.Boolean) booleanSort(a) else mergeSort[Boolean](a, 0, a.length, ord) + // Array[Unit] is matched as an Array[AnyRef] due to covariance in runtime matching. Not worth catching it as a special case. + case null => throw new NullPointerException + } - // Swap partition elements back to middle - val n = off + len - var s = math.min(a-off, b-a) - vecswap(off, b-s, s) - s = math.min(d-c, n-d-1) - vecswap(b, n-s, s) + // TODO: remove unnecessary ClassTag (not binary compatible) + /** Sort array `a` using the Ordering on its elements, preserving the original ordering where possible. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag: Ordering](a: Array[K]): Unit = sort(a, Ordering[K]) - // Recursively sort non-partition-elements - s = b - a - if (s > 1) - sort2(off, s) - s = d - c - if (s > 1) - sort2(n-s, s) - } - } - sort2(off, len) + // TODO: Remove unnecessary ClassTag (not binary compatible) + // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering) + /** Sort array `a` using function `f` that computes the less-than relation for each element. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag](a: Array[K], f: (K, K) => Boolean): Unit = sort(a, Ordering fromLessThan f) + + /** A sorted Array, using the Ordering for the elements in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag: Ordering](a: Seq[K]): Array[K] = { + val ret = a.toArray + sort(ret, Ordering[K]) + ret } - private def stableSort[K : ClassTag](a: Array[K], lo: Int, hi: Int, scratch: Array[K], f: (K,K) => Boolean) { - if (lo < hi) { - val mid = (lo+hi) / 2 - stableSort(a, lo, mid, scratch, f) - stableSort(a, mid+1, hi, scratch, f) - var k, t_lo = lo - var t_hi = mid + 1 - while (k <= hi) { - if ((t_lo <= mid) && ((t_hi > hi) || (!f(a(t_hi), a(t_lo))))) { - scratch(k) = a(t_lo) - t_lo += 1 - } else { - scratch(k) = a(t_hi) - t_hi += 1 - } - k += 1 - } - k = lo - while (k <= hi) { - a(k) = scratch(k) - k += 1 - } - } + // TODO: make this fast for primitive K (could be specialized if it didn't go through Ordering) + /** A sorted Array, given a function `f` that computes the less-than relation for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag](a: Seq[K], f: (K, K) => Boolean): Array[K] = { + val ret = a.toArray + sort(ret, Ordering fromLessThan f) + ret + } + + /** A sorted Array, given an extraction function `f` that returns an ordered key for each item in the sequence `a`. Uses `java.util.Arrays.sort` unless `K` is a primitive type. */ + def stableSort[K: ClassTag, M: Ordering](a: Seq[K], f: K => M): Array[K] = { + val ret = a.toArray + sort(ret, Ordering[M] on f) + ret } } diff --git a/src/repl/scala/tools/nsc/interpreter/IMain.scala b/src/repl/scala/tools/nsc/interpreter/IMain.scala index c281126d5f..e355d9f864 100644 --- a/src/repl/scala/tools/nsc/interpreter/IMain.scala +++ b/src/repl/scala/tools/nsc/interpreter/IMain.scala @@ -69,6 +69,8 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set // Used in a test case. def showDirectory() = replOutput.show(out) + lazy val isClassBased: Boolean = settings.Yreplclassbased.value + private[nsc] var printResults = true // whether to print result lines private[nsc] var totalSilence = false // whether to print anything private var _initializeComplete = false // compiler is initialized @@ -310,8 +312,14 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set } def originalPath(name: String): String = originalPath(TermName(name)) - def originalPath(name: Name): String = typerOp path name - def originalPath(sym: Symbol): String = typerOp path sym + def originalPath(name: Name): String = translateOriginalPath(typerOp path name) + def originalPath(sym: Symbol): String = translateOriginalPath(typerOp path sym) + /** For class based repl mode we use an .INSTANCE accessor. */ + val readInstanceName = if(isClassBased) ".INSTANCE" else "" + def translateOriginalPath(p: String): String = { + val readName = java.util.regex.Matcher.quoteReplacement(sessionNames.read) + p.replaceFirst(readName, readName + readInstanceName) + } def flatPath(sym: Symbol): String = flatOp shift sym.javaClassName def translatePath(path: String) = { @@ -758,11 +766,13 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set // object and we can do that much less wrapping. def packageDecl = "package " + packageName + def pathToInstance(name: String) = packageName + "." + name + readInstanceName def pathTo(name: String) = packageName + "." + name def packaged(code: String) = packageDecl + "\n\n" + code - def readPath = pathTo(readName) - def evalPath = pathTo(evalName) + def readPathInstance = pathToInstance(readName) + def readPath = pathTo(readName) + def evalPath = pathTo(evalName) def call(name: String, args: Any*): AnyRef = { val m = evalMethod(name) @@ -802,7 +812,8 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set /** The innermost object inside the wrapper, found by * following accessPath into the outer one. */ - def resolvePathToSymbol(accessPath: String): Symbol = { + def resolvePathToSymbol(fullAccessPath: String): Symbol = { + val accessPath = fullAccessPath.stripPrefix(readPath) val readRoot = readRootPath(readPath) // the outermost wrapper (accessPath split '.').foldLeft(readRoot: Symbol) { case (sym, "") => sym @@ -849,7 +860,6 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set def defines = defHandlers flatMap (_.definedSymbols) def imports = importedSymbols def value = Some(handlers.last) filter (h => h.definesValue) map (h => definedSymbols(h.definesTerm.get)) getOrElse NoSymbol - val lineRep = new ReadEvalPrint() private var _originalLine: String = null @@ -858,6 +868,11 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set /** handlers for each tree in this request */ val handlers: List[MemberHandler] = trees map (memberHandlers chooseHandler _) + val definesClass = handlers.exists { + case _: ClassHandler => true + case _ => false + } + def defHandlers = handlers collect { case x: MemberDefHandler => x } /** list of names used by this expression */ @@ -875,13 +890,13 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set * append to objectName to access anything bound by request. */ lazy val ComputedImports(importsPreamble, importsTrailer, accessPath) = - exitingTyper(importsCode(referencedNames.toSet, ObjectSourceCode)) + exitingTyper(importsCode(referencedNames.toSet, ObjectSourceCode, definesClass)) /** the line of code to compute */ def toCompute = line /** The path of the value that contains the user code. */ - def fullAccessPath = s"${lineRep.readPath}$accessPath" + def fullAccessPath = s"${lineRep.readPathInstance}$accessPath" /** The path of the given member of the wrapping instance. */ def fullPath(vname: String) = s"$fullAccessPath.`$vname`" @@ -911,7 +926,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set def postwrap: String } - private class ObjectBasedWrapper extends Wrapper { + class ObjectBasedWrapper extends Wrapper { def preambleHeader = "object %s {" def postamble = importsTrailer + "\n}" @@ -919,13 +934,16 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set def postwrap = "}\n" } - private class ClassBasedWrapper extends Wrapper { - def preambleHeader = "class %s extends Serializable {" + class ClassBasedWrapper extends Wrapper { + def preambleHeader = "class %s extends Serializable { " /** Adds an object that instantiates the outer wrapping class. */ - def postamble = s"""$importsTrailer + def postamble = s""" + |$importsTrailer + |} + |object ${lineRep.readName} { + | val INSTANCE = new ${lineRep.readName}(); |} - |object ${lineRep.readName} extends ${lineRep.readName} |""".stripMargin import nme.{ INTERPRETER_IMPORT_WRAPPER => iw } @@ -935,7 +953,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set } private lazy val ObjectSourceCode: Wrapper = - if (settings.Yreplclassbased) new ClassBasedWrapper else new ObjectBasedWrapper + if (isClassBased) new ClassBasedWrapper else new ObjectBasedWrapper private object ResultObjectSourceCode extends IMain.CodeAssembler[MemberHandler] { /** We only want to generate this code when the result @@ -994,7 +1012,7 @@ class IMain(@BeanProperty val factory: ScriptEngineFactory, initialSettings: Set } } - lazy val resultSymbol = lineRep.resolvePathToSymbol(accessPath) + lazy val resultSymbol = lineRep.resolvePathToSymbol(fullAccessPath) def applyToResultMember[T](name: Name, f: Symbol => T) = exitingTyper(f(resultSymbol.info.nonPrivateDecl(name))) /* typeOf lookup with encoding */ diff --git a/src/repl/scala/tools/nsc/interpreter/Imports.scala b/src/repl/scala/tools/nsc/interpreter/Imports.scala index 5244858a62..3ec77e46f1 100644 --- a/src/repl/scala/tools/nsc/interpreter/Imports.scala +++ b/src/repl/scala/tools/nsc/interpreter/Imports.scala @@ -92,7 +92,7 @@ trait Imports { * last one imported is actually usable. */ case class ComputedImports(prepend: String, append: String, access: String) - protected def importsCode(wanted: Set[Name], wrapper: Request#Wrapper): ComputedImports = { + protected def importsCode(wanted: Set[Name], wrapper: Request#Wrapper, definesClass: Boolean): ComputedImports = { /** Narrow down the list of requests from which imports * should be taken. Removes requests which cannot contribute * useful imports for the specified set of wanted names. @@ -107,6 +107,8 @@ trait Imports { // Single symbol imports might be implicits! See bug #1752. Rather than // try to finesse this, we will mimic all imports for now. def keepHandler(handler: MemberHandler) = handler match { + /* While defining classes in class based mode - implicits are not needed. */ + case h: ImportHandler if isClassBased && definesClass => h.importedNames.exists(x => wanted.contains(x)) case _: ImportHandler => true case x => x.definesImplicit || (x.definedNames exists wanted) } @@ -146,7 +148,10 @@ trait Imports { // loop through previous requests, adding imports for each one wrapBeforeAndAfter { + // Reusing a single temporary value when import from a line with multiple definitions. + val tempValLines = mutable.Set[Int]() for (ReqAndHandler(req, handler) <- reqsToUse) { + val objName = req.lineRep.readPathInstance handler match { // If the user entered an import, then just use it; add an import wrapping // level if the import might conflict with some other import @@ -157,6 +162,23 @@ trait Imports { code append (x.member + "\n") currentImps ++= x.importedNames + case x if isClassBased => + for (imv <- x.definedNames) { + if (!currentImps.contains(imv)) { + x match { + case _: ClassHandler => + code.append("import " + objName + req.accessPath + ".`" + imv + "`\n") + case _ => + val valName = req.lineRep.packageName + req.lineRep.readName + if (!tempValLines.contains(req.lineRep.lineId)) { + code.append(s"val $valName = $objName\n") + tempValLines += req.lineRep.lineId + } + code.append(s"import $valName${req.accessPath}.`$imv`;\n") + } + currentImps += imv + } + } // For other requests, import each defined name. // import them explicitly instead of with _, so that // ambiguity errors will not be generated. Also, quote diff --git a/test/files/run/repl-serialization.check b/test/files/run/repl-serialization.check new file mode 100644 index 0000000000..eb62729f5c --- /dev/null +++ b/test/files/run/repl-serialization.check @@ -0,0 +1,25 @@ +== evaluating lines +extract: AnyRef => Unit = <function1> + evaluating x +x: Int = 0 +getX: ()Int +defined class U +y: Int = <lazy> + evaluating z + evaluating zz +defined class D +z: Int = 0 +zz: Int = 0 +defined object O +defined class A +defined type alias AA +constructing U +u: U = U +== evaluating lambda + evaluating y + evaluating O + constructing A +== reconstituting into a fresh classloader + evaluating O +== evaluating reconstituted lambda + constructing A diff --git a/test/files/run/repl-serialization.scala b/test/files/run/repl-serialization.scala new file mode 100644 index 0000000000..55b7519631 --- /dev/null +++ b/test/files/run/repl-serialization.scala @@ -0,0 +1,68 @@ +import java.io._ + +import scala.reflect.io.AbstractFile +import scala.tools.nsc.Settings +import scala.tools.nsc.interpreter.IMain +import scala.tools.nsc.util._ +import scala.reflect.internal.util.AbstractFileClassLoader + +object Test { + def main(args: Array[String]) { + run() + } + + def run(): Unit = { + val settings = new Settings() + settings.Yreplclassbased.value = true + settings.usejavacp.value = true + + var imain: IMain = null + object extract extends ((AnyRef) => Unit) with Serializable { + var value: AnyRef = null + + def apply(a: AnyRef) = value = a + } + + val code = + """val x = {println(" evaluating x"); 0 } + |def getX() = x + |class U extends Serializable { println("constructing U"); val x = 0 ; override def toString = "U" } + |lazy val y = {println(" evaluating y"); 0 } + |class D; val z = {println(" evaluating z"); 0}; val zz = {println(" evaluating zz"); 0} + |object O extends Serializable { val apply = {println(" evaluating O"); 0} } + |class A(i: Int) { println(" constructing A") } + |type AA = A + |val u = new U() + |extract(() => new AA(x + getX() + y + z + zz + O.apply + u.x)) + """.stripMargin + + imain = new IMain(settings) + println("== evaluating lines") + imain.directBind("extract", "(AnyRef => Unit)", extract) + code.lines.foreach(imain.interpret) + + val virtualFile: AbstractFile = extract.value.getClass.getClassLoader.asInstanceOf[AbstractFileClassLoader].root + val newLoader = new AbstractFileClassLoader(virtualFile, getClass.getClassLoader) + + def deserializeInNewLoader(string: Array[Byte]): AnyRef = { + val bis = new ByteArrayInputStream(string) + val in = new ObjectInputStream(bis) { + override def resolveClass(desc: ObjectStreamClass) = Class.forName(desc.getName, false, newLoader) + } + in.readObject() + } + def serialize(o: AnyRef): Array[Byte] = { + val bos = new ByteArrayOutputStream() + val out = new ObjectOutputStream(bos) + out.writeObject(o) + out.close() + bos.toByteArray + } + println("== evaluating lambda") + extract.value.asInstanceOf[() => Any].apply() + println("== reconstituting into a fresh classloader") + val reconstituted = deserializeInNewLoader(serialize(extract.value)).asInstanceOf[() => Any] + println("== evaluating reconstituted lambda") + reconstituted.apply() // should not print("evaluating x") a second time + } +} diff --git a/test/files/run/t7747-repl.check b/test/files/run/t7747-repl.check index 105b238d01..5f436ba6b1 100644 --- a/test/files/run/t7747-repl.check +++ b/test/files/run/t7747-repl.check @@ -112,7 +112,7 @@ scala> 55 ; ((2 + 2)) ; (1, 2, 3) res15: (Int, Int, Int) = (1,2,3) scala> 55 ; (x: Int) => x + 1 ; () => ((5)) -<console>:8: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses +<console>:9: warning: a pure expression does nothing in statement position; you may be omitting necessary parentheses 55 ; (x: Int) => x + 1 ;; ^ res16: () => Int = <function0> @@ -258,12 +258,12 @@ class $read extends Serializable { super.<init>; () }; - import $line44.$read.$iw.$iw.BippyBups; - import $line44.$read.$iw.$iw.BippyBups; - import $line45.$read.$iw.$iw.PuppyPups; - import $line45.$read.$iw.$iw.PuppyPups; - import $line46.$read.$iw.$iw.Bingo; - import $line46.$read.$iw.$iw.Bingo; + import $line44.$read.INSTANCE.$iw.$iw.BippyBups; + import $line44.$read.INSTANCE.$iw.$iw.BippyBups; + import $line45.$read.INSTANCE.$iw.$iw.PuppyPups; + import $line45.$read.INSTANCE.$iw.$iw.PuppyPups; + import $line46.$read.INSTANCE.$iw.$iw.Bingo; + import $line46.$read.INSTANCE.$iw.$iw.Bingo; class $iw extends Serializable { def <init>() = { super.<init>; @@ -275,12 +275,35 @@ class $read extends Serializable { }; val $iw = new $iw.<init> } -object $read extends $read { +object $read extends scala.AnyRef { def <init>() = { super.<init>; () - } + }; + val INSTANCE = new $read.<init> } res3: List[Product with Serializable] = List(BippyBups(), PuppyPups(), Bingo()) +scala> case class Sum(exp: String, exp2: String) +defined class Sum + +scala> val a = Sum("A", "B") +a: Sum = Sum(A,B) + +scala> def b(a: Sum): String = a match { case Sum(_, _) => "Found Sum" } +b: (a: Sum)String + +scala> b(a) +res4: String = Found Sum + +scala> :power +** Power User mode enabled - BEEP WHIR GYVE ** +** :phase has been set to 'typer'. ** +** scala.tools.nsc._ has been imported ** +** global._, definitions._ also imported ** +** Try :help, :vals, power.<tab> ** + +scala> intp.lastRequest +res5: $r.intp.Request = Request(line=def $ires3 = intp.global, 1 trees) + scala> :quit diff --git a/test/files/run/t7747-repl.scala b/test/files/run/t7747-repl.scala index 0e64210460..141c2d9844 100644 --- a/test/files/run/t7747-repl.scala +++ b/test/files/run/t7747-repl.scala @@ -65,5 +65,11 @@ object Test extends ReplTest { |case class PuppyPups() |case class Bingo() |List(BippyBups(), PuppyPups(), Bingo()) // show + |case class Sum(exp: String, exp2: String) + |val a = Sum("A", "B") + |def b(a: Sum): String = a match { case Sum(_, _) => "Found Sum" } + |b(a) + |:power + |intp.lastRequest |""".stripMargin } diff --git a/test/junit/scala/util/SortingTest.scala b/test/junit/scala/util/SortingTest.scala new file mode 100644 index 0000000000..15a00c8903 --- /dev/null +++ b/test/junit/scala/util/SortingTest.scala @@ -0,0 +1,69 @@ +package scala.util + +import org.junit.Test +import org.junit.Assert._ +import scala.math.{ Ordered, Ordering } +import scala.reflect.ClassTag + +class SortingTest { + case class N(i: Int, j: Int) extends Ordered[N] { def compare(n: N) = if (i < n.i) -1 else if (i > n.i) 1 else 0 } + + def mkA(n: Int, max: Int) = Array.tabulate(n)(i => N(util.Random.nextInt(max), i)) + + def isStable(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true } + + def isAntistable(a: Array[N]): Boolean = + { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i || (a(i).i == a(i-1).i && a(i).j < a(i-1).j)) return false; i += 1 }; true } + + def isSorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i < a(i-1).i) return false; i += 1 }; true } + + def isAntisorted(a: Array[N]): Boolean = { var i = 1; while (i < a.length) { if (a(i).i > a(i-1).i) return false; i += 1 }; true } + + val sizes = Seq.range(0, 65) ++ Seq(256, 1024, 9121, 65539) + val variety = Seq(1, 2, 10, 100, 1000, Int.MaxValue) + val workLimit = 1e6 + val rng = new util.Random(198571) + + val backwardsN = Ordering by ((n: N) => -n.i) + + def runOneTest(size: Int, variety: Int): Unit = { + val xs = Array.tabulate(size)(i => N(rng.nextInt(variety), i)) + val ys = Array.range(0, xs.length) + val zs = { val temp = xs.clone; java.util.Arrays.sort(temp, new java.util.Comparator[N] { def compare(a: N, b: N) = a.compare(b) }); temp } + val qxs = { val temp = xs.clone; Sorting.quickSort(temp); temp } + val pxs = { val temp = xs.clone; Sorting.quickSort(temp)(backwardsN); temp } + val sxs = { val temp = xs.clone; Sorting.stableSort(temp); temp } + val rxs = { val temp = xs.clone; Sorting.stableSort(temp)(implicitly[ClassTag[N]], backwardsN); temp } + val sys = Sorting.stableSort(ys.clone: Seq[Int], (i: Int) => xs(i)) + + assertTrue("Quicksort should be in order", isSorted(qxs)) + assertTrue("Quicksort should be in reverse order", isAntisorted(pxs)) + assertTrue("Stable sort should be sorted and stable", isStable(sxs)) + assertTrue("Stable sort should be reverse sorted but stable", isAntistable(rxs)) + assertTrue("Stable sorting by proxy should produce sorted stable list", isStable(sys.map(i => xs(i)))) + assertTrue("Quicksort should produce canonical ordering", (qxs zip zs).forall{ case (a,b) => a.i == b.i }) + assertTrue("Reverse quicksort should produce canonical ordering", (pxs.reverse zip zs).forall{ case (a,b) => a.i == b.i }) + assertTrue("Stable sort should produce exact ordering", (sxs zip zs).forall{ case (a,b) => a == b }) + assertTrue("Reverse stable sort should produce canonical ordering", (rxs.reverse zip zs).forall{ case (a,b) => a.i == b.i }) + assertTrue("Proxy sort and direct sort should produce exactly the same thing", (sxs zip sys.map(i => xs(i))).forall{ case (a,b) => a == b }) + } + + @Test def testSortConsistency: Unit = { + for { + size <- sizes + v <- variety + i <- 0 until math.min(100, math.max(math.min(math.floor(math.pow(v, size)/2), math.ceil(workLimit / (math.log(math.max(2,size))/math.log(2) * size))), 1).toInt) + } runOneTest(size, v) + + for (size <- sizes) { + val b = Array.fill(size)(rng.nextBoolean) + val bfwd = Sorting.stableSort(b.clone: Seq[Boolean]) + val bbkw = Sorting.stableSort(b.clone: Seq[Boolean], (x: Boolean, y: Boolean) => x && !y) + assertTrue("All falses should be first", bfwd.dropWhile(_ == false).forall(_ == true)) + assertTrue("All falses should be last when sorted backwards", bbkw.dropWhile(_ == true).forall(_ == false)) + assertTrue("Sorting booleans should preserve the number of trues", b.count(_ == true) == bfwd.count(_ == true)) + assertTrue("Backwards sorting booleans should preserve the number of trues", b.count(_ == true) == bbkw.count(_ == true)) + assertTrue("Sorting should not change the sizes of arrays", b.length == bfwd.length && b.length == bbkw.length) + } + } +} |