adt.rs 37.4 KB
Newer Older
1 2 3 4 5 6 7 8 9 10
// Copyright 2013 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.

11 12 13
/*!
 * # Representation of Algebraic Data Types
 *
14 15 16
 * This module determines how to represent enums, structs, and tuples
 * based on their monomorphized types; it is responsible both for
 * choosing a representation and translating basic operations on
17 18
 * values of those types.  (Note: exporting the representations for
 * debuggers is handled in debuginfo.rs, not here.)
19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
 *
 * Note that the interface treats everything as a general case of an
 * enum, so structs/tuples/etc. have one pseudo-variant with
 * discriminant 0; i.e., as if they were a univariant enum.
 *
 * Having everything in one place will enable improvements to data
 * structure representation; possibilities include:
 *
 * - User-specified alignment (e.g., cacheline-aligning parts of
 *   concurrently accessed data structures); LLVM can't represent this
 *   directly, so we'd have to insert padding fields in any structure
 *   that might contain one and adjust GEP indices accordingly.  See
 *   issue #4578.
 *
 * - Store nested enums' discriminants in the same word.  Rather, if
 *   some variants start with enums, and those enums representations
 *   have unused alignment padding between discriminant and body, the
 *   outer enum's discriminant can be stored there and those variants
 *   can start at offset 0.  Kind of fancy, and might need work to
 *   make copies of the inner enum type cooperate, but it could help
 *   with `Option` or `Result` wrapped around another enum.
 *
 * - Tagged pointers would be neat, but given that any type can be
 *   used unboxed and any field can have pointers (including mutable)
 *   taken to it, implementing them for Rust seems difficult.
 */

46 47
#![allow(unsigned_negate)]

48
use libc::c_ulonglong;
E
Eduard Burtescu 已提交
49
use std::rc::Rc;
50

J
James Miller 已提交
51
use lib::llvm::{ValueRef, True, IntEQ, IntNE};
52 53
use middle::subst;
use middle::subst::Subst;
54 55 56 57
use middle::trans::_match;
use middle::trans::build::*;
use middle::trans::common::*;
use middle::trans::machine;
58
use middle::trans::type_::Type;
59 60
use middle::trans::type_of;
use middle::ty;
61
use middle::ty::Disr;
62
use syntax::abi::{X86, X86_64, Arm, Mips, Mipsel};
63
use syntax::ast;
64 65
use syntax::attr;
use syntax::attr::IntType;
66 67
use util::ppaux::ty_to_str;

68 69
type Hint = attr::ReprAttr;

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)
J
Jed Davis 已提交
75 76 77 78 79 80 81 82
    /**
     * Single-case variants, and structs/tuples/records.
     *
     * Structs with destructors need a dynamic destroyedness flag to
     * avoid running the destructor too many times; this is included
     * in the `Struct` if present.
     */
    Univariant(Struct, bool),
83
    /**
84 85
     * General-case enums: for each case there is a struct, and they
     * all start with a field for the discriminant.
86
     */
87
    General(IntType, Vec<Struct>),
88 89 90 91 92 93 94 95 96 97 98 99
    /**
     * Two cases distinguished by a nullable pointer: the case with discriminant
     * `nndiscr` must have single field which is known to be nonnull due to its type.
     * The other case is known to be zero sized. Hence we represent the enum
     * as simply a nullable pointer: if not null it indicates the `nndiscr` variant,
     * otherwise it indicates the other case.
     */
    RawNullablePointer {
        pub nndiscr: Disr,
        pub nnty: ty::t,
        pub nullfields: Vec<ty::t>
    },
100 101 102 103 104 105 106
    /**
     * Two cases distinguished by a nullable pointer: the case with discriminant
     * `nndiscr` is represented by the struct `nonnull`, where the `ptrfield`th
     * field is known to be nonnull due to its type; if that field is null, then
     * it represents the other case, which is inhabited by at most one value
     * (and all other fields are undefined/unused).
     *
107
     * For example, `std::option::Option` instantiated at a safe pointer type
108 109 110
     * is represented such that `None` is a null pointer and `Some` is the
     * identity function.
     */
111
    StructWrappedNullablePointer {
112 113 114 115 116
        pub nonnull: Struct,
        pub nndiscr: Disr,
        pub ptrfield: uint,
        pub nullfields: Vec<ty::t>,
    }
117 118
}

119
/// For structs, and struct-like parts of anything fancier.
120
pub struct Struct {
121 122 123 124 125
    pub size: u64,
    pub align: u64,
    pub packed: bool,
    pub fields: Vec<ty::t>,
}
126

127 128 129 130 131
/**
 * Convenience for `represent_type`.  There should probably be more or
 * these, for places in trans where the `ty::t` isn't directly
 * available.
 */
E
Eduard Burtescu 已提交
132
pub fn represent_node(bcx: &Block, node: ast::NodeId) -> Rc<Repr> {
133 134 135
    represent_type(bcx.ccx(), node_id_type(bcx, node))
}

136
/// Decides how to represent a given type.
E
Eduard Burtescu 已提交
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) {
E
Eduard Burtescu 已提交
140
        Some(repr) => return repr.clone(),
141
        None => {}
J
Jed Davis 已提交
142
    }
143

E
Eduard Burtescu 已提交
144
    let repr = Rc::new(represent_type_uncached(cx, t));
145
    debug!("Represented as: {:?}", repr)
E
Eduard Burtescu 已提交
146 147
    cx.adt_reprs.borrow_mut().insert(t, repr.clone());
    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 161
            let packed = ty::lookup_packed(cx.tcx(), def_id);
            let dtor = ty::ty_dtor(cx.tcx(), def_id).has_drop_flag();
162 163
            if dtor { ftys.push(ty::mk_bool()); }

164
            return Univariant(mk_struct(cx, ftys.as_slice(), packed), dtor)
165 166
        }
        ty::ty_enum(def_id, ref substs) => {
167 168
            let cases = get_cases(cx.tcx(), def_id, substs);
            let hint = ty::lookup_repr_hint(cx.tcx(), def_id);
169

170 171
            if cases.len() == 0 {
                // Uninhabitable; represent as unit
172 173
                // (Typechecking will reject discriminant-sizing attrs.)
                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 181 182 183 184 185 186
                let bounds = IntBounds {
                    ulo: *discrs.iter().min().unwrap(),
                    uhi: *discrs.iter().max().unwrap(),
                    slo: discrs.iter().map(|n| *n as i64).min().unwrap(),
                    shi: discrs.iter().map(|n| *n as i64).max().unwrap()
                };
                return mk_cenum(cx, hint, &bounds);
187 188 189 190 191
            }

            // Since there's at least one
            // non-empty body, explicit discriminants should have
            // been rejected by a checker before this point.
192
            if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
E
Eduard Burtescu 已提交
193 194
                cx.sess().bug(format!("non-C-like enum {} with specified \
                                      discriminants",
195 196
                                      ty::item_path_str(cx.tcx(),
                                                        def_id)).as_slice())
197 198
            }

199 200 201 202
            if cases.len() == 1 {
                // Equivalent to a struct/tuple/newtype.
                // (Typechecking will reject discriminant-sizing attrs.)
                assert_eq!(hint, attr::ReprAny);
203 204 205 206
                return Univariant(mk_struct(cx,
                                            cases.get(0).tys.as_slice(),
                                            false),
                                  false)
207 208 209 210
            }

            if cases.len() == 2 && hint == attr::ReprAny {
                // Nullable pointer optimization
211 212
                let mut discr = 0;
                while discr < 2 {
213 214
                    if cases.get(1 - discr).is_zerolen(cx) {
                        match cases.get(discr).find_ptr() {
215
                            Some(ptrfield) => {
216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
                                let st = mk_struct(cx, cases.get(discr).tys.as_slice(),
                                                   false);

                                return if st.fields.len() == 1 {
                                    RawNullablePointer {
                                        nndiscr: discr as Disr,
                                        nnty: *st.fields.get(0),
                                        nullfields: cases.get(1 - discr).tys.clone()
                                    }
                                } else {
                                    StructWrappedNullablePointer {
                                        nndiscr: discr as Disr,
                                        nonnull: st,
                                        ptrfield: ptrfield,
                                        nullfields: cases.get(1 - discr).tys.clone()
                                    }
                                };
233 234 235 236 237
                            }
                            None => { }
                        }
                    }
                    discr += 1;
238 239
                }
            }
240 241

            // The general case.
242 243 244 245
            assert!((cases.len() - 1) as i64 >= 0);
            let bounds = IntBounds { ulo: 0, uhi: (cases.len() - 1) as u64,
                                     slo: 0, shi: (cases.len() - 1) as i64 };
            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
        }
E
Eduard Burtescu 已提交
251
        _ => cx.sess().bug("adt::represent_type called on non-ADT type")
252
    }
253 254
}

J
Jed Davis 已提交
255 256
/// Determine, without doing translation, whether an ADT must be FFI-safe.
/// For use in lint or similar, where being sound but slightly incomplete is acceptable.
E
Eduard Burtescu 已提交
257
pub fn is_ffi_safe(tcx: &ty::ctxt, def_id: ast::DefId) -> bool {
J
Jed Davis 已提交
258
    match ty::get(ty::lookup_item_type(tcx, def_id).ty).sty {
259 260
        ty::ty_enum(def_id, _) => {
            let variants = ty::enum_variants(tcx, def_id);
J
Jed Davis 已提交
261
            // Univariant => like struct/tuple.
262
            if variants.len() <= 1 {
J
Jed Davis 已提交
263 264 265 266 267 268 269
                return true;
            }
            let hint = ty::lookup_repr_hint(tcx, def_id);
            // Appropriate representation explicitly selected?
            if hint.is_ffi_safe() {
                return true;
            }
270 271 272 273
            // Option<Box<T>> and similar are used in FFI.  Rather than try to
            // resolve type parameters and recognize this case exactly, this
            // overapproximates -- assuming that if a non-C-like enum is being
            // used in FFI then the user knows what they're doing.
274
            if variants.iter().any(|vi| !vi.args.is_empty()) {
J
Jed Davis 已提交
275 276 277 278 279 280 281 282 283 284
                return true;
            }
            false
        }
        // struct, tuple, etc.
        // (is this right in the present of typedefs?)
        _ => true
    }
}

A
Alex Crichton 已提交
285
// this should probably all be in ty
286
struct Case { discr: Disr, tys: Vec<ty::t> }
J
Jed Davis 已提交
287
impl Case {
288
    fn is_zerolen(&self, cx: &CrateContext) -> bool {
289
        mk_struct(cx, self.tys.as_slice(), false).size == 0
J
Jed Davis 已提交
290 291
    }
    fn find_ptr(&self) -> Option<uint> {
292 293
        self.tys.iter().position(|&ty| {
            match ty::get(ty).sty {
N
Nick Cameron 已提交
294 295
                ty::ty_uniq(ty) | ty::ty_rptr(_, ty::mt{ty, ..}) => match ty::get(ty).sty {
                    ty::ty_vec(_, None) | ty::ty_str| ty::ty_trait(..) => false,
296 297
                    _ => true,
                },
N
Nick Cameron 已提交
298
                ty::ty_box(..) | ty::ty_bare_fn(..) => true,
299 300 301 302
                // Is that everything?  Would closures or slices qualify?
                _ => false
            }
        })
J
Jed Davis 已提交
303 304 305
    }
}

306
fn get_cases(tcx: &ty::ctxt, def_id: ast::DefId, substs: &subst::Substs) -> Vec<Case> {
307 308
    ty::enum_variants(tcx, def_id).iter().map(|vi| {
        let arg_tys = vi.args.iter().map(|&raw_ty| {
309
            raw_ty.subst(tcx, substs)
310
        }).collect();
J
Jed Davis 已提交
311
        Case { discr: vi.disr_val, tys: arg_tys }
312
    }).collect()
J
Jed Davis 已提交
313 314 315
}


316
fn mk_struct(cx: &CrateContext, tys: &[ty::t], packed: bool) -> Struct {
317 318
    let lltys = tys.iter().map(|&ty| type_of::sizing_type_of(cx, ty)).collect::<Vec<_>>();
    let llty_rec = Type::struct_(cx, lltys.as_slice(), packed);
319 320 321
    Struct {
        size: machine::llsize_of_alloc(cx, llty_rec) /*bad*/as u64,
        align: machine::llalign_of_min(cx, llty_rec) /*bad*/as u64,
322
        packed: packed,
323
        fields: Vec::from_slice(tys),
324 325 326
    }
}

327 328 329 330 331 332 333
struct IntBounds {
    slo: i64,
    shi: i64,
    ulo: u64,
    uhi: u64
}

334
fn mk_cenum(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> Repr {
335 336 337 338 339 340 341
    let it = range_to_inttype(cx, hint, bounds);
    match it {
        attr::SignedInt(_) => CEnum(it, bounds.slo as Disr, bounds.shi as Disr),
        attr::UnsignedInt(_) => CEnum(it, bounds.ulo, bounds.uhi)
    }
}

342
fn range_to_inttype(cx: &CrateContext, hint: Hint, bounds: &IntBounds) -> IntType {
343 344 345
    debug!("range_to_inttype: {:?} {:?}", hint, bounds);
    // Lists of sizes to try.  u64 is always allowed as a fallback.
    static choose_shortest: &'static[IntType] = &[
346 347 348
        attr::UnsignedInt(ast::TyU8), attr::SignedInt(ast::TyI8),
        attr::UnsignedInt(ast::TyU16), attr::SignedInt(ast::TyI16),
        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 353 354 355

    let attempts;
    match hint {
        attr::ReprInt(span, ity) => {
            if !bounds_usable(cx, ity, bounds) {
E
Eduard Burtescu 已提交
356
                cx.sess().span_bug(span, "representation hint insufficient for discriminant range")
357 358 359 360
            }
            return ity;
        }
        attr::ReprExtern => {
E
Eduard Burtescu 已提交
361
            attempts = match cx.sess().targ_cfg.arch {
362 363 364 365 366 367
                X86 | X86_64 => at_least_32,
                // WARNING: the ARM EABI has two variants; the one corresponding to `at_least_32`
                // appears to be used on Linux and NetBSD, but some systems may use the variant
                // corresponding to `choose_shortest`.  However, we don't run on those yet...?
                Arm => at_least_32,
                Mips => at_least_32,
368
                Mipsel => at_least_32,
369 370 371 372 373 374 375 376
            }
        }
        attr::ReprAny => {
            attempts = choose_shortest;
        }
    }
    for &ity in attempts.iter() {
        if bounds_usable(cx, ity, bounds) {
J
Jed Davis 已提交
377
            return ity;
378 379
        }
    }
380
    return attr::UnsignedInt(ast::TyU64);
381 382
}

383
pub fn ll_inttype(cx: &CrateContext, ity: IntType) -> Type {
384 385 386 387 388 389
    match ity {
        attr::SignedInt(t) => Type::int_from_ty(cx, t),
        attr::UnsignedInt(t) => Type::uint_from_ty(cx, t)
    }
}

390
fn bounds_usable(cx: &CrateContext, ity: IntType, bounds: &IntBounds) -> bool {
391 392 393 394 395 396 397 398 399 400 401 402 403 404 405
    debug!("bounds_usable: {:?} {:?}", ity, bounds);
    match ity {
        attr::SignedInt(_) => {
            let lllo = C_integral(ll_inttype(cx, ity), bounds.slo as u64, true);
            let llhi = C_integral(ll_inttype(cx, ity), bounds.shi as u64, true);
            bounds.slo == const_to_int(lllo) as i64 && bounds.shi == const_to_int(llhi) as i64
        }
        attr::UnsignedInt(_) => {
            let lllo = C_integral(ll_inttype(cx, ity), bounds.ulo, false);
            let llhi = C_integral(ll_inttype(cx, ity), bounds.uhi, false);
            bounds.ulo == const_to_uint(lllo) as u64 && bounds.uhi == const_to_uint(llhi) as u64
        }
    }
}

406
pub fn ty_of_inttype(ity: IntType) -> ty::t {
407 408 409 410 411 412
    match ity {
        attr::SignedInt(t) => ty::mk_mach_int(t),
        attr::UnsignedInt(t) => ty::mk_mach_uint(t)
    }
}

413

414
/**
415 416 417 418 419 420 421 422
 * LLVM-level types are a little complicated.
 *
 * C-like enums need to be actual ints, not wrapped in a struct,
 * because that changes the ABI on some platforms (see issue #10308).
 *
 * For nominal types, in some cases, we need to use LLVM named structs
 * and fill in the actual contents in a second pass to prevent
 * unbounded recursion; see also the comments in `trans::type_of`.
423
 */
424
pub fn type_of(cx: &CrateContext, r: &Repr) -> Type {
425 426
    generic_type_of(cx, r, None, false)
}
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 432
    generic_type_of(cx, r, Some(name), false)
}
433
pub fn finish_type_of(cx: &CrateContext, r: &Repr, llty: &mut Type) {
434
    match *r {
435 436
        CEnum(..) | General(..) | RawNullablePointer { .. } => { }
        Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } =>
437 438
            llty.set_struct_body(struct_llfields(cx, st, false).as_slice(),
                                 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 446
        RawNullablePointer { nnty, .. } => type_of::sizing_type_of(cx, nnty),
        Univariant(ref st, _) | StructWrappedNullablePointer { nonnull: ref st, .. } => {
447
            match name {
448
                None => {
449
                    Type::struct_(cx, struct_llfields(cx, st, sizing).as_slice(),
450 451
                                  st.packed)
                }
452
                Some(name) => { assert_eq!(sizing, false); Type::named_struct(cx, name) }
453 454
            }
        }
455 456 457 458 459 460 461 462 463 464 465 466
        General(ity, ref sts) => {
            // We need a representation that has:
            // * The alignment of the most-aligned field
            // * The size of the largest variant (rounded up to that alignment)
            // * No alignment padding anywhere any variant has actual data
            //   (currently matters only for enums small enough to be immediate)
            // * The discriminant in an obvious place.
            //
            // So we start with the discriminant, pad it up to the alignment with
            // more of its own type, then use alignment-sized ints to get the rest
            // of the size.
            //
467
            // FIXME #10604: this breaks when vector types are present.
468 469 470 471 472
            let size = sts.iter().map(|st| st.size).max().unwrap();
            let most_aligned = sts.iter().max_by(|st| st.align).unwrap();
            let align = most_aligned.align;
            let discr_ty = ll_inttype(cx, ity);
            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 476 477 478 479 480
                1 => Type::array(&Type::i8(cx), align_units),
                2 => Type::array(&Type::i16(cx), align_units),
                4 => Type::array(&Type::i32(cx), align_units),
                8 if machine::llalign_of_min(cx, Type::i64(cx)) == 8 =>
                                 Type::array(&Type::i64(cx), align_units),
                a if a.count_ones() == 1 => Type::array(&Type::vector(&Type::i32(cx), a / 4),
481
                                                              align_units),
M
mr.Shu 已提交
482
                _ => fail!("unsupported enum alignment: {:?}", align)
483 484 485
            };
            assert_eq!(machine::llalign_of_min(cx, pad_ty) as u64, align);
            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 495 496
                    llty
                }
            }
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 511 512
 * Obtain a representation of the discriminant sufficient to translate
 * destructuring; this may or may not involve the actual discriminant.
 *
513 514
 * This should ideally be less tightly tied to `_match`.
 */
515
pub fn trans_switch(bcx: &Block, r: &Repr, scrutinee: ValueRef)
516
    -> (_match::branch_kind, Option<ValueRef>) {
517
    match *r {
518 519
        CEnum(..) | General(..) |
        RawNullablePointer { .. } | StructWrappedNullablePointer { .. } => {
520
            (_match::switch, Some(trans_get_discr(bcx, r, scrutinee, None)))
521
        }
A
Alex Crichton 已提交
522
        Univariant(..) => {
523 524
            (_match::single, None)
        }
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 534
    let signed;
    let val;
535
    match *r {
536 537 538 539 540
        CEnum(ity, min, max) => {
            val = load_discr(bcx, ity, scrutinee, min, max);
            signed = ity.is_signed();
        }
        General(ity, ref cases) => {
541 542
            let ptr = GEPi(bcx, scrutinee, [0, 0]);
            val = load_discr(bcx, ity, ptr, 0, (cases.len() - 1) as Disr);
543 544
            signed = ity.is_signed();
        }
A
Alex Crichton 已提交
545
        Univariant(..) => {
546
            val = C_u8(bcx.ccx(), 0);
547 548
            signed = false;
        }
549 550 551 552 553 554 555 556
        RawNullablePointer { nndiscr, nnty, .. } =>  {
            let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
            let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
            val = ICmp(bcx, cmp, Load(bcx, scrutinee), C_null(llptrty));
            signed = false;
        }
        StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
            val = struct_wrapped_nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee);
557
            signed = false;
558
        }
559
    }
560 561 562 563
    match cast_to {
        None => val,
        Some(llty) => if signed { SExt(bcx, val, llty) } else { ZExt(bcx, val, llty) }
    }
564 565
}

566 567 568
fn struct_wrapped_nullable_bitdiscr(bcx: &Block, nonnull: &Struct, nndiscr: Disr, ptrfield: uint,
                                    scrutinee: ValueRef) -> ValueRef {
    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 572 573
    ICmp(bcx, cmp, llptr, C_null(llptrty))
}

574
/// Helper for cases where the discriminant is simply loaded.
575
fn load_discr(bcx: &Block, ity: IntType, ptr: ValueRef, min: Disr, max: Disr)
J
Jed Davis 已提交
576
    -> ValueRef {
577 578 579 580 581 582
    let llty = ll_inttype(bcx.ccx(), ity);
    assert_eq!(val_ty(ptr), llty.ptr_to());
    let bits = machine::llbitsize_of_real(bcx.ccx(), llty);
    assert!(bits <= 64);
    let mask = (-1u64 >> (64 - bits)) as Disr;
    if (max + 1) & mask == min & mask {
J
Jed Davis 已提交
583 584 585 586 587 588 589 590 591 592 593 594 595 596
        // i.e., if the range is everything.  The lo==hi case would be
        // rejected by the LLVM verifier (it would mean either an
        // empty set, which is impossible, or the entire range of the
        // type, which is pointless).
        Load(bcx, ptr)
    } else {
        // llvm::ConstantRange can deal with ranges that wrap around,
        // so an overflow on (max + 1) is fine.
        LoadRangeAssert(bcx, ptr, min as c_ulonglong,
                        (max + 1) as c_ulonglong,
                        /* signed: */ True)
    }
}

597 598 599
/**
 * Yield information about how to dispatch a case of the
 * discriminant-like value returned by `trans_switch`.
600
 *
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)
                  -> _match::opt_result<'a> {
605
    match *r {
606
        CEnum(ity, _, _) => {
N
Nick Cameron 已提交
607 608
            _match::single_result(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
                                                              discr as u64, true)))
609 610
        }
        General(ity, _) => {
N
Nick Cameron 已提交
611 612
            _match::single_result(Result::new(bcx, C_integral(ll_inttype(bcx.ccx(), ity),
                                                              discr as u64, true)))
613
        }
A
Alex Crichton 已提交
614
        Univariant(..) => {
E
Eduard Burtescu 已提交
615
            bcx.ccx().sess().bug("no cases for univariants or structs")
616
        }
617 618
        RawNullablePointer { .. } |
        StructWrappedNullablePointer { .. } => {
619
            assert!(discr == 0 || discr == 1);
N
Nick Cameron 已提交
620
            _match::single_result(Result::new(bcx, C_i1(bcx.ccx(), discr != 0)))
621
        }
622 623 624
    }
}

625 626
/**
 * Begin initializing a new value of the given case of the given
627 628
 * representation.  The fields, if any, should then be initialized via
 * `trans_field_ptr`.
629
 */
630
pub fn trans_start_init(bcx: &Block, r: &Repr, val: ValueRef, discr: Disr) {
631
    match *r {
632 633 634
        CEnum(ity, min, max) => {
            assert_discr_in_range(ity, min, max, discr);
            Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
635
                  val)
636 637 638 639
        }
        General(ity, _) => {
            Store(bcx, C_integral(ll_inttype(bcx.ccx(), ity), discr as u64, true),
                  GEPi(bcx, val, [0, 0]))
640
        }
J
Jed Davis 已提交
641
        Univariant(ref st, true) => {
642
            assert_eq!(discr, 0);
643
            Store(bcx, C_bool(bcx.ccx(), true),
J
Jed Davis 已提交
644
                  GEPi(bcx, val, [0, st.fields.len() - 1]))
645
        }
A
Alex Crichton 已提交
646
        Univariant(..) => {
647
            assert_eq!(discr, 0);
648
        }
649
        RawNullablePointer { nndiscr, nnty, ..} => {
650
            if discr != nndiscr {
651 652 653 654 655 656 657
                let llptrty = type_of::sizing_type_of(bcx.ccx(), nnty);
                Store(bcx, C_null(llptrty), val)
            }
        }
        StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr, ptrfield, .. } => {
            if discr != nndiscr {
                let llptrptr = GEPi(bcx, val, [0, ptrfield]);
658 659
                let llptrty = type_of::type_of(bcx.ccx(),
                                               *nonnull.fields.get(ptrfield));
660 661 662
                Store(bcx, C_null(llptrty), llptrptr)
            }
        }
663 664 665
    }
}

666 667 668 669 670 671 672
fn assert_discr_in_range(ity: IntType, min: Disr, max: Disr, discr: Disr) {
    match ity {
        attr::UnsignedInt(_) => assert!(min <= discr && discr <= max),
        attr::SignedInt(_) => assert!(min as i64 <= discr as i64 && discr as i64 <= max as i64)
    }
}

673 674 675 676
/**
 * The number of fields in a given case; for use when obtaining this
 * information from the type or definition is less convenient.
 */
677
pub fn num_args(r: &Repr, discr: Disr) -> uint {
678
    match *r {
A
Alex Crichton 已提交
679
        CEnum(..) => 0,
J
Jed Davis 已提交
680
        Univariant(ref st, dtor) => {
681
            assert_eq!(discr, 0);
J
Jed Davis 已提交
682 683
            st.fields.len() - (if dtor { 1 } else { 0 })
        }
684
        General(_, ref cases) => cases.get(discr as uint).fields.len() - 1,
685 686 687 688 689
        RawNullablePointer { nndiscr, ref nullfields, .. } => {
            if discr == nndiscr { 1 } else { nullfields.len() }
        }
        StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr,
                                       nullfields: ref nullfields, .. } => {
690
            if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
691
        }
692 693 694
    }
}

695
/// Access a field, at a point when the value's case is known.
696
pub fn trans_field_ptr(bcx: &Block, r: &Repr, val: ValueRef, discr: Disr,
697
                       ix: uint) -> ValueRef {
698 699
    // Note: if this ever needs to generate conditionals (e.g., if we
    // decide to do some kind of cdr-coding-like non-unique repr
700
    // someday), it will need to return a possibly-new bcx as well.
701
    match *r {
A
Alex Crichton 已提交
702
        CEnum(..) => {
E
Eduard Burtescu 已提交
703
            bcx.ccx().sess().bug("element access in C-like enum")
704
        }
J
Jed Davis 已提交
705
        Univariant(ref st, _dtor) => {
706
            assert_eq!(discr, 0);
707
            struct_field_ptr(bcx, st, val, ix, false)
708
        }
709
        General(_, ref cases) => {
710
            struct_field_ptr(bcx, cases.get(discr as uint), val, ix + 1, true)
711
        }
712 713 714 715 716 717 718
        RawNullablePointer { nndiscr, ref nullfields, .. } |
        StructWrappedNullablePointer { nndiscr, ref nullfields, .. } if discr != nndiscr => {
            // The unit-like case might have a nonzero number of unit-like fields.
            // (e.d., Result of Either with (), as one side.)
            let ty = type_of::type_of(bcx.ccx(), *nullfields.get(ix));
            assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
            // The contents of memory at this pointer can't matter, but use
719
            // the value that's "reasonable" in case of pointer comparison.
720 721 722 723 724 725 726 727 728 729 730
            PointerCast(bcx, val, ty.ptr_to())
        }
        RawNullablePointer { nndiscr, nnty, .. } => {
            assert_eq!(ix, 0);
            assert_eq!(discr, nndiscr);
            let ty = type_of::type_of(bcx.ccx(), nnty);
            PointerCast(bcx, val, ty.ptr_to())
        }
        StructWrappedNullablePointer { ref nonnull, nndiscr, .. } => {
            assert_eq!(discr, nndiscr);
            struct_field_ptr(bcx, nonnull, val, ix, false)
731
        }
732 733 734
    }
}

735
fn struct_field_ptr(bcx: &Block, st: &Struct, val: ValueRef, ix: uint,
736
              needs_cast: bool) -> ValueRef {
737 738
    let ccx = bcx.ccx();

739
    let val = if needs_cast {
740
        let fields = st.fields.iter().map(|&ty| type_of::type_of(ccx, ty)).collect::<Vec<_>>();
741
        let real_ty = Type::struct_(ccx, fields.as_slice(), st.packed);
J
James Miller 已提交
742
        PointerCast(bcx, val, real_ty.ptr_to())
743 744 745
    } else {
        val
    };
746

747
    GEPi(bcx, val, [0, ix])
748 749
}

750
/// Access the struct drop flag, if present.
751
pub fn trans_drop_flag_ptr(bcx: &Block, r: &Repr, val: ValueRef) -> ValueRef {
752
    match *r {
J
Jed Davis 已提交
753
        Univariant(ref st, true) => GEPi(bcx, val, [0, st.fields.len() - 1]),
E
Eduard Burtescu 已提交
754
        _ => bcx.ccx().sess().bug("tried to get drop flag of non-droppable type")
755 756 757
    }
}

758 759 760 761 762 763 764
/**
 * Construct a constant value, suitable for initializing a
 * GlobalVariable, given a case and constant values for its fields.
 * Note that this may have a different LLVM type (and different
 * alignment!) from the representation's `type_of`, so it needs a
 * pointer cast before use.
 *
765 766 767 768 769 770
 * The LLVM type system does not directly support unions, and only
 * pointers can be bitcast, so a constant (and, by extension, the
 * GlobalVariable initialized by it) will have a type that can vary
 * depending on which case of an enum it is.
 *
 * To understand the alignment situation, consider `enum E { V64(u64),
771 772 773
 * V32(u32, u32) }` on win32.  The type has 8-byte alignment to
 * accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
 * i32, i32}`, which is 4-byte aligned.
774 775
 *
 * Currently the returned value has the same size as the type, but
776
 * this could be changed in the future to avoid allocating unnecessary
777
 * space after values of shorter-than-maximum cases.
778
 */
779
pub fn trans_const(ccx: &CrateContext, r: &Repr, discr: Disr,
780 781
                   vals: &[ValueRef]) -> ValueRef {
    match *r {
782
        CEnum(ity, min, max) => {
783
            assert_eq!(vals.len(), 0);
784 785
            assert_discr_in_range(ity, min, max, discr);
            C_integral(ll_inttype(ccx, ity), discr as u64, true)
786
        }
787
        General(ity, ref cases) => {
788
            let case = cases.get(discr as uint);
789
            let max_sz = cases.iter().map(|x| x.size).max().unwrap();
790
            let lldiscr = C_integral(ll_inttype(ccx, ity), discr as u64, true);
791 792
            let contents = build_const_struct(ccx,
                                              case,
793 794
                                              (vec!(lldiscr)).append(vals).as_slice());
            C_struct(ccx, contents.append([padding(ccx, max_sz - case.size)]).as_slice(),
795
                     false)
796
        }
797 798 799
        Univariant(ref st, _dro) => {
            assert!(discr == 0);
            let contents = build_const_struct(ccx, st, vals);
800
            C_struct(ccx, contents.as_slice(), st.packed)
801
        }
802
        RawNullablePointer { nndiscr, nnty, .. } => {
803 804 805 806
            if discr == nndiscr {
                assert_eq!(vals.len(), 1);
                vals[0]
            } else {
807
                C_null(type_of::sizing_type_of(ccx, nnty))
808 809
            }
        }
810
        StructWrappedNullablePointer { nonnull: ref nonnull, nndiscr, .. } => {
811
            if discr == nndiscr {
812 813 814
                C_struct(ccx, build_const_struct(ccx,
                                                 nonnull,
                                                 vals).as_slice(),
815
                         false)
816
            } else {
817
                let vals = nonnull.fields.iter().map(|&ty| {
818 819 820
                    // Always use null even if it's not the `ptrfield`th
                    // field; see #8506.
                    C_null(type_of::sizing_type_of(ccx, ty))
821
                }).collect::<Vec<ValueRef>>();
822 823 824
                C_struct(ccx, build_const_struct(ccx,
                                                 nonnull,
                                                 vals.as_slice()).as_slice(),
825
                         false)
826 827
            }
        }
828 829 830
    }
}

831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850
/**
 * Compute struct field offsets relative to struct begin.
 */
fn compute_struct_field_offsets(ccx: &CrateContext, st: &Struct) -> Vec<u64> {
    let mut offsets = vec!();

    let mut offset = 0;
    for &ty in st.fields.iter() {
        let llty = type_of::sizing_type_of(ccx, ty);
        if !st.packed {
            let type_align = machine::llalign_of_min(ccx, llty) as u64;
            offset = roundup(offset, type_align);
        }
        offsets.push(offset);
        offset += machine::llsize_of_alloc(ccx, llty) as u64;
    }
    assert_eq!(st.fields.len(), offsets.len());
    offsets
}

J
Jed Davis 已提交
851 852 853
/**
 * Building structs is a little complicated, because we might need to
 * insert padding if a field's value is less aligned than its type.
854 855 856 857 858 859
 *
 * Continuing the example from `trans_const`, a value of type `(u32,
 * E)` should have the `E` at offset 8, but if that field's
 * initializer is 4-byte aligned then simply translating the tuple as
 * a two-element struct will locate it at offset 4, and accesses to it
 * will read the wrong memory.
J
Jed Davis 已提交
860
 */
861
fn build_const_struct(ccx: &CrateContext, st: &Struct, vals: &[ValueRef])
862
    -> Vec<ValueRef> {
863
    assert_eq!(vals.len(), st.fields.len());
864

865 866 867
    let target_offsets = compute_struct_field_offsets(ccx, st);

    // offset of current value
868
    let mut offset = 0;
869
    let mut cfields = Vec::new();
870 871 872 873 874 875
    for (&val, &target_offset) in vals.iter().zip(target_offsets.iter()) {
        if !st.packed {
            let val_align = machine::llalign_of_min(ccx, val_ty(val))
                /*bad*/as u64;
            offset = roundup(offset, val_align);
        }
H
Huon Wilson 已提交
876
        if offset != target_offset {
877
            cfields.push(padding(ccx, target_offset - offset));
878 879
            offset = target_offset;
        }
880 881 882 883 884 885 886 887
        assert!(!is_undef(val));
        cfields.push(val);
        offset += machine::llsize_of_alloc(ccx, val_ty(val)) as u64;
    }

    assert!(offset <= st.size);
    if offset != st.size {
        cfields.push(padding(ccx, st.size - offset));
888 889
    }

890
    cfields
891 892
}

893 894
fn padding(ccx: &CrateContext, size: u64) -> ValueRef {
    C_undef(Type::array(&Type::i8(ccx), size))
J
Jed Davis 已提交
895 896
}

897
// FIXME this utility routine should be somewhere more general
898
#[inline]
899 900
fn roundup(x: u64, a: u64) -> u64 { ((x + (a - 1)) / a) * a }

901
/// Get the discriminant of a constant value.  (Not currently used.)
902
pub fn const_get_discrim(ccx: &CrateContext, r: &Repr, val: ValueRef)
903
    -> Disr {
904
    match *r {
905 906
        CEnum(ity, _, _) => {
            match ity {
A
Alex Crichton 已提交
907 908
                attr::SignedInt(..) => const_to_int(val) as Disr,
                attr::UnsignedInt(..) => const_to_uint(val) as Disr
909 910 911 912
            }
        }
        General(ity, _) => {
            match ity {
A
Alex Crichton 已提交
913 914
                attr::SignedInt(..) => const_to_int(const_get_elt(ccx, val, [0])) as Disr,
                attr::UnsignedInt(..) => const_to_uint(const_get_elt(ccx, val, [0])) as Disr
915 916
            }
        }
A
Alex Crichton 已提交
917
        Univariant(..) => 0,
918
        RawNullablePointer { nndiscr, .. } => {
919 920 921 922 923 924 925
            if is_null(val) {
                /* subtraction as uint is ok because nndiscr is either 0 or 1 */
                (1 - nndiscr) as Disr
            } else {
                nndiscr
            }
        }
926
        StructWrappedNullablePointer { nndiscr, ptrfield, .. } => {
927 928
            if is_null(const_struct_field(ccx, val, ptrfield)) {
                /* subtraction as uint is ok because nndiscr is either 0 or 1 */
929
                (1 - nndiscr) as Disr
930 931 932
            } else {
                nndiscr
            }
933
        }
934 935 936
    }
}

937 938 939 940 941 942 943
/**
 * Extract a field of a constant value, as appropriate for its
 * representation.
 *
 * (Not to be confused with `common::const_get_elt`, which operates on
 * raw LLVM-level structs and arrays.)
 */
944
pub fn const_get_field(ccx: &CrateContext, r: &Repr, val: ValueRef,
945
                       _discr: Disr, ix: uint) -> ValueRef {
946
    match *r {
E
Eduard Burtescu 已提交
947
        CEnum(..) => ccx.sess().bug("element access in C-like enum const"),
A
Alex Crichton 已提交
948 949
        Univariant(..) => const_struct_field(ccx, val, ix),
        General(..) => const_struct_field(ccx, val, ix + 1),
950
        RawNullablePointer { .. } => {
951 952 953
            assert_eq!(ix, 0);
            val
        }
954
        StructWrappedNullablePointer{ .. } => const_struct_field(ccx, val, ix)
955 956 957
    }
}

J
Jed Davis 已提交
958
/// Extract field of struct-like const, skipping our alignment padding.
959
fn const_struct_field(ccx: &CrateContext, val: ValueRef, ix: uint)
960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979
    -> ValueRef {
    // Get the ix-th non-undef element of the struct.
    let mut real_ix = 0; // actual position in the struct
    let mut ix = ix; // logical index relative to real_ix
    let mut field;
    loop {
        loop {
            field = const_get_elt(ccx, val, [real_ix]);
            if !is_undef(field) {
                break;
            }
            real_ix = real_ix + 1;
        }
        if ix == 0 {
            return field;
        }
        ix = ix - 1;
        real_ix = real_ix + 1;
    }
}