src/librustc/middle/ty.rs

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