src/librustc/middle/ty.rs

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