8 import std::map::hashmap;
10 import std::option::none;
11 import std::option::some;
12 import std::smallintmap;
13 import driver::session;
15 import syntax::ast::*;
16 import syntax::ast_util;
17 import syntax::codemap::span;
18 import metadata::csearch;
19 import util::common::*;
20 import syntax::util::interner;
21 import util::ppaux::ty_to_str;
22 import util::ppaux::ty_constr_to_str;
23 import util::ppaux::mode_str_1;
24 import syntax::print::pprust::*;
26 export node_id_to_monotype;
27 export node_id_to_type;
28 export node_id_to_type_params;
29 export node_id_to_ty_param_substs_opt_and_ty;
32 export ast_constr_to_constr;
33 export bind_params_in_type;
36 export constr_general;
38 export count_ty_params;
40 export def_has_ty_params;
42 export expr_has_ty_params;
44 export expr_ty_params_and_ty;
50 export get_element_type;
55 export lookup_item_type;
58 export method_ty_to_fn_ty;
88 export mk_iter_body_fn;
91 export node_type_table;
96 export sequence_element_type;
102 export substitute_type_params;
105 export tag_variant_with_id;
106 export ty_param_substs_opt_and_ty;
107 export ty_param_kinds_and_ty;
114 export ty_constr_arg;
120 export ty_fn_ret_style;
139 export ty_param_substs_opt_and_ty_to_monotype;
142 export type_contains_params;
143 export type_contains_vars;
146 export type_err_to_str;
147 export type_has_dynamic_size;
148 export type_has_pointers;
149 export type_needs_drop;
153 export type_is_boxed;
154 export type_is_unique_box;
157 export type_allows_implicit_copy;
158 export type_is_integral;
159 export type_is_native;
162 export type_is_scalar;
163 export type_is_sequence;
164 export type_is_signed;
165 export type_is_structural;
166 export type_is_copyable;
167 export type_is_tup_like;
169 export type_is_unique;
170 export type_structurally_contains_uniques;
171 export type_autoderef;
176 export occurs_check_fails;
180 type arg = {mode: mode, ty: t};
182 type field = {ident: ast::ident, mt: mt};
192 type constr_table = hashmap<ast::node_id, [constr]>;
194 type mt = {ty: t, mut: ast::mutability};
197 // Contains information needed to resolve types and (in the future) look up
198 // the types of AST nodes.
199 type creader_cache = hashmap<{cnum: int, pos: uint, len: uint}, ty::t>;
202 // constr_table fn_constrs,
203 // We need the ext_map just for printing the types of tags defined in
204 // other crates. Once we get cnames back it should go.
206 sess: session::session,
207 def_map: resolve::def_map,
208 ext_map: resolve::ext_map,
209 node_types: node_type_table,
211 freevars: freevars::freevar_map,
213 rcache: creader_cache,
214 short_names_cache: hashmap<t, @str>,
215 has_pointer_cache: hashmap<t, bool>,
216 kind_cache: hashmap<t, ast::kind>,
217 ast_ty_to_ty_cache: hashmap<@ast::ty, option::t<t>>};
222 // Needed for disambiguation from unify::ctxt.
223 // Convert from method type to function type. Pretty easy; we just drop
225 fn method_ty_to_fn_ty(cx: ctxt, m: method) -> t {
226 ret mk_fn(cx, m.proto, m.inputs, m.output, m.cf, m.constrs);
230 // Never construct these manually. These are interned.
233 cname: option::t<str>,
241 // NB: If you change this, you'll probably want to change the corresponding
242 // AST structure in front/ast::rs as well.
250 ty_machine(ast::ty_mach);
259 ty_fn(ast::proto, [arg], t, ret_style, [@constr]);
260 ty_native_fn(ast::native_abi, [arg], t);
262 ty_res(def_id, t, [t]);
264 ty_var(int); // type variable
266 ty_param(uint, ast::kind); // fn/tag type param
270 ty_constr(t, [@type_constr]);
271 // TODO: ty_fn_arg(t), for a possibly-aliased function argument
274 // In the middle end, constraints have a def_id attached, referring
275 // to the definition of the operator in the constraint.
276 type constr_general<ARG> = spanned<constr_general_<ARG, def_id>>;
277 type type_constr = constr_general<path>;
278 type constr = constr_general<uint>;
280 // Data structures used in type unification
283 terr_ret_style_mismatch(ast::ret_style, ast::ret_style);
286 terr_tuple_size(uint, uint);
287 terr_record_size(uint, uint);
288 terr_record_mutability;
289 terr_record_fields(ast::ident, ast::ident);
291 terr_obj_meths(ast::ident, ast::ident);
293 terr_mode_mismatch(mode, mode);
294 terr_constr_len(uint, uint);
295 terr_constr_mismatch(@type_constr, @type_constr);
298 type ty_param_kinds_and_ty = {kinds: [ast::kind], ty: t};
300 type type_cache = hashmap<ast::def_id, ty_param_kinds_and_ty>;
302 const idx_nil: uint = 0u;
304 const idx_bool: uint = 1u;
306 const idx_int: uint = 2u;
308 const idx_float: uint = 3u;
310 const idx_uint: uint = 4u;
312 const idx_i8: uint = 5u;
314 const idx_i16: uint = 6u;
316 const idx_i32: uint = 7u;
318 const idx_i64: uint = 8u;
320 const idx_u8: uint = 9u;
322 const idx_u16: uint = 10u;
324 const idx_u32: uint = 11u;
326 const idx_u64: uint = 12u;
328 const idx_f32: uint = 13u;
330 const idx_f64: uint = 14u;
332 const idx_char: uint = 15u;
334 const idx_str: uint = 16u;
336 const idx_type: uint = 17u;
338 const idx_bot: uint = 18u;
340 const idx_first_others: uint = 19u;
342 type type_store = interner::interner<@raw_t>;
344 type ty_param_substs_opt_and_ty = {substs: option::t<[ty::t]>, ty: ty::t};
346 type node_type_table =
347 @smallintmap::smallintmap<ty::ty_param_substs_opt_and_ty>;
349 fn populate_type_store(cx: ctxt) {
350 intern(cx, ty_nil, none);
351 intern(cx, ty_bool, none);
352 intern(cx, ty_int, none);
353 intern(cx, ty_float, none);
354 intern(cx, ty_uint, none);
355 intern(cx, ty_machine(ast::ty_i8), none);
356 intern(cx, ty_machine(ast::ty_i16), none);
357 intern(cx, ty_machine(ast::ty_i32), none);
358 intern(cx, ty_machine(ast::ty_i64), none);
359 intern(cx, ty_machine(ast::ty_u8), none);
360 intern(cx, ty_machine(ast::ty_u16), none);
361 intern(cx, ty_machine(ast::ty_u32), none);
362 intern(cx, ty_machine(ast::ty_u64), none);
363 intern(cx, ty_machine(ast::ty_f32), none);
364 intern(cx, ty_machine(ast::ty_f64), none);
365 intern(cx, ty_char, none);
366 intern(cx, ty_str, none);
367 intern(cx, ty_type, none);
368 intern(cx, ty_bot, none);
369 assert (vec::len(cx.ts.vect) == idx_first_others);
372 fn mk_rcache() -> creader_cache {
373 type val = {cnum: int, pos: uint, len: uint};
374 fn hash_cache_entry(k: val) -> uint {
375 ret (k.cnum as uint) + k.pos + k.len;
377 fn eq_cache_entries(a: val, b: val) -> bool {
378 ret a.cnum == b.cnum && a.pos == b.pos && a.len == b.len;
380 ret map::mk_hashmap(hash_cache_entry, eq_cache_entries);
384 fn mk_ctxt(s: session::session, dm: resolve::def_map,
385 em: hashmap<def_id, [ident]>, amap: ast_map::map,
386 freevars: freevars::freevar_map) -> ctxt {
387 let ntt: node_type_table =
388 @smallintmap::mk::<ty::ty_param_substs_opt_and_ty>();
389 let tcache = new_def_hash::<ty::ty_param_kinds_and_ty>();
390 let ts = @interner::mk::<@raw_t>(hash_raw_ty, eq_raw_ty);
401 short_names_cache: map::mk_hashmap(ty::hash_ty, ty::eq_ty),
402 has_pointer_cache: map::mk_hashmap(ty::hash_ty, ty::eq_ty),
403 kind_cache: map::mk_hashmap(ty::hash_ty, ty::eq_ty),
405 map::mk_hashmap(ast_util::hash_ty, ast_util::eq_ty)};
406 populate_type_store(cx);
412 fn mk_raw_ty(cx: ctxt, st: sty, _in_cname: option::t<str>) -> @raw_t {
413 let cname: option::t<str> = none;
414 let h = hash_type_info(st, cname);
415 let has_params: bool = false;
416 let has_vars: bool = false;
417 fn derive_flags_t(cx: ctxt, &has_params: bool, &has_vars: bool, tt: t) {
418 let rt = interner::get::<@raw_t>(*cx.ts, tt);
419 has_params = has_params || rt.has_params;
420 has_vars = has_vars || rt.has_vars;
422 fn derive_flags_mt(cx: ctxt, &has_params: bool, &has_vars: bool, m: mt) {
423 derive_flags_t(cx, has_params, has_vars, m.ty);
425 fn derive_flags_arg(cx: ctxt, &has_params: bool, &has_vars: bool,
427 derive_flags_t(cx, has_params, has_vars, a.ty);
429 fn derive_flags_sig(cx: ctxt, &has_params: bool, &has_vars: bool,
430 args: [arg], tt: t) {
431 for a: arg in args { derive_flags_arg(cx, has_params, has_vars, a); }
432 derive_flags_t(cx, has_params, has_vars, tt);
435 ty_nil. {/* no-op */ }
436 ty_bot. {/* no-op */ }
437 ty_bool. {/* no-op */ }
438 ty_int. {/* no-op */ }
439 ty_float. {/* no-op */ }
440 ty_uint. {/* no-op */ }
441 ty_machine(_) {/* no-op */ }
442 ty_char. {/* no-op */ }
443 ty_str. {/* no-op */ }
444 ty_type. {/* no-op */ }
445 ty_native(_) {/* no-op */ }
446 ty_param(_, _) { has_params = true; }
447 ty_var(_) { has_vars = true; }
449 for tt: t in tys { derive_flags_t(cx, has_params, has_vars, tt); }
451 ty_box(m) { derive_flags_mt(cx, has_params, has_vars, m); }
452 ty_uniq(m) { derive_flags_mt(cx, has_params, has_vars, m); }
453 ty_vec(m) { derive_flags_mt(cx, has_params, has_vars, m); }
454 ty_ptr(m) { derive_flags_mt(cx, has_params, has_vars, m); }
456 for f: field in flds {
457 derive_flags_mt(cx, has_params, has_vars, f.mt);
461 for tt in ts { derive_flags_t(cx, has_params, has_vars, tt); }
463 ty_fn(_, args, tt, _, _) {
464 derive_flags_sig(cx, has_params, has_vars, args, tt);
466 ty_native_fn(_, args, tt) {
467 derive_flags_sig(cx, has_params, has_vars, args, tt);
470 for m: method in meths {
471 derive_flags_sig(cx, has_params, has_vars, m.inputs, m.output);
475 derive_flags_t(cx, has_params, has_vars, tt);
476 for tt: t in tps { derive_flags_t(cx, has_params, has_vars, tt); }
478 ty_constr(tt, _) { derive_flags_t(cx, has_params, has_vars, tt); }
483 has_params: has_params,
487 fn intern(cx: ctxt, st: sty, cname: option::t<str>) {
488 interner::intern(*cx.ts, mk_raw_ty(cx, st, cname));
491 fn gen_ty_full(cx: ctxt, st: sty, cname: option::t<str>) -> t {
492 let raw_type = mk_raw_ty(cx, st, cname);
493 ret interner::intern(*cx.ts, raw_type);
497 // These are private constructors to this module. External users should always
498 // use the mk_foo() functions below.
499 fn gen_ty(cx: ctxt, st: sty) -> t { ret gen_ty_full(cx, st, none); }
501 fn mk_nil(_cx: ctxt) -> t { ret idx_nil; }
503 fn mk_bot(_cx: ctxt) -> t { ret idx_bot; }
505 fn mk_bool(_cx: ctxt) -> t { ret idx_bool; }
507 fn mk_int(_cx: ctxt) -> t { ret idx_int; }
509 fn mk_float(_cx: ctxt) -> t { ret idx_float; }
511 fn mk_uint(_cx: ctxt) -> t { ret idx_uint; }
513 fn mk_mach(_cx: ctxt, tm: ast::ty_mach) -> t {
515 ast::ty_u8. { ret idx_u8; }
516 ast::ty_u16. { ret idx_u16; }
517 ast::ty_u32. { ret idx_u32; }
518 ast::ty_u64. { ret idx_u64; }
519 ast::ty_i8. { ret idx_i8; }
520 ast::ty_i16. { ret idx_i16; }
521 ast::ty_i32. { ret idx_i32; }
522 ast::ty_i64. { ret idx_i64; }
523 ast::ty_f32. { ret idx_f32; }
524 ast::ty_f64. { ret idx_f64; }
528 fn mk_char(_cx: ctxt) -> t { ret idx_char; }
530 fn mk_str(_cx: ctxt) -> t { ret idx_str; }
532 fn mk_tag(cx: ctxt, did: ast::def_id, tys: [t]) -> t {
533 ret gen_ty(cx, ty_tag(did, tys));
536 fn mk_box(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_box(tm)); }
538 fn mk_uniq(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_uniq(tm)); }
540 fn mk_imm_uniq(cx: ctxt, ty: t) -> t {
541 ret mk_uniq(cx, {ty: ty, mut: ast::imm});
544 fn mk_ptr(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_ptr(tm)); }
546 fn mk_imm_box(cx: ctxt, ty: t) -> t {
547 ret mk_box(cx, {ty: ty, mut: ast::imm});
550 fn mk_mut_ptr(cx: ctxt, ty: t) -> t {
551 ret mk_ptr(cx, {ty: ty, mut: ast::mut});
554 fn mk_vec(cx: ctxt, tm: mt) -> t { ret gen_ty(cx, ty_vec(tm)); }
556 fn mk_rec(cx: ctxt, fs: [field]) -> t { ret gen_ty(cx, ty_rec(fs)); }
558 fn mk_constr(cx: ctxt, t: t, cs: [@type_constr]) -> t {
559 ret gen_ty(cx, ty_constr(t, cs));
562 fn mk_tup(cx: ctxt, ts: [t]) -> t { ret gen_ty(cx, ty_tup(ts)); }
564 fn mk_fn(cx: ctxt, proto: ast::proto, args: [arg], ty: t, cf: ret_style,
565 constrs: [@constr]) -> t {
566 ret gen_ty(cx, ty_fn(proto, args, ty, cf, constrs));
569 fn mk_native_fn(cx: ctxt, abi: ast::native_abi, args: [arg], ty: t) -> t {
570 ret gen_ty(cx, ty_native_fn(abi, args, ty));
573 fn mk_obj(cx: ctxt, meths: [method]) -> t { ret gen_ty(cx, ty_obj(meths)); }
575 fn mk_res(cx: ctxt, did: ast::def_id, inner: t, tps: [t]) -> t {
576 ret gen_ty(cx, ty_res(did, inner, tps));
579 fn mk_var(cx: ctxt, v: int) -> t { ret gen_ty(cx, ty_var(v)); }
581 fn mk_param(cx: ctxt, n: uint, k: ast::kind) -> t {
582 ret gen_ty(cx, ty_param(n, k));
585 fn mk_type(_cx: ctxt) -> t { ret idx_type; }
587 fn mk_native(cx: ctxt, did: def_id) -> t { ret gen_ty(cx, ty_native(did)); }
589 fn mk_iter_body_fn(cx: ctxt, output: t) -> t {
590 ret mk_fn(cx, ast::proto_block, [{mode: ast::by_ref, ty: output}],
591 ty::mk_nil(cx), ast::return_val, []);
594 // Returns the one-level-deep type structure of the given type.
595 fn struct(cx: ctxt, typ: t) -> sty { ret interner::get(*cx.ts, typ).struct; }
598 // Returns the canonical name of the given type.
599 fn cname(cx: ctxt, typ: t) -> option::t<str> {
600 ret interner::get(*cx.ts, typ).cname;
605 type ty_walk = fn(t);
607 fn walk_ty(cx: ctxt, walker: ty_walk, ty: t) {
609 ty_nil. {/* no-op */ }
610 ty_bot. {/* no-op */ }
611 ty_bool. {/* no-op */ }
612 ty_int. {/* no-op */ }
613 ty_uint. {/* no-op */ }
614 ty_float. {/* no-op */ }
615 ty_machine(_) {/* no-op */ }
616 ty_char. {/* no-op */ }
617 ty_str. {/* no-op */ }
618 ty_type. {/* no-op */ }
619 ty_native(_) {/* no-op */ }
620 ty_box(tm) { walk_ty(cx, walker, tm.ty); }
621 ty_vec(tm) { walk_ty(cx, walker, tm.ty); }
622 ty_ptr(tm) { walk_ty(cx, walker, tm.ty); }
623 ty_tag(tid, subtys) {
624 for subty: t in subtys { walk_ty(cx, walker, subty); }
627 for fl: field in fields { walk_ty(cx, walker, fl.mt.ty); }
629 ty_tup(ts) { for tt in ts { walk_ty(cx, walker, tt); } }
630 ty_fn(proto, args, ret_ty, _, _) {
631 for a: arg in args { walk_ty(cx, walker, a.ty); }
632 walk_ty(cx, walker, ret_ty);
634 ty_native_fn(abi, args, ret_ty) {
635 for a: arg in args { walk_ty(cx, walker, a.ty); }
636 walk_ty(cx, walker, ret_ty);
639 for m: method in methods {
640 for a: arg in m.inputs { walk_ty(cx, walker, a.ty); }
641 walk_ty(cx, walker, m.output);
644 ty_res(_, sub, tps) {
645 walk_ty(cx, walker, sub);
646 for tp: t in tps { walk_ty(cx, walker, tp); }
648 ty_constr(sub, _) { walk_ty(cx, walker, sub); }
649 ty_var(_) {/* no-op */ }
650 ty_param(_, _) {/* no-op */ }
651 ty_uniq(tm) { walk_ty(cx, walker, tm.ty); }
657 fm_var(fn(int) -> t);
658 fm_param(fn(uint, ast::kind) -> t);
659 fm_general(fn(t) -> t);
662 fn fold_ty(cx: ctxt, fld: fold_mode, ty_0: t) -> t {
667 fm_var(_) { if !type_contains_vars(cx, ty) { ret ty; } }
668 fm_param(_) { if !type_contains_params(cx, ty) { ret ty; } }
669 fm_general(_) {/* no fast path */ }
672 ty_nil. {/* no-op */ }
673 ty_bot. {/* no-op */ }
674 ty_bool. {/* no-op */ }
675 ty_int. {/* no-op */ }
676 ty_uint. {/* no-op */ }
677 ty_float. {/* no-op */ }
678 ty_machine(_) {/* no-op */ }
679 ty_char. {/* no-op */ }
680 ty_str. {/* no-op */ }
681 ty_type. {/* no-op */ }
682 ty_native(_) {/* no-op */ }
684 ty = mk_box(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
687 ty = mk_uniq(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
690 ty = mk_ptr(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
693 ty = mk_vec(cx, {ty: fold_ty(cx, fld, tm.ty), mut: tm.mut});
695 ty_tag(tid, subtys) {
696 let new_subtys: [t] = [];
697 for subty: t in subtys { new_subtys += [fold_ty(cx, fld, subty)]; }
698 ty = copy_cname(cx, mk_tag(cx, tid, new_subtys), ty);
701 let new_fields: [field] = [];
702 for fl: field in fields {
703 let new_ty = fold_ty(cx, fld, fl.mt.ty);
704 let new_mt = {ty: new_ty, mut: fl.mt.mut};
705 new_fields += [{ident: fl.ident, mt: new_mt}];
707 ty = copy_cname(cx, mk_rec(cx, new_fields), ty);
711 for tt in ts { new_ts += [fold_ty(cx, fld, tt)]; }
712 ty = copy_cname(cx, mk_tup(cx, new_ts), ty);
714 ty_fn(proto, args, ret_ty, cf, constrs) {
715 let new_args: [arg] = [];
717 let new_ty = fold_ty(cx, fld, a.ty);
718 new_args += [{mode: a.mode, ty: new_ty}];
722 mk_fn(cx, proto, new_args, fold_ty(cx, fld, ret_ty),
725 ty_native_fn(abi, args, ret_ty) {
726 let new_args: [arg] = [];
728 let new_ty = fold_ty(cx, fld, a.ty);
729 new_args += [{mode: a.mode, ty: new_ty}];
733 mk_native_fn(cx, abi, new_args,
734 fold_ty(cx, fld, ret_ty)), ty);
737 let new_methods: [method] = [];
738 for m: method in methods {
739 let new_args: [arg] = [];
740 for a: arg in m.inputs {
741 new_args += [{mode: a.mode, ty: fold_ty(cx, fld, a.ty)}];
747 output: fold_ty(cx, fld, m.output),
749 constrs: m.constrs}];
751 ty = copy_cname(cx, mk_obj(cx, new_methods), ty);
753 ty_res(did, subty, tps) {
755 for tp: t in tps { new_tps += [fold_ty(cx, fld, tp)]; }
757 copy_cname(cx, mk_res(cx, did, fold_ty(cx, fld, subty), new_tps),
761 alt fld { fm_var(folder) { ty = folder(id); } _ {/* no-op */ } }
764 alt fld { fm_param(folder) { ty = folder(id, k); } _ {/* no-op */ } }
769 // If this is a general type fold, then we need to run it now.
770 alt fld { fm_general(folder) { ret folder(ty); } _ { ret ty; } }
776 fn rename(cx: ctxt, typ: t, new_cname: str) -> t {
777 ret gen_ty_full(cx, struct(cx, typ), some(new_cname));
780 fn strip_cname(cx: ctxt, typ: t) -> t {
781 ret gen_ty_full(cx, struct(cx, typ), none);
784 // Returns a type with the structural part taken from `struct_ty` and the
785 // canonical name from `cname_ty`.
786 fn copy_cname(cx: ctxt, struct_ty: t, cname_ty: t) -> t {
787 ret gen_ty_full(cx, struct(cx, struct_ty), cname(cx, cname_ty));
790 fn type_is_nil(cx: ctxt, ty: t) -> bool {
791 alt struct(cx, ty) { ty_nil. { ret true; } _ { ret false; } }
794 fn type_is_bot(cx: ctxt, ty: t) -> bool {
795 alt struct(cx, ty) { ty_bot. { ret true; } _ { ret false; } }
798 fn type_is_bool(cx: ctxt, ty: t) -> bool {
799 alt struct(cx, ty) { ty_bool. { ret true; } _ { ret false; } }
802 fn type_is_structural(cx: ctxt, ty: t) -> bool {
804 ty_rec(_) { ret true; }
805 ty_tup(_) { ret true; }
806 ty_tag(_, _) { ret true; }
807 ty_fn(_, _, _, _, _) { ret true; }
808 ty_native_fn(_, _, _) { ret true; }
809 ty_obj(_) { ret true; }
810 ty_res(_, _, _) { ret true; }
815 fn type_is_copyable(cx: ctxt, ty: t) -> bool {
816 ret alt struct(cx, ty) {
817 ty_res(_, _, _) { false }
818 ty_fn(proto_block., _, _, _, _) { false }
823 fn type_is_sequence(cx: ctxt, ty: t) -> bool {
825 ty_str. { ret true; }
826 ty_vec(_) { ret true; }
831 fn type_is_str(cx: ctxt, ty: t) -> bool {
832 alt struct(cx, ty) { ty_str. { ret true; } _ { ret false; } }
835 fn sequence_element_type(cx: ctxt, ty: t) -> t {
837 ty_str. { ret mk_mach(cx, ast::ty_u8); }
838 ty_vec(mt) { ret mt.ty; }
839 _ { cx.sess.bug("sequence_element_type called on non-sequence value"); }
843 pure fn type_is_tup_like(cx: ctxt, ty: t) -> bool {
844 let sty = unchecked { struct(cx, ty) };
846 ty_box(_) | ty_rec(_) | ty_tup(_) | ty_tag(_,_) { true }
851 fn get_element_type(cx: ctxt, ty: t, i: uint) -> t {
853 ty_rec(flds) { ret flds[i].mt.ty; }
854 ty_tup(ts) { ret ts[i]; }
856 cx.sess.bug("get_element_type called on type " + ty_to_str(cx, ty) +
861 // NB: This is not exhaustive -- struct(cx, ty) could be a box or a
865 fn type_is_box(cx: ctxt, ty: t) -> bool {
867 ty_box(_) { ret true; }
872 fn type_is_boxed(cx: ctxt, ty: t) -> bool {
874 ty_box(_) { ret true; }
879 fn type_is_unique_box(cx: ctxt, ty: t) -> bool {
881 ty_uniq(_) { ret true; }
886 fn type_is_vec(cx: ctxt, ty: t) -> bool {
887 ret alt struct(cx, ty) {
894 fn type_is_unique(cx: ctxt, ty: t) -> bool {
896 ty_uniq(_) { ret true; }
903 fn type_is_scalar(cx: ctxt, ty: t) -> bool {
905 ty_nil. { ret true; }
906 ty_bool. { ret true; }
907 ty_int. { ret true; }
908 ty_float. { ret true; }
909 ty_uint. { ret true; }
910 ty_machine(_) { ret true; }
911 ty_char. { ret true; }
912 ty_type. { ret true; }
913 ty_native(_) { ret true; }
914 ty_ptr(_) { ret true; }
919 fn type_has_pointers(cx: ctxt, ty: t) -> bool {
920 alt cx.has_pointer_cache.find(ty) {
921 some(result) { ret result; }
922 none. {/* fall through */ }
935 ty_bot. {/* no-op */ }
936 ty_bool. {/* no-op */ }
937 ty_int. {/* no-op */ }
938 ty_float. {/* no-op */ }
939 ty_uint. {/* no-op */ }
940 ty_machine(_) {/* no-op */ }
941 ty_char. {/* no-op */ }
942 ty_type. {/* no-op */ }
943 ty_native(_) {/* no-op */ }
945 for f: field in flds {
946 if type_has_pointers(cx, f.mt.ty) { result = true; break; }
950 for m in elts { if type_has_pointers(cx, m) { result = true; } }
953 let variants = tag_variants(cx, did);
954 for variant: variant_info in variants {
955 for aty: t in variant.args {
956 // Perform any type parameter substitutions.
957 let arg_ty = substitute_type_params(cx, tps, aty);
958 if type_has_pointers(cx, arg_ty) { result = true; break; }
963 ty_res(did, inner, tps) {
965 type_has_pointers(cx, substitute_type_params(cx, tps, inner));
970 cx.has_pointer_cache.insert(ty, result);
974 fn type_needs_drop(cx: ctxt, ty: t) -> bool {
975 ret alt struct(cx, ty) {
976 ty_res(_, _, _) { true }
977 ty_param(_, _) { true }
978 _ { type_has_pointers(cx, ty) }
982 fn type_kind(cx: ctxt, ty: t) -> ast::kind {
983 alt cx.kind_cache.find(ty) {
984 some(result) { ret result; }
985 none. {/* fall through */ }
988 let result = ast::kind_unique;
990 // Insert a default in case we loop back on self recursively.
991 cx.kind_cache.insert(ty, result);
994 // Scalar types are unique-kind, no substructure.
995 ty_nil. | ty_bot. | ty_bool. | ty_int. | ty_uint. | ty_float. |
996 ty_machine(_) | ty_char. | ty_native(_) {
999 // A handful of other built-in are unique too.
1000 ty_type. | ty_str. | ty_native_fn(_, _, _) {
1003 // FIXME: obj is broken for now, since we aren't asserting
1004 // anything about its fields.
1006 result = kind_shared;
1008 // FIXME: the environment capture mode is not fully encoded
1009 // here yet, leading to weirdness around closure.
1010 ty_fn(proto, _, _, _, _) {
1011 result = alt proto {
1012 ast::proto_block. { ast::kind_pinned }
1013 ast::proto_closure. { ast::kind_shared }
1014 _ { ast::kind_unique }
1017 // Those with refcounts-to-inner raise pinned to shared,
1018 // lower unique to shared. Therefore just set result to shared.
1020 result = ast::kind_shared;
1022 // Pointers raise pinned to shared.
1024 let k = type_kind(cx, tm.ty);
1025 if k == ast::kind_pinned { k = ast::kind_shared; }
1026 result = kind::lower_kind(result, k);
1028 // Unique containers pass through their pointee kind.
1029 ty_vec(tm) | ty_uniq(tm) {
1030 let k = type_kind(cx, tm.ty);
1031 result = kind::lower_kind(result, k);
1033 // Records lower to the lowest of their members.
1035 for f: field in flds {
1036 result = kind::lower_kind(result, type_kind(cx, f.mt.ty));
1037 if result == ast::kind_pinned { break; }
1040 // Tuples lower to the lowest of their members.
1043 result = kind::lower_kind(result, type_kind(cx, ty));
1044 if result == ast::kind_pinned { break; }
1047 // Tags lower to the lowest of their variants.
1049 let variants = tag_variants(cx, did);
1050 for variant: variant_info in variants {
1051 for aty: t in variant.args {
1052 // Perform any type parameter substitutions.
1053 let arg_ty = substitute_type_params(cx, tps, aty);
1054 result = kind::lower_kind(result, type_kind(cx, arg_ty));
1055 if result == ast::kind_pinned { break; }
1057 if result == ast::kind_pinned { break; }
1060 // Resources are always pinned.
1061 ty_res(did, inner, tps) {
1062 result = ast::kind_pinned;
1068 result = kind::lower_kind(result, k);
1071 result = type_kind(cx, t);
1074 cx.sess.bug("missed case: " + ty_to_str(cx, ty));
1078 cx.kind_cache.insert(ty, result);
1083 // FIXME: should we just return true for native types in
1085 fn type_is_native(cx: ctxt, ty: t) -> bool {
1086 alt struct(cx, ty) { ty_native(_) { ret true; } _ { ret false; } }
1089 fn type_structurally_contains(cx: ctxt, ty: t, test: fn(sty) -> bool) ->
1091 let sty = struct(cx, ty);
1092 if test(sty) { ret true; }
1095 for variant in tag_variants(cx, did) {
1096 for aty in variant.args {
1097 let sty = substitute_type_params(cx, tps, aty);
1098 if type_structurally_contains(cx, sty, test) { ret true; }
1104 for field in fields {
1105 if type_structurally_contains(cx, field.mt.ty, test) { ret true; }
1111 if type_structurally_contains(cx, tt, test) { ret true; }
1115 ty_res(_, sub, tps) {
1116 let sty = substitute_type_params(cx, tps, sub);
1117 ret type_structurally_contains(cx, sty, test);
1123 pure fn type_has_dynamic_size(cx: ctxt, ty: t) -> bool {
1125 /* type_structurally_contains can't be declared pure
1126 because it takes a function argument. But it should be
1127 referentially transparent, since a given type's size should
1128 never change once it's created.
1129 (It would be interesting to think about how to make such properties
1130 actually checkable. It seems to me like a lot of properties
1131 that the type context tracks about types should be immutable.)
1134 type_structurally_contains(cx, ty,
1135 fn (sty: sty) -> bool {
1137 ty_param(_, _) { true }
1144 // Returns true for types where a copy of a value can be distinguished from
1145 // the value itself. I.e. types with mutable content that's not shared through
1147 fn type_allows_implicit_copy(cx: ctxt, ty: t) -> bool {
1148 ret !type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1150 ty_param(_, _) { true }
1155 for field in fields {
1168 fn type_structurally_contains_uniques(cx: ctxt, ty: t) -> bool {
1169 ret type_structurally_contains(cx, ty, fn (sty: sty) -> bool {
1171 ty_uniq(_) { ret true; }
1179 fn type_is_integral(cx: ctxt, ty: t) -> bool {
1180 alt struct(cx, ty) {
1181 ty_int. { ret true; }
1182 ty_uint. { ret true; }
1185 ast::ty_i8. { ret true; }
1186 ast::ty_i16. { ret true; }
1187 ast::ty_i32. { ret true; }
1188 ast::ty_i64. { ret true; }
1189 ast::ty_u8. { ret true; }
1190 ast::ty_u16. { ret true; }
1191 ast::ty_u32. { ret true; }
1192 ast::ty_u64. { ret true; }
1196 ty_char. { ret true; }
1197 ty_bool. { ret true; }
1202 fn type_is_fp(cx: ctxt, ty: t) -> bool {
1203 alt struct(cx, ty) {
1206 ast::ty_f32. { ret true; }
1207 ast::ty_f64. { ret true; }
1211 ty_float. { ret true; }
1216 fn type_is_signed(cx: ctxt, ty: t) -> bool {
1217 alt struct(cx, ty) {
1218 ty_int. { ret true; }
1221 ast::ty_i8. { ret true; }
1222 ast::ty_i16. { ret true; }
1223 ast::ty_i32. { ret true; }
1224 ast::ty_i64. { ret true; }
1232 // Whether a type is Plain Old Data (i.e. can be safely memmoved).
1233 fn type_is_pod(cx: ctxt, ty: t) -> bool {
1235 alt struct(cx, ty) {
1237 ty_nil. | ty_bot. | ty_bool. | ty_int. | ty_float. | ty_uint. |
1238 ty_machine(_) | ty_char. | ty_type. | ty_native(_) | ty_ptr(_) {
1242 ty_str. | ty_box(_) | ty_uniq(_) | ty_vec(_) | ty_fn(_, _, _, _, _) |
1243 ty_native_fn(_, _, _) | ty_obj(_) {
1248 let variants = tag_variants(cx, did);
1249 for variant: variant_info in variants {
1250 let tup_ty = mk_tup(cx, variant.args);
1252 // Perform any type parameter substitutions.
1253 tup_ty = substitute_type_params(cx, tps, tup_ty);
1254 if !type_is_pod(cx, tup_ty) { result = false; }
1258 for f: field in flds {
1259 if !type_is_pod(cx, f.mt.ty) { result = false; }
1263 for elt in elts { if !type_is_pod(cx, elt) { result = false; } }
1265 ty_res(_, inner, tps) {
1266 result = type_is_pod(cx, substitute_type_params(cx, tps, inner));
1268 ty_constr(subt, _) { result = type_is_pod(cx, subt); }
1270 fail "ty_var in type_is_pod";
1272 ty_param(_, _) { result = false; }
1278 fn type_param(cx: ctxt, ty: t) -> option::t<uint> {
1279 alt struct(cx, ty) {
1280 ty_param(id, _) { ret some(id); }
1281 _ {/* fall through */ }
1286 // Returns a vec of all the type variables
1287 // occurring in t. It may contain duplicates.
1288 fn vars_in_type(cx: ctxt, ty: t) -> [int] {
1289 fn collect_var(cx: ctxt, vars: @mutable [int], ty: t) {
1290 alt struct(cx, ty) { ty_var(v) { *vars += [v]; } _ { } }
1292 let rslt: @mutable [int] = @mutable [];
1293 walk_ty(cx, bind collect_var(cx, rslt, _), ty);
1294 // Works because of a "convenient" bug that lets us
1295 // return a mutable vec as if it's immutable
1299 fn type_autoderef(cx: ctxt, t: ty::t) -> ty::t {
1302 alt struct(cx, t1) {
1303 ty::ty_box(mt) { t1 = mt.ty; }
1304 ty::ty_res(_, inner, tps) {
1305 t1 = substitute_type_params(cx, tps, inner);
1307 ty::ty_tag(did, tps) {
1308 let variants = tag_variants(cx, did);
1309 if vec::len(variants) != 1u || vec::len(variants[0].args) != 1u {
1312 t1 = substitute_type_params(cx, tps, variants[0].args[0]);
1320 // Type hashing. This function is private to this module (and slow); external
1321 // users should use `hash_ty()` instead.
1322 fn hash_type_structure(st: sty) -> uint {
1323 fn hash_uint(id: uint, n: uint) -> uint {
1328 fn hash_def(id: uint, did: ast::def_id) -> uint {
1330 h += h << 5u + (did.crate as uint);
1331 h += h << 5u + (did.node as uint);
1334 fn hash_subty(id: uint, subty: t) -> uint {
1336 h += h << 5u + hash_ty(subty);
1339 fn hash_type_constr(id: uint, c: @type_constr) -> uint {
1341 h += h << 5u + hash_def(h, c.node.id);
1342 ret hash_type_constr_args(h, c.node.args);
1344 fn hash_type_constr_args(id: uint, args: [@ty_constr_arg]) -> uint {
1346 for a: @ty_constr_arg in args {
1348 carg_base. { h += h << 5u; }
1351 fail "lit args not implemented yet";
1354 // FIXME: Not sure what to do here.
1362 fn hash_fn(id: uint, args: [arg], rty: t) -> uint {
1364 for a: arg in args { h += h << 5u + hash_ty(a.ty); }
1365 h += h << 5u + hash_ty(rty);
1370 ty_bool. { ret 1u; }
1372 ty_float. { ret 3u; }
1373 ty_uint. { ret 4u; }
1376 ast::ty_i8. { ret 5u; }
1377 ast::ty_i16. { ret 6u; }
1378 ast::ty_i32. { ret 7u; }
1379 ast::ty_i64. { ret 8u; }
1380 ast::ty_u8. { ret 9u; }
1381 ast::ty_u16. { ret 10u; }
1382 ast::ty_u32. { ret 11u; }
1383 ast::ty_u64. { ret 12u; }
1384 ast::ty_f32. { ret 13u; }
1385 ast::ty_f64. { ret 14u; }
1388 ty_char. { ret 15u; }
1389 ty_str. { ret 17u; }
1391 let h = hash_def(18u, did);
1392 for typ: t in tys { h += h << 5u + hash_ty(typ); }
1395 ty_box(mt) { ret hash_subty(19u, mt.ty); }
1396 ty_vec(mt) { ret hash_subty(21u, mt.ty); }
1399 for f: field in fields { h += h << 5u + hash_ty(f.mt.ty); }
1404 for tt in ts { h += h << 5u + hash_ty(tt); }
1409 ty_fn(_, args, rty, _, _) {
1410 ret hash_fn(27u, args, rty);
1412 ty_native_fn(_, args, rty) { ret hash_fn(28u, args, rty); }
1415 for m: method in methods { h += h << 5u + str::hash(m.ident); }
1418 ty_var(v) { ret hash_uint(30u, v as uint); }
1419 ty_param(pid, _) { ret hash_uint(31u, pid); }
1420 ty_type. { ret 32u; }
1421 ty_native(did) { ret hash_def(33u, did); }
1422 ty_bot. { ret 34u; }
1423 ty_ptr(mt) { ret hash_subty(35u, mt.ty); }
1424 ty_res(did, sub, tps) {
1425 let h = hash_subty(hash_def(18u, did), sub);
1426 for tp: t in tps { h += h << 5u + hash_ty(tp); }
1431 for c: @type_constr in cs { h += h << 5u + hash_type_constr(h, c); }
1434 ty_uniq(mt) { let h = 37u; h += h << 5u + hash_ty(mt.ty); ret h; }
1438 fn hash_type_info(st: sty, cname_opt: option::t<str>) -> uint {
1439 let h = hash_type_structure(st);
1441 none. {/* no-op */ }
1442 some(s) { h += h << 5u + str::hash(s); }
1447 fn hash_raw_ty(rt: @raw_t) -> uint { ret rt.hash; }
1449 fn hash_ty(typ: t) -> uint { ret typ; }
1452 // Type equality. This function is private to this module (and slow); external
1453 // users should use `eq_ty()` instead.
1454 fn eq_int(x: uint, y: uint) -> bool { ret x == y; }
1456 fn arg_eq<T>(eq: fn(T, T) -> bool, a: @sp_constr_arg<T>, b: @sp_constr_arg<T>)
1460 alt b.node { ast::carg_base. { ret true; } _ { ret false; } }
1462 ast::carg_ident(s) {
1463 alt b.node { ast::carg_ident(t) { ret eq(s, t); } _ { ret false; } }
1466 alt b.node { ast::carg_lit(m) { ret lit_eq(l, m); } _ { ret false; } }
1471 fn args_eq<T>(eq: fn(T, T) -> bool, a: [@sp_constr_arg<T>],
1472 b: [@sp_constr_arg<T>]) -> bool {
1474 for arg: @sp_constr_arg<T> in a {
1475 if !arg_eq(eq, arg, b[i]) { ret false; }
1481 fn constr_eq(c: @constr, d: @constr) -> bool {
1482 ret path_to_str(c.node.path) == path_to_str(d.node.path) &&
1484 args_eq(eq_int, c.node.args, d.node.args);
1487 fn constrs_eq(cs: [@constr], ds: [@constr]) -> bool {
1488 if vec::len(cs) != vec::len(ds) { ret false; }
1490 for c: @constr in cs { if !constr_eq(c, ds[i]) { ret false; } i += 1u; }
1494 // An expensive type equality function. This function is private to this
1496 fn eq_raw_ty(a: @raw_t, b: @raw_t) -> bool {
1497 // Check hashes (fast path).
1499 if a.hash != b.hash { ret false; }
1500 // Check canonical names.
1503 none. { alt b.cname { none. {/* ok */ } _ { ret false; } } }
1506 some(s_b) { if !str::eq(s_a, s_b) { ret false; } }
1511 // Check structures.
1513 ret a.struct == b.struct;
1517 // This is the equality function the public should use. It works as long as
1518 // the types are interned.
1519 fn eq_ty(a: t, b: t) -> bool { ret a == b; }
1523 fn node_id_to_ty_param_substs_opt_and_ty(cx: ctxt, id: ast::node_id) ->
1524 ty_param_substs_opt_and_ty {
1527 // Pull out the node type table.
1528 alt smallintmap::find(*cx.node_types, id as uint) {
1530 cx.sess.bug("node_id_to_ty_param_substs_opt_and_ty() called on " +
1531 "an untyped node (" + std::int::to_str(id, 10u) +
1534 some(tpot) { ret tpot; }
1538 fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
1539 ret node_id_to_ty_param_substs_opt_and_ty(cx, id).ty;
1542 fn node_id_to_type_params(cx: ctxt, id: ast::node_id) -> [t] {
1543 alt node_id_to_ty_param_substs_opt_and_ty(cx, id).substs {
1545 some(tps) { ret tps; }
1549 fn node_id_has_type_params(cx: ctxt, id: ast::node_id) -> bool {
1550 ret vec::len(node_id_to_type_params(cx, id)) > 0u;
1554 // Returns a type with type parameter substitutions performed if applicable.
1555 fn ty_param_substs_opt_and_ty_to_monotype(cx: ctxt,
1556 tpot: ty_param_substs_opt_and_ty) ->
1559 none. { ret tpot.ty; }
1560 some(tps) { ret substitute_type_params(cx, tps, tpot.ty); }
1565 // Returns the type of an annotation, with type parameter substitutions
1566 // performed if applicable.
1567 fn node_id_to_monotype(cx: ctxt, id: ast::node_id) -> t {
1568 let tpot = node_id_to_ty_param_substs_opt_and_ty(cx, id);
1569 ret ty_param_substs_opt_and_ty_to_monotype(cx, tpot);
1573 // Returns the number of distinct type parameters in the given type.
1574 fn count_ty_params(cx: ctxt, ty: t) -> uint {
1575 fn counter(cx: ctxt, param_indices: @mutable [uint], ty: t) {
1576 alt struct(cx, ty) {
1577 ty_param(param_idx, _) {
1579 for other_param_idx: uint in *param_indices {
1580 if param_idx == other_param_idx { seen = true; }
1582 if !seen { *param_indices += [param_idx]; }
1584 _ {/* fall through */ }
1587 let param_indices: @mutable [uint] = @mutable [];
1588 let f = bind counter(cx, param_indices, _);
1590 ret vec::len::<uint>(*param_indices);
1593 fn type_contains_vars(cx: ctxt, typ: t) -> bool {
1594 ret interner::get(*cx.ts, typ).has_vars;
1597 fn type_contains_params(cx: ctxt, typ: t) -> bool {
1598 ret interner::get(*cx.ts, typ).has_params;
1602 // Type accessors for substructures of types
1603 fn ty_fn_args(cx: ctxt, fty: t) -> [arg] {
1604 alt struct(cx, fty) {
1605 ty::ty_fn(_, a, _, _, _) { ret a; }
1606 ty::ty_native_fn(_, a, _) { ret a; }
1607 _ { cx.sess.bug("ty_fn_args() called on non-fn type"); }
1611 fn ty_fn_proto(cx: ctxt, fty: t) -> ast::proto {
1612 alt struct(cx, fty) {
1613 ty::ty_fn(p, _, _, _, _) { ret p; }
1614 ty::ty_native_fn(_, _, _) { ret ast::proto_fn; }
1615 _ { cx.sess.bug("ty_fn_proto() called on non-fn type"); }
1619 fn ty_fn_abi(cx: ctxt, fty: t) -> ast::native_abi {
1620 alt struct(cx, fty) {
1621 ty::ty_native_fn(a, _, _) { ret a; }
1622 _ { cx.sess.bug("ty_fn_abi() called on non-native-fn type"); }
1626 pure fn ty_fn_ret(cx: ctxt, fty: t) -> t {
1627 // Should be pure, as type interner contents
1628 // shouldn't change once set...
1629 let sty = unchecked { struct(cx, fty) };
1631 ty::ty_fn(_, _, r, _, _) { ret r; }
1632 ty::ty_native_fn(_, _, r) { ret r; }
1634 // Unchecked is ok since we diverge here
1635 // (might want to change the typechecker to allow
1636 // it without an unchecked)
1637 // Or, it wouldn't be necessary if we had the right
1638 // typestate constraint on cx and t (then we could
1639 // call unreachable() instead)
1640 unchecked { cx.sess.bug("ty_fn_ret() called on non-fn type"); }}
1644 fn ty_fn_ret_style(cx: ctxt, fty: t) -> ast::ret_style {
1645 alt struct(cx, fty) {
1646 ty::ty_fn(_, _, _, rs, _) { rs }
1647 ty::ty_native_fn(_, _, _) { ast::return_val }
1648 _ { cx.sess.bug("ty_fn_ret_style() called on non-fn type"); }
1652 fn is_fn_ty(cx: ctxt, fty: t) -> bool {
1653 alt struct(cx, fty) {
1654 ty::ty_fn(_, _, _, _, _) { ret true; }
1655 ty::ty_native_fn(_, _, _) { ret true; }
1660 // Just checks whether it's a fn that returns bool,
1662 fn is_pred_ty(cx: ctxt, fty: t) -> bool {
1663 is_fn_ty(cx, fty) && type_is_bool(cx, ty_fn_ret(cx, fty))
1666 fn ty_var_id(cx: ctxt, typ: t) -> int {
1667 alt struct(cx, typ) {
1668 ty::ty_var(vid) { ret vid; }
1669 _ { log_err "ty_var_id called on non-var ty"; fail; }
1674 // Type accessors for AST nodes
1675 fn block_ty(cx: ctxt, b: ast::blk) -> t {
1676 ret node_id_to_type(cx, b.node.id);
1680 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
1681 // doesn't provide type parameter substitutions.
1682 fn pat_ty(cx: ctxt, pat: @ast::pat) -> t {
1683 ret node_id_to_monotype(cx, pat.id);
1687 // Returns the type of an expression as a monotype.
1689 // NB: This type doesn't provide type parameter substitutions; e.g. if you
1690 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
1691 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
1692 // expr_ty_params_and_ty() below.
1693 fn expr_ty(cx: ctxt, expr: @ast::expr) -> t {
1694 ret node_id_to_monotype(cx, expr.id);
1697 fn expr_ty_params_and_ty(cx: ctxt, expr: @ast::expr) -> {params: [t], ty: t} {
1698 ret {params: node_id_to_type_params(cx, expr.id),
1699 ty: node_id_to_type(cx, expr.id)};
1702 fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
1703 ret node_id_has_type_params(cx, expr.id);
1706 fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
1708 ast::stmt_decl(_, id) { ret id; }
1709 ast::stmt_expr(_, id) { ret id; }
1710 ast::stmt_crate_directive(_) {
1711 log_err "ty::stmt_node_id(): crate directive found";
1717 fn field_idx(sess: session::session, sp: span, id: ast::ident,
1718 fields: [field]) -> uint {
1720 for f: field in fields { if str::eq(f.ident, id) { ret i; } i += 1u; }
1721 sess.span_fatal(sp, "unknown field '" + id + "' of record");
1724 fn get_field(tcx: ctxt, rec_ty: t, id: ast::ident) -> field {
1725 alt struct(tcx, rec_ty) {
1727 alt vec::find({|f| str::eq(f.ident, id) }, fields) {
1734 fn method_idx(sess: session::session, sp: span, id: ast::ident,
1735 meths: [method]) -> uint {
1737 for m: method in meths { if str::eq(m.ident, id) { ret i; } i += 1u; }
1738 sess.span_fatal(sp, "unknown method '" + id + "' of obj");
1741 fn sort_methods(meths: [method]) -> [method] {
1742 fn method_lteq(a: method, b: method) -> bool {
1743 ret str::lteq(a.ident, b.ident);
1745 ret std::sort::merge_sort::<method>(bind method_lteq(_, _), meths);
1748 fn occurs_check_fails(tcx: ctxt, sp: option::t<span>, vid: int, rt: t) ->
1750 if !type_contains_vars(tcx, rt) {
1756 if vec::member(vid, vars_in_type(tcx, rt)) {
1759 // Maybe this should be span_err -- however, there's an
1760 // assertion later on that the type doesn't contain
1761 // variables, so in this case we have to be sure to die.
1763 (s, "Type inference failed because I \
1764 could not find a type\n that's both of the form "
1765 + ty_to_str(tcx, ty::mk_var(tcx, vid)) +
1766 " and of the form " + ty_to_str(tcx, rt) +
1767 ". Such a type would have to be infinitely large.");
1771 } else { ret false; }
1774 // Type unification via Robinson's algorithm (Robinson 1965). Implemented as
1775 // described in Hoder and Voronkov:
1777 // http://www.cs.man.ac.uk/~hoderk/ubench/unification_full.pdf
1780 export fixup_result;
1784 export mk_var_bindings;
1785 export resolve_type_structure;
1786 export resolve_type_var;
1791 export var_bindings;
1793 tag result { ures_ok(t); ures_err(type_err); }
1794 tag union_result { unres_ok; unres_err(type_err); }
1796 fix_ok(t); // fixup succeeded
1797 fix_err(int); // fixup failed because a type variable was unresolved
1800 {sets: ufind::ufind, types: smallintmap::smallintmap<t>};
1802 type ctxt = {vb: @var_bindings, tcx: ty_ctxt};
1804 fn mk_var_bindings() -> @var_bindings {
1805 ret @{sets: ufind::make(), types: smallintmap::mk::<t>()};
1808 // Unifies two sets.
1809 fn union(cx: @ctxt, set_a: uint, set_b: uint) -> union_result {
1810 ufind::grow(cx.vb.sets, uint::max(set_a, set_b) + 1u);
1811 let root_a = ufind::find(cx.vb.sets, set_a);
1812 let root_b = ufind::find(cx.vb.sets, set_b);
1815 bind fn (cx: @ctxt, t: t, set_a: uint, set_b: uint) {
1816 ufind::union(cx.vb.sets, set_a, set_b);
1817 let root_c: uint = ufind::find(cx.vb.sets, set_a);
1818 smallintmap::insert::<t>(cx.vb.types, root_c, t);
1819 }(_, _, set_a, set_b);
1822 alt smallintmap::find(cx.vb.types, root_a) {
1824 alt smallintmap::find(cx.vb.types, root_b) {
1825 none. { ufind::union(cx.vb.sets, set_a, set_b); ret unres_ok; }
1826 some(t_b) { replace_type(cx, t_b); ret unres_ok; }
1830 alt smallintmap::find(cx.vb.types, root_b) {
1831 none. { replace_type(cx, t_a); ret unres_ok; }
1833 alt unify_step(cx, t_a, t_b) {
1834 ures_ok(t_c) { replace_type(cx, t_c); ret unres_ok; }
1835 ures_err(terr) { ret unres_err(terr); }
1842 fn record_var_binding(cx: @ctxt, key: int, typ: t) -> result {
1843 ufind::grow(cx.vb.sets, (key as uint) + 1u);
1844 let root = ufind::find(cx.vb.sets, key as uint);
1845 let result_type = typ;
1846 alt smallintmap::find::<t>(cx.vb.types, root) {
1848 alt unify_step(cx, old_type, typ) {
1849 ures_ok(unified_type) { result_type = unified_type; }
1853 none. {/* fall through */ }
1855 smallintmap::insert::<t>(cx.vb.types, root, result_type);
1859 // Wraps the given type in an appropriate cname.
1861 // TODO: This doesn't do anything yet. We should carry the cname up from
1862 // the expected and/or actual types when unification results in a type
1863 // identical to one or both of the two. The precise algorithm for this is
1864 // something we'll probably need to develop over time.
1866 // Simple structural type comparison.
1867 fn struct_cmp(cx: @ctxt, expected: t, actual: t) -> result {
1868 if struct(cx.tcx, expected) == struct(cx.tcx, actual) {
1869 ret ures_ok(expected);
1871 ret ures_err(terr_mismatch);
1874 // Right now this just checks that the lists of constraints are
1876 fn unify_constrs(base_t: t, expected: [@type_constr],
1877 actual: [@type_constr]) -> result {
1878 let expected_len = vec::len(expected);
1879 let actual_len = vec::len(actual);
1881 if expected_len != actual_len {
1882 ret ures_err(terr_constr_len(expected_len, actual_len));
1886 for c: @type_constr in expected {
1887 rslt = unify_constr(base_t, c, actual[i]);
1888 alt rslt { ures_ok(_) { } ures_err(_) { ret rslt; } }
1891 ret ures_ok(base_t);
1893 fn unify_constr(base_t: t, expected: @type_constr,
1894 actual_constr: @type_constr) -> result {
1895 let ok_res = ures_ok(base_t);
1896 let err_res = ures_err(terr_constr_mismatch(expected, actual_constr));
1897 if expected.node.id != actual_constr.node.id { ret err_res; }
1898 let expected_arg_len = vec::len(expected.node.args);
1899 let actual_arg_len = vec::len(actual_constr.node.args);
1900 if expected_arg_len != actual_arg_len { ret err_res; }
1903 for a: @ty_constr_arg in expected.node.args {
1904 actual = actual_constr.node.args[i];
1907 alt actual.node { carg_base. { } _ { ret err_res; } }
1911 carg_lit(m) { if l != m { ret err_res; } }
1917 carg_ident(q) { if p.node != q.node { ret err_res; } }
1927 // Unifies two mutability flags.
1928 fn unify_mut(expected: ast::mutability, actual: ast::mutability) ->
1929 option::t<ast::mutability> {
1930 if expected == actual { ret some(expected); }
1931 if expected == ast::maybe_mut { ret some(actual); }
1932 if actual == ast::maybe_mut { ret some(expected); }
1936 fn_common_res_err(result);
1937 fn_common_res_ok([arg], t);
1939 fn unify_fn_common(cx: @ctxt, _expected: t, _actual: t,
1940 expected_inputs: [arg], expected_output: t,
1941 actual_inputs: [arg], actual_output: t) ->
1943 let expected_len = vec::len::<arg>(expected_inputs);
1944 let actual_len = vec::len::<arg>(actual_inputs);
1945 if expected_len != actual_len {
1946 ret fn_common_res_err(ures_err(terr_arg_count));
1948 // TODO: as above, we should have an iter2 iterator.
1950 let result_ins: [arg] = [];
1952 while i < expected_len {
1953 let expected_input = expected_inputs[i];
1954 let actual_input = actual_inputs[i];
1955 // Unify the result modes.
1958 if expected_input.mode != actual_input.mode {
1959 ret fn_common_res_err
1960 (ures_err(terr_mode_mismatch(expected_input.mode,
1961 actual_input.mode)));
1962 } else { result_mode = expected_input.mode; }
1963 let result = unify_step(cx, expected_input.ty, actual_input.ty);
1965 ures_ok(rty) { result_ins += [{mode: result_mode, ty: rty}]; }
1966 _ { ret fn_common_res_err(result); }
1970 // Check the output.
1972 let result = unify_step(cx, expected_output, actual_output);
1974 ures_ok(rty) { ret fn_common_res_ok(result_ins, rty); }
1975 _ { ret fn_common_res_err(result); }
1978 fn unify_fn(cx: @ctxt, e_proto: ast::proto, a_proto: ast::proto,
1979 expected: t, actual: t, expected_inputs: [arg],
1980 expected_output: t, actual_inputs: [arg], actual_output: t,
1981 expected_cf: ret_style, actual_cf: ret_style,
1982 _expected_constrs: [@constr], actual_constrs: [@constr]) ->
1984 if e_proto != a_proto { ret ures_err(terr_mismatch); }
1985 if actual_cf != ast::noreturn && actual_cf != expected_cf {
1986 /* even though typestate checking is mostly
1987 responsible for checking control flow annotations,
1988 this check is necessary to ensure that the
1989 annotation in an object method matches the
1990 declared object type */
1991 ret ures_err(terr_ret_style_mismatch(expected_cf, actual_cf));
1994 unify_fn_common(cx, expected, actual, expected_inputs,
1995 expected_output, actual_inputs, actual_output);
1997 fn_common_res_err(r) { ret r; }
1998 fn_common_res_ok(result_ins, result_out) {
2000 mk_fn(cx.tcx, e_proto, result_ins, result_out, actual_cf,
2006 fn unify_native_fn(cx: @ctxt, e_abi: ast::native_abi,
2007 a_abi: ast::native_abi, expected: t, actual: t,
2008 expected_inputs: [arg], expected_output: t,
2009 actual_inputs: [arg], actual_output: t) -> result {
2010 if e_abi != a_abi { ret ures_err(terr_mismatch); }
2012 unify_fn_common(cx, expected, actual, expected_inputs,
2013 expected_output, actual_inputs, actual_output);
2015 fn_common_res_err(r) { ret r; }
2016 fn_common_res_ok(result_ins, result_out) {
2017 let t2 = mk_native_fn(cx.tcx, e_abi, result_ins, result_out);
2022 fn unify_obj(cx: @ctxt, expected: t, actual: t, expected_meths: [method],
2023 actual_meths: [method]) -> result {
2024 let result_meths: [method] = [];
2026 let expected_len: uint = vec::len::<method>(expected_meths);
2027 let actual_len: uint = vec::len::<method>(actual_meths);
2028 if expected_len != actual_len { ret ures_err(terr_meth_count); }
2029 while i < expected_len {
2030 let e_meth = expected_meths[i];
2031 let a_meth = actual_meths[i];
2032 if !str::eq(e_meth.ident, a_meth.ident) {
2033 ret ures_err(terr_obj_meths(e_meth.ident, a_meth.ident));
2036 unify_fn(cx, e_meth.proto, a_meth.proto, expected, actual,
2037 e_meth.inputs, e_meth.output, a_meth.inputs,
2038 a_meth.output, e_meth.cf, a_meth.cf, e_meth.constrs,
2042 alt struct(cx.tcx, tfn) {
2043 ty_fn(proto, ins, out, cf, constrs) {
2045 [{inputs: ins, output: out, cf: cf, constrs: constrs
2054 let t = mk_obj(cx.tcx, result_meths);
2058 // If the given type is a variable, returns the structure of that type.
2059 fn resolve_type_structure(tcx: ty_ctxt, vb: @var_bindings, typ: t) ->
2061 alt struct(tcx, typ) {
2063 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2064 let root_id = ufind::find(vb.sets, vid as uint);
2065 alt smallintmap::find::<t>(vb.types, root_id) {
2066 none. { ret fix_err(vid); }
2067 some(rt) { ret fix_ok(rt); }
2070 _ { ret fix_ok(typ); }
2073 fn unify_step(cx: @ctxt, expected: t, actual: t) -> result {
2074 // TODO: rewrite this using tuple pattern matching when available, to
2075 // avoid all this rightward drift and spikiness.
2079 if eq_ty(expected, actual) { ret ures_ok(expected); }
2080 // Stage 1: Handle the cases in which one side or another is a type
2083 alt struct(cx.tcx, actual) {
2084 // If the RHS is a variable type, then just do the
2085 // appropriate binding.
2086 ty::ty_var(actual_id) {
2087 let actual_n = actual_id as uint;
2088 alt struct(cx.tcx, expected) {
2089 ty::ty_var(expected_id) {
2090 let expected_n = expected_id as uint;
2091 alt union(cx, expected_n, actual_n) {
2092 unres_ok. {/* fall through */ }
2093 unres_err(t_e) { ret ures_err(t_e); }
2097 // Just bind the type variable to the expected type.
2098 alt record_var_binding(cx, actual_id, expected) {
2099 ures_ok(_) {/* fall through */ }
2104 ret ures_ok(mk_var(cx.tcx, actual_id));
2108 alt struct(cx.tcx, expected) {
2109 ty::ty_var(expected_id) {
2110 // Add a binding. (`actual` can't actually be a var here.)
2112 alt record_var_binding(cx, expected_id, actual) {
2113 ures_ok(_) {/* fall through */ }
2116 ret ures_ok(mk_var(cx.tcx, expected_id));
2118 _ {/* fall through */ }
2120 // Stage 2: Handle all other cases.
2122 alt struct(cx.tcx, actual) {
2123 ty::ty_bot. { ret ures_ok(expected); }
2124 _ {/* fall through */ }
2126 alt struct(cx.tcx, expected) {
2127 ty::ty_nil. { ret struct_cmp(cx, expected, actual); }
2128 // _|_ unifies with anything
2130 ret ures_ok(actual);
2132 ty::ty_bool. { ret struct_cmp(cx, expected, actual); }
2133 ty::ty_int. { ret struct_cmp(cx, expected, actual); }
2134 ty::ty_uint. { ret struct_cmp(cx, expected, actual); }
2135 ty::ty_machine(_) { ret struct_cmp(cx, expected, actual); }
2136 ty::ty_float. { ret struct_cmp(cx, expected, actual); }
2137 ty::ty_char. { ret struct_cmp(cx, expected, actual); }
2138 ty::ty_str. { ret struct_cmp(cx, expected, actual); }
2139 ty::ty_type. { ret struct_cmp(cx, expected, actual); }
2140 ty::ty_native(ex_id) {
2141 alt struct(cx.tcx, actual) {
2143 if ex_id.crate == act_id.crate && ex_id.node == act_id.node {
2144 ret ures_ok(actual);
2145 } else { ret ures_err(terr_mismatch); }
2147 _ { ret ures_err(terr_mismatch); }
2150 ty::ty_param(_, _) { ret struct_cmp(cx, expected, actual); }
2151 ty::ty_tag(expected_id, expected_tps) {
2152 alt struct(cx.tcx, actual) {
2153 ty::ty_tag(actual_id, actual_tps) {
2154 if expected_id.crate != actual_id.crate ||
2155 expected_id.node != actual_id.node {
2156 ret ures_err(terr_mismatch);
2158 // TODO: factor this cruft out
2159 let result_tps: [t] = [];
2161 let expected_len = vec::len::<t>(expected_tps);
2162 while i < expected_len {
2163 let expected_tp = expected_tps[i];
2164 let actual_tp = actual_tps[i];
2165 let result = unify_step(cx, expected_tp, actual_tp);
2167 ures_ok(rty) { result_tps += [rty]; }
2172 ret ures_ok(mk_tag(cx.tcx, expected_id, result_tps));
2174 _ {/* fall through */ }
2176 ret ures_err(terr_mismatch);
2178 ty::ty_box(expected_mt) {
2179 alt struct(cx.tcx, actual) {
2180 ty::ty_box(actual_mt) {
2182 alt unify_mut(expected_mt.mut, actual_mt.mut) {
2183 none. { ret ures_err(terr_box_mutability); }
2184 some(m) { mut = m; }
2186 let result = unify_step(cx, expected_mt.ty, actual_mt.ty);
2188 ures_ok(result_sub) {
2189 let mt = {ty: result_sub, mut: mut};
2190 ret ures_ok(mk_box(cx.tcx, mt));
2195 _ { ret ures_err(terr_mismatch); }
2198 ty::ty_uniq(expected_mt) {
2199 alt struct(cx.tcx, actual) {
2200 ty::ty_uniq(actual_mt) {
2201 let mut = expected_mt.mut;
2202 alt unify_mut(expected_mt.mut, actual_mt.mut) {
2203 none. { ret ures_err(terr_box_mutability); }
2204 some(m) { mut = m; }
2206 let result = unify_step(cx, expected_mt.ty, actual_mt.ty);
2208 ures_ok(result_mt) {
2209 let mt = {ty: result_mt, mut: mut};
2210 ret ures_ok(mk_uniq(cx.tcx, mt));
2215 _ { ret ures_err(terr_mismatch); }
2218 ty::ty_vec(expected_mt) {
2219 alt struct(cx.tcx, actual) {
2220 ty::ty_vec(actual_mt) {
2222 alt unify_mut(expected_mt.mut, actual_mt.mut) {
2223 none. { ret ures_err(terr_vec_mutability); }
2224 some(m) { mut = m; }
2226 let result = unify_step(cx, expected_mt.ty, actual_mt.ty);
2228 ures_ok(result_sub) {
2229 let mt = {ty: result_sub, mut: mut};
2230 ret ures_ok(mk_vec(cx.tcx, mt));
2235 _ { ret ures_err(terr_mismatch); }
2238 ty::ty_ptr(expected_mt) {
2239 alt struct(cx.tcx, actual) {
2240 ty::ty_ptr(actual_mt) {
2242 alt unify_mut(expected_mt.mut, actual_mt.mut) {
2243 none. { ret ures_err(terr_vec_mutability); }
2244 some(m) { mut = m; }
2246 let result = unify_step(cx, expected_mt.ty, actual_mt.ty);
2248 ures_ok(result_sub) {
2249 let mt = {ty: result_sub, mut: mut};
2250 ret ures_ok(mk_ptr(cx.tcx, mt));
2255 _ { ret ures_err(terr_mismatch); }
2258 ty::ty_res(ex_id, ex_inner, ex_tps) {
2259 alt struct(cx.tcx, actual) {
2260 ty::ty_res(act_id, act_inner, act_tps) {
2261 if ex_id.crate != act_id.crate || ex_id.node != act_id.node {
2262 ret ures_err(terr_mismatch);
2264 let result = unify_step(cx, ex_inner, act_inner);
2266 ures_ok(res_inner) {
2269 for ex_tp: t in ex_tps {
2270 let result = unify_step(cx, ex_tp, act_tps[i]);
2272 ures_ok(rty) { res_tps += [rty]; }
2277 ret ures_ok(mk_res(cx.tcx, act_id, res_inner, res_tps));
2282 _ { ret ures_err(terr_mismatch); }
2285 ty::ty_rec(expected_fields) {
2286 alt struct(cx.tcx, actual) {
2287 ty::ty_rec(actual_fields) {
2288 let expected_len = vec::len::<field>(expected_fields);
2289 let actual_len = vec::len::<field>(actual_fields);
2290 if expected_len != actual_len {
2291 let err = terr_record_size(expected_len, actual_len);
2294 // TODO: implement an iterator that can iterate over
2295 // two arrays simultaneously.
2297 let result_fields: [field] = [];
2299 while i < expected_len {
2300 let expected_field = expected_fields[i];
2301 let actual_field = actual_fields[i];
2303 alt unify_mut(expected_field.mt.mut, actual_field.mt.mut)
2305 none. { ret ures_err(terr_record_mutability); }
2306 some(m) { mut = m; }
2308 if !str::eq(expected_field.ident, actual_field.ident) {
2310 terr_record_fields(expected_field.ident,
2311 actual_field.ident);
2315 unify_step(cx, expected_field.mt.ty,
2316 actual_field.mt.ty);
2319 let mt = {ty: rty, mut: mut};
2320 result_fields += [{mt: mt with expected_field}];
2326 ret ures_ok(mk_rec(cx.tcx, result_fields));
2328 _ { ret ures_err(terr_mismatch); }
2331 ty::ty_tup(expected_elems) {
2332 alt struct(cx.tcx, actual) {
2333 ty::ty_tup(actual_elems) {
2334 let expected_len = vec::len(expected_elems);
2335 let actual_len = vec::len(actual_elems);
2336 if expected_len != actual_len {
2337 let err = terr_tuple_size(expected_len, actual_len);
2340 // TODO: implement an iterator that can iterate over
2341 // two arrays simultaneously.
2343 let result_elems = [];
2345 while i < expected_len {
2346 let expected_elem = expected_elems[i];
2347 let actual_elem = actual_elems[i];
2348 let result = unify_step(cx, expected_elem, actual_elem);
2350 ures_ok(rty) { result_elems += [rty]; }
2355 ret ures_ok(mk_tup(cx.tcx, result_elems));
2357 _ { ret ures_err(terr_mismatch); }
2360 ty::ty_fn(ep, expected_inputs, expected_output, expected_cf,
2362 alt struct(cx.tcx, actual) {
2363 ty::ty_fn(ap, actual_inputs, actual_output, actual_cf,
2365 ret unify_fn(cx, ep, ap, expected, actual, expected_inputs,
2366 expected_output, actual_inputs, actual_output,
2367 expected_cf, actual_cf, expected_constrs,
2370 _ { ret ures_err(terr_mismatch); }
2373 ty::ty_native_fn(e_abi, expected_inputs, expected_output) {
2374 alt struct(cx.tcx, actual) {
2375 ty::ty_native_fn(a_abi, actual_inputs, actual_output) {
2376 ret unify_native_fn(cx, e_abi, a_abi, expected, actual,
2377 expected_inputs, expected_output,
2378 actual_inputs, actual_output);
2380 _ { ret ures_err(terr_mismatch); }
2383 ty::ty_obj(expected_meths) {
2384 alt struct(cx.tcx, actual) {
2385 ty::ty_obj(actual_meths) {
2386 ret unify_obj(cx, expected, actual, expected_meths,
2389 _ { ret ures_err(terr_mismatch); }
2392 ty::ty_constr(expected_t, expected_constrs) {
2394 // unify the base types...
2395 alt struct(cx.tcx, actual) {
2396 ty::ty_constr(actual_t, actual_constrs) {
2397 let rslt = unify_step(cx, expected_t, actual_t);
2400 // FIXME: probably too restrictive --
2401 // requires the constraints to be
2402 // syntactically equal
2403 ret unify_constrs(expected, expected_constrs,
2410 // If the actual type is *not* a constrained type,
2411 // then we go ahead and just ignore the constraints on
2412 // the expected type. typestate handles the rest.
2413 ret unify_step(cx, expected_t, actual);
2419 fn unify(expected: t, actual: t, vb: @var_bindings, tcx: ty_ctxt) ->
2421 let cx = @{vb: vb, tcx: tcx};
2422 ret unify_step(cx, expected, actual);
2424 fn dump_var_bindings(tcx: ty_ctxt, vb: @var_bindings) {
2426 while i < vec::len::<ufind::node>(vb.sets.nodes) {
2429 while j < vec::len::<option::t<uint>>(vb.sets.nodes) {
2430 if ufind::find(vb.sets, j) == i { sets += #fmt[" %u", j]; }
2434 alt smallintmap::find::<t>(vb.types, i) {
2435 none. { typespec = ""; }
2436 some(typ) { typespec = " =" + ty_to_str(tcx, typ); }
2438 log_err #fmt["set %u:%s%s", i, typespec, sets];
2443 // Fixups and substitutions
2444 // Takes an optional span - complain about occurs check violations
2445 // iff the span is present (so that if we already know we're going
2446 // to error anyway, we don't complain)
2447 fn fixup_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2448 typ: t) -> fixup_result {
2449 fn subst_vars(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2450 unresolved: @mutable option::t<int>, vid: int) -> t {
2451 // Should really return a fixup_result instead of a t, but fold_ty
2452 // doesn't allow returning anything but a t.
2453 if vid as uint >= ufind::set_count(vb.sets) {
2454 *unresolved = some(vid);
2455 ret ty::mk_var(tcx, vid);
2457 let root_id = ufind::find(vb.sets, vid as uint);
2458 alt smallintmap::find::<t>(vb.types, root_id) {
2459 none. { *unresolved = some(vid); ret ty::mk_var(tcx, vid); }
2461 if occurs_check_fails(tcx, sp, vid, rt) {
2462 // Return the type unchanged, so we can error out
2467 fm_var(bind subst_vars(tcx, sp, vb, unresolved,
2472 let unresolved = @mutable none::<int>;
2474 fold_ty(tcx, fm_var(bind subst_vars(tcx, sp, vb, unresolved, _)),
2476 let ur = *unresolved;
2478 none. { ret fix_ok(rty); }
2479 some(var_id) { ret fix_err(var_id); }
2482 fn resolve_type_var(tcx: ty_ctxt, sp: option::t<span>, vb: @var_bindings,
2483 vid: int) -> fixup_result {
2484 if vid as uint >= ufind::set_count(vb.sets) { ret fix_err(vid); }
2485 let root_id = ufind::find(vb.sets, vid as uint);
2486 alt smallintmap::find::<t>(vb.types, root_id) {
2487 none. { ret fix_err(vid); }
2488 some(rt) { ret fixup_vars(tcx, sp, vb, rt); }
2493 fn type_err_to_str(err: ty::type_err) -> str {
2495 terr_mismatch. { ret "types differ"; }
2496 terr_ret_style_mismatch(expect, actual) {
2497 fn to_str(s: ast::ret_style) -> str {
2499 ast::noreturn. { "non-returning" }
2500 ast::return_val. { "return-by-value" }
2501 ast::return_ref(mut, arg) {
2502 #fmt("return-by-%sreference on arg %u",
2503 mut ? "mutable-" : "", arg)
2507 ret to_str(actual) + " function found where " + to_str(expect) +
2508 " function was expected";
2510 terr_box_mutability. { ret "boxed values differ in mutability"; }
2511 terr_vec_mutability. { ret "vectors differ in mutability"; }
2512 terr_tuple_size(e_sz, a_sz) {
2513 ret "expected a tuple with " + uint::to_str(e_sz, 10u) +
2514 " elements but found one with " + uint::to_str(a_sz, 10u) +
2517 terr_record_size(e_sz, a_sz) {
2518 ret "expected a record with " + uint::to_str(e_sz, 10u) +
2519 " fields but found one with " + uint::to_str(a_sz, 10u) +
2522 terr_record_mutability. { ret "record elements differ in mutability"; }
2523 terr_record_fields(e_fld, a_fld) {
2524 ret "expected a record with field '" + e_fld +
2525 "' but found one with field '" + a_fld + "'";
2527 terr_arg_count. { ret "incorrect number of function parameters"; }
2528 terr_meth_count. { ret "incorrect number of object methods"; }
2529 terr_obj_meths(e_meth, a_meth) {
2530 ret "expected an obj with method '" + e_meth +
2531 "' but found one with method '" + a_meth + "'";
2533 terr_mode_mismatch(e_mode, a_mode) {
2534 ret "expected argument mode " + mode_str_1(e_mode) + " but found " +
2537 terr_constr_len(e_len, a_len) {
2538 ret "Expected a type with " + uint::str(e_len) +
2539 " constraints, but found one with " + uint::str(a_len) +
2542 terr_constr_mismatch(e_constr, a_constr) {
2543 ret "Expected a type with constraint " + ty_constr_to_str(e_constr) +
2544 " but found one with constraint " +
2545 ty_constr_to_str(a_constr);
2551 // Converts type parameters in a type to type variables and returns the
2552 // resulting type along with a list of type variable IDs.
2553 fn bind_params_in_type(sp: span, cx: ctxt, next_ty_var: fn() -> int, typ: t,
2554 ty_param_count: uint) -> {ids: [int], ty: t} {
2555 let param_var_ids: @mutable [int] = @mutable [];
2557 while i < ty_param_count { *param_var_ids += [next_ty_var()]; i += 1u; }
2558 fn binder(sp: span, cx: ctxt, param_var_ids: @mutable [int],
2559 _next_ty_var: fn() -> int, index: uint, _kind: ast::kind) -> t {
2560 if index < vec::len(*param_var_ids) {
2561 ret mk_var(cx, param_var_ids[index]);
2563 cx.sess.span_fatal(sp, "Unbound type parameter in callee's type");
2568 fm_param(bind binder(sp, cx, param_var_ids, next_ty_var, _,
2570 ret {ids: *param_var_ids, ty: new_typ};
2574 // Replaces type parameters in the given type using the given list of
2576 fn substitute_type_params(cx: ctxt, substs: [ty::t], typ: t) -> t {
2577 if !type_contains_params(cx, typ) { ret typ; }
2578 fn substituter(_cx: ctxt, substs: @[ty::t], idx: uint, _kind: ast::kind)
2580 // FIXME: bounds check can fail
2583 ret fold_ty(cx, fm_param(bind substituter(cx, @substs, _, _)), typ);
2586 fn def_has_ty_params(def: ast::def) -> bool {
2588 ast::def_fn(_, _) { ret true; }
2589 ast::def_obj_field(_, _) { ret false; }
2590 ast::def_mod(_) { ret false; }
2591 ast::def_const(_) { ret false; }
2592 ast::def_arg(_, _) { ret false; }
2593 ast::def_local(_, _) { ret false; }
2594 ast::def_upvar(_, _, _) { ret false; }
2595 ast::def_variant(_, _) { ret true; }
2596 ast::def_ty(_) { ret false; }
2597 ast::def_ty_arg(_, _) { ret false; }
2598 ast::def_binding(_) { ret false; }
2599 ast::def_use(_) { ret false; }
2600 ast::def_native_ty(_) { ret false; }
2601 ast::def_native_fn(_) { ret true; }
2607 type variant_info = {args: [ty::t], ctor_ty: ty::t, id: ast::def_id};
2609 fn tag_variants(cx: ctxt, id: ast::def_id) -> [variant_info] {
2610 if ast::local_crate != id.crate { ret csearch::get_tag_variants(cx, id); }
2612 alt cx.items.find(id.node) {
2614 none. { cx.sess.bug("expected to find cached node_item") }
2617 ast_map::node_item(item) {
2619 ast::item_tag(variants, _) {
2620 let result: [variant_info] = [];
2621 for variant: ast::variant in variants {
2622 let ctor_ty = node_id_to_monotype(cx, variant.node.id);
2623 let arg_tys: [t] = [];
2624 if std::vec::len(variant.node.args) > 0u {
2625 for a: arg in ty_fn_args(cx, ctor_ty) {
2629 let did = variant.node.id;
2633 id: ast_util::local_def(did)}];
2643 // Returns information about the tag variant with the given ID:
2644 fn tag_variant_with_id(cx: ctxt, tag_id: ast::def_id, variant_id: ast::def_id)
2646 let variants = tag_variants(cx, tag_id);
2648 while i < vec::len::<variant_info>(variants) {
2649 let variant = variants[i];
2650 if def_eq(variant.id, variant_id) { ret variant; }
2653 cx.sess.bug("tag_variant_with_id(): no variant exists with that ID");
2657 // If the given item is in an external crate, looks up its type and adds it to
2658 // the type cache. Returns the type parameters and type.
2659 fn lookup_item_type(cx: ctxt, did: ast::def_id) -> ty_param_kinds_and_ty {
2660 if did.crate == ast::local_crate {
2661 // The item is in this crate. The caller should have added it to the
2662 // type cache already; we simply return it.
2664 ret cx.tcache.get(did);
2666 alt cx.tcache.find(did) {
2667 some(tpt) { ret tpt; }
2669 let tyt = csearch::get_type(cx, did);
2670 cx.tcache.insert(did, tyt);
2676 fn ret_ty_of_fn(cx: ctxt, id: ast::node_id) -> t {
2677 ty_fn_ret(cx, node_id_to_type(cx, id))
2680 fn is_binopable(cx: ctxt, ty: t, op: ast::binop) -> bool {
2682 const tycat_other: int = 0;
2683 const tycat_bool: int = 1;
2684 const tycat_int: int = 2;
2685 const tycat_float: int = 3;
2686 const tycat_str: int = 4;
2687 const tycat_vec: int = 5;
2688 const tycat_struct: int = 6;
2689 const tycat_bot: int = 7;
2691 const opcat_add: int = 0;
2692 const opcat_sub: int = 1;
2693 const opcat_mult: int = 2;
2694 const opcat_shift: int = 3;
2695 const opcat_rel: int = 4;
2696 const opcat_eq: int = 5;
2697 const opcat_bit: int = 6;
2698 const opcat_logic: int = 7;
2700 fn opcat(op: ast::binop) -> int {
2702 ast::add. { opcat_add }
2703 ast::sub. { opcat_sub }
2704 ast::mul. { opcat_mult }
2705 ast::div. { opcat_mult }
2706 ast::rem. { opcat_mult }
2707 ast::and. { opcat_logic }
2708 ast::or. { opcat_logic }
2709 ast::bitxor. { opcat_bit }
2710 ast::bitand. { opcat_bit }
2711 ast::bitor. { opcat_bit }
2712 ast::lsl. { opcat_shift }
2713 ast::lsr. { opcat_shift }
2714 ast::asr. { opcat_shift }
2715 ast::eq. { opcat_eq }
2716 ast::ne. { opcat_eq }
2717 ast::lt. { opcat_rel }
2718 ast::le. { opcat_rel }
2719 ast::ge. { opcat_rel }
2720 ast::gt. { opcat_rel }
2724 fn tycat(cx: ctxt, ty: t) -> int {
2725 alt struct(cx, ty) {
2726 ty_bool. { tycat_bool }
2727 ty_int. { tycat_int }
2728 ty_uint. { tycat_int }
2729 ty_machine(ast::ty_i8.) { tycat_int }
2730 ty_machine(ast::ty_i16.) { tycat_int }
2731 ty_machine(ast::ty_i32.) { tycat_int }
2732 ty_machine(ast::ty_i64.) { tycat_int }
2733 ty_machine(ast::ty_u8.) { tycat_int }
2734 ty_machine(ast::ty_u16.) { tycat_int }
2735 ty_machine(ast::ty_u32.) { tycat_int }
2736 ty_machine(ast::ty_u64.) { tycat_int }
2737 ty_float. { tycat_float }
2738 ty_machine(ast::ty_f32.) { tycat_float }
2739 ty_machine(ast::ty_f64.) { tycat_float }
2740 ty_char. { tycat_int }
2741 ty_ptr(_) { tycat_int }
2742 ty_str. { tycat_str }
2743 ty_vec(_) { tycat_vec }
2744 ty_rec(_) { tycat_struct }
2745 ty_tup(_) { tycat_struct }
2746 ty_tag(_, _) { tycat_struct }
2747 ty_bot. { tycat_bot }
2752 const t: bool = true;
2753 const f: bool = false;
2766 [[f, f, f, f, t, t, f, f], [f, f, f, f, t, t, t, t],
2767 [t, t, t, t, t, t, t, f], [t, t, t, f, t, t, f, f],
2768 [t, f, f, f, t, t, f, f], [t, f, f, f, t, t, f, f],
2769 [f, f, f, f, t, t, f, f], [t, t, t, t, t, t, t, t]]; /*struct*/
2771 ret tbl[tycat(cx, ty)][opcat(op)];
2774 fn ast_constr_to_constr<T>(tcx: ty::ctxt, c: @ast::constr_general<T>) ->
2775 @ty::constr_general<T> {
2776 alt tcx.def_map.find(c.node.id) {
2777 some(ast::def_fn(pred_id, ast::pure_fn.)) {
2778 ret @ast_util::respan(c.span,
2784 tcx.sess.span_fatal(c.span,
2785 "Predicate " + path_to_str(c.node.path) +
2786 " is unbound or bound to a non-function or an \
2795 // indent-tabs-mode: nil
2796 // c-basic-offset: 4
2797 // buffer-file-coding-system: utf-8-unix
2798 // compile-command: "make -k -C $RBUILD 2>&1 | sed -e 's/\\/x\\//x:\\//g'";