Skip to content

Latest commit

 

History

History
480 lines (398 loc) · 24.4 KB

3334-niche.md

File metadata and controls

480 lines (398 loc) · 24.4 KB
Raw

Summary

Provide a stable attribute to define "niche" values of a type. The type cannot store these values, allowing the compiler to use them to optimize the representation of containing types such as Option<Type>.

Motivation

Rust makes extensive use of types like Option, and many programs benefit from the efficient storage of such types. Many programs also interface with others via FFI, via interfaces that provide data and a sentinel value (such as for errors or missing data) within the same bits.

The Rust compiler already provides support for this via "niche" optimizations, and various types providing guarantees of such optimizations, including references, bool, char, and the NonZero family of types. However, Rust does not provide any stable means of defining new types with niches, reserving this mechanism for the standard library. This puts pressure on the standard library to provide additional families of types with niches, while preventing the broader crate ecosystem from experimenting with such types.

Past efforts to define a stable niche mechanism stalled out due to scope creep: alignment niches, null-page niches, multiple niches, structures with multiple fields, and many other valid but challenging ideas (documented in the "Future possibilities" section). This RFC defines a simple mechanism for defining one common type of niche, while leaving room for future extension.

Defining a niche mechanism allows libraries to build arbitrary types containing niches, and simplifies handling of space-efficient data structures in Rust without manual bit-twiddling.

Guide-level explanation

When defining a struct containing exactly one field, you can attach a niche attribute to the struct to declare a specific value or range of values for that field as invalid. This promises the compiler that you will never store those values in that field, which allows the compiler to use those in-memory representations for different purposes, such as the representation of None in a containing Option.

use std::mem::size_of;

#[niche(value = 42)]
struct MeaninglessNumber(u64);

assert_eq!(size_of::<MeaninglessNumber>(), 8);
assert_eq!(size_of::<Option<MeaninglessNumber>>(), 8);

#[niche(range = 2..)]
struct Bit(u8);

assert_eq!(size_of::<Bit>(), 1);
assert_eq!(size_of::<Option<Option<Option<Bit>>>>(), 1);

Constructing a struct with a niche value, or writing to the field of such a struct, or obtaining a mutable reference to such a field, requires unsafe code. Causing a type with a niche to contain one of its niche values (whether by construction, writing, or transmuting) results in undefined behavior.

The field type must be a built-in integer or floating-point type, a char, or a raw pointer.

The value given for value, or the endpoints of the range given for range, may be either a value of the same type as the field, or an unsigned integer.

Typically, a user-defined type with a niche may wish to provide safe methods to construct or modify the type. For instance, a type T might choose to provide one or more of the following, depending on what makes sense for the expected usage of the type:

  • a new or try_new method returning a Result<T, E> or Option<T>
  • an unsafe new_unchecked method returning T
  • TryFrom implementations for conversions that can fail
  • From implementations for conversions from types that fully map to the valid values, such that the conversion cannot fail
  • an implementation of Default
  • constant values of the type
  • methods that may fail to map to the valid range, and return Result<T, E> or Option<T>
  • operators that may fail by panicking
  • saturating, checked, or similar versions of operators that cannot fail
  • methods or operators that cannot fail

If a type T contains only a single niche value, Option<T> (and other enums isomorphic to it, with one variant containing T and one nullary variant) will use that value to represent None (the nullary variant). If such a T is additionally repr(transparent) or repr(C) or otherwise permitted in FFI, Option<T> will likewise be permitted in FFI, with the niche value mapping bidirectionally to None across the FFI boundary.

If a type contains multiple niche values, Rust does not guarantee any particular mapping at this time, but may in the future.

Structs with niches may be constructed or written to in const code, though such construction or writing still requires unsafe.

Reference-level explanation

If a struct contains a niche, the following operations may only occur in unsafe code, and produce an error if invoked in safe code:

  • Constructing the struct, which requires initializing the field.
  • Writing to the field.
  • Obtaining a mutable reference to the field.

Other operations, including reading from the field, obtaining a non-mutable reference to the field, obtaining a mutable reference to the whole struct, or assigning to the whole struct, are not affected by the presence of the niche.

Causing a type with a niche to contain one of its niche values (whether by construction, writing, or transmuting) results in undefined behavior.

The niche attribute may either contain value = N or range = R. The value given for N, or the endpoints of the range given for R, may be either a literal value of the same type as the field, or an unsigned integer literal.

Signed and unsigned integer literals may use any integer base representation (decimal, hex, binary, octal), but must not have a type suffix. The unsigned integers are interpreted as the bit patterns in memory corresponding to the representation of the field. For instance, a struct with a float field could specify one or more NaN values as a niche using the integer representation of those values.

The range may be exclusive (start..end), inclusive (start..=end), bounded below (start..), bounded above (..end), or bounded above inclusive (..=end).

Note that on a signed or floating-point field, a range bounded only above will include all values less than the upper bound, including any negative numbers less than the upper bound. For instance, a field of type i8 with a niche range of ..2 will have as niche values 1, 0, -1, -2, ..., -128.

The attribute #[niche] may only appear on a struct declaration. The struct must contain exactly one field.

The field must have one of a restricted set of types:

  • A built-in unsigned integer type (uN). In this case, the niche specification must use an unsigned integer.
  • A built-in signed integer type (iN). In this case, the niche specification may use a signed integer, or an unsigned integer corresponding to the two's complement representation. For instance, a field of type i32 could have a niche of -1 or equivalently 0x8000_0000.
  • A built-in floating-point type (fN). In this case, the niche specification may use a floating-point number, or an unsigned integer corresponding to the IEEE representation of that floating-point type.
  • A char. In this case, the niche specification may use a char literal, or an unsigned integer. The niche gets merged with the built-in niches of char; if the result after merging would have multiple discontiguous niches, the compiler need not take all of them into account.
  • A raw pointer. In this case, the niche specification must use an unsigned integer. This allows user-defined types to store a properly typed pointer while using known-invalid pointer values as niches.

Declaring a niche on a struct whose field type does not meet these restrictions results in an error.

Declaring a niche on any item other than a struct declaration results in an error.

Declaring a niche on a struct containing more or less than one field results in an error.

Declaring multiple niche attributes on a single item, or multiple key-value pairs within a single niche attribute, results in an error.

The niche attribute may appear inside cfg_attr. The net effect after evaluating all configuration must be to apply at most one niche attribute to the type.

Declaring a niche on a struct that has any generic parameters results in an error.

Declaring a range niche with an empty range (e.g. 0..0) results in a warn-by-default lint. As with many lints, this lint should be automatically suppressed for code expanded from a macro.

Declaring a range niche with an invalid range (e.g. 5..0) results in an error.

Declaring a range niche with an unbounded range (..) results in an error, as this would represent a field with no valid values.

Declaring a niche using a non-literal value (e.g. usize::MAX) results in an error. Constants can use compile-time evaluation, and compile-time evaluation does not occur early enough for attributes such as niche declarations.

If a type T contains multiple niche values (e.g. #[niche(range = 8..16)]), the compiler does not guarantee any particular usage of those niche values in the representation of types containing T. In particular, the compiler does not commit to making use of all the niche values, even if it otherwise could have.

However, multiple instances of the same identical type (e.g. Option<T> and Option<T>) will use an identical representation (whether the type contains a niche or not). This permits a round-trip between such a value and a byte representation.

Adding a niche to a type does not change the storage size, alignment, or other ABI details of the type, even if the niche might otherwise allow storing fewer bytes; it only changes the ABI of other types containing the type (e.g. Option<T>). The type still allows obtaining mutable references to the field, which requires storing valid values using the same representation as those values would have had without the niche.

Declaring a niche may allow additional optimizations that assume the type cannot contain the niche values, though the compiler does not guarantee this. For instance, the compiler may be able to elide bounds checks that the valid values always satisfy.

Niches do not affect pattern-matching exhaustiveness. For the purposes of pattern matching, the compiler will check exhaustiveness as if the field could take on any value.

If a struct has both a niche and derive(Default) declared on it, the compiler will check if the default value falls within the niche, and produce an error if so.

If a struct has both a niche and repr(packed), the compiler will produce an error.

Rationale and alternatives

We could allow defining either valid or invalid ranges. For instance, niche(invalid_range(0..=3)) or niche(valid_range(4..)). Different types could use whichever of the two proved simpler for a given use case. However, in addition to adding gratuitous complexity and requiring longer names (invalid_range vs range), this would double the number of cases when defining other kinds of niches in the future. For instance, a future syntax for bit-pattern niches would need to provide both valid and invalid variants as well. We could introduce another level of nesting to make this orthogonal, such as niche(invalid(range(...))) and niche(invalid(range(...))), but that further increases complexity.

Rather than defining the range of invalid values, the attribute could define the range of valid values. Different types may find one or the other case simpler. This RFC chooses to define the range of invalid values for three reasons:

  • As an arbitrary choice, because we need to pick one or the other (see above).
  • The most common case will be a single invalid value, for which defining invalid values results in simpler code.
  • This mechanism commonly goes by the name niche, and niche also refers to the invalid value. So, an attribute defining the niche of a type most naturally refers to the invalid value.

Note that the compiler already supports having a niche in the middle of a type's possible values; internally, the compiler represents this by defining a valid range that wraps around the type's possible values. For instance, #[niche(value = 42)] gets represented internally in the compiler as a valid range starting at 43 and ending at 41.

We could define only single-value niches, not ranges. However, the compiler already supports ranges internally, and the standard library already makes use of multi-value ranges, so this seems like an artificial limitation.

We could define only ranges, not single-value niches, and users could express single-value niches via ranges, such as 0..=0. However, that makes single-value niches more verbose to define, and makes mistakes such as 0..0 more likely. (This RFC suggests a lint to catch such cases, but the syntax should still attempt to guide users away from that mistake.)

We could guarantee more usage of niches than just a single value; however, this would constrain the compiler in areas that still see active development.

We could avoid guaranteeing the use of a single-value niche for Option; however, this would eliminate one of the primary user goals for such niches.

We could require types to opt into the guaranteed use of a niche, separately from declaring a niche. This seems unnecessarily verbose, as well as limiting: we can't yet provide a full guarantee of all future uses we may want to guarantee, only of the limited single-value uses.

We could implement niches using a lang-item type that uses const generics (e.g. Niche<T, const RANGE: std::ops::Range<T>>. This type would be useful regardless, and we should likely provide it if we can. However, this RFC advocates (eventually) building such a type on an underlying language-level building block like niche, and providing the underlying building blocks to the ecosystem as well.

We could implement niches using a trait Niche implemented for a type, with associated consts for niche values. If we chose to do this in the future, the #[niche(...)] attribute could become forward-compatible with this, by generating the trait impl.

We could use a syntax based on patterns, such as struct S(u8 is 0..=32); or struct S(MyEnum is MyEnum::A | MyEnum::B). The niche attribute could be forward-compatible with this, by generating the appropriate patterns.

We could attach the #[niche(...)] attribute to the field rather than to the struct. This would have the advantage of extending naturally to multiple fields, and would associate the value restrictions specifically to the field they apply to. This would also be more convenient for application to enum fields. However, this would be less convenient for defining single-field tuple structs:

// Proposed syntax
#[niche(value = 0)]
struct NonZeroU32(u32);

// Alternative syntax
struct NonZeroU32(
    #[niche(value = 0)]
    u32,
);

In addition, that alternative syntax would not work for future multi-field niches that need to correlate across fields (e.g. a niche for one field that depends on the value of another field). It also would not work as well for niches on a union.

Since the syntax proposed in this RFC requires exactly one field in the struct, this does not prevent future syntax additions from adding a niche attribute on fields, in which case the two could be declared as equivalent on a single-field struct.

We could support bool, just as easily as char. However, since bool has only two valid values, any niche applying a further restriction to it would result in either a one-value type or a zero-value type, neither of which seems useful enough to support.

Rather than supporting derive(Default), we could reject it, and wait for general-purpose compiler support for safe assignment of compile-time constant expressions.

We could entirely forbid taking mutable references to fields of structs with niches, rather than allowing them in unsafe code. This would mean that unsafe code could not produce such a reference and call other code with it. However, that would also prevent calling mutating methods and otherwise reusing existing code that makes use of &mut. Other unsafe code already incurs similar obligations. We could also have lints detecting at least trivial misuses, such as returning such a &mut reference from a safe method.

Prior art

The Rust compiler has supported niches for types like Option in various forms since versions prior to Rust 1.0. In particular, Rust 1.0 already guaranteed that Option<&T> has the same size as &T. Rust has had many additional niche-related optimizations since then.

The Rust compiler already supports user-defined niches via the unstable attributes rustc_layout_scalar_valid_range_start and rustc_layout_scalar_valid_range_end.

C, C++, and various other languages have "bitfields", which allow restricting the range and storage of a type based on the number of bits used to store it. This doesn't allow excluding a more fine-grained range, though.

Ada supports declaring integer types with explicit ranges.

Bit-twiddling tricks to store information compactly have seen widespread use and innovation since computing antiquity.

Unresolved questions

Could we support niches on generic types? For instance, could we support declaring a niche of 0 on a generic struct with a single field?

Are there any attributes we need to make mutually exclusive with niche?

Can we make derive(Default) detect errors? The compiler already has support for detecting whether a type permits zero-initialization (used to produce a warning for mem::zeroed()); hopefully we can make use of the same support.

Future possibilities

Niches offer possibilities as vast, rich, clever, and depraved as the collective ingenuity of bit-twiddlers everywhere. This section includes many possibilities that have come up in the past. This RFC deliberately excludes all of these possibilities from the scope of the initial version, choosing to specify only behavior that the Rust compiler already implements.

New types of niches can use the same niche attribute, adding new key-values within the attribute.

  • Limited constant evaluation: This RFC excludes the possibility of using constants in the range expression, because doing so simplifies the implementation. Ideally, a future version would allow ranges to use at least simple numeric constants, such as usize::MAX. Full constant evaluation may be much harder to support.
  • Alignment niches: If a pointer requires a certain alignment, any bit pattern corresponding to an unaligned pointer could serve as a niche. This provides an automatic mechanism for handling "tagged pointers" using the low bits.
  • Null-page niches: If a target treats the entire null page as invalid, pointers on that target could have a niche corresponding to that entire page, rather than just the null value. This would allow defining niches spanning a large swath of the value space. However, this would either require extensive use of cfg_attr for various targets, or a new mechanism for obtaining the valid range from the compiler. In addition, for some targets the valid range may vary based on environment, even for the same target; in such cases, the compiler would need to provide a mechanism for the user to supply the valid range to the compiler.
  • Invalid-pointer niches: On targets where certain pointer values cannot represent a valid pointer in a given context (such as on x86-64 where the upper half of the address space represents kernel-space address and the lower half represents userspace addresses), types containing such pointers could use a large swathe of values as a niche.
  • Pointer high-bit niches: On targets that don't permit addresses with some of the high bits set (such as implicitly on historical x86 or ARM platforms, or explicitly defined via ARM's "top-byte ignore" or AMD's "upper address ignore" or Intel's "Linear Address Masking"), types containing pointers could potentially use values with those high bits set as a niche. This would likely require compile-time configuration.
  • Multiple niches: A type could define multiple niches, rather than just a single range.
  • Other bit-pattern niches: A type could define niches via a bit pattern, rather than a range.
  • Per-field niches: A struct containing multiple fields could have a niche on a specific field, rather than the whole struct.
  • structs with ZST fields: A struct could contain fields with zero-sized types (e.g. PhantomData) and still have a niche.
  • Fields of reference type: In addition to allowing raw pointers, structs with niches could allow references. In practice, if the references have a lifetime other than 'static, this will also require at least some support for generic parameters.
  • Non-primitive fields: A struct could contain fields of non-primitive types, such as enums, tuples, arrays, or other structs (including structs with niches themselves).
  • Whole-struct niches: A struct containing multiple non-zero-sized fields could have niche values for the whole struct.
  • Union niches: A union could have a niche.
  • Enum niches: An enum or an enum variant could have a niche.
  • Specified mappings into niches: Users may want to rely on mappings of multiple values into a multi-value niche. For instance, users could define a type with a niche containing a range of integer values, and a range of integer error codes, and rely on Result<T, E> assigning specific niche values to specific error codes, in order to match a specific ABI (such as the Linux kernel's ERR_PTR).
  • Safety: The attribute specified in this RFC requires an unsafe block to set the field. Future extensions could allow safely setting the field, after verifying in a compiler-visible manner that the value does not fall within the niche. For instance, via derive(TryFrom) (see below), or by checking the value of a compile-time constant expression to ensure that it does not fall within the niche.
  • derive(TryFrom): Rust could support deriving TryFrom from the contained type to the struct. The implementation could explicitly check the range, and return an error if not in-range. This would avoid the need to write explicit unsafe code, and many uses may be able to elide or coalesce the check if the compiler can prove the range of a value at compile time. This would also avoid needing to duplicate the range in multiple places.
  • Lints: Multiple lints may help users define niches, or detect usages of niches that may be better expressed via other means. For instance, a lint could detect a newtype whose constructor maintains a range invariant, and suggest adding a niche.
  • Niches affecting pattern-matching exhaustiveness: In the future, Rust could support having niches affect pattern-matching exhaustiveness. If so, that future version of Rust would need to do so in a backwards-compatible manner, such as by ensuring that the resulting redundant match arms produce at most a suppressible warning lint (at least until an edition boundary).
  • Range types: Rust (or libraries built atop Rust) could provide integer types with associated valid ranges, along with operations that expand/contract/propagate those ranges as appropriate.
  • unsafe fields: If in the future Rust introduces unsafe fields, declaring a niche could internally mark the field as unsafe, taking advantage of the same machinery.
  • read-only fields: If in the future Rust introduces read-only fields, types with a niche may wish to provide read-only access to the value they contain, rather than just providing conversion methods or traits.
  • Move types, or types that don't support references: Rust currently requires that all values of a given type have the same representation no matter where they get stored, to allow taking references to such types and passing them to contexts that don't know about any relevant storage quirks such as niches. Given a mechanism for disallowing references to a type and requiring users to copy or move it rather than referencing it in-place, Rust could more aggressively optimize storage layout, such as by renumbering enum values and translating them back when read, or by storing fields using fewer bytes if their valid range requires fewer bytes to fully represent.