typer.ml 19.5 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
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
  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
116
			 (fun v t -> mk noloc (And (t, (mk noloc (Capture v)), true)))
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
			 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 = 
142
    mk noloc (And (t, (mk noloc (Constant (v, Types.Atom atom_nil))), true))
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

  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
161
162
       with Not_found -> 
	 raise_loc loc (Pattern ("Undefined type variable " ^ s))
163
      )
164
  | Recurs (t, b) -> compile (compile_many env b) t
165
166
167
  | 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))
168
  | And (t1,t2,e) -> cons loc (`And (compile env t1, compile env t2,e))
169
170
171
172
173
174
175
  | 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)

176
177
178
179
180
181
182
183
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


184
185
186
187
188
189
let rec comp_fv seen s =
  match s.fv with
    | Some l -> l
    | None ->
	let l = 
	  match s.descr' with
190
	    | `Alias (_,x) -> if List.memq s seen then [] else comp_fv (s :: seen) x
191
	    | `Or (s1,s2) 
192
	    | `And (s1,s2,_)
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
	    | `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
209
210
211
212
213
    | `Alias (v,x) ->
	if List.memq s seen then 
	  raise_loc s.loc' 
	    (Pattern 
	       ("Unguarded recursion on variable " ^ v ^ " in this type"))
214
215
216
	else typ (s :: seen) x
    | `Type t -> t
    | `Or (s1,s2) -> Types.cup (typ seen s1) (typ seen s2)
217
    | `And (s1,s2,_) ->  Types.cap (typ seen s1) (typ seen s2)
218
219
220
221
    | `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)
222
    | `Capture _ | `Constant _ -> assert false
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

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

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

273
274
275
let global_types = ref StringMap.empty

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

let typ e =
  mk_typ (compile !global_types e)
282
283

let pat e =
284
  let e = compile !global_types e in
285
286
  pat_node e

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


297
298
(* II. Build skeleton *)

299
300
module Fv = StringSet

301
let rec expr { loc = loc; descr = d } = 
302
  let (fv,td) = 
303
    match d with
304
      | DebugTyper t -> (Fv.empty, Typed.DebugTyper (typ t))
305
306
307
      | Forget (e,t) ->
	  let (fv,e) = expr e and t = typ t in
	  (fv, Typed.Forget (e,t))
308
309
310
311
      | 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))
312
      | Abstraction a ->
313
314
315
316
	  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
317
318
319
	  let iface = List.map 
			(fun (t1,t2) -> (Types.descr t1, Types.descr t2)) 
			iface in
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
	  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))
337
338
      | Dot (e,l) ->
	  let (fv,e) = expr e in
339
	  (fv,  Typed.Dot (e,l))
340
341
      | RecordLitt r -> 
	  let fv = ref Fv.empty in
342
	  let r  = List.sort (fun (l1,_) (l2,_) -> compare l1 l2) r in
343
344
	  let r = List.map 
		    (fun (l,e) -> 
345
346
347
348
349
350
351
352
		       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;
353
	  (!fv, Typed.RecordLitt r)
354
355
356
357
      | 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))
358
359
360
361
362
363
364
365
      | 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))
366
367
368
369
      | Try (e,b) ->
	  let (fv1,e) = expr e
	  and (fv2,b) = branches b in
	  (Fv.union fv1 fv2, Typed.Try (e, b))
370
  in
371
372
  fv,
  { Typed.exp_loc = loc;
373
374
375
376
    Typed.exp_typ = Types.empty;
    Typed.exp_descr = td;
  }
	      
377
378
  and branches b = 
    let fv = ref Fv.empty in
379
    let accept = ref Types.empty in
380
381
382
383
    let b = List.map 
	      (fun (p,e) ->
		 let (fv2,e) = expr e in
		 fv := Fv.union !fv fv2;
384
385
		 let p = pat p in
		 accept := Types.cup !accept (Types.descr (Patterns.accept p));
386
		 { Typed.br_used = false;
387
		   Typed.br_pat = p;
388
389
		   Typed.br_body = e }
	      ) b in
390
391
392
393
    (!fv, 
     { 
       Typed.br_typ = Types.empty; 
       Typed.br_branches = b; 
394
395
       Typed.br_accept = !accept;
       Typed.br_compiled = None;
396
397
     } 
    )
398
399
400
401
402

module Env = StringMap

open Typed

403
404
405
406

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

407
let rec type_check env e constr precise = 
408
(*  Format.fprintf Format.std_formatter "constr=%a precise=%b@\n"
409
410
    Types.Print.print_descr constr precise; 
*)
411
  let d = type_check' e.exp_loc env e.exp_descr constr precise in
412
413
414
  e.exp_typ <- Types.cup e.exp_typ d;
  d

415
and type_check' loc env e constr precise = match e with
416
417
418
419
  | Forget (e,t) ->
      let t = Types.descr t in
      ignore (type_check env e t false);
      t
420
  | Abstraction a ->
421
422
423
424
425
426
427
      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
428
429
430
      let env = match a.fun_name with
	| None -> env
	| Some f -> Env.add f a.fun_typ env in
431
432
      List.iter 
	(fun (t1,t2) ->
433
	   ignore (type_check_branches loc env t1 a.fun_body t2 false)
434
435
	) a.fun_iface;
      t
436

437
438
  | Match (e,b) ->
      let t = type_check env e b.br_accept true in
439
      type_check_branches loc env t b constr precise
440
441
442

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

446
  | Pair (e1,e2) -> 
447
448
449
450
451
452
453
454
455
456
457
458
459
      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
460

461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
  | 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."
					(Types.label_name l)
				     )
			     ));
	     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

490
491
492
493
494
  | 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
495
496
497
498
499
500
501
502
503
504
505
(*
      Format.fprintf Format.std_formatter 
	"(Map) constr = %a@;  exact = %b\n@." Types.Print.print_descr constr exact;
*)
      (* Note: 
	 - could be more precise by integrating the decomposition
	 of constr inside Sequence.map.
      *)
      let res = 
	Sequence.map 
	  (fun t -> 
506
	     type_check_branches loc env t b constr' (precise || (not exact)))
507
508
509
	  t in
      if not exact then check loc res constr "";
      if precise then res else constr
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
  | 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
527
528
529
530
531
532
533
534
535
536
537
538
539
  | 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
540
541
542
543
544
545
546
547
548
549
  | _ -> 
      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
550
551
552
553
  | Var s -> 
      (try Env.find s env 
       with Not_found -> raise_loc loc (UnboundId s)
      )
554
555
556
557
558
559
560
561
562
563
  | 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
564
565
566
567
  | 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)))
568
569
570
  | Op (op, el) ->
      let args = List.map (fun e -> (e.exp_loc, compute_type env e)) el in
      type_op loc op args
571
572
  | Map (e,b) ->
      let t = compute_type env e in
573
      Sequence.map (fun t -> type_check_branches loc env t b Types.any true) t
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591

(* 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


592
  | _ -> assert false
593

594
and type_check_branches loc env targ brs constr precise =
595
  if Types.is_empty targ then Types.empty 
596
597
  else (
    brs.br_typ <- Types.cup brs.br_typ targ;
598
    branches_aux loc env targ 
599
600
      (if precise then Types.empty else constr) 
      constr precise brs.br_branches
601
  )
602
    
603
604
and branches_aux loc env targ tres constr precise = function
  | [] -> raise_loc loc (NonExhaustive targ)
605
606
607
608
609
610
  | 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' 
611
      then branches_aux loc env targ tres constr precise rem
612
613
614
615
616
617
      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
618
619
	  let t = type_check env' b.br_body constr precise in
	  let tres = if precise then Types.cup t tres else tres in
620
621
	  let targ'' = Types.diff targ acc in
	  if (Types.non_empty targ'') then 
622
	    branches_aux loc env targ'' tres constr precise rem 
623
624
	  else
	    tres
625
	)
626
627
628

and type_op loc op args =
  match (op,args) with
629
    | "+", [loc1,t1; loc2,t2] ->
630
	type_int_binop Intervals.add loc1 t1 loc2 t2
631
632
633
    | "-", [loc1,t1; loc2,t2] ->
	type_int_binop Intervals.sub loc1 t1 loc2 t2
    | ("*" | "/"), [loc1,t1; loc2,t2] ->
634
	type_int_binop (fun i1 i2 -> Intervals.any) loc1 t1 loc2 t2
635
    | "@", [loc1,t1; loc2,t2] ->
636
637
638
	check loc1 t1 Sequence.any
	  "The first argument of @ must be a sequence";
	Sequence.concat t1 t2
639
    | "flatten", [loc1,t1] ->
640
641
642
	check loc1 t1 Sequence.seqseq 
	  "The argument of flatten must be a sequence of sequences";
	Sequence.flatten t1
643
644
645
646
    | "load_xml", [loc1,t1] ->
	check loc1 t1 Sequence.string
	  "The argument of load_xml must be a string (filename)";
	Types.any
647
648
    | "raise", [loc1,t1] ->
	Types.empty
649
650
651
652
653
654
655
656
657
658
659
    | _ -> 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 
660
	       (t2,Types.Int.any,
661
662
663
664
665
		"The second argument must be an integer"));
  Types.Int.put
    (f (Types.Int.get t1) (Types.Int.get t2));