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 // Converts s to its machine type equivalent
1257 pub fn mach_sty(cfg: @session::config, t: t) -> sty {
1258     match get(t).sty {
1259       ty_int(ast::ty_i) => ty_int(cfg.int_type),
1260       ty_uint(ast::ty_u) => ty_uint(cfg.uint_type),
1261       ty_float(ast::ty_f) => ty_float(cfg.float_type),
1262       ref s => (/*bad*/copy *s)
1263     }
1264 }
1265
1266 pub fn walk_ty(ty: t, f: &fn(t)) {
1267     maybe_walk_ty(ty, |t| { f(t); true });
1268 }
1269
1270 pub fn maybe_walk_ty(ty: t, f: &fn(t) -> bool) {
1271     if !f(ty) {
1272         return;
1273     }
1274     match get(ty).sty {
1275       ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1276       ty_estr(_) | ty_type | ty_opaque_box | ty_self(_) |
1277       ty_opaque_closure_ptr(_) | ty_infer(_) | ty_param(_) | ty_err => {
1278       }
1279       ty_box(ref tm) | ty_evec(ref tm, _) | ty_unboxed_vec(ref tm) |
1280       ty_ptr(ref tm) | ty_rptr(_, ref tm) | ty_uniq(ref tm) => {
1281         maybe_walk_ty(tm.ty, f);
1282       }
1283       ty_enum(_, ref substs) | ty_struct(_, ref substs) |
1284       ty_trait(_, ref substs, _, _) => {
1285         for (*substs).tps.each |subty| { maybe_walk_ty(*subty, f); }
1286       }
1287       ty_tup(ref ts) => { for ts.each |tt| { maybe_walk_ty(*tt, f); } }
1288       ty_bare_fn(ref ft) => {
1289         for ft.sig.inputs.each |a| { maybe_walk_ty(a.ty, f); }
1290         maybe_walk_ty(ft.sig.output, f);
1291       }
1292       ty_closure(ref ft) => {
1293         for ft.sig.inputs.each |a| { maybe_walk_ty(a.ty, f); }
1294         maybe_walk_ty(ft.sig.output, f);
1295       }
1296     }
1297 }
1298
1299 pub fn fold_sty_to_ty(tcx: ty::ctxt, sty: &sty, foldop: &fn(t) -> t) -> t {
1300     mk_t(tcx, fold_sty(sty, foldop))
1301 }
1302
1303 pub fn fold_sig(sig: &FnSig, fldop: &fn(t) -> t) -> FnSig {
1304     let args = do sig.inputs.map |arg| {
1305         arg {
1306             ty: fldop(arg.ty)
1307         }
1308     };
1309
1310     FnSig {
1311         bound_lifetime_names: copy sig.bound_lifetime_names,
1312         inputs: args,
1313         output: fldop(sig.output)
1314     }
1315 }
1316
1317 pub fn fold_bare_fn_ty(fty: &BareFnTy, fldop: &fn(t) -> t) -> BareFnTy {
1318     BareFnTy {sig: fold_sig(&fty.sig, fldop),
1319               abis: fty.abis,
1320               purity: fty.purity}
1321 }
1322
1323 fn fold_sty(sty: &sty, fldop: &fn(t) -> t) -> sty {
1324     fn fold_substs(substs: &substs, fldop: &fn(t) -> t) -> substs {
1325         substs {self_r: substs.self_r,
1326                 self_ty: substs.self_ty.map(|t| fldop(*t)),
1327                 tps: substs.tps.map(|t| fldop(*t))}
1328     }
1329
1330     match *sty {
1331         ty_box(ref tm) => {
1332             ty_box(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1333         }
1334         ty_uniq(ref tm) => {
1335             ty_uniq(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1336         }
1337         ty_ptr(ref tm) => {
1338             ty_ptr(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1339         }
1340         ty_unboxed_vec(ref tm) => {
1341             ty_unboxed_vec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1342         }
1343         ty_evec(ref tm, vst) => {
1344             ty_evec(mt {ty: fldop(tm.ty), mutbl: tm.mutbl}, vst)
1345         }
1346         ty_enum(tid, ref substs) => {
1347             ty_enum(tid, fold_substs(substs, fldop))
1348         }
1349         ty_trait(did, ref substs, st, mutbl) => {
1350             ty_trait(did, fold_substs(substs, fldop), st, mutbl)
1351         }
1352         ty_tup(ref ts) => {
1353             let new_ts = ts.map(|tt| fldop(*tt));
1354             ty_tup(new_ts)
1355         }
1356         ty_bare_fn(ref f) => {
1357             ty_bare_fn(fold_bare_fn_ty(f, fldop))
1358         }
1359         ty_closure(ref f) => {
1360             let sig = fold_sig(&f.sig, fldop);
1361             ty_closure(ClosureTy {sig: sig, ..copy *f})
1362         }
1363         ty_rptr(r, ref tm) => {
1364             ty_rptr(r, mt {ty: fldop(tm.ty), mutbl: tm.mutbl})
1365         }
1366         ty_struct(did, ref substs) => {
1367             ty_struct(did, fold_substs(substs, fldop))
1368         }
1369         ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1370         ty_estr(_) | ty_type | ty_opaque_closure_ptr(_) | ty_err |
1371         ty_opaque_box | ty_infer(_) | ty_param(*) | ty_self(_) => {
1372             /*bad*/copy *sty
1373         }
1374     }
1375 }
1376
1377 // Folds types from the bottom up.
1378 pub fn fold_ty(cx: ctxt, t0: t, fldop: &fn(t) -> t) -> t {
1379     let sty = fold_sty(&get(t0).sty, |t| fold_ty(cx, fldop(t), fldop));
1380     fldop(mk_t(cx, sty))
1381 }
1382
1383 pub fn walk_regions_and_ty(
1384     cx: ctxt,
1385     ty: t,
1386     walkr: &fn(r: Region),
1387     walkt: &fn(t: t) -> bool) {
1388
1389     if (walkt(ty)) {
1390         fold_regions_and_ty(
1391             cx, ty,
1392             |r| { walkr(r); r },
1393             |t| { walk_regions_and_ty(cx, t, walkr, walkt); t },
1394             |t| { walk_regions_and_ty(cx, t, walkr, walkt); t });
1395     }
1396 }
1397
1398 pub fn fold_regions_and_ty(
1399     cx: ctxt,
1400     ty: t,
1401     fldr: &fn(r: Region) -> Region,
1402     fldfnt: &fn(t: t) -> t,
1403     fldt: &fn(t: t) -> t) -> t {
1404
1405     fn fold_substs(
1406         substs: &substs,
1407         fldr: &fn(r: Region) -> Region,
1408         fldt: &fn(t: t) -> t)
1409      -> substs {
1410         substs {
1411             self_r: substs.self_r.map(|r| fldr(*r)),
1412             self_ty: substs.self_ty.map(|t| fldt(*t)),
1413             tps: substs.tps.map(|t| fldt(*t))
1414         }
1415     }
1416
1417     let tb = ty::get(ty);
1418     match tb.sty {
1419       ty::ty_rptr(r, mt) => {
1420         let m_r = fldr(r);
1421         let m_t = fldt(mt.ty);
1422         ty::mk_rptr(cx, m_r, mt {ty: m_t, mutbl: mt.mutbl})
1423       }
1424       ty_estr(vstore_slice(r)) => {
1425         let m_r = fldr(r);
1426         ty::mk_estr(cx, vstore_slice(m_r))
1427       }
1428       ty_evec(mt, vstore_slice(r)) => {
1429         let m_r = fldr(r);
1430         let m_t = fldt(mt.ty);
1431         ty::mk_evec(cx, mt {ty: m_t, mutbl: mt.mutbl}, vstore_slice(m_r))
1432       }
1433       ty_enum(def_id, ref substs) => {
1434         ty::mk_enum(cx, def_id, fold_substs(substs, fldr, fldt))
1435       }
1436       ty_struct(def_id, ref substs) => {
1437         ty::mk_struct(cx, def_id, fold_substs(substs, fldr, fldt))
1438       }
1439       ty_trait(def_id, ref substs, st, mutbl) => {
1440         ty::mk_trait(cx, def_id, fold_substs(substs, fldr, fldt), st, mutbl)
1441       }
1442       ty_bare_fn(ref f) => {
1443           ty::mk_bare_fn(cx, BareFnTy {sig: fold_sig(&f.sig, fldfnt),
1444                                        ..copy *f})
1445       }
1446       ty_closure(ref f) => {
1447           ty::mk_closure(cx, ClosureTy {region: fldr(f.region),
1448                                         sig: fold_sig(&f.sig, fldfnt),
1449                                         ..copy *f})
1450       }
1451       ref sty => {
1452         fold_sty_to_ty(cx, sty, |t| fldt(t))
1453       }
1454     }
1455 }
1456
1457 // n.b. this function is intended to eventually replace fold_region() below,
1458 // that is why its name is so similar.
1459 pub fn fold_regions(
1460     cx: ctxt,
1461     ty: t,
1462     fldr: &fn(r: Region, in_fn: bool) -> Region) -> t {
1463     fn do_fold(cx: ctxt, ty: t, in_fn: bool,
1464                fldr: &fn(Region, bool) -> Region) -> t {
1465         debug!("do_fold(ty=%s, in_fn=%b)", ty_to_str(cx, ty), in_fn);
1466         if !type_has_regions(ty) { return ty; }
1467         fold_regions_and_ty(
1468             cx, ty,
1469             |r| fldr(r, in_fn),
1470             |t| do_fold(cx, t, true, fldr),
1471             |t| do_fold(cx, t, in_fn, fldr))
1472     }
1473     do_fold(cx, ty, false, fldr)
1474 }
1475
1476 // Substitute *only* type parameters.  Used in trans where regions are erased.
1477 pub fn subst_tps(cx: ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
1478     if tps.len() == 0u && self_ty_opt.is_none() { return typ; }
1479     let tb = ty::get(typ);
1480     if self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) { return typ; }
1481     match tb.sty {
1482         ty_param(p) => tps[p.idx],
1483         ty_self(_) => {
1484             match self_ty_opt {
1485                 None => cx.sess.bug(~"ty_self unexpected here"),
1486                 Some(self_ty) => {
1487                     subst_tps(cx, tps, self_ty_opt, self_ty)
1488                 }
1489             }
1490         }
1491         ref sty => {
1492             fold_sty_to_ty(cx, sty, |t| subst_tps(cx, tps, self_ty_opt, t))
1493         }
1494     }
1495 }
1496
1497 pub fn substs_is_noop(substs: &substs) -> bool {
1498     substs.tps.len() == 0u &&
1499         substs.self_r.is_none() &&
1500         substs.self_ty.is_none()
1501 }
1502
1503 pub fn substs_to_str(cx: ctxt, substs: &substs) -> ~str {
1504     substs.repr(cx)
1505 }
1506
1507 pub fn param_bound_to_str(cx: ctxt, pb: &param_bound) -> ~str {
1508     pb.repr(cx)
1509 }
1510
1511 pub fn param_bounds_to_str(cx: ctxt, pbs: param_bounds) -> ~str {
1512     pbs.repr(cx)
1513 }
1514
1515 pub fn subst(cx: ctxt,
1516              substs: &substs,
1517              typ: t)
1518           -> t {
1519     typ.subst(cx, substs)
1520 }
1521
1522 // Type utilities
1523
1524 pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil }
1525
1526 pub fn type_is_bot(ty: t) -> bool {
1527     (get(ty).flags & (has_ty_bot as uint)) != 0
1528 }
1529
1530 pub fn type_is_error(ty: t) -> bool {
1531     (get(ty).flags & (has_ty_err as uint)) != 0
1532 }
1533
1534 pub fn type_needs_subst(ty: t) -> bool {
1535     tbox_has_flag(get(ty), needs_subst)
1536 }
1537
1538 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
1539     tref.substs.self_ty.any(|&t| type_is_error(t)) ||
1540         tref.substs.tps.any(|&t| type_is_error(t))
1541 }
1542
1543 pub fn type_is_ty_var(ty: t) -> bool {
1544     match get(ty).sty {
1545       ty_infer(TyVar(_)) => true,
1546       _ => false
1547     }
1548 }
1549
1550 pub fn type_is_bool(ty: t) -> bool { get(ty).sty == ty_bool }
1551
1552 pub fn type_is_structural(ty: t) -> bool {
1553     match get(ty).sty {
1554       ty_struct(*) | ty_tup(_) | ty_enum(*) | ty_closure(_) | ty_trait(*) |
1555       ty_evec(_, vstore_fixed(_)) | ty_estr(vstore_fixed(_)) |
1556       ty_evec(_, vstore_slice(_)) | ty_estr(vstore_slice(_))
1557       => true,
1558       _ => false
1559     }
1560 }
1561
1562 pub fn type_is_sequence(ty: t) -> bool {
1563     match get(ty).sty {
1564       ty_estr(_) | ty_evec(_, _) => true,
1565       _ => false
1566     }
1567 }
1568
1569 pub fn type_is_str(ty: t) -> bool {
1570     match get(ty).sty {
1571       ty_estr(_) => true,
1572       _ => false
1573     }
1574 }
1575
1576 pub fn sequence_element_type(cx: ctxt, ty: t) -> t {
1577     match get(ty).sty {
1578       ty_estr(_) => return mk_mach_uint(ast::ty_u8),
1579       ty_evec(mt, _) | ty_unboxed_vec(mt) => return mt.ty,
1580       _ => cx.sess.bug(
1581           ~"sequence_element_type called on non-sequence value"),
1582     }
1583 }
1584
1585 pub fn get_element_type(ty: t, i: uint) -> t {
1586     match get(ty).sty {
1587       ty_tup(ref ts) => return ts[i],
1588       _ => fail!(~"get_element_type called on invalid type")
1589     }
1590 }
1591
1592 pub fn type_is_box(ty: t) -> bool {
1593     match get(ty).sty {
1594       ty_box(_) => return true,
1595       _ => return false
1596     }
1597 }
1598
1599 pub fn type_is_boxed(ty: t) -> bool {
1600     match get(ty).sty {
1601       ty_box(_) | ty_opaque_box |
1602       ty_evec(_, vstore_box) | ty_estr(vstore_box) => true,
1603       _ => false
1604     }
1605 }
1606
1607 pub fn type_is_region_ptr(ty: t) -> bool {
1608     match get(ty).sty {
1609       ty_rptr(_, _) => true,
1610       _ => false
1611     }
1612 }
1613
1614 pub fn type_is_slice(ty: t) -> bool {
1615     match get(ty).sty {
1616       ty_evec(_, vstore_slice(_)) | ty_estr(vstore_slice(_)) => true,
1617       _ => return false
1618     }
1619 }
1620
1621 pub fn type_is_unique_box(ty: t) -> bool {
1622     match get(ty).sty {
1623       ty_uniq(_) => return true,
1624       _ => return false
1625     }
1626 }
1627
1628 pub fn type_is_unsafe_ptr(ty: t) -> bool {
1629     match get(ty).sty {
1630       ty_ptr(_) => return true,
1631       _ => return false
1632     }
1633 }
1634
1635 pub fn type_is_vec(ty: t) -> bool {
1636     return match get(ty).sty {
1637           ty_evec(_, _) | ty_unboxed_vec(_) => true,
1638           ty_estr(_) => true,
1639           _ => false
1640         };
1641 }
1642
1643 pub fn type_is_unique(ty: t) -> bool {
1644     match get(ty).sty {
1645         ty_uniq(_) |
1646         ty_evec(_, vstore_uniq) |
1647         ty_estr(vstore_uniq) |
1648         ty_opaque_closure_ptr(ast::OwnedSigil) => true,
1649         _ => return false
1650     }
1651 }
1652
1653 /*
1654  A scalar type is one that denotes an atomic datum, with no sub-components.
1655  (A ty_ptr is scalar because it represents a non-managed pointer, so its
1656  contents are abstract to rustc.)
1657 */
1658 pub fn type_is_scalar(ty: t) -> bool {
1659     match get(ty).sty {
1660       ty_nil | ty_bool | ty_int(_) | ty_float(_) | ty_uint(_) |
1661       ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) | ty_type |
1662       ty_bare_fn(*) | ty_ptr(_) => true,
1663       _ => false
1664     }
1665 }
1666
1667 pub fn type_is_immediate(ty: t) -> bool {
1668     return type_is_scalar(ty) || type_is_boxed(ty) ||
1669         type_is_unique(ty) || type_is_region_ptr(ty);
1670 }
1671
1672 pub fn type_needs_drop(cx: ctxt, ty: t) -> bool {
1673     type_contents(cx, ty).needs_drop(cx)
1674 }
1675
1676 // Some things don't need cleanups during unwinding because the
1677 // task can free them all at once later. Currently only things
1678 // that only contain scalars and shared boxes can avoid unwind
1679 // cleanups.
1680 pub fn type_needs_unwind_cleanup(cx: ctxt, ty: t) -> bool {
1681     match cx.needs_unwind_cleanup_cache.find(&ty) {
1682       Some(&result) => return result,
1683       None => ()
1684     }
1685
1686     let mut tycache = HashSet::new();
1687     let needs_unwind_cleanup =
1688         type_needs_unwind_cleanup_(cx, ty, &mut tycache, false);
1689     cx.needs_unwind_cleanup_cache.insert(ty, needs_unwind_cleanup);
1690     return needs_unwind_cleanup;
1691 }
1692
1693 fn type_needs_unwind_cleanup_(cx: ctxt, ty: t,
1694                               tycache: &mut HashSet<t>,
1695                               encountered_box: bool) -> bool {
1696
1697     // Prevent infinite recursion
1698     if !tycache.insert(ty) {
1699         return false;
1700     }
1701
1702     let mut encountered_box = encountered_box;
1703     let mut needs_unwind_cleanup = false;
1704     do maybe_walk_ty(ty) |ty| {
1705         let old_encountered_box = encountered_box;
1706         let result = match get(ty).sty {
1707           ty_box(_) | ty_opaque_box => {
1708             encountered_box = true;
1709             true
1710           }
1711           ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1712           ty_tup(_) | ty_ptr(_) => {
1713             true
1714           }
1715           ty_enum(did, ref substs) => {
1716             for vec::each(*enum_variants(cx, did)) |v| {
1717                 for v.args.each |aty| {
1718                     let t = subst(cx, substs, *aty);
1719                     needs_unwind_cleanup |=
1720                         type_needs_unwind_cleanup_(cx, t, tycache,
1721                                                    encountered_box);
1722                 }
1723             }
1724             !needs_unwind_cleanup
1725           }
1726           ty_uniq(_) |
1727           ty_estr(vstore_uniq) |
1728           ty_estr(vstore_box) |
1729           ty_evec(_, vstore_uniq) |
1730           ty_evec(_, vstore_box)
1731           => {
1732             // Once we're inside a box, the annihilator will find
1733             // it and destroy it.
1734             if !encountered_box {
1735                 needs_unwind_cleanup = true;
1736                 false
1737             } else {
1738                 true
1739             }
1740           }
1741           _ => {
1742             needs_unwind_cleanup = true;
1743             false
1744           }
1745         };
1746
1747         encountered_box = old_encountered_box;
1748         result
1749     }
1750
1751     return needs_unwind_cleanup;
1752 }
1753
1754 /**
1755  * Type contents is how the type checker reasons about kinds.
1756  * They track what kinds of things are found within a type.  You can
1757  * think of them as kind of an "anti-kind".  They track the kinds of values
1758  * and thinks that are contained in types.  Having a larger contents for
1759  * a type tends to rule that type *out* from various kinds.  For example,
1760  * a type that contains a borrowed pointer is not sendable.
1761  *
1762  * The reason we compute type contents and not kinds is that it is
1763  * easier for me (nmatsakis) to think about what is contained within
1764  * a type than to think about what is *not* contained within a type.
1765  */
1766 pub struct TypeContents {
1767     bits: u32
1768 }
1769
1770 pub impl TypeContents {
1771     fn intersects(&self, tc: TypeContents) -> bool {
1772         (self.bits & tc.bits) != 0
1773     }
1774
1775     fn is_copy(&self, cx: ctxt) -> bool {
1776         !self.intersects(TypeContents::noncopyable(cx))
1777     }
1778
1779     fn noncopyable(_cx: ctxt) -> TypeContents {
1780         TC_DTOR + TC_BORROWED_MUT + TC_ONCE_CLOSURE + TC_OWNED_CLOSURE +
1781             TC_EMPTY_ENUM
1782     }
1783
1784     fn is_durable(&self, cx: ctxt) -> bool {
1785         !self.intersects(TypeContents::nondurable(cx))
1786     }
1787
1788     fn nondurable(_cx: ctxt) -> TypeContents {
1789         TC_BORROWED_POINTER
1790     }
1791
1792     fn is_owned(&self, cx: ctxt) -> bool {
1793         !self.intersects(TypeContents::nonowned(cx))
1794     }
1795
1796     fn nonowned(_cx: ctxt) -> TypeContents {
1797         TC_MANAGED + TC_BORROWED_POINTER
1798     }
1799
1800     fn contains_managed(&self) -> bool {
1801         self.intersects(TC_MANAGED)
1802     }
1803
1804     fn is_const(&self, cx: ctxt) -> bool {
1805         !self.intersects(TypeContents::nonconst(cx))
1806     }
1807
1808     fn nonconst(_cx: ctxt) -> TypeContents {
1809         TC_MUTABLE
1810     }
1811
1812     fn moves_by_default(&self, cx: ctxt) -> bool {
1813         self.intersects(TypeContents::nonimplicitly_copyable(cx))
1814     }
1815
1816     fn nonimplicitly_copyable(cx: ctxt) -> TypeContents {
1817         let base = TypeContents::noncopyable(cx) + TC_OWNED_POINTER;
1818         if cx.vecs_implicitly_copyable {base} else {base + TC_OWNED_VEC}
1819     }
1820
1821     fn is_safe_for_default_mode(&self, cx: ctxt) -> bool {
1822         !self.intersects(TypeContents::nondefault_mode(cx))
1823     }
1824
1825     fn nondefault_mode(cx: ctxt) -> TypeContents {
1826         let tc = TypeContents::nonimplicitly_copyable(cx);
1827         tc + TC_BIG + TC_OWNED_VEC // disregard cx.vecs_implicitly_copyable
1828     }
1829
1830     fn needs_drop(&self, cx: ctxt) -> bool {
1831         let tc = TC_MANAGED + TC_DTOR + TypeContents::owned(cx);
1832         self.intersects(tc)
1833     }
1834
1835     fn owned(_cx: ctxt) -> TypeContents {
1836         //! Any kind of owned contents.
1837         TC_OWNED_CLOSURE + TC_OWNED_POINTER + TC_OWNED_VEC
1838     }
1839 }
1840
1841 impl ops::Add<TypeContents,TypeContents> for TypeContents {
1842     fn add(&self, other: &TypeContents) -> TypeContents {
1843         TypeContents {bits: self.bits | other.bits}
1844     }
1845 }
1846
1847 impl ops::Sub<TypeContents,TypeContents> for TypeContents {
1848     fn sub(&self, other: &TypeContents) -> TypeContents {
1849         TypeContents {bits: self.bits & !other.bits}
1850     }
1851 }
1852
1853 impl ToStr for TypeContents {
1854     fn to_str(&self) -> ~str {
1855         fmt!("TypeContents(%s)", u32::to_str_radix(self.bits, 2))
1856     }
1857 }
1858
1859 /// Constant for a type containing nothing of interest.
1860 static TC_NONE: TypeContents =             TypeContents{bits:0b0000_00000000};
1861
1862 /// Contains a borrowed value with a lifetime other than static
1863 static TC_BORROWED_POINTER: TypeContents = TypeContents{bits:0b0000_00000001};
1864
1865 /// Contains an owned pointer (~T) but not slice of some kind
1866 static TC_OWNED_POINTER: TypeContents =    TypeContents{bits:0b000000000010};
1867
1868 /// Contains an owned vector ~[] or owned string ~str
1869 static TC_OWNED_VEC: TypeContents =        TypeContents{bits:0b000000000100};
1870
1871 /// Contains a ~fn() or a ~Trait, which is non-copyable.
1872 static TC_OWNED_CLOSURE: TypeContents =    TypeContents{bits:0b000000001000};
1873
1874 /// Type with a destructor
1875 static TC_DTOR: TypeContents =             TypeContents{bits:0b000000010000};
1876
1877 /// Contains a managed value
1878 static TC_MANAGED: TypeContents =          TypeContents{bits:0b000000100000};
1879
1880 /// &mut with any region
1881 static TC_BORROWED_MUT: TypeContents =     TypeContents{bits:0b000001000000};
1882
1883 /// Mutable content, whether owned or by ref
1884 static TC_MUTABLE: TypeContents =          TypeContents{bits:0b000010000000};
1885
1886 /// Mutable content, whether owned or by ref
1887 static TC_ONCE_CLOSURE: TypeContents =     TypeContents{bits:0b000100000000};
1888
1889 /// Something we estimate to be "big"
1890 static TC_BIG: TypeContents =              TypeContents{bits:0b001000000000};
1891
1892 /// An enum with no variants.
1893 static TC_EMPTY_ENUM: TypeContents =       TypeContents{bits:0b010000000000};
1894
1895 /// All possible contents.
1896 static TC_ALL: TypeContents =              TypeContents{bits:0b011111111111};
1897
1898 pub fn type_is_copyable(cx: ctxt, t: ty::t) -> bool {
1899     type_contents(cx, t).is_copy(cx)
1900 }
1901
1902 pub fn type_is_durable(cx: ctxt, t: ty::t) -> bool {
1903     type_contents(cx, t).is_durable(cx)
1904 }
1905
1906 pub fn type_is_owned(cx: ctxt, t: ty::t) -> bool {
1907     type_contents(cx, t).is_owned(cx)
1908 }
1909
1910 pub fn type_is_const(cx: ctxt, t: ty::t) -> bool {
1911     type_contents(cx, t).is_const(cx)
1912 }
1913
1914 pub fn type_contents(cx: ctxt, ty: t) -> TypeContents {
1915     let ty_id = type_id(ty);
1916     match cx.tc_cache.find(&ty_id) {
1917         Some(tc) => { return *tc; }
1918         None => {}
1919     }
1920
1921     let mut cache = HashMap::new();
1922     let result = tc_ty(cx, ty, &mut cache);
1923     cx.tc_cache.insert(ty_id, result);
1924     return result;
1925
1926     fn tc_ty(cx: ctxt,
1927              ty: t,
1928              cache: &mut HashMap<uint, TypeContents>) -> TypeContents
1929     {
1930         // Subtle: Note that we are *not* using cx.tc_cache here but rather a
1931         // private cache for this walk.  This is needed in the case of cyclic
1932         // types like:
1933         //
1934         //     struct List { next: ~Option<List>, ... }
1935         //
1936         // When computing the type contents of such a type, we wind up deeply
1937         // recursing as we go.  So when we encounter the recursive reference
1938         // to List, we temporarily use TC_NONE as its contents.  Later we'll
1939         // patch up the cache with the correct value, once we've computed it
1940         // (this is basically a co-inductive process, if that helps).  So in
1941         // the end we'll compute TC_OWNED_POINTER, in this case.
1942         //
1943         // The problem is, as we are doing the computation, we will also
1944         // compute an *intermediate* contents for, e.g., Option<List> of
1945         // TC_NONE.  This is ok during the computation of List itself, but if
1946         // we stored this intermediate value into cx.tc_cache, then later
1947         // requests for the contents of Option<List> would also yield TC_NONE
1948         // which is incorrect.  This value was computed based on the crutch
1949         // value for the type contents of list.  The correct value is
1950         // TC_OWNED_POINTER.  This manifested as issue #4821.
1951         let ty_id = type_id(ty);
1952         match cache.find(&ty_id) {
1953             Some(tc) => { return *tc; }
1954             None => {}
1955         }
1956         match cx.tc_cache.find(&ty_id) {    // Must check both caches!
1957             Some(tc) => { return *tc; }
1958             None => {}
1959         }
1960         cache.insert(ty_id, TC_NONE);
1961
1962         let _i = indenter();
1963
1964         let mut result = match get(ty).sty {
1965             // Scalar and unique types are sendable, constant, and owned
1966             ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1967             ty_bare_fn(_) | ty_ptr(_) => {
1968                 TC_NONE
1969             }
1970
1971             ty_estr(vstore_uniq) => {
1972                 TC_OWNED_VEC
1973             }
1974
1975             ty_closure(ref c) => {
1976                 closure_contents(c)
1977             }
1978
1979             ty_box(mt) => {
1980                 TC_MANAGED + nonowned(tc_mt(cx, mt, cache))
1981             }
1982
1983             ty_trait(_, _, UniqTraitStore, _) => {
1984                 TC_OWNED_CLOSURE
1985             }
1986
1987             ty_trait(_, _, BoxTraitStore, mutbl) => {
1988                 match mutbl {
1989                     ast::m_mutbl => TC_MANAGED + TC_MUTABLE,
1990                     _ => TC_MANAGED
1991                 }
1992             }
1993
1994             ty_trait(_, _, RegionTraitStore(r), mutbl) => {
1995                 borrowed_contents(r, mutbl)
1996             }
1997
1998             ty_rptr(r, mt) => {
1999                 borrowed_contents(r, mt.mutbl) +
2000                     nonowned(tc_mt(cx, mt, cache))
2001             }
2002
2003             ty_uniq(mt) => {
2004                 TC_OWNED_POINTER + tc_mt(cx, mt, cache)
2005             }
2006
2007             ty_evec(mt, vstore_uniq) => {
2008                 TC_OWNED_VEC + tc_mt(cx, mt, cache)
2009             }
2010
2011             ty_evec(mt, vstore_box) => {
2012                 TC_MANAGED + nonowned(tc_mt(cx, mt, cache))
2013             }
2014
2015             ty_evec(mt, vstore_slice(r)) => {
2016                 borrowed_contents(r, mt.mutbl) +
2017                     nonowned(tc_mt(cx, mt, cache))
2018             }
2019
2020             ty_evec(mt, vstore_fixed(_)) => {
2021                 tc_mt(cx, mt, cache)
2022             }
2023
2024             ty_estr(vstore_box) => {
2025                 TC_MANAGED
2026             }
2027
2028             ty_estr(vstore_slice(r)) => {
2029                 borrowed_contents(r, m_imm)
2030             }
2031
2032             ty_estr(vstore_fixed(_)) => {
2033                 TC_NONE
2034             }
2035
2036             ty_struct(did, ref substs) => {
2037                 let flds = struct_fields(cx, did, substs);
2038                 let flds_tc = flds.foldl(
2039                     TC_NONE,
2040                     |tc, f| tc + tc_mt(cx, f.mt, cache));
2041                 if ty::has_dtor(cx, did) {
2042                     flds_tc + TC_DTOR
2043                 } else {
2044                     flds_tc
2045                 }
2046             }
2047
2048             ty_tup(ref tys) => {
2049                 tys.foldl(TC_NONE, |tc, ty| *tc + tc_ty(cx, *ty, cache))
2050             }
2051
2052             ty_enum(did, ref substs) => {
2053                 let variants = substd_enum_variants(cx, did, substs);
2054                 if variants.is_empty() {
2055                     // we somewhat arbitrary declare that empty enums
2056                     // are non-copyable
2057                     TC_EMPTY_ENUM
2058                 } else {
2059                     variants.foldl(TC_NONE, |tc, variant| {
2060                         variant.args.foldl(
2061                             *tc,
2062                             |tc, arg_ty| *tc + tc_ty(cx, *arg_ty, cache))
2063                     })
2064                 }
2065             }
2066
2067             ty_param(p) => {
2068                 // We only ever ask for the kind of types that are defined in
2069                 // the current crate; therefore, the only type parameters that
2070                 // could be in scope are those defined in the current crate.
2071                 // If this assertion failures, it is likely because of a
2072                 // failure in the cross-crate inlining code to translate a
2073                 // def-id.
2074                 assert!(p.def_id.crate == ast::local_crate);
2075
2076                 type_param_def_to_contents(
2077                     cx, cx.ty_param_defs.get(&p.def_id.node))
2078             }
2079
2080             ty_self(_) => {
2081                 // Currently, self is not bounded, so we must assume the
2082                 // worst.  But in the future we should examine the super
2083                 // traits.
2084                 //
2085                 // FIXME(#4678)---self should just be a ty param
2086                 TC_ALL
2087             }
2088
2089             ty_infer(_) => {
2090                 // This occurs during coherence, but shouldn't occur at other
2091                 // times.
2092                 TC_ALL
2093             }
2094
2095             ty_opaque_box => TC_MANAGED,
2096             ty_unboxed_vec(mt) => tc_mt(cx, mt, cache),
2097             ty_opaque_closure_ptr(sigil) => {
2098                 match sigil {
2099                     ast::BorrowedSigil => TC_BORROWED_POINTER,
2100                     ast::ManagedSigil => TC_MANAGED,
2101                     ast::OwnedSigil => TC_OWNED_CLOSURE
2102                 }
2103             }
2104
2105             ty_type => TC_NONE,
2106
2107             ty_err => {
2108                 cx.sess.bug(~"Asked to compute contents of fictitious type");
2109             }
2110         };
2111
2112         if type_size(cx, ty) > 4 {
2113             result = result + TC_BIG;
2114         }
2115
2116         cache.insert(ty_id, result);
2117         return result;
2118     }
2119
2120     fn tc_mt(cx: ctxt,
2121              mt: mt,
2122              cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2123     {
2124         let mc = if mt.mutbl == m_mutbl {TC_MUTABLE} else {TC_NONE};
2125         mc + tc_ty(cx, mt.ty, cache)
2126     }
2127
2128     fn borrowed_contents(region: ty::Region,
2129                          mutbl: ast::mutability) -> TypeContents
2130     {
2131         let mc = if mutbl == m_mutbl {
2132             TC_MUTABLE + TC_BORROWED_MUT
2133         } else {
2134             TC_NONE
2135         };
2136         let rc = if region != ty::re_static {
2137             TC_BORROWED_POINTER
2138         } else {
2139             TC_NONE
2140         };
2141         mc + rc
2142     }
2143
2144     fn nonowned(pointee: TypeContents) -> TypeContents {
2145         /*!
2146          *
2147          * Given a non-owning pointer to some type `T` with
2148          * contents `pointee` (like `@T` or
2149          * `&T`), returns the relevant bits that
2150          * apply to the owner of the pointer.
2151          */
2152
2153         let mask = TC_MUTABLE.bits | TC_BORROWED_POINTER.bits;
2154         TypeContents {bits: pointee.bits & mask}
2155     }
2156
2157     fn closure_contents(cty: &ClosureTy) -> TypeContents {
2158         let st = match cty.sigil {
2159             ast::BorrowedSigil => TC_BORROWED_POINTER,
2160             ast::ManagedSigil => TC_MANAGED,
2161             ast::OwnedSigil => TC_OWNED_CLOSURE
2162         };
2163         let rt = borrowed_contents(cty.region, m_imm);
2164         let ot = match cty.onceness {
2165             ast::Once => TC_ONCE_CLOSURE,
2166             ast::Many => TC_NONE
2167         };
2168         st + rt + ot
2169     }
2170
2171     fn type_param_def_to_contents(cx: ctxt,
2172                                   type_param_def: &TypeParameterDef) -> TypeContents
2173     {
2174         debug!("type_param_def_to_contents(%s)", type_param_def.repr(cx));
2175         let _i = indenter();
2176
2177         let r = type_param_def.bounds.foldl(TC_ALL, |tc, bound| {
2178             debug!("tc = %s, bound = %?", tc.to_str(), bound);
2179             match *bound {
2180                 bound_copy => tc - TypeContents::nonimplicitly_copyable(cx),
2181                 bound_durable => tc - TypeContents::nondurable(cx),
2182                 bound_owned => tc - TypeContents::nonowned(cx),
2183                 bound_const => tc - TypeContents::nonconst(cx),
2184                 bound_trait(_) => *tc
2185             }
2186         });
2187
2188         debug!("result = %s", r.to_str());
2189         return r;
2190     }
2191
2192     /// gives a rough estimate of how much space it takes to represent
2193     /// an instance of `ty`.  Used for the mode transition.
2194     fn type_size(cx: ctxt, ty: t) -> uint {
2195         match get(ty).sty {
2196           ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
2197           ty_ptr(_) | ty_box(_) | ty_uniq(_) | ty_estr(vstore_uniq) |
2198           ty_trait(*) | ty_rptr(*) | ty_evec(_, vstore_uniq) |
2199           ty_evec(_, vstore_box) | ty_estr(vstore_box) => {
2200             1
2201           }
2202
2203           ty_evec(_, vstore_slice(_)) |
2204           ty_estr(vstore_slice(_)) |
2205           ty_bare_fn(*) |
2206           ty_closure(*) => {
2207             2
2208           }
2209
2210           ty_evec(t, vstore_fixed(n)) => {
2211             type_size(cx, t.ty) * n
2212           }
2213
2214           ty_estr(vstore_fixed(n)) => {
2215             n
2216           }
2217
2218           ty_struct(did, ref substs) => {
2219             let flds = struct_fields(cx, did, substs);
2220             flds.foldl(0, |s, f| *s + type_size(cx, f.mt.ty))
2221           }
2222
2223           ty_tup(ref tys) => {
2224             tys.foldl(0, |s, t| *s + type_size(cx, *t))
2225           }
2226
2227           ty_enum(did, ref substs) => {
2228             let variants = substd_enum_variants(cx, did, substs);
2229             variants.foldl( // find max size of any variant
2230                 0,
2231                 |m, v| uint::max(
2232                     *m,
2233                     // find size of this variant:
2234                     v.args.foldl(0, |s, a| *s + type_size(cx, *a))))
2235           }
2236
2237           ty_param(_) | ty_self(_) => {
2238             1
2239           }
2240
2241           ty_infer(_) => {
2242             cx.sess.bug(~"Asked to compute kind of a type variable");
2243           }
2244           ty_type => 1,
2245           ty_opaque_closure_ptr(_) => 1,
2246           ty_opaque_box => 1,
2247           ty_unboxed_vec(_) => 10,
2248           ty_err => {
2249             cx.sess.bug(~"Asked to compute kind of fictitious type");
2250           }
2251         }
2252     }
2253 }
2254
2255 pub fn type_moves_by_default(cx: ctxt, ty: t) -> bool {
2256     type_contents(cx, ty).moves_by_default(cx)
2257 }
2258
2259 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
2260 pub fn is_instantiable(cx: ctxt, r_ty: t) -> bool {
2261     fn type_requires(cx: ctxt, seen: &mut ~[def_id],
2262                      r_ty: t, ty: t) -> bool {
2263         debug!("type_requires(%s, %s)?",
2264                ::util::ppaux::ty_to_str(cx, r_ty),
2265                ::util::ppaux::ty_to_str(cx, ty));
2266
2267         let r = {
2268             get(r_ty).sty == get(ty).sty ||
2269                 subtypes_require(cx, seen, r_ty, ty)
2270         };
2271
2272         debug!("type_requires(%s, %s)? %b",
2273                ::util::ppaux::ty_to_str(cx, r_ty),
2274                ::util::ppaux::ty_to_str(cx, ty),
2275                r);
2276         return r;
2277     }
2278
2279     fn subtypes_require(cx: ctxt, seen: &mut ~[def_id],
2280                         r_ty: t, ty: t) -> bool {
2281         debug!("subtypes_require(%s, %s)?",
2282                ::util::ppaux::ty_to_str(cx, r_ty),
2283                ::util::ppaux::ty_to_str(cx, ty));
2284
2285         let r = match get(ty).sty {
2286           ty_nil |
2287           ty_bot |
2288           ty_bool |
2289           ty_int(_) |
2290           ty_uint(_) |
2291           ty_float(_) |
2292           ty_estr(_) |
2293           ty_bare_fn(_) |
2294           ty_closure(_) |
2295           ty_infer(_) |
2296           ty_err |
2297           ty_param(_) |
2298           ty_self(_) |
2299           ty_type |
2300           ty_opaque_box |
2301           ty_opaque_closure_ptr(_) |
2302           ty_evec(_, _) |
2303           ty_unboxed_vec(_) => {
2304             false
2305           }
2306           ty_box(ref mt) |
2307           ty_uniq(ref mt) |
2308           ty_rptr(_, ref mt) => {
2309             return type_requires(cx, seen, r_ty, mt.ty);
2310           }
2311
2312           ty_ptr(*) => {
2313             false           // unsafe ptrs can always be NULL
2314           }
2315
2316           ty_trait(_, _, _, _) => {
2317             false
2318           }
2319
2320           ty_struct(ref did, _) if vec::contains(*seen, did) => {
2321             false
2322           }
2323
2324           ty_struct(did, ref substs) => {
2325               seen.push(did);
2326               let r = vec::any(struct_fields(cx, did, substs),
2327                                |f| type_requires(cx, seen, r_ty, f.mt.ty));
2328               seen.pop();
2329             r
2330           }
2331
2332           ty_tup(ref ts) => {
2333             ts.any(|t| type_requires(cx, seen, r_ty, *t))
2334           }
2335
2336           ty_enum(ref did, _) if vec::contains(*seen, did) => {
2337             false
2338           }
2339
2340             ty_enum(did, ref substs) => {
2341                 seen.push(did);
2342                 let vs = enum_variants(cx, did);
2343                 let r = vec::len(*vs) > 0u && vec::all(*vs, |variant| {
2344                     vec::any(variant.args, |aty| {
2345                         let sty = subst(cx, substs, *aty);
2346                         type_requires(cx, seen, r_ty, sty)
2347                     })
2348                 });
2349                 seen.pop();
2350                 r
2351             }
2352         };
2353
2354         debug!("subtypes_require(%s, %s)? %b",
2355                ::util::ppaux::ty_to_str(cx, r_ty),
2356                ::util::ppaux::ty_to_str(cx, ty),
2357                r);
2358
2359         return r;
2360     }
2361
2362     let seen = @mut ~[];
2363     !subtypes_require(cx, seen, r_ty, r_ty)
2364 }
2365
2366 pub fn type_structurally_contains(cx: ctxt,
2367                                   ty: t,
2368                                   test: &fn(x: &sty) -> bool)
2369                                -> bool {
2370     let sty = &get(ty).sty;
2371     debug!("type_structurally_contains: %s",
2372            ::util::ppaux::ty_to_str(cx, ty));
2373     if test(sty) { return true; }
2374     match *sty {
2375       ty_enum(did, ref substs) => {
2376         for vec::each(*enum_variants(cx, did)) |variant| {
2377             for variant.args.each |aty| {
2378                 let sty = subst(cx, substs, *aty);
2379                 if type_structurally_contains(cx, sty, test) { return true; }
2380             }
2381         }
2382         return false;
2383       }
2384       ty_struct(did, ref substs) => {
2385         for lookup_struct_fields(cx, did).each |field| {
2386             let ft = lookup_field_type(cx, did, field.id, substs);
2387             if type_structurally_contains(cx, ft, test) { return true; }
2388         }
2389         return false;
2390       }
2391
2392       ty_tup(ref ts) => {
2393         for ts.each |tt| {
2394             if type_structurally_contains(cx, *tt, test) { return true; }
2395         }
2396         return false;
2397       }
2398       ty_evec(ref mt, vstore_fixed(_)) => {
2399         return type_structurally_contains(cx, mt.ty, test);
2400       }
2401       _ => return false
2402     }
2403 }
2404
2405 pub fn type_structurally_contains_uniques(cx: ctxt, ty: t) -> bool {
2406     return type_structurally_contains(cx, ty, |sty| {
2407         match *sty {
2408           ty_uniq(_) |
2409           ty_evec(_, vstore_uniq) |
2410           ty_estr(vstore_uniq) => true,
2411           _ => false,
2412         }
2413     });
2414 }
2415
2416 pub fn type_is_integral(ty: t) -> bool {
2417     match get(ty).sty {
2418       ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
2419       _ => false
2420     }
2421 }
2422
2423 pub fn type_is_char(ty: t) -> bool {
2424     match get(ty).sty {
2425         ty_int(ty_char) => true,
2426         _ => false
2427     }
2428 }
2429
2430 pub fn type_is_fp(ty: t) -> bool {
2431     match get(ty).sty {
2432       ty_infer(FloatVar(_)) | ty_float(_) => true,
2433       _ => false
2434     }
2435 }
2436
2437 pub fn type_is_numeric(ty: t) -> bool {
2438     return type_is_integral(ty) || type_is_fp(ty);
2439 }
2440
2441 pub fn type_is_signed(ty: t) -> bool {
2442     match get(ty).sty {
2443       ty_int(_) => true,
2444       _ => false
2445     }
2446 }
2447
2448 // Whether a type is Plain Old Data -- meaning it does not contain pointers
2449 // that the cycle collector might care about.
2450 pub fn type_is_pod(cx: ctxt, ty: t) -> bool {
2451     let mut result = true;
2452     match get(ty).sty {
2453       // Scalar types
2454       ty_nil | ty_bot | ty_bool | ty_int(_) | ty_float(_) | ty_uint(_) |
2455       ty_type | ty_ptr(_) | ty_bare_fn(_) => result = true,
2456       // Boxed types
2457       ty_box(_) | ty_uniq(_) | ty_closure(_) |
2458       ty_estr(vstore_uniq) | ty_estr(vstore_box) |
2459       ty_evec(_, vstore_uniq) | ty_evec(_, vstore_box) |
2460       ty_trait(_, _, _, _) | ty_rptr(_,_) | ty_opaque_box => result = false,
2461       // Structural types
2462       ty_enum(did, ref substs) => {
2463         let variants = enum_variants(cx, did);
2464         for vec::each(*variants) |variant| {
2465             let tup_ty = mk_tup(cx, /*bad*/copy variant.args);
2466
2467             // Perform any type parameter substitutions.
2468             let tup_ty = subst(cx, substs, tup_ty);
2469             if !type_is_pod(cx, tup_ty) { result = false; }
2470         }
2471       }
2472       ty_tup(ref elts) => {
2473         for elts.each |elt| { if !type_is_pod(cx, *elt) { result = false; } }
2474       }
2475       ty_estr(vstore_fixed(_)) => result = true,
2476       ty_evec(ref mt, vstore_fixed(_)) | ty_unboxed_vec(ref mt) => {
2477         result = type_is_pod(cx, mt.ty);
2478       }
2479       ty_param(_) => result = false,
2480       ty_opaque_closure_ptr(_) => result = true,
2481       ty_struct(did, ref substs) => {
2482         result = vec::any(lookup_struct_fields(cx, did), |f| {
2483             let fty = ty::lookup_item_type(cx, f.id);
2484             let sty = subst(cx, substs, fty.ty);
2485             type_is_pod(cx, sty)
2486         });
2487       }
2488
2489       ty_estr(vstore_slice(*)) | ty_evec(_, vstore_slice(*)) => {
2490         result = false;
2491       }
2492
2493       ty_infer(*) | ty_self(*) | ty_err => {
2494         cx.sess.bug(~"non concrete type in type_is_pod");
2495       }
2496     }
2497
2498     return result;
2499 }
2500
2501 pub fn type_is_enum(ty: t) -> bool {
2502     match get(ty).sty {
2503       ty_enum(_, _) => return true,
2504       _ => return false
2505     }
2506 }
2507
2508 // Whether a type is enum like, that is a enum type with only nullary
2509 // constructors
2510 pub fn type_is_c_like_enum(cx: ctxt, ty: t) -> bool {
2511     match get(ty).sty {
2512         ty_enum(did, _) => {
2513             let variants = enum_variants(cx, did);
2514             if variants.len() == 0 {
2515                 false
2516             } else {
2517                 variants.all(|v| v.args.len() == 0)
2518             }
2519         }
2520         _ => false
2521     }
2522 }
2523
2524 pub fn type_param(ty: t) -> Option<uint> {
2525     match get(ty).sty {
2526       ty_param(p) => return Some(p.idx),
2527       _ => {/* fall through */ }
2528     }
2529     return None;
2530 }
2531
2532 // Returns the type and mutability of *t.
2533 //
2534 // The parameter `explicit` indicates if this is an *explicit* dereference.
2535 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
2536 pub fn deref(cx: ctxt, t: t, explicit: bool) -> Option<mt> {
2537     deref_sty(cx, &get(t).sty, explicit)
2538 }
2539
2540 pub fn deref_sty(cx: ctxt, sty: &sty, explicit: bool) -> Option<mt> {
2541     match *sty {
2542       ty_rptr(_, mt) | ty_box(mt) | ty_uniq(mt) => {
2543         Some(mt)
2544       }
2545
2546       ty_ptr(mt) if explicit => {
2547         Some(mt)
2548       }
2549
2550       ty_enum(did, ref substs) => {
2551         let variants = enum_variants(cx, did);
2552         if vec::len(*variants) == 1u && vec::len(variants[0].args) == 1u {
2553             let v_t = subst(cx, substs, variants[0].args[0]);
2554             Some(mt {ty: v_t, mutbl: ast::m_imm})
2555         } else {
2556             None
2557         }
2558       }
2559
2560       ty_struct(did, ref substs) => {
2561         let fields = struct_fields(cx, did, substs);
2562         if fields.len() == 1 && fields[0].ident ==
2563                 syntax::parse::token::special_idents::unnamed_field {
2564             Some(mt {ty: fields[0].mt.ty, mutbl: ast::m_imm})
2565         } else {
2566             None
2567         }
2568       }
2569
2570       _ => None
2571     }
2572 }
2573
2574 pub fn type_autoderef(cx: ctxt, t: t) -> t {
2575     let mut t = t;
2576     loop {
2577         match deref(cx, t, false) {
2578           None => return t,
2579           Some(mt) => t = mt.ty
2580         }
2581     }
2582 }
2583
2584 // Returns the type and mutability of t[i]
2585 pub fn index(t: t) -> Option<mt> {
2586     index_sty(&get(t).sty)
2587 }
2588
2589 pub fn index_sty(sty: &sty) -> Option<mt> {
2590     match *sty {
2591       ty_evec(mt, _) => Some(mt),
2592       ty_estr(_) => Some(mt {ty: mk_u8(), mutbl: ast::m_imm}),
2593       _ => None
2594     }
2595 }
2596
2597 /**
2598  * Enforces an arbitrary but consistent total ordering over
2599  * free regions.  This is needed for establishing a consistent
2600  * LUB in region_inference. */
2601 impl cmp::TotalOrd for FreeRegion {
2602     fn cmp(&self, other: &FreeRegion) -> Ordering {
2603         cmp::cmp2(&self.scope_id, &self.bound_region,
2604                   &other.scope_id, &other.bound_region)
2605     }
2606 }
2607
2608 impl cmp::TotalEq for FreeRegion {
2609     fn equals(&self, other: &FreeRegion) -> bool {
2610         *self == *other
2611     }
2612 }
2613
2614 /**
2615  * Enforces an arbitrary but consistent total ordering over
2616  * bound regions.  This is needed for establishing a consistent
2617  * LUB in region_inference. */
2618 impl cmp::TotalOrd for bound_region {
2619     fn cmp(&self, other: &bound_region) -> Ordering {
2620         match (self, other) {
2621             (&ty::br_self, &ty::br_self) => cmp::Equal,
2622             (&ty::br_self, _) => cmp::Less,
2623
2624             (&ty::br_anon(ref a1), &ty::br_anon(ref a2)) => a1.cmp(a2),
2625             (&ty::br_anon(*), _) => cmp::Less,
2626
2627             (&ty::br_named(ref a1), &ty::br_named(ref a2)) => a1.repr.cmp(&a2.repr),
2628             (&ty::br_named(*), _) => cmp::Less,
2629
2630             (&ty::br_cap_avoid(ref a1, @ref b1),
2631              &ty::br_cap_avoid(ref a2, @ref b2)) => cmp::cmp2(a1, b1, a2, b2),
2632             (&ty::br_cap_avoid(*), _) => cmp::Less,
2633
2634             (&ty::br_fresh(ref a1), &ty::br_fresh(ref a2)) => a1.cmp(a2),
2635             (&ty::br_fresh(*), _) => cmp::Less,
2636         }
2637     }
2638 }
2639
2640 impl cmp::TotalEq for bound_region {
2641     fn equals(&self, other: &bound_region) -> bool {
2642         *self == *other
2643     }
2644 }
2645
2646 impl to_bytes::IterBytes for vstore {
2647     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2648         match *self {
2649           vstore_fixed(ref u) =>
2650           to_bytes::iter_bytes_2(&0u8, u, lsb0, f),
2651
2652           vstore_uniq => 1u8.iter_bytes(lsb0, f),
2653           vstore_box => 2u8.iter_bytes(lsb0, f),
2654
2655           vstore_slice(ref r) =>
2656           to_bytes::iter_bytes_2(&3u8, r, lsb0, f),
2657         }
2658     }
2659 }
2660
2661 impl to_bytes::IterBytes for substs {
2662     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2663           to_bytes::iter_bytes_3(&self.self_r,
2664                                  &self.self_ty,
2665                                  &self.tps, lsb0, f)
2666     }
2667 }
2668
2669 impl to_bytes::IterBytes for mt {
2670     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2671           to_bytes::iter_bytes_2(&self.ty,
2672                                  &self.mutbl, lsb0, f)
2673     }
2674 }
2675
2676 impl to_bytes::IterBytes for field {
2677     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2678           to_bytes::iter_bytes_2(&self.ident,
2679                                  &self.mt, lsb0, f)
2680     }
2681 }
2682
2683 impl to_bytes::IterBytes for FnSig {
2684     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2685         to_bytes::iter_bytes_2(&self.inputs,
2686                                &self.output,
2687                                lsb0, f);
2688     }
2689 }
2690
2691 impl to_bytes::IterBytes for sty {
2692     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
2693         match *self {
2694           ty_nil => 0u8.iter_bytes(lsb0, f),
2695           ty_bool => 1u8.iter_bytes(lsb0, f),
2696
2697           ty_int(ref t) =>
2698           to_bytes::iter_bytes_2(&2u8, t, lsb0, f),
2699
2700           ty_uint(ref t) =>
2701           to_bytes::iter_bytes_2(&3u8, t, lsb0, f),
2702
2703           ty_float(ref t) =>
2704           to_bytes::iter_bytes_2(&4u8, t, lsb0, f),
2705
2706           ty_estr(ref v) =>
2707           to_bytes::iter_bytes_2(&5u8, v, lsb0, f),
2708
2709           ty_enum(ref did, ref substs) =>
2710           to_bytes::iter_bytes_3(&6u8, did, substs, lsb0, f),
2711
2712           ty_box(ref mt) =>
2713           to_bytes::iter_bytes_2(&7u8, mt, lsb0, f),
2714
2715           ty_evec(ref mt, ref v) =>
2716           to_bytes::iter_bytes_3(&8u8, mt, v, lsb0, f),
2717
2718           ty_unboxed_vec(ref mt) =>
2719           to_bytes::iter_bytes_2(&9u8, mt, lsb0, f),
2720
2721           ty_tup(ref ts) =>
2722           to_bytes::iter_bytes_2(&10u8, ts, lsb0, f),
2723
2724           ty_bare_fn(ref ft) =>
2725           to_bytes::iter_bytes_2(&12u8, ft, lsb0, f),
2726
2727           ty_self(ref did) => to_bytes::iter_bytes_2(&13u8, did, lsb0, f),
2728
2729           ty_infer(ref v) =>
2730           to_bytes::iter_bytes_2(&14u8, v, lsb0, f),
2731
2732           ty_param(ref p) =>
2733           to_bytes::iter_bytes_2(&15u8, p, lsb0, f),
2734
2735           ty_type => 16u8.iter_bytes(lsb0, f),
2736           ty_bot => 17u8.iter_bytes(lsb0, f),
2737
2738           ty_ptr(ref mt) =>
2739           to_bytes::iter_bytes_2(&18u8, mt, lsb0, f),
2740
2741           ty_uniq(ref mt) =>
2742           to_bytes::iter_bytes_2(&19u8, mt, lsb0, f),
2743
2744           ty_trait(ref did, ref substs, ref v, ref mutbl) =>
2745           to_bytes::iter_bytes_5(&20u8, did, substs, v, mutbl, lsb0, f),
2746
2747           ty_opaque_closure_ptr(ref ck) =>
2748           to_bytes::iter_bytes_2(&21u8, ck, lsb0, f),
2749
2750           ty_opaque_box => 22u8.iter_bytes(lsb0, f),
2751
2752           ty_struct(ref did, ref substs) =>
2753           to_bytes::iter_bytes_3(&23u8, did, substs, lsb0, f),
2754
2755           ty_rptr(ref r, ref mt) =>
2756           to_bytes::iter_bytes_3(&24u8, r, mt, lsb0, f),
2757
2758           ty_err => 25u8.iter_bytes(lsb0, f),
2759
2760           ty_closure(ref ct) =>
2761           to_bytes::iter_bytes_2(&26u8, ct, lsb0, f),
2762         }
2763     }
2764 }
2765
2766 pub fn node_id_to_trait_ref(cx: ctxt, id: ast::node_id) -> @ty::TraitRef {
2767     match cx.trait_refs.find(&id) {
2768        Some(&t) => t,
2769        None => cx.sess.bug(
2770            fmt!("node_id_to_trait_ref: no trait ref for node `%s`",
2771                 ast_map::node_id_to_str(cx.items, id,
2772                                         cx.sess.parse_sess.interner)))
2773     }
2774 }
2775
2776 pub fn node_id_to_type(cx: ctxt, id: ast::node_id) -> t {
2777     //io::println(fmt!("%?/%?", id, cx.node_types.len()));
2778     match cx.node_types.find(&(id as uint)) {
2779        Some(&t) => t,
2780        None => cx.sess.bug(
2781            fmt!("node_id_to_type: no type for node `%s`",
2782                 ast_map::node_id_to_str(cx.items, id,
2783                                         cx.sess.parse_sess.interner)))
2784     }
2785 }
2786
2787 pub fn node_id_to_type_params(cx: ctxt, id: ast::node_id) -> ~[t] {
2788     match cx.node_type_substs.find(&id) {
2789       None => return ~[],
2790       Some(ts) => return /*bad*/ copy *ts
2791     }
2792 }
2793
2794 fn node_id_has_type_params(cx: ctxt, id: ast::node_id) -> bool {
2795     cx.node_type_substs.contains_key(&id)
2796 }
2797
2798 pub fn ty_fn_sig(fty: t) -> FnSig {
2799     match get(fty).sty {
2800         ty_bare_fn(ref f) => copy f.sig,
2801         ty_closure(ref f) => copy f.sig,
2802         ref s => {
2803             fail!(fmt!("ty_fn_sig() called on non-fn type: %?", s))
2804         }
2805     }
2806 }
2807
2808 // Type accessors for substructures of types
2809 pub fn ty_fn_args(fty: t) -> ~[arg] {
2810     match get(fty).sty {
2811         ty_bare_fn(ref f) => copy f.sig.inputs,
2812         ty_closure(ref f) => copy f.sig.inputs,
2813         ref s => {
2814             fail!(fmt!("ty_fn_args() called on non-fn type: %?", s))
2815         }
2816     }
2817 }
2818
2819 pub fn ty_closure_sigil(fty: t) -> Sigil {
2820     match get(fty).sty {
2821         ty_closure(ref f) => f.sigil,
2822         ref s => {
2823             fail!(fmt!("ty_closure_sigil() called on non-closure type: %?",
2824                        s))
2825         }
2826     }
2827 }
2828
2829 pub fn ty_fn_purity(fty: t) -> ast::purity {
2830     match get(fty).sty {
2831         ty_bare_fn(ref f) => f.purity,
2832         ty_closure(ref f) => f.purity,
2833         ref s => {
2834             fail!(fmt!("ty_fn_purity() called on non-fn type: %?", s))
2835         }
2836     }
2837 }
2838
2839 pub fn ty_fn_ret(fty: t) -> t {
2840     match get(fty).sty {
2841         ty_bare_fn(ref f) => f.sig.output,
2842         ty_closure(ref f) => f.sig.output,
2843         ref s => {
2844             fail!(fmt!("ty_fn_ret() called on non-fn type: %?", s))
2845         }
2846     }
2847 }
2848
2849 pub fn is_fn_ty(fty: t) -> bool {
2850     match get(fty).sty {
2851         ty_bare_fn(_) => true,
2852         ty_closure(_) => true,
2853         _ => false
2854     }
2855 }
2856
2857 pub fn ty_vstore(ty: t) -> vstore {
2858     match get(ty).sty {
2859         ty_evec(_, vstore) => vstore,
2860         ty_estr(vstore) => vstore,
2861         ref s => fail!(fmt!("ty_vstore() called on invalid sty: %?", s))
2862     }
2863 }
2864
2865 pub fn ty_region(tcx: ctxt,
2866                  span: span,
2867                  ty: t) -> Region {
2868     match get(ty).sty {
2869         ty_rptr(r, _) => r,
2870         ty_evec(_, vstore_slice(r)) => r,
2871         ty_estr(vstore_slice(r)) => r,
2872         ref s => {
2873             tcx.sess.span_bug(
2874                 span,
2875                 fmt!("ty_region() invoked on in appropriate ty: %?", s));
2876         }
2877     }
2878 }
2879
2880 pub fn replace_closure_return_type(tcx: ctxt, fn_type: t, ret_type: t) -> t {
2881     /*!
2882      *
2883      * Returns a new function type based on `fn_type` but returning a value of
2884      * type `ret_type` instead. */
2885
2886     match ty::get(fn_type).sty {
2887         ty::ty_closure(ref fty) => {
2888             ty::mk_closure(tcx, ClosureTy {
2889                 sig: FnSig {output: ret_type, ..copy fty.sig},
2890                 ..copy *fty
2891             })
2892         }
2893         _ => {
2894             tcx.sess.bug(fmt!(
2895                 "replace_fn_ret() invoked with non-fn-type: %s",
2896                 ty_to_str(tcx, fn_type)));
2897         }
2898     }
2899 }
2900
2901 // Returns a vec of all the input and output types of fty.
2902 pub fn tys_in_fn_sig(sig: &FnSig) -> ~[t] {
2903     vec::append_one(sig.inputs.map(|a| a.ty), sig.output)
2904 }
2905
2906 // Type accessors for AST nodes
2907 pub fn block_ty(cx: ctxt, b: &ast::blk) -> t {
2908     return node_id_to_type(cx, b.node.id);
2909 }
2910
2911
2912 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
2913 // doesn't provide type parameter substitutions.
2914 pub fn pat_ty(cx: ctxt, pat: @ast::pat) -> t {
2915     return node_id_to_type(cx, pat.id);
2916 }
2917
2918
2919 // Returns the type of an expression as a monotype.
2920 //
2921 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression.  That is, in
2922 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
2923 // auto-ref.  The type returned by this function does not consider such
2924 // adjustments.  See `expr_ty_adjusted()` instead.
2925 //
2926 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
2927 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
2928 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
2929 // expr_ty_params_and_ty() below.
2930 pub fn expr_ty(cx: ctxt, expr: @ast::expr) -> t {
2931     return node_id_to_type(cx, expr.id);
2932 }
2933
2934 pub fn expr_ty_adjusted(cx: ctxt, expr: @ast::expr) -> t {
2935     /*!
2936      *
2937      * Returns the type of `expr`, considering any `AutoAdjustment`
2938      * entry recorded for that expression.
2939      *
2940      * It would almost certainly be better to store the adjusted ty in with
2941      * the `AutoAdjustment`, but I opted not to do this because it would
2942      * require serializing and deserializing the type and, although that's not
2943      * hard to do, I just hate that code so much I didn't want to touch it
2944      * unless it was to fix it properly, which seemed a distraction from the
2945      * task at hand! -nmatsakis
2946      */
2947
2948     let unadjusted_ty = expr_ty(cx, expr);
2949     adjust_ty(cx, expr.span, unadjusted_ty, cx.adjustments.find(&expr.id))
2950 }
2951
2952 pub fn adjust_ty(cx: ctxt,
2953                  span: span,
2954                  unadjusted_ty: ty::t,
2955                  adjustment: Option<&@AutoAdjustment>) -> ty::t
2956 {
2957     /*! See `expr_ty_adjusted` */
2958
2959     return match adjustment {
2960         None => unadjusted_ty,
2961
2962         Some(&@AutoAddEnv(r, s)) => {
2963             match ty::get(unadjusted_ty).sty {
2964                 ty::ty_bare_fn(ref b) => {
2965                     ty::mk_closure(
2966                         cx,
2967                         ty::ClosureTy {purity: b.purity,
2968                                        sigil: s,
2969                                        onceness: ast::Many,
2970                                        region: r,
2971                                        sig: copy b.sig})
2972                 }
2973                 ref b => {
2974                     cx.sess.bug(
2975                         fmt!("add_env adjustment on non-bare-fn: %?", b));
2976                 }
2977             }
2978         }
2979
2980         Some(&@AutoDerefRef(ref adj)) => {
2981             let mut adjusted_ty = unadjusted_ty;
2982
2983             for uint::range(0, adj.autoderefs) |i| {
2984                 match ty::deref(cx, adjusted_ty, true) {
2985                     Some(mt) => { adjusted_ty = mt.ty; }
2986                     None => {
2987                         cx.sess.span_bug(
2988                             span,
2989                             fmt!("The %uth autoderef failed: %s",
2990                                  i, ty_to_str(cx,
2991                                               adjusted_ty)));
2992                     }
2993                 }
2994             }
2995
2996             match adj.autoref {
2997                 None => adjusted_ty,
2998                 Some(ref autoref) => {
2999                     match autoref.kind {
3000                         AutoPtr => {
3001                             mk_rptr(cx, autoref.region,
3002                                     mt {ty: adjusted_ty,
3003                                         mutbl: autoref.mutbl})
3004                         }
3005
3006                         AutoBorrowVec => {
3007                             borrow_vec(cx, span, autoref, adjusted_ty)
3008                         }
3009
3010                         AutoBorrowVecRef => {
3011                             adjusted_ty = borrow_vec(cx, span, autoref,
3012                                                      adjusted_ty);
3013                             mk_rptr(cx, autoref.region,
3014                                     mt {ty: adjusted_ty, mutbl: ast::m_imm})
3015                         }
3016
3017                         AutoBorrowFn => {
3018                             borrow_fn(cx, span, autoref, adjusted_ty)
3019                         }
3020                     }
3021                 }
3022             }
3023         }
3024     };
3025
3026     fn borrow_vec(cx: ctxt, span: span,
3027                   autoref: &AutoRef, ty: ty::t) -> ty::t {
3028         match get(ty).sty {
3029             ty_evec(mt, _) => {
3030                 ty::mk_evec(cx, mt {ty: mt.ty, mutbl: autoref.mutbl},
3031                             vstore_slice(autoref.region))
3032             }
3033
3034             ty_estr(_) => {
3035                 ty::mk_estr(cx, vstore_slice(autoref.region))
3036             }
3037
3038             ref s => {
3039                 cx.sess.span_bug(
3040                     span,
3041                     fmt!("borrow-vec associated with bad sty: %?",
3042                          s));
3043             }
3044         }
3045     }
3046
3047     fn borrow_fn(cx: ctxt, span: span,
3048                  autoref: &AutoRef, ty: ty::t) -> ty::t {
3049         match get(ty).sty {
3050             ty_closure(ref fty) => {
3051                 ty::mk_closure(cx, ClosureTy {
3052                     sigil: BorrowedSigil,
3053                     region: autoref.region,
3054                     ..copy *fty
3055                 })
3056             }
3057
3058             ref s => {
3059                 cx.sess.span_bug(
3060                     span,
3061                     fmt!("borrow-fn associated with bad sty: %?",
3062                          s));
3063             }
3064         }
3065     }
3066 }
3067
3068 pub struct ParamsTy {
3069     params: ~[t],
3070     ty: t
3071 }
3072
3073 pub fn expr_ty_params_and_ty(cx: ctxt,
3074                              expr: @ast::expr)
3075                           -> ParamsTy {
3076     ParamsTy {
3077         params: node_id_to_type_params(cx, expr.id),
3078         ty: node_id_to_type(cx, expr.id)
3079     }
3080 }
3081
3082 pub fn expr_has_ty_params(cx: ctxt, expr: @ast::expr) -> bool {
3083     return node_id_has_type_params(cx, expr.id);
3084 }
3085
3086 pub fn method_call_type_param_defs(
3087     tcx: ctxt,
3088     method_map: typeck::method_map,
3089     id: ast::node_id) -> Option<@~[TypeParameterDef]>
3090 {
3091     do method_map.find(&id).map |method| {
3092         match method.origin {
3093           typeck::method_static(did) => {
3094             // n.b.: When we encode impl methods, the bounds
3095             // that we encode include both the impl bounds
3096             // and then the method bounds themselves...
3097             ty::lookup_item_type(tcx, did).generics.type_param_defs
3098           }
3099           typeck::method_param(typeck::method_param {
3100               trait_id: trt_id,
3101               method_num: n_mth, _}) |
3102           typeck::method_trait(trt_id, n_mth, _) |
3103           typeck::method_self(trt_id, n_mth) |
3104           typeck::method_super(trt_id, n_mth) => {
3105             // ...trait methods bounds, in contrast, include only the
3106             // method bounds, so we must preprend the tps from the
3107             // trait itself.  This ought to be harmonized.
3108             let trait_type_param_defs =
3109                 ty::lookup_trait_def(tcx, trt_id).generics.type_param_defs;
3110             @vec::append(
3111                 copy *trait_type_param_defs,
3112                 *ty::trait_method(tcx, trt_id, n_mth).generics.type_param_defs)
3113           }
3114         }
3115     }
3116 }
3117
3118 pub fn resolve_expr(tcx: ctxt, expr: @ast::expr) -> ast::def {
3119     match tcx.def_map.find(&expr.id) {
3120         Some(&def) => def,
3121         None => {
3122             tcx.sess.span_bug(expr.span, fmt!(
3123                 "No def-map entry for expr %?", expr.id));
3124         }
3125     }
3126 }
3127
3128 pub fn expr_is_lval(tcx: ctxt,
3129                     method_map: typeck::method_map,
3130                     e: @ast::expr) -> bool {
3131     match expr_kind(tcx, method_map, e) {
3132         LvalueExpr => true,
3133         RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
3134     }
3135 }
3136
3137 /// We categorize expressions into three kinds.  The distinction between
3138 /// lvalue/rvalue is fundamental to the language.  The distinction between the
3139 /// two kinds of rvalues is an artifact of trans which reflects how we will
3140 /// generate code for that kind of expression.  See trans/expr.rs for more
3141 /// information.
3142 pub enum ExprKind {
3143     LvalueExpr,
3144     RvalueDpsExpr,
3145     RvalueDatumExpr,
3146     RvalueStmtExpr
3147 }
3148
3149 pub fn expr_kind(tcx: ctxt,
3150                  method_map: typeck::method_map,
3151                  expr: @ast::expr) -> ExprKind {
3152     if method_map.contains_key(&expr.id) {
3153         // Overloaded operations are generally calls, and hence they are
3154         // generated via DPS.  However, assign_op (e.g., `x += y`) is an
3155         // exception, as its result is always unit.
3156         return match expr.node {
3157             ast::expr_assign_op(*) => RvalueStmtExpr,
3158             _ => RvalueDpsExpr
3159         };
3160     }
3161
3162     match expr.node {
3163         ast::expr_path(*) => {
3164             match resolve_expr(tcx, expr) {
3165                 ast::def_variant(*) | ast::def_struct(*) => RvalueDpsExpr,
3166
3167                 // Fn pointers are just scalar values.
3168                 ast::def_fn(*) | ast::def_static_method(*) => RvalueDatumExpr,
3169
3170                 // Note: there is actually a good case to be made that
3171                 // def_args, particularly those of immediate type, ought to
3172                 // considered rvalues.
3173                 ast::def_const(*) |
3174                 ast::def_binding(*) |
3175                 ast::def_upvar(*) |
3176                 ast::def_arg(*) |
3177                 ast::def_local(*) |
3178                 ast::def_self(*) => LvalueExpr,
3179
3180                 def => {
3181                     tcx.sess.span_bug(expr.span, fmt!(
3182                         "Uncategorized def for expr %?: %?",
3183                         expr.id, def));
3184                 }
3185             }
3186         }
3187
3188         ast::expr_unary(ast::deref, _) |
3189         ast::expr_field(*) |
3190         ast::expr_index(*) => {
3191             LvalueExpr
3192         }
3193
3194         ast::expr_call(*) |
3195         ast::expr_method_call(*) |
3196         ast::expr_struct(*) |
3197         ast::expr_tup(*) |
3198         ast::expr_if(*) |
3199         ast::expr_match(*) |
3200         ast::expr_fn_block(*) |
3201         ast::expr_loop_body(*) |
3202         ast::expr_do_body(*) |
3203         ast::expr_block(*) |
3204         ast::expr_copy(*) |
3205         ast::expr_repeat(*) |
3206         ast::expr_lit(@codemap::spanned {node: lit_str(_), _}) |
3207         ast::expr_vstore(_, ast::expr_vstore_slice) |
3208         ast::expr_vstore(_, ast::expr_vstore_mut_slice) |
3209         ast::expr_vec(*) => {
3210             RvalueDpsExpr
3211         }
3212
3213         ast::expr_cast(*) => {
3214             match tcx.node_types.find(&(expr.id as uint)) {
3215                 Some(&t) => {
3216                     if ty::type_is_immediate(t) {
3217                         RvalueDatumExpr
3218                     } else {
3219                         RvalueDpsExpr
3220                     }
3221                 }
3222                 None => {
3223                     // Technically, it should not happen that the expr is not
3224                     // present within the table.  However, it DOES happen
3225                     // during type check, because the final types from the
3226                     // expressions are not yet recorded in the tcx.  At that
3227                     // time, though, we are only interested in knowing lvalue
3228                     // vs rvalue.  It would be better to base this decision on
3229                     // the AST type in cast node---but (at the time of this
3230                     // writing) it's not easy to distinguish casts to traits
3231                     // from other casts based on the AST.  This should be
3232                     // easier in the future, when casts to traits would like
3233                     // like @Foo, ~Foo, or &Foo.
3234                     RvalueDatumExpr
3235                 }
3236             }
3237         }
3238
3239         ast::expr_break(*) |
3240         ast::expr_again(*) |
3241         ast::expr_ret(*) |
3242         ast::expr_log(*) |
3243         ast::expr_while(*) |
3244         ast::expr_loop(*) |
3245         ast::expr_assign(*) |
3246         ast::expr_swap(*) |
3247         ast::expr_inline_asm(*) |
3248         ast::expr_assign_op(*) => {
3249             RvalueStmtExpr
3250         }
3251
3252         ast::expr_lit(_) | // Note: lit_str is carved out above
3253         ast::expr_unary(*) |
3254         ast::expr_addr_of(*) |
3255         ast::expr_binary(*) |
3256         ast::expr_vstore(_, ast::expr_vstore_box) |
3257         ast::expr_vstore(_, ast::expr_vstore_mut_box) |
3258         ast::expr_vstore(_, ast::expr_vstore_uniq) => {
3259             RvalueDatumExpr
3260         }
3261
3262         ast::expr_paren(e) => expr_kind(tcx, method_map, e),
3263
3264         ast::expr_mac(*) => {
3265             tcx.sess.span_bug(
3266                 expr.span,
3267                 "macro expression remains after expansion");
3268         }
3269     }
3270 }
3271
3272 pub fn stmt_node_id(s: @ast::stmt) -> ast::node_id {
3273     match s.node {
3274       ast::stmt_decl(_, id) | stmt_expr(_, id) | stmt_semi(_, id) => {
3275         return id;
3276       }
3277       ast::stmt_mac(*) => fail!(~"unexpanded macro in trans")
3278     }
3279 }
3280
3281 pub fn field_idx(id: ast::ident, fields: &[field]) -> Option<uint> {
3282     let mut i = 0u;
3283     for fields.each |f| { if f.ident == id { return Some(i); } i += 1u; }
3284     return None;
3285 }
3286
3287 pub fn field_idx_strict(tcx: ty::ctxt, id: ast::ident, fields: &[field])
3288                      -> uint {
3289     let mut i = 0u;
3290     for fields.each |f| { if f.ident == id { return i; } i += 1u; }
3291     tcx.sess.bug(fmt!(
3292         "No field named `%s` found in the list of fields `%?`",
3293         *tcx.sess.str_of(id),
3294         fields.map(|f| tcx.sess.str_of(f.ident))));
3295 }
3296
3297 pub fn method_idx(id: ast::ident, meths: &[@method]) -> Option<uint> {
3298     vec::position(meths, |m| m.ident == id)
3299 }
3300
3301 /// Returns a vector containing the indices of all type parameters that appear
3302 /// in `ty`.  The vector may contain duplicates.  Probably should be converted
3303 /// to a bitset or some other representation.
3304 pub fn param_tys_in_type(ty: t) -> ~[param_ty] {
3305     let mut rslt = ~[];
3306     do walk_ty(ty) |ty| {
3307         match get(ty).sty {
3308           ty_param(p) => {
3309             rslt.push(p);
3310           }
3311           _ => ()
3312         }
3313     }
3314     rslt
3315 }
3316
3317 pub fn occurs_check(tcx: ctxt, sp: span, vid: TyVid, rt: t) {
3318     // Returns a vec of all the type variables occurring in `ty`. It may
3319     // contain duplicates.  (Integral type vars aren't counted.)
3320     fn vars_in_type(ty: t) -> ~[TyVid] {
3321         let mut rslt = ~[];
3322         do walk_ty(ty) |ty| {
3323             match get(ty).sty {
3324               ty_infer(TyVar(v)) => rslt.push(v),
3325               _ => ()
3326             }
3327         }
3328         rslt
3329     }
3330
3331     // Fast path
3332     if !type_needs_infer(rt) { return; }
3333
3334     // Occurs check!
3335     if vec::contains(vars_in_type(rt), &vid) {
3336             // Maybe this should be span_err -- however, there's an
3337             // assertion later on that the type doesn't contain
3338             // variables, so in this case we have to be sure to die.
3339             tcx.sess.span_fatal
3340                 (sp, ~"type inference failed because I \
3341                      could not find a type\n that's both of the form "
3342                  + ::util::ppaux::ty_to_str(tcx, mk_var(tcx, vid)) +
3343                  ~" and of the form " + ::util::ppaux::ty_to_str(tcx, rt) +
3344                  ~" - such a type would have to be infinitely large.");
3345     }
3346 }
3347
3348 pub fn ty_sort_str(cx: ctxt, t: t) -> ~str {
3349     match get(t).sty {
3350       ty_nil | ty_bot | ty_bool | ty_int(_) |
3351       ty_uint(_) | ty_float(_) | ty_estr(_) |
3352       ty_type | ty_opaque_box | ty_opaque_closure_ptr(_) => {
3353         ::util::ppaux::ty_to_str(cx, t)
3354       }
3355
3356       ty_enum(id, _) => fmt!("enum %s", item_path_str(cx, id)),
3357       ty_box(_) => ~"@-ptr",
3358       ty_uniq(_) => ~"~-ptr",
3359       ty_evec(_, _) => ~"vector",
3360       ty_unboxed_vec(_) => ~"unboxed vector",
3361       ty_ptr(_) => ~"*-ptr",
3362       ty_rptr(_, _) => ~"&-ptr",
3363       ty_bare_fn(_) => ~"extern fn",
3364       ty_closure(_) => ~"fn",
3365       ty_trait(id, _, _, _) => fmt!("trait %s", item_path_str(cx, id)),
3366       ty_struct(id, _) => fmt!("struct %s", item_path_str(cx, id)),
3367       ty_tup(_) => ~"tuple",
3368       ty_infer(TyVar(_)) => ~"inferred type",
3369       ty_infer(IntVar(_)) => ~"integral variable",
3370       ty_infer(FloatVar(_)) => ~"floating-point variable",
3371       ty_param(_) => ~"type parameter",
3372       ty_self(_) => ~"self",
3373       ty_err => ~"type error"
3374     }
3375 }
3376
3377 pub fn type_err_to_str(cx: ctxt, err: &type_err) -> ~str {
3378     /*!
3379      *
3380      * Explains the source of a type err in a short,
3381      * human readable way.  This is meant to be placed in
3382      * parentheses after some larger message.  You should
3383      * also invoke `note_and_explain_type_err()` afterwards
3384      * to present additional details, particularly when
3385      * it comes to lifetime-related errors. */
3386
3387     fn terr_vstore_kind_to_str(k: terr_vstore_kind) -> ~str {
3388         match k {
3389             terr_vec => ~"[]",
3390             terr_str => ~"str",
3391             terr_fn => ~"fn",
3392             terr_trait => ~"trait"
3393         }
3394     }
3395
3396     match *err {
3397         terr_mismatch => ~"types differ",
3398         terr_purity_mismatch(values) => {
3399             fmt!("expected %s fn but found %s fn",
3400                  values.expected.to_str(), values.found.to_str())
3401         }
3402         terr_abi_mismatch(values) => {
3403             fmt!("expected %s fn but found %s fn",
3404                  values.expected.to_str(), values.found.to_str())
3405         }
3406         terr_onceness_mismatch(values) => {
3407             fmt!("expected %s fn but found %s fn",
3408                  values.expected.to_str(), values.found.to_str())
3409         }
3410         terr_sigil_mismatch(values) => {
3411             fmt!("expected %s closure, found %s closure",
3412                  values.expected.to_str(),
3413                  values.found.to_str())
3414         }
3415         terr_mutability => ~"values differ in mutability",
3416         terr_box_mutability => ~"boxed values differ in mutability",
3417         terr_vec_mutability => ~"vectors differ in mutability",
3418         terr_ptr_mutability => ~"pointers differ in mutability",
3419         terr_ref_mutability => ~"references differ in mutability",
3420         terr_ty_param_size(values) => {
3421             fmt!("expected a type with %? type params \
3422                   but found one with %? type params",
3423                  values.expected, values.found)
3424         }
3425         terr_tuple_size(values) => {
3426             fmt!("expected a tuple with %? elements \
3427                   but found one with %? elements",
3428                  values.expected, values.found)
3429         }
3430         terr_record_size(values) => {
3431             fmt!("expected a record with %? fields \
3432                   but found one with %? fields",
3433                  values.expected, values.found)
3434         }
3435         terr_record_mutability => {
3436             ~"record elements differ in mutability"
3437         }
3438         terr_record_fields(values) => {
3439             fmt!("expected a record with field `%s` but found one with field \
3440                   `%s`",
3441                  *cx.sess.str_of(values.expected),
3442                  *cx.sess.str_of(values.found))
3443         }
3444         terr_arg_count => ~"incorrect number of function parameters",
3445         terr_regions_does_not_outlive(*) => {
3446             fmt!("lifetime mismatch")
3447         }
3448         terr_regions_not_same(*) => {
3449             fmt!("lifetimes are not the same")
3450         }
3451         terr_regions_no_overlap(*) => {
3452             fmt!("lifetimes do not intersect")
3453         }
3454         terr_regions_insufficiently_polymorphic(br, _) => {
3455             fmt!("expected bound lifetime parameter %s, \
3456                   but found concrete lifetime",
3457                  bound_region_to_str(cx, br))
3458         }
3459         terr_regions_overly_polymorphic(br, _) => {
3460             fmt!("expected concrete lifetime, \
3461                   but found bound lifetime parameter %s",
3462                  bound_region_to_str(cx, br))
3463         }
3464         terr_vstores_differ(k, ref values) => {
3465             fmt!("%s storage differs: expected %s but found %s",
3466                  terr_vstore_kind_to_str(k),
3467                  vstore_to_str(cx, (*values).expected),
3468                  vstore_to_str(cx, (*values).found))
3469         }
3470         terr_trait_stores_differ(_, ref values) => {
3471             fmt!("trait storage differs: expected %s but found %s",
3472                  trait_store_to_str(cx, (*values).expected),
3473                  trait_store_to_str(cx, (*values).found))
3474         }
3475         terr_in_field(err, fname) => {
3476             fmt!("in field `%s`, %s", *cx.sess.str_of(fname),
3477                  type_err_to_str(cx, err))
3478         }
3479         terr_sorts(values) => {
3480             fmt!("expected %s but found %s",
3481                  ty_sort_str(cx, values.expected),
3482                  ty_sort_str(cx, values.found))
3483         }
3484         terr_traits(values) => {
3485             fmt!("expected trait %s but found trait %s",
3486                  item_path_str(cx, values.expected),
3487                  item_path_str(cx, values.found))
3488         }
3489         terr_self_substs => {
3490             ~"inconsistent self substitution" // XXX this is more of a bug
3491         }
3492         terr_integer_as_char => {
3493             fmt!("expected an integral type but found char")
3494         }
3495         terr_int_mismatch(ref values) => {
3496             fmt!("expected %s but found %s",
3497                  values.expected.to_str(),
3498                  values.found.to_str())
3499         }
3500         terr_float_mismatch(ref values) => {
3501             fmt!("expected %s but found %s",
3502                  values.expected.to_str(),
3503                  values.found.to_str())
3504         }
3505     }
3506 }
3507
3508 pub fn note_and_explain_type_err(cx: ctxt, err: &type_err) {
3509     match *err {
3510         terr_regions_does_not_outlive(subregion, superregion) => {
3511             note_and_explain_region(cx, ~"", subregion, ~"...");
3512             note_and_explain_region(cx, ~"...does not necessarily outlive ",
3513                                     superregion, ~"");
3514         }
3515         terr_regions_not_same(region1, region2) => {
3516             note_and_explain_region(cx, ~"", region1, ~"...");
3517             note_and_explain_region(cx, ~"...is not the same lifetime as ",
3518                                     region2, ~"");
3519         }
3520         terr_regions_no_overlap(region1, region2) => {
3521             note_and_explain_region(cx, ~"", region1, ~"...");
3522             note_and_explain_region(cx, ~"...does not overlap ",
3523                                     region2, ~"");
3524         }
3525         terr_regions_insufficiently_polymorphic(_, conc_region) => {
3526             note_and_explain_region(cx,
3527                                     ~"concrete lifetime that was found is ",
3528                                     conc_region, ~"");
3529         }
3530         terr_regions_overly_polymorphic(_, conc_region) => {
3531             note_and_explain_region(cx,
3532                                     ~"expected concrete lifetime is ",
3533                                     conc_region, ~"");
3534         }
3535         _ => {}
3536     }
3537 }
3538
3539 pub fn def_has_ty_params(def: ast::def) -> bool {
3540     match def {
3541       ast::def_fn(_, _) | ast::def_variant(_, _) | ast::def_struct(_)
3542         => true,
3543       _ => false
3544     }
3545 }
3546
3547 pub fn provided_trait_methods(cx: ctxt, id: ast::def_id) -> ~[ast::ident] {
3548     if is_local(id) {
3549         match cx.items.find(&id.node) {
3550             Some(&ast_map::node_item(@ast::item {
3551                         node: item_trait(_, _, ref ms),
3552                         _
3553                     }, _)) =>
3554                 match ast_util::split_trait_methods(*ms) {
3555                    (_, p) => p.map(|method| method.ident)
3556                 },
3557             _ => cx.sess.bug(fmt!("provided_trait_methods: %? is not a trait",
3558                                   id))
3559         }
3560     } else {
3561         csearch::get_provided_trait_methods(cx, id).map(|ifo| ifo.ty.ident)
3562     }
3563 }
3564
3565 pub fn trait_supertraits(cx: ctxt,
3566                          id: ast::def_id) -> @~[@TraitRef]
3567 {
3568     // Check the cache.
3569     match cx.supertraits.find(&id) {
3570         Some(&trait_refs) => { return trait_refs; }
3571         None => {}  // Continue.
3572     }
3573
3574     // Not in the cache. It had better be in the metadata, which means it
3575     // shouldn't be local.
3576     assert!(!is_local(id));
3577
3578     // Get the supertraits out of the metadata and create the
3579     // TraitRef for each.
3580     let result = @csearch::get_supertraits(cx, id);
3581     cx.supertraits.insert(id, result);
3582     return result;
3583 }
3584
3585 pub fn trait_ref_supertraits(cx: ctxt, trait_ref: &ty::TraitRef) -> ~[@TraitRef] {
3586     let supertrait_refs = trait_supertraits(cx, trait_ref.def_id);
3587     supertrait_refs.map(
3588         |supertrait_ref| @supertrait_ref.subst(cx, &trait_ref.substs))
3589 }
3590
3591 fn lookup_locally_or_in_crate_store<V:Copy>(
3592     descr: &str,
3593     def_id: ast::def_id,
3594     map: &mut HashMap<ast::def_id, V>,
3595     load_external: &fn() -> V) -> V
3596 {
3597     /*!
3598      *
3599      * Helper for looking things up in the various maps
3600      * that are populated during typeck::collect (e.g.,
3601      * `cx.methods`, `cx.tcache`, etc).  All of these share
3602      * the pattern that if the id is local, it should have
3603      * been loaded into the map by the `typeck::collect` phase.
3604      * If the def-id is external, then we have to go consult
3605      * the crate loading code (and cache the result for the future).
3606      */
3607
3608     match map.find(&def_id) {
3609         Some(&v) => { return v; }
3610         None => { }
3611     }
3612
3613     if def_id.crate == ast::local_crate {
3614         fail!(fmt!("No def'n found for %? in tcx.%s",
3615                    def_id, descr));
3616     }
3617     let v = load_external();
3618     map.insert(def_id, v);
3619     return v;
3620 }
3621
3622 pub fn trait_method(cx: ctxt, trait_did: ast::def_id, idx: uint) -> @method {
3623     let method_def_id = ty::trait_method_def_ids(cx, trait_did)[idx];
3624     ty::method(cx, method_def_id)
3625 }
3626
3627 pub fn trait_methods(cx: ctxt, trait_did: ast::def_id) -> @~[@method] {
3628     match cx.trait_methods_cache.find(&trait_did) {
3629         Some(&methods) => methods,
3630         None => {
3631             let def_ids = ty::trait_method_def_ids(cx, trait_did);
3632             let methods = @def_ids.map(|d| ty::method(cx, *d));
3633             cx.trait_methods_cache.insert(trait_did, methods);
3634             methods
3635         }
3636     }
3637 }
3638
3639 pub fn method(cx: ctxt, id: ast::def_id) -> @method {
3640     lookup_locally_or_in_crate_store(
3641         "methods", id, cx.methods,
3642         || @csearch::get_method(cx, id))
3643 }
3644
3645 pub fn trait_method_def_ids(cx: ctxt, id: ast::def_id) -> @~[def_id] {
3646     lookup_locally_or_in_crate_store(
3647         "methods", id, cx.trait_method_def_ids,
3648         || @csearch::get_trait_method_def_ids(cx.cstore, id))
3649 }
3650
3651 pub fn impl_trait_refs(cx: ctxt, id: ast::def_id) -> ~[@TraitRef] {
3652     if id.crate == ast::local_crate {
3653         debug!("(impl_traits) searching for trait impl %?", id);
3654         match cx.items.find(&id.node) {
3655            Some(&ast_map::node_item(@ast::item {
3656                         node: ast::item_impl(_, opt_trait, _, _),
3657                         _},
3658                     _)) => {
3659                match opt_trait {
3660                    Some(t) => ~[ty::node_id_to_trait_ref(cx, t.ref_id)],
3661                    None => ~[]
3662                }
3663            }
3664            _ => ~[]
3665         }
3666     } else {
3667         csearch::get_impl_traits(cx, id)
3668     }
3669 }
3670
3671 pub fn ty_to_def_id(ty: t) -> Option<ast::def_id> {
3672     match get(ty).sty {
3673       ty_trait(id, _, _, _) | ty_struct(id, _) | ty_enum(id, _) => Some(id),
3674       _ => None
3675     }
3676 }
3677
3678 /// Returns the def ID of the constructor for the given tuple-like struct, or
3679 /// None if the struct is not tuple-like. Fails if the given def ID does not
3680 /// refer to a struct at all.
3681 fn struct_ctor_id(cx: ctxt, struct_did: ast::def_id) -> Option<ast::def_id> {
3682     if struct_did.crate != ast::local_crate {
3683         // XXX: Cross-crate functionality.
3684         cx.sess.unimpl(~"constructor ID of cross-crate tuple structs");
3685     }
3686
3687     match cx.items.find(&struct_did.node) {
3688         Some(&ast_map::node_item(item, _)) => {
3689             match item.node {
3690                 ast::item_struct(struct_def, _) => {
3691                     struct_def.ctor_id.map(|ctor_id|
3692                         ast_util::local_def(*ctor_id))
3693                 }
3694                 _ => cx.sess.bug(~"called struct_ctor_id on non-struct")
3695             }
3696         }
3697         _ => cx.sess.bug(~"called struct_ctor_id on non-struct")
3698     }
3699 }
3700
3701 // Enum information
3702 pub struct VariantInfo_ {
3703     args: ~[t],
3704     ctor_ty: t,
3705     name: ast::ident,
3706     id: ast::def_id,
3707     disr_val: int,
3708     vis: visibility
3709 }
3710
3711 pub type VariantInfo = @VariantInfo_;
3712
3713 pub fn substd_enum_variants(cx: ctxt,
3714                             id: ast::def_id,
3715                             substs: &substs)
3716                          -> ~[VariantInfo] {
3717     do vec::map(*enum_variants(cx, id)) |variant_info| {
3718         let substd_args = vec::map(variant_info.args,
3719                                    |aty| subst(cx, substs, *aty));
3720
3721         let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
3722
3723         @VariantInfo_{args: substd_args, ctor_ty: substd_ctor_ty,
3724                       ../*bad*/copy **variant_info}
3725     }
3726 }
3727
3728 pub fn item_path_str(cx: ctxt, id: ast::def_id) -> ~str {
3729     ast_map::path_to_str(item_path(cx, id), cx.sess.parse_sess.interner)
3730 }
3731
3732 pub enum DtorKind {
3733     NoDtor,
3734     TraitDtor(def_id)
3735 }
3736
3737 pub impl DtorKind {
3738     fn is_not_present(&const self) -> bool {
3739         match *self {
3740             NoDtor => true,
3741             _ => false
3742         }
3743     }
3744     fn is_present(&const self) -> bool {
3745         !self.is_not_present()
3746     }
3747 }
3748
3749 /* If struct_id names a struct with a dtor, return Some(the dtor's id).
3750    Otherwise return none. */
3751 pub fn ty_dtor(cx: ctxt, struct_id: def_id) -> DtorKind {
3752     match cx.destructor_for_type.find(&struct_id) {
3753         Some(&method_def_id) => TraitDtor(method_def_id),
3754         None => NoDtor,
3755     }
3756 }
3757
3758 pub fn has_dtor(cx: ctxt, struct_id: def_id) -> bool {
3759     ty_dtor(cx, struct_id).is_present()
3760 }
3761
3762 pub fn item_path(cx: ctxt, id: ast::def_id) -> ast_map::path {
3763     if id.crate != ast::local_crate {
3764         csearch::get_item_path(cx, id)
3765     } else {
3766         // FIXME (#5521): uncomment this code and don't have a catch-all at the
3767         //                end of the match statement. Favor explicitly listing
3768         //                each variant.
3769         // let node = cx.items.get(&id.node);
3770         // match *node {
3771         match *cx.items.get(&id.node) {
3772           ast_map::node_item(item, path) => {
3773             let item_elt = match item.node {
3774               item_mod(_) | item_foreign_mod(_) => {
3775                 ast_map::path_mod(item.ident)
3776               }
3777               _ => {
3778                 ast_map::path_name(item.ident)
3779               }
3780             };
3781             vec::append_one(/*bad*/copy *path, item_elt)
3782           }
3783
3784           ast_map::node_foreign_item(nitem, _, _, path) => {
3785             vec::append_one(/*bad*/copy *path,
3786                             ast_map::path_name(nitem.ident))
3787           }
3788
3789           ast_map::node_method(method, _, path) => {
3790             vec::append_one(/*bad*/copy *path,
3791                             ast_map::path_name(method.ident))
3792           }
3793           ast_map::node_trait_method(trait_method, _, path) => {
3794             let method = ast_util::trait_method_to_ty_method(&*trait_method);
3795             vec::append_one(/*bad*/copy *path,
3796                             ast_map::path_name(method.ident))
3797           }
3798
3799           ast_map::node_variant(ref variant, _, path) => {
3800             vec::append_one(vec::from_slice(vec::init(*path)),
3801                             ast_map::path_name((*variant).node.name))
3802           }
3803
3804           ast_map::node_struct_ctor(_, item, path) => {
3805             vec::append_one(/*bad*/copy *path, ast_map::path_name(item.ident))
3806           }
3807
3808           ref node => {
3809             cx.sess.bug(fmt!("cannot find item_path for node %?", node));
3810           }
3811         }
3812     }
3813 }
3814
3815 pub fn enum_is_univariant(cx: ctxt, id: ast::def_id) -> bool {
3816     enum_variants(cx, id).len() == 1
3817 }
3818
3819 pub fn type_is_empty(cx: ctxt, t: t) -> bool {
3820     match ty::get(t).sty {
3821        ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
3822        _ => false
3823      }
3824 }
3825
3826 pub fn enum_variants(cx: ctxt, id: ast::def_id) -> @~[VariantInfo] {
3827     match cx.enum_var_cache.find(&id) {
3828       Some(&variants) => return variants,
3829       _ => { /* fallthrough */ }
3830     }
3831
3832     let result = if ast::local_crate != id.crate {
3833         @csearch::get_enum_variants(cx, id)
3834     } else {
3835         /*
3836           Although both this code and check_enum_variants in typeck/check
3837           call eval_const_expr, it should never get called twice for the same
3838           expr, since check_enum_variants also updates the enum_var_cache
3839          */
3840         match *cx.items.get(&id.node) {
3841           ast_map::node_item(@ast::item {
3842                     node: ast::item_enum(ref enum_definition, _),
3843                     _
3844                 }, _) => {
3845             let mut disr_val = -1;
3846             @vec::map(enum_definition.variants, |variant| {
3847                 match variant.node.kind {
3848                     ast::tuple_variant_kind(ref args) => {
3849                         let ctor_ty = node_id_to_type(cx, variant.node.id);
3850                         let arg_tys = {
3851                             if args.len() > 0u {
3852                                 ty_fn_args(ctor_ty).map(|a| a.ty)
3853                             } else {
3854                                 ~[]
3855                             }
3856                         };
3857                         match variant.node.disr_expr {
3858                           Some (ex) => {
3859                             disr_val = match const_eval::eval_const_expr(cx,
3860                                                                          ex) {
3861                               const_eval::const_int(val) => val as int,
3862                               _ => cx.sess.bug(~"tag_variants: bad disr expr")
3863                             }
3864                           }
3865                           _ => disr_val += 1
3866                         }
3867                         @VariantInfo_{args: arg_tys,
3868                           ctor_ty: ctor_ty,
3869                           name: variant.node.name,
3870                           id: ast_util::local_def(variant.node.id),
3871                           disr_val: disr_val,
3872                           vis: variant.node.vis
3873                          }
3874                     }
3875                     ast::struct_variant_kind(_) => {
3876                         fail!(~"struct variant kinds unimpl in enum_variants")
3877                     }
3878                 }
3879             })
3880           }
3881           _ => cx.sess.bug(~"tag_variants: id not bound to an enum")
3882         }
3883     };
3884     cx.enum_var_cache.insert(id, result);
3885     result
3886 }
3887
3888
3889 // Returns information about the enum variant with the given ID:
3890 pub fn enum_variant_with_id(cx: ctxt,
3891                             enum_id: ast::def_id,
3892                             variant_id: ast::def_id)
3893                          -> VariantInfo {
3894     let variants = enum_variants(cx, enum_id);
3895     let mut i = 0;
3896     while i < variants.len() {
3897         let variant = variants[i];
3898         if variant.id == variant_id { return variant; }
3899         i += 1;
3900     }
3901     cx.sess.bug(~"enum_variant_with_id(): no variant exists with that ID");
3902 }
3903
3904
3905 // If the given item is in an external crate, looks up its type and adds it to
3906 // the type cache. Returns the type parameters and type.
3907 pub fn lookup_item_type(cx: ctxt,
3908                         did: ast::def_id)
3909                      -> ty_param_bounds_and_ty {
3910     lookup_locally_or_in_crate_store(
3911         "tcache", did, cx.tcache,
3912         || csearch::get_type(cx, did))
3913 }
3914
3915 /// Given the did of a trait, returns its canonical trait ref.
3916 pub fn lookup_trait_def(cx: ctxt, did: ast::def_id) -> @ty::TraitDef {
3917     match cx.trait_defs.find(&did) {
3918         Some(&trait_def) => {
3919             // The item is in this crate. The caller should have added it to the
3920             // type cache already
3921             return trait_def;
3922         }
3923         None => {
3924             assert!(did.crate != ast::local_crate);
3925             let trait_def = @csearch::get_trait_def(cx, did);
3926             cx.trait_defs.insert(did, trait_def);
3927             return trait_def;
3928         }
3929     }
3930 }
3931
3932 // Determine whether an item is annotated with #[packed] or not
3933 pub fn lookup_packed(tcx: ctxt,
3934                   did: def_id) -> bool {
3935     if is_local(did) {
3936         match tcx.items.find(&did.node) {
3937             Some(
3938                 &ast_map::node_item(@ast::item {
3939                     attrs: ref attrs,
3940                     _
3941                 }, _)) => attr::attrs_contains_name(*attrs, "packed"),
3942             _ => tcx.sess.bug(fmt!("lookup_packed: %? is not an item",
3943                                    did))
3944         }
3945     } else {
3946         let mut ret = false;
3947         do csearch::get_item_attrs(tcx.cstore, did) |meta_items| {
3948             ret = attr::contains_name(meta_items, "packed");
3949         }
3950         ret
3951     }
3952 }
3953
3954 // Look up a field ID, whether or not it's local
3955 // Takes a list of type substs in case the struct is generic
3956 pub fn lookup_field_type(tcx: ctxt,
3957                          struct_id: def_id,
3958                          id: def_id,
3959                          substs: &substs)
3960                       -> ty::t {
3961     let t = if id.crate == ast::local_crate {
3962         node_id_to_type(tcx, id.node)
3963     }
3964     else {
3965         match tcx.tcache.find(&id) {
3966            Some(tpt) => tpt.ty,
3967            None => {
3968                let tpt = csearch::get_field_type(tcx, struct_id, id);
3969                tcx.tcache.insert(id, tpt);
3970                tpt.ty
3971            }
3972         }
3973     };
3974     subst(tcx, substs, t)
3975 }
3976
3977 // Look up the list of field names and IDs for a given struct
3978 // Fails if the id is not bound to a struct.
3979 pub fn lookup_struct_fields(cx: ctxt, did: ast::def_id) -> ~[field_ty] {
3980   if did.crate == ast::local_crate {
3981     match cx.items.find(&did.node) {
3982        Some(&ast_map::node_item(i,_)) => {
3983          match i.node {
3984             ast::item_struct(struct_def, _) => {
3985                struct_field_tys(struct_def.fields)
3986             }
3987             _ => cx.sess.bug(~"struct ID bound to non-struct")
3988          }
3989        }
3990        Some(&ast_map::node_variant(ref variant, _, _)) => {
3991           match (*variant).node.kind {
3992             ast::struct_variant_kind(struct_def) => {
3993               struct_field_tys(struct_def.fields)
3994             }
3995             _ => {
3996               cx.sess.bug(~"struct ID bound to enum variant that isn't \
3997                             struct-like")
3998             }
3999           }
4000        }
4001        _ => {
4002            cx.sess.bug(
4003                fmt!("struct ID not bound to an item: %s",
4004                     ast_map::node_id_to_str(cx.items, did.node,
4005                                             cx.sess.parse_sess.interner)));
4006        }
4007     }
4008         }
4009   else {
4010         return csearch::get_struct_fields(cx.sess.cstore, did);
4011     }
4012 }
4013
4014 pub fn lookup_struct_field(cx: ctxt,
4015                            parent: ast::def_id,
4016                            field_id: ast::def_id)
4017                         -> field_ty {
4018     match vec::find(lookup_struct_fields(cx, parent),
4019                  |f| f.id.node == field_id.node) {
4020         Some(t) => t,
4021         None => cx.sess.bug(~"struct ID not found in parent's fields")
4022     }
4023 }
4024
4025 fn struct_field_tys(fields: &[@struct_field]) -> ~[field_ty] {
4026     do fields.map |field| {
4027         match field.node.kind {
4028             named_field(ident, mutability, visibility) => {
4029                 field_ty {
4030                     ident: ident,
4031                     id: ast_util::local_def(field.node.id),
4032                     vis: visibility,
4033                     mutability: mutability,
4034                 }
4035             }
4036             unnamed_field => {
4037                 field_ty {
4038                     ident:
4039                         syntax::parse::token::special_idents::unnamed_field,
4040                     id: ast_util::local_def(field.node.id),
4041                     vis: ast::public,
4042                     mutability: ast::struct_immutable,
4043                 }
4044             }
4045         }
4046     }
4047 }
4048
4049 // Return a list of fields corresponding to the struct's items
4050 // (as if the struct was a record). trans uses this
4051 // Takes a list of substs with which to instantiate field types
4052 // Keep in mind that this function reports that all fields are
4053 // mutable, regardless of how they were declared. It's meant to
4054 // be used in trans.
4055 pub fn struct_mutable_fields(cx: ctxt,
4056                              did: ast::def_id,
4057                              substs: &substs)
4058                           -> ~[field] {
4059     struct_item_fields(cx, did, substs, |_mt| m_mutbl)
4060 }
4061
4062 // Same as struct_mutable_fields, but doesn't change
4063 // mutability.
4064 pub fn struct_fields(cx: ctxt,
4065                      did: ast::def_id,
4066                      substs: &substs)
4067                   -> ~[field] {
4068     struct_item_fields(cx, did, substs, |mt| match mt {
4069       struct_mutable => m_mutbl,
4070         struct_immutable => m_imm })
4071 }
4072
4073
4074 fn struct_item_fields(cx:ctxt,
4075                      did: ast::def_id,
4076                      substs: &substs,
4077                      frob_mutability: &fn(struct_mutability) -> mutability)
4078     -> ~[field] {
4079     do lookup_struct_fields(cx, did).map |f| {
4080        // consider all instance vars mut, because the
4081        // constructor may mutate all vars
4082        field {
4083            ident: f.ident,
4084             mt: mt {
4085                 ty: lookup_field_type(cx, did, f.id, substs),
4086                 mutbl: frob_mutability(f.mutability)
4087             }
4088         }
4089     }
4090 }
4091
4092 pub fn is_binopable(_cx: ctxt, ty: t, op: ast::binop) -> bool {
4093     static tycat_other: int = 0;
4094     static tycat_bool: int = 1;
4095     static tycat_int: int = 2;
4096     static tycat_float: int = 3;
4097     static tycat_struct: int = 4;
4098     static tycat_bot: int = 5;
4099
4100     static opcat_add: int = 0;
4101     static opcat_sub: int = 1;
4102     static opcat_mult: int = 2;
4103     static opcat_shift: int = 3;
4104     static opcat_rel: int = 4;
4105     static opcat_eq: int = 5;
4106     static opcat_bit: int = 6;
4107     static opcat_logic: int = 7;
4108
4109     fn opcat(op: ast::binop) -> int {
4110         match op {
4111           ast::add => opcat_add,
4112           ast::subtract => opcat_sub,
4113           ast::mul => opcat_mult,
4114           ast::div => opcat_mult,
4115           ast::rem => opcat_mult,
4116           ast::and => opcat_logic,
4117           ast::or => opcat_logic,
4118           ast::bitxor => opcat_bit,
4119           ast::bitand => opcat_bit,
4120           ast::bitor => opcat_bit,
4121           ast::shl => opcat_shift,
4122           ast::shr => opcat_shift,
4123           ast::eq => opcat_eq,
4124           ast::ne => opcat_eq,
4125           ast::lt => opcat_rel,
4126           ast::le => opcat_rel,
4127           ast::ge => opcat_rel,
4128           ast::gt => opcat_rel
4129         }
4130     }
4131
4132     fn tycat(ty: t) -> int {
4133         match get(ty).sty {
4134           ty_bool => tycat_bool,
4135           ty_int(_) | ty_uint(_) | ty_infer(IntVar(_)) => tycat_int,
4136           ty_float(_) | ty_infer(FloatVar(_)) => tycat_float,
4137           ty_tup(_) | ty_enum(_, _) => tycat_struct,
4138           ty_bot => tycat_bot,
4139           _ => tycat_other
4140         }
4141     }
4142
4143     static t: bool = true;
4144     static f: bool = false;
4145
4146     let tbl = ~[
4147     /*.          add,     shift,   bit
4148       .             sub,     rel,     logic
4149       .                mult,    eq,         */
4150     /*other*/   ~[f, f, f, f, f, f, f, f],
4151     /*bool*/    ~[f, f, f, f, t, t, t, t],
4152     /*int*/     ~[t, t, t, t, t, t, t, f],
4153     /*float*/   ~[t, t, t, f, t, t, f, f],
4154     /*bot*/     ~[f, f, f, f, f, f, f, f],
4155     /*struct*/  ~[t, t, t, t, f, f, t, t]];
4156
4157     return tbl[tycat(ty)][opcat(op)];
4158 }
4159
4160 pub fn ty_params_to_tys(tcx: ty::ctxt, generics: &ast::Generics) -> ~[t] {
4161     vec::from_fn(generics.ty_params.len(), |i| {
4162         let id = generics.ty_params.get(i).id;
4163         ty::mk_param(tcx, i, ast_util::local_def(id))
4164     })
4165 }
4166
4167 /// Returns an equivalent type with all the typedefs and self regions removed.
4168 pub fn normalize_ty(cx: ctxt, t: t) -> t {
4169     fn normalize_mt(cx: ctxt, mt: mt) -> mt {
4170         mt { ty: normalize_ty(cx, mt.ty), mutbl: mt.mutbl }
4171     }
4172     fn normalize_vstore(vstore: vstore) -> vstore {
4173         match vstore {
4174             vstore_fixed(*) | vstore_uniq | vstore_box => vstore,
4175             vstore_slice(_) => vstore_slice(re_static)
4176         }
4177     }
4178
4179     match cx.normalized_cache.find(&t) {
4180       Some(&t) => return t,
4181       None => ()
4182     }
4183
4184     let t = match get(t).sty {
4185         ty_evec(mt, vstore) =>
4186             // This type has a vstore. Get rid of it
4187             mk_evec(cx, normalize_mt(cx, mt), normalize_vstore(vstore)),
4188
4189         ty_estr(vstore) =>
4190             // This type has a vstore. Get rid of it
4191             mk_estr(cx, normalize_vstore(vstore)),
4192
4193         ty_rptr(_, mt) =>
4194             // This type has a region. Get rid of it
4195             mk_rptr(cx, re_static, normalize_mt(cx, mt)),
4196
4197         ty_closure(ref closure_ty) => {
4198             mk_closure(cx, ClosureTy {
4199                 region: ty::re_static,
4200                 ..copy *closure_ty
4201             })
4202         }
4203
4204         ty_enum(did, ref r) =>
4205             match (*r).self_r {
4206                 Some(_) =>
4207                     // Use re_static since trans doesn't care about regions
4208                     mk_enum(cx, did,
4209                      substs {
4210                         self_r: Some(ty::re_static),
4211                         self_ty: None,
4212                         tps: /*bad*/copy (*r).tps
4213                      }),
4214                 None =>
4215                     t
4216             },
4217
4218         ty_struct(did, ref r) =>
4219             match (*r).self_r {
4220               Some(_) =>
4221                 // Ditto.
4222                 mk_struct(cx, did, substs {self_r: Some(ty::re_static),
4223                                            self_ty: None,
4224                                            tps: /*bad*/copy (*r).tps}),
4225               None =>
4226                 t
4227             },
4228
4229         _ =>
4230             t
4231     };
4232
4233     let sty = fold_sty(&get(t).sty, |t| { normalize_ty(cx, t) });
4234     let t_norm = mk_t(cx, sty);
4235     cx.normalized_cache.insert(t, t_norm);
4236     return t_norm;
4237 }
4238
4239 // Returns the repeat count for a repeating vector expression.
4240 pub fn eval_repeat_count(tcx: ctxt, count_expr: @ast::expr) -> uint {
4241     match const_eval::eval_const_expr_partial(tcx, count_expr) {
4242       Ok(ref const_val) => match *const_val {
4243         const_eval::const_int(count) => return count as uint,
4244         const_eval::const_uint(count) => return count as uint,
4245         const_eval::const_float(count) => {
4246             tcx.sess.span_err(count_expr.span,
4247                               "expected signed or unsigned integer for \
4248                                repeat count but found float");
4249             return count as uint;
4250         }
4251         const_eval::const_str(_) => {
4252             tcx.sess.span_err(count_expr.span,
4253                               "expected signed or unsigned integer for \
4254                                repeat count but found string");
4255             return 0;
4256         }
4257         const_eval::const_bool(_) => {
4258             tcx.sess.span_err(count_expr.span,
4259                               "expected signed or unsigned integer for \
4260                                repeat count but found boolean");
4261             return 0;
4262         }
4263       },
4264       Err(*) => {
4265         tcx.sess.span_err(count_expr.span,
4266                           "expected constant integer for repeat count \
4267                            but found variable");
4268         return 0;
4269       }
4270     }
4271 }
4272
4273 // Determine what purity to check a nested function under
4274 pub fn determine_inherited_purity(parent: (ast::purity, ast::node_id),
4275                                   child: (ast::purity, ast::node_id),
4276                                   child_sigil: ast::Sigil)
4277                                     -> (ast::purity, ast::node_id) {
4278     // If the closure is a stack closure and hasn't had some non-standard
4279     // purity inferred for it, then check it under its parent's purity.
4280     // Otherwise, use its own
4281     match child_sigil {
4282         ast::BorrowedSigil if child.first() == ast::impure_fn => parent,
4283         _ => child
4284     }
4285 }
4286
4287 // Iterate over a type parameter's bounded traits and any supertraits
4288 // of those traits, ignoring kinds.
4289 // Here, the supertraits are the transitive closure of the supertrait
4290 // relation on the supertraits from each bounded trait's constraint
4291 // list.
4292 pub fn each_bound_trait_and_supertraits(tcx: ctxt,
4293                                          bounds: param_bounds,
4294                                          f: &fn(&TraitRef) -> bool) {
4295     for bounds.each |bound| {
4296         let bound_trait_ref = match *bound {
4297             ty::bound_trait(bound_t) => bound_t,
4298
4299             ty::bound_copy | ty::bound_owned |
4300             ty::bound_const | ty::bound_durable => {
4301                 loop; // skip non-trait bounds
4302             }
4303         };
4304
4305         let mut supertrait_set = HashMap::new();
4306         let mut trait_refs = ~[];
4307         let mut i = 0;
4308
4309         // Seed the worklist with the trait from the bound
4310         supertrait_set.insert(bound_trait_ref.def_id, ());
4311         trait_refs.push(bound_trait_ref);
4312
4313         // Add the given trait ty to the hash map
4314         while i < trait_refs.len() {
4315             debug!("each_bound_trait_and_supertraits(i=%?, trait_ref=%s)",
4316                    i, trait_refs[i].repr(tcx));
4317
4318             if !f(trait_refs[i]) {
4319                 return;
4320             }
4321
4322             // Add supertraits to supertrait_set
4323             let supertrait_refs = trait_ref_supertraits(tcx, trait_refs[i]);
4324             for supertrait_refs.each |&supertrait_ref| {
4325                 debug!("each_bound_trait_and_supertraits(supertrait_ref=%s)",
4326                        supertrait_ref.repr(tcx));
4327
4328                 let d_id = supertrait_ref.def_id;
4329                 if !supertrait_set.contains_key(&d_id) {
4330                     // FIXME(#5527) Could have same trait multiple times
4331                     supertrait_set.insert(d_id, ());
4332                     trait_refs.push(supertrait_ref);
4333                 }
4334             }
4335
4336             i += 1;
4337         }
4338     }
4339 }
4340
4341 pub fn count_traits_and_supertraits(tcx: ctxt,
4342                                     type_param_defs: &[TypeParameterDef]) -> uint {
4343     let mut total = 0;
4344     for type_param_defs.each |type_param_def| {
4345         for each_bound_trait_and_supertraits(tcx, type_param_def.bounds) |_| {
4346             total += 1;
4347         }
4348     }
4349     return total;
4350 }
4351
4352 // Given a trait and a type, returns the impl of that type
4353 pub fn get_impl_id(tcx: ctxt, trait_id: def_id, self_ty: t) -> def_id {
4354     match tcx.trait_impls.find(&trait_id) {
4355         Some(ty_to_impl) => match ty_to_impl.find(&self_ty) {
4356             Some(the_impl) => the_impl.did,
4357             None => // try autoderef!
4358                 match deref(tcx, self_ty, false) {
4359                     Some(some_ty) => get_impl_id(tcx, trait_id, some_ty.ty),
4360                     None => tcx.sess.bug(~"get_impl_id: no impl of trait for \
4361                                            this type")
4362             }
4363         },
4364         None => tcx.sess.bug(~"get_impl_id: trait isn't in trait_impls")
4365     }
4366 }
4367
4368 pub fn visitor_object_ty(tcx: ctxt) -> (@TraitRef, t) {
4369     let ty_visitor_name = special_idents::ty_visitor;
4370     assert!(tcx.intrinsic_traits.contains_key(&ty_visitor_name));
4371     let trait_ref = *tcx.intrinsic_traits.get(&ty_visitor_name);
4372     (trait_ref,
4373      mk_trait(tcx, trait_ref.def_id, copy trait_ref.substs, BoxTraitStore, ast::m_imm))
4374 }