The term "niche" when referring to disallowed bit patterns and reusing them in option-like enums

[Tom-Phinney]

… and also why it does not increase the object size over that of the base &T.

[Ixrec]

IMO "niche" is actually a very good term for this, maybe even the best term available.

I strongly disagree with using anything like "invalid value", because AFAICT that's just a completely different concept. One billion is an invalid value for an i32, but it's not a niche. Color::Blue is an invalid value for i32, though it might have the same byte-pattern, but it's not a niche regardless.

IIUC, niches exist simply because all the memory in all the hardware we care about is made up of bytes/u8s, a u8 has 256 valid values, and the number of valid values for most types is not a multiple of 256 (and unsafe code is allowed to know these things). So whenever we're trying to put a T value in memory, most of the time we simply have to "round up" to however many bytes we need, and accept that either some of the possible values of those bytes do not correspond to any possible T value, or several different byte values will correspond to the same T value. And unless we're doing floating point, we typically prefer to leave values unmapped rather than "multimapped", and those unmapped values are niches (we could try to define "niche" in a way that also covers the redundant parts of multimapped values, so that things like NaN payload trickery becomes just another kind of niche optimization, but I'd rather call that something else and I doubt anyone's worried about that anyway).

Then we bring in the analogy of memory to physical space, and say the unmapped values are like unoccupied space. This is clearest when one or more bits of the byte are completely unused, but gets a little weird for the vast majority of cases where the unmapped value does not correspond to a memory location like a bit or byte does, but just one or more possible configurations of that memory. And that is why I think "niche" is one of the best possible words: it already has established usages for gaps in a metaphorical or logical "space", like "ecological niche", while synonyms like nook, alcove, indentation, recess, etc are much more concrete and physical. "Gap" comes close, but it's such a vague amorphous term that you probably wouldn't even realize it was being used as technical jargon with a precise meaning.

@mcy

I'm a bit late to this party, but it's not clear to my why "niche" is a big deal? It provides good motivation for why we care about such representations (i.e., we want to stick data into an unused bit) and is, ultimately, specialized vocabulary that only the small minority that writes unsafe code will ultimately care about.

It's vocabulary, similar to the sense that "definition" and "declaration" are frequently used interchangeably, but are distinct terms in C++ standardsese. Of all the Rust vocabulary out there, I argue that this is a case where it does not matter.

Ironically, I think the precedent of C++ here makes me inclined to think it does matter, a lot. Many details of C++ come off as far more arcane than they actually are because of poor terminology. "declaration" and "definition" are perfectly fine terms imo; I'm thinking of things like "lvalue" vs "rvalue" (recently expanded to include "prvalue", "plvalue" and "xvalue").

Or at least, it matters enough to justify one thread asking if anyone can think of better terms or reasons the current term might cause confusion. Presumably everyone agrees that we don't need to RFC this (although it might show up in future RFCs about layout guarantees and such).

[mcy]

@jethrogb

Not necessarily, you'd also want to use this to explain to beginner-to-intermediate users why e.g. Option<&T> is a zero-cost abstraction.

I'm not sure we should be teaching people that Option<&T> has a layout optimization until we're introducing something advanced concepts like FFI (where it actually matters!).

Option<T>, in contrast to Option<T&>, costs as much as your type's alignment, which is a source of confusion. The whole nonesense with alignment, padding, and niches is very much an advanced topic that most users should not be worried about.

@Ixrec

I'm thinking of things like "lvalue" vs "rvalue" (recently expanded to include "prvalue", "plvalue" and "xvalue").

I may have intentionally not used those as an example. Also, how could you forget "glvalue"?! =P

I think most of C++'s standardsese is pretty readable, outside of value category names (they're so bad omg) and some of the spooker corners like ODR, ADL, and std::launder() (S21.6.4 of C++17, for the curious). If it's a common English word with a nice mental picture you can attach to it, I think you've done well enough.

[steven099]

@Ixrec

IMO "niche" is actually a very good term for this, maybe even the best term available.

Edit: Basically just rewriting the comment...

The word itself seems fine, but how it's being used makes it a bit confusing. It seems like the niche of a type would refer to the area of the available bit space which it occupies, rather than the area it leaves vacant. I think it would be clearer to talk about the niches left by a type, rather than the niches of a type.

[Tom-Phinney]

That interpretation is compatible with how many of us think of the situation: that a niche left in the encoding of one type provides code-points for encoding related-but-distinct information.

[repax]

I'd just think of "niche" as a "special subset", just like a niche market is a subset of the market, so:

Zero is a niche not used by &T.
Zero is a niche of Option<&T>.

[Ixrec]

My understanding was that it's simply incorrect to say that Option<&T> has/leaves any niches, whether or not we end up calling this concept a "niche". The layout of Option<&T> does exploit the fact that &T has/leaves a niche, but that's different from Option<&T> itself having/leaving a niche.

I get the prima facie appeal of saying things like "Option<&T> uses its niche for layout optimizations", but because "niche" basically means "unused value" that's actually a contradiction in terms: "Option<&T> uses its unused value" clearly isn't right.

[RalfJung]

@Tom-Phinney

With analogy to IEEE Floating Point, I classify all such representation values as "NotAValue" ( NaV ). For NonZeroU8 the b8 representation 0b00000000 is NaV . For bool all b8 representation values except 0b00000000 and 0b00000001 are NaV . In my view, a representation value that is NaV implies instant UB.

So you are basically saying the representation domain of bool is {true, false, NaV}. I don't think I like this. And the mess that is NaN in floating point doesn't indicate that this is a good idea.

It is much easier to just make this a partial function/relation. Then the domain of bool can truly be the canonical Boolean algebra (or rather it's carrier set), and "typed copies" naturally enforce the validity invariant. To achieve the same you need to first add a dummy value (NaV) to every domain and then special-case that dummy value in the semantics---those are entirely unnecessary contortions.

@Ixrec

I strongly disagree with using anything like "invalid value", because AFAICT that's just a completely different concept. One billion is an invalid value for an i32 , but it's not a niche. Color::Blue is an invalid value for i32 , though it might have the same byte-pattern, but it's not a niche regardless.

Right, that's what I meant above when I said that "value" is a concept on the "abstract" side whereas "niche" is on the "concrete"/"representation" side of things.

@Ixrec

IIUC, niches exist simply because all the memory in all the hardware we care about is made up of bytes/ u8 s, a u8 has 256 valid values, and the number of valid values for most types is not a multiple of 256 (and unsafe code is allowed to know these things).

Except we don't specify Rust in terms of hardware, we specify it in terms of an Abstract Machine, so bytes get more complicated. But that is a separate concern.

@Ixrec

My understanding was that it's simply incorrect to say that Option<&T> has/leaves any niches, whether or not we end up calling this concept a "niche". The layout of Option<&T> does exploit the fact that &T has/leaves a niche, but that's different from Option<&T> itself having/leaving a niche.

[repax]

@Ixrec

because "niche" basically means "unused value"

I don't think it would be correct to say that. Rather, "niche" means "subset". And, if a bit pattern is valid for some type then it is also a value.

Edit: To say something is a value, "unused" or not, is to say that it is a valid bit pattern for its type.

[Tom-Phinney]

@RalfJung

So you are basically saying the representation domain of bool is {true, false, NaV} . I don't think I like this. And the mess that is NaN in floating point doesn't indicate that this is a good idea.

It is much easier to just make this a partial function/relation. Then the domain of bool can truly be the canonical Boolean algebra (or rather it's carrier set), and "typed copies" naturally enforce the validity invariant. To achieve the same you need to first add a dummy value ( NaV ) to every domain and then special-case that dummy value in the semantics---those are entirely unnecessary contortions.

The issue I see in this and many other posts within this thread is that we oscillate between

1. a view that is so abstract that it ignores the underlying hardware to which it must map (e.g., a byte that represents a bool has only two values), and
2. a view that attempts to be an abstraction of the underlying hardware (e.g., a byte has 256 values, of which only two are used).

In View #2 niches occur at the level of the abstract machine; in View #1 they do not, so must somehow be described and accounted for by another means. The area of philosophical disagreement here is about how (and at what level) to account for those niches, independent of whether the niches are exploited by an extension of the base type or are simply unused/invalid/instant-UB when they occur.

I, and apparently many others, are attempting to account for those niches via a single-level description (View #2), whereas you seem to be espousing View #1. Both seem to be reasonable approaches, but only View #2 accounts for the niches within the abstract machine itself; View #1 seems to require an additional descriptive layer and mechanism. How do you propose to account (in a formal descriptive sense) for the unused niches in the mapping from b8 to bool, or from b8 to NonZeroU8? How would you formally describe the use of the latter niche to encode the value None in Option<NonZeroU8>?

[Tom-Phinney]

Incidentally, my use of NaV was simply an attempt to put a name to the wildcard alternative (_) that arises implicitly when a mapping from a bN representation to a T value is only a partial mapping.

[RalfJung]

I and many others share the view that in Rust's Abstract Machine, memory is untyped, only operations are typed. If we start with that postulate, there is no such thing as storing a "bool" in memory, only bytes can be stored there -- or maybe let's call them "abytes", abstract bytes, because they are more like Option<u8> to account for uninitialized memory (and then they really are even more complicated because of pointers).

Surely a typed memory (that you seem to propose) is possible. But I think it is much easier to define and reason about an untyped memory, because this minimizes the amount of "extra state" that the Abstract Machine has to carry (like type information). A typed memory also gets really tricky when you want to explain transmutes, or using raw pointers to read data from memory at the "wrong" type (which is totally allowed in Rust, we don't have strict aliasing rules like C does). As a data point, CompCert started with a kind-of typed memory but later switched to untyped memory and everything got simpler.

I have a detailed (semi-)formal proposal for all of this over in the UCG repo. This explains how you can, based on an untyped memory, define loading/storing typed data for memories. This proposal explains niches (in the sense that it explains where the UB is coming from when creating a "bad" boolean), it explains padding (in the sense that it explains why padding bytes can change when a struct is copied), it explains transmutes and type punning (both through raw pointers and unions).
I think getting the typed approach to the same level of detail will take quite a bit of work. Once someone did that work, I'd be happy to talk more specifically about comparing the two -- but right now it's hard to compare because one version hasn't really been written down.

EDIT: reading your post again, I am not even sure any more if you suggested a typed memory. I honestly don't understand what the difference is between what you call "view #1" and "view #2" -- both abstract memory, I do it with a (functional) relation, you do it with a function. So what? Oh, your model also doesn't account for uninitialized memory if you assume a byte only has 256 values, maybe that's what you mean? But that is orthogonal to the niche discussion, it's just yet another thing that the Abstract Machine has to take care of.

@Tom-Phinney

only View #2 accounts for the niches within the abstract machine itself

That's incorrect, my definition of the Abstract Machine does account for niches as part of the value representation relation. The representation relations are an important part of the Abstract Machine specification.

@Tom-Phinney

a view that is so abstract that it ignores the underlying hardware to which it must map (e.g., a byte that represents a bool has only two values), and

No idea why you are claiming that my view "ignores the underlying hardware". Unless you mean that it is weird that, observably, memory in Rust is not "real memory" -- but that is an observable fact that any proposed Abstract Machine will have to explain.

@Tom-Phinney

View #1 seems to require an additional descriptive layer and mechanism

You need some mechanism to talk about values and their representations. That's unavoidable in a language like Rust where the programmer can and is allowed to observe the representation of object. In my proposal, that same mechanism takes care of niches. Your proposal needs a dedicated solution for niches ("not-a-value").

So, contrary to what you said, view #1 requires no extra handling for niches, it just falls out of mechanisms we need anyway; view #2 needs special handling.

@Tom-Phinney

How do you propose to account (in a formal descriptive sense) for the unused niches in the mapping from b8 to bool , or from b8 to NonZeroU8 ?

I have linked to https://github.com/rust-lang/unsafe-code-guidelines/pull/175 several times in this thread now, have you read it? It actually (semi-)formally defines bool and NonZeroU8. You will notice that there's no "NaT" anywhere.

@Tom-Phinney

How would you formally describe the use of the latter niche to encode the value None in Option<NonZeroU8> ?

The value relation for Option<NonZeroU8> looks as follows:

• A value Variant { idx: 1, data: Int(i) } (this is the meta-level way to say Some(i)) where i in 1..256 is related to byte list [b] if b.as_int() == Some(i). (This accounts for pointer provenance; if you prefer to gloss over that, we can just say it is related to byte list [i].)
• Moreover, a value Variant { idx: 0, data: Tuple([]) } (the meta-level way to say None) is related to [b] if b.as_int() == Some(0). (This accounts for pointer provenance; if you prefer to gloss over that, we can just say it is related to byte list [0].)

How would it look like as a representation function? I think almost the same, except that we'd have to start with the byte list and then figure out the abstract value from there. For a type as simple as this, that's still fairly straight-forward.

But how would it look like, in your proposal with typed memory, to write an Option<NonZeroU8> somewhere, and then later use a *const u8 to read it? If memory remembers the "abstract value", you now have to do something.

@Tom-Phinney

Incidentally, my use of NaV was simply an attempt to put a name to the wildcard alternative ( _ ) that arises implicitly when a mapping from a bN representation to a T value is only a partial mapping.

Oh. That seems like an odd choice; instead of just saying "the mapping is partial" (so it's domain effectively is Option<Value>, where this is the meta-level Option), you require it to be total and then require every single type to complete the function by doing an Option-like construction? Looks like an overcomplication to me. But well. As I have already stated above, partial representation functions and representation relations are basically the same thing except that the former bake in the extra assumption that a given byte list can never represent more than one value. I hope that's true but union leaves me unsure.

[steven099]

@Ixrec

...but because "niche" basically means "unused value"...

This is the issue I was having with the use of "niche". It's like you've taken the concept of "unfilled niche", isolated the aspect of that concept contributed by "unfilled", but then referred to that as "niche". If the term "niche" is going to work, the "unfilled" part needs to be supplied by context, and then of course, the question is "unfilled by who"? The representation of &T leaves a niche which is filled by the None variant in the representation of Option<&T>.

As an aside, referring to the 254 byte values left unused by the representation of bool as "niches" feels a little odd. At that point, it seems more like bool is filling niches in the representation of discriminants.

Of course, I understand that the use of the term is niche anyways.

[Tom-Phinney]

@RalfJung My background includes working on ISAs (Instruction Set Architectures) with tagged/typed memory, including capability-based systems. It's one of those computing approaches (like VLIW, e.g., IA-64) that do not scale well and thus need not be revisited. Thus I was not proposing any kind of tagged memory (unlike Stacked Borrows).

Also, consideration of undefined (0xUUUUUUUU) bytes was an intentional omission, as that seemed to be an unnecessary complication/digression to the discussion of niches.

Most importantly, I had not seen your recent changes to the UCG Glossary and its latest definition of niche. I agree with that definition; if I had known of it I would simply have posted a reference to it rather than all the writing that I've done so far in this thread.

So let's just end this philosophical journey with a reference to the current UCG documents.

[samsieber]

I'd like to weigh in as an English speaker without enough technical background to follow the discussion that's been going on.

Niche totally makes sense to me. Both the phrases "niche left by" and "niche of" connoting left over space you can put small things (e.g. marking the enum variant.) Just my two cents.

[RalfJung]

@Tom-Phinney

unlike Stacked Borrows

Well played. I don't think what Stacked Borrows achieves can be achieved without some kind of tagging, though. (And even C and C++ do have pointer provenance as a form of tagging.)

[gnzlbg]

After using the term "niche" for a while, I think it is a fine term and have not encountered any issues with it.

The alternative of using valid/invalid instead has one issue that I haven't seen discussed here yet (if somebody already mentioned it, I apologize, but I couldn't find it): currently we use the term "niche" to denote only those invalid representations that can be used for layout optimizations.

For example, with today's terminology, according to the validity invariant of &T both 0x00 and 0xUU are invalid, but only 0x00 is a niche since we can't exploit 0xUU for layout optimizations. The current terminology makes this difference clear.

A proposal to replace "niche" with "invalid" should also propose a way to continue to differentiate 0x00 from 0xUU for &T - none of which are valid according to the validity invariant, but one of them allows layout optimizations while the other does not.

[Florob]

FWIW, unless I'm missing a crucial difference here the C standard refers to the representations in a type's niche as "trap representations".

Certain object representations need not represent a value of the object type. [...] Such a representation is called a trap representation.

I have also been using this term when talking about Rust and was a bit surprised when I first saw "niche" emerging. While I'm fine with the term "niche", I'm actually also quite fond of "trap representation". It conveys that one is talking about representation not value, and the fact that being able to produce a representation in memory, but not being able to use it via a certain type, is sort of a "trap".

I suppose the main difference is that the definition of trap representation could be seen to encompass uninitialized bits. My own mental model is that uninitialized bits don't constitute a representation at all I.e. accessing them is invalid in its own right, not because it's an invalid representation. However, I realize that is not necessarily a nice/useful way to define a formal model.

[RalfJung]

"trap representation" IMO sounds way too much like a "real hardware" concept than a Rust Abstract Machine concept. The "trap" refers to a CPU trap. That grossly understates the danger of the Undefined Behavior that is actually at play here.

@Florob

My own mental model is that uninitialized bits don't constitute a representation at all I.e. accessing them is invalid in its own right, not because it's an invalid representation.

Accessing uninitialized bits at type MaybeUninit<usize> is perfectly fine though. And even in C, when you have a struct with padding, accessing that entire struct (e.g. passing it to a function) is fine even if the padding is uninitialized. So I think you cannot really consider this separate from the representation of a type, formal model or not.