Skip to:

  1. Skip to Jira Navigation
  2. Skip to Side Navigation
  3. Skip to Main Content

bind doesn't shrink very well

Description

This is a long-standing Hard Problem.

The Problem

The classic example is shrinking a 2d matrix with a poisoned element in it:

(def gen-matrix (gen/let [width gen/nat] (gen/vector (gen/vector gen/large-integer width)))) (quick-check 10000 (prop/for-all [matrix gen-matrix] (->> matrix (apply concat) (not-any? #{42})))) ;; => {:result false, :seed 1466646880334, :failing-size 16, :num-tests 17, :fail [[[290 42 10 3 1 3 196] [-1793 3484 -5795 -206 -1 -8 464] [2 3 -1951 -761 -28829 5518 1] [-32 4477 1 -4086 0 1640 -22185] [-485 3156 -625 4082 -2 -845 513] [-3 -1 26 323 232 5 -1] [32 51 -1 240 -1814 0 -190] [2417 -4239 326 -4096 -8 1898 75] [-509 1 0 466 199 -1 10] [-23 5838 -441 30741 -6724 -1169 -171] [-4 3974 -1432 -4 698 -56 1210] [-2148 -6526 -1 453 19 -5343 461]]], :shrunk {:total-nodes-visited 31, :depth 8, :result false, ;; would be better if shrunk to [[[42]]] ;; ;; note that it's plausible the smallest value here could have the same width (7) ;; as the original failure -- the only reason it was able to shrink the width at ;; all was that it got lucky by generating an entirely new matrix with the smaller ;; width that happened to have 42 in it :smallest [[[0 42 0]]]}}

Ideas

Environment

None

Activity

Show:

Kevin Downey October 27, 2022 at 10:33 PM

hypothesis (the python pbt library) has a mechanism that I think solves this(which is what the DRMacIver tweet is about, but it seems like the alluded to java port is dead).

there are some neat videos and papers about it, but basically generators don’t do any shrinking. generators just consume a random vector of numbers, and produce some structure from it, and then you shrink by shrinking the random vector, and re-feeding it to the generator.

I think it is possible to add this to test.check as an additive change.

Kevin Downey March 9, 2022 at 4:57 AM

https://www.well-typed.com/blog/2019/05/integrated-shrinking/ talks about composing rose trees as applicatives instead monads (bind) resulting in better shrinking, because the f passed to bind is opaque

Details

Assignee

Reporter

Priority

Created June 23, 2016 at 2:56 AM
Updated October 27, 2022 at 10:33 PM