3 ms·

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?

• tialaramex 2y ago
  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.
  • jpc0 2y ago
    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.
    • Measter 2y ago
      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.
    • tialaramex 2y ago
      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).