summaryrefslogtreecommitdiff
path: root/test/files/scalacheck
diff options
context:
space:
mode:
Diffstat (limited to 'test/files/scalacheck')
-rw-r--r--test/files/scalacheck/Ctrie.scala199
-rw-r--r--test/files/scalacheck/avl.scala114
-rw-r--r--test/files/scalacheck/parallel-collections/ParallelCtrieCheck.scala98
-rw-r--r--test/files/scalacheck/parallel-collections/ParallelIterableCheck.scala30
-rw-r--r--test/files/scalacheck/parallel-collections/pc.scala3
-rw-r--r--test/files/scalacheck/si4147.scala67
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]()
+ }
+ }
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-12 07:25:44 +0000