output.txt

Tree: {:version :a, :state :enabled, :parent nil}
Live: #{:a}
Shadow: #{}

Tree: {:version :b, :state :disabled, :parent :a}
      {:version :a, :state :enabled, :parent nil}
Live: #{}
Shadow: #{}

Tree: {:version :b, :state :shadow, :parent :a}
      {:version :c, :state :disabled, :parent :a}
      {:version :a, :state :enabled, :parent nil}
Live: #{}
Shadow: #{:b}

Tree: {:version :c, :state :shadow-disabled, :parent :b}
      {:version :b, :state :shadow, :parent :a}
      {:version :a, :state :enabled, :parent nil}
Live: #{:a}
Shadow: #{}

Tree: {:version :b, :state :shadow, :parent :a}
      {:version :c, :state :disabled, :parent :a}
      {:version :a, :state :enabled, :parent nil}
Live: #{}
Shadow: #{:b}

Tree: {:version :b, :state :disabled, :parent :a}
      {:version :c, :state :enabled, :parent :b}
      {:version :a, :state :enabled, :parent nil}
Live: #{:c}
Shadow: #{}

Tree: {:version :d, :state :shadow, :parent :a}
      {:version :b, :state :shadow, :parent :a}
      {:version :c, :state :shadow, :parent :b}
      {:version :a, :state :enabled, :parent nil}
Live: #{:a}
Shadow: #{:c :b :d}

version-tree.clj

(def enabled
  #{{:version :a
     :state :enabled
     :parent nil}})

(def disabled
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :disabled
     :parent :a}})

(def shadow-then-disabled
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :shadow
     :parent :a}
    {:version :c
     :state :disabled
     :parent :a}})

(def enabled-and-no-shadow
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :shadow
     :parent :a}
    {:version :c
     :state :shadow-disabled
     :parent :b}})

(def disabled-and-shadow
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :shadow
     :parent :a}
    {:version :c
     :state :disabled
     :parent :a}})


(def enabled-after-disabled
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :disabled
     :parent :a}
    {:version :c
     :state :enabled
     :parent :b}})

(def lots-of-shadows
  #{{:version :a
     :state :enabled
     :parent nil}
    {:version :b
     :state :shadow
     :parent :a}
    {:version :c
     :state :shadow
     :parent :b}
    {:version :d
     :state :shadow
     :parent :a}})

;;;;;;;;
;; functions to transform the tree:
;;
;;   - from an adjacency list of nodes pointing to their parents
;;     (emulating immutable documents in mongo),
;;   - to a map of nodes which include a list of their children
;;
;; this allows an easier top-down walk of the version tree
;; there's probably a better way to do this

;; go from set of nodes which point to their parent
;; to a map of node-id -> set of node children ids
(defn find-children [tree]
  (reduce (fn [acc node]
            (assoc acc
                   (:parent node)
                   (conj
                    (get acc (:parent node) #{})
                    (:version node))))
          {}
          tree))

;; take the adjacency list of nodes and the map returned from
;; find-children, augment each node with a set of its children and
;; return as a map of version->node
(defn add-children-to-tree [tree child-map]
  (reduce (fn [acc node]
            (assoc acc (:version node) node))
          {}
          (map (fn [node]
                 (assoc node :children (get child-map (:version node))))
               tree)))



;;;;;;;;;;
;; functions to walk the tree (as returned from add-children-to-tree)
;;
;; two mutually-recursive functions do this. the first one (the entry
;; point to the walk) looks at a node and, based on the
;; :state on that node, calls walk-children with an updated set of
;; live versions or shadow-versions.
;;
(declare walk-children) ;; gotta declare since `collect-versions`
                        ;; calls this without it having been defined

;; returns a pair: [set-of-enabled-versions, set-of-shadow-versions]
(defn collect-versions [tree-map current-node live-versions shadow-versions]
  (let [[updated-live-versions updated-shadow-versions]
        (case (:state current-node)
          :enabled [(conj live-versions (:version current-node))
                    shadow-versions]
          :disabled [(disj live-versions (:parent current-node))
                     shadow-versions]
          :shadow [live-versions
                   (conj shadow-versions (:version current-node))]
          :shadow-disabled [live-versions
                            (disj shadow-versions (:parent current-node))])]
    (walk-children
     tree-map current-node
     updated-live-versions
     updated-shadow-versions)))

;; the second function takes a node and the current set of live and
;; shadow versions, and calls collect-version for each child on the
;; current node, accumulating the state of the live and shadow
;; versions all the while
;; returns a pair: [set-of-enabled-versions, set-of-shadow-versions]
(defn walk-children [tree-map current-node new-live-versions new-shadow-versions]
  (reduce (fn [[live-versions shadow-versions] child-node]
            (collect-versions
             tree-map
             (get tree-map child-node)
             live-versions
             shadow-versions))
          [new-live-versions new-shadow-versions]
          (:children current-node)))


;;;;;;;
;; finally, some functions to kick off the process
;;
;; a little helper: given the result of add-children-to-tree,
;; return the root
(defn find-root [tree-map]
  (:version (first (filter #(nil? (:parent %)) (vals tree-map)))))

;; the entry point to the whole thing: given a tree (adjacency list of
;; immutable version document from Mongo), return two sets: the set of
;; enabled versions (which we can assert is length 0 or 1) and the set of
;; enabled shadow versions.
;;
;; this fn just kicks off the recursive walk of the tree
(defn collect [tree]
  (let [tree-map (add-children-to-tree
                  tree
                  (find-children tree))
        root     (get tree-map (find-root tree-map))]
    (collect-versions tree-map root #{} #{})))


;; and, run all the example trees at the top
(doall (map (fn [tree]
              (let [[live shadow]  (collect tree)]
                (println)
                (println (str "Tree: " (clojure.string/join "\n      " tree)))
                (println (str "Live: " live))
                (println (str "Shadow: " shadow))))
            [enabled disabled shadow-then-disabled enabled-and-no-shadow
             disabled-and-shadow enabled-after-disabled lots-of-shadows]))