6 import std::map::hashmap;
10 import std::smallintmap;
11 import driver::session;
13 import syntax::ast::*;
14 import syntax::ast_util;
15 import syntax::codemap::span;
16 import metadata::csearch;
17 import util::common::*;
18 import syntax::util::interner;
19 import util::ppaux::ty_to_str;
20 import util::ppaux::ty_constr_to_str;
21 import util::ppaux::mode_str;
22 import syntax::print::pprust::*;
24 export node_id_to_monotype;
25 export node_id_to_type;
26 export node_id_to_type_params;
27 export node_id_to_ty_param_substs_opt_and_ty;
30 export ast_constr_to_constr;
33 export constr_general;
35 export count_ty_params;
37 export def_has_ty_params;
38 export expr_has_ty_params;
40 export expr_ty_params_and_ty;
47 export get_element_type;
51 export lookup_item_type;
87 export mk_opaque_closure_ptr;
92 export node_type_table;
95 export sequence_element_type;
101 export substitute_type_params;
105 export iface_methods, store_iface_methods, impl_iface;
106 export tag_variant_with_id;
107 export ty_param_substs_opt_and_ty;
108 export ty_param_bounds_and_ty;
114 export ty_opaque_closure_ptr;
115 export ty_constr_arg;
120 export ty_fn_ret_style;
140 export same_type, same_method;
142 export ty_param_substs_opt_and_ty_to_monotype;
145 export type_contains_params;
146 export type_contains_vars;
147 export kind, kind_sendable, kind_copyable, kind_noncopyable;
148 export kind_can_be_copied, kind_can_be_sent, proto_kind, kind_lteq, type_kind;
150 export type_err_to_str;
151 export type_has_dynamic_size;
152 export type_needs_drop;
156 export type_is_boxed;
157 export type_is_unique_box;
158 export type_is_unsafe_ptr;
161 export type_allows_implicit_copy;
162 export type_is_integral;
163 export type_is_numeric;
164 export type_is_native;
167 export type_is_scalar;
168 export type_is_immediate;
169 export type_is_sequence;
170 export type_is_signed;
171 export type_is_structural;
172 export type_is_copyable;
173 export type_is_tup_like;
175 export type_is_unique;
176 export type_structurally_contains_uniques;
177 export type_autoderef;
182 export occurs_check_fails;
184 export closure_block;
185 export closure_shared;
187 export param_bound, param_bounds, bound_copy, bound_send, bound_iface;
188 export param_bounds_to_kind;
192 type arg = {mode: mode, ty: t};
194 type field = {ident: ast::ident, mt: mt};
196 type param_bounds = @[param_bound];
198 type method = {ident: ast::ident, tps: @[param_bounds], fty: fn_ty};
200 type constr_table = hashmap<ast::node_id, [constr]>;
202 type mt = {ty: t, mut: ast::mutability};
205 // Contains information needed to resolve types and (in the future) look up
206 // the types of AST nodes.
207 type creader_cache = hashmap<{cnum: int, pos: uint, len: uint}, ty::t>;
211 sess: session::session,
212 def_map: resolve::def_map,
213 node_types: node_type_table,
215 freevars: freevars::freevar_map,
217 rcache: creader_cache,
218 short_names_cache: hashmap<t, @str>,
219 needs_drop_cache: hashmap<t, bool>,
220 kind_cache: hashmap<t, kind>,
221 ast_ty_to_ty_cache: hashmap<@ast::ty, option::t<t>>,
222 tag_var_cache: hashmap<def_id, @[variant_info]>,
223 iface_method_cache: hashmap<def_id, @[method]>,
224 ty_param_bounds: hashmap<ast::node_id, param_bounds>};
228 // Never construct these manually. These are interned.
229 type raw_t = {struct: sty,
242 type fn_ty = {proto: ast::proto,
245 ret_style: ret_style,
246 constraints: [@constr]};
248 // NB: If you change this, you'll probably want to change the corresponding
249 // AST structure in front/ast::rs as well.
255 ty_uint(ast::uint_ty);
256 ty_float(ast::float_ty);
265 ty_native_fn([arg], t);
267 ty_iface(def_id, [t]);
268 ty_res(def_id, t, [t]);
270 ty_var(int); // type variable
272 ty_param(uint, def_id); // fn/tag type param
274 ty_type; // type_desc*
275 ty_send_type; // type_desc* that has been cloned into exchange heap
277 ty_constr(t, [@type_constr]);
278 ty_opaque_closure_ptr(closure_kind); // ptr to env for fn, fn@, fn~
282 // In the middle end, constraints have a def_id attached, referring
283 // to the definition of the operator in the constraint.
284 type constr_general<ARG> = spanned<constr_general_<ARG, def_id>>;
285 type type_constr = constr_general<@path>;
286 type constr = constr_general<uint>;
288 // Data structures used in type unification
291 terr_ret_style_mismatch(ast::ret_style, ast::ret_style);
294 terr_tuple_size(uint, uint);
295 terr_record_size(uint, uint);
296 terr_record_mutability;
297 terr_record_fields(ast::ident, ast::ident);
299 terr_obj_meths(ast::ident, ast::ident);
301 terr_mode_mismatch(mode, mode);
302 terr_constr_len(uint, uint);
303 terr_constr_mismatch(@type_constr, @type_constr);
312 fn param_bounds_to_kind(bounds: param_bounds) -> kind {
313 let kind = kind_noncopyable;
314 for bound in *bounds {
317 if kind != kind_sendable { kind = kind_copyable; }
319 bound_send. { kind = kind_sendable; }
326 type ty_param_bounds_and_ty = {bounds: @[param_bounds], ty: t};
328 type type_cache = hashmap<ast::def_id, ty_param_bounds_and_ty>;
330 const idx_nil: uint = 0u;
332 const idx_bool: uint = 1u;
334 const idx_int: uint = 2u;
336 const idx_float: uint = 3u;
338 const idx_uint: uint = 4u;
340 const idx_i8: uint = 5u;
342 const idx_i16: uint = 6u;
344 const idx_i32: uint = 7u;
346 const idx_i64: uint = 8u;
348 const idx_u8: uint = 9u;
350 const idx_u16: uint = 10u;
352 const idx_u32: uint = 11u;
354 const idx_u64: uint = 12u;
356 const idx_f32: uint = 13u;
358 const idx_f64: uint = 14u;
360 const idx_char: uint = 15u;
362 const idx_str: uint = 16u;
364 const idx_type: uint = 17u;
366 const idx_send_type: uint = 18u;
368 const idx_bot: uint = 19u;
370 const idx_first_others: uint = 20u;
372 type type_store = interner::interner<@raw_t>;
374 type ty_param_substs_opt_and_ty = {substs: option::t<[ty::t]>, ty: ty::t};
376 type node_type_table =
377 @smallintmap::smallintmap<ty::ty_param_substs_opt_and_ty>;
379 fn populate_type_store(cx: ctxt) {
382 intern(cx, ty_int(ast::ty_i));
383 intern(cx, ty_float(ast::ty_f));
384 intern(cx, ty_uint(ast::ty_u));
385 intern(cx, ty_int(ast::ty_i8));
386 intern(cx, ty_int(ast::ty_i16));
387 intern(cx, ty_int(ast::ty_i32));
388 intern(cx, ty_int(ast::ty_i64));
389 intern(cx, ty_uint(ast::ty_u8));
390 intern(cx, ty_uint(ast::ty_u16));
391 intern(cx, ty_uint(ast::ty_u32));
392 intern(cx, ty_uint(ast::ty_u64));
393 intern(cx, ty_float(ast::ty_f32));
394 intern(cx, ty_float(ast::ty_f64));
395 intern(cx, ty_int(ast::ty_char));
398 intern(cx, ty_send_type);
400 assert (vec::len(cx.ts.vect) == idx_first_others);
403 fn mk_rcache() -> creader_cache {
404 type val = {cnum: int, pos: uint, len: uint};
405 fn hash_cache_entry(k: val) -> uint {
406 ret (k.cnum as uint) + k.pos + k.len;
408 fn eq_cache_entries(a: val, b: val) -> bool {
409 ret a.cnum == b.cnum && a.pos == b.pos && a.len == b.len;
411 ret map::mk_hashmap(hash_cache_entry, eq_cache_entries);
414 fn new_ty_hash<V: copy>() -> map::hashmap<t, V> { map::new_uint_hash() }
416 fn mk_ctxt(s: session::session, dm: resolve::def_map, amap: ast_map::map,
417 freevars: freevars::freevar_map) -> ctxt {
418 let ntt: node_type_table =
419 @smallintmap::mk::<ty::ty_param_substs_opt_and_ty>();
420 fn eq_raw_ty(&&a: @raw_t, &&b: @raw_t) -> bool {
421 ret a.hash == b.hash && a.struct == b.struct;
423 let ts = @interner::mk::<@raw_t>(hash_raw_ty, eq_raw_ty);
431 tcache: new_def_hash(),
433 short_names_cache: new_ty_hash(),
434 needs_drop_cache: new_ty_hash(),
435 kind_cache: new_ty_hash(),
437 map::mk_hashmap(ast_util::hash_ty, ast_util::eq_ty),
438 tag_var_cache: new_def_hash(),
439 iface_method_cache: new_def_hash(),
440 ty_param_bounds: map::new_int_hash()};
441 populate_type_store(cx);
447 fn mk_raw_ty(cx: ctxt, st: sty) -> @raw_t {
448 let h = hash_type_structure(st);
449 let has_params: bool = false;
450 let has_vars: bool = false;
451 fn derive_flags_t(cx: ctxt, &has_params: bool, &has_vars: bool, tt: t) {
452 let rt = interner::get::<@raw_t>(*cx.ts, tt);
453 has_params = has_params || rt.has_params;
454 has_vars = has_vars || rt.has_vars;
456 fn derive_flags_mt(cx: ctxt, &has_params: bool, &has_vars: bool, m: mt) {
457 derive_flags_t(cx, has_params, has_vars, m.ty);
459 fn derive_flags_arg(cx: ctxt, &has_params: bool, &has_vars: bool,
461 derive_flags_t(cx, has_params, has_vars, a.ty);
463 fn derive_flags_sig(cx: ctxt, &has_params: bool, &has_vars: bool,
464 args: [arg], tt: t) {
465 for a: arg in args { derive_flags_arg(cx, has_params, has_vars, a); }
466 derive_flags_t(cx, has_params, has_vars, tt);
469 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
470 ty_str. | ty_send_type. | ty_type. | ty_native(_) |
471 ty_opaque_closure_ptr(_) {
474 ty_param(_, _) { has_params = true; }
475 ty_var(_) { has_vars = true; }
476 ty_tag(_, tys) | ty_iface(_, tys) {
477 for tt: t in tys { derive_flags_t(cx, has_params, has_vars, tt); }
479 ty_box(m) { derive_flags_mt(cx, has_params, has_vars, m); }
480 ty_uniq(m) { derive_flags_mt(cx, has_params, has_vars, m); }
481 ty_vec(m) { derive_flags_mt(cx, has_params, has_vars, m); }
482 ty_ptr(m) { derive_flags_mt(cx, has_params, has_vars, m); }
484 for f: field in flds {
485 derive_flags_mt(cx, has_params, has_vars, f.mt);
489 for tt in ts { derive_flags_t(cx, has_params, has_vars, tt); }
492 derive_flags_sig(cx, has_params, has_vars, f.inputs, f.output);
494 ty_native_fn(args, tt) {
495 derive_flags_sig(cx, has_params, has_vars, args, tt);
498 for m: method in meths {
499 derive_flags_sig(cx, has_params, has_vars, m.fty.inputs,
504 derive_flags_t(cx, has_params, has_vars, tt);
505 for tt: t in tps { derive_flags_t(cx, has_params, has_vars, tt); }
507 ty_constr(tt, _) | ty_named(tt, _) {
508 derive_flags_t(cx, has_params, has_vars, tt);
513 has_params: has_params,
517 fn intern(cx: ctxt, st: sty) {
518 interner::intern(*cx.ts, mk_raw_ty(cx, st));
521 // These are private constructors to this module. External users should always
522 // use the mk_foo() functions below.
523 fn gen_ty(cx: ctxt, st: sty) -> t {
524 let raw_type = mk_raw_ty(cx, st);
525 ret interner::intern(*cx.ts, raw_type);
528 fn mk_nil(_cx: ctxt) -> t { ret idx_nil; }
530 fn mk_bot(_cx: ctxt) -> t { ret idx_bot; }
532 fn mk_bool(_cx: ctxt) -> t { ret idx_bool; }
534 fn mk_int(_cx: ctxt) -> t { ret idx_int; }
536 fn mk_float(_cx: ctxt) -> t { ret idx_float; }
538 fn mk_uint(_cx: ctxt) -> t { ret idx_uint; }
540 fn mk_mach_int(_cx: ctxt, tm: ast::int_ty) -> t {
542 ast::ty_i. { ret idx_int; }
543 ast::ty_char. { ret idx_char; }
544 ast::ty_i8. { ret idx_i8; }
545 ast::ty_i16. { ret idx_i16; }
546 ast::ty_i32. { ret idx_i32; }
547 ast::ty_i64. { ret idx_i64; }
551 fn mk_mach_uint(_cx: ctxt, tm: ast::uint_ty) -> t {
553 ast::ty_u. { ret idx_uint; }
554 ast::ty_u8. { ret idx_u8; }
555 ast::ty_u16. { ret idx_u16; }
556 ast::ty_u32. { ret idx_u32; }
557 ast::ty_u64. { ret idx_u64; }
561 fn mk_mach_float(_cx: ctxt, tm: ast::float_ty) -> t {
563 ast::ty_f. { ret idx_float; }
564 ast::ty_f32. { ret idx_f32; }
565 ast::ty_f64. { ret idx_f64; }
570 fn mk_char(_cx: ctxt) -> t { ret idx_char; }
572 fn mk_str(_cx: ctxt) -> t { ret idx_str; }
574 fn mk_tag(cx: ctxt, did: ast::def_id, tys: [t]) -> t {
575 ret gen_ty(cx, ty_tag(did, tys));
578 fn mk_box(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_box(tm)); }
580 fn mk_uniq(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_uniq(tm)); }
582 fn mk_imm_uniq(cx: ctxt, ty: t) -> t {
583 ret mk_uniq(cx, {ty: ty, mut: ast::imm});
586 fn mk_ptr(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_ptr(tm)); }
588 fn mk_imm_box(cx: ctxt, ty: t) -> t {
589 ret mk_box(cx, {ty: ty, mut: ast::imm});
592 fn mk_mut_ptr(cx: ctxt, ty: t) -> t {
593 ret mk_ptr(cx, {ty: ty, mut: ast::mut});
596 fn mk_vec(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_vec(tm)); }
598 fn mk_rec(cx: ctxt, fs: [field]) -> t { ret gen_ty(cx, ty_rec(fs)); }
600 fn mk_constr(cx: ctxt, t: t, cs: [@type_constr]) -> t {
601 ret gen_ty(cx, ty_constr(t, cs));
604 fn mk_tup(cx: ctxt, ts: [t]) -> t { ret gen_ty(cx, ty_tup(ts)); }
606 fn mk_fn(cx: ctxt, fty: fn_ty) -> t {
607 ret gen_ty(cx, ty_fn(fty));
610 fn mk_native_fn(cx: ctxt, args: [arg], ty: t) -> t {
611 ret gen_ty(cx, ty_native_fn(args, ty));
614 fn mk_obj(cx: ctxt, meths: [method]) -> t { ret gen_ty(cx, ty_obj(meths)); }
616 fn mk_iface(cx: ctxt, did: ast::def_id, tys: [t]) -> t {
617 ret gen_ty(cx, ty_iface(did, tys));
620 fn mk_res(cx: ctxt, did: ast::def_id, inner: t, tps: [t]) -> t {
621 ret gen_ty(cx, ty_res(did, inner, tps));
624 fn mk_var(cx: ctxt, v: int) -> t { ret gen_ty(cx, ty_var(v)); }
626 fn mk_param(cx: ctxt, n: uint, k: def_id) -> t {
627 ret gen_ty(cx, ty_param(n, k));
630 fn mk_type(_cx: ctxt) -> t { ret idx_type; }
632 fn mk_send_type(_cx: ctxt) -> t { ret idx_send_type; }
634 fn mk_native(cx: ctxt, did: def_id) -> t { ret gen_ty(cx, ty_native(did)); }
636 fn mk_opaque_closure_ptr(cx: ctxt, ck: closure_kind) -> t {
637 ret gen_ty(cx, ty_opaque_closure_ptr(ck));
640 fn mk_named(cx: ctxt, base: t, name: @str) -> t {
641 gen_ty(cx, ty_named(base, name))
644 // Returns the one-level-deep type structure of the given type.
645 pure fn struct(cx: ctxt, typ: t) -> sty {
646 alt interner::get(*cx.ts, typ).struct {
647 ty_named(t, _) { struct(cx, t) }
652 // Returns struact(cx, typ) but replaces all occurences of platform
653 // dependent primitive types with their machine type equivalent
654 pure fn mach_struct(cx: ctxt, cfg: @session::config, typ: t) -> sty {
655 alt interner::get(*cx.ts, typ).struct {
656 ty_named(t, _) { mach_struct(cx, cfg, t) }
657 s { mach_sty(cfg, s) }
661 // Converts s to its machine type equivalent
662 pure fn mach_sty(cfg: @session::config, s: sty) -> sty {
664 ty_int(ast::ty_i.) { ty_int(cfg.int_type) }
665 ty_uint(ast::ty_u.) { ty_uint(cfg.uint_type) }
666 ty_float(ast::ty_f.) { ty_float(cfg.float_type) }
671 pure fn ty_name(cx: ctxt, typ: t) -> option::t<@str> {
672 alt interner::get(*cx.ts, typ).struct {
673 ty_named(_, n) { some(n) }
680 type ty_walk = fn@(t);
682 fn walk_ty(cx: ctxt, walker: ty_walk, ty: t) {
684 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_uint(_) | ty_float(_) |
685 ty_str. | ty_send_type. | ty_type. | ty_native(_) |
686 ty_opaque_closure_ptr(_) {
689 ty_box(tm) | ty_vec(tm) | ty_ptr(tm) { walk_ty(cx, walker, tm.ty); }
690 ty_tag(_, subtys) | ty_iface(_, subtys) {
691 for subty: t in subtys { walk_ty(cx, walker, subty); }
694 for fl: field in fields { walk_ty(cx, walker, fl.mt.ty); }
696 ty_tup(ts) { for tt in ts { walk_ty(cx, walker, tt); } }
698 for a: arg in f.inputs { walk_ty(cx, walker, a.ty); }
699 walk_ty(cx, walker, f.output);
701 ty_native_fn(args, ret_ty) {
702 for a: arg in args { walk_ty(cx, walker, a.ty); }
703 walk_ty(cx, walker, ret_ty);
706 for m: method in methods {
707 for a: arg in m.fty.inputs { walk_ty(cx, walker, a.ty); }
708 walk_ty(cx, walker, m.fty.output);
711 ty_res(_, sub, tps) {
712 walk_ty(cx, walker, sub);
713 for tp: t in tps { walk_ty(cx, walker, tp); }
715 ty_constr(sub, _) { walk_ty(cx, walker, sub); }
716 ty_var(_) {/* no-op */ }
717 ty_param(_, _) {/* no-op */ }
718 ty_uniq(tm) { walk_ty(cx, walker, tm.ty); }
724 fm_var(fn@(int) -> t);
725 fm_param(fn@(uint, def_id) -> t);
726 fm_general(fn@(t) -> t);
729 fn fold_ty(cx: ctxt, fld: fold_mode, ty_0: t) -> t {
734 fm_var(_) { if !type_contains_vars(cx, ty) { ret ty; } }
735 fm_param(_) { if !type_contains_params(cx, ty) { ret ty; } }
736 fm_general(_) {/* no fast path */ }
738 alt interner::get(*cx.ts, ty).struct {
739 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_uint(_) | ty_float(_) |
740 ty_str. | ty_send_type. | ty_type. | ty_native(_) |
741 ty_opaque_closure_ptr(_) {
745 ty = mk_box(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
748 ty = mk_uniq(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
751 ty = mk_named(cx, fold_ty(cx, fld, t), nm);
754 ty = mk_ptr(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
757 ty = mk_vec(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
759 ty_tag(tid, subtys) {
760 ty = mk_tag(cx, tid, vec::map(subtys, {|t| fold_ty(cx, fld, t) }));
762 ty_iface(did, subtys) {
763 ty = mk_iface(cx, did, vec::map(subtys, {|t| fold_ty(cx, fld, t) }));
766 let new_fields: [field] = [];
767 for fl: field in fields {
768 let new_ty = fold_ty(cx, fld, fl.mt.ty);
769 let new_mt = {ty: new_ty, mut: fl.mt.mut};
770 new_fields += [{ident: fl.ident, mt: new_mt}];
772 ty = mk_rec(cx, new_fields);
776 for tt in ts { new_ts += [fold_ty(cx, fld, tt)]; }
777 ty = mk_tup(cx, new_ts);
780 let new_args: [arg] = [];
781 for a: arg in f.inputs {
782 let new_ty = fold_ty(cx, fld, a.ty);
783 new_args += [{mode: a.mode, ty: new_ty}];
785 ty = mk_fn(cx, {inputs: new_args,
786 output: fold_ty(cx, fld, f.output)
789 ty_native_fn(args, ret_ty) {
790 let new_args: [arg] = [];
792 let new_ty = fold_ty(cx, fld, a.ty);
793 new_args += [{mode: a.mode, ty: new_ty}];
795 ty = mk_native_fn(cx, new_args, fold_ty(cx, fld, ret_ty));
798 let new_methods = vec::map(methods, {|m|
799 let new_args = vec::map(m.fty.inputs, {|a|
800 {mode: a.mode, ty: fold_ty(cx, fld, a.ty)}
802 {ident: m.ident, tps: m.tps,
803 fty: {inputs: new_args,
804 output: fold_ty(cx, fld, m.fty.output)
807 ty = mk_obj(cx, new_methods);
809 ty_res(did, subty, tps) {
811 for tp: t in tps { new_tps += [fold_ty(cx, fld, tp)]; }
812 ty = mk_res(cx, did, fold_ty(cx, fld, subty), new_tps);
815 alt fld { fm_var(folder) { ty = folder(id); } _ {/* no-op */ } }
818 alt fld { fm_param(folder) { ty = folder(id, did); } _ {} }
820 ty_constr(subty, cs) {
821 ty = mk_constr(cx, fold_ty(cx, fld, subty), cs);
824 cx.sess.fatal("Unsupported sort of type in fold_ty");
828 // If this is a general type fold, then we need to run it now.
829 alt fld { fm_general(folder) { ret folder(ty); } _ { ret ty; } }
835 fn type_is_nil(cx: ctxt, ty: t) -> bool {
836 alt struct(cx, ty) { ty_nil. { ret true; } _ { ret false; } }
839 fn type_is_bot(cx: ctxt, ty: t) -> bool {
840 alt struct(cx, ty) { ty_bot. { ret true; } _ { ret false; } }
843 fn type_is_bool(cx: ctxt, ty: t) -> bool {
844 alt struct(cx, ty) { ty_bool. { ret true; } _ { ret false; } }
847 fn type_is_structural(cx: ctxt, ty: t) -> bool {
849 ty_rec(_) | ty_tup(_) | ty_tag(_, _) | ty_fn(_) |
850 ty_native_fn(_, _) | ty_obj(_) | ty_res(_, _, _) { true }
855 fn type_is_copyable(cx: ctxt, ty: t) -> bool {
856 ret kind_can_be_copied(type_kind(cx, ty));
859 fn type_is_sequence(cx: ctxt, ty: t) -> bool {
861 ty_str. { ret true; }
862 ty_vec(_) { ret true; }
867 fn type_is_str(cx: ctxt, ty: t) -> bool {
868 alt struct(cx, ty) { ty_str. { ret true; } _ { ret false; } }
871 fn sequence_element_type(cx: ctxt, ty: t) -> t {
873 ty_str. { ret mk_mach_uint(cx, ast::ty_u8); }
874 ty_vec(mt) { ret mt.ty; }
875 _ { cx.sess.bug("sequence_element_type called on non-sequence value"); }
879 pure fn type_is_tup_like(cx: ctxt, ty: t) -> bool {
880 let sty = struct(cx, ty);
882 ty_ptr(_) | ty_uniq(_) |
883 ty_box(_) | ty_rec(_) | ty_tup(_) | ty_tag(_,_) { true }
888 fn get_element_type(cx: ctxt, ty: t, i: uint) -> t {
890 ty_rec(flds) { ret flds[i].mt.ty; }
891 ty_tup(ts) { ret ts[i]; }
893 cx.sess.bug("get_element_type called on type " + ty_to_str(cx, ty) +
898 // NB: This is not exhaustive -- struct(cx, ty) could be a box or a
902 pure fn type_is_box(cx: ctxt, ty: t) -> bool {
904 ty_box(_) { ret true; }
909 pure fn type_is_boxed(cx: ctxt, ty: t) -> bool {
911 ty_box(_) | ty_iface(_, _) { ret true; }
916 pure fn type_is_unique_box(cx: ctxt, ty: t) -> bool {
918 ty_uniq(_) { ret true; }
923 pure fn type_is_unsafe_ptr(cx: ctxt, ty: t) -> bool {
925 ty_ptr(_) { ret true; }
930 pure fn type_is_vec(cx: ctxt, ty: t) -> bool {
931 ret alt struct(cx, ty) {
938 pure fn type_is_unique(cx: ctxt, ty: t) -> bool {
940 ty_uniq(_) { ret true; }
947 pure fn type_is_scalar(cx: ctxt, ty: t) -> bool {
949 ty_nil. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
950 ty_send_type. | ty_type. | ty_native(_) | ty_ptr(_) { true }
955 // FIXME maybe inline this for speed?
956 fn type_is_immediate(cx: ctxt, ty: t) -> bool {
957 ret type_is_scalar(cx, ty) || type_is_boxed(cx, ty) ||
958 type_is_unique(cx, ty) || type_is_native(cx, ty);
961 fn type_needs_drop(cx: ctxt, ty: t) -> bool {
962 alt cx.needs_drop_cache.find(ty) {
963 some(result) { ret result; }
964 none. {/* fall through */ }
968 let result = alt struct(cx, ty) {
970 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
971 ty_type. | ty_native(_) | ty_ptr(_) { false }
973 for f in flds { if type_needs_drop(cx, f.mt.ty) { accum = true; } }
977 for m in elts { if type_needs_drop(cx, m) { accum = true; } }
981 let variants = tag_variants(cx, did);
982 for variant in *variants {
983 for aty in variant.args {
984 // Perform any type parameter substitutions.
985 let arg_ty = substitute_type_params(cx, tps, aty);
986 if type_needs_drop(cx, arg_ty) { accum = true; }
995 cx.needs_drop_cache.insert(ty, result);
999 tag kind { kind_sendable; kind_copyable; kind_noncopyable; }
1001 // Using these query functons is preferable to direct comparison or matching
1002 // against the kind constants, as we may modify the kind hierarchy in the
1004 pure fn kind_can_be_copied(k: kind) -> bool {
1006 kind_sendable. { true }
1007 kind_copyable. { true }
1008 kind_noncopyable. { false }
1012 pure fn kind_can_be_sent(k: kind) -> bool {
1014 kind_sendable. { true }
1015 kind_copyable. { false }
1016 kind_noncopyable. { false }
1020 fn proto_kind(p: proto) -> kind {
1022 ast::proto_block. { kind_noncopyable }
1023 ast::proto_shared. { kind_copyable }
1024 ast::proto_send. { kind_sendable }
1025 ast::proto_bare. { kind_sendable }
1029 fn kind_lteq(a: kind, b: kind) -> bool {
1031 kind_noncopyable. { true }
1032 kind_copyable. { b != kind_noncopyable }
1033 kind_sendable. { b == kind_sendable }
1037 fn lower_kind(a: kind, b: kind) -> kind {
1038 if ty::kind_lteq(a, b) { a } else { b }
1041 fn type_kind(cx: ctxt, ty: t) -> kind {
1042 alt cx.kind_cache.find(ty) {
1043 some(result) { ret result; }
1044 none. {/* fall through */ }
1047 // Insert a default in case we loop back on self recursively.
1048 cx.kind_cache.insert(ty, kind_sendable);
1050 let result = alt struct(cx, ty) {
1051 // Scalar and unique types are sendable
1052 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_uint(_) | ty_float(_) |
1053 ty_native(_) | ty_ptr(_) |
1054 ty_send_type. | ty_str. | ty_native_fn(_, _) { kind_sendable }
1055 ty_type. { kind_copyable }
1056 // FIXME: obj is broken for now, since we aren't asserting
1057 // anything about its fields.
1058 ty_obj(_) { kind_copyable }
1059 ty_fn(f) { proto_kind(f.proto) }
1060 ty_opaque_closure_ptr(closure_block.) { kind_noncopyable }
1061 ty_opaque_closure_ptr(closure_shared.) { kind_copyable }
1062 ty_opaque_closure_ptr(closure_send.) { kind_sendable }
1063 // Those with refcounts-to-inner raise pinned to shared,
1064 // lower unique to shared. Therefore just set result to shared.
1065 ty_box(_) | ty_iface(_, _) { kind_copyable }
1066 // Boxes and unique pointers raise pinned to shared.
1067 ty_vec(tm) | ty_uniq(tm) { type_kind(cx, tm.ty) }
1068 // Records lower to the lowest of their members.
1070 let lowest = kind_sendable;
1071 for f in flds { lowest = lower_kind(lowest, type_kind(cx, f.mt.ty)); }
1074 // Tuples lower to the lowest of their members.
1076 let lowest = kind_sendable;
1077 for ty in tys { lowest = lower_kind(lowest, type_kind(cx, ty)); }
1080 // Tags lower to the lowest of their variants.
1082 let lowest = kind_sendable;
1083 for variant in *tag_variants(cx, did) {
1084 for aty in variant.args {
1085 // Perform any type parameter substitutions.
1086 let arg_ty = substitute_type_params(cx, tps, aty);
1087 lowest = lower_kind(lowest, type_kind(cx, arg_ty));
1088 if lowest == kind_noncopyable { break; }
1093 // Resources are always noncopyable.
1094 ty_res(did, inner, tps) { kind_noncopyable }
1096 param_bounds_to_kind(cx.ty_param_bounds.get(did.node))
1098 ty_constr(t, _) { type_kind(cx, t) }
1101 cx.kind_cache.insert(ty, result);
1105 // FIXME: should we just return true for native types in
1107 fn type_is_native(cx: ctxt, ty: t) -> bool {
1108 alt struct(cx, ty) { ty_native(_) { ret true; } _ { ret false; } }
1111 fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
1113 let sty = struct(cx, ty);
1114 if test(sty) { ret true; }
1117 for variant in *tag_variants(cx, did) {
1118 for aty in variant.args {
1119 let sty = substitute_type_params(cx, tps, aty);
1120 if type_structurally_contains(cx, sty, test) { ret true; }
1126 for field in fields {
1127 if type_structurally_contains(cx, field.mt.ty, test) { ret true; }
1133 if type_structurally_contains(cx, tt, test) { ret true; }
1137 ty_res(_, sub, tps) {
1138 let sty = substitute_type_params(cx, tps, sub);
1139 ret type_structurally_contains(cx, sty, test);
1145 pure fn type_has_dynamic_size(cx: ctxt, ty: t) -> bool unchecked {
1147 /* type_structurally_contains can't be declared pure
1148 because it takes a function argument. But it should be
1149 referentially transparent, since a given type's size should
1150 never change once it's created.
1151 (It would be interesting to think about how to make such properties
1152 actually checkable. It seems to me like a lot of properties
1153 that the type context tracks about types should be immutable.)
1155 type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1157 ty_param(_, _) { true }
1163 // Returns true for noncopyable types and types where a copy of a value can be
1164 // distinguished from the value itself. I.e. types with mutable content that's
1165 // not shared through a pointer.
1166 fn type_allows_implicit_copy(cx: ctxt, ty: t) -> bool {
1167 ret !type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1169 ty_param(_, _) { true }
1174 for field in fields {
1184 }) && type_kind(cx, ty) != kind_noncopyable;
1187 fn type_structurally_contains_uniques(cx: ctxt, ty: t) -> bool {
1188 ret type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1190 ty_uniq(_) { ret true; }
1198 fn type_is_integral(cx: ctxt, ty: t) -> bool {
1199 alt struct(cx, ty) {
1200 ty_int(_) | ty_uint(_) | ty_bool. { true }
1205 fn type_is_fp(cx: ctxt, ty: t) -> bool {
1206 alt struct(cx, ty) {
1207 ty_float(_) { true }
1212 fn type_is_numeric(cx: ctxt, ty: t) -> bool {
1213 ret type_is_integral(cx, ty) || type_is_fp(cx, ty);
1216 fn type_is_signed(cx: ctxt, ty: t) -> bool {
1217 alt struct(cx, ty) {
1223 // Whether a type is Plain Old Data -- meaning it does not contain pointers
1224 // that the cycle collector might care about.
1225 fn type_is_pod(cx: ctxt, ty: t) -> bool {
1227 alt struct(cx, ty) {
1229 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
1230 ty_send_type. | ty_type. | ty_native(_) | ty_ptr(_) { result = true; }
1232 ty_str. | ty_box(_) | ty_uniq(_) | ty_vec(_) | ty_fn(_) |
1233 ty_native_fn(_, _) | ty_obj(_) | ty_iface(_, _) { result = false; }
1236 let variants = tag_variants(cx, did);
1237 for variant: variant_info in *variants {
1238 let tup_ty = mk_tup(cx, variant.args);
1240 // Perform any type parameter substitutions.
1241 tup_ty = substitute_type_params(cx, tps, tup_ty);
1242 if !type_is_pod(cx, tup_ty) { result = false; }
1246 for f: field in flds {
1247 if !type_is_pod(cx, f.mt.ty) { result = false; }
1251 for elt in elts { if !type_is_pod(cx, elt) { result = false; } }
1253 ty_res(_, inner, tps) {
1254 result = type_is_pod(cx, substitute_type_params(cx, tps, inner));
1256 ty_constr(subt, _) { result = type_is_pod(cx, subt); }
1258 fail "ty_var in type_is_pod";
1260 ty_param(_, _) { result = false; }
1266 fn type_param(cx: ctxt, ty: t) -> option::t<uint> {
1267 alt struct(cx, ty) {
1268 ty_param(id, _) { ret some(id); }
1269 _ {/* fall through */ }
1274 // Returns a vec of all the type variables
1275 // occurring in t. It may contain duplicates.
1276 fn vars_in_type(cx: ctxt, ty: t) -> [int] {
1277 fn collect_var(cx: ctxt, vars: @mutable [int], ty: t) {
1278 alt struct(cx, ty) { ty_var(v) { *vars += [v]; } _ { } }
1280 let rslt: @mutable [int] = @mutable [];
1281 walk_ty(cx, bind collect_var(cx, rslt, _), ty);
1282 // Works because of a "convenient" bug that lets us
1283 // return a mutable vec as if it's immutable
1287 fn type_autoderef(cx: ctxt, t: ty::t) -> ty::t {
1290 alt struct(cx, t1) {
1291 ty_box(mt) | ty_uniq(mt) { t1 = mt.ty; }
1292 ty_res(_, inner, tps) {
1293 t1 = substitute_type_params(cx, tps, inner);
1296 let variants = tag_variants(cx, did);
1297 if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
1300 t1 = substitute_type_params(cx, tps, variants[0].args[0]);
1309 fn hash_type_structure(st: sty) -> uint {
1310 fn hash_uint(id: uint, n: uint) -> uint {
1315 fn hash_def(id: uint, did: ast::def_id) -> uint {
1317 h += (h << 5u) + (did.crate as uint);
1318 h += (h << 5u) + (did.node as uint);
1321 fn hash_subty(id: uint, subty: t) -> uint {
1323 h += (h << 5u) + subty;
1326 fn hash_subtys(id: uint, subtys: [t]) -> uint {
1328 vec::iter(subtys) { |subty|
1329 h = hash_subty(h, subty);
1333 fn hash_type_constr(id: uint, c: @type_constr) -> uint {
1335 h += (h << 5u) + hash_def(h, c.node.id);
1336 ret hash_type_constr_args(h, c.node.args);
1338 fn hash_type_constr_args(id: uint, args: [@ty_constr_arg]) -> uint {
1340 for a: @ty_constr_arg in args {
1342 carg_base. { h += h << 5u; }
1345 fail "lit args not implemented yet";
1348 // FIXME: Not sure what to do here.
1356 fn hash_fn(id: uint, args: [arg], rty: t) -> uint {
1358 for a: arg in args { h += (h << 5u) + a.ty; }
1359 h += (h << 5u) + rty;
1363 ty_nil. { 0u } ty_bool. { 1u }
1366 ast::ty_i. { 2u } ast::ty_char. { 3u } ast::ty_i8. { 4u }
1367 ast::ty_i16. { 5u } ast::ty_i32. { 6u } ast::ty_i64. { 7u }
1372 ast::ty_u. { 8u } ast::ty_u8. { 9u } ast::ty_u16. { 10u }
1373 ast::ty_u32. { 11u } ast::ty_u64. { 12u }
1377 alt t { ast::ty_f. { 13u } ast::ty_f32. { 14u } ast::ty_f64. { 15u } }
1379 ty_str. { ret 17u; }
1381 let h = hash_def(18u, did);
1382 for typ: t in tys { h += (h << 5u) + typ; }
1385 ty_box(mt) { ret hash_subty(19u, mt.ty); }
1386 ty_vec(mt) { ret hash_subty(21u, mt.ty); }
1389 for f: field in fields { h += (h << 5u) + f.mt.ty; }
1392 ty_tup(ts) { ret hash_subtys(25u, ts); }
1395 ty_fn(f) { ret hash_fn(27u, f.inputs, f.output); }
1396 ty_native_fn(args, rty) { ret hash_fn(28u, args, rty); }
1399 for m: method in methods { h += (h << 5u) + str::hash(m.ident); }
1402 ty_var(v) { ret hash_uint(30u, v as uint); }
1403 ty_param(pid, _) { ret hash_uint(31u, pid); }
1404 ty_type. { ret 32u; }
1405 ty_native(did) { ret hash_def(33u, did); }
1406 ty_bot. { ret 34u; }
1407 ty_ptr(mt) { ret hash_subty(35u, mt.ty); }
1408 ty_res(did, sub, tps) {
1409 let h = hash_subty(hash_def(18u, did), sub);
1410 ret hash_subtys(h, tps);
1413 let h = hash_subty(36u, t);
1414 for c: @type_constr in cs { h += (h << 5u) + hash_type_constr(h, c); }
1417 ty_uniq(mt) { ret hash_subty(37u, mt.ty); }
1418 ty_send_type. { ret 38u; }
1419 ty_named(t, name) { (str::hash(*name) << 5u) + hash_subty(39u, t) }
1420 ty_iface(did, tys) {
1421 let h = hash_def(40u, did);
1422 for typ: t in tys { h = hash_subty(h, typ); }
1425 ty_opaque_closure_ptr(closure_block.) { ret 41u; }
1426 ty_opaque_closure_ptr(closure_shared.) { ret 42u; }
1427 ty_opaque_closure_ptr(closure_send.) { ret 43u; }
1431 fn hash_raw_ty(&&rt: @raw_t) -> uint { ret rt.hash; }
1433 fn arg_eq<T>(eq: fn(T, T) -> bool, a: @sp_constr_arg<T>, b: @sp_constr_arg<T>)
1437 alt b.node { ast::carg_base. { ret true; } _ { ret false; } }
1439 ast::carg_ident(s) {
1440 alt b.node { ast::carg_ident(t) { ret eq(s, t); } _ { ret false; } }
1444 ast::carg_lit(m) { ret ast_util::lit_eq(l, m); } _ { ret false; }
1450 fn args_eq<T>(eq: fn(T, T) -> bool, a: [@sp_constr_arg<T>],
1451 b: [@sp_constr_arg<T>]) -> bool {
1453 for arg: @sp_constr_arg<T> in a {
1454 if !arg_eq(eq, arg, b[i]) { ret false; }
1460 fn constr_eq(c: @constr, d: @constr) -> bool {
1461 fn eq_int(&&x: uint, &&y: uint) -> bool { ret x == y; }
1462 ret path_to_str(c.node.path) == path_to_str(d.node.path) &&
1464 args_eq(eq_int, c.node.args, d.node.args);
1467 fn constrs_eq(cs: [@constr], ds: [@constr]) -> bool {
1468 if vec::len(cs) != vec::len(ds) { ret false; }
1470 for c: @constr in cs { if !constr_eq(c, ds[i]) { ret false; } i += 1u; }
1475 fn node_id_to_ty_param_substs_opt_and_ty(cx: ctxt, id: ast::node_id) ->
1476 ty_param_substs_opt_and_ty {
1477 // Pull out the node type table.
1478 alt smallintmap::find(*cx.node_types, id as uint) {
1480 cx.sess.bug("node_id_to_ty_param_substs_opt_and_ty() called on " +
1481 "an untyped node (" + int::to_str(id, 10u) +
1484 some(tpot) { ret tpot; }
1488 fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
1489 ret node_id_to_ty_param_substs_opt_and_ty(cx, id).ty;
1492 fn node_id_to_type_params(cx: ctxt, id: ast::node_id) -> [t] {
1493 alt node_id_to_ty_param_substs_opt_and_ty(cx, id).substs {
1495 some(tps) { ret tps; }
1499 fn node_id_has_type_params(cx: ctxt, id: ast::node_id) -> bool {
1500 ret vec::len(node_id_to_type_params(cx, id)) > 0u;
1504 // Returns a type with type parameter substitutions performed if applicable.
1505 fn ty_param_substs_opt_and_ty_to_monotype(cx: ctxt,
1506 tpot: ty_param_substs_opt_and_ty) ->
1509 none. { ret tpot.ty; }
1510 some(tps) { ret substitute_type_params(cx, tps, tpot.ty); }
1515 // Returns the type of an annotation, with type parameter substitutions
1516 // performed if applicable.
1517 fn node_id_to_monotype(cx: ctxt, id: ast::node_id) -> t {
1518 let tpot = node_id_to_ty_param_substs_opt_and_ty(cx, id);
1519 ret ty_param_substs_opt_and_ty_to_monotype(cx, tpot);
1523 // Returns the number of distinct type parameters in the given type.
1524 fn count_ty_params(cx: ctxt, ty: t) -> uint {
1525 fn counter(cx: ctxt, param_indices: @mutable [uint], ty: t) {
1526 alt struct(cx, ty) {
1527 ty_param(param_idx, _) {
1529 for other_param_idx: uint in *param_indices {
1530 if param_idx == other_param_idx { seen = true; }
1532 if !seen { *param_indices += [param_idx]; }
1534 _ {/* fall through */ }
1537 let param_indices: @mutable [uint] = @mutable [];
1538 let f = bind counter(cx, param_indices, _);
1540 ret vec::len::<uint>(*param_indices);
1543 fn type_contains_vars(cx: ctxt, typ: t) -> bool {
1544 ret interner::get(*cx.ts, typ).has_vars;
1547 fn type_contains_params(cx: ctxt, typ: t) -> bool {
1548 ret interner::get(*cx.ts, typ).has_params;
1552 // Type accessors for substructures of types
1553 fn ty_fn_args(cx: ctxt, fty: t) -> [arg] {
1554 alt struct(cx, fty) {
1555 ty::ty_fn(f) { ret f.inputs; }
1556 ty::ty_native_fn(a, _) { ret a; }
1557 _ { cx.sess.bug("ty_fn_args() called on non-fn type"); }
1561 fn ty_fn_proto(cx: ctxt, fty: t) -> ast::proto {
1562 alt struct(cx, fty) {
1563 ty::ty_fn(f) { ret f.proto; }
1564 ty::ty_native_fn(_, _) {
1565 // FIXME: This should probably be proto_bare
1566 ret ast::proto_shared;
1568 _ { cx.sess.bug("ty_fn_proto() called on non-fn type"); }
1572 pure fn ty_fn_ret(cx: ctxt, fty: t) -> t {
1573 let sty = struct(cx, fty);
1575 ty::ty_fn(f) { ret f.output; }
1576 ty::ty_native_fn(_, r) { ret r; }
1578 // Unchecked is ok since we diverge here
1579 // (might want to change the typechecker to allow
1580 // it without an unchecked)
1581 // Or, it wouldn't be necessary if we had the right
1582 // typestate constraint on cx and t (then we could
1583 // call unreachable() instead)
1584 unchecked { cx.sess.bug("ty_fn_ret() called on non-fn type"); }}
1588 fn ty_fn_ret_style(cx: ctxt, fty: t) -> ast::ret_style {
1589 alt struct(cx, fty) {
1590 ty::ty_fn(f) { f.ret_style }
1591 ty::ty_native_fn(_, _) { ast::return_val }
1592 _ { cx.sess.bug("ty_fn_ret_style() called on non-fn type"); }
1596 fn is_fn_ty(cx: ctxt, fty: t) -> bool {
1597 alt struct(cx, fty) {
1598 ty::ty_fn(_) { ret true; }
1599 ty::ty_native_fn(_, _) { ret true; }
1604 // Just checks whether it's a fn that returns bool,
1606 fn is_pred_ty(cx: ctxt, fty: t) -> bool {
1607 is_fn_ty(cx, fty) && type_is_bool(cx, ty_fn_ret(cx, fty))
1610 fn ty_var_id(cx: ctxt, typ: t) -> int {
1611 alt struct(cx, typ) {
1612 ty::ty_var(vid) { ret vid; }
1613 _ { #error("ty_var_id called on non-var ty"); fail; }
1618 // Type accessors for AST nodes
1619 fn block_ty(cx: ctxt, b: ast::blk) -> t {
1620 ret node_id_to_type(cx, b.node.id);
1624 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
1625 // doesn't provide type parameter substitutions.
1626 fn pat_ty(cx: ctxt, pat: @ast::pat) -> t {
1627 ret node_id_to_monotype(cx, pat.id);
1631 // Returns the type of an expression as a monotype.
1633 // NB: This type doesn't provide type parameter substitutions; e.g. if you
1634 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
1635 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
1636 // expr_ty_params_and_ty() below.
1637 fn expr_ty(cx: ctxt, expr: @ast::expr) -> t {
1638 ret node_id_to_monotype(cx, expr.id);
1641 fn expr_ty_params_and_ty(cx: ctxt, expr: @ast::expr) -> {params: [t], ty: t} {
1642 ret {params: node_id_to_type_params(cx, expr.id),
1643 ty: node_id_to_type(cx, expr.id)};
1646 fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
1647 ret node_id_has_type_params(cx, expr.id);
1650 fn expr_is_lval(method_map: typeck::method_map, tcx: ty::ctxt,
1651 e: @ast::expr) -> bool {
1653 ast::expr_path(_) | ast::expr_index(_, _) |
1654 ast::expr_unary(ast::deref., _) { true }
1655 ast::expr_field(base, ident, _) {
1656 method_map.contains_key(e.id) ? false : {
1657 let basety = type_autoderef(tcx, expr_ty(tcx, base));
1658 alt struct(tcx, basety) {
1668 fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
1670 ast::stmt_decl(_, id) | stmt_expr(_, id) | stmt_semi(_, id) {
1676 fn field_idx(id: ast::ident, fields: [field]) -> option::t<uint> {
1678 for f in fields { if f.ident == id { ret some(i); } i += 1u; }
1682 fn get_field(tcx: ctxt, rec_ty: t, id: ast::ident) -> field {
1683 alt struct(tcx, rec_ty) {
1685 alt vec::find(fields, {|f| str::eq(f.ident, id) }) {
1692 fn method_idx(id: ast::ident, meths: [method]) -> option::t<uint> {
1694 for m in meths { if m.ident == id { ret some(i); } i += 1u; }
1698 fn sort_methods(meths: [method]) -> [method] {
1699 fn method_lteq(a: method, b: method) -> bool {
1700 ret str::lteq(a.ident, b.ident);
1702 ret std::sort::merge_sort(bind method_lteq(_, _), meths);
1705 fn occurs_check_fails(tcx: ctxt, sp: option::t<span>, vid: int, rt: t) ->
1707 if !type_contains_vars(tcx, rt) {
1713 if vec::member(vid, vars_in_type(tcx, rt)) {
1716 // Maybe this should be span_err -- however, there's an
1717 // assertion later on that the type doesn't contain
1718 // variables, so in this case we have to be sure to die.
1720 (s, "Type inference failed because I \
1721 could not find a type\n that's both of the form "
1722 + ty_to_str(tcx, ty::mk_var(tcx, vid)) +
1723 " and of the form " + ty_to_str(tcx, rt) +
1724 ". Such a type would have to be infinitely large.");
1728 } else { ret false; }
1731 // Type unification via Robinson's algorithm (Robinson 1965). Implemented as
1732 // described in Hoder and Voronkov:
1734 // http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
1737 export fixup_result;
1741 export mk_var_bindings;
1742 export resolve_type_structure;
1743 export resolve_type_var;
1748 export var_bindings;
1749 export precise, in_bindings;
1751 tag result { ures_ok(t); ures_err(type_err); }
1752 tag union_result { unres_ok; unres_err(type_err); }
1754 fix_ok(t); // fixup succeeded
1755 fix_err(int); // fixup failed because a type variable was unresolved
1758 {sets: ufind::ufind, types: smallintmap::smallintmap<t>};
1762 in_bindings(@var_bindings);
1764 type ctxt = {st: unify_style, tcx: ty_ctxt};
1766 fn mk_var_bindings() -> @var_bindings {
1767 ret @{sets: ufind::make(), types: smallintmap::mk::<t>()};
1770 // Unifies two sets.
1771 fn union(cx: @ctxt, set_a: uint, set_b: uint,
1772 variance: variance) -> union_result {
1773 let vb = alt cx.st {
1774 in_bindings(vb) { vb }
1776 ufind::grow(vb.sets, math::max(set_a, set_b) + 1u);
1777 let root_a = ufind::find(vb.sets, set_a);
1778 let root_b = ufind::find(vb.sets, set_b);
1781 bind fn (vb: @var_bindings, t: t, set_a: uint, set_b: uint) {
1782 ufind::union(vb.sets, set_a, set_b);
1783 let root_c: uint = ufind::find(vb.sets, set_a);
1784 smallintmap::insert::<t>(vb.types, root_c, t);
1785 }(_, _, set_a, set_b);
1788 alt smallintmap::find(vb.types, root_a) {
1790 alt smallintmap::find(vb.types, root_b) {
1791 none. { ufind::union(vb.sets, set_a, set_b); ret unres_ok; }
1792 some(t_b) { replace_type(vb, t_b); ret unres_ok; }
1796 alt smallintmap::find(vb.types, root_b) {
1797 none. { replace_type(vb, t_a); ret unres_ok; }
1799 alt unify_step(cx, t_a, t_b, variance) {
1800 ures_ok(t_c) { replace_type(vb, t_c); ret unres_ok; }
1801 ures_err(terr) { ret unres_err(terr); }
1809 fn record_var_binding_for_expected(
1810 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1812 cx, key, typ, variance_transform(variance, covariant))
1815 fn record_var_binding_for_actual(
1816 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1817 // Unifying in 'the other direction' so flip the variance
1819 cx, key, typ, variance_transform(variance, contravariant))
1822 fn record_var_binding(
1823 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1825 let vb = alt cx.st { in_bindings(vb) { vb } };
1826 ufind::grow(vb.sets, (key as uint) + 1u);
1827 let root = ufind::find(vb.sets, key as uint);
1828 let result_type = typ;
1829 alt smallintmap::find(vb.types, root) {
1831 alt unify_step(cx, old_type, typ, variance) {
1832 ures_ok(unified_type) { result_type = unified_type; }
1836 none. {/* fall through */ }
1838 smallintmap::insert::<t>(vb.types, root, result_type);
1842 // Simple structural type comparison.
1843 fn struct_cmp(cx: @ctxt, expected: t, actual: t) -> result {
1845 let cfg = tcx.sess.get_targ_cfg();
1846 if mach_struct(tcx, cfg, expected) == mach_struct(tcx, cfg, actual) {
1847 ret ures_ok(expected);
1849 ret ures_err(terr_mismatch);
1852 // Right now this just checks that the lists of constraints are
1854 fn unify_constrs(base_t: t, expected: [@type_constr],
1855 actual: [@type_constr]) -> result {
1856 let expected_len = vec::len(expected);
1857 let actual_len = vec::len(actual);
1859 if expected_len != actual_len {
1860 ret ures_err(terr_constr_len(expected_len, actual_len));
1864 for c: @type_constr in expected {
1865 rslt = unify_constr(base_t, c, actual[i]);
1866 alt rslt { ures_ok(_) { } ures_err(_) { ret rslt; } }
1869 ret ures_ok(base_t);
1871 fn unify_constr(base_t: t, expected: @type_constr,
1872 actual_constr: @type_constr) -> result {
1873 let ok_res = ures_ok(base_t);
1874 let err_res = ures_err(terr_constr_mismatch(expected, actual_constr));
1875 if expected.node.id != actual_constr.node.id { ret err_res; }
1876 let expected_arg_len = vec::len(expected.node.args);
1877 let actual_arg_len = vec::len(actual_constr.node.args);
1878 if expected_arg_len != actual_arg_len { ret err_res; }
1881 for a: @ty_constr_arg in expected.node.args {
1882 actual = actual_constr.node.args[i];
1885 alt actual.node { carg_base. { } _ { ret err_res; } }
1889 carg_lit(m) { if l != m { ret err_res; } }
1895 carg_ident(q) { if p.node != q.node { ret err_res; } }
1905 // Unifies two mutability flags.
1906 fn unify_mut(expected: ast::mutability, actual: ast::mutability,
1907 variance: variance) ->
1908 option::t<(ast::mutability, variance)> {
1910 // If you're unifying on something mutable then we have to
1911 // be invariant on the inner type
1912 let newvariance = alt expected {
1914 variance_transform(variance, invariant)
1917 variance_transform(variance, covariant)
1921 if expected == actual { ret some((expected, newvariance)); }
1922 if variance == covariant {
1923 if expected == ast::maybe_mut {
1924 ret some((actual, newvariance));
1926 } else if variance == contravariant {
1927 if actual == ast::maybe_mut {
1928 ret some((expected, newvariance));
1933 fn unify_fn_proto(e_proto: ast::proto, a_proto: ast::proto,
1934 variance: variance) -> option::t<result> {
1935 // Prototypes form a diamond-shaped partial order:
1943 // where "^" means "subtype of" (forgive the abuse of the term
1945 fn sub_proto(p_sub: ast::proto, p_sup: ast::proto) -> bool {
1946 ret alt (p_sub, p_sup) {
1947 (_, ast::proto_block.) { true }
1948 (ast::proto_bare., _) { true }
1950 // Equal prototypes are always subprotos:
1951 (_, _) { p_sub == p_sup }
1956 invariant. when e_proto == a_proto { none }
1957 covariant. when sub_proto(a_proto, e_proto) { none }
1958 contravariant. when sub_proto(e_proto, a_proto) { none }
1959 _ { some(ures_err(terr_mismatch)) }
1962 fn unify_args(cx: @ctxt, e_args: [arg], a_args: [arg], variance: variance)
1963 -> either::t<result, [arg]> {
1964 if !vec::same_length(e_args, a_args) {
1965 ret either::left(ures_err(terr_arg_count));
1967 // The variance changes (flips basically) when descending
1968 // into arguments of function types
1969 let variance = variance_transform(variance, contravariant);
1970 // Would use vec::map2(), but for the need to return in case of
1972 let i = 0u, result = [];
1973 for expected_input in e_args {
1974 let actual_input = a_args[i];
1976 // Unify the result modes.
1977 let result_mode = if expected_input.mode == ast::mode_infer {
1979 } else if actual_input.mode == ast::mode_infer {
1981 } else if expected_input.mode != actual_input.mode {
1982 ret either::left(ures_err(terr_mode_mismatch(
1983 expected_input.mode, actual_input.mode)));
1984 } else { expected_input.mode };
1986 alt unify_step(cx, expected_input.ty, actual_input.ty,
1988 ures_ok(rty) { result += [{mode: result_mode, ty: rty}]; }
1989 err { ret either::left(err); }
1992 either::right(result)
1994 fn unify_fn(cx: @ctxt, e_f: fn_ty, a_f: fn_ty, variance: variance)
1996 alt unify_fn_proto(e_f.proto, a_f.proto, variance) {
1997 some(err) { ret err; }
1998 none. { /* fall through */ }
2001 if a_f.ret_style != ast::noreturn && a_f.ret_style != e_f.ret_style {
2002 /* even though typestate checking is mostly
2003 responsible for checking control flow annotations,
2004 this check is necessary to ensure that the
2005 annotation in an object method matches the
2006 declared object type */
2007 ret ures_err(terr_ret_style_mismatch(e_f.ret_style,
2010 let result_ins = alt unify_args(cx, e_f.inputs, a_f.inputs,
2012 either::left(err) { ret err; }
2013 either::right(ts) { ts }
2016 // Check the output.
2017 alt unify_step(cx, e_f.output, a_f.output, variance) {
2019 ures_ok(mk_fn(cx.tcx, {proto: e_f.proto,
2027 fn unify_native_fn(cx: @ctxt, expected_inputs: [arg], expected_output: t,
2028 actual_inputs: [arg], actual_output: t,
2029 variance: variance) -> result {
2030 let result_ins = alt unify_args(cx, expected_inputs,
2031 actual_inputs, variance) {
2032 either::left(err) { ret err; }
2033 either::right(ts) { ts }
2035 alt unify_step(cx, expected_output, actual_output, variance) {
2036 ures_ok(out) { ures_ok(mk_native_fn(cx.tcx, result_ins, out)) }
2040 fn unify_obj(cx: @ctxt, expected_meths: [method],
2041 actual_meths: [method], variance: variance) -> result {
2042 let result_meths: [method] = [];
2044 let expected_len: uint = vec::len(expected_meths);
2045 let actual_len: uint = vec::len(actual_meths);
2046 if expected_len != actual_len { ret ures_err(terr_meth_count); }
2047 while i < expected_len {
2048 let e_meth = expected_meths[i];
2049 let a_meth = actual_meths[i];
2050 if !str::eq(e_meth.ident, a_meth.ident) {
2051 ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident));
2053 alt unify_fn(cx, e_meth.fty, a_meth.fty, variance) {
2055 alt struct(cx.tcx, tfn) {
2057 result_meths += [{ident: e_meth.ident,
2058 tps: a_meth.tps, fty: f}];
2066 let t = mk_obj(cx.tcx, result_meths);
2070 // If the given type is a variable, returns the structure of that type.
2071 fn resolve_type_structure(tcx: ty_ctxt, vb: @var_bindings, typ: t) ->
2073 alt struct(tcx, typ) {
2075 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2076 let root_id = ufind::find(vb.sets, vid as uint);
2077 alt smallintmap::find::<t>(vb.types, root_id) {
2078 none. { ret fix_err(vid); }
2079 some(rt) { ret fix_ok(rt); }
2082 _ { ret fix_ok(typ); }
2086 // Specifies the allowable subtyping between expected and actual types
2088 // Actual may be a subtype of expected
2090 // Actual may be a supertype of expected
2092 // Actual must be the same type as expected
2096 // The calculation for recursive variance
2097 // "Taming the Wildcards: Combining Definition- and Use-Site Variance"
2098 // by John Altidor, et. al.
2100 // I'm just copying the table from figure 1 - haven't actually
2101 // read the paper (yet).
2102 fn variance_transform(a: variance, b: variance) -> variance {
2106 covariant. { covariant }
2107 contravariant. { contravariant }
2108 invariant. { invariant }
2113 covariant. { contravariant }
2114 contravariant. { covariant }
2115 invariant. { invariant }
2120 covariant. { invariant }
2121 contravariant. { invariant }
2122 invariant. { invariant }
2128 fn unify_tps(cx: @ctxt, expected_tps: [t], actual_tps: [t],
2129 variance: variance, finish: block([t]) -> result) -> result {
2130 let result_tps = [], i = 0u;
2131 for exp in expected_tps {
2132 let act = actual_tps[i];
2134 let result = unify_step(cx, exp, act, variance);
2136 ures_ok(rty) { result_tps += [rty]; }
2142 fn unify_step(cx: @ctxt, expected: t, actual: t,
2143 variance: variance) -> result {
2144 // FIXME: rewrite this using tuple pattern matching when available, to
2145 // avoid all this rightward drift and spikiness.
2146 // NOTE: we have tuple matching now, but that involves copying the
2147 // matched elements into a tuple first, which is expensive, since sty
2148 // holds vectors, which are currently unique
2151 if expected == actual { ret ures_ok(expected); }
2153 // Stage 1: Handle the cases in which one side or another is a type
2156 alt struct(cx.tcx, actual) {
2157 // If the RHS is a variable type, then just do the
2158 // appropriate binding.
2159 ty::ty_var(actual_id) {
2160 let actual_n = actual_id as uint;
2161 alt struct(cx.tcx, expected) {
2162 ty::ty_var(expected_id) {
2163 let expected_n = expected_id as uint;
2164 alt union(cx, expected_n, actual_n, variance) {
2165 unres_ok. {/* fall through */ }
2166 unres_err(t_e) { ret ures_err(t_e); }
2170 // Just bind the type variable to the expected type.
2171 alt record_var_binding_for_actual(
2172 cx, actual_id, expected, variance) {
2173 ures_ok(_) {/* fall through */ }
2178 ret ures_ok(mk_var(cx.tcx, actual_id));
2182 alt struct(cx.tcx, expected) {
2183 ty::ty_var(expected_id) {
2184 // Add a binding. (`actual` can't actually be a var here.)
2185 alt record_var_binding_for_expected(
2186 cx, expected_id, actual,
2188 ures_ok(_) {/* fall through */ }
2191 ret ures_ok(mk_var(cx.tcx, expected_id));
2193 _ {/* fall through */ }
2195 // Stage 2: Handle all other cases.
2197 alt struct(cx.tcx, actual) {
2198 ty::ty_bot. { ret ures_ok(expected); }
2199 _ {/* fall through */ }
2201 alt struct(cx.tcx, expected) {
2202 ty::ty_nil. { ret struct_cmp(cx, expected, actual); }
2203 // _|_ unifies with anything
2205 ret ures_ok(actual);
2207 ty::ty_bool. | ty::ty_int(_) | ty_uint(_) | ty_float(_) |
2208 ty::ty_str. | ty::ty_type. | ty::ty_send_type. {
2209 ret struct_cmp(cx, expected, actual);
2211 ty::ty_native(ex_id) {
2212 alt struct(cx.tcx, actual) {
2214 if ex_id.crate == act_id.crate && ex_id.node == act_id.node {
2215 ret ures_ok(actual);
2216 } else { ret ures_err(terr_mismatch); }
2218 _ { ret ures_err(terr_mismatch); }
2221 ty::ty_param(expected_n, _) {
2222 alt struct(cx.tcx, actual) {
2223 ty::ty_param(actual_n, _) when expected_n == actual_n {
2224 ret ures_ok(expected);
2226 _ { ret ures_err(terr_mismatch); }
2229 ty::ty_tag(expected_id, expected_tps) {
2230 alt struct(cx.tcx, actual) {
2231 ty::ty_tag(actual_id, actual_tps) {
2232 if expected_id != actual_id {
2233 ret ures_err(terr_mismatch);
2235 ret unify_tps(cx, expected_tps, actual_tps, variance, {|tps|
2236 ures_ok(mk_tag(cx.tcx, expected_id, tps))
2239 _ {/* fall through */ }
2241 ret ures_err(terr_mismatch);
2243 ty_iface(expected_id, expected_tps) {
2244 alt struct(cx.tcx, actual) {
2245 ty::ty_iface(actual_id, actual_tps) {
2246 if expected_id != actual_id {
2247 ret ures_err(terr_mismatch);
2249 ret unify_tps(cx, expected_tps, actual_tps, variance, {|tps|
2250 ures_ok(mk_iface(cx.tcx, expected_id, tps))
2255 ret ures_err(terr_mismatch);
2257 ty::ty_box(expected_mt) {
2258 alt struct(cx.tcx, actual) {
2259 ty::ty_box(actual_mt) {
2260 let (mut, var) = alt unify_mut(
2261 expected_mt.mut, actual_mt.mut, variance) {
2262 none. { ret ures_err(terr_box_mutability); }
2265 let result = unify_step(
2266 cx, expected_mt.ty, actual_mt.ty, var);
2268 ures_ok(result_sub) {
2269 let mt = {ty: result_sub, mut: mut};
2270 ret ures_ok(mk_box(cx.tcx, mt));
2275 _ { ret ures_err(terr_mismatch); }
2278 ty::ty_uniq(expected_mt) {
2279 alt struct(cx.tcx, actual) {
2280 ty::ty_uniq(actual_mt) {
2281 let (mut, var) = alt unify_mut(
2282 expected_mt.mut, actual_mt.mut, variance) {
2283 none. { ret ures_err(terr_box_mutability); }
2286 let result = unify_step(
2287 cx, expected_mt.ty, actual_mt.ty, var);
2289 ures_ok(result_mt) {
2290 let mt = {ty: result_mt, mut: mut};
2291 ret ures_ok(mk_uniq(cx.tcx, mt));
2296 _ { ret ures_err(terr_mismatch); }
2299 ty::ty_vec(expected_mt) {
2300 alt struct(cx.tcx, actual) {
2301 ty::ty_vec(actual_mt) {
2302 let (mut, var) = alt unify_mut(
2303 expected_mt.mut, actual_mt.mut, variance) {
2304 none. { ret ures_err(terr_vec_mutability); }
2307 let result = unify_step(
2308 cx, expected_mt.ty, actual_mt.ty, var);
2310 ures_ok(result_sub) {
2311 let mt = {ty: result_sub, mut: mut};
2312 ret ures_ok(mk_vec(cx.tcx, mt));
2317 _ { ret ures_err(terr_mismatch); }
2320 ty::ty_ptr(expected_mt) {
2321 alt struct(cx.tcx, actual) {
2322 ty::ty_ptr(actual_mt) {
2323 let (mut, var) = alt unify_mut(
2324 expected_mt.mut, actual_mt.mut, variance) {
2325 none. { ret ures_err(terr_vec_mutability); }
2328 let result = unify_step(
2329 cx, expected_mt.ty, actual_mt.ty, var);
2331 ures_ok(result_sub) {
2332 let mt = {ty: result_sub, mut: mut};
2333 ret ures_ok(mk_ptr(cx.tcx, mt));
2338 _ { ret ures_err(terr_mismatch); }
2341 ty::ty_res(ex_id, ex_inner, ex_tps) {
2342 alt struct(cx.tcx, actual) {
2343 ty::ty_res(act_id, act_inner, act_tps) {
2344 if ex_id.crate != act_id.crate || ex_id.node != act_id.node {
2345 ret ures_err(terr_mismatch);
2347 let result = unify_step(
2348 cx, ex_inner, act_inner, variance);
2350 ures_ok(res_inner) {
2353 for ex_tp: t in ex_tps {
2354 let result = unify_step(
2355 cx, ex_tp, act_tps[i], variance);
2357 ures_ok(rty) { res_tps += [rty]; }
2362 ret ures_ok(mk_res(cx.tcx, act_id, res_inner, res_tps));
2367 _ { ret ures_err(terr_mismatch); }
2370 ty::ty_rec(expected_fields) {
2371 alt struct(cx.tcx, actual) {
2372 ty::ty_rec(actual_fields) {
2373 let expected_len = vec::len::<field>(expected_fields);
2374 let actual_len = vec::len::<field>(actual_fields);
2375 if expected_len != actual_len {
2376 let err = terr_record_size(expected_len, actual_len);
2379 // TODO: implement an iterator that can iterate over
2380 // two arrays simultaneously.
2382 let result_fields: [field] = [];
2384 while i < expected_len {
2385 let expected_field = expected_fields[i];
2386 let actual_field = actual_fields[i];
2387 let (mut, var) = alt unify_mut(
2388 expected_field.mt.mut, actual_field.mt.mut, variance)
2390 none. { ret ures_err(terr_record_mutability); }
2393 if !str::eq(expected_field.ident, actual_field.ident) {
2395 terr_record_fields(expected_field.ident,
2396 actual_field.ident);
2400 unify_step(cx, expected_field.mt.ty,
2401 actual_field.mt.ty, var);
2404 let mt = {ty: rty, mut: mut};
2405 result_fields += [{mt: mt with expected_field}];
2411 ret ures_ok(mk_rec(cx.tcx, result_fields));
2413 _ { ret ures_err(terr_mismatch); }
2416 ty::ty_tup(expected_elems) {
2417 alt struct(cx.tcx, actual) {
2418 ty::ty_tup(actual_elems) {
2419 let expected_len = vec::len(expected_elems);
2420 let actual_len = vec::len(actual_elems);
2421 if expected_len != actual_len {
2422 let err = terr_tuple_size(expected_len, actual_len);
2425 // TODO: implement an iterator that can iterate over
2426 // two arrays simultaneously.
2428 let result_elems = [];
2430 while i < expected_len {
2431 let expected_elem = expected_elems[i];
2432 let actual_elem = actual_elems[i];
2433 let result = unify_step(
2434 cx, expected_elem, actual_elem, variance);
2436 ures_ok(rty) { result_elems += [rty]; }
2441 ret ures_ok(mk_tup(cx.tcx, result_elems));
2443 _ { ret ures_err(terr_mismatch); }
2446 ty::ty_fn(expected_f) {
2447 alt struct(cx.tcx, actual) {
2448 ty::ty_fn(actual_f) {
2449 ret unify_fn(cx, expected_f, actual_f, variance);
2451 _ { ret ures_err(terr_mismatch); }
2454 ty::ty_native_fn(expected_inputs, expected_output) {
2455 alt struct(cx.tcx, actual) {
2456 ty::ty_native_fn(actual_inputs, actual_output) {
2457 ret unify_native_fn(cx, expected_inputs, expected_output,
2458 actual_inputs, actual_output, variance);
2460 _ { ret ures_err(terr_mismatch); }
2463 ty::ty_obj(expected_meths) {
2464 alt struct(cx.tcx, actual) {
2465 ty::ty_obj(actual_meths) {
2466 ret unify_obj(cx, expected_meths, actual_meths, variance);
2468 _ { ret ures_err(terr_mismatch); }
2471 ty::ty_constr(expected_t, expected_constrs) {
2473 // unify the base types...
2474 alt struct(cx.tcx, actual) {
2475 ty::ty_constr(actual_t, actual_constrs) {
2476 let rslt = unify_step(
2477 cx, expected_t, actual_t, variance);
2480 // FIXME: probably too restrictive --
2481 // requires the constraints to be
2482 // syntactically equal
2483 ret unify_constrs(expected, expected_constrs,
2490 // If the actual type is *not* a constrained type,
2491 // then we go ahead and just ignore the constraints on
2492 // the expected type. typestate handles the rest.
2494 cx, expected_t, actual, variance);
2500 fn unify(expected: t, actual: t, st: unify_style,
2501 tcx: ty_ctxt) -> result {
2502 let cx = @{st: st, tcx: tcx};
2503 ret unify_step(cx, expected, actual, covariant);
2505 fn dump_var_bindings(tcx: ty_ctxt, vb: @var_bindings) {
2507 while i < vec::len::<ufind::node>(vb.sets.nodes) {
2510 while j < vec::len::<option::t<uint>>(vb.sets.nodes) {
2511 if ufind::find(vb.sets, j) == i { sets += #fmt[" %u", j]; }
2515 alt smallintmap::find::<t>(vb.types, i) {
2516 none. { typespec = ""; }
2517 some(typ) { typespec = " =" + ty_to_str(tcx, typ); }
2519 #error("set %u:%s%s", i, typespec, sets);
2524 // Fixups and substitutions
2525 // Takes an optional span - complain about occurs check violations
2526 // iff the span is present (so that if we already know we're going
2527 // to error anyway, we don't complain)
2528 fn fixup_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2529 typ: t) -> fixup_result {
2530 fn subst_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2531 unresolved: @mutable option::t<int>, vid: int) -> t {
2532 // Should really return a fixup_result instead of a t, but fold_ty
2533 // doesn't allow returning anything but a t.
2534 if vid as uint >= ufind::set_count(vb.sets) {
2535 *unresolved = some(vid);
2536 ret ty::mk_var(tcx, vid);
2538 let root_id = ufind::find(vb.sets, vid as uint);
2539 alt smallintmap::find::<t>(vb.types, root_id) {
2540 none. { *unresolved = some(vid); ret ty::mk_var(tcx, vid); }
2542 if occurs_check_fails(tcx, sp, vid, rt) {
2543 // Return the type unchanged, so we can error out
2548 fm_var(bind subst_vars(tcx, sp, vb, unresolved,
2553 let unresolved = @mutable none::<int>;
2555 fold_ty(tcx, fm_var(bind subst_vars(tcx, sp, vb, unresolved, _)),
2557 let ur = *unresolved;
2559 none. { ret fix_ok(rty); }
2560 some(var_id) { ret fix_err(var_id); }
2563 fn resolve_type_var(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2564 vid: int) -> fixup_result {
2565 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2566 let root_id = ufind::find(vb.sets, vid as uint);
2567 alt smallintmap::find::<t>(vb.types, root_id) {
2568 none. { ret fix_err(vid); }
2569 some(rt) { ret fixup_vars(tcx, sp, vb, rt); }
2574 fn same_type(cx: ctxt, a: t, b: t) -> bool {
2575 alt unify::unify(a, b, unify::precise, cx) {
2576 unify::ures_ok(_) { true }
2580 fn same_method(cx: ctxt, a: method, b: method) -> bool {
2581 a.tps == b.tps && a.fty.proto == b.fty.proto && a.ident == b.ident &&
2582 vec::all2(a.fty.inputs, b.fty.inputs,
2583 {|a, b| a.mode == b.mode && same_type(cx, a.ty, b.ty) }) &&
2584 same_type(cx, a.fty.output, b.fty.output) &&
2585 a.fty.ret_style == b.fty.ret_style
2588 fn type_err_to_str(err: ty::type_err) -> str {
2590 terr_mismatch. { ret "types differ"; }
2591 terr_ret_style_mismatch(expect, actual) {
2592 fn to_str(s: ast::ret_style) -> str {
2594 ast::noreturn. { "non-returning" }
2595 ast::return_val. { "return-by-value" }
2598 ret to_str(actual) + " function found where " + to_str(expect) +
2599 " function was expected";
2601 terr_box_mutability. { ret "boxed values differ in mutability"; }
2602 terr_vec_mutability. { ret "vectors differ in mutability"; }
2603 terr_tuple_size(e_sz, a_sz) {
2604 ret "expected a tuple with " + uint::to_str(e_sz, 10u) +
2605 " elements but found one with " + uint::to_str(a_sz, 10u) +
2608 terr_record_size(e_sz, a_sz) {
2609 ret "expected a record with " + uint::to_str(e_sz, 10u) +
2610 " fields but found one with " + uint::to_str(a_sz, 10u) +
2613 terr_record_mutability. { ret "record elements differ in mutability"; }
2614 terr_record_fields(e_fld, a_fld) {
2615 ret "expected a record with field '" + e_fld +
2616 "' but found one with field '" + a_fld + "'";
2618 terr_arg_count. { ret "incorrect number of function parameters"; }
2619 terr_meth_count. { ret "incorrect number of object methods"; }
2620 terr_obj_meths(e_meth, a_meth) {
2621 ret "expected an obj with method '" + e_meth +
2622 "' but found one with method '" + a_meth + "'";
2624 terr_mode_mismatch(e_mode, a_mode) {
2625 ret "expected argument mode " + mode_str(e_mode) + " but found " +
2628 terr_constr_len(e_len, a_len) {
2629 ret "Expected a type with " + uint::str(e_len) +
2630 " constraints, but found one with " + uint::str(a_len) +
2633 terr_constr_mismatch(e_constr, a_constr) {
2634 ret "Expected a type with constraint " + ty_constr_to_str(e_constr) +
2635 " but found one with constraint " +
2636 ty_constr_to_str(a_constr);
2641 // Replaces type parameters in the given type using the given list of
2643 fn substitute_type_params(cx: ctxt, substs: [ty::t], typ: t) -> t {
2644 if !type_contains_params(cx, typ) { ret typ; }
2645 fn substituter(_cx: ctxt, substs: @[ty::t], idx: uint, _did: def_id)
2647 // FIXME: bounds check can fail
2650 ret fold_ty(cx, fm_param(bind substituter(cx, @substs, _, _)), typ);
2653 fn def_has_ty_params(def: ast::def) -> bool {
2655 ast::def_obj_field(_, _) | ast::def_mod(_) | ast::def_const(_) |
2656 ast::def_arg(_, _) | ast::def_local(_, _) | ast::def_upvar(_, _, _) |
2657 ast::def_ty_param(_, _) | ast::def_binding(_) | ast::def_use(_) |
2658 ast::def_native_ty(_) | ast::def_self(_) | ast::def_ty(_) { false }
2659 ast::def_fn(_, _) | ast::def_variant(_, _) |
2660 ast::def_native_fn(_, _) { true }
2664 fn store_iface_methods(cx: ctxt, id: ast::node_id, ms: @[method]) {
2665 cx.iface_method_cache.insert(ast_util::local_def(id), ms);
2668 fn iface_methods(cx: ctxt, id: ast::def_id) -> @[method] {
2669 alt cx.iface_method_cache.find(id) {
2670 some(ms) { ret ms; }
2673 // Local interfaces are supposed to have been added explicitly.
2674 assert id.crate != ast::local_crate;
2675 let result = csearch::get_iface_methods(cx, id);
2676 cx.iface_method_cache.insert(id, result);
2680 fn impl_iface(cx: ctxt, id: ast::def_id) -> option::t<t> {
2681 if id.crate == ast::local_crate {
2682 option::map(cx.tcache.find(id), {|it| it.ty})
2684 csearch::get_impl_iface(cx, id)
2689 type variant_info = @{args: [ty::t], ctor_ty: ty::t, id: ast::def_id};
2691 fn tag_variants(cx: ctxt, id: ast::def_id) -> @[variant_info] {
2692 alt cx.tag_var_cache.find(id) {
2693 some(variants) { ret variants; }
2694 _ { /* fallthrough */ }
2696 let result = if ast::local_crate != id.crate {
2697 @csearch::get_tag_variants(cx, id)
2699 alt cx.items.get(id.node) {
2700 ast_map::node_item(@{node: ast::item_tag(variants, _), _}) {
2701 @vec::map(variants, {|variant|
2702 let ctor_ty = node_id_to_monotype(cx, variant.node.id);
2703 let arg_tys = if vec::len(variant.node.args) > 0u {
2704 vec::map(ty_fn_args(cx, ctor_ty), {|a| a.ty})
2708 id: ast_util::local_def(variant.node.id)}
2713 cx.tag_var_cache.insert(id, result);
2718 // Returns information about the tag variant with the given ID:
2719 fn tag_variant_with_id(cx: ctxt, tag_id: ast::def_id, variant_id: ast::def_id)
2721 let variants = tag_variants(cx, tag_id);
2723 while i < vec::len::<variant_info>(*variants) {
2724 let variant = variants[i];
2725 if def_eq(variant.id, variant_id) { ret variant; }
2728 cx.sess.bug("tag_variant_with_id(): no variant exists with that ID");
2732 // If the given item is in an external crate, looks up its type and adds it to
2733 // the type cache. Returns the type parameters and type.
2734 fn lookup_item_type(cx: ctxt, did: ast::def_id) -> ty_param_bounds_and_ty {
2735 if did.crate == ast::local_crate {
2736 // The item is in this crate. The caller should have added it to the
2737 // type cache already; we simply return it.
2739 ret cx.tcache.get(did);
2741 alt cx.tcache.find(did) {
2742 some(tpt) { ret tpt; }
2744 let tyt = csearch::get_type(cx, did);
2745 cx.tcache.insert(did, tyt);
2751 fn ret_ty_of_fn(cx: ctxt, id: ast::node_id) -> t {
2752 ty_fn_ret(cx, node_id_to_type(cx, id))
2755 fn is_binopable(cx: ctxt, ty: t, op: ast::binop) -> bool {
2757 const tycat_other: int = 0;
2758 const tycat_bool: int = 1;
2759 const tycat_int: int = 2;
2760 const tycat_float: int = 3;
2761 const tycat_str: int = 4;
2762 const tycat_vec: int = 5;
2763 const tycat_struct: int = 6;
2764 const tycat_bot: int = 7;
2766 const opcat_add: int = 0;
2767 const opcat_sub: int = 1;
2768 const opcat_mult: int = 2;
2769 const opcat_shift: int = 3;
2770 const opcat_rel: int = 4;
2771 const opcat_eq: int = 5;
2772 const opcat_bit: int = 6;
2773 const opcat_logic: int = 7;
2775 fn opcat(op: ast::binop) -> int {
2777 ast::add. { opcat_add }
2778 ast::sub. { opcat_sub }
2779 ast::mul. { opcat_mult }
2780 ast::div. { opcat_mult }
2781 ast::rem. { opcat_mult }
2782 ast::and. { opcat_logic }
2783 ast::or. { opcat_logic }
2784 ast::bitxor. { opcat_bit }
2785 ast::bitand. { opcat_bit }
2786 ast::bitor. { opcat_bit }
2787 ast::lsl. { opcat_shift }
2788 ast::lsr. { opcat_shift }
2789 ast::asr. { opcat_shift }
2790 ast::eq. { opcat_eq }
2791 ast::ne. { opcat_eq }
2792 ast::lt. { opcat_rel }
2793 ast::le. { opcat_rel }
2794 ast::ge. { opcat_rel }
2795 ast::gt. { opcat_rel }
2799 fn tycat(cx: ctxt, ty: t) -> int {
2800 alt struct(cx, ty) {
2801 ty_bool. { tycat_bool }
2802 ty_int(_) { tycat_int }
2803 ty_uint(_) { tycat_int }
2804 ty_float(_) { tycat_float }
2805 ty_str. { tycat_str }
2806 ty_vec(_) { tycat_vec }
2807 ty_rec(_) { tycat_struct }
2808 ty_tup(_) { tycat_struct }
2809 ty_tag(_, _) { tycat_struct }
2810 ty_bot. { tycat_bot }
2815 const t: bool = true;
2816 const f: bool = false;
2829 [[f, f, f, f, t, t, f, f], [f, f, f, f, t, t, t, t],
2830 [t, t, t, t, t, t, t, f], [t, t, t, f, t, t, f, f],
2831 [t, f, f, f, t, t, f, f], [t, f, f, f, t, t, f, f],
2832 [f, f, f, f, t, t, f, f], [t, t, t, t, t, t, t, t]]; /*struct*/
2834 ret tbl[tycat(cx, ty)][opcat(op)];
2837 fn ast_constr_to_constr<T>(tcx: ty::ctxt, c: @ast::constr_general<T>) ->
2838 @ty::constr_general<T> {
2839 alt tcx.def_map.find(c.node.id) {
2840 some(ast::def_fn(pred_id, ast::pure_fn.)) {
2841 ret @ast_util::respan(c.span,
2847 tcx.sess.span_fatal(c.span,
2848 "Predicate " + path_to_str(c.node.path) +
2849 " is unbound or bound to a non-function or an \
2858 // indent-tabs-mode: nil
2859 // c-basic-offset: 4
2860 // buffer-file-coding-system: utf-8-unix