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 pub use self::Integer::*;
  12 pub use self::Layout::*;
  13 pub use self::Primitive::*;
  14
  15 use session::{self, DataTypeKind, Session};
  16 use ty::{self, Ty, TyCtxt, TypeFoldable, ReprOptions, ReprFlags};
  17
  18 use syntax::ast::{self, FloatTy, IntTy, UintTy};
  19 use syntax::attr;
  20 use syntax_pos::DUMMY_SP;
  21
  22 use std::cmp;
  23 use std::fmt;
  24 use std::i64;
  25 use std::iter;
  26 use std::ops::Deref;
  27
  28 /// Parsed [Data layout](http://llvm.org/docs/LangRef.html#data-layout)
  29 /// for a target, which contains everything needed to compute layouts.
  30 pub struct TargetDataLayout {
  31     pub endian: Endian,
  32     pub i1_align: Align,
  33     pub i8_align: Align,
  34     pub i16_align: Align,
  35     pub i32_align: Align,
  36     pub i64_align: Align,
  37     pub i128_align: Align,
  38     pub f32_align: Align,
  39     pub f64_align: Align,
  40     pub pointer_size: Size,
  41     pub pointer_align: Align,
  42     pub aggregate_align: Align,
  43
  44     /// Alignments for vector types.
  45     pub vector_align: Vec<(Size, Align)>
  46 }
  47
  48 impl Default for TargetDataLayout {
  49     /// Creates an instance of `TargetDataLayout`.
  50     fn default() -> TargetDataLayout {
  51         TargetDataLayout {
  52             endian: Endian::Big,
  53             i1_align: Align::from_bits(8, 8).unwrap(),
  54             i8_align: Align::from_bits(8, 8).unwrap(),
  55             i16_align: Align::from_bits(16, 16).unwrap(),
  56             i32_align: Align::from_bits(32, 32).unwrap(),
  57             i64_align: Align::from_bits(32, 64).unwrap(),
  58             i128_align: Align::from_bits(32, 64).unwrap(),
  59             f32_align: Align::from_bits(32, 32).unwrap(),
  60             f64_align: Align::from_bits(64, 64).unwrap(),
  61             pointer_size: Size::from_bits(64),
  62             pointer_align: Align::from_bits(64, 64).unwrap(),
  63             aggregate_align: Align::from_bits(0, 64).unwrap(),
  64             vector_align: vec![
  65                 (Size::from_bits(64), Align::from_bits(64, 64).unwrap()),
  66                 (Size::from_bits(128), Align::from_bits(128, 128).unwrap())
  67             ]
  68         }
  69     }
  70 }
  71
  72 impl TargetDataLayout {
  73     pub fn parse(sess: &Session) -> TargetDataLayout {
  74         // Parse a bit count from a string.
  75         let parse_bits = |s: &str, kind: &str, cause: &str| {
  76             s.parse::<u64>().unwrap_or_else(|err| {
  77                 sess.err(&format!("invalid {} `{}` for `{}` in \"data-layout\": {}",
  78                                   kind, s, cause, err));
  79                 0
  80             })
  81         };
  82
  83         // Parse a size string.
  84         let size = |s: &str, cause: &str| {
  85             Size::from_bits(parse_bits(s, "size", cause))
  86         };
  87
  88         // Parse an alignment string.
  89         let align = |s: &[&str], cause: &str| {
  90             if s.is_empty() {
  91                 sess.err(&format!("missing alignment for `{}` in \"data-layout\"", cause));
  92             }
  93             let abi = parse_bits(s[0], "alignment", cause);
  94             let pref = s.get(1).map_or(abi, |pref| parse_bits(pref, "alignment", cause));
  95             Align::from_bits(abi, pref).unwrap_or_else(|err| {
  96                 sess.err(&format!("invalid alignment for `{}` in \"data-layout\": {}",
  97                                   cause, err));
  98                 Align::from_bits(8, 8).unwrap()
  99             })
 100         };
 101
 102         let mut dl = TargetDataLayout::default();
 103         let mut i128_align_src = 64;
 104         for spec in sess.target.target.data_layout.split("-") {
 105             match &spec.split(":").collect::<Vec<_>>()[..] {
 106                 &["e"] => dl.endian = Endian::Little,
 107                 &["E"] => dl.endian = Endian::Big,
 108                 &["a", ref a..] => dl.aggregate_align = align(a, "a"),
 109                 &["f32", ref a..] => dl.f32_align = align(a, "f32"),
 110                 &["f64", ref a..] => dl.f64_align = align(a, "f64"),
 111                 &[p @ "p", s, ref a..] | &[p @ "p0", s, ref a..] => {
 112                     dl.pointer_size = size(s, p);
 113                     dl.pointer_align = align(a, p);
 114                 }
 115                 &[s, ref a..] if s.starts_with("i") => {
 116                     let bits = match s[1..].parse::<u64>() {
 117                         Ok(bits) => bits,
 118                         Err(_) => {
 119                             size(&s[1..], "i"); // For the user error.
 120                             continue;
 121                         }
 122                     };
 123                     let a = align(a, s);
 124                     match bits {
 125                         1 => dl.i1_align = a,
 126                         8 => dl.i8_align = a,
 127                         16 => dl.i16_align = a,
 128                         32 => dl.i32_align = a,
 129                         64 => dl.i64_align = a,
 130                         _ => {}
 131                     }
 132                     if bits >= i128_align_src && bits <= 128 {
 133                         // Default alignment for i128 is decided by taking the alignment of
 134                         // largest-sized i{64...128}.
 135                         i128_align_src = bits;
 136                         dl.i128_align = a;
 137                     }
 138                 }
 139                 &[s, ref a..] if s.starts_with("v") => {
 140                     let v_size = size(&s[1..], "v");
 141                     let a = align(a, s);
 142                     if let Some(v) = dl.vector_align.iter_mut().find(|v| v.0 == v_size) {
 143                         v.1 = a;
 144                         continue;
 145                     }
 146                     // No existing entry, add a new one.
 147                     dl.vector_align.push((v_size, a));
 148                 }
 149                 _ => {} // Ignore everything else.
 150             }
 151         }
 152
 153         // Perform consistency checks against the Target information.
 154         let endian_str = match dl.endian {
 155             Endian::Little => "little",
 156             Endian::Big => "big"
 157         };
 158         if endian_str != sess.target.target.target_endian {
 159             sess.err(&format!("inconsistent target specification: \"data-layout\" claims \
 160                                architecture is {}-endian, while \"target-endian\" is `{}`",
 161                               endian_str, sess.target.target.target_endian));
 162         }
 163
 164         if dl.pointer_size.bits().to_string() != sess.target.target.target_pointer_width {
 165             sess.err(&format!("inconsistent target specification: \"data-layout\" claims \
 166                                pointers are {}-bit, while \"target-pointer-width\" is `{}`",
 167                               dl.pointer_size.bits(), sess.target.target.target_pointer_width));
 168         }
 169
 170         dl
 171     }
 172
 173     /// Return exclusive upper bound on object size.
 174     ///
 175     /// The theoretical maximum object size is defined as the maximum positive `isize` value.
 176     /// This ensures that the `offset` semantics remain well-defined by allowing it to correctly
 177     /// index every address within an object along with one byte past the end, along with allowing
 178     /// `isize` to store the difference between any two pointers into an object.
 179     ///
 180     /// The upper bound on 64-bit currently needs to be lower because LLVM uses a 64-bit integer
 181     /// to represent object size in bits. It would need to be 1 << 61 to account for this, but is
 182     /// currently conservatively bounded to 1 << 47 as that is enough to cover the current usable
 183     /// address space on 64-bit ARMv8 and x86_64.
 184     pub fn obj_size_bound(&self) -> u64 {
 185         match self.pointer_size.bits() {
 186             16 => 1 << 15,
 187             32 => 1 << 31,
 188             64 => 1 << 47,
 189             bits => bug!("obj_size_bound: unknown pointer bit size {}", bits)
 190         }
 191     }
 192
 193     pub fn ptr_sized_integer(&self) -> Integer {
 194         match self.pointer_size.bits() {
 195             16 => I16,
 196             32 => I32,
 197             64 => I64,
 198             bits => bug!("ptr_sized_integer: unknown pointer bit size {}", bits)
 199         }
 200     }
 201 }
 202
 203 pub trait HasDataLayout: Copy {
 204     fn data_layout(&self) -> &TargetDataLayout;
 205 }
 206
 207 impl<'a> HasDataLayout for &'a TargetDataLayout {
 208     fn data_layout(&self) -> &TargetDataLayout {
 209         self
 210     }
 211 }
 212
 213 impl<'a, 'tcx> HasDataLayout for TyCtxt<'a, 'tcx, 'tcx> {
 214     fn data_layout(&self) -> &TargetDataLayout {
 215         &self.data_layout
 216     }
 217 }
 218
 219 /// Endianness of the target, which must match cfg(target-endian).
 220 #[derive(Copy, Clone)]
 221 pub enum Endian {
 222     Little,
 223     Big
 224 }
 225
 226 /// Size of a type in bytes.
 227 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 228 pub struct Size {
 229     raw: u64
 230 }
 231
 232 impl Size {
 233     pub fn from_bits(bits: u64) -> Size {
 234         Size::from_bytes((bits + 7) / 8)
 235     }
 236
 237     pub fn from_bytes(bytes: u64) -> Size {
 238         if bytes >= (1 << 61) {
 239             bug!("Size::from_bytes: {} bytes in bits doesn't fit in u64", bytes)
 240         }
 241         Size {
 242             raw: bytes
 243         }
 244     }
 245
 246     pub fn bytes(self) -> u64 {
 247         self.raw
 248     }
 249
 250     pub fn bits(self) -> u64 {
 251         self.bytes() * 8
 252     }
 253
 254     pub fn abi_align(self, align: Align) -> Size {
 255         let mask = align.abi() - 1;
 256         Size::from_bytes((self.bytes() + mask) & !mask)
 257     }
 258
 259     pub fn checked_add<C: HasDataLayout>(self, offset: Size, cx: C) -> Option<Size> {
 260         let dl = cx.data_layout();
 261
 262         // Each Size is less than dl.obj_size_bound(), so the sum is
 263         // also less than 1 << 62 (and therefore can't overflow).
 264         let bytes = self.bytes() + offset.bytes();
 265
 266         if bytes < dl.obj_size_bound() {
 267             Some(Size::from_bytes(bytes))
 268         } else {
 269             None
 270         }
 271     }
 272
 273     pub fn checked_mul<C: HasDataLayout>(self, count: u64, cx: C) -> Option<Size> {
 274         let dl = cx.data_layout();
 275
 276         // Each Size is less than dl.obj_size_bound(), so the sum is
 277         // also less than 1 << 62 (and therefore can't overflow).
 278         match self.bytes().checked_mul(count) {
 279             Some(bytes) if bytes < dl.obj_size_bound() => {
 280                 Some(Size::from_bytes(bytes))
 281             }
 282             _ => None
 283         }
 284     }
 285 }
 286
 287 /// Alignment of a type in bytes, both ABI-mandated and preferred.
 288 /// Each field is a power of two, giving the alignment a maximum
 289 /// value of 2^(2^8 - 1), which is limited by LLVM to a i32, with
 290 /// a maximum capacity of 2^31 - 1 or 2147483647.
 291 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 292 pub struct Align {
 293     abi: u8,
 294     pref: u8,
 295 }
 296
 297 impl Align {
 298     pub fn from_bits(abi: u64, pref: u64) -> Result<Align, String> {
 299         Align::from_bytes((abi + 7) / 8, (pref + 7) / 8)
 300     }
 301
 302     pub fn from_bytes(abi: u64, pref: u64) -> Result<Align, String> {
 303         let log2 = |align: u64| {
 304             // Treat an alignment of 0 bytes like 1-byte alignment.
 305             if align == 0 {
 306                 return Ok(0);
 307             }
 308
 309             let mut bytes = align;
 310             let mut pow: u8 = 0;
 311             while (bytes & 1) == 0 {
 312                 pow += 1;
 313                 bytes >>= 1;
 314             }
 315             if bytes != 1 {
 316                 Err(format!("`{}` is not a power of 2", align))
 317             } else if pow > 30 {
 318                 Err(format!("`{}` is too large", align))
 319             } else {
 320                 Ok(pow)
 321             }
 322         };
 323
 324         Ok(Align {
 325             abi: log2(abi)?,
 326             pref: log2(pref)?,
 327         })
 328     }
 329
 330     pub fn abi(self) -> u64 {
 331         1 << self.abi
 332     }
 333
 334     pub fn pref(self) -> u64 {
 335         1 << self.pref
 336     }
 337
 338     pub fn min(self, other: Align) -> Align {
 339         Align {
 340             abi: cmp::min(self.abi, other.abi),
 341             pref: cmp::min(self.pref, other.pref),
 342         }
 343     }
 344
 345     pub fn max(self, other: Align) -> Align {
 346         Align {
 347             abi: cmp::max(self.abi, other.abi),
 348             pref: cmp::max(self.pref, other.pref),
 349         }
 350     }
 351 }
 352
 353 /// Integers, also used for enum discriminants.
 354 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 355 pub enum Integer {
 356     I1,
 357     I8,
 358     I16,
 359     I32,
 360     I64,
 361     I128,
 362 }
 363
 364 impl Integer {
 365     pub fn size(&self) -> Size {
 366         match *self {
 367             I1 => Size::from_bits(1),
 368             I8 => Size::from_bytes(1),
 369             I16 => Size::from_bytes(2),
 370             I32 => Size::from_bytes(4),
 371             I64  => Size::from_bytes(8),
 372             I128  => Size::from_bytes(16),
 373         }
 374     }
 375
 376     pub fn align<C: HasDataLayout>(&self, cx: C) -> Align {
 377         let dl = cx.data_layout();
 378
 379         match *self {
 380             I1 => dl.i1_align,
 381             I8 => dl.i8_align,
 382             I16 => dl.i16_align,
 383             I32 => dl.i32_align,
 384             I64 => dl.i64_align,
 385             I128 => dl.i128_align,
 386         }
 387     }
 388
 389     pub fn to_ty<'a, 'tcx>(&self, tcx: &ty::TyCtxt<'a, 'tcx, 'tcx>,
 390                            signed: bool) -> Ty<'tcx> {
 391         match (*self, signed) {
 392             (I1, false) => tcx.types.u8,
 393             (I8, false) => tcx.types.u8,
 394             (I16, false) => tcx.types.u16,
 395             (I32, false) => tcx.types.u32,
 396             (I64, false) => tcx.types.u64,
 397             (I128, false) => tcx.types.u128,
 398             (I1, true) => tcx.types.i8,
 399             (I8, true) => tcx.types.i8,
 400             (I16, true) => tcx.types.i16,
 401             (I32, true) => tcx.types.i32,
 402             (I64, true) => tcx.types.i64,
 403             (I128, true) => tcx.types.i128,
 404         }
 405     }
 406
 407     /// Find the smallest Integer type which can represent the signed value.
 408     pub fn fit_signed(x: i64) -> Integer {
 409         match x {
 410             -0x0000_0000_0000_0001...0x0000_0000_0000_0000 => I1,
 411             -0x0000_0000_0000_0080...0x0000_0000_0000_007f => I8,
 412             -0x0000_0000_0000_8000...0x0000_0000_0000_7fff => I16,
 413             -0x0000_0000_8000_0000...0x0000_0000_7fff_ffff => I32,
 414             -0x8000_0000_0000_0000...0x7fff_ffff_ffff_ffff => I64,
 415             _ => I128
 416         }
 417     }
 418
 419     /// Find the smallest Integer type which can represent the unsigned value.
 420     pub fn fit_unsigned(x: u64) -> Integer {
 421         match x {
 422             0...0x0000_0000_0000_0001 => I1,
 423             0...0x0000_0000_0000_00ff => I8,
 424             0...0x0000_0000_0000_ffff => I16,
 425             0...0x0000_0000_ffff_ffff => I32,
 426             0...0xffff_ffff_ffff_ffff => I64,
 427             _ => I128,
 428         }
 429     }
 430
 431     /// Find the smallest integer with the given alignment.
 432     pub fn for_abi_align<C: HasDataLayout>(cx: C, align: Align) -> Option<Integer> {
 433         let dl = cx.data_layout();
 434
 435         let wanted = align.abi();
 436         for &candidate in &[I8, I16, I32, I64] {
 437             let ty = Int(candidate);
 438             if wanted == ty.align(dl).abi() && wanted == ty.size(dl).bytes() {
 439                 return Some(candidate);
 440             }
 441         }
 442         None
 443     }
 444
 445     /// Get the Integer type from an attr::IntType.
 446     pub fn from_attr<C: HasDataLayout>(cx: C, ity: attr::IntType) -> Integer {
 447         let dl = cx.data_layout();
 448
 449         match ity {
 450             attr::SignedInt(IntTy::I8) | attr::UnsignedInt(UintTy::U8) => I8,
 451             attr::SignedInt(IntTy::I16) | attr::UnsignedInt(UintTy::U16) => I16,
 452             attr::SignedInt(IntTy::I32) | attr::UnsignedInt(UintTy::U32) => I32,
 453             attr::SignedInt(IntTy::I64) | attr::UnsignedInt(UintTy::U64) => I64,
 454             attr::SignedInt(IntTy::I128) | attr::UnsignedInt(UintTy::U128) => I128,
 455             attr::SignedInt(IntTy::Is) | attr::UnsignedInt(UintTy::Us) => {
 456                 dl.ptr_sized_integer()
 457             }
 458         }
 459     }
 460
 461     /// Find the appropriate Integer type and signedness for the given
 462     /// signed discriminant range and #[repr] attribute.
 463     /// N.B.: u64 values above i64::MAX will be treated as signed, but
 464     /// that shouldn't affect anything, other than maybe debuginfo.
 465     fn repr_discr<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 466                             ty: Ty<'tcx>,
 467                             repr: &ReprOptions,
 468                             min: i64,
 469                             max: i64)
 470                             -> (Integer, bool) {
 471         // Theoretically, negative values could be larger in unsigned representation
 472         // than the unsigned representation of the signed minimum. However, if there
 473         // are any negative values, the only valid unsigned representation is u64
 474         // which can fit all i64 values, so the result remains unaffected.
 475         let unsigned_fit = Integer::fit_unsigned(cmp::max(min as u64, max as u64));
 476         let signed_fit = cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));
 477
 478         let mut min_from_extern = None;
 479         let min_default = I8;
 480
 481         if let Some(ity) = repr.int {
 482             let discr = Integer::from_attr(tcx, ity);
 483             let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
 484             if discr < fit {
 485                 bug!("Integer::repr_discr: `#[repr]` hint too small for \
 486                   discriminant range of enum `{}", ty)
 487             }
 488             return (discr, ity.is_signed());
 489         }
 490
 491         if repr.c() {
 492             match &tcx.sess.target.target.arch[..] {
 493                 // WARNING: the ARM EABI has two variants; the one corresponding
 494                 // to `at_least == I32` appears to be used on Linux and NetBSD,
 495                 // but some systems may use the variant corresponding to no
 496                 // lower bound.  However, we don't run on those yet...?
 497                 "arm" => min_from_extern = Some(I32),
 498                 _ => min_from_extern = Some(I32),
 499             }
 500         }
 501
 502         let at_least = min_from_extern.unwrap_or(min_default);
 503
 504         // If there are no negative values, we can use the unsigned fit.
 505         if min >= 0 {
 506             (cmp::max(unsigned_fit, at_least), false)
 507         } else {
 508             (cmp::max(signed_fit, at_least), true)
 509         }
 510     }
 511 }
 512
 513 /// Fundamental unit of memory access and layout.
 514 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 515 pub enum Primitive {
 516     Int(Integer),
 517     F32,
 518     F64,
 519     Pointer
 520 }
 521
 522 impl Primitive {
 523     pub fn size<C: HasDataLayout>(self, cx: C) -> Size {
 524         let dl = cx.data_layout();
 525
 526         match self {
 527             Int(I1) | Int(I8) => Size::from_bits(8),
 528             Int(I16) => Size::from_bits(16),
 529             Int(I32) | F32 => Size::from_bits(32),
 530             Int(I64) | F64 => Size::from_bits(64),
 531             Int(I128) => Size::from_bits(128),
 532             Pointer => dl.pointer_size
 533         }
 534     }
 535
 536     pub fn align<C: HasDataLayout>(self, cx: C) -> Align {
 537         let dl = cx.data_layout();
 538
 539         match self {
 540             Int(I1) => dl.i1_align,
 541             Int(I8) => dl.i8_align,
 542             Int(I16) => dl.i16_align,
 543             Int(I32) => dl.i32_align,
 544             Int(I64) => dl.i64_align,
 545             Int(I128) => dl.i128_align,
 546             F32 => dl.f32_align,
 547             F64 => dl.f64_align,
 548             Pointer => dl.pointer_align
 549         }
 550     }
 551 }
 552
 553 /// Path through fields of nested structures.
 554 // FIXME(eddyb) use small vector optimization for the common case.
 555 pub type FieldPath = Vec<u32>;
 556
 557 /// A structure, a product type in ADT terms.
 558 #[derive(PartialEq, Eq, Hash, Debug)]
 559 pub struct Struct {
 560     /// Maximum alignment of fields and repr alignment.
 561     pub align: Align,
 562
 563     /// Primitive alignment of fields without repr alignment.
 564     pub primitive_align: Align,
 565
 566     /// If true, no alignment padding is used.
 567     pub packed: bool,
 568
 569     /// If true, the size is exact, otherwise it's only a lower bound.
 570     pub sized: bool,
 571
 572     /// Offsets for the first byte of each field, ordered to match the source definition order.
 573     /// This vector does not go in increasing order.
 574     /// FIXME(eddyb) use small vector optimization for the common case.
 575     pub offsets: Vec<Size>,
 576
 577     /// Maps source order field indices to memory order indices, depending how fields were permuted.
 578     /// FIXME (camlorn) also consider small vector  optimization here.
 579     pub memory_index: Vec<u32>,
 580
 581     pub min_size: Size,
 582 }
 583
 584 /// Info required to optimize struct layout.
 585 #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
 586 enum StructKind {
 587     /// A tuple, closure, or univariant which cannot be coerced to unsized.
 588     AlwaysSizedUnivariant,
 589     /// A univariant, the last field of which may be coerced to unsized.
 590     MaybeUnsizedUnivariant,
 591     /// A univariant, but part of an enum.
 592     EnumVariant,
 593 }
 594
 595 impl<'a, 'tcx> Struct {
 596     fn new(dl: &TargetDataLayout,
 597            fields: &Vec<&'a Layout>,
 598            repr: &ReprOptions,
 599            kind: StructKind,
 600            scapegoat: Ty<'tcx>)
 601            -> Result<Struct, LayoutError<'tcx>> {
 602         if repr.packed() && repr.align > 0 {
 603             bug!("Struct cannot be packed and aligned");
 604         }
 605
 606         let align = if repr.packed() {
 607             dl.i8_align
 608         } else {
 609             dl.aggregate_align
 610         };
 611
 612         let mut ret = Struct {
 613             align,
 614             primitive_align: align,
 615             packed: repr.packed(),
 616             sized: true,
 617             offsets: vec![],
 618             memory_index: vec![],
 619             min_size: Size::from_bytes(0),
 620         };
 621
 622         // Anything with repr(C) or repr(packed) doesn't optimize.
 623         // Neither do  1-member and 2-member structs.
 624         // In addition, code in trans assume that 2-element structs can become pairs.
 625         // It's easier to just short-circuit here.
 626         let can_optimize = (fields.len() > 2 || StructKind::EnumVariant == kind)
 627             && (repr.flags & ReprFlags::IS_UNOPTIMISABLE).is_empty();
 628
 629         let (optimize, sort_ascending) = match kind {
 630             StructKind::AlwaysSizedUnivariant => (can_optimize, false),
 631             StructKind::MaybeUnsizedUnivariant => (can_optimize, false),
 632             StructKind::EnumVariant => {
 633                 assert!(fields.len() >= 1, "Enum variants must have discriminants.");
 634                 (can_optimize && fields[0].size(dl).bytes() == 1, true)
 635             }
 636         };
 637
 638         ret.offsets = vec![Size::from_bytes(0); fields.len()];
 639         let mut inverse_memory_index: Vec<u32> = (0..fields.len() as u32).collect();
 640
 641         if optimize {
 642             let start = if let StructKind::EnumVariant = kind { 1 } else { 0 };
 643             let end = if let StructKind::MaybeUnsizedUnivariant = kind {
 644                 fields.len() - 1
 645             } else {
 646                 fields.len()
 647             };
 648             if end > start {
 649                 let optimizing  = &mut inverse_memory_index[start..end];
 650                 if sort_ascending {
 651                     optimizing.sort_by_key(|&x| fields[x as usize].align(dl).abi());
 652                 } else {
 653                     optimizing.sort_by(| &a, &b | {
 654                         let a = fields[a as usize].align(dl).abi();
 655                         let b = fields[b as usize].align(dl).abi();
 656                         b.cmp(&a)
 657                     });
 658                 }
 659             }
 660         }
 661
 662         // inverse_memory_index holds field indices by increasing memory offset.
 663         // That is, if field 5 has offset 0, the first element of inverse_memory_index is 5.
 664         // We now write field offsets to the corresponding offset slot;
 665         // field 5 with offset 0 puts 0 in offsets[5].
 666         // At the bottom of this function, we use inverse_memory_index to produce memory_index.
 667
 668         if let StructKind::EnumVariant = kind {
 669             assert_eq!(inverse_memory_index[0], 0,
 670               "Enum variant discriminants must have the lowest offset.");
 671         }
 672
 673         let mut offset = Size::from_bytes(0);
 674
 675         for i in inverse_memory_index.iter() {
 676             let field = fields[*i as usize];
 677             if !ret.sized {
 678                 bug!("Struct::new: field #{} of `{}` comes after unsized field",
 679                      ret.offsets.len(), scapegoat);
 680             }
 681
 682             if field.is_unsized() {
 683                 ret.sized = false;
 684             }
 685
 686             // Invariant: offset < dl.obj_size_bound() <= 1<<61
 687             if !ret.packed {
 688                 let align = field.align(dl);
 689                 let primitive_align = field.primitive_align(dl);
 690                 ret.align = ret.align.max(align);
 691                 ret.primitive_align = ret.primitive_align.max(primitive_align);
 692                 offset = offset.abi_align(align);
 693             }
 694
 695             debug!("Struct::new offset: {:?} field: {:?} {:?}", offset, field, field.size(dl));
 696             ret.offsets[*i as usize] = offset;
 697
 698             offset = offset.checked_add(field.size(dl), dl)
 699                            .map_or(Err(LayoutError::SizeOverflow(scapegoat)), Ok)?;
 700         }
 701
 702         if repr.align > 0 {
 703             let repr_align = repr.align as u64;
 704             ret.align = ret.align.max(Align::from_bytes(repr_align, repr_align).unwrap());
 705             debug!("Struct::new repr_align: {:?}", repr_align);
 706         }
 707
 708         debug!("Struct::new min_size: {:?}", offset);
 709         ret.min_size = offset;
 710
 711         // As stated above, inverse_memory_index holds field indices by increasing offset.
 712         // This makes it an already-sorted view of the offsets vec.
 713         // To invert it, consider:
 714         // If field 5 has offset 0, offsets[0] is 5, and memory_index[5] should be 0.
 715         // Field 5 would be the first element, so memory_index is i:
 716         // Note: if we didn't optimize, it's already right.
 717
 718         if optimize {
 719             ret.memory_index = vec![0; inverse_memory_index.len()];
 720
 721             for i in 0..inverse_memory_index.len() {
 722                 ret.memory_index[inverse_memory_index[i] as usize]  = i as u32;
 723             }
 724         } else {
 725             ret.memory_index = inverse_memory_index;
 726         }
 727
 728         Ok(ret)
 729     }
 730
 731     /// Get the size with trailing alignment padding.
 732     pub fn stride(&self) -> Size {
 733         self.min_size.abi_align(self.align)
 734     }
 735
 736     /// Determine whether a structure would be zero-sized, given its fields.
 737     fn would_be_zero_sized<I>(dl: &TargetDataLayout, fields: I)
 738                               -> Result<bool, LayoutError<'tcx>>
 739     where I: Iterator<Item=Result<&'a Layout, LayoutError<'tcx>>> {
 740         for field in fields {
 741             let field = field?;
 742             if field.is_unsized() || field.size(dl).bytes() > 0 {
 743                 return Ok(false);
 744             }
 745         }
 746         Ok(true)
 747     }
 748
 749     /// Get indices of the tys that made this struct by increasing offset.
 750     #[inline]
 751     pub fn field_index_by_increasing_offset<'b>(&'b self) -> impl iter::Iterator<Item=usize>+'b {
 752         let mut inverse_small = [0u8; 64];
 753         let mut inverse_big = vec![];
 754         let use_small = self.memory_index.len() <= inverse_small.len();
 755
 756         // We have to write this logic twice in order to keep the array small.
 757         if use_small {
 758             for i in 0..self.memory_index.len() {
 759                 inverse_small[self.memory_index[i] as usize] = i as u8;
 760             }
 761         } else {
 762             inverse_big = vec![0; self.memory_index.len()];
 763             for i in 0..self.memory_index.len() {
 764                 inverse_big[self.memory_index[i] as usize] = i as u32;
 765             }
 766         }
 767
 768         (0..self.memory_index.len()).map(move |i| {
 769             if use_small { inverse_small[i] as usize }
 770             else { inverse_big[i] as usize }
 771         })
 772     }
 773
 774     /// Find the path leading to a non-zero leaf field, starting from
 775     /// the given type and recursing through aggregates.
 776     /// The tuple is `(path, source_path)`,
 777     /// where `path` is in memory order and `source_path` in source order.
 778     // FIXME(eddyb) track value ranges and traverse already optimized enums.
 779     fn non_zero_field_in_type(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 780                               param_env: ty::ParamEnv<'tcx>,
 781                               ty: Ty<'tcx>)
 782                               -> Result<Option<(FieldPath, FieldPath)>, LayoutError<'tcx>> {
 783         match (ty.layout(tcx, param_env)?, &ty.sty) {
 784             (&Scalar { non_zero: true, .. }, _) |
 785             (&CEnum { non_zero: true, .. }, _) => Ok(Some((vec![], vec![]))),
 786             (&FatPointer { non_zero: true, .. }, _) => {
 787                 Ok(Some((vec![FAT_PTR_ADDR as u32], vec![FAT_PTR_ADDR as u32])))
 788             }
 789
 790             // Is this the NonZero lang item wrapping a pointer or integer type?
 791             (&Univariant { non_zero: true, .. }, &ty::TyAdt(def, substs)) => {
 792                 let fields = &def.struct_variant().fields;
 793                 assert_eq!(fields.len(), 1);
 794                 match *fields[0].ty(tcx, substs).layout(tcx, param_env)? {
 795                     // FIXME(eddyb) also allow floating-point types here.
 796                     Scalar { value: Int(_), non_zero: false } |
 797                     Scalar { value: Pointer, non_zero: false } => {
 798                         Ok(Some((vec![0], vec![0])))
 799                     }
 800                     FatPointer { non_zero: false, .. } => {
 801                         let tmp = vec![FAT_PTR_ADDR as u32, 0];
 802                         Ok(Some((tmp.clone(), tmp)))
 803                     }
 804                     _ => Ok(None)
 805                 }
 806             }
 807
 808             // Perhaps one of the fields of this struct is non-zero
 809             // let's recurse and find out
 810             (&Univariant { ref variant, .. }, &ty::TyAdt(def, substs)) if def.is_struct() => {
 811                 Struct::non_zero_field_paths(
 812                     tcx,
 813                     param_env,
 814                     def.struct_variant().fields.iter().map(|field| {
 815                         field.ty(tcx, substs)
 816                     }),
 817                     Some(&variant.memory_index[..]))
 818             }
 819
 820             // Perhaps one of the upvars of this closure is non-zero
 821             (&Univariant { ref variant, .. }, &ty::TyClosure(def, substs)) => {
 822                 let upvar_tys = substs.upvar_tys(def, tcx);
 823                 Struct::non_zero_field_paths(
 824                     tcx,
 825                     param_env,
 826                     upvar_tys,
 827                     Some(&variant.memory_index[..]))
 828             }
 829             // Can we use one of the fields in this tuple?
 830             (&Univariant { ref variant, .. }, &ty::TyTuple(tys, _)) => {
 831                 Struct::non_zero_field_paths(
 832                     tcx,
 833                     param_env,
 834                     tys.iter().cloned(),
 835                     Some(&variant.memory_index[..]))
 836             }
 837
 838             // Is this a fixed-size array of something non-zero
 839             // with at least one element?
 840             (_, &ty::TyArray(ety, mut count)) => {
 841                 if count.has_projections() {
 842                     count = tcx.normalize_associated_type_in_env(&count, param_env);
 843                     if count.has_projections() {
 844                         return Err(LayoutError::Unknown(ty));
 845                     }
 846                 }
 847                 if count.val.to_const_int().unwrap().to_u64().unwrap() != 0 {
 848                     Struct::non_zero_field_paths(
 849                         tcx,
 850                         param_env,
 851                         Some(ety).into_iter(),
 852                         None)
 853                 } else {
 854                     Ok(None)
 855                 }
 856             }
 857
 858             (_, &ty::TyProjection(_)) | (_, &ty::TyAnon(..)) => {
 859                 let normalized = tcx.normalize_associated_type_in_env(&ty, param_env);
 860                 if ty == normalized {
 861                     return Ok(None);
 862                 }
 863                 return Struct::non_zero_field_in_type(tcx, param_env, normalized);
 864             }
 865
 866             // Anything else is not a non-zero type.
 867             _ => Ok(None)
 868         }
 869     }
 870
 871     /// Find the path leading to a non-zero leaf field, starting from
 872     /// the given set of fields and recursing through aggregates.
 873     /// Returns Some((path, source_path)) on success.
 874     /// `path` is translated to memory order. `source_path` is not.
 875     fn non_zero_field_paths<I>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 876                                param_env: ty::ParamEnv<'tcx>,
 877                                fields: I,
 878                                permutation: Option<&[u32]>)
 879                                -> Result<Option<(FieldPath, FieldPath)>, LayoutError<'tcx>>
 880     where I: Iterator<Item=Ty<'tcx>> {
 881         for (i, ty) in fields.enumerate() {
 882             let r = Struct::non_zero_field_in_type(tcx, param_env, ty)?;
 883             if let Some((mut path, mut source_path)) = r {
 884                 source_path.push(i as u32);
 885                 let index = if let Some(p) = permutation {
 886                     p[i] as usize
 887                 } else {
 888                     i
 889                 };
 890                 path.push(index as u32);
 891                 return Ok(Some((path, source_path)));
 892             }
 893         }
 894         Ok(None)
 895     }
 896
 897     pub fn over_align(&self) -> Option<u32> {
 898         let align = self.align.abi();
 899         let primitive_align = self.primitive_align.abi();
 900         if align > primitive_align {
 901             Some(align as u32)
 902         } else {
 903             None
 904         }
 905     }
 906 }
 907
 908 /// An untagged union.
 909 #[derive(PartialEq, Eq, Hash, Debug)]
 910 pub struct Union {
 911     pub align: Align,
 912     pub primitive_align: Align,
 913
 914     pub min_size: Size,
 915
 916     /// If true, no alignment padding is used.
 917     pub packed: bool,
 918 }
 919
 920 impl<'a, 'tcx> Union {
 921     fn new(dl: &TargetDataLayout, repr: &ReprOptions) -> Union {
 922         if repr.packed() && repr.align > 0 {
 923             bug!("Union cannot be packed and aligned");
 924         }
 925
 926         let primitive_align = if repr.packed() {
 927             dl.i8_align
 928         } else {
 929             dl.aggregate_align
 930         };
 931
 932         let align = if repr.align > 0 {
 933             let repr_align = repr.align as u64;
 934             debug!("Union::new repr_align: {:?}", repr_align);
 935             primitive_align.max(Align::from_bytes(repr_align, repr_align).unwrap())
 936         } else {
 937             primitive_align
 938         };
 939
 940         Union {
 941             align,
 942             primitive_align,
 943             min_size: Size::from_bytes(0),
 944             packed: repr.packed(),
 945         }
 946     }
 947
 948     /// Extend the Struct with more fields.
 949     fn extend<I>(&mut self, dl: &TargetDataLayout,
 950                  fields: I,
 951                  scapegoat: Ty<'tcx>)
 952                  -> Result<(), LayoutError<'tcx>>
 953     where I: Iterator<Item=Result<&'a Layout, LayoutError<'tcx>>> {
 954         for (index, field) in fields.enumerate() {
 955             let field = field?;
 956             if field.is_unsized() {
 957                 bug!("Union::extend: field #{} of `{}` is unsized",
 958                      index, scapegoat);
 959             }
 960
 961             debug!("Union::extend field: {:?} {:?}", field, field.size(dl));
 962
 963             if !self.packed {
 964                 self.align = self.align.max(field.align(dl));
 965                 self.primitive_align = self.primitive_align.max(field.primitive_align(dl));
 966             }
 967             self.min_size = cmp::max(self.min_size, field.size(dl));
 968         }
 969
 970         debug!("Union::extend min-size: {:?}", self.min_size);
 971
 972         Ok(())
 973     }
 974
 975     /// Get the size with trailing alignment padding.
 976     pub fn stride(&self) -> Size {
 977         self.min_size.abi_align(self.align)
 978     }
 979
 980     pub fn over_align(&self) -> Option<u32> {
 981         let align = self.align.abi();
 982         let primitive_align = self.primitive_align.abi();
 983         if align > primitive_align {
 984             Some(align as u32)
 985         } else {
 986             None
 987         }
 988     }
 989 }
 990
 991 /// The first half of a fat pointer.
 992 /// - For a trait object, this is the address of the box.
 993 /// - For a slice, this is the base address.
 994 pub const FAT_PTR_ADDR: usize = 0;
 995
 996 /// The second half of a fat pointer.
 997 /// - For a trait object, this is the address of the vtable.
 998 /// - For a slice, this is the length.
 999 pub const FAT_PTR_EXTRA: usize = 1;
1000
1001 /// Type layout, from which size and alignment can be cheaply computed.
1002 /// For ADTs, it also includes field placement and enum optimizations.
1003 /// NOTE: Because Layout is interned, redundant information should be
1004 /// kept to a minimum, e.g. it includes no sub-component Ty or Layout.
1005 #[derive(Debug, PartialEq, Eq, Hash)]
1006 pub enum Layout {
1007     /// TyBool, TyChar, TyInt, TyUint, TyFloat, TyRawPtr, TyRef or TyFnPtr.
1008     Scalar {
1009         value: Primitive,
1010         // If true, the value cannot represent a bit pattern of all zeroes.
1011         non_zero: bool
1012     },
1013
1014     /// SIMD vectors, from structs marked with #[repr(simd)].
1015     Vector {
1016         element: Primitive,
1017         count: u64
1018     },
1019
1020     /// TyArray, TySlice or TyStr.
1021     Array {
1022         /// If true, the size is exact, otherwise it's only a lower bound.
1023         sized: bool,
1024         align: Align,
1025         primitive_align: Align,
1026         element_size: Size,
1027         count: u64
1028     },
1029
1030     /// TyRawPtr or TyRef with a !Sized pointee.
1031     FatPointer {
1032         metadata: Primitive,
1033         /// If true, the pointer cannot be null.
1034         non_zero: bool
1035     },
1036
1037     // Remaining variants are all ADTs such as structs, enums or tuples.
1038
1039     /// C-like enums; basically an integer.
1040     CEnum {
1041         discr: Integer,
1042         signed: bool,
1043         non_zero: bool,
1044         /// Inclusive discriminant range.
1045         /// If min > max, it represents min...u64::MAX followed by 0...max.
1046         // FIXME(eddyb) always use the shortest range, e.g. by finding
1047         // the largest space between two consecutive discriminants and
1048         // taking everything else as the (shortest) discriminant range.
1049         min: u64,
1050         max: u64
1051     },
1052
1053     /// Single-case enums, and structs/tuples.
1054     Univariant {
1055         variant: Struct,
1056         /// If true, the structure is NonZero.
1057         // FIXME(eddyb) use a newtype Layout kind for this.
1058         non_zero: bool
1059     },
1060
1061     /// Untagged unions.
1062     UntaggedUnion {
1063         variants: Union,
1064     },
1065
1066     /// General-case enums: for each case there is a struct, and they
1067     /// all start with a field for the discriminant.
1068     General {
1069         discr: Integer,
1070         variants: Vec<Struct>,
1071         size: Size,
1072         align: Align,
1073         primitive_align: Align,
1074     },
1075
1076     /// Two cases distinguished by a nullable pointer: the case with discriminant
1077     /// `nndiscr` must have single field which is known to be nonnull due to its type.
1078     /// The other case is known to be zero sized. Hence we represent the enum
1079     /// as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
1080     /// otherwise it indicates the other case.
1081     ///
1082     /// For example, `std::option::Option` instantiated at a safe pointer type
1083     /// is represented such that `None` is a null pointer and `Some` is the
1084     /// identity function.
1085     RawNullablePointer {
1086         nndiscr: u64,
1087         value: Primitive
1088     },
1089
1090     /// Two cases distinguished by a nullable pointer: the case with discriminant
1091     /// `nndiscr` is represented by the struct `nonnull`, where the `discrfield`th
1092     /// field is known to be nonnull due to its type; if that field is null, then
1093     /// it represents the other case, which is known to be zero sized.
1094     StructWrappedNullablePointer {
1095         nndiscr: u64,
1096         nonnull: Struct,
1097         /// N.B. There is a 0 at the start, for LLVM GEP through a pointer.
1098         discrfield: FieldPath,
1099         /// Like discrfield, but in source order. For debuginfo.
1100         discrfield_source: FieldPath
1101     }
1102 }
1103
1104 #[derive(Copy, Clone, Debug)]
1105 pub enum LayoutError<'tcx> {
1106     Unknown(Ty<'tcx>),
1107     SizeOverflow(Ty<'tcx>)
1108 }
1109
1110 impl<'tcx> fmt::Display for LayoutError<'tcx> {
1111     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1112         match *self {
1113             LayoutError::Unknown(ty) => {
1114                 write!(f, "the type `{:?}` has an unknown layout", ty)
1115             }
1116             LayoutError::SizeOverflow(ty) => {
1117                 write!(f, "the type `{:?}` is too big for the current architecture", ty)
1118             }
1119         }
1120     }
1121 }
1122
1123 impl<'a, 'tcx> Layout {
1124     pub fn compute_uncached(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1125                             param_env: ty::ParamEnv<'tcx>,
1126                             ty: Ty<'tcx>)
1127                             -> Result<&'tcx Layout, LayoutError<'tcx>> {
1128         let success = |layout| Ok(tcx.intern_layout(layout));
1129         let dl = &tcx.data_layout;
1130         assert!(!ty.has_infer_types());
1131
1132         let ptr_layout = |pointee: Ty<'tcx>| {
1133             let non_zero = !ty.is_unsafe_ptr();
1134             let pointee = tcx.normalize_associated_type_in_env(&pointee, param_env);
1135             if pointee.is_sized(tcx, param_env, DUMMY_SP) {
1136                 Ok(Scalar { value: Pointer, non_zero: non_zero })
1137             } else {
1138                 let unsized_part = tcx.struct_tail(pointee);
1139                 let meta = match unsized_part.sty {
1140                     ty::TySlice(_) | ty::TyStr => {
1141                         Int(dl.ptr_sized_integer())
1142                     }
1143                     ty::TyDynamic(..) => Pointer,
1144                     _ => return Err(LayoutError::Unknown(unsized_part))
1145                 };
1146                 Ok(FatPointer { metadata: meta, non_zero: non_zero })
1147             }
1148         };
1149
1150         let layout = match ty.sty {
1151             // Basic scalars.
1152             ty::TyBool => Scalar { value: Int(I1), non_zero: false },
1153             ty::TyChar => Scalar { value: Int(I32), non_zero: false },
1154             ty::TyInt(ity) => {
1155                 Scalar {
1156                     value: Int(Integer::from_attr(dl, attr::SignedInt(ity))),
1157                     non_zero: false
1158                 }
1159             }
1160             ty::TyUint(ity) => {
1161                 Scalar {
1162                     value: Int(Integer::from_attr(dl, attr::UnsignedInt(ity))),
1163                     non_zero: false
1164                 }
1165             }
1166             ty::TyFloat(FloatTy::F32) => Scalar { value: F32, non_zero: false },
1167             ty::TyFloat(FloatTy::F64) => Scalar { value: F64, non_zero: false },
1168             ty::TyFnPtr(_) => Scalar { value: Pointer, non_zero: true },
1169
1170             // The never type.
1171             ty::TyNever => Univariant {
1172                 variant: Struct::new(dl, &vec![], &ReprOptions::default(),
1173                   StructKind::AlwaysSizedUnivariant, ty)?,
1174                 non_zero: false
1175             },
1176
1177             // Potentially-fat pointers.
1178             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
1179             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1180                 ptr_layout(pointee)?
1181             }
1182             ty::TyAdt(def, _) if def.is_box() => {
1183                 ptr_layout(ty.boxed_ty())?
1184             }
1185
1186             // Arrays and slices.
1187             ty::TyArray(element, mut count) => {
1188                 if count.has_projections() {
1189                     count = tcx.normalize_associated_type_in_env(&count, param_env);
1190                     if count.has_projections() {
1191                         return Err(LayoutError::Unknown(ty));
1192                     }
1193                 }
1194
1195                 let element = element.layout(tcx, param_env)?;
1196                 let element_size = element.size(dl);
1197                 let count = count.val.to_const_int().unwrap().to_u64().unwrap();
1198                 if element_size.checked_mul(count, dl).is_none() {
1199                     return Err(LayoutError::SizeOverflow(ty));
1200                 }
1201                 Array {
1202                     sized: true,
1203                     align: element.align(dl),
1204                     primitive_align: element.primitive_align(dl),
1205                     element_size,
1206                     count,
1207                 }
1208             }
1209             ty::TySlice(element) => {
1210                 let element = element.layout(tcx, param_env)?;
1211                 Array {
1212                     sized: false,
1213                     align: element.align(dl),
1214                     primitive_align: element.primitive_align(dl),
1215                     element_size: element.size(dl),
1216                     count: 0
1217                 }
1218             }
1219             ty::TyStr => {
1220                 Array {
1221                     sized: false,
1222                     align: dl.i8_align,
1223                     primitive_align: dl.i8_align,
1224                     element_size: Size::from_bytes(1),
1225                     count: 0
1226                 }
1227             }
1228
1229             // Odd unit types.
1230             ty::TyFnDef(..) => {
1231                 Univariant {
1232                     variant: Struct::new(dl, &vec![],
1233                       &ReprOptions::default(), StructKind::AlwaysSizedUnivariant, ty)?,
1234                     non_zero: false
1235                 }
1236             }
1237             ty::TyDynamic(..) => {
1238                 let mut unit = Struct::new(dl, &vec![], &ReprOptions::default(),
1239                   StructKind::AlwaysSizedUnivariant, ty)?;
1240                 unit.sized = false;
1241                 Univariant { variant: unit, non_zero: false }
1242             }
1243
1244             // Tuples, generators and closures.
1245             ty::TyGenerator(def_id, ref substs, _) => {
1246                 let tys = substs.field_tys(def_id, tcx);
1247                 let st = Struct::new(dl,
1248                     &tys.map(|ty| ty.layout(tcx, param_env))
1249                       .collect::<Result<Vec<_>, _>>()?,
1250                     &ReprOptions::default(),
1251                     StructKind::AlwaysSizedUnivariant, ty)?;
1252                 Univariant { variant: st, non_zero: false }
1253             }
1254
1255             ty::TyClosure(def_id, ref substs) => {
1256                 let tys = substs.upvar_tys(def_id, tcx);
1257                 let st = Struct::new(dl,
1258                     &tys.map(|ty| ty.layout(tcx, param_env))
1259                       .collect::<Result<Vec<_>, _>>()?,
1260                     &ReprOptions::default(),
1261                     StructKind::AlwaysSizedUnivariant, ty)?;
1262                 Univariant { variant: st, non_zero: false }
1263             }
1264
1265             ty::TyTuple(tys, _) => {
1266                 let kind = if tys.len() == 0 {
1267                     StructKind::AlwaysSizedUnivariant
1268                 } else {
1269                     StructKind::MaybeUnsizedUnivariant
1270                 };
1271
1272                 let st = Struct::new(dl,
1273                     &tys.iter().map(|ty| ty.layout(tcx, param_env))
1274                       .collect::<Result<Vec<_>, _>>()?,
1275                     &ReprOptions::default(), kind, ty)?;
1276                 Univariant { variant: st, non_zero: false }
1277             }
1278
1279             // SIMD vector types.
1280             ty::TyAdt(def, ..) if def.repr.simd() => {
1281                 let element = ty.simd_type(tcx);
1282                 match *element.layout(tcx, param_env)? {
1283                     Scalar { value, .. } => {
1284                         return success(Vector {
1285                             element: value,
1286                             count: ty.simd_size(tcx) as u64
1287                         });
1288                     }
1289                     _ => {
1290                         tcx.sess.fatal(&format!("monomorphising SIMD type `{}` with \
1291                                                 a non-machine element type `{}`",
1292                                                 ty, element));
1293                     }
1294                 }
1295             }
1296
1297             // ADTs.
1298             ty::TyAdt(def, substs) => {
1299                 if def.variants.is_empty() {
1300                     // Uninhabitable; represent as unit
1301                     // (Typechecking will reject discriminant-sizing attrs.)
1302
1303                     return success(Univariant {
1304                         variant: Struct::new(dl, &vec![],
1305                           &def.repr, StructKind::AlwaysSizedUnivariant, ty)?,
1306                         non_zero: false
1307                     });
1308                 }
1309
1310                 if def.is_enum() && def.variants.iter().all(|v| v.fields.is_empty()) {
1311                     // All bodies empty -> intlike
1312                     let (mut min, mut max, mut non_zero) = (i64::max_value(),
1313                                                             i64::min_value(),
1314                                                             true);
1315                     for discr in def.discriminants(tcx) {
1316                         let x = discr.to_u128_unchecked() as i64;
1317                         if x == 0 { non_zero = false; }
1318                         if x < min { min = x; }
1319                         if x > max { max = x; }
1320                     }
1321
1322                     // FIXME: should handle i128? signed-value based impl is weird and hard to
1323                     // grok.
1324                     let (discr, signed) = Integer::repr_discr(tcx, ty, &def.repr, min, max);
1325                     return success(CEnum {
1326                         discr,
1327                         signed,
1328                         non_zero,
1329                         // FIXME: should be u128?
1330                         min: min as u64,
1331                         max: max as u64
1332                     });
1333                 }
1334
1335                 if !def.is_enum() || (def.variants.len() == 1 &&
1336                                       !def.repr.inhibit_enum_layout_opt()) {
1337                     // Struct, or union, or univariant enum equivalent to a struct.
1338                     // (Typechecking will reject discriminant-sizing attrs.)
1339
1340                     let kind = if def.is_enum() || def.variants[0].fields.len() == 0{
1341                         StructKind::AlwaysSizedUnivariant
1342                     } else {
1343                         let param_env = tcx.param_env(def.did);
1344                         let fields = &def.variants[0].fields;
1345                         let last_field = &fields[fields.len()-1];
1346                         let always_sized = tcx.type_of(last_field.did)
1347                           .is_sized(tcx, param_env, DUMMY_SP);
1348                         if !always_sized { StructKind::MaybeUnsizedUnivariant }
1349                         else { StructKind::AlwaysSizedUnivariant }
1350                     };
1351
1352                     let fields = def.variants[0].fields.iter().map(|field| {
1353                         field.ty(tcx, substs).layout(tcx, param_env)
1354                     }).collect::<Result<Vec<_>, _>>()?;
1355                     let layout = if def.is_union() {
1356                         let mut un = Union::new(dl, &def.repr);
1357                         un.extend(dl, fields.iter().map(|&f| Ok(f)), ty)?;
1358                         UntaggedUnion { variants: un }
1359                     } else {
1360                         let st = Struct::new(dl, &fields, &def.repr,
1361                           kind, ty)?;
1362                         let non_zero = Some(def.did) == tcx.lang_items().non_zero();
1363                         Univariant { variant: st, non_zero: non_zero }
1364                     };
1365                     return success(layout);
1366                 }
1367
1368                 // Since there's at least one
1369                 // non-empty body, explicit discriminants should have
1370                 // been rejected by a checker before this point.
1371                 for (i, v) in def.variants.iter().enumerate() {
1372                     if v.discr != ty::VariantDiscr::Relative(i) {
1373                         bug!("non-C-like enum {} with specified discriminants",
1374                             tcx.item_path_str(def.did));
1375                     }
1376                 }
1377
1378                 // Cache the substituted and normalized variant field types.
1379                 let variants = def.variants.iter().map(|v| {
1380                     v.fields.iter().map(|field| field.ty(tcx, substs)).collect::<Vec<_>>()
1381                 }).collect::<Vec<_>>();
1382
1383                 if variants.len() == 2 && !def.repr.inhibit_enum_layout_opt() {
1384                     // Nullable pointer optimization
1385                     for discr in 0..2 {
1386                         let other_fields = variants[1 - discr].iter().map(|ty| {
1387                             ty.layout(tcx, param_env)
1388                         });
1389                         if !Struct::would_be_zero_sized(dl, other_fields)? {
1390                             continue;
1391                         }
1392                         let paths = Struct::non_zero_field_paths(tcx,
1393                                                                  param_env,
1394                                                                  variants[discr].iter().cloned(),
1395                                                                  None)?;
1396                         let (mut path, mut path_source) = if let Some(p) = paths { p }
1397                           else { continue };
1398
1399                         // FIXME(eddyb) should take advantage of a newtype.
1400                         if path == &[0] && variants[discr].len() == 1 {
1401                             let value = match *variants[discr][0].layout(tcx, param_env)? {
1402                                 Scalar { value, .. } => value,
1403                                 CEnum { discr, .. } => Int(discr),
1404                                 _ => bug!("Layout::compute: `{}`'s non-zero \
1405                                            `{}` field not scalar?!",
1406                                            ty, variants[discr][0])
1407                             };
1408                             return success(RawNullablePointer {
1409                                 nndiscr: discr as u64,
1410                                 value,
1411                             });
1412                         }
1413
1414                         let st = Struct::new(dl,
1415                             &variants[discr].iter().map(|ty| ty.layout(tcx, param_env))
1416                               .collect::<Result<Vec<_>, _>>()?,
1417                             &def.repr, StructKind::AlwaysSizedUnivariant, ty)?;
1418
1419                         // We have to fix the last element of path here.
1420                         let mut i = *path.last().unwrap();
1421                         i = st.memory_index[i as usize];
1422                         *path.last_mut().unwrap() = i;
1423                         path.push(0); // For GEP through a pointer.
1424                         path.reverse();
1425                         path_source.push(0);
1426                         path_source.reverse();
1427
1428                         return success(StructWrappedNullablePointer {
1429                             nndiscr: discr as u64,
1430                             nonnull: st,
1431                             discrfield: path,
1432                             discrfield_source: path_source
1433                         });
1434                     }
1435                 }
1436
1437                 // The general case.
1438                 let discr_max = (variants.len() - 1) as i64;
1439                 assert!(discr_max >= 0);
1440                 let (min_ity, _) = Integer::repr_discr(tcx, ty, &def.repr, 0, discr_max);
1441                 let mut align = dl.aggregate_align;
1442                 let mut primitive_align = dl.aggregate_align;
1443                 let mut size = Size::from_bytes(0);
1444
1445                 // We're interested in the smallest alignment, so start large.
1446                 let mut start_align = Align::from_bytes(256, 256).unwrap();
1447
1448                 // Create the set of structs that represent each variant
1449                 // Use the minimum integer type we figured out above
1450                 let discr = Scalar { value: Int(min_ity), non_zero: false };
1451                 let mut variants = variants.into_iter().map(|fields| {
1452                     let mut fields = fields.into_iter().map(|field| {
1453                         field.layout(tcx, param_env)
1454                     }).collect::<Result<Vec<_>, _>>()?;
1455                     fields.insert(0, &discr);
1456                     let st = Struct::new(dl,
1457                         &fields,
1458                         &def.repr, StructKind::EnumVariant, ty)?;
1459                     // Find the first field we can't move later
1460                     // to make room for a larger discriminant.
1461                     // It is important to skip the first field.
1462                     for i in st.field_index_by_increasing_offset().skip(1) {
1463                         let field = fields[i];
1464                         let field_align = field.align(dl);
1465                         if field.size(dl).bytes() != 0 || field_align.abi() != 1 {
1466                             start_align = start_align.min(field_align);
1467                             break;
1468                         }
1469                     }
1470                     size = cmp::max(size, st.min_size);
1471                     align = align.max(st.align);
1472                     primitive_align = primitive_align.max(st.primitive_align);
1473                     Ok(st)
1474                 }).collect::<Result<Vec<_>, _>>()?;
1475
1476                 // Align the maximum variant size to the largest alignment.
1477                 size = size.abi_align(align);
1478
1479                 if size.bytes() >= dl.obj_size_bound() {
1480                     return Err(LayoutError::SizeOverflow(ty));
1481                 }
1482
1483                 let typeck_ity = Integer::from_attr(dl, def.repr.discr_type());
1484                 if typeck_ity < min_ity {
1485                     // It is a bug if Layout decided on a greater discriminant size than typeck for
1486                     // some reason at this point (based on values discriminant can take on). Mostly
1487                     // because this discriminant will be loaded, and then stored into variable of
1488                     // type calculated by typeck. Consider such case (a bug): typeck decided on
1489                     // byte-sized discriminant, but layout thinks we need a 16-bit to store all
1490                     // discriminant values. That would be a bug, because then, in trans, in order
1491                     // to store this 16-bit discriminant into 8-bit sized temporary some of the
1492                     // space necessary to represent would have to be discarded (or layout is wrong
1493                     // on thinking it needs 16 bits)
1494                     bug!("layout decided on a larger discriminant type ({:?}) than typeck ({:?})",
1495                          min_ity, typeck_ity);
1496                     // However, it is fine to make discr type however large (as an optimisation)
1497                     // after this point – we’ll just truncate the value we load in trans.
1498                 }
1499
1500                 // Check to see if we should use a different type for the
1501                 // discriminant. We can safely use a type with the same size
1502                 // as the alignment of the first field of each variant.
1503                 // We increase the size of the discriminant to avoid LLVM copying
1504                 // padding when it doesn't need to. This normally causes unaligned
1505                 // load/stores and excessive memcpy/memset operations. By using a
1506                 // bigger integer size, LLVM can be sure about it's contents and
1507                 // won't be so conservative.
1508
1509                 // Use the initial field alignment
1510                 let mut ity = Integer::for_abi_align(dl, start_align).unwrap_or(min_ity);
1511
1512                 // If the alignment is not larger than the chosen discriminant size,
1513                 // don't use the alignment as the final size.
1514                 if ity <= min_ity {
1515                     ity = min_ity;
1516                 } else {
1517                     // Patch up the variants' first few fields.
1518                     let old_ity_size = Int(min_ity).size(dl);
1519                     let new_ity_size = Int(ity).size(dl);
1520                     for variant in &mut variants {
1521                         for i in variant.offsets.iter_mut() {
1522                             // The first field is the discrimminant, at offset 0.
1523                             // These aren't in order, and we need to skip it.
1524                             if *i <= old_ity_size && *i > Size::from_bytes(0) {
1525                                 *i = new_ity_size;
1526                             }
1527                         }
1528                         // We might be making the struct larger.
1529                         if variant.min_size <= old_ity_size {
1530                             variant.min_size = new_ity_size;
1531                         }
1532                     }
1533                 }
1534
1535                 General {
1536                     discr: ity,
1537                     variants,
1538                     size,
1539                     align,
1540                     primitive_align,
1541                 }
1542             }
1543
1544             // Types with no meaningful known layout.
1545             ty::TyProjection(_) | ty::TyAnon(..) => {
1546                 let normalized = tcx.normalize_associated_type_in_env(&ty, param_env);
1547                 if ty == normalized {
1548                     return Err(LayoutError::Unknown(ty));
1549                 }
1550                 return normalized.layout(tcx, param_env);
1551             }
1552             ty::TyParam(_) => {
1553                 return Err(LayoutError::Unknown(ty));
1554             }
1555             ty::TyInfer(_) | ty::TyError => {
1556                 bug!("Layout::compute: unexpected type `{}`", ty)
1557             }
1558         };
1559
1560         success(layout)
1561     }
1562
1563     /// Returns true if the layout corresponds to an unsized type.
1564     pub fn is_unsized(&self) -> bool {
1565         match *self {
1566             Scalar {..} | Vector {..} | FatPointer {..} |
1567             CEnum {..} | UntaggedUnion {..} | General {..} |
1568             RawNullablePointer {..} |
1569             StructWrappedNullablePointer {..} => false,
1570
1571             Array { sized, .. } |
1572             Univariant { variant: Struct { sized, .. }, .. } => !sized
1573         }
1574     }
1575
1576     pub fn size<C: HasDataLayout>(&self, cx: C) -> Size {
1577         let dl = cx.data_layout();
1578
1579         match *self {
1580             Scalar { value, .. } | RawNullablePointer { value, .. } => {
1581                 value.size(dl)
1582             }
1583
1584             Vector { element, count } => {
1585                 let element_size = element.size(dl);
1586                 let vec_size = match element_size.checked_mul(count, dl) {
1587                     Some(size) => size,
1588                     None => bug!("Layout::size({:?}): {} * {} overflowed",
1589                                  self, element_size.bytes(), count)
1590                 };
1591                 vec_size.abi_align(self.align(dl))
1592             }
1593
1594             Array { element_size, count, .. } => {
1595                 match element_size.checked_mul(count, dl) {
1596                     Some(size) => size,
1597                     None => bug!("Layout::size({:?}): {} * {} overflowed",
1598                                  self, element_size.bytes(), count)
1599                 }
1600             }
1601
1602             FatPointer { metadata, .. } => {
1603                 // Effectively a (ptr, meta) tuple.
1604                 Pointer.size(dl).abi_align(metadata.align(dl))
1605                        .checked_add(metadata.size(dl), dl).unwrap()
1606                        .abi_align(self.align(dl))
1607             }
1608
1609             CEnum { discr, .. } => Int(discr).size(dl),
1610             General { size, .. } => size,
1611             UntaggedUnion { ref variants } => variants.stride(),
1612
1613             Univariant { ref variant, .. } |
1614             StructWrappedNullablePointer { nonnull: ref variant, .. } => {
1615                 variant.stride()
1616             }
1617         }
1618     }
1619
1620     pub fn align<C: HasDataLayout>(&self, cx: C) -> Align {
1621         let dl = cx.data_layout();
1622
1623         match *self {
1624             Scalar { value, .. } | RawNullablePointer { value, .. } => {
1625                 value.align(dl)
1626             }
1627
1628             Vector { element, count } => {
1629                 let elem_size = element.size(dl);
1630                 let vec_size = match elem_size.checked_mul(count, dl) {
1631                     Some(size) => size,
1632                     None => bug!("Layout::align({:?}): {} * {} overflowed",
1633                                  self, elem_size.bytes(), count)
1634                 };
1635                 for &(size, align) in &dl.vector_align {
1636                     if size == vec_size {
1637                         return align;
1638                     }
1639                 }
1640                 // Default to natural alignment, which is what LLVM does.
1641                 // That is, use the size, rounded up to a power of 2.
1642                 let align = vec_size.bytes().next_power_of_two();
1643                 Align::from_bytes(align, align).unwrap()
1644             }
1645
1646             FatPointer { metadata, .. } => {
1647                 // Effectively a (ptr, meta) tuple.
1648                 Pointer.align(dl).max(metadata.align(dl))
1649             }
1650
1651             CEnum { discr, .. } => Int(discr).align(dl),
1652             Array { align, .. } | General { align, .. } => align,
1653             UntaggedUnion { ref variants } => variants.align,
1654
1655             Univariant { ref variant, .. } |
1656             StructWrappedNullablePointer { nonnull: ref variant, .. } => {
1657                 variant.align
1658             }
1659         }
1660     }
1661
1662     /// Returns alignment before repr alignment is applied
1663     pub fn primitive_align(&self, dl: &TargetDataLayout) -> Align {
1664         match *self {
1665             Array { primitive_align, .. } | General { primitive_align, .. } => primitive_align,
1666             Univariant { ref variant, .. } |
1667             StructWrappedNullablePointer { nonnull: ref variant, .. } => {
1668                 variant.primitive_align
1669             },
1670
1671             _ => self.align(dl)
1672         }
1673     }
1674
1675     /// Returns repr alignment if it is greater than the primitive alignment.
1676     pub fn over_align(&self, dl: &TargetDataLayout) -> Option<u32> {
1677         let align = self.align(dl);
1678         let primitive_align = self.primitive_align(dl);
1679         if align.abi() > primitive_align.abi() {
1680             Some(align.abi() as u32)
1681         } else {
1682             None
1683         }
1684     }
1685
1686     pub fn field_offset<C: HasDataLayout>(&self,
1687                                           cx: C,
1688                                           i: usize,
1689                                           variant_index: Option<usize>)
1690                                           -> Size {
1691         let dl = cx.data_layout();
1692
1693         match *self {
1694             Scalar { .. } |
1695             CEnum { .. } |
1696             UntaggedUnion { .. } |
1697             RawNullablePointer { .. } => {
1698                 Size::from_bytes(0)
1699             }
1700
1701             Vector { element, count } => {
1702                 let element_size = element.size(dl);
1703                 let i = i as u64;
1704                 assert!(i < count);
1705                 Size::from_bytes(element_size.bytes() * count)
1706             }
1707
1708             Array { element_size, count, .. } => {
1709                 let i = i as u64;
1710                 assert!(i < count);
1711                 Size::from_bytes(element_size.bytes() * count)
1712             }
1713
1714             FatPointer { metadata, .. } => {
1715                 // Effectively a (ptr, meta) tuple.
1716                 assert!(i < 2);
1717                 if i == 0 {
1718                     Size::from_bytes(0)
1719                 } else {
1720                     Pointer.size(dl).abi_align(metadata.align(dl))
1721                 }
1722             }
1723
1724             Univariant { ref variant, .. } => variant.offsets[i],
1725
1726             General { ref variants, .. } => {
1727                 let v = variant_index.expect("variant index required");
1728                 variants[v].offsets[i + 1]
1729             }
1730
1731             StructWrappedNullablePointer { nndiscr, ref nonnull, .. } => {
1732                 if Some(nndiscr as usize) == variant_index {
1733                     nonnull.offsets[i]
1734                 } else {
1735                     Size::from_bytes(0)
1736                 }
1737             }
1738         }
1739     }
1740
1741     /// This is invoked by the `layout_raw` query to record the final
1742     /// layout of each type.
1743     #[inline]
1744     pub fn record_layout_for_printing(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1745                                       ty: Ty<'tcx>,
1746                                       param_env: ty::ParamEnv<'tcx>,
1747                                       layout: &Layout) {
1748         // If we are running with `-Zprint-type-sizes`, record layouts for
1749         // dumping later. Ignore layouts that are done with non-empty
1750         // environments or non-monomorphic layouts, as the user only wants
1751         // to see the stuff resulting from the final trans session.
1752         if
1753             !tcx.sess.opts.debugging_opts.print_type_sizes ||
1754             ty.has_param_types() ||
1755             ty.has_self_ty() ||
1756             !param_env.caller_bounds.is_empty()
1757         {
1758             return;
1759         }
1760
1761         Self::record_layout_for_printing_outlined(tcx, ty, param_env, layout)
1762     }
1763
1764     fn record_layout_for_printing_outlined(tcx: TyCtxt<'a, 'tcx, 'tcx>,
1765                                            ty: Ty<'tcx>,
1766                                            param_env: ty::ParamEnv<'tcx>,
1767                                            layout: &Layout) {
1768         // (delay format until we actually need it)
1769         let record = |kind, opt_discr_size, variants| {
1770             let type_desc = format!("{:?}", ty);
1771             let overall_size = layout.size(tcx);
1772             let align = layout.align(tcx);
1773             tcx.sess.code_stats.borrow_mut().record_type_size(kind,
1774                                                               type_desc,
1775                                                               align,
1776                                                               overall_size,
1777                                                               opt_discr_size,
1778                                                               variants);
1779         };
1780
1781         let (adt_def, substs) = match ty.sty {
1782             ty::TyAdt(ref adt_def, substs) => {
1783                 debug!("print-type-size t: `{:?}` process adt", ty);
1784                 (adt_def, substs)
1785             }
1786
1787             ty::TyClosure(..) => {
1788                 debug!("print-type-size t: `{:?}` record closure", ty);
1789                 record(DataTypeKind::Closure, None, vec![]);
1790                 return;
1791             }
1792
1793             _ => {
1794                 debug!("print-type-size t: `{:?}` skip non-nominal", ty);
1795                 return;
1796             }
1797         };
1798
1799         let adt_kind = adt_def.adt_kind();
1800
1801         let build_field_info = |(field_name, field_ty): (ast::Name, Ty<'tcx>), offset: &Size| {
1802             let layout = field_ty.layout(tcx, param_env);
1803             match layout {
1804                 Err(_) => bug!("no layout found for field {} type: `{:?}`", field_name, field_ty),
1805                 Ok(field_layout) => {
1806                     session::FieldInfo {
1807                         name: field_name.to_string(),
1808                         offset: offset.bytes(),
1809                         size: field_layout.size(tcx).bytes(),
1810                         align: field_layout.align(tcx).abi(),
1811                     }
1812                 }
1813             }
1814         };
1815
1816         let build_primitive_info = |name: ast::Name, value: &Primitive| {
1817             session::VariantInfo {
1818                 name: Some(name.to_string()),
1819                 kind: session::SizeKind::Exact,
1820                 align: value.align(tcx).abi(),
1821                 size: value.size(tcx).bytes(),
1822                 fields: vec![],
1823             }
1824         };
1825
1826         enum Fields<'a> {
1827             WithDiscrim(&'a Struct),
1828             NoDiscrim(&'a Struct),
1829         }
1830
1831         let build_variant_info = |n: Option<ast::Name>,
1832                                   flds: &[(ast::Name, Ty<'tcx>)],
1833                                   layout: Fields| {
1834             let (s, field_offsets) = match layout {
1835                 Fields::WithDiscrim(s) => (s, &s.offsets[1..]),
1836                 Fields::NoDiscrim(s) => (s, &s.offsets[0..]),
1837             };
1838             let field_info: Vec<_> =
1839                 flds.iter()
1840                     .zip(field_offsets.iter())
1841                     .map(|(&field_name_ty, offset)| build_field_info(field_name_ty, offset))
1842                     .collect();
1843
1844             session::VariantInfo {
1845                 name: n.map(|n|n.to_string()),
1846                 kind: if s.sized {
1847                     session::SizeKind::Exact
1848                 } else {
1849                     session::SizeKind::Min
1850                 },
1851                 align: s.align.abi(),
1852                 size: s.min_size.bytes(),
1853                 fields: field_info,
1854             }
1855         };
1856
1857         match *layout {
1858             Layout::StructWrappedNullablePointer { nonnull: ref variant_layout,
1859                                                    nndiscr,
1860                                                    discrfield: _,
1861                                                    discrfield_source: _ } => {
1862                 debug!("print-type-size t: `{:?}` adt struct-wrapped nullable nndiscr {} is {:?}",
1863                        ty, nndiscr, variant_layout);
1864                 let variant_def = &adt_def.variants[nndiscr as usize];
1865                 let fields: Vec<_> =
1866                     variant_def.fields.iter()
1867                                       .map(|field_def| (field_def.name, field_def.ty(tcx, substs)))
1868                                       .collect();
1869                 record(adt_kind.into(),
1870                        None,
1871                        vec![build_variant_info(Some(variant_def.name),
1872                                                &fields,
1873                                                Fields::NoDiscrim(variant_layout))]);
1874             }
1875             Layout::RawNullablePointer { nndiscr, value } => {
1876                 debug!("print-type-size t: `{:?}` adt raw nullable nndiscr {} is {:?}",
1877                        ty, nndiscr, value);
1878                 let variant_def = &adt_def.variants[nndiscr as usize];
1879                 record(adt_kind.into(), None,
1880                        vec![build_primitive_info(variant_def.name, &value)]);
1881             }
1882             Layout::Univariant { variant: ref variant_layout, non_zero: _ } => {
1883                 let variant_names = || {
1884                     adt_def.variants.iter().map(|v|format!("{}", v.name)).collect::<Vec<_>>()
1885                 };
1886                 debug!("print-type-size t: `{:?}` adt univariant {:?} variants: {:?}",
1887                        ty, variant_layout, variant_names());
1888                 assert!(adt_def.variants.len() <= 1,
1889                         "univariant with variants {:?}", variant_names());
1890                 if adt_def.variants.len() == 1 {
1891                     let variant_def = &adt_def.variants[0];
1892                     let fields: Vec<_> =
1893                         variant_def.fields.iter()
1894                                           .map(|f| (f.name, f.ty(tcx, substs)))
1895                                           .collect();
1896                     record(adt_kind.into(),
1897                            None,
1898                            vec![build_variant_info(Some(variant_def.name),
1899                                                    &fields,
1900                                                    Fields::NoDiscrim(variant_layout))]);
1901                 } else {
1902                     // (This case arises for *empty* enums; so give it
1903                     // zero variants.)
1904                     record(adt_kind.into(), None, vec![]);
1905                 }
1906             }
1907
1908             Layout::General { ref variants, discr, .. } => {
1909                 debug!("print-type-size t: `{:?}` adt general variants def {} layouts {} {:?}",
1910                        ty, adt_def.variants.len(), variants.len(), variants);
1911                 let variant_infos: Vec<_> =
1912                     adt_def.variants.iter()
1913                                     .zip(variants.iter())
1914                                     .map(|(variant_def, variant_layout)| {
1915                                         let fields: Vec<_> =
1916                                             variant_def.fields
1917                                                        .iter()
1918                                                        .map(|f| (f.name, f.ty(tcx, substs)))
1919                                                        .collect();
1920                                         build_variant_info(Some(variant_def.name),
1921                                                            &fields,
1922                                                            Fields::WithDiscrim(variant_layout))
1923                                     })
1924                                     .collect();
1925                 record(adt_kind.into(), Some(discr.size()), variant_infos);
1926             }
1927
1928             Layout::UntaggedUnion { ref variants } => {
1929                 debug!("print-type-size t: `{:?}` adt union variants {:?}",
1930                        ty, variants);
1931                 // layout does not currently store info about each
1932                 // variant...
1933                 record(adt_kind.into(), None, Vec::new());
1934             }
1935
1936             Layout::CEnum { discr, .. } => {
1937                 debug!("print-type-size t: `{:?}` adt c-like enum", ty);
1938                 let variant_infos: Vec<_> =
1939                     adt_def.variants.iter()
1940                                     .map(|variant_def| {
1941                                         build_primitive_info(variant_def.name,
1942                                                              &Primitive::Int(discr))
1943                                     })
1944                                     .collect();
1945                 record(adt_kind.into(), Some(discr.size()), variant_infos);
1946             }
1947
1948             // other cases provide little interesting (i.e. adjustable
1949             // via representation tweaks) size info beyond total size.
1950             Layout::Scalar { .. } |
1951             Layout::Vector { .. } |
1952             Layout::Array { .. } |
1953             Layout::FatPointer { .. } => {
1954                 debug!("print-type-size t: `{:?}` adt other", ty);
1955                 record(adt_kind.into(), None, Vec::new())
1956             }
1957         }
1958     }
1959 }
1960
1961 /// Type size "skeleton", i.e. the only information determining a type's size.
1962 /// While this is conservative, (aside from constant sizes, only pointers,
1963 /// newtypes thereof and null pointer optimized enums are allowed), it is
1964 /// enough to statically check common usecases of transmute.
1965 #[derive(Copy, Clone, Debug)]
1966 pub enum SizeSkeleton<'tcx> {
1967     /// Any statically computable Layout.
1968     Known(Size),
1969
1970     /// A potentially-fat pointer.
1971     Pointer {
1972         /// If true, this pointer is never null.
1973         non_zero: bool,
1974         /// The type which determines the unsized metadata, if any,
1975         /// of this pointer. Either a type parameter or a projection
1976         /// depending on one, with regions erased.
1977         tail: Ty<'tcx>
1978     }
1979 }
1980
1981 impl<'a, 'tcx> SizeSkeleton<'tcx> {
1982     pub fn compute(ty: Ty<'tcx>,
1983                    tcx: TyCtxt<'a, 'tcx, 'tcx>,
1984                    param_env: ty::ParamEnv<'tcx>)
1985                    -> Result<SizeSkeleton<'tcx>, LayoutError<'tcx>> {
1986         assert!(!ty.has_infer_types());
1987
1988         // First try computing a static layout.
1989         let err = match ty.layout(tcx, param_env) {
1990             Ok(layout) => {
1991                 return Ok(SizeSkeleton::Known(layout.size(tcx)));
1992             }
1993             Err(err) => err
1994         };
1995
1996         let ptr_skeleton = |pointee: Ty<'tcx>| {
1997             let non_zero = !ty.is_unsafe_ptr();
1998             let tail = tcx.struct_tail(pointee);
1999             match tail.sty {
2000                 ty::TyParam(_) | ty::TyProjection(_) => {
2001                     assert!(tail.has_param_types() || tail.has_self_ty());
2002                     Ok(SizeSkeleton::Pointer {
2003                         non_zero,
2004                         tail: tcx.erase_regions(&tail)
2005                     })
2006                 }
2007                 _ => {
2008                     bug!("SizeSkeleton::compute({}): layout errored ({}), yet \
2009                             tail `{}` is not a type parameter or a projection",
2010                             ty, err, tail)
2011                 }
2012             }
2013         };
2014
2015         match ty.sty {
2016             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
2017             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
2018                 ptr_skeleton(pointee)
2019             }
2020             ty::TyAdt(def, _) if def.is_box() => {
2021                 ptr_skeleton(ty.boxed_ty())
2022             }
2023
2024             ty::TyAdt(def, substs) => {
2025                 // Only newtypes and enums w/ nullable pointer optimization.
2026                 if def.is_union() || def.variants.is_empty() || def.variants.len() > 2 {
2027                     return Err(err);
2028                 }
2029
2030                 // Get a zero-sized variant or a pointer newtype.
2031                 let zero_or_ptr_variant = |i: usize| {
2032                     let fields = def.variants[i].fields.iter().map(|field| {
2033                         SizeSkeleton::compute(field.ty(tcx, substs), tcx, param_env)
2034                     });
2035                     let mut ptr = None;
2036                     for field in fields {
2037                         let field = field?;
2038                         match field {
2039                             SizeSkeleton::Known(size) => {
2040                                 if size.bytes() > 0 {
2041                                     return Err(err);
2042                                 }
2043                             }
2044                             SizeSkeleton::Pointer {..} => {
2045                                 if ptr.is_some() {
2046                                     return Err(err);
2047                                 }
2048                                 ptr = Some(field);
2049                             }
2050                         }
2051                     }
2052                     Ok(ptr)
2053                 };
2054
2055                 let v0 = zero_or_ptr_variant(0)?;
2056                 // Newtype.
2057                 if def.variants.len() == 1 {
2058                     if let Some(SizeSkeleton::Pointer { non_zero, tail }) = v0 {
2059                         return Ok(SizeSkeleton::Pointer {
2060                             non_zero: non_zero ||
2061                                 Some(def.did) == tcx.lang_items().non_zero(),
2062                             tail,
2063                         });
2064                     } else {
2065                         return Err(err);
2066                     }
2067                 }
2068
2069                 let v1 = zero_or_ptr_variant(1)?;
2070                 // Nullable pointer enum optimization.
2071                 match (v0, v1) {
2072                     (Some(SizeSkeleton::Pointer { non_zero: true, tail }), None) |
2073                     (None, Some(SizeSkeleton::Pointer { non_zero: true, tail })) => {
2074                         Ok(SizeSkeleton::Pointer {
2075                             non_zero: false,
2076                             tail,
2077                         })
2078                     }
2079                     _ => Err(err)
2080                 }
2081             }
2082
2083             ty::TyProjection(_) | ty::TyAnon(..) => {
2084                 let normalized = tcx.normalize_associated_type_in_env(&ty, param_env);
2085                 if ty == normalized {
2086                     Err(err)
2087                 } else {
2088                     SizeSkeleton::compute(normalized, tcx, param_env)
2089                 }
2090             }
2091
2092             _ => Err(err)
2093         }
2094     }
2095
2096     pub fn same_size(self, other: SizeSkeleton) -> bool {
2097         match (self, other) {
2098             (SizeSkeleton::Known(a), SizeSkeleton::Known(b)) => a == b,
2099             (SizeSkeleton::Pointer { tail: a, .. },
2100              SizeSkeleton::Pointer { tail: b, .. }) => a == b,
2101             _ => false
2102         }
2103     }
2104 }
2105
2106 /// A pair of a type and its layout. Implements various
2107 /// type traversal APIs (e.g. recursing into fields).
2108 #[derive(Copy, Clone, Debug)]
2109 pub struct TyLayout<'tcx> {
2110     pub ty: Ty<'tcx>,
2111     pub layout: &'tcx Layout,
2112     pub variant_index: Option<usize>,
2113 }
2114
2115 impl<'tcx> Deref for TyLayout<'tcx> {
2116     type Target = Layout;
2117     fn deref(&self) -> &Layout {
2118         self.layout
2119     }
2120 }
2121
2122 pub trait LayoutTyper<'tcx>: HasDataLayout {
2123     type TyLayout;
2124
2125     fn tcx<'a>(&'a self) -> TyCtxt<'a, 'tcx, 'tcx>;
2126     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout;
2127     fn normalize_projections(self, ty: Ty<'tcx>) -> Ty<'tcx>;
2128 }
2129
2130 /// Combines a tcx with the parameter environment so that you can
2131 /// compute layout operations.
2132 #[derive(Copy, Clone)]
2133 pub struct LayoutCx<'a, 'tcx: 'a> {
2134     tcx: TyCtxt<'a, 'tcx, 'tcx>,
2135     param_env: ty::ParamEnv<'tcx>,
2136 }
2137
2138 impl<'a, 'tcx> LayoutCx<'a, 'tcx> {
2139     pub fn new(tcx: TyCtxt<'a, 'tcx, 'tcx>, param_env: ty::ParamEnv<'tcx>) -> Self {
2140         LayoutCx { tcx, param_env }
2141     }
2142 }
2143
2144 impl<'a, 'tcx> HasDataLayout for LayoutCx<'a, 'tcx> {
2145     fn data_layout(&self) -> &TargetDataLayout {
2146         &self.tcx.data_layout
2147     }
2148 }
2149
2150 impl<'a, 'tcx> LayoutTyper<'tcx> for LayoutCx<'a, 'tcx> {
2151     type TyLayout = Result<TyLayout<'tcx>, LayoutError<'tcx>>;
2152
2153     fn tcx<'b>(&'b self) -> TyCtxt<'b, 'tcx, 'tcx> {
2154         self.tcx
2155     }
2156
2157     fn layout_of(self, ty: Ty<'tcx>) -> Self::TyLayout {
2158         let ty = self.normalize_projections(ty);
2159
2160         Ok(TyLayout {
2161             ty,
2162             layout: ty.layout(self.tcx, self.param_env)?,
2163             variant_index: None
2164         })
2165     }
2166
2167     fn normalize_projections(self, ty: Ty<'tcx>) -> Ty<'tcx> {
2168         self.tcx.normalize_associated_type_in_env(&ty, self.param_env)
2169     }
2170 }
2171
2172 impl<'a, 'tcx> TyLayout<'tcx> {
2173     pub fn for_variant(&self, variant_index: usize) -> Self {
2174         TyLayout {
2175             variant_index: Some(variant_index),
2176             ..*self
2177         }
2178     }
2179
2180     pub fn field_offset<C: HasDataLayout>(&self, cx: C, i: usize) -> Size {
2181         self.layout.field_offset(cx, i, self.variant_index)
2182     }
2183
2184     pub fn field_count(&self) -> usize {
2185         // Handle enum/union through the type rather than Layout.
2186         if let ty::TyAdt(def, _) = self.ty.sty {
2187             let v = self.variant_index.unwrap_or(0);
2188             if def.variants.is_empty() {
2189                 assert_eq!(v, 0);
2190                 return 0;
2191             } else {
2192                 return def.variants[v].fields.len();
2193             }
2194         }
2195
2196         match *self.layout {
2197             Scalar { .. } => {
2198                 bug!("TyLayout::field_count({:?}): not applicable", self)
2199             }
2200
2201             // Handled above (the TyAdt case).
2202             CEnum { .. } |
2203             General { .. } |
2204             UntaggedUnion { .. } |
2205             RawNullablePointer { .. } |
2206             StructWrappedNullablePointer { .. } => bug!(),
2207
2208             FatPointer { .. } => 2,
2209
2210             Vector { count, .. } |
2211             Array { count, .. } => {
2212                 let usize_count = count as usize;
2213                 assert_eq!(usize_count as u64, count);
2214                 usize_count
2215             }
2216
2217             Univariant { ref variant, .. } => variant.offsets.len(),
2218         }
2219     }
2220
2221     pub fn field_type<C: LayoutTyper<'tcx>>(&self, cx: C, i: usize) -> Ty<'tcx> {
2222         let tcx = cx.tcx();
2223
2224         let ptr_field_type = |pointee: Ty<'tcx>| {
2225             assert!(i < 2);
2226             let slice = |element: Ty<'tcx>| {
2227                 if i == 0 {
2228                     tcx.mk_mut_ptr(element)
2229                 } else {
2230                     tcx.types.usize
2231                 }
2232             };
2233             match tcx.struct_tail(pointee).sty {
2234                 ty::TySlice(element) => slice(element),
2235                 ty::TyStr => slice(tcx.types.u8),
2236                 ty::TyDynamic(..) => tcx.mk_mut_ptr(tcx.mk_nil()),
2237                 _ => bug!("TyLayout::field_type({:?}): not applicable", self)
2238             }
2239         };
2240
2241         match self.ty.sty {
2242             ty::TyBool |
2243             ty::TyChar |
2244             ty::TyInt(_) |
2245             ty::TyUint(_) |
2246             ty::TyFloat(_) |
2247             ty::TyFnPtr(_) |
2248             ty::TyNever |
2249             ty::TyFnDef(..) |
2250             ty::TyDynamic(..) => {
2251                 bug!("TyLayout::field_type({:?}): not applicable", self)
2252             }
2253
2254             // Potentially-fat pointers.
2255             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
2256             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
2257                 ptr_field_type(pointee)
2258             }
2259             ty::TyAdt(def, _) if def.is_box() => {
2260                 ptr_field_type(self.ty.boxed_ty())
2261             }
2262
2263             // Arrays and slices.
2264             ty::TyArray(element, _) |
2265             ty::TySlice(element) => element,
2266             ty::TyStr => tcx.types.u8,
2267
2268             // Tuples, generators and closures.
2269             ty::TyClosure(def_id, ref substs) => {
2270                 substs.upvar_tys(def_id, tcx).nth(i).unwrap()
2271             }
2272
2273             ty::TyGenerator(def_id, ref substs, _) => {
2274                 substs.field_tys(def_id, tcx).nth(i).unwrap()
2275             }
2276
2277             ty::TyTuple(tys, _) => tys[i],
2278
2279             // SIMD vector types.
2280             ty::TyAdt(def, ..) if def.repr.simd() => {
2281                 self.ty.simd_type(tcx)
2282             }
2283
2284             // ADTs.
2285             ty::TyAdt(def, substs) => {
2286                 def.variants[self.variant_index.unwrap_or(0)].fields[i].ty(tcx, substs)
2287             }
2288
2289             ty::TyProjection(_) | ty::TyAnon(..) | ty::TyParam(_) |
2290             ty::TyInfer(_) | ty::TyError => {
2291                 bug!("TyLayout::field_type: unexpected type `{}`", self.ty)
2292             }
2293         }
2294     }
2295
2296     pub fn field<C: LayoutTyper<'tcx>>(&self,
2297                                        cx: C,
2298                                        i: usize)
2299                                        -> C::TyLayout {
2300         cx.layout_of(cx.normalize_projections(self.field_type(cx, i)))
2301     }
2302 }