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