Mercurial > urweb

annotate src/especialize.sml @ 1078:b9321bcefb42

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix new Especialize security bug: do not duplicate free variables as specialized arguments
author Adam Chlipala <adamc@hcoop.net>
date Tue, 15 Dec 2009 13:20:13 -0500
parents a3273bee05a9
children d069b193ed6b
rev   line source
adamc@443 1 (* Copyright (c) 2008, Adam Chlipala
adamc@443 2 * All rights reserved.
adamc@443 3 *
adamc@443 4 * Redistribution and use in source and binary forms, with or without
adamc@443 5 * modification, are permitted provided that the following conditions are met:
adamc@443 6 *
adamc@443 7 * - Redistributions of source code must retain the above copyright notice,
adamc@443 8 * this list of conditions and the following disclaimer.
adamc@443 9 * - Redistributions in binary form must reproduce the above copyright notice,
adamc@443 10 * this list of conditions and the following disclaimer in the documentation
adamc@443 11 * and/or other materials provided with the distribution.
adamc@443 12 * - The names of contributors may not be used to endorse or promote products
adamc@443 13 * derived from this software without specific prior written permission.
adamc@443 14 *
adamc@443 15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
adamc@443 16 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
adamc@443 17 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
adamc@443 18 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
adamc@443 19 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
adamc@443 20 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
adamc@443 21 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
adamc@443 22 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
adamc@443 23 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
adamc@443 24 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
adamc@443 25 * POSSIBILITY OF SUCH DAMAGE.
adamc@443 26 *)
adamc@443 27
adamc@443 28 structure ESpecialize :> ESPECIALIZE = struct
adamc@443 29
adamc@443 30 open Core
adamc@443 31
adamc@443 32 structure E = CoreEnv
adamc@443 33 structure U = CoreUtil
adamc@443 34
adamc@479 35 type skey = exp
adamc@453 36
adamc@453 37 structure K = struct
adamc@479 38 type ord_key = exp list
adamc@479 39 val compare = Order.joinL U.Exp.compare
adamc@443 40 end
adamc@443 41
adamc@453 42 structure KM = BinaryMapFn(K)
adamc@443 43 structure IM = IntBinaryMap
adamc@482 44 structure IS = IntBinarySet
adamc@443 45
adamc@626 46 val freeVars = U.Exp.foldB {kind = fn (_, _, xs) => xs,
adamc@488 47 con = fn (_, _, xs) => xs,
adamc@488 48 exp = fn (bound, e, xs) =>
adamc@488 49 case e of
adamc@488 50 ERel x =>
adamc@488 51 if x >= bound then
adamc@488 52 IS.add (xs, x - bound)
adamc@488 53 else
adamc@488 54 xs
adamc@488 55 | _ => xs,
adamc@488 56 bind = fn (bound, b) =>
adamc@488 57 case b of
adamc@488 58 U.Exp.RelE _ => bound + 1
adamc@488 59 | _ => bound}
adamc@488 60 0 IS.empty
adamc@479 61
adamc@522 62 val isPoly = U.Decl.exists {kind = fn _ => false,
adamc@522 63 con = fn _ => false,
adamc@522 64 exp = fn ECAbs _ => true
adamc@522 65 | _ => false,
adamc@522 66 decl = fn _ => false}
adamc@522 67
adamc@488 68 fun positionOf (v : int, ls) =
adamc@488 69 let
adamc@488 70 fun pof (pos, ls) =
adamc@488 71 case ls of
adamc@488 72 [] => raise Fail "Defunc.positionOf"
adamc@488 73 | v' :: ls' =>
adamc@488 74 if v = v' then
adamc@488 75 pos
adamc@488 76 else
adamc@488 77 pof (pos + 1, ls')
adamc@488 78 in
adamc@488 79 pof (0, ls)
adamc@488 80 end
adamc@488 81
adamc@1077 82 fun squish (untouched, fvs) =
adamc@626 83 U.Exp.mapB {kind = fn _ => fn k => k,
adamc@488 84 con = fn _ => fn c => c,
adamc@488 85 exp = fn bound => fn e =>
adamc@479 86 case e of
adamc@488 87 ERel x =>
adamc@488 88 if x >= bound then
adamc@1077 89 ERel (positionOf (x - bound, fvs) + bound + untouched)
adamc@488 90 else
adamc@488 91 e
adamc@488 92 | _ => e,
adamc@488 93 bind = fn (bound, b) =>
adamc@488 94 case b of
adamc@488 95 U.Exp.RelE _ => bound + 1
adamc@488 96 | _ => bound}
adamc@488 97 0
adamc@453 98
adamc@443 99 type func = {
adamc@443 100 name : string,
adamc@453 101 args : int KM.map,
adamc@443 102 body : exp,
adamc@443 103 typ : con,
adamc@443 104 tag : string
adamc@443 105 }
adamc@443 106
adamc@443 107 type state = {
adamc@443 108 maxName : int,
adamc@443 109 funcs : func IM.map,
adamc@443 110 decls : (string * int * con * exp * string) list
adamc@443 111 }
adamc@443 112
adamc@488 113 fun default (_, x, st) = (x, st)
adamc@443 114
adamc@800 115 structure SS = BinarySetFn(struct
adamc@800 116 type ord_key = string
adamc@800 117 val compare = String.compare
adamc@800 118 end)
adamc@800 119
adamc@800 120 val mayNotSpec = ref SS.empty
adamc@800 121
adamc@453 122 fun specialize' file =
adamc@443 123 let
adamc@488 124 fun bind (env, b) =
adamc@488 125 case b of
adamc@521 126 U.Decl.RelE xt => xt :: env
adamc@521 127 | _ => env
adamc@488 128
adamc@488 129 fun exp (env, e, st : state) =
adamc@482 130 let
adamc@721 131 (*val () = Print.prefaces "exp" [("e", CorePrint.p_exp CoreEnv.empty
adamc@721 132 (e, ErrorMsg.dummySpan))]*)
adamc@721 133
adamc@488 134 fun getApp e =
adamc@482 135 case e of
adamc@488 136 ENamed f => SOME (f, [])
adamc@482 137 | EApp (e1, e2) =>
adamc@488 138 (case getApp (#1 e1) of
adamc@482 139 NONE => NONE
adamc@488 140 | SOME (f, xs) => SOME (f, xs @ [e2]))
adamc@482 141 | _ => NONE
adamc@482 142 in
adamc@482 143 case getApp e of
adamc@721 144 NONE => ((*Print.prefaces "No" [("e", CorePrint.p_exp CoreEnv.empty
adamc@721 145 (e, ErrorMsg.dummySpan))];*)
adamc@721 146 (e, st))
adamc@488 147 | SOME (f, xs) =>
adamc@485 148 case IM.find (#funcs st, f) of
adamc@485 149 NONE => (e, st)
adamc@485 150 | SOME {name, args, body, typ, tag} =>
adamc@488 151 let
adamc@721 152 (*val () = Print.prefaces "Consider" [("e", CorePrint.p_exp CoreEnv.empty
adamc@721 153 (e, ErrorMsg.dummySpan))]*)
adamc@721 154
adamc@488 155 val functionInside = U.Con.exists {kind = fn _ => false,
adamc@488 156 con = fn TFun _ => true
adamc@488 157 | CFfi ("Basis", "transaction") => true
adamc@794 158 | CFfi ("Basis", "eq") => true
adamc@794 159 | CFfi ("Basis", "num") => true
adamc@794 160 | CFfi ("Basis", "ord") => true
adamc@794 161 | CFfi ("Basis", "show") => true
adamc@794 162 | CFfi ("Basis", "read") => true
adamc@794 163 | CFfi ("Basis", "sql_injectable_prim") => true
adamc@794 164 | CFfi ("Basis", "sql_injectable") => true
adamc@488 165 | _ => false}
adamc@488 166 val loc = ErrorMsg.dummySpan
adamc@488 167
adamc@1078 168 fun hasFuncArg t =
adamc@1078 169 case #1 t of
adamc@1078 170 TFun (dom, ran) => functionInside dom orelse hasFuncArg ran
adamc@1078 171 | _ => false
adamc@1078 172
adamc@1078 173 fun findSplit hfa (xs, typ, fxs, fvs, ts) =
adamc@488 174 case (#1 typ, xs) of
adamc@488 175 (TFun (dom, ran), e :: xs') =>
adamc@1078 176 let
adamc@1078 177 val isVar = case #1 e of
adamc@1078 178 ERel _ => true
adamc@1078 179 | _ => false
adamc@1078 180 val hfa = hfa andalso isVar
adamc@1078 181 in
adamc@1078 182 if hfa orelse functionInside dom then
adamc@1078 183 findSplit hfa (xs',
adamc@1078 184 ran,
adamc@1078 185 (true, e) :: fxs,
adamc@1078 186 IS.union (fvs, freeVars e),
adamc@1078 187 ts)
adamc@1078 188 else
adamc@1078 189 findSplit hfa (xs', ran, (false, e) :: fxs, fvs, dom :: ts)
adamc@1078 190 end
adamc@1077 191 | _ => (List.revAppend (fxs, map (fn e => (false, e)) xs), fvs, rev ts)
adamc@488 192
adamc@1078 193 val (xs, fvs, ts) = findSplit (hasFuncArg typ) (xs, typ, [], IS.empty, [])
adamc@1077 194 val fxs = List.mapPartial (fn (true, e) => SOME e | _ => NONE) xs
adamc@1077 195 val untouched = length (List.filter (fn (false, _) => true | _ => false) xs)
adamc@1077 196 val squish = squish (untouched, IS.listItems fvs)
adamc@1077 197 val fxs' = map squish fxs
adamc@488 198 in
adamc@800 199 (*Print.preface ("fxs'", Print.p_list (CorePrint.p_exp CoreEnv.empty) fxs');*)
adamc@1077 200 if List.all (fn (false, _) => true
adamc@1077 201 | (true, (ERel _, _)) => true
adamc@1077 202 | _ => false) xs then
adamc@488 203 (e, st)
adamc@488 204 else
adamc@800 205 case (KM.find (args, fxs'), SS.member (!mayNotSpec, name)) of
adamc@800 206 (SOME f', _) =>
adamc@485 207 let
adamc@488 208 val e = (ENamed f', loc)
adamc@488 209 val e = IS.foldr (fn (arg, e) => (EApp (e, (ERel arg, loc)), loc))
adamc@488 210 e fvs
adamc@1077 211 val e = foldl (fn ((false, arg), e) => (EApp (e, arg), loc)
adamc@1077 212 | (_, e) => e)
adamc@488 213 e xs
adamc@488 214 in
adamc@488 215 (*Print.prefaces "Brand new (reuse)"
adamc@721 216 [("e'", CorePrint.p_exp CoreEnv.empty e)];*)
adamc@488 217 (#1 e, st)
adamc@488 218 end
adamc@818 219 | (_, true) => ((*Print.prefaces ("No(" ^ name ^ ")")
adamc@818 220 [("fxs'",
adamc@818 221 Print.p_list (CorePrint.p_exp CoreEnv.empty) fxs')];*)
adamc@818 222 (e, st))
adamc@800 223 | (NONE, false) =>
adamc@488 224 let
adamc@800 225 (*val () = Print.prefaces "New one"
adamc@800 226 [("f", Print.PD.string (Int.toString f)),
adamc@800 227 ("mns", Print.p_list Print.PD.string
adamc@800 228 (SS.listItems (!mayNotSpec)))]*)
adamc@800 229
adamc@818 230 (*val () = Print.prefaces ("Yes(" ^ name ^ ")")
adamc@818 231 [("fxs'",
adamc@818 232 Print.p_list (CorePrint.p_exp CoreEnv.empty) fxs')]*)
adamc@818 233
adamc@1077 234 fun subBody (body, typ, xs) =
adamc@1077 235 case (#1 body, #1 typ, xs) of
adamc@488 236 (_, _, []) => SOME (body, typ)
adamc@1077 237 | (EAbs (_, _, _, body'), TFun (_, typ'), (b, x) :: xs) =>
adamc@488 238 let
adamc@1077 239 val body'' =
adamc@1077 240 if b then
adamc@1077 241 E.subExpInExp (0, squish x) body'
adamc@1077 242 else
adamc@1077 243 body'
adamc@488 244 in
adamc@488 245 subBody (body'',
adamc@488 246 typ',
adamc@1077 247 xs)
adamc@488 248 end
adamc@488 249 | _ => NONE
adamc@488 250 in
adamc@1077 251 case subBody (body, typ, xs) of
adamc@488 252 NONE => (e, st)
adamc@488 253 | SOME (body', typ') =>
adamc@488 254 let
adamc@488 255 val f' = #maxName st
adamc@488 256 val args = KM.insert (args, fxs', f')
adamc@488 257 val funcs = IM.insert (#funcs st, f, {name = name,
adamc@488 258 args = args,
adamc@488 259 body = body,
adamc@488 260 typ = typ,
adamc@488 261 tag = tag})
adamc@488 262 val st = {
adamc@488 263 maxName = f' + 1,
adamc@488 264 funcs = funcs,
adamc@488 265 decls = #decls st
adamc@488 266 }
adamc@487 267
adamc@488 268 (*val () = Print.prefaces "specExp"
adamc@488 269 [("f", CorePrint.p_exp env (ENamed f, loc)),
adamc@488 270 ("f'", CorePrint.p_exp env (ENamed f', loc)),
adamc@488 271 ("xs", Print.p_list (CorePrint.p_exp env) xs),
adamc@488 272 ("fxs'", Print.p_list
adamc@488 273 (CorePrint.p_exp E.empty) fxs'),
adamc@488 274 ("e", CorePrint.p_exp env (e, loc))]*)
adamc@1077 275
adamc@1077 276 val (body', typ') = foldr (fn (t, (body', typ')) =>
adamc@1077 277 ((EAbs ("x", t, typ', body'), loc),
adamc@1077 278 (TFun (t, typ'), loc)))
adamc@1077 279 (body', typ') ts
adamc@1077 280
adamc@488 281 val (body', typ') = IS.foldl (fn (n, (body', typ')) =>
adamc@488 282 let
adamc@521 283 val (x, xt) = List.nth (env, n)
adamc@488 284 in
adamc@488 285 ((EAbs (x, xt, typ', body'),
adamc@488 286 loc),
adamc@488 287 (TFun (xt, typ'), loc))
adamc@488 288 end)
adamc@488 289 (body', typ') fvs
adamc@800 290 val mns = !mayNotSpec
adamc@800 291 val () = mayNotSpec := SS.add (mns, name)
adamc@800 292 (*val () = Print.preface ("body'", CorePrint.p_exp CoreEnv.empty body')*)
adamc@488 293 val (body', st) = specExp env st body'
adamc@800 294 val () = mayNotSpec := mns
adamc@482 295
adamc@488 296 val e' = (ENamed f', loc)
adamc@488 297 val e' = IS.foldr (fn (arg, e) => (EApp (e, (ERel arg, loc)), loc))
adamc@488 298 e' fvs
adamc@1077 299 val e' = foldl (fn ((false, arg), e) => (EApp (e, arg), loc)
adamc@1077 300 | (_, e) => e)
adamc@488 301 e' xs
adamc@488 302 (*val () = Print.prefaces "Brand new"
adamc@721 303 [("e'", CorePrint.p_exp CoreEnv.empty e'),
adamc@721 304 ("e", CorePrint.p_exp CoreEnv.empty (e, loc)),
adamc@721 305 ("body'", CorePrint.p_exp CoreEnv.empty body')]*)
adamc@488 306 in
adamc@488 307 (#1 e',
adamc@488 308 {maxName = #maxName st,
adamc@488 309 funcs = #funcs st,
adamc@488 310 decls = (name, f', typ', body', tag) :: #decls st})
adamc@488 311 end
adamc@485 312 end
adamc@488 313 end
adamc@485 314 end
adamc@482 315
adamc@626 316 and specExp env = U.Exp.foldMapB {kind = default, con = default, exp = exp, bind = bind} env
adamc@482 317
adamc@626 318 val specDecl = U.Decl.foldMapB {kind = default, con = default, exp = exp, decl = default, bind = bind}
adamc@482 319
adamc@521 320 fun doDecl (d, (st : state, changed)) =
adamc@488 321 let
adamc@521 322 (*val befor = Time.now ()*)
adamc@482 323
adamc@453 324 val funcs = #funcs st
adamc@453 325 val funcs =
adamc@453 326 case #1 d of
adamc@453 327 DValRec vis =>
adamc@453 328 foldl (fn ((x, n, c, e, tag), funcs) =>
adamc@453 329 IM.insert (funcs, n, {name = x,
adamc@453 330 args = KM.empty,
adamc@453 331 body = e,
adamc@453 332 typ = c,
adamc@453 333 tag = tag}))
adamc@453 334 funcs vis
adamc@453 335 | _ => funcs
adamc@453 336
adamc@453 337 val st = {maxName = #maxName st,
adamc@453 338 funcs = funcs,
adamc@453 339 decls = []}
adamc@453 340
adamc@482 341 (*val () = Print.prefaces "decl" [("d", CorePrint.p_decl CoreEnv.empty d)]*)
adamc@521 342
adamc@522 343 val (d', st) =
adamc@522 344 if isPoly d then
adamc@522 345 (d, st)
adamc@522 346 else
adamc@1078 347 (mayNotSpec := SS.empty(*(case #1 d of
adamc@800 348 DValRec vis => foldl (fn ((x, _, _, _, _), mns) =>
adamc@800 349 SS.add (mns, x)) SS.empty vis
adamc@800 350 | DVal (x, _, _, _, _) => SS.singleton x
adamc@1078 351 | _ => SS.empty)*);
adamc@800 352 specDecl [] st d
adamc@800 353 before mayNotSpec := SS.empty)
adamc@521 354
adamc@482 355 (*val () = print "/decl\n"*)
adamc@443 356
adamc@443 357 val funcs = #funcs st
adamc@443 358 val funcs =
adamc@443 359 case #1 d of
adamc@443 360 DVal (x, n, c, e as (EAbs _, _), tag) =>
adamc@443 361 IM.insert (funcs, n, {name = x,
adamc@453 362 args = KM.empty,
adamc@443 363 body = e,
adamc@443 364 typ = c,
adamc@443 365 tag = tag})
adamc@469 366 | DVal (_, n, _, (ENamed n', _), _) =>
adamc@469 367 (case IM.find (funcs, n') of
adamc@469 368 NONE => funcs
adamc@469 369 | SOME v => IM.insert (funcs, n, v))
adamc@443 370 | _ => funcs
adamc@443 371
adamc@453 372 val (changed, ds) =
adamc@443 373 case #decls st of
adamc@453 374 [] => (changed, [d'])
adamc@453 375 | vis =>
adamc@453 376 (true, case d' of
adamc@453 377 (DValRec vis', _) => [(DValRec (vis @ vis'), ErrorMsg.dummySpan)]
adamc@453 378 | _ => [(DValRec vis, ErrorMsg.dummySpan), d'])
adamc@443 379 in
adamc@802 380 (*Print.prefaces "doDecl" [("d", CorePrint.p_decl E.empty d),
adamc@802 381 ("d'", CorePrint.p_decl E.empty d')];*)
adamc@521 382 (ds, ({maxName = #maxName st,
adamc@453 383 funcs = funcs,
adamc@453 384 decls = []}, changed))
adamc@443 385 end
adamc@443 386
adamc@521 387 val (ds, (_, changed)) = ListUtil.foldlMapConcat doDecl
adamc@521 388 ({maxName = U.File.maxName file + 1,
adamc@488 389 funcs = IM.empty,
adamc@488 390 decls = []},
adamc@488 391 false)
adamc@488 392 file
adamc@443 393 in
adamc@453 394 (changed, ds)
adamc@443 395 end
adamc@443 396
adamc@453 397 fun specialize file =
adamc@453 398 let
adamc@721 399 val file = ReduceLocal.reduce file
adamc@721 400 (*val () = Print.prefaces "Intermediate" [("file", CorePrint.p_file CoreEnv.empty file)]*)
adamc@520 401 (*val file = ReduceLocal.reduce file*)
adamc@453 402 val (changed, file) = specialize' file
adamc@520 403 (*val file = ReduceLocal.reduce file
adamc@520 404 val file = CoreUntangle.untangle file
adamc@488 405 val file = Shake.shake file*)
adamc@453 406 in
adamc@488 407 (*print "Round over\n";*)
adamc@453 408 if changed then
adamc@520 409 let
adamc@721 410 (*val file = ReduceLocal.reduce file*)
adamc@802 411 (*val () = Print.prefaces "Pre-untangle" [("file", CorePrint.p_file CoreEnv.empty file)]*)
adamc@520 412 val file = CoreUntangle.untangle file
adamc@802 413 (*val () = Print.prefaces "Post-untangle" [("file", CorePrint.p_file CoreEnv.empty file)]*)
adamc@520 414 val file = Shake.shake file
adamc@520 415 in
adamc@520 416 (*print "Again!\n";*)
adamc@520 417 specialize file
adamc@520 418 end
adamc@453 419 else
adamc@453 420 file
adamc@453 421 end
adamc@453 422
adamc@443 423 end