Welcome! Please see the About page for a little more info on how this works.

0 votes
in test.check by
I wrote a AST generator for a search engine using test.check. It works quite well, but for some reason recursive generators don't shrink "vertically", instead they only shrink vertically. For exmaple, let's say this AST failed:



{:op :and
 :args [{:op :and
         :args [{:op :term ...}
                {:op :term ...}
                {:op :term ...}]}]}



After Shrinking



{:op :and
 :args [{:op :and
         :args [{:op :term ...}]}]}



The problem is in `{:op :term}` but for some reason test.check doesn't try to remove the recursive `:and` nodes. Not a big deal, but would be a nice feature to have.

7 Answers

0 votes
by

Comment made by: gfredericks

Does this use {{gen/recursive-gen}}?

0 votes
by

Comment made by: halgari

Yes, I'm using recursive-gen.

0 votes
by
_Comment made by: gfredericks_

So this looks like the same issue?


(quick-check 10000
             (prop/for-all [tree (gen/recursive-gen gen/vector gen/large-integer)]
               (->> tree
                    (tree-seq coll? seq)
                    (not-any? #{4242}))))
;; =>
{:result false,
 :seed 1466641044276,
 :failing-size 151,
 :num-tests 3152,
 :fail [[[-250312923371676 -2634403398808308]
         [-134580]
         1190117809715
         [1736827773692]
         [91379147228 281572852]
         []
         []
         [264322377680727]
         [-2 -2005122340306]
         []
         []
         [2133414023]
         []
         [-7203148411369 2093087]
         [-1 -1]
         [-350804570003194 -24726]
         [-2145238760990835556]
         [-4410884650149229158 27914810]
         []
         [21126727]
         [816412492 102]
         [1]
         [-119 -2132126120873]
         [50]
         [1590594626470485464 -555554916273244]
         [4242 322325]]],
 :shrunk {:total-nodes-visited 57,
          :depth 11,
          :result false,
          ;; should have shrunk to `4242`
          :smallest [[[4242]]]}}
0 votes
by

Comment made by: gfredericks

I'm not 100% sure there's a clean solution to this, but note to self: shrinking to sub-trees should be the first thing we try

0 votes
by

Comment made by: gfredericks

If TCHECK-112 ends up being figured out it might apply here too.

0 votes
by

Comment made by: gfredericks

I think there is a messy solution to this that is just barely okay.

To shrink to the children, you need to know what they are, including their shrink trees.

One way to do this would be for {{recursive-gen}} to wrap the generator it passes to the user function in some instrumentation that keeps track of what args the generator was called with (or what its return values were), and then prepends items to the final shrink tree that attempt to shrink directly to those values first.

A minor objection to this approach is that just because the generator passed in was called, does not mean that the values generated by those calls were actually used (e.g., they could have been filtered out by {{such-that}}).

However, I think this only amounts to possible confusion in the worst case, since anything generated by the generator passed to the user function is a valid thing for the whole structure to generate. So it shouldn't be invalid to shrink to, even if it is unrelated.

0 votes
by
Reference: https://clojure.atlassian.net/browse/TCHECK-110 (reported by halgari)
...