src/doc/nomicon/exotic-sizes.md

   1 % Exotically Sized Types
   2
   3 Most of the time, we think in terms of types with a fixed, positive size. This
   4 is not always the case, however.
   5
   6
   7
   8
   9
  10 # Dynamically Sized Types (DSTs)
  11
  12 Rust in fact supports Dynamically Sized Types (DSTs): types without a statically
  13 known size or alignment. On the surface, this is a bit nonsensical: Rust *must*
  14 know the size and alignment of something in order to correctly work with it! In
  15 this regard, DSTs are not normal types. Due to their lack of a statically known
  16 size, these types can only exist behind some kind of pointer. Any pointer to a
  17 DST consequently becomes a *fat* pointer consisting of the pointer and the
  18 information that "completes" them (more on this below).
  19
  20 There are two major DSTs exposed by the language: trait objects, and slices.
  21
  22 A trait object represents some type that implements the traits it specifies.
  23 The exact original type is *erased* in favor of runtime reflection
  24 with a vtable containing all the information necessary to use the type.
  25 This is the information that completes a trait object: a pointer to its vtable.
  26
  27 A slice is simply a view into some contiguous storage -- typically an array or
  28 `Vec`. The information that completes a slice is just the number of elements
  29 it points to.
  30
  31 Structs can actually store a single DST directly as their last field, but this
  32 makes them a DST as well:
  33
  34 ```rust
  35 // Can't be stored on the stack directly
  36 struct Foo {
  37     info: u32,
  38     data: [u8],
  39 }
  40 ```
  41
  42 **NOTE: [As of Rust 1.0 struct DSTs are broken if the last field has
  43 a variable position based on its alignment][dst-issue].**
  44
  45
  46
  47
  48
  49 # Zero Sized Types (ZSTs)
  50
  51 Rust actually allows types to be specified that occupy no space:
  52
  53 ```rust
  54 struct Foo; // No fields = no size
  55
  56 // All fields have no size = no size
  57 struct Baz {
  58     foo: Foo,
  59     qux: (),      // empty tuple has no size
  60     baz: [u8; 0], // empty array has no size
  61 }
  62 ```
  63
  64 On their own, Zero Sized Types (ZSTs) are, for obvious reasons, pretty useless.
  65 However as with many curious layout choices in Rust, their potential is realized
  66 in a generic context: Rust largely understands that any operation that  produces
  67 or stores a ZST can be reduced to a no-op. First off, storing it  doesn't even
  68 make sense -- it doesn't occupy any space. Also there's only one  value of that
  69 type, so anything that loads it can just produce it from the  aether -- which is
  70 also a no-op since it doesn't occupy any space.
  71
  72 One of the most extreme example's of this is Sets and Maps. Given a
  73 `Map<Key, Value>`, it is common to implement a `Set<Key>` as just a thin wrapper
  74 around `Map<Key, UselessJunk>`. In many languages, this would necessitate
  75 allocating space for UselessJunk and doing work to store and load UselessJunk
  76 only to discard it. Proving this unnecessary would be a difficult analysis for
  77 the compiler.
  78
  79 However in Rust, we can just say that  `Set<Key> = Map<Key, ()>`. Now Rust
  80 statically knows that every load and store is useless, and no allocation has any
  81 size. The result is that the monomorphized code is basically a custom
  82 implementation of a HashSet with none of the overhead that HashMap would have to
  83 support values.
  84
  85 Safe code need not worry about ZSTs, but *unsafe* code must be careful about the
  86 consequence of types with no size. In particular, pointer offsets are no-ops,
  87 and standard allocators (including jemalloc, the one used by default in Rust)
  88 may return `nullptr` when a zero-sized allocation is requested, which is
  89 indistinguishable from out of memory.
  90
  91
  92
  93
  94
  95 # Empty Types
  96
  97 Rust also enables types to be declared that *cannot even be instantiated*. These
  98 types can only be talked about at the type level, and never at the value level.
  99 Empty types can be declared by specifying an enum with no variants:
 100
 101 ```rust
 102 enum Void {} // No variants = EMPTY
 103 ```
 104
 105 Empty types are even more marginal than ZSTs. The primary motivating example for
 106 Void types is type-level unreachability. For instance, suppose an API needs to
 107 return a Result in general, but a specific case actually is infallible. It's
 108 actually possible to communicate this at the type level by returning a
 109 `Result<T, Void>`. Consumers of the API can confidently unwrap such a Result
 110 knowing that it's *statically impossible* for this value to be an `Err`, as
 111 this would require providing a value of type `Void`.
 112
 113 In principle, Rust can do some interesting analyses and optimizations based
 114 on this fact. For instance, `Result<T, Void>` could be represented as just `T`,
 115 because the `Err` case doesn't actually exist. The following *could* also
 116 compile:
 117
 118 ```rust,ignore
 119 enum Void {}
 120
 121 let res: Result<u32, Void> = Ok(0);
 122
 123 // Err doesn't exist anymore, so Ok is actually irrefutable.
 124 let Ok(num) = res;
 125 ```
 126
 127 But neither of these tricks work today, so all Void types get you is
 128 the ability to be confident that certain situations are statically impossible.
 129
 130 One final subtle detail about empty types is that raw pointers to them are
 131 actually valid to construct, but dereferencing them is Undefined Behavior
 132 because that doesn't actually make sense. That is, you could model C's `void *`
 133 type with `*const Void`, but this doesn't necessarily gain anything over using
 134 e.g. `*const ()`, which *is* safe to randomly dereference.
 135
 136
 137 [dst-issue]: https://github.com/rust-lang/rust/issues/26403