Про ScalaCheck. Генератори (Частина 2)

Частина 2. Генератори
вступної статті серії ви, сподіваюся, вже встигли познайомитися з генераторами. У цьому туториале ми закріпимо отримані знання, навчимося писати власні (у тому числі рекурсивні) генератори. Хоча він і присвячений генераторам, про властивості ми теж не забудемо. Більше того, ми будемо їх активно використовувати, демонструючи всю міць механізму генераторів. Розглянемо механізм передумов (preconditions). Можливо, більш логічним було б присвятити властивостями другу статтю серії і, можливо, це стало б правильним рішенням. Однак, за моїми особистими спостереженнями, найбільші труднощі викликають саме генератори. Властивості ми розглянемо в наступній статті.
Структура циклу
  • Введення
  • Генератори
  • Властивості
  • Мінімізація
  • Інтеграція та налаштування
Генератори
Метод
forAll
з об'єкта
Prop
використовує дані, сгенеровані довільним чином. Це можуть бути як прості типи даних, так і контейнерні (compound). У ScalaCheck будь генератор є спадкоємцем Gen:
sealed abstract class Gen[+T] {
def apply(prms: Gen.Params): Option[T]
...
}

Клас є параметричним за типом генерується значення. Відповідно, для рядків ми будемо мати
Gen[String]
, а для горезвісних
Person
Gen[Person]
. Також ви можете використовувати метод
arbitrary
з об'єкта
Arbitrary
за умови наявності в області видимості необхідних имплиситов.
Додаємо підтримку implicit'ів до наших генераторів
Раз вже ми заговорили про имплиситах, давайте розберемося, як зробити
arbitrary

для вашого типу. Для початку, нам потрібен сам тип:
sealed trait LED
case object Red LED extends
case object Green LED extends
case object Blue extends LED

Тепер створимо генератор для наших діодів:
val ledGenerator: Gen[LED] = Gen.oneOf(Red, Green, Blue)

А тепер створимо
implicit
примірник
Arbitrary
з наявного у нас генератора:
implicit val arbitraryLed: Arbitrary[LED] = Arbitrary(ledGenerator)

Arbitrary.arbitrary[LED].sample
// Some(Green)

Тепер, маючи світлодіоди в нашій області видимості, ми можемо перевірити деякі властивості:
val ledProp = forAll { diode: LED =>
// тестуємо нещасні діоди
}

Для ряду примітивних типів, а так само контейнерів із стандартної бібліотеки, неявні перетворення вже визначені всередині об'єкта
Arbitrary
:
import org.scalacheck.Arbitrary.arbitrary

val arbitraryString = arbitrary[String]
val arbitraryInteger = arbitrary[Int]

Gen.resultOf
може значно допомогти у цій справі. Ця функція приймає case-клас, для параметрів конструктора якого вже визначені
arbitrary
значення:
case class Coord(x: Double, y: Double)

// Створюємо генератор за допомогою resultOf.
val genCoord = Gen.resultOf(Coord)

// Поміщаємо його в Arbitrary.
implicit val arbitraryCoord = Arbitrary(genCoord)

// А тепер перевіряємо все що нам прийде в голову.
val prop = Prop.forAll { coord: Coord =>
//...
}

Метод
sample

На жаль, для екземплярів класу
Gen
не визначено метод
toString
, проте є метод, який краще і зручніше. Вам навіть доведеться дуже часто їм користуватися при написанні генераторів. Це метод
Gen.sample
. Він повертає приклад згенерованого значення всередині
Option
:
// ScalaCheck може повертати дуже довгі рядки, тому відріжемо
// перші 10 символів.
Arbitrary.arbitrary[String].sample map (_ take 10)

// А ось і кінцевий результат.
// Some(Q冋执龭轙⮻拍箘㖕)
Arbitrary.arbitrary[Double].sample
// Some(-5.180668081211655E245)

Трансформації
Як вже було розказано в попередній частині, до генераторів так само можна застосовувати метод
map
. Проілюструємо це наступним прикладом:
val octDigitStr = choose(0, 7) map (_.toString)

octDigitStr.sample
// Some(3)

octDigitStr.sample
// Some(5)

Фільтрація
Для генераторів також існує метод
filter
, хоча, насправді, це лише псевдонім для виклику методу
suchThat
:
val evenOct = octDigit.filter(_ % 2 == 0)

evenOct.sample
// None

// Не пощастило, спробуємо ще раз:
evenOct.sample
// None

// Ось досада, а може бути зараз?
evenOct.sample
// Some(2)

Приклад вище демонструє, чому користуватися
filter
або
suchThat
не варто. Новий генератор просто відкидає значення, які не проходять фільтр. Це сильно уповільнює процес тестування.
Передумови діють аналогічно фільтрів.
Передумови
Подаються в логіці операцією імплікації передумови в ScalaCheck — це методи, використовувані усередині властивостей. Вони дозволяють обмежити вхідні дані. Записуються оператором
==>
. Для того, щоб скористатися передумовами, вам необхідно додати в область видимості
Prop.propBoolean
. Отже, давайте перевіримо твердження про те, що для будь-якого парного числа остання цифра також буде парним числом:
import org.scalacheck.Prop.{forAll, propBoolean}

def isEven(number: Int) = number % 2 == 0

// Отримуємо останню цифру числа.
def lastChar(number: Int) =
number.toString.last.toInt

// Фільтрування.
val p2 = forAll(arbitrary[Int] suchThat isEven) { number =>
isEven(lastChar(number))
}

// Використання передумови.
val p1 = forAll(arbitrary[Int]) { number =>
isEven(number) ==> isEven(lastChar(number))
}

Щоб запустити властивість, ми можемо скористатися функцією
check
:
// перевіримо наше перше властивість
p1.check
// + OK, passed 100 tests.

// та друге
p2.check
// + OK, passed 100 tests.

Чим жорсткіше фільтр, тим більше значень буде проигнорированно. Це може бути критичним для малого набору значень або значень, які знаходяться дуже далеко один отдруга. Наприклад, простих чисел в діапазоні Int. Від такої затії ScalaCheck легко може втомитися і здатися вам в полон:
scala> p1.check
! Gave up after only 1 passed tests. 100 tests were discarded

Ви не помітите це на прикладі з парними числами, а на прикладі з простими — легко. Також слід знати, що:
Фільтр для парних чисел можна реалізувати по-різному. Наприклад, можна брати
будь-яке ціле число і просто множити його на 2. У випадку з простими числами
набагато простіше буде порахувати їх заздалегідь, скориставшись, наприклад,
решетом Ератосфена, а потім просунути список
обчислених значень всередину
Gen.oneOf
, який ми розглянемо далі в цій
статті.
Якщо ви комбінуєте генератори, використовують
suchThat
, у вас також можуть виникнути проблеми. У таких випадках вам слід скористатися методом
retryUtil
. На відміну від
suchThat
, він змушує ScalaCheck працювати старанніше, що може закінчитися нескінченним циклом. Викликається
retrtyUtil
аналогічно
fiter
або
suchThat
:
arbitrary[Int] retryUntil isEven

Ви також можете помітити, що методи
collect
та
flatten
, так само як і
fromOption
, оголошені
Deprecated
. Це зроблено, щоб у вас було менше спокуси плодити порожні генератори.
Створюємо свій генератор
Як вже було відмічено раніше, ви можете створювати свої власні генератори, комбінуючи вже існуючі за допомогою for comprehension:
val coordGen =
for { i <- arbitrary[Int]; j <- arbitrary[Int] } yield (i, j)

coordGen.sample
// Option[(Int, Int)] = Some((45,60))

coordGen.sample
// Option[(Int, Int)] = Some((29, 37))

Ви можете оголосити генератори для будь-якої структури даних. Простий випадок використання ADT:
sealed trait LightColor
case object Red extends LightColor
case object Orange extends LightColor
case object Green extends LightColor
case object FlashingGreen extends LightColor
case object Extinct extends LightColor

val colorGen = Gen.oneOf(Red, Orange, Green, Extinct)

Якщо ускладнювати собі життя, так грунтовно:
// Якщо мова тут буде йти про колір, то тільки про колір світла.
type Color = LightColor

object PedestrianTrafficLight {
sealed class State(_1: Color, _2: Color)
case object Stop extends State(Red, Extinct)
case object Move extends State(Extinct, Green)
case object FinishMove extends State(Extinct, FlashingGreen)
def states: Seq[State] = Seq(Move, FinishMove, Stop)
}

object VehicularTrafficLight {
sealed class State(_1: Color, _2: Color, _3: Color)
case object Stop extends State(Red, Extinct, Extinct)
case object Ready extends State(Red, Orange, Extinct)
case object Move extends State(Extinct, Extinct, Green)
case object Warn extends State(Red, Orange, Extinct)
case object FinishMove extends State(Extinct, Extinct, FlashingGreen)
def states: Seq[State] = Seq(Stop, Ready, Move, Warn, FinishMove)
}

sealed trait TrafficLight

case class PedestrianTrafficLight(state: PedestrianTrafficLight.State)
extends TrafficLight

case class VehicularTrafficLight(state: VehicularTrafficLight.State)
extends TrafficLight

Оголосимо наші генератори:
import Gen._

// Набір станів для пішохідного світлофора
val pedestrianTrafficLightStateGen =
Gen.oneOf(PedestrianTrafficLight.states)

// Набір станів для транспортного світлофора
val vehicularTrafficLightStateGen =
Gen.oneOf(VehicularTrafficLight.states)

А тепер згенеруємо кортеж з пішохідного і транспортного світлофорів. Є тільки одне але: стану світлофорів не повинні бути взаємовиключними. Для початку визначимося з умовою, при якому пішохід може здійснити маневр. Так як ми створюємо генератор шляхом композиції, ми використовуємо
retryUntil
замість
suchThat
:
val pedestrianCanGo = pedestrianTrafficLightStateGen.retryUntil { state =>
state != PedestrianTrafficLight.Stop
}

Тепер згенеруємо стан автомобільного світлофора і, відштовхуючись від нього, визначимо допустимий стан для пішохідного, а потім об'єднаємо їх в список. Отриманий нами генератор буде мати наступний тип:
Gen[(VehicularTrafficLight.State, PedestrianTrafficLight.State)]
.
val states = vehicularTrafficLightStateGen flatMap {
case vehState @ VehicularTrafficLight.Stop =>
pedestrianCanGo map (pedState => (vehState, pedState))
case pedestrianCanNotGo =>
(pedestrianCanNotGo, PedestrianTrafficLight.Stop)
}

Тепер відобразимо стану світлофорів в самі об'єкти:
val trafficLightPair = states map { case (v, p) =>
(VehicularTrafficLight(v), PedestrianTrafficLight(p))
}

Перевіримо результати? Я отримав:
(VehicularTrafficLight(FinishMove),PedestrianTrafficLight(Stop))

та
(VehicularTrafficLight(Move),PedestrianTrafficLight(Stop))

що цілком скидається на правду. Може бути, де-то я і помилився. Головним було продемонструвати сам механізм.
ScalaCheck також дозволяє вам генерувати рекурсивні структури даних,
однак легким і тривіальним цей процес назвати складно. Далі в цій
статті ми розглянемо рекурсивні генератори і проблеми, з якими ви
можете зіткнутися при їх використанні.
Генератори властивості
У більшості використаних раніше прикладів ScalaCheck самостійно підбирає відповідний примірник генератора і використовує його для обчислення властивості. Однак, не для того ми самі писали генератори, щоб ScalaCheck забирав з області видимості, що попало. Пам'ятаєте наші «сумісні» світлофори? Давайте вже куди-небудь їх приткнем:
import Prop.{forAll, propBoolean}

def isRed(trafficLight: VehicularTrafficLight) =
trafficLight.state == VehicularTrafficLight.Stop

def notRed(trafficLight: PedestrianTrafficLight) =
trafficLight.state != PedestrianTrafficLight.Stop

// Генератор передається в якості першого параметра для Prop.forAll
val canNotBothBeRed =
forAll(trafficLightPair) { case (vehicular, pedestrian) =>
isRed(vehicular) ==> notRed(pedestrian)
}

Перевіримо?
canNotBothBeRed.check

І переконаємося, що все добре:
+ OK, passed 100 tests.

Часто, одного генератора буває недостатньо, тоді ви можете використовувати кілька:
val p = forAll(Gen.posNum[Int], Gen.negNum[Int]) { (pos, neg) =>
neg < pos
}

Властивості як і генератори, можна вкладати один в одного, тому наведений вище приклад можна переписати так:
val p = forAll(Gen.posNum[Int]) { pos =>
forAll(Gen.negNum[Int]) { neg =>
neg < pos
}
}

Замість вкладених викликів
forAll
ви також можете зібрати кортеж із генераторів, які хочете використовувати. І не викликати
forAll
двічі.
Мітки на генераторах
Використання міток є гарною практикою. Це дозволяє поліпшити звіти про помилки та підвищити читаність коду, що використовує генератори. Для того, щоб додати тег, ви можете використовувати оператори
|:
та
:|
. Мітка може бути як рядком, так і символом. До генератора може бути додано декілька міток. Для ілюстрації візьмемо попередній приклад, тільки змінимо знак, зробивши властивість абсурдним:
// Оператори|:: | відрізняються тільки асоціативністю.
val p = forAll('positive |: Gen.posNum[Int]) { pos =>
forAll(Gen.negNum[Int] :| "negative numbers") { neg =>
neg > pos
}
}

Погодьтеся, стало краще?
! Falsified after 0 passed tests.
> positive: 0
> positive_ORIGINAL: 1
> negative numbers: 0

Генератори примітивів
Константи
Важко придумати щось простіше, ніж
Gen.const
. Він приймає будь-яке значення і дбайливо упаковує його в генератор. Будь-який об'єкт, що знаходиться у вдалому місці і в потрібний час, буде неявним чином приведений до
Gen
. Тому, швидше за все, в явному вигляді викликати цей метод вам не доведеться.
Умирашка
Всередині ScalaCheck використовується метод
Gen.fail
повертає нежиттєздатний генератор. При спробі викликати метод
sample
ви завжди отримаєте
None
. Швидше за все, на вашому шляху він не зустрінеться, а якщо і трапиться, вважайте, що з ним ви знайомі:
Gen.fail.sample
// Option[Nothing] = None


Ви можете використовувати
Gen.posNum
та
Gen.negNum
для генерації позитивних і негативних чисел відповідно:
import org.scalacheck.Gen
import org.scalacheck.Prop.forAll

val negative = Gen.negNum[Int]
val positive = Gen.posNum[Int]

val propCube = forAll (negative) { x =>
x * x * x < 0
}

Цікавим функціоналом володіє
Gen.chooseNum
: цей генератор породжує числа в заданому діапазоні (включно), з великою вагою для нуля (якщо він входить в діапазон), мінімального і максимального значення, а так само для представленого списку значень:
// Значення specials є vararg.
Gen.chooseNum(minT = 2, maxT = 10, specials = 9, 5)

Gen.choose
можна використовувати для генерації числових значень в межах заданого діапазону. Більш того, це той рідкісний тип генератора, який ніколи не провалюється. Його також можна використовувати стосовно до символів. До речі, про символьних генераторах...
Символи
Символьних генераторів в ScalaCheck існує безліч. Вам пропонується вибрати з наступних:
  • Gen.alphaUpperChar
  • Gen.alphaLowerChar
  • Gen.alphaChar
  • Gen.numChar
  • Gen.alphaNumChar
Тепер спробуємо згенерувати координати для гри в «Морський бій»:
val coord = for {
letter: Char <- Gen.alphaUpperChar
number: Char <- Gen.numChar
} yield s"$letter$number"

coord.sample
// Some(L1)

Завдяки for comprehension, ви можете генерувати будь-які агрегати: списки, кортежі, рядки. До речі про рядках...
Рядка
ви також можете легко породжувати.
Gen.alphaStr
генерує рядка тільки з алфавітних символів.
Gen.numStr
генерує числові рядки. Існує можливість окремо генерувати рядка з символів різного регістра:
Gen.alphaLowerStr
та
Gen.alphaUpperStr
якраз призначені для цих цілей.
Gen.idenifier
дає вам непустую рядок, яка завжди починається з алфавітного символи в нижньому регістрі, за яким слідують алфавітно-цифрові символи. Для деяких граматик це цілком собі ідентифікатор.
import org.scalacheck.Gen

val stringsGen = for {
key <- Gen.identifier
value <- Gen.numStr
} yield Bucket(key take 8, value take 2)

stringsGen.sample

// Some(Bucket(kinioQqg,60))


У Scalacheck можна генерувати і функції (примірники
Function0
:
() => T
). Для цього потрібно передати генератор, який відповідає за повернуте значення
Gen.function0
:
val f = Gen.function0(Arbitrary.arbitrary[Int]).sample
// Метод tostring любить функції, однак лямбду ми можемо споглядати якось так:
// some(org.scalacheck.gen$$$lambda$40/1418621776@4f7d0008)

Генератори контейнерів
Ви можете генерувати примірники стандартних колекцій, використовуючи
arbitrary
:
import Arbitrary.arbitrary

val listgen = arbitrary[List[Int]]
val optgen = arbitrary[Option[Int]]

Але цього часто буває недостатньо, тому ScalaCheck надає розширені інструменти для роботи з колекціями, а також їх генерації. Далі ми будемо опускати
Option
-и, які повертає метод
sample
, і будемо показувати вам значення відразу, щоб не водити зайве в оману.
<h3 id=«generiruem-option>Генеруємо Option
Якщо ви використовуєте
Gen.some
, то «дохід» вам гарантовано:
// Той рідкісний і щасливий випадок:
Gen.some("грошик")
// Some(гроші)

Гірше, коли у грошики з'являються додаткові ступені свободи:
// Загубилася.
Gen.option("грошик")
// None

Генеруємо списки й словники
Gen.listOf
породжує списки довільних довжин, а
Gen.listOfN
породжує списки заданої довжини.
// Константа 3 буде неявно приведена до Gen[Int].
Gen.listOf(3) map (_ take 5)
// List(3, 3, 3, 3, 3)

// Для отримання пятиэлементного списку.
Gen.listOfN(5, Gen.posNum[Double]) map (_ take 5)

Генератор
Gen.listOf
може повернути порожній список. Якщо вам гарантовано потрібен непорожній список, ви можете скористатися
Gen.nonEmptyListOf
. Для генерації словників, або відображень (
Map
), існують аналогічні методи:
Gen.mapOf
,
Gen.mapOfN
, а також
Gen.nonEmptyMapOf
. На відміну від методів для списку, генератори для словників вимагають, щоб їм передали генератор двухэлементного кортежу:
import Arbitrary._

val tupleGen = for {
i <- arbitrary[Short]
j <- arbitrary[Short]
} yield (i, j)

Gen.mapOfN(3, tupleGen) map (_ take 3)
// Map(10410 -> -7991, -19269 -> -18509, 0 -> -18730)

Породжуємо список елементів заданої множини
Gen.someOf
повертає вам
ArrayBuffer
з деякого набору елементів, що входять у заданий вами безліч, наприклад:
import org.scalacheck.Gen.someOf

val numbers = someOf(List(1, 2, 3, 4, 5)).sample
// Some(ArrayBuffer(5, 4, 3))

val leds = someOf(List(Red, Green, Blue)).sample
// Some(ArrayBuffer(Blue, Green))

Gen.pick
працює аналогічно
Gen.someOf
. Відмінність лише в тому, що
Gen.pick
дозволяє вам вказати необхідну кількість елементів:
import org.scalacheck.Gen.pick

val lettersGen =
Gen.pick(2, List('a', 'e', 'i', 'o', 't', 'n', 'm')).sample

// Some(ArrayBuffer(m, n))

Породжуємо послідовність
Gen.sequence
створює
ArrayList
на основі прийнятої послідовності значень. Якщо хоча б один з наданих генераторів впаде — вся послідовність впаде.
import Gen.{const, choose}

val ArrayListGen =
Gen.sequence(List(const('a'), const('b'), choose('c', 'd')))

// [a, b, d]

Генеруємо нескінченний потік
ScalaCheck підтримує можливість генерації нескінченних потоків:
val stream = Gen.infiniteStream(Gen.choose(0,1))

// візьмемо перші 8 елементів
stream.sample map (stream => stream.take(8).toList)
// Some(List(1, 0, 0, 0, 1, 1, 1, 0))

Генератор контейнерів
Перераховані вище методи для словників і списків, насправді, є приватними випадками використання
Gen.containerOf
і його співтоваришів:
containerOfN
і nonEmptyContainerOf`. Це найбільш узагальнена форма, яка дозволяє згенерувати більшість відомих нам колекцій. Давайте розглянемо наступні приклади:
import Arbitrary._

// Створимо колекцію «коротких» цілих чисел з трьох елементів.
val prettyShortSeq =
Gen.containerOfN[Seq, Short](3, arbitrary[Short])

// Vector(0, -24114, 32767)

// Завдання складніше: спорудимо мапу.
val genNonEmptyList =
Gen.nonEmptyContainerOf[Map[K, V], (K, V)] (oneOf("foo", "bar"))

Генератори, створені за допомогою
containerOf
, абстрагуються над типами, але не над пологами (kinds). Давайте подивимося на сигнатуру методу
containerOf
:
def containerOf[C[_],T](g: Gen[T])(implicit
evb: Buildable[T,C[T]], evt: C[T] => Traversable[T]
): Gen[C[T]] =

і на його реалізацію:
buildableOf[C[T],T](g)

Так що, якщо вам потрібно згенерувати список або щось, що може бути представлено як
* ⟶ *
,
containerOf
буде вам корисний. А якщо вам потрібно створити щось на зразок
* ⟶ * ⟶ *
(наприклад
Map
), доведеться використовувати ще більш абстрактний метод, який ми можемо підглянути в реалізації
mapOf
:
def mapOf[T,U](g: => Gen[(T,U)]) = buildableOf[Map[T,U],(T,U)](g)

Аналогічно методам
container
, існують методи
buildableOf
,
buildableOfN
та
nonEmptyBuildableOf
. Зазвичай Scalacheck сам вирішує, як побудувати передану йому в якості типу колекцію. Для цього він використовує неявний екземпляр типу
org.scalacheck.util.Buildable
. Такі екземпляри оголошені в ScalaCheck для всіх стандартних типів колекцій. Досить легко реалізувати свою колекцію і отримати підтримку
containerOf
, так само, як і екземпляри
Arbitrary
.
Генератори вищого порядку
Я думаю, вам, шановний читач, відомо, що представляють із себе функції вищого порядку. Генераторам теж властиво подібна поведінка: генератор може приймати інші генератори в якості аргументів, породжуючи цим інші генератори. Розглянуті нами раніше генератори контейнерів, за рідкісним винятком, також є генераторами вищого порядку.
Один з безлічі
Gen.oneOf
може приймати від двох до
N
генераторів, тим самим породжуючи новий генератор.
import Gen.{oneOf, const, choose}

// В даному випадку ми отримуємо Gen[T]
val dogies = oneOf("Lucy", "Max", "Daisy", "Barney")

// А тут ми передаємо генератори явним чином
val windows = oneOf(choose(1, 8), const(10))

oneOf
можна передати будь-спадкоємець
scala.collection.Seq
, наприклад, список.
Частотний генератор
Gen.frequency
приймає на вхід список кортежів. Кожен з яких складається з генератора і його імовірнісного ваги. На виході виходить новий генератор, який буде використовувати передані йому цілочисельні значення як імовірнісні ваги:
val russianLettersInText = Gen.frequency (
(9, 'про'),
(9, 'а'),
(8, 'е'),
(7, 'і'),
(6, 'н')
//.. залишилися літери
)

Ледачий генератор
Використання
Gen.lzy
дозволить відкласти генерацію до моменту, поки вона дійсно не потрібно. Він дуже зручний у композитних генераторах, а також при генерації рекурсивних структур даних, наприклад AST. У разі використання
Gen.lzy
, обчислення проводяться один раз.
Gen.delay
також відкладає обчислення, проте, вони будуть виконуватися щоразу.
Розмір генераторів
Gen.size
приймає своїм єдиним параметром лямбду, яка приймає своїм параметром ціле число. Це число є розміром, який ScalaCheck вказує під час виконання генератора.
Gen.resize
дозволяє встановити розмір для генератора там, де це необхідно. Проілюструємо це наступним прикладом:
def genNonEmptySeq[T](genElem: Gen[T]): Gen[Seq[T]] = Gen.sized { size =>
for {
listSize <- Gen.choose(1, size)
list <- Gen.containerOfN[Seq, T](listSize, genElem)
} yield list
}

val intVector = genNonEmptySeq(Arbitrary.arbitrary[Int])

val p = Prop.forAll(Gen.resize(5, intVector)) { list =>
list.length <= 5
}

Перевіримо:
p.check
// + OK, passed 100 tests.

Gen.resize
створює новий генератор на базі існуючого, але із зміненим розміром. Це корисно при створенні рекурсивних генераторів, а так само при створенні складних генераторів з простих за допомогою композиції.
Рекурсивні генератори
Мені досить часто доводиться працювати з рекурсивними структурами даних, а саме AST. Рекурсивні генератори викликають примірники себе всередині власного контексту. Викликати себе вони можуть як явно, так неявно, наприклад, вдаючись до допомоги інших генераторів. В якості прикладу давайте розглянемо бінарне дерево з цілочисельними вершинами:
trait IntTree
case class Leaf (value: Int) extends IntTree
case class Node (children: Seq[IntTree]) extends IntTree

Напишемо генератори для нашого дерева:
import org.scalacheck.Gen._

def treeGen: Gen[IntTree] =
oneOf(leafGen, nodeGen)

def leafGen: Gen[Leaf] =
arbitrary[Int] map (value => Leaf(value))

def nodeGen: Gen[Node] =
listOf(treeGen) map (children => Node(children))

і переконаємося, що вони рекурсивні:
treeGen.sample

Exception in thread "main" java.lang.StackOverflowError
at org.scalacheck.ArbitraryLowPriority$$anon$1.arbitrary(Arbitrary.scala:70)
at org.scalacheck.ArbitraryLowPriority.arbitrary(Arbitrary.scala:74)
at org.scalacheck.ArbitraryLowPriority.arbitrary$(Arbitrary.scala:74)
at org.scalacheck.Arbitrary$.arbitrary(Arbitrary.scala:61)

treeGen
ми одночасно запускаємо генератори для обох гілок. Це призводить до швидкого заповнення стека. Давайте спробуємо зробити наше дерево ледачим. Для цього перепишемо
treeGen
:
def treeGen: Gen[IntTree] =
lzy(oneOf(leafGen, nodeGen))

Запустимо:
treeGen.sample
// Some(Leaf(857998833))
// Some(Leaf(2147483647))
// Some(Leaf(489549235))

image
Exception in thread "main" java.lang.StackOverflowError
at org.scalacheck.rng.Seed.next(Seed.scala:17)
at org.scalacheck.rng.Seed.long(Seed.scala:39)
at org.scalacheck.Gen$Choose$.org$scalacheck$Gen$Choose$$chLng(Gen.scala:309)
at org.scalacheck.Gen$Choose$$anon$5.$anonfun$choose$1(Gen.scala:358)
at org.scalacheck.Gen$$anon$3.doApply(Gen.scala:254)
at org.scalacheck.Gen.$anonfun$map$1(Gen.scala:75)
at org.scalacheck.Gen$$anon$3.doApply(Gen.scala:254)
at org.scalacheck.Gen.$anonfun$flatMap$2(Gen.scala:80)
at org.scalacheck.Gen$R. flatMap(Gen.scala:242)
at org.scalacheck.Gen$R. flatMap$(Gen.scala:239)

Ми не генеруємо кілька нод відразу, але якщо генеруємо, то з нескінченною вкладеністю. Цю вкладеність нам слід зробити кінцевої. Використання
Gen.sized
та
Gen.resize
в тандемі зможе нам допомогти:
def nodeGen: Gen[Node] = sized { size =>
choose(0, size) flatMap { currSize =>
val nGen = resize(size / (currSize + 1), treeGen)
listOfN(currSize, nGen) map (child => Node(child))
}
}

У цій рядку:
val nGen = resize(size / (currSize + 1), treeGen)

ми створюємо новий генератор меншого розміру: розмір зменшується пропорційно до рівня вкладеності. Для певного N буде створено порожній генератор розміру 0, і ми не отримаємо переповнення стека. Розмір генератора слід зменшувати кожен раз, так як генератор не знає, на якому рівні вкладеності він знаходиться.
Ось ми і розібралися з рекурсивними генераторами. Приклад генерації AST для JSON ви можете знайти в блозі Eric Torreborre (творця specs2).
На цьому ми закінчимо наше знайомство з генераторами і перейдемо до властивостям. Детальніше про них буде розказано в наступній статті серії. До зустрічі!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.