Tree zippers

Read first: nothing — standalone

A tree that is never changed in place cannot give its nodes parent pointers: after an edit, an untouched node hangs under both the old parent and the new one. Without them, climbing up, or finding which ancestors an edit must rebuild, means walking down again from the root.

On this page's six-node tree, the zipper walks Root → A → A1 → X once and keeps the ancestors it passed, [A1, A, Root]. Stepping back up to A1 and giving it a new child Y both read that list instead of walking again; the edit rebuilds the 3 nodes on the path, adds Y, and reuses X, A2 and B.

Terms (current, trail, path copying, structural sharing) are defined where the walks first use them.

The example: one edit, three levels down

A small tree, four levels at its deepest. The goal is to reach X, step back up to its parent A1, and give A1 a second child Y:

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

The answer, with the old tree and the new one drawn together. The edit built the four amber nodes; X, A2 and B each now have two parents, one in each tree:

flowchart TD
    Root --> A
    Root --> B
    A --> A1
    A --> A2
    A1 --> X
    newRoot["new-Root"] --> newA["new-A"]
    newRoot --> B
    newA --> newA1["new-A1"]
    newA --> A2
    newA1 --> X
    newA1 --> Y
    class newRoot,newA,newA1,Y changed
    classDef changed fill:#f5b041,stroke:#f5b041,color:#000

Built by the edit (4)

Reused as they are (3)

The zipper behind it is a pair: current, the node in focus, and trail, the ancestors passed to get there, nearest first. This is the shape of NativeZipper, an experimental zipper in cobol-rekt's test sources, in this page's names (full source below):

down(child):
  Zipper(trail.prepend(current), child)

up():
  Zipper(trail.tail, trail.head)

replaceChildren(kids):
  edited = current.clone(kids)
  return up().replaceChild(current, edited)

replaceChild(old, new):
  copy = current.clone(children,
                       old → new)
  if trail empty: return Zipper([], copy)
  return up().replaceChild(current, copy)

And the four lines that produce the answer graph above. The walks below take them one at a time:

z = Zipper([], Root)
z = z.down(A).down(A1).down(X)
z = z.up()                   // at A1
z = z.replaceChildren([X, Y])
// current new-Root, trail []

@Getter
public class NativeZipper<T extends ZipperNode<T>> {
  private final List<T> thread;
  private final T current;

  public NativeZipper(List<T> thread, T current) {
    this.thread = thread;
    this.current = current;
  }

  public T current() {
    return current;
  }

  public NativeZipper<T> down(T child) {
    int childIndex = current.children().indexOf(child);
    if (childIndex == -1) return this;
    return new NativeZipper<>(thread.prepend(current), child);
  }

  public NativeZipper<T> down(Predicate<T> condition) {
    List<T> filtered = current.children().filter(condition);
    if (filtered.isEmpty()) return this;
    return down(filtered.head());
  }

  public NativeZipper<T> up() {
    if (thread.isEmpty()) return this;
    return new NativeZipper<>(thread.tail(), thread.head());
  }

  public NativeZipper<T> replaceChildren(List<T> newChildren) {
    return up().replaceChild(current, current.clone(current, newChildren));
  }

  private NativeZipper<T> replaceChild(T replacedChild, T replacingChild) {
    List<T> currentChildren = current.children();
    List<T> updatedChildren =
        currentChildren.update(currentChildren.indexOf(replacedChild), replacingChild);
    NativeZipper<T> upZipper = up();
    T nodeCopy = current.clone(current, updatedChildren);
    if (upZipper == this) return new NativeZipper<>(List.of(), nodeCopy);
    return upZipper.replaceChild(current, nodeCopy);
  }
}

Going down: the trail grows

The second fragment's down(A).down(A1).down(X), one call per step. In the diagrams, amber marks the node currently in focus; a bordered node is one remembered on the trail. Each down puts the node just left at the front of the trail.

Steps 1 to 3 made three moves and remembered three ancestors, in the order a rebuild will need them: the trail chips under step 3 read A1, A, Root, nearest first. Nothing has been copied yet; this is pure navigation.

Going up: free, because it was already remembered

The fragment's z.up(). Going up reads the front of the trail from step 3 above; it does not search for a parent.

Compare the trail chips with step 3 of the walk down: A1 moved from the front of the trail into current, and nothing else changed. No comparison with the original tree, no re-walk from the root.

Editing: rebuild on the way back up

The fragment's z.replaceChildren([X, Y]), from A1. The edit itself is ordinary: give the node in focus a new list of children. What happens next is the part worth watching. The diagrams below mark the newly built node that is current amber, and any node built earlier in the same walk but no longer current with a border.

Step 1 built new-A1 and new-A; step 2 built new-Root and emptied the trail:

Path copied, old → new

The original tree has six nodes. The edit built four: the three on the path — A1 and its ancestors A and Root, in the chips above — plus the new leaf Y, rather than copying all six. In step 2's diagram, A2, B and X are untouched originals, reused as children of the new nodes: structural sharing. Copying only the path to the root is path copying. Neither is the zipper's doing; any persistent tree edits this way. What the zipper adds is that the path was already on the trail, so no second walk from the root was needed. The old Root, A, A1 still exist, unchanged: they are the original tree in the answer graph at the top.

Why keep the trail

Look again at the answer graph at the top: X hangs under both A1 and new-A1. A node shared like that cannot carry a single parent pointer, so a tree that is never changed in place has none. The table counts the nodes visited for each of the example's three operations, with and without the trail:

The two amber cells are the walk down done a second and a third time, only to learn which nodes lie on the path. The zipper is what remembers the first walk, so there is no second one.

How Huet's zipper differs

The data structure in the walks above is a simplified, ancestor-trail variant of Huet's zipper.^[1] Huet's version keeps more at each level of its context: the parent path plus the focus's left and right siblings. At the edit's starting point (focus on A1, before step 1 of the edit walk) the two hold:

Those sibling lists make a step left or right O(1), make an edit at the focus O(1), and defer rebuilding — each up reassembles one level from its left siblings, the focus and its right siblings, and nothing is rebuilt until something moves up. The variant here keeps only the middle column and rebuilds eagerly: the edit walk climbs straight back to the root in its two steps. The idea both share — remember the way back up instead of re-walking it — is the one this page is about.

What goes wrong

Expecting the focus to stay where the edit happened. In this page's variant it doesn't (Huet's does, deferring the rebuild to up) — 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 variant's 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 variant's trail only remembers ancestors, not the siblings beside them. Moving from A1 to its sibling A2 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. Huet's zipper keeps exactly those sibling lists, which is what makes its sideways step O(1):

Forgetting the old tree is still there. Nothing was mutated, so a reference taken before the edit still sees the pre-edit shape. Reading A1's children through each root of the answer graph:

That's structural sharing — the old and new tree share all the nodes that didn't change, only the edited node and its ancestors are new — working as intended, not a bug. But code that edits and then re-reads the original variable expecting to see its own change gets the first row.

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 the example's shape of problem, row for row:

• A GOTO-elimination pass over a parsed COBOL program: walk down to a jump, turn it into a conditional block, climb back out. The next jump 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 meets the same problem at every control-flow fixup: thousands of nodes, a handful to rewrite, and the cost should follow the handful.
• "Just mutate the tree" is the wrong comparison: the zipper's saving is the amber cells under why keep the trail, not avoiding mutation. A tool that already knows its path back up because it just walked there is most of the way to a zipper.

Where this is used

Rewriting an immutable AST without arbitrary jumps, one jump at a time, as in the table above: the trail hands over the path, and path copying keeps the rebuild to the ancestors on it — a few nodes per fix, not thousands. cobol-rekt does not do this:

Its eliminating GOTOs pass mutates its tree in place, so it needs neither a trail nor path copying; a zipper is how the same edits could be made to an immutable one. Its zippers are ancestor-only: NativeZipper, in the full listing under the example, and BridgeZipper, the same design over its AST nodes — the variant this page walks through.

References

1. G. Huet. "The Zipper." Journal of Functional Programming, 7(5), September 1997, pp. 549–554. The original zipper, whose context stores sibling lists at every level; this page presents a simplified ancestor-only variant of it.