diff options
Diffstat (limited to 'test/junit')
10 files changed, 414 insertions, 9 deletions
diff --git a/test/junit/scala/collection/IteratorTest.scala b/test/junit/scala/collection/IteratorTest.scala index b3cd6707c1..b0639ef365 100644 --- a/test/junit/scala/collection/IteratorTest.scala +++ b/test/junit/scala/collection/IteratorTest.scala @@ -176,4 +176,14 @@ class IteratorTest { assertEquals(-1, List(5 -> 0, 9 -> 2, 0 -> 3).iterator.indexOf(9, 2)) assertEquals(1, List(5 -> 0, 9 -> 2, 0 -> 3).iterator.indexOf(9 -> 2)) } + // SI-9332 + @Test def spanExhaustsLeadingIterator(): Unit = { + def it = Iterator.iterate(0)(_ + 1).take(6) + val (x, y) = it.span(_ != 1) + val z = x.toList + assertEquals(1, z.size) + assertFalse(x.hasNext) + assertEquals(1, y.next) + assertFalse(x.hasNext) // was true, after advancing underlying iterator + } } diff --git a/test/junit/scala/collection/immutable/RangeConsistencyTest.scala b/test/junit/scala/collection/immutable/RangeConsistencyTest.scala index 3980c31577..135796979d 100644 --- a/test/junit/scala/collection/immutable/RangeConsistencyTest.scala +++ b/test/junit/scala/collection/immutable/RangeConsistencyTest.scala @@ -137,4 +137,15 @@ class RangeConsistencyTest { assert( (-3 to Int.MaxValue).dropWhile(_ <= 0).length == Int.MaxValue ) assert( (-3 to Int.MaxValue).span(_ <= 0) match { case (a,b) => a.length == 4 && b.length == Int.MaxValue } ) } + + @Test + def testSI9348() { + // Test exclusive range with (end-start) != 0 (mod step) + assert( (0.0f until 0.4f by 0.25f) sameElements List(0.0f, 0.25f) ) + assert( (1.0 until 2.2 by 0.5) sameElements List(1.0, 1.5, 2.0) ) + + def bd(d: Double) = BigDecimal(d) + val bdRange = bd(-10.0) until bd(0.0) by bd(4.5) + assert( bdRange sameElements List(bd(-10.0), bd(-5.5), bd(-1.0)) ) + } } diff --git a/test/junit/scala/collection/immutable/StringLikeTest.scala b/test/junit/scala/collection/immutable/StringLikeTest.scala index 3722bdfe4d..50be638b89 100644 --- a/test/junit/scala/collection/immutable/StringLikeTest.scala +++ b/test/junit/scala/collection/immutable/StringLikeTest.scala @@ -28,10 +28,16 @@ class StringLikeTest { @Test def testSplitEdgeCases: Unit = { + val high = 0xD852.toChar + val low = 0xDF62.toChar + val surrogatepair = List(high, low).mkString + val twopairs = surrogatepair + "_" + surrogatepair + AssertUtil.assertSameElements("abcd".split('d'), Array("abc")) // not Array("abc", "") AssertUtil.assertSameElements("abccc".split('c'), Array("ab")) // not Array("ab", "", "", "") AssertUtil.assertSameElements("xxx".split('x'), Array[String]()) // not Array("", "", "", "") AssertUtil.assertSameElements("".split('x'), Array("")) // not Array() AssertUtil.assertSameElements("--ch--omp--".split("-"), Array("", "", "ch", "", "omp")) // All the cases! + AssertUtil.assertSameElements(twopairs.split(high), Array(twopairs)) //don't split on characters that are half a surrogate pair } } diff --git a/test/junit/scala/math/BigDecimalTest.scala b/test/junit/scala/math/BigDecimalTest.scala index c7a63da890..a9e2481f37 100644 --- a/test/junit/scala/math/BigDecimalTest.scala +++ b/test/junit/scala/math/BigDecimalTest.scala @@ -228,4 +228,36 @@ class BigDecimalTest { def test_SI8970() { assert((0.1).## == BigDecimal(0.1).##) } + + // Motivated by the problem of MathContext lost + @Test + def testMathContext() { + def testPrecision() { + val p = 1000 + val n = BigDecimal("1.1", MC.UNLIMITED).pow(p) + + // BigDecimal(x: Float, mc: MC), which may not do what you want, is deprecated + assert(BigDecimal(1.1f, MC.UNLIMITED).pow(p) == BigDecimal(java.lang.Double.toString(1.1f.toDouble), MC.UNLIMITED).pow(p)) + assert(BigDecimal(1.1d, MC.UNLIMITED).pow(p) == n) + assert(BigDecimal(new BD("1.1"), MC.UNLIMITED).pow(p) == n) + + assert(BigDecimal.decimal(1.1f, MC.UNLIMITED).pow(p) == n) + assert(BigDecimal.decimal(1.1d, MC.UNLIMITED).pow(p) == n) + assert(BigDecimal.decimal(new BD("1.1"), MC.UNLIMITED).pow(p) == n) + + assert((BigDecimal(11, MC.UNLIMITED) / 10).pow(p) == n) + assert((BigDecimal.decimal(11, MC.UNLIMITED) / 10).pow(p) == n) + } + + def testRounded() { + // the default rounding mode is HALF_UP + assert((BigDecimal(1.23f, new MC(3)) + BigDecimal("0.005")).rounded == BigDecimal("1.24")) // deprecated api + assert((BigDecimal(1.23d, new MC(3)) + BigDecimal("0.005")).rounded == BigDecimal("1.24")) + assert((BigDecimal.decimal(1.23f, new MC(3)) + BigDecimal("0.005")).rounded == BigDecimal("1.24")) + assert((BigDecimal.decimal(1.23d, new MC(3)) + BigDecimal("0.005")).rounded == BigDecimal("1.24")) + } + + testPrecision() + testRounded() + } } diff --git a/test/junit/scala/math/NumericTest.scala b/test/junit/scala/math/NumericTest.scala index 9bf7d4f1e4..682dcbfd75 100644 --- a/test/junit/scala/math/NumericTest.scala +++ b/test/junit/scala/math/NumericTest.scala @@ -5,6 +5,9 @@ import org.junit.Test import org.junit.runner.RunWith import org.junit.runners.JUnit4 +import scala.math.Numeric.FloatAsIfIntegral + + @RunWith(classOf[JUnit4]) class NumericTest { @@ -14,5 +17,28 @@ class NumericTest { assertTrue(-0.0.abs equals 0.0) assertTrue(-0.0f.abs equals 0.0f) } -} + + /* Test for SI-9348 */ + @Test + def testFloatAsIfIntegral { + val num = scala.math.Numeric.FloatAsIfIntegral + assertTrue(num.quot(1.0f, 0.5f) equals 2.0f) + assertTrue(num.quot(1.0f, 0.3f) equals 3.0f) + } + + /* Test for SI-9348 */ + @Test + def testDoubleAsIfIntegral { + val num = scala.math.Numeric.DoubleAsIfIntegral + assertTrue(num.quot(1.0, 0.25) equals 4.0) + assertTrue(num.quot(0.5, 0.15) equals 3.0) + } + + /* Test for SI-9348 */ + @Test + def testBigDecimalAsIfIntegral { + val num = scala.math.Numeric.BigDecimalAsIfIntegral + assertTrue(num.quot(BigDecimal(2.5), BigDecimal(0.5)) equals BigDecimal(5.0)) + assertTrue(num.quot(BigDecimal(5.0), BigDecimal(2.0)) equals BigDecimal(2.0)) + }} diff --git a/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala new file mode 100644 index 0000000000..3a85f03da2 --- /dev/null +++ b/test/junit/scala/tools/nsc/backend/jvm/analysis/NullnessAnalyzerTest.scala @@ -0,0 +1,231 @@ +package scala.tools.nsc +package backend.jvm +package analysis + +import org.junit.runner.RunWith +import org.junit.runners.JUnit4 +import org.junit.Test +import scala.tools.asm.Opcodes._ +import org.junit.Assert._ + +import CodeGenTools._ +import scala.tools.asm.tree.{AbstractInsnNode, MethodNode} +import scala.tools.nsc.backend.jvm.BTypes._ +import scala.tools.partest.ASMConverters +import ASMConverters._ +import scala.tools.testing.ClearAfterClass +import scala.tools.nsc.backend.jvm.opt.BytecodeUtils._ +import AsmUtils._ + +import scala.collection.convert.decorateAsScala._ + +object NullnessAnalyzerTest extends ClearAfterClass.Clearable { + var noOptCompiler = newCompiler(extraArgs = "-Ybackend:GenBCode -Yopt:l:none") + + def clear(): Unit = { + noOptCompiler = null + } +} + +@RunWith(classOf[JUnit4]) +class NullnessAnalyzerTest extends ClearAfterClass { + ClearAfterClass.stateToClear = NullnessAnalyzerTest + val noOptCompiler = NullnessAnalyzerTest.noOptCompiler + + def newNullnessAnalyzer(methodNode: MethodNode, classInternalName: InternalName = "C"): NullnessAnalyzer = { + val nullnessAnalyzer = new NullnessAnalyzer + nullnessAnalyzer.analyze(classInternalName, methodNode) + nullnessAnalyzer + } + + /** + * Instructions that match `query` when textified. + * If `query` starts with a `+`, the next instruction is returned. + */ + def findInstr(method: MethodNode, query: String): List[AbstractInsnNode] = { + val useNext = query(0) == '+' + val instrPart = if (useNext) query.drop(1) else query + val insns = method.instructions.iterator.asScala.find(i => textify(i) contains instrPart).toList + if (useNext) insns.map(_.getNext) else insns + } + + def testNullness(analyzer: NullnessAnalyzer, method: MethodNode, query: String, index: Int, nullness: Nullness): Unit = { + for (i <- findInstr(method, query)) { + val r = analyzer.frameAt(i, method).getValue(index).nullness + assertTrue(s"Expected: $nullness, found: $r. At instr ${textify(i)}", nullness == r) + } + } + + // debug / helper for writing tests + def showAllNullnessFrames(analyzer: NullnessAnalyzer, method: MethodNode): String = { + val instrLength = method.instructions.iterator.asScala.map(textify(_).length).max + val lines = for (i <- method.instructions.iterator.asScala) yield { + val f = analyzer.frameAt(i, method) + val frameString = { + if (f == null) "null" + else (0 until (f.getLocals + f.getStackSize)).iterator + .map(f.getValue(_).toString) + .map(s => "%8s".format(s)) + .zipWithIndex.map({case (s, i) => s"$i: $s"}) + .mkString(", ") + } + ("%"+ instrLength +"s: %s").format(textify(i), frameString) + } + lines.mkString("\n") + } + + @Test + def showNullnessFramesTest(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = this.toString") + + // NOTE: the frame for an instruction represents the state *before* executing that instr. + // So in the frame for `ALOAD 0`, the stack is still empty. + + val res = + """ L0: 0: NotNull + | LINENUMBER 1 L0: 0: NotNull + | ALOAD 0: 0: NotNull + |INVOKEVIRTUAL java/lang/Object.toString ()Ljava/lang/String;: 0: NotNull, 1: NotNull + | ARETURN: 0: NotNull, 1: Unknown1 + | L0: null""".stripMargin + assertEquals(showAllNullnessFrames(newNullnessAnalyzer(m), m), res) + } + + @Test + def thisNonNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = this.toString") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "ALOAD 0", 0, NotNull) + } + + @Test + def instanceMethodCall(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f(a: String) = a.trim") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "INVOKEVIRTUAL java/lang/String.trim", 1, Unknown) + testNullness(a, m, "ARETURN", 1, NotNull) + } + + @Test + def constructorCall(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = { val a = new Object; a.toString }") + val a = newNullnessAnalyzer(m) + + // for reference, the output of showAllNullnessFrames(a, m) - note that the frame represents the state *before* executing the instr. + // NEW java/lang/Object: 0: NotNull, 1: Unknown + // DUP: 0: NotNull, 1: Unknown, 2: Unknown + // INVOKESPECIAL java/lang/Object.<init>: 0: NotNull, 1: Unknown, 2: Unknown, 3: Unknown + // ASTORE 1: 0: NotNull, 1: Unknown, 2: NotNull + // ALOAD 1: 0: NotNull, 1: NotNull + // INVOKEVIRTUAL java/lang/Object.toString: 0: NotNull, 1: NotNull, 2: NotNull + // ARETURN: 0: NotNull, 1: NotNull, 2: Unknown + + for ((insn, index, nullness) <- List( + ("+NEW", 2, Unknown), // new value at slot 2 on the stack + ("+DUP", 3, Unknown), + ("+INVOKESPECIAL java/lang/Object", 2, NotNull), // after calling the initializer on 3, the value at 2 becomes NotNull + ("ASTORE 1", 1, Unknown), // before the ASTORE 1, nullness of the value in local 1 is Unknown + ("+ASTORE 1", 1, NotNull), // after storing the value at 2 in local 1, the local 1 is NotNull + ("+ALOAD 1", 2, NotNull), // loading the value 1 puts a NotNull value on the stack (at 2) + ("+INVOKEVIRTUAL java/lang/Object.toString", 2, Unknown) // nullness of value returned by `toString` is Unknown + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def explicitNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("def f = { var a: Object = null; a }") + val a = newNullnessAnalyzer(m) + for ((insn, index, nullness) <- List( + ("+ACONST_NULL", 2, Null), + ("+ASTORE 1", 1, Null), + ("+ALOAD 1", 2, Null) + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def stringLiteralsNotNull(): Unit = { + val List(m) = compileMethods(noOptCompiler)("""def f = { val a = "hi"; a.trim }""") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "+ASTORE 1", 1, NotNull) + } + + @Test + def newArraynotNull() { + val List(m) = compileMethods(noOptCompiler)("def f = { val a = new Array[Int](2); a(0) }") + val a = newNullnessAnalyzer(m) + testNullness(a, m, "+NEWARRAY T_INT", 2, NotNull) // new array on stack + testNullness(a, m, "+ASTORE 1", 1, NotNull) // local var (a) + } + + @Test + def aliasBranching(): Unit = { + val code = + """def f(o: Object) = { + | var a: Object = o // a and o are aliases + | var b: Object = null + | var c: Object = null + | var d: Object = o + | if ("".trim == "") { + | b = o + | c = o // a, o, b, aliases + | d = null + | } else { + | b = a // a, o, b aliases + | d = null + | } + | b.toString // a, o, b aliases (so they become NotNull), but not c + | // d is null here, assinged in both branches. + |} + """.stripMargin + val List(m) = compileMethods(noOptCompiler)(code) + val a = newNullnessAnalyzer(m) + + val trim = "INVOKEVIRTUAL java/lang/String.trim" + val toSt = "INVOKEVIRTUAL java/lang/Object.toString" + val end = s"+$toSt" + for ((insn, index, nullness) <- List( + (trim, 0, NotNull), // this + (trim, 1, Unknown), // parameter o + (trim, 2, Unknown), // a + (trim, 3, Null), // b + (trim, 4, Null), // c + (trim, 5, Unknown), // d + + (toSt, 2, Unknown), // a, still the same + (toSt, 3, Unknown), // b, was re-assinged in both branches to Unknown + (toSt, 4, Unknown), // c, was re-assigned in one branch to Unknown + (toSt, 5, Null), // d, was assigned to null in both branches + + (end, 2, NotNull), // a, NotNull (alias of b) + (end, 3, NotNull), // b, receiver of toString + (end, 4, Unknown), // c, no change (not an alias of b) + (end, 5, Null) // d, no change + )) testNullness(a, m, insn, index, nullness) + } + + @Test + def testInstanceOf(): Unit = { + val code = + """def f(a: Object) = { + | val x = a + | x.isInstanceOf[Throwable] // x and a remain unknown - INSTANCEOF doesn't throw a NPE on null + | x.toString // x and a are not null + | a.asInstanceOf[String].trim // the stack value (LOAD of local a) is still not-null after the CHECKCAST + |} + """.stripMargin + val List(m) = compileMethods(noOptCompiler)(code) + val a = newNullnessAnalyzer(m) + + val instof = "+INSTANCEOF" + val tost = "+INVOKEVIRTUAL java/lang/Object.toString" + val trim = "INVOKEVIRTUAL java/lang/String.trim" + + for ((insn, index, nullness) <- List( + (instof, 1, Unknown), // a after INSTANCEOF + (instof, 2, Unknown), // x after INSTANCEOF + (tost, 1, NotNull), + (tost, 2, NotNull), + (trim, 3, NotNull) // receiver at `trim` + )) testNullness(a, m, insn, index, nullness) + } +} diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala index b4839dcec8..7ed0e13226 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerIllegalAccessTest.scala @@ -32,7 +32,8 @@ class InlinerIllegalAccessTest extends ClearAfterClass { import compiler.genBCode.bTypes._ def addToRepo(cls: List[ClassNode]): Unit = for (c <- cls) byteCodeRepository.add(c, ByteCodeRepository.Classfile) - def assertEmpty(ins: Option[AbstractInsnNode]) = for (i <- ins) throw new AssertionError(textify(i)) + def assertEmpty(ins: Option[AbstractInsnNode]) = for (i <- ins) + throw new AssertionError(textify(i)) @Test def typeAccessible(): Unit = { @@ -176,15 +177,18 @@ class InlinerIllegalAccessTest extends ClearAfterClass { // PROTECTED - // protected accessed in same class, or protected static accessed in subclass(rgD). - // can be inlined to subclasses, and classes in the same package (gCl) - for ((m, declCls) <- Set((rcC, cCl), (rgC, cCl), (rgD, dCl)); c <- Set(cCl, dCl, eCl, fCl, gCl, hCl)) check(m, declCls, c, assertEmpty) + // protected static accessed in same class, or protected static accessed in subclass(rgD). + // can be inlined to sub- and superclasses, and classes in the same package (gCl) + for ((m, declCls) <- Set((rgC, cCl), (rgD, dCl)); c <- Set(cCl, dCl, eCl, fCl, gCl, hCl)) check(m, declCls, c, assertEmpty) // protected in non-subclass and different package for (m <- Set(rcC, rgC)) check(m, cCl, iCl, cOrDOwner) - // non-static protected accessed in subclass (rcD). can be inlined to related class, or classes in the same package - for (c <- Set(cCl, dCl, eCl, fCl, gCl)) check(rcD, dCl, c, assertEmpty) + // non-static protected accessed in subclass (rcD). + // can be inlined only if the destination class is related (sub- or superclass) or in the same package, + // AND if the receiver object is a subtype of the destination class + // TODO: we cannot check this yet, so the check flags the instruction as causing an IllegalAccess. https://github.com/scala-opt/scala/issues/13 + for ((m, declCls) <- Set((rcC, cCl), (rcD, dCl)); c <- Set(cCl, dCl, eCl, fCl, gCl)) check(m, declCls, c, cOrDOwner) // rcD cannot be inlined into non-related classes, if the declaration and destination are not in the same package for (c <- Set(hCl, iCl)) check(rcD, dCl, c, cOrDOwner) diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala index 0fc3601603..0309bb97cc 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/InlinerTest.scala @@ -503,7 +503,7 @@ class InlinerTest extends ClearAfterClass { |class C extends T """.stripMargin val List(c, t, tClass) = compile(code) - // the static implementaiton method is inlined into the mixin, so there's no invocation in the mixin + // the static implementation method is inlined into the mixin, so there's no invocation in the mixin assertNoInvoke(getSingleMethod(c, "f")) } @@ -975,4 +975,20 @@ class InlinerTest extends ClearAfterClass { val List(c) = compile(code) assertInvoke(getSingleMethod(c, "t"), "java/lang/Error", "<init>") } + + @Test + def noRedunantNullChecks(): Unit = { + val code = + """class C { + | @inline final def f: String = "hai!" + | def t(c: C) = {c.f; c.f} // null check on the first, but not the second + |} + """.stripMargin + + val List(c) = compile(code) + val t = getSingleMethod(c, "t").instructions + assertNoInvoke(t) + assert(2 == t.collect({case Ldc(_, "hai!") => }).size) // twice the body of f + assert(1 == t.collect({case Jump(IFNONNULL, _) => }).size) // one single null check + } } diff --git a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala index bd9964391b..8d910629ca 100644 --- a/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala +++ b/test/junit/scala/tools/nsc/backend/jvm/opt/MethodLevelOpts.scala @@ -56,7 +56,7 @@ class MethodLevelOpts extends ClearAfterClass { } @Test - def inlineReturnInCachtNotTry(): Unit = { + def inlineReturnInCatchNotTry(): Unit = { val code = "def f: Int = return { try 1 catch { case _: Throwable => 2 } }" // cannot inline the IRETURN into the try block (because RETURN may throw IllegalMonitorState) val m = singleMethod(methodOptCompiler)(code) 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) + } + } +} |