`NonNull<T>`, null, and dangling-but-aligned

pub fn stack_ops(script: Vec<String>) -> Vec<i64>

Build a growable stack of i64 out of alloc, dealloc and NonNull<i64>, then run a script of operations against it. One number comes out per operation:

The empty stack must store NonNull::dangling() and must not allocate until the first push. Start with capacity 4 and double. reset must return the stack to exactly the state empty() produced — including not leaving a freed pointer behind, and including not calling dealloc on the dangling one.

Why containers store NonNull<T>, not *mut T

Three reasons, and they are all real.

The niche. NonNull<T> is a *mut T that the compiler knows is never null. That “never null” is a validity invariant, which means the all-zeroes bit pattern is free for another use — so Option<NonNull<T>> is the same size as a pointer, with None represented as the null address. Option<*mut T> is two words. For a linked list node, that is a 50% saving on every link.

Variance. *mut T is invariant in T; NonNull<T> is covariant. That matters for a container of T that only ever hands out &T: covariance lets MyVec<&'long str> be used where MyVec<&'short str> is expected, which is what a caller expects of an owning collection. If your container hands out &mut T you must undo this and become invariant again, with PhantomData<*mut T> — item 17.19 is entirely about that trap.

Documentation. A NonNull field says “this is always a real pointer” in the type, so the null check does not need to exist in every method and cannot be forgotten in one of them.

::: question NonNull::new_unchecked(std::ptr::null_mut()) — you construct it and never use it. Is anything wrong yet? Yes. That is instant undefined behaviour, at the construction.

Non-nullness is NonNull‘s validity invariant, not a safety convention. Producing a value that violates its type’s validity invariant is UB the moment the value exists — assigned to a place, passed as an argument, returned. There is no “I only made a bad one, I did not use it”.

The safe constructor NonNull::new(p) returns Option<NonNull<T>> and costs nothing at runtime, precisely because of the niche: the check and the Option compile away. Reach for new_unchecked only when the non-nullness is already proven by something else on the line above, and say what in the safety comment.

Item 17.12 draws the general line between validity invariants (never break them, not even briefly) and safety invariants (you may break them inside your own module, which is what set_len is for). :::

Dangling is not null

These are two different failures and conflating them causes real bugs.

Null means address zero. Reading it faults on every platform you care about.

Dangling means “the bytes are not all inside one live allocation”. A freed pointer is dangling. A pointer to a stack slot whose frame has returned is dangling. NonNull::dangling() is dangling on purpose: it returns the address align_of::<T>() — a small, well-aligned, non-null, deliberately invalid address.

That is exactly the right thing to store in an empty container, and here is why it has to exist at all: you cannot ask the allocator for zero bytes. Layout::array::<T>(0) produces a zero-sized layout, and passing a zero-sized layout to alloc is undefined behaviour. So an empty Vec has no allocation to point at, and it still needs something in the pointer field that is non-null (for the niche) and aligned (because slice::from_raw_parts(ptr, 0) requires alignment even for length zero). NonNull::dangling() is that something.

The consequence you must get right in this problem: cap == 0 means there is nothing to free. Calling dealloc on NonNull::dangling() hands the allocator an address it never issued.

::: question Your reset frees the buffer and sets cap = 0. A later push allocates again. What must reset leave in the ptr field, and why not just leave the old address? It must write NonNull::dangling() back.

Leaving the freed address there is not immediately UB — nothing dereferences it — but it is a loaded gun. The next person to add a method that reads ptr without checking cap has a use-after-free, and the invariant they violated was never written down anywhere. Restoring the dangling sentinel makes the type have exactly one representation of “empty”, which is what lets every other method reason about cap == 0 instead of about history.

This is the general shape of a safety invariant: a property no compiler checks, that every method in the module both relies on and must restore. Item 17.20 is about why that makes the module — not the block — the unit you have to audit. :::

Two more facts worth carrying

NonNull::as_ref() and as_mut() produce references with an unbounded lifetime: the caller picks it, and picking too long is UB. Prefer to mint references at the point of use, with a lifetime the signature ties down.

A pointer to a zero-sized type is never dangling. Every ZST access is a zero-sized access, and zero-sized accesses are exempt from the “dereferenceable” requirement. That is why Vec<()> works and why item 17.16 explicitly excludes ZSTs from the hand-rolled Vec.

What this grader cannot check

There is no clippy lint for NonNull::new_unchecked misuse, and none for deallocating a dangling pointer. Both are graded here only through behaviour: the reset-then-push cases exercise the dangling round trip, and a dealloc on the sentinel will usually — not always — abort. Your reasoning is the real check.

Remember the grade is compile + tests + clippy -D warnings.