Тестирование рекурсивной структуры данных

ScalaCheck: Полное руководство объясняет, как создавать генераторы для рекурсивных структур данных.

Во-первых, он определяет структуру данных:

trait Tree[T] {
    def size: Int
}
case class Leaf[T](item: T) extends Tree[T] {
    def size = 1
}
case class Node[T] (children: List[Tree[T]]) extends Tree[T] {
    def size = children.map(_.size).sum
}

Далее он показывает код Gen[Tree[A]]:

import org.scalacheck.Gen
import org.scalacheck.Gen.{oneOf, listOf, lzy}

def genTree[T](genT: Gen[T]): Gen[Tree[T]] = lzy {
    oneOf(genLeaf(genT), genNode(genT))
}

def genLeaf[T](genT: Gen[T]): Gen[Leaf[T]] =
    genT.map(Leaf(_))

def genNode[T](genT: Gen[T]): Gen[Node[T]] = for {
    children <listOf(
    genTree(genT))
} yield Node(children)

Книга демонстрирует, что для приведенного выше генератора вызов его может привести к StackOverflowError:

scala> genIntTree.sample
res0: Option[Tree[Int]] = Some(Leaf(2147483648))

scala> genIntTree.sample
res1: Option[Tree[Int]] = Some(Leaf(0))

scala> genIntTree.sample
java.lang.StackOverflowError
     at org.scalacheck.Gen$$anonfun$1$$anonfun$apply...

Учитывая следующую структуру данных MyList:

sealed abstract class MyList[+A]
case class Cons[+A](elem: A, rest: MyList[A]) extends MyList[A]
case object Empty                             extends MyList[Nothing]

И следующий генератор:

def genList[A](gen: Gen[A]): Gen[MyList[A]] =
    lzy { oneOf(genCons(gen), Gen.const(Empty)) } 

def genCons[A](gen: Gen[A]): Gen[MyList[A]] = for {
    list <- genList(gen)
    a    <- gen
} yield Cons(a, list)

Насколько я понимаю, использование Gen[Tree[A]] listOf отвечает за StackOverflowError.

Однако возможен ли StackOverflowError в генераторе кода Gen[MyList[A]]?

Я предполагаю, что это так, если достаточно genList возвращает достаточно Cons, но я не уверен.


scala property-based-testing scalacheck
person Kevin Meredith    schedule 15.03.2017    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Поскольку генератор является рекурсивным, он вполне может вызвать ошибку переполнения стека. Проблема в том, что oneOf() случайным образом выбирает путь для исследования; ваш генератор случайных чисел управляет расширением дерева.

Я обнаружил, что могу использовать взвешивание, чтобы получить деревья нужной глубины. Я считаю, что я играл с frequency(), чтобы заставить работать правильные веса.

person Bob Dalgleish    schedule 15.03.2017
comment
The issue is really that oneOf() is random in its selection of a path to explore. В приведенном выше примере Tree oneOf(gen1, gen2, ...) будет генерировать каждый gen* в списке varargs, не так ли? Если да, то что вызывает бесконечную рекурсию? - person Kevin Meredith; 16.03.2017

arrow_upward
0
arrow_downward

В вашем примере со списком вероятность переполнения стека очень мала — если вообще существует. Причина — и отличие от примера с деревом — заключается в том, что вы одновременно используете только один элемент.

Допустим, ваш стек взорвется после 1000 элементов, вероятность того, что это произойдет, составляет примерно 1/(2^1000), что является ОЧЕНЬ малым числом.

person johanneslink    schedule 16.03.2018