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