Creating a Clojure spec generator for a nested data structure with constraints across layers

Question

I am using Clojure spec to spec a simple data structure:

{:max 10
 :data [[3 8 1]
        [9 0 1]]}

The :data value is a vector of equal-size vectors of integers in the interval from zero to the :max value inclusive. I expressed this with spec as follows:

(s/def ::max pos-int?)
(s/def ::row (s/coll-of nat-int? :kind vector?, :min-count 1))
(s/def ::data (s/and (s/coll-of ::row :kind vector?, :min-count 1)
                     #(apply = (map count %))))

(s/def ::image (s/and (s/keys :req-un [::max ::data])
                      (fn [{:keys [max data]}]
                        (every? #(<= 0 % max) (flatten data)))))

Automatic generators work fine for the first three specs, but not for ::image. (s/exercise ::image) always fails after 100 tries.

I tried to create a custom generator for ::image but did not manage. I don’t see how I could express the constraints which cross the layers of the nested structure (key :max constrains values in a vector somewhere else).

Is it possible to create a Clojure spec/test.check generator that generates ::images?

Answer 1

Definitely! The key here is to create a model of the domain. Here I think the model is the max, col-size, and row-size. That's enough to generate a valid example.

So something like this:

(def image-gen
  (gen/bind
    (s/gen (s/tuple pos-int? (s/int-in 1 8) (s/int-in 1 8)))
    (fn [[max rows cols]]
      (gen/hash-map
        :max (s/gen #{max})
        :data (gen/fmap #(into [] (partition-all cols) %)
                (s/gen (s/coll-of (s/int-in 0 (inc max)) 
                                  :kind vector?
                                  :count (* rows cols))))))))

First, we generate a tuple of [<max-value> <rows> <cols>]. The gen/bind then returns a new generator that creates maps in the desired shape. We nest gen/fmap inside to build a vector of all random data values, then re-shape it into the proper nested vector form.

You can then combine that into image with:

(s/def ::image
  (s/with-gen 
    (s/and (s/keys :req-un [::max ::data])
           (fn [{:keys [max data]}]
             (every? #(<= 0 % max) (flatten data))))
    (fn [] image-gen)))

One maybe interesting thing to note is that I bounded the rows and cols to no more than 7 as the generator can otherwise attempt to generate very large random random sample values. Needing to bound things like this is pretty common in custom generators.

With some more effort, you could get greater reuse out of some of these specs and generator pieces as well.