The shrinking problem with bind

Hegel-clj is a Clojure interface for Hegel, a cross-platform generative testing library. Its motivation comes from a long-standing frustration with test.check: complex generators can get stuck while shrinking, leaving developers to prune intricate data structures by hand. The usual suspect is bind, a generator that draws a random value and uses it to construct a new generator, from which another value is drawn.

(require '[clojure.test.check :as tc]
         '[clojure.test.check.generators :as tcg]
         '[clojure.test.check.properties :as tcp])
(tcg/bind ; Take a number from `nat`, a generator of small positive
          ; integers.
          tcg/nat
          ; Now with that number, construct a generator of vectors, each
          ; with that many elements.
          (fn [size]
            (tcg/vector tcg/large-integer size)))

The same construct can be written with test.check's let macro, which expands into nested binds.

(tcg/let [size tcg/nat]
  (tcg/vector tcg/large-integer size))

The canonical failure case is a search for a vector containing 42:

(-> (tc/quick-check 1000
      (tcp/for-all [xs (tcg/let [size tcg/nat]
                         (tcg/vector tcg/large-integer size))]
                   (not-any? #{42} xs))
      {:seed 1777986545686})
  :shrunk :smallest first)

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0]

The result does contain 42, but the vector is far larger than necessary. The explanation lies in shrink trees. test.check generators do not return plain values like 64; they return lazily evaluated trees of values, where the root might be 64 with children such as [32 48 ... 63], and each child has its own children in turn. Simplifying somewhat, that is how the tree for large integers is defined.

(defn- shrink-long
  "Given a number x, returns a coll of (x-x, x-x/2, x-x/4, x-x/8, ..., x-1)"
  [^long x]
  (core/let [size (- 64 (Long/numberOfLeadingZeros (Math/abs x)))
             ^longs vals (long-array size)]
    (loop [i 0 n x]
      (if (zero? n)
        vals
        (do
          (aset vals i (- x n))
          (recur (inc i) (quot n 2))))))))

When 64 violates a property, test.check tries its first child, 32. If that passes, it tries 48; if 48 fails, it descends into 24, and so on. This clever depth-first walk often shrinks an integer quickly.

Fixed-size vectors follow a similar pattern: the tree for [2 2] has children like [1 2] and [2 1], derived from each element's tree. That is why test.check produced something like [0 0 0 ... 42 0]: it found a vector such as [91 23 1034543 ... 42 15] and shrank elements from the front until only the failing 42 refused to shrink. Since (tcg/vector tcg/large-integer size) always used a fixed size, the tree kept size elements—39 here.

But the original generator did not use a fixed size. It drew the size, then built a vector of that length:

(tcg/bind tcg/nat
          (fn [size]
            (tcg/vector tcg/large-integer size)))

The trees bind produces can shrink in two directions: the outer value (the size from tcg/nat) or the inner value (the vector). Suppose a size of 100 yields [15 32 42 ...], which contains 42. One shrink branch tries sizes like [50, 75, ... 99]. Picking 50 invalidates the old vector, so bind invokes the function with 50 to build a new generator and draws a fresh vector with different random elements, such as [69, 45, 1, ...]. If that vector lacks a 42, test.check abandons the branch and tries size 75, drawing yet another vector. Because 42 is uncommon, most sizes fail to reproduce it, and shrinking stalls at, say, 39 elements. From there each element can still be shrunk, yielding the oversized result.

[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 42 0]

With simple vectors the defect is easy to spot. In nontrivial generators, a dozen nested levels of bind can each serve as a place to get stuck, and the resulting minimal case is very hard to interpret. Seasoned test.check users avoid bind and let, but many problems make them unavoidable.

A different shrinking strategy

Python's Hypothesis team took the other route. test.check is a two-phase system: a generator builds a shrink tree, then the library walks that tree once the root looks bad. Hypothesis generators instead return a single value, and when that value looks bad, the generator is re-run with a request for something similar but smaller. This technique, internal test-case-reduction, underpins Hegel.

The hegel-clj API

Hegel supplies deterministic generators drawing from an imperative, structured RNG, plus a family of special values and shrinking tactics. That core library does the hard work once; thin wrappers bring the results to many languages. hegel-clj is the Clojure binding: call hegel-clj/test!, draw from generators, and throw when the test should fail. Hegel searches for values that make the body throw, then shrinks them.

(require '[hegel-clj [core :as h] [generator :as g]])
(h/test! {:seed 4}
  (assert (even? (h/draw! (g/integer)))))

{:passed? false
 :status :failed
 :statistics {:total 34
              :valid 5
              :invalid 0
              :overrun 18
              :interesting 11}
 :health-check-failed? false
 :failures ({:draws {"draw_1" 1}
             :exception
             #error {:cause "Assert failed: (even? (h/draw! (g/integer)))"
                     ...}})
 :reproduce-blob "AAEAAAAACgEAAAAB", :caveat nil}

Here the smallest case was a single draw of 1, which made (even? 1) throw. Generators are pure, composable structures as in test.check:

(h/sample 5 (g/boolean))

[false false true true false]

A map representing a person, with a name drawn from a regular expression and an integer age, works the same way:

(h/sample 5 (g/hmap {:name (g/regex-str #"[A-Z][a-z]+")
                     :age  (g/integer 0 101)}))

[{:name "Aa", :age 0}
 {:name "Iyjdklppzxhqdnwmd", :age 89}
 {:name "Kslvqorm", :age 64}
 {:name "Fvyybe", :age 45}
 {:name "Puwppxqag", :age 4}]

Higher-order combinators are present as well. fmap transforms generated values:

(h/sample 5 (g/fmap keyword (g/string)))

[: :R :👍🏻 :True :çç¦ç¦򜝉ÏÏ򜝉¦¦Ï¦¦ç򜝉Ϧç򜝉çÏ򜝉çç¦]

and bind builds one generator from another:

(h/sample 2 (g/bind (fn [size]
                      (g/tuple (g/vector size (g/integer))
                               (g/vector size (g/boolean))))
                    (g/integer 0 3)))

[[[] []]
 [[144229 531621 -364 -1569883 8194954 -913 16 -745]
 [false true false true]]]

As in test.check, the let macro binds either ordinary values or generators; a generator on the right-hand side draws a random value. Unlike test.check, the shrink quality holds up: Hegel reduces the bad vector to [42] instead of thirty-nine elements.

(-> (h/test! {:test-cases 1000
              :seed       1777986545686}
      (h/let [size (g/integer {:min 0, :max 128})
              xs   (g/vector {:size size} (g/integer))]
        (assert (not-any? #{42} xs))))
    :failures first :draws (get "xs"))

[42]

Where test.check forces you to build and destructure maps or tuples to thread several values through bind or fmap, composite lifts arbitrary code into a generator, simplifying complex definitions:

(h/sample 2
  (g/composite
    (h/let [name      (g/string)
            cat-count (g/integer 0 2)
            cats      (g/vector {:size cat-count, :unique? true} (g/string))]
      {:name name     
       :cats cats})))

[{:name "",
  :cats []}
 {:name "𝐓𝐡𝐞 𝐪𝐮𝐢𝐜𝐤 𝐛𝐫𝐨𝐰𝐧 𝐟𝐨𝐱 𝐣𝐮𝐦𝐩𝐬 𝐨𝐯𝐞𝐫 𝐭𝐡𝐞 𝐥𝐚𝐳𝐲 𝐝𝐨𝐠",
  :cats ["🇺🇸" "👍🏻"]}]

Recursive generators are possible through a promise-style API. deferred leaves a blank slot for a generator that can be filled in later:

(let [leaf (g/integer 0 9)
      tree (g/deferred)]
  (g/set-deferred! tree (g/one-of [leaf (g/vector tree)]))
  (mapv prn (h/sample 5 tree)))

0
[[1] 8 [2 []] 5 [] [[4 6 []]]]
[[1] 2]
3
0

clojure.test integration is built in, so generative tests are as easy to write as example-based ones:

(require '[clojure.test :refer :all] '[hegel-clj.clojure-test :refer [with]])

(defn bad-add
  "Adds two integers via floating-point"
  [x y]
  (long (+ (float x) (float y))))

(deftest bad-add-test
  (with {:test-cases 100}
        [x (g/integer)
         y (g/integer)]
    (h/fprn :x x, :y y)
    (is (= (+ x y) (bad-add x y)))))
    
(bad-add-test)

:x 0 :y 16777217

FAIL in (bad-add-test) (form-init7301103820420620476.clj:6)
expected: (= (+ x y) (bad-add x y))
  actual: (not (= 16777217 16777216))

Debuggability and API design

Debug logging is awkward with test.check: you sift through thousands of runs, most of which never trigger the bug. Hegel has a notion of a "final" test case—after finding and shrinking a counterexample, it re-runs that case during a final phase. (when (h/final?) ...) executes debugging code only for those cases, and fprn and finfo wrap clojure.core/prn and clojure.tools.logging/info. A Hegel bug currently runs more final cases than it should, but the feature is still a significant improvement.

test.check's long stability has frozen some early design choices. It is (fmap gen f) but (bind f gen). Choosing an integer means remembering the difference between nat, int, pos-int, s-pos-int, small-integer, large-integer, large-integer* and others. Common generators take keyword arguments like (large-integer* {:min 0, :max 10}), and some, such as hash-map, are only callable with varargs, which complicates composition. The properties API feels fussy, and ergonomic features—regex-based string generation, clojure.test integration—need an extra library such as test.chuck. hegel-clj aims for a more streamlined, consistent and approachable API.

hegel-clj 0.1.1 is available now on GitHub.