How do I create a test.check generator for a sequence of actions in a constrained order?

Question

(require '[clojure.test.check.generators :as gen])

(def ACTIONS
  {:create-new-user #{}
   :edit-user #{:create-new-user}
   :create-new-board #{:create-new-user}
   :edit-board #{:create-new-board}
   :create-new-anonymous-comment #{:create-new-board}
   :create-new-signed-comment #{:create-new-board}
   :edit-comment-text #{:create-new-anonymous-comment :create-new-signed-comment}
   :edit-comment-text-and-flip-anonymity #{:create-new-anonymous-comment :create-new-signed-comment}
   :flip-anonymity #{:create-new-anonymous-comment :create-new-signed-comment}
   :vote-comment-up #{:create-new-anonymous-comment :create-new-signed-comment}
   :vote-comment-down #{:create-new-anonymous-comment :create-new-signed-comment}})

(def actions (-> ACTIONS keys vec gen/elements gen/vector))

(defn filter-actions-into-logical-order [as]
  (let [seen (atom #{})]
    (filter
     (fn [v]
       (let [required (get ACTIONS v)
             valid? (or (some? (some required @seen)) 
                        (and (empty? @seen) (= v :create-new-user)))]
         (when valid?
           (swap! seen conj v)
           true)))
     as)))

(def ordered-actions (gen/fmap #(-> % filter-actions-into-logical-order vec)  actions))

As an example of the two generators:

# (last (gen/sample actions 100))
[:edit-user :vote-comment-down :flip-anonymity :vote-comment-down :vote-comment-down :vote-comment-up :edit-user :create-new-anonymous-comment :edit-board :create-new-signed-comment :vote-comment-up :edit-comment-text-and-flip-anonymity :edit-user :create-new-signed-comment :edit-user :edit-user :vote-comment-down :edit-user :vote-comment-down :create-new-user :vote-comment-down :create-new-user :create-new-user :edit-comment-text-and-flip-anonymity :create-new-user :edit-comment-text-and-flip-anonymity :create-new-anonymous-comment :edit-comment-text :create-new-board :vote-comment-down :flip-anonymity :create-new-signed-comment :vote-comment-up :create-new-user :create-new-signed-comment :edit-user :create-new-user :create-new-board :vote-comment-down :create-new-board :create-new-board :create-new-board :edit-board :edit-comment-text-and-flip-anonymity :edit-user :edit-comment-text :create-new-signed-comment :vote-comment-up :edit-comment-text-and-flip-anonymity :flip-anonymity :create-new-anonymous-comment :create-new-anonymous-comment :edit-board :create-new-signed-comment :edit-comment-text-and-flip-anonymity :edit-board :vote-comment-up :edit-comment-text :create-new-board :edit-comment-text-and-flip-anonymity :create-new-board :vote-comment-down :edit-comment-text-and-flip-anonymity :vote-comment-up :create-new-user :vote-comment-up :edit-comment-text :edit-board :edit-comment-text-and-flip-anonymity :flip-anonymity :edit-board :create-new-anonymous-comment :flip-anonymity :create-new-signed-comment :edit-user :edit-comment-text-and-flip-anonymity :edit-comment-text :edit-comment-text :create-new-user :flip-anonymity :edit-user :vote-comment-up :edit-user :create-new-user :edit-comment-text :edit-comment-text :flip-anonymity :edit-comment-text :edit-board :flip-anonymity :edit-board :edit-comment-text :edit-user :create-new-user :flip-anonymity]


# (last (gen/sample ordered-actions 100))
[:create-new-user :edit-user :edit-user :create-new-board :edit-board :edit-user :create-new-anonymous-comment :edit-comment-text :edit-board :edit-user :edit-user :vote-comment-up :edit-comment-text :create-new-signed-comment :edit-comment-text :create-new-board :edit-comment-text :edit-comment-text :edit-comment-text :vote-comment-up :vote-comment-up :edit-board :edit-comment-text-and-flip-anonymity :create-new-signed-comment :create-new-anonymous-comment :create-new-signed-comment :edit-user :create-new-anonymous-comment :edit-board :create-new-board :create-new-anonymous-comment :create-new-board :flip-anonymity :create-new-anonymous-comment :edit-board :vote-comment-up :vote-comment-down :edit-board :edit-comment-text :edit-user :edit-comment-text :flip-anonymity :create-new-signed-comment :vote-comment-up :edit-comment-text-and-flip-anonymity :vote-comment-up :create-new-signed-comment :edit-comment-text :create-new-signed-comment :create-new-anonymous-comment :edit-board :create-new-anonymous-comment]

ACTIONS is a map where the key is the name of the action, and the value is the (OR based) dependency for that action. As an example, you must first :create-new-user before you can do anything, you must :create-new-board before you can :edit-board, and you must have at least one :create-new-*-comment before you can :edit-comment-text.

The code above seems to work, but it is ugly. 1) I don't like how filter-actions-into-logical-order code has to have a specific exception for :create-new-user. 2) I don't like that I am basically taking the list of random actions, and filtering it down until the actions make ordered sense.

I am wondering how others would generate a sequence of actions like this using test.check? Surely there must be a way to do so using only generators?

Answer 1

Well, filter-into-logical-order could arguably be cleaner with a switch to reduce

(defn filter-into-logical-order [as]
  (last (reduce
         (fn [[seen accepted-as] action]
           (let[needed (get ACTIONS action)]
             (if (or (empty? needed) (some seen needed))
               [(conj seen action) (conj accepted-as action)]
               [seen accepted-as]))
           )
         [#{} []]
         as)))

but that still puts out about 30% empty vectors for me and it's not a generator. I'm not sure the documented combinators actually support what you want, though. gen/vector does not appear to support handing a vector-in-construction to its inner generator so it can know what values are allowed, which is kinda the structure your requirements need.

Answer 2

It's not too hard to do this with a recursive generator that uses gen/bind (e.g., first generate the size of your list of actions, then use recursion over that size with gen/bind so that you have the previously generated actions at each step). The big downside to this approach is that gen/bind works rather poorly with shrinking, and so you're likely to end up with long sequences of actions that can't shrink almost at all.

I'd really like to come up with something better for this.