typer.ml 21.8 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
exception Pattern of string
exception NonExhaustive of Types.descr
9
exception MultipleLabel of Types.label
10
exception Constraint of Types.descr * Types.descr * string
11
exception ShouldHave of Types.descr * string
12
exception WrongLabel of Types.descr * Types.label
13
exception UnboundId of string
14
15

let raise_loc loc exn = raise (Location (loc,exn))
16
17
18
19

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

20
type ti = {
21
22
23
24
25
26
27
28
  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 =
29
   [ `Alias of string * ti
30
31
   | `Type of Types.descr
   | `Or of ti * ti
32
   | `And of ti * ti * bool
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
   | `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
49
  fun loc ->
50
    incr counter;
51
52
    let rec x = { 
      id = !counter; 
53
      loc' = loc; 
54
55
56
57
58
      fv = None; 
      descr' = `Alias ("__dummy__", x);  
      type_node = None; 
      pat_node = None 
    } in
59
60
61
    x

let cons loc d =
62
  let x = mk' loc in
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
  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 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

89
90
91
92
93
94
95
96
97
98
99
  let uniq_id = let r = ref 0 in fun () -> incr r; !r

  type flat = [ `Epsilon 
	      | `Elem of int * Ast.ppat  (* the int arg is used to
					    to stop generic comparison *)
	      | `Seq of flat * flat
	      | `Alt of flat * flat
	      | `Star of flat
	      | `WeakStar of flat ]

  let rec propagate vars : regexp -> flat = function
100
    | Epsilon -> `Epsilon
101
    | Elem x -> let p = vars x in `Elem (uniq_id (),p)
102
103
104
105
    | 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)
106
107
108
    | SeqCapture (v,x) -> 
	let v= mk noloc (Capture v) in
	propagate (fun p -> mk noloc (And (vars p,v,true))) x
109
110
111
112
113
114
115

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

116
117
118
119
120
121
122
(*TODO: review this compilation schema to avoid explosion when
  coding (Optional x) by  (Or(Epsilon,x)); memoization ... *)

  module Memo = Map.Make(struct type t = flat list let compare = compare end)
  module Coind = Set.Make(struct type t = flat list let compare = compare end)
  let memo = ref Memo.empty

123
  let rec compile fin e seq : [`Res of Ast.ppat | `Empty] = 
124
125
126
    if Coind.mem seq !e then `Empty
    else (
      e := Coind.add seq !e;
127
128
129
130
131
      match seq with
	| [] ->
	    `Res fin
	| `Epsilon :: rest -> 
	    compile fin e rest
132
133
	| `Elem (_,p) :: rest -> 
	    `Res (mk noloc (Prod (p, guard_compile fin rest)))
134
135
136
137
	| `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))
138
139
140
141
142
	| `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))
    )
143
  and guard_compile fin seq =
144
    try Memo.find seq !memo
145
146
147
148
    with
	Not_found ->
          let n = name () in
	  let v = mk noloc (PatVar n) in
149
150
          memo := Memo.add seq v !memo;
	  let d = compile fin (ref Coind.empty) seq in
151
152
153
154
155
156
157
	  (match d with
	     | `Empty -> assert false
	     | `Res d -> defs := (n,d) :: !defs);
	  v


  let constant_nil v t = 
158
    mk noloc (And (t, (mk noloc (Constant (v, Types.Atom Sequence.nil_atom))), true))
159
160
161

  let compile regexp queue : ppat =
    let vars = seq_vars StringSet.empty regexp in
162
163
164
   let fin = StringSet.fold constant_nil vars queue in
    let n = guard_compile fin [propagate (fun p -> p) regexp] in
    memo := Memo.empty; 
165
166
167
168
169
170
171
172
173
174
175
176
    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
177
178
       with Not_found -> 
	 raise_loc loc (Pattern ("Undefined type variable " ^ s))
179
      )
180
  | Recurs (t, b) -> compile (compile_many env b) t
181
182
183
  | 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))
184
  | And (t1,t2,e) -> cons loc (`And (compile env t1, compile env t2,e))
185
186
187
188
189
190
191
  | 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)

192
193
194
195
196
197
198
199
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


200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
let comp_fv_seen = ref []
let comp_fv_res = ref []
let rec comp_fv s =
  if List.memq s !comp_fv_seen then ()
  else (
    comp_fv_seen := s :: !comp_fv_seen;
    (match s.descr' with
      | `Alias (_,x) -> comp_fv x
      | `Or (s1,s2) 
      | `And (s1,s2,_)
      | `Diff (s1,s2)
      | `Times (s1,s2)
      | `Arrow (s1,s2) -> comp_fv s1; comp_fv s2
      | `Record (l,opt,s) -> comp_fv s
      | `Type _ -> ()
      | `Capture x
      | `Constant (x,_) -> comp_fv_res := x :: !comp_fv_res);
    if (!comp_fv_res = []) then s.fv <- Some [];
    (* TODO: check that the above line is correct *)
  )



let fv s =   
224
225
  match s.fv with
    | Some l -> l
226
227
228
229
230
231
    | None -> 
	comp_fv s;
	let l = SortedList.from_list !comp_fv_res in
	comp_fv_res := [];
	comp_fv_seen := [];
	s.fv <- Some l; 
232
233
234
235
	l

let rec typ seen s : Types.descr =
  match s.descr' with
236
237
238
239
240
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this type"))
241
242
243
	else typ (s :: seen) x
    | `Type t -> t
    | `Or (s1,s2) -> Types.cup (typ seen s1) (typ seen s2)
244
    | `And (s1,s2,_) ->  Types.cap (typ seen s1) (typ seen s2)
245
246
247
248
    | `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)
249
    | `Capture _ | `Constant _ -> assert false
250
251
252
253
254
255
256
257
258
259
260

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

261
262
263
264
265
let type_node s = 
  let s = typ_node s in
  let s = Types.internalize s in
(*  Types.define s (Types.normalize (Types.descr s)); *)
  s
266
267
268
269

let rec pat seen s : Patterns.descr =
  if fv s = [] then Patterns.constr (type_node s) else
  match s.descr' with
270
271
272
273
274
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this pattern"))
275
276
	else pat (s :: seen) x
    | `Or (s1,s2) -> Patterns.cup (pat seen s1) (pat seen s2)
277
    | `And (s1,s2,e) -> Patterns.cap (pat seen s1) (pat seen s2) e
278
279
    | `Diff (s1,s2) when fv s2 = [] ->
	let s2 = Types.cons (Types.neg (Types.descr (type_node s2)))in
280
	Patterns.cap (pat seen s1) (Patterns.constr s2) true
281
282
    | `Diff _ ->
	raise_loc s.loc' (Pattern "Difference not allowed in patterns")
283
284
    | `Times (s1,s2) -> Patterns.times (pat_node s1) (pat_node s2)
    | `Record (l,false,s) -> Patterns.record l (pat_node s)
285
286
287
    | `Record _ ->
	raise_loc s.loc' 
	  (Pattern "Optional field not allowed in record patterns")
288
289
    | `Capture x ->  Patterns.capture x
    | `Constant (x,c) -> Patterns.constant x c
290
291
292
    | `Arrow _ ->
	raise_loc s.loc' (Pattern "Arrow not allowed in patterns")
    | `Type _ -> assert false
293
294
295
296
297
298
299
300
301
302
303

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

304
305
306
let global_types = ref StringMap.empty

let mk_typ e =
307
  if fv e = [] then type_node e
308
309
310
311
312
  else raise_loc e.loc' (Pattern "Capture variables are not allowed in types")
    

let typ e =
  mk_typ (compile !global_types e)
313
314

let pat e =
315
  let e = compile !global_types e in
316
317
  pat_node e

318
319
let register_global_types b =
  let env = compile_many !global_types b in
320
321
  List.iter (fun (v,_) -> 
	       let d = Types.descr (mk_typ (StringMap.find v env)) in
322
323
324
(*	       let d = Types.normalize d in*)
	       Types.Print.register_global v d;
	       ()
325
	    ) b;
326
  global_types := env
327
328


329
330
(* II. Build skeleton *)

331
332
module Fv = StringSet

333
let rec expr { loc = loc; descr = d } = 
334
  let (fv,td) = 
335
    match d with
336
      | DebugTyper t -> (Fv.empty, Typed.DebugTyper (typ t))
337
338
339
      | Forget (e,t) ->
	  let (fv,e) = expr e and t = typ t in
	  (fv, Typed.Forget (e,t))
340
341
342
343
      | 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))
344
      | Abstraction a ->
345
346
347
348
	  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
349
350
351
	  let iface = List.map 
			(fun (t1,t2) -> (Types.descr t1, Types.descr t2)) 
			iface in
352
353
354
355
356
357
358
359
360
361
	  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;
362
	       Typed.fun_fv = Fv.elements fv
363
364
365
366
367
368
	     }
	  )
      | 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))
369
370
      | Dot (e,l) ->
	  let (fv,e) = expr e in
371
	  (fv,  Typed.Dot (e,l))
372
373
      | RecordLitt r -> 
	  let fv = ref Fv.empty in
374
	  let r  = List.sort (fun (l1,_) (l2,_) -> compare l1 l2) r in
375
376
	  let r = List.map 
		    (fun (l,e) -> 
377
378
379
380
381
382
383
384
		       let (fv2,e) = expr e in fv := Fv.union !fv fv2; (l,e))
		    r in
	  let rec check = function
	    | (l1,_) :: (l2,_) :: _ when l1 = l2 -> 
		raise_loc loc (MultipleLabel l1)
	    | _ :: rem -> check rem
	    | _ -> () in
	  check r;
385
	  (!fv, Typed.RecordLitt r)
386
387
388
389
      | 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))
390
391
392
393
394
395
396
397
      | 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))
398
399
400
401
      | Try (e,b) ->
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Try (e, b))
402
  in
403
404
  fv,
  { Typed.exp_loc = loc;
405
406
407
408
    Typed.exp_typ = Types.empty;
    Typed.exp_descr = td;
  }
	      
409
410
  and branches b = 
    let fv = ref Fv.empty in
411
    let accept = ref Types.empty in
412
413
414
    let b = List.map 
	      (fun (p,e) ->
		 let (fv2,e) = expr e in
415
		 let p = pat p in
416
417
		 let fv2 = List.fold_right Fv.remove (Patterns.fv p) fv2 in
		 fv := Fv.union !fv fv2;
418
		 accept := Types.cup !accept (Types.descr (Patterns.accept p));
419
		 { Typed.br_used = false;
420
		   Typed.br_pat = p;
421
422
		   Typed.br_body = e }
	      ) b in
423
424
425
426
    (!fv, 
     { 
       Typed.br_typ = Types.empty; 
       Typed.br_branches = b; 
427
428
       Typed.br_accept = !accept;
       Typed.br_compiled = None;
429
430
     } 
    )
431

432
433
434
435
436
437
438
439
let let_decl p e =
  let (_,e) = expr e in
  { Typed.let_pat = pat p;
    Typed.let_body = e;
    Typed.let_compiled = None }

(* III. Type-checks *)

440
module Env = StringMap
441
type env = Types.descr Env.t
442
443
444

open Typed

445
446
447
let warning loc msg =
  Format.fprintf Format.std_formatter 
    "Warning %a:@\n%s@\n" Location.print_loc loc msg
448
449
450
451

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

452
let rec type_check env e constr precise = 
453
(*  Format.fprintf Format.std_formatter "constr=%a precise=%b@\n"
454
455
    Types.Print.print_descr constr precise; 
*)
456
  let d = type_check' e.exp_loc env e.exp_descr constr precise in
457
458
459
  e.exp_typ <- Types.cup e.exp_typ d;
  d

460
and type_check' loc env e constr precise = match e with
461
462
463
464
  | Forget (e,t) ->
      let t = Types.descr t in
      ignore (type_check env e t false);
      t
465
  | Abstraction a ->
466
467
468
469
470
471
472
      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
473
474
475
      let env = match a.fun_name with
	| None -> env
	| Some f -> Env.add f a.fun_typ env in
476
477
      List.iter 
	(fun (t1,t2) ->
478
	   ignore (type_check_branches loc env t1 a.fun_body t2 false)
479
480
	) a.fun_iface;
      t
481

482
483
  | Match (e,b) ->
      let t = type_check env e b.br_accept true in
484
      type_check_branches loc env t b constr precise
485
486
487

  | Try (e,b) ->
      let te = type_check env e constr precise in
488
      let tb = type_check_branches loc env Types.any b constr precise in
489
      Types.cup te tb
490

491
  | Pair (e1,e2) -> 
492
493
494
495
496
497
498
499
500
501
502
503
504
      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
505

506
507
508
509
510
511
512
513
514
515
516
517
518
519
  | RecordLitt r ->
      let rconstr = Types.Record.get constr in
      if Types.Record.is_empty rconstr then
	raise_loc loc (ShouldHave (constr,"but it is a record."));

      let (rconstr,res) = 
	List.fold_left 
	  (fun (rconstr,res) (l,e) ->
	     let rconstr = Types.Record.restrict_label_present rconstr l in
	     let pi = Types.Record.project_field rconstr l in
	     if Types.Record.is_empty rconstr then
	       raise_loc loc 
		 (ShouldHave (constr,(Printf.sprintf 
					"Field %s is not allowed here."
520
					(Types.LabelPool.value l)
521
522
523
524
525
526
527
528
529
530
531
532
533
534
				     )
			     ));
	     let t = type_check env e pi true in
	     let rconstr = Types.Record.restrict_field rconstr l t in
	     
	     let res = 
	       if precise 
	       then Types.cap res (Types.record l false (Types.cons t))
	       else res in
	     (rconstr,res)
	  ) (rconstr, if precise then Types.Record.any else constr) r
      in
      res

535
536
537
538
539
  | Map (e,b) ->
      let t = type_check env e (Sequence.star b.br_accept) true in

      let constr' = Sequence.approx (Types.cap Sequence.any constr) in
      let exact = Types.subtype (Sequence.star constr') constr in
540
541
542
543
544
545
546
      (* Note: 
	 - could be more precise by integrating the decomposition
	 of constr inside Sequence.map.
      *)
      let res = 
	Sequence.map 
	  (fun t -> 
547
	     type_check_branches loc env t b constr' (precise || (not exact)))
548
549
550
	  t in
      if not exact then check loc res constr "";
      if precise then res else constr
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
  | Op ("@", [e1;e2]) ->
      let constr' = Sequence.star 
		      (Sequence.approx (Types.cap Sequence.any constr)) in
      let exact = Types.subtype constr' constr in
      if exact then
	let t1 = type_check env e1 constr' precise
	and t2 = type_check env e2 constr' precise in
	if precise then Sequence.concat t1 t2 else constr
      else
	(* Note:
	   the knownledge of t1 may makes it useless to
	   check t2 with 'precise' ... *)
	let t1 = type_check env e1 constr' true
	and t2 = type_check env e2 constr' true in
	let res = Sequence.concat t1 t2 in
	check loc res constr "";
	if precise then res else constr
568
569
570
571
572
573
574
575
576
577
578
579
580
  | Op ("flatten", [e]) ->
      let constr' = Sequence.star 
		      (Sequence.approx (Types.cap Sequence.any constr)) in
      let sconstr' = Sequence.star constr' in
      let exact = Types.subtype constr' constr in
      if exact then
	let t = type_check env e sconstr' precise in
	if precise then Sequence.flatten t else constr
      else
	let t = type_check env e sconstr' true in
	let res = Sequence.flatten t in
	check loc res constr "";
	if precise then res else constr
581
582
583
584
585
586
587
588
589
590
  | _ -> 
      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
591
592
593
594
  | Var s -> 
      (try Env.find s env 
       with Not_found -> raise_loc loc (UnboundId s)
      )
595
596
597
598
599
600
601
602
603
604
  | 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
605
606
607
608
  | 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)))
609
610
611
  | Op (op, el) ->
      let args = List.map (fun e -> (e.exp_loc, compute_type env e)) el in
      type_op loc op args
612
613
  | Map (e,b) ->
      let t = compute_type env e in
614
      Sequence.map (fun t -> type_check_branches loc env t b Types.any true) t
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632

(* We keep these cases here to allow comparison and benchmarking ...
   Just comment the corresponding cases in type_check' to
   activate these ones.
*)
  | Pair (e1,e2) -> 
      let t1 = compute_type env e1 
      and t2 = compute_type env e2 in
      Types.times (Types.cons t1) (Types.cons t2)
  | 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


633
  | _ -> assert false
634

635
and type_check_branches loc env targ brs constr precise =
636
  if Types.is_empty targ then Types.empty 
637
638
  else (
    brs.br_typ <- Types.cup brs.br_typ targ;
639
    branches_aux loc env targ 
640
641
      (if precise then Types.empty else constr) 
      constr precise brs.br_branches
642
  )
643
    
644
645
and branches_aux loc env targ tres constr precise = function
  | [] -> raise_loc loc (NonExhaustive targ)
646
647
648
649
650
651
  | 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' 
652
      then branches_aux loc env targ tres constr precise rem
653
654
655
656
657
658
      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
659
660
	  let t = type_check env' b.br_body constr precise in
	  let tres = if precise then Types.cup t tres else tres in
661
662
	  let targ'' = Types.diff targ acc in
	  if (Types.non_empty targ'') then 
663
	    branches_aux loc env targ'' tres constr precise rem 
664
665
	  else
	    tres
666
	)
667

668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
and type_let_decl env l =
  let acc = Types.descr (Patterns.accept l.let_pat) in
  let t = type_check env l.let_body acc true in
  let res = Patterns.filter t l.let_pat in
  List.map (fun (x,t) -> (x, Types.descr t)) res

and type_rec_funs env l =
  let types = 
    List.fold_left
      (fun accu -> function  {let_body={exp_descr=Abstraction a}} as l ->
	 let t = a.fun_typ in
	 let acc = Types.descr (Patterns.accept l.let_pat) in
	 if not (Types.subtype t acc) then
	   raise_loc l.let_body.exp_loc (NonExhaustive (Types.diff t acc));
	 let res = Patterns.filter t l.let_pat in
	 List.fold_left (fun accu (x,t) -> (x, Types.descr t)::accu) accu res
	 | _ -> assert false) [] l
  in
  let env' = List.fold_left (fun env (x,t) -> Env.add x t env) env types in
  List.iter 
    (function  { let_body = { exp_descr = Abstraction a } } as l ->
       ignore (type_check env' l.let_body Types.any false)
       | _ -> assert false) l;
  types


694
695
and type_op loc op args =
  match (op,args) with
696
    | "+", [loc1,t1; loc2,t2] ->
697
	type_int_binop Intervals.add loc1 t1 loc2 t2
698
699
700
    | "-", [loc1,t1; loc2,t2] ->
	type_int_binop Intervals.sub loc1 t1 loc2 t2
    | ("*" | "/"), [loc1,t1; loc2,t2] ->
701
	type_int_binop (fun i1 i2 -> Intervals.any) loc1 t1 loc2 t2
702
    | "@", [loc1,t1; loc2,t2] ->
703
704
705
	check loc1 t1 Sequence.any
	  "The first argument of @ must be a sequence";
	Sequence.concat t1 t2
706
    | "flatten", [loc1,t1] ->
707
708
709
	check loc1 t1 Sequence.seqseq 
	  "The argument of flatten must be a sequence of sequences";
	Sequence.flatten t1
710
711
712
713
    | "load_xml", [loc1,t1] ->
	check loc1 t1 Sequence.string
	  "The argument of load_xml must be a string (filename)";
	Types.any
714
715
    | "raise", [loc1,t1] ->
	Types.empty
716
717
    | "print_xml", [loc1,t1] ->
	Sequence.string
718
719
720
721
722
723
    | "int_of", [loc1,t1] ->
	check loc1 t1 Sequence.string
	  "The argument of int_of must a string";
	if not (Types.subtype t1 Builtin.intstr) then
	  warning loc "This application of int_of may fail";
	Types.interval Intervals.any
724
725
726
727
728
729
730
731
732
733
734
    | _ -> 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 
735
	       (t2,Types.Int.any,
736
737
738
739
740
		"The second argument must be an integer"));
  Types.Int.put
    (f (Types.Int.get t1) (Types.Int.get t2));