Why does a byte-size cap on a request body fail to protect a recursive-descent decoder from deeply nested input?
answer
- different currencies, terrible exchange rate
- one byte buys one level
- frames, not bytes, run out first
- counter tested before the recursive call
- real documents nest under thirty levels
basics
~20 sA byte is cheap and a stack frame is not: a megabyte of opening brackets is about a million nesting levels, and a decoder that recurses per level exhausts its stack long before it exhausts that input. Depth needs its own ceiling.
solid answer
~50 sThe two ceilings measure different things. A byte cap bounds how much input arrives; nesting depth bounds how much *structure* that input describes, and the exchange rate between them is terrible. One byte of opening bracket buys one level, so a body under a megabyte reaches roughly a million levels, while a thread's stack holds orders of magnitude fewer parser frames. The decoder runs out of stack first, and stack exhaustion is not a recoverable error you can catch and carry on from: the thread is left in an unclear state and whatever it held is in question. The fix is a separate counter incremented on entry to each nested value and tested **before** recursing, with a cap in the low hundreds — real documents rarely nest past twenty or thirty. Rejecting at that counter is a clean parse error at a point you chose.
code
pseudocode · 18 linesfunction parse_value(depth):
if depth > MAX_DEPTH:
reject("nesting deeper than MAX_DEPTH")
token = next_token()
if token is array_start:
while not peek_is(array_end):
parse_value(depth + 1)
consume(array_end)
else if token is object_start:
while not peek_is(object_end):
parse_key()
parse_value(depth + 1)
consume(object_end)
else:
return scalar_of(token)
parse_value(depth = 0)go deeper
Recall that a small document can still be extremely deeply nested, and that decoders need an explicit limit on how deep they will go.
Explain why one byte buys one level while a stack frame costs far more, and where the depth counter is tested relative to the recursive call.
Argue why catching stack exhaustion is not a defence, what an iterative parser does and does not fix, and how you picked the cap from measured traffic.
Decide what depth the platform permits by default, how a team justifies an exception, and how the limit is surfaced to callers so it does not become a silent breakage.
## Two ceilings that measure different things A request-body byte cap answers *how much did the sender transmit?* A nesting-depth cap answers *how much structure did the sender ask me to build, one level inside another?* Both are decode ceilings, and neither implies the other. What makes depth dangerous is the exchange rate. In a text encoding, one level of nesting costs a single opening character. So a body of 1 MiB — a limit most endpoints would consider tight — describes about 1,048,576 levels of nesting. In a binary encoding with a one-byte container tag the arithmetic is the same. Compressed input makes it far worse still, since a run of identical opening characters is the single most compressible thing there is. ## What actually runs out A recursive-descent decoder calls itself once per level. Each call places a frame on the thread's stack holding its locals, its return address and its bookkeeping. Thread stacks are fixed and small compared with the heap, and frames cost tens to hundreds of bytes, so a thread holds thousands to tens of thousands of parser frames — orders of magnitude short of a million. The consequence is not a rejected request. It is stack exhaustion, and that has three properties which make it much worse than an ordinary error: - It arrives at an arbitrary point in the parse, wherever the stack happened to run out. - Recovering from it is unreliable: ecosystems differ in whether it is catchable at all, and in what state the thread is left in when it is. - The thread that dies may hold locks, connections or partially updated state that nothing else knows to clean up. Catching the error and continuing to serve is therefore not a defence; it is a guess about what the thread was holding. ## Where the counter goes The ceiling is a depth parameter carried through the parse and tested **on entry to each nested value, before recursing**: 1. Enter a value at depth `d`. 2. If `d` exceeds the cap, abort with a structural parse error. 3. Otherwise, parse this value, recursing into its children at `d + 1`. Testing on entry, before the recursive call, is what keeps the check ahead of the cost. Testing at the end of the parse, or after building the tree, has the same failure as every other post-hoc ceiling: the work was done before the check ran. ## An iterative parser is not a fix A decoder that keeps an explicit stack on the heap instead of recursing moves the failure rather than removing it. The heap is larger, so it survives longer, but a million pending containers is still a million entries of bookkeeping plus the partially built structure hanging off them. Worse, the deep structure then **exists**, and everything downstream of the parse may recurse over it: a validator walking it, a serializer writing it back out, and in many ecosystems the teardown that releases it. A depth ceiling protects all of those; converting the parser to an explicit stack protects only the parser. ## Choosing the number Measure real traffic. Legitimate documents on a typical endpoint nest under twenty levels; a deeply generic one might reach thirty or forty. A cap in the low hundreds therefore leaves generous headroom while remaining thousands of times below anything that threatens a stack. Two practical notes: - Publish the cap in the API documentation, and return a clear structural error naming *depth* as the reason, so a caller who trips it can act rather than guess. - Count breaches per caller. A cap nobody legitimately reaches produces a flat zero, which makes any spike meaningful on sight. ## What this looks like in an interview The answer that lands is the exchange-rate observation: input size and structural depth are different currencies, and the conversion between them is about one byte per level, so any byte cap you would actually deploy still permits a depth no decoder survives. Everything else — the separate counter, the check before recursion, the low-hundreds cap — follows from that single sentence.
- What is a sensible maximum nesting depth for a general document endpoint?Measure first: legitimate traffic on most endpoints stays under twenty levels, and a broadly generic document might reach thirty or forty. A cap in the low hundreds gives ample headroom while sitting thousands of times below anything a stack cannot absorb. The wrong way to choose is a large round number nobody measured, since that reintroduces the failure it was meant to prevent.
- Does an iterative decoder with an explicit heap stack remove the need for the cap?No. It moves the growth from the thread stack to the heap, which survives longer but is still unbounded. And the deep structure now exists, so anything that later walks it — a validator, a serializer writing it back out, the teardown that releases it — may recurse to the same depth. The cap protects all of those; the rewrite protects only the parser.
- Why is catching the stack-exhaustion error not an acceptable defence?Because it fires at an arbitrary point in the parse, ecosystems differ in whether it can be caught at all, and the thread may have been holding a lock, a connection or half-updated state when it died. You are left guessing about invariants rather than rejecting a request. The depth counter fails at a point you chose, with nothing in flight.
saying these in an interview costs you the question
- Thinks a body-size cap implies a useful depth bound
- Catches the stack-exhaustion error and treats it as handled
- Assumes real documents legitimately nest hundreds of levels deep
- Believes an iterative parser removes the need for a depth ceiling
- Forgets that validating or tearing down the structure recurses too
- Checks depth after the document has been parsed