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)]
13 pub use self::terr_vstore_kind::*;
14 pub use self::type_err::*;
15 pub use self::BuiltinBound::*;
16 pub use self::InferTy::*;
17 pub use self::InferRegion::*;
18 pub use self::ImplOrTraitItemId::*;
19 pub use self::ClosureKind::*;
20 pub use self::Variance::*;
21 pub use self::AutoAdjustment::*;
22 pub use self::Representability::*;
23 pub use self::AutoRef::*;
24 pub use self::ExprKind::*;
25 pub use self::DtorKind::*;
26 pub use self::ExplicitSelfCategory::*;
27 pub use self::FnOutput::*;
28 pub use self::Region::*;
29 pub use self::ImplOrTraitItemContainer::*;
30 pub use self::BorrowKind::*;
31 pub use self::ImplOrTraitItem::*;
32 pub use self::BoundRegion::*;
34 pub use self::IntVarValue::*;
35 pub use self::MethodOrigin::*;
36 pub use self::CopyImplementationError::*;
41 use metadata::csearch;
44 use middle::check_const;
45 use middle::const_eval;
46 use middle::def::{self, DefMap, ExportMap};
47 use middle::dependency_format;
48 use middle::fast_reject;
49 use middle::free_region::FreeRegionMap;
50 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
51 use middle::mem_categorization as mc;
53 use middle::resolve_lifetime;
56 use middle::region::RegionMaps;
57 use middle::stability;
58 use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace};
61 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
62 use middle::ty_walk::{self, TypeWalker};
63 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_string};
64 use util::ppaux::ty_to_string;
65 use util::ppaux::{Repr, UserString};
66 use util::common::{memoized, ErrorReported};
67 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
68 use util::nodemap::FnvHashMap;
69 use util::num::ToPrimitive;
71 use arena::TypedArena;
72 use std::borrow::{Borrow, Cow};
73 use std::cell::{Cell, RefCell, Ref};
76 use std::hash::{Hash, SipHasher, Hasher};
80 use std::vec::IntoIter;
81 use collections::enum_set::{EnumSet, CLike};
82 use std::collections::{HashMap, HashSet};
84 use syntax::ast::{CrateNum, DefId, ItemImpl, ItemTrait, LOCAL_CRATE};
85 use syntax::ast::{MutImmutable, MutMutable, Name, NamedField, NodeId};
86 use syntax::ast::{StmtExpr, StmtSemi, StructField, UnnamedField, Visibility};
87 use syntax::ast_util::{self, is_local, lit_is_str, local_def};
88 use syntax::attr::{self, AttrMetaMethods, SignedInt, UnsignedInt};
89 use syntax::codemap::Span;
90 use syntax::parse::token::{self, InternedString, special_idents};
91 use syntax::print::pprust;
94 use syntax::ast_map::{self, LinkedPath};
98 pub const INITIAL_DISCRIMINANT_VALUE: Disr = 0;
102 /// The complete set of all analyses described in this module. This is
103 /// produced by the driver and fed to trans and later passes.
104 pub struct CrateAnalysis<'tcx> {
105 pub export_map: ExportMap,
106 pub exported_items: middle::privacy::ExportedItems,
107 pub public_items: middle::privacy::PublicItems,
108 pub ty_cx: ty::ctxt<'tcx>,
109 pub reachable: NodeSet,
111 pub glob_map: Option<GlobMap>,
114 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
115 pub struct field<'tcx> {
120 #[derive(Clone, Copy, Debug)]
121 pub enum ImplOrTraitItemContainer {
122 TraitContainer(ast::DefId),
123 ImplContainer(ast::DefId),
126 impl ImplOrTraitItemContainer {
127 pub fn id(&self) -> ast::DefId {
129 TraitContainer(id) => id,
130 ImplContainer(id) => id,
135 #[derive(Clone, Debug)]
136 pub enum ImplOrTraitItem<'tcx> {
137 ConstTraitItem(Rc<AssociatedConst<'tcx>>),
138 MethodTraitItem(Rc<Method<'tcx>>),
139 TypeTraitItem(Rc<AssociatedType<'tcx>>),
142 impl<'tcx> ImplOrTraitItem<'tcx> {
143 fn id(&self) -> ImplOrTraitItemId {
145 ConstTraitItem(ref associated_const) => {
146 ConstTraitItemId(associated_const.def_id)
148 MethodTraitItem(ref method) => MethodTraitItemId(method.def_id),
149 TypeTraitItem(ref associated_type) => {
150 TypeTraitItemId(associated_type.def_id)
155 pub fn def_id(&self) -> ast::DefId {
157 ConstTraitItem(ref associated_const) => associated_const.def_id,
158 MethodTraitItem(ref method) => method.def_id,
159 TypeTraitItem(ref associated_type) => associated_type.def_id,
163 pub fn name(&self) -> ast::Name {
165 ConstTraitItem(ref associated_const) => associated_const.name,
166 MethodTraitItem(ref method) => method.name,
167 TypeTraitItem(ref associated_type) => associated_type.name,
171 pub fn vis(&self) -> ast::Visibility {
173 ConstTraitItem(ref associated_const) => associated_const.vis,
174 MethodTraitItem(ref method) => method.vis,
175 TypeTraitItem(ref associated_type) => associated_type.vis,
179 pub fn container(&self) -> ImplOrTraitItemContainer {
181 ConstTraitItem(ref associated_const) => associated_const.container,
182 MethodTraitItem(ref method) => method.container,
183 TypeTraitItem(ref associated_type) => associated_type.container,
187 pub fn as_opt_method(&self) -> Option<Rc<Method<'tcx>>> {
189 MethodTraitItem(ref m) => Some((*m).clone()),
195 #[derive(Clone, Copy, Debug)]
196 pub enum ImplOrTraitItemId {
197 ConstTraitItemId(ast::DefId),
198 MethodTraitItemId(ast::DefId),
199 TypeTraitItemId(ast::DefId),
202 impl ImplOrTraitItemId {
203 pub fn def_id(&self) -> ast::DefId {
205 ConstTraitItemId(def_id) => def_id,
206 MethodTraitItemId(def_id) => def_id,
207 TypeTraitItemId(def_id) => def_id,
212 #[derive(Clone, Debug)]
213 pub struct Method<'tcx> {
215 pub generics: Generics<'tcx>,
216 pub predicates: GenericPredicates<'tcx>,
217 pub fty: BareFnTy<'tcx>,
218 pub explicit_self: ExplicitSelfCategory,
219 pub vis: ast::Visibility,
220 pub def_id: ast::DefId,
221 pub container: ImplOrTraitItemContainer,
223 // If this method is provided, we need to know where it came from
224 pub provided_source: Option<ast::DefId>
227 impl<'tcx> Method<'tcx> {
228 pub fn new(name: ast::Name,
229 generics: ty::Generics<'tcx>,
230 predicates: GenericPredicates<'tcx>,
232 explicit_self: ExplicitSelfCategory,
233 vis: ast::Visibility,
235 container: ImplOrTraitItemContainer,
236 provided_source: Option<ast::DefId>)
241 predicates: predicates,
243 explicit_self: explicit_self,
246 container: container,
247 provided_source: provided_source
251 pub fn container_id(&self) -> ast::DefId {
252 match self.container {
253 TraitContainer(id) => id,
254 ImplContainer(id) => id,
259 #[derive(Clone, Copy, Debug)]
260 pub struct AssociatedConst<'tcx> {
263 pub vis: ast::Visibility,
264 pub def_id: ast::DefId,
265 pub container: ImplOrTraitItemContainer,
266 pub default: Option<ast::DefId>,
269 #[derive(Clone, Copy, Debug)]
270 pub struct AssociatedType<'tcx> {
272 pub ty: Option<Ty<'tcx>>,
273 pub vis: ast::Visibility,
274 pub def_id: ast::DefId,
275 pub container: ImplOrTraitItemContainer,
278 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
279 pub struct mt<'tcx> {
281 pub mutbl: ast::Mutability,
284 #[derive(Clone, Copy, Debug)]
285 pub struct field_ty {
288 pub vis: ast::Visibility,
289 pub origin: ast::DefId, // The DefId of the struct in which the field is declared.
292 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable)]
293 pub struct ItemVariances {
294 pub types: VecPerParamSpace<Variance>,
295 pub regions: VecPerParamSpace<Variance>,
298 #[derive(Clone, PartialEq, RustcDecodable, RustcEncodable, Debug, Copy)]
300 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
301 Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
302 Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
303 Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
306 #[derive(Copy, Clone, Debug)]
307 pub enum AutoAdjustment<'tcx> {
308 AdjustReifyFnPointer, // go from a fn-item type to a fn-pointer type
309 AdjustUnsafeFnPointer, // go from a safe fn pointer to an unsafe fn pointer
310 AdjustDerefRef(AutoDerefRef<'tcx>),
313 /// Represents coercing a pointer to a different kind of pointer - where 'kind'
314 /// here means either or both of raw vs borrowed vs unique and fat vs thin.
316 /// We transform pointers by following the following steps in order:
317 /// 1. Deref the pointer `self.autoderefs` times (may be 0).
318 /// 2. If `autoref` is `Some(_)`, then take the address and produce either a
319 /// `&` or `*` pointer.
320 /// 3. If `unsize` is `Some(_)`, then apply the unsize transformation,
321 /// which will do things like convert thin pointers to fat
322 /// pointers, or convert structs containing thin pointers to
323 /// structs containing fat pointers, or convert between fat
324 /// pointers. We don't store the details of how the transform is
325 /// done (in fact, we don't know that, because it might depend on
326 /// the precise type parameters). We just store the target
327 /// type. Trans figures out what has to be done at monomorphization
328 /// time based on the precise source/target type at hand.
330 /// To make that more concrete, here are some common scenarios:
332 /// 1. The simplest cases are where the pointer is not adjusted fat vs thin.
333 /// Here the pointer will be dereferenced N times (where a dereference can
334 /// happen to to raw or borrowed pointers or any smart pointer which implements
335 /// Deref, including Box<_>). The number of dereferences is given by
336 /// `autoderefs`. It can then be auto-referenced zero or one times, indicated
337 /// by `autoref`, to either a raw or borrowed pointer. In these cases unsize is
340 /// 2. A thin-to-fat coercon involves unsizing the underlying data. We start
341 /// with a thin pointer, deref a number of times, unsize the underlying data,
342 /// then autoref. The 'unsize' phase may change a fixed length array to a
343 /// dynamically sized one, a concrete object to a trait object, or statically
344 /// sized struct to a dyncamically sized one. E.g., &[i32; 4] -> &[i32] is
349 /// autoderefs: 1, // &[i32; 4] -> [i32; 4]
350 /// autoref: Some(AutoPtr), // [i32] -> &[i32]
351 /// unsize: Some([i32]), // [i32; 4] -> [i32]
355 /// Note that for a struct, the 'deep' unsizing of the struct is not recorded.
356 /// E.g., `struct Foo<T> { x: T }` we can coerce &Foo<[i32; 4]> to &Foo<[i32]>
357 /// The autoderef and -ref are the same as in the above example, but the type
358 /// stored in `unsize` is `Foo<[i32]>`, we don't store any further detail about
359 /// the underlying conversions from `[i32; 4]` to `[i32]`.
361 /// 3. Coercing a `Box<T>` to `Box<Trait>` is an interesting special case. In
362 /// that case, we have the pointer we need coming in, so there are no
363 /// autoderefs, and no autoref. Instead we just do the `Unsize` transformation.
364 /// At some point, of course, `Box` should move out of the compiler, in which
365 /// case this is analogous to transformating a struct. E.g., Box<[i32; 4]> ->
366 /// Box<[i32]> is represented by:
372 /// unsize: Some(Box<[i32]>),
375 #[derive(Copy, Clone, Debug)]
376 pub struct AutoDerefRef<'tcx> {
377 /// Step 1. Apply a number of dereferences, producing an lvalue.
378 pub autoderefs: usize,
380 /// Step 2. Optionally produce a pointer/reference from the value.
381 pub autoref: Option<AutoRef<'tcx>>,
383 /// Step 3. Unsize a pointer/reference value, e.g. `&[T; n]` to
384 /// `&[T]`. The stored type is the target pointer type. Note that
385 /// the source could be a thin or fat pointer.
386 pub unsize: Option<Ty<'tcx>>,
389 #[derive(Copy, Clone, PartialEq, Debug)]
390 pub enum AutoRef<'tcx> {
391 /// Convert from T to &T.
392 AutoPtr(&'tcx Region, ast::Mutability),
394 /// Convert from T to *T.
395 /// Value to thin pointer.
396 AutoUnsafe(ast::Mutability),
399 #[derive(Clone, Copy, RustcEncodable, RustcDecodable, Debug)]
400 pub enum CustomCoerceUnsized {
401 /// Records the index of the field being coerced.
405 #[derive(Clone, Debug)]
406 pub enum MethodOrigin<'tcx> {
407 // fully statically resolved method
408 MethodStatic(ast::DefId),
410 // fully statically resolved closure invocation
411 MethodStaticClosure(ast::DefId),
413 // method invoked on a type parameter with a bounded trait
414 MethodTypeParam(MethodParam<'tcx>),
416 // method invoked on a trait instance
417 MethodTraitObject(MethodObject<'tcx>),
421 // details for a method invoked with a receiver whose type is a type parameter
422 // with a bounded trait.
423 #[derive(Clone, Debug)]
424 pub struct MethodParam<'tcx> {
425 // the precise trait reference that occurs as a bound -- this may
426 // be a supertrait of what the user actually typed. Note that it
427 // never contains bound regions; those regions should have been
428 // instantiated with fresh variables at this point.
429 pub trait_ref: ty::TraitRef<'tcx>,
431 // index of usize in the list of trait items. Note that this is NOT
432 // the index into the vtable, because the list of trait items
433 // includes associated types.
434 pub method_num: usize,
436 /// The impl for the trait from which the method comes. This
437 /// should only be used for certain linting/heuristic purposes
438 /// since there is no guarantee that this is Some in every
439 /// situation that it could/should be.
440 pub impl_def_id: Option<ast::DefId>,
443 // details for a method invoked with a receiver whose type is an object
444 #[derive(Clone, Debug)]
445 pub struct MethodObject<'tcx> {
446 // the (super)trait containing the method to be invoked
447 pub trait_ref: TraitRef<'tcx>,
449 // the actual base trait id of the object
450 pub object_trait_id: ast::DefId,
452 // index of the method to be invoked amongst the trait's items
453 pub method_num: usize,
455 // index into the actual runtime vtable.
456 // the vtable is formed by concatenating together the method lists of
457 // the base object trait and all supertraits; this is the index into
459 pub vtable_index: usize,
462 #[derive(Clone, Debug)]
463 pub struct MethodCallee<'tcx> {
464 pub origin: MethodOrigin<'tcx>,
466 pub substs: subst::Substs<'tcx>
469 /// With method calls, we store some extra information in
470 /// side tables (i.e method_map). We use
471 /// MethodCall as a key to index into these tables instead of
472 /// just directly using the expression's NodeId. The reason
473 /// for this being that we may apply adjustments (coercions)
474 /// with the resulting expression also needing to use the
475 /// side tables. The problem with this is that we don't
476 /// assign a separate NodeId to this new expression
477 /// and so it would clash with the base expression if both
478 /// needed to add to the side tables. Thus to disambiguate
479 /// we also keep track of whether there's an adjustment in
481 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
482 pub struct MethodCall {
483 pub expr_id: ast::NodeId,
488 pub fn expr(id: ast::NodeId) -> MethodCall {
495 pub fn autoderef(expr_id: ast::NodeId, autoderef: u32) -> MethodCall {
498 autoderef: 1 + autoderef
503 // maps from an expression id that corresponds to a method call to the details
504 // of the method to be invoked
505 pub type MethodMap<'tcx> = RefCell<FnvHashMap<MethodCall, MethodCallee<'tcx>>>;
507 // Contains information needed to resolve types and (in the future) look up
508 // the types of AST nodes.
509 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
510 pub struct creader_cache_key {
516 /// A restriction that certain types must be the same size. The use of
517 /// `transmute` gives rise to these restrictions. These generally
518 /// cannot be checked until trans; therefore, each call to `transmute`
519 /// will push one or more such restriction into the
520 /// `transmute_restrictions` vector during `intrinsicck`. They are
521 /// then checked during `trans` by the fn `check_intrinsics`.
522 #[derive(Copy, Clone)]
523 pub struct TransmuteRestriction<'tcx> {
524 /// The span whence the restriction comes.
527 /// The type being transmuted from.
528 pub original_from: Ty<'tcx>,
530 /// The type being transmuted to.
531 pub original_to: Ty<'tcx>,
533 /// The type being transmuted from, with all type parameters
534 /// substituted for an arbitrary representative. Not to be shown
536 pub substituted_from: Ty<'tcx>,
538 /// The type being transmuted to, with all type parameters
539 /// substituted for an arbitrary representative. Not to be shown
541 pub substituted_to: Ty<'tcx>,
543 /// NodeId of the transmute intrinsic.
548 pub struct CtxtArenas<'tcx> {
550 type_: TypedArena<TyS<'tcx>>,
551 substs: TypedArena<Substs<'tcx>>,
552 bare_fn: TypedArena<BareFnTy<'tcx>>,
553 region: TypedArena<Region>,
554 stability: TypedArena<attr::Stability>,
557 trait_defs: TypedArena<TraitDef<'tcx>>,
560 impl<'tcx> CtxtArenas<'tcx> {
561 pub fn new() -> CtxtArenas<'tcx> {
563 type_: TypedArena::new(),
564 substs: TypedArena::new(),
565 bare_fn: TypedArena::new(),
566 region: TypedArena::new(),
567 stability: TypedArena::new(),
569 trait_defs: TypedArena::new()
574 pub struct CommonTypes<'tcx> {
592 /// The data structure to keep track of all the information that typechecker
593 /// generates so that so that it can be reused and doesn't have to be redone
595 pub struct ctxt<'tcx> {
596 /// The arenas that types etc are allocated from.
597 arenas: &'tcx CtxtArenas<'tcx>,
599 /// Specifically use a speedy hash algorithm for this hash map, it's used
601 // FIXME(eddyb) use a FnvHashSet<InternedTy<'tcx>> when equivalent keys can
602 // queried from a HashSet.
603 interner: RefCell<FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>>,
605 // FIXME as above, use a hashset if equivalent elements can be queried.
606 substs_interner: RefCell<FnvHashMap<&'tcx Substs<'tcx>, &'tcx Substs<'tcx>>>,
607 bare_fn_interner: RefCell<FnvHashMap<&'tcx BareFnTy<'tcx>, &'tcx BareFnTy<'tcx>>>,
608 region_interner: RefCell<FnvHashMap<&'tcx Region, &'tcx Region>>,
609 stability_interner: RefCell<FnvHashMap<&'tcx attr::Stability, &'tcx attr::Stability>>,
611 /// Common types, pre-interned for your convenience.
612 pub types: CommonTypes<'tcx>,
617 pub named_region_map: resolve_lifetime::NamedRegionMap,
619 pub region_maps: RegionMaps,
621 // For each fn declared in the local crate, type check stores the
622 // free-region relationships that were deduced from its where
623 // clauses and parameter types. These are then read-again by
624 // borrowck. (They are not used during trans, and hence are not
625 // serialized or needed for cross-crate fns.)
626 free_region_maps: RefCell<NodeMap<FreeRegionMap>>,
628 /// Stores the types for various nodes in the AST. Note that this table
629 /// is not guaranteed to be populated until after typeck. See
630 /// typeck::check::fn_ctxt for details.
631 node_types: RefCell<NodeMap<Ty<'tcx>>>,
633 /// Stores the type parameters which were substituted to obtain the type
634 /// of this node. This only applies to nodes that refer to entities
635 /// parameterized by type parameters, such as generic fns, types, or
637 pub item_substs: RefCell<NodeMap<ItemSubsts<'tcx>>>,
639 /// Maps from a trait item to the trait item "descriptor"
640 pub impl_or_trait_items: RefCell<DefIdMap<ImplOrTraitItem<'tcx>>>,
642 /// Maps from a trait def-id to a list of the def-ids of its trait items
643 pub trait_item_def_ids: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItemId>>>>,
645 /// A cache for the trait_items() routine
646 pub trait_items_cache: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItem<'tcx>>>>>,
648 pub impl_trait_refs: RefCell<DefIdMap<Option<TraitRef<'tcx>>>>,
649 pub trait_defs: RefCell<DefIdMap<&'tcx TraitDef<'tcx>>>,
651 /// Maps from the def-id of an item (trait/struct/enum/fn) to its
652 /// associated predicates.
653 pub predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
655 /// Maps from the def-id of a trait to the list of
656 /// super-predicates. This is a subset of the full list of
657 /// predicates. We store these in a separate map because we must
658 /// evaluate them even during type conversion, often before the
659 /// full predicates are available (note that supertraits have
660 /// additional acyclicity requirements).
661 pub super_predicates: RefCell<DefIdMap<GenericPredicates<'tcx>>>,
663 pub map: ast_map::Map<'tcx>,
664 pub freevars: RefCell<FreevarMap>,
665 pub tcache: RefCell<DefIdMap<TypeScheme<'tcx>>>,
666 pub rcache: RefCell<FnvHashMap<creader_cache_key, Ty<'tcx>>>,
667 pub tc_cache: RefCell<FnvHashMap<Ty<'tcx>, TypeContents>>,
668 pub ast_ty_to_ty_cache: RefCell<NodeMap<Ty<'tcx>>>,
669 pub enum_var_cache: RefCell<DefIdMap<Rc<Vec<Rc<VariantInfo<'tcx>>>>>>,
670 pub ty_param_defs: RefCell<NodeMap<TypeParameterDef<'tcx>>>,
671 pub adjustments: RefCell<NodeMap<AutoAdjustment<'tcx>>>,
672 pub normalized_cache: RefCell<FnvHashMap<Ty<'tcx>, Ty<'tcx>>>,
673 pub lang_items: middle::lang_items::LanguageItems,
674 /// A mapping of fake provided method def_ids to the default implementation
675 pub provided_method_sources: RefCell<DefIdMap<ast::DefId>>,
676 pub struct_fields: RefCell<DefIdMap<Rc<Vec<field_ty>>>>,
678 /// Maps from def-id of a type or region parameter to its
679 /// (inferred) variance.
680 pub item_variance_map: RefCell<DefIdMap<Rc<ItemVariances>>>,
682 /// True if the variance has been computed yet; false otherwise.
683 pub variance_computed: Cell<bool>,
685 /// A mapping from the def ID of an enum or struct type to the def ID
686 /// of the method that implements its destructor. If the type is not
687 /// present in this map, it does not have a destructor. This map is
688 /// populated during the coherence phase of typechecking.
689 pub destructor_for_type: RefCell<DefIdMap<ast::DefId>>,
691 /// A method will be in this list if and only if it is a destructor.
692 pub destructors: RefCell<DefIdSet>,
694 /// Maps a DefId of a type to a list of its inherent impls.
695 /// Contains implementations of methods that are inherent to a type.
696 /// Methods in these implementations don't need to be exported.
697 pub inherent_impls: RefCell<DefIdMap<Rc<Vec<ast::DefId>>>>,
699 /// Maps a DefId of an impl to a list of its items.
700 /// Note that this contains all of the impls that we know about,
701 /// including ones in other crates. It's not clear that this is the best
703 pub impl_items: RefCell<DefIdMap<Vec<ImplOrTraitItemId>>>,
705 /// Set of used unsafe nodes (functions or blocks). Unsafe nodes not
706 /// present in this set can be warned about.
707 pub used_unsafe: RefCell<NodeSet>,
709 /// Set of nodes which mark locals as mutable which end up getting used at
710 /// some point. Local variable definitions not in this set can be warned
712 pub used_mut_nodes: RefCell<NodeSet>,
714 /// The set of external nominal types whose implementations have been read.
715 /// This is used for lazy resolution of methods.
716 pub populated_external_types: RefCell<DefIdSet>,
717 /// The set of external primitive types whose implementations have been read.
718 /// FIXME(arielb1): why is this separate from populated_external_types?
719 pub populated_external_primitive_impls: RefCell<DefIdSet>,
722 pub upvar_capture_map: RefCell<UpvarCaptureMap>,
724 /// These caches are used by const_eval when decoding external constants.
725 pub extern_const_statics: RefCell<DefIdMap<ast::NodeId>>,
726 pub extern_const_variants: RefCell<DefIdMap<ast::NodeId>>,
727 pub extern_const_fns: RefCell<DefIdMap<ast::NodeId>>,
729 pub method_map: MethodMap<'tcx>,
731 pub dependency_formats: RefCell<dependency_format::Dependencies>,
733 /// Records the type of each closure. The def ID is the ID of the
734 /// expression defining the closure.
735 pub closure_kinds: RefCell<DefIdMap<ClosureKind>>,
737 /// Records the type of each closure. The def ID is the ID of the
738 /// expression defining the closure.
739 pub closure_tys: RefCell<DefIdMap<ClosureTy<'tcx>>>,
741 pub node_lint_levels: RefCell<FnvHashMap<(ast::NodeId, lint::LintId),
744 /// The types that must be asserted to be the same size for `transmute`
745 /// to be valid. We gather up these restrictions in the intrinsicck pass
746 /// and check them in trans.
747 pub transmute_restrictions: RefCell<Vec<TransmuteRestriction<'tcx>>>,
749 /// Maps any item's def-id to its stability index.
750 pub stability: RefCell<stability::Index<'tcx>>,
752 /// Caches the results of trait selection. This cache is used
753 /// for things that do not have to do with the parameters in scope.
754 pub selection_cache: traits::SelectionCache<'tcx>,
756 /// Caches the representation hints for struct definitions.
757 pub repr_hint_cache: RefCell<DefIdMap<Rc<Vec<attr::ReprAttr>>>>,
759 /// Maps Expr NodeId's to their constant qualification.
760 pub const_qualif_map: RefCell<NodeMap<check_const::ConstQualif>>,
762 /// Caches CoerceUnsized kinds for impls on custom types.
763 pub custom_coerce_unsized_kinds: RefCell<DefIdMap<CustomCoerceUnsized>>,
765 /// Maps a cast expression to its kind. This is keyed on the
766 /// *from* expression of the cast, not the cast itself.
767 pub cast_kinds: RefCell<NodeMap<cast::CastKind>>,
770 impl<'tcx> ctxt<'tcx> {
771 pub fn node_types(&self) -> Ref<NodeMap<Ty<'tcx>>> { self.node_types.borrow() }
772 pub fn node_type_insert(&self, id: NodeId, ty: Ty<'tcx>) {
773 self.node_types.borrow_mut().insert(id, ty);
776 pub fn intern_trait_def(&self, def: TraitDef<'tcx>) -> &'tcx TraitDef<'tcx> {
777 let did = def.trait_ref.def_id;
778 let interned = self.arenas.trait_defs.alloc(def);
779 self.trait_defs.borrow_mut().insert(did, interned);
783 pub fn intern_stability(&self, stab: attr::Stability) -> &'tcx attr::Stability {
784 if let Some(st) = self.stability_interner.borrow().get(&stab) {
788 let interned = self.arenas.stability.alloc(stab);
789 self.stability_interner.borrow_mut().insert(interned, interned);
793 pub fn store_free_region_map(&self, id: NodeId, map: FreeRegionMap) {
794 self.free_region_maps.borrow_mut()
798 pub fn free_region_map(&self, id: NodeId) -> FreeRegionMap {
799 self.free_region_maps.borrow()[&id].clone()
803 // Flags that we track on types. These flags are propagated upwards
804 // through the type during type construction, so that we can quickly
805 // check whether the type has various kinds of types in it without
806 // recursing over the type itself.
808 flags TypeFlags: u32 {
809 const HAS_PARAMS = 1 << 0,
810 const HAS_SELF = 1 << 1,
811 const HAS_TY_INFER = 1 << 2,
812 const HAS_RE_INFER = 1 << 3,
813 const HAS_RE_EARLY_BOUND = 1 << 4,
814 const HAS_FREE_REGIONS = 1 << 5,
815 const HAS_TY_ERR = 1 << 6,
816 const HAS_PROJECTION = 1 << 7,
817 const HAS_TY_CLOSURE = 1 << 8,
818 const NEEDS_SUBST = TypeFlags::HAS_PARAMS.bits |
819 TypeFlags::HAS_SELF.bits |
820 TypeFlags::HAS_RE_EARLY_BOUND.bits,
822 // Flags representing the nominal content of a type,
823 // computed by FlagsComputation. If you add a new nominal
824 // flag, it should be added here too.
825 const NOMINAL_FLAGS = TypeFlags::HAS_PARAMS.bits |
826 TypeFlags::HAS_SELF.bits |
827 TypeFlags::HAS_TY_INFER.bits |
828 TypeFlags::HAS_RE_INFER.bits |
829 TypeFlags::HAS_RE_EARLY_BOUND.bits |
830 TypeFlags::HAS_FREE_REGIONS.bits |
831 TypeFlags::HAS_TY_ERR.bits |
832 TypeFlags::HAS_PROJECTION.bits |
833 TypeFlags::HAS_TY_CLOSURE.bits,
835 // Caches for type_is_sized, type_moves_by_default
836 const SIZEDNESS_CACHED = 1 << 16,
837 const IS_SIZED = 1 << 17,
838 const MOVENESS_CACHED = 1 << 18,
839 const MOVES_BY_DEFAULT = 1 << 19,
843 macro_rules! sty_debug_print {
844 ($ctxt: expr, $($variant: ident),*) => {{
845 // curious inner module to allow variant names to be used as
849 #[derive(Copy, Clone)]
857 pub fn go(tcx: &ty::ctxt) {
858 let mut total = DebugStat {
860 region_infer: 0, ty_infer: 0, both_infer: 0,
862 $(let mut $variant = total;)*
865 for (_, t) in &*tcx.interner.borrow() {
866 let variant = match t.sty {
867 ty::ty_bool | ty::ty_char | ty::ty_int(..) | ty::ty_uint(..) |
868 ty::ty_float(..) | ty::ty_str => continue,
869 ty::ty_err => /* unimportant */ continue,
870 $(ty::$variant(..) => &mut $variant,)*
872 let region = t.flags.get().intersects(ty::TypeFlags::HAS_RE_INFER);
873 let ty = t.flags.get().intersects(ty::TypeFlags::HAS_TY_INFER);
877 if region { total.region_infer += 1; variant.region_infer += 1 }
878 if ty { total.ty_infer += 1; variant.ty_infer += 1 }
879 if region && ty { total.both_infer += 1; variant.both_infer += 1 }
881 println!("Ty interner total ty region both");
882 $(println!(" {:18}: {uses:6} {usespc:4.1}%, \
883 {ty:4.1}% {region:5.1}% {both:4.1}%",
884 stringify!($variant),
885 uses = $variant.total,
886 usespc = $variant.total as f64 * 100.0 / total.total as f64,
887 ty = $variant.ty_infer as f64 * 100.0 / total.total as f64,
888 region = $variant.region_infer as f64 * 100.0 / total.total as f64,
889 both = $variant.both_infer as f64 * 100.0 / total.total as f64);
891 println!(" total {uses:6} \
892 {ty:4.1}% {region:5.1}% {both:4.1}%",
894 ty = total.ty_infer as f64 * 100.0 / total.total as f64,
895 region = total.region_infer as f64 * 100.0 / total.total as f64,
896 both = total.both_infer as f64 * 100.0 / total.total as f64)
904 impl<'tcx> ctxt<'tcx> {
905 pub fn print_debug_stats(&self) {
908 ty_enum, ty_uniq, ty_vec, ty_ptr, ty_rptr, ty_bare_fn, ty_trait,
909 ty_struct, ty_closure, ty_tup, ty_param, ty_infer, ty_projection);
911 println!("Substs interner: #{}", self.substs_interner.borrow().len());
912 println!("BareFnTy interner: #{}", self.bare_fn_interner.borrow().len());
913 println!("Region interner: #{}", self.region_interner.borrow().len());
914 println!("Stability interner: #{}", self.stability_interner.borrow().len());
919 pub struct TyS<'tcx> {
921 pub flags: Cell<TypeFlags>,
923 // the maximal depth of any bound regions appearing in this type.
927 impl fmt::Debug for TypeFlags {
928 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
929 write!(f, "{}", self.bits)
933 impl<'tcx> PartialEq for TyS<'tcx> {
935 fn eq(&self, other: &TyS<'tcx>) -> bool {
936 // (self as *const _) == (other as *const _)
937 (self as *const TyS<'tcx>) == (other as *const TyS<'tcx>)
940 impl<'tcx> Eq for TyS<'tcx> {}
942 impl<'tcx> Hash for TyS<'tcx> {
943 fn hash<H: Hasher>(&self, s: &mut H) {
944 (self as *const TyS).hash(s)
948 pub type Ty<'tcx> = &'tcx TyS<'tcx>;
950 /// An entry in the type interner.
951 pub struct InternedTy<'tcx> {
955 // NB: An InternedTy compares and hashes as a sty.
956 impl<'tcx> PartialEq for InternedTy<'tcx> {
957 fn eq(&self, other: &InternedTy<'tcx>) -> bool {
958 self.ty.sty == other.ty.sty
962 impl<'tcx> Eq for InternedTy<'tcx> {}
964 impl<'tcx> Hash for InternedTy<'tcx> {
965 fn hash<H: Hasher>(&self, s: &mut H) {
970 impl<'tcx> Borrow<sty<'tcx>> for InternedTy<'tcx> {
971 fn borrow<'a>(&'a self) -> &'a sty<'tcx> {
976 pub fn type_has_params(ty: Ty) -> bool {
977 ty.flags.get().intersects(TypeFlags::HAS_PARAMS)
979 pub fn type_has_self(ty: Ty) -> bool {
980 ty.flags.get().intersects(TypeFlags::HAS_SELF)
982 pub fn type_has_ty_infer(ty: Ty) -> bool {
983 ty.flags.get().intersects(TypeFlags::HAS_TY_INFER)
985 pub fn type_needs_infer(ty: Ty) -> bool {
986 ty.flags.get().intersects(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER)
988 pub fn type_has_projection(ty: Ty) -> bool {
989 ty.flags.get().intersects(TypeFlags::HAS_PROJECTION)
991 pub fn type_has_ty_closure(ty: Ty) -> bool {
992 ty.flags.get().intersects(TypeFlags::HAS_TY_CLOSURE)
995 pub fn type_has_erasable_regions(ty: Ty) -> bool {
996 ty.flags.get().intersects(TypeFlags::HAS_RE_EARLY_BOUND |
997 TypeFlags::HAS_RE_INFER |
998 TypeFlags::HAS_FREE_REGIONS)
1001 /// An "escaping region" is a bound region whose binder is not part of `t`.
1003 /// So, for example, consider a type like the following, which has two binders:
1005 /// for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
1006 /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
1007 /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ inner scope
1009 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
1010 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
1011 /// fn type*, that type has an escaping region: `'a`.
1013 /// Note that what I'm calling an "escaping region" is often just called a "free region". However,
1014 /// we already use the term "free region". It refers to the regions that we use to represent bound
1015 /// regions on a fn definition while we are typechecking its body.
1017 /// To clarify, conceptually there is no particular difference between an "escaping" region and a
1018 /// "free" region. However, there is a big difference in practice. Basically, when "entering" a
1019 /// binding level, one is generally required to do some sort of processing to a bound region, such
1020 /// as replacing it with a fresh/skolemized region, or making an entry in the environment to
1021 /// represent the scope to which it is attached, etc. An escaping region represents a bound region
1022 /// for which this processing has not yet been done.
1023 pub fn type_has_escaping_regions(ty: Ty) -> bool {
1024 type_escapes_depth(ty, 0)
1027 pub fn type_escapes_depth(ty: Ty, depth: u32) -> bool {
1028 ty.region_depth > depth
1031 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1032 pub struct BareFnTy<'tcx> {
1033 pub unsafety: ast::Unsafety,
1035 pub sig: PolyFnSig<'tcx>,
1038 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1039 pub struct ClosureTy<'tcx> {
1040 pub unsafety: ast::Unsafety,
1042 pub sig: PolyFnSig<'tcx>,
1045 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1046 pub enum FnOutput<'tcx> {
1047 FnConverging(Ty<'tcx>),
1051 impl<'tcx> FnOutput<'tcx> {
1052 pub fn diverges(&self) -> bool {
1053 *self == FnDiverging
1056 pub fn unwrap(self) -> Ty<'tcx> {
1058 ty::FnConverging(t) => t,
1059 ty::FnDiverging => unreachable!()
1063 pub fn unwrap_or(self, def: Ty<'tcx>) -> Ty<'tcx> {
1065 ty::FnConverging(t) => t,
1066 ty::FnDiverging => def
1071 pub type PolyFnOutput<'tcx> = Binder<FnOutput<'tcx>>;
1073 impl<'tcx> PolyFnOutput<'tcx> {
1074 pub fn diverges(&self) -> bool {
1079 /// Signature of a function type, which I have arbitrarily
1080 /// decided to use to refer to the input/output types.
1082 /// - `inputs` is the list of arguments and their modes.
1083 /// - `output` is the return type.
1084 /// - `variadic` indicates whether this is a variadic function. (only true for foreign fns)
1085 #[derive(Clone, PartialEq, Eq, Hash)]
1086 pub struct FnSig<'tcx> {
1087 pub inputs: Vec<Ty<'tcx>>,
1088 pub output: FnOutput<'tcx>,
1092 pub type PolyFnSig<'tcx> = Binder<FnSig<'tcx>>;
1094 impl<'tcx> PolyFnSig<'tcx> {
1095 pub fn inputs(&self) -> ty::Binder<Vec<Ty<'tcx>>> {
1096 self.map_bound_ref(|fn_sig| fn_sig.inputs.clone())
1098 pub fn input(&self, index: usize) -> ty::Binder<Ty<'tcx>> {
1099 self.map_bound_ref(|fn_sig| fn_sig.inputs[index])
1101 pub fn output(&self) -> ty::Binder<FnOutput<'tcx>> {
1102 self.map_bound_ref(|fn_sig| fn_sig.output.clone())
1104 pub fn variadic(&self) -> bool {
1105 self.skip_binder().variadic
1109 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1110 pub struct ParamTy {
1111 pub space: subst::ParamSpace,
1113 pub name: ast::Name,
1116 /// A [De Bruijn index][dbi] is a standard means of representing
1117 /// regions (and perhaps later types) in a higher-ranked setting. In
1118 /// particular, imagine a type like this:
1120 /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
1123 /// | +------------+ 1 | |
1125 /// +--------------------------------+ 2 |
1127 /// +------------------------------------------+ 1
1129 /// In this type, there are two binders (the outer fn and the inner
1130 /// fn). We need to be able to determine, for any given region, which
1131 /// fn type it is bound by, the inner or the outer one. There are
1132 /// various ways you can do this, but a De Bruijn index is one of the
1133 /// more convenient and has some nice properties. The basic idea is to
1134 /// count the number of binders, inside out. Some examples should help
1135 /// clarify what I mean.
1137 /// Let's start with the reference type `&'b isize` that is the first
1138 /// argument to the inner function. This region `'b` is assigned a De
1139 /// Bruijn index of 1, meaning "the innermost binder" (in this case, a
1140 /// fn). The region `'a` that appears in the second argument type (`&'a
1141 /// isize`) would then be assigned a De Bruijn index of 2, meaning "the
1142 /// second-innermost binder". (These indices are written on the arrays
1143 /// in the diagram).
1145 /// What is interesting is that De Bruijn index attached to a particular
1146 /// variable will vary depending on where it appears. For example,
1147 /// the final type `&'a char` also refers to the region `'a` declared on
1148 /// the outermost fn. But this time, this reference is not nested within
1149 /// any other binders (i.e., it is not an argument to the inner fn, but
1150 /// rather the outer one). Therefore, in this case, it is assigned a
1151 /// De Bruijn index of 1, because the innermost binder in that location
1152 /// is the outer fn.
1154 /// [dbi]: http://en.wikipedia.org/wiki/De_Bruijn_index
1155 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug, Copy)]
1156 pub struct DebruijnIndex {
1157 // We maintain the invariant that this is never 0. So 1 indicates
1158 // the innermost binder. To ensure this, create with `DebruijnIndex::new`.
1162 /// Representation of regions:
1163 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug, Copy)]
1165 // Region bound in a type or fn declaration which will be
1166 // substituted 'early' -- that is, at the same time when type
1167 // parameters are substituted.
1168 ReEarlyBound(EarlyBoundRegion),
1170 // Region bound in a function scope, which will be substituted when the
1171 // function is called.
1172 ReLateBound(DebruijnIndex, BoundRegion),
1174 /// When checking a function body, the types of all arguments and so forth
1175 /// that refer to bound region parameters are modified to refer to free
1176 /// region parameters.
1179 /// A concrete region naming some statically determined extent
1180 /// (e.g. an expression or sequence of statements) within the
1181 /// current function.
1182 ReScope(region::CodeExtent),
1184 /// Static data that has an "infinite" lifetime. Top in the region lattice.
1187 /// A region variable. Should not exist after typeck.
1188 ReInfer(InferRegion),
1190 /// Empty lifetime is for data that is never accessed.
1191 /// Bottom in the region lattice. We treat ReEmpty somewhat
1192 /// specially; at least right now, we do not generate instances of
1193 /// it during the GLB computations, but rather
1194 /// generate an error instead. This is to improve error messages.
1195 /// The only way to get an instance of ReEmpty is to have a region
1196 /// variable with no constraints.
1200 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
1201 pub struct EarlyBoundRegion {
1202 pub param_id: ast::NodeId,
1203 pub space: subst::ParamSpace,
1205 pub name: ast::Name,
1208 /// Upvars do not get their own node-id. Instead, we use the pair of
1209 /// the original var id (that is, the root variable that is referenced
1210 /// by the upvar) and the id of the closure expression.
1211 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1212 pub struct UpvarId {
1213 pub var_id: ast::NodeId,
1214 pub closure_expr_id: ast::NodeId,
1217 #[derive(Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable, Copy)]
1218 pub enum BorrowKind {
1219 /// Data must be immutable and is aliasable.
1222 /// Data must be immutable but not aliasable. This kind of borrow
1223 /// cannot currently be expressed by the user and is used only in
1224 /// implicit closure bindings. It is needed when you the closure
1225 /// is borrowing or mutating a mutable referent, e.g.:
1227 /// let x: &mut isize = ...;
1228 /// let y = || *x += 5;
1230 /// If we were to try to translate this closure into a more explicit
1231 /// form, we'd encounter an error with the code as written:
1233 /// struct Env { x: & &mut isize }
1234 /// let x: &mut isize = ...;
1235 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
1236 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
1238 /// This is then illegal because you cannot mutate a `&mut` found
1239 /// in an aliasable location. To solve, you'd have to translate with
1240 /// an `&mut` borrow:
1242 /// struct Env { x: & &mut isize }
1243 /// let x: &mut isize = ...;
1244 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
1245 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
1247 /// Now the assignment to `**env.x` is legal, but creating a
1248 /// mutable pointer to `x` is not because `x` is not mutable. We
1249 /// could fix this by declaring `x` as `let mut x`. This is ok in
1250 /// user code, if awkward, but extra weird for closures, since the
1251 /// borrow is hidden.
1253 /// So we introduce a "unique imm" borrow -- the referent is
1254 /// immutable, but not aliasable. This solves the problem. For
1255 /// simplicity, we don't give users the way to express this
1256 /// borrow, it's just used when translating closures.
1259 /// Data is mutable and not aliasable.
1263 /// Information describing the capture of an upvar. This is computed
1264 /// during `typeck`, specifically by `regionck`.
1265 #[derive(PartialEq, Clone, RustcEncodable, RustcDecodable, Debug, Copy)]
1266 pub enum UpvarCapture {
1267 /// Upvar is captured by value. This is always true when the
1268 /// closure is labeled `move`, but can also be true in other cases
1269 /// depending on inference.
1272 /// Upvar is captured by reference.
1276 #[derive(PartialEq, Clone, RustcEncodable, RustcDecodable, Debug, Copy)]
1277 pub struct UpvarBorrow {
1278 /// The kind of borrow: by-ref upvars have access to shared
1279 /// immutable borrows, which are not part of the normal language
1281 pub kind: BorrowKind,
1283 /// Region of the resulting reference.
1284 pub region: ty::Region,
1287 pub type UpvarCaptureMap = FnvHashMap<UpvarId, UpvarCapture>;
1290 pub fn is_bound(&self) -> bool {
1292 ty::ReEarlyBound(..) => true,
1293 ty::ReLateBound(..) => true,
1298 pub fn escapes_depth(&self, depth: u32) -> bool {
1300 ty::ReLateBound(debruijn, _) => debruijn.depth > depth,
1306 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash,
1307 RustcEncodable, RustcDecodable, Debug, Copy)]
1308 /// A "free" region `fr` can be interpreted as "some region
1309 /// at least as big as the scope `fr.scope`".
1310 pub struct FreeRegion {
1311 pub scope: region::DestructionScopeData,
1312 pub bound_region: BoundRegion
1315 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash,
1316 RustcEncodable, RustcDecodable, Debug, Copy)]
1317 pub enum BoundRegion {
1318 /// An anonymous region parameter for a given fn (&T)
1321 /// Named region parameters for functions (a in &'a T)
1323 /// The def-id is needed to distinguish free regions in
1324 /// the event of shadowing.
1325 BrNamed(ast::DefId, ast::Name),
1327 /// Fresh bound identifiers created during GLB computations.
1330 // Anonymous region for the implicit env pointer parameter
1335 // NB: If you change this, you'll probably want to change the corresponding
1336 // AST structure in libsyntax/ast.rs as well.
1337 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1338 pub enum sty<'tcx> {
1342 ty_uint(ast::UintTy),
1343 ty_float(ast::FloatTy),
1344 /// Substs here, possibly against intuition, *may* contain `ty_param`s.
1345 /// That is, even after substitution it is possible that there are type
1346 /// variables. This happens when the `ty_enum` corresponds to an enum
1347 /// definition and not a concrete use of it. To get the correct `ty_enum`
1348 /// from the tcx, use the `NodeId` from the `ast::Ty` and look it up in
1349 /// the `ast_ty_to_ty_cache`. This is probably true for `ty_struct` as
1351 ty_enum(DefId, &'tcx Substs<'tcx>),
1354 ty_vec(Ty<'tcx>, Option<usize>), // Second field is length.
1356 ty_rptr(&'tcx Region, mt<'tcx>),
1358 // If the def-id is Some(_), then this is the type of a specific
1359 // fn item. Otherwise, if None(_), it a fn pointer type.
1360 ty_bare_fn(Option<DefId>, &'tcx BareFnTy<'tcx>),
1362 ty_trait(Box<TyTrait<'tcx>>),
1363 ty_struct(DefId, &'tcx Substs<'tcx>),
1365 ty_closure(DefId, &'tcx Substs<'tcx>),
1367 ty_tup(Vec<Ty<'tcx>>),
1369 ty_projection(ProjectionTy<'tcx>),
1370 ty_param(ParamTy), // type parameter
1372 ty_infer(InferTy), // something used only during inference/typeck
1373 ty_err, // Also only used during inference/typeck, to represent
1374 // the type of an erroneous expression (helps cut down
1375 // on non-useful type error messages)
1378 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1379 pub struct TyTrait<'tcx> {
1380 pub principal: ty::PolyTraitRef<'tcx>,
1381 pub bounds: ExistentialBounds<'tcx>,
1384 impl<'tcx> TyTrait<'tcx> {
1385 pub fn principal_def_id(&self) -> ast::DefId {
1386 self.principal.0.def_id
1389 /// Object types don't have a self-type specified. Therefore, when
1390 /// we convert the principal trait-ref into a normal trait-ref,
1391 /// you must give *some* self-type. A common choice is `mk_err()`
1392 /// or some skolemized type.
1393 pub fn principal_trait_ref_with_self_ty(&self,
1396 -> ty::PolyTraitRef<'tcx>
1398 // otherwise the escaping regions would be captured by the binder
1399 assert!(!self_ty.has_escaping_regions());
1401 ty::Binder(TraitRef {
1402 def_id: self.principal.0.def_id,
1403 substs: tcx.mk_substs(self.principal.0.substs.with_self_ty(self_ty)),
1407 pub fn projection_bounds_with_self_ty(&self,
1410 -> Vec<ty::PolyProjectionPredicate<'tcx>>
1412 // otherwise the escaping regions would be captured by the binders
1413 assert!(!self_ty.has_escaping_regions());
1415 self.bounds.projection_bounds.iter()
1416 .map(|in_poly_projection_predicate| {
1417 let in_projection_ty = &in_poly_projection_predicate.0.projection_ty;
1418 let substs = tcx.mk_substs(in_projection_ty.trait_ref.substs.with_self_ty(self_ty));
1419 let trait_ref = ty::TraitRef::new(in_projection_ty.trait_ref.def_id,
1421 let projection_ty = ty::ProjectionTy {
1422 trait_ref: trait_ref,
1423 item_name: in_projection_ty.item_name
1425 ty::Binder(ty::ProjectionPredicate {
1426 projection_ty: projection_ty,
1427 ty: in_poly_projection_predicate.0.ty
1434 /// A complete reference to a trait. These take numerous guises in syntax,
1435 /// but perhaps the most recognizable form is in a where clause:
1439 /// This would be represented by a trait-reference where the def-id is the
1440 /// def-id for the trait `Foo` and the substs defines `T` as parameter 0 in the
1441 /// `SelfSpace` and `U` as parameter 0 in the `TypeSpace`.
1443 /// Trait references also appear in object types like `Foo<U>`, but in
1444 /// that case the `Self` parameter is absent from the substitutions.
1446 /// Note that a `TraitRef` introduces a level of region binding, to
1447 /// account for higher-ranked trait bounds like `T : for<'a> Foo<&'a
1448 /// U>` or higher-ranked object types.
1449 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
1450 pub struct TraitRef<'tcx> {
1452 pub substs: &'tcx Substs<'tcx>,
1455 pub type PolyTraitRef<'tcx> = Binder<TraitRef<'tcx>>;
1457 impl<'tcx> PolyTraitRef<'tcx> {
1458 pub fn self_ty(&self) -> Ty<'tcx> {
1462 pub fn def_id(&self) -> ast::DefId {
1466 pub fn substs(&self) -> &'tcx Substs<'tcx> {
1467 // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
1471 pub fn input_types(&self) -> &[Ty<'tcx>] {
1472 // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
1473 self.0.input_types()
1476 pub fn to_poly_trait_predicate(&self) -> PolyTraitPredicate<'tcx> {
1477 // Note that we preserve binding levels
1478 Binder(TraitPredicate { trait_ref: self.0.clone() })
1482 /// Binder is a binder for higher-ranked lifetimes. It is part of the
1483 /// compiler's representation for things like `for<'a> Fn(&'a isize)`
1484 /// (which would be represented by the type `PolyTraitRef ==
1485 /// Binder<TraitRef>`). Note that when we skolemize, instantiate,
1486 /// erase, or otherwise "discharge" these bound regions, we change the
1487 /// type from `Binder<T>` to just `T` (see
1488 /// e.g. `liberate_late_bound_regions`).
1489 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1490 pub struct Binder<T>(pub T);
1493 /// Skips the binder and returns the "bound" value. This is a
1494 /// risky thing to do because it's easy to get confused about
1495 /// debruijn indices and the like. It is usually better to
1496 /// discharge the binder using `no_late_bound_regions` or
1497 /// `replace_late_bound_regions` or something like
1498 /// that. `skip_binder` is only valid when you are either
1499 /// extracting data that has nothing to do with bound regions, you
1500 /// are doing some sort of test that does not involve bound
1501 /// regions, or you are being very careful about your depth
1504 /// Some examples where `skip_binder` is reasonable:
1505 /// - extracting the def-id from a PolyTraitRef;
1506 /// - comparing the self type of a PolyTraitRef to see if it is equal to
1507 /// a type parameter `X`, since the type `X` does not reference any regions
1508 pub fn skip_binder(&self) -> &T {
1512 pub fn as_ref(&self) -> Binder<&T> {
1516 pub fn map_bound_ref<F,U>(&self, f: F) -> Binder<U>
1517 where F: FnOnce(&T) -> U
1519 self.as_ref().map_bound(f)
1522 pub fn map_bound<F,U>(self, f: F) -> Binder<U>
1523 where F: FnOnce(T) -> U
1525 ty::Binder(f(self.0))
1529 #[derive(Clone, Copy, PartialEq)]
1530 pub enum IntVarValue {
1531 IntType(ast::IntTy),
1532 UintType(ast::UintTy),
1535 #[derive(Clone, Copy, Debug)]
1536 pub enum terr_vstore_kind {
1543 #[derive(Clone, Copy, Debug)]
1544 pub struct expected_found<T> {
1549 // Data structures used in type unification
1550 #[derive(Clone, Copy, Debug)]
1551 pub enum type_err<'tcx> {
1553 terr_unsafety_mismatch(expected_found<ast::Unsafety>),
1554 terr_abi_mismatch(expected_found<abi::Abi>),
1556 terr_box_mutability,
1557 terr_ptr_mutability,
1558 terr_ref_mutability,
1559 terr_vec_mutability,
1560 terr_tuple_size(expected_found<usize>),
1561 terr_fixed_array_size(expected_found<usize>),
1562 terr_ty_param_size(expected_found<usize>),
1564 terr_regions_does_not_outlive(Region, Region),
1565 terr_regions_not_same(Region, Region),
1566 terr_regions_no_overlap(Region, Region),
1567 terr_regions_insufficiently_polymorphic(BoundRegion, Region),
1568 terr_regions_overly_polymorphic(BoundRegion, Region),
1569 terr_sorts(expected_found<Ty<'tcx>>),
1570 terr_integer_as_char,
1571 terr_int_mismatch(expected_found<IntVarValue>),
1572 terr_float_mismatch(expected_found<ast::FloatTy>),
1573 terr_traits(expected_found<ast::DefId>),
1574 terr_builtin_bounds(expected_found<BuiltinBounds>),
1575 terr_variadic_mismatch(expected_found<bool>),
1577 terr_convergence_mismatch(expected_found<bool>),
1578 terr_projection_name_mismatched(expected_found<ast::Name>),
1579 terr_projection_bounds_length(expected_found<usize>),
1582 /// Bounds suitable for a named type parameter like `A` in `fn foo<A>`
1583 /// as well as the existential type parameter in an object type.
1584 #[derive(PartialEq, Eq, Hash, Clone, Debug)]
1585 pub struct ParamBounds<'tcx> {
1586 pub region_bounds: Vec<ty::Region>,
1587 pub builtin_bounds: BuiltinBounds,
1588 pub trait_bounds: Vec<PolyTraitRef<'tcx>>,
1589 pub projection_bounds: Vec<PolyProjectionPredicate<'tcx>>,
1592 /// Bounds suitable for an existentially quantified type parameter
1593 /// such as those that appear in object types or closure types. The
1594 /// major difference between this case and `ParamBounds` is that
1595 /// general purpose trait bounds are omitted and there must be
1596 /// *exactly one* region.
1597 #[derive(PartialEq, Eq, Hash, Clone, Debug)]
1598 pub struct ExistentialBounds<'tcx> {
1599 pub region_bound: ty::Region,
1600 pub builtin_bounds: BuiltinBounds,
1601 pub projection_bounds: Vec<PolyProjectionPredicate<'tcx>>,
1604 pub type BuiltinBounds = EnumSet<BuiltinBound>;
1606 #[derive(Clone, RustcEncodable, PartialEq, Eq, RustcDecodable, Hash,
1609 pub enum BuiltinBound {
1616 pub fn empty_builtin_bounds() -> BuiltinBounds {
1620 pub fn all_builtin_bounds() -> BuiltinBounds {
1621 let mut set = EnumSet::new();
1622 set.insert(BoundSend);
1623 set.insert(BoundSized);
1624 set.insert(BoundSync);
1628 /// An existential bound that does not implement any traits.
1629 pub fn region_existential_bound<'tcx>(r: ty::Region) -> ExistentialBounds<'tcx> {
1630 ty::ExistentialBounds { region_bound: r,
1631 builtin_bounds: empty_builtin_bounds(),
1632 projection_bounds: Vec::new() }
1635 impl CLike for BuiltinBound {
1636 fn to_usize(&self) -> usize {
1639 fn from_usize(v: usize) -> BuiltinBound {
1640 unsafe { mem::transmute(v) }
1644 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1649 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1654 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1655 pub struct FloatVid {
1659 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1660 pub struct RegionVid {
1664 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1670 /// A `FreshTy` is one that is generated as a replacement for an
1671 /// unbound type variable. This is convenient for caching etc. See
1672 /// `middle::infer::freshen` for more details.
1678 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
1679 pub enum UnconstrainedNumeric {
1686 #[derive(Clone, RustcEncodable, RustcDecodable, Eq, Hash, Debug, Copy)]
1687 pub enum InferRegion {
1689 ReSkolemized(u32, BoundRegion)
1692 impl cmp::PartialEq for InferRegion {
1693 fn eq(&self, other: &InferRegion) -> bool {
1694 match ((*self), *other) {
1695 (ReVar(rva), ReVar(rvb)) => {
1698 (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
1704 fn ne(&self, other: &InferRegion) -> bool {
1705 !((*self) == (*other))
1709 impl fmt::Debug for TyVid {
1710 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
1711 write!(f, "_#{}t", self.index)
1715 impl fmt::Debug for IntVid {
1716 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1717 write!(f, "_#{}i", self.index)
1721 impl fmt::Debug for FloatVid {
1722 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1723 write!(f, "_#{}f", self.index)
1727 impl fmt::Debug for RegionVid {
1728 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1729 write!(f, "'_#{}r", self.index)
1733 impl<'tcx> fmt::Debug for FnSig<'tcx> {
1734 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1735 write!(f, "({:?}; variadic: {})->{:?}", self.inputs, self.variadic, self.output)
1739 impl fmt::Debug for InferTy {
1740 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1742 TyVar(ref v) => v.fmt(f),
1743 IntVar(ref v) => v.fmt(f),
1744 FloatVar(ref v) => v.fmt(f),
1745 FreshTy(v) => write!(f, "FreshTy({:?})", v),
1746 FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
1747 FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v)
1752 impl fmt::Debug for IntVarValue {
1753 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1755 IntType(ref v) => v.fmt(f),
1756 UintType(ref v) => v.fmt(f),
1761 /// Default region to use for the bound of objects that are
1762 /// supplied as the value for this type parameter. This is derived
1763 /// from `T:'a` annotations appearing in the type definition. If
1764 /// this is `None`, then the default is inherited from the
1765 /// surrounding context. See RFC #599 for details.
1766 #[derive(Copy, Clone, Debug)]
1767 pub enum ObjectLifetimeDefault {
1768 /// Require an explicit annotation. Occurs when multiple
1769 /// `T:'a` constraints are found.
1772 /// Use the given region as the default.
1776 #[derive(Clone, Debug)]
1777 pub struct TypeParameterDef<'tcx> {
1778 pub name: ast::Name,
1779 pub def_id: ast::DefId,
1780 pub space: subst::ParamSpace,
1782 pub default: Option<Ty<'tcx>>,
1783 pub object_lifetime_default: Option<ObjectLifetimeDefault>,
1786 #[derive(RustcEncodable, RustcDecodable, Clone, Debug)]
1787 pub struct RegionParameterDef {
1788 pub name: ast::Name,
1789 pub def_id: ast::DefId,
1790 pub space: subst::ParamSpace,
1792 pub bounds: Vec<ty::Region>,
1795 impl RegionParameterDef {
1796 pub fn to_early_bound_region(&self) -> ty::Region {
1797 ty::ReEarlyBound(ty::EarlyBoundRegion {
1798 param_id: self.def_id.node,
1804 pub fn to_bound_region(&self) -> ty::BoundRegion {
1805 ty::BoundRegion::BrNamed(self.def_id, self.name)
1809 /// Information about the formal type/lifetime parameters associated
1810 /// with an item or method. Analogous to ast::Generics.
1811 #[derive(Clone, Debug)]
1812 pub struct Generics<'tcx> {
1813 pub types: VecPerParamSpace<TypeParameterDef<'tcx>>,
1814 pub regions: VecPerParamSpace<RegionParameterDef>,
1817 impl<'tcx> Generics<'tcx> {
1818 pub fn empty() -> Generics<'tcx> {
1820 types: VecPerParamSpace::empty(),
1821 regions: VecPerParamSpace::empty(),
1825 pub fn is_empty(&self) -> bool {
1826 self.types.is_empty() && self.regions.is_empty()
1829 pub fn has_type_params(&self, space: subst::ParamSpace) -> bool {
1830 !self.types.is_empty_in(space)
1833 pub fn has_region_params(&self, space: subst::ParamSpace) -> bool {
1834 !self.regions.is_empty_in(space)
1838 /// Bounds on generics.
1839 #[derive(Clone, Debug)]
1840 pub struct GenericPredicates<'tcx> {
1841 pub predicates: VecPerParamSpace<Predicate<'tcx>>,
1844 impl<'tcx> GenericPredicates<'tcx> {
1845 pub fn empty() -> GenericPredicates<'tcx> {
1847 predicates: VecPerParamSpace::empty(),
1851 pub fn instantiate(&self, tcx: &ty::ctxt<'tcx>, substs: &Substs<'tcx>)
1852 -> InstantiatedPredicates<'tcx> {
1853 InstantiatedPredicates {
1854 predicates: self.predicates.subst(tcx, substs),
1858 pub fn instantiate_supertrait(&self,
1859 tcx: &ty::ctxt<'tcx>,
1860 poly_trait_ref: &ty::PolyTraitRef<'tcx>)
1861 -> InstantiatedPredicates<'tcx>
1863 InstantiatedPredicates {
1864 predicates: self.predicates.map(|pred| pred.subst_supertrait(tcx, poly_trait_ref))
1869 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1870 pub enum Predicate<'tcx> {
1871 /// Corresponds to `where Foo : Bar<A,B,C>`. `Foo` here would be
1872 /// the `Self` type of the trait reference and `A`, `B`, and `C`
1873 /// would be the parameters in the `TypeSpace`.
1874 Trait(PolyTraitPredicate<'tcx>),
1876 /// where `T1 == T2`.
1877 Equate(PolyEquatePredicate<'tcx>),
1880 RegionOutlives(PolyRegionOutlivesPredicate),
1883 TypeOutlives(PolyTypeOutlivesPredicate<'tcx>),
1885 /// where <T as TraitRef>::Name == X, approximately.
1886 /// See `ProjectionPredicate` struct for details.
1887 Projection(PolyProjectionPredicate<'tcx>),
1890 impl<'tcx> Predicate<'tcx> {
1891 /// Performs a substitution suitable for going from a
1892 /// poly-trait-ref to supertraits that must hold if that
1893 /// poly-trait-ref holds. This is slightly different from a normal
1894 /// substitution in terms of what happens with bound regions. See
1895 /// lengthy comment below for details.
1896 pub fn subst_supertrait(&self,
1897 tcx: &ty::ctxt<'tcx>,
1898 trait_ref: &ty::PolyTraitRef<'tcx>)
1899 -> ty::Predicate<'tcx>
1901 // The interaction between HRTB and supertraits is not entirely
1902 // obvious. Let me walk you (and myself) through an example.
1904 // Let's start with an easy case. Consider two traits:
1906 // trait Foo<'a> : Bar<'a,'a> { }
1907 // trait Bar<'b,'c> { }
1909 // Now, if we have a trait reference `for<'x> T : Foo<'x>`, then
1910 // we can deduce that `for<'x> T : Bar<'x,'x>`. Basically, if we
1911 // knew that `Foo<'x>` (for any 'x) then we also know that
1912 // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
1913 // normal substitution.
1915 // In terms of why this is sound, the idea is that whenever there
1916 // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
1917 // holds. So if there is an impl of `T:Foo<'a>` that applies to
1918 // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
1921 // Another example to be careful of is this:
1923 // trait Foo1<'a> : for<'b> Bar1<'a,'b> { }
1924 // trait Bar1<'b,'c> { }
1926 // Here, if we have `for<'x> T : Foo1<'x>`, then what do we know?
1927 // The answer is that we know `for<'x,'b> T : Bar1<'x,'b>`. The
1928 // reason is similar to the previous example: any impl of
1929 // `T:Foo1<'x>` must show that `for<'b> T : Bar1<'x, 'b>`. So
1930 // basically we would want to collapse the bound lifetimes from
1931 // the input (`trait_ref`) and the supertraits.
1933 // To achieve this in practice is fairly straightforward. Let's
1934 // consider the more complicated scenario:
1936 // - We start out with `for<'x> T : Foo1<'x>`. In this case, `'x`
1937 // has a De Bruijn index of 1. We want to produce `for<'x,'b> T : Bar1<'x,'b>`,
1938 // where both `'x` and `'b` would have a DB index of 1.
1939 // The substitution from the input trait-ref is therefore going to be
1940 // `'a => 'x` (where `'x` has a DB index of 1).
1941 // - The super-trait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
1942 // early-bound parameter and `'b' is a late-bound parameter with a
1944 // - If we replace `'a` with `'x` from the input, it too will have
1945 // a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
1946 // just as we wanted.
1948 // There is only one catch. If we just apply the substitution `'a
1949 // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
1950 // adjust the DB index because we substituting into a binder (it
1951 // tries to be so smart...) resulting in `for<'x> for<'b>
1952 // Bar1<'x,'b>` (we have no syntax for this, so use your
1953 // imagination). Basically the 'x will have DB index of 2 and 'b
1954 // will have DB index of 1. Not quite what we want. So we apply
1955 // the substitution to the *contents* of the trait reference,
1956 // rather than the trait reference itself (put another way, the
1957 // substitution code expects equal binding levels in the values
1958 // from the substitution and the value being substituted into, and
1959 // this trick achieves that).
1961 let substs = &trait_ref.0.substs;
1963 Predicate::Trait(ty::Binder(ref data)) =>
1964 Predicate::Trait(ty::Binder(data.subst(tcx, substs))),
1965 Predicate::Equate(ty::Binder(ref data)) =>
1966 Predicate::Equate(ty::Binder(data.subst(tcx, substs))),
1967 Predicate::RegionOutlives(ty::Binder(ref data)) =>
1968 Predicate::RegionOutlives(ty::Binder(data.subst(tcx, substs))),
1969 Predicate::TypeOutlives(ty::Binder(ref data)) =>
1970 Predicate::TypeOutlives(ty::Binder(data.subst(tcx, substs))),
1971 Predicate::Projection(ty::Binder(ref data)) =>
1972 Predicate::Projection(ty::Binder(data.subst(tcx, substs))),
1977 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1978 pub struct TraitPredicate<'tcx> {
1979 pub trait_ref: TraitRef<'tcx>
1981 pub type PolyTraitPredicate<'tcx> = ty::Binder<TraitPredicate<'tcx>>;
1983 impl<'tcx> TraitPredicate<'tcx> {
1984 pub fn def_id(&self) -> ast::DefId {
1985 self.trait_ref.def_id
1988 pub fn input_types(&self) -> &[Ty<'tcx>] {
1989 self.trait_ref.substs.types.as_slice()
1992 pub fn self_ty(&self) -> Ty<'tcx> {
1993 self.trait_ref.self_ty()
1997 impl<'tcx> PolyTraitPredicate<'tcx> {
1998 pub fn def_id(&self) -> ast::DefId {
2003 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2004 pub struct EquatePredicate<'tcx>(pub Ty<'tcx>, pub Ty<'tcx>); // `0 == 1`
2005 pub type PolyEquatePredicate<'tcx> = ty::Binder<EquatePredicate<'tcx>>;
2007 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2008 pub struct OutlivesPredicate<A,B>(pub A, pub B); // `A : B`
2009 pub type PolyOutlivesPredicate<A,B> = ty::Binder<OutlivesPredicate<A,B>>;
2010 pub type PolyRegionOutlivesPredicate = PolyOutlivesPredicate<ty::Region, ty::Region>;
2011 pub type PolyTypeOutlivesPredicate<'tcx> = PolyOutlivesPredicate<Ty<'tcx>, ty::Region>;
2013 /// This kind of predicate has no *direct* correspondent in the
2014 /// syntax, but it roughly corresponds to the syntactic forms:
2016 /// 1. `T : TraitRef<..., Item=Type>`
2017 /// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
2019 /// In particular, form #1 is "desugared" to the combination of a
2020 /// normal trait predicate (`T : TraitRef<...>`) and one of these
2021 /// predicates. Form #2 is a broader form in that it also permits
2022 /// equality between arbitrary types. Processing an instance of Form
2023 /// #2 eventually yields one of these `ProjectionPredicate`
2024 /// instances to normalize the LHS.
2025 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2026 pub struct ProjectionPredicate<'tcx> {
2027 pub projection_ty: ProjectionTy<'tcx>,
2031 pub type PolyProjectionPredicate<'tcx> = Binder<ProjectionPredicate<'tcx>>;
2033 impl<'tcx> PolyProjectionPredicate<'tcx> {
2034 pub fn item_name(&self) -> ast::Name {
2035 self.0.projection_ty.item_name // safe to skip the binder to access a name
2038 pub fn sort_key(&self) -> (ast::DefId, ast::Name) {
2039 self.0.projection_ty.sort_key()
2043 /// Represents the projection of an associated type. In explicit UFCS
2044 /// form this would be written `<T as Trait<..>>::N`.
2045 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2046 pub struct ProjectionTy<'tcx> {
2047 /// The trait reference `T as Trait<..>`.
2048 pub trait_ref: ty::TraitRef<'tcx>,
2050 /// The name `N` of the associated type.
2051 pub item_name: ast::Name,
2054 impl<'tcx> ProjectionTy<'tcx> {
2055 pub fn sort_key(&self) -> (ast::DefId, ast::Name) {
2056 (self.trait_ref.def_id, self.item_name)
2060 pub trait ToPolyTraitRef<'tcx> {
2061 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
2064 impl<'tcx> ToPolyTraitRef<'tcx> for TraitRef<'tcx> {
2065 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2066 assert!(!self.has_escaping_regions());
2067 ty::Binder(self.clone())
2071 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
2072 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2073 self.map_bound_ref(|trait_pred| trait_pred.trait_ref.clone())
2077 impl<'tcx> ToPolyTraitRef<'tcx> for PolyProjectionPredicate<'tcx> {
2078 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2079 // Note: unlike with TraitRef::to_poly_trait_ref(),
2080 // self.0.trait_ref is permitted to have escaping regions.
2081 // This is because here `self` has a `Binder` and so does our
2082 // return value, so we are preserving the number of binding
2084 ty::Binder(self.0.projection_ty.trait_ref.clone())
2088 pub trait AsPredicate<'tcx> {
2089 fn as_predicate(&self) -> Predicate<'tcx>;
2092 impl<'tcx> AsPredicate<'tcx> for TraitRef<'tcx> {
2093 fn as_predicate(&self) -> Predicate<'tcx> {
2094 // we're about to add a binder, so let's check that we don't
2095 // accidentally capture anything, or else that might be some
2096 // weird debruijn accounting.
2097 assert!(!self.has_escaping_regions());
2099 ty::Predicate::Trait(ty::Binder(ty::TraitPredicate {
2100 trait_ref: self.clone()
2105 impl<'tcx> AsPredicate<'tcx> for PolyTraitRef<'tcx> {
2106 fn as_predicate(&self) -> Predicate<'tcx> {
2107 ty::Predicate::Trait(self.to_poly_trait_predicate())
2111 impl<'tcx> AsPredicate<'tcx> for PolyEquatePredicate<'tcx> {
2112 fn as_predicate(&self) -> Predicate<'tcx> {
2113 Predicate::Equate(self.clone())
2117 impl<'tcx> AsPredicate<'tcx> for PolyRegionOutlivesPredicate {
2118 fn as_predicate(&self) -> Predicate<'tcx> {
2119 Predicate::RegionOutlives(self.clone())
2123 impl<'tcx> AsPredicate<'tcx> for PolyTypeOutlivesPredicate<'tcx> {
2124 fn as_predicate(&self) -> Predicate<'tcx> {
2125 Predicate::TypeOutlives(self.clone())
2129 impl<'tcx> AsPredicate<'tcx> for PolyProjectionPredicate<'tcx> {
2130 fn as_predicate(&self) -> Predicate<'tcx> {
2131 Predicate::Projection(self.clone())
2135 impl<'tcx> Predicate<'tcx> {
2136 /// Iterates over the types in this predicate. Note that in all
2137 /// cases this is skipping over a binder, so late-bound regions
2138 /// with depth 0 are bound by the predicate.
2139 pub fn walk_tys(&self) -> IntoIter<Ty<'tcx>> {
2140 let vec: Vec<_> = match *self {
2141 ty::Predicate::Trait(ref data) => {
2142 data.0.trait_ref.substs.types.as_slice().to_vec()
2144 ty::Predicate::Equate(ty::Binder(ref data)) => {
2145 vec![data.0, data.1]
2147 ty::Predicate::TypeOutlives(ty::Binder(ref data)) => {
2150 ty::Predicate::RegionOutlives(..) => {
2153 ty::Predicate::Projection(ref data) => {
2154 let trait_inputs = data.0.projection_ty.trait_ref.substs.types.as_slice();
2157 .chain(Some(data.0.ty).into_iter())
2162 // The only reason to collect into a vector here is that I was
2163 // too lazy to make the full (somewhat complicated) iterator
2164 // type that would be needed here. But I wanted this fn to
2165 // return an iterator conceptually, rather than a `Vec`, so as
2166 // to be closer to `Ty::walk`.
2170 pub fn has_escaping_regions(&self) -> bool {
2172 Predicate::Trait(ref trait_ref) => trait_ref.has_escaping_regions(),
2173 Predicate::Equate(ref p) => p.has_escaping_regions(),
2174 Predicate::RegionOutlives(ref p) => p.has_escaping_regions(),
2175 Predicate::TypeOutlives(ref p) => p.has_escaping_regions(),
2176 Predicate::Projection(ref p) => p.has_escaping_regions(),
2180 pub fn to_opt_poly_trait_ref(&self) -> Option<PolyTraitRef<'tcx>> {
2182 Predicate::Trait(ref t) => {
2183 Some(t.to_poly_trait_ref())
2185 Predicate::Projection(..) |
2186 Predicate::Equate(..) |
2187 Predicate::RegionOutlives(..) |
2188 Predicate::TypeOutlives(..) => {
2195 /// Represents the bounds declared on a particular set of type
2196 /// parameters. Should eventually be generalized into a flag list of
2197 /// where clauses. You can obtain a `InstantiatedPredicates` list from a
2198 /// `GenericPredicates` by using the `instantiate` method. Note that this method
2199 /// reflects an important semantic invariant of `InstantiatedPredicates`: while
2200 /// the `GenericPredicates` are expressed in terms of the bound type
2201 /// parameters of the impl/trait/whatever, an `InstantiatedPredicates` instance
2202 /// represented a set of bounds for some particular instantiation,
2203 /// meaning that the generic parameters have been substituted with
2208 /// struct Foo<T,U:Bar<T>> { ... }
2210 /// Here, the `GenericPredicates` for `Foo` would contain a list of bounds like
2211 /// `[[], [U:Bar<T>]]`. Now if there were some particular reference
2212 /// like `Foo<isize,usize>`, then the `InstantiatedPredicates` would be `[[],
2213 /// [usize:Bar<isize>]]`.
2214 #[derive(Clone, Debug)]
2215 pub struct InstantiatedPredicates<'tcx> {
2216 pub predicates: VecPerParamSpace<Predicate<'tcx>>,
2219 impl<'tcx> InstantiatedPredicates<'tcx> {
2220 pub fn empty() -> InstantiatedPredicates<'tcx> {
2221 InstantiatedPredicates { predicates: VecPerParamSpace::empty() }
2224 pub fn has_escaping_regions(&self) -> bool {
2225 self.predicates.any(|p| p.has_escaping_regions())
2228 pub fn is_empty(&self) -> bool {
2229 self.predicates.is_empty()
2233 impl<'tcx> TraitRef<'tcx> {
2234 pub fn new(def_id: ast::DefId, substs: &'tcx Substs<'tcx>) -> TraitRef<'tcx> {
2235 TraitRef { def_id: def_id, substs: substs }
2238 pub fn self_ty(&self) -> Ty<'tcx> {
2239 self.substs.self_ty().unwrap()
2242 pub fn input_types(&self) -> &[Ty<'tcx>] {
2243 // Select only the "input types" from a trait-reference. For
2244 // now this is all the types that appear in the
2245 // trait-reference, but it should eventually exclude
2246 // associated types.
2247 self.substs.types.as_slice()
2251 /// When type checking, we use the `ParameterEnvironment` to track
2252 /// details about the type/lifetime parameters that are in scope.
2253 /// It primarily stores the bounds information.
2255 /// Note: This information might seem to be redundant with the data in
2256 /// `tcx.ty_param_defs`, but it is not. That table contains the
2257 /// parameter definitions from an "outside" perspective, but this
2258 /// struct will contain the bounds for a parameter as seen from inside
2259 /// the function body. Currently the only real distinction is that
2260 /// bound lifetime parameters are replaced with free ones, but in the
2261 /// future I hope to refine the representation of types so as to make
2262 /// more distinctions clearer.
2264 pub struct ParameterEnvironment<'a, 'tcx:'a> {
2265 pub tcx: &'a ctxt<'tcx>,
2267 /// See `construct_free_substs` for details.
2268 pub free_substs: Substs<'tcx>,
2270 /// Each type parameter has an implicit region bound that
2271 /// indicates it must outlive at least the function body (the user
2272 /// may specify stronger requirements). This field indicates the
2273 /// region of the callee.
2274 pub implicit_region_bound: ty::Region,
2276 /// Obligations that the caller must satisfy. This is basically
2277 /// the set of bounds on the in-scope type parameters, translated
2278 /// into Obligations.
2279 pub caller_bounds: Vec<ty::Predicate<'tcx>>,
2281 /// Caches the results of trait selection. This cache is used
2282 /// for things that have to do with the parameters in scope.
2283 pub selection_cache: traits::SelectionCache<'tcx>,
2286 impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
2287 pub fn with_caller_bounds(&self,
2288 caller_bounds: Vec<ty::Predicate<'tcx>>)
2289 -> ParameterEnvironment<'a,'tcx>
2291 ParameterEnvironment {
2293 free_substs: self.free_substs.clone(),
2294 implicit_region_bound: self.implicit_region_bound,
2295 caller_bounds: caller_bounds,
2296 selection_cache: traits::SelectionCache::new(),
2300 pub fn for_item(cx: &'a ctxt<'tcx>, id: NodeId) -> ParameterEnvironment<'a, 'tcx> {
2301 match cx.map.find(id) {
2302 Some(ast_map::NodeImplItem(ref impl_item)) => {
2303 match impl_item.node {
2304 ast::ConstImplItem(_, _) => {
2305 let def_id = ast_util::local_def(id);
2306 let scheme = lookup_item_type(cx, def_id);
2307 let predicates = lookup_predicates(cx, def_id);
2308 construct_parameter_environment(cx,
2314 ast::MethodImplItem(_, ref body) => {
2315 let method_def_id = ast_util::local_def(id);
2316 match ty::impl_or_trait_item(cx, method_def_id) {
2317 MethodTraitItem(ref method_ty) => {
2318 let method_generics = &method_ty.generics;
2319 let method_bounds = &method_ty.predicates;
2320 construct_parameter_environment(
2329 .bug("ParameterEnvironment::for_item(): \
2330 got non-method item from impl method?!")
2334 ast::TypeImplItem(_) => {
2335 cx.sess.bug("ParameterEnvironment::for_item(): \
2336 can't create a parameter environment \
2337 for type impl items")
2339 ast::MacImplItem(_) => cx.sess.bug("unexpanded macro")
2342 Some(ast_map::NodeTraitItem(trait_item)) => {
2343 match trait_item.node {
2344 ast::ConstTraitItem(_, ref default) => {
2347 let def_id = ast_util::local_def(id);
2348 let scheme = lookup_item_type(cx, def_id);
2349 let predicates = lookup_predicates(cx, def_id);
2350 construct_parameter_environment(cx,
2357 cx.sess.bug("ParameterEnvironment::from_item(): \
2358 can't create a parameter environment \
2359 for const trait items without defaults")
2363 ast::MethodTraitItem(_, None) => {
2364 cx.sess.span_bug(trait_item.span,
2365 "ParameterEnvironment::for_item():
2366 can't create a parameter \
2367 environment for required trait \
2370 ast::MethodTraitItem(_, Some(ref body)) => {
2371 let method_def_id = ast_util::local_def(id);
2372 match ty::impl_or_trait_item(cx, method_def_id) {
2373 MethodTraitItem(ref method_ty) => {
2374 let method_generics = &method_ty.generics;
2375 let method_bounds = &method_ty.predicates;
2376 construct_parameter_environment(
2385 .bug("ParameterEnvironment::for_item(): \
2386 got non-method item from provided \
2391 ast::TypeTraitItem(..) => {
2392 cx.sess.bug("ParameterEnvironment::from_item(): \
2393 can't create a parameter environment \
2394 for type trait items")
2398 Some(ast_map::NodeItem(item)) => {
2400 ast::ItemFn(_, _, _, _, _, ref body) => {
2401 // We assume this is a function.
2402 let fn_def_id = ast_util::local_def(id);
2403 let fn_scheme = lookup_item_type(cx, fn_def_id);
2404 let fn_predicates = lookup_predicates(cx, fn_def_id);
2406 construct_parameter_environment(cx,
2408 &fn_scheme.generics,
2413 ast::ItemStruct(..) |
2415 ast::ItemConst(..) |
2416 ast::ItemStatic(..) => {
2417 let def_id = ast_util::local_def(id);
2418 let scheme = lookup_item_type(cx, def_id);
2419 let predicates = lookup_predicates(cx, def_id);
2420 construct_parameter_environment(cx,
2427 cx.sess.span_bug(item.span,
2428 "ParameterEnvironment::from_item():
2429 can't create a parameter \
2430 environment for this kind of item")
2434 Some(ast_map::NodeExpr(..)) => {
2435 // This is a convenience to allow closures to work.
2436 ParameterEnvironment::for_item(cx, cx.map.get_parent(id))
2439 cx.sess.bug(&format!("ParameterEnvironment::from_item(): \
2440 `{}` is not an item",
2441 cx.map.node_to_string(id)))
2447 /// A "type scheme", in ML terminology, is a type combined with some
2448 /// set of generic types that the type is, well, generic over. In Rust
2449 /// terms, it is the "type" of a fn item or struct -- this type will
2450 /// include various generic parameters that must be substituted when
2451 /// the item/struct is referenced. That is called converting the type
2452 /// scheme to a monotype.
2454 /// - `generics`: the set of type parameters and their bounds
2455 /// - `ty`: the base types, which may reference the parameters defined
2458 /// Note that TypeSchemes are also sometimes called "polytypes" (and
2459 /// in fact this struct used to carry that name, so you may find some
2460 /// stray references in a comment or something). We try to reserve the
2461 /// "poly" prefix to refer to higher-ranked things, as in
2464 /// Note that each item also comes with predicates, see
2465 /// `lookup_predicates`.
2466 #[derive(Clone, Debug)]
2467 pub struct TypeScheme<'tcx> {
2468 pub generics: Generics<'tcx>,
2473 flags TraitFlags: u32 {
2474 const NO_TRAIT_FLAGS = 0,
2475 const HAS_DEFAULT_IMPL = 1 << 0,
2476 const IS_OBJECT_SAFE = 1 << 1,
2477 const OBJECT_SAFETY_VALID = 1 << 2,
2478 const IMPLS_VALID = 1 << 3,
2482 /// As `TypeScheme` but for a trait ref.
2483 pub struct TraitDef<'tcx> {
2484 pub unsafety: ast::Unsafety,
2486 /// If `true`, then this trait had the `#[rustc_paren_sugar]`
2487 /// attribute, indicating that it should be used with `Foo()`
2488 /// sugar. This is a temporary thing -- eventually any trait wil
2489 /// be usable with the sugar (or without it).
2490 pub paren_sugar: bool,
2492 /// Generic type definitions. Note that `Self` is listed in here
2493 /// as having a single bound, the trait itself (e.g., in the trait
2494 /// `Eq`, there is a single bound `Self : Eq`). This is so that
2495 /// default methods get to assume that the `Self` parameters
2496 /// implements the trait.
2497 pub generics: Generics<'tcx>,
2499 pub trait_ref: TraitRef<'tcx>,
2501 /// A list of the associated types defined in this trait. Useful
2502 /// for resolving `X::Foo` type markers.
2503 pub associated_type_names: Vec<ast::Name>,
2505 // Impls of this trait. To allow for quicker lookup, the impls are indexed
2506 // by a simplified version of their Self type: impls with a simplifiable
2507 // Self are stored in nonblanket_impls keyed by it, while all other impls
2508 // are stored in blanket_impls.
2510 /// Impls of the trait.
2511 pub nonblanket_impls: RefCell<
2512 FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>
2515 /// Blanket impls associated with the trait.
2516 pub blanket_impls: RefCell<Vec<DefId>>,
2519 pub flags: Cell<TraitFlags>
2522 impl<'tcx> TraitDef<'tcx> {
2523 // returns None if not yet calculated
2524 pub fn object_safety(&self) -> Option<bool> {
2525 if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
2526 Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
2532 pub fn set_object_safety(&self, is_safe: bool) {
2533 assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
2535 self.flags.get() | if is_safe {
2536 TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
2538 TraitFlags::OBJECT_SAFETY_VALID
2543 /// Records a trait-to-implementation mapping.
2544 pub fn record_impl(&self,
2547 impl_trait_ref: TraitRef<'tcx>) {
2548 debug!("TraitDef::record_impl for {}, from {}",
2549 self.repr(tcx), impl_trait_ref.repr(tcx));
2551 // We don't want to borrow_mut after we already populated all impls,
2552 // so check if an impl is present with an immutable borrow first.
2553 if let Some(sty) = fast_reject::simplify_type(tcx,
2554 impl_trait_ref.self_ty(), false) {
2555 if let Some(is) = self.nonblanket_impls.borrow().get(&sty) {
2556 if is.contains(&impl_def_id) {
2557 return // duplicate - skip
2561 self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
2563 if self.blanket_impls.borrow().contains(&impl_def_id) {
2564 return // duplicate - skip
2566 self.blanket_impls.borrow_mut().push(impl_def_id)
2571 pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &ctxt<'tcx>, mut f: F) {
2572 ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
2574 for &impl_def_id in self.blanket_impls.borrow().iter() {
2578 for v in self.nonblanket_impls.borrow().values() {
2579 for &impl_def_id in v {
2585 pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
2590 ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
2592 for &impl_def_id in self.blanket_impls.borrow().iter() {
2596 if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, false) {
2597 if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
2598 for &impl_def_id in impls {
2601 return; // we don't need to process the other non-blanket impls
2605 for v in self.nonblanket_impls.borrow().values() {
2606 for &impl_def_id in v {
2614 /// Records the substitutions used to translate the polytype for an
2615 /// item into the monotype of an item reference.
2617 pub struct ItemSubsts<'tcx> {
2618 pub substs: Substs<'tcx>,
2621 #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Debug, RustcEncodable, RustcDecodable)]
2622 pub enum ClosureKind {
2623 // Warning: Ordering is significant here! The ordering is chosen
2624 // because the trait Fn is a subtrait of FnMut and so in turn, and
2625 // hence we order it so that Fn < FnMut < FnOnce.
2632 pub fn trait_did(&self, cx: &ctxt) -> ast::DefId {
2633 let result = match *self {
2634 FnClosureKind => cx.lang_items.require(FnTraitLangItem),
2635 FnMutClosureKind => {
2636 cx.lang_items.require(FnMutTraitLangItem)
2638 FnOnceClosureKind => {
2639 cx.lang_items.require(FnOnceTraitLangItem)
2643 Ok(trait_did) => trait_did,
2644 Err(err) => cx.sess.fatal(&err[..]),
2648 /// True if this a type that impls this closure kind
2649 /// must also implement `other`.
2650 pub fn extends(self, other: ty::ClosureKind) -> bool {
2651 match (self, other) {
2652 (FnClosureKind, FnClosureKind) => true,
2653 (FnClosureKind, FnMutClosureKind) => true,
2654 (FnClosureKind, FnOnceClosureKind) => true,
2655 (FnMutClosureKind, FnMutClosureKind) => true,
2656 (FnMutClosureKind, FnOnceClosureKind) => true,
2657 (FnOnceClosureKind, FnOnceClosureKind) => true,
2663 pub trait ClosureTyper<'tcx> {
2664 fn tcx(&self) -> &ty::ctxt<'tcx> {
2665 self.param_env().tcx
2668 fn param_env<'a>(&'a self) -> &'a ty::ParameterEnvironment<'a, 'tcx>;
2670 /// Is this a `Fn`, `FnMut` or `FnOnce` closure? During typeck,
2671 /// returns `None` if the kind of this closure has not yet been
2673 fn closure_kind(&self,
2675 -> Option<ty::ClosureKind>;
2677 /// Returns the argument/return types of this closure.
2678 fn closure_type(&self,
2680 substs: &subst::Substs<'tcx>)
2681 -> ty::ClosureTy<'tcx>;
2683 /// Returns the set of all upvars and their transformed
2684 /// types. During typeck, maybe return `None` if the upvar types
2685 /// have not yet been inferred.
2686 fn closure_upvars(&self,
2688 substs: &Substs<'tcx>)
2689 -> Option<Vec<ClosureUpvar<'tcx>>>;
2692 impl<'tcx> CommonTypes<'tcx> {
2693 fn new(arena: &'tcx TypedArena<TyS<'tcx>>,
2694 interner: &mut FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>)
2695 -> CommonTypes<'tcx>
2698 bool: intern_ty(arena, interner, ty_bool),
2699 char: intern_ty(arena, interner, ty_char),
2700 err: intern_ty(arena, interner, ty_err),
2701 isize: intern_ty(arena, interner, ty_int(ast::TyIs)),
2702 i8: intern_ty(arena, interner, ty_int(ast::TyI8)),
2703 i16: intern_ty(arena, interner, ty_int(ast::TyI16)),
2704 i32: intern_ty(arena, interner, ty_int(ast::TyI32)),
2705 i64: intern_ty(arena, interner, ty_int(ast::TyI64)),
2706 usize: intern_ty(arena, interner, ty_uint(ast::TyUs)),
2707 u8: intern_ty(arena, interner, ty_uint(ast::TyU8)),
2708 u16: intern_ty(arena, interner, ty_uint(ast::TyU16)),
2709 u32: intern_ty(arena, interner, ty_uint(ast::TyU32)),
2710 u64: intern_ty(arena, interner, ty_uint(ast::TyU64)),
2711 f32: intern_ty(arena, interner, ty_float(ast::TyF32)),
2712 f64: intern_ty(arena, interner, ty_float(ast::TyF64)),
2717 pub fn mk_ctxt<'tcx>(s: Session,
2718 arenas: &'tcx CtxtArenas<'tcx>,
2720 named_region_map: resolve_lifetime::NamedRegionMap,
2721 map: ast_map::Map<'tcx>,
2722 freevars: RefCell<FreevarMap>,
2723 region_maps: RegionMaps,
2724 lang_items: middle::lang_items::LanguageItems,
2725 stability: stability::Index<'tcx>) -> ctxt<'tcx>
2727 let mut interner = FnvHashMap();
2728 let common_types = CommonTypes::new(&arenas.type_, &mut interner);
2732 interner: RefCell::new(interner),
2733 substs_interner: RefCell::new(FnvHashMap()),
2734 bare_fn_interner: RefCell::new(FnvHashMap()),
2735 region_interner: RefCell::new(FnvHashMap()),
2736 stability_interner: RefCell::new(FnvHashMap()),
2737 types: common_types,
2738 named_region_map: named_region_map,
2739 region_maps: region_maps,
2740 free_region_maps: RefCell::new(FnvHashMap()),
2741 item_variance_map: RefCell::new(DefIdMap()),
2742 variance_computed: Cell::new(false),
2745 node_types: RefCell::new(FnvHashMap()),
2746 item_substs: RefCell::new(NodeMap()),
2747 impl_trait_refs: RefCell::new(DefIdMap()),
2748 trait_defs: RefCell::new(DefIdMap()),
2749 predicates: RefCell::new(DefIdMap()),
2750 super_predicates: RefCell::new(DefIdMap()),
2753 tcache: RefCell::new(DefIdMap()),
2754 rcache: RefCell::new(FnvHashMap()),
2755 tc_cache: RefCell::new(FnvHashMap()),
2756 ast_ty_to_ty_cache: RefCell::new(NodeMap()),
2757 enum_var_cache: RefCell::new(DefIdMap()),
2758 impl_or_trait_items: RefCell::new(DefIdMap()),
2759 trait_item_def_ids: RefCell::new(DefIdMap()),
2760 trait_items_cache: RefCell::new(DefIdMap()),
2761 ty_param_defs: RefCell::new(NodeMap()),
2762 adjustments: RefCell::new(NodeMap()),
2763 normalized_cache: RefCell::new(FnvHashMap()),
2764 lang_items: lang_items,
2765 provided_method_sources: RefCell::new(DefIdMap()),
2766 struct_fields: RefCell::new(DefIdMap()),
2767 destructor_for_type: RefCell::new(DefIdMap()),
2768 destructors: RefCell::new(DefIdSet()),
2769 inherent_impls: RefCell::new(DefIdMap()),
2770 impl_items: RefCell::new(DefIdMap()),
2771 used_unsafe: RefCell::new(NodeSet()),
2772 used_mut_nodes: RefCell::new(NodeSet()),
2773 populated_external_types: RefCell::new(DefIdSet()),
2774 populated_external_primitive_impls: RefCell::new(DefIdSet()),
2775 upvar_capture_map: RefCell::new(FnvHashMap()),
2776 extern_const_statics: RefCell::new(DefIdMap()),
2777 extern_const_variants: RefCell::new(DefIdMap()),
2778 extern_const_fns: RefCell::new(DefIdMap()),
2779 method_map: RefCell::new(FnvHashMap()),
2780 dependency_formats: RefCell::new(FnvHashMap()),
2781 closure_kinds: RefCell::new(DefIdMap()),
2782 closure_tys: RefCell::new(DefIdMap()),
2783 node_lint_levels: RefCell::new(FnvHashMap()),
2784 transmute_restrictions: RefCell::new(Vec::new()),
2785 stability: RefCell::new(stability),
2786 selection_cache: traits::SelectionCache::new(),
2787 repr_hint_cache: RefCell::new(DefIdMap()),
2788 const_qualif_map: RefCell::new(NodeMap()),
2789 custom_coerce_unsized_kinds: RefCell::new(DefIdMap()),
2790 cast_kinds: RefCell::new(NodeMap()),
2794 // Type constructors
2796 impl<'tcx> ctxt<'tcx> {
2797 pub fn mk_substs(&self, substs: Substs<'tcx>) -> &'tcx Substs<'tcx> {
2798 if let Some(substs) = self.substs_interner.borrow().get(&substs) {
2802 let substs = self.arenas.substs.alloc(substs);
2803 self.substs_interner.borrow_mut().insert(substs, substs);
2807 /// Create an unsafe fn ty based on a safe fn ty.
2808 pub fn safe_to_unsafe_fn_ty(&self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
2809 assert_eq!(bare_fn.unsafety, ast::Unsafety::Normal);
2810 let unsafe_fn_ty_a = self.mk_bare_fn(ty::BareFnTy {
2811 unsafety: ast::Unsafety::Unsafe,
2813 sig: bare_fn.sig.clone()
2815 ty::mk_bare_fn(self, None, unsafe_fn_ty_a)
2818 pub fn mk_bare_fn(&self, bare_fn: BareFnTy<'tcx>) -> &'tcx BareFnTy<'tcx> {
2819 if let Some(bare_fn) = self.bare_fn_interner.borrow().get(&bare_fn) {
2823 let bare_fn = self.arenas.bare_fn.alloc(bare_fn);
2824 self.bare_fn_interner.borrow_mut().insert(bare_fn, bare_fn);
2828 pub fn mk_region(&self, region: Region) -> &'tcx Region {
2829 if let Some(region) = self.region_interner.borrow().get(®ion) {
2833 let region = self.arenas.region.alloc(region);
2834 self.region_interner.borrow_mut().insert(region, region);
2838 pub fn closure_kind(&self, def_id: ast::DefId) -> ty::ClosureKind {
2839 *self.closure_kinds.borrow().get(&def_id).unwrap()
2842 pub fn closure_type(&self,
2844 substs: &subst::Substs<'tcx>)
2845 -> ty::ClosureTy<'tcx>
2847 self.closure_tys.borrow().get(&def_id).unwrap().subst(self, substs)
2850 pub fn type_parameter_def(&self,
2851 node_id: ast::NodeId)
2852 -> TypeParameterDef<'tcx>
2854 self.ty_param_defs.borrow().get(&node_id).unwrap().clone()
2857 pub fn pat_contains_ref_binding(&self, pat: &ast::Pat) -> Option<ast::Mutability> {
2858 pat_util::pat_contains_ref_binding(&self.def_map, pat)
2861 pub fn arm_contains_ref_binding(&self, arm: &ast::Arm) -> Option<ast::Mutability> {
2862 pat_util::arm_contains_ref_binding(&self.def_map, arm)
2866 // Interns a type/name combination, stores the resulting box in cx.interner,
2867 // and returns the box as cast to an unsafe ptr (see comments for Ty above).
2868 pub fn mk_t<'tcx>(cx: &ctxt<'tcx>, st: sty<'tcx>) -> Ty<'tcx> {
2869 let mut interner = cx.interner.borrow_mut();
2870 intern_ty(&cx.arenas.type_, &mut *interner, st)
2873 fn intern_ty<'tcx>(type_arena: &'tcx TypedArena<TyS<'tcx>>,
2874 interner: &mut FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>,
2878 match interner.get(&st) {
2879 Some(ty) => return *ty,
2883 let flags = FlagComputation::for_sty(&st);
2886 () => type_arena.alloc(TyS { sty: st,
2887 flags: Cell::new(flags.flags),
2888 region_depth: flags.depth, }),
2891 debug!("Interned type: {:?} Pointer: {:?}",
2892 ty, ty as *const TyS);
2894 interner.insert(InternedTy { ty: ty }, ty);
2899 struct FlagComputation {
2902 // maximum depth of any bound region that we have seen thus far
2906 impl FlagComputation {
2907 fn new() -> FlagComputation {
2908 FlagComputation { flags: TypeFlags::empty(), depth: 0 }
2911 fn for_sty(st: &sty) -> FlagComputation {
2912 let mut result = FlagComputation::new();
2917 fn add_flags(&mut self, flags: TypeFlags) {
2918 self.flags = self.flags | (flags & TypeFlags::NOMINAL_FLAGS);
2921 fn add_depth(&mut self, depth: u32) {
2922 if depth > self.depth {
2927 /// Adds the flags/depth from a set of types that appear within the current type, but within a
2929 fn add_bound_computation(&mut self, computation: &FlagComputation) {
2930 self.add_flags(computation.flags);
2932 // The types that contributed to `computation` occurred within
2933 // a region binder, so subtract one from the region depth
2934 // within when adding the depth to `self`.
2935 let depth = computation.depth;
2937 self.add_depth(depth - 1);
2941 fn add_sty(&mut self, st: &sty) {
2951 // You might think that we could just return ty_err for
2952 // any type containing ty_err as a component, and get
2953 // rid of the TypeFlags::HAS_TY_ERR flag -- likewise for ty_bot (with
2954 // the exception of function types that return bot).
2955 // But doing so caused sporadic memory corruption, and
2956 // neither I (tjc) nor nmatsakis could figure out why,
2957 // so we're doing it this way.
2959 self.add_flags(TypeFlags::HAS_TY_ERR)
2962 &ty_param(ref p) => {
2963 if p.space == subst::SelfSpace {
2964 self.add_flags(TypeFlags::HAS_SELF);
2966 self.add_flags(TypeFlags::HAS_PARAMS);
2970 &ty_closure(_, substs) => {
2971 self.add_flags(TypeFlags::HAS_TY_CLOSURE);
2972 self.add_substs(substs);
2976 self.add_flags(TypeFlags::HAS_TY_INFER)
2979 &ty_enum(_, substs) | &ty_struct(_, substs) => {
2980 self.add_substs(substs);
2983 &ty_projection(ref data) => {
2984 self.add_flags(TypeFlags::HAS_PROJECTION);
2985 self.add_projection_ty(data);
2988 &ty_trait(box TyTrait { ref principal, ref bounds }) => {
2989 let mut computation = FlagComputation::new();
2990 computation.add_substs(principal.0.substs);
2991 for projection_bound in &bounds.projection_bounds {
2992 let mut proj_computation = FlagComputation::new();
2993 proj_computation.add_projection_predicate(&projection_bound.0);
2994 self.add_bound_computation(&proj_computation);
2996 self.add_bound_computation(&computation);
2998 self.add_bounds(bounds);
3001 &ty_uniq(tt) | &ty_vec(tt, _) => {
3009 &ty_rptr(r, ref m) => {
3010 self.add_region(*r);
3014 &ty_tup(ref ts) => {
3015 self.add_tys(&ts[..]);
3018 &ty_bare_fn(_, ref f) => {
3019 self.add_fn_sig(&f.sig);
3024 fn add_ty(&mut self, ty: Ty) {
3025 self.add_flags(ty.flags.get());
3026 self.add_depth(ty.region_depth);
3029 fn add_tys(&mut self, tys: &[Ty]) {
3035 fn add_fn_sig(&mut self, fn_sig: &PolyFnSig) {
3036 let mut computation = FlagComputation::new();
3038 computation.add_tys(&fn_sig.0.inputs);
3040 if let ty::FnConverging(output) = fn_sig.0.output {
3041 computation.add_ty(output);
3044 self.add_bound_computation(&computation);
3047 fn add_region(&mut self, r: Region) {
3049 ty::ReInfer(_) => { self.add_flags(TypeFlags::HAS_RE_INFER); }
3050 ty::ReLateBound(debruijn, _) => { self.add_depth(debruijn.depth); }
3051 ty::ReEarlyBound(..) => { self.add_flags(TypeFlags::HAS_RE_EARLY_BOUND); }
3053 _ => { self.add_flags(TypeFlags::HAS_FREE_REGIONS); }
3057 fn add_projection_predicate(&mut self, projection_predicate: &ProjectionPredicate) {
3058 self.add_projection_ty(&projection_predicate.projection_ty);
3059 self.add_ty(projection_predicate.ty);
3062 fn add_projection_ty(&mut self, projection_ty: &ProjectionTy) {
3063 self.add_substs(projection_ty.trait_ref.substs);
3066 fn add_substs(&mut self, substs: &Substs) {
3067 self.add_tys(substs.types.as_slice());
3068 match substs.regions {
3069 subst::ErasedRegions => {}
3070 subst::NonerasedRegions(ref regions) => {
3071 for &r in regions.iter() {
3078 fn add_bounds(&mut self, bounds: &ExistentialBounds) {
3079 self.add_region(bounds.region_bound);
3083 pub fn mk_mach_int<'tcx>(tcx: &ctxt<'tcx>, tm: ast::IntTy) -> Ty<'tcx> {
3085 ast::TyIs => tcx.types.isize,
3086 ast::TyI8 => tcx.types.i8,
3087 ast::TyI16 => tcx.types.i16,
3088 ast::TyI32 => tcx.types.i32,
3089 ast::TyI64 => tcx.types.i64,
3093 pub fn mk_mach_uint<'tcx>(tcx: &ctxt<'tcx>, tm: ast::UintTy) -> Ty<'tcx> {
3095 ast::TyUs => tcx.types.usize,
3096 ast::TyU8 => tcx.types.u8,
3097 ast::TyU16 => tcx.types.u16,
3098 ast::TyU32 => tcx.types.u32,
3099 ast::TyU64 => tcx.types.u64,
3103 pub fn mk_mach_float<'tcx>(tcx: &ctxt<'tcx>, tm: ast::FloatTy) -> Ty<'tcx> {
3105 ast::TyF32 => tcx.types.f32,
3106 ast::TyF64 => tcx.types.f64,
3110 pub fn mk_str<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3114 pub fn mk_str_slice<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, m: ast::Mutability) -> Ty<'tcx> {
3117 ty: mk_t(cx, ty_str),
3122 pub fn mk_enum<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
3123 // take a copy of substs so that we own the vectors inside
3124 mk_t(cx, ty_enum(did, substs))
3127 pub fn mk_uniq<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> { mk_t(cx, ty_uniq(ty)) }
3129 pub fn mk_ptr<'tcx>(cx: &ctxt<'tcx>, tm: mt<'tcx>) -> Ty<'tcx> { mk_t(cx, ty_ptr(tm)) }
3131 pub fn mk_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, tm: mt<'tcx>) -> Ty<'tcx> {
3132 mk_t(cx, ty_rptr(r, tm))
3135 pub fn mk_mut_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
3136 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutMutable})
3138 pub fn mk_imm_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
3139 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutImmutable})
3142 pub fn mk_mut_ptr<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3143 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutMutable})
3146 pub fn mk_imm_ptr<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3147 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutImmutable})
3150 pub fn mk_nil_ptr<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3151 mk_ptr(cx, mt {ty: mk_nil(cx), mutbl: ast::MutImmutable})
3154 pub fn mk_vec<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>, sz: Option<usize>) -> Ty<'tcx> {
3155 mk_t(cx, ty_vec(ty, sz))
3158 pub fn mk_slice<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, tm: mt<'tcx>) -> Ty<'tcx> {
3161 ty: mk_vec(cx, tm.ty, None),
3166 pub fn mk_tup<'tcx>(cx: &ctxt<'tcx>, ts: Vec<Ty<'tcx>>) -> Ty<'tcx> {
3167 mk_t(cx, ty_tup(ts))
3170 pub fn mk_nil<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3171 mk_tup(cx, Vec::new())
3174 pub fn mk_bool<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3178 pub fn mk_bare_fn<'tcx>(cx: &ctxt<'tcx>,
3179 opt_def_id: Option<ast::DefId>,
3180 fty: &'tcx BareFnTy<'tcx>) -> Ty<'tcx> {
3181 mk_t(cx, ty_bare_fn(opt_def_id, fty))
3184 pub fn mk_ctor_fn<'tcx>(cx: &ctxt<'tcx>,
3186 input_tys: &[Ty<'tcx>],
3187 output: Ty<'tcx>) -> Ty<'tcx> {
3188 let input_args = input_tys.iter().cloned().collect();
3191 cx.mk_bare_fn(BareFnTy {
3192 unsafety: ast::Unsafety::Normal,
3194 sig: ty::Binder(FnSig {
3196 output: ty::FnConverging(output),
3202 pub fn mk_trait<'tcx>(cx: &ctxt<'tcx>,
3203 principal: ty::PolyTraitRef<'tcx>,
3204 bounds: ExistentialBounds<'tcx>)
3207 assert!(bound_list_is_sorted(&bounds.projection_bounds));
3209 let inner = box TyTrait {
3210 principal: principal,
3213 mk_t(cx, ty_trait(inner))
3216 fn bound_list_is_sorted(bounds: &[ty::PolyProjectionPredicate]) -> bool {
3217 bounds.is_empty() ||
3218 bounds[1..].iter().enumerate().all(
3219 |(index, bound)| bounds[index].sort_key() <= bound.sort_key())
3222 pub fn sort_bounds_list(bounds: &mut [ty::PolyProjectionPredicate]) {
3223 bounds.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()))
3226 pub fn mk_projection<'tcx>(cx: &ctxt<'tcx>,
3227 trait_ref: TraitRef<'tcx>,
3228 item_name: ast::Name)
3230 // take a copy of substs so that we own the vectors inside
3231 let inner = ProjectionTy { trait_ref: trait_ref, item_name: item_name };
3232 mk_t(cx, ty_projection(inner))
3235 pub fn mk_struct<'tcx>(cx: &ctxt<'tcx>, struct_id: ast::DefId,
3236 substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
3237 // take a copy of substs so that we own the vectors inside
3238 mk_t(cx, ty_struct(struct_id, substs))
3241 pub fn mk_closure<'tcx>(cx: &ctxt<'tcx>, closure_id: ast::DefId, substs: &'tcx Substs<'tcx>)
3243 mk_t(cx, ty_closure(closure_id, substs))
3246 pub fn mk_var<'tcx>(cx: &ctxt<'tcx>, v: TyVid) -> Ty<'tcx> {
3247 mk_infer(cx, TyVar(v))
3250 pub fn mk_int_var<'tcx>(cx: &ctxt<'tcx>, v: IntVid) -> Ty<'tcx> {
3251 mk_infer(cx, IntVar(v))
3254 pub fn mk_float_var<'tcx>(cx: &ctxt<'tcx>, v: FloatVid) -> Ty<'tcx> {
3255 mk_infer(cx, FloatVar(v))
3258 pub fn mk_infer<'tcx>(cx: &ctxt<'tcx>, it: InferTy) -> Ty<'tcx> {
3259 mk_t(cx, ty_infer(it))
3262 pub fn mk_param<'tcx>(cx: &ctxt<'tcx>,
3263 space: subst::ParamSpace,
3265 name: ast::Name) -> Ty<'tcx> {
3266 mk_t(cx, ty_param(ParamTy { space: space, idx: index, name: name }))
3269 pub fn mk_self_type<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3270 mk_param(cx, subst::SelfSpace, 0, special_idents::type_self.name)
3273 pub fn mk_param_from_def<'tcx>(cx: &ctxt<'tcx>, def: &TypeParameterDef) -> Ty<'tcx> {
3274 mk_param(cx, def.space, def.index, def.name)
3277 impl<'tcx> TyS<'tcx> {
3278 /// Iterator that walks `self` and any types reachable from
3279 /// `self`, in depth-first order. Note that just walks the types
3280 /// that appear in `self`, it does not descend into the fields of
3281 /// structs or variants. For example:
3284 /// isize => { isize }
3285 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
3286 /// [isize] => { [isize], isize }
3288 pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
3289 TypeWalker::new(self)
3292 /// Iterator that walks the immediate children of `self`. Hence
3293 /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
3294 /// (but not `i32`, like `walk`).
3295 pub fn walk_shallow(&'tcx self) -> IntoIter<Ty<'tcx>> {
3296 ty_walk::walk_shallow(self)
3299 pub fn as_opt_param_ty(&self) -> Option<ty::ParamTy> {
3301 ty::ty_param(ref d) => Some(d.clone()),
3306 pub fn is_param(&self, space: ParamSpace, index: u32) -> bool {
3308 ty::ty_param(ref data) => data.space == space && data.idx == index,
3314 pub fn walk_ty<'tcx, F>(ty_root: Ty<'tcx>, mut f: F)
3315 where F: FnMut(Ty<'tcx>),
3317 for ty in ty_root.walk() {
3322 /// Walks `ty` and any types appearing within `ty`, invoking the
3323 /// callback `f` on each type. If the callback returns false, then the
3324 /// children of the current type are ignored.
3326 /// Note: prefer `ty.walk()` where possible.
3327 pub fn maybe_walk_ty<'tcx,F>(ty_root: Ty<'tcx>, mut f: F)
3328 where F : FnMut(Ty<'tcx>) -> bool
3330 let mut walker = ty_root.walk();
3331 while let Some(ty) = walker.next() {
3333 walker.skip_current_subtree();
3338 // Folds types from the bottom up.
3339 pub fn fold_ty<'tcx, F>(cx: &ctxt<'tcx>, t0: Ty<'tcx>,
3342 F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
3344 let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
3349 pub fn new(space: subst::ParamSpace,
3353 ParamTy { space: space, idx: index, name: name }
3356 pub fn for_self() -> ParamTy {
3357 ParamTy::new(subst::SelfSpace, 0, special_idents::type_self.name)
3360 pub fn for_def(def: &TypeParameterDef) -> ParamTy {
3361 ParamTy::new(def.space, def.index, def.name)
3364 pub fn to_ty<'tcx>(self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
3365 ty::mk_param(tcx, self.space, self.idx, self.name)
3368 pub fn is_self(&self) -> bool {
3369 self.space == subst::SelfSpace && self.idx == 0
3373 impl<'tcx> ItemSubsts<'tcx> {
3374 pub fn empty() -> ItemSubsts<'tcx> {
3375 ItemSubsts { substs: Substs::empty() }
3378 pub fn is_noop(&self) -> bool {
3379 self.substs.is_noop()
3383 impl<'tcx> ParamBounds<'tcx> {
3384 pub fn empty() -> ParamBounds<'tcx> {
3386 builtin_bounds: empty_builtin_bounds(),
3387 trait_bounds: Vec::new(),
3388 region_bounds: Vec::new(),
3389 projection_bounds: Vec::new(),
3396 pub fn type_is_nil(ty: Ty) -> bool {
3398 ty_tup(ref tys) => tys.is_empty(),
3403 pub fn type_is_error(ty: Ty) -> bool {
3404 ty.flags.get().intersects(TypeFlags::HAS_TY_ERR)
3407 pub fn type_needs_subst(ty: Ty) -> bool {
3408 ty.flags.get().intersects(TypeFlags::NEEDS_SUBST)
3411 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
3412 tref.substs.types.any(|&ty| type_is_error(ty))
3415 pub fn type_is_ty_var(ty: Ty) -> bool {
3417 ty_infer(TyVar(_)) => true,
3422 pub fn type_is_bool(ty: Ty) -> bool { ty.sty == ty_bool }
3424 pub fn type_is_self(ty: Ty) -> bool {
3426 ty_param(ref p) => p.space == subst::SelfSpace,
3431 fn type_is_slice(ty: Ty) -> bool {
3433 ty_ptr(mt) | ty_rptr(_, mt) => match mt.ty.sty {
3434 ty_vec(_, None) | ty_str => true,
3441 pub fn type_is_vec(ty: Ty) -> bool {
3444 ty_ptr(mt{ty, ..}) | ty_rptr(_, mt{ty, ..}) |
3445 ty_uniq(ty) => match ty.sty {
3446 ty_vec(_, None) => true,
3453 pub fn type_is_structural(ty: Ty) -> bool {
3455 ty_struct(..) | ty_tup(_) | ty_enum(..) |
3456 ty_vec(_, Some(_)) | ty_closure(..) => true,
3457 _ => type_is_slice(ty) | type_is_trait(ty)
3461 pub fn type_is_simd(cx: &ctxt, ty: Ty) -> bool {
3463 ty_struct(did, _) => lookup_simd(cx, did),
3468 pub fn sequence_element_type<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3470 ty_vec(ty, _) => ty,
3471 ty_str => mk_mach_uint(cx, ast::TyU8),
3472 _ => cx.sess.bug(&format!("sequence_element_type called on non-sequence value: {}",
3473 ty_to_string(cx, ty))),
3477 pub fn simd_type<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3479 ty_struct(did, substs) => {
3480 let fields = lookup_struct_fields(cx, did);
3481 lookup_field_type(cx, did, fields[0].id, substs)
3483 _ => panic!("simd_type called on invalid type")
3487 pub fn simd_size(cx: &ctxt, ty: Ty) -> usize {
3489 ty_struct(did, _) => {
3490 let fields = lookup_struct_fields(cx, did);
3493 _ => panic!("simd_size called on invalid type")
3497 pub fn type_is_region_ptr(ty: Ty) -> bool {
3499 ty_rptr(..) => true,
3504 pub fn type_is_unsafe_ptr(ty: Ty) -> bool {
3506 ty_ptr(_) => return true,
3511 pub fn type_is_unique(ty: Ty) -> bool {
3519 A scalar type is one that denotes an atomic datum, with no sub-components.
3520 (A ty_ptr is scalar because it represents a non-managed pointer, so its
3521 contents are abstract to rustc.)
3523 pub fn type_is_scalar(ty: Ty) -> bool {
3525 ty_bool | ty_char | ty_int(_) | ty_float(_) | ty_uint(_) |
3526 ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) |
3527 ty_bare_fn(..) | ty_ptr(_) => true,
3532 /// Returns true if this type is a floating point type and false otherwise.
3533 pub fn type_is_floating_point(ty: Ty) -> bool {
3536 ty_infer(FloatVar(_)) =>
3544 /// Type contents is how the type checker reasons about kinds.
3545 /// They track what kinds of things are found within a type. You can
3546 /// think of them as kind of an "anti-kind". They track the kinds of values
3547 /// and thinks that are contained in types. Having a larger contents for
3548 /// a type tends to rule that type *out* from various kinds. For example,
3549 /// a type that contains a reference is not sendable.
3551 /// The reason we compute type contents and not kinds is that it is
3552 /// easier for me (nmatsakis) to think about what is contained within
3553 /// a type than to think about what is *not* contained within a type.
3554 #[derive(Clone, Copy)]
3555 pub struct TypeContents {
3559 macro_rules! def_type_content_sets {
3560 (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
3561 #[allow(non_snake_case)]
3563 use middle::ty::TypeContents;
3565 #[allow(non_upper_case_globals)]
3566 pub const $name: TypeContents = TypeContents { bits: $bits };
3572 def_type_content_sets! {
3574 None = 0b0000_0000__0000_0000__0000,
3576 // Things that are interior to the value (first nibble):
3577 InteriorUnsized = 0b0000_0000__0000_0000__0001,
3578 InteriorUnsafe = 0b0000_0000__0000_0000__0010,
3579 InteriorParam = 0b0000_0000__0000_0000__0100,
3580 // InteriorAll = 0b00000000__00000000__1111,
3582 // Things that are owned by the value (second and third nibbles):
3583 OwnsOwned = 0b0000_0000__0000_0001__0000,
3584 OwnsDtor = 0b0000_0000__0000_0010__0000,
3585 OwnsAll = 0b0000_0000__1111_1111__0000,
3587 // Things that are reachable by the value in any way (fourth nibble):
3588 ReachesBorrowed = 0b0000_0010__0000_0000__0000,
3589 ReachesMutable = 0b0000_1000__0000_0000__0000,
3590 ReachesFfiUnsafe = 0b0010_0000__0000_0000__0000,
3591 ReachesAll = 0b0011_1111__0000_0000__0000,
3593 // Things that mean drop glue is necessary
3594 NeedsDrop = 0b0000_0000__0000_0111__0000,
3596 // Things that prevent values from being considered sized
3597 Nonsized = 0b0000_0000__0000_0000__0001,
3600 All = 0b1111_1111__1111_1111__1111
3605 pub fn when(&self, cond: bool) -> TypeContents {
3606 if cond {*self} else {TC::None}
3609 pub fn intersects(&self, tc: TypeContents) -> bool {
3610 (self.bits & tc.bits) != 0
3613 pub fn owns_owned(&self) -> bool {
3614 self.intersects(TC::OwnsOwned)
3617 pub fn is_sized(&self, _: &ctxt) -> bool {
3618 !self.intersects(TC::Nonsized)
3621 pub fn interior_param(&self) -> bool {
3622 self.intersects(TC::InteriorParam)
3625 pub fn interior_unsafe(&self) -> bool {
3626 self.intersects(TC::InteriorUnsafe)
3629 pub fn interior_unsized(&self) -> bool {
3630 self.intersects(TC::InteriorUnsized)
3633 pub fn needs_drop(&self, _: &ctxt) -> bool {
3634 self.intersects(TC::NeedsDrop)
3637 /// Includes only those bits that still apply when indirected through a `Box` pointer
3638 pub fn owned_pointer(&self) -> TypeContents {
3640 *self & (TC::OwnsAll | TC::ReachesAll))
3643 /// Includes only those bits that still apply when indirected through a reference (`&`)
3644 pub fn reference(&self, bits: TypeContents) -> TypeContents {
3646 *self & TC::ReachesAll)
3649 /// Includes only those bits that still apply when indirected through an unsafe pointer (`*`)
3650 pub fn unsafe_pointer(&self) -> TypeContents {
3651 *self & TC::ReachesAll
3654 pub fn union<T, F>(v: &[T], mut f: F) -> TypeContents where
3655 F: FnMut(&T) -> TypeContents,
3657 v.iter().fold(TC::None, |tc, ty| tc | f(ty))
3660 pub fn has_dtor(&self) -> bool {
3661 self.intersects(TC::OwnsDtor)
3665 impl ops::BitOr for TypeContents {
3666 type Output = TypeContents;
3668 fn bitor(self, other: TypeContents) -> TypeContents {
3669 TypeContents {bits: self.bits | other.bits}
3673 impl ops::BitAnd for TypeContents {
3674 type Output = TypeContents;
3676 fn bitand(self, other: TypeContents) -> TypeContents {
3677 TypeContents {bits: self.bits & other.bits}
3681 impl ops::Sub for TypeContents {
3682 type Output = TypeContents;
3684 fn sub(self, other: TypeContents) -> TypeContents {
3685 TypeContents {bits: self.bits & !other.bits}
3689 impl fmt::Debug for TypeContents {
3690 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3691 write!(f, "TypeContents({:b})", self.bits)
3695 pub fn type_interior_is_unsafe<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
3696 type_contents(cx, ty).interior_unsafe()
3699 pub fn type_contents<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> TypeContents {
3700 return memoized(&cx.tc_cache, ty, |ty| {
3701 tc_ty(cx, ty, &mut FnvHashMap())
3704 fn tc_ty<'tcx>(cx: &ctxt<'tcx>,
3706 cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
3708 // Subtle: Note that we are *not* using cx.tc_cache here but rather a
3709 // private cache for this walk. This is needed in the case of cyclic
3712 // struct List { next: Box<Option<List>>, ... }
3714 // When computing the type contents of such a type, we wind up deeply
3715 // recursing as we go. So when we encounter the recursive reference
3716 // to List, we temporarily use TC::None as its contents. Later we'll
3717 // patch up the cache with the correct value, once we've computed it
3718 // (this is basically a co-inductive process, if that helps). So in
3719 // the end we'll compute TC::OwnsOwned, in this case.
3721 // The problem is, as we are doing the computation, we will also
3722 // compute an *intermediate* contents for, e.g., Option<List> of
3723 // TC::None. This is ok during the computation of List itself, but if
3724 // we stored this intermediate value into cx.tc_cache, then later
3725 // requests for the contents of Option<List> would also yield TC::None
3726 // which is incorrect. This value was computed based on the crutch
3727 // value for the type contents of list. The correct value is
3728 // TC::OwnsOwned. This manifested as issue #4821.
3729 match cache.get(&ty) {
3730 Some(tc) => { return *tc; }
3733 match cx.tc_cache.borrow().get(&ty) { // Must check both caches!
3734 Some(tc) => { return *tc; }
3737 cache.insert(ty, TC::None);
3739 let result = match ty.sty {
3740 // usize and isize are ffi-unsafe
3741 ty_uint(ast::TyUs) | ty_int(ast::TyIs) => {
3742 TC::ReachesFfiUnsafe
3745 // Scalar and unique types are sendable, and durable
3746 ty_infer(ty::FreshIntTy(_)) | ty_infer(ty::FreshFloatTy(_)) |
3747 ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
3748 ty_bare_fn(..) | ty::ty_char => {
3753 TC::ReachesFfiUnsafe | match typ.sty {
3754 ty_str => TC::OwnsOwned,
3755 _ => tc_ty(cx, typ, cache).owned_pointer(),
3759 ty_trait(box TyTrait { ref bounds, .. }) => {
3760 object_contents(bounds) | TC::ReachesFfiUnsafe | TC::Nonsized
3764 tc_ty(cx, mt.ty, cache).unsafe_pointer()
3767 ty_rptr(r, ref mt) => {
3768 TC::ReachesFfiUnsafe | match mt.ty.sty {
3769 ty_str => borrowed_contents(*r, ast::MutImmutable),
3770 ty_vec(..) => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(*r,
3772 _ => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(*r, mt.mutbl)),
3776 ty_vec(ty, Some(_)) => {
3777 tc_ty(cx, ty, cache)
3780 ty_vec(ty, None) => {
3781 tc_ty(cx, ty, cache) | TC::Nonsized
3783 ty_str => TC::Nonsized,
3785 ty_struct(did, substs) => {
3786 let flds = struct_fields(cx, did, substs);
3788 TypeContents::union(&flds[..],
3789 |f| tc_mt(cx, f.mt, cache));
3791 if !lookup_repr_hints(cx, did).contains(&attr::ReprExtern) {
3792 res = res | TC::ReachesFfiUnsafe;
3795 if ty::has_dtor(cx, did) {
3796 res = res | TC::OwnsDtor;
3798 apply_lang_items(cx, did, res)
3801 ty_closure(did, substs) => {
3802 // FIXME(#14449): `borrowed_contents` below assumes `&mut` closure.
3803 let param_env = ty::empty_parameter_environment(cx);
3804 let upvars = closure_upvars(¶m_env, did, substs).unwrap();
3805 TypeContents::union(&upvars, |f| tc_ty(cx, &f.ty, cache))
3808 ty_tup(ref tys) => {
3809 TypeContents::union(&tys[..],
3810 |ty| tc_ty(cx, *ty, cache))
3813 ty_enum(did, substs) => {
3814 let variants = substd_enum_variants(cx, did, substs);
3816 TypeContents::union(&variants[..], |variant| {
3817 TypeContents::union(&variant.args,
3819 tc_ty(cx, *arg_ty, cache)
3823 if ty::has_dtor(cx, did) {
3824 res = res | TC::OwnsDtor;
3827 if !variants.is_empty() {
3828 let repr_hints = lookup_repr_hints(cx, did);
3829 if repr_hints.len() > 1 {
3830 // this is an error later on, but this type isn't safe
3831 res = res | TC::ReachesFfiUnsafe;
3834 match repr_hints.get(0) {
3835 Some(h) => if !h.is_ffi_safe() {
3836 res = res | TC::ReachesFfiUnsafe;
3840 res = res | TC::ReachesFfiUnsafe;
3842 // We allow ReprAny enums if they are eligible for
3843 // the nullable pointer optimization and the
3844 // contained type is an `extern fn`
3846 if variants.len() == 2 {
3847 let mut data_idx = 0;
3849 if variants[0].args.is_empty() {
3853 if variants[data_idx].args.len() == 1 {
3854 match variants[data_idx].args[0].sty {
3855 ty_bare_fn(..) => { res = res - TC::ReachesFfiUnsafe; }
3865 apply_lang_items(cx, did, res)
3875 cx.sess.bug("asked to compute contents of error type");
3879 cache.insert(ty, result);
3883 fn tc_mt<'tcx>(cx: &ctxt<'tcx>,
3885 cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
3887 let mc = TC::ReachesMutable.when(mt.mutbl == MutMutable);
3888 mc | tc_ty(cx, mt.ty, cache)
3891 fn apply_lang_items(cx: &ctxt, did: ast::DefId, tc: TypeContents)
3893 if Some(did) == cx.lang_items.unsafe_cell_type() {
3894 tc | TC::InteriorUnsafe
3900 /// Type contents due to containing a reference with the region `region` and borrow kind `bk`
3901 fn borrowed_contents(region: ty::Region,
3902 mutbl: ast::Mutability)
3904 let b = match mutbl {
3905 ast::MutMutable => TC::ReachesMutable,
3906 ast::MutImmutable => TC::None,
3908 b | (TC::ReachesBorrowed).when(region != ty::ReStatic)
3911 fn object_contents(bounds: &ExistentialBounds) -> TypeContents {
3912 // These are the type contents of the (opaque) interior. We
3913 // make no assumptions (other than that it cannot have an
3914 // in-scope type parameter within, which makes no sense).
3915 let mut tc = TC::All - TC::InteriorParam;
3916 for bound in &bounds.builtin_bounds {
3917 tc = tc - match bound {
3918 BoundSync | BoundSend | BoundCopy => TC::None,
3919 BoundSized => TC::Nonsized,
3926 fn type_impls_bound<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
3927 tcx: &ty::ctxt<'tcx>,
3929 bound: ty::BuiltinBound,
3934 let param_env = match param_env {
3937 pe = empty_parameter_environment(tcx);
3941 let infcx = infer::new_infer_ctxt(tcx);
3943 let is_impld = traits::type_known_to_meet_builtin_bound(&infcx, param_env, ty, bound, span);
3945 debug!("type_impls_bound({}, {:?}) = {:?}",
3953 pub fn type_moves_by_default<'a,'tcx>(param_env: &ParameterEnvironment<'a,'tcx>,
3958 if ty.flags.get().intersects(TypeFlags::MOVENESS_CACHED) {
3959 return ty.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT);
3962 assert!(!ty::type_needs_infer(ty));
3964 // Fast-path for primitive types
3965 let result = match ty.sty {
3966 ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
3967 ty_ptr(..) | ty_bare_fn(..) | ty_rptr(_, mt {
3968 mutbl: ast::MutImmutable, ..
3971 ty_str | ty_uniq(..) | ty_rptr(_, mt {
3972 mutbl: ast::MutMutable, ..
3975 ty_vec(..) | ty_trait(..) | ty_tup(..) |
3976 ty_closure(..) | ty_enum(..) | ty_struct(..) |
3977 ty_projection(..) | ty_param(..) | ty_infer(..) | ty_err => None
3978 }.unwrap_or_else(|| !type_impls_bound(Some(param_env),
3984 if !type_has_params(ty) && !type_has_self(ty) {
3985 ty.flags.set(ty.flags.get() | if result {
3986 TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT
3988 TypeFlags::MOVENESS_CACHED
3996 pub fn type_is_sized<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
3997 tcx: &ty::ctxt<'tcx>,
4002 if ty.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) {
4003 let result = ty.flags.get().intersects(TypeFlags::IS_SIZED);
4007 type_is_sized_uncached(param_env, tcx, span, ty)
4010 fn type_is_sized_uncached<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
4011 tcx: &ty::ctxt<'tcx>,
4013 ty: Ty<'tcx>) -> bool {
4014 assert!(!ty::type_needs_infer(ty));
4016 // Fast-path for primitive types
4017 let result = match ty.sty {
4018 ty_bool | ty_char | ty_int(..) | ty_uint(..) | ty_float(..) |
4019 ty_uniq(..) | ty_ptr(..) | ty_rptr(..) | ty_bare_fn(..) |
4020 ty_vec(_, Some(..)) | ty_tup(..) | ty_closure(..) => Some(true),
4022 ty_str | ty_trait(..) | ty_vec(_, None) => Some(false),
4024 ty_enum(..) | ty_struct(..) | ty_projection(..) | ty_param(..) |
4025 ty_infer(..) | ty_err => None
4026 }.unwrap_or_else(|| type_impls_bound(param_env, tcx, ty, ty::BoundSized, span));
4028 if !type_has_params(ty) && !type_has_self(ty) {
4029 ty.flags.set(ty.flags.get() | if result {
4030 TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED
4032 TypeFlags::SIZEDNESS_CACHED
4039 pub fn is_ffi_safe<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
4040 !type_contents(cx, ty).intersects(TC::ReachesFfiUnsafe)
4043 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
4044 pub fn is_instantiable<'tcx>(cx: &ctxt<'tcx>, r_ty: Ty<'tcx>) -> bool {
4045 fn type_requires<'tcx>(cx: &ctxt<'tcx>, seen: &mut Vec<DefId>,
4046 r_ty: Ty<'tcx>, ty: Ty<'tcx>) -> bool {
4047 debug!("type_requires({:?}, {:?})?",
4048 ::util::ppaux::ty_to_string(cx, r_ty),
4049 ::util::ppaux::ty_to_string(cx, ty));
4051 let r = r_ty == ty || subtypes_require(cx, seen, r_ty, ty);
4053 debug!("type_requires({:?}, {:?})? {:?}",
4054 ::util::ppaux::ty_to_string(cx, r_ty),
4055 ::util::ppaux::ty_to_string(cx, ty),
4060 fn subtypes_require<'tcx>(cx: &ctxt<'tcx>, seen: &mut Vec<DefId>,
4061 r_ty: Ty<'tcx>, ty: Ty<'tcx>) -> bool {
4062 debug!("subtypes_require({:?}, {:?})?",
4063 ::util::ppaux::ty_to_string(cx, r_ty),
4064 ::util::ppaux::ty_to_string(cx, ty));
4066 let r = match ty.sty {
4067 // fixed length vectors need special treatment compared to
4068 // normal vectors, since they don't necessarily have the
4069 // possibility to have length zero.
4070 ty_vec(_, Some(0)) => false, // don't need no contents
4071 ty_vec(ty, Some(_)) => type_requires(cx, seen, r_ty, ty),
4082 ty_vec(_, None) => {
4086 type_requires(cx, seen, r_ty, typ)
4088 ty_rptr(_, ref mt) => {
4089 type_requires(cx, seen, r_ty, mt.ty)
4093 false // unsafe ptrs can always be NULL
4100 ty_struct(ref did, _) if seen.contains(did) => {
4104 ty_struct(did, substs) => {
4106 let fields = struct_fields(cx, did, substs);
4107 let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
4108 seen.pop().unwrap();
4115 // this check is run on type definitions, so we don't expect to see
4116 // inference by-products or closure types
4117 cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
4121 ts.iter().any(|ty| type_requires(cx, seen, r_ty, *ty))
4124 ty_enum(ref did, _) if seen.contains(did) => {
4128 ty_enum(did, substs) => {
4130 let vs = enum_variants(cx, did);
4131 let r = !vs.is_empty() && vs.iter().all(|variant| {
4132 variant.args.iter().any(|aty| {
4133 let sty = aty.subst(cx, substs);
4134 type_requires(cx, seen, r_ty, sty)
4137 seen.pop().unwrap();
4142 debug!("subtypes_require({:?}, {:?})? {:?}",
4143 ::util::ppaux::ty_to_string(cx, r_ty),
4144 ::util::ppaux::ty_to_string(cx, ty),
4150 let mut seen = Vec::new();
4151 !subtypes_require(cx, &mut seen, r_ty, r_ty)
4154 /// Describes whether a type is representable. For types that are not
4155 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
4156 /// distinguish between types that are recursive with themselves and types that
4157 /// contain a different recursive type. These cases can therefore be treated
4158 /// differently when reporting errors.
4160 /// The ordering of the cases is significant. They are sorted so that cmp::max
4161 /// will keep the "more erroneous" of two values.
4162 #[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
4163 pub enum Representability {
4169 /// Check whether a type is representable. This means it cannot contain unboxed
4170 /// structural recursion. This check is needed for structs and enums.
4171 pub fn is_type_representable<'tcx>(cx: &ctxt<'tcx>, sp: Span, ty: Ty<'tcx>)
4172 -> Representability {
4174 // Iterate until something non-representable is found
4175 fn find_nonrepresentable<'tcx, It: Iterator<Item=Ty<'tcx>>>(cx: &ctxt<'tcx>, sp: Span,
4176 seen: &mut Vec<Ty<'tcx>>,
4178 -> Representability {
4179 iter.fold(Representable,
4180 |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
4183 fn are_inner_types_recursive<'tcx>(cx: &ctxt<'tcx>, sp: Span,
4184 seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>)
4185 -> Representability {
4188 find_nonrepresentable(cx, sp, seen, ts.iter().cloned())
4190 // Fixed-length vectors.
4191 // FIXME(#11924) Behavior undecided for zero-length vectors.
4192 ty_vec(ty, Some(_)) => {
4193 is_type_structurally_recursive(cx, sp, seen, ty)
4195 ty_struct(did, substs) => {
4196 let fields = struct_fields(cx, did, substs);
4197 find_nonrepresentable(cx, sp, seen, fields.iter().map(|f| f.mt.ty))
4199 ty_enum(did, substs) => {
4200 let vs = enum_variants(cx, did);
4201 let iter = vs.iter()
4202 .flat_map(|variant| { variant.args.iter() })
4203 .map(|aty| { aty.subst_spanned(cx, substs, Some(sp)) });
4205 find_nonrepresentable(cx, sp, seen, iter)
4208 // this check is run on type definitions, so we don't expect
4209 // to see closure types
4210 cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
4216 fn same_struct_or_enum_def_id(ty: Ty, did: DefId) -> bool {
4218 ty_struct(ty_did, _) | ty_enum(ty_did, _) => {
4225 fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
4226 match (&a.sty, &b.sty) {
4227 (&ty_struct(did_a, ref substs_a), &ty_struct(did_b, ref substs_b)) |
4228 (&ty_enum(did_a, ref substs_a), &ty_enum(did_b, ref substs_b)) => {
4233 let types_a = substs_a.types.get_slice(subst::TypeSpace);
4234 let types_b = substs_b.types.get_slice(subst::TypeSpace);
4236 let mut pairs = types_a.iter().zip(types_b.iter());
4238 pairs.all(|(&a, &b)| same_type(a, b))
4246 // Does the type `ty` directly (without indirection through a pointer)
4247 // contain any types on stack `seen`?
4248 fn is_type_structurally_recursive<'tcx>(cx: &ctxt<'tcx>, sp: Span,
4249 seen: &mut Vec<Ty<'tcx>>,
4250 ty: Ty<'tcx>) -> Representability {
4251 debug!("is_type_structurally_recursive: {:?}",
4252 ::util::ppaux::ty_to_string(cx, ty));
4255 ty_struct(did, _) | ty_enum(did, _) => {
4257 // Iterate through stack of previously seen types.
4258 let mut iter = seen.iter();
4260 // The first item in `seen` is the type we are actually curious about.
4261 // We want to return SelfRecursive if this type contains itself.
4262 // It is important that we DON'T take generic parameters into account
4263 // for this check, so that Bar<T> in this example counts as SelfRecursive:
4266 // struct Bar<T> { x: Bar<Foo> }
4269 Some(&seen_type) => {
4270 if same_struct_or_enum_def_id(seen_type, did) {
4271 debug!("SelfRecursive: {:?} contains {:?}",
4272 ::util::ppaux::ty_to_string(cx, seen_type),
4273 ::util::ppaux::ty_to_string(cx, ty));
4274 return SelfRecursive;
4280 // We also need to know whether the first item contains other types that
4281 // are structurally recursive. If we don't catch this case, we will recurse
4282 // infinitely for some inputs.
4284 // It is important that we DO take generic parameters into account here,
4285 // so that code like this is considered SelfRecursive, not ContainsRecursive:
4287 // struct Foo { Option<Option<Foo>> }
4289 for &seen_type in iter {
4290 if same_type(ty, seen_type) {
4291 debug!("ContainsRecursive: {:?} contains {:?}",
4292 ::util::ppaux::ty_to_string(cx, seen_type),
4293 ::util::ppaux::ty_to_string(cx, ty));
4294 return ContainsRecursive;
4299 // For structs and enums, track all previously seen types by pushing them
4300 // onto the 'seen' stack.
4302 let out = are_inner_types_recursive(cx, sp, seen, ty);
4307 // No need to push in other cases.
4308 are_inner_types_recursive(cx, sp, seen, ty)
4313 debug!("is_type_representable: {:?}",
4314 ::util::ppaux::ty_to_string(cx, ty));
4316 // To avoid a stack overflow when checking an enum variant or struct that
4317 // contains a different, structurally recursive type, maintain a stack
4318 // of seen types and check recursion for each of them (issues #3008, #3779).
4319 let mut seen: Vec<Ty> = Vec::new();
4320 let r = is_type_structurally_recursive(cx, sp, &mut seen, ty);
4321 debug!("is_type_representable: {:?} is {:?}",
4322 ::util::ppaux::ty_to_string(cx, ty), r);
4326 pub fn type_is_trait(ty: Ty) -> bool {
4328 ty_trait(..) => true,
4333 pub fn type_is_integral(ty: Ty) -> bool {
4335 ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
4340 pub fn type_is_fresh(ty: Ty) -> bool {
4342 ty_infer(FreshTy(_)) => true,
4343 ty_infer(FreshIntTy(_)) => true,
4344 ty_infer(FreshFloatTy(_)) => true,
4349 pub fn type_is_uint(ty: Ty) -> bool {
4351 ty_infer(IntVar(_)) | ty_uint(ast::TyUs) => true,
4356 pub fn type_is_char(ty: Ty) -> bool {
4363 pub fn type_is_bare_fn(ty: Ty) -> bool {
4365 ty_bare_fn(..) => true,
4370 pub fn type_is_bare_fn_item(ty: Ty) -> bool {
4372 ty_bare_fn(Some(_), _) => true,
4377 pub fn type_is_fp(ty: Ty) -> bool {
4379 ty_infer(FloatVar(_)) | ty_float(_) => true,
4384 pub fn type_is_numeric(ty: Ty) -> bool {
4385 return type_is_integral(ty) || type_is_fp(ty);
4388 pub fn type_is_signed(ty: Ty) -> bool {
4395 pub fn type_is_machine(ty: Ty) -> bool {
4397 ty_int(ast::TyIs) | ty_uint(ast::TyUs) => false,
4398 ty_int(..) | ty_uint(..) | ty_float(..) => true,
4403 // Whether a type is enum like, that is an enum type with only nullary
4405 pub fn type_is_c_like_enum(cx: &ctxt, ty: Ty) -> bool {
4407 ty_enum(did, _) => {
4408 let variants = enum_variants(cx, did);
4409 if variants.is_empty() {
4412 variants.iter().all(|v| v.args.is_empty())
4419 // Returns the type and mutability of *ty.
4421 // The parameter `explicit` indicates if this is an *explicit* dereference.
4422 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
4423 pub fn deref<'tcx>(ty: Ty<'tcx>, explicit: bool) -> Option<mt<'tcx>> {
4428 mutbl: ast::MutImmutable,
4431 ty_rptr(_, mt) => Some(mt),
4432 ty_ptr(mt) if explicit => Some(mt),
4437 pub fn type_content<'tcx>(ty: Ty<'tcx>) -> Ty<'tcx> {
4440 ty_rptr(_, mt) | ty_ptr(mt) => mt.ty,
4445 // Returns the type of ty[i]
4446 pub fn index<'tcx>(ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
4448 ty_vec(ty, _) => Some(ty),
4453 // Returns the type of elements contained within an 'array-like' type.
4454 // This is exactly the same as the above, except it supports strings,
4455 // which can't actually be indexed.
4456 pub fn array_element_ty<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
4458 ty_vec(ty, _) => Some(ty),
4459 ty_str => Some(tcx.types.u8),
4464 /// Returns the type of element at index `i` in tuple or tuple-like type `t`.
4465 /// For an enum `t`, `variant` is None only if `t` is a univariant enum.
4466 pub fn positional_element_ty<'tcx>(cx: &ctxt<'tcx>,
4469 variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
4471 match (&ty.sty, variant) {
4472 (&ty_tup(ref v), None) => v.get(i).cloned(),
4475 (&ty_struct(def_id, substs), None) => lookup_struct_fields(cx, def_id)
4477 .map(|&t|lookup_item_type(cx, t.id).ty.subst(cx, substs)),
4479 (&ty_enum(def_id, substs), Some(variant_def_id)) => {
4480 let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
4481 variant_info.args.get(i).map(|t|t.subst(cx, substs))
4484 (&ty_enum(def_id, substs), None) => {
4485 assert!(enum_is_univariant(cx, def_id));
4486 let enum_variants = enum_variants(cx, def_id);
4487 let variant_info = &(*enum_variants)[0];
4488 variant_info.args.get(i).map(|t|t.subst(cx, substs))
4495 /// Returns the type of element at field `n` in struct or struct-like type `t`.
4496 /// For an enum `t`, `variant` must be some def id.
4497 pub fn named_element_ty<'tcx>(cx: &ctxt<'tcx>,
4500 variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
4502 match (&ty.sty, variant) {
4503 (&ty_struct(def_id, substs), None) => {
4504 let r = lookup_struct_fields(cx, def_id);
4505 r.iter().find(|f| f.name == n)
4506 .map(|&f| lookup_field_type(cx, def_id, f.id, substs))
4508 (&ty_enum(def_id, substs), Some(variant_def_id)) => {
4509 let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
4510 variant_info.arg_names.as_ref()
4511 .expect("must have struct enum variant if accessing a named fields")
4512 .iter().zip(variant_info.args.iter())
4513 .find(|&(&name, _)| name == n)
4514 .map(|(_name, arg_t)| arg_t.subst(cx, substs))
4520 pub fn node_id_to_type<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> Ty<'tcx> {
4521 match node_id_to_type_opt(cx, id) {
4523 None => cx.sess.bug(
4524 &format!("node_id_to_type: no type for node `{}`",
4525 cx.map.node_to_string(id)))
4529 pub fn node_id_to_type_opt<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> Option<Ty<'tcx>> {
4530 match cx.node_types.borrow().get(&id) {
4531 Some(&ty) => Some(ty),
4536 pub fn node_id_item_substs<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> ItemSubsts<'tcx> {
4537 match cx.item_substs.borrow().get(&id) {
4538 None => ItemSubsts::empty(),
4539 Some(ts) => ts.clone(),
4543 pub fn fn_is_variadic(fty: Ty) -> bool {
4545 ty_bare_fn(_, ref f) => f.sig.0.variadic,
4547 panic!("fn_is_variadic() called on non-fn type: {:?}", s)
4552 pub fn ty_fn_sig<'tcx>(fty: Ty<'tcx>) -> &'tcx PolyFnSig<'tcx> {
4554 ty_bare_fn(_, ref f) => &f.sig,
4556 panic!("ty_fn_sig() called on non-fn type: {:?}", s)
4561 /// Returns the ABI of the given function.
4562 pub fn ty_fn_abi(fty: Ty) -> abi::Abi {
4564 ty_bare_fn(_, ref f) => f.abi,
4565 _ => panic!("ty_fn_abi() called on non-fn type"),
4569 // Type accessors for substructures of types
4570 pub fn ty_fn_args<'tcx>(fty: Ty<'tcx>) -> ty::Binder<Vec<Ty<'tcx>>> {
4571 ty_fn_sig(fty).inputs()
4574 pub fn ty_fn_ret<'tcx>(fty: Ty<'tcx>) -> Binder<FnOutput<'tcx>> {
4576 ty_bare_fn(_, ref f) => f.sig.output(),
4578 panic!("ty_fn_ret() called on non-fn type: {:?}", s)
4583 pub fn is_fn_ty(fty: Ty) -> bool {
4585 ty_bare_fn(..) => true,
4590 pub fn ty_region(tcx: &ctxt,
4594 ty_rptr(r, _) => *r,
4598 &format!("ty_region() invoked on an inappropriate ty: {:?}",
4604 pub fn free_region_from_def(outlives_extent: region::DestructionScopeData,
4605 def: &RegionParameterDef)
4609 ty::ReFree(ty::FreeRegion { scope: outlives_extent,
4610 bound_region: ty::BrNamed(def.def_id,
4612 debug!("free_region_from_def returns {:?}", ret);
4616 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
4617 // doesn't provide type parameter substitutions.
4618 pub fn pat_ty<'tcx>(cx: &ctxt<'tcx>, pat: &ast::Pat) -> Ty<'tcx> {
4619 return node_id_to_type(cx, pat.id);
4621 pub fn pat_ty_opt<'tcx>(cx: &ctxt<'tcx>, pat: &ast::Pat) -> Option<Ty<'tcx>> {
4622 return node_id_to_type_opt(cx, pat.id);
4626 // Returns the type of an expression as a monotype.
4628 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression. That is, in
4629 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
4630 // auto-ref. The type returned by this function does not consider such
4631 // adjustments. See `expr_ty_adjusted()` instead.
4633 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
4634 // ask for the type of "id" in "id(3)", it will return "fn(&isize) -> isize"
4635 // instead of "fn(ty) -> T with T = isize".
4636 pub fn expr_ty<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Ty<'tcx> {
4637 return node_id_to_type(cx, expr.id);
4640 pub fn expr_ty_opt<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Option<Ty<'tcx>> {
4641 return node_id_to_type_opt(cx, expr.id);
4644 /// Returns the type of `expr`, considering any `AutoAdjustment`
4645 /// entry recorded for that expression.
4647 /// It would almost certainly be better to store the adjusted ty in with
4648 /// the `AutoAdjustment`, but I opted not to do this because it would
4649 /// require serializing and deserializing the type and, although that's not
4650 /// hard to do, I just hate that code so much I didn't want to touch it
4651 /// unless it was to fix it properly, which seemed a distraction from the
4652 /// thread at hand! -nmatsakis
4653 pub fn expr_ty_adjusted<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Ty<'tcx> {
4654 adjust_ty(cx, expr.span, expr.id, expr_ty(cx, expr),
4655 cx.adjustments.borrow().get(&expr.id),
4656 |method_call| cx.method_map.borrow().get(&method_call).map(|method| method.ty))
4659 pub fn expr_span(cx: &ctxt, id: NodeId) -> Span {
4660 match cx.map.find(id) {
4661 Some(ast_map::NodeExpr(e)) => {
4665 cx.sess.bug(&format!("Node id {} is not an expr: {:?}",
4670 cx.sess.bug(&format!("Node id {} is not present \
4671 in the node map", id));
4676 pub fn local_var_name_str(cx: &ctxt, id: NodeId) -> InternedString {
4677 match cx.map.find(id) {
4678 Some(ast_map::NodeLocal(pat)) => {
4680 ast::PatIdent(_, ref path1, _) => {
4681 token::get_ident(path1.node)
4685 &format!("Variable id {} maps to {:?}, not local",
4692 cx.sess.bug(&format!("Variable id {} maps to {:?}, not local",
4699 /// See `expr_ty_adjusted`
4700 pub fn adjust_ty<'tcx, F>(cx: &ctxt<'tcx>,
4702 expr_id: ast::NodeId,
4703 unadjusted_ty: Ty<'tcx>,
4704 adjustment: Option<&AutoAdjustment<'tcx>>,
4707 F: FnMut(MethodCall) -> Option<Ty<'tcx>>,
4709 if let ty_err = unadjusted_ty.sty {
4710 return unadjusted_ty;
4713 return match adjustment {
4714 Some(adjustment) => {
4716 AdjustReifyFnPointer => {
4717 match unadjusted_ty.sty {
4718 ty::ty_bare_fn(Some(_), b) => {
4719 ty::mk_bare_fn(cx, None, b)
4723 &format!("AdjustReifyFnPointer adjustment on non-fn-item: \
4724 {}", unadjusted_ty.repr(cx)));
4729 AdjustUnsafeFnPointer => {
4730 match unadjusted_ty.sty {
4731 ty::ty_bare_fn(None, b) => cx.safe_to_unsafe_fn_ty(b),
4734 &format!("AdjustReifyFnPointer adjustment on non-fn-item: \
4741 AdjustDerefRef(ref adj) => {
4742 let mut adjusted_ty = unadjusted_ty;
4744 if !ty::type_is_error(adjusted_ty) {
4745 for i in 0..adj.autoderefs {
4746 let method_call = MethodCall::autoderef(expr_id, i as u32);
4747 match method_type(method_call) {
4748 Some(method_ty) => {
4749 // Overloaded deref operators have all late-bound
4750 // regions fully instantiated and coverge.
4752 ty::no_late_bound_regions(cx,
4753 &ty_fn_ret(method_ty)).unwrap();
4754 adjusted_ty = fn_ret.unwrap();
4758 match deref(adjusted_ty, true) {
4759 Some(mt) => { adjusted_ty = mt.ty; }
4763 &format!("the {}th autoderef failed: {}",
4765 ty_to_string(cx, adjusted_ty))
4772 if let Some(target) = adj.unsize {
4775 adjust_ty_for_autoref(cx, adjusted_ty, adj.autoref)
4780 None => unadjusted_ty
4784 pub fn adjust_ty_for_autoref<'tcx>(cx: &ctxt<'tcx>,
4786 autoref: Option<AutoRef<'tcx>>)
4790 Some(AutoPtr(r, m)) => {
4791 mk_rptr(cx, r, mt { ty: ty, mutbl: m })
4793 Some(AutoUnsafe(m)) => {
4794 mk_ptr(cx, mt { ty: ty, mutbl: m })
4799 pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> def::Def {
4800 match tcx.def_map.borrow().get(&expr.id) {
4801 Some(def) => def.full_def(),
4803 tcx.sess.span_bug(expr.span, &format!(
4804 "no def-map entry for expr {}", expr.id));
4809 pub fn expr_is_lval(tcx: &ctxt, e: &ast::Expr) -> bool {
4810 match expr_kind(tcx, e) {
4812 RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
4816 /// We categorize expressions into three kinds. The distinction between
4817 /// lvalue/rvalue is fundamental to the language. The distinction between the
4818 /// two kinds of rvalues is an artifact of trans which reflects how we will
4819 /// generate code for that kind of expression. See trans/expr.rs for more
4821 #[derive(Copy, Clone)]
4829 pub fn expr_kind(tcx: &ctxt, expr: &ast::Expr) -> ExprKind {
4830 if tcx.method_map.borrow().contains_key(&MethodCall::expr(expr.id)) {
4831 // Overloaded operations are generally calls, and hence they are
4832 // generated via DPS, but there are a few exceptions:
4833 return match expr.node {
4834 // `a += b` has a unit result.
4835 ast::ExprAssignOp(..) => RvalueStmtExpr,
4837 // the deref method invoked for `*a` always yields an `&T`
4838 ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
4840 // the index method invoked for `a[i]` always yields an `&T`
4841 ast::ExprIndex(..) => LvalueExpr,
4843 // in the general case, result could be any type, use DPS
4849 ast::ExprPath(..) => {
4850 match resolve_expr(tcx, expr) {
4851 def::DefVariant(tid, vid, _) => {
4852 let variant_info = enum_variant_with_id(tcx, tid, vid);
4853 if !variant_info.args.is_empty() {
4862 def::DefStruct(_) => {
4863 match tcx.node_types.borrow().get(&expr.id) {
4864 Some(ty) => match ty.sty {
4865 ty_bare_fn(..) => RvalueDatumExpr,
4868 // See ExprCast below for why types might be missing.
4869 None => RvalueDatumExpr
4873 // Special case: A unit like struct's constructor must be called without () at the
4874 // end (like `UnitStruct`) which means this is an ExprPath to a DefFn. But in case
4875 // of unit structs this is should not be interpreted as function pointer but as
4876 // call to the constructor.
4877 def::DefFn(_, true) => RvalueDpsExpr,
4879 // Fn pointers are just scalar values.
4880 def::DefFn(..) | def::DefMethod(..) => RvalueDatumExpr,
4882 // Note: there is actually a good case to be made that
4883 // DefArg's, particularly those of immediate type, ought to
4884 // considered rvalues.
4885 def::DefStatic(..) |
4887 def::DefLocal(..) => LvalueExpr,
4890 def::DefAssociatedConst(..) => RvalueDatumExpr,
4895 &format!("uncategorized def for expr {}: {:?}",
4902 ast::ExprUnary(ast::UnDeref, _) |
4903 ast::ExprField(..) |
4904 ast::ExprTupField(..) |
4905 ast::ExprIndex(..) => {
4910 ast::ExprMethodCall(..) |
4911 ast::ExprStruct(..) |
4912 ast::ExprRange(..) |
4915 ast::ExprMatch(..) |
4916 ast::ExprClosure(..) |
4917 ast::ExprBlock(..) |
4918 ast::ExprRepeat(..) |
4919 ast::ExprVec(..) => {
4923 ast::ExprIfLet(..) => {
4924 tcx.sess.span_bug(expr.span, "non-desugared ExprIfLet");
4926 ast::ExprWhileLet(..) => {
4927 tcx.sess.span_bug(expr.span, "non-desugared ExprWhileLet");
4930 ast::ExprForLoop(..) => {
4931 tcx.sess.span_bug(expr.span, "non-desugared ExprForLoop");
4934 ast::ExprLit(ref lit) if lit_is_str(&**lit) => {
4938 ast::ExprBreak(..) |
4939 ast::ExprAgain(..) |
4941 ast::ExprWhile(..) |
4943 ast::ExprAssign(..) |
4944 ast::ExprInlineAsm(..) |
4945 ast::ExprAssignOp(..) => {
4949 ast::ExprLit(_) | // Note: LitStr is carved out above
4950 ast::ExprUnary(..) |
4951 ast::ExprBox(None, _) |
4952 ast::ExprAddrOf(..) |
4953 ast::ExprBinary(..) |
4954 ast::ExprCast(..) => {
4958 ast::ExprBox(Some(ref place), _) => {
4959 // Special case `Box<T>` for now:
4960 let def_id = match tcx.def_map.borrow().get(&place.id) {
4961 Some(def) => def.def_id(),
4962 None => panic!("no def for place"),
4964 if tcx.lang_items.exchange_heap() == Some(def_id) {
4971 ast::ExprParen(ref e) => expr_kind(tcx, &**e),
4973 ast::ExprMac(..) => {
4976 "macro expression remains after expansion");
4981 pub fn stmt_node_id(s: &ast::Stmt) -> ast::NodeId {
4983 ast::StmtDecl(_, id) | StmtExpr(_, id) | StmtSemi(_, id) => {
4986 ast::StmtMac(..) => panic!("unexpanded macro in trans")
4990 pub fn field_idx_strict(tcx: &ctxt, name: ast::Name, fields: &[field])
4993 for f in fields { if f.name == name { return i; } i += 1; }
4994 tcx.sess.bug(&format!(
4995 "no field named `{}` found in the list of fields `{:?}`",
4996 token::get_name(name),
4998 .map(|f| token::get_name(f.name).to_string())
4999 .collect::<Vec<String>>()));
5002 pub fn impl_or_trait_item_idx(id: ast::Name, trait_items: &[ImplOrTraitItem])
5004 trait_items.iter().position(|m| m.name() == id)
5007 pub fn ty_sort_string<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> String {
5009 ty_bool | ty_char | ty_int(_) |
5010 ty_uint(_) | ty_float(_) | ty_str => {
5011 ::util::ppaux::ty_to_string(cx, ty)
5013 ty_tup(ref tys) if tys.is_empty() => ::util::ppaux::ty_to_string(cx, ty),
5015 ty_enum(id, _) => format!("enum `{}`", item_path_str(cx, id)),
5016 ty_uniq(_) => "box".to_string(),
5017 ty_vec(_, Some(n)) => format!("array of {} elements", n),
5018 ty_vec(_, None) => "slice".to_string(),
5019 ty_ptr(_) => "*-ptr".to_string(),
5020 ty_rptr(_, _) => "&-ptr".to_string(),
5021 ty_bare_fn(Some(_), _) => format!("fn item"),
5022 ty_bare_fn(None, _) => "fn pointer".to_string(),
5023 ty_trait(ref inner) => {
5024 format!("trait {}", item_path_str(cx, inner.principal_def_id()))
5026 ty_struct(id, _) => {
5027 format!("struct `{}`", item_path_str(cx, id))
5029 ty_closure(..) => "closure".to_string(),
5030 ty_tup(_) => "tuple".to_string(),
5031 ty_infer(TyVar(_)) => "inferred type".to_string(),
5032 ty_infer(IntVar(_)) => "integral variable".to_string(),
5033 ty_infer(FloatVar(_)) => "floating-point variable".to_string(),
5034 ty_infer(FreshTy(_)) => "skolemized type".to_string(),
5035 ty_infer(FreshIntTy(_)) => "skolemized integral type".to_string(),
5036 ty_infer(FreshFloatTy(_)) => "skolemized floating-point type".to_string(),
5037 ty_projection(_) => "associated type".to_string(),
5038 ty_param(ref p) => {
5039 if p.space == subst::SelfSpace {
5042 "type parameter".to_string()
5045 ty_err => "type error".to_string(),
5049 impl<'tcx> Repr<'tcx> for ty::type_err<'tcx> {
5050 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
5051 ty::type_err_to_str(tcx, self)
5055 /// Explains the source of a type err in a short, human readable way. This is meant to be placed
5056 /// in parentheses after some larger message. You should also invoke `note_and_explain_type_err()`
5057 /// afterwards to present additional details, particularly when it comes to lifetime-related
5059 pub fn type_err_to_str<'tcx>(cx: &ctxt<'tcx>, err: &type_err<'tcx>) -> String {
5061 terr_cyclic_ty => "cyclic type of infinite size".to_string(),
5062 terr_mismatch => "types differ".to_string(),
5063 terr_unsafety_mismatch(values) => {
5064 format!("expected {} fn, found {} fn",
5068 terr_abi_mismatch(values) => {
5069 format!("expected {} fn, found {} fn",
5073 terr_mutability => "values differ in mutability".to_string(),
5074 terr_box_mutability => {
5075 "boxed values differ in mutability".to_string()
5077 terr_vec_mutability => "vectors differ in mutability".to_string(),
5078 terr_ptr_mutability => "pointers differ in mutability".to_string(),
5079 terr_ref_mutability => "references differ in mutability".to_string(),
5080 terr_ty_param_size(values) => {
5081 format!("expected a type with {} type params, \
5082 found one with {} type params",
5086 terr_fixed_array_size(values) => {
5087 format!("expected an array with a fixed size of {} elements, \
5088 found one with {} elements",
5092 terr_tuple_size(values) => {
5093 format!("expected a tuple with {} elements, \
5094 found one with {} elements",
5099 "incorrect number of function parameters".to_string()
5101 terr_regions_does_not_outlive(..) => {
5102 "lifetime mismatch".to_string()
5104 terr_regions_not_same(..) => {
5105 "lifetimes are not the same".to_string()
5107 terr_regions_no_overlap(..) => {
5108 "lifetimes do not intersect".to_string()
5110 terr_regions_insufficiently_polymorphic(br, _) => {
5111 format!("expected bound lifetime parameter {}, \
5112 found concrete lifetime",
5113 bound_region_ptr_to_string(cx, br))
5115 terr_regions_overly_polymorphic(br, _) => {
5116 format!("expected concrete lifetime, \
5117 found bound lifetime parameter {}",
5118 bound_region_ptr_to_string(cx, br))
5120 terr_sorts(values) => {
5121 // A naive approach to making sure that we're not reporting silly errors such as:
5122 // (expected closure, found closure).
5123 let expected_str = ty_sort_string(cx, values.expected);
5124 let found_str = ty_sort_string(cx, values.found);
5125 if expected_str == found_str {
5126 format!("expected {}, found a different {}", expected_str, found_str)
5128 format!("expected {}, found {}", expected_str, found_str)
5131 terr_traits(values) => {
5132 format!("expected trait `{}`, found trait `{}`",
5133 item_path_str(cx, values.expected),
5134 item_path_str(cx, values.found))
5136 terr_builtin_bounds(values) => {
5137 if values.expected.is_empty() {
5138 format!("expected no bounds, found `{}`",
5139 values.found.user_string(cx))
5140 } else if values.found.is_empty() {
5141 format!("expected bounds `{}`, found no bounds",
5142 values.expected.user_string(cx))
5144 format!("expected bounds `{}`, found bounds `{}`",
5145 values.expected.user_string(cx),
5146 values.found.user_string(cx))
5149 terr_integer_as_char => {
5150 "expected an integral type, found `char`".to_string()
5152 terr_int_mismatch(ref values) => {
5153 format!("expected `{:?}`, found `{:?}`",
5157 terr_float_mismatch(ref values) => {
5158 format!("expected `{:?}`, found `{:?}`",
5162 terr_variadic_mismatch(ref values) => {
5163 format!("expected {} fn, found {} function",
5164 if values.expected { "variadic" } else { "non-variadic" },
5165 if values.found { "variadic" } else { "non-variadic" })
5167 terr_convergence_mismatch(ref values) => {
5168 format!("expected {} fn, found {} function",
5169 if values.expected { "converging" } else { "diverging" },
5170 if values.found { "converging" } else { "diverging" })
5172 terr_projection_name_mismatched(ref values) => {
5173 format!("expected {}, found {}",
5174 token::get_name(values.expected),
5175 token::get_name(values.found))
5177 terr_projection_bounds_length(ref values) => {
5178 format!("expected {} associated type bindings, found {}",
5185 pub fn note_and_explain_type_err<'tcx>(cx: &ctxt<'tcx>, err: &type_err<'tcx>, sp: Span) {
5187 terr_regions_does_not_outlive(subregion, superregion) => {
5188 note_and_explain_region(cx, "", subregion, "...");
5189 note_and_explain_region(cx, "...does not necessarily outlive ",
5192 terr_regions_not_same(region1, region2) => {
5193 note_and_explain_region(cx, "", region1, "...");
5194 note_and_explain_region(cx, "...is not the same lifetime as ",
5197 terr_regions_no_overlap(region1, region2) => {
5198 note_and_explain_region(cx, "", region1, "...");
5199 note_and_explain_region(cx, "...does not overlap ",
5202 terr_regions_insufficiently_polymorphic(_, conc_region) => {
5203 note_and_explain_region(cx,
5204 "concrete lifetime that was found is ",
5207 terr_regions_overly_polymorphic(_, ty::ReInfer(ty::ReVar(_))) => {
5208 // don't bother to print out the message below for
5209 // inference variables, it's not very illuminating.
5211 terr_regions_overly_polymorphic(_, conc_region) => {
5212 note_and_explain_region(cx,
5213 "expected concrete lifetime is ",
5216 terr_sorts(values) => {
5217 let expected_str = ty_sort_string(cx, values.expected);
5218 let found_str = ty_sort_string(cx, values.found);
5219 if expected_str == found_str && expected_str == "closure" {
5220 cx.sess.span_note(sp, &format!("no two closures, even if identical, have the same \
5222 cx.sess.span_help(sp, &format!("consider boxing your closure and/or \
5223 using it as a trait object"));
5230 pub fn provided_source(cx: &ctxt, id: ast::DefId) -> Option<ast::DefId> {
5231 cx.provided_method_sources.borrow().get(&id).cloned()
5234 pub fn provided_trait_methods<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5235 -> Vec<Rc<Method<'tcx>>> {
5237 if let ItemTrait(_, _, _, ref ms) = cx.map.expect_item(id.node).node {
5238 ms.iter().filter_map(|ti| {
5239 if let ast::MethodTraitItem(_, Some(_)) = ti.node {
5240 match impl_or_trait_item(cx, ast_util::local_def(ti.id)) {
5241 MethodTraitItem(m) => Some(m),
5243 cx.sess.bug("provided_trait_methods(): \
5244 non-method item found from \
5245 looking up provided method?!")
5253 cx.sess.bug(&format!("provided_trait_methods: `{:?}` is not a trait", id))
5256 csearch::get_provided_trait_methods(cx, id)
5260 pub fn associated_consts<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5261 -> Vec<Rc<AssociatedConst<'tcx>>> {
5263 match cx.map.expect_item(id.node).node {
5264 ItemTrait(_, _, _, ref tis) => {
5265 tis.iter().filter_map(|ti| {
5266 if let ast::ConstTraitItem(_, _) = ti.node {
5267 match impl_or_trait_item(cx, ast_util::local_def(ti.id)) {
5268 ConstTraitItem(ac) => Some(ac),
5270 cx.sess.bug("associated_consts(): \
5271 non-const item found from \
5272 looking up a constant?!")
5280 ItemImpl(_, _, _, _, _, ref iis) => {
5281 iis.iter().filter_map(|ii| {
5282 if let ast::ConstImplItem(_, _) = ii.node {
5283 match impl_or_trait_item(cx, ast_util::local_def(ii.id)) {
5284 ConstTraitItem(ac) => Some(ac),
5286 cx.sess.bug("associated_consts(): \
5287 non-const item found from \
5288 looking up a constant?!")
5297 cx.sess.bug(&format!("associated_consts: `{:?}` is not a trait \
5302 csearch::get_associated_consts(cx, id)
5306 /// Helper for looking things up in the various maps that are populated during
5307 /// typeck::collect (e.g., `cx.impl_or_trait_items`, `cx.tcache`, etc). All of
5308 /// these share the pattern that if the id is local, it should have been loaded
5309 /// into the map by the `typeck::collect` phase. If the def-id is external,
5310 /// then we have to go consult the crate loading code (and cache the result for
5312 fn lookup_locally_or_in_crate_store<V, F>(descr: &str,
5314 map: &RefCell<DefIdMap<V>>,
5315 load_external: F) -> V where
5319 match map.borrow().get(&def_id).cloned() {
5320 Some(v) => { return v; }
5324 if def_id.krate == ast::LOCAL_CRATE {
5325 panic!("No def'n found for {:?} in tcx.{}", def_id, descr);
5327 let v = load_external();
5328 map.borrow_mut().insert(def_id, v.clone());
5332 pub fn trait_item<'tcx>(cx: &ctxt<'tcx>, trait_did: ast::DefId, idx: usize)
5333 -> ImplOrTraitItem<'tcx> {
5334 let method_def_id = (*ty::trait_item_def_ids(cx, trait_did))[idx].def_id();
5335 impl_or_trait_item(cx, method_def_id)
5338 pub fn trait_items<'tcx>(cx: &ctxt<'tcx>, trait_did: ast::DefId)
5339 -> Rc<Vec<ImplOrTraitItem<'tcx>>> {
5340 let mut trait_items = cx.trait_items_cache.borrow_mut();
5341 match trait_items.get(&trait_did).cloned() {
5342 Some(trait_items) => trait_items,
5344 let def_ids = ty::trait_item_def_ids(cx, trait_did);
5345 let items: Rc<Vec<ImplOrTraitItem>> =
5346 Rc::new(def_ids.iter()
5347 .map(|d| impl_or_trait_item(cx, d.def_id()))
5349 trait_items.insert(trait_did, items.clone());
5355 pub fn trait_impl_polarity<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5356 -> Option<ast::ImplPolarity> {
5357 if id.krate == ast::LOCAL_CRATE {
5358 match cx.map.find(id.node) {
5359 Some(ast_map::NodeItem(item)) => {
5361 ast::ItemImpl(_, polarity, _, _, _, _) => Some(polarity),
5368 csearch::get_impl_polarity(cx, id)
5372 pub fn custom_coerce_unsized_kind<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
5373 -> CustomCoerceUnsized {
5374 memoized(&cx.custom_coerce_unsized_kinds, did, |did: DefId| {
5375 let (kind, src) = if did.krate != ast::LOCAL_CRATE {
5376 (csearch::get_custom_coerce_unsized_kind(cx, did), "external")
5384 cx.sess.bug(&format!("custom_coerce_unsized_kind: \
5385 {} impl `{}` is missing its kind",
5386 src, item_path_str(cx, did)));
5392 pub fn impl_or_trait_item<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5393 -> ImplOrTraitItem<'tcx> {
5394 lookup_locally_or_in_crate_store(
5395 "impl_or_trait_items", id, &cx.impl_or_trait_items,
5396 || csearch::get_impl_or_trait_item(cx, id))
5399 /// Returns the parameter index that the given associated type corresponds to.
5400 pub fn associated_type_parameter_index(cx: &ctxt,
5401 trait_def: &TraitDef,
5402 associated_type_id: ast::DefId)
5404 for type_parameter_def in trait_def.generics.types.iter() {
5405 if type_parameter_def.def_id == associated_type_id {
5406 return type_parameter_def.index as usize
5409 cx.sess.bug("couldn't find associated type parameter index")
5412 pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId)
5413 -> Rc<Vec<ImplOrTraitItemId>> {
5414 lookup_locally_or_in_crate_store(
5415 "trait_item_def_ids", id, &cx.trait_item_def_ids,
5416 || Rc::new(csearch::get_trait_item_def_ids(&cx.sess.cstore, id)))
5419 /// Returns the trait-ref corresponding to a given impl, or None if it is
5420 /// an inherent impl.
5421 pub fn impl_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5422 -> Option<TraitRef<'tcx>>
5424 lookup_locally_or_in_crate_store(
5425 "impl_trait_refs", id, &cx.impl_trait_refs,
5426 || csearch::get_impl_trait(cx, id))
5429 /// Returns whether this DefId refers to an impl
5430 pub fn is_impl<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId) -> bool {
5431 if id.krate == ast::LOCAL_CRATE {
5432 if let Some(ast_map::NodeItem(
5433 &ast::Item { node: ast::ItemImpl(..), .. })) = cx.map.find(id.node) {
5439 csearch::is_impl(&cx.sess.cstore, id)
5443 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
5444 tcx.def_map.borrow().get(&tr.ref_id).expect("no def-map entry for trait").def_id()
5447 pub fn try_add_builtin_trait(
5449 trait_def_id: ast::DefId,
5450 builtin_bounds: &mut EnumSet<BuiltinBound>)
5453 //! Checks whether `trait_ref` refers to one of the builtin
5454 //! traits, like `Send`, and adds the corresponding
5455 //! bound to the set `builtin_bounds` if so. Returns true if `trait_ref`
5456 //! is a builtin trait.
5458 match tcx.lang_items.to_builtin_kind(trait_def_id) {
5459 Some(bound) => { builtin_bounds.insert(bound); true }
5464 pub fn ty_to_def_id(ty: Ty) -> Option<ast::DefId> {
5467 Some(tt.principal_def_id()),
5470 ty_closure(id, _) =>
5479 pub struct VariantInfo<'tcx> {
5480 pub args: Vec<Ty<'tcx>>,
5481 pub arg_names: Option<Vec<ast::Name>>,
5482 pub ctor_ty: Option<Ty<'tcx>>,
5483 pub name: ast::Name,
5489 impl<'tcx> VariantInfo<'tcx> {
5491 /// Creates a new VariantInfo from the corresponding ast representation.
5493 /// Does not do any caching of the value in the type context.
5494 pub fn from_ast_variant(cx: &ctxt<'tcx>,
5495 ast_variant: &ast::Variant,
5496 discriminant: Disr) -> VariantInfo<'tcx> {
5497 let ctor_ty = node_id_to_type(cx, ast_variant.node.id);
5499 match ast_variant.node.kind {
5500 ast::TupleVariantKind(ref args) => {
5501 let arg_tys = if !args.is_empty() {
5502 // the regions in the argument types come from the
5503 // enum def'n, and hence will all be early bound
5504 ty::no_late_bound_regions(cx, &ty_fn_args(ctor_ty)).unwrap()
5509 return VariantInfo {
5512 ctor_ty: Some(ctor_ty),
5513 name: ast_variant.node.name.name,
5514 id: ast_util::local_def(ast_variant.node.id),
5515 disr_val: discriminant,
5516 vis: ast_variant.node.vis
5519 ast::StructVariantKind(ref struct_def) => {
5520 let fields: &[StructField] = &struct_def.fields;
5522 assert!(!fields.is_empty());
5524 let arg_tys = struct_def.fields.iter()
5525 .map(|field| node_id_to_type(cx, field.node.id)).collect();
5526 let arg_names = fields.iter().map(|field| {
5527 match field.node.kind {
5528 NamedField(ident, _) => ident.name,
5529 UnnamedField(..) => cx.sess.bug(
5530 "enum_variants: all fields in struct must have a name")
5534 return VariantInfo {
5536 arg_names: Some(arg_names),
5538 name: ast_variant.node.name.name,
5539 id: ast_util::local_def(ast_variant.node.id),
5540 disr_val: discriminant,
5541 vis: ast_variant.node.vis
5548 pub fn substd_enum_variants<'tcx>(cx: &ctxt<'tcx>,
5550 substs: &Substs<'tcx>)
5551 -> Vec<Rc<VariantInfo<'tcx>>> {
5552 enum_variants(cx, id).iter().map(|variant_info| {
5553 let substd_args = variant_info.args.iter()
5554 .map(|aty| aty.subst(cx, substs)).collect::<Vec<_>>();
5556 let substd_ctor_ty = variant_info.ctor_ty.subst(cx, substs);
5558 Rc::new(VariantInfo {
5560 ctor_ty: substd_ctor_ty,
5561 ..(**variant_info).clone()
5566 pub fn item_path_str(cx: &ctxt, id: ast::DefId) -> String {
5567 with_path(cx, id, |path| ast_map::path_to_string(path)).to_string()
5570 #[derive(Copy, Clone)]
5573 TraitDtor(DefId, bool)
5577 pub fn is_present(&self) -> bool {
5579 TraitDtor(..) => true,
5584 pub fn has_drop_flag(&self) -> bool {
5587 &TraitDtor(_, flag) => flag
5592 /* If struct_id names a struct with a dtor. */
5593 pub fn ty_dtor(cx: &ctxt, struct_id: DefId) -> DtorKind {
5594 match cx.destructor_for_type.borrow().get(&struct_id) {
5595 Some(&method_def_id) => {
5596 let flag = !has_attr(cx, struct_id, "unsafe_no_drop_flag");
5598 TraitDtor(method_def_id, flag)
5604 pub fn has_dtor(cx: &ctxt, struct_id: DefId) -> bool {
5605 cx.destructor_for_type.borrow().contains_key(&struct_id)
5608 pub fn with_path<T, F>(cx: &ctxt, id: ast::DefId, f: F) -> T where
5609 F: FnOnce(ast_map::PathElems) -> T,
5611 if id.krate == ast::LOCAL_CRATE {
5612 cx.map.with_path(id.node, f)
5614 f(csearch::get_item_path(cx, id).iter().cloned().chain(LinkedPath::empty()))
5618 pub fn enum_is_univariant(cx: &ctxt, id: ast::DefId) -> bool {
5619 enum_variants(cx, id).len() == 1
5622 pub fn type_is_empty(cx: &ctxt, ty: Ty) -> bool {
5624 ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
5630 fn to_ty<'tcx>(&self, cx: &ctxt<'tcx>) -> Ty<'tcx>;
5631 fn i64_to_disr(&self, val: i64) -> Option<Disr>;
5632 fn u64_to_disr(&self, val: u64) -> Option<Disr>;
5633 fn disr_incr(&self, val: Disr) -> Option<Disr>;
5634 fn disr_string(&self, val: Disr) -> String;
5635 fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr;
5638 impl IntTypeExt for attr::IntType {
5639 fn to_ty<'tcx>(&self, cx: &ctxt<'tcx>) -> Ty<'tcx> {
5641 SignedInt(ast::TyI8) => cx.types.i8,
5642 SignedInt(ast::TyI16) => cx.types.i16,
5643 SignedInt(ast::TyI32) => cx.types.i32,
5644 SignedInt(ast::TyI64) => cx.types.i64,
5645 SignedInt(ast::TyIs) => cx.types.isize,
5646 UnsignedInt(ast::TyU8) => cx.types.u8,
5647 UnsignedInt(ast::TyU16) => cx.types.u16,
5648 UnsignedInt(ast::TyU32) => cx.types.u32,
5649 UnsignedInt(ast::TyU64) => cx.types.u64,
5650 UnsignedInt(ast::TyUs) => cx.types.usize,
5654 fn i64_to_disr(&self, val: i64) -> Option<Disr> {
5656 SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr),
5657 SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr),
5658 SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr),
5659 SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr),
5660 UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr),
5661 UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr),
5662 UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr),
5663 UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr),
5665 UnsignedInt(ast::TyUs) |
5666 SignedInt(ast::TyIs) => unreachable!(),
5670 fn u64_to_disr(&self, val: u64) -> Option<Disr> {
5672 SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr),
5673 SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr),
5674 SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr),
5675 SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr),
5676 UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr),
5677 UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr),
5678 UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr),
5679 UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr),
5681 UnsignedInt(ast::TyUs) |
5682 SignedInt(ast::TyIs) => unreachable!(),
5686 fn disr_incr(&self, val: Disr) -> Option<Disr> {
5688 ($e:expr) => { $e.and_then(|v|v.checked_add(1)).map(|v| v as Disr) }
5691 // SignedInt repr means we *want* to reinterpret the bits
5692 // treating the highest bit of Disr as a sign-bit, so
5693 // cast to i64 before range-checking.
5694 SignedInt(ast::TyI8) => add1!((val as i64).to_i8()),
5695 SignedInt(ast::TyI16) => add1!((val as i64).to_i16()),
5696 SignedInt(ast::TyI32) => add1!((val as i64).to_i32()),
5697 SignedInt(ast::TyI64) => add1!(Some(val as i64)),
5699 UnsignedInt(ast::TyU8) => add1!(val.to_u8()),
5700 UnsignedInt(ast::TyU16) => add1!(val.to_u16()),
5701 UnsignedInt(ast::TyU32) => add1!(val.to_u32()),
5702 UnsignedInt(ast::TyU64) => add1!(Some(val)),
5704 UnsignedInt(ast::TyUs) |
5705 SignedInt(ast::TyIs) => unreachable!(),
5709 // This returns a String because (1.) it is only used for
5710 // rendering an error message and (2.) a string can represent the
5711 // full range from `i64::MIN` through `u64::MAX`.
5712 fn disr_string(&self, val: Disr) -> String {
5714 SignedInt(ast::TyI8) => format!("{}", val as i8 ),
5715 SignedInt(ast::TyI16) => format!("{}", val as i16),
5716 SignedInt(ast::TyI32) => format!("{}", val as i32),
5717 SignedInt(ast::TyI64) => format!("{}", val as i64),
5718 UnsignedInt(ast::TyU8) => format!("{}", val as u8 ),
5719 UnsignedInt(ast::TyU16) => format!("{}", val as u16),
5720 UnsignedInt(ast::TyU32) => format!("{}", val as u32),
5721 UnsignedInt(ast::TyU64) => format!("{}", val as u64),
5723 UnsignedInt(ast::TyUs) |
5724 SignedInt(ast::TyIs) => unreachable!(),
5728 fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr {
5730 ($e:expr) => { ($e).wrapping_add(1) as Disr }
5732 let val = val.unwrap_or(ty::INITIAL_DISCRIMINANT_VALUE);
5734 SignedInt(ast::TyI8) => add1!(val as i8 ),
5735 SignedInt(ast::TyI16) => add1!(val as i16),
5736 SignedInt(ast::TyI32) => add1!(val as i32),
5737 SignedInt(ast::TyI64) => add1!(val as i64),
5738 UnsignedInt(ast::TyU8) => add1!(val as u8 ),
5739 UnsignedInt(ast::TyU16) => add1!(val as u16),
5740 UnsignedInt(ast::TyU32) => add1!(val as u32),
5741 UnsignedInt(ast::TyU64) => add1!(val as u64),
5743 UnsignedInt(ast::TyUs) |
5744 SignedInt(ast::TyIs) => unreachable!(),
5749 /// Returns `(normalized_type, ty)`, where `normalized_type` is the
5750 /// IntType representation of one of {i64,i32,i16,i8,u64,u32,u16,u8},
5751 /// and `ty` is the original type (i.e. may include `isize` or
5753 pub fn enum_repr_type<'tcx>(cx: &ctxt<'tcx>,
5754 opt_hint: Option<&attr::ReprAttr>)
5755 -> (attr::IntType, Ty<'tcx>)
5757 let repr_type = match opt_hint {
5758 // Feed in the given type
5759 Some(&attr::ReprInt(_, int_t)) => int_t,
5760 // ... but provide sensible default if none provided
5762 // NB. Historically `fn enum_variants` generate i64 here, while
5763 // rustc_typeck::check would generate isize.
5764 _ => SignedInt(ast::TyIs),
5767 let repr_type_ty = repr_type.to_ty(cx);
5768 let repr_type = match repr_type {
5769 SignedInt(ast::TyIs) =>
5770 SignedInt(cx.sess.target.int_type),
5771 UnsignedInt(ast::TyUs) =>
5772 UnsignedInt(cx.sess.target.uint_type),
5776 (repr_type, repr_type_ty)
5779 fn report_discrim_overflow(cx: &ctxt,
5782 repr_type: attr::IntType,
5784 let computed_value = repr_type.disr_wrap_incr(Some(prev_val));
5785 let computed_value = repr_type.disr_string(computed_value);
5786 let prev_val = repr_type.disr_string(prev_val);
5787 let repr_type = repr_type.to_ty(cx).user_string(cx);
5788 span_err!(cx.sess, variant_span, E0370,
5789 "enum discriminant overflowed on value after {}: {}; \
5790 set explicitly via {} = {} if that is desired outcome",
5791 prev_val, repr_type, variant_name, computed_value);
5794 // This computes the discriminant values for the sequence of Variants
5795 // attached to a particular enum, taking into account the #[repr] (if
5796 // any) provided via the `opt_hint`.
5797 fn compute_enum_variants<'tcx>(cx: &ctxt<'tcx>,
5798 vs: &'tcx [P<ast::Variant>],
5799 opt_hint: Option<&attr::ReprAttr>)
5800 -> Vec<Rc<ty::VariantInfo<'tcx>>> {
5801 let mut variants: Vec<Rc<ty::VariantInfo>> = Vec::new();
5802 let mut prev_disr_val: Option<ty::Disr> = None;
5804 let (repr_type, repr_type_ty) = ty::enum_repr_type(cx, opt_hint);
5807 // If the discriminant value is specified explicitly in the
5808 // enum, check whether the initialization expression is valid,
5809 // otherwise use the last value plus one.
5810 let current_disr_val;
5812 // This closure marks cases where, when an error occurs during
5813 // the computation, attempt to assign a (hopefully) fresh
5814 // value to avoid spurious error reports downstream.
5815 let attempt_fresh_value = move || -> Disr {
5816 repr_type.disr_wrap_incr(prev_disr_val)
5819 match v.node.disr_expr {
5821 debug!("disr expr, checking {}", pprust::expr_to_string(&**e));
5823 // check_expr (from check_const pass) doesn't guarantee
5824 // that the expression is in a form that eval_const_expr can
5825 // handle, so we may still get an internal compiler error
5827 // pnkfelix: The above comment was transcribed from
5828 // the version of this code taken from rustc_typeck.
5829 // Presumably the implication is that we need to deal
5830 // with such ICE's as they arise.
5832 // Since this can be called from `ty::enum_variants`
5833 // anyway, best thing is to make `eval_const_expr`
5834 // more robust (on case-by-case basis).
5836 match const_eval::eval_const_expr_partial(cx, &**e, Some(repr_type_ty)) {
5837 Ok(const_eval::const_int(val)) => current_disr_val = val as Disr,
5838 Ok(const_eval::const_uint(val)) => current_disr_val = val as Disr,
5840 let sign_desc = if repr_type.is_signed() { "signed" } else { "unsigned" };
5841 span_err!(cx.sess, e.span, E0079,
5842 "expected {} integer constant",
5844 current_disr_val = attempt_fresh_value();
5847 span_err!(cx.sess, err.span, E0080,
5848 "constant evaluation error: {}",
5850 current_disr_val = attempt_fresh_value();
5855 current_disr_val = match prev_disr_val {
5856 Some(prev_disr_val) => {
5857 if let Some(v) = repr_type.disr_incr(prev_disr_val) {
5860 report_discrim_overflow(cx, v.span, v.node.name.as_str(),
5861 repr_type, prev_disr_val);
5862 attempt_fresh_value()
5865 None => ty::INITIAL_DISCRIMINANT_VALUE
5870 let variant_info = Rc::new(VariantInfo::from_ast_variant(cx, &**v, current_disr_val));
5871 prev_disr_val = Some(current_disr_val);
5873 variants.push(variant_info);
5879 pub fn enum_variants<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5880 -> Rc<Vec<Rc<VariantInfo<'tcx>>>> {
5881 memoized(&cx.enum_var_cache, id, |id: ast::DefId| {
5882 if ast::LOCAL_CRATE != id.krate {
5883 Rc::new(csearch::get_enum_variants(cx, id))
5885 match cx.map.get(id.node) {
5886 ast_map::NodeItem(ref item) => {
5888 ast::ItemEnum(ref enum_definition, _) => {
5889 Rc::new(compute_enum_variants(
5891 &enum_definition.variants,
5892 lookup_repr_hints(cx, id).get(0)))
5895 cx.sess.bug("enum_variants: id not bound to an enum")
5899 _ => cx.sess.bug("enum_variants: id not bound to an enum")
5905 // Returns information about the enum variant with the given ID:
5906 pub fn enum_variant_with_id<'tcx>(cx: &ctxt<'tcx>,
5907 enum_id: ast::DefId,
5908 variant_id: ast::DefId)
5909 -> Rc<VariantInfo<'tcx>> {
5910 enum_variants(cx, enum_id).iter()
5911 .find(|variant| variant.id == variant_id)
5912 .expect("enum_variant_with_id(): no variant exists with that ID")
5917 // If the given item is in an external crate, looks up its type and adds it to
5918 // the type cache. Returns the type parameters and type.
5919 pub fn lookup_item_type<'tcx>(cx: &ctxt<'tcx>,
5921 -> TypeScheme<'tcx> {
5922 lookup_locally_or_in_crate_store(
5923 "tcache", did, &cx.tcache,
5924 || csearch::get_type(cx, did))
5927 /// Given the did of a trait, returns its canonical trait ref.
5928 pub fn lookup_trait_def<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
5929 -> &'tcx TraitDef<'tcx> {
5930 lookup_locally_or_in_crate_store(
5931 "trait_defs", did, &cx.trait_defs,
5932 || cx.arenas.trait_defs.alloc(csearch::get_trait_def(cx, did))
5936 /// Given the did of an item, returns its full set of predicates.
5937 pub fn lookup_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
5938 -> GenericPredicates<'tcx>
5940 lookup_locally_or_in_crate_store(
5941 "predicates", did, &cx.predicates,
5942 || csearch::get_predicates(cx, did))
5945 /// Given the did of a trait, returns its superpredicates.
5946 pub fn lookup_super_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
5947 -> GenericPredicates<'tcx>
5949 lookup_locally_or_in_crate_store(
5950 "super_predicates", did, &cx.super_predicates,
5951 || csearch::get_super_predicates(cx, did))
5954 pub fn predicates<'tcx>(
5957 bounds: &ParamBounds<'tcx>)
5958 -> Vec<Predicate<'tcx>>
5960 let mut vec = Vec::new();
5962 for builtin_bound in &bounds.builtin_bounds {
5963 match traits::trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty) {
5964 Ok(trait_ref) => { vec.push(trait_ref.as_predicate()); }
5965 Err(ErrorReported) => { }
5969 for ®ion_bound in &bounds.region_bounds {
5970 // account for the binder being introduced below; no need to shift `param_ty`
5971 // because, at present at least, it can only refer to early-bound regions
5972 let region_bound = ty_fold::shift_region(region_bound, 1);
5973 vec.push(ty::Binder(ty::OutlivesPredicate(param_ty, region_bound)).as_predicate());
5976 for bound_trait_ref in &bounds.trait_bounds {
5977 vec.push(bound_trait_ref.as_predicate());
5980 for projection in &bounds.projection_bounds {
5981 vec.push(projection.as_predicate());
5987 /// Get the attributes of a definition.
5988 pub fn get_attrs<'tcx>(tcx: &'tcx ctxt, did: DefId)
5989 -> Cow<'tcx, [ast::Attribute]> {
5991 Cow::Borrowed(tcx.map.attrs(did.node))
5993 Cow::Owned(csearch::get_item_attrs(&tcx.sess.cstore, did))
5997 /// Determine whether an item is annotated with an attribute
5998 pub fn has_attr(tcx: &ctxt, did: DefId, attr: &str) -> bool {
5999 get_attrs(tcx, did).iter().any(|item| item.check_name(attr))
6002 /// Determine whether an item is annotated with `#[repr(packed)]`
6003 pub fn lookup_packed(tcx: &ctxt, did: DefId) -> bool {
6004 lookup_repr_hints(tcx, did).contains(&attr::ReprPacked)
6007 /// Determine whether an item is annotated with `#[simd]`
6008 pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
6009 has_attr(tcx, did, "simd")
6012 /// Obtain the representation annotation for a struct definition.
6013 pub fn lookup_repr_hints(tcx: &ctxt, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
6014 memoized(&tcx.repr_hint_cache, did, |did: DefId| {
6015 Rc::new(if did.krate == LOCAL_CRATE {
6016 get_attrs(tcx, did).iter().flat_map(|meta| {
6017 attr::find_repr_attrs(tcx.sess.diagnostic(), meta).into_iter()
6020 csearch::get_repr_attrs(&tcx.sess.cstore, did)
6025 // Look up a field ID, whether or not it's local
6026 pub fn lookup_field_type_unsubstituted<'tcx>(tcx: &ctxt<'tcx>,
6030 if id.krate == ast::LOCAL_CRATE {
6031 node_id_to_type(tcx, id.node)
6033 let mut tcache = tcx.tcache.borrow_mut();
6034 tcache.entry(id).or_insert_with(|| csearch::get_field_type(tcx, struct_id, id)).ty
6039 // Look up a field ID, whether or not it's local
6040 // Takes a list of type substs in case the struct is generic
6041 pub fn lookup_field_type<'tcx>(tcx: &ctxt<'tcx>,
6044 substs: &Substs<'tcx>)
6046 lookup_field_type_unsubstituted(tcx, struct_id, id).subst(tcx, substs)
6049 // Look up the list of field names and IDs for a given struct.
6050 // Panics if the id is not bound to a struct.
6051 pub fn lookup_struct_fields(cx: &ctxt, did: ast::DefId) -> Vec<field_ty> {
6052 if did.krate == ast::LOCAL_CRATE {
6053 let struct_fields = cx.struct_fields.borrow();
6054 match struct_fields.get(&did) {
6055 Some(fields) => (**fields).clone(),
6058 &format!("ID not mapped to struct fields: {}",
6059 cx.map.node_to_string(did.node)));
6063 csearch::get_struct_fields(&cx.sess.cstore, did)
6067 pub fn is_tuple_struct(cx: &ctxt, did: ast::DefId) -> bool {
6068 let fields = lookup_struct_fields(cx, did);
6069 !fields.is_empty() && fields.iter().all(|f| f.name == token::special_names::unnamed_field)
6072 // Returns a list of fields corresponding to the struct's items. trans uses
6073 // this. Takes a list of substs with which to instantiate field types.
6074 pub fn struct_fields<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId, substs: &Substs<'tcx>)
6075 -> Vec<field<'tcx>> {
6076 lookup_struct_fields(cx, did).iter().map(|f| {
6080 ty: lookup_field_type(cx, did, f.id, substs),
6087 // Returns a list of fields corresponding to the tuple's items. trans uses
6089 pub fn tup_fields<'tcx>(v: &[Ty<'tcx>]) -> Vec<field<'tcx>> {
6090 v.iter().enumerate().map(|(i, &f)| {
6092 name: token::intern(&i.to_string()),
6101 /// Returns the deeply last field of nested structures, or the same type,
6102 /// if not a structure at all. Corresponds to the only possible unsized
6103 /// field, and its type can be used to determine unsizing strategy.
6104 pub fn struct_tail<'tcx>(cx: &ctxt<'tcx>, mut ty: Ty<'tcx>) -> Ty<'tcx> {
6105 while let ty_struct(def_id, substs) = ty.sty {
6106 match struct_fields(cx, def_id, substs).last() {
6107 Some(f) => ty = f.mt.ty,
6114 /// Same as applying struct_tail on `source` and `target`, but only
6115 /// keeps going as long as the two types are instances of the same
6116 /// structure definitions.
6117 /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`,
6118 /// whereas struct_tail produces `T`, and `Trait`, respectively.
6119 pub fn struct_lockstep_tails<'tcx>(cx: &ctxt<'tcx>,
6122 -> (Ty<'tcx>, Ty<'tcx>) {
6123 let (mut a, mut b) = (source, target);
6124 while let (&ty_struct(a_did, a_substs), &ty_struct(b_did, b_substs)) = (&a.sty, &b.sty) {
6128 if let Some(a_f) = struct_fields(cx, a_did, a_substs).last() {
6129 if let Some(b_f) = struct_fields(cx, b_did, b_substs).last() {
6142 #[derive(Copy, Clone)]
6143 pub struct ClosureUpvar<'tcx> {
6149 // Returns a list of `ClosureUpvar`s for each upvar.
6150 pub fn closure_upvars<'tcx>(typer: &mc::Typer<'tcx>,
6151 closure_id: ast::DefId,
6152 substs: &Substs<'tcx>)
6153 -> Option<Vec<ClosureUpvar<'tcx>>>
6155 // Presently an unboxed closure type cannot "escape" out of a
6156 // function, so we will only encounter ones that originated in the
6157 // local crate or were inlined into it along with some function.
6158 // This may change if abstract return types of some sort are
6160 assert!(closure_id.krate == ast::LOCAL_CRATE);
6161 let tcx = typer.tcx();
6162 match tcx.freevars.borrow().get(&closure_id.node) {
6163 None => Some(vec![]),
6164 Some(ref freevars) => {
6167 let freevar_def_id = freevar.def.def_id();
6168 let freevar_ty = match typer.node_ty(freevar_def_id.node) {
6170 Err(()) => { return None; }
6172 let freevar_ty = freevar_ty.subst(tcx, substs);
6174 let upvar_id = ty::UpvarId {
6175 var_id: freevar_def_id.node,
6176 closure_expr_id: closure_id.node
6179 typer.upvar_capture(upvar_id).map(|capture| {
6180 let freevar_ref_ty = match capture {
6181 UpvarCapture::ByValue => {
6184 UpvarCapture::ByRef(borrow) => {
6186 tcx.mk_region(borrow.region),
6189 mutbl: borrow.kind.to_mutbl_lossy(),
6206 // Returns the repeat count for a repeating vector expression.
6207 pub fn eval_repeat_count(tcx: &ctxt, count_expr: &ast::Expr) -> usize {
6208 match const_eval::eval_const_expr_partial(tcx, count_expr, Some(tcx.types.usize)) {
6210 let found = match val {
6211 const_eval::const_uint(count) => return count as usize,
6212 const_eval::const_int(count) if count >= 0 => return count as usize,
6213 const_eval::const_int(_) => "negative integer",
6214 const_eval::const_float(_) => "float",
6215 const_eval::const_str(_) => "string",
6216 const_eval::const_bool(_) => "boolean",
6217 const_eval::const_binary(_) => "binary array",
6218 const_eval::Struct(..) => "struct",
6219 const_eval::Tuple(_) => "tuple"
6221 span_err!(tcx.sess, count_expr.span, E0306,
6222 "expected positive integer for repeat count, found {}",
6226 let err_description = err.description();
6227 let found = match count_expr.node {
6228 ast::ExprPath(None, ast::Path {
6232 }) if segments.len() == 1 =>
6233 format!("{}", "found variable"),
6235 format!("but {}", err_description),
6237 span_err!(tcx.sess, count_expr.span, E0307,
6238 "expected constant integer for repeat count, {}",
6245 // Iterate over a type parameter's bounded traits and any supertraits
6246 // of those traits, ignoring kinds.
6247 // Here, the supertraits are the transitive closure of the supertrait
6248 // relation on the supertraits from each bounded trait's constraint
6250 pub fn each_bound_trait_and_supertraits<'tcx, F>(tcx: &ctxt<'tcx>,
6251 bounds: &[PolyTraitRef<'tcx>],
6254 F: FnMut(PolyTraitRef<'tcx>) -> bool,
6256 for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
6257 if !f(bound_trait_ref) {
6264 /// Given a set of predicates that apply to an object type, returns
6265 /// the region bounds that the (erased) `Self` type must
6266 /// outlive. Precisely *because* the `Self` type is erased, the
6267 /// parameter `erased_self_ty` must be supplied to indicate what type
6268 /// has been used to represent `Self` in the predicates
6269 /// themselves. This should really be a unique type; `FreshTy(0)` is a
6272 /// Requires that trait definitions have been processed so that we can
6273 /// elaborate predicates and walk supertraits.
6274 pub fn required_region_bounds<'tcx>(tcx: &ctxt<'tcx>,
6275 erased_self_ty: Ty<'tcx>,
6276 predicates: Vec<ty::Predicate<'tcx>>)
6279 debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})",
6280 erased_self_ty.repr(tcx),
6281 predicates.repr(tcx));
6283 assert!(!erased_self_ty.has_escaping_regions());
6285 traits::elaborate_predicates(tcx, predicates)
6286 .filter_map(|predicate| {
6288 ty::Predicate::Projection(..) |
6289 ty::Predicate::Trait(..) |
6290 ty::Predicate::Equate(..) |
6291 ty::Predicate::RegionOutlives(..) => {
6294 ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t, r))) => {
6295 // Search for a bound of the form `erased_self_ty
6296 // : 'a`, but be wary of something like `for<'a>
6297 // erased_self_ty : 'a` (we interpret a
6298 // higher-ranked bound like that as 'static,
6299 // though at present the code in `fulfill.rs`
6300 // considers such bounds to be unsatisfiable, so
6301 // it's kind of a moot point since you could never
6302 // construct such an object, but this seems
6303 // correct even if that code changes).
6304 if t == erased_self_ty && !r.has_escaping_regions() {
6305 if r.has_escaping_regions() {
6319 pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
6320 lookup_locally_or_in_crate_store(
6321 "item_variance_map", item_id, &tcx.item_variance_map,
6322 || Rc::new(csearch::get_item_variances(&tcx.sess.cstore, item_id)))
6325 pub fn trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) -> bool {
6326 populate_implementations_for_trait_if_necessary(tcx, trait_def_id);
6328 let def = lookup_trait_def(tcx, trait_def_id);
6329 def.flags.get().intersects(TraitFlags::HAS_DEFAULT_IMPL)
6332 /// Records a trait-to-implementation mapping.
6333 pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) {
6334 let def = lookup_trait_def(tcx, trait_def_id);
6335 def.flags.set(def.flags.get() | TraitFlags::HAS_DEFAULT_IMPL)
6338 /// Load primitive inherent implementations if necessary
6339 pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt,
6340 primitive_def_id: ast::DefId) {
6341 if primitive_def_id.krate == LOCAL_CRATE {
6345 if tcx.populated_external_primitive_impls.borrow().contains(&primitive_def_id) {
6349 debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}",
6352 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, primitive_def_id);
6354 // Store the implementation info.
6355 tcx.impl_items.borrow_mut().insert(primitive_def_id, impl_items);
6356 tcx.populated_external_primitive_impls.borrow_mut().insert(primitive_def_id);
6359 /// Populates the type context with all the inherent implementations for
6360 /// the given type if necessary.
6361 pub fn populate_inherent_implementations_for_type_if_necessary(tcx: &ctxt,
6362 type_id: ast::DefId) {
6363 if type_id.krate == LOCAL_CRATE {
6367 if tcx.populated_external_types.borrow().contains(&type_id) {
6371 debug!("populate_inherent_implementations_for_type_if_necessary: searching for {:?}", type_id);
6373 let mut inherent_impls = Vec::new();
6374 csearch::each_inherent_implementation_for_type(&tcx.sess.cstore, type_id, |impl_def_id| {
6375 // Record the implementation.
6376 inherent_impls.push(impl_def_id);
6378 // Store the implementation info.
6379 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, impl_def_id);
6380 tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
6383 tcx.inherent_impls.borrow_mut().insert(type_id, Rc::new(inherent_impls));
6384 tcx.populated_external_types.borrow_mut().insert(type_id);
6387 /// Populates the type context with all the implementations for the given
6388 /// trait if necessary.
6389 pub fn populate_implementations_for_trait_if_necessary(tcx: &ctxt, trait_id: ast::DefId) {
6390 if trait_id.krate == LOCAL_CRATE {
6394 let def = lookup_trait_def(tcx, trait_id);
6395 if def.flags.get().intersects(TraitFlags::IMPLS_VALID) {
6399 debug!("populate_implementations_for_trait_if_necessary: searching for {}", def.repr(tcx));
6401 if csearch::is_defaulted_trait(&tcx.sess.cstore, trait_id) {
6402 record_trait_has_default_impl(tcx, trait_id);
6405 csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id, |implementation_def_id| {
6406 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
6407 let trait_ref = impl_trait_ref(tcx, implementation_def_id).unwrap();
6408 // Record the trait->implementation mapping.
6409 def.record_impl(tcx, implementation_def_id, trait_ref);
6411 // For any methods that use a default implementation, add them to
6412 // the map. This is a bit unfortunate.
6413 for impl_item_def_id in &impl_items {
6414 let method_def_id = impl_item_def_id.def_id();
6415 match impl_or_trait_item(tcx, method_def_id) {
6416 MethodTraitItem(method) => {
6417 if let Some(source) = method.provided_source {
6418 tcx.provided_method_sources
6420 .insert(method_def_id, source);
6427 // Store the implementation info.
6428 tcx.impl_items.borrow_mut().insert(implementation_def_id, impl_items);
6431 def.flags.set(def.flags.get() | TraitFlags::IMPLS_VALID);
6434 /// Given the def_id of an impl, return the def_id of the trait it implements.
6435 /// If it implements no trait, return `None`.
6436 pub fn trait_id_of_impl(tcx: &ctxt,
6438 -> Option<ast::DefId> {
6439 ty::impl_trait_ref(tcx, def_id).map(|tr| tr.def_id)
6442 /// If the given def ID describes a method belonging to an impl, return the
6443 /// ID of the impl that the method belongs to. Otherwise, return `None`.
6444 pub fn impl_of_method(tcx: &ctxt, def_id: ast::DefId)
6445 -> Option<ast::DefId> {
6446 if def_id.krate != LOCAL_CRATE {
6447 return match csearch::get_impl_or_trait_item(tcx,
6448 def_id).container() {
6449 TraitContainer(_) => None,
6450 ImplContainer(def_id) => Some(def_id),
6453 match tcx.impl_or_trait_items.borrow().get(&def_id).cloned() {
6454 Some(trait_item) => {
6455 match trait_item.container() {
6456 TraitContainer(_) => None,
6457 ImplContainer(def_id) => Some(def_id),
6464 /// If the given def ID describes an item belonging to a trait (either a
6465 /// default method or an implementation of a trait method), return the ID of
6466 /// the trait that the method belongs to. Otherwise, return `None`.
6467 pub fn trait_of_item(tcx: &ctxt, def_id: ast::DefId) -> Option<ast::DefId> {
6468 if def_id.krate != LOCAL_CRATE {
6469 return csearch::get_trait_of_item(&tcx.sess.cstore, def_id, tcx);
6471 match tcx.impl_or_trait_items.borrow().get(&def_id).cloned() {
6472 Some(impl_or_trait_item) => {
6473 match impl_or_trait_item.container() {
6474 TraitContainer(def_id) => Some(def_id),
6475 ImplContainer(def_id) => trait_id_of_impl(tcx, def_id),
6482 /// If the given def ID describes an item belonging to a trait, (either a
6483 /// default method or an implementation of a trait method), return the ID of
6484 /// the method inside trait definition (this means that if the given def ID
6485 /// is already that of the original trait method, then the return value is
6487 /// Otherwise, return `None`.
6488 pub fn trait_item_of_item(tcx: &ctxt, def_id: ast::DefId)
6489 -> Option<ImplOrTraitItemId> {
6490 let impl_item = match tcx.impl_or_trait_items.borrow().get(&def_id) {
6491 Some(m) => m.clone(),
6492 None => return None,
6494 let name = impl_item.name();
6495 match trait_of_item(tcx, def_id) {
6496 Some(trait_did) => {
6497 let trait_items = ty::trait_items(tcx, trait_did);
6499 .position(|m| m.name() == name)
6500 .map(|idx| ty::trait_item(tcx, trait_did, idx).id())
6506 /// Creates a hash of the type `Ty` which will be the same no matter what crate
6507 /// context it's calculated within. This is used by the `type_id` intrinsic.
6508 pub fn hash_crate_independent<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh) -> u64 {
6509 let mut state = SipHasher::new();
6510 helper(tcx, ty, svh, &mut state);
6511 return state.finish();
6513 fn helper<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh,
6514 state: &mut SipHasher) {
6515 macro_rules! byte { ($b:expr) => { ($b as u8).hash(state) } }
6516 macro_rules! hash { ($e:expr) => { $e.hash(state) } }
6518 let region = |state: &mut SipHasher, r: Region| {
6521 ReLateBound(db, BrAnon(i)) => {
6531 tcx.sess.bug("unexpected region found when hashing a type")
6535 let did = |state: &mut SipHasher, did: DefId| {
6536 let h = if ast_util::is_local(did) {
6539 tcx.sess.cstore.get_crate_hash(did.krate)
6541 h.as_str().hash(state);
6542 did.node.hash(state);
6544 let mt = |state: &mut SipHasher, mt: mt| {
6545 mt.mutbl.hash(state);
6547 let fn_sig = |state: &mut SipHasher, sig: &Binder<FnSig<'tcx>>| {
6548 let sig = anonymize_late_bound_regions(tcx, sig).0;
6549 for a in &sig.inputs { helper(tcx, *a, svh, state); }
6550 if let ty::FnConverging(output) = sig.output {
6551 helper(tcx, output, svh, state);
6554 maybe_walk_ty(ty, |ty| {
6556 ty_bool => byte!(2),
6557 ty_char => byte!(3),
6580 ty_vec(_, Some(n)) => {
6584 ty_vec(_, None) => {
6596 ty_bare_fn(opt_def_id, ref b) => {
6601 fn_sig(state, &b.sig);
6604 ty_trait(ref data) => {
6606 did(state, data.principal_def_id());
6609 let principal = anonymize_late_bound_regions(tcx, &data.principal).0;
6610 for subty in principal.substs.types.iter() {
6611 helper(tcx, *subty, svh, state);
6616 ty_struct(d, _) => {
6620 ty_tup(ref inner) => {
6628 hash!(token::get_name(p.name));
6630 ty_infer(_) => unreachable!(),
6631 ty_err => byte!(21),
6632 ty_closure(d, _) => {
6636 ty_projection(ref data) => {
6638 did(state, data.trait_ref.def_id);
6639 hash!(token::get_name(data.item_name));
6648 pub fn to_string(self) -> &'static str {
6651 Contravariant => "-",
6658 /// Construct a parameter environment suitable for static contexts or other contexts where there
6659 /// are no free type/lifetime parameters in scope.
6660 pub fn empty_parameter_environment<'a,'tcx>(cx: &'a ctxt<'tcx>) -> ParameterEnvironment<'a,'tcx> {
6661 ty::ParameterEnvironment { tcx: cx,
6662 free_substs: Substs::empty(),
6663 caller_bounds: Vec::new(),
6664 implicit_region_bound: ty::ReEmpty,
6665 selection_cache: traits::SelectionCache::new(), }
6668 /// Constructs and returns a substitution that can be applied to move from
6669 /// the "outer" view of a type or method to the "inner" view.
6670 /// In general, this means converting from bound parameters to
6671 /// free parameters. Since we currently represent bound/free type
6672 /// parameters in the same way, this only has an effect on regions.
6673 pub fn construct_free_substs<'a,'tcx>(
6674 tcx: &'a ctxt<'tcx>,
6675 generics: &Generics<'tcx>,
6676 free_id: ast::NodeId)
6680 let mut types = VecPerParamSpace::empty();
6681 push_types_from_defs(tcx, &mut types, generics.types.as_slice());
6683 let free_id_outlive = region::DestructionScopeData::new(free_id);
6685 // map bound 'a => free 'a
6686 let mut regions = VecPerParamSpace::empty();
6687 push_region_params(&mut regions, free_id_outlive, generics.regions.as_slice());
6691 regions: subst::NonerasedRegions(regions)
6694 fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
6695 all_outlive_extent: region::DestructionScopeData,
6696 region_params: &[RegionParameterDef])
6698 for r in region_params {
6699 regions.push(r.space, ty::free_region_from_def(all_outlive_extent, r));
6703 fn push_types_from_defs<'tcx>(tcx: &ty::ctxt<'tcx>,
6704 types: &mut VecPerParamSpace<Ty<'tcx>>,
6705 defs: &[TypeParameterDef<'tcx>]) {
6707 debug!("construct_parameter_environment(): push_types_from_defs: def={:?}",
6709 let ty = ty::mk_param_from_def(tcx, def);
6710 types.push(def.space, ty);
6715 /// See `ParameterEnvironment` struct def'n for details
6716 pub fn construct_parameter_environment<'a,'tcx>(
6717 tcx: &'a ctxt<'tcx>,
6719 generics: &ty::Generics<'tcx>,
6720 generic_predicates: &ty::GenericPredicates<'tcx>,
6721 free_id: ast::NodeId)
6722 -> ParameterEnvironment<'a, 'tcx>
6725 // Construct the free substs.
6728 let free_substs = construct_free_substs(tcx, generics, free_id);
6729 let free_id_outlive = region::DestructionScopeData::new(free_id);
6732 // Compute the bounds on Self and the type parameters.
6735 let bounds = generic_predicates.instantiate(tcx, &free_substs);
6736 let bounds = liberate_late_bound_regions(tcx, free_id_outlive, &ty::Binder(bounds));
6737 let predicates = bounds.predicates.into_vec();
6739 debug!("construct_parameter_environment: free_id={:?} free_subst={:?} predicates={:?}",
6741 free_substs.repr(tcx),
6742 predicates.repr(tcx));
6745 // Finally, we have to normalize the bounds in the environment, in
6746 // case they contain any associated type projections. This process
6747 // can yield errors if the put in illegal associated types, like
6748 // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
6749 // report these errors right here; this doesn't actually feel
6750 // right to me, because constructing the environment feels like a
6751 // kind of a "idempotent" action, but I'm not sure where would be
6752 // a better place. In practice, we construct environments for
6753 // every fn once during type checking, and we'll abort if there
6754 // are any errors at that point, so after type checking you can be
6755 // sure that this will succeed without errors anyway.
6758 let unnormalized_env = ty::ParameterEnvironment {
6760 free_substs: free_substs,
6761 implicit_region_bound: ty::ReScope(free_id_outlive.to_code_extent()),
6762 caller_bounds: predicates,
6763 selection_cache: traits::SelectionCache::new(),
6766 let cause = traits::ObligationCause::misc(span, free_id);
6767 traits::normalize_param_env_or_error(unnormalized_env, cause)
6771 pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
6773 ast::MutMutable => MutBorrow,
6774 ast::MutImmutable => ImmBorrow,
6778 /// Returns a mutability `m` such that an `&m T` pointer could be used to obtain this borrow
6779 /// kind. Because borrow kinds are richer than mutabilities, we sometimes have to pick a
6780 /// mutability that is stronger than necessary so that it at least *would permit* the borrow in
6782 pub fn to_mutbl_lossy(self) -> ast::Mutability {
6784 MutBorrow => ast::MutMutable,
6785 ImmBorrow => ast::MutImmutable,
6787 // We have no type corresponding to a unique imm borrow, so
6788 // use `&mut`. It gives all the capabilities of an `&uniq`
6789 // and hence is a safe "over approximation".
6790 UniqueImmBorrow => ast::MutMutable,
6794 pub fn to_user_str(&self) -> &'static str {
6796 MutBorrow => "mutable",
6797 ImmBorrow => "immutable",
6798 UniqueImmBorrow => "uniquely immutable",
6803 impl<'tcx> ctxt<'tcx> {
6804 pub fn is_method_call(&self, expr_id: ast::NodeId) -> bool {
6805 self.method_map.borrow().contains_key(&MethodCall::expr(expr_id))
6808 pub fn upvar_capture(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarCapture> {
6809 Some(self.upvar_capture_map.borrow().get(&upvar_id).unwrap().clone())
6813 impl<'a,'tcx> mc::Typer<'tcx> for ParameterEnvironment<'a,'tcx> {
6814 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
6815 Ok(ty::node_id_to_type(self.tcx, id))
6818 fn expr_ty_adjusted(&self, expr: &ast::Expr) -> mc::McResult<Ty<'tcx>> {
6819 Ok(ty::expr_ty_adjusted(self.tcx, expr))
6822 fn node_method_ty(&self, method_call: ty::MethodCall) -> Option<Ty<'tcx>> {
6823 self.tcx.method_map.borrow().get(&method_call).map(|method| method.ty)
6826 fn node_method_origin(&self, method_call: ty::MethodCall)
6827 -> Option<ty::MethodOrigin<'tcx>>
6829 self.tcx.method_map.borrow().get(&method_call).map(|method| method.origin.clone())
6832 fn adjustments(&self) -> &RefCell<NodeMap<ty::AutoAdjustment<'tcx>>> {
6833 &self.tcx.adjustments
6836 fn is_method_call(&self, id: ast::NodeId) -> bool {
6837 self.tcx.is_method_call(id)
6840 fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<region::CodeExtent> {
6841 self.tcx.region_maps.temporary_scope(rvalue_id)
6844 fn upvar_capture(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarCapture> {
6845 self.tcx.upvar_capture(upvar_id)
6848 fn type_moves_by_default(&self, span: Span, ty: Ty<'tcx>) -> bool {
6849 type_moves_by_default(self, span, ty)
6853 impl<'a,'tcx> ClosureTyper<'tcx> for ty::ParameterEnvironment<'a,'tcx> {
6854 fn param_env<'b>(&'b self) -> &'b ty::ParameterEnvironment<'b,'tcx> {
6858 fn closure_kind(&self,
6860 -> Option<ty::ClosureKind>
6862 Some(self.tcx.closure_kind(def_id))
6865 fn closure_type(&self,
6867 substs: &subst::Substs<'tcx>)
6868 -> ty::ClosureTy<'tcx>
6870 self.tcx.closure_type(def_id, substs)
6873 fn closure_upvars(&self,
6875 substs: &Substs<'tcx>)
6876 -> Option<Vec<ClosureUpvar<'tcx>>>
6878 closure_upvars(self, def_id, substs)
6883 /// The category of explicit self.
6884 #[derive(Clone, Copy, Eq, PartialEq, Debug)]
6885 pub enum ExplicitSelfCategory {
6886 StaticExplicitSelfCategory,
6887 ByValueExplicitSelfCategory,
6888 ByReferenceExplicitSelfCategory(Region, ast::Mutability),
6889 ByBoxExplicitSelfCategory,
6892 /// Pushes all the lifetimes in the given type onto the given list. A
6893 /// "lifetime in a type" is a lifetime specified by a reference or a lifetime
6894 /// in a list of type substitutions. This does *not* traverse into nominal
6895 /// types, nor does it resolve fictitious types.
6896 pub fn accumulate_lifetimes_in_type(accumulator: &mut Vec<ty::Region>,
6900 ty_rptr(region, _) => {
6901 accumulator.push(*region)
6903 ty_trait(ref t) => {
6904 accumulator.push_all(t.principal.0.substs.regions().as_slice());
6906 ty_enum(_, substs) |
6907 ty_struct(_, substs) => {
6908 accum_substs(accumulator, substs);
6910 ty_closure(_, substs) => {
6911 accum_substs(accumulator, substs);
6932 fn accum_substs(accumulator: &mut Vec<Region>, substs: &Substs) {
6933 match substs.regions {
6934 subst::ErasedRegions => {}
6935 subst::NonerasedRegions(ref regions) => {
6936 for region in regions.iter() {
6937 accumulator.push(*region)
6944 /// A free variable referred to in a function.
6945 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
6946 pub struct Freevar {
6947 /// The variable being accessed free.
6950 // First span where it is accessed (there can be multiple).
6954 pub type FreevarMap = NodeMap<Vec<Freevar>>;
6956 pub type CaptureModeMap = NodeMap<ast::CaptureClause>;
6958 // Trait method resolution
6959 pub type TraitMap = NodeMap<Vec<DefId>>;
6961 // Map from the NodeId of a glob import to a list of items which are actually
6963 pub type GlobMap = HashMap<NodeId, HashSet<Name>>;
6965 pub fn with_freevars<T, F>(tcx: &ty::ctxt, fid: ast::NodeId, f: F) -> T where
6966 F: FnOnce(&[Freevar]) -> T,
6968 match tcx.freevars.borrow().get(&fid) {
6970 Some(d) => f(&d[..])
6974 impl<'tcx> AutoAdjustment<'tcx> {
6975 pub fn is_identity(&self) -> bool {
6977 AdjustReifyFnPointer |
6978 AdjustUnsafeFnPointer => false,
6979 AdjustDerefRef(ref r) => r.is_identity(),
6984 impl<'tcx> AutoDerefRef<'tcx> {
6985 pub fn is_identity(&self) -> bool {
6986 self.autoderefs == 0 && self.unsize.is_none() && self.autoref.is_none()
6990 /// Replace any late-bound regions bound in `value` with free variants attached to scope-id
6992 pub fn liberate_late_bound_regions<'tcx, T>(
6993 tcx: &ty::ctxt<'tcx>,
6994 all_outlive_scope: region::DestructionScopeData,
6997 where T : TypeFoldable<'tcx> + Repr<'tcx>
6999 ty_fold::replace_late_bound_regions(
7001 |br| ty::ReFree(ty::FreeRegion{scope: all_outlive_scope, bound_region: br})).0
7004 pub fn count_late_bound_regions<'tcx, T>(
7005 tcx: &ty::ctxt<'tcx>,
7008 where T : TypeFoldable<'tcx> + Repr<'tcx>
7010 let (_, skol_map) = ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic);
7014 pub fn binds_late_bound_regions<'tcx, T>(
7015 tcx: &ty::ctxt<'tcx>,
7018 where T : TypeFoldable<'tcx> + Repr<'tcx>
7020 count_late_bound_regions(tcx, value) > 0
7023 /// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
7024 /// becomes `for<'a,'b> Foo`.
7025 pub fn flatten_late_bound_regions<'tcx, T>(
7026 tcx: &ty::ctxt<'tcx>,
7027 bound2_value: &Binder<Binder<T>>)
7029 where T: TypeFoldable<'tcx> + Repr<'tcx>
7031 let bound0_value = bound2_value.skip_binder().skip_binder();
7032 let value = ty_fold::fold_regions(tcx, bound0_value, |region, current_depth| {
7034 ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
7035 // should be true if no escaping regions from bound2_value
7036 assert!(debruijn.depth - current_depth <= 1);
7037 ty::ReLateBound(DebruijnIndex::new(current_depth), br)
7047 pub fn no_late_bound_regions<'tcx, T>(
7048 tcx: &ty::ctxt<'tcx>,
7051 where T : TypeFoldable<'tcx> + Repr<'tcx> + Clone
7053 if binds_late_bound_regions(tcx, value) {
7056 Some(value.0.clone())
7060 /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also
7061 /// method lookup and a few other places where precise region relationships are not required.
7062 pub fn erase_late_bound_regions<'tcx, T>(
7063 tcx: &ty::ctxt<'tcx>,
7066 where T : TypeFoldable<'tcx> + Repr<'tcx>
7068 ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic).0
7071 /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
7072 /// assigned starting at 1 and increasing monotonically in the order traversed
7073 /// by the fold operation.
7075 /// The chief purpose of this function is to canonicalize regions so that two
7076 /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
7077 /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
7078 /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
7079 pub fn anonymize_late_bound_regions<'tcx, T>(
7083 where T : TypeFoldable<'tcx> + Repr<'tcx>,
7085 let mut counter = 0;
7086 ty::Binder(ty_fold::replace_late_bound_regions(tcx, sig, |_| {
7088 ReLateBound(ty::DebruijnIndex::new(1), BrAnon(counter))
7092 impl DebruijnIndex {
7093 pub fn new(depth: u32) -> DebruijnIndex {
7095 DebruijnIndex { depth: depth }
7098 pub fn shifted(&self, amount: u32) -> DebruijnIndex {
7099 DebruijnIndex { depth: self.depth + amount }
7103 impl<'tcx> Repr<'tcx> for AutoAdjustment<'tcx> {
7104 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7106 AdjustReifyFnPointer => {
7107 format!("AdjustReifyFnPointer")
7109 AdjustUnsafeFnPointer => {
7110 format!("AdjustUnsafeFnPointer")
7112 AdjustDerefRef(ref data) => {
7119 impl<'tcx> Repr<'tcx> for AutoDerefRef<'tcx> {
7120 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7121 format!("AutoDerefRef({}, unsize={}, {})",
7122 self.autoderefs, self.unsize.repr(tcx), self.autoref.repr(tcx))
7126 impl<'tcx> Repr<'tcx> for AutoRef<'tcx> {
7127 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7130 format!("AutoPtr({},{:?})", a.repr(tcx), b)
7132 AutoUnsafe(ref a) => {
7133 format!("AutoUnsafe({:?})", a)
7139 impl<'tcx> Repr<'tcx> for TyTrait<'tcx> {
7140 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7141 format!("TyTrait({},{})",
7142 self.principal.repr(tcx),
7143 self.bounds.repr(tcx))
7147 impl<'tcx> Repr<'tcx> for ty::Predicate<'tcx> {
7148 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7150 Predicate::Trait(ref a) => a.repr(tcx),
7151 Predicate::Equate(ref pair) => pair.repr(tcx),
7152 Predicate::RegionOutlives(ref pair) => pair.repr(tcx),
7153 Predicate::TypeOutlives(ref pair) => pair.repr(tcx),
7154 Predicate::Projection(ref pair) => pair.repr(tcx),
7159 pub fn make_substs_for_receiver_types<'tcx>(tcx: &ty::ctxt<'tcx>,
7160 trait_ref: &ty::TraitRef<'tcx>,
7161 method: &ty::Method<'tcx>)
7162 -> subst::Substs<'tcx>
7165 * Substitutes the values for the receiver's type parameters
7166 * that are found in method, leaving the method's type parameters
7170 let meth_tps: Vec<Ty> =
7171 method.generics.types.get_slice(subst::FnSpace)
7173 .map(|def| ty::mk_param_from_def(tcx, def))
7175 let meth_regions: Vec<ty::Region> =
7176 method.generics.regions.get_slice(subst::FnSpace)
7178 .map(|def| def.to_early_bound_region())
7180 trait_ref.substs.clone().with_method(meth_tps, meth_regions)
7183 #[derive(Copy, Clone)]
7184 pub enum CopyImplementationError {
7185 FieldDoesNotImplementCopy(ast::Name),
7186 VariantDoesNotImplementCopy(ast::Name),
7191 pub fn can_type_implement_copy<'a,'tcx>(param_env: &ParameterEnvironment<'a, 'tcx>,
7193 self_type: Ty<'tcx>)
7194 -> Result<(),CopyImplementationError>
7196 let tcx = param_env.tcx;
7198 let did = match self_type.sty {
7199 ty::ty_struct(struct_did, substs) => {
7200 let fields = ty::struct_fields(tcx, struct_did, substs);
7201 for field in &fields {
7202 if type_moves_by_default(param_env, span, field.mt.ty) {
7203 return Err(FieldDoesNotImplementCopy(field.name))
7208 ty::ty_enum(enum_did, substs) => {
7209 let enum_variants = ty::enum_variants(tcx, enum_did);
7210 for variant in &*enum_variants {
7211 for variant_arg_type in &variant.args {
7212 let substd_arg_type =
7213 variant_arg_type.subst(tcx, substs);
7214 if type_moves_by_default(param_env, span, substd_arg_type) {
7215 return Err(VariantDoesNotImplementCopy(variant.name))
7221 _ => return Err(TypeIsStructural),
7224 if ty::has_dtor(tcx, did) {
7225 return Err(TypeHasDestructor)
7231 // FIXME(#20298) -- all of these types basically walk various
7232 // structures to test whether types/regions are reachable with various
7233 // properties. It should be possible to express them in terms of one
7234 // common "walker" trait or something.
7236 pub trait RegionEscape {
7237 fn has_escaping_regions(&self) -> bool {
7238 self.has_regions_escaping_depth(0)
7241 fn has_regions_escaping_depth(&self, depth: u32) -> bool;
7244 impl<'tcx> RegionEscape for Ty<'tcx> {
7245 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7246 ty::type_escapes_depth(*self, depth)
7250 impl<'tcx> RegionEscape for Substs<'tcx> {
7251 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7252 self.types.has_regions_escaping_depth(depth) ||
7253 self.regions.has_regions_escaping_depth(depth)
7257 impl<'tcx,T:RegionEscape> RegionEscape for VecPerParamSpace<T> {
7258 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7259 self.iter_enumerated().any(|(space, _, t)| {
7260 if space == subst::FnSpace {
7261 t.has_regions_escaping_depth(depth+1)
7263 t.has_regions_escaping_depth(depth)
7269 impl<'tcx> RegionEscape for TypeScheme<'tcx> {
7270 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7271 self.ty.has_regions_escaping_depth(depth)
7275 impl RegionEscape for Region {
7276 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7277 self.escapes_depth(depth)
7281 impl<'tcx> RegionEscape for GenericPredicates<'tcx> {
7282 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7283 self.predicates.has_regions_escaping_depth(depth)
7287 impl<'tcx> RegionEscape for Predicate<'tcx> {
7288 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7290 Predicate::Trait(ref data) => data.has_regions_escaping_depth(depth),
7291 Predicate::Equate(ref data) => data.has_regions_escaping_depth(depth),
7292 Predicate::RegionOutlives(ref data) => data.has_regions_escaping_depth(depth),
7293 Predicate::TypeOutlives(ref data) => data.has_regions_escaping_depth(depth),
7294 Predicate::Projection(ref data) => data.has_regions_escaping_depth(depth),
7299 impl<'tcx,P:RegionEscape> RegionEscape for traits::Obligation<'tcx,P> {
7300 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7301 self.predicate.has_regions_escaping_depth(depth)
7305 impl<'tcx> RegionEscape for TraitRef<'tcx> {
7306 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7307 self.substs.types.iter().any(|t| t.has_regions_escaping_depth(depth)) ||
7308 self.substs.regions.has_regions_escaping_depth(depth)
7312 impl<'tcx> RegionEscape for subst::RegionSubsts {
7313 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7315 subst::ErasedRegions => false,
7316 subst::NonerasedRegions(ref r) => {
7317 r.iter().any(|t| t.has_regions_escaping_depth(depth))
7323 impl<'tcx,T:RegionEscape> RegionEscape for Binder<T> {
7324 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7325 self.0.has_regions_escaping_depth(depth + 1)
7329 impl<'tcx> RegionEscape for EquatePredicate<'tcx> {
7330 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7331 self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
7335 impl<'tcx> RegionEscape for TraitPredicate<'tcx> {
7336 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7337 self.trait_ref.has_regions_escaping_depth(depth)
7341 impl<T:RegionEscape,U:RegionEscape> RegionEscape for OutlivesPredicate<T,U> {
7342 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7343 self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
7347 impl<'tcx> RegionEscape for ProjectionPredicate<'tcx> {
7348 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7349 self.projection_ty.has_regions_escaping_depth(depth) ||
7350 self.ty.has_regions_escaping_depth(depth)
7354 impl<'tcx> RegionEscape for ProjectionTy<'tcx> {
7355 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7356 self.trait_ref.has_regions_escaping_depth(depth)
7360 impl<'tcx> Repr<'tcx> for ty::ProjectionPredicate<'tcx> {
7361 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7362 format!("ProjectionPredicate({}, {})",
7363 self.projection_ty.repr(tcx),
7368 pub trait HasProjectionTypes {
7369 fn has_projection_types(&self) -> bool;
7372 impl<'tcx,T:HasProjectionTypes> HasProjectionTypes for Vec<T> {
7373 fn has_projection_types(&self) -> bool {
7374 self.iter().any(|p| p.has_projection_types())
7378 impl<'tcx,T:HasProjectionTypes> HasProjectionTypes for VecPerParamSpace<T> {
7379 fn has_projection_types(&self) -> bool {
7380 self.iter().any(|p| p.has_projection_types())
7384 impl<'tcx> HasProjectionTypes for ClosureTy<'tcx> {
7385 fn has_projection_types(&self) -> bool {
7386 self.sig.has_projection_types()
7390 impl<'tcx> HasProjectionTypes for ClosureUpvar<'tcx> {
7391 fn has_projection_types(&self) -> bool {
7392 self.ty.has_projection_types()
7396 impl<'tcx> HasProjectionTypes for ty::InstantiatedPredicates<'tcx> {
7397 fn has_projection_types(&self) -> bool {
7398 self.predicates.has_projection_types()
7402 impl<'tcx> HasProjectionTypes for Predicate<'tcx> {
7403 fn has_projection_types(&self) -> bool {
7405 Predicate::Trait(ref data) => data.has_projection_types(),
7406 Predicate::Equate(ref data) => data.has_projection_types(),
7407 Predicate::RegionOutlives(ref data) => data.has_projection_types(),
7408 Predicate::TypeOutlives(ref data) => data.has_projection_types(),
7409 Predicate::Projection(ref data) => data.has_projection_types(),
7414 impl<'tcx> HasProjectionTypes for TraitPredicate<'tcx> {
7415 fn has_projection_types(&self) -> bool {
7416 self.trait_ref.has_projection_types()
7420 impl<'tcx> HasProjectionTypes for EquatePredicate<'tcx> {
7421 fn has_projection_types(&self) -> bool {
7422 self.0.has_projection_types() || self.1.has_projection_types()
7426 impl HasProjectionTypes for Region {
7427 fn has_projection_types(&self) -> bool {
7432 impl<T:HasProjectionTypes,U:HasProjectionTypes> HasProjectionTypes for OutlivesPredicate<T,U> {
7433 fn has_projection_types(&self) -> bool {
7434 self.0.has_projection_types() || self.1.has_projection_types()
7438 impl<'tcx> HasProjectionTypes for ProjectionPredicate<'tcx> {
7439 fn has_projection_types(&self) -> bool {
7440 self.projection_ty.has_projection_types() || self.ty.has_projection_types()
7444 impl<'tcx> HasProjectionTypes for ProjectionTy<'tcx> {
7445 fn has_projection_types(&self) -> bool {
7446 self.trait_ref.has_projection_types()
7450 impl<'tcx> HasProjectionTypes for Ty<'tcx> {
7451 fn has_projection_types(&self) -> bool {
7452 ty::type_has_projection(*self)
7456 impl<'tcx> HasProjectionTypes for TraitRef<'tcx> {
7457 fn has_projection_types(&self) -> bool {
7458 self.substs.has_projection_types()
7462 impl<'tcx> HasProjectionTypes for subst::Substs<'tcx> {
7463 fn has_projection_types(&self) -> bool {
7464 self.types.iter().any(|t| t.has_projection_types())
7468 impl<'tcx,T> HasProjectionTypes for Option<T>
7469 where T : HasProjectionTypes
7471 fn has_projection_types(&self) -> bool {
7472 self.iter().any(|t| t.has_projection_types())
7476 impl<'tcx,T> HasProjectionTypes for Rc<T>
7477 where T : HasProjectionTypes
7479 fn has_projection_types(&self) -> bool {
7480 (**self).has_projection_types()
7484 impl<'tcx,T> HasProjectionTypes for Box<T>
7485 where T : HasProjectionTypes
7487 fn has_projection_types(&self) -> bool {
7488 (**self).has_projection_types()
7492 impl<T> HasProjectionTypes for Binder<T>
7493 where T : HasProjectionTypes
7495 fn has_projection_types(&self) -> bool {
7496 self.0.has_projection_types()
7500 impl<'tcx> HasProjectionTypes for FnOutput<'tcx> {
7501 fn has_projection_types(&self) -> bool {
7503 FnConverging(t) => t.has_projection_types(),
7504 FnDiverging => false,
7509 impl<'tcx> HasProjectionTypes for FnSig<'tcx> {
7510 fn has_projection_types(&self) -> bool {
7511 self.inputs.iter().any(|t| t.has_projection_types()) ||
7512 self.output.has_projection_types()
7516 impl<'tcx> HasProjectionTypes for field<'tcx> {
7517 fn has_projection_types(&self) -> bool {
7518 self.mt.ty.has_projection_types()
7522 impl<'tcx> HasProjectionTypes for BareFnTy<'tcx> {
7523 fn has_projection_types(&self) -> bool {
7524 self.sig.has_projection_types()
7528 pub trait ReferencesError {
7529 fn references_error(&self) -> bool;
7532 impl<T:ReferencesError> ReferencesError for Binder<T> {
7533 fn references_error(&self) -> bool {
7534 self.0.references_error()
7538 impl<T:ReferencesError> ReferencesError for Rc<T> {
7539 fn references_error(&self) -> bool {
7540 (&**self).references_error()
7544 impl<'tcx> ReferencesError for TraitPredicate<'tcx> {
7545 fn references_error(&self) -> bool {
7546 self.trait_ref.references_error()
7550 impl<'tcx> ReferencesError for ProjectionPredicate<'tcx> {
7551 fn references_error(&self) -> bool {
7552 self.projection_ty.trait_ref.references_error() || self.ty.references_error()
7556 impl<'tcx> ReferencesError for TraitRef<'tcx> {
7557 fn references_error(&self) -> bool {
7558 self.input_types().iter().any(|t| t.references_error())
7562 impl<'tcx> ReferencesError for Ty<'tcx> {
7563 fn references_error(&self) -> bool {
7564 type_is_error(*self)
7568 impl<'tcx> ReferencesError for Predicate<'tcx> {
7569 fn references_error(&self) -> bool {
7571 Predicate::Trait(ref data) => data.references_error(),
7572 Predicate::Equate(ref data) => data.references_error(),
7573 Predicate::RegionOutlives(ref data) => data.references_error(),
7574 Predicate::TypeOutlives(ref data) => data.references_error(),
7575 Predicate::Projection(ref data) => data.references_error(),
7580 impl<A,B> ReferencesError for OutlivesPredicate<A,B>
7581 where A : ReferencesError, B : ReferencesError
7583 fn references_error(&self) -> bool {
7584 self.0.references_error() || self.1.references_error()
7588 impl<'tcx> ReferencesError for EquatePredicate<'tcx>
7590 fn references_error(&self) -> bool {
7591 self.0.references_error() || self.1.references_error()
7595 impl ReferencesError for Region
7597 fn references_error(&self) -> bool {
7602 impl<'tcx> Repr<'tcx> for ClosureTy<'tcx> {
7603 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7604 format!("ClosureTy({},{},{})",
7611 impl<'tcx> Repr<'tcx> for ClosureUpvar<'tcx> {
7612 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7613 format!("ClosureUpvar({},{})",
7619 impl<'tcx> Repr<'tcx> for field<'tcx> {
7620 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7621 format!("field({},{})",
7622 self.name.repr(tcx),
7627 impl<'a, 'tcx> Repr<'tcx> for ParameterEnvironment<'a, 'tcx> {
7628 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7629 format!("ParameterEnvironment(\
7631 implicit_region_bound={}, \
7633 self.free_substs.repr(tcx),
7634 self.implicit_region_bound.repr(tcx),
7635 self.caller_bounds.repr(tcx))
7639 impl<'tcx> Repr<'tcx> for ObjectLifetimeDefault {
7640 fn repr(&self, tcx: &ctxt<'tcx>) -> String {
7642 ObjectLifetimeDefault::Ambiguous => format!("Ambiguous"),
7643 ObjectLifetimeDefault::Specific(ref r) => r.repr(tcx),