Mercurial > urweb
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 |