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::InferTy::*;
16 pub use self::InferRegion::*;
17 pub use self::ImplOrTraitItemId::*;
18 pub use self::ClosureKind::*;
19 pub use self::Variance::*;
20 pub use self::AutoAdjustment::*;
21 pub use self::Representability::*;
22 pub use self::AutoRef::*;
23 pub use self::DtorKind::*;
24 pub use self::ExplicitSelfCategory::*;
25 pub use self::FnOutput::*;
26 pub use self::Region::*;
27 pub use self::ImplOrTraitItemContainer::*;
28 pub use self::BorrowKind::*;
29 pub use self::ImplOrTraitItem::*;
30 pub use self::BoundRegion::*;
31 pub use self::TypeVariants::*;
32 pub use self::IntVarValue::*;
33 pub use self::MethodOrigin::*;
34 pub use self::CopyImplementationError::*;
36 pub use self::BuiltinBound::Send as BoundSend;
37 pub use self::BuiltinBound::Sized as BoundSized;
38 pub use self::BuiltinBound::Copy as BoundCopy;
39 pub use self::BuiltinBound::Sync as BoundSync;
41 use ast_map::{self, LinkedPath};
45 use metadata::csearch;
48 use middle::check_const;
49 use middle::const_eval;
50 use middle::def::{self, DefMap, ExportMap};
51 use middle::dependency_format;
52 use middle::fast_reject;
53 use middle::free_region::FreeRegionMap;
54 use middle::infer::error_reporting::note_and_explain_region;
55 use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem};
56 use middle::mem_categorization as mc;
58 use middle::resolve_lifetime;
61 use middle::region::RegionMaps;
62 use middle::stability;
63 use middle::subst::{self, ParamSpace, Subst, Substs, VecPerParamSpace};
66 use middle::ty_fold::{self, TypeFoldable, TypeFolder};
67 use middle::ty_walk::{self, TypeWalker};
68 use util::common::{memoized, ErrorReported};
69 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet};
70 use util::nodemap::FnvHashMap;
71 use util::num::ToPrimitive;
73 use arena::TypedArena;
74 use std::borrow::{Borrow, Cow};
75 use std::cell::{Cell, RefCell, Ref};
78 use std::hash::{Hash, SipHasher, Hasher};
82 use std::vec::IntoIter;
83 use collections::enum_set::{self, EnumSet, CLike};
84 use std::collections::{HashMap, HashSet};
86 use syntax::ast::{CrateNum, DefId, ItemImpl, ItemTrait, LOCAL_CRATE};
87 use syntax::ast::{MutImmutable, MutMutable, Name, NamedField, NodeId};
88 use syntax::ast::{StmtExpr, StmtSemi, StructField, UnnamedField, Visibility};
89 use syntax::ast_util::{self, is_local, local_def};
90 use syntax::attr::{self, AttrMetaMethods, SignedInt, UnsignedInt};
91 use syntax::codemap::Span;
92 use syntax::parse::token::{self, InternedString, special_idents};
93 use syntax::print::pprust;
99 pub const INITIAL_DISCRIMINANT_VALUE: Disr = 0;
103 /// The complete set of all analyses described in this module. This is
104 /// produced by the driver and fed to trans and later passes.
105 pub struct CrateAnalysis {
106 pub export_map: ExportMap,
107 pub exported_items: middle::privacy::ExportedItems,
108 pub public_items: middle::privacy::PublicItems,
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,
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, 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)]
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)]
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.
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.
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
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 /// A set of predicates that have been fulfilled *somewhere*.
757 /// This is used to avoid duplicate work. Predicates are only
758 /// added to this set when they mention only "global" names
759 /// (i.e., no type or lifetime parameters).
760 pub fulfilled_predicates: RefCell<traits::FulfilledPredicates<'tcx>>,
762 /// Caches the representation hints for struct definitions.
763 pub repr_hint_cache: RefCell<DefIdMap<Rc<Vec<attr::ReprAttr>>>>,
765 /// Maps Expr NodeId's to their constant qualification.
766 pub const_qualif_map: RefCell<NodeMap<check_const::ConstQualif>>,
768 /// Caches CoerceUnsized kinds for impls on custom types.
769 pub custom_coerce_unsized_kinds: RefCell<DefIdMap<CustomCoerceUnsized>>,
771 /// Maps a cast expression to its kind. This is keyed on the
772 /// *from* expression of the cast, not the cast itself.
773 pub cast_kinds: RefCell<NodeMap<cast::CastKind>>,
776 impl<'tcx> ctxt<'tcx> {
777 pub fn node_types(&self) -> Ref<NodeMap<Ty<'tcx>>> { self.node_types.borrow() }
778 pub fn node_type_insert(&self, id: NodeId, ty: Ty<'tcx>) {
779 self.node_types.borrow_mut().insert(id, ty);
782 pub fn intern_trait_def(&self, def: TraitDef<'tcx>) -> &'tcx TraitDef<'tcx> {
783 let did = def.trait_ref.def_id;
784 let interned = self.arenas.trait_defs.alloc(def);
785 self.trait_defs.borrow_mut().insert(did, interned);
789 pub fn intern_stability(&self, stab: attr::Stability) -> &'tcx attr::Stability {
790 if let Some(st) = self.stability_interner.borrow().get(&stab) {
794 let interned = self.arenas.stability.alloc(stab);
795 self.stability_interner.borrow_mut().insert(interned, interned);
799 pub fn store_free_region_map(&self, id: NodeId, map: FreeRegionMap) {
800 self.free_region_maps.borrow_mut()
804 pub fn free_region_map(&self, id: NodeId) -> FreeRegionMap {
805 self.free_region_maps.borrow()[&id].clone()
808 pub fn lift<T: ?Sized + Lift<'tcx>>(&self, value: &T) -> Option<T::Lifted> {
809 value.lift_to_tcx(self)
813 /// A trait implemented for all X<'a> types which can be safely and
814 /// efficiently converted to X<'tcx> as long as they are part of the
815 /// provided ty::ctxt<'tcx>.
816 /// This can be done, for example, for Ty<'tcx> or &'tcx Substs<'tcx>
817 /// by looking them up in their respective interners.
818 /// None is returned if the value or one of the components is not part
819 /// of the provided context.
820 /// For Ty, None can be returned if either the type interner doesn't
821 /// contain the TypeVariants key or if the address of the interned
822 /// pointer differs. The latter case is possible if a primitive type,
823 /// e.g. `()` or `u8`, was interned in a different context.
824 pub trait Lift<'tcx> {
826 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted>;
829 impl<'tcx, A: Lift<'tcx>, B: Lift<'tcx>> Lift<'tcx> for (A, B) {
830 type Lifted = (A::Lifted, B::Lifted);
831 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted> {
832 tcx.lift(&self.0).and_then(|a| tcx.lift(&self.1).map(|b| (a, b)))
836 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for [T] {
837 type Lifted = Vec<T::Lifted>;
838 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted> {
839 let mut result = Vec::with_capacity(self.len());
841 if let Some(value) = tcx.lift(x) {
851 impl<'tcx> Lift<'tcx> for Region {
853 fn lift_to_tcx(&self, _: &ctxt<'tcx>) -> Option<Region> {
858 impl<'a, 'tcx> Lift<'tcx> for Ty<'a> {
859 type Lifted = Ty<'tcx>;
860 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Ty<'tcx>> {
861 if let Some(&ty) = tcx.interner.borrow().get(&self.sty) {
862 if *self as *const _ == ty as *const _ {
870 impl<'a, 'tcx> Lift<'tcx> for &'a Substs<'a> {
871 type Lifted = &'tcx Substs<'tcx>;
872 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<&'tcx Substs<'tcx>> {
873 if let Some(&substs) = tcx.substs_interner.borrow().get(*self) {
874 if *self as *const _ == substs as *const _ {
882 impl<'a, 'tcx> Lift<'tcx> for TraitRef<'a> {
883 type Lifted = TraitRef<'tcx>;
884 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<TraitRef<'tcx>> {
885 tcx.lift(&self.substs).map(|substs| TraitRef {
892 impl<'a, 'tcx> Lift<'tcx> for TraitPredicate<'a> {
893 type Lifted = TraitPredicate<'tcx>;
894 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<TraitPredicate<'tcx>> {
895 tcx.lift(&self.trait_ref).map(|trait_ref| TraitPredicate {
901 impl<'a, 'tcx> Lift<'tcx> for EquatePredicate<'a> {
902 type Lifted = EquatePredicate<'tcx>;
903 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<EquatePredicate<'tcx>> {
904 tcx.lift(&(self.0, self.1)).map(|(a, b)| EquatePredicate(a, b))
908 impl<'tcx, A: Copy+Lift<'tcx>, B: Copy+Lift<'tcx>> Lift<'tcx> for OutlivesPredicate<A, B> {
909 type Lifted = OutlivesPredicate<A::Lifted, B::Lifted>;
910 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted> {
911 tcx.lift(&(self.0, self.1)).map(|(a, b)| OutlivesPredicate(a, b))
915 impl<'a, 'tcx> Lift<'tcx> for ProjectionPredicate<'a> {
916 type Lifted = ProjectionPredicate<'tcx>;
917 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<ProjectionPredicate<'tcx>> {
918 tcx.lift(&(self.projection_ty.trait_ref, self.ty)).map(|(trait_ref, ty)| {
919 ProjectionPredicate {
920 projection_ty: ProjectionTy {
921 trait_ref: trait_ref,
922 item_name: self.projection_ty.item_name
930 impl<'tcx, T: Lift<'tcx>> Lift<'tcx> for Binder<T> {
931 type Lifted = Binder<T::Lifted>;
932 fn lift_to_tcx(&self, tcx: &ctxt<'tcx>) -> Option<Self::Lifted> {
933 tcx.lift(&self.0).map(|x| Binder(x))
940 use session::Session;
946 /// Marker type used for the scoped TLS slot.
947 /// The type context cannot be used directly because the scoped TLS
948 /// in libstd doesn't allow types generic over lifetimes.
949 struct ThreadLocalTyCx;
951 scoped_thread_local!(static TLS_TCX: ThreadLocalTyCx);
953 fn def_id_debug(def_id: ast::DefId, f: &mut fmt::Formatter) -> fmt::Result {
954 // Unfortunately, there seems to be no way to attempt to print
955 // a path for a def-id, so I'll just make a best effort for now
956 // and otherwise fallback to just printing the crate/node pair
958 if def_id.krate == ast::LOCAL_CRATE {
959 match tcx.map.find(def_id.node) {
960 Some(ast_map::NodeItem(..)) |
961 Some(ast_map::NodeForeignItem(..)) |
962 Some(ast_map::NodeImplItem(..)) |
963 Some(ast_map::NodeTraitItem(..)) |
964 Some(ast_map::NodeVariant(..)) |
965 Some(ast_map::NodeStructCtor(..)) => {
966 return write!(f, "{}", ty::item_path_str(tcx, def_id));
975 fn span_debug(span: codemap::Span, f: &mut fmt::Formatter) -> fmt::Result {
977 write!(f, "{}", tcx.sess.codemap().span_to_string(span))
981 pub fn enter<'tcx, F: FnOnce(&ty::ctxt<'tcx>) -> R, R>(tcx: ty::ctxt<'tcx>, f: F)
983 let result = ast::DEF_ID_DEBUG.with(|def_id_dbg| {
984 codemap::SPAN_DEBUG.with(|span_dbg| {
985 let original_def_id_debug = def_id_dbg.get();
986 def_id_dbg.set(def_id_debug);
987 let original_span_debug = span_dbg.get();
988 span_dbg.set(span_debug);
989 let tls_ptr = &tcx as *const _ as *const ThreadLocalTyCx;
990 let result = TLS_TCX.set(unsafe { &*tls_ptr }, || f(&tcx));
991 def_id_dbg.set(original_def_id_debug);
992 span_dbg.set(original_span_debug);
999 pub fn with<F: FnOnce(&ty::ctxt) -> R, R>(f: F) -> R {
1000 TLS_TCX.with(|tcx| f(unsafe { &*(tcx as *const _ as *const ty::ctxt) }))
1004 // Flags that we track on types. These flags are propagated upwards
1005 // through the type during type construction, so that we can quickly
1006 // check whether the type has various kinds of types in it without
1007 // recursing over the type itself.
1009 flags TypeFlags: u32 {
1010 const HAS_PARAMS = 1 << 0,
1011 const HAS_SELF = 1 << 1,
1012 const HAS_TY_INFER = 1 << 2,
1013 const HAS_RE_INFER = 1 << 3,
1014 const HAS_RE_EARLY_BOUND = 1 << 4,
1015 const HAS_FREE_REGIONS = 1 << 5,
1016 const HAS_TY_ERR = 1 << 6,
1017 const HAS_PROJECTION = 1 << 7,
1018 const HAS_TY_CLOSURE = 1 << 8,
1020 // true if there are "names" of types and regions and so forth
1021 // that are local to a particular fn
1022 const HAS_LOCAL_NAMES = 1 << 9,
1024 const NEEDS_SUBST = TypeFlags::HAS_PARAMS.bits |
1025 TypeFlags::HAS_SELF.bits |
1026 TypeFlags::HAS_RE_EARLY_BOUND.bits,
1028 // Flags representing the nominal content of a type,
1029 // computed by FlagsComputation. If you add a new nominal
1030 // flag, it should be added here too.
1031 const NOMINAL_FLAGS = TypeFlags::HAS_PARAMS.bits |
1032 TypeFlags::HAS_SELF.bits |
1033 TypeFlags::HAS_TY_INFER.bits |
1034 TypeFlags::HAS_RE_INFER.bits |
1035 TypeFlags::HAS_RE_EARLY_BOUND.bits |
1036 TypeFlags::HAS_FREE_REGIONS.bits |
1037 TypeFlags::HAS_TY_ERR.bits |
1038 TypeFlags::HAS_PROJECTION.bits |
1039 TypeFlags::HAS_TY_CLOSURE.bits |
1040 TypeFlags::HAS_LOCAL_NAMES.bits,
1042 // Caches for type_is_sized, type_moves_by_default
1043 const SIZEDNESS_CACHED = 1 << 16,
1044 const IS_SIZED = 1 << 17,
1045 const MOVENESS_CACHED = 1 << 18,
1046 const MOVES_BY_DEFAULT = 1 << 19,
1050 macro_rules! sty_debug_print {
1051 ($ctxt: expr, $($variant: ident),*) => {{
1052 // curious inner module to allow variant names to be used as
1054 #[allow(non_snake_case)]
1057 #[derive(Copy, Clone)]
1060 region_infer: usize,
1065 pub fn go(tcx: &ty::ctxt) {
1066 let mut total = DebugStat {
1068 region_infer: 0, ty_infer: 0, both_infer: 0,
1070 $(let mut $variant = total;)*
1073 for (_, t) in tcx.interner.borrow().iter() {
1074 let variant = match t.sty {
1075 ty::TyBool | ty::TyChar | ty::TyInt(..) | ty::TyUint(..) |
1076 ty::TyFloat(..) | ty::TyStr => continue,
1077 ty::TyError => /* unimportant */ continue,
1078 $(ty::$variant(..) => &mut $variant,)*
1080 let region = t.flags.get().intersects(ty::TypeFlags::HAS_RE_INFER);
1081 let ty = t.flags.get().intersects(ty::TypeFlags::HAS_TY_INFER);
1085 if region { total.region_infer += 1; variant.region_infer += 1 }
1086 if ty { total.ty_infer += 1; variant.ty_infer += 1 }
1087 if region && ty { total.both_infer += 1; variant.both_infer += 1 }
1089 println!("Ty interner total ty region both");
1090 $(println!(" {:18}: {uses:6} {usespc:4.1}%, \
1091 {ty:4.1}% {region:5.1}% {both:4.1}%",
1092 stringify!($variant),
1093 uses = $variant.total,
1094 usespc = $variant.total as f64 * 100.0 / total.total as f64,
1095 ty = $variant.ty_infer as f64 * 100.0 / total.total as f64,
1096 region = $variant.region_infer as f64 * 100.0 / total.total as f64,
1097 both = $variant.both_infer as f64 * 100.0 / total.total as f64);
1099 println!(" total {uses:6} \
1100 {ty:4.1}% {region:5.1}% {both:4.1}%",
1102 ty = total.ty_infer as f64 * 100.0 / total.total as f64,
1103 region = total.region_infer as f64 * 100.0 / total.total as f64,
1104 both = total.both_infer as f64 * 100.0 / total.total as f64)
1112 impl<'tcx> ctxt<'tcx> {
1113 pub fn print_debug_stats(&self) {
1116 TyEnum, TyBox, TyArray, TySlice, TyRawPtr, TyRef, TyBareFn, TyTrait,
1117 TyStruct, TyClosure, TyTuple, TyParam, TyInfer, TyProjection);
1119 println!("Substs interner: #{}", self.substs_interner.borrow().len());
1120 println!("BareFnTy interner: #{}", self.bare_fn_interner.borrow().len());
1121 println!("Region interner: #{}", self.region_interner.borrow().len());
1122 println!("Stability interner: #{}", self.stability_interner.borrow().len());
1126 pub struct TyS<'tcx> {
1127 pub sty: TypeVariants<'tcx>,
1128 pub flags: Cell<TypeFlags>,
1130 // the maximal depth of any bound regions appearing in this type.
1134 impl fmt::Debug for TypeFlags {
1135 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1136 write!(f, "{}", self.bits)
1140 impl<'tcx> PartialEq for TyS<'tcx> {
1142 fn eq(&self, other: &TyS<'tcx>) -> bool {
1143 // (self as *const _) == (other as *const _)
1144 (self as *const TyS<'tcx>) == (other as *const TyS<'tcx>)
1147 impl<'tcx> Eq for TyS<'tcx> {}
1149 impl<'tcx> Hash for TyS<'tcx> {
1150 fn hash<H: Hasher>(&self, s: &mut H) {
1151 (self as *const TyS).hash(s)
1155 pub type Ty<'tcx> = &'tcx TyS<'tcx>;
1157 /// An entry in the type interner.
1158 pub struct InternedTy<'tcx> {
1162 // NB: An InternedTy compares and hashes as a sty.
1163 impl<'tcx> PartialEq for InternedTy<'tcx> {
1164 fn eq(&self, other: &InternedTy<'tcx>) -> bool {
1165 self.ty.sty == other.ty.sty
1169 impl<'tcx> Eq for InternedTy<'tcx> {}
1171 impl<'tcx> Hash for InternedTy<'tcx> {
1172 fn hash<H: Hasher>(&self, s: &mut H) {
1177 impl<'tcx> Borrow<TypeVariants<'tcx>> for InternedTy<'tcx> {
1178 fn borrow<'a>(&'a self) -> &'a TypeVariants<'tcx> {
1183 pub fn type_has_params(ty: Ty) -> bool {
1184 ty.flags.get().intersects(TypeFlags::HAS_PARAMS)
1186 pub fn type_has_self(ty: Ty) -> bool {
1187 ty.flags.get().intersects(TypeFlags::HAS_SELF)
1189 pub fn type_has_ty_infer(ty: Ty) -> bool {
1190 ty.flags.get().intersects(TypeFlags::HAS_TY_INFER)
1192 pub fn type_needs_infer(ty: Ty) -> bool {
1193 ty.flags.get().intersects(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER)
1195 pub fn type_is_global(ty: Ty) -> bool {
1196 !ty.flags.get().intersects(TypeFlags::HAS_LOCAL_NAMES)
1198 pub fn type_has_projection(ty: Ty) -> bool {
1199 ty.flags.get().intersects(TypeFlags::HAS_PROJECTION)
1201 pub fn type_has_ty_closure(ty: Ty) -> bool {
1202 ty.flags.get().intersects(TypeFlags::HAS_TY_CLOSURE)
1205 pub fn type_has_erasable_regions(ty: Ty) -> bool {
1206 ty.flags.get().intersects(TypeFlags::HAS_RE_EARLY_BOUND |
1207 TypeFlags::HAS_RE_INFER |
1208 TypeFlags::HAS_FREE_REGIONS)
1211 /// An "escaping region" is a bound region whose binder is not part of `t`.
1213 /// So, for example, consider a type like the following, which has two binders:
1215 /// for<'a> fn(x: for<'b> fn(&'a isize, &'b isize))
1216 /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ outer scope
1217 /// ^~~~~~~~~~~~~~~~~~~~~~~~~~~~ inner scope
1219 /// This type has *bound regions* (`'a`, `'b`), but it does not have escaping regions, because the
1220 /// binders of both `'a` and `'b` are part of the type itself. However, if we consider the *inner
1221 /// fn type*, that type has an escaping region: `'a`.
1223 /// Note that what I'm calling an "escaping region" is often just called a "free region". However,
1224 /// we already use the term "free region". It refers to the regions that we use to represent bound
1225 /// regions on a fn definition while we are typechecking its body.
1227 /// To clarify, conceptually there is no particular difference between an "escaping" region and a
1228 /// "free" region. However, there is a big difference in practice. Basically, when "entering" a
1229 /// binding level, one is generally required to do some sort of processing to a bound region, such
1230 /// as replacing it with a fresh/skolemized region, or making an entry in the environment to
1231 /// represent the scope to which it is attached, etc. An escaping region represents a bound region
1232 /// for which this processing has not yet been done.
1233 pub fn type_has_escaping_regions(ty: Ty) -> bool {
1234 type_escapes_depth(ty, 0)
1237 pub fn type_escapes_depth(ty: Ty, depth: u32) -> bool {
1238 ty.region_depth > depth
1241 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1242 pub struct BareFnTy<'tcx> {
1243 pub unsafety: ast::Unsafety,
1245 pub sig: PolyFnSig<'tcx>,
1248 #[derive(Clone, PartialEq, Eq, Hash)]
1249 pub struct ClosureTy<'tcx> {
1250 pub unsafety: ast::Unsafety,
1252 pub sig: PolyFnSig<'tcx>,
1255 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1256 pub enum FnOutput<'tcx> {
1257 FnConverging(Ty<'tcx>),
1261 impl<'tcx> FnOutput<'tcx> {
1262 pub fn diverges(&self) -> bool {
1263 *self == FnDiverging
1266 pub fn unwrap(self) -> Ty<'tcx> {
1268 ty::FnConverging(t) => t,
1269 ty::FnDiverging => unreachable!()
1273 pub fn unwrap_or(self, def: Ty<'tcx>) -> Ty<'tcx> {
1275 ty::FnConverging(t) => t,
1276 ty::FnDiverging => def
1281 pub type PolyFnOutput<'tcx> = Binder<FnOutput<'tcx>>;
1283 impl<'tcx> PolyFnOutput<'tcx> {
1284 pub fn diverges(&self) -> bool {
1289 /// Signature of a function type, which I have arbitrarily
1290 /// decided to use to refer to the input/output types.
1292 /// - `inputs` is the list of arguments and their modes.
1293 /// - `output` is the return type.
1294 /// - `variadic` indicates whether this is a variadic function. (only true for foreign fns)
1295 #[derive(Clone, PartialEq, Eq, Hash)]
1296 pub struct FnSig<'tcx> {
1297 pub inputs: Vec<Ty<'tcx>>,
1298 pub output: FnOutput<'tcx>,
1302 pub type PolyFnSig<'tcx> = Binder<FnSig<'tcx>>;
1304 impl<'tcx> PolyFnSig<'tcx> {
1305 pub fn inputs(&self) -> ty::Binder<Vec<Ty<'tcx>>> {
1306 self.map_bound_ref(|fn_sig| fn_sig.inputs.clone())
1308 pub fn input(&self, index: usize) -> ty::Binder<Ty<'tcx>> {
1309 self.map_bound_ref(|fn_sig| fn_sig.inputs[index])
1311 pub fn output(&self) -> ty::Binder<FnOutput<'tcx>> {
1312 self.map_bound_ref(|fn_sig| fn_sig.output.clone())
1314 pub fn variadic(&self) -> bool {
1315 self.skip_binder().variadic
1319 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1320 pub struct ParamTy {
1321 pub space: subst::ParamSpace,
1323 pub name: ast::Name,
1326 /// A [De Bruijn index][dbi] is a standard means of representing
1327 /// regions (and perhaps later types) in a higher-ranked setting. In
1328 /// particular, imagine a type like this:
1330 /// for<'a> fn(for<'b> fn(&'b isize, &'a isize), &'a char)
1333 /// | +------------+ 1 | |
1335 /// +--------------------------------+ 2 |
1337 /// +------------------------------------------+ 1
1339 /// In this type, there are two binders (the outer fn and the inner
1340 /// fn). We need to be able to determine, for any given region, which
1341 /// fn type it is bound by, the inner or the outer one. There are
1342 /// various ways you can do this, but a De Bruijn index is one of the
1343 /// more convenient and has some nice properties. The basic idea is to
1344 /// count the number of binders, inside out. Some examples should help
1345 /// clarify what I mean.
1347 /// Let's start with the reference type `&'b isize` that is the first
1348 /// argument to the inner function. This region `'b` is assigned a De
1349 /// Bruijn index of 1, meaning "the innermost binder" (in this case, a
1350 /// fn). The region `'a` that appears in the second argument type (`&'a
1351 /// isize`) would then be assigned a De Bruijn index of 2, meaning "the
1352 /// second-innermost binder". (These indices are written on the arrays
1353 /// in the diagram).
1355 /// What is interesting is that De Bruijn index attached to a particular
1356 /// variable will vary depending on where it appears. For example,
1357 /// the final type `&'a char` also refers to the region `'a` declared on
1358 /// the outermost fn. But this time, this reference is not nested within
1359 /// any other binders (i.e., it is not an argument to the inner fn, but
1360 /// rather the outer one). Therefore, in this case, it is assigned a
1361 /// De Bruijn index of 1, because the innermost binder in that location
1362 /// is the outer fn.
1364 /// [dbi]: http://en.wikipedia.org/wiki/De_Bruijn_index
1365 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug, Copy)]
1366 pub struct DebruijnIndex {
1367 // We maintain the invariant that this is never 0. So 1 indicates
1368 // the innermost binder. To ensure this, create with `DebruijnIndex::new`.
1372 /// Representation of regions:
1373 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Copy)]
1375 // Region bound in a type or fn declaration which will be
1376 // substituted 'early' -- that is, at the same time when type
1377 // parameters are substituted.
1378 ReEarlyBound(EarlyBoundRegion),
1380 // Region bound in a function scope, which will be substituted when the
1381 // function is called.
1382 ReLateBound(DebruijnIndex, BoundRegion),
1384 /// When checking a function body, the types of all arguments and so forth
1385 /// that refer to bound region parameters are modified to refer to free
1386 /// region parameters.
1389 /// A concrete region naming some statically determined extent
1390 /// (e.g. an expression or sequence of statements) within the
1391 /// current function.
1392 ReScope(region::CodeExtent),
1394 /// Static data that has an "infinite" lifetime. Top in the region lattice.
1397 /// A region variable. Should not exist after typeck.
1398 ReInfer(InferRegion),
1400 /// Empty lifetime is for data that is never accessed.
1401 /// Bottom in the region lattice. We treat ReEmpty somewhat
1402 /// specially; at least right now, we do not generate instances of
1403 /// it during the GLB computations, but rather
1404 /// generate an error instead. This is to improve error messages.
1405 /// The only way to get an instance of ReEmpty is to have a region
1406 /// variable with no constraints.
1410 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable, Debug)]
1411 pub struct EarlyBoundRegion {
1412 pub param_id: ast::NodeId,
1413 pub space: subst::ParamSpace,
1415 pub name: ast::Name,
1418 /// Upvars do not get their own node-id. Instead, we use the pair of
1419 /// the original var id (that is, the root variable that is referenced
1420 /// by the upvar) and the id of the closure expression.
1421 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1422 pub struct UpvarId {
1423 pub var_id: ast::NodeId,
1424 pub closure_expr_id: ast::NodeId,
1427 #[derive(Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable, Copy)]
1428 pub enum BorrowKind {
1429 /// Data must be immutable and is aliasable.
1432 /// Data must be immutable but not aliasable. This kind of borrow
1433 /// cannot currently be expressed by the user and is used only in
1434 /// implicit closure bindings. It is needed when you the closure
1435 /// is borrowing or mutating a mutable referent, e.g.:
1437 /// let x: &mut isize = ...;
1438 /// let y = || *x += 5;
1440 /// If we were to try to translate this closure into a more explicit
1441 /// form, we'd encounter an error with the code as written:
1443 /// struct Env { x: & &mut isize }
1444 /// let x: &mut isize = ...;
1445 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
1446 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
1448 /// This is then illegal because you cannot mutate a `&mut` found
1449 /// in an aliasable location. To solve, you'd have to translate with
1450 /// an `&mut` borrow:
1452 /// struct Env { x: & &mut isize }
1453 /// let x: &mut isize = ...;
1454 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
1455 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
1457 /// Now the assignment to `**env.x` is legal, but creating a
1458 /// mutable pointer to `x` is not because `x` is not mutable. We
1459 /// could fix this by declaring `x` as `let mut x`. This is ok in
1460 /// user code, if awkward, but extra weird for closures, since the
1461 /// borrow is hidden.
1463 /// So we introduce a "unique imm" borrow -- the referent is
1464 /// immutable, but not aliasable. This solves the problem. For
1465 /// simplicity, we don't give users the way to express this
1466 /// borrow, it's just used when translating closures.
1469 /// Data is mutable and not aliasable.
1473 /// Information describing the capture of an upvar. This is computed
1474 /// during `typeck`, specifically by `regionck`.
1475 #[derive(PartialEq, Clone, RustcEncodable, RustcDecodable, Debug, Copy)]
1476 pub enum UpvarCapture {
1477 /// Upvar is captured by value. This is always true when the
1478 /// closure is labeled `move`, but can also be true in other cases
1479 /// depending on inference.
1482 /// Upvar is captured by reference.
1486 #[derive(PartialEq, Clone, RustcEncodable, RustcDecodable, Copy)]
1487 pub struct UpvarBorrow {
1488 /// The kind of borrow: by-ref upvars have access to shared
1489 /// immutable borrows, which are not part of the normal language
1491 pub kind: BorrowKind,
1493 /// Region of the resulting reference.
1494 pub region: ty::Region,
1497 pub type UpvarCaptureMap = FnvHashMap<UpvarId, UpvarCapture>;
1500 pub fn is_global(&self) -> bool {
1501 // does this represent a region that can be named in a global
1502 // way? used in fulfillment caching.
1504 ty::ReStatic | ty::ReEmpty => true,
1509 pub fn is_bound(&self) -> bool {
1511 ty::ReEarlyBound(..) => true,
1512 ty::ReLateBound(..) => true,
1517 pub fn escapes_depth(&self, depth: u32) -> bool {
1519 ty::ReLateBound(debruijn, _) => debruijn.depth > depth,
1525 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash,
1526 RustcEncodable, RustcDecodable, Copy)]
1527 /// A "free" region `fr` can be interpreted as "some region
1528 /// at least as big as the scope `fr.scope`".
1529 pub struct FreeRegion {
1530 pub scope: region::DestructionScopeData,
1531 pub bound_region: BoundRegion
1534 #[derive(Clone, PartialEq, PartialOrd, Eq, Ord, Hash,
1535 RustcEncodable, RustcDecodable, Copy, Debug)]
1536 pub enum BoundRegion {
1537 /// An anonymous region parameter for a given fn (&T)
1540 /// Named region parameters for functions (a in &'a T)
1542 /// The def-id is needed to distinguish free regions in
1543 /// the event of shadowing.
1544 BrNamed(ast::DefId, ast::Name),
1546 /// Fresh bound identifiers created during GLB computations.
1549 // Anonymous region for the implicit env pointer parameter
1554 // NB: If you change this, you'll probably want to change the corresponding
1555 // AST structure in libsyntax/ast.rs as well.
1556 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1557 pub enum TypeVariants<'tcx> {
1558 /// The primitive boolean type. Written as `bool`.
1561 /// The primitive character type; holds a Unicode scalar value
1562 /// (a non-surrogate code point). Written as `char`.
1565 /// A primitive signed integer type. For example, `i32`.
1568 /// A primitive unsigned integer type. For example, `u32`.
1569 TyUint(ast::UintTy),
1571 /// A primitive floating-point type. For example, `f64`.
1572 TyFloat(ast::FloatTy),
1574 /// An enumerated type, defined with `enum`.
1576 /// Substs here, possibly against intuition, *may* contain `TyParam`s.
1577 /// That is, even after substitution it is possible that there are type
1578 /// variables. This happens when the `TyEnum` corresponds to an enum
1579 /// definition and not a concrete use of it. To get the correct `TyEnum`
1580 /// from the tcx, use the `NodeId` from the `ast::Ty` and look it up in
1581 /// the `ast_ty_to_ty_cache`. This is probably true for `TyStruct` as
1583 TyEnum(DefId, &'tcx Substs<'tcx>),
1585 /// A structure type, defined with `struct`.
1587 /// See warning about substitutions for enumerated types.
1588 TyStruct(DefId, &'tcx Substs<'tcx>),
1590 /// `Box<T>`; this is nominally a struct in the documentation, but is
1591 /// special-cased internally. For example, it is possible to implicitly
1592 /// move the contents of a box out of that box, and methods of any type
1593 /// can have type `Box<Self>`.
1596 /// The pointee of a string slice. Written as `str`.
1599 /// An array with the given length. Written as `[T; n]`.
1600 TyArray(Ty<'tcx>, usize),
1602 /// The pointee of an array slice. Written as `[T]`.
1605 /// A raw pointer. Written as `*mut T` or `*const T`
1608 /// A reference; a pointer with an associated lifetime. Written as
1609 /// `&a mut T` or `&'a T`.
1610 TyRef(&'tcx Region, mt<'tcx>),
1612 /// If the def-id is Some(_), then this is the type of a specific
1613 /// fn item. Otherwise, if None(_), it a fn pointer type.
1615 /// FIXME: Conflating function pointers and the type of a
1616 /// function is probably a terrible idea; a function pointer is a
1617 /// value with a specific type, but a function can be polymorphic
1618 /// or dynamically dispatched.
1619 TyBareFn(Option<DefId>, &'tcx BareFnTy<'tcx>),
1621 /// A trait, defined with `trait`.
1622 TyTrait(Box<TraitTy<'tcx>>),
1624 /// The anonymous type of a closure. Used to represent the type of
1626 TyClosure(DefId, &'tcx Substs<'tcx>),
1628 /// A tuple type. For example, `(i32, bool)`.
1629 TyTuple(Vec<Ty<'tcx>>),
1631 /// The projection of an associated type. For example,
1632 /// `<T as Trait<..>>::N`.
1633 TyProjection(ProjectionTy<'tcx>),
1635 /// A type parameter; for example, `T` in `fn f<T>(x: T) {}
1638 /// A type variable used during type-checking.
1641 /// A placeholder for a type which could not be computed; this is
1642 /// propagated to avoid useless error messages.
1646 #[derive(Clone, PartialEq, Eq, Hash)]
1647 pub struct TraitTy<'tcx> {
1648 pub principal: ty::PolyTraitRef<'tcx>,
1649 pub bounds: ExistentialBounds<'tcx>,
1652 impl<'tcx> TraitTy<'tcx> {
1653 pub fn principal_def_id(&self) -> ast::DefId {
1654 self.principal.0.def_id
1657 /// Object types don't have a self-type specified. Therefore, when
1658 /// we convert the principal trait-ref into a normal trait-ref,
1659 /// you must give *some* self-type. A common choice is `mk_err()`
1660 /// or some skolemized type.
1661 pub fn principal_trait_ref_with_self_ty(&self,
1664 -> ty::PolyTraitRef<'tcx>
1666 // otherwise the escaping regions would be captured by the binder
1667 assert!(!self_ty.has_escaping_regions());
1669 ty::Binder(TraitRef {
1670 def_id: self.principal.0.def_id,
1671 substs: tcx.mk_substs(self.principal.0.substs.with_self_ty(self_ty)),
1675 pub fn projection_bounds_with_self_ty(&self,
1678 -> Vec<ty::PolyProjectionPredicate<'tcx>>
1680 // otherwise the escaping regions would be captured by the binders
1681 assert!(!self_ty.has_escaping_regions());
1683 self.bounds.projection_bounds.iter()
1684 .map(|in_poly_projection_predicate| {
1685 let in_projection_ty = &in_poly_projection_predicate.0.projection_ty;
1686 let substs = tcx.mk_substs(in_projection_ty.trait_ref.substs.with_self_ty(self_ty));
1687 let trait_ref = ty::TraitRef::new(in_projection_ty.trait_ref.def_id,
1689 let projection_ty = ty::ProjectionTy {
1690 trait_ref: trait_ref,
1691 item_name: in_projection_ty.item_name
1693 ty::Binder(ty::ProjectionPredicate {
1694 projection_ty: projection_ty,
1695 ty: in_poly_projection_predicate.0.ty
1702 /// A complete reference to a trait. These take numerous guises in syntax,
1703 /// but perhaps the most recognizable form is in a where clause:
1707 /// This would be represented by a trait-reference where the def-id is the
1708 /// def-id for the trait `Foo` and the substs defines `T` as parameter 0 in the
1709 /// `SelfSpace` and `U` as parameter 0 in the `TypeSpace`.
1711 /// Trait references also appear in object types like `Foo<U>`, but in
1712 /// that case the `Self` parameter is absent from the substitutions.
1714 /// Note that a `TraitRef` introduces a level of region binding, to
1715 /// account for higher-ranked trait bounds like `T : for<'a> Foo<&'a
1716 /// U>` or higher-ranked object types.
1717 #[derive(Copy, Clone, PartialEq, Eq, Hash)]
1718 pub struct TraitRef<'tcx> {
1720 pub substs: &'tcx Substs<'tcx>,
1723 pub type PolyTraitRef<'tcx> = Binder<TraitRef<'tcx>>;
1725 impl<'tcx> PolyTraitRef<'tcx> {
1726 pub fn self_ty(&self) -> Ty<'tcx> {
1730 pub fn def_id(&self) -> ast::DefId {
1734 pub fn substs(&self) -> &'tcx Substs<'tcx> {
1735 // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
1739 pub fn input_types(&self) -> &[Ty<'tcx>] {
1740 // FIXME(#20664) every use of this fn is probably a bug, it should yield Binder<>
1741 self.0.input_types()
1744 pub fn to_poly_trait_predicate(&self) -> PolyTraitPredicate<'tcx> {
1745 // Note that we preserve binding levels
1746 Binder(TraitPredicate { trait_ref: self.0.clone() })
1750 /// Binder is a binder for higher-ranked lifetimes. It is part of the
1751 /// compiler's representation for things like `for<'a> Fn(&'a isize)`
1752 /// (which would be represented by the type `PolyTraitRef ==
1753 /// Binder<TraitRef>`). Note that when we skolemize, instantiate,
1754 /// erase, or otherwise "discharge" these bound regions, we change the
1755 /// type from `Binder<T>` to just `T` (see
1756 /// e.g. `liberate_late_bound_regions`).
1757 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
1758 pub struct Binder<T>(pub T);
1761 /// Skips the binder and returns the "bound" value. This is a
1762 /// risky thing to do because it's easy to get confused about
1763 /// debruijn indices and the like. It is usually better to
1764 /// discharge the binder using `no_late_bound_regions` or
1765 /// `replace_late_bound_regions` or something like
1766 /// that. `skip_binder` is only valid when you are either
1767 /// extracting data that has nothing to do with bound regions, you
1768 /// are doing some sort of test that does not involve bound
1769 /// regions, or you are being very careful about your depth
1772 /// Some examples where `skip_binder` is reasonable:
1773 /// - extracting the def-id from a PolyTraitRef;
1774 /// - comparing the self type of a PolyTraitRef to see if it is equal to
1775 /// a type parameter `X`, since the type `X` does not reference any regions
1776 pub fn skip_binder(&self) -> &T {
1780 pub fn as_ref(&self) -> Binder<&T> {
1784 pub fn map_bound_ref<F,U>(&self, f: F) -> Binder<U>
1785 where F: FnOnce(&T) -> U
1787 self.as_ref().map_bound(f)
1790 pub fn map_bound<F,U>(self, f: F) -> Binder<U>
1791 where F: FnOnce(T) -> U
1793 ty::Binder(f(self.0))
1797 #[derive(Clone, Copy, PartialEq)]
1798 pub enum IntVarValue {
1799 IntType(ast::IntTy),
1800 UintType(ast::UintTy),
1803 #[derive(Clone, Copy, Debug)]
1804 pub enum terr_vstore_kind {
1811 #[derive(Clone, Copy, Debug)]
1812 pub struct expected_found<T> {
1817 // Data structures used in type unification
1818 #[derive(Clone, Copy, Debug)]
1819 pub enum type_err<'tcx> {
1821 terr_unsafety_mismatch(expected_found<ast::Unsafety>),
1822 terr_abi_mismatch(expected_found<abi::Abi>),
1824 terr_box_mutability,
1825 terr_ptr_mutability,
1826 terr_ref_mutability,
1827 terr_vec_mutability,
1828 terr_tuple_size(expected_found<usize>),
1829 terr_fixed_array_size(expected_found<usize>),
1830 terr_ty_param_size(expected_found<usize>),
1832 terr_regions_does_not_outlive(Region, Region),
1833 terr_regions_not_same(Region, Region),
1834 terr_regions_no_overlap(Region, Region),
1835 terr_regions_insufficiently_polymorphic(BoundRegion, Region),
1836 terr_regions_overly_polymorphic(BoundRegion, Region),
1837 terr_sorts(expected_found<Ty<'tcx>>),
1838 terr_integer_as_char,
1839 terr_int_mismatch(expected_found<IntVarValue>),
1840 terr_float_mismatch(expected_found<ast::FloatTy>),
1841 terr_traits(expected_found<ast::DefId>),
1842 terr_builtin_bounds(expected_found<BuiltinBounds>),
1843 terr_variadic_mismatch(expected_found<bool>),
1845 terr_convergence_mismatch(expected_found<bool>),
1846 terr_projection_name_mismatched(expected_found<ast::Name>),
1847 terr_projection_bounds_length(expected_found<usize>),
1850 /// Bounds suitable for a named type parameter like `A` in `fn foo<A>`
1851 /// as well as the existential type parameter in an object type.
1852 #[derive(PartialEq, Eq, Hash, Clone)]
1853 pub struct ParamBounds<'tcx> {
1854 pub region_bounds: Vec<ty::Region>,
1855 pub builtin_bounds: BuiltinBounds,
1856 pub trait_bounds: Vec<PolyTraitRef<'tcx>>,
1857 pub projection_bounds: Vec<PolyProjectionPredicate<'tcx>>,
1860 /// Bounds suitable for an existentially quantified type parameter
1861 /// such as those that appear in object types or closure types. The
1862 /// major difference between this case and `ParamBounds` is that
1863 /// general purpose trait bounds are omitted and there must be
1864 /// *exactly one* region.
1865 #[derive(PartialEq, Eq, Hash, Clone)]
1866 pub struct ExistentialBounds<'tcx> {
1867 pub region_bound: ty::Region,
1868 pub builtin_bounds: BuiltinBounds,
1869 pub projection_bounds: Vec<PolyProjectionPredicate<'tcx>>,
1872 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
1873 pub struct BuiltinBounds(EnumSet<BuiltinBound>);
1875 impl BuiltinBounds {
1876 pub fn empty() -> BuiltinBounds {
1877 BuiltinBounds(EnumSet::new())
1880 pub fn iter(&self) -> enum_set::Iter<BuiltinBound> {
1885 impl ops::Deref for BuiltinBounds {
1886 type Target = EnumSet<BuiltinBound>;
1887 fn deref(&self) -> &Self::Target { &self.0 }
1890 impl ops::DerefMut for BuiltinBounds {
1891 fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 }
1894 impl<'a> IntoIterator for &'a BuiltinBounds {
1895 type Item = BuiltinBound;
1896 type IntoIter = enum_set::Iter<BuiltinBound>;
1897 fn into_iter(self) -> Self::IntoIter {
1898 (**self).into_iter()
1902 #[derive(Clone, RustcEncodable, PartialEq, Eq, RustcDecodable, Hash,
1905 pub enum BuiltinBound {
1912 /// An existential bound that does not implement any traits.
1913 pub fn region_existential_bound<'tcx>(r: ty::Region) -> ExistentialBounds<'tcx> {
1914 ty::ExistentialBounds { region_bound: r,
1915 builtin_bounds: BuiltinBounds::empty(),
1916 projection_bounds: Vec::new() }
1919 impl CLike for BuiltinBound {
1920 fn to_usize(&self) -> usize {
1923 fn from_usize(v: usize) -> BuiltinBound {
1924 unsafe { mem::transmute(v) }
1928 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1933 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1938 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1939 pub struct FloatVid {
1943 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1944 pub struct RegionVid {
1948 #[derive(Clone, Copy, PartialEq, Eq, Hash)]
1954 /// A `FreshTy` is one that is generated as a replacement for an
1955 /// unbound type variable. This is convenient for caching etc. See
1956 /// `middle::infer::freshen` for more details.
1962 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Eq, Hash, Debug, Copy)]
1963 pub enum UnconstrainedNumeric {
1970 #[derive(Clone, RustcEncodable, RustcDecodable, Eq, Hash, Debug, Copy)]
1971 pub enum InferRegion {
1973 ReSkolemized(u32, BoundRegion)
1976 impl cmp::PartialEq for InferRegion {
1977 fn eq(&self, other: &InferRegion) -> bool {
1978 match ((*self), *other) {
1979 (ReVar(rva), ReVar(rvb)) => {
1982 (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
1988 fn ne(&self, other: &InferRegion) -> bool {
1989 !((*self) == (*other))
1993 impl fmt::Debug for TyVid {
1994 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1995 write!(f, "_#{}t", self.index)
1999 impl fmt::Debug for IntVid {
2000 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2001 write!(f, "_#{}i", self.index)
2005 impl fmt::Debug for FloatVid {
2006 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2007 write!(f, "_#{}f", self.index)
2011 impl fmt::Debug for RegionVid {
2012 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2013 write!(f, "'_#{}r", self.index)
2017 impl<'tcx> fmt::Debug for FnSig<'tcx> {
2018 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2019 write!(f, "({:?}; variadic: {})->{:?}", self.inputs, self.variadic, self.output)
2023 impl fmt::Debug for InferTy {
2024 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2026 TyVar(ref v) => v.fmt(f),
2027 IntVar(ref v) => v.fmt(f),
2028 FloatVar(ref v) => v.fmt(f),
2029 FreshTy(v) => write!(f, "FreshTy({:?})", v),
2030 FreshIntTy(v) => write!(f, "FreshIntTy({:?})", v),
2031 FreshFloatTy(v) => write!(f, "FreshFloatTy({:?})", v)
2036 impl fmt::Debug for IntVarValue {
2037 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2039 IntType(ref v) => v.fmt(f),
2040 UintType(ref v) => v.fmt(f),
2045 /// Default region to use for the bound of objects that are
2046 /// supplied as the value for this type parameter. This is derived
2047 /// from `T:'a` annotations appearing in the type definition. If
2048 /// this is `None`, then the default is inherited from the
2049 /// surrounding context. See RFC #599 for details.
2050 #[derive(Copy, Clone)]
2051 pub enum ObjectLifetimeDefault {
2052 /// Require an explicit annotation. Occurs when multiple
2053 /// `T:'a` constraints are found.
2056 /// Use the given region as the default.
2061 pub struct TypeParameterDef<'tcx> {
2062 pub name: ast::Name,
2063 pub def_id: ast::DefId,
2064 pub space: subst::ParamSpace,
2066 pub default: Option<Ty<'tcx>>,
2067 pub object_lifetime_default: Option<ObjectLifetimeDefault>,
2070 #[derive(RustcEncodable, RustcDecodable, Clone, Debug)]
2071 pub struct RegionParameterDef {
2072 pub name: ast::Name,
2073 pub def_id: ast::DefId,
2074 pub space: subst::ParamSpace,
2076 pub bounds: Vec<ty::Region>,
2079 impl RegionParameterDef {
2080 pub fn to_early_bound_region(&self) -> ty::Region {
2081 ty::ReEarlyBound(ty::EarlyBoundRegion {
2082 param_id: self.def_id.node,
2088 pub fn to_bound_region(&self) -> ty::BoundRegion {
2089 ty::BoundRegion::BrNamed(self.def_id, self.name)
2093 /// Information about the formal type/lifetime parameters associated
2094 /// with an item or method. Analogous to ast::Generics.
2095 #[derive(Clone, Debug)]
2096 pub struct Generics<'tcx> {
2097 pub types: VecPerParamSpace<TypeParameterDef<'tcx>>,
2098 pub regions: VecPerParamSpace<RegionParameterDef>,
2101 impl<'tcx> Generics<'tcx> {
2102 pub fn empty() -> Generics<'tcx> {
2104 types: VecPerParamSpace::empty(),
2105 regions: VecPerParamSpace::empty(),
2109 pub fn is_empty(&self) -> bool {
2110 self.types.is_empty() && self.regions.is_empty()
2113 pub fn has_type_params(&self, space: subst::ParamSpace) -> bool {
2114 !self.types.is_empty_in(space)
2117 pub fn has_region_params(&self, space: subst::ParamSpace) -> bool {
2118 !self.regions.is_empty_in(space)
2122 /// Bounds on generics.
2124 pub struct GenericPredicates<'tcx> {
2125 pub predicates: VecPerParamSpace<Predicate<'tcx>>,
2128 impl<'tcx> GenericPredicates<'tcx> {
2129 pub fn empty() -> GenericPredicates<'tcx> {
2131 predicates: VecPerParamSpace::empty(),
2135 pub fn instantiate(&self, tcx: &ty::ctxt<'tcx>, substs: &Substs<'tcx>)
2136 -> InstantiatedPredicates<'tcx> {
2137 InstantiatedPredicates {
2138 predicates: self.predicates.subst(tcx, substs),
2142 pub fn instantiate_supertrait(&self,
2143 tcx: &ty::ctxt<'tcx>,
2144 poly_trait_ref: &ty::PolyTraitRef<'tcx>)
2145 -> InstantiatedPredicates<'tcx>
2147 InstantiatedPredicates {
2148 predicates: self.predicates.map(|pred| pred.subst_supertrait(tcx, poly_trait_ref))
2153 #[derive(Clone, PartialEq, Eq, Hash)]
2154 pub enum Predicate<'tcx> {
2155 /// Corresponds to `where Foo : Bar<A,B,C>`. `Foo` here would be
2156 /// the `Self` type of the trait reference and `A`, `B`, and `C`
2157 /// would be the parameters in the `TypeSpace`.
2158 Trait(PolyTraitPredicate<'tcx>),
2160 /// where `T1 == T2`.
2161 Equate(PolyEquatePredicate<'tcx>),
2164 RegionOutlives(PolyRegionOutlivesPredicate),
2167 TypeOutlives(PolyTypeOutlivesPredicate<'tcx>),
2169 /// where <T as TraitRef>::Name == X, approximately.
2170 /// See `ProjectionPredicate` struct for details.
2171 Projection(PolyProjectionPredicate<'tcx>),
2174 impl<'tcx> Predicate<'tcx> {
2175 /// Performs a substitution suitable for going from a
2176 /// poly-trait-ref to supertraits that must hold if that
2177 /// poly-trait-ref holds. This is slightly different from a normal
2178 /// substitution in terms of what happens with bound regions. See
2179 /// lengthy comment below for details.
2180 pub fn subst_supertrait(&self,
2181 tcx: &ty::ctxt<'tcx>,
2182 trait_ref: &ty::PolyTraitRef<'tcx>)
2183 -> ty::Predicate<'tcx>
2185 // The interaction between HRTB and supertraits is not entirely
2186 // obvious. Let me walk you (and myself) through an example.
2188 // Let's start with an easy case. Consider two traits:
2190 // trait Foo<'a> : Bar<'a,'a> { }
2191 // trait Bar<'b,'c> { }
2193 // Now, if we have a trait reference `for<'x> T : Foo<'x>`, then
2194 // we can deduce that `for<'x> T : Bar<'x,'x>`. Basically, if we
2195 // knew that `Foo<'x>` (for any 'x) then we also know that
2196 // `Bar<'x,'x>` (for any 'x). This more-or-less falls out from
2197 // normal substitution.
2199 // In terms of why this is sound, the idea is that whenever there
2200 // is an impl of `T:Foo<'a>`, it must show that `T:Bar<'a,'a>`
2201 // holds. So if there is an impl of `T:Foo<'a>` that applies to
2202 // all `'a`, then we must know that `T:Bar<'a,'a>` holds for all
2205 // Another example to be careful of is this:
2207 // trait Foo1<'a> : for<'b> Bar1<'a,'b> { }
2208 // trait Bar1<'b,'c> { }
2210 // Here, if we have `for<'x> T : Foo1<'x>`, then what do we know?
2211 // The answer is that we know `for<'x,'b> T : Bar1<'x,'b>`. The
2212 // reason is similar to the previous example: any impl of
2213 // `T:Foo1<'x>` must show that `for<'b> T : Bar1<'x, 'b>`. So
2214 // basically we would want to collapse the bound lifetimes from
2215 // the input (`trait_ref`) and the supertraits.
2217 // To achieve this in practice is fairly straightforward. Let's
2218 // consider the more complicated scenario:
2220 // - We start out with `for<'x> T : Foo1<'x>`. In this case, `'x`
2221 // has a De Bruijn index of 1. We want to produce `for<'x,'b> T : Bar1<'x,'b>`,
2222 // where both `'x` and `'b` would have a DB index of 1.
2223 // The substitution from the input trait-ref is therefore going to be
2224 // `'a => 'x` (where `'x` has a DB index of 1).
2225 // - The super-trait-ref is `for<'b> Bar1<'a,'b>`, where `'a` is an
2226 // early-bound parameter and `'b' is a late-bound parameter with a
2228 // - If we replace `'a` with `'x` from the input, it too will have
2229 // a DB index of 1, and thus we'll have `for<'x,'b> Bar1<'x,'b>`
2230 // just as we wanted.
2232 // There is only one catch. If we just apply the substitution `'a
2233 // => 'x` to `for<'b> Bar1<'a,'b>`, the substitution code will
2234 // adjust the DB index because we substituting into a binder (it
2235 // tries to be so smart...) resulting in `for<'x> for<'b>
2236 // Bar1<'x,'b>` (we have no syntax for this, so use your
2237 // imagination). Basically the 'x will have DB index of 2 and 'b
2238 // will have DB index of 1. Not quite what we want. So we apply
2239 // the substitution to the *contents* of the trait reference,
2240 // rather than the trait reference itself (put another way, the
2241 // substitution code expects equal binding levels in the values
2242 // from the substitution and the value being substituted into, and
2243 // this trick achieves that).
2245 let substs = &trait_ref.0.substs;
2247 Predicate::Trait(ty::Binder(ref data)) =>
2248 Predicate::Trait(ty::Binder(data.subst(tcx, substs))),
2249 Predicate::Equate(ty::Binder(ref data)) =>
2250 Predicate::Equate(ty::Binder(data.subst(tcx, substs))),
2251 Predicate::RegionOutlives(ty::Binder(ref data)) =>
2252 Predicate::RegionOutlives(ty::Binder(data.subst(tcx, substs))),
2253 Predicate::TypeOutlives(ty::Binder(ref data)) =>
2254 Predicate::TypeOutlives(ty::Binder(data.subst(tcx, substs))),
2255 Predicate::Projection(ty::Binder(ref data)) =>
2256 Predicate::Projection(ty::Binder(data.subst(tcx, substs))),
2260 // Indicates whether this predicate references only 'global'
2261 // types/lifetimes that are the same regardless of what fn we are
2262 // in. This is used for caching. Errs on the side of returning
2264 pub fn is_global(&self) -> bool {
2266 ty::Predicate::Trait(ref data) => {
2267 let substs = data.skip_binder().trait_ref.substs;
2269 substs.types.iter().all(|t| ty::type_is_global(t)) && {
2270 match substs.regions {
2271 subst::ErasedRegions => true,
2272 subst::NonerasedRegions(ref r) => r.iter().all(|r| r.is_global()),
2284 #[derive(Clone, PartialEq, Eq, Hash)]
2285 pub struct TraitPredicate<'tcx> {
2286 pub trait_ref: TraitRef<'tcx>
2288 pub type PolyTraitPredicate<'tcx> = ty::Binder<TraitPredicate<'tcx>>;
2290 impl<'tcx> TraitPredicate<'tcx> {
2291 pub fn def_id(&self) -> ast::DefId {
2292 self.trait_ref.def_id
2295 pub fn input_types(&self) -> &[Ty<'tcx>] {
2296 self.trait_ref.substs.types.as_slice()
2299 pub fn self_ty(&self) -> Ty<'tcx> {
2300 self.trait_ref.self_ty()
2304 impl<'tcx> PolyTraitPredicate<'tcx> {
2305 pub fn def_id(&self) -> ast::DefId {
2310 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2311 pub struct EquatePredicate<'tcx>(pub Ty<'tcx>, pub Ty<'tcx>); // `0 == 1`
2312 pub type PolyEquatePredicate<'tcx> = ty::Binder<EquatePredicate<'tcx>>;
2314 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2315 pub struct OutlivesPredicate<A,B>(pub A, pub B); // `A : B`
2316 pub type PolyOutlivesPredicate<A,B> = ty::Binder<OutlivesPredicate<A,B>>;
2317 pub type PolyRegionOutlivesPredicate = PolyOutlivesPredicate<ty::Region, ty::Region>;
2318 pub type PolyTypeOutlivesPredicate<'tcx> = PolyOutlivesPredicate<Ty<'tcx>, ty::Region>;
2320 /// This kind of predicate has no *direct* correspondent in the
2321 /// syntax, but it roughly corresponds to the syntactic forms:
2323 /// 1. `T : TraitRef<..., Item=Type>`
2324 /// 2. `<T as TraitRef<...>>::Item == Type` (NYI)
2326 /// In particular, form #1 is "desugared" to the combination of a
2327 /// normal trait predicate (`T : TraitRef<...>`) and one of these
2328 /// predicates. Form #2 is a broader form in that it also permits
2329 /// equality between arbitrary types. Processing an instance of Form
2330 /// #2 eventually yields one of these `ProjectionPredicate`
2331 /// instances to normalize the LHS.
2332 #[derive(Clone, PartialEq, Eq, Hash)]
2333 pub struct ProjectionPredicate<'tcx> {
2334 pub projection_ty: ProjectionTy<'tcx>,
2338 pub type PolyProjectionPredicate<'tcx> = Binder<ProjectionPredicate<'tcx>>;
2340 impl<'tcx> PolyProjectionPredicate<'tcx> {
2341 pub fn item_name(&self) -> ast::Name {
2342 self.0.projection_ty.item_name // safe to skip the binder to access a name
2345 pub fn sort_key(&self) -> (ast::DefId, ast::Name) {
2346 self.0.projection_ty.sort_key()
2350 /// Represents the projection of an associated type. In explicit UFCS
2351 /// form this would be written `<T as Trait<..>>::N`.
2352 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
2353 pub struct ProjectionTy<'tcx> {
2354 /// The trait reference `T as Trait<..>`.
2355 pub trait_ref: ty::TraitRef<'tcx>,
2357 /// The name `N` of the associated type.
2358 pub item_name: ast::Name,
2361 impl<'tcx> ProjectionTy<'tcx> {
2362 pub fn sort_key(&self) -> (ast::DefId, ast::Name) {
2363 (self.trait_ref.def_id, self.item_name)
2367 pub trait ToPolyTraitRef<'tcx> {
2368 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>;
2371 impl<'tcx> ToPolyTraitRef<'tcx> for TraitRef<'tcx> {
2372 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2373 assert!(!self.has_escaping_regions());
2374 ty::Binder(self.clone())
2378 impl<'tcx> ToPolyTraitRef<'tcx> for PolyTraitPredicate<'tcx> {
2379 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2380 self.map_bound_ref(|trait_pred| trait_pred.trait_ref.clone())
2384 impl<'tcx> ToPolyTraitRef<'tcx> for PolyProjectionPredicate<'tcx> {
2385 fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> {
2386 // Note: unlike with TraitRef::to_poly_trait_ref(),
2387 // self.0.trait_ref is permitted to have escaping regions.
2388 // This is because here `self` has a `Binder` and so does our
2389 // return value, so we are preserving the number of binding
2391 ty::Binder(self.0.projection_ty.trait_ref.clone())
2395 pub trait AsPredicate<'tcx> {
2396 fn as_predicate(&self) -> Predicate<'tcx>;
2399 impl<'tcx> AsPredicate<'tcx> for TraitRef<'tcx> {
2400 fn as_predicate(&self) -> Predicate<'tcx> {
2401 // we're about to add a binder, so let's check that we don't
2402 // accidentally capture anything, or else that might be some
2403 // weird debruijn accounting.
2404 assert!(!self.has_escaping_regions());
2406 ty::Predicate::Trait(ty::Binder(ty::TraitPredicate {
2407 trait_ref: self.clone()
2412 impl<'tcx> AsPredicate<'tcx> for PolyTraitRef<'tcx> {
2413 fn as_predicate(&self) -> Predicate<'tcx> {
2414 ty::Predicate::Trait(self.to_poly_trait_predicate())
2418 impl<'tcx> AsPredicate<'tcx> for PolyEquatePredicate<'tcx> {
2419 fn as_predicate(&self) -> Predicate<'tcx> {
2420 Predicate::Equate(self.clone())
2424 impl<'tcx> AsPredicate<'tcx> for PolyRegionOutlivesPredicate {
2425 fn as_predicate(&self) -> Predicate<'tcx> {
2426 Predicate::RegionOutlives(self.clone())
2430 impl<'tcx> AsPredicate<'tcx> for PolyTypeOutlivesPredicate<'tcx> {
2431 fn as_predicate(&self) -> Predicate<'tcx> {
2432 Predicate::TypeOutlives(self.clone())
2436 impl<'tcx> AsPredicate<'tcx> for PolyProjectionPredicate<'tcx> {
2437 fn as_predicate(&self) -> Predicate<'tcx> {
2438 Predicate::Projection(self.clone())
2442 impl<'tcx> Predicate<'tcx> {
2443 /// Iterates over the types in this predicate. Note that in all
2444 /// cases this is skipping over a binder, so late-bound regions
2445 /// with depth 0 are bound by the predicate.
2446 pub fn walk_tys(&self) -> IntoIter<Ty<'tcx>> {
2447 let vec: Vec<_> = match *self {
2448 ty::Predicate::Trait(ref data) => {
2449 data.0.trait_ref.substs.types.as_slice().to_vec()
2451 ty::Predicate::Equate(ty::Binder(ref data)) => {
2452 vec![data.0, data.1]
2454 ty::Predicate::TypeOutlives(ty::Binder(ref data)) => {
2457 ty::Predicate::RegionOutlives(..) => {
2460 ty::Predicate::Projection(ref data) => {
2461 let trait_inputs = data.0.projection_ty.trait_ref.substs.types.as_slice();
2464 .chain(Some(data.0.ty))
2469 // The only reason to collect into a vector here is that I was
2470 // too lazy to make the full (somewhat complicated) iterator
2471 // type that would be needed here. But I wanted this fn to
2472 // return an iterator conceptually, rather than a `Vec`, so as
2473 // to be closer to `Ty::walk`.
2477 pub fn has_escaping_regions(&self) -> bool {
2479 Predicate::Trait(ref trait_ref) => trait_ref.has_escaping_regions(),
2480 Predicate::Equate(ref p) => p.has_escaping_regions(),
2481 Predicate::RegionOutlives(ref p) => p.has_escaping_regions(),
2482 Predicate::TypeOutlives(ref p) => p.has_escaping_regions(),
2483 Predicate::Projection(ref p) => p.has_escaping_regions(),
2487 pub fn to_opt_poly_trait_ref(&self) -> Option<PolyTraitRef<'tcx>> {
2489 Predicate::Trait(ref t) => {
2490 Some(t.to_poly_trait_ref())
2492 Predicate::Projection(..) |
2493 Predicate::Equate(..) |
2494 Predicate::RegionOutlives(..) |
2495 Predicate::TypeOutlives(..) => {
2502 /// Represents the bounds declared on a particular set of type
2503 /// parameters. Should eventually be generalized into a flag list of
2504 /// where clauses. You can obtain a `InstantiatedPredicates` list from a
2505 /// `GenericPredicates` by using the `instantiate` method. Note that this method
2506 /// reflects an important semantic invariant of `InstantiatedPredicates`: while
2507 /// the `GenericPredicates` are expressed in terms of the bound type
2508 /// parameters of the impl/trait/whatever, an `InstantiatedPredicates` instance
2509 /// represented a set of bounds for some particular instantiation,
2510 /// meaning that the generic parameters have been substituted with
2515 /// struct Foo<T,U:Bar<T>> { ... }
2517 /// Here, the `GenericPredicates` for `Foo` would contain a list of bounds like
2518 /// `[[], [U:Bar<T>]]`. Now if there were some particular reference
2519 /// like `Foo<isize,usize>`, then the `InstantiatedPredicates` would be `[[],
2520 /// [usize:Bar<isize>]]`.
2522 pub struct InstantiatedPredicates<'tcx> {
2523 pub predicates: VecPerParamSpace<Predicate<'tcx>>,
2526 impl<'tcx> InstantiatedPredicates<'tcx> {
2527 pub fn empty() -> InstantiatedPredicates<'tcx> {
2528 InstantiatedPredicates { predicates: VecPerParamSpace::empty() }
2531 pub fn has_escaping_regions(&self) -> bool {
2532 self.predicates.any(|p| p.has_escaping_regions())
2535 pub fn is_empty(&self) -> bool {
2536 self.predicates.is_empty()
2540 impl<'tcx> TraitRef<'tcx> {
2541 pub fn new(def_id: ast::DefId, substs: &'tcx Substs<'tcx>) -> TraitRef<'tcx> {
2542 TraitRef { def_id: def_id, substs: substs }
2545 pub fn self_ty(&self) -> Ty<'tcx> {
2546 self.substs.self_ty().unwrap()
2549 pub fn input_types(&self) -> &[Ty<'tcx>] {
2550 // Select only the "input types" from a trait-reference. For
2551 // now this is all the types that appear in the
2552 // trait-reference, but it should eventually exclude
2553 // associated types.
2554 self.substs.types.as_slice()
2558 /// When type checking, we use the `ParameterEnvironment` to track
2559 /// details about the type/lifetime parameters that are in scope.
2560 /// It primarily stores the bounds information.
2562 /// Note: This information might seem to be redundant with the data in
2563 /// `tcx.ty_param_defs`, but it is not. That table contains the
2564 /// parameter definitions from an "outside" perspective, but this
2565 /// struct will contain the bounds for a parameter as seen from inside
2566 /// the function body. Currently the only real distinction is that
2567 /// bound lifetime parameters are replaced with free ones, but in the
2568 /// future I hope to refine the representation of types so as to make
2569 /// more distinctions clearer.
2571 pub struct ParameterEnvironment<'a, 'tcx:'a> {
2572 pub tcx: &'a ctxt<'tcx>,
2574 /// See `construct_free_substs` for details.
2575 pub free_substs: Substs<'tcx>,
2577 /// Each type parameter has an implicit region bound that
2578 /// indicates it must outlive at least the function body (the user
2579 /// may specify stronger requirements). This field indicates the
2580 /// region of the callee.
2581 pub implicit_region_bound: ty::Region,
2583 /// Obligations that the caller must satisfy. This is basically
2584 /// the set of bounds on the in-scope type parameters, translated
2585 /// into Obligations, and elaborated and normalized.
2586 pub caller_bounds: Vec<ty::Predicate<'tcx>>,
2588 /// Caches the results of trait selection. This cache is used
2589 /// for things that have to do with the parameters in scope.
2590 pub selection_cache: traits::SelectionCache<'tcx>,
2593 impl<'a, 'tcx> ParameterEnvironment<'a, 'tcx> {
2594 pub fn with_caller_bounds(&self,
2595 caller_bounds: Vec<ty::Predicate<'tcx>>)
2596 -> ParameterEnvironment<'a,'tcx>
2598 ParameterEnvironment {
2600 free_substs: self.free_substs.clone(),
2601 implicit_region_bound: self.implicit_region_bound,
2602 caller_bounds: caller_bounds,
2603 selection_cache: traits::SelectionCache::new(),
2607 pub fn for_item(cx: &'a ctxt<'tcx>, id: NodeId) -> ParameterEnvironment<'a, 'tcx> {
2608 match cx.map.find(id) {
2609 Some(ast_map::NodeImplItem(ref impl_item)) => {
2610 match impl_item.node {
2611 ast::ConstImplItem(_, _) => {
2612 let def_id = ast_util::local_def(id);
2613 let scheme = lookup_item_type(cx, def_id);
2614 let predicates = lookup_predicates(cx, def_id);
2615 construct_parameter_environment(cx,
2621 ast::MethodImplItem(_, ref body) => {
2622 let method_def_id = ast_util::local_def(id);
2623 match ty::impl_or_trait_item(cx, method_def_id) {
2624 MethodTraitItem(ref method_ty) => {
2625 let method_generics = &method_ty.generics;
2626 let method_bounds = &method_ty.predicates;
2627 construct_parameter_environment(
2636 .bug("ParameterEnvironment::for_item(): \
2637 got non-method item from impl method?!")
2641 ast::TypeImplItem(_) => {
2642 cx.sess.bug("ParameterEnvironment::for_item(): \
2643 can't create a parameter environment \
2644 for type impl items")
2646 ast::MacImplItem(_) => cx.sess.bug("unexpanded macro")
2649 Some(ast_map::NodeTraitItem(trait_item)) => {
2650 match trait_item.node {
2651 ast::ConstTraitItem(_, ref default) => {
2654 let def_id = ast_util::local_def(id);
2655 let scheme = lookup_item_type(cx, def_id);
2656 let predicates = lookup_predicates(cx, def_id);
2657 construct_parameter_environment(cx,
2664 cx.sess.bug("ParameterEnvironment::from_item(): \
2665 can't create a parameter environment \
2666 for const trait items without defaults")
2670 ast::MethodTraitItem(_, None) => {
2671 cx.sess.span_bug(trait_item.span,
2672 "ParameterEnvironment::for_item():
2673 can't create a parameter \
2674 environment for required trait \
2677 ast::MethodTraitItem(_, Some(ref body)) => {
2678 let method_def_id = ast_util::local_def(id);
2679 match ty::impl_or_trait_item(cx, method_def_id) {
2680 MethodTraitItem(ref method_ty) => {
2681 let method_generics = &method_ty.generics;
2682 let method_bounds = &method_ty.predicates;
2683 construct_parameter_environment(
2692 .bug("ParameterEnvironment::for_item(): \
2693 got non-method item from provided \
2698 ast::TypeTraitItem(..) => {
2699 cx.sess.bug("ParameterEnvironment::from_item(): \
2700 can't create a parameter environment \
2701 for type trait items")
2705 Some(ast_map::NodeItem(item)) => {
2707 ast::ItemFn(_, _, _, _, _, ref body) => {
2708 // We assume this is a function.
2709 let fn_def_id = ast_util::local_def(id);
2710 let fn_scheme = lookup_item_type(cx, fn_def_id);
2711 let fn_predicates = lookup_predicates(cx, fn_def_id);
2713 construct_parameter_environment(cx,
2715 &fn_scheme.generics,
2720 ast::ItemStruct(..) |
2722 ast::ItemConst(..) |
2723 ast::ItemStatic(..) => {
2724 let def_id = ast_util::local_def(id);
2725 let scheme = lookup_item_type(cx, def_id);
2726 let predicates = lookup_predicates(cx, def_id);
2727 construct_parameter_environment(cx,
2734 cx.sess.span_bug(item.span,
2735 "ParameterEnvironment::from_item():
2736 can't create a parameter \
2737 environment for this kind of item")
2741 Some(ast_map::NodeExpr(..)) => {
2742 // This is a convenience to allow closures to work.
2743 ParameterEnvironment::for_item(cx, cx.map.get_parent(id))
2746 cx.sess.bug(&format!("ParameterEnvironment::from_item(): \
2747 `{}` is not an item",
2748 cx.map.node_to_string(id)))
2754 /// A "type scheme", in ML terminology, is a type combined with some
2755 /// set of generic types that the type is, well, generic over. In Rust
2756 /// terms, it is the "type" of a fn item or struct -- this type will
2757 /// include various generic parameters that must be substituted when
2758 /// the item/struct is referenced. That is called converting the type
2759 /// scheme to a monotype.
2761 /// - `generics`: the set of type parameters and their bounds
2762 /// - `ty`: the base types, which may reference the parameters defined
2765 /// Note that TypeSchemes are also sometimes called "polytypes" (and
2766 /// in fact this struct used to carry that name, so you may find some
2767 /// stray references in a comment or something). We try to reserve the
2768 /// "poly" prefix to refer to higher-ranked things, as in
2771 /// Note that each item also comes with predicates, see
2772 /// `lookup_predicates`.
2773 #[derive(Clone, Debug)]
2774 pub struct TypeScheme<'tcx> {
2775 pub generics: Generics<'tcx>,
2780 flags TraitFlags: u32 {
2781 const NO_TRAIT_FLAGS = 0,
2782 const HAS_DEFAULT_IMPL = 1 << 0,
2783 const IS_OBJECT_SAFE = 1 << 1,
2784 const OBJECT_SAFETY_VALID = 1 << 2,
2785 const IMPLS_VALID = 1 << 3,
2789 /// As `TypeScheme` but for a trait ref.
2790 pub struct TraitDef<'tcx> {
2791 pub unsafety: ast::Unsafety,
2793 /// If `true`, then this trait had the `#[rustc_paren_sugar]`
2794 /// attribute, indicating that it should be used with `Foo()`
2795 /// sugar. This is a temporary thing -- eventually any trait wil
2796 /// be usable with the sugar (or without it).
2797 pub paren_sugar: bool,
2799 /// Generic type definitions. Note that `Self` is listed in here
2800 /// as having a single bound, the trait itself (e.g., in the trait
2801 /// `Eq`, there is a single bound `Self : Eq`). This is so that
2802 /// default methods get to assume that the `Self` parameters
2803 /// implements the trait.
2804 pub generics: Generics<'tcx>,
2806 pub trait_ref: TraitRef<'tcx>,
2808 /// A list of the associated types defined in this trait. Useful
2809 /// for resolving `X::Foo` type markers.
2810 pub associated_type_names: Vec<ast::Name>,
2812 // Impls of this trait. To allow for quicker lookup, the impls are indexed
2813 // by a simplified version of their Self type: impls with a simplifiable
2814 // Self are stored in nonblanket_impls keyed by it, while all other impls
2815 // are stored in blanket_impls.
2817 /// Impls of the trait.
2818 pub nonblanket_impls: RefCell<
2819 FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>>
2822 /// Blanket impls associated with the trait.
2823 pub blanket_impls: RefCell<Vec<DefId>>,
2826 pub flags: Cell<TraitFlags>
2829 impl<'tcx> TraitDef<'tcx> {
2830 // returns None if not yet calculated
2831 pub fn object_safety(&self) -> Option<bool> {
2832 if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) {
2833 Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE))
2839 pub fn set_object_safety(&self, is_safe: bool) {
2840 assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true));
2842 self.flags.get() | if is_safe {
2843 TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE
2845 TraitFlags::OBJECT_SAFETY_VALID
2850 /// Records a trait-to-implementation mapping.
2851 pub fn record_impl(&self,
2854 impl_trait_ref: TraitRef<'tcx>) {
2855 debug!("TraitDef::record_impl for {:?}, from {:?}",
2856 self, impl_trait_ref);
2858 // We don't want to borrow_mut after we already populated all impls,
2859 // so check if an impl is present with an immutable borrow first.
2860 if let Some(sty) = fast_reject::simplify_type(tcx,
2861 impl_trait_ref.self_ty(), false) {
2862 if let Some(is) = self.nonblanket_impls.borrow().get(&sty) {
2863 if is.contains(&impl_def_id) {
2864 return // duplicate - skip
2868 self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id)
2870 if self.blanket_impls.borrow().contains(&impl_def_id) {
2871 return // duplicate - skip
2873 self.blanket_impls.borrow_mut().push(impl_def_id)
2878 pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &ctxt<'tcx>, mut f: F) {
2879 ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
2881 for &impl_def_id in self.blanket_impls.borrow().iter() {
2885 for v in self.nonblanket_impls.borrow().values() {
2886 for &impl_def_id in v {
2892 pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self,
2897 ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id);
2899 for &impl_def_id in self.blanket_impls.borrow().iter() {
2903 if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, false) {
2904 if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) {
2905 for &impl_def_id in impls {
2908 return; // we don't need to process the other non-blanket impls
2912 for v in self.nonblanket_impls.borrow().values() {
2913 for &impl_def_id in v {
2921 /// Records the substitutions used to translate the polytype for an
2922 /// item into the monotype of an item reference.
2924 pub struct ItemSubsts<'tcx> {
2925 pub substs: Substs<'tcx>,
2928 #[derive(Clone, Copy, PartialOrd, Ord, PartialEq, Eq, Debug, RustcEncodable, RustcDecodable)]
2929 pub enum ClosureKind {
2930 // Warning: Ordering is significant here! The ordering is chosen
2931 // because the trait Fn is a subtrait of FnMut and so in turn, and
2932 // hence we order it so that Fn < FnMut < FnOnce.
2939 pub fn trait_did(&self, cx: &ctxt) -> ast::DefId {
2940 let result = match *self {
2941 FnClosureKind => cx.lang_items.require(FnTraitLangItem),
2942 FnMutClosureKind => {
2943 cx.lang_items.require(FnMutTraitLangItem)
2945 FnOnceClosureKind => {
2946 cx.lang_items.require(FnOnceTraitLangItem)
2950 Ok(trait_did) => trait_did,
2951 Err(err) => cx.sess.fatal(&err[..]),
2955 /// True if this a type that impls this closure kind
2956 /// must also implement `other`.
2957 pub fn extends(self, other: ty::ClosureKind) -> bool {
2958 match (self, other) {
2959 (FnClosureKind, FnClosureKind) => true,
2960 (FnClosureKind, FnMutClosureKind) => true,
2961 (FnClosureKind, FnOnceClosureKind) => true,
2962 (FnMutClosureKind, FnMutClosureKind) => true,
2963 (FnMutClosureKind, FnOnceClosureKind) => true,
2964 (FnOnceClosureKind, FnOnceClosureKind) => true,
2970 pub trait ClosureTyper<'tcx> {
2971 fn tcx(&self) -> &ty::ctxt<'tcx> {
2972 self.param_env().tcx
2975 fn param_env<'a>(&'a self) -> &'a ty::ParameterEnvironment<'a, 'tcx>;
2977 /// Is this a `Fn`, `FnMut` or `FnOnce` closure? During typeck,
2978 /// returns `None` if the kind of this closure has not yet been
2980 fn closure_kind(&self,
2982 -> Option<ty::ClosureKind>;
2984 /// Returns the argument/return types of this closure.
2985 fn closure_type(&self,
2987 substs: &subst::Substs<'tcx>)
2988 -> ty::ClosureTy<'tcx>;
2990 /// Returns the set of all upvars and their transformed
2991 /// types. During typeck, maybe return `None` if the upvar types
2992 /// have not yet been inferred.
2993 fn closure_upvars(&self,
2995 substs: &Substs<'tcx>)
2996 -> Option<Vec<ClosureUpvar<'tcx>>>;
2999 impl<'tcx> CommonTypes<'tcx> {
3000 fn new(arena: &'tcx TypedArena<TyS<'tcx>>,
3001 interner: &mut FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>)
3002 -> CommonTypes<'tcx>
3005 bool: intern_ty(arena, interner, TyBool),
3006 char: intern_ty(arena, interner, TyChar),
3007 err: intern_ty(arena, interner, TyError),
3008 isize: intern_ty(arena, interner, TyInt(ast::TyIs)),
3009 i8: intern_ty(arena, interner, TyInt(ast::TyI8)),
3010 i16: intern_ty(arena, interner, TyInt(ast::TyI16)),
3011 i32: intern_ty(arena, interner, TyInt(ast::TyI32)),
3012 i64: intern_ty(arena, interner, TyInt(ast::TyI64)),
3013 usize: intern_ty(arena, interner, TyUint(ast::TyUs)),
3014 u8: intern_ty(arena, interner, TyUint(ast::TyU8)),
3015 u16: intern_ty(arena, interner, TyUint(ast::TyU16)),
3016 u32: intern_ty(arena, interner, TyUint(ast::TyU32)),
3017 u64: intern_ty(arena, interner, TyUint(ast::TyU64)),
3018 f32: intern_ty(arena, interner, TyFloat(ast::TyF32)),
3019 f64: intern_ty(arena, interner, TyFloat(ast::TyF64)),
3024 /// Create a type context and call the closure with a `&ty::ctxt` reference
3025 /// to the context. The closure enforces that the type context and any interned
3026 /// value (types, substs, etc.) can only be used while `ty::tls` has a valid
3027 /// reference to the context, to allow formatting values that need it.
3028 pub fn with_ctxt<'tcx, F, R>(s: Session,
3029 arenas: &'tcx CtxtArenas<'tcx>,
3031 named_region_map: resolve_lifetime::NamedRegionMap,
3032 map: ast_map::Map<'tcx>,
3033 freevars: RefCell<FreevarMap>,
3034 region_maps: RegionMaps,
3035 lang_items: middle::lang_items::LanguageItems,
3036 stability: stability::Index<'tcx>,
3037 f: F) -> (Session, R)
3038 where F: FnOnce(&ctxt<'tcx>) -> R
3040 let mut interner = FnvHashMap();
3041 let common_types = CommonTypes::new(&arenas.type_, &mut interner);
3045 interner: RefCell::new(interner),
3046 substs_interner: RefCell::new(FnvHashMap()),
3047 bare_fn_interner: RefCell::new(FnvHashMap()),
3048 region_interner: RefCell::new(FnvHashMap()),
3049 stability_interner: RefCell::new(FnvHashMap()),
3050 types: common_types,
3051 named_region_map: named_region_map,
3052 region_maps: region_maps,
3053 free_region_maps: RefCell::new(FnvHashMap()),
3054 item_variance_map: RefCell::new(DefIdMap()),
3055 variance_computed: Cell::new(false),
3058 node_types: RefCell::new(FnvHashMap()),
3059 item_substs: RefCell::new(NodeMap()),
3060 impl_trait_refs: RefCell::new(DefIdMap()),
3061 trait_defs: RefCell::new(DefIdMap()),
3062 predicates: RefCell::new(DefIdMap()),
3063 super_predicates: RefCell::new(DefIdMap()),
3064 fulfilled_predicates: RefCell::new(traits::FulfilledPredicates::new()),
3067 tcache: RefCell::new(DefIdMap()),
3068 rcache: RefCell::new(FnvHashMap()),
3069 tc_cache: RefCell::new(FnvHashMap()),
3070 ast_ty_to_ty_cache: RefCell::new(NodeMap()),
3071 enum_var_cache: RefCell::new(DefIdMap()),
3072 impl_or_trait_items: RefCell::new(DefIdMap()),
3073 trait_item_def_ids: RefCell::new(DefIdMap()),
3074 trait_items_cache: RefCell::new(DefIdMap()),
3075 ty_param_defs: RefCell::new(NodeMap()),
3076 adjustments: RefCell::new(NodeMap()),
3077 normalized_cache: RefCell::new(FnvHashMap()),
3078 lang_items: lang_items,
3079 provided_method_sources: RefCell::new(DefIdMap()),
3080 struct_fields: RefCell::new(DefIdMap()),
3081 destructor_for_type: RefCell::new(DefIdMap()),
3082 destructors: RefCell::new(DefIdSet()),
3083 inherent_impls: RefCell::new(DefIdMap()),
3084 impl_items: RefCell::new(DefIdMap()),
3085 used_unsafe: RefCell::new(NodeSet()),
3086 used_mut_nodes: RefCell::new(NodeSet()),
3087 populated_external_types: RefCell::new(DefIdSet()),
3088 populated_external_primitive_impls: RefCell::new(DefIdSet()),
3089 upvar_capture_map: RefCell::new(FnvHashMap()),
3090 extern_const_statics: RefCell::new(DefIdMap()),
3091 extern_const_variants: RefCell::new(DefIdMap()),
3092 extern_const_fns: RefCell::new(DefIdMap()),
3093 method_map: RefCell::new(FnvHashMap()),
3094 dependency_formats: RefCell::new(FnvHashMap()),
3095 closure_kinds: RefCell::new(DefIdMap()),
3096 closure_tys: RefCell::new(DefIdMap()),
3097 node_lint_levels: RefCell::new(FnvHashMap()),
3098 transmute_restrictions: RefCell::new(Vec::new()),
3099 stability: RefCell::new(stability),
3100 selection_cache: traits::SelectionCache::new(),
3101 repr_hint_cache: RefCell::new(DefIdMap()),
3102 const_qualif_map: RefCell::new(NodeMap()),
3103 custom_coerce_unsized_kinds: RefCell::new(DefIdMap()),
3104 cast_kinds: RefCell::new(NodeMap()),
3108 // Type constructors
3110 impl<'tcx> ctxt<'tcx> {
3111 pub fn mk_substs(&self, substs: Substs<'tcx>) -> &'tcx Substs<'tcx> {
3112 if let Some(substs) = self.substs_interner.borrow().get(&substs) {
3116 let substs = self.arenas.substs.alloc(substs);
3117 self.substs_interner.borrow_mut().insert(substs, substs);
3121 /// Create an unsafe fn ty based on a safe fn ty.
3122 pub fn safe_to_unsafe_fn_ty(&self, bare_fn: &BareFnTy<'tcx>) -> Ty<'tcx> {
3123 assert_eq!(bare_fn.unsafety, ast::Unsafety::Normal);
3124 let unsafe_fn_ty_a = self.mk_bare_fn(ty::BareFnTy {
3125 unsafety: ast::Unsafety::Unsafe,
3127 sig: bare_fn.sig.clone()
3129 ty::mk_bare_fn(self, None, unsafe_fn_ty_a)
3132 pub fn mk_bare_fn(&self, bare_fn: BareFnTy<'tcx>) -> &'tcx BareFnTy<'tcx> {
3133 if let Some(bare_fn) = self.bare_fn_interner.borrow().get(&bare_fn) {
3137 let bare_fn = self.arenas.bare_fn.alloc(bare_fn);
3138 self.bare_fn_interner.borrow_mut().insert(bare_fn, bare_fn);
3142 pub fn mk_region(&self, region: Region) -> &'tcx Region {
3143 if let Some(region) = self.region_interner.borrow().get(®ion) {
3147 let region = self.arenas.region.alloc(region);
3148 self.region_interner.borrow_mut().insert(region, region);
3152 pub fn closure_kind(&self, def_id: ast::DefId) -> ty::ClosureKind {
3153 *self.closure_kinds.borrow().get(&def_id).unwrap()
3156 pub fn closure_type(&self,
3158 substs: &subst::Substs<'tcx>)
3159 -> ty::ClosureTy<'tcx>
3161 self.closure_tys.borrow().get(&def_id).unwrap().subst(self, substs)
3164 pub fn type_parameter_def(&self,
3165 node_id: ast::NodeId)
3166 -> TypeParameterDef<'tcx>
3168 self.ty_param_defs.borrow().get(&node_id).unwrap().clone()
3171 pub fn pat_contains_ref_binding(&self, pat: &ast::Pat) -> Option<ast::Mutability> {
3172 pat_util::pat_contains_ref_binding(&self.def_map, pat)
3175 pub fn arm_contains_ref_binding(&self, arm: &ast::Arm) -> Option<ast::Mutability> {
3176 pat_util::arm_contains_ref_binding(&self.def_map, arm)
3180 // Interns a type/name combination, stores the resulting box in cx.interner,
3181 // and returns the box as cast to an unsafe ptr (see comments for Ty above).
3182 pub fn mk_t<'tcx>(cx: &ctxt<'tcx>, st: TypeVariants<'tcx>) -> Ty<'tcx> {
3183 let mut interner = cx.interner.borrow_mut();
3184 intern_ty(&cx.arenas.type_, &mut *interner, st)
3187 fn intern_ty<'tcx>(type_arena: &'tcx TypedArena<TyS<'tcx>>,
3188 interner: &mut FnvHashMap<InternedTy<'tcx>, Ty<'tcx>>,
3189 st: TypeVariants<'tcx>)
3192 match interner.get(&st) {
3193 Some(ty) => return *ty,
3197 let flags = FlagComputation::for_sty(&st);
3200 () => type_arena.alloc(TyS { sty: st,
3201 flags: Cell::new(flags.flags),
3202 region_depth: flags.depth, }),
3205 debug!("Interned type: {:?} Pointer: {:?}",
3206 ty, ty as *const TyS);
3208 interner.insert(InternedTy { ty: ty }, ty);
3213 struct FlagComputation {
3216 // maximum depth of any bound region that we have seen thus far
3220 impl FlagComputation {
3221 fn new() -> FlagComputation {
3222 FlagComputation { flags: TypeFlags::empty(), depth: 0 }
3225 fn for_sty(st: &TypeVariants) -> FlagComputation {
3226 let mut result = FlagComputation::new();
3231 fn add_flags(&mut self, flags: TypeFlags) {
3232 self.flags = self.flags | (flags & TypeFlags::NOMINAL_FLAGS);
3235 fn add_depth(&mut self, depth: u32) {
3236 if depth > self.depth {
3241 /// Adds the flags/depth from a set of types that appear within the current type, but within a
3243 fn add_bound_computation(&mut self, computation: &FlagComputation) {
3244 self.add_flags(computation.flags);
3246 // The types that contributed to `computation` occurred within
3247 // a region binder, so subtract one from the region depth
3248 // within when adding the depth to `self`.
3249 let depth = computation.depth;
3251 self.add_depth(depth - 1);
3255 fn add_sty(&mut self, st: &TypeVariants) {
3265 // You might think that we could just return TyError for
3266 // any type containing TyError as a component, and get
3267 // rid of the TypeFlags::HAS_TY_ERR flag -- likewise for ty_bot (with
3268 // the exception of function types that return bot).
3269 // But doing so caused sporadic memory corruption, and
3270 // neither I (tjc) nor nmatsakis could figure out why,
3271 // so we're doing it this way.
3273 self.add_flags(TypeFlags::HAS_TY_ERR)
3276 &TyParam(ref p) => {
3277 self.add_flags(TypeFlags::HAS_LOCAL_NAMES);
3278 if p.space == subst::SelfSpace {
3279 self.add_flags(TypeFlags::HAS_SELF);
3281 self.add_flags(TypeFlags::HAS_PARAMS);
3285 &TyClosure(_, substs) => {
3286 self.add_flags(TypeFlags::HAS_LOCAL_NAMES);
3287 self.add_substs(substs);
3291 self.add_flags(TypeFlags::HAS_LOCAL_NAMES); // it might, right?
3292 self.add_flags(TypeFlags::HAS_TY_INFER)
3295 &TyEnum(_, substs) | &TyStruct(_, substs) => {
3296 self.add_substs(substs);
3299 &TyProjection(ref data) => {
3300 self.add_flags(TypeFlags::HAS_PROJECTION);
3301 self.add_projection_ty(data);
3304 &TyTrait(box TraitTy { ref principal, ref bounds }) => {
3305 let mut computation = FlagComputation::new();
3306 computation.add_substs(principal.0.substs);
3307 for projection_bound in &bounds.projection_bounds {
3308 let mut proj_computation = FlagComputation::new();
3309 proj_computation.add_projection_predicate(&projection_bound.0);
3310 self.add_bound_computation(&proj_computation);
3312 self.add_bound_computation(&computation);
3314 self.add_bounds(bounds);
3317 &TyBox(tt) | &TyArray(tt, _) | &TySlice(tt) => {
3321 &TyRawPtr(ref m) => {
3325 &TyRef(r, ref m) => {
3326 self.add_region(*r);
3330 &TyTuple(ref ts) => {
3331 self.add_tys(&ts[..]);
3334 &TyBareFn(_, ref f) => {
3335 self.add_fn_sig(&f.sig);
3340 fn add_ty(&mut self, ty: Ty) {
3341 self.add_flags(ty.flags.get());
3342 self.add_depth(ty.region_depth);
3345 fn add_tys(&mut self, tys: &[Ty]) {
3351 fn add_fn_sig(&mut self, fn_sig: &PolyFnSig) {
3352 let mut computation = FlagComputation::new();
3354 computation.add_tys(&fn_sig.0.inputs);
3356 if let ty::FnConverging(output) = fn_sig.0.output {
3357 computation.add_ty(output);
3360 self.add_bound_computation(&computation);
3363 fn add_region(&mut self, r: Region) {
3365 ty::ReInfer(_) => { self.add_flags(TypeFlags::HAS_RE_INFER); }
3366 ty::ReLateBound(debruijn, _) => { self.add_depth(debruijn.depth); }
3367 ty::ReEarlyBound(..) => { self.add_flags(TypeFlags::HAS_RE_EARLY_BOUND); }
3369 _ => { self.add_flags(TypeFlags::HAS_FREE_REGIONS); }
3373 self.add_flags(TypeFlags::HAS_LOCAL_NAMES);
3377 fn add_projection_predicate(&mut self, projection_predicate: &ProjectionPredicate) {
3378 self.add_projection_ty(&projection_predicate.projection_ty);
3379 self.add_ty(projection_predicate.ty);
3382 fn add_projection_ty(&mut self, projection_ty: &ProjectionTy) {
3383 self.add_substs(projection_ty.trait_ref.substs);
3386 fn add_substs(&mut self, substs: &Substs) {
3387 self.add_tys(substs.types.as_slice());
3388 match substs.regions {
3389 subst::ErasedRegions => {}
3390 subst::NonerasedRegions(ref regions) => {
3398 fn add_bounds(&mut self, bounds: &ExistentialBounds) {
3399 self.add_region(bounds.region_bound);
3403 pub fn mk_mach_int<'tcx>(tcx: &ctxt<'tcx>, tm: ast::IntTy) -> Ty<'tcx> {
3405 ast::TyIs => tcx.types.isize,
3406 ast::TyI8 => tcx.types.i8,
3407 ast::TyI16 => tcx.types.i16,
3408 ast::TyI32 => tcx.types.i32,
3409 ast::TyI64 => tcx.types.i64,
3413 pub fn mk_mach_uint<'tcx>(tcx: &ctxt<'tcx>, tm: ast::UintTy) -> Ty<'tcx> {
3415 ast::TyUs => tcx.types.usize,
3416 ast::TyU8 => tcx.types.u8,
3417 ast::TyU16 => tcx.types.u16,
3418 ast::TyU32 => tcx.types.u32,
3419 ast::TyU64 => tcx.types.u64,
3423 pub fn mk_mach_float<'tcx>(tcx: &ctxt<'tcx>, tm: ast::FloatTy) -> Ty<'tcx> {
3425 ast::TyF32 => tcx.types.f32,
3426 ast::TyF64 => tcx.types.f64,
3430 pub fn mk_str<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3434 pub fn mk_str_slice<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, m: ast::Mutability) -> Ty<'tcx> {
3437 ty: mk_t(cx, TyStr),
3442 pub fn mk_enum<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId, substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
3443 // take a copy of substs so that we own the vectors inside
3444 mk_t(cx, TyEnum(did, substs))
3447 pub fn mk_uniq<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> { mk_t(cx, TyBox(ty)) }
3449 pub fn mk_ptr<'tcx>(cx: &ctxt<'tcx>, tm: mt<'tcx>) -> Ty<'tcx> { mk_t(cx, TyRawPtr(tm)) }
3451 pub fn mk_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, tm: mt<'tcx>) -> Ty<'tcx> {
3452 mk_t(cx, TyRef(r, tm))
3455 pub fn mk_mut_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
3456 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutMutable})
3458 pub fn mk_imm_rptr<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, ty: Ty<'tcx>) -> Ty<'tcx> {
3459 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutImmutable})
3462 pub fn mk_mut_ptr<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3463 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutMutable})
3466 pub fn mk_imm_ptr<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3467 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutImmutable})
3470 pub fn mk_nil_ptr<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3471 mk_ptr(cx, mt {ty: mk_nil(cx), mutbl: ast::MutImmutable})
3474 pub fn mk_vec<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>, sz: Option<usize>) -> Ty<'tcx> {
3476 Some(n) => mk_t(cx, TyArray(ty, n)),
3477 None => mk_t(cx, TySlice(ty))
3481 pub fn mk_slice<'tcx>(cx: &ctxt<'tcx>, r: &'tcx Region, tm: mt<'tcx>) -> Ty<'tcx> {
3484 ty: mk_vec(cx, tm.ty, None),
3489 pub fn mk_tup<'tcx>(cx: &ctxt<'tcx>, ts: Vec<Ty<'tcx>>) -> Ty<'tcx> {
3490 mk_t(cx, TyTuple(ts))
3493 pub fn mk_nil<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3494 mk_tup(cx, Vec::new())
3497 pub fn mk_bool<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3501 pub fn mk_bare_fn<'tcx>(cx: &ctxt<'tcx>,
3502 opt_def_id: Option<ast::DefId>,
3503 fty: &'tcx BareFnTy<'tcx>) -> Ty<'tcx> {
3504 mk_t(cx, TyBareFn(opt_def_id, fty))
3507 pub fn mk_ctor_fn<'tcx>(cx: &ctxt<'tcx>,
3509 input_tys: &[Ty<'tcx>],
3510 output: Ty<'tcx>) -> Ty<'tcx> {
3511 let input_args = input_tys.iter().cloned().collect();
3514 cx.mk_bare_fn(BareFnTy {
3515 unsafety: ast::Unsafety::Normal,
3517 sig: ty::Binder(FnSig {
3519 output: ty::FnConverging(output),
3525 pub fn mk_trait<'tcx>(cx: &ctxt<'tcx>,
3526 principal: ty::PolyTraitRef<'tcx>,
3527 bounds: ExistentialBounds<'tcx>)
3530 assert!(bound_list_is_sorted(&bounds.projection_bounds));
3532 let inner = box TraitTy {
3533 principal: principal,
3536 mk_t(cx, TyTrait(inner))
3539 fn bound_list_is_sorted(bounds: &[ty::PolyProjectionPredicate]) -> bool {
3540 bounds.is_empty() ||
3541 bounds[1..].iter().enumerate().all(
3542 |(index, bound)| bounds[index].sort_key() <= bound.sort_key())
3545 pub fn sort_bounds_list(bounds: &mut [ty::PolyProjectionPredicate]) {
3546 bounds.sort_by(|a, b| a.sort_key().cmp(&b.sort_key()))
3549 pub fn mk_projection<'tcx>(cx: &ctxt<'tcx>,
3550 trait_ref: TraitRef<'tcx>,
3551 item_name: ast::Name)
3553 // take a copy of substs so that we own the vectors inside
3554 let inner = ProjectionTy { trait_ref: trait_ref, item_name: item_name };
3555 mk_t(cx, TyProjection(inner))
3558 pub fn mk_struct<'tcx>(cx: &ctxt<'tcx>, struct_id: ast::DefId,
3559 substs: &'tcx Substs<'tcx>) -> Ty<'tcx> {
3560 // take a copy of substs so that we own the vectors inside
3561 mk_t(cx, TyStruct(struct_id, substs))
3564 pub fn mk_closure<'tcx>(cx: &ctxt<'tcx>, closure_id: ast::DefId, substs: &'tcx Substs<'tcx>)
3566 mk_t(cx, TyClosure(closure_id, substs))
3569 pub fn mk_var<'tcx>(cx: &ctxt<'tcx>, v: TyVid) -> Ty<'tcx> {
3570 mk_infer(cx, TyVar(v))
3573 pub fn mk_int_var<'tcx>(cx: &ctxt<'tcx>, v: IntVid) -> Ty<'tcx> {
3574 mk_infer(cx, IntVar(v))
3577 pub fn mk_float_var<'tcx>(cx: &ctxt<'tcx>, v: FloatVid) -> Ty<'tcx> {
3578 mk_infer(cx, FloatVar(v))
3581 pub fn mk_infer<'tcx>(cx: &ctxt<'tcx>, it: InferTy) -> Ty<'tcx> {
3582 mk_t(cx, TyInfer(it))
3585 pub fn mk_param<'tcx>(cx: &ctxt<'tcx>,
3586 space: subst::ParamSpace,
3588 name: ast::Name) -> Ty<'tcx> {
3589 mk_t(cx, TyParam(ParamTy { space: space, idx: index, name: name }))
3592 pub fn mk_self_type<'tcx>(cx: &ctxt<'tcx>) -> Ty<'tcx> {
3593 mk_param(cx, subst::SelfSpace, 0, special_idents::type_self.name)
3596 pub fn mk_param_from_def<'tcx>(cx: &ctxt<'tcx>, def: &TypeParameterDef) -> Ty<'tcx> {
3597 mk_param(cx, def.space, def.index, def.name)
3600 impl<'tcx> TyS<'tcx> {
3601 /// Iterator that walks `self` and any types reachable from
3602 /// `self`, in depth-first order. Note that just walks the types
3603 /// that appear in `self`, it does not descend into the fields of
3604 /// structs or variants. For example:
3607 /// isize => { isize }
3608 /// Foo<Bar<isize>> => { Foo<Bar<isize>>, Bar<isize>, isize }
3609 /// [isize] => { [isize], isize }
3611 pub fn walk(&'tcx self) -> TypeWalker<'tcx> {
3612 TypeWalker::new(self)
3615 /// Iterator that walks the immediate children of `self`. Hence
3616 /// `Foo<Bar<i32>, u32>` yields the sequence `[Bar<i32>, u32]`
3617 /// (but not `i32`, like `walk`).
3618 pub fn walk_shallow(&'tcx self) -> IntoIter<Ty<'tcx>> {
3619 ty_walk::walk_shallow(self)
3622 pub fn as_opt_param_ty(&self) -> Option<ty::ParamTy> {
3624 ty::TyParam(ref d) => Some(d.clone()),
3629 pub fn is_param(&self, space: ParamSpace, index: u32) -> bool {
3631 ty::TyParam(ref data) => data.space == space && data.idx == index,
3637 pub fn walk_ty<'tcx, F>(ty_root: Ty<'tcx>, mut f: F)
3638 where F: FnMut(Ty<'tcx>),
3640 for ty in ty_root.walk() {
3645 /// Walks `ty` and any types appearing within `ty`, invoking the
3646 /// callback `f` on each type. If the callback returns false, then the
3647 /// children of the current type are ignored.
3649 /// Note: prefer `ty.walk()` where possible.
3650 pub fn maybe_walk_ty<'tcx,F>(ty_root: Ty<'tcx>, mut f: F)
3651 where F : FnMut(Ty<'tcx>) -> bool
3653 let mut walker = ty_root.walk();
3654 while let Some(ty) = walker.next() {
3656 walker.skip_current_subtree();
3661 // Folds types from the bottom up.
3662 pub fn fold_ty<'tcx, F>(cx: &ctxt<'tcx>, t0: Ty<'tcx>,
3665 F: FnMut(Ty<'tcx>) -> Ty<'tcx>,
3667 let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
3672 pub fn new(space: subst::ParamSpace,
3676 ParamTy { space: space, idx: index, name: name }
3679 pub fn for_self() -> ParamTy {
3680 ParamTy::new(subst::SelfSpace, 0, special_idents::type_self.name)
3683 pub fn for_def(def: &TypeParameterDef) -> ParamTy {
3684 ParamTy::new(def.space, def.index, def.name)
3687 pub fn to_ty<'tcx>(self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
3688 ty::mk_param(tcx, self.space, self.idx, self.name)
3691 pub fn is_self(&self) -> bool {
3692 self.space == subst::SelfSpace && self.idx == 0
3696 impl<'tcx> ItemSubsts<'tcx> {
3697 pub fn empty() -> ItemSubsts<'tcx> {
3698 ItemSubsts { substs: Substs::empty() }
3701 pub fn is_noop(&self) -> bool {
3702 self.substs.is_noop()
3706 impl<'tcx> ParamBounds<'tcx> {
3707 pub fn empty() -> ParamBounds<'tcx> {
3709 builtin_bounds: BuiltinBounds::empty(),
3710 trait_bounds: Vec::new(),
3711 region_bounds: Vec::new(),
3712 projection_bounds: Vec::new(),
3719 pub fn type_is_nil(ty: Ty) -> bool {
3721 TyTuple(ref tys) => tys.is_empty(),
3726 pub fn type_is_error(ty: Ty) -> bool {
3727 ty.flags.get().intersects(TypeFlags::HAS_TY_ERR)
3730 pub fn type_needs_subst(ty: Ty) -> bool {
3731 ty.flags.get().intersects(TypeFlags::NEEDS_SUBST)
3734 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
3735 tref.substs.types.any(|&ty| type_is_error(ty))
3738 pub fn type_is_ty_var(ty: Ty) -> bool {
3740 TyInfer(TyVar(_)) => true,
3745 pub fn type_is_bool(ty: Ty) -> bool { ty.sty == TyBool }
3747 pub fn type_is_self(ty: Ty) -> bool {
3749 TyParam(ref p) => p.space == subst::SelfSpace,
3754 fn type_is_slice(ty: Ty) -> bool {
3756 TyRawPtr(mt) | TyRef(_, mt) => match mt.ty.sty {
3757 TySlice(_) | TyStr => true,
3764 pub fn type_is_structural(ty: Ty) -> bool {
3766 TyStruct(..) | TyTuple(_) | TyEnum(..) |
3767 TyArray(..) | TyClosure(..) => true,
3768 _ => type_is_slice(ty) | type_is_trait(ty)
3772 pub fn type_is_simd(cx: &ctxt, ty: Ty) -> bool {
3774 TyStruct(did, _) => lookup_simd(cx, did),
3779 pub fn sequence_element_type<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3781 TyArray(ty, _) | TySlice(ty) => ty,
3782 TyStr => mk_mach_uint(cx, ast::TyU8),
3783 _ => cx.sess.bug(&format!("sequence_element_type called on non-sequence value: {}",
3788 pub fn simd_type<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Ty<'tcx> {
3790 TyStruct(did, substs) => {
3791 let fields = lookup_struct_fields(cx, did);
3792 lookup_field_type(cx, did, fields[0].id, substs)
3794 _ => panic!("simd_type called on invalid type")
3798 pub fn simd_size(cx: &ctxt, ty: Ty) -> usize {
3800 TyStruct(did, _) => {
3801 let fields = lookup_struct_fields(cx, did);
3804 _ => panic!("simd_size called on invalid type")
3808 pub fn type_is_region_ptr(ty: Ty) -> bool {
3815 pub fn type_is_unsafe_ptr(ty: Ty) -> bool {
3817 TyRawPtr(_) => return true,
3822 pub fn type_is_unique(ty: Ty) -> bool {
3830 A scalar type is one that denotes an atomic datum, with no sub-components.
3831 (A TyRawPtr is scalar because it represents a non-managed pointer, so its
3832 contents are abstract to rustc.)
3834 pub fn type_is_scalar(ty: Ty) -> bool {
3836 TyBool | TyChar | TyInt(_) | TyFloat(_) | TyUint(_) |
3837 TyInfer(IntVar(_)) | TyInfer(FloatVar(_)) |
3838 TyBareFn(..) | TyRawPtr(_) => true,
3843 /// Returns true if this type is a floating point type and false otherwise.
3844 pub fn type_is_floating_point(ty: Ty) -> bool {
3847 TyInfer(FloatVar(_)) =>
3855 /// Type contents is how the type checker reasons about kinds.
3856 /// They track what kinds of things are found within a type. You can
3857 /// think of them as kind of an "anti-kind". They track the kinds of values
3858 /// and thinks that are contained in types. Having a larger contents for
3859 /// a type tends to rule that type *out* from various kinds. For example,
3860 /// a type that contains a reference is not sendable.
3862 /// The reason we compute type contents and not kinds is that it is
3863 /// easier for me (nmatsakis) to think about what is contained within
3864 /// a type than to think about what is *not* contained within a type.
3865 #[derive(Clone, Copy)]
3866 pub struct TypeContents {
3870 macro_rules! def_type_content_sets {
3871 (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
3872 #[allow(non_snake_case)]
3874 use middle::ty::TypeContents;
3876 #[allow(non_upper_case_globals)]
3877 pub const $name: TypeContents = TypeContents { bits: $bits };
3883 def_type_content_sets! {
3885 None = 0b0000_0000__0000_0000__0000,
3887 // Things that are interior to the value (first nibble):
3888 InteriorUnsized = 0b0000_0000__0000_0000__0001,
3889 InteriorUnsafe = 0b0000_0000__0000_0000__0010,
3890 InteriorParam = 0b0000_0000__0000_0000__0100,
3891 // InteriorAll = 0b00000000__00000000__1111,
3893 // Things that are owned by the value (second and third nibbles):
3894 OwnsOwned = 0b0000_0000__0000_0001__0000,
3895 OwnsDtor = 0b0000_0000__0000_0010__0000,
3896 OwnsAll = 0b0000_0000__1111_1111__0000,
3898 // Things that are reachable by the value in any way (fourth nibble):
3899 ReachesBorrowed = 0b0000_0010__0000_0000__0000,
3900 ReachesMutable = 0b0000_1000__0000_0000__0000,
3901 ReachesFfiUnsafe = 0b0010_0000__0000_0000__0000,
3902 ReachesAll = 0b0011_1111__0000_0000__0000,
3904 // Things that mean drop glue is necessary
3905 NeedsDrop = 0b0000_0000__0000_0111__0000,
3907 // Things that prevent values from being considered sized
3908 Nonsized = 0b0000_0000__0000_0000__0001,
3911 All = 0b1111_1111__1111_1111__1111
3916 pub fn when(&self, cond: bool) -> TypeContents {
3917 if cond {*self} else {TC::None}
3920 pub fn intersects(&self, tc: TypeContents) -> bool {
3921 (self.bits & tc.bits) != 0
3924 pub fn owns_owned(&self) -> bool {
3925 self.intersects(TC::OwnsOwned)
3928 pub fn is_sized(&self, _: &ctxt) -> bool {
3929 !self.intersects(TC::Nonsized)
3932 pub fn interior_param(&self) -> bool {
3933 self.intersects(TC::InteriorParam)
3936 pub fn interior_unsafe(&self) -> bool {
3937 self.intersects(TC::InteriorUnsafe)
3940 pub fn interior_unsized(&self) -> bool {
3941 self.intersects(TC::InteriorUnsized)
3944 pub fn needs_drop(&self, _: &ctxt) -> bool {
3945 self.intersects(TC::NeedsDrop)
3948 /// Includes only those bits that still apply when indirected through a `Box` pointer
3949 pub fn owned_pointer(&self) -> TypeContents {
3951 *self & (TC::OwnsAll | TC::ReachesAll))
3954 /// Includes only those bits that still apply when indirected through a reference (`&`)
3955 pub fn reference(&self, bits: TypeContents) -> TypeContents {
3957 *self & TC::ReachesAll)
3960 /// Includes only those bits that still apply when indirected through a raw pointer (`*`)
3961 pub fn unsafe_pointer(&self) -> TypeContents {
3962 *self & TC::ReachesAll
3965 pub fn union<T, F>(v: &[T], mut f: F) -> TypeContents where
3966 F: FnMut(&T) -> TypeContents,
3968 v.iter().fold(TC::None, |tc, ty| tc | f(ty))
3971 pub fn has_dtor(&self) -> bool {
3972 self.intersects(TC::OwnsDtor)
3976 impl ops::BitOr for TypeContents {
3977 type Output = TypeContents;
3979 fn bitor(self, other: TypeContents) -> TypeContents {
3980 TypeContents {bits: self.bits | other.bits}
3984 impl ops::BitAnd for TypeContents {
3985 type Output = TypeContents;
3987 fn bitand(self, other: TypeContents) -> TypeContents {
3988 TypeContents {bits: self.bits & other.bits}
3992 impl ops::Sub for TypeContents {
3993 type Output = TypeContents;
3995 fn sub(self, other: TypeContents) -> TypeContents {
3996 TypeContents {bits: self.bits & !other.bits}
4000 impl fmt::Debug for TypeContents {
4001 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
4002 write!(f, "TypeContents({:b})", self.bits)
4006 pub fn type_contents<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> TypeContents {
4007 return memoized(&cx.tc_cache, ty, |ty| {
4008 tc_ty(cx, ty, &mut FnvHashMap())
4011 fn tc_ty<'tcx>(cx: &ctxt<'tcx>,
4013 cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
4015 // Subtle: Note that we are *not* using cx.tc_cache here but rather a
4016 // private cache for this walk. This is needed in the case of cyclic
4019 // struct List { next: Box<Option<List>>, ... }
4021 // When computing the type contents of such a type, we wind up deeply
4022 // recursing as we go. So when we encounter the recursive reference
4023 // to List, we temporarily use TC::None as its contents. Later we'll
4024 // patch up the cache with the correct value, once we've computed it
4025 // (this is basically a co-inductive process, if that helps). So in
4026 // the end we'll compute TC::OwnsOwned, in this case.
4028 // The problem is, as we are doing the computation, we will also
4029 // compute an *intermediate* contents for, e.g., Option<List> of
4030 // TC::None. This is ok during the computation of List itself, but if
4031 // we stored this intermediate value into cx.tc_cache, then later
4032 // requests for the contents of Option<List> would also yield TC::None
4033 // which is incorrect. This value was computed based on the crutch
4034 // value for the type contents of list. The correct value is
4035 // TC::OwnsOwned. This manifested as issue #4821.
4036 match cache.get(&ty) {
4037 Some(tc) => { return *tc; }
4040 match cx.tc_cache.borrow().get(&ty) { // Must check both caches!
4041 Some(tc) => { return *tc; }
4044 cache.insert(ty, TC::None);
4046 let result = match ty.sty {
4047 // usize and isize are ffi-unsafe
4048 TyUint(ast::TyUs) | TyInt(ast::TyIs) => {
4049 TC::ReachesFfiUnsafe
4052 // Scalar and unique types are sendable, and durable
4053 TyInfer(ty::FreshIntTy(_)) | TyInfer(ty::FreshFloatTy(_)) |
4054 TyBool | TyInt(_) | TyUint(_) | TyFloat(_) |
4055 TyBareFn(..) | ty::TyChar => {
4060 TC::ReachesFfiUnsafe | match typ.sty {
4061 TyStr => TC::OwnsOwned,
4062 _ => tc_ty(cx, typ, cache).owned_pointer(),
4066 TyTrait(box TraitTy { ref bounds, .. }) => {
4067 object_contents(bounds) | TC::ReachesFfiUnsafe | TC::Nonsized
4070 TyRawPtr(ref mt) => {
4071 tc_ty(cx, mt.ty, cache).unsafe_pointer()
4074 TyRef(r, ref mt) => {
4075 TC::ReachesFfiUnsafe | match mt.ty.sty {
4076 TyStr => borrowed_contents(*r, ast::MutImmutable),
4078 TySlice(_) => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(*r,
4080 _ => tc_ty(cx, mt.ty, cache).reference(borrowed_contents(*r, mt.mutbl)),
4085 tc_ty(cx, ty, cache)
4089 tc_ty(cx, ty, cache) | TC::Nonsized
4091 TyStr => TC::Nonsized,
4093 TyStruct(did, substs) => {
4094 let flds = struct_fields(cx, did, substs);
4096 TypeContents::union(&flds[..],
4097 |f| tc_mt(cx, f.mt, cache));
4099 if !lookup_repr_hints(cx, did).contains(&attr::ReprExtern) {
4100 res = res | TC::ReachesFfiUnsafe;
4103 if ty::has_dtor(cx, did) {
4104 res = res | TC::OwnsDtor;
4106 apply_lang_items(cx, did, res)
4109 TyClosure(did, substs) => {
4110 // FIXME(#14449): `borrowed_contents` below assumes `&mut` closure.
4111 let param_env = ty::empty_parameter_environment(cx);
4112 let upvars = closure_upvars(¶m_env, did, substs).unwrap();
4113 TypeContents::union(&upvars, |f| tc_ty(cx, &f.ty, cache))
4116 TyTuple(ref tys) => {
4117 TypeContents::union(&tys[..],
4118 |ty| tc_ty(cx, *ty, cache))
4121 TyEnum(did, substs) => {
4122 let variants = substd_enum_variants(cx, did, substs);
4124 TypeContents::union(&variants[..], |variant| {
4125 TypeContents::union(&variant.args,
4127 tc_ty(cx, *arg_ty, cache)
4131 if ty::has_dtor(cx, did) {
4132 res = res | TC::OwnsDtor;
4135 if !variants.is_empty() {
4136 let repr_hints = lookup_repr_hints(cx, did);
4137 if repr_hints.len() > 1 {
4138 // this is an error later on, but this type isn't safe
4139 res = res | TC::ReachesFfiUnsafe;
4142 match repr_hints.get(0) {
4143 Some(h) => if !h.is_ffi_safe() {
4144 res = res | TC::ReachesFfiUnsafe;
4148 res = res | TC::ReachesFfiUnsafe;
4150 // We allow ReprAny enums if they are eligible for
4151 // the nullable pointer optimization and the
4152 // contained type is an `extern fn`
4154 if variants.len() == 2 {
4155 let mut data_idx = 0;
4157 if variants[0].args.is_empty() {
4161 if variants[data_idx].args.len() == 1 {
4162 match variants[data_idx].args[0].sty {
4163 TyBareFn(..) => { res = res - TC::ReachesFfiUnsafe; }
4173 apply_lang_items(cx, did, res)
4183 cx.sess.bug("asked to compute contents of error type");
4187 cache.insert(ty, result);
4191 fn tc_mt<'tcx>(cx: &ctxt<'tcx>,
4193 cache: &mut FnvHashMap<Ty<'tcx>, TypeContents>) -> TypeContents
4195 let mc = TC::ReachesMutable.when(mt.mutbl == MutMutable);
4196 mc | tc_ty(cx, mt.ty, cache)
4199 fn apply_lang_items(cx: &ctxt, did: ast::DefId, tc: TypeContents)
4201 if Some(did) == cx.lang_items.unsafe_cell_type() {
4202 tc | TC::InteriorUnsafe
4208 /// Type contents due to containing a reference with the region `region` and borrow kind `bk`
4209 fn borrowed_contents(region: ty::Region,
4210 mutbl: ast::Mutability)
4212 let b = match mutbl {
4213 ast::MutMutable => TC::ReachesMutable,
4214 ast::MutImmutable => TC::None,
4216 b | (TC::ReachesBorrowed).when(region != ty::ReStatic)
4219 fn object_contents(bounds: &ExistentialBounds) -> TypeContents {
4220 // These are the type contents of the (opaque) interior. We
4221 // make no assumptions (other than that it cannot have an
4222 // in-scope type parameter within, which makes no sense).
4223 let mut tc = TC::All - TC::InteriorParam;
4224 for bound in &bounds.builtin_bounds {
4225 tc = tc - match bound {
4226 BoundSync | BoundSend | BoundCopy => TC::None,
4227 BoundSized => TC::Nonsized,
4234 fn type_impls_bound<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
4235 tcx: &ty::ctxt<'tcx>,
4237 bound: ty::BuiltinBound,
4242 let param_env = match param_env {
4245 pe = empty_parameter_environment(tcx);
4249 let infcx = infer::new_infer_ctxt(tcx);
4251 let is_impld = traits::type_known_to_meet_builtin_bound(&infcx, param_env, ty, bound, span);
4253 debug!("type_impls_bound({:?}, {:?}) = {:?}",
4261 pub fn type_moves_by_default<'a,'tcx>(param_env: &ParameterEnvironment<'a,'tcx>,
4266 if ty.flags.get().intersects(TypeFlags::MOVENESS_CACHED) {
4267 return ty.flags.get().intersects(TypeFlags::MOVES_BY_DEFAULT);
4270 assert!(!ty::type_needs_infer(ty));
4272 // Fast-path for primitive types
4273 let result = match ty.sty {
4274 TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
4275 TyRawPtr(..) | TyBareFn(..) | TyRef(_, mt {
4276 mutbl: ast::MutImmutable, ..
4279 TyStr | TyBox(..) | TyRef(_, mt {
4280 mutbl: ast::MutMutable, ..
4283 TyArray(..) | TySlice(_) | TyTrait(..) | TyTuple(..) |
4284 TyClosure(..) | TyEnum(..) | TyStruct(..) |
4285 TyProjection(..) | TyParam(..) | TyInfer(..) | TyError => None
4286 }.unwrap_or_else(|| !type_impls_bound(Some(param_env),
4292 if !type_has_params(ty) && !type_has_self(ty) {
4293 ty.flags.set(ty.flags.get() | if result {
4294 TypeFlags::MOVENESS_CACHED | TypeFlags::MOVES_BY_DEFAULT
4296 TypeFlags::MOVENESS_CACHED
4304 pub fn type_is_sized<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
4305 tcx: &ty::ctxt<'tcx>,
4310 if ty.flags.get().intersects(TypeFlags::SIZEDNESS_CACHED) {
4311 let result = ty.flags.get().intersects(TypeFlags::IS_SIZED);
4315 type_is_sized_uncached(param_env, tcx, span, ty)
4318 fn type_is_sized_uncached<'a,'tcx>(param_env: Option<&ParameterEnvironment<'a,'tcx>>,
4319 tcx: &ty::ctxt<'tcx>,
4321 ty: Ty<'tcx>) -> bool {
4322 assert!(!ty::type_needs_infer(ty));
4324 // Fast-path for primitive types
4325 let result = match ty.sty {
4326 TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) |
4327 TyBox(..) | TyRawPtr(..) | TyRef(..) | TyBareFn(..) |
4328 TyArray(..) | TyTuple(..) | TyClosure(..) => Some(true),
4330 TyStr | TyTrait(..) | TySlice(_) => Some(false),
4332 TyEnum(..) | TyStruct(..) | TyProjection(..) | TyParam(..) |
4333 TyInfer(..) | TyError => None
4334 }.unwrap_or_else(|| type_impls_bound(param_env, tcx, ty, ty::BoundSized, span));
4336 if !type_has_params(ty) && !type_has_self(ty) {
4337 ty.flags.set(ty.flags.get() | if result {
4338 TypeFlags::SIZEDNESS_CACHED | TypeFlags::IS_SIZED
4340 TypeFlags::SIZEDNESS_CACHED
4347 pub fn is_ffi_safe<'tcx>(cx: &ctxt<'tcx>, ty: Ty<'tcx>) -> bool {
4348 !type_contents(cx, ty).intersects(TC::ReachesFfiUnsafe)
4351 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
4352 pub fn is_instantiable<'tcx>(cx: &ctxt<'tcx>, r_ty: Ty<'tcx>) -> bool {
4353 fn type_requires<'tcx>(cx: &ctxt<'tcx>, seen: &mut Vec<DefId>,
4354 r_ty: Ty<'tcx>, ty: Ty<'tcx>) -> bool {
4355 debug!("type_requires({:?}, {:?})?",
4358 let r = r_ty == ty || subtypes_require(cx, seen, r_ty, ty);
4360 debug!("type_requires({:?}, {:?})? {:?}",
4365 fn subtypes_require<'tcx>(cx: &ctxt<'tcx>, seen: &mut Vec<DefId>,
4366 r_ty: Ty<'tcx>, ty: Ty<'tcx>) -> bool {
4367 debug!("subtypes_require({:?}, {:?})?",
4370 let r = match ty.sty {
4371 // fixed length vectors need special treatment compared to
4372 // normal vectors, since they don't necessarily have the
4373 // possibility to have length zero.
4374 TyArray(_, 0) => false, // don't need no contents
4375 TyArray(ty, _) => type_requires(cx, seen, r_ty, ty),
4390 type_requires(cx, seen, r_ty, typ)
4392 TyRef(_, ref mt) => {
4393 type_requires(cx, seen, r_ty, mt.ty)
4397 false // unsafe ptrs can always be NULL
4404 TyStruct(ref did, _) if seen.contains(did) => {
4408 TyStruct(did, substs) => {
4410 let fields = struct_fields(cx, did, substs);
4411 let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
4412 seen.pop().unwrap();
4419 // this check is run on type definitions, so we don't expect to see
4420 // inference by-products or closure types
4421 cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
4424 TyTuple(ref ts) => {
4425 ts.iter().any(|ty| type_requires(cx, seen, r_ty, *ty))
4428 TyEnum(ref did, _) if seen.contains(did) => {
4432 TyEnum(did, substs) => {
4434 let vs = enum_variants(cx, did);
4435 let r = !vs.is_empty() && vs.iter().all(|variant| {
4436 variant.args.iter().any(|aty| {
4437 let sty = aty.subst(cx, substs);
4438 type_requires(cx, seen, r_ty, sty)
4441 seen.pop().unwrap();
4446 debug!("subtypes_require({:?}, {:?})? {:?}",
4452 let mut seen = Vec::new();
4453 !subtypes_require(cx, &mut seen, r_ty, r_ty)
4456 /// Describes whether a type is representable. For types that are not
4457 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
4458 /// distinguish between types that are recursive with themselves and types that
4459 /// contain a different recursive type. These cases can therefore be treated
4460 /// differently when reporting errors.
4462 /// The ordering of the cases is significant. They are sorted so that cmp::max
4463 /// will keep the "more erroneous" of two values.
4464 #[derive(Copy, Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
4465 pub enum Representability {
4471 /// Check whether a type is representable. This means it cannot contain unboxed
4472 /// structural recursion. This check is needed for structs and enums.
4473 pub fn is_type_representable<'tcx>(cx: &ctxt<'tcx>, sp: Span, ty: Ty<'tcx>)
4474 -> Representability {
4476 // Iterate until something non-representable is found
4477 fn find_nonrepresentable<'tcx, It: Iterator<Item=Ty<'tcx>>>(cx: &ctxt<'tcx>, sp: Span,
4478 seen: &mut Vec<Ty<'tcx>>,
4480 -> Representability {
4481 iter.fold(Representable,
4482 |r, ty| cmp::max(r, is_type_structurally_recursive(cx, sp, seen, ty)))
4485 fn are_inner_types_recursive<'tcx>(cx: &ctxt<'tcx>, sp: Span,
4486 seen: &mut Vec<Ty<'tcx>>, ty: Ty<'tcx>)
4487 -> Representability {
4489 TyTuple(ref ts) => {
4490 find_nonrepresentable(cx, sp, seen, ts.iter().cloned())
4492 // Fixed-length vectors.
4493 // FIXME(#11924) Behavior undecided for zero-length vectors.
4495 is_type_structurally_recursive(cx, sp, seen, ty)
4497 TyStruct(did, substs) => {
4498 let fields = struct_fields(cx, did, substs);
4499 find_nonrepresentable(cx, sp, seen, fields.iter().map(|f| f.mt.ty))
4501 TyEnum(did, substs) => {
4502 let vs = enum_variants(cx, did);
4503 let iter = vs.iter()
4504 .flat_map(|variant| &variant.args)
4505 .map(|aty| { aty.subst_spanned(cx, substs, Some(sp)) });
4507 find_nonrepresentable(cx, sp, seen, iter)
4510 // this check is run on type definitions, so we don't expect
4511 // to see closure types
4512 cx.sess.bug(&format!("requires check invoked on inapplicable type: {:?}", ty))
4518 fn same_struct_or_enum_def_id(ty: Ty, did: DefId) -> bool {
4520 TyStruct(ty_did, _) | TyEnum(ty_did, _) => {
4527 fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
4528 match (&a.sty, &b.sty) {
4529 (&TyStruct(did_a, ref substs_a), &TyStruct(did_b, ref substs_b)) |
4530 (&TyEnum(did_a, ref substs_a), &TyEnum(did_b, ref substs_b)) => {
4535 let types_a = substs_a.types.get_slice(subst::TypeSpace);
4536 let types_b = substs_b.types.get_slice(subst::TypeSpace);
4538 let mut pairs = types_a.iter().zip(types_b);
4540 pairs.all(|(&a, &b)| same_type(a, b))
4548 // Does the type `ty` directly (without indirection through a pointer)
4549 // contain any types on stack `seen`?
4550 fn is_type_structurally_recursive<'tcx>(cx: &ctxt<'tcx>, sp: Span,
4551 seen: &mut Vec<Ty<'tcx>>,
4552 ty: Ty<'tcx>) -> Representability {
4553 debug!("is_type_structurally_recursive: {:?}", ty);
4556 TyStruct(did, _) | TyEnum(did, _) => {
4558 // Iterate through stack of previously seen types.
4559 let mut iter = seen.iter();
4561 // The first item in `seen` is the type we are actually curious about.
4562 // We want to return SelfRecursive if this type contains itself.
4563 // It is important that we DON'T take generic parameters into account
4564 // for this check, so that Bar<T> in this example counts as SelfRecursive:
4567 // struct Bar<T> { x: Bar<Foo> }
4570 Some(&seen_type) => {
4571 if same_struct_or_enum_def_id(seen_type, did) {
4572 debug!("SelfRecursive: {:?} contains {:?}",
4575 return SelfRecursive;
4581 // We also need to know whether the first item contains other types that
4582 // are structurally recursive. If we don't catch this case, we will recurse
4583 // infinitely for some inputs.
4585 // It is important that we DO take generic parameters into account here,
4586 // so that code like this is considered SelfRecursive, not ContainsRecursive:
4588 // struct Foo { Option<Option<Foo>> }
4590 for &seen_type in iter {
4591 if same_type(ty, seen_type) {
4592 debug!("ContainsRecursive: {:?} contains {:?}",
4595 return ContainsRecursive;
4600 // For structs and enums, track all previously seen types by pushing them
4601 // onto the 'seen' stack.
4603 let out = are_inner_types_recursive(cx, sp, seen, ty);
4608 // No need to push in other cases.
4609 are_inner_types_recursive(cx, sp, seen, ty)
4614 debug!("is_type_representable: {:?}", ty);
4616 // To avoid a stack overflow when checking an enum variant or struct that
4617 // contains a different, structurally recursive type, maintain a stack
4618 // of seen types and check recursion for each of them (issues #3008, #3779).
4619 let mut seen: Vec<Ty> = Vec::new();
4620 let r = is_type_structurally_recursive(cx, sp, &mut seen, ty);
4621 debug!("is_type_representable: {:?} is {:?}", ty, r);
4625 pub fn type_is_trait(ty: Ty) -> bool {
4627 TyTrait(..) => true,
4632 pub fn type_is_integral(ty: Ty) -> bool {
4634 TyInfer(IntVar(_)) | TyInt(_) | TyUint(_) => true,
4639 pub fn type_is_fresh(ty: Ty) -> bool {
4641 TyInfer(FreshTy(_)) => true,
4642 TyInfer(FreshIntTy(_)) => true,
4643 TyInfer(FreshFloatTy(_)) => true,
4648 pub fn type_is_uint(ty: Ty) -> bool {
4650 TyInfer(IntVar(_)) | TyUint(ast::TyUs) => true,
4655 pub fn type_is_char(ty: Ty) -> bool {
4662 pub fn type_is_bare_fn(ty: Ty) -> bool {
4664 TyBareFn(..) => true,
4669 pub fn type_is_bare_fn_item(ty: Ty) -> bool {
4671 TyBareFn(Some(_), _) => true,
4676 pub fn type_is_fp(ty: Ty) -> bool {
4678 TyInfer(FloatVar(_)) | TyFloat(_) => true,
4683 pub fn type_is_numeric(ty: Ty) -> bool {
4684 return type_is_integral(ty) || type_is_fp(ty);
4687 pub fn type_is_signed(ty: Ty) -> bool {
4694 pub fn type_is_machine(ty: Ty) -> bool {
4696 TyInt(ast::TyIs) | TyUint(ast::TyUs) => false,
4697 TyInt(..) | TyUint(..) | TyFloat(..) => true,
4702 // Whether a type is enum like, that is an enum type with only nullary
4704 pub fn type_is_c_like_enum(cx: &ctxt, ty: Ty) -> bool {
4707 let variants = enum_variants(cx, did);
4708 if variants.is_empty() {
4711 variants.iter().all(|v| v.args.is_empty())
4718 // Returns the type and mutability of *ty.
4720 // The parameter `explicit` indicates if this is an *explicit* dereference.
4721 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
4722 pub fn deref<'tcx>(ty: Ty<'tcx>, explicit: bool) -> Option<mt<'tcx>> {
4727 mutbl: ast::MutImmutable,
4730 TyRef(_, mt) => Some(mt),
4731 TyRawPtr(mt) if explicit => Some(mt),
4736 pub fn type_content<'tcx>(ty: Ty<'tcx>) -> Ty<'tcx> {
4739 TyRef(_, mt) | TyRawPtr(mt) => mt.ty,
4744 // Returns the type of ty[i]
4745 pub fn index<'tcx>(ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
4747 TyArray(ty, _) | TySlice(ty) => Some(ty),
4752 // Returns the type of elements contained within an 'array-like' type.
4753 // This is exactly the same as the above, except it supports strings,
4754 // which can't actually be indexed.
4755 pub fn array_element_ty<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
4757 TyArray(ty, _) | TySlice(ty) => Some(ty),
4758 TyStr => Some(tcx.types.u8),
4763 /// Returns the type of element at index `i` in tuple or tuple-like type `t`.
4764 /// For an enum `t`, `variant` is None only if `t` is a univariant enum.
4765 pub fn positional_element_ty<'tcx>(cx: &ctxt<'tcx>,
4768 variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
4770 match (&ty.sty, variant) {
4771 (&TyTuple(ref v), None) => v.get(i).cloned(),
4774 (&TyStruct(def_id, substs), None) => lookup_struct_fields(cx, def_id)
4776 .map(|&t|lookup_item_type(cx, t.id).ty.subst(cx, substs)),
4778 (&TyEnum(def_id, substs), Some(variant_def_id)) => {
4779 let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
4780 variant_info.args.get(i).map(|t|t.subst(cx, substs))
4783 (&TyEnum(def_id, substs), None) => {
4784 assert!(enum_is_univariant(cx, def_id));
4785 let enum_variants = enum_variants(cx, def_id);
4786 let variant_info = &(*enum_variants)[0];
4787 variant_info.args.get(i).map(|t|t.subst(cx, substs))
4794 /// Returns the type of element at field `n` in struct or struct-like type `t`.
4795 /// For an enum `t`, `variant` must be some def id.
4796 pub fn named_element_ty<'tcx>(cx: &ctxt<'tcx>,
4799 variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
4801 match (&ty.sty, variant) {
4802 (&TyStruct(def_id, substs), None) => {
4803 let r = lookup_struct_fields(cx, def_id);
4804 r.iter().find(|f| f.name == n)
4805 .map(|&f| lookup_field_type(cx, def_id, f.id, substs))
4807 (&TyEnum(def_id, substs), Some(variant_def_id)) => {
4808 let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
4809 variant_info.arg_names.as_ref()
4810 .expect("must have struct enum variant if accessing a named fields")
4811 .iter().zip(&variant_info.args)
4812 .find(|&(&name, _)| name == n)
4813 .map(|(_name, arg_t)| arg_t.subst(cx, substs))
4819 pub fn node_id_to_type<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> Ty<'tcx> {
4820 match node_id_to_type_opt(cx, id) {
4822 None => cx.sess.bug(
4823 &format!("node_id_to_type: no type for node `{}`",
4824 cx.map.node_to_string(id)))
4828 pub fn node_id_to_type_opt<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> Option<Ty<'tcx>> {
4829 match cx.node_types.borrow().get(&id) {
4830 Some(&ty) => Some(ty),
4835 pub fn node_id_item_substs<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) -> ItemSubsts<'tcx> {
4836 match cx.item_substs.borrow().get(&id) {
4837 None => ItemSubsts::empty(),
4838 Some(ts) => ts.clone(),
4842 pub fn fn_is_variadic(fty: Ty) -> bool {
4844 TyBareFn(_, ref f) => f.sig.0.variadic,
4846 panic!("fn_is_variadic() called on non-fn type: {:?}", s)
4851 pub fn ty_fn_sig<'tcx>(fty: Ty<'tcx>) -> &'tcx PolyFnSig<'tcx> {
4853 TyBareFn(_, ref f) => &f.sig,
4855 panic!("ty_fn_sig() called on non-fn type: {:?}", s)
4860 /// Returns the ABI of the given function.
4861 pub fn ty_fn_abi(fty: Ty) -> abi::Abi {
4863 TyBareFn(_, ref f) => f.abi,
4864 _ => panic!("ty_fn_abi() called on non-fn type"),
4868 // Type accessors for substructures of types
4869 pub fn ty_fn_args<'tcx>(fty: Ty<'tcx>) -> ty::Binder<Vec<Ty<'tcx>>> {
4870 ty_fn_sig(fty).inputs()
4873 pub fn ty_fn_ret<'tcx>(fty: Ty<'tcx>) -> Binder<FnOutput<'tcx>> {
4875 TyBareFn(_, ref f) => f.sig.output(),
4877 panic!("ty_fn_ret() called on non-fn type: {:?}", s)
4882 pub fn is_fn_ty(fty: Ty) -> bool {
4884 TyBareFn(..) => true,
4889 pub fn ty_region(tcx: &ctxt,
4897 &format!("ty_region() invoked on an inappropriate ty: {:?}",
4903 pub fn free_region_from_def(outlives_extent: region::DestructionScopeData,
4904 def: &RegionParameterDef)
4908 ty::ReFree(ty::FreeRegion { scope: outlives_extent,
4909 bound_region: ty::BrNamed(def.def_id,
4911 debug!("free_region_from_def returns {:?}", ret);
4915 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
4916 // doesn't provide type parameter substitutions.
4917 pub fn pat_ty<'tcx>(cx: &ctxt<'tcx>, pat: &ast::Pat) -> Ty<'tcx> {
4918 return node_id_to_type(cx, pat.id);
4920 pub fn pat_ty_opt<'tcx>(cx: &ctxt<'tcx>, pat: &ast::Pat) -> Option<Ty<'tcx>> {
4921 return node_id_to_type_opt(cx, pat.id);
4925 // Returns the type of an expression as a monotype.
4927 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression. That is, in
4928 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
4929 // auto-ref. The type returned by this function does not consider such
4930 // adjustments. See `expr_ty_adjusted()` instead.
4932 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
4933 // ask for the type of "id" in "id(3)", it will return "fn(&isize) -> isize"
4934 // instead of "fn(ty) -> T with T = isize".
4935 pub fn expr_ty<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Ty<'tcx> {
4936 return node_id_to_type(cx, expr.id);
4939 pub fn expr_ty_opt<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Option<Ty<'tcx>> {
4940 return node_id_to_type_opt(cx, expr.id);
4943 /// Returns the type of `expr`, considering any `AutoAdjustment`
4944 /// entry recorded for that expression.
4946 /// It would almost certainly be better to store the adjusted ty in with
4947 /// the `AutoAdjustment`, but I opted not to do this because it would
4948 /// require serializing and deserializing the type and, although that's not
4949 /// hard to do, I just hate that code so much I didn't want to touch it
4950 /// unless it was to fix it properly, which seemed a distraction from the
4951 /// thread at hand! -nmatsakis
4952 pub fn expr_ty_adjusted<'tcx>(cx: &ctxt<'tcx>, expr: &ast::Expr) -> Ty<'tcx> {
4953 adjust_ty(cx, expr.span, expr.id, expr_ty(cx, expr),
4954 cx.adjustments.borrow().get(&expr.id),
4955 |method_call| cx.method_map.borrow().get(&method_call).map(|method| method.ty))
4958 pub fn expr_span(cx: &ctxt, id: NodeId) -> Span {
4959 match cx.map.find(id) {
4960 Some(ast_map::NodeExpr(e)) => {
4964 cx.sess.bug(&format!("Node id {} is not an expr: {:?}",
4969 cx.sess.bug(&format!("Node id {} is not present \
4970 in the node map", id));
4975 pub fn local_var_name_str(cx: &ctxt, id: NodeId) -> InternedString {
4976 match cx.map.find(id) {
4977 Some(ast_map::NodeLocal(pat)) => {
4979 ast::PatIdent(_, ref path1, _) => {
4980 token::get_ident(path1.node)
4984 &format!("Variable id {} maps to {:?}, not local",
4991 cx.sess.bug(&format!("Variable id {} maps to {:?}, not local",
4998 /// See `expr_ty_adjusted`
4999 pub fn adjust_ty<'tcx, F>(cx: &ctxt<'tcx>,
5001 expr_id: ast::NodeId,
5002 unadjusted_ty: Ty<'tcx>,
5003 adjustment: Option<&AutoAdjustment<'tcx>>,
5006 F: FnMut(MethodCall) -> Option<Ty<'tcx>>,
5008 if let TyError = unadjusted_ty.sty {
5009 return unadjusted_ty;
5012 return match adjustment {
5013 Some(adjustment) => {
5015 AdjustReifyFnPointer => {
5016 match unadjusted_ty.sty {
5017 ty::TyBareFn(Some(_), b) => {
5018 ty::mk_bare_fn(cx, None, b)
5022 &format!("AdjustReifyFnPointer adjustment on non-fn-item: \
5023 {:?}", unadjusted_ty));
5028 AdjustUnsafeFnPointer => {
5029 match unadjusted_ty.sty {
5030 ty::TyBareFn(None, b) => cx.safe_to_unsafe_fn_ty(b),
5033 &format!("AdjustReifyFnPointer adjustment on non-fn-item: \
5040 AdjustDerefRef(ref adj) => {
5041 let mut adjusted_ty = unadjusted_ty;
5043 if !ty::type_is_error(adjusted_ty) {
5044 for i in 0..adj.autoderefs {
5045 let method_call = MethodCall::autoderef(expr_id, i as u32);
5046 match method_type(method_call) {
5047 Some(method_ty) => {
5048 // Overloaded deref operators have all late-bound
5049 // regions fully instantiated and coverge.
5051 ty::no_late_bound_regions(cx,
5052 &ty_fn_ret(method_ty)).unwrap();
5053 adjusted_ty = fn_ret.unwrap();
5057 match deref(adjusted_ty, true) {
5058 Some(mt) => { adjusted_ty = mt.ty; }
5062 &format!("the {}th autoderef failed: {}",
5071 if let Some(target) = adj.unsize {
5074 adjust_ty_for_autoref(cx, adjusted_ty, adj.autoref)
5079 None => unadjusted_ty
5083 pub fn adjust_ty_for_autoref<'tcx>(cx: &ctxt<'tcx>,
5085 autoref: Option<AutoRef<'tcx>>)
5089 Some(AutoPtr(r, m)) => {
5090 mk_rptr(cx, r, mt { ty: ty, mutbl: m })
5092 Some(AutoUnsafe(m)) => {
5093 mk_ptr(cx, mt { ty: ty, mutbl: m })
5098 pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> def::Def {
5099 match tcx.def_map.borrow().get(&expr.id) {
5100 Some(def) => def.full_def(),
5102 tcx.sess.span_bug(expr.span, &format!(
5103 "no def-map entry for expr {}", expr.id));
5108 pub fn expr_is_lval(tcx: &ctxt, expr: &ast::Expr) -> bool {
5110 ast::ExprPath(..) => {
5111 // We can't use resolve_expr here, as this needs to run on broken
5112 // programs. We don't need to through - associated items are all
5114 match tcx.def_map.borrow().get(&expr.id) {
5115 Some(&def::PathResolution {
5116 base_def: def::DefStatic(..), ..
5117 }) | Some(&def::PathResolution {
5118 base_def: def::DefUpvar(..), ..
5119 }) | Some(&def::PathResolution {
5120 base_def: def::DefLocal(..), ..
5127 None => tcx.sess.span_bug(expr.span, &format!(
5128 "no def for path {}", expr.id))
5132 ast::ExprUnary(ast::UnDeref, _) |
5133 ast::ExprField(..) |
5134 ast::ExprTupField(..) |
5135 ast::ExprIndex(..) => {
5140 ast::ExprMethodCall(..) |
5141 ast::ExprStruct(..) |
5142 ast::ExprRange(..) |
5145 ast::ExprMatch(..) |
5146 ast::ExprClosure(..) |
5147 ast::ExprBlock(..) |
5148 ast::ExprRepeat(..) |
5150 ast::ExprBreak(..) |
5151 ast::ExprAgain(..) |
5153 ast::ExprWhile(..) |
5155 ast::ExprAssign(..) |
5156 ast::ExprInlineAsm(..) |
5157 ast::ExprAssignOp(..) |
5159 ast::ExprUnary(..) |
5161 ast::ExprAddrOf(..) |
5162 ast::ExprBinary(..) |
5163 ast::ExprCast(..) => {
5167 ast::ExprParen(ref e) => expr_is_lval(tcx, e),
5169 ast::ExprIfLet(..) |
5170 ast::ExprWhileLet(..) |
5171 ast::ExprForLoop(..) |
5172 ast::ExprMac(..) => {
5175 "macro expression remains after expansion");
5180 pub fn stmt_node_id(s: &ast::Stmt) -> ast::NodeId {
5182 ast::StmtDecl(_, id) | StmtExpr(_, id) | StmtSemi(_, id) => {
5185 ast::StmtMac(..) => panic!("unexpanded macro in trans")
5189 pub fn field_idx_strict(tcx: &ctxt, name: ast::Name, fields: &[field])
5192 for f in fields { if f.name == name { return i; } i += 1; }
5193 tcx.sess.bug(&format!(
5194 "no field named `{}` found in the list of fields `{:?}`",
5195 token::get_name(name),
5197 .map(|f| token::get_name(f.name).to_string())
5198 .collect::<Vec<String>>()));
5201 pub fn impl_or_trait_item_idx(id: ast::Name, trait_items: &[ImplOrTraitItem])
5203 trait_items.iter().position(|m| m.name() == id)
5206 pub fn ty_sort_string(cx: &ctxt, ty: Ty) -> String {
5208 TyBool | TyChar | TyInt(_) |
5209 TyUint(_) | TyFloat(_) | TyStr => ty.to_string(),
5210 TyTuple(ref tys) if tys.is_empty() => ty.to_string(),
5212 TyEnum(id, _) => format!("enum `{}`", item_path_str(cx, id)),
5213 TyBox(_) => "box".to_string(),
5214 TyArray(_, n) => format!("array of {} elements", n),
5215 TySlice(_) => "slice".to_string(),
5216 TyRawPtr(_) => "*-ptr".to_string(),
5217 TyRef(_, _) => "&-ptr".to_string(),
5218 TyBareFn(Some(_), _) => format!("fn item"),
5219 TyBareFn(None, _) => "fn pointer".to_string(),
5220 TyTrait(ref inner) => {
5221 format!("trait {}", item_path_str(cx, inner.principal_def_id()))
5223 TyStruct(id, _) => {
5224 format!("struct `{}`", item_path_str(cx, id))
5226 TyClosure(..) => "closure".to_string(),
5227 TyTuple(_) => "tuple".to_string(),
5228 TyInfer(TyVar(_)) => "inferred type".to_string(),
5229 TyInfer(IntVar(_)) => "integral variable".to_string(),
5230 TyInfer(FloatVar(_)) => "floating-point variable".to_string(),
5231 TyInfer(FreshTy(_)) => "skolemized type".to_string(),
5232 TyInfer(FreshIntTy(_)) => "skolemized integral type".to_string(),
5233 TyInfer(FreshFloatTy(_)) => "skolemized floating-point type".to_string(),
5234 TyProjection(_) => "associated type".to_string(),
5236 if p.space == subst::SelfSpace {
5239 "type parameter".to_string()
5242 TyError => "type error".to_string(),
5246 /// Explains the source of a type err in a short, human readable way. This is meant to be placed
5247 /// in parentheses after some larger message. You should also invoke `note_and_explain_type_err()`
5248 /// afterwards to present additional details, particularly when it comes to lifetime-related
5250 impl<'tcx> fmt::Display for type_err<'tcx> {
5251 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
5253 terr_cyclic_ty => write!(f, "cyclic type of infinite size"),
5254 terr_mismatch => write!(f, "types differ"),
5255 terr_unsafety_mismatch(values) => {
5256 write!(f, "expected {} fn, found {} fn",
5260 terr_abi_mismatch(values) => {
5261 write!(f, "expected {} fn, found {} fn",
5265 terr_mutability => write!(f, "values differ in mutability"),
5266 terr_box_mutability => {
5267 write!(f, "boxed values differ in mutability")
5269 terr_vec_mutability => write!(f, "vectors differ in mutability"),
5270 terr_ptr_mutability => write!(f, "pointers differ in mutability"),
5271 terr_ref_mutability => write!(f, "references differ in mutability"),
5272 terr_ty_param_size(values) => {
5273 write!(f, "expected a type with {} type params, \
5274 found one with {} type params",
5278 terr_fixed_array_size(values) => {
5279 write!(f, "expected an array with a fixed size of {} elements, \
5280 found one with {} elements",
5284 terr_tuple_size(values) => {
5285 write!(f, "expected a tuple with {} elements, \
5286 found one with {} elements",
5291 write!(f, "incorrect number of function parameters")
5293 terr_regions_does_not_outlive(..) => {
5294 write!(f, "lifetime mismatch")
5296 terr_regions_not_same(..) => {
5297 write!(f, "lifetimes are not the same")
5299 terr_regions_no_overlap(..) => {
5300 write!(f, "lifetimes do not intersect")
5302 terr_regions_insufficiently_polymorphic(br, _) => {
5303 write!(f, "expected bound lifetime parameter {}, \
5304 found concrete lifetime", br)
5306 terr_regions_overly_polymorphic(br, _) => {
5307 write!(f, "expected concrete lifetime, \
5308 found bound lifetime parameter {}", br)
5310 terr_sorts(values) => tls::with(|tcx| {
5311 // A naive approach to making sure that we're not reporting silly errors such as:
5312 // (expected closure, found closure).
5313 let expected_str = ty_sort_string(tcx, values.expected);
5314 let found_str = ty_sort_string(tcx, values.found);
5315 if expected_str == found_str {
5316 write!(f, "expected {}, found a different {}", expected_str, found_str)
5318 write!(f, "expected {}, found {}", expected_str, found_str)
5321 terr_traits(values) => tls::with(|tcx| {
5322 write!(f, "expected trait `{}`, found trait `{}`",
5323 item_path_str(tcx, values.expected),
5324 item_path_str(tcx, values.found))
5326 terr_builtin_bounds(values) => {
5327 if values.expected.is_empty() {
5328 write!(f, "expected no bounds, found `{}`",
5330 } else if values.found.is_empty() {
5331 write!(f, "expected bounds `{}`, found no bounds",
5334 write!(f, "expected bounds `{}`, found bounds `{}`",
5339 terr_integer_as_char => {
5340 write!(f, "expected an integral type, found `char`")
5342 terr_int_mismatch(ref values) => {
5343 write!(f, "expected `{:?}`, found `{:?}`",
5347 terr_float_mismatch(ref values) => {
5348 write!(f, "expected `{:?}`, found `{:?}`",
5352 terr_variadic_mismatch(ref values) => {
5353 write!(f, "expected {} fn, found {} function",
5354 if values.expected { "variadic" } else { "non-variadic" },
5355 if values.found { "variadic" } else { "non-variadic" })
5357 terr_convergence_mismatch(ref values) => {
5358 write!(f, "expected {} fn, found {} function",
5359 if values.expected { "converging" } else { "diverging" },
5360 if values.found { "converging" } else { "diverging" })
5362 terr_projection_name_mismatched(ref values) => {
5363 write!(f, "expected {}, found {}",
5367 terr_projection_bounds_length(ref values) => {
5368 write!(f, "expected {} associated type bindings, found {}",
5376 pub fn note_and_explain_type_err<'tcx>(cx: &ctxt<'tcx>, err: &type_err<'tcx>, sp: Span) {
5378 terr_regions_does_not_outlive(subregion, superregion) => {
5379 note_and_explain_region(cx, "", subregion, "...");
5380 note_and_explain_region(cx, "...does not necessarily outlive ",
5383 terr_regions_not_same(region1, region2) => {
5384 note_and_explain_region(cx, "", region1, "...");
5385 note_and_explain_region(cx, "...is not the same lifetime as ",
5388 terr_regions_no_overlap(region1, region2) => {
5389 note_and_explain_region(cx, "", region1, "...");
5390 note_and_explain_region(cx, "...does not overlap ",
5393 terr_regions_insufficiently_polymorphic(_, conc_region) => {
5394 note_and_explain_region(cx,
5395 "concrete lifetime that was found is ",
5398 terr_regions_overly_polymorphic(_, ty::ReInfer(ty::ReVar(_))) => {
5399 // don't bother to print out the message below for
5400 // inference variables, it's not very illuminating.
5402 terr_regions_overly_polymorphic(_, conc_region) => {
5403 note_and_explain_region(cx,
5404 "expected concrete lifetime is ",
5407 terr_sorts(values) => {
5408 let expected_str = ty_sort_string(cx, values.expected);
5409 let found_str = ty_sort_string(cx, values.found);
5410 if expected_str == found_str && expected_str == "closure" {
5411 cx.sess.span_note(sp, &format!("no two closures, even if identical, have the same \
5413 cx.sess.span_help(sp, &format!("consider boxing your closure and/or \
5414 using it as a trait object"));
5421 pub fn provided_source(cx: &ctxt, id: ast::DefId) -> Option<ast::DefId> {
5422 cx.provided_method_sources.borrow().get(&id).cloned()
5425 pub fn provided_trait_methods<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5426 -> Vec<Rc<Method<'tcx>>> {
5428 if let ItemTrait(_, _, _, ref ms) = cx.map.expect_item(id.node).node {
5429 ms.iter().filter_map(|ti| {
5430 if let ast::MethodTraitItem(_, Some(_)) = ti.node {
5431 match impl_or_trait_item(cx, ast_util::local_def(ti.id)) {
5432 MethodTraitItem(m) => Some(m),
5434 cx.sess.bug("provided_trait_methods(): \
5435 non-method item found from \
5436 looking up provided method?!")
5444 cx.sess.bug(&format!("provided_trait_methods: `{:?}` is not a trait", id))
5447 csearch::get_provided_trait_methods(cx, id)
5451 pub fn associated_consts<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5452 -> Vec<Rc<AssociatedConst<'tcx>>> {
5454 match cx.map.expect_item(id.node).node {
5455 ItemTrait(_, _, _, ref tis) => {
5456 tis.iter().filter_map(|ti| {
5457 if let ast::ConstTraitItem(_, _) = ti.node {
5458 match impl_or_trait_item(cx, ast_util::local_def(ti.id)) {
5459 ConstTraitItem(ac) => Some(ac),
5461 cx.sess.bug("associated_consts(): \
5462 non-const item found from \
5463 looking up a constant?!")
5471 ItemImpl(_, _, _, _, _, ref iis) => {
5472 iis.iter().filter_map(|ii| {
5473 if let ast::ConstImplItem(_, _) = ii.node {
5474 match impl_or_trait_item(cx, ast_util::local_def(ii.id)) {
5475 ConstTraitItem(ac) => Some(ac),
5477 cx.sess.bug("associated_consts(): \
5478 non-const item found from \
5479 looking up a constant?!")
5488 cx.sess.bug(&format!("associated_consts: `{:?}` is not a trait \
5493 csearch::get_associated_consts(cx, id)
5497 /// Helper for looking things up in the various maps that are populated during
5498 /// typeck::collect (e.g., `cx.impl_or_trait_items`, `cx.tcache`, etc). All of
5499 /// these share the pattern that if the id is local, it should have been loaded
5500 /// into the map by the `typeck::collect` phase. If the def-id is external,
5501 /// then we have to go consult the crate loading code (and cache the result for
5503 fn lookup_locally_or_in_crate_store<V, F>(descr: &str,
5505 map: &RefCell<DefIdMap<V>>,
5506 load_external: F) -> V where
5510 match map.borrow().get(&def_id).cloned() {
5511 Some(v) => { return v; }
5515 if def_id.krate == ast::LOCAL_CRATE {
5516 panic!("No def'n found for {:?} in tcx.{}", def_id, descr);
5518 let v = load_external();
5519 map.borrow_mut().insert(def_id, v.clone());
5523 pub fn trait_item<'tcx>(cx: &ctxt<'tcx>, trait_did: ast::DefId, idx: usize)
5524 -> ImplOrTraitItem<'tcx> {
5525 let method_def_id = (*ty::trait_item_def_ids(cx, trait_did))[idx].def_id();
5526 impl_or_trait_item(cx, method_def_id)
5529 pub fn trait_items<'tcx>(cx: &ctxt<'tcx>, trait_did: ast::DefId)
5530 -> Rc<Vec<ImplOrTraitItem<'tcx>>> {
5531 let mut trait_items = cx.trait_items_cache.borrow_mut();
5532 match trait_items.get(&trait_did).cloned() {
5533 Some(trait_items) => trait_items,
5535 let def_ids = ty::trait_item_def_ids(cx, trait_did);
5536 let items: Rc<Vec<ImplOrTraitItem>> =
5537 Rc::new(def_ids.iter()
5538 .map(|d| impl_or_trait_item(cx, d.def_id()))
5540 trait_items.insert(trait_did, items.clone());
5546 pub fn trait_impl_polarity<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5547 -> Option<ast::ImplPolarity> {
5548 if id.krate == ast::LOCAL_CRATE {
5549 match cx.map.find(id.node) {
5550 Some(ast_map::NodeItem(item)) => {
5552 ast::ItemImpl(_, polarity, _, _, _, _) => Some(polarity),
5559 csearch::get_impl_polarity(cx, id)
5563 pub fn custom_coerce_unsized_kind<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
5564 -> CustomCoerceUnsized {
5565 memoized(&cx.custom_coerce_unsized_kinds, did, |did: DefId| {
5566 let (kind, src) = if did.krate != ast::LOCAL_CRATE {
5567 (csearch::get_custom_coerce_unsized_kind(cx, did), "external")
5575 cx.sess.bug(&format!("custom_coerce_unsized_kind: \
5576 {} impl `{}` is missing its kind",
5577 src, item_path_str(cx, did)));
5583 pub fn impl_or_trait_item<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5584 -> ImplOrTraitItem<'tcx> {
5585 lookup_locally_or_in_crate_store(
5586 "impl_or_trait_items", id, &cx.impl_or_trait_items,
5587 || csearch::get_impl_or_trait_item(cx, id))
5590 /// Returns the parameter index that the given associated type corresponds to.
5591 pub fn associated_type_parameter_index(cx: &ctxt,
5592 trait_def: &TraitDef,
5593 associated_type_id: ast::DefId)
5595 for type_parameter_def in &trait_def.generics.types {
5596 if type_parameter_def.def_id == associated_type_id {
5597 return type_parameter_def.index as usize
5600 cx.sess.bug("couldn't find associated type parameter index")
5603 pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId)
5604 -> Rc<Vec<ImplOrTraitItemId>> {
5605 lookup_locally_or_in_crate_store(
5606 "trait_item_def_ids", id, &cx.trait_item_def_ids,
5607 || Rc::new(csearch::get_trait_item_def_ids(&cx.sess.cstore, id)))
5610 /// Returns the trait-ref corresponding to a given impl, or None if it is
5611 /// an inherent impl.
5612 pub fn impl_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
5613 -> Option<TraitRef<'tcx>>
5615 lookup_locally_or_in_crate_store(
5616 "impl_trait_refs", id, &cx.impl_trait_refs,
5617 || csearch::get_impl_trait(cx, id))
5620 /// Returns whether this DefId refers to an impl
5621 pub fn is_impl<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId) -> bool {
5622 if id.krate == ast::LOCAL_CRATE {
5623 if let Some(ast_map::NodeItem(
5624 &ast::Item { node: ast::ItemImpl(..), .. })) = cx.map.find(id.node) {
5630 csearch::is_impl(&cx.sess.cstore, id)
5634 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
5635 tcx.def_map.borrow().get(&tr.ref_id).expect("no def-map entry for trait").def_id()
5638 pub fn try_add_builtin_trait(
5640 trait_def_id: ast::DefId,
5641 builtin_bounds: &mut EnumSet<BuiltinBound>)
5644 //! Checks whether `trait_ref` refers to one of the builtin
5645 //! traits, like `Send`, and adds the corresponding
5646 //! bound to the set `builtin_bounds` if so. Returns true if `trait_ref`
5647 //! is a builtin trait.
5649 match tcx.lang_items.to_builtin_kind(trait_def_id) {
5650 Some(bound) => { builtin_bounds.insert(bound); true }
5655 pub fn ty_to_def_id(ty: Ty) -> Option<ast::DefId> {
5658 Some(tt.principal_def_id()),
5670 pub struct VariantInfo<'tcx> {
5671 pub args: Vec<Ty<'tcx>>,
5672 pub arg_names: Option<Vec<ast::Name>>,
5673 pub ctor_ty: Option<Ty<'tcx>>,
5674 pub name: ast::Name,
5680 impl<'tcx> VariantInfo<'tcx> {
5682 /// Creates a new VariantInfo from the corresponding ast representation.
5684 /// Does not do any caching of the value in the type context.
5685 pub fn from_ast_variant(cx: &ctxt<'tcx>,
5686 ast_variant: &ast::Variant,
5687 discriminant: Disr) -> VariantInfo<'tcx> {
5688 let ctor_ty = node_id_to_type(cx, ast_variant.node.id);
5690 match ast_variant.node.kind {
5691 ast::TupleVariantKind(ref args) => {
5692 let arg_tys = if !args.is_empty() {
5693 // the regions in the argument types come from the
5694 // enum def'n, and hence will all be early bound
5695 ty::no_late_bound_regions(cx, &ty_fn_args(ctor_ty)).unwrap()
5700 return VariantInfo {
5703 ctor_ty: Some(ctor_ty),
5704 name: ast_variant.node.name.name,
5705 id: ast_util::local_def(ast_variant.node.id),
5706 disr_val: discriminant,
5707 vis: ast_variant.node.vis
5710 ast::StructVariantKind(ref struct_def) => {
5711 let fields: &[StructField] = &struct_def.fields;
5713 assert!(!fields.is_empty());
5715 let arg_tys = struct_def.fields.iter()
5716 .map(|field| node_id_to_type(cx, field.node.id)).collect();
5717 let arg_names = fields.iter().map(|field| {
5718 match field.node.kind {
5719 NamedField(ident, _) => ident.name,
5720 UnnamedField(..) => cx.sess.bug(
5721 "enum_variants: all fields in struct must have a name")
5725 return VariantInfo {
5727 arg_names: Some(arg_names),
5729 name: ast_variant.node.name.name,
5730 id: ast_util::local_def(ast_variant.node.id),
5731 disr_val: discriminant,
5732 vis: ast_variant.node.vis
5739 pub fn substd_enum_variants<'tcx>(cx: &ctxt<'tcx>,
5741 substs: &Substs<'tcx>)
5742 -> Vec<Rc<VariantInfo<'tcx>>> {
5743 enum_variants(cx, id).iter().map(|variant_info| {
5744 let substd_args = variant_info.args.iter()
5745 .map(|aty| aty.subst(cx, substs)).collect::<Vec<_>>();
5747 let substd_ctor_ty = variant_info.ctor_ty.subst(cx, substs);
5749 Rc::new(VariantInfo {
5751 ctor_ty: substd_ctor_ty,
5752 ..(**variant_info).clone()
5757 pub fn item_path_str(cx: &ctxt, id: ast::DefId) -> String {
5758 with_path(cx, id, |path| ast_map::path_to_string(path)).to_string()
5761 #[derive(Copy, Clone)]
5764 TraitDtor(DefId, bool)
5768 pub fn is_present(&self) -> bool {
5770 TraitDtor(..) => true,
5775 pub fn has_drop_flag(&self) -> bool {
5778 &TraitDtor(_, flag) => flag
5783 /* If struct_id names a struct with a dtor. */
5784 pub fn ty_dtor(cx: &ctxt, struct_id: DefId) -> DtorKind {
5785 match cx.destructor_for_type.borrow().get(&struct_id) {
5786 Some(&method_def_id) => {
5787 let flag = !has_attr(cx, struct_id, "unsafe_no_drop_flag");
5789 TraitDtor(method_def_id, flag)
5795 pub fn has_dtor(cx: &ctxt, struct_id: DefId) -> bool {
5796 cx.destructor_for_type.borrow().contains_key(&struct_id)
5799 pub fn with_path<T, F>(cx: &ctxt, id: ast::DefId, f: F) -> T where
5800 F: FnOnce(ast_map::PathElems) -> T,
5802 if id.krate == ast::LOCAL_CRATE {
5803 cx.map.with_path(id.node, f)
5805 f(csearch::get_item_path(cx, id).iter().cloned().chain(LinkedPath::empty()))
5809 pub fn enum_is_univariant(cx: &ctxt, id: ast::DefId) -> bool {
5810 enum_variants(cx, id).len() == 1
5813 pub fn type_is_empty(cx: &ctxt, ty: Ty) -> bool {
5815 TyEnum(did, _) => (*enum_variants(cx, did)).is_empty(),
5821 fn to_ty<'tcx>(&self, cx: &ctxt<'tcx>) -> Ty<'tcx>;
5822 fn i64_to_disr(&self, val: i64) -> Option<Disr>;
5823 fn u64_to_disr(&self, val: u64) -> Option<Disr>;
5824 fn disr_incr(&self, val: Disr) -> Option<Disr>;
5825 fn disr_string(&self, val: Disr) -> String;
5826 fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr;
5829 impl IntTypeExt for attr::IntType {
5830 fn to_ty<'tcx>(&self, cx: &ctxt<'tcx>) -> Ty<'tcx> {
5832 SignedInt(ast::TyI8) => cx.types.i8,
5833 SignedInt(ast::TyI16) => cx.types.i16,
5834 SignedInt(ast::TyI32) => cx.types.i32,
5835 SignedInt(ast::TyI64) => cx.types.i64,
5836 SignedInt(ast::TyIs) => cx.types.isize,
5837 UnsignedInt(ast::TyU8) => cx.types.u8,
5838 UnsignedInt(ast::TyU16) => cx.types.u16,
5839 UnsignedInt(ast::TyU32) => cx.types.u32,
5840 UnsignedInt(ast::TyU64) => cx.types.u64,
5841 UnsignedInt(ast::TyUs) => cx.types.usize,
5845 fn i64_to_disr(&self, val: i64) -> Option<Disr> {
5847 SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr),
5848 SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr),
5849 SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr),
5850 SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr),
5851 UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr),
5852 UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr),
5853 UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr),
5854 UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr),
5856 UnsignedInt(ast::TyUs) |
5857 SignedInt(ast::TyIs) => unreachable!(),
5861 fn u64_to_disr(&self, val: u64) -> Option<Disr> {
5863 SignedInt(ast::TyI8) => val.to_i8() .map(|v| v as Disr),
5864 SignedInt(ast::TyI16) => val.to_i16() .map(|v| v as Disr),
5865 SignedInt(ast::TyI32) => val.to_i32() .map(|v| v as Disr),
5866 SignedInt(ast::TyI64) => val.to_i64() .map(|v| v as Disr),
5867 UnsignedInt(ast::TyU8) => val.to_u8() .map(|v| v as Disr),
5868 UnsignedInt(ast::TyU16) => val.to_u16() .map(|v| v as Disr),
5869 UnsignedInt(ast::TyU32) => val.to_u32() .map(|v| v as Disr),
5870 UnsignedInt(ast::TyU64) => val.to_u64() .map(|v| v as Disr),
5872 UnsignedInt(ast::TyUs) |
5873 SignedInt(ast::TyIs) => unreachable!(),
5877 fn disr_incr(&self, val: Disr) -> Option<Disr> {
5879 ($e:expr) => { $e.and_then(|v|v.checked_add(1)).map(|v| v as Disr) }
5882 // SignedInt repr means we *want* to reinterpret the bits
5883 // treating the highest bit of Disr as a sign-bit, so
5884 // cast to i64 before range-checking.
5885 SignedInt(ast::TyI8) => add1!((val as i64).to_i8()),
5886 SignedInt(ast::TyI16) => add1!((val as i64).to_i16()),
5887 SignedInt(ast::TyI32) => add1!((val as i64).to_i32()),
5888 SignedInt(ast::TyI64) => add1!(Some(val as i64)),
5890 UnsignedInt(ast::TyU8) => add1!(val.to_u8()),
5891 UnsignedInt(ast::TyU16) => add1!(val.to_u16()),
5892 UnsignedInt(ast::TyU32) => add1!(val.to_u32()),
5893 UnsignedInt(ast::TyU64) => add1!(Some(val)),
5895 UnsignedInt(ast::TyUs) |
5896 SignedInt(ast::TyIs) => unreachable!(),
5900 // This returns a String because (1.) it is only used for
5901 // rendering an error message and (2.) a string can represent the
5902 // full range from `i64::MIN` through `u64::MAX`.
5903 fn disr_string(&self, val: Disr) -> String {
5905 SignedInt(ast::TyI8) => format!("{}", val as i8 ),
5906 SignedInt(ast::TyI16) => format!("{}", val as i16),
5907 SignedInt(ast::TyI32) => format!("{}", val as i32),
5908 SignedInt(ast::TyI64) => format!("{}", val as i64),
5909 UnsignedInt(ast::TyU8) => format!("{}", val as u8 ),
5910 UnsignedInt(ast::TyU16) => format!("{}", val as u16),
5911 UnsignedInt(ast::TyU32) => format!("{}", val as u32),
5912 UnsignedInt(ast::TyU64) => format!("{}", val as u64),
5914 UnsignedInt(ast::TyUs) |
5915 SignedInt(ast::TyIs) => unreachable!(),
5919 fn disr_wrap_incr(&self, val: Option<Disr>) -> Disr {
5921 ($e:expr) => { ($e).wrapping_add(1) as Disr }
5923 let val = val.unwrap_or(ty::INITIAL_DISCRIMINANT_VALUE);
5925 SignedInt(ast::TyI8) => add1!(val as i8 ),
5926 SignedInt(ast::TyI16) => add1!(val as i16),
5927 SignedInt(ast::TyI32) => add1!(val as i32),
5928 SignedInt(ast::TyI64) => add1!(val as i64),
5929 UnsignedInt(ast::TyU8) => add1!(val as u8 ),
5930 UnsignedInt(ast::TyU16) => add1!(val as u16),
5931 UnsignedInt(ast::TyU32) => add1!(val as u32),
5932 UnsignedInt(ast::TyU64) => add1!(val as u64),
5934 UnsignedInt(ast::TyUs) |
5935 SignedInt(ast::TyIs) => unreachable!(),
5940 /// Returns `(normalized_type, ty)`, where `normalized_type` is the
5941 /// IntType representation of one of {i64,i32,i16,i8,u64,u32,u16,u8},
5942 /// and `ty` is the original type (i.e. may include `isize` or
5944 pub fn enum_repr_type<'tcx>(cx: &ctxt<'tcx>,
5945 opt_hint: Option<&attr::ReprAttr>)
5946 -> (attr::IntType, Ty<'tcx>)
5948 let repr_type = match opt_hint {
5949 // Feed in the given type
5950 Some(&attr::ReprInt(_, int_t)) => int_t,
5951 // ... but provide sensible default if none provided
5953 // NB. Historically `fn enum_variants` generate i64 here, while
5954 // rustc_typeck::check would generate isize.
5955 _ => SignedInt(ast::TyIs),
5958 let repr_type_ty = repr_type.to_ty(cx);
5959 let repr_type = match repr_type {
5960 SignedInt(ast::TyIs) =>
5961 SignedInt(cx.sess.target.int_type),
5962 UnsignedInt(ast::TyUs) =>
5963 UnsignedInt(cx.sess.target.uint_type),
5967 (repr_type, repr_type_ty)
5970 fn report_discrim_overflow(cx: &ctxt,
5973 repr_type: attr::IntType,
5975 let computed_value = repr_type.disr_wrap_incr(Some(prev_val));
5976 let computed_value = repr_type.disr_string(computed_value);
5977 let prev_val = repr_type.disr_string(prev_val);
5978 let repr_type = repr_type.to_ty(cx);
5979 span_err!(cx.sess, variant_span, E0370,
5980 "enum discriminant overflowed on value after {}: {}; \
5981 set explicitly via {} = {} if that is desired outcome",
5982 prev_val, repr_type, variant_name, computed_value);
5985 // This computes the discriminant values for the sequence of Variants
5986 // attached to a particular enum, taking into account the #[repr] (if
5987 // any) provided via the `opt_hint`.
5988 fn compute_enum_variants<'tcx>(cx: &ctxt<'tcx>,
5989 vs: &'tcx [P<ast::Variant>],
5990 opt_hint: Option<&attr::ReprAttr>)
5991 -> Vec<Rc<ty::VariantInfo<'tcx>>> {
5992 let mut variants: Vec<Rc<ty::VariantInfo>> = Vec::new();
5993 let mut prev_disr_val: Option<ty::Disr> = None;
5995 let (repr_type, repr_type_ty) = ty::enum_repr_type(cx, opt_hint);
5998 // If the discriminant value is specified explicitly in the
5999 // enum, check whether the initialization expression is valid,
6000 // otherwise use the last value plus one.
6001 let current_disr_val;
6003 // This closure marks cases where, when an error occurs during
6004 // the computation, attempt to assign a (hopefully) fresh
6005 // value to avoid spurious error reports downstream.
6006 let attempt_fresh_value = move || -> Disr {
6007 repr_type.disr_wrap_incr(prev_disr_val)
6010 match v.node.disr_expr {
6012 debug!("disr expr, checking {}", pprust::expr_to_string(&**e));
6014 // check_expr (from check_const pass) doesn't guarantee
6015 // that the expression is in a form that eval_const_expr can
6016 // handle, so we may still get an internal compiler error
6018 // pnkfelix: The above comment was transcribed from
6019 // the version of this code taken from rustc_typeck.
6020 // Presumably the implication is that we need to deal
6021 // with such ICE's as they arise.
6023 // Since this can be called from `ty::enum_variants`
6024 // anyway, best thing is to make `eval_const_expr`
6025 // more robust (on case-by-case basis).
6027 match const_eval::eval_const_expr_partial(cx, &**e, Some(repr_type_ty)) {
6028 Ok(const_eval::const_int(val)) => current_disr_val = val as Disr,
6029 Ok(const_eval::const_uint(val)) => current_disr_val = val as Disr,
6031 let sign_desc = if repr_type.is_signed() { "signed" } else { "unsigned" };
6032 span_err!(cx.sess, e.span, E0079,
6033 "expected {} integer constant",
6035 current_disr_val = attempt_fresh_value();
6038 span_err!(cx.sess, err.span, E0080,
6039 "constant evaluation error: {}",
6041 current_disr_val = attempt_fresh_value();
6046 current_disr_val = match prev_disr_val {
6047 Some(prev_disr_val) => {
6048 if let Some(v) = repr_type.disr_incr(prev_disr_val) {
6051 report_discrim_overflow(cx, v.span, v.node.name.as_str(),
6052 repr_type, prev_disr_val);
6053 attempt_fresh_value()
6056 None => ty::INITIAL_DISCRIMINANT_VALUE
6061 let variant_info = Rc::new(VariantInfo::from_ast_variant(cx, &**v, current_disr_val));
6062 prev_disr_val = Some(current_disr_val);
6064 variants.push(variant_info);
6070 pub fn enum_variants<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId)
6071 -> Rc<Vec<Rc<VariantInfo<'tcx>>>> {
6072 memoized(&cx.enum_var_cache, id, |id: ast::DefId| {
6073 if ast::LOCAL_CRATE != id.krate {
6074 Rc::new(csearch::get_enum_variants(cx, id))
6076 match cx.map.get(id.node) {
6077 ast_map::NodeItem(ref item) => {
6079 ast::ItemEnum(ref enum_definition, _) => {
6080 Rc::new(compute_enum_variants(
6082 &enum_definition.variants,
6083 lookup_repr_hints(cx, id).get(0)))
6086 cx.sess.bug("enum_variants: id not bound to an enum")
6090 _ => cx.sess.bug("enum_variants: id not bound to an enum")
6096 // Returns information about the enum variant with the given ID:
6097 pub fn enum_variant_with_id<'tcx>(cx: &ctxt<'tcx>,
6098 enum_id: ast::DefId,
6099 variant_id: ast::DefId)
6100 -> Rc<VariantInfo<'tcx>> {
6101 enum_variants(cx, enum_id).iter()
6102 .find(|variant| variant.id == variant_id)
6103 .expect("enum_variant_with_id(): no variant exists with that ID")
6108 // If the given item is in an external crate, looks up its type and adds it to
6109 // the type cache. Returns the type parameters and type.
6110 pub fn lookup_item_type<'tcx>(cx: &ctxt<'tcx>,
6112 -> TypeScheme<'tcx> {
6113 lookup_locally_or_in_crate_store(
6114 "tcache", did, &cx.tcache,
6115 || csearch::get_type(cx, did))
6118 /// Given the did of a trait, returns its canonical trait ref.
6119 pub fn lookup_trait_def<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
6120 -> &'tcx TraitDef<'tcx> {
6121 lookup_locally_or_in_crate_store(
6122 "trait_defs", did, &cx.trait_defs,
6123 || cx.arenas.trait_defs.alloc(csearch::get_trait_def(cx, did))
6127 /// Given the did of an item, returns its full set of predicates.
6128 pub fn lookup_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
6129 -> GenericPredicates<'tcx>
6131 lookup_locally_or_in_crate_store(
6132 "predicates", did, &cx.predicates,
6133 || csearch::get_predicates(cx, did))
6136 /// Given the did of a trait, returns its superpredicates.
6137 pub fn lookup_super_predicates<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId)
6138 -> GenericPredicates<'tcx>
6140 lookup_locally_or_in_crate_store(
6141 "super_predicates", did, &cx.super_predicates,
6142 || csearch::get_super_predicates(cx, did))
6145 pub fn predicates<'tcx>(
6148 bounds: &ParamBounds<'tcx>)
6149 -> Vec<Predicate<'tcx>>
6151 let mut vec = Vec::new();
6153 for builtin_bound in &bounds.builtin_bounds {
6154 match traits::trait_ref_for_builtin_bound(tcx, builtin_bound, param_ty) {
6155 Ok(trait_ref) => { vec.push(trait_ref.as_predicate()); }
6156 Err(ErrorReported) => { }
6160 for ®ion_bound in &bounds.region_bounds {
6161 // account for the binder being introduced below; no need to shift `param_ty`
6162 // because, at present at least, it can only refer to early-bound regions
6163 let region_bound = ty_fold::shift_region(region_bound, 1);
6164 vec.push(ty::Binder(ty::OutlivesPredicate(param_ty, region_bound)).as_predicate());
6167 for bound_trait_ref in &bounds.trait_bounds {
6168 vec.push(bound_trait_ref.as_predicate());
6171 for projection in &bounds.projection_bounds {
6172 vec.push(projection.as_predicate());
6178 /// Get the attributes of a definition.
6179 pub fn get_attrs<'tcx>(tcx: &'tcx ctxt, did: DefId)
6180 -> Cow<'tcx, [ast::Attribute]> {
6182 Cow::Borrowed(tcx.map.attrs(did.node))
6184 Cow::Owned(csearch::get_item_attrs(&tcx.sess.cstore, did))
6188 /// Determine whether an item is annotated with an attribute
6189 pub fn has_attr(tcx: &ctxt, did: DefId, attr: &str) -> bool {
6190 get_attrs(tcx, did).iter().any(|item| item.check_name(attr))
6193 /// Determine whether an item is annotated with `#[repr(packed)]`
6194 pub fn lookup_packed(tcx: &ctxt, did: DefId) -> bool {
6195 lookup_repr_hints(tcx, did).contains(&attr::ReprPacked)
6198 /// Determine whether an item is annotated with `#[simd]`
6199 pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
6200 has_attr(tcx, did, "simd")
6203 /// Obtain the representation annotation for a struct definition.
6204 pub fn lookup_repr_hints(tcx: &ctxt, did: DefId) -> Rc<Vec<attr::ReprAttr>> {
6205 memoized(&tcx.repr_hint_cache, did, |did: DefId| {
6206 Rc::new(if did.krate == LOCAL_CRATE {
6207 get_attrs(tcx, did).iter().flat_map(|meta| {
6208 attr::find_repr_attrs(tcx.sess.diagnostic(), meta).into_iter()
6211 csearch::get_repr_attrs(&tcx.sess.cstore, did)
6216 // Look up a field ID, whether or not it's local
6217 pub fn lookup_field_type_unsubstituted<'tcx>(tcx: &ctxt<'tcx>,
6221 if id.krate == ast::LOCAL_CRATE {
6222 node_id_to_type(tcx, id.node)
6224 let mut tcache = tcx.tcache.borrow_mut();
6225 tcache.entry(id).or_insert_with(|| csearch::get_field_type(tcx, struct_id, id)).ty
6230 // Look up a field ID, whether or not it's local
6231 // Takes a list of type substs in case the struct is generic
6232 pub fn lookup_field_type<'tcx>(tcx: &ctxt<'tcx>,
6235 substs: &Substs<'tcx>)
6237 lookup_field_type_unsubstituted(tcx, struct_id, id).subst(tcx, substs)
6240 // Look up the list of field names and IDs for a given struct.
6241 // Panics if the id is not bound to a struct.
6242 pub fn lookup_struct_fields(cx: &ctxt, did: ast::DefId) -> Vec<field_ty> {
6243 if did.krate == ast::LOCAL_CRATE {
6244 let struct_fields = cx.struct_fields.borrow();
6245 match struct_fields.get(&did) {
6246 Some(fields) => (**fields).clone(),
6249 &format!("ID not mapped to struct fields: {}",
6250 cx.map.node_to_string(did.node)));
6254 csearch::get_struct_fields(&cx.sess.cstore, did)
6258 pub fn is_tuple_struct(cx: &ctxt, did: ast::DefId) -> bool {
6259 let fields = lookup_struct_fields(cx, did);
6260 !fields.is_empty() && fields.iter().all(|f| f.name == token::special_names::unnamed_field)
6263 // Returns a list of fields corresponding to the struct's items. trans uses
6264 // this. Takes a list of substs with which to instantiate field types.
6265 pub fn struct_fields<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId, substs: &Substs<'tcx>)
6266 -> Vec<field<'tcx>> {
6267 lookup_struct_fields(cx, did).iter().map(|f| {
6271 ty: lookup_field_type(cx, did, f.id, substs),
6278 // Returns a list of fields corresponding to the tuple's items. trans uses
6280 pub fn tup_fields<'tcx>(v: &[Ty<'tcx>]) -> Vec<field<'tcx>> {
6281 v.iter().enumerate().map(|(i, &f)| {
6283 name: token::intern(&i.to_string()),
6292 /// Returns the deeply last field of nested structures, or the same type,
6293 /// if not a structure at all. Corresponds to the only possible unsized
6294 /// field, and its type can be used to determine unsizing strategy.
6295 pub fn struct_tail<'tcx>(cx: &ctxt<'tcx>, mut ty: Ty<'tcx>) -> Ty<'tcx> {
6296 while let TyStruct(def_id, substs) = ty.sty {
6297 match struct_fields(cx, def_id, substs).last() {
6298 Some(f) => ty = f.mt.ty,
6305 /// Same as applying struct_tail on `source` and `target`, but only
6306 /// keeps going as long as the two types are instances of the same
6307 /// structure definitions.
6308 /// For `(Foo<Foo<T>>, Foo<Trait>)`, the result will be `(Foo<T>, Trait)`,
6309 /// whereas struct_tail produces `T`, and `Trait`, respectively.
6310 pub fn struct_lockstep_tails<'tcx>(cx: &ctxt<'tcx>,
6313 -> (Ty<'tcx>, Ty<'tcx>) {
6314 let (mut a, mut b) = (source, target);
6315 while let (&TyStruct(a_did, a_substs), &TyStruct(b_did, b_substs)) = (&a.sty, &b.sty) {
6319 if let Some(a_f) = struct_fields(cx, a_did, a_substs).last() {
6320 if let Some(b_f) = struct_fields(cx, b_did, b_substs).last() {
6333 #[derive(Copy, Clone)]
6334 pub struct ClosureUpvar<'tcx> {
6340 // Returns a list of `ClosureUpvar`s for each upvar.
6341 pub fn closure_upvars<'tcx>(typer: &mc::Typer<'tcx>,
6342 closure_id: ast::DefId,
6343 substs: &Substs<'tcx>)
6344 -> Option<Vec<ClosureUpvar<'tcx>>>
6346 // Presently an unboxed closure type cannot "escape" out of a
6347 // function, so we will only encounter ones that originated in the
6348 // local crate or were inlined into it along with some function.
6349 // This may change if abstract return types of some sort are
6351 assert!(closure_id.krate == ast::LOCAL_CRATE);
6352 let tcx = typer.tcx();
6353 match tcx.freevars.borrow().get(&closure_id.node) {
6354 None => Some(vec![]),
6355 Some(ref freevars) => {
6358 let freevar_def_id = freevar.def.def_id();
6359 let freevar_ty = match typer.node_ty(freevar_def_id.node) {
6361 Err(()) => { return None; }
6363 let freevar_ty = freevar_ty.subst(tcx, substs);
6365 let upvar_id = ty::UpvarId {
6366 var_id: freevar_def_id.node,
6367 closure_expr_id: closure_id.node
6370 typer.upvar_capture(upvar_id).map(|capture| {
6371 let freevar_ref_ty = match capture {
6372 UpvarCapture::ByValue => {
6375 UpvarCapture::ByRef(borrow) => {
6377 tcx.mk_region(borrow.region),
6380 mutbl: borrow.kind.to_mutbl_lossy(),
6397 // Returns the repeat count for a repeating vector expression.
6398 pub fn eval_repeat_count(tcx: &ctxt, count_expr: &ast::Expr) -> usize {
6399 match const_eval::eval_const_expr_partial(tcx, count_expr, Some(tcx.types.usize)) {
6401 let found = match val {
6402 const_eval::const_uint(count) => return count as usize,
6403 const_eval::const_int(count) if count >= 0 => return count as usize,
6404 const_eval::const_int(_) => "negative integer",
6405 const_eval::const_float(_) => "float",
6406 const_eval::const_str(_) => "string",
6407 const_eval::const_bool(_) => "boolean",
6408 const_eval::const_binary(_) => "binary array",
6409 const_eval::Struct(..) => "struct",
6410 const_eval::Tuple(_) => "tuple"
6412 span_err!(tcx.sess, count_expr.span, E0306,
6413 "expected positive integer for repeat count, found {}",
6417 let err_description = err.description();
6418 let found = match count_expr.node {
6419 ast::ExprPath(None, ast::Path {
6423 }) if segments.len() == 1 =>
6424 format!("{}", "found variable"),
6426 format!("but {}", err_description),
6428 span_err!(tcx.sess, count_expr.span, E0307,
6429 "expected constant integer for repeat count, {}",
6436 // Iterate over a type parameter's bounded traits and any supertraits
6437 // of those traits, ignoring kinds.
6438 // Here, the supertraits are the transitive closure of the supertrait
6439 // relation on the supertraits from each bounded trait's constraint
6441 pub fn each_bound_trait_and_supertraits<'tcx, F>(tcx: &ctxt<'tcx>,
6442 bounds: &[PolyTraitRef<'tcx>],
6445 F: FnMut(PolyTraitRef<'tcx>) -> bool,
6447 for bound_trait_ref in traits::transitive_bounds(tcx, bounds) {
6448 if !f(bound_trait_ref) {
6455 /// Given a set of predicates that apply to an object type, returns
6456 /// the region bounds that the (erased) `Self` type must
6457 /// outlive. Precisely *because* the `Self` type is erased, the
6458 /// parameter `erased_self_ty` must be supplied to indicate what type
6459 /// has been used to represent `Self` in the predicates
6460 /// themselves. This should really be a unique type; `FreshTy(0)` is a
6463 /// Requires that trait definitions have been processed so that we can
6464 /// elaborate predicates and walk supertraits.
6465 pub fn required_region_bounds<'tcx>(tcx: &ctxt<'tcx>,
6466 erased_self_ty: Ty<'tcx>,
6467 predicates: Vec<ty::Predicate<'tcx>>)
6470 debug!("required_region_bounds(erased_self_ty={:?}, predicates={:?})",
6474 assert!(!erased_self_ty.has_escaping_regions());
6476 traits::elaborate_predicates(tcx, predicates)
6477 .filter_map(|predicate| {
6479 ty::Predicate::Projection(..) |
6480 ty::Predicate::Trait(..) |
6481 ty::Predicate::Equate(..) |
6482 ty::Predicate::RegionOutlives(..) => {
6485 ty::Predicate::TypeOutlives(ty::Binder(ty::OutlivesPredicate(t, r))) => {
6486 // Search for a bound of the form `erased_self_ty
6487 // : 'a`, but be wary of something like `for<'a>
6488 // erased_self_ty : 'a` (we interpret a
6489 // higher-ranked bound like that as 'static,
6490 // though at present the code in `fulfill.rs`
6491 // considers such bounds to be unsatisfiable, so
6492 // it's kind of a moot point since you could never
6493 // construct such an object, but this seems
6494 // correct even if that code changes).
6495 if t == erased_self_ty && !r.has_escaping_regions() {
6496 if r.has_escaping_regions() {
6510 pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> {
6511 lookup_locally_or_in_crate_store(
6512 "item_variance_map", item_id, &tcx.item_variance_map,
6513 || Rc::new(csearch::get_item_variances(&tcx.sess.cstore, item_id)))
6516 pub fn trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) -> bool {
6517 populate_implementations_for_trait_if_necessary(tcx, trait_def_id);
6519 let def = lookup_trait_def(tcx, trait_def_id);
6520 def.flags.get().intersects(TraitFlags::HAS_DEFAULT_IMPL)
6523 /// Records a trait-to-implementation mapping.
6524 pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) {
6525 let def = lookup_trait_def(tcx, trait_def_id);
6526 def.flags.set(def.flags.get() | TraitFlags::HAS_DEFAULT_IMPL)
6529 /// Load primitive inherent implementations if necessary
6530 pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt,
6531 primitive_def_id: ast::DefId) {
6532 if primitive_def_id.krate == LOCAL_CRATE {
6536 if tcx.populated_external_primitive_impls.borrow().contains(&primitive_def_id) {
6540 debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}",
6543 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, primitive_def_id);
6545 // Store the implementation info.
6546 tcx.impl_items.borrow_mut().insert(primitive_def_id, impl_items);
6547 tcx.populated_external_primitive_impls.borrow_mut().insert(primitive_def_id);
6550 /// Populates the type context with all the inherent implementations for
6551 /// the given type if necessary.
6552 pub fn populate_inherent_implementations_for_type_if_necessary(tcx: &ctxt,
6553 type_id: ast::DefId) {
6554 if type_id.krate == LOCAL_CRATE {
6558 if tcx.populated_external_types.borrow().contains(&type_id) {
6562 debug!("populate_inherent_implementations_for_type_if_necessary: searching for {:?}", type_id);
6564 let mut inherent_impls = Vec::new();
6565 csearch::each_inherent_implementation_for_type(&tcx.sess.cstore, type_id, |impl_def_id| {
6566 // Record the implementation.
6567 inherent_impls.push(impl_def_id);
6569 // Store the implementation info.
6570 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, impl_def_id);
6571 tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items);
6574 tcx.inherent_impls.borrow_mut().insert(type_id, Rc::new(inherent_impls));
6575 tcx.populated_external_types.borrow_mut().insert(type_id);
6578 /// Populates the type context with all the implementations for the given
6579 /// trait if necessary.
6580 pub fn populate_implementations_for_trait_if_necessary(tcx: &ctxt, trait_id: ast::DefId) {
6581 if trait_id.krate == LOCAL_CRATE {
6585 let def = lookup_trait_def(tcx, trait_id);
6586 if def.flags.get().intersects(TraitFlags::IMPLS_VALID) {
6590 debug!("populate_implementations_for_trait_if_necessary: searching for {:?}", def);
6592 if csearch::is_defaulted_trait(&tcx.sess.cstore, trait_id) {
6593 record_trait_has_default_impl(tcx, trait_id);
6596 csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id, |implementation_def_id| {
6597 let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id);
6598 let trait_ref = impl_trait_ref(tcx, implementation_def_id).unwrap();
6599 // Record the trait->implementation mapping.
6600 def.record_impl(tcx, implementation_def_id, trait_ref);
6602 // For any methods that use a default implementation, add them to
6603 // the map. This is a bit unfortunate.
6604 for impl_item_def_id in &impl_items {
6605 let method_def_id = impl_item_def_id.def_id();
6606 match impl_or_trait_item(tcx, method_def_id) {
6607 MethodTraitItem(method) => {
6608 if let Some(source) = method.provided_source {
6609 tcx.provided_method_sources
6611 .insert(method_def_id, source);
6618 // Store the implementation info.
6619 tcx.impl_items.borrow_mut().insert(implementation_def_id, impl_items);
6622 def.flags.set(def.flags.get() | TraitFlags::IMPLS_VALID);
6625 /// Given the def_id of an impl, return the def_id of the trait it implements.
6626 /// If it implements no trait, return `None`.
6627 pub fn trait_id_of_impl(tcx: &ctxt,
6629 -> Option<ast::DefId> {
6630 ty::impl_trait_ref(tcx, def_id).map(|tr| tr.def_id)
6633 /// If the given def ID describes a method belonging to an impl, return the
6634 /// ID of the impl that the method belongs to. Otherwise, return `None`.
6635 pub fn impl_of_method(tcx: &ctxt, def_id: ast::DefId)
6636 -> Option<ast::DefId> {
6637 if def_id.krate != LOCAL_CRATE {
6638 return match csearch::get_impl_or_trait_item(tcx,
6639 def_id).container() {
6640 TraitContainer(_) => None,
6641 ImplContainer(def_id) => Some(def_id),
6644 match tcx.impl_or_trait_items.borrow().get(&def_id).cloned() {
6645 Some(trait_item) => {
6646 match trait_item.container() {
6647 TraitContainer(_) => None,
6648 ImplContainer(def_id) => Some(def_id),
6655 /// If the given def ID describes an item belonging to a trait (either a
6656 /// default method or an implementation of a trait method), return the ID of
6657 /// the trait that the method belongs to. Otherwise, return `None`.
6658 pub fn trait_of_item(tcx: &ctxt, def_id: ast::DefId) -> Option<ast::DefId> {
6659 if def_id.krate != LOCAL_CRATE {
6660 return csearch::get_trait_of_item(&tcx.sess.cstore, def_id, tcx);
6662 match tcx.impl_or_trait_items.borrow().get(&def_id).cloned() {
6663 Some(impl_or_trait_item) => {
6664 match impl_or_trait_item.container() {
6665 TraitContainer(def_id) => Some(def_id),
6666 ImplContainer(def_id) => trait_id_of_impl(tcx, def_id),
6673 /// If the given def ID describes an item belonging to a trait, (either a
6674 /// default method or an implementation of a trait method), return the ID of
6675 /// the method inside trait definition (this means that if the given def ID
6676 /// is already that of the original trait method, then the return value is
6678 /// Otherwise, return `None`.
6679 pub fn trait_item_of_item(tcx: &ctxt, def_id: ast::DefId)
6680 -> Option<ImplOrTraitItemId> {
6681 let impl_item = match tcx.impl_or_trait_items.borrow().get(&def_id) {
6682 Some(m) => m.clone(),
6683 None => return None,
6685 let name = impl_item.name();
6686 match trait_of_item(tcx, def_id) {
6687 Some(trait_did) => {
6688 let trait_items = ty::trait_items(tcx, trait_did);
6690 .position(|m| m.name() == name)
6691 .map(|idx| ty::trait_item(tcx, trait_did, idx).id())
6697 /// Creates a hash of the type `Ty` which will be the same no matter what crate
6698 /// context it's calculated within. This is used by the `type_id` intrinsic.
6699 pub fn hash_crate_independent<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh) -> u64 {
6700 let mut state = SipHasher::new();
6701 helper(tcx, ty, svh, &mut state);
6702 return state.finish();
6704 fn helper<'tcx>(tcx: &ctxt<'tcx>, ty: Ty<'tcx>, svh: &Svh,
6705 state: &mut SipHasher) {
6706 macro_rules! byte { ($b:expr) => { ($b as u8).hash(state) } }
6707 macro_rules! hash { ($e:expr) => { $e.hash(state) } }
6709 let region = |state: &mut SipHasher, r: Region| {
6712 ReLateBound(db, BrAnon(i)) => {
6722 tcx.sess.bug("unexpected region found when hashing a type")
6726 let did = |state: &mut SipHasher, did: DefId| {
6727 let h = if ast_util::is_local(did) {
6730 tcx.sess.cstore.get_crate_hash(did.krate)
6732 h.as_str().hash(state);
6733 did.node.hash(state);
6735 let mt = |state: &mut SipHasher, mt: mt| {
6736 mt.mutbl.hash(state);
6738 let fn_sig = |state: &mut SipHasher, sig: &Binder<FnSig<'tcx>>| {
6739 let sig = anonymize_late_bound_regions(tcx, sig).0;
6740 for a in &sig.inputs { helper(tcx, *a, svh, state); }
6741 if let ty::FnConverging(output) = sig.output {
6742 helper(tcx, output, svh, state);
6745 maybe_walk_ty(ty, |ty| {
6787 TyBareFn(opt_def_id, ref b) => {
6792 fn_sig(state, &b.sig);
6795 TyTrait(ref data) => {
6797 did(state, data.principal_def_id());
6800 let principal = anonymize_late_bound_regions(tcx, &data.principal).0;
6801 for subty in &principal.substs.types {
6802 helper(tcx, subty, svh, state);
6811 TyTuple(ref inner) => {
6819 hash!(token::get_name(p.name));
6821 TyInfer(_) => unreachable!(),
6822 TyError => byte!(21),
6823 TyClosure(d, _) => {
6827 TyProjection(ref data) => {
6829 did(state, data.trait_ref.def_id);
6830 hash!(token::get_name(data.item_name));
6838 impl fmt::Debug for Variance {
6839 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
6840 f.write_str(match *self {
6842 Contravariant => "-",
6849 /// Construct a parameter environment suitable for static contexts or other contexts where there
6850 /// are no free type/lifetime parameters in scope.
6851 pub fn empty_parameter_environment<'a,'tcx>(cx: &'a ctxt<'tcx>) -> ParameterEnvironment<'a,'tcx> {
6852 ty::ParameterEnvironment { tcx: cx,
6853 free_substs: Substs::empty(),
6854 caller_bounds: Vec::new(),
6855 implicit_region_bound: ty::ReEmpty,
6856 selection_cache: traits::SelectionCache::new(), }
6859 /// Constructs and returns a substitution that can be applied to move from
6860 /// the "outer" view of a type or method to the "inner" view.
6861 /// In general, this means converting from bound parameters to
6862 /// free parameters. Since we currently represent bound/free type
6863 /// parameters in the same way, this only has an effect on regions.
6864 pub fn construct_free_substs<'a,'tcx>(
6865 tcx: &'a ctxt<'tcx>,
6866 generics: &Generics<'tcx>,
6867 free_id: ast::NodeId)
6871 let mut types = VecPerParamSpace::empty();
6872 push_types_from_defs(tcx, &mut types, generics.types.as_slice());
6874 let free_id_outlive = region::DestructionScopeData::new(free_id);
6876 // map bound 'a => free 'a
6877 let mut regions = VecPerParamSpace::empty();
6878 push_region_params(&mut regions, free_id_outlive, generics.regions.as_slice());
6882 regions: subst::NonerasedRegions(regions)
6885 fn push_region_params(regions: &mut VecPerParamSpace<ty::Region>,
6886 all_outlive_extent: region::DestructionScopeData,
6887 region_params: &[RegionParameterDef])
6889 for r in region_params {
6890 regions.push(r.space, ty::free_region_from_def(all_outlive_extent, r));
6894 fn push_types_from_defs<'tcx>(tcx: &ty::ctxt<'tcx>,
6895 types: &mut VecPerParamSpace<Ty<'tcx>>,
6896 defs: &[TypeParameterDef<'tcx>]) {
6898 debug!("construct_parameter_environment(): push_types_from_defs: def={:?}",
6900 let ty = ty::mk_param_from_def(tcx, def);
6901 types.push(def.space, ty);
6906 /// See `ParameterEnvironment` struct def'n for details
6907 pub fn construct_parameter_environment<'a,'tcx>(
6908 tcx: &'a ctxt<'tcx>,
6910 generics: &ty::Generics<'tcx>,
6911 generic_predicates: &ty::GenericPredicates<'tcx>,
6912 free_id: ast::NodeId)
6913 -> ParameterEnvironment<'a, 'tcx>
6916 // Construct the free substs.
6919 let free_substs = construct_free_substs(tcx, generics, free_id);
6920 let free_id_outlive = region::DestructionScopeData::new(free_id);
6923 // Compute the bounds on Self and the type parameters.
6926 let bounds = generic_predicates.instantiate(tcx, &free_substs);
6927 let bounds = liberate_late_bound_regions(tcx, free_id_outlive, &ty::Binder(bounds));
6928 let predicates = bounds.predicates.into_vec();
6930 debug!("construct_parameter_environment: free_id={:?} free_subst={:?} predicates={:?}",
6936 // Finally, we have to normalize the bounds in the environment, in
6937 // case they contain any associated type projections. This process
6938 // can yield errors if the put in illegal associated types, like
6939 // `<i32 as Foo>::Bar` where `i32` does not implement `Foo`. We
6940 // report these errors right here; this doesn't actually feel
6941 // right to me, because constructing the environment feels like a
6942 // kind of a "idempotent" action, but I'm not sure where would be
6943 // a better place. In practice, we construct environments for
6944 // every fn once during type checking, and we'll abort if there
6945 // are any errors at that point, so after type checking you can be
6946 // sure that this will succeed without errors anyway.
6949 let unnormalized_env = ty::ParameterEnvironment {
6951 free_substs: free_substs,
6952 implicit_region_bound: ty::ReScope(free_id_outlive.to_code_extent()),
6953 caller_bounds: predicates,
6954 selection_cache: traits::SelectionCache::new(),
6957 let cause = traits::ObligationCause::misc(span, free_id);
6958 traits::normalize_param_env_or_error(unnormalized_env, cause)
6962 pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
6964 ast::MutMutable => MutBorrow,
6965 ast::MutImmutable => ImmBorrow,
6969 /// Returns a mutability `m` such that an `&m T` pointer could be used to obtain this borrow
6970 /// kind. Because borrow kinds are richer than mutabilities, we sometimes have to pick a
6971 /// mutability that is stronger than necessary so that it at least *would permit* the borrow in
6973 pub fn to_mutbl_lossy(self) -> ast::Mutability {
6975 MutBorrow => ast::MutMutable,
6976 ImmBorrow => ast::MutImmutable,
6978 // We have no type corresponding to a unique imm borrow, so
6979 // use `&mut`. It gives all the capabilities of an `&uniq`
6980 // and hence is a safe "over approximation".
6981 UniqueImmBorrow => ast::MutMutable,
6985 pub fn to_user_str(&self) -> &'static str {
6987 MutBorrow => "mutable",
6988 ImmBorrow => "immutable",
6989 UniqueImmBorrow => "uniquely immutable",
6994 impl<'tcx> ctxt<'tcx> {
6995 pub fn is_method_call(&self, expr_id: ast::NodeId) -> bool {
6996 self.method_map.borrow().contains_key(&MethodCall::expr(expr_id))
6999 pub fn upvar_capture(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarCapture> {
7000 Some(self.upvar_capture_map.borrow().get(&upvar_id).unwrap().clone())
7004 impl<'a,'tcx> mc::Typer<'tcx> for ParameterEnvironment<'a,'tcx> {
7005 fn node_ty(&self, id: ast::NodeId) -> mc::McResult<Ty<'tcx>> {
7006 Ok(ty::node_id_to_type(self.tcx, id))
7009 fn expr_ty_adjusted(&self, expr: &ast::Expr) -> mc::McResult<Ty<'tcx>> {
7010 Ok(ty::expr_ty_adjusted(self.tcx, expr))
7013 fn node_method_ty(&self, method_call: ty::MethodCall) -> Option<Ty<'tcx>> {
7014 self.tcx.method_map.borrow().get(&method_call).map(|method| method.ty)
7017 fn node_method_origin(&self, method_call: ty::MethodCall)
7018 -> Option<ty::MethodOrigin<'tcx>>
7020 self.tcx.method_map.borrow().get(&method_call).map(|method| method.origin.clone())
7023 fn adjustments(&self) -> &RefCell<NodeMap<ty::AutoAdjustment<'tcx>>> {
7024 &self.tcx.adjustments
7027 fn is_method_call(&self, id: ast::NodeId) -> bool {
7028 self.tcx.is_method_call(id)
7031 fn temporary_scope(&self, rvalue_id: ast::NodeId) -> Option<region::CodeExtent> {
7032 self.tcx.region_maps.temporary_scope(rvalue_id)
7035 fn upvar_capture(&self, upvar_id: ty::UpvarId) -> Option<ty::UpvarCapture> {
7036 self.tcx.upvar_capture(upvar_id)
7039 fn type_moves_by_default(&self, span: Span, ty: Ty<'tcx>) -> bool {
7040 type_moves_by_default(self, span, ty)
7044 impl<'a,'tcx> ClosureTyper<'tcx> for ty::ParameterEnvironment<'a,'tcx> {
7045 fn param_env<'b>(&'b self) -> &'b ty::ParameterEnvironment<'b,'tcx> {
7049 fn closure_kind(&self,
7051 -> Option<ty::ClosureKind>
7053 Some(self.tcx.closure_kind(def_id))
7056 fn closure_type(&self,
7058 substs: &subst::Substs<'tcx>)
7059 -> ty::ClosureTy<'tcx>
7061 self.tcx.closure_type(def_id, substs)
7064 fn closure_upvars(&self,
7066 substs: &Substs<'tcx>)
7067 -> Option<Vec<ClosureUpvar<'tcx>>>
7069 closure_upvars(self, def_id, substs)
7074 /// The category of explicit self.
7075 #[derive(Clone, Copy, Eq, PartialEq, Debug)]
7076 pub enum ExplicitSelfCategory {
7077 StaticExplicitSelfCategory,
7078 ByValueExplicitSelfCategory,
7079 ByReferenceExplicitSelfCategory(Region, ast::Mutability),
7080 ByBoxExplicitSelfCategory,
7083 /// Pushes all the lifetimes in the given type onto the given list. A
7084 /// "lifetime in a type" is a lifetime specified by a reference or a lifetime
7085 /// in a list of type substitutions. This does *not* traverse into nominal
7086 /// types, nor does it resolve fictitious types.
7087 pub fn accumulate_lifetimes_in_type(accumulator: &mut Vec<ty::Region>,
7091 TyRef(region, _) => {
7092 accumulator.push(*region)
7095 accumulator.push_all(t.principal.0.substs.regions().as_slice());
7098 TyStruct(_, substs) => {
7099 accum_substs(accumulator, substs);
7101 TyClosure(_, substs) => {
7102 accum_substs(accumulator, substs);
7124 fn accum_substs(accumulator: &mut Vec<Region>, substs: &Substs) {
7125 match substs.regions {
7126 subst::ErasedRegions => {}
7127 subst::NonerasedRegions(ref regions) => {
7128 for region in regions {
7129 accumulator.push(*region)
7136 /// A free variable referred to in a function.
7137 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
7138 pub struct Freevar {
7139 /// The variable being accessed free.
7142 // First span where it is accessed (there can be multiple).
7146 pub type FreevarMap = NodeMap<Vec<Freevar>>;
7148 pub type CaptureModeMap = NodeMap<ast::CaptureClause>;
7150 // Trait method resolution
7151 pub type TraitMap = NodeMap<Vec<DefId>>;
7153 // Map from the NodeId of a glob import to a list of items which are actually
7155 pub type GlobMap = HashMap<NodeId, HashSet<Name>>;
7157 pub fn with_freevars<T, F>(tcx: &ty::ctxt, fid: ast::NodeId, f: F) -> T where
7158 F: FnOnce(&[Freevar]) -> T,
7160 match tcx.freevars.borrow().get(&fid) {
7162 Some(d) => f(&d[..])
7166 impl<'tcx> AutoAdjustment<'tcx> {
7167 pub fn is_identity(&self) -> bool {
7169 AdjustReifyFnPointer |
7170 AdjustUnsafeFnPointer => false,
7171 AdjustDerefRef(ref r) => r.is_identity(),
7176 impl<'tcx> AutoDerefRef<'tcx> {
7177 pub fn is_identity(&self) -> bool {
7178 self.autoderefs == 0 && self.unsize.is_none() && self.autoref.is_none()
7182 /// Replace any late-bound regions bound in `value` with free variants attached to scope-id
7184 pub fn liberate_late_bound_regions<'tcx, T>(
7185 tcx: &ty::ctxt<'tcx>,
7186 all_outlive_scope: region::DestructionScopeData,
7189 where T : TypeFoldable<'tcx>
7191 ty_fold::replace_late_bound_regions(
7193 |br| ty::ReFree(ty::FreeRegion{scope: all_outlive_scope, bound_region: br})).0
7196 pub fn count_late_bound_regions<'tcx, T>(
7197 tcx: &ty::ctxt<'tcx>,
7200 where T : TypeFoldable<'tcx>
7202 let (_, skol_map) = ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic);
7206 pub fn binds_late_bound_regions<'tcx, T>(
7207 tcx: &ty::ctxt<'tcx>,
7210 where T : TypeFoldable<'tcx>
7212 count_late_bound_regions(tcx, value) > 0
7215 /// Flattens two binding levels into one. So `for<'a> for<'b> Foo`
7216 /// becomes `for<'a,'b> Foo`.
7217 pub fn flatten_late_bound_regions<'tcx, T>(
7218 tcx: &ty::ctxt<'tcx>,
7219 bound2_value: &Binder<Binder<T>>)
7221 where T: TypeFoldable<'tcx>
7223 let bound0_value = bound2_value.skip_binder().skip_binder();
7224 let value = ty_fold::fold_regions(tcx, bound0_value, |region, current_depth| {
7226 ty::ReLateBound(debruijn, br) if debruijn.depth >= current_depth => {
7227 // should be true if no escaping regions from bound2_value
7228 assert!(debruijn.depth - current_depth <= 1);
7229 ty::ReLateBound(DebruijnIndex::new(current_depth), br)
7239 pub fn no_late_bound_regions<'tcx, T>(
7240 tcx: &ty::ctxt<'tcx>,
7243 where T : TypeFoldable<'tcx>
7245 if binds_late_bound_regions(tcx, value) {
7248 Some(value.0.clone())
7252 /// Replace any late-bound regions bound in `value` with `'static`. Useful in trans but also
7253 /// method lookup and a few other places where precise region relationships are not required.
7254 pub fn erase_late_bound_regions<'tcx, T>(
7255 tcx: &ty::ctxt<'tcx>,
7258 where T : TypeFoldable<'tcx>
7260 ty_fold::replace_late_bound_regions(tcx, value, |_| ty::ReStatic).0
7263 /// Rewrite any late-bound regions so that they are anonymous. Region numbers are
7264 /// assigned starting at 1 and increasing monotonically in the order traversed
7265 /// by the fold operation.
7267 /// The chief purpose of this function is to canonicalize regions so that two
7268 /// `FnSig`s or `TraitRef`s which are equivalent up to region naming will become
7269 /// structurally identical. For example, `for<'a, 'b> fn(&'a isize, &'b isize)` and
7270 /// `for<'a, 'b> fn(&'b isize, &'a isize)` will become identical after anonymization.
7271 pub fn anonymize_late_bound_regions<'tcx, T>(
7275 where T : TypeFoldable<'tcx>,
7277 let mut counter = 0;
7278 ty::Binder(ty_fold::replace_late_bound_regions(tcx, sig, |_| {
7280 ReLateBound(ty::DebruijnIndex::new(1), BrAnon(counter))
7284 impl DebruijnIndex {
7285 pub fn new(depth: u32) -> DebruijnIndex {
7287 DebruijnIndex { depth: depth }
7290 pub fn shifted(&self, amount: u32) -> DebruijnIndex {
7291 DebruijnIndex { depth: self.depth + amount }
7295 impl<'tcx> fmt::Debug for AutoAdjustment<'tcx> {
7296 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7298 AdjustReifyFnPointer => {
7299 write!(f, "AdjustReifyFnPointer")
7301 AdjustUnsafeFnPointer => {
7302 write!(f, "AdjustUnsafeFnPointer")
7304 AdjustDerefRef(ref data) => {
7305 write!(f, "{:?}", data)
7311 impl<'tcx> fmt::Debug for AutoDerefRef<'tcx> {
7312 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7313 write!(f, "AutoDerefRef({}, unsize={:?}, {:?})",
7314 self.autoderefs, self.unsize, self.autoref)
7318 impl<'tcx> fmt::Debug for TraitTy<'tcx> {
7319 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7320 write!(f, "TraitTy({:?},{:?})",
7326 impl<'tcx> fmt::Debug for ty::Predicate<'tcx> {
7327 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7329 Predicate::Trait(ref a) => write!(f, "{:?}", a),
7330 Predicate::Equate(ref pair) => write!(f, "{:?}", pair),
7331 Predicate::RegionOutlives(ref pair) => write!(f, "{:?}", pair),
7332 Predicate::TypeOutlives(ref pair) => write!(f, "{:?}", pair),
7333 Predicate::Projection(ref pair) => write!(f, "{:?}", pair),
7338 pub fn make_substs_for_receiver_types<'tcx>(tcx: &ty::ctxt<'tcx>,
7339 trait_ref: &ty::TraitRef<'tcx>,
7340 method: &ty::Method<'tcx>)
7341 -> subst::Substs<'tcx>
7344 * Substitutes the values for the receiver's type parameters
7345 * that are found in method, leaving the method's type parameters
7349 let meth_tps: Vec<Ty> =
7350 method.generics.types.get_slice(subst::FnSpace)
7352 .map(|def| ty::mk_param_from_def(tcx, def))
7354 let meth_regions: Vec<ty::Region> =
7355 method.generics.regions.get_slice(subst::FnSpace)
7357 .map(|def| def.to_early_bound_region())
7359 trait_ref.substs.clone().with_method(meth_tps, meth_regions)
7362 #[derive(Copy, Clone)]
7363 pub enum CopyImplementationError {
7364 FieldDoesNotImplementCopy(ast::Name),
7365 VariantDoesNotImplementCopy(ast::Name),
7370 pub fn can_type_implement_copy<'a,'tcx>(param_env: &ParameterEnvironment<'a, 'tcx>,
7372 self_type: Ty<'tcx>)
7373 -> Result<(),CopyImplementationError>
7375 let tcx = param_env.tcx;
7377 let did = match self_type.sty {
7378 ty::TyStruct(struct_did, substs) => {
7379 let fields = ty::struct_fields(tcx, struct_did, substs);
7380 for field in &fields {
7381 if type_moves_by_default(param_env, span, field.mt.ty) {
7382 return Err(FieldDoesNotImplementCopy(field.name))
7387 ty::TyEnum(enum_did, substs) => {
7388 let enum_variants = ty::enum_variants(tcx, enum_did);
7389 for variant in enum_variants.iter() {
7390 for variant_arg_type in &variant.args {
7391 let substd_arg_type =
7392 variant_arg_type.subst(tcx, substs);
7393 if type_moves_by_default(param_env, span, substd_arg_type) {
7394 return Err(VariantDoesNotImplementCopy(variant.name))
7400 _ => return Err(TypeIsStructural),
7403 if ty::has_dtor(tcx, did) {
7404 return Err(TypeHasDestructor)
7410 // FIXME(#20298) -- all of these types basically walk various
7411 // structures to test whether types/regions are reachable with various
7412 // properties. It should be possible to express them in terms of one
7413 // common "walker" trait or something.
7415 pub trait RegionEscape {
7416 fn has_escaping_regions(&self) -> bool {
7417 self.has_regions_escaping_depth(0)
7420 fn has_regions_escaping_depth(&self, depth: u32) -> bool;
7423 impl<'tcx> RegionEscape for Ty<'tcx> {
7424 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7425 ty::type_escapes_depth(*self, depth)
7429 impl<'tcx> RegionEscape for Substs<'tcx> {
7430 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7431 self.types.has_regions_escaping_depth(depth) ||
7432 self.regions.has_regions_escaping_depth(depth)
7436 impl<'tcx,T:RegionEscape> RegionEscape for VecPerParamSpace<T> {
7437 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7438 self.iter_enumerated().any(|(space, _, t)| {
7439 if space == subst::FnSpace {
7440 t.has_regions_escaping_depth(depth+1)
7442 t.has_regions_escaping_depth(depth)
7448 impl<'tcx> RegionEscape for TypeScheme<'tcx> {
7449 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7450 self.ty.has_regions_escaping_depth(depth)
7454 impl RegionEscape for Region {
7455 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7456 self.escapes_depth(depth)
7460 impl<'tcx> RegionEscape for GenericPredicates<'tcx> {
7461 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7462 self.predicates.has_regions_escaping_depth(depth)
7466 impl<'tcx> RegionEscape for Predicate<'tcx> {
7467 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7469 Predicate::Trait(ref data) => data.has_regions_escaping_depth(depth),
7470 Predicate::Equate(ref data) => data.has_regions_escaping_depth(depth),
7471 Predicate::RegionOutlives(ref data) => data.has_regions_escaping_depth(depth),
7472 Predicate::TypeOutlives(ref data) => data.has_regions_escaping_depth(depth),
7473 Predicate::Projection(ref data) => data.has_regions_escaping_depth(depth),
7478 impl<'tcx,P:RegionEscape> RegionEscape for traits::Obligation<'tcx,P> {
7479 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7480 self.predicate.has_regions_escaping_depth(depth)
7484 impl<'tcx> RegionEscape for TraitRef<'tcx> {
7485 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7486 self.substs.types.iter().any(|t| t.has_regions_escaping_depth(depth)) ||
7487 self.substs.regions.has_regions_escaping_depth(depth)
7491 impl<'tcx> RegionEscape for subst::RegionSubsts {
7492 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7494 subst::ErasedRegions => false,
7495 subst::NonerasedRegions(ref r) => {
7496 r.iter().any(|t| t.has_regions_escaping_depth(depth))
7502 impl<'tcx,T:RegionEscape> RegionEscape for Binder<T> {
7503 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7504 self.0.has_regions_escaping_depth(depth + 1)
7508 impl<'tcx> RegionEscape for EquatePredicate<'tcx> {
7509 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7510 self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
7514 impl<'tcx> RegionEscape for TraitPredicate<'tcx> {
7515 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7516 self.trait_ref.has_regions_escaping_depth(depth)
7520 impl<T:RegionEscape,U:RegionEscape> RegionEscape for OutlivesPredicate<T,U> {
7521 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7522 self.0.has_regions_escaping_depth(depth) || self.1.has_regions_escaping_depth(depth)
7526 impl<'tcx> RegionEscape for ProjectionPredicate<'tcx> {
7527 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7528 self.projection_ty.has_regions_escaping_depth(depth) ||
7529 self.ty.has_regions_escaping_depth(depth)
7533 impl<'tcx> RegionEscape for ProjectionTy<'tcx> {
7534 fn has_regions_escaping_depth(&self, depth: u32) -> bool {
7535 self.trait_ref.has_regions_escaping_depth(depth)
7539 pub trait HasProjectionTypes {
7540 fn has_projection_types(&self) -> bool;
7543 impl<'tcx,T:HasProjectionTypes> HasProjectionTypes for Vec<T> {
7544 fn has_projection_types(&self) -> bool {
7545 self.iter().any(|p| p.has_projection_types())
7549 impl<'tcx,T:HasProjectionTypes> HasProjectionTypes for VecPerParamSpace<T> {
7550 fn has_projection_types(&self) -> bool {
7551 self.iter().any(|p| p.has_projection_types())
7555 impl<'tcx> HasProjectionTypes for ClosureTy<'tcx> {
7556 fn has_projection_types(&self) -> bool {
7557 self.sig.has_projection_types()
7561 impl<'tcx> HasProjectionTypes for ClosureUpvar<'tcx> {
7562 fn has_projection_types(&self) -> bool {
7563 self.ty.has_projection_types()
7567 impl<'tcx> HasProjectionTypes for ty::InstantiatedPredicates<'tcx> {
7568 fn has_projection_types(&self) -> bool {
7569 self.predicates.has_projection_types()
7573 impl<'tcx> HasProjectionTypes for Predicate<'tcx> {
7574 fn has_projection_types(&self) -> bool {
7576 Predicate::Trait(ref data) => data.has_projection_types(),
7577 Predicate::Equate(ref data) => data.has_projection_types(),
7578 Predicate::RegionOutlives(ref data) => data.has_projection_types(),
7579 Predicate::TypeOutlives(ref data) => data.has_projection_types(),
7580 Predicate::Projection(ref data) => data.has_projection_types(),
7585 impl<'tcx> HasProjectionTypes for TraitPredicate<'tcx> {
7586 fn has_projection_types(&self) -> bool {
7587 self.trait_ref.has_projection_types()
7591 impl<'tcx> HasProjectionTypes for EquatePredicate<'tcx> {
7592 fn has_projection_types(&self) -> bool {
7593 self.0.has_projection_types() || self.1.has_projection_types()
7597 impl HasProjectionTypes for Region {
7598 fn has_projection_types(&self) -> bool {
7603 impl<T:HasProjectionTypes,U:HasProjectionTypes> HasProjectionTypes for OutlivesPredicate<T,U> {
7604 fn has_projection_types(&self) -> bool {
7605 self.0.has_projection_types() || self.1.has_projection_types()
7609 impl<'tcx> HasProjectionTypes for ProjectionPredicate<'tcx> {
7610 fn has_projection_types(&self) -> bool {
7611 self.projection_ty.has_projection_types() || self.ty.has_projection_types()
7615 impl<'tcx> HasProjectionTypes for ProjectionTy<'tcx> {
7616 fn has_projection_types(&self) -> bool {
7617 self.trait_ref.has_projection_types()
7621 impl<'tcx> HasProjectionTypes for Ty<'tcx> {
7622 fn has_projection_types(&self) -> bool {
7623 ty::type_has_projection(*self)
7627 impl<'tcx> HasProjectionTypes for TraitRef<'tcx> {
7628 fn has_projection_types(&self) -> bool {
7629 self.substs.has_projection_types()
7633 impl<'tcx> HasProjectionTypes for subst::Substs<'tcx> {
7634 fn has_projection_types(&self) -> bool {
7635 self.types.iter().any(|t| t.has_projection_types())
7639 impl<'tcx,T> HasProjectionTypes for Option<T>
7640 where T : HasProjectionTypes
7642 fn has_projection_types(&self) -> bool {
7643 self.iter().any(|t| t.has_projection_types())
7647 impl<'tcx,T> HasProjectionTypes for Rc<T>
7648 where T : HasProjectionTypes
7650 fn has_projection_types(&self) -> bool {
7651 (**self).has_projection_types()
7655 impl<'tcx,T> HasProjectionTypes for Box<T>
7656 where T : HasProjectionTypes
7658 fn has_projection_types(&self) -> bool {
7659 (**self).has_projection_types()
7663 impl<T> HasProjectionTypes for Binder<T>
7664 where T : HasProjectionTypes
7666 fn has_projection_types(&self) -> bool {
7667 self.0.has_projection_types()
7671 impl<'tcx> HasProjectionTypes for FnOutput<'tcx> {
7672 fn has_projection_types(&self) -> bool {
7674 FnConverging(t) => t.has_projection_types(),
7675 FnDiverging => false,
7680 impl<'tcx> HasProjectionTypes for FnSig<'tcx> {
7681 fn has_projection_types(&self) -> bool {
7682 self.inputs.iter().any(|t| t.has_projection_types()) ||
7683 self.output.has_projection_types()
7687 impl<'tcx> HasProjectionTypes for field<'tcx> {
7688 fn has_projection_types(&self) -> bool {
7689 self.mt.ty.has_projection_types()
7693 impl<'tcx> HasProjectionTypes for BareFnTy<'tcx> {
7694 fn has_projection_types(&self) -> bool {
7695 self.sig.has_projection_types()
7699 pub trait ReferencesError {
7700 fn references_error(&self) -> bool;
7703 impl<T:ReferencesError> ReferencesError for Binder<T> {
7704 fn references_error(&self) -> bool {
7705 self.0.references_error()
7709 impl<T:ReferencesError> ReferencesError for Rc<T> {
7710 fn references_error(&self) -> bool {
7711 (&**self).references_error()
7715 impl<'tcx> ReferencesError for TraitPredicate<'tcx> {
7716 fn references_error(&self) -> bool {
7717 self.trait_ref.references_error()
7721 impl<'tcx> ReferencesError for ProjectionPredicate<'tcx> {
7722 fn references_error(&self) -> bool {
7723 self.projection_ty.trait_ref.references_error() || self.ty.references_error()
7727 impl<'tcx> ReferencesError for TraitRef<'tcx> {
7728 fn references_error(&self) -> bool {
7729 self.input_types().iter().any(|t| t.references_error())
7733 impl<'tcx> ReferencesError for Ty<'tcx> {
7734 fn references_error(&self) -> bool {
7735 type_is_error(*self)
7739 impl<'tcx> ReferencesError for Predicate<'tcx> {
7740 fn references_error(&self) -> bool {
7742 Predicate::Trait(ref data) => data.references_error(),
7743 Predicate::Equate(ref data) => data.references_error(),
7744 Predicate::RegionOutlives(ref data) => data.references_error(),
7745 Predicate::TypeOutlives(ref data) => data.references_error(),
7746 Predicate::Projection(ref data) => data.references_error(),
7751 impl<A,B> ReferencesError for OutlivesPredicate<A,B>
7752 where A : ReferencesError, B : ReferencesError
7754 fn references_error(&self) -> bool {
7755 self.0.references_error() || self.1.references_error()
7759 impl<'tcx> ReferencesError for EquatePredicate<'tcx>
7761 fn references_error(&self) -> bool {
7762 self.0.references_error() || self.1.references_error()
7766 impl ReferencesError for Region
7768 fn references_error(&self) -> bool {
7773 impl<'tcx> fmt::Debug for ClosureTy<'tcx> {
7774 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7775 write!(f, "ClosureTy({},{:?},{})",
7782 impl<'tcx> fmt::Debug for ClosureUpvar<'tcx> {
7783 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7784 write!(f, "ClosureUpvar({:?},{:?})",
7790 impl<'tcx> fmt::Debug for field<'tcx> {
7791 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7792 write!(f, "field({},{})", self.name, self.mt)
7796 impl<'a, 'tcx> fmt::Debug for ParameterEnvironment<'a, 'tcx> {
7797 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7798 write!(f, "ParameterEnvironment(\
7800 implicit_region_bound={:?}, \
7801 caller_bounds={:?})",
7803 self.implicit_region_bound,
7808 impl<'tcx> fmt::Debug for ObjectLifetimeDefault {
7809 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
7811 ObjectLifetimeDefault::Ambiguous => write!(f, "Ambiguous"),
7812 ObjectLifetimeDefault::Specific(ref r) => write!(f, "{:?}", r),