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 infer::InferCtxt;
  16 use session::Session;
  17 use traits;
  18 use ty::{self, Ty, TyCtxt, TypeFoldable, ReprOptions};
  19
  20 use syntax::ast::{FloatTy, IntTy, UintTy};
  21 use syntax::attr;
  22 use syntax_pos::DUMMY_SP;
  23 use rustc_const_math::ConstInt;
  24
  25 use std::cmp;
  26 use std::fmt;
  27 use std::i64;
  28 use std::iter;
  29
  30 /// Parsed [Data layout](http://llvm.org/docs/LangRef.html#data-layout)
  31 /// for a target, which contains everything needed to compute layouts.
  32 pub struct TargetDataLayout {
  33     pub endian: Endian,
  34     pub i1_align: Align,
  35     pub i8_align: Align,
  36     pub i16_align: Align,
  37     pub i32_align: Align,
  38     pub i64_align: Align,
  39     pub i128_align: Align,
  40     pub f32_align: Align,
  41     pub f64_align: Align,
  42     pub pointer_size: Size,
  43     pub pointer_align: Align,
  44     pub aggregate_align: Align,
  45
  46     /// Alignments for vector types.
  47     pub vector_align: Vec<(Size, Align)>
  48 }
  49
  50 impl Default for TargetDataLayout {
  51     /// Creates an instance of `TargetDataLayout`.
  52     fn default() -> TargetDataLayout {
  53         TargetDataLayout {
  54             endian: Endian::Big,
  55             i1_align: Align::from_bits(8, 8).unwrap(),
  56             i8_align: Align::from_bits(8, 8).unwrap(),
  57             i16_align: Align::from_bits(16, 16).unwrap(),
  58             i32_align: Align::from_bits(32, 32).unwrap(),
  59             i64_align: Align::from_bits(32, 64).unwrap(),
  60             i128_align: Align::from_bits(32, 64).unwrap(),
  61             f32_align: Align::from_bits(32, 32).unwrap(),
  62             f64_align: Align::from_bits(64, 64).unwrap(),
  63             pointer_size: Size::from_bits(64),
  64             pointer_align: Align::from_bits(64, 64).unwrap(),
  65             aggregate_align: Align::from_bits(0, 64).unwrap(),
  66             vector_align: vec![
  67                 (Size::from_bits(64), Align::from_bits(64, 64).unwrap()),
  68                 (Size::from_bits(128), Align::from_bits(128, 128).unwrap())
  69             ]
  70         }
  71     }
  72 }
  73
  74 impl TargetDataLayout {
  75     pub fn parse(sess: &Session) -> TargetDataLayout {
  76         // Parse a bit count from a string.
  77         let parse_bits = |s: &str, kind: &str, cause: &str| {
  78             s.parse::<u64>().unwrap_or_else(|err| {
  79                 sess.err(&format!("invalid {} `{}` for `{}` in \"data-layout\": {}",
  80                                   kind, s, cause, err));
  81                 0
  82             })
  83         };
  84
  85         // Parse a size string.
  86         let size = |s: &str, cause: &str| {
  87             Size::from_bits(parse_bits(s, "size", cause))
  88         };
  89
  90         // Parse an alignment string.
  91         let align = |s: &[&str], cause: &str| {
  92             if s.is_empty() {
  93                 sess.err(&format!("missing alignment for `{}` in \"data-layout\"", cause));
  94             }
  95             let abi = parse_bits(s[0], "alignment", cause);
  96             let pref = s.get(1).map_or(abi, |pref| parse_bits(pref, "alignment", cause));
  97             Align::from_bits(abi, pref).unwrap_or_else(|err| {
  98                 sess.err(&format!("invalid alignment for `{}` in \"data-layout\": {}",
  99                                   cause, err));
 100                 Align::from_bits(8, 8).unwrap()
 101             })
 102         };
 103
 104         let mut dl = TargetDataLayout::default();
 105         let mut i128_align_src = 64;
 106         for spec in sess.target.target.data_layout.split("-") {
 107             match &spec.split(":").collect::<Vec<_>>()[..] {
 108                 &["e"] => dl.endian = Endian::Little,
 109                 &["E"] => dl.endian = Endian::Big,
 110                 &["a", ref a..] => dl.aggregate_align = align(a, "a"),
 111                 &["f32", ref a..] => dl.f32_align = align(a, "f32"),
 112                 &["f64", ref a..] => dl.f64_align = align(a, "f64"),
 113                 &[p @ "p", s, ref a..] | &[p @ "p0", s, ref a..] => {
 114                     dl.pointer_size = size(s, p);
 115                     dl.pointer_align = align(a, p);
 116                 }
 117                 &[s, ref a..] if s.starts_with("i") => {
 118                     let bits = match s[1..].parse::<u64>() {
 119                         Ok(bits) => bits,
 120                         Err(_) => {
 121                             size(&s[1..], "i"); // For the user error.
 122                             continue;
 123                         }
 124                     };
 125                     let a = align(a, s);
 126                     match bits {
 127                         1 => dl.i1_align = a,
 128                         8 => dl.i8_align = a,
 129                         16 => dl.i16_align = a,
 130                         32 => dl.i32_align = a,
 131                         64 => dl.i64_align = a,
 132                         _ => {}
 133                     }
 134                     if bits >= i128_align_src && bits <= 128 {
 135                         // Default alignment for i128 is decided by taking the alignment of
 136                         // largest-sized i{64...128}.
 137                         i128_align_src = bits;
 138                         dl.i128_align = a;
 139                     }
 140                 }
 141                 &[s, ref a..] if s.starts_with("v") => {
 142                     let v_size = size(&s[1..], "v");
 143                     let a = align(a, s);
 144                     if let Some(v) = dl.vector_align.iter_mut().find(|v| v.0 == v_size) {
 145                         v.1 = a;
 146                         continue;
 147                     }
 148                     // No existing entry, add a new one.
 149                     dl.vector_align.push((v_size, a));
 150                 }
 151                 _ => {} // Ignore everything else.
 152             }
 153         }
 154
 155         // Perform consistency checks against the Target information.
 156         let endian_str = match dl.endian {
 157             Endian::Little => "little",
 158             Endian::Big => "big"
 159         };
 160         if endian_str != sess.target.target.target_endian {
 161             sess.err(&format!("inconsistent target specification: \"data-layout\" claims \
 162                                architecture is {}-endian, while \"target-endian\" is `{}`",
 163                               endian_str, sess.target.target.target_endian));
 164         }
 165
 166         if dl.pointer_size.bits().to_string() != sess.target.target.target_pointer_width {
 167             sess.err(&format!("inconsistent target specification: \"data-layout\" claims \
 168                                pointers are {}-bit, while \"target-pointer-width\" is `{}`",
 169                               dl.pointer_size.bits(), sess.target.target.target_pointer_width));
 170         }
 171
 172         dl
 173     }
 174
 175     /// Return exclusive upper bound on object size.
 176     ///
 177     /// The theoretical maximum object size is defined as the maximum positive `isize` value.
 178     /// This ensures that the `offset` semantics remain well-defined by allowing it to correctly
 179     /// index every address within an object along with one byte past the end, along with allowing
 180     /// `isize` to store the difference between any two pointers into an object.
 181     ///
 182     /// The upper bound on 64-bit currently needs to be lower because LLVM uses a 64-bit integer
 183     /// to represent object size in bits. It would need to be 1 << 61 to account for this, but is
 184     /// currently conservatively bounded to 1 << 47 as that is enough to cover the current usable
 185     /// address space on 64-bit ARMv8 and x86_64.
 186     pub fn obj_size_bound(&self) -> u64 {
 187         match self.pointer_size.bits() {
 188             16 => 1 << 15,
 189             32 => 1 << 31,
 190             64 => 1 << 47,
 191             bits => bug!("obj_size_bound: unknown pointer bit size {}", bits)
 192         }
 193     }
 194
 195     pub fn ptr_sized_integer(&self) -> Integer {
 196         match self.pointer_size.bits() {
 197             16 => I16,
 198             32 => I32,
 199             64 => I64,
 200             bits => bug!("ptr_sized_integer: unknown pointer bit size {}", bits)
 201         }
 202     }
 203 }
 204
 205 /// Endianness of the target, which must match cfg(target-endian).
 206 #[derive(Copy, Clone)]
 207 pub enum Endian {
 208     Little,
 209     Big
 210 }
 211
 212 /// Size of a type in bytes.
 213 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 214 pub struct Size {
 215     raw: u64
 216 }
 217
 218 impl Size {
 219     pub fn from_bits(bits: u64) -> Size {
 220         Size::from_bytes((bits + 7) / 8)
 221     }
 222
 223     pub fn from_bytes(bytes: u64) -> Size {
 224         if bytes >= (1 << 61) {
 225             bug!("Size::from_bytes: {} bytes in bits doesn't fit in u64", bytes)
 226         }
 227         Size {
 228             raw: bytes
 229         }
 230     }
 231
 232     pub fn bytes(self) -> u64 {
 233         self.raw
 234     }
 235
 236     pub fn bits(self) -> u64 {
 237         self.bytes() * 8
 238     }
 239
 240     pub fn abi_align(self, align: Align) -> Size {
 241         let mask = align.abi() - 1;
 242         Size::from_bytes((self.bytes() + mask) & !mask)
 243     }
 244
 245     pub fn checked_add(self, offset: Size, dl: &TargetDataLayout) -> Option<Size> {
 246         // Each Size is less than dl.obj_size_bound(), so the sum is
 247         // also less than 1 << 62 (and therefore can't overflow).
 248         let bytes = self.bytes() + offset.bytes();
 249
 250         if bytes < dl.obj_size_bound() {
 251             Some(Size::from_bytes(bytes))
 252         } else {
 253             None
 254         }
 255     }
 256
 257     pub fn checked_mul(self, count: u64, dl: &TargetDataLayout) -> Option<Size> {
 258         // Each Size is less than dl.obj_size_bound(), so the sum is
 259         // also less than 1 << 62 (and therefore can't overflow).
 260         match self.bytes().checked_mul(count) {
 261             Some(bytes) if bytes < dl.obj_size_bound() => {
 262                 Some(Size::from_bytes(bytes))
 263             }
 264             _ => None
 265         }
 266     }
 267 }
 268
 269 /// Alignment of a type in bytes, both ABI-mandated and preferred.
 270 /// Since alignments are always powers of 2, we can pack both in one byte,
 271 /// giving each a nibble (4 bits) for a maximum alignment of 2^15 = 32768.
 272 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 273 pub struct Align {
 274     raw: u8
 275 }
 276
 277 impl Align {
 278     pub fn from_bits(abi: u64, pref: u64) -> Result<Align, String> {
 279         Align::from_bytes((abi + 7) / 8, (pref + 7) / 8)
 280     }
 281
 282     pub fn from_bytes(abi: u64, pref: u64) -> Result<Align, String> {
 283         let pack = |align: u64| {
 284             // Treat an alignment of 0 bytes like 1-byte alignment.
 285             if align == 0 {
 286                 return Ok(0);
 287             }
 288
 289             let mut bytes = align;
 290             let mut pow: u8 = 0;
 291             while (bytes & 1) == 0 {
 292                 pow += 1;
 293                 bytes >>= 1;
 294             }
 295             if bytes != 1 {
 296                 Err(format!("`{}` is not a power of 2", align))
 297             } else if pow > 0x0f {
 298                 Err(format!("`{}` is too large", align))
 299             } else {
 300                 Ok(pow)
 301             }
 302         };
 303
 304         Ok(Align {
 305             raw: pack(abi)? | (pack(pref)? << 4)
 306         })
 307     }
 308
 309     pub fn abi(self) -> u64 {
 310         1 << (self.raw & 0xf)
 311     }
 312
 313     pub fn pref(self) -> u64 {
 314         1 << (self.raw >> 4)
 315     }
 316
 317     pub fn min(self, other: Align) -> Align {
 318         let abi = cmp::min(self.raw & 0x0f, other.raw & 0x0f);
 319         let pref = cmp::min(self.raw & 0xf0, other.raw & 0xf0);
 320         Align {
 321             raw: abi | pref
 322         }
 323     }
 324
 325     pub fn max(self, other: Align) -> Align {
 326         let abi = cmp::max(self.raw & 0x0f, other.raw & 0x0f);
 327         let pref = cmp::max(self.raw & 0xf0, other.raw & 0xf0);
 328         Align {
 329             raw: abi | pref
 330         }
 331     }
 332 }
 333
 334 /// Integers, also used for enum discriminants.
 335 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
 336 pub enum Integer {
 337     I1,
 338     I8,
 339     I16,
 340     I32,
 341     I64,
 342     I128,
 343 }
 344
 345 impl Integer {
 346     pub fn size(&self) -> Size {
 347         match *self {
 348             I1 => Size::from_bits(1),
 349             I8 => Size::from_bytes(1),
 350             I16 => Size::from_bytes(2),
 351             I32 => Size::from_bytes(4),
 352             I64  => Size::from_bytes(8),
 353             I128  => Size::from_bytes(16),
 354         }
 355     }
 356
 357     pub fn align(&self, dl: &TargetDataLayout)-> Align {
 358         match *self {
 359             I1 => dl.i1_align,
 360             I8 => dl.i8_align,
 361             I16 => dl.i16_align,
 362             I32 => dl.i32_align,
 363             I64 => dl.i64_align,
 364             I128 => dl.i128_align,
 365         }
 366     }
 367
 368     pub fn to_ty<'a, 'tcx>(&self, tcx: &ty::TyCtxt<'a, 'tcx, 'tcx>,
 369                            signed: bool) -> Ty<'tcx> {
 370         match (*self, signed) {
 371             (I1, false) => tcx.types.u8,
 372             (I8, false) => tcx.types.u8,
 373             (I16, false) => tcx.types.u16,
 374             (I32, false) => tcx.types.u32,
 375             (I64, false) => tcx.types.u64,
 376             (I128, false) => tcx.types.u128,
 377             (I1, true) => tcx.types.i8,
 378             (I8, true) => tcx.types.i8,
 379             (I16, true) => tcx.types.i16,
 380             (I32, true) => tcx.types.i32,
 381             (I64, true) => tcx.types.i64,
 382             (I128, true) => tcx.types.i128,
 383         }
 384     }
 385
 386     /// Find the smallest Integer type which can represent the signed value.
 387     pub fn fit_signed(x: i64) -> Integer {
 388         match x {
 389             -0x0000_0000_0000_0001...0x0000_0000_0000_0000 => I1,
 390             -0x0000_0000_0000_0080...0x0000_0000_0000_007f => I8,
 391             -0x0000_0000_0000_8000...0x0000_0000_0000_7fff => I16,
 392             -0x0000_0000_8000_0000...0x0000_0000_7fff_ffff => I32,
 393             -0x8000_0000_0000_0000...0x7fff_ffff_ffff_ffff => I64,
 394             _ => I128
 395         }
 396     }
 397
 398     /// Find the smallest Integer type which can represent the unsigned value.
 399     pub fn fit_unsigned(x: u64) -> Integer {
 400         match x {
 401             0...0x0000_0000_0000_0001 => I1,
 402             0...0x0000_0000_0000_00ff => I8,
 403             0...0x0000_0000_0000_ffff => I16,
 404             0...0x0000_0000_ffff_ffff => I32,
 405             0...0xffff_ffff_ffff_ffff => I64,
 406             _ => I128,
 407         }
 408     }
 409
 410     /// Find the smallest integer with the given alignment.
 411     pub fn for_abi_align(dl: &TargetDataLayout, align: Align) -> Option<Integer> {
 412         let wanted = align.abi();
 413         for &candidate in &[I8, I16, I32, I64] {
 414             let ty = Int(candidate);
 415             if wanted == ty.align(dl).abi() && wanted == ty.size(dl).bytes() {
 416                 return Some(candidate);
 417             }
 418         }
 419         None
 420     }
 421
 422     /// Get the Integer type from an attr::IntType.
 423     pub fn from_attr(dl: &TargetDataLayout, ity: attr::IntType) -> Integer {
 424         match ity {
 425             attr::SignedInt(IntTy::I8) | attr::UnsignedInt(UintTy::U8) => I8,
 426             attr::SignedInt(IntTy::I16) | attr::UnsignedInt(UintTy::U16) => I16,
 427             attr::SignedInt(IntTy::I32) | attr::UnsignedInt(UintTy::U32) => I32,
 428             attr::SignedInt(IntTy::I64) | attr::UnsignedInt(UintTy::U64) => I64,
 429             attr::SignedInt(IntTy::I128) | attr::UnsignedInt(UintTy::U128) => I128,
 430             attr::SignedInt(IntTy::Is) | attr::UnsignedInt(UintTy::Us) => {
 431                 dl.ptr_sized_integer()
 432             }
 433         }
 434     }
 435
 436     /// Find the appropriate Integer type and signedness for the given
 437     /// signed discriminant range and #[repr] attribute.
 438     /// N.B.: u64 values above i64::MAX will be treated as signed, but
 439     /// that shouldn't affect anything, other than maybe debuginfo.
 440     fn repr_discr(tcx: TyCtxt, ty: Ty, repr: &ReprOptions, min: i64, max: i64)
 441                       -> (Integer, bool) {
 442         // Theoretically, negative values could be larger in unsigned representation
 443         // than the unsigned representation of the signed minimum. However, if there
 444         // are any negative values, the only valid unsigned representation is u64
 445         // which can fit all i64 values, so the result remains unaffected.
 446         let unsigned_fit = Integer::fit_unsigned(cmp::max(min as u64, max as u64));
 447         let signed_fit = cmp::max(Integer::fit_signed(min), Integer::fit_signed(max));
 448
 449         let mut min_from_extern = None;
 450         let min_default = I8;
 451
 452         if let Some(ity) = repr.int {
 453             let discr = Integer::from_attr(&tcx.data_layout, ity);
 454             let fit = if ity.is_signed() { signed_fit } else { unsigned_fit };
 455             if discr < fit {
 456                 bug!("Integer::repr_discr: `#[repr]` hint too small for \
 457                   discriminant range of enum `{}", ty)
 458             }
 459             return (discr, ity.is_signed());
 460         }
 461
 462         if repr.c {
 463             match &tcx.sess.target.target.arch[..] {
 464                 // WARNING: the ARM EABI has two variants; the one corresponding
 465                 // to `at_least == I32` appears to be used on Linux and NetBSD,
 466                 // but some systems may use the variant corresponding to no
 467                 // lower bound.  However, we don't run on those yet...?
 468                 "arm" => min_from_extern = Some(I32),
 469                 _ => min_from_extern = Some(I32),
 470             }
 471         }
 472
 473         let at_least = min_from_extern.unwrap_or(min_default);
 474
 475         // If there are no negative values, we can use the unsigned fit.
 476         if min >= 0 {
 477             (cmp::max(unsigned_fit, at_least), false)
 478         } else {
 479             (cmp::max(signed_fit, at_least), true)
 480         }
 481     }
 482 }
 483
 484 /// Fundamental unit of memory access and layout.
 485 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)]
 486 pub enum Primitive {
 487     Int(Integer),
 488     F32,
 489     F64,
 490     Pointer
 491 }
 492
 493 impl Primitive {
 494     pub fn size(self, dl: &TargetDataLayout) -> Size {
 495         match self {
 496             Int(I1) | Int(I8) => Size::from_bits(8),
 497             Int(I16) => Size::from_bits(16),
 498             Int(I32) | F32 => Size::from_bits(32),
 499             Int(I64) | F64 => Size::from_bits(64),
 500             Int(I128) => Size::from_bits(128),
 501             Pointer => dl.pointer_size
 502         }
 503     }
 504
 505     pub fn align(self, dl: &TargetDataLayout) -> Align {
 506         match self {
 507             Int(I1) => dl.i1_align,
 508             Int(I8) => dl.i8_align,
 509             Int(I16) => dl.i16_align,
 510             Int(I32) => dl.i32_align,
 511             Int(I64) => dl.i64_align,
 512             Int(I128) => dl.i128_align,
 513             F32 => dl.f32_align,
 514             F64 => dl.f64_align,
 515             Pointer => dl.pointer_align
 516         }
 517     }
 518 }
 519
 520 /// Path through fields of nested structures.
 521 // FIXME(eddyb) use small vector optimization for the common case.
 522 pub type FieldPath = Vec<u32>;
 523
 524 /// A structure, a product type in ADT terms.
 525 #[derive(PartialEq, Eq, Hash, Debug)]
 526 pub struct Struct {
 527     pub align: Align,
 528
 529     /// If true, no alignment padding is used.
 530     pub packed: bool,
 531
 532     /// If true, the size is exact, otherwise it's only a lower bound.
 533     pub sized: bool,
 534
 535     /// Offsets for the first byte of each field, ordered to match the source definition order.
 536     /// This vector does not go in increasing order.
 537     /// FIXME(eddyb) use small vector optimization for the common case.
 538     pub offsets: Vec<Size>,
 539
 540     /// Maps source order field indices to memory order indices, depending how fields were permuted.
 541     /// FIXME (camlorn) also consider small vector  optimization here.
 542     pub memory_index: Vec<u32>,
 543
 544     pub min_size: Size,
 545 }
 546
 547 // Info required to optimize struct layout.
 548 #[derive(Copy, Clone, Eq, PartialEq, Ord, PartialOrd, Debug)]
 549 enum StructKind {
 550     // A tuple, closure, or univariant which cannot be coerced to unsized.
 551     AlwaysSizedUnivariant,
 552     // A univariant, the last field of which may be coerced to unsized.
 553     MaybeUnsizedUnivariant,
 554     // A univariant, but part of an enum.
 555     EnumVariant,
 556 }
 557
 558 impl<'a, 'gcx, 'tcx> Struct {
 559     // FIXME(camlorn): reprs need a better representation to deal with multiple reprs on one type.
 560     fn new(dl: &TargetDataLayout, fields: &Vec<&'a Layout>,
 561                   repr: &ReprOptions, kind: StructKind,
 562                   scapegoat: Ty<'gcx>) -> Result<Struct, LayoutError<'gcx>> {
 563         let packed = repr.packed;
 564         let mut ret = Struct {
 565             align: if packed { dl.i8_align } else { dl.aggregate_align },
 566             packed: packed,
 567             sized: true,
 568             offsets: vec![],
 569             memory_index: vec![],
 570             min_size: Size::from_bytes(0),
 571         };
 572
 573         // Anything with repr(C) or repr(packed) doesn't optimize.
 574         // Neither do  1-member and 2-member structs.
 575         // In addition, code in trans assume that 2-element structs can become pairs.
 576         // It's easier to just short-circuit here.
 577         let mut can_optimize = (fields.len() > 2 || StructKind::EnumVariant == kind)
 578             && ! (repr.c || repr.packed);
 579
 580         // Disable field reordering until we can decide what to do.
 581         // The odd pattern here avoids a warning about the value never being read.
 582         if can_optimize { can_optimize = false; }
 583
 584         let (optimize, sort_ascending) = match kind {
 585             StructKind::AlwaysSizedUnivariant => (can_optimize, false),
 586             StructKind::MaybeUnsizedUnivariant => (can_optimize, false),
 587             StructKind::EnumVariant => {
 588                 assert!(fields.len() >= 1, "Enum variants must have discriminants.");
 589                 (can_optimize && fields[0].size(dl).bytes() == 1, true)
 590             }
 591         };
 592
 593         ret.offsets = vec![Size::from_bytes(0); fields.len()];
 594         let mut inverse_memory_index: Vec<u32> = (0..fields.len() as u32).collect();
 595
 596         if optimize {
 597             let start = if let StructKind::EnumVariant = kind { 1 } else { 0 };
 598             let end = if let StructKind::MaybeUnsizedUnivariant = kind {
 599                 fields.len() - 1
 600             } else {
 601                 fields.len()
 602             };
 603             if end > start {
 604                 let optimizing  = &mut inverse_memory_index[start..end];
 605                 if sort_ascending {
 606                     optimizing.sort_by_key(|&x| fields[x as usize].align(dl).abi());
 607                 } else {
 608                     optimizing.sort_by(| &a, &b | {
 609                         let a = fields[a as usize].align(dl).abi();
 610                         let b = fields[b as usize].align(dl).abi();
 611                         b.cmp(&a)
 612                     });
 613                 }
 614             }
 615         }
 616
 617         // inverse_memory_index holds field indices by increasing memory offset.
 618         // That is, if field 5 has offset 0, the first element of inverse_memory_index is 5.
 619         // We now write field offsets to the corresponding offset slot;
 620         // field 5 with offset 0 puts 0 in offsets[5].
 621         // At the bottom of this function, we use inverse_memory_index to produce memory_index.
 622
 623         if let StructKind::EnumVariant = kind {
 624             assert_eq!(inverse_memory_index[0], 0,
 625               "Enum variant discriminants must have the lowest offset.");
 626         }
 627
 628         let mut offset = Size::from_bytes(0);
 629
 630         for i in inverse_memory_index.iter() {
 631             let field = fields[*i as usize];
 632             if !ret.sized {
 633                 bug!("Struct::new: field #{} of `{}` comes after unsized field",
 634                      ret.offsets.len(), scapegoat);
 635             }
 636
 637             if field.is_unsized() {
 638                 ret.sized = false;
 639             }
 640
 641             // Invariant: offset < dl.obj_size_bound() <= 1<<61
 642             if !ret.packed {
 643                 let align = field.align(dl);
 644                 ret.align = ret.align.max(align);
 645                 offset = offset.abi_align(align);
 646             }
 647
 648             debug!("Struct::new offset: {:?} field: {:?} {:?}", offset, field, field.size(dl));
 649             ret.offsets[*i as usize] = offset;
 650
 651             offset = offset.checked_add(field.size(dl), dl)
 652                            .map_or(Err(LayoutError::SizeOverflow(scapegoat)), Ok)?;
 653         }
 654
 655
 656         debug!("Struct::new min_size: {:?}", offset);
 657         ret.min_size = offset;
 658
 659         // As stated above, inverse_memory_index holds field indices by increasing offset.
 660         // This makes it an already-sorted view of the offsets vec.
 661         // To invert it, consider:
 662         // If field 5 has offset 0, offsets[0] is 5, and memory_index[5] should be 0.
 663         // Field 5 would be the first element, so memory_index is i:
 664         // Note: if we didn't optimize, it's already right.
 665
 666         if optimize {
 667             ret.memory_index = vec![0; inverse_memory_index.len()];
 668
 669             for i in 0..inverse_memory_index.len() {
 670                 ret.memory_index[inverse_memory_index[i] as usize]  = i as u32;
 671             }
 672         } else {
 673             ret.memory_index = inverse_memory_index;
 674         }
 675
 676         Ok(ret)
 677     }
 678
 679     /// Get the size with trailing alignment padding.
 680     pub fn stride(&self) -> Size {
 681         self.min_size.abi_align(self.align)
 682     }
 683
 684     /// Determine whether a structure would be zero-sized, given its fields.
 685     pub fn would_be_zero_sized<I>(dl: &TargetDataLayout, fields: I)
 686                                   -> Result<bool, LayoutError<'gcx>>
 687     where I: Iterator<Item=Result<&'a Layout, LayoutError<'gcx>>> {
 688         for field in fields {
 689             let field = field?;
 690             if field.is_unsized() || field.size(dl).bytes() > 0 {
 691                 return Ok(false);
 692             }
 693         }
 694         Ok(true)
 695     }
 696
 697     /// Get indices of the tys that made this struct by increasing offset.
 698     #[inline]
 699     pub fn field_index_by_increasing_offset<'b>(&'b self) -> impl iter::Iterator<Item=usize>+'b {
 700         let mut inverse_small = [0u8; 64];
 701         let mut inverse_big = vec![];
 702         let use_small = self.memory_index.len() <= inverse_small.len();
 703
 704         // We have to write this logic twice in order to keep the array small.
 705         if use_small {
 706             for i in 0..self.memory_index.len() {
 707                 inverse_small[self.memory_index[i] as usize] = i as u8;
 708             }
 709         } else {
 710             inverse_big = vec![0; self.memory_index.len()];
 711             for i in 0..self.memory_index.len() {
 712                 inverse_big[self.memory_index[i] as usize] = i as u32;
 713             }
 714         }
 715
 716         (0..self.memory_index.len()).map(move |i| {
 717             if use_small { inverse_small[i] as usize }
 718             else { inverse_big[i] as usize }
 719         })
 720     }
 721
 722     /// Find the path leading to a non-zero leaf field, starting from
 723     /// the given type and recursing through aggregates.
 724     /// The tuple is `(path, source_path)`,
 725     /// where `path` is in memory order and `source_path` in source order.
 726     // FIXME(eddyb) track value ranges and traverse already optimized enums.
 727     fn non_zero_field_in_type(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 728                                ty: Ty<'gcx>)
 729                                -> Result<Option<(FieldPath, FieldPath)>, LayoutError<'gcx>> {
 730         let tcx = infcx.tcx.global_tcx();
 731         match (ty.layout(infcx)?, &ty.sty) {
 732             (&Scalar { non_zero: true, .. }, _) |
 733             (&CEnum { non_zero: true, .. }, _) => Ok(Some((vec![], vec![]))),
 734             (&FatPointer { non_zero: true, .. }, _) => {
 735                 Ok(Some((vec![FAT_PTR_ADDR as u32], vec![FAT_PTR_ADDR as u32])))
 736             }
 737
 738             // Is this the NonZero lang item wrapping a pointer or integer type?
 739             (&Univariant { non_zero: true, .. }, &ty::TyAdt(def, substs)) => {
 740                 let fields = &def.struct_variant().fields;
 741                 assert_eq!(fields.len(), 1);
 742                 match *fields[0].ty(tcx, substs).layout(infcx)? {
 743                     // FIXME(eddyb) also allow floating-point types here.
 744                     Scalar { value: Int(_), non_zero: false } |
 745                     Scalar { value: Pointer, non_zero: false } => {
 746                         Ok(Some((vec![0], vec![0])))
 747                     }
 748                     FatPointer { non_zero: false, .. } => {
 749                         let tmp = vec![FAT_PTR_ADDR as u32, 0];
 750                         Ok(Some((tmp.clone(), tmp)))
 751                     }
 752                     _ => Ok(None)
 753                 }
 754             }
 755
 756             // Perhaps one of the fields of this struct is non-zero
 757             // let's recurse and find out
 758             (&Univariant { ref variant, .. }, &ty::TyAdt(def, substs)) if def.is_struct() => {
 759                 Struct::non_zero_field_paths(infcx, def.struct_variant().fields
 760                                                       .iter().map(|field| {
 761                     field.ty(tcx, substs)
 762                 }),
 763                 Some(&variant.memory_index[..]))
 764             }
 765
 766             // Perhaps one of the upvars of this closure is non-zero
 767             (&Univariant { ref variant, .. }, &ty::TyClosure(def, substs)) => {
 768                 let upvar_tys = substs.upvar_tys(def, tcx);
 769                 Struct::non_zero_field_paths(infcx, upvar_tys,
 770                     Some(&variant.memory_index[..]))
 771             }
 772             // Can we use one of the fields in this tuple?
 773             (&Univariant { ref variant, .. }, &ty::TyTuple(tys, _)) => {
 774                 Struct::non_zero_field_paths(infcx, tys.iter().cloned(),
 775                     Some(&variant.memory_index[..]))
 776             }
 777
 778             // Is this a fixed-size array of something non-zero
 779             // with at least one element?
 780             (_, &ty::TyArray(ety, d)) if d > 0 => {
 781                 Struct::non_zero_field_paths(infcx, Some(ety).into_iter(), None)
 782             }
 783
 784             (_, &ty::TyProjection(_)) | (_, &ty::TyAnon(..)) => {
 785                 let normalized = normalize_associated_type(infcx, ty);
 786                 if ty == normalized {
 787                     return Ok(None);
 788                 }
 789                 return Struct::non_zero_field_in_type(infcx, normalized);
 790             }
 791
 792             // Anything else is not a non-zero type.
 793             _ => Ok(None)
 794         }
 795     }
 796
 797     /// Find the path leading to a non-zero leaf field, starting from
 798     /// the given set of fields and recursing through aggregates.
 799     /// Returns Some((path, source_path)) on success.
 800     /// `path` is translated to memory order. `source_path` is not.
 801     fn non_zero_field_paths<I>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
 802                                   fields: I,
 803                                   permutation: Option<&[u32]>)
 804                                   -> Result<Option<(FieldPath, FieldPath)>, LayoutError<'gcx>>
 805     where I: Iterator<Item=Ty<'gcx>> {
 806         for (i, ty) in fields.enumerate() {
 807             if let Some((mut path, mut source_path)) = Struct::non_zero_field_in_type(infcx, ty)? {
 808                 source_path.push(i as u32);
 809                 let index = if let Some(p) = permutation {
 810                     p[i] as usize
 811                 } else {
 812                     i
 813                 };
 814                 path.push(index as u32);
 815                 return Ok(Some((path, source_path)));
 816             }
 817         }
 818         Ok(None)
 819     }
 820 }
 821
 822 /// An untagged union.
 823 #[derive(PartialEq, Eq, Hash, Debug)]
 824 pub struct Union {
 825     pub align: Align,
 826
 827     pub min_size: Size,
 828
 829     /// If true, no alignment padding is used.
 830     pub packed: bool,
 831 }
 832
 833 impl<'a, 'gcx, 'tcx> Union {
 834     pub fn new(dl: &TargetDataLayout, packed: bool) -> Union {
 835         Union {
 836             align: if packed { dl.i8_align } else { dl.aggregate_align },
 837             min_size: Size::from_bytes(0),
 838             packed: packed,
 839         }
 840     }
 841
 842     /// Extend the Struct with more fields.
 843     pub fn extend<I>(&mut self, dl: &TargetDataLayout,
 844                      fields: I,
 845                      scapegoat: Ty<'gcx>)
 846                      -> Result<(), LayoutError<'gcx>>
 847     where I: Iterator<Item=Result<&'a Layout, LayoutError<'gcx>>> {
 848         for (index, field) in fields.enumerate() {
 849             let field = field?;
 850             if field.is_unsized() {
 851                 bug!("Union::extend: field #{} of `{}` is unsized",
 852                      index, scapegoat);
 853             }
 854
 855             debug!("Union::extend field: {:?} {:?}", field, field.size(dl));
 856
 857             if !self.packed {
 858                 self.align = self.align.max(field.align(dl));
 859             }
 860             self.min_size = cmp::max(self.min_size, field.size(dl));
 861         }
 862
 863         debug!("Union::extend min-size: {:?}", self.min_size);
 864
 865         Ok(())
 866     }
 867
 868     /// Get the size with trailing alignment padding.
 869     pub fn stride(&self) -> Size {
 870         self.min_size.abi_align(self.align)
 871     }
 872 }
 873
 874 /// The first half of a fat pointer.
 875 /// - For a trait object, this is the address of the box.
 876 /// - For a slice, this is the base address.
 877 pub const FAT_PTR_ADDR: usize = 0;
 878
 879 /// The second half of a fat pointer.
 880 /// - For a trait object, this is the address of the vtable.
 881 /// - For a slice, this is the length.
 882 pub const FAT_PTR_EXTRA: usize = 1;
 883
 884 /// Type layout, from which size and alignment can be cheaply computed.
 885 /// For ADTs, it also includes field placement and enum optimizations.
 886 /// NOTE: Because Layout is interned, redundant information should be
 887 /// kept to a minimum, e.g. it includes no sub-component Ty or Layout.
 888 #[derive(Debug, PartialEq, Eq, Hash)]
 889 pub enum Layout {
 890     /// TyBool, TyChar, TyInt, TyUint, TyFloat, TyRawPtr, TyRef or TyFnPtr.
 891     Scalar {
 892         value: Primitive,
 893         // If true, the value cannot represent a bit pattern of all zeroes.
 894         non_zero: bool
 895     },
 896
 897     /// SIMD vectors, from structs marked with #[repr(simd)].
 898     Vector {
 899         element: Primitive,
 900         count: u64
 901     },
 902
 903     /// TyArray, TySlice or TyStr.
 904     Array {
 905         /// If true, the size is exact, otherwise it's only a lower bound.
 906         sized: bool,
 907         align: Align,
 908         size: Size
 909     },
 910
 911     /// TyRawPtr or TyRef with a !Sized pointee.
 912     FatPointer {
 913         metadata: Primitive,
 914         // If true, the pointer cannot be null.
 915         non_zero: bool
 916     },
 917
 918     // Remaining variants are all ADTs such as structs, enums or tuples.
 919
 920     /// C-like enums; basically an integer.
 921     CEnum {
 922         discr: Integer,
 923         signed: bool,
 924         non_zero: bool,
 925         // Inclusive discriminant range.
 926         // If min > max, it represents min...u64::MAX followed by 0...max.
 927         // FIXME(eddyb) always use the shortest range, e.g. by finding
 928         // the largest space between two consecutive discriminants and
 929         // taking everything else as the (shortest) discriminant range.
 930         min: u64,
 931         max: u64
 932     },
 933
 934     /// Single-case enums, and structs/tuples.
 935     Univariant {
 936         variant: Struct,
 937         // If true, the structure is NonZero.
 938         // FIXME(eddyb) use a newtype Layout kind for this.
 939         non_zero: bool
 940     },
 941
 942     /// Untagged unions.
 943     UntaggedUnion {
 944         variants: Union,
 945     },
 946
 947     /// General-case enums: for each case there is a struct, and they
 948     /// all start with a field for the discriminant.
 949     General {
 950         discr: Integer,
 951         variants: Vec<Struct>,
 952         size: Size,
 953         align: Align
 954     },
 955
 956     /// Two cases distinguished by a nullable pointer: the case with discriminant
 957     /// `nndiscr` must have single field which is known to be nonnull due to its type.
 958     /// The other case is known to be zero sized. Hence we represent the enum
 959     /// as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
 960     /// otherwise it indicates the other case.
 961     ///
 962     /// For example, `std::option::Option` instantiated at a safe pointer type
 963     /// is represented such that `None` is a null pointer and `Some` is the
 964     /// identity function.
 965     RawNullablePointer {
 966         nndiscr: u64,
 967         value: Primitive
 968     },
 969
 970     /// Two cases distinguished by a nullable pointer: the case with discriminant
 971     /// `nndiscr` is represented by the struct `nonnull`, where the `discrfield`th
 972     /// field is known to be nonnull due to its type; if that field is null, then
 973     /// it represents the other case, which is known to be zero sized.
 974     StructWrappedNullablePointer {
 975         nndiscr: u64,
 976         nonnull: Struct,
 977         // N.B. There is a 0 at the start, for LLVM GEP through a pointer.
 978         discrfield: FieldPath,
 979         // Like discrfield, but in source order. For debuginfo.
 980         discrfield_source: FieldPath
 981     }
 982 }
 983
 984 #[derive(Copy, Clone, Debug)]
 985 pub enum LayoutError<'tcx> {
 986     Unknown(Ty<'tcx>),
 987     SizeOverflow(Ty<'tcx>)
 988 }
 989
 990 impl<'tcx> fmt::Display for LayoutError<'tcx> {
 991     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 992         match *self {
 993             LayoutError::Unknown(ty) => {
 994                 write!(f, "the type `{:?}` has an unknown layout", ty)
 995             }
 996             LayoutError::SizeOverflow(ty) => {
 997                 write!(f, "the type `{:?}` is too big for the current architecture", ty)
 998             }
 999         }
1000     }
1001 }
1002
1003 /// Helper function for normalizing associated types in an inference context.
1004 fn normalize_associated_type<'a, 'gcx, 'tcx>(infcx: &InferCtxt<'a, 'gcx, 'tcx>,
1005                                              ty: Ty<'gcx>)
1006                                              -> Ty<'gcx> {
1007     if !ty.has_projection_types() {
1008         return ty;
1009     }
1010
1011     let mut selcx = traits::SelectionContext::new(infcx);
1012     let cause = traits::ObligationCause::dummy();
1013     let traits::Normalized { value: result, obligations } =
1014         traits::normalize(&mut selcx, cause, &ty);
1015
1016     let mut fulfill_cx = traits::FulfillmentContext::new();
1017
1018     for obligation in obligations {
1019         fulfill_cx.register_predicate_obligation(infcx, obligation);
1020     }
1021
1022     infcx.drain_fulfillment_cx_or_panic(DUMMY_SP, &mut fulfill_cx, &result)
1023 }
1024
1025 impl<'a, 'gcx, 'tcx> Layout {
1026     pub fn compute_uncached(ty: Ty<'gcx>,
1027                             infcx: &InferCtxt<'a, 'gcx, 'tcx>)
1028                             -> Result<&'gcx Layout, LayoutError<'gcx>> {
1029         let tcx = infcx.tcx.global_tcx();
1030         let success = |layout| Ok(tcx.intern_layout(layout));
1031         let dl = &tcx.data_layout;
1032         assert!(!ty.has_infer_types());
1033
1034         let ptr_layout = |pointee: Ty<'gcx>| {
1035             let non_zero = !ty.is_unsafe_ptr();
1036             let pointee = normalize_associated_type(infcx, pointee);
1037             if pointee.is_sized(tcx, &infcx.parameter_environment, DUMMY_SP) {
1038                 Ok(Scalar { value: Pointer, non_zero: non_zero })
1039             } else {
1040                 let unsized_part = tcx.struct_tail(pointee);
1041                 let meta = match unsized_part.sty {
1042                     ty::TySlice(_) | ty::TyStr => {
1043                         Int(dl.ptr_sized_integer())
1044                     }
1045                     ty::TyDynamic(..) => Pointer,
1046                     _ => return Err(LayoutError::Unknown(unsized_part))
1047                 };
1048                 Ok(FatPointer { metadata: meta, non_zero: non_zero })
1049             }
1050         };
1051
1052         let layout = match ty.sty {
1053             // Basic scalars.
1054             ty::TyBool => Scalar { value: Int(I1), non_zero: false },
1055             ty::TyChar => Scalar { value: Int(I32), non_zero: false },
1056             ty::TyInt(ity) => {
1057                 Scalar {
1058                     value: Int(Integer::from_attr(dl, attr::SignedInt(ity))),
1059                     non_zero: false
1060                 }
1061             }
1062             ty::TyUint(ity) => {
1063                 Scalar {
1064                     value: Int(Integer::from_attr(dl, attr::UnsignedInt(ity))),
1065                     non_zero: false
1066                 }
1067             }
1068             ty::TyFloat(FloatTy::F32) => Scalar { value: F32, non_zero: false },
1069             ty::TyFloat(FloatTy::F64) => Scalar { value: F64, non_zero: false },
1070             ty::TyFnPtr(_) => Scalar { value: Pointer, non_zero: true },
1071
1072             // The never type.
1073             ty::TyNever => Univariant {
1074                 variant: Struct::new(dl, &vec![], &ReprOptions::default(),
1075                   StructKind::AlwaysSizedUnivariant, ty)?,
1076                 non_zero: false
1077             },
1078
1079             // Potentially-fat pointers.
1080             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
1081             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1082                 ptr_layout(pointee)?
1083             }
1084             ty::TyAdt(def, _) if def.is_box() => {
1085                 ptr_layout(ty.boxed_ty())?
1086             }
1087
1088             // Arrays and slices.
1089             ty::TyArray(element, count) => {
1090                 let element = element.layout(infcx)?;
1091                 Array {
1092                     sized: true,
1093                     align: element.align(dl),
1094                     size: element.size(dl).checked_mul(count as u64, dl)
1095                                  .map_or(Err(LayoutError::SizeOverflow(ty)), Ok)?
1096                 }
1097             }
1098             ty::TySlice(element) => {
1099                 Array {
1100                     sized: false,
1101                     align: element.layout(infcx)?.align(dl),
1102                     size: Size::from_bytes(0)
1103                 }
1104             }
1105             ty::TyStr => {
1106                 Array {
1107                     sized: false,
1108                     align: dl.i8_align,
1109                     size: Size::from_bytes(0)
1110                 }
1111             }
1112
1113             // Odd unit types.
1114             ty::TyFnDef(..) => {
1115                 Univariant {
1116                     variant: Struct::new(dl, &vec![],
1117                       &ReprOptions::default(), StructKind::AlwaysSizedUnivariant, ty)?,
1118                     non_zero: false
1119                 }
1120             }
1121             ty::TyDynamic(..) => {
1122                 let mut unit = Struct::new(dl, &vec![], &ReprOptions::default(),
1123                   StructKind::AlwaysSizedUnivariant, ty)?;
1124                 unit.sized = false;
1125                 Univariant { variant: unit, non_zero: false }
1126             }
1127
1128             // Tuples and closures.
1129             ty::TyClosure(def_id, ref substs) => {
1130                 let tys = substs.upvar_tys(def_id, tcx);
1131                 let st = Struct::new(dl,
1132                     &tys.map(|ty| ty.layout(infcx))
1133                       .collect::<Result<Vec<_>, _>>()?,
1134                     &ReprOptions::default(),
1135                     StructKind::AlwaysSizedUnivariant, ty)?;
1136                 Univariant { variant: st, non_zero: false }
1137             }
1138
1139             ty::TyTuple(tys, _) => {
1140                 // FIXME(camlorn): if we ever allow unsized tuples, this needs to be checked.
1141                 // See the univariant case below to learn how.
1142                 let st = Struct::new(dl,
1143                     &tys.iter().map(|ty| ty.layout(infcx))
1144                       .collect::<Result<Vec<_>, _>>()?,
1145                     &ReprOptions::default(), StructKind::AlwaysSizedUnivariant, ty)?;
1146                 Univariant { variant: st, non_zero: false }
1147             }
1148
1149             // SIMD vector types.
1150             ty::TyAdt(def, ..) if def.is_simd() => {
1151                 let element = ty.simd_type(tcx);
1152                 match *element.layout(infcx)? {
1153                     Scalar { value, .. } => {
1154                         return success(Vector {
1155                             element: value,
1156                             count: ty.simd_size(tcx) as u64
1157                         });
1158                     }
1159                     _ => {
1160                         tcx.sess.fatal(&format!("monomorphising SIMD type `{}` with \
1161                                                 a non-machine element type `{}`",
1162                                                 ty, element));
1163                     }
1164                 }
1165             }
1166
1167             // ADTs.
1168             ty::TyAdt(def, substs) => {
1169                 if def.variants.is_empty() {
1170                     // Uninhabitable; represent as unit
1171                     // (Typechecking will reject discriminant-sizing attrs.)
1172
1173                     return success(Univariant {
1174                         variant: Struct::new(dl, &vec![],
1175                           &def.repr, StructKind::AlwaysSizedUnivariant, ty)?,
1176                         non_zero: false
1177                     });
1178                 }
1179
1180                 if def.is_enum() && def.variants.iter().all(|v| v.fields.is_empty()) {
1181                     // All bodies empty -> intlike
1182                     let (mut min, mut max, mut non_zero) = (i64::max_value(),
1183                                                             i64::min_value(),
1184                                                             true);
1185                     for v in &def.variants {
1186                         let x = match v.disr_val.erase_type() {
1187                             ConstInt::InferSigned(i) => i as i64,
1188                             ConstInt::Infer(i) => i as u64 as i64,
1189                             _ => bug!()
1190                         };
1191                         if x == 0 { non_zero = false; }
1192                         if x < min { min = x; }
1193                         if x > max { max = x; }
1194                     }
1195
1196                     // FIXME: should handle i128? signed-value based impl is weird and hard to
1197                     // grok.
1198                     let (discr, signed) = Integer::repr_discr(tcx, ty, &def.repr,
1199                                                               min,
1200                                                               max);
1201                     return success(CEnum {
1202                         discr: discr,
1203                         signed: signed,
1204                         non_zero: non_zero,
1205                         // FIXME: should be u128?
1206                         min: min as u64,
1207                         max: max as u64
1208                     });
1209                 }
1210
1211                 if !def.is_enum() || def.variants.len() == 1 {
1212                     // Struct, or union, or univariant enum equivalent to a struct.
1213                     // (Typechecking will reject discriminant-sizing attrs.)
1214
1215                     let kind = if def.is_enum() || def.variants[0].fields.len() == 0{
1216                         StructKind::AlwaysSizedUnivariant
1217                     } else {
1218                         use middle::region::ROOT_CODE_EXTENT;
1219                         let param_env = tcx.construct_parameter_environment(DUMMY_SP,
1220                           def.did, ROOT_CODE_EXTENT);
1221                         let fields = &def.variants[0].fields;
1222                         let last_field = &fields[fields.len()-1];
1223                         let always_sized = last_field.ty(tcx, param_env.free_substs)
1224                           .is_sized(tcx, &param_env, DUMMY_SP);
1225                         if !always_sized { StructKind::MaybeUnsizedUnivariant }
1226                         else { StructKind::AlwaysSizedUnivariant }
1227                     };
1228
1229                     let fields = def.variants[0].fields.iter().map(|field| {
1230                         field.ty(tcx, substs).layout(infcx)
1231                     }).collect::<Result<Vec<_>, _>>()?;
1232                     let packed = tcx.lookup_packed(def.did);
1233                     let layout = if def.is_union() {
1234                         let mut un = Union::new(dl, packed);
1235                         un.extend(dl, fields.iter().map(|&f| Ok(f)), ty)?;
1236                         UntaggedUnion { variants: un }
1237                     } else {
1238                         let st = Struct::new(dl, &fields, &def.repr,
1239                           kind, ty)?;
1240                         let non_zero = Some(def.did) == tcx.lang_items.non_zero();
1241                         Univariant { variant: st, non_zero: non_zero }
1242                     };
1243                     return success(layout);
1244                 }
1245
1246                 // Since there's at least one
1247                 // non-empty body, explicit discriminants should have
1248                 // been rejected by a checker before this point.
1249                 for (i, v) in def.variants.iter().enumerate() {
1250                     if i as u128 != v.disr_val.to_u128_unchecked() {
1251                         bug!("non-C-like enum {} with specified discriminants",
1252                             tcx.item_path_str(def.did));
1253                     }
1254                 }
1255
1256                 // Cache the substituted and normalized variant field types.
1257                 let variants = def.variants.iter().map(|v| {
1258                     v.fields.iter().map(|field| field.ty(tcx, substs)).collect::<Vec<_>>()
1259                 }).collect::<Vec<_>>();
1260
1261                 if variants.len() == 2 && !def.repr.c {
1262                     // Nullable pointer optimization
1263                     for discr in 0..2 {
1264                         let other_fields = variants[1 - discr].iter().map(|ty| {
1265                             ty.layout(infcx)
1266                         });
1267                         if !Struct::would_be_zero_sized(dl, other_fields)? {
1268                             continue;
1269                         }
1270                         let paths = Struct::non_zero_field_paths(infcx,
1271                             variants[discr].iter().cloned(),
1272                             None)?;
1273                         let (mut path, mut path_source) = if let Some(p) = paths { p }
1274                           else { continue };
1275
1276                         // FIXME(eddyb) should take advantage of a newtype.
1277                         if path == &[0] && variants[discr].len() == 1 {
1278                             let value = match *variants[discr][0].layout(infcx)? {
1279                                 Scalar { value, .. } => value,
1280                                 CEnum { discr, .. } => Int(discr),
1281                                 _ => bug!("Layout::compute: `{}`'s non-zero \
1282                                            `{}` field not scalar?!",
1283                                            ty, variants[discr][0])
1284                             };
1285                             return success(RawNullablePointer {
1286                                 nndiscr: discr as u64,
1287                                 value: value,
1288                             });
1289                         }
1290
1291                         let st = Struct::new(dl,
1292                             &variants[discr].iter().map(|ty| ty.layout(infcx))
1293                               .collect::<Result<Vec<_>, _>>()?,
1294                             &def.repr, StructKind::AlwaysSizedUnivariant, ty)?;
1295
1296                         // We have to fix the last element of path here.
1297                         let mut i = *path.last().unwrap();
1298                         i = st.memory_index[i as usize];
1299                         *path.last_mut().unwrap() = i;
1300                         path.push(0); // For GEP through a pointer.
1301                         path.reverse();
1302                         path_source.push(0);
1303                         path_source.reverse();
1304
1305                         return success(StructWrappedNullablePointer {
1306                             nndiscr: discr as u64,
1307                             nonnull: st,
1308                             discrfield: path,
1309                             discrfield_source: path_source
1310                         });
1311                     }
1312                 }
1313
1314                 // The general case.
1315                 let discr_max = (variants.len() - 1) as i64;
1316                 assert!(discr_max >= 0);
1317                 let (min_ity, _) = Integer::repr_discr(tcx, ty, &def.repr, 0, discr_max);
1318
1319                 let mut align = dl.aggregate_align;
1320                 let mut size = Size::from_bytes(0);
1321
1322                 // We're interested in the smallest alignment, so start large.
1323                 let mut start_align = Align::from_bytes(256, 256).unwrap();
1324
1325                 // Create the set of structs that represent each variant
1326                 // Use the minimum integer type we figured out above
1327                 let discr = Scalar { value: Int(min_ity), non_zero: false };
1328                 let mut variants = variants.into_iter().map(|fields| {
1329                     let mut fields = fields.into_iter().map(|field| {
1330                         field.layout(infcx)
1331                     }).collect::<Result<Vec<_>, _>>()?;
1332                     fields.insert(0, &discr);
1333                     let st = Struct::new(dl,
1334                         &fields,
1335                         &def.repr, StructKind::EnumVariant, ty)?;
1336                     // Find the first field we can't move later
1337                     // to make room for a larger discriminant.
1338                     // It is important to skip the first field.
1339                     for i in st.field_index_by_increasing_offset().skip(1) {
1340                         let field = fields[i];
1341                         let field_align = field.align(dl);
1342                         if field.size(dl).bytes() != 0 || field_align.abi() != 1 {
1343                             start_align = start_align.min(field_align);
1344                             break;
1345                         }
1346                     }
1347                     size = cmp::max(size, st.min_size);
1348                     align = align.max(st.align);
1349                     Ok(st)
1350                 }).collect::<Result<Vec<_>, _>>()?;
1351
1352                 // Align the maximum variant size to the largest alignment.
1353                 size = size.abi_align(align);
1354
1355                 if size.bytes() >= dl.obj_size_bound() {
1356                     return Err(LayoutError::SizeOverflow(ty));
1357                 }
1358
1359                 // Check to see if we should use a different type for the
1360                 // discriminant. We can safely use a type with the same size
1361                 // as the alignment of the first field of each variant.
1362                 // We increase the size of the discriminant to avoid LLVM copying
1363                 // padding when it doesn't need to. This normally causes unaligned
1364                 // load/stores and excessive memcpy/memset operations. By using a
1365                 // bigger integer size, LLVM can be sure about it's contents and
1366                 // won't be so conservative.
1367
1368                 // Use the initial field alignment
1369                 let mut ity = Integer::for_abi_align(dl, start_align).unwrap_or(min_ity);
1370
1371                 // If the alignment is not larger than the chosen discriminant size,
1372                 // don't use the alignment as the final size.
1373                 if ity <= min_ity {
1374                     ity = min_ity;
1375                 } else {
1376                     // Patch up the variants' first few fields.
1377                     let old_ity_size = Int(min_ity).size(dl);
1378                     let new_ity_size = Int(ity).size(dl);
1379                     for variant in &mut variants {
1380                         for i in variant.offsets.iter_mut() {
1381                             // The first field is the discrimminant, at offset 0.
1382                             // These aren't in order, and we need to skip it.
1383                             if *i <= old_ity_size && *i > Size::from_bytes(0) {
1384                                 *i = new_ity_size;
1385                             }
1386                         }
1387                         // We might be making the struct larger.
1388                         if variant.min_size <= old_ity_size {
1389                             variant.min_size = new_ity_size;
1390                         }
1391                     }
1392                 }
1393
1394                 General {
1395                     discr: ity,
1396                     variants: variants,
1397                     size: size,
1398                     align: align
1399                 }
1400             }
1401
1402             // Types with no meaningful known layout.
1403             ty::TyProjection(_) | ty::TyAnon(..) => {
1404                 let normalized = normalize_associated_type(infcx, ty);
1405                 if ty == normalized {
1406                     return Err(LayoutError::Unknown(ty));
1407                 }
1408                 return normalized.layout(infcx);
1409             }
1410             ty::TyParam(_) => {
1411                 return Err(LayoutError::Unknown(ty));
1412             }
1413             ty::TyInfer(_) | ty::TyError => {
1414                 bug!("Layout::compute: unexpected type `{}`", ty)
1415             }
1416         };
1417
1418         success(layout)
1419     }
1420
1421     /// Returns true if the layout corresponds to an unsized type.
1422     pub fn is_unsized(&self) -> bool {
1423         match *self {
1424             Scalar {..} | Vector {..} | FatPointer {..} |
1425             CEnum {..} | UntaggedUnion {..} | General {..} |
1426             RawNullablePointer {..} |
1427             StructWrappedNullablePointer {..} => false,
1428
1429             Array { sized, .. } |
1430             Univariant { variant: Struct { sized, .. }, .. } => !sized
1431         }
1432     }
1433
1434     pub fn size(&self, dl: &TargetDataLayout) -> Size {
1435         match *self {
1436             Scalar { value, .. } | RawNullablePointer { value, .. } => {
1437                 value.size(dl)
1438             }
1439
1440             Vector { element, count } => {
1441                 let elem_size = element.size(dl);
1442                 let vec_size = match elem_size.checked_mul(count, dl) {
1443                     Some(size) => size,
1444                     None => bug!("Layout::size({:?}): {} * {} overflowed",
1445                                  self, elem_size.bytes(), count)
1446                 };
1447                 vec_size.abi_align(self.align(dl))
1448             }
1449
1450             FatPointer { metadata, .. } => {
1451                 // Effectively a (ptr, meta) tuple.
1452                 Pointer.size(dl).abi_align(metadata.align(dl))
1453                        .checked_add(metadata.size(dl), dl).unwrap()
1454                        .abi_align(self.align(dl))
1455             }
1456
1457             CEnum { discr, .. } => Int(discr).size(dl),
1458             Array { size, .. } | General { size, .. } => size,
1459             UntaggedUnion { ref variants } => variants.stride(),
1460
1461             Univariant { ref variant, .. } |
1462             StructWrappedNullablePointer { nonnull: ref variant, .. } => {
1463                 variant.stride()
1464             }
1465         }
1466     }
1467
1468     pub fn align(&self, dl: &TargetDataLayout) -> Align {
1469         match *self {
1470             Scalar { value, .. } | RawNullablePointer { value, .. } => {
1471                 value.align(dl)
1472             }
1473
1474             Vector { element, count } => {
1475                 let elem_size = element.size(dl);
1476                 let vec_size = match elem_size.checked_mul(count, dl) {
1477                     Some(size) => size,
1478                     None => bug!("Layout::align({:?}): {} * {} overflowed",
1479                                  self, elem_size.bytes(), count)
1480                 };
1481                 for &(size, align) in &dl.vector_align {
1482                     if size == vec_size {
1483                         return align;
1484                     }
1485                 }
1486                 // Default to natural alignment, which is what LLVM does.
1487                 // That is, use the size, rounded up to a power of 2.
1488                 let align = vec_size.bytes().next_power_of_two();
1489                 Align::from_bytes(align, align).unwrap()
1490             }
1491
1492             FatPointer { metadata, .. } => {
1493                 // Effectively a (ptr, meta) tuple.
1494                 Pointer.align(dl).max(metadata.align(dl))
1495             }
1496
1497             CEnum { discr, .. } => Int(discr).align(dl),
1498             Array { align, .. } | General { align, .. } => align,
1499             UntaggedUnion { ref variants } => variants.align,
1500
1501             Univariant { ref variant, .. } |
1502             StructWrappedNullablePointer { nonnull: ref variant, .. } => {
1503                 variant.align
1504             }
1505         }
1506     }
1507 }
1508
1509 /// Type size "skeleton", i.e. the only information determining a type's size.
1510 /// While this is conservative, (aside from constant sizes, only pointers,
1511 /// newtypes thereof and null pointer optimized enums are allowed), it is
1512 /// enough to statically check common usecases of transmute.
1513 #[derive(Copy, Clone, Debug)]
1514 pub enum SizeSkeleton<'tcx> {
1515     /// Any statically computable Layout.
1516     Known(Size),
1517
1518     /// A potentially-fat pointer.
1519     Pointer {
1520         // If true, this pointer is never null.
1521         non_zero: bool,
1522         // The type which determines the unsized metadata, if any,
1523         // of this pointer. Either a type parameter or a projection
1524         // depending on one, with regions erased.
1525         tail: Ty<'tcx>
1526     }
1527 }
1528
1529 impl<'a, 'gcx, 'tcx> SizeSkeleton<'gcx> {
1530     pub fn compute(ty: Ty<'gcx>, infcx: &InferCtxt<'a, 'gcx, 'tcx>)
1531                    -> Result<SizeSkeleton<'gcx>, LayoutError<'gcx>> {
1532         let tcx = infcx.tcx.global_tcx();
1533         assert!(!ty.has_infer_types());
1534
1535         // First try computing a static layout.
1536         let err = match ty.layout(infcx) {
1537             Ok(layout) => {
1538                 return Ok(SizeSkeleton::Known(layout.size(&tcx.data_layout)));
1539             }
1540             Err(err) => err
1541         };
1542
1543         let ptr_skeleton = |pointee: Ty<'gcx>| {
1544             let non_zero = !ty.is_unsafe_ptr();
1545             let tail = tcx.struct_tail(pointee);
1546             match tail.sty {
1547                 ty::TyParam(_) | ty::TyProjection(_) => {
1548                     assert!(tail.has_param_types() || tail.has_self_ty());
1549                     Ok(SizeSkeleton::Pointer {
1550                         non_zero: non_zero,
1551                         tail: tcx.erase_regions(&tail)
1552                     })
1553                 }
1554                 _ => {
1555                     bug!("SizeSkeleton::compute({}): layout errored ({}), yet \
1556                             tail `{}` is not a type parameter or a projection",
1557                             ty, err, tail)
1558                 }
1559             }
1560         };
1561
1562         match ty.sty {
1563             ty::TyRef(_, ty::TypeAndMut { ty: pointee, .. }) |
1564             ty::TyRawPtr(ty::TypeAndMut { ty: pointee, .. }) => {
1565                 ptr_skeleton(pointee)
1566             }
1567             ty::TyAdt(def, _) if def.is_box() => {
1568                 ptr_skeleton(ty.boxed_ty())
1569             }
1570
1571             ty::TyAdt(def, substs) => {
1572                 // Only newtypes and enums w/ nullable pointer optimization.
1573                 if def.is_union() || def.variants.is_empty() || def.variants.len() > 2 {
1574                     return Err(err);
1575                 }
1576
1577                 // Get a zero-sized variant or a pointer newtype.
1578                 let zero_or_ptr_variant = |i: usize| {
1579                     let fields = def.variants[i].fields.iter().map(|field| {
1580                         SizeSkeleton::compute(field.ty(tcx, substs), infcx)
1581                     });
1582                     let mut ptr = None;
1583                     for field in fields {
1584                         let field = field?;
1585                         match field {
1586                             SizeSkeleton::Known(size) => {
1587                                 if size.bytes() > 0 {
1588                                     return Err(err);
1589                                 }
1590                             }
1591                             SizeSkeleton::Pointer {..} => {
1592                                 if ptr.is_some() {
1593                                     return Err(err);
1594                                 }
1595                                 ptr = Some(field);
1596                             }
1597                         }
1598                     }
1599                     Ok(ptr)
1600                 };
1601
1602                 let v0 = zero_or_ptr_variant(0)?;
1603                 // Newtype.
1604                 if def.variants.len() == 1 {
1605                     if let Some(SizeSkeleton::Pointer { non_zero, tail }) = v0 {
1606                         return Ok(SizeSkeleton::Pointer {
1607                             non_zero: non_zero ||
1608                                 Some(def.did) == tcx.lang_items.non_zero(),
1609                             tail: tail
1610                         });
1611                     } else {
1612                         return Err(err);
1613                     }
1614                 }
1615
1616                 let v1 = zero_or_ptr_variant(1)?;
1617                 // Nullable pointer enum optimization.
1618                 match (v0, v1) {
1619                     (Some(SizeSkeleton::Pointer { non_zero: true, tail }), None) |
1620                     (None, Some(SizeSkeleton::Pointer { non_zero: true, tail })) => {
1621                         Ok(SizeSkeleton::Pointer {
1622                             non_zero: false,
1623                             tail: tail
1624                         })
1625                     }
1626                     _ => Err(err)
1627                 }
1628             }
1629
1630             ty::TyProjection(_) | ty::TyAnon(..) => {
1631                 let normalized = normalize_associated_type(infcx, ty);
1632                 if ty == normalized {
1633                     Err(err)
1634                 } else {
1635                     SizeSkeleton::compute(normalized, infcx)
1636                 }
1637             }
1638
1639             _ => Err(err)
1640         }
1641     }
1642
1643     pub fn same_size(self, other: SizeSkeleton) -> bool {
1644         match (self, other) {
1645             (SizeSkeleton::Known(a), SizeSkeleton::Known(b)) => a == b,
1646             (SizeSkeleton::Pointer { tail: a, .. },
1647              SizeSkeleton::Pointer { tail: b, .. }) => a == b,
1648             _ => false
1649         }
1650     }
1651 }