<< Back to previous view

[TCHECK-112] bind doesn't shrink very well Created: 22/Jun/16  Updated: 22/Jun/16

Status: Open
Project: test.check
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Gary Fredericks Assignee: Gary Fredericks
Resolution: Unresolved Votes: 0
Labels: None


 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






[TCHECK-111] The latest recursive-gen algorithm seems to exhibit a peculiar lack of variety in depths Created: 22/Jun/16  Updated: 22/Jun/16

Status: Open
Project: test.check
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Gary Fredericks Assignee: Gary Fredericks
Resolution: Unresolved Votes: 0
Labels: None


 Description   

In particular the output of (generate (recursive-gen vector nat) 1000) is rather less varied than I would hope.






[TCHECK-110] Enable shrinking on recursive generators Created: 22/Jun/16  Updated: 22/Jun/16

Status: Open
Project: test.check
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Timothy Baldridge Assignee: Gary Fredericks
Resolution: Unresolved Votes: 0
Labels: None


 Description   

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.



 Comments   
Comment by Gary Fredericks [ 22/Jun/16 7:12 PM ]

Does this use gen/recursive-gen?

Comment by Timothy Baldridge [ 22/Jun/16 7:17 PM ]

Yes, I'm using recursive-gen.

Comment by Gary Fredericks [ 22/Jun/16 7:25 PM ]

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]]]}}
Comment by Gary Fredericks [ 22/Jun/16 7:36 PM ]

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

Comment by Gary Fredericks [ 22/Jun/16 8:58 PM ]

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





Generated at Sun Jun 26 05:10:56 CDT 2016 using JIRA 4.4#649-r158309.