1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 #![allow(non_camel_case_types)]
14 use driver::session::Session;
15 use metadata::csearch;
16 use middle::const_eval;
17 use middle::lang_items::{ExchangeHeapLangItem, OpaqueStructLangItem};
18 use middle::lang_items::{TyDescStructLangItem, TyVisitorTraitLangItem};
21 use middle::resolve_lifetime;
23 use middle::subst::Subst;
25 use middle::typeck::{MethodCall, MethodCallee, MethodMap};
27 use middle::ty_fold::TypeFolder;
29 use util::ppaux::{note_and_explain_region, bound_region_ptr_to_str};
30 use util::ppaux::{trait_store_to_str, ty_to_str};
31 use util::ppaux::{Repr, UserString};
32 use util::common::{indenter};
33 use util::nodemap::{NodeMap, NodeSet, DefIdMap, DefIdSet, FnvHashMap};
36 use std::cell::{Cell, RefCell};
40 use std::hash::{Hash, sip};
43 use collections::{HashMap, HashSet};
45 use syntax::ast_util::{is_local, lit_is_str};
48 use syntax::attr::AttrMetaMethods;
49 use syntax::codemap::Span;
50 use syntax::parse::token;
51 use syntax::parse::token::InternedString;
52 use syntax::{ast, ast_map};
53 use syntax::owned_slice::OwnedSlice;
56 use collections::enum_set::{EnumSet, CLike};
60 pub static INITIAL_DISCRIMINANT_VALUE: Disr = 0;
64 #[deriving(Eq, TotalEq, Hash)]
66 pub ident: ast::Ident,
71 pub enum MethodContainer {
72 TraitContainer(ast::DefId),
73 ImplContainer(ast::DefId),
78 pub ident: ast::Ident,
79 pub generics: ty::Generics,
81 pub explicit_self: ast::ExplicitSelf_,
82 pub vis: ast::Visibility,
83 pub def_id: ast::DefId,
84 pub container: MethodContainer,
86 // If this method is provided, we need to know where it came from
87 pub provided_source: Option<ast::DefId>
91 pub fn new(ident: ast::Ident,
92 generics: ty::Generics,
94 explicit_self: ast::ExplicitSelf_,
97 container: MethodContainer,
98 provided_source: Option<ast::DefId>)
104 explicit_self: explicit_self,
107 container: container,
108 provided_source: provided_source
112 pub fn container_id(&self) -> ast::DefId {
113 match self.container {
114 TraitContainer(id) => id,
115 ImplContainer(id) => id,
123 pub methods: Vec<@Method>,
126 #[deriving(Clone, Eq, TotalEq, Hash)]
129 pub mutbl: ast::Mutability,
132 #[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash, Show)]
133 /// Describes the "storage mode" of a `[]`, whether it's fixed length or a slice.
135 /// Set M to () to disable mutable slices.
136 pub enum Vstore<M = ast::Mutability> {
141 /// &[T] and &mut [T]
142 VstoreSlice(Region, M)
145 #[deriving(Clone, Eq, TotalEq, Hash, Encodable, Decodable, Show)]
146 pub enum TraitStore {
149 /// &Trait and &mut Trait
150 RegionTraitStore(Region, ast::Mutability),
153 pub struct field_ty {
156 pub vis: ast::Visibility,
159 // Contains information needed to resolve types and (in the future) look up
160 // the types of AST nodes.
161 #[deriving(Eq, TotalEq, Hash)]
162 pub struct creader_cache_key {
168 pub type creader_cache = RefCell<HashMap<creader_cache_key, t>>;
170 pub struct intern_key {
174 // NB: Do not replace this with #[deriving(Eq)]. The automatically-derived
175 // implementation will not recurse through sty and you will get stack
177 impl cmp::Eq for intern_key {
178 fn eq(&self, other: &intern_key) -> bool {
180 *self.sty == *other.sty
183 fn ne(&self, other: &intern_key) -> bool {
188 impl TotalEq for intern_key {}
190 impl<W:Writer> Hash<W> for intern_key {
191 fn hash(&self, s: &mut W) {
192 unsafe { (*self.sty).hash(s) }
196 pub enum ast_ty_to_ty_cache_entry {
197 atttce_unresolved, /* not resolved yet */
198 atttce_resolved(t) /* resolved to a type, irrespective of region */
201 #[deriving(Clone, Eq, Decodable, Encodable)]
202 pub struct ItemVariances {
203 pub self_param: Option<Variance>,
204 pub type_params: OwnedSlice<Variance>,
205 pub region_params: OwnedSlice<Variance>
208 #[deriving(Clone, Eq, Decodable, Encodable, Show)]
210 Covariant, // T<A> <: T<B> iff A <: B -- e.g., function return type
211 Invariant, // T<A> <: T<B> iff B == A -- e.g., type of mutable cell
212 Contravariant, // T<A> <: T<B> iff B <: A -- e.g., function param type
213 Bivariant, // T<A> <: T<B> -- e.g., unused type parameter
216 pub enum AutoAdjustment {
217 AutoAddEnv(ty::Region, ast::Sigil),
218 AutoDerefRef(AutoDerefRef),
219 AutoObject(ty::TraitStore,
221 ast::DefId, /* Trait ID */
222 ty::substs /* Trait substitutions */)
225 #[deriving(Decodable, Encodable)]
226 pub struct AutoDerefRef {
227 pub autoderefs: uint,
228 pub autoref: Option<AutoRef>
231 #[deriving(Decodable, Encodable, Eq, Show)]
233 /// Convert from T to &T
234 AutoPtr(Region, ast::Mutability),
236 /// Convert from ~[]/&[] to &[] (or str)
237 AutoBorrowVec(Region, ast::Mutability),
239 /// Convert from ~[]/&[] to &&[] (or str)
240 AutoBorrowVecRef(Region, ast::Mutability),
242 /// Convert from @fn()/~fn()/|| to ||
243 AutoBorrowFn(Region),
245 /// Convert from T to *T
246 AutoUnsafe(ast::Mutability),
248 /// Convert from ~Trait/&Trait to &Trait
249 AutoBorrowObj(Region, ast::Mutability),
252 /// The data structure to keep track of all the information that typechecker
253 /// generates so that so that it can be reused and doesn't have to be redone
256 // Specifically use a speedy hash algorithm for this hash map, it's used
258 pub interner: RefCell<FnvHashMap<intern_key, ~t_box_>>,
259 pub next_id: Cell<uint>,
261 pub def_map: resolve::DefMap,
263 pub named_region_map: resolve_lifetime::NamedRegionMap,
265 pub region_maps: middle::region::RegionMaps,
267 // Stores the types for various nodes in the AST. Note that this table
268 // is not guaranteed to be populated until after typeck. See
269 // typeck::check::fn_ctxt for details.
270 pub node_types: node_type_table,
272 // Stores the type parameters which were substituted to obtain the type
273 // of this node. This only applies to nodes that refer to entities
274 // parameterized by type parameters, such as generic fns, types, or
276 pub node_type_substs: RefCell<NodeMap<Vec<t>>>,
278 // Maps from a method to the method "descriptor"
279 pub methods: RefCell<DefIdMap<@Method>>,
281 // Maps from a trait def-id to a list of the def-ids of its methods
282 pub trait_method_def_ids: RefCell<DefIdMap<@Vec<DefId> >>,
284 // A cache for the trait_methods() routine
285 pub trait_methods_cache: RefCell<DefIdMap<@Vec<@Method> >>,
287 pub impl_trait_cache: RefCell<DefIdMap<Option<@ty::TraitRef>>>,
289 pub trait_refs: RefCell<NodeMap<@TraitRef>>,
290 pub trait_defs: RefCell<DefIdMap<@TraitDef>>,
292 pub map: ast_map::Map,
293 pub intrinsic_defs: RefCell<DefIdMap<t>>,
294 pub freevars: RefCell<freevars::freevar_map>,
295 pub tcache: type_cache,
296 pub rcache: creader_cache,
297 pub short_names_cache: RefCell<HashMap<t, ~str>>,
298 pub needs_unwind_cleanup_cache: RefCell<HashMap<t, bool>>,
299 pub tc_cache: RefCell<HashMap<uint, TypeContents>>,
300 pub ast_ty_to_ty_cache: RefCell<NodeMap<ast_ty_to_ty_cache_entry>>,
301 pub enum_var_cache: RefCell<DefIdMap<@Vec<@VariantInfo> >>,
302 pub ty_param_defs: RefCell<NodeMap<TypeParameterDef>>,
303 pub adjustments: RefCell<NodeMap<@AutoAdjustment>>,
304 pub normalized_cache: RefCell<HashMap<t, t>>,
305 pub lang_items: @middle::lang_items::LanguageItems,
306 // A mapping of fake provided method def_ids to the default implementation
307 pub provided_method_sources: RefCell<DefIdMap<ast::DefId>>,
308 pub supertraits: RefCell<DefIdMap<@Vec<@TraitRef> >>,
310 // Maps from def-id of a type or region parameter to its
311 // (inferred) variance.
312 pub item_variance_map: RefCell<DefIdMap<@ItemVariances>>,
314 // A mapping from the def ID of an enum or struct type to the def ID
315 // of the method that implements its destructor. If the type is not
316 // present in this map, it does not have a destructor. This map is
317 // populated during the coherence phase of typechecking.
318 pub destructor_for_type: RefCell<DefIdMap<ast::DefId>>,
320 // A method will be in this list if and only if it is a destructor.
321 pub destructors: RefCell<DefIdSet>,
323 // Maps a trait onto a list of impls of that trait.
324 pub trait_impls: RefCell<DefIdMap<@RefCell<Vec<@Impl> >>>,
326 // Maps a def_id of a type to a list of its inherent impls.
327 // Contains implementations of methods that are inherent to a type.
328 // Methods in these implementations don't need to be exported.
329 pub inherent_impls: RefCell<DefIdMap<@RefCell<Vec<@Impl> >>>,
331 // Maps a def_id of an impl to an Impl structure.
332 // Note that this contains all of the impls that we know about,
333 // including ones in other crates. It's not clear that this is the best
335 pub impls: RefCell<DefIdMap<@Impl>>,
337 // Set of used unsafe nodes (functions or blocks). Unsafe nodes not
338 // present in this set can be warned about.
339 pub used_unsafe: RefCell<NodeSet>,
341 // Set of nodes which mark locals as mutable which end up getting used at
342 // some point. Local variable definitions not in this set can be warned
344 pub used_mut_nodes: RefCell<NodeSet>,
346 // vtable resolution information for impl declarations
347 pub impl_vtables: typeck::impl_vtable_map,
349 // The set of external nominal types whose implementations have been read.
350 // This is used for lazy resolution of methods.
351 pub populated_external_types: RefCell<DefIdSet>,
353 // The set of external traits whose implementations have been read. This
354 // is used for lazy resolution of traits.
355 pub populated_external_traits: RefCell<DefIdSet>,
358 pub upvar_borrow_map: RefCell<UpvarBorrowMap>,
360 // These two caches are used by const_eval when decoding external statics
361 // and variants that are found.
362 pub extern_const_statics: RefCell<DefIdMap<Option<@ast::Expr>>>,
363 pub extern_const_variants: RefCell<DefIdMap<Option<@ast::Expr>>>,
374 // a meta-pub flag: subst may be required if the type has parameters, a self
375 // type, or references bound regions
376 needs_subst = 1 | 2 | 8
379 pub type t_box = &'static t_box_;
387 // To reduce refcounting cost, we're representing types as unsafe pointers
388 // throughout the compiler. These are simply casted t_box values. Use ty::get
389 // to cast them back to a box. (Without the cast, compiler performance suffers
390 // ~15%.) This does mean that a t value relies on the ctxt to keep its box
391 // alive, and using ty::get is unsafe when the ctxt is no longer alive.
394 #[allow(raw_pointer_deriving)]
395 #[deriving(Clone, Eq, TotalEq, Hash)]
396 pub struct t { inner: *t_opaque }
398 impl fmt::Show for t {
399 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
400 f.buf.write_str("*t_opaque")
404 pub fn get(t: t) -> t_box {
406 let t2: t_box = cast::transmute(t);
411 pub fn tbox_has_flag(tb: t_box, flag: tbox_flag) -> bool {
412 (tb.flags & (flag as uint)) != 0u
414 pub fn type_has_params(t: t) -> bool {
415 tbox_has_flag(get(t), has_params)
417 pub fn type_has_self(t: t) -> bool { tbox_has_flag(get(t), has_self) }
418 pub fn type_needs_infer(t: t) -> bool {
419 tbox_has_flag(get(t), needs_infer)
421 pub fn type_id(t: t) -> uint { get(t).id }
423 #[deriving(Clone, Eq, TotalEq, Hash)]
424 pub struct BareFnTy {
425 pub fn_style: ast::FnStyle,
430 #[deriving(Clone, Eq, TotalEq, Hash)]
431 pub struct ClosureTy {
432 pub fn_style: ast::FnStyle,
433 pub sigil: ast::Sigil,
434 pub onceness: ast::Onceness,
436 pub bounds: BuiltinBounds,
441 * Signature of a function type, which I have arbitrarily
442 * decided to use to refer to the input/output types.
444 * - `binder_id` is the node id where this fn type appeared;
445 * it is used to identify all the bound regions appearing
446 * in the input/output types that are bound by this fn type
447 * (vs some enclosing or enclosed fn type)
448 * - `inputs` is the list of arguments and their modes.
449 * - `output` is the return type.
450 * - `variadic` indicates whether this is a varidic function. (only true for foreign fns)
452 #[deriving(Clone, Eq, TotalEq, Hash)]
454 pub binder_id: ast::NodeId,
460 #[deriving(Clone, Eq, TotalEq, Hash)]
461 pub struct param_ty {
466 /// Representation of regions:
467 #[deriving(Clone, Eq, TotalEq, Hash, Encodable, Decodable, Show)]
469 // Region bound in a type or fn declaration which will be
470 // substituted 'early' -- that is, at the same time when type
471 // parameters are substituted.
472 ReEarlyBound(/* param id */ ast::NodeId, /*index*/ uint, ast::Name),
474 // Region bound in a function scope, which will be substituted when the
475 // function is called. The first argument must be the `binder_id` of
476 // some enclosing function signature.
477 ReLateBound(/* binder_id */ ast::NodeId, BoundRegion),
479 /// When checking a function body, the types of all arguments and so forth
480 /// that refer to bound region parameters are modified to refer to free
481 /// region parameters.
484 /// A concrete region naming some expression within the current function.
487 /// Static data that has an "infinite" lifetime. Top in the region lattice.
490 /// A region variable. Should not exist after typeck.
491 ReInfer(InferRegion),
493 /// Empty lifetime is for data that is never accessed.
494 /// Bottom in the region lattice. We treat ReEmpty somewhat
495 /// specially; at least right now, we do not generate instances of
496 /// it during the GLB computations, but rather
497 /// generate an error instead. This is to improve error messages.
498 /// The only way to get an instance of ReEmpty is to have a region
499 /// variable with no constraints.
504 * Upvars do not get their own node-id. Instead, we use the pair of
505 * the original var id (that is, the root variable that is referenced
506 * by the upvar) and the id of the closure expression.
508 #[deriving(Clone, Eq, TotalEq, Hash)]
510 pub var_id: ast::NodeId,
511 pub closure_expr_id: ast::NodeId,
514 #[deriving(Clone, Eq, TotalEq, Hash)]
515 pub enum BorrowKind {
516 /// Data must be immutable and is aliasable.
519 /// Data must be immutable but not aliasable. This kind of borrow
520 /// cannot currently be expressed by the user and is used only in
521 /// implicit closure bindings. It is needed when you the closure
522 /// is borrowing or mutating a mutable referent, e.g.:
524 /// let x: &mut int = ...;
525 /// let y = || *x += 5;
527 /// If we were to try to translate this closure into a more explicit
528 /// form, we'd encounter an error with the code as written:
530 /// struct Env { x: & &mut int }
531 /// let x: &mut int = ...;
532 /// let y = (&mut Env { &x }, fn_ptr); // Closure is pair of env and fn
533 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
535 /// This is then illegal because you cannot mutate a `&mut` found
536 /// in an aliasable location. To solve, you'd have to translate with
537 /// an `&mut` borrow:
539 /// struct Env { x: & &mut int }
540 /// let x: &mut int = ...;
541 /// let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
542 /// fn fn_ptr(env: &mut Env) { **env.x += 5; }
544 /// Now the assignment to `**env.x` is legal, but creating a
545 /// mutable pointer to `x` is not because `x` is not mutable. We
546 /// could fix this by declaring `x` as `let mut x`. This is ok in
547 /// user code, if awkward, but extra weird for closures, since the
548 /// borrow is hidden.
550 /// So we introduce a "unique imm" borrow -- the referent is
551 /// immutable, but not aliasable. This solves the problem. For
552 /// simplicity, we don't give users the way to express this
553 /// borrow, it's just used when translating closures.
556 /// Data is mutable and not aliasable.
561 * Information describing the borrowing of an upvar. This is computed
562 * during `typeck`, specifically by `regionck`. The general idea is
563 * that the compiler analyses treat closures like:
565 * let closure: &'e fn() = || {
566 * x = 1; // upvar x is assigned to
567 * use(y); // upvar y is read
568 * foo(&z); // upvar z is borrowed immutably
571 * as if they were "desugared" to something loosely like:
573 * struct Vars<'x,'y,'z> { x: &'x mut int,
576 * let closure: &'e fn() = {
582 * let env: &'e mut Vars<'x,'y,'z> = &mut Vars { x: &'x mut x,
588 * This is basically what happens at runtime. The closure is basically
589 * an existentially quantified version of the `(env, f)` pair.
591 * This data structure indicates the region and mutability of a single
592 * one of the `x...z` borrows.
594 * It may not be obvious why each borrowed variable gets its own
595 * lifetime (in the desugared version of the example, these are indicated
596 * by the lifetime parameters `'x`, `'y`, and `'z` in the `Vars` definition).
597 * Each such lifetime must encompass the lifetime `'e` of the closure itself,
598 * but need not be identical to it. The reason that this makes sense:
600 * - Callers are only permitted to invoke the closure, and hence to
601 * use the pointers, within the lifetime `'e`, so clearly `'e` must
602 * be a sublifetime of `'x...'z`.
603 * - The closure creator knows which upvars were borrowed by the closure
604 * and thus `x...z` will be reserved for `'x...'z` respectively.
605 * - Through mutation, the borrowed upvars can actually escape
606 * the closure, so sometimes it is necessary for them to be larger
607 * than the closure lifetime itself.
609 #[deriving(Eq, Clone)]
610 pub struct UpvarBorrow {
611 pub kind: BorrowKind,
612 pub region: ty::Region,
615 pub type UpvarBorrowMap = HashMap<UpvarId, UpvarBorrow>;
618 pub fn is_bound(&self) -> bool {
620 &ty::ReEarlyBound(..) => true,
621 &ty::ReLateBound(..) => true,
627 #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd, Hash, Encodable, Decodable, Show)]
628 pub struct FreeRegion {
629 pub scope_id: NodeId,
630 pub bound_region: BoundRegion
633 #[deriving(Clone, Eq, Ord, TotalEq, TotalOrd, Hash, Encodable, Decodable, Show)]
634 pub enum BoundRegion {
635 /// An anonymous region parameter for a given fn (&T)
638 /// Named region parameters for functions (a in &'a T)
640 /// The def-id is needed to distinguish free regions in
641 /// the event of shadowing.
642 BrNamed(ast::DefId, ast::Name),
644 /// Fresh bound identifiers created during GLB computations.
649 * Represents the values to use when substituting lifetime parameters.
650 * If the value is `ErasedRegions`, then this subst is occurring during
651 * trans, and all region parameters will be replaced with `ty::ReStatic`. */
652 #[deriving(Clone, Eq, TotalEq, Hash)]
653 pub enum RegionSubsts {
655 NonerasedRegions(OwnedSlice<ty::Region>)
659 * The type substs represents the kinds of things that can be substituted to
660 * convert a polytype into a monotype. Note however that substituting bound
661 * regions other than `self` is done through a different mechanism:
663 * - `tps` represents the type parameters in scope. They are indexed
664 * according to the order in which they were declared.
666 * - `self_r` indicates the region parameter `self` that is present on nominal
667 * types (enums, structs) declared as having a region parameter. `self_r`
668 * should always be none for types that are not region-parameterized and
669 * Some(_) for types that are. The only bound region parameter that should
670 * appear within a region-parameterized type is `self`.
672 * - `self_ty` is the type to which `self` should be remapped, if any. The
673 * `self` type is rather funny in that it can only appear on traits and is
674 * always substituted away to the implementing type for a trait. */
675 #[deriving(Clone, Eq, TotalEq, Hash)]
677 pub self_ty: Option<ty::t>,
679 pub regions: RegionSubsts,
687 macro_rules! def_prim_ty(
688 ($name:ident, $sty:expr, $id:expr) => (
689 pub static $name: t_box_ = t_box_ {
697 def_prim_ty!(TY_NIL, super::ty_nil, 0)
698 def_prim_ty!(TY_BOOL, super::ty_bool, 1)
699 def_prim_ty!(TY_CHAR, super::ty_char, 2)
700 def_prim_ty!(TY_INT, super::ty_int(ast::TyI), 3)
701 def_prim_ty!(TY_I8, super::ty_int(ast::TyI8), 4)
702 def_prim_ty!(TY_I16, super::ty_int(ast::TyI16), 5)
703 def_prim_ty!(TY_I32, super::ty_int(ast::TyI32), 6)
704 def_prim_ty!(TY_I64, super::ty_int(ast::TyI64), 7)
705 def_prim_ty!(TY_UINT, super::ty_uint(ast::TyU), 8)
706 def_prim_ty!(TY_U8, super::ty_uint(ast::TyU8), 9)
707 def_prim_ty!(TY_U16, super::ty_uint(ast::TyU16), 10)
708 def_prim_ty!(TY_U32, super::ty_uint(ast::TyU32), 11)
709 def_prim_ty!(TY_U64, super::ty_uint(ast::TyU64), 12)
710 def_prim_ty!(TY_F32, super::ty_float(ast::TyF32), 14)
711 def_prim_ty!(TY_F64, super::ty_float(ast::TyF64), 15)
713 pub static TY_BOT: t_box_ = t_box_ {
716 flags: super::has_ty_bot as uint,
719 pub static TY_ERR: t_box_ = t_box_ {
722 flags: super::has_ty_err as uint,
725 pub static LAST_PRIMITIVE_ID: uint = 18;
728 // NB: If you change this, you'll probably want to change the corresponding
729 // AST structure in libsyntax/ast.rs as well.
730 #[deriving(Clone, Eq, TotalEq, Hash)]
737 ty_uint(ast::UintTy),
738 ty_float(ast::FloatTy),
739 ty_enum(DefId, substs),
746 ty_bare_fn(BareFnTy),
747 ty_closure(~ClosureTy),
749 ty_struct(DefId, substs),
752 ty_param(param_ty), // type parameter
753 ty_self(DefId), /* special, implicit `self` type parameter;
754 * def_id is the id of the trait */
756 ty_infer(InferTy), // something used only during inference/typeck
757 ty_err, // Also only used during inference/typeck, to represent
758 // the type of an erroneous expression (helps cut down
759 // on non-useful type error messages)
762 #[deriving(Clone, Eq, TotalEq, Hash)]
766 pub store: TraitStore,
767 pub bounds: BuiltinBounds
770 #[deriving(Eq, TotalEq, Hash)]
771 pub struct TraitRef {
776 #[deriving(Clone, Eq)]
777 pub enum IntVarValue {
779 UintType(ast::UintTy),
782 #[deriving(Clone, Show)]
783 pub enum terr_vstore_kind {
790 #[deriving(Clone, Show)]
791 pub struct expected_found<T> {
796 // Data structures used in type unification
797 #[deriving(Clone, Show)]
800 terr_fn_style_mismatch(expected_found<FnStyle>),
801 terr_onceness_mismatch(expected_found<Onceness>),
802 terr_abi_mismatch(expected_found<abi::Abi>),
804 terr_sigil_mismatch(expected_found<ast::Sigil>),
809 terr_tuple_size(expected_found<uint>),
810 terr_ty_param_size(expected_found<uint>),
811 terr_record_size(expected_found<uint>),
812 terr_record_mutability,
813 terr_record_fields(expected_found<Ident>),
815 terr_regions_does_not_outlive(Region, Region),
816 terr_regions_not_same(Region, Region),
817 terr_regions_no_overlap(Region, Region),
818 terr_regions_insufficiently_polymorphic(BoundRegion, Region),
819 terr_regions_overly_polymorphic(BoundRegion, Region),
820 terr_vstores_differ(terr_vstore_kind, expected_found<Vstore<()>>),
821 terr_trait_stores_differ(terr_vstore_kind, expected_found<TraitStore>),
822 terr_in_field(@type_err, ast::Ident),
823 terr_sorts(expected_found<t>),
824 terr_integer_as_char,
825 terr_int_mismatch(expected_found<IntVarValue>),
826 terr_float_mismatch(expected_found<ast::FloatTy>),
827 terr_traits(expected_found<ast::DefId>),
828 terr_builtin_bounds(expected_found<BuiltinBounds>),
829 terr_variadic_mismatch(expected_found<bool>)
832 #[deriving(Eq, TotalEq, Hash)]
833 pub struct ParamBounds {
834 pub builtin_bounds: BuiltinBounds,
835 pub trait_bounds: Vec<@TraitRef> }
837 pub type BuiltinBounds = EnumSet<BuiltinBound>;
839 #[deriving(Clone, Encodable, Eq, TotalEq, Decodable, Hash, Show)]
841 pub enum BuiltinBound {
849 pub fn EmptyBuiltinBounds() -> BuiltinBounds {
853 pub fn AllBuiltinBounds() -> BuiltinBounds {
854 let mut set = EnumSet::empty();
855 set.add(BoundStatic);
862 impl CLike for BuiltinBound {
863 fn to_uint(&self) -> uint {
866 fn from_uint(v: uint) -> BuiltinBound {
867 unsafe { cast::transmute(v) }
871 #[deriving(Clone, Eq, TotalEq, Hash)]
872 pub struct TyVid(pub uint);
874 #[deriving(Clone, Eq, TotalEq, Hash)]
875 pub struct IntVid(pub uint);
877 #[deriving(Clone, Eq, TotalEq, Hash)]
878 pub struct FloatVid(pub uint);
880 #[deriving(Clone, Eq, TotalEq, Encodable, Decodable, Hash)]
881 pub struct RegionVid {
885 #[deriving(Clone, Eq, TotalEq, Hash)]
892 #[deriving(Clone, Encodable, Decodable, TotalEq, Hash, Show)]
893 pub enum InferRegion {
895 ReSkolemized(uint, BoundRegion)
898 impl cmp::Eq for InferRegion {
899 fn eq(&self, other: &InferRegion) -> bool {
900 match ((*self), *other) {
901 (ReVar(rva), ReVar(rvb)) => {
904 (ReSkolemized(rva, _), ReSkolemized(rvb, _)) => {
910 fn ne(&self, other: &InferRegion) -> bool {
911 !((*self) == (*other))
916 fn to_uint(&self) -> uint;
920 fn to_uint(&self) -> uint { let TyVid(v) = *self; v }
923 impl fmt::Show for TyVid {
924 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result{
925 write!(f.buf, "<generic \\#{}>", self.to_uint())
929 impl Vid for IntVid {
930 fn to_uint(&self) -> uint { let IntVid(v) = *self; v }
933 impl fmt::Show for IntVid {
934 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
935 write!(f.buf, "<generic integer \\#{}>", self.to_uint())
939 impl Vid for FloatVid {
940 fn to_uint(&self) -> uint { let FloatVid(v) = *self; v }
943 impl fmt::Show for FloatVid {
944 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
945 write!(f.buf, "<generic float \\#{}>", self.to_uint())
949 impl Vid for RegionVid {
950 fn to_uint(&self) -> uint { self.id }
953 impl fmt::Show for RegionVid {
954 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
959 impl fmt::Show for FnSig {
960 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
961 // grr, without tcx not much we can do.
962 write!(f.buf, "(...)")
966 impl fmt::Show for InferTy {
967 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
969 TyVar(ref v) => v.fmt(f),
970 IntVar(ref v) => v.fmt(f),
971 FloatVar(ref v) => v.fmt(f),
976 impl fmt::Show for IntVarValue {
977 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
979 IntType(ref v) => v.fmt(f),
980 UintType(ref v) => v.fmt(f),
986 pub struct TypeParameterDef {
987 pub ident: ast::Ident,
988 pub def_id: ast::DefId,
989 pub bounds: @ParamBounds,
990 pub default: Option<ty::t>
993 #[deriving(Encodable, Decodable, Clone)]
994 pub struct RegionParameterDef {
996 pub def_id: ast::DefId,
999 /// Information about the type/lifetime parameters associated with an item.
1000 /// Analogous to ast::Generics.
1002 pub struct Generics {
1003 /// List of type parameters declared on the item.
1004 pub type_param_defs: Rc<Vec<TypeParameterDef>>,
1006 /// List of region parameters declared on the item.
1007 /// For a fn or method, only includes *early-bound* lifetimes.
1008 pub region_param_defs: Rc<Vec<RegionParameterDef>>,
1012 pub fn has_type_params(&self) -> bool {
1013 !self.type_param_defs.is_empty()
1015 pub fn type_param_defs<'a>(&'a self) -> &'a [TypeParameterDef] {
1016 self.type_param_defs.as_slice()
1018 pub fn region_param_defs<'a>(&'a self) -> &'a [RegionParameterDef] {
1019 self.region_param_defs.as_slice()
1023 /// When type checking, we use the `ParameterEnvironment` to track
1024 /// details about the type/lifetime parameters that are in scope.
1025 /// It primarily stores the bounds information.
1027 /// Note: This information might seem to be redundant with the data in
1028 /// `tcx.ty_param_defs`, but it is not. That table contains the
1029 /// parameter definitions from an "outside" perspective, but this
1030 /// struct will contain the bounds for a parameter as seen from inside
1031 /// the function body. Currently the only real distinction is that
1032 /// bound lifetime parameters are replaced with free ones, but in the
1033 /// future I hope to refine the representation of types so as to make
1034 /// more distinctions clearer.
1035 pub struct ParameterEnvironment {
1036 /// A substitution that can be applied to move from
1037 /// the "outer" view of a type or method to the "inner" view.
1038 /// In general, this means converting from bound parameters to
1039 /// free parameters. Since we currently represent bound/free type
1040 /// parameters in the same way, this only has an affect on regions.
1041 pub free_substs: ty::substs,
1043 /// Bound on the Self parameter
1044 pub self_param_bound: Option<@TraitRef>,
1046 /// Bounds on each numbered type parameter
1047 pub type_param_bounds: Vec<ParamBounds> ,
1052 /// - `bounds`: The list of bounds for each type parameter. The length of the
1053 /// list also tells you how many type parameters there are.
1055 /// - `rp`: true if the type is region-parameterized. Types can have at
1056 /// most one region parameter, always called `&self`.
1058 /// - `ty`: the base type. May have reference to the (unsubstituted) bound
1059 /// region `&self` or to (unsubstituted) ty_param types
1061 pub struct ty_param_bounds_and_ty {
1062 pub generics: Generics,
1066 /// As `ty_param_bounds_and_ty` but for a trait ref.
1067 pub struct TraitDef {
1068 pub generics: Generics,
1069 pub bounds: BuiltinBounds,
1070 pub trait_ref: @ty::TraitRef,
1073 pub struct ty_param_substs_and_ty {
1074 pub substs: ty::substs,
1078 pub type type_cache = RefCell<DefIdMap<ty_param_bounds_and_ty>>;
1080 pub type node_type_table = RefCell<HashMap<uint,t>>;
1082 pub fn mk_ctxt(s: Session,
1083 dm: resolve::DefMap,
1084 named_region_map: resolve_lifetime::NamedRegionMap,
1086 freevars: freevars::freevar_map,
1087 region_maps: middle::region::RegionMaps,
1088 lang_items: @middle::lang_items::LanguageItems)
1091 named_region_map: named_region_map,
1092 item_variance_map: RefCell::new(DefIdMap::new()),
1093 interner: RefCell::new(FnvHashMap::new()),
1094 next_id: Cell::new(primitives::LAST_PRIMITIVE_ID),
1097 region_maps: region_maps,
1098 node_types: RefCell::new(HashMap::new()),
1099 node_type_substs: RefCell::new(NodeMap::new()),
1100 trait_refs: RefCell::new(NodeMap::new()),
1101 trait_defs: RefCell::new(DefIdMap::new()),
1103 intrinsic_defs: RefCell::new(DefIdMap::new()),
1104 freevars: RefCell::new(freevars),
1105 tcache: RefCell::new(DefIdMap::new()),
1106 rcache: RefCell::new(HashMap::new()),
1107 short_names_cache: RefCell::new(HashMap::new()),
1108 needs_unwind_cleanup_cache: RefCell::new(HashMap::new()),
1109 tc_cache: RefCell::new(HashMap::new()),
1110 ast_ty_to_ty_cache: RefCell::new(NodeMap::new()),
1111 enum_var_cache: RefCell::new(DefIdMap::new()),
1112 methods: RefCell::new(DefIdMap::new()),
1113 trait_method_def_ids: RefCell::new(DefIdMap::new()),
1114 trait_methods_cache: RefCell::new(DefIdMap::new()),
1115 impl_trait_cache: RefCell::new(DefIdMap::new()),
1116 ty_param_defs: RefCell::new(NodeMap::new()),
1117 adjustments: RefCell::new(NodeMap::new()),
1118 normalized_cache: RefCell::new(HashMap::new()),
1119 lang_items: lang_items,
1120 provided_method_sources: RefCell::new(DefIdMap::new()),
1121 supertraits: RefCell::new(DefIdMap::new()),
1122 destructor_for_type: RefCell::new(DefIdMap::new()),
1123 destructors: RefCell::new(DefIdSet::new()),
1124 trait_impls: RefCell::new(DefIdMap::new()),
1125 inherent_impls: RefCell::new(DefIdMap::new()),
1126 impls: RefCell::new(DefIdMap::new()),
1127 used_unsafe: RefCell::new(NodeSet::new()),
1128 used_mut_nodes: RefCell::new(NodeSet::new()),
1129 impl_vtables: RefCell::new(DefIdMap::new()),
1130 populated_external_types: RefCell::new(DefIdSet::new()),
1131 populated_external_traits: RefCell::new(DefIdSet::new()),
1132 upvar_borrow_map: RefCell::new(HashMap::new()),
1133 extern_const_statics: RefCell::new(DefIdMap::new()),
1134 extern_const_variants: RefCell::new(DefIdMap::new()),
1138 // Type constructors
1140 // Interns a type/name combination, stores the resulting box in cx.interner,
1141 // and returns the box as cast to an unsafe ptr (see comments for t above).
1142 pub fn mk_t(cx: &ctxt, st: sty) -> t {
1143 // Check for primitive types.
1145 ty_nil => return mk_nil(),
1146 ty_err => return mk_err(),
1147 ty_bool => return mk_bool(),
1148 ty_int(i) => return mk_mach_int(i),
1149 ty_uint(u) => return mk_mach_uint(u),
1150 ty_float(f) => return mk_mach_float(f),
1151 ty_char => return mk_char(),
1152 ty_bot => return mk_bot(),
1156 let key = intern_key { sty: &st };
1158 match cx.interner.borrow().find(&key) {
1159 Some(t) => unsafe { return cast::transmute(&t.sty); },
1164 fn rflags(r: Region) -> uint {
1165 (has_regions as uint) | {
1167 ty::ReInfer(_) => needs_infer as uint,
1172 fn sflags(substs: &substs) -> uint {
1174 for tt in substs.tps.iter() { f |= get(*tt).flags; }
1175 match substs.regions {
1177 NonerasedRegions(ref regions) => {
1178 for r in regions.iter() {
1186 &ty_str(VstoreSlice(r, ())) => {
1189 &ty_vec(ty, VstoreSlice(r, _)) => {
1191 flags |= get(ty).flags;
1193 &ty_nil | &ty_bool | &ty_char | &ty_int(_) | &ty_float(_) | &ty_uint(_) |
1195 // You might think that we could just return ty_err for
1196 // any type containing ty_err as a component, and get
1197 // rid of the has_ty_err flag -- likewise for ty_bot (with
1198 // the exception of function types that return bot).
1199 // But doing so caused sporadic memory corruption, and
1200 // neither I (tjc) nor nmatsakis could figure out why,
1201 // so we're doing it this way.
1202 &ty_bot => flags |= has_ty_bot as uint,
1203 &ty_err => flags |= has_ty_err as uint,
1204 &ty_param(_) => flags |= has_params as uint,
1205 &ty_infer(_) => flags |= needs_infer as uint,
1206 &ty_self(_) => flags |= has_self as uint,
1207 &ty_enum(_, ref substs) | &ty_struct(_, ref substs) |
1208 &ty_trait(~ty::TyTrait { ref substs, .. }) => {
1209 flags |= sflags(substs);
1211 ty_trait(~ty::TyTrait { store: RegionTraitStore(r, _), .. }) => {
1217 &ty_box(tt) | &ty_uniq(tt) | &ty_vec(tt, _) => {
1218 flags |= get(tt).flags
1221 flags |= get(m.ty).flags;
1223 &ty_rptr(r, ref m) => {
1225 flags |= get(m.ty).flags;
1227 &ty_tup(ref ts) => for tt in ts.iter() { flags |= get(*tt).flags; },
1228 &ty_bare_fn(ref f) => {
1229 for a in f.sig.inputs.iter() { flags |= get(*a).flags; }
1230 flags |= get(f.sig.output).flags;
1231 // T -> _|_ is *not* _|_ !
1232 flags &= !(has_ty_bot as uint);
1234 &ty_closure(ref f) => {
1235 flags |= rflags(f.region);
1236 for a in f.sig.inputs.iter() { flags |= get(*a).flags; }
1237 flags |= get(f.sig.output).flags;
1238 // T -> _|_ is *not* _|_ !
1239 flags &= !(has_ty_bot as uint);
1245 id: cx.next_id.get(),
1249 let sty_ptr = &t.sty as *sty;
1251 let key = intern_key {
1255 cx.interner.borrow_mut().insert(key, t);
1257 cx.next_id.set(cx.next_id.get() + 1);
1260 cast::transmute::<*sty, t>(sty_ptr)
1265 pub fn mk_prim_t(primitive: &'static t_box_) -> t {
1267 cast::transmute::<&'static t_box_, t>(primitive)
1272 pub fn mk_nil() -> t { mk_prim_t(&primitives::TY_NIL) }
1275 pub fn mk_err() -> t { mk_prim_t(&primitives::TY_ERR) }
1278 pub fn mk_bot() -> t { mk_prim_t(&primitives::TY_BOT) }
1281 pub fn mk_bool() -> t { mk_prim_t(&primitives::TY_BOOL) }
1284 pub fn mk_int() -> t { mk_prim_t(&primitives::TY_INT) }
1287 pub fn mk_i8() -> t { mk_prim_t(&primitives::TY_I8) }
1290 pub fn mk_i16() -> t { mk_prim_t(&primitives::TY_I16) }
1293 pub fn mk_i32() -> t { mk_prim_t(&primitives::TY_I32) }
1296 pub fn mk_i64() -> t { mk_prim_t(&primitives::TY_I64) }
1299 pub fn mk_f32() -> t { mk_prim_t(&primitives::TY_F32) }
1302 pub fn mk_f64() -> t { mk_prim_t(&primitives::TY_F64) }
1305 pub fn mk_uint() -> t { mk_prim_t(&primitives::TY_UINT) }
1308 pub fn mk_u8() -> t { mk_prim_t(&primitives::TY_U8) }
1311 pub fn mk_u16() -> t { mk_prim_t(&primitives::TY_U16) }
1314 pub fn mk_u32() -> t { mk_prim_t(&primitives::TY_U32) }
1317 pub fn mk_u64() -> t { mk_prim_t(&primitives::TY_U64) }
1319 pub fn mk_mach_int(tm: ast::IntTy) -> t {
1321 ast::TyI => mk_int(),
1322 ast::TyI8 => mk_i8(),
1323 ast::TyI16 => mk_i16(),
1324 ast::TyI32 => mk_i32(),
1325 ast::TyI64 => mk_i64(),
1329 pub fn mk_mach_uint(tm: ast::UintTy) -> t {
1331 ast::TyU => mk_uint(),
1332 ast::TyU8 => mk_u8(),
1333 ast::TyU16 => mk_u16(),
1334 ast::TyU32 => mk_u32(),
1335 ast::TyU64 => mk_u64(),
1339 pub fn mk_mach_float(tm: ast::FloatTy) -> t {
1341 ast::TyF32 => mk_f32(),
1342 ast::TyF64 => mk_f64(),
1347 pub fn mk_char() -> t { mk_prim_t(&primitives::TY_CHAR) }
1349 pub fn mk_str(cx: &ctxt, v: Vstore<()>) -> t {
1353 pub fn mk_enum(cx: &ctxt, did: ast::DefId, substs: substs) -> t {
1354 // take a copy of substs so that we own the vectors inside
1355 mk_t(cx, ty_enum(did, substs))
1358 pub fn mk_box(cx: &ctxt, ty: t) -> t { mk_t(cx, ty_box(ty)) }
1360 pub fn mk_uniq(cx: &ctxt, ty: t) -> t { mk_t(cx, ty_uniq(ty)) }
1362 pub fn mk_ptr(cx: &ctxt, tm: mt) -> t { mk_t(cx, ty_ptr(tm)) }
1364 pub fn mk_rptr(cx: &ctxt, r: Region, tm: mt) -> t { mk_t(cx, ty_rptr(r, tm)) }
1366 pub fn mk_mut_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1367 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutMutable})
1369 pub fn mk_imm_rptr(cx: &ctxt, r: Region, ty: t) -> t {
1370 mk_rptr(cx, r, mt {ty: ty, mutbl: ast::MutImmutable})
1373 pub fn mk_mut_ptr(cx: &ctxt, ty: t) -> t {
1374 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutMutable})
1377 pub fn mk_imm_ptr(cx: &ctxt, ty: t) -> t {
1378 mk_ptr(cx, mt {ty: ty, mutbl: ast::MutImmutable})
1381 pub fn mk_nil_ptr(cx: &ctxt) -> t {
1382 mk_ptr(cx, mt {ty: mk_nil(), mutbl: ast::MutImmutable})
1385 pub fn mk_vec(cx: &ctxt, ty: t, v: Vstore) -> t {
1386 mk_t(cx, ty_vec(ty, v))
1389 pub fn mk_tup(cx: &ctxt, ts: Vec<t>) -> t { mk_t(cx, ty_tup(ts)) }
1391 pub fn mk_closure(cx: &ctxt, fty: ClosureTy) -> t {
1392 mk_t(cx, ty_closure(~fty))
1395 pub fn mk_bare_fn(cx: &ctxt, fty: BareFnTy) -> t {
1396 mk_t(cx, ty_bare_fn(fty))
1399 pub fn mk_ctor_fn(cx: &ctxt,
1400 binder_id: ast::NodeId,
1401 input_tys: &[ty::t],
1402 output: ty::t) -> t {
1403 let input_args = input_tys.iter().map(|t| *t).collect();
1406 fn_style: ast::NormalFn,
1409 binder_id: binder_id,
1418 pub fn mk_trait(cx: &ctxt,
1422 bounds: BuiltinBounds)
1424 // take a copy of substs so that we own the vectors inside
1425 let inner = ~TyTrait {
1431 mk_t(cx, ty_trait(inner))
1434 pub fn mk_struct(cx: &ctxt, struct_id: ast::DefId, substs: substs) -> t {
1435 // take a copy of substs so that we own the vectors inside
1436 mk_t(cx, ty_struct(struct_id, substs))
1439 pub fn mk_var(cx: &ctxt, v: TyVid) -> t { mk_infer(cx, TyVar(v)) }
1441 pub fn mk_int_var(cx: &ctxt, v: IntVid) -> t { mk_infer(cx, IntVar(v)) }
1443 pub fn mk_float_var(cx: &ctxt, v: FloatVid) -> t { mk_infer(cx, FloatVar(v)) }
1445 pub fn mk_infer(cx: &ctxt, it: InferTy) -> t { mk_t(cx, ty_infer(it)) }
1447 pub fn mk_self(cx: &ctxt, did: ast::DefId) -> t { mk_t(cx, ty_self(did)) }
1449 pub fn mk_param(cx: &ctxt, n: uint, k: DefId) -> t {
1450 mk_t(cx, ty_param(param_ty { idx: n, def_id: k }))
1453 pub fn walk_ty(ty: t, f: |t|) {
1454 maybe_walk_ty(ty, |t| { f(t); true });
1457 pub fn maybe_walk_ty(ty: t, f: |t| -> bool) {
1462 ty_nil | ty_bot | ty_bool | ty_char | ty_int(_) | ty_uint(_) | ty_float(_) |
1463 ty_str(_) | ty_self(_) |
1464 ty_infer(_) | ty_param(_) | ty_err => {}
1465 ty_box(ty) | ty_uniq(ty) | ty_vec(ty, _) => maybe_walk_ty(ty, f),
1466 ty_ptr(ref tm) | ty_rptr(_, ref tm) => {
1467 maybe_walk_ty(tm.ty, f);
1469 ty_enum(_, ref substs) | ty_struct(_, ref substs) |
1470 ty_trait(~TyTrait { ref substs, .. }) => {
1471 for subty in (*substs).tps.iter() { maybe_walk_ty(*subty, |x| f(x)); }
1473 ty_tup(ref ts) => { for tt in ts.iter() { maybe_walk_ty(*tt, |x| f(x)); } }
1474 ty_bare_fn(ref ft) => {
1475 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1476 maybe_walk_ty(ft.sig.output, f);
1478 ty_closure(ref ft) => {
1479 for a in ft.sig.inputs.iter() { maybe_walk_ty(*a, |x| f(x)); }
1480 maybe_walk_ty(ft.sig.output, f);
1485 // Folds types from the bottom up.
1486 pub fn fold_ty(cx: &ctxt, t0: t, fldop: |t| -> t) -> t {
1487 let mut f = ty_fold::BottomUpFolder {tcx: cx, fldop: fldop};
1491 pub fn walk_regions_and_ty(cx: &ctxt, ty: t, fldr: |r: Region|, fldt: |t: t|)
1493 ty_fold::RegionFolder::general(cx,
1495 |t| { fldt(t); t }).fold_ty(ty)
1498 // Substitute *only* type parameters. Used in trans where regions are erased.
1499 pub fn subst_tps(tcx: &ctxt, tps: &[t], self_ty_opt: Option<t>, typ: t) -> t {
1500 let mut subst = TpsSubst { tcx: tcx, self_ty_opt: self_ty_opt, tps: tps };
1501 return subst.fold_ty(typ);
1503 struct TpsSubst<'a> {
1505 self_ty_opt: Option<t>,
1509 impl<'a> TypeFolder for TpsSubst<'a> {
1510 fn tcx<'a>(&'a self) -> &'a ctxt { self.tcx }
1512 fn fold_ty(&mut self, t: ty::t) -> ty::t {
1513 if self.tps.len() == 0u && self.self_ty_opt.is_none() {
1517 let tb = ty::get(t);
1518 if self.self_ty_opt.is_none() && !tbox_has_flag(tb, has_params) {
1522 match ty::get(t).sty {
1528 match self.self_ty_opt {
1529 None => self.tcx.sess.bug("ty_self unexpected here"),
1530 Some(self_ty) => self_ty
1535 ty_fold::super_fold_ty(self, t)
1542 pub fn substs_is_noop(substs: &substs) -> bool {
1543 let regions_is_noop = match substs.regions {
1544 ErasedRegions => false, // may be used to canonicalize
1545 NonerasedRegions(ref regions) => regions.is_empty()
1548 substs.tps.len() == 0u &&
1550 substs.self_ty.is_none()
1553 pub fn substs_to_str(cx: &ctxt, substs: &substs) -> ~str {
1557 pub fn subst(cx: &ctxt,
1561 typ.subst(cx, substs)
1566 pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil }
1568 pub fn type_is_bot(ty: t) -> bool {
1569 (get(ty).flags & (has_ty_bot as uint)) != 0
1572 pub fn type_is_error(ty: t) -> bool {
1573 (get(ty).flags & (has_ty_err as uint)) != 0
1576 pub fn type_needs_subst(ty: t) -> bool {
1577 tbox_has_flag(get(ty), needs_subst)
1580 pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool {
1581 tref.substs.self_ty.iter().any(|&t| type_is_error(t)) ||
1582 tref.substs.tps.iter().any(|&t| type_is_error(t))
1585 pub fn type_is_ty_var(ty: t) -> bool {
1587 ty_infer(TyVar(_)) => true,
1592 pub fn type_is_bool(ty: t) -> bool { get(ty).sty == ty_bool }
1594 pub fn type_is_self(ty: t) -> bool {
1596 ty_self(..) => true,
1601 pub fn type_is_structural(ty: t) -> bool {
1603 ty_struct(..) | ty_tup(_) | ty_enum(..) | ty_closure(_) | ty_trait(..) |
1604 ty_vec(_, VstoreFixed(_)) | ty_str(VstoreFixed(_)) |
1605 ty_vec(_, VstoreSlice(..)) | ty_str(VstoreSlice(..))
1611 pub fn type_is_simd(cx: &ctxt, ty: t) -> bool {
1613 ty_struct(did, _) => lookup_simd(cx, did),
1618 pub fn sequence_element_type(cx: &ctxt, ty: t) -> t {
1620 ty_str(_) => mk_mach_uint(ast::TyU8),
1621 ty_vec(ty, _) => ty,
1622 _ => cx.sess.bug("sequence_element_type called on non-sequence value"),
1626 pub fn simd_type(cx: &ctxt, ty: t) -> t {
1628 ty_struct(did, ref substs) => {
1629 let fields = lookup_struct_fields(cx, did);
1630 lookup_field_type(cx, did, fields.get(0).id, substs)
1632 _ => fail!("simd_type called on invalid type")
1636 pub fn simd_size(cx: &ctxt, ty: t) -> uint {
1638 ty_struct(did, _) => {
1639 let fields = lookup_struct_fields(cx, did);
1642 _ => fail!("simd_size called on invalid type")
1646 pub fn type_is_boxed(ty: t) -> bool {
1653 pub fn type_is_region_ptr(ty: t) -> bool {
1655 ty_rptr(_, _) => true,
1660 pub fn type_is_unsafe_ptr(ty: t) -> bool {
1662 ty_ptr(_) => return true,
1667 pub fn type_is_unique(ty: t) -> bool {
1669 ty_uniq(_) | ty_vec(_, VstoreUniq) | ty_str(VstoreUniq) => true,
1675 A scalar type is one that denotes an atomic datum, with no sub-components.
1676 (A ty_ptr is scalar because it represents a non-managed pointer, so its
1677 contents are abstract to rustc.)
1679 pub fn type_is_scalar(ty: t) -> bool {
1681 ty_nil | ty_bool | ty_char | ty_int(_) | ty_float(_) | ty_uint(_) |
1682 ty_infer(IntVar(_)) | ty_infer(FloatVar(_)) |
1683 ty_bare_fn(..) | ty_ptr(_) => true,
1688 pub fn type_needs_drop(cx: &ctxt, ty: t) -> bool {
1689 type_contents(cx, ty).needs_drop(cx)
1692 // Some things don't need cleanups during unwinding because the
1693 // task can free them all at once later. Currently only things
1694 // that only contain scalars and shared boxes can avoid unwind
1696 pub fn type_needs_unwind_cleanup(cx: &ctxt, ty: t) -> bool {
1697 match cx.needs_unwind_cleanup_cache.borrow().find(&ty) {
1698 Some(&result) => return result,
1702 let mut tycache = HashSet::new();
1703 let needs_unwind_cleanup =
1704 type_needs_unwind_cleanup_(cx, ty, &mut tycache, false);
1705 cx.needs_unwind_cleanup_cache.borrow_mut().insert(ty, needs_unwind_cleanup);
1706 return needs_unwind_cleanup;
1709 fn type_needs_unwind_cleanup_(cx: &ctxt, ty: t,
1710 tycache: &mut HashSet<t>,
1711 encountered_box: bool) -> bool {
1713 // Prevent infinite recursion
1714 if !tycache.insert(ty) {
1718 let mut encountered_box = encountered_box;
1719 let mut needs_unwind_cleanup = false;
1720 maybe_walk_ty(ty, |ty| {
1721 let old_encountered_box = encountered_box;
1722 let result = match get(ty).sty {
1724 encountered_box = true;
1727 ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
1728 ty_tup(_) | ty_ptr(_) => {
1731 ty_enum(did, ref substs) => {
1732 for v in (*enum_variants(cx, did)).iter() {
1733 for aty in v.args.iter() {
1734 let t = subst(cx, substs, *aty);
1735 needs_unwind_cleanup |=
1736 type_needs_unwind_cleanup_(cx, t, tycache,
1740 !needs_unwind_cleanup
1743 ty_str(VstoreUniq) |
1744 ty_vec(_, VstoreUniq) => {
1745 // Once we're inside a box, the annihilator will find
1746 // it and destroy it.
1747 if !encountered_box {
1748 needs_unwind_cleanup = true;
1755 needs_unwind_cleanup = true;
1760 encountered_box = old_encountered_box;
1764 return needs_unwind_cleanup;
1768 * Type contents is how the type checker reasons about kinds.
1769 * They track what kinds of things are found within a type. You can
1770 * think of them as kind of an "anti-kind". They track the kinds of values
1771 * and thinks that are contained in types. Having a larger contents for
1772 * a type tends to rule that type *out* from various kinds. For example,
1773 * a type that contains a reference is not sendable.
1775 * The reason we compute type contents and not kinds is that it is
1776 * easier for me (nmatsakis) to think about what is contained within
1777 * a type than to think about what is *not* contained within a type.
1779 pub struct TypeContents {
1783 macro_rules! def_type_content_sets(
1784 (mod $mname:ident { $($name:ident = $bits:expr),+ }) => {
1786 use middle::ty::TypeContents;
1787 $(pub static $name: TypeContents = TypeContents { bits: $bits };)+
1792 def_type_content_sets!(
1794 None = 0b0000_0000__0000_0000__0000,
1796 // Things that are interior to the value (first nibble):
1797 InteriorUnsized = 0b0000_0000__0000_0000__0001,
1798 InteriorUnsafe = 0b0000_0000__0000_0000__0010,
1799 // InteriorAll = 0b00000000__00000000__1111,
1801 // Things that are owned by the value (second and third nibbles):
1802 OwnsOwned = 0b0000_0000__0000_0001__0000,
1803 OwnsDtor = 0b0000_0000__0000_0010__0000,
1804 OwnsManaged /* see [1] below */ = 0b0000_0000__0000_0100__0000,
1805 OwnsAffine = 0b0000_0000__0000_1000__0000,
1806 OwnsAll = 0b0000_0000__1111_1111__0000,
1808 // Things that are reachable by the value in any way (fourth nibble):
1809 ReachesNonsendAnnot = 0b0000_0001__0000_0000__0000,
1810 ReachesBorrowed = 0b0000_0010__0000_0000__0000,
1811 // ReachesManaged /* see [1] below */ = 0b0000_0100__0000_0000__0000,
1812 ReachesMutable = 0b0000_1000__0000_0000__0000,
1813 ReachesNoShare = 0b0001_0000__0000_0000__0000,
1814 ReachesAll = 0b0001_1111__0000_0000__0000,
1816 // Things that cause values to *move* rather than *copy*
1817 Moves = 0b0000_0000__0000_1011__0000,
1819 // Things that mean drop glue is necessary
1820 NeedsDrop = 0b0000_0000__0000_0111__0000,
1822 // Things that prevent values from being sent
1824 // Note: For checking whether something is sendable, it'd
1825 // be sufficient to have ReachesManaged. However, we include
1826 // both ReachesManaged and OwnsManaged so that when
1827 // a parameter has a bound T:Send, we are able to deduce
1828 // that it neither reaches nor owns a managed pointer.
1829 Nonsendable = 0b0000_0111__0000_0100__0000,
1831 // Things that prevent values from being considered 'static
1832 Nonstatic = 0b0000_0010__0000_0000__0000,
1834 // Things that prevent values from being considered sized
1835 Nonsized = 0b0000_0000__0000_0000__0001,
1837 // Things that prevent values from being shared
1838 Nonsharable = 0b0001_0000__0000_0000__0000,
1840 // Things that make values considered not POD (would be same
1841 // as `Moves`, but for the fact that managed data `@` is
1842 // not considered POD)
1843 Noncopy = 0b0000_0000__0000_1111__0000,
1845 // Bits to set when a managed value is encountered
1847 // [1] Do not set the bits TC::OwnsManaged or
1848 // TC::ReachesManaged directly, instead reference
1849 // TC::Managed to set them both at once.
1850 Managed = 0b0000_0100__0000_0100__0000,
1853 All = 0b1111_1111__1111_1111__1111
1858 pub fn meets_bound(&self, cx: &ctxt, bb: BuiltinBound) -> bool {
1860 BoundStatic => self.is_static(cx),
1861 BoundSend => self.is_sendable(cx),
1862 BoundSized => self.is_sized(cx),
1863 BoundCopy => self.is_copy(cx),
1864 BoundShare => self.is_sharable(cx),
1868 pub fn when(&self, cond: bool) -> TypeContents {
1869 if cond {*self} else {TC::None}
1872 pub fn intersects(&self, tc: TypeContents) -> bool {
1873 (self.bits & tc.bits) != 0
1876 pub fn is_static(&self, _: &ctxt) -> bool {
1877 !self.intersects(TC::Nonstatic)
1880 pub fn is_sendable(&self, _: &ctxt) -> bool {
1881 !self.intersects(TC::Nonsendable)
1884 pub fn is_sharable(&self, _: &ctxt) -> bool {
1885 !self.intersects(TC::Nonsharable)
1888 pub fn owns_managed(&self) -> bool {
1889 self.intersects(TC::OwnsManaged)
1892 pub fn owns_owned(&self) -> bool {
1893 self.intersects(TC::OwnsOwned)
1896 pub fn is_sized(&self, _: &ctxt) -> bool {
1897 !self.intersects(TC::Nonsized)
1900 pub fn is_copy(&self, _: &ctxt) -> bool {
1901 !self.intersects(TC::Noncopy)
1904 pub fn interior_unsafe(&self) -> bool {
1905 self.intersects(TC::InteriorUnsafe)
1908 pub fn interior_unsized(&self) -> bool {
1909 self.intersects(TC::InteriorUnsized)
1912 pub fn moves_by_default(&self, _: &ctxt) -> bool {
1913 self.intersects(TC::Moves)
1916 pub fn needs_drop(&self, _: &ctxt) -> bool {
1917 self.intersects(TC::NeedsDrop)
1920 pub fn owned_pointer(&self) -> TypeContents {
1922 * Includes only those bits that still apply
1923 * when indirected through a `~` pointer
1926 *self & (TC::OwnsAll | TC::ReachesAll))
1929 pub fn reference(&self, bits: TypeContents) -> TypeContents {
1931 * Includes only those bits that still apply
1932 * when indirected through a reference (`&`)
1935 *self & TC::ReachesAll)
1938 pub fn managed_pointer(&self) -> TypeContents {
1940 * Includes only those bits that still apply
1941 * when indirected through a managed pointer (`@`)
1944 *self & TC::ReachesAll)
1947 pub fn unsafe_pointer(&self) -> TypeContents {
1949 * Includes only those bits that still apply
1950 * when indirected through an unsafe pointer (`*`)
1952 *self & TC::ReachesAll
1955 pub fn union<T>(v: &[T], f: |&T| -> TypeContents) -> TypeContents {
1956 v.iter().fold(TC::None, |tc, t| tc | f(t))
1959 pub fn has_dtor(&self) -> bool {
1960 self.intersects(TC::OwnsDtor)
1964 impl ops::BitOr<TypeContents,TypeContents> for TypeContents {
1965 fn bitor(&self, other: &TypeContents) -> TypeContents {
1966 TypeContents {bits: self.bits | other.bits}
1970 impl ops::BitAnd<TypeContents,TypeContents> for TypeContents {
1971 fn bitand(&self, other: &TypeContents) -> TypeContents {
1972 TypeContents {bits: self.bits & other.bits}
1976 impl ops::Sub<TypeContents,TypeContents> for TypeContents {
1977 fn sub(&self, other: &TypeContents) -> TypeContents {
1978 TypeContents {bits: self.bits & !other.bits}
1982 impl fmt::Show for TypeContents {
1983 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1984 write!(f.buf, "TypeContents({:t})", self.bits)
1988 pub fn type_is_static(cx: &ctxt, t: ty::t) -> bool {
1989 type_contents(cx, t).is_static(cx)
1992 pub fn type_is_sendable(cx: &ctxt, t: ty::t) -> bool {
1993 type_contents(cx, t).is_sendable(cx)
1996 pub fn type_interior_is_unsafe(cx: &ctxt, t: ty::t) -> bool {
1997 type_contents(cx, t).interior_unsafe()
2000 pub fn type_contents(cx: &ctxt, ty: t) -> TypeContents {
2001 let ty_id = type_id(ty);
2003 match cx.tc_cache.borrow().find(&ty_id) {
2004 Some(tc) => { return *tc; }
2008 let mut cache = HashMap::new();
2009 let result = tc_ty(cx, ty, &mut cache);
2011 cx.tc_cache.borrow_mut().insert(ty_id, result);
2016 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2018 // Subtle: Note that we are *not* using cx.tc_cache here but rather a
2019 // private cache for this walk. This is needed in the case of cyclic
2022 // struct List { next: ~Option<List>, ... }
2024 // When computing the type contents of such a type, we wind up deeply
2025 // recursing as we go. So when we encounter the recursive reference
2026 // to List, we temporarily use TC::None as its contents. Later we'll
2027 // patch up the cache with the correct value, once we've computed it
2028 // (this is basically a co-inductive process, if that helps). So in
2029 // the end we'll compute TC::OwnsOwned, in this case.
2031 // The problem is, as we are doing the computation, we will also
2032 // compute an *intermediate* contents for, e.g., Option<List> of
2033 // TC::None. This is ok during the computation of List itself, but if
2034 // we stored this intermediate value into cx.tc_cache, then later
2035 // requests for the contents of Option<List> would also yield TC::None
2036 // which is incorrect. This value was computed based on the crutch
2037 // value for the type contents of list. The correct value is
2038 // TC::OwnsOwned. This manifested as issue #4821.
2039 let ty_id = type_id(ty);
2040 match cache.find(&ty_id) {
2041 Some(tc) => { return *tc; }
2044 match cx.tc_cache.borrow().find(&ty_id) { // Must check both caches!
2045 Some(tc) => { return *tc; }
2048 cache.insert(ty_id, TC::None);
2050 let result = match get(ty).sty {
2051 // Scalar and unique types are sendable, and durable
2052 ty_nil | ty_bot | ty_bool | ty_int(_) | ty_uint(_) | ty_float(_) |
2053 ty_bare_fn(_) | ty::ty_char => {
2057 ty_str(VstoreUniq) => {
2061 ty_closure(ref c) => {
2062 closure_contents(cx, *c)
2066 tc_ty(cx, typ, cache).managed_pointer()
2070 tc_ty(cx, typ, cache).owned_pointer()
2073 ty_trait(~ty::TyTrait { store, bounds, .. }) => {
2074 object_contents(cx, store, bounds)
2078 tc_ty(cx, mt.ty, cache).unsafe_pointer()
2081 ty_rptr(r, ref mt) => {
2082 tc_ty(cx, mt.ty, cache).reference(
2083 borrowed_contents(r, mt.mutbl))
2086 ty_vec(ty, VstoreUniq) => {
2087 tc_ty(cx, ty, cache).owned_pointer()
2090 ty_vec(ty, VstoreSlice(r, mutbl)) => {
2091 tc_ty(cx, ty, cache).reference(borrowed_contents(r, mutbl))
2094 ty_vec(ty, VstoreFixed(_)) => {
2095 tc_ty(cx, ty, cache)
2098 ty_str(VstoreSlice(r, ())) => {
2099 borrowed_contents(r, ast::MutImmutable)
2102 ty_str(VstoreFixed(_)) => {
2106 ty_struct(did, ref substs) => {
2107 let flds = struct_fields(cx, did, substs);
2109 TypeContents::union(flds.as_slice(),
2110 |f| tc_mt(cx, f.mt, cache));
2111 if ty::has_dtor(cx, did) {
2112 res = res | TC::OwnsDtor;
2114 apply_lang_items(cx, did, res)
2117 ty_tup(ref tys) => {
2118 TypeContents::union(tys.as_slice(),
2119 |ty| tc_ty(cx, *ty, cache))
2122 ty_enum(did, ref substs) => {
2123 let variants = substd_enum_variants(cx, did, substs);
2125 TypeContents::union(variants.as_slice(), |variant| {
2126 TypeContents::union(variant.args.as_slice(),
2128 tc_ty(cx, *arg_ty, cache)
2131 apply_lang_items(cx, did, res)
2135 // We only ever ask for the kind of types that are defined in
2136 // the current crate; therefore, the only type parameters that
2137 // could be in scope are those defined in the current crate.
2138 // If this assertion failures, it is likely because of a
2139 // failure in the cross-crate inlining code to translate a
2141 assert_eq!(p.def_id.krate, ast::LOCAL_CRATE);
2143 let ty_param_defs = cx.ty_param_defs.borrow();
2144 let tp_def = ty_param_defs.get(&p.def_id.node);
2145 kind_bounds_to_contents(cx,
2146 tp_def.bounds.builtin_bounds,
2147 tp_def.bounds.trait_bounds.as_slice())
2150 ty_self(def_id) => {
2151 // FIXME(#4678)---self should just be a ty param
2153 // Self may be bounded if the associated trait has builtin kinds
2154 // for supertraits. If so we can use those bounds.
2155 let trait_def = lookup_trait_def(cx, def_id);
2156 let traits = [trait_def.trait_ref];
2157 kind_bounds_to_contents(cx, trait_def.bounds, traits)
2161 // This occurs during coherence, but shouldn't occur at other
2167 cx.sess.bug("asked to compute contents of error type");
2171 cache.insert(ty_id, result);
2177 cache: &mut HashMap<uint, TypeContents>) -> TypeContents
2179 let mc = TC::ReachesMutable.when(mt.mutbl == MutMutable);
2180 mc | tc_ty(cx, mt.ty, cache)
2183 fn apply_lang_items(cx: &ctxt,
2187 if Some(did) == cx.lang_items.no_send_bound() {
2188 tc | TC::ReachesNonsendAnnot
2189 } else if Some(did) == cx.lang_items.managed_bound() {
2191 } else if Some(did) == cx.lang_items.no_copy_bound() {
2193 } else if Some(did) == cx.lang_items.no_share_bound() {
2194 tc | TC::ReachesNoShare
2195 } else if Some(did) == cx.lang_items.unsafe_type() {
2196 tc | TC::InteriorUnsafe
2202 fn borrowed_contents(region: ty::Region,
2203 mutbl: ast::Mutability)
2206 * Type contents due to containing a reference
2207 * with the region `region` and borrow kind `bk`
2210 let b = match mutbl {
2211 ast::MutMutable => TC::ReachesMutable | TC::OwnsAffine,
2212 ast::MutImmutable => TC::None,
2214 b | (TC::ReachesBorrowed).when(region != ty::ReStatic)
2217 fn closure_contents(cx: &ctxt, cty: &ClosureTy) -> TypeContents {
2218 // Closure contents are just like trait contents, but with potentially
2220 let st = match cty.sigil {
2221 ast::BorrowedSigil =>
2222 object_contents(cx, RegionTraitStore(cty.region, MutMutable), cty.bounds),
2223 ast::OwnedSigil => object_contents(cx, UniqTraitStore, cty.bounds),
2224 ast::ManagedSigil => unreachable!()
2227 // FIXME(#3569): This borrowed_contents call should be taken care of in
2228 // object_contents, after ~Traits and @Traits can have region bounds too.
2229 // This one here is redundant for &fns but important for ~fns and @fns.
2230 let rt = borrowed_contents(cty.region, ast::MutImmutable);
2232 // This also prohibits "@once fn" from being copied, which allows it to
2233 // be called. Neither way really makes much sense.
2234 let ot = match cty.onceness {
2235 ast::Once => TC::OwnsAffine,
2236 ast::Many => TC::None,
2242 fn object_contents(cx: &ctxt,
2244 bounds: BuiltinBounds)
2246 // These are the type contents of the (opaque) interior
2247 let contents = kind_bounds_to_contents(cx, bounds, []);
2251 contents.owned_pointer()
2253 RegionTraitStore(r, mutbl) => {
2254 contents.reference(borrowed_contents(r, mutbl))
2259 fn kind_bounds_to_contents(cx: &ctxt,
2260 bounds: BuiltinBounds,
2261 traits: &[@TraitRef])
2263 let _i = indenter();
2264 let mut tc = TC::All;
2265 each_inherited_builtin_bound(cx, bounds, traits, |bound| {
2266 tc = tc - match bound {
2267 BoundStatic => TC::Nonstatic,
2268 BoundSend => TC::Nonsendable,
2269 BoundSized => TC::Nonsized,
2270 BoundCopy => TC::Noncopy,
2271 BoundShare => TC::Nonsharable,
2276 // Iterates over all builtin bounds on the type parameter def, including
2277 // those inherited from traits with builtin-kind-supertraits.
2278 fn each_inherited_builtin_bound(cx: &ctxt,
2279 bounds: BuiltinBounds,
2280 traits: &[@TraitRef],
2281 f: |BuiltinBound|) {
2282 for bound in bounds.iter() {
2286 each_bound_trait_and_supertraits(cx, traits, |trait_ref| {
2287 let trait_def = lookup_trait_def(cx, trait_ref.def_id);
2288 for bound in trait_def.bounds.iter() {
2297 pub fn type_moves_by_default(cx: &ctxt, ty: t) -> bool {
2298 type_contents(cx, ty).moves_by_default(cx)
2301 // True if instantiating an instance of `r_ty` requires an instance of `r_ty`.
2302 pub fn is_instantiable(cx: &ctxt, r_ty: t) -> bool {
2303 fn type_requires(cx: &ctxt, seen: &mut Vec<DefId>,
2304 r_ty: t, ty: t) -> bool {
2305 debug!("type_requires({}, {})?",
2306 ::util::ppaux::ty_to_str(cx, r_ty),
2307 ::util::ppaux::ty_to_str(cx, ty));
2310 get(r_ty).sty == get(ty).sty ||
2311 subtypes_require(cx, seen, r_ty, ty)
2314 debug!("type_requires({}, {})? {}",
2315 ::util::ppaux::ty_to_str(cx, r_ty),
2316 ::util::ppaux::ty_to_str(cx, ty),
2321 fn subtypes_require(cx: &ctxt, seen: &mut Vec<DefId>,
2322 r_ty: t, ty: t) -> bool {
2323 debug!("subtypes_require({}, {})?",
2324 ::util::ppaux::ty_to_str(cx, r_ty),
2325 ::util::ppaux::ty_to_str(cx, ty));
2327 let r = match get(ty).sty {
2328 // fixed length vectors need special treatment compared to
2329 // normal vectors, since they don't necessarily have the
2330 // possibilty to have length zero.
2331 ty_vec(_, VstoreFixed(0)) => false, // don't need no contents
2332 ty_vec(ty, VstoreFixed(_)) => type_requires(cx, seen, r_ty, ty),
2351 ty_box(typ) | ty_uniq(typ) => {
2352 type_requires(cx, seen, r_ty, typ)
2354 ty_rptr(_, ref mt) => {
2355 type_requires(cx, seen, r_ty, mt.ty)
2359 false // unsafe ptrs can always be NULL
2366 ty_struct(ref did, _) if seen.contains(did) => {
2370 ty_struct(did, ref substs) => {
2372 let fields = struct_fields(cx, did, substs);
2373 let r = fields.iter().any(|f| type_requires(cx, seen, r_ty, f.mt.ty));
2374 seen.pop().unwrap();
2379 ts.iter().any(|t| type_requires(cx, seen, r_ty, *t))
2382 ty_enum(ref did, _) if seen.contains(did) => {
2386 ty_enum(did, ref substs) => {
2388 let vs = enum_variants(cx, did);
2389 let r = !vs.is_empty() && vs.iter().all(|variant| {
2390 variant.args.iter().any(|aty| {
2391 let sty = subst(cx, substs, *aty);
2392 type_requires(cx, seen, r_ty, sty)
2395 seen.pop().unwrap();
2400 debug!("subtypes_require({}, {})? {}",
2401 ::util::ppaux::ty_to_str(cx, r_ty),
2402 ::util::ppaux::ty_to_str(cx, ty),
2408 let mut seen = Vec::new();
2409 !subtypes_require(cx, &mut seen, r_ty, r_ty)
2412 /// Describes whether a type is representable. For types that are not
2413 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
2414 /// distinguish between types that are recursive with themselves and types that
2415 /// contain a different recursive type. These cases can therefore be treated
2416 /// differently when reporting errors.
2418 pub enum Representability {
2424 /// Check whether a type is representable. This means it cannot contain unboxed
2425 /// structural recursion. This check is needed for structs and enums.
2426 pub fn is_type_representable(cx: &ctxt, ty: t) -> Representability {
2428 // Iterate until something non-representable is found
2429 fn find_nonrepresentable<It: Iterator<t>>(cx: &ctxt, seen: &mut Vec<DefId>,
2430 mut iter: It) -> Representability {
2432 let r = type_structurally_recursive(cx, seen, ty);
2433 if r != Representable {
2440 // Does the type `ty` directly (without indirection through a pointer)
2441 // contain any types on stack `seen`?
2442 fn type_structurally_recursive(cx: &ctxt, seen: &mut Vec<DefId>,
2443 ty: t) -> Representability {
2444 debug!("type_structurally_recursive: {}",
2445 ::util::ppaux::ty_to_str(cx, ty));
2447 // Compare current type to previously seen types
2450 ty_enum(did, _) => {
2451 for (i, &seen_did) in seen.iter().enumerate() {
2452 if did == seen_did {
2453 return if i == 0 { SelfRecursive }
2454 else { ContainsRecursive }
2461 // Check inner types
2465 find_nonrepresentable(cx, seen, ts.iter().map(|t| *t))
2467 // Fixed-length vectors.
2468 // FIXME(#11924) Behavior undecided for zero-length vectors.
2469 ty_vec(ty, VstoreFixed(_)) => {
2470 type_structurally_recursive(cx, seen, ty)
2473 // Push struct and enum def-ids onto `seen` before recursing.
2474 ty_struct(did, ref substs) => {
2476 let fields = struct_fields(cx, did, substs);
2477 let r = find_nonrepresentable(cx, seen,
2478 fields.iter().map(|f| f.mt.ty));
2482 ty_enum(did, ref substs) => {
2484 let vs = enum_variants(cx, did);
2486 let mut r = Representable;
2487 for variant in vs.iter() {
2488 let iter = variant.args.iter().map(|aty| subst(cx, substs, *aty));
2489 r = find_nonrepresentable(cx, seen, iter);
2491 if r != Representable { break }
2502 debug!("is_type_representable: {}",
2503 ::util::ppaux::ty_to_str(cx, ty));
2505 // To avoid a stack overflow when checking an enum variant or struct that
2506 // contains a different, structurally recursive type, maintain a stack
2507 // of seen types and check recursion for each of them (issues #3008, #3779).
2508 let mut seen: Vec<DefId> = Vec::new();
2509 type_structurally_recursive(cx, &mut seen, ty)
2512 pub fn type_is_trait(ty: t) -> bool {
2514 ty_trait(..) => true,
2519 pub fn type_is_integral(ty: t) -> bool {
2521 ty_infer(IntVar(_)) | ty_int(_) | ty_uint(_) => true,
2526 pub fn type_is_uint(ty: t) -> bool {
2528 ty_infer(IntVar(_)) | ty_uint(ast::TyU) => true,
2533 pub fn type_is_char(ty: t) -> bool {
2540 pub fn type_is_bare_fn(ty: t) -> bool {
2542 ty_bare_fn(..) => true,
2547 pub fn type_is_fp(ty: t) -> bool {
2549 ty_infer(FloatVar(_)) | ty_float(_) => true,
2554 pub fn type_is_numeric(ty: t) -> bool {
2555 return type_is_integral(ty) || type_is_fp(ty);
2558 pub fn type_is_signed(ty: t) -> bool {
2565 pub fn type_is_machine(ty: t) -> bool {
2567 ty_int(ast::TyI) | ty_uint(ast::TyU) => false,
2568 ty_int(..) | ty_uint(..) | ty_float(..) => true,
2573 // Is the type's representation size known at compile time?
2574 #[allow(dead_code)] // leaving in for DST
2575 pub fn type_is_sized(cx: &ctxt, ty: ty::t) -> bool {
2577 // FIXME(#6308) add trait, vec, str, etc here.
2579 let ty_param_defs = cx.ty_param_defs.borrow();
2580 let param_def = ty_param_defs.get(&p.def_id.node);
2581 if param_def.bounds.builtin_bounds.contains_elem(BoundSized) {
2590 // Whether a type is enum like, that is an enum type with only nullary
2592 pub fn type_is_c_like_enum(cx: &ctxt, ty: t) -> bool {
2594 ty_enum(did, _) => {
2595 let variants = enum_variants(cx, did);
2596 if variants.len() == 0 {
2599 variants.iter().all(|v| v.args.len() == 0)
2606 // Returns the type and mutability of *t.
2608 // The parameter `explicit` indicates if this is an *explicit* dereference.
2609 // Some types---notably unsafe ptrs---can only be dereferenced explicitly.
2610 pub fn deref(t: t, explicit: bool) -> Option<mt> {
2612 ty_box(typ) | ty_uniq(typ) => Some(mt {
2614 mutbl: ast::MutImmutable,
2616 ty_rptr(_, mt) => Some(mt),
2617 ty_ptr(mt) if explicit => Some(mt),
2622 // Returns the type of t[i]
2623 pub fn index(t: t) -> Option<t> {
2625 ty_vec(ty, _) => Some(ty),
2626 ty_str(_) => Some(mk_u8()),
2631 pub fn node_id_to_trait_ref(cx: &ctxt, id: ast::NodeId) -> @ty::TraitRef {
2632 match cx.trait_refs.borrow().find(&id) {
2634 None => cx.sess.bug(
2635 format!("node_id_to_trait_ref: no trait ref for node `{}`",
2636 cx.map.node_to_str(id)))
2640 pub fn try_node_id_to_type(cx: &ctxt, id: ast::NodeId) -> Option<t> {
2641 cx.node_types.borrow().find_copy(&(id as uint))
2644 pub fn node_id_to_type(cx: &ctxt, id: ast::NodeId) -> t {
2645 match try_node_id_to_type(cx, id) {
2647 None => cx.sess.bug(
2648 format!("node_id_to_type: no type for node `{}`",
2649 cx.map.node_to_str(id)))
2653 pub fn node_id_to_type_opt(cx: &ctxt, id: ast::NodeId) -> Option<t> {
2654 match cx.node_types.borrow().find(&(id as uint)) {
2655 Some(&t) => Some(t),
2660 // FIXME(pcwalton): Makes a copy, bleh. Probably better to not do that.
2661 pub fn node_id_to_type_params(cx: &ctxt, id: ast::NodeId) -> Vec<t> {
2662 match cx.node_type_substs.borrow().find(&id) {
2663 None => return Vec::new(),
2664 Some(ts) => return (*ts).clone(),
2668 pub fn fn_is_variadic(fty: t) -> bool {
2669 match get(fty).sty {
2670 ty_bare_fn(ref f) => f.sig.variadic,
2671 ty_closure(ref f) => f.sig.variadic,
2673 fail!("fn_is_variadic() called on non-fn type: {:?}", s)
2678 pub fn ty_fn_sig(fty: t) -> FnSig {
2679 match get(fty).sty {
2680 ty_bare_fn(ref f) => f.sig.clone(),
2681 ty_closure(ref f) => f.sig.clone(),
2683 fail!("ty_fn_sig() called on non-fn type: {:?}", s)
2688 // Type accessors for substructures of types
2689 pub fn ty_fn_args(fty: t) -> Vec<t> {
2690 match get(fty).sty {
2691 ty_bare_fn(ref f) => f.sig.inputs.clone(),
2692 ty_closure(ref f) => f.sig.inputs.clone(),
2694 fail!("ty_fn_args() called on non-fn type: {:?}", s)
2699 pub fn ty_closure_sigil(fty: t) -> Sigil {
2700 match get(fty).sty {
2701 ty_closure(ref f) => f.sigil,
2703 fail!("ty_closure_sigil() called on non-closure type: {:?}", s)
2708 pub fn ty_fn_ret(fty: t) -> t {
2709 match get(fty).sty {
2710 ty_bare_fn(ref f) => f.sig.output,
2711 ty_closure(ref f) => f.sig.output,
2713 fail!("ty_fn_ret() called on non-fn type: {:?}", s)
2718 pub fn is_fn_ty(fty: t) -> bool {
2719 match get(fty).sty {
2720 ty_bare_fn(_) => true,
2721 ty_closure(_) => true,
2726 pub fn ty_region(tcx: &ctxt,
2731 ty_vec(_, VstoreSlice(r, _)) => r,
2732 ty_str(VstoreSlice(r, ())) => r,
2736 format!("ty_region() invoked on in appropriate ty: {:?}", s));
2741 // Returns the type of a pattern as a monotype. Like @expr_ty, this function
2742 // doesn't provide type parameter substitutions.
2743 pub fn pat_ty(cx: &ctxt, pat: &ast::Pat) -> t {
2744 return node_id_to_type(cx, pat.id);
2748 // Returns the type of an expression as a monotype.
2750 // NB (1): This is the PRE-ADJUSTMENT TYPE for the expression. That is, in
2751 // some cases, we insert `AutoAdjustment` annotations such as auto-deref or
2752 // auto-ref. The type returned by this function does not consider such
2753 // adjustments. See `expr_ty_adjusted()` instead.
2755 // NB (2): This type doesn't provide type parameter substitutions; e.g. if you
2756 // ask for the type of "id" in "id(3)", it will return "fn(&int) -> int"
2757 // instead of "fn(t) -> T with T = int". If this isn't what you want, see
2758 // expr_ty_params_and_ty() below.
2759 pub fn expr_ty(cx: &ctxt, expr: &ast::Expr) -> t {
2760 return node_id_to_type(cx, expr.id);
2763 pub fn expr_ty_opt(cx: &ctxt, expr: &ast::Expr) -> Option<t> {
2764 return node_id_to_type_opt(cx, expr.id);
2767 pub fn expr_ty_adjusted(cx: &ctxt,
2769 method_map: &FnvHashMap<MethodCall, MethodCallee>)
2773 * Returns the type of `expr`, considering any `AutoAdjustment`
2774 * entry recorded for that expression.
2776 * It would almost certainly be better to store the adjusted ty in with
2777 * the `AutoAdjustment`, but I opted not to do this because it would
2778 * require serializing and deserializing the type and, although that's not
2779 * hard to do, I just hate that code so much I didn't want to touch it
2780 * unless it was to fix it properly, which seemed a distraction from the
2781 * task at hand! -nmatsakis
2784 let unadjusted_ty = expr_ty(cx, expr);
2785 let adjustment = cx.adjustments.borrow().find_copy(&expr.id);
2786 adjust_ty(cx, expr.span, expr.id, unadjusted_ty, adjustment, |method_call| {
2787 method_map.find(&method_call).map(|method| method.ty)
2791 pub fn expr_span(cx: &ctxt, id: NodeId) -> Span {
2792 match cx.map.find(id) {
2793 Some(ast_map::NodeExpr(e)) => {
2797 cx.sess.bug(format!("Node id {} is not an expr: {:?}",
2801 cx.sess.bug(format!("Node id {} is not present \
2802 in the node map", id));
2807 pub fn local_var_name_str(cx: &ctxt, id: NodeId) -> InternedString {
2808 match cx.map.find(id) {
2809 Some(ast_map::NodeLocal(pat)) => {
2811 ast::PatIdent(_, ref path, _) => {
2812 token::get_ident(ast_util::path_to_ident(path))
2816 format!("Variable id {} maps to {:?}, not local",
2823 format!("Variable id {} maps to {:?}, not local",
2829 pub fn adjust_ty(cx: &ctxt,
2831 expr_id: ast::NodeId,
2832 unadjusted_ty: ty::t,
2833 adjustment: Option<@AutoAdjustment>,
2834 method_type: |MethodCall| -> Option<ty::t>)
2836 /*! See `expr_ty_adjusted` */
2838 return match adjustment {
2839 Some(adjustment) => {
2841 AutoAddEnv(r, s) => {
2842 match ty::get(unadjusted_ty).sty {
2843 ty::ty_bare_fn(ref b) => {
2846 ty::ClosureTy {fn_style: b.fn_style,
2848 onceness: ast::Many,
2850 bounds: ty::AllBuiltinBounds(),
2851 sig: b.sig.clone()})
2855 format!("add_env adjustment on non-bare-fn: \
2862 AutoDerefRef(ref adj) => {
2863 let mut adjusted_ty = unadjusted_ty;
2865 if !ty::type_is_error(adjusted_ty) {
2866 for i in range(0, adj.autoderefs) {
2867 match method_type(MethodCall::autoderef(expr_id, i as u32)) {
2868 Some(method_ty) => {
2869 adjusted_ty = ty_fn_ret(method_ty);
2873 match deref(adjusted_ty, true) {
2874 Some(mt) => { adjusted_ty = mt.ty; }
2878 format!("the {}th autoderef failed: \
2881 ty_to_str(cx, adjusted_ty)));
2888 None => adjusted_ty,
2889 Some(ref autoref) => {
2898 AutoBorrowVec(r, m) => {
2899 borrow_vec(cx, span, r, m, adjusted_ty)
2902 AutoBorrowVecRef(r, m) => {
2903 adjusted_ty = borrow_vec(cx,
2910 mutbl: ast::MutImmutable
2914 AutoBorrowFn(r) => {
2915 borrow_fn(cx, span, r, adjusted_ty)
2919 mk_ptr(cx, mt {ty: adjusted_ty, mutbl: m})
2922 AutoBorrowObj(r, m) => {
2923 borrow_obj(cx, span, r, m, adjusted_ty)
2930 AutoObject(store, bounds, def_id, ref substs) => {
2931 mk_trait(cx, def_id, substs.clone(), store, bounds)
2935 None => unadjusted_ty
2938 fn borrow_vec(cx: &ctxt, span: Span,
2939 r: Region, m: ast::Mutability,
2940 ty: ty::t) -> ty::t {
2943 ty::mk_vec(cx, ty, VstoreSlice(r, m))
2947 ty::mk_str(cx, VstoreSlice(r, ()))
2953 format!("borrow-vec associated with bad sty: {:?}",
2959 fn borrow_fn(cx: &ctxt, span: Span, r: Region, ty: ty::t) -> ty::t {
2961 ty_closure(ref fty) => {
2962 ty::mk_closure(cx, ClosureTy {
2963 sigil: BorrowedSigil,
2972 format!("borrow-fn associated with bad sty: {:?}",
2978 fn borrow_obj(cx: &ctxt, span: Span, r: Region,
2979 m: ast::Mutability, ty: ty::t) -> ty::t {
2981 ty_trait(~ty::TyTrait {def_id, ref substs, bounds, .. }) => {
2982 ty::mk_trait(cx, def_id, substs.clone(),
2983 RegionTraitStore(r, m), bounds)
2988 format!("borrow-trait-obj associated with bad sty: {:?}",
2996 pub fn map_region(&self, f: |Region| -> Region) -> AutoRef {
2998 ty::AutoPtr(r, m) => ty::AutoPtr(f(r), m),
2999 ty::AutoBorrowVec(r, m) => ty::AutoBorrowVec(f(r), m),
3000 ty::AutoBorrowVecRef(r, m) => ty::AutoBorrowVecRef(f(r), m),
3001 ty::AutoBorrowFn(r) => ty::AutoBorrowFn(f(r)),
3002 ty::AutoUnsafe(m) => ty::AutoUnsafe(m),
3003 ty::AutoBorrowObj(r, m) => ty::AutoBorrowObj(f(r), m),
3008 pub struct ParamsTy {
3013 #[allow(dead_code)] // this may be useful?
3014 pub fn expr_ty_params_and_ty(cx: &ctxt,
3018 params: node_id_to_type_params(cx, expr.id),
3019 ty: node_id_to_type(cx, expr.id)
3023 pub fn method_call_type_param_defs(tcx: &ctxt, origin: typeck::MethodOrigin)
3024 -> Rc<Vec<TypeParameterDef>> {
3026 typeck::MethodStatic(did) => {
3027 // n.b.: When we encode impl methods, the bounds
3028 // that we encode include both the impl bounds
3029 // and then the method bounds themselves...
3030 ty::lookup_item_type(tcx, did).generics.type_param_defs
3032 typeck::MethodParam(typeck::MethodParam {
3034 method_num: n_mth, ..}) |
3035 typeck::MethodObject(typeck::MethodObject {
3037 method_num: n_mth, ..}) => {
3038 // ...trait methods bounds, in contrast, include only the
3039 // method bounds, so we must preprend the tps from the
3040 // trait itself. This ought to be harmonized.
3041 let trait_type_param_defs =
3042 lookup_trait_def(tcx, trt_id).generics.type_param_defs();
3043 Rc::new(Vec::from_slice(trait_type_param_defs).append(
3044 ty::trait_method(tcx, trt_id, n_mth).generics.type_param_defs()))
3049 pub fn resolve_expr(tcx: &ctxt, expr: &ast::Expr) -> ast::Def {
3050 match tcx.def_map.borrow().find(&expr.id) {
3053 tcx.sess.span_bug(expr.span, format!(
3054 "no def-map entry for expr {:?}", expr.id));
3059 pub fn expr_is_lval(tcx: &ctxt,
3060 method_map: MethodMap,
3061 e: &ast::Expr) -> bool {
3062 match expr_kind(tcx, method_map, e) {
3064 RvalueDpsExpr | RvalueDatumExpr | RvalueStmtExpr => false
3068 /// We categorize expressions into three kinds. The distinction between
3069 /// lvalue/rvalue is fundamental to the language. The distinction between the
3070 /// two kinds of rvalues is an artifact of trans which reflects how we will
3071 /// generate code for that kind of expression. See trans/expr.rs for more
3080 pub fn expr_kind(tcx: &ctxt,
3081 method_map: MethodMap,
3082 expr: &ast::Expr) -> ExprKind {
3083 if method_map.borrow().contains_key(&MethodCall::expr(expr.id)) {
3084 // Overloaded operations are generally calls, and hence they are
3085 // generated via DPS, but there are two exceptions:
3086 return match expr.node {
3087 // `a += b` has a unit result.
3088 ast::ExprAssignOp(..) => RvalueStmtExpr,
3090 // the deref method invoked for `*a` always yields an `&T`
3091 ast::ExprUnary(ast::UnDeref, _) => LvalueExpr,
3093 // in the general case, result could be any type, use DPS
3099 ast::ExprPath(..) => {
3100 match resolve_expr(tcx, expr) {
3101 ast::DefVariant(tid, vid, _) => {
3102 let variant_info = enum_variant_with_id(tcx, tid, vid);
3103 if variant_info.args.len() > 0u {
3112 ast::DefStruct(_) => {
3113 match get(expr_ty(tcx, expr)).sty {
3114 ty_bare_fn(..) => RvalueDatumExpr,
3119 // Fn pointers are just scalar values.
3120 ast::DefFn(..) | ast::DefStaticMethod(..) => RvalueDatumExpr,
3122 // Note: there is actually a good case to be made that
3123 // DefArg's, particularly those of immediate type, ought to
3124 // considered rvalues.
3125 ast::DefStatic(..) |
3126 ast::DefBinding(..) |
3129 ast::DefLocal(..) => LvalueExpr,
3132 tcx.sess.span_bug(expr.span, format!(
3133 "uncategorized def for expr {:?}: {:?}",
3139 ast::ExprUnary(ast::UnDeref, _) |
3140 ast::ExprField(..) |
3141 ast::ExprIndex(..) => {
3146 ast::ExprMethodCall(..) |
3147 ast::ExprStruct(..) |
3150 ast::ExprMatch(..) |
3151 ast::ExprFnBlock(..) |
3153 ast::ExprBlock(..) |
3154 ast::ExprRepeat(..) |
3155 ast::ExprVstore(_, ast::ExprVstoreSlice) |
3156 ast::ExprVstore(_, ast::ExprVstoreMutSlice) |
3157 ast::ExprVec(..) => {
3161 ast::ExprLit(lit) if lit_is_str(lit) => {
3165 ast::ExprCast(..) => {
3166 match tcx.node_types.borrow().find(&(expr.id as uint)) {
3168 if type_is_trait(t) {
3175 // Technically, it should not happen that the expr is not
3176 // present within the table. However, it DOES happen
3177 // during type check, because the final types from the
3178 // expressions are not yet recorded in the tcx. At that
3179 // time, though, we are only interested in knowing lvalue
3180 // vs rvalue. It would be better to base this decision on
3181 // the AST type in cast node---but (at the time of this
3182 // writing) it's not easy to distinguish casts to traits
3183 // from other casts based on the AST. This should be
3184 // easier in the future, when casts to traits
3185 // would like @Foo, ~Foo, or &Foo.
3191 ast::ExprBreak(..) |
3192 ast::ExprAgain(..) |
3194 ast::ExprWhile(..) |
3196 ast::ExprAssign(..) |
3197 ast::ExprInlineAsm(..) |
3198 ast::ExprAssignOp(..) => {
3202 ast::ExprForLoop(..) => fail!("non-desugared expr_for_loop"),
3204 ast::ExprLit(_) | // Note: LitStr is carved out above
3205 ast::ExprUnary(..) |
3206 ast::ExprAddrOf(..) |
3207 ast::ExprBinary(..) |
3208 ast::ExprVstore(_, ast::ExprVstoreUniq) => {
3212 ast::ExprBox(place, _) => {
3213 // Special case `~T` for now:
3214 let definition = match tcx.def_map.borrow().find(&place.id) {
3216 None => fail!("no def for place"),
3218 let def_id = ast_util::def_id_of_def(definition);
3219 match tcx.lang_items.items.get(ExchangeHeapLangItem as uint) {
3220 &Some(item_def_id) if def_id == item_def_id => {
3223 &Some(_) | &None => RvalueDpsExpr,
3227 ast::ExprParen(e) => expr_kind(tcx, method_map, e),
3229 ast::ExprMac(..) => {
3232 "macro expression remains after expansion");
3237 pub fn stmt_node_id(s: &ast::Stmt) -> ast::NodeId {
3239 ast::StmtDecl(_, id) | StmtExpr(_, id) | StmtSemi(_, id) => {
3242 ast::StmtMac(..) => fail!("unexpanded macro in trans")
3246 pub fn field_idx_strict(tcx: &ctxt, name: ast::Name, fields: &[field])
3249 for f in fields.iter() { if f.ident.name == name { return i; } i += 1u; }
3250 tcx.sess.bug(format!(
3251 "no field named `{}` found in the list of fields `{:?}`",
3252 token::get_name(name),
3253 fields.iter().map(|f| token::get_ident(f.ident).get().to_str()).collect::<Vec<~str>>()));
3256 pub fn method_idx(id: ast::Ident, meths: &[@Method]) -> Option<uint> {
3257 meths.iter().position(|m| m.ident == id)
3260 /// Returns a vector containing the indices of all type parameters that appear
3261 /// in `ty`. The vector may contain duplicates. Probably should be converted
3262 /// to a bitset or some other representation.
3263 pub fn param_tys_in_type(ty: t) -> Vec<param_ty> {
3264 let mut rslt = Vec::new();
3276 pub fn ty_sort_str(cx: &ctxt, t: t) -> ~str {
3278 ty_nil | ty_bot | ty_bool | ty_char | ty_int(_) |
3279 ty_uint(_) | ty_float(_) | ty_str(_) => {
3280 ::util::ppaux::ty_to_str(cx, t)
3283 ty_enum(id, _) => format!("enum {}", item_path_str(cx, id)),
3284 ty_box(_) => ~"@-ptr",
3285 ty_uniq(_) => ~"~-ptr",
3286 ty_vec(_, _) => ~"vector",
3287 ty_ptr(_) => ~"*-ptr",
3288 ty_rptr(_, _) => ~"&-ptr",
3289 ty_bare_fn(_) => ~"extern fn",
3290 ty_closure(_) => ~"fn",
3291 ty_trait(ref inner) => format!("trait {}", item_path_str(cx, inner.def_id)),
3292 ty_struct(id, _) => format!("struct {}", item_path_str(cx, id)),
3293 ty_tup(_) => ~"tuple",
3294 ty_infer(TyVar(_)) => ~"inferred type",
3295 ty_infer(IntVar(_)) => ~"integral variable",
3296 ty_infer(FloatVar(_)) => ~"floating-point variable",
3297 ty_param(_) => ~"type parameter",
3298 ty_self(_) => ~"self",
3299 ty_err => ~"type error"
3303 pub fn type_err_to_str(cx: &ctxt, err: &type_err) -> ~str {
3306 * Explains the source of a type err in a short,
3307 * human readable way. This is meant to be placed in
3308 * parentheses after some larger message. You should
3309 * also invoke `note_and_explain_type_err()` afterwards
3310 * to present additional details, particularly when
3311 * it comes to lifetime-related errors. */
3313 fn terr_vstore_kind_to_str(k: terr_vstore_kind) -> ~str {
3318 terr_trait => ~"trait"
3323 terr_mismatch => ~"types differ",
3324 terr_fn_style_mismatch(values) => {
3325 format!("expected {} fn but found {} fn",
3326 values.expected.to_str(), values.found.to_str())
3328 terr_abi_mismatch(values) => {
3329 format!("expected {} fn but found {} fn",
3330 values.expected.to_str(), values.found.to_str())
3332 terr_onceness_mismatch(values) => {
3333 format!("expected {} fn but found {} fn",
3334 values.expected.to_str(), values.found.to_str())
3336 terr_sigil_mismatch(values) => {
3337 format!("expected {} closure, found {} closure",
3338 values.expected.to_str(),
3339 values.found.to_str())
3341 terr_mutability => ~"values differ in mutability",
3342 terr_box_mutability => ~"boxed values differ in mutability",
3343 terr_vec_mutability => ~"vectors differ in mutability",
3344 terr_ptr_mutability => ~"pointers differ in mutability",
3345 terr_ref_mutability => ~"references differ in mutability",
3346 terr_ty_param_size(values) => {
3347 format!("expected a type with {} type params \
3348 but found one with {} type params",
3349 values.expected, values.found)
3351 terr_tuple_size(values) => {
3352 format!("expected a tuple with {} elements \
3353 but found one with {} elements",
3354 values.expected, values.found)
3356 terr_record_size(values) => {
3357 format!("expected a record with {} fields \
3358 but found one with {} fields",
3359 values.expected, values.found)
3361 terr_record_mutability => {
3362 ~"record elements differ in mutability"
3364 terr_record_fields(values) => {
3365 format!("expected a record with field `{}` but found one with field \
3367 token::get_ident(values.expected),
3368 token::get_ident(values.found))
3370 terr_arg_count => ~"incorrect number of function parameters",
3371 terr_regions_does_not_outlive(..) => {
3372 format!("lifetime mismatch")
3374 terr_regions_not_same(..) => {
3375 format!("lifetimes are not the same")
3377 terr_regions_no_overlap(..) => {
3378 format!("lifetimes do not intersect")
3380 terr_regions_insufficiently_polymorphic(br, _) => {
3381 format!("expected bound lifetime parameter {}, \
3382 but found concrete lifetime",
3383 bound_region_ptr_to_str(cx, br))
3385 terr_regions_overly_polymorphic(br, _) => {
3386 format!("expected concrete lifetime, \
3387 but found bound lifetime parameter {}",
3388 bound_region_ptr_to_str(cx, br))
3390 terr_vstores_differ(k, ref values) => {
3391 format!("{} storage differs: expected `{}` but found `{}`",
3392 terr_vstore_kind_to_str(k),
3393 (*values).expected.repr(cx),
3394 (*values).found.repr(cx))
3396 terr_trait_stores_differ(_, ref values) => {
3397 format!("trait storage differs: expected `{}` but found `{}`",
3398 trait_store_to_str(cx, (*values).expected),
3399 trait_store_to_str(cx, (*values).found))
3401 terr_in_field(err, fname) => {
3402 format!("in field `{}`, {}", token::get_ident(fname),
3403 type_err_to_str(cx, err))
3405 terr_sorts(values) => {
3406 format!("expected {} but found {}",
3407 ty_sort_str(cx, values.expected),
3408 ty_sort_str(cx, values.found))
3410 terr_traits(values) => {
3411 format!("expected trait `{}` but found trait `{}`",
3412 item_path_str(cx, values.expected),
3413 item_path_str(cx, values.found))
3415 terr_builtin_bounds(values) => {
3416 if values.expected.is_empty() {
3417 format!("expected no bounds but found `{}`",
3418 values.found.user_string(cx))
3419 } else if values.found.is_empty() {
3420 format!("expected bounds `{}` but found no bounds",
3421 values.expected.user_string(cx))
3423 format!("expected bounds `{}` but found bounds `{}`",
3424 values.expected.user_string(cx),
3425 values.found.user_string(cx))
3428 terr_integer_as_char => {
3429 format!("expected an integral type but found `char`")
3431 terr_int_mismatch(ref values) => {
3432 format!("expected `{}` but found `{}`",
3433 values.expected.to_str(),
3434 values.found.to_str())
3436 terr_float_mismatch(ref values) => {
3437 format!("expected `{}` but found `{}`",
3438 values.expected.to_str(),
3439 values.found.to_str())
3441 terr_variadic_mismatch(ref values) => {
3442 format!("expected {} fn but found {} function",
3443 if values.expected { "variadic" } else { "non-variadic" },
3444 if values.found { "variadic" } else { "non-variadic" })
3449 pub fn note_and_explain_type_err(cx: &ctxt, err: &type_err) {
3451 terr_regions_does_not_outlive(subregion, superregion) => {
3452 note_and_explain_region(cx, "", subregion, "...");
3453 note_and_explain_region(cx, "...does not necessarily outlive ",
3456 terr_regions_not_same(region1, region2) => {
3457 note_and_explain_region(cx, "", region1, "...");
3458 note_and_explain_region(cx, "...is not the same lifetime as ",
3461 terr_regions_no_overlap(region1, region2) => {
3462 note_and_explain_region(cx, "", region1, "...");
3463 note_and_explain_region(cx, "...does not overlap ",
3466 terr_regions_insufficiently_polymorphic(_, conc_region) => {
3467 note_and_explain_region(cx,
3468 "concrete lifetime that was found is ",
3471 terr_regions_overly_polymorphic(_, conc_region) => {
3472 note_and_explain_region(cx,
3473 "expected concrete lifetime is ",
3480 pub fn provided_source(cx: &ctxt, id: ast::DefId) -> Option<ast::DefId> {
3481 cx.provided_method_sources.borrow().find(&id).map(|x| *x)
3484 pub fn provided_trait_methods(cx: &ctxt, id: ast::DefId) -> Vec<@Method> {
3487 match cx.map.find(id.node) {
3488 Some(ast_map::NodeItem(item)) => {
3490 ItemTrait(_, _, ref ms) => {
3492 ast_util::split_trait_methods(ms.as_slice());
3494 .map(|m| method(cx, ast_util::local_def(m.id)))
3498 cx.sess.bug(format!("provided_trait_methods: \
3499 `{:?}` is not a trait",
3505 cx.sess.bug(format!("provided_trait_methods: `{:?}` is not \
3512 csearch::get_provided_trait_methods(cx, id)
3516 pub fn trait_supertraits(cx: &ctxt, id: ast::DefId) -> @Vec<@TraitRef> {
3518 match cx.supertraits.borrow().find(&id) {
3519 Some(&trait_refs) => { return trait_refs; }
3520 None => {} // Continue.
3523 // Not in the cache. It had better be in the metadata, which means it
3524 // shouldn't be local.
3525 assert!(!is_local(id));
3527 // Get the supertraits out of the metadata and create the
3528 // TraitRef for each.
3529 let result = @csearch::get_supertraits(cx, id);
3530 cx.supertraits.borrow_mut().insert(id, result);
3534 pub fn trait_ref_supertraits(cx: &ctxt, trait_ref: &ty::TraitRef) -> Vec<@TraitRef> {
3535 let supertrait_refs = trait_supertraits(cx, trait_ref.def_id);
3536 supertrait_refs.iter().map(
3537 |supertrait_ref| supertrait_ref.subst(cx, &trait_ref.substs)).collect()
3540 fn lookup_locally_or_in_crate_store<V:Clone>(
3543 map: &mut DefIdMap<V>,
3544 load_external: || -> V) -> V {
3546 * Helper for looking things up in the various maps
3547 * that are populated during typeck::collect (e.g.,
3548 * `cx.methods`, `cx.tcache`, etc). All of these share
3549 * the pattern that if the id is local, it should have
3550 * been loaded into the map by the `typeck::collect` phase.
3551 * If the def-id is external, then we have to go consult
3552 * the crate loading code (and cache the result for the future).
3555 match map.find_copy(&def_id) {
3556 Some(v) => { return v; }
3560 if def_id.krate == ast::LOCAL_CRATE {
3561 fail!("No def'n found for {:?} in tcx.{}", def_id, descr);
3563 let v = load_external();
3564 map.insert(def_id, v.clone());
3568 pub fn trait_method(cx: &ctxt, trait_did: ast::DefId, idx: uint) -> @Method {
3569 let method_def_id = *ty::trait_method_def_ids(cx, trait_did).get(idx);
3570 ty::method(cx, method_def_id)
3574 pub fn trait_methods(cx: &ctxt, trait_did: ast::DefId) -> @Vec<@Method> {
3575 let mut trait_methods = cx.trait_methods_cache.borrow_mut();
3576 match trait_methods.find(&trait_did) {
3577 Some(&methods) => methods,
3579 let def_ids = ty::trait_method_def_ids(cx, trait_did);
3580 let methods = @def_ids.iter().map(|d| ty::method(cx, *d)).collect();
3581 trait_methods.insert(trait_did, methods);
3587 pub fn method(cx: &ctxt, id: ast::DefId) -> @Method {
3588 lookup_locally_or_in_crate_store("methods", id,
3589 &mut *cx.methods.borrow_mut(), || {
3590 @csearch::get_method(cx, id)
3594 pub fn trait_method_def_ids(cx: &ctxt, id: ast::DefId) -> @Vec<DefId> {
3595 lookup_locally_or_in_crate_store("trait_method_def_ids",
3597 &mut *cx.trait_method_def_ids.borrow_mut(),
3599 @csearch::get_trait_method_def_ids(&cx.sess.cstore, id)
3603 pub fn impl_trait_ref(cx: &ctxt, id: ast::DefId) -> Option<@TraitRef> {
3604 match cx.impl_trait_cache.borrow().find(&id) {
3605 Some(&ret) => { return ret; }
3609 let ret = if id.krate == ast::LOCAL_CRATE {
3610 debug!("(impl_trait_ref) searching for trait impl {:?}", id);
3611 match cx.map.find(id.node) {
3612 Some(ast_map::NodeItem(item)) => {
3614 ast::ItemImpl(_, ref opt_trait, _, _) => {
3617 Some(ty::node_id_to_trait_ref(cx, t.ref_id))
3628 csearch::get_impl_trait(cx, id)
3631 cx.impl_trait_cache.borrow_mut().insert(id, ret);
3635 pub fn trait_ref_to_def_id(tcx: &ctxt, tr: &ast::TraitRef) -> ast::DefId {
3636 let def = *tcx.def_map.borrow()
3638 .expect("no def-map entry for trait");
3639 ast_util::def_id_of_def(def)
3642 pub fn try_add_builtin_trait(tcx: &ctxt,
3643 trait_def_id: ast::DefId,
3644 builtin_bounds: &mut BuiltinBounds) -> bool {
3645 //! Checks whether `trait_ref` refers to one of the builtin
3646 //! traits, like `Send`, and adds the corresponding
3647 //! bound to the set `builtin_bounds` if so. Returns true if `trait_ref`
3648 //! is a builtin trait.
3650 match tcx.lang_items.to_builtin_kind(trait_def_id) {
3651 Some(bound) => { builtin_bounds.add(bound); true }
3656 pub fn ty_to_def_id(ty: t) -> Option<ast::DefId> {
3658 ty_trait(~TyTrait { def_id: id, .. }) | ty_struct(id, _) | ty_enum(id, _) => Some(id),
3665 pub struct VariantInfo {
3667 pub arg_names: Option<Vec<ast::Ident> >,
3669 pub name: ast::Ident,
3677 /// Creates a new VariantInfo from the corresponding ast representation.
3679 /// Does not do any caching of the value in the type context.
3680 pub fn from_ast_variant(cx: &ctxt,
3681 ast_variant: &ast::Variant,
3682 discriminant: Disr) -> VariantInfo {
3683 let ctor_ty = node_id_to_type(cx, ast_variant.node.id);
3685 match ast_variant.node.kind {
3686 ast::TupleVariantKind(ref args) => {
3687 let arg_tys = if args.len() > 0 {
3688 ty_fn_args(ctor_ty).iter().map(|a| *a).collect()
3693 return VariantInfo {
3697 name: ast_variant.node.name,
3698 id: ast_util::local_def(ast_variant.node.id),
3699 disr_val: discriminant,
3700 vis: ast_variant.node.vis
3703 ast::StructVariantKind(ref struct_def) => {
3705 let fields: &[StructField] = struct_def.fields.as_slice();
3707 assert!(fields.len() > 0);
3709 let arg_tys = ty_fn_args(ctor_ty).iter().map(|a| *a).collect();
3710 let arg_names = fields.iter().map(|field| {
3711 match field.node.kind {
3712 NamedField(ident, _) => ident,
3713 UnnamedField(..) => cx.sess.bug(
3714 "enum_variants: all fields in struct must have a name")
3718 return VariantInfo {
3720 arg_names: Some(arg_names),
3722 name: ast_variant.node.name,
3723 id: ast_util::local_def(ast_variant.node.id),
3724 disr_val: discriminant,
3725 vis: ast_variant.node.vis
3732 pub fn substd_enum_variants(cx: &ctxt,
3735 -> Vec<@VariantInfo> {
3736 enum_variants(cx, id).iter().map(|variant_info| {
3737 let substd_args = variant_info.args.iter()
3738 .map(|aty| subst(cx, substs, *aty)).collect();
3740 let substd_ctor_ty = subst(cx, substs, variant_info.ctor_ty);
3744 ctor_ty: substd_ctor_ty,
3745 ..(**variant_info).clone()
3750 pub fn item_path_str(cx: &ctxt, id: ast::DefId) -> ~str {
3751 with_path(cx, id, |path| ast_map::path_to_str(path))
3756 TraitDtor(DefId, bool)
3760 pub fn is_not_present(&self) -> bool {
3767 pub fn is_present(&self) -> bool {
3768 !self.is_not_present()
3771 pub fn has_drop_flag(&self) -> bool {
3774 &TraitDtor(_, flag) => flag
3779 /* If struct_id names a struct with a dtor, return Some(the dtor's id).
3780 Otherwise return none. */
3781 pub fn ty_dtor(cx: &ctxt, struct_id: DefId) -> DtorKind {
3782 match cx.destructor_for_type.borrow().find(&struct_id) {
3783 Some(&method_def_id) => {
3784 let flag = !has_attr(cx, struct_id, "unsafe_no_drop_flag");
3786 TraitDtor(method_def_id, flag)
3792 pub fn has_dtor(cx: &ctxt, struct_id: DefId) -> bool {
3793 ty_dtor(cx, struct_id).is_present()
3796 pub fn with_path<T>(cx: &ctxt, id: ast::DefId, f: |ast_map::PathElems| -> T) -> T {
3797 if id.krate == ast::LOCAL_CRATE {
3798 cx.map.with_path(id.node, f)
3800 f(ast_map::Values(csearch::get_item_path(cx, id).iter()).chain(None))
3804 pub fn enum_is_univariant(cx: &ctxt, id: ast::DefId) -> bool {
3805 enum_variants(cx, id).len() == 1
3808 pub fn type_is_empty(cx: &ctxt, t: t) -> bool {
3809 match ty::get(t).sty {
3810 ty_enum(did, _) => (*enum_variants(cx, did)).is_empty(),
3815 pub fn enum_variants(cx: &ctxt, id: ast::DefId) -> @Vec<@VariantInfo> {
3816 match cx.enum_var_cache.borrow().find(&id) {
3817 Some(&variants) => return variants,
3818 _ => { /* fallthrough */ }
3821 let result = if ast::LOCAL_CRATE != id.krate {
3822 @csearch::get_enum_variants(cx, id)
3825 Although both this code and check_enum_variants in typeck/check
3826 call eval_const_expr, it should never get called twice for the same
3827 expr, since check_enum_variants also updates the enum_var_cache
3830 match cx.map.get(id.node) {
3831 ast_map::NodeItem(item) => {
3833 ast::ItemEnum(ref enum_definition, _) => {
3834 let mut last_discriminant: Option<Disr> = None;
3835 @enum_definition.variants.iter().map(|&variant| {
3837 let mut discriminant = match last_discriminant {
3838 Some(val) => val + 1,
3839 None => INITIAL_DISCRIMINANT_VALUE
3842 match variant.node.disr_expr {
3843 Some(e) => match const_eval::eval_const_expr_partial(cx, e) {
3844 Ok(const_eval::const_int(val)) => {
3845 discriminant = val as Disr
3847 Ok(const_eval::const_uint(val)) => {
3848 discriminant = val as Disr
3853 "expected signed integer \
3868 @VariantInfo::from_ast_variant(cx,
3871 last_discriminant = Some(discriminant);
3877 cx.sess.bug("enum_variants: id not bound to an enum")
3881 _ => cx.sess.bug("enum_variants: id not bound to an enum")
3886 cx.enum_var_cache.borrow_mut().insert(id, result);
3891 // Returns information about the enum variant with the given ID:
3892 pub fn enum_variant_with_id(cx: &ctxt,
3893 enum_id: ast::DefId,
3894 variant_id: ast::DefId)
3896 let variants = enum_variants(cx, enum_id);
3898 while i < variants.len() {
3899 let variant = *variants.get(i);
3900 if variant.id == variant_id {
3905 cx.sess.bug("enum_variant_with_id(): no variant exists with that ID");
3909 // If the given item is in an external crate, looks up its type and adds it to
3910 // the type cache. Returns the type parameters and type.
3911 pub fn lookup_item_type(cx: &ctxt,
3913 -> ty_param_bounds_and_ty {
3914 lookup_locally_or_in_crate_store(
3915 "tcache", did, &mut *cx.tcache.borrow_mut(),
3916 || csearch::get_type(cx, did))
3919 pub fn lookup_impl_vtables(cx: &ctxt,
3921 -> typeck::impl_res {
3922 lookup_locally_or_in_crate_store(
3923 "impl_vtables", did, &mut *cx.impl_vtables.borrow_mut(),
3924 || csearch::get_impl_vtables(cx, did) )
3927 /// Given the did of a trait, returns its canonical trait ref.
3928 pub fn lookup_trait_def(cx: &ctxt, did: ast::DefId) -> @ty::TraitDef {
3929 let mut trait_defs = cx.trait_defs.borrow_mut();
3930 match trait_defs.find(&did) {
3931 Some(&trait_def) => {
3932 // The item is in this crate. The caller should have added it to the
3933 // type cache already
3937 assert!(did.krate != ast::LOCAL_CRATE);
3938 let trait_def = @csearch::get_trait_def(cx, did);
3939 trait_defs.insert(did, trait_def);
3945 /// Iterate over meta_items of a definition.
3946 // (This should really be an iterator, but that would require csearch and
3947 // decoder to use iterators instead of higher-order functions.)
3948 pub fn each_attr(tcx: &ctxt, did: DefId, f: |@MetaItem| -> bool) -> bool {
3950 let item = tcx.map.expect_item(did.node);
3951 item.attrs.iter().advance(|attr| f(attr.node.value))
3953 let mut cont = true;
3954 csearch::get_item_attrs(&tcx.sess.cstore, did, |meta_items| {
3956 cont = meta_items.iter().advance(|ptrptr| f(*ptrptr));
3963 /// Determine whether an item is annotated with an attribute
3964 pub fn has_attr(tcx: &ctxt, did: DefId, attr: &str) -> bool {
3965 let mut found = false;
3966 each_attr(tcx, did, |item| {
3967 if item.name().equiv(&attr) {
3977 /// Determine whether an item is annotated with `#[packed]`
3978 pub fn lookup_packed(tcx: &ctxt, did: DefId) -> bool {
3979 has_attr(tcx, did, "packed")
3982 /// Determine whether an item is annotated with `#[simd]`
3983 pub fn lookup_simd(tcx: &ctxt, did: DefId) -> bool {
3984 has_attr(tcx, did, "simd")
3987 // Obtain the representation annotation for a definition.
3988 pub fn lookup_repr_hint(tcx: &ctxt, did: DefId) -> attr::ReprAttr {
3989 let mut acc = attr::ReprAny;
3990 ty::each_attr(tcx, did, |meta| {
3991 acc = attr::find_repr_attr(tcx.sess.diagnostic(), meta, acc);
3997 // Look up a field ID, whether or not it's local
3998 // Takes a list of type substs in case the struct is generic
3999 pub fn lookup_field_type(tcx: &ctxt,
4004 let t = if id.krate == ast::LOCAL_CRATE {
4005 node_id_to_type(tcx, id.node)
4007 let mut tcache = tcx.tcache.borrow_mut();
4008 match tcache.find(&id) {
4009 Some(&ty_param_bounds_and_ty {ty, ..}) => ty,
4011 let tpt = csearch::get_field_type(tcx, struct_id, id);
4012 tcache.insert(id, tpt.clone());
4017 subst(tcx, substs, t)
4020 // Look up the list of field names and IDs for a given struct
4021 // Fails if the id is not bound to a struct.
4022 pub fn lookup_struct_fields(cx: &ctxt, did: ast::DefId) -> Vec<field_ty> {
4023 if did.krate == ast::LOCAL_CRATE {
4024 match cx.map.find(did.node) {
4025 Some(ast_map::NodeItem(i)) => {
4027 ast::ItemStruct(struct_def, _) => {
4028 struct_field_tys(struct_def.fields.as_slice())
4030 _ => cx.sess.bug("struct ID bound to non-struct")
4033 Some(ast_map::NodeVariant(ref variant)) => {
4034 match (*variant).node.kind {
4035 ast::StructVariantKind(struct_def) => {
4036 struct_field_tys(struct_def.fields.as_slice())
4039 cx.sess.bug("struct ID bound to enum variant that \
4046 format!("struct ID not bound to an item: {}",
4047 cx.map.node_to_str(did.node)));
4051 csearch::get_struct_fields(&cx.sess.cstore, did)
4055 fn struct_field_tys(fields: &[StructField]) -> Vec<field_ty> {
4056 fields.iter().map(|field| {
4057 match field.node.kind {
4058 NamedField(ident, visibility) => {
4061 id: ast_util::local_def(field.node.id),
4065 UnnamedField(visibility) => {
4067 name: syntax::parse::token::special_idents::unnamed_field.name,
4068 id: ast_util::local_def(field.node.id),
4076 // Returns a list of fields corresponding to the struct's items. trans uses
4077 // this. Takes a list of substs with which to instantiate field types.
4078 pub fn struct_fields(cx: &ctxt, did: ast::DefId, substs: &substs)
4080 lookup_struct_fields(cx, did).iter().map(|f| {
4082 // FIXME #6993: change type of field to Name and get rid of new()
4083 ident: ast::Ident::new(f.name),
4085 ty: lookup_field_type(cx, did, f.id, substs),
4092 pub fn is_binopable(cx: &ctxt, ty: t, op: ast::BinOp) -> bool {
4093 static tycat_other: int = 0;
4094 static tycat_bool: int = 1;
4095 static tycat_char: int = 2;
4096 static tycat_int: int = 3;
4097 static tycat_float: int = 4;
4098 static tycat_bot: int = 5;
4099 static tycat_raw_ptr: int = 6;
4101 static opcat_add: int = 0;
4102 static opcat_sub: int = 1;
4103 static opcat_mult: int = 2;
4104 static opcat_shift: int = 3;
4105 static opcat_rel: int = 4;
4106 static opcat_eq: int = 5;
4107 static opcat_bit: int = 6;
4108 static opcat_logic: int = 7;
4110 fn opcat(op: ast::BinOp) -> int {
4112 ast::BiAdd => opcat_add,
4113 ast::BiSub => opcat_sub,
4114 ast::BiMul => opcat_mult,
4115 ast::BiDiv => opcat_mult,
4116 ast::BiRem => opcat_mult,
4117 ast::BiAnd => opcat_logic,
4118 ast::BiOr => opcat_logic,
4119 ast::BiBitXor => opcat_bit,
4120 ast::BiBitAnd => opcat_bit,
4121 ast::BiBitOr => opcat_bit,
4122 ast::BiShl => opcat_shift,
4123 ast::BiShr => opcat_shift,
4124 ast::BiEq => opcat_eq,
4125 ast::BiNe => opcat_eq,
4126 ast::BiLt => opcat_rel,
4127 ast::BiLe => opcat_rel,
4128 ast::BiGe => opcat_rel,
4129 ast::BiGt => opcat_rel
4133 fn tycat(cx: &ctxt, ty: t) -> int {
4134 if type_is_simd(cx, ty) {
4135 return tycat(cx, simd_type(cx, ty))
4138 ty_char => tycat_char,
4139 ty_bool => tycat_bool,
4140 ty_int(_) | ty_uint(_) | ty_infer(IntVar(_)) => tycat_int,
4141 ty_float(_) | ty_infer(FloatVar(_)) => tycat_float,
4142 ty_bot => tycat_bot,
4143 ty_ptr(_) => tycat_raw_ptr,
4148 static t: bool = true;
4149 static f: bool = false;
4152 // +, -, *, shift, rel, ==, bit, logic
4153 /*other*/ [f, f, f, f, f, f, f, f],
4154 /*bool*/ [f, f, f, f, t, t, t, t],
4155 /*char*/ [f, f, f, f, t, t, f, f],
4156 /*int*/ [t, t, t, t, t, t, t, f],
4157 /*float*/ [t, t, t, f, t, t, f, f],
4158 /*bot*/ [t, t, t, t, t, t, t, t],
4159 /*raw ptr*/ [f, f, f, f, t, t, f, f]];
4161 return tbl[tycat(cx, ty) as uint ][opcat(op) as uint];
4164 /// Returns an equivalent type with all the typedefs and self regions removed.
4165 pub fn normalize_ty(cx: &ctxt, t: t) -> t {
4166 let u = TypeNormalizer(cx).fold_ty(t);
4169 struct TypeNormalizer<'a>(&'a ctxt);
4171 impl<'a> TypeFolder for TypeNormalizer<'a> {
4172 fn tcx<'a>(&'a self) -> &'a ctxt { let TypeNormalizer(c) = *self; c }
4174 fn fold_ty(&mut self, t: ty::t) -> ty::t {
4175 match self.tcx().normalized_cache.borrow().find_copy(&t) {
4180 let t_norm = ty_fold::super_fold_ty(self, t);
4181 self.tcx().normalized_cache.borrow_mut().insert(t, t_norm);
4185 fn fold_vstore<M>(&mut self, vstore: Vstore<M>) -> Vstore<M> {
4187 VstoreFixed(..) | VstoreUniq => vstore,
4188 VstoreSlice(_, m) => VstoreSlice(ReStatic, m)
4192 fn fold_region(&mut self, _: ty::Region) -> ty::Region {
4196 fn fold_substs(&mut self,
4199 substs { regions: ErasedRegions,
4200 self_ty: ty_fold::fold_opt_ty(self, substs.self_ty),
4201 tps: ty_fold::fold_ty_vec(self, substs.tps.as_slice()) }
4204 fn fold_sig(&mut self,
4207 // The binder-id is only relevant to bound regions, which
4208 // are erased at trans time.
4210 binder_id: ast::DUMMY_NODE_ID,
4211 inputs: ty_fold::fold_ty_vec(self, sig.inputs.as_slice()),
4212 output: self.fold_ty(sig.output),
4213 variadic: sig.variadic,
4219 pub trait ExprTyProvider {
4220 fn expr_ty(&self, ex: &ast::Expr) -> t;
4221 fn ty_ctxt<'a>(&'a self) -> &'a ctxt;
4224 impl ExprTyProvider for ctxt {
4225 fn expr_ty(&self, ex: &ast::Expr) -> t {
4229 fn ty_ctxt<'a>(&'a self) -> &'a ctxt {
4234 // Returns the repeat count for a repeating vector expression.
4235 pub fn eval_repeat_count<T: ExprTyProvider>(tcx: &T, count_expr: &ast::Expr) -> uint {
4236 match const_eval::eval_const_expr_partial(tcx, count_expr) {
4237 Ok(ref const_val) => match *const_val {
4238 const_eval::const_int(count) => if count < 0 {
4239 tcx.ty_ctxt().sess.span_err(count_expr.span,
4240 "expected positive integer for \
4241 repeat count but found negative integer");
4244 return count as uint
4246 const_eval::const_uint(count) => return count as uint,
4247 const_eval::const_float(count) => {
4248 tcx.ty_ctxt().sess.span_err(count_expr.span,
4249 "expected positive integer for \
4250 repeat count but found float");
4251 return count as uint;
4253 const_eval::const_str(_) => {
4254 tcx.ty_ctxt().sess.span_err(count_expr.span,
4255 "expected positive integer for \
4256 repeat count but found string");
4259 const_eval::const_bool(_) => {
4260 tcx.ty_ctxt().sess.span_err(count_expr.span,
4261 "expected positive integer for \
4262 repeat count but found boolean");
4265 const_eval::const_binary(_) => {
4266 tcx.ty_ctxt().sess.span_err(count_expr.span,
4267 "expected positive integer for \
4268 repeat count but found binary array");
4273 tcx.ty_ctxt().sess.span_err(count_expr.span,
4274 "expected constant integer for repeat count \
4275 but found variable");
4281 // Determine what the style to check a nested function under
4282 pub fn determine_inherited_style(parent: (ast::FnStyle, ast::NodeId),
4283 child: (ast::FnStyle, ast::NodeId),
4284 child_sigil: ast::Sigil)
4285 -> (ast::FnStyle, ast::NodeId) {
4286 // If the closure is a stack closure and hasn't had some non-standard
4287 // style inferred for it, then check it under its parent's style.
4288 // Otherwise, use its own
4290 ast::BorrowedSigil if child.val0() == ast::NormalFn => parent,
4295 // Iterate over a type parameter's bounded traits and any supertraits
4296 // of those traits, ignoring kinds.
4297 // Here, the supertraits are the transitive closure of the supertrait
4298 // relation on the supertraits from each bounded trait's constraint
4300 pub fn each_bound_trait_and_supertraits(tcx: &ctxt,
4301 bounds: &[@TraitRef],
4302 f: |@TraitRef| -> bool)
4304 for &bound_trait_ref in bounds.iter() {
4305 let mut supertrait_set = HashMap::new();
4306 let mut trait_refs = Vec::new();
4309 // Seed the worklist with the trait from the bound
4310 supertrait_set.insert(bound_trait_ref.def_id, ());
4311 trait_refs.push(bound_trait_ref);
4313 // Add the given trait ty to the hash map
4314 while i < trait_refs.len() {
4315 debug!("each_bound_trait_and_supertraits(i={:?}, trait_ref={})",
4316 i, trait_refs.get(i).repr(tcx));
4318 if !f(*trait_refs.get(i)) {
4322 // Add supertraits to supertrait_set
4323 let supertrait_refs = trait_ref_supertraits(tcx,
4324 *trait_refs.get(i));
4325 for &supertrait_ref in supertrait_refs.iter() {
4326 debug!("each_bound_trait_and_supertraits(supertrait_ref={})",
4327 supertrait_ref.repr(tcx));
4329 let d_id = supertrait_ref.def_id;
4330 if !supertrait_set.contains_key(&d_id) {
4331 // FIXME(#5527) Could have same trait multiple times
4332 supertrait_set.insert(d_id, ());
4333 trait_refs.push(supertrait_ref);
4343 pub fn get_tydesc_ty(tcx: &ctxt) -> Result<t, ~str> {
4344 tcx.lang_items.require(TyDescStructLangItem).map(|tydesc_lang_item| {
4345 tcx.intrinsic_defs.borrow().find_copy(&tydesc_lang_item)
4346 .expect("Failed to resolve TyDesc")
4350 pub fn get_opaque_ty(tcx: &ctxt) -> Result<t, ~str> {
4351 tcx.lang_items.require(OpaqueStructLangItem).map(|opaque_lang_item| {
4352 tcx.intrinsic_defs.borrow().find_copy(&opaque_lang_item)
4353 .expect("Failed to resolve Opaque")
4357 pub fn visitor_object_ty(tcx: &ctxt,
4358 region: ty::Region) -> Result<(@TraitRef, t), ~str> {
4359 let trait_lang_item = match tcx.lang_items.require(TyVisitorTraitLangItem) {
4361 Err(s) => { return Err(s); }
4363 let substs = substs {
4364 regions: ty::NonerasedRegions(OwnedSlice::empty()),
4368 let trait_ref = @TraitRef { def_id: trait_lang_item, substs: substs };
4372 trait_ref.substs.clone(),
4373 RegionTraitStore(region, ast::MutMutable),
4374 EmptyBuiltinBounds())))
4377 pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> @ItemVariances {
4378 lookup_locally_or_in_crate_store(
4379 "item_variance_map", item_id, &mut *tcx.item_variance_map.borrow_mut(),
4380 || @csearch::get_item_variances(&tcx.sess.cstore, item_id))
4383 /// Records a trait-to-implementation mapping.
4384 fn record_trait_implementation(tcx: &ctxt,
4385 trait_def_id: DefId,
4386 implementation: @Impl) {
4387 let implementation_list;
4388 let mut trait_impls = tcx.trait_impls.borrow_mut();
4389 match trait_impls.find(&trait_def_id) {
4391 implementation_list = @RefCell::new(Vec::new());
4392 trait_impls.insert(trait_def_id, implementation_list);
4394 Some(&existing_implementation_list) => {
4395 implementation_list = existing_implementation_list
4399 implementation_list.borrow_mut().push(implementation);
4402 /// Populates the type context with all the implementations for the given type
4404 pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt,
4405 type_id: ast::DefId) {
4406 if type_id.krate == LOCAL_CRATE {
4409 if tcx.populated_external_types.borrow().contains(&type_id) {
4413 csearch::each_implementation_for_type(&tcx.sess.cstore, type_id,
4414 |implementation_def_id| {
4415 let implementation = @csearch::get_impl(tcx, implementation_def_id);
4417 // Record the trait->implementation mappings, if applicable.
4418 let associated_traits = csearch::get_impl_trait(tcx,
4419 implementation.did);
4420 for trait_ref in associated_traits.iter() {
4421 record_trait_implementation(tcx,
4426 // For any methods that use a default implementation, add them to
4427 // the map. This is a bit unfortunate.
4428 for method in implementation.methods.iter() {
4429 for source in method.provided_source.iter() {
4430 tcx.provided_method_sources.borrow_mut()
4431 .insert(method.def_id, *source);
4435 // If this is an inherent implementation, record it.
4436 if associated_traits.is_none() {
4437 let implementation_list;
4438 let mut inherent_impls = tcx.inherent_impls.borrow_mut();
4439 match inherent_impls.find(&type_id) {
4441 implementation_list = @RefCell::new(Vec::new());
4442 inherent_impls.insert(type_id, implementation_list);
4444 Some(&existing_implementation_list) => {
4445 implementation_list = existing_implementation_list;
4448 implementation_list.borrow_mut().push(implementation);
4451 // Store the implementation info.
4452 tcx.impls.borrow_mut().insert(implementation_def_id, implementation);
4455 tcx.populated_external_types.borrow_mut().insert(type_id);
4458 /// Populates the type context with all the implementations for the given
4459 /// trait if necessary.
4460 pub fn populate_implementations_for_trait_if_necessary(
4462 trait_id: ast::DefId) {
4463 if trait_id.krate == LOCAL_CRATE {
4466 if tcx.populated_external_traits.borrow().contains(&trait_id) {
4470 csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id,
4471 |implementation_def_id| {
4472 let implementation = @csearch::get_impl(tcx, implementation_def_id);
4474 // Record the trait->implementation mapping.
4475 record_trait_implementation(tcx, trait_id, implementation);
4477 // For any methods that use a default implementation, add them to
4478 // the map. This is a bit unfortunate.
4479 for method in implementation.methods.iter() {
4480 for source in method.provided_source.iter() {
4481 tcx.provided_method_sources.borrow_mut()
4482 .insert(method.def_id, *source);
4486 // Store the implementation info.
4487 tcx.impls.borrow_mut().insert(implementation_def_id, implementation);
4490 tcx.populated_external_traits.borrow_mut().insert(trait_id);
4493 /// Given the def_id of an impl, return the def_id of the trait it implements.
4494 /// If it implements no trait, return `None`.
4495 pub fn trait_id_of_impl(tcx: &ctxt,
4496 def_id: ast::DefId) -> Option<ast::DefId> {
4497 let node = match tcx.map.find(def_id.node) {
4502 ast_map::NodeItem(item) => {
4504 ast::ItemImpl(_, Some(ref trait_ref), _, _) => {
4505 Some(node_id_to_trait_ref(tcx, trait_ref.ref_id).def_id)
4514 /// If the given def ID describes a method belonging to a trait (either a
4515 /// default method or an implementation of a trait method), return the ID of
4516 /// the trait that the method belongs to. Otherwise, return `None`.
4517 pub fn trait_of_method(tcx: &ctxt, def_id: ast::DefId)
4518 -> Option<ast::DefId> {
4519 if def_id.krate != LOCAL_CRATE {
4520 return csearch::get_trait_of_method(&tcx.sess.cstore, def_id, tcx);
4522 match tcx.methods.borrow().find(&def_id).map(|m| *m) {
4524 match method.container {
4525 TraitContainer(def_id) => Some(def_id),
4526 ImplContainer(def_id) => trait_id_of_impl(tcx, def_id),
4533 /// If the given def ID describes a method belonging to a trait, (either a
4534 /// default method or an implementation of a trait method), return the ID of
4535 /// the method inside trait definition (this means that if the given def ID
4536 /// is already that of the original trait method, then the return value is
4538 /// Otherwise, return `None`.
4539 pub fn trait_method_of_method(tcx: &ctxt,
4540 def_id: ast::DefId) -> Option<ast::DefId> {
4541 let method = match tcx.methods.borrow().find(&def_id) {
4543 None => return None,
4545 let name = method.ident.name;
4546 match trait_of_method(tcx, def_id) {
4547 Some(trait_did) => {
4548 let trait_methods = ty::trait_methods(tcx, trait_did);
4549 trait_methods.iter()
4550 .position(|m| m.ident.name == name)
4551 .map(|idx| ty::trait_method(tcx, trait_did, idx).def_id)
4557 /// Creates a hash of the type `t` which will be the same no matter what crate
4558 /// context it's calculated within. This is used by the `type_id` intrinsic.
4559 pub fn hash_crate_independent(tcx: &ctxt, t: t, svh: &Svh) -> u64 {
4560 let mut state = sip::SipState::new();
4561 macro_rules! byte( ($b:expr) => { ($b as u8).hash(&mut state) } );
4562 macro_rules! hash( ($e:expr) => { $e.hash(&mut state) } );
4564 let region = |_state: &mut sip::SipState, r: Region| {
4574 tcx.sess.bug("non-static region found when hashing a type")
4578 let did = |state: &mut sip::SipState, did: DefId| {
4579 let h = if ast_util::is_local(did) {
4582 tcx.sess.cstore.get_crate_hash(did.krate)
4584 h.as_str().hash(state);
4585 did.node.hash(state);
4587 let mt = |state: &mut sip::SipState, mt: mt| {
4588 mt.mutbl.hash(state);
4590 ty::walk_ty(t, |t| {
4591 match ty::get(t).sty {
4594 ty_bool => byte!(2),
4595 ty_char => byte!(3),
4632 region(&mut state, r);
4635 ty_bare_fn(ref b) => {
4640 ty_closure(ref c) => {
4646 region(&mut state, c.region);
4648 ty_trait(~ty::TyTrait { def_id: d, store, bounds, .. }) => {
4652 UniqTraitStore => byte!(0),
4653 RegionTraitStore(r, m) => {
4655 region(&mut state, r);
4661 ty_struct(d, _) => {
4665 ty_tup(ref inner) => {
4672 did(&mut state, p.def_id);
4678 ty_infer(_) => unreachable!(),
4679 ty_err => byte!(23),
4687 pub fn to_str(self) -> &'static str {
4690 Contravariant => "-",
4697 pub fn construct_parameter_environment(
4699 self_bound: Option<@TraitRef>,
4700 item_type_params: &[TypeParameterDef],
4701 method_type_params: &[TypeParameterDef],
4702 item_region_params: &[RegionParameterDef],
4703 method_region_params: &[RegionParameterDef],
4704 free_id: ast::NodeId)
4705 -> ParameterEnvironment
4707 /*! See `ParameterEnvironment` struct def'n for details */
4710 // Construct the free substs.
4714 let self_ty = self_bound.map(|t| ty::mk_self(tcx, t.def_id));
4717 let num_item_type_params = item_type_params.len();
4718 let num_method_type_params = method_type_params.len();
4719 let num_type_params = num_item_type_params + num_method_type_params;
4720 let type_params = Vec::from_fn(num_type_params, |i| {
4721 let def_id = if i < num_item_type_params {
4722 item_type_params[i].def_id
4724 method_type_params[i - num_item_type_params].def_id
4727 ty::mk_param(tcx, i, def_id)
4730 // map bound 'a => free 'a
4731 let region_params = {
4732 fn push_region_params(mut accum: Vec<ty::Region>,
4733 free_id: ast::NodeId,
4734 region_params: &[RegionParameterDef])
4735 -> Vec<ty::Region> {
4736 for r in region_params.iter() {
4738 ty::ReFree(ty::FreeRegion {
4740 bound_region: ty::BrNamed(r.def_id, r.name)}));
4745 let t = push_region_params(vec!(), free_id, item_region_params);
4746 push_region_params(t, free_id, method_region_params)
4749 let free_substs = substs {
4752 regions: ty::NonerasedRegions(OwnedSlice::from_vec(region_params))
4756 // Compute the bounds on Self and the type parameters.
4759 let self_bound_substd = self_bound.map(|b| b.subst(tcx, &free_substs));
4760 let type_param_bounds_substd = Vec::from_fn(num_type_params, |i| {
4761 if i < num_item_type_params {
4762 (*item_type_params[i].bounds).subst(tcx, &free_substs)
4764 let j = i - num_item_type_params;
4765 (*method_type_params[j].bounds).subst(tcx, &free_substs)
4769 debug!("construct_parameter_environment: free_id={} \
4771 self_param_bound={} \
4772 type_param_bound={}",
4774 free_substs.repr(tcx),
4775 self_bound_substd.repr(tcx),
4776 type_param_bounds_substd.repr(tcx));
4778 ty::ParameterEnvironment {
4779 free_substs: free_substs,
4780 self_param_bound: self_bound_substd,
4781 type_param_bounds: type_param_bounds_substd,
4786 pub fn empty() -> substs {
4790 regions: NonerasedRegions(OwnedSlice::empty())
4796 pub fn from_mutbl(m: ast::Mutability) -> BorrowKind {
4798 ast::MutMutable => MutBorrow,
4799 ast::MutImmutable => ImmBorrow,
4803 pub fn to_user_str(&self) -> &'static str {
4805 MutBorrow => "mutable",
4806 ImmBorrow => "immutable",
4807 UniqueImmBorrow => "uniquely immutable",