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.
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.
11 #![allow(non_camel_case_types)]
14 use driver::session::Session;
15 use metadata::csearch;
16 use mc = middle::mem_categorization;
17 use middle::const_eval;
18 use middle::dependency_format;
19 use middle::lang_items::{ExchangeHeapLangItem, OpaqueStructLangItem};
20 use middle::lang_items::{TyDescStructLangItem, TyVisitorTraitLangItem};
23 use middle::resolve_lifetime;
25 use middle::subst::Subst;
27 use middle::typeck::MethodCall;
29 use middle::ty_fold::{TypeFoldable,TypeFolder};
31 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_str};
32 use util::ppaux::{trait_store_to_str, ty_to_str};
33 use util::ppaux::{Repr, UserString};
34 use util::common::{indenter};
35 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet, FnvHashMap};
37 use std::cell::{Cell, RefCell};
41 use std::hash::{Hash, sip};
42 use std::iter::AdditiveIterator;
46 use collections::{HashMap, HashSet};
49 use syntax::ast_util::{is_local, lit_is_str};
52 use syntax::attr::AttrMetaMethods;
53 use syntax::codemap::Span;
54 use syntax::parse::token;
55 use syntax::parse::token::InternedString;
56 use syntax::{ast, ast_map};
57 use syntax::owned_slice::OwnedSlice;
58 use syntax::util::small_vector::SmallVector;
59 use collections::enum_set::{EnumSet, CLike};
63 pub static INITIAL_DISCRIMINANT_VALUE: Disr = 0;
67 #[deriving(Eq, TotalEq, Hash)]
69 pub ident: ast::Ident,
74 pub enum MethodContainer {
75 TraitContainer(ast::DefId),
76 ImplContainer(ast::DefId),
81 pub ident: ast::Ident,
82 pub generics: ty::Generics,
84 pub explicit_self: ast::ExplicitSelf_,
85 pub vis: ast::Visibility,
86 pub def_id: ast::DefId,
87 pub container: MethodContainer,
89 // If this method is provided, we need to know where it came from
90 pub provided_source: Option<ast::DefId>
94 pub fn new(ident: ast::Ident,
95 generics: ty::Generics,
97 explicit_self: ast::ExplicitSelf_,
100 container: MethodContainer,
101 provided_source: Option<ast::DefId>)
107 explicit_self: explicit_self,
110 container: container,
111 provided_source: provided_source
115 pub fn container_id(&self) -> ast::DefId {
116 match self.container {
117 TraitContainer(id) => id,
118 ImplContainer(id) => id,
123 #[deriving(Clone, Eq, TotalEq, Hash)]
126 pub mutbl: ast::Mutability,
129 #[deriving(Clone, Eq, TotalEq, Hash, Encodable, Decodable, Show)]
130 pub enum TraitStore {
133 /// &Trait and &mut Trait
134 RegionTraitStore(Region, ast::Mutability),
138 pub struct field_ty {
141 pub vis: ast::Visibility,
142 pub origin: ast::DefId, // The DefId of the struct in which the field is declared.
145 // Contains information needed to resolve types and (in the future) look up
146 // the types of AST nodes.
147 #[deriving(Eq, TotalEq, Hash)]
148 pub struct creader_cache_key {
154 pub type creader_cache = RefCell<HashMap<creader_cache_key, t>>;
156 pub struct intern_key {
160 // NB: Do not replace this with #[deriving(Eq)]. The automatically-derived
161 // implementation will not recurse through sty and you will get stack
163 impl cmp::Eq for intern_key {
164 fn eq(&self, other: &intern_key) -> bool {
166 *self.sty == *other.sty
169 fn ne(&self, other: &intern_key) -> bool {
174 impl TotalEq for intern_key {}
176 impl<W:Writer> Hash<W> for intern_key {
177 fn hash(&self, s: &mut W) {
178 unsafe { (*self.sty).hash(s) }
182 pub enum ast_ty_to_ty_cache_entry {
183 atttce_unresolved, /* not resolved yet */
184 atttce_resolved(t) /* resolved to a type, irrespective of region */
187 #[deriving(Clone, Eq, Decodable, Encodable)]
188 pub struct ItemVariances {
189 pub self_param: Option<Variance>,
190 pub type_params: OwnedSlice<Variance>,
191 pub region_params: OwnedSlice<Variance>
194 #[deriving(Clone, Eq, Decodable, Encodable, Show)]
196 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
197 Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
198 Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
199 Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
203 pub enum AutoAdjustment {
204 AutoAddEnv(ty::TraitStore),
205 AutoDerefRef(AutoDerefRef),
206 AutoObject(ty::TraitStore,
208 ast::DefId, /* Trait ID */
209 ty::substs /* Trait substitutions */)
212 #[deriving(Clone, Decodable, Encodable)]
213 pub struct AutoDerefRef {
214 pub autoderefs: uint,
215 pub autoref: Option<AutoRef>
218 #[deriving(Clone, Decodable, Encodable, Eq, Show)]
220 /// Convert from T to &T
221 AutoPtr(Region, ast::Mutability),
223 /// Convert from ~[]/&[] to &[] (or str)
224 AutoBorrowVec(Region, ast::Mutability),
226 /// Convert from ~[]/&[] to &&[] (or str)
227 AutoBorrowVecRef(Region, ast::Mutability),
229 /// Convert from T to *T
230 AutoUnsafe(ast::Mutability),
232 /// Convert from Box<Trait>/&Trait to &Trait
233 AutoBorrowObj(Region, ast::Mutability),
236 /// The data structure to keep track of all the information that typechecker
237 /// generates so that so that it can be reused and doesn't have to be redone
240 // Specifically use a speedy hash algorithm for this hash map, it's used
242 pub interner: RefCell<FnvHashMap<intern_key, Box<t_box_>>>,
243 pub next_id: Cell<uint>,
245 pub def_map: resolve::DefMap,
247 pub named_region_map: resolve_lifetime::NamedRegionMap,
249 pub region_maps: middle::region::RegionMaps,
251 // Stores the types for various nodes in the AST. Note that this table
252 // is not guaranteed to be populated until after typeck. See
253 // typeck::check::fn_ctxt for details.
254 pub node_types: node_type_table,
256 // Stores the type parameters which were substituted to obtain the type
257 // of this node. This only applies to nodes that refer to entities
258 // param<eterized by type parameters, such as generic fns, types, or
260 pub item_substs: RefCell<NodeMap<ItemSubsts>>,
262 // Maps from a method to the method "descriptor"
263 pub methods: RefCell<DefIdMap<Rc<Method>>>,
265 // Maps from a trait def-id to a list of the def-ids of its methods
266 pub trait_method_def_ids: RefCell<DefIdMap<Rc<Vec<DefId>>>>,
268 // A cache for the trait_methods() routine
269 pub trait_methods_cache: RefCell<DefIdMap<Rc<Vec<Rc<Method>>>>>,
271 pub impl_trait_cache: RefCell<DefIdMap<Option<Rc<ty::TraitRef>>>>,
273 pub trait_refs: RefCell<NodeMap<Rc<TraitRef>>>,
274 pub trait_defs: RefCell<DefIdMap<Rc<TraitDef>>>,
276 pub map: ast_map::Map,
277 pub intrinsic_defs: RefCell<DefIdMap<t>>,
278 pub freevars: RefCell<freevars::freevar_map>,
279 pub tcache: type_cache,
280 pub rcache: creader_cache,
281 pub short_names_cache: RefCell<HashMap<t, StrBuf>>,
282 pub needs_unwind_cleanup_cache: RefCell<HashMap<t, bool>>,
283 pub tc_cache: RefCell<HashMap<uint, TypeContents>>,
284 pub ast_ty_to_ty_cache: RefCell<NodeMap<ast_ty_to_ty_cache_entry>>,
285 pub enum_var_cache: RefCell<DefIdMap<Rc<Vec<Rc<VariantInfo>>>>>,
286 pub ty_param_defs: RefCell<NodeMap<TypeParameterDef>>,
287 pub adjustments: RefCell<NodeMap<AutoAdjustment>>,
288 pub normalized_cache: RefCell<HashMap<t, t>>,
289 pub lang_items: middle::lang_items::LanguageItems,
290 // A mapping of fake provided method def_ids to the default implementation
291 pub provided_method_sources: RefCell<DefIdMap<ast::DefId>>,
292 pub supertraits: RefCell<DefIdMap<Rc<Vec<Rc<TraitRef>>>>>,
293 pub superstructs: RefCell<DefIdMap<Option<ast::DefId>>>,
294 pub struct_fields: RefCell<DefIdMap<Rc<Vec<field_ty>>>>,
296 // Maps from def-id of a type or region parameter to its
297 // (inferred) variance.
298 pub item_variance_map: RefCell<DefIdMap<Rc<ItemVariances>>>,
300 // A mapping from the def ID of an enum or struct type to the def ID
301 // of the method that implements its destructor. If the type is not
302 // present in this map, it does not have a destructor. This map is
303 // populated during the coherence phase of typechecking.
304 pub destructor_for_type: RefCell<DefIdMap<ast::DefId>>,
306 // A method will be in this list if and only if it is a destructor.
307 pub destructors: RefCell<DefIdSet>,
309 // Maps a trait onto a list of impls of that trait.
310 pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
312 // Maps a DefId of a type to a list of its inherent impls.
313 // Contains implementations of methods that are inherent to a type.
314 // Methods in these implementations don't need to be exported.
315 pub inherent_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
317 // Maps a DefId of an impl to a list of its methods.
318 // Note that this contains all of the impls that we know about,
319 // including ones in other crates. It's not clear that this is the best
321 pub impl_methods: RefCell<DefIdMap<Vec<ast::DefId>>>,
323 // Set of used unsafe nodes (functions or blocks). Unsafe nodes not
324 // present in this set can be warned about.
325 pub used_unsafe: RefCell<NodeSet>,
327 // Set of nodes which mark locals as mutable which end up getting used at
328 // some point. Local variable definitions not in this set can be warned
330 pub used_mut_nodes: RefCell<NodeSet>,
332 // vtable resolution information for impl declarations
333 pub impl_vtables: typeck::impl_vtable_map,
335 // The set of external nominal types whose implementations have been read.
336 // This is used for lazy resolution of methods.
337 pub populated_external_types: RefCell<DefIdSet>,
339 // The set of external traits whose implementations have been read. This
340 // is used for lazy resolution of traits.
341 pub populated_external_traits: RefCell<DefIdSet>,
344 pub upvar_borrow_map: RefCell<UpvarBorrowMap>,
346 // These two caches are used by const_eval when decoding external statics
347 // and variants that are found.
348 pub extern_const_statics: RefCell<DefIdMap<Option<@ast::Expr>>>,
349 pub extern_const_variants: RefCell<DefIdMap<Option<@ast::Expr>>>,
351 pub method_map: typeck::MethodMap,
352 pub vtable_map: typeck::vtable_map,
354 pub dependency_formats: RefCell<dependency_format::Dependencies>,
365 // a meta-pub flag: subst may be required if the type has parameters, a self
366 // type, or references bound regions
367 needs_subst = 1 | 2 | 8
370 pub type t_box = &'static t_box_;
378 // To reduce refcounting cost, we're representing types as unsafe pointers
379 // throughout the compiler. These are simply casted t_box values. Use ty::get
380 // to cast them back to a box. (Without the cast, compiler performance suffers
381 // ~15%.) This does mean that a t value relies on the ctxt to keep its box
382 // alive, and using ty::get is unsafe when the ctxt is no longer alive.
385 #[allow(raw_pointer_deriving)]
386 #[deriving(Clone, Eq, TotalEq, Hash)]
387 pub struct t { inner: *t_opaque }
389 impl fmt::Show for t {
390 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
395 pub fn get(t: t) -> t_box {
397 let t2: t_box = mem::transmute(t);
402 pub fn tbox_has_flag(tb: t_box, flag: tbox_flag) -> bool {
403 (tb.flags & (flag as uint)) != 0u
405 pub fn type_has_params(t: t) -> bool {
406 tbox_has_flag(get(t), has_params)
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)
412 pub fn type_id(t: t) -> uint { get(t).id }
414 #[deriving(Clone, Eq, TotalEq, Hash)]
415 pub struct BareFnTy {
416 pub fn_style: ast::FnStyle,
421 #[deriving(Clone, Eq, TotalEq, Hash)]
422 pub struct ClosureTy {
423 pub fn_style: ast::FnStyle,
424 pub onceness: ast::Onceness,
425 pub store: TraitStore,
426 pub bounds: BuiltinBounds,
431 * Signature of a function type, which I have arbitrarily
432 * decided to use to refer to the input/output types.
434 * - `binder_id` is the node id where this fn type appeared;
435 * it is used to identify all the bound regions appearing
436 * in the input/output types that are bound by this fn type
437 * (vs some enclosing or enclosed fn type)
438 * - `inputs` is the list of arguments and their modes.
439 * - `output` is the return type.
440 * - `variadic` indicates whether this is a varidic function. (only true for foreign fns)
442 #[deriving(Clone, Eq, TotalEq, Hash)]
444 pub binder_id: ast::NodeId,
450 #[deriving(Clone, Eq, TotalEq, Hash)]
451 pub struct param_ty {
456 /// Representation of regions:
457 #[deriving(Clone, Eq, TotalEq, Hash, Encodable, Decodable, Show)]
459 // Region bound in a type or fn declaration which will be
460 // substituted 'early' -- that is, at the same time when type
461 // parameters are substituted.
462 ReEarlyBound(/* param id */ ast::NodeId, /*index*/ uint, ast::Name),
464 // Region bound in a function scope, which will be substituted when the
465 // function is called. The first argument must be the `binder_id` of
466 // some enclosing function signature.
467 ReLateBound(/* binder_id */ ast::NodeId, BoundRegion),
469 /// When checking a function body, the types of all arguments and so forth
470 /// that refer to bound region parameters are modified to refer to free
471 /// region parameters.
474 /// A concrete region naming some expression within the current function.
477 /// Static data that has an "infinite" lifetime. Top in the region lattice.
480 /// A region variable. Should not exist after typeck.
481 ReInfer(InferRegion),
483 /// Empty lifetime is for data that is never accessed.
484 /// Bottom in the region lattice. We treat ReEmpty somewhat
485 /// specially; at least right now, we do not generate instances of
486 /// it during the GLB computations, but rather
487 /// generate an error instead. This is to improve error messages.
488 /// The only way to get an instance of ReEmpty is to have a region
489 /// variable with no constraints.
494 * Upvars do not get their own node-id. Instead, we use the pair of
495 * the original var id (that is, the root variable that is referenced
496 * by the upvar) and the id of the closure expression.
498 #[deriving(Clone, Eq, TotalEq, Hash)]
500 pub var_id: ast::NodeId,
501 pub closure_expr_id: ast::NodeId,
504 #[deriving(Clone, Eq, TotalEq, Hash, Show)]
505 pub enum BorrowKind {
506 /// Data must be immutable and is aliasable.
509 /// Data must be immutable but not aliasable. This kind of borrow
510 /// cannot currently be expressed by the user and is used only in
511 /// implicit closure bindings. It is needed when you the closure
512 /// is borrowing or mutating a mutable referent, e.g.:
514 /// let x: &mut int = ...;
515 /// let y = || *x += 5;
517 /// If we were to try to translate this closure into a more explicit
518 /// form, we'd encounter an error with the code as written:
520 /// struct Env { x: & &mut int }
521 /// let x: &mut int = ...;
522 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
523 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
525 /// This is then illegal because you cannot mutate a `&mut` found
526 /// in an aliasable location. To solve, you'd have to translate with
527 /// an `&mut` borrow:
529 /// struct Env { x: & &mut int }
530 /// let x: &mut int = ...;
531 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
532 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
534 /// Now the assignment to `**env.x` is legal, but creating a
535 /// mutable pointer to `x` is not because `x` is not mutable. We
536 /// could fix this by declaring `x` as `let mut x`. This is ok in
537 /// user code, if awkward, but extra weird for closures, since the
538 /// borrow is hidden.
540 /// So we introduce a "unique imm" borrow -- the referent is
541 /// immutable, but not aliasable. This solves the problem. For
542 /// simplicity, we don't give users the way to express this
543 /// borrow, it's just used when translating closures.
546 /// Data is mutable and not aliasable.
551 * Information describing the borrowing of an upvar. This is computed
552 * during `typeck`, specifically by `regionck`. The general idea is
553 * that the compiler analyses treat closures like:
555 * let closure: &'e fn() = || {
556 * x = 1; // upvar x is assigned to
557 * use(y); // upvar y is read
558 * foo(&z); // upvar z is borrowed immutably
561 * as if they were "desugared" to something loosely like:
563 * struct Vars<'x,'y,'z> { x: &'x mut int,
566 * let closure: &'e fn() = {
572 * let env: &'e mut Vars<'x,'y,'z> = &mut Vars { x: &'x mut x,
578 * This is basically what happens at runtime. The closure is basically
579 * an existentially quantified version of the `(env, f)` pair.
581 * This data structure indicates the region and mutability of a single
582 * one of the `x...z` borrows.
584 * It may not be obvious why each borrowed variable gets its own
585 * lifetime (in the desugared version of the example, these are indicated
586 * by the lifetime parameters `'x`, `'y`, and `'z` in the `Vars` definition).
587 * Each such lifetime must encompass the lifetime `'e` of the closure itself,
588 * but need not be identical to it. The reason that this makes sense:
590 * - Callers are only permitted to invoke the closure, and hence to
591 * use the pointers, within the lifetime `'e`, so clearly `'e` must
592 * be a sublifetime of `'x...'z`.
593 * - The closure creator knows which upvars were borrowed by the closure
594 * and thus `x...z` will be reserved for `'x...'z` respectively.
595 * - Through mutation, the borrowed upvars can actually escape
596 * the closure, so sometimes it is necessary for them to be larger
597 * than the closure lifetime itself.
599 #[deriving(Eq, Clone)]
600 pub struct UpvarBorrow {
601 pub kind: BorrowKind,
602 pub region: ty::Region,
605 pub type UpvarBorrowMap = HashMap<UpvarId, UpvarBorrow>;
608 pub fn is_bound(&self) -> bool {
610 &ty::ReEarlyBound(..) => true,
611 &ty::ReLateBound(..) => true,
617 #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd, Hash, Encodable, Decodable, Show)]
618 pub struct FreeRegion {
619 pub scope_id: NodeId,
620 pub bound_region: BoundRegion
623 #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd, Hash, Encodable, Decodable, Show)]
624 pub enum BoundRegion {
625 /// An anonymous region parameter for a given fn (&T)
628 /// Named region parameters for functions (a in &'a T)
630 /// The def-id is needed to distinguish free regions in
631 /// the event of shadowing.
632 BrNamed(ast::DefId, ast::Name),
634 /// Fresh bound identifiers created during GLB computations.
639 * Represents the values to use when substituting lifetime parameters.
640 * If the value is `ErasedRegions`, then this subst is occurring during
641 * trans, and all region parameters will be replaced with `ty::ReStatic`. */
642 #[deriving(Clone, Eq, TotalEq, Hash)]
643 pub enum RegionSubsts {
645 NonerasedRegions(OwnedSlice<ty::Region>)
649 * The type substs represents the kinds of things that can be substituted to
650 * convert a polytype into a monotype. Note however that substituting bound
651 * regions other than `self` is done through a different mechanism:
653 * - `tps` represents the type parameters in scope. They are indexed
654 * according to the order in which they were declared.
656 * - `self_r` indicates the region parameter `self` that is present on nominal
657 * types (enums, structs) declared as having a region parameter. `self_r`
658 * should always be none for types that are not region-parameterized and
659 * Some(_) for types that are. The only bound region parameter that should
660 * appear within a region-parameterized type is `self`.
662 * - `self_ty` is the type to which `self` should be remapped, if any. The
663 * `self` type is rather funny in that it can only appear on traits and is
664 * always substituted away to the implementing type for a trait. */
665 #[deriving(Clone, Eq, TotalEq, Hash)]
667 pub self_ty: Option<ty::t>,
669 pub regions: RegionSubsts,
677 macro_rules! def_prim_ty(
678 ($name:ident, $sty:expr, $id:expr) => (
679 pub static $name: t_box_ = t_box_ {
687 def_prim_ty!(TY_NIL, super::ty_nil, 0)
688 def_prim_ty!(TY_BOOL, super::ty_bool, 1)
689 def_prim_ty!(TY_CHAR, super::ty_char, 2)
690 def_prim_ty!(TY_INT, super::ty_int(ast::TyI), 3)
691 def_prim_ty!(TY_I8, super::ty_int(ast::TyI8), 4)
692 def_prim_ty!(TY_I16, super::ty_int(ast::TyI16), 5)
693 def_prim_ty!(TY_I32, super::ty_int(ast::TyI32), 6)
694 def_prim_ty!(TY_I64, super::ty_int(ast::TyI64), 7)
695 def_prim_ty!(TY_UINT, super::ty_uint(ast::TyU), 8)
696 def_prim_ty!(TY_U8, super::ty_uint(ast::TyU8), 9)
697 def_prim_ty!(TY_U16, super::ty_uint(ast::TyU16), 10)
698 def_prim_ty!(TY_U32, super::ty_uint(ast::TyU32), 11)
699 def_prim_ty!(TY_U64, super::ty_uint(ast::TyU64), 12)
700 def_prim_ty!(TY_F32, super::ty_float(ast::TyF32), 14)
701 def_prim_ty!(TY_F64, super::ty_float(ast::TyF64), 15)
702 def_prim_ty!(TY_F128, super::ty_float(ast::TyF128), 16)
704 pub static TY_BOT: t_box_ = t_box_ {
707 flags: super::has_ty_bot as uint,
710 pub static TY_ERR: t_box_ = t_box_ {
713 flags: super::has_ty_err as uint,
716 pub static LAST_PRIMITIVE_ID: uint = 18;
719 // NB: If you change this, you'll probably want to change the corresponding
720 // AST structure in libsyntax/ast.rs as well.
721 #[deriving(Clone, Eq, TotalEq, Hash)]
728 ty_uint(ast::UintTy),
729 ty_float(ast::FloatTy),
730 ty_enum(DefId, substs),
734 ty_vec(mt, Option<uint>), // Second field is length.
737 ty_bare_fn(BareFnTy),
738 ty_closure(Box<ClosureTy>),
739 ty_trait(Box<TyTrait>),
740 ty_struct(DefId, substs),
743 ty_param(param_ty), // type parameter
744 ty_self(DefId), /* special, implicit `self` type parameter;
745 * def_id is the id of the trait */
747 ty_infer(InferTy), // something used only during inference/typeck
748 ty_err, // Also only used during inference/typeck, to represent
749 // the type of an erroneous expression (helps cut down
750 // on non-useful type error messages)
753 #[deriving(Clone, Eq, TotalEq, Hash)]
757 pub store: TraitStore,
758 pub bounds: BuiltinBounds
761 #[deriving(Eq, TotalEq, Hash)]
762 pub struct TraitRef {
767 #[deriving(Clone, Eq)]
768 pub enum IntVarValue {
770 UintType(ast::UintTy),
773 #[deriving(Clone, Show)]
774 pub enum terr_vstore_kind {
781 #[deriving(Clone, Show)]
782 pub struct expected_found<T> {
787 // Data structures used in type unification
788 #[deriving(Clone, Show)]
791 terr_fn_style_mismatch(expected_found<FnStyle>),
792 terr_onceness_mismatch(expected_found<Onceness>),
793 terr_abi_mismatch(expected_found<abi::Abi>),
795 terr_sigil_mismatch(expected_found<TraitStore>),
800 terr_tuple_size(expected_found<uint>),
801 terr_ty_param_size(expected_found<uint>),
802 terr_record_size(expected_found<uint>),
803 terr_record_mutability,
804 terr_record_fields(expected_found<Ident>),
806 terr_regions_does_not_outlive(Region, Region),
807 terr_regions_not_same(Region, Region),
808 terr_regions_no_overlap(Region, Region),
809 terr_regions_insufficiently_polymorphic(BoundRegion, Region),
810 terr_regions_overly_polymorphic(BoundRegion, Region),
811 terr_trait_stores_differ(terr_vstore_kind, expected_found<TraitStore>),
812 terr_sorts(expected_found<t>),
813 terr_integer_as_char,
814 terr_int_mismatch(expected_found<IntVarValue>),
815 terr_float_mismatch(expected_found<ast::FloatTy>),
816 terr_traits(expected_found<ast::DefId>),
817 terr_builtin_bounds(expected_found<BuiltinBounds>),
818 terr_variadic_mismatch(expected_found<bool>)
821 #[deriving(Eq, TotalEq, Hash)]
822 pub struct ParamBounds {
823 pub builtin_bounds: BuiltinBounds,
824 pub trait_bounds: Vec<Rc<TraitRef>>
827 pub type BuiltinBounds = EnumSet<BuiltinBound>;
829 #[deriving(Clone, Encodable, Eq, TotalEq, Decodable, Hash, Show)]
831 pub enum BuiltinBound {
839 pub fn EmptyBuiltinBounds() -> BuiltinBounds {
843 pub fn AllBuiltinBounds() -> BuiltinBounds {
844 let mut set = EnumSet::empty();
845 set.add(BoundStatic);
852 impl CLike for BuiltinBound {
853 fn to_uint(&self) -> uint {
856 fn from_uint(v: uint) -> BuiltinBound {
857 unsafe { mem::transmute(v) }
861 #[deriving(Clone, Eq, TotalEq, Hash)]
862 pub struct TyVid(pub uint);
864 #[deriving(Clone, Eq, TotalEq, Hash)]
865 pub struct IntVid(pub uint);
867 #[deriving(Clone, Eq, TotalEq, Hash)]
868 pub struct FloatVid(pub uint);
870 #[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
871 pub struct RegionVid {
875 #[deriving(Clone, Eq, TotalEq, Hash)]
882 #[deriving(Clone, Encodable, Decodable, TotalEq, Hash, Show)]
883 pub enum InferRegion {
885 ReSkolemized(uint, BoundRegion)
888 impl cmp::Eq for InferRegion {
889 fn eq(&self, other: &InferRegion) -> bool {
890 match ((*self), *other) {
891 (ReVar(rva), ReVar(rvb)) => {
894 (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
900 fn ne(&self, other: &InferRegion) -> bool {
901 !((*self) == (*other))
906 fn to_uint(&self) -> uint;
910 fn to_uint(&self) -> uint { let TyVid(v) = *self; v }
913 impl fmt::Show for TyVid {
914 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
915 write!(f, "<generic \\#{}>", self.to_uint())
919 impl Vid for IntVid {
920 fn to_uint(&self) -> uint { let IntVid(v) = *self; v }
923 impl fmt::Show for IntVid {
924 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
925 write!(f, "<generic integer \\#{}>", self.to_uint())
929 impl Vid for FloatVid {
930 fn to_uint(&self) -> uint { let FloatVid(v) = *self; v }
933 impl fmt::Show for FloatVid {
934 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
935 write!(f, "<generic float \\#{}>", self.to_uint())
939 impl Vid for RegionVid {
940 fn to_uint(&self) -> uint { self.id }
943 impl fmt::Show for RegionVid {
944 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
949 impl fmt::Show for FnSig {
950 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
951 // grr, without tcx not much we can do.
956 impl fmt::Show for InferTy {
957 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
959 TyVar(ref v) => v.fmt(f),
960 IntVar(ref v) => v.fmt(f),
961 FloatVar(ref v) => v.fmt(f),
966 impl fmt::Show for IntVarValue {
967 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
969 IntType(ref v) => v.fmt(f),
970 UintType(ref v) => v.fmt(f),
976 pub struct TypeParameterDef {
977 pub ident: ast::Ident,
978 pub def_id: ast::DefId,
979 pub bounds: Rc<ParamBounds>,
980 pub default: Option<ty::t>
983 #[deriving(Encodable, Decodable, Clone)]
984 pub struct RegionParameterDef {
986 pub def_id: ast::DefId,
989 /// Information about the type/lifetime parameters associated with an item.
990 /// Analogous to ast::Generics.
992 pub struct Generics {
993 /// List of type parameters declared on the item.
994 pub type_param_defs: Rc<Vec<TypeParameterDef>>,
996 /// List of region parameters declared on the item.
997 /// For a fn or method, only includes *early-bound* lifetimes.
998 pub region_param_defs: Rc<Vec<RegionParameterDef>>,
1002 pub fn has_type_params(&self) -> bool {
1003 !self.type_param_defs.is_empty()
1005 pub fn type_param_defs<'a>(&'a self) -> &'a [TypeParameterDef] {
1006 self.type_param_defs.as_slice()
1008 pub fn region_param_defs<'a>(&'a self) -> &'a [RegionParameterDef] {
1009 self.region_param_defs.as_slice()
1013 /// When type checking, we use the `ParameterEnvironment` to track
1014 /// details about the type/lifetime parameters that are in scope.
1015 /// It primarily stores the bounds information.
1017 /// Note: This information might seem to be redundant with the data in
1018 /// `tcx.ty_param_defs`, but it is not. That table contains the
1019 /// parameter definitions from an "outside" perspective, but this
1020 /// struct will contain the bounds for a parameter as seen from inside
1021 /// the function body. Currently the only real distinction is that
1022 /// bound lifetime parameters are replaced with free ones, but in the
1023 /// future I hope to refine the representation of types so as to make
1024 /// more distinctions clearer.
1025 pub struct ParameterEnvironment {
1026 /// A substitution that can be applied to move from
1027 /// the "outer" view of a type or method to the "inner" view.
1028 /// In general, this means converting from bound parameters to
1029 /// free parameters. Since we currently represent bound/free type
1030 /// parameters in the same way, this only has an affect on regions.
1031 pub free_substs: ty::substs,
1033 /// Bound on the Self parameter
1034 pub self_param_bound: Option<Rc<TraitRef>>,
1036 /// Bounds on each numbered type parameter
1037 pub type_param_bounds: Vec<ParamBounds>,
1042 /// - `bounds`: The list of bounds for each type parameter. The length of the
1043 /// list also tells you how many type parameters there are.
1045 /// - `rp`: true if the type is region-parameterized. Types can have at
1046 /// most one region parameter, always called `&self`.
1048 /// - `ty`: the base type. May have reference to the (unsubstituted) bound
1049 /// region `&self` or to (unsubstituted) ty_param types
1051 pub struct ty_param_bounds_and_ty {
1052 pub generics: Generics,
1056 /// As `ty_param_bounds_and_ty` but for a trait ref.
1057 pub struct TraitDef {
1058 pub generics: Generics,
1059 pub bounds: BuiltinBounds,
1060 pub trait_ref: Rc<ty::TraitRef>,
1063 /// Records the substitutions used to translate the polytype for an
1064 /// item into the monotype of an item reference.
1066 pub struct ItemSubsts {
1067 pub substs: ty::substs,
1070 pub struct ty_param_substs_and_ty {
1071 pub substs: ty::substs,
1075 pub type type_cache = RefCell<DefIdMap<ty_param_bounds_and_ty>>;
1077 pub type node_type_table = RefCell<HashMap<uint,t>>;
1079 pub fn mk_ctxt(s: Session,
1080 dm: resolve::DefMap,
1081 named_region_map: resolve_lifetime::NamedRegionMap,
1083 freevars: freevars::freevar_map,
1084 region_maps: middle::region::RegionMaps,
1085 lang_items: middle::lang_items::LanguageItems)
1088 named_region_map: named_region_map,
1089 item_variance_map: RefCell::new(DefIdMap::new()),
1090 interner: RefCell::new(FnvHashMap::new()),
1091 next_id: Cell::new(primitives::LAST_PRIMITIVE_ID),
1094 region_maps: region_maps,
1095 node_types: RefCell::new(HashMap::new()),
1096 item_substs: RefCell::new(NodeMap::new()),
1097 trait_refs: RefCell::new(NodeMap::new()),
1098 trait_defs: RefCell::new(DefIdMap::new()),
1100 intrinsic_defs: RefCell::new(DefIdMap::new()),
1101 freevars: RefCell::new(freevars),
1102 tcache: RefCell::new(DefIdMap::new()),
1103 rcache: RefCell::new(HashMap::new()),
1104 short_names_cache: RefCell::new(HashMap::new()),
1105 needs_unwind_cleanup_cache: RefCell::new(HashMap::new()),
1106 tc_cache: RefCell::new(HashMap::new()),
1107 ast_ty_to_ty_cache: RefCell::new(NodeMap::new()),
1108 enum_var_cache: RefCell::new(DefIdMap::new()),
1109 methods: RefCell::new(DefIdMap::new()),
1110 trait_method_def_ids: RefCell::new(DefIdMap::new()),
1111 trait_methods_cache: RefCell::new(DefIdMap::new()),
1112 impl_trait_cache: RefCell::new(DefIdMap::new()),
1113 ty_param_defs: RefCell::new(NodeMap::new()),
1114 adjustments: RefCell::new(NodeMap::new()),
1115 normalized_cache: RefCell::new(HashMap::new()),
1116 lang_items: lang_items,
1117 provided_method_sources: RefCell::new(DefIdMap::new()),
1118 supertraits: RefCell::new(DefIdMap::new()),
1119 superstructs: RefCell::new(DefIdMap::new()),
1120 struct_fields: RefCell::new(DefIdMap::new()),
1121 destructor_for_type: RefCell::new(DefIdMap::new()),
1122 destructors: RefCell::new(DefIdSet::new()),
1123 trait_impls: RefCell::new(DefIdMap::new()),
1124 inherent_impls: RefCell::new(DefIdMap::new()),
1125 impl_methods: RefCell::new(DefIdMap::new()),
1126 used_unsafe: RefCell::new(NodeSet::new()),
1127 used_mut_nodes: RefCell::new(NodeSet::new()),
1128 impl_vtables: RefCell::new(DefIdMap::new()),
1129 populated_external_types: RefCell::new(DefIdSet::new()),
1130 populated_external_traits: RefCell::new(DefIdSet::new()),
1131 upvar_borrow_map: RefCell::new(HashMap::new()),
1132 extern_const_statics: RefCell::new(DefIdMap::new()),
1133 extern_const_variants: RefCell::new(DefIdMap::new()),
1134 method_map: RefCell::new(FnvHashMap::new()),
1135 vtable_map: RefCell::new(FnvHashMap::new()),
1136 dependency_formats: RefCell::new(HashMap::new()),
1140 // Type constructors
1142 // Interns a type/name combination, stores the resulting box in cx.interner,
1143 // and returns the box as cast to an unsafe ptr (see comments for t above).
1144 pub fn mk_t(cx: &ctxt, st: sty) -> t {
1145 // Check for primitive types.
1147 ty_nil => return mk_nil(),
1148 ty_err => return mk_err(),
1149 ty_bool => return mk_bool(),
1150 ty_int(i) => return mk_mach_int(i),
1151 ty_uint(u) => return mk_mach_uint(u),
1152 ty_float(f) => return mk_mach_float(f),
1153 ty_char => return mk_char(),
1154 ty_bot => return mk_bot(),
1158 let key = intern_key { sty: &st };
1160 match cx.interner.borrow().find(&key) {
1161 Some(t) => unsafe { return mem::transmute(&t.sty); },
1166 fn rflags(r: Region) -> uint {
1167 (has_regions as uint) | {
1169 ty::ReInfer(_) => needs_infer as uint,
1174 fn sflags(substs: &substs) -> uint {
1176 for tt in substs.tps.iter() { f |= get(*tt).flags; }
1177 match substs.regions {
1179 NonerasedRegions(ref regions) => {
1180 for r in regions.iter() {
1188 &ty_nil | &ty_bool | &ty_char | &ty_int(_) | &ty_float(_) | &ty_uint(_) |
1190 // You might think that we could just return ty_err for
1191 // any type containing ty_err as a component, and get
1192 // rid of the has_ty_err flag -- likewise for ty_bot (with
1193 // the exception of function types that return bot).
1194 // But doing so caused sporadic memory corruption, and
1195 // neither I (tjc) nor nmatsakis could figure out why,
1196 // so we're doing it this way.
1197 &ty_bot => flags |= has_ty_bot as uint,
1198 &ty_err => flags |= has_ty_err as uint,
1199 &ty_param(_) => flags |= has_params as uint,
1200 &ty_infer(_) => flags |= needs_infer as uint,
1201 &ty_self(_) => flags |= has_self as uint,
1202 &ty_enum(_, ref substs) | &ty_struct(_, ref substs) => {
1203 flags |= sflags(substs);
1205 &ty_trait(box ty::TyTrait { ref substs, store, .. }) => {
1206 flags |= sflags(substs);
1208 RegionTraitStore(r, _) => {
1214 &ty_box(tt) | &ty_uniq(tt) => {
1215 flags |= get(tt).flags
1217 &ty_ptr(ref m) | &ty_vec(ref m, _) => {
1218 flags |= get(m.ty).flags;
1220 &ty_rptr(r, ref m) => {
1222 flags |= get(m.ty).flags;
1224 &ty_tup(ref ts) => for tt in ts.iter() { flags |= get(*tt).flags; },
1225 &ty_bare_fn(ref f) => {
1226 for a in f.sig.inputs.iter() { flags |= get(*a).flags; }
1227 flags |= get(f.sig.output).flags;
1228 // T -> _|_ is *not* _|_ !
1229 flags &= !(has_ty_bot as uint);
1231 &ty_closure(ref f) => {
1233 RegionTraitStore(r, _) => {
1238 for a in f.sig.inputs.iter() { flags |= get(*a).flags; }
1239 flags |= get(f.sig.output).flags;
1240 // T -> _|_ is *not* _|_ !
1241 flags &= !(has_ty_bot as uint);
1245 let t = box t_box_ {
1247 id: cx.next_id.get(),
1251 let sty_ptr = &t.sty as *sty;
1253 let key = intern_key {
1257 cx.interner.borrow_mut().insert(key, t);
1259 cx.next_id.set(cx.next_id.get() + 1);
1262 mem::transmute::<*sty, t>(sty_ptr)
1267 pub fn mk_prim_t(primitive: &'static t_box_) -> t {
1269 mem::transmute::<&'static t_box_, t>(primitive)
1274 pub fn mk_nil() -> t { mk_prim_t(&primitives::TY_NIL) }
1277 pub fn mk_err() -> t { mk_prim_t(&primitives::TY_ERR) }
1280 pub fn mk_bot() -> t { mk_prim_t(&primitives::TY_BOT) }
1283 pub fn mk_bool() -> t { mk_prim_t(&primitives::TY_BOOL) }
1286 pub fn mk_int() -> t { mk_prim_t(&primitives::TY_INT) }
1289 pub fn mk_i8() -> t { mk_prim_t(&primitives::TY_I8) }
1292 pub fn mk_i16() -> t { mk_prim_t(&primitives::TY_I16) }
1295 pub fn mk_i32() -> t { mk_prim_t(&primitives::TY_I32) }
1298 pub fn mk_i64() -> t { mk_prim_t(&primitives::TY_I64) }
1301 pub fn mk_f32() -> t { mk_prim_t(&primitives::TY_F32) }
1304 pub fn mk_f64() -> t { mk_prim_t(&primitives::TY_F64) }
1307 pub fn mk_f128() -> t { mk_prim_t(&primitives::TY_F128) }
1310 pub fn mk_uint() -> t { mk_prim_t(&primitives::TY_UINT) }
1313 pub fn mk_u8() -> t { mk_prim_t(&primitives::TY_U8) }
1316 pub fn mk_u16() -> t { mk_prim_t(&primitives::TY_U16) }
1319 pub fn mk_u32() -> t { mk_prim_t(&primitives::TY_U32) }
1322 pub fn mk_u64() -> t { mk_prim_t(&primitives::TY_U64) }
1324 pub fn mk_mach_int(tm: ast::IntTy) -> t {
1326 ast::TyI => mk_int(),
1327 ast::TyI8 => mk_i8(),
1328 ast::TyI16 => mk_i16(),
1329 ast::TyI32 => mk_i32(),
1330 ast::TyI64 => mk_i64(),
1334 pub fn mk_mach_uint(tm: ast::UintTy) -> t {
1336 ast::TyU => mk_uint(),
1337 ast::TyU8 => mk_u8(),
1338 ast::TyU16 => mk_u16(),
1339 ast::TyU32 => mk_u32(),
1340 ast::TyU64 => mk_u64(),
1344 pub fn mk_mach_float(tm: ast::FloatTy) -> t {
1346 ast::TyF32 => mk_f32(),
1347 ast::TyF64 => mk_f64(),
1348 ast::TyF128 => mk_f128()
1353 pub fn mk_char() -> t { mk_prim_t(&primitives::TY_CHAR) }
1355 pub fn mk_str(cx: &ctxt) -> t {
1359 pub fn mk_str_slice(cx: &ctxt, r: Region, m: ast::Mutability) -> t {
1362 ty: mk_t(cx, ty_str),
1367 pub fn mk_enum(cx: &ctxt, did: ast::DefId, substs: substs) -> t {
1368 // take a copy of substs so that we own the vectors inside
1369 mk_t(cx, ty_enum(did, substs))
1372 pub fn mk_box(cx: &ctxt, ty: t) -> t { mk_t(cx, ty_box(ty)) }
1374 pub fn mk_uniq(cx: &ctxt, ty: t) -> t { mk_t(cx, ty_uniq(ty)) }
1376 pub fn mk_ptr(cx: &ctxt, tm: mt) -> t { mk_t(cx, ty_ptr(tm)) }
1378 pub fn mk_rptr(cx: &ctxt, r: Region, tm: mt) -> t { mk_t(cx, ty_rptr(r, tm)) }
1380 pub fn mk_mut_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1381 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutMutable})
1383 pub fn mk_imm_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1384 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutImmutable})
1387 pub fn mk_mut_ptr(cx: &ctxt, ty: t) -> t {
1388 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutMutable})
1391 pub fn mk_imm_ptr(cx: &ctxt, ty: t) -> t {
1392 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutImmutable})
1395 pub fn mk_nil_ptr(cx: &ctxt) -> t {
1396 mk_ptr(cx, mt {ty: mk_nil(), mutbl: ast::MutImmutable})
1399 pub fn mk_vec(cx: &ctxt, tm: mt, sz: Option<uint>) -> t {
1400 mk_t(cx, ty_vec(tm, sz))
1403 pub fn mk_slice(cx: &ctxt, r: Region, tm: mt) -> t {
1406 ty: mk_vec(cx, tm, None),
1411 pub fn mk_tup(cx: &ctxt, ts: Vec<t>) -> t { mk_t(cx, ty_tup(ts)) }
1413 pub fn mk_closure(cx: &ctxt, fty: ClosureTy) -> t {
1414 mk_t(cx, ty_closure(box fty))
1417 pub fn mk_bare_fn(cx: &ctxt, fty: BareFnTy) -> t {
1418 mk_t(cx, ty_bare_fn(fty))
1421 pub fn mk_ctor_fn(cx: &ctxt,
1422 binder_id: ast::NodeId,
1423 input_tys: &[ty::t],
1424 output: ty::t) -> t {
1425 let input_args = input_tys.iter().map(|t| *t).collect();
1428 fn_style: ast::NormalFn,
1431 binder_id: binder_id,
1440 pub fn mk_trait(cx: &ctxt,
1444 bounds: BuiltinBounds)
1446 // take a copy of substs so that we own the vectors inside
1447 let inner = box TyTrait {
1453 mk_t(cx, ty_trait(inner))
1456 pub fn mk_struct(cx: &ctxt, struct_id: ast::DefId, substs: substs) -> t {
1457 // take a copy of substs so that we own the vectors inside
1458 mk_t(cx, ty_struct(struct_id, substs))
1461 pub fn mk_var(cx: &ctxt, v: TyVid) -> t { mk_infer(cx, TyVar(v)) }
1463 pub fn mk_int_var(cx: &ctxt, v: IntVid) -> t { mk_infer(cx, IntVar(v)) }
1465 pub fn mk_float_var(cx: &ctxt, v: FloatVid) -> t { mk_infer(cx, FloatVar(v)) }
1467 pub fn mk_infer(cx: &ctxt, it: InferTy) -> t { mk_t(cx, ty_infer(it)) }
1469 pub fn mk_self(cx: &ctxt, did: ast::DefId) -> t { mk_t(cx, ty_self(did)) }
1471 pub fn mk_param(cx: &ctxt, n: uint, k: DefId) -> t {
1472 mk_t(cx, ty_param(param_ty { idx: n, def_id: k }))
1475 pub fn walk_ty(ty: t, f: |t|) {
1476 maybe_walk_ty(ty, |t| { f(t); true });
1479 pub fn maybe_walk_ty(ty: t, f: |t| -> bool) {
1484 ty_nil | ty_bot | ty_bool | ty_char | ty_int(_) | ty_uint(_) | ty_float(_) |
1485 ty_str | ty_self(_) |
1486 ty_infer(_) | ty_param(_) | ty_err => {}
1487 ty_box(ty) | ty_uniq(ty) => maybe_walk_ty(ty, f),
1488 ty_ptr(ref tm) | ty_rptr(_, ref tm) | ty_vec(ref tm, _) => {
1489 maybe_walk_ty(tm.ty, f);
1491 ty_enum(_, ref substs) | ty_struct(_, ref substs) |
1492 ty_trait(box TyTrait { ref substs, .. }) => {
1493 for subty in (*substs).tps.iter() { maybe_walk_ty(*subty, |x| f(x)); }
1495 ty_tup(ref ts) => { for tt in ts.iter() { maybe_walk_ty(*tt, |x| f(x)); } }
1496 ty_bare_fn(ref ft) => {
1497 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1498 maybe_walk_ty(ft.sig.output, f);
1500 ty_closure(ref ft) => {
1501 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1502 maybe_walk_ty(ft.sig.output, f);
1507 // Folds types from the bottom up.
1508 pub fn fold_ty(cx: &ctxt, t0: t, fldop: |t| -> t) -> t {
1509 let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
1513 pub fn walk_regions_and_ty(cx: &ctxt, ty: t, fldr: |r: Region|, fldt: |t: t|)
1515 ty_fold::RegionFolder::general(cx,
1517 |t| { fldt(t); t }).fold_ty(ty)
1521 pub fn empty() -> ItemSubsts {
1523 substs: substs::empty(),
1527 pub fn is_noop(&self) -> bool {
1528 ty::substs_is_noop(&self.substs)
1532 pub fn substs_is_noop(substs: &substs) -> bool {
1533 let regions_is_noop = match substs.regions {
1534 ErasedRegions => false, // may be used to canonicalize
1535 NonerasedRegions(ref regions) => regions.is_empty()
1538 substs.tps.len() == 0u &&
1540 substs.self_ty.is_none()
1543 pub fn substs_to_str(cx: &ctxt, substs: &substs) -> StrBuf {
1547 pub fn subst(cx: &ctxt,
1551 typ.subst(cx, substs)
1556 pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil }
1558 pub fn type_is_bot(ty: t) -> bool {
1559 (get(ty).flags & (has_ty_bot as uint)) != 0
1562 pub fn type_is_error(ty: t) -> bool {
1563 (get(ty).flags & (has_ty_err as uint)) != 0
1566 pub fn type_needs_subst(ty: t) -> bool {
1567 tbox_has_flag(get(ty), needs_subst)
1570 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
1571 tref.substs.self_ty.iter().any(|&t| type_is_error(t)) ||
1572 tref.substs.tps.iter().any(|&t| type_is_error(t))
1575 pub fn type_is_ty_var(ty: t) -> bool {
1577 ty_infer(TyVar(_)) => true,
1582 pub fn type_is_bool(ty: t) -> bool { get(ty).sty == ty_bool }
1584 pub fn type_is_self(ty: t) -> bool {
1586 ty_self(..) => true,
1591 fn type_is_slice(ty:t) -> bool {
1593 ty_rptr(_, mt) => match get(mt.ty).sty {
1594 ty_vec(_, None) | ty_str => true,
1601 pub fn type_is_structural(ty: t) -> bool {
1603 ty_struct(..) | ty_tup(_) | ty_enum(..) | ty_closure(_) | ty_trait(..) |
1604 ty_vec(_, Some(_)) => true,
1605 _ => type_is_slice(ty)
1609 pub fn type_is_simd(cx: &ctxt, ty: t) -> bool {
1611 ty_struct(did, _) => lookup_simd(cx, did),
1616 pub fn sequence_element_type(cx: &ctxt, ty: t) -> t {
1618 ty_vec(mt, Some(_)) => mt.ty,
1619 ty_ptr(mt{ty: t, ..}) | ty_rptr(_, mt{ty: t, ..}) |
1620 ty_box(t) | ty_uniq(t) => match get(t).sty {
1621 ty_vec(mt, None) => mt.ty,
1622 ty_str => mk_mach_uint(ast::TyU8),
1623 _ => cx.sess.bug("sequence_element_type called on non-sequence value"),
1625 _ => cx.sess.bug("sequence_element_type called on non-sequence value"),
1629 pub fn simd_type(cx: &ctxt, ty: t) -> t {
1631 ty_struct(did, ref substs) => {
1632 let fields = lookup_struct_fields(cx, did);
1633 lookup_field_type(cx, did, fields.get(0).id, substs)
1635 _ => fail!("simd_type called on invalid type")
1639 pub fn simd_size(cx: &ctxt, ty: t) -> uint {
1641 ty_struct(did, _) => {
1642 let fields = lookup_struct_fields(cx, did);
1645 _ => fail!("simd_size called on invalid type")
1649 pub fn type_is_boxed(ty: t) -> bool {
1656 pub fn type_is_region_ptr(ty: t) -> bool {
1658 ty_rptr(_, mt) => match get(mt.ty).sty {
1659 // FIXME(nrc, DST) slices weren't regarded as rptrs, so we preserve this
1660 // odd behaviour for now. (But ~[] were unique. I have no idea why).
1661 ty_vec(_, None) | ty_str => false,
1668 pub fn type_is_unsafe_ptr(ty: t) -> bool {
1670 ty_ptr(_) => return true,
1675 pub fn type_is_unique(ty: t) -> bool {
1683 A scalar type is one that denotes an atomic datum, with no sub-components.
1684 (A ty_ptr is scalar because it represents a non-managed pointer, so its
1685 contents are abstract to rustc.)
1687 pub fn type_is_scalar(ty: t) -> bool {
1689 ty_nil | ty_bool | ty_char | ty_int(_) | ty_float(_) | ty_uint(_) |
1690 ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) |
1691 ty_bare_fn(..) | ty_ptr(_) => true,
1696 pub fn type_needs_drop(cx: &ctxt, ty: t) -> bool {
1697 type_contents(cx, ty).needs_drop(cx)
1700 // Some things don't need cleanups during unwinding because the
1701 // task can free them all at once later. Currently only things
1702 // that only contain scalars and shared boxes can avoid unwind
1704 pub fn type_needs_unwind_cleanup(cx: &ctxt, ty: t) -> bool {
1705 match cx.needs_unwind_cleanup_cache.borrow().find(&ty) {
1706 Some(&result) => return result,
1710 let mut tycache = HashSet::new();
1711 let needs_unwind_cleanup =
1712 type_needs_unwind_cleanup_(cx, ty, &mut tycache, false);
1713 cx.needs_unwind_cleanup_cache.borrow_mut().insert(ty, needs_unwind_cleanup);
1714 return needs_unwind_cleanup;
1717 fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t,
1718 tycache: &mut HashSet<t>,
1719 encountered_box: bool) -> bool {
1721 // Prevent infinite recursion
1722 if !tycache.insert(ty) {
1726 let mut encountered_box = encountered_box;
1727 let mut needs_unwind_cleanup = false;
1728 maybe_walk_ty(ty, |ty| {
1729 let old_encountered_box = encountered_box;
1730 let result = match get(ty).sty {
1732 encountered_box = true;
1735 ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1736 ty_tup(_) | ty_ptr(_) => {
1739 ty_enum(did, ref substs) => {
1740 for v in (*enum_variants(cx, did)).iter() {
1741 for aty in v.args.iter() {
1742 let t = subst(cx, substs, *aty);
1743 needs_unwind_cleanup |=
1744 type_needs_unwind_cleanup_(cx, t, tycache,
1748 !needs_unwind_cleanup
1751 // Once we're inside a box, the annihilator will find
1752 // it and destroy it.
1753 if !encountered_box {
1754 needs_unwind_cleanup = true;
1761 needs_unwind_cleanup = true;
1766 encountered_box = old_encountered_box;
1770 return needs_unwind_cleanup;
1774 * Type contents is how the type checker reasons about kinds.
1775 * They track what kinds of things are found within a type. You can
1776 * think of them as kind of an "anti-kind". They track the kinds of values
1777 * and thinks that are contained in types. Having a larger contents for
1778 * a type tends to rule that type *out* from various kinds. For example,
1779 * a type that contains a reference is not sendable.
1781 * The reason we compute type contents and not kinds is that it is
1782 * easier for me (nmatsakis) to think about what is contained within
1783 * a type than to think about what is *not* contained within a type.
1785 pub struct TypeContents {
1789 macro_rules! def_type_content_sets(
1790 (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
1792 use middle::ty::TypeContents;
1793 $(pub static $name: TypeContents = TypeContents { bits: $bits };)+
1798 def_type_content_sets!(
1800 None = 0b0000_0000__0000_0000__0000,
1802 // Things that are interior to the value (first nibble):
1803 InteriorUnsized = 0b0000_0000__0000_0000__0001,
1804 InteriorUnsafe = 0b0000_0000__0000_0000__0010,
1805 // InteriorAll = 0b00000000__00000000__1111,
1807 // Things that are owned by the value (second and third nibbles):
1808 OwnsOwned = 0b0000_0000__0000_0001__0000,
1809 OwnsDtor = 0b0000_0000__0000_0010__0000,
1810 OwnsManaged /* see [1] below */ = 0b0000_0000__0000_0100__0000,
1811 OwnsAffine = 0b0000_0000__0000_1000__0000,
1812 OwnsAll = 0b0000_0000__1111_1111__0000,
1814 // Things that are reachable by the value in any way (fourth nibble):
1815 ReachesNonsendAnnot = 0b0000_0001__0000_0000__0000,
1816 ReachesBorrowed = 0b0000_0010__0000_0000__0000,
1817 // ReachesManaged /* see [1] below */ = 0b0000_0100__0000_0000__0000,
1818 ReachesMutable = 0b0000_1000__0000_0000__0000,
1819 ReachesNoShare = 0b0001_0000__0000_0000__0000,
1820 ReachesAll = 0b0001_1111__0000_0000__0000,
1822 // Things that cause values to *move* rather than *copy*
1823 Moves = 0b0000_0000__0000_1011__0000,
1825 // Things that mean drop glue is necessary
1826 NeedsDrop = 0b0000_0000__0000_0111__0000,
1828 // Things that prevent values from being sent
1830 // Note: For checking whether something is sendable, it'd
1831 // be sufficient to have ReachesManaged. However, we include
1832 // both ReachesManaged and OwnsManaged so that when
1833 // a parameter has a bound T:Send, we are able to deduce
1834 // that it neither reaches nor owns a managed pointer.
1835 Nonsendable = 0b0000_0111__0000_0100__0000,
1837 // Things that prevent values from being considered 'static
1838 Nonstatic = 0b0000_0010__0000_0000__0000,
1840 // Things that prevent values from being considered sized
1841 Nonsized = 0b0000_0000__0000_0000__0001,
1843 // Things that prevent values from being shared
1844 Nonsharable = 0b0001_0000__0000_0000__0000,
1846 // Things that make values considered not POD (would be same
1847 // as `Moves`, but for the fact that managed data `@` is
1848 // not considered POD)
1849 Noncopy = 0b0000_0000__0000_1111__0000,
1851 // Bits to set when a managed value is encountered
1853 // [1] Do not set the bits TC::OwnsManaged or
1854 // TC::ReachesManaged directly, instead reference
1855 // TC::Managed to set them both at once.
1856 Managed = 0b0000_0100__0000_0100__0000,
1859 All = 0b1111_1111__1111_1111__1111
1864 pub fn meets_bound(&self, cx: &ctxt, bb: BuiltinBound) -> bool {
1866 BoundStatic => self.is_static(cx),
1867 BoundSend => self.is_sendable(cx),
1868 BoundSized => self.is_sized(cx),
1869 BoundCopy => self.is_copy(cx),
1870 BoundShare => self.is_sharable(cx),
1874 pub fn when(&self, cond: bool) -> TypeContents {
1875 if cond {*self} else {TC::None}
1878 pub fn intersects(&self, tc: TypeContents) -> bool {
1879 (self.bits & tc.bits) != 0
1882 pub fn is_static(&self, _: &ctxt) -> bool {
1883 !self.intersects(TC::Nonstatic)
1886 pub fn is_sendable(&self, _: &ctxt) -> bool {
1887 !self.intersects(TC::Nonsendable)
1890 pub fn is_sharable(&self, _: &ctxt) -> bool {
1891 !self.intersects(TC::Nonsharable)
1894 pub fn owns_managed(&self) -> bool {
1895 self.intersects(TC::OwnsManaged)
1898 pub fn owns_owned(&self) -> bool {
1899 self.intersects(TC::OwnsOwned)
1902 pub fn is_sized(&self, _: &ctxt) -> bool {
1903 !self.intersects(TC::Nonsized)
1906 pub fn is_copy(&self, _: &ctxt) -> bool {
1907 !self.intersects(TC::Noncopy)
1910 pub fn interior_unsafe(&self) -> bool {
1911 self.intersects(TC::InteriorUnsafe)
1914 pub fn interior_unsized(&self) -> bool {
1915 self.intersects(TC::InteriorUnsized)
1918 pub fn moves_by_default(&self, _: &ctxt) -> bool {
1919 self.intersects(TC::Moves)
1922 pub fn needs_drop(&self, _: &ctxt) -> bool {
1923 self.intersects(TC::NeedsDrop)
1926 pub fn owned_pointer(&self) -> TypeContents {
1928 * Includes only those bits that still apply
1929 * when indirected through a `Box` pointer
1932 *self & (TC::OwnsAll | TC::ReachesAll))
1935 pub fn reference(&self, bits: TypeContents) -> TypeContents {
1937 * Includes only those bits that still apply
1938 * when indirected through a reference (`&`)
1941 *self & TC::ReachesAll)
1944 pub fn managed_pointer(&self) -> TypeContents {
1946 * Includes only those bits that still apply
1947 * when indirected through a managed pointer (`@`)
1950 *self & TC::ReachesAll)
1953 pub fn unsafe_pointer(&self) -> TypeContents {
1955 * Includes only those bits that still apply
1956 * when indirected through an unsafe pointer (`*`)
1958 *self & TC::ReachesAll
1961 pub fn union<T>(v: &[T], f: |&T| -> TypeContents) -> TypeContents {
1962 v.iter().fold(TC::None, |tc, t| tc | f(t))
1965 pub fn has_dtor(&self) -> bool {
1966 self.intersects(TC::OwnsDtor)
1970 impl ops::BitOr<TypeContents,TypeContents> for TypeContents {
1971 fn bitor(&self, other: &TypeContents) -> TypeContents {
1972 TypeContents {bits: self.bits | other.bits}
1976 impl ops::BitAnd<TypeContents,TypeContents> for TypeContents {
1977 fn bitand(&self, other: &TypeContents) -> TypeContents {
1978 TypeContents {bits: self.bits & other.bits}
1982 impl ops::Sub<TypeContents,TypeContents> for TypeContents {
1983 fn sub(&self, other: &TypeContents) -> TypeContents {
1984 TypeContents {bits: self.bits & !other.bits}
1988 impl fmt::Show for TypeContents {
1989 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1990 write!(f, "TypeContents({:t})", self.bits)
1994 pub fn type_is_static(cx: &ctxt, t: ty::t) -> bool {
1995 type_contents(cx, t).is_static(cx)
1998 pub fn type_is_sendable(cx: &ctxt, t: ty::t) -> bool {
1999 type_contents(cx, t).is_sendable(cx)
2002 pub fn type_interior_is_unsafe(cx: &ctxt, t: ty::t) -> bool {
2003 type_contents(cx, t).interior_unsafe()
2006 pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
2007 let ty_id = type_id(ty);
2009 match cx.tc_cache.borrow().find(&ty_id) {
2010 Some(tc) => { return *tc; }
2014 let mut cache = HashMap::new();
2015 let result = tc_ty(cx, ty, &mut cache);
2017 cx.tc_cache.borrow_mut().insert(ty_id, result);
2022 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2024 // Subtle: Note that we are *not* using cx.tc_cache here but rather a
2025 // private cache for this walk. This is needed in the case of cyclic
2028 // struct List { next: Box<Option<List>>, ... }
2030 // When computing the type contents of such a type, we wind up deeply
2031 // recursing as we go. So when we encounter the recursive reference
2032 // to List, we temporarily use TC::None as its contents. Later we'll
2033 // patch up the cache with the correct value, once we've computed it
2034 // (this is basically a co-inductive process, if that helps). So in
2035 // the end we'll compute TC::OwnsOwned, in this case.
2037 // The problem is, as we are doing the computation, we will also
2038 // compute an *intermediate* contents for, e.g., Option<List> of
2039 // TC::None. This is ok during the computation of List itself, but if
2040 // we stored this intermediate value into cx.tc_cache, then later
2041 // requests for the contents of Option<List> would also yield TC::None
2042 // which is incorrect. This value was computed based on the crutch
2043 // value for the type contents of list. The correct value is
2044 // TC::OwnsOwned. This manifested as issue #4821.
2045 let ty_id = type_id(ty);
2046 match cache.find(&ty_id) {
2047 Some(tc) => { return *tc; }
2050 match cx.tc_cache.borrow().find(&ty_id) { // Must check both caches!
2051 Some(tc) => { return *tc; }
2054 cache.insert(ty_id, TC::None);
2056 let result = match get(ty).sty {
2057 // Scalar and unique types are sendable, and durable
2058 ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
2059 ty_bare_fn(_) | ty::ty_char | ty_str => {
2063 ty_closure(ref c) => {
2064 closure_contents(cx, *c)
2068 tc_ty(cx, typ, cache).managed_pointer()
2072 match get(typ).sty {
2073 ty_str => TC::OwnsOwned,
2074 _ => tc_ty(cx, typ, cache).owned_pointer(),
2078 ty_trait(box ty::TyTrait { store, bounds, .. }) => {
2079 object_contents(cx, store, bounds)
2083 tc_ty(cx, mt.ty, cache).unsafe_pointer()
2086 ty_rptr(r, ref mt) => {
2087 match get(mt.ty).sty {
2088 ty_str => borrowed_contents(r, ast::MutImmutable),
2089 _ => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(r, mt.mutbl)),
2094 tc_mt(cx, mt, cache)
2097 ty_struct(did, ref substs) => {
2098 let flds = struct_fields(cx, did, substs);
2100 TypeContents::union(flds.as_slice(),
2101 |f| tc_mt(cx, f.mt, cache));
2102 if ty::has_dtor(cx, did) {
2103 res = res | TC::OwnsDtor;
2105 apply_lang_items(cx, did, res)
2108 ty_tup(ref tys) => {
2109 TypeContents::union(tys.as_slice(),
2110 |ty| tc_ty(cx, *ty, cache))
2113 ty_enum(did, ref substs) => {
2114 let variants = substd_enum_variants(cx, did, substs);
2116 TypeContents::union(variants.as_slice(), |variant| {
2117 TypeContents::union(variant.args.as_slice(),
2119 tc_ty(cx, *arg_ty, cache)
2122 apply_lang_items(cx, did, res)
2126 // We only ever ask for the kind of types that are defined in
2127 // the current crate; therefore, the only type parameters that
2128 // could be in scope are those defined in the current crate.
2129 // If this assertion failures, it is likely because of a
2130 // failure in the cross-crate inlining code to translate a
2132 assert_eq!(p.def_id.krate, ast::LOCAL_CRATE);
2134 let ty_param_defs = cx.ty_param_defs.borrow();
2135 let tp_def = ty_param_defs.get(&p.def_id.node);
2136 kind_bounds_to_contents(cx,
2137 tp_def.bounds.builtin_bounds,
2138 tp_def.bounds.trait_bounds.as_slice())
2141 ty_self(def_id) => {
2142 // FIXME(#4678)---self should just be a ty param
2144 // Self may be bounded if the associated trait has builtin kinds
2145 // for supertraits. If so we can use those bounds.
2146 let trait_def = lookup_trait_def(cx, def_id);
2147 let traits = [trait_def.trait_ref.clone()];
2148 kind_bounds_to_contents(cx, trait_def.bounds, traits)
2152 // This occurs during coherence, but shouldn't occur at other
2158 cx.sess.bug("asked to compute contents of error type");
2162 cache.insert(ty_id, result);
2168 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2170 let mc = TC::ReachesMutable.when(mt.mutbl == MutMutable);
2171 mc | tc_ty(cx, mt.ty, cache)
2174 fn apply_lang_items(cx: &ctxt,
2178 if Some(did) == cx.lang_items.no_send_bound() {
2179 tc | TC::ReachesNonsendAnnot
2180 } else if Some(did) == cx.lang_items.managed_bound() {
2182 } else if Some(did) == cx.lang_items.no_copy_bound() {
2184 } else if Some(did) == cx.lang_items.no_share_bound() {
2185 tc | TC::ReachesNoShare
2186 } else if Some(did) == cx.lang_items.unsafe_type() {
2187 // FIXME(#13231): This shouldn't be needed after
2188 // opt-in built-in bounds are implemented.
2189 (tc | TC::InteriorUnsafe) - TC::Nonsharable
2195 fn borrowed_contents(region: ty::Region,
2196 mutbl: ast::Mutability)
2199 * Type contents due to containing a reference
2200 * with the region `region` and borrow kind `bk`
2203 let b = match mutbl {
2204 ast::MutMutable => TC::ReachesMutable | TC::OwnsAffine,
2205 ast::MutImmutable => TC::None,
2207 b | (TC::ReachesBorrowed).when(region != ty::ReStatic)
2210 fn closure_contents(cx: &ctxt, cty: &ClosureTy) -> TypeContents {
2211 // Closure contents are just like trait contents, but with potentially
2213 let st = object_contents(cx, cty.store, cty.bounds);
2215 // This also prohibits "@once fn" from being copied, which allows it to
2216 // be called. Neither way really makes much sense.
2217 let ot = match cty.onceness {
2218 ast::Once => TC::OwnsAffine,
2219 ast::Many => TC::None,
2225 fn object_contents(cx: &ctxt,
2227 bounds: BuiltinBounds)
2229 // These are the type contents of the (opaque) interior
2230 let contents = kind_bounds_to_contents(cx, bounds, []);
2234 contents.owned_pointer()
2236 RegionTraitStore(r, mutbl) => {
2237 contents.reference(borrowed_contents(r, mutbl))
2242 fn kind_bounds_to_contents(cx: &ctxt,
2243 bounds: BuiltinBounds,
2244 traits: &[Rc<TraitRef>])
2246 let _i = indenter();
2247 let mut tc = TC::All;
2248 each_inherited_builtin_bound(cx, bounds, traits, |bound| {
2249 tc = tc - match bound {
2250 BoundStatic => TC::Nonstatic,
2251 BoundSend => TC::Nonsendable,
2252 BoundSized => TC::Nonsized,
2253 BoundCopy => TC::Noncopy,
2254 BoundShare => TC::Nonsharable,
2259 // Iterates over all builtin bounds on the type parameter def, including
2260 // those inherited from traits with builtin-kind-supertraits.
2261 fn each_inherited_builtin_bound(cx: &ctxt,
2262 bounds: BuiltinBounds,
2263 traits: &[Rc<TraitRef>],
2264 f: |BuiltinBound|) {
2265 for bound in bounds.iter() {
2269 each_bound_trait_and_supertraits(cx, traits, |trait_ref| {
2270 let trait_def = lookup_trait_def(cx, trait_ref.def_id);
2271 for bound in trait_def.bounds.iter() {
2280 pub fn type_moves_by_default(cx: &ctxt, ty: t) -> bool {
2281 type_contents(cx, ty).moves_by_default(cx)
2284 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
2285 pub fn is_instantiable(cx: &ctxt, r_ty: t) -> bool {
2286 fn type_requires(cx: &ctxt, seen: &mut Vec<DefId>,
2287 r_ty: t, ty: t) -> bool {
2288 debug!("type_requires({}, {})?",
2289 ::util::ppaux::ty_to_str(cx, r_ty),
2290 ::util::ppaux::ty_to_str(cx, ty));
2293 get(r_ty).sty == get(ty).sty ||
2294 subtypes_require(cx, seen, r_ty, ty)
2297 debug!("type_requires({}, {})? {}",
2298 ::util::ppaux::ty_to_str(cx, r_ty),
2299 ::util::ppaux::ty_to_str(cx, ty),
2304 fn subtypes_require(cx: &ctxt, seen: &mut Vec<DefId>,
2305 r_ty: t, ty: t) -> bool {
2306 debug!("subtypes_require({}, {})?",
2307 ::util::ppaux::ty_to_str(cx, r_ty),
2308 ::util::ppaux::ty_to_str(cx, ty));
2310 let r = match get(ty).sty {
2311 // fixed length vectors need special treatment compared to
2312 // normal vectors, since they don't necessarily have the
2313 // possibility to have length zero.
2314 ty_vec(_, Some(0)) => false, // don't need no contents
2315 ty_vec(mt, Some(_)) => type_requires(cx, seen, r_ty, mt.ty),
2331 ty_vec(_, None) => {
2334 ty_box(typ) | ty_uniq(typ) => {
2335 type_requires(cx, seen, r_ty, typ)
2337 ty_rptr(_, ref mt) => {
2338 type_requires(cx, seen, r_ty, mt.ty)
2342 false // unsafe ptrs can always be NULL
2349 ty_struct(ref did, _) if seen.contains(did) => {
2353 ty_struct(did, ref substs) => {
2355 let fields = struct_fields(cx, did, substs);
2356 let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
2357 seen.pop().unwrap();
2362 ts.iter().any(|t| type_requires(cx, seen, r_ty, *t))
2365 ty_enum(ref did, _) if seen.contains(did) => {
2369 ty_enum(did, ref substs) => {
2371 let vs = enum_variants(cx, did);
2372 let r = !vs.is_empty() && vs.iter().all(|variant| {
2373 variant.args.iter().any(|aty| {
2374 let sty = subst(cx, substs, *aty);
2375 type_requires(cx, seen, r_ty, sty)
2378 seen.pop().unwrap();
2383 debug!("subtypes_require({}, {})? {}",
2384 ::util::ppaux::ty_to_str(cx, r_ty),
2385 ::util::ppaux::ty_to_str(cx, ty),
2391 let mut seen = Vec::new();
2392 !subtypes_require(cx, &mut seen, r_ty, r_ty)
2395 /// Describes whether a type is representable. For types that are not
2396 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
2397 /// distinguish between types that are recursive with themselves and types that
2398 /// contain a different recursive type. These cases can therefore be treated
2399 /// differently when reporting errors.
2401 pub enum Representability {
2407 /// Check whether a type is representable. This means it cannot contain unboxed
2408 /// structural recursion. This check is needed for structs and enums.
2409 pub fn is_type_representable(cx: &ctxt, sp: Span, ty: t) -> Representability {
2411 // Iterate until something non-representable is found
2412 fn find_nonrepresentable<It: Iterator<t>>(cx: &ctxt, sp: Span, seen: &mut Vec<DefId>,
2413 mut iter: It) -> Representability {
2415 let r = type_structurally_recursive(cx, sp, seen, ty);
2416 if r != Representable {
2423 // Does the type `ty` directly (without indirection through a pointer)
2424 // contain any types on stack `seen`?
2425 fn type_structurally_recursive(cx: &ctxt, sp: Span, seen: &mut Vec<DefId>,
2426 ty: t) -> Representability {
2427 debug!("type_structurally_recursive: {}",
2428 ::util::ppaux::ty_to_str(cx, ty));
2430 // Compare current type to previously seen types
2433 ty_enum(did, _) => {
2434 for (i, &seen_did) in seen.iter().enumerate() {
2435 if did == seen_did {
2436 return if i == 0 { SelfRecursive }
2437 else { ContainsRecursive }
2444 // Check inner types
2448 find_nonrepresentable(cx, sp, seen, ts.iter().map(|t| *t))
2450 // Fixed-length vectors.
2451 // FIXME(#11924) Behavior undecided for zero-length vectors.
2452 ty_vec(mt, Some(_)) => {
2453 type_structurally_recursive(cx, sp, seen, mt.ty)
2456 // Push struct and enum def-ids onto `seen` before recursing.
2457 ty_struct(did, ref substs) => {
2459 let fields = struct_fields(cx, did, substs);
2460 let r = find_nonrepresentable(cx, sp, seen,
2461 fields.iter().map(|f| f.mt.ty));
2465 ty_enum(did, ref substs) => {
2467 let vs = enum_variants(cx, did);
2469 let mut r = Representable;
2470 for variant in vs.iter() {
2471 let iter = variant.args.iter().map(|aty| {
2472 aty.subst_spanned(cx, substs, Some(sp))
2474 r = find_nonrepresentable(cx, sp, seen, iter);
2476 if r != Representable { break }
2487 debug!("is_type_representable: {}",
2488 ::util::ppaux::ty_to_str(cx, ty));
2490 // To avoid a stack overflow when checking an enum variant or struct that
2491 // contains a different, structurally recursive type, maintain a stack
2492 // of seen types and check recursion for each of them (issues #3008, #3779).
2493 let mut seen: Vec<DefId> = Vec::new();
2494 type_structurally_recursive(cx, sp, &mut seen, ty)
2497 pub fn type_is_trait(ty: t) -> bool {
2499 ty_trait(..) => true,
2504 pub fn type_is_integral(ty: t) -> bool {
2506 ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
2511 pub fn type_is_uint(ty: t) -> bool {
2513 ty_infer(IntVar(_)) | ty_uint(ast::TyU) => true,
2518 pub fn type_is_char(ty: t) -> bool {
2525 pub fn type_is_bare_fn(ty: t) -> bool {
2527 ty_bare_fn(..) => true,
2532 pub fn type_is_fp(ty: t) -> bool {
2534 ty_infer(FloatVar(_)) | ty_float(_) => true,
2539 pub fn type_is_numeric(ty: t) -> bool {
2540 return type_is_integral(ty) || type_is_fp(ty);
2543 pub fn type_is_signed(ty: t) -> bool {
2550 pub fn type_is_machine(ty: t) -> bool {
2552 ty_int(ast::TyI) | ty_uint(ast::TyU) => false,
2553 ty_int(..) | ty_uint(..) | ty_float(..) => true,
2558 // Is the type's representation size known at compile time?
2559 #[allow(dead_code)] // leaving in for DST
2560 pub fn type_is_sized(cx: &ctxt, ty: ty::t) -> bool {
2561 type_contents(cx, ty).is_sized(cx)
2564 // Whether a type is enum like, that is an enum type with only nullary
2566 pub fn type_is_c_like_enum(cx: &ctxt, ty: t) -> bool {
2568 ty_enum(did, _) => {
2569 let variants = enum_variants(cx, did);
2570 if variants.len() == 0 {
2573 variants.iter().all(|v| v.args.len() == 0)
2580 // Returns the type and mutability of *t.
2582 // The parameter `explicit` indicates if this is an *explicit* dereference.
2583 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
2584 pub fn deref(t: t, explicit: bool) -> Option<mt> {
2586 ty_box(typ) | ty_uniq(typ) => match get(typ).sty {
2587 // Don't deref ~[] etc., might need to generalise this to all DST.
2588 ty_vec(_, None) | ty_str => None,
2591 mutbl: ast::MutImmutable,
2594 ty_rptr(_, mt) => match get(mt.ty).sty {
2595 // Don't deref &[], might need to generalise this to all DST.
2596 ty_vec(_, None) | ty_str => None,
2599 ty_ptr(mt) if explicit => Some(mt),
2604 // Returns the type of t[i]
2605 pub fn index(t: t) -> Option<mt> {
2607 ty_vec(mt, Some(_)) => Some(mt),
2608 ty_ptr(mt{ty: t, ..}) | ty_rptr(_, mt{ty: t, ..}) |
2609 ty_box(t) | ty_uniq(t) => match get(t).sty {
2610 ty_vec(mt, None) => Some(mt),
2611 ty_str => Some(mt {ty: mk_u8(), mutbl: ast::MutImmutable}),
2618 pub fn node_id_to_trait_ref(cx: &ctxt, id: ast::NodeId) -> Rc<ty::TraitRef> {
2619 match cx.trait_refs.borrow().find(&id) {
2620 Some(t) => t.clone(),
2621 None => cx.sess.bug(
2622 format!("node_id_to_trait_ref: no trait ref for node `{}`",
2623 cx.map.node_to_str(id)))
2627 pub fn try_node_id_to_type(cx: &ctxt, id: ast::NodeId) -> Option<t> {
2628 cx.node_types.borrow().find_copy(&(id as uint))
2631 pub fn node_id_to_type(cx: &ctxt, id: ast::NodeId) -> t {
2632 match try_node_id_to_type(cx, id) {
2634 None => cx.sess.bug(
2635 format!("node_id_to_type: no type for node `{}`",
2636 cx.map.node_to_str(id)))
2640 pub fn node_id_to_type_opt(cx: &ctxt, id: ast::NodeId) -> Option<t> {
2641 match cx.node_types.borrow().find(&(id as uint)) {
2642 Some(&t) => Some(t),
2647 pub fn node_id_item_substs(cx: &ctxt, id: ast::NodeId) -> ItemSubsts {
2648 match cx.item_substs.borrow().find(&id) {
2649 None => ItemSubsts::empty(),
2650 Some(ts) => ts.clone(),
2654 pub fn fn_is_variadic(fty: t) -> bool {
2655 match get(fty).sty {
2656 ty_bare_fn(ref f) => f.sig.variadic,
2657 ty_closure(ref f) => f.sig.variadic,
2659 fail!("fn_is_variadic() called on non-fn type: {:?}", s)
2664 pub fn ty_fn_sig(fty: t) -> FnSig {
2665 match get(fty).sty {
2666 ty_bare_fn(ref f) => f.sig.clone(),
2667 ty_closure(ref f) => f.sig.clone(),
2669 fail!("ty_fn_sig() called on non-fn type: {:?}", s)
2674 // Type accessors for substructures of types
2675 pub fn ty_fn_args(fty: t) -> Vec<t> {
2676 match get(fty).sty {
2677 ty_bare_fn(ref f) => f.sig.inputs.clone(),
2678 ty_closure(ref f) => f.sig.inputs.clone(),
2680 fail!("ty_fn_args() called on non-fn type: {:?}", s)
2685 pub fn ty_closure_store(fty: t) -> TraitStore {
2686 match get(fty).sty {
2687 ty_closure(ref f) => f.store,
2689 fail!("ty_closure_store() called on non-closure type: {:?}", s)
2694 pub fn ty_fn_ret(fty: t) -> t {
2695 match get(fty).sty {
2696 ty_bare_fn(ref f) => f.sig.output,
2697 ty_closure(ref f) => f.sig.output,
2699 fail!("ty_fn_ret() called on non-fn type: {:?}", s)
2704 pub fn is_fn_ty(fty: t) -> bool {
2705 match get(fty).sty {
2706 ty_bare_fn(_) => true,
2707 ty_closure(_) => true,
2712 pub fn ty_region(tcx: &ctxt,
2720 format!("ty_region() invoked on in appropriate ty: {:?}", s));
2725 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
2726 // doesn't provide type parameter substitutions.
2727 pub fn pat_ty(cx: &ctxt, pat: &ast::Pat) -> t {
2728 return node_id_to_type(cx, pat.id);
2732 // Returns the type of an expression as a monotype.
2734 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression. That is, in
2735 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
2736 // auto-ref. The type returned by this function does not consider such
2737 // adjustments. See `expr_ty_adjusted()` instead.
2739 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
2740 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
2741 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
2742 // expr_ty_params_and_ty() below.
2743 pub fn expr_ty(cx: &ctxt, expr: &ast::Expr) -> t {
2744 return node_id_to_type(cx, expr.id);
2747 pub fn expr_ty_opt(cx: &ctxt, expr: &ast::Expr) -> Option<t> {
2748 return node_id_to_type_opt(cx, expr.id);
2751 pub fn expr_ty_adjusted(cx: &ctxt, expr: &ast::Expr) -> t {
2754 * Returns the type of `expr`, considering any `AutoAdjustment`
2755 * entry recorded for that expression.
2757 * It would almost certainly be better to store the adjusted ty in with
2758 * the `AutoAdjustment`, but I opted not to do this because it would
2759 * require serializing and deserializing the type and, although that's not
2760 * hard to do, I just hate that code so much I didn't want to touch it
2761 * unless it was to fix it properly, which seemed a distraction from the
2762 * task at hand! -nmatsakis
2765 adjust_ty(cx, expr.span, expr.id, expr_ty(cx, expr),
2766 cx.adjustments.borrow().find(&expr.id),
2767 |method_call| cx.method_map.borrow().find(&method_call).map(|method| method.ty))
2770 pub fn expr_span(cx: &ctxt, id: NodeId) -> Span {
2771 match cx.map.find(id) {
2772 Some(ast_map::NodeExpr(e)) => {
2776 cx.sess.bug(format!("Node id {} is not an expr: {:?}",
2780 cx.sess.bug(format!("Node id {} is not present \
2781 in the node map", id));
2786 pub fn local_var_name_str(cx: &ctxt, id: NodeId) -> InternedString {
2787 match cx.map.find(id) {
2788 Some(ast_map::NodeLocal(pat)) => {
2790 ast::PatIdent(_, ref path, _) => {
2791 token::get_ident(ast_util::path_to_ident(path))
2795 format!("Variable id {} maps to {:?}, not local",
2802 format!("Variable id {} maps to {:?}, not local",
2808 pub fn adjust_ty(cx: &ctxt,
2810 expr_id: ast::NodeId,
2811 unadjusted_ty: ty::t,
2812 adjustment: Option<&AutoAdjustment>,
2813 method_type: |typeck::MethodCall| -> Option<ty::t>)
2815 /*! See `expr_ty_adjusted` */
2817 return match adjustment {
2818 Some(adjustment) => {
2820 AutoAddEnv(store) => {
2821 match ty::get(unadjusted_ty).sty {
2822 ty::ty_bare_fn(ref b) => {
2825 ty::ClosureTy {fn_style: b.fn_style,
2826 onceness: ast::Many,
2828 bounds: ty::AllBuiltinBounds(),
2829 sig: b.sig.clone()})
2833 format!("add_env adjustment on non-bare-fn: \
2840 AutoDerefRef(ref adj) => {
2841 let mut adjusted_ty = unadjusted_ty;
2843 if !ty::type_is_error(adjusted_ty) {
2844 for i in range(0, adj.autoderefs) {
2845 let method_call = typeck::MethodCall::autoderef(expr_id, i as u32);
2846 match method_type(method_call) {
2847 Some(method_ty) => {
2848 adjusted_ty = ty_fn_ret(method_ty);
2852 match deref(adjusted_ty, true) {
2853 Some(mt) => { adjusted_ty = mt.ty; }
2857 format!("the {}th autoderef failed: \
2860 ty_to_str(cx, adjusted_ty)));
2867 None => adjusted_ty,
2868 Some(ref autoref) => {
2877 AutoBorrowVec(r, m) => {
2878 borrow_vec(cx, span, r, m, adjusted_ty)
2881 AutoBorrowVecRef(r, m) => {
2882 adjusted_ty = borrow_vec(cx,
2889 mutbl: ast::MutImmutable
2894 mk_ptr(cx, mt {ty: adjusted_ty, mutbl: m})
2897 AutoBorrowObj(r, m) => {
2898 borrow_obj(cx, span, r, m, adjusted_ty)
2905 AutoObject(store, bounds, def_id, ref substs) => {
2906 mk_trait(cx, def_id, substs.clone(), store, bounds)
2910 None => unadjusted_ty
2913 fn borrow_vec(cx: &ctxt,
2917 ty: ty::t) -> ty::t {
2919 ty_uniq(t) | ty_ptr(mt{ty: t, ..}) |
2920 ty_rptr(_, mt{ty: t, ..}) => match get(t).sty {
2921 ty::ty_vec(mt, None) => ty::mk_slice(cx, r, ty::mt {ty: mt.ty, mutbl: m}),
2922 ty::ty_str => ty::mk_str_slice(cx, r, m),
2926 format!("borrow-vec associated with bad sty: {:?}", get(ty).sty));
2929 ty_vec(mt, Some(_)) => ty::mk_slice(cx, r, ty::mt {ty: mt.ty, mutbl: m}),
2934 format!("borrow-vec associated with bad sty: {:?}", s));
2939 fn borrow_obj(cx: &ctxt, span: Span, r: Region,
2940 m: ast::Mutability, ty: ty::t) -> ty::t {
2942 ty_trait(box ty::TyTrait {def_id, ref substs, bounds, .. }) => {
2943 ty::mk_trait(cx, def_id, substs.clone(),
2944 RegionTraitStore(r, m), bounds)
2949 format!("borrow-trait-obj associated with bad sty: {:?}",
2957 pub fn map_region(&self, f: |Region| -> Region) -> AutoRef {
2959 ty::AutoPtr(r, m) => ty::AutoPtr(f(r), m),
2960 ty::AutoBorrowVec(r, m) => ty::AutoBorrowVec(f(r), m),
2961 ty::AutoBorrowVecRef(r, m) => ty::AutoBorrowVecRef(f(r), m),
2962 ty::AutoUnsafe(m) => ty::AutoUnsafe(m),
2963 ty::AutoBorrowObj(r, m) => ty::AutoBorrowObj(f(r), m),
2968 pub fn method_call_type_param_defs(tcx: &ctxt, origin: typeck::MethodOrigin)
2969 -> Rc<Vec<TypeParameterDef>> {
2971 typeck::MethodStatic(did) => {
2972 // n.b.: When we encode impl methods, the bounds
2973 // that we encode include both the impl bounds
2974 // and then the method bounds themselves...
2975 ty::lookup_item_type(tcx, did).generics.type_param_defs
2977 typeck::MethodParam(typeck::MethodParam {
2979 method_num: n_mth, ..}) |
2980 typeck::MethodObject(typeck::MethodObject {
2982 method_num: n_mth, ..}) => {
2983 // ...trait methods bounds, in contrast, include only the
2984 // method bounds, so we must preprend the tps from the
2985 // trait itself. This ought to be harmonized.
2986 let trait_type_param_defs =
2987 Vec::from_slice(lookup_trait_def(tcx, trt_id).generics.type_param_defs());
2988 Rc::new(trait_type_param_defs.append(
2989 ty::trait_method(tcx, trt_id, n_mth).generics.type_param_defs()))
2994 pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> ast::Def {
2995 match tcx.def_map.borrow().find(&expr.id) {
2998 tcx.sess.span_bug(expr.span, format!(
2999 "no def-map entry for expr {:?}", expr.id));
3004 pub fn expr_is_lval(tcx: &ctxt, e: &ast::Expr) -> bool {
3005 match expr_kind(tcx, e) {
3007 RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
3011 /// We categorize expressions into three kinds. The distinction between
3012 /// lvalue/rvalue is fundamental to the language. The distinction between the
3013 /// two kinds of rvalues is an artifact of trans which reflects how we will
3014 /// generate code for that kind of expression. See trans/expr.rs for more
3023 pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
3024 if tcx.method_map.borrow().contains_key(&typeck::MethodCall::expr(expr.id)) {
3025 // Overloaded operations are generally calls, and hence they are
3026 // generated via DPS, but there are two exceptions:
3027 return match expr.node {
3028 // `a += b` has a unit result.
3029 ast::ExprAssignOp(..) => RvalueStmtExpr,
3031 // the deref method invoked for `*a` always yields an `&T`
3032 ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
3034 // in the general case, result could be any type, use DPS
3040 ast::ExprPath(..) => {
3041 match resolve_expr(tcx, expr) {
3042 ast::DefVariant(tid, vid, _) => {
3043 let variant_info = enum_variant_with_id(tcx, tid, vid);
3044 if variant_info.args.len() > 0u {
3053 ast::DefStruct(_) => {
3054 match get(expr_ty(tcx, expr)).sty {
3055 ty_bare_fn(..) => RvalueDatumExpr,
3060 // Fn pointers are just scalar values.
3061 ast::DefFn(..) | ast::DefStaticMethod(..) => RvalueDatumExpr,
3063 // Note: there is actually a good case to be made that
3064 // DefArg's, particularly those of immediate type, ought to
3065 // considered rvalues.
3066 ast::DefStatic(..) |
3067 ast::DefBinding(..) |
3070 ast::DefLocal(..) => LvalueExpr,
3073 tcx.sess.span_bug(expr.span, format!(
3074 "uncategorized def for expr {:?}: {:?}",
3080 ast::ExprUnary(ast::UnDeref, _) |
3081 ast::ExprField(..) |
3082 ast::ExprIndex(..) => {
3087 ast::ExprMethodCall(..) |
3088 ast::ExprStruct(..) |
3091 ast::ExprMatch(..) |
3092 ast::ExprFnBlock(..) |
3094 ast::ExprBlock(..) |
3095 ast::ExprRepeat(..) |
3096 ast::ExprVstore(_, ast::ExprVstoreSlice) |
3097 ast::ExprVstore(_, ast::ExprVstoreMutSlice) |
3098 ast::ExprVec(..) => {
3102 ast::ExprLit(lit) if lit_is_str(lit) => {
3106 ast::ExprCast(..) => {
3107 match tcx.node_types.borrow().find(&(expr.id as uint)) {
3109 if type_is_trait(t) {
3116 // Technically, it should not happen that the expr is not
3117 // present within the table. However, it DOES happen
3118 // during type check, because the final types from the
3119 // expressions are not yet recorded in the tcx. At that
3120 // time, though, we are only interested in knowing lvalue
3121 // vs rvalue. It would be better to base this decision on
3122 // the AST type in cast node---but (at the time of this
3123 // writing) it's not easy to distinguish casts to traits
3124 // from other casts based on the AST. This should be
3125 // easier in the future, when casts to traits
3126 // would like @Foo, Box<Foo>, or &Foo.
3132 ast::ExprBreak(..) |
3133 ast::ExprAgain(..) |
3135 ast::ExprWhile(..) |
3137 ast::ExprAssign(..) |
3138 ast::ExprInlineAsm(..) |
3139 ast::ExprAssignOp(..) => {
3143 ast::ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
3145 ast::ExprLit(_) | // Note: LitStr is carved out above
3146 ast::ExprUnary(..) |
3147 ast::ExprAddrOf(..) |
3148 ast::ExprBinary(..) |
3149 ast::ExprVstore(_, ast::ExprVstoreUniq) => {
3153 ast::ExprBox(place, _) => {
3154 // Special case `Box<T>` for now:
3155 let definition = match tcx.def_map.borrow().find(&place.id) {
3157 None => fail!("no def for place"),
3159 let def_id = ast_util::def_id_of_def(definition);
3160 match tcx.lang_items.items.get(ExchangeHeapLangItem as uint) {
3161 &Some(item_def_id) if def_id == item_def_id => {
3164 &Some(_) | &None => RvalueDpsExpr,
3168 ast::ExprParen(e) => expr_kind(tcx, e),
3170 ast::ExprMac(..) => {
3173 "macro expression remains after expansion");
3178 pub fn stmt_node_id(s: &ast::Stmt) -> ast::NodeId {
3180 ast::StmtDecl(_, id) | StmtExpr(_, id) | StmtSemi(_, id) => {
3183 ast::StmtMac(..) => fail!("unexpanded macro in trans")
3187 pub fn field_idx_strict(tcx: &ctxt, name: ast::Name, fields: &[field])
3190 for f in fields.iter() { if f.ident.name == name { return i; } i += 1u; }
3191 tcx.sess.bug(format!(
3192 "no field named `{}` found in the list of fields `{:?}`",
3193 token::get_name(name),
3195 .map(|f| token::get_ident(f.ident).get().to_strbuf())
3196 .collect::<Vec<StrBuf>>()));
3199 pub fn method_idx(id: ast::Ident, meths: &[Rc<Method>]) -> Option<uint> {
3200 meths.iter().position(|m| m.ident == id)
3203 /// Returns a vector containing the indices of all type parameters that appear
3204 /// in `ty`. The vector may contain duplicates. Probably should be converted
3205 /// to a bitset or some other representation.
3206 pub fn param_tys_in_type(ty: t) -> Vec<param_ty> {
3207 let mut rslt = Vec::new();
3219 pub fn ty_sort_str(cx: &ctxt, t: t) -> StrBuf {
3221 ty_nil | ty_bot | ty_bool | ty_char | ty_int(_) |
3222 ty_uint(_) | ty_float(_) | ty_str => {
3223 ::util::ppaux::ty_to_str(cx, t)
3226 ty_enum(id, _) => format_strbuf!("enum {}", item_path_str(cx, id)),
3227 ty_box(_) => "@-ptr".to_strbuf(),
3228 ty_uniq(_) => "box".to_strbuf(),
3229 ty_vec(_, _) => "vector".to_strbuf(),
3230 ty_ptr(_) => "*-ptr".to_strbuf(),
3231 ty_rptr(_, _) => "&-ptr".to_strbuf(),
3232 ty_bare_fn(_) => "extern fn".to_strbuf(),
3233 ty_closure(_) => "fn".to_strbuf(),
3234 ty_trait(ref inner) => {
3235 format_strbuf!("trait {}", item_path_str(cx, inner.def_id))
3237 ty_struct(id, _) => {
3238 format_strbuf!("struct {}", item_path_str(cx, id))
3240 ty_tup(_) => "tuple".to_strbuf(),
3241 ty_infer(TyVar(_)) => "inferred type".to_strbuf(),
3242 ty_infer(IntVar(_)) => "integral variable".to_strbuf(),
3243 ty_infer(FloatVar(_)) => "floating-point variable".to_strbuf(),
3244 ty_param(_) => "type parameter".to_strbuf(),
3245 ty_self(_) => "self".to_strbuf(),
3246 ty_err => "type error".to_strbuf(),
3250 pub fn type_err_to_str(cx: &ctxt, err: &type_err) -> StrBuf {
3253 * Explains the source of a type err in a short,
3254 * human readable way. This is meant to be placed in
3255 * parentheses after some larger message. You should
3256 * also invoke `note_and_explain_type_err()` afterwards
3257 * to present additional details, particularly when
3258 * it comes to lifetime-related errors. */
3260 fn tstore_to_closure(s: &TraitStore) -> StrBuf {
3262 &UniqTraitStore => "proc".to_strbuf(),
3263 &RegionTraitStore(..) => "closure".to_strbuf()
3268 terr_mismatch => "types differ".to_strbuf(),
3269 terr_fn_style_mismatch(values) => {
3270 format_strbuf!("expected {} fn but found {} fn",
3271 values.expected.to_str(),
3272 values.found.to_str())
3274 terr_abi_mismatch(values) => {
3275 format_strbuf!("expected {} fn but found {} fn",
3276 values.expected.to_str(),
3277 values.found.to_str())
3279 terr_onceness_mismatch(values) => {
3280 format_strbuf!("expected {} fn but found {} fn",
3281 values.expected.to_str(),
3282 values.found.to_str())
3284 terr_sigil_mismatch(values) => {
3285 format_strbuf!("expected {}, found {}",
3286 tstore_to_closure(&values.expected),
3287 tstore_to_closure(&values.found))
3289 terr_mutability => "values differ in mutability".to_strbuf(),
3290 terr_box_mutability => {
3291 "boxed values differ in mutability".to_strbuf()
3293 terr_vec_mutability => "vectors differ in mutability".to_strbuf(),
3294 terr_ptr_mutability => "pointers differ in mutability".to_strbuf(),
3295 terr_ref_mutability => "references differ in mutability".to_strbuf(),
3296 terr_ty_param_size(values) => {
3297 format_strbuf!("expected a type with {} type params \
3298 but found one with {} type params",
3302 terr_tuple_size(values) => {
3303 format_strbuf!("expected a tuple with {} elements \
3304 but found one with {} elements",
3308 terr_record_size(values) => {
3309 format_strbuf!("expected a record with {} fields \
3310 but found one with {} fields",
3314 terr_record_mutability => {
3315 "record elements differ in mutability".to_strbuf()
3317 terr_record_fields(values) => {
3318 format_strbuf!("expected a record with field `{}` but found one \
3320 token::get_ident(values.expected),
3321 token::get_ident(values.found))
3324 "incorrect number of function parameters".to_strbuf()
3326 terr_regions_does_not_outlive(..) => {
3327 "lifetime mismatch".to_strbuf()
3329 terr_regions_not_same(..) => {
3330 "lifetimes are not the same".to_strbuf()
3332 terr_regions_no_overlap(..) => {
3333 "lifetimes do not intersect".to_strbuf()
3335 terr_regions_insufficiently_polymorphic(br, _) => {
3336 format_strbuf!("expected bound lifetime parameter {}, \
3337 but found concrete lifetime",
3338 bound_region_ptr_to_str(cx, br))
3340 terr_regions_overly_polymorphic(br, _) => {
3341 format_strbuf!("expected concrete lifetime, \
3342 but found bound lifetime parameter {}",
3343 bound_region_ptr_to_str(cx, br))
3345 terr_trait_stores_differ(_, ref values) => {
3346 format_strbuf!("trait storage differs: expected `{}` but found \
3348 trait_store_to_str(cx, (*values).expected),
3349 trait_store_to_str(cx, (*values).found))
3351 terr_sorts(values) => {
3352 format_strbuf!("expected {} but found {}",
3353 ty_sort_str(cx, values.expected),
3354 ty_sort_str(cx, values.found))
3356 terr_traits(values) => {
3357 format_strbuf!("expected trait `{}` but found trait `{}`",
3358 item_path_str(cx, values.expected),
3359 item_path_str(cx, values.found))
3361 terr_builtin_bounds(values) => {
3362 if values.expected.is_empty() {
3363 format_strbuf!("expected no bounds but found `{}`",
3364 values.found.user_string(cx))
3365 } else if values.found.is_empty() {
3366 format_strbuf!("expected bounds `{}` but found no bounds",
3367 values.expected.user_string(cx))
3369 format_strbuf!("expected bounds `{}` but found bounds `{}`",
3370 values.expected.user_string(cx),
3371 values.found.user_string(cx))
3374 terr_integer_as_char => {
3375 "expected an integral type but found `char`".to_strbuf()
3377 terr_int_mismatch(ref values) => {
3378 format_strbuf!("expected `{}` but found `{}`",
3379 values.expected.to_str(),
3380 values.found.to_str())
3382 terr_float_mismatch(ref values) => {
3383 format_strbuf!("expected `{}` but found `{}`",
3384 values.expected.to_str(),
3385 values.found.to_str())
3387 terr_variadic_mismatch(ref values) => {
3388 format_strbuf!("expected {} fn but found {} function",
3389 if values.expected {
3403 pub fn note_and_explain_type_err(cx: &ctxt, err: &type_err) {
3405 terr_regions_does_not_outlive(subregion, superregion) => {
3406 note_and_explain_region(cx, "", subregion, "...");
3407 note_and_explain_region(cx, "...does not necessarily outlive ",
3410 terr_regions_not_same(region1, region2) => {
3411 note_and_explain_region(cx, "", region1, "...");
3412 note_and_explain_region(cx, "...is not the same lifetime as ",
3415 terr_regions_no_overlap(region1, region2) => {
3416 note_and_explain_region(cx, "", region1, "...");
3417 note_and_explain_region(cx, "...does not overlap ",
3420 terr_regions_insufficiently_polymorphic(_, conc_region) => {
3421 note_and_explain_region(cx,
3422 "concrete lifetime that was found is ",
3425 terr_regions_overly_polymorphic(_, conc_region) => {
3426 note_and_explain_region(cx,
3427 "expected concrete lifetime is ",
3434 pub fn provided_source(cx: &ctxt, id: ast::DefId) -> Option<ast::DefId> {
3435 cx.provided_method_sources.borrow().find(&id).map(|x| *x)
3438 pub fn provided_trait_methods(cx: &ctxt, id: ast::DefId) -> Vec<Rc<Method>> {
3440 match cx.map.find(id.node) {
3441 Some(ast_map::NodeItem(item)) => {
3443 ItemTrait(_, _, _, ref ms) => {
3444 let (_, p) = ast_util::split_trait_methods(ms.as_slice());
3445 p.iter().map(|m| method(cx, ast_util::local_def(m.id))).collect()
3447 _ => cx.sess.bug(format!("provided_trait_methods: `{}` is not a trait", id))
3450 _ => cx.sess.bug(format!("provided_trait_methods: `{}` is not a trait", id))
3453 csearch::get_provided_trait_methods(cx, id)
3457 pub fn trait_supertraits(cx: &ctxt, id: ast::DefId) -> Rc<Vec<Rc<TraitRef>>> {
3459 match cx.supertraits.borrow().find(&id) {
3460 Some(trait_refs) => { return trait_refs.clone(); }
3461 None => {} // Continue.
3464 // Not in the cache. It had better be in the metadata, which means it
3465 // shouldn't be local.
3466 assert!(!is_local(id));
3468 // Get the supertraits out of the metadata and create the
3469 // TraitRef for each.
3470 let result = Rc::new(csearch::get_supertraits(cx, id));
3471 cx.supertraits.borrow_mut().insert(id, result.clone());
3475 pub fn trait_ref_supertraits(cx: &ctxt, trait_ref: &ty::TraitRef) -> Vec<Rc<TraitRef>> {
3476 let supertrait_refs = trait_supertraits(cx, trait_ref.def_id);
3477 supertrait_refs.iter().map(
3478 |supertrait_ref| supertrait_ref.subst(cx, &trait_ref.substs)).collect()
3481 fn lookup_locally_or_in_crate_store<V:Clone>(
3484 map: &mut DefIdMap<V>,
3485 load_external: || -> V) -> V {
3487 * Helper for looking things up in the various maps
3488 * that are populated during typeck::collect (e.g.,
3489 * `cx.methods`, `cx.tcache`, etc). All of these share
3490 * the pattern that if the id is local, it should have
3491 * been loaded into the map by the `typeck::collect` phase.
3492 * If the def-id is external, then we have to go consult
3493 * the crate loading code (and cache the result for the future).
3496 match map.find_copy(&def_id) {
3497 Some(v) => { return v; }
3501 if def_id.krate == ast::LOCAL_CRATE {
3502 fail!("No def'n found for {:?} in tcx.{}", def_id, descr);
3504 let v = load_external();
3505 map.insert(def_id, v.clone());
3509 pub fn trait_method(cx: &ctxt, trait_did: ast::DefId, idx: uint) -> Rc<Method> {
3510 let method_def_id = *ty::trait_method_def_ids(cx, trait_did).get(idx);
3511 ty::method(cx, method_def_id)
3515 pub fn trait_methods(cx: &ctxt, trait_did: ast::DefId) -> Rc<Vec<Rc<Method>>> {
3516 let mut trait_methods = cx.trait_methods_cache.borrow_mut();
3517 match trait_methods.find_copy(&trait_did) {
3518 Some(methods) => methods,
3520 let def_ids = ty::trait_method_def_ids(cx, trait_did);
3521 let methods: Rc<Vec<Rc<Method>>> = Rc::new(def_ids.iter().map(|d| {
3524 trait_methods.insert(trait_did, methods.clone());
3530 pub fn method(cx: &ctxt, id: ast::DefId) -> Rc<Method> {
3531 lookup_locally_or_in_crate_store("methods", id,
3532 &mut *cx.methods.borrow_mut(), || {
3533 Rc::new(csearch::get_method(cx, id))
3537 pub fn trait_method_def_ids(cx: &ctxt, id: ast::DefId) -> Rc<Vec<DefId>> {
3538 lookup_locally_or_in_crate_store("trait_method_def_ids",
3540 &mut *cx.trait_method_def_ids.borrow_mut(),
3542 Rc::new(csearch::get_trait_method_def_ids(&cx.sess.cstore, id))
3546 pub fn impl_trait_ref(cx: &ctxt, id: ast::DefId) -> Option<Rc<TraitRef>> {
3547 match cx.impl_trait_cache.borrow().find(&id) {
3548 Some(ret) => { return ret.clone(); }
3552 let ret = if id.krate == ast::LOCAL_CRATE {
3553 debug!("(impl_trait_ref) searching for trait impl {:?}", id);
3554 match cx.map.find(id.node) {
3555 Some(ast_map::NodeItem(item)) => {
3557 ast::ItemImpl(_, ref opt_trait, _, _) => {
3560 Some(ty::node_id_to_trait_ref(cx, t.ref_id))
3571 csearch::get_impl_trait(cx, id)
3574 cx.impl_trait_cache.borrow_mut().insert(id, ret.clone());
3578 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
3579 let def = *tcx.def_map.borrow()
3581 .expect("no def-map entry for trait");
3582 ast_util::def_id_of_def(def)
3585 pub fn try_add_builtin_trait(tcx: &ctxt,
3586 trait_def_id: ast::DefId,
3587 builtin_bounds: &mut BuiltinBounds) -> bool {
3588 //! Checks whether `trait_ref` refers to one of the builtin
3589 //! traits, like `Send`, and adds the corresponding
3590 //! bound to the set `builtin_bounds` if so. Returns true if `trait_ref`
3591 //! is a builtin trait.
3593 match tcx.lang_items.to_builtin_kind(trait_def_id) {
3594 Some(bound) => { builtin_bounds.add(bound); true }
3599 pub fn ty_to_def_id(ty: t) -> Option<ast::DefId> {
3601 ty_trait(box TyTrait { def_id: id, .. }) |
3603 ty_enum(id, _) => Some(id),
3610 pub struct VariantInfo {
3612 pub arg_names: Option<Vec<ast::Ident> >,
3614 pub name: ast::Ident,
3622 /// Creates a new VariantInfo from the corresponding ast representation.
3624 /// Does not do any caching of the value in the type context.
3625 pub fn from_ast_variant(cx: &ctxt,
3626 ast_variant: &ast::Variant,
3627 discriminant: Disr) -> VariantInfo {
3628 let ctor_ty = node_id_to_type(cx, ast_variant.node.id);
3630 match ast_variant.node.kind {
3631 ast::TupleVariantKind(ref args) => {
3632 let arg_tys = if args.len() > 0 {
3633 ty_fn_args(ctor_ty).iter().map(|a| *a).collect()
3638 return VariantInfo {
3642 name: ast_variant.node.name,
3643 id: ast_util::local_def(ast_variant.node.id),
3644 disr_val: discriminant,
3645 vis: ast_variant.node.vis
3648 ast::StructVariantKind(ref struct_def) => {
3650 let fields: &[StructField] = struct_def.fields.as_slice();
3652 assert!(fields.len() > 0);
3654 let arg_tys = ty_fn_args(ctor_ty).iter().map(|a| *a).collect();
3655 let arg_names = fields.iter().map(|field| {
3656 match field.node.kind {
3657 NamedField(ident, _) => ident,
3658 UnnamedField(..) => cx.sess.bug(
3659 "enum_variants: all fields in struct must have a name")
3663 return VariantInfo {
3665 arg_names: Some(arg_names),
3667 name: ast_variant.node.name,
3668 id: ast_util::local_def(ast_variant.node.id),
3669 disr_val: discriminant,
3670 vis: ast_variant.node.vis
3677 pub fn substd_enum_variants(cx: &ctxt,
3680 -> Vec<Rc<VariantInfo>> {
3681 enum_variants(cx, id).iter().map(|variant_info| {
3682 let substd_args = variant_info.args.iter()
3683 .map(|aty| subst(cx, substs, *aty)).collect();
3685 let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
3687 Rc::new(VariantInfo {
3689 ctor_ty: substd_ctor_ty,
3690 ..(**variant_info).clone()
3695 pub fn item_path_str(cx: &ctxt, id: ast::DefId) -> StrBuf {
3696 with_path(cx, id, |path| ast_map::path_to_str(path)).to_strbuf()
3701 TraitDtor(DefId, bool)
3705 pub fn is_not_present(&self) -> bool {
3712 pub fn is_present(&self) -> bool {
3713 !self.is_not_present()
3716 pub fn has_drop_flag(&self) -> bool {
3719 &TraitDtor(_, flag) => flag
3724 /* If struct_id names a struct with a dtor, return Some(the dtor's id).
3725 Otherwise return none. */
3726 pub fn ty_dtor(cx: &ctxt, struct_id: DefId) -> DtorKind {
3727 match cx.destructor_for_type.borrow().find(&struct_id) {
3728 Some(&method_def_id) => {
3729 let flag = !has_attr(cx, struct_id, "unsafe_no_drop_flag");
3731 TraitDtor(method_def_id, flag)
3737 pub fn has_dtor(cx: &ctxt, struct_id: DefId) -> bool {
3738 ty_dtor(cx, struct_id).is_present()
3741 pub fn with_path<T>(cx: &ctxt, id: ast::DefId, f: |ast_map::PathElems| -> T) -> T {
3742 if id.krate == ast::LOCAL_CRATE {
3743 cx.map.with_path(id.node, f)
3745 f(ast_map::Values(csearch::get_item_path(cx, id).iter()).chain(None))
3749 pub fn enum_is_univariant(cx: &ctxt, id: ast::DefId) -> bool {
3750 enum_variants(cx, id).len() == 1
3753 pub fn type_is_empty(cx: &ctxt, t: t) -> bool {
3754 match ty::get(t).sty {
3755 ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
3760 pub fn enum_variants(cx: &ctxt, id: ast::DefId) -> Rc<Vec<Rc<VariantInfo>>> {
3761 match cx.enum_var_cache.borrow().find(&id) {
3762 Some(variants) => return variants.clone(),
3763 _ => { /* fallthrough */ }
3766 let result = if ast::LOCAL_CRATE != id.krate {
3767 Rc::new(csearch::get_enum_variants(cx, id))
3770 Although both this code and check_enum_variants in typeck/check
3771 call eval_const_expr, it should never get called twice for the same
3772 expr, since check_enum_variants also updates the enum_var_cache
3774 match cx.map.get(id.node) {
3775 ast_map::NodeItem(item) => {
3777 ast::ItemEnum(ref enum_definition, _) => {
3778 let mut last_discriminant: Option<Disr> = None;
3779 Rc::new(enum_definition.variants.iter().map(|&variant| {
3781 let mut discriminant = match last_discriminant {
3782 Some(val) => val + 1,
3783 None => INITIAL_DISCRIMINANT_VALUE
3786 match variant.node.disr_expr {
3787 Some(e) => match const_eval::eval_const_expr_partial(cx, e) {
3788 Ok(const_eval::const_int(val)) => {
3789 discriminant = val as Disr
3791 Ok(const_eval::const_uint(val)) => {
3792 discriminant = val as Disr
3797 "expected signed integer constant");
3802 format!("expected constant: {}",
3809 last_discriminant = Some(discriminant);
3810 Rc::new(VariantInfo::from_ast_variant(cx, variant,
3815 cx.sess.bug("enum_variants: id not bound to an enum")
3819 _ => cx.sess.bug("enum_variants: id not bound to an enum")
3823 cx.enum_var_cache.borrow_mut().insert(id, result.clone());
3828 // Returns information about the enum variant with the given ID:
3829 pub fn enum_variant_with_id(cx: &ctxt,
3830 enum_id: ast::DefId,
3831 variant_id: ast::DefId)
3832 -> Rc<VariantInfo> {
3833 enum_variants(cx, enum_id).iter()
3834 .find(|variant| variant.id == variant_id)
3835 .expect("enum_variant_with_id(): no variant exists with that ID")
3840 // If the given item is in an external crate, looks up its type and adds it to
3841 // the type cache. Returns the type parameters and type.
3842 pub fn lookup_item_type(cx: &ctxt,
3844 -> ty_param_bounds_and_ty {
3845 lookup_locally_or_in_crate_store(
3846 "tcache", did, &mut *cx.tcache.borrow_mut(),
3847 || csearch::get_type(cx, did))
3850 pub fn lookup_impl_vtables(cx: &ctxt,
3852 -> typeck::impl_res {
3853 lookup_locally_or_in_crate_store(
3854 "impl_vtables", did, &mut *cx.impl_vtables.borrow_mut(),
3855 || csearch::get_impl_vtables(cx, did) )
3858 /// Given the did of a trait, returns its canonical trait ref.
3859 pub fn lookup_trait_def(cx: &ctxt, did: ast::DefId) -> Rc<ty::TraitDef> {
3860 let mut trait_defs = cx.trait_defs.borrow_mut();
3861 match trait_defs.find_copy(&did) {
3862 Some(trait_def) => {
3863 // The item is in this crate. The caller should have added it to the
3864 // type cache already
3868 assert!(did.krate != ast::LOCAL_CRATE);
3869 let trait_def = Rc::new(csearch::get_trait_def(cx, did));
3870 trait_defs.insert(did, trait_def.clone());
3876 /// Iterate over meta_items of a definition.
3877 // (This should really be an iterator, but that would require csearch and
3878 // decoder to use iterators instead of higher-order functions.)
3879 pub fn each_attr(tcx: &ctxt, did: DefId, f: |@ast::MetaItem| -> bool) -> bool {
3881 let item = tcx.map.expect_item(did.node);
3882 item.attrs.iter().advance(|attr| f(attr.node.value))
3884 let mut cont = true;
3885 csearch::get_item_attrs(&tcx.sess.cstore, did, |meta_items| {
3887 cont = meta_items.iter().advance(|ptrptr| f(*ptrptr));
3894 /// Determine whether an item is annotated with an attribute
3895 pub fn has_attr(tcx: &ctxt, did: DefId, attr: &str) -> bool {
3896 let mut found = false;
3897 each_attr(tcx, did, |item| {
3898 if item.name().equiv(&attr) {
3908 /// Determine whether an item is annotated with `#[packed]`
3909 pub fn lookup_packed(tcx: &ctxt, did: DefId) -> bool {
3910 has_attr(tcx, did, "packed")
3913 /// Determine whether an item is annotated with `#[simd]`
3914 pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
3915 has_attr(tcx, did, "simd")
3918 // Obtain the representation annotation for a definition.
3919 pub fn lookup_repr_hint(tcx: &ctxt, did: DefId) -> attr::ReprAttr {
3920 let mut acc = attr::ReprAny;
3921 ty::each_attr(tcx, did, |meta| {
3922 acc = attr::find_repr_attr(tcx.sess.diagnostic(), meta, acc);
3928 // Look up a field ID, whether or not it's local
3929 // Takes a list of type substs in case the struct is generic
3930 pub fn lookup_field_type(tcx: &ctxt,
3935 let t = if id.krate == ast::LOCAL_CRATE {
3936 node_id_to_type(tcx, id.node)
3938 let mut tcache = tcx.tcache.borrow_mut();
3939 match tcache.find(&id) {
3940 Some(&ty_param_bounds_and_ty {ty, ..}) => ty,
3942 let tpt = csearch::get_field_type(tcx, struct_id, id);
3943 tcache.insert(id, tpt.clone());
3948 subst(tcx, substs, t)
3951 // Lookup all ancestor structs of a struct indicated by did. That is the reflexive,
3952 // transitive closure of doing a single lookup in cx.superstructs.
3953 fn each_super_struct(cx: &ctxt, mut did: ast::DefId, f: |ast::DefId|) {
3954 let superstructs = cx.superstructs.borrow();
3958 match superstructs.find(&did) {
3959 Some(&Some(def_id)) => {
3962 Some(&None) => break,
3965 format!("ID not mapped to super-struct: {}",
3966 cx.map.node_to_str(did.node)));
3972 // Look up the list of field names and IDs for a given struct.
3973 // Fails if the id is not bound to a struct.
3974 pub fn lookup_struct_fields(cx: &ctxt, did: ast::DefId) -> Vec<field_ty> {
3975 if did.krate == ast::LOCAL_CRATE {
3976 // We store the fields which are syntactically in each struct in cx. So
3977 // we have to walk the inheritance chain of the struct to get all the
3978 // structs (explicit and inherited) for a struct. If this is expensive
3979 // we could cache the whole list of fields here.
3980 let struct_fields = cx.struct_fields.borrow();
3981 let mut results: SmallVector<&[field_ty]> = SmallVector::zero();
3982 each_super_struct(cx, did, |s| {
3983 match struct_fields.find(&s) {
3984 Some(fields) => results.push(fields.as_slice()),
3987 format!("ID not mapped to struct fields: {}",
3988 cx.map.node_to_str(did.node)));
3993 let len = results.as_slice().iter().map(|x| x.len()).sum();
3994 let mut result: Vec<field_ty> = Vec::with_capacity(len);
3995 result.extend(results.as_slice().iter().flat_map(|rs| rs.iter().map(|&f| f)));
3996 assert!(result.len() == len);
3999 csearch::get_struct_fields(&cx.sess.cstore, did)
4003 pub fn lookup_struct_field(cx: &ctxt,
4005 field_id: ast::DefId)
4007 let r = lookup_struct_fields(cx, parent);
4008 match r.iter().find(|f| f.id.node == field_id.node) {
4010 None => cx.sess.bug("struct ID not found in parent's fields")
4014 // Returns a list of fields corresponding to the struct's items. trans uses
4015 // this. Takes a list of substs with which to instantiate field types.
4016 pub fn struct_fields(cx: &ctxt, did: ast::DefId, substs: &substs)
4018 lookup_struct_fields(cx, did).iter().map(|f| {
4020 // FIXME #6993: change type of field to Name and get rid of new()
4021 ident: ast::Ident::new(f.name),
4023 ty: lookup_field_type(cx, did, f.id, substs),
4030 pub fn is_binopable(cx: &ctxt, ty: t, op: ast::BinOp) -> bool {
4031 static tycat_other: int = 0;
4032 static tycat_bool: int = 1;
4033 static tycat_char: int = 2;
4034 static tycat_int: int = 3;
4035 static tycat_float: int = 4;
4036 static tycat_bot: int = 5;
4037 static tycat_raw_ptr: int = 6;
4039 static opcat_add: int = 0;
4040 static opcat_sub: int = 1;
4041 static opcat_mult: int = 2;
4042 static opcat_shift: int = 3;
4043 static opcat_rel: int = 4;
4044 static opcat_eq: int = 5;
4045 static opcat_bit: int = 6;
4046 static opcat_logic: int = 7;
4047 static opcat_mod: int = 8;
4049 fn opcat(op: ast::BinOp) -> int {
4051 ast::BiAdd => opcat_add,
4052 ast::BiSub => opcat_sub,
4053 ast::BiMul => opcat_mult,
4054 ast::BiDiv => opcat_mult,
4055 ast::BiRem => opcat_mod,
4056 ast::BiAnd => opcat_logic,
4057 ast::BiOr => opcat_logic,
4058 ast::BiBitXor => opcat_bit,
4059 ast::BiBitAnd => opcat_bit,
4060 ast::BiBitOr => opcat_bit,
4061 ast::BiShl => opcat_shift,
4062 ast::BiShr => opcat_shift,
4063 ast::BiEq => opcat_eq,
4064 ast::BiNe => opcat_eq,
4065 ast::BiLt => opcat_rel,
4066 ast::BiLe => opcat_rel,
4067 ast::BiGe => opcat_rel,
4068 ast::BiGt => opcat_rel
4072 fn tycat(cx: &ctxt, ty: t) -> int {
4073 if type_is_simd(cx, ty) {
4074 return tycat(cx, simd_type(cx, ty))
4077 ty_char => tycat_char,
4078 ty_bool => tycat_bool,
4079 ty_int(_) | ty_uint(_) | ty_infer(IntVar(_)) => tycat_int,
4080 ty_float(_) | ty_infer(FloatVar(_)) => tycat_float,
4081 ty_bot => tycat_bot,
4082 ty_ptr(_) => tycat_raw_ptr,
4087 static t: bool = true;
4088 static f: bool = false;
4091 // +, -, *, shift, rel, ==, bit, logic, mod
4092 /*other*/ [f, f, f, f, f, f, f, f, f],
4093 /*bool*/ [f, f, f, f, t, t, t, t, f],
4094 /*char*/ [f, f, f, f, t, t, f, f, f],
4095 /*int*/ [t, t, t, t, t, t, t, f, t],
4096 /*float*/ [t, t, t, f, t, t, f, f, f],
4097 /*bot*/ [t, t, t, t, t, t, t, t, t],
4098 /*raw ptr*/ [f, f, f, f, t, t, f, f, f]];
4100 return tbl[tycat(cx, ty) as uint ][opcat(op) as uint];
4103 /// Returns an equivalent type with all the typedefs and self regions removed.
4104 pub fn normalize_ty(cx: &ctxt, t: t) -> t {
4105 let u = TypeNormalizer(cx).fold_ty(t);
4108 struct TypeNormalizer<'a>(&'a ctxt);
4110 impl<'a> TypeFolder for TypeNormalizer<'a> {
4111 fn tcx<'a>(&'a self) -> &'a ctxt { let TypeNormalizer(c) = *self; c }
4113 fn fold_ty(&mut self, t: ty::t) -> ty::t {
4114 match self.tcx().normalized_cache.borrow().find_copy(&t) {
4119 let t_norm = ty_fold::super_fold_ty(self, t);
4120 self.tcx().normalized_cache.borrow_mut().insert(t, t_norm);
4124 fn fold_region(&mut self, _: ty::Region) -> ty::Region {
4128 fn fold_substs(&mut self,
4131 substs { regions: ErasedRegions,
4132 self_ty: substs.self_ty.fold_with(self),
4133 tps: substs.tps.fold_with(self) }
4136 fn fold_sig(&mut self,
4139 // The binder-id is only relevant to bound regions, which
4140 // are erased at trans time.
4142 binder_id: ast::DUMMY_NODE_ID,
4143 inputs: sig.inputs.fold_with(self),
4144 output: sig.output.fold_with(self),
4145 variadic: sig.variadic,
4151 pub trait ExprTyProvider {
4152 fn expr_ty(&self, ex: &ast::Expr) -> t;
4153 fn ty_ctxt<'a>(&'a self) -> &'a ctxt;
4156 impl ExprTyProvider for ctxt {
4157 fn expr_ty(&self, ex: &ast::Expr) -> t {
4161 fn ty_ctxt<'a>(&'a self) -> &'a ctxt {
4166 // Returns the repeat count for a repeating vector expression.
4167 pub fn eval_repeat_count<T: ExprTyProvider>(tcx: &T, count_expr: &ast::Expr) -> uint {
4168 match const_eval::eval_const_expr_partial(tcx, count_expr) {
4169 Ok(ref const_val) => match *const_val {
4170 const_eval::const_int(count) => if count < 0 {
4171 tcx.ty_ctxt().sess.span_err(count_expr.span,
4172 "expected positive integer for \
4173 repeat count but found negative integer");
4176 return count as uint
4178 const_eval::const_uint(count) => return count as uint,
4179 const_eval::const_float(count) => {
4180 tcx.ty_ctxt().sess.span_err(count_expr.span,
4181 "expected positive integer for \
4182 repeat count but found float");
4183 return count as uint;
4185 const_eval::const_str(_) => {
4186 tcx.ty_ctxt().sess.span_err(count_expr.span,
4187 "expected positive integer for \
4188 repeat count but found string");
4191 const_eval::const_bool(_) => {
4192 tcx.ty_ctxt().sess.span_err(count_expr.span,
4193 "expected positive integer for \
4194 repeat count but found boolean");
4197 const_eval::const_binary(_) => {
4198 tcx.ty_ctxt().sess.span_err(count_expr.span,
4199 "expected positive integer for \
4200 repeat count but found binary array");
4205 tcx.ty_ctxt().sess.span_err(count_expr.span,
4206 "expected constant integer for repeat count \
4207 but found variable");
4213 // Iterate over a type parameter's bounded traits and any supertraits
4214 // of those traits, ignoring kinds.
4215 // Here, the supertraits are the transitive closure of the supertrait
4216 // relation on the supertraits from each bounded trait's constraint
4218 pub fn each_bound_trait_and_supertraits(tcx: &ctxt,
4219 bounds: &[Rc<TraitRef>],
4220 f: |Rc<TraitRef>| -> bool)
4222 for bound_trait_ref in bounds.iter() {
4223 let mut supertrait_set = HashMap::new();
4224 let mut trait_refs = Vec::new();
4227 // Seed the worklist with the trait from the bound
4228 supertrait_set.insert(bound_trait_ref.def_id, ());
4229 trait_refs.push(bound_trait_ref.clone());
4231 // Add the given trait ty to the hash map
4232 while i < trait_refs.len() {
4233 debug!("each_bound_trait_and_supertraits(i={:?}, trait_ref={})",
4234 i, trait_refs.get(i).repr(tcx));
4236 if !f(trait_refs.get(i).clone()) {
4240 // Add supertraits to supertrait_set
4241 let supertrait_refs = trait_ref_supertraits(tcx,
4242 &**trait_refs.get(i));
4243 for supertrait_ref in supertrait_refs.iter() {
4244 debug!("each_bound_trait_and_supertraits(supertrait_ref={})",
4245 supertrait_ref.repr(tcx));
4247 let d_id = supertrait_ref.def_id;
4248 if !supertrait_set.contains_key(&d_id) {
4249 // FIXME(#5527) Could have same trait multiple times
4250 supertrait_set.insert(d_id, ());
4251 trait_refs.push(supertrait_ref.clone());
4261 pub fn get_tydesc_ty(tcx: &ctxt) -> Result<t, StrBuf> {
4262 tcx.lang_items.require(TyDescStructLangItem).map(|tydesc_lang_item| {
4263 tcx.intrinsic_defs.borrow().find_copy(&tydesc_lang_item)
4264 .expect("Failed to resolve TyDesc")
4268 pub fn get_opaque_ty(tcx: &ctxt) -> Result<t, StrBuf> {
4269 tcx.lang_items.require(OpaqueStructLangItem).map(|opaque_lang_item| {
4270 tcx.intrinsic_defs.borrow().find_copy(&opaque_lang_item)
4271 .expect("Failed to resolve Opaque")
4275 pub fn visitor_object_ty(tcx: &ctxt,
4276 region: ty::Region) -> Result<(Rc<TraitRef>, t), StrBuf> {
4277 let trait_lang_item = match tcx.lang_items.require(TyVisitorTraitLangItem) {
4279 Err(s) => { return Err(s); }
4281 let substs = substs {
4282 regions: ty::NonerasedRegions(OwnedSlice::empty()),
4286 let trait_ref = Rc::new(TraitRef { def_id: trait_lang_item, substs: substs });
4287 Ok((trait_ref.clone(),
4290 trait_ref.substs.clone(),
4291 RegionTraitStore(region, ast::MutMutable),
4292 EmptyBuiltinBounds())))
4295 pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
4296 lookup_locally_or_in_crate_store(
4297 "item_variance_map", item_id, &mut *tcx.item_variance_map.borrow_mut(),
4298 || Rc::new(csearch::get_item_variances(&tcx.sess.cstore, item_id)))
4301 /// Records a trait-to-implementation mapping.
4302 pub fn record_trait_implementation(tcx: &ctxt,
4303 trait_def_id: DefId,
4304 impl_def_id: DefId) {
4305 match tcx.trait_impls.borrow().find(&trait_def_id) {
4306 Some(impls_for_trait) => {
4307 impls_for_trait.borrow_mut().push(impl_def_id);
4312 tcx.trait_impls.borrow_mut().insert(trait_def_id, Rc::new(RefCell::new(vec!(impl_def_id))));
4315 /// Populates the type context with all the implementations for the given type
4317 pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
4318 type_id: ast::DefId) {
4319 if type_id.krate == LOCAL_CRATE {
4322 if tcx.populated_external_types.borrow().contains(&type_id) {
4326 csearch::each_implementation_for_type(&tcx.sess.cstore, type_id,
4328 let methods = csearch::get_impl_methods(&tcx.sess.cstore, impl_def_id);
4330 // Record the trait->implementation mappings, if applicable.
4331 let associated_traits = csearch::get_impl_trait(tcx, impl_def_id);
4332 for trait_ref in associated_traits.iter() {
4333 record_trait_implementation(tcx, trait_ref.def_id, impl_def_id);
4336 // For any methods that use a default implementation, add them to
4337 // the map. This is a bit unfortunate.
4338 for &method_def_id in methods.iter() {
4339 for &source in ty::method(tcx, method_def_id).provided_source.iter() {
4340 tcx.provided_method_sources.borrow_mut().insert(method_def_id, source);
4344 // Store the implementation info.
4345 tcx.impl_methods.borrow_mut().insert(impl_def_id, methods);
4347 // If this is an inherent implementation, record it.
4348 if associated_traits.is_none() {
4349 match tcx.inherent_impls.borrow().find(&type_id) {
4350 Some(implementation_list) => {
4351 implementation_list.borrow_mut().push(impl_def_id);
4356 tcx.inherent_impls.borrow_mut().insert(type_id,
4357 Rc::new(RefCell::new(vec!(impl_def_id))));
4361 tcx.populated_external_types.borrow_mut().insert(type_id);
4364 /// Populates the type context with all the implementations for the given
4365 /// trait if necessary.
4366 pub fn populate_implementations_for_trait_if_necessary(
4368 trait_id: ast::DefId) {
4369 if trait_id.krate == LOCAL_CRATE {
4372 if tcx.populated_external_traits.borrow().contains(&trait_id) {
4376 csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id,
4377 |implementation_def_id| {
4378 let methods = csearch::get_impl_methods(&tcx.sess.cstore, implementation_def_id);
4380 // Record the trait->implementation mapping.
4381 record_trait_implementation(tcx, trait_id, implementation_def_id);
4383 // For any methods that use a default implementation, add them to
4384 // the map. This is a bit unfortunate.
4385 for &method_def_id in methods.iter() {
4386 for &source in ty::method(tcx, method_def_id).provided_source.iter() {
4387 tcx.provided_method_sources.borrow_mut().insert(method_def_id, source);
4391 // Store the implementation info.
4392 tcx.impl_methods.borrow_mut().insert(implementation_def_id, methods);
4395 tcx.populated_external_traits.borrow_mut().insert(trait_id);
4398 /// Given the def_id of an impl, return the def_id of the trait it implements.
4399 /// If it implements no trait, return `None`.
4400 pub fn trait_id_of_impl(tcx: &ctxt,
4401 def_id: ast::DefId) -> Option<ast::DefId> {
4402 let node = match tcx.map.find(def_id.node) {
4407 ast_map::NodeItem(item) => {
4409 ast::ItemImpl(_, Some(ref trait_ref), _, _) => {
4410 Some(node_id_to_trait_ref(tcx, trait_ref.ref_id).def_id)
4419 /// If the given def ID describes a method belonging to a trait (either a
4420 /// default method or an implementation of a trait method), return the ID of
4421 /// the trait that the method belongs to. Otherwise, return `None`.
4422 pub fn trait_of_method(tcx: &ctxt, def_id: ast::DefId)
4423 -> Option<ast::DefId> {
4424 if def_id.krate != LOCAL_CRATE {
4425 return csearch::get_trait_of_method(&tcx.sess.cstore, def_id, tcx);
4427 match tcx.methods.borrow().find_copy(&def_id) {
4429 match method.container {
4430 TraitContainer(def_id) => Some(def_id),
4431 ImplContainer(def_id) => trait_id_of_impl(tcx, def_id),
4438 /// If the given def ID describes a method belonging to a trait, (either a
4439 /// default method or an implementation of a trait method), return the ID of
4440 /// the method inside trait definition (this means that if the given def ID
4441 /// is already that of the original trait method, then the return value is
4443 /// Otherwise, return `None`.
4444 pub fn trait_method_of_method(tcx: &ctxt,
4445 def_id: ast::DefId) -> Option<ast::DefId> {
4446 let method = match tcx.methods.borrow().find(&def_id) {
4447 Some(m) => m.clone(),
4448 None => return None,
4450 let name = method.ident.name;
4451 match trait_of_method(tcx, def_id) {
4452 Some(trait_did) => {
4453 let trait_methods = ty::trait_methods(tcx, trait_did);
4454 trait_methods.iter()
4455 .position(|m| m.ident.name == name)
4456 .map(|idx| ty::trait_method(tcx, trait_did, idx).def_id)
4462 /// Creates a hash of the type `t` which will be the same no matter what crate
4463 /// context it's calculated within. This is used by the `type_id` intrinsic.
4464 pub fn hash_crate_independent(tcx: &ctxt, t: t, svh: &Svh) -> u64 {
4465 let mut state = sip::SipState::new();
4466 macro_rules! byte( ($b:expr) => { ($b as u8).hash(&mut state) } );
4467 macro_rules! hash( ($e:expr) => { $e.hash(&mut state) } );
4469 let region = |_state: &mut sip::SipState, r: Region| {
4479 tcx.sess.bug("non-static region found when hashing a type")
4483 let did = |state: &mut sip::SipState, did: DefId| {
4484 let h = if ast_util::is_local(did) {
4487 tcx.sess.cstore.get_crate_hash(did.krate)
4489 h.as_str().hash(state);
4490 did.node.hash(state);
4492 let mt = |state: &mut sip::SipState, mt: mt| {
4493 mt.mutbl.hash(state);
4495 ty::walk_ty(t, |t| {
4496 match ty::get(t).sty {
4499 ty_bool => byte!(2),
4500 ty_char => byte!(3),
4526 ty_vec(m, Some(_)) => {
4529 1u8.hash(&mut state);
4531 ty_vec(m, None) => {
4534 0u8.hash(&mut state);
4542 region(&mut state, r);
4545 ty_bare_fn(ref b) => {
4550 ty_closure(ref c) => {
4556 UniqTraitStore => byte!(0),
4557 RegionTraitStore(r, m) => {
4559 region(&mut state, r);
4560 assert_eq!(m, ast::MutMutable);
4564 ty_trait(box ty::TyTrait { def_id: d, store, bounds, .. }) => {
4568 UniqTraitStore => byte!(0),
4569 RegionTraitStore(r, m) => {
4571 region(&mut state, r);
4577 ty_struct(d, _) => {
4581 ty_tup(ref inner) => {
4588 did(&mut state, p.def_id);
4594 ty_infer(_) => unreachable!(),
4595 ty_err => byte!(23),
4603 pub fn to_str(self) -> &'static str {
4606 Contravariant => "-",
4613 pub fn construct_parameter_environment(
4615 self_bound: Option<Rc<TraitRef>>,
4616 item_type_params: &[TypeParameterDef],
4617 method_type_params: &[TypeParameterDef],
4618 item_region_params: &[RegionParameterDef],
4619 method_region_params: &[RegionParameterDef],
4620 free_id: ast::NodeId)
4621 -> ParameterEnvironment
4623 /*! See `ParameterEnvironment` struct def'n for details */
4626 // Construct the free substs.
4630 let self_ty = self_bound.as_ref().map(|t| ty::mk_self(tcx, t.def_id));
4633 let num_item_type_params = item_type_params.len();
4634 let num_method_type_params = method_type_params.len();
4635 let num_type_params = num_item_type_params + num_method_type_params;
4636 let type_params = Vec::from_fn(num_type_params, |i| {
4637 let def_id = if i < num_item_type_params {
4638 item_type_params[i].def_id
4640 method_type_params[i - num_item_type_params].def_id
4643 ty::mk_param(tcx, i, def_id)
4646 // map bound 'a => free 'a
4647 let region_params = {
4648 fn push_region_params(mut accum: Vec<ty::Region>,
4649 free_id: ast::NodeId,
4650 region_params: &[RegionParameterDef])
4651 -> Vec<ty::Region> {
4652 for r in region_params.iter() {
4654 ty::ReFree(ty::FreeRegion {
4656 bound_region: ty::BrNamed(r.def_id, r.name)}));
4661 let t = push_region_params(vec!(), free_id, item_region_params);
4662 push_region_params(t, free_id, method_region_params)
4665 let free_substs = substs {
4668 regions: ty::NonerasedRegions(OwnedSlice::from_vec(region_params))
4672 // Compute the bounds on Self and the type parameters.
4675 let self_bound_substd = self_bound.map(|b| b.subst(tcx, &free_substs));
4676 let type_param_bounds_substd = Vec::from_fn(num_type_params, |i| {
4677 if i < num_item_type_params {
4678 (*item_type_params[i].bounds).subst(tcx, &free_substs)
4680 let j = i - num_item_type_params;
4681 (*method_type_params[j].bounds).subst(tcx, &free_substs)
4685 debug!("construct_parameter_environment: free_id={} \
4687 self_param_bound={} \
4688 type_param_bound={}",
4690 free_substs.repr(tcx),
4691 self_bound_substd.repr(tcx),
4692 type_param_bounds_substd.repr(tcx));
4694 ty::ParameterEnvironment {
4695 free_substs: free_substs,
4696 self_param_bound: self_bound_substd,
4697 type_param_bounds: type_param_bounds_substd,
4702 pub fn empty() -> substs {
4706 regions: NonerasedRegions(OwnedSlice::empty())
4712 pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
4714 ast::MutMutable => MutBorrow,
4715 ast::MutImmutable => ImmBorrow,
4719 pub fn to_user_str(&self) -> &'static str {
4721 MutBorrow => "mutable",
4722 ImmBorrow => "immutable",
4723 UniqueImmBorrow => "uniquely immutable",
4728 impl mc::Typer for ty::ctxt {
4729 fn tcx<'a>(&'a self) -> &'a ty::ctxt {
4733 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<ty::t> {
4734 Ok(ty::node_id_to_type(self, id))
4737 fn node_method_ty(&self, method_call: typeck::MethodCall) -> Option<ty::t> {
4738 self.method_map.borrow().find(&method_call).map(|method| method.ty)
4741 fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>> {
4745 fn is_method_call(&self, id: ast::NodeId) -> bool {
4746 self.method_map.borrow().contains_key(&typeck::MethodCall::expr(id))
4749 fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<ast::NodeId> {
4750 self.region_maps.temporary_scope(rvalue_id)
4753 fn upvar_borrow(&self, upvar_id: ty::UpvarId) -> ty::UpvarBorrow {
4754 self.upvar_borrow_map.borrow().get_copy(&upvar_id)