12: what about cycles?

(NOTE: this section digs into some intricate details of how Specmonstah works. It might be confusing and it could use improvement.)

Let's say that in your forum all posts reference a parent topic, and that topics reference their first post. That means that for every topic, its :first-post-id that should be set to a post's :id, and that's post's :topic-id must reference the topic's :id. What we got here is a good ol' fashioned cycle:

(ns reifyhealth.specmonstah-tutorial.12
  (:require [clojure.spec.alpha :as s]
            [clojure.spec.gen.alpha :as gen]
            [reifyhealth.specmonstah.core :as sm]
            [reifyhealth.specmonstah.spec-gen :as sg]))

(def id-seq (atom 0))
;; This spec uses a generated such that each time a value is generated
;; it returns the incremented value of the atom id-seq
(s/def ::id (s/with-gen pos-int?
              #(gen/fmap (fn [_] (swap! id-seq inc))
                         (gen/return nil))))
(s/def ::topic-id ::id)
(s/def ::first-post-id ::id)

(s/def ::post (s/keys :req-un [::id ::topic-id]))
(s/def ::topic (s/keys :req-un [::id ::first-post-id]))

(def schema
  {:topic {:prefix    :t
           :spec      ::topic
           :relations {:first-post-id [:post :id]}
           :conform   {:cycle-keys #{:first-post-id}}}
   :post  {:prefix      :p
           :relations   {:topic-id [:topic :id]}
           :constraints {:topic-id #{:required}}
           :spec        ::post}})

(defn ex-01
  []
  (sm/view (sm/add-ents {:schema schema} {:post [[3]]})))
  
(ex-01)

behold! a cycle!

This graph shows how the ents are related: :p0, :p1, and :p2 all reference the topic :t0, and :t0 references :p0.

One problem that could arise in this situation is that your database might have a foreign key constraint on the post table requiring that a post's :topic-id be NOT NULL and that it reference a topic that actually exists. The topic's :first-post-id might allow NULL values, but have the constraint that the field reference a post that actually exist. However, when cycles exist in a graph there's no way to know which of the two nodes in the cycle should come first. How do we make sure that Specmonstah does the following?

1. Inserts a :topic without a value for :first-post-id

2. Inserts a :post that references the :topic

3. Performs an update on the :topic to set it's :first-post-id to the :post's :id

There are two parts to solving this problem. The first is to ensure that ents are sorted correctly for visiting functions. Since you can't topologically sort a cycle, we need some way to tell Specmonstah how to get from a graph with a cycle to a graph without one. We do that with the :required constraint. Have another look at the schema:

(def schema
  {:topic {:prefix    :t
           :spec      ::topic
           :relations {:first-post-id [:post :id]}
           :conform   {:cycle-keys #{:first-post-id}}}
   :post  {:prefix      :p
           :relations   {:topic-id [:topic :id]}
           :constraints {:topic-id #{:required}}
           :spec        ::post}})

You can see that the the :post definition includes :constraints {:topic-id #{:required}}. This is how you tell specmonstah, "Make sure that the :topic that this :topic-id refers to gets visited before this :post". Internally, this instructs Specmonstah to create a temporary graph where the directed edges from topics to posts are removed, and then topologically sort that graph. You can see it at work:

(defn ex-02
  "Shows that `:required` results in correct order"
  []
  (-> (sm/add-ents {:schema schema} {:post [[3]]})
      (sm/visit-ents :print (fn [_ {:keys [ent-name]}] (prn ent-name))))
  nil)
(ex-02)
=>
:t0
:p2
:p1
:p0

The second part to solving this problem is to break your visiting function up into multiple functions:

(def database (atom []))

(defn insert
  "When inserting records, remove any `:cycle-keys` because those keys
  will reference records that haven't been inserted yet."
  [db {:keys [ent-name ent-type visit-query-opts spec-gen schema-opts]}]
  (let [cycle-keys (into (:cycle-keys schema-opts) (:cycle-keys visit-query-opts))
        record     (apply dissoc spec-gen cycle-keys)]
    (swap! database conj [:insert ent-name record])))

(defn update-keys
  "Perform an 'update', setting all cycle keys to the correct value now
  that the referenced record exists"
  [db {:keys [ent-name ent-type visit-query-opts spec-gen schema-opts]}]
  (let [cycle-keys (into (:cycle-keys schema-opts) (:cycle-keys visit-query-opts))]
    (when (seq cycle-keys)
      (swap! database conj [:update ent-name (select-keys spec-gen cycle-keys)]))))

(def conform [insert update-keys])

(defn ex-03
  []
  (reset! database [])
  (reset! id-seq 0)
  (-> (sg/ent-db-spec-gen {:schema schema} {:post [[3]]})
      (sm/visit-ents :conform conform))
  @database)

(ex-03) ; =>
[[:insert :t0 {:id 1}]
 [:insert :p2 {:id 3, :topic-id 1}]
 [:insert :p1 {:id 5, :topic-id 1}]
 [:insert :p0 {:id 7, :topic-id 1}]
 [:update :t0 {:first-post-id 7}]]

Here we're creating a visiting "function" named conform which is actually a vector of functions. The insert function is applied to all ents in topsort order, then the update-keys function is applied to ents in topsort order. You can see that :t0 is "inserted" without a :first-post-id, and then after all records have been inserted :t0 is "updated", setting its :first-post-id.

This introduces one more question: How does the visiting function know to leave out :first-post-id when the insert function is applied, and add it when the update-keys function is applied?

The answer has multiple parts. First, let's look at the schema again:

(def schema
  {:topic {:prefix    :t
           :spec      ::topic
           :relations {:first-post-id [:post :id]}
           :conform   {:cycle-keys #{:first-post-id}}}
   :post  {:prefix      :p
           :relations   {:topic-id [:topic :id]}
           :constraints {:topic-id #{:required}}
           :spec        ::post}})

Notice the :conform key in :topic schema. The :conform key doesn't have any special meaning; we name it to match the visiting key for the conform visiting function. When the conform visiting function is applied, the value of the :conform key is passed in under the :schema-opts key. You can see that the insert function uses this:

(defn insert
  "When inserting records, remove any `:cycle-keys` because those keys
  will reference records that haven't been inserted yet."
  [db {:keys [ent-name ent-type visit-query-opts spec-gen schema-opts]}]
  (let [cycle-keys (into (:cycle-keys schema-opts) (:cycle-keys visit-query-opts))
        record     (apply dissoc spec-gen cycle-keys)]
    (swap! database conj [:insert ent-name record])))

The insert function creates the record to be inserted by dissocing any keys found in :cycle-keys of schema-opts.