typer.ml 15.4 KB
Newer Older
1
2
(* I. Transform the abstract syntax of types and patterns into
      the internal form *)
3
4
5
6

open Location
open Ast

7
8
9
exception Pattern of string
exception NonExhaustive of Types.descr
exception Constraint of Types.descr * Types.descr * string
10
exception ShouldHave of Types.descr * string
11
exception WrongLabel of Types.descr * Types.label
12
13

let raise_loc loc exn = raise (Location (loc,exn))
14
15
16
17

(* Internal representation as a graph (desugar recursive types and regexp),
   to compute freevars, etc... *)

18
type ti = {
19
20
21
22
23
24
25
26
  id : int; 
  mutable loc' : loc;
  mutable fv : string SortedList.t option; 
  mutable descr': descr;
  mutable type_node: Types.node option;
  mutable pat_node: Patterns.node option
} 
and descr =
27
   [ `Alias of string * ti
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
   | `Type of Types.descr
   | `Or of ti * ti
   | `And of ti * ti
   | `Diff of ti * ti
   | `Times of ti * ti
   | `Arrow of ti * ti
   | `Record of Types.label * bool * ti
   | `Capture of Patterns.capture
   | `Constant of Patterns.capture * Types.const
   ]
    


module S = struct type t = string let compare = compare end
module StringMap = Map.Make(S)
module StringSet = Set.Make(S)

let mk' =
  let counter = ref 0 in
47
  fun loc ->
48
    incr counter;
49
50
    let rec x = { 
      id = !counter; 
51
      loc' = loc; 
52
53
54
55
56
      fv = None; 
      descr' = `Alias ("__dummy__", x);  
      type_node = None; 
      pat_node = None 
    } in
57
58
59
    x

let cons loc d =
60
  let x = mk' loc in
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
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
  x.descr' <- d;
  x
    
(* Note:
   Compilation of Regexp is implemented as a ``rewriting'' of
   the parsed syntax, in order to be able to print its result
   (for debugging for instance)
   
   It would be possible (and a little more efficient) to produce
   directly ti nodes.
*)
    
module Regexp = struct
  let memo = Hashtbl.create 51
  let defs = ref []
  let name =
    let c = ref 0 in
    fun () ->
      incr c;
      "#" ^ (string_of_int !c)

  let rec seq_vars accu = function
    | Epsilon | Elem _ -> accu
    | Seq (r1,r2) | Alt (r1,r2) -> seq_vars (seq_vars accu r1) r2
    | Star r | WeakStar r -> seq_vars accu r
    | SeqCapture (v,r) -> seq_vars (StringSet.add v accu) r

  let rec propagate vars = function
    | Epsilon -> `Epsilon
    | Elem x -> `Elem (vars,x)
    | Seq (r1,r2) -> `Seq (propagate vars r1,propagate vars r2)
    | Alt (r1,r2) -> `Alt (propagate vars r1, propagate vars r2)
    | Star r -> `Star (propagate vars r)
    | WeakStar r -> `WeakStar (propagate vars r)
    | SeqCapture (v,x) -> propagate (StringSet.add v vars) x

  let cup r1 r2 = 
    match (r1,r2) with
      | (_, `Empty) -> r1
      | (`Empty, _) -> r2
      | (`Res t1, `Res t2) -> `Res (mk noloc (Or (t1,t2)))

  let rec compile fin e seq : [`Res of Ast.ppat | `Empty] = 
    if List.mem seq e then `Empty
    else 
      let e = seq :: e in
      match seq with
	| [] ->
	    `Res fin
	| `Epsilon :: rest -> 
	    compile fin e rest
	| `Elem (vars,x) :: rest -> 
	    let capt = StringSet.fold
			 (fun v t -> mk noloc (And (t, (mk noloc (Capture v)))))
			 vars x in
	    `Res (mk noloc (Prod (capt, guard_compile fin rest)))
	| `Seq (r1,r2) :: rest -> 
	    compile fin e (r1 :: r2 :: rest)
	| `Alt (r1,r2) :: rest -> 
	    cup (compile fin e (r1::rest)) (compile fin e (r2::rest))
	| `Star r :: rest -> cup (compile fin e (r::seq)) (compile fin e rest) 
	| `WeakStar r :: rest -> cup (compile fin e rest) (compile fin e (r::seq))

  and guard_compile fin seq =
    try Hashtbl.find memo seq 
    with
	Not_found ->
          let n = name () in
	  let v = mk noloc (PatVar n) in
          Hashtbl.add memo seq v;
	  let d = compile fin [] seq in
	  (match d with
	     | `Empty -> assert false
	     | `Res d -> defs := (n,d) :: !defs);
	  v


  let atom_nil = Types.mk_atom "nil"
  let constant_nil v t = 
    mk noloc (And (t, (mk noloc (Constant (v, Types.Atom atom_nil)))))

  let compile regexp queue : ppat =
    let vars = seq_vars StringSet.empty regexp in
    let fin = StringSet.fold constant_nil vars queue in
    let n = guard_compile fin [propagate StringSet.empty regexp] in
    Hashtbl.clear memo;
    let d = !defs in
    defs := [];
    mk noloc (Recurs (n,d))
end

let compile_regexp = Regexp.compile


let rec compile env { loc = loc; descr = d } : ti = 
  match (d : Ast.ppat') with
  | PatVar s -> 
      (try StringMap.find s env
159
160
       with Not_found -> 
	 raise_loc loc (Pattern ("Undefined type variable " ^ s))
161
      )
162
  | Recurs (t, b) -> compile (compile_many env b) t
163
164
165
166
167
168
169
170
171
172
173
  | Regexp (r,q) -> compile env (Regexp.compile r q)
  | Internal t -> cons loc (`Type t)
  | Or (t1,t2) -> cons loc (`Or (compile env t1, compile env t2))
  | And (t1,t2) -> cons loc (`And (compile env t1, compile env t2))
  | Diff (t1,t2) -> cons loc (`Diff (compile env t1, compile env t2))
  | Prod (t1,t2) -> cons loc (`Times (compile env t1, compile env t2))
  | Arrow (t1,t2) -> cons loc (`Arrow (compile env t1, compile env t2))
  | Record (l,o,t) -> cons loc (`Record (l,o,compile env t))
  | Constant (x,v) -> cons loc (`Constant (x,v))
  | Capture x -> cons loc (`Capture x)

174
175
176
177
178
179
180
181
and compile_many env b = 
  let b = List.map (fun (v,t) -> (v,t,mk' t.loc)) b in
  let env = 
    List.fold_left (fun env (v,t,x) -> StringMap.add v x env) env b in
  List.iter (fun (v,t,x) -> x.descr' <- `Alias (v, compile env t)) b;
  env


182
183
184
185
186
187
let rec comp_fv seen s =
  match s.fv with
    | Some l -> l
    | None ->
	let l = 
	  match s.descr' with
188
	    | `Alias (_,x) -> if List.memq s seen then [] else comp_fv (s :: seen) x
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
	    | `Or (s1,s2) 
	    | `And (s1,s2)
	    | `Diff (s1,s2)
	    | `Times (s1,s2)
	    | `Arrow (s1,s2) -> SortedList.cup (comp_fv seen s1) (comp_fv seen s2)
	    | `Record (l,opt,s) -> comp_fv seen s
	    | `Type _ -> []
	    | `Capture x
	    | `Constant (x,_) -> [x]
	in
	if seen = [] then s.fv <- Some l;
	l


let fv = comp_fv []

let rec typ seen s : Types.descr =
  match s.descr' with
207
208
209
210
211
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this type"))
212
213
214
215
216
217
218
219
	else typ (s :: seen) x
    | `Type t -> t
    | `Or (s1,s2) -> Types.cup (typ seen s1) (typ seen s2)
    | `And (s1,s2) ->  Types.cap (typ seen s1) (typ seen s2)
    | `Diff (s1,s2) -> Types.diff (typ seen s1) (typ seen s2)
    | `Times (s1,s2) ->	Types.times (typ_node s1) (typ_node s2)
    | `Arrow (s1,s2) ->	Types.arrow (typ_node s1) (typ_node s2)
    | `Record (l,o,s) -> Types.record l o (typ_node s)
220
    | `Capture _ | `Constant _ -> assert false
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236

and typ_node s : Types.node =
  match s.type_node with
    | Some x -> x
    | None ->
	let x = Types.make () in
	s.type_node <- Some x;
	let t = typ [] s in
	Types.define x t;
	x

let type_node s = Types.internalize (typ_node s)

let rec pat seen s : Patterns.descr =
  if fv s = [] then Patterns.constr (type_node s) else
  match s.descr' with
237
238
239
240
241
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this pattern"))
242
243
244
245
246
247
	else pat (s :: seen) x
    | `Or (s1,s2) -> Patterns.cup (pat seen s1) (pat seen s2)
    | `And (s1,s2) -> Patterns.cap (pat seen s1) (pat seen s2)
    | `Diff (s1,s2) when fv s2 = [] ->
	let s2 = Types.cons (Types.neg (Types.descr (type_node s2)))in
	Patterns.cap (pat seen s1) (Patterns.constr s2)
248
249
    | `Diff _ ->
	raise_loc s.loc' (Pattern "Difference not allowed in patterns")
250
251
    | `Times (s1,s2) -> Patterns.times (pat_node s1) (pat_node s2)
    | `Record (l,false,s) -> Patterns.record l (pat_node s)
252
253
254
    | `Record _ ->
	raise_loc s.loc' 
	  (Pattern "Optional field not allowed in record patterns")
255
256
    | `Capture x ->  Patterns.capture x
    | `Constant (x,c) -> Patterns.constant x c
257
258
259
    | `Arrow _ ->
	raise_loc s.loc' (Pattern "Arrow not allowed in patterns")
    | `Type _ -> assert false
260
261
262
263
264
265
266
267
268
269
270

and pat_node s : Patterns.node =
  match s.pat_node with
    | Some x -> x
    | None ->
	let x = Patterns.make (fv s) in
	s.pat_node <- Some x;
	let t = pat [] s in
	Patterns.define x t;
	x

271
272
273
let global_types = ref StringMap.empty

let mk_typ e =
274
  if fv e = [] then type_node e 
275
276
277
278
279
  else raise_loc e.loc' (Pattern "Capture variables are not allowed in types")
    

let typ e =
  mk_typ (compile !global_types e)
280
281

let pat e =
282
  let e = compile !global_types e in
283
284
  pat_node e

285
286
let register_global_types b =
  let env = compile_many !global_types b in
287
288
289
290
  List.iter (fun (v,_) -> 
	       let d = Types.descr (mk_typ (StringMap.find v env)) in
	       Types.Print.register_global v d
	    ) b;
291
  global_types := env
292
293


294
295
(* II. Build skeleton *)

296
297
module Fv = StringSet

298
let rec expr { loc = loc; descr = d } = 
299
  let (fv,td) = 
300
    match d with
301
      | DebugTyper t -> (Fv.empty, Typed.DebugTyper (typ t))
302
303
304
305
      | Var s -> (Fv.singleton s, Typed.Var s)
      | Apply (e1,e2) -> 
	  let (fv1,e1) = expr e1 and (fv2,e2) = expr e2 in
	  (Fv.union fv1 fv2, Typed.Apply (e1,e2))
306
      | Abstraction a ->
307
308
309
310
	  let iface = List.map (fun (t1,t2) -> (typ t1, typ t2)) a.fun_iface in
	  let t = List.fold_left 
		    (fun accu (t1,t2) -> Types.cap accu (Types.arrow t1 t2)) 
		    Types.any iface in
311
312
313
	  let iface = List.map 
			(fun (t1,t2) -> (Types.descr t1, Types.descr t2)) 
			iface in
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
	  let (fv0,body) = branches a.fun_body in
	  let fv = match a.fun_name with
	    | None -> fv0
	    | Some f -> Fv.remove f fv0 in
	  (fv,
	   Typed.Abstraction 
	     { Typed.fun_name = a.fun_name;
	       Typed.fun_iface = iface;
	       Typed.fun_body = body;
	       Typed.fun_typ = t;
	       Typed.fun_fv = Fv.elements fv0
	     }
	  )
      | Cst c -> (Fv.empty, Typed.Cst c)
      | Pair (e1,e2) ->
	  let (fv1,e1) = expr e1 and (fv2,e2) = expr e2 in
	  (Fv.union fv1 fv2, Typed.Pair (e1,e2))
331
332
      | Dot (e,l) ->
	  let (fv,e) = expr e in
333
	  (fv,  Typed.Dot (e,l))
334
335
336
337
338
339
340
341
342
343
      | RecordLitt r -> 
	  (* XXX TODO: check that no label appears twice *)
	  let fv = ref Fv.empty in
	  let r = List.map 
		    (fun (l,e) -> 
		       let (fv2,e) = expr e in
		       fv := Fv.union !fv fv2;
		       (l,e)
		    ) r in
	  (!fv, Typed.RecordLitt r)
344
345
346
347
      | Op (op,le) ->
	  let (fvs,ltes) = List.split (List.map expr le) in
	  let fv = List.fold_left Fv.union Fv.empty fvs in
	  (fv, Typed.Op (op,ltes))
348
349
350
351
352
353
354
355
      | Match (e,b) -> 
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Match (e, b))
      | Map (e,b) ->
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Map (e, b))
356
  in
357
358
  fv,
  { Typed.exp_loc = loc;
359
360
361
362
    Typed.exp_typ = Types.empty;
    Typed.exp_descr = td;
  }
	      
363
364
  and branches b = 
    let fv = ref Fv.empty in
365
    let accept = ref Types.empty in
366
367
368
369
    let b = List.map 
	      (fun (p,e) ->
		 let (fv2,e) = expr e in
		 fv := Fv.union !fv fv2;
370
371
		 let p = pat p in
		 accept := Types.cup !accept (Types.descr (Patterns.accept p));
372
		 { Typed.br_used = false;
373
		   Typed.br_pat = p;
374
375
		   Typed.br_body = e }
	      ) b in
376
377
378
379
380
381
382
    (!fv, 
     { 
       Typed.br_typ = Types.empty; 
       Typed.br_branches = b; 
       Typed.br_accept = !accept 
     } 
    )
383
384
385
386
387

module Env = StringMap

open Typed

388
389
390
391

let check loc t s msg =
  if not (Types.subtype t s) then raise_loc loc (Constraint (t, s, msg))

392
393
394
395
let rec type_check env e constr precise = 
 (* Format.fprintf Format.std_formatter "constr=%a precise=%b@\n"
    Types.Print.print_descr constr precise;  *)
  let d = type_check' e.exp_loc env e.exp_descr constr precise in
396
397
398
  e.exp_typ <- Types.cup e.exp_typ d;
  d

399
and type_check' loc env e constr precise = match e with
400
  | Abstraction a ->
401
402
403
404
405
406
407
      let t =
	try Types.Arrow.check_strenghten a.fun_typ constr 
	with Not_found -> 
	  raise_loc loc 
	  (ShouldHave
	     (constr, "but the interface of the abstraction is not compatible"))
      in
408
409
410
      let env = match a.fun_name with
	| None -> env
	| Some f -> Env.add f a.fun_typ env in
411
412
413
414
415
416
417
418
      List.iter 
	(fun (t1,t2) ->
	   ignore (type_check_branches loc env t1 a.fun_body t2 false)
	) a.fun_iface;
      t
  | Match (e,b) ->
      let t = type_check env e b.br_accept true in
      type_check_branches loc env t b constr precise
419
  | Pair (e1,e2) -> 
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
      let rects = Types.Product.get constr in
      if Types.Product.is_empty rects then 
	raise_loc loc (ShouldHave (constr,"but it is a pair."));
      let pi1 = Types.Product.pi1 rects in

      let t1 = type_check env e1 (Types.Product.pi1 rects) 
		 (precise || (Types.Product.need_second rects))in
      let rects = Types.Product.restrict_1 rects t1 in
      let t2 = type_check env e2 (Types.Product.pi2 rects) precise in
      if precise then 
	Types.times (Types.cons t1) (Types.cons t2)
      else
	constr
  | _ -> 
      let t : Types.descr = compute_type' loc env e in
      check loc t constr "";
      t

and compute_type env e =
  type_check env e Types.any true

and compute_type' loc env = function
  | DebugTyper t -> Types.descr t
  | Var s -> Env.find s env
  | Apply (e1,e2) ->
      let t1 = type_check env e1 Types.Arrow.any true in
      let t1 = Types.Arrow.get t1 in
      let dom = Types.Arrow.domain t1 in
      if Types.Arrow.need_arg t1 then
	let t2 = type_check env e2 dom true in
	Types.Arrow.apply t1 t2
      else
	(ignore (type_check env e2 dom false); Types.Arrow.apply_noarg t1)
  | Cst c -> Types.constant c
454
455
456
457
  | Dot (e,l) ->
      let t = type_check env e Types.Record.any true in
         (try (Types.Record.project t l) 
          with Not_found -> raise_loc loc (WrongLabel(t,l)))
458
459
460
461
462
463
464
  | RecordLitt r ->
      List.fold_left 
	(fun accu (l,e) ->
	   let t = compute_type env e in
	   let t = Types.record l false (Types.cons t) in
	   Types.cap accu t
	) Types.Record.any r
465
466
467
  | Op (op, el) ->
      let args = List.map (fun e -> (e.exp_loc, compute_type env e)) el in
      type_op loc op args
468
469
  | Map (e,b) ->
      let t = compute_type env e in
470
471
      Sequence.map (fun t -> type_check_branches loc env t b Types.any true) t
  | _ -> assert false
472

473
and type_check_branches loc env targ brs constr precise =
474
  if Types.is_empty targ then Types.empty 
475
476
  else (
    brs.br_typ <- Types.cup brs.br_typ targ;
477
478
479
    branches_aux loc env targ 
      (if precise then Types.empty else constr) 
      constr precise brs.br_branches
480
  )
481
    
482
and branches_aux loc env targ tres constr precise = function
483
  | [] -> raise_loc loc (NonExhaustive targ)
484
485
486
487
488
489
  | b :: rem ->
      let p = b.br_pat in
      let acc = Types.descr (Patterns.accept p) in

      let targ' = Types.cap targ acc in
      if Types.is_empty targ' 
490
      then branches_aux loc env targ tres constr precise rem
491
492
493
494
495
496
      else 
	( b.br_used <- true;
	  let res = Patterns.filter targ' p in
	  let env' = List.fold_left 
		       (fun env (x,t) -> Env.add x (Types.descr t) env) 
		       env res in
497
498
	  let t = type_check env' b.br_body constr precise in
	  let tres = if precise then Types.cup t tres else tres in
499
500
	  let targ'' = Types.diff targ acc in
	  if (Types.non_empty targ'') then 
501
	    branches_aux loc env targ'' tres constr precise rem 
502
503
	  else
	    tres
504
	)
505
506
507
508
509
510
511

and type_op loc op args =
  match (op,args) with
    | ("+", [loc1,t1; loc2,t2]) ->
	type_int_binop Intervals.add loc1 t1 loc2 t2
    | ("*", [loc1,t1; loc2,t2]) ->
	type_int_binop (fun i1 i2 -> Intervals.any) loc1 t1 loc2 t2
512
513
514
515
516
517
518
519
    | ("@", [loc1,t1; loc2,t2]) ->
	check loc1 t1 Sequence.any
	  "The first argument of @ must be a sequence";
	Sequence.concat t1 t2
    | ("flatten", [loc1,t1]) ->
	check loc1 t1 Sequence.seqseq 
	  "The argument of flatten must be a sequence of sequences";
	Sequence.flatten t1
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
    | _ -> assert false

and type_int_binop f loc1 t1 loc2 t2 =
  if not (Types.Int.is_int t1) then
    raise_loc loc1 
      (Constraint 
	 (t1,Types.Int.any,
	  "The first argument must be an integer"));
  if not (Types.Int.is_int t2) then
    raise_loc loc2
      (Constraint 
	       (t1,Types.Int.any,
		"The second argument must be an integer"));
  Types.Int.put
    (f (Types.Int.get t1) (Types.Int.get t2));