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