Case Study 1: The Leaking Stack

"A pointer bug does not announce itself. It waits."

Executive Summary

You have inherited a small but load-bearing routine from a departed colleague: a pointer-based stack used inside a particle code to hold "candidate collisions" while a sweep runs. It works on small inputs and then, on a long production run, it slowly consumes all of memory and eventually crashes — and once, alarmingly, it printed a wrong answer without crashing at all. This is the archetypal pointer situation: code that is mostly right, failing silently in exactly the ways §11.2 warned about. We will read it, name each of its three defects precisely — an undefined pointer, a leak, and a dangling alias — repair them into a version that runs clean, and then make the professional call: port the structure to a plain allocatable array, because in Fortran that is what it should have been all along.

Skills applied: reading pointer code and identifying the data structure (§11.1, §11.3); the three association statuses and the two hazards (§11.2); safe teardown of a linked structure (§11.3); the allocatable-over-pointer rule and why it removes whole bug classes (§11.4).

Background

The structure is a singly linked stack: push a node onto the head, pop from the head, last-in-first-out. Here is the inherited code, faithfully reproduced. Read it before you read our diagnosis — see how many of the three faults you can find yourself.

! --- INHERITED CODE (contains three bugs; do not model code on this) ---
type :: node_t
  integer :: id
  type(node_t), pointer :: next        ! (bug 1 lives here)
end type node_t

type(node_t), pointer :: top           ! (and here)

subroutine push(id)
  integer, intent(in) :: id
  type(node_t), pointer :: fresh
  allocate(fresh)
  fresh%id   = id
  fresh%next => top
  top        => fresh
end subroutine

subroutine pop(id)
  integer, intent(out) :: id
  id  =  top%id
  top => top%next        ! (bug 2 lives here)
end subroutine

Elsewhere, the caller keeps a handle to the "current best" candidate for use after the sweep:

best => top              ! remember the current top node
call pop(discard)        ! ... but then pop it off
print *, best%id         ! (bug 3 lives here)

Four hard questions press on any such inheritance: what is the structure? where does it corrupt state? where does it leak? and should it exist at all? We take them in turn.

Phase 1 — Read the Code and Name the Structure

Start by recognizing the shape, because the bugs follow from it. node_t holds an id and a pointer to the same type — the signature of a linked structure (§11.3). top is the head; push prepends; pop reads the head's id and advances top to the next node. So it is a stack, and its operations are $O(1)$, which is why the original author chose it. Nothing here is exotic. Everything here is a place a pointer can betray you.

A useful first move with any inherited pointer code is to annotate, for every pointer, when it gets a defined status and who is responsible for freeing what it points at. Do that here and two of the three bugs fall out immediately.

Phase 2 — Bug One: The Undefined Pointer

Look at the declarations: type(node_t), pointer :: next in the type, and type(node_t), pointer :: top at module level. Neither is initialized. That means top begins with undefined association status (§11.2) — not disassociated, undefined. The very first push does fresh%next => top, reading top before it has ever been given a defined value, and any code that guards with if (associated(top)) before the first push is asking a question the standard says must not be asked.

On most runs this happens to work, because uninitialized memory happens to look null — which is exactly what makes it dangerous: it passes your tests and fails on the cluster. The fix is the one-time habit from §11.2: give every pointer a defined status at birth.

type(node_t), pointer :: next => null()   ! in the type
type(node_t), pointer :: top  => null()   ! at module level

Now top is genuinely disassociated before the first push, associated(top) is a legal question with a .false. answer, and the end-of-stack test (next => null() on the last node) is well defined.

Phase 3 — Bug Two: The Leak

Trace the memory in pop. It reads top%id, then does top => top%next, moving the head pointer past the old node. But nothing ever deallocates that old node. Its memory was obtained by allocate in push; once top no longer points at it and no other pointer does either, it is unreachable and unfreed — a classic leak. Push a million candidates over a long run, pop them all, and you have leaked a million nodes: the slow memory growth the production run exhibited.

The repair is the save-then-free discipline of §11.3 — capture the node, advance the head, then free:

subroutine pop(id, status)
  integer, intent(out) :: id, status
  type(node_t), pointer :: old
  if (.not. associated(top)) then      ! defensive: don't pop an empty stack
    id = 0; status = -1; return
  end if
  id     =  top%id
  old    => top          ! remember the node to free
  top    => top%next     ! unlink it from the head
  deallocate(old)        ! free it — no leak
  status =  0
end subroutine

Note we also hardened pop against an empty stack: reading top%id when top is disassociated is itself a null-dereference, and returning a status lets the caller notice rather than crash.

Phase 4 — Bug Three: The Dangling Alias

The subtlest fault is in the caller, not the structure. It saves best => top — a second alias for the head node — then pops that very node, which (with our fix) now frees it. best is untouched by the deallocation; it still holds the old address; it now dangles (§11.2). The subsequent print *, best%id reads freed memory: on a good day a crash, on a bad day a plausible-looking wrong number — which is precisely the "wrong answer without crashing" the run once produced.

There is no way to make best safe after the fact, because associated(best) may still report .true.. The only cure is discipline about ownership: if you intend to keep using a node's data, either do not free it while an alias survives, or copy the value out before freeing:

best_id = top%id     ! copy the VALUE out (an integer, owned by nobody)
call pop(discard, st)
print *, best_id     ! safe: it is a plain integer, not an alias

This is the deepest lesson of the case study: a deallocation is the death of every alias to that memory, and the language tracks only the one pointer you named. The rest are your responsibility.

Phase 5 — The Fix, Verified — and the Port

Assemble the repairs into a self-contained stack and run it. This version initializes every pointer, frees on pop, and copies values rather than aliasing nodes it will destroy:

program fixed_stack
  implicit none
  type :: node_t
    integer :: id
    type(node_t), pointer :: next => null()
  end type node_t
  type(node_t), pointer :: top => null()
  integer :: id, st

  call push(10)
  call push(20)
  call push(30)                 ! stack (top -> bottom): 30, 20, 10

  do while (associated(top))
    call pop(id, st)
    if (st /= 0) exit
    print '(a, i0)', 'popped ', id
  end do
  print '(a, l1)', 'empty now? ', .not. associated(top)

contains
  subroutine push(id_in)
    integer, intent(in) :: id_in
    type(node_t), pointer :: fresh
    allocate(fresh)
    fresh%id   = id_in
    fresh%next => top
    top        => fresh
  end subroutine push

  subroutine pop(id_out, status)
    integer, intent(out) :: id_out, status
    type(node_t), pointer :: old
    if (.not. associated(top)) then
      id_out = 0; status = -1; return
    end if
    id_out =  top%id
    old    => top
    top    => top%next
    deallocate(old)
    status =  0
  end subroutine pop
end program fixed_stack

$ gfortran -std=f2018 -Wall fixed_stack.f90 -o stack && ./stack
popped 30
popped 20
popped 10
empty now? T

The output confirms the LIFO order (30, 20, 10) and an empty, disassociated stack at the end — and, though you cannot see it in the output, no leak: every node freed on its way out.

Now the professional judgment. We have a correct pointer stack. Should we keep it? In Fortran, almost certainly not. A stack is a textbook case where an array wins (§11.3, §11.4): a stack is just an allocatable array plus an integer "top" index. Push is n = n + 1; data(n) = x (growing the array when full, as the second case study builds); pop is x = data(n); n = n - 1. There are no nodes to allocate, no next pointers to maintain, no teardown loop, and — the point of this whole study — none of the three bugs is even expressible: an integer index cannot be undefined-as-a-pointer, cannot leak, and cannot dangle. The array version is faster (contiguous, cache-friendly), shorter, and safe by construction. The pointer stack was not wrong to fix; it was wrong to exist, and the modernizing move is to replace it.

Discussion Questions

1. Of the three bugs, which would you expect to survive the longest in production undetected, and why? Rank them by "days until someone notices."
2. The undefined-pointer bug "happens to work" when uninitialized memory reads as null. Why is code that works by accident more dangerous than code that fails immediately? Connect your answer to the book's honesty discipline.
3. The port to an array eliminates all three bug classes "by construction." Name another data structure where switching from pointers to an index-based array would remove entire categories of bug, and one where it genuinely would not.

Your Turn: Extensions

• Option A. Take the corrected pointer stack and add a peek(id, status) operation that returns the top id without removing the node. Show that peek is safe even though pop frees nodes — what makes the difference?
• Option B. Rewrite the stack as an allocatable array with a top index (fixed capacity is fine for a first pass). Compare the line counts and list, for each of the three original bugs, why it can no longer occur.
• Option C. Add -fcheck=all and valgrind to your toolchain (previewing Chapter 13) and run both the leaking original and your fix. What does each tool report, and which bug does each catch?

Key Takeaways

• Pointer code fails in three characteristic ways — undefined status, leaks, dangling aliases — and all three are silent; you learn to see them on the page, not from a crash.
• A deallocation kills every alias to that memory. The language tracks the one pointer you named; the rest are your responsibility. Copy values out before you free what an alias still watches.
• Teardown is save-then-free: never read a node after deallocating it.
• The deepest fix is often not to fix the pointer code but to replace it. In Fortran a stack, a queue, or a growable list is an allocatable array, and that choice makes the whole family of pointer bugs inexpressible.