shrink-seq doesn't shrink

[cemerick]

cemerick.test-sedan=> (def genvec (sgen/vector (sgen/int 5000) 10))
#'cemerick.test-sedan/genvec
cemerick.test-sedan=> (sgen/arbitrary genvec)
[4502 382 714 4866 3339]
cemerick.test-sedan=> (sgen/shrink genvec *1)
([382 714 4866 3339] [4502 714 4866 3339] [4502 382 4866 3339] [4502 382 714 3339] [4502 382 714 4866] [4502 382 714 4866 0] [4502 382 714 4866 1670] [4502 382 714 4866 2505] [4502 382 714 4866 2922] [4502 382 714 4866 3131] [4502 382 714 4866 3235] [4502 382 714 4866 3287] [4502 382 714 4866 3313] [4502 382 714 4866 3326] [4502 382 714 4866 3333] [4502 382 714 4866 3336] [4502 382 714 4866 3338] [4502 382 714 0 3339] [4502 382 714 2433 3339] [4502 382 714 3650 3339] [4502 382 714 4258 3339] [4502 382 714 4562 3339] [4502 382 714 4714 3339] [4502 382 714 4790 3339] [4502 382 714 4828 3339] [4502 382 714 4847 3339] [4502 382 714 4857 3339] [4502 382 714 4862 3339] [4502 382 714 4864 3339] [4502 382 714 4865 3339] [4502 382 0 4866 3339] [4502 382 357 4866 3339] [4502 382 536 4866 3339] [4502 382 625 4866 3339] [4502 382 670 4866 3339] [4502 382 692 4866 3339] [4502 382 703 4866 3339] [4502 382 709 4866 3339] [4502 382 712 4866 3339] [4502 382 713 4866 3339] [4502 0 714 4866 3339] [4502 191 714 4866 3339] [4502 287 714 4866 3339] [4502 335 714 4866 3339] [4502 359 714 4866 3339] [4502 371 714 4866 3339] [4502 377 714 4866 3339] [4502 380 714 4866 3339] [4502 381 714 4866 3339] [0 382 714 4866 3339] [2251 382 714 4866 3339] [3377 382 714 4866 3339] [3940 382 714 4866 3339] [4221 382 714 4866 3339] [4362 382 714 4866 3339] [4432 382 714 4866 3339] [4467 382 714 4866 3339] [4485 382 714 4866 3339] [4494 382 714 4866 3339] [4498 382 714 4866 3339] [4500 382 714 4866 3339] [4501 382 714 4866 3339])

Here's the vector generator I'm using at the moment:

(defn vector-gen
  [gen max-size]
  (reify Generator
    (arbitrary [this]
      (vec (repeatedly (rand-int max-size) #(arbitrary gen))))
    (shrink [this v]
      ; TODO should we recursively shrink the contents? Almost surely...
      (->> (iterate #(subvec % 0 (Math/floor (/ (count %) 2))) v)
           (map vec)
           (take-while seq)
           (#(concat % [[]]))))))

cemerick.test-sedan=> (def genvec (vector-gen (sgen/int 5000) 10))
#'cemerick.test-sedan/genvec
cemerick.test-sedan=> (sgen/arbitrary genvec)
[4267 288 808 170 3365]
cemerick.test-sedan=> (sgen/shrink genvec *1)
([4267 288 808 170 3365] [4267 288] [4267] [])

Seems more sane…?

[cemerick]

FYI, what I thought must have been an infinite loop bug in shrink-loop disappeared once I started using the vector-gen above, avoiding shrink-seq.

I think it might make sense to cap total-nodes-visited at some reasonable large number by default so that borked shrinker impls don't create runaways.

[reiddraper]

It's a little tough to see, but the shrinking is working how I intended. Whether that's correct or not is also up for debate though. First, it's important to view shrinking as a tree, the shrink function which returns a sequence of shrinks only returns one level of the tree. Each of those children can then be shrunk more. So let's take a walk down the left-hand side of the tree:

(def starting [4502 382 714 4866 3339])
(first (gen/shrink genvec starting))
;; => [382 714 4866 3339]
(first (gen/shrink genvec *1))
;; => [714 4866 3339]
(first (gen/shrink genvec *1))
;; => [4866 3339]
(first (gen/shrink genvec *1))
;; => [3339]
(first (gen/shrink genvec *1))
;; => []

Going down the left-hand side of the tree is interesting because we'll keep going deeper in the tree as long as the test continues to fail. All of this being said, I think it's definitely worth comparing the performance/effectiveness of different shrink sequence generators.

---

I think it might make sense to cap total-nodes-visited at some reasonable large number by default so that borked shrinker impls don't create runaways.

+1. Perhaps a metric based on time too.

[reiddraper]

Created #9 to track shrink time-capping.