News for hackers. Stuff that matters.
Re:In Defense of Linked Lists by dekhn on Friday November 04, 2022 @05:48PM (#33474312)
I don't know Rust but I would guess that an Option<NonNull<Node<T>>> would be a Node of type T, that cannot be set to null, but can be optional. This is a type I would want to return from a function that could either return nothing, or a pointer to a real thing.

As for the unsafety, I would assume the authors of collections know what they are doing and do that for performance.

Re:In Defense of Linked Lists by proto_lambda on Friday November 04, 2022 @05:51PM (#33474354)
`NonNull` is actually a wrapper around the pointer type, with the added invariant that the pointer cannot be null. The compiler is made aware of this, which allows `Option<NonNull<T>>` to be just a plain pointer, where the `None` variant of the option corresponds to a null pointer and the `Some(ptr)` case corresponds to a non-null pointer.
Re:In Defense of Linked Lists by josephg on Friday November 04, 2022 @06:36PM (#33474932)
I really wish rust had better syntax for this. Raw C pointers should probably all be Option<NonNull<T>> rather than *mut T.

The latter is easier to type but worse in almost every way. Ergonomics should guide you to the former, not the latter.

Re:In Defense of Linked Lists by andrewflnr on Friday November 04, 2022 @06:47PM (#33475059)
I think if you tried to do that, you'd basically be mixing type-driven optimizations with the C FFI, which sounds sketchy, to me at least. The null-optimization for Option is just that, an optimization, and I don't like taking it for granted where safety/security is at stake.
Re:In Defense of Linked Lists by josephg on Friday November 04, 2022 @07:54PM (#33475826)
Thats fair.

I suppose one problem with this approach for C FFI is that there's a lot of different values which could all be "null pointers". Converting them all for Option would be awkward and slow, and you wouldn't want to ever risk getting this stuff wrong.

But pointers are also useful even if you aren't doing FFI. Eg for implementing custom data structures. In that case, Option<NonNull<T>> (Or even NonNull<T>) is usually better than *mut T. But its harder to type, and it doesn't clearly tell you if the pointer should be *mut T or *const T. NonNull<T> should be preferred because security/safety is at stake for this sort of code.

Re:In Defense of Linked Lists by nickitolas on Friday November 04, 2022 @09:09PM (#33476568)
The layout is guaranteed and documented as thus: https://doc.rust-lang.org/std/option/#representation

> Rust guarantees to optimize the following types T such that Option<T> has the same size as T:

> - Box<U>

> - &U

> - &mut U

> - fn, extern "C" fn1

> - num::NonZero*

> - ptr::NonNull<U>

> - #[repr(transparent)] struct around one of the types in this list.

> This is called the “null pointer optimization” or NPO.

> It is further guaranteed that, for the cases above, one can mem::transmute from all valid values of T to Option<T> and from Some::<T>(_) to T (but transmuting None::<T> to T is undefined behaviour).

Although I'm not sure if the ABI is guaranteed to match (Which could differ even if the layout matches AFAIK). The ABI for Box is guaranteed to match since https://blog.rust-lang.org/2020/01/30/Rust-1.41.0.html , and I would imagine NonNull is the same. Maybe you could open an issue in the UCG asking if you're needing confirmation.

Re:In Defense of Linked Lists by kibwen on Friday November 04, 2022 @06:55PM (#33475163)
It's an interesting suggestion to impose Option semantics on raw pointers by default (presumably with some alternative way to receive a nullable pointer, for completeness). But in the meantime, in your own codebase, it's easy enough to do `type Ptr<T> = Option<NonNull<<T>>`.
Re:In Defense of Linked Lists by josephg on Saturday November 05, 2022 @02:28AM (#33478547)
The problem there is that NonNull is exclusively a wrapper around *mut T. Using it discards the distinction with *const _ pointers. I think that has implications for correctness with Miri.