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(_, _, _) |
851 ty_iface(_, _) { true }
856 fn type_is_copyable(cx: ctxt, ty: t) -> bool {
857 ret kind_can_be_copied(type_kind(cx, ty));
860 fn type_is_sequence(cx: ctxt, ty: t) -> bool {
862 ty_str. { ret true; }
863 ty_vec(_) { ret true; }
868 fn type_is_str(cx: ctxt, ty: t) -> bool {
869 alt struct(cx, ty) { ty_str. { ret true; } _ { ret false; } }
872 fn sequence_element_type(cx: ctxt, ty: t) -> t {
874 ty_str. { ret mk_mach_uint(cx, ast::ty_u8); }
875 ty_vec(mt) { ret mt.ty; }
876 _ { cx.sess.bug("sequence_element_type called on non-sequence value"); }
880 pure fn type_is_tup_like(cx: ctxt, ty: t) -> bool {
881 let sty = struct(cx, ty);
883 ty_ptr(_) | ty_uniq(_) |
884 ty_box(_) | ty_rec(_) | ty_tup(_) | ty_tag(_,_) { true }
889 fn get_element_type(cx: ctxt, ty: t, i: uint) -> t {
891 ty_rec(flds) { ret flds[i].mt.ty; }
892 ty_tup(ts) { ret ts[i]; }
894 cx.sess.bug("get_element_type called on type " + ty_to_str(cx, ty) +
899 // NB: This is not exhaustive -- struct(cx, ty) could be a box or a
903 pure fn type_is_box(cx: ctxt, ty: t) -> bool {
905 ty_box(_) { ret true; }
910 pure fn type_is_boxed(cx: ctxt, ty: t) -> bool {
912 ty_box(_) { ret true; }
917 pure fn type_is_unique_box(cx: ctxt, ty: t) -> bool {
919 ty_uniq(_) { ret true; }
924 pure fn type_is_unsafe_ptr(cx: ctxt, ty: t) -> bool {
926 ty_ptr(_) { ret true; }
931 pure fn type_is_vec(cx: ctxt, ty: t) -> bool {
932 ret alt struct(cx, ty) {
939 pure fn type_is_unique(cx: ctxt, ty: t) -> bool {
941 ty_uniq(_) { ret true; }
948 pure fn type_is_scalar(cx: ctxt, ty: t) -> bool {
950 ty_nil. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
951 ty_send_type. | ty_type. | ty_native(_) | ty_ptr(_) { true }
956 // FIXME maybe inline this for speed?
957 fn type_is_immediate(cx: ctxt, ty: t) -> bool {
958 ret type_is_scalar(cx, ty) || type_is_boxed(cx, ty) ||
959 type_is_unique(cx, ty) || type_is_native(cx, ty);
962 fn type_needs_drop(cx: ctxt, ty: t) -> bool {
963 alt cx.needs_drop_cache.find(ty) {
964 some(result) { ret result; }
965 none. {/* fall through */ }
969 let result = alt struct(cx, ty) {
971 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
972 ty_type. | ty_native(_) | ty_ptr(_) { false }
974 for f in flds { if type_needs_drop(cx, f.mt.ty) { accum = true; } }
978 for m in elts { if type_needs_drop(cx, m) { accum = true; } }
982 let variants = tag_variants(cx, did);
983 for variant in *variants {
984 for aty in variant.args {
985 // Perform any type parameter substitutions.
986 let arg_ty = substitute_type_params(cx, tps, aty);
987 if type_needs_drop(cx, arg_ty) { accum = true; }
996 cx.needs_drop_cache.insert(ty, result);
1000 tag kind { kind_sendable; kind_copyable; kind_noncopyable; }
1002 // Using these query functons is preferable to direct comparison or matching
1003 // against the kind constants, as we may modify the kind hierarchy in the
1005 pure fn kind_can_be_copied(k: kind) -> bool {
1007 kind_sendable. { true }
1008 kind_copyable. { true }
1009 kind_noncopyable. { false }
1013 pure fn kind_can_be_sent(k: kind) -> bool {
1015 kind_sendable. { true }
1016 kind_copyable. { false }
1017 kind_noncopyable. { false }
1021 fn proto_kind(p: proto) -> kind {
1023 ast::proto_block. { kind_noncopyable }
1024 ast::proto_shared(_) { kind_copyable }
1025 ast::proto_send. { kind_sendable }
1026 ast::proto_bare. { kind_sendable }
1030 fn kind_lteq(a: kind, b: kind) -> bool {
1032 kind_noncopyable. { true }
1033 kind_copyable. { b != kind_noncopyable }
1034 kind_sendable. { b == kind_sendable }
1038 fn lower_kind(a: kind, b: kind) -> kind {
1039 if ty::kind_lteq(a, b) { a } else { b }
1042 fn type_kind(cx: ctxt, ty: t) -> kind {
1043 alt cx.kind_cache.find(ty) {
1044 some(result) { ret result; }
1045 none. {/* fall through */ }
1048 // Insert a default in case we loop back on self recursively.
1049 cx.kind_cache.insert(ty, kind_sendable);
1051 let result = alt struct(cx, ty) {
1052 // Scalar and unique types are sendable
1053 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_uint(_) | ty_float(_) |
1054 ty_native(_) | ty_ptr(_) |
1055 ty_send_type. | ty_str. | ty_native_fn(_, _) { kind_sendable }
1056 ty_type. { kind_copyable }
1057 // FIXME: obj is broken for now, since we aren't asserting
1058 // anything about its fields.
1059 ty_obj(_) { kind_copyable }
1060 ty_fn(f) { proto_kind(f.proto) }
1061 ty_opaque_closure_ptr(closure_block.) { kind_noncopyable }
1062 ty_opaque_closure_ptr(closure_shared.) { kind_copyable }
1063 ty_opaque_closure_ptr(closure_send.) { kind_sendable }
1064 // Those with refcounts-to-inner raise pinned to shared,
1065 // lower unique to shared. Therefore just set result to shared.
1066 ty_box(_) | ty_iface(_, _) { kind_copyable }
1067 // Boxes and unique pointers raise pinned to shared.
1068 ty_vec(tm) | ty_uniq(tm) { type_kind(cx, tm.ty) }
1069 // Records lower to the lowest of their members.
1071 let lowest = kind_sendable;
1072 for f in flds { lowest = lower_kind(lowest, type_kind(cx, f.mt.ty)); }
1075 // Tuples lower to the lowest of their members.
1077 let lowest = kind_sendable;
1078 for ty in tys { lowest = lower_kind(lowest, type_kind(cx, ty)); }
1081 // Tags lower to the lowest of their variants.
1083 let lowest = kind_sendable;
1084 for variant in *tag_variants(cx, did) {
1085 for aty in variant.args {
1086 // Perform any type parameter substitutions.
1087 let arg_ty = substitute_type_params(cx, tps, aty);
1088 lowest = lower_kind(lowest, type_kind(cx, arg_ty));
1089 if lowest == kind_noncopyable { break; }
1094 // Resources are always noncopyable.
1095 ty_res(did, inner, tps) { kind_noncopyable }
1097 param_bounds_to_kind(cx.ty_param_bounds.get(did.node))
1099 ty_constr(t, _) { type_kind(cx, t) }
1102 cx.kind_cache.insert(ty, result);
1106 // FIXME: should we just return true for native types in
1108 fn type_is_native(cx: ctxt, ty: t) -> bool {
1109 alt struct(cx, ty) { ty_native(_) { ret true; } _ { ret false; } }
1112 fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
1114 let sty = struct(cx, ty);
1115 if test(sty) { ret true; }
1118 for variant in *tag_variants(cx, did) {
1119 for aty in variant.args {
1120 let sty = substitute_type_params(cx, tps, aty);
1121 if type_structurally_contains(cx, sty, test) { ret true; }
1127 for field in fields {
1128 if type_structurally_contains(cx, field.mt.ty, test) { ret true; }
1134 if type_structurally_contains(cx, tt, test) { ret true; }
1138 ty_res(_, sub, tps) {
1139 let sty = substitute_type_params(cx, tps, sub);
1140 ret type_structurally_contains(cx, sty, test);
1146 pure fn type_has_dynamic_size(cx: ctxt, ty: t) -> bool unchecked {
1148 /* type_structurally_contains can't be declared pure
1149 because it takes a function argument. But it should be
1150 referentially transparent, since a given type's size should
1151 never change once it's created.
1152 (It would be interesting to think about how to make such properties
1153 actually checkable. It seems to me like a lot of properties
1154 that the type context tracks about types should be immutable.)
1156 type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1158 ty_param(_, _) { true }
1164 // Returns true for noncopyable types and types where a copy of a value can be
1165 // distinguished from the value itself. I.e. types with mutable content that's
1166 // not shared through a pointer.
1167 fn type_allows_implicit_copy(cx: ctxt, ty: t) -> bool {
1168 ret !type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1170 ty_param(_, _) { true }
1175 for field in fields {
1185 }) && type_kind(cx, ty) != kind_noncopyable;
1188 fn type_structurally_contains_uniques(cx: ctxt, ty: t) -> bool {
1189 ret type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1191 ty_uniq(_) { ret true; }
1199 fn type_is_integral(cx: ctxt, ty: t) -> bool {
1200 alt struct(cx, ty) {
1201 ty_int(_) | ty_uint(_) | ty_bool. { true }
1206 fn type_is_fp(cx: ctxt, ty: t) -> bool {
1207 alt struct(cx, ty) {
1208 ty_float(_) { true }
1213 fn type_is_numeric(cx: ctxt, ty: t) -> bool {
1214 ret type_is_integral(cx, ty) || type_is_fp(cx, ty);
1217 fn type_is_signed(cx: ctxt, ty: t) -> bool {
1218 alt struct(cx, ty) {
1224 // Whether a type is Plain Old Data -- meaning it does not contain pointers
1225 // that the cycle collector might care about.
1226 fn type_is_pod(cx: ctxt, ty: t) -> bool {
1228 alt struct(cx, ty) {
1230 ty_nil. | ty_bot. | ty_bool. | ty_int(_) | ty_float(_) | ty_uint(_) |
1231 ty_send_type. | ty_type. | ty_native(_) | ty_ptr(_) { result = true; }
1233 ty_str. | ty_box(_) | ty_uniq(_) | ty_vec(_) | ty_fn(_) |
1234 ty_native_fn(_, _) | ty_obj(_) | ty_iface(_, _) { result = false; }
1237 let variants = tag_variants(cx, did);
1238 for variant: variant_info in *variants {
1239 let tup_ty = mk_tup(cx, variant.args);
1241 // Perform any type parameter substitutions.
1242 tup_ty = substitute_type_params(cx, tps, tup_ty);
1243 if !type_is_pod(cx, tup_ty) { result = false; }
1247 for f: field in flds {
1248 if !type_is_pod(cx, f.mt.ty) { result = false; }
1252 for elt in elts { if !type_is_pod(cx, elt) { result = false; } }
1254 ty_res(_, inner, tps) {
1255 result = type_is_pod(cx, substitute_type_params(cx, tps, inner));
1257 ty_constr(subt, _) { result = type_is_pod(cx, subt); }
1259 fail "ty_var in type_is_pod";
1261 ty_param(_, _) { result = false; }
1267 fn type_param(cx: ctxt, ty: t) -> option::t<uint> {
1268 alt struct(cx, ty) {
1269 ty_param(id, _) { ret some(id); }
1270 _ {/* fall through */ }
1275 // Returns a vec of all the type variables
1276 // occurring in t. It may contain duplicates.
1277 fn vars_in_type(cx: ctxt, ty: t) -> [int] {
1278 fn collect_var(cx: ctxt, vars: @mutable [int], ty: t) {
1279 alt struct(cx, ty) { ty_var(v) { *vars += [v]; } _ { } }
1281 let rslt: @mutable [int] = @mutable [];
1282 walk_ty(cx, bind collect_var(cx, rslt, _), ty);
1283 // Works because of a "convenient" bug that lets us
1284 // return a mutable vec as if it's immutable
1288 fn type_autoderef(cx: ctxt, t: ty::t) -> ty::t {
1291 alt struct(cx, t1) {
1292 ty_box(mt) | ty_uniq(mt) { t1 = mt.ty; }
1293 ty_res(_, inner, tps) {
1294 t1 = substitute_type_params(cx, tps, inner);
1297 let variants = tag_variants(cx, did);
1298 if vec::len(*variants) != 1u || vec::len(variants[0].args) != 1u {
1301 t1 = substitute_type_params(cx, tps, variants[0].args[0]);
1310 fn hash_type_structure(st: sty) -> uint {
1311 fn hash_uint(id: uint, n: uint) -> uint {
1316 fn hash_def(id: uint, did: ast::def_id) -> uint {
1318 h += (h << 5u) + (did.crate as uint);
1319 h += (h << 5u) + (did.node as uint);
1322 fn hash_subty(id: uint, subty: t) -> uint {
1324 h += (h << 5u) + subty;
1327 fn hash_subtys(id: uint, subtys: [t]) -> uint {
1329 vec::iter(subtys) { |subty|
1330 h = hash_subty(h, subty);
1334 fn hash_type_constr(id: uint, c: @type_constr) -> uint {
1336 h += (h << 5u) + hash_def(h, c.node.id);
1337 ret hash_type_constr_args(h, c.node.args);
1339 fn hash_type_constr_args(id: uint, args: [@ty_constr_arg]) -> uint {
1341 for a: @ty_constr_arg in args {
1343 carg_base. { h += h << 5u; }
1346 fail "lit args not implemented yet";
1349 // FIXME: Not sure what to do here.
1357 fn hash_fn(id: uint, args: [arg], rty: t) -> uint {
1359 for a: arg in args { h += (h << 5u) + a.ty; }
1360 h += (h << 5u) + rty;
1364 ty_nil. { 0u } ty_bool. { 1u }
1367 ast::ty_i. { 2u } ast::ty_char. { 3u } ast::ty_i8. { 4u }
1368 ast::ty_i16. { 5u } ast::ty_i32. { 6u } ast::ty_i64. { 7u }
1373 ast::ty_u. { 8u } ast::ty_u8. { 9u } ast::ty_u16. { 10u }
1374 ast::ty_u32. { 11u } ast::ty_u64. { 12u }
1378 alt t { ast::ty_f. { 13u } ast::ty_f32. { 14u } ast::ty_f64. { 15u } }
1380 ty_str. { ret 17u; }
1382 let h = hash_def(18u, did);
1383 for typ: t in tys { h += (h << 5u) + typ; }
1386 ty_box(mt) { ret hash_subty(19u, mt.ty); }
1387 ty_vec(mt) { ret hash_subty(21u, mt.ty); }
1390 for f: field in fields { h += (h << 5u) + f.mt.ty; }
1393 ty_tup(ts) { ret hash_subtys(25u, ts); }
1396 ty_fn(f) { ret hash_fn(27u, f.inputs, f.output); }
1397 ty_native_fn(args, rty) { ret hash_fn(28u, args, rty); }
1400 for m: method in methods { h += (h << 5u) + str::hash(m.ident); }
1403 ty_var(v) { ret hash_uint(30u, v as uint); }
1404 ty_param(pid, _) { ret hash_uint(31u, pid); }
1405 ty_type. { ret 32u; }
1406 ty_native(did) { ret hash_def(33u, did); }
1407 ty_bot. { ret 34u; }
1408 ty_ptr(mt) { ret hash_subty(35u, mt.ty); }
1409 ty_res(did, sub, tps) {
1410 let h = hash_subty(hash_def(18u, did), sub);
1411 ret hash_subtys(h, tps);
1414 let h = hash_subty(36u, t);
1415 for c: @type_constr in cs { h += (h << 5u) + hash_type_constr(h, c); }
1418 ty_uniq(mt) { ret hash_subty(37u, mt.ty); }
1419 ty_send_type. { ret 38u; }
1420 ty_named(t, name) { (str::hash(*name) << 5u) + hash_subty(39u, t) }
1421 ty_iface(did, tys) {
1422 let h = hash_def(40u, did);
1423 for typ: t in tys { h = hash_subty(h, typ); }
1426 ty_opaque_closure_ptr(closure_block.) { ret 41u; }
1427 ty_opaque_closure_ptr(closure_shared.) { ret 42u; }
1428 ty_opaque_closure_ptr(closure_send.) { ret 43u; }
1432 fn hash_raw_ty(&&rt: @raw_t) -> uint { ret rt.hash; }
1434 fn arg_eq<T>(eq: fn(T, T) -> bool, a: @sp_constr_arg<T>, b: @sp_constr_arg<T>)
1438 alt b.node { ast::carg_base. { ret true; } _ { ret false; } }
1440 ast::carg_ident(s) {
1441 alt b.node { ast::carg_ident(t) { ret eq(s, t); } _ { ret false; } }
1445 ast::carg_lit(m) { ret ast_util::lit_eq(l, m); } _ { ret false; }
1451 fn args_eq<T>(eq: fn(T, T) -> bool, a: [@sp_constr_arg<T>],
1452 b: [@sp_constr_arg<T>]) -> bool {
1454 for arg: @sp_constr_arg<T> in a {
1455 if !arg_eq(eq, arg, b[i]) { ret false; }
1461 fn constr_eq(c: @constr, d: @constr) -> bool {
1462 fn eq_int(&&x: uint, &&y: uint) -> bool { ret x == y; }
1463 ret path_to_str(c.node.path) == path_to_str(d.node.path) &&
1465 args_eq(eq_int, c.node.args, d.node.args);
1468 fn constrs_eq(cs: [@constr], ds: [@constr]) -> bool {
1469 if vec::len(cs) != vec::len(ds) { ret false; }
1471 for c: @constr in cs { if !constr_eq(c, ds[i]) { ret false; } i += 1u; }
1476 fn node_id_to_ty_param_substs_opt_and_ty(cx: ctxt, id: ast::node_id) ->
1477 ty_param_substs_opt_and_ty {
1478 // Pull out the node type table.
1479 alt smallintmap::find(*cx.node_types, id as uint) {
1481 cx.sess.bug("node_id_to_ty_param_substs_opt_and_ty() called on " +
1482 "an untyped node (" + int::to_str(id, 10u) +
1485 some(tpot) { ret tpot; }
1489 fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
1490 ret node_id_to_ty_param_substs_opt_and_ty(cx, id).ty;
1493 fn node_id_to_type_params(cx: ctxt, id: ast::node_id) -> [t] {
1494 alt node_id_to_ty_param_substs_opt_and_ty(cx, id).substs {
1496 some(tps) { ret tps; }
1500 fn node_id_has_type_params(cx: ctxt, id: ast::node_id) -> bool {
1501 ret vec::len(node_id_to_type_params(cx, id)) > 0u;
1505 // Returns a type with type parameter substitutions performed if applicable.
1506 fn ty_param_substs_opt_and_ty_to_monotype(cx: ctxt,
1507 tpot: ty_param_substs_opt_and_ty) ->
1510 none. { ret tpot.ty; }
1511 some(tps) { ret substitute_type_params(cx, tps, tpot.ty); }
1516 // Returns the type of an annotation, with type parameter substitutions
1517 // performed if applicable.
1518 fn node_id_to_monotype(cx: ctxt, id: ast::node_id) -> t {
1519 let tpot = node_id_to_ty_param_substs_opt_and_ty(cx, id);
1520 ret ty_param_substs_opt_and_ty_to_monotype(cx, tpot);
1524 // Returns the number of distinct type parameters in the given type.
1525 fn count_ty_params(cx: ctxt, ty: t) -> uint {
1526 fn counter(cx: ctxt, param_indices: @mutable [uint], ty: t) {
1527 alt struct(cx, ty) {
1528 ty_param(param_idx, _) {
1530 for other_param_idx: uint in *param_indices {
1531 if param_idx == other_param_idx { seen = true; }
1533 if !seen { *param_indices += [param_idx]; }
1535 _ {/* fall through */ }
1538 let param_indices: @mutable [uint] = @mutable [];
1539 let f = bind counter(cx, param_indices, _);
1541 ret vec::len::<uint>(*param_indices);
1544 fn type_contains_vars(cx: ctxt, typ: t) -> bool {
1545 ret interner::get(*cx.ts, typ).has_vars;
1548 fn type_contains_params(cx: ctxt, typ: t) -> bool {
1549 ret interner::get(*cx.ts, typ).has_params;
1553 // Type accessors for substructures of types
1554 fn ty_fn_args(cx: ctxt, fty: t) -> [arg] {
1555 alt struct(cx, fty) {
1556 ty::ty_fn(f) { ret f.inputs; }
1557 ty::ty_native_fn(a, _) { ret a; }
1558 _ { cx.sess.bug("ty_fn_args() called on non-fn type"); }
1562 fn ty_fn_proto(cx: ctxt, fty: t) -> ast::proto {
1563 alt struct(cx, fty) {
1564 ty::ty_fn(f) { ret f.proto; }
1565 ty::ty_native_fn(_, _) {
1566 // FIXME: This should probably be proto_bare
1567 ret ast::proto_shared(ast::sugar_normal);
1569 _ { cx.sess.bug("ty_fn_proto() called on non-fn type"); }
1573 pure fn ty_fn_ret(cx: ctxt, fty: t) -> t {
1574 let sty = struct(cx, fty);
1576 ty::ty_fn(f) { ret f.output; }
1577 ty::ty_native_fn(_, r) { ret r; }
1579 // Unchecked is ok since we diverge here
1580 // (might want to change the typechecker to allow
1581 // it without an unchecked)
1582 // Or, it wouldn't be necessary if we had the right
1583 // typestate constraint on cx and t (then we could
1584 // call unreachable() instead)
1585 unchecked { cx.sess.bug("ty_fn_ret() called on non-fn type"); }}
1589 fn ty_fn_ret_style(cx: ctxt, fty: t) -> ast::ret_style {
1590 alt struct(cx, fty) {
1591 ty::ty_fn(f) { f.ret_style }
1592 ty::ty_native_fn(_, _) { ast::return_val }
1593 _ { cx.sess.bug("ty_fn_ret_style() called on non-fn type"); }
1597 fn is_fn_ty(cx: ctxt, fty: t) -> bool {
1598 alt struct(cx, fty) {
1599 ty::ty_fn(_) { ret true; }
1600 ty::ty_native_fn(_, _) { ret true; }
1605 // Just checks whether it's a fn that returns bool,
1607 fn is_pred_ty(cx: ctxt, fty: t) -> bool {
1608 is_fn_ty(cx, fty) && type_is_bool(cx, ty_fn_ret(cx, fty))
1611 fn ty_var_id(cx: ctxt, typ: t) -> int {
1612 alt struct(cx, typ) {
1613 ty::ty_var(vid) { ret vid; }
1614 _ { #error("ty_var_id called on non-var ty"); fail; }
1619 // Type accessors for AST nodes
1620 fn block_ty(cx: ctxt, b: ast::blk) -> t {
1621 ret node_id_to_type(cx, b.node.id);
1625 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
1626 // doesn't provide type parameter substitutions.
1627 fn pat_ty(cx: ctxt, pat: @ast::pat) -> t {
1628 ret node_id_to_monotype(cx, pat.id);
1632 // Returns the type of an expression as a monotype.
1634 // NB: This type doesn't provide type parameter substitutions; e.g. if you
1635 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
1636 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
1637 // expr_ty_params_and_ty() below.
1638 fn expr_ty(cx: ctxt, expr: @ast::expr) -> t {
1639 ret node_id_to_monotype(cx, expr.id);
1642 fn expr_ty_params_and_ty(cx: ctxt, expr: @ast::expr) -> {params: [t], ty: t} {
1643 ret {params: node_id_to_type_params(cx, expr.id),
1644 ty: node_id_to_type(cx, expr.id)};
1647 fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
1648 ret node_id_has_type_params(cx, expr.id);
1651 fn expr_is_lval(method_map: typeck::method_map, tcx: ty::ctxt,
1652 e: @ast::expr) -> bool {
1654 ast::expr_path(_) | ast::expr_index(_, _) |
1655 ast::expr_unary(ast::deref., _) { true }
1656 ast::expr_field(base, ident, _) {
1657 method_map.contains_key(e.id) ? false : {
1658 let basety = type_autoderef(tcx, expr_ty(tcx, base));
1659 alt struct(tcx, basety) {
1669 fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
1671 ast::stmt_decl(_, id) | stmt_expr(_, id) | stmt_semi(_, id) {
1677 fn field_idx(id: ast::ident, fields: [field]) -> option::t<uint> {
1679 for f in fields { if f.ident == id { ret some(i); } i += 1u; }
1683 fn get_field(tcx: ctxt, rec_ty: t, id: ast::ident) -> field {
1684 alt struct(tcx, rec_ty) {
1686 alt vec::find(fields, {|f| str::eq(f.ident, id) }) {
1693 fn method_idx(id: ast::ident, meths: [method]) -> option::t<uint> {
1695 for m in meths { if m.ident == id { ret some(i); } i += 1u; }
1699 fn sort_methods(meths: [method]) -> [method] {
1700 fn method_lteq(a: method, b: method) -> bool {
1701 ret str::lteq(a.ident, b.ident);
1703 ret std::sort::merge_sort(bind method_lteq(_, _), meths);
1706 fn occurs_check_fails(tcx: ctxt, sp: option::t<span>, vid: int, rt: t) ->
1708 if !type_contains_vars(tcx, rt) {
1714 if vec::member(vid, vars_in_type(tcx, rt)) {
1717 // Maybe this should be span_err -- however, there's an
1718 // assertion later on that the type doesn't contain
1719 // variables, so in this case we have to be sure to die.
1721 (s, "Type inference failed because I \
1722 could not find a type\n that's both of the form "
1723 + ty_to_str(tcx, ty::mk_var(tcx, vid)) +
1724 " and of the form " + ty_to_str(tcx, rt) +
1725 ". Such a type would have to be infinitely large.");
1729 } else { ret false; }
1732 // Type unification via Robinson's algorithm (Robinson 1965). Implemented as
1733 // described in Hoder and Voronkov:
1735 // http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
1738 export fixup_result;
1742 export mk_var_bindings;
1743 export resolve_type_structure;
1744 export resolve_type_var;
1749 export var_bindings;
1750 export precise, in_bindings;
1752 tag result { ures_ok(t); ures_err(type_err); }
1753 tag union_result { unres_ok; unres_err(type_err); }
1755 fix_ok(t); // fixup succeeded
1756 fix_err(int); // fixup failed because a type variable was unresolved
1759 {sets: ufind::ufind, types: smallintmap::smallintmap<t>};
1763 in_bindings(@var_bindings);
1765 type ctxt = {st: unify_style, tcx: ty_ctxt};
1767 fn mk_var_bindings() -> @var_bindings {
1768 ret @{sets: ufind::make(), types: smallintmap::mk::<t>()};
1771 // Unifies two sets.
1772 fn union(cx: @ctxt, set_a: uint, set_b: uint,
1773 variance: variance) -> union_result {
1774 let vb = alt cx.st {
1775 in_bindings(vb) { vb }
1777 ufind::grow(vb.sets, math::max(set_a, set_b) + 1u);
1778 let root_a = ufind::find(vb.sets, set_a);
1779 let root_b = ufind::find(vb.sets, set_b);
1782 bind fn (vb: @var_bindings, t: t, set_a: uint, set_b: uint) {
1783 ufind::union(vb.sets, set_a, set_b);
1784 let root_c: uint = ufind::find(vb.sets, set_a);
1785 smallintmap::insert::<t>(vb.types, root_c, t);
1786 }(_, _, set_a, set_b);
1789 alt smallintmap::find(vb.types, root_a) {
1791 alt smallintmap::find(vb.types, root_b) {
1792 none. { ufind::union(vb.sets, set_a, set_b); ret unres_ok; }
1793 some(t_b) { replace_type(vb, t_b); ret unres_ok; }
1797 alt smallintmap::find(vb.types, root_b) {
1798 none. { replace_type(vb, t_a); ret unres_ok; }
1800 alt unify_step(cx, t_a, t_b, variance) {
1801 ures_ok(t_c) { replace_type(vb, t_c); ret unres_ok; }
1802 ures_err(terr) { ret unres_err(terr); }
1810 fn record_var_binding_for_expected(
1811 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1813 cx, key, typ, variance_transform(variance, covariant))
1816 fn record_var_binding_for_actual(
1817 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1818 // Unifying in 'the other direction' so flip the variance
1820 cx, key, typ, variance_transform(variance, contravariant))
1823 fn record_var_binding(
1824 cx: @ctxt, key: int, typ: t, variance: variance) -> result {
1826 let vb = alt cx.st { in_bindings(vb) { vb } };
1827 ufind::grow(vb.sets, (key as uint) + 1u);
1828 let root = ufind::find(vb.sets, key as uint);
1829 let result_type = typ;
1830 alt smallintmap::find(vb.types, root) {
1832 alt unify_step(cx, old_type, typ, variance) {
1833 ures_ok(unified_type) { result_type = unified_type; }
1837 none. {/* fall through */ }
1839 smallintmap::insert::<t>(vb.types, root, result_type);
1843 // Simple structural type comparison.
1844 fn struct_cmp(cx: @ctxt, expected: t, actual: t) -> result {
1846 let cfg = tcx.sess.get_targ_cfg();
1847 if mach_struct(tcx, cfg, expected) == mach_struct(tcx, cfg, actual) {
1848 ret ures_ok(expected);
1850 ret ures_err(terr_mismatch);
1853 // Right now this just checks that the lists of constraints are
1855 fn unify_constrs(base_t: t, expected: [@type_constr],
1856 actual: [@type_constr]) -> result {
1857 let expected_len = vec::len(expected);
1858 let actual_len = vec::len(actual);
1860 if expected_len != actual_len {
1861 ret ures_err(terr_constr_len(expected_len, actual_len));
1865 for c: @type_constr in expected {
1866 rslt = unify_constr(base_t, c, actual[i]);
1867 alt rslt { ures_ok(_) { } ures_err(_) { ret rslt; } }
1870 ret ures_ok(base_t);
1872 fn unify_constr(base_t: t, expected: @type_constr,
1873 actual_constr: @type_constr) -> result {
1874 let ok_res = ures_ok(base_t);
1875 let err_res = ures_err(terr_constr_mismatch(expected, actual_constr));
1876 if expected.node.id != actual_constr.node.id { ret err_res; }
1877 let expected_arg_len = vec::len(expected.node.args);
1878 let actual_arg_len = vec::len(actual_constr.node.args);
1879 if expected_arg_len != actual_arg_len { ret err_res; }
1882 for a: @ty_constr_arg in expected.node.args {
1883 actual = actual_constr.node.args[i];
1886 alt actual.node { carg_base. { } _ { ret err_res; } }
1890 carg_lit(m) { if l != m { ret err_res; } }
1896 carg_ident(q) { if p.node != q.node { ret err_res; } }
1906 // Unifies two mutability flags.
1907 fn unify_mut(expected: ast::mutability, actual: ast::mutability,
1908 variance: variance) ->
1909 option::t<(ast::mutability, variance)> {
1911 // If you're unifying on something mutable then we have to
1912 // be invariant on the inner type
1913 let newvariance = alt expected {
1915 variance_transform(variance, invariant)
1918 variance_transform(variance, covariant)
1922 if expected == actual { ret some((expected, newvariance)); }
1923 if variance == covariant {
1924 if expected == ast::maybe_mut {
1925 ret some((actual, newvariance));
1927 } else if variance == contravariant {
1928 if actual == ast::maybe_mut {
1929 ret some((expected, newvariance));
1934 fn unify_fn_proto(e_proto: ast::proto, a_proto: ast::proto,
1935 variance: variance) -> option::t<result> {
1936 // Prototypes form a diamond-shaped partial order:
1944 // where "^" means "subtype of" (forgive the abuse of the term
1946 fn sub_proto(p_sub: ast::proto, p_sup: ast::proto) -> bool {
1947 ret alt (p_sub, p_sup) {
1948 (_, ast::proto_block.) { true }
1949 (ast::proto_bare., _) { true }
1951 // Equal prototypes (modulo sugar) are always subprotos:
1952 (ast::proto_shared(_), ast::proto_shared(_)) { true }
1953 (_, _) { p_sub == p_sup }
1958 invariant. when e_proto == a_proto { none }
1959 covariant. when sub_proto(a_proto, e_proto) { none }
1960 contravariant. when sub_proto(e_proto, a_proto) { none }
1961 _ { some(ures_err(terr_mismatch)) }
1964 fn unify_args(cx: @ctxt, e_args: [arg], a_args: [arg], variance: variance)
1965 -> either::t<result, [arg]> {
1966 if !vec::same_length(e_args, a_args) {
1967 ret either::left(ures_err(terr_arg_count));
1969 // The variance changes (flips basically) when descending
1970 // into arguments of function types
1971 let variance = variance_transform(variance, contravariant);
1972 // Would use vec::map2(), but for the need to return in case of
1974 let i = 0u, result = [];
1975 for expected_input in e_args {
1976 let actual_input = a_args[i];
1978 // Unify the result modes.
1979 let result_mode = if expected_input.mode == ast::mode_infer {
1981 } else if actual_input.mode == ast::mode_infer {
1983 } else if expected_input.mode != actual_input.mode {
1984 ret either::left(ures_err(terr_mode_mismatch(
1985 expected_input.mode, actual_input.mode)));
1986 } else { expected_input.mode };
1988 alt unify_step(cx, expected_input.ty, actual_input.ty,
1990 ures_ok(rty) { result += [{mode: result_mode, ty: rty}]; }
1991 err { ret either::left(err); }
1994 either::right(result)
1996 fn unify_fn(cx: @ctxt, e_f: fn_ty, a_f: fn_ty, variance: variance)
1998 alt unify_fn_proto(e_f.proto, a_f.proto, variance) {
1999 some(err) { ret err; }
2000 none. { /* fall through */ }
2003 if a_f.ret_style != ast::noreturn && a_f.ret_style != e_f.ret_style {
2004 /* even though typestate checking is mostly
2005 responsible for checking control flow annotations,
2006 this check is necessary to ensure that the
2007 annotation in an object method matches the
2008 declared object type */
2009 ret ures_err(terr_ret_style_mismatch(e_f.ret_style,
2012 let result_ins = alt unify_args(cx, e_f.inputs, a_f.inputs,
2014 either::left(err) { ret err; }
2015 either::right(ts) { ts }
2018 // Check the output.
2019 alt unify_step(cx, e_f.output, a_f.output, variance) {
2021 ures_ok(mk_fn(cx.tcx, {proto: e_f.proto,
2029 fn unify_native_fn(cx: @ctxt, expected_inputs: [arg], expected_output: t,
2030 actual_inputs: [arg], actual_output: t,
2031 variance: variance) -> result {
2032 let result_ins = alt unify_args(cx, expected_inputs,
2033 actual_inputs, variance) {
2034 either::left(err) { ret err; }
2035 either::right(ts) { ts }
2037 alt unify_step(cx, expected_output, actual_output, variance) {
2038 ures_ok(out) { ures_ok(mk_native_fn(cx.tcx, result_ins, out)) }
2042 fn unify_obj(cx: @ctxt, expected_meths: [method],
2043 actual_meths: [method], variance: variance) -> result {
2044 let result_meths: [method] = [];
2046 let expected_len: uint = vec::len(expected_meths);
2047 let actual_len: uint = vec::len(actual_meths);
2048 if expected_len != actual_len { ret ures_err(terr_meth_count); }
2049 while i < expected_len {
2050 let e_meth = expected_meths[i];
2051 let a_meth = actual_meths[i];
2052 if !str::eq(e_meth.ident, a_meth.ident) {
2053 ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident));
2055 alt unify_fn(cx, e_meth.fty, a_meth.fty, variance) {
2057 alt struct(cx.tcx, tfn) {
2059 result_meths += [{ident: e_meth.ident,
2060 tps: a_meth.tps, fty: f}];
2068 let t = mk_obj(cx.tcx, result_meths);
2072 // If the given type is a variable, returns the structure of that type.
2073 fn resolve_type_structure(tcx: ty_ctxt, vb: @var_bindings, typ: t) ->
2075 alt struct(tcx, typ) {
2077 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2078 let root_id = ufind::find(vb.sets, vid as uint);
2079 alt smallintmap::find::<t>(vb.types, root_id) {
2080 none. { ret fix_err(vid); }
2081 some(rt) { ret fix_ok(rt); }
2084 _ { ret fix_ok(typ); }
2088 // Specifies the allowable subtyping between expected and actual types
2090 // Actual may be a subtype of expected
2092 // Actual may be a supertype of expected
2094 // Actual must be the same type as expected
2098 // The calculation for recursive variance
2099 // "Taming the Wildcards: Combining Definition- and Use-Site Variance"
2100 // by John Altidor, et. al.
2102 // I'm just copying the table from figure 1 - haven't actually
2103 // read the paper (yet).
2104 fn variance_transform(a: variance, b: variance) -> variance {
2108 covariant. { covariant }
2109 contravariant. { contravariant }
2110 invariant. { invariant }
2115 covariant. { contravariant }
2116 contravariant. { covariant }
2117 invariant. { invariant }
2122 covariant. { invariant }
2123 contravariant. { invariant }
2124 invariant. { invariant }
2130 fn unify_tps(cx: @ctxt, expected_tps: [t], actual_tps: [t],
2131 variance: variance, finish: block([t]) -> result) -> result {
2132 let result_tps = [], i = 0u;
2133 for exp in expected_tps {
2134 let act = actual_tps[i];
2136 let result = unify_step(cx, exp, act, variance);
2138 ures_ok(rty) { result_tps += [rty]; }
2144 fn unify_step(cx: @ctxt, expected: t, actual: t,
2145 variance: variance) -> result {
2146 // FIXME: rewrite this using tuple pattern matching when available, to
2147 // avoid all this rightward drift and spikiness.
2148 // NOTE: we have tuple matching now, but that involves copying the
2149 // matched elements into a tuple first, which is expensive, since sty
2150 // holds vectors, which are currently unique
2153 if expected == actual { ret ures_ok(expected); }
2155 // Stage 1: Handle the cases in which one side or another is a type
2158 alt struct(cx.tcx, actual) {
2159 // If the RHS is a variable type, then just do the
2160 // appropriate binding.
2161 ty::ty_var(actual_id) {
2162 let actual_n = actual_id as uint;
2163 alt struct(cx.tcx, expected) {
2164 ty::ty_var(expected_id) {
2165 let expected_n = expected_id as uint;
2166 alt union(cx, expected_n, actual_n, variance) {
2167 unres_ok. {/* fall through */ }
2168 unres_err(t_e) { ret ures_err(t_e); }
2172 // Just bind the type variable to the expected type.
2173 alt record_var_binding_for_actual(
2174 cx, actual_id, expected, variance) {
2175 ures_ok(_) {/* fall through */ }
2180 ret ures_ok(mk_var(cx.tcx, actual_id));
2184 alt struct(cx.tcx, expected) {
2185 ty::ty_var(expected_id) {
2186 // Add a binding. (`actual` can't actually be a var here.)
2187 alt record_var_binding_for_expected(
2188 cx, expected_id, actual,
2190 ures_ok(_) {/* fall through */ }
2193 ret ures_ok(mk_var(cx.tcx, expected_id));
2195 _ {/* fall through */ }
2197 // Stage 2: Handle all other cases.
2199 alt struct(cx.tcx, actual) {
2200 ty::ty_bot. { ret ures_ok(expected); }
2201 _ {/* fall through */ }
2203 alt struct(cx.tcx, expected) {
2204 ty::ty_nil. { ret struct_cmp(cx, expected, actual); }
2205 // _|_ unifies with anything
2207 ret ures_ok(actual);
2209 ty::ty_bool. | ty::ty_int(_) | ty_uint(_) | ty_float(_) |
2210 ty::ty_str. | ty::ty_type. | ty::ty_send_type. {
2211 ret struct_cmp(cx, expected, actual);
2213 ty::ty_native(ex_id) {
2214 alt struct(cx.tcx, actual) {
2216 if ex_id.crate == act_id.crate && ex_id.node == act_id.node {
2217 ret ures_ok(actual);
2218 } else { ret ures_err(terr_mismatch); }
2220 _ { ret ures_err(terr_mismatch); }
2223 ty::ty_param(expected_n, _) {
2224 alt struct(cx.tcx, actual) {
2225 ty::ty_param(actual_n, _) when expected_n == actual_n {
2226 ret ures_ok(expected);
2228 _ { ret ures_err(terr_mismatch); }
2231 ty::ty_tag(expected_id, expected_tps) {
2232 alt struct(cx.tcx, actual) {
2233 ty::ty_tag(actual_id, actual_tps) {
2234 if expected_id != actual_id {
2235 ret ures_err(terr_mismatch);
2237 ret unify_tps(cx, expected_tps, actual_tps, variance, {|tps|
2238 ures_ok(mk_tag(cx.tcx, expected_id, tps))
2241 _ {/* fall through */ }
2243 ret ures_err(terr_mismatch);
2245 ty_iface(expected_id, expected_tps) {
2246 alt struct(cx.tcx, actual) {
2247 ty::ty_iface(actual_id, actual_tps) {
2248 if expected_id != actual_id {
2249 ret ures_err(terr_mismatch);
2251 ret unify_tps(cx, expected_tps, actual_tps, variance, {|tps|
2252 ures_ok(mk_iface(cx.tcx, expected_id, tps))
2257 ret ures_err(terr_mismatch);
2259 ty::ty_box(expected_mt) {
2260 alt struct(cx.tcx, actual) {
2261 ty::ty_box(actual_mt) {
2262 let (mut, var) = alt unify_mut(
2263 expected_mt.mut, actual_mt.mut, variance) {
2264 none. { ret ures_err(terr_box_mutability); }
2267 let result = unify_step(
2268 cx, expected_mt.ty, actual_mt.ty, var);
2270 ures_ok(result_sub) {
2271 let mt = {ty: result_sub, mut: mut};
2272 ret ures_ok(mk_box(cx.tcx, mt));
2277 _ { ret ures_err(terr_mismatch); }
2280 ty::ty_uniq(expected_mt) {
2281 alt struct(cx.tcx, actual) {
2282 ty::ty_uniq(actual_mt) {
2283 let (mut, var) = alt unify_mut(
2284 expected_mt.mut, actual_mt.mut, variance) {
2285 none. { ret ures_err(terr_box_mutability); }
2288 let result = unify_step(
2289 cx, expected_mt.ty, actual_mt.ty, var);
2291 ures_ok(result_mt) {
2292 let mt = {ty: result_mt, mut: mut};
2293 ret ures_ok(mk_uniq(cx.tcx, mt));
2298 _ { ret ures_err(terr_mismatch); }
2301 ty::ty_vec(expected_mt) {
2302 alt struct(cx.tcx, actual) {
2303 ty::ty_vec(actual_mt) {
2304 let (mut, var) = alt unify_mut(
2305 expected_mt.mut, actual_mt.mut, variance) {
2306 none. { ret ures_err(terr_vec_mutability); }
2309 let result = unify_step(
2310 cx, expected_mt.ty, actual_mt.ty, var);
2312 ures_ok(result_sub) {
2313 let mt = {ty: result_sub, mut: mut};
2314 ret ures_ok(mk_vec(cx.tcx, mt));
2319 _ { ret ures_err(terr_mismatch); }
2322 ty::ty_ptr(expected_mt) {
2323 alt struct(cx.tcx, actual) {
2324 ty::ty_ptr(actual_mt) {
2325 let (mut, var) = alt unify_mut(
2326 expected_mt.mut, actual_mt.mut, variance) {
2327 none. { ret ures_err(terr_vec_mutability); }
2330 let result = unify_step(
2331 cx, expected_mt.ty, actual_mt.ty, var);
2333 ures_ok(result_sub) {
2334 let mt = {ty: result_sub, mut: mut};
2335 ret ures_ok(mk_ptr(cx.tcx, mt));
2340 _ { ret ures_err(terr_mismatch); }
2343 ty::ty_res(ex_id, ex_inner, ex_tps) {
2344 alt struct(cx.tcx, actual) {
2345 ty::ty_res(act_id, act_inner, act_tps) {
2346 if ex_id.crate != act_id.crate || ex_id.node != act_id.node {
2347 ret ures_err(terr_mismatch);
2349 let result = unify_step(
2350 cx, ex_inner, act_inner, variance);
2352 ures_ok(res_inner) {
2355 for ex_tp: t in ex_tps {
2356 let result = unify_step(
2357 cx, ex_tp, act_tps[i], variance);
2359 ures_ok(rty) { res_tps += [rty]; }
2364 ret ures_ok(mk_res(cx.tcx, act_id, res_inner, res_tps));
2369 _ { ret ures_err(terr_mismatch); }
2372 ty::ty_rec(expected_fields) {
2373 alt struct(cx.tcx, actual) {
2374 ty::ty_rec(actual_fields) {
2375 let expected_len = vec::len::<field>(expected_fields);
2376 let actual_len = vec::len::<field>(actual_fields);
2377 if expected_len != actual_len {
2378 let err = terr_record_size(expected_len, actual_len);
2381 // TODO: implement an iterator that can iterate over
2382 // two arrays simultaneously.
2384 let result_fields: [field] = [];
2386 while i < expected_len {
2387 let expected_field = expected_fields[i];
2388 let actual_field = actual_fields[i];
2389 let (mut, var) = alt unify_mut(
2390 expected_field.mt.mut, actual_field.mt.mut, variance)
2392 none. { ret ures_err(terr_record_mutability); }
2395 if !str::eq(expected_field.ident, actual_field.ident) {
2397 terr_record_fields(expected_field.ident,
2398 actual_field.ident);
2402 unify_step(cx, expected_field.mt.ty,
2403 actual_field.mt.ty, var);
2406 let mt = {ty: rty, mut: mut};
2407 result_fields += [{mt: mt with expected_field}];
2413 ret ures_ok(mk_rec(cx.tcx, result_fields));
2415 _ { ret ures_err(terr_mismatch); }
2418 ty::ty_tup(expected_elems) {
2419 alt struct(cx.tcx, actual) {
2420 ty::ty_tup(actual_elems) {
2421 let expected_len = vec::len(expected_elems);
2422 let actual_len = vec::len(actual_elems);
2423 if expected_len != actual_len {
2424 let err = terr_tuple_size(expected_len, actual_len);
2427 // TODO: implement an iterator that can iterate over
2428 // two arrays simultaneously.
2430 let result_elems = [];
2432 while i < expected_len {
2433 let expected_elem = expected_elems[i];
2434 let actual_elem = actual_elems[i];
2435 let result = unify_step(
2436 cx, expected_elem, actual_elem, variance);
2438 ures_ok(rty) { result_elems += [rty]; }
2443 ret ures_ok(mk_tup(cx.tcx, result_elems));
2445 _ { ret ures_err(terr_mismatch); }
2448 ty::ty_fn(expected_f) {
2449 alt struct(cx.tcx, actual) {
2450 ty::ty_fn(actual_f) {
2451 ret unify_fn(cx, expected_f, actual_f, variance);
2453 _ { ret ures_err(terr_mismatch); }
2456 ty::ty_native_fn(expected_inputs, expected_output) {
2457 alt struct(cx.tcx, actual) {
2458 ty::ty_native_fn(actual_inputs, actual_output) {
2459 ret unify_native_fn(cx, expected_inputs, expected_output,
2460 actual_inputs, actual_output, variance);
2462 _ { ret ures_err(terr_mismatch); }
2465 ty::ty_obj(expected_meths) {
2466 alt struct(cx.tcx, actual) {
2467 ty::ty_obj(actual_meths) {
2468 ret unify_obj(cx, expected_meths, actual_meths, variance);
2470 _ { ret ures_err(terr_mismatch); }
2473 ty::ty_constr(expected_t, expected_constrs) {
2475 // unify the base types...
2476 alt struct(cx.tcx, actual) {
2477 ty::ty_constr(actual_t, actual_constrs) {
2478 let rslt = unify_step(
2479 cx, expected_t, actual_t, variance);
2482 // FIXME: probably too restrictive --
2483 // requires the constraints to be
2484 // syntactically equal
2485 ret unify_constrs(expected, expected_constrs,
2492 // If the actual type is *not* a constrained type,
2493 // then we go ahead and just ignore the constraints on
2494 // the expected type. typestate handles the rest.
2496 cx, expected_t, actual, variance);
2502 fn unify(expected: t, actual: t, st: unify_style,
2503 tcx: ty_ctxt) -> result {
2504 let cx = @{st: st, tcx: tcx};
2505 ret unify_step(cx, expected, actual, covariant);
2507 fn dump_var_bindings(tcx: ty_ctxt, vb: @var_bindings) {
2509 while i < vec::len::<ufind::node>(vb.sets.nodes) {
2512 while j < vec::len::<option::t<uint>>(vb.sets.nodes) {
2513 if ufind::find(vb.sets, j) == i { sets += #fmt[" %u", j]; }
2517 alt smallintmap::find::<t>(vb.types, i) {
2518 none. { typespec = ""; }
2519 some(typ) { typespec = " =" + ty_to_str(tcx, typ); }
2521 #error("set %u:%s%s", i, typespec, sets);
2526 // Fixups and substitutions
2527 // Takes an optional span - complain about occurs check violations
2528 // iff the span is present (so that if we already know we're going
2529 // to error anyway, we don't complain)
2530 fn fixup_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2531 typ: t) -> fixup_result {
2532 fn subst_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2533 unresolved: @mutable option::t<int>, vid: int) -> t {
2534 // Should really return a fixup_result instead of a t, but fold_ty
2535 // doesn't allow returning anything but a t.
2536 if vid as uint >= ufind::set_count(vb.sets) {
2537 *unresolved = some(vid);
2538 ret ty::mk_var(tcx, vid);
2540 let root_id = ufind::find(vb.sets, vid as uint);
2541 alt smallintmap::find::<t>(vb.types, root_id) {
2542 none. { *unresolved = some(vid); ret ty::mk_var(tcx, vid); }
2544 if occurs_check_fails(tcx, sp, vid, rt) {
2545 // Return the type unchanged, so we can error out
2550 fm_var(bind subst_vars(tcx, sp, vb, unresolved,
2555 let unresolved = @mutable none::<int>;
2557 fold_ty(tcx, fm_var(bind subst_vars(tcx, sp, vb, unresolved, _)),
2559 let ur = *unresolved;
2561 none. { ret fix_ok(rty); }
2562 some(var_id) { ret fix_err(var_id); }
2565 fn resolve_type_var(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2566 vid: int) -> fixup_result {
2567 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2568 let root_id = ufind::find(vb.sets, vid as uint);
2569 alt smallintmap::find::<t>(vb.types, root_id) {
2570 none. { ret fix_err(vid); }
2571 some(rt) { ret fixup_vars(tcx, sp, vb, rt); }
2576 fn same_type(cx: ctxt, a: t, b: t) -> bool {
2577 alt unify::unify(a, b, unify::precise, cx) {
2578 unify::ures_ok(_) { true }
2582 fn same_method(cx: ctxt, a: method, b: method) -> bool {
2583 a.tps == b.tps && a.fty.proto == b.fty.proto && a.ident == b.ident &&
2584 vec::all2(a.fty.inputs, b.fty.inputs,
2585 {|a, b| a.mode == b.mode && same_type(cx, a.ty, b.ty) }) &&
2586 same_type(cx, a.fty.output, b.fty.output) &&
2587 a.fty.ret_style == b.fty.ret_style
2590 fn type_err_to_str(err: ty::type_err) -> str {
2592 terr_mismatch. { ret "types differ"; }
2593 terr_ret_style_mismatch(expect, actual) {
2594 fn to_str(s: ast::ret_style) -> str {
2596 ast::noreturn. { "non-returning" }
2597 ast::return_val. { "return-by-value" }
2600 ret to_str(actual) + " function found where " + to_str(expect) +
2601 " function was expected";
2603 terr_box_mutability. { ret "boxed values differ in mutability"; }
2604 terr_vec_mutability. { ret "vectors differ in mutability"; }
2605 terr_tuple_size(e_sz, a_sz) {
2606 ret "expected a tuple with " + uint::to_str(e_sz, 10u) +
2607 " elements but found one with " + uint::to_str(a_sz, 10u) +
2610 terr_record_size(e_sz, a_sz) {
2611 ret "expected a record with " + uint::to_str(e_sz, 10u) +
2612 " fields but found one with " + uint::to_str(a_sz, 10u) +
2615 terr_record_mutability. { ret "record elements differ in mutability"; }
2616 terr_record_fields(e_fld, a_fld) {
2617 ret "expected a record with field '" + e_fld +
2618 "' but found one with field '" + a_fld + "'";
2620 terr_arg_count. { ret "incorrect number of function parameters"; }
2621 terr_meth_count. { ret "incorrect number of object methods"; }
2622 terr_obj_meths(e_meth, a_meth) {
2623 ret "expected an obj with method '" + e_meth +
2624 "' but found one with method '" + a_meth + "'";
2626 terr_mode_mismatch(e_mode, a_mode) {
2627 ret "expected argument mode " + mode_str(e_mode) + " but found " +
2630 terr_constr_len(e_len, a_len) {
2631 ret "Expected a type with " + uint::str(e_len) +
2632 " constraints, but found one with " + uint::str(a_len) +
2635 terr_constr_mismatch(e_constr, a_constr) {
2636 ret "Expected a type with constraint " + ty_constr_to_str(e_constr) +
2637 " but found one with constraint " +
2638 ty_constr_to_str(a_constr);
2643 // Replaces type parameters in the given type using the given list of
2645 fn substitute_type_params(cx: ctxt, substs: [ty::t], typ: t) -> t {
2646 if !type_contains_params(cx, typ) { ret typ; }
2647 fn substituter(_cx: ctxt, substs: @[ty::t], idx: uint, _did: def_id)
2649 // FIXME: bounds check can fail
2652 ret fold_ty(cx, fm_param(bind substituter(cx, @substs, _, _)), typ);
2655 fn def_has_ty_params(def: ast::def) -> bool {
2657 ast::def_obj_field(_, _) | ast::def_mod(_) | ast::def_const(_) |
2658 ast::def_arg(_, _) | ast::def_local(_, _) | ast::def_upvar(_, _, _) |
2659 ast::def_ty_param(_, _) | ast::def_binding(_) | ast::def_use(_) |
2660 ast::def_native_ty(_) | ast::def_self(_) | ast::def_ty(_) { false }
2661 ast::def_fn(_, _) | ast::def_variant(_, _) |
2662 ast::def_native_fn(_, _) { true }
2666 fn store_iface_methods(cx: ctxt, id: ast::node_id, ms: @[method]) {
2667 cx.iface_method_cache.insert(ast_util::local_def(id), ms);
2670 fn iface_methods(cx: ctxt, id: ast::def_id) -> @[method] {
2671 alt cx.iface_method_cache.find(id) {
2672 some(ms) { ret ms; }
2675 // Local interfaces are supposed to have been added explicitly.
2676 assert id.crate != ast::local_crate;
2677 let result = csearch::get_iface_methods(cx, id);
2678 cx.iface_method_cache.insert(id, result);
2682 fn impl_iface(cx: ctxt, id: ast::def_id) -> option::t<t> {
2683 if id.crate == ast::local_crate {
2684 option::map(cx.tcache.find(id), {|it| it.ty})
2686 csearch::get_impl_iface(cx, id)
2691 type variant_info = @{args: [ty::t], ctor_ty: ty::t, id: ast::def_id};
2693 fn tag_variants(cx: ctxt, id: ast::def_id) -> @[variant_info] {
2694 alt cx.tag_var_cache.find(id) {
2695 some(variants) { ret variants; }
2696 _ { /* fallthrough */ }
2698 let result = if ast::local_crate != id.crate {
2699 @csearch::get_tag_variants(cx, id)
2701 alt cx.items.get(id.node) {
2702 ast_map::node_item(@{node: ast::item_tag(variants, _), _}) {
2703 @vec::map(variants, {|variant|
2704 let ctor_ty = node_id_to_monotype(cx, variant.node.id);
2705 let arg_tys = if vec::len(variant.node.args) > 0u {
2706 vec::map(ty_fn_args(cx, ctor_ty), {|a| a.ty})
2710 id: ast_util::local_def(variant.node.id)}
2715 cx.tag_var_cache.insert(id, result);
2720 // Returns information about the tag variant with the given ID:
2721 fn tag_variant_with_id(cx: ctxt, tag_id: ast::def_id, variant_id: ast::def_id)
2723 let variants = tag_variants(cx, tag_id);
2725 while i < vec::len::<variant_info>(*variants) {
2726 let variant = variants[i];
2727 if def_eq(variant.id, variant_id) { ret variant; }
2730 cx.sess.bug("tag_variant_with_id(): no variant exists with that ID");
2734 // If the given item is in an external crate, looks up its type and adds it to
2735 // the type cache. Returns the type parameters and type.
2736 fn lookup_item_type(cx: ctxt, did: ast::def_id) -> ty_param_bounds_and_ty {
2737 if did.crate == ast::local_crate {
2738 // The item is in this crate. The caller should have added it to the
2739 // type cache already; we simply return it.
2741 ret cx.tcache.get(did);
2743 alt cx.tcache.find(did) {
2744 some(tpt) { ret tpt; }
2746 let tyt = csearch::get_type(cx, did);
2747 cx.tcache.insert(did, tyt);
2753 fn ret_ty_of_fn(cx: ctxt, id: ast::node_id) -> t {
2754 ty_fn_ret(cx, node_id_to_type(cx, id))
2757 fn is_binopable(cx: ctxt, ty: t, op: ast::binop) -> bool {
2759 const tycat_other: int = 0;
2760 const tycat_bool: int = 1;
2761 const tycat_int: int = 2;
2762 const tycat_float: int = 3;
2763 const tycat_str: int = 4;
2764 const tycat_vec: int = 5;
2765 const tycat_struct: int = 6;
2766 const tycat_bot: int = 7;
2768 const opcat_add: int = 0;
2769 const opcat_sub: int = 1;
2770 const opcat_mult: int = 2;
2771 const opcat_shift: int = 3;
2772 const opcat_rel: int = 4;
2773 const opcat_eq: int = 5;
2774 const opcat_bit: int = 6;
2775 const opcat_logic: int = 7;
2777 fn opcat(op: ast::binop) -> int {
2779 ast::add. { opcat_add }
2780 ast::sub. { opcat_sub }
2781 ast::mul. { opcat_mult }
2782 ast::div. { opcat_mult }
2783 ast::rem. { opcat_mult }
2784 ast::and. { opcat_logic }
2785 ast::or. { opcat_logic }
2786 ast::bitxor. { opcat_bit }
2787 ast::bitand. { opcat_bit }
2788 ast::bitor. { opcat_bit }
2789 ast::lsl. { opcat_shift }
2790 ast::lsr. { opcat_shift }
2791 ast::asr. { opcat_shift }
2792 ast::eq. { opcat_eq }
2793 ast::ne. { opcat_eq }
2794 ast::lt. { opcat_rel }
2795 ast::le. { opcat_rel }
2796 ast::ge. { opcat_rel }
2797 ast::gt. { opcat_rel }
2801 fn tycat(cx: ctxt, ty: t) -> int {
2802 alt struct(cx, ty) {
2803 ty_bool. { tycat_bool }
2804 ty_int(_) { tycat_int }
2805 ty_uint(_) { tycat_int }
2806 ty_float(_) { tycat_float }
2807 ty_str. { tycat_str }
2808 ty_vec(_) { tycat_vec }
2809 ty_rec(_) { tycat_struct }
2810 ty_tup(_) { tycat_struct }
2811 ty_tag(_, _) { tycat_struct }
2812 ty_bot. { tycat_bot }
2817 const t: bool = true;
2818 const f: bool = false;
2831 [[f, f, f, f, t, t, f, f], [f, f, f, f, t, t, t, t],
2832 [t, t, t, t, t, t, t, f], [t, t, t, f, t, t, f, f],
2833 [t, f, f, f, t, t, f, f], [t, f, f, f, t, t, f, f],
2834 [f, f, f, f, t, t, f, f], [t, t, t, t, t, t, t, t]]; /*struct*/
2836 ret tbl[tycat(cx, ty)][opcat(op)];
2839 fn ast_constr_to_constr<T>(tcx: ty::ctxt, c: @ast::constr_general<T>) ->
2840 @ty::constr_general<T> {
2841 alt tcx.def_map.find(c.node.id) {
2842 some(ast::def_fn(pred_id, ast::pure_fn.)) {
2843 ret @ast_util::respan(c.span,
2849 tcx.sess.span_fatal(c.span,
2850 "Predicate " + path_to_str(c.node.path) +
2851 " is unbound or bound to a non-function or an \
2860 // indent-tabs-mode: nil
2861 // c-basic-offset: 4
2862 // buffer-file-coding-system: utf-8-unix