test.check

stateful PRNG + bind => nondeterministic shrink tree

Details

  • Type: Defect Defect
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: None
  • Fix Version/s: None
  • Component/s: None
  • Labels:
    None

Description

bind inherently needs to consume randomness while shrinking, since the inner generator has to be run multiple times. Since the shrink tree is lazy and there's only one Random object providing the randomness, the resulting shrank values are sensitive to what order the tree is walked in.

I don't believe this affects normal usage, but there are various modifications I've made that I think are useful (e.g., resuming slow shrinks) that are thwarted by this nondeterminism.

Ideally we could stop using a stateful PRNG, but I think this would be a rather extreme change. A much smaller fix is to change bind to create a new Random object each time the inner function is called, based on a seed from the outer Random. I will have a patch that does this shortly, and it seems to fix the issues I've had.

Code for reproducing the issue:

(ns user
  (:require [clojure.test.check.generators :as gen]
            [clojure.test.check.rose-tree :as rose]))

(def the-gen
  (gen/bind gen/nat
            (fn [n]
              (gen/fmap (fn [m] [n m]) gen/nat))))

(defn reproduced?
  [seed]
  (let [make-rose-tree #(gen/call-gen the-gen (java.util.Random. seed) 100)
        rose-1 (make-rose-tree)
        rose-2 (doto (make-rose-tree)
                 ((fn [rt1]
                    ;; force the tree to be realized in a different way
                    (dorun (for [rt2 (rose/children rt1)
                                 rt3 (rose/children rt2)]
                             42)))))
        last-child #(-> % rose/children last rose/root)]
    ;; when these two are not equal, we've reproduced the problem
    (not= (last-child rose-1)
          (last-child rose-2))))

(frequencies (map reproduced? (range 10000)))
;; => {false 9952, true 48}

Activity

Hide
Gary Fredericks added a comment -

Attached TCHECK-27-p1, which makes the change I described in the description to the bind-helper function.

Show
Gary Fredericks added a comment - Attached TCHECK-27-p1, which makes the change I described in the description to the bind-helper function.
Hide
Gary Fredericks added a comment -

The only function that uses bind-helper is bind; however, bind is also implemented with gen-bind, and several other functions use gen-bind. So we'll have to check if gen-bind is sensitive to this as well (e.g., perhaps frequencies has this issue?). If so, I'm not sure what that means about the best way to fix it. Maybe there's an alternative fix that could happen in gen-bind, or maybe the other functions could be rewritten with bind?

Show
Gary Fredericks added a comment - The only function that uses bind-helper is bind; however, bind is also implemented with gen-bind, and several other functions use gen-bind. So we'll have to check if gen-bind is sensitive to this as well (e.g., perhaps frequencies has this issue?). If so, I'm not sure what that means about the best way to fix it. Maybe there's an alternative fix that could happen in gen-bind, or maybe the other functions could be rewritten with bind?

People

Vote (0)
Watch (1)

Dates

  • Created:
    Updated: