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