A stack takes out the element that went in most recently, and that is the whole specification. No indexing, no search, no insertion in the middle, no access to anything but one end. Most collections are described by the operations they add; a stack is described by the ones it takes away, and the reason to accept fewer operations is that the remaining ones answer a question nothing else answers cleanly: what has been started and not yet finished, innermost first.
One rule, and nothing else
Draw a column of boxes with a mark on the top one. Push puts a new box above the mark and moves the mark up. Pop takes the marked box away and moves the mark down. Peek reads the marked box without moving anything. There is no fourth operation and no way to name box three.
The invariant is that the elements present are exactly those pushed and not yet popped, and the one reachable element is the newest of them. Stated that way it sounds like a restatement, so look at what it rules out. It rules out reading past the top, which means no code anywhere can depend on the second element while the first is still there. It rules out removing from the bottom, which means the sequence of pops is the exact reverse of the sequence of pushes. Hold both and the stack’s contents at any instant are a chain: each element was pushed while the one below it was already present and will be popped before it. That is nesting, written down.
Which is why the restriction is worth imposing rather than merely tolerating. A parser reading ([{ has three open constructs, and the order they must close in is determined. If the parser keeps them in a slice and indexes freely, nothing stops it from matching the round bracket and leaving the brace open behind it, and the bug that results is a parser that accepts malformed input. If it keeps them on a stack, the only element it can remove is the innermost one, so the out-of-order match is not a case to be detected but a move the structure does not offer. A mismatched closer still has to be caught, and the Balanced function below catches it with a single comparison against the popped opener. One comparison to get right, and no way to express the wrong removal at all.
Depth falls out of the same arrangement, with no extra bookkeeping. The number of elements on the stack is the current nesting level, so a bound on recursion depth is a comparison against Len, and that comparison is why an explicit stack beats recursion for anything reading input you did not write.
What it costs, past the complexity table
Push is amortised constant time, Pop and Peek are constant time in the worst case, and indexing by position does not exist. That is the complexity table, and for a stack it is almost uninformative: there is no operation whose cost depends on the number of elements. Everything interesting is in the constants, and in Go the constants come from which of two representations you picked.
The slice representation is a slice used with append and a shortened length, and the reason it is the right default is that the slice header is three words over a contiguous array. Pushing writes to an address the compiler computed by adding a constant to the data pointer. Popping reads the same way and decrements a length. The top few elements of a working stack stay in cache because they are adjacent in memory and the access pattern touches them repeatedly, so a push-pop pair against a warm stack is a handful of instructions and a cache hit.
Growth is the one place the slice representation does real work. append allocates a larger array and copies when the current capacity runs out, so a run of pushes from an empty stack does a logarithmic number of reallocations and copies each element a constant number of times on average. Amortised growth is arithmetic rather than sleight of hand, and the growth factor is an implementation choice that has changed between Go releases, so do not write code that assumes one. What is reliable is the fix: when you know the depth, make([]T, 0, depth) and the reallocations go away.
The capacity stays after the pops. A slice stack that reached a million elements and popped back to empty still holds the array for a million elements, because the slice header still points at it and nothing shrinks a slice’s capacity. For a stack that is reused, that is reuse and not waste: the next run of pushes allocates nothing. For a stack that handled one pathological input and will now sit idle in a long-lived struct, it is room for a million elements holding nothing, and releasing it means assigning a fresh slice rather than truncating.
Escape analysis can keep the backing array off the heap, and whether it does on any given day is a compiler decision rather than a language guarantee. A stack declared as a local variable, with a capacity the compiler can see and no address escaping the function, is a candidate. Pass a pointer to it into something the compiler cannot see through and it is not. go build -gcflags=-m prints the decision the compiler actually made, which is the only honest way to find out, and the answer is specific to the version you are building with.
The linked representation is one node per element, each holding a value and the address of the node below. It never reallocates, so no push ever copies an element and no element ever moves. The cost is one allocation per push, one pointer of overhead per element, a dependent load per pop, and a node per element for the garbage collector to trace. Popping cannot stall on a copy, which is its one real advantage over the slice, and the allocator traffic is heavy enough that it is the wrong default. Do not take a ratio from me for that; take the benchmark below and run it on the machine you deploy to.
Two Go specifics apply to both representations. A method on a value receiver gets a copy of the struct, so func (s Stack[T]) Push(v T) allocates, appends, assigns the result to a struct that goes out of scope on return, and loses the element. It compiles and it does nothing. And handing out &s.items[len(s.items)-1] as a pointer to the top element is the append-aliasing bug in its stack-shaped form: the next push may move the array, and the pointer then refers to a stale copy that further pushes do not update. Return the value from Peek, or return an index, or use the linked representation where node addresses are stable because nothing ever moves.
The shape of problem it fits
Reach for a stack when the work opens and closes and what you need to know is what is currently open. The call stack is the version everybody uses and nobody names. Calling a function pushes a frame holding its arguments, locals and return address; returning pops it. Recursion depth is the height of that stack, which is why a recursive function on deeply nested input runs out of memory rather than running slowly. In Go the goroutine stack starts small and grows, and runtime/debug.SetMaxStack documents the initial maximum as 1 GB on 64-bit systems and 250 MB on 32-bit. Exceeding it is a fatal error and not a panic, so recover does not catch it and the process ends. defer is the same structure made explicit in the language: deferred calls run in last-in-first-out order, so the cleanup for the thing you opened last happens first.
Expression evaluation is the textbook case and it is textbook because it works. Dijkstra’s shunting-yard algorithm reads tokens left to right, sends operands straight to the output, and keeps operators on a stack; when an operator arrives that binds less tightly than the one on top, the top goes to the output first, and a tie is settled by the operators’ associativity. A left parenthesis pushes, a right parenthesis pops until it finds the matching left one. The operator stack holds exactly the operators whose right-hand operands have not arrived yet, which is the same nesting claim in a different domain.
Depth-first traversal written iteratively is a stack holding the nodes discovered but not yet visited. The detail that catches people is the order: a stack returns children in the reverse of the order they went on, so pushing a node’s children left to right visits them right to left. The iterative version has to push them in reverse to match the recursive one, and getting it wrong produces a traversal that is correct in structure and mirrored in output, which passes every test that only checks the set of nodes visited.
Undo history is a stack because an undo reverses the most recent change, and redo is a second stack that the undo pops feed into. Any new edit clears the redo stack, because the history it described no longer leads anywhere. Checking balanced delimiters is a stack of openers, which is the Balanced function written out below.
The reason to convert a recursive algorithm to an explicit stack is control over all of this. Recursion puts the pending work in frames you cannot inspect, cannot bound except by crashing, and cannot save. An explicit stack puts the same work in a slice you own. A depth limit becomes if pending.Len() > maxDepth { return ErrTooDeep }, which is an error the caller handles rather than a fatal error that ends the process, and that difference is the entire argument for writing a parser for untrusted input iteratively. The loop can also stop between iterations, because the whole state of the traversal is the stack plus the loop variable: check a context for cancellation, report progress as a fraction of the nodes seen, serialise the stack and resume the traversal in a different process tomorrow. None of that is available when the state lives in frames.
When not to, and what instead
Use a slice directly whenever you need to look at anything other than the top. Walking the collection, indexing by position, sorting, searching: all of these are what a contiguous array is built for, and the slices package covers more of it than people expect, with slices.Sort, slices.BinarySearch, slices.Index, slices.Reverse, slices.Clone, slices.Delete, slices.Compact and slices.Equal already written and tested. Wrapping a slice in a type that exposes three methods hides all of that, so impose the restriction only where the restriction is doing work.
Use a queue when the order you want out is the order things went in. The wrong way to build one in Go is a slice popped with q = q[1:], which walks the data pointer forward and leaves the consumed elements allocated behind it, so a long-running queue holds its entire history in memory while reporting a small length. A ring buffer over a fixed array suits a bounded queue; a linked queue with head and tail pointers suits an unbounded bursty one. A buffered channel is a queue as well, and it is not a stack substitute, because the receive order is the send order.
Use a heap when you want the largest or the smallest rather than the newest. container/heap is in the standard library, the algorithm in it is correct and worth using, and its interface predates generics: you implement five methods on your own type and the element boundary is any, so small values are boxed on the way in and type-asserted on the way out. That is a real cost and still usually better than writing your own sift-down.
Do not reach for container/list as a stack. It is a doubly linked list, its Element.Value field is any, and every element it allocates carries a next, a prev and a pointer back to the list it belongs to, for a structure that needs one pointer at most. There is no container/stack in the standard library, and the absence is correct: a slice with append and a shortened length is three lines, and generics made those three lines type-safe without any anywhere in them.
Use the linked representation only for the two cases that justify it. One is a stack whose elements are referred to from outside while the stack changes, where a node address has to stay valid across pushes. The other is a stack shared between versions: pushing onto a chain produces a new head whose tail is the old chain, both remain valid, and every element below the new one is shared rather than copied. A stack of lexical scopes works that way, and so does any history that branches.
Nothing here is safe to share between goroutines. Push writes both the backing array and the length, two goroutines pushing concurrently is a data race whether or not it has ever produced a wrong answer, and go test -race reports it with both stacks. Guard it with a mutex, give each goroutine its own, or use a channel.
Writing it in Go
The slice version is a struct, three methods and one assignment that people leave out.
// Package stackkit is a last-in-first-out stack, written out so the
// truncation is visible. The slice version is the default; LinkedStack and
// Chain below exist for the two cases that need stable addresses.
package stackkit
import (
"fmt"
"sync"
)
// Stack is a slice used as a stack: index 0 is the bottom, len(items)-1 is the
// top. The invariant, which checkCleared verifies, is that every slot in
// items[len(items):cap(items)] holds the zero value of T, so nothing popped is
// reachable from the backing array.
type Stack[T any] struct {
items []T
}
func (s *Stack[T]) Len() int { return len(s.items) }
// Push appends to the top. Growth is amortised and the factor is an
// implementation choice, so pass a capacity to make() when the depth is known
// rather than relying on a number the language does not specify.
func (s *Stack[T]) Push(v T) {
s.items = append(s.items, v)
}
// Pop removes and returns the top. The zero assignment is the line that gets
// left out: s.items = s.items[:n] on its own leaves the popped value in the
// backing array, where the collector still sees it and still keeps alive
// whatever it points at.
func (s *Stack[T]) Pop() (T, bool) {
var zero T
n := len(s.items) - 1
if n < 0 {
return zero, false
}
v := s.items[n]
s.items[n] = zero
s.items = s.items[:n]
return v, true
}
// Peek returns the top by value. It does not return &s.items[n], because the
// next Push may move the array and leave that pointer naming a stale copy.
func (s *Stack[T]) Peek() (T, bool) {
var zero T
if len(s.items) == 0 {
return zero, false
}
return s.items[len(s.items)-1], true
}
How much that zero assignment matters depends entirely on T. For Stack[int] it is a write that changes nothing anyone can observe, because an int holds no references and the slot is going to be overwritten by the next push anyway. For Stack[*Connection], Stack[[]byte], Stack[string] or any struct containing a pointer, the abandoned slot holds a live reference in an array the collector can reach, so the popped object stays alive until something pushes over the top of it. A stack that peaks at ten thousand elements and then idles at three holds 9,997 dead objects. The generic form, var zero T and an assignment, costs nothing for the types where it is unnecessary and fixes the types where it is not, so write it unconditionally rather than reasoning about T at every call site.
Truncating several elements at once needs the same fix applied in bulk, and clear does it: on a slice it sets every element up to the length to the zero value.
// TruncateTo pops down to k elements, zeroing every slot it abandons. The
// subslice items[k:] has length len(items)-k, which is exactly the range
// clear needs to cover.
func (s *Stack[T]) TruncateTo(k int) {
if k < 0 || k > len(s.items) {
panic(fmt.Sprintf("truncate to %d with %d elements", k, len(s.items)))
}
clear(s.items[k:])
s.items = s.items[:k]
}
// Reset empties the stack and keeps the capacity, so the next run of pushes
// allocates nothing. Assign a fresh zero Stack instead where the array should
// be released: truncating never shrinks capacity.
func (s *Stack[T]) Reset() {
clear(s.items)
s.items = s.items[:0]
}
// checkCleared verifies the invariant. It compares against the zero value, so
// it constrains T to comparable; the exported type does not.
func checkCleared[T comparable](s *Stack[T]) error {
var zero T
tail := s.items[len(s.items):cap(s.items)]
for i, v := range tail {
if v != zero {
return fmt.Errorf("slot %d above the top holds %v, want the zero value",
len(s.items)+i, v)
}
}
return nil
}
slices.Delete applies the same fix in the standard library, zeroing the slots it abandons at the end of the slice. That has not always been true of it, so check go doc slices.Delete against the version you build with rather than trusting a memory of the behaviour.
The two operations that need the linked representation are a mutable stack with stable node addresses and an immutable chain that shares its tail.
type node[T any] struct {
next *node[T]
value T
}
// LinkedStack never reallocates and never moves an element, so an address
// taken from it stays valid whatever is pushed afterwards. One allocation per
// push is what that costs.
type LinkedStack[T any] struct {
top *node[T]
n int
}
func (s *LinkedStack[T]) Len() int { return s.n }
func (s *LinkedStack[T]) Push(v T) {
s.top = &node[T]{next: s.top, value: v}
s.n++
}
func (s *LinkedStack[T]) Pop() (T, bool) {
var zero T
if s.top == nil {
return zero, false
}
nd := s.top
s.top = nd.next
nd.next = nil // the popped node must not hold the rest of the stack alive
s.n--
return nd.value, true
}
// Chain is the same nodes used immutably. Push returns a new Chain sharing
// every node below the new top, and the receiver is unchanged, so several
// chains can descend from one tail. The value receivers are deliberate here:
// copying a two-field struct is what makes the old chain keep working.
type Chain[T any] struct {
head *node[T]
n int
}
func (c Chain[T]) Len() int { return c.n }
func (c Chain[T]) Push(v T) Chain[T] {
return Chain[T]{head: &node[T]{next: c.head, value: v}, n: c.n + 1}
}
func (c Chain[T]) Pop() (T, Chain[T], bool) {
var zero T
if c.head == nil {
return zero, c, false
}
return c.head.value, Chain[T]{head: c.head.next, n: c.n - 1}, true
}
Sharing a stack between goroutines is a separate type rather than a mutex inside Stack, because the single-goroutine case is the common one and should not take the lock.
type Locked[T any] struct {
mu sync.Mutex
s Stack[T]
}
func (l *Locked[T]) Push(v T) {
l.mu.Lock()
defer l.mu.Unlock()
l.s.Push(v)
}
func (l *Locked[T]) Pop() (T, bool) {
l.mu.Lock()
defer l.mu.Unlock()
return l.s.Pop()
}
Two uses of the slice stack are worth writing out in full. The first is delimiter matching, which is the smallest honest example of the nesting claim.
// closers maps each closing delimiter to the opener it matches. A map suits
// this because the only operation is a lookup by key: nothing iterates it,
// which matters because the language does not specify map iteration order and
// the runtime randomises it.
var closers = map[byte]byte{')': '(', ']': '[', '}': '{'}
// Balanced reports whether every opening delimiter in s is closed by its
// partner in the right order, and the offset of the first delimiter that
// breaks the rule, or -1 when none does. An unclosed opener reports len(s),
// because the fault is the end of the input rather than any byte in it.
func Balanced(s []byte) (bool, int) {
var open Stack[byte]
for i, c := range s {
switch c {
case '(', '[', '{':
open.Push(c)
case ')', ']', '}':
top, ok := open.Pop()
if !ok || top != closers[c] {
return false, i
}
}
}
if open.Len() > 0 {
return false, len(s)
}
return true, -1
}
The second is the iterative traversal, where the reverse push is the line worth reading twice.
type Tree struct {
Label string
Children []*Tree
}
// PreorderIterative visits every node in the same order the recursive version
// would. Children go on in reverse because a stack returns them in the
// reverse of the order they were pushed, and pushing them forwards produces a
// traversal that is correct in structure and mirrored at every level.
func PreorderIterative(root *Tree, visit func(*Tree)) {
if root == nil {
return
}
pending := Stack[*Tree]{items: make([]*Tree, 0, 16)}
pending.Push(root)
for {
nd, ok := pending.Pop()
if !ok {
return
}
visit(nd)
for i := len(nd.Children) - 1; i >= 0; i-- {
pending.Push(nd.Children[i])
}
}
}
That stack holds *Tree, so the zeroing in Pop is doing real work: a traversal of a wide tree pushes thousands of pointers, and without it the deepest part of the array keeps subtrees alive long after the traversal has moved past them.
How to test it
Start with the invariant check, because the defect that actually ships with this structure is the uncleared slot, and no comparison of contents finds it. Everything below lives in stackkit_test.go in the same package, so it can reach items and checkCleared.
Table-driven tests cover the cases you can name, and for Balanced the named cases are the boundaries of the rule: nothing, one pair, nesting, adjacency, a close with nothing open, an open never closed, and the crossed pair that a counter-based implementation gets wrong.
package stackkit
import (
"math/rand/v2"
"slices"
"testing"
)
func TestBalanced(t *testing.T) {
tests := []struct {
name string
in string
want bool
wantPos int
}{
{"empty", "", true, -1},
{"one pair", "()", true, -1},
{"nested three deep", "([{}])", true, -1},
{"adjacent", "()[]{}", true, -1},
{"text between", "a(b[c]d)e", true, -1},
{"crossed", "([)]", false, 2},
{"close with nothing open", ")", false, 0},
{"opener never closed", "(", false, 1},
{"inner opener never closed", "([]", false, 3},
}
for _, tt := range tests {
t.Run(tt.name, func(t *testing.T) {
got, pos := Balanced([]byte(tt.in))
if got != tt.want || pos != tt.wantPos {
t.Errorf("Balanced(%q) = %v, %d; want %v, %d",
tt.in, got, pos, tt.want, tt.wantPos)
}
})
}
}
The property that defines a stack is that the pops come out in the reverse of the order the pushes went in, and that is testable directly against slices.Reverse on generated input. It finds any confusion between the two ends immediately, on the first input longer than one element.
func TestPopOrderIsPushOrderReversed(t *testing.T) {
rng := rand.New(rand.NewPCG(13, 17)) // fixed seed, so a failure replays
for range 2000 {
pushed := make([]int, rng.IntN(32))
for i := range pushed {
pushed[i] = rng.IntN(1000)
}
var s Stack[int]
for _, v := range pushed {
s.Push(v)
}
var popped []int
for {
v, ok := s.Pop()
if !ok {
break
}
popped = append(popped, v)
}
want := slices.Clone(pushed)
slices.Reverse(want)
if !slices.Equal(popped, want) {
t.Fatalf("pushed %v, popped %v, want %v", pushed, popped, want)
}
}
}
The test that finds more than any list of cases is a randomised comparison against a reference, and for a stack the reference is a plain slice. Generate an operation sequence, apply each operation to both, and compare after every one. The reference pops with ref = ref[:len(ref)-1], the bare truncation Pop goes out of its way to avoid, and that is correct here: the reference holds int, which contains no references, so there is nothing for the abandoned slot to keep alive.
func TestMatchesSliceReference(t *testing.T) {
rng := rand.New(rand.NewPCG(3, 5))
for range 500 {
var s Stack[int]
var ref []int
for range rng.IntN(60) {
switch rng.IntN(3) {
case 0:
v := rng.IntN(100)
s.Push(v)
ref = append(ref, v)
case 1:
got, ok := s.Pop()
if ok != (len(ref) > 0) {
t.Fatalf("Pop ok = %v with %d reference elements", ok, len(ref))
}
if ok {
if want := ref[len(ref)-1]; got != want {
t.Fatalf("Pop = %d, want %d", got, want)
}
ref = ref[:len(ref)-1]
}
case 2:
got, ok := s.Peek()
if ok != (len(ref) > 0) {
t.Fatalf("Peek ok = %v with %d reference elements", ok, len(ref))
}
if ok && got != ref[len(ref)-1] {
t.Fatalf("Peek = %d, want %d", got, ref[len(ref)-1])
}
}
if err := checkCleared(&s); err != nil {
t.Fatal(err)
}
if !slices.Equal(s.items, ref) {
t.Fatalf("stack %v, reference %v", s.items, ref)
}
}
}
}
checkCleared runs after every single operation rather than once at the end, so a failure names the operation that broke the invariant instead of the one that happened to notice. That matters more here than for most structures, because the uncleared slot is invisible until some later push either overwrites it or does not.
The leak itself needs its own test, and the way to write it is to look at the backing array rather than at the stack. Take a slice over the whole capacity before the pops, pop everything, and assert that every slot is nil. Nothing reallocates during a run of pops, so the view stays pointed at the same array.
func TestPopClearsTheSlot(t *testing.T) {
var s Stack[*int]
for i := range 4 {
v := i
s.Push(&v)
}
array := s.items[:cap(s.items)] // the whole backing array, not just the live part
for range 4 {
if _, ok := s.Pop(); !ok {
t.Fatal("Pop on a non-empty stack returned false")
}
}
for i, p := range array {
if p != nil {
t.Errorf("slot %d still holds %p after the element was popped", i, p)
}
}
}
Delete the zero assignment from Pop and two tests fail, this one and the checkCleared call inside the reference comparison, while everything that only compares contents still passes. That is the shape of the defect: an implementation that returns the right values and holds memory it has no use for.
A fuzz target suits Balanced because its input is bytes and the interesting inputs are orderings a uniform generator will not reach. Comparing against a reduction reference is stronger than comparing against another stack: strip the non-delimiters, then delete adjacent matched pairs until no more can be removed, and a balanced input reduces to nothing. The reduction is quadratic and correct by inspection, which is what a reference is for.
func FuzzBalanced(f *testing.F) {
f.Add([]byte("([{}])"))
f.Add([]byte("([)]"))
f.Add([]byte("a(b)c"))
f.Fuzz(func(t *testing.T, in []byte) {
got, pos := Balanced(in)
if got {
if pos != -1 {
t.Fatalf("Balanced(%q) reported balanced at position %d", in, pos)
}
if left := reduce(in); len(left) != 0 {
t.Fatalf("Balanced(%q) said balanced, reduction left %q", in, left)
}
return
}
if pos < 0 || pos > len(in) {
t.Fatalf("Balanced(%q) failed at %d, outside 0..%d", in, pos, len(in))
}
})
}
// reduce deletes adjacent matched pairs until none remain. An empty result
// means the input was balanced. slices.Delete does the removal, and it zeroes
// the slots it abandons, which is the same fix Pop applies by hand.
func reduce(in []byte) []byte {
ds := make([]byte, 0, len(in))
for _, c := range in {
switch c {
case '(', ')', '[', ']', '{', '}':
ds = append(ds, c)
}
}
for {
shrunk := false
for i := 0; i+1 < len(ds); i++ {
if opener, ok := closers[ds[i+1]]; ok && ds[i] == opener {
ds = slices.Delete(ds, i, i+2)
shrunk = true
break
}
}
if !shrunk {
return ds
}
}
}
That target asserts one direction, that anything Balanced accepts the reference also accepts, plus a range check on the reported position. Asserting the other direction needs the reference to agree about which byte is at fault, and the two algorithms find faults in different orders, so the position would disagree on inputs where both are right. Pick the direction you can state exactly and leave the other to the table.
Where the claim is about cost, the test is a benchmark and the result is a measurement on one machine rather than a fact about Go. Build and drain both representations at the same depth and read the allocation columns first, because allocs/op is a property of the code while nanoseconds are a property of the hardware and the load on it.
var sink int
func BenchmarkPushPopDrain(b *testing.B) {
const n = 4096
drain := func(pop func() (int, bool)) int {
total := 0
for {
v, ok := pop()
if !ok {
return total
}
total += v
}
}
b.Run("slice/preallocated", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
s := Stack[int]{items: make([]int, 0, n)}
for i := range n {
s.Push(i)
}
sink = drain(s.Pop)
}
})
b.Run("slice/grown", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
var s Stack[int]
for i := range n {
s.Push(i)
}
sink = drain(s.Pop)
}
})
b.Run("linked", func(b *testing.B) {
b.ReportAllocs()
for range b.N {
var s LinkedStack[int]
for i := range n {
s.Push(i)
}
sink = drain(s.Pop)
}
})
}
The three cases are there because the comparison people want is the wrong one. A preallocated slice stack against a linked stack measures the allocator, and the answer is not in doubt. The pair worth reading is slice/grown against linked, which is a logarithmic number of allocations and a bounded number of copies per element against one allocation per element and no copies at all. Run it with -benchmem on your own hardware with your own element type, because a 200-byte struct changes the copy cost and a pointer-free type changes what the collector has to walk afterwards.
Then run everything under -race. Stack has no synchronisation, so a test that pushes from several goroutines is a reported race with both stacks named, and the same test under a plain go test passes nearly always. Locked is what makes it safe, and the test that proves it is the concurrent one that comes back clean.