NPE on recursive tree generation

[Patrick Roemer]

If I modify the tree case class generation example from the user guide
to use a constant node value instead of the arbitrary int generator, I
get a NullPointerException.

val genNode = for {
left <- genTree
right <- genTree
} yield Node(left, right, 0)

! Exception raised on argument generation.
> Exception: java.lang.NullPointerException: null
org.scalacheck.Gen$$anonfun$oneOf$2.apply(Gen.scala:310)
org.scalacheck.Gen$$anonfun$oneOf$2.apply(Gen.scala:309)
[...]

What's going wrong there, and how can this be avoided in the general
case when I don't need such a "base value" at all, e.g. when
generating trees for boolean expressions?

Thanks and best regards,
Patrick

[Rickard Nilsson]

Hi Patrick,

Sorry for my late reply.

Den 2012-03-01 01:53:10 skrev Patrick Roemer
<quellkris...@gmail.com>:

What's going wrong is recursion, combined with val initialisation. When
genNode is initialised, the first statement (but not the rest of them) of
the for-expression will be evaluated. In your case, it will be the genTree
method. However, when genTree is evaluated, it will access genNode, which
at that point in time is null (since it is being initialised). So when you
later on try to use genNode, it will use this null generator, and a NPE
will occur.

The solution is to use org.scalacheck.Gen.lzy. This method will take a
generator as its only parameter and create a new generator of the same
type. The new generator is just a straightforward thin wrapper over the
provided generator. However, the lzy method will _not_ evaluate its
parameter until it really needs to get a value out of it. So, if you wrap
your first call to genTree with lzy, genTree will not be evaluated when
genNode is initialised.

This code would work just fine:

sealed abstract class Tree
case class Node(left: Tree, rigt: Tree, v: Int) extends Tree
case object Leaf extends Tree

import org.scalacheck._
import Gen._
import Arbitrary.arbitrary

val genLeaf = value(Leaf)

val genNode = for {
left <- lzy(genTree)

right <- genTree
} yield Node(left, right, 0)

def genTree: Gen[Tree] = oneOf(genLeaf, genNode)

Best regards,
Rickard Nilsson

[Patrick Roemer]

Responding to Rickard Nilsson:

>> val genNode = for {
>> left<- genTree
>> right<- genTree
>> } yield Node(left, right, 0)
>>
>> ! Exception raised on argument generation.
>>> Exception: java.lang.NullPointerException: null
>> org.scalacheck.Gen$$anonfun$oneOf$2.apply(Gen.scala:310)
>> org.scalacheck.Gen$$anonfun$oneOf$2.apply(Gen.scala:309)
>> [...]

[...]

> The solution is to use org.scalacheck.Gen.lzy.

[...]

Nice, works. Thanks for the help and the detailed explanation.

Best regards,
Patrick