src/librustc/ty/layout.rs

   1 // Copyright 2016 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 use session::{self, DataTypeKind};
  12 use ty::{self, Ty, TyCtxt, TypeFoldable, ReprOptions};
  13
  14 use syntax::ast::{self, FloatTy, IntTy, UintTy};
  15 use syntax::attr;
  16 use syntax_pos::DUMMY_SP;
  17
  18 use std::cmp;
  19 use std::fmt;
  20 use std::i128;
  21 use std::mem;
  22 use std::ops::RangeInclusive;
  23
  24 use ich::StableHashingContext;
  25 use rustc_data_structures::stable_hasher::{HashStable, StableHasher,
  26                                            StableHasherResult};
  27
  28 pub use rustc_target::abi::*;
  29
  30 pub trait IntegerExt {
  31     fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, signed: bool) -> Ty<'tcx>;
  32     fn from_attr<C: HasDataLayout>(cx: C, ity: attr::IntType) -> Integer;
  33     fn repr_discr<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  34                   ty: Ty<'tcx>,
  35                   repr: &ReprOptions,
  36                   min: i128,
  37                   max: i128)
  38                   -> (Integer, bool);
  39 }
  40
  41 impl IntegerExt for Integer {
  42     fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, signed: bool) -> Ty<'tcx> {
  43         match (*self, signed) {
  44             (I8, false) => tcx.types.u8,
  45             (I16, false) => tcx.types.u16,
  46             (I32, false) => tcx.types.u32,
  47             (I64, false) => tcx.types.u64,
  48             (I128, false) => tcx.types.u128,
  49             (I8, true) => tcx.types.i8,
  50             (I16, true) => tcx.types.i16,
  51             (I32, true) => tcx.types.i32,
  52             (I64, true) => tcx.types.i64,
  53             (I128, true) => tcx.types.i128,
  54         }
  55     }
  56
  57     /// Get the Integer type from an attr::IntType.
  58     fn from_attr<C: HasDataLayout>(cx: C, ity: attr::IntType) -> Integer {
  59         let dl = cx.data_layout();
  60
  61         match ity {
  62             attr::SignedInt(IntTy::I8) | attr::UnsignedInt(UintTy::U8) => I8,
  63             attr::SignedInt(IntTy::I16) | attr::UnsignedInt(UintTy::U16) => I16,
  64             attr::SignedInt(IntTy::I32) | attr::UnsignedInt(UintTy::U32) => I32,
  65             attr::SignedInt(IntTy::I64) | attr::UnsignedInt(UintTy::U64) => I64,
  66             attr::SignedInt(IntTy::I128) | attr::UnsignedInt(UintTy::U128) => I128,
  67             attr::SignedInt(IntTy::Isize) | attr::UnsignedInt(UintTy::Usize) => {
  68                 dl.ptr_sized_integer()
  69             }
  70         }
  71     }
  72
  73     /// Find the appropriate Integer type and signedness for the given
  74     /// signed discriminant range and #[repr] attribute.
  75     /// N.B.: u128 values above i128::MAX will be treated as signed, but
  76     /// that shouldn't affect anything, other than maybe debuginfo.
  77     fn repr_discr<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  78                   ty: Ty<'tcx>,
  79                   repr: &ReprOptions,
  80                   min: i128,
  81                   max: i128)
  82                   -> (Integer, bool) {
  83         // Theoretically, negative values could be larger in unsigned representation
  84         // than the unsigned representation of the signed minimum. However, if there
  85         // are any negative values, the only valid unsigned representation is u128
  86         // which can fit all i128 values, so the result remains unaffected.
  87         let unsigned_fit = Integer::fit_unsigned(cmp::max(min as u128, max as u128));
  88         let signed_fit = cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));
  89
  90         let mut min_from_extern = None;
  91         let min_default = I8;
  92
  93         if let Some(ity) = repr.int {
  94             let discr = Integer::from_attr(tcx, ity);
  95             let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
  96             if discr < fit {
  97                 bug!("Integer::repr_discr: `#[repr]` hint too small for \
  98                   discriminant range of enum `{}", ty)
  99             }
 100             return (discr, ity.is_signed());
 101         }
 102
 103         if repr.c() {
 104             match &tcx.sess.target.target.arch[..] {
 105                 // WARNING: the ARM EABI has two variants; the one corresponding
 106                 // to `at_least == I32` appears to be used on Linux and NetBSD,
 107                 // but some systems may use the variant corresponding to no
 108                 // lower bound.  However, we don't run on those yet...?
 109                 "arm" => min_from_extern = Some(I32),
 110                 _ => min_from_extern = Some(I32),
 111             }
 112         }
 113
 114         let at_least = min_from_extern.unwrap_or(min_default);
 115
 116         // If there are no negative values, we can use the unsigned fit.
 117         if min >= 0 {
 118             (cmp::max(unsigned_fit, at_least), false)
 119         } else {
 120             (cmp::max(signed_fit, at_least), true)
 121         }
 122     }
 123 }
 124
 125 pub trait PrimitiveExt {
 126     fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx>;
 127 }
 128
 129 impl PrimitiveExt for Primitive {
 130     fn to_ty<'a, 'tcx>(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>) -> Ty<'tcx> {
 131         match *self {
 132             Int(i, signed) => i.to_ty(tcx, signed),
 133             F32 => tcx.types.f32,
 134             F64 => tcx.types.f64,
 135             Pointer => tcx.mk_mut_ptr(tcx.mk_nil()),
 136         }
 137     }
 138 }
 139
 140 /// The first half of a fat pointer.
 141 ///
 142 /// - For a trait object, this is the address of the box.
 143 /// - For a slice, this is the base address.
 144 pub const FAT_PTR_ADDR: usize = 0;
 145
 146 /// The second half of a fat pointer.
 147 ///
 148 /// - For a trait object, this is the address of the vtable.
 149 /// - For a slice, this is the length.
 150 pub const FAT_PTR_EXTRA: usize = 1;
 151
 152 #[derive(Copy, Clone, Debug)]
 153 pub enum LayoutError<'tcx> {
 154     Unknown(Ty<'tcx>),
 155     SizeOverflow(Ty<'tcx>)
 156 }
 157
 158 impl<'tcx> fmt::Display for LayoutError<'tcx> {
 159     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 160         match *self {
 161             LayoutError::Unknown(ty) => {
 162                 write!(f, "the type `{:?}` has an unknown layout", ty)
 163             }
 164             LayoutError::SizeOverflow(ty) => {
 165                 write!(f, "the type `{:?}` is too big for the current architecture", ty)
 166             }
 167         }
 168     }
 169 }
 170
 171 fn layout_raw<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 172                         query: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
 173                         -> Result<&'tcx LayoutDetails, LayoutError<'tcx>>
 174 {
 175     ty::tls::with_related_context(tcx, move |icx| {
 176         let rec_limit = *tcx.sess.recursion_limit.get();
 177         let (param_env, ty) = query.into_parts();
 178
 179         if icx.layout_depth > rec_limit {
 180             tcx.sess.fatal(
 181                 &format!("overflow representing the type `{}`", ty));
 182         }
 183
 184         // Update the ImplicitCtxt to increase the layout_depth
 185         let icx = ty::tls::ImplicitCtxt {
 186             layout_depth: icx.layout_depth + 1,
 187             ..icx.clone()
 188         };
 189
 190         ty::tls::enter_context(&icx, |_| {
 191             let cx = LayoutCx { tcx, param_env };
 192             cx.layout_raw_uncached(ty)
 193         })
 194     })
 195 }
 196
 197 pub fn provide(providers: &mut ty::maps::Providers) {
 198     *providers = ty::maps::Providers {
 199         layout_raw,
 200         ..*providers
 201     };
 202 }
 203
 204 #[derive(Copy, Clone)]
 205 pub struct LayoutCx<'tcx, C> {
 206     pub tcx: C,
 207     pub param_env: ty::ParamEnv<'tcx>
 208 }
 209
 210 impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
 211     fn layout_raw_uncached(self, ty: Ty<'tcx>)
 212                            -> Result<&'tcx LayoutDetails, LayoutError<'tcx>> {
 213         let tcx = self.tcx;
 214         let param_env = self.param_env;
 215         let dl = self.data_layout();
 216         let scalar_unit = |value: Primitive| {
 217             let bits = value.size(dl).bits();
 218             assert!(bits <= 128);
 219             Scalar {
 220                 value,
 221                 valid_range: 0..=(!0 >> (128 - bits))
 222             }
 223         };
 224         let scalar = |value: Primitive| {
 225             tcx.intern_layout(LayoutDetails::scalar(self, scalar_unit(value)))
 226         };
 227         let scalar_pair = |a: Scalar, b: Scalar| {
 228             let align = a.value.align(dl).max(b.value.align(dl)).max(dl.aggregate_align);
 229             let b_offset = a.value.size(dl).abi_align(b.value.align(dl));
 230             let size = (b_offset + b.value.size(dl)).abi_align(align);
 231             LayoutDetails {
 232                 variants: Variants::Single { index: 0 },
 233                 fields: FieldPlacement::Arbitrary {
 234                     offsets: vec![Size::from_bytes(0), b_offset],
 235                     memory_index: vec![0, 1]
 236                 },
 237                 abi: Abi::ScalarPair(a, b),
 238                 align,
 239                 size
 240             }
 241         };
 242
 243         #[derive(Copy, Clone, Debug)]
 244         enum StructKind {
 245             /// A tuple, closure, or univariant which cannot be coerced to unsized.
 246             AlwaysSized,
 247             /// A univariant, the last field of which may be coerced to unsized.
 248             MaybeUnsized,
 249             /// A univariant, but with a prefix of an arbitrary size & alignment (e.g. enum tag).
 250             Prefixed(Size, Align),
 251         }
 252         let univariant_uninterned = |fields: &[TyLayout], repr: &ReprOptions, kind| {
 253             let packed = repr.packed();
 254             if packed && repr.align > 0 {
 255                 bug!("struct cannot be packed and aligned");
 256             }
 257
 258             let pack = {
 259                 let pack = repr.pack as u64;
 260                 Align::from_bytes(pack, pack).unwrap()
 261             };
 262
 263             let mut align = if packed {
 264                 dl.i8_align
 265             } else {
 266                 dl.aggregate_align
 267             };
 268
 269             let mut sized = true;
 270             let mut offsets = vec![Size::from_bytes(0); fields.len()];
 271             let mut inverse_memory_index: Vec<u32> = (0..fields.len() as u32).collect();
 272
 273             let mut optimize = !repr.inhibit_struct_field_reordering_opt();
 274             if let StructKind::Prefixed(_, align) = kind {
 275                 optimize &= align.abi() == 1;
 276             }
 277
 278             if optimize {
 279                 let end = if let StructKind::MaybeUnsized = kind {
 280                     fields.len() - 1
 281                 } else {
 282                     fields.len()
 283                 };
 284                 let optimizing = &mut inverse_memory_index[..end];
 285                 let field_align = |f: &TyLayout| {
 286                     if packed { f.align.min(pack).abi() } else { f.align.abi() }
 287                 };
 288                 match kind {
 289                     StructKind::AlwaysSized |
 290                     StructKind::MaybeUnsized => {
 291                         optimizing.sort_by_key(|&x| {
 292                             // Place ZSTs first to avoid "interesting offsets",
 293                             // especially with only one or two non-ZST fields.
 294                             let f = &fields[x as usize];
 295                             (!f.is_zst(), cmp::Reverse(field_align(f)))
 296                         });
 297                     }
 298                     StructKind::Prefixed(..) => {
 299                         optimizing.sort_by_key(|&x| field_align(&fields[x as usize]));
 300                     }
 301                 }
 302             }
 303
 304             // inverse_memory_index holds field indices by increasing memory offset.
 305             // That is, if field 5 has offset 0, the first element of inverse_memory_index is 5.
 306             // We now write field offsets to the corresponding offset slot;
 307             // field 5 with offset 0 puts 0 in offsets[5].
 308             // At the bottom of this function, we use inverse_memory_index to produce memory_index.
 309
 310             let mut offset = Size::from_bytes(0);
 311
 312             if let StructKind::Prefixed(prefix_size, prefix_align) = kind {
 313                 if packed {
 314                     let prefix_align = prefix_align.min(pack);
 315                     align = align.max(prefix_align);
 316                 } else {
 317                     align = align.max(prefix_align);
 318                 }
 319                 offset = prefix_size.abi_align(prefix_align);
 320             }
 321
 322             for &i in &inverse_memory_index {
 323                 let field = fields[i as usize];
 324                 if !sized {
 325                     bug!("univariant: field #{} of `{}` comes after unsized field",
 326                         offsets.len(), ty);
 327                 }
 328
 329                 if field.abi == Abi::Uninhabited {
 330                     return Ok(LayoutDetails::uninhabited(fields.len()));
 331                 }
 332
 333                 if field.is_unsized() {
 334                     sized = false;
 335                 }
 336
 337                 // Invariant: offset < dl.obj_size_bound() <= 1<<61
 338                 if packed {
 339                     let field_pack = field.align.min(pack);
 340                     offset = offset.abi_align(field_pack);
 341                     align = align.max(field_pack);
 342                 }
 343                 else {
 344                     offset = offset.abi_align(field.align);
 345                     align = align.max(field.align);
 346                 }
 347
 348                 debug!("univariant offset: {:?} field: {:#?}", offset, field);
 349                 offsets[i as usize] = offset;
 350
 351                 offset = offset.checked_add(field.size, dl)
 352                     .ok_or(LayoutError::SizeOverflow(ty))?;
 353             }
 354
 355             if repr.align > 0 {
 356                 let repr_align = repr.align as u64;
 357                 align = align.max(Align::from_bytes(repr_align, repr_align).unwrap());
 358                 debug!("univariant repr_align: {:?}", repr_align);
 359             }
 360
 361             debug!("univariant min_size: {:?}", offset);
 362             let min_size = offset;
 363
 364             // As stated above, inverse_memory_index holds field indices by increasing offset.
 365             // This makes it an already-sorted view of the offsets vec.
 366             // To invert it, consider:
 367             // If field 5 has offset 0, offsets[0] is 5, and memory_index[5] should be 0.
 368             // Field 5 would be the first element, so memory_index is i:
 369             // Note: if we didn't optimize, it's already right.
 370
 371             let mut memory_index;
 372             if optimize {
 373                 memory_index = vec![0; inverse_memory_index.len()];
 374
 375                 for i in 0..inverse_memory_index.len() {
 376                     memory_index[inverse_memory_index[i] as usize]  = i as u32;
 377                 }
 378             } else {
 379                 memory_index = inverse_memory_index;
 380             }
 381
 382             let size = min_size.abi_align(align);
 383             let mut abi = Abi::Aggregate { sized };
 384
 385             // Unpack newtype ABIs and find scalar pairs.
 386             if sized && size.bytes() > 0 {
 387                 // All other fields must be ZSTs, and we need them to all start at 0.
 388                 let mut zst_offsets =
 389                     offsets.iter().enumerate().filter(|&(i, _)| fields[i].is_zst());
 390                 if zst_offsets.all(|(_, o)| o.bytes() == 0) {
 391                     let mut non_zst_fields =
 392                         fields.iter().enumerate().filter(|&(_, f)| !f.is_zst());
 393
 394                     match (non_zst_fields.next(), non_zst_fields.next(), non_zst_fields.next()) {
 395                         // We have exactly one non-ZST field.
 396                         (Some((i, field)), None, None) => {
 397                             // Field fills the struct and it has a scalar or scalar pair ABI.
 398                             if offsets[i].bytes() == 0 &&
 399                                align.abi() == field.align.abi() &&
 400                                size == field.size {
 401                                 match field.abi {
 402                                     // For plain scalars, or vectors of them, we can't unpack
 403                                     // newtypes for `#[repr(C)]`, as that affects C ABIs.
 404                                     Abi::Scalar(_) | Abi::Vector { .. } if optimize => {
 405                                         abi = field.abi.clone();
 406                                     }
 407                                     // But scalar pairs are Rust-specific and get
 408                                     // treated as aggregates by C ABIs anyway.
 409                                     Abi::ScalarPair(..) => {
 410                                         abi = field.abi.clone();
 411                                     }
 412                                     _ => {}
 413                                 }
 414                             }
 415                         }
 416
 417                         // Two non-ZST fields, and they're both scalars.
 418                         (Some((i, &TyLayout {
 419                             details: &LayoutDetails { abi: Abi::Scalar(ref a), .. }, ..
 420                         })), Some((j, &TyLayout {
 421                             details: &LayoutDetails { abi: Abi::Scalar(ref b), .. }, ..
 422                         })), None) => {
 423                             // Order by the memory placement, not source order.
 424                             let ((i, a), (j, b)) = if offsets[i] < offsets[j] {
 425                                 ((i, a), (j, b))
 426                             } else {
 427                                 ((j, b), (i, a))
 428                             };
 429                             let pair = scalar_pair(a.clone(), b.clone());
 430                             let pair_offsets = match pair.fields {
 431                                 FieldPlacement::Arbitrary {
 432                                     ref offsets,
 433                                     ref memory_index
 434                                 } => {
 435                                     assert_eq!(memory_index, &[0, 1]);
 436                                     offsets
 437                                 }
 438                                 _ => bug!()
 439                             };
 440                             if offsets[i] == pair_offsets[0] &&
 441                                offsets[j] == pair_offsets[1] &&
 442                                align == pair.align &&
 443                                size == pair.size {
 444                                 // We can use `ScalarPair` only when it matches our
 445                                 // already computed layout (including `#[repr(C)]`).
 446                                 abi = pair.abi;
 447                             }
 448                         }
 449
 450                         _ => {}
 451                     }
 452                 }
 453             }
 454
 455             Ok(LayoutDetails {
 456                 variants: Variants::Single { index: 0 },
 457                 fields: FieldPlacement::Arbitrary {
 458                     offsets,
 459                     memory_index
 460                 },
 461                 abi,
 462                 align,
 463                 size
 464             })
 465         };
 466         let univariant = |fields: &[TyLayout], repr: &ReprOptions, kind| {
 467             Ok(tcx.intern_layout(univariant_uninterned(fields, repr, kind)?))
 468         };
 469         assert!(!ty.has_infer_types());
 470
 471         Ok(match ty.sty {
 472             // Basic scalars.
 473             ty::TyBool => {
 474                 tcx.intern_layout(LayoutDetails::scalar(self, Scalar {
 475                     value: Int(I8, false),
 476                     valid_range: 0..=1
 477                 }))
 478             }
 479             ty::TyChar => {
 480                 tcx.intern_layout(LayoutDetails::scalar(self, Scalar {
 481                     value: Int(I32, false),
 482                     valid_range: 0..=0x10FFFF
 483                 }))
 484             }
 485             ty::TyInt(ity) => {
 486                 scalar(Int(Integer::from_attr(dl, attr::SignedInt(ity)), true))
 487             }
 488             ty::TyUint(ity) => {
 489                 scalar(Int(Integer::from_attr(dl, attr::UnsignedInt(ity)), false))
 490             }
 491             ty::TyFloat(FloatTy::F32) => scalar(F32),
 492             ty::TyFloat(FloatTy::F64) => scalar(F64),
 493             ty::TyFnPtr(_) => {
 494                 let mut ptr = scalar_unit(Pointer);
 495                 ptr.valid_range.start = 1;
 496                 tcx.intern_layout(LayoutDetails::scalar(self, ptr))
 497             }
 498
 499             // The never type.
 500             ty::TyNever => {
 501                 tcx.intern_layout(LayoutDetails::uninhabited(0))
 502             }
 503
 504             // Potentially-fat pointers.
 505             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
 506             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
 507                 let mut data_ptr = scalar_unit(Pointer);
 508                 if !ty.is_unsafe_ptr() {
 509                     data_ptr.valid_range.start = 1;
 510                 }
 511
 512                 let pointee = tcx.normalize_erasing_regions(param_env, pointee);
 513                 if pointee.is_sized(tcx.at(DUMMY_SP), param_env) {
 514                     return Ok(tcx.intern_layout(LayoutDetails::scalar(self, data_ptr)));
 515                 }
 516
 517                 let unsized_part = tcx.struct_tail(pointee);
 518                 let metadata = match unsized_part.sty {
 519                     ty::TyForeign(..) => {
 520                         return Ok(tcx.intern_layout(LayoutDetails::scalar(self, data_ptr)));
 521                     }
 522                     ty::TySlice(_) | ty::TyStr => {
 523                         scalar_unit(Int(dl.ptr_sized_integer(), false))
 524                     }
 525                     ty::TyDynamic(..) => {
 526                         let mut vtable = scalar_unit(Pointer);
 527                         vtable.valid_range.start = 1;
 528                         vtable
 529                     }
 530                     _ => return Err(LayoutError::Unknown(unsized_part))
 531                 };
 532
 533                 // Effectively a (ptr, meta) tuple.
 534                 tcx.intern_layout(scalar_pair(data_ptr, metadata))
 535             }
 536
 537             // Arrays and slices.
 538             ty::TyArray(element, mut count) => {
 539                 if count.has_projections() {
 540                     count = tcx.normalize_erasing_regions(param_env, count);
 541                     if count.has_projections() {
 542                         return Err(LayoutError::Unknown(ty));
 543                     }
 544                 }
 545
 546                 let element = self.layout_of(element)?;
 547                 let count = count.val.unwrap_u64();
 548                 let size = element.size.checked_mul(count, dl)
 549                     .ok_or(LayoutError::SizeOverflow(ty))?;
 550
 551                 tcx.intern_layout(LayoutDetails {
 552                     variants: Variants::Single { index: 0 },
 553                     fields: FieldPlacement::Array {
 554                         stride: element.size,
 555                         count
 556                     },
 557                     abi: Abi::Aggregate { sized: true },
 558                     align: element.align,
 559                     size
 560                 })
 561             }
 562             ty::TySlice(element) => {
 563                 let element = self.layout_of(element)?;
 564                 tcx.intern_layout(LayoutDetails {
 565                     variants: Variants::Single { index: 0 },
 566                     fields: FieldPlacement::Array {
 567                         stride: element.size,
 568                         count: 0
 569                     },
 570                     abi: Abi::Aggregate { sized: false },
 571                     align: element.align,
 572                     size: Size::from_bytes(0)
 573                 })
 574             }
 575             ty::TyStr => {
 576                 tcx.intern_layout(LayoutDetails {
 577                     variants: Variants::Single { index: 0 },
 578                     fields: FieldPlacement::Array {
 579                         stride: Size::from_bytes(1),
 580                         count: 0
 581                     },
 582                     abi: Abi::Aggregate { sized: false },
 583                     align: dl.i8_align,
 584                     size: Size::from_bytes(0)
 585                 })
 586             }
 587
 588             // Odd unit types.
 589             ty::TyFnDef(..) => {
 590                 univariant(&[], &ReprOptions::default(), StructKind::AlwaysSized)?
 591             }
 592             ty::TyDynamic(..) | ty::TyForeign(..) => {
 593                 let mut unit = univariant_uninterned(&[], &ReprOptions::default(),
 594                   StructKind::AlwaysSized)?;
 595                 match unit.abi {
 596                     Abi::Aggregate { ref mut sized } => *sized = false,
 597                     _ => bug!()
 598                 }
 599                 tcx.intern_layout(unit)
 600             }
 601
 602             // Tuples, generators and closures.
 603             ty::TyGenerator(def_id, ref substs, _) => {
 604                 let tys = substs.field_tys(def_id, tcx);
 605                 univariant(&tys.map(|ty| self.layout_of(ty)).collect::<Result<Vec<_>, _>>()?,
 606                     &ReprOptions::default(),
 607                     StructKind::AlwaysSized)?
 608             }
 609
 610             ty::TyClosure(def_id, ref substs) => {
 611                 let tys = substs.upvar_tys(def_id, tcx);
 612                 univariant(&tys.map(|ty| self.layout_of(ty)).collect::<Result<Vec<_>, _>>()?,
 613                     &ReprOptions::default(),
 614                     StructKind::AlwaysSized)?
 615             }
 616
 617             ty::TyTuple(tys) => {
 618                 let kind = if tys.len() == 0 {
 619                     StructKind::AlwaysSized
 620                 } else {
 621                     StructKind::MaybeUnsized
 622                 };
 623
 624                 univariant(&tys.iter().map(|ty| self.layout_of(ty)).collect::<Result<Vec<_>, _>>()?,
 625                     &ReprOptions::default(), kind)?
 626             }
 627
 628             // SIMD vector types.
 629             ty::TyAdt(def, ..) if def.repr.simd() => {
 630                 let element = self.layout_of(ty.simd_type(tcx))?;
 631                 let count = ty.simd_size(tcx) as u64;
 632                 assert!(count > 0);
 633                 let scalar = match element.abi {
 634                     Abi::Scalar(ref scalar) => scalar.clone(),
 635                     _ => {
 636                         tcx.sess.fatal(&format!("monomorphising SIMD type `{}` with \
 637                                                 a non-machine element type `{}`",
 638                                                 ty, element.ty));
 639                     }
 640                 };
 641                 let size = element.size.checked_mul(count, dl)
 642                     .ok_or(LayoutError::SizeOverflow(ty))?;
 643                 let align = dl.vector_align(size);
 644                 let size = size.abi_align(align);
 645
 646                 tcx.intern_layout(LayoutDetails {
 647                     variants: Variants::Single { index: 0 },
 648                     fields: FieldPlacement::Array {
 649                         stride: element.size,
 650                         count
 651                     },
 652                     abi: Abi::Vector {
 653                         element: scalar,
 654                         count
 655                     },
 656                     size,
 657                     align,
 658                 })
 659             }
 660
 661             // ADTs.
 662             ty::TyAdt(def, substs) => {
 663                 // Cache the field layouts.
 664                 let variants = def.variants.iter().map(|v| {
 665                     v.fields.iter().map(|field| {
 666                         self.layout_of(field.ty(tcx, substs))
 667                     }).collect::<Result<Vec<_>, _>>()
 668                 }).collect::<Result<Vec<_>, _>>()?;
 669
 670                 if def.is_union() {
 671                     let packed = def.repr.packed();
 672                     if packed && def.repr.align > 0 {
 673                         bug!("Union cannot be packed and aligned");
 674                     }
 675
 676                     let pack = {
 677                         let pack = def.repr.pack as u64;
 678                         Align::from_bytes(pack, pack).unwrap()
 679                     };
 680
 681                     let mut align = if packed {
 682                         dl.i8_align
 683                     } else {
 684                         dl.aggregate_align
 685                     };
 686
 687                     if def.repr.align > 0 {
 688                         let repr_align = def.repr.align as u64;
 689                         align = align.max(
 690                             Align::from_bytes(repr_align, repr_align).unwrap());
 691                     }
 692
 693                     let mut size = Size::from_bytes(0);
 694                     for field in &variants[0] {
 695                         assert!(!field.is_unsized());
 696
 697                         if packed {
 698                             let field_pack = field.align.min(pack);
 699                             align = align.max(field_pack);
 700                         } else {
 701                             align = align.max(field.align);
 702                         }
 703                         size = cmp::max(size, field.size);
 704                     }
 705
 706                     return Ok(tcx.intern_layout(LayoutDetails {
 707                         variants: Variants::Single { index: 0 },
 708                         fields: FieldPlacement::Union(variants[0].len()),
 709                         abi: Abi::Aggregate { sized: true },
 710                         align,
 711                         size: size.abi_align(align)
 712                     }));
 713                 }
 714
 715                 let (inh_first, inh_second) = {
 716                     let mut inh_variants = (0..variants.len()).filter(|&v| {
 717                         variants[v].iter().all(|f| f.abi != Abi::Uninhabited)
 718                     });
 719                     (inh_variants.next(), inh_variants.next())
 720                 };
 721                 if inh_first.is_none() {
 722                     // Uninhabited because it has no variants, or only uninhabited ones.
 723                     return Ok(tcx.intern_layout(LayoutDetails::uninhabited(0)));
 724                 }
 725
 726                 let is_struct = !def.is_enum() ||
 727                     // Only one variant is inhabited.
 728                     (inh_second.is_none() &&
 729                     // Representation optimizations are allowed.
 730                      !def.repr.inhibit_enum_layout_opt() &&
 731                     // Inhabited variant either has data ...
 732                      (!variants[inh_first.unwrap()].is_empty() ||
 733                     // ... or there other, uninhabited, variants.
 734                       variants.len() > 1));
 735                 if is_struct {
 736                     // Struct, or univariant enum equivalent to a struct.
 737                     // (Typechecking will reject discriminant-sizing attrs.)
 738
 739                     let v = inh_first.unwrap();
 740                     let kind = if def.is_enum() || variants[v].len() == 0 {
 741                         StructKind::AlwaysSized
 742                     } else {
 743                         let param_env = tcx.param_env(def.did);
 744                         let last_field = def.variants[v].fields.last().unwrap();
 745                         let always_sized = tcx.type_of(last_field.did)
 746                           .is_sized(tcx.at(DUMMY_SP), param_env);
 747                         if !always_sized { StructKind::MaybeUnsized }
 748                         else { StructKind::AlwaysSized }
 749                     };
 750
 751                     let mut st = univariant_uninterned(&variants[v], &def.repr, kind)?;
 752                     st.variants = Variants::Single { index: v };
 753                     // Exclude 0 from the range of a newtype ABI NonZero<T>.
 754                     if Some(def.did) == self.tcx.lang_items().non_zero() {
 755                         match st.abi {
 756                             Abi::Scalar(ref mut scalar) |
 757                             Abi::ScalarPair(ref mut scalar, _) => {
 758                                 if scalar.valid_range.start == 0 {
 759                                     scalar.valid_range.start = 1;
 760                                 }
 761                             }
 762                             _ => {}
 763                         }
 764                     }
 765                     return Ok(tcx.intern_layout(st));
 766                 }
 767
 768                 let no_explicit_discriminants = def.variants.iter().enumerate()
 769                     .all(|(i, v)| v.discr == ty::VariantDiscr::Relative(i));
 770
 771                 // Niche-filling enum optimization.
 772                 if !def.repr.inhibit_enum_layout_opt() && no_explicit_discriminants {
 773                     let mut dataful_variant = None;
 774                     let mut niche_variants = usize::max_value()..=0;
 775
 776                     // Find one non-ZST variant.
 777                     'variants: for (v, fields) in variants.iter().enumerate() {
 778                         if fields.iter().any(|f| f.abi == Abi::Uninhabited) {
 779                             continue 'variants;
 780                         }
 781                         for f in fields {
 782                             if !f.is_zst() {
 783                                 if dataful_variant.is_none() {
 784                                     dataful_variant = Some(v);
 785                                     continue 'variants;
 786                                 } else {
 787                                     dataful_variant = None;
 788                                     break 'variants;
 789                                 }
 790                             }
 791                         }
 792                         if niche_variants.start > v {
 793                             niche_variants.start = v;
 794                         }
 795                         niche_variants.end = v;
 796                     }
 797
 798                     if niche_variants.start > niche_variants.end {
 799                         dataful_variant = None;
 800                     }
 801
 802                     if let Some(i) = dataful_variant {
 803                         let count = (niche_variants.end - niche_variants.start + 1) as u128;
 804                         for (field_index, &field) in variants[i].iter().enumerate() {
 805                             let (offset, niche, niche_start) =
 806                                 match self.find_niche(field, count)? {
 807                                     Some(niche) => niche,
 808                                     None => continue
 809                                 };
 810                             let mut align = dl.aggregate_align;
 811                             let st = variants.iter().enumerate().map(|(j, v)| {
 812                                 let mut st = univariant_uninterned(v,
 813                                     &def.repr, StructKind::AlwaysSized)?;
 814                                 st.variants = Variants::Single { index: j };
 815
 816                                 align = align.max(st.align);
 817
 818                                 Ok(st)
 819                             }).collect::<Result<Vec<_>, _>>()?;
 820
 821                             let offset = st[i].fields.offset(field_index) + offset;
 822                             let size = st[i].size;
 823
 824                             let abi = match st[i].abi {
 825                                 Abi::Scalar(_) => Abi::Scalar(niche.clone()),
 826                                 Abi::ScalarPair(ref first, ref second) => {
 827                                     // We need to use scalar_unit to reset the
 828                                     // valid range to the maximal one for that
 829                                     // primitive, because only the niche is
 830                                     // guaranteed to be initialised, not the
 831                                     // other primitive.
 832                                     if offset.bytes() == 0 {
 833                                         Abi::ScalarPair(niche.clone(), scalar_unit(second.value))
 834                                     } else {
 835                                         Abi::ScalarPair(scalar_unit(first.value), niche.clone())
 836                                     }
 837                                 }
 838                                 _ => Abi::Aggregate { sized: true },
 839                             };
 840
 841                             return Ok(tcx.intern_layout(LayoutDetails {
 842                                 variants: Variants::NicheFilling {
 843                                     dataful_variant: i,
 844                                     niche_variants,
 845                                     niche,
 846                                     niche_start,
 847                                     variants: st,
 848                                 },
 849                                 fields: FieldPlacement::Arbitrary {
 850                                     offsets: vec![offset],
 851                                     memory_index: vec![0]
 852                                 },
 853                                 abi,
 854                                 size,
 855                                 align,
 856                             }));
 857                         }
 858                     }
 859                 }
 860
 861                 let (mut min, mut max) = (i128::max_value(), i128::min_value());
 862                 let discr_type = def.repr.discr_type();
 863                 let bits = Integer::from_attr(tcx, discr_type).size().bits();
 864                 for (i, discr) in def.discriminants(tcx).enumerate() {
 865                     if variants[i].iter().any(|f| f.abi == Abi::Uninhabited) {
 866                         continue;
 867                     }
 868                     let mut x = discr.val as i128;
 869                     if discr_type.is_signed() {
 870                         // sign extend the raw representation to be an i128
 871                         x = (x << (128 - bits)) >> (128 - bits);
 872                     }
 873                     if x < min { min = x; }
 874                     if x > max { max = x; }
 875                 }
 876                 assert!(min <= max, "discriminant range is {}...{}", min, max);
 877                 let (min_ity, signed) = Integer::repr_discr(tcx, ty, &def.repr, min, max);
 878
 879                 let mut align = dl.aggregate_align;
 880                 let mut size = Size::from_bytes(0);
 881
 882                 // We're interested in the smallest alignment, so start large.
 883                 let mut start_align = Align::from_bytes(256, 256).unwrap();
 884                 assert_eq!(Integer::for_abi_align(dl, start_align), None);
 885
 886                 // repr(C) on an enum tells us to make a (tag, union) layout,
 887                 // so we need to grow the prefix alignment to be at least
 888                 // the alignment of the union. (This value is used both for
 889                 // determining the alignment of the overall enum, and the
 890                 // determining the alignment of the payload after the tag.)
 891                 let mut prefix_align = min_ity.align(dl);
 892                 if def.repr.c() {
 893                     for fields in &variants {
 894                         for field in fields {
 895                             prefix_align = prefix_align.max(field.align);
 896                         }
 897                     }
 898                 }
 899
 900                 // Create the set of structs that represent each variant.
 901                 let mut variants = variants.into_iter().enumerate().map(|(i, field_layouts)| {
 902                     let mut st = univariant_uninterned(&field_layouts,
 903                         &def.repr, StructKind::Prefixed(min_ity.size(), prefix_align))?;
 904                     st.variants = Variants::Single { index: i };
 905                     // Find the first field we can't move later
 906                     // to make room for a larger discriminant.
 907                     for field in st.fields.index_by_increasing_offset().map(|j| field_layouts[j]) {
 908                         if !field.is_zst() || field.align.abi() != 1 {
 909                             start_align = start_align.min(field.align);
 910                             break;
 911                         }
 912                     }
 913                     size = cmp::max(size, st.size);
 914                     align = align.max(st.align);
 915                     Ok(st)
 916                 }).collect::<Result<Vec<_>, _>>()?;
 917
 918                 // Align the maximum variant size to the largest alignment.
 919                 size = size.abi_align(align);
 920
 921                 if size.bytes() >= dl.obj_size_bound() {
 922                     return Err(LayoutError::SizeOverflow(ty));
 923                 }
 924
 925                 let typeck_ity = Integer::from_attr(dl, def.repr.discr_type());
 926                 if typeck_ity < min_ity {
 927                     // It is a bug if Layout decided on a greater discriminant size than typeck for
 928                     // some reason at this point (based on values discriminant can take on). Mostly
 929                     // because this discriminant will be loaded, and then stored into variable of
 930                     // type calculated by typeck. Consider such case (a bug): typeck decided on
 931                     // byte-sized discriminant, but layout thinks we need a 16-bit to store all
 932                     // discriminant values. That would be a bug, because then, in trans, in order
 933                     // to store this 16-bit discriminant into 8-bit sized temporary some of the
 934                     // space necessary to represent would have to be discarded (or layout is wrong
 935                     // on thinking it needs 16 bits)
 936                     bug!("layout decided on a larger discriminant type ({:?}) than typeck ({:?})",
 937                          min_ity, typeck_ity);
 938                     // However, it is fine to make discr type however large (as an optimisation)
 939                     // after this point – we’ll just truncate the value we load in trans.
 940                 }
 941
 942                 // Check to see if we should use a different type for the
 943                 // discriminant. We can safely use a type with the same size
 944                 // as the alignment of the first field of each variant.
 945                 // We increase the size of the discriminant to avoid LLVM copying
 946                 // padding when it doesn't need to. This normally causes unaligned
 947                 // load/stores and excessive memcpy/memset operations. By using a
 948                 // bigger integer size, LLVM can be sure about it's contents and
 949                 // won't be so conservative.
 950
 951                 // Use the initial field alignment
 952                 let mut ity = Integer::for_abi_align(dl, start_align).unwrap_or(min_ity);
 953
 954                 // If the alignment is not larger than the chosen discriminant size,
 955                 // don't use the alignment as the final size.
 956                 if ity <= min_ity {
 957                     ity = min_ity;
 958                 } else {
 959                     // Patch up the variants' first few fields.
 960                     let old_ity_size = min_ity.size();
 961                     let new_ity_size = ity.size();
 962                     for variant in &mut variants {
 963                         if variant.abi == Abi::Uninhabited {
 964                             continue;
 965                         }
 966                         match variant.fields {
 967                             FieldPlacement::Arbitrary { ref mut offsets, .. } => {
 968                                 for i in offsets {
 969                                     if *i <= old_ity_size {
 970                                         assert_eq!(*i, old_ity_size);
 971                                         *i = new_ity_size;
 972                                     }
 973                                 }
 974                                 // We might be making the struct larger.
 975                                 if variant.size <= old_ity_size {
 976                                     variant.size = new_ity_size;
 977                                 }
 978                             }
 979                             _ => bug!()
 980                         }
 981                     }
 982                 }
 983
 984                 let tag_mask = !0u128 >> (128 - ity.size().bits());
 985                 let tag = Scalar {
 986                     value: Int(ity, signed),
 987                     valid_range: (min as u128 & tag_mask)..=(max as u128 & tag_mask),
 988                 };
 989                 let abi = if tag.value.size(dl) == size {
 990                     Abi::Scalar(tag.clone())
 991                 } else {
 992                     Abi::Aggregate { sized: true }
 993                 };
 994                 tcx.intern_layout(LayoutDetails {
 995                     variants: Variants::Tagged {
 996                         discr: tag,
 997                         variants
 998                     },
 999                     fields: FieldPlacement::Arbitrary {
1000                         offsets: vec![Size::from_bytes(0)],
1001                         memory_index: vec![0]
1002                     },
1003                     abi,
1004                     align,
1005                     size
1006                 })
1007             }
1008
1009             // Types with no meaningful known layout.
1010             ty::TyProjection(_) | ty::TyAnon(..) => {
1011                 let normalized = tcx.normalize_erasing_regions(param_env, ty);
1012                 if ty == normalized {
1013                     return Err(LayoutError::Unknown(ty));
1014                 }
1015                 tcx.layout_raw(param_env.and(normalized))?
1016             }
1017             ty::TyParam(_) => {
1018                 return Err(LayoutError::Unknown(ty));
1019             }
1020             ty::TyGeneratorWitness(..) | ty::TyInfer(_) | ty::TyError => {
1021                 bug!("LayoutDetails::compute: unexpected type `{}`", ty)
1022             }
1023         })
1024     }
1025
1026     /// This is invoked by the `layout_raw` query to record the final
1027     /// layout of each type.
1028     #[inline]
1029     fn record_layout_for_printing(self, layout: TyLayout<'tcx>) {
1030         // If we are running with `-Zprint-type-sizes`, record layouts for
1031         // dumping later. Ignore layouts that are done with non-empty
1032         // environments or non-monomorphic layouts, as the user only wants
1033         // to see the stuff resulting from the final trans session.
1034         if
1035             !self.tcx.sess.opts.debugging_opts.print_type_sizes ||
1036             layout.ty.has_param_types() ||
1037             layout.ty.has_self_ty() ||
1038             !self.param_env.caller_bounds.is_empty()
1039         {
1040             return;
1041         }
1042
1043         self.record_layout_for_printing_outlined(layout)
1044     }
1045
1046     fn record_layout_for_printing_outlined(self, layout: TyLayout<'tcx>) {
1047         // (delay format until we actually need it)
1048         let record = |kind, packed, opt_discr_size, variants| {
1049             let type_desc = format!("{:?}", layout.ty);
1050             self.tcx.sess.code_stats.borrow_mut().record_type_size(kind,
1051                                                                    type_desc,
1052                                                                    layout.align,
1053                                                                    layout.size,
1054                                                                    packed,
1055                                                                    opt_discr_size,
1056                                                                    variants);
1057         };
1058
1059         let adt_def = match layout.ty.sty {
1060             ty::TyAdt(ref adt_def, _) => {
1061                 debug!("print-type-size t: `{:?}` process adt", layout.ty);
1062                 adt_def
1063             }
1064
1065             ty::TyClosure(..) => {
1066                 debug!("print-type-size t: `{:?}` record closure", layout.ty);
1067                 record(DataTypeKind::Closure, false, None, vec![]);
1068                 return;
1069             }
1070
1071             _ => {
1072                 debug!("print-type-size t: `{:?}` skip non-nominal", layout.ty);
1073                 return;
1074             }
1075         };
1076
1077         let adt_kind = adt_def.adt_kind();
1078         let adt_packed = adt_def.repr.packed();
1079
1080         let build_variant_info = |n: Option<ast::Name>,
1081                                   flds: &[ast::Name],
1082                                   layout: TyLayout<'tcx>| {
1083             let mut min_size = Size::from_bytes(0);
1084             let field_info: Vec<_> = flds.iter().enumerate().map(|(i, &name)| {
1085                 match layout.field(self, i) {
1086                     Err(err) => {
1087                         bug!("no layout found for field {}: `{:?}`", name, err);
1088                     }
1089                     Ok(field_layout) => {
1090                         let offset = layout.fields.offset(i);
1091                         let field_end = offset + field_layout.size;
1092                         if min_size < field_end {
1093                             min_size = field_end;
1094                         }
1095                         session::FieldInfo {
1096                             name: name.to_string(),
1097                             offset: offset.bytes(),
1098                             size: field_layout.size.bytes(),
1099                             align: field_layout.align.abi(),
1100                         }
1101                     }
1102                 }
1103             }).collect();
1104
1105             session::VariantInfo {
1106                 name: n.map(|n|n.to_string()),
1107                 kind: if layout.is_unsized() {
1108                     session::SizeKind::Min
1109                 } else {
1110                     session::SizeKind::Exact
1111                 },
1112                 align: layout.align.abi(),
1113                 size: if min_size.bytes() == 0 {
1114                     layout.size.bytes()
1115                 } else {
1116                     min_size.bytes()
1117                 },
1118                 fields: field_info,
1119             }
1120         };
1121
1122         match layout.variants {
1123             Variants::Single { index } => {
1124                 debug!("print-type-size `{:#?}` variant {}",
1125                        layout, adt_def.variants[index].name);
1126                 if !adt_def.variants.is_empty() {
1127                     let variant_def = &adt_def.variants[index];
1128                     let fields: Vec<_> =
1129                         variant_def.fields.iter().map(|f| f.name).collect();
1130                     record(adt_kind.into(),
1131                            adt_packed,
1132                            None,
1133                            vec![build_variant_info(Some(variant_def.name),
1134                                                    &fields,
1135                                                    layout)]);
1136                 } else {
1137                     // (This case arises for *empty* enums; so give it
1138                     // zero variants.)
1139                     record(adt_kind.into(), adt_packed, None, vec![]);
1140                 }
1141             }
1142
1143             Variants::NicheFilling { .. } |
1144             Variants::Tagged { .. } => {
1145                 debug!("print-type-size `{:#?}` adt general variants def {}",
1146                        layout.ty, adt_def.variants.len());
1147                 let variant_infos: Vec<_> =
1148                     adt_def.variants.iter().enumerate().map(|(i, variant_def)| {
1149                         let fields: Vec<_> =
1150                             variant_def.fields.iter().map(|f| f.name).collect();
1151                         build_variant_info(Some(variant_def.name),
1152                                             &fields,
1153                                             layout.for_variant(self, i))
1154                     })
1155                     .collect();
1156                 record(adt_kind.into(), adt_packed, match layout.variants {
1157                     Variants::Tagged { ref discr, .. } => Some(discr.value.size(self)),
1158                     _ => None
1159                 }, variant_infos);
1160             }
1161         }
1162     }
1163 }
1164
1165 /// Type size "skeleton", i.e. the only information determining a type's size.
1166 /// While this is conservative, (aside from constant sizes, only pointers,
1167 /// newtypes thereof and null pointer optimized enums are allowed), it is
1168 /// enough to statically check common usecases of transmute.
1169 #[derive(Copy, Clone, Debug)]
1170 pub enum SizeSkeleton<'tcx> {
1171     /// Any statically computable Layout.
1172     Known(Size),
1173
1174     /// A potentially-fat pointer.
1175     Pointer {
1176         /// If true, this pointer is never null.
1177         non_zero: bool,
1178         /// The type which determines the unsized metadata, if any,
1179         /// of this pointer. Either a type parameter or a projection
1180         /// depending on one, with regions erased.
1181         tail: Ty<'tcx>
1182     }
1183 }
1184
1185 impl<'a, 'tcx> SizeSkeleton<'tcx> {
1186     pub fn compute(ty: Ty<'tcx>,
1187                    tcx: TyCtxt<'a, 'tcx, 'tcx>,
1188                    param_env: ty::ParamEnv<'tcx>)
1189                    -> Result<SizeSkeleton<'tcx>, LayoutError<'tcx>> {
1190         assert!(!ty.has_infer_types());
1191
1192         // First try computing a static layout.
1193         let err = match tcx.layout_of(param_env.and(ty)) {
1194             Ok(layout) => {
1195                 return Ok(SizeSkeleton::Known(layout.size));
1196             }
1197             Err(err) => err
1198         };
1199
1200         match ty.sty {
1201             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
1202             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1203                 let non_zero = !ty.is_unsafe_ptr();
1204                 let tail = tcx.struct_tail(pointee);
1205                 match tail.sty {
1206                     ty::TyParam(_) | ty::TyProjection(_) => {
1207                         assert!(tail.has_param_types() || tail.has_self_ty());
1208                         Ok(SizeSkeleton::Pointer {
1209                             non_zero,
1210                             tail: tcx.erase_regions(&tail)
1211                         })
1212                     }
1213                     _ => {
1214                         bug!("SizeSkeleton::compute({}): layout errored ({}), yet \
1215                               tail `{}` is not a type parameter or a projection",
1216                              ty, err, tail)
1217                     }
1218                 }
1219             }
1220
1221             ty::TyAdt(def, substs) => {
1222                 // Only newtypes and enums w/ nullable pointer optimization.
1223                 if def.is_union() || def.variants.is_empty() || def.variants.len() > 2 {
1224                     return Err(err);
1225                 }
1226
1227                 // Get a zero-sized variant or a pointer newtype.
1228                 let zero_or_ptr_variant = |i: usize| {
1229                     let fields = def.variants[i].fields.iter().map(|field| {
1230                         SizeSkeleton::compute(field.ty(tcx, substs), tcx, param_env)
1231                     });
1232                     let mut ptr = None;
1233                     for field in fields {
1234                         let field = field?;
1235                         match field {
1236                             SizeSkeleton::Known(size) => {
1237                                 if size.bytes() > 0 {
1238                                     return Err(err);
1239                                 }
1240                             }
1241                             SizeSkeleton::Pointer {..} => {
1242                                 if ptr.is_some() {
1243                                     return Err(err);
1244                                 }
1245                                 ptr = Some(field);
1246                             }
1247                         }
1248                     }
1249                     Ok(ptr)
1250                 };
1251
1252                 let v0 = zero_or_ptr_variant(0)?;
1253                 // Newtype.
1254                 if def.variants.len() == 1 {
1255                     if let Some(SizeSkeleton::Pointer { non_zero, tail }) = v0 {
1256                         return Ok(SizeSkeleton::Pointer {
1257                             non_zero: non_zero ||
1258                                 Some(def.did) == tcx.lang_items().non_zero(),
1259                             tail,
1260                         });
1261                     } else {
1262                         return Err(err);
1263                     }
1264                 }
1265
1266                 let v1 = zero_or_ptr_variant(1)?;
1267                 // Nullable pointer enum optimization.
1268                 match (v0, v1) {
1269                     (Some(SizeSkeleton::Pointer { non_zero: true, tail }), None) |
1270                     (None, Some(SizeSkeleton::Pointer { non_zero: true, tail })) => {
1271                         Ok(SizeSkeleton::Pointer {
1272                             non_zero: false,
1273                             tail,
1274                         })
1275                     }
1276                     _ => Err(err)
1277                 }
1278             }
1279
1280             ty::TyProjection(_) | ty::TyAnon(..) => {
1281                 let normalized = tcx.normalize_erasing_regions(param_env, ty);
1282                 if ty == normalized {
1283                     Err(err)
1284                 } else {
1285                     SizeSkeleton::compute(normalized, tcx, param_env)
1286                 }
1287             }
1288
1289             _ => Err(err)
1290         }
1291     }
1292
1293     pub fn same_size(self, other: SizeSkeleton) -> bool {
1294         match (self, other) {
1295             (SizeSkeleton::Known(a), SizeSkeleton::Known(b)) => a == b,
1296             (SizeSkeleton::Pointer { tail: a, .. },
1297              SizeSkeleton::Pointer { tail: b, .. }) => a == b,
1298             _ => false
1299         }
1300     }
1301 }
1302
1303 pub trait HasTyCtxt<'tcx>: HasDataLayout {
1304     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'tcx, 'tcx>;
1305 }
1306
1307 impl<'a, 'gcx, 'tcx> HasDataLayout for TyCtxt<'a, 'gcx, 'tcx> {
1308     fn data_layout(&self) -> &TargetDataLayout {
1309         &self.data_layout
1310     }
1311 }
1312
1313 impl<'a, 'gcx, 'tcx> HasTyCtxt<'gcx> for TyCtxt<'a, 'gcx, 'tcx> {
1314     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'gcx> {
1315         self.global_tcx()
1316     }
1317 }
1318
1319 impl<'tcx, T: HasDataLayout> HasDataLayout for LayoutCx<'tcx, T> {
1320     fn data_layout(&self) -> &TargetDataLayout {
1321         self.tcx.data_layout()
1322     }
1323 }
1324
1325 impl<'gcx, 'tcx, T: HasTyCtxt<'gcx>> HasTyCtxt<'gcx> for LayoutCx<'tcx, T> {
1326     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'gcx> {
1327         self.tcx.tcx()
1328     }
1329 }
1330
1331 pub trait MaybeResult<T> {
1332     fn from_ok(x: T) -> Self;
1333     fn map_same<F: FnOnce(T) -> T>(self, f: F) -> Self;
1334 }
1335
1336 impl<T> MaybeResult<T> for T {
1337     fn from_ok(x: T) -> Self {
1338         x
1339     }
1340     fn map_same<F: FnOnce(T) -> T>(self, f: F) -> Self {
1341         f(self)
1342     }
1343 }
1344
1345 impl<T, E> MaybeResult<T> for Result<T, E> {
1346     fn from_ok(x: T) -> Self {
1347         Ok(x)
1348     }
1349     fn map_same<F: FnOnce(T) -> T>(self, f: F) -> Self {
1350         self.map(f)
1351     }
1352 }
1353
1354 pub type TyLayout<'tcx> = ::rustc_target::abi::TyLayout<'tcx, Ty<'tcx>>;
1355
1356 impl<'a, 'tcx> LayoutOf for LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
1357     type Ty = Ty<'tcx>;
1358     type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
1359
1360     /// Computes the layout of a type. Note that this implicitly
1361     /// executes in "reveal all" mode.
1362     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
1363         let param_env = self.param_env.with_reveal_all();
1364         let ty = self.tcx.normalize_erasing_regions(param_env, ty);
1365         let details = self.tcx.layout_raw(param_env.and(ty))?;
1366         let layout = TyLayout {
1367             ty,
1368             details
1369         };
1370
1371         // NB: This recording is normally disabled; when enabled, it
1372         // can however trigger recursive invocations of `layout_of`.
1373         // Therefore, we execute it *after* the main query has
1374         // completed, to avoid problems around recursive structures
1375         // and the like. (Admittedly, I wasn't able to reproduce a problem
1376         // here, but it seems like the right thing to do. -nmatsakis)
1377         self.record_layout_for_printing(layout);
1378
1379         Ok(layout)
1380     }
1381 }
1382
1383 impl<'a, 'tcx> LayoutOf for LayoutCx<'tcx, ty::maps::TyCtxtAt<'a, 'tcx, 'tcx>> {
1384     type Ty = Ty<'tcx>;
1385     type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
1386
1387     /// Computes the layout of a type. Note that this implicitly
1388     /// executes in "reveal all" mode.
1389     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
1390         let param_env = self.param_env.with_reveal_all();
1391         let ty = self.tcx.normalize_erasing_regions(param_env, ty);
1392         let details = self.tcx.layout_raw(param_env.and(ty))?;
1393         let layout = TyLayout {
1394             ty,
1395             details
1396         };
1397
1398         // NB: This recording is normally disabled; when enabled, it
1399         // can however trigger recursive invocations of `layout_of`.
1400         // Therefore, we execute it *after* the main query has
1401         // completed, to avoid problems around recursive structures
1402         // and the like. (Admittedly, I wasn't able to reproduce a problem
1403         // here, but it seems like the right thing to do. -nmatsakis)
1404         let cx = LayoutCx {
1405             tcx: *self.tcx,
1406             param_env: self.param_env
1407         };
1408         cx.record_layout_for_printing(layout);
1409
1410         Ok(layout)
1411     }
1412 }
1413
1414 // Helper (inherent) `layout_of` methods to avoid pushing `LayoutCx` to users.
1415 impl<'a, 'tcx> TyCtxt<'a, 'tcx, 'tcx> {
1416     /// Computes the layout of a type. Note that this implicitly
1417     /// executes in "reveal all" mode.
1418     #[inline]
1419     pub fn layout_of(self, param_env_and_ty: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
1420                      -> Result<TyLayout<'tcx>, LayoutError<'tcx>> {
1421         let cx = LayoutCx {
1422             tcx: self,
1423             param_env: param_env_and_ty.param_env
1424         };
1425         cx.layout_of(param_env_and_ty.value)
1426     }
1427 }
1428
1429 impl<'a, 'tcx> ty::maps::TyCtxtAt<'a, 'tcx, 'tcx> {
1430     /// Computes the layout of a type. Note that this implicitly
1431     /// executes in "reveal all" mode.
1432     #[inline]
1433     pub fn layout_of(self, param_env_and_ty: ty::ParamEnvAnd<'tcx, Ty<'tcx>>)
1434                      -> Result<TyLayout<'tcx>, LayoutError<'tcx>> {
1435         let cx = LayoutCx {
1436             tcx: self,
1437             param_env: param_env_and_ty.param_env
1438         };
1439         cx.layout_of(param_env_and_ty.value)
1440     }
1441 }
1442
1443 impl<'a, 'tcx, C> TyLayoutMethods<'tcx, C> for Ty<'tcx>
1444     where C: LayoutOf<Ty = Ty<'tcx>> + HasTyCtxt<'tcx>,
1445           C::TyLayout: MaybeResult<TyLayout<'tcx>>
1446 {
1447     fn for_variant(this: TyLayout<'tcx>, cx: C, variant_index: usize) -> TyLayout<'tcx> {
1448         let details = match this.variants {
1449             Variants::Single { index } if index == variant_index => this.details,
1450
1451             Variants::Single { index } => {
1452                 // Deny calling for_variant more than once for non-Single enums.
1453                 cx.layout_of(this.ty).map_same(|layout| {
1454                     assert_eq!(layout.variants, Variants::Single { index });
1455                     layout
1456                 });
1457
1458                 let fields = match this.ty.sty {
1459                     ty::TyAdt(def, _) => def.variants[variant_index].fields.len(),
1460                     _ => bug!()
1461                 };
1462                 let mut details = LayoutDetails::uninhabited(fields);
1463                 details.variants = Variants::Single { index: variant_index };
1464                 cx.tcx().intern_layout(details)
1465             }
1466
1467             Variants::NicheFilling { ref variants, .. } |
1468             Variants::Tagged { ref variants, .. } => {
1469                 &variants[variant_index]
1470             }
1471         };
1472
1473         assert_eq!(details.variants, Variants::Single { index: variant_index });
1474
1475         TyLayout {
1476             ty: this.ty,
1477             details
1478         }
1479     }
1480
1481     fn field(this: TyLayout<'tcx>, cx: C, i: usize) -> C::TyLayout {
1482         let tcx = cx.tcx();
1483         cx.layout_of(match this.ty.sty {
1484             ty::TyBool |
1485             ty::TyChar |
1486             ty::TyInt(_) |
1487             ty::TyUint(_) |
1488             ty::TyFloat(_) |
1489             ty::TyFnPtr(_) |
1490             ty::TyNever |
1491             ty::TyFnDef(..) |
1492             ty::TyGeneratorWitness(..) |
1493             ty::TyForeign(..) |
1494             ty::TyDynamic(..) => {
1495                 bug!("TyLayout::field_type({:?}): not applicable", this)
1496             }
1497
1498             // Potentially-fat pointers.
1499             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
1500             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1501                 assert!(i < 2);
1502
1503                 // Reuse the fat *T type as its own thin pointer data field.
1504                 // This provides information about e.g. DST struct pointees
1505                 // (which may have no non-DST form), and will work as long
1506                 // as the `Abi` or `FieldPlacement` is checked by users.
1507                 if i == 0 {
1508                     let nil = tcx.mk_nil();
1509                     let ptr_ty = if this.ty.is_unsafe_ptr() {
1510                         tcx.mk_mut_ptr(nil)
1511                     } else {
1512                         tcx.mk_mut_ref(tcx.types.re_static, nil)
1513                     };
1514                     return cx.layout_of(ptr_ty).map_same(|mut ptr_layout| {
1515                         ptr_layout.ty = this.ty;
1516                         ptr_layout
1517                     });
1518                 }
1519
1520                 match tcx.struct_tail(pointee).sty {
1521                     ty::TySlice(_) |
1522                     ty::TyStr => tcx.types.usize,
1523                     ty::TyDynamic(..) => {
1524                         // FIXME(eddyb) use an usize/fn() array with
1525                         // the correct number of vtables slots.
1526                         tcx.mk_imm_ref(tcx.types.re_static, tcx.mk_nil())
1527                     }
1528                     _ => bug!("TyLayout::field_type({:?}): not applicable", this)
1529                 }
1530             }
1531
1532             // Arrays and slices.
1533             ty::TyArray(element, _) |
1534             ty::TySlice(element) => element,
1535             ty::TyStr => tcx.types.u8,
1536
1537             // Tuples, generators and closures.
1538             ty::TyClosure(def_id, ref substs) => {
1539                 substs.upvar_tys(def_id, tcx).nth(i).unwrap()
1540             }
1541
1542             ty::TyGenerator(def_id, ref substs, _) => {
1543                 substs.field_tys(def_id, tcx).nth(i).unwrap()
1544             }
1545
1546             ty::TyTuple(tys) => tys[i],
1547
1548             // SIMD vector types.
1549             ty::TyAdt(def, ..) if def.repr.simd() => {
1550                 this.ty.simd_type(tcx)
1551             }
1552
1553             // ADTs.
1554             ty::TyAdt(def, substs) => {
1555                 match this.variants {
1556                     Variants::Single { index } => {
1557                         def.variants[index].fields[i].ty(tcx, substs)
1558                     }
1559
1560                     // Discriminant field for enums (where applicable).
1561                     Variants::Tagged { ref discr, .. } |
1562                     Variants::NicheFilling { niche: ref discr, .. } => {
1563                         assert_eq!(i, 0);
1564                         let layout = LayoutDetails::scalar(tcx, discr.clone());
1565                         return MaybeResult::from_ok(TyLayout {
1566                             details: tcx.intern_layout(layout),
1567                             ty: discr.value.to_ty(tcx)
1568                         });
1569                     }
1570                 }
1571             }
1572
1573             ty::TyProjection(_) | ty::TyAnon(..) | ty::TyParam(_) |
1574             ty::TyInfer(_) | ty::TyError => {
1575                 bug!("TyLayout::field_type: unexpected type `{}`", this.ty)
1576             }
1577         })
1578     }
1579 }
1580
1581 impl<'a, 'tcx> LayoutCx<'tcx, TyCtxt<'a, 'tcx, 'tcx>> {
1582     /// Find the offset of a niche leaf field, starting from
1583     /// the given type and recursing through aggregates, which
1584     /// has at least `count` consecutive invalid values.
1585     /// The tuple is `(offset, scalar, niche_value)`.
1586     // FIXME(eddyb) traverse already optimized enums.
1587     fn find_niche(self, layout: TyLayout<'tcx>, count: u128)
1588         -> Result<Option<(Size, Scalar, u128)>, LayoutError<'tcx>>
1589     {
1590         let scalar_component = |scalar: &Scalar, offset| {
1591             let Scalar { value, valid_range: ref v } = *scalar;
1592
1593             let bits = value.size(self).bits();
1594             assert!(bits <= 128);
1595             let max_value = !0u128 >> (128 - bits);
1596
1597             // Find out how many values are outside the valid range.
1598             let niches = if v.start <= v.end {
1599                 v.start + (max_value - v.end)
1600             } else {
1601                 v.start - v.end - 1
1602             };
1603
1604             // Give up if we can't fit `count` consecutive niches.
1605             if count > niches {
1606                 return None;
1607             }
1608
1609             let niche_start = v.end.wrapping_add(1) & max_value;
1610             let niche_end = v.end.wrapping_add(count) & max_value;
1611             Some((offset, Scalar {
1612                 value,
1613                 valid_range: v.start..=niche_end
1614             }, niche_start))
1615         };
1616
1617         // Locals variables which live across yields are stored
1618         // in the generator type as fields. These may be uninitialized
1619         // so we don't look for niches there.
1620         if let ty::TyGenerator(..) = layout.ty.sty {
1621             return Ok(None);
1622         }
1623
1624         match layout.abi {
1625             Abi::Scalar(ref scalar) => {
1626                 return Ok(scalar_component(scalar, Size::from_bytes(0)));
1627             }
1628             Abi::ScalarPair(ref a, ref b) => {
1629                 return Ok(scalar_component(a, Size::from_bytes(0)).or_else(|| {
1630                     scalar_component(b, a.value.size(self).abi_align(b.value.align(self)))
1631                 }));
1632             }
1633             Abi::Vector { ref element, .. } => {
1634                 return Ok(scalar_component(element, Size::from_bytes(0)));
1635             }
1636             _ => {}
1637         }
1638
1639         // Perhaps one of the fields is non-zero, let's recurse and find out.
1640         if let FieldPlacement::Union(_) = layout.fields {
1641             // Only Rust enums have safe-to-inspect fields
1642             // (a discriminant), other unions are unsafe.
1643             if let Variants::Single { .. } = layout.variants {
1644                 return Ok(None);
1645             }
1646         }
1647         if let FieldPlacement::Array { .. } = layout.fields {
1648             if layout.fields.count() > 0 {
1649                 return self.find_niche(layout.field(self, 0)?, count);
1650             }
1651         }
1652         for i in 0..layout.fields.count() {
1653             let r = self.find_niche(layout.field(self, i)?, count)?;
1654             if let Some((offset, scalar, niche_value)) = r {
1655                 let offset = layout.fields.offset(i) + offset;
1656                 return Ok(Some((offset, scalar, niche_value)));
1657             }
1658         }
1659         Ok(None)
1660     }
1661 }
1662
1663 impl<'a> HashStable<StableHashingContext<'a>> for Variants {
1664     fn hash_stable<W: StableHasherResult>(&self,
1665                                           hcx: &mut StableHashingContext<'a>,
1666                                           hasher: &mut StableHasher<W>) {
1667         use ty::layout::Variants::*;
1668         mem::discriminant(self).hash_stable(hcx, hasher);
1669
1670         match *self {
1671             Single { index } => {
1672                 index.hash_stable(hcx, hasher);
1673             }
1674             Tagged {
1675                 ref discr,
1676                 ref variants,
1677             } => {
1678                 discr.hash_stable(hcx, hasher);
1679                 variants.hash_stable(hcx, hasher);
1680             }
1681             NicheFilling {
1682                 dataful_variant,
1683                 niche_variants: RangeInclusive { start, end },
1684                 ref niche,
1685                 niche_start,
1686                 ref variants,
1687             } => {
1688                 dataful_variant.hash_stable(hcx, hasher);
1689                 start.hash_stable(hcx, hasher);
1690                 end.hash_stable(hcx, hasher);
1691                 niche.hash_stable(hcx, hasher);
1692                 niche_start.hash_stable(hcx, hasher);
1693                 variants.hash_stable(hcx, hasher);
1694             }
1695         }
1696     }
1697 }
1698
1699 impl<'a> HashStable<StableHashingContext<'a>> for FieldPlacement {
1700     fn hash_stable<W: StableHasherResult>(&self,
1701                                           hcx: &mut StableHashingContext<'a>,
1702                                           hasher: &mut StableHasher<W>) {
1703         use ty::layout::FieldPlacement::*;
1704         mem::discriminant(self).hash_stable(hcx, hasher);
1705
1706         match *self {
1707             Union(count) => {
1708                 count.hash_stable(hcx, hasher);
1709             }
1710             Array { count, stride } => {
1711                 count.hash_stable(hcx, hasher);
1712                 stride.hash_stable(hcx, hasher);
1713             }
1714             Arbitrary { ref offsets, ref memory_index } => {
1715                 offsets.hash_stable(hcx, hasher);
1716                 memory_index.hash_stable(hcx, hasher);
1717             }
1718         }
1719     }
1720 }
1721
1722 impl<'a> HashStable<StableHashingContext<'a>> for Abi {
1723     fn hash_stable<W: StableHasherResult>(&self,
1724                                           hcx: &mut StableHashingContext<'a>,
1725                                           hasher: &mut StableHasher<W>) {
1726         use ty::layout::Abi::*;
1727         mem::discriminant(self).hash_stable(hcx, hasher);
1728
1729         match *self {
1730             Uninhabited => {}
1731             Scalar(ref value) => {
1732                 value.hash_stable(hcx, hasher);
1733             }
1734             ScalarPair(ref a, ref b) => {
1735                 a.hash_stable(hcx, hasher);
1736                 b.hash_stable(hcx, hasher);
1737             }
1738             Vector { ref element, count } => {
1739                 element.hash_stable(hcx, hasher);
1740                 count.hash_stable(hcx, hasher);
1741             }
1742             Aggregate { sized } => {
1743                 sized.hash_stable(hcx, hasher);
1744             }
1745         }
1746     }
1747 }
1748
1749 impl<'a> HashStable<StableHashingContext<'a>> for Scalar {
1750     fn hash_stable<W: StableHasherResult>(&self,
1751                                           hcx: &mut StableHashingContext<'a>,
1752                                           hasher: &mut StableHasher<W>) {
1753         let Scalar { value, valid_range: RangeInclusive { start, end } } = *self;
1754         value.hash_stable(hcx, hasher);
1755         start.hash_stable(hcx, hasher);
1756         end.hash_stable(hcx, hasher);
1757     }
1758 }
1759
1760 impl_stable_hash_for!(struct ::ty::layout::LayoutDetails {
1761     variants,
1762     fields,
1763     abi,
1764     size,
1765     align
1766 });
1767
1768 impl_stable_hash_for!(enum ::ty::layout::Integer {
1769     I8,
1770     I16,
1771     I32,
1772     I64,
1773     I128
1774 });
1775
1776 impl_stable_hash_for!(enum ::ty::layout::Primitive {
1777     Int(integer, signed),
1778     F32,
1779     F64,
1780     Pointer
1781 });
1782
1783 impl<'gcx> HashStable<StableHashingContext<'gcx>> for Align {
1784     fn hash_stable<W: StableHasherResult>(&self,
1785                                           hcx: &mut StableHashingContext<'gcx>,
1786                                           hasher: &mut StableHasher<W>) {
1787         self.abi().hash_stable(hcx, hasher);
1788         self.pref().hash_stable(hcx, hasher);
1789     }
1790 }
1791
1792 impl<'gcx> HashStable<StableHashingContext<'gcx>> for Size {
1793     fn hash_stable<W: StableHasherResult>(&self,
1794                                           hcx: &mut StableHashingContext<'gcx>,
1795                                           hasher: &mut StableHasher<W>) {
1796         self.bytes().hash_stable(hcx, hasher);
1797     }
1798 }
1799
1800 impl<'a, 'gcx> HashStable<StableHashingContext<'a>> for LayoutError<'gcx>
1801 {
1802     fn hash_stable<W: StableHasherResult>(&self,
1803                                           hcx: &mut StableHashingContext<'a>,
1804                                           hasher: &mut StableHasher<W>) {
1805         use ty::layout::LayoutError::*;
1806         mem::discriminant(self).hash_stable(hcx, hasher);
1807
1808         match *self {
1809             Unknown(t) |
1810             SizeOverflow(t) => t.hash_stable(hcx, hasher)
1811         }
1812     }
1813 }