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