comparison src/sqlcache.sml @ 2271:85f91c7452b0

First draft of cache consolidation.
author Ziv Scully <ziv@mit.edu>
date Wed, 21 Oct 2015 09:18:36 -0400
parents f7bc7c11a656
children a3cac6cea625
comparison
equal deleted inserted replaced
2270:1e3ba868f8bf 2271:85f91c7452b0
54 val doBind = 54 val doBind =
55 fn (env, MonoUtil.Exp.RelE (x, t)) => MonoEnv.pushERel env x t NONE 55 fn (env, MonoUtil.Exp.RelE (x, t)) => MonoEnv.pushERel env x t NONE
56 | (env, MonoUtil.Exp.NamedE (x, n, t, eo, s)) => MonoEnv.pushENamed env x n t eo s 56 | (env, MonoUtil.Exp.NamedE (x, n, t, eo, s)) => MonoEnv.pushENamed env x n t eo s
57 | (env, MonoUtil.Exp.Datatype (x, n, cs)) => MonoEnv.pushDatatype env x n cs 57 | (env, MonoUtil.Exp.Datatype (x, n, cs)) => MonoEnv.pushDatatype env x n cs
58 58
59 (***********************) 59 val dummyLoc = ErrorMsg.dummySpan
60 (* General Combinators *) 60
61 (***********************) 61
62 (*********************)
63 (* General Utilities *)
64 (*********************)
62 65
63 (* From the MLton wiki. *) 66 (* From the MLton wiki. *)
64 infixr 3 /> fun f /> y = fn x => f (x, y) (* Right section *) 67 infixr 3 /> fun f /> y = fn x => f (x, y) (* Right section *)
65 infixr 3 </ fun x </ f = f x (* Right application *) 68 infixr 3 </ fun x </ f = f x (* Right application *)
66 69
70 fun mapFst f (x, y) = (f x, y)
71
67 (* Option monad. *) 72 (* Option monad. *)
68 fun obind (x, f) = Option.mapPartial f x 73 fun obind (x, f) = Option.mapPartial f x
69 fun oguard (b, x) = if b then x else NONE 74 fun oguard (b, x) = if b then x else NONE
70 75 fun omap f = fn SOME x => SOME (f x) | _ => NONE
71 fun mapFst f (x, y) = (f x, y) 76 fun omap2 f = fn (SOME x, SOME y) => SOME (f (x,y)) | _ => NONE
72 77 fun osequence ys = List.foldr (omap2 op::) (SOME []) ys
78
79 fun indexOf test =
80 let
81 fun f n =
82 fn [] => NONE
83 | (x::xs) => if test x then SOME n else f (n+1) xs
84 in
85 f 0
86 end
73 87
74 (*******************) 88 (*******************)
75 (* Effect Analysis *) 89 (* Effect Analysis *)
76 (*******************) 90 (*******************)
77 91
287 301
288 end 302 end
289 303
290 structure AtomOptionKey = OptionKeyFn(AtomExpKey) 304 structure AtomOptionKey = OptionKeyFn(AtomExpKey)
291 305
306 val rec tablesOfQuery =
307 fn Sql.Query1 {From = tablePairs, ...} => SS.fromList (map #1 tablePairs)
308 | Sql.Union (q1, q2) => SS.union (tablesOfQuery q1, tablesOfQuery q2)
309
310 val tableOfDml =
311 fn Sql.Insert (tab, _) => tab
312 | Sql.Delete (tab, _) => tab
313 | Sql.Update (tab, _, _) => tab
314
315 val freeVars =
316 MonoUtil.Exp.foldB
317 {typ = #2,
318 exp = fn (bound, ERel n, vars) => if n < bound
319 then vars
320 else IS.add (vars, n - bound)
321 | (_, _, vars) => vars,
322 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1 | (bound, _) => bound}
323 0
324 IS.empty
325
326 datatype unbind = Known of exp | Unknowns of int
327
328 structure InvalInfo :> sig
329 type t
330 type state = {tableToIndices : SIMM.multimap,
331 indexToInvalInfo : (t * int) IntBinaryMap.map,
332 ffiInfo : {index : int, params : int} list,
333 index : int}
334 val empty : t
335 val singleton : Sql.query -> t
336 val query : t -> Sql.query
337 val orderArgs : t * IS.set -> int list
338 val unbind : t * unbind -> t option
339 val union : t * t -> t
340 val updateState : t * int * state -> state
341 end = struct
342
343 type t = Sql.query list
344
345 type state = {tableToIndices : SIMM.multimap,
346 indexToInvalInfo : (t * int) IntBinaryMap.map,
347 ffiInfo : {index : int, params : int} list,
348 index : int}
349
350 val empty = []
351
352 fun singleton q = [q]
353
354 val union = op@
355
356 (* Need lift', etc. because we don't have rank-2 polymorphism. This should
357 probably use a functor, but this works for now. *)
358 fun traverseSqexp (pure, _, lift, _, lift'', lift2, _) f =
359 let
360 val rec tr =
361 fn Sql.SqNot se => lift Sql.SqNot (tr se)
362 | Sql.Binop (r, se1, se2) =>
363 lift2 (fn (trse1, trse2) => Sql.Binop (r, trse1, trse2)) (tr se1, tr se2)
364 | Sql.SqKnown se => lift Sql.SqKnown (tr se)
365 | Sql.Inj (e', loc) => lift'' (fn fe' => Sql.Inj (fe', loc)) (f e')
366 | Sql.SqFunc (s, se) => lift (fn trse => Sql.SqFunc (s, trse)) (tr se)
367 | se => pure se
368 in
369 tr
370 end
371
372 fun traverseQuery (ops as (_, pure', _, lift', _, _, lift2')) f =
373 let
374 val rec mp =
375 fn Sql.Query1 q =>
376 (case #Where q of
377 NONE => pure' (Sql.Query1 q)
378 | SOME se =>
379 lift' (fn mpse => Sql.Query1 {Select = #Select q,
380 From = #From q,
381 Where = SOME mpse})
382 (traverseSqexp ops f se))
383 | Sql.Union (q1, q2) => lift2' Sql.Union (mp q1, mp q2)
384 in
385 mp
386 end
387
388 fun foldMapQuery plus zero = traverseQuery (fn _ => zero,
389 fn _ => zero,
390 fn _ => fn x => x,
391 fn _ => fn x => x,
392 fn _ => fn x => x,
393 fn _ => plus,
394 fn _ => plus)
395
396 val omapQuery = traverseQuery (SOME, SOME, omap, omap, omap, omap2, omap2)
397
398 val varsOfQuery = foldMapQuery IS.union
399 IS.empty
400 (fn e' => freeVars (e', dummyLoc))
401
402 val varsOfList =
403 fn [] => IS.empty
404 | (q::qs) => varsOfQuery (List.foldl Sql.Union q qs)
405
406 fun orderArgs (qs, vars) =
407 let
408 val invalVars = varsOfList qs
409 in
410 (* Put arguments we might invalidate by first. *)
411 IS.listItems invalVars @ IS.listItems (IS.difference (vars, invalVars))
412 end
413
414 (* As a kludge, we rename the variables in the query to correspond to the
415 argument of the cache they're part of. *)
416 val query =
417 fn (q::qs) =>
418 let
419 val q = List.foldl Sql.Union q qs
420 val ns = IS.listItems (varsOfQuery q)
421 val rename =
422 fn ERel n => omap ERel (indexOf (fn n' => n' = n) ns)
423 | _ => raise Match
424 in
425 case omapQuery rename q of
426 SOME q => q
427 (* We should never get NONE because indexOf should never fail. *)
428 | NONE => raise Match
429 end
430 (* We should never reach this case because [updateState] won't put
431 anything in the state if there are no queries. *)
432 | [] => raise Match
433
434 fun unbind1 ub =
435 case ub of
436 Known (e', loc) =>
437 let
438 val replaceRel0 = case e' of
439 ERel m => SOME (ERel m)
440 | _ => NONE
441 in
442 omapQuery (fn ERel 0 => replaceRel0
443 | ERel n => SOME (ERel (n-1))
444 | _ => raise Match)
445 end
446 | Unknowns k =>
447 omapQuery (fn ERel n => if n >= k then NONE else SOME (ERel (n-k))
448 | _ => raise Match)
449
450 fun unbind (qs, ub) =
451 case ub of
452 (* Shortcut if nothing's changing. *)
453 Unknowns 0 => SOME qs
454 | _ => osequence (map (unbind1 ub) qs)
455
456 fun updateState ((qs, numArgs, state as {index, ...}) : t * int * state) =
457 {tableToIndices = List.foldr (fn (q, acc) =>
458 SS.foldl (fn (tab, acc) =>
459 SIMM.insert (acc, tab, index))
460 acc
461 (tablesOfQuery q))
462 (#tableToIndices state)
463 qs,
464 indexToInvalInfo = IM.insert (#indexToInvalInfo state, index, (qs, numArgs)),
465 ffiInfo = {index = index, params = numArgs} :: #ffiInfo state,
466 index = index + 1}
467
468 end
469
292 structure UF = UnionFindFn(AtomExpKey) 470 structure UF = UnionFindFn(AtomExpKey)
293 471
294 structure ConflictMaps = struct 472 structure ConflictMaps = struct
295 473
296 structure TK = TripleKeyFn(structure I = CmpKey 474 structure TK = TripleKeyFn(structure I = CmpKey
386 564
387 (* No eqs should have key conflicts because no variable is in two 565 (* No eqs should have key conflicts because no variable is in two
388 equivalence classes, so the [#1] could be [#2]. *) 566 equivalence classes, so the [#1] could be [#2]. *)
389 val mergeEqs : (atomExp IntBinaryMap.map option list 567 val mergeEqs : (atomExp IntBinaryMap.map option list
390 -> atomExp IntBinaryMap.map option) = 568 -> atomExp IntBinaryMap.map option) =
391 List.foldr (fn (SOME eqs, SOME acc) => SOME (IM.unionWith #1 (eqs, acc)) | _ => NONE) 569 List.foldr (omap2 (IM.unionWith #1)) (SOME IM.empty)
392 (SOME IM.empty)
393 570
394 val simplify = 571 val simplify =
395 map TS.listItems 572 map TS.listItems
396 o removeRedundant (fn (x, y) => TS.isSubset (y, x)) 573 o removeRedundant (fn (x, y) => TS.isSubset (y, x))
397 o map (fn xs => TS.addList (TS.empty, xs)) 574 o map (fn xs => TS.addList (TS.empty, xs))
457 renameTables [(table, "T")] 634 renameTables [(table, "T")]
458 (Combo (Disj, [Combo (Conj, [fVals, mark fWhere]), 635 (Combo (Disj, [Combo (Conj, [fVals, mark fWhere]),
459 Combo (Conj, [mark fVals, fWhere])])) 636 Combo (Conj, [mark fVals, fWhere])]))
460 end 637 end
461 638
462 val rec tablesQuery =
463 fn Sql.Query1 {From = tablePairs, ...} => SS.fromList (map #1 tablePairs)
464 | Sql.Union (q1, q2) => SS.union (tablesQuery q1, tablesQuery q2)
465
466 val tableDml =
467 fn Sql.Insert (tab, _) => tab
468 | Sql.Delete (tab, _) => tab
469 | Sql.Update (tab, _, _) => tab
470
471 639
472 (*************************************) 640 (*************************************)
473 (* Program Instrumentation Utilities *) 641 (* Program Instrumentation Utilities *)
474 (*************************************) 642 (*************************************)
475 643
479 in 647 in
480 fn s => (varNumber := !varNumber + 1; s ^ Int.toString (!varNumber)) 648 fn s => (varNumber := !varNumber + 1; s ^ Int.toString (!varNumber))
481 end 649 end
482 650
483 val {check, store, flush, ...} = getCache () 651 val {check, store, flush, ...} = getCache ()
484
485 val dummyLoc = ErrorMsg.dummySpan
486 652
487 val dummyTyp = (TRecord [], dummyLoc) 653 val dummyTyp = (TRecord [], dummyLoc)
488 654
489 fun stringExp s = (EPrim (Prim.String (Prim.Normal, s)), dummyLoc) 655 fun stringExp s = (EPrim (Prim.String (Prim.Normal, s)), dummyLoc)
490 656
699 * a map from free variable to cache arg number (per cache). 865 * a map from free variable to cache arg number (per cache).
700 Both queries and caches should have IDs. 866 Both queries and caches should have IDs.
701 867
702 *) 868 *)
703 869
704 fun cacheWrap (env, exp, resultTyp, args, state as (_, _, ffiInfo, index)) = 870 type state = InvalInfo.state
871
872 datatype subexp = Cachable of InvalInfo.t * (state -> exp * state) | Impure of exp
873
874 val isImpure =
875 fn Cachable _ => false
876 | Impure _ => true
877
878 val runSubexp : subexp * state -> exp * state =
879 fn (Cachable (_, f), state) => f state
880 | (Impure e, state) => (e, state)
881
882 val invalInfoOfSubexp =
883 fn Cachable (invalInfo, _) => invalInfo
884 | Impure _ => raise Match
885
886 fun cacheWrap (env, exp, typ, args, index) =
705 let 887 let
706 val loc = dummyLoc 888 val loc = dummyLoc
707 val rel0 = (ERel 0, loc) 889 val rel0 = (ERel 0, loc)
708 in 890 in
709 case MonoFooify.urlify env (rel0, resultTyp) of 891 case MonoFooify.urlify env (rel0, typ) of
710 NONE => NONE 892 NONE => NONE
711 | SOME urlified => 893 | SOME urlified =>
712 let 894 let
713 (* We ensure before this step that all arguments aren't effectful. 895 (* We ensure before this step that all arguments aren't effectful.
714 by turning them into local variables as needed. *) 896 by turning them into local variables as needed. *)
715 val argsInc = map (incRels 1) args 897 val argsInc = map (incRels 1) args
716 val check = (check (index, args), loc) 898 val check = (check (index, args), loc)
717 val store = (store (index, argsInc, urlified), loc) 899 val store = (store (index, argsInc, urlified), loc)
718 in 900 in
719 SOME ((ECase 901 SOME (ECase (check,
720 (check, 902 [((PNone stringTyp, loc),
721 [((PNone stringTyp, loc), 903 (ELet (varName "q", typ, exp, (ESeq (store, rel0), loc)), loc)),
722 (ELet (varName "q", resultTyp, exp, (ESeq (store, rel0), loc)), loc)), 904 ((PSome (stringTyp, (PVar (varName "hit", stringTyp), loc)), loc),
723 ((PSome (stringTyp, (PVar (varName "hit", stringTyp), loc)), loc), 905 (* Boolean is false because we're not unurlifying from a cookie. *)
724 (* Boolean is false because we're not unurlifying from a cookie. *) 906 (EUnurlify (rel0, typ, false), loc))],
725 (EUnurlify (rel0, resultTyp, false), loc))], 907 {disc = (TOption stringTyp, loc), result = typ}))
726 {disc = (TOption stringTyp, loc), result = resultTyp})),
727 (#1 state,
728 #2 state,
729 {index = index, params = length args} :: ffiInfo,
730 index + 1))
731 end 908 end
732 end 909 end
733 910
734 val maxFreeVar =
735 MonoUtil.Exp.foldB
736 {typ = #2,
737 exp = fn (bound, ERel n, v) => Int.max (v, n - bound) | (_, _, v) => v,
738 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1 | (bound, _) => bound}
739 0
740 ~1
741
742 val freeVars =
743 IS.listItems
744 o MonoUtil.Exp.foldB
745 {typ = #2,
746 exp = fn (bound, ERel n, vars) => if n < bound
747 then vars
748 else IS.add (vars, n - bound)
749 | (_, _, vars) => vars,
750 bind = fn (bound, MonoUtil.Exp.RelE _) => bound + 1 | (bound, _) => bound}
751 0
752 IS.empty
753
754 val expSize = MonoUtil.Exp.fold {typ = #2, exp = fn (_, n) => n+1} 0 911 val expSize = MonoUtil.Exp.fold {typ = #2, exp = fn (_, n) => n+1} 0
755
756 type state = (SIMM.multimap
757 * (Sql.query * int) IntBinaryMap.map
758 * {index : int, params : int} list
759 * int)
760
761 datatype subexp = Cachable of state -> (exp * state) | Impure of exp
762
763 val isImpure =
764 fn Cachable _ => false
765 | Impure _ => true
766
767 val runSubexp : subexp * state -> exp * state =
768 fn (Cachable f, state) => f state
769 | (Impure e, state) => (e, state)
770 912
771 (* TODO: pick a number. *) 913 (* TODO: pick a number. *)
772 val sizeWorthCaching = 5 914 val sizeWorthCaching = 5
773 915
774 val worthCaching = 916 val worthCaching =
775 fn EQuery _ => true 917 fn EQuery _ => true
776 | exp' => expSize (exp', dummyLoc) > sizeWorthCaching 918 | exp' => expSize (exp', dummyLoc) > sizeWorthCaching
777 919
778 fun cachePure (env, exp', state as (_, _, _, index)) = 920 fun cacheExp ((env, exp', invalInfo, state) : MonoEnv.env * exp' * InvalInfo.t * state) =
779 case (worthCaching exp') 921 case (worthCaching exp')
780 </oguard/> 922 </oguard/>
781 typOfExp' env exp' of 923 typOfExp' env exp' of
782 NONE => NONE 924 NONE => NONE
783 | SOME (TFun _, _) => NONE 925 | SOME (TFun _, _) => NONE
784 | SOME typ => 926 | SOME typ =>
785 (List.foldr (fn (_, NONE) => NONE 927 let
786 | ((n, typ), SOME args) => 928 val ns = InvalInfo.orderArgs (invalInfo, freeVars (exp', dummyLoc))
787 (MonoFooify.urlify env ((ERel n, dummyLoc), typ)) 929 val numArgs = length ns
788 </obind/> 930 in (List.foldr (fn (_, NONE) => NONE
789 (fn arg => SOME (arg :: args))) 931 | ((n, typ), SOME args) =>
790 (SOME []) 932 (MonoFooify.urlify env ((ERel n, dummyLoc), typ))
791 (map (fn n => (n, #2 (MonoEnv.lookupERel env n))) 933 </obind/>
792 (ListMergeSort.sort op> (freeVars (exp', dummyLoc))))) 934 (fn arg => SOME (arg :: args)))
793 </obind/> 935 (SOME [])
794 (fn args => cacheWrap (env, (exp', dummyLoc), typ, args, state)) 936 (map (fn n => (n, #2 (MonoEnv.lookupERel env n))) ns))
795 937 </obind/>
796 fun cacheQuery (effs, env, state, q) : (exp' * state) = 938 (fn args =>
797 let 939 (cacheWrap (env, (exp', dummyLoc), typ, args, #index state))
798 val (tableToIndices, indexToQueryNumArgs, ffiInfo, index) = state 940 </obind/>
799 val {query = queryText, initial, body, ...} = q 941 (fn cachedExp =>
800 val numArgs = maxFreeVar queryText + 1 942 SOME (cachedExp, InvalInfo.updateState (invalInfo, numArgs, state))))
801 (* DEBUG *) 943 end
802 (* val () = Print.preface ("sqlcache> ", MonoPrint.p_exp MonoEnv.empty queryText) *) 944
945 fun cacheQuery (effs, env, q) : subexp =
946 let
803 (* We use dummyTyp here. I think this is okay because databases don't 947 (* We use dummyTyp here. I think this is okay because databases don't
804 store (effectful) functions, but perhaps there's some pathalogical 948 store (effectful) functions, but perhaps there's some pathalogical
805 corner case missing.... *) 949 corner case missing.... *)
806 fun safe bound = 950 fun safe bound =
807 not 951 not
808 o effectful effs 952 o effectful effs
809 (iterate (fn env => MonoEnv.pushERel env "_" dummyTyp NONE) 953 (iterate (fn env => MonoEnv.pushERel env "_" dummyTyp NONE)
810 bound 954 bound
811 env) 955 env)
812 val {state = resultTyp, ...} = q 956 val {query = queryText, initial, body, ...} = q
813 val args = List.tabulate (numArgs, fn n => (ERel n, dummyLoc)) 957 (* DEBUG *)
958 (* val () = Print.preface ("sqlcache> ", MonoPrint.p_exp MonoEnv.empty queryText) *)
814 val attempt = 959 val attempt =
815 (* Ziv misses Haskell's do notation.... *) 960 (* Ziv misses Haskell's do notation.... *)
816 (safe 0 queryText andalso safe 0 initial andalso safe 2 body) 961 (safe 0 queryText andalso safe 0 initial andalso safe 2 body)
817 </oguard/> 962 </oguard/>
818 Sql.parse Sql.query queryText 963 Sql.parse Sql.query queryText
819 </obind/> 964 </obind/>
820 (fn queryParsed => 965 (fn queryParsed =>
821 (cachePure (env, EQuery q, state)) 966 let
822 </obind/> 967 val invalInfo = InvalInfo.singleton queryParsed
823 (fn (cachedExp, state) => 968 fun mkExp state =
824 SOME (cachedExp, 969 case cacheExp (env, EQuery q, invalInfo, state) of
825 (SS.foldr (fn (tab, qi) => SIMM.insert (qi, tab, index)) 970 NONE => ((EQuery q, dummyLoc), state)
826 tableToIndices 971 | SOME (cachedExp, state) => ((cachedExp, dummyLoc), state)
827 (tablesQuery queryParsed), 972 in
828 IM.insert (indexToQueryNumArgs, index, (queryParsed, numArgs)), 973 SOME (Cachable (invalInfo, mkExp))
829 #3 state, 974 end)
830 #4 state))))
831 in 975 in
832 case attempt of 976 case attempt of
833 SOME pair => pair 977 NONE => Impure (EQuery q, dummyLoc)
834 | NONE => (EQuery q, state) 978 | SOME subexp => subexp
835 end 979 end
836 980
837 fun cache (effs : IS.set) ((env, exp as (exp', loc)), state) = 981 fun cacheTree (effs : IS.set) ((env, exp as (exp', loc)), state) =
838 let 982 let
839 fun wrapBindN (f : exp list -> exp') (args : (MonoEnv.env * exp) list) = 983 fun wrapBindN (f : exp list -> exp')
984 (args : ((MonoEnv.env * exp) * unbind) list) =
840 let 985 let
841 val (subexps, state) = ListUtil.foldlMap (cache effs) state args 986 val (subexps, state) =
987 ListUtil.foldlMap (cacheTree effs)
988 state
989 (map #1 args)
842 fun mkExp state = mapFst (fn exps => (f exps, loc)) 990 fun mkExp state = mapFst (fn exps => (f exps, loc))
843 (ListUtil.foldlMap runSubexp state subexps) 991 (ListUtil.foldlMap runSubexp state subexps)
992 val attempt =
993 if List.exists isImpure subexps
994 then NONE
995 else (List.foldl (omap2 InvalInfo.union)
996 (SOME InvalInfo.empty)
997 (ListPair.map
998 (fn (subexp, (_, unbinds)) =>
999 InvalInfo.unbind (invalInfoOfSubexp subexp, unbinds))
1000 (subexps, args)))
1001 </obind/>
1002 (fn invalInfo =>
1003 SOME (Cachable (invalInfo,
1004 fn state =>
1005 case cacheExp (env,
1006 f (map (#2 o #1) args),
1007 invalInfo,
1008 state) of
1009 NONE => mkExp state
1010 | SOME (e', state) => ((e', loc), state)),
1011 state))
844 in 1012 in
845 if List.exists isImpure subexps 1013 case attempt of
846 then mapFst Impure (mkExp state) 1014 SOME (subexp, state) => (subexp, state)
847 else (Cachable (fn state => 1015 | NONE => mapFst Impure (mkExp state)
848 case cachePure (env, f (map #2 args), state) of
849 NONE => mkExp state
850 | SOME (e', state) => ((e', loc), state)),
851 state)
852 end 1016 end
853 fun wrapBind1 f arg = 1017 fun wrapBind1 f arg =
854 wrapBindN (fn [arg] => f arg | _ => raise Match) [arg] 1018 wrapBindN (fn [arg] => f arg | _ => raise Match) [arg]
855 fun wrapBind2 f (arg1, arg2) = 1019 fun wrapBind2 f (arg1, arg2) =
856 wrapBindN (fn [arg1, arg2] => f (arg1, arg2) | _ => raise Match) [arg1, arg2] 1020 wrapBindN (fn [arg1, arg2] => f (arg1, arg2) | _ => raise Match) [arg1, arg2]
857 fun wrapN f es = wrapBindN f (map (fn e => (env, e)) es) 1021 fun wrapN f es = wrapBindN f (map (fn e => ((env, e), Unknowns 0)) es)
858 fun wrap1 f e = wrapBind1 f (env, e) 1022 fun wrap1 f e = wrapBind1 f ((env, e), Unknowns 0)
859 fun wrap2 f (e1, e2) = wrapBind2 f ((env, e1), (env, e2)) 1023 fun wrap2 f (e1, e2) = wrapBind2 f (((env, e1), Unknowns 0), ((env, e2), Unknowns 0))
860 in 1024 in
861 case exp' of 1025 case exp' of
862 ECon (dk, pc, SOME e) => wrap1 (fn e => ECon (dk, pc, SOME e)) e 1026 ECon (dk, pc, SOME e) => wrap1 (fn e => ECon (dk, pc, SOME e)) e
863 | ESome (t, e) => wrap1 (fn e => ESome (t, e)) e 1027 | ESome (t, e) => wrap1 (fn e => ESome (t, e)) e
864 | EFfiApp (s1, s2, args) => 1028 | EFfiApp (s1, s2, args) =>
868 EFfiApp (s1, s2, ListPair.map (fn (e, (_, t)) => (e, t)) (es, args))) 1032 EFfiApp (s1, s2, ListPair.map (fn (e, (_, t)) => (e, t)) (es, args)))
869 (map #1 args) 1033 (map #1 args)
870 | EApp (e1, e2) => wrap2 EApp (e1, e2) 1034 | EApp (e1, e2) => wrap2 EApp (e1, e2)
871 | EAbs (s, t1, t2, e) => 1035 | EAbs (s, t1, t2, e) =>
872 wrapBind1 (fn e => EAbs (s, t1, t2, e)) 1036 wrapBind1 (fn e => EAbs (s, t1, t2, e))
873 (MonoEnv.pushERel env s t1 NONE, e) 1037 ((MonoEnv.pushERel env s t1 NONE, e), Unknowns 1)
874 | EUnop (s, e) => wrap1 (fn e => EUnop (s, e)) e 1038 | EUnop (s, e) => wrap1 (fn e => EUnop (s, e)) e
875 | EBinop (bi, s, e1, e2) => wrap2 (fn (e1, e2) => EBinop (bi, s, e1, e2)) (e1, e2) 1039 | EBinop (bi, s, e1, e2) => wrap2 (fn (e1, e2) => EBinop (bi, s, e1, e2)) (e1, e2)
876 | ERecord fields => 1040 | ERecord fields =>
877 wrapN (fn es => ERecord (ListPair.map (fn (e, (s, _, t)) => (s, e, t)) (es, fields))) 1041 wrapN (fn es => ERecord (ListPair.map (fn (e, (s, _, t)) => (s, e, t)) (es, fields)))
878 (map #2 fields) 1042 (map #2 fields)
881 wrapBindN (fn (e::es) => 1045 wrapBindN (fn (e::es) =>
882 ECase (e, 1046 ECase (e,
883 (ListPair.map (fn (e, (p, _)) => (p, e)) (es, cases)), 1047 (ListPair.map (fn (e, (p, _)) => (p, e)) (es, cases)),
884 {disc = disc, result = result}) 1048 {disc = disc, result = result})
885 | _ => raise Match) 1049 | _ => raise Match)
886 ((env, e) :: map (fn (p, e) => (MonoEnv.patBinds env p, e)) cases) 1050 (((env, e), Unknowns 0)
1051 :: map (fn (p, e) =>
1052 ((MonoEnv.patBinds env p, e), Unknowns (MonoEnv.patBindsN p)))
1053 cases)
887 | EStrcat (e1, e2) => wrap2 EStrcat (e1, e2) 1054 | EStrcat (e1, e2) => wrap2 EStrcat (e1, e2)
888 (* We record page writes, so they're cachable. *) 1055 (* We record page writes, so they're cachable. *)
889 | EWrite e => wrap1 EWrite e 1056 | EWrite e => wrap1 EWrite e
890 | ESeq (e1, e2) => wrap2 ESeq (e1, e2) 1057 | ESeq (e1, e2) => wrap2 ESeq (e1, e2)
891 | ELet (s, t, e1, e2) => 1058 | ELet (s, t, e1, e2) =>
892 wrapBind2 (fn (e1, e2) => ELet (s, t, e1, e2)) 1059 wrapBind2 (fn (e1, e2) => ELet (s, t, e1, e2))
893 ((env, e1), (MonoEnv.pushERel env s t (SOME e1), e2)) 1060 (((env, e1), Unknowns 0),
1061 ((MonoEnv.pushERel env s t (SOME e1), e2), Known e1))
894 (* ASK: | EClosure (n, es) => ? *) 1062 (* ASK: | EClosure (n, es) => ? *)
895 | EUnurlify (e, t, b) => wrap1 (fn e => EUnurlify (e, t, b)) e 1063 | EUnurlify (e, t, b) => wrap1 (fn e => EUnurlify (e, t, b)) e
896 | EQuery q => 1064 | EQuery q => (cacheQuery (effs, env, q), state)
897 let
898 val (exp', state) = cacheQuery (effs, env, state, q)
899 in
900 (Impure (exp', loc), state)
901 end
902 | _ => (if effectful effs env exp 1065 | _ => (if effectful effs env exp
903 then Impure exp 1066 then Impure exp
904 else Cachable (fn state => 1067 else Cachable (InvalInfo.empty,
905 case cachePure (env, exp', state) of 1068 fn state =>
1069 case cacheExp (env, exp', InvalInfo.empty, state) of
906 NONE => ((exp', loc), state) 1070 NONE => ((exp', loc), state)
907 | SOME (exp', state) => ((exp', loc), state)), 1071 | SOME (exp', state) => ((exp', loc), state)),
908 state) 1072 state)
909 end 1073 end
910 1074
911 fun addCaching file = 1075 fun addCaching file =
912 let 1076 let
913 val effs = effectfulDecls file 1077 val effs = effectfulDecls file
914 fun doTopLevelExp env exp state = runSubexp (cache effs ((env, exp), state)) 1078 fun doTopLevelExp env exp state = runSubexp (cacheTree effs ((env, exp), state))
915 in 1079 in
916 ((fileTopLevelMapfoldB doTopLevelExp file (SIMM.empty, IM.empty, [], 0)), effs) 1080 (fileTopLevelMapfoldB doTopLevelExp
1081 file
1082 {tableToIndices = SIMM.empty,
1083 indexToInvalInfo = IM.empty,
1084 ffiInfo = [],
1085 index = 0},
1086 effs)
917 end 1087 end
918 1088
919 1089
920 (************) 1090 (************)
921 (* Flushing *) 1091 (* Flushing *)
949 | _ => false) 1119 | _ => false)
950 | _ => false 1120 | _ => false
951 1121
952 fun eqss (query, dml) = conflictMaps (queryToFormula query, dmlToFormula dml) 1122 fun eqss (query, dml) = conflictMaps (queryToFormula query, dmlToFormula dml)
953 1123
954 fun invalidations ((query, numArgs), dml) = 1124 fun invalidations ((invalInfo, numArgs), dml) =
955 (map (map optionAtomExpToExp) 1125 let
956 o removeRedundant madeRedundantBy 1126 val query = InvalInfo.query invalInfo
957 o map (eqsToInvalidation numArgs) 1127 in
958 o eqss) 1128 (map (map optionAtomExpToExp)
959 (query, dml) 1129 o removeRedundant madeRedundantBy
1130 o map (eqsToInvalidation numArgs)
1131 o eqss)
1132 (query, dml)
1133 end
960 1134
961 end 1135 end
962 1136
963 val invalidations = Invalidations.invalidations 1137 val invalidations = Invalidations.invalidations
964 1138
965 (* DEBUG *) 1139 (* DEBUG *)
966 (* val gunk : ((Sql.query * int) * Sql.dml) list ref = ref [] *) 1140 (* val gunk : ((Sql.query * int) * Sql.dml) list ref = ref [] *)
967 (* val gunk' : exp list ref = ref [] *) 1141 (* val gunk' : exp list ref = ref [] *)
968 1142
969 fun addFlushing ((file, (tableToIndices, indexToQueryNumArgs, ffiInfo, index)), effs) = 1143 fun addFlushing ((file, {tableToIndices, indexToInvalInfo, ffiInfo, index}), effs) =
970 let 1144 let
971 val flushes = List.concat 1145 val flushes = List.concat
972 o map (fn (i, argss) => map (fn args => flush (i, args)) argss) 1146 o map (fn (i, argss) => map (fn args => flush (i, args)) argss)
973 val doExp = 1147 val doExp =
974 fn dmlExp as EDml (dmlText, failureMode) => 1148 fn dmlExp as EDml (dmlText, failureMode) =>
977 (* val () = gunk' := origDmlText :: !gunk' *) 1151 (* val () = gunk' := origDmlText :: !gunk' *)
978 (* val () = Print.preface ("SQLCACHE: ", (MonoPrint.p_exp MonoEnv.empty origDmlText)) *) 1152 (* val () = Print.preface ("SQLCACHE: ", (MonoPrint.p_exp MonoEnv.empty origDmlText)) *)
979 val inval = 1153 val inval =
980 case Sql.parse Sql.dml dmlText of 1154 case Sql.parse Sql.dml dmlText of
981 SOME dmlParsed => 1155 SOME dmlParsed =>
982 SOME (map (fn i => (case IM.find (indexToQueryNumArgs, i) of 1156 SOME (map (fn i => (case IM.find (indexToInvalInfo, i) of
983 SOME queryNumArgs => 1157 SOME invalInfo =>
984 (* DEBUG *) 1158 (i, invalidations (invalInfo, dmlParsed))
985 ((* gunk := (queryNumArgs, dmlParsed) :: !gunk; *)
986 (i, invalidations (queryNumArgs, dmlParsed)))
987 (* TODO: fail more gracefully. *) 1159 (* TODO: fail more gracefully. *)
1160 (* This probably means invalidating everything.... *)
988 | NONE => raise Match)) 1161 | NONE => raise Match))
989 (SIMM.findList (tableToIndices, tableDml dmlParsed))) 1162 (SIMM.findList (tableToIndices, tableOfDml dmlParsed)))
990 | NONE => NONE 1163 | NONE => NONE
991 in 1164 in
992 case inval of 1165 case inval of
993 (* TODO: fail more gracefully. *) 1166 (* TODO: fail more gracefully. *)
994 NONE => raise Match 1167 NONE => raise Match