-
Notifications
You must be signed in to change notification settings - Fork 0
/
analysis.cljc
163 lines (139 loc) · 6.48 KB
/
analysis.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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
(ns mapdag.analysis
"'Static' analysis of mapdag graphs - in particular validation."
(:require [mapdag.step :as mdg]))
(defn- dependency-cycle-path
[step-name steps-trace]
(->> steps-trace
(take-while #(not= step-name %))
(cons step-name)
(reverse)
(into [step-name])))
(defn- dependency-cycle-str
[step-name steps-trace]
(->> (dependency-cycle-path step-name steps-trace)
(map pr-str)
(interpose " -> ")
(apply str)))
(defn validate-shape
"Performs basic 'data shape/types' validation on the given graph, throwing an error if an invariant violation is found, otherwise returning the graph unmodified.
Some kinds of errors that won't be detected:
- incorrect arity of :mapdag.step/compute-fn
- dependencies-related invariant violations, such as dependency cycles or missing keys."
[graph]
(when-not (map? graph)
(throw
(ex-info
"graph must be a map."
{:mapdag.error/reason :mapdag.errors/invalid-graph
:graph graph})))
(run!
(fn [[step-name step]]
(when-not (map? step)
(throw
(ex-info
(str "step " (pr-str step-name) " must be a map.")
{:mapdag.error/reason :mapdag.errors/invalid-graph
:mapdag.step/name step-name
:mapdag/step step})))
(let [dps (::mdg/deps step)]
(when-not (sequential? dps)
(throw
(ex-info
(str "step " (pr-str step-name)
" must contain a sequence at key " (pr-str ::mdg/deps))
{:mapdag.error/reason :mapdag.errors/invalid-graph
:mapdag.step/name step-name
:mapdag/step step}))))
(let [cfn (::mdg/compute-fn step)]
(when-not (fn? cfn)
(throw
(ex-info
(str "step " (pr-str step-name)
" must contain a function at key " (pr-str ::mdg/compute-fn))
{:mapdag.error/reason :mapdag.errors/invalid-graph
:mapdag.step/name step-name
:mapdag/step step})))))
graph)
graph)
(defn validate-dependency-links
"Performs validation on the dependency structure of the given graph, throwing an error if an invariant violation is found, otherwise returning the graph unmodified.
The only key required in Step maps for this validation is :mapdag.step/deps, so this function is suitable for validating partially-constructed graphs.
See the documentation of #'validate for the additional arguments."
[graph input-keys-or-false output-keys-or-false]
(let [start-keys (if (false? output-keys-or-false)
(keys graph)
output-keys-or-false)
check-inputs? (not (false? input-keys-or-false))
graph1 (-> {}
(into graph)
(into
(map (juxt
identity
(constantly {::mdg/deps []}))
(or input-keys-or-false []))))]
(letfn [(check-key [acc step-name steps-trace]
(if (contains? acc step-name)
(let [step-v (get acc step-name)]
(if (list? step-v)
(throw
(ex-info
(str "Found dependency cycle: "
" " (dependency-cycle-str step-name steps-trace))
{:mapdag.error/reason :mapdag.errors/dependency-cycle ;; INTRO This error indicates a dependency cycle amongst DAG steps. (Val, 20 May 2020)
:mapdag.trace/deps-cycle (dependency-cycle-path step-name steps-trace)
:mapdag.step/name step-name}))
acc))
(if-some [[_ step] (find graph1 step-name)]
(let [st1 (conj steps-trace step-name)]
(assoc
(reduce
(fn [acc step-name]
(check-key acc step-name st1))
(assoc acc
step-name
(conj steps-trace step-name))
(::mdg/deps step))
step-name :checked))
(if check-inputs?
(throw
(ex-info
(str "Missing step or input: " (pr-str step-name))
{:mapdag.error/reason :mapdag.errors/missing-step-or-input ;; INTRO This error indicates that some of the steps or inputs required for the computations are not present. Note that given the API semantics, it's impossible to distinguish between a missing input and a missing step. (Val, 20 May 2020)
:mapdag.step/name step-name}))
(assoc acc step-name :checked)))))]
(reduce
(fn [acc step-name]
(check-key acc step-name (list)))
{}
start-keys)))
graph)
(defn validate-graph
"Performs validation on the given mapdag Graph, throwing an error if an invariant violation is found, otherwise returning the graph unmodified.
The other arguments can be used to limit what the validation will cover:
- if `input-keys-or-false` is a sequence of input names, will check if some inputs or steps are missing.
Otherwise it argument should be set to the boolean `false` (not `nil`, which would be interpreted as an empty sequence.).
- if `output-keys-or-false` is a sequence of step names, will only check for dependency cycles or missing steps on the sub-graph induced by the ancestors of these steps.
Otherwise it argument should be set to the boolean `false` (not `nil`, which would be interpreted as an empty sequence.).
When not-false, these arguments lead to tolerating pathological properties that don't get in the way of the computation at hands:
- dependency cycles that are outside of the necessary steps, or broken by the inputs, will not be reported.
- missing steps outside of the necessary steps won't be reported."
[graph input-keys-or-false output-keys-or-false]
(validate-shape graph)
(validate-dependency-links graph input-keys-or-false output-keys-or-false)
graph)
(comment
(validate-graph
{:a (mdg/step [:b] (constantly nil))
:b (mdg/step [:c] (constantly nil))
:c (mdg/step [:d] (constantly nil))
:d (mdg/step [:b] (constantly nil))}
nil nil)
;Found dependency cycle: :b -> :c -> :d -> :b
(validate-graph
{:a (mdg/step [:b] (constantly nil))
:b (mdg/step [:c] (constantly nil))
:c (mdg/step [:d] (constantly nil))}
{}
nil)
;Missing step or input: :d
*e)