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