src/librustc/middle/ty.rs

   1 // Copyright 2012-2013 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11
  12 use driver::session;
  13 use metadata::csearch;
  14 use metadata;
  15 use middle::const_eval;
  16 use middle::freevars;
  17 use middle::lint::{get_lint_level, allow};
  18 use middle::lint;
  19 use middle::resolve::{Impl, MethodInfo};
  20 use middle::resolve;
  21 use middle::ty;
  22 use middle::subst::Subst;
  23 use middle::typeck;
  24 use middle;
  25 use util::ppaux::{note_and_explain_region, bound_region_to_str};
  26 use util::ppaux::{trait_store_to_str, ty_to_str, vstore_to_str};
  27 use util::ppaux::Repr;
  28 use util::common::{indenter};
  29
  30 use core;
  31 use core::ptr::to_unsafe_ptr;
  32 use core::to_bytes;
  33 use core::hashmap::{HashMap, HashSet};
  34 use std::smallintmap::SmallIntMap;
  35 use syntax::ast::*;
  36 use syntax::ast_util::{is_local, local_def};
  37 use syntax::ast_util;
  38 use syntax::attr;
  39 use syntax::codemap::span;
  40 use syntax::codemap;
  41 use syntax::parse::token::special_idents;
  42 use syntax::{ast, ast_map};
  43 use syntax::opt_vec::OptVec;
  44 use syntax::opt_vec;
  45 use syntax::abi::AbiSet;
  46 use syntax;
  47
  48 // Data types
  49
  50 #[deriving(Eq, IterBytes)]
  51 pub struct arg {
  52     ty: t
  53 }
  54
  55 #[deriving(Eq)]
  56 pub struct field {
  57     ident: ast::ident,
  58     mt: mt
  59 }
  60
  61 pub type param_bounds = @~[param_bound];
  62
  63 pub struct method {
  64     ident: ast::ident,
  65     generics: ty::Generics,
  66     transformed_self_ty: Option<ty::t>,
  67     fty: BareFnTy,
  68     self_ty: ast::self_ty_,
  69     vis: ast::visibility,
  70     def_id: ast::def_id
  71 }
  72
  73 #[deriving(Eq)]
  74 pub struct mt {
  75     ty: t,
  76     mutbl: ast::mutability,
  77 }
  78
  79 #[auto_encode]
  80 #[auto_decode]
  81 #[deriving(Eq)]
  82 pub enum vstore {
  83     vstore_fixed(uint),
  84     vstore_uniq,
  85     vstore_box,
  86     vstore_slice(Region)
  87 }
  88
  89 #[auto_encode]
  90 #[auto_decode]
  91 #[deriving(Eq, IterBytes)]
  92 pub enum TraitStore {
  93     BoxTraitStore,              // @Trait
  94     UniqTraitStore,             // ~Trait
  95     RegionTraitStore(Region),   // &Trait
  96 }
  97
  98 // XXX: This should probably go away at some point. Maybe after destructors
  99 // do?
 100 #[auto_encode]
 101 #[auto_decode]
 102 #[deriving(Eq)]
 103 pub enum SelfMode {
 104     ByCopy,
 105     ByRef,
 106 }
 107
 108 pub struct field_ty {
 109   ident: ident,
 110   id: def_id,
 111   vis: ast::visibility,
 112   mutability: ast::struct_mutability,
 113 }
 114
 115 // Contains information needed to resolve types and (in the future) look up
 116 // the types of AST nodes.
 117 #[deriving(Eq)]
 118 pub struct creader_cache_key {
 119     cnum: int,
 120     pos: uint,
 121     len: uint
 122 }
 123
 124 type creader_cache = @mut HashMap<creader_cache_key, t>;
 125
 126 impl to_bytes::IterBytes for creader_cache_key {
 127     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 128         to_bytes::iter_bytes_3(&self.cnum, &self.pos, &self.len, lsb0, f);
 129     }
 130 }
 131
 132 struct intern_key {
 133     sty: *sty,
 134 }
 135
 136 // NB: Do not replace this with #[deriving(Eq)]. The automatically-derived
 137 // implementation will not recurse through sty and you will get stack
 138 // exhaustion.
 139 impl cmp::Eq for intern_key {
 140     fn eq(&self, other: &intern_key) -> bool {
 141         unsafe {
 142             *self.sty == *other.sty
 143         }
 144     }
 145     fn ne(&self, other: &intern_key) -> bool {
 146         !self.eq(other)
 147     }
 148 }
 149
 150 impl to_bytes::IterBytes for intern_key {
 151     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 152         unsafe {
 153             (*self.sty).iter_bytes(lsb0, f);
 154         }
 155     }
 156 }
 157
 158 pub enum ast_ty_to_ty_cache_entry {
 159     atttce_unresolved,  /* not resolved yet */
 160     atttce_resolved(t)  /* resolved to a type, irrespective of region */
 161 }
 162
 163 pub type opt_region_variance = Option<region_variance>;
 164
 165 #[auto_encode]
 166 #[auto_decode]
 167 #[deriving(Eq)]
 168 pub enum region_variance { rv_covariant, rv_invariant, rv_contravariant }
 169
 170 #[auto_encode]
 171 #[auto_decode]
 172 pub enum AutoAdjustment {
 173     AutoAddEnv(ty::Region, ast::Sigil),
 174     AutoDerefRef(AutoDerefRef)
 175 }
 176
 177 #[auto_encode]
 178 #[auto_decode]
 179 pub struct AutoDerefRef {
 180     autoderefs: uint,
 181     autoref: Option<AutoRef>
 182 }
 183
 184 #[auto_encode]
 185 #[auto_decode]
 186 pub struct AutoRef {
 187     kind: AutoRefKind,
 188     region: Region,
 189     mutbl: ast::mutability
 190 }
 191
 192 #[auto_encode]
 193 #[auto_decode]
 194 pub enum AutoRefKind {
 195     /// Convert from T to &T
 196     AutoPtr,
 197
 198     /// Convert from @[]/~[]/&[] to &[] (or str)
 199     AutoBorrowVec,
 200
 201     /// Convert from @[]/~[]/&[] to &&[] (or str)
 202     AutoBorrowVecRef,
 203
 204     /// Convert from @fn()/~fn()/&fn() to &fn()
 205     AutoBorrowFn
 206 }
 207
 208 // Stores information about provided methods (a.k.a. default methods) in
 209 // implementations.
 210 //
 211 // This is a map from ID of each implementation to the method info and trait
 212 // method ID of each of the default methods belonging to the trait that that
 213 // implementation implements.
 214 pub type ProvidedMethodsMap = @mut HashMap<def_id,@mut ~[@ProvidedMethodInfo]>;
 215
 216 // Stores the method info and definition ID of the associated trait method for
 217 // each instantiation of each provided method.
 218 pub struct ProvidedMethodInfo {
 219     method_info: @MethodInfo,
 220     trait_method_def_id: def_id
 221 }
 222
 223 pub struct ProvidedMethodSource {
 224     method_id: ast::def_id,
 225     impl_id: ast::def_id
 226 }
 227
 228 pub type ctxt = @ctxt_;
 229
 230 struct ctxt_ {
 231     diag: @syntax::diagnostic::span_handler,
 232     interner: @mut HashMap<intern_key, ~t_box_>,
 233     next_id: @mut uint,
 234     vecs_implicitly_copyable: bool,
 235     legacy_modes: bool,
 236     cstore: @mut metadata::cstore::CStore,
 237     sess: session::Session,
 238     def_map: resolve::DefMap,
 239
 240     region_maps: @mut middle::region::RegionMaps,
 241     region_paramd_items: middle::region::region_paramd_items,
 242
 243     // Stores the types for various nodes in the AST.  Note that this table
 244     // is not guaranteed to be populated until after typeck.  See
 245     // typeck::check::fn_ctxt for details.
 246     node_types: node_type_table,
 247
 248     // Stores the type parameters which were substituted to obtain the type
 249     // of this node.  This only applies to nodes that refer to entities
 250     // parameterized by type parameters, such as generic fns, types, or
 251     // other items.
 252     node_type_substs: @mut HashMap<node_id, ~[t]>,
 253
 254     // Maps from a method to the method "descriptor"
 255     methods: @mut HashMap<def_id, @method>,
 256
 257     // Maps from a trait def-id to a list of the def-ids of its methods
 258     trait_method_def_ids: @mut HashMap<def_id, @~[def_id]>,
 259
 260     // A cache for the trait_methods() routine
 261     trait_methods_cache: @mut HashMap<def_id, @~[@method]>,
 262
 263     trait_refs: @mut HashMap<node_id, @TraitRef>,
 264     trait_defs: @mut HashMap<def_id, @TraitDef>,
 265
 266     items: ast_map::map,
 267     intrinsic_defs: @mut HashMap<ast::ident, (ast::def_id, t)>,
 268     intrinsic_traits: @mut HashMap<ast::ident, @TraitRef>,
 269     freevars: freevars::freevar_map,
 270     tcache: type_cache,
 271     rcache: creader_cache,
 272     ccache: constness_cache,
 273     short_names_cache: @mut HashMap<t, @~str>,
 274     needs_unwind_cleanup_cache: @mut HashMap<t, bool>,
 275     tc_cache: @mut HashMap<uint, TypeContents>,
 276     ast_ty_to_ty_cache: @mut HashMap<node_id, ast_ty_to_ty_cache_entry>,
 277     enum_var_cache: @mut HashMap<def_id, @~[VariantInfo]>,
 278     ty_param_defs: @mut HashMap<ast::node_id, TypeParameterDef>,
 279     adjustments: @mut HashMap<ast::node_id, @AutoAdjustment>,
 280     normalized_cache: @mut HashMap<t, t>,
 281     lang_items: middle::lang_items::LanguageItems,
 282     // A mapping from an implementation ID to the method info and trait
 283     // method ID of the provided (a.k.a. default) methods in the traits that
 284     // that implementation implements.
 285     provided_methods: ProvidedMethodsMap,
 286     provided_method_sources: @mut HashMap<ast::def_id, ProvidedMethodSource>,
 287     supertraits: @mut HashMap<ast::def_id, @~[@TraitRef]>,
 288
 289     // A mapping from the def ID of an enum or struct type to the def ID
 290     // of the method that implements its destructor. If the type is not
 291     // present in this map, it does not have a destructor. This map is
 292     // populated during the coherence phase of typechecking.
 293     destructor_for_type: @mut HashMap<ast::def_id, ast::def_id>,
 294
 295     // A method will be in this list if and only if it is a destructor.
 296     destructors: @mut HashSet<ast::def_id>,
 297
 298     // Maps a trait onto a mapping from self-ty to impl
 299     trait_impls: @mut HashMap<ast::def_id, @mut HashMap<t, @Impl>>,
 300
 301     // Set of used unsafe nodes (functions or blocks). Unsafe nodes not
 302     // present in this set can be warned about.
 303     used_unsafe: @mut HashSet<ast::node_id>,
 304
 305     // Set of nodes which mark locals as mutable which end up getting used at
 306     // some point. Local variable definitions not in this set can be warned
 307     // about.
 308     used_mut_nodes: @mut HashSet<ast::node_id>,
 309 }
 310
 311 pub enum tbox_flag {
 312     has_params = 1,
 313     has_self = 2,
 314     needs_infer = 4,
 315     has_regions = 8,
 316     has_ty_err = 16,
 317     has_ty_bot = 32,
 318
 319     // a meta-flag: subst may be required if the type has parameters, a self
 320     // type, or references bound regions
 321     needs_subst = 1 | 2 | 8
 322 }
 323
 324 pub type t_box = &'static t_box_;
 325
 326 pub struct t_box_ {
 327     sty: sty,
 328     id: uint,
 329     flags: uint,
 330 }
 331
 332 // To reduce refcounting cost, we're representing types as unsafe pointers
 333 // throughout the compiler. These are simply casted t_box values. Use ty::get
 334 // to cast them back to a box. (Without the cast, compiler performance suffers
 335 // ~15%.) This does mean that a t value relies on the ctxt to keep its box
 336 // alive, and using ty::get is unsafe when the ctxt is no longer alive.
 337 enum t_opaque {}
 338 pub type t = *t_opaque;
 339
 340 pub fn get(t: t) -> t_box {
 341     unsafe {
 342         let t2: t_box = cast::transmute(t);
 343         t2
 344     }
 345 }
 346
 347 pub fn tbox_has_flag(tb: t_box, flag: tbox_flag) -> bool {
 348     (tb.flags & (flag as uint)) != 0u
 349 }
 350 pub fn type_has_params(t: t) -> bool {
 351     tbox_has_flag(get(t), has_params)
 352 }
 353 pub fn type_has_self(t: t) -> bool { tbox_has_flag(get(t), has_self) }
 354 pub fn type_needs_infer(t: t) -> bool {
 355     tbox_has_flag(get(t), needs_infer)
 356 }
 357 pub fn type_has_regions(t: t) -> bool {
 358     tbox_has_flag(get(t), has_regions)
 359 }
 360 pub fn type_id(t: t) -> uint { get(t).id }
 361
 362 #[deriving(Eq)]
 363 pub struct BareFnTy {
 364     purity: ast::purity,
 365     abis: AbiSet,
 366     sig: FnSig
 367 }
 368
 369 #[deriving(Eq)]
 370 pub struct ClosureTy {
 371     purity: ast::purity,
 372     sigil: ast::Sigil,
 373     onceness: ast::Onceness,
 374     region: Region,
 375     sig: FnSig
 376 }
 377
 378 /**
 379  * Signature of a function type, which I have arbitrarily
 380  * decided to use to refer to the input/output types.
 381  *
 382  * - `lifetimes` is the list of region names bound in this fn.
 383  * - `inputs` is the list of arguments and their modes.
 384  * - `output` is the return type. */
 385 #[deriving(Eq)]
 386 pub struct FnSig {
 387     bound_lifetime_names: OptVec<ast::ident>,
 388     inputs: ~[arg],
 389     output: t
 390 }
 391
 392 impl to_bytes::IterBytes for BareFnTy {
 393     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 394         to_bytes::iter_bytes_3(&self.purity, &self.abis, &self.sig, lsb0, f)
 395     }
 396 }
 397
 398 impl to_bytes::IterBytes for ClosureTy {
 399     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 400         to_bytes::iter_bytes_5(&self.purity, &self.sigil, &self.onceness,
 401                                &self.region, &self.sig, lsb0, f)
 402     }
 403 }
 404
 405 #[deriving(Eq, IterBytes)]
 406 pub struct param_ty {
 407     idx: uint,
 408     def_id: def_id
 409 }
 410
 411 /// Representation of regions:
 412 #[auto_encode]
 413 #[auto_decode]
 414 #[deriving(Eq, IterBytes)]
 415 pub enum Region {
 416     /// Bound regions are found (primarily) in function types.  They indicate
 417     /// region parameters that have yet to be replaced with actual regions
 418     /// (analogous to type parameters, except that due to the monomorphic
 419     /// nature of our type system, bound type parameters are always replaced
 420     /// with fresh type variables whenever an item is referenced, so type
 421     /// parameters only appear "free" in types.  Regions in contrast can
 422     /// appear free or bound.).  When a function is called, all bound regions
 423     /// tied to that function's node-id are replaced with fresh region
 424     /// variables whose value is then inferred.
 425     re_bound(bound_region),
 426
 427     /// When checking a function body, the types of all arguments and so forth
 428     /// that refer to bound region parameters are modified to refer to free
 429     /// region parameters.
 430     re_free(FreeRegion),
 431
 432     /// A concrete region naming some expression within the current function.
 433     re_scope(node_id),
 434
 435     /// Static data that has an "infinite" lifetime.
 436     re_static,
 437
 438     /// A region variable.  Should not exist after typeck.
 439     re_infer(InferRegion)
 440 }
 441
 442 pub impl Region {
 443     fn is_bound(&self) -> bool {
 444         match self {
 445             &re_bound(*) => true,
 446             _ => false
 447         }
 448     }
 449 }
 450
 451 #[auto_encode]
 452 #[auto_decode]
 453 #[deriving(Eq, IterBytes)]
 454 pub struct FreeRegion {
 455     scope_id: node_id,
 456     bound_region: bound_region
 457 }
 458
 459 #[auto_encode]
 460 #[auto_decode]
 461 #[deriving(Eq, IterBytes)]
 462 pub enum bound_region {
 463     /// The self region for structs, impls (&T in a type defn or &'self T)
 464     br_self,
 465
 466     /// An anonymous region parameter for a given fn (&T)
 467     br_anon(uint),
 468
 469     /// Named region parameters for functions (a in &'a T)
 470     br_named(ast::ident),
 471
 472     /// Fresh bound identifiers created during GLB computations.
 473     br_fresh(uint),
 474
 475     /**
 476      * Handles capture-avoiding substitution in a rather subtle case.  If you
 477      * have a closure whose argument types are being inferred based on the
 478      * expected type, and the expected type includes bound regions, then we
 479      * will wrap those bound regions in a br_cap_avoid() with the id of the
 480      * fn expression.  This ensures that the names are not "captured" by the
 481      * enclosing scope, which may define the same names.  For an example of
 482      * where this comes up, see src/test/compile-fail/regions-ret-borrowed.rs
 483      * and regions-ret-borrowed-1.rs. */
 484     br_cap_avoid(ast::node_id, @bound_region),
 485 }
 486
 487 type opt_region = Option<Region>;
 488
 489 /**
 490  * The type substs represents the kinds of things that can be substituted to
 491  * convert a polytype into a monotype.  Note however that substituting bound
 492  * regions other than `self` is done through a different mechanism:
 493  *
 494  * - `tps` represents the type parameters in scope.  They are indexed
 495  *   according to the order in which they were declared.
 496  *
 497  * - `self_r` indicates the region parameter `self` that is present on nominal
 498  *   types (enums, structs) declared as having a region parameter.  `self_r`
 499  *   should always be none for types that are not region-parameterized and
 500  *   Some(_) for types that are.  The only bound region parameter that should
 501  *   appear within a region-parameterized type is `self`.
 502  *
 503  * - `self_ty` is the type to which `self` should be remapped, if any.  The
 504  *   `self` type is rather funny in that it can only appear on traits and is
 505  *   always substituted away to the implementing type for a trait. */
 506 #[deriving(Eq)]
 507 pub struct substs {
 508     self_r: opt_region,
 509     self_ty: Option<ty::t>,
 510     tps: ~[t]
 511 }
 512
 513 mod primitives {
 514     use super::t_box_;
 515
 516     use syntax::ast;
 517
 518     macro_rules! def_prim_ty(
 519         ($name:ident, $sty:expr, $id:expr) => (
 520             pub static $name: t_box_ = t_box_ {
 521                 sty: $sty,
 522                 id: $id,
 523                 flags: 0,
 524             };
 525         )
 526     )
 527
 528     def_prim_ty!(TY_NIL,    super::ty_nil,                  0)
 529     def_prim_ty!(TY_BOOL,   super::ty_bool,                 1)
 530     def_prim_ty!(TY_INT,    super::ty_int(ast::ty_i),       2)
 531     def_prim_ty!(TY_CHAR,   super::ty_int(ast::ty_char),    3)
 532     def_prim_ty!(TY_I8,     super::ty_int(ast::ty_i8),      4)
 533     def_prim_ty!(TY_I16,    super::ty_int(ast::ty_i16),     5)
 534     def_prim_ty!(TY_I32,    super::ty_int(ast::ty_i32),     6)
 535     def_prim_ty!(TY_I64,    super::ty_int(ast::ty_i64),     7)
 536     def_prim_ty!(TY_UINT,   super::ty_uint(ast::ty_u),      8)
 537     def_prim_ty!(TY_U8,     super::ty_uint(ast::ty_u8),     9)
 538     def_prim_ty!(TY_U16,    super::ty_uint(ast::ty_u16),    10)
 539     def_prim_ty!(TY_U32,    super::ty_uint(ast::ty_u32),    11)
 540     def_prim_ty!(TY_U64,    super::ty_uint(ast::ty_u64),    12)
 541     def_prim_ty!(TY_FLOAT,  super::ty_float(ast::ty_f),     13)
 542     def_prim_ty!(TY_F32,    super::ty_float(ast::ty_f32),   14)
 543     def_prim_ty!(TY_F64,    super::ty_float(ast::ty_f64),   15)
 544
 545     pub static TY_BOT: t_box_ = t_box_ {
 546         sty: super::ty_bot,
 547         id: 16,
 548         flags: super::has_ty_bot as uint,
 549     };
 550
 551     pub static TY_ERR: t_box_ = t_box_ {
 552         sty: super::ty_err,
 553         id: 17,
 554         flags: super::has_ty_err as uint,
 555     };
 556
 557     pub static LAST_PRIMITIVE_ID: uint = 18;
 558 }
 559
 560 // NB: If you change this, you'll probably want to change the corresponding
 561 // AST structure in libsyntax/ast.rs as well.
 562 #[deriving(Eq)]
 563 pub enum sty {
 564     ty_nil,
 565     ty_bot,
 566     ty_bool,
 567     ty_int(ast::int_ty),
 568     ty_uint(ast::uint_ty),
 569     ty_float(ast::float_ty),
 570     ty_estr(vstore),
 571     ty_enum(def_id, substs),
 572     ty_box(mt),
 573     ty_uniq(mt),
 574     ty_evec(mt, vstore),
 575     ty_ptr(mt),
 576     ty_rptr(Region, mt),
 577     ty_bare_fn(BareFnTy),
 578     ty_closure(ClosureTy),
 579     ty_trait(def_id, substs, TraitStore, ast::mutability),
 580     ty_struct(def_id, substs),
 581     ty_tup(~[t]),
 582
 583     ty_param(param_ty), // type parameter
 584     ty_self(def_id), /* special, implicit `self` type parameter;
 585                       * def_id is the id of the trait */
 586
 587     ty_infer(InferTy), // something used only during inference/typeck
 588     ty_err, // Also only used during inference/typeck, to represent
 589             // the type of an erroneous expression (helps cut down
 590             // on non-useful type error messages)
 591
 592     // "Fake" types, used for trans purposes
 593     ty_type, // type_desc*
 594     ty_opaque_box, // used by monomorphizer to represent any @ box
 595     ty_opaque_closure_ptr(Sigil), // ptr to env for &fn, @fn, ~fn
 596     ty_unboxed_vec(mt),
 597 }
 598
 599 #[deriving(Eq, IterBytes)]
 600 pub struct TraitRef {
 601     def_id: def_id,
 602     substs: substs
 603 }
 604
 605 #[deriving(Eq)]
 606 pub enum IntVarValue {
 607     IntType(ast::int_ty),
 608     UintType(ast::uint_ty),
 609 }
 610
 611 pub enum terr_vstore_kind {
 612     terr_vec, terr_str, terr_fn, terr_trait
 613 }
 614
 615 pub struct expected_found<T> {
 616     expected: T,
 617     found: T
 618 }
 619
 620 // Data structures used in type unification
 621 pub enum type_err {
 622     terr_mismatch,
 623     terr_purity_mismatch(expected_found<purity>),
 624     terr_onceness_mismatch(expected_found<Onceness>),
 625     terr_abi_mismatch(expected_found<AbiSet>),
 626     terr_mutability,
 627     terr_sigil_mismatch(expected_found<ast::Sigil>),
 628     terr_box_mutability,
 629     terr_ptr_mutability,
 630     terr_ref_mutability,
 631     terr_vec_mutability,
 632     terr_tuple_size(expected_found<uint>),
 633     terr_ty_param_size(expected_found<uint>),
 634     terr_record_size(expected_found<uint>),
 635     terr_record_mutability,
 636     terr_record_fields(expected_found<ident>),
 637     terr_arg_count,
 638     terr_regions_does_not_outlive(Region, Region),
 639     terr_regions_not_same(Region, Region),
 640     terr_regions_no_overlap(Region, Region),
 641     terr_regions_insufficiently_polymorphic(bound_region, Region),
 642     terr_regions_overly_polymorphic(bound_region, Region),
 643     terr_vstores_differ(terr_vstore_kind, expected_found<vstore>),
 644     terr_trait_stores_differ(terr_vstore_kind, expected_found<TraitStore>),
 645     terr_in_field(@type_err, ast::ident),
 646     terr_sorts(expected_found<t>),
 647     terr_self_substs,
 648     terr_integer_as_char,
 649     terr_int_mismatch(expected_found<IntVarValue>),
 650     terr_float_mismatch(expected_found<ast::float_ty>),
 651     terr_traits(expected_found<ast::def_id>),
 652 }
 653
 654 #[deriving(Eq, IterBytes)]
 655 pub enum param_bound {
 656     bound_copy,
 657     bound_durable,
 658     bound_owned,
 659     bound_const,
 660     bound_trait(@TraitRef),
 661 }
 662
 663 #[deriving(Eq)]
 664 pub struct TyVid(uint);
 665
 666 #[deriving(Eq)]
 667 pub struct IntVid(uint);
 668
 669 #[deriving(Eq)]
 670 pub struct FloatVid(uint);
 671
 672 #[deriving(Eq)]
 673 #[auto_encode]
 674 #[auto_decode]
 675 pub struct RegionVid {
 676     id: uint
 677 }
 678
 679 #[deriving(Eq)]
 680 pub enum InferTy {
 681     TyVar(TyVid),
 682     IntVar(IntVid),
 683     FloatVar(FloatVid)
 684 }
 685
 686 impl to_bytes::IterBytes for InferTy {
 687     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 688         match *self {
 689           TyVar(ref tv) => to_bytes::iter_bytes_2(&0u8, tv, lsb0, f),
 690           IntVar(ref iv) => to_bytes::iter_bytes_2(&1u8, iv, lsb0, f),
 691           FloatVar(ref fv) => to_bytes::iter_bytes_2(&2u8, fv, lsb0, f),
 692         }
 693     }
 694 }
 695
 696 #[auto_encode]
 697 #[auto_decode]
 698 pub enum InferRegion {
 699     ReVar(RegionVid),
 700     ReSkolemized(uint, bound_region)
 701 }
 702
 703 impl to_bytes::IterBytes for InferRegion {
 704     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 705         match *self {
 706             ReVar(ref rv) => to_bytes::iter_bytes_2(&0u8, rv, lsb0, f),
 707             ReSkolemized(ref v, _) => to_bytes::iter_bytes_2(&1u8, v, lsb0, f)
 708         }
 709     }
 710 }
 711
 712 impl cmp::Eq for InferRegion {
 713     fn eq(&self, other: &InferRegion) -> bool {
 714         match ((*self), *other) {
 715             (ReVar(rva), ReVar(rvb)) => {
 716                 rva == rvb
 717             }
 718             (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
 719                 rva == rvb
 720             }
 721             _ => false
 722         }
 723     }
 724     fn ne(&self, other: &InferRegion) -> bool {
 725         !((*self) == (*other))
 726     }
 727 }
 728
 729 pub trait Vid {
 730     fn to_uint(&self) -> uint;
 731 }
 732
 733 impl Vid for TyVid {
 734     fn to_uint(&self) -> uint { **self }
 735 }
 736
 737 impl ToStr for TyVid {
 738     fn to_str(&self) -> ~str { fmt!("<V%u>", self.to_uint()) }
 739 }
 740
 741 impl Vid for IntVid {
 742     fn to_uint(&self) -> uint { **self }
 743 }
 744
 745 impl ToStr for IntVid {
 746     fn to_str(&self) -> ~str { fmt!("<VI%u>", self.to_uint()) }
 747 }
 748
 749 impl Vid for FloatVid {
 750     fn to_uint(&self) -> uint { **self }
 751 }
 752
 753 impl ToStr for FloatVid {
 754     fn to_str(&self) -> ~str { fmt!("<VF%u>", self.to_uint()) }
 755 }
 756
 757 impl Vid for RegionVid {
 758     fn to_uint(&self) -> uint { self.id }
 759 }
 760
 761 impl ToStr for RegionVid {
 762     fn to_str(&self) -> ~str { fmt!("%?", self.id) }
 763 }
 764
 765 impl ToStr for FnSig {
 766     fn to_str(&self) -> ~str {
 767         // grr, without tcx not much we can do.
 768         return ~"(...)";
 769     }
 770 }
 771
 772 impl ToStr for InferTy {
 773     fn to_str(&self) -> ~str {
 774         match *self {
 775             TyVar(ref v) => v.to_str(),
 776             IntVar(ref v) => v.to_str(),
 777             FloatVar(ref v) => v.to_str()
 778         }
 779     }
 780 }
 781
 782 impl ToStr for IntVarValue {
 783     fn to_str(&self) -> ~str {
 784         match *self {
 785             IntType(ref v) => v.to_str(),
 786             UintType(ref v) => v.to_str(),
 787         }
 788     }
 789 }
 790
 791 impl to_bytes::IterBytes for TyVid {
 792     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 793         self.to_uint().iter_bytes(lsb0, f)
 794     }
 795 }
 796
 797 impl to_bytes::IterBytes for IntVid {
 798     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 799         self.to_uint().iter_bytes(lsb0, f)
 800     }
 801 }
 802
 803 impl to_bytes::IterBytes for FloatVid {
 804     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 805         self.to_uint().iter_bytes(lsb0, f)
 806     }
 807 }
 808
 809 impl to_bytes::IterBytes for RegionVid {
 810     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 811         self.to_uint().iter_bytes(lsb0, f)
 812     }
 813 }
 814
 815 pub struct TypeParameterDef {
 816     def_id: ast::def_id,
 817     bounds: param_bounds
 818 }
 819
 820 /// Information about the type/lifetime parametesr associated with an item.
 821 /// Analogous to ast::Generics.
 822 pub struct Generics {
 823     type_param_defs: @~[TypeParameterDef],
 824     region_param: Option<region_variance>,
 825 }
 826
 827 pub impl Generics {
 828     fn has_type_params(&self) -> bool {
 829         !self.type_param_defs.is_empty()
 830     }
 831 }
 832
 833 /// A polytype.
 834 ///
 835 /// - `bounds`: The list of bounds for each type parameter.  The length of the
 836 ///   list also tells you how many type parameters there are.
 837 ///
 838 /// - `rp`: true if the type is region-parameterized.  Types can have at
 839 ///   most one region parameter, always called `&self`.
 840 ///
 841 /// - `ty`: the base type.  May have reference to the (unsubstituted) bound
 842 ///   region `&self` or to (unsubstituted) ty_param types
 843 pub struct ty_param_bounds_and_ty {
 844     generics: Generics,
 845     ty: t
 846 }
 847
 848 /// As `ty_param_bounds_and_ty` but for a trait ref.
 849 pub struct TraitDef {
 850     generics: Generics,
 851     trait_ref: @ty::TraitRef,
 852 }
 853
 854 pub struct ty_param_substs_and_ty {
 855     substs: ty::substs,
 856     ty: ty::t
 857 }
 858
 859 type type_cache = @mut HashMap<ast::def_id, ty_param_bounds_and_ty>;
 860
 861 type constness_cache = @mut HashMap<ast::def_id, const_eval::constness>;
 862
 863 pub type node_type_table = @mut SmallIntMap<t>;
 864
 865 fn mk_rcache() -> creader_cache {
 866     return @mut HashMap::new();
 867 }
 868
 869 pub fn new_ty_hash<V:Copy>() -> @mut HashMap<t, V> {
 870     @mut HashMap::new()
 871 }
 872
 873 pub fn mk_ctxt(s: session::Session,
 874                dm: resolve::DefMap,
 875                amap: ast_map::map,
 876                freevars: freevars::freevar_map,
 877                region_maps: @mut middle::region::RegionMaps,
 878                region_paramd_items: middle::region::region_paramd_items,
 879                lang_items: middle::lang_items::LanguageItems,
 880                crate: @ast::crate)
 881             -> ctxt {
 882     let mut legacy_modes = false;
 883     for crate.node.attrs.each |attribute| {
 884         match attribute.node.value.node {
 885             ast::meta_word(w) if *w == ~"legacy_modes" => {
 886                 legacy_modes = true;
 887             }
 888             _ => {}
 889         }
 890     }
 891
 892     let vecs_implicitly_copyable =
 893         get_lint_level(s.lint_settings.default_settings,
 894                        lint::vecs_implicitly_copyable) == allow;
 895     @ctxt_ {
 896         diag: s.diagnostic(),
 897         interner: @mut HashMap::new(),
 898         next_id: @mut primitives::LAST_PRIMITIVE_ID,
 899         vecs_implicitly_copyable: vecs_implicitly_copyable,
 900         legacy_modes: legacy_modes,
 901         cstore: s.cstore,
 902         sess: s,
 903         def_map: dm,
 904         region_maps: region_maps,
 905         region_paramd_items: region_paramd_items,
 906         node_types: @mut SmallIntMap::new(),
 907         node_type_substs: @mut HashMap::new(),
 908         trait_refs: @mut HashMap::new(),
 909         trait_defs: @mut HashMap::new(),
 910         intrinsic_traits: @mut HashMap::new(),
 911         items: amap,
 912         intrinsic_defs: @mut HashMap::new(),
 913         freevars: freevars,
 914         tcache: @mut HashMap::new(),
 915         rcache: mk_rcache(),
 916         ccache: @mut HashMap::new(),
 917         short_names_cache: new_ty_hash(),
 918         needs_unwind_cleanup_cache: new_ty_hash(),
 919         tc_cache: @mut HashMap::new(),
 920         ast_ty_to_ty_cache: @mut HashMap::new(),
 921         enum_var_cache: @mut HashMap::new(),
 922         methods: @mut HashMap::new(),
 923         trait_method_def_ids: @mut HashMap::new(),
 924         trait_methods_cache: @mut HashMap::new(),
 925         ty_param_defs: @mut HashMap::new(),
 926         adjustments: @mut HashMap::new(),
 927         normalized_cache: new_ty_hash(),
 928         lang_items: lang_items,
 929         provided_methods: @mut HashMap::new(),
 930         provided_method_sources: @mut HashMap::new(),
 931         supertraits: @mut HashMap::new(),
 932         destructor_for_type: @mut HashMap::new(),
 933         destructors: @mut HashSet::new(),
 934         trait_impls: @mut HashMap::new(),
 935         used_unsafe: @mut HashSet::new(),
 936         used_mut_nodes: @mut HashSet::new(),
 937      }
 938 }
 939
 940 // Type constructors
 941
 942 // Interns a type/name combination, stores the resulting box in cx.interner,
 943 // and returns the box as cast to an unsafe ptr (see comments for t above).
 944 fn mk_t(cx: ctxt, st: sty) -> t {
 945     // Check for primitive types.
 946     match st {
 947         ty_nil => return mk_nil(),
 948         ty_err => return mk_err(),
 949         ty_bool => return mk_bool(),
 950         ty_int(i) => return mk_mach_int(i),
 951         ty_uint(u) => return mk_mach_uint(u),
 952         ty_float(f) => return mk_mach_float(f),
 953         _ => {}
 954     };
 955
 956     let key = intern_key { sty: to_unsafe_ptr(&st) };
 957     match cx.interner.find(&key) {
 958       Some(t) => unsafe { return cast::transmute(&t.sty); },
 959       _ => ()
 960     }
 961
 962     let mut flags = 0u;
 963     fn rflags(r: Region) -> uint {
 964         (has_regions as uint) | {
 965             match r {
 966               ty::re_infer(_) => needs_infer as uint,
 967               _ => 0u
 968             }
 969         }
 970     }
 971     fn sflags(substs: &substs) -> uint {
 972         let mut f = 0u;
 973         for substs.tps.each |tt| { f |= get(*tt).flags; }
 974         for substs.self_r.each |r| { f |= rflags(*r) }
 975         return f;
 976     }
 977     match &st {
 978       &ty_estr(vstore_slice(r)) => {
 979         flags |= rflags(r);
 980       }
 981       &ty_evec(ref mt, vstore_slice(r)) => {
 982         flags |= rflags(r);
 983         flags |= get(mt.ty).flags;
 984       }
 985       &ty_nil | &ty_bool | &ty_int(_) | &ty_float(_) | &ty_uint(_) |
 986       &ty_estr(_) | &ty_type | &ty_opaque_closure_ptr(_) |
 987       &ty_opaque_box => (),
 988       // You might think that we could just return ty_err for
 989       // any type containing ty_err as a component, and get
 990       // rid of the has_ty_err flag -- likewise for ty_bot (with
 991       // the exception of function types that return bot).
 992       // But doing so caused sporadic memory corruption, and
 993       // neither I (tjc) nor nmatsakis could figure out why,
 994       // so we're doing it this way.
 995       &ty_bot => flags |= has_ty_bot as uint,
 996       &ty_err => flags |= has_ty_err as uint,
 997       &ty_param(_) => flags |= has_params as uint,
 998       &ty_infer(_) => flags |= needs_infer as uint,
 999       &ty_self(_) => flags |= has_self as uint,
1000       &ty_enum(_, ref substs) | &ty_struct(_, ref substs) |
1001       &ty_trait(_, ref substs, _, _) => {
1002         flags |= sflags(substs);
1003       }
1004       &ty_box(ref m) | &ty_uniq(ref m) | &ty_evec(ref m, _) |
1005       &ty_ptr(ref m) | &ty_unboxed_vec(ref m) => {
1006         flags |= get(m.ty).flags;
1007       }
1008       &ty_rptr(r, ref m) => {
1009         flags |= rflags(r);
1010         flags |= get(m.ty).flags;
1011       }
1012       &ty_tup(ref ts) => for ts.each |tt| { flags |= get(*tt).flags; },
1013       &ty_bare_fn(ref f) => {
1014         for f.sig.inputs.each |a| { flags |= get(a.ty).flags; }
1015          flags |= get(f.sig.output).flags;
1016          // T -> _|_ is *not* _|_ !
1017          flags &= !(has_ty_bot as uint);
1018       }
1019       &ty_closure(ref f) => {
1020         flags |= rflags(f.region);
1021         for f.sig.inputs.each |a| { flags |= get(a.ty).flags; }
1022         flags |= get(f.sig.output).flags;
1023         // T -> _|_ is *not* _|_ !
1024         flags &= !(has_ty_bot as uint);
1025       }
1026     }
1027
1028     let t = ~t_box_ {
1029         sty: st,
1030         id: *cx.next_id,
1031         flags: flags,
1032     };
1033
1034     let sty_ptr = to_unsafe_ptr(&t.sty);
1035
1036     let key = intern_key {
1037         sty: sty_ptr,
1038     };
1039
1040     cx.interner.insert(key, t);
1041
1042     *cx.next_id += 1;
1043
1044     unsafe {
1045         cast::transmute::<*sty, t>(sty_ptr)
1046     }
1047 }
1048
1049 #[inline(always)]
1050 pub fn mk_prim_t(primitive: &'static t_box_) -> t {
1051     unsafe {
1052         cast::transmute::<&'static t_box_, t>(primitive)
1053     }
1054 }
1055
1056 #[inline(always)]
1057 pub fn mk_nil() -> t { mk_prim_t(&primitives::TY_NIL) }
1058
1059 #[inline(always)]
1060 pub fn mk_err() -> t { mk_prim_t(&primitives::TY_ERR) }
1061
1062 #[inline(always)]
1063 pub fn mk_bot() -> t { mk_prim_t(&primitives::TY_BOT) }
1064
1065 #[inline(always)]
1066 pub fn mk_bool() -> t { mk_prim_t(&primitives::TY_BOOL) }
1067
1068 #[inline(always)]
1069 pub fn mk_int() -> t { mk_prim_t(&primitives::TY_INT) }
1070
1071 #[inline(always)]
1072 pub fn mk_i8() -> t { mk_prim_t(&primitives::TY_I8) }
1073
1074 #[inline(always)]
1075 pub fn mk_i16() -> t { mk_prim_t(&primitives::TY_I16) }
1076
1077 #[inline(always)]
1078 pub fn mk_i32() -> t { mk_prim_t(&primitives::TY_I32) }
1079
1080 #[inline(always)]
1081 pub fn mk_i64() -> t { mk_prim_t(&primitives::TY_I64) }
1082
1083 #[inline(always)]
1084 pub fn mk_float() -> t { mk_prim_t(&primitives::TY_FLOAT) }
1085
1086 #[inline(always)]
1087 pub fn mk_f32() -> t { mk_prim_t(&primitives::TY_F32) }
1088
1089 #[inline(always)]
1090 pub fn mk_f64() -> t { mk_prim_t(&primitives::TY_F64) }
1091
1092 #[inline(always)]
1093 pub fn mk_uint() -> t { mk_prim_t(&primitives::TY_UINT) }
1094
1095 #[inline(always)]
1096 pub fn mk_u8() -> t { mk_prim_t(&primitives::TY_U8) }
1097
1098 #[inline(always)]
1099 pub fn mk_u16() -> t { mk_prim_t(&primitives::TY_U16) }
1100
1101 #[inline(always)]
1102 pub fn mk_u32() -> t { mk_prim_t(&primitives::TY_U32) }
1103
1104 #[inline(always)]
1105 pub fn mk_u64() -> t { mk_prim_t(&primitives::TY_U64) }
1106
1107 pub fn mk_mach_int(tm: ast::int_ty) -> t {
1108     match tm {
1109         ast::ty_i    => mk_int(),
1110         ast::ty_char => mk_char(),
1111         ast::ty_i8   => mk_i8(),
1112         ast::ty_i16  => mk_i16(),
1113         ast::ty_i32  => mk_i32(),
1114         ast::ty_i64  => mk_i64(),
1115     }
1116 }
1117
1118 pub fn mk_mach_uint(tm: ast::uint_ty) -> t {
1119     match tm {
1120         ast::ty_u    => mk_uint(),
1121         ast::ty_u8   => mk_u8(),
1122         ast::ty_u16  => mk_u16(),
1123         ast::ty_u32  => mk_u32(),
1124         ast::ty_u64  => mk_u64(),
1125     }
1126 }
1127
1128 pub fn mk_mach_float(tm: ast::float_ty) -> t {
1129     match tm {
1130         ast::ty_f    => mk_float(),
1131         ast::ty_f32  => mk_f32(),
1132         ast::ty_f64  => mk_f64(),
1133     }
1134 }
1135
1136 #[inline(always)]
1137 pub fn mk_char() -> t { mk_prim_t(&primitives::TY_CHAR) }
1138
1139 pub fn mk_estr(cx: ctxt, t: vstore) -> t {
1140     mk_t(cx, ty_estr(t))
1141 }
1142
1143 pub fn mk_enum(cx: ctxt, did: ast::def_id, substs: substs) -> t {
1144     // take a copy of substs so that we own the vectors inside
1145     mk_t(cx, ty_enum(did, substs))
1146 }
1147
1148 pub fn mk_box(cx: ctxt, tm: mt) -> t { mk_t(cx, ty_box(tm)) }
1149
1150 pub fn mk_imm_box(cx: ctxt, ty: t) -> t {
1151     mk_box(cx, mt {ty: ty, mutbl: ast::m_imm})
1152 }
1153
1154 pub fn mk_uniq(cx: ctxt, tm: mt) -> t { mk_t(cx, ty_uniq(tm)) }
1155
1156 pub fn mk_imm_uniq(cx: ctxt, ty: t) -> t {
1157     mk_uniq(cx, mt {ty: ty, mutbl: ast::m_imm})
1158 }
1159
1160 pub fn mk_ptr(cx: ctxt, tm: mt) -> t { mk_t(cx, ty_ptr(tm)) }
1161
1162 pub fn mk_rptr(cx: ctxt, r: Region, tm: mt) -> t { mk_t(cx, ty_rptr(r, tm)) }
1163
1164 pub fn mk_mut_rptr(cx: ctxt, r: Region, ty: t) -> t {
1165     mk_rptr(cx, r, mt {ty: ty, mutbl: ast::m_mutbl})
1166 }
1167 pub fn mk_imm_rptr(cx: ctxt, r: Region, ty: t) -> t {
1168     mk_rptr(cx, r, mt {ty: ty, mutbl: ast::m_imm})
1169 }
1170
1171 pub fn mk_mut_ptr(cx: ctxt, ty: t) -> t {
1172     mk_ptr(cx, mt {ty: ty, mutbl: ast::m_mutbl})
1173 }
1174
1175 pub fn mk_imm_ptr(cx: ctxt, ty: t) -> t {
1176     mk_ptr(cx, mt {ty: ty, mutbl: ast::m_imm})
1177 }
1178
1179 pub fn mk_nil_ptr(cx: ctxt) -> t {
1180     mk_ptr(cx, mt {ty: mk_nil(), mutbl: ast::m_imm})
1181 }
1182
1183 pub fn mk_evec(cx: ctxt, tm: mt, t: vstore) -> t {
1184     mk_t(cx, ty_evec(tm, t))
1185 }
1186
1187 pub fn mk_unboxed_vec(cx: ctxt, tm: mt) -> t {
1188     mk_t(cx, ty_unboxed_vec(tm))
1189 }
1190 pub fn mk_mut_unboxed_vec(cx: ctxt, ty: t) -> t {
1191     mk_t(cx, ty_unboxed_vec(mt {ty: ty, mutbl: ast::m_imm}))
1192 }
1193
1194 pub fn mk_tup(cx: ctxt, ts: ~[t]) -> t { mk_t(cx, ty_tup(ts)) }
1195
1196 pub fn mk_closure(cx: ctxt, fty: ClosureTy) -> t {
1197     mk_t(cx, ty_closure(fty))
1198 }
1199
1200 pub fn mk_bare_fn(cx: ctxt, fty: BareFnTy) -> t {
1201     mk_t(cx, ty_bare_fn(fty))
1202 }
1203
1204 pub fn mk_ctor_fn(cx: ctxt, input_tys: &[ty::t], output: ty::t) -> t {
1205     let input_args = input_tys.map(|t| arg { ty: *t });
1206     mk_bare_fn(cx,
1207                BareFnTy {
1208                    purity: ast::pure_fn,
1209                    abis: AbiSet::Rust(),
1210                    sig: FnSig {
1211                     bound_lifetime_names: opt_vec::Empty,
1212                     inputs: input_args,
1213                     output: output
1214                    }
1215                 })
1216 }
1217
1218
1219 pub fn mk_trait(cx: ctxt,
1220                 did: ast::def_id,
1221                 substs: substs,
1222                 store: TraitStore,
1223                 mutability: ast::mutability)
1224              -> t {
1225     // take a copy of substs so that we own the vectors inside
1226     mk_t(cx, ty_trait(did, substs, store, mutability))
1227 }
1228
1229 pub fn mk_struct(cx: ctxt, struct_id: ast::def_id, substs: substs) -> t {
1230     // take a copy of substs so that we own the vectors inside
1231     mk_t(cx, ty_struct(struct_id, substs))
1232 }
1233
1234 pub fn mk_var(cx: ctxt, v: TyVid) -> t { mk_infer(cx, TyVar(v)) }
1235
1236 pub fn mk_int_var(cx: ctxt, v: IntVid) -> t { mk_infer(cx, IntVar(v)) }
1237
1238 pub fn mk_float_var(cx: ctxt, v: FloatVid) -> t { mk_infer(cx, FloatVar(v)) }
1239
1240 pub fn mk_infer(cx: ctxt, it: InferTy) -> t { mk_t(cx, ty_infer(it)) }
1241
1242 pub fn mk_self(cx: ctxt, did: ast::def_id) -> t { mk_t(cx, ty_self(did)) }
1243
1244 pub fn mk_param(cx: ctxt, n: uint, k: def_id) -> t {
1245     mk_t(cx, ty_param(param_ty { idx: n, def_id: k }))
1246 }
1247
1248 pub fn mk_type(cx: ctxt) -> t { mk_t(cx, ty_type) }
1249
1250 pub fn mk_opaque_closure_ptr(cx: ctxt, sigil: ast::Sigil) -> t {
1251     mk_t(cx, ty_opaque_closure_ptr(sigil))
1252 }
1253
1254 pub fn mk_opaque_box(cx: ctxt) -> t { mk_t(cx, ty_opaque_box) }
1255
1256 pub fn walk_ty(ty: t, f: &fn(t)) {
1257     maybe_walk_ty(ty, |t| { f(t); true });
1258 }
1259
1260 pub fn maybe_walk_ty(ty: t, f: &fn(t) -> bool) {
1261     if !f(ty) {
1262         return;
1263     }
1264     match get(ty).sty {
1265       ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1266       ty_estr(_) | ty_type | ty_opaque_box | ty_self(_) |
1267       ty_opaque_closure_ptr(_) | ty_infer(_) | ty_param(_) | ty_err => {
1268       }
1269       ty_box(ref tm) | ty_evec(ref tm, _) | ty_unboxed_vec(ref tm) |
1270       ty_ptr(ref tm) | ty_rptr(_, ref tm) | ty_uniq(ref tm) => {
1271         maybe_walk_ty(tm.ty, f);
1272       }
1273       ty_enum(_, ref substs) | ty_struct(_, ref substs) |
1274       ty_trait(_, ref substs, _, _) => {
1275         for (*substs).tps.each |subty| { maybe_walk_ty(*subty, f); }
1276       }
1277       ty_tup(ref ts) => { for ts.each |tt| { maybe_walk_ty(*tt, f); } }
1278       ty_bare_fn(ref ft) => {
1279         for ft.sig.inputs.each |a| { maybe_walk_ty(a.ty, f); }
1280         maybe_walk_ty(ft.sig.output, f);
1281       }
1282       ty_closure(ref ft) => {
1283         for ft.sig.inputs.each |a| { maybe_walk_ty(a.ty, f); }
1284         maybe_walk_ty(ft.sig.output, f);
1285       }
1286     }
1287 }
1288
1289 pub fn fold_sty_to_ty(tcx: ty::ctxt, sty: &sty, foldop: &fn(t) -> t) -> t {
1290     mk_t(tcx, fold_sty(sty, foldop))
1291 }
1292
1293 pub fn fold_sig(sig: &FnSig, fldop: &fn(t) -> t) -> FnSig {
1294     let args = do sig.inputs.map |arg| {
1295         arg {
1296             ty: fldop(arg.ty)
1297         }
1298     };
1299
1300     FnSig {
1301         bound_lifetime_names: copy sig.bound_lifetime_names,
1302         inputs: args,
1303         output: fldop(sig.output)
1304     }
1305 }
1306
1307 pub fn fold_bare_fn_ty(fty: &BareFnTy, fldop: &fn(t) -> t) -> BareFnTy {
1308     BareFnTy {sig: fold_sig(&fty.sig, fldop),
1309               abis: fty.abis,
1310               purity: fty.purity}
1311 }
1312
1313 fn fold_sty(sty: &sty, fldop: &fn(t) -> t) -> sty {
1314     fn fold_substs(substs: &substs, fldop: &fn(t) -> t) -> substs {
1315         substs {self_r: substs.self_r,
1316                 self_ty: substs.self_ty.map(|t| fldop(*t)),
1317                 tps: substs.tps.map(|t| fldop(*t))}
1318     }
1319
1320     match *sty {
1321         ty_box(ref tm) => {
1322             ty_box(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1323         }
1324         ty_uniq(ref tm) => {
1325             ty_uniq(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1326         }
1327         ty_ptr(ref tm) => {
1328             ty_ptr(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1329         }
1330         ty_unboxed_vec(ref tm) => {
1331             ty_unboxed_vec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1332         }
1333         ty_evec(ref tm, vst) => {
1334             ty_evec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl}, vst)
1335         }
1336         ty_enum(tid, ref substs) => {
1337             ty_enum(tid, fold_substs(substs, fldop))
1338         }
1339         ty_trait(did, ref substs, st, mutbl) => {
1340             ty_trait(did, fold_substs(substs, fldop), st, mutbl)
1341         }
1342         ty_tup(ref ts) => {
1343             let new_ts = ts.map(|tt| fldop(*tt));
1344             ty_tup(new_ts)
1345         }
1346         ty_bare_fn(ref f) => {
1347             ty_bare_fn(fold_bare_fn_ty(f, fldop))
1348         }
1349         ty_closure(ref f) => {
1350             let sig = fold_sig(&f.sig, fldop);
1351             ty_closure(ClosureTy {sig: sig, ..copy *f})
1352         }
1353         ty_rptr(r, ref tm) => {
1354             ty_rptr(r, mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1355         }
1356         ty_struct(did, ref substs) => {
1357             ty_struct(did, fold_substs(substs, fldop))
1358         }
1359         ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1360         ty_estr(_) | ty_type | ty_opaque_closure_ptr(_) | ty_err |
1361         ty_opaque_box | ty_infer(_) | ty_param(*) | ty_self(_) => {
1362             /*bad*/copy *sty
1363         }
1364     }
1365 }
1366
1367 // Folds types from the bottom up.
1368 pub fn fold_ty(cx: ctxt, t0: t, fldop: &fn(t) -> t) -> t {
1369     let sty = fold_sty(&get(t0).sty, |t| fold_ty(cx, fldop(t), fldop));
1370     fldop(mk_t(cx, sty))
1371 }
1372
1373 pub fn walk_regions_and_ty(
1374     cx: ctxt,
1375     ty: t,
1376     walkr: &fn(r: Region),
1377     walkt: &fn(t: t) -> bool) {
1378
1379     if (walkt(ty)) {
1380         fold_regions_and_ty(
1381             cx, ty,
1382             |r| { walkr(r); r },
1383             |t| { walk_regions_and_ty(cx, t, walkr, walkt); t },
1384             |t| { walk_regions_and_ty(cx, t, walkr, walkt); t });
1385     }
1386 }
1387
1388 pub fn fold_regions_and_ty(
1389     cx: ctxt,
1390     ty: t,
1391     fldr: &fn(r: Region) -> Region,
1392     fldfnt: &fn(t: t) -> t,
1393     fldt: &fn(t: t) -> t) -> t {
1394
1395     fn fold_substs(
1396         substs: &substs,
1397         fldr: &fn(r: Region) -> Region,
1398         fldt: &fn(t: t) -> t)
1399      -> substs {
1400         substs {
1401             self_r: substs.self_r.map(|r| fldr(*r)),
1402             self_ty: substs.self_ty.map(|t| fldt(*t)),
1403             tps: substs.tps.map(|t| fldt(*t))
1404         }
1405     }
1406
1407     let tb = ty::get(ty);
1408     match tb.sty {
1409       ty::ty_rptr(r, mt) => {
1410         let m_r = fldr(r);
1411         let m_t = fldt(mt.ty);
1412         ty::mk_rptr(cx, m_r, mt {ty: m_t, mutbl: mt.mutbl})
1413       }
1414       ty_estr(vstore_slice(r)) => {
1415         let m_r = fldr(r);
1416         ty::mk_estr(cx, vstore_slice(m_r))
1417       }
1418       ty_evec(mt, vstore_slice(r)) => {
1419         let m_r = fldr(r);
1420         let m_t = fldt(mt.ty);
1421         ty::mk_evec(cx, mt {ty: m_t, mutbl: mt.mutbl}, vstore_slice(m_r))
1422       }
1423       ty_enum(def_id, ref substs) => {
1424         ty::mk_enum(cx, def_id, fold_substs(substs, fldr, fldt))
1425       }
1426       ty_struct(def_id, ref substs) => {
1427         ty::mk_struct(cx, def_id, fold_substs(substs, fldr, fldt))
1428       }
1429       ty_trait(def_id, ref substs, st, mutbl) => {
1430         ty::mk_trait(cx, def_id, fold_substs(substs, fldr, fldt), st, mutbl)
1431       }
1432       ty_bare_fn(ref f) => {
1433           ty::mk_bare_fn(cx, BareFnTy {sig: fold_sig(&f.sig, fldfnt),
1434                                        ..copy *f})
1435       }
1436       ty_closure(ref f) => {
1437           ty::mk_closure(cx, ClosureTy {region: fldr(f.region),
1438                                         sig: fold_sig(&f.sig, fldfnt),
1439                                         ..copy *f})
1440       }
1441       ref sty => {
1442         fold_sty_to_ty(cx, sty, |t| fldt(t))
1443       }
1444     }
1445 }
1446
1447 // n.b. this function is intended to eventually replace fold_region() below,
1448 // that is why its name is so similar.
1449 pub fn fold_regions(
1450     cx: ctxt,
1451     ty: t,
1452     fldr: &fn(r: Region, in_fn: bool) -> Region) -> t {
1453     fn do_fold(cx: ctxt, ty: t, in_fn: bool,
1454                fldr: &fn(Region, bool) -> Region) -> t {
1455         debug!("do_fold(ty=%s, in_fn=%b)", ty_to_str(cx, ty), in_fn);
1456         if !type_has_regions(ty) { return ty; }
1457         fold_regions_and_ty(
1458             cx, ty,
1459             |r| fldr(r, in_fn),
1460             |t| do_fold(cx, t, true, fldr),
1461             |t| do_fold(cx, t, in_fn, fldr))
1462     }
1463     do_fold(cx, ty, false, fldr)
1464 }
1465
1466 // Substitute *only* type parameters.  Used in trans where regions are erased.
1467 pub fn subst_tps(cx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
1468     if tps.len() == 0u && self_ty_opt.is_none() { return typ; }
1469     let tb = ty::get(typ);
1470     if self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) { return typ; }
1471     match tb.sty {
1472         ty_param(p) => tps[p.idx],
1473         ty_self(_) => {
1474             match self_ty_opt {
1475                 None => cx.sess.bug(~"ty_self unexpected here"),
1476                 Some(self_ty) => {
1477                     subst_tps(cx, tps, self_ty_opt, self_ty)
1478                 }
1479             }
1480         }
1481         ref sty => {
1482             fold_sty_to_ty(cx, sty, |t| subst_tps(cx, tps, self_ty_opt, t))
1483         }
1484     }
1485 }
1486
1487 pub fn substs_is_noop(substs: &substs) -> bool {
1488     substs.tps.len() == 0u &&
1489         substs.self_r.is_none() &&
1490         substs.self_ty.is_none()
1491 }
1492
1493 pub fn substs_to_str(cx: ctxt, substs: &substs) -> ~str {
1494     substs.repr(cx)
1495 }
1496
1497 pub fn param_bound_to_str(cx: ctxt, pb: &param_bound) -> ~str {
1498     pb.repr(cx)
1499 }
1500
1501 pub fn param_bounds_to_str(cx: ctxt, pbs: param_bounds) -> ~str {
1502     pbs.repr(cx)
1503 }
1504
1505 pub fn subst(cx: ctxt,
1506              substs: &substs,
1507              typ: t)
1508           -> t {
1509     typ.subst(cx, substs)
1510 }
1511
1512 // Type utilities
1513
1514 pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil }
1515
1516 pub fn type_is_bot(ty: t) -> bool {
1517     (get(ty).flags & (has_ty_bot as uint)) != 0
1518 }
1519
1520 pub fn type_is_error(ty: t) -> bool {
1521     (get(ty).flags & (has_ty_err as uint)) != 0
1522 }
1523
1524 pub fn type_needs_subst(ty: t) -> bool {
1525     tbox_has_flag(get(ty), needs_subst)
1526 }
1527
1528 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
1529     tref.substs.self_ty.any(|&t| type_is_error(t)) ||
1530         tref.substs.tps.any(|&t| type_is_error(t))
1531 }
1532
1533 pub fn type_is_ty_var(ty: t) -> bool {
1534     match get(ty).sty {
1535       ty_infer(TyVar(_)) => true,
1536       _ => false
1537     }
1538 }
1539
1540 pub fn type_is_bool(ty: t) -> bool { get(ty).sty == ty_bool }
1541
1542 pub fn type_is_structural(ty: t) -> bool {
1543     match get(ty).sty {
1544       ty_struct(*) | ty_tup(_) | ty_enum(*) | ty_closure(_) | ty_trait(*) |
1545       ty_evec(_, vstore_fixed(_)) | ty_estr(vstore_fixed(_)) |
1546       ty_evec(_, vstore_slice(_)) | ty_estr(vstore_slice(_))
1547       => true,
1548       _ => false
1549     }
1550 }
1551
1552 pub fn type_is_sequence(ty: t) -> bool {
1553     match get(ty).sty {
1554       ty_estr(_) | ty_evec(_, _) => true,
1555       _ => false
1556     }
1557 }
1558
1559 pub fn type_is_str(ty: t) -> bool {
1560     match get(ty).sty {
1561       ty_estr(_) => true,
1562       _ => false
1563     }
1564 }
1565
1566 pub fn sequence_element_type(cx: ctxt, ty: t) -> t {
1567     match get(ty).sty {
1568       ty_estr(_) => return mk_mach_uint(ast::ty_u8),
1569       ty_evec(mt, _) | ty_unboxed_vec(mt) => return mt.ty,
1570       _ => cx.sess.bug(
1571           ~"sequence_element_type called on non-sequence value"),
1572     }
1573 }
1574
1575 pub fn get_element_type(ty: t, i: uint) -> t {
1576     match get(ty).sty {
1577       ty_tup(ref ts) => return ts[i],
1578       _ => fail!(~"get_element_type called on invalid type")
1579     }
1580 }
1581
1582 pub fn type_is_box(ty: t) -> bool {
1583     match get(ty).sty {
1584       ty_box(_) => return true,
1585       _ => return false
1586     }
1587 }
1588
1589 pub fn type_is_boxed(ty: t) -> bool {
1590     match get(ty).sty {
1591       ty_box(_) | ty_opaque_box |
1592       ty_evec(_, vstore_box) | ty_estr(vstore_box) => true,
1593       _ => false
1594     }
1595 }
1596
1597 pub fn type_is_region_ptr(ty: t) -> bool {
1598     match get(ty).sty {
1599       ty_rptr(_, _) => true,
1600       _ => false
1601     }
1602 }
1603
1604 pub fn type_is_slice(ty: t) -> bool {
1605     match get(ty).sty {
1606       ty_evec(_, vstore_slice(_)) | ty_estr(vstore_slice(_)) => true,
1607       _ => return false
1608     }
1609 }
1610
1611 pub fn type_is_unique_box(ty: t) -> bool {
1612     match get(ty).sty {
1613       ty_uniq(_) => return true,
1614       _ => return false
1615     }
1616 }
1617
1618 pub fn type_is_unsafe_ptr(ty: t) -> bool {
1619     match get(ty).sty {
1620       ty_ptr(_) => return true,
1621       _ => return false
1622     }
1623 }
1624
1625 pub fn type_is_vec(ty: t) -> bool {
1626     return match get(ty).sty {
1627           ty_evec(_, _) | ty_unboxed_vec(_) => true,
1628           ty_estr(_) => true,
1629           _ => false
1630         };
1631 }
1632
1633 pub fn type_is_unique(ty: t) -> bool {
1634     match get(ty).sty {
1635         ty_uniq(_) |
1636         ty_evec(_, vstore_uniq) |
1637         ty_estr(vstore_uniq) |
1638         ty_opaque_closure_ptr(ast::OwnedSigil) => true,
1639         _ => return false
1640     }
1641 }
1642
1643 /*
1644  A scalar type is one that denotes an atomic datum, with no sub-components.
1645  (A ty_ptr is scalar because it represents a non-managed pointer, so its
1646  contents are abstract to rustc.)
1647 */
1648 pub fn type_is_scalar(ty: t) -> bool {
1649     match get(ty).sty {
1650       ty_nil | ty_bool | ty_int(_) | ty_float(_) | ty_uint(_) |
1651       ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) | ty_type |
1652       ty_bare_fn(*) | ty_ptr(_) => true,
1653       _ => false
1654     }
1655 }
1656
1657 pub fn type_is_immediate(ty: t) -> bool {
1658     return type_is_scalar(ty) || type_is_boxed(ty) ||
1659         type_is_unique(ty) || type_is_region_ptr(ty);
1660 }
1661
1662 pub fn type_needs_drop(cx: ctxt, ty: t) -> bool {
1663     type_contents(cx, ty).needs_drop(cx)
1664 }
1665
1666 // Some things don't need cleanups during unwinding because the
1667 // task can free them all at once later. Currently only things
1668 // that only contain scalars and shared boxes can avoid unwind
1669 // cleanups.
1670 pub fn type_needs_unwind_cleanup(cx: ctxt, ty: t) -> bool {
1671     match cx.needs_unwind_cleanup_cache.find(&ty) {
1672       Some(&result) => return result,
1673       None => ()
1674     }
1675
1676     let mut tycache = HashSet::new();
1677     let needs_unwind_cleanup =
1678         type_needs_unwind_cleanup_(cx, ty, &mut tycache, false);
1679     cx.needs_unwind_cleanup_cache.insert(ty, needs_unwind_cleanup);
1680     return needs_unwind_cleanup;
1681 }
1682
1683 fn type_needs_unwind_cleanup_(cx: ctxt, ty: t,
1684                               tycache: &mut HashSet<t>,
1685                               encountered_box: bool) -> bool {
1686
1687     // Prevent infinite recursion
1688     if !tycache.insert(ty) {
1689         return false;
1690     }
1691
1692     let mut encountered_box = encountered_box;
1693     let mut needs_unwind_cleanup = false;
1694     do maybe_walk_ty(ty) |ty| {
1695         let old_encountered_box = encountered_box;
1696         let result = match get(ty).sty {
1697           ty_box(_) | ty_opaque_box => {
1698             encountered_box = true;
1699             true
1700           }
1701           ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1702           ty_tup(_) | ty_ptr(_) => {
1703             true
1704           }
1705           ty_enum(did, ref substs) => {
1706             for vec::each(*enum_variants(cx, did)) |v| {
1707                 for v.args.each |aty| {
1708                     let t = subst(cx, substs, *aty);
1709                     needs_unwind_cleanup |=
1710                         type_needs_unwind_cleanup_(cx, t, tycache,
1711                                                    encountered_box);
1712                 }
1713             }
1714             !needs_unwind_cleanup
1715           }
1716           ty_uniq(_) |
1717           ty_estr(vstore_uniq) |
1718           ty_estr(vstore_box) |
1719           ty_evec(_, vstore_uniq) |
1720           ty_evec(_, vstore_box)
1721           => {
1722             // Once we're inside a box, the annihilator will find
1723             // it and destroy it.
1724             if !encountered_box {
1725                 needs_unwind_cleanup = true;
1726                 false
1727             } else {
1728                 true
1729             }
1730           }
1731           _ => {
1732             needs_unwind_cleanup = true;
1733             false
1734           }
1735         };
1736
1737         encountered_box = old_encountered_box;
1738         result
1739     }
1740
1741     return needs_unwind_cleanup;
1742 }
1743
1744 /**
1745  * Type contents is how the type checker reasons about kinds.
1746  * They track what kinds of things are found within a type.  You can
1747  * think of them as kind of an "anti-kind".  They track the kinds of values
1748  * and thinks that are contained in types.  Having a larger contents for
1749  * a type tends to rule that type *out* from various kinds.  For example,
1750  * a type that contains a borrowed pointer is not sendable.
1751  *
1752  * The reason we compute type contents and not kinds is that it is
1753  * easier for me (nmatsakis) to think about what is contained within
1754  * a type than to think about what is *not* contained within a type.
1755  */
1756 pub struct TypeContents {
1757     bits: u32
1758 }
1759
1760 pub impl TypeContents {
1761     fn intersects(&self, tc: TypeContents) -> bool {
1762         (self.bits & tc.bits) != 0
1763     }
1764
1765     fn is_copy(&self, cx: ctxt) -> bool {
1766         !self.intersects(TypeContents::noncopyable(cx))
1767     }
1768
1769     fn noncopyable(_cx: ctxt) -> TypeContents {
1770         TC_DTOR + TC_BORROWED_MUT + TC_ONCE_CLOSURE + TC_OWNED_CLOSURE +
1771             TC_EMPTY_ENUM
1772     }
1773
1774     fn is_durable(&self, cx: ctxt) -> bool {
1775         !self.intersects(TypeContents::nondurable(cx))
1776     }
1777
1778     fn nondurable(_cx: ctxt) -> TypeContents {
1779         TC_BORROWED_POINTER
1780     }
1781
1782     fn is_owned(&self, cx: ctxt) -> bool {
1783         !self.intersects(TypeContents::nonowned(cx))
1784     }
1785
1786     fn nonowned(_cx: ctxt) -> TypeContents {
1787         TC_MANAGED + TC_BORROWED_POINTER
1788     }
1789
1790     fn contains_managed(&self) -> bool {
1791         self.intersects(TC_MANAGED)
1792     }
1793
1794     fn is_const(&self, cx: ctxt) -> bool {
1795         !self.intersects(TypeContents::nonconst(cx))
1796     }
1797
1798     fn nonconst(_cx: ctxt) -> TypeContents {
1799         TC_MUTABLE
1800     }
1801
1802     fn moves_by_default(&self, cx: ctxt) -> bool {
1803         self.intersects(TypeContents::nonimplicitly_copyable(cx))
1804     }
1805
1806     fn nonimplicitly_copyable(cx: ctxt) -> TypeContents {
1807         let base = TypeContents::noncopyable(cx) + TC_OWNED_POINTER;
1808         if cx.vecs_implicitly_copyable {base} else {base + TC_OWNED_VEC}
1809     }
1810
1811     fn needs_drop(&self, cx: ctxt) -> bool {
1812         let tc = TC_MANAGED + TC_DTOR + TypeContents::owned(cx);
1813         self.intersects(tc)
1814     }
1815
1816     fn owned(_cx: ctxt) -> TypeContents {
1817         //! Any kind of owned contents.
1818         TC_OWNED_CLOSURE + TC_OWNED_POINTER + TC_OWNED_VEC
1819     }
1820 }
1821
1822 impl ops::Add<TypeContents,TypeContents> for TypeContents {
1823     fn add(&self, other: &TypeContents) -> TypeContents {
1824         TypeContents {bits: self.bits | other.bits}
1825     }
1826 }
1827
1828 impl ops::Sub<TypeContents,TypeContents> for TypeContents {
1829     fn sub(&self, other: &TypeContents) -> TypeContents {
1830         TypeContents {bits: self.bits & !other.bits}
1831     }
1832 }
1833
1834 impl ToStr for TypeContents {
1835     fn to_str(&self) -> ~str {
1836         fmt!("TypeContents(%s)", u32::to_str_radix(self.bits, 2))
1837     }
1838 }
1839
1840 /// Constant for a type containing nothing of interest.
1841 static TC_NONE: TypeContents =             TypeContents{bits:0b0000_00000000};
1842
1843 /// Contains a borrowed value with a lifetime other than static
1844 static TC_BORROWED_POINTER: TypeContents = TypeContents{bits:0b0000_00000001};
1845
1846 /// Contains an owned pointer (~T) but not slice of some kind
1847 static TC_OWNED_POINTER: TypeContents =    TypeContents{bits:0b000000000010};
1848
1849 /// Contains an owned vector ~[] or owned string ~str
1850 static TC_OWNED_VEC: TypeContents =        TypeContents{bits:0b000000000100};
1851
1852 /// Contains a ~fn() or a ~Trait, which is non-copyable.
1853 static TC_OWNED_CLOSURE: TypeContents =    TypeContents{bits:0b000000001000};
1854
1855 /// Type with a destructor
1856 static TC_DTOR: TypeContents =             TypeContents{bits:0b000000010000};
1857
1858 /// Contains a managed value
1859 static TC_MANAGED: TypeContents =          TypeContents{bits:0b000000100000};
1860
1861 /// &mut with any region
1862 static TC_BORROWED_MUT: TypeContents =     TypeContents{bits:0b000001000000};
1863
1864 /// Mutable content, whether owned or by ref
1865 static TC_MUTABLE: TypeContents =          TypeContents{bits:0b000010000000};
1866
1867 /// Mutable content, whether owned or by ref
1868 static TC_ONCE_CLOSURE: TypeContents =     TypeContents{bits:0b000100000000};
1869
1870 /// An enum with no variants.
1871 static TC_EMPTY_ENUM: TypeContents =       TypeContents{bits:0b010000000000};
1872
1873 /// All possible contents.
1874 static TC_ALL: TypeContents =              TypeContents{bits:0b011111111111};
1875
1876 pub fn type_is_copyable(cx: ctxt, t: ty::t) -> bool {
1877     type_contents(cx, t).is_copy(cx)
1878 }
1879
1880 pub fn type_is_durable(cx: ctxt, t: ty::t) -> bool {
1881     type_contents(cx, t).is_durable(cx)
1882 }
1883
1884 pub fn type_is_owned(cx: ctxt, t: ty::t) -> bool {
1885     type_contents(cx, t).is_owned(cx)
1886 }
1887
1888 pub fn type_is_const(cx: ctxt, t: ty::t) -> bool {
1889     type_contents(cx, t).is_const(cx)
1890 }
1891
1892 pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
1893     let ty_id = type_id(ty);
1894     match cx.tc_cache.find(&ty_id) {
1895         Some(tc) => { return *tc; }
1896         None => {}
1897     }
1898
1899     let mut cache = HashMap::new();
1900     let result = tc_ty(cx, ty, &mut cache);
1901     cx.tc_cache.insert(ty_id, result);
1902     return result;
1903
1904     fn tc_ty(cx: ctxt,
1905              ty: t,
1906              cache: &mut HashMap<uint, TypeContents>) -> TypeContents
1907     {
1908         // Subtle: Note that we are *not* using cx.tc_cache here but rather a
1909         // private cache for this walk.  This is needed in the case of cyclic
1910         // types like:
1911         //
1912         //     struct List { next: ~Option<List>, ... }
1913         //
1914         // When computing the type contents of such a type, we wind up deeply
1915         // recursing as we go.  So when we encounter the recursive reference
1916         // to List, we temporarily use TC_NONE as its contents.  Later we'll
1917         // patch up the cache with the correct value, once we've computed it
1918         // (this is basically a co-inductive process, if that helps).  So in
1919         // the end we'll compute TC_OWNED_POINTER, in this case.
1920         //
1921         // The problem is, as we are doing the computation, we will also
1922         // compute an *intermediate* contents for, e.g., Option<List> of
1923         // TC_NONE.  This is ok during the computation of List itself, but if
1924         // we stored this intermediate value into cx.tc_cache, then later
1925         // requests for the contents of Option<List> would also yield TC_NONE
1926         // which is incorrect.  This value was computed based on the crutch
1927         // value for the type contents of list.  The correct value is
1928         // TC_OWNED_POINTER.  This manifested as issue #4821.
1929         let ty_id = type_id(ty);
1930         match cache.find(&ty_id) {
1931             Some(tc) => { return *tc; }
1932             None => {}
1933         }
1934         match cx.tc_cache.find(&ty_id) {    // Must check both caches!
1935             Some(tc) => { return *tc; }
1936             None => {}
1937         }
1938         cache.insert(ty_id, TC_NONE);
1939
1940         let _i = indenter();
1941
1942         let mut result = match get(ty).sty {
1943             // Scalar and unique types are sendable, constant, and owned
1944             ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1945             ty_bare_fn(_) | ty_ptr(_) => {
1946                 TC_NONE
1947             }
1948
1949             ty_estr(vstore_uniq) => {
1950                 TC_OWNED_VEC
1951             }
1952
1953             ty_closure(ref c) => {
1954                 closure_contents(c)
1955             }
1956
1957             ty_box(mt) => {
1958                 TC_MANAGED + nonowned(tc_mt(cx, mt, cache))
1959             }
1960
1961             ty_trait(_, _, UniqTraitStore, _) => {
1962                 TC_OWNED_CLOSURE
1963             }
1964
1965             ty_trait(_, _, BoxTraitStore, mutbl) => {
1966                 match mutbl {
1967                     ast::m_mutbl => TC_MANAGED + TC_MUTABLE,
1968                     _ => TC_MANAGED
1969                 }
1970             }
1971
1972             ty_trait(_, _, RegionTraitStore(r), mutbl) => {
1973                 borrowed_contents(r, mutbl)
1974             }
1975
1976             ty_rptr(r, mt) => {
1977                 borrowed_contents(r, mt.mutbl) +
1978                     nonowned(tc_mt(cx, mt, cache))
1979             }
1980
1981             ty_uniq(mt) => {
1982                 TC_OWNED_POINTER + tc_mt(cx, mt, cache)
1983             }
1984
1985             ty_evec(mt, vstore_uniq) => {
1986                 TC_OWNED_VEC + tc_mt(cx, mt, cache)
1987             }
1988
1989             ty_evec(mt, vstore_box) => {
1990                 TC_MANAGED + nonowned(tc_mt(cx, mt, cache))
1991             }
1992
1993             ty_evec(mt, vstore_slice(r)) => {
1994                 borrowed_contents(r, mt.mutbl) +
1995                     nonowned(tc_mt(cx, mt, cache))
1996             }
1997
1998             ty_evec(mt, vstore_fixed(_)) => {
1999                 tc_mt(cx, mt, cache)
2000             }
2001
2002             ty_estr(vstore_box) => {
2003                 TC_MANAGED
2004             }
2005
2006             ty_estr(vstore_slice(r)) => {
2007                 borrowed_contents(r, m_imm)
2008             }
2009
2010             ty_estr(vstore_fixed(_)) => {
2011                 TC_NONE
2012             }
2013
2014             ty_struct(did, ref substs) => {
2015                 let flds = struct_fields(cx, did, substs);
2016                 let flds_tc = flds.foldl(
2017                     TC_NONE,
2018                     |tc, f| tc + tc_mt(cx, f.mt, cache));
2019                 if ty::has_dtor(cx, did) {
2020                     flds_tc + TC_DTOR
2021                 } else {
2022                     flds_tc
2023                 }
2024             }
2025
2026             ty_tup(ref tys) => {
2027                 tys.foldl(TC_NONE, |tc, ty| *tc + tc_ty(cx, *ty, cache))
2028             }
2029
2030             ty_enum(did, ref substs) => {
2031                 let variants = substd_enum_variants(cx, did, substs);
2032                 if variants.is_empty() {
2033                     // we somewhat arbitrary declare that empty enums
2034                     // are non-copyable
2035                     TC_EMPTY_ENUM
2036                 } else {
2037                     variants.foldl(TC_NONE, |tc, variant| {
2038                         variant.args.foldl(
2039                             *tc,
2040                             |tc, arg_ty| *tc + tc_ty(cx, *arg_ty, cache))
2041                     })
2042                 }
2043             }
2044
2045             ty_param(p) => {
2046                 // We only ever ask for the kind of types that are defined in
2047                 // the current crate; therefore, the only type parameters that
2048                 // could be in scope are those defined in the current crate.
2049                 // If this assertion failures, it is likely because of a
2050                 // failure in the cross-crate inlining code to translate a
2051                 // def-id.
2052                 assert!(p.def_id.crate == ast::local_crate);
2053
2054                 type_param_def_to_contents(
2055                     cx, cx.ty_param_defs.get(&p.def_id.node))
2056             }
2057
2058             ty_self(_) => {
2059                 // Currently, self is not bounded, so we must assume the
2060                 // worst.  But in the future we should examine the super
2061                 // traits.
2062                 //
2063                 // FIXME(#4678)---self should just be a ty param
2064                 TC_ALL
2065             }
2066
2067             ty_infer(_) => {
2068                 // This occurs during coherence, but shouldn't occur at other
2069                 // times.
2070                 TC_ALL
2071             }
2072
2073             ty_opaque_box => TC_MANAGED,
2074             ty_unboxed_vec(mt) => tc_mt(cx, mt, cache),
2075             ty_opaque_closure_ptr(sigil) => {
2076                 match sigil {
2077                     ast::BorrowedSigil => TC_BORROWED_POINTER,
2078                     ast::ManagedSigil => TC_MANAGED,
2079                     ast::OwnedSigil => TC_OWNED_CLOSURE
2080                 }
2081             }
2082
2083             ty_type => TC_NONE,
2084
2085             ty_err => {
2086                 cx.sess.bug(~"Asked to compute contents of fictitious type");
2087             }
2088         };
2089
2090         cache.insert(ty_id, result);
2091         return result;
2092     }
2093
2094     fn tc_mt(cx: ctxt,
2095              mt: mt,
2096              cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2097     {
2098         let mc = if mt.mutbl == m_mutbl {TC_MUTABLE} else {TC_NONE};
2099         mc + tc_ty(cx, mt.ty, cache)
2100     }
2101
2102     fn borrowed_contents(region: ty::Region,
2103                          mutbl: ast::mutability) -> TypeContents
2104     {
2105         let mc = if mutbl == m_mutbl {
2106             TC_MUTABLE + TC_BORROWED_MUT
2107         } else {
2108             TC_NONE
2109         };
2110         let rc = if region != ty::re_static {
2111             TC_BORROWED_POINTER
2112         } else {
2113             TC_NONE
2114         };
2115         mc + rc
2116     }
2117
2118     fn nonowned(pointee: TypeContents) -> TypeContents {
2119         /*!
2120          *
2121          * Given a non-owning pointer to some type `T` with
2122          * contents `pointee` (like `@T` or
2123          * `&T`), returns the relevant bits that
2124          * apply to the owner of the pointer.
2125          */
2126
2127         let mask = TC_MUTABLE.bits | TC_BORROWED_POINTER.bits;
2128         TypeContents {bits: pointee.bits & mask}
2129     }
2130
2131     fn closure_contents(cty: &ClosureTy) -> TypeContents {
2132         let st = match cty.sigil {
2133             ast::BorrowedSigil => TC_BORROWED_POINTER,
2134             ast::ManagedSigil => TC_MANAGED,
2135             ast::OwnedSigil => TC_OWNED_CLOSURE
2136         };
2137         let rt = borrowed_contents(cty.region, m_imm);
2138         let ot = match cty.onceness {
2139             ast::Once => TC_ONCE_CLOSURE,
2140             ast::Many => TC_NONE
2141         };
2142         st + rt + ot
2143     }
2144
2145     fn type_param_def_to_contents(cx: ctxt,
2146                                   type_param_def: &TypeParameterDef) -> TypeContents
2147     {
2148         debug!("type_param_def_to_contents(%s)", type_param_def.repr(cx));
2149         let _i = indenter();
2150
2151         let r = type_param_def.bounds.foldl(TC_ALL, |tc, bound| {
2152             debug!("tc = %s, bound = %?", tc.to_str(), bound);
2153             match *bound {
2154                 bound_copy => tc - TypeContents::nonimplicitly_copyable(cx),
2155                 bound_durable => tc - TypeContents::nondurable(cx),
2156                 bound_owned => tc - TypeContents::nonowned(cx),
2157                 bound_const => tc - TypeContents::nonconst(cx),
2158                 bound_trait(_) => *tc
2159             }
2160         });
2161
2162         debug!("result = %s", r.to_str());
2163         return r;
2164     }
2165 }
2166
2167 pub fn type_moves_by_default(cx: ctxt, ty: t) -> bool {
2168     type_contents(cx, ty).moves_by_default(cx)
2169 }
2170
2171 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
2172 pub fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
2173     fn type_requires(cx: ctxt, seen: &mut ~[def_id],
2174                      r_ty: t, ty: t) -> bool {
2175         debug!("type_requires(%s, %s)?",
2176                ::util::ppaux::ty_to_str(cx, r_ty),
2177                ::util::ppaux::ty_to_str(cx, ty));
2178
2179         let r = {
2180             get(r_ty).sty == get(ty).sty ||
2181                 subtypes_require(cx, seen, r_ty, ty)
2182         };
2183
2184         debug!("type_requires(%s, %s)? %b",
2185                ::util::ppaux::ty_to_str(cx, r_ty),
2186                ::util::ppaux::ty_to_str(cx, ty),
2187                r);
2188         return r;
2189     }
2190
2191     fn subtypes_require(cx: ctxt, seen: &mut ~[def_id],
2192                         r_ty: t, ty: t) -> bool {
2193         debug!("subtypes_require(%s, %s)?",
2194                ::util::ppaux::ty_to_str(cx, r_ty),
2195                ::util::ppaux::ty_to_str(cx, ty));
2196
2197         let r = match get(ty).sty {
2198           ty_nil |
2199           ty_bot |
2200           ty_bool |
2201           ty_int(_) |
2202           ty_uint(_) |
2203           ty_float(_) |
2204           ty_estr(_) |
2205           ty_bare_fn(_) |
2206           ty_closure(_) |
2207           ty_infer(_) |
2208           ty_err |
2209           ty_param(_) |
2210           ty_self(_) |
2211           ty_type |
2212           ty_opaque_box |
2213           ty_opaque_closure_ptr(_) |
2214           ty_evec(_, _) |
2215           ty_unboxed_vec(_) => {
2216             false
2217           }
2218           ty_box(ref mt) |
2219           ty_uniq(ref mt) |
2220           ty_rptr(_, ref mt) => {
2221             return type_requires(cx, seen, r_ty, mt.ty);
2222           }
2223
2224           ty_ptr(*) => {
2225             false           // unsafe ptrs can always be NULL
2226           }
2227
2228           ty_trait(_, _, _, _) => {
2229             false
2230           }
2231
2232           ty_struct(ref did, _) if vec::contains(*seen, did) => {
2233             false
2234           }
2235
2236           ty_struct(did, ref substs) => {
2237               seen.push(did);
2238               let r = vec::any(struct_fields(cx, did, substs),
2239                                |f| type_requires(cx, seen, r_ty, f.mt.ty));
2240               seen.pop();
2241             r
2242           }
2243
2244           ty_tup(ref ts) => {
2245             ts.any(|t| type_requires(cx, seen, r_ty, *t))
2246           }
2247
2248           ty_enum(ref did, _) if vec::contains(*seen, did) => {
2249             false
2250           }
2251
2252             ty_enum(did, ref substs) => {
2253                 seen.push(did);
2254                 let vs = enum_variants(cx, did);
2255                 let r = vec::len(*vs) > 0u && vec::all(*vs, |variant| {
2256                     vec::any(variant.args, |aty| {
2257                         let sty = subst(cx, substs, *aty);
2258                         type_requires(cx, seen, r_ty, sty)
2259                     })
2260                 });
2261                 seen.pop();
2262                 r
2263             }
2264         };
2265
2266         debug!("subtypes_require(%s, %s)? %b",
2267                ::util::ppaux::ty_to_str(cx, r_ty),
2268                ::util::ppaux::ty_to_str(cx, ty),
2269                r);
2270
2271         return r;
2272     }
2273
2274     let seen = @mut ~[];
2275     !subtypes_require(cx, seen, r_ty, r_ty)
2276 }
2277
2278 pub fn type_structurally_contains(cx: ctxt,
2279                                   ty: t,
2280                                   test: &fn(x: &sty) -> bool)
2281                                -> bool {
2282     let sty = &get(ty).sty;
2283     debug!("type_structurally_contains: %s",
2284            ::util::ppaux::ty_to_str(cx, ty));
2285     if test(sty) { return true; }
2286     match *sty {
2287       ty_enum(did, ref substs) => {
2288         for vec::each(*enum_variants(cx, did)) |variant| {
2289             for variant.args.each |aty| {
2290                 let sty = subst(cx, substs, *aty);
2291                 if type_structurally_contains(cx, sty, test) { return true; }
2292             }
2293         }
2294         return false;
2295       }
2296       ty_struct(did, ref substs) => {
2297         for lookup_struct_fields(cx, did).each |field| {
2298             let ft = lookup_field_type(cx, did, field.id, substs);
2299             if type_structurally_contains(cx, ft, test) { return true; }
2300         }
2301         return false;
2302       }
2303
2304       ty_tup(ref ts) => {
2305         for ts.each |tt| {
2306             if type_structurally_contains(cx, *tt, test) { return true; }
2307         }
2308         return false;
2309       }
2310       ty_evec(ref mt, vstore_fixed(_)) => {
2311         return type_structurally_contains(cx, mt.ty, test);
2312       }
2313       _ => return false
2314     }
2315 }
2316
2317 pub fn type_structurally_contains_uniques(cx: ctxt, ty: t) -> bool {
2318     return type_structurally_contains(cx, ty, |sty| {
2319         match *sty {
2320           ty_uniq(_) |
2321           ty_evec(_, vstore_uniq) |
2322           ty_estr(vstore_uniq) => true,
2323           _ => false,
2324         }
2325     });
2326 }
2327
2328 pub fn type_is_integral(ty: t) -> bool {
2329     match get(ty).sty {
2330       ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
2331       _ => false
2332     }
2333 }
2334
2335 pub fn type_is_char(ty: t) -> bool {
2336     match get(ty).sty {
2337         ty_int(ty_char) => true,
2338         _ => false
2339     }
2340 }
2341
2342 pub fn type_is_fp(ty: t) -> bool {
2343     match get(ty).sty {
2344       ty_infer(FloatVar(_)) | ty_float(_) => true,
2345       _ => false
2346     }
2347 }
2348
2349 pub fn type_is_numeric(ty: t) -> bool {
2350     return type_is_integral(ty) || type_is_fp(ty);
2351 }
2352
2353 pub fn type_is_signed(ty: t) -> bool {
2354     match get(ty).sty {
2355       ty_int(_) => true,
2356       _ => false
2357     }
2358 }
2359
2360 // Whether a type is Plain Old Data -- meaning it does not contain pointers
2361 // that the cycle collector might care about.
2362 pub fn type_is_pod(cx: ctxt, ty: t) -> bool {
2363     let mut result = true;
2364     match get(ty).sty {
2365       // Scalar types
2366       ty_nil | ty_bot | ty_bool | ty_int(_) | ty_float(_) | ty_uint(_) |
2367       ty_type | ty_ptr(_) | ty_bare_fn(_) => result = true,
2368       // Boxed types
2369       ty_box(_) | ty_uniq(_) | ty_closure(_) |
2370       ty_estr(vstore_uniq) | ty_estr(vstore_box) |
2371       ty_evec(_, vstore_uniq) | ty_evec(_, vstore_box) |
2372       ty_trait(_, _, _, _) | ty_rptr(_,_) | ty_opaque_box => result = false,
2373       // Structural types
2374       ty_enum(did, ref substs) => {
2375         let variants = enum_variants(cx, did);
2376         for vec::each(*variants) |variant| {
2377             let tup_ty = mk_tup(cx, /*bad*/copy variant.args);
2378
2379             // Perform any type parameter substitutions.
2380             let tup_ty = subst(cx, substs, tup_ty);
2381             if !type_is_pod(cx, tup_ty) { result = false; }
2382         }
2383       }
2384       ty_tup(ref elts) => {
2385         for elts.each |elt| { if !type_is_pod(cx, *elt) { result = false; } }
2386       }
2387       ty_estr(vstore_fixed(_)) => result = true,
2388       ty_evec(ref mt, vstore_fixed(_)) | ty_unboxed_vec(ref mt) => {
2389         result = type_is_pod(cx, mt.ty);
2390       }
2391       ty_param(_) => result = false,
2392       ty_opaque_closure_ptr(_) => result = true,
2393       ty_struct(did, ref substs) => {
2394         result = vec::any(lookup_struct_fields(cx, did), |f| {
2395             let fty = ty::lookup_item_type(cx, f.id);
2396             let sty = subst(cx, substs, fty.ty);
2397             type_is_pod(cx, sty)
2398         });
2399       }
2400
2401       ty_estr(vstore_slice(*)) | ty_evec(_, vstore_slice(*)) => {
2402         result = false;
2403       }
2404
2405       ty_infer(*) | ty_self(*) | ty_err => {
2406         cx.sess.bug(~"non concrete type in type_is_pod");
2407       }
2408     }
2409
2410     return result;
2411 }
2412
2413 pub fn type_is_enum(ty: t) -> bool {
2414     match get(ty).sty {
2415       ty_enum(_, _) => return true,
2416       _ => return false
2417     }
2418 }
2419
2420 // Whether a type is enum like, that is a enum type with only nullary
2421 // constructors
2422 pub fn type_is_c_like_enum(cx: ctxt, ty: t) -> bool {
2423     match get(ty).sty {
2424         ty_enum(did, _) => {
2425             let variants = enum_variants(cx, did);
2426             if variants.len() == 0 {
2427                 false
2428             } else {
2429                 variants.all(|v| v.args.len() == 0)
2430             }
2431         }
2432         _ => false
2433     }
2434 }
2435
2436 pub fn type_param(ty: t) -> Option<uint> {
2437     match get(ty).sty {
2438       ty_param(p) => return Some(p.idx),
2439       _ => {/* fall through */ }
2440     }
2441     return None;
2442 }
2443
2444 // Returns the type and mutability of *t.
2445 //
2446 // The parameter `explicit` indicates if this is an *explicit* dereference.
2447 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
2448 pub fn deref(cx: ctxt, t: t, explicit: bool) -> Option<mt> {
2449     deref_sty(cx, &get(t).sty, explicit)
2450 }
2451
2452 pub fn deref_sty(cx: ctxt, sty: &sty, explicit: bool) -> Option<mt> {
2453     match *sty {
2454       ty_rptr(_, mt) | ty_box(mt) | ty_uniq(mt) => {
2455         Some(mt)
2456       }
2457
2458       ty_ptr(mt) if explicit => {
2459         Some(mt)
2460       }
2461
2462       ty_enum(did, ref substs) => {
2463         let variants = enum_variants(cx, did);
2464         if vec::len(*variants) == 1u && vec::len(variants[0].args) == 1u {
2465             let v_t = subst(cx, substs, variants[0].args[0]);
2466             Some(mt {ty: v_t, mutbl: ast::m_imm})
2467         } else {
2468             None
2469         }
2470       }
2471
2472       ty_struct(did, ref substs) => {
2473         let fields = struct_fields(cx, did, substs);
2474         if fields.len() == 1 && fields[0].ident ==
2475                 syntax::parse::token::special_idents::unnamed_field {
2476             Some(mt {ty: fields[0].mt.ty, mutbl: ast::m_imm})
2477         } else {
2478             None
2479         }
2480       }
2481
2482       _ => None
2483     }
2484 }
2485
2486 pub fn type_autoderef(cx: ctxt, t: t) -> t {
2487     let mut t = t;
2488     loop {
2489         match deref(cx, t, false) {
2490           None => return t,
2491           Some(mt) => t = mt.ty
2492         }
2493     }
2494 }
2495
2496 // Returns the type and mutability of t[i]
2497 pub fn index(t: t) -> Option<mt> {
2498     index_sty(&get(t).sty)
2499 }
2500
2501 pub fn index_sty(sty: &sty) -> Option<mt> {
2502     match *sty {
2503       ty_evec(mt, _) => Some(mt),
2504       ty_estr(_) => Some(mt {ty: mk_u8(), mutbl: ast::m_imm}),
2505       _ => None
2506     }
2507 }
2508
2509 /**
2510  * Enforces an arbitrary but consistent total ordering over
2511  * free regions.  This is needed for establishing a consistent
2512  * LUB in region_inference. */
2513 impl cmp::TotalOrd for FreeRegion {
2514     fn cmp(&self, other: &FreeRegion) -> Ordering {
2515         cmp::cmp2(&self.scope_id, &self.bound_region,
2516                   &other.scope_id, &other.bound_region)
2517     }
2518 }
2519
2520 impl cmp::TotalEq for FreeRegion {
2521     fn equals(&self, other: &FreeRegion) -> bool {
2522         *self == *other
2523     }
2524 }
2525
2526 /**
2527  * Enforces an arbitrary but consistent total ordering over
2528  * bound regions.  This is needed for establishing a consistent
2529  * LUB in region_inference. */
2530 impl cmp::TotalOrd for bound_region {
2531     fn cmp(&self, other: &bound_region) -> Ordering {
2532         match (self, other) {
2533             (&ty::br_self, &ty::br_self) => cmp::Equal,
2534             (&ty::br_self, _) => cmp::Less,
2535
2536             (&ty::br_anon(ref a1), &ty::br_anon(ref a2)) => a1.cmp(a2),
2537             (&ty::br_anon(*), _) => cmp::Less,
2538
2539             (&ty::br_named(ref a1), &ty::br_named(ref a2)) => a1.repr.cmp(&a2.repr),
2540             (&ty::br_named(*), _) => cmp::Less,
2541
2542             (&ty::br_cap_avoid(ref a1, @ref b1),
2543              &ty::br_cap_avoid(ref a2, @ref b2)) => cmp::cmp2(a1, b1, a2, b2),
2544             (&ty::br_cap_avoid(*), _) => cmp::Less,
2545
2546             (&ty::br_fresh(ref a1), &ty::br_fresh(ref a2)) => a1.cmp(a2),
2547             (&ty::br_fresh(*), _) => cmp::Less,
2548         }
2549     }
2550 }
2551
2552 impl cmp::TotalEq for bound_region {
2553     fn equals(&self, other: &bound_region) -> bool {
2554         *self == *other
2555     }
2556 }
2557
2558 impl to_bytes::IterBytes for vstore {
2559     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2560         match *self {
2561           vstore_fixed(ref u) =>
2562           to_bytes::iter_bytes_2(&0u8, u, lsb0, f),
2563
2564           vstore_uniq => 1u8.iter_bytes(lsb0, f),
2565           vstore_box => 2u8.iter_bytes(lsb0, f),
2566
2567           vstore_slice(ref r) =>
2568           to_bytes::iter_bytes_2(&3u8, r, lsb0, f),
2569         }
2570     }
2571 }
2572
2573 impl to_bytes::IterBytes for substs {
2574     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2575           to_bytes::iter_bytes_3(&self.self_r,
2576                                  &self.self_ty,
2577                                  &self.tps, lsb0, f)
2578     }
2579 }
2580
2581 impl to_bytes::IterBytes for mt {
2582     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2583           to_bytes::iter_bytes_2(&self.ty,
2584                                  &self.mutbl, lsb0, f)
2585     }
2586 }
2587
2588 impl to_bytes::IterBytes for field {
2589     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2590           to_bytes::iter_bytes_2(&self.ident,
2591                                  &self.mt, lsb0, f)
2592     }
2593 }
2594
2595 impl to_bytes::IterBytes for FnSig {
2596     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2597         to_bytes::iter_bytes_2(&self.inputs,
2598                                &self.output,
2599                                lsb0, f);
2600     }
2601 }
2602
2603 impl to_bytes::IterBytes for sty {
2604     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2605         match *self {
2606           ty_nil => 0u8.iter_bytes(lsb0, f),
2607           ty_bool => 1u8.iter_bytes(lsb0, f),
2608
2609           ty_int(ref t) =>
2610           to_bytes::iter_bytes_2(&2u8, t, lsb0, f),
2611
2612           ty_uint(ref t) =>
2613           to_bytes::iter_bytes_2(&3u8, t, lsb0, f),
2614
2615           ty_float(ref t) =>
2616           to_bytes::iter_bytes_2(&4u8, t, lsb0, f),
2617
2618           ty_estr(ref v) =>
2619           to_bytes::iter_bytes_2(&5u8, v, lsb0, f),
2620
2621           ty_enum(ref did, ref substs) =>
2622           to_bytes::iter_bytes_3(&6u8, did, substs, lsb0, f),
2623
2624           ty_box(ref mt) =>
2625           to_bytes::iter_bytes_2(&7u8, mt, lsb0, f),
2626
2627           ty_evec(ref mt, ref v) =>
2628           to_bytes::iter_bytes_3(&8u8, mt, v, lsb0, f),
2629
2630           ty_unboxed_vec(ref mt) =>
2631           to_bytes::iter_bytes_2(&9u8, mt, lsb0, f),
2632
2633           ty_tup(ref ts) =>
2634           to_bytes::iter_bytes_2(&10u8, ts, lsb0, f),
2635
2636           ty_bare_fn(ref ft) =>
2637           to_bytes::iter_bytes_2(&12u8, ft, lsb0, f),
2638
2639           ty_self(ref did) => to_bytes::iter_bytes_2(&13u8, did, lsb0, f),
2640
2641           ty_infer(ref v) =>
2642           to_bytes::iter_bytes_2(&14u8, v, lsb0, f),
2643
2644           ty_param(ref p) =>
2645           to_bytes::iter_bytes_2(&15u8, p, lsb0, f),
2646
2647           ty_type => 16u8.iter_bytes(lsb0, f),
2648           ty_bot => 17u8.iter_bytes(lsb0, f),
2649
2650           ty_ptr(ref mt) =>
2651           to_bytes::iter_bytes_2(&18u8, mt, lsb0, f),
2652
2653           ty_uniq(ref mt) =>
2654           to_bytes::iter_bytes_2(&19u8, mt, lsb0, f),
2655
2656           ty_trait(ref did, ref substs, ref v, ref mutbl) =>
2657           to_bytes::iter_bytes_5(&20u8, did, substs, v, mutbl, lsb0, f),
2658
2659           ty_opaque_closure_ptr(ref ck) =>
2660           to_bytes::iter_bytes_2(&21u8, ck, lsb0, f),
2661
2662           ty_opaque_box => 22u8.iter_bytes(lsb0, f),
2663
2664           ty_struct(ref did, ref substs) =>
2665           to_bytes::iter_bytes_3(&23u8, did, substs, lsb0, f),
2666
2667           ty_rptr(ref r, ref mt) =>
2668           to_bytes::iter_bytes_3(&24u8, r, mt, lsb0, f),
2669
2670           ty_err => 25u8.iter_bytes(lsb0, f),
2671
2672           ty_closure(ref ct) =>
2673           to_bytes::iter_bytes_2(&26u8, ct, lsb0, f),
2674         }
2675     }
2676 }
2677
2678 pub fn node_id_to_trait_ref(cx: ctxt, id: ast::node_id) -> @ty::TraitRef {
2679     match cx.trait_refs.find(&id) {
2680        Some(&t) => t,
2681        None => cx.sess.bug(
2682            fmt!("node_id_to_trait_ref: no trait ref for node `%s`",
2683                 ast_map::node_id_to_str(cx.items, id,
2684                                         cx.sess.parse_sess.interner)))
2685     }
2686 }
2687
2688 pub fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
2689     //io::println(fmt!("%?/%?", id, cx.node_types.len()));
2690     match cx.node_types.find(&(id as uint)) {
2691        Some(&t) => t,
2692        None => cx.sess.bug(
2693            fmt!("node_id_to_type: no type for node `%s`",
2694                 ast_map::node_id_to_str(cx.items, id,
2695                                         cx.sess.parse_sess.interner)))
2696     }
2697 }
2698
2699 pub fn node_id_to_type_params(cx: ctxt, id: ast::node_id) -> ~[t] {
2700     match cx.node_type_substs.find(&id) {
2701       None => return ~[],
2702       Some(ts) => return /*bad*/ copy *ts
2703     }
2704 }
2705
2706 fn node_id_has_type_params(cx: ctxt, id: ast::node_id) -> bool {
2707     cx.node_type_substs.contains_key(&id)
2708 }
2709
2710 pub fn ty_fn_sig(fty: t) -> FnSig {
2711     match get(fty).sty {
2712         ty_bare_fn(ref f) => copy f.sig,
2713         ty_closure(ref f) => copy f.sig,
2714         ref s => {
2715             fail!(fmt!("ty_fn_sig() called on non-fn type: %?", s))
2716         }
2717     }
2718 }
2719
2720 // Type accessors for substructures of types
2721 pub fn ty_fn_args(fty: t) -> ~[arg] {
2722     match get(fty).sty {
2723         ty_bare_fn(ref f) => copy f.sig.inputs,
2724         ty_closure(ref f) => copy f.sig.inputs,
2725         ref s => {
2726             fail!(fmt!("ty_fn_args() called on non-fn type: %?", s))
2727         }
2728     }
2729 }
2730
2731 pub fn ty_closure_sigil(fty: t) -> Sigil {
2732     match get(fty).sty {
2733         ty_closure(ref f) => f.sigil,
2734         ref s => {
2735             fail!(fmt!("ty_closure_sigil() called on non-closure type: %?",
2736                        s))
2737         }
2738     }
2739 }
2740
2741 pub fn ty_fn_purity(fty: t) -> ast::purity {
2742     match get(fty).sty {
2743         ty_bare_fn(ref f) => f.purity,
2744         ty_closure(ref f) => f.purity,
2745         ref s => {
2746             fail!(fmt!("ty_fn_purity() called on non-fn type: %?", s))
2747         }
2748     }
2749 }
2750
2751 pub fn ty_fn_ret(fty: t) -> t {
2752     match get(fty).sty {
2753         ty_bare_fn(ref f) => f.sig.output,
2754         ty_closure(ref f) => f.sig.output,
2755         ref s => {
2756             fail!(fmt!("ty_fn_ret() called on non-fn type: %?", s))
2757         }
2758     }
2759 }
2760
2761 pub fn is_fn_ty(fty: t) -> bool {
2762     match get(fty).sty {
2763         ty_bare_fn(_) => true,
2764         ty_closure(_) => true,
2765         _ => false
2766     }
2767 }
2768
2769 pub fn ty_vstore(ty: t) -> vstore {
2770     match get(ty).sty {
2771         ty_evec(_, vstore) => vstore,
2772         ty_estr(vstore) => vstore,
2773         ref s => fail!(fmt!("ty_vstore() called on invalid sty: %?", s))
2774     }
2775 }
2776
2777 pub fn ty_region(tcx: ctxt,
2778                  span: span,
2779                  ty: t) -> Region {
2780     match get(ty).sty {
2781         ty_rptr(r, _) => r,
2782         ty_evec(_, vstore_slice(r)) => r,
2783         ty_estr(vstore_slice(r)) => r,
2784         ref s => {
2785             tcx.sess.span_bug(
2786                 span,
2787                 fmt!("ty_region() invoked on in appropriate ty: %?", s));
2788         }
2789     }
2790 }
2791
2792 pub fn replace_closure_return_type(tcx: ctxt, fn_type: t, ret_type: t) -> t {
2793     /*!
2794      *
2795      * Returns a new function type based on `fn_type` but returning a value of
2796      * type `ret_type` instead. */
2797
2798     match ty::get(fn_type).sty {
2799         ty::ty_closure(ref fty) => {
2800             ty::mk_closure(tcx, ClosureTy {
2801                 sig: FnSig {output: ret_type, ..copy fty.sig},
2802                 ..copy *fty
2803             })
2804         }
2805         _ => {
2806             tcx.sess.bug(fmt!(
2807                 "replace_fn_ret() invoked with non-fn-type: %s",
2808                 ty_to_str(tcx, fn_type)));
2809         }
2810     }
2811 }
2812
2813 // Returns a vec of all the input and output types of fty.
2814 pub fn tys_in_fn_sig(sig: &FnSig) -> ~[t] {
2815     vec::append_one(sig.inputs.map(|a| a.ty), sig.output)
2816 }
2817
2818 // Type accessors for AST nodes
2819 pub fn block_ty(cx: ctxt, b: &ast::blk) -> t {
2820     return node_id_to_type(cx, b.node.id);
2821 }
2822
2823
2824 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
2825 // doesn't provide type parameter substitutions.
2826 pub fn pat_ty(cx: ctxt, pat: @ast::pat) -> t {
2827     return node_id_to_type(cx, pat.id);
2828 }
2829
2830
2831 // Returns the type of an expression as a monotype.
2832 //
2833 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression.  That is, in
2834 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
2835 // auto-ref.  The type returned by this function does not consider such
2836 // adjustments.  See `expr_ty_adjusted()` instead.
2837 //
2838 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
2839 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
2840 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
2841 // expr_ty_params_and_ty() below.
2842 pub fn expr_ty(cx: ctxt, expr: @ast::expr) -> t {
2843     return node_id_to_type(cx, expr.id);
2844 }
2845
2846 pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
2847     /*!
2848      *
2849      * Returns the type of `expr`, considering any `AutoAdjustment`
2850      * entry recorded for that expression.
2851      *
2852      * It would almost certainly be better to store the adjusted ty in with
2853      * the `AutoAdjustment`, but I opted not to do this because it would
2854      * require serializing and deserializing the type and, although that's not
2855      * hard to do, I just hate that code so much I didn't want to touch it
2856      * unless it was to fix it properly, which seemed a distraction from the
2857      * task at hand! -nmatsakis
2858      */
2859
2860     let unadjusted_ty = expr_ty(cx, expr);
2861     adjust_ty(cx, expr.span, unadjusted_ty, cx.adjustments.find(&expr.id))
2862 }
2863
2864 pub fn adjust_ty(cx: ctxt,
2865                  span: span,
2866                  unadjusted_ty: ty::t,
2867                  adjustment: Option<&@AutoAdjustment>) -> ty::t
2868 {
2869     /*! See `expr_ty_adjusted` */
2870
2871     return match adjustment {
2872         None => unadjusted_ty,
2873
2874         Some(&@AutoAddEnv(r, s)) => {
2875             match ty::get(unadjusted_ty).sty {
2876                 ty::ty_bare_fn(ref b) => {
2877                     ty::mk_closure(
2878                         cx,
2879                         ty::ClosureTy {purity: b.purity,
2880                                        sigil: s,
2881                                        onceness: ast::Many,
2882                                        region: r,
2883                                        sig: copy b.sig})
2884                 }
2885                 ref b => {
2886                     cx.sess.bug(
2887                         fmt!("add_env adjustment on non-bare-fn: %?", b));
2888                 }
2889             }
2890         }
2891
2892         Some(&@AutoDerefRef(ref adj)) => {
2893             let mut adjusted_ty = unadjusted_ty;
2894
2895             for uint::range(0, adj.autoderefs) |i| {
2896                 match ty::deref(cx, adjusted_ty, true) {
2897                     Some(mt) => { adjusted_ty = mt.ty; }
2898                     None => {
2899                         cx.sess.span_bug(
2900                             span,
2901                             fmt!("The %uth autoderef failed: %s",
2902                                  i, ty_to_str(cx,
2903                                               adjusted_ty)));
2904                     }
2905                 }
2906             }
2907
2908             match adj.autoref {
2909                 None => adjusted_ty,
2910                 Some(ref autoref) => {
2911                     match autoref.kind {
2912                         AutoPtr => {
2913                             mk_rptr(cx, autoref.region,
2914                                     mt {ty: adjusted_ty,
2915                                         mutbl: autoref.mutbl})
2916                         }
2917
2918                         AutoBorrowVec => {
2919                             borrow_vec(cx, span, autoref, adjusted_ty)
2920                         }
2921
2922                         AutoBorrowVecRef => {
2923                             adjusted_ty = borrow_vec(cx, span, autoref,
2924                                                      adjusted_ty);
2925                             mk_rptr(cx, autoref.region,
2926                                     mt {ty: adjusted_ty, mutbl: ast::m_imm})
2927                         }
2928
2929                         AutoBorrowFn => {
2930                             borrow_fn(cx, span, autoref, adjusted_ty)
2931                         }
2932                     }
2933                 }
2934             }
2935         }
2936     };
2937
2938     fn borrow_vec(cx: ctxt, span: span,
2939                   autoref: &AutoRef, ty: ty::t) -> ty::t {
2940         match get(ty).sty {
2941             ty_evec(mt, _) => {
2942                 ty::mk_evec(cx, mt {ty: mt.ty, mutbl: autoref.mutbl},
2943                             vstore_slice(autoref.region))
2944             }
2945
2946             ty_estr(_) => {
2947                 ty::mk_estr(cx, vstore_slice(autoref.region))
2948             }
2949
2950             ref s => {
2951                 cx.sess.span_bug(
2952                     span,
2953                     fmt!("borrow-vec associated with bad sty: %?",
2954                          s));
2955             }
2956         }
2957     }
2958
2959     fn borrow_fn(cx: ctxt, span: span,
2960                  autoref: &AutoRef, ty: ty::t) -> ty::t {
2961         match get(ty).sty {
2962             ty_closure(ref fty) => {
2963                 ty::mk_closure(cx, ClosureTy {
2964                     sigil: BorrowedSigil,
2965                     region: autoref.region,
2966                     ..copy *fty
2967                 })
2968             }
2969
2970             ref s => {
2971                 cx.sess.span_bug(
2972                     span,
2973                     fmt!("borrow-fn associated with bad sty: %?",
2974                          s));
2975             }
2976         }
2977     }
2978 }
2979
2980 pub struct ParamsTy {
2981     params: ~[t],
2982     ty: t
2983 }
2984
2985 pub fn expr_ty_params_and_ty(cx: ctxt,
2986                              expr: @ast::expr)
2987                           -> ParamsTy {
2988     ParamsTy {
2989         params: node_id_to_type_params(cx, expr.id),
2990         ty: node_id_to_type(cx, expr.id)
2991     }
2992 }
2993
2994 pub fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
2995     return node_id_has_type_params(cx, expr.id);
2996 }
2997
2998 pub fn method_call_type_param_defs(
2999     tcx: ctxt,
3000     method_map: typeck::method_map,
3001     id: ast::node_id) -> Option<@~[TypeParameterDef]>
3002 {
3003     do method_map.find(&id).map |method| {
3004         match method.origin {
3005           typeck::method_static(did) => {
3006             // n.b.: When we encode impl methods, the bounds
3007             // that we encode include both the impl bounds
3008             // and then the method bounds themselves...
3009             ty::lookup_item_type(tcx, did).generics.type_param_defs
3010           }
3011           typeck::method_param(typeck::method_param {
3012               trait_id: trt_id,
3013               method_num: n_mth, _}) |
3014           typeck::method_trait(trt_id, n_mth, _) |
3015           typeck::method_self(trt_id, n_mth) |
3016           typeck::method_super(trt_id, n_mth) => {
3017             // ...trait methods bounds, in contrast, include only the
3018             // method bounds, so we must preprend the tps from the
3019             // trait itself.  This ought to be harmonized.
3020             let trait_type_param_defs =
3021                 ty::lookup_trait_def(tcx, trt_id).generics.type_param_defs;
3022             @vec::append(
3023                 copy *trait_type_param_defs,
3024                 *ty::trait_method(tcx, trt_id, n_mth).generics.type_param_defs)
3025           }
3026         }
3027     }
3028 }
3029
3030 pub fn resolve_expr(tcx: ctxt, expr: @ast::expr) -> ast::def {
3031     match tcx.def_map.find(&expr.id) {
3032         Some(&def) => def,
3033         None => {
3034             tcx.sess.span_bug(expr.span, fmt!(
3035                 "No def-map entry for expr %?", expr.id));
3036         }
3037     }
3038 }
3039
3040 pub fn expr_is_lval(tcx: ctxt,
3041                     method_map: typeck::method_map,
3042                     e: @ast::expr) -> bool {
3043     match expr_kind(tcx, method_map, e) {
3044         LvalueExpr => true,
3045         RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
3046     }
3047 }
3048
3049 /// We categorize expressions into three kinds.  The distinction between
3050 /// lvalue/rvalue is fundamental to the language.  The distinction between the
3051 /// two kinds of rvalues is an artifact of trans which reflects how we will
3052 /// generate code for that kind of expression.  See trans/expr.rs for more
3053 /// information.
3054 pub enum ExprKind {
3055     LvalueExpr,
3056     RvalueDpsExpr,
3057     RvalueDatumExpr,
3058     RvalueStmtExpr
3059 }
3060
3061 pub fn expr_kind(tcx: ctxt,
3062                  method_map: typeck::method_map,
3063                  expr: @ast::expr) -> ExprKind {
3064     if method_map.contains_key(&expr.id) {
3065         // Overloaded operations are generally calls, and hence they are
3066         // generated via DPS.  However, assign_op (e.g., `x += y`) is an
3067         // exception, as its result is always unit.
3068         return match expr.node {
3069             ast::expr_assign_op(*) => RvalueStmtExpr,
3070             _ => RvalueDpsExpr
3071         };
3072     }
3073
3074     match expr.node {
3075         ast::expr_path(*) => {
3076             match resolve_expr(tcx, expr) {
3077                 ast::def_variant(*) | ast::def_struct(*) => RvalueDpsExpr,
3078
3079                 // Fn pointers are just scalar values.
3080                 ast::def_fn(*) | ast::def_static_method(*) => RvalueDatumExpr,
3081
3082                 // Note: there is actually a good case to be made that
3083                 // def_args, particularly those of immediate type, ought to
3084                 // considered rvalues.
3085                 ast::def_const(*) |
3086                 ast::def_binding(*) |
3087                 ast::def_upvar(*) |
3088                 ast::def_arg(*) |
3089                 ast::def_local(*) |
3090                 ast::def_self(*) => LvalueExpr,
3091
3092                 def => {
3093                     tcx.sess.span_bug(expr.span, fmt!(
3094                         "Uncategorized def for expr %?: %?",
3095                         expr.id, def));
3096                 }
3097             }
3098         }
3099
3100         ast::expr_unary(ast::deref, _) |
3101         ast::expr_field(*) |
3102         ast::expr_index(*) => {
3103             LvalueExpr
3104         }
3105
3106         ast::expr_call(*) |
3107         ast::expr_method_call(*) |
3108         ast::expr_struct(*) |
3109         ast::expr_tup(*) |
3110         ast::expr_if(*) |
3111         ast::expr_match(*) |
3112         ast::expr_fn_block(*) |
3113         ast::expr_loop_body(*) |
3114         ast::expr_do_body(*) |
3115         ast::expr_block(*) |
3116         ast::expr_copy(*) |
3117         ast::expr_repeat(*) |
3118         ast::expr_lit(@codemap::spanned {node: lit_str(_), _}) |
3119         ast::expr_vstore(_, ast::expr_vstore_slice) |
3120         ast::expr_vstore(_, ast::expr_vstore_mut_slice) |
3121         ast::expr_vec(*) => {
3122             RvalueDpsExpr
3123         }
3124
3125         ast::expr_cast(*) => {
3126             match tcx.node_types.find(&(expr.id as uint)) {
3127                 Some(&t) => {
3128                     if ty::type_is_immediate(t) {
3129                         RvalueDatumExpr
3130                     } else {
3131                         RvalueDpsExpr
3132                     }
3133                 }
3134                 None => {
3135                     // Technically, it should not happen that the expr is not
3136                     // present within the table.  However, it DOES happen
3137                     // during type check, because the final types from the
3138                     // expressions are not yet recorded in the tcx.  At that
3139                     // time, though, we are only interested in knowing lvalue
3140                     // vs rvalue.  It would be better to base this decision on
3141                     // the AST type in cast node---but (at the time of this
3142                     // writing) it's not easy to distinguish casts to traits
3143                     // from other casts based on the AST.  This should be
3144                     // easier in the future, when casts to traits would like
3145                     // like @Foo, ~Foo, or &Foo.
3146                     RvalueDatumExpr
3147                 }
3148             }
3149         }
3150
3151         ast::expr_break(*) |
3152         ast::expr_again(*) |
3153         ast::expr_ret(*) |
3154         ast::expr_log(*) |
3155         ast::expr_while(*) |
3156         ast::expr_loop(*) |
3157         ast::expr_assign(*) |
3158         ast::expr_swap(*) |
3159         ast::expr_inline_asm(*) |
3160         ast::expr_assign_op(*) => {
3161             RvalueStmtExpr
3162         }
3163
3164         ast::expr_lit(_) | // Note: lit_str is carved out above
3165         ast::expr_unary(*) |
3166         ast::expr_addr_of(*) |
3167         ast::expr_binary(*) |
3168         ast::expr_vstore(_, ast::expr_vstore_box) |
3169         ast::expr_vstore(_, ast::expr_vstore_mut_box) |
3170         ast::expr_vstore(_, ast::expr_vstore_uniq) => {
3171             RvalueDatumExpr
3172         }
3173
3174         ast::expr_paren(e) => expr_kind(tcx, method_map, e),
3175
3176         ast::expr_mac(*) => {
3177             tcx.sess.span_bug(
3178                 expr.span,
3179                 "macro expression remains after expansion");
3180         }
3181     }
3182 }
3183
3184 pub fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
3185     match s.node {
3186       ast::stmt_decl(_, id) | stmt_expr(_, id) | stmt_semi(_, id) => {
3187         return id;
3188       }
3189       ast::stmt_mac(*) => fail!(~"unexpanded macro in trans")
3190     }
3191 }
3192
3193 pub fn field_idx(id: ast::ident, fields: &[field]) -> Option<uint> {
3194     let mut i = 0u;
3195     for fields.each |f| { if f.ident == id { return Some(i); } i += 1u; }
3196     return None;
3197 }
3198
3199 pub fn field_idx_strict(tcx: ty::ctxt, id: ast::ident, fields: &[field])
3200                      -> uint {
3201     let mut i = 0u;
3202     for fields.each |f| { if f.ident == id { return i; } i += 1u; }
3203     tcx.sess.bug(fmt!(
3204         "No field named `%s` found in the list of fields `%?`",
3205         *tcx.sess.str_of(id),
3206         fields.map(|f| tcx.sess.str_of(f.ident))));
3207 }
3208
3209 pub fn method_idx(id: ast::ident, meths: &[@method]) -> Option<uint> {
3210     vec::position(meths, |m| m.ident == id)
3211 }
3212
3213 /// Returns a vector containing the indices of all type parameters that appear
3214 /// in `ty`.  The vector may contain duplicates.  Probably should be converted
3215 /// to a bitset or some other representation.
3216 pub fn param_tys_in_type(ty: t) -> ~[param_ty] {
3217     let mut rslt = ~[];
3218     do walk_ty(ty) |ty| {
3219         match get(ty).sty {
3220           ty_param(p) => {
3221             rslt.push(p);
3222           }
3223           _ => ()
3224         }
3225     }
3226     rslt
3227 }
3228
3229 pub fn occurs_check(tcx: ctxt, sp: span, vid: TyVid, rt: t) {
3230     // Returns a vec of all the type variables occurring in `ty`. It may
3231     // contain duplicates.  (Integral type vars aren't counted.)
3232     fn vars_in_type(ty: t) -> ~[TyVid] {
3233         let mut rslt = ~[];
3234         do walk_ty(ty) |ty| {
3235             match get(ty).sty {
3236               ty_infer(TyVar(v)) => rslt.push(v),
3237               _ => ()
3238             }
3239         }
3240         rslt
3241     }
3242
3243     // Fast path
3244     if !type_needs_infer(rt) { return; }
3245
3246     // Occurs check!
3247     if vec::contains(vars_in_type(rt), &vid) {
3248             // Maybe this should be span_err -- however, there's an
3249             // assertion later on that the type doesn't contain
3250             // variables, so in this case we have to be sure to die.
3251             tcx.sess.span_fatal
3252                 (sp, ~"type inference failed because I \
3253                      could not find a type\n that's both of the form "
3254                  + ::util::ppaux::ty_to_str(tcx, mk_var(tcx, vid)) +
3255                  ~" and of the form " + ::util::ppaux::ty_to_str(tcx, rt) +
3256                  ~" - such a type would have to be infinitely large.");
3257     }
3258 }
3259
3260 pub fn ty_sort_str(cx: ctxt, t: t) -> ~str {
3261     match get(t).sty {
3262       ty_nil | ty_bot | ty_bool | ty_int(_) |
3263       ty_uint(_) | ty_float(_) | ty_estr(_) |
3264       ty_type | ty_opaque_box | ty_opaque_closure_ptr(_) => {
3265         ::util::ppaux::ty_to_str(cx, t)
3266       }
3267
3268       ty_enum(id, _) => fmt!("enum %s", item_path_str(cx, id)),
3269       ty_box(_) => ~"@-ptr",
3270       ty_uniq(_) => ~"~-ptr",
3271       ty_evec(_, _) => ~"vector",
3272       ty_unboxed_vec(_) => ~"unboxed vector",
3273       ty_ptr(_) => ~"*-ptr",
3274       ty_rptr(_, _) => ~"&-ptr",
3275       ty_bare_fn(_) => ~"extern fn",
3276       ty_closure(_) => ~"fn",
3277       ty_trait(id, _, _, _) => fmt!("trait %s", item_path_str(cx, id)),
3278       ty_struct(id, _) => fmt!("struct %s", item_path_str(cx, id)),
3279       ty_tup(_) => ~"tuple",
3280       ty_infer(TyVar(_)) => ~"inferred type",
3281       ty_infer(IntVar(_)) => ~"integral variable",
3282       ty_infer(FloatVar(_)) => ~"floating-point variable",
3283       ty_param(_) => ~"type parameter",
3284       ty_self(_) => ~"self",
3285       ty_err => ~"type error"
3286     }
3287 }
3288
3289 pub fn type_err_to_str(cx: ctxt, err: &type_err) -> ~str {
3290     /*!
3291      *
3292      * Explains the source of a type err in a short,
3293      * human readable way.  This is meant to be placed in
3294      * parentheses after some larger message.  You should
3295      * also invoke `note_and_explain_type_err()` afterwards
3296      * to present additional details, particularly when
3297      * it comes to lifetime-related errors. */
3298
3299     fn terr_vstore_kind_to_str(k: terr_vstore_kind) -> ~str {
3300         match k {
3301             terr_vec => ~"[]",
3302             terr_str => ~"str",
3303             terr_fn => ~"fn",
3304             terr_trait => ~"trait"
3305         }
3306     }
3307
3308     match *err {
3309         terr_mismatch => ~"types differ",
3310         terr_purity_mismatch(values) => {
3311             fmt!("expected %s fn but found %s fn",
3312                  values.expected.to_str(), values.found.to_str())
3313         }
3314         terr_abi_mismatch(values) => {
3315             fmt!("expected %s fn but found %s fn",
3316                  values.expected.to_str(), values.found.to_str())
3317         }
3318         terr_onceness_mismatch(values) => {
3319             fmt!("expected %s fn but found %s fn",
3320                  values.expected.to_str(), values.found.to_str())
3321         }
3322         terr_sigil_mismatch(values) => {
3323             fmt!("expected %s closure, found %s closure",
3324                  values.expected.to_str(),
3325                  values.found.to_str())
3326         }
3327         terr_mutability => ~"values differ in mutability",
3328         terr_box_mutability => ~"boxed values differ in mutability",
3329         terr_vec_mutability => ~"vectors differ in mutability",
3330         terr_ptr_mutability => ~"pointers differ in mutability",
3331         terr_ref_mutability => ~"references differ in mutability",
3332         terr_ty_param_size(values) => {
3333             fmt!("expected a type with %? type params \
3334                   but found one with %? type params",
3335                  values.expected, values.found)
3336         }
3337         terr_tuple_size(values) => {
3338             fmt!("expected a tuple with %? elements \
3339                   but found one with %? elements",
3340                  values.expected, values.found)
3341         }
3342         terr_record_size(values) => {
3343             fmt!("expected a record with %? fields \
3344                   but found one with %? fields",
3345                  values.expected, values.found)
3346         }
3347         terr_record_mutability => {
3348             ~"record elements differ in mutability"
3349         }
3350         terr_record_fields(values) => {
3351             fmt!("expected a record with field `%s` but found one with field \
3352                   `%s`",
3353                  *cx.sess.str_of(values.expected),
3354                  *cx.sess.str_of(values.found))
3355         }
3356         terr_arg_count => ~"incorrect number of function parameters",
3357         terr_regions_does_not_outlive(*) => {
3358             fmt!("lifetime mismatch")
3359         }
3360         terr_regions_not_same(*) => {
3361             fmt!("lifetimes are not the same")
3362         }
3363         terr_regions_no_overlap(*) => {
3364             fmt!("lifetimes do not intersect")
3365         }
3366         terr_regions_insufficiently_polymorphic(br, _) => {
3367             fmt!("expected bound lifetime parameter %s, \
3368                   but found concrete lifetime",
3369                  bound_region_to_str(cx, br))
3370         }
3371         terr_regions_overly_polymorphic(br, _) => {
3372             fmt!("expected concrete lifetime, \
3373                   but found bound lifetime parameter %s",
3374                  bound_region_to_str(cx, br))
3375         }
3376         terr_vstores_differ(k, ref values) => {
3377             fmt!("%s storage differs: expected %s but found %s",
3378                  terr_vstore_kind_to_str(k),
3379                  vstore_to_str(cx, (*values).expected),
3380                  vstore_to_str(cx, (*values).found))
3381         }
3382         terr_trait_stores_differ(_, ref values) => {
3383             fmt!("trait storage differs: expected %s but found %s",
3384                  trait_store_to_str(cx, (*values).expected),
3385                  trait_store_to_str(cx, (*values).found))
3386         }
3387         terr_in_field(err, fname) => {
3388             fmt!("in field `%s`, %s", *cx.sess.str_of(fname),
3389                  type_err_to_str(cx, err))
3390         }
3391         terr_sorts(values) => {
3392             fmt!("expected %s but found %s",
3393                  ty_sort_str(cx, values.expected),
3394                  ty_sort_str(cx, values.found))
3395         }
3396         terr_traits(values) => {
3397             fmt!("expected trait %s but found trait %s",
3398                  item_path_str(cx, values.expected),
3399                  item_path_str(cx, values.found))
3400         }
3401         terr_self_substs => {
3402             ~"inconsistent self substitution" // XXX this is more of a bug
3403         }
3404         terr_integer_as_char => {
3405             fmt!("expected an integral type but found char")
3406         }
3407         terr_int_mismatch(ref values) => {
3408             fmt!("expected %s but found %s",
3409                  values.expected.to_str(),
3410                  values.found.to_str())
3411         }
3412         terr_float_mismatch(ref values) => {
3413             fmt!("expected %s but found %s",
3414                  values.expected.to_str(),
3415                  values.found.to_str())
3416         }
3417     }
3418 }
3419
3420 pub fn note_and_explain_type_err(cx: ctxt, err: &type_err) {
3421     match *err {
3422         terr_regions_does_not_outlive(subregion, superregion) => {
3423             note_and_explain_region(cx, ~"", subregion, ~"...");
3424             note_and_explain_region(cx, ~"...does not necessarily outlive ",
3425                                     superregion, ~"");
3426         }
3427         terr_regions_not_same(region1, region2) => {
3428             note_and_explain_region(cx, ~"", region1, ~"...");
3429             note_and_explain_region(cx, ~"...is not the same lifetime as ",
3430                                     region2, ~"");
3431         }
3432         terr_regions_no_overlap(region1, region2) => {
3433             note_and_explain_region(cx, ~"", region1, ~"...");
3434             note_and_explain_region(cx, ~"...does not overlap ",
3435                                     region2, ~"");
3436         }
3437         terr_regions_insufficiently_polymorphic(_, conc_region) => {
3438             note_and_explain_region(cx,
3439                                     ~"concrete lifetime that was found is ",
3440                                     conc_region, ~"");
3441         }
3442         terr_regions_overly_polymorphic(_, conc_region) => {
3443             note_and_explain_region(cx,
3444                                     ~"expected concrete lifetime is ",
3445                                     conc_region, ~"");
3446         }
3447         _ => {}
3448     }
3449 }
3450
3451 pub fn def_has_ty_params(def: ast::def) -> bool {
3452     match def {
3453       ast::def_fn(_, _) | ast::def_variant(_, _) | ast::def_struct(_)
3454         => true,
3455       _ => false
3456     }
3457 }
3458
3459 pub fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[ast::ident] {
3460     if is_local(id) {
3461         match cx.items.find(&id.node) {
3462             Some(&ast_map::node_item(@ast::item {
3463                         node: item_trait(_, _, ref ms),
3464                         _
3465                     }, _)) =>
3466                 match ast_util::split_trait_methods(*ms) {
3467                    (_, p) => p.map(|method| method.ident)
3468                 },
3469             _ => cx.sess.bug(fmt!("provided_trait_methods: %? is not a trait",
3470                                   id))
3471         }
3472     } else {
3473         csearch::get_provided_trait_methods(cx, id).map(|ifo| ifo.ty.ident)
3474     }
3475 }
3476
3477 pub fn trait_supertraits(cx: ctxt,
3478                          id: ast::def_id) -> @~[@TraitRef]
3479 {
3480     // Check the cache.
3481     match cx.supertraits.find(&id) {
3482         Some(&trait_refs) => { return trait_refs; }
3483         None => {}  // Continue.
3484     }
3485
3486     // Not in the cache. It had better be in the metadata, which means it
3487     // shouldn't be local.
3488     assert!(!is_local(id));
3489
3490     // Get the supertraits out of the metadata and create the
3491     // TraitRef for each.
3492     let result = @csearch::get_supertraits(cx, id);
3493     cx.supertraits.insert(id, result);
3494     return result;
3495 }
3496
3497 pub fn trait_ref_supertraits(cx: ctxt, trait_ref: &ty::TraitRef) -> ~[@TraitRef] {
3498     let supertrait_refs = trait_supertraits(cx, trait_ref.def_id);
3499     supertrait_refs.map(
3500         |supertrait_ref| @supertrait_ref.subst(cx, &trait_ref.substs))
3501 }
3502
3503 fn lookup_locally_or_in_crate_store<V:Copy>(
3504     descr: &str,
3505     def_id: ast::def_id,
3506     map: &mut HashMap<ast::def_id, V>,
3507     load_external: &fn() -> V) -> V
3508 {
3509     /*!
3510      *
3511      * Helper for looking things up in the various maps
3512      * that are populated during typeck::collect (e.g.,
3513      * `cx.methods`, `cx.tcache`, etc).  All of these share
3514      * the pattern that if the id is local, it should have
3515      * been loaded into the map by the `typeck::collect` phase.
3516      * If the def-id is external, then we have to go consult
3517      * the crate loading code (and cache the result for the future).
3518      */
3519
3520     match map.find(&def_id) {
3521         Some(&v) => { return v; }
3522         None => { }
3523     }
3524
3525     if def_id.crate == ast::local_crate {
3526         fail!(fmt!("No def'n found for %? in tcx.%s",
3527                    def_id, descr));
3528     }
3529     let v = load_external();
3530     map.insert(def_id, v);
3531     return v;
3532 }
3533
3534 pub fn trait_method(cx: ctxt, trait_did: ast::def_id, idx: uint) -> @method {
3535     let method_def_id = ty::trait_method_def_ids(cx, trait_did)[idx];
3536     ty::method(cx, method_def_id)
3537 }
3538
3539 pub fn trait_methods(cx: ctxt, trait_did: ast::def_id) -> @~[@method] {
3540     match cx.trait_methods_cache.find(&trait_did) {
3541         Some(&methods) => methods,
3542         None => {
3543             let def_ids = ty::trait_method_def_ids(cx, trait_did);
3544             let methods = @def_ids.map(|d| ty::method(cx, *d));
3545             cx.trait_methods_cache.insert(trait_did, methods);
3546             methods
3547         }
3548     }
3549 }
3550
3551 pub fn method(cx: ctxt, id: ast::def_id) -> @method {
3552     lookup_locally_or_in_crate_store(
3553         "methods", id, cx.methods,
3554         || @csearch::get_method(cx, id))
3555 }
3556
3557 pub fn trait_method_def_ids(cx: ctxt, id: ast::def_id) -> @~[def_id] {
3558     lookup_locally_or_in_crate_store(
3559         "methods", id, cx.trait_method_def_ids,
3560         || @csearch::get_trait_method_def_ids(cx.cstore, id))
3561 }
3562
3563 pub fn impl_trait_refs(cx: ctxt, id: ast::def_id) -> ~[@TraitRef] {
3564     if id.crate == ast::local_crate {
3565         debug!("(impl_traits) searching for trait impl %?", id);
3566         match cx.items.find(&id.node) {
3567            Some(&ast_map::node_item(@ast::item {
3568                         node: ast::item_impl(_, opt_trait, _, _),
3569                         _},
3570                     _)) => {
3571                match opt_trait {
3572                    Some(t) => ~[ty::node_id_to_trait_ref(cx, t.ref_id)],
3573                    None => ~[]
3574                }
3575            }
3576            _ => ~[]
3577         }
3578     } else {
3579         csearch::get_impl_traits(cx, id)
3580     }
3581 }
3582
3583 pub fn ty_to_def_id(ty: t) -> Option<ast::def_id> {
3584     match get(ty).sty {
3585       ty_trait(id, _, _, _) | ty_struct(id, _) | ty_enum(id, _) => Some(id),
3586       _ => None
3587     }
3588 }
3589
3590 /// Returns the def ID of the constructor for the given tuple-like struct, or
3591 /// None if the struct is not tuple-like. Fails if the given def ID does not
3592 /// refer to a struct at all.
3593 fn struct_ctor_id(cx: ctxt, struct_did: ast::def_id) -> Option<ast::def_id> {
3594     if struct_did.crate != ast::local_crate {
3595         // XXX: Cross-crate functionality.
3596         cx.sess.unimpl(~"constructor ID of cross-crate tuple structs");
3597     }
3598
3599     match cx.items.find(&struct_did.node) {
3600         Some(&ast_map::node_item(item, _)) => {
3601             match item.node {
3602                 ast::item_struct(struct_def, _) => {
3603                     struct_def.ctor_id.map(|ctor_id|
3604                         ast_util::local_def(*ctor_id))
3605                 }
3606                 _ => cx.sess.bug(~"called struct_ctor_id on non-struct")
3607             }
3608         }
3609         _ => cx.sess.bug(~"called struct_ctor_id on non-struct")
3610     }
3611 }
3612
3613 // Enum information
3614 pub struct VariantInfo_ {
3615     args: ~[t],
3616     ctor_ty: t,
3617     name: ast::ident,
3618     id: ast::def_id,
3619     disr_val: int,
3620     vis: visibility
3621 }
3622
3623 pub type VariantInfo = @VariantInfo_;
3624
3625 pub fn substd_enum_variants(cx: ctxt,
3626                             id: ast::def_id,
3627                             substs: &substs)
3628                          -> ~[VariantInfo] {
3629     do vec::map(*enum_variants(cx, id)) |variant_info| {
3630         let substd_args = vec::map(variant_info.args,
3631                                    |aty| subst(cx, substs, *aty));
3632
3633         let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
3634
3635         @VariantInfo_{args: substd_args, ctor_ty: substd_ctor_ty,
3636                       ../*bad*/copy **variant_info}
3637     }
3638 }
3639
3640 pub fn item_path_str(cx: ctxt, id: ast::def_id) -> ~str {
3641     ast_map::path_to_str(item_path(cx, id), cx.sess.parse_sess.interner)
3642 }
3643
3644 pub enum DtorKind {
3645     NoDtor,
3646     TraitDtor(def_id)
3647 }
3648
3649 pub impl DtorKind {
3650     fn is_not_present(&const self) -> bool {
3651         match *self {
3652             NoDtor => true,
3653             _ => false
3654         }
3655     }
3656     fn is_present(&const self) -> bool {
3657         !self.is_not_present()
3658     }
3659 }
3660
3661 /* If struct_id names a struct with a dtor, return Some(the dtor's id).
3662    Otherwise return none. */
3663 pub fn ty_dtor(cx: ctxt, struct_id: def_id) -> DtorKind {
3664     match cx.destructor_for_type.find(&struct_id) {
3665         Some(&method_def_id) => TraitDtor(method_def_id),
3666         None => NoDtor,
3667     }
3668 }
3669
3670 pub fn has_dtor(cx: ctxt, struct_id: def_id) -> bool {
3671     ty_dtor(cx, struct_id).is_present()
3672 }
3673
3674 pub fn item_path(cx: ctxt, id: ast::def_id) -> ast_map::path {
3675     if id.crate != ast::local_crate {
3676         csearch::get_item_path(cx, id)
3677     } else {
3678         // FIXME (#5521): uncomment this code and don't have a catch-all at the
3679         //                end of the match statement. Favor explicitly listing
3680         //                each variant.
3681         // let node = cx.items.get(&id.node);
3682         // match *node {
3683         match *cx.items.get(&id.node) {
3684           ast_map::node_item(item, path) => {
3685             let item_elt = match item.node {
3686               item_mod(_) | item_foreign_mod(_) => {
3687                 ast_map::path_mod(item.ident)
3688               }
3689               _ => {
3690                 ast_map::path_name(item.ident)
3691               }
3692             };
3693             vec::append_one(/*bad*/copy *path, item_elt)
3694           }
3695
3696           ast_map::node_foreign_item(nitem, _, _, path) => {
3697             vec::append_one(/*bad*/copy *path,
3698                             ast_map::path_name(nitem.ident))
3699           }
3700
3701           ast_map::node_method(method, _, path) => {
3702             vec::append_one(/*bad*/copy *path,
3703                             ast_map::path_name(method.ident))
3704           }
3705           ast_map::node_trait_method(trait_method, _, path) => {
3706             let method = ast_util::trait_method_to_ty_method(&*trait_method);
3707             vec::append_one(/*bad*/copy *path,
3708                             ast_map::path_name(method.ident))
3709           }
3710
3711           ast_map::node_variant(ref variant, _, path) => {
3712             vec::append_one(vec::from_slice(vec::init(*path)),
3713                             ast_map::path_name((*variant).node.name))
3714           }
3715
3716           ast_map::node_struct_ctor(_, item, path) => {
3717             vec::append_one(/*bad*/copy *path, ast_map::path_name(item.ident))
3718           }
3719
3720           ref node => {
3721             cx.sess.bug(fmt!("cannot find item_path for node %?", node));
3722           }
3723         }
3724     }
3725 }
3726
3727 pub fn enum_is_univariant(cx: ctxt, id: ast::def_id) -> bool {
3728     enum_variants(cx, id).len() == 1
3729 }
3730
3731 pub fn type_is_empty(cx: ctxt, t: t) -> bool {
3732     match ty::get(t).sty {
3733        ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
3734        _ => false
3735      }
3736 }
3737
3738 pub fn enum_variants(cx: ctxt, id: ast::def_id) -> @~[VariantInfo] {
3739     match cx.enum_var_cache.find(&id) {
3740       Some(&variants) => return variants,
3741       _ => { /* fallthrough */ }
3742     }
3743
3744     let result = if ast::local_crate != id.crate {
3745         @csearch::get_enum_variants(cx, id)
3746     } else {
3747         /*
3748           Although both this code and check_enum_variants in typeck/check
3749           call eval_const_expr, it should never get called twice for the same
3750           expr, since check_enum_variants also updates the enum_var_cache
3751          */
3752         match *cx.items.get(&id.node) {
3753           ast_map::node_item(@ast::item {
3754                     node: ast::item_enum(ref enum_definition, _),
3755                     _
3756                 }, _) => {
3757             let mut disr_val = -1;
3758             @vec::map(enum_definition.variants, |variant| {
3759                 match variant.node.kind {
3760                     ast::tuple_variant_kind(ref args) => {
3761                         let ctor_ty = node_id_to_type(cx, variant.node.id);
3762                         let arg_tys = {
3763                             if args.len() > 0u {
3764                                 ty_fn_args(ctor_ty).map(|a| a.ty)
3765                             } else {
3766                                 ~[]
3767                             }
3768                         };
3769                         match variant.node.disr_expr {
3770                           Some (ex) => {
3771                             disr_val = match const_eval::eval_const_expr(cx,
3772                                                                          ex) {
3773                               const_eval::const_int(val) => val as int,
3774                               _ => cx.sess.bug(~"tag_variants: bad disr expr")
3775                             }
3776                           }
3777                           _ => disr_val += 1
3778                         }
3779                         @VariantInfo_{args: arg_tys,
3780                           ctor_ty: ctor_ty,
3781                           name: variant.node.name,
3782                           id: ast_util::local_def(variant.node.id),
3783                           disr_val: disr_val,
3784                           vis: variant.node.vis
3785                          }
3786                     }
3787                     ast::struct_variant_kind(_) => {
3788                         fail!(~"struct variant kinds unimpl in enum_variants")
3789                     }
3790                 }
3791             })
3792           }
3793           _ => cx.sess.bug(~"tag_variants: id not bound to an enum")
3794         }
3795     };
3796     cx.enum_var_cache.insert(id, result);
3797     result
3798 }
3799
3800
3801 // Returns information about the enum variant with the given ID:
3802 pub fn enum_variant_with_id(cx: ctxt,
3803                             enum_id: ast::def_id,
3804                             variant_id: ast::def_id)
3805                          -> VariantInfo {
3806     let variants = enum_variants(cx, enum_id);
3807     let mut i = 0;
3808     while i < variants.len() {
3809         let variant = variants[i];
3810         if variant.id == variant_id { return variant; }
3811         i += 1;
3812     }
3813     cx.sess.bug(~"enum_variant_with_id(): no variant exists with that ID");
3814 }
3815
3816
3817 // If the given item is in an external crate, looks up its type and adds it to
3818 // the type cache. Returns the type parameters and type.
3819 pub fn lookup_item_type(cx: ctxt,
3820                         did: ast::def_id)
3821                      -> ty_param_bounds_and_ty {
3822     lookup_locally_or_in_crate_store(
3823         "tcache", did, cx.tcache,
3824         || csearch::get_type(cx, did))
3825 }
3826
3827 /// Given the did of a trait, returns its canonical trait ref.
3828 pub fn lookup_trait_def(cx: ctxt, did: ast::def_id) -> @ty::TraitDef {
3829     match cx.trait_defs.find(&did) {
3830         Some(&trait_def) => {
3831             // The item is in this crate. The caller should have added it to the
3832             // type cache already
3833             return trait_def;
3834         }
3835         None => {
3836             assert!(did.crate != ast::local_crate);
3837             let trait_def = @csearch::get_trait_def(cx, did);
3838             cx.trait_defs.insert(did, trait_def);
3839             return trait_def;
3840         }
3841     }
3842 }
3843
3844 // Determine whether an item is annotated with #[packed] or not
3845 pub fn lookup_packed(tcx: ctxt,
3846                   did: def_id) -> bool {
3847     if is_local(did) {
3848         match tcx.items.find(&did.node) {
3849             Some(
3850                 &ast_map::node_item(@ast::item {
3851                     attrs: ref attrs,
3852                     _
3853                 }, _)) => attr::attrs_contains_name(*attrs, "packed"),
3854             _ => tcx.sess.bug(fmt!("lookup_packed: %? is not an item",
3855                                    did))
3856         }
3857     } else {
3858         let mut ret = false;
3859         do csearch::get_item_attrs(tcx.cstore, did) |meta_items| {
3860             ret = attr::contains_name(meta_items, "packed");
3861         }
3862         ret
3863     }
3864 }
3865
3866 // Look up a field ID, whether or not it's local
3867 // Takes a list of type substs in case the struct is generic
3868 pub fn lookup_field_type(tcx: ctxt,
3869                          struct_id: def_id,
3870                          id: def_id,
3871                          substs: &substs)
3872                       -> ty::t {
3873     let t = if id.crate == ast::local_crate {
3874         node_id_to_type(tcx, id.node)
3875     }
3876     else {
3877         match tcx.tcache.find(&id) {
3878            Some(tpt) => tpt.ty,
3879            None => {
3880                let tpt = csearch::get_field_type(tcx, struct_id, id);
3881                tcx.tcache.insert(id, tpt);
3882                tpt.ty
3883            }
3884         }
3885     };
3886     subst(tcx, substs, t)
3887 }
3888
3889 // Look up the list of field names and IDs for a given struct
3890 // Fails if the id is not bound to a struct.
3891 pub fn lookup_struct_fields(cx: ctxt, did: ast::def_id) -> ~[field_ty] {
3892   if did.crate == ast::local_crate {
3893     match cx.items.find(&did.node) {
3894        Some(&ast_map::node_item(i,_)) => {
3895          match i.node {
3896             ast::item_struct(struct_def, _) => {
3897                struct_field_tys(struct_def.fields)
3898             }
3899             _ => cx.sess.bug(~"struct ID bound to non-struct")
3900          }
3901        }
3902        Some(&ast_map::node_variant(ref variant, _, _)) => {
3903           match (*variant).node.kind {
3904             ast::struct_variant_kind(struct_def) => {
3905               struct_field_tys(struct_def.fields)
3906             }
3907             _ => {
3908               cx.sess.bug(~"struct ID bound to enum variant that isn't \
3909                             struct-like")
3910             }
3911           }
3912        }
3913        _ => {
3914            cx.sess.bug(
3915                fmt!("struct ID not bound to an item: %s",
3916                     ast_map::node_id_to_str(cx.items, did.node,
3917                                             cx.sess.parse_sess.interner)));
3918        }
3919     }
3920         }
3921   else {
3922         return csearch::get_struct_fields(cx.sess.cstore, did);
3923     }
3924 }
3925
3926 pub fn lookup_struct_field(cx: ctxt,
3927                            parent: ast::def_id,
3928                            field_id: ast::def_id)
3929                         -> field_ty {
3930     match vec::find(lookup_struct_fields(cx, parent),
3931                  |f| f.id.node == field_id.node) {
3932         Some(t) => t,
3933         None => cx.sess.bug(~"struct ID not found in parent's fields")
3934     }
3935 }
3936
3937 fn struct_field_tys(fields: &[@struct_field]) -> ~[field_ty] {
3938     do fields.map |field| {
3939         match field.node.kind {
3940             named_field(ident, mutability, visibility) => {
3941                 field_ty {
3942                     ident: ident,
3943                     id: ast_util::local_def(field.node.id),
3944                     vis: visibility,
3945                     mutability: mutability,
3946                 }
3947             }
3948             unnamed_field => {
3949                 field_ty {
3950                     ident:
3951                         syntax::parse::token::special_idents::unnamed_field,
3952                     id: ast_util::local_def(field.node.id),
3953                     vis: ast::public,
3954                     mutability: ast::struct_immutable,
3955                 }
3956             }
3957         }
3958     }
3959 }
3960
3961 // Return a list of fields corresponding to the struct's items
3962 // (as if the struct was a record). trans uses this
3963 // Takes a list of substs with which to instantiate field types
3964 // Keep in mind that this function reports that all fields are
3965 // mutable, regardless of how they were declared. It's meant to
3966 // be used in trans.
3967 pub fn struct_mutable_fields(cx: ctxt,
3968                              did: ast::def_id,
3969                              substs: &substs)
3970                           -> ~[field] {
3971     struct_item_fields(cx, did, substs, |_mt| m_mutbl)
3972 }
3973
3974 // Same as struct_mutable_fields, but doesn't change
3975 // mutability.
3976 pub fn struct_fields(cx: ctxt,
3977                      did: ast::def_id,
3978                      substs: &substs)
3979                   -> ~[field] {
3980     struct_item_fields(cx, did, substs, |mt| match mt {
3981       struct_mutable => m_mutbl,
3982         struct_immutable => m_imm })
3983 }
3984
3985
3986 fn struct_item_fields(cx:ctxt,
3987                      did: ast::def_id,
3988                      substs: &substs,
3989                      frob_mutability: &fn(struct_mutability) -> mutability)
3990     -> ~[field] {
3991     do lookup_struct_fields(cx, did).map |f| {
3992        // consider all instance vars mut, because the
3993        // constructor may mutate all vars
3994        field {
3995            ident: f.ident,
3996             mt: mt {
3997                 ty: lookup_field_type(cx, did, f.id, substs),
3998                 mutbl: frob_mutability(f.mutability)
3999             }
4000         }
4001     }
4002 }
4003
4004 pub fn is_binopable(_cx: ctxt, ty: t, op: ast::binop) -> bool {
4005     static tycat_other: int = 0;
4006     static tycat_bool: int = 1;
4007     static tycat_int: int = 2;
4008     static tycat_float: int = 3;
4009     static tycat_struct: int = 4;
4010     static tycat_bot: int = 5;
4011
4012     static opcat_add: int = 0;
4013     static opcat_sub: int = 1;
4014     static opcat_mult: int = 2;
4015     static opcat_shift: int = 3;
4016     static opcat_rel: int = 4;
4017     static opcat_eq: int = 5;
4018     static opcat_bit: int = 6;
4019     static opcat_logic: int = 7;
4020
4021     fn opcat(op: ast::binop) -> int {
4022         match op {
4023           ast::add => opcat_add,
4024           ast::subtract => opcat_sub,
4025           ast::mul => opcat_mult,
4026           ast::div => opcat_mult,
4027           ast::rem => opcat_mult,
4028           ast::and => opcat_logic,
4029           ast::or => opcat_logic,
4030           ast::bitxor => opcat_bit,
4031           ast::bitand => opcat_bit,
4032           ast::bitor => opcat_bit,
4033           ast::shl => opcat_shift,
4034           ast::shr => opcat_shift,
4035           ast::eq => opcat_eq,
4036           ast::ne => opcat_eq,
4037           ast::lt => opcat_rel,
4038           ast::le => opcat_rel,
4039           ast::ge => opcat_rel,
4040           ast::gt => opcat_rel
4041         }
4042     }
4043
4044     fn tycat(ty: t) -> int {
4045         match get(ty).sty {
4046           ty_bool => tycat_bool,
4047           ty_int(_) | ty_uint(_) | ty_infer(IntVar(_)) => tycat_int,
4048           ty_float(_) | ty_infer(FloatVar(_)) => tycat_float,
4049           ty_tup(_) | ty_enum(_, _) => tycat_struct,
4050           ty_bot => tycat_bot,
4051           _ => tycat_other
4052         }
4053     }
4054
4055     static t: bool = true;
4056     static f: bool = false;
4057
4058     let tbl = ~[
4059     /*.          add,     shift,   bit
4060       .             sub,     rel,     logic
4061       .                mult,    eq,         */
4062     /*other*/   ~[f, f, f, f, f, f, f, f],
4063     /*bool*/    ~[f, f, f, f, t, t, t, t],
4064     /*int*/     ~[t, t, t, t, t, t, t, f],
4065     /*float*/   ~[t, t, t, f, t, t, f, f],
4066     /*bot*/     ~[f, f, f, f, f, f, f, f],
4067     /*struct*/  ~[t, t, t, t, f, f, t, t]];
4068
4069     return tbl[tycat(ty)][opcat(op)];
4070 }
4071
4072 pub fn ty_params_to_tys(tcx: ty::ctxt, generics: &ast::Generics) -> ~[t] {
4073     vec::from_fn(generics.ty_params.len(), |i| {
4074         let id = generics.ty_params.get(i).id;
4075         ty::mk_param(tcx, i, ast_util::local_def(id))
4076     })
4077 }
4078
4079 /// Returns an equivalent type with all the typedefs and self regions removed.
4080 pub fn normalize_ty(cx: ctxt, t: t) -> t {
4081     fn normalize_mt(cx: ctxt, mt: mt) -> mt {
4082         mt { ty: normalize_ty(cx, mt.ty), mutbl: mt.mutbl }
4083     }
4084     fn normalize_vstore(vstore: vstore) -> vstore {
4085         match vstore {
4086             vstore_fixed(*) | vstore_uniq | vstore_box => vstore,
4087             vstore_slice(_) => vstore_slice(re_static)
4088         }
4089     }
4090
4091     match cx.normalized_cache.find(&t) {
4092       Some(&t) => return t,
4093       None => ()
4094     }
4095
4096     let t = match get(t).sty {
4097         ty_evec(mt, vstore) =>
4098             // This type has a vstore. Get rid of it
4099             mk_evec(cx, normalize_mt(cx, mt), normalize_vstore(vstore)),
4100
4101         ty_estr(vstore) =>
4102             // This type has a vstore. Get rid of it
4103             mk_estr(cx, normalize_vstore(vstore)),
4104
4105         ty_rptr(_, mt) =>
4106             // This type has a region. Get rid of it
4107             mk_rptr(cx, re_static, normalize_mt(cx, mt)),
4108
4109         ty_closure(ref closure_ty) => {
4110             mk_closure(cx, ClosureTy {
4111                 region: ty::re_static,
4112                 ..copy *closure_ty
4113             })
4114         }
4115
4116         ty_enum(did, ref r) =>
4117             match (*r).self_r {
4118                 Some(_) =>
4119                     // Use re_static since trans doesn't care about regions
4120                     mk_enum(cx, did,
4121                      substs {
4122                         self_r: Some(ty::re_static),
4123                         self_ty: None,
4124                         tps: /*bad*/copy (*r).tps
4125                      }),
4126                 None =>
4127                     t
4128             },
4129
4130         ty_struct(did, ref r) =>
4131             match (*r).self_r {
4132               Some(_) =>
4133                 // Ditto.
4134                 mk_struct(cx, did, substs {self_r: Some(ty::re_static),
4135                                            self_ty: None,
4136                                            tps: /*bad*/copy (*r).tps}),
4137               None =>
4138                 t
4139             },
4140
4141         _ =>
4142             t
4143     };
4144
4145     let sty = fold_sty(&get(t).sty, |t| { normalize_ty(cx, t) });
4146     let t_norm = mk_t(cx, sty);
4147     cx.normalized_cache.insert(t, t_norm);
4148     return t_norm;
4149 }
4150
4151 // Returns the repeat count for a repeating vector expression.
4152 pub fn eval_repeat_count(tcx: ctxt, count_expr: @ast::expr) -> uint {
4153     match const_eval::eval_const_expr_partial(tcx, count_expr) {
4154       Ok(ref const_val) => match *const_val {
4155         const_eval::const_int(count) => return count as uint,
4156         const_eval::const_uint(count) => return count as uint,
4157         const_eval::const_float(count) => {
4158             tcx.sess.span_err(count_expr.span,
4159                               "expected signed or unsigned integer for \
4160                                repeat count but found float");
4161             return count as uint;
4162         }
4163         const_eval::const_str(_) => {
4164             tcx.sess.span_err(count_expr.span,
4165                               "expected signed or unsigned integer for \
4166                                repeat count but found string");
4167             return 0;
4168         }
4169         const_eval::const_bool(_) => {
4170             tcx.sess.span_err(count_expr.span,
4171                               "expected signed or unsigned integer for \
4172                                repeat count but found boolean");
4173             return 0;
4174         }
4175       },
4176       Err(*) => {
4177         tcx.sess.span_err(count_expr.span,
4178                           "expected constant integer for repeat count \
4179                            but found variable");
4180         return 0;
4181       }
4182     }
4183 }
4184
4185 // Determine what purity to check a nested function under
4186 pub fn determine_inherited_purity(parent: (ast::purity, ast::node_id),
4187                                   child: (ast::purity, ast::node_id),
4188                                   child_sigil: ast::Sigil)
4189                                     -> (ast::purity, ast::node_id) {
4190     // If the closure is a stack closure and hasn't had some non-standard
4191     // purity inferred for it, then check it under its parent's purity.
4192     // Otherwise, use its own
4193     match child_sigil {
4194         ast::BorrowedSigil if child.first() == ast::impure_fn => parent,
4195         _ => child
4196     }
4197 }
4198
4199 // Iterate over a type parameter's bounded traits and any supertraits
4200 // of those traits, ignoring kinds.
4201 // Here, the supertraits are the transitive closure of the supertrait
4202 // relation on the supertraits from each bounded trait's constraint
4203 // list.
4204 pub fn each_bound_trait_and_supertraits(tcx: ctxt,
4205                                          bounds: param_bounds,
4206                                          f: &fn(&TraitRef) -> bool) {
4207     for bounds.each |bound| {
4208         let bound_trait_ref = match *bound {
4209             ty::bound_trait(bound_t) => bound_t,
4210
4211             ty::bound_copy | ty::bound_owned |
4212             ty::bound_const | ty::bound_durable => {
4213                 loop; // skip non-trait bounds
4214             }
4215         };
4216
4217         let mut supertrait_set = HashMap::new();
4218         let mut trait_refs = ~[];
4219         let mut i = 0;
4220
4221         // Seed the worklist with the trait from the bound
4222         supertrait_set.insert(bound_trait_ref.def_id, ());
4223         trait_refs.push(bound_trait_ref);
4224
4225         // Add the given trait ty to the hash map
4226         while i < trait_refs.len() {
4227             debug!("each_bound_trait_and_supertraits(i=%?, trait_ref=%s)",
4228                    i, trait_refs[i].repr(tcx));
4229
4230             if !f(trait_refs[i]) {
4231                 return;
4232             }
4233
4234             // Add supertraits to supertrait_set
4235             let supertrait_refs = trait_ref_supertraits(tcx, trait_refs[i]);
4236             for supertrait_refs.each |&supertrait_ref| {
4237                 debug!("each_bound_trait_and_supertraits(supertrait_ref=%s)",
4238                        supertrait_ref.repr(tcx));
4239
4240                 let d_id = supertrait_ref.def_id;
4241                 if !supertrait_set.contains_key(&d_id) {
4242                     // FIXME(#5527) Could have same trait multiple times
4243                     supertrait_set.insert(d_id, ());
4244                     trait_refs.push(supertrait_ref);
4245                 }
4246             }
4247
4248             i += 1;
4249         }
4250     }
4251 }
4252
4253 pub fn count_traits_and_supertraits(tcx: ctxt,
4254                                     type_param_defs: &[TypeParameterDef]) -> uint {
4255     let mut total = 0;
4256     for type_param_defs.each |type_param_def| {
4257         for each_bound_trait_and_supertraits(tcx, type_param_def.bounds) |_| {
4258             total += 1;
4259         }
4260     }
4261     return total;
4262 }
4263
4264 // Given a trait and a type, returns the impl of that type
4265 pub fn get_impl_id(tcx: ctxt, trait_id: def_id, self_ty: t) -> def_id {
4266     match tcx.trait_impls.find(&trait_id) {
4267         Some(ty_to_impl) => match ty_to_impl.find(&self_ty) {
4268             Some(the_impl) => the_impl.did,
4269             None => // try autoderef!
4270                 match deref(tcx, self_ty, false) {
4271                     Some(some_ty) => get_impl_id(tcx, trait_id, some_ty.ty),
4272                     None => tcx.sess.bug(~"get_impl_id: no impl of trait for \
4273                                            this type")
4274             }
4275         },
4276         None => tcx.sess.bug(~"get_impl_id: trait isn't in trait_impls")
4277     }
4278 }
4279
4280 pub fn visitor_object_ty(tcx: ctxt) -> (@TraitRef, t) {
4281     let ty_visitor_name = special_idents::ty_visitor;
4282     assert!(tcx.intrinsic_traits.contains_key(&ty_visitor_name));
4283     let trait_ref = *tcx.intrinsic_traits.get(&ty_visitor_name);
4284     (trait_ref,
4285      mk_trait(tcx, trait_ref.def_id, copy trait_ref.substs, BoxTraitStore, ast::m_imm))
4286 }