viewcvs.cgi/compile/compile.ml

open Ident
open Lambda

type env = {
  cu: Types.CompUnit.t option;  (* None: toplevel *)
  vars: var_loc Env.t;
  stack_size: int;
  global_size: int
}

let global_size env = env.global_size

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 mk cu g = { cu = cu; vars = Env.empty; stack_size = 0; global_size = g }
let empty_toplevel = mk None 0
let empty x g = mk (Some x) g


let serialize s env =
  assert (env.stack_size = 0);
  (match env.cu with
    | Some cu -> Types.CompUnit.serialize s cu
    | None -> assert false);
  Serialize.Put.env Id.serialize Lambda.Put.var_loc Env.iter s env.vars;
  Serialize.Put.int s env.global_size

let deserialize s =
  let cu = Types.CompUnit.deserialize s in
  let vars = 
    Serialize.Get.env Id.deserialize Lambda.Get.var_loc Env.add Env.empty s in
  let size = Serialize.Get.int s in
  { cu = Some cu; vars = vars; stack_size = 0; global_size = size }


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

let find_slot x env =
  match find x env with
    | Ext (_,slot) -> slot
    | _ -> assert false
 

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

let find_ext cu x =
  let env = !from_comp_unit cu in
  find x env


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) -> Var (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)
  | Typed.External (t,i) -> 
      (match env.cu with
         | Some cu -> Var (Ext (cu,i))
         | None -> failwith "Cannot compile externals in the toplevel")

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 _ | Ext _ 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 = { env with 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 ->
         { env with 
             vars = Env.add x (Stack env.stack_size) env.vars;
             stack_size = env.stack_size + 1 }

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


let enter_globals env n = 
  match env.cu with
    | None ->
        let env = 
          List.fold_left
            (fun env x ->
               { env with
                   vars = Env.add x (Global env.stack_size) env.vars;
                   stack_size = env.stack_size + 1 })
            env n in
        (env,[])
    | Some cu ->
        List.fold_left
        (fun (env,code) x ->
         let code = SetGlobal (cu, env.global_size) :: code in
         let env = 
           { env with
               vars = Env.add x (Ext (cu, env.global_size)) env.vars;
               global_size = env.global_size + 1 } in
         (env,code)
        )
        (env,[])
        n

let compile_expr env = compile env false

let compile_eval env e = [ Push (compile_expr env e); Pop ]

let compile_let_decl env decl =
  let pat = decl.Typed.let_pat in
  let e = compile_expr env decl.Typed.let_body in
  let (env,code) = enter_globals env (Patterns.fv pat) in
  (env, (Push e) :: (Split pat) :: 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 env = function
    | { Typed.exp_descr=Typed.Abstraction a } -> 
        Push (compile_abstr env a)
    | _ -> assert false in
  let names = List.map fun_name funs in
  let (env,code) = enter_globals env names in
  let exprs = List.map (fun_a env) funs in
  (env, exprs @ code)


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

open Location

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

let run_show ~run ~show tenv cenv codes ids =
  if run then
    let () = Eval.code_items codes 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,List.rev_append 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,List.rev_append 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 find_cu (tenv,_,_) cu =
  Typer.find_cu cu tenv

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