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.
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.
12 * # Representation of Algebraic Data Types
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.
19 * Note that the interface treats everything as a general case of an
20 * enum, so structs/tuples/etc. have one pseudo-variant with
21 * discriminant 0; i.e., as if they were a univariant enum.
23 * Having everything in one place will enable improvements to data
24 * structure representation; possibilities include:
26 * - User-specified alignment (e.g., cacheline-aligning parts of
27 * concurrently accessed data structures); LLVM can't represent this
28 * directly, so we'd have to insert padding fields in any structure
29 * that might contain one and adjust GEP indices accordingly. See
32 * - Using smaller integer types for discriminants.
34 * - Store nested enums' discriminants in the same word. Rather, if
35 * some variants start with enums, and those enums representations
36 * have unused alignment padding between discriminant and body, the
37 * outer enum's discriminant can be stored there and those variants
38 * can start at offset 0. Kind of fancy, and might need work to
39 * make copies of the inner enum type cooperate, but it could help
40 * with `Option` or `Result` wrapped around another enum.
42 * - Tagged pointers would be neat, but given that any type can be
43 * used unboxed and any field can have pointers (including mutable)
44 * taken to it, implementing them for Rust seems difficult.
47 use std::container::Map;
48 use std::libc::c_ulonglong;
49 use std::option::{Option, Some, None};
51 use lib::llvm::{ValueRef, True, IntEQ, IntNE};
52 use middle::trans::_match;
53 use middle::trans::build::*;
54 use middle::trans::common::*;
55 use middle::trans::machine;
56 use middle::trans::type_of;
60 use util::ppaux::ty_to_str;
62 use middle::trans::type_::Type;
67 /// C-like enums; basically an int.
68 CEnum(Disr, Disr), // discriminant range
70 * Single-case variants, and structs/tuples/records.
72 * Structs with destructors need a dynamic destroyedness flag to
73 * avoid running the destructor too many times; this is included
74 * in the `Struct` if present.
76 Univariant(Struct, bool),
78 * General-case enums: for each case there is a struct, and they
79 * all start with a field for the discriminant.
83 * Two cases distinguished by a nullable pointer: the case with discriminant
84 * `nndiscr` is represented by the struct `nonnull`, where the `ptrfield`th
85 * field is known to be nonnull due to its type; if that field is null, then
86 * it represents the other case, which is inhabited by at most one value
87 * (and all other fields are undefined/unused).
89 * For example, `std::option::Option` instantiated at a safe pointer type
90 * is represented such that `None` is a null pointer and `Some` is the
93 NullablePointer{ nonnull: Struct, nndiscr: Disr, ptrfield: uint,
94 nullfields: ~[ty::t] }
97 /// For structs, and struct-like parts of anything fancier.
106 * Convenience for `represent_type`. There should probably be more or
107 * these, for places in trans where the `ty::t` isn't directly
110 pub fn represent_node(bcx: @mut Block, node: ast::NodeId) -> @Repr {
111 represent_type(bcx.ccx(), node_id_type(bcx, node))
114 /// Decides how to represent a given type.
115 pub fn represent_type(cx: &mut CrateContext, t: ty::t) -> @Repr {
116 debug2!("Representing: {}", ty_to_str(cx.tcx, t));
117 match cx.adt_reprs.find(&t) {
118 Some(repr) => return *repr,
121 let repr = @represent_type_uncached(cx, t);
122 debug2!("Represented as: {:?}", repr)
123 cx.adt_reprs.insert(t, repr);
127 fn represent_type_uncached(cx: &mut CrateContext, t: ty::t) -> Repr {
128 match ty::get(t).sty {
129 ty::ty_tup(ref elems) => {
130 return Univariant(mk_struct(cx, *elems, false), false)
132 ty::ty_struct(def_id, ref substs) => {
133 let fields = ty::lookup_struct_fields(cx.tcx, def_id);
134 let mut ftys = do fields.map |field| {
135 ty::lookup_field_type(cx.tcx, def_id, field.id, substs)
137 let packed = ty::lookup_packed(cx.tcx, def_id);
138 let dtor = ty::ty_dtor(cx.tcx, def_id).has_drop_flag();
139 if dtor { ftys.push(ty::mk_bool()); }
141 return Univariant(mk_struct(cx, ftys, packed), dtor)
143 ty::ty_enum(def_id, ref substs) => {
144 struct Case { discr: Disr, tys: ~[ty::t] };
146 fn is_zerolen(&self, cx: &mut CrateContext) -> bool {
147 mk_struct(cx, self.tys, false).size == 0
149 fn find_ptr(&self) -> Option<uint> {
150 self.tys.iter().position(|&ty| mono_data_classify(ty) == MonoNonNull)
154 let cases = do ty::enum_variants(cx.tcx, def_id).map |vi| {
155 let arg_tys = do vi.args.map |&raw_ty| {
156 ty::subst(cx.tcx, substs, raw_ty)
158 Case { discr: vi.disr_val, tys: arg_tys }
161 if cases.len() == 0 {
162 // Uninhabitable; represent as unit
163 return Univariant(mk_struct(cx, [], false), false);
166 if cases.iter().all(|c| c.tys.len() == 0) {
167 // All bodies empty -> intlike
168 let discrs = cases.map(|c| c.discr);
169 return CEnum(*discrs.iter().min().unwrap(), *discrs.iter().max().unwrap());
172 if cases.len() == 1 {
173 // Equivalent to a struct/tuple/newtype.
174 assert_eq!(cases[0].discr, 0);
175 return Univariant(mk_struct(cx, cases[0].tys, false), false)
178 // Since there's at least one
179 // non-empty body, explicit discriminants should have
180 // been rejected by a checker before this point.
181 if !cases.iter().enumerate().all(|(i,c)| c.discr == (i as Disr)) {
182 cx.sess.bug(format!("non-C-like enum {} with specified \
184 ty::item_path_str(cx.tcx, def_id)))
187 if cases.len() == 2 {
190 if cases[1 - discr].is_zerolen(cx) {
191 match cases[discr].find_ptr() {
193 return NullablePointer {
195 nonnull: mk_struct(cx,
199 nullfields: cases[1 - discr].tys.clone()
210 let discr = ~[ty::mk_uint()];
211 return General(cases.map(|c| mk_struct(cx, discr + c.tys, false)))
213 _ => cx.sess.bug("adt::represent_type called on non-ADT type")
217 fn mk_struct(cx: &mut CrateContext, tys: &[ty::t], packed: bool) -> Struct {
218 let lltys = tys.map(|&ty| type_of::sizing_type_of(cx, ty));
219 let llty_rec = Type::struct_(lltys, packed);
221 size: machine::llsize_of_alloc(cx, llty_rec) /*bad*/as u64,
222 align: machine::llalign_of_min(cx, llty_rec) /*bad*/as u64,
224 fields: tys.to_owned(),
229 * Returns the fields of a struct for the given representation.
230 * All nominal types are LLVM structs, in order to be able to use
231 * forward-declared opaque types to prevent circularity in `type_of`.
233 pub fn fields_of(cx: &mut CrateContext, r: &Repr) -> ~[Type] {
234 generic_fields_of(cx, r, false)
236 /// Like `fields_of`, but for `type_of::sizing_type_of` (q.v.).
237 pub fn sizing_fields_of(cx: &mut CrateContext, r: &Repr) -> ~[Type] {
238 generic_fields_of(cx, r, true)
240 fn generic_fields_of(cx: &mut CrateContext, r: &Repr, sizing: bool) -> ~[Type] {
242 CEnum(*) => ~[Type::enum_discrim(cx)],
243 Univariant(ref st, _dtor) => struct_llfields(cx, st, sizing),
244 NullablePointer{ nonnull: ref st, _ } => struct_llfields(cx, st, sizing),
245 General(ref sts) => {
246 // To get "the" type of a general enum, we pick the case
247 // with the largest alignment (so it will always align
248 // correctly in containing structures) and pad it out.
249 assert!(sts.len() >= 1);
250 let mut most_aligned = None;
251 let mut largest_align = 0;
252 let mut largest_size = 0;
253 for st in sts.iter() {
254 if largest_size < st.size {
255 largest_size = st.size;
257 if largest_align < st.align {
258 // Clang breaks ties by size; it is unclear if
259 // that accomplishes anything important.
260 largest_align = st.align;
261 most_aligned = Some(st);
264 let most_aligned = most_aligned.unwrap();
265 let padding = largest_size - most_aligned.size;
267 struct_llfields(cx, most_aligned, sizing)
268 + &[Type::array(&Type::i8(), padding)]
273 fn struct_llfields(cx: &mut CrateContext, st: &Struct, sizing: bool) -> ~[Type] {
275 st.fields.map(|&ty| type_of::sizing_type_of(cx, ty))
277 st.fields.map(|&ty| type_of::type_of(cx, ty))
282 * Obtain a representation of the discriminant sufficient to translate
283 * destructuring; this may or may not involve the actual discriminant.
285 * This should ideally be less tightly tied to `_match`.
287 pub fn trans_switch(bcx: @mut Block, r: &Repr, scrutinee: ValueRef)
288 -> (_match::branch_kind, Option<ValueRef>) {
290 CEnum(*) | General(*) => {
291 (_match::switch, Some(trans_get_discr(bcx, r, scrutinee)))
293 NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, _ } => {
294 (_match::switch, Some(nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee)))
297 (_match::single, None)
304 /// Obtain the actual discriminant of a value.
305 pub fn trans_get_discr(bcx: @mut Block, r: &Repr, scrutinee: ValueRef)
308 CEnum(min, max) => load_discr(bcx, scrutinee, min, max),
309 Univariant(*) => C_disr(bcx.ccx(), 0),
310 General(ref cases) => load_discr(bcx, scrutinee, 0, (cases.len() - 1) as Disr),
311 NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, _ } => {
312 ZExt(bcx, nullable_bitdiscr(bcx, nonnull, nndiscr, ptrfield, scrutinee),
313 Type::enum_discrim(bcx.ccx()))
318 fn nullable_bitdiscr(bcx: @mut Block, nonnull: &Struct, nndiscr: Disr, ptrfield: uint,
319 scrutinee: ValueRef) -> ValueRef {
320 let cmp = if nndiscr == 0 { IntEQ } else { IntNE };
321 let llptr = Load(bcx, GEPi(bcx, scrutinee, [0, ptrfield]));
322 let llptrty = type_of::type_of(bcx.ccx(), nonnull.fields[ptrfield]);
323 ICmp(bcx, cmp, llptr, C_null(llptrty))
326 /// Helper for cases where the discriminant is simply loaded.
327 fn load_discr(bcx: @mut Block, scrutinee: ValueRef, min: Disr, max: Disr)
329 let ptr = GEPi(bcx, scrutinee, [0, 0]);
331 // i.e., if the range is everything. The lo==hi case would be
332 // rejected by the LLVM verifier (it would mean either an
333 // empty set, which is impossible, or the entire range of the
334 // type, which is pointless).
337 // llvm::ConstantRange can deal with ranges that wrap around,
338 // so an overflow on (max + 1) is fine.
339 LoadRangeAssert(bcx, ptr, min as c_ulonglong,
340 (max + 1) as c_ulonglong,
346 * Yield information about how to dispatch a case of the
347 * discriminant-like value returned by `trans_switch`.
349 * This should ideally be less tightly tied to `_match`.
351 pub fn trans_case(bcx: @mut Block, r: &Repr, discr: Disr) -> _match::opt_result {
354 _match::single_result(rslt(bcx, C_disr(bcx.ccx(), discr)))
357 bcx.ccx().sess.bug("no cases for univariants or structs")
360 _match::single_result(rslt(bcx, C_disr(bcx.ccx(), discr)))
362 NullablePointer{ _ } => {
363 assert!(discr == 0 || discr == 1);
364 _match::single_result(rslt(bcx, C_i1(discr != 0)))
370 * Begin initializing a new value of the given case of the given
371 * representation. The fields, if any, should then be initialized via
374 pub fn trans_start_init(bcx: @mut Block, r: &Repr, val: ValueRef, discr: Disr) {
377 assert!(min <= discr && discr <= max);
378 Store(bcx, C_disr(bcx.ccx(), discr), GEPi(bcx, val, [0, 0]))
380 Univariant(ref st, true) => {
381 assert_eq!(discr, 0);
382 Store(bcx, C_bool(true),
383 GEPi(bcx, val, [0, st.fields.len() - 1]))
386 assert_eq!(discr, 0);
389 Store(bcx, C_disr(bcx.ccx(), discr), GEPi(bcx, val, [0, 0]))
391 NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, _ } => {
392 if discr != nndiscr {
393 let llptrptr = GEPi(bcx, val, [0, ptrfield]);
394 let llptrty = type_of::type_of(bcx.ccx(), nonnull.fields[ptrfield]);
395 Store(bcx, C_null(llptrty), llptrptr)
402 * The number of fields in a given case; for use when obtaining this
403 * information from the type or definition is less convenient.
405 pub fn num_args(r: &Repr, discr: Disr) -> uint {
408 Univariant(ref st, dtor) => {
409 assert_eq!(discr, 0);
410 st.fields.len() - (if dtor { 1 } else { 0 })
412 General(ref cases) => cases[discr].fields.len() - 1,
413 NullablePointer{ nonnull: ref nonnull, nndiscr, nullfields: ref nullfields, _ } => {
414 if discr == nndiscr { nonnull.fields.len() } else { nullfields.len() }
419 /// Access a field, at a point when the value's case is known.
420 pub fn trans_field_ptr(bcx: @mut Block, r: &Repr, val: ValueRef, discr: Disr,
421 ix: uint) -> ValueRef {
422 // Note: if this ever needs to generate conditionals (e.g., if we
423 // decide to do some kind of cdr-coding-like non-unique repr
424 // someday), it will need to return a possibly-new bcx as well.
427 bcx.ccx().sess.bug("element access in C-like enum")
429 Univariant(ref st, _dtor) => {
430 assert_eq!(discr, 0);
431 struct_field_ptr(bcx, st, val, ix, false)
433 General(ref cases) => {
434 struct_field_ptr(bcx, &cases[discr], val, ix + 1, true)
436 NullablePointer{ nonnull: ref nonnull, nullfields: ref nullfields, nndiscr, _ } => {
437 if (discr == nndiscr) {
438 struct_field_ptr(bcx, nonnull, val, ix, false)
440 // The unit-like case might have a nonzero number of unit-like fields.
441 // (e.g., Result or Either with () as one side.)
442 let ty = type_of::type_of(bcx.ccx(), nullfields[ix]);
443 assert_eq!(machine::llsize_of_alloc(bcx.ccx(), ty), 0);
444 // The contents of memory at this pointer can't matter, but use
445 // the value that's "reasonable" in case of pointer comparison.
446 PointerCast(bcx, val, ty.ptr_to())
452 fn struct_field_ptr(bcx: @mut Block, st: &Struct, val: ValueRef, ix: uint,
453 needs_cast: bool) -> ValueRef {
456 let val = if needs_cast {
457 let fields = do st.fields.map |&ty| {
458 type_of::type_of(ccx, ty)
460 let real_ty = Type::struct_(fields, st.packed);
461 PointerCast(bcx, val, real_ty.ptr_to())
466 GEPi(bcx, val, [0, ix])
469 /// Access the struct drop flag, if present.
470 pub fn trans_drop_flag_ptr(bcx: @mut Block, r: &Repr, val: ValueRef) -> ValueRef {
472 Univariant(ref st, true) => GEPi(bcx, val, [0, st.fields.len() - 1]),
473 _ => bcx.ccx().sess.bug("tried to get drop flag of non-droppable type")
478 * Construct a constant value, suitable for initializing a
479 * GlobalVariable, given a case and constant values for its fields.
480 * Note that this may have a different LLVM type (and different
481 * alignment!) from the representation's `type_of`, so it needs a
482 * pointer cast before use.
484 * The LLVM type system does not directly support unions, and only
485 * pointers can be bitcast, so a constant (and, by extension, the
486 * GlobalVariable initialized by it) will have a type that can vary
487 * depending on which case of an enum it is.
489 * To understand the alignment situation, consider `enum E { V64(u64),
490 * V32(u32, u32) }` on win32. The type has 8-byte alignment to
491 * accommodate the u64, but `V32(x, y)` would have LLVM type `{i32,
492 * i32, i32}`, which is 4-byte aligned.
494 * Currently the returned value has the same size as the type, but
495 * this could be changed in the future to avoid allocating unnecessary
496 * space after values of shorter-than-maximum cases.
498 pub fn trans_const(ccx: &mut CrateContext, r: &Repr, discr: Disr,
499 vals: &[ValueRef]) -> ValueRef {
502 assert_eq!(vals.len(), 0);
503 assert!(min <= discr && discr <= max);
506 Univariant(ref st, _dro) => {
507 assert_eq!(discr, 0);
508 let contents = build_const_struct(ccx, st, vals);
510 C_packed_struct(contents)
515 General(ref cases) => {
516 let case = &cases[discr];
517 let max_sz = cases.iter().map(|x| x.size).max().unwrap();
518 let discr_ty = C_disr(ccx, discr);
519 let contents = build_const_struct(ccx, case,
521 C_struct(contents + &[padding(max_sz - case.size)])
523 NullablePointer{ nonnull: ref nonnull, nndiscr, ptrfield, _ } => {
524 if discr == nndiscr {
525 C_struct(build_const_struct(ccx, nonnull, vals))
527 assert_eq!(vals.len(), 0);
528 let vals = do nonnull.fields.iter().enumerate().map |(i, &ty)| {
529 let llty = type_of::sizing_type_of(ccx, ty);
530 if i == ptrfield { C_null(llty) } else { C_undef(llty) }
531 }.collect::<~[ValueRef]>();
532 C_struct(build_const_struct(ccx, nonnull, vals))
539 * Building structs is a little complicated, because we might need to
540 * insert padding if a field's value is less aligned than its type.
542 * Continuing the example from `trans_const`, a value of type `(u32,
543 * E)` should have the `E` at offset 8, but if that field's
544 * initializer is 4-byte aligned then simply translating the tuple as
545 * a two-element struct will locate it at offset 4, and accesses to it
546 * will read the wrong memory.
548 fn build_const_struct(ccx: &mut CrateContext, st: &Struct, vals: &[ValueRef])
550 assert_eq!(vals.len(), st.fields.len());
553 let mut cfields = ~[];
554 for (i, &ty) in st.fields.iter().enumerate() {
555 let llty = type_of::sizing_type_of(ccx, ty);
556 let type_align = machine::llalign_of_min(ccx, llty)
558 let val_align = machine::llalign_of_min(ccx, val_ty(vals[i]))
560 let target_offset = roundup(offset, type_align);
561 offset = roundup(offset, val_align);
562 if (offset != target_offset) {
563 cfields.push(padding(target_offset - offset));
564 offset = target_offset;
566 let val = if is_undef(vals[i]) {
567 let wrapped = C_struct([vals[i]]);
568 assert!(!is_undef(wrapped));
574 offset += machine::llsize_of_alloc(ccx, llty) as u64
580 fn padding(size: u64) -> ValueRef {
581 C_undef(Type::array(&Type::i8(), size))
584 // XXX this utility routine should be somewhere more general
586 fn roundup(x: u64, a: u64) -> u64 { ((x + (a - 1)) / a) * a }
588 /// Get the discriminant of a constant value. (Not currently used.)
589 pub fn const_get_discrim(ccx: &mut CrateContext, r: &Repr, val: ValueRef)
592 CEnum(*) => const_to_uint(val) as Disr,
594 General(*) => const_to_uint(const_get_elt(ccx, val, [0])) as Disr,
595 NullablePointer{ nndiscr, ptrfield, _ } => {
596 if is_null(const_struct_field(ccx, val, ptrfield)) {
597 /* subtraction as uint is ok because nndiscr is either 0 or 1 */
598 (1 - nndiscr) as Disr
607 * Extract a field of a constant value, as appropriate for its
610 * (Not to be confused with `common::const_get_elt`, which operates on
611 * raw LLVM-level structs and arrays.)
613 pub fn const_get_field(ccx: &mut CrateContext, r: &Repr, val: ValueRef,
614 _discr: Disr, ix: uint) -> ValueRef {
616 CEnum(*) => ccx.sess.bug("element access in C-like enum const"),
617 Univariant(*) => const_struct_field(ccx, val, ix),
618 General(*) => const_struct_field(ccx, val, ix + 1),
619 NullablePointer{ _ } => const_struct_field(ccx, val, ix)
623 /// Extract field of struct-like const, skipping our alignment padding.
624 fn const_struct_field(ccx: &mut CrateContext, val: ValueRef, ix: uint)
626 // Get the ix-th non-undef element of the struct.
627 let mut real_ix = 0; // actual position in the struct
628 let mut ix = ix; // logical index relative to real_ix
632 field = const_get_elt(ccx, val, [real_ix]);
633 if !is_undef(field) {
636 real_ix = real_ix + 1;
642 real_ix = real_ix + 1;
646 /// Is it safe to bitcast a value to the one field of its one variant?
647 pub fn is_newtypeish(r: &Repr) -> bool {
649 Univariant(ref st, false) => st.fields.len() == 1,
654 fn C_disr(cx: &CrateContext, i: Disr) -> ValueRef {
655 return C_integral(cx.int_type, i, false);