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;
16 use metadata::csearch;
17 use middle::const_eval;
19 use middle::dependency_format;
20 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem};
21 use middle::lang_items::{FnOnceTraitLangItem, TyDescStructLangItem};
22 use middle::mem_categorization as mc;
24 use middle::resolve_lifetime;
25 use middle::stability;
26 use middle::subst::{mod, Subst, Substs, VecPerParamSpace};
30 use middle::ty_fold::{mod, TypeFoldable,TypeFolder};
32 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
33 use util::ppaux::{trait_store_to_string, ty_to_string};
34 use util::ppaux::{Repr, UserString};
35 use util::common::{indenter, memoized, memoized_with_key};
36 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet, FnvHashMap};
38 use std::cell::{Cell, RefCell};
40 use std::fmt::{mod, Show};
41 use std::hash::{Hash, sip, Writer};
45 use std::collections::{HashMap, HashSet};
46 use std::collections::hashmap::{Occupied, Vacant};
47 use arena::TypedArena;
49 use syntax::ast::{CrateNum, DefId, FnStyle, Ident, ItemTrait, LOCAL_CRATE};
50 use syntax::ast::{MutImmutable, MutMutable, Name, NamedField, NodeId};
51 use syntax::ast::{Onceness, StmtExpr, StmtSemi, StructField, UnnamedField};
52 use syntax::ast::{Visibility};
53 use syntax::ast_util::{mod, is_local, lit_is_str, local_def, PostExpansionMethod};
54 use syntax::attr::{mod, AttrMetaMethods};
55 use syntax::codemap::Span;
56 use syntax::parse::token::{mod, InternedString};
57 use syntax::{ast, ast_map};
58 use std::collections::enum_set::{EnumSet, CLike};
62 pub const INITIAL_DISCRIMINANT_VALUE: Disr = 0;
66 #[deriving(PartialEq, Eq, Hash)]
72 #[deriving(Clone, Show)]
73 pub enum ImplOrTraitItemContainer {
74 TraitContainer(ast::DefId),
75 ImplContainer(ast::DefId),
78 impl ImplOrTraitItemContainer {
79 pub fn id(&self) -> ast::DefId {
81 TraitContainer(id) => id,
82 ImplContainer(id) => id,
88 pub enum ImplOrTraitItem {
89 MethodTraitItem(Rc<Method>),
90 TypeTraitItem(Rc<AssociatedType>),
93 impl ImplOrTraitItem {
94 fn id(&self) -> ImplOrTraitItemId {
96 MethodTraitItem(ref method) => MethodTraitItemId(method.def_id),
97 TypeTraitItem(ref associated_type) => {
98 TypeTraitItemId(associated_type.def_id)
103 pub fn def_id(&self) -> ast::DefId {
105 MethodTraitItem(ref method) => method.def_id,
106 TypeTraitItem(ref associated_type) => associated_type.def_id,
110 pub fn name(&self) -> ast::Name {
112 MethodTraitItem(ref method) => method.name,
113 TypeTraitItem(ref associated_type) => associated_type.name,
117 pub fn container(&self) -> ImplOrTraitItemContainer {
119 MethodTraitItem(ref method) => method.container,
120 TypeTraitItem(ref associated_type) => associated_type.container,
124 pub fn as_opt_method(&self) -> Option<Rc<Method>> {
126 MethodTraitItem(ref m) => Some((*m).clone()),
127 TypeTraitItem(_) => None
133 pub enum ImplOrTraitItemId {
134 MethodTraitItemId(ast::DefId),
135 TypeTraitItemId(ast::DefId),
138 impl ImplOrTraitItemId {
139 pub fn def_id(&self) -> ast::DefId {
141 MethodTraitItemId(def_id) => def_id,
142 TypeTraitItemId(def_id) => def_id,
147 #[deriving(Clone, Show)]
150 pub generics: ty::Generics,
152 pub explicit_self: ExplicitSelfCategory,
153 pub vis: ast::Visibility,
154 pub def_id: ast::DefId,
155 pub container: ImplOrTraitItemContainer,
157 // If this method is provided, we need to know where it came from
158 pub provided_source: Option<ast::DefId>
162 pub fn new(name: ast::Name,
163 generics: ty::Generics,
165 explicit_self: ExplicitSelfCategory,
166 vis: ast::Visibility,
168 container: ImplOrTraitItemContainer,
169 provided_source: Option<ast::DefId>)
175 explicit_self: explicit_self,
178 container: container,
179 provided_source: provided_source
183 pub fn container_id(&self) -> ast::DefId {
184 match self.container {
185 TraitContainer(id) => id,
186 ImplContainer(id) => id,
192 pub struct AssociatedType {
194 pub vis: ast::Visibility,
195 pub def_id: ast::DefId,
196 pub container: ImplOrTraitItemContainer,
199 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
202 pub mutbl: ast::Mutability,
205 #[deriving(Clone, PartialEq, Eq, Hash, Encodable, Decodable, Show)]
206 pub enum TraitStore {
209 /// &Trait and &mut Trait
210 RegionTraitStore(Region, ast::Mutability),
213 #[deriving(Clone, Show)]
214 pub struct field_ty {
217 pub vis: ast::Visibility,
218 pub origin: ast::DefId, // The DefId of the struct in which the field is declared.
221 // Contains information needed to resolve types and (in the future) look up
222 // the types of AST nodes.
223 #[deriving(PartialEq, Eq, Hash)]
224 pub struct creader_cache_key {
230 pub type creader_cache = RefCell<HashMap<creader_cache_key, t>>;
232 pub struct intern_key {
236 // NB: Do not replace this with #[deriving(PartialEq)]. The automatically-derived
237 // implementation will not recurse through sty and you will get stack
239 impl cmp::PartialEq for intern_key {
240 fn eq(&self, other: &intern_key) -> bool {
242 *self.sty == *other.sty
245 fn ne(&self, other: &intern_key) -> bool {
250 impl Eq for intern_key {}
252 impl<W:Writer> Hash<W> for intern_key {
253 fn hash(&self, s: &mut W) {
254 unsafe { (*self.sty).hash(s) }
258 pub enum ast_ty_to_ty_cache_entry {
259 atttce_unresolved, /* not resolved yet */
260 atttce_resolved(t) /* resolved to a type, irrespective of region */
263 #[deriving(Clone, PartialEq, Decodable, Encodable)]
264 pub struct ItemVariances {
265 pub types: VecPerParamSpace<Variance>,
266 pub regions: VecPerParamSpace<Variance>,
269 #[deriving(Clone, PartialEq, Decodable, Encodable, Show)]
271 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
272 Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
273 Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
274 Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
277 #[deriving(Clone, Show)]
278 pub enum AutoAdjustment {
279 AdjustAddEnv(ty::TraitStore),
280 AdjustDerefRef(AutoDerefRef)
283 #[deriving(Clone, PartialEq, Show)]
284 pub enum UnsizeKind {
285 // [T, ..n] -> [T], the uint field is n.
287 // An unsize coercion applied to the tail field of a struct.
288 // The uint is the index of the type parameter which is unsized.
289 UnsizeStruct(Box<UnsizeKind>, uint),
290 UnsizeVtable(TyTrait, /* the self type of the trait */ ty::t)
293 #[deriving(Clone, Show)]
294 pub struct AutoDerefRef {
295 pub autoderefs: uint,
296 pub autoref: Option<AutoRef>
299 #[deriving(Clone, PartialEq, Show)]
301 /// Convert from T to &T
302 /// The third field allows us to wrap other AutoRef adjustments.
303 AutoPtr(Region, ast::Mutability, Option<Box<AutoRef>>),
305 /// Convert [T, ..n] to [T] (or similar, depending on the kind)
306 AutoUnsize(UnsizeKind),
308 /// Convert Box<[T, ..n]> to Box<[T]> or something similar in a Box.
309 /// With DST and Box a library type, this should be replaced by UnsizeStruct.
310 AutoUnsizeUniq(UnsizeKind),
312 /// Convert from T to *T
313 /// Value to thin pointer
314 /// The second field allows us to wrap other AutoRef adjustments.
315 AutoUnsafe(ast::Mutability, Option<Box<AutoRef>>),
318 // Ugly little helper function. The first bool in the returned tuple is true if
319 // there is an 'unsize to trait object' adjustment at the bottom of the
320 // adjustment. If that is surrounded by an AutoPtr, then we also return the
321 // region of the AutoPtr (in the third argument). The second bool is true if the
322 // adjustment is unique.
323 fn autoref_object_region(autoref: &AutoRef) -> (bool, bool, Option<Region>) {
324 fn unsize_kind_is_object(k: &UnsizeKind) -> bool {
326 &UnsizeVtable(..) => true,
327 &UnsizeStruct(box ref k, _) => unsize_kind_is_object(k),
333 &AutoUnsize(ref k) => (unsize_kind_is_object(k), false, None),
334 &AutoUnsizeUniq(ref k) => (unsize_kind_is_object(k), true, None),
335 &AutoPtr(adj_r, _, Some(box ref autoref)) => {
336 let (b, u, r) = autoref_object_region(autoref);
337 if r.is_some() || u {
343 &AutoUnsafe(_, Some(box ref autoref)) => autoref_object_region(autoref),
344 _ => (false, false, None)
348 // If the adjustment introduces a borrowed reference to a trait object, then
349 // returns the region of the borrowed reference.
350 pub fn adjusted_object_region(adj: &AutoAdjustment) -> Option<Region> {
352 &AdjustDerefRef(AutoDerefRef{autoref: Some(ref autoref), ..}) => {
353 let (b, _, r) = autoref_object_region(autoref);
364 // Returns true if there is a trait cast at the bottom of the adjustment.
365 pub fn adjust_is_object(adj: &AutoAdjustment) -> bool {
367 &AdjustDerefRef(AutoDerefRef{autoref: Some(ref autoref), ..}) => {
368 let (b, _, _) = autoref_object_region(autoref);
375 // If possible, returns the type expected from the given adjustment. This is not
376 // possible if the adjustment depends on the type of the adjusted expression.
377 pub fn type_of_adjust(cx: &ctxt, adj: &AutoAdjustment) -> Option<t> {
378 fn type_of_autoref(cx: &ctxt, autoref: &AutoRef) -> Option<t> {
380 &AutoUnsize(ref k) => match k {
381 &UnsizeVtable(TyTrait { def_id, ref substs, bounds }, _) => {
382 Some(mk_trait(cx, def_id, substs.clone(), bounds))
386 &AutoUnsizeUniq(ref k) => match k {
387 &UnsizeVtable(TyTrait { def_id, ref substs, bounds }, _) => {
388 Some(mk_uniq(cx, mk_trait(cx, def_id, substs.clone(), bounds)))
392 &AutoPtr(r, m, Some(box ref autoref)) => {
393 match type_of_autoref(cx, autoref) {
394 Some(t) => Some(mk_rptr(cx, r, mt {mutbl: m, ty: t})),
398 &AutoUnsafe(m, Some(box ref autoref)) => {
399 match type_of_autoref(cx, autoref) {
400 Some(t) => Some(mk_ptr(cx, mt {mutbl: m, ty: t})),
409 &AdjustDerefRef(AutoDerefRef{autoref: Some(ref autoref), ..}) => {
410 type_of_autoref(cx, autoref)
418 /// A restriction that certain types must be the same size. The use of
419 /// `transmute` gives rise to these restrictions.
420 pub struct TransmuteRestriction {
421 /// The span from whence the restriction comes.
423 /// The type being transmuted from.
425 /// The type being transmuted to.
427 /// NodeIf of the transmute intrinsic.
431 /// The data structure to keep track of all the information that typechecker
432 /// generates so that so that it can be reused and doesn't have to be redone
434 pub struct ctxt<'tcx> {
435 /// The arena that types are allocated from.
436 type_arena: &'tcx TypedArena<t_box_>,
438 /// Specifically use a speedy hash algorithm for this hash map, it's used
440 interner: RefCell<FnvHashMap<intern_key, &'tcx t_box_>>,
441 pub next_id: Cell<uint>,
443 pub def_map: resolve::DefMap,
445 pub named_region_map: resolve_lifetime::NamedRegionMap,
447 pub region_maps: middle::region::RegionMaps,
449 /// Stores the types for various nodes in the AST. Note that this table
450 /// is not guaranteed to be populated until after typeck. See
451 /// typeck::check::fn_ctxt for details.
452 pub node_types: node_type_table,
454 /// Stores the type parameters which were substituted to obtain the type
455 /// of this node. This only applies to nodes that refer to entities
456 /// parameterized by type parameters, such as generic fns, types, or
458 pub item_substs: RefCell<NodeMap<ItemSubsts>>,
460 /// Maps from a trait item to the trait item "descriptor"
461 pub impl_or_trait_items: RefCell<DefIdMap<ImplOrTraitItem>>,
463 /// Maps from a trait def-id to a list of the def-ids of its trait items
464 pub trait_item_def_ids: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItemId>>>>,
466 /// A cache for the trait_items() routine
467 pub trait_items_cache: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItem>>>>,
469 pub impl_trait_cache: RefCell<DefIdMap<Option<Rc<ty::TraitRef>>>>,
471 pub trait_refs: RefCell<NodeMap<Rc<TraitRef>>>,
472 pub trait_defs: RefCell<DefIdMap<Rc<TraitDef>>>,
474 /// Maps from node-id of a trait object cast (like `foo as
475 /// Box<Trait>`) to the trait reference.
476 pub object_cast_map: typeck::ObjectCastMap,
478 pub map: ast_map::Map<'tcx>,
479 pub intrinsic_defs: RefCell<DefIdMap<t>>,
480 pub freevars: RefCell<FreevarMap>,
481 pub tcache: type_cache,
482 pub rcache: creader_cache,
483 pub short_names_cache: RefCell<HashMap<t, String>>,
484 pub needs_unwind_cleanup_cache: RefCell<HashMap<t, bool>>,
485 pub tc_cache: RefCell<HashMap<uint, TypeContents>>,
486 pub ast_ty_to_ty_cache: RefCell<NodeMap<ast_ty_to_ty_cache_entry>>,
487 pub enum_var_cache: RefCell<DefIdMap<Rc<Vec<Rc<VariantInfo>>>>>,
488 pub ty_param_defs: RefCell<NodeMap<TypeParameterDef>>,
489 pub adjustments: RefCell<NodeMap<AutoAdjustment>>,
490 pub normalized_cache: RefCell<HashMap<t, t>>,
491 pub lang_items: middle::lang_items::LanguageItems,
492 /// A mapping of fake provided method def_ids to the default implementation
493 pub provided_method_sources: RefCell<DefIdMap<ast::DefId>>,
494 pub struct_fields: RefCell<DefIdMap<Rc<Vec<field_ty>>>>,
496 /// Maps from def-id of a type or region parameter to its
497 /// (inferred) variance.
498 pub item_variance_map: RefCell<DefIdMap<Rc<ItemVariances>>>,
500 /// True if the variance has been computed yet; false otherwise.
501 pub variance_computed: Cell<bool>,
503 /// A mapping from the def ID of an enum or struct type to the def ID
504 /// of the method that implements its destructor. If the type is not
505 /// present in this map, it does not have a destructor. This map is
506 /// populated during the coherence phase of typechecking.
507 pub destructor_for_type: RefCell<DefIdMap<ast::DefId>>,
509 /// A method will be in this list if and only if it is a destructor.
510 pub destructors: RefCell<DefIdSet>,
512 /// Maps a trait onto a list of impls of that trait.
513 pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>,
515 /// Maps a DefId of a type to a list of its inherent impls.
516 /// Contains implementations of methods that are inherent to a type.
517 /// Methods in these implementations don't need to be exported.
518 pub inherent_impls: RefCell<DefIdMap<Rc<Vec<ast::DefId>>>>,
520 /// Maps a DefId of an impl to a list of its items.
521 /// Note that this contains all of the impls that we know about,
522 /// including ones in other crates. It's not clear that this is the best
524 pub impl_items: RefCell<DefIdMap<Vec<ImplOrTraitItemId>>>,
526 /// Set of used unsafe nodes (functions or blocks). Unsafe nodes not
527 /// present in this set can be warned about.
528 pub used_unsafe: RefCell<NodeSet>,
530 /// Set of nodes which mark locals as mutable which end up getting used at
531 /// some point. Local variable definitions not in this set can be warned
533 pub used_mut_nodes: RefCell<NodeSet>,
535 /// The set of external nominal types whose implementations have been read.
536 /// This is used for lazy resolution of methods.
537 pub populated_external_types: RefCell<DefIdSet>,
539 /// The set of external traits whose implementations have been read. This
540 /// is used for lazy resolution of traits.
541 pub populated_external_traits: RefCell<DefIdSet>,
544 pub upvar_borrow_map: RefCell<UpvarBorrowMap>,
546 /// These two caches are used by const_eval when decoding external statics
547 /// and variants that are found.
548 pub extern_const_statics: RefCell<DefIdMap<ast::NodeId>>,
549 pub extern_const_variants: RefCell<DefIdMap<ast::NodeId>>,
551 pub method_map: typeck::MethodMap,
553 pub dependency_formats: RefCell<dependency_format::Dependencies>,
555 /// Records the type of each unboxed closure. The def ID is the ID of the
556 /// expression defining the unboxed closure.
557 pub unboxed_closures: RefCell<DefIdMap<UnboxedClosure>>,
559 pub node_lint_levels: RefCell<HashMap<(ast::NodeId, lint::LintId),
562 /// The types that must be asserted to be the same size for `transmute`
563 /// to be valid. We gather up these restrictions in the intrinsicck pass
564 /// and check them in trans.
565 pub transmute_restrictions: RefCell<Vec<TransmuteRestriction>>,
567 /// Maps any item's def-id to its stability index.
568 pub stability: RefCell<stability::Index>,
570 /// Maps closures to their capture clauses.
571 pub capture_modes: RefCell<CaptureModeMap>,
573 /// Maps def IDs to true if and only if they're associated types.
574 pub associated_types: RefCell<DefIdMap<bool>>,
576 /// Maps def IDs of traits to information about their associated types.
577 pub trait_associated_types:
578 RefCell<DefIdMap<Rc<Vec<AssociatedTypeInfo>>>>,
580 /// Caches the results of trait selection. This cache is used
581 /// for things that do not have to do with the parameters in scope.
582 pub selection_cache: traits::SelectionCache,
584 /// Caches the representation hints for struct definitions.
585 pub repr_hint_cache: RefCell<DefIdMap<Rc<Vec<attr::ReprAttr>>>>,
588 // Flags that we track on types. These flags are propagated upwards
589 // through the type during type construction, so that we can quickly
590 // check whether the type has various kinds of types in it without
591 // recursing over the type itself.
593 flags TypeFlags: u32 {
594 const NO_TYPE_FLAGS = 0b0,
595 const HAS_PARAMS = 0b1,
596 const HAS_SELF = 0b10,
597 const HAS_TY_INFER = 0b100,
598 const HAS_RE_INFER = 0b1000,
599 const HAS_REGIONS = 0b10000,
600 const HAS_TY_ERR = 0b100000,
601 const NEEDS_SUBST = HAS_PARAMS.bits | HAS_SELF.bits | HAS_REGIONS.bits,
605 pub type t_box = &'static t_box_;
611 pub flags: TypeFlags,
614 impl fmt::Show for TypeFlags {
615 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
616 write!(f, "{}", self.bits)
620 // To reduce refcounting cost, we're representing types as unsafe pointers
621 // throughout the compiler. These are simply casted t_box values. Use ty::get
622 // to cast them back to a box. (Without the cast, compiler performance suffers
623 // ~15%.) This does mean that a t value relies on the ctxt to keep its box
624 // alive, and using ty::get is unsafe when the ctxt is no longer alive.
627 #[allow(raw_pointer_deriving)]
628 #[deriving(Clone, PartialEq, Eq, Hash)]
629 pub struct t { inner: *const t_opaque }
631 impl fmt::Show for t {
632 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
633 write!(f, "{}", get(*self))
637 pub fn get(t: t) -> t_box {
639 let t2: t_box = mem::transmute(t);
644 fn tbox_has_flag(tb: t_box, flag: TypeFlags) -> bool {
645 tb.flags.intersects(flag)
647 pub fn type_has_params(t: t) -> bool {
648 tbox_has_flag(get(t), HAS_PARAMS)
650 pub fn type_has_self(t: t) -> bool { tbox_has_flag(get(t), HAS_SELF) }
651 pub fn type_has_ty_infer(t: t) -> bool { tbox_has_flag(get(t), HAS_TY_INFER) }
652 pub fn type_needs_infer(t: t) -> bool {
653 tbox_has_flag(get(t), HAS_TY_INFER | HAS_RE_INFER)
655 pub fn type_id(t: t) -> uint { get(t).id }
657 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
658 pub struct BareFnTy {
659 pub fn_style: ast::FnStyle,
664 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
665 pub struct ClosureTy {
666 pub fn_style: ast::FnStyle,
667 pub onceness: ast::Onceness,
668 pub store: TraitStore,
669 pub bounds: ExistentialBounds,
674 #[deriving(Clone, PartialEq, Eq, Hash)]
681 pub fn unwrap(&self) -> ty::t {
683 ty::FnConverging(ref t) => *t,
684 ty::FnDiverging => unreachable!()
690 * Signature of a function type, which I have arbitrarily
691 * decided to use to refer to the input/output types.
693 * - `binder_id` is the node id where this fn type appeared;
694 * it is used to identify all the bound regions appearing
695 * in the input/output types that are bound by this fn type
696 * (vs some enclosing or enclosed fn type)
697 * - `inputs` is the list of arguments and their modes.
698 * - `output` is the return type.
699 * - `variadic` indicates whether this is a varidic function. (only true for foreign fns)
701 #[deriving(Clone, PartialEq, Eq, Hash)]
703 pub binder_id: ast::NodeId,
705 pub output: FnOutput,
709 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
711 pub space: subst::ParamSpace,
716 /// Representation of regions:
717 #[deriving(Clone, PartialEq, Eq, Hash, Encodable, Decodable, Show)]
719 // Region bound in a type or fn declaration which will be
720 // substituted 'early' -- that is, at the same time when type
721 // parameters are substituted.
722 ReEarlyBound(/* param id */ ast::NodeId,
727 // Region bound in a function scope, which will be substituted when the
728 // function is called. The first argument must be the `binder_id` of
729 // some enclosing function signature.
730 ReLateBound(/* binder_id */ ast::NodeId, BoundRegion),
732 /// When checking a function body, the types of all arguments and so forth
733 /// that refer to bound region parameters are modified to refer to free
734 /// region parameters.
737 /// A concrete region naming some expression within the current function.
740 /// Static data that has an "infinite" lifetime. Top in the region lattice.
743 /// A region variable. Should not exist after typeck.
744 ReInfer(InferRegion),
746 /// Empty lifetime is for data that is never accessed.
747 /// Bottom in the region lattice. We treat ReEmpty somewhat
748 /// specially; at least right now, we do not generate instances of
749 /// it during the GLB computations, but rather
750 /// generate an error instead. This is to improve error messages.
751 /// The only way to get an instance of ReEmpty is to have a region
752 /// variable with no constraints.
757 * Upvars do not get their own node-id. Instead, we use the pair of
758 * the original var id (that is, the root variable that is referenced
759 * by the upvar) and the id of the closure expression.
761 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
763 pub var_id: ast::NodeId,
764 pub closure_expr_id: ast::NodeId,
767 #[deriving(Clone, PartialEq, Eq, Hash, Show, Encodable, Decodable)]
768 pub enum BorrowKind {
769 /// Data must be immutable and is aliasable.
772 /// Data must be immutable but not aliasable. This kind of borrow
773 /// cannot currently be expressed by the user and is used only in
774 /// implicit closure bindings. It is needed when you the closure
775 /// is borrowing or mutating a mutable referent, e.g.:
777 /// let x: &mut int = ...;
778 /// let y = || *x += 5;
780 /// If we were to try to translate this closure into a more explicit
781 /// form, we'd encounter an error with the code as written:
783 /// struct Env { x: & &mut int }
784 /// let x: &mut int = ...;
785 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
786 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
788 /// This is then illegal because you cannot mutate a `&mut` found
789 /// in an aliasable location. To solve, you'd have to translate with
790 /// an `&mut` borrow:
792 /// struct Env { x: & &mut int }
793 /// let x: &mut int = ...;
794 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
795 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
797 /// Now the assignment to `**env.x` is legal, but creating a
798 /// mutable pointer to `x` is not because `x` is not mutable. We
799 /// could fix this by declaring `x` as `let mut x`. This is ok in
800 /// user code, if awkward, but extra weird for closures, since the
801 /// borrow is hidden.
803 /// So we introduce a "unique imm" borrow -- the referent is
804 /// immutable, but not aliasable. This solves the problem. For
805 /// simplicity, we don't give users the way to express this
806 /// borrow, it's just used when translating closures.
809 /// Data is mutable and not aliasable.
814 * Information describing the borrowing of an upvar. This is computed
815 * during `typeck`, specifically by `regionck`. The general idea is
816 * that the compiler analyses treat closures like:
818 * let closure: &'e fn() = || {
819 * x = 1; // upvar x is assigned to
820 * use(y); // upvar y is read
821 * foo(&z); // upvar z is borrowed immutably
824 * as if they were "desugared" to something loosely like:
826 * struct Vars<'x,'y,'z> { x: &'x mut int,
829 * let closure: &'e fn() = {
835 * let env: &'e mut Vars<'x,'y,'z> = &mut Vars { x: &'x mut x,
841 * This is basically what happens at runtime. The closure is basically
842 * an existentially quantified version of the `(env, f)` pair.
844 * This data structure indicates the region and mutability of a single
845 * one of the `x...z` borrows.
847 * It may not be obvious why each borrowed variable gets its own
848 * lifetime (in the desugared version of the example, these are indicated
849 * by the lifetime parameters `'x`, `'y`, and `'z` in the `Vars` definition).
850 * Each such lifetime must encompass the lifetime `'e` of the closure itself,
851 * but need not be identical to it. The reason that this makes sense:
853 * - Callers are only permitted to invoke the closure, and hence to
854 * use the pointers, within the lifetime `'e`, so clearly `'e` must
855 * be a sublifetime of `'x...'z`.
856 * - The closure creator knows which upvars were borrowed by the closure
857 * and thus `x...z` will be reserved for `'x...'z` respectively.
858 * - Through mutation, the borrowed upvars can actually escape
859 * the closure, so sometimes it is necessary for them to be larger
860 * than the closure lifetime itself.
862 #[deriving(PartialEq, Clone, Encodable, Decodable, Show)]
863 pub struct UpvarBorrow {
864 pub kind: BorrowKind,
865 pub region: ty::Region,
868 pub type UpvarBorrowMap = HashMap<UpvarId, UpvarBorrow>;
871 pub fn is_bound(&self) -> bool {
873 &ty::ReEarlyBound(..) => true,
874 &ty::ReLateBound(..) => true,
880 #[deriving(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Encodable, Decodable, Show)]
881 pub struct FreeRegion {
882 pub scope_id: NodeId,
883 pub bound_region: BoundRegion
886 #[deriving(Clone, PartialEq, PartialOrd, Eq, Ord, Hash, Encodable, Decodable, Show)]
887 pub enum BoundRegion {
888 /// An anonymous region parameter for a given fn (&T)
891 /// Named region parameters for functions (a in &'a T)
893 /// The def-id is needed to distinguish free regions in
894 /// the event of shadowing.
895 BrNamed(ast::DefId, ast::Name),
897 /// Fresh bound identifiers created during GLB computations.
900 // Anonymous region for the implicit env pointer parameter
910 macro_rules! def_prim_ty(
911 ($name:ident, $sty:expr, $id:expr) => (
912 pub static $name: t_box_ = t_box_ {
915 flags: super::NO_TYPE_FLAGS,
920 def_prim_ty!(TY_NIL, super::ty_nil, 0)
921 def_prim_ty!(TY_BOOL, super::ty_bool, 1)
922 def_prim_ty!(TY_CHAR, super::ty_char, 2)
923 def_prim_ty!(TY_INT, super::ty_int(ast::TyI), 3)
924 def_prim_ty!(TY_I8, super::ty_int(ast::TyI8), 4)
925 def_prim_ty!(TY_I16, super::ty_int(ast::TyI16), 5)
926 def_prim_ty!(TY_I32, super::ty_int(ast::TyI32), 6)
927 def_prim_ty!(TY_I64, super::ty_int(ast::TyI64), 7)
928 def_prim_ty!(TY_UINT, super::ty_uint(ast::TyU), 8)
929 def_prim_ty!(TY_U8, super::ty_uint(ast::TyU8), 9)
930 def_prim_ty!(TY_U16, super::ty_uint(ast::TyU16), 10)
931 def_prim_ty!(TY_U32, super::ty_uint(ast::TyU32), 11)
932 def_prim_ty!(TY_U64, super::ty_uint(ast::TyU64), 12)
933 def_prim_ty!(TY_F32, super::ty_float(ast::TyF32), 14)
934 def_prim_ty!(TY_F64, super::ty_float(ast::TyF64), 15)
936 pub static TY_ERR: t_box_ = t_box_ {
939 flags: super::HAS_TY_ERR,
942 pub const LAST_PRIMITIVE_ID: uint = 18;
945 // NB: If you change this, you'll probably want to change the corresponding
946 // AST structure in libsyntax/ast.rs as well.
947 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
953 ty_uint(ast::UintTy),
954 ty_float(ast::FloatTy),
955 /// Substs here, possibly against intuition, *may* contain `ty_param`s.
956 /// That is, even after substitution it is possible that there are type
957 /// variables. This happens when the `ty_enum` corresponds to an enum
958 /// definition and not a concrete use of it. To get the correct `ty_enum`
959 /// from the tcx, use the `NodeId` from the `ast::Ty` and look it up in
960 /// the `ast_ty_to_ty_cache`. This is probably true for `ty_struct` as
962 ty_enum(DefId, Substs),
965 ty_vec(t, Option<uint>), // Second field is length.
968 ty_bare_fn(BareFnTy),
969 ty_closure(Box<ClosureTy>),
970 ty_trait(Box<TyTrait>),
971 ty_struct(DefId, Substs),
972 ty_unboxed_closure(DefId, Region, Substs),
975 ty_param(ParamTy), // type parameter
976 ty_open(t), // A deref'ed fat pointer, i.e., a dynamically sized value
977 // and its size. Only ever used in trans. It is not necessary
978 // earlier since we don't need to distinguish a DST with its
979 // size (e.g., in a deref) vs a DST with the size elsewhere (
980 // e.g., in a field).
982 ty_infer(InferTy), // something used only during inference/typeck
983 ty_err, // Also only used during inference/typeck, to represent
984 // the type of an erroneous expression (helps cut down
985 // on non-useful type error messages)
988 #[deriving(Clone, PartialEq, Eq, Hash, Show)]
992 pub bounds: ExistentialBounds
995 #[deriving(PartialEq, Eq, Hash, Show)]
996 pub struct TraitRef {
1001 #[deriving(Clone, PartialEq)]
1002 pub enum IntVarValue {
1003 IntType(ast::IntTy),
1004 UintType(ast::UintTy),
1007 #[deriving(Clone, Show)]
1008 pub enum terr_vstore_kind {
1015 #[deriving(Clone, Show)]
1016 pub struct expected_found<T> {
1021 // Data structures used in type unification
1022 #[deriving(Clone, Show)]
1025 terr_fn_style_mismatch(expected_found<FnStyle>),
1026 terr_onceness_mismatch(expected_found<Onceness>),
1027 terr_abi_mismatch(expected_found<abi::Abi>),
1029 terr_sigil_mismatch(expected_found<TraitStore>),
1030 terr_box_mutability,
1031 terr_ptr_mutability,
1032 terr_ref_mutability,
1033 terr_vec_mutability,
1034 terr_tuple_size(expected_found<uint>),
1035 terr_ty_param_size(expected_found<uint>),
1036 terr_record_size(expected_found<uint>),
1037 terr_record_mutability,
1038 terr_record_fields(expected_found<Ident>),
1040 terr_regions_does_not_outlive(Region, Region),
1041 terr_regions_not_same(Region, Region),
1042 terr_regions_no_overlap(Region, Region),
1043 terr_regions_insufficiently_polymorphic(BoundRegion, Region),
1044 terr_regions_overly_polymorphic(BoundRegion, Region),
1045 terr_trait_stores_differ(terr_vstore_kind, expected_found<TraitStore>),
1046 terr_sorts(expected_found<t>),
1047 terr_integer_as_char,
1048 terr_int_mismatch(expected_found<IntVarValue>),
1049 terr_float_mismatch(expected_found<ast::FloatTy>),
1050 terr_traits(expected_found<ast::DefId>),
1051 terr_builtin_bounds(expected_found<BuiltinBounds>),
1052 terr_variadic_mismatch(expected_found<bool>),
1054 terr_convergence_mismatch(expected_found<bool>)
1057 /// Bounds suitable for a named type parameter like `A` in `fn foo<A>`
1058 /// as well as the existential type parameter in an object type.
1059 #[deriving(PartialEq, Eq, Hash, Clone, Show)]
1060 pub struct ParamBounds {
1061 pub region_bounds: Vec<ty::Region>,
1062 pub builtin_bounds: BuiltinBounds,
1063 pub trait_bounds: Vec<Rc<TraitRef>>
1066 /// Bounds suitable for an existentially quantified type parameter
1067 /// such as those that appear in object types or closure types. The
1068 /// major difference between this case and `ParamBounds` is that
1069 /// general purpose trait bounds are omitted and there must be
1070 /// *exactly one* region.
1071 #[deriving(PartialEq, Eq, Hash, Clone, Show)]
1072 pub struct ExistentialBounds {
1073 pub region_bound: ty::Region,
1074 pub builtin_bounds: BuiltinBounds
1077 pub type BuiltinBounds = EnumSet<BuiltinBound>;
1079 #[deriving(Clone, Encodable, PartialEq, Eq, Decodable, Hash, Show)]
1081 pub enum BuiltinBound {
1088 pub fn empty_builtin_bounds() -> BuiltinBounds {
1092 pub fn all_builtin_bounds() -> BuiltinBounds {
1093 let mut set = EnumSet::empty();
1095 set.add(BoundSized);
1100 pub fn region_existential_bound(r: ty::Region) -> ExistentialBounds {
1102 * An existential bound that does not implement any traits.
1105 ty::ExistentialBounds { region_bound: r,
1106 builtin_bounds: empty_builtin_bounds() }
1109 impl CLike for BuiltinBound {
1110 fn to_uint(&self) -> uint {
1113 fn from_uint(v: uint) -> BuiltinBound {
1114 unsafe { mem::transmute(v) }
1118 #[deriving(Clone, PartialEq, Eq, Hash)]
1123 #[deriving(Clone, PartialEq, Eq, Hash)]
1128 #[deriving(Clone, PartialEq, Eq, Hash)]
1129 pub struct FloatVid {
1133 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1134 pub struct RegionVid {
1138 #[deriving(Clone, PartialEq, Eq, Hash)]
1145 // FIXME -- once integral fallback is impl'd, we should remove
1146 // this type. It's only needed to prevent spurious errors for
1147 // integers whose type winds up never being constrained.
1148 SkolemizedIntTy(uint),
1151 #[deriving(Clone, Encodable, Decodable, Eq, Hash, Show)]
1152 pub enum InferRegion {
1154 ReSkolemized(uint, BoundRegion)
1157 impl cmp::PartialEq for InferRegion {
1158 fn eq(&self, other: &InferRegion) -> bool {
1159 match ((*self), *other) {
1160 (ReVar(rva), ReVar(rvb)) => {
1163 (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
1169 fn ne(&self, other: &InferRegion) -> bool {
1170 !((*self) == (*other))
1174 impl fmt::Show for TyVid {
1175 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
1176 write!(f, "<generic #{}>", self.index)
1180 impl fmt::Show for IntVid {
1181 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1182 write!(f, "<generic integer #{}>", self.index)
1186 impl fmt::Show for FloatVid {
1187 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1188 write!(f, "<generic float #{}>", self.index)
1192 impl fmt::Show for RegionVid {
1193 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1194 write!(f, "'<generic lifetime #{}>", self.index)
1198 impl fmt::Show for FnSig {
1199 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1200 // grr, without tcx not much we can do.
1205 impl fmt::Show for InferTy {
1206 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1208 TyVar(ref v) => v.fmt(f),
1209 IntVar(ref v) => v.fmt(f),
1210 FloatVar(ref v) => v.fmt(f),
1211 SkolemizedTy(v) => write!(f, "SkolemizedTy({})", v),
1212 SkolemizedIntTy(v) => write!(f, "SkolemizedIntTy({})", v),
1217 impl fmt::Show for IntVarValue {
1218 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1220 IntType(ref v) => v.fmt(f),
1221 UintType(ref v) => v.fmt(f),
1226 #[deriving(Clone, Show)]
1227 pub struct TypeParameterDef {
1228 pub name: ast::Name,
1229 pub def_id: ast::DefId,
1230 pub space: subst::ParamSpace,
1232 pub associated_with: Option<ast::DefId>,
1233 pub bounds: ParamBounds,
1234 pub default: Option<ty::t>,
1237 #[deriving(Encodable, Decodable, Clone, Show)]
1238 pub struct RegionParameterDef {
1239 pub name: ast::Name,
1240 pub def_id: ast::DefId,
1241 pub space: subst::ParamSpace,
1243 pub bounds: Vec<ty::Region>,
1246 /// Information about the type/lifetime parameters associated with an
1247 /// item or method. Analogous to ast::Generics.
1248 #[deriving(Clone, Show)]
1249 pub struct Generics {
1250 pub types: VecPerParamSpace<TypeParameterDef>,
1251 pub regions: VecPerParamSpace<RegionParameterDef>,
1255 pub fn empty() -> Generics {
1256 Generics { types: VecPerParamSpace::empty(),
1257 regions: VecPerParamSpace::empty() }
1260 pub fn has_type_params(&self, space: subst::ParamSpace) -> bool {
1261 !self.types.is_empty_in(space)
1264 pub fn has_region_params(&self, space: subst::ParamSpace) -> bool {
1265 !self.regions.is_empty_in(space)
1270 pub fn new(def_id: ast::DefId, substs: Substs) -> TraitRef {
1271 TraitRef { def_id: def_id, substs: substs }
1274 pub fn self_ty(&self) -> ty::t {
1275 self.substs.self_ty().unwrap()
1278 pub fn input_types(&self) -> &[ty::t] {
1279 // Select only the "input types" from a trait-reference. For
1280 // now this is all the types that appear in the
1281 // trait-reference, but it should eventually exclude
1282 // associated types.
1283 self.substs.types.as_slice()
1287 /// When type checking, we use the `ParameterEnvironment` to track
1288 /// details about the type/lifetime parameters that are in scope.
1289 /// It primarily stores the bounds information.
1291 /// Note: This information might seem to be redundant with the data in
1292 /// `tcx.ty_param_defs`, but it is not. That table contains the
1293 /// parameter definitions from an "outside" perspective, but this
1294 /// struct will contain the bounds for a parameter as seen from inside
1295 /// the function body. Currently the only real distinction is that
1296 /// bound lifetime parameters are replaced with free ones, but in the
1297 /// future I hope to refine the representation of types so as to make
1298 /// more distinctions clearer.
1299 pub struct ParameterEnvironment {
1300 /// A substitution that can be applied to move from
1301 /// the "outer" view of a type or method to the "inner" view.
1302 /// In general, this means converting from bound parameters to
1303 /// free parameters. Since we currently represent bound/free type
1304 /// parameters in the same way, this only has an effect on regions.
1305 pub free_substs: Substs,
1307 /// Bounds on the various type parameters
1308 pub bounds: VecPerParamSpace<ParamBounds>,
1310 /// Each type parameter has an implicit region bound that
1311 /// indicates it must outlive at least the function body (the user
1312 /// may specify stronger requirements). This field indicates the
1313 /// region of the callee.
1314 pub implicit_region_bound: ty::Region,
1316 /// Obligations that the caller must satisfy. This is basically
1317 /// the set of bounds on the in-scope type parameters, translated
1318 /// into Obligations.
1320 /// Note: This effectively *duplicates* the `bounds` array for
1322 pub caller_obligations: VecPerParamSpace<traits::Obligation>,
1324 /// Caches the results of trait selection. This cache is used
1325 /// for things that have to do with the parameters in scope.
1326 pub selection_cache: traits::SelectionCache,
1329 impl ParameterEnvironment {
1330 pub fn for_item(cx: &ctxt, id: NodeId) -> ParameterEnvironment {
1331 match cx.map.find(id) {
1332 Some(ast_map::NodeImplItem(ref impl_item)) => {
1334 ast::MethodImplItem(ref method) => {
1335 let method_def_id = ast_util::local_def(id);
1336 match ty::impl_or_trait_item(cx, method_def_id) {
1337 MethodTraitItem(ref method_ty) => {
1338 let method_generics = &method_ty.generics;
1339 construct_parameter_environment(
1343 method.pe_body().id)
1345 TypeTraitItem(_) => {
1347 .bug("ParameterEnvironment::from_item(): \
1348 can't create a parameter environment \
1349 for type trait items")
1353 ast::TypeImplItem(_) => {
1354 cx.sess.bug("ParameterEnvironment::from_item(): \
1355 can't create a parameter environment \
1356 for type impl items")
1360 Some(ast_map::NodeTraitItem(trait_method)) => {
1361 match *trait_method {
1362 ast::RequiredMethod(ref required) => {
1363 cx.sess.span_bug(required.span,
1364 "ParameterEnvironment::from_item():
1365 can't create a parameter \
1366 environment for required trait \
1369 ast::ProvidedMethod(ref method) => {
1370 let method_def_id = ast_util::local_def(id);
1371 match ty::impl_or_trait_item(cx, method_def_id) {
1372 MethodTraitItem(ref method_ty) => {
1373 let method_generics = &method_ty.generics;
1374 construct_parameter_environment(
1378 method.pe_body().id)
1380 TypeTraitItem(_) => {
1382 .bug("ParameterEnvironment::from_item(): \
1383 can't create a parameter environment \
1384 for type trait items")
1388 ast::TypeTraitItem(_) => {
1389 cx.sess.bug("ParameterEnvironment::from_item(): \
1390 can't create a parameter environment \
1391 for type trait items")
1395 Some(ast_map::NodeItem(item)) => {
1397 ast::ItemFn(_, _, _, _, ref body) => {
1398 // We assume this is a function.
1399 let fn_def_id = ast_util::local_def(id);
1400 let fn_pty = ty::lookup_item_type(cx, fn_def_id);
1402 construct_parameter_environment(cx,
1408 ast::ItemStruct(..) |
1410 ast::ItemConst(..) |
1411 ast::ItemStatic(..) => {
1412 let def_id = ast_util::local_def(id);
1413 let pty = ty::lookup_item_type(cx, def_id);
1414 construct_parameter_environment(cx, item.span,
1418 cx.sess.span_bug(item.span,
1419 "ParameterEnvironment::from_item():
1420 can't create a parameter \
1421 environment for this kind of item")
1426 cx.sess.bug(format!("ParameterEnvironment::from_item(): \
1427 `{}` is not an item",
1428 cx.map.node_to_string(id)).as_slice())
1436 /// - `generics`: the set of type parameters and their bounds
1437 /// - `ty`: the base types, which may reference the parameters defined
1439 #[deriving(Clone, Show)]
1440 pub struct Polytype {
1441 pub generics: Generics,
1445 /// As `Polytype` but for a trait ref.
1446 pub struct TraitDef {
1447 /// Generic type definitions. Note that `Self` is listed in here
1448 /// as having a single bound, the trait itself (e.g., in the trait
1449 /// `Eq`, there is a single bound `Self : Eq`). This is so that
1450 /// default methods get to assume that the `Self` parameters
1451 /// implements the trait.
1452 pub generics: Generics,
1454 /// The "supertrait" bounds.
1455 pub bounds: ParamBounds,
1456 pub trait_ref: Rc<ty::TraitRef>,
1459 /// Records the substitutions used to translate the polytype for an
1460 /// item into the monotype of an item reference.
1462 pub struct ItemSubsts {
1466 pub type type_cache = RefCell<DefIdMap<Polytype>>;
1468 pub type node_type_table = RefCell<HashMap<uint,t>>;
1470 /// Records information about each unboxed closure.
1472 pub struct UnboxedClosure {
1473 /// The type of the unboxed closure.
1474 pub closure_type: ClosureTy,
1475 /// The kind of unboxed closure this is.
1476 pub kind: UnboxedClosureKind,
1479 #[deriving(Clone, PartialEq, Eq, Show)]
1480 pub enum UnboxedClosureKind {
1481 FnUnboxedClosureKind,
1482 FnMutUnboxedClosureKind,
1483 FnOnceUnboxedClosureKind,
1486 impl UnboxedClosureKind {
1487 pub fn trait_did(&self, cx: &ctxt) -> ast::DefId {
1488 let result = match *self {
1489 FnUnboxedClosureKind => cx.lang_items.require(FnTraitLangItem),
1490 FnMutUnboxedClosureKind => {
1491 cx.lang_items.require(FnMutTraitLangItem)
1493 FnOnceUnboxedClosureKind => {
1494 cx.lang_items.require(FnOnceTraitLangItem)
1498 Ok(trait_did) => trait_did,
1499 Err(err) => cx.sess.fatal(err.as_slice()),
1504 pub fn mk_ctxt<'tcx>(s: Session,
1505 type_arena: &'tcx TypedArena<t_box_>,
1506 dm: resolve::DefMap,
1507 named_region_map: resolve_lifetime::NamedRegionMap,
1508 map: ast_map::Map<'tcx>,
1509 freevars: RefCell<FreevarMap>,
1510 capture_modes: RefCell<CaptureModeMap>,
1511 region_maps: middle::region::RegionMaps,
1512 lang_items: middle::lang_items::LanguageItems,
1513 stability: stability::Index) -> ctxt<'tcx> {
1515 type_arena: type_arena,
1516 interner: RefCell::new(FnvHashMap::new()),
1517 named_region_map: named_region_map,
1518 item_variance_map: RefCell::new(DefIdMap::new()),
1519 variance_computed: Cell::new(false),
1520 next_id: Cell::new(primitives::LAST_PRIMITIVE_ID),
1523 region_maps: region_maps,
1524 node_types: RefCell::new(HashMap::new()),
1525 item_substs: RefCell::new(NodeMap::new()),
1526 trait_refs: RefCell::new(NodeMap::new()),
1527 trait_defs: RefCell::new(DefIdMap::new()),
1528 object_cast_map: RefCell::new(NodeMap::new()),
1530 intrinsic_defs: RefCell::new(DefIdMap::new()),
1532 tcache: RefCell::new(DefIdMap::new()),
1533 rcache: RefCell::new(HashMap::new()),
1534 short_names_cache: RefCell::new(HashMap::new()),
1535 needs_unwind_cleanup_cache: RefCell::new(HashMap::new()),
1536 tc_cache: RefCell::new(HashMap::new()),
1537 ast_ty_to_ty_cache: RefCell::new(NodeMap::new()),
1538 enum_var_cache: RefCell::new(DefIdMap::new()),
1539 impl_or_trait_items: RefCell::new(DefIdMap::new()),
1540 trait_item_def_ids: RefCell::new(DefIdMap::new()),
1541 trait_items_cache: RefCell::new(DefIdMap::new()),
1542 impl_trait_cache: RefCell::new(DefIdMap::new()),
1543 ty_param_defs: RefCell::new(NodeMap::new()),
1544 adjustments: RefCell::new(NodeMap::new()),
1545 normalized_cache: RefCell::new(HashMap::new()),
1546 lang_items: lang_items,
1547 provided_method_sources: RefCell::new(DefIdMap::new()),
1548 struct_fields: RefCell::new(DefIdMap::new()),
1549 destructor_for_type: RefCell::new(DefIdMap::new()),
1550 destructors: RefCell::new(DefIdSet::new()),
1551 trait_impls: RefCell::new(DefIdMap::new()),
1552 inherent_impls: RefCell::new(DefIdMap::new()),
1553 impl_items: RefCell::new(DefIdMap::new()),
1554 used_unsafe: RefCell::new(NodeSet::new()),
1555 used_mut_nodes: RefCell::new(NodeSet::new()),
1556 populated_external_types: RefCell::new(DefIdSet::new()),
1557 populated_external_traits: RefCell::new(DefIdSet::new()),
1558 upvar_borrow_map: RefCell::new(HashMap::new()),
1559 extern_const_statics: RefCell::new(DefIdMap::new()),
1560 extern_const_variants: RefCell::new(DefIdMap::new()),
1561 method_map: RefCell::new(FnvHashMap::new()),
1562 dependency_formats: RefCell::new(HashMap::new()),
1563 unboxed_closures: RefCell::new(DefIdMap::new()),
1564 node_lint_levels: RefCell::new(HashMap::new()),
1565 transmute_restrictions: RefCell::new(Vec::new()),
1566 stability: RefCell::new(stability),
1567 capture_modes: capture_modes,
1568 associated_types: RefCell::new(DefIdMap::new()),
1569 trait_associated_types: RefCell::new(DefIdMap::new()),
1570 selection_cache: traits::SelectionCache::new(),
1571 repr_hint_cache: RefCell::new(DefIdMap::new()),
1575 // Type constructors
1577 // Interns a type/name combination, stores the resulting box in cx.interner,
1578 // and returns the box as cast to an unsafe ptr (see comments for t above).
1579 pub fn mk_t(cx: &ctxt, st: sty) -> t {
1580 // Check for primitive types.
1582 ty_nil => return mk_nil(),
1583 ty_err => return mk_err(),
1584 ty_bool => return mk_bool(),
1585 ty_int(i) => return mk_mach_int(i),
1586 ty_uint(u) => return mk_mach_uint(u),
1587 ty_float(f) => return mk_mach_float(f),
1588 ty_char => return mk_char(),
1592 let key = intern_key { sty: &st };
1594 match cx.interner.borrow().find(&key) {
1595 Some(t) => unsafe { return mem::transmute(&t.sty); },
1599 let mut flags = NO_TYPE_FLAGS;
1600 fn rflags(r: Region) -> TypeFlags {
1603 ty::ReInfer(_) => HAS_RE_INFER,
1608 fn sflags(substs: &Substs) -> TypeFlags {
1609 let mut f = NO_TYPE_FLAGS;
1610 let mut i = substs.types.iter();
1612 f = f | get(*tt).flags;
1614 match substs.regions {
1615 subst::ErasedRegions => {}
1616 subst::NonerasedRegions(ref regions) => {
1617 for r in regions.iter() {
1624 fn flags_for_bounds(bounds: &ExistentialBounds) -> TypeFlags {
1625 rflags(bounds.region_bound)
1628 &ty_nil | &ty_bool | &ty_char | &ty_int(_) | &ty_float(_) | &ty_uint(_) |
1630 // You might think that we could just return ty_err for
1631 // any type containing ty_err as a component, and get
1632 // rid of the HAS_TY_ERR flag -- likewise for ty_bot (with
1633 // the exception of function types that return bot).
1634 // But doing so caused sporadic memory corruption, and
1635 // neither I (tjc) nor nmatsakis could figure out why,
1636 // so we're doing it this way.
1637 &ty_err => flags = flags | HAS_TY_ERR,
1638 &ty_param(ref p) => {
1639 if p.space == subst::SelfSpace {
1640 flags = flags | HAS_SELF;
1642 flags = flags | HAS_PARAMS;
1645 &ty_unboxed_closure(_, ref region, ref substs) => {
1646 flags = flags | rflags(*region);
1647 flags = flags | sflags(substs);
1649 &ty_infer(_) => flags = flags | HAS_TY_INFER,
1650 &ty_enum(_, ref substs) | &ty_struct(_, ref substs) => {
1651 flags = flags | sflags(substs);
1653 &ty_trait(box TyTrait { ref substs, ref bounds, .. }) => {
1654 flags = flags | sflags(substs);
1655 flags = flags | flags_for_bounds(bounds);
1657 &ty_uniq(tt) | &ty_vec(tt, _) | &ty_open(tt) => {
1658 flags = flags | get(tt).flags
1661 flags = flags | get(m.ty).flags;
1663 &ty_rptr(r, ref m) => {
1664 flags = flags | rflags(r);
1665 flags = flags | get(m.ty).flags;
1667 &ty_tup(ref ts) => for tt in ts.iter() { flags = flags | get(*tt).flags; },
1668 &ty_bare_fn(ref f) => {
1669 for a in f.sig.inputs.iter() { flags = flags | get(*a).flags; }
1670 if let ty::FnConverging(output) = f.sig.output {
1671 flags = flags | get(output).flags;
1674 &ty_closure(ref f) => {
1676 RegionTraitStore(r, _) => {
1677 flags = flags | rflags(r);
1681 for a in f.sig.inputs.iter() { flags = flags | get(*a).flags; }
1682 if let ty::FnConverging(output) = f.sig.output {
1683 flags = flags | get(output).flags;
1685 flags = flags | flags_for_bounds(&f.bounds);
1689 let t = cx.type_arena.alloc(t_box_ {
1691 id: cx.next_id.get(),
1695 let sty_ptr = &t.sty as *const sty;
1697 let key = intern_key {
1701 cx.interner.borrow_mut().insert(key, t);
1703 cx.next_id.set(cx.next_id.get() + 1);
1706 mem::transmute::<*const sty, t>(sty_ptr)
1711 pub fn mk_prim_t(primitive: &'static t_box_) -> t {
1713 mem::transmute::<&'static t_box_, t>(primitive)
1718 pub fn mk_nil() -> t { mk_prim_t(&primitives::TY_NIL) }
1721 pub fn mk_err() -> t { mk_prim_t(&primitives::TY_ERR) }
1724 pub fn mk_bool() -> t { mk_prim_t(&primitives::TY_BOOL) }
1727 pub fn mk_int() -> t { mk_prim_t(&primitives::TY_INT) }
1730 pub fn mk_i8() -> t { mk_prim_t(&primitives::TY_I8) }
1733 pub fn mk_i16() -> t { mk_prim_t(&primitives::TY_I16) }
1736 pub fn mk_i32() -> t { mk_prim_t(&primitives::TY_I32) }
1739 pub fn mk_i64() -> t { mk_prim_t(&primitives::TY_I64) }
1742 pub fn mk_f32() -> t { mk_prim_t(&primitives::TY_F32) }
1745 pub fn mk_f64() -> t { mk_prim_t(&primitives::TY_F64) }
1748 pub fn mk_uint() -> t { mk_prim_t(&primitives::TY_UINT) }
1751 pub fn mk_u8() -> t { mk_prim_t(&primitives::TY_U8) }
1754 pub fn mk_u16() -> t { mk_prim_t(&primitives::TY_U16) }
1757 pub fn mk_u32() -> t { mk_prim_t(&primitives::TY_U32) }
1760 pub fn mk_u64() -> t { mk_prim_t(&primitives::TY_U64) }
1762 pub fn mk_mach_int(tm: ast::IntTy) -> t {
1764 ast::TyI => mk_int(),
1765 ast::TyI8 => mk_i8(),
1766 ast::TyI16 => mk_i16(),
1767 ast::TyI32 => mk_i32(),
1768 ast::TyI64 => mk_i64(),
1772 pub fn mk_mach_uint(tm: ast::UintTy) -> t {
1774 ast::TyU => mk_uint(),
1775 ast::TyU8 => mk_u8(),
1776 ast::TyU16 => mk_u16(),
1777 ast::TyU32 => mk_u32(),
1778 ast::TyU64 => mk_u64(),
1782 pub fn mk_mach_float(tm: ast::FloatTy) -> t {
1784 ast::TyF32 => mk_f32(),
1785 ast::TyF64 => mk_f64(),
1790 pub fn mk_char() -> t { mk_prim_t(&primitives::TY_CHAR) }
1792 pub fn mk_str(cx: &ctxt) -> t {
1796 pub fn mk_str_slice(cx: &ctxt, r: Region, m: ast::Mutability) -> t {
1799 ty: mk_t(cx, ty_str),
1804 pub fn mk_enum(cx: &ctxt, did: ast::DefId, substs: Substs) -> t {
1805 // take a copy of substs so that we own the vectors inside
1806 mk_t(cx, ty_enum(did, substs))
1809 pub fn mk_uniq(cx: &ctxt, ty: t) -> t { mk_t(cx, ty_uniq(ty)) }
1811 pub fn mk_ptr(cx: &ctxt, tm: mt) -> t { mk_t(cx, ty_ptr(tm)) }
1813 pub fn mk_rptr(cx: &ctxt, r: Region, tm: mt) -> t { mk_t(cx, ty_rptr(r, tm)) }
1815 pub fn mk_mut_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1816 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutMutable})
1818 pub fn mk_imm_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1819 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutImmutable})
1822 pub fn mk_mut_ptr(cx: &ctxt, ty: t) -> t {
1823 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutMutable})
1826 pub fn mk_imm_ptr(cx: &ctxt, ty: t) -> t {
1827 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutImmutable})
1830 pub fn mk_nil_ptr(cx: &ctxt) -> t {
1831 mk_ptr(cx, mt {ty: mk_nil(), mutbl: ast::MutImmutable})
1834 pub fn mk_vec(cx: &ctxt, t: t, sz: Option<uint>) -> t {
1835 mk_t(cx, ty_vec(t, sz))
1838 pub fn mk_slice(cx: &ctxt, r: Region, tm: mt) -> t {
1841 ty: mk_vec(cx, tm.ty, None),
1846 pub fn mk_tup(cx: &ctxt, ts: Vec<t>) -> t { mk_t(cx, ty_tup(ts)) }
1848 pub fn mk_closure(cx: &ctxt, fty: ClosureTy) -> t {
1849 mk_t(cx, ty_closure(box fty))
1852 pub fn mk_bare_fn(cx: &ctxt, fty: BareFnTy) -> t {
1853 mk_t(cx, ty_bare_fn(fty))
1856 pub fn mk_ctor_fn(cx: &ctxt,
1857 binder_id: ast::NodeId,
1858 input_tys: &[ty::t],
1859 output: ty::t) -> t {
1860 let input_args = input_tys.iter().map(|t| *t).collect();
1863 fn_style: ast::NormalFn,
1866 binder_id: binder_id,
1868 output: ty::FnConverging(output),
1875 pub fn mk_trait(cx: &ctxt,
1878 bounds: ExistentialBounds)
1880 // take a copy of substs so that we own the vectors inside
1881 let inner = box TyTrait {
1886 mk_t(cx, ty_trait(inner))
1889 pub fn mk_struct(cx: &ctxt, struct_id: ast::DefId, substs: Substs) -> t {
1890 // take a copy of substs so that we own the vectors inside
1891 mk_t(cx, ty_struct(struct_id, substs))
1894 pub fn mk_unboxed_closure(cx: &ctxt, closure_id: ast::DefId, region: Region, substs: Substs)
1896 mk_t(cx, ty_unboxed_closure(closure_id, region, substs))
1899 pub fn mk_var(cx: &ctxt, v: TyVid) -> t { mk_infer(cx, TyVar(v)) }
1901 pub fn mk_int_var(cx: &ctxt, v: IntVid) -> t { mk_infer(cx, IntVar(v)) }
1903 pub fn mk_float_var(cx: &ctxt, v: FloatVid) -> t { mk_infer(cx, FloatVar(v)) }
1905 pub fn mk_infer(cx: &ctxt, it: InferTy) -> t { mk_t(cx, ty_infer(it)) }
1907 pub fn mk_param(cx: &ctxt, space: subst::ParamSpace, n: uint, k: DefId) -> t {
1908 mk_t(cx, ty_param(ParamTy { space: space, idx: n, def_id: k }))
1911 pub fn mk_self_type(cx: &ctxt, did: ast::DefId) -> t {
1912 mk_param(cx, subst::SelfSpace, 0, did)
1915 pub fn mk_param_from_def(cx: &ctxt, def: &TypeParameterDef) -> t {
1916 mk_param(cx, def.space, def.index, def.def_id)
1919 pub fn mk_open(cx: &ctxt, t: t) -> t { mk_t(cx, ty_open(t)) }
1921 pub fn walk_ty(ty: t, f: |t|) {
1922 maybe_walk_ty(ty, |t| { f(t); true });
1925 pub fn maybe_walk_ty(ty: t, f: |t| -> bool) {
1930 ty_nil | ty_bool | ty_char | ty_int(_) | ty_uint(_) | ty_float(_) |
1931 ty_str | ty_infer(_) | ty_param(_) | ty_err => {}
1932 ty_uniq(ty) | ty_vec(ty, _) | ty_open(ty) => maybe_walk_ty(ty, f),
1933 ty_ptr(ref tm) | ty_rptr(_, ref tm) => {
1934 maybe_walk_ty(tm.ty, f);
1936 ty_enum(_, ref substs) | ty_struct(_, ref substs) | ty_unboxed_closure(_, _, ref substs) |
1937 ty_trait(box TyTrait { ref substs, .. }) => {
1938 for subty in (*substs).types.iter() {
1939 maybe_walk_ty(*subty, |x| f(x));
1942 ty_tup(ref ts) => { for tt in ts.iter() { maybe_walk_ty(*tt, |x| f(x)); } }
1943 ty_bare_fn(ref ft) => {
1944 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1945 if let ty::FnConverging(output) = ft.sig.output {
1946 maybe_walk_ty(output, f);
1949 ty_closure(ref ft) => {
1950 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1951 if let ty::FnConverging(output) = ft.sig.output {
1952 maybe_walk_ty(output, f);
1958 // Folds types from the bottom up.
1959 pub fn fold_ty(cx: &ctxt, t0: t, fldop: |t| -> t) -> t {
1960 let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
1965 pub fn new(space: subst::ParamSpace,
1969 ParamTy { space: space, idx: index, def_id: def_id }
1972 pub fn for_self(trait_def_id: ast::DefId) -> ParamTy {
1973 ParamTy::new(subst::SelfSpace, 0, trait_def_id)
1976 pub fn for_def(def: &TypeParameterDef) -> ParamTy {
1977 ParamTy::new(def.space, def.index, def.def_id)
1980 pub fn to_ty(self, tcx: &ty::ctxt) -> ty::t {
1981 ty::mk_param(tcx, self.space, self.idx, self.def_id)
1984 pub fn is_self(&self) -> bool {
1985 self.space == subst::SelfSpace && self.idx == 0
1990 pub fn empty() -> ItemSubsts {
1991 ItemSubsts { substs: Substs::empty() }
1994 pub fn is_noop(&self) -> bool {
1995 self.substs.is_noop()
2001 pub fn type_is_nil(ty: t) -> bool {
2002 get(ty).sty == ty_nil
2005 pub fn type_is_error(ty: t) -> bool {
2006 get(ty).flags.intersects(HAS_TY_ERR)
2009 pub fn type_needs_subst(ty: t) -> bool {
2010 tbox_has_flag(get(ty), NEEDS_SUBST)
2013 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
2014 tref.substs.types.any(|&t| type_is_error(t))
2017 pub fn type_is_ty_var(ty: t) -> bool {
2019 ty_infer(TyVar(_)) => true,
2024 pub fn type_is_bool(ty: t) -> bool { get(ty).sty == ty_bool }
2026 pub fn type_is_self(ty: t) -> bool {
2028 ty_param(ref p) => p.space == subst::SelfSpace,
2033 fn type_is_slice(ty: t) -> bool {
2035 ty_ptr(mt) | ty_rptr(_, mt) => match get(mt.ty).sty {
2036 ty_vec(_, None) | ty_str => true,
2043 pub fn type_is_vec(ty: t) -> bool {
2046 ty_ptr(mt{ty: t, ..}) | ty_rptr(_, mt{ty: t, ..}) |
2047 ty_uniq(t) => match get(t).sty {
2048 ty_vec(_, None) => true,
2055 pub fn type_is_structural(ty: t) -> bool {
2057 ty_struct(..) | ty_tup(_) | ty_enum(..) | ty_closure(_) |
2058 ty_vec(_, Some(_)) | ty_unboxed_closure(..) => true,
2059 _ => type_is_slice(ty) | type_is_trait(ty)
2063 pub fn type_is_simd(cx: &ctxt, ty: t) -> bool {
2065 ty_struct(did, _) => lookup_simd(cx, did),
2070 pub fn sequence_element_type(cx: &ctxt, ty: t) -> t {
2072 ty_vec(ty, _) => ty,
2073 ty_str => mk_mach_uint(ast::TyU8),
2074 ty_open(ty) => sequence_element_type(cx, ty),
2075 _ => cx.sess.bug(format!("sequence_element_type called on non-sequence value: {}",
2076 ty_to_string(cx, ty)).as_slice()),
2080 pub fn simd_type(cx: &ctxt, ty: t) -> t {
2082 ty_struct(did, ref substs) => {
2083 let fields = lookup_struct_fields(cx, did);
2084 lookup_field_type(cx, did, fields[0].id, substs)
2086 _ => panic!("simd_type called on invalid type")
2090 pub fn simd_size(cx: &ctxt, ty: t) -> uint {
2092 ty_struct(did, _) => {
2093 let fields = lookup_struct_fields(cx, did);
2096 _ => panic!("simd_size called on invalid type")
2100 pub fn type_is_region_ptr(ty: t) -> bool {
2102 ty_rptr(..) => true,
2107 pub fn type_is_unsafe_ptr(ty: t) -> bool {
2109 ty_ptr(_) => return true,
2114 pub fn type_is_unique(ty: t) -> bool {
2116 ty_uniq(_) => match get(ty).sty {
2117 ty_trait(..) => false,
2124 pub fn type_is_fat_ptr(cx: &ctxt, ty: t) -> bool {
2126 ty_ptr(mt{ty, ..}) | ty_rptr(_, mt{ty, ..})
2127 | ty_uniq(ty) if !type_is_sized(cx, ty) => true,
2133 A scalar type is one that denotes an atomic datum, with no sub-components.
2134 (A ty_ptr is scalar because it represents a non-managed pointer, so its
2135 contents are abstract to rustc.)
2137 pub fn type_is_scalar(ty: t) -> bool {
2139 ty_nil | ty_bool | ty_char | ty_int(_) | ty_float(_) | ty_uint(_) |
2140 ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) |
2141 ty_bare_fn(..) | ty_ptr(_) => true,
2146 /// Returns true if this type is a floating point type and false otherwise.
2147 pub fn type_is_floating_point(ty: t) -> bool {
2149 ty_float(_) => true,
2154 pub fn type_needs_drop(cx: &ctxt, ty: t) -> bool {
2155 type_contents(cx, ty).needs_drop(cx)
2158 // Some things don't need cleanups during unwinding because the
2159 // task can free them all at once later. Currently only things
2160 // that only contain scalars and shared boxes can avoid unwind
2162 pub fn type_needs_unwind_cleanup(cx: &ctxt, ty: t) -> bool {
2163 return memoized(&cx.needs_unwind_cleanup_cache, ty, |ty| {
2164 type_needs_unwind_cleanup_(cx, ty, &mut HashSet::new())
2167 fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t, tycache: &mut HashSet<t>) -> bool {
2168 // Prevent infinite recursion
2169 if !tycache.insert(ty) {
2173 let mut needs_unwind_cleanup = false;
2174 maybe_walk_ty(ty, |ty| {
2175 needs_unwind_cleanup |= match get(ty).sty {
2176 ty_nil | ty_bool | ty_int(_) | ty_uint(_) |
2177 ty_float(_) | ty_tup(_) | ty_ptr(_) => false,
2179 ty_enum(did, ref substs) =>
2180 enum_variants(cx, did).iter().any(|v|
2181 v.args.iter().any(|aty| {
2182 let t = aty.subst(cx, substs);
2183 type_needs_unwind_cleanup_(cx, t, tycache)
2189 !needs_unwind_cleanup
2191 needs_unwind_cleanup
2196 * Type contents is how the type checker reasons about kinds.
2197 * They track what kinds of things are found within a type. You can
2198 * think of them as kind of an "anti-kind". They track the kinds of values
2199 * and thinks that are contained in types. Having a larger contents for
2200 * a type tends to rule that type *out* from various kinds. For example,
2201 * a type that contains a reference is not sendable.
2203 * The reason we compute type contents and not kinds is that it is
2204 * easier for me (nmatsakis) to think about what is contained within
2205 * a type than to think about what is *not* contained within a type.
2208 pub struct TypeContents {
2212 macro_rules! def_type_content_sets(
2213 (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
2214 #[allow(non_snake_case)]
2216 use middle::ty::TypeContents;
2218 #[allow(non_uppercase_statics)]
2219 pub const $name: TypeContents = TypeContents { bits: $bits };
2225 def_type_content_sets!(
2227 None = 0b0000_0000__0000_0000__0000,
2229 // Things that are interior to the value (first nibble):
2230 InteriorUnsized = 0b0000_0000__0000_0000__0001,
2231 InteriorUnsafe = 0b0000_0000__0000_0000__0010,
2232 // InteriorAll = 0b00000000__00000000__1111,
2234 // Things that are owned by the value (second and third nibbles):
2235 OwnsOwned = 0b0000_0000__0000_0001__0000,
2236 OwnsDtor = 0b0000_0000__0000_0010__0000,
2237 OwnsManaged /* see [1] below */ = 0b0000_0000__0000_0100__0000,
2238 OwnsAffine = 0b0000_0000__0000_1000__0000,
2239 OwnsAll = 0b0000_0000__1111_1111__0000,
2241 // Things that are reachable by the value in any way (fourth nibble):
2242 ReachesBorrowed = 0b0000_0010__0000_0000__0000,
2243 // ReachesManaged /* see [1] below */ = 0b0000_0100__0000_0000__0000,
2244 ReachesMutable = 0b0000_1000__0000_0000__0000,
2245 ReachesFfiUnsafe = 0b0010_0000__0000_0000__0000,
2246 ReachesAll = 0b0011_1111__0000_0000__0000,
2248 // Things that cause values to *move* rather than *copy*. This
2249 // is almost the same as the `Copy` trait, but for managed
2250 // data -- atm, we consider managed data to copy, not move,
2251 // but it does not impl Copy as a pure memcpy is not good
2253 Moves = 0b0000_0000__0000_1011__0000,
2255 // Things that mean drop glue is necessary
2256 NeedsDrop = 0b0000_0000__0000_0111__0000,
2258 // Things that prevent values from being considered sized
2259 Nonsized = 0b0000_0000__0000_0000__0001,
2261 // Things that make values considered not POD (would be same
2262 // as `Moves`, but for the fact that managed data `@` is
2263 // not considered POD)
2264 Noncopy = 0b0000_0000__0000_1111__0000,
2266 // Bits to set when a managed value is encountered
2268 // [1] Do not set the bits TC::OwnsManaged or
2269 // TC::ReachesManaged directly, instead reference
2270 // TC::Managed to set them both at once.
2271 Managed = 0b0000_0100__0000_0100__0000,
2274 All = 0b1111_1111__1111_1111__1111
2279 pub fn when(&self, cond: bool) -> TypeContents {
2280 if cond {*self} else {TC::None}
2283 pub fn intersects(&self, tc: TypeContents) -> bool {
2284 (self.bits & tc.bits) != 0
2287 pub fn owns_managed(&self) -> bool {
2288 self.intersects(TC::OwnsManaged)
2291 pub fn owns_owned(&self) -> bool {
2292 self.intersects(TC::OwnsOwned)
2295 pub fn is_sized(&self, _: &ctxt) -> bool {
2296 !self.intersects(TC::Nonsized)
2299 pub fn interior_unsafe(&self) -> bool {
2300 self.intersects(TC::InteriorUnsafe)
2303 pub fn interior_unsized(&self) -> bool {
2304 self.intersects(TC::InteriorUnsized)
2307 pub fn moves_by_default(&self, _: &ctxt) -> bool {
2308 self.intersects(TC::Moves)
2311 pub fn needs_drop(&self, _: &ctxt) -> bool {
2312 self.intersects(TC::NeedsDrop)
2315 pub fn owned_pointer(&self) -> TypeContents {
2317 * Includes only those bits that still apply
2318 * when indirected through a `Box` pointer
2321 *self & (TC::OwnsAll | TC::ReachesAll))
2324 pub fn reference(&self, bits: TypeContents) -> TypeContents {
2326 * Includes only those bits that still apply
2327 * when indirected through a reference (`&`)
2330 *self & TC::ReachesAll)
2333 pub fn managed_pointer(&self) -> TypeContents {
2335 * Includes only those bits that still apply
2336 * when indirected through a managed pointer (`@`)
2339 *self & TC::ReachesAll)
2342 pub fn unsafe_pointer(&self) -> TypeContents {
2344 * Includes only those bits that still apply
2345 * when indirected through an unsafe pointer (`*`)
2347 *self & TC::ReachesAll
2350 pub fn union<T>(v: &[T], f: |&T| -> TypeContents) -> TypeContents {
2351 v.iter().fold(TC::None, |tc, t| tc | f(t))
2354 pub fn has_dtor(&self) -> bool {
2355 self.intersects(TC::OwnsDtor)
2359 impl ops::BitOr<TypeContents,TypeContents> for TypeContents {
2360 fn bitor(&self, other: &TypeContents) -> TypeContents {
2361 TypeContents {bits: self.bits | other.bits}
2365 impl ops::BitAnd<TypeContents,TypeContents> for TypeContents {
2366 fn bitand(&self, other: &TypeContents) -> TypeContents {
2367 TypeContents {bits: self.bits & other.bits}
2371 impl ops::Sub<TypeContents,TypeContents> for TypeContents {
2372 fn sub(&self, other: &TypeContents) -> TypeContents {
2373 TypeContents {bits: self.bits & !other.bits}
2377 impl fmt::Show for TypeContents {
2378 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2379 write!(f, "TypeContents({:t})", self.bits)
2383 pub fn type_interior_is_unsafe(cx: &ctxt, t: ty::t) -> bool {
2384 type_contents(cx, t).interior_unsafe()
2387 pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
2388 return memoized_with_key(&cx.tc_cache, ty, |ty| {
2389 tc_ty(cx, ty, &mut HashMap::new())
2390 }, |&ty| type_id(ty));
2394 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2396 // Subtle: Note that we are *not* using cx.tc_cache here but rather a
2397 // private cache for this walk. This is needed in the case of cyclic
2400 // struct List { next: Box<Option<List>>, ... }
2402 // When computing the type contents of such a type, we wind up deeply
2403 // recursing as we go. So when we encounter the recursive reference
2404 // to List, we temporarily use TC::None as its contents. Later we'll
2405 // patch up the cache with the correct value, once we've computed it
2406 // (this is basically a co-inductive process, if that helps). So in
2407 // the end we'll compute TC::OwnsOwned, in this case.
2409 // The problem is, as we are doing the computation, we will also
2410 // compute an *intermediate* contents for, e.g., Option<List> of
2411 // TC::None. This is ok during the computation of List itself, but if
2412 // we stored this intermediate value into cx.tc_cache, then later
2413 // requests for the contents of Option<List> would also yield TC::None
2414 // which is incorrect. This value was computed based on the crutch
2415 // value for the type contents of list. The correct value is
2416 // TC::OwnsOwned. This manifested as issue #4821.
2417 let ty_id = type_id(ty);
2418 match cache.find(&ty_id) {
2419 Some(tc) => { return *tc; }
2422 match cx.tc_cache.borrow().find(&ty_id) { // Must check both caches!
2423 Some(tc) => { return *tc; }
2426 cache.insert(ty_id, TC::None);
2428 let result = match get(ty).sty {
2429 // uint and int are ffi-unsafe
2430 ty_uint(ast::TyU) | ty_int(ast::TyI) => {
2431 TC::ReachesFfiUnsafe
2434 // Scalar and unique types are sendable, and durable
2435 ty_infer(ty::SkolemizedIntTy(_)) |
2436 ty_nil | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
2437 ty_bare_fn(_) | ty::ty_char => {
2441 ty_closure(ref c) => {
2442 closure_contents(cx, &**c) | TC::ReachesFfiUnsafe
2446 TC::ReachesFfiUnsafe | match get(typ).sty {
2447 ty_str => TC::OwnsOwned,
2448 _ => tc_ty(cx, typ, cache).owned_pointer(),
2452 ty_trait(box TyTrait { bounds, .. }) => {
2453 object_contents(cx, bounds) | TC::ReachesFfiUnsafe | TC::Nonsized
2457 tc_ty(cx, mt.ty, cache).unsafe_pointer()
2460 ty_rptr(r, ref mt) => {
2461 TC::ReachesFfiUnsafe | match get(mt.ty).sty {
2462 ty_str => borrowed_contents(r, ast::MutImmutable),
2463 ty_vec(..) => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(r, mt.mutbl)),
2464 _ => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(r, mt.mutbl)),
2468 ty_vec(t, Some(_)) => {
2472 ty_vec(t, None) => {
2473 tc_ty(cx, t, cache) | TC::Nonsized
2475 ty_str => TC::Nonsized,
2477 ty_struct(did, ref substs) => {
2478 let flds = struct_fields(cx, did, substs);
2480 TypeContents::union(flds.as_slice(),
2481 |f| tc_mt(cx, f.mt, cache));
2483 if !lookup_repr_hints(cx, did).contains(&attr::ReprExtern) {
2484 res = res | TC::ReachesFfiUnsafe;
2487 if ty::has_dtor(cx, did) {
2488 res = res | TC::OwnsDtor;
2490 apply_lang_items(cx, did, res)
2493 ty_unboxed_closure(did, r, ref substs) => {
2494 // FIXME(#14449): `borrowed_contents` below assumes `&mut`
2496 let upvars = unboxed_closure_upvars(cx, did, substs);
2497 TypeContents::union(upvars.as_slice(),
2498 |f| tc_ty(cx, f.ty, cache)) |
2499 borrowed_contents(r, MutMutable)
2502 ty_tup(ref tys) => {
2503 TypeContents::union(tys.as_slice(),
2504 |ty| tc_ty(cx, *ty, cache))
2507 ty_enum(did, ref substs) => {
2508 let variants = substd_enum_variants(cx, did, substs);
2510 TypeContents::union(variants.as_slice(), |variant| {
2511 TypeContents::union(variant.args.as_slice(),
2513 tc_ty(cx, *arg_ty, cache)
2517 if ty::has_dtor(cx, did) {
2518 res = res | TC::OwnsDtor;
2521 if variants.len() != 0 {
2522 let repr_hints = lookup_repr_hints(cx, did);
2523 if repr_hints.len() > 1 {
2524 // this is an error later on, but this type isn't safe
2525 res = res | TC::ReachesFfiUnsafe;
2528 match repr_hints.as_slice().get(0) {
2529 Some(h) => if !h.is_ffi_safe() {
2530 res = res | TC::ReachesFfiUnsafe;
2534 res = res | TC::ReachesFfiUnsafe;
2536 // We allow ReprAny enums if they are eligible for
2537 // the nullable pointer optimization and the
2538 // contained type is an `extern fn`
2540 if variants.len() == 2 {
2541 let mut data_idx = 0;
2543 if variants[0].args.len() == 0 {
2547 if variants[data_idx].args.len() == 1 {
2548 match get(variants[data_idx].args[0]).sty {
2549 ty_bare_fn(..) => { res = res - TC::ReachesFfiUnsafe; }
2559 apply_lang_items(cx, did, res)
2563 // We only ever ask for the kind of types that are defined in
2564 // the current crate; therefore, the only type parameters that
2565 // could be in scope are those defined in the current crate.
2566 // If this assertion fails, it is likely because of a
2567 // failure of the cross-crate inlining code to translate a
2569 assert_eq!(p.def_id.krate, ast::LOCAL_CRATE);
2571 let ty_param_defs = cx.ty_param_defs.borrow();
2572 let tp_def = &(*ty_param_defs)[p.def_id.node];
2573 kind_bounds_to_contents(
2575 tp_def.bounds.builtin_bounds,
2576 tp_def.bounds.trait_bounds.as_slice())
2580 // This occurs during coherence, but shouldn't occur at other
2586 let result = tc_ty(cx, t, cache);
2587 assert!(!result.is_sized(cx))
2588 result.unsafe_pointer() | TC::Nonsized
2592 cx.sess.bug("asked to compute contents of error type");
2596 cache.insert(ty_id, result);
2602 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2604 let mc = TC::ReachesMutable.when(mt.mutbl == MutMutable);
2605 mc | tc_ty(cx, mt.ty, cache)
2608 fn apply_lang_items(cx: &ctxt,
2613 if Some(did) == cx.lang_items.managed_bound() {
2615 } else if Some(did) == cx.lang_items.no_copy_bound() {
2617 } else if Some(did) == cx.lang_items.unsafe_type() {
2618 tc | TC::InteriorUnsafe
2624 fn borrowed_contents(region: ty::Region,
2625 mutbl: ast::Mutability)
2628 * Type contents due to containing a reference
2629 * with the region `region` and borrow kind `bk`
2632 let b = match mutbl {
2633 ast::MutMutable => TC::ReachesMutable | TC::OwnsAffine,
2634 ast::MutImmutable => TC::None,
2636 b | (TC::ReachesBorrowed).when(region != ty::ReStatic)
2639 fn closure_contents(cx: &ctxt, cty: &ClosureTy) -> TypeContents {
2640 // Closure contents are just like trait contents, but with potentially
2642 let st = object_contents(cx, cty.bounds);
2644 let st = match cty.store {
2648 RegionTraitStore(r, mutbl) => {
2649 st.reference(borrowed_contents(r, mutbl))
2653 // This also prohibits "@once fn" from being copied, which allows it to
2654 // be called. Neither way really makes much sense.
2655 let ot = match cty.onceness {
2656 ast::Once => TC::OwnsAffine,
2657 ast::Many => TC::None,
2663 fn object_contents(cx: &ctxt,
2664 bounds: ExistentialBounds)
2666 // These are the type contents of the (opaque) interior
2667 kind_bounds_to_contents(cx, bounds.builtin_bounds, [])
2670 fn kind_bounds_to_contents(cx: &ctxt,
2671 bounds: BuiltinBounds,
2672 traits: &[Rc<TraitRef>])
2674 let _i = indenter();
2675 let mut tc = TC::All;
2676 each_inherited_builtin_bound(cx, bounds, traits, |bound| {
2677 tc = tc - match bound {
2678 BoundSync | BoundSend => TC::None,
2679 BoundSized => TC::Nonsized,
2680 BoundCopy => TC::Noncopy,
2685 // Iterates over all builtin bounds on the type parameter def, including
2686 // those inherited from traits with builtin-kind-supertraits.
2687 fn each_inherited_builtin_bound(cx: &ctxt,
2688 bounds: BuiltinBounds,
2689 traits: &[Rc<TraitRef>],
2690 f: |BuiltinBound|) {
2691 for bound in bounds.iter() {
2695 each_bound_trait_and_supertraits(cx, traits, |trait_ref| {
2696 let trait_def = lookup_trait_def(cx, trait_ref.def_id);
2697 for bound in trait_def.bounds.builtin_bounds.iter() {
2706 pub fn type_moves_by_default(cx: &ctxt, ty: t) -> bool {
2707 type_contents(cx, ty).moves_by_default(cx)
2710 pub fn is_ffi_safe(cx: &ctxt, ty: t) -> bool {
2711 !type_contents(cx, ty).intersects(TC::ReachesFfiUnsafe)
2714 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
2715 pub fn is_instantiable(cx: &ctxt, r_ty: t) -> bool {
2716 fn type_requires(cx: &ctxt, seen: &mut Vec<DefId>,
2717 r_ty: t, ty: t) -> bool {
2718 debug!("type_requires({}, {})?",
2719 ::util::ppaux::ty_to_string(cx, r_ty),
2720 ::util::ppaux::ty_to_string(cx, ty));
2723 get(r_ty).sty == get(ty).sty ||
2724 subtypes_require(cx, seen, r_ty, ty)
2727 debug!("type_requires({}, {})? {}",
2728 ::util::ppaux::ty_to_string(cx, r_ty),
2729 ::util::ppaux::ty_to_string(cx, ty),
2734 fn subtypes_require(cx: &ctxt, seen: &mut Vec<DefId>,
2735 r_ty: t, ty: t) -> bool {
2736 debug!("subtypes_require({}, {})?",
2737 ::util::ppaux::ty_to_string(cx, r_ty),
2738 ::util::ppaux::ty_to_string(cx, ty));
2740 let r = match get(ty).sty {
2741 // fixed length vectors need special treatment compared to
2742 // normal vectors, since they don't necessarily have the
2743 // possibility to have length zero.
2744 ty_vec(_, Some(0)) => false, // don't need no contents
2745 ty_vec(ty, Some(_)) => type_requires(cx, seen, r_ty, ty),
2759 ty_vec(_, None) => {
2762 ty_uniq(typ) | ty_open(typ) => {
2763 type_requires(cx, seen, r_ty, typ)
2765 ty_rptr(_, ref mt) => {
2766 type_requires(cx, seen, r_ty, mt.ty)
2770 false // unsafe ptrs can always be NULL
2777 ty_struct(ref did, _) if seen.contains(did) => {
2781 ty_struct(did, ref substs) => {
2783 let fields = struct_fields(cx, did, substs);
2784 let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
2785 seen.pop().unwrap();
2789 ty_unboxed_closure(did, _, ref substs) => {
2790 let upvars = unboxed_closure_upvars(cx, did, substs);
2791 upvars.iter().any(|f| type_requires(cx, seen, r_ty, f.ty))
2795 ts.iter().any(|t| type_requires(cx, seen, r_ty, *t))
2798 ty_enum(ref did, _) if seen.contains(did) => {
2802 ty_enum(did, ref substs) => {
2804 let vs = enum_variants(cx, did);
2805 let r = !vs.is_empty() && vs.iter().all(|variant| {
2806 variant.args.iter().any(|aty| {
2807 let sty = aty.subst(cx, substs);
2808 type_requires(cx, seen, r_ty, sty)
2811 seen.pop().unwrap();
2816 debug!("subtypes_require({}, {})? {}",
2817 ::util::ppaux::ty_to_string(cx, r_ty),
2818 ::util::ppaux::ty_to_string(cx, ty),
2824 let mut seen = Vec::new();
2825 !subtypes_require(cx, &mut seen, r_ty, r_ty)
2828 /// Describes whether a type is representable. For types that are not
2829 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
2830 /// distinguish between types that are recursive with themselves and types that
2831 /// contain a different recursive type. These cases can therefore be treated
2832 /// differently when reporting errors.
2834 /// The ordering of the cases is significant. They are sorted so that cmp::max
2835 /// will keep the "more erroneous" of two values.
2836 #[deriving(PartialOrd, Ord, Eq, PartialEq, Show)]
2837 pub enum Representability {
2843 /// Check whether a type is representable. This means it cannot contain unboxed
2844 /// structural recursion. This check is needed for structs and enums.
2845 pub fn is_type_representable(cx: &ctxt, sp: Span, ty: t) -> Representability {
2847 // Iterate until something non-representable is found
2848 fn find_nonrepresentable<It: Iterator<t>>(cx: &ctxt, sp: Span, seen: &mut Vec<t>,
2849 mut iter: It) -> Representability {
2850 iter.fold(Representable,
2851 |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
2854 fn are_inner_types_recursive(cx: &ctxt, sp: Span,
2855 seen: &mut Vec<t>, ty: t) -> Representability {
2858 find_nonrepresentable(cx, sp, seen, ts.iter().map(|t| *t))
2860 // Fixed-length vectors.
2861 // FIXME(#11924) Behavior undecided for zero-length vectors.
2862 ty_vec(ty, Some(_)) => {
2863 is_type_structurally_recursive(cx, sp, seen, ty)
2865 ty_struct(did, ref substs) => {
2866 let fields = struct_fields(cx, did, substs);
2867 find_nonrepresentable(cx, sp, seen, fields.iter().map(|f| f.mt.ty))
2869 ty_enum(did, ref substs) => {
2870 let vs = enum_variants(cx, did);
2871 let iter = vs.iter()
2872 .flat_map(|variant| { variant.args.iter() })
2873 .map(|aty| { aty.subst_spanned(cx, substs, Some(sp)) });
2875 find_nonrepresentable(cx, sp, seen, iter)
2877 ty_unboxed_closure(did, _, ref substs) => {
2878 let upvars = unboxed_closure_upvars(cx, did, substs);
2879 find_nonrepresentable(cx, sp, seen, upvars.iter().map(|f| f.ty))
2885 fn same_struct_or_enum_def_id(ty: t, did: DefId) -> bool {
2887 ty_struct(ty_did, _) | ty_enum(ty_did, _) => {
2894 fn same_type(a: t, b: t) -> bool {
2895 match (&get(a).sty, &get(b).sty) {
2896 (&ty_struct(did_a, ref substs_a), &ty_struct(did_b, ref substs_b)) |
2897 (&ty_enum(did_a, ref substs_a), &ty_enum(did_b, ref substs_b)) => {
2902 let types_a = substs_a.types.get_slice(subst::TypeSpace);
2903 let types_b = substs_b.types.get_slice(subst::TypeSpace);
2905 let mut pairs = types_a.iter().zip(types_b.iter());
2907 pairs.all(|(&a, &b)| same_type(a, b))
2910 type_id(a) == type_id(b)
2915 // Does the type `ty` directly (without indirection through a pointer)
2916 // contain any types on stack `seen`?
2917 fn is_type_structurally_recursive(cx: &ctxt, sp: Span, seen: &mut Vec<t>,
2918 ty: t) -> Representability {
2919 debug!("is_type_structurally_recursive: {}",
2920 ::util::ppaux::ty_to_string(cx, ty));
2923 ty_struct(did, _) | ty_enum(did, _) => {
2925 // Iterate through stack of previously seen types.
2926 let mut iter = seen.iter();
2928 // The first item in `seen` is the type we are actually curious about.
2929 // We want to return SelfRecursive if this type contains itself.
2930 // It is important that we DON'T take generic parameters into account
2931 // for this check, so that Bar<T> in this example counts as SelfRecursive:
2934 // struct Bar<T> { x: Bar<Foo> }
2937 Some(&seen_type) => {
2938 if same_struct_or_enum_def_id(seen_type, did) {
2939 debug!("SelfRecursive: {} contains {}",
2940 ::util::ppaux::ty_to_string(cx, seen_type),
2941 ::util::ppaux::ty_to_string(cx, ty));
2942 return SelfRecursive;
2948 // We also need to know whether the first item contains other types that
2949 // are structurally recursive. If we don't catch this case, we will recurse
2950 // infinitely for some inputs.
2952 // It is important that we DO take generic parameters into account here,
2953 // so that code like this is considered SelfRecursive, not ContainsRecursive:
2955 // struct Foo { Option<Option<Foo>> }
2957 for &seen_type in iter {
2958 if same_type(ty, seen_type) {
2959 debug!("ContainsRecursive: {} contains {}",
2960 ::util::ppaux::ty_to_string(cx, seen_type),
2961 ::util::ppaux::ty_to_string(cx, ty));
2962 return ContainsRecursive;
2967 // For structs and enums, track all previously seen types by pushing them
2968 // onto the 'seen' stack.
2970 let out = are_inner_types_recursive(cx, sp, seen, ty);
2975 // No need to push in other cases.
2976 are_inner_types_recursive(cx, sp, seen, ty)
2981 debug!("is_type_representable: {}",
2982 ::util::ppaux::ty_to_string(cx, ty));
2984 // To avoid a stack overflow when checking an enum variant or struct that
2985 // contains a different, structurally recursive type, maintain a stack
2986 // of seen types and check recursion for each of them (issues #3008, #3779).
2987 let mut seen: Vec<t> = Vec::new();
2988 let r = is_type_structurally_recursive(cx, sp, &mut seen, ty);
2989 debug!("is_type_representable: {} is {}",
2990 ::util::ppaux::ty_to_string(cx, ty), r);
2994 pub fn type_is_trait(ty: t) -> bool {
2995 type_trait_info(ty).is_some()
2998 pub fn type_trait_info(ty: t) -> Option<&'static TyTrait> {
3000 ty_uniq(ty) | ty_rptr(_, mt { ty, ..}) | ty_ptr(mt { ty, ..}) => match get(ty).sty {
3001 ty_trait(ref t) => Some(&**t),
3004 ty_trait(ref t) => Some(&**t),
3009 pub fn type_is_integral(ty: t) -> bool {
3011 ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
3016 pub fn type_is_skolemized(ty: t) -> bool {
3018 ty_infer(SkolemizedTy(_)) => true,
3019 ty_infer(SkolemizedIntTy(_)) => true,
3024 pub fn type_is_uint(ty: t) -> bool {
3026 ty_infer(IntVar(_)) | ty_uint(ast::TyU) => true,
3031 pub fn type_is_char(ty: t) -> bool {
3038 pub fn type_is_bare_fn(ty: t) -> bool {
3040 ty_bare_fn(..) => true,
3045 pub fn type_is_fp(ty: t) -> bool {
3047 ty_infer(FloatVar(_)) | ty_float(_) => true,
3052 pub fn type_is_numeric(ty: t) -> bool {
3053 return type_is_integral(ty) || type_is_fp(ty);
3056 pub fn type_is_signed(ty: t) -> bool {
3063 pub fn type_is_machine(ty: t) -> bool {
3065 ty_int(ast::TyI) | ty_uint(ast::TyU) => false,
3066 ty_int(..) | ty_uint(..) | ty_float(..) => true,
3071 // Is the type's representation size known at compile time?
3072 pub fn type_is_sized(cx: &ctxt, ty: t) -> bool {
3073 type_contents(cx, ty).is_sized(cx)
3076 pub fn lltype_is_sized(cx: &ctxt, ty: t) -> bool {
3079 _ => type_contents(cx, ty).is_sized(cx)
3083 // Return the smallest part of t which is unsized. Fails if t is sized.
3084 // 'Smallest' here means component of the static representation of the type; not
3085 // the size of an object at runtime.
3086 pub fn unsized_part_of_type(cx: &ctxt, ty: t) -> t {
3088 ty_str | ty_trait(..) | ty_vec(..) => ty,
3089 ty_struct(def_id, ref substs) => {
3090 let unsized_fields: Vec<_> = struct_fields(cx, def_id, substs).iter()
3091 .map(|f| f.mt.ty).filter(|ty| !type_is_sized(cx, *ty)).collect();
3092 // Exactly one of the fields must be unsized.
3093 assert!(unsized_fields.len() == 1)
3095 unsized_part_of_type(cx, unsized_fields[0])
3098 assert!(type_is_sized(cx, ty),
3099 "unsized_part_of_type failed even though ty is unsized");
3100 panic!("called unsized_part_of_type with sized ty");
3105 // Whether a type is enum like, that is an enum type with only nullary
3107 pub fn type_is_c_like_enum(cx: &ctxt, ty: t) -> bool {
3109 ty_enum(did, _) => {
3110 let variants = enum_variants(cx, did);
3111 if variants.len() == 0 {
3114 variants.iter().all(|v| v.args.len() == 0)
3121 // Returns the type and mutability of *t.
3123 // The parameter `explicit` indicates if this is an *explicit* dereference.
3124 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
3125 pub fn deref(t: t, explicit: bool) -> Option<mt> {
3130 mutbl: ast::MutImmutable,
3133 ty_rptr(_, mt) => Some(mt),
3134 ty_ptr(mt) if explicit => Some(mt),
3139 pub fn deref_or_dont(t: t) -> t {
3142 ty_rptr(_, mt) | ty_ptr(mt) => mt.ty,
3147 pub fn close_type(cx: &ctxt, t: t) -> t {
3149 ty_open(t) => mk_rptr(cx, ReStatic, mt {ty: t, mutbl:ast::MutImmutable}),
3150 _ => cx.sess.bug(format!("Trying to close a non-open type {}",
3151 ty_to_string(cx, t)).as_slice())
3155 pub fn type_content(t: t) -> t {
3158 ty_rptr(_, mt) |ty_ptr(mt) => mt.ty,
3164 // Extract the unsized type in an open type (or just return t if it is not open).
3165 pub fn unopen_type(t: t) -> t {
3172 // Returns the type of t[i]
3173 pub fn index(ty: t) -> Option<t> {
3175 ty_vec(t, _) => Some(t),
3180 // Returns the type of elements contained within an 'array-like' type.
3181 // This is exactly the same as the above, except it supports strings,
3182 // which can't actually be indexed.
3183 pub fn array_element_ty(t: t) -> Option<t> {
3185 ty_vec(t, _) => Some(t),
3186 ty_str => Some(mk_u8()),
3191 pub fn node_id_to_trait_ref(cx: &ctxt, id: ast::NodeId) -> Rc<ty::TraitRef> {
3192 match cx.trait_refs.borrow().find(&id) {
3193 Some(t) => t.clone(),
3194 None => cx.sess.bug(
3195 format!("node_id_to_trait_ref: no trait ref for node `{}`",
3196 cx.map.node_to_string(id)).as_slice())
3200 pub fn try_node_id_to_type(cx: &ctxt, id: ast::NodeId) -> Option<t> {
3201 cx.node_types.borrow().find_copy(&(id as uint))
3204 pub fn node_id_to_type(cx: &ctxt, id: ast::NodeId) -> t {
3205 match try_node_id_to_type(cx, id) {
3207 None => cx.sess.bug(
3208 format!("node_id_to_type: no type for node `{}`",
3209 cx.map.node_to_string(id)).as_slice())
3213 pub fn node_id_to_type_opt(cx: &ctxt, id: ast::NodeId) -> Option<t> {
3214 match cx.node_types.borrow().find(&(id as uint)) {
3215 Some(&t) => Some(t),
3220 pub fn node_id_item_substs(cx: &ctxt, id: ast::NodeId) -> ItemSubsts {
3221 match cx.item_substs.borrow().find(&id) {
3222 None => ItemSubsts::empty(),
3223 Some(ts) => ts.clone(),
3227 pub fn fn_is_variadic(fty: t) -> bool {
3228 match get(fty).sty {
3229 ty_bare_fn(ref f) => f.sig.variadic,
3230 ty_closure(ref f) => f.sig.variadic,
3232 panic!("fn_is_variadic() called on non-fn type: {}", s)
3237 pub fn ty_fn_sig(fty: t) -> FnSig {
3238 match get(fty).sty {
3239 ty_bare_fn(ref f) => f.sig.clone(),
3240 ty_closure(ref f) => f.sig.clone(),
3242 panic!("ty_fn_sig() called on non-fn type: {}", s)
3247 /// Returns the ABI of the given function.
3248 pub fn ty_fn_abi(fty: t) -> abi::Abi {
3249 match get(fty).sty {
3250 ty_bare_fn(ref f) => f.abi,
3251 ty_closure(ref f) => f.abi,
3252 _ => panic!("ty_fn_abi() called on non-fn type"),
3256 // Type accessors for substructures of types
3257 pub fn ty_fn_args(fty: t) -> Vec<t> {
3258 match get(fty).sty {
3259 ty_bare_fn(ref f) => f.sig.inputs.clone(),
3260 ty_closure(ref f) => f.sig.inputs.clone(),
3262 panic!("ty_fn_args() called on non-fn type: {}", s)
3267 pub fn ty_closure_store(fty: t) -> TraitStore {
3268 match get(fty).sty {
3269 ty_closure(ref f) => f.store,
3270 ty_unboxed_closure(..) => {
3271 // Close enough for the purposes of all the callers of this
3272 // function (which is soon to be deprecated anyhow).
3276 panic!("ty_closure_store() called on non-closure type: {}", s)
3281 pub fn ty_fn_ret(fty: t) -> FnOutput {
3282 match get(fty).sty {
3283 ty_bare_fn(ref f) => f.sig.output,
3284 ty_closure(ref f) => f.sig.output,
3286 panic!("ty_fn_ret() called on non-fn type: {}", s)
3291 pub fn is_fn_ty(fty: t) -> bool {
3292 match get(fty).sty {
3293 ty_bare_fn(_) => true,
3294 ty_closure(_) => true,
3299 pub fn ty_region(tcx: &ctxt,
3307 format!("ty_region() invoked on an inappropriate ty: {}",
3313 pub fn free_region_from_def(free_id: ast::NodeId, def: &RegionParameterDef)
3316 ty::ReFree(ty::FreeRegion { scope_id: free_id,
3317 bound_region: ty::BrNamed(def.def_id,
3321 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
3322 // doesn't provide type parameter substitutions.
3323 pub fn pat_ty(cx: &ctxt, pat: &ast::Pat) -> t {
3324 return node_id_to_type(cx, pat.id);
3328 // Returns the type of an expression as a monotype.
3330 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression. That is, in
3331 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
3332 // auto-ref. The type returned by this function does not consider such
3333 // adjustments. See `expr_ty_adjusted()` instead.
3335 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
3336 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
3337 // instead of "fn(t) -> T with T = int".
3338 pub fn expr_ty(cx: &ctxt, expr: &ast::Expr) -> t {
3339 return node_id_to_type(cx, expr.id);
3342 pub fn expr_ty_opt(cx: &ctxt, expr: &ast::Expr) -> Option<t> {
3343 return node_id_to_type_opt(cx, expr.id);
3346 pub fn expr_ty_adjusted(cx: &ctxt, expr: &ast::Expr) -> t {
3349 * Returns the type of `expr`, considering any `AutoAdjustment`
3350 * entry recorded for that expression.
3352 * It would almost certainly be better to store the adjusted ty in with
3353 * the `AutoAdjustment`, but I opted not to do this because it would
3354 * require serializing and deserializing the type and, although that's not
3355 * hard to do, I just hate that code so much I didn't want to touch it
3356 * unless it was to fix it properly, which seemed a distraction from the
3357 * task at hand! -nmatsakis
3360 adjust_ty(cx, expr.span, expr.id, expr_ty(cx, expr),
3361 cx.adjustments.borrow().find(&expr.id),
3362 |method_call| cx.method_map.borrow().find(&method_call).map(|method| method.ty))
3365 pub fn expr_span(cx: &ctxt, id: NodeId) -> Span {
3366 match cx.map.find(id) {
3367 Some(ast_map::NodeExpr(e)) => {
3371 cx.sess.bug(format!("Node id {} is not an expr: {}",
3376 cx.sess.bug(format!("Node id {} is not present \
3377 in the node map", id).as_slice());
3382 pub fn local_var_name_str(cx: &ctxt, id: NodeId) -> InternedString {
3383 match cx.map.find(id) {
3384 Some(ast_map::NodeLocal(pat)) => {
3386 ast::PatIdent(_, ref path1, _) => {
3387 token::get_ident(path1.node)
3391 format!("Variable id {} maps to {}, not local",
3398 cx.sess.bug(format!("Variable id {} maps to {}, not local",
3405 pub fn adjust_ty(cx: &ctxt,
3407 expr_id: ast::NodeId,
3408 unadjusted_ty: ty::t,
3409 adjustment: Option<&AutoAdjustment>,
3410 method_type: |typeck::MethodCall| -> Option<ty::t>)
3412 /*! See `expr_ty_adjusted` */
3414 match get(unadjusted_ty).sty {
3415 ty_err => return unadjusted_ty,
3419 return match adjustment {
3420 Some(adjustment) => {
3422 AdjustAddEnv(store) => {
3423 match ty::get(unadjusted_ty).sty {
3424 ty::ty_bare_fn(ref b) => {
3425 let bounds = ty::ExistentialBounds {
3426 region_bound: ReStatic,
3427 builtin_bounds: all_builtin_bounds(),
3432 ty::ClosureTy {fn_style: b.fn_style,
3433 onceness: ast::Many,
3441 format!("add_env adjustment on non-bare-fn: \
3448 AdjustDerefRef(ref adj) => {
3449 let mut adjusted_ty = unadjusted_ty;
3451 if !ty::type_is_error(adjusted_ty) {
3452 for i in range(0, adj.autoderefs) {
3453 let method_call = typeck::MethodCall::autoderef(expr_id, i);
3454 match method_type(method_call) {
3455 Some(method_ty) => {
3456 if let ty::FnConverging(result_type) = ty_fn_ret(method_ty) {
3457 adjusted_ty = result_type;
3462 match deref(adjusted_ty, true) {
3463 Some(mt) => { adjusted_ty = mt.ty; }
3467 format!("the {}th autoderef failed: \
3470 ty_to_string(cx, adjusted_ty))
3478 None => adjusted_ty,
3479 Some(ref autoref) => adjust_for_autoref(cx, span, adjusted_ty, autoref)
3484 None => unadjusted_ty
3487 fn adjust_for_autoref(cx: &ctxt,
3490 autoref: &AutoRef) -> ty::t{
3492 AutoPtr(r, m, ref a) => {
3493 let adjusted_ty = match a {
3494 &Some(box ref a) => adjust_for_autoref(cx, span, ty, a),
3503 AutoUnsafe(m, ref a) => {
3504 let adjusted_ty = match a {
3505 &Some(box ref a) => adjust_for_autoref(cx, span, ty, a),
3508 mk_ptr(cx, mt {ty: adjusted_ty, mutbl: m})
3511 AutoUnsize(ref k) => unsize_ty(cx, ty, k, span),
3512 AutoUnsizeUniq(ref k) => ty::mk_uniq(cx, unsize_ty(cx, ty, k, span)),
3517 // Take a sized type and a sizing adjustment and produce an unsized version of
3519 pub fn unsize_ty(cx: &ctxt,
3525 &UnsizeLength(len) => match get(ty).sty {
3526 ty_vec(t, Some(n)) => {
3530 _ => cx.sess.span_bug(span,
3531 format!("UnsizeLength with bad sty: {}",
3532 ty_to_string(cx, ty)).as_slice())
3534 &UnsizeStruct(box ref k, tp_index) => match get(ty).sty {
3535 ty_struct(did, ref substs) => {
3536 let ty_substs = substs.types.get_slice(subst::TypeSpace);
3537 let new_ty = unsize_ty(cx, ty_substs[tp_index], k, span);
3538 let mut unsized_substs = substs.clone();
3539 unsized_substs.types.get_mut_slice(subst::TypeSpace)[tp_index] = new_ty;
3540 mk_struct(cx, did, unsized_substs)
3542 _ => cx.sess.span_bug(span,
3543 format!("UnsizeStruct with bad sty: {}",
3544 ty_to_string(cx, ty)).as_slice())
3546 &UnsizeVtable(TyTrait { def_id, ref substs, bounds }, _) => {
3547 mk_trait(cx, def_id, substs.clone(), bounds)
3552 pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> def::Def {
3553 match tcx.def_map.borrow().find(&expr.id) {
3556 tcx.sess.span_bug(expr.span, format!(
3557 "no def-map entry for expr {}", expr.id).as_slice());
3562 pub fn expr_is_lval(tcx: &ctxt, e: &ast::Expr) -> bool {
3563 match expr_kind(tcx, e) {
3565 RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
3569 /// We categorize expressions into three kinds. The distinction between
3570 /// lvalue/rvalue is fundamental to the language. The distinction between the
3571 /// two kinds of rvalues is an artifact of trans which reflects how we will
3572 /// generate code for that kind of expression. See trans/expr.rs for more
3581 pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
3582 if tcx.method_map.borrow().contains_key(&typeck::MethodCall::expr(expr.id)) {
3583 // Overloaded operations are generally calls, and hence they are
3584 // generated via DPS, but there are a few exceptions:
3585 return match expr.node {
3586 // `a += b` has a unit result.
3587 ast::ExprAssignOp(..) => RvalueStmtExpr,
3589 // the deref method invoked for `*a` always yields an `&T`
3590 ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
3592 // the index method invoked for `a[i]` always yields an `&T`
3593 ast::ExprIndex(..) => LvalueExpr,
3595 // the slice method invoked for `a[..]` always yields an `&T`
3596 ast::ExprSlice(..) => LvalueExpr,
3598 // `for` loops are statements
3599 ast::ExprForLoop(..) => RvalueStmtExpr,
3601 // in the general case, result could be any type, use DPS
3607 ast::ExprPath(..) => {
3608 match resolve_expr(tcx, expr) {
3609 def::DefVariant(tid, vid, _) => {
3610 let variant_info = enum_variant_with_id(tcx, tid, vid);
3611 if variant_info.args.len() > 0u {
3620 def::DefStruct(_) => {
3621 match get(expr_ty(tcx, expr)).sty {
3622 ty_bare_fn(..) => RvalueDatumExpr,
3627 // Special case: A unit like struct's constructor must be called without () at the
3628 // end (like `UnitStruct`) which means this is an ExprPath to a DefFn. But in case
3629 // of unit structs this is should not be interpreted as function pointer but as
3630 // call to the constructor.
3631 def::DefFn(_, _, true) => RvalueDpsExpr,
3633 // Fn pointers are just scalar values.
3634 def::DefFn(..) | def::DefStaticMethod(..) | def::DefMethod(..) => RvalueDatumExpr,
3636 // Note: there is actually a good case to be made that
3637 // DefArg's, particularly those of immediate type, ought to
3638 // considered rvalues.
3639 def::DefStatic(..) |
3641 def::DefLocal(..) => LvalueExpr,
3643 def::DefConst(..) => RvalueDatumExpr,
3648 format!("uncategorized def for expr {}: {}",
3655 ast::ExprUnary(ast::UnDeref, _) |
3656 ast::ExprField(..) |
3657 ast::ExprTupField(..) |
3658 ast::ExprIndex(..) |
3659 ast::ExprSlice(..) => {
3664 ast::ExprMethodCall(..) |
3665 ast::ExprStruct(..) |
3668 ast::ExprMatch(..) |
3669 ast::ExprFnBlock(..) |
3671 ast::ExprUnboxedFn(..) |
3672 ast::ExprBlock(..) |
3673 ast::ExprRepeat(..) |
3674 ast::ExprVec(..) => {
3678 ast::ExprIfLet(..) => {
3679 tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
3681 ast::ExprWhileLet(..) => {
3682 tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
3685 ast::ExprLit(ref lit) if lit_is_str(&**lit) => {
3689 ast::ExprCast(..) => {
3690 match tcx.node_types.borrow().find(&(expr.id as uint)) {
3692 if type_is_trait(t) {
3699 // Technically, it should not happen that the expr is not
3700 // present within the table. However, it DOES happen
3701 // during type check, because the final types from the
3702 // expressions are not yet recorded in the tcx. At that
3703 // time, though, we are only interested in knowing lvalue
3704 // vs rvalue. It would be better to base this decision on
3705 // the AST type in cast node---but (at the time of this
3706 // writing) it's not easy to distinguish casts to traits
3707 // from other casts based on the AST. This should be
3708 // easier in the future, when casts to traits
3709 // would like @Foo, Box<Foo>, or &Foo.
3715 ast::ExprBreak(..) |
3716 ast::ExprAgain(..) |
3718 ast::ExprWhile(..) |
3720 ast::ExprAssign(..) |
3721 ast::ExprInlineAsm(..) |
3722 ast::ExprAssignOp(..) |
3723 ast::ExprForLoop(..) => {
3727 ast::ExprLit(_) | // Note: LitStr is carved out above
3728 ast::ExprUnary(..) |
3729 ast::ExprAddrOf(..) |
3730 ast::ExprBinary(..) => {
3734 ast::ExprBox(ref place, _) => {
3735 // Special case `Box<T>` for now:
3736 let definition = match tcx.def_map.borrow().find(&place.id) {
3738 None => panic!("no def for place"),
3740 let def_id = definition.def_id();
3741 if tcx.lang_items.exchange_heap() == Some(def_id) {
3748 ast::ExprParen(ref e) => expr_kind(tcx, &**e),
3750 ast::ExprMac(..) => {
3753 "macro expression remains after expansion");
3758 pub fn stmt_node_id(s: &ast::Stmt) -> ast::NodeId {
3760 ast::StmtDecl(_, id) | StmtExpr(_, id) | StmtSemi(_, id) => {
3763 ast::StmtMac(..) => panic!("unexpanded macro in trans")
3767 pub fn field_idx_strict(tcx: &ctxt, name: ast::Name, fields: &[field])
3770 for f in fields.iter() { if f.name == name { return i; } i += 1u; }
3771 tcx.sess.bug(format!(
3772 "no field named `{}` found in the list of fields `{}`",
3773 token::get_name(name),
3775 .map(|f| token::get_name(f.name).get().to_string())
3776 .collect::<Vec<String>>()).as_slice());
3779 pub fn impl_or_trait_item_idx(id: ast::Name, trait_items: &[ImplOrTraitItem])
3781 trait_items.iter().position(|m| m.name() == id)
3784 pub fn ty_sort_string(cx: &ctxt, t: t) -> String {
3786 ty_nil | ty_bool | ty_char | ty_int(_) |
3787 ty_uint(_) | ty_float(_) | ty_str => {
3788 ::util::ppaux::ty_to_string(cx, t)
3791 ty_enum(id, _) => format!("enum {}", item_path_str(cx, id)),
3792 ty_uniq(_) => "box".to_string(),
3793 ty_vec(_, Some(_)) => "array".to_string(),
3794 ty_vec(_, None) => "unsized array".to_string(),
3795 ty_ptr(_) => "*-ptr".to_string(),
3796 ty_rptr(_, _) => "&-ptr".to_string(),
3797 ty_bare_fn(_) => "extern fn".to_string(),
3798 ty_closure(_) => "fn".to_string(),
3799 ty_trait(ref inner) => {
3800 format!("trait {}", item_path_str(cx, inner.def_id))
3802 ty_struct(id, _) => {
3803 format!("struct {}", item_path_str(cx, id))
3805 ty_unboxed_closure(..) => "closure".to_string(),
3806 ty_tup(_) => "tuple".to_string(),
3807 ty_infer(TyVar(_)) => "inferred type".to_string(),
3808 ty_infer(IntVar(_)) => "integral variable".to_string(),
3809 ty_infer(FloatVar(_)) => "floating-point variable".to_string(),
3810 ty_infer(SkolemizedTy(_)) => "skolemized type".to_string(),
3811 ty_infer(SkolemizedIntTy(_)) => "skolemized integral type".to_string(),
3812 ty_param(ref p) => {
3813 if p.space == subst::SelfSpace {
3816 "type parameter".to_string()
3819 ty_err => "type error".to_string(),
3820 ty_open(_) => "opened DST".to_string(),
3824 pub fn type_err_to_str(cx: &ctxt, err: &type_err) -> String {
3827 * Explains the source of a type err in a short,
3828 * human readable way. This is meant to be placed in
3829 * parentheses after some larger message. You should
3830 * also invoke `note_and_explain_type_err()` afterwards
3831 * to present additional details, particularly when
3832 * it comes to lifetime-related errors. */
3834 fn tstore_to_closure(s: &TraitStore) -> String {
3836 &UniqTraitStore => "proc".to_string(),
3837 &RegionTraitStore(..) => "closure".to_string()
3842 terr_cyclic_ty => "cyclic type of infinite size".to_string(),
3843 terr_mismatch => "types differ".to_string(),
3844 terr_fn_style_mismatch(values) => {
3845 format!("expected {} fn, found {} fn",
3846 values.expected.to_string(),
3847 values.found.to_string())
3849 terr_abi_mismatch(values) => {
3850 format!("expected {} fn, found {} fn",
3851 values.expected.to_string(),
3852 values.found.to_string())
3854 terr_onceness_mismatch(values) => {
3855 format!("expected {} fn, found {} fn",
3856 values.expected.to_string(),
3857 values.found.to_string())
3859 terr_sigil_mismatch(values) => {
3860 format!("expected {}, found {}",
3861 tstore_to_closure(&values.expected),
3862 tstore_to_closure(&values.found))
3864 terr_mutability => "values differ in mutability".to_string(),
3865 terr_box_mutability => {
3866 "boxed values differ in mutability".to_string()
3868 terr_vec_mutability => "vectors differ in mutability".to_string(),
3869 terr_ptr_mutability => "pointers differ in mutability".to_string(),
3870 terr_ref_mutability => "references differ in mutability".to_string(),
3871 terr_ty_param_size(values) => {
3872 format!("expected a type with {} type params, \
3873 found one with {} type params",
3877 terr_tuple_size(values) => {
3878 format!("expected a tuple with {} elements, \
3879 found one with {} elements",
3883 terr_record_size(values) => {
3884 format!("expected a record with {} fields, \
3885 found one with {} fields",
3889 terr_record_mutability => {
3890 "record elements differ in mutability".to_string()
3892 terr_record_fields(values) => {
3893 format!("expected a record with field `{}`, found one \
3895 token::get_ident(values.expected),
3896 token::get_ident(values.found))
3899 "incorrect number of function parameters".to_string()
3901 terr_regions_does_not_outlive(..) => {
3902 "lifetime mismatch".to_string()
3904 terr_regions_not_same(..) => {
3905 "lifetimes are not the same".to_string()
3907 terr_regions_no_overlap(..) => {
3908 "lifetimes do not intersect".to_string()
3910 terr_regions_insufficiently_polymorphic(br, _) => {
3911 format!("expected bound lifetime parameter {}, \
3912 found concrete lifetime",
3913 bound_region_ptr_to_string(cx, br))
3915 terr_regions_overly_polymorphic(br, _) => {
3916 format!("expected concrete lifetime, \
3917 found bound lifetime parameter {}",
3918 bound_region_ptr_to_string(cx, br))
3920 terr_trait_stores_differ(_, ref values) => {
3921 format!("trait storage differs: expected `{}`, found `{}`",
3922 trait_store_to_string(cx, (*values).expected),
3923 trait_store_to_string(cx, (*values).found))
3925 terr_sorts(values) => {
3926 format!("expected {}, found {}",
3927 ty_sort_string(cx, values.expected),
3928 ty_sort_string(cx, values.found))
3930 terr_traits(values) => {
3931 format!("expected trait `{}`, found trait `{}`",
3932 item_path_str(cx, values.expected),
3933 item_path_str(cx, values.found))
3935 terr_builtin_bounds(values) => {
3936 if values.expected.is_empty() {
3937 format!("expected no bounds, found `{}`",
3938 values.found.user_string(cx))
3939 } else if values.found.is_empty() {
3940 format!("expected bounds `{}`, found no bounds",
3941 values.expected.user_string(cx))
3943 format!("expected bounds `{}`, found bounds `{}`",
3944 values.expected.user_string(cx),
3945 values.found.user_string(cx))
3948 terr_integer_as_char => {
3949 "expected an integral type, found `char`".to_string()
3951 terr_int_mismatch(ref values) => {
3952 format!("expected `{}`, found `{}`",
3953 values.expected.to_string(),
3954 values.found.to_string())
3956 terr_float_mismatch(ref values) => {
3957 format!("expected `{}`, found `{}`",
3958 values.expected.to_string(),
3959 values.found.to_string())
3961 terr_variadic_mismatch(ref values) => {
3962 format!("expected {} fn, found {} function",
3963 if values.expected { "variadic" } else { "non-variadic" },
3964 if values.found { "variadic" } else { "non-variadic" })
3966 terr_convergence_mismatch(ref values) => {
3967 format!("expected {} fn, found {} function",
3968 if values.expected { "converging" } else { "diverging" },
3969 if values.found { "converging" } else { "diverging" })
3974 pub fn note_and_explain_type_err(cx: &ctxt, err: &type_err) {
3976 terr_regions_does_not_outlive(subregion, superregion) => {
3977 note_and_explain_region(cx, "", subregion, "...");
3978 note_and_explain_region(cx, "...does not necessarily outlive ",
3981 terr_regions_not_same(region1, region2) => {
3982 note_and_explain_region(cx, "", region1, "...");
3983 note_and_explain_region(cx, "...is not the same lifetime as ",
3986 terr_regions_no_overlap(region1, region2) => {
3987 note_and_explain_region(cx, "", region1, "...");
3988 note_and_explain_region(cx, "...does not overlap ",
3991 terr_regions_insufficiently_polymorphic(_, conc_region) => {
3992 note_and_explain_region(cx,
3993 "concrete lifetime that was found is ",
3996 terr_regions_overly_polymorphic(_, conc_region) => {
3997 note_and_explain_region(cx,
3998 "expected concrete lifetime is ",
4005 pub fn provided_source(cx: &ctxt, id: ast::DefId) -> Option<ast::DefId> {
4006 cx.provided_method_sources.borrow().find(&id).map(|x| *x)
4009 pub fn provided_trait_methods(cx: &ctxt, id: ast::DefId) -> Vec<Rc<Method>> {
4011 match cx.map.find(id.node) {
4012 Some(ast_map::NodeItem(item)) => {
4014 ItemTrait(_, _, _, ref ms) => {
4016 ast_util::split_trait_methods(ms.as_slice());
4019 match impl_or_trait_item(
4021 ast_util::local_def(m.id)) {
4022 MethodTraitItem(m) => m,
4023 TypeTraitItem(_) => {
4024 cx.sess.bug("provided_trait_methods(): \
4025 split_trait_methods() put \
4026 associated types in the \
4027 provided method bucket?!")
4033 cx.sess.bug(format!("provided_trait_methods: `{}` is \
4040 cx.sess.bug(format!("provided_trait_methods: `{}` is not a \
4046 csearch::get_provided_trait_methods(cx, id)
4050 fn lookup_locally_or_in_crate_store<V:Clone>(
4053 map: &mut DefIdMap<V>,
4054 load_external: || -> V) -> V {
4056 * Helper for looking things up in the various maps
4057 * that are populated during typeck::collect (e.g.,
4058 * `cx.impl_or_trait_items`, `cx.tcache`, etc). All of these share
4059 * the pattern that if the id is local, it should have
4060 * been loaded into the map by the `typeck::collect` phase.
4061 * If the def-id is external, then we have to go consult
4062 * the crate loading code (and cache the result for the future).
4065 match map.find_copy(&def_id) {
4066 Some(v) => { return v; }
4070 if def_id.krate == ast::LOCAL_CRATE {
4071 panic!("No def'n found for {} in tcx.{}", def_id, descr);
4073 let v = load_external();
4074 map.insert(def_id, v.clone());
4078 pub fn trait_item(cx: &ctxt, trait_did: ast::DefId, idx: uint)
4079 -> ImplOrTraitItem {
4080 let method_def_id = (*ty::trait_item_def_ids(cx, trait_did))[idx].def_id();
4081 impl_or_trait_item(cx, method_def_id)
4084 pub fn trait_items(cx: &ctxt, trait_did: ast::DefId)
4085 -> Rc<Vec<ImplOrTraitItem>> {
4086 let mut trait_items = cx.trait_items_cache.borrow_mut();
4087 match trait_items.find_copy(&trait_did) {
4088 Some(trait_items) => trait_items,
4090 let def_ids = ty::trait_item_def_ids(cx, trait_did);
4091 let items: Rc<Vec<ImplOrTraitItem>> =
4092 Rc::new(def_ids.iter()
4093 .map(|d| impl_or_trait_item(cx, d.def_id()))
4095 trait_items.insert(trait_did, items.clone());
4101 pub fn impl_or_trait_item(cx: &ctxt, id: ast::DefId) -> ImplOrTraitItem {
4102 lookup_locally_or_in_crate_store("impl_or_trait_items",
4104 &mut *cx.impl_or_trait_items
4107 csearch::get_impl_or_trait_item(cx, id)
4111 /// Returns true if the given ID refers to an associated type and false if it
4112 /// refers to anything else.
4113 pub fn is_associated_type(cx: &ctxt, id: ast::DefId) -> bool {
4114 memoized(&cx.associated_types, id, |id: ast::DefId| {
4115 if id.krate == ast::LOCAL_CRATE {
4116 match cx.impl_or_trait_items.borrow().find(&id) {
4119 TypeTraitItem(_) => true,
4120 MethodTraitItem(_) => false,
4126 csearch::is_associated_type(&cx.sess.cstore, id)
4131 /// Returns the parameter index that the given associated type corresponds to.
4132 pub fn associated_type_parameter_index(cx: &ctxt,
4133 trait_def: &TraitDef,
4134 associated_type_id: ast::DefId)
4136 for type_parameter_def in trait_def.generics.types.iter() {
4137 if type_parameter_def.def_id == associated_type_id {
4138 return type_parameter_def.index
4141 cx.sess.bug("couldn't find associated type parameter index")
4144 #[deriving(PartialEq, Eq)]
4145 pub struct AssociatedTypeInfo {
4146 pub def_id: ast::DefId,
4148 pub name: ast::Name,
4151 impl PartialOrd for AssociatedTypeInfo {
4152 fn partial_cmp(&self, other: &AssociatedTypeInfo) -> Option<Ordering> {
4153 Some(self.index.cmp(&other.index))
4157 impl Ord for AssociatedTypeInfo {
4158 fn cmp(&self, other: &AssociatedTypeInfo) -> Ordering {
4159 self.index.cmp(&other.index)
4163 /// Returns the associated types belonging to the given trait, in parameter
4165 pub fn associated_types_for_trait(cx: &ctxt, trait_id: ast::DefId)
4166 -> Rc<Vec<AssociatedTypeInfo>> {
4167 cx.trait_associated_types
4170 .expect("associated_types_for_trait(): trait not found, try calling \
4171 ensure_associated_types()")
4175 pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId)
4176 -> Rc<Vec<ImplOrTraitItemId>> {
4177 lookup_locally_or_in_crate_store("trait_item_def_ids",
4179 &mut *cx.trait_item_def_ids.borrow_mut(),
4181 Rc::new(csearch::get_trait_item_def_ids(&cx.sess.cstore, id))
4185 pub fn impl_trait_ref(cx: &ctxt, id: ast::DefId) -> Option<Rc<TraitRef>> {
4186 memoized(&cx.impl_trait_cache, id, |id: ast::DefId| {
4187 if id.krate == ast::LOCAL_CRATE {
4188 debug!("(impl_trait_ref) searching for trait impl {}", id);
4189 match cx.map.find(id.node) {
4190 Some(ast_map::NodeItem(item)) => {
4192 ast::ItemImpl(_, ref opt_trait, _, _) => {
4195 Some(ty::node_id_to_trait_ref(cx, t.ref_id))
4206 csearch::get_impl_trait(cx, id)
4211 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
4212 let def = *tcx.def_map.borrow()
4214 .expect("no def-map entry for trait");
4218 pub fn try_add_builtin_trait(
4220 trait_def_id: ast::DefId,
4221 builtin_bounds: &mut EnumSet<BuiltinBound>)
4224 //! Checks whether `trait_ref` refers to one of the builtin
4225 //! traits, like `Send`, and adds the corresponding
4226 //! bound to the set `builtin_bounds` if so. Returns true if `trait_ref`
4227 //! is a builtin trait.
4229 match tcx.lang_items.to_builtin_kind(trait_def_id) {
4230 Some(bound) => { builtin_bounds.add(bound); true }
4235 pub fn ty_to_def_id(ty: t) -> Option<ast::DefId> {
4237 ty_trait(box TyTrait { def_id: id, .. }) |
4240 ty_unboxed_closure(id, _, _) => Some(id),
4247 pub struct VariantInfo {
4249 pub arg_names: Option<Vec<ast::Ident> >,
4250 pub ctor_ty: Option<t>,
4251 pub name: ast::Name,
4259 /// Creates a new VariantInfo from the corresponding ast representation.
4261 /// Does not do any caching of the value in the type context.
4262 pub fn from_ast_variant(cx: &ctxt,
4263 ast_variant: &ast::Variant,
4264 discriminant: Disr) -> VariantInfo {
4265 let ctor_ty = node_id_to_type(cx, ast_variant.node.id);
4267 match ast_variant.node.kind {
4268 ast::TupleVariantKind(ref args) => {
4269 let arg_tys = if args.len() > 0 {
4270 ty_fn_args(ctor_ty).iter().map(|a| *a).collect()
4275 return VariantInfo {
4278 ctor_ty: Some(ctor_ty),
4279 name: ast_variant.node.name.name,
4280 id: ast_util::local_def(ast_variant.node.id),
4281 disr_val: discriminant,
4282 vis: ast_variant.node.vis
4285 ast::StructVariantKind(ref struct_def) => {
4287 let fields: &[StructField] = struct_def.fields.as_slice();
4289 assert!(fields.len() > 0);
4291 let arg_tys = struct_def.fields.iter()
4292 .map(|field| node_id_to_type(cx, field.node.id)).collect();
4293 let arg_names = fields.iter().map(|field| {
4294 match field.node.kind {
4295 NamedField(ident, _) => ident,
4296 UnnamedField(..) => cx.sess.bug(
4297 "enum_variants: all fields in struct must have a name")
4301 return VariantInfo {
4303 arg_names: Some(arg_names),
4305 name: ast_variant.node.name.name,
4306 id: ast_util::local_def(ast_variant.node.id),
4307 disr_val: discriminant,
4308 vis: ast_variant.node.vis
4315 pub fn substd_enum_variants(cx: &ctxt,
4318 -> Vec<Rc<VariantInfo>> {
4319 enum_variants(cx, id).iter().map(|variant_info| {
4320 let substd_args = variant_info.args.iter()
4321 .map(|aty| aty.subst(cx, substs)).collect::<Vec<_>>();
4323 let substd_ctor_ty = variant_info.ctor_ty.subst(cx, substs);
4325 Rc::new(VariantInfo {
4327 ctor_ty: substd_ctor_ty,
4328 ..(**variant_info).clone()
4333 pub fn item_path_str(cx: &ctxt, id: ast::DefId) -> String {
4334 with_path(cx, id, |path| ast_map::path_to_string(path)).to_string()
4339 TraitDtor(DefId, bool)
4343 pub fn is_present(&self) -> bool {
4345 TraitDtor(..) => true,
4350 pub fn has_drop_flag(&self) -> bool {
4353 &TraitDtor(_, flag) => flag
4358 /* If struct_id names a struct with a dtor, return Some(the dtor's id).
4359 Otherwise return none. */
4360 pub fn ty_dtor(cx: &ctxt, struct_id: DefId) -> DtorKind {
4361 match cx.destructor_for_type.borrow().find(&struct_id) {
4362 Some(&method_def_id) => {
4363 let flag = !has_attr(cx, struct_id, "unsafe_no_drop_flag");
4365 TraitDtor(method_def_id, flag)
4371 pub fn has_dtor(cx: &ctxt, struct_id: DefId) -> bool {
4372 cx.destructor_for_type.borrow().contains_key(&struct_id)
4375 pub fn with_path<T>(cx: &ctxt, id: ast::DefId, f: |ast_map::PathElems| -> T) -> T {
4376 if id.krate == ast::LOCAL_CRATE {
4377 cx.map.with_path(id.node, f)
4379 f(ast_map::Values(csearch::get_item_path(cx, id).iter()).chain(None))
4383 pub fn enum_is_univariant(cx: &ctxt, id: ast::DefId) -> bool {
4384 enum_variants(cx, id).len() == 1
4387 pub fn type_is_empty(cx: &ctxt, t: t) -> bool {
4388 match ty::get(t).sty {
4389 ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
4394 pub fn enum_variants(cx: &ctxt, id: ast::DefId) -> Rc<Vec<Rc<VariantInfo>>> {
4395 memoized(&cx.enum_var_cache, id, |id: ast::DefId| {
4396 if ast::LOCAL_CRATE != id.krate {
4397 Rc::new(csearch::get_enum_variants(cx, id))
4400 Although both this code and check_enum_variants in typeck/check
4401 call eval_const_expr, it should never get called twice for the same
4402 expr, since check_enum_variants also updates the enum_var_cache
4404 match cx.map.get(id.node) {
4405 ast_map::NodeItem(ref item) => {
4407 ast::ItemEnum(ref enum_definition, _) => {
4408 let mut last_discriminant: Option<Disr> = None;
4409 Rc::new(enum_definition.variants.iter().map(|variant| {
4411 let mut discriminant = match last_discriminant {
4412 Some(val) => val + 1,
4413 None => INITIAL_DISCRIMINANT_VALUE
4416 match variant.node.disr_expr {
4418 match const_eval::eval_const_expr_partial(cx, &**e) {
4419 Ok(const_eval::const_int(val)) => {
4420 discriminant = val as Disr
4422 Ok(const_eval::const_uint(val)) => {
4423 discriminant = val as Disr
4428 "expected signed integer constant");
4433 format!("expected constant: {}",
4440 last_discriminant = Some(discriminant);
4441 Rc::new(VariantInfo::from_ast_variant(cx, &**variant,
4446 cx.sess.bug("enum_variants: id not bound to an enum")
4450 _ => cx.sess.bug("enum_variants: id not bound to an enum")
4456 // Returns information about the enum variant with the given ID:
4457 pub fn enum_variant_with_id(cx: &ctxt,
4458 enum_id: ast::DefId,
4459 variant_id: ast::DefId)
4460 -> Rc<VariantInfo> {
4461 enum_variants(cx, enum_id).iter()
4462 .find(|variant| variant.id == variant_id)
4463 .expect("enum_variant_with_id(): no variant exists with that ID")
4468 // If the given item is in an external crate, looks up its type and adds it to
4469 // the type cache. Returns the type parameters and type.
4470 pub fn lookup_item_type(cx: &ctxt,
4473 lookup_locally_or_in_crate_store(
4474 "tcache", did, &mut *cx.tcache.borrow_mut(),
4475 || csearch::get_type(cx, did))
4478 /// Given the did of a trait, returns its canonical trait ref.
4479 pub fn lookup_trait_def(cx: &ctxt, did: DefId) -> Rc<ty::TraitDef> {
4480 memoized(&cx.trait_defs, did, |did: DefId| {
4481 assert!(did.krate != ast::LOCAL_CRATE);
4482 Rc::new(csearch::get_trait_def(cx, did))
4486 /// Given a reference to a trait, returns the bounds declared on the
4487 /// trait, with appropriate substitutions applied.
4488 pub fn bounds_for_trait_ref(tcx: &ctxt,
4489 trait_ref: &TraitRef)
4492 let trait_def = lookup_trait_def(tcx, trait_ref.def_id);
4493 debug!("bounds_for_trait_ref(trait_def={}, trait_ref={})",
4494 trait_def.repr(tcx), trait_ref.repr(tcx));
4495 trait_def.bounds.subst(tcx, &trait_ref.substs)
4498 /// Iterate over attributes of a definition.
4499 // (This should really be an iterator, but that would require csearch and
4500 // decoder to use iterators instead of higher-order functions.)
4501 pub fn each_attr(tcx: &ctxt, did: DefId, f: |&ast::Attribute| -> bool) -> bool {
4503 let item = tcx.map.expect_item(did.node);
4504 item.attrs.iter().all(|attr| f(attr))
4506 info!("getting foreign attrs");
4507 let mut cont = true;
4508 csearch::get_item_attrs(&tcx.sess.cstore, did, |attrs| {
4510 cont = attrs.iter().all(|attr| f(attr));
4518 /// Determine whether an item is annotated with an attribute
4519 pub fn has_attr(tcx: &ctxt, did: DefId, attr: &str) -> bool {
4520 let mut found = false;
4521 each_attr(tcx, did, |item| {
4522 if item.check_name(attr) {
4532 /// Determine whether an item is annotated with `#[repr(packed)]`
4533 pub fn lookup_packed(tcx: &ctxt, did: DefId) -> bool {
4534 lookup_repr_hints(tcx, did).contains(&attr::ReprPacked)
4537 /// Determine whether an item is annotated with `#[simd]`
4538 pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
4539 has_attr(tcx, did, "simd")
4542 /// Obtain the representation annotation for a struct definition.
4543 pub fn lookup_repr_hints(tcx: &ctxt, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
4544 memoized(&tcx.repr_hint_cache, did, |did: DefId| {
4545 Rc::new(if did.krate == LOCAL_CRATE {
4546 let mut acc = Vec::new();
4547 ty::each_attr(tcx, did, |meta| {
4548 acc.extend(attr::find_repr_attrs(tcx.sess.diagnostic(),
4554 csearch::get_repr_attrs(&tcx.sess.cstore, did)
4559 // Look up a field ID, whether or not it's local
4560 // Takes a list of type substs in case the struct is generic
4561 pub fn lookup_field_type(tcx: &ctxt,
4566 let t = if id.krate == ast::LOCAL_CRATE {
4567 node_id_to_type(tcx, id.node)
4569 let mut tcache = tcx.tcache.borrow_mut();
4570 let pty = match tcache.entry(id) {
4571 Occupied(entry) => entry.into_mut(),
4572 Vacant(entry) => entry.set(csearch::get_field_type(tcx, struct_id, id)),
4576 t.subst(tcx, substs)
4579 // Look up the list of field names and IDs for a given struct.
4580 // Fails if the id is not bound to a struct.
4581 pub fn lookup_struct_fields(cx: &ctxt, did: ast::DefId) -> Vec<field_ty> {
4582 if did.krate == ast::LOCAL_CRATE {
4583 let struct_fields = cx.struct_fields.borrow();
4584 match struct_fields.find(&did) {
4585 Some(fields) => (**fields).clone(),
4588 format!("ID not mapped to struct fields: {}",
4589 cx.map.node_to_string(did.node)).as_slice());
4593 csearch::get_struct_fields(&cx.sess.cstore, did)
4597 pub fn is_tuple_struct(cx: &ctxt, did: ast::DefId) -> bool {
4598 let fields = lookup_struct_fields(cx, did);
4599 !fields.is_empty() && fields.iter().all(|f| f.name == token::special_names::unnamed_field)
4602 // Returns a list of fields corresponding to the struct's items. trans uses
4603 // this. Takes a list of substs with which to instantiate field types.
4604 pub fn struct_fields(cx: &ctxt, did: ast::DefId, substs: &Substs)
4606 lookup_struct_fields(cx, did).iter().map(|f| {
4610 ty: lookup_field_type(cx, did, f.id, substs),
4617 // Returns a list of fields corresponding to the tuple's items. trans uses
4619 pub fn tup_fields(v: &[t]) -> Vec<field> {
4620 v.iter().enumerate().map(|(i, &f)| {
4622 name: token::intern(i.to_string().as_slice()),
4631 pub struct UnboxedClosureUpvar {
4637 // Returns a list of `UnboxedClosureUpvar`s for each upvar.
4638 pub fn unboxed_closure_upvars(tcx: &ctxt, closure_id: ast::DefId, substs: &Substs)
4639 -> Vec<UnboxedClosureUpvar> {
4640 if closure_id.krate == ast::LOCAL_CRATE {
4641 let capture_mode = tcx.capture_modes.borrow().get_copy(&closure_id.node);
4642 match tcx.freevars.borrow().find(&closure_id.node) {
4644 Some(ref freevars) => {
4645 freevars.iter().map(|freevar| {
4646 let freevar_def_id = freevar.def.def_id();
4647 let freevar_ty = node_id_to_type(tcx, freevar_def_id.node);
4648 let mut freevar_ty = freevar_ty.subst(tcx, substs);
4649 if capture_mode == ast::CaptureByRef {
4650 let borrow = tcx.upvar_borrow_map.borrow().get_copy(&ty::UpvarId {
4651 var_id: freevar_def_id.node,
4652 closure_expr_id: closure_id.node
4654 freevar_ty = mk_rptr(tcx, borrow.region, ty::mt {
4656 mutbl: borrow.kind.to_mutbl_lossy()
4659 UnboxedClosureUpvar {
4668 tcx.sess.bug("unimplemented cross-crate closure upvars")
4672 pub fn is_binopable(cx: &ctxt, ty: t, op: ast::BinOp) -> bool {
4673 #![allow(non_uppercase_statics)]
4674 static tycat_other: int = 0;
4675 static tycat_bool: int = 1;
4676 static tycat_char: int = 2;
4677 static tycat_int: int = 3;
4678 static tycat_float: int = 4;
4679 static tycat_raw_ptr: int = 6;
4681 static opcat_add: int = 0;
4682 static opcat_sub: int = 1;
4683 static opcat_mult: int = 2;
4684 static opcat_shift: int = 3;
4685 static opcat_rel: int = 4;
4686 static opcat_eq: int = 5;
4687 static opcat_bit: int = 6;
4688 static opcat_logic: int = 7;
4689 static opcat_mod: int = 8;
4691 fn opcat(op: ast::BinOp) -> int {
4693 ast::BiAdd => opcat_add,
4694 ast::BiSub => opcat_sub,
4695 ast::BiMul => opcat_mult,
4696 ast::BiDiv => opcat_mult,
4697 ast::BiRem => opcat_mod,
4698 ast::BiAnd => opcat_logic,
4699 ast::BiOr => opcat_logic,
4700 ast::BiBitXor => opcat_bit,
4701 ast::BiBitAnd => opcat_bit,
4702 ast::BiBitOr => opcat_bit,
4703 ast::BiShl => opcat_shift,
4704 ast::BiShr => opcat_shift,
4705 ast::BiEq => opcat_eq,
4706 ast::BiNe => opcat_eq,
4707 ast::BiLt => opcat_rel,
4708 ast::BiLe => opcat_rel,
4709 ast::BiGe => opcat_rel,
4710 ast::BiGt => opcat_rel
4714 fn tycat(cx: &ctxt, ty: t) -> int {
4715 if type_is_simd(cx, ty) {
4716 return tycat(cx, simd_type(cx, ty))
4719 ty_char => tycat_char,
4720 ty_bool => tycat_bool,
4721 ty_int(_) | ty_uint(_) | ty_infer(IntVar(_)) => tycat_int,
4722 ty_float(_) | ty_infer(FloatVar(_)) => tycat_float,
4723 ty_ptr(_) => tycat_raw_ptr,
4728 static t: bool = true;
4729 static f: bool = false;
4732 // +, -, *, shift, rel, ==, bit, logic, mod
4733 /*other*/ [f, f, f, f, f, f, f, f, f],
4734 /*bool*/ [f, f, f, f, t, t, t, t, f],
4735 /*char*/ [f, f, f, f, t, t, f, f, f],
4736 /*int*/ [t, t, t, t, t, t, t, f, t],
4737 /*float*/ [t, t, t, f, t, t, f, f, f],
4738 /*bot*/ [t, t, t, t, t, t, t, t, t],
4739 /*raw ptr*/ [f, f, f, f, t, t, f, f, f]];
4741 return tbl[tycat(cx, ty) as uint ][opcat(op) as uint];
4744 /// Returns an equivalent type with all the typedefs and self regions removed.
4745 pub fn normalize_ty(cx: &ctxt, t: t) -> t {
4746 let u = TypeNormalizer(cx).fold_ty(t);
4749 struct TypeNormalizer<'a, 'tcx: 'a>(&'a ctxt<'tcx>);
4751 impl<'a, 'tcx> TypeFolder<'tcx> for TypeNormalizer<'a, 'tcx> {
4752 fn tcx(&self) -> &ctxt<'tcx> { let TypeNormalizer(c) = *self; c }
4754 fn fold_ty(&mut self, t: ty::t) -> ty::t {
4755 match self.tcx().normalized_cache.borrow().find_copy(&t) {
4760 let t_norm = ty_fold::super_fold_ty(self, t);
4761 self.tcx().normalized_cache.borrow_mut().insert(t, t_norm);
4765 fn fold_region(&mut self, _: ty::Region) -> ty::Region {
4769 fn fold_substs(&mut self,
4770 substs: &subst::Substs)
4772 subst::Substs { regions: subst::ErasedRegions,
4773 types: substs.types.fold_with(self) }
4776 fn fold_sig(&mut self,
4779 // The binder-id is only relevant to bound regions, which
4780 // are erased at trans time.
4782 binder_id: ast::DUMMY_NODE_ID,
4783 inputs: sig.inputs.fold_with(self),
4784 output: sig.output.fold_with(self),
4785 variadic: sig.variadic,
4791 // Returns the repeat count for a repeating vector expression.
4792 pub fn eval_repeat_count(tcx: &ctxt, count_expr: &ast::Expr) -> uint {
4793 match const_eval::eval_const_expr_partial(tcx, count_expr) {
4794 Ok(ref const_val) => match *const_val {
4795 const_eval::const_int(count) => if count < 0 {
4796 tcx.sess.span_err(count_expr.span,
4797 "expected positive integer for \
4798 repeat count, found negative integer");
4803 const_eval::const_uint(count) => count as uint,
4804 const_eval::const_float(count) => {
4805 tcx.sess.span_err(count_expr.span,
4806 "expected positive integer for \
4807 repeat count, found float");
4810 const_eval::const_str(_) => {
4811 tcx.sess.span_err(count_expr.span,
4812 "expected positive integer for \
4813 repeat count, found string");
4816 const_eval::const_bool(_) => {
4817 tcx.sess.span_err(count_expr.span,
4818 "expected positive integer for \
4819 repeat count, found boolean");
4822 const_eval::const_binary(_) => {
4823 tcx.sess.span_err(count_expr.span,
4824 "expected positive integer for \
4825 repeat count, found binary array");
4828 const_eval::const_nil => {
4829 tcx.sess.span_err(count_expr.span,
4830 "expected positive integer for \
4831 repeat count, found ()");
4836 tcx.sess.span_err(count_expr.span,
4837 "expected constant integer for repeat count, \
4844 // Iterate over a type parameter's bounded traits and any supertraits
4845 // of those traits, ignoring kinds.
4846 // Here, the supertraits are the transitive closure of the supertrait
4847 // relation on the supertraits from each bounded trait's constraint
4849 pub fn each_bound_trait_and_supertraits(tcx: &ctxt,
4850 bounds: &[Rc<TraitRef>],
4851 f: |Rc<TraitRef>| -> bool)
4854 for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
4855 if !f(bound_trait_ref) {
4862 pub fn required_region_bounds(tcx: &ctxt,
4863 region_bounds: &[ty::Region],
4864 builtin_bounds: BuiltinBounds,
4865 trait_bounds: &[Rc<TraitRef>])
4869 * Given a type which must meet the builtin bounds and trait
4870 * bounds, returns a set of lifetimes which the type must outlive.
4872 * Requires that trait definitions have been processed.
4875 let mut all_bounds = Vec::new();
4877 debug!("required_region_bounds(builtin_bounds={}, trait_bounds={})",
4878 builtin_bounds.repr(tcx),
4879 trait_bounds.repr(tcx));
4881 all_bounds.push_all(region_bounds);
4883 push_region_bounds([],
4887 debug!("from builtin bounds: all_bounds={}", all_bounds.repr(tcx));
4889 each_bound_trait_and_supertraits(
4893 let bounds = ty::bounds_for_trait_ref(tcx, &*trait_ref);
4894 push_region_bounds(bounds.region_bounds.as_slice(),
4895 bounds.builtin_bounds,
4897 debug!("from {}: bounds={} all_bounds={}",
4898 trait_ref.repr(tcx),
4900 all_bounds.repr(tcx));
4906 fn push_region_bounds(region_bounds: &[ty::Region],
4907 builtin_bounds: ty::BuiltinBounds,
4908 all_bounds: &mut Vec<ty::Region>) {
4909 all_bounds.push_all(region_bounds.as_slice());
4911 if builtin_bounds.contains_elem(ty::BoundSend) {
4912 all_bounds.push(ty::ReStatic);
4917 pub fn get_tydesc_ty(tcx: &ctxt) -> Result<t, String> {
4918 tcx.lang_items.require(TyDescStructLangItem).map(|tydesc_lang_item| {
4919 tcx.intrinsic_defs.borrow().find_copy(&tydesc_lang_item)
4920 .expect("Failed to resolve TyDesc")
4924 pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
4925 lookup_locally_or_in_crate_store(
4926 "item_variance_map", item_id, &mut *tcx.item_variance_map.borrow_mut(),
4927 || Rc::new(csearch::get_item_variances(&tcx.sess.cstore, item_id)))
4930 /// Records a trait-to-implementation mapping.
4931 pub fn record_trait_implementation(tcx: &ctxt,
4932 trait_def_id: DefId,
4933 impl_def_id: DefId) {
4934 match tcx.trait_impls.borrow().find(&trait_def_id) {
4935 Some(impls_for_trait) => {
4936 impls_for_trait.borrow_mut().push(impl_def_id);
4941 tcx.trait_impls.borrow_mut().insert(trait_def_id, Rc::new(RefCell::new(vec!(impl_def_id))));
4944 /// Populates the type context with all the implementations for the given type
4946 pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
4947 type_id: ast::DefId) {
4948 if type_id.krate == LOCAL_CRATE {
4951 if tcx.populated_external_types.borrow().contains(&type_id) {
4955 let mut inherent_impls = Vec::new();
4956 csearch::each_implementation_for_type(&tcx.sess.cstore, type_id,
4958 let impl_items = csearch::get_impl_items(&tcx.sess.cstore,
4961 // Record the trait->implementation mappings, if applicable.
4962 let associated_traits = csearch::get_impl_trait(tcx, impl_def_id);
4963 for trait_ref in associated_traits.iter() {
4964 record_trait_implementation(tcx, trait_ref.def_id, impl_def_id);
4967 // For any methods that use a default implementation, add them to
4968 // the map. This is a bit unfortunate.
4969 for impl_item_def_id in impl_items.iter() {
4970 let method_def_id = impl_item_def_id.def_id();
4971 match impl_or_trait_item(tcx, method_def_id) {
4972 MethodTraitItem(method) => {
4973 for &source in method.provided_source.iter() {
4974 tcx.provided_method_sources
4976 .insert(method_def_id, source);
4979 TypeTraitItem(_) => {}
4983 // Store the implementation info.
4984 tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
4986 // If this is an inherent implementation, record it.
4987 if associated_traits.is_none() {
4988 inherent_impls.push(impl_def_id);
4992 tcx.inherent_impls.borrow_mut().insert(type_id, Rc::new(inherent_impls));
4993 tcx.populated_external_types.borrow_mut().insert(type_id);
4996 /// Populates the type context with all the implementations for the given
4997 /// trait if necessary.
4998 pub fn populate_implementations_for_trait_if_necessary(
5000 trait_id: ast::DefId) {
5001 if trait_id.krate == LOCAL_CRATE {
5004 if tcx.populated_external_traits.borrow().contains(&trait_id) {
5008 csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id,
5009 |implementation_def_id| {
5010 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
5012 // Record the trait->implementation mapping.
5013 record_trait_implementation(tcx, trait_id, implementation_def_id);
5015 // For any methods that use a default implementation, add them to
5016 // the map. This is a bit unfortunate.
5017 for impl_item_def_id in impl_items.iter() {
5018 let method_def_id = impl_item_def_id.def_id();
5019 match impl_or_trait_item(tcx, method_def_id) {
5020 MethodTraitItem(method) => {
5021 for &source in method.provided_source.iter() {
5022 tcx.provided_method_sources
5024 .insert(method_def_id, source);
5027 TypeTraitItem(_) => {}
5031 // Store the implementation info.
5032 tcx.impl_items.borrow_mut().insert(implementation_def_id, impl_items);
5035 tcx.populated_external_traits.borrow_mut().insert(trait_id);
5038 /// Given the def_id of an impl, return the def_id of the trait it implements.
5039 /// If it implements no trait, return `None`.
5040 pub fn trait_id_of_impl(tcx: &ctxt,
5041 def_id: ast::DefId) -> Option<ast::DefId> {
5042 let node = match tcx.map.find(def_id.node) {
5047 ast_map::NodeItem(item) => {
5049 ast::ItemImpl(_, Some(ref trait_ref), _, _) => {
5050 Some(node_id_to_trait_ref(tcx, trait_ref.ref_id).def_id)
5059 /// If the given def ID describes a method belonging to an impl, return the
5060 /// ID of the impl that the method belongs to. Otherwise, return `None`.
5061 pub fn impl_of_method(tcx: &ctxt, def_id: ast::DefId)
5062 -> Option<ast::DefId> {
5063 if def_id.krate != LOCAL_CRATE {
5064 return match csearch::get_impl_or_trait_item(tcx,
5065 def_id).container() {
5066 TraitContainer(_) => None,
5067 ImplContainer(def_id) => Some(def_id),
5070 match tcx.impl_or_trait_items.borrow().find_copy(&def_id) {
5071 Some(trait_item) => {
5072 match trait_item.container() {
5073 TraitContainer(_) => None,
5074 ImplContainer(def_id) => Some(def_id),
5081 /// If the given def ID describes an item belonging to a trait (either a
5082 /// default method or an implementation of a trait method), return the ID of
5083 /// the trait that the method belongs to. Otherwise, return `None`.
5084 pub fn trait_of_item(tcx: &ctxt, def_id: ast::DefId) -> Option<ast::DefId> {
5085 if def_id.krate != LOCAL_CRATE {
5086 return csearch::get_trait_of_item(&tcx.sess.cstore, def_id, tcx);
5088 match tcx.impl_or_trait_items.borrow().find_copy(&def_id) {
5089 Some(impl_or_trait_item) => {
5090 match impl_or_trait_item.container() {
5091 TraitContainer(def_id) => Some(def_id),
5092 ImplContainer(def_id) => trait_id_of_impl(tcx, def_id),
5099 /// If the given def ID describes an item belonging to a trait, (either a
5100 /// default method or an implementation of a trait method), return the ID of
5101 /// the method inside trait definition (this means that if the given def ID
5102 /// is already that of the original trait method, then the return value is
5104 /// Otherwise, return `None`.
5105 pub fn trait_item_of_item(tcx: &ctxt, def_id: ast::DefId)
5106 -> Option<ImplOrTraitItemId> {
5107 let impl_item = match tcx.impl_or_trait_items.borrow().find(&def_id) {
5108 Some(m) => m.clone(),
5109 None => return None,
5111 let name = impl_item.name();
5112 match trait_of_item(tcx, def_id) {
5113 Some(trait_did) => {
5114 let trait_items = ty::trait_items(tcx, trait_did);
5116 .position(|m| m.name() == name)
5117 .map(|idx| ty::trait_item(tcx, trait_did, idx).id())
5123 /// Creates a hash of the type `t` which will be the same no matter what crate
5124 /// context it's calculated within. This is used by the `type_id` intrinsic.
5125 pub fn hash_crate_independent(tcx: &ctxt, t: t, svh: &Svh) -> u64 {
5126 let mut state = sip::SipState::new();
5127 macro_rules! byte( ($b:expr) => { ($b as u8).hash(&mut state) } );
5128 macro_rules! hash( ($e:expr) => { $e.hash(&mut state) } );
5130 let region = |_state: &mut sip::SipState, r: Region| {
5140 tcx.sess.bug("non-static region found when hashing a type")
5144 let did = |state: &mut sip::SipState, did: DefId| {
5145 let h = if ast_util::is_local(did) {
5148 tcx.sess.cstore.get_crate_hash(did.krate)
5150 h.as_str().hash(state);
5151 did.node.hash(state);
5153 let mt = |state: &mut sip::SipState, mt: mt| {
5154 mt.mutbl.hash(state);
5156 ty::walk_ty(t, |t| {
5157 match ty::get(t).sty {
5159 ty_bool => byte!(2),
5160 ty_char => byte!(3),
5183 ty_vec(_, Some(n)) => {
5187 ty_vec(_, None) => {
5196 region(&mut state, r);
5199 ty_bare_fn(ref b) => {
5204 ty_closure(ref c) => {
5210 UniqTraitStore => byte!(0),
5211 RegionTraitStore(r, m) => {
5213 region(&mut state, r);
5214 assert_eq!(m, ast::MutMutable);
5218 ty_trait(box TyTrait { def_id: d, bounds, .. }) => {
5223 ty_struct(d, _) => {
5227 ty_tup(ref inner) => {
5234 did(&mut state, p.def_id);
5236 ty_open(_) => byte!(22),
5237 ty_infer(_) => unreachable!(),
5238 ty_err => byte!(23),
5239 ty_unboxed_closure(d, r, _) => {
5242 region(&mut state, r);
5251 pub fn to_string(self) -> &'static str {
5254 Contravariant => "-",
5261 pub fn empty_parameter_environment() -> ParameterEnvironment {
5263 * Construct a parameter environment suitable for static contexts
5264 * or other contexts where there are no free type/lifetime
5265 * parameters in scope.
5268 ty::ParameterEnvironment { free_substs: Substs::empty(),
5269 bounds: VecPerParamSpace::empty(),
5270 caller_obligations: VecPerParamSpace::empty(),
5271 implicit_region_bound: ty::ReEmpty,
5272 selection_cache: traits::SelectionCache::new(), }
5275 pub fn construct_parameter_environment(
5278 generics: &ty::Generics,
5279 free_id: ast::NodeId)
5280 -> ParameterEnvironment
5282 /*! See `ParameterEnvironment` struct def'n for details */
5285 // Construct the free substs.
5289 let mut types = VecPerParamSpace::empty();
5290 for &space in subst::ParamSpace::all().iter() {
5291 push_types_from_defs(tcx, &mut types, space,
5292 generics.types.get_slice(space));
5295 // map bound 'a => free 'a
5296 let mut regions = VecPerParamSpace::empty();
5297 for &space in subst::ParamSpace::all().iter() {
5298 push_region_params(&mut regions, space, free_id,
5299 generics.regions.get_slice(space));
5302 let free_substs = Substs {
5304 regions: subst::NonerasedRegions(regions)
5308 // Compute the bounds on Self and the type parameters.
5311 let mut bounds = VecPerParamSpace::empty();
5312 for &space in subst::ParamSpace::all().iter() {
5313 push_bounds_from_defs(tcx, &mut bounds, space, &free_substs,
5314 generics.types.get_slice(space));
5318 // Compute region bounds. For now, these relations are stored in a
5319 // global table on the tcx, so just enter them there. I'm not
5320 // crazy about this scheme, but it's convenient, at least.
5323 for &space in subst::ParamSpace::all().iter() {
5324 record_region_bounds_from_defs(tcx, space, &free_substs,
5325 generics.regions.get_slice(space));
5329 debug!("construct_parameter_environment: free_id={} \
5333 free_substs.repr(tcx),
5336 let obligations = traits::obligations_for_generics(tcx, traits::ObligationCause::misc(span),
5337 generics, &free_substs);
5339 return ty::ParameterEnvironment {
5340 free_substs: free_substs,
5342 implicit_region_bound: ty::ReScope(free_id),
5343 caller_obligations: obligations,
5344 selection_cache: traits::SelectionCache::new(),
5347 fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
5348 space: subst::ParamSpace,
5349 free_id: ast::NodeId,
5350 region_params: &[RegionParameterDef])
5352 for r in region_params.iter() {
5353 regions.push(space, ty::free_region_from_def(free_id, r));
5357 fn push_types_from_defs(tcx: &ty::ctxt,
5358 types: &mut subst::VecPerParamSpace<ty::t>,
5359 space: subst::ParamSpace,
5360 defs: &[TypeParameterDef]) {
5361 for (i, def) in defs.iter().enumerate() {
5362 debug!("construct_parameter_environment(): push_types_from_defs: \
5363 space={} def={} index={}",
5367 let ty = ty::mk_param(tcx, space, i, def.def_id);
5368 types.push(space, ty);
5372 fn push_bounds_from_defs(tcx: &ty::ctxt,
5373 bounds: &mut subst::VecPerParamSpace<ParamBounds>,
5374 space: subst::ParamSpace,
5375 free_substs: &subst::Substs,
5376 defs: &[TypeParameterDef]) {
5377 for def in defs.iter() {
5378 let b = def.bounds.subst(tcx, free_substs);
5379 bounds.push(space, b);
5383 fn record_region_bounds_from_defs(tcx: &ty::ctxt,
5384 space: subst::ParamSpace,
5385 free_substs: &subst::Substs,
5386 defs: &[RegionParameterDef]) {
5387 for (subst_region, def) in
5388 free_substs.regions().get_slice(space).iter().zip(
5391 // For each region parameter 'subst...
5392 let bounds = def.bounds.subst(tcx, free_substs);
5393 for bound_region in bounds.iter() {
5394 // Which is declared with a bound like 'subst:'bound...
5395 match (subst_region, bound_region) {
5396 (&ty::ReFree(subst_fr), &ty::ReFree(bound_fr)) => {
5397 // Record that 'subst outlives 'bound. Or, put
5398 // another way, 'bound <= 'subst.
5399 tcx.region_maps.relate_free_regions(bound_fr, subst_fr);
5402 // All named regions are instantiated with free regions.
5404 format!("push_region_bounds_from_defs: \
5405 non free region: {} / {}",
5406 subst_region.repr(tcx),
5407 bound_region.repr(tcx)).as_slice());
5416 pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
5418 ast::MutMutable => MutBorrow,
5419 ast::MutImmutable => ImmBorrow,
5423 pub fn to_mutbl_lossy(self) -> ast::Mutability {
5425 * Returns a mutability `m` such that an `&m T` pointer could
5426 * be used to obtain this borrow kind. Because borrow kinds
5427 * are richer than mutabilities, we sometimes have to pick a
5428 * mutability that is stronger than necessary so that it at
5429 * least *would permit* the borrow in question.
5433 MutBorrow => ast::MutMutable,
5434 ImmBorrow => ast::MutImmutable,
5436 // We have no type corresponding to a unique imm borrow, so
5437 // use `&mut`. It gives all the capabilities of an `&uniq`
5438 // and hence is a safe "over approximation".
5439 UniqueImmBorrow => ast::MutMutable,
5443 pub fn to_user_str(&self) -> &'static str {
5445 MutBorrow => "mutable",
5446 ImmBorrow => "immutable",
5447 UniqueImmBorrow => "uniquely immutable",
5452 impl<'tcx> mc::Typer<'tcx> for ty::ctxt<'tcx> {
5453 fn tcx<'a>(&'a self) -> &'a ty::ctxt<'tcx> {
5457 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<ty::t> {
5458 Ok(ty::node_id_to_type(self, id))
5461 fn node_method_ty(&self, method_call: typeck::MethodCall) -> Option<ty::t> {
5462 self.method_map.borrow().find(&method_call).map(|method| method.ty)
5465 fn adjustments<'a>(&'a self) -> &'a RefCell<NodeMap<ty::AutoAdjustment>> {
5469 fn is_method_call(&self, id: ast::NodeId) -> bool {
5470 self.method_map.borrow().contains_key(&typeck::MethodCall::expr(id))
5473 fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<ast::NodeId> {
5474 self.region_maps.temporary_scope(rvalue_id)
5477 fn upvar_borrow(&self, upvar_id: ty::UpvarId) -> ty::UpvarBorrow {
5478 self.upvar_borrow_map.borrow().get_copy(&upvar_id)
5481 fn capture_mode(&self, closure_expr_id: ast::NodeId)
5482 -> ast::CaptureClause {
5483 self.capture_modes.borrow().get_copy(&closure_expr_id)
5486 fn unboxed_closures<'a>(&'a self)
5487 -> &'a RefCell<DefIdMap<UnboxedClosure>> {
5488 &self.unboxed_closures
5492 /// The category of explicit self.
5493 #[deriving(Clone, Eq, PartialEq, Show)]
5494 pub enum ExplicitSelfCategory {
5495 StaticExplicitSelfCategory,
5496 ByValueExplicitSelfCategory,
5497 ByReferenceExplicitSelfCategory(Region, ast::Mutability),
5498 ByBoxExplicitSelfCategory,
5501 /// Pushes all the lifetimes in the given type onto the given list. A
5502 /// "lifetime in a type" is a lifetime specified by a reference or a lifetime
5503 /// in a list of type substitutions. This does *not* traverse into nominal
5504 /// types, nor does it resolve fictitious types.
5505 pub fn accumulate_lifetimes_in_type(accumulator: &mut Vec<ty::Region>,
5507 walk_ty(typ, |typ| {
5508 match get(typ).sty {
5509 ty_rptr(region, _) => accumulator.push(region),
5510 ty_enum(_, ref substs) |
5511 ty_trait(box TyTrait {
5515 ty_struct(_, ref substs) => {
5516 accum_substs(accumulator, substs);
5518 ty_closure(ref closure_ty) => {
5519 match closure_ty.store {
5520 RegionTraitStore(region, _) => accumulator.push(region),
5521 UniqTraitStore => {}
5524 ty_unboxed_closure(_, ref region, ref substs) => {
5525 accumulator.push(*region);
5526 accum_substs(accumulator, substs);
5547 fn accum_substs(accumulator: &mut Vec<Region>, substs: &Substs) {
5548 match substs.regions {
5549 subst::ErasedRegions => {}
5550 subst::NonerasedRegions(ref regions) => {
5551 for region in regions.iter() {
5552 accumulator.push(*region)
5559 /// A free variable referred to in a function.
5560 #[deriving(Encodable, Decodable)]
5561 pub struct Freevar {
5562 /// The variable being accessed free.
5565 // First span where it is accessed (there can be multiple).
5569 pub type FreevarMap = NodeMap<Vec<Freevar>>;
5571 pub type CaptureModeMap = NodeMap<ast::CaptureClause>;
5573 pub fn with_freevars<T>(tcx: &ty::ctxt, fid: ast::NodeId, f: |&[Freevar]| -> T) -> T {
5574 match tcx.freevars.borrow().find(&fid) {
5576 Some(d) => f(d.as_slice())