Advanced

Recursion inside async

A state machine lives on the heap when it is spawned, but a recursive async function builds a machine per frame. The size of the machine is the size of the stack, and the stack has no owner.

What you will see

One line naming the input. The limit is about an input, so the input is named.

About 1 min of reading

Try It

Bound the depth of a walk

Write the pending steps

printf 'a\nb\nc\n' > /tmp/q.txt; wc -l < /tmp/q.txt

Before you run it, say out loud what it will print. Then open the answer.

What it prints

3. The pending count is the depth, and the count is a number you can print.

Check the limit

awk 'BEGIN {d=64; if (d>32) print "refuse"; else print "walk"}'

Before you run it, say out loud what it will print. Then open the answer.

What it prints

refuse. The limit is checked before the walk, not after the overflow.

Stamp the limit

printf 'max_depth 32 input=tree.json\n' > /tmp/d.txt; cat /tmp/d.txt

Before you run it, say out loud what it will print. Then open the answer.

What it prints

One line naming the input. The limit is about an input, so the input is named.

Data Flow

A recursive call to a loop

1 The function returns a step instead of calling

↓

2 The loop holds the pending steps

↓

3 The pending count is the depth

↓

4 The count is checked against a limit

Why this works

Why the input decides the depth

The shape walked is the shape given. An input written by a user is an input that can be deep on purpose.

The visible symptom

A stack overflow in a worker thread. The symptom names the depth, and the depth names the input.

Examples

The machine is inline

A recursive async function cannot know its depth. The compiler cannot size the machine, so it nests.

The trampoline is the fix

Return the next step instead of calling. The loop becomes the stack, and the loop has a size.

Why depth is a number

A tree walk has a depth. A depth that is not measured is a depth that can be reached by an input.

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← One flat memory, two owners

Previous Lesson

One flat memory, two owners

Next Lesson

Send and Sync are the contract

Send and Sync are the contract →