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