diff options
Diffstat (limited to 'test/files/scalacheck')
-rw-r--r-- | test/files/scalacheck/Ctrie.scala | 199 | ||||
-rw-r--r-- | test/files/scalacheck/avl.scala | 114 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala | 98 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala | 30 | ||||
-rw-r--r-- | test/files/scalacheck/parallel-collections/pc.scala | 3 | ||||
-rw-r--r-- | test/files/scalacheck/si4147.scala | 67 |
6 files changed, 496 insertions, 15 deletions
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 new file mode 100644 index 0000000000..af79ad49e3 --- /dev/null +++ b/test/files/scalacheck/avl.scala @@ -0,0 +1,114 @@ +import org.scalacheck.Gen +import org.scalacheck.Prop.forAll +import org.scalacheck.Properties + +import util.logging.ConsoleLogger + +package scala.collection.mutable { + + /** + * Property of an AVL Tree : Any node of the tree has a balance value beetween in [-1; 1] + */ + abstract class AVLTreeTest(name: String) extends Properties(name) with ConsoleLogger { + + def `2^`(n: Int) = (1 to n).fold(1)((a, b) => b*2) + + def capacityMax(depth: Int): Int = `2^`(depth+1) - 1 + + def minDepthForCapacity(x: Int): Int = { + var depth = 0 + while(capacityMax(depth) < x) + depth += 1 + depth + } + + def numberOfElementsInLeftSubTree(n: Int): collection.immutable.IndexedSeq[Int] = { + val mid = n/2 + n%2 + ((1 until mid) + .filter { i => math.abs(minDepthForCapacity(i) - minDepthForCapacity(n-i)) < 2 } + .flatMap { i => Seq(i, n-(i+1)) }).toIndexedSeq.distinct + } + + def makeAllBalancedTree[A](elements: List[A]): List[AVLTree[A]] = elements match { + case Nil => Leaf::Nil + case first::Nil => Node(first, Leaf, Leaf)::Nil + case first::second::Nil => Node(second, Node(first, Leaf, Leaf), Leaf)::Node(first, Leaf, Node(second, Leaf, Leaf))::Nil + case first::second::third::Nil => Node(second, Node(first, Leaf, Leaf), Node(third, Leaf, Leaf))::Nil + case _ => { + val combinations = for { + left <- numberOfElementsInLeftSubTree(elements.size) + root = elements(left) + right = elements.size - (left + 1) + } yield (root, left, right) + (combinations.flatMap(triple => for { + l <- makeAllBalancedTree(elements.take(triple._2)) + r <- makeAllBalancedTree(elements.takeRight(triple._3)) + } yield Node(triple._1, l, r))).toList + } + } + + 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: 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 <- org.scalacheck.Gen.choose(0, e.size-1) + } yield { + // selected must be in elements already + val list = makeAllBalancedTree(e) + (e(selected), list) + } + } + + trait AVLInvariants { + self: AVLTreeTest => + + def isBalanced[A](t: AVLTree[A]): Boolean = t match { + case node: Node[A] => math.abs(node.balance) < 2 && (List(node.left, node.right) forall isBalanced) + case Leaf => true + } + + def setup(invariant: AVLTree[Int] => Boolean) = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => invariant(tree)).fold(true)((a, b) => a && b) + } + + property("Every tree is initially balanced.") = setup(isBalanced) + } + + object TestInsert extends AVLTreeTest("Insert") with AVLInvariants { + import math.Ordering.Int + property("`insert` creates a new tree containing the given element. The tree remains balanced.") = forAll(genInput) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.insert(selected, Int) + modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } + + object TestRemove extends AVLTreeTest("Remove") with AVLInvariants { + import math.Ordering.Int + property("`remove` creates a new tree without the given element. The tree remains balanced.") = forAll(genInputDelete) { + case (selected: Int, trees: List[AVLTree[Int]]) => + trees.map(tree => { + val modifiedTree = tree.remove(selected, Int) + tree.contains(selected, Int) && !modifiedTree.contains(selected, Int) && isBalanced(modifiedTree) + }).fold(true)((a, b) => a && b) + } + } +} + +object Test extends Properties("AVL") { + include(scala.collection.mutable.TestInsert) + include(scala.collection.mutable.TestRemove) +} 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/ParallelIterableCheck.scala b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala index fbacb9f45c..8273e302a2 100644 --- a/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala +++ b/test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala @@ -414,21 +414,21 @@ abstract class ParallelIterableCheck[T](collName: String) extends Properties(col }).reduceLeft(_ && _) } - // property("groupBy must be equal") = forAll(collectionPairs) { - // case (t, coll) => - // (for ((f, ind) <- groupByFunctions.zipWithIndex) yield { - // val tgroup = t.groupBy(f) - // val cgroup = coll.groupBy(f) - // if (tgroup != cgroup || cgroup != tgroup) { - // println("from: " + t) - // println("and: " + coll) - // println("groups are: ") - // println(tgroup) - // println(cgroup) - // } - // ("operator " + ind) |: tgroup == cgroup && cgroup == tgroup - // }).reduceLeft(_ && _) - // } + property("groupBy must be equal") = forAll(collectionPairs) { + case (t, coll) => + (for ((f, ind) <- groupByFunctions.zipWithIndex) yield { + val tgroup = t.groupBy(f) + val cgroup = coll.groupBy(f) + if (tgroup != cgroup || cgroup != tgroup) { + println("from: " + t) + println("and: " + coll) + println("groups are: ") + println(tgroup) + println(cgroup) + } + ("operator " + ind) |: tgroup == cgroup && cgroup == tgroup + }).reduceLeft(_ && _) + } } 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) diff --git a/test/files/scalacheck/si4147.scala b/test/files/scalacheck/si4147.scala new file mode 100644 index 0000000000..1453440ef1 --- /dev/null +++ b/test/files/scalacheck/si4147.scala @@ -0,0 +1,67 @@ +import org.scalacheck.Prop.forAll +import org.scalacheck.Properties +import org.scalacheck.ConsoleReporter.testStatsEx +import org.scalacheck.Gen +import org.scalacheck.ConsoleReporter + + +import collection.mutable + + +object Test extends Properties("Mutable TreeSet") { + + val generator = Gen.listOfN(1000, Gen.chooseNum(0, 1000)) + + val denseGenerator = Gen.listOfN(1000, Gen.chooseNum(0, 200)) + + property("Insertion doesn't allow duplicates values.") = forAll(generator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + t == s.toSet + } + } + + property("Verification of size method validity") = forAll(generator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + for (a <- s) { + t -= a + } + t.size == 0 + } + } + + property("All inserted elements are removed") = forAll(generator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + for (a <- s) { + t -= a + } + t == Set() + } + } + + property("Elements are sorted.") = forAll(generator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + t.toList == s.distinct.sorted + } + } + + property("Implicit CanBuildFrom resolution succeeds as well as the \"same-result-type\" principle.") = + forAll(generator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + val t2 = t.map(_ * 2) + t2.isInstanceOf[collection.mutable.TreeSet[Int]] + } + } + + property("A view doesn't expose off bounds elements") = forAll(denseGenerator) { (s: List[Int]) => + { + val t = mutable.TreeSet[Int](s: _*) + val view = t.rangeImpl(Some(50), Some(150)) + view.filter(_ < 50) == Set[Int]() && view.filter(_ >= 150) == Set[Int]() + } + } +} |