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