edwintorok
commented
1 year ago FWIW I'm using the following string generator/shrinker in my code, it makes the shrinker work reasonably fast, although it is not a general purpose shrinker.
I tried to make 'shrink_all_chars' apply Shrink.char to each char just once, but even that is too slow, even if I write a one-step shrinker using just Char.chr/Char.code/Bytes.set and bit shifts (my strings are sometimes in the range of ~64k to reproduce certain bugs), workarounds there are to artifically introduce smaller limits elsewhere in the code such that bugs can still be hit with much shorter strings.
let truncated_str s =
if String.length s < 6 then
String.escaped s
else
Printf.sprintf "%s…(len:%d)"
(String.sub s 0 6 |> String.escaped)
(String.length s)
let all_bytes = String.init 256 Char.chr
let repeat n = List.init n (fun _ -> all_bytes) |> String.concat ""
let shrink_string_length str =
let open QCheck in
str |> String.length |> Shrink.int |>
QCheck.Iter.map (String.sub str 0)
let shrink_all_chars str yield =
(* shrinking each char individually would yield too many possibilities
on long strings if shrinking doesn't reproduce the bug anymore.
Instead shrink all chars at once, with a single result.
It will eventually converge on 'aa...a'.
*)
let next = String.make (String.length str) 'a' in
(* avoid infinite iteration: stop when target reached *)
if not (String.equal next str) then
yield next
let shrink_string str yield =
shrink_string_length str yield;
shrink_all_chars str yield
let bounded_string_arb n =
(* QCheck.Shrink.string is very slow: first converts to list of chars.
In our case bugs come from 3 sources:
* the byte values (e.g. ASCII vs non-ascii)
* the length of the string (whether it hits various limits or not)
* the uniqueness of the string (e.g. duplicate inserts)
Generate a small fully random string of fixed size, and concatenate it with a random length substring of a static string.
Shrinking will take care of producing smaller and more readable results as needed,
even below the fixed size
*)
assert (n > 4) ;
let n = n - 4 in
let long = ref [] in
let () = if n > 0 then
(* pregenerate all the long strings by running the shrinker on a static string *)
let max_repetitions = n / String.length all_bytes in
let max_str =
repeat max_repetitions
^ String.sub all_bytes 0 (n mod String.length all_bytes)
in
shrink_string_length max_str (fun s -> long := s :: !long)
in
let gen_long = QCheck.Gen.oneofa @@ Array.of_list !long in
let gen_string =
let open QCheck.Gen in
let* small = string_size @@ return 4 in
let+ long = gen_long in
small ^ long
in
QCheck.(make
~print:truncated_str
~small:String.length
~shrink:shrink_string
gen_string)
jmid
As the new
QCheck.Shrink.stringunit tests document, on a failure path (going through all shrinking candidates without luck) the current approach may be a bit too exhaustive: https://github.com/c-cube/qcheck/blob/f37621a4763d556f05e35cefe81d4e29b932be25/test/core/QCheck_unit_tests.ml#L93-L103By falling back on
Shrink.list_spinewe get a nice and short candidate sequence when we stay clear of element reduction:However, exhaustively trying to reduce all O(n) entries, say O(log n) times, brings this to O(n log n) which may be a bit much:
We are getting bitten by this in ocaml-multicore/multicoretests, as remarked by @edwintorok here: https://github.com/ocaml-multicore/multicoretests/pull/329#issuecomment-1522990777
As an alternative to avoiding character-shrinks above a certain threshold, one could consider alternative approaches, e.g.
'a'charchars simultaneously"zzzzz"-> "aaazz"