Skip to content

0000-discriminant-bits.md

Latest commit

 

History

History
120 lines (83 loc) · 3.78 KB

0000-discriminant-bits.md

File metadata and controls

120 lines (83 loc) · 3.78 KB

Summary

Add methods to std::mem::Discriminant which inform of the space necessary for a bitwise representation of an enum's discriminant and the bits itself in an opaque fashion.

Motivation

Rust encourages using enums to encode data with multiple variants. An example of this can be found in the game of life tutorial.

enum Cell {
    Dead  = 0,
    Alive = 1
}

Using these enums in collections is wasteful, as each instance reserves at least 1 byte of space. Similarly, std::mem::size_of<Discriminant<Cell>>() is at least 1 byte. For that reason, the Wasm book later goes on and replaces Vec<Cell> by fixedbitset, ending up with a much less intuitive implementation.

If it were possible to read the exact necessary size and the bit representation the descriminant, we could have a PackedBits<T> that uses exactly as much space as necessary.

This allows for an efficient representation of discriminant sets, which is both useful for simple enums, but also for crating an index of all discriminant values present in collection.

Guide-level explanation

Disciminant data

Discriminant::bit_size is a method to retrieve the minimal number in bits necessary to represent this discriminant.

const fn bit_size() -> usize;

This number is not subject to optimisation, so e.g. Option<&str> reports a bitsize of 1.

For example:

enum Cell {
    Dead = 0,
    Alive = 1,
}

enum RGB {
    Red,
    Green,
    Blue
}

Discriminant<Cell>::bit_size() == 1
Discriminant<Option<&str>>::bit_size() == 1
Discriminant<RGB>::bit_size() == 2

This information can be used to pack multiple discriminants easily for efficient storage and easy indexing.

Discriminant<T> gains the methods into_bits and from_bits:

fn into_bits(&self) -> u128

Returns a bit representation of the discriminant. This data can be used to construct an efficient storage or index.

fn from_bits(data: u128) -> Self

Creates a Discriminant from emitted bits usable for comparison.

Reference-level explanation

The feature may interact with non-exhaustive enums. In this case, still, the currently used discriminant size should be used.

Adding the proposed functions probably entails adding a new compiler intrinsic discriminant_size.

Empty enums are of size 0.

Drawbacks

The added methods increase API surface in stdlib.

Rationale and alternatives

  • Why is this design the best in the space of possible designs?
  • What other designs have been considered and what is the rationale for not choosing them?
  • What is the impact of not doing this?
  • from_data and into_data could instead be straight From/Into implementations
  • Alternatively, from/into_bits could return a Bits<T> type with a richer interface

Prior art

Unresolved questions

  • Naming of the functions could be improved.
  • A basic implementation of a bitfield should be created during the implementation phase

Future possibilities

The feature is self-contained and I don't see direct extensions.