What Could Possibly Go Wrong

What could possibly go wrong? We have no clue; that's why we use QuickCheck.

Hedgehog is a modern property-based testing toolkit. It's implemented in a number of programming languages, among others in Scala.

To celebrate the recent release of my workmate's new Scala book, let's throw a Polyglot Party and wrap Hedgehog with Clojure. We'll loosely model our API after test.check, a popular Clojure property-based testing library.

We'll implement our wrapper in a Nextjournal notebook with two environments: one with a Scala compiler and one running a Clojure REPL. We'll use the former to compile some Scala sources and then load the resulting bytecode into the latter.

What could possibly go wrong if you put Clojure 1.10 and Scala 2.13 on the same classpath? We're about to find out.

Dependencies

We declare our dependencies in deps.edn. Contents of this file are automatically picked up by the Clojure environment. Preinstalled tooling will download all dependencies and save them in the ~/.m2 directory.

We begin with Clojure and the Scala standard library. On top of those we add a snapshot of the Hedgehog library, available in a Maven repository hosted at Bintray. We also add /shared to the class path. It's a directory shared by all environments running in this notebook, allowing us to share files between them.

{:deps
 {org.clojure/clojure {:mvn/version "1.10.1"}
  org.scala-lang/scala-library {:mvn/version "2.13.1"}
  qa.hedgehog/hedgehog-core_2.13 {:mvn/version "452df95337eb6d29485f34cd30e23e584b3987f0"}}
 
 :mvn/repos
 {"hedgehog" {:url "https://dl.bintray.com/hedgehogqa/scala-hedgehog/"}}
 
 :paths ["/shared"]}
deps.edn
Clojure

Upon startup, the Clojure environment picks up the list of dependencies and fetches them from Maven repositories. One of the downloaded files—the Hedgehog archive—needs to be shared with the Scala environment. Let's do it by “shell scripting” in the Clojure REPL.

(require '[clojure.java.shell :refer [sh]])
(let [cmd "find ~/.m2 -name hedgehog-core*.jar -exec cp '{}' /shared/ \\;"
      {:keys [exit err]} (sh "sh" "-c" cmd)]
  (assert (zero? exit) err))
0.5s
Clojure

The Scala environment we're using includes a number of versions of the language. By default it's 2.12.8. We can switch it to 2.13.0 by replacing a symlink.

cd /opt/scalas && rm default && ln -s scala-2.13.0 default
scalac -version
2.4s
Bash

Wrapping Scala

At this point all the dependencies are in place. Unfortunately, vanilla Clojure can't easily interact with Hedgehog's Scala API. To go around it we need to wrap the library with a thin layer translating its Scala interface to Java. While struggling with the former, Clojure will readily consume the latter.

wrap.scala looks as follows.

package urchin
import hedgehog._
import hedgehog.core.{PropertyConfig, Report, PropertyT}
import java.{util => ju}
import java.{lang => jl}
import scala.jdk.CollectionConverters._
// The Interop object will expose two functions for converting Scala
// collections to Java and back again. Notice the null case in the
// second function. In Clojure, null is often used to represent
// an empty collection, and we convert it accordingly.
object Interop {
  def java(xs: Iterable[Any]): jl.Iterable[Any] =
    xs.asJava
  def scala(xs: ju.Collection[Any]): List[Any] = xs match {
    case null => List()
    case _ => xs.asScala.toList
  }
}
// Now we can move on to wrapping Hedgehog. We begin with generators
// of simple values and proceed to combinators such as `choice` or
// `vec`.
object G {
  val boolean: Gen[Boolean] = Gen.boolean
  val alpha: Gen[Char] = Gen.alpha
  val alphaNum: Gen[Char] = Gen.alphaNum
  val unicode: Gen[Char] = Gen.unicode
  def string(g: Gen[Char], len: Int): Gen[String] =
    Gen.string(g, Range.linear(0, len))
  def double(min: Double, max: Double): Gen[Double] =
    Gen.double(Range.linearFracFrom(0.0, min, max))
  def long(min: Long, max: Long): Gen[Long] =
    Gen.long(Range.linearFrom(0, min, max))
  def element(x: Any, xs: List[Any]): Gen[Any] =
    Gen.element(x, xs)
  def choice(g: Gen[Any], gs: List[Gen[Any]]): Gen[Any] =
    Gen.choice(g, gs)
  def vec(g: Gen[Any], max: Int): Gen[jl.Iterable[Any]] =
    Gen.list(g, Range.linear(0, max)).map(Interop.java)
}
// Our generators are in place. Now we need a way to turn
// them into properties. Additionally, given properties
// we want Hedgehog to run and check them.
object P {
  def prop(g: Gen[Any], pred: Any => Boolean): Property =
    for {
      value <- g.forAll
    } yield Result.assert(pred(value))
  def check(c: PropertyConfig, p: PropertyT[Result]): Report =
    Property.checkRandom(c, p)
}
wrap.scala
Scala

After all, the wrapper's only task is to remove all the implicit parameters and type information from the original Scala API and expose a pure Java interface. This allows us to consume it from Clojure.

We leave it as an exercise for the adventurous reader to programmatically turn the original type information into a clojure.spec specification of the new API.

With the wrap.scala file in place, we can invoke scalac and compile the wrapper. We'll depend on the jar file we copied from the Clojure environment's ~/.m2 directory.

The compiler writes resulting classes to /shared. The directory is already on Clojure's classpath, allowing us to load our wrapper into the JVM running in the other environment.

scalac -cp /shared/hedgehog-core*.jar -d /shared wrap.scala
7.7s
Bash

Amidst Parentheses

Our Scala wrapper consists of three classes in the urchin package: G, P and Interop. We can now move on to defining a Clojure API around them. Let's create a new namespace urchin.core. We exclude some core functions, as we're going to define our own vars aliasing those names.

(ns urchin.core
  (:refer-clojure :exclude [boolean
                            double
                            filter
                            keyword
                            long
                            map
                            vec])
  (:import [urchin G P Interop]
           [hedgehog
            Size PropertyTOps]
           [hedgehog.core
            GenT Tree Seed
            Failed OK$ GaveUp$ Info
            PropertyConfig SuccessCount DiscardCount ShrinkLimit]))
0.1s
Clojure

Let's turn on warnings on reflection. We're going to do some Java interop and we'd rather avoid reflective invocations or accidental misuse of the Java API.

(set! *warn-on-reflection* :yes-please)
0.1s
Clojure
:yes-please

Sampling

Before we embark on defining generators of Clojure values, it'd be convenient to have an easy way of sampling them, i.e. inspecting values they generate. To achieve that we need to do wrap some low level operations of Hedgehog generators. Bear with me, it'll take just a minute, and don't let the exposed wiring bother you.

(defn seed
  ([] (Seed/fromTime))
  ([x] (Seed/fromLong x)))
(defn from-pair [^scala.Tuple2 pair]
  [(._1 pair) (._2 pair)])
(defn from-option [^scala.Option option]
  (if-not (.isEmpty option)
    (.get option)))
(defn run
  ([^GenT g size]
   (run g size (seed)))
  ([^GenT g size seed]
   (let [tree (.. g run (apply (Size. size) seed))
         [next-seed option] (from-pair (.value ^Tree tree))]
     (merge {:seed next-seed}
            (if-let [value (from-option option)]
              {:value value}
              {:empty true})))))
0.2s
Clojure
urchin.core/run

run is quite an eyesore, but we'd rather have all the plumbing in one place. Now we can use it to define a function sampling a generator.

(defn sample-seq
  ([g]
   (sample-seq g 0))
  ([g size]
   (->> [nil true (seed) size]
        (iterate (fn [[_ _ seed size]]
                   (let [{:keys [value seed empty]} (run g size seed)]
                     [value empty seed (inc size)])))
        (remove second)
        (clojure.core/map first))))
(def sample
  (comp (partial take 5) sample-seq))
0.1s
Clojure
urchin.core/sample

Generators

Now let's wrap generators of simple values.

(defn boolean []
  (G/boolean))
(defn alpha []
  (G/alpha))
(defn alpha-num []
  (G/alphaNum))
(defn unicode []
  (G/unicode))
(defn string
  ([]
   (string (alpha) 10))
  ([g size]
   (G/string g size)))
(defn double
  ([]
   (double -1e6 1e6))
  ([min max]
   (G/double min max)))
(defn long
  ([]
   (long -1e6 1e6))
  ([min max]
   (G/long min max)))
(sample (string) 100)
0.2s
Clojure
List(5) ("SRLqgYO", "TrOkPzsKBK", "vmp", "", "Ec")

We can also wrap element and choice to build more complex generators.

(defn element [x & xs]
  (G/element x (Interop/scala xs)))
(defn choice [g & gs]
  (G/choice g (Interop/scala gs)))
(sample (choice (element :yes :no)
                (long)
                (double)))
0.2s
Clojure
List(5) (0, -3040, -6601, :yes, -7592.566658511856)

Interfaces of Clojure and Scala functions differ. Let's convert unary Clojure functions to Scala ones. Due to Clojure's broad definition of what's true and false, scala-predicate needs to coerce the return value of f into a Boolean.

(defn scala-fn [f]
  (reify scala.Function1
    (apply [this x]
      (f x))))
(defn scala-predicate [f]
  (scala-fn (comp clojure.core/boolean f)))
0.1s
Clojure
urchin.core/scala-predicate

scala-fn and scala-predicate allow us to define map and filter operating on generators.

(defn map [f ^GenT g]
  (.map g (scala-fn f)))
(defn filter [f ^GenT g]
  (.filter g (scala-predicate f)))
0.1s
Clojure
urchin.core/filter

Using map and filter we can provide generators of vectors and simple keywords.

(defn vec
  ([g]
   (vec g 1e3))
  ([g size]
   (map clojure.core/vec (G/vec g size))))
(defn keyword []
  (->> (string (alpha) 20)
       (filter seq)
       (map clojure.core/keyword)))
(sample (vec (keyword)))
0.4s
Clojure
List(5) (Vector(0), Vector(3), Vector(8), Vector(9), Vector(12))

In order to define namespaced keywords we'll introduce gen, a macro allowing us to combine generators.

(defn bind [^GenT g f]
  (.flatMap g (scala-fn f)))
(defmacro gen [binding body]
  (if-let [[sym g & more] (seq binding)]
    `(bind ~g (fn [~sym] (gen ~more ~body)))
    `(element ~body)))
(defn keyword-ns []
  (let [non-empty-string (filter seq (string (alpha) 20))]
    (gen [ns   non-empty-string
          name non-empty-string]
       (clojure.core/keyword ns name))))
(sample (keyword-ns) 20)
0.2s
Clojure
List(5) (:jc/fJzM, :h/A, :aaNK/yWj, :CXy/FUb, :C/dE)

The bind function comes in handy when we define a generator of tuples.

(defn tuple [g & gs]
  (if (seq gs)
    (bind g (fn [x] (map #(cons x %) (apply tuple gs))))
    (map list g)))
(sample (tuple (keyword) (string (unicode) 10)) 20)
0.1s
Clojure
List(5) (List(2), List(2), List(2), List(2), List(2))

Properties

There are many more kinds of values we could generate. Let's stop here though and instead focus our attention on properties.

To define a property we need a generator and a predicate. Let's introduce for-all macro implemented in terms of gen we've defined above and for-all*, a simple helper function.

(defn for-all* [g p]
  (P/prop g (scala-predicate p)))
(defmacro for-all [binding body]
  (let [symbols (mapv first (partition 2 binding))]
    `(for-all* (gen ~binding ~symbols)
               (fn ~[symbols]
                 ~body))))
0.2s
Clojure
urchin.core/for-all

We can use the for-all macro to express an iffy claim that all non-empty vectors of longs are sorted. But how do we check it?

(def all-sorted-prop
  (for-all [x (long)
            xs (vec (long))]
     (apply <= (cons x xs))))
0.2s
Clojure
urchin.core/all-sorted-prop

Inputs and Outputs

Before we check our newly defined property, let's translate Hedgehog's reporting and logging mechanism into Clojure, i.e. into plain data.

(defmulti ^:private log class)
(defmethod log Info
  [^Info info]
  {:info (.value info)})
(defmethod log hedgehog.core.Error
  [^hedgehog.core.Error error]
  {:error (.value error)})
(defmulti ^:private status class)
(defmethod status Failed
  [^Failed fail]
  {:status :failed
   :shrinks (.. fail shrinks value)
   :log (for [elem (Interop/java (.log fail))]
          (log elem))})
(defmethod status OK$
  [ok]
  {:status :ok})
(defmethod status GaveUp$
  [g]
  {:status :gave-up})
0.4s
Clojure
Vector(4) [clojure.lang.MultiFn, "0x2c71171f", "clojure.lang.MultiFn", Map]

We also need to convert a Clojure map with options into a PropertyConfig value.

(def ^:private defaults
  (let [default (PropertyConfig/default)]
    {:test-limit    (.. default testLimit value)
     :discard-limit (.. default discardLimit value)
     :shrink-limit  (.. default shrinkLimit value)}))
(defn- config [{:keys [test-limit discard-limit shrink-limit]}]
  (PropertyConfig. (SuccessCount. test-limit)
                   (DiscardCount. discard-limit)
                   (ShrinkLimit. shrink-limit)))
0.1s
Clojure
urchin.core/config

It All Checks Out

All what's left is defining a function taking a property, running it, and reporting the result.

(defn check
  ([property] (check {} property))
  ([opts property]
   (let [report (P/check (config (merge defaults opts)) property)]
     (merge {:tests (.. report tests value)
             :discards (.. report discards value)}
            (status (.status report))))))
0.1s
Clojure
urchin.core/check

So are all vectors sorted?

(check all-sorted-prop)
0.7s
Clojure
Map {:tests: 0, :discards: 0, :status: :failed, :shrinks: 16, :log: List(1)}

Not really. [0 -1] is a convincing counterexample. What if we sort them, though?

(check
  (for-all [x (long)
            xs (vec (long))]
     (apply <= (sort (cons x xs)))))
0.6s
Clojure
Map {:tests: 100, :discards: 0, :status: :ok}

By Jove, it all appears to work.

🦔 Appendix

A bit more plumbing code allows us to obtain shrinking trees of arbitrary Hedgehog generators.

(import '[hedgehog.predef LazyList])
(defn shrink-tree
  ([^GenT g size]
   (shrink-tree g size (seed)))
  ([^GenT g size seed]
   (letfn [(rec [^Tree tree depth]
             (let [[_ option] (from-pair (.value tree))
                   ^LazyList list (.. tree children value)
                   children (Interop/java (.toList list 10))]
               (merge (if-let [value (from-option option)]
                        {:value value})
                      (if (pos? depth)
                        {:children (->> (for [child children]
                                          (rec child (dec depth)))
                                        (remove nil?)
                                        distinct)}))))]
     (rec (.. g run (apply (Size. size) seed)) 2))))
0.2s
Clojure
urchin.core/shrink-tree

In the follow example we can see how Hedgehog shrinks a pair of Booleans. (true, true) gets shrunk to (false, true), (true, false), and ultimately to (false, false).

(shrink-tree (tuple (boolean) (boolean)) 5)
0.1s
Clojure
Map {:value: List(2), :children: List(2)}

George Kendall shot the header photo.

Runtimes (2)