src/librustc_target/abi/mod.rs

   1 pub use Integer::*;
   2 pub use Primitive::*;
   3
   4 use crate::spec::Target;
   5
   6 use std::ops::{Add, AddAssign, Deref, Mul, Range, RangeInclusive, Sub};
   7
   8 use rustc_index::vec::{Idx, IndexVec};
   9 use rustc_macros::HashStable_Generic;
  10 use rustc_span::Span;
  11
  12 pub mod call;
  13
  14 /// Parsed [Data layout](http://llvm.org/docs/LangRef.html#data-layout)
  15 /// for a target, which contains everything needed to compute layouts.
  16 pub struct TargetDataLayout {
  17     pub endian: Endian,
  18     pub i1_align: AbiAndPrefAlign,
  19     pub i8_align: AbiAndPrefAlign,
  20     pub i16_align: AbiAndPrefAlign,
  21     pub i32_align: AbiAndPrefAlign,
  22     pub i64_align: AbiAndPrefAlign,
  23     pub i128_align: AbiAndPrefAlign,
  24     pub f32_align: AbiAndPrefAlign,
  25     pub f64_align: AbiAndPrefAlign,
  26     pub pointer_size: Size,
  27     pub pointer_align: AbiAndPrefAlign,
  28     pub aggregate_align: AbiAndPrefAlign,
  29
  30     /// Alignments for vector types.
  31     pub vector_align: Vec<(Size, AbiAndPrefAlign)>,
  32
  33     pub instruction_address_space: u32,
  34 }
  35
  36 impl Default for TargetDataLayout {
  37     /// Creates an instance of `TargetDataLayout`.
  38     fn default() -> TargetDataLayout {
  39         let align = |bits| Align::from_bits(bits).unwrap();
  40         TargetDataLayout {
  41             endian: Endian::Big,
  42             i1_align: AbiAndPrefAlign::new(align(8)),
  43             i8_align: AbiAndPrefAlign::new(align(8)),
  44             i16_align: AbiAndPrefAlign::new(align(16)),
  45             i32_align: AbiAndPrefAlign::new(align(32)),
  46             i64_align: AbiAndPrefAlign { abi: align(32), pref: align(64) },
  47             i128_align: AbiAndPrefAlign { abi: align(32), pref: align(64) },
  48             f32_align: AbiAndPrefAlign::new(align(32)),
  49             f64_align: AbiAndPrefAlign::new(align(64)),
  50             pointer_size: Size::from_bits(64),
  51             pointer_align: AbiAndPrefAlign::new(align(64)),
  52             aggregate_align: AbiAndPrefAlign { abi: align(0), pref: align(64) },
  53             vector_align: vec![
  54                 (Size::from_bits(64), AbiAndPrefAlign::new(align(64))),
  55                 (Size::from_bits(128), AbiAndPrefAlign::new(align(128))),
  56             ],
  57             instruction_address_space: 0,
  58         }
  59     }
  60 }
  61
  62 impl TargetDataLayout {
  63     pub fn parse(target: &Target) -> Result<TargetDataLayout, String> {
  64         // Parse an address space index from a string.
  65         let parse_address_space = |s: &str, cause: &str| {
  66             s.parse::<u32>().map_err(|err| {
  67                 format!("invalid address space `{}` for `{}` in \"data-layout\": {}", s, cause, err)
  68             })
  69         };
  70
  71         // Parse a bit count from a string.
  72         let parse_bits = |s: &str, kind: &str, cause: &str| {
  73             s.parse::<u64>().map_err(|err| {
  74                 format!("invalid {} `{}` for `{}` in \"data-layout\": {}", kind, s, cause, err)
  75             })
  76         };
  77
  78         // Parse a size string.
  79         let size = |s: &str, cause: &str| parse_bits(s, "size", cause).map(Size::from_bits);
  80
  81         // Parse an alignment string.
  82         let align = |s: &[&str], cause: &str| {
  83             if s.is_empty() {
  84                 return Err(format!("missing alignment for `{}` in \"data-layout\"", cause));
  85             }
  86             let align_from_bits = |bits| {
  87                 Align::from_bits(bits).map_err(|err| {
  88                     format!("invalid alignment for `{}` in \"data-layout\": {}", cause, err)
  89                 })
  90             };
  91             let abi = parse_bits(s[0], "alignment", cause)?;
  92             let pref = s.get(1).map_or(Ok(abi), |pref| parse_bits(pref, "alignment", cause))?;
  93             Ok(AbiAndPrefAlign { abi: align_from_bits(abi)?, pref: align_from_bits(pref)? })
  94         };
  95
  96         let mut dl = TargetDataLayout::default();
  97         let mut i128_align_src = 64;
  98         for spec in target.data_layout.split('-') {
  99             let spec_parts = spec.split(':').collect::<Vec<_>>();
 100
 101             match &*spec_parts {
 102                 ["e"] => dl.endian = Endian::Little,
 103                 ["E"] => dl.endian = Endian::Big,
 104                 [p] if p.starts_with('P') => {
 105                     dl.instruction_address_space = parse_address_space(&p[1..], "P")?
 106                 }
 107                 ["a", ref a @ ..] => dl.aggregate_align = align(a, "a")?,
 108                 ["f32", ref a @ ..] => dl.f32_align = align(a, "f32")?,
 109                 ["f64", ref a @ ..] => dl.f64_align = align(a, "f64")?,
 110                 [p @ "p", s, ref a @ ..] | [p @ "p0", s, ref a @ ..] => {
 111                     dl.pointer_size = size(s, p)?;
 112                     dl.pointer_align = align(a, p)?;
 113                 }
 114                 [s, ref a @ ..] if s.starts_with('i') => {
 115                     let bits = match s[1..].parse::<u64>() {
 116                         Ok(bits) => bits,
 117                         Err(_) => {
 118                             size(&s[1..], "i")?; // For the user error.
 119                             continue;
 120                         }
 121                     };
 122                     let a = align(a, s)?;
 123                     match bits {
 124                         1 => dl.i1_align = a,
 125                         8 => dl.i8_align = a,
 126                         16 => dl.i16_align = a,
 127                         32 => dl.i32_align = a,
 128                         64 => dl.i64_align = a,
 129                         _ => {}
 130                     }
 131                     if bits >= i128_align_src && bits <= 128 {
 132                         // Default alignment for i128 is decided by taking the alignment of
 133                         // largest-sized i{64..=128}.
 134                         i128_align_src = bits;
 135                         dl.i128_align = a;
 136                     }
 137                 }
 138                 [s, ref a @ ..] if s.starts_with('v') => {
 139                     let v_size = size(&s[1..], "v")?;
 140                     let a = align(a, s)?;
 141                     if let Some(v) = dl.vector_align.iter_mut().find(|v| v.0 == v_size) {
 142                         v.1 = a;
 143                         continue;
 144                     }
 145                     // No existing entry, add a new one.
 146                     dl.vector_align.push((v_size, a));
 147                 }
 148                 _ => {} // Ignore everything else.
 149             }
 150         }
 151
 152         // Perform consistency checks against the Target information.
 153         let endian_str = match dl.endian {
 154             Endian::Little => "little",
 155             Endian::Big => "big",
 156         };
 157         if endian_str != target.target_endian {
 158             return Err(format!(
 159                 "inconsistent target specification: \"data-layout\" claims \
 160                                 architecture is {}-endian, while \"target-endian\" is `{}`",
 161                 endian_str, target.target_endian
 162             ));
 163         }
 164
 165         if dl.pointer_size.bits().to_string() != target.target_pointer_width {
 166             return Err(format!(
 167                 "inconsistent target specification: \"data-layout\" claims \
 168                                 pointers are {}-bit, while \"target-pointer-width\" is `{}`",
 169                 dl.pointer_size.bits(),
 170                 target.target_pointer_width
 171             ));
 172         }
 173
 174         Ok(dl)
 175     }
 176
 177     /// Returns exclusive upper bound on object size.
 178     ///
 179     /// The theoretical maximum object size is defined as the maximum positive `isize` value.
 180     /// This ensures that the `offset` semantics remain well-defined by allowing it to correctly
 181     /// index every address within an object along with one byte past the end, along with allowing
 182     /// `isize` to store the difference between any two pointers into an object.
 183     ///
 184     /// The upper bound on 64-bit currently needs to be lower because LLVM uses a 64-bit integer
 185     /// to represent object size in bits. It would need to be 1 << 61 to account for this, but is
 186     /// currently conservatively bounded to 1 << 47 as that is enough to cover the current usable
 187     /// address space on 64-bit ARMv8 and x86_64.
 188     pub fn obj_size_bound(&self) -> u64 {
 189         match self.pointer_size.bits() {
 190             16 => 1 << 15,
 191             32 => 1 << 31,
 192             64 => 1 << 47,
 193             bits => panic!("obj_size_bound: unknown pointer bit size {}", bits),
 194         }
 195     }
 196
 197     pub fn ptr_sized_integer(&self) -> Integer {
 198         match self.pointer_size.bits() {
 199             16 => I16,
 200             32 => I32,
 201             64 => I64,
 202             bits => panic!("ptr_sized_integer: unknown pointer bit size {}", bits),
 203         }
 204     }
 205
 206     pub fn vector_align(&self, vec_size: Size) -> AbiAndPrefAlign {
 207         for &(size, align) in &self.vector_align {
 208             if size == vec_size {
 209                 return align;
 210             }
 211         }
 212         // Default to natural alignment, which is what LLVM does.
 213         // That is, use the size, rounded up to a power of 2.
 214         AbiAndPrefAlign::new(Align::from_bytes(vec_size.bytes().next_power_of_two()).unwrap())
 215     }
 216 }
 217
 218 pub trait HasDataLayout {
 219     fn data_layout(&self) -> &TargetDataLayout;
 220 }
 221
 222 impl HasDataLayout for TargetDataLayout {
 223     fn data_layout(&self) -> &TargetDataLayout {
 224         self
 225     }
 226 }
 227
 228 /// Endianness of the target, which must match cfg(target-endian).
 229 #[derive(Copy, Clone, PartialEq)]
 230 pub enum Endian {
 231     Little,
 232     Big,
 233 }
 234
 235 /// Size of a type in bytes.
 236 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 237 #[derive(HashStable_Generic)]
 238 pub struct Size {
 239     raw: u64,
 240 }
 241
 242 impl Size {
 243     pub const ZERO: Size = Self::from_bytes(0);
 244
 245     #[inline]
 246     pub fn from_bits(bits: u64) -> Size {
 247         // Avoid potential overflow from `bits + 7`.
 248         Size::from_bytes(bits / 8 + ((bits % 8) + 7) / 8)
 249     }
 250
 251     #[inline]
 252     pub const fn from_bytes(bytes: u64) -> Size {
 253         Size { raw: bytes }
 254     }
 255
 256     #[inline]
 257     pub fn bytes(self) -> u64 {
 258         self.raw
 259     }
 260
 261     #[inline]
 262     pub fn bits(self) -> u64 {
 263         self.bytes().checked_mul(8).unwrap_or_else(|| {
 264             panic!("Size::bits: {} bytes in bits doesn't fit in u64", self.bytes())
 265         })
 266     }
 267
 268     #[inline]
 269     pub fn align_to(self, align: Align) -> Size {
 270         let mask = align.bytes() - 1;
 271         Size::from_bytes((self.bytes() + mask) & !mask)
 272     }
 273
 274     #[inline]
 275     pub fn is_aligned(self, align: Align) -> bool {
 276         let mask = align.bytes() - 1;
 277         self.bytes() & mask == 0
 278     }
 279
 280     #[inline]
 281     pub fn checked_add<C: HasDataLayout>(self, offset: Size, cx: &C) -> Option<Size> {
 282         let dl = cx.data_layout();
 283
 284         let bytes = self.bytes().checked_add(offset.bytes())?;
 285
 286         if bytes < dl.obj_size_bound() { Some(Size::from_bytes(bytes)) } else { None }
 287     }
 288
 289     #[inline]
 290     pub fn checked_mul<C: HasDataLayout>(self, count: u64, cx: &C) -> Option<Size> {
 291         let dl = cx.data_layout();
 292
 293         let bytes = self.bytes().checked_mul(count)?;
 294         if bytes < dl.obj_size_bound() { Some(Size::from_bytes(bytes)) } else { None }
 295     }
 296 }
 297
 298 // Panicking addition, subtraction and multiplication for convenience.
 299 // Avoid during layout computation, return `LayoutError` instead.
 300
 301 impl Add for Size {
 302     type Output = Size;
 303     #[inline]
 304     fn add(self, other: Size) -> Size {
 305         Size::from_bytes(self.bytes().checked_add(other.bytes()).unwrap_or_else(|| {
 306             panic!("Size::add: {} + {} doesn't fit in u64", self.bytes(), other.bytes())
 307         }))
 308     }
 309 }
 310
 311 impl Sub for Size {
 312     type Output = Size;
 313     #[inline]
 314     fn sub(self, other: Size) -> Size {
 315         Size::from_bytes(self.bytes().checked_sub(other.bytes()).unwrap_or_else(|| {
 316             panic!("Size::sub: {} - {} would result in negative size", self.bytes(), other.bytes())
 317         }))
 318     }
 319 }
 320
 321 impl Mul<Size> for u64 {
 322     type Output = Size;
 323     #[inline]
 324     fn mul(self, size: Size) -> Size {
 325         size * self
 326     }
 327 }
 328
 329 impl Mul<u64> for Size {
 330     type Output = Size;
 331     #[inline]
 332     fn mul(self, count: u64) -> Size {
 333         match self.bytes().checked_mul(count) {
 334             Some(bytes) => Size::from_bytes(bytes),
 335             None => panic!("Size::mul: {} * {} doesn't fit in u64", self.bytes(), count),
 336         }
 337     }
 338 }
 339
 340 impl AddAssign for Size {
 341     #[inline]
 342     fn add_assign(&mut self, other: Size) {
 343         *self = *self + other;
 344     }
 345 }
 346
 347 /// Alignment of a type in bytes (always a power of two).
 348 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, RustcEncodable, RustcDecodable)]
 349 #[derive(HashStable_Generic)]
 350 pub struct Align {
 351     pow2: u8,
 352 }
 353
 354 impl Align {
 355     pub fn from_bits(bits: u64) -> Result<Align, String> {
 356         Align::from_bytes(Size::from_bits(bits).bytes())
 357     }
 358
 359     pub fn from_bytes(align: u64) -> Result<Align, String> {
 360         // Treat an alignment of 0 bytes like 1-byte alignment.
 361         if align == 0 {
 362             return Ok(Align { pow2: 0 });
 363         }
 364
 365         let mut bytes = align;
 366         let mut pow2: u8 = 0;
 367         while (bytes & 1) == 0 {
 368             pow2 += 1;
 369             bytes >>= 1;
 370         }
 371         if bytes != 1 {
 372             return Err(format!("`{}` is not a power of 2", align));
 373         }
 374         if pow2 > 29 {
 375             return Err(format!("`{}` is too large", align));
 376         }
 377
 378         Ok(Align { pow2 })
 379     }
 380
 381     pub fn bytes(self) -> u64 {
 382         1 << self.pow2
 383     }
 384
 385     pub fn bits(self) -> u64 {
 386         self.bytes() * 8
 387     }
 388
 389     /// Computes the best alignment possible for the given offset
 390     /// (the largest power of two that the offset is a multiple of).
 391     ///
 392     /// N.B., for an offset of `0`, this happens to return `2^64`.
 393     pub fn max_for_offset(offset: Size) -> Align {
 394         Align { pow2: offset.bytes().trailing_zeros() as u8 }
 395     }
 396
 397     /// Lower the alignment, if necessary, such that the given offset
 398     /// is aligned to it (the offset is a multiple of the alignment).
 399     pub fn restrict_for_offset(self, offset: Size) -> Align {
 400         self.min(Align::max_for_offset(offset))
 401     }
 402 }
 403
 404 /// A pair of alignments, ABI-mandated and preferred.
 405 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
 406 #[derive(HashStable_Generic)]
 407 pub struct AbiAndPrefAlign {
 408     pub abi: Align,
 409     pub pref: Align,
 410 }
 411
 412 impl AbiAndPrefAlign {
 413     pub fn new(align: Align) -> AbiAndPrefAlign {
 414         AbiAndPrefAlign { abi: align, pref: align }
 415     }
 416
 417     pub fn min(self, other: AbiAndPrefAlign) -> AbiAndPrefAlign {
 418         AbiAndPrefAlign { abi: self.abi.min(other.abi), pref: self.pref.min(other.pref) }
 419     }
 420
 421     pub fn max(self, other: AbiAndPrefAlign) -> AbiAndPrefAlign {
 422         AbiAndPrefAlign { abi: self.abi.max(other.abi), pref: self.pref.max(other.pref) }
 423     }
 424 }
 425
 426 /// Integers, also used for enum discriminants.
 427 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Debug, HashStable_Generic)]
 428 pub enum Integer {
 429     I8,
 430     I16,
 431     I32,
 432     I64,
 433     I128,
 434 }
 435
 436 impl Integer {
 437     pub fn size(self) -> Size {
 438         match self {
 439             I8 => Size::from_bytes(1),
 440             I16 => Size::from_bytes(2),
 441             I32 => Size::from_bytes(4),
 442             I64 => Size::from_bytes(8),
 443             I128 => Size::from_bytes(16),
 444         }
 445     }
 446
 447     pub fn align<C: HasDataLayout>(self, cx: &C) -> AbiAndPrefAlign {
 448         let dl = cx.data_layout();
 449
 450         match self {
 451             I8 => dl.i8_align,
 452             I16 => dl.i16_align,
 453             I32 => dl.i32_align,
 454             I64 => dl.i64_align,
 455             I128 => dl.i128_align,
 456         }
 457     }
 458
 459     /// Finds the smallest Integer type which can represent the signed value.
 460     pub fn fit_signed(x: i128) -> Integer {
 461         match x {
 462             -0x0000_0000_0000_0080..=0x0000_0000_0000_007f => I8,
 463             -0x0000_0000_0000_8000..=0x0000_0000_0000_7fff => I16,
 464             -0x0000_0000_8000_0000..=0x0000_0000_7fff_ffff => I32,
 465             -0x8000_0000_0000_0000..=0x7fff_ffff_ffff_ffff => I64,
 466             _ => I128,
 467         }
 468     }
 469
 470     /// Finds the smallest Integer type which can represent the unsigned value.
 471     pub fn fit_unsigned(x: u128) -> Integer {
 472         match x {
 473             0..=0x0000_0000_0000_00ff => I8,
 474             0..=0x0000_0000_0000_ffff => I16,
 475             0..=0x0000_0000_ffff_ffff => I32,
 476             0..=0xffff_ffff_ffff_ffff => I64,
 477             _ => I128,
 478         }
 479     }
 480
 481     /// Finds the smallest integer with the given alignment.
 482     pub fn for_align<C: HasDataLayout>(cx: &C, wanted: Align) -> Option<Integer> {
 483         let dl = cx.data_layout();
 484
 485         for &candidate in &[I8, I16, I32, I64, I128] {
 486             if wanted == candidate.align(dl).abi && wanted.bytes() == candidate.size().bytes() {
 487                 return Some(candidate);
 488             }
 489         }
 490         None
 491     }
 492
 493     /// Find the largest integer with the given alignment or less.
 494     pub fn approximate_align<C: HasDataLayout>(cx: &C, wanted: Align) -> Integer {
 495         let dl = cx.data_layout();
 496
 497         // FIXME(eddyb) maybe include I128 in the future, when it works everywhere.
 498         for &candidate in &[I64, I32, I16] {
 499             if wanted >= candidate.align(dl).abi && wanted.bytes() >= candidate.size().bytes() {
 500                 return candidate;
 501             }
 502         }
 503         I8
 504     }
 505 }
 506
 507 /// Fundamental unit of memory access and layout.
 508 #[derive(Copy, Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 509 pub enum Primitive {
 510     /// The `bool` is the signedness of the `Integer` type.
 511     ///
 512     /// One would think we would not care about such details this low down,
 513     /// but some ABIs are described in terms of C types and ISAs where the
 514     /// integer arithmetic is done on {sign,zero}-extended registers, e.g.
 515     /// a negative integer passed by zero-extension will appear positive in
 516     /// the callee, and most operations on it will produce the wrong values.
 517     Int(Integer, bool),
 518     F32,
 519     F64,
 520     Pointer,
 521 }
 522
 523 impl Primitive {
 524     pub fn size<C: HasDataLayout>(self, cx: &C) -> Size {
 525         let dl = cx.data_layout();
 526
 527         match self {
 528             Int(i, _) => i.size(),
 529             F32 => Size::from_bits(32),
 530             F64 => Size::from_bits(64),
 531             Pointer => dl.pointer_size,
 532         }
 533     }
 534
 535     pub fn align<C: HasDataLayout>(self, cx: &C) -> AbiAndPrefAlign {
 536         let dl = cx.data_layout();
 537
 538         match self {
 539             Int(i, _) => i.align(dl),
 540             F32 => dl.f32_align,
 541             F64 => dl.f64_align,
 542             Pointer => dl.pointer_align,
 543         }
 544     }
 545
 546     pub fn is_float(self) -> bool {
 547         match self {
 548             F32 | F64 => true,
 549             _ => false,
 550         }
 551     }
 552
 553     pub fn is_int(self) -> bool {
 554         match self {
 555             Int(..) => true,
 556             _ => false,
 557         }
 558     }
 559 }
 560
 561 /// Information about one scalar component of a Rust type.
 562 #[derive(Clone, PartialEq, Eq, Hash, Debug)]
 563 #[derive(HashStable_Generic)]
 564 pub struct Scalar {
 565     pub value: Primitive,
 566
 567     /// Inclusive wrap-around range of valid values, that is, if
 568     /// start > end, it represents `start..=max_value()`,
 569     /// followed by `0..=end`.
 570     ///
 571     /// That is, for an i8 primitive, a range of `254..=2` means following
 572     /// sequence:
 573     ///
 574     ///    254 (-2), 255 (-1), 0, 1, 2
 575     ///
 576     /// This is intended specifically to mirror LLVM’s `!range` metadata,
 577     /// semantics.
 578     // FIXME(eddyb) always use the shortest range, e.g., by finding
 579     // the largest space between two consecutive valid values and
 580     // taking everything else as the (shortest) valid range.
 581     pub valid_range: RangeInclusive<u128>,
 582 }
 583
 584 impl Scalar {
 585     pub fn is_bool(&self) -> bool {
 586         if let Int(I8, _) = self.value { self.valid_range == (0..=1) } else { false }
 587     }
 588
 589     /// Returns the valid range as a `x..y` range.
 590     ///
 591     /// If `x` and `y` are equal, the range is full, not empty.
 592     pub fn valid_range_exclusive<C: HasDataLayout>(&self, cx: &C) -> Range<u128> {
 593         // For a (max) value of -1, max will be `-1 as usize`, which overflows.
 594         // However, that is fine here (it would still represent the full range),
 595         // i.e., if the range is everything.
 596         let bits = self.value.size(cx).bits();
 597         assert!(bits <= 128);
 598         let mask = !0u128 >> (128 - bits);
 599         let start = *self.valid_range.start();
 600         let end = *self.valid_range.end();
 601         assert_eq!(start, start & mask);
 602         assert_eq!(end, end & mask);
 603         start..(end.wrapping_add(1) & mask)
 604     }
 605 }
 606
 607 /// Describes how the fields of a type are located in memory.
 608 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 609 pub enum FieldPlacement {
 610     /// All fields start at no offset. The `usize` is the field count.
 611     ///
 612     /// In the case of primitives the number of fields is `0`.
 613     Union(usize),
 614
 615     /// Array/vector-like placement, with all fields of identical types.
 616     Array { stride: Size, count: u64 },
 617
 618     /// Struct-like placement, with precomputed offsets.
 619     ///
 620     /// Fields are guaranteed to not overlap, but note that gaps
 621     /// before, between and after all the fields are NOT always
 622     /// padding, and as such their contents may not be discarded.
 623     /// For example, enum variants leave a gap at the start,
 624     /// where the discriminant field in the enum layout goes.
 625     Arbitrary {
 626         /// Offsets for the first byte of each field,
 627         /// ordered to match the source definition order.
 628         /// This vector does not go in increasing order.
 629         // FIXME(eddyb) use small vector optimization for the common case.
 630         offsets: Vec<Size>,
 631
 632         /// Maps source order field indices to memory order indices,
 633         /// depending on how the fields were reordered (if at all).
 634         /// This is a permutation, with both the source order and the
 635         /// memory order using the same (0..n) index ranges.
 636         ///
 637         /// Note that during computation of `memory_index`, sometimes
 638         /// it is easier to operate on the inverse mapping (that is,
 639         /// from memory order to source order), and that is usually
 640         /// named `inverse_memory_index`.
 641         ///
 642         // FIXME(eddyb) build a better abstraction for permutations, if possible.
 643         // FIXME(camlorn) also consider small vector  optimization here.
 644         memory_index: Vec<u32>,
 645     },
 646 }
 647
 648 impl FieldPlacement {
 649     pub fn count(&self) -> usize {
 650         match *self {
 651             FieldPlacement::Union(count) => count,
 652             FieldPlacement::Array { count, .. } => {
 653                 let usize_count = count as usize;
 654                 assert_eq!(usize_count as u64, count);
 655                 usize_count
 656             }
 657             FieldPlacement::Arbitrary { ref offsets, .. } => offsets.len(),
 658         }
 659     }
 660
 661     pub fn offset(&self, i: usize) -> Size {
 662         match *self {
 663             FieldPlacement::Union(count) => {
 664                 assert!(i < count, "tried to access field {} of union with {} fields", i, count);
 665                 Size::ZERO
 666             }
 667             FieldPlacement::Array { stride, count } => {
 668                 let i = i as u64;
 669                 assert!(i < count);
 670                 stride * i
 671             }
 672             FieldPlacement::Arbitrary { ref offsets, .. } => offsets[i],
 673         }
 674     }
 675
 676     pub fn memory_index(&self, i: usize) -> usize {
 677         match *self {
 678             FieldPlacement::Union(_) | FieldPlacement::Array { .. } => i,
 679             FieldPlacement::Arbitrary { ref memory_index, .. } => {
 680                 let r = memory_index[i];
 681                 assert_eq!(r as usize as u32, r);
 682                 r as usize
 683             }
 684         }
 685     }
 686
 687     /// Gets source indices of the fields by increasing offsets.
 688     #[inline]
 689     pub fn index_by_increasing_offset<'a>(&'a self) -> impl Iterator<Item = usize> + 'a {
 690         let mut inverse_small = [0u8; 64];
 691         let mut inverse_big = vec![];
 692         let use_small = self.count() <= inverse_small.len();
 693
 694         // We have to write this logic twice in order to keep the array small.
 695         if let FieldPlacement::Arbitrary { ref memory_index, .. } = *self {
 696             if use_small {
 697                 for i in 0..self.count() {
 698                     inverse_small[memory_index[i] as usize] = i as u8;
 699                 }
 700             } else {
 701                 inverse_big = vec![0; self.count()];
 702                 for i in 0..self.count() {
 703                     inverse_big[memory_index[i] as usize] = i as u32;
 704                 }
 705             }
 706         }
 707
 708         (0..self.count()).map(move |i| match *self {
 709             FieldPlacement::Union(_) | FieldPlacement::Array { .. } => i,
 710             FieldPlacement::Arbitrary { .. } => {
 711                 if use_small {
 712                     inverse_small[i] as usize
 713                 } else {
 714                     inverse_big[i] as usize
 715                 }
 716             }
 717         })
 718     }
 719 }
 720
 721 /// Describes how values of the type are passed by target ABIs,
 722 /// in terms of categories of C types there are ABI rules for.
 723 #[derive(Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 724 pub enum Abi {
 725     Uninhabited,
 726     Scalar(Scalar),
 727     ScalarPair(Scalar, Scalar),
 728     Vector {
 729         element: Scalar,
 730         count: u64,
 731     },
 732     Aggregate {
 733         /// If true, the size is exact, otherwise it's only a lower bound.
 734         sized: bool,
 735     },
 736 }
 737
 738 impl Abi {
 739     /// Returns `true` if the layout corresponds to an unsized type.
 740     pub fn is_unsized(&self) -> bool {
 741         match *self {
 742             Abi::Uninhabited | Abi::Scalar(_) | Abi::ScalarPair(..) | Abi::Vector { .. } => false,
 743             Abi::Aggregate { sized } => !sized,
 744         }
 745     }
 746
 747     /// Returns `true` if this is a single signed integer scalar
 748     pub fn is_signed(&self) -> bool {
 749         match *self {
 750             Abi::Scalar(ref scal) => match scal.value {
 751                 Primitive::Int(_, signed) => signed,
 752                 _ => false,
 753             },
 754             _ => false,
 755         }
 756     }
 757
 758     /// Returns `true` if this is an uninhabited type
 759     pub fn is_uninhabited(&self) -> bool {
 760         match *self {
 761             Abi::Uninhabited => true,
 762             _ => false,
 763         }
 764     }
 765
 766     /// Returns `true` is this is a scalar type
 767     pub fn is_scalar(&self) -> bool {
 768         match *self {
 769             Abi::Scalar(_) => true,
 770             _ => false,
 771         }
 772     }
 773 }
 774
 775 rustc_index::newtype_index! {
 776     pub struct VariantIdx {
 777         derive [HashStable_Generic]
 778     }
 779 }
 780
 781 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 782 pub enum Variants {
 783     /// Single enum variants, structs/tuples, unions, and all non-ADTs.
 784     Single { index: VariantIdx },
 785
 786     /// Enum-likes with more than one inhabited variant: for each case there is
 787     /// a struct, and they all have space reserved for the discriminant.
 788     /// For enums this is the sole field of the layout.
 789     Multiple {
 790         discr: Scalar,
 791         discr_kind: DiscriminantKind,
 792         discr_index: usize,
 793         variants: IndexVec<VariantIdx, LayoutDetails>,
 794     },
 795 }
 796
 797 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 798 pub enum DiscriminantKind {
 799     /// Integer tag holding the discriminant value itself.
 800     Tag,
 801
 802     /// Niche (values invalid for a type) encoding the discriminant:
 803     /// the variant `dataful_variant` contains a niche at an arbitrary
 804     /// offset (field `discr_index` of the enum), which for a variant with
 805     /// discriminant `d` is set to
 806     /// `(d - niche_variants.start).wrapping_add(niche_start)`.
 807     ///
 808     /// For example, `Option<(usize, &T)>`  is represented such that
 809     /// `None` has a null pointer for the second tuple field, and
 810     /// `Some` is the identity function (with a non-null reference).
 811     Niche {
 812         dataful_variant: VariantIdx,
 813         niche_variants: RangeInclusive<VariantIdx>,
 814         niche_start: u128,
 815     },
 816 }
 817
 818 #[derive(Clone, PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 819 pub struct Niche {
 820     pub offset: Size,
 821     pub scalar: Scalar,
 822 }
 823
 824 impl Niche {
 825     pub fn from_scalar<C: HasDataLayout>(cx: &C, offset: Size, scalar: Scalar) -> Option<Self> {
 826         let niche = Niche { offset, scalar };
 827         if niche.available(cx) > 0 { Some(niche) } else { None }
 828     }
 829
 830     pub fn available<C: HasDataLayout>(&self, cx: &C) -> u128 {
 831         let Scalar { value, valid_range: ref v } = self.scalar;
 832         let bits = value.size(cx).bits();
 833         assert!(bits <= 128);
 834         let max_value = !0u128 >> (128 - bits);
 835
 836         // Find out how many values are outside the valid range.
 837         let niche = v.end().wrapping_add(1)..*v.start();
 838         niche.end.wrapping_sub(niche.start) & max_value
 839     }
 840
 841     pub fn reserve<C: HasDataLayout>(&self, cx: &C, count: u128) -> Option<(u128, Scalar)> {
 842         assert!(count > 0);
 843
 844         let Scalar { value, valid_range: ref v } = self.scalar;
 845         let bits = value.size(cx).bits();
 846         assert!(bits <= 128);
 847         let max_value = !0u128 >> (128 - bits);
 848
 849         if count > max_value {
 850             return None;
 851         }
 852
 853         // Compute the range of invalid values being reserved.
 854         let start = v.end().wrapping_add(1) & max_value;
 855         let end = v.end().wrapping_add(count) & max_value;
 856
 857         // If the `end` of our range is inside the valid range,
 858         // then we ran out of invalid values.
 859         // FIXME(eddyb) abstract this with a wraparound range type.
 860         let valid_range_contains = |x| {
 861             if v.start() <= v.end() {
 862                 *v.start() <= x && x <= *v.end()
 863             } else {
 864                 *v.start() <= x || x <= *v.end()
 865             }
 866         };
 867         if valid_range_contains(end) {
 868             return None;
 869         }
 870
 871         Some((start, Scalar { value, valid_range: *v.start()..=end }))
 872     }
 873 }
 874
 875 #[derive(PartialEq, Eq, Hash, Debug, HashStable_Generic)]
 876 pub struct LayoutDetails {
 877     /// Says where the fields are located within the layout.
 878     /// Primitives and uninhabited enums appear as unions without fields.
 879     pub fields: FieldPlacement,
 880
 881     /// Encodes information about multi-variant layouts.
 882     /// Even with `Multiple` variants, a layout still has its own fields! Those are then
 883     /// shared between all variants. One of them will be the discriminant,
 884     /// but e.g. generators can have more.
 885     ///
 886     /// To access all fields of this layout, both `fields` and the fields of the active variant
 887     /// must be taken into account.
 888     pub variants: Variants,
 889
 890     /// The `abi` defines how this data is passed between functions, and it defines
 891     /// value restrictions via `valid_range`.
 892     ///
 893     /// Note that this is entirely orthogonal to the recursive structure defined by
 894     /// `variants` and `fields`; for example, `ManuallyDrop<Result<isize, isize>>` has
 895     /// `Abi::ScalarPair`! So, even with non-`Aggregate` `abi`, `fields` and `variants`
 896     /// have to be taken into account to find all fields of this layout.
 897     pub abi: Abi,
 898
 899     /// The leaf scalar with the largest number of invalid values
 900     /// (i.e. outside of its `valid_range`), if it exists.
 901     pub largest_niche: Option<Niche>,
 902
 903     pub align: AbiAndPrefAlign,
 904     pub size: Size,
 905 }
 906
 907 impl LayoutDetails {
 908     pub fn scalar<C: HasDataLayout>(cx: &C, scalar: Scalar) -> Self {
 909         let largest_niche = Niche::from_scalar(cx, Size::ZERO, scalar.clone());
 910         let size = scalar.value.size(cx);
 911         let align = scalar.value.align(cx);
 912         LayoutDetails {
 913             variants: Variants::Single { index: VariantIdx::new(0) },
 914             fields: FieldPlacement::Union(0),
 915             abi: Abi::Scalar(scalar),
 916             largest_niche,
 917             size,
 918             align,
 919         }
 920     }
 921 }
 922
 923 /// The details of the layout of a type, alongside the type itself.
 924 /// Provides various type traversal APIs (e.g., recursing into fields).
 925 ///
 926 /// Note that the details are NOT guaranteed to always be identical
 927 /// to those obtained from `layout_of(ty)`, as we need to produce
 928 /// layouts for which Rust types do not exist, such as enum variants
 929 /// or synthetic fields of enums (i.e., discriminants) and fat pointers.
 930 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
 931 pub struct TyLayout<'a, Ty> {
 932     pub ty: Ty,
 933     pub details: &'a LayoutDetails,
 934 }
 935
 936 impl<'a, Ty> Deref for TyLayout<'a, Ty> {
 937     type Target = &'a LayoutDetails;
 938     fn deref(&self) -> &&'a LayoutDetails {
 939         &self.details
 940     }
 941 }
 942
 943 /// Trait for context types that can compute layouts of things.
 944 pub trait LayoutOf {
 945     type Ty;
 946     type TyLayout;
 947
 948     fn layout_of(&self, ty: Self::Ty) -> Self::TyLayout;
 949     fn spanned_layout_of(&self, ty: Self::Ty, _span: Span) -> Self::TyLayout {
 950         self.layout_of(ty)
 951     }
 952 }
 953
 954 /// The `TyLayout` above will always be a `MaybeResult<TyLayout<'_, Self>>`.
 955 /// We can't add the bound due to the lifetime, but this trait is still useful when
 956 /// writing code that's generic over the `LayoutOf` impl.
 957 pub trait MaybeResult<T> {
 958     type Error;
 959
 960     fn from(x: Result<T, Self::Error>) -> Self;
 961     fn to_result(self) -> Result<T, Self::Error>;
 962 }
 963
 964 impl<T> MaybeResult<T> for T {
 965     type Error = !;
 966
 967     fn from(Ok(x): Result<T, Self::Error>) -> Self {
 968         x
 969     }
 970     fn to_result(self) -> Result<T, Self::Error> {
 971         Ok(self)
 972     }
 973 }
 974
 975 impl<T, E> MaybeResult<T> for Result<T, E> {
 976     type Error = E;
 977
 978     fn from(x: Result<T, Self::Error>) -> Self {
 979         x
 980     }
 981     fn to_result(self) -> Result<T, Self::Error> {
 982         self
 983     }
 984 }
 985
 986 #[derive(Copy, Clone, PartialEq, Eq)]
 987 pub enum PointerKind {
 988     /// Most general case, we know no restrictions to tell LLVM.
 989     Shared,
 990
 991     /// `&T` where `T` contains no `UnsafeCell`, is `noalias` and `readonly`.
 992     Frozen,
 993
 994     /// `&mut T`, when we know `noalias` is safe for LLVM.
 995     UniqueBorrowed,
 996
 997     /// `Box<T>`, unlike `UniqueBorrowed`, it also has `noalias` on returns.
 998     UniqueOwned,
 999 }
1000
1001 #[derive(Copy, Clone)]
1002 pub struct PointeeInfo {
1003     pub size: Size,
1004     pub align: Align,
1005     pub safe: Option<PointerKind>,
1006 }
1007
1008 pub trait TyLayoutMethods<'a, C: LayoutOf<Ty = Self>>: Sized {
1009     fn for_variant(
1010         this: TyLayout<'a, Self>,
1011         cx: &C,
1012         variant_index: VariantIdx,
1013     ) -> TyLayout<'a, Self>;
1014     fn field(this: TyLayout<'a, Self>, cx: &C, i: usize) -> C::TyLayout;
1015     fn pointee_info_at(this: TyLayout<'a, Self>, cx: &C, offset: Size) -> Option<PointeeInfo>;
1016 }
1017
1018 impl<'a, Ty> TyLayout<'a, Ty> {
1019     pub fn for_variant<C>(self, cx: &C, variant_index: VariantIdx) -> Self
1020     where
1021         Ty: TyLayoutMethods<'a, C>,
1022         C: LayoutOf<Ty = Ty>,
1023     {
1024         Ty::for_variant(self, cx, variant_index)
1025     }
1026
1027     /// Callers might want to use `C: LayoutOf<Ty=Ty, TyLayout: MaybeResult<Self>>`
1028     /// to allow recursion (see `might_permit_zero_init` below for an example).
1029     pub fn field<C>(self, cx: &C, i: usize) -> C::TyLayout
1030     where
1031         Ty: TyLayoutMethods<'a, C>,
1032         C: LayoutOf<Ty = Ty>,
1033     {
1034         Ty::field(self, cx, i)
1035     }
1036
1037     pub fn pointee_info_at<C>(self, cx: &C, offset: Size) -> Option<PointeeInfo>
1038     where
1039         Ty: TyLayoutMethods<'a, C>,
1040         C: LayoutOf<Ty = Ty>,
1041     {
1042         Ty::pointee_info_at(self, cx, offset)
1043     }
1044 }
1045
1046 impl<'a, Ty> TyLayout<'a, Ty> {
1047     /// Returns `true` if the layout corresponds to an unsized type.
1048     pub fn is_unsized(&self) -> bool {
1049         self.abi.is_unsized()
1050     }
1051
1052     /// Returns `true` if the type is a ZST and not unsized.
1053     pub fn is_zst(&self) -> bool {
1054         match self.abi {
1055             Abi::Scalar(_) | Abi::ScalarPair(..) | Abi::Vector { .. } => false,
1056             Abi::Uninhabited => self.size.bytes() == 0,
1057             Abi::Aggregate { sized } => sized && self.size.bytes() == 0,
1058         }
1059     }
1060
1061     /// Determines if this type permits "raw" initialization by just transmuting some
1062     /// memory into an instance of `T`.
1063     /// `zero` indicates if the memory is zero-initialized, or alternatively
1064     /// left entirely uninitialized.
1065     /// This is conservative: in doubt, it will answer `true`.
1066     ///
1067     /// FIXME: Once we removed all the conservatism, we could alternatively
1068     /// create an all-0/all-undef constant and run the const value validator to see if
1069     /// this is a valid value for the given type.
1070     pub fn might_permit_raw_init<C, E>(self, cx: &C, zero: bool) -> Result<bool, E>
1071     where
1072         Self: Copy,
1073         Ty: TyLayoutMethods<'a, C>,
1074         C: LayoutOf<Ty = Ty, TyLayout: MaybeResult<Self, Error = E>> + HasDataLayout,
1075     {
1076         let scalar_allows_raw_init = move |s: &Scalar| -> bool {
1077             if zero {
1078                 let range = &s.valid_range;
1079                 // The range must contain 0.
1080                 range.contains(&0) || (*range.start() > *range.end()) // wrap-around allows 0
1081             } else {
1082                 // The range must include all values. `valid_range_exclusive` handles
1083                 // the wrap-around using target arithmetic; with wrap-around then the full
1084                 // range is one where `start == end`.
1085                 let range = s.valid_range_exclusive(cx);
1086                 range.start == range.end
1087             }
1088         };
1089
1090         // Check the ABI.
1091         let valid = match &self.abi {
1092             Abi::Uninhabited => false, // definitely UB
1093             Abi::Scalar(s) => scalar_allows_raw_init(s),
1094             Abi::ScalarPair(s1, s2) => scalar_allows_raw_init(s1) && scalar_allows_raw_init(s2),
1095             Abi::Vector { element: s, count } => *count == 0 || scalar_allows_raw_init(s),
1096             Abi::Aggregate { .. } => true, // Cannot be excluded *right now*.
1097         };
1098         if !valid {
1099             // This is definitely not okay.
1100             trace!("might_permit_raw_init({:?}, zero={}): not valid", self.details, zero);
1101             return Ok(false);
1102         }
1103
1104         // If we have not found an error yet, we need to recursively descend.
1105         // FIXME(#66151): For now, we are conservative and do not do this.
1106         Ok(true)
1107     }
1108 }