Skip to content

← Unsafe and Soundness step 9 of 24

Medium Primitives

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

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

Implement the unfinished methods of a growable stack of i64, using alloc, dealloc, and NonNull<i64>. Then run the supplied operations. Return one number per operation:

Operation Output
push N The new length
pop The removed top value, or -1 if empty
peek The top value without removing it, or -1 if empty
len The current length
reset 0, after freeing any buffer
Unknown command -2

For example, ["push 8", "push 3", "peek", "pop", "len", "reset", "peek"] returns [1, 2, 3, 3, 1, 0, -1]. A stored -1 is allowed, so that output alone does not distinguish an empty stack from a top value of -1.

Keep the supplied command parser. It splits at the first space, treats a missing or invalid push argument as zero, and ignores arguments on other recognized commands. The seeded tests use valid integer arguments.

Track allocation separately from length

A new stack has len = 0, cap = 0, and ptr = NonNull::dangling(). Allocate four slots on its first push and double capacity when full.

Popping the last element makes the stack empty but leaves its buffer allocated. By contrast, reset must free any allocation and restore all three fields to their initial values. Calling reset twice must be safe.

Maintain these invariants:

  • len <= cap.
  • If cap == 0, there is no allocation to access or free.
  • If cap > 0, the stack owns a buffer with layout Layout::array::<i64>(cap).
  • The first len slots hold the stack's values. Read only those slots.

During growth, allocate the new buffer, copy the live elements, and free the old buffer using its old capacity. Since the elements are i64, they need no destructor calls. A generic collection would need additional handling.

What non-null means

NonNull<T> guarantees a non-null pointer. It does not guarantee a live allocation, alignment, initialized data, or permission to access that data.

For sized types such as i64, Option<NonNull<T>> has the size and alignment of a raw pointer. Null represents None, so no separate tag is needed. This is useful for optional links in data structures.

Check your understanding Is constructing a null NonNull valid if you never dereference it? Show answer

No. Passing null to NonNull::new_unchecked violates its safety requirement immediately. Use NonNull::new(raw), which returns None for null. After allocation, handle that case before using the pointer.

Why use dangling()?

NonNull::dangling() supplies an aligned, non-null placeholder. It does not allocate storage for an i64. Never read, write, or deallocate that placeholder in this stack.

Use cap to determine whether storage exists. Comparing the pointer's address with the placeholder is not a valid allocation test: the address returned by dangling() is not reserved exclusively for this purpose.

The global alloc function requires a nonzero allocation size. That is why this implementation skips allocation when its capacity is zero. Likewise, dealloc requires a currently allocated pointer and the matching layout.

Check your understanding After reset, why restore ptr as well as len and cap? Show answer

It restores the representation established by empty(), making subsequent operations easier to reason about. Merely retaining a freed raw pointer is not itself a dereference, but it is no longer usable for accessing the old allocation. Replacing it with dangling() also does not make unchecked access safe: every method must still respect the length and capacity.

Related pointer rules

Unlike *mut T, NonNull<T> is covariant in T. Whether that is sound for a wrapper depends on its API. Returning &mut T from &mut self does not by itself require an invariant container: Vec<T> is covariant too. Mutation through shared access needs particular care. See variance and PhantomData.

Unsafe reference conversions such as as_ref require more than non-nullness. The data must remain valid for the reference's lifetime, and access must obey Rust's aliasing rules. Zero-sized types have special access rules, but references still require non-null, aligned pointers. This exercise uses i64 only.

A passing submission must compile, pass the tests, and pass clippy -D warnings. These checks do not prove unsafe code sound. In particular, undefined behavior need not produce a crash. Review the invariants and safety comments as well as the outputs.

References: NonNull, global allocation, and pointer safety.