viewcvs.cgi/compile/compile.ml

open Ident
open Lambda

type env = {
  vars: var_loc Env.t;
  stack_size: int
}

let dump ppf env =
  Env.iter 
    (fun id loc ->
       Format.fprintf ppf "Var %a : %a@\n" U.print (Id.value id) Lambda.print_var_loc loc)
    env.vars


let empty = { vars = Env.empty; stack_size = 0 }

let serialize s env =
  Serialize.Put.env Id.serialize Lambda.Put.var_loc Env.iter s env.vars;
  Serialize.Put.int s env.stack_size    

let deserialize s =
  let vars = 
    Serialize.Get.env Id.deserialize Lambda.Get.var_loc Env.add Env.empty s in
  let size = Serialize.Get.int s in
  { vars = vars; stack_size = size }


let find x env =
  try Env.find x env.vars
  with Not_found -> 
    failwith ("Compile: cannot find " ^ (Ident.to_string x))

let from_comp_unit = ref (fun cu -> assert false)

let find_ext cu x =
  let env = !from_comp_unit cu in
  match find x env with
    | Global i -> ExtVar (cu,i)
    | _ -> assert false

let rec compile env tail e = compile_aux env tail e.Typed.exp_descr
and compile_aux env tail = function
  | Typed.Forget (e,_) -> compile env tail e
  | Typed.Var x -> Var (find x env)
  | Typed.ExtVar (cu,x) -> find_ext cu x
  | Typed.Apply (e1,e2) -> Apply (tail, compile env false e1, compile env tail e2)
  | Typed.Abstraction a -> compile_abstr env a
  | Typed.Cst c -> Const c
  | Typed.Pair (e1,e2) -> Pair(compile env false e1, compile env tail e2)
  | Typed.Xml (e1, { Typed.exp_descr = Typed.Pair (e2,e3) }) -> 
      Xml (compile env false e1, compile env false e2, compile env tail e3)
  | Typed.Xml (_,_) -> assert false
  | Typed.RecordLitt r -> Record (LabelMap.map (compile env false) r)
  | Typed.String (i,j,s,q) -> String (i,j,s,compile env tail q)
  | Typed.Match (e,brs) -> Match (compile env false e, compile_branches env tail brs)
  | Typed.Map (e,brs) -> Map (compile env false e, compile_branches env false brs)
  | Typed.Transform (e,brs) -> Transform 
      (compile env false e, compile_branches env false brs)
  | Typed.Xtrans (e,brs) -> Xtrans (compile env false e, compile_branches env false brs)
  | Typed.Validate (e,k,sch,t) -> Validate (compile env tail e, k, sch, t)
  | Typed.RemoveField (e,l) -> RemoveField (compile env tail e,l)
  | Typed.Dot (e,l) -> Dot (compile env tail e, l)
  | Typed.Try (e,brs) -> Try (compile env false e, compile_branches env tail brs)
  | Typed.UnaryOp (op,e) -> UnaryOp (op, compile env tail e)
  | Typed.BinaryOp (op,e1,e2) -> BinaryOp (op, compile env false e1, compile env tail e2)
  | Typed.Ref (e,t) ->  Ref (compile env tail e, t)

and compile_abstr env a =
  let fun_env = 
    match a.Typed.fun_name with
      | Some x -> Env.add x (Env 0) Env.empty
      | None -> Env.empty in

  let (slots,nb_slots,fun_env) = 
    List.fold_left 
      (fun (slots,nb_slots,fun_env) x ->
         match find x env with
           | (Stack _ | Env _) as p -> 
               p::slots,
               succ nb_slots,
               Env.add x (Env nb_slots) fun_env;
           | Global _ as p -> 
               slots,
               nb_slots,
               Env.add x p fun_env
           | Dummy -> assert false
      )
      ([Dummy],1,fun_env) (IdSet.get a.Typed.fun_fv) in


  let slots = Array.of_list (List.rev slots) in  
  let env = { vars = fun_env; stack_size = 0 } in
  let body = compile_branches env true a.Typed.fun_body in
  Abstraction (slots, a.Typed.fun_iface, body)

and compile_branches env tail (brs : Typed.branches) =
  (* Don't compile unused branches, because they have not been
     type checked. *)
  let used = List.filter (fun br -> br.Typed.br_used) brs.Typed.br_branches in
  { 
    brs = List.map (compile_branch env tail) used;
    brs_tail = tail;
    brs_accept_chars = not (Types.Char.is_empty brs.Typed.br_accept);
    brs_input = brs.Typed.br_typ;
    brs_compiled = None
  }

and compile_branch env tail br =
  let env = 
    List.fold_left 
      (fun env x ->
         { vars = Env.add x (Stack env.stack_size) env.vars;
           stack_size = env.stack_size + 1 }

      ) env (Patterns.fv_list br.Typed.br_pat) in
  (br.Typed.br_pat, compile env tail br.Typed.br_body)


let enter_global env x =
  { vars = Env.add x (Global env.stack_size) env.vars;
    stack_size = env.stack_size + 1 }

let enter_globals = List.fold_left enter_global

let compile_eval env e = Eval (compile env false e)

let compile_let_decl env decl =
  let pat = decl.Typed.let_pat in
  let code = Let_decl (pat, compile env false (decl.Typed.let_body)) in
  let env = enter_globals env (Patterns.fv_list pat) in
  (env, code)


let compile_rec_funs env funs =
  let fun_name = function
    | { Typed.exp_descr=Typed.Abstraction{Typed.fun_name = Some x}} -> x
    | _ -> assert false in
  let fun_a = function
    | { Typed.exp_descr=Typed.Abstraction a } -> a
    | _ -> assert false in
  let names = List.map fun_name funs in
  let env = enter_globals env names in
  let exprs = List.map (compile_abstr env) (List.map fun_a funs) in
  (env, Let_funs exprs)


(****************************************)

open Location

let eval ~run ~show (tenv,cenv,codes) e =
  let (e,t) = Typer.type_expr tenv e in
  let code = compile_eval cenv e in
  if run then
    let v = Eval.expr code in
    show None t (Some v)
  else
    show None t None;
  (tenv,cenv,code::codes)

let run_show ~run ~show tenv cenv code ids =
  if run then
    let () = Eval.eval code in
    List.iter 
      (fun (id,_) -> show (Some id) 
         (Typer.find_value id tenv)
         (Some (Eval.var (find id cenv)))) ids
  else
    List.iter 
      (fun (id,_) -> show (Some id) 
         (Typer.find_value id tenv)
         None) ids
  
let let_decl ~run ~show (tenv,cenv,codes) p e =
  let (tenv,decl,ids) = Typer.type_let_decl tenv p e in
  let (cenv,code) = compile_let_decl cenv decl in
  run_show ~run ~show tenv cenv code ids;
  (tenv,cenv,code::codes)
  
let let_funs ~run ~show (tenv,cenv,codes) funs =
  let (tenv,funs,ids) = Typer.type_let_funs tenv funs in
  let (cenv,code) = compile_rec_funs cenv funs in
  run_show ~run ~show tenv cenv code ids;
  (tenv,cenv,code::codes)
  
let type_defs (tenv,cenv,codes) typs =
  let tenv = Typer.enter_types (Typer.type_defs tenv typs) tenv in
  (tenv,cenv,codes)

let namespace (tenv,cenv,codes) pr ns =
  let tenv = Typer.enter_ns pr ns tenv in
  (tenv,cenv,codes)

let using (tenv,cenv,codes) x cu =
  let tenv = Typer.enter_cu x cu tenv in
  (tenv,cenv,codes)

let rec collect_funs accu = function
  | { descr = Ast.FunDecl e } :: rest -> collect_funs (e::accu) rest
  | rest -> (accu,rest)

let rec collect_types accu = function
  | { descr = Ast.TypeDecl (x,t) } :: rest -> 
      collect_types ((x,t) :: accu) rest
  | rest -> (accu,rest)

let rec phrases ~run ~show ~loading ~directive =
  let rec loop accu phs =
    match phs with
      | { descr = Ast.FunDecl _ } :: _ -> 
          let (funs,rest) = collect_funs [] phs in
          loop (let_funs ~run ~show accu funs) rest
      | { descr = Ast.TypeDecl (_,_) } :: _ ->
          let (typs,rest) = collect_types [] phs in
          loop (type_defs accu typs) rest
      | { descr = Ast.SchemaDecl (name, schema) } :: rest ->
          Typer.register_schema name schema;
          loop accu rest
      | { descr = Ast.Namespace (pr,ns) } :: rest ->
          loop (namespace accu pr ns) rest
      | { descr = Ast.Using (x,cu) } :: rest ->
          loading cu;
          loop (using accu x cu) rest
      | { descr = Ast.EvalStatement e } :: rest ->
          loop (eval ~run ~show accu e) rest
      | { descr = Ast.LetDecl (p,e) } :: rest ->
          loop (let_decl ~run ~show accu p e) rest
      | { descr = Ast.Directive d } :: rest ->
          let (tenv,cenv,_) = accu in
          directive tenv cenv d;
          loop accu rest
      | [] -> 
          accu
  in
  loop

let comp_unit ?(run=false) 
  ?(show=fun _ _ _ -> ()) 
  ?(loading=fun _ -> ())
  ?(directive=fun _ _ _ -> ())  tenv cenv phs =
  let (tenv,cenv,codes) = phrases ~run ~show ~loading ~directive (tenv,cenv,[]) phs in
  (tenv,cenv,List.rev codes)
1	open Ident
2	open Lambda
3
4	type env = {
5	vars: var_loc Env.t;
6	stack_size: int
7	}
8
9	let dump ppf env =
10	Env.iter
11	(fun id loc ->
12	Format.fprintf ppf "Var %a : %a@\n" U.print (Id.value id) Lambda.print_var_loc loc)
13	env.vars
14
15
16	let empty = { vars = Env.empty; stack_size = 0 }
17
18	let serialize s env =
19	Serialize.Put.env Id.serialize Lambda.Put.var_loc Env.iter s env.vars;
20	Serialize.Put.int s env.stack_size
21
22	let deserialize s =
23	let vars =
24	Serialize.Get.env Id.deserialize Lambda.Get.var_loc Env.add Env.empty s in
25	let size = Serialize.Get.int s in
26	{ vars = vars; stack_size = size }
27
28
29
30
31	let find x env =
32	try Env.find x env.vars
33	with Not_found ->
34	failwith ("Compile: cannot find " ^ (Ident.to_string x))
35
36	let from_comp_unit = ref (fun cu -> assert false)
37
38	let find_ext cu x =
39	let env = !from_comp_unit cu in
40	match find x env with
41	\| Global i -> ExtVar (cu,i)
42	\| _ -> assert false
43
44	let rec compile env tail e = compile_aux env tail e.Typed.exp_descr
45	and compile_aux env tail = function
46	\| Typed.Forget (e,_) -> compile env tail e
47	\| Typed.Var x -> Var (find x env)
48	\| Typed.ExtVar (cu,x) -> find_ext cu x
49	\| Typed.Apply (e1,e2) -> Apply (tail, compile env false e1, compile env tail e2)
50	\| Typed.Abstraction a -> compile_abstr env a
51	\| Typed.Cst c -> Const c
52	\| Typed.Pair (e1,e2) -> Pair(compile env false e1, compile env tail e2)
53	\| Typed.Xml (e1, { Typed.exp_descr = Typed.Pair (e2,e3) }) ->
54	Xml (compile env false e1, compile env false e2, compile env tail e3)
55	\| Typed.Xml (_,_) -> assert false
56	\| Typed.RecordLitt r -> Record (LabelMap.map (compile env false) r)
57	\| Typed.String (i,j,s,q) -> String (i,j,s,compile env tail q)
58	\| Typed.Match (e,brs) -> Match (compile env false e, compile_branches env tail brs)
59	\| Typed.Map (e,brs) -> Map (compile env false e, compile_branches env false brs)
60	\| Typed.Transform (e,brs) -> Transform
61	(compile env false e, compile_branches env false brs)
62	\| Typed.Xtrans (e,brs) -> Xtrans (compile env false e, compile_branches env false brs)
63	\| Typed.Validate (e,k,sch,t) -> Validate (compile env tail e, k, sch, t)
64	\| Typed.RemoveField (e,l) -> RemoveField (compile env tail e,l)
65	\| Typed.Dot (e,l) -> Dot (compile env tail e, l)
66	\| Typed.Try (e,brs) -> Try (compile env false e, compile_branches env tail brs)
67	\| Typed.UnaryOp (op,e) -> UnaryOp (op, compile env tail e)
68	\| Typed.BinaryOp (op,e1,e2) -> BinaryOp (op, compile env false e1, compile env tail e2)
69	\| Typed.Ref (e,t) -> Ref (compile env tail e, t)
70
71	and compile_abstr env a =
72	let fun_env =
73	match a.Typed.fun_name with
74	\| Some x -> Env.add x (Env 0) Env.empty
75	\| None -> Env.empty in
76
77	let (slots,nb_slots,fun_env) =
78	List.fold_left
79	(fun (slots,nb_slots,fun_env) x ->
80	match find x env with
81	\| (Stack _ \| Env _) as p ->
82	p::slots,
83	succ nb_slots,
84	Env.add x (Env nb_slots) fun_env;
85	\| Global _ as p ->
86	slots,
87	nb_slots,
88	Env.add x p fun_env
89	\| Dummy -> assert false
90	)
91	([Dummy],1,fun_env) (IdSet.get a.Typed.fun_fv) in
92
93
94	let slots = Array.of_list (List.rev slots) in
95	let env = { vars = fun_env; stack_size = 0 } in
96	let body = compile_branches env true a.Typed.fun_body in
97	Abstraction (slots, a.Typed.fun_iface, body)
98
99	and compile_branches env tail (brs : Typed.branches) =
100	(* Don't compile unused branches, because they have not been
101	type checked. *)
102	let used = List.filter (fun br -> br.Typed.br_used) brs.Typed.br_branches in
103	{
104	brs = List.map (compile_branch env tail) used;
105	brs_tail = tail;
106	brs_accept_chars = not (Types.Char.is_empty brs.Typed.br_accept);
107	brs_input = brs.Typed.br_typ;
108	brs_compiled = None
109	}
110
111	and compile_branch env tail br =
112	let env =
113	List.fold_left
114	(fun env x ->
115	{ vars = Env.add x (Stack env.stack_size) env.vars;
116	stack_size = env.stack_size + 1 }
117
118	) env (Patterns.fv_list br.Typed.br_pat) in
119	(br.Typed.br_pat, compile env tail br.Typed.br_body)
120
121
122	let enter_global env x =
123	{ vars = Env.add x (Global env.stack_size) env.vars;
124	stack_size = env.stack_size + 1 }
125
126	let enter_globals = List.fold_left enter_global
127
128	let compile_eval env e = Eval (compile env false e)
129
130	let compile_let_decl env decl =
131	let pat = decl.Typed.let_pat in
132	let code = Let_decl (pat, compile env false (decl.Typed.let_body)) in
133	let env = enter_globals env (Patterns.fv_list pat) in
134	(env, code)
135
136
137	let compile_rec_funs env funs =
138	let fun_name = function
139	\| { Typed.exp_descr=Typed.Abstraction{Typed.fun_name = Some x}} -> x
140	\| _ -> assert false in
141	let fun_a = function
142	\| { Typed.exp_descr=Typed.Abstraction a } -> a
143	\| _ -> assert false in
144	let names = List.map fun_name funs in
145	let env = enter_globals env names in
146	let exprs = List.map (compile_abstr env) (List.map fun_a funs) in
147	(env, Let_funs exprs)
148
149
150	(****************************************)
151
152	open Location
153
154	let eval ~run ~show (tenv,cenv,codes) e =
155	let (e,t) = Typer.type_expr tenv e in
156	let code = compile_eval cenv e in
157	if run then
158	let v = Eval.expr code in
159	show None t (Some v)
160	else
161	show None t None;
162	(tenv,cenv,code::codes)
163
164	let run_show ~run ~show tenv cenv code ids =
165	if run then
166	let () = Eval.eval code in
167	List.iter
168	(fun (id,_) -> show (Some id)
169	(Typer.find_value id tenv)
170	(Some (Eval.var (find id cenv)))) ids
171	else
172	List.iter
173	(fun (id,_) -> show (Some id)
174	(Typer.find_value id tenv)
175	None) ids
176
177	let let_decl ~run ~show (tenv,cenv,codes) p e =
178	let (tenv,decl,ids) = Typer.type_let_decl tenv p e in
179	let (cenv,code) = compile_let_decl cenv decl in
180	run_show ~run ~show tenv cenv code ids;
181	(tenv,cenv,code::codes)
182
183	let let_funs ~run ~show (tenv,cenv,codes) funs =
184	let (tenv,funs,ids) = Typer.type_let_funs tenv funs in
185	let (cenv,code) = compile_rec_funs cenv funs in
186	run_show ~run ~show tenv cenv code ids;
187	(tenv,cenv,code::codes)
188
189	let type_defs (tenv,cenv,codes) typs =
190	let tenv = Typer.enter_types (Typer.type_defs tenv typs) tenv in
191	(tenv,cenv,codes)
192
193	let namespace (tenv,cenv,codes) pr ns =
194	let tenv = Typer.enter_ns pr ns tenv in
195	(tenv,cenv,codes)
196
197	let using (tenv,cenv,codes) x cu =
198	let tenv = Typer.enter_cu x cu tenv in
199	(tenv,cenv,codes)
200
201	let rec collect_funs accu = function
202	\| { descr = Ast.FunDecl e } :: rest -> collect_funs (e::accu) rest
203	\| rest -> (accu,rest)
204
205	let rec collect_types accu = function
206	\| { descr = Ast.TypeDecl (x,t) } :: rest ->
207	collect_types ((x,t) :: accu) rest
208	\| rest -> (accu,rest)
209
210	let rec phrases ~run ~show ~loading ~directive =
211	let rec loop accu phs =
212	match phs with
213	\| { descr = Ast.FunDecl _ } :: _ ->
214	let (funs,rest) = collect_funs [] phs in
215	loop (let_funs ~run ~show accu funs) rest
216	\| { descr = Ast.TypeDecl (_,_) } :: _ ->
217	let (typs,rest) = collect_types [] phs in
218	loop (type_defs accu typs) rest
219	\| { descr = Ast.SchemaDecl (name, schema) } :: rest ->
220	Typer.register_schema name schema;
221	loop accu rest
222	\| { descr = Ast.Namespace (pr,ns) } :: rest ->
223	loop (namespace accu pr ns) rest
224	\| { descr = Ast.Using (x,cu) } :: rest ->
225	loading cu;
226	loop (using accu x cu) rest
227	\| { descr = Ast.EvalStatement e } :: rest ->
228	loop (eval ~run ~show accu e) rest
229	\| { descr = Ast.LetDecl (p,e) } :: rest ->
230	loop (let_decl ~run ~show accu p e) rest
231	\| { descr = Ast.Directive d } :: rest ->
232	let (tenv,cenv,_) = accu in
233	directive tenv cenv d;
234	loop accu rest
235	\| [] ->
236	accu
237	in
238	loop
239
240	let comp_unit ?(run=false)
241	?(show=fun _ _ _ -> ())
242	?(loading=fun _ -> ())
243	?(directive=fun _ _ _ -> ()) tenv cenv phs =
244	let (tenv,cenv,codes) = phrases ~run ~show ~loading ~directive (tenv,cenv,[]) phs in
245	(tenv,cenv,List.rev codes)