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