Debian Codegraph @

src/nekoml/Typer.nml

raw
1 /*
2 * Copyright (C)2005-2022 Haxe Foundation
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included in
12 * all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20 * DEALINGS IN THE SOFTWARE.
21 */
22
23 open Nekoml.Ast;
24 open Nekoml.Type;
25
26 type module_context {
27 mutable file : string;
28 path : string list;
29 types : (string,t) Hashtbl.t;
30 constrs : (string, (t, t)) Hashtbl.t;
31 records : (string, (t, t, mutflag)) Hashtbl.t;
32 deps : (string list, module_context) Hashtbl.t;
33 mutable done : bool;
34 mutable idents : (string,t) Map.t;
35 }
36
37 type context {
38 gen : id_gen;
39 mutable mink : int;
40 mutable functions : (bool, string, texpr ref, t, (string, t) list, expr, t, pos) list;
41 mutable opens : module_context list;
42 mutable curfunction : string;
43 filecache : (string, string) Hashtbl.t;
44 tmptypes : (string, (t, t list, (string,t) Hashtbl.t)) Hashtbl.t;
45 current : module_context;
46 modules : (string list, module_context) Hashtbl.t;
47 classpath : string list;
48 callback : context -> module_context -> texpr -> void;
49 }
50
51 type error_msg {
52 Cannot_unify : (t, t);
53 Have_no_field : (t, string);
54 Stack : (error_msg, error_msg);
55 Unknown_field : string;
56 Module_not_loaded : module_context;
57 Custom : string;
58 }
59
60 exception Error : (error_msg , pos);
61
62 function rec error_msg_loop(h,m) {
63 match m {
64 | Cannot_unify (t1,t2) -> "Cannot unify " + s_type false h t1 + " and " + s_type false h t2
65 | Have_no_field (t,f) -> s_type false h t + " have no field " + f
66 | Stack (m1,m2) -> error_msg_loop h m1 + "\n " + error_msg_loop h m2
67 | Unknown_field s -> "Unknown field " + s
68 | Module_not_loaded m -> "Module " + String.concat "." m.path + " require an interface"
69 | Custom s -> s
70 }
71 }
72
73 function error_msg(m) {
74 error_msg_loop s_context() m
75 }
76
77 function s_ttype(t) {
78 s_type false s_context() t
79 }
80
81 function error(m,p) {
82 throw Error(m,p)
83 }
84
85 Nekoml.Match.error_ref := (function(msg,p) error Custom(msg) p);
86
87 var verbose = &false;
88
89 var load_module_ref = &(function(_,_,_) { assert() });
90
91 function add_local(ctx,v,t) {
92 if v != "_" then ctx.current.idents := Map.add ctx.current.idents v t
93 }
94
95 function save_locals(ctx) {
96 ctx.current.idents
97 }
98
99 function restore_locals(ctx,l) {
100 ctx.current.idents := l
101 }
102
103 function module(ctx,path) {
104 Hashtbl.find ctx.modules path
105 }
106
107 function union(m,c) {
108 fst (Hashtbl.find m.constrs c)
109 }
110
111 function get_module(ctx,path,p) {
112 match path {
113 | [] -> ctx.current
114 | _ ->
115 var m = try
116 Hashtbl.find ctx.modules path
117 catch { Not_found -> (*load_module_ref) ctx path p };
118 if m != ctx.current then {
119 if !m.done then error (Module_not_loaded m) p;
120 Hashtbl.replace ctx.current.deps m.path m;
121 };
122 m
123 }
124 }
125
126 function get_type(ctx,path,name,p) {
127 function rec loop(l) {
128 match l {
129 | [] -> error Custom("Unknown type " + s_path path name) p
130 | m :: l ->
131 try {
132 Hashtbl.find m.types name
133 } catch {
134 Not_found -> loop l
135 }
136 }
137 }
138 match path {
139 | [] ->
140 loop (ctx.current :: ctx.opens);
141 | _ ->
142 loop [get_module ctx path p]
143 }
144 }
145
146 function get_constr(ctx,path,name,p) {
147 function rec loop(l) {
148 match l {
149 | [] -> error Custom("Unknown constructor " + s_path path name) p
150 | m :: l ->
151 try {
152 var t1, t2 = Hashtbl.find m.constrs name;
153 (if m == ctx.current then [] else m.path , t1, t2)
154 } catch {
155 Not_found -> loop l
156 }
157 }
158 };
159 match path {
160 | [] ->
161 loop (ctx.current :: ctx.opens)
162 | _ ->
163 loop [get_module ctx path p]
164 }
165 }
166
167 function get_ident(ctx,path,name,p) {
168 function rec loop(l) {
169 match l {
170 | [] -> error Custom("Unknown identifier " + s_path path name) p
171 | m :: l ->
172 try
173 (if m == ctx.current then [] else m.path , Map.find m.idents name)
174 catch {
175 Not_found -> loop l
176 }
177 }
178 }
179 match path {
180 | [] ->
181 loop (ctx.current :: ctx.opens)
182 | _ ->
183 loop [get_module ctx path p]
184 }
185 }
186
187 function get_record(ctx,f,p) {
188 function rec loop(l) {
189 match l {
190 | [] -> error (Unknown_field f) p
191 | m :: l ->
192 try
193 Hashtbl.find m.records f
194 catch {
195 Not_found -> loop l
196 }
197 }
198 }
199 var rt , ft , mut = loop (ctx.current :: ctx.opens);
200 var h = Hashtbl.create();
201 (duplicate ctx.gen h rt, duplicate ctx.gen h ft, mut)
202 }
203
204 function rec is_tuple(t) {
205 match t.texpr {
206 | TLink t -> is_tuple t
207 | TTuple _ -> true
208 | TNamed(_,_,t) -> is_tuple t
209 | _ -> false
210 }
211 }
212
213 function rec is_recursive(t1,t2) {
214 if t1 === t2 then
215 true
216 else match t2.texpr {
217 | TAbstract
218 | TMono _
219 | TPoly ->
220 false
221 | TRecord _
222 | TUnion _ ->
223 assert()
224 | TTuple tl -> List.exists (is_recursive t1) tl
225 | TLink t -> is_recursive t1 t
226 | TFun (tl,t) -> List.exists (is_recursive t1) tl || is_recursive t1 t
227 | TNamed (_,p,t) -> List.exists (is_recursive t1) p
228 }
229 }
230
231 function link(ctx,t1,t2,p) {
232 if is_recursive t1 t2 then error Cannot_unify(t1,t2) p;
233 t1.texpr := TLink t2;
234 if t1.tid < 0 then {
235 if t2.tid == -1 then t1.tid := -1 else t1.tid := genid ctx.gen;
236 } else
237 if t2.tid == -1 then t1.tid := -1
238 }
239
240 function unify_stack(t1,t2,e) {
241 match e {
242 | Error ((Cannot_unify _) as e, p) -> error (Stack e Cannot_unify(t1,t2)) p
243 | e -> throw e
244 }
245 }
246
247 function is_alias(t) {
248 match t {
249 | TAbstract
250 | TRecord _
251 | TUnion _ -> false
252 | TMono _
253 | TPoly
254 | TTuple _
255 | TLink _
256 | TFun _
257 | TNamed _ -> true
258 }
259 }
260
261 function rec propagate(k,t) {
262 match t.texpr {
263 | TAbstract
264 | TPoly -> ()
265 | TUnion _
266 | TRecord _ -> assert()
267 | TMono k2 -> if k < k2 then t.texpr := TMono k
268 | TTuple tl -> List.iter (propagate k) tl
269 | TLink t -> propagate k t
270 | TFun (tl,t) -> propagate k t; List.iter (propagate k) tl
271 | TNamed (_,tl,_) -> List.iter (propagate k) tl
272 }
273 }
274
275 function rec unify(ctx,t1,t2,p) {
276 if t1 == t2 then
277 ()
278 else match (t1.texpr , t2.texpr) {
279 | (TLink t , _) -> unify ctx t t2 p
280 | (_ , TLink t) -> unify ctx t1 t p
281 | (TPoly , _) -> link ctx t1 t2 p
282 | (_ , TPoly) -> link ctx t2 t1 p
283 | (TMono k , _) -> link ctx t1 t2 p; propagate k t2
284 | (_ , TMono k) -> link ctx t2 t1 p; propagate k t1
285 | (TNamed (n1,p1,_) , TNamed (n2,p2,_)) when n1 == n2 ->
286 try
287 List.iter2 (function(p1,p2) { unify ctx p1 p2 p }) p1 p2
288 catch { e -> unify_stack t1 t2 e }
289 | (TNamed (_,_,t1) , _) when is_alias t1.texpr ->
290 try
291 unify ctx t1 t2 p
292 catch { e -> unify_stack t1 t2 e }
293 | (_ , TNamed (_,_,t2)) when is_alias t2.texpr ->
294 try
295 unify ctx t1 t2 p
296 catch { e -> unify_stack t1 t2 e }
297 | (TFun (tl1,r1) , TFun (tl2,r2)) when List.length tl1 == List.length tl2 ->
298 try
299 List.iter2 (function(t1,t2) { unify ctx t1 t2 p }) tl1 tl2;
300 unify ctx r1 r2 p;
301 catch { e -> unify_stack t1 t2 e }
302 | (TTuple tl1 , TTuple tl2) when List.length tl1 == List.length tl2 ->
303 try
304 List.iter2 (function(t1,t2) { unify ctx t1 t2 p }) tl1 tl2
305 catch { e -> unify_stack t1 t2 e }
306 | _ ->
307 error Cannot_unify(t1,t2) p
308 }
309 }
310
311 function rec type_type(allow,h,ctx,t,p) {
312 match t {
313 | ETuple [] ->
314 assert()
315 | ETuple [t] ->
316 type_type allow h ctx t p
317 | ETuple el ->
318 mk_tup ctx.gen (List.map (function(t) { type_type allow h ctx t p }) el)
319 | EPoly s ->
320 try
321 Hashtbl.find h s
322 catch {
323 Not_found ->
324 if !allow then error Custom("Unbound type variable '" + s) p;
325 var t = t_mono ctx.gen;
326 Hashtbl.add h s t;
327 t
328 }
329 | EType (param,path,name) ->
330 var param = match param { None -> None | Some t -> Some (type_type allow h ctx t p) };
331 var t = get_type ctx path name p;
332 match t.texpr {
333 | TNamed (_,params,t2) ->
334 var tl = match (params, param) {
335 | ([] , None) -> []
336 | ([x] , Some t) -> [t]
337 | (l , Some { texpr = TTuple tl }) when List.length tl == List.length l -> tl
338 | _ -> error Custom("Invalid number of type parameters for " + s_path path name) p
339 };
340 var h = Hashtbl.create();
341 var t = duplicate ctx.gen h t;
342 var params = List.map (duplicate ctx.gen h) params;
343 List.iter2 (function(pa,t) { unify ctx pa t p }) params tl;
344 t
345 | _ ->
346 assert()
347 }
348 | EArrow _ ->
349 function rec loop(params,t) {
350 match t {
351 | EArrow (ta,tb) ->
352 var ta = type_type allow h ctx ta p;
353 loop (ta :: params) tb
354 | _ ->
355 var t = type_type allow h ctx t p;
356 mk_fun ctx.gen (List.rev params) t
357 }
358 };
359 loop [] t
360 }
361 }
362
363 function rec type_constant(ctx,path,c,p) {
364 match c {
365 | Int i -> mk TConst(TInt i) t_int p
366 | Float s -> mk TConst(TFloat s) t_float p
367 | Bool b -> mk TConst(TBool b) t_bool p
368 | String s -> mk TConst(TString s) t_string p
369 | Char c -> mk TConst(TChar c) t_char p
370 | Ident s ->
371 var path , t = get_ident ctx path s p;
372 var t = duplicate ctx.gen Hashtbl.create() t;
373 mk TConst(TModule path TIdent(s)) t p
374 | Constr s ->
375 var path , ut , t = get_constr ctx path s p;
376 var t = duplicate ctx.gen Hashtbl.create() (match t.texpr {
377 | TAbstract -> ut
378 | TTuple tl -> mk_fun ctx.gen tl ut
379 | _ -> mk_fun ctx.gen [t] ut
380 });
381 mk TConst(TModule path TConstr(s)) t p
382 | Module (path,c) ->
383 type_constant ctx path c p
384 }
385 }
386
387 type addable {
388 NInt;
389 NFloat;
390 NString;
391 NNan;
392 }
393
394 function addable(str,e) {
395 match etype true e {
396 | TNamed (["int"],_,_) -> NInt
397 | TNamed (["float"],_,_) -> NFloat
398 | TNamed (["string"],_,_) when str -> NString
399 | _ -> NNan
400 }
401 }
402
403 function type_binop(ctx,op,e1,e2,p) {
404 function emk(t) { mk TBinop(op,e1,e2) t p };
405 match op {
406 | "%"
407 | "+"
408 | "-"
409 | "/"
410 | "*" ->
411 var str = (op == "+");
412 match (addable str e1, addable str e2) {
413 | (NInt , NInt) -> emk t_int
414 | (NFloat , NFloat)
415 | (NInt , NFloat)
416 | (NFloat , NInt) -> emk t_float
417 | (NInt , NString)
418 | (NFloat , NString)
419 | (NString , NInt)
420 | (NString , NFloat)
421 | (NString , NString) -> emk t_string
422 | (NInt , NNan)
423 | (NFloat , NNan)
424 | (NString , NNan) ->
425 unify ctx e2.etype e1.etype (pos e2);
426 emk e1.etype
427 | (NNan , NInt)
428 | (NNan , NFloat)
429 | (NNan , NString) ->
430 unify ctx e1.etype e2.etype (pos e1);
431 emk e2.etype
432 | (NNan , NNan) ->
433 unify ctx e1.etype t_int (pos e1);
434 unify ctx e2.etype t_int (pos e2);
435 emk t_int
436 }
437 | ">>"
438 | ">>>"
439 | "<<"
440 | "and"
441 | "or"
442 | "xor" ->
443 unify ctx e1.etype t_int (pos e1);
444 unify ctx e2.etype t_int (pos e2);
445 emk t_int
446 | "&&"
447 | "||" ->
448 unify ctx e1.etype t_bool (pos e1);
449 unify ctx e2.etype t_bool (pos e2);
450 emk t_bool
451 | "<"
452 | "<="
453 | ">"
454 | ">="
455 | "=="
456 | "!="
457 | "==="
458 | "!==" ->
459 unify ctx e2.etype e1.etype (pos e2);
460 emk t_bool
461 | ":=" ->
462 match e1.edecl {
463 | TArray _ ->
464 unify ctx e2.etype e1.etype (pos e2);
465 emk t_void
466 | TField (e,f) ->
467 match tlinks false e.etype {
468 | TRecord fl ->
469 var _ , mut , _ = try List.find (function((f2,_,_)) { f2 == f }) fl catch { Not_found -> assert() };
470 if mut == Immutable then error Custom("Field " + f + " is not mutable") pos(e1);
471 unify ctx e2.etype e1.etype (pos e2);
472 emk t_void
473 | _ -> assert();
474 }
475 | _ ->
476 var t , pt = t_poly ctx.gen "ref";
477 unify ctx e2.etype pt (pos e2);
478 unify ctx e1.etype t (pos e1);
479 emk t_void
480 }
481 | "::" ->
482 var t , pt = t_poly ctx.gen "list";
483 unify ctx e1.etype pt (pos e1);
484 unify ctx e2.etype t (pos e2);
485 var c = mk TConst(TConstr "::") t_mono(ctx.gen) p;
486 mk (TCall c [e1;e2]) t p
487 | _ ->
488 error Custom("Invalid operation " + op) p
489 }
490 }
491
492 function type_unop(ctx,op,e,p) {
493 function emk(t) { mk TUnop(op,e) t p };
494 match op {
495 | "&" ->
496 var p , pt = t_poly ctx.gen "ref";
497 unify ctx e.etype pt (pos e);
498 emk p
499 | "*" ->
500 var p , pt = t_poly ctx.gen "ref";
501 unify ctx e.etype p (pos e);
502 emk pt
503 | "!" ->
504 unify ctx e.etype t_bool (pos e);
505 emk t_bool
506 | "-" ->
507 match addable false e {
508 | NInt -> emk t_int
509 | NFloat -> emk t_float
510 | _ ->
511 unify ctx e.etype t_int (pos e);
512 emk t_int
513 }
514 | _ ->
515 assert()
516 }
517 }
518
519 function rec type_arg(ctx,h,binds,p,a) {
520 match a {
521 | ATyped (a,t) ->
522 var n , ta = type_arg ctx h binds p a;
523 unify ctx ta (type_type true h ctx t p) p;
524 (n , ta)
525 | ANamed s ->
526 (s , t_mono ctx.gen)
527 | ATuple al ->
528 var aname = "@t" + string (genid ctx.gen);
529 var nl , tl = List.split (List.map (type_arg ctx h binds p) al);
530 var k = &0;
531 List.iter (function(n) {
532 if n != "_" then binds := (aname,*k,n) :: *binds;
533 k := *k + 1;
534 }) nl;
535 (aname , mk_tup ctx.gen tl)
536 }
537 }
538
539 function register_function(ctx,isrec,name,pl,e,rt,p) {
540 if ctx.functions == [] then ctx.mink := *ctx.gen;
541 var pl = match pl {
542 | [] -> [ATyped (ANamed "_") EType(None,[],"void")]
543 | _ -> pl
544 };
545 var expr = &(mk (TConst TVoid) t_void p);
546 var h = Hashtbl.create();
547 var binds = &[];
548 var el = List.map (type_arg ctx h binds p) pl;
549 var name = match name { None -> "_" | Some n -> n };
550 var e = match List.rev (*binds) {
551 | [] -> e
552 | l ->
553 var b = List.fold (function(acc,(v,n,v2)) {
554 var tget = ETupleGet (EConst Ident(v),p) n;
555 (EVar [(v2,None)] (tget,p) , p) :: acc
556 }) [e] l;
557 (EBlock b , p)
558 };
559 var rt = match rt {
560 | None -> t_mono ctx.gen
561 | Some rt -> type_type true h ctx rt p
562 };
563 var ft = mk_fun ctx.gen (List.map snd el) rt;
564 ctx.functions := (isrec,name,expr,ft,el,e,rt,p) :: ctx.functions;
565 if isrec then add_local ctx name ft;
566 mk (TMut expr) (if name == "_" then ft else t_void) p
567 }
568
569
570 function type_format(ctx,s,p) {
571 var types = &[];
572 var percent = &false;
573 var i = &0;
574 var l = String.length s;
575 while *i < l {
576 var c = String.get s (*i);
577 if *percent then {
578 percent := false;
579 match c {
580 | '%' ->
581 ()
582 | 'x' | 'X' | 'd' ->
583 types := t_int :: *types
584 | 'f' ->
585 types := t_float :: *types
586 | 's' ->
587 types := t_string :: *types
588 | 'b' ->
589 types := t_bool :: *types
590 | 'c' ->
591 types := t_char :: *types
592 | '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9' | '.' ->
593 percent := true
594 | _ ->
595 error (Custom "Invalid % sequence") p
596 }
597 } else
598 match c {
599 | '%' ->
600 percent := true
601 | _ ->
602 ()
603 }
604 i := *i + 1;
605 };
606 if *percent then error (Custom "Invalid % sequence") p;
607 match *types {
608 | [] -> t_void
609 | [x] -> x
610 | l -> mk_tup ctx.gen (List.rev l)
611 }
612 }
613
614 function rec type_functions(ctx) {
615 var l = ctx.functions;
616 if l != [] then {
617 var mink = ctx.mink;
618 ctx.functions := [];
619 var l = List.map (function((isrec,name,expr,ft,el,e,rt,p)) {
620 var locals = save_locals ctx;
621 var func = ctx.curfunction;
622 if name != "_" then {
623 var fname = s_path ctx.current.path name;
624 if *verbose then print ("Typing "+fname+"\n");
625 ctx.curfunction := fname;
626 }
627 List.iter (function((p,pt)) {
628 add_local ctx p pt
629 }) el;
630 var e = type_expr ctx e;
631 restore_locals ctx locals;
632 ctx.curfunction := func;
633 var ft2 = mk_fun ctx.gen (List.map snd el) e.etype;
634 unify ctx ft ft2 p;
635 expr := mk TFunction(isrec,name,el,e) ft2 p;
636 if !isrec then add_local ctx name ft;
637 (name == "_" , ft2)
638 }) (List.rev l);
639 List.iter (function((anon,t)) {
640 if !anon then polymorphize ctx.gen mink t
641 }) l
642 }
643 }
644
645 function rec type_expr(ctx,(e,p)) {
646 match e {
647 | EConst c ->
648 type_constant ctx [] c p
649 | EBlock [] ->
650 mk TConst(TVoid) t_void p
651 | EBlock (e :: l) ->
652 var locals = save_locals ctx;
653 var e = type_block ctx e;
654 var el , t = List.fold (function((l,t),e) {
655 unify ctx t t_void (List.hd l).epos;
656 var e = type_block ctx e;
657 (e :: l , e.etype)
658 }) ([e] , e.etype) l;
659 type_functions ctx;
660 restore_locals ctx locals;
661 mk TBlock(List.rev el) t p
662 | EApply (e,el) ->
663 type_expr ctx (ECall e el,p)
664 | ECall ((EConst (Ident "open"),_),[(EConst (Module (m,Constr modname)),p)]) ->
665 ctx.opens := get_module ctx (List.append m [modname]) p :: ctx.opens;
666 mk (TConst TVoid) t_void p
667 | ECall ((EConst (Ident "open"),_),[(EConst (Constr modname),p)]) ->
668 ctx.opens := get_module ctx [modname] p :: ctx.opens;
669 mk (TConst TVoid) t_void p
670 | ECall ((EConst (Ident "assert"),_) as a,[]) ->
671 type_expr ctx (ECall a [(EConst (String p.psource),p);(EConst (Int p.pline),p)], p)
672 | ECall ((EConst (Ident "invalid_arg"),_) as a,[]) ->
673 type_expr ctx (ECall a [(EConst (String ctx.curfunction),p)], p)
674 | ECall ((EConst (Constr "TYPE"),_),[e]) ->
675 var e = type_expr ctx e;
676 printf "%s:(%d): type : %s\n" (p.psource,p.pline,s_type true s_context() e.etype);
677 mk (TParenthesis e) t_void p
678 | ECall (e,el) ->
679 var e = type_expr ctx e;
680 var el = match el { [] -> [(ETupleDecl [],p)] | _ -> el };
681 var el = List.map (type_expr ctx) el;
682 match etype false e {
683 | TFun (args,r) ->
684 function rec loop(acc,expr,l,tl,r) {
685 match (l , tl) {
686 | (e :: l , t :: tl) ->
687 match tlinks true t {
688 | TNamed (["format"],[param],_) ->
689 match e.edecl {
690 | TConst (TString s) ->
691 var tfmt = type_format ctx s e.epos;
692 unify ctx param tfmt e.epos;
693 | _ ->
694 match tlinks true e.etype {
695 | TNamed (["format"],[param2],_) ->
696 unify ctx param2 param e.epos
697 | _ ->
698 error Custom("Constant string required for format") e.epos
699 }
700 }
701 | _ ->
702 unify ctx e.etype t (pos e)
703 }
704 loop (e :: acc) expr l tl r
705 | ([] , []) ->
706 mk TCall(expr,List.rev acc) r p
707 | ([] , tl) ->
708 mk TCall(expr,List.rev acc) (mk_fun ctx.gen tl r) p
709 | (el , []) ->
710 match tlinks false r {
711 | TFun (args,r2) -> loop [] (mk TCall(expr,List.rev acc) r p) el args r2
712 | _ -> error Custom("Too many arguments") p
713 }
714 | _ ->
715 assert()
716 }
717 }
718 loop [] e el args r
719 | _ ->
720 var r = t_mono ctx.gen;
721 var f = mk_fun ctx.gen (List.map (function(e) { e.etype }) el) r;
722 unify ctx e.etype f p;
723 mk TCall(e,el) r p
724 }
725 | EField (e,s) ->
726 var e = type_expr ctx e;
727 var t = match etype false e {
728 | TRecord fl ->
729 try {
730 var _ , _ , t = List.find (function((s2,_,_)) { s == s2 }) fl;
731 t
732 } catch {
733 Not_found -> error Have_no_field(e.etype,s) p
734 }
735 | _ ->
736 var r , t , _ = get_record ctx s p;
737 unify ctx e.etype r (pos e);
738 t
739 };
740 mk TField(e,s) t p
741 | EArray (e,ei) ->
742 var e = type_expr ctx e;
743 var ei = type_expr ctx ei;
744 unify ctx ei.etype t_int (pos ei);
745 var t , pt = t_poly ctx.gen "array";
746 unify ctx e.etype t (pos e);
747 mk TArray(e,ei) pt p
748 | EVar _ ->
749 error Custom("Variable declaration not allowed outside a block") p
750 | EIf (e,e1,None) ->
751 var e = type_expr ctx e;
752 unify ctx e.etype t_bool (pos e);
753 var e1 = type_expr ctx e1;
754 unify ctx e1.etype t_void (pos e1);
755 mk TIf(e,e1,None) t_void p
756 | EIf (e,e1,Some e2) ->
757 var e = type_expr ctx e;
758 unify ctx e.etype t_bool (pos e);
759 var e1 = type_expr ctx e1;
760 var e2 = type_expr ctx e2;
761 unify ctx e2.etype e1.etype (pos e2);
762 mk TIf(e,e1,Some e2) e1.etype p
763 | EWhile (e1,e2) ->
764 var e1 = type_expr ctx e1;
765 unify ctx e1.etype t_bool (pos e1);
766 var e2 = type_expr ctx e2;
767 unify ctx e2.etype t_void (pos e2);
768 mk TWhile(e1,e2) t_void p
769 | EFunction (isrec,name,pl,e,rt) ->
770 var r = register_function ctx isrec name pl e rt p;
771 type_functions ctx;
772 r
773 | EBinop (op,e1,e2) ->
774 type_binop ctx op (type_expr ctx e1) (type_expr ctx e2) p
775 | ETypeAnnot (e,t) ->
776 var e = type_expr ctx e;
777 var t = type_type true Hashtbl.create() ctx t p;
778 unify ctx e.etype t (pos e);
779 mk e.edecl t p
780 | ETupleDecl [] ->
781 mk TConst(TVoid) t_void p
782 | ETupleDecl [e] ->
783 var e = type_expr ctx e;
784 mk TParenthesis(e) e.etype (pos e)
785 | ETupleDecl el ->
786 var el = List.map (type_expr ctx) el;
787 mk TTupleDecl(el) (mk_tup ctx.gen (List.map (function(e) { e.etype }) el)) p
788 | ETypeDecl (params,tname,decl) ->
789 var fullname = match ctx.current.path { ["Core"] -> [tname] | p -> List.append p [tname]};
790 var t , tl , h = try {
791 var t , tl , h = Hashtbl.find ctx.tmptypes tname;
792 if decl != EAbstract then Hashtbl.remove ctx.tmptypes tname;
793 if List.length tl != List.length params then error Custom("Invalid number of parameters for type " + tname) p;
794 (t , tl , h)
795 } catch {
796 Not_found ->
797 if Hashtbl.exists ctx.current.types tname then error Custom("Invalid type redefinition of type " + tname) p;
798 var h = Hashtbl.create();
799 var tl = List.map (function(p) {
800 var t = t_mono ctx.gen;
801 Hashtbl.add h p t;
802 t
803 }) params;
804 var t = {
805 tid = -1;
806 texpr = TNamed fullname tl t_abstract;
807 };
808 Hashtbl.add ctx.current.types tname t;
809 if decl == EAbstract then Hashtbl.add ctx.tmptypes tname (t,tl,h);
810 (t , tl , h)
811 };
812 var t2 = match decl {
813 | EAbstract -> t_abstract
814 | EAlias t -> type_type false h ctx t p
815 | ERecord fields ->
816 var fields = List.map (function((f,m,ft)) {
817 var ft = type_type false h ctx ft p;
818 var m = (if m then Mutable else Immutable);
819 Hashtbl.add ctx.current.records f (t,ft,m);
820 (f , m , ft)
821 }) fields;
822 mk_record ctx.gen fields
823 | EUnion constr ->
824 var constr = List.map (function((c,ft)) {
825 var ft = match ft {
826 | None -> t_abstract
827 | Some ft -> type_type false h ctx ft p
828 };
829 Hashtbl.add ctx.current.constrs c (t,ft);
830 (c , ft)
831 }) constr;
832 mk_union ctx.gen constr
833 };
834 t.tid := if t2.tid == -1 && params == [] then -1 else genid ctx.gen;
835 t.texpr := TNamed fullname tl t2;
836 polymorphize ctx.gen 0 t;
837 mk TTypeDecl(t) t_void p
838 | ERecordDecl fl ->
839 var s , _ = try List.hd fl catch { _ -> assert() };
840 var r , _ , _ = get_record ctx s p;
841 var fll = match tlinks false r {
842 | TRecord fl -> fl
843 | _ -> assert()
844 };
845 var fl2 = &fll;
846 function rec loop(f,l) {
847 match l {
848 | [] ->
849 if List.exists (function((f2,_,_)) { f == f2 }) fll then
850 error Custom("Duplicate declaration for field " + f) p
851 else
852 error Have_no_field(r,f) p
853 | (f2,_,ft) :: l when f == f2 ->
854 (ft , l)
855 | x :: l ->
856 var t , l = loop f l;
857 (t , x :: l)
858 }
859 }
860 var el = List.map (function((f,e)) {
861 var ft , fl2b = loop f (*fl2);
862 fl2 := fl2b;
863 var e = type_expr ctx e;
864 unify ctx e.etype ft (pos e);
865 (f , e)
866 }) fl;
867 List.iter (function((f,_,_)) {
868 error Custom("Missing field " + f + " in record declaration") p;
869 }) (*fl2);
870 mk (TRecordDecl el) r p
871 | EErrorDecl (name,t) ->
872 var t = match t { None -> t_abstract | Some t -> type_type false Hashtbl.create() ctx t p };
873 Hashtbl.add ctx.current.constrs name (t_error,t);
874 mk TErrorDecl(name,t) t_void p
875 | EUnop (op,e) ->
876 type_unop ctx op (type_expr ctx e) p
877 | EMatch (e,cl) ->
878 var e = type_expr ctx e;
879 var is_stream = match cl { [] -> false | _ -> List.all (function((l,_,_)) { List.all (function((p,_)) { match p { PStream _ -> true | _ -> false }}) l}) cl };
880 var partial , m , t = type_match ctx e.etype cl p;
881 if !is_stream && partial then error Custom("This matching is not complete") p;
882 mk TMatch(e,m,is_stream) t p
883 | ETry (e,cl) ->
884 var e = type_expr ctx e;
885 var _ , m , t = type_match ctx t_error cl p;
886 unify ctx t e.etype p;
887 mk TTry(e,m) t p
888 | ETupleGet (e,n) ->
889 var e = type_expr ctx e;
890 function try_unify(et) {
891 var t = Array.init (n + 1) (function(_) { t_mono ctx.gen });
892 unify ctx et (mk_tup ctx.gen (Array.list t)) p;
893 t.[n]
894 }
895 function rec loop(et) {
896 match et.texpr {
897 | TLink et -> loop et
898 | TTuple l -> try List.nth l n catch { _ -> try_unify et }
899 | _ -> try_unify et
900 }
901 }
902 mk TTupleGet(e,n) (loop e.etype) p
903 }
904 }
905
906 function rec type_block(ctx,x) {
907 var e , p = x;
908 match e {
909 | EVar (vl,e) ->
910 type_functions ctx;
911 var e = type_expr ctx e;
912 function make(v,t) {
913 var t = match t {
914 | None -> t_mono ctx.gen
915 | Some t -> type_type true Hashtbl.create() ctx t p
916 }
917 add_local ctx v t;
918 t
919 }
920 var t = match vl {
921 | [] -> assert()
922 | [(v,t)] -> make v t
923 | _ ->
924 mk_tup ctx.gen (List.map (function((v,t)) { make v t }) vl)
925 }
926 unify ctx t e.etype (pos e);
927 mk TVar(List.map fst vl,e) t_void p
928 | EFunction (true,name,pl,e,rt) ->
929 register_function ctx true name pl e rt p
930 | _ ->
931 type_functions ctx;
932 type_expr ctx x
933 }
934 }
935
936 function rec type_pattern(ctx,h,h2,set,add,(pat,p)) {
937 function pvar(add,s) {
938 if Set.exists (*set) s then error Custom("This variable is several time in the pattern") p;
939 set := Set.add (*set) s;
940 try
941 Hashtbl.find h s
942 catch { Not_found ->
943 var t = t_mono ctx.gen;
944 Hashtbl.add h s t;
945 if add then add_local ctx s t;
946 t
947 }
948 }
949 var pt , pat = match pat {
950 | PConst c ->
951 (match c {
952 | Int n -> t_int
953 | Float s -> t_float
954 | String s -> t_string
955 | Char c -> t_char
956 | Bool b -> t_bool
957 | Ident _ | Constr _ | Module _ ->
958 assert()
959 } , pat)
960 | PTuple [p] ->
961 var pt , pat = type_pattern ctx h h2 set add p;
962 (pt , fst pat)
963 | PTuple pl ->
964 var pl , patl = List.split (List.map (type_pattern ctx h h2 set add) pl);
965 (mk_tup ctx.gen pl , PTuple patl)
966 | PRecord (fl,_) ->
967 var s = try fst (List.hd fl) catch { _ -> assert() };
968 var r , _ , _ = get_record ctx s p;
969 var fl = match tlinks false r {
970 | TRecord rl ->
971 List.map (function((f,pat)) {
972 var pt , pat = type_pattern ctx h h2 set add pat;
973 var t = try {
974 var _ , _ , t = List.find (function((f2,_,_)) { f == f2 }) rl;
975 t
976 } catch { Not_found ->
977 error Have_no_field(r,f) p
978 };
979 unify ctx pt t (snd pat);
980 (f , pat)
981 }) fl
982 | _ ->
983 assert()
984 };
985 (r , PRecord fl magic(r))
986 | PIdent s ->
987 (if s == "_" then t_mono ctx.gen else pvar add s , pat)
988 | PConstr (path,s,param) ->
989 var tparam , param = match param {
990 | None -> (None , None )
991 | Some ((_,p) as param) ->
992 var t , pat = type_pattern ctx h h2 set add param;
993 (Some (p,t) , Some pat)
994 }
995 var path , ut , t = get_constr ctx path s p;
996 match (t.texpr , tparam) {
997 | (TAbstract , None) -> (duplicate ctx.gen Hashtbl.create() ut , PConstr path s param)
998 | (TAbstract , Some _) -> error Custom("Constructor does not take parameters") p
999 | (_ , None) -> error Custom("Constructor require parameters") p
1000 | (_ , Some (p,pt)) ->
1001 var h = Hashtbl.create();
1002 var ut = duplicate ctx.gen h ut;
1003 var t = duplicate ctx.gen h t;
1004 var param , pt = match param {
1005 | Some (PTuple l,p) when !is_tuple t -> (Some (PTuple [(PTuple l,p)],p) , mk_fun ctx.gen [pt] ut)
1006 | Some (PIdent "_",p) -> (param , pt)
1007 | _ -> (param , match pt.texpr { TTuple l -> mk_fun ctx.gen l ut | _ -> mk_fun ctx.gen [pt] ut })
1008 }
1009 var t = match t.texpr { TTuple l -> mk_fun ctx.gen l ut | _ -> mk_fun ctx.gen [t] ut };
1010 unify ctx t pt p;
1011 (ut , PConstr path s param)
1012 }
1013 | PAlias (s,pat) ->
1014 var pt , pat = type_pattern ctx h h2 set false pat;
1015 var t = pvar false s;
1016 unify ctx pt t (snd pat);
1017 (t , PAlias s pat)
1018 | PTyped (pat,t) ->
1019 var pt , pat = type_pattern ctx h h2 set add pat;
1020 unify ctx pt (type_type true h2 ctx t p) p;
1021 (pt , PTyped pat t)
1022 | PStream (l,k) ->
1023 var t , polyt = t_poly ctx.gen "stream";
1024 var locals = save_locals ctx;
1025 var l = List.map (function(s) {
1026 match s {
1027 | SPattern pat ->
1028 var t , p = type_pattern ctx h h2 set true pat;
1029 unify ctx t polyt (snd p);
1030 SPattern p
1031 | SExpr ([v],e) ->
1032 var e = type_expr ctx e;
1033 var t = pvar true v;
1034 unify ctx t e.etype e.epos;
1035 SMagicExpr (PIdent v,e.epos) magic(e)
1036 | SExpr (vl,e) ->
1037 var e = type_expr ctx e;
1038 var tl = List.map (pvar true) vl;
1039 unify ctx (mk_tup ctx.gen tl) e.etype e.epos;
1040 var tup = PTuple (List.map (function(v) { (PIdent v, e.epos) }) vl);
1041 SMagicExpr (tup,e.epos) magic(e)
1042 | SMagicExpr _ ->
1043 assert()
1044 }
1045 }) l;
1046 restore_locals ctx locals;
1047 (t , PStream l k)
1048 }
1049 (pt , (pat,p))
1050 }
1051
1052 function rec type_match(ctx,t,cl,p) {
1053 var ret = t_mono ctx.gen;
1054 var cl = List.map (function((pl,wh,pe)) {
1055 var first = &true;
1056 var h = Hashtbl.create();
1057 var mainset = &Set.empty();
1058 var pl = List.map (function(pat) {
1059 var set = &Set.empty();
1060 var pt , pat = type_pattern ctx h Hashtbl.create() set false pat;
1061 if *first then {
1062 first := false;
1063 mainset := *set;
1064 } else {
1065 var s1 = Set.diff (*set) (*mainset);
1066 var s2 = Set.diff (*mainset) (*set);
1067 Set.iter (function(s) { error Custom("Variable " + s + " must occur in all patterns") p }) (Set.union s1 s2);
1068 }
1069 unify ctx pt t p;
1070 pat
1071 }) pl;
1072 var locals = save_locals ctx;
1073 Hashtbl.iter (function(v,t) { add_local ctx v t }) h;
1074 var wh = match wh {
1075 | None -> None
1076 | Some e ->
1077 var e = type_expr ctx e;
1078 unify ctx e.etype t_bool e.epos;
1079 Some e
1080 }
1081 var pe = type_expr ctx pe;
1082 unify ctx pe.etype ret (pos pe);
1083 restore_locals ctx locals;
1084 (pl , wh , pe)
1085 }) cl;
1086 Nekoml.Match.fully_matched_ref := (function(cl) {
1087 match cl {
1088 | (TModule(path,TConstr c)) :: l ->
1089 var path , ut , t = get_constr ctx path c Lexer.null_pos;
1090 if ut == t_error then
1091 false
1092 else match tlinks false ut {
1093 | TUnion (n,_) ->
1094 n == List.length cl
1095 | _ ->
1096 assert()
1097 }
1098 | TVoid :: _ ->
1099 true
1100 | _ ->
1101 false
1102 }
1103 });
1104 var partial , m = Nekoml.Match.make cl p;
1105 (partial , m , ret)
1106 }
1107
1108 function module_infos(m) {
1109 var h = Hashtbl.create();
1110 var deps = &(if m.path == ["Core"] || Hashtbl.exists m.deps ["Core"] then [] else [["Core"]]);
1111 var idents = &[];
1112 Hashtbl.iter (function(_,m) {
1113 deps := m.path :: *deps
1114 }) m.deps;
1115 Map.iter (function(i,t) {
1116 idents := i :: *idents
1117 }) m.idents;
1118 (m.path,*deps,*idents)
1119 }
1120
1121 function open_file(ctx,m,p) {
1122 var file = file_name m ".nml";
1123 function rec loop(l) {
1124 match l {
1125 | [] ->
1126 try {
1127 (file, IO.read_string (Hashtbl.find ctx.filecache (String.concat "." m)))
1128 } catch {
1129 Not_found -> error Custom("File not found " + file) p
1130 }
1131 | pp :: l ->
1132 try {
1133 var f = pp + file;
1134 (f , IO.read_file f true)
1135 } catch { _ -> loop l }
1136 }
1137 }
1138 loop ctx.classpath
1139 }
1140
1141 function load_module(ctx,m,p) {
1142 try
1143 Hashtbl.find ctx.modules m
1144 catch {
1145 Not_found ->
1146 var file , ch = open_file ctx m p;
1147 var is_core , core = try
1148 (false , Hashtbl.find ctx.modules ["Core"])
1149 catch { Not_found ->
1150 ctx.current.file := file;
1151 (true , ctx.current)
1152 }
1153 var ctx = {
1154 mink = ctx.mink;
1155 gen = ctx.gen;
1156 modules = ctx.modules;
1157 classpath = ctx.classpath;
1158 callback = ctx.callback;
1159 filecache = ctx.filecache;
1160
1161 curfunction = "anonymous";
1162 tmptypes = Hashtbl.create();
1163 functions = [];
1164 opens = [core];
1165 current = if is_core then ctx.current else {
1166 file = file;
1167 path = m;
1168 constrs = Hashtbl.create();
1169 records = Hashtbl.create();
1170 types = Hashtbl.create();
1171 done = false;
1172 idents = Map.empty();
1173 deps = Hashtbl.create();
1174 }
1175 };
1176 Hashtbl.add ctx.modules m ctx.current;
1177 var lex = Lexer.create Buffer.create();
1178 Lexer.input lex file ch 1 0;
1179 var ast = Nekoml.Parser.parse lex;
1180 if *verbose then printf "Parsed %s\n" file;
1181 var e = match ast {
1182 | (EBlock (e :: l) , p) ->
1183 var e = type_block ctx e;
1184 var el , t = List.fold (function((l,t),e) {
1185 var e = type_block ctx e;
1186 (e :: l , e.etype)
1187 }) ([e] , e.etype) l;
1188 type_functions ctx;
1189 mk TBlock(List.rev el) t p
1190 | _ ->
1191 type_expr ctx ast
1192 }
1193 if *verbose then printf "Typing done with %s\n" file;
1194 ctx.current.done := true;
1195 ctx.callback ctx ctx.current e;
1196 ctx.current
1197 }
1198 }
1199
1200 function context(cpath,filecache,callb) {
1201 var ctx = {
1202 gen = generator();
1203 tmptypes = Hashtbl.create();
1204 modules = Hashtbl.create();
1205 filecache = filecache;
1206 functions = [];
1207 opens = [];
1208 mink = 0;
1209 classpath = cpath;
1210 curfunction = "anonymous";
1211 callback = callb;
1212 current = {
1213 file = "";
1214 path = ["Core"];
1215 done = false;
1216 idents = Map.empty();
1217 constrs = Hashtbl.create();
1218 types = Hashtbl.create();
1219 deps = Hashtbl.create();
1220 records = Hashtbl.create();
1221 };
1222 };
1223 function add_type(args,name,t) {
1224 ignore(type_expr ctx (ETypeDecl args name t, Lexer.null_pos));
1225 }
1226 function add_variable(name,t) {
1227 ctx.current.idents := Map.add ctx.current.idents name t
1228 }
1229 add_type [] "bool" EUnion([("true",None);("false",None)]);
1230 add_type ["a"] "list" (EUnion [("[]",None);("::",Some (ETuple [
1231 EPoly "a";
1232 EType Some(EPoly "a") [] "list";
1233 ]))]);
1234 add_variable "neko" (mk_fun ctx.gen [t_polymorph ctx.gen] (t_polymorph ctx.gen));
1235 var core = load_module ctx ["Core"] Lexer.null_pos;
1236 ctx
1237 }
1238
1239 load_module_ref := load_module