10 ms·

Removing a layer of indirection when you had a reference type anyway is an optimization that runs into the issue that you describe. The obvious solution is to

Removing a layer of indirection when you had a reference type anyway is an optimization that runs into the issue that you describe. The obvious solution is to not apply it when null is already a valid inhabitant of that reference type. Without collapsing that indirection, Option<Option<T>> is perfectly expressible: Just (Just foo): <ptr> -> <ptr> -> foo Just Nothing: <ptr> -> <0> Nothing: <0> It's true that some languages expose "nullable references" as a distinct type and not a detail of representation, and it's true (... and sometimes obnoxious) that this doesn't layer as nicely (in particular, it's not a functor).

jblandy 11y ago
It may be worth pointing out that the `Option<T>` type in Rust doesn't inherently involve any pointers at all, assuming `T` is not a pointer type itself. For example, `Option<i32>` is probably (the compiler gets to choose) going to be represented as two four-byte values: the discriminant, which distinguishes the `Some` and `None` cases, and then a space for the value `v`, for when the discriminant says we have `Some(v)`. Since zero is a perfectly fine value for an `i32`, we have to store the discriminant separately. But note that this is just a flat eight-byte value. There's no heap allocation involved. It's just as if you'd written in C: struct O { enum { Some, None } discriminant; int32_t value }; I compiled a program that uses `Option<Option<i32>>`, and looked at the DWARF debugging info to see what the compiler did with it. It seems to represent this as a twelve-byte value: four bytes for the discriminant for the outer `Option`, followed an eight-byte `Option<i32>` value laid out as before. Since you can get the address of a value held by an enum, I guess this makes sense; the compiler can't combine the discriminants or do anything clever like that.
- SamReidHughes 11y ago
  It could combine the discriminants, I think: Option<i32> could have discriminant values 0 or 1, and Option<Option<i32>> could use discriminant value 2 for None, and 0 or 1 mean the object's an Option<i32>.
  - dllthomas 11y ago
    Yeah, while the ability to provide a pointer seems meaningful, it might be illusory. If our value is None, then a pointer to the inside Option<i32> is... what? Edited to add: With your proposed encoding, the memory contents of an Option<Option<i32>> is identical to an Option<i32> precisely when there is an Option<i32> to speak about. And when there is no Option<i32>, you can tell that with one comparison, rather than by backing out an unknown number of levels. I like it.
    - deleted 11y ago
      [deleted]
  - jblandy 11y ago
    Yeah, that's a nice trick. I wonder how general it is, though.
    - SamReidHughes 11y ago
      If one alternative is larger than the others and it has an enum tag or pointer inside of it, such that you can squeeze the other alternatives before/after that tag word, you're good to go. If you had multiple alternatives of maximum size, they'd need some word in them, at the same offset/size, such that they don't have conflicting representations. An enum tag could overlap with a non-null pointer, and two enum tags with user-declared tag values (such that they do not overlap) could work too. Or if you're crazy you could discard having each type's representation be computed solely as a function of what the type is made of, choosing their representations based on how well they pack into other types. (Or worse yet, if you've got a borrow checker and your types are memcpyable, you could pack things and rejigger bytes however you wanted and then unfurl them into a temporary whenever something uses the interior value, unless I'm overlooking something. So if you had Either<Either<u32, u32>, Either<u32, u32>>, you could represent that with a single tag whose value is 0, 1, 2, or 3, and when if the tag's 2 or 3 and you make a reference to the interior value, either fix the tag in-place and fix it back when you're done (if you're the sole owner of the Either<Either...>), or copy the value out and let the borrower borrow that (and copy it back in when it's done, if it was a mutable borrow).)

jblandy 11y ago

It may be worth pointing out that the `Option<T>` type in Rust doesn't inherently involve any pointers at all, assuming `T` is not a pointer type itself. For example, `Option<i32>` is probably (the compiler gets to choose) going to be represented as two four-byte values: the discriminant, which distinguishes the `Some` and `None` cases, and then a space for the value `v`, for when the discriminant says we have `Some(v)`. Since zero is a perfectly fine value for an `i32`, we have to store the discriminant separately. But note that this is just a flat eight-byte value. There's no heap allocation involved. It's just as if you'd written in C: struct O { enum { Some, None } discriminant; int32_t value }; I compiled a program that uses `Option<Option<i32>>`, and looked at the DWARF debugging info to see what the compiler did with it. It seems to represent this as a twelve-byte value: four bytes for the discriminant for the outer `Option`, followed an eight-byte `Option<i32>` value laid out as before. Since you can get the address of a value held by an enum, I guess this makes sense; the compiler can't combine the discriminants or do anything clever like that.

SamReidHughes 11y ago
It could combine the discriminants, I think: Option<i32> could have discriminant values 0 or 1, and Option<Option<i32>> could use discriminant value 2 for None, and 0 or 1 mean the object's an Option<i32>.
- dllthomas 11y ago
  Yeah, while the ability to provide a pointer seems meaningful, it might be illusory. If our value is None, then a pointer to the inside Option<i32> is... what? Edited to add: With your proposed encoding, the memory contents of an Option<Option<i32>> is identical to an Option<i32> precisely when there is an Option<i32> to speak about. And when there is no Option<i32>, you can tell that with one comparison, rather than by backing out an unknown number of levels. I like it.
  - deleted 11y ago
    [deleted]
- jblandy 11y ago
  Yeah, that's a nice trick. I wonder how general it is, though.
  - SamReidHughes 11y ago
    If one alternative is larger than the others and it has an enum tag or pointer inside of it, such that you can squeeze the other alternatives before/after that tag word, you're good to go. If you had multiple alternatives of maximum size, they'd need some word in them, at the same offset/size, such that they don't have conflicting representations. An enum tag could overlap with a non-null pointer, and two enum tags with user-declared tag values (such that they do not overlap) could work too. Or if you're crazy you could discard having each type's representation be computed solely as a function of what the type is made of, choosing their representations based on how well they pack into other types. (Or worse yet, if you've got a borrow checker and your types are memcpyable, you could pack things and rejigger bytes however you wanted and then unfurl them into a temporary whenever something uses the interior value, unless I'm overlooking something. So if you had Either<Either<u32, u32>, Either<u32, u32>>, you could represent that with a single tag whose value is 0, 1, 2, or 3, and when if the tag's 2 or 3 and you make a reference to the interior value, either fix the tag in-place and fix it back when you're done (if you're the sole owner of the Either<Either...>), or copy the value out and let the borrower borrow that (and copy it back in when it's done, if it was a mutable borrow).)