Exhaustive testing and generating test cases according to an order

[Christian Urban]

Hi,

I like ScalaCheck, but have two questions. I am using the following generator code

val genLeaf = const(Leaf)

def genNode(level: Int) = for {

left <- genTree(level);

right <- genTree(level)

} yield Node(left, right)

def genTree(level: Int): Gen[Tree] =

if (level == 0) genLeaf

else oneOf(genLeaf, genNode(level - 1))

in order to generate simple binary trees up to a certain size/level. I needed to restrict the size, because otherwise

I received occasionally heap overflow exceptions in some samples. I assume the generation was called to "deeply".

Anyway, my questions are:

(1) Is there an easy way with ScalaCheck to generate all trees up to a certain size and then test

a property exhaustively on the generated trees?

(2) Even if I cannot generate all trees, is there a way to generate the random test cases according to an

order? For example generate trees according to the size, first small trees and then bigger trees. In this

case it would be guaranteed that no case is tested twice....in the code above it will test the Leaf-case many

times over. 

Thank you very much,

Christian

[Paul Ford]

You asked

(1) Is there a way generate all trees up to a certain size and then test a property exhaustively on the generated trees?

Not clear that a Generator is the right tool for this case. Generators can be viewed as infinite streams of random value. Exhaustive testing over a finite collection of known values is a different problem.

Presumably you can create some sort of exhaustive collection of values to test:

val allItems: Seq[T] = ...

And presumably you have a predicate the expresses the property being tested:

def p(item: T): Boolean = ...

Since ScalaCheck implicitly converts Boolean to Prop, you can then create a non-generator, exhaustive property as part of a ScalaCheck specification.

property("exhaustive") = allItems.forall(p)

Or if you want to report first failure

property("exhaustive reporting first failure") =
allItems.forall(item => { val result = p(item); if (!result) println(s"p failed for item $item"); result })

Or if you want to report all failures

property("exhaustive reporting all failures") =
allItems.map(item => { val result = p(item); if (!result) println(s"p failed for item $item"); result }).forall(_)

[Aaron S. Hawley]

(1) Is there an easy way with ScalaCheck to generate all trees up to a certain size and then test

a property exhaustively on the generated trees?

You can parameterize your generator with Gen.sized.  Conveniently, it can controlled from sbt with the testOnly -x option which defaults to 100.

  implicit val arbitraryTree = Arbitrary {

    Gen.sized(sz => genTree(sz))

  }

  property("size") = {

    Prop.forAll { t: Tree =>

      ...

    }

  }

You probably need to delay evaluation of the second argument to oneOf by using Gen.delay.

  def genTree(level: Int): Gen[Tree] =

    if (level == 0) genLeaf

    else oneOf(genLeaf, Gen.delay(genNode(level - 1)))

 

(2) Even if I cannot generate all trees, is there a way to generate the random test cases according to an

order? For example generate trees according to the size, first small trees and then bigger trees. In this

case it would be guaranteed that no case is tested twice....in the code above it will test the Leaf-case many

times over. 

There's no way to ensure the sizes be executed in order, but shrinking could help find the smallest failing case.

  implicit val shrinkTree: Shrink[Tree] = Shrink {

    case Node(left, right) => left #:: right #:: Stream.empty

    case Leaf => Stream.empty

  }

That way failures will give output like this:

[info] Falsified after 4 passed tests.

[info] > ARG_0: Node(Leaf,Leaf)

[info] > ARG_0_ORIGINAL: Node(Leaf,Node(Leaf,Leaf))

Hope that helps,

Aaron

[Abdhesh kumar]

The solution to this problem is to use Gen.lzy.

def genLeaf[A: Arbitrary]: Gen[Leaf[A]] = arbitrary[A].map(Leaf(_))

def genNode[A: Arbitrary]: Gen[Branch[A]] =
  for {
    left  <- genTree[A]
    right <- genTree[A]
  } yield Branch(left, right)

def genTree[A: Arbitrary]: Gen[Tree[A]] = Gen.oneOf(Gen.lzy(genLeaf[A]), Gen.lzy(genNode[A]))