ziv@2275
|
1 structure Sqlcache (* DEBUG :> SQLCACHE *) = struct
|
ziv@2209
|
2
|
ziv@2209
|
3 open Mono
|
ziv@2209
|
4
|
ziv@2209
|
5 structure IS = IntBinarySet
|
ziv@2209
|
6 structure IM = IntBinaryMap
|
ziv@2213
|
7 structure SK = struct type ord_key = string val compare = String.compare end
|
ziv@2213
|
8 structure SS = BinarySetFn(SK)
|
ziv@2213
|
9 structure SM = BinaryMapFn(SK)
|
ziv@2213
|
10 structure SIMM = MultimapFn(structure KeyMap = SM structure ValSet = IS)
|
ziv@2209
|
11
|
ziv@2274
|
12 (* ASK: how do we deal with heap reallocation? *)
|
ziv@2274
|
13
|
ziv@2274
|
14 fun id x = x
|
ziv@2274
|
15
|
ziv@2250
|
16 fun iterate f n x = if n < 0
|
ziv@2250
|
17 then raise Fail "Can't iterate function negative number of times."
|
ziv@2250
|
18 else if n = 0
|
ziv@2250
|
19 then x
|
ziv@2250
|
20 else iterate f (n-1) (f x)
|
ziv@2250
|
21
|
ziv@2268
|
22 (* Filled in by [addFlushing]. *)
|
ziv@2268
|
23 val ffiInfoRef : {index : int, params : int} list ref = ref []
|
ziv@2209
|
24
|
ziv@2268
|
25 fun resetFfiInfo () = ffiInfoRef := []
|
ziv@2227
|
26
|
ziv@2268
|
27 fun getFfiInfo () = !ffiInfoRef
|
ziv@2213
|
28
|
ziv@2215
|
29 (* Some FFIs have writing as their only effect, which the caching records. *)
|
ziv@2215
|
30 val ffiEffectful =
|
ziv@2223
|
31 (* ASK: how can this be less hard-coded? *)
|
ziv@2215
|
32 let
|
ziv@2258
|
33 val okayWrites = SS.fromList ["htmlifyInt_w",
|
ziv@2258
|
34 "htmlifyFloat_w",
|
ziv@2258
|
35 "htmlifyString_w",
|
ziv@2258
|
36 "htmlifyBool_w",
|
ziv@2258
|
37 "htmlifyTime_w",
|
ziv@2258
|
38 "attrifyInt_w",
|
ziv@2258
|
39 "attrifyFloat_w",
|
ziv@2258
|
40 "attrifyString_w",
|
ziv@2258
|
41 "attrifyChar_w",
|
ziv@2258
|
42 "urlifyInt_w",
|
ziv@2258
|
43 "urlifyFloat_w",
|
ziv@2258
|
44 "urlifyString_w",
|
ziv@2258
|
45 "urlifyBool_w",
|
ziv@2258
|
46 "urlifyChannel_w"]
|
ziv@2215
|
47 in
|
ziv@2265
|
48 (* ASK: is it okay to hardcode Sqlcache functions as effectful? *)
|
ziv@2215
|
49 fn (m, f) => Settings.isEffectful (m, f)
|
ziv@2258
|
50 andalso not (m = "Basis" andalso SS.member (okayWrites, f))
|
ziv@2215
|
51 end
|
ziv@2215
|
52
|
ziv@2234
|
53 val cache = ref LruCache.cache
|
ziv@2233
|
54 fun setCache c = cache := c
|
ziv@2233
|
55 fun getCache () = !cache
|
ziv@2233
|
56
|
ziv@2248
|
57 (* Used to have type context for local variables in MonoUtil functions. *)
|
ziv@2248
|
58 val doBind =
|
ziv@2262
|
59 fn (env, MonoUtil.Exp.RelE (x, t)) => MonoEnv.pushERel env x t NONE
|
ziv@2262
|
60 | (env, MonoUtil.Exp.NamedE (x, n, t, eo, s)) => MonoEnv.pushENamed env x n t eo s
|
ziv@2262
|
61 | (env, MonoUtil.Exp.Datatype (x, n, cs)) => MonoEnv.pushDatatype env x n cs
|
ziv@2215
|
62
|
ziv@2271
|
63 val dummyLoc = ErrorMsg.dummySpan
|
ziv@2271
|
64
|
ziv@2271
|
65
|
ziv@2271
|
66 (*********************)
|
ziv@2271
|
67 (* General Utilities *)
|
ziv@2271
|
68 (*********************)
|
ziv@2266
|
69
|
ziv@2266
|
70 (* From the MLton wiki. *)
|
ziv@2273
|
71 infix 3 <\ fun x <\ f = fn y => f (x, y) (* Left section *)
|
ziv@2273
|
72 infix 3 \> fun f \> y = f y (* Left application *)
|
ziv@2266
|
73
|
ziv@2271
|
74 fun mapFst f (x, y) = (f x, y)
|
ziv@2271
|
75
|
ziv@2266
|
76 (* Option monad. *)
|
ziv@2266
|
77 fun obind (x, f) = Option.mapPartial f x
|
ziv@2266
|
78 fun oguard (b, x) = if b then x else NONE
|
ziv@2271
|
79 fun omap f = fn SOME x => SOME (f x) | _ => NONE
|
ziv@2271
|
80 fun omap2 f = fn (SOME x, SOME y) => SOME (f (x,y)) | _ => NONE
|
ziv@2271
|
81 fun osequence ys = List.foldr (omap2 op::) (SOME []) ys
|
ziv@2248
|
82
|
ziv@2271
|
83 fun indexOf test =
|
ziv@2271
|
84 let
|
ziv@2271
|
85 fun f n =
|
ziv@2271
|
86 fn [] => NONE
|
ziv@2271
|
87 | (x::xs) => if test x then SOME n else f (n+1) xs
|
ziv@2271
|
88 in
|
ziv@2271
|
89 f 0
|
ziv@2271
|
90 end
|
ziv@2268
|
91
|
ziv@2248
|
92 (*******************)
|
ziv@2248
|
93 (* Effect Analysis *)
|
ziv@2248
|
94 (*******************)
|
ziv@2215
|
95
|
ziv@2216
|
96 (* Makes an exception for [EWrite] (which is recorded when caching). *)
|
ziv@2248
|
97 fun effectful (effs : IS.set) =
|
ziv@2215
|
98 let
|
ziv@2248
|
99 val isFunction =
|
ziv@2248
|
100 fn (TFun _, _) => true
|
ziv@2248
|
101 | _ => false
|
ziv@2250
|
102 fun doExp (env, e) =
|
ziv@2248
|
103 case e of
|
ziv@2248
|
104 EPrim _ => false
|
ziv@2248
|
105 (* For now: variables of function type might be effectful, but
|
ziv@2248
|
106 others are fully evaluated and are therefore not effectful. *)
|
ziv@2250
|
107 | ERel n => isFunction (#2 (MonoEnv.lookupERel env n))
|
ziv@2248
|
108 | ENamed n => IS.member (effs, n)
|
ziv@2248
|
109 | EFfi (m, f) => ffiEffectful (m, f)
|
ziv@2248
|
110 | EFfiApp (m, f, _) => ffiEffectful (m, f)
|
ziv@2248
|
111 (* These aren't effectful unless a subexpression is. *)
|
ziv@2248
|
112 | ECon _ => false
|
ziv@2248
|
113 | ENone _ => false
|
ziv@2248
|
114 | ESome _ => false
|
ziv@2248
|
115 | EApp _ => false
|
ziv@2248
|
116 | EAbs _ => false
|
ziv@2248
|
117 | EUnop _ => false
|
ziv@2248
|
118 | EBinop _ => false
|
ziv@2248
|
119 | ERecord _ => false
|
ziv@2248
|
120 | EField _ => false
|
ziv@2248
|
121 | ECase _ => false
|
ziv@2248
|
122 | EStrcat _ => false
|
ziv@2248
|
123 (* EWrite is a special exception because we record writes when caching. *)
|
ziv@2248
|
124 | EWrite _ => false
|
ziv@2248
|
125 | ESeq _ => false
|
ziv@2248
|
126 | ELet _ => false
|
ziv@2250
|
127 | EUnurlify _ => false
|
ziv@2248
|
128 (* ASK: what should we do about closures? *)
|
ziv@2248
|
129 (* Everything else is some sort of effect. We could flip this and
|
ziv@2248
|
130 explicitly list bits of Mono that are effectful, but this is
|
ziv@2248
|
131 conservatively robust to future changes (however unlikely). *)
|
ziv@2248
|
132 | _ => true
|
ziv@2215
|
133 in
|
ziv@2248
|
134 MonoUtil.Exp.existsB {typ = fn _ => false, exp = doExp, bind = doBind}
|
ziv@2215
|
135 end
|
ziv@2215
|
136
|
ziv@2215
|
137 (* TODO: test this. *)
|
ziv@2252
|
138 fun effectfulDecls (decls, _) =
|
ziv@2215
|
139 let
|
ziv@2248
|
140 fun doVal ((_, name, _, e, _), effs) =
|
ziv@2250
|
141 if effectful effs MonoEnv.empty e
|
ziv@2248
|
142 then IS.add (effs, name)
|
ziv@2248
|
143 else effs
|
ziv@2215
|
144 val doDecl =
|
ziv@2248
|
145 fn ((DVal v, _), effs) => doVal (v, effs)
|
ziv@2248
|
146 (* Repeat the list of declarations a number of times equal to its size,
|
ziv@2248
|
147 making sure effectfulness propagates everywhere it should. This is
|
ziv@2248
|
148 analagous to the Bellman-Ford algorithm. *)
|
ziv@2248
|
149 | ((DValRec vs, _), effs) =>
|
ziv@2248
|
150 List.foldl doVal effs (List.concat (List.map (fn _ => vs) vs))
|
ziv@2215
|
151 (* ASK: any other cases? *)
|
ziv@2248
|
152 | (_, effs) => effs
|
ziv@2215
|
153 in
|
ziv@2248
|
154 List.foldl doDecl IS.empty decls
|
ziv@2215
|
155 end
|
ziv@2215
|
156
|
ziv@2215
|
157
|
ziv@2248
|
158 (*********************************)
|
ziv@2248
|
159 (* Boolean Formula Normalization *)
|
ziv@2248
|
160 (*********************************)
|
ziv@2216
|
161
|
ziv@2234
|
162 datatype junctionType = Conj | Disj
|
ziv@2216
|
163
|
ziv@2216
|
164 datatype 'atom formula =
|
ziv@2216
|
165 Atom of 'atom
|
ziv@2216
|
166 | Negate of 'atom formula
|
ziv@2234
|
167 | Combo of junctionType * 'atom formula list
|
ziv@2216
|
168
|
ziv@2243
|
169 (* Guaranteed to have all negation pushed to the atoms. *)
|
ziv@2243
|
170 datatype 'atom formula' =
|
ziv@2243
|
171 Atom' of 'atom
|
ziv@2243
|
172 | Combo' of junctionType * 'atom formula' list
|
ziv@2243
|
173
|
ziv@2234
|
174 val flipJt = fn Conj => Disj | Disj => Conj
|
ziv@2216
|
175
|
ziv@2236
|
176 fun concatMap f xs = List.concat (map f xs)
|
ziv@2216
|
177
|
ziv@2216
|
178 val rec cartesianProduct : 'a list list -> 'a list list =
|
ziv@2216
|
179 fn [] => [[]]
|
ziv@2236
|
180 | (xs :: xss) => concatMap (fn ys => concatMap (fn x => [x :: ys]) xs)
|
ziv@2236
|
181 (cartesianProduct xss)
|
ziv@2216
|
182
|
ziv@2218
|
183 (* Pushes all negation to the atoms.*)
|
ziv@2244
|
184 fun pushNegate (normalizeAtom : bool * 'atom -> 'atom) (negating : bool) =
|
ziv@2244
|
185 fn Atom x => Atom' (normalizeAtom (negating, x))
|
ziv@2244
|
186 | Negate f => pushNegate normalizeAtom (not negating) f
|
ziv@2244
|
187 | Combo (j, fs) => Combo' (if negating then flipJt j else j,
|
ziv@2244
|
188 map (pushNegate normalizeAtom negating) fs)
|
ziv@2218
|
189
|
ziv@2218
|
190 val rec flatten =
|
ziv@2243
|
191 fn Combo' (_, [f]) => flatten f
|
ziv@2243
|
192 | Combo' (j, fs) =>
|
ziv@2243
|
193 Combo' (j, List.foldr (fn (f, acc) =>
|
ziv@2243
|
194 case f of
|
ziv@2243
|
195 Combo' (j', fs') =>
|
ziv@2243
|
196 if j = j' orelse length fs' = 1
|
ziv@2243
|
197 then fs' @ acc
|
ziv@2243
|
198 else f :: acc
|
ziv@2243
|
199 | _ => f :: acc)
|
ziv@2243
|
200 []
|
ziv@2243
|
201 (map flatten fs))
|
ziv@2218
|
202 | f => f
|
ziv@2218
|
203
|
ziv@2243
|
204 (* [simplify] operates on the desired normal form. E.g., if [junc] is [Disj],
|
ziv@2243
|
205 consider the list of lists to be a disjunction of conjunctions. *)
|
ziv@2237
|
206 fun normalize' (simplify : 'a list list -> 'a list list)
|
ziv@2235
|
207 (junc : junctionType) =
|
ziv@2216
|
208 let
|
ziv@2235
|
209 fun norm junc =
|
ziv@2237
|
210 simplify
|
ziv@2243
|
211 o (fn Atom' x => [[x]]
|
ziv@2243
|
212 | Combo' (j, fs) =>
|
ziv@2235
|
213 let
|
ziv@2236
|
214 val fss = map (norm junc) fs
|
ziv@2235
|
215 in
|
ziv@2236
|
216 if j = junc
|
ziv@2236
|
217 then List.concat fss
|
ziv@2236
|
218 else map List.concat (cartesianProduct fss)
|
ziv@2235
|
219 end)
|
ziv@2216
|
220 in
|
ziv@2235
|
221 norm junc
|
ziv@2216
|
222 end
|
ziv@2216
|
223
|
ziv@2244
|
224 fun normalize simplify normalizeAtom junc =
|
ziv@2243
|
225 normalize' simplify junc
|
ziv@2235
|
226 o flatten
|
ziv@2244
|
227 o pushNegate normalizeAtom false
|
ziv@2216
|
228
|
ziv@2221
|
229 fun mapFormula mf =
|
ziv@2221
|
230 fn Atom x => Atom (mf x)
|
ziv@2221
|
231 | Negate f => Negate (mapFormula mf f)
|
ziv@2235
|
232 | Combo (j, fs) => Combo (j, map (mapFormula mf) fs)
|
ziv@2216
|
233
|
ziv@2274
|
234 fun mapFormulaExps mf = mapFormula (fn (cmp, e1, e2) => (cmp, mf e1, mf e2))
|
ziv@2274
|
235
|
ziv@2230
|
236
|
ziv@2248
|
237 (****************)
|
ziv@2248
|
238 (* SQL Analysis *)
|
ziv@2248
|
239 (****************)
|
ziv@2213
|
240
|
ziv@2240
|
241 structure CmpKey = struct
|
ziv@2235
|
242
|
ziv@2235
|
243 type ord_key = Sql.cmp
|
ziv@2235
|
244
|
ziv@2235
|
245 val compare =
|
ziv@2235
|
246 fn (Sql.Eq, Sql.Eq) => EQUAL
|
ziv@2235
|
247 | (Sql.Eq, _) => LESS
|
ziv@2235
|
248 | (_, Sql.Eq) => GREATER
|
ziv@2235
|
249 | (Sql.Ne, Sql.Ne) => EQUAL
|
ziv@2235
|
250 | (Sql.Ne, _) => LESS
|
ziv@2235
|
251 | (_, Sql.Ne) => GREATER
|
ziv@2235
|
252 | (Sql.Lt, Sql.Lt) => EQUAL
|
ziv@2235
|
253 | (Sql.Lt, _) => LESS
|
ziv@2235
|
254 | (_, Sql.Lt) => GREATER
|
ziv@2235
|
255 | (Sql.Le, Sql.Le) => EQUAL
|
ziv@2235
|
256 | (Sql.Le, _) => LESS
|
ziv@2235
|
257 | (_, Sql.Le) => GREATER
|
ziv@2235
|
258 | (Sql.Gt, Sql.Gt) => EQUAL
|
ziv@2235
|
259 | (Sql.Gt, _) => LESS
|
ziv@2235
|
260 | (_, Sql.Gt) => GREATER
|
ziv@2235
|
261 | (Sql.Ge, Sql.Ge) => EQUAL
|
ziv@2235
|
262
|
ziv@2235
|
263 end
|
ziv@2235
|
264
|
ziv@2216
|
265 val rec chooseTwos : 'a list -> ('a * 'a) list =
|
ziv@2216
|
266 fn [] => []
|
ziv@2216
|
267 | x :: ys => map (fn y => (x, y)) ys @ chooseTwos ys
|
ziv@2213
|
268
|
ziv@2237
|
269 fun removeRedundant madeRedundantBy zs =
|
ziv@2237
|
270 let
|
ziv@2237
|
271 fun removeRedundant' (xs, ys) =
|
ziv@2237
|
272 case xs of
|
ziv@2237
|
273 [] => ys
|
ziv@2237
|
274 | x :: xs' =>
|
ziv@2237
|
275 removeRedundant' (xs',
|
ziv@2237
|
276 if List.exists (fn y => madeRedundantBy (x, y)) (xs' @ ys)
|
ziv@2237
|
277 then ys
|
ziv@2237
|
278 else x :: ys)
|
ziv@2237
|
279 in
|
ziv@2237
|
280 removeRedundant' (zs, [])
|
ziv@2237
|
281 end
|
ziv@2237
|
282
|
ziv@2216
|
283 datatype atomExp =
|
ziv@2216
|
284 QueryArg of int
|
ziv@2216
|
285 | DmlRel of int
|
ziv@2216
|
286 | Prim of Prim.t
|
ziv@2216
|
287 | Field of string * string
|
ziv@2216
|
288
|
ziv@2216
|
289 structure AtomExpKey : ORD_KEY = struct
|
ziv@2216
|
290
|
ziv@2234
|
291 type ord_key = atomExp
|
ziv@2216
|
292
|
ziv@2234
|
293 val compare =
|
ziv@2234
|
294 fn (QueryArg n1, QueryArg n2) => Int.compare (n1, n2)
|
ziv@2234
|
295 | (QueryArg _, _) => LESS
|
ziv@2234
|
296 | (_, QueryArg _) => GREATER
|
ziv@2234
|
297 | (DmlRel n1, DmlRel n2) => Int.compare (n1, n2)
|
ziv@2234
|
298 | (DmlRel _, _) => LESS
|
ziv@2234
|
299 | (_, DmlRel _) => GREATER
|
ziv@2234
|
300 | (Prim p1, Prim p2) => Prim.compare (p1, p2)
|
ziv@2234
|
301 | (Prim _, _) => LESS
|
ziv@2234
|
302 | (_, Prim _) => GREATER
|
ziv@2234
|
303 | (Field (t1, f1), Field (t2, f2)) =>
|
ziv@2234
|
304 case String.compare (t1, t2) of
|
ziv@2234
|
305 EQUAL => String.compare (f1, f2)
|
ziv@2234
|
306 | ord => ord
|
ziv@2216
|
307
|
ziv@2216
|
308 end
|
ziv@2216
|
309
|
ziv@2244
|
310 structure AtomOptionKey = OptionKeyFn(AtomExpKey)
|
ziv@2244
|
311
|
ziv@2271
|
312 val rec tablesOfQuery =
|
ziv@2271
|
313 fn Sql.Query1 {From = tablePairs, ...} => SS.fromList (map #1 tablePairs)
|
ziv@2271
|
314 | Sql.Union (q1, q2) => SS.union (tablesOfQuery q1, tablesOfQuery q2)
|
ziv@2271
|
315
|
ziv@2271
|
316 val tableOfDml =
|
ziv@2271
|
317 fn Sql.Insert (tab, _) => tab
|
ziv@2271
|
318 | Sql.Delete (tab, _) => tab
|
ziv@2271
|
319 | Sql.Update (tab, _, _) => tab
|
ziv@2271
|
320
|
ziv@2271
|
321 val freeVars =
|
ziv@2271
|
322 MonoUtil.Exp.foldB
|
ziv@2271
|
323 {typ = #2,
|
ziv@2271
|
324 exp = fn (bound, ERel n, vars) => if n < bound
|
ziv@2271
|
325 then vars
|
ziv@2271
|
326 else IS.add (vars, n - bound)
|
ziv@2271
|
327 | (_, _, vars) => vars,
|
ziv@2273
|
328 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1
|
ziv@2273
|
329 | (bound, _) => bound}
|
ziv@2271
|
330 0
|
ziv@2271
|
331 IS.empty
|
ziv@2271
|
332
|
ziv@2271
|
333 datatype unbind = Known of exp | Unknowns of int
|
ziv@2271
|
334
|
ziv@2273
|
335 datatype cacheArg = AsIs of exp | Urlify of exp
|
ziv@2273
|
336
|
ziv@2271
|
337 structure InvalInfo :> sig
|
ziv@2271
|
338 type t
|
ziv@2271
|
339 type state = {tableToIndices : SIMM.multimap,
|
ziv@2271
|
340 indexToInvalInfo : (t * int) IntBinaryMap.map,
|
ziv@2271
|
341 ffiInfo : {index : int, params : int} list,
|
ziv@2271
|
342 index : int}
|
ziv@2271
|
343 val empty : t
|
ziv@2271
|
344 val singleton : Sql.query -> t
|
ziv@2271
|
345 val query : t -> Sql.query
|
ziv@2273
|
346 val orderArgs : t * IS.set -> cacheArg list
|
ziv@2271
|
347 val unbind : t * unbind -> t option
|
ziv@2271
|
348 val union : t * t -> t
|
ziv@2271
|
349 val updateState : t * int * state -> state
|
ziv@2271
|
350 end = struct
|
ziv@2271
|
351
|
ziv@2273
|
352 datatype sqlArg = FreeVar of int | Sqlify of string * string * sqlArg * typ
|
ziv@2273
|
353
|
ziv@2273
|
354 type subst = sqlArg IM.map
|
ziv@2273
|
355
|
ziv@2273
|
356 (* TODO: store free variables as well? *)
|
ziv@2273
|
357 type t = (Sql.query * subst) list
|
ziv@2271
|
358
|
ziv@2271
|
359 type state = {tableToIndices : SIMM.multimap,
|
ziv@2271
|
360 indexToInvalInfo : (t * int) IntBinaryMap.map,
|
ziv@2271
|
361 ffiInfo : {index : int, params : int} list,
|
ziv@2271
|
362 index : int}
|
ziv@2271
|
363
|
ziv@2273
|
364 structure AM = BinaryMapFn(struct
|
ziv@2273
|
365 type ord_key = sqlArg
|
ziv@2273
|
366 (* Saw this on MLton wiki. *)
|
ziv@2273
|
367 fun ifNotEq (cmp, thunk) = case cmp of
|
ziv@2273
|
368 EQUAL => thunk ()
|
ziv@2273
|
369 | _ => cmp
|
ziv@2273
|
370 fun try f x () = f x
|
ziv@2273
|
371 val rec compare =
|
ziv@2273
|
372 fn (FreeVar n1, FreeVar n2) =>
|
ziv@2273
|
373 Int.compare (n1, n2)
|
ziv@2273
|
374 | (FreeVar _, _) => LESS
|
ziv@2273
|
375 | (_, FreeVar _) => GREATER
|
ziv@2273
|
376 | (Sqlify (m1, x1, arg1, t1), Sqlify (m2, x2, arg2, t2)) =>
|
ziv@2273
|
377 String.compare (m1, m2)
|
ziv@2273
|
378 <\ifNotEq\> try String.compare (x1, x2)
|
ziv@2273
|
379 <\ifNotEq\> try MonoUtil.Typ.compare (t1, t2)
|
ziv@2273
|
380 <\ifNotEq\> try compare (arg1, arg2)
|
ziv@2273
|
381 end)
|
ziv@2271
|
382
|
ziv@2273
|
383 (* Traversal Utilities *)
|
ziv@2273
|
384 (* TODO: get rid of unused ones. *)
|
ziv@2271
|
385
|
ziv@2271
|
386 (* Need lift', etc. because we don't have rank-2 polymorphism. This should
|
ziv@2273
|
387 probably use a functor (an ML one, not Haskell) but works for now. *)
|
ziv@2271
|
388 fun traverseSqexp (pure, _, lift, _, lift'', lift2, _) f =
|
ziv@2271
|
389 let
|
ziv@2271
|
390 val rec tr =
|
ziv@2271
|
391 fn Sql.SqNot se => lift Sql.SqNot (tr se)
|
ziv@2271
|
392 | Sql.Binop (r, se1, se2) =>
|
ziv@2271
|
393 lift2 (fn (trse1, trse2) => Sql.Binop (r, trse1, trse2)) (tr se1, tr se2)
|
ziv@2271
|
394 | Sql.SqKnown se => lift Sql.SqKnown (tr se)
|
ziv@2271
|
395 | Sql.Inj (e', loc) => lift'' (fn fe' => Sql.Inj (fe', loc)) (f e')
|
ziv@2271
|
396 | Sql.SqFunc (s, se) => lift (fn trse => Sql.SqFunc (s, trse)) (tr se)
|
ziv@2271
|
397 | se => pure se
|
ziv@2271
|
398 in
|
ziv@2271
|
399 tr
|
ziv@2271
|
400 end
|
ziv@2271
|
401
|
ziv@2271
|
402 fun traverseQuery (ops as (_, pure', _, lift', _, _, lift2')) f =
|
ziv@2271
|
403 let
|
ziv@2271
|
404 val rec mp =
|
ziv@2271
|
405 fn Sql.Query1 q =>
|
ziv@2271
|
406 (case #Where q of
|
ziv@2271
|
407 NONE => pure' (Sql.Query1 q)
|
ziv@2271
|
408 | SOME se =>
|
ziv@2271
|
409 lift' (fn mpse => Sql.Query1 {Select = #Select q,
|
ziv@2271
|
410 From = #From q,
|
ziv@2271
|
411 Where = SOME mpse})
|
ziv@2271
|
412 (traverseSqexp ops f se))
|
ziv@2271
|
413 | Sql.Union (q1, q2) => lift2' Sql.Union (mp q1, mp q2)
|
ziv@2271
|
414 in
|
ziv@2271
|
415 mp
|
ziv@2271
|
416 end
|
ziv@2271
|
417
|
ziv@2273
|
418 (* Include unused tuple elements in argument for convenience of using same
|
ziv@2273
|
419 argument as [traverseQuery]. *)
|
ziv@2273
|
420 fun traverseIM (pure, _, _, _, _, lift2, _) f =
|
ziv@2273
|
421 IM.foldli (fn (k, v, acc) => lift2 (fn (acc, w) => IM.insert (acc, k, w)) (acc, f (k,v)))
|
ziv@2273
|
422 (pure IM.empty)
|
ziv@2271
|
423
|
ziv@2273
|
424 fun traverseSubst (ops as (_, pure', lift, _, _, _, lift2')) f =
|
ziv@2273
|
425 let
|
ziv@2273
|
426 val rec mp =
|
ziv@2273
|
427 fn FreeVar n => f n
|
ziv@2273
|
428 | Sqlify (m, x, arg, t) => lift (fn mparg => Sqlify (m, x, mparg, t)) (mp arg)
|
ziv@2273
|
429 in
|
ziv@2273
|
430 traverseIM ops (fn (_, v) => mp v)
|
ziv@2273
|
431 end
|
ziv@2273
|
432
|
ziv@2273
|
433 fun monoidOps plus zero = (fn _ => zero, fn _ => zero,
|
ziv@2273
|
434 fn _ => fn x => x, fn _ => fn x => x, fn _ => fn x => x,
|
ziv@2273
|
435 fn _ => plus, fn _ => plus)
|
ziv@2273
|
436
|
ziv@2273
|
437 val optionOps = (SOME, SOME, omap, omap, omap, omap2, omap2)
|
ziv@2273
|
438
|
ziv@2273
|
439 fun foldMapQuery plus zero = traverseQuery (monoidOps plus zero)
|
ziv@2273
|
440 val omapQuery = traverseQuery optionOps
|
ziv@2273
|
441 fun foldMapIM plus zero = traverseIM (monoidOps plus zero)
|
ziv@2273
|
442 fun omapIM f = traverseIM optionOps f
|
ziv@2273
|
443 fun foldMapSubst plus zero = traverseSubst (monoidOps plus zero)
|
ziv@2273
|
444 fun omapSubst f = traverseSubst optionOps f
|
ziv@2271
|
445
|
ziv@2271
|
446 val varsOfQuery = foldMapQuery IS.union
|
ziv@2271
|
447 IS.empty
|
ziv@2271
|
448 (fn e' => freeVars (e', dummyLoc))
|
ziv@2271
|
449
|
ziv@2273
|
450 val varsOfSubst = foldMapSubst IS.union IS.empty IS.singleton
|
ziv@2273
|
451
|
ziv@2271
|
452 val varsOfList =
|
ziv@2271
|
453 fn [] => IS.empty
|
ziv@2271
|
454 | (q::qs) => varsOfQuery (List.foldl Sql.Union q qs)
|
ziv@2271
|
455
|
ziv@2273
|
456 (* Signature Implementation *)
|
ziv@2273
|
457
|
ziv@2273
|
458 val empty = []
|
ziv@2273
|
459
|
ziv@2273
|
460 fun singleton q = [(q, IS.foldl (fn (n, acc) => IM.insert (acc, n, FreeVar n))
|
ziv@2273
|
461 IM.empty
|
ziv@2273
|
462 (varsOfQuery q))]
|
ziv@2273
|
463
|
ziv@2273
|
464 val union = op@
|
ziv@2273
|
465
|
ziv@2273
|
466 fun sqlArgsMap (qs : t) =
|
ziv@2271
|
467 let
|
ziv@2273
|
468 val args =
|
ziv@2273
|
469 List.foldl (fn ((q, subst), acc) =>
|
ziv@2273
|
470 IM.foldl (fn (arg, acc) => AM.insert (acc, arg, ())) acc subst)
|
ziv@2273
|
471 AM.empty
|
ziv@2273
|
472 qs
|
ziv@2273
|
473 val countRef = ref (~1)
|
ziv@2273
|
474 fun count () = (countRef := !countRef + 1; !countRef)
|
ziv@2273
|
475 in
|
ziv@2273
|
476 (* Maps each arg to a different consecutive integer, starting from 0. *)
|
ziv@2273
|
477 AM.map count args
|
ziv@2273
|
478 end
|
ziv@2273
|
479
|
ziv@2273
|
480 val rec expOfArg =
|
ziv@2273
|
481 fn FreeVar n => (ERel n, dummyLoc)
|
ziv@2273
|
482 | Sqlify (m, x, arg, t) => (EFfiApp (m, x, [(expOfArg arg, t)]), dummyLoc)
|
ziv@2273
|
483
|
ziv@2273
|
484 fun orderArgs (qs : t, vars) =
|
ziv@2273
|
485 let
|
ziv@2273
|
486 fun erel n = (ERel n, dummyLoc)
|
ziv@2273
|
487 val argsMap = sqlArgsMap qs
|
ziv@2273
|
488 val args = map (expOfArg o #1) (AM.listItemsi argsMap)
|
ziv@2273
|
489 val invalVars = List.foldl IS.union IS.empty (map freeVars args)
|
ziv@2271
|
490 in
|
ziv@2271
|
491 (* Put arguments we might invalidate by first. *)
|
ziv@2273
|
492 map AsIs args
|
ziv@2273
|
493 (* TODO: make sure these variables are okay to remove from the argument list. *)
|
ziv@2273
|
494 @ map (Urlify o erel) (IS.listItems (IS.difference (vars, invalVars)))
|
ziv@2271
|
495 end
|
ziv@2271
|
496
|
ziv@2271
|
497 (* As a kludge, we rename the variables in the query to correspond to the
|
ziv@2271
|
498 argument of the cache they're part of. *)
|
ziv@2273
|
499 fun query (qs : t) =
|
ziv@2271
|
500 let
|
ziv@2273
|
501 val argsMap = sqlArgsMap qs
|
ziv@2273
|
502 fun substitute subst =
|
ziv@2273
|
503 fn ERel n => IM.find (subst, n)
|
ziv@2273
|
504 <\obind\>
|
ziv@2273
|
505 (fn arg =>
|
ziv@2273
|
506 AM.find (argsMap, arg)
|
ziv@2273
|
507 <\obind\>
|
ziv@2273
|
508 (fn n' => SOME (ERel n')))
|
ziv@2271
|
509 | _ => raise Match
|
ziv@2271
|
510 in
|
ziv@2273
|
511 case (map #1 qs) of
|
ziv@2273
|
512 (q :: qs) =>
|
ziv@2273
|
513 let
|
ziv@2273
|
514 val q = List.foldl Sql.Union q qs
|
ziv@2273
|
515 val ns = IS.listItems (varsOfQuery q)
|
ziv@2273
|
516 val rename =
|
ziv@2273
|
517 fn ERel n => omap ERel (indexOf (fn n' => n' = n) ns)
|
ziv@2273
|
518 | _ => raise Match
|
ziv@2273
|
519 in
|
ziv@2273
|
520 case omapQuery rename q of
|
ziv@2273
|
521 SOME q => q
|
ziv@2273
|
522 (* We should never get NONE because indexOf should never fail. *)
|
ziv@2273
|
523 | NONE => raise Match
|
ziv@2273
|
524 end
|
ziv@2273
|
525 (* We should never reach this case because [updateState] won't
|
ziv@2273
|
526 put anything in the state if there are no queries. *)
|
ziv@2273
|
527 | [] => raise Match
|
ziv@2271
|
528 end
|
ziv@2271
|
529
|
ziv@2273
|
530 val rec argOfExp =
|
ziv@2273
|
531 fn (ERel n, _) => SOME (FreeVar n)
|
ziv@2273
|
532 | (EFfiApp ("Basis", x, [(exp, t)]), _) =>
|
ziv@2273
|
533 if String.isPrefix "sqlify" x
|
ziv@2273
|
534 then omap (fn arg => Sqlify ("Basis", x, arg, t)) (argOfExp exp)
|
ziv@2273
|
535 else NONE
|
ziv@2273
|
536 | _ => NONE
|
ziv@2273
|
537
|
ziv@2273
|
538 val unbind1 =
|
ziv@2273
|
539 fn Known e =>
|
ziv@2273
|
540 let
|
ziv@2273
|
541 val replacement = argOfExp e
|
ziv@2273
|
542 in
|
ziv@2273
|
543 omapSubst (fn 0 => replacement
|
ziv@2273
|
544 | n => SOME (FreeVar (n-1)))
|
ziv@2273
|
545 end
|
ziv@2273
|
546 | Unknowns k => omapSubst (fn n => if n >= k then NONE else SOME (FreeVar (n-k)))
|
ziv@2271
|
547
|
ziv@2271
|
548 fun unbind (qs, ub) =
|
ziv@2271
|
549 case ub of
|
ziv@2271
|
550 (* Shortcut if nothing's changing. *)
|
ziv@2271
|
551 Unknowns 0 => SOME qs
|
ziv@2273
|
552 | _ => osequence (map (fn (q, subst) => unbind1 ub subst
|
ziv@2273
|
553 <\obind\>
|
ziv@2273
|
554 (fn subst' => SOME (q, subst'))) qs)
|
ziv@2271
|
555
|
ziv@2273
|
556 fun updateState (qs, numArgs, state as {index, ...} : state) =
|
ziv@2273
|
557 {tableToIndices = List.foldr (fn ((q, _), acc) =>
|
ziv@2271
|
558 SS.foldl (fn (tab, acc) =>
|
ziv@2271
|
559 SIMM.insert (acc, tab, index))
|
ziv@2271
|
560 acc
|
ziv@2271
|
561 (tablesOfQuery q))
|
ziv@2271
|
562 (#tableToIndices state)
|
ziv@2271
|
563 qs,
|
ziv@2271
|
564 indexToInvalInfo = IM.insert (#indexToInvalInfo state, index, (qs, numArgs)),
|
ziv@2271
|
565 ffiInfo = {index = index, params = numArgs} :: #ffiInfo state,
|
ziv@2271
|
566 index = index + 1}
|
ziv@2271
|
567
|
ziv@2271
|
568 end
|
ziv@2271
|
569
|
ziv@2275
|
570 (* DEBUG *)
|
ziv@2275
|
571 val gunk0 : ((Sql.cmp * Sql.sqexp * Sql.sqexp) formula
|
ziv@2275
|
572 * (Sql.cmp * Sql.sqexp * Sql.sqexp) formula) list ref = ref []
|
ziv@2275
|
573 val gunk1 : (Sql.cmp * atomExp option * atomExp option) list list list ref = ref []
|
ziv@2275
|
574 val gunk2 : exp list ref = ref []
|
ziv@2275
|
575
|
ziv@2216
|
576 structure UF = UnionFindFn(AtomExpKey)
|
ziv@2234
|
577
|
ziv@2273
|
578 val rec sqexpToFormula =
|
ziv@2273
|
579 fn Sql.SqTrue => Combo (Conj, [])
|
ziv@2273
|
580 | Sql.SqFalse => Combo (Disj, [])
|
ziv@2273
|
581 | Sql.SqNot e => Negate (sqexpToFormula e)
|
ziv@2273
|
582 | Sql.Binop (Sql.RCmp c, e1, e2) => Atom (c, e1, e2)
|
ziv@2273
|
583 | Sql.Binop (Sql.RLop l, p1, p2) => Combo (case l of Sql.And => Conj | Sql.Or => Disj,
|
ziv@2273
|
584 [sqexpToFormula p1, sqexpToFormula p2])
|
ziv@2273
|
585 (* ASK: any other sqexps that can be props? *)
|
ziv@2273
|
586 | _ => raise Match
|
ziv@2273
|
587
|
ziv@2275
|
588 fun mapSqexpFields f =
|
ziv@2275
|
589 fn Sql.Field (t, v) => f (t, v)
|
ziv@2275
|
590 | Sql.SqNot e => Sql.SqNot (mapSqexpFields f e)
|
ziv@2275
|
591 | Sql.Binop (r, e1, e2) => Sql.Binop (r, mapSqexpFields f e1, mapSqexpFields f e2)
|
ziv@2275
|
592 | Sql.SqKnown e => Sql.SqKnown (mapSqexpFields f e)
|
ziv@2275
|
593 | Sql.SqFunc (s, e) => Sql.SqFunc (s, mapSqexpFields f e)
|
ziv@2275
|
594 | e => e
|
ziv@2275
|
595
|
ziv@2273
|
596 fun renameTables tablePairs =
|
ziv@2273
|
597 let
|
ziv@2275
|
598 fun rename table =
|
ziv@2273
|
599 case List.find (fn (_, t) => table = t) tablePairs of
|
ziv@2273
|
600 NONE => table
|
ziv@2273
|
601 | SOME (realTable, _) => realTable
|
ziv@2273
|
602 in
|
ziv@2275
|
603 mapSqexpFields (fn (t, f) => Sql.Field (rename t, f))
|
ziv@2273
|
604 end
|
ziv@2273
|
605
|
ziv@2274
|
606 fun queryToFormula marker =
|
ziv@2274
|
607 fn Sql.Query1 {Select = sitems, From = tablePairs, Where = wher} =>
|
ziv@2274
|
608 let
|
ziv@2274
|
609 val fWhere = case wher of
|
ziv@2274
|
610 NONE => Combo (Conj, [])
|
ziv@2275
|
611 | SOME e => sqexpToFormula (renameTables tablePairs e)
|
ziv@2274
|
612 in
|
ziv@2275
|
613 case marker of
|
ziv@2275
|
614 NONE => fWhere
|
ziv@2275
|
615 | SOME markFields =>
|
ziv@2275
|
616 let
|
ziv@2275
|
617 val fWhereMarked = mapFormulaExps markFields fWhere
|
ziv@2275
|
618 val toSqexp =
|
ziv@2275
|
619 fn Sql.SqField tf => Sql.Field tf
|
ziv@2275
|
620 | Sql.SqExp (se, _) => se
|
ziv@2275
|
621 fun ineq se = Atom (Sql.Ne, se, markFields se)
|
ziv@2275
|
622 val fIneqs = Combo (Disj, map (ineq o renameTables tablePairs o toSqexp) sitems)
|
ziv@2275
|
623 in
|
ziv@2275
|
624 (Combo (Conj,
|
ziv@2275
|
625 [fWhere,
|
ziv@2275
|
626 Combo (Disj,
|
ziv@2275
|
627 [Negate fWhereMarked,
|
ziv@2275
|
628 Combo (Conj, [fWhereMarked, fIneqs])])]))
|
ziv@2275
|
629 end
|
ziv@2274
|
630 end
|
ziv@2274
|
631 | Sql.Union (q1, q2) => Combo (Disj, [queryToFormula marker q1, queryToFormula marker q2])
|
ziv@2273
|
632
|
ziv@2274
|
633 fun valsToFormula (markLeft, markRight) (table, vals) =
|
ziv@2274
|
634 Combo (Conj,
|
ziv@2274
|
635 map (fn (field, v) => Atom (Sql.Eq, markLeft (Sql.Field (table, field)), markRight v))
|
ziv@2274
|
636 vals)
|
ziv@2273
|
637
|
ziv@2274
|
638 (* TODO: verify logic for insertion and deletion. *)
|
ziv@2274
|
639 val rec dmlToFormulaMarker =
|
ziv@2274
|
640 fn Sql.Insert (table, vals) => (valsToFormula (id, id) (table, vals), NONE)
|
ziv@2275
|
641 | Sql.Delete (table, wher) => (sqexpToFormula (renameTables [(table, "T")] wher), NONE)
|
ziv@2273
|
642 | Sql.Update (table, vals, wher) =>
|
ziv@2273
|
643 let
|
ziv@2275
|
644 val fWhere = sqexpToFormula (renameTables [(table, "T")] wher)
|
ziv@2274
|
645 fun fVals marks = valsToFormula marks (table, vals)
|
ziv@2273
|
646 val modifiedFields = SS.addList (SS.empty, map #1 vals)
|
ziv@2273
|
647 (* TODO: don't use field name hack. *)
|
ziv@2275
|
648 val markFields =
|
ziv@2275
|
649 mapSqexpFields (fn (t, v) => if t = table andalso SS.member (modifiedFields, v)
|
ziv@2275
|
650 then ((* DEBUG *) print ("yep" ^ Int.toString (length (!gunk0)));
|
ziv@2275
|
651 Sql.Field (t, v ^ "'"))
|
ziv@2275
|
652 else ((* DEBUG *) print (table ^ " " ^ t ^ "\n"); Sql.Field (t, v)))
|
ziv@2275
|
653 val mark = mapFormulaExps markFields
|
ziv@2273
|
654 in
|
ziv@2275
|
655 ((Combo (Disj, [Combo (Conj, [fVals (id, markFields), mark fWhere]),
|
ziv@2275
|
656 Combo (Conj, [fVals (markFields, id), fWhere])])),
|
ziv@2275
|
657 SOME markFields)
|
ziv@2273
|
658 end
|
ziv@2273
|
659
|
ziv@2274
|
660 fun pairToFormulas (query, dml) =
|
ziv@2274
|
661 let
|
ziv@2275
|
662 val (fDml, marker) = ((* DEBUG *) print "dml\n"; dmlToFormulaMarker dml)
|
ziv@2274
|
663 in
|
ziv@2275
|
664 (* DEBUG *) print "query\n";
|
ziv@2274
|
665 (queryToFormula marker query, fDml)
|
ziv@2274
|
666 end
|
ziv@2274
|
667
|
ziv@2235
|
668 structure ConflictMaps = struct
|
ziv@2235
|
669
|
ziv@2235
|
670 structure TK = TripleKeyFn(structure I = CmpKey
|
ziv@2244
|
671 structure J = AtomOptionKey
|
ziv@2244
|
672 structure K = AtomOptionKey)
|
ziv@2274
|
673
|
ziv@2244
|
674 structure TS : ORD_SET = BinarySetFn(TK)
|
ziv@2235
|
675
|
ziv@2235
|
676 val toKnownEquality =
|
ziv@2235
|
677 (* [NONE] here means unkown. Anything that isn't a comparison between two
|
ziv@2235
|
678 knowns shouldn't be used, and simply dropping unused terms is okay in
|
ziv@2235
|
679 disjunctive normal form. *)
|
ziv@2235
|
680 fn (Sql.Eq, SOME e1, SOME e2) => SOME (e1, e2)
|
ziv@2235
|
681 | _ => NONE
|
ziv@2235
|
682
|
ziv@2274
|
683 fun equivClasses atoms : atomExp list list option =
|
ziv@2274
|
684 let
|
ziv@2274
|
685 val uf = List.foldl UF.union' UF.empty (List.mapPartial toKnownEquality atoms)
|
ziv@2274
|
686 val ineqs = List.filter (fn (cmp, _, _) =>
|
ziv@2274
|
687 cmp = Sql.Ne orelse cmp = Sql.Lt orelse cmp = Sql.Gt)
|
ziv@2274
|
688 atoms
|
ziv@2274
|
689 val contradiction =
|
ziv@2274
|
690 fn (cmp, SOME ae1, SOME ae2) => (cmp = Sql.Ne orelse cmp = Sql.Lt orelse cmp = Sql.Gt)
|
ziv@2275
|
691 andalso UF.together (uf, ae1, ae2)
|
ziv@2274
|
692 (* If we don't know one side of the comparision, not a contradiction. *)
|
ziv@2274
|
693 | _ => false
|
ziv@2274
|
694 in
|
ziv@2274
|
695 not (List.exists contradiction atoms) <\oguard\> SOME (UF.classes uf)
|
ziv@2274
|
696 end
|
ziv@2235
|
697
|
ziv@2235
|
698 fun addToEqs (eqs, n, e) =
|
ziv@2235
|
699 case IM.find (eqs, n) of
|
ziv@2235
|
700 (* Comparing to a constant is probably better than comparing to a
|
ziv@2235
|
701 variable? Checking that existing constants match a new ones is
|
ziv@2235
|
702 handled by [accumulateEqs]. *)
|
ziv@2235
|
703 SOME (Prim _) => eqs
|
ziv@2235
|
704 | _ => IM.insert (eqs, n, e)
|
ziv@2235
|
705
|
ziv@2235
|
706 val accumulateEqs =
|
ziv@2235
|
707 (* [NONE] means we have a contradiction. *)
|
ziv@2235
|
708 fn (_, NONE) => NONE
|
ziv@2235
|
709 | ((Prim p1, Prim p2), eqso) =>
|
ziv@2235
|
710 (case Prim.compare (p1, p2) of
|
ziv@2235
|
711 EQUAL => eqso
|
ziv@2235
|
712 | _ => NONE)
|
ziv@2235
|
713 | ((QueryArg n, Prim p), SOME eqs) => SOME (addToEqs (eqs, n, Prim p))
|
ziv@2235
|
714 | ((QueryArg n, DmlRel r), SOME eqs) => SOME (addToEqs (eqs, n, DmlRel r))
|
ziv@2235
|
715 | ((Prim p, QueryArg n), SOME eqs) => SOME (addToEqs (eqs, n, Prim p))
|
ziv@2235
|
716 | ((DmlRel r, QueryArg n), SOME eqs) => SOME (addToEqs (eqs, n, DmlRel r))
|
ziv@2235
|
717 (* TODO: deal with equalities between [DmlRel]s and [Prim]s.
|
ziv@2235
|
718 This would involve guarding the invalidation with a check for the
|
ziv@2235
|
719 relevant comparisons. *)
|
ziv@2235
|
720 | (_, eqso) => eqso
|
ziv@2235
|
721
|
ziv@2235
|
722 val eqsOfClass : atomExp list -> atomExp IM.map option =
|
ziv@2235
|
723 List.foldl accumulateEqs (SOME IM.empty)
|
ziv@2235
|
724 o chooseTwos
|
ziv@2235
|
725
|
ziv@2235
|
726 fun toAtomExps rel (cmp, e1, e2) =
|
ziv@2235
|
727 let
|
ziv@2235
|
728 val qa =
|
ziv@2235
|
729 (* Here [NONE] means unkown. *)
|
ziv@2235
|
730 fn Sql.SqConst p => SOME (Prim p)
|
ziv@2235
|
731 | Sql.Field tf => SOME (Field tf)
|
ziv@2235
|
732 | Sql.Inj (EPrim p, _) => SOME (Prim p)
|
ziv@2235
|
733 | Sql.Inj (ERel n, _) => SOME (rel n)
|
ziv@2235
|
734 (* We can't deal with anything else, e.g., CURRENT_TIMESTAMP
|
ziv@2235
|
735 becomes Sql.Unmodeled, which becomes NONE here. *)
|
ziv@2235
|
736 | _ => NONE
|
ziv@2235
|
737 in
|
ziv@2235
|
738 (cmp, qa e1, qa e2)
|
ziv@2235
|
739 end
|
ziv@2235
|
740
|
ziv@2244
|
741 val negateCmp =
|
ziv@2244
|
742 fn Sql.Eq => Sql.Ne
|
ziv@2244
|
743 | Sql.Ne => Sql.Eq
|
ziv@2244
|
744 | Sql.Lt => Sql.Ge
|
ziv@2244
|
745 | Sql.Le => Sql.Gt
|
ziv@2244
|
746 | Sql.Gt => Sql.Le
|
ziv@2244
|
747 | Sql.Ge => Sql.Lt
|
ziv@2244
|
748
|
ziv@2244
|
749 fun normalizeAtom (negating, (cmp, e1, e2)) =
|
ziv@2244
|
750 (* Restricting to Le/Lt and sorting the expressions in Eq/Ne helps with
|
ziv@2244
|
751 simplification, where we put the triples in sets. *)
|
ziv@2244
|
752 case (if negating then negateCmp cmp else cmp) of
|
ziv@2244
|
753 Sql.Eq => (case AtomOptionKey.compare (e1, e2) of
|
ziv@2244
|
754 LESS => (Sql.Eq, e2, e1)
|
ziv@2244
|
755 | _ => (Sql.Eq, e1, e2))
|
ziv@2244
|
756 | Sql.Ne => (case AtomOptionKey.compare (e1, e2) of
|
ziv@2244
|
757 LESS => (Sql.Ne, e2, e1)
|
ziv@2244
|
758 | _ => (Sql.Ne, e1, e2))
|
ziv@2244
|
759 | Sql.Lt => (Sql.Lt, e1, e2)
|
ziv@2244
|
760 | Sql.Le => (Sql.Le, e1, e2)
|
ziv@2244
|
761 | Sql.Gt => (Sql.Lt, e2, e1)
|
ziv@2244
|
762 | Sql.Ge => (Sql.Le, e2, e1)
|
ziv@2235
|
763
|
ziv@2235
|
764 val markQuery : (Sql.cmp * Sql.sqexp * Sql.sqexp) formula ->
|
ziv@2235
|
765 (Sql.cmp * atomExp option * atomExp option) formula =
|
ziv@2235
|
766 mapFormula (toAtomExps QueryArg)
|
ziv@2235
|
767
|
ziv@2235
|
768 val markDml : (Sql.cmp * Sql.sqexp * Sql.sqexp) formula ->
|
ziv@2235
|
769 (Sql.cmp * atomExp option * atomExp option) formula =
|
ziv@2235
|
770 mapFormula (toAtomExps DmlRel)
|
ziv@2250
|
771
|
ziv@2235
|
772 (* No eqs should have key conflicts because no variable is in two
|
ziv@2235
|
773 equivalence classes, so the [#1] could be [#2]. *)
|
ziv@2235
|
774 val mergeEqs : (atomExp IntBinaryMap.map option list
|
ziv@2235
|
775 -> atomExp IntBinaryMap.map option) =
|
ziv@2271
|
776 List.foldr (omap2 (IM.unionWith #1)) (SOME IM.empty)
|
ziv@2235
|
777
|
ziv@2239
|
778 val simplify =
|
ziv@2239
|
779 map TS.listItems
|
ziv@2239
|
780 o removeRedundant (fn (x, y) => TS.isSubset (y, x))
|
ziv@2239
|
781 o map (fn xs => TS.addList (TS.empty, xs))
|
ziv@2239
|
782
|
ziv@2235
|
783 fun dnf (fQuery, fDml) =
|
ziv@2244
|
784 normalize simplify normalizeAtom Disj (Combo (Conj, [markQuery fQuery, markDml fDml]))
|
ziv@2235
|
785
|
ziv@2274
|
786 val conflictMaps =
|
ziv@2274
|
787 List.mapPartial (mergeEqs o map eqsOfClass)
|
ziv@2274
|
788 o List.mapPartial equivClasses
|
ziv@2275
|
789 o (fn x => (gunk1 := x :: !gunk1; x))
|
ziv@2274
|
790 o dnf
|
ziv@2275
|
791 o (fn x => (gunk0 := x :: !gunk0; x))
|
ziv@2235
|
792
|
ziv@2235
|
793 end
|
ziv@2235
|
794
|
ziv@2235
|
795 val conflictMaps = ConflictMaps.conflictMaps
|
ziv@2213
|
796
|
ziv@2213
|
797
|
ziv@2265
|
798 (*************************************)
|
ziv@2265
|
799 (* Program Instrumentation Utilities *)
|
ziv@2265
|
800 (*************************************)
|
ziv@2213
|
801
|
ziv@2233
|
802 val {check, store, flush, ...} = getCache ()
|
ziv@2233
|
803
|
ziv@2248
|
804 val dummyTyp = (TRecord [], dummyLoc)
|
ziv@2248
|
805
|
ziv@2230
|
806 fun stringExp s = (EPrim (Prim.String (Prim.Normal, s)), dummyLoc)
|
ziv@2230
|
807
|
ziv@2230
|
808 val stringTyp = (TFfi ("Basis", "string"), dummyLoc)
|
ziv@2213
|
809
|
ziv@2213
|
810 val sequence =
|
ziv@2213
|
811 fn (exp :: exps) =>
|
ziv@2213
|
812 let
|
ziv@2230
|
813 val loc = dummyLoc
|
ziv@2213
|
814 in
|
ziv@2213
|
815 List.foldl (fn (e', seq) => ESeq ((seq, loc), (e', loc))) exp exps
|
ziv@2213
|
816 end
|
ziv@2213
|
817 | _ => raise Match
|
ziv@2213
|
818
|
ziv@2248
|
819 (* Always increments negative indices as a hack we use later. *)
|
ziv@2248
|
820 fun incRels inc =
|
ziv@2215
|
821 MonoUtil.Exp.mapB
|
ziv@2248
|
822 {typ = fn t' => t',
|
ziv@2248
|
823 exp = fn bound =>
|
ziv@2248
|
824 (fn ERel n => ERel (if n >= bound orelse n < 0 then n + inc else n)
|
ziv@2248
|
825 | e' => e'),
|
ziv@2248
|
826 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1 | (bound, _) => bound}
|
ziv@2248
|
827 0
|
ziv@2213
|
828
|
ziv@2262
|
829 fun fileTopLevelMapfoldB doTopLevelExp (decls, sideInfo) state =
|
ziv@2262
|
830 let
|
ziv@2262
|
831 fun doVal env ((x, n, t, exp, s), state) =
|
ziv@2262
|
832 let
|
ziv@2262
|
833 val (exp, state) = doTopLevelExp env exp state
|
ziv@2262
|
834 in
|
ziv@2262
|
835 ((x, n, t, exp, s), state)
|
ziv@2262
|
836 end
|
ziv@2262
|
837 fun doDecl' env (decl', state) =
|
ziv@2262
|
838 case decl' of
|
ziv@2262
|
839 DVal v =>
|
ziv@2262
|
840 let
|
ziv@2262
|
841 val (v, state) = doVal env (v, state)
|
ziv@2262
|
842 in
|
ziv@2262
|
843 (DVal v, state)
|
ziv@2262
|
844 end
|
ziv@2262
|
845 | DValRec vs =>
|
ziv@2262
|
846 let
|
ziv@2262
|
847 val (vs, state) = ListUtil.foldlMap (doVal env) state vs
|
ziv@2262
|
848 in
|
ziv@2262
|
849 (DValRec vs, state)
|
ziv@2262
|
850 end
|
ziv@2262
|
851 | _ => (decl', state)
|
ziv@2262
|
852 fun doDecl (decl as (decl', loc), (env, state)) =
|
ziv@2262
|
853 let
|
ziv@2262
|
854 val env = MonoEnv.declBinds env decl
|
ziv@2262
|
855 val (decl', state) = doDecl' env (decl', state)
|
ziv@2262
|
856 in
|
ziv@2262
|
857 ((decl', loc), (env, state))
|
ziv@2262
|
858 end
|
ziv@2262
|
859 val (decls, (_, state)) = (ListUtil.foldlMap doDecl (MonoEnv.empty, state) decls)
|
ziv@2262
|
860 in
|
ziv@2262
|
861 ((decls, sideInfo), state)
|
ziv@2262
|
862 end
|
ziv@2262
|
863
|
ziv@2262
|
864 fun fileAllMapfoldB doExp file start =
|
ziv@2248
|
865 case MonoUtil.File.mapfoldB
|
ziv@2248
|
866 {typ = Search.return2,
|
ziv@2250
|
867 exp = fn env => fn e' => fn s => Search.Continue (doExp env e' s),
|
ziv@2248
|
868 decl = fn _ => Search.return2,
|
ziv@2248
|
869 bind = doBind}
|
ziv@2250
|
870 MonoEnv.empty file start of
|
ziv@2213
|
871 Search.Continue x => x
|
ziv@2213
|
872 | Search.Return _ => raise Match
|
ziv@2213
|
873
|
ziv@2262
|
874 fun fileMap doExp file = #1 (fileAllMapfoldB (fn _ => fn e => fn _ => (doExp e, ())) file ())
|
ziv@2213
|
875
|
ziv@2267
|
876 (* TODO: make this a bit prettier.... *)
|
ziv@2267
|
877 val simplifySql =
|
ziv@2266
|
878 let
|
ziv@2267
|
879 fun factorOutNontrivial text =
|
ziv@2267
|
880 let
|
ziv@2267
|
881 val loc = dummyLoc
|
ziv@2267
|
882 fun strcat (e1, e2) = (EStrcat (e1, e2), loc)
|
ziv@2267
|
883 val chunks = Sql.chunkify text
|
ziv@2267
|
884 val (newText, newVariables) =
|
ziv@2267
|
885 (* Important that this is foldr (to oppose foldl below). *)
|
ziv@2267
|
886 List.foldr
|
ziv@2267
|
887 (fn (chunk, (qText, newVars)) =>
|
ziv@2267
|
888 (* Variable bound to the head of newVars will have the lowest index. *)
|
ziv@2267
|
889 case chunk of
|
ziv@2267
|
890 (* EPrim should always be a string in this case. *)
|
ziv@2267
|
891 Sql.Exp (e as (EPrim _, _)) => (strcat (e, qText), newVars)
|
ziv@2267
|
892 | Sql.Exp e =>
|
ziv@2267
|
893 let
|
ziv@2267
|
894 val n = length newVars
|
ziv@2267
|
895 in
|
ziv@2267
|
896 (* This is the (n+1)th new variable, so there are
|
ziv@2267
|
897 already n new variables bound, so we increment
|
ziv@2267
|
898 indices by n. *)
|
ziv@2267
|
899 (strcat ((ERel (~(n+1)), loc), qText), incRels n e :: newVars)
|
ziv@2267
|
900 end
|
ziv@2267
|
901 | Sql.String s => (strcat (stringExp s, qText), newVars))
|
ziv@2267
|
902 (stringExp "", [])
|
ziv@2267
|
903 chunks
|
ziv@2267
|
904 fun wrapLets e' =
|
ziv@2267
|
905 (* Important that this is foldl (to oppose foldr above). *)
|
ziv@2273
|
906 List.foldl (fn (v, e') => ELet ("sqlArg", stringTyp, v, (e', loc)))
|
ziv@2267
|
907 e'
|
ziv@2267
|
908 newVariables
|
ziv@2267
|
909 val numArgs = length newVariables
|
ziv@2267
|
910 in
|
ziv@2267
|
911 (newText, wrapLets, numArgs)
|
ziv@2267
|
912 end
|
ziv@2267
|
913 fun doExp exp' =
|
ziv@2267
|
914 let
|
ziv@2267
|
915 val text = case exp' of
|
ziv@2267
|
916 EQuery {query = text, ...} => text
|
ziv@2267
|
917 | EDml (text, _) => text
|
ziv@2267
|
918 | _ => raise Match
|
ziv@2267
|
919 val (newText, wrapLets, numArgs) = factorOutNontrivial text
|
ziv@2267
|
920 val newExp' = case exp' of
|
ziv@2267
|
921 EQuery q => EQuery {query = newText,
|
ziv@2267
|
922 exps = #exps q,
|
ziv@2267
|
923 tables = #tables q,
|
ziv@2267
|
924 state = #state q,
|
ziv@2267
|
925 body = #body q,
|
ziv@2267
|
926 initial = #initial q}
|
ziv@2267
|
927 | EDml (_, failureMode) => EDml (newText, failureMode)
|
ziv@2267
|
928 | _ => raise Match
|
ziv@2267
|
929 in
|
ziv@2267
|
930 (* Increment once for each new variable just made. This is
|
ziv@2267
|
931 where we use the negative De Bruijn indices hack. *)
|
ziv@2267
|
932 (* TODO: please don't use that hack. As anyone could have
|
ziv@2267
|
933 predicted, it was incomprehensible a year later.... *)
|
ziv@2267
|
934 wrapLets (#1 (incRels numArgs (newExp', dummyLoc)))
|
ziv@2267
|
935 end
|
ziv@2266
|
936 in
|
ziv@2267
|
937 fileMap (fn exp' => case exp' of
|
ziv@2267
|
938 EQuery _ => doExp exp'
|
ziv@2267
|
939 | EDml _ => doExp exp'
|
ziv@2267
|
940 | _ => exp')
|
ziv@2266
|
941 end
|
ziv@2266
|
942
|
ziv@2250
|
943
|
ziv@2250
|
944 (**********************)
|
ziv@2250
|
945 (* Mono Type Checking *)
|
ziv@2250
|
946 (**********************)
|
ziv@2250
|
947
|
ziv@2250
|
948 fun typOfExp' (env : MonoEnv.env) : exp' -> typ option =
|
ziv@2250
|
949 fn EPrim p => SOME (TFfi ("Basis", case p of
|
ziv@2250
|
950 Prim.Int _ => "int"
|
ziv@2250
|
951 | Prim.Float _ => "double"
|
ziv@2250
|
952 | Prim.String _ => "string"
|
ziv@2250
|
953 | Prim.Char _ => "char"),
|
ziv@2250
|
954 dummyLoc)
|
ziv@2250
|
955 | ERel n => SOME (#2 (MonoEnv.lookupERel env n))
|
ziv@2250
|
956 | ENamed n => SOME (#2 (MonoEnv.lookupENamed env n))
|
ziv@2250
|
957 (* ASK: okay to make a new [ref] each time? *)
|
ziv@2250
|
958 | ECon (dk, PConVar nCon, _) =>
|
ziv@2250
|
959 let
|
ziv@2250
|
960 val (_, _, nData) = MonoEnv.lookupConstructor env nCon
|
ziv@2250
|
961 val (_, cs) = MonoEnv.lookupDatatype env nData
|
ziv@2250
|
962 in
|
ziv@2250
|
963 SOME (TDatatype (nData, ref (dk, cs)), dummyLoc)
|
ziv@2250
|
964 end
|
ziv@2250
|
965 | ECon (_, PConFfi {mod = s, datatyp, ...}, _) => SOME (TFfi (s, datatyp), dummyLoc)
|
ziv@2250
|
966 | ENone t => SOME (TOption t, dummyLoc)
|
ziv@2250
|
967 | ESome (t, _) => SOME (TOption t, dummyLoc)
|
ziv@2250
|
968 | EFfi _ => NONE
|
ziv@2250
|
969 | EFfiApp _ => NONE
|
ziv@2250
|
970 | EApp (e1, e2) => (case typOfExp env e1 of
|
ziv@2250
|
971 SOME (TFun (_, t), _) => SOME t
|
ziv@2250
|
972 | _ => NONE)
|
ziv@2250
|
973 | EAbs (_, t1, t2, _) => SOME (TFun (t1, t2), dummyLoc)
|
ziv@2250
|
974 (* ASK: is this right? *)
|
ziv@2250
|
975 | EUnop (unop, e) => (case unop of
|
ziv@2250
|
976 "!" => SOME (TFfi ("Basis", "bool"), dummyLoc)
|
ziv@2250
|
977 | "-" => typOfExp env e
|
ziv@2250
|
978 | _ => NONE)
|
ziv@2250
|
979 (* ASK: how should this (and other "=> NONE" cases) work? *)
|
ziv@2250
|
980 | EBinop _ => NONE
|
ziv@2250
|
981 | ERecord fields => SOME (TRecord (map (fn (s, _, t) => (s, t)) fields), dummyLoc)
|
ziv@2250
|
982 | EField (e, s) => (case typOfExp env e of
|
ziv@2250
|
983 SOME (TRecord fields, _) =>
|
ziv@2250
|
984 (case List.find (fn (s', _) => s = s') fields of
|
ziv@2250
|
985 SOME (_, t) => SOME t
|
ziv@2250
|
986 | _ => NONE)
|
ziv@2250
|
987 | _ => NONE)
|
ziv@2250
|
988 | ECase (_, _, {result, ...}) => SOME result
|
ziv@2250
|
989 | EStrcat _ => SOME (TFfi ("Basis", "string"), dummyLoc)
|
ziv@2250
|
990 | EWrite _ => SOME (TRecord [], dummyLoc)
|
ziv@2250
|
991 | ESeq (_, e) => typOfExp env e
|
ziv@2250
|
992 | ELet (s, t, e1, e2) => typOfExp (MonoEnv.pushERel env s t (SOME e1)) e2
|
ziv@2250
|
993 | EClosure _ => NONE
|
ziv@2250
|
994 | EUnurlify (_, t, _) => SOME t
|
ziv@2269
|
995 | EQuery {state, ...} => SOME state
|
ziv@2256
|
996 | _ => NONE
|
ziv@2250
|
997
|
ziv@2250
|
998 and typOfExp env (e', loc) = typOfExp' env e'
|
ziv@2250
|
999
|
ziv@2250
|
1000
|
ziv@2266
|
1001 (***********)
|
ziv@2266
|
1002 (* Caching *)
|
ziv@2266
|
1003 (***********)
|
ziv@2250
|
1004
|
ziv@2267
|
1005 (*
|
ziv@2267
|
1006
|
ziv@2267
|
1007 To get the invalidations for a dml, we need (each <- is list-monad-y):
|
ziv@2267
|
1008 * table <- dml
|
ziv@2267
|
1009 * cache <- table
|
ziv@2267
|
1010 * query <- cache
|
ziv@2267
|
1011 * inval <- (query, dml),
|
ziv@2267
|
1012 where inval is a list of query argument indices, so
|
ziv@2267
|
1013 * way to change query args in inval to cache args.
|
ziv@2267
|
1014 For now, the last one is just
|
ziv@2267
|
1015 * a map from query arg number to the corresponding free variable (per query)
|
ziv@2267
|
1016 * a map from free variable to cache arg number (per cache).
|
ziv@2267
|
1017 Both queries and caches should have IDs.
|
ziv@2267
|
1018
|
ziv@2267
|
1019 *)
|
ziv@2267
|
1020
|
ziv@2271
|
1021 type state = InvalInfo.state
|
ziv@2271
|
1022
|
ziv@2271
|
1023 datatype subexp = Cachable of InvalInfo.t * (state -> exp * state) | Impure of exp
|
ziv@2271
|
1024
|
ziv@2271
|
1025 val isImpure =
|
ziv@2271
|
1026 fn Cachable _ => false
|
ziv@2271
|
1027 | Impure _ => true
|
ziv@2271
|
1028
|
ziv@2271
|
1029 val runSubexp : subexp * state -> exp * state =
|
ziv@2271
|
1030 fn (Cachable (_, f), state) => f state
|
ziv@2271
|
1031 | (Impure e, state) => (e, state)
|
ziv@2271
|
1032
|
ziv@2271
|
1033 val invalInfoOfSubexp =
|
ziv@2271
|
1034 fn Cachable (invalInfo, _) => invalInfo
|
ziv@2271
|
1035 | Impure _ => raise Match
|
ziv@2271
|
1036
|
ziv@2271
|
1037 fun cacheWrap (env, exp, typ, args, index) =
|
ziv@2265
|
1038 let
|
ziv@2265
|
1039 val loc = dummyLoc
|
ziv@2265
|
1040 val rel0 = (ERel 0, loc)
|
ziv@2265
|
1041 in
|
ziv@2271
|
1042 case MonoFooify.urlify env (rel0, typ) of
|
ziv@2265
|
1043 NONE => NONE
|
ziv@2265
|
1044 | SOME urlified =>
|
ziv@2265
|
1045 let
|
ziv@2265
|
1046 (* We ensure before this step that all arguments aren't effectful.
|
ziv@2265
|
1047 by turning them into local variables as needed. *)
|
ziv@2265
|
1048 val argsInc = map (incRels 1) args
|
ziv@2268
|
1049 val check = (check (index, args), loc)
|
ziv@2268
|
1050 val store = (store (index, argsInc, urlified), loc)
|
ziv@2265
|
1051 in
|
ziv@2271
|
1052 SOME (ECase (check,
|
ziv@2271
|
1053 [((PNone stringTyp, loc),
|
ziv@2273
|
1054 (ELet ("q", typ, exp, (ESeq (store, rel0), loc)), loc)),
|
ziv@2273
|
1055 ((PSome (stringTyp, (PVar ("hit", stringTyp), loc)), loc),
|
ziv@2271
|
1056 (* Boolean is false because we're not unurlifying from a cookie. *)
|
ziv@2271
|
1057 (EUnurlify (rel0, typ, false), loc))],
|
ziv@2271
|
1058 {disc = (TOption stringTyp, loc), result = typ}))
|
ziv@2265
|
1059 end
|
ziv@2265
|
1060 end
|
ziv@2265
|
1061
|
ziv@2258
|
1062 val expSize = MonoUtil.Exp.fold {typ = #2, exp = fn (_, n) => n+1} 0
|
ziv@2258
|
1063
|
ziv@2259
|
1064 (* TODO: pick a number. *)
|
ziv@2259
|
1065 val sizeWorthCaching = 5
|
ziv@2259
|
1066
|
ziv@2269
|
1067 val worthCaching =
|
ziv@2269
|
1068 fn EQuery _ => true
|
ziv@2269
|
1069 | exp' => expSize (exp', dummyLoc) > sizeWorthCaching
|
ziv@2269
|
1070
|
ziv@2273
|
1071 fun cacheExp (env, exp', invalInfo, state : state) =
|
ziv@2273
|
1072 case worthCaching exp' <\oguard\> typOfExp' env exp' of
|
ziv@2269
|
1073 NONE => NONE
|
ziv@2269
|
1074 | SOME (TFun _, _) => NONE
|
ziv@2269
|
1075 | SOME typ =>
|
ziv@2271
|
1076 let
|
ziv@2273
|
1077 val args = InvalInfo.orderArgs (invalInfo, freeVars (exp', dummyLoc))
|
ziv@2273
|
1078 val numArgs = length args
|
ziv@2273
|
1079 in (List.foldr (fn (arg, acc) =>
|
ziv@2273
|
1080 acc
|
ziv@2273
|
1081 <\obind\>
|
ziv@2273
|
1082 (fn args' =>
|
ziv@2273
|
1083 (case arg of
|
ziv@2273
|
1084 AsIs exp => SOME exp
|
ziv@2273
|
1085 | Urlify exp =>
|
ziv@2273
|
1086 typOfExp env exp
|
ziv@2273
|
1087 <\obind\>
|
ziv@2273
|
1088 (fn typ =>
|
ziv@2273
|
1089 (MonoFooify.urlify env (exp, typ))))
|
ziv@2273
|
1090 <\obind\>
|
ziv@2273
|
1091 (fn arg' => SOME (arg' :: args'))))
|
ziv@2273
|
1092 (SOME [])
|
ziv@2273
|
1093 args)
|
ziv@2273
|
1094 <\obind\>
|
ziv@2273
|
1095 (fn args' =>
|
ziv@2273
|
1096 cacheWrap (env, (exp', dummyLoc), typ, args', #index state)
|
ziv@2273
|
1097 <\obind\>
|
ziv@2273
|
1098 (fn cachedExp =>
|
ziv@2273
|
1099 SOME (cachedExp, InvalInfo.updateState (invalInfo, numArgs, state))))
|
ziv@2271
|
1100 end
|
ziv@2269
|
1101
|
ziv@2271
|
1102 fun cacheQuery (effs, env, q) : subexp =
|
ziv@2266
|
1103 let
|
ziv@2266
|
1104 (* We use dummyTyp here. I think this is okay because databases don't
|
ziv@2266
|
1105 store (effectful) functions, but perhaps there's some pathalogical
|
ziv@2266
|
1106 corner case missing.... *)
|
ziv@2266
|
1107 fun safe bound =
|
ziv@2266
|
1108 not
|
ziv@2266
|
1109 o effectful effs
|
ziv@2266
|
1110 (iterate (fn env => MonoEnv.pushERel env "_" dummyTyp NONE)
|
ziv@2266
|
1111 bound
|
ziv@2266
|
1112 env)
|
ziv@2271
|
1113 val {query = queryText, initial, body, ...} = q
|
ziv@2271
|
1114 (* DEBUG *)
|
ziv@2271
|
1115 (* val () = Print.preface ("sqlcache> ", MonoPrint.p_exp MonoEnv.empty queryText) *)
|
ziv@2266
|
1116 val attempt =
|
ziv@2266
|
1117 (* Ziv misses Haskell's do notation.... *)
|
ziv@2267
|
1118 (safe 0 queryText andalso safe 0 initial andalso safe 2 body)
|
ziv@2273
|
1119 <\oguard\>
|
ziv@2268
|
1120 Sql.parse Sql.query queryText
|
ziv@2273
|
1121 <\obind\>
|
ziv@2268
|
1122 (fn queryParsed =>
|
ziv@2271
|
1123 let
|
ziv@2271
|
1124 val invalInfo = InvalInfo.singleton queryParsed
|
ziv@2271
|
1125 fun mkExp state =
|
ziv@2271
|
1126 case cacheExp (env, EQuery q, invalInfo, state) of
|
ziv@2271
|
1127 NONE => ((EQuery q, dummyLoc), state)
|
ziv@2271
|
1128 | SOME (cachedExp, state) => ((cachedExp, dummyLoc), state)
|
ziv@2271
|
1129 in
|
ziv@2271
|
1130 SOME (Cachable (invalInfo, mkExp))
|
ziv@2271
|
1131 end)
|
ziv@2266
|
1132 in
|
ziv@2266
|
1133 case attempt of
|
ziv@2271
|
1134 NONE => Impure (EQuery q, dummyLoc)
|
ziv@2271
|
1135 | SOME subexp => subexp
|
ziv@2266
|
1136 end
|
ziv@2266
|
1137
|
ziv@2271
|
1138 fun cacheTree (effs : IS.set) ((env, exp as (exp', loc)), state) =
|
ziv@2250
|
1139 let
|
ziv@2271
|
1140 fun wrapBindN (f : exp list -> exp')
|
ziv@2271
|
1141 (args : ((MonoEnv.env * exp) * unbind) list) =
|
ziv@2250
|
1142 let
|
ziv@2271
|
1143 val (subexps, state) =
|
ziv@2271
|
1144 ListUtil.foldlMap (cacheTree effs)
|
ziv@2271
|
1145 state
|
ziv@2271
|
1146 (map #1 args)
|
ziv@2268
|
1147 fun mkExp state = mapFst (fn exps => (f exps, loc))
|
ziv@2268
|
1148 (ListUtil.foldlMap runSubexp state subexps)
|
ziv@2271
|
1149 val attempt =
|
ziv@2271
|
1150 if List.exists isImpure subexps
|
ziv@2271
|
1151 then NONE
|
ziv@2271
|
1152 else (List.foldl (omap2 InvalInfo.union)
|
ziv@2271
|
1153 (SOME InvalInfo.empty)
|
ziv@2271
|
1154 (ListPair.map
|
ziv@2271
|
1155 (fn (subexp, (_, unbinds)) =>
|
ziv@2271
|
1156 InvalInfo.unbind (invalInfoOfSubexp subexp, unbinds))
|
ziv@2271
|
1157 (subexps, args)))
|
ziv@2273
|
1158 <\obind\>
|
ziv@2271
|
1159 (fn invalInfo =>
|
ziv@2271
|
1160 SOME (Cachable (invalInfo,
|
ziv@2271
|
1161 fn state =>
|
ziv@2271
|
1162 case cacheExp (env,
|
ziv@2271
|
1163 f (map (#2 o #1) args),
|
ziv@2271
|
1164 invalInfo,
|
ziv@2271
|
1165 state) of
|
ziv@2271
|
1166 NONE => mkExp state
|
ziv@2271
|
1167 | SOME (e', state) => ((e', loc), state)),
|
ziv@2271
|
1168 state))
|
ziv@2250
|
1169 in
|
ziv@2271
|
1170 case attempt of
|
ziv@2271
|
1171 SOME (subexp, state) => (subexp, state)
|
ziv@2271
|
1172 | NONE => mapFst Impure (mkExp state)
|
ziv@2250
|
1173 end
|
ziv@2250
|
1174 fun wrapBind1 f arg =
|
ziv@2250
|
1175 wrapBindN (fn [arg] => f arg | _ => raise Match) [arg]
|
ziv@2250
|
1176 fun wrapBind2 f (arg1, arg2) =
|
ziv@2250
|
1177 wrapBindN (fn [arg1, arg2] => f (arg1, arg2) | _ => raise Match) [arg1, arg2]
|
ziv@2271
|
1178 fun wrapN f es = wrapBindN f (map (fn e => ((env, e), Unknowns 0)) es)
|
ziv@2271
|
1179 fun wrap1 f e = wrapBind1 f ((env, e), Unknowns 0)
|
ziv@2271
|
1180 fun wrap2 f (e1, e2) = wrapBind2 f (((env, e1), Unknowns 0), ((env, e2), Unknowns 0))
|
ziv@2250
|
1181 in
|
ziv@2250
|
1182 case exp' of
|
ziv@2250
|
1183 ECon (dk, pc, SOME e) => wrap1 (fn e => ECon (dk, pc, SOME e)) e
|
ziv@2250
|
1184 | ESome (t, e) => wrap1 (fn e => ESome (t, e)) e
|
ziv@2250
|
1185 | EFfiApp (s1, s2, args) =>
|
ziv@2258
|
1186 if ffiEffectful (s1, s2)
|
ziv@2266
|
1187 then (Impure exp, state)
|
ziv@2258
|
1188 else wrapN (fn es =>
|
ziv@2258
|
1189 EFfiApp (s1, s2, ListPair.map (fn (e, (_, t)) => (e, t)) (es, args)))
|
ziv@2258
|
1190 (map #1 args)
|
ziv@2250
|
1191 | EApp (e1, e2) => wrap2 EApp (e1, e2)
|
ziv@2250
|
1192 | EAbs (s, t1, t2, e) =>
|
ziv@2250
|
1193 wrapBind1 (fn e => EAbs (s, t1, t2, e))
|
ziv@2271
|
1194 ((MonoEnv.pushERel env s t1 NONE, e), Unknowns 1)
|
ziv@2250
|
1195 | EUnop (s, e) => wrap1 (fn e => EUnop (s, e)) e
|
ziv@2250
|
1196 | EBinop (bi, s, e1, e2) => wrap2 (fn (e1, e2) => EBinop (bi, s, e1, e2)) (e1, e2)
|
ziv@2250
|
1197 | ERecord fields =>
|
ziv@2250
|
1198 wrapN (fn es => ERecord (ListPair.map (fn (e, (s, _, t)) => (s, e, t)) (es, fields)))
|
ziv@2250
|
1199 (map #2 fields)
|
ziv@2250
|
1200 | EField (e, s) => wrap1 (fn e => EField (e, s)) e
|
ziv@2250
|
1201 | ECase (e, cases, {disc, result}) =>
|
ziv@2250
|
1202 wrapBindN (fn (e::es) =>
|
ziv@2250
|
1203 ECase (e,
|
ziv@2250
|
1204 (ListPair.map (fn (e, (p, _)) => (p, e)) (es, cases)),
|
ziv@2256
|
1205 {disc = disc, result = result})
|
ziv@2256
|
1206 | _ => raise Match)
|
ziv@2271
|
1207 (((env, e), Unknowns 0)
|
ziv@2271
|
1208 :: map (fn (p, e) =>
|
ziv@2271
|
1209 ((MonoEnv.patBinds env p, e), Unknowns (MonoEnv.patBindsN p)))
|
ziv@2271
|
1210 cases)
|
ziv@2250
|
1211 | EStrcat (e1, e2) => wrap2 EStrcat (e1, e2)
|
ziv@2250
|
1212 (* We record page writes, so they're cachable. *)
|
ziv@2250
|
1213 | EWrite e => wrap1 EWrite e
|
ziv@2250
|
1214 | ESeq (e1, e2) => wrap2 ESeq (e1, e2)
|
ziv@2250
|
1215 | ELet (s, t, e1, e2) =>
|
ziv@2250
|
1216 wrapBind2 (fn (e1, e2) => ELet (s, t, e1, e2))
|
ziv@2271
|
1217 (((env, e1), Unknowns 0),
|
ziv@2271
|
1218 ((MonoEnv.pushERel env s t (SOME e1), e2), Known e1))
|
ziv@2250
|
1219 (* ASK: | EClosure (n, es) => ? *)
|
ziv@2250
|
1220 | EUnurlify (e, t, b) => wrap1 (fn e => EUnurlify (e, t, b)) e
|
ziv@2271
|
1221 | EQuery q => (cacheQuery (effs, env, q), state)
|
ziv@2269
|
1222 | _ => (if effectful effs env exp
|
ziv@2269
|
1223 then Impure exp
|
ziv@2271
|
1224 else Cachable (InvalInfo.empty,
|
ziv@2271
|
1225 fn state =>
|
ziv@2271
|
1226 case cacheExp (env, exp', InvalInfo.empty, state) of
|
ziv@2269
|
1227 NONE => ((exp', loc), state)
|
ziv@2269
|
1228 | SOME (exp', state) => ((exp', loc), state)),
|
ziv@2269
|
1229 state)
|
ziv@2256
|
1230 end
|
ziv@2256
|
1231
|
ziv@2266
|
1232 fun addCaching file =
|
ziv@2256
|
1233 let
|
ziv@2266
|
1234 val effs = effectfulDecls file
|
ziv@2271
|
1235 fun doTopLevelExp env exp state = runSubexp (cacheTree effs ((env, exp), state))
|
ziv@2256
|
1236 in
|
ziv@2271
|
1237 (fileTopLevelMapfoldB doTopLevelExp
|
ziv@2271
|
1238 file
|
ziv@2271
|
1239 {tableToIndices = SIMM.empty,
|
ziv@2271
|
1240 indexToInvalInfo = IM.empty,
|
ziv@2271
|
1241 ffiInfo = [],
|
ziv@2271
|
1242 index = 0},
|
ziv@2271
|
1243 effs)
|
ziv@2265
|
1244 end
|
ziv@2265
|
1245
|
ziv@2265
|
1246
|
ziv@2265
|
1247 (************)
|
ziv@2265
|
1248 (* Flushing *)
|
ziv@2265
|
1249 (************)
|
ziv@2265
|
1250
|
ziv@2265
|
1251 structure Invalidations = struct
|
ziv@2265
|
1252
|
ziv@2265
|
1253 val loc = dummyLoc
|
ziv@2265
|
1254
|
ziv@2265
|
1255 val optionAtomExpToExp =
|
ziv@2265
|
1256 fn NONE => (ENone stringTyp, loc)
|
ziv@2265
|
1257 | SOME e => (ESome (stringTyp,
|
ziv@2265
|
1258 (case e of
|
ziv@2265
|
1259 DmlRel n => ERel n
|
ziv@2265
|
1260 | Prim p => EPrim p
|
ziv@2265
|
1261 (* TODO: make new type containing only these two. *)
|
ziv@2265
|
1262 | _ => raise Match,
|
ziv@2265
|
1263 loc)),
|
ziv@2265
|
1264 loc)
|
ziv@2265
|
1265
|
ziv@2265
|
1266 fun eqsToInvalidation numArgs eqs =
|
ziv@2269
|
1267 List.tabulate (numArgs, (fn n => IM.find (eqs, n)))
|
ziv@2265
|
1268
|
ziv@2265
|
1269 (* Tests if [ys] makes [xs] a redundant cache invalidation. [NONE] here
|
ziv@2265
|
1270 represents unknown, which means a wider invalidation. *)
|
ziv@2265
|
1271 val rec madeRedundantBy : atomExp option list * atomExp option list -> bool =
|
ziv@2265
|
1272 fn ([], []) => true
|
ziv@2265
|
1273 | (_ :: xs, NONE :: ys) => madeRedundantBy (xs, ys)
|
ziv@2265
|
1274 | (SOME x :: xs, SOME y :: ys) => (case AtomExpKey.compare (x, y) of
|
ziv@2265
|
1275 EQUAL => madeRedundantBy (xs, ys)
|
ziv@2265
|
1276 | _ => false)
|
ziv@2265
|
1277 | _ => false
|
ziv@2265
|
1278
|
ziv@2271
|
1279 fun invalidations ((invalInfo, numArgs), dml) =
|
ziv@2271
|
1280 let
|
ziv@2271
|
1281 val query = InvalInfo.query invalInfo
|
ziv@2271
|
1282 in
|
ziv@2271
|
1283 (map (map optionAtomExpToExp)
|
ziv@2271
|
1284 o removeRedundant madeRedundantBy
|
ziv@2271
|
1285 o map (eqsToInvalidation numArgs)
|
ziv@2273
|
1286 o conflictMaps)
|
ziv@2274
|
1287 (pairToFormulas (query, dml))
|
ziv@2271
|
1288 end
|
ziv@2265
|
1289
|
ziv@2265
|
1290 end
|
ziv@2265
|
1291
|
ziv@2265
|
1292 val invalidations = Invalidations.invalidations
|
ziv@2265
|
1293
|
ziv@2273
|
1294 fun addFlushing ((file, {tableToIndices, indexToInvalInfo, ffiInfo, ...} : state), effs) =
|
ziv@2265
|
1295 let
|
ziv@2265
|
1296 val flushes = List.concat
|
ziv@2265
|
1297 o map (fn (i, argss) => map (fn args => flush (i, args)) argss)
|
ziv@2265
|
1298 val doExp =
|
ziv@2267
|
1299 fn dmlExp as EDml (dmlText, failureMode) =>
|
ziv@2265
|
1300 let
|
ziv@2265
|
1301 (* DEBUG *)
|
ziv@2275
|
1302 (* val () = gunk2 := dmlText :: !gunk2 *)
|
ziv@2265
|
1303 (* val () = Print.preface ("SQLCACHE: ", (MonoPrint.p_exp MonoEnv.empty origDmlText)) *)
|
ziv@2265
|
1304 val inval =
|
ziv@2265
|
1305 case Sql.parse Sql.dml dmlText of
|
ziv@2265
|
1306 SOME dmlParsed =>
|
ziv@2271
|
1307 SOME (map (fn i => (case IM.find (indexToInvalInfo, i) of
|
ziv@2271
|
1308 SOME invalInfo =>
|
ziv@2271
|
1309 (i, invalidations (invalInfo, dmlParsed))
|
ziv@2265
|
1310 (* TODO: fail more gracefully. *)
|
ziv@2271
|
1311 (* This probably means invalidating everything.... *)
|
ziv@2265
|
1312 | NONE => raise Match))
|
ziv@2271
|
1313 (SIMM.findList (tableToIndices, tableOfDml dmlParsed)))
|
ziv@2265
|
1314 | NONE => NONE
|
ziv@2265
|
1315 in
|
ziv@2265
|
1316 case inval of
|
ziv@2265
|
1317 (* TODO: fail more gracefully. *)
|
ziv@2265
|
1318 NONE => raise Match
|
ziv@2267
|
1319 | SOME invs => sequence (flushes invs @ [dmlExp])
|
ziv@2265
|
1320 end
|
ziv@2265
|
1321 | e' => e'
|
ziv@2274
|
1322 val file = fileMap doExp file
|
ziv@2274
|
1323
|
ziv@2265
|
1324 in
|
ziv@2268
|
1325 ffiInfoRef := ffiInfo;
|
ziv@2274
|
1326 file
|
ziv@2265
|
1327 end
|
ziv@2265
|
1328
|
ziv@2265
|
1329
|
ziv@2268
|
1330 (************************)
|
ziv@2268
|
1331 (* Compiler Entry Point *)
|
ziv@2268
|
1332 (************************)
|
ziv@2265
|
1333
|
ziv@2265
|
1334 val inlineSql =
|
ziv@2265
|
1335 let
|
ziv@2265
|
1336 val doExp =
|
ziv@2265
|
1337 (* TODO: EQuery, too? *)
|
ziv@2265
|
1338 (* ASK: should this live in [MonoOpt]? *)
|
ziv@2265
|
1339 fn EDml ((ECase (disc, cases, {disc = dTyp, ...}), loc), failureMode) =>
|
ziv@2265
|
1340 let
|
ziv@2265
|
1341 val newCases = map (fn (p, e) => (p, (EDml (e, failureMode), loc))) cases
|
ziv@2265
|
1342 in
|
ziv@2265
|
1343 ECase (disc, newCases, {disc = dTyp, result = (TRecord [], loc)})
|
ziv@2265
|
1344 end
|
ziv@2265
|
1345 | e => e
|
ziv@2265
|
1346 in
|
ziv@2265
|
1347 fileMap doExp
|
ziv@2265
|
1348 end
|
ziv@2265
|
1349
|
ziv@2262
|
1350 fun insertAfterDatatypes ((decls, sideInfo), newDecls) =
|
ziv@2262
|
1351 let
|
ziv@2262
|
1352 val (datatypes, others) = List.partition (fn (DDatatype _, _) => true | _ => false) decls
|
ziv@2262
|
1353 in
|
ziv@2262
|
1354 (datatypes @ newDecls @ others, sideInfo)
|
ziv@2262
|
1355 end
|
ziv@2262
|
1356
|
ziv@2267
|
1357 val go' = addFlushing o addCaching o simplifySql o inlineSql
|
ziv@2256
|
1358
|
ziv@2256
|
1359 fun go file =
|
ziv@2256
|
1360 let
|
ziv@2256
|
1361 (* TODO: do something nicer than [Sql] being in one of two modes. *)
|
ziv@2256
|
1362 val () = (resetFfiInfo (); Sql.sqlcacheMode := true)
|
ziv@2262
|
1363 val file = go' file
|
ziv@2262
|
1364 (* Important that this happens after [MonoFooify.urlify] calls! *)
|
ziv@2262
|
1365 val fmDecls = MonoFooify.getNewFmDecls ()
|
ziv@2256
|
1366 val () = Sql.sqlcacheMode := false
|
ziv@2256
|
1367 in
|
ziv@2262
|
1368 insertAfterDatatypes (file, rev fmDecls)
|
ziv@2250
|
1369 end
|
ziv@2250
|
1370
|
ziv@2209
|
1371 end
|