mltypes.ml 9.59 KB
Newer Older
1
exception Error of string
2

3
module Loc = Cduce_loc
4
open Caml_cduce
5
open Caml_cduce.Types
6
7
8

(* Unfolding of OCaml types *)

9
10
exception PolyAbstract of string

11
12
13
14
15
let ocaml_env = ref Env.initial

type t = { uid : int; mutable recurs : int; mutable def : def }
and def =
  | Link of t
16
  | Arrow of string * t * t
17
18
  | Tuple of t list
  | PVariant of (string * t option) list  (* Polymorphic variant *)
19
20
  | Variant of string * (string * t list) list * bool
  | Record of string * (string * t) list * bool
21
22
  | Builtin of string * t list
  | Abstract of string
23
  | Var of int
24
25
26

module IntMap = 
  Map.Make(struct type t = int let compare : t -> t -> int = compare end)
27
28
29
30
module IntSet = 
  Set.Make(struct type t = int let compare : t -> t -> int = compare end)
module StringSet =   Set.Make(struct type t = string let compare : t -> t -> int = compare end)

31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

let rec print_sep f sep ppf = function
  | [] -> ()
  | [x] -> f ppf x
  | x::tl -> Format.fprintf ppf "%a%s" f x sep; print_sep f sep ppf tl

let printed = ref IntMap.empty

let rec print_slot ppf slot =
  if slot.recurs > 0 then
    (
      if IntMap.mem slot.uid !printed then
	Format.fprintf ppf "X%i" slot.uid
      else (
	printed := IntMap.add slot.uid () !printed;
	Format.fprintf ppf "X%i:=%a" slot.uid print_def slot.def
      )
    )
  else 
    print_def ppf slot.def

and print_def ppf = function
  | Link t -> print_slot ppf t
54
  | Arrow (l,t,s) -> Format.fprintf ppf "%s:%a -> %a" l print_slot t print_slot s
55
56
  | Tuple tl -> Format.fprintf ppf "(%a)" (print_sep print_slot ",") tl
  | PVariant l -> Format.fprintf ppf "[%a]" (print_sep print_palt " | ") l
57
58
  | Variant (p,l,_) -> Format.fprintf ppf "[%s:%a]" p (print_sep print_alt " | ") l
  | Record (p,l,_) -> Format.fprintf ppf "{%s:%a}" p (print_sep print_field " ; ") l
59
60
  | Builtin (p,tl) -> Format.fprintf ppf "%s(%a)" p (print_sep print_slot ",") tl
  | Abstract s -> Format.fprintf ppf "%s" s
61
  | Var i -> Format.fprintf ppf "'a%i" i
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84


and print_palt ppf = function
  | lab, None -> Format.fprintf ppf "`%s" lab
  | lab, Some t -> Format.fprintf ppf "`%s of %a" lab print_slot t
   
and print_alt ppf = function
  | (lab,[]) ->
      Format.fprintf ppf "%s" lab
  | (lab,l) ->
      Format.fprintf ppf "%s of [%a]" lab (print_sep print_slot ",") l

and print_field ppf (lab,t) =
  Format.fprintf ppf "%s:%a" lab print_slot t


let print = print_slot

let counter = ref 0
let new_slot () =
  incr counter;
  { uid = !counter; recurs = 0; def = Abstract "DUMMY" }

85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
let reg_uid t =
  let saved = ref [] in
  let rec aux t =
    if t.recurs < 0 then () else begin
      if t.uid > !counter then counter := t.uid;
      saved := (t,t.recurs) :: !saved;
      t.recurs <- (-1);
      match t.def with
	| Link t -> aux t
	| Arrow (_,t1,t2) -> aux t1; aux t2
	| Tuple tl -> List.iter aux tl
	| PVariant pl -> List.iter (function (_,Some t) -> aux t | _ -> ()) pl
	| Variant (_,pl,_) -> List.iter (fun (_,tl) -> List.iter aux tl) pl
	| Record (_,tl,_) ->  List.iter (fun (_,t) -> aux t) tl
	| Builtin (_,tl) -> List.iter aux tl
	| _ -> ()
    end
  in
  aux t;
  List.iter (fun (t,recurs) -> t.recurs <- recurs) !saved

106
let builtins =
107
  List.fold_left (fun m x -> StringSet.add x m) StringSet.empty
108
109
110
    [
      "list"; "Pervasives.ref"; 
      "unit"; "array";
111
      "Big_int.big_int";
112
      "option";
113
114
115
      "Cduce_lib.Value.t"; 
      "Cduce_lib.Encodings.Utf8.t";
      "Cduce_lib.Atoms.V.t";
116
    ]
117

118
119
let vars = ref []

120
let get_var id = 
121
  try List.assq id !vars
122
  with Not_found -> 
123
    let i = List.length !vars in
124
    vars := (id,i) :: !vars; 
125
126
    i

127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
let constr_table = Hashtbl.create 1024

type env = { constrs: StringSet.t; seen: IntSet.t; vars: t IntMap.t }

let rec unfold_constr env p args =
  let args = List.map (unfold env) args in
  let pn = Path.name p in
  if StringSet.mem pn builtins 
  then ( let slot = new_slot () in slot.def <- Builtin (pn,args); slot )
  else
    let args_id = List.map (fun t -> t.uid) args in
    let k = (pn,args_id) in
    try Hashtbl.find constr_table k
    with Not_found ->
      if StringSet.mem pn env.constrs then
	failwith "Polymorphic recursion forbidden";
      let slot = new_slot () in
      slot.recurs <- 1;
      Hashtbl.add constr_table k slot;

      let decl = 
	try Env.find_type p !ocaml_env
	with Not_found -> failwith ("Cannot resolve path " ^ pn) in

      let env = 
	{ env with 
	    constrs = StringSet.add pn env.constrs;
	    vars = 
	    List.fold_left2 
	      (fun vars a t -> IntMap.add a.id t vars) 
	      env.vars decl.type_params args } in

      let prefix = match p with
	| Path.Pident _ -> ""
	| Path.Pdot (p,_,_) -> Path.name p ^ "."
	| _ -> assert false in

      slot.def <- 
	(match decl.type_kind, decl.type_manifest with
	   | Type_variant (cstrs,pub), _ ->
	       let cstrs =
		 List.map 
		   (fun (cst,f) -> (cst,List.map (unfold env) f)) cstrs in
170
	       Variant (prefix, cstrs, pub = Caml_cduce.Asttypes.Public)
171
172
	   | Type_record (f,_,pub), _ ->
	       let f = List.map (fun (l,_,t) -> (l,unfold env t)) f in
173
	       Record (prefix, f, pub = Caml_cduce.Asttypes.Public)
174
175
176
177
178
179
180
181
182
183
184
185
186
	   | Type_abstract, Some t ->
	       Link (unfold env t)
	   | Type_abstract, None ->
	       (match args with
		  | [] -> Abstract pn
		  | l ->raise (PolyAbstract pn)));
      slot
	
and unfold env ty =
  if IntSet.mem ty.id env.seen then failwith "Unguarded recursion";
  let env = { env with seen = IntSet.add ty.id env.seen } in 
  let slot = new_slot () in
  slot.def <-
187
    (match ty.desc with
188
189
190
191
192
       | Tarrow (l,t1,t2,_) -> 
	   let t1 = unfold env t1 in
	   let t2 = unfold env t2 in 
	   Arrow (l, t1,t2)
       | Ttuple tyl -> Tuple (List.map (unfold env) tyl)
193
194
       | Tvariant rd ->
	   let fields = 
195
196
	     List.fold_left
	       (fun accu (lab,f) -> 
197
		  match f with
198
		    | Rpresent (Some t) 
199
200
		    | Reither(true, [t], _, _) -> 
			(lab, Some (unfold env t)) :: accu
201
202
203
204
205
		    | Rpresent None 
		    | Reither(true, [], _, _) -> (lab, None) :: accu
		    | Rabsent -> Printf.eprintf "Warning: Rabsent not supported"; accu
		    | Reither _ -> Printf.eprintf "Warning: Reither not supported"; accu
	       ) []
206
207
	       rd.row_fields in
	   PVariant fields
208
209
210
       | Tvar -> 
	   (try Link (IntMap.find ty.id env.vars)
	    with Not_found -> Var (get_var ty.id))
211
       | Tconstr (p,args,_) ->
212
	   Link (unfold_constr env p args)
213
214
       | _ -> failwith "Unsupported feature"
    );
215
  slot
216

217
218
let unfold ty = 
  vars := [];
219
220
221
  Hashtbl.clear constr_table; (* Get rid of that (careful with exceptions) *)
  let t = unfold { seen = IntSet.empty; constrs = StringSet.empty;
		   vars = IntMap.empty } ty in
222
223
224
  let n = List.length !vars in
  vars := [];
  (t,n)
225
226
227

(* Reading .cmi *)

228
let unsupported s =
229
  raise (Error (Printf.sprintf "Unsupported feature (%s) found in .cmi" s))
230

231
let has_cmi name =
232
  Config.load_path := Config.standard_library :: !Loc.obj_path;
233
234
235
  try ignore (Misc.find_in_path_uncap !Config.load_path (name ^ ".cmi")); true
  with Not_found -> false

236
let find_value v =
237
  Config.load_path := Config.standard_library :: !Loc.obj_path;
238
239
  let li = Longident.parse v in
  ocaml_env := Env.initial;
240
  let (_,vd) = Env.lookup_value li Env.initial in
241
242
  unfold vd.val_type

243
let values_of_sig name sg =
244
245
246
  List.fold_left
    (fun accu v -> match v with
       | Tsig_value (id,_) -> 
247
248
249
250
251
252
253
	   let id = Ident.name id in
	   (match id.[0] with
	     | 'a'..'z' | '_' ->
		 let n = name ^ "." ^ id in
		 (try (n, (fst (find_value n))) :: accu
		  with PolyAbstract _ -> accu)
	     | _ -> accu (* operator *))
254
255
       | _ -> accu
    ) [] sg
256

257
258

let load_module name = 
259
  Config.load_path := Config.standard_library :: !Loc.obj_path;
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
  let li = Longident.parse name in
  ocaml_env := Env.initial;
  let (_,mty) = Env.lookup_module li Env.initial in
  match mty with
    | Tmty_signature sg -> values_of_sig name sg
    | _ -> raise (Loc.Generic 
		    (Printf.sprintf "Module %s is not a structure" name))

(*
  let filename = Misc.find_in_path_uncap !Config.load_path (name ^ ".cmi") in
  let sg = Env.read_signature name filename in
  values_of_sig sg
*)

let load_module name =
  try load_module name
276
277
278
279
280
  with Env.Error e ->
    Env.report_error Format.str_formatter e;
    let s = Format.flush_str_formatter () in
    let s = Printf.sprintf "Error while reading OCaml interface %s: %s"
	      name s in
281
    raise (Loc.Generic s)
282

283
let read_cmi name =
284
  Config.load_path := Config.standard_library :: !Loc.obj_path;
285
286
287
288
289
290
291
292
293
  let filename = Misc.find_in_path_uncap !Config.load_path (name ^ ".cmi") in
  let sg = Env.read_signature name filename in
  ocaml_env := Env.add_signature sg Env.initial;
  let buf = Buffer.create 1024 in
  let ppf = Format.formatter_of_buffer buf in
  let values = ref [] in
  List.iter
    (function
       | Tsig_value (id, {val_type=t;val_kind=Val_reg}) -> 
294
295
296
	   let (unf,n) = unfold t in
	   if n !=0 then unsupported "polymorphic value";
	   values := (Ident.name id, t, unf) :: !values
297
298
299
       | Tsig_type (id,t,rs) -> 
	   Format.fprintf ppf "%a@."
	     !Oprint.out_sig_item (Printtyp.tree_of_type_declaration id t rs);
300
301
302
303
304
305
       | Tsig_value _ -> unsupported "external value"
       | Tsig_exception _ -> unsupported "exception"
       | Tsig_module _ -> unsupported "module"
       | Tsig_modtype _ -> unsupported "module type"
       | Tsig_class _ -> unsupported "class"
       | Tsig_cltype _ -> unsupported "class type"
306
307
308
    ) sg;
  (Buffer.contents buf, !values)

309
310
311
312
313
314
315
let read_cmi name =
  try read_cmi name
  with Env.Error e ->
    Env.report_error Format.str_formatter e;
    let s = Format.flush_str_formatter () in
    let s = Printf.sprintf "Error while reading OCaml interface %s: %s"
	      name s in
316
    raise (Loc.Generic s)
317
318


319
let print_ocaml = Printtyp.type_expr
320
321
322
323
324
325
326


let rec dump_li = function
  | Longident.Lident s -> print_endline s
  | Longident.Ldot (li,s) -> dump_li li; print_endline s
  | _ -> assert false