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