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