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