Skip to content

Tear down child nodes iteratively to avoid deep-tree stack overflow#396

Merged
aehlke merged 1 commit into
scinfu:masterfrom
rursache:fix/deep-tree-teardown-stack-overflow
May 15, 2026
Merged

Tear down child nodes iteratively to avoid deep-tree stack overflow#396
aehlke merged 1 commit into
scinfu:masterfrom
rursache:fix/deep-tree-teardown-stack-overflow

Conversation

@rursache

Copy link
Copy Markdown
Collaborator

Closes #393.

Problem

Node.childNodes is a strong-reference Array<Node>. When a node's refcount reaches zero, the default ARC release chain is:

Node.deinit -> release childNodes -> child Node.deinit -> release childNodes -> ...

That recurses once per HTML nesting level. Real-world pages routinely exceed 10k levels of nesting, which overflows the smaller stacks of non-main threads (Swift cooperative-pool workers, GCD workers, explicit Threads). The result is an EXC_BAD_ACCESS crash on Document teardown or Element.empty() when the work happens off the main thread. Element.empty() hits the same recursive release through its childNodes.removeAll().

Fix

Add a Node.deinit that unwinds the subtree iteratively instead of recursively:

  • Children are drained onto a work stack.
  • A popped node held only by the stack (isKnownUniquelyReferenced) is about to deinit anyway, so its own children are hoisted onto the stack and its childNodes cleared before it is dropped. It then deinits with an already-empty childNodes, so the chain never nests.
  • Nodes still referenced elsewhere (e.g. handed out via Elements, selector caches, or held by the caller) are left fully intact.

This keeps stack depth bounded regardless of nesting depth, and is behaviourally identical to the default recursive release - it only changes the order of unwinding, not which nodes get freed. Element.empty() needs no change of its own: once the deinit hook is in place, the children it releases tear down iteratively too.

Testing

  • New StackOverflow393Test runs teardown on a Thread with a deliberately small 512 KB stack:
    • testShallowOnSmallStackSurvives - control: shallow tree on a small stack.
    • testDeepOnMainThreadSurvives - control: deep tree (12k levels) on the main thread's large stack.
    • testDeepTeardownOnSmallStackSurvives - regression: deep tree released on a small-stack thread. Crashed with EXC_BAD_ACCESS / SIGBUS before the fix.
    • testDeepEmptyOnSmallStackSurvives - regression: same shape via Element.empty() on a uniquely-held deep subtree.
  • All four pass with the fix; the two regression tests hard-crashed the test process (SIGBUS) without it.
  • Full existing suite: 650/650 pass, no regressions.

Node.childNodes holds strong references, so the default ARC release chain
(Node.deinit -> release childNodes -> child Node.deinit -> ...) recurses
once per nesting level. Deeply nested HTML overflows small thread stacks
(Swift cooperative-pool workers, GCD workers, explicit Threads), crashing
with EXC_BAD_ACCESS on Document teardown or Element.empty().

Add a Node.deinit that unwinds the subtree iteratively: children are
drained onto a work stack, and a popped node held only by the stack
(isKnownUniquelyReferenced) has its own children hoisted and its
childNodes cleared before it is dropped, so it deinits with an empty
childNodes and the chain never nests. Nodes still referenced elsewhere
are left fully intact, making this behaviourally identical to the
default recursive release.

Adds StackOverflow393Test covering deep teardown and Element.empty() on
a small-stack thread, plus shallow and main-thread controls.

Closes scinfu#393

@aehlke aehlke left a comment

Copy link
Copy Markdown
Collaborator

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Thanks as always

@aehlke aehlke merged commit 98537b5 into scinfu:master May 15, 2026
3 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Stack overflow on deeply-nested HTML during Document teardown / Element.empty() on small-stack threads

2 participants