Mercurial > urweb

annotate src/sqlcache.sml @ 2274:0730e217fc9c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
First draft of more specific formulas for queries.
author Ziv Scully <ziv@mit.edu>
date Thu, 05 Nov 2015 01:48:42 -0500
parents a3cac6cea625
children ce96e166d938
rev   line source
ziv@2250 1 structure Sqlcache :> 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@2216 570 structure UF = UnionFindFn(AtomExpKey)
ziv@2234 571
ziv@2273 572 val rec sqexpToFormula =
ziv@2273 573 fn Sql.SqTrue => Combo (Conj, [])
ziv@2273 574 | Sql.SqFalse => Combo (Disj, [])
ziv@2273 575 | Sql.SqNot e => Negate (sqexpToFormula e)
ziv@2273 576 | Sql.Binop (Sql.RCmp c, e1, e2) => Atom (c, e1, e2)
ziv@2273 577 | Sql.Binop (Sql.RLop l, p1, p2) => Combo (case l of Sql.And => Conj | Sql.Or => Disj,
ziv@2273 578 [sqexpToFormula p1, sqexpToFormula p2])
ziv@2273 579 (* ASK: any other sqexps that can be props? *)
ziv@2273 580 | _ => raise Match
ziv@2273 581
ziv@2273 582 fun renameTables tablePairs =
ziv@2273 583 let
ziv@2273 584 fun renameString table =
ziv@2273 585 case List.find (fn (_, t) => table = t) tablePairs of
ziv@2273 586 NONE => table
ziv@2273 587 | SOME (realTable, _) => realTable
ziv@2273 588 val renameSqexp =
ziv@2273 589 fn Sql.Field (table, field) => Sql.Field (renameString table, field)
ziv@2273 590 | e => e
ziv@2274 591 (* fun renameAtom (cmp, e1, e2) = (cmp, renameSqexp e1, renameSqexp e2) *)
ziv@2273 592 in
ziv@2274 593 mapFormulaExps renameSqexp
ziv@2273 594 end
ziv@2273 595
ziv@2274 596 fun queryToFormula marker =
ziv@2274 597 fn Sql.Query1 {Select = sitems, From = tablePairs, Where = wher} =>
ziv@2274 598 let
ziv@2274 599 val fWhere = case wher of
ziv@2274 600 NONE => Combo (Conj, [])
ziv@2274 601 | SOME e => sqexpToFormula e
ziv@2274 602 in
ziv@2274 603 renameTables tablePairs
ziv@2274 604 (case marker of
ziv@2274 605 NONE => fWhere
ziv@2274 606 | SOME markFields =>
ziv@2274 607 let
ziv@2274 608 val fWhereMarked = mapFormulaExps markFields fWhere
ziv@2274 609 val toSqexp =
ziv@2274 610 fn Sql.SqField tf => Sql.Field tf
ziv@2274 611 | Sql.SqExp (se, _) => se
ziv@2274 612 fun ineq se = Atom (Sql.Ne, se, markFields se)
ziv@2274 613 val fIneqs = Combo (Disj, map (ineq o toSqexp) sitems)
ziv@2274 614 in
ziv@2274 615 (Combo (Conj,
ziv@2274 616 [fWhere,
ziv@2274 617 Combo (Disj,
ziv@2274 618 [Negate fWhereMarked,
ziv@2274 619 Combo (Conj, [fWhereMarked, fIneqs])])]))
ziv@2274 620 end)
ziv@2274 621 end
ziv@2274 622 | Sql.Union (q1, q2) => Combo (Disj, [queryToFormula marker q1, queryToFormula marker q2])
ziv@2273 623
ziv@2274 624 fun valsToFormula (markLeft, markRight) (table, vals) =
ziv@2274 625 Combo (Conj,
ziv@2274 626 map (fn (field, v) => Atom (Sql.Eq, markLeft (Sql.Field (table, field)), markRight v))
ziv@2274 627 vals)
ziv@2273 628
ziv@2274 629 (* TODO: verify logic for insertion and deletion. *)
ziv@2274 630 val rec dmlToFormulaMarker =
ziv@2274 631 fn Sql.Insert (table, vals) => (valsToFormula (id, id) (table, vals), NONE)
ziv@2274 632 | Sql.Delete (table, wher) => (renameTables [(table, "T")] (sqexpToFormula wher), NONE)
ziv@2273 633 | Sql.Update (table, vals, wher) =>
ziv@2273 634 let
ziv@2273 635 val fWhere = sqexpToFormula wher
ziv@2274 636 fun fVals marks = valsToFormula marks (table, vals)
ziv@2273 637 val modifiedFields = SS.addList (SS.empty, map #1 vals)
ziv@2273 638 (* TODO: don't use field name hack. *)
ziv@2274 639 fun markFields table =
ziv@2274 640 fn e as Sql.Field (t, v) => if t = table andalso SS.member (modifiedFields, v)
ziv@2273 641 then Sql.Field (t, v ^ "'")
ziv@2273 642 else e
ziv@2274 643 | Sql.SqNot e => Sql.SqNot (markFields table e)
ziv@2274 644 | Sql.Binop (r, e1, e2) => Sql.Binop (r, markFields table e1, markFields table e2)
ziv@2274 645 | Sql.SqKnown e => Sql.SqKnown (markFields table e)
ziv@2274 646 | Sql.SqFunc (s, e) => Sql.SqFunc (s, markFields table e)
ziv@2273 647 | e => e
ziv@2274 648 val mark = mapFormulaExps (markFields "T")
ziv@2273 649 in
ziv@2274 650 (* Inside renameTables, we mark with table "T". Outside, we use the real table name. *)
ziv@2274 651 (renameTables [(table, "T")]
ziv@2274 652 (Combo (Disj, [Combo (Conj, [fVals (id, markFields "T"), mark fWhere]),
ziv@2274 653 Combo (Conj, [fVals (markFields "T", id), fWhere])])),
ziv@2274 654 SOME (markFields table))
ziv@2273 655 end
ziv@2273 656
ziv@2274 657 fun pairToFormulas (query, dml) =
ziv@2274 658 let
ziv@2274 659 val (fDml, marker) = dmlToFormulaMarker dml
ziv@2274 660 in
ziv@2274 661 (queryToFormula marker query, fDml)
ziv@2274 662 end
ziv@2274 663
ziv@2274 664 (* structure ToFormula = struct *)
ziv@2274 665
ziv@2274 666 (* val testOfQuery : Sql.query1 -> (Sql.cmp * Sql.sqexp * Sql.sqexp) formula = *)
ziv@2274 667 (* fn {From = tablePairs, Where = SOME e, ...} => renameTables tablePairs (sqexpToFormula e) *)
ziv@2274 668 (* | {Where = NONE, ...} => Combo (Conj, []) *)
ziv@2274 669
ziv@2274 670 (* (* If selecting some parsable subset of fields, says which ones. [NONE] *)
ziv@2274 671 (* means anything could be selected. *) *)
ziv@2274 672 (* fun fieldsOfQuery (q : Sql.query1) = *)
ziv@2274 673 (* osequence (map (fn Sql.SqField tf => SOME tf *)
ziv@2274 674 (* | Sql.SqExp (Sql.Field tf) => SOME tf *)
ziv@2274 675 (* | _ => NONE) (#Select q)) *)
ziv@2274 676
ziv@2274 677 (* fun fieldsOfVals (table, vals, wher) = *)
ziv@2274 678 (* let *)
ziv@2274 679 (* val fWhere = renameTables [(table, "T")] (sqexpToFormula wher) *)
ziv@2274 680 (* val fVals = valsToFormula (table, vals) *)
ziv@2274 681 (* val modifiedFields = SS.addList (SS.empty, map #1 vals) *)
ziv@2274 682 (* (* TODO: don't use field name hack. *) *)
ziv@2274 683 (* val markField = *)
ziv@2274 684 (* fn e as Sql.Field (t, v) => if SS.member (modifiedFields, v) *)
ziv@2274 685 (* then Sql.Field (t, v ^ "'") *)
ziv@2274 686 (* else e *)
ziv@2274 687 (* | e => e *)
ziv@2274 688 (* val mark = mapFormula (fn (cmp, e1, e2) => (cmp, markField e1, markField e2)) *)
ziv@2274 689 (* in *)
ziv@2274 690 (* renameTables [(table, "T")] *)
ziv@2274 691 (* (Combo (Disj, [Combo (Conj, [fVals, mark fWhere]), *)
ziv@2274 692 (* Combo (Conj, [mark fVals, fWhere])])) *)
ziv@2274 693 (* end *)
ziv@2274 694 (* end *)
ziv@2273 695
ziv@2235 696 structure ConflictMaps = struct
ziv@2235 697
ziv@2235 698 structure TK = TripleKeyFn(structure I = CmpKey
ziv@2244 699 structure J = AtomOptionKey
ziv@2244 700 structure K = AtomOptionKey)
ziv@2274 701
ziv@2244 702 structure TS : ORD_SET = BinarySetFn(TK)
ziv@2235 703
ziv@2235 704 val toKnownEquality =
ziv@2235 705 (* [NONE] here means unkown. Anything that isn't a comparison between two
ziv@2235 706 knowns shouldn't be used, and simply dropping unused terms is okay in
ziv@2235 707 disjunctive normal form. *)
ziv@2235 708 fn (Sql.Eq, SOME e1, SOME e2) => SOME (e1, e2)
ziv@2235 709 | _ => NONE
ziv@2235 710
ziv@2274 711 fun equivClasses atoms : atomExp list list option =
ziv@2274 712 let
ziv@2274 713 val uf = List.foldl UF.union' UF.empty (List.mapPartial toKnownEquality atoms)
ziv@2274 714 val ineqs = List.filter (fn (cmp, _, _) =>
ziv@2274 715 cmp = Sql.Ne orelse cmp = Sql.Lt orelse cmp = Sql.Gt)
ziv@2274 716 atoms
ziv@2274 717 val contradiction =
ziv@2274 718 fn (cmp, SOME ae1, SOME ae2) => (cmp = Sql.Ne orelse cmp = Sql.Lt orelse cmp = Sql.Gt)
ziv@2274 719 andalso not (UF.together (uf, ae1, ae2))
ziv@2274 720 (* If we don't know one side of the comparision, not a contradiction. *)
ziv@2274 721 | _ => false
ziv@2274 722 in
ziv@2274 723 not (List.exists contradiction atoms) <\oguard\> SOME (UF.classes uf)
ziv@2274 724 end
ziv@2235 725
ziv@2235 726 fun addToEqs (eqs, n, e) =
ziv@2235 727 case IM.find (eqs, n) of
ziv@2235 728 (* Comparing to a constant is probably better than comparing to a
ziv@2235 729 variable? Checking that existing constants match a new ones is
ziv@2235 730 handled by [accumulateEqs]. *)
ziv@2235 731 SOME (Prim _) => eqs
ziv@2235 732 | _ => IM.insert (eqs, n, e)
ziv@2235 733
ziv@2235 734 val accumulateEqs =
ziv@2235 735 (* [NONE] means we have a contradiction. *)
ziv@2235 736 fn (_, NONE) => NONE
ziv@2235 737 | ((Prim p1, Prim p2), eqso) =>
ziv@2235 738 (case Prim.compare (p1, p2) of
ziv@2235 739 EQUAL => eqso
ziv@2235 740 | _ => NONE)
ziv@2235 741 | ((QueryArg n, Prim p), SOME eqs) => SOME (addToEqs (eqs, n, Prim p))
ziv@2235 742 | ((QueryArg n, DmlRel r), SOME eqs) => SOME (addToEqs (eqs, n, DmlRel r))
ziv@2235 743 | ((Prim p, QueryArg n), SOME eqs) => SOME (addToEqs (eqs, n, Prim p))
ziv@2235 744 | ((DmlRel r, QueryArg n), SOME eqs) => SOME (addToEqs (eqs, n, DmlRel r))
ziv@2235 745 (* TODO: deal with equalities between [DmlRel]s and [Prim]s.
ziv@2235 746 This would involve guarding the invalidation with a check for the
ziv@2235 747 relevant comparisons. *)
ziv@2235 748 | (_, eqso) => eqso
ziv@2235 749
ziv@2235 750 val eqsOfClass : atomExp list -> atomExp IM.map option =
ziv@2235 751 List.foldl accumulateEqs (SOME IM.empty)
ziv@2235 752 o chooseTwos
ziv@2235 753
ziv@2235 754 fun toAtomExps rel (cmp, e1, e2) =
ziv@2235 755 let
ziv@2235 756 val qa =
ziv@2235 757 (* Here [NONE] means unkown. *)
ziv@2235 758 fn Sql.SqConst p => SOME (Prim p)
ziv@2235 759 | Sql.Field tf => SOME (Field tf)
ziv@2235 760 | Sql.Inj (EPrim p, _) => SOME (Prim p)
ziv@2235 761 | Sql.Inj (ERel n, _) => SOME (rel n)
ziv@2235 762 (* We can't deal with anything else, e.g., CURRENT_TIMESTAMP
ziv@2235 763 becomes Sql.Unmodeled, which becomes NONE here. *)
ziv@2235 764 | _ => NONE
ziv@2235 765 in
ziv@2235 766 (cmp, qa e1, qa e2)
ziv@2235 767 end
ziv@2235 768
ziv@2244 769 val negateCmp =
ziv@2244 770 fn Sql.Eq => Sql.Ne
ziv@2244 771 | Sql.Ne => Sql.Eq
ziv@2244 772 | Sql.Lt => Sql.Ge
ziv@2244 773 | Sql.Le => Sql.Gt
ziv@2244 774 | Sql.Gt => Sql.Le
ziv@2244 775 | Sql.Ge => Sql.Lt
ziv@2244 776
ziv@2244 777 fun normalizeAtom (negating, (cmp, e1, e2)) =
ziv@2244 778 (* Restricting to Le/Lt and sorting the expressions in Eq/Ne helps with
ziv@2244 779 simplification, where we put the triples in sets. *)
ziv@2244 780 case (if negating then negateCmp cmp else cmp) of
ziv@2244 781 Sql.Eq => (case AtomOptionKey.compare (e1, e2) of
ziv@2244 782 LESS => (Sql.Eq, e2, e1)
ziv@2244 783 | _ => (Sql.Eq, e1, e2))
ziv@2244 784 | Sql.Ne => (case AtomOptionKey.compare (e1, e2) of
ziv@2244 785 LESS => (Sql.Ne, e2, e1)
ziv@2244 786 | _ => (Sql.Ne, e1, e2))
ziv@2244 787 | Sql.Lt => (Sql.Lt, e1, e2)
ziv@2244 788 | Sql.Le => (Sql.Le, e1, e2)
ziv@2244 789 | Sql.Gt => (Sql.Lt, e2, e1)
ziv@2244 790 | Sql.Ge => (Sql.Le, e2, e1)
ziv@2235 791
ziv@2235 792 val markQuery : (Sql.cmp * Sql.sqexp * Sql.sqexp) formula ->
ziv@2235 793 (Sql.cmp * atomExp option * atomExp option) formula =
ziv@2235 794 mapFormula (toAtomExps QueryArg)
ziv@2235 795
ziv@2235 796 val markDml : (Sql.cmp * Sql.sqexp * Sql.sqexp) formula ->
ziv@2235 797 (Sql.cmp * atomExp option * atomExp option) formula =
ziv@2235 798 mapFormula (toAtomExps DmlRel)
ziv@2250 799
ziv@2235 800 (* No eqs should have key conflicts because no variable is in two
ziv@2235 801 equivalence classes, so the [#1] could be [#2]. *)
ziv@2235 802 val mergeEqs : (atomExp IntBinaryMap.map option list
ziv@2235 803 -> atomExp IntBinaryMap.map option) =
ziv@2271 804 List.foldr (omap2 (IM.unionWith #1)) (SOME IM.empty)
ziv@2235 805
ziv@2239 806 val simplify =
ziv@2239 807 map TS.listItems
ziv@2239 808 o removeRedundant (fn (x, y) => TS.isSubset (y, x))
ziv@2239 809 o map (fn xs => TS.addList (TS.empty, xs))
ziv@2239 810
ziv@2235 811 fun dnf (fQuery, fDml) =
ziv@2244 812 normalize simplify normalizeAtom Disj (Combo (Conj, [markQuery fQuery, markDml fDml]))
ziv@2235 813
ziv@2274 814 val conflictMaps =
ziv@2274 815 List.mapPartial (mergeEqs o map eqsOfClass)
ziv@2274 816 o List.mapPartial equivClasses
ziv@2274 817 o dnf
ziv@2235 818
ziv@2235 819 end
ziv@2235 820
ziv@2235 821 val conflictMaps = ConflictMaps.conflictMaps
ziv@2213 822
ziv@2213 823
ziv@2265 824 (*************************************)
ziv@2265 825 (* Program Instrumentation Utilities *)
ziv@2265 826 (*************************************)
ziv@2213 827
ziv@2233 828 val {check, store, flush, ...} = getCache ()
ziv@2233 829
ziv@2248 830 val dummyTyp = (TRecord [], dummyLoc)
ziv@2248 831
ziv@2230 832 fun stringExp s = (EPrim (Prim.String (Prim.Normal, s)), dummyLoc)
ziv@2230 833
ziv@2230 834 val stringTyp = (TFfi ("Basis", "string"), dummyLoc)
ziv@2213 835
ziv@2213 836 val sequence =
ziv@2213 837 fn (exp :: exps) =>
ziv@2213 838 let
ziv@2230 839 val loc = dummyLoc
ziv@2213 840 in
ziv@2213 841 List.foldl (fn (e', seq) => ESeq ((seq, loc), (e', loc))) exp exps
ziv@2213 842 end
ziv@2213 843 | _ => raise Match
ziv@2213 844
ziv@2248 845 (* Always increments negative indices as a hack we use later. *)
ziv@2248 846 fun incRels inc =
ziv@2215 847 MonoUtil.Exp.mapB
ziv@2248 848 {typ = fn t' => t',
ziv@2248 849 exp = fn bound =>
ziv@2248 850 (fn ERel n => ERel (if n >= bound orelse n < 0 then n + inc else n)
ziv@2248 851 | e' => e'),
ziv@2248 852 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1 | (bound, _) => bound}
ziv@2248 853 0
ziv@2213 854
ziv@2262 855 fun fileTopLevelMapfoldB doTopLevelExp (decls, sideInfo) state =
ziv@2262 856 let
ziv@2262 857 fun doVal env ((x, n, t, exp, s), state) =
ziv@2262 858 let
ziv@2262 859 val (exp, state) = doTopLevelExp env exp state
ziv@2262 860 in
ziv@2262 861 ((x, n, t, exp, s), state)
ziv@2262 862 end
ziv@2262 863 fun doDecl' env (decl', state) =
ziv@2262 864 case decl' of
ziv@2262 865 DVal v =>
ziv@2262 866 let
ziv@2262 867 val (v, state) = doVal env (v, state)
ziv@2262 868 in
ziv@2262 869 (DVal v, state)
ziv@2262 870 end
ziv@2262 871 | DValRec vs =>
ziv@2262 872 let
ziv@2262 873 val (vs, state) = ListUtil.foldlMap (doVal env) state vs
ziv@2262 874 in
ziv@2262 875 (DValRec vs, state)
ziv@2262 876 end
ziv@2262 877 | _ => (decl', state)
ziv@2262 878 fun doDecl (decl as (decl', loc), (env, state)) =
ziv@2262 879 let
ziv@2262 880 val env = MonoEnv.declBinds env decl
ziv@2262 881 val (decl', state) = doDecl' env (decl', state)
ziv@2262 882 in
ziv@2262 883 ((decl', loc), (env, state))
ziv@2262 884 end
ziv@2262 885 val (decls, (_, state)) = (ListUtil.foldlMap doDecl (MonoEnv.empty, state) decls)
ziv@2262 886 in
ziv@2262 887 ((decls, sideInfo), state)
ziv@2262 888 end
ziv@2262 889
ziv@2262 890 fun fileAllMapfoldB doExp file start =
ziv@2248 891 case MonoUtil.File.mapfoldB
ziv@2248 892 {typ = Search.return2,
ziv@2250 893 exp = fn env => fn e' => fn s => Search.Continue (doExp env e' s),
ziv@2248 894 decl = fn _ => Search.return2,
ziv@2248 895 bind = doBind}
ziv@2250 896 MonoEnv.empty file start of
ziv@2213 897 Search.Continue x => x
ziv@2213 898 | Search.Return _ => raise Match
ziv@2213 899
ziv@2262 900 fun fileMap doExp file = #1 (fileAllMapfoldB (fn _ => fn e => fn _ => (doExp e, ())) file ())
ziv@2213 901
ziv@2267 902 (* TODO: make this a bit prettier.... *)
ziv@2267 903 val simplifySql =
ziv@2266 904 let
ziv@2267 905 fun factorOutNontrivial text =
ziv@2267 906 let
ziv@2267 907 val loc = dummyLoc
ziv@2267 908 fun strcat (e1, e2) = (EStrcat (e1, e2), loc)
ziv@2267 909 val chunks = Sql.chunkify text
ziv@2267 910 val (newText, newVariables) =
ziv@2267 911 (* Important that this is foldr (to oppose foldl below). *)
ziv@2267 912 List.foldr
ziv@2267 913 (fn (chunk, (qText, newVars)) =>
ziv@2267 914 (* Variable bound to the head of newVars will have the lowest index. *)
ziv@2267 915 case chunk of
ziv@2267 916 (* EPrim should always be a string in this case. *)
ziv@2267 917 Sql.Exp (e as (EPrim _, _)) => (strcat (e, qText), newVars)
ziv@2267 918 | Sql.Exp e =>
ziv@2267 919 let
ziv@2267 920 val n = length newVars
ziv@2267 921 in
ziv@2267 922 (* This is the (n+1)th new variable, so there are
ziv@2267 923 already n new variables bound, so we increment
ziv@2267 924 indices by n. *)
ziv@2267 925 (strcat ((ERel (~(n+1)), loc), qText), incRels n e :: newVars)
ziv@2267 926 end
ziv@2267 927 | Sql.String s => (strcat (stringExp s, qText), newVars))
ziv@2267 928 (stringExp "", [])
ziv@2267 929 chunks
ziv@2267 930 fun wrapLets e' =
ziv@2267 931 (* Important that this is foldl (to oppose foldr above). *)
ziv@2273 932 List.foldl (fn (v, e') => ELet ("sqlArg", stringTyp, v, (e', loc)))
ziv@2267 933 e'
ziv@2267 934 newVariables
ziv@2267 935 val numArgs = length newVariables
ziv@2267 936 in
ziv@2267 937 (newText, wrapLets, numArgs)
ziv@2267 938 end
ziv@2267 939 fun doExp exp' =
ziv@2267 940 let
ziv@2267 941 val text = case exp' of
ziv@2267 942 EQuery {query = text, ...} => text
ziv@2267 943 | EDml (text, _) => text
ziv@2267 944 | _ => raise Match
ziv@2267 945 val (newText, wrapLets, numArgs) = factorOutNontrivial text
ziv@2267 946 val newExp' = case exp' of
ziv@2267 947 EQuery q => EQuery {query = newText,
ziv@2267 948 exps = #exps q,
ziv@2267 949 tables = #tables q,
ziv@2267 950 state = #state q,
ziv@2267 951 body = #body q,
ziv@2267 952 initial = #initial q}
ziv@2267 953 | EDml (_, failureMode) => EDml (newText, failureMode)
ziv@2267 954 | _ => raise Match
ziv@2267 955 in
ziv@2267 956 (* Increment once for each new variable just made. This is
ziv@2267 957 where we use the negative De Bruijn indices hack. *)
ziv@2267 958 (* TODO: please don't use that hack. As anyone could have
ziv@2267 959 predicted, it was incomprehensible a year later.... *)
ziv@2267 960 wrapLets (#1 (incRels numArgs (newExp', dummyLoc)))
ziv@2267 961 end
ziv@2266 962 in
ziv@2267 963 fileMap (fn exp' => case exp' of
ziv@2267 964 EQuery _ => doExp exp'
ziv@2267 965 | EDml _ => doExp exp'
ziv@2267 966 | _ => exp')
ziv@2266 967 end
ziv@2266 968
ziv@2250 969
ziv@2250 970 (**********************)
ziv@2250 971 (* Mono Type Checking *)
ziv@2250 972 (**********************)
ziv@2250 973
ziv@2250 974 fun typOfExp' (env : MonoEnv.env) : exp' -> typ option =
ziv@2250 975 fn EPrim p => SOME (TFfi ("Basis", case p of
ziv@2250 976 Prim.Int _ => "int"
ziv@2250 977 | Prim.Float _ => "double"
ziv@2250 978 | Prim.String _ => "string"
ziv@2250 979 | Prim.Char _ => "char"),
ziv@2250 980 dummyLoc)
ziv@2250 981 | ERel n => SOME (#2 (MonoEnv.lookupERel env n))
ziv@2250 982 | ENamed n => SOME (#2 (MonoEnv.lookupENamed env n))
ziv@2250 983 (* ASK: okay to make a new [ref] each time? *)
ziv@2250 984 | ECon (dk, PConVar nCon, _) =>
ziv@2250 985 let
ziv@2250 986 val (_, _, nData) = MonoEnv.lookupConstructor env nCon
ziv@2250 987 val (_, cs) = MonoEnv.lookupDatatype env nData
ziv@2250 988 in
ziv@2250 989 SOME (TDatatype (nData, ref (dk, cs)), dummyLoc)
ziv@2250 990 end
ziv@2250 991 | ECon (_, PConFfi {mod = s, datatyp, ...}, _) => SOME (TFfi (s, datatyp), dummyLoc)
ziv@2250 992 | ENone t => SOME (TOption t, dummyLoc)
ziv@2250 993 | ESome (t, _) => SOME (TOption t, dummyLoc)
ziv@2250 994 | EFfi _ => NONE
ziv@2250 995 | EFfiApp _ => NONE
ziv@2250 996 | EApp (e1, e2) => (case typOfExp env e1 of
ziv@2250 997 SOME (TFun (_, t), _) => SOME t
ziv@2250 998 | _ => NONE)
ziv@2250 999 | EAbs (_, t1, t2, _) => SOME (TFun (t1, t2), dummyLoc)
ziv@2250 1000 (* ASK: is this right? *)
ziv@2250 1001 | EUnop (unop, e) => (case unop of
ziv@2250 1002 "!" => SOME (TFfi ("Basis", "bool"), dummyLoc)
ziv@2250 1003 | "-" => typOfExp env e
ziv@2250 1004 | _ => NONE)
ziv@2250 1005 (* ASK: how should this (and other "=> NONE" cases) work? *)
ziv@2250 1006 | EBinop _ => NONE
ziv@2250 1007 | ERecord fields => SOME (TRecord (map (fn (s, _, t) => (s, t)) fields), dummyLoc)
ziv@2250 1008 | EField (e, s) => (case typOfExp env e of
ziv@2250 1009 SOME (TRecord fields, _) =>
ziv@2250 1010 (case List.find (fn (s', _) => s = s') fields of
ziv@2250 1011 SOME (_, t) => SOME t
ziv@2250 1012 | _ => NONE)
ziv@2250 1013 | _ => NONE)
ziv@2250 1014 | ECase (_, _, {result, ...}) => SOME result
ziv@2250 1015 | EStrcat _ => SOME (TFfi ("Basis", "string"), dummyLoc)
ziv@2250 1016 | EWrite _ => SOME (TRecord [], dummyLoc)
ziv@2250 1017 | ESeq (_, e) => typOfExp env e
ziv@2250 1018 | ELet (s, t, e1, e2) => typOfExp (MonoEnv.pushERel env s t (SOME e1)) e2
ziv@2250 1019 | EClosure _ => NONE
ziv@2250 1020 | EUnurlify (_, t, _) => SOME t
ziv@2269 1021 | EQuery {state, ...} => SOME state
ziv@2256 1022 | _ => NONE
ziv@2250 1023
ziv@2250 1024 and typOfExp env (e', loc) = typOfExp' env e'
ziv@2250 1025
ziv@2250 1026
ziv@2266 1027 (***********)
ziv@2266 1028 (* Caching *)
ziv@2266 1029 (***********)
ziv@2250 1030
ziv@2267 1031 (*
ziv@2267 1032
ziv@2267 1033 To get the invalidations for a dml, we need (each <- is list-monad-y):
ziv@2267 1034 * table <- dml
ziv@2267 1035 * cache <- table
ziv@2267 1036 * query <- cache
ziv@2267 1037 * inval <- (query, dml),
ziv@2267 1038 where inval is a list of query argument indices, so
ziv@2267 1039 * way to change query args in inval to cache args.
ziv@2267 1040 For now, the last one is just
ziv@2267 1041 * a map from query arg number to the corresponding free variable (per query)
ziv@2267 1042 * a map from free variable to cache arg number (per cache).
ziv@2267 1043 Both queries and caches should have IDs.
ziv@2267 1044
ziv@2267 1045 *)
ziv@2267 1046
ziv@2271 1047 type state = InvalInfo.state
ziv@2271 1048
ziv@2271 1049 datatype subexp = Cachable of InvalInfo.t * (state -> exp * state) | Impure of exp
ziv@2271 1050
ziv@2271 1051 val isImpure =
ziv@2271 1052 fn Cachable _ => false
ziv@2271 1053 | Impure _ => true
ziv@2271 1054
ziv@2271 1055 val runSubexp : subexp * state -> exp * state =
ziv@2271 1056 fn (Cachable (_, f), state) => f state
ziv@2271 1057 | (Impure e, state) => (e, state)
ziv@2271 1058
ziv@2271 1059 val invalInfoOfSubexp =
ziv@2271 1060 fn Cachable (invalInfo, _) => invalInfo
ziv@2271 1061 | Impure _ => raise Match
ziv@2271 1062
ziv@2271 1063 fun cacheWrap (env, exp, typ, args, index) =
ziv@2265 1064 let
ziv@2265 1065 val loc = dummyLoc
ziv@2265 1066 val rel0 = (ERel 0, loc)
ziv@2265 1067 in
ziv@2271 1068 case MonoFooify.urlify env (rel0, typ) of
ziv@2265 1069 NONE => NONE
ziv@2265 1070 | SOME urlified =>
ziv@2265 1071 let
ziv@2265 1072 (* We ensure before this step that all arguments aren't effectful.
ziv@2265 1073 by turning them into local variables as needed. *)
ziv@2265 1074 val argsInc = map (incRels 1) args
ziv@2268 1075 val check = (check (index, args), loc)
ziv@2268 1076 val store = (store (index, argsInc, urlified), loc)
ziv@2265 1077 in
ziv@2271 1078 SOME (ECase (check,
ziv@2271 1079 [((PNone stringTyp, loc),
ziv@2273 1080 (ELet ("q", typ, exp, (ESeq (store, rel0), loc)), loc)),
ziv@2273 1081 ((PSome (stringTyp, (PVar ("hit", stringTyp), loc)), loc),
ziv@2271 1082 (* Boolean is false because we're not unurlifying from a cookie. *)
ziv@2271 1083 (EUnurlify (rel0, typ, false), loc))],
ziv@2271 1084 {disc = (TOption stringTyp, loc), result = typ}))
ziv@2265 1085 end
ziv@2265 1086 end
ziv@2265 1087
ziv@2258 1088 val expSize = MonoUtil.Exp.fold {typ = #2, exp = fn (_, n) => n+1} 0
ziv@2258 1089
ziv@2259 1090 (* TODO: pick a number. *)
ziv@2259 1091 val sizeWorthCaching = 5
ziv@2259 1092
ziv@2269 1093 val worthCaching =
ziv@2269 1094 fn EQuery _ => true
ziv@2269 1095 | exp' => expSize (exp', dummyLoc) > sizeWorthCaching
ziv@2269 1096
ziv@2273 1097 fun cacheExp (env, exp', invalInfo, state : state) =
ziv@2273 1098 case worthCaching exp' <\oguard\> typOfExp' env exp' of
ziv@2269 1099 NONE => NONE
ziv@2269 1100 | SOME (TFun _, _) => NONE
ziv@2269 1101 | SOME typ =>
ziv@2271 1102 let
ziv@2273 1103 val args = InvalInfo.orderArgs (invalInfo, freeVars (exp', dummyLoc))
ziv@2273 1104 val numArgs = length args
ziv@2273 1105 in (List.foldr (fn (arg, acc) =>
ziv@2273 1106 acc
ziv@2273 1107 <\obind\>
ziv@2273 1108 (fn args' =>
ziv@2273 1109 (case arg of
ziv@2273 1110 AsIs exp => SOME exp
ziv@2273 1111 | Urlify exp =>
ziv@2273 1112 typOfExp env exp
ziv@2273 1113 <\obind\>
ziv@2273 1114 (fn typ =>
ziv@2273 1115 (MonoFooify.urlify env (exp, typ))))
ziv@2273 1116 <\obind\>
ziv@2273 1117 (fn arg' => SOME (arg' :: args'))))
ziv@2273 1118 (SOME [])
ziv@2273 1119 args)
ziv@2273 1120 <\obind\>
ziv@2273 1121 (fn args' =>
ziv@2273 1122 cacheWrap (env, (exp', dummyLoc), typ, args', #index state)
ziv@2273 1123 <\obind\>
ziv@2273 1124 (fn cachedExp =>
ziv@2273 1125 SOME (cachedExp, InvalInfo.updateState (invalInfo, numArgs, state))))
ziv@2271 1126 end
ziv@2269 1127
ziv@2271 1128 fun cacheQuery (effs, env, q) : subexp =
ziv@2266 1129 let
ziv@2266 1130 (* We use dummyTyp here. I think this is okay because databases don't
ziv@2266 1131 store (effectful) functions, but perhaps there's some pathalogical
ziv@2266 1132 corner case missing.... *)
ziv@2266 1133 fun safe bound =
ziv@2266 1134 not
ziv@2266 1135 o effectful effs
ziv@2266 1136 (iterate (fn env => MonoEnv.pushERel env "_" dummyTyp NONE)
ziv@2266 1137 bound
ziv@2266 1138 env)
ziv@2271 1139 val {query = queryText, initial, body, ...} = q
ziv@2271 1140 (* DEBUG *)
ziv@2271 1141 (* val () = Print.preface ("sqlcache> ", MonoPrint.p_exp MonoEnv.empty queryText) *)
ziv@2266 1142 val attempt =
ziv@2266 1143 (* Ziv misses Haskell's do notation.... *)
ziv@2267 1144 (safe 0 queryText andalso safe 0 initial andalso safe 2 body)
ziv@2273 1145 <\oguard\>
ziv@2268 1146 Sql.parse Sql.query queryText
ziv@2273 1147 <\obind\>
ziv@2268 1148 (fn queryParsed =>
ziv@2271 1149 let
ziv@2271 1150 val invalInfo = InvalInfo.singleton queryParsed
ziv@2271 1151 fun mkExp state =
ziv@2271 1152 case cacheExp (env, EQuery q, invalInfo, state) of
ziv@2271 1153 NONE => ((EQuery q, dummyLoc), state)
ziv@2271 1154 | SOME (cachedExp, state) => ((cachedExp, dummyLoc), state)
ziv@2271 1155 in
ziv@2271 1156 SOME (Cachable (invalInfo, mkExp))
ziv@2271 1157 end)
ziv@2266 1158 in
ziv@2266 1159 case attempt of
ziv@2271 1160 NONE => Impure (EQuery q, dummyLoc)
ziv@2271 1161 | SOME subexp => subexp
ziv@2266 1162 end
ziv@2266 1163
ziv@2271 1164 fun cacheTree (effs : IS.set) ((env, exp as (exp', loc)), state) =
ziv@2250 1165 let
ziv@2271 1166 fun wrapBindN (f : exp list -> exp')
ziv@2271 1167 (args : ((MonoEnv.env * exp) * unbind) list) =
ziv@2250 1168 let
ziv@2271 1169 val (subexps, state) =
ziv@2271 1170 ListUtil.foldlMap (cacheTree effs)
ziv@2271 1171 state
ziv@2271 1172 (map #1 args)
ziv@2268 1173 fun mkExp state = mapFst (fn exps => (f exps, loc))
ziv@2268 1174 (ListUtil.foldlMap runSubexp state subexps)
ziv@2271 1175 val attempt =
ziv@2271 1176 if List.exists isImpure subexps
ziv@2271 1177 then NONE
ziv@2271 1178 else (List.foldl (omap2 InvalInfo.union)
ziv@2271 1179 (SOME InvalInfo.empty)
ziv@2271 1180 (ListPair.map
ziv@2271 1181 (fn (subexp, (_, unbinds)) =>
ziv@2271 1182 InvalInfo.unbind (invalInfoOfSubexp subexp, unbinds))
ziv@2271 1183 (subexps, args)))
ziv@2273 1184 <\obind\>
ziv@2271 1185 (fn invalInfo =>
ziv@2271 1186 SOME (Cachable (invalInfo,
ziv@2271 1187 fn state =>
ziv@2271 1188 case cacheExp (env,
ziv@2271 1189 f (map (#2 o #1) args),
ziv@2271 1190 invalInfo,
ziv@2271 1191 state) of
ziv@2271 1192 NONE => mkExp state
ziv@2271 1193 | SOME (e', state) => ((e', loc), state)),
ziv@2271 1194 state))
ziv@2250 1195 in
ziv@2271 1196 case attempt of
ziv@2271 1197 SOME (subexp, state) => (subexp, state)
ziv@2271 1198 | NONE => mapFst Impure (mkExp state)
ziv@2250 1199 end
ziv@2250 1200 fun wrapBind1 f arg =
ziv@2250 1201 wrapBindN (fn [arg] => f arg | _ => raise Match) [arg]
ziv@2250 1202 fun wrapBind2 f (arg1, arg2) =
ziv@2250 1203 wrapBindN (fn [arg1, arg2] => f (arg1, arg2) | _ => raise Match) [arg1, arg2]
ziv@2271 1204 fun wrapN f es = wrapBindN f (map (fn e => ((env, e), Unknowns 0)) es)
ziv@2271 1205 fun wrap1 f e = wrapBind1 f ((env, e), Unknowns 0)
ziv@2271 1206 fun wrap2 f (e1, e2) = wrapBind2 f (((env, e1), Unknowns 0), ((env, e2), Unknowns 0))
ziv@2250 1207 in
ziv@2250 1208 case exp' of
ziv@2250 1209 ECon (dk, pc, SOME e) => wrap1 (fn e => ECon (dk, pc, SOME e)) e
ziv@2250 1210 | ESome (t, e) => wrap1 (fn e => ESome (t, e)) e
ziv@2250 1211 | EFfiApp (s1, s2, args) =>
ziv@2258 1212 if ffiEffectful (s1, s2)
ziv@2266 1213 then (Impure exp, state)
ziv@2258 1214 else wrapN (fn es =>
ziv@2258 1215 EFfiApp (s1, s2, ListPair.map (fn (e, (_, t)) => (e, t)) (es, args)))
ziv@2258 1216 (map #1 args)
ziv@2250 1217 | EApp (e1, e2) => wrap2 EApp (e1, e2)
ziv@2250 1218 | EAbs (s, t1, t2, e) =>
ziv@2250 1219 wrapBind1 (fn e => EAbs (s, t1, t2, e))
ziv@2271 1220 ((MonoEnv.pushERel env s t1 NONE, e), Unknowns 1)
ziv@2250 1221 | EUnop (s, e) => wrap1 (fn e => EUnop (s, e)) e
ziv@2250 1222 | EBinop (bi, s, e1, e2) => wrap2 (fn (e1, e2) => EBinop (bi, s, e1, e2)) (e1, e2)
ziv@2250 1223 | ERecord fields =>
ziv@2250 1224 wrapN (fn es => ERecord (ListPair.map (fn (e, (s, _, t)) => (s, e, t)) (es, fields)))
ziv@2250 1225 (map #2 fields)
ziv@2250 1226 | EField (e, s) => wrap1 (fn e => EField (e, s)) e
ziv@2250 1227 | ECase (e, cases, {disc, result}) =>
ziv@2250 1228 wrapBindN (fn (e::es) =>
ziv@2250 1229 ECase (e,
ziv@2250 1230 (ListPair.map (fn (e, (p, _)) => (p, e)) (es, cases)),
ziv@2256 1231 {disc = disc, result = result})
ziv@2256 1232 | _ => raise Match)
ziv@2271 1233 (((env, e), Unknowns 0)
ziv@2271 1234 :: map (fn (p, e) =>
ziv@2271 1235 ((MonoEnv.patBinds env p, e), Unknowns (MonoEnv.patBindsN p)))
ziv@2271 1236 cases)
ziv@2250 1237 | EStrcat (e1, e2) => wrap2 EStrcat (e1, e2)
ziv@2250 1238 (* We record page writes, so they're cachable. *)
ziv@2250 1239 | EWrite e => wrap1 EWrite e
ziv@2250 1240 | ESeq (e1, e2) => wrap2 ESeq (e1, e2)
ziv@2250 1241 | ELet (s, t, e1, e2) =>
ziv@2250 1242 wrapBind2 (fn (e1, e2) => ELet (s, t, e1, e2))
ziv@2271 1243 (((env, e1), Unknowns 0),
ziv@2271 1244 ((MonoEnv.pushERel env s t (SOME e1), e2), Known e1))
ziv@2250 1245 (* ASK: | EClosure (n, es) => ? *)
ziv@2250 1246 | EUnurlify (e, t, b) => wrap1 (fn e => EUnurlify (e, t, b)) e
ziv@2271 1247 | EQuery q => (cacheQuery (effs, env, q), state)
ziv@2269 1248 | _ => (if effectful effs env exp
ziv@2269 1249 then Impure exp
ziv@2271 1250 else Cachable (InvalInfo.empty,
ziv@2271 1251 fn state =>
ziv@2271 1252 case cacheExp (env, exp', InvalInfo.empty, state) of
ziv@2269 1253 NONE => ((exp', loc), state)
ziv@2269 1254 | SOME (exp', state) => ((exp', loc), state)),
ziv@2269 1255 state)
ziv@2256 1256 end
ziv@2256 1257
ziv@2266 1258 fun addCaching file =
ziv@2256 1259 let
ziv@2266 1260 val effs = effectfulDecls file
ziv@2271 1261 fun doTopLevelExp env exp state = runSubexp (cacheTree effs ((env, exp), state))
ziv@2256 1262 in
ziv@2271 1263 (fileTopLevelMapfoldB doTopLevelExp
ziv@2271 1264 file
ziv@2271 1265 {tableToIndices = SIMM.empty,
ziv@2271 1266 indexToInvalInfo = IM.empty,
ziv@2271 1267 ffiInfo = [],
ziv@2271 1268 index = 0},
ziv@2271 1269 effs)
ziv@2265 1270 end
ziv@2265 1271
ziv@2265 1272
ziv@2265 1273 (************)
ziv@2265 1274 (* Flushing *)
ziv@2265 1275 (************)
ziv@2265 1276
ziv@2265 1277 structure Invalidations = struct
ziv@2265 1278
ziv@2265 1279 val loc = dummyLoc
ziv@2265 1280
ziv@2265 1281 val optionAtomExpToExp =
ziv@2265 1282 fn NONE => (ENone stringTyp, loc)
ziv@2265 1283 | SOME e => (ESome (stringTyp,
ziv@2265 1284 (case e of
ziv@2265 1285 DmlRel n => ERel n
ziv@2265 1286 | Prim p => EPrim p
ziv@2265 1287 (* TODO: make new type containing only these two. *)
ziv@2265 1288 | _ => raise Match,
ziv@2265 1289 loc)),
ziv@2265 1290 loc)
ziv@2265 1291
ziv@2265 1292 fun eqsToInvalidation numArgs eqs =
ziv@2269 1293 List.tabulate (numArgs, (fn n => IM.find (eqs, n)))
ziv@2265 1294
ziv@2265 1295 (* Tests if [ys] makes [xs] a redundant cache invalidation. [NONE] here
ziv@2265 1296 represents unknown, which means a wider invalidation. *)
ziv@2265 1297 val rec madeRedundantBy : atomExp option list * atomExp option list -> bool =
ziv@2265 1298 fn ([], []) => true
ziv@2265 1299 | (_ :: xs, NONE :: ys) => madeRedundantBy (xs, ys)
ziv@2265 1300 | (SOME x :: xs, SOME y :: ys) => (case AtomExpKey.compare (x, y) of
ziv@2265 1301 EQUAL => madeRedundantBy (xs, ys)
ziv@2265 1302 | _ => false)
ziv@2265 1303 | _ => false
ziv@2265 1304
ziv@2271 1305 fun invalidations ((invalInfo, numArgs), dml) =
ziv@2271 1306 let
ziv@2271 1307 val query = InvalInfo.query invalInfo
ziv@2271 1308 in
ziv@2271 1309 (map (map optionAtomExpToExp)
ziv@2271 1310 o removeRedundant madeRedundantBy
ziv@2271 1311 o map (eqsToInvalidation numArgs)
ziv@2273 1312 o conflictMaps)
ziv@2274 1313 (pairToFormulas (query, dml))
ziv@2271 1314 end
ziv@2265 1315
ziv@2265 1316 end
ziv@2265 1317
ziv@2265 1318 val invalidations = Invalidations.invalidations
ziv@2265 1319
ziv@2265 1320 (* DEBUG *)
ziv@2265 1321 (* val gunk : ((Sql.query * int) * Sql.dml) list ref = ref [] *)
ziv@2265 1322 (* val gunk' : exp list ref = ref [] *)
ziv@2265 1323
ziv@2273 1324 fun addFlushing ((file, {tableToIndices, indexToInvalInfo, ffiInfo, ...} : state), effs) =
ziv@2265 1325 let
ziv@2265 1326 val flushes = List.concat
ziv@2265 1327 o map (fn (i, argss) => map (fn args => flush (i, args)) argss)
ziv@2265 1328 val doExp =
ziv@2267 1329 fn dmlExp as EDml (dmlText, failureMode) =>
ziv@2265 1330 let
ziv@2265 1331 (* DEBUG *)
ziv@2265 1332 (* val () = gunk' := origDmlText :: !gunk' *)
ziv@2265 1333 (* val () = Print.preface ("SQLCACHE: ", (MonoPrint.p_exp MonoEnv.empty origDmlText)) *)
ziv@2265 1334 val inval =
ziv@2265 1335 case Sql.parse Sql.dml dmlText of
ziv@2265 1336 SOME dmlParsed =>
ziv@2271 1337 SOME (map (fn i => (case IM.find (indexToInvalInfo, i) of
ziv@2271 1338 SOME invalInfo =>
ziv@2271 1339 (i, invalidations (invalInfo, dmlParsed))
ziv@2265 1340 (* TODO: fail more gracefully. *)
ziv@2271 1341 (* This probably means invalidating everything.... *)
ziv@2265 1342 | NONE => raise Match))
ziv@2271 1343 (SIMM.findList (tableToIndices, tableOfDml dmlParsed)))
ziv@2265 1344 | NONE => NONE
ziv@2265 1345 in
ziv@2265 1346 case inval of
ziv@2265 1347 (* TODO: fail more gracefully. *)
ziv@2265 1348 NONE => raise Match
ziv@2267 1349 | SOME invs => sequence (flushes invs @ [dmlExp])
ziv@2265 1350 end
ziv@2265 1351 | e' => e'
ziv@2274 1352 val file = fileMap doExp file
ziv@2274 1353
ziv@2265 1354 in
ziv@2265 1355 (* DEBUG *)
ziv@2265 1356 (* gunk := []; *)
ziv@2268 1357 ffiInfoRef := ffiInfo;
ziv@2274 1358 file
ziv@2265 1359 end
ziv@2265 1360
ziv@2265 1361
ziv@2268 1362 (************************)
ziv@2268 1363 (* Compiler Entry Point *)
ziv@2268 1364 (************************)
ziv@2265 1365
ziv@2265 1366 val inlineSql =
ziv@2265 1367 let
ziv@2265 1368 val doExp =
ziv@2265 1369 (* TODO: EQuery, too? *)
ziv@2265 1370 (* ASK: should this live in [MonoOpt]? *)
ziv@2265 1371 fn EDml ((ECase (disc, cases, {disc = dTyp, ...}), loc), failureMode) =>
ziv@2265 1372 let
ziv@2265 1373 val newCases = map (fn (p, e) => (p, (EDml (e, failureMode), loc))) cases
ziv@2265 1374 in
ziv@2265 1375 ECase (disc, newCases, {disc = dTyp, result = (TRecord [], loc)})
ziv@2265 1376 end
ziv@2265 1377 | e => e
ziv@2265 1378 in
ziv@2265 1379 fileMap doExp
ziv@2265 1380 end
ziv@2265 1381
ziv@2262 1382 fun insertAfterDatatypes ((decls, sideInfo), newDecls) =
ziv@2262 1383 let
ziv@2262 1384 val (datatypes, others) = List.partition (fn (DDatatype _, _) => true | _ => false) decls
ziv@2262 1385 in
ziv@2262 1386 (datatypes @ newDecls @ others, sideInfo)
ziv@2262 1387 end
ziv@2262 1388
ziv@2267 1389 val go' = addFlushing o addCaching o simplifySql o inlineSql
ziv@2256 1390
ziv@2256 1391 fun go file =
ziv@2256 1392 let
ziv@2256 1393 (* TODO: do something nicer than [Sql] being in one of two modes. *)
ziv@2256 1394 val () = (resetFfiInfo (); Sql.sqlcacheMode := true)
ziv@2262 1395 val file = go' file
ziv@2262 1396 (* Important that this happens after [MonoFooify.urlify] calls! *)
ziv@2262 1397 val fmDecls = MonoFooify.getNewFmDecls ()
ziv@2256 1398 val () = Sql.sqlcacheMode := false
ziv@2256 1399 in
ziv@2262 1400 insertAfterDatatypes (file, rev fmDecls)
ziv@2250 1401 end
ziv@2250 1402
ziv@2209 1403 end