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