It's not the Standard ML of New Jersey of course, like I was taught last century, but it looks like an ML to me. Rust has a sound type system, whereas a language like C++ inherits C's YOLO approach to typing.
In Rust Vec<Option<Infallible>> is just a counter. Really, that's not theory that'll just happen by default because of how type arithmetic works.
In C++ you can't even write down an equivalent type, let alone say how it would be represented, the type system blows up long before we get there.
I've looked for this optimisation, and while it makes sense to me (Infallible is unhabitable ==> s: Option<Infallible> can only exist if s = None ==> all values in vector must be of the same value None that is known ahead of time ==> store a counter of how many Nones are in the vector instead of each None as an entry into a traditional vec), I cannot find any trace of such optimisation, whether by reading into the bytes backing the vector (with rustc -O / -C opt-level=3 to ensure this opt is triggered), or by calling `mem::size_of::<Vec<Option<std::convert::Infallible>>>()`.
What's happening is that `Infallible` has no values, and cannot be instantiated. This results in `Option<Infallible>` only having one possible variant (None) which has no payload, and therefore being a zero-sized type.
Separately `Vec<T>`, if `T` is a zero-sized type, never allocates and has a capacity of usize::MAX. Then, when you push into the Vec, because the value you push is zero-sized, there's no allocation and no data to write anywhere. Therefore the only effect is to increment the length counter.
Infallible is a clunky name for the Never type in Rust, i.e. a type that has no values and cannot be instantiated. Thus, Option<Infallible> only has a single value, viz. None. Then Vec<Option<Infallible>> is isomorphic to Vec<()> which reduces to a length field - there's no other data associated with it.
Could you explain the semantics of Vec<Option<Infallible>>?
What would exist in the memory pointed to by the Vec?
What would be the use case for this type?
The Vec itself carries four items, a unique pointer to T, a capacity, an Allocator A, and a current length. It is a generic type, generic over the type T and the allocator A.
1) lets dispense with the Allocator, for a typical Vec the global Allocator is used, so this type has no size, every Vec is talking about the same global Allocator, its state is tracked internally to itself. We need not consider this object further†
2) now lets dispense with that unique pointer. Its semantics are crucial if T had non zero size because this is why Rust knows the associated memory which is pointed to is "owned" by the Vec. However, for a zero size T this pointer is entirely unused.
3) Capacity at last actually is used, it's a machine word sized integer, so on a modern computer that's 64-bits, 8 bytes to store the capacity of the Vec, which will be the maximum possible unsigned integer of that kind, usize::MAX. It is set to this value when the Vec is created (because the size of T was zero) and never changes.
4) Length is also used, despite not needing to store any data for T the Vec is finite and this tracks how many of the zero size item are in the Vec. Thus, it's a counter.
† In C++ they use the "Empty Base Optimisation" to avoid needing space for such things, in Rust their size is just Zero and so they won't be stored.
What is the use case? Vec<T> is a generic type (Rust's generic growable array of T) so although Vec<Option<Infallible>> seems somewhat useless as a concrete type, it is likely to sometimes occur in generic code.
Example: generic code to do a bunch of potentially fallible operations and remember whether and how they failed for later summarisation may make a type Vec<Option<E>> where E is the failure type. When the operation wasn't actually fallible E is Infallible and instead of an actual growable array type we're just making a trivial counter, our summary is going to inevitably say that all N operations were successful, any code for the "List of failures" summary should even get trimmed as dead code in this case since it depends on an Infallible object and the compiler knows Infallible cannot exist.
So from what I've played with Option<Infallible> in rust would be directly equivalent to std::nullopt_t and has similar semantics in vectors, ie it just increments length.
There seems to be slightly more compile time work done in Rust but using the use case you described the concept of a Vec<Option<Infallible>> can just as easily be represented as std::vector<std::nullopt_t> with very similar semantics although possibly slightly less optimisation, although I would think if it was actually used in the language extensively I would see library implementors makeing it entirely compile time just like in rust.
I don't disagree that algebraic data types are nice and that Rust has an interesting implementation of them, however this specific example doesn't seem unrepresentable in C++ using std::option and std::variant although the actual semantics relating to usage is easier in Rust.
Bear in mind that the optimization on `Option<Infallible>` isn't specific to that type; it applies to anything that results in one possible value. For example, `Foo` in this example is also zero-sized:
pub enum Foo {
Foo,
Bar(A),
Baz(B),
Qux(C),
}
pub enum A {}
pub enum B {}
pub enum C {}
The optimization applied to Vec also applies to any zero-sized type.
How do you get to the idea that std::vector<std::nullopt_t> "just increments length" ?
I spent some time trying this out in Godbolt†, and then by hand, and then reading the Microsoft STL, and exactly as I'd assumed before I read your comment it was a growable array of one byte objects, with the type std::nullopt_t, 400 objects? 400 bytes. 4 million objects? 4 million bytes.
† Including longer than I'd like to admit forgetting that C++ silently copies large objects without telling you and so my diagnostic was actually making a new std::vector because I forgot to write an ampersand to make it a reference...
It is still possible I missed something and so I invite you to tell me what that was. But overall my thought is that you've missed the whole point and are in the same place as when C++ programmers get confused and think Empty types (like Infallible) and Zero Size Types (like Option<Infallible>) are somehow the same, which is like confusing zero (The additive identity) with one (the multiplicative identity).
In Rust Vec<Option<Infallible>> is just a counter. Really, that's not theory that'll just happen by default because of how type arithmetic works.
In C++ you can't even write down an equivalent type, let alone say how it would be represented, the type system blows up long before we get there.