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