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