src/librustc/middle/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 /*!
  12  * # Representation of Algebraic Data Types
  13  *
  14  * This module determines how to represent enums, structs, and tuples
  15  * based on their monomorphized types; it is responsible both for
  16  * choosing a representation and translating basic operations on
  17  * values of those types.  (Note: exporting the representations for
  18  * debuggers is handled in debuginfo.rs, not here.)
  19  *
  20  * Note that the interface treats everything as a general case of an
  21  * enum, so structs/tuples/etc. have one pseudo-variant with
  22  * discriminant 0; i.e., as if they were a univariant enum.
  23  *
  24  * Having everything in one place will enable improvements to data
  25  * structure representation; possibilities include:
  26  *
  27  * - User-specified alignment (e.g., cacheline-aligning parts of
  28  *   concurrently accessed data structures); LLVM can't represent this
  29  *   directly, so we'd have to insert padding fields in any structure
  30  *   that might contain one and adjust GEP indices accordingly.  See
  31  *   issue #4578.
  32  *
  33  * - Store nested enums' discriminants in the same word.  Rather, if
  34  *   some variants start with enums, and those enums representations
  35  *   have unused alignment padding between discriminant and body, the
  36  *   outer enum's discriminant can be stored there and those variants
  37  *   can start at offset 0.  Kind of fancy, and might need work to
  38  *   make copies of the inner enum type cooperate, but it could help
  39  *   with `Option` or `Result` wrapped around another enum.
  40  *
  41  * - Tagged pointers would be neat, but given that any type can be
  42  *   used unboxed and any field can have pointers (including mutable)
  43  *   taken to it, implementing them for Rust seems difficult.
  44  */
  45
  46 use std::container::Map;
  47 use std::libc::c_ulonglong;
  48 use std::option::{Option, Some, None};
  49 use std::num::{Bitwise};
  50
  51 use lib::llvm::{ValueRef, True, IntEQ, IntNE};
  52 use middle::trans::_match;
  53 use middle::trans::build::*;
  54 use middle::trans::common::*;
  55 use middle::trans::machine;
  56 use middle::trans::type_::Type;
  57 use middle::trans::type_of;
  58 use middle::ty;
  59 use middle::ty::Disr;
  60 use std::vec;
  61 use syntax::abi::{X86, X86_64, Arm, Mips};
  62 use syntax::ast;
  63 use syntax::attr;
  64 use syntax::attr::IntType;
  65 use util::ppaux::ty_to_str;
  66
  67 type Hint = attr::ReprAttr;
  68
  69
  70 /// Representations.
  71 pub enum Repr {
  72     /// C-like enums; basically an int.
  73     CEnum(IntType, Disr, Disr), // discriminant range (signedness based on the IntType)
  74     /**
  75      * Single-case variants, and structs/tuples/records.
  76      *
  77      * Structs with destructors need a dynamic destroyedness flag to
  78      * avoid running the destructor too many times; this is included
  79      * in the `Struct` if present.
  80      */
  81     Univariant(Struct, bool),
  82     /**
  83      * General-case enums: for each case there is a struct, and they
  84      * all start with a field for the discriminant.
  85      */
  86     General(IntType, Vec<Struct> ),
  87     /**
  88      * Two cases distinguished by a nullable pointer: the case with discriminant
  89      * `nndiscr` is represented by the struct `nonnull`, where the `ptrfield`th
  90      * field is known to be nonnull due to its type; if that field is null, then
  91      * it represents the other case, which is inhabited by at most one value
  92      * (and all other fields are undefined/unused).
  93      *
  94      * For example, `std::option::Option` instantiated at a safe pointer type
  95      * is represented such that `None` is a null pointer and `Some` is the
  96      * identity function.
  97      */
  98     NullablePointer{ nonnull: Struct, nndiscr: Disr, ptrfield: uint,
  99                      nullfields: Vec<ty::t> }
 100 }
 101
 102 /// For structs, and struct-like parts of anything fancier.
 103 pub struct Struct {
 104     size: u64,
 105     align: u64,
 106     packed: bool,
 107     fields: Vec<ty::t> }
 108
 109 /**
 110  * Convenience for `represent_type`.  There should probably be more or
 111  * these, for places in trans where the `ty::t` isn't directly
 112  * available.
 113  */
 114 pub fn represent_node(bcx: &Block, node: ast::NodeId) -> @Repr {
 115     represent_type(bcx.ccx(), node_id_type(bcx, node))
 116 }
 117
 118 /// Decides how to represent a given type.
 119 pub fn represent_type(cx: &CrateContext, t: ty::t) -> @Repr {
 120     debug!("Representing: {}", ty_to_str(cx.tcx(), t));
 121     match cx.adt_reprs.borrow().find(&t) {
 122         Some(repr) => return *repr,
 123         None => {}
 124     }
 125
 126     let repr = @represent_type_uncached(cx, t);
 127     debug!("Represented as: {:?}", repr)
 128     cx.adt_reprs.borrow_mut().insert(t, repr);
 129     return repr;
 130 }
 131
 132 fn represent_type_uncached(cx: &CrateContext, t: ty::t) -> Repr {
 133     match ty::get(t).sty {
 134         ty::ty_tup(ref elems) => {
 135             return Univariant(mk_struct(cx, elems.as_slice(), false), false)
 136         }
 137         ty::ty_struct(def_id, ref substs) => {
 138             let fields = ty::lookup_struct_fields(cx.tcx(), def_id);
 139             let mut ftys = fields.map(|field| {
 140                 ty::lookup_field_type(cx.tcx(), def_id, field.id, substs)
 141             });
 142             let packed = ty::lookup_packed(cx.tcx(), def_id);
 143             let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
 144             if dtor { ftys.push(ty::mk_bool()); }
 145
 146             return Univariant(mk_struct(cx, ftys.as_slice(), packed), dtor)
 147         }
 148         ty::ty_enum(def_id, ref substs) => {
 149             let cases = get_cases(cx.tcx(), def_id, substs);
 150             let hint = ty::lookup_repr_hint(cx.tcx(), def_id);
 151
 152             if cases.len() == 0 {
 153                 // Uninhabitable; represent as unit
 154                 // (Typechecking will reject discriminant-sizing attrs.)
 155                 assert_eq!(hint, attr::ReprAny);
 156                 return Univariant(mk_struct(cx, [], false), false);
 157             }
 158
 159             if cases.iter().all(|c| c.tys.len() == 0) {
 160                 // All bodies empty -> intlike
 161                 let discrs = cases.map(|c| c.discr);
 162                 let bounds = IntBounds {
 163                     ulo: *discrs.iter().min().unwrap(),
 164                     uhi: *discrs.iter().max().unwrap(),
 165                     slo: discrs.iter().map(|n| *n as i64).min().unwrap(),
 166                     shi: discrs.iter().map(|n| *n as i64).max().unwrap()
 167                 };
 168                 return mk_cenum(cx, hint, &bounds);
 169             }
 170
 171             // Since there's at least one
 172             // non-empty body, explicit discriminants should have
 173             // been rejected by a checker before this point.
 174             if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
 175                 cx.sess().bug(format!("non-C-like enum {} with specified \
 176                                       discriminants",
 177                                       ty::item_path_str(cx.tcx(), def_id)))
 178             }
 179
 180             if cases.len() == 1 {
 181                 // Equivalent to a struct/tuple/newtype.
 182                 // (Typechecking will reject discriminant-sizing attrs.)
 183                 assert_eq!(hint, attr::ReprAny);
 184                 return Univariant(mk_struct(cx,
 185                                             cases.get(0).tys.as_slice(),
 186                                             false),
 187                                   false)
 188             }
 189
 190             if cases.len() == 2 && hint == attr::ReprAny {
 191                 // Nullable pointer optimization
 192                 let mut discr = 0;
 193                 while discr < 2 {
 194                     if cases.get(1 - discr).is_zerolen(cx) {
 195                         match cases.get(discr).find_ptr() {
 196                             Some(ptrfield) => {
 197                                 return NullablePointer {
 198                                     nndiscr: discr as u64,
 199                                     nonnull: mk_struct(cx,
 200                                                        cases.get(discr)
 201                                                             .tys
 202                                                             .as_slice(),
 203                                                        false),
 204                                     ptrfield: ptrfield,
 205                                     nullfields: cases.get(1 - discr).tys
 206                                                                     .clone()
 207                                 }
 208                             }
 209                             None => { }
 210                         }
 211                     }
 212                     discr += 1;
 213                 }
 214             }
 215
 216             // The general case.
 217             assert!((cases.len() - 1) as i64 >= 0);
 218             let bounds = IntBounds { ulo: 0, uhi: (cases.len() - 1) as u64,
 219                                      slo: 0, shi: (cases.len() - 1) as i64 };
 220             let ity = range_to_inttype(cx, hint, &bounds);
 221             return General(ity, cases.map(|c| {
 222                 let discr = vec!(ty_of_inttype(ity));
 223                 mk_struct(cx,
 224                           vec::append(discr, c.tys.as_slice()).as_slice(),
 225                           false)
 226             }))
 227         }
 228         _ => cx.sess().bug("adt::represent_type called on non-ADT type")
 229     }
 230 }
 231
 232 /// Determine, without doing translation, whether an ADT must be FFI-safe.
 233 /// For use in lint or similar, where being sound but slightly incomplete is acceptable.
 234 pub fn is_ffi_safe(tcx: &ty::ctxt, def_id: ast::DefId) -> bool {
 235     match ty::get(ty::lookup_item_type(tcx, def_id).ty).sty {
 236         ty::ty_enum(def_id, _) => {
 237             let variants = ty::enum_variants(tcx, def_id);
 238             // Univariant => like struct/tuple.
 239             if variants.len() <= 1 {
 240                 return true;
 241             }
 242             let hint = ty::lookup_repr_hint(tcx, def_id);
 243             // Appropriate representation explicitly selected?
 244             if hint.is_ffi_safe() {
 245                 return true;
 246             }
 247             // Option<~T> and similar are used in FFI.  Rather than try to resolve type parameters
 248             // and recognize this case exactly, this overapproximates -- assuming that if a
 249             // non-C-like enum is being used in FFI then the user knows what they're doing.
 250             if variants.iter().any(|vi| !vi.args.is_empty()) {
 251                 return true;
 252             }
 253             false
 254         }
 255         // struct, tuple, etc.
 256         // (is this right in the present of typedefs?)
 257         _ => true
 258     }
 259 }
 260
 261 // this should probably all be in ty
 262 struct Case { discr: Disr, tys: Vec<ty::t> }
 263 impl Case {
 264     fn is_zerolen(&self, cx: &CrateContext) -> bool {
 265         mk_struct(cx, self.tys.as_slice(), false).size == 0
 266     }
 267     fn find_ptr(&self) -> Option<uint> {
 268         self.tys.iter().position(|&ty| mono_data_classify(ty) == MonoNonNull)
 269     }
 270 }
 271
 272 fn get_cases(tcx: &ty::ctxt, def_id: ast::DefId, substs: &ty::substs) -> Vec<Case> {
 273     ty::enum_variants(tcx, def_id).map(|vi| {
 274         let arg_tys = vi.args.map(|&raw_ty| {
 275             ty::subst(tcx, substs, raw_ty)
 276         });
 277         Case { discr: vi.disr_val, tys: arg_tys }
 278     })
 279 }
 280
 281
 282 fn mk_struct(cx: &CrateContext, tys: &[ty::t], packed: bool) -> Struct {
 283     let lltys = tys.map(|&ty| type_of::sizing_type_of(cx, ty));
 284     let llty_rec = Type::struct_(cx, lltys, packed);
 285     Struct {
 286         size: machine::llsize_of_alloc(cx, llty_rec) /*bad*/as u64,
 287         align: machine::llalign_of_min(cx, llty_rec) /*bad*/as u64,
 288         packed: packed,
 289         fields: Vec::from_slice(tys),
 290     }
 291 }
 292
 293 struct IntBounds {
 294     slo: i64,
 295     shi: i64,
 296     ulo: u64,
 297     uhi: u64
 298 }
 299
 300 fn mk_cenum(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> Repr {
 301     let it = range_to_inttype(cx, hint, bounds);
 302     match it {
 303         attr::SignedInt(_) => CEnum(it, bounds.slo as Disr, bounds.shi as Disr),
 304         attr::UnsignedInt(_) => CEnum(it, bounds.ulo, bounds.uhi)
 305     }
 306 }
 307
 308 fn range_to_inttype(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> IntType {
 309     debug!("range_to_inttype: {:?} {:?}", hint, bounds);
 310     // Lists of sizes to try.  u64 is always allowed as a fallback.
 311     static choose_shortest: &'static[IntType] = &[
 312         attr::UnsignedInt(ast::TyU8), attr::SignedInt(ast::TyI8),
 313         attr::UnsignedInt(ast::TyU16), attr::SignedInt(ast::TyI16),
 314         attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
 315     static at_least_32: &'static[IntType] = &[
 316         attr::UnsignedInt(ast::TyU32), attr::SignedInt(ast::TyI32)];
 317
 318     let attempts;
 319     match hint {
 320         attr::ReprInt(span, ity) => {
 321             if !bounds_usable(cx, ity, bounds) {
 322                 cx.sess().span_bug(span, "representation hint insufficient for discriminant range")
 323             }
 324             return ity;
 325         }
 326         attr::ReprExtern => {
 327             attempts = match cx.sess().targ_cfg.arch {
 328                 X86 | X86_64 => at_least_32,
 329                 // WARNING: the ARM EABI has two variants; the one corresponding to `at_least_32`
 330                 // appears to be used on Linux and NetBSD, but some systems may use the variant
 331                 // corresponding to `choose_shortest`.  However, we don't run on those yet...?
 332                 Arm => at_least_32,
 333                 Mips => at_least_32,
 334             }
 335         }
 336         attr::ReprAny => {
 337             attempts = choose_shortest;
 338         }
 339     }
 340     for &ity in attempts.iter() {
 341         if bounds_usable(cx, ity, bounds) {
 342             return ity;
 343         }
 344     }
 345     return attr::UnsignedInt(ast::TyU64);
 346 }
 347
 348 pub fn ll_inttype(cx: &CrateContext, ity: IntType) -> Type {
 349     match ity {
 350         attr::SignedInt(t) => Type::int_from_ty(cx, t),
 351         attr::UnsignedInt(t) => Type::uint_from_ty(cx, t)
 352     }
 353 }
 354
 355 fn bounds_usable(cx: &CrateContext, ity: IntType, bounds: &IntBounds) -> bool {
 356     debug!("bounds_usable: {:?} {:?}", ity, bounds);
 357     match ity {
 358         attr::SignedInt(_) => {
 359             let lllo = C_integral(ll_inttype(cx, ity), bounds.slo as u64, true);
 360             let llhi = C_integral(ll_inttype(cx, ity), bounds.shi as u64, true);
 361             bounds.slo == const_to_int(lllo) as i64 && bounds.shi == const_to_int(llhi) as i64
 362         }
 363         attr::UnsignedInt(_) => {
 364             let lllo = C_integral(ll_inttype(cx, ity), bounds.ulo, false);
 365             let llhi = C_integral(ll_inttype(cx, ity), bounds.uhi, false);
 366             bounds.ulo == const_to_uint(lllo) as u64 && bounds.uhi == const_to_uint(llhi) as u64
 367         }
 368     }
 369 }
 370
 371 pub fn ty_of_inttype(ity: IntType) -> ty::t {
 372     match ity {
 373         attr::SignedInt(t) => ty::mk_mach_int(t),
 374         attr::UnsignedInt(t) => ty::mk_mach_uint(t)
 375     }
 376 }
 377
 378
 379 /**
 380  * LLVM-level types are a little complicated.
 381  *
 382  * C-like enums need to be actual ints, not wrapped in a struct,
 383  * because that changes the ABI on some platforms (see issue #10308).
 384  *
 385  * For nominal types, in some cases, we need to use LLVM named structs
 386  * and fill in the actual contents in a second pass to prevent
 387  * unbounded recursion; see also the comments in `trans::type_of`.
 388  */
 389 pub fn type_of(cx: &CrateContext, r: &Repr) -> Type {
 390     generic_type_of(cx, r, None, false)
 391 }
 392 pub fn sizing_type_of(cx: &CrateContext, r: &Repr) -> Type {
 393     generic_type_of(cx, r, None, true)
 394 }
 395 pub fn incomplete_type_of(cx: &CrateContext, r: &Repr, name: &str) -> Type {
 396     generic_type_of(cx, r, Some(name), false)
 397 }
 398 pub fn finish_type_of(cx: &CrateContext, r: &Repr, llty: &mut Type) {
 399     match *r {
 400         CEnum(..) | General(..) => { }
 401         Univariant(ref st, _) | NullablePointer{ nonnull: ref st, .. } =>
 402             llty.set_struct_body(struct_llfields(cx, st, false).as_slice(),
 403                                  st.packed)
 404     }
 405 }
 406
 407 fn generic_type_of(cx: &CrateContext, r: &Repr, name: Option<&str>, sizing: bool) -> Type {
 408     match *r {
 409         CEnum(ity, _, _) => ll_inttype(cx, ity),
 410         Univariant(ref st, _) | NullablePointer{ nonnull: ref st, .. } => {
 411             match name {
 412                 None => {
 413                     Type::struct_(cx, struct_llfields(cx, st, sizing).as_slice(),
 414                                   st.packed)
 415                 }
 416                 Some(name) => { assert_eq!(sizing, false); Type::named_struct(cx, name) }
 417             }
 418         }
 419         General(ity, ref sts) => {
 420             // We need a representation that has:
 421             // * The alignment of the most-aligned field
 422             // * The size of the largest variant (rounded up to that alignment)
 423             // * No alignment padding anywhere any variant has actual data
 424             //   (currently matters only for enums small enough to be immediate)
 425             // * The discriminant in an obvious place.
 426             //
 427             // So we start with the discriminant, pad it up to the alignment with
 428             // more of its own type, then use alignment-sized ints to get the rest
 429             // of the size.
 430             //
 431             // FIXME #10604: this breaks when vector types are present.
 432             let size = sts.iter().map(|st| st.size).max().unwrap();
 433             let most_aligned = sts.iter().max_by(|st| st.align).unwrap();
 434             let align = most_aligned.align;
 435             let discr_ty = ll_inttype(cx, ity);
 436             let discr_size = machine::llsize_of_alloc(cx, discr_ty) as u64;
 437             let align_units = (size + align - 1) / align - 1;
 438             let pad_ty = match align {
 439                 1 => Type::array(&Type::i8(cx), align_units),
 440                 2 => Type::array(&Type::i16(cx), align_units),
 441                 4 => Type::array(&Type::i32(cx), align_units),
 442                 8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
 443                                  Type::array(&Type::i64(cx), align_units),
 444                 a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(cx), a / 4),
 445                                                               align_units),
 446                 _ => fail!("unsupported enum alignment: {:?}", align)
 447             };
 448             assert_eq!(machine::llalign_of_min(cx, pad_ty) as u64, align);
 449             assert_eq!(align % discr_size, 0);
 450             let fields = vec!(discr_ty,
 451                            Type::array(&discr_ty, align / discr_size - 1),
 452                            pad_ty);
 453             match name {
 454                 None => Type::struct_(cx, fields.as_slice(), false),
 455                 Some(name) => {
 456                     let mut llty = Type::named_struct(cx, name);
 457                     llty.set_struct_body(fields.as_slice(), false);
 458                     llty
 459                 }
 460             }
 461         }
 462     }
 463 }
 464
 465 fn struct_llfields(cx: &CrateContext, st: &Struct, sizing: bool) -> Vec<Type> {
 466     if sizing {
 467         st.fields.map(|&ty| type_of::sizing_type_of(cx, ty))
 468     } else {
 469         st.fields.map(|&ty| type_of::type_of(cx, ty))
 470     }
 471 }
 472
 473 /**
 474  * Obtain a representation of the discriminant sufficient to translate
 475  * destructuring; this may or may not involve the actual discriminant.
 476  *
 477  * This should ideally be less tightly tied to `_match`.
 478  */
 479 pub fn trans_switch(bcx: &Block, r: &Repr, scrutinee: ValueRef)
 480     -> (_match::branch_kind, Option<ValueRef>) {
 481     match *r {
 482         CEnum(..) | General(..) => {
 483             (_match::switch, Some(trans_get_discr(bcx, r, scrutinee, None)))
 484         }
 485         NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
 486             (_match::switch, Some(nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee)))
 487         }
 488         Univariant(..) => {
 489             (_match::single, None)
 490         }
 491     }
 492 }
 493
 494
 495
 496 /// Obtain the actual discriminant of a value.
 497 pub fn trans_get_discr(bcx: &Block, r: &Repr, scrutinee: ValueRef, cast_to: Option<Type>)
 498     -> ValueRef {
 499     let signed;
 500     let val;
 501     match *r {
 502         CEnum(ity, min, max) => {
 503             val = load_discr(bcx, ity, scrutinee, min, max);
 504             signed = ity.is_signed();
 505         }
 506         General(ity, ref cases) => {
 507             let ptr = GEPi(bcx, scrutinee, [0, 0]);
 508             val = load_discr(bcx, ity, ptr, 0, (cases.len() - 1) as Disr);
 509             signed = ity.is_signed();
 510         }
 511         Univariant(..) => {
 512             val = C_u8(bcx.ccx(), 0);
 513             signed = false;
 514         }
 515         NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
 516             val = nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee);
 517             signed = false;
 518         }
 519     }
 520     match cast_to {
 521         None => val,
 522         Some(llty) => if signed { SExt(bcx, val, llty) } else { ZExt(bcx, val, llty) }
 523     }
 524 }
 525
 526 fn nullable_bitdiscr(bcx: &Block, nonnull: &Struct, nndiscr: Disr, ptrfield: uint,
 527                      scrutinee: ValueRef) -> ValueRef {
 528     let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
 529     let llptr = Load(bcx, GEPi(bcx, scrutinee, [0, ptrfield]));
 530     let llptrty = type_of::type_of(bcx.ccx(), *nonnull.fields.get(ptrfield));
 531     ICmp(bcx, cmp, llptr, C_null(llptrty))
 532 }
 533
 534 /// Helper for cases where the discriminant is simply loaded.
 535 fn load_discr(bcx: &Block, ity: IntType, ptr: ValueRef, min: Disr, max: Disr)
 536     -> ValueRef {
 537     let llty = ll_inttype(bcx.ccx(), ity);
 538     assert_eq!(val_ty(ptr), llty.ptr_to());
 539     let bits = machine::llbitsize_of_real(bcx.ccx(), llty);
 540     assert!(bits <= 64);
 541     let mask = (-1u64 >> (64 - bits)) as Disr;
 542     if (max + 1) & mask == min & mask {
 543         // i.e., if the range is everything.  The lo==hi case would be
 544         // rejected by the LLVM verifier (it would mean either an
 545         // empty set, which is impossible, or the entire range of the
 546         // type, which is pointless).
 547         Load(bcx, ptr)
 548     } else {
 549         // llvm::ConstantRange can deal with ranges that wrap around,
 550         // so an overflow on (max + 1) is fine.
 551         LoadRangeAssert(bcx, ptr, min as c_ulonglong,
 552                         (max + 1) as c_ulonglong,
 553                         /* signed: */ True)
 554     }
 555 }
 556
 557 /**
 558  * Yield information about how to dispatch a case of the
 559  * discriminant-like value returned by `trans_switch`.
 560  *
 561  * This should ideally be less tightly tied to `_match`.
 562  */
 563 pub fn trans_case<'a>(bcx: &'a Block<'a>, r: &Repr, discr: Disr)
 564                   -> _match::opt_result<'a> {
 565     match *r {
 566         CEnum(ity, _, _) => {
 567             _match::single_result(rslt(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
 568                                                        discr as u64, true)))
 569         }
 570         General(ity, _) => {
 571             _match::single_result(rslt(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
 572                                                        discr as u64, true)))
 573         }
 574         Univariant(..) => {
 575             bcx.ccx().sess().bug("no cases for univariants or structs")
 576         }
 577         NullablePointer{ .. } => {
 578             assert!(discr == 0 || discr == 1);
 579             _match::single_result(rslt(bcx, C_i1(bcx.ccx(), discr != 0)))
 580         }
 581     }
 582 }
 583
 584 /**
 585  * Begin initializing a new value of the given case of the given
 586  * representation.  The fields, if any, should then be initialized via
 587  * `trans_field_ptr`.
 588  */
 589 pub fn trans_start_init(bcx: &Block, r: &Repr, val: ValueRef, discr: Disr) {
 590     match *r {
 591         CEnum(ity, min, max) => {
 592             assert_discr_in_range(ity, min, max, discr);
 593             Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
 594                   val)
 595         }
 596         General(ity, _) => {
 597             Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
 598                   GEPi(bcx, val, [0, 0]))
 599         }
 600         Univariant(ref st, true) => {
 601             assert_eq!(discr, 0);
 602             Store(bcx, C_bool(bcx.ccx(), true),
 603                   GEPi(bcx, val, [0, st.fields.len() - 1]))
 604         }
 605         Univariant(..) => {
 606             assert_eq!(discr, 0);
 607         }
 608         NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
 609             if discr != nndiscr {
 610                 let llptrptr = GEPi(bcx, val, [0, ptrfield]);
 611                 let llptrty = type_of::type_of(bcx.ccx(),
 612                                                *nonnull.fields.get(ptrfield));
 613                 Store(bcx, C_null(llptrty), llptrptr)
 614             }
 615         }
 616     }
 617 }
 618
 619 fn assert_discr_in_range(ity: IntType, min: Disr, max: Disr, discr: Disr) {
 620     match ity {
 621         attr::UnsignedInt(_) => assert!(min <= discr && discr <= max),
 622         attr::SignedInt(_) => assert!(min as i64 <= discr as i64 && discr as i64 <= max as i64)
 623     }
 624 }
 625
 626 /**
 627  * The number of fields in a given case; for use when obtaining this
 628  * information from the type or definition is less convenient.
 629  */
 630 pub fn num_args(r: &Repr, discr: Disr) -> uint {
 631     match *r {
 632         CEnum(..) => 0,
 633         Univariant(ref st, dtor) => {
 634             assert_eq!(discr, 0);
 635             st.fields.len() - (if dtor { 1 } else { 0 })
 636         }
 637         General(_, ref cases) => cases.get(discr as uint).fields.len() - 1,
 638         NullablePointer{ nonnull: ref nonnull, nndiscr,
 639                          nullfields: ref nullfields, .. } => {
 640             if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
 641         }
 642     }
 643 }
 644
 645 /// Access a field, at a point when the value's case is known.
 646 pub fn deref_ty(ccx: &CrateContext, r: &Repr) -> ty::t {
 647     match *r {
 648         CEnum(..) => {
 649             ccx.sess().bug("deref of c-like enum")
 650         }
 651         Univariant(ref st, _) => {
 652             *st.fields.get(0)
 653         }
 654         General(_, ref cases) => {
 655             assert!(cases.len() == 1);
 656             *cases.get(0).fields.get(0)
 657         }
 658         NullablePointer{ .. } => {
 659             ccx.sess().bug("deref of nullable ptr")
 660         }
 661     }
 662 }
 663
 664 /// Access a field, at a point when the value's case is known.
 665 pub fn trans_field_ptr(bcx: &Block, r: &Repr, val: ValueRef, discr: Disr,
 666                        ix: uint) -> ValueRef {
 667     // Note: if this ever needs to generate conditionals (e.g., if we
 668     // decide to do some kind of cdr-coding-like non-unique repr
 669     // someday), it will need to return a possibly-new bcx as well.
 670     match *r {
 671         CEnum(..) => {
 672             bcx.ccx().sess().bug("element access in C-like enum")
 673         }
 674         Univariant(ref st, _dtor) => {
 675             assert_eq!(discr, 0);
 676             struct_field_ptr(bcx, st, val, ix, false)
 677         }
 678         General(_, ref cases) => {
 679             struct_field_ptr(bcx, cases.get(discr as uint), val, ix + 1, true)
 680         }
 681         NullablePointer{ nonnull: ref nonnull, nullfields: ref nullfields,
 682                          nndiscr, .. } => {
 683             if discr == nndiscr {
 684                 struct_field_ptr(bcx, nonnull, val, ix, false)
 685             } else {
 686                 // The unit-like case might have a nonzero number of unit-like fields.
 687                 // (e.g., Result or Either with () as one side.)
 688                 let ty = type_of::type_of(bcx.ccx(), *nullfields.get(ix));
 689                 assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
 690                 // The contents of memory at this pointer can't matter, but use
 691                 // the value that's "reasonable" in case of pointer comparison.
 692                 PointerCast(bcx, val, ty.ptr_to())
 693             }
 694         }
 695     }
 696 }
 697
 698 fn struct_field_ptr(bcx: &Block, st: &Struct, val: ValueRef, ix: uint,
 699               needs_cast: bool) -> ValueRef {
 700     let ccx = bcx.ccx();
 701
 702     let val = if needs_cast {
 703         let fields = st.fields.map(|&ty| type_of::type_of(ccx, ty));
 704         let real_ty = Type::struct_(ccx, fields.as_slice(), st.packed);
 705         PointerCast(bcx, val, real_ty.ptr_to())
 706     } else {
 707         val
 708     };
 709
 710     GEPi(bcx, val, [0, ix])
 711 }
 712
 713 /// Access the struct drop flag, if present.
 714 pub fn trans_drop_flag_ptr(bcx: &Block, r: &Repr, val: ValueRef) -> ValueRef {
 715     match *r {
 716         Univariant(ref st, true) => GEPi(bcx, val, [0, st.fields.len() - 1]),
 717         _ => bcx.ccx().sess().bug("tried to get drop flag of non-droppable type")
 718     }
 719 }
 720
 721 /**
 722  * Construct a constant value, suitable for initializing a
 723  * GlobalVariable, given a case and constant values for its fields.
 724  * Note that this may have a different LLVM type (and different
 725  * alignment!) from the representation's `type_of`, so it needs a
 726  * pointer cast before use.
 727  *
 728  * The LLVM type system does not directly support unions, and only
 729  * pointers can be bitcast, so a constant (and, by extension, the
 730  * GlobalVariable initialized by it) will have a type that can vary
 731  * depending on which case of an enum it is.
 732  *
 733  * To understand the alignment situation, consider `enum E { V64(u64),
 734  * V32(u32, u32) }` on win32.  The type has 8-byte alignment to
 735  * accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
 736  * i32, i32}`, which is 4-byte aligned.
 737  *
 738  * Currently the returned value has the same size as the type, but
 739  * this could be changed in the future to avoid allocating unnecessary
 740  * space after values of shorter-than-maximum cases.
 741  */
 742 pub fn trans_const(ccx: &CrateContext, r: &Repr, discr: Disr,
 743                    vals: &[ValueRef]) -> ValueRef {
 744     match *r {
 745         CEnum(ity, min, max) => {
 746             assert_eq!(vals.len(), 0);
 747             assert_discr_in_range(ity, min, max, discr);
 748             C_integral(ll_inttype(ccx, ity), discr as u64, true)
 749         }
 750         General(ity, ref cases) => {
 751             let case = cases.get(discr as uint);
 752             let max_sz = cases.iter().map(|x| x.size).max().unwrap();
 753             let lldiscr = C_integral(ll_inttype(ccx, ity), discr as u64, true);
 754             let contents = build_const_struct(ccx,
 755                                               case,
 756                                               vec::append(
 757                                                   vec!(lldiscr),
 758                                                   vals).as_slice());
 759             C_struct(ccx, vec::append(
 760                         contents,
 761                         &[padding(ccx, max_sz - case.size)]).as_slice(),
 762                      false)
 763         }
 764         Univariant(ref st, _dro) => {
 765             assert!(discr == 0);
 766             let contents = build_const_struct(ccx, st, vals);
 767             C_struct(ccx, contents.as_slice(), st.packed)
 768         }
 769         NullablePointer{ nonnull: ref nonnull, nndiscr, .. } => {
 770             if discr == nndiscr {
 771                 C_struct(ccx, build_const_struct(ccx,
 772                                                  nonnull,
 773                                                  vals).as_slice(),
 774                          false)
 775             } else {
 776                 let vals = nonnull.fields.map(|&ty| {
 777                     // Always use null even if it's not the `ptrfield`th
 778                     // field; see #8506.
 779                     C_null(type_of::sizing_type_of(ccx, ty))
 780                 }).move_iter().collect::<Vec<ValueRef> >();
 781                 C_struct(ccx, build_const_struct(ccx,
 782                                                  nonnull,
 783                                                  vals.as_slice()).as_slice(),
 784                          false)
 785             }
 786         }
 787     }
 788 }
 789
 790 /**
 791  * Building structs is a little complicated, because we might need to
 792  * insert padding if a field's value is less aligned than its type.
 793  *
 794  * Continuing the example from `trans_const`, a value of type `(u32,
 795  * E)` should have the `E` at offset 8, but if that field's
 796  * initializer is 4-byte aligned then simply translating the tuple as
 797  * a two-element struct will locate it at offset 4, and accesses to it
 798  * will read the wrong memory.
 799  */
 800 fn build_const_struct(ccx: &CrateContext, st: &Struct, vals: &[ValueRef])
 801     -> Vec<ValueRef> {
 802     assert_eq!(vals.len(), st.fields.len());
 803
 804     let mut offset = 0;
 805     let mut cfields = Vec::new();
 806     for (i, &ty) in st.fields.iter().enumerate() {
 807         let llty = type_of::sizing_type_of(ccx, ty);
 808         let type_align = machine::llalign_of_min(ccx, llty)
 809             /*bad*/as u64;
 810         let val_align = machine::llalign_of_min(ccx, val_ty(vals[i]))
 811             /*bad*/as u64;
 812         let target_offset = roundup(offset, type_align);
 813         offset = roundup(offset, val_align);
 814         if offset != target_offset {
 815             cfields.push(padding(ccx, target_offset - offset));
 816             offset = target_offset;
 817         }
 818         assert!(!is_undef(vals[i]));
 819         cfields.push(vals[i]);
 820         offset += machine::llsize_of_alloc(ccx, llty) as u64
 821     }
 822
 823     return cfields;
 824 }
 825
 826 fn padding(ccx: &CrateContext, size: u64) -> ValueRef {
 827     C_undef(Type::array(&Type::i8(ccx), size))
 828 }
 829
 830 // FIXME this utility routine should be somewhere more general
 831 #[inline]
 832 fn roundup(x: u64, a: u64) -> u64 { ((x + (a - 1)) / a) * a }
 833
 834 /// Get the discriminant of a constant value.  (Not currently used.)
 835 pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef)
 836     -> Disr {
 837     match *r {
 838         CEnum(ity, _, _) => {
 839             match ity {
 840                 attr::SignedInt(..) => const_to_int(val) as Disr,
 841                 attr::UnsignedInt(..) => const_to_uint(val) as Disr
 842             }
 843         }
 844         General(ity, _) => {
 845             match ity {
 846                 attr::SignedInt(..) => const_to_int(const_get_elt(ccx, val, [0])) as Disr,
 847                 attr::UnsignedInt(..) => const_to_uint(const_get_elt(ccx, val, [0])) as Disr
 848             }
 849         }
 850         Univariant(..) => 0,
 851         NullablePointer{ nndiscr, ptrfield, .. } => {
 852             if is_null(const_struct_field(ccx, val, ptrfield)) {
 853                 /* subtraction as uint is ok because nndiscr is either 0 or 1 */
 854                 (1 - nndiscr) as Disr
 855             } else {
 856                 nndiscr
 857             }
 858         }
 859     }
 860 }
 861
 862 /**
 863  * Extract a field of a constant value, as appropriate for its
 864  * representation.
 865  *
 866  * (Not to be confused with `common::const_get_elt`, which operates on
 867  * raw LLVM-level structs and arrays.)
 868  */
 869 pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
 870                        _discr: Disr, ix: uint) -> ValueRef {
 871     match *r {
 872         CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
 873         Univariant(..) => const_struct_field(ccx, val, ix),
 874         General(..) => const_struct_field(ccx, val, ix + 1),
 875         NullablePointer{ .. } => const_struct_field(ccx, val, ix)
 876     }
 877 }
 878
 879 /// Extract field of struct-like const, skipping our alignment padding.
 880 fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint)
 881     -> ValueRef {
 882     // Get the ix-th non-undef element of the struct.
 883     let mut real_ix = 0; // actual position in the struct
 884     let mut ix = ix; // logical index relative to real_ix
 885     let mut field;
 886     loop {
 887         loop {
 888             field = const_get_elt(ccx, val, [real_ix]);
 889             if !is_undef(field) {
 890                 break;
 891             }
 892             real_ix = real_ix + 1;
 893         }
 894         if ix == 0 {
 895             return field;
 896         }
 897         ix = ix - 1;
 898         real_ix = real_ix + 1;
 899     }
 900 }
 901
 902 /// Is it safe to bitcast a value to the one field of its one variant?
 903 pub fn is_newtypeish(r: &Repr) -> bool {
 904     match *r {
 905         Univariant(ref st, false) => st.fields.len() == 1,
 906         _ => false
 907     }
 908 }