Tree zippers

A cursor into an immutable tree that remembers the way back up, so editing one node deep inside does not mean redoing the walk that found it.

Where this shows up in reverse engineering

Any tool that rewrites an AST recovered from legacy or compiled source — rather than one it generated itself — has this exact shape of problem: find one node deep inside a large tree, change it, climb back out, then do it again for the next one.

• A GOTO-elimination pass over a parsed COBOL program is the concrete case this page builds toward: walk down to a jump that needs restructuring, turn it into a conditional block, climb back out — and the next jump needing attention is somewhere else in the same tree, reached the same way, with none of the first edit's work redone.
• A decompiler reconstructing source from a recovered AST faces the identical problem at every control-flow fixup it makes: an AST with thousands of nodes and a handful of places that need rewriting should cost work proportional to the handful, not to the thousands, every single time one of them is touched.
• Why "just mutate the tree" is the wrong comparison: a zipper is not primarily about avoiding mutation — it is about not re-walking from the root to find out which ancestors need rebuilding. A tool that already knows "I am three levels deep, here is my path back up" because it just walked there, instead of re-deriving that path after the fact, is already most of the way to a zipper whether or not it calls it one.

The problem

The data structure this page walks through is Huet's zipper.^[1] The tree never changes in place — a new node is built, never overwritten. So changing one node three levels down means building a new copy of it, then a new copy of its parent pointing at the new copy, then a new copy of its parent, up to the root. Nothing above the edit can be reused; the whole path has to be rebuilt.

Walking down to find the node in the first place already visits every statement on that path. Thrown away once the node is found, that walk has to happen a second time, backward, just to know which nodes need rebuilding. The zipper is what remembers the first walk, so there is no second one.

The tree

A small tree, four levels at its deepest:

flowchart TD
    Root --> A
    Root --> B
    A --> A1
    A --> A2
    A1 --> X

Say the goal is to reach X and give it a sibling. In the diagrams below, amber marks the node currently in focus; a bordered node marks one remembered on the trail.

Going down: the trail grows

A zipper is two things: current, the node in focus, and trail, the ancestors passed to get there, nearest first. Moving down to a named child adds the node just left to the front of the trail.

Three moves, three ancestors remembered — in the order a rebuild will need them, nearest first. Nothing has been copied yet; this is pure navigation.

Going up: free, because it was already remembered

Going up is reading the front of the trail, not searching for a parent — the whole point of having written it down on the way in.

No comparison with the original tree, no re-walk from the root — the parent was sitting at the front of the trail the whole time.

Editing: rebuild on the way back up

The edit itself is ordinary: give the node in focus a new list of children. What happens next is the part worth watching. From A1, giving it a second child Y alongside X. The diagrams below mark the newly built node that is current amber, and any node built earlier in the same step but no longer current with a border.

Three new nodes — A1, A, Root — not five. A2 and B are untouched originals, reused as children of the new nodes around them rather than copied. And the old Root, A, A1 still exist, unchanged, pointed to by anything that was holding them before the edit — the edit built a new path to a new root; it did not touch the old one.

What goes wrong

• Expecting the focus to stay where the edit happened. It doesn't — an edit climbs the whole trail and lands on the new root, trail empty, same as if the zipper had just been created. Treat the return value as "a new tree," not "my cursor, still at A1."
• Assuming a step sideways is as cheap as a step up or down. This zipper's trail only remembers ancestors, not the siblings beside them. Moving to a different child means going up and back down by name or by condition, scanning that level's children — never a single "move right" step, because none is kept.
• Forgetting the old tree is still there. Nothing was mutated, so a reference taken before the edit still sees the pre-edit shape. That's the structural sharing working as intended, not a bug — but code that edits and then re-reads the original variable expecting to see its own change will not.

Where this is used

Rewriting an AST without arbitrary jumps: walk down into the tree to a jump that needs restructuring, turn it into a conditional block, climb back out — each climb rebuilding only the handful of ancestors on that one path, every sibling subtree reused untouched. An AST with thousands of nodes and one jump somewhere inside it rebuilds a few nodes per fix, not thousands.

References

1. G. Huet. "The Zipper." Journal of Functional Programming, 7(5), September 1997, pp. 549–554. Names and popularizes the data structure this page walks through.