src/librustc_trans/trans/adt.rs

   1 // Copyright 2013 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 //! # Representation of Algebraic Data Types
  12 //!
  13 //! This module determines how to represent enums, structs, and tuples
  14 //! based on their monomorphized types; it is responsible both for
  15 //! choosing a representation and translating basic operations on
  16 //! values of those types.  (Note: exporting the representations for
  17 //! debuggers is handled in debuginfo.rs, not here.)
  18 //!
  19 //! Note that the interface treats everything as a general case of an
  20 //! enum, so structs/tuples/etc. have one pseudo-variant with
  21 //! discriminant 0; i.e., as if they were a univariant enum.
  22 //!
  23 //! Having everything in one place will enable improvements to data
  24 //! structure representation; possibilities include:
  25 //!
  26 //! - User-specified alignment (e.g., cacheline-aligning parts of
  27 //!   concurrently accessed data structures); LLVM can't represent this
  28 //!   directly, so we'd have to insert padding fields in any structure
  29 //!   that might contain one and adjust GEP indices accordingly.  See
  30 //!   issue #4578.
  31 //!
  32 //! - Store nested enums' discriminants in the same word.  Rather, if
  33 //!   some variants start with enums, and those enums representations
  34 //!   have unused alignment padding between discriminant and body, the
  35 //!   outer enum's discriminant can be stored there and those variants
  36 //!   can start at offset 0.  Kind of fancy, and might need work to
  37 //!   make copies of the inner enum type cooperate, but it could help
  38 //!   with `Option` or `Result` wrapped around another enum.
  39 //!
  40 //! - Tagged pointers would be neat, but given that any type can be
  41 //!   used unboxed and any field can have pointers (including mutable)
  42 //!   taken to it, implementing them for Rust seems difficult.
  43
  44 #![allow(unsigned_negation)]
  45
  46 pub use self::Repr::*;
  47
  48 use std::rc::Rc;
  49
  50 use llvm::{ValueRef, True, IntEQ, IntNE};
  51 use back::abi::FAT_PTR_ADDR;
  52 use middle::subst;
  53 use middle::ty::{self, Ty, ClosureTyper};
  54 use middle::ty::Disr;
  55 use syntax::ast;
  56 use syntax::attr;
  57 use syntax::attr::IntType;
  58 use trans::_match;
  59 use trans::build::*;
  60 use trans::cleanup;
  61 use trans::cleanup::CleanupMethods;
  62 use trans::common::*;
  63 use trans::datum;
  64 use trans::debuginfo::DebugLoc;
  65 use trans::machine;
  66 use trans::monomorphize;
  67 use trans::type_::Type;
  68 use trans::type_of;
  69 use util::ppaux::ty_to_string;
  70
  71 type Hint = attr::ReprAttr;
  72
  73 /// Representations.
  74 #[derive(Eq, PartialEq, Debug)]
  75 pub enum Repr<'tcx> {
  76     /// C-like enums; basically an int.
  77     CEnum(IntType, Disr, Disr), // discriminant range (signedness based on the IntType)
  78     /// Single-case variants, and structs/tuples/records.
  79     ///
  80     /// Structs with destructors need a dynamic destroyedness flag to
  81     /// avoid running the destructor too many times; this is included
  82     /// in the `Struct` if present.
  83     /// (The flag if nonzero, represents the initialization value to use;
  84     ///  if zero, then use no flag at all.)
  85     Univariant(Struct<'tcx>, u8),
  86     /// General-case enums: for each case there is a struct, and they
  87     /// all start with a field for the discriminant.
  88     ///
  89     /// Types with destructors need a dynamic destroyedness flag to
  90     /// avoid running the destructor too many times; the last argument
  91     /// indicates whether such a flag is present.
  92     /// (The flag, if nonzero, represents the initialization value to use;
  93     ///  if zero, then use no flag at all.)
  94     General(IntType, Vec<Struct<'tcx>>, u8),
  95     /// Two cases distinguished by a nullable pointer: the case with discriminant
  96     /// `nndiscr` must have single field which is known to be nonnull due to its type.
  97     /// The other case is known to be zero sized. Hence we represent the enum
  98     /// as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
  99     /// otherwise it indicates the other case.
 100     RawNullablePointer {
 101         nndiscr: Disr,
 102         nnty: Ty<'tcx>,
 103         nullfields: Vec<Ty<'tcx>>
 104     },
 105     /// Two cases distinguished by a nullable pointer: the case with discriminant
 106     /// `nndiscr` is represented by the struct `nonnull`, where the `discrfield`th
 107     /// field is known to be nonnull due to its type; if that field is null, then
 108     /// it represents the other case, which is inhabited by at most one value
 109     /// (and all other fields are undefined/unused).
 110     ///
 111     /// For example, `std::option::Option` instantiated at a safe pointer type
 112     /// is represented such that `None` is a null pointer and `Some` is the
 113     /// identity function.
 114     StructWrappedNullablePointer {
 115         nonnull: Struct<'tcx>,
 116         nndiscr: Disr,
 117         discrfield: DiscrField,
 118         nullfields: Vec<Ty<'tcx>>,
 119     }
 120 }
 121
 122 /// For structs, and struct-like parts of anything fancier.
 123 #[derive(Eq, PartialEq, Debug)]
 124 pub struct Struct<'tcx> {
 125     // If the struct is DST, then the size and alignment do not take into
 126     // account the unsized fields of the struct.
 127     pub size: u64,
 128     pub align: u32,
 129     pub sized: bool,
 130     pub packed: bool,
 131     pub fields: Vec<Ty<'tcx>>
 132 }
 133
 134 /// Convenience for `represent_type`.  There should probably be more or
 135 /// these, for places in trans where the `Ty` isn't directly
 136 /// available.
 137 pub fn represent_node<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 138                                   node: ast::NodeId) -> Rc<Repr<'tcx>> {
 139     represent_type(bcx.ccx(), node_id_type(bcx, node))
 140 }
 141
 142 /// Decides how to represent a given type.
 143 pub fn represent_type<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 144                                 t: Ty<'tcx>) -> Rc<Repr<'tcx>> {
 145     debug!("Representing: {}", ty_to_string(cx.tcx(), t));
 146     match cx.adt_reprs().borrow().get(&t) {
 147         Some(repr) => return repr.clone(),
 148         None => {}
 149     }
 150
 151     let repr = Rc::new(represent_type_uncached(cx, t));
 152     debug!("Represented as: {:?}", repr);
 153     cx.adt_reprs().borrow_mut().insert(t, repr.clone());
 154     repr
 155 }
 156
 157 macro_rules! repeat_u8_as_u32 {
 158     ($name:expr) => { (($name as u32) << 24 |
 159                        ($name as u32) << 16 |
 160                        ($name as u32) <<  8 |
 161                        ($name as u32)) }
 162 }
 163 macro_rules! repeat_u8_as_u64 {
 164     ($name:expr) => { ((repeat_u8_as_u32!($name) as u64) << 32 |
 165                        (repeat_u8_as_u32!($name) as u64)) }
 166 }
 167
 168 pub const DTOR_NEEDED: u8 = 0xd4;
 169 pub const DTOR_NEEDED_U32: u32 = repeat_u8_as_u32!(DTOR_NEEDED);
 170 pub const DTOR_NEEDED_U64: u64 = repeat_u8_as_u64!(DTOR_NEEDED);
 171 #[allow(dead_code)]
 172 pub fn dtor_needed_usize(ccx: &CrateContext) -> usize {
 173     match &ccx.tcx().sess.target.target.target_pointer_width[..] {
 174         "32" => DTOR_NEEDED_U32 as usize,
 175         "64" => DTOR_NEEDED_U64 as usize,
 176         tws => panic!("Unsupported target word size for int: {}", tws),
 177     }
 178 }
 179
 180 pub const DTOR_DONE: u8 = 0x1d;
 181 pub const DTOR_DONE_U32: u32 = repeat_u8_as_u32!(DTOR_DONE);
 182 pub const DTOR_DONE_U64: u64 = repeat_u8_as_u64!(DTOR_DONE);
 183 #[allow(dead_code)]
 184 pub fn dtor_done_usize(ccx: &CrateContext) -> usize {
 185     match &ccx.tcx().sess.target.target.target_pointer_width[..] {
 186         "32" => DTOR_DONE_U32 as usize,
 187         "64" => DTOR_DONE_U64 as usize,
 188         tws => panic!("Unsupported target word size for int: {}", tws),
 189     }
 190 }
 191
 192 fn dtor_to_init_u8(dtor: bool) -> u8 {
 193     if dtor { DTOR_NEEDED } else { 0 }
 194 }
 195
 196 pub trait GetDtorType<'tcx> { fn dtor_type(&self) -> Ty<'tcx>; }
 197 impl<'tcx> GetDtorType<'tcx> for ty::ctxt<'tcx> {
 198     fn dtor_type(&self) -> Ty<'tcx> { self.types.u8 }
 199 }
 200
 201 fn dtor_active(flag: u8) -> bool {
 202     flag != 0
 203 }
 204
 205 fn represent_type_uncached<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 206                                      t: Ty<'tcx>) -> Repr<'tcx> {
 207     match t.sty {
 208         ty::ty_tup(ref elems) => {
 209             Univariant(mk_struct(cx, &elems[..], false, t), 0)
 210         }
 211         ty::ty_struct(def_id, substs) => {
 212             let fields = ty::lookup_struct_fields(cx.tcx(), def_id);
 213             let mut ftys = fields.iter().map(|field| {
 214                 let fty = ty::lookup_field_type(cx.tcx(), def_id, field.id, substs);
 215                 monomorphize::normalize_associated_type(cx.tcx(), &fty)
 216             }).collect::<Vec<_>>();
 217             let packed = ty::lookup_packed(cx.tcx(), def_id);
 218             let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
 219             if dtor { ftys.push(cx.tcx().dtor_type()); }
 220
 221             Univariant(mk_struct(cx, &ftys[..], packed, t), dtor_to_init_u8(dtor))
 222         }
 223         ty::ty_closure(def_id, substs) => {
 224             let typer = NormalizingClosureTyper::new(cx.tcx());
 225             let upvars = typer.closure_upvars(def_id, substs).unwrap();
 226             let upvar_types = upvars.iter().map(|u| u.ty).collect::<Vec<_>>();
 227             Univariant(mk_struct(cx, &upvar_types[..], false, t), 0)
 228         }
 229         ty::ty_enum(def_id, substs) => {
 230             let cases = get_cases(cx.tcx(), def_id, substs);
 231             let hint = *ty::lookup_repr_hints(cx.tcx(), def_id).get(0)
 232                 .unwrap_or(&attr::ReprAny);
 233
 234             let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
 235
 236             if cases.is_empty() {
 237                 // Uninhabitable; represent as unit
 238                 // (Typechecking will reject discriminant-sizing attrs.)
 239                 assert_eq!(hint, attr::ReprAny);
 240                 let ftys = if dtor { vec!(cx.tcx().dtor_type()) } else { vec!() };
 241                 return Univariant(mk_struct(cx, &ftys[..], false, t),
 242                                   dtor_to_init_u8(dtor));
 243             }
 244
 245             if !dtor && cases.iter().all(|c| c.tys.is_empty()) {
 246                 // All bodies empty -> intlike
 247                 let discrs: Vec<u64> = cases.iter().map(|c| c.discr).collect();
 248                 let bounds = IntBounds {
 249                     ulo: *discrs.iter().min().unwrap(),
 250                     uhi: *discrs.iter().max().unwrap(),
 251                     slo: discrs.iter().map(|n| *n as i64).min().unwrap(),
 252                     shi: discrs.iter().map(|n| *n as i64).max().unwrap()
 253                 };
 254                 return mk_cenum(cx, hint, &bounds);
 255             }
 256
 257             // Since there's at least one
 258             // non-empty body, explicit discriminants should have
 259             // been rejected by a checker before this point.
 260             if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
 261                 cx.sess().bug(&format!("non-C-like enum {} with specified \
 262                                       discriminants",
 263                                       ty::item_path_str(cx.tcx(),
 264                                                         def_id)));
 265             }
 266
 267             if cases.len() == 1 {
 268                 // Equivalent to a struct/tuple/newtype.
 269                 // (Typechecking will reject discriminant-sizing attrs.)
 270                 assert_eq!(hint, attr::ReprAny);
 271                 let mut ftys = cases[0].tys.clone();
 272                 if dtor { ftys.push(cx.tcx().dtor_type()); }
 273                 return Univariant(mk_struct(cx, &ftys[..], false, t),
 274                                   dtor_to_init_u8(dtor));
 275             }
 276
 277             if !dtor && cases.len() == 2 && hint == attr::ReprAny {
 278                 // Nullable pointer optimization
 279                 let mut discr = 0;
 280                 while discr < 2 {
 281                     if cases[1 - discr].is_zerolen(cx, t) {
 282                         let st = mk_struct(cx, &cases[discr].tys,
 283                                            false, t);
 284                         match cases[discr].find_ptr(cx) {
 285                             Some(ref df) if df.len() == 1 && st.fields.len() == 1 => {
 286                                 return RawNullablePointer {
 287                                     nndiscr: discr as Disr,
 288                                     nnty: st.fields[0],
 289                                     nullfields: cases[1 - discr].tys.clone()
 290                                 };
 291                             }
 292                             Some(mut discrfield) => {
 293                                 discrfield.push(0);
 294                                 discrfield.reverse();
 295                                 return StructWrappedNullablePointer {
 296                                     nndiscr: discr as Disr,
 297                                     nonnull: st,
 298                                     discrfield: discrfield,
 299                                     nullfields: cases[1 - discr].tys.clone()
 300                                 };
 301                             }
 302                             None => {}
 303                         }
 304                     }
 305                     discr += 1;
 306                 }
 307             }
 308
 309             // The general case.
 310             assert!((cases.len() - 1) as i64 >= 0);
 311             let bounds = IntBounds { ulo: 0, uhi: (cases.len() - 1) as u64,
 312                                      slo: 0, shi: (cases.len() - 1) as i64 };
 313             let min_ity = range_to_inttype(cx, hint, &bounds);
 314
 315             // Create the set of structs that represent each variant
 316             // Use the minimum integer type we figured out above
 317             let fields : Vec<_> = cases.iter().map(|c| {
 318                 let mut ftys = vec!(ty_of_inttype(cx.tcx(), min_ity));
 319                 ftys.push_all(&c.tys);
 320                 if dtor { ftys.push(cx.tcx().dtor_type()); }
 321                 mk_struct(cx, &ftys, false, t)
 322             }).collect();
 323
 324
 325             // Check to see if we should use a different type for the
 326             // discriminant. If the overall alignment of the type is
 327             // the same as the first field in each variant, we can safely use
 328             // an alignment-sized type.
 329             // We increase the size of the discriminant to avoid LLVM copying
 330             // padding when it doesn't need to. This normally causes unaligned
 331             // load/stores and excessive memcpy/memset operations. By using a
 332             // bigger integer size, LLVM can be sure about it's contents and
 333             // won't be so conservative.
 334             // This check is needed to avoid increasing the size of types when
 335             // the alignment of the first field is smaller than the overall
 336             // alignment of the type.
 337             let (_, align) = union_size_and_align(&fields);
 338             let mut use_align = true;
 339             for st in &fields {
 340                 // Get the first non-zero-sized field
 341                 let field = st.fields.iter().skip(1).filter(|ty| {
 342                     let t = type_of::sizing_type_of(cx, **ty);
 343                     machine::llsize_of_real(cx, t) != 0 ||
 344                     // This case is only relevant for zero-sized types with large alignment
 345                     machine::llalign_of_min(cx, t) != 1
 346                 }).next();
 347
 348                 if let Some(field) = field {
 349                     let field_align = type_of::align_of(cx, *field);
 350                     if field_align != align {
 351                         use_align = false;
 352                         break;
 353                     }
 354                 }
 355             }
 356             let ity = if use_align {
 357                 // Use the overall alignment
 358                 match align {
 359                     1 => attr::UnsignedInt(ast::TyU8),
 360                     2 => attr::UnsignedInt(ast::TyU16),
 361                     4 => attr::UnsignedInt(ast::TyU32),
 362                     8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
 363                         attr::UnsignedInt(ast::TyU64),
 364                     _ => min_ity // use min_ity as a fallback
 365                 }
 366             } else {
 367                 min_ity
 368             };
 369
 370             let fields : Vec<_> = cases.iter().map(|c| {
 371                 let mut ftys = vec!(ty_of_inttype(cx.tcx(), ity));
 372                 ftys.push_all(&c.tys);
 373                 if dtor { ftys.push(cx.tcx().dtor_type()); }
 374                 mk_struct(cx, &ftys[..], false, t)
 375             }).collect();
 376
 377             ensure_enum_fits_in_address_space(cx, &fields[..], t);
 378
 379             General(ity, fields, dtor_to_init_u8(dtor))
 380         }
 381         _ => cx.sess().bug(&format!("adt::represent_type called on non-ADT type: {}",
 382                            ty_to_string(cx.tcx(), t)))
 383     }
 384 }
 385
 386 // this should probably all be in ty
 387 struct Case<'tcx> {
 388     discr: Disr,
 389     tys: Vec<Ty<'tcx>>
 390 }
 391
 392 /// This represents the (GEP) indices to follow to get to the discriminant field
 393 pub type DiscrField = Vec<usize>;
 394
 395 fn find_discr_field_candidate<'tcx>(tcx: &ty::ctxt<'tcx>,
 396                                     ty: Ty<'tcx>,
 397                                     mut path: DiscrField) -> Option<DiscrField> {
 398     match ty.sty {
 399         // Fat &T/&mut T/Box<T> i.e. T is [T], str, or Trait
 400         ty::ty_rptr(_, ty::mt { ty, .. }) | ty::ty_uniq(ty) if !type_is_sized(tcx, ty) => {
 401             path.push(FAT_PTR_ADDR);
 402             Some(path)
 403         },
 404
 405         // Regular thin pointer: &T/&mut T/Box<T>
 406         ty::ty_rptr(..) | ty::ty_uniq(..) => Some(path),
 407
 408         // Functions are just pointers
 409         ty::ty_bare_fn(..) => Some(path),
 410
 411         // Is this the NonZero lang item wrapping a pointer or integer type?
 412         ty::ty_struct(did, substs) if Some(did) == tcx.lang_items.non_zero() => {
 413             let nonzero_fields = ty::lookup_struct_fields(tcx, did);
 414             assert_eq!(nonzero_fields.len(), 1);
 415             let nonzero_field = ty::lookup_field_type(tcx, did, nonzero_fields[0].id, substs);
 416             match nonzero_field.sty {
 417                 ty::ty_ptr(ty::mt { ty, .. }) if !type_is_sized(tcx, ty) => {
 418                     path.push_all(&[0, FAT_PTR_ADDR]);
 419                     Some(path)
 420                 },
 421                 ty::ty_ptr(..) | ty::ty_int(..) | ty::ty_uint(..) => {
 422                     path.push(0);
 423                     Some(path)
 424                 },
 425                 _ => None
 426             }
 427         },
 428
 429         // Perhaps one of the fields of this struct is non-zero
 430         // let's recurse and find out
 431         ty::ty_struct(def_id, substs) => {
 432             let fields = ty::lookup_struct_fields(tcx, def_id);
 433             for (j, field) in fields.iter().enumerate() {
 434                 let field_ty = ty::lookup_field_type(tcx, def_id, field.id, substs);
 435                 if let Some(mut fpath) = find_discr_field_candidate(tcx, field_ty, path.clone()) {
 436                     fpath.push(j);
 437                     return Some(fpath);
 438                 }
 439             }
 440             None
 441         },
 442
 443         // Can we use one of the fields in this tuple?
 444         ty::ty_tup(ref tys) => {
 445             for (j, &ty) in tys.iter().enumerate() {
 446                 if let Some(mut fpath) = find_discr_field_candidate(tcx, ty, path.clone()) {
 447                     fpath.push(j);
 448                     return Some(fpath);
 449                 }
 450             }
 451             None
 452         },
 453
 454         // Is this a fixed-size array of something non-zero
 455         // with at least one element?
 456         ty::ty_vec(ety, Some(d)) if d > 0 => {
 457             if let Some(mut vpath) = find_discr_field_candidate(tcx, ety, path) {
 458                 vpath.push(0);
 459                 Some(vpath)
 460             } else {
 461                 None
 462             }
 463         },
 464
 465         // Anything else is not a pointer
 466         _ => None
 467     }
 468 }
 469
 470 impl<'tcx> Case<'tcx> {
 471     fn is_zerolen<'a>(&self, cx: &CrateContext<'a, 'tcx>, scapegoat: Ty<'tcx>) -> bool {
 472         mk_struct(cx, &self.tys, false, scapegoat).size == 0
 473     }
 474
 475     fn find_ptr<'a>(&self, cx: &CrateContext<'a, 'tcx>) -> Option<DiscrField> {
 476         for (i, &ty) in self.tys.iter().enumerate() {
 477             if let Some(mut path) = find_discr_field_candidate(cx.tcx(), ty, vec![]) {
 478                 path.push(i);
 479                 return Some(path);
 480             }
 481         }
 482         None
 483     }
 484 }
 485
 486 fn get_cases<'tcx>(tcx: &ty::ctxt<'tcx>,
 487                    def_id: ast::DefId,
 488                    substs: &subst::Substs<'tcx>)
 489                    -> Vec<Case<'tcx>> {
 490     ty::enum_variants(tcx, def_id).iter().map(|vi| {
 491         let arg_tys = vi.args.iter().map(|&raw_ty| {
 492             monomorphize::apply_param_substs(tcx, substs, &raw_ty)
 493         }).collect();
 494         Case { discr: vi.disr_val, tys: arg_tys }
 495     }).collect()
 496 }
 497
 498 fn mk_struct<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 499                        tys: &[Ty<'tcx>], packed: bool,
 500                        scapegoat: Ty<'tcx>)
 501                        -> Struct<'tcx> {
 502     let sized = tys.iter().all(|&ty| type_is_sized(cx.tcx(), ty));
 503     let lltys : Vec<Type> = if sized {
 504         tys.iter()
 505            .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
 506     } else {
 507         tys.iter().filter(|&ty| type_is_sized(cx.tcx(), *ty))
 508            .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
 509     };
 510
 511     ensure_struct_fits_in_address_space(cx, &lltys[..], packed, scapegoat);
 512
 513     let llty_rec = Type::struct_(cx, &lltys[..], packed);
 514     Struct {
 515         size: machine::llsize_of_alloc(cx, llty_rec),
 516         align: machine::llalign_of_min(cx, llty_rec),
 517         sized: sized,
 518         packed: packed,
 519         fields: tys.to_vec(),
 520     }
 521 }
 522
 523 #[derive(Debug)]
 524 struct IntBounds {
 525     slo: i64,
 526     shi: i64,
 527     ulo: u64,
 528     uhi: u64
 529 }
 530
 531 fn mk_cenum<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 532                       hint: Hint, bounds: &IntBounds)
 533                       -> Repr<'tcx> {
 534     let it = range_to_inttype(cx, hint, bounds);
 535     match it {
 536         attr::SignedInt(_) => CEnum(it, bounds.slo as Disr, bounds.shi as Disr),
 537         attr::UnsignedInt(_) => CEnum(it, bounds.ulo, bounds.uhi)
 538     }
 539 }
 540
 541 fn range_to_inttype(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> IntType {
 542     debug!("range_to_inttype: {:?} {:?}", hint, bounds);
 543     // Lists of sizes to try.  u64 is always allowed as a fallback.
 544     #[allow(non_upper_case_globals)]
 545     const choose_shortest: &'static [IntType] = &[
 546         attr::UnsignedInt(ast::TyU8), attr::SignedInt(ast::TyI8),
 547         attr::UnsignedInt(ast::TyU16), attr::SignedInt(ast::TyI16),
 548         attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
 549     #[allow(non_upper_case_globals)]
 550     const at_least_32: &'static [IntType] = &[
 551         attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
 552
 553     let attempts;
 554     match hint {
 555         attr::ReprInt(span, ity) => {
 556             if !bounds_usable(cx, ity, bounds) {
 557                 cx.sess().span_bug(span, "representation hint insufficient for discriminant range")
 558             }
 559             return ity;
 560         }
 561         attr::ReprExtern => {
 562             attempts = match &cx.sess().target.target.arch[..] {
 563                 // WARNING: the ARM EABI has two variants; the one corresponding to `at_least_32`
 564                 // appears to be used on Linux and NetBSD, but some systems may use the variant
 565                 // corresponding to `choose_shortest`.  However, we don't run on those yet...?
 566                 "arm" => at_least_32,
 567                 _ => at_least_32,
 568             }
 569         }
 570         attr::ReprAny => {
 571             attempts = choose_shortest;
 572         },
 573         attr::ReprPacked => {
 574             cx.tcx().sess.bug("range_to_inttype: found ReprPacked on an enum");
 575         }
 576     }
 577     for &ity in attempts {
 578         if bounds_usable(cx, ity, bounds) {
 579             return ity;
 580         }
 581     }
 582     return attr::UnsignedInt(ast::TyU64);
 583 }
 584
 585 pub fn ll_inttype(cx: &CrateContext, ity: IntType) -> Type {
 586     match ity {
 587         attr::SignedInt(t) => Type::int_from_ty(cx, t),
 588         attr::UnsignedInt(t) => Type::uint_from_ty(cx, t)
 589     }
 590 }
 591
 592 fn bounds_usable(cx: &CrateContext, ity: IntType, bounds: &IntBounds) -> bool {
 593     debug!("bounds_usable: {:?} {:?}", ity, bounds);
 594     match ity {
 595         attr::SignedInt(_) => {
 596             let lllo = C_integral(ll_inttype(cx, ity), bounds.slo as u64, true);
 597             let llhi = C_integral(ll_inttype(cx, ity), bounds.shi as u64, true);
 598             bounds.slo == const_to_int(lllo) as i64 && bounds.shi == const_to_int(llhi) as i64
 599         }
 600         attr::UnsignedInt(_) => {
 601             let lllo = C_integral(ll_inttype(cx, ity), bounds.ulo, false);
 602             let llhi = C_integral(ll_inttype(cx, ity), bounds.uhi, false);
 603             bounds.ulo == const_to_uint(lllo) as u64 && bounds.uhi == const_to_uint(llhi) as u64
 604         }
 605     }
 606 }
 607
 608 pub fn ty_of_inttype<'tcx>(tcx: &ty::ctxt<'tcx>, ity: IntType) -> Ty<'tcx> {
 609     match ity {
 610         attr::SignedInt(t) => ty::mk_mach_int(tcx, t),
 611         attr::UnsignedInt(t) => ty::mk_mach_uint(tcx, t)
 612     }
 613 }
 614
 615 // LLVM doesn't like types that don't fit in the address space
 616 fn ensure_struct_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 617                                                  fields: &[Type],
 618                                                  packed: bool,
 619                                                  scapegoat: Ty<'tcx>) {
 620     let mut offset = 0;
 621     for &llty in fields {
 622         // Invariant: offset < ccx.obj_size_bound() <= 1<<61
 623         if !packed {
 624             let type_align = machine::llalign_of_min(ccx, llty);
 625             offset = roundup(offset, type_align);
 626         }
 627         // type_align is a power-of-2, so still offset < ccx.obj_size_bound()
 628         // llsize_of_alloc(ccx, llty) is also less than ccx.obj_size_bound()
 629         // so the sum is less than 1<<62 (and therefore can't overflow).
 630         offset += machine::llsize_of_alloc(ccx, llty);
 631
 632         if offset >= ccx.obj_size_bound() {
 633             ccx.report_overbig_object(scapegoat);
 634         }
 635     }
 636 }
 637
 638 fn union_size_and_align(sts: &[Struct]) -> (machine::llsize, machine::llalign) {
 639     let size = sts.iter().map(|st| st.size).max().unwrap();
 640     let align = sts.iter().map(|st| st.align).max().unwrap();
 641     (roundup(size, align), align)
 642 }
 643
 644 fn ensure_enum_fits_in_address_space<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
 645                                                fields: &[Struct],
 646                                                scapegoat: Ty<'tcx>) {
 647     let (total_size, _) = union_size_and_align(fields);
 648
 649     if total_size >= ccx.obj_size_bound() {
 650         ccx.report_overbig_object(scapegoat);
 651     }
 652 }
 653
 654
 655 /// LLVM-level types are a little complicated.
 656 ///
 657 /// C-like enums need to be actual ints, not wrapped in a struct,
 658 /// because that changes the ABI on some platforms (see issue #10308).
 659 ///
 660 /// For nominal types, in some cases, we need to use LLVM named structs
 661 /// and fill in the actual contents in a second pass to prevent
 662 /// unbounded recursion; see also the comments in `trans::type_of`.
 663 pub fn type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>) -> Type {
 664     generic_type_of(cx, r, None, false, false)
 665 }
 666 // Pass dst=true if the type you are passing is a DST. Yes, we could figure
 667 // this out, but if you call this on an unsized type without realising it, you
 668 // are going to get the wrong type (it will not include the unsized parts of it).
 669 pub fn sizing_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 670                                 r: &Repr<'tcx>, dst: bool) -> Type {
 671     generic_type_of(cx, r, None, true, dst)
 672 }
 673 pub fn incomplete_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 674                                     r: &Repr<'tcx>, name: &str) -> Type {
 675     generic_type_of(cx, r, Some(name), false, false)
 676 }
 677 pub fn finish_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 678                                 r: &Repr<'tcx>, llty: &mut Type) {
 679     match *r {
 680         CEnum(..) | General(..) | RawNullablePointer { .. } => { }
 681         Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } =>
 682             llty.set_struct_body(&struct_llfields(cx, st, false, false),
 683                                  st.packed)
 684     }
 685 }
 686
 687 fn generic_type_of<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>,
 688                              r: &Repr<'tcx>,
 689                              name: Option<&str>,
 690                              sizing: bool,
 691                              dst: bool) -> Type {
 692     match *r {
 693         CEnum(ity, _, _) => ll_inttype(cx, ity),
 694         RawNullablePointer { nnty, .. } => type_of::sizing_type_of(cx, nnty),
 695         Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } => {
 696             match name {
 697                 None => {
 698                     Type::struct_(cx, &struct_llfields(cx, st, sizing, dst),
 699                                   st.packed)
 700                 }
 701                 Some(name) => { assert_eq!(sizing, false); Type::named_struct(cx, name) }
 702             }
 703         }
 704         General(ity, ref sts, _) => {
 705             // We need a representation that has:
 706             // * The alignment of the most-aligned field
 707             // * The size of the largest variant (rounded up to that alignment)
 708             // * No alignment padding anywhere any variant has actual data
 709             //   (currently matters only for enums small enough to be immediate)
 710             // * The discriminant in an obvious place.
 711             //
 712             // So we start with the discriminant, pad it up to the alignment with
 713             // more of its own type, then use alignment-sized ints to get the rest
 714             // of the size.
 715             //
 716             // FIXME #10604: this breaks when vector types are present.
 717             let (size, align) = union_size_and_align(&sts[..]);
 718             let align_s = align as u64;
 719             assert_eq!(size % align_s, 0);
 720             let align_units = size / align_s - 1;
 721
 722             let discr_ty = ll_inttype(cx, ity);
 723             let discr_size = machine::llsize_of_alloc(cx, discr_ty);
 724             let fill_ty = match align_s {
 725                 1 => Type::array(&Type::i8(cx), align_units),
 726                 2 => Type::array(&Type::i16(cx), align_units),
 727                 4 => Type::array(&Type::i32(cx), align_units),
 728                 8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
 729                                  Type::array(&Type::i64(cx), align_units),
 730                 a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(cx), a / 4),
 731                                                               align_units),
 732                 _ => panic!("unsupported enum alignment: {}", align)
 733             };
 734             assert_eq!(machine::llalign_of_min(cx, fill_ty), align);
 735             assert_eq!(align_s % discr_size, 0);
 736             let fields = [discr_ty,
 737                           Type::array(&discr_ty, align_s / discr_size - 1),
 738                           fill_ty];
 739             match name {
 740                 None => Type::struct_(cx, &fields[..], false),
 741                 Some(name) => {
 742                     let mut llty = Type::named_struct(cx, name);
 743                     llty.set_struct_body(&fields[..], false);
 744                     llty
 745                 }
 746             }
 747         }
 748     }
 749 }
 750
 751 fn struct_llfields<'a, 'tcx>(cx: &CrateContext<'a, 'tcx>, st: &Struct<'tcx>,
 752                              sizing: bool, dst: bool) -> Vec<Type> {
 753     if sizing {
 754         st.fields.iter().filter(|&ty| !dst || type_is_sized(cx.tcx(), *ty))
 755             .map(|&ty| type_of::sizing_type_of(cx, ty)).collect()
 756     } else {
 757         st.fields.iter().map(|&ty| type_of::in_memory_type_of(cx, ty)).collect()
 758     }
 759 }
 760
 761 /// Obtain a representation of the discriminant sufficient to translate
 762 /// destructuring; this may or may not involve the actual discriminant.
 763 ///
 764 /// This should ideally be less tightly tied to `_match`.
 765 pub fn trans_switch<'blk, 'tcx>(bcx: Block<'blk, 'tcx>,
 766                                 r: &Repr<'tcx>, scrutinee: ValueRef)
 767                                 -> (_match::BranchKind, Option<ValueRef>) {
 768     match *r {
 769         CEnum(..) | General(..) |
 770         RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
 771             (_match::Switch, Some(trans_get_discr(bcx, r, scrutinee, None)))
 772         }
 773         Univariant(..) => {
 774             // N.B.: Univariant means <= 1 enum variants (*not* == 1 variants).
 775             (_match::Single, None)
 776         }
 777     }
 778 }
 779
 780
 781
 782 /// Obtain the actual discriminant of a value.
 783 pub fn trans_get_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
 784                                    scrutinee: ValueRef, cast_to: Option<Type>)
 785     -> ValueRef {
 786     let signed;
 787     let val;
 788     debug!("trans_get_discr r: {:?}", r);
 789     match *r {
 790         CEnum(ity, min, max) => {
 791             val = load_discr(bcx, ity, scrutinee, min, max);
 792             signed = ity.is_signed();
 793         }
 794         General(ity, ref cases, _) => {
 795             let ptr = GEPi(bcx, scrutinee, &[0, 0]);
 796             val = load_discr(bcx, ity, ptr, 0, (cases.len() - 1) as Disr);
 797             signed = ity.is_signed();
 798         }
 799         Univariant(..) => {
 800             val = C_u8(bcx.ccx(), 0);
 801             signed = false;
 802         }
 803         RawNullablePointer { nndiscr, nnty, .. } =>  {
 804             let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 805             let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
 806             val = ICmp(bcx, cmp, Load(bcx, scrutinee), C_null(llptrty), DebugLoc::None);
 807             signed = false;
 808         }
 809         StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
 810             val = struct_wrapped_nullable_bitdiscr(bcx, nndiscr, discrfield, scrutinee);
 811             signed = false;
 812         }
 813     }
 814     match cast_to {
 815         None => val,
 816         Some(llty) => if signed { SExt(bcx, val, llty) } else { ZExt(bcx, val, llty) }
 817     }
 818 }
 819
 820 fn struct_wrapped_nullable_bitdiscr(bcx: Block, nndiscr: Disr, discrfield: &DiscrField,
 821                                     scrutinee: ValueRef) -> ValueRef {
 822     let llptrptr = GEPi(bcx, scrutinee, &discrfield[..]);
 823     let llptr = Load(bcx, llptrptr);
 824     let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 825     ICmp(bcx, cmp, llptr, C_null(val_ty(llptr)), DebugLoc::None)
 826 }
 827
 828 /// Helper for cases where the discriminant is simply loaded.
 829 fn load_discr(bcx: Block, ity: IntType, ptr: ValueRef, min: Disr, max: Disr)
 830     -> ValueRef {
 831     let llty = ll_inttype(bcx.ccx(), ity);
 832     assert_eq!(val_ty(ptr), llty.ptr_to());
 833     let bits = machine::llbitsize_of_real(bcx.ccx(), llty);
 834     assert!(bits <= 64);
 835     let  bits = bits as usize;
 836     let mask = (!0u64 >> (64 - bits)) as Disr;
 837     // For a (max) discr of -1, max will be `-1 as usize`, which overflows.
 838     // However, that is fine here (it would still represent the full range),
 839     if (max.wrapping_add(1)) & mask == min & mask {
 840         // i.e., if the range is everything.  The lo==hi case would be
 841         // rejected by the LLVM verifier (it would mean either an
 842         // empty set, which is impossible, or the entire range of the
 843         // type, which is pointless).
 844         Load(bcx, ptr)
 845     } else {
 846         // llvm::ConstantRange can deal with ranges that wrap around,
 847         // so an overflow on (max + 1) is fine.
 848         LoadRangeAssert(bcx, ptr, min, (max.wrapping_add(1)), /* signed: */ True)
 849     }
 850 }
 851
 852 /// Yield information about how to dispatch a case of the
 853 /// discriminant-like value returned by `trans_switch`.
 854 ///
 855 /// This should ideally be less tightly tied to `_match`.
 856 pub fn trans_case<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr, discr: Disr)
 857                               -> _match::OptResult<'blk, 'tcx> {
 858     match *r {
 859         CEnum(ity, _, _) => {
 860             _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
 861                                                               discr as u64, true)))
 862         }
 863         General(ity, _, _) => {
 864             _match::SingleResult(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
 865                                                               discr as u64, true)))
 866         }
 867         Univariant(..) => {
 868             bcx.ccx().sess().bug("no cases for univariants or structs")
 869         }
 870         RawNullablePointer { .. } |
 871         StructWrappedNullablePointer { .. } => {
 872             assert!(discr == 0 || discr == 1);
 873             _match::SingleResult(Result::new(bcx, C_bool(bcx.ccx(), discr != 0)))
 874         }
 875     }
 876 }
 877
 878 /// Set the discriminant for a new value of the given case of the given
 879 /// representation.
 880 pub fn trans_set_discr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
 881                                    val: ValueRef, discr: Disr) {
 882     match *r {
 883         CEnum(ity, min, max) => {
 884             assert_discr_in_range(ity, min, max, discr);
 885             Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
 886                   val);
 887         }
 888         General(ity, ref cases, dtor) => {
 889             if dtor_active(dtor) {
 890                 let ptr = trans_field_ptr(bcx, r, val, discr,
 891                                           cases[discr as usize].fields.len() - 2);
 892                 Store(bcx, C_u8(bcx.ccx(), DTOR_NEEDED as usize), ptr);
 893             }
 894             Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
 895                   GEPi(bcx, val, &[0, 0]));
 896         }
 897         Univariant(ref st, dtor) => {
 898             assert_eq!(discr, 0);
 899             if dtor_active(dtor) {
 900                 Store(bcx, C_u8(bcx.ccx(), DTOR_NEEDED as usize),
 901                     GEPi(bcx, val, &[0, st.fields.len() - 1]));
 902             }
 903         }
 904         RawNullablePointer { nndiscr, nnty, ..} => {
 905             if discr != nndiscr {
 906                 let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
 907                 Store(bcx, C_null(llptrty), val);
 908             }
 909         }
 910         StructWrappedNullablePointer { nndiscr, ref discrfield, .. } => {
 911             if discr != nndiscr {
 912                 let llptrptr = GEPi(bcx, val, &discrfield[..]);
 913                 let llptrty = val_ty(llptrptr).element_type();
 914                 Store(bcx, C_null(llptrty), llptrptr);
 915             }
 916         }
 917     }
 918 }
 919
 920 fn assert_discr_in_range(ity: IntType, min: Disr, max: Disr, discr: Disr) {
 921     match ity {
 922         attr::UnsignedInt(_) => assert!(min <= discr && discr <= max),
 923         attr::SignedInt(_) => assert!(min as i64 <= discr as i64 && discr as i64 <= max as i64)
 924     }
 925 }
 926
 927 /// The number of fields in a given case; for use when obtaining this
 928 /// information from the type or definition is less convenient.
 929 pub fn num_args(r: &Repr, discr: Disr) -> usize {
 930     match *r {
 931         CEnum(..) => 0,
 932         Univariant(ref st, dtor) => {
 933             assert_eq!(discr, 0);
 934             st.fields.len() - (if dtor_active(dtor) { 1 } else { 0 })
 935         }
 936         General(_, ref cases, dtor) => {
 937             cases[discr as usize].fields.len() - 1 - (if dtor_active(dtor) { 1 } else { 0 })
 938         }
 939         RawNullablePointer { nndiscr, ref nullfields, .. } => {
 940             if discr == nndiscr { 1 } else { nullfields.len() }
 941         }
 942         StructWrappedNullablePointer { ref nonnull, nndiscr,
 943                                        ref nullfields, .. } => {
 944             if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
 945         }
 946     }
 947 }
 948
 949 /// Access a field, at a point when the value's case is known.
 950 pub fn trans_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>,
 951                                    val: ValueRef, discr: Disr, ix: usize) -> ValueRef {
 952     // Note: if this ever needs to generate conditionals (e.g., if we
 953     // decide to do some kind of cdr-coding-like non-unique repr
 954     // someday), it will need to return a possibly-new bcx as well.
 955     match *r {
 956         CEnum(..) => {
 957             bcx.ccx().sess().bug("element access in C-like enum")
 958         }
 959         Univariant(ref st, _dtor) => {
 960             assert_eq!(discr, 0);
 961             struct_field_ptr(bcx, st, val, ix, false)
 962         }
 963         General(_, ref cases, _) => {
 964             struct_field_ptr(bcx, &cases[discr as usize], val, ix + 1, true)
 965         }
 966         RawNullablePointer { nndiscr, ref nullfields, .. } |
 967         StructWrappedNullablePointer { nndiscr, ref nullfields, .. } if discr != nndiscr => {
 968             // The unit-like case might have a nonzero number of unit-like fields.
 969             // (e.d., Result of Either with (), as one side.)
 970             let ty = type_of::type_of(bcx.ccx(), nullfields[ix]);
 971             assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
 972             // The contents of memory at this pointer can't matter, but use
 973             // the value that's "reasonable" in case of pointer comparison.
 974             PointerCast(bcx, val, ty.ptr_to())
 975         }
 976         RawNullablePointer { nndiscr, nnty, .. } => {
 977             assert_eq!(ix, 0);
 978             assert_eq!(discr, nndiscr);
 979             let ty = type_of::type_of(bcx.ccx(), nnty);
 980             PointerCast(bcx, val, ty.ptr_to())
 981         }
 982         StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
 983             assert_eq!(discr, nndiscr);
 984             struct_field_ptr(bcx, nonnull, val, ix, false)
 985         }
 986     }
 987 }
 988
 989 pub fn struct_field_ptr<'blk, 'tcx>(bcx: Block<'blk, 'tcx>, st: &Struct<'tcx>, val: ValueRef,
 990                                     ix: usize, needs_cast: bool) -> ValueRef {
 991     let val = if needs_cast {
 992         let ccx = bcx.ccx();
 993         let fields = st.fields.iter().map(|&ty| type_of::type_of(ccx, ty)).collect::<Vec<_>>();
 994         let real_ty = Type::struct_(ccx, &fields[..], st.packed);
 995         PointerCast(bcx, val, real_ty.ptr_to())
 996     } else {
 997         val
 998     };
 999
1000     GEPi(bcx, val, &[0, ix])
1001 }
1002
1003 pub fn fold_variants<'blk, 'tcx, F>(bcx: Block<'blk, 'tcx>,
1004                                     r: &Repr<'tcx>,
1005                                     value: ValueRef,
1006                                     mut f: F)
1007                                     -> Block<'blk, 'tcx> where
1008     F: FnMut(Block<'blk, 'tcx>, &Struct<'tcx>, ValueRef) -> Block<'blk, 'tcx>,
1009 {
1010     let fcx = bcx.fcx;
1011     match *r {
1012         Univariant(ref st, _) => {
1013             f(bcx, st, value)
1014         }
1015         General(ity, ref cases, _) => {
1016             let ccx = bcx.ccx();
1017             let unr_cx = fcx.new_temp_block("enum-variant-iter-unr");
1018             Unreachable(unr_cx);
1019
1020             let discr_val = trans_get_discr(bcx, r, value, None);
1021             let llswitch = Switch(bcx, discr_val, unr_cx.llbb, cases.len());
1022             let bcx_next = fcx.new_temp_block("enum-variant-iter-next");
1023
1024             for (discr, case) in cases.iter().enumerate() {
1025                 let mut variant_cx = fcx.new_temp_block(
1026                     &format!("enum-variant-iter-{}", &discr.to_string())
1027                 );
1028                 let rhs_val = C_integral(ll_inttype(ccx, ity), discr as u64, true);
1029                 AddCase(llswitch, rhs_val, variant_cx.llbb);
1030
1031                 let fields = case.fields.iter().map(|&ty|
1032                     type_of::type_of(bcx.ccx(), ty)).collect::<Vec<_>>();
1033                 let real_ty = Type::struct_(ccx, &fields[..], case.packed);
1034                 let variant_value = PointerCast(variant_cx, value, real_ty.ptr_to());
1035
1036                 variant_cx = f(variant_cx, case, variant_value);
1037                 Br(variant_cx, bcx_next.llbb, DebugLoc::None);
1038             }
1039
1040             bcx_next
1041         }
1042         _ => unreachable!()
1043     }
1044 }
1045
1046 /// Access the struct drop flag, if present.
1047 pub fn trans_drop_flag_ptr<'blk, 'tcx>(mut bcx: Block<'blk, 'tcx>, r: &Repr<'tcx>, val: ValueRef)
1048                                        -> datum::DatumBlock<'blk, 'tcx, datum::Expr>
1049 {
1050     let tcx = bcx.tcx();
1051     let ptr_ty = ty::mk_imm_ptr(bcx.tcx(), tcx.dtor_type());
1052     match *r {
1053         Univariant(ref st, dtor) if dtor_active(dtor) => {
1054             let flag_ptr = GEPi(bcx, val, &[0, st.fields.len() - 1]);
1055             datum::immediate_rvalue_bcx(bcx, flag_ptr, ptr_ty).to_expr_datumblock()
1056         }
1057         General(_, _, dtor) if dtor_active(dtor) => {
1058             let fcx = bcx.fcx;
1059             let custom_cleanup_scope = fcx.push_custom_cleanup_scope();
1060             let scratch = unpack_datum!(bcx, datum::lvalue_scratch_datum(
1061                 bcx, tcx.dtor_type(), "drop_flag",
1062                 cleanup::CustomScope(custom_cleanup_scope), (), |_, bcx, _| bcx
1063             ));
1064             bcx = fold_variants(bcx, r, val, |variant_cx, st, value| {
1065                 let ptr = struct_field_ptr(variant_cx, st, value, (st.fields.len() - 1), false);
1066                 datum::Datum::new(ptr, ptr_ty, datum::Lvalue)
1067                     .store_to(variant_cx, scratch.val)
1068             });
1069             let expr_datum = scratch.to_expr_datum();
1070             fcx.pop_custom_cleanup_scope(custom_cleanup_scope);
1071             datum::DatumBlock::new(bcx, expr_datum)
1072         }
1073         _ => bcx.ccx().sess().bug("tried to get drop flag of non-droppable type")
1074     }
1075 }
1076
1077 /// Construct a constant value, suitable for initializing a
1078 /// GlobalVariable, given a case and constant values for its fields.
1079 /// Note that this may have a different LLVM type (and different
1080 /// alignment!) from the representation's `type_of`, so it needs a
1081 /// pointer cast before use.
1082 ///
1083 /// The LLVM type system does not directly support unions, and only
1084 /// pointers can be bitcast, so a constant (and, by extension, the
1085 /// GlobalVariable initialized by it) will have a type that can vary
1086 /// depending on which case of an enum it is.
1087 ///
1088 /// To understand the alignment situation, consider `enum E { V64(u64),
1089 /// V32(u32, u32) }` on Windows.  The type has 8-byte alignment to
1090 /// accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
1091 /// i32, i32}`, which is 4-byte aligned.
1092 ///
1093 /// Currently the returned value has the same size as the type, but
1094 /// this could be changed in the future to avoid allocating unnecessary
1095 /// space after values of shorter-than-maximum cases.
1096 pub fn trans_const<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, r: &Repr<'tcx>, discr: Disr,
1097                              vals: &[ValueRef]) -> ValueRef {
1098     match *r {
1099         CEnum(ity, min, max) => {
1100             assert_eq!(vals.len(), 0);
1101             assert_discr_in_range(ity, min, max, discr);
1102             C_integral(ll_inttype(ccx, ity), discr as u64, true)
1103         }
1104         General(ity, ref cases, _) => {
1105             let case = &cases[discr as usize];
1106             let (max_sz, _) = union_size_and_align(&cases[..]);
1107             let lldiscr = C_integral(ll_inttype(ccx, ity), discr as u64, true);
1108             let mut f = vec![lldiscr];
1109             f.push_all(vals);
1110             let mut contents = build_const_struct(ccx, case, &f[..]);
1111             contents.push_all(&[padding(ccx, max_sz - case.size)]);
1112             C_struct(ccx, &contents[..], false)
1113         }
1114         Univariant(ref st, _dro) => {
1115             assert!(discr == 0);
1116             let contents = build_const_struct(ccx, st, vals);
1117             C_struct(ccx, &contents[..], st.packed)
1118         }
1119         RawNullablePointer { nndiscr, nnty, .. } => {
1120             if discr == nndiscr {
1121                 assert_eq!(vals.len(), 1);
1122                 vals[0]
1123             } else {
1124                 C_null(type_of::sizing_type_of(ccx, nnty))
1125             }
1126         }
1127         StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
1128             if discr == nndiscr {
1129                 C_struct(ccx, &build_const_struct(ccx,
1130                                                  nonnull,
1131                                                  vals),
1132                          false)
1133             } else {
1134                 let vals = nonnull.fields.iter().map(|&ty| {
1135                     // Always use null even if it's not the `discrfield`th
1136                     // field; see #8506.
1137                     C_null(type_of::sizing_type_of(ccx, ty))
1138                 }).collect::<Vec<ValueRef>>();
1139                 C_struct(ccx, &build_const_struct(ccx,
1140                                                  nonnull,
1141                                                  &vals[..]),
1142                          false)
1143             }
1144         }
1145     }
1146 }
1147
1148 /// Compute struct field offsets relative to struct begin.
1149 fn compute_struct_field_offsets<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1150                                           st: &Struct<'tcx>) -> Vec<u64> {
1151     let mut offsets = vec!();
1152
1153     let mut offset = 0;
1154     for &ty in &st.fields {
1155         let llty = type_of::sizing_type_of(ccx, ty);
1156         if !st.packed {
1157             let type_align = type_of::align_of(ccx, ty);
1158             offset = roundup(offset, type_align);
1159         }
1160         offsets.push(offset);
1161         offset += machine::llsize_of_alloc(ccx, llty);
1162     }
1163     assert_eq!(st.fields.len(), offsets.len());
1164     offsets
1165 }
1166
1167 /// Building structs is a little complicated, because we might need to
1168 /// insert padding if a field's value is less aligned than its type.
1169 ///
1170 /// Continuing the example from `trans_const`, a value of type `(u32,
1171 /// E)` should have the `E` at offset 8, but if that field's
1172 /// initializer is 4-byte aligned then simply translating the tuple as
1173 /// a two-element struct will locate it at offset 4, and accesses to it
1174 /// will read the wrong memory.
1175 fn build_const_struct<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>,
1176                                 st: &Struct<'tcx>, vals: &[ValueRef])
1177                                 -> Vec<ValueRef> {
1178     assert_eq!(vals.len(), st.fields.len());
1179
1180     let target_offsets = compute_struct_field_offsets(ccx, st);
1181
1182     // offset of current value
1183     let mut offset = 0;
1184     let mut cfields = Vec::new();
1185     for (&val, &target_offset) in vals.iter().zip(target_offsets.iter()) {
1186         if !st.packed {
1187             let val_align = machine::llalign_of_min(ccx, val_ty(val));
1188             offset = roundup(offset, val_align);
1189         }
1190         if offset != target_offset {
1191             cfields.push(padding(ccx, target_offset - offset));
1192             offset = target_offset;
1193         }
1194         assert!(!is_undef(val));
1195         cfields.push(val);
1196         offset += machine::llsize_of_alloc(ccx, val_ty(val));
1197     }
1198
1199     assert!(st.sized && offset <= st.size);
1200     if offset != st.size {
1201         cfields.push(padding(ccx, st.size - offset));
1202     }
1203
1204     cfields
1205 }
1206
1207 fn padding(ccx: &CrateContext, size: u64) -> ValueRef {
1208     C_undef(Type::array(&Type::i8(ccx), size))
1209 }
1210
1211 // FIXME this utility routine should be somewhere more general
1212 #[inline]
1213 fn roundup(x: u64, a: u32) -> u64 { let a = a as u64; ((x + (a - 1)) / a) * a }
1214
1215 /// Get the discriminant of a constant value.
1216 pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef) -> Disr {
1217     match *r {
1218         CEnum(ity, _, _) => {
1219             match ity {
1220                 attr::SignedInt(..) => const_to_int(val) as Disr,
1221                 attr::UnsignedInt(..) => const_to_uint(val) as Disr
1222             }
1223         }
1224         General(ity, _, _) => {
1225             match ity {
1226                 attr::SignedInt(..) => const_to_int(const_get_elt(ccx, val, &[0])) as Disr,
1227                 attr::UnsignedInt(..) => const_to_uint(const_get_elt(ccx, val, &[0])) as Disr
1228             }
1229         }
1230         Univariant(..) => 0,
1231         RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
1232             ccx.sess().bug("const discrim access of non c-like enum")
1233         }
1234     }
1235 }
1236
1237 /// Extract a field of a constant value, as appropriate for its
1238 /// representation.
1239 ///
1240 /// (Not to be confused with `common::const_get_elt`, which operates on
1241 /// raw LLVM-level structs and arrays.)
1242 pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
1243                        _discr: Disr, ix: usize) -> ValueRef {
1244     match *r {
1245         CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
1246         Univariant(..) => const_struct_field(ccx, val, ix),
1247         General(..) => const_struct_field(ccx, val, ix + 1),
1248         RawNullablePointer { .. } => {
1249             assert_eq!(ix, 0);
1250             val
1251         },
1252         StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix)
1253     }
1254 }
1255
1256 /// Extract field of struct-like const, skipping our alignment padding.
1257 fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: usize) -> ValueRef {
1258     // Get the ix-th non-undef element of the struct.
1259     let mut real_ix = 0; // actual position in the struct
1260     let mut ix = ix; // logical index relative to real_ix
1261     let mut field;
1262     loop {
1263         loop {
1264             field = const_get_elt(ccx, val, &[real_ix]);
1265             if !is_undef(field) {
1266                 break;
1267             }
1268             real_ix = real_ix + 1;
1269         }
1270         if ix == 0 {
1271             return field;
1272         }
1273         ix = ix - 1;
1274         real_ix = real_ix + 1;
1275     }
1276 }