この記事はRust Advent Calendar 2022 - Qiitaの12日目の記事です。
以前、Rustの実装力をあげるために、Property-based testingライブラリを作ったのですが、それについて説明する記事です。
Property-based testingとは
Property-based testingとは何か。詳しくは以下を参照してください。
Property-based tests make statements about the output of your code based on the input, and these statements are verified for many different possible inputs.
statementsはDSLのことかなと理解していますが、がくぞさんの説明のほうが簡潔なので以下の資料も参考にしてみてください。
テストデータをランダムに半自動生成して、その生成された全ての値について、満たすべき性質を満たしているかテストする
実装はしたくない使いたいという人はこっち
なんでもかんでも作ればいいってわけではないので、crates.ioから検索すると以下が代表的なクレートです。
実用ならこっちのほうがいいかも。
今回は実装力を上げるために車輪を再実装します。
実装したクレートについて
これです。
コード量はそんなにないので、さらっと読めるかも。
なにがうれしいのか
URIパーサを実装したときに、このクレートを使ってテストを書きました。以下のようなものです。
absolute_uri関数やuri関数がURIパーサーです。その関数をテストしています。
#[test] fn test_uri() -> Result<()> { let mut counter = 0; let uri_gen = uri_gen(); // テストデータを生成するジェネレータ // Property-based testingを行うPropを生成する let prop = prop::for_all_gen(uri_gen, move |s| { counter += 1; log::debug!("{:>03}, uri:string = {}", counter, s); let input = s.as_bytes(); let uri = (uri() - end()).parse(input).success().unwrap(); log::debug!("{:>03}, uri:object = {:?}", counter, uri); assert_eq!(uri.to_string(), s); true }); // Property-based testingの実行 prop::test_with_prop(prop, 5, TEST_COUNT, RNG::new()) }
テストではuri_gen関数が利用されます。これはURIの仕様に沿った文字列をランダムに生成するジェネレータ(Gen)です。uri_gen関数はscheme_gen関数やquery_gen関数やfragment_gen関数によって実装されます。Genどうしを合成したGenが作れます。
他のケースとして、IPv6アドレスのパーサーのテストとかもあります。これはまぁまぁ面倒で、こういうのは手でテストデータを作りたくないですね。
このような手法を使わずに自前でテストデータを作るのは骨が折れます。原始的なGenを使って高度なGenを組み上げるスタイルで、Property based testingのライブラリを使うと割と楽ができます。
Genの利用方法
もうちょっと実装よりのGenの利用方法について。
なんらかの方法でGenを生成(後述します)しfor_all_gen関数に第一引数に渡して、第二引数の関数でGenによって生成された値を使います(この関数の戻り値がfalseを返した場合はProperty based testingが失敗します)。第二引数で与えた関数はテスト実行時に指定されたテスト回数分 呼び出されます。すべてのテストにおいて戻り値がtrueでないとテストは成功と見なされません。
そして、for_all_gen関数はPropを生成するので、それをtest_with_prop関数を渡すとテストを実行します。テストの実行にはProp以外にテストサイズ、テスト数、乱数生成器を指定する必要があります。
let gen = ... let prop = for_all_gen(gen, move |input| { // テストコード true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
参考にした実装
この記事では詳しく説明しませんが、FP in Scalaのfirst-edtionのコードを参考にしました。
興味がある方は、日本語の書籍もあるので読んでみてください。
実装コード
主な実装を説明します。
for_all_gen関数とtest_with_prop関数
for_all_gen関数はGenを基にPropを生成する関数です。
pub fn for_all_gen<A, F>(g: Gen<A>, mut test: F) -> Prop where F: FnMut(A) -> bool + 'static, A: Clone + Debug + 'static, { Prop { run_f: Rc::new(RefCell::new(move |_, n, rng| { let success_counter = itertools::iterate(1, |&i| i + 1).into_iter(); random_stream(g.clone(), rng) .zip(success_counter) .take(n as usize) .map(|(test_value, success_count)| { if test(test_value.clone()) { PropResult::Passed { test_cases: n } } else { PropResult::Falsified { failure: format!("{:?}", test_value), successes: success_count, } } }) .find(move |e| e.is_falsified()) .unwrap_or(PropResult::Passed { test_cases: n }) })), } }
PropはFnMutを内包する構造体です。メソッドはそのFnMutを実行するrunがあります。他にもPropとPropを合成するandメソッドがあったりします。
pub struct Prop { run_f: Rc<RefCell<dyn FnMut(MaxSize, TestCases, RNG) -> PropResult>>, }
prop-check-rs/prop.rs at 4776da568ca35ca319e66c866d9670ce7c9fe40f · j5ik2o/prop-check-rs · GitHub
for_all_gen関数では、Genを実行できる無限ストリームを生成し、そのGenから生成された値を引数として渡し、指定されたテスト関数に指定回数分呼び出すPropを生成します。
test_with_propはテスト条件を指定して、Propを実行するだけです。
GenとGenを生成するファクトリGens
Genを実行する仕組みがわかったところで、Gen自体をどうやって生成するかについて簡単に説明します。
その前にGenの定義から。 GenはState型を内包する型です。RNGは純粋な乱数生成器です。
pub struct Gen<A> { sample: State<RNG, A>, }
State型はいわゆるStateモナドのような実装になっていて、Stateどうしを合成して新たなStateを生成することができます。そして、それを使うGenもGenどうしを合成可能です。
Gens#pure
GensはGenのファクトリメソッドが定義されています。
最も単純なメソッドはpure関数でしょう。何度呼び出してもpureの引数に与えた値しか返さないGenを生成できます。
let gen = Gens::pure(1); let prop = for_all_gen(gen, move |input| { input == 1 // inputは常に1 }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
やっていることは単純にrunされたときに実行される関数内で固定値を返すようにします。
pub fn pure<B>(value: B) -> Gen<B> where B: Clone + 'static, { Gen::<B>::new(State::value(value)) }
https://github.com/j5ik2o/prop-check-rs/blob/4776da568ca35ca319e66c866d9670ce7c9fe40f/src/gen.rs#L27
Gens#one_char
one_char関数は任意のcharを返します。他にもone_u8, one_u32, ...など型に応じたメソッドがあります。ジェネリック版のoneメソッドもあります。
let gen = Gens::one_char(); let prop = for_all_gen(gen, move |input| { println!("input = {}", input.to_string()); // 任意の文字 true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
prop-check-rs/rng.rs at 4776da568ca35ca319e66c866d9670ce7c9fe40f · j5ik2o/prop-check-rs · GitHub
やっていることは単純にrunされたときに実行される関数内でRNGから任意の値を取っているだけです。
Gens#list_of_n
このファクトリメソッドは任意の数値の配列を生成できるGenが欲しい場合に使えます。以下のようにすると、任意のu8を5個保持するVecを返すGenを生成できます。
let gen = Gens::list_of_n(5, Gens::one_u8()); let prop = for_all_gen(gen, move |input| { println!("input = {:?}", input); // 任意の文字の配列 true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
複数の、Gen#sampleを返す関数を保持するVecを素に作ったStateをGenに組み込むことで、複数の値を生成して返せるようになります。
pub fn list_of_n<B>(n: usize, gen: Gen<B>) -> Gen<Vec<B>> where B: Clone + 'static, { let mut v: Vec<State<RNG, B>> = Vec::with_capacity(n); v.resize_with(n, move || gen.clone().sample); Gen { sample: State::sequence(v), } }
https://github.com/j5ik2o/prop-check-rs/blob/4776da568ca35ca319e66c866d9670ce7c9fe40f/src/gen.rs#L93
Gens#choose
特定の値の範囲から一つの値を選択する場合は、chooseが使えます。以下のようにすると、1から10までの値を一つ選択するGenを生成できます。
let gen = Gens::choose(1, 10); let prop = for_all_gen(gen, move |input| { println!("input = {}", input); // 1から10までの任意の数値 true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
map関数の中で、生成された乱数を素に、与えられた最小・最大の範囲から対応する数値を選ぶようにしています。
pub fn choose_u32(min: u32, max: u32) -> Gen<u32> { Gen { sample: State::<RNG, u32>::new(move |rng: RNG| rng.next_u32()), } .map(move |n| min + n % (max - min + 1)) }
Gens#one_of
chooseを使うと引数で与えた複数のGenから一つ選ぶone_ofも実装できます。
let gen = Gens::one_of(vec![Gens::choose(1, 10), Gens::choose(90, 100)]); let prop = for_all_gen(gen, move |input| { println!("input = {}", input); // 1から10までもしくは90から100までの任意の数値 true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
これもシンプル。コレクションのインデックスをchooseで選ぶ。そのインデックスを使ってVecからGenを取得して返すだけ。
pub fn one_of<T: Choose + Clone + 'static>(values: impl IntoIterator<Item = Gen<T>>) -> Gen<T> { let mut vec = vec![]; vec.extend(values.into_iter()); Self::choose(0usize, vec.len() - 1).flat_map(move |idx| vec[idx as usize].clone()) }
prop-check-rs/gen.rs at 4776da568ca35ca319e66c866d9670ce7c9fe40f · j5ik2o/prop-check-rs · GitHub
Gens#frequency
出現比率を指定できるfrequencyもあります。比率を表す数値とGenのタプルの配列かVecを引数に指定できます。
let gens = [ (3, Gens::choose_u32(1, 10)), (2, Gens::choose_u32(50, 100)), (5, Gens::choose_u32(200, 300)), ]; let gen = Gens::frequency(gens); let prop = for_all_gen(gen, move |input| { println!("input = {}", input); // 1〜10 or 50〜100 or 200から300の任意の数値が指定された出現比率で得られる true }); let result = test_with_prop(prop, 5, TEST_COUNT, RNG::new());
GenをBTreeMapに格納して、生成された乱数でキーを指定し、対応するGenを引き当てているだけです。
pub fn frequency<B>(values: impl IntoIterator<Item = (u32, Gen<B>)>) -> Gen<B> where B: Debug + Clone + 'static, { let filtered = values.into_iter().filter(|kv| kv.0 > 0).collect::<Vec<_>>(); let (tree, total) = filtered .into_iter() .fold((BTreeMap::new(), 0), |(mut tree, total), (weight, value)| { let t = total + weight; tree.insert(t, value.clone()); (tree, t) }); Self::choose_u32(1, total).flat_map(move |n| tree.range(n..).into_iter().next().unwrap().1.clone()) }
https://github.com/j5ik2o/prop-check-rs/blob/4776da568ca35ca319e66c866d9670ce7c9fe40f/src/gen.rs#L77
まとめ
あまり良い方法だと思いませんが、構造体に参照を持ち込むとどうしてもロジックが複雑になってしまうので、dyn FnをRcでラップしClone可能にしました。ほかに代替のよい方法があればよいのですが…。
pub struct State<S, A> { pub(crate) run_f: Rc<dyn Fn(S) -> (A, S)>, } impl<S, A> Clone for State<S, A> where S: 'static, A: Clone + 'static, { fn clone(&self) -> Self { Self { run_f: self.run_f.clone(), } } }
ということでご参考になれば幸いです。
