A declarative configuration template language gained recursion, and some renders never finish — how do you make evaluation safe?

seniorshould knowfreq 45%

answer

three ingredients arrived one release at a time
no static bound on arbitrary input
meter the run, do not analyse it
fuel, depth, output size, memory
deterministic failure beats a wall-clock timeout

basics

~20 s

Conditionals plus recursion plus arithmetic over unbounded values pushed the format into Turing completeness, so no inspection of a template bounds its evaluation. The fix is to bound the evaluator itself: a step budget, an expansion-depth cap and an output-size cap, enforced deterministically.

solid answer

~50 s

Feature by feature the format acquired the three ingredients of a complete model — a conditional, repetition nothing caps, and unbounded values. From that point, no analysis of a template text tells you how long an arbitrary render takes, so you stop trying to analyse and start metering. Give the evaluator a per-render step budget it decrements on every node, an expansion-depth cap for nested definitions, and caps on output size and on any collection it materialises. Make exhaustion a deterministic failure — the same template and inputs must fail the same way on every machine — rather than a wall-clock timeout, whose outcome depends on load. Then report the expansion path that consumed the budget, so the author can see which definition ran away, and, if the format is multi-tenant, meter per tenant so one template cannot starve the rest.

Feature by feature the format acquired the three ingredients of a complete model — a conditional, repetition nothing caps, and unbounded values. From that point, no analysis of a template text tells you how long an arbitrary render takes, so you stop trying to analyse and start **metering**. Give the evaluator a per-render **step budget** it decrements on every node, an **expansion-depth cap** for nested definitions, and caps on output size and on any collection it materialises. Make exhaustion a **deterministic** failure — the same template and inputs must fail the same way on every machine — rather than a wall-clock timeout, whose outcome depends on load. Then report the expansion path that consumed the budget, so the author can see which definition ran away, and, if the format is multi-tenant, meter per tenant so one template cannot starve the rest.

code

pseudocode · 22 lines

pseudocode

function eval(node, env, budget):
    if budget.steps <= 0:
        fail "step budget exhausted", trace(env)
    if budget.depth <= 0:
        fail "expansion depth exceeded", trace(env)
    budget.steps = budget.steps - 1

    if node is literal:
        return node.value

    if node is reference:
        return lookup(env, node.name)

    if node is call:
        args = empty list
        for each a in node.arguments:
            append(args, eval(a, env, budget))
        body = definition_of(node.name)
        budget.depth = budget.depth - 1
        result = eval(body, bind(body.parameters, args), budget)
        budget.depth = budget.depth + 1
        return result

go deeper

for a junior

Recall that a configuration format with recursion and computed values is a program, not data, and that a render can then run forever. The evaluator, not the reviewer, has to stop it.

for a middle

Explain which features combine into completeness and name the controls that bound an evaluator: a step budget decremented per node, an expansion-depth cap, and caps on output and collection size.

for a senior

Demonstrate the operational judgment: deterministic exhaustion over wall-clock timeouts, budgets sized from measured renders, an error that names the expansion path, and per-tenant metering so one runaway render costs one render.

for a principal

Own the consequence for the platform. Once evaluation is unbounded, caching, capacity planning and the promise you make about running untrusted content all change, and the budget becomes part of the format's contract rather than an implementation detail.

How a declarative format drifts across the line

No one decides to make a configuration format Turing complete. It happens one reasonable release at a time:

Substitution. Values get interpolated into a template. Evaluation is a single pass and its cost is proportional to the text.
Conditionals. A block should appear only in some environments. Evaluation now has branches, but still terminates: each node is visited at most once.
Reusable definitions. Users are copying blocks, so definitions become callable with parameters. Cost is still bounded if a definition cannot reach itself.
Recursion. Someone needs a nested structure of unknown depth, and the restriction against a definition using itself is lifted — often without anyone framing it as a language change.
Arithmetic on computed values. A counter can now be incremented and compared, and a definition can decide to call itself based on the result.

After step 5 the format has unbounded storage, a conditional and repetition nothing caps. Those are the three ingredients, and the format can now simulate an arbitrary machine. The symptom arrives later: a render that consumes a worker and never returns.

What is lost the moment it crosses

Any static bound on evaluation. Previously you could say a render costs no more than the template size times the data size. Now the specification imposes no bound at all, and no tool can compute one for an arbitrary input.
Review as a safety net. A runaway expansion is not visible in a diff. The recursive definition looks like every other definition; only the inputs decide whether it terminates.
Safe evaluation of untrusted content. A template supplied by a tenant, a customer or a pull request is now a program you are agreeing to run.
Predictable cost accounting. Caching, pre-computation and capacity estimates all assumed a cost proportional to input size.

Note what is not lost: parsing is unaffected. The grammar of a loop or a recursive call is ordinary; the change is in evaluation, not in syntax. A candidate who reaches for the parser here has misplaced the problem.

Bounding an evaluator you can no longer analyse

Since you cannot decide the question by inspection, meter the run:

Control	What it bounds	What it misses on its own
Step budget (fuel)	total evaluation work	a single step that allocates hugely
Expansion-depth cap	nesting of definitions	wide recursion that is shallow but enormous
Output-size cap	the result actually produced	work that produces nothing before failing
Collection-size cap	any list or map built during evaluation	scalar blow-ups such as repeated doubling
Memory ceiling	the whole evaluation's footprint	slow, small, endless loops

None of them is sufficient alone, which is why real evaluators carry several. The step budget is the backbone: a counter decremented on every evaluation step, checked before the work is done, failing the render when it reaches zero.

Make the failure deterministic

A wall-clock timeout is the tempting single control and the weakest one. Its outcome depends on machine load, so the same template and inputs can succeed on a quiet host and fail on a busy one. That is unusable: authors cannot reproduce it, tests are flaky, and a retry looks like it fixed something. A step budget makes the outcome a function of the input, so a template that renders in continuous integration renders in production, and one that fails does so identically everywhere. Keep a wall-clock deadline as the outer backstop for the cases the counters miss, but never as the primary bound.

Make the failure legible

An exhausted budget must say more than "too complex". Report:

the definition chain that was expanding when the budget ran out, deepest frames first;
how much budget each level of the chain consumed;
the input value that drove the recursion, when it can be identified.

Without this, the author's only move is to guess and re-run, and the guess is usually "raise the limit".

What not to do

Do not raise the stack size and call it fixed. That changes which templates fail, not whether unbounded ones exist.
Do not let a template raise its own budget. A bound a program can lift is not a bound.
Do not rely on a review rule that says templates should not recurse deeply; nothing enforces it and nobody can see it.
Do not evaluate untrusted templates in-process with the request path. Give them their own bounded execution and a per-tenant quota, so one runaway render costs one render.

## How a declarative format drifts across the line No one decides to make a configuration format Turing complete. It happens one reasonable release at a time: 1. **Substitution.** Values get interpolated into a template. Evaluation is a single pass and its cost is proportional to the text. 2. **Conditionals.** A block should appear only in some environments. Evaluation now has branches, but still terminates: each node is visited at most once. 3. **Reusable definitions.** Users are copying blocks, so definitions become callable with parameters. Cost is still bounded if a definition cannot reach itself. 4. **Recursion.** Someone needs a nested structure of unknown depth, and the restriction against a definition using itself is lifted — often without anyone framing it as a language change. 5. **Arithmetic on computed values.** A counter can now be incremented and compared, and a definition can decide to call itself based on the result. After step 5 the format has unbounded storage, a conditional and repetition nothing caps. Those are the three ingredients, and the format can now simulate an arbitrary machine. The symptom arrives later: a render that consumes a worker and never returns. ## What is lost the moment it crosses - **Any static bound on evaluation.** Previously you could say a render costs no more than the template size times the data size. Now the specification imposes no bound at all, and no tool can compute one for an arbitrary input. - **Review as a safety net.** A runaway expansion is not visible in a diff. The recursive definition looks like every other definition; only the inputs decide whether it terminates. - **Safe evaluation of untrusted content.** A template supplied by a tenant, a customer or a pull request is now a program you are agreeing to run. - **Predictable cost accounting.** Caching, pre-computation and capacity estimates all assumed a cost proportional to input size. Note what is *not* lost: parsing is unaffected. The grammar of a loop or a recursive call is ordinary; the change is in evaluation, not in syntax. A candidate who reaches for the parser here has misplaced the problem. ## Bounding an evaluator you can no longer analyse Since you cannot decide the question by inspection, meter the run: | Control | What it bounds | What it misses on its own | |---|---|---| | Step budget (fuel) | total evaluation work | a single step that allocates hugely | | Expansion-depth cap | nesting of definitions | wide recursion that is shallow but enormous | | Output-size cap | the result actually produced | work that produces nothing before failing | | Collection-size cap | any list or map built during evaluation | scalar blow-ups such as repeated doubling | | Memory ceiling | the whole evaluation's footprint | slow, small, endless loops | None of them is sufficient alone, which is why real evaluators carry several. The step budget is the backbone: a counter decremented on every evaluation step, checked before the work is done, failing the render when it reaches zero. ## Make the failure deterministic A wall-clock timeout is the tempting single control and the weakest one. Its outcome depends on machine load, so the same template and inputs can succeed on a quiet host and fail on a busy one. That is unusable: authors cannot reproduce it, tests are flaky, and a retry looks like it fixed something. A step budget makes the outcome a **function of the input**, so a template that renders in continuous integration renders in production, and one that fails does so identically everywhere. Keep a wall-clock deadline as the outer backstop for the cases the counters miss, but never as the primary bound. ## Make the failure legible An exhausted budget must say more than "too complex". Report: - the definition chain that was expanding when the budget ran out, deepest frames first; - how much budget each level of the chain consumed; - the input value that drove the recursion, when it can be identified. Without this, the author's only move is to guess and re-run, and the guess is usually "raise the limit". ## What not to do - **Do not raise the stack size** and call it fixed. That changes which templates fail, not whether unbounded ones exist. - **Do not let a template raise its own budget.** A bound a program can lift is not a bound. - **Do not rely on a review rule** that says templates should not recurse deeply; nothing enforces it and nobody can see it. - **Do not evaluate untrusted templates in-process with the request path.** Give them their own bounded execution and a per-tenant quota, so one runaway render costs one render.

How do you pick the size of the step budget?
Measure, do not guess: instrument the evaluator, collect the step count of real renders, and set the budget well above the observed tail — often an order of magnitude — so ordinary growth never trips it. Then treat exhaustion as a signal worth reading rather than a number to raise, and alert on renders that come close, because those are the ones that will break next.
Why is a wall-clock timeout a weaker bound than a step budget?
Its outcome depends on machine load rather than on the input, so the same template can pass on one host and fail on another, and a retry can appear to fix it. A step budget makes success a function of the template and its inputs, which is reproducible in tests and in production. Keep the clock as an outer backstop only.
Does catching a stack overflow count as a depth cap?
No. It fires at whatever depth the execution stack happens to allow, which varies with build, platform and the shape of the frames, so the same template can fail inconsistently. It also unwinds from an unreliable state and gives the author no expansion path. An explicit counter checked before each expansion is deterministic and can report where the depth went.

saying these in an interview costs you the question

Says a timeout is enough because hung renders eventually get killed
Believes reviewing the template by eye catches the non-terminating ones
Raises the stack size instead of bounding how much work a render may do
Lets a template configure its own evaluation limits
Claims the format is still declarative because it has no loop keyword
Blames the parser for a runaway expansion that happens during evaluation

A declarative configuration template language gained recursion, and some renders never finish — how do you make evaluation safe?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

How a declarative format drifts across the line

What is lost the moment it crosses

Bounding an evaluator you can no longer analyse

Make the failure deterministic

Make the failure legible

What not to do

▾common follow-ups3 questions

▾red flags6 flags

How a declarative format drifts across the line

What is lost the moment it crosses

Bounding an evaluator you can no longer analyse

Make the failure deterministic

Make the failure legible

What not to do

answer

go deeper