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