diff options
author | Paul Phillips <paulp@improving.org> | 2012-02-06 11:37:35 -0800 |
---|---|---|
committer | Paul Phillips <paulp@improving.org> | 2012-02-06 11:49:38 -0800 |
commit | 7539c4ee51c25a684399cd5400bf0285e6508fe2 (patch) | |
tree | 94a9eb9b9519417d1924711f56638a4be02f4a2b /test/files | |
parent | f0dcb3c87fe9c3214af6abe4e8d2032a8d51295c (diff) | |
parent | 93c2d93f4e7aaffaac92bdf14714a6c3871718c9 (diff) | |
download | scala-7539c4ee51c25a684399cd5400bf0285e6508fe2.tar.gz scala-7539c4ee51c25a684399cd5400bf0285e6508fe2.tar.bz2 scala-7539c4ee51c25a684399cd5400bf0285e6508fe2.zip |
Merge branch 'master' into topic/inline
Conflicts:
src/compiler/scala/tools/nsc/Global.scala
test/files/run/programmatic-main.check
Diffstat (limited to 'test/files')
39 files changed, 1291 insertions, 183 deletions
diff --git a/test/files/codelib/code.jar.desired.sha1 b/test/files/codelib/code.jar.desired.sha1 new file mode 100644 index 0000000000..5e7acf3b90 --- /dev/null +++ b/test/files/codelib/code.jar.desired.sha1 @@ -0,0 +1 @@ +5880dd44ee9fedec44fed3f223842e42d8a63959 ?code.jar diff --git a/test/files/jvm/serialization.check b/test/files/jvm/serialization.check index f58f763a76..67b77639a2 100644 --- a/test/files/jvm/serialization.check +++ b/test/files/jvm/serialization.check @@ -192,6 +192,10 @@ x = TreeSet(1, 2, 3) y = TreeSet(1, 2, 3) x equals y: true, y equals x: true +x = Ctrie(1 -> one, 2 -> two, 3 -> three) +y = Ctrie(1 -> one, 2 -> two, 3 -> three) +x equals y: true, y equals x: true + x = xml:src="hello" y = xml:src="hello" x equals y: true, y equals x: true @@ -283,6 +287,10 @@ x = ParHashMap(1 -> 2, 2 -> 4) y = ParHashMap(1 -> 2, 2 -> 4) x equals y: true, y equals x: true +x = ParCtrie(1 -> 2, 2 -> 4) +y = ParCtrie(1 -> 2, 2 -> 4) +x equals y: true, y equals x: true + x = ParHashSet(1, 2, 3) y = ParHashSet(1, 2, 3) x equals y: true, y equals x: true diff --git a/test/files/jvm/serialization.scala b/test/files/jvm/serialization.scala index 73bed2d46b..75daa8903d 100644 --- a/test/files/jvm/serialization.scala +++ b/test/files/jvm/serialization.scala @@ -286,7 +286,7 @@ object Test3_mutable { import scala.collection.mutable.{ ArrayBuffer, ArrayBuilder, ArraySeq, ArrayStack, BitSet, DoubleLinkedList, HashMap, HashSet, History, LinkedList, ListBuffer, Publisher, Queue, - Stack, StringBuilder, WrappedArray, TreeSet} + Stack, StringBuilder, WrappedArray, TreeSet, Ctrie} // in alphabetic order try { @@ -385,6 +385,11 @@ object Test3_mutable { val ts1 = TreeSet[Int]() ++= Array(1, 2, 3) val _ts1: TreeSet[Int] = read(write(ts1)) check(ts1, _ts1) + + // Ctrie + val ct1 = Ctrie[Int, String]() ++= Array(1 -> "one", 2 -> "two", 3 -> "three") + val _ct1: Ctrie[Int, String] = read(write(ct1)) + check(ct1, _ct1) } catch { case e: Exception => @@ -608,6 +613,11 @@ object Test9_parallel { val _mpm: mutable.ParHashMap[Int, Int] = read(write(mpm)) check(mpm, _mpm) + // mutable.ParCtrie + val mpc = mutable.ParCtrie(1 -> 2, 2 -> 4) + val _mpc: mutable.ParCtrie[Int, Int] = read(write(mpc)) + check(mpc, _mpc) + // mutable.ParHashSet val mps = mutable.ParHashSet(1, 2, 3) val _mps: mutable.ParHashSet[Int] = read(write(mps)) diff --git a/test/files/pos/t531.scala b/test/files/pos/t531.scala index 02763e08f1..856926de4f 100644 --- a/test/files/pos/t531.scala +++ b/test/files/pos/t531.scala @@ -2,9 +2,9 @@ object Test extends App { import scala.reflect._; def titi = { var truc = 0 - val tata: Code[()=>Unit] = () => { + val tata = Code.lift{() => { truc = 6 - } + }} () } } diff --git a/test/files/pos/t532.scala b/test/files/pos/t532.scala index 32649b1629..f864bbf45e 100644 --- a/test/files/pos/t532.scala +++ b/test/files/pos/t532.scala @@ -2,9 +2,9 @@ object Test extends App { import scala.reflect._; def titi: Unit = { var truc = 0 - val tata: Code[()=>Unit] = () => { + val tata = Code.lift{() => { truc = truc + 6 - } + }} () } } diff --git a/test/files/run/code.check b/test/files/run/code.check deleted file mode 100644 index 9b0351bbf9..0000000000 --- a/test/files/run/code.check +++ /dev/null @@ -1,36 +0,0 @@ -testing: ((x: Int) => x.$plus(ys.length)) -type is: Int => Int -result = ((x: Int) => x.+{(x: <?>)Int}(ys.length{Int}){Int}){Int => Int} -evaluated = <function1> -testing: (() => { - val e: Element = new Element("someName"); - e -}) -type is: () => Element -result = (() => { - val e: Element = new Element{Element}{(name: <?>)Element}("someName"{String("someName")}){Element}; - e{Element} -}{Element}){() => Element} -evaluated = Element(someName) -testing: (() => truc.elem = 6) -type is: () => Unit -result = (() => truc.elem{Int} = 6{Int(6)}{Unit}){() => Unit} -evaluated = null -testing: (() => truc.elem = truc.elem.$plus(6)) -type is: () => Unit -result = (() => truc.elem{Int} = truc.elem.+{(x: <?>)Int}(6{Int(6)}){Int}{Unit}){() => Unit} -evaluated = null -testing: (() => new baz.BazElement("someName")) -type is: () => baz.BazElement -result = (() => new baz.BazElement{baz.BazElement}{(name: <?>)baz.BazElement}("someName"{String("someName")}){baz.BazElement}){() => baz.BazElement} -evaluated = BazElement(someName) -testing: ((x: Int) => x.$plus(ys.length)) -type is: Int => Int -result = ((x: Int) => x.+{(x: <?>)Int}(ys.length{Int}){Int}){Int => Int} -evaluated = <function1> -static: 2 -testing: (() => x.$plus(1)) -type is: () => Int -result = (() => x.+{(x: <?>)Int}(1{Int(1)}){Int}){() => Int} -evaluated = 2 -1+1 = 2 diff --git a/test/files/run/code.scala b/test/files/run/code.scala deleted file mode 100644 index 162f796c63..0000000000 --- a/test/files/run/code.scala +++ /dev/null @@ -1,60 +0,0 @@ -import scala.tools.partest.utils.CodeTest - -case class Element(name: String) - -object Test extends App { - case class InnerElement(name: String) - def foo[T](ys: List[T]) = { - val fun: reflect.Code[Int => Int] = x => x + ys.length - fun - } - CodeTest(foo(List(2)), args) - CodeTest({() => val e = Element("someName"); e}, args) -// CodeTest({() => val e = InnerElement("someName"); e}, args) // (does not work yet) - def titi() = { - var truc = 0 - CodeTest(() => { - truc = 6 - }, args) - } - def tata(): Unit = { - var truc = 0 - CodeTest(() => { - truc = truc + 6 - }, args) - } - titi() - tata() - new baz.A(args) - - def show() { - def foo[T](ys: List[T]) = { - val fun: reflect.Code[Int => Int] = x => x + ys.length - CodeTest(fun, args) - } - foo(List(1, 2, 3)) - } - - show() - - def evaltest(x: Int) = { - CodeTest.static(() => x + 1, args) - CodeTest(() => x + 1, args) - } - - println("1+1 = "+evaltest(1)) -} - - -package baz { - - case class BazElement(name: String) { } - - class A(args: Array[String]) { - CodeTest(() => new baz.BazElement("someName"), args) - } - -} - - - diff --git a/test/files/run/ctries/DumbHash.scala b/test/files/run/ctries/DumbHash.scala new file mode 100644 index 0000000000..8ef325b67c --- /dev/null +++ b/test/files/run/ctries/DumbHash.scala @@ -0,0 +1,14 @@ + + + + + + +class DumbHash(val i: Int) { + override def equals(other: Any) = other match { + case that: DumbHash => that.i == this.i + case _ => false + } + override def hashCode = i % 5 + override def toString = "DH(%s)".format(i) +} diff --git a/test/files/run/ctries/Wrap.scala b/test/files/run/ctries/Wrap.scala new file mode 100644 index 0000000000..7b645c1612 --- /dev/null +++ b/test/files/run/ctries/Wrap.scala @@ -0,0 +1,9 @@ + + + + + + +case class Wrap(i: Int) { + override def hashCode = i * 0x9e3775cd +} diff --git a/test/files/run/ctries/concmap.scala b/test/files/run/ctries/concmap.scala new file mode 100644 index 0000000000..85a305ce5b --- /dev/null +++ b/test/files/run/ctries/concmap.scala @@ -0,0 +1,169 @@ + + + +import collection.mutable.Ctrie + + +object ConcurrentMapSpec extends Spec { + + val initsz = 500 + val secondsz = 750 + + def test() { + "support put" in { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until initsz) assert(ct.put(new Wrap(i), i) == None) + for (i <- 0 until initsz) assert(ct.put(new Wrap(i), -i) == Some(i)) + } + + "support put if absent" in { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until initsz) ct.update(new Wrap(i), i) + for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i)) + for (i <- 0 until initsz) assert(ct.putIfAbsent(new Wrap(i), -i) == Some(i)) + for (i <- initsz until secondsz) assert(ct.putIfAbsent(new Wrap(i), -i) == None) + for (i <- initsz until secondsz) assert(ct.putIfAbsent(new Wrap(i), i) == Some(-i)) + } + + "support remove if mapped to a specific value" in { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until initsz) ct.update(new Wrap(i), i) + for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), -i - 1) == false) + for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), i) == true) + for (i <- 0 until initsz) assert(ct.remove(new Wrap(i), i) == false) + } + + "support replace if mapped to a specific value" in { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until initsz) ct.update(new Wrap(i), i) + for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i - 1, -i - 2) == false) + for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i, -i - 2) == true) + for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i, -i - 2) == false) + for (i <- initsz until secondsz) assert(ct.replace(new Wrap(i), i, 0) == false) + } + + "support replace if present" in { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until initsz) ct.update(new Wrap(i), i) + for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), -i) == Some(i)) + for (i <- 0 until initsz) assert(ct.replace(new Wrap(i), i) == Some(-i)) + for (i <- initsz until secondsz) assert(ct.replace(new Wrap(i), i) == None) + } + + def assertEqual(a: Any, b: Any) = { + if (a != b) println(a, b) + assert(a == b) + } + + "support replace if mapped to a specific value, using several threads" in { + val ct = new Ctrie[Wrap, Int] + val sz = 55000 + for (i <- 0 until sz) ct.update(new Wrap(i), i) + + class Updater(index: Int, offs: Int) extends Thread { + override def run() { + var repeats = 0 + for (i <- 0 until sz) { + val j = (offs + i) % sz + var k = Int.MaxValue + do { + if (k != Int.MaxValue) repeats += 1 + k = ct.lookup(new Wrap(j)) + } while (!ct.replace(new Wrap(j), k, -k)) + } + //println("Thread %d repeats: %d".format(index, repeats)) + } + } + + val threads = for (i <- 0 until 16) yield new Updater(i, sz / 32 * i) + threads.foreach(_.start()) + threads.foreach(_.join()) + + for (i <- 0 until sz) assertEqual(ct(new Wrap(i)), i) + + val threads2 = for (i <- 0 until 15) yield new Updater(i, sz / 32 * i) + threads2.foreach(_.start()) + threads2.foreach(_.join()) + + for (i <- 0 until sz) assertEqual(ct(new Wrap(i)), -i) + } + + "support put if absent, several threads" in { + val ct = new Ctrie[Wrap, Int] + val sz = 110000 + + class Updater(offs: Int) extends Thread { + override def run() { + for (i <- 0 until sz) { + val j = (offs + i) % sz + ct.putIfAbsent(new Wrap(j), j) + assert(ct.lookup(new Wrap(j)) == j) + } + } + } + + val threads = for (i <- 0 until 16) yield new Updater(sz / 32 * i) + threads.foreach(_.start()) + threads.foreach(_.join()) + + for (i <- 0 until sz) assert(ct(new Wrap(i)) == i) + } + + "support remove if mapped to a specific value, several threads" in { + val ct = new Ctrie[Wrap, Int] + val sz = 55000 + for (i <- 0 until sz) ct.update(new Wrap(i), i) + + class Remover(offs: Int) extends Thread { + override def run() { + for (i <- 0 until sz) { + val j = (offs + i) % sz + ct.remove(new Wrap(j), j) + assert(ct.get(new Wrap(j)) == None) + } + } + } + + val threads = for (i <- 0 until 16) yield new Remover(sz / 32 * i) + threads.foreach(_.start()) + threads.foreach(_.join()) + + for (i <- 0 until sz) assert(ct.get(new Wrap(i)) == None) + } + + "have all or none of the elements depending on the oddity" in { + val ct = new Ctrie[Wrap, Int] + val sz = 65000 + for (i <- 0 until sz) ct(new Wrap(i)) = i + + class Modifier(index: Int, offs: Int) extends Thread { + override def run() { + for (j <- 0 until sz) { + val i = (offs + j) % sz + var success = false + do { + if (ct.contains(new Wrap(i))) { + success = ct.remove(new Wrap(i)) != None + } else { + success = ct.putIfAbsent(new Wrap(i), i) == None + } + } while (!success) + } + } + } + + def modify(n: Int) = { + val threads = for (i <- 0 until n) yield new Modifier(i, sz / n * i) + threads.foreach(_.start()) + threads.foreach(_.join()) + } + + modify(16) + for (i <- 0 until sz) assertEqual(ct.get(new Wrap(i)), Some(i)) + modify(15) + for (i <- 0 until sz) assertEqual(ct.get(new Wrap(i)), None) + } + + } + +} diff --git a/test/files/run/ctries/iterator.scala b/test/files/run/ctries/iterator.scala new file mode 100644 index 0000000000..4bbf9009f0 --- /dev/null +++ b/test/files/run/ctries/iterator.scala @@ -0,0 +1,279 @@ + + + + +import collection._ +import collection.mutable.Ctrie + + + +object IteratorSpec extends Spec { + + def test() { + "work for an empty trie" in { + val ct = new Ctrie + val it = ct.iterator + + it.hasNext shouldEqual (false) + evaluating { it.next() }.shouldProduce [NoSuchElementException] + } + + def nonEmptyIteratorCheck(sz: Int) { + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct.put(new Wrap(i), i) + + val it = ct.iterator + val tracker = mutable.Map[Wrap, Int]() + for (i <- 0 until sz) { + assert(it.hasNext == true) + tracker += it.next + } + + it.hasNext shouldEqual (false) + evaluating { it.next() }.shouldProduce [NoSuchElementException] + tracker.size shouldEqual (sz) + tracker shouldEqual (ct) + } + + "work for a 1 element trie" in { + nonEmptyIteratorCheck(1) + } + + "work for a 2 element trie" in { + nonEmptyIteratorCheck(2) + } + + "work for a 3 element trie" in { + nonEmptyIteratorCheck(3) + } + + "work for a 5 element trie" in { + nonEmptyIteratorCheck(5) + } + + "work for a 10 element trie" in { + nonEmptyIteratorCheck(10) + } + + "work for a 20 element trie" in { + nonEmptyIteratorCheck(20) + } + + "work for a 50 element trie" in { + nonEmptyIteratorCheck(50) + } + + "work for a 100 element trie" in { + nonEmptyIteratorCheck(100) + } + + "work for a 1k element trie" in { + nonEmptyIteratorCheck(1000) + } + + "work for a 5k element trie" in { + nonEmptyIteratorCheck(5000) + } + + "work for a 75k element trie" in { + nonEmptyIteratorCheck(75000) + } + + "work for a 250k element trie" in { + nonEmptyIteratorCheck(500000) + } + + def nonEmptyCollideCheck(sz: Int) { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until sz) ct.put(new DumbHash(i), i) + + val it = ct.iterator + val tracker = mutable.Map[DumbHash, Int]() + for (i <- 0 until sz) { + assert(it.hasNext == true) + tracker += it.next + } + + it.hasNext shouldEqual (false) + evaluating { it.next() }.shouldProduce [NoSuchElementException] + tracker.size shouldEqual (sz) + tracker shouldEqual (ct) + } + + "work for colliding hashcodes, 2 element trie" in { + nonEmptyCollideCheck(2) + } + + "work for colliding hashcodes, 3 element trie" in { + nonEmptyCollideCheck(3) + } + + "work for colliding hashcodes, 5 element trie" in { + nonEmptyCollideCheck(5) + } + + "work for colliding hashcodes, 10 element trie" in { + nonEmptyCollideCheck(10) + } + + "work for colliding hashcodes, 100 element trie" in { + nonEmptyCollideCheck(100) + } + + "work for colliding hashcodes, 500 element trie" in { + nonEmptyCollideCheck(500) + } + + "work for colliding hashcodes, 5k element trie" in { + nonEmptyCollideCheck(5000) + } + + def assertEqual(a: Map[Wrap, Int], b: Map[Wrap, Int]) { + if (a != b) { + println(a.size + " vs " + b.size) + // println(a) + // println(b) + // println(a.toSeq.sortBy((x: (Wrap, Int)) => x._1.i)) + // println(b.toSeq.sortBy((x: (Wrap, Int)) => x._1.i)) + } + assert(a == b) + } + + "be consistent when taken with concurrent modifications" in { + val sz = 25000 + val W = 15 + val S = 5 + val checks = 5 + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct.put(new Wrap(i), i) + + class Modifier extends Thread { + override def run() { + for (i <- 0 until sz) ct.putIfAbsent(new Wrap(i), i) match { + case Some(_) => ct.remove(new Wrap(i)) + case None => + } + } + } + + def consistentIteration(ct: Ctrie[Wrap, Int], checks: Int) { + class Iter extends Thread { + override def run() { + val snap = ct.readOnlySnapshot() + val initial = mutable.Map[Wrap, Int]() + for (kv <- snap) initial += kv + + for (i <- 0 until checks) { + assertEqual(snap.iterator.toMap, initial) + } + } + } + + val iter = new Iter + iter.start() + iter.join() + } + + val threads = for (_ <- 0 until W) yield new Modifier + threads.foreach(_.start()) + for (_ <- 0 until S) consistentIteration(ct, checks) + threads.foreach(_.join()) + } + + "be consistent with a concurrent removal with a well defined order" in { + val sz = 150000 + val sgroupsize = 10 + val sgroupnum = 5 + val removerslowdown = 50 + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct.put(new Wrap(i), i) + + class Remover extends Thread { + override def run() { + for (i <- 0 until sz) { + assert(ct.remove(new Wrap(i)) == Some(i)) + for (i <- 0 until removerslowdown) ct.get(new Wrap(i)) // slow down, mate + } + //println("done removing") + } + } + + def consistentIteration(it: Iterator[(Wrap, Int)]) = { + class Iter extends Thread { + override def run() { + val elems = it.toBuffer + if (elems.nonEmpty) { + val minelem = elems.minBy((x: (Wrap, Int)) => x._1.i)._1.i + assert(elems.forall(_._1.i >= minelem)) + } + } + } + new Iter + } + + val remover = new Remover + remover.start() + for (_ <- 0 until sgroupnum) { + val iters = for (_ <- 0 until sgroupsize) yield consistentIteration(ct.iterator) + iters.foreach(_.start()) + iters.foreach(_.join()) + } + //println("done with iterators") + remover.join() + } + + "be consistent with a concurrent insertion with a well defined order" in { + val sz = 150000 + val sgroupsize = 10 + val sgroupnum = 10 + val inserterslowdown = 50 + val ct = new Ctrie[Wrap, Int] + + class Inserter extends Thread { + override def run() { + for (i <- 0 until sz) { + assert(ct.put(new Wrap(i), i) == None) + for (i <- 0 until inserterslowdown) ct.get(new Wrap(i)) // slow down, mate + } + //println("done inserting") + } + } + + def consistentIteration(it: Iterator[(Wrap, Int)]) = { + class Iter extends Thread { + override def run() { + val elems = it.toSeq + if (elems.nonEmpty) { + val maxelem = elems.maxBy((x: (Wrap, Int)) => x._1.i)._1.i + assert(elems.forall(_._1.i <= maxelem)) + } + } + } + new Iter + } + + val inserter = new Inserter + inserter.start() + for (_ <- 0 until sgroupnum) { + val iters = for (_ <- 0 until sgroupsize) yield consistentIteration(ct.iterator) + iters.foreach(_.start()) + iters.foreach(_.join()) + } + //println("done with iterators") + inserter.join() + } + + "work on a yet unevaluated snapshot" in { + val sz = 50000 + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct.update(new Wrap(i), i) + + val snap = ct.snapshot() + val it = snap.iterator + + while (it.hasNext) it.next() + } + + } + +} diff --git a/test/files/run/ctries/lnode.scala b/test/files/run/ctries/lnode.scala new file mode 100644 index 0000000000..88cbeed1f6 --- /dev/null +++ b/test/files/run/ctries/lnode.scala @@ -0,0 +1,61 @@ + + + +import collection.mutable.Ctrie + + +object LNodeSpec extends Spec { + + val initsz = 1500 + val secondsz = 1750 + + def test() { + "accept elements with the same hash codes" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) ct.update(new DumbHash(i), i) + } + + "lookup elements with the same hash codes" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) ct.update(new DumbHash(i), i) + for (i <- 0 until initsz) assert(ct.get(new DumbHash(i)) == Some(i)) + for (i <- initsz until secondsz) assert(ct.get(new DumbHash(i)) == None) + } + + "remove elements with the same hash codes" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) ct.update(new DumbHash(i), i) + for (i <- 0 until initsz) { + val remelem = ct.remove(new DumbHash(i)) + assert(remelem == Some(i), "removing " + i + " yields " + remelem) + } + for (i <- 0 until initsz) assert(ct.get(new DumbHash(i)) == None) + } + + "put elements with the same hash codes if absent" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) ct.put(new DumbHash(i), i) + for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i) + for (i <- 0 until initsz) assert(ct.putIfAbsent(new DumbHash(i), i) == Some(i)) + for (i <- initsz until secondsz) assert(ct.putIfAbsent(new DumbHash(i), i) == None) + for (i <- initsz until secondsz) assert(ct.lookup(new DumbHash(i)) == i) + } + + "replace elements with the same hash codes" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None) + for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == i) + for (i <- 0 until initsz) assert(ct.replace(new DumbHash(i), -i) == Some(i)) + for (i <- 0 until initsz) assert(ct.lookup(new DumbHash(i)) == -i) + for (i <- 0 until initsz) assert(ct.replace(new DumbHash(i), -i, i) == true) + } + + "remove elements with the same hash codes if mapped to a specific value" in { + val ct = new Ctrie[DumbHash, Int] + for (i <- 0 until initsz) assert(ct.put(new DumbHash(i), i) == None) + for (i <- 0 until initsz) assert(ct.remove(new DumbHash(i), i) == true) + } + + } + +} diff --git a/test/files/run/ctries/main.scala b/test/files/run/ctries/main.scala new file mode 100644 index 0000000000..8db7fcef54 --- /dev/null +++ b/test/files/run/ctries/main.scala @@ -0,0 +1,45 @@ + + + + + + + +object Test { + + def main(args: Array[String]) { + ConcurrentMapSpec.test() + IteratorSpec.test() + LNodeSpec.test() + SnapshotSpec.test() + } + +} + + +trait Spec { + + implicit def str2ops(s: String) = new { + def in[U](body: =>U) { + // just execute body + body + } + } + + implicit def any2ops(a: Any) = new { + def shouldEqual(other: Any) = assert(a == other) + } + + def evaluating[U](body: =>U) = new { + def shouldProduce[T <: Throwable: ClassManifest]() = { + var produced = false + try body + catch { + case e => if (e.getClass == implicitly[ClassManifest[T]].erasure) produced = true + } finally { + assert(produced, "Did not produce exception of type: " + implicitly[ClassManifest[T]]) + } + } + } + +} diff --git a/test/files/run/ctries/snapshot.scala b/test/files/run/ctries/snapshot.scala new file mode 100644 index 0000000000..69073d3f06 --- /dev/null +++ b/test/files/run/ctries/snapshot.scala @@ -0,0 +1,267 @@ + + + + +import collection._ +import collection.mutable.Ctrie + + + +object SnapshotSpec extends Spec { + + def test() { + "support snapshots" in { + val ctn = new Ctrie + ctn.snapshot() + ctn.readOnlySnapshot() + + val ct = new Ctrie[Int, Int] + for (i <- 0 until 100) ct.put(i, i) + ct.snapshot() + ct.readOnlySnapshot() + } + + "empty 2 quiescent snapshots in isolation" in { + val sz = 4000 + + class Worker(trie: Ctrie[Wrap, Int]) extends Thread { + override def run() { + for (i <- 0 until sz) { + assert(trie.remove(new Wrap(i)) == Some(i)) + for (j <- 0 until sz) + if (j <= i) assert(trie.get(new Wrap(j)) == None) + else assert(trie.get(new Wrap(j)) == Some(j)) + } + } + } + + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct.put(new Wrap(i), i) + val snapt = ct.snapshot() + + val original = new Worker(ct) + val snapshot = new Worker(snapt) + original.start() + snapshot.start() + original.join() + snapshot.join() + + for (i <- 0 until sz) { + assert(ct.get(new Wrap(i)) == None) + assert(snapt.get(new Wrap(i)) == None) + } + } + + def consistentReadOnly(name: String, readonly: Map[Wrap, Int], sz: Int, N: Int) { + @volatile var e: Exception = null + + // reads possible entries once and stores them + // then reads all these N more times to check if the + // state stayed the same + class Reader(trie: Map[Wrap, Int]) extends Thread { + setName("Reader " + name) + + override def run() = + try check() + catch { + case ex: Exception => e = ex + } + + def check() { + val initial = mutable.Map[Wrap, Int]() + for (i <- 0 until sz) trie.get(new Wrap(i)) match { + case Some(i) => initial.put(new Wrap(i), i) + case None => // do nothing + } + + for (k <- 0 until N) { + for (i <- 0 until sz) { + val tres = trie.get(new Wrap(i)) + val ires = initial.get(new Wrap(i)) + if (tres != ires) println(i, "initially: " + ires, "traversal %d: %s".format(k, tres)) + assert(tres == ires) + } + } + } + } + + val reader = new Reader(readonly) + reader.start() + reader.join() + + if (e ne null) { + e.printStackTrace() + throw e + } + } + + // traverses the trie `rep` times and modifies each entry + class Modifier(trie: Ctrie[Wrap, Int], index: Int, rep: Int, sz: Int) extends Thread { + setName("Modifier %d".format(index)) + + override def run() { + for (k <- 0 until rep) { + for (i <- 0 until sz) trie.putIfAbsent(new Wrap(i), i) match { + case Some(_) => trie.remove(new Wrap(i)) + case None => // do nothing + } + } + } + } + + // removes all the elements from the trie + class Remover(trie: Ctrie[Wrap, Int], index: Int, totremovers: Int, sz: Int) extends Thread { + setName("Remover %d".format(index)) + + override def run() { + for (i <- 0 until sz) trie.remove(new Wrap((i + sz / totremovers * index) % sz)) + } + } + + "have a consistent quiescent read-only snapshot" in { + val sz = 10000 + val N = 100 + val W = 10 + + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(new Wrap(i)) = i + val readonly = ct.readOnlySnapshot() + val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) + + threads.foreach(_.start()) + consistentReadOnly("qm", readonly, sz, N) + threads.foreach(_.join()) + } + + // now, we check non-quiescent snapshots, as these permit situations + // where a thread is caught in the middle of the update when a snapshot is taken + + "have a consistent non-quiescent read-only snapshot, concurrent with removes only" in { + val sz = 1250 + val W = 100 + val S = 5000 + + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(new Wrap(i)) = i + val threads = for (i <- 0 until W) yield new Remover(ct, i, W, sz) + + threads.foreach(_.start()) + for (i <- 0 until S) consistentReadOnly("non-qr", ct.readOnlySnapshot(), sz, 5) + threads.foreach(_.join()) + } + + "have a consistent non-quiescent read-only snapshot, concurrent with modifications" in { + val sz = 1000 + val N = 7000 + val W = 10 + val S = 7000 + + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(new Wrap(i)) = i + val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) + + threads.foreach(_.start()) + for (i <- 0 until S) consistentReadOnly("non-qm", ct.readOnlySnapshot(), sz, 5) + threads.foreach(_.join()) + } + + def consistentNonReadOnly(name: String, trie: Ctrie[Wrap, Int], sz: Int, N: Int) { + @volatile var e: Exception = null + + // reads possible entries once and stores them + // then reads all these N more times to check if the + // state stayed the same + class Worker extends Thread { + setName("Worker " + name) + + override def run() = + try check() + catch { + case ex: Exception => e = ex + } + + def check() { + val initial = mutable.Map[Wrap, Int]() + for (i <- 0 until sz) trie.get(new Wrap(i)) match { + case Some(i) => initial.put(new Wrap(i), i) + case None => // do nothing + } + + for (k <- 0 until N) { + // modify + for ((key, value) <- initial) { + val oldv = if (k % 2 == 0) value else -value + val newv = -oldv + trie.replace(key, oldv, newv) + } + + // check + for (i <- 0 until sz) if (initial.contains(new Wrap(i))) { + val expected = if (k % 2 == 0) -i else i + //println(trie.get(new Wrap(i))) + assert(trie.get(new Wrap(i)) == Some(expected)) + } else { + assert(trie.get(new Wrap(i)) == None) + } + } + } + } + + val worker = new Worker + worker.start() + worker.join() + + if (e ne null) { + e.printStackTrace() + throw e + } + } + + "have a consistent non-quiescent snapshot, concurrent with modifications" in { + val sz = 9000 + val N = 1000 + val W = 10 + val S = 400 + + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(new Wrap(i)) = i + val threads = for (i <- 0 until W) yield new Modifier(ct, i, N, sz) + + threads.foreach(_.start()) + for (i <- 0 until S) { + consistentReadOnly("non-qm", ct.snapshot(), sz, 5) + consistentNonReadOnly("non-qsnap", ct.snapshot(), sz, 5) + } + threads.foreach(_.join()) + } + + "work when many concurrent snapshots are taken, concurrent with modifications" in { + val sz = 12000 + val W = 10 + val S = 10 + val modifytimes = 1200 + val snaptimes = 600 + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(new Wrap(i)) = i + + class Snapshooter extends Thread { + setName("Snapshooter") + override def run() { + for (k <- 0 until snaptimes) { + val snap = ct.snapshot() + for (i <- 0 until sz) snap.remove(new Wrap(i)) + for (i <- 0 until sz) assert(!snap.contains(new Wrap(i))) + } + } + } + + val mods = for (i <- 0 until W) yield new Modifier(ct, i, modifytimes, sz) + val shooters = for (i <- 0 until S) yield new Snapshooter + val threads = mods ++ shooters + threads.foreach(_.start()) + threads.foreach(_.join()) + } + + } + +} diff --git a/test/files/run/programmatic-main.check b/test/files/run/programmatic-main.check index a24de79b8a..b5a54f5ea7 100644 --- a/test/files/run/programmatic-main.check +++ b/test/files/run/programmatic-main.check @@ -8,23 +8,22 @@ superaccessors 6 add super accessors in traits and nested classes pickler 7 serialize symbol tables refchecks 8 reference/override checking, translate nested objects - liftcode 9 reify trees - uncurry 10 uncurry, translate function values to anonymous classes - tailcalls 11 replace tail calls by jumps - specialize 12 @specialized-driven class and method specialization - explicitouter 13 this refs to outer pointers, translate patterns - erasure 14 erase types, add interfaces for traits - lazyvals 15 allocate bitmaps, translate lazy vals into lazified defs - lambdalift 16 move nested functions to top level - constructors 17 move field definitions into constructors - flatten 18 eliminate inner classes - mixin 19 mixin composition - cleanup 20 platform-specific cleanups, generate reflective calls - icode 21 generate portable intermediate code - inliner 22 optimization: do inlining -inlineExceptionHandlers 23 optimization: inline exception handlers - closelim 24 optimization: eliminate uncalled closures - dce 25 optimization: eliminate dead code - jvm 26 generate JVM bytecode - terminal 27 The last phase in the compiler chain + uncurry 9 uncurry, translate function values to anonymous classes + tailcalls 10 replace tail calls by jumps + specialize 11 @specialized-driven class and method specialization + explicitouter 12 this refs to outer pointers, translate patterns + erasure 13 erase types, add interfaces for traits + lazyvals 14 allocate bitmaps, translate lazy vals into lazified defs + lambdalift 15 move nested functions to top level + constructors 16 move field definitions into constructors + flatten 17 eliminate inner classes + mixin 18 mixin composition + cleanup 19 platform-specific cleanups, generate reflective calls + icode 20 generate portable intermediate code + inliner 21 optimization: do inlining +inlineExceptionHandlers 22 optimization: inline exception handlers + closelim 23 optimization: eliminate uncalled closures + dce 24 optimization: eliminate dead code + jvm 25 generate JVM bytecode + terminal 26 The last phase in the compiler chain diff --git a/test/files/run/reflection-implClass.scala b/test/files/run/reflection-implClass.scala index 2b30e29bb3..7718b52f33 100644 --- a/test/files/run/reflection-implClass.scala +++ b/test/files/run/reflection-implClass.scala @@ -8,19 +8,19 @@ object Test extends App with Outer { import scala.reflect.mirror - assert(mirror.classToSymbol(manifest[Foo].erasure).typeSig.declaration(mirror.newTermName("bar")).typeSig == - mirror.classToSymbol(manifest[Bar].erasure).typeSig.declaration(mirror.newTermName("foo")).typeSig) + assert(mirror.classToSymbol(manifest[Foo].erasure).typeSignature.declaration(mirror.newTermName("bar")).typeSignature == + mirror.classToSymbol(manifest[Bar].erasure).typeSignature.declaration(mirror.newTermName("foo")).typeSignature) val s1 = implClass(manifest[Foo].erasure) assert(s1 != mirror.NoSymbol) - assert(s1.typeSig != mirror.NoType) - assert(s1.companionModule.typeSig != mirror.NoType) - assert(s1.companionModule.typeSig.declaration(mirror.newTermName("bar")) != mirror.NoSymbol) + assert(s1.typeSignature != mirror.NoType) + assert(s1.companionSymbol.typeSignature != mirror.NoType) + assert(s1.companionSymbol.typeSignature.declaration(mirror.newTermName("bar")) != mirror.NoSymbol) val s2 = implClass(manifest[Bar].erasure) assert(s2 != mirror.NoSymbol) - assert(s2.typeSig != mirror.NoType) - assert(s2.companionModule.typeSig != mirror.NoType) - assert(s2.companionModule.typeSig.declaration(mirror.newTermName("foo")) != mirror.NoSymbol) + assert(s2.typeSignature != mirror.NoType) + assert(s2.companionSymbol.typeSignature != mirror.NoType) + assert(s2.companionSymbol.typeSignature.declaration(mirror.newTermName("foo")) != mirror.NoSymbol) def implClass(clazz: Class[_]) = { val implClass = Class.forName(clazz.getName + "$class") mirror.classToSymbol(implClass) diff --git a/test/files/run/reify_closure1.scala b/test/files/run/reify_closure1.scala index 825a38dc1d..960f6aec3e 100644 --- a/test/files/run/reify_closure1.scala +++ b/test/files/run/reify_closure1.scala @@ -4,9 +4,9 @@ import reflect.runtime.Mirror.ToolBox object Test extends App { def foo[T](ys: List[T]): Int => Int = { - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { x - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure2a.scala b/test/files/run/reify_closure2a.scala index b88bec005d..6c28514c2b 100644 --- a/test/files/run/reify_closure2a.scala +++ b/test/files/run/reify_closure2a.scala @@ -4,9 +4,9 @@ import reflect.runtime.Mirror.ToolBox object Test extends App { def foo(y: Int): Int => Int = { - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { x + y - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure3a.scala b/test/files/run/reify_closure3a.scala index 6414fa58a3..4444c55ddf 100644 --- a/test/files/run/reify_closure3a.scala +++ b/test/files/run/reify_closure3a.scala @@ -6,9 +6,9 @@ object Test extends App { def foo(y: Int): Int => Int = { def y1 = y - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { x + y1 - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure4a.scala b/test/files/run/reify_closure4a.scala index 99e9d82706..886e643a47 100644 --- a/test/files/run/reify_closure4a.scala +++ b/test/files/run/reify_closure4a.scala @@ -6,9 +6,9 @@ object Test extends App { def foo(y: Int): Int => Int = { val y1 = y - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { x + y1 - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure5a.scala b/test/files/run/reify_closure5a.scala index 0ac53d5479..20994abff0 100644 --- a/test/files/run/reify_closure5a.scala +++ b/test/files/run/reify_closure5a.scala @@ -4,9 +4,9 @@ import reflect.runtime.Mirror.ToolBox object Test extends App { def foo[T](ys: List[T]): Int => Int = { - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { x + ys.length - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure6.scala b/test/files/run/reify_closure6.scala index 54f1791bf2..192c08f701 100644 --- a/test/files/run/reify_closure6.scala +++ b/test/files/run/reify_closure6.scala @@ -7,13 +7,13 @@ object Test extends App { def foo[T](ys: List[T]): Int => Int = { val z = 1 var y = 0 - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { y += 1 q += 1 println("q = " + q) println("y = " + y) x + ys.length * z + q + y - } + }} val reporter = new ConsoleReporter(new Settings) val toolbox = new ToolBox(reporter) diff --git a/test/files/run/reify_closure7.scala b/test/files/run/reify_closure7.scala index 8933df23fa..942c2cda9c 100644 --- a/test/files/run/reify_closure7.scala +++ b/test/files/run/reify_closure7.scala @@ -8,13 +8,13 @@ object Test extends App { def foo[T](ys: List[T]): Int => Int = { val z = 1 var y = 0 - val fun: reflect.Code[Int => Int] = x => { + val fun = reflect.Code.lift{(x: Int) => { y += 1 q += 1 println("q = " + q) println("y = " + y) x + ys.length * z + q + y - } + }} if (clo == null) { val reporter = new ConsoleReporter(new Settings) diff --git a/test/files/run/reify_this.scala b/test/files/run/reify_this.scala index 38ef72b6eb..44a25ae1b6 100644 --- a/test/files/run/reify_this.scala +++ b/test/files/run/reify_this.scala @@ -5,7 +5,7 @@ import scala.tools.nsc.Settings import reflect.runtime.Mirror.ToolBox trait Eval { - def eval(code: Code[_]): Any = eval(code.tree) + def eval(code: Code): Any = eval(code.tree) def eval(tree: Tree): Any = { val settings = new Settings diff --git a/test/files/run/t4875.check b/test/files/run/t4875.check deleted file mode 100644 index f7609d5ca5..0000000000 --- a/test/files/run/t4875.check +++ /dev/null @@ -1,17 +0,0 @@ -Type in expressions to have them evaluated. -Type :help for more information. - -scala> - -scala> import scala.reflect.Code -import scala.reflect.Code - -scala> def codeOf[A](code: Code[A]) = code -codeOf: [A](code: scala.reflect.Code[A])scala.reflect.Code[A] - -scala> codeOf((x: Iterable[_]) => throw new Exception) -res0: scala.reflect.Code[Iterable[_] => Nothing] = Code(tree = ((x: Iterable[Any]) => throw new scala.`package`.Exception()), manifest = scala.Function1[scala.collection.Iterable[Any], Nothing]) - -scala> - -scala> diff --git a/test/files/run/t4875.scala b/test/files/run/t4875.scala deleted file mode 100644 index c17211aede..0000000000 --- a/test/files/run/t4875.scala +++ /dev/null @@ -1,12 +0,0 @@ -import scala.tools.nsc.interpreter._ -import scala.tools.partest.ReplTest - -object Test extends ReplTest { - class M[@specialized T] { } - - def code = """ - |import scala.reflect.Code - |def codeOf[A](code: Code[A]) = code - |codeOf((x: Iterable[_]) => throw new Exception) - """.stripMargin -} diff --git a/test/files/run/t5272_1.check b/test/files/run/t5272_1.check new file mode 100644 index 0000000000..9f8d6f24e7 --- /dev/null +++ b/test/files/run/t5272_1.check @@ -0,0 +1 @@ +okay
\ No newline at end of file diff --git a/test/files/run/t5272_1.scala b/test/files/run/t5272_1.scala new file mode 100644 index 0000000000..3f44d05fb3 --- /dev/null +++ b/test/files/run/t5272_1.scala @@ -0,0 +1,17 @@ +import scala.tools.nsc.reporters._ +import scala.tools.nsc.Settings +import reflect.runtime.Mirror.ToolBox + +object Test extends App { + val code = scala.reflect.Code.lift{ + 2 match { + case 2 => println("okay") + case _ => println("not okay") + } + }; + + val reporter = new ConsoleReporter(new Settings) + val toolbox = new ToolBox(reporter) + val ttree = toolbox.typeCheck(code.tree) + toolbox.runExpr(ttree) +} diff --git a/test/files/run/t5272_2.check b/test/files/run/t5272_2.check new file mode 100644 index 0000000000..549f3f3af8 --- /dev/null +++ b/test/files/run/t5272_2.check @@ -0,0 +1 @@ +okay2
\ No newline at end of file diff --git a/test/files/run/t5272_2.scala b/test/files/run/t5272_2.scala new file mode 100644 index 0000000000..833ee65285 --- /dev/null +++ b/test/files/run/t5272_2.scala @@ -0,0 +1,16 @@ +import scala.tools.nsc.reporters._ +import scala.tools.nsc.Settings +import reflect.runtime.Mirror.ToolBox + +object Test extends App { + val code = scala.reflect.Code.lift{ + 2 match { + case x => println("okay" + x) + } + }; + + val reporter = new ConsoleReporter(new Settings) + val toolbox = new ToolBox(reporter) + val ttree = toolbox.typeCheck(code.tree) + toolbox.runExpr(ttree) +} diff --git a/test/files/run/t5334_1.check b/test/files/run/t5334_1.check new file mode 100644 index 0000000000..e09aedaede --- /dev/null +++ b/test/files/run/t5334_1.check @@ -0,0 +1,2 @@ +C +C
\ No newline at end of file diff --git a/test/files/run/t5334_1.scala b/test/files/run/t5334_1.scala new file mode 100644 index 0000000000..7acf282bb8 --- /dev/null +++ b/test/files/run/t5334_1.scala @@ -0,0 +1,16 @@ +import scala.tools.nsc.reporters._ +import scala.tools.nsc.Settings +import reflect.runtime.Mirror.ToolBox + +object Test extends App { + val code = scala.reflect.Code.lift{ + class C { override def toString = "C" } + new C + }; + + val reporter = new ConsoleReporter(new Settings) + val toolbox = new ToolBox(reporter) + val ttree = toolbox.typeCheck(code.tree) + println(ttree.tpe) + println(toolbox.runExpr(ttree)) +} diff --git a/test/files/run/t5334_2.check b/test/files/run/t5334_2.check new file mode 100644 index 0000000000..2ae76754c0 --- /dev/null +++ b/test/files/run/t5334_2.check @@ -0,0 +1,2 @@ +List[(C, C)] +List((C,C))
\ No newline at end of file diff --git a/test/files/run/t5334_2.scala b/test/files/run/t5334_2.scala new file mode 100644 index 0000000000..26f0778400 --- /dev/null +++ b/test/files/run/t5334_2.scala @@ -0,0 +1,16 @@ +import scala.tools.nsc.reporters._ +import scala.tools.nsc.Settings +import reflect.runtime.Mirror.ToolBox + +object Test extends App { + val code = scala.reflect.Code.lift{ + class C { override def toString() = "C" } + List((new C, new C)) + }; + + val reporter = new ConsoleReporter(new Settings) + val toolbox = new ToolBox(reporter) + val ttree = toolbox.typeCheck(code.tree) + println(ttree.tpe) + println(toolbox.runExpr(ttree)) +} diff --git a/test/files/run/t5423.scala b/test/files/run/t5423.scala index 2139773ff1..fc507c417b 100644 --- a/test/files/run/t5423.scala +++ b/test/files/run/t5423.scala @@ -6,7 +6,7 @@ import scala.reflect.Code final class table extends StaticAnnotation @table class A -object Test extends App{ +object Test extends App { val s = classToSymbol(classOf[A]) - println(s.getAnnotations) + println(s.annotations) } diff --git a/test/files/scalacheck/Ctrie.scala b/test/files/scalacheck/Ctrie.scala new file mode 100644 index 0000000000..2950937278 --- /dev/null +++ b/test/files/scalacheck/Ctrie.scala @@ -0,0 +1,199 @@ + + + +import org.scalacheck._ +import Prop._ +import org.scalacheck.Gen._ +import collection._ +import collection.mutable.Ctrie + + + +case class Wrap(i: Int) { + override def hashCode = i // * 0x9e3775cd +} + + +/** A check mainly oriented towards checking snapshot correctness. + */ +object Test extends Properties("Ctrie") { + + /* generators */ + + val sizes = choose(0, 200000) + + val threadCounts = choose(2, 16) + + val threadCountsAndSizes = for { + p <- threadCounts + sz <- sizes + } yield (p, sz); + + + /* helpers */ + + def inParallel[T](totalThreads: Int)(body: Int => T): Seq[T] = { + val threads = for (idx <- 0 until totalThreads) yield new Thread { + setName("ParThread-" + idx) + private var res: T = _ + override def run() { + res = body(idx) + } + def result = { + this.join() + res + } + } + + threads foreach (_.start()) + threads map (_.result) + } + + def spawn[T](body: =>T): { def get: T } = { + val t = new Thread { + setName("SpawnThread") + private var res: T = _ + override def run() { + res = body + } + def result = res + } + t.start() + new { + def get: T = { + t.join() + t.result + } + } + } + + def elementRange(threadIdx: Int, totalThreads: Int, totalElems: Int): Range = { + val sz = totalElems + val idx = threadIdx + val p = totalThreads + val start = (sz / p) * idx + math.min(idx, sz % p) + val elems = (sz / p) + (if (idx < sz % p) 1 else 0) + val end = start + elems + (start until end) + } + + def hasGrown[K, V](last: Map[K, V], current: Map[K, V]) = { + (last.size <= current.size) && { + last forall { + case (k, v) => current.get(k) == Some(v) + } + } + } + + object err { + var buffer = new StringBuilder + def println(a: AnyRef) = buffer.append(a.toString).append("\n") + def clear() = buffer.clear() + def flush() = { + Console.out.println(buffer) + clear() + } + } + + + /* properties */ + + property("concurrent growing snapshots") = forAll(threadCounts, sizes) { + (numThreads, numElems) => + val p = 3 //numThreads + val sz = 102 //numElems + val ct = new Ctrie[Wrap, Int] + + // checker + val checker = spawn { + def check(last: Map[Wrap, Int], iterationsLeft: Int): Boolean = { + val current = ct.readOnlySnapshot() + if (!hasGrown(last, current)) false + else if (current.size >= sz) true + else if (iterationsLeft < 0) false + else check(current, iterationsLeft - 1) + } + check(ct.readOnlySnapshot(), 500) + } + + // fillers + inParallel(p) { + idx => + elementRange(idx, p, sz) foreach (i => ct.update(Wrap(i), i)) + } + + // wait for checker to finish + val growing = true//checker.get + + val ok = growing && ((0 until sz) forall { + case i => ct.get(Wrap(i)) == Some(i) + }) + + ok + } + + property("update") = forAll(sizes) { + (n: Int) => + val ct = new Ctrie[Int, Int] + for (i <- 0 until n) ct(i) = i + (0 until n) forall { + case i => ct(i) == i + } + } + + property("concurrent update") = forAll(threadCountsAndSizes) { + case (p, sz) => + val ct = new Ctrie[Wrap, Int] + + inParallel(p) { + idx => + for (i <- elementRange(idx, p, sz)) ct(Wrap(i)) = i + } + + (0 until sz) forall { + case i => ct(Wrap(i)) == i + } + } + + + property("concurrent remove") = forAll(threadCounts, sizes) { + (p, sz) => + val ct = new Ctrie[Wrap, Int] + for (i <- 0 until sz) ct(Wrap(i)) = i + + inParallel(p) { + idx => + for (i <- elementRange(idx, p, sz)) ct.remove(Wrap(i)) + } + + (0 until sz) forall { + case i => ct.get(Wrap(i)) == None + } + } + + + property("concurrent putIfAbsent") = forAll(threadCounts, sizes) { + (p, sz) => + val ct = new Ctrie[Wrap, Int] + + val results = inParallel(p) { + idx => + elementRange(idx, p, sz) find (i => ct.putIfAbsent(Wrap(i), i) != None) + } + + (results forall (_ == None)) && ((0 until sz) forall { + case i => ct.get(Wrap(i)) == Some(i) + }) + } + +} + + + + + + + + + + diff --git a/test/files/scalacheck/avl.scala b/test/files/scalacheck/avl.scala index 51fb1fe8c3..af79ad49e3 100644 --- a/test/files/scalacheck/avl.scala +++ b/test/files/scalacheck/avl.scala @@ -47,21 +47,21 @@ package scala.collection.mutable { } } - def genInput: Gen[(Int, List[AVLTree[Int]])] = for { - size <- Gen.choose(20, 25) - elements <- Gen.listOfN(size, Gen.choose(0, 1000)) - selected <- Gen.choose(0, 1000) + def genInput: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { + size <- org.scalacheck.Gen.choose(20, 25) + elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) + selected <- org.scalacheck.Gen.choose(0, 1000) } yield { // selected mustn't be in elements already val list = makeAllBalancedTree(elements.sorted.distinct.map(_*2)) (selected*2+1, list) } - def genInputDelete: Gen[(Int, List[AVLTree[Int]])] = for { - size <- Gen.choose(20, 25) - elements <- Gen.listOfN(size, Gen.choose(0, 1000)) + def genInputDelete: org.scalacheck.Gen[(Int, List[AVLTree[Int]])] = for { + size <- org.scalacheck.Gen.choose(20, 25) + elements <- org.scalacheck.Gen.listOfN(size, org.scalacheck.Gen.choose(0, 1000)) e = elements.sorted.distinct - selected <- Gen.choose(0, e.size-1) + selected <- org.scalacheck.Gen.choose(0, e.size-1) } yield { // selected must be in elements already val list = makeAllBalancedTree(e) @@ -111,4 +111,4 @@ package scala.collection.mutable { object Test extends Properties("AVL") { include(scala.collection.mutable.TestInsert) include(scala.collection.mutable.TestRemove) -}
\ No newline at end of file +} diff --git a/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala new file mode 100644 index 0000000000..d1924f0ada --- /dev/null +++ b/test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala @@ -0,0 +1,98 @@ +package scala.collection.parallel +package mutable + + + +import org.scalacheck._ +import org.scalacheck.Gen +import org.scalacheck.Gen._ +import org.scalacheck.Prop._ +import org.scalacheck.Properties +import org.scalacheck.Arbitrary._ + +import scala.collection._ +import scala.collection.parallel.ops._ + + + +abstract class ParallelCtrieCheck[K, V](tp: String) extends ParallelMapCheck[K, V]("mutable.ParCtrie[" + tp + "]") { + // ForkJoinTasks.defaultForkJoinPool.setMaximumPoolSize(Runtime.getRuntime.availableProcessors * 2) + // ForkJoinTasks.defaultForkJoinPool.setParallelism(Runtime.getRuntime.availableProcessors * 2) + + type CollType = ParCtrie[K, V] + + def isCheckingViews = false + + def hasStrictOrder = false + + def ofSize(vals: Seq[Gen[(K, V)]], sz: Int) = { + val ct = new mutable.Ctrie[K, V] + val gen = vals(rnd.nextInt(vals.size)) + for (i <- 0 until sz) ct += sample(gen) + ct + } + + def fromTraversable(t: Traversable[(K, V)]) = { + val pct = new ParCtrie[K, V] + var i = 0 + for (kv <- t.toList) { + pct += kv + i += 1 + } + pct + } + +} + + +object IntIntParallelCtrieCheck extends ParallelCtrieCheck[Int, Int]("Int, Int") +with PairOperators[Int, Int] +with PairValues[Int, Int] +{ + def intvalues = new IntValues {} + def kvalues = intvalues.values + def vvalues = intvalues.values + + val intoperators = new IntOperators {} + def voperators = intoperators + def koperators = intoperators + + override def printDataStructureDebugInfo(ds: AnyRef) = ds match { + case pm: ParCtrie[k, v] => + println("Mutable parallel ctrie") + case _ => + println("could not match data structure type: " + ds.getClass) + } + + override def checkDataStructureInvariants(orig: Traversable[(Int, Int)], ds: AnyRef) = ds match { + // case pm: ParHashMap[k, v] if 1 == 0 => // disabled this to make tests faster + // val invs = pm.brokenInvariants + + // val containsall = (for ((k, v) <- orig) yield { + // if (pm.asInstanceOf[ParHashMap[Int, Int]].get(k) == Some(v)) true + // else { + // println("Does not contain original element: " + (k, v)) + // false + // } + // }).foldLeft(true)(_ && _) + + + // if (invs.isEmpty) containsall + // else { + // println("Invariants broken:\n" + invs.mkString("\n")) + // false + // } + case _ => true + } + +} + + + + + + + + + + diff --git a/test/files/scalacheck/parallel-collections/pc.scala b/test/files/scalacheck/parallel-collections/pc.scala index cc0382303a..8a0dba3c25 100644 --- a/test/files/scalacheck/parallel-collections/pc.scala +++ b/test/files/scalacheck/parallel-collections/pc.scala @@ -25,6 +25,9 @@ class ParCollProperties extends Properties("Parallel collections") { // parallel mutable hash maps (tables) include(mutable.IntIntParallelHashMapCheck) + // parallel ctrie + include(mutable.IntIntParallelCtrieCheck) + // parallel mutable hash sets (tables) include(mutable.IntParallelHashSetCheck) |