src/librustc_trans/type_of.rs

   1 // Copyright 2012-2013 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.
   4 //
   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.
  10
  11 #![allow(non_camel_case_types)]
  12
  13 use rustc::hir::def_id::DefId;
  14 use rustc::infer;
  15 use rustc::ty::subst;
  16 use abi::FnType;
  17 use adt;
  18 use common::*;
  19 use machine;
  20 use rustc::traits::ProjectionMode;
  21 use rustc::ty::{self, Ty, TypeFoldable};
  22
  23 use type_::Type;
  24
  25 use syntax::ast;
  26
  27 // LLVM doesn't like objects that are too big. Issue #17913
  28 fn ensure_array_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
  29                                                 llet: Type,
  30                                                 size: machine::llsize,
  31                                                 scapegoat: Ty<'tcx>) {
  32     let esz = machine::llsize_of_alloc(ccx, llet);
  33     match esz.checked_mul(size) {
  34         Some(n) if n < ccx.obj_size_bound() => {}
  35         _ => { ccx.report_overbig_object(scapegoat) }
  36     }
  37 }
  38
  39 // A "sizing type" is an LLVM type, the size and alignment of which are
  40 // guaranteed to be equivalent to what you would get out of `type_of()`. It's
  41 // useful because:
  42 //
  43 // (1) It may be cheaper to compute the sizing type than the full type if all
  44 //     you're interested in is the size and/or alignment;
  45 //
  46 // (2) It won't make any recursive calls to determine the structure of the
  47 //     type behind pointers. This can help prevent infinite loops for
  48 //     recursive types. For example, enum types rely on this behavior.
  49
  50 pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
  51     if let Some(t) = cx.llsizingtypes().borrow().get(&t).cloned() {
  52         return t;
  53     }
  54
  55     debug!("sizing_type_of {:?}", t);
  56     let _recursion_lock = cx.enter_type_of(t);
  57
  58     let llsizingty = match t.sty {
  59         _ if !type_is_sized(cx.tcx(), t) => {
  60             Type::struct_(cx, &[Type::i8p(cx), unsized_info_ty(cx, t)], false)
  61         }
  62
  63         ty::TyBool => Type::bool(cx),
  64         ty::TyChar => Type::char(cx),
  65         ty::TyInt(t) => Type::int_from_ty(cx, t),
  66         ty::TyUint(t) => Type::uint_from_ty(cx, t),
  67         ty::TyFloat(t) => Type::float_from_ty(cx, t),
  68
  69         ty::TyBox(ty) |
  70         ty::TyRef(_, ty::TypeAndMut{ty, ..}) |
  71         ty::TyRawPtr(ty::TypeAndMut{ty, ..}) => {
  72             if type_is_sized(cx.tcx(), ty) {
  73                 Type::i8p(cx)
  74             } else {
  75                 Type::struct_(cx, &[Type::i8p(cx), unsized_info_ty(cx, ty)], false)
  76             }
  77         }
  78
  79         ty::TyFnDef(..) => Type::nil(cx),
  80         ty::TyFnPtr(_) => Type::i8p(cx),
  81
  82         ty::TyArray(ty, size) => {
  83             let llty = sizing_type_of(cx, ty);
  84             let size = size as u64;
  85             ensure_array_fits_in_address_space(cx, llty, size, t);
  86             Type::array(&llty, size)
  87         }
  88
  89         ty::TyTuple(ref tys) if tys.is_empty() => {
  90             Type::nil(cx)
  91         }
  92
  93         ty::TyTuple(..) | ty::TyEnum(..) | ty::TyClosure(..) => {
  94             let repr = adt::represent_type(cx, t);
  95             adt::sizing_type_of(cx, &repr, false)
  96         }
  97
  98         ty::TyStruct(..) => {
  99             if t.is_simd() {
 100                 let e = t.simd_type(cx.tcx());
 101                 if !e.is_machine() {
 102                     cx.sess().fatal(&format!("monomorphising SIMD type `{}` with \
 103                                               a non-machine element type `{}`",
 104                                              t, e))
 105                 }
 106                 let llet = type_of(cx, e);
 107                 let n = t.simd_size(cx.tcx()) as u64;
 108                 ensure_array_fits_in_address_space(cx, llet, n, t);
 109                 Type::vector(&llet, n)
 110             } else {
 111                 let repr = adt::represent_type(cx, t);
 112                 adt::sizing_type_of(cx, &repr, false)
 113             }
 114         }
 115
 116         ty::TyProjection(..) | ty::TyInfer(..) | ty::TyParam(..) | ty::TyError => {
 117             bug!("fictitious type {:?} in sizing_type_of()", t)
 118         }
 119         ty::TySlice(_) | ty::TyTrait(..) | ty::TyStr => bug!()
 120     };
 121
 122     debug!("--> mapped t={:?} to llsizingty={:?}", t, llsizingty);
 123
 124     cx.llsizingtypes().borrow_mut().insert(t, llsizingty);
 125
 126     // FIXME(eddyb) Temporary sanity check for ty::layout.
 127     let infcx = infer::normalizing_infer_ctxt(cx.tcx(), &cx.tcx().tables, ProjectionMode::Any);
 128     match t.layout(&infcx) {
 129         Ok(layout) => {
 130             if !type_is_sized(cx.tcx(), t) {
 131                 if !layout.is_unsized() {
 132                     bug!("layout should be unsized for type `{}` / {:#?}",
 133                          t, layout);
 134                 }
 135
 136                 // Unsized types get turned into a fat pointer for LLVM.
 137                 return llsizingty;
 138             }
 139             let r = layout.size(&cx.tcx().data_layout).bytes();
 140             let l = machine::llsize_of_alloc(cx, llsizingty);
 141             if r != l {
 142                 bug!("size differs (rustc: {}, llvm: {}) for type `{}` / {:#?}",
 143                      r, l, t, layout);
 144             }
 145             let r = layout.align(&cx.tcx().data_layout).abi();
 146             let l = machine::llalign_of_min(cx, llsizingty) as u64;
 147             if r != l {
 148                 bug!("align differs (rustc: {}, llvm: {}) for type `{}` / {:#?}",
 149                      r, l, t, layout);
 150             }
 151         }
 152         Err(e) => {
 153             bug!("failed to get layout for `{}`: {}", t, e);
 154         }
 155     }
 156     llsizingty
 157 }
 158
 159 fn unsized_info_ty<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>) -> Type {
 160     let unsized_part = ccx.tcx().struct_tail(ty);
 161     match unsized_part.sty {
 162         ty::TyStr | ty::TyArray(..) | ty::TySlice(_) => {
 163             Type::uint_from_ty(ccx, ast::UintTy::Us)
 164         }
 165         ty::TyTrait(_) => Type::vtable_ptr(ccx),
 166         _ => bug!("Unexpected tail in unsized_info_ty: {:?} for ty={:?}",
 167                           unsized_part, ty)
 168     }
 169 }
 170
 171 pub fn immediate_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
 172     if t.is_bool() {
 173         Type::i1(cx)
 174     } else {
 175         type_of(cx, t)
 176     }
 177 }
 178
 179 /// Get the LLVM type corresponding to a Rust type, i.e. `rustc::ty::Ty`.
 180 /// This is the right LLVM type for an alloca containing a value of that type,
 181 /// and the pointee of an Lvalue Datum (which is always a LLVM pointer).
 182 /// For unsized types, the returned type is a fat pointer, thus the resulting
 183 /// LLVM type for a `Trait` Lvalue is `{ i8*, void(i8*)** }*`, which is a double
 184 /// indirection to the actual data, unlike a `i8` Lvalue, which is just `i8*`.
 185 /// This is needed due to the treatment of immediate values, as a fat pointer
 186 /// is too large for it to be placed in SSA value (by our rules).
 187 /// For the raw type without far pointer indirection, see `in_memory_type_of`.
 188 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, ty: Ty<'tcx>) -> Type {
 189     let ty = if !type_is_sized(cx.tcx(), ty) {
 190         cx.tcx().mk_imm_ptr(ty)
 191     } else {
 192         ty
 193     };
 194     in_memory_type_of(cx, ty)
 195 }
 196
 197 /// Get the LLVM type corresponding to a Rust type, i.e. `rustc::ty::Ty`.
 198 /// This is the right LLVM type for a field/array element of that type,
 199 /// and is the same as `type_of` for all Sized types.
 200 /// Unsized types, however, are represented by a "minimal unit", e.g.
 201 /// `[T]` becomes `T`, while `str` and `Trait` turn into `i8` - this
 202 /// is useful for indexing slices, as `&[T]`'s data pointer is `T*`.
 203 /// If the type is an unsized struct, the regular layout is generated,
 204 /// with the inner-most trailing unsized field using the "minimal unit"
 205 /// of that field's type - this is useful for taking the address of
 206 /// that field and ensuring the struct has the right alignment.
 207 /// For the LLVM type of a value as a whole, see `type_of`.
 208 /// NB: If you update this, be sure to update `sizing_type_of()` as well.
 209 pub fn in_memory_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>) -> Type {
 210     // Check the cache.
 211     if let Some(&llty) = cx.lltypes().borrow().get(&t) {
 212         return llty;
 213     }
 214
 215     debug!("type_of {:?}", t);
 216
 217     assert!(!t.has_escaping_regions(), "{:?} has escaping regions", t);
 218
 219     // Replace any typedef'd types with their equivalent non-typedef
 220     // type. This ensures that all LLVM nominal types that contain
 221     // Rust types are defined as the same LLVM types.  If we don't do
 222     // this then, e.g. `Option<{myfield: bool}>` would be a different
 223     // type than `Option<myrec>`.
 224     let t_norm = cx.tcx().erase_regions(&t);
 225
 226     if t != t_norm {
 227         let llty = in_memory_type_of(cx, t_norm);
 228         debug!("--> normalized {:?} to {:?} llty={:?}", t, t_norm, llty);
 229         cx.lltypes().borrow_mut().insert(t, llty);
 230         return llty;
 231     }
 232
 233     let mut llty = match t.sty {
 234       ty::TyBool => Type::bool(cx),
 235       ty::TyChar => Type::char(cx),
 236       ty::TyInt(t) => Type::int_from_ty(cx, t),
 237       ty::TyUint(t) => Type::uint_from_ty(cx, t),
 238       ty::TyFloat(t) => Type::float_from_ty(cx, t),
 239       ty::TyEnum(def, ref substs) => {
 240           // Only create the named struct, but don't fill it in. We
 241           // fill it in *after* placing it into the type cache. This
 242           // avoids creating more than one copy of the enum when one
 243           // of the enum's variants refers to the enum itself.
 244           let repr = adt::represent_type(cx, t);
 245           let tps = substs.types.get_slice(subst::TypeSpace);
 246           let name = llvm_type_name(cx, def.did, tps);
 247           adt::incomplete_type_of(cx, &repr, &name[..])
 248       }
 249       ty::TyClosure(..) => {
 250           // Only create the named struct, but don't fill it in. We
 251           // fill it in *after* placing it into the type cache.
 252           let repr = adt::represent_type(cx, t);
 253           // Unboxed closures can have substitutions in all spaces
 254           // inherited from their environment, so we use entire
 255           // contents of the VecPerParamSpace to construct the llvm
 256           // name
 257           adt::incomplete_type_of(cx, &repr, "closure")
 258       }
 259
 260       ty::TyBox(ty) |
 261       ty::TyRef(_, ty::TypeAndMut{ty, ..}) |
 262       ty::TyRawPtr(ty::TypeAndMut{ty, ..}) => {
 263           if !type_is_sized(cx.tcx(), ty) {
 264               if let ty::TyStr = ty.sty {
 265                   // This means we get a nicer name in the output (str is always
 266                   // unsized).
 267                   cx.tn().find_type("str_slice").unwrap()
 268               } else {
 269                   let ptr_ty = in_memory_type_of(cx, ty).ptr_to();
 270                   let info_ty = unsized_info_ty(cx, ty);
 271                   Type::struct_(cx, &[ptr_ty, info_ty], false)
 272               }
 273           } else {
 274               in_memory_type_of(cx, ty).ptr_to()
 275           }
 276       }
 277
 278       ty::TyArray(ty, size) => {
 279           let size = size as u64;
 280           // we must use `sizing_type_of` here as the type may
 281           // not be fully initialized.
 282           let szty = sizing_type_of(cx, ty);
 283           ensure_array_fits_in_address_space(cx, szty, size, t);
 284
 285           let llty = in_memory_type_of(cx, ty);
 286           Type::array(&llty, size)
 287       }
 288
 289       // Unsized slice types (and str) have the type of their element, and
 290       // traits have the type of u8. This is so that the data pointer inside
 291       // fat pointers is of the right type (e.g. for array accesses), even
 292       // when taking the address of an unsized field in a struct.
 293       ty::TySlice(ty) => in_memory_type_of(cx, ty),
 294       ty::TyStr | ty::TyTrait(..) => Type::i8(cx),
 295
 296       ty::TyFnDef(..) => Type::nil(cx),
 297       ty::TyFnPtr(f) => {
 298         let sig = cx.tcx().erase_late_bound_regions(&f.sig);
 299         let sig = infer::normalize_associated_type(cx.tcx(), &sig);
 300         FnType::new(cx, f.abi, &sig, &[]).llvm_type(cx).ptr_to()
 301       }
 302       ty::TyTuple(ref tys) if tys.is_empty() => Type::nil(cx),
 303       ty::TyTuple(..) => {
 304           let repr = adt::represent_type(cx, t);
 305           adt::type_of(cx, &repr)
 306       }
 307       ty::TyStruct(def, ref substs) => {
 308           if t.is_simd() {
 309               let e = t.simd_type(cx.tcx());
 310               if !e.is_machine() {
 311                   cx.sess().fatal(&format!("monomorphising SIMD type `{}` with \
 312                                             a non-machine element type `{}`",
 313                                            t, e))
 314               }
 315               let llet = in_memory_type_of(cx, e);
 316               let n = t.simd_size(cx.tcx()) as u64;
 317               ensure_array_fits_in_address_space(cx, llet, n, t);
 318               Type::vector(&llet, n)
 319           } else {
 320               // Only create the named struct, but don't fill it in. We fill it
 321               // in *after* placing it into the type cache. This prevents
 322               // infinite recursion with recursive struct types.
 323               let repr = adt::represent_type(cx, t);
 324               let tps = substs.types.get_slice(subst::TypeSpace);
 325               let name = llvm_type_name(cx, def.did, tps);
 326               adt::incomplete_type_of(cx, &repr, &name[..])
 327           }
 328       }
 329
 330       ty::TyInfer(..) => bug!("type_of with TyInfer"),
 331       ty::TyProjection(..) => bug!("type_of with TyProjection"),
 332       ty::TyParam(..) => bug!("type_of with ty_param"),
 333       ty::TyError => bug!("type_of with TyError"),
 334     };
 335
 336     debug!("--> mapped t={:?} to llty={:?}", t, llty);
 337
 338     cx.lltypes().borrow_mut().insert(t, llty);
 339
 340     // If this was an enum or struct, fill in the type now.
 341     match t.sty {
 342         ty::TyEnum(..) | ty::TyStruct(..) | ty::TyClosure(..)
 343                 if !t.is_simd() => {
 344             let repr = adt::represent_type(cx, t);
 345             adt::finish_type_of(cx, &repr, &mut llty);
 346         }
 347         _ => ()
 348     }
 349
 350     llty
 351 }
 352
 353 pub fn align_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, t: Ty<'tcx>)
 354                           -> machine::llalign {
 355     let llty = sizing_type_of(cx, t);
 356     machine::llalign_of_min(cx, llty)
 357 }
 358
 359 fn llvm_type_name<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 360                             did: DefId,
 361                             tps: &[Ty<'tcx>])
 362                             -> String {
 363     let base = cx.tcx().item_path_str(did);
 364     let strings: Vec<String> = tps.iter().map(|t| t.to_string()).collect();
 365     let tstr = if strings.is_empty() {
 366         base
 367     } else {
 368         format!("{}<{}>", base, strings.join(", "))
 369     };
 370
 371     if did.krate == 0 {
 372         tstr
 373     } else {
 374         format!("{}.{}", did.krate, tstr)
 375     }
 376 }