-
Notifications
You must be signed in to change notification settings - Fork 109
/
dataflow.cljc
34 lines (33 loc) · 1.3 KB
/
dataflow.cljc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
(ns ^{:doc "Dataflow analysis framework"
:author "Aysylu Greenberg"}
loom.dataflow
(:require [loom.graph :as g]))
(defn dataflow-analysis
"Performs dataflow analysis using iterative worklist-based algorithm.
Must provide the graph and its start node, join and transfer functions."
[{:keys [start graph join transfer]}]
(let [start (cond
(set? start) start
(and (coll? start) (not (map? start))) (set start)
:else #{start})]
(loop [out-values {}
queue (into
#?(:clj clojure.lang.PersistentQueue/EMPTY
:cljs #queue [])
start)]
(let [node (peek queue)
worklist (pop queue)
in-value (join (mapv out-values (g/predecessors graph node)))
out (transfer node in-value)
update? (not= out (get out-values node))
out-values (if update?
(assoc out-values node out)
out-values)
workset (set worklist)
worklist (if update?
(->> (g/successors graph node)
(remove workset)
(into worklist)))]
(if (seq worklist)
(recur out-values worklist)
out-values)))))