# Resource limits

A validator runs against untrusted values, so every recursive descent and every error-reporting probe is bounded. A pathological input meets a gated limit and is rejected cleanly; on a thread with the stack its platform gives one, it never overflows the native stack, and a Python `RecursionError` comes only from the value's own code: a `__repr__`, an `__eq__` or a predicate that recurses past the interpreter's limit raises one, or that re-enters a validator until the thread's stack runs short ([re-entry](<https://ppigazzini.github.io/valgebra/explanation/boundaries/index.md#your-code-runs-inside-the-check-and-may-call-back-in>)), and it propagates as every fatal signal does ([when a comparison raises](<https://ppigazzini.github.io/valgebra/guides/error-model/index.md#when-a-comparison-raises>)). On PyPy under a lowered recursion limit the explaining walk's own rendering can raise one too (the value-walk depth entry below). The bounds cap sizes, not time: [what the bounds do not bound](<#what-the-bounds-do-not-bound>) names the inputs whose cost grows inside them. The limits bound work driven by the *value* — the untrusted part. A schema's own size (the width of a union, the number of declared fields) is written by the developer and is trusted.

## The bounds

- **Schema build depth.** The frontend descends at most one level past the construction bound while compiling (`MAX_BUILD_DEPTH` in `crates/valgebra-py/src/build.rs`) and refuses anything deeper with the `ValueError` the construction bound below raises, whether or not it reaches a leaf: an annotation exactly one level too deep is refused by that bound, and a deeper one meets the frontend's first, with the same type. A self-referential class does not get there: it is refused with `NotImplementedError` where it is reached again while its own fields are being built, under the type arguments it is applied to and with no `type` alias opened since, because its field type names the class and the build never bottoms out; model it with [`recursive`](<https://ppigazzini.github.io/valgebra/guides/recursion/index.md>) instead. An alias opened since ties the cycle where the fields reach it again ([recursion](<https://ppigazzini.github.io/valgebra/guides/recursion/index.md#why-classes-need-it>)).
- **Schema construction size.** Every way of growing a schema — the `Validator` constructor, the `|` operator, `union`, `intersection`, `complement`, `recursive`, and the record transforms — is bounded at construction, so no sequence of calls can build a schema that overflows the stack or exhausts memory on a later walk. Three bounds apply, and passing any one raises `ValueError`:

  - **depth** — at most `MAX_SCHEMA_DEPTH` levels of structural nesting, 128 (a chain built in a loop, such as repeatedly wrapping a validator in a list or a set; a union of unions flattens and adds no level). Every node counts one level, containers and the leaf they end in included, so 127 nested lists around an `int` are the deepest chain it admits and the 128th list is refused. A refinement counts one more on top of whatever it narrows, since the set it denotes is a node of its own: pinning a length on each list of such a chain admits 63 refined lists and refuses the 64th. Which marker the refinement carries makes no difference — the level belongs to the node;
  - **definitions** — at most 128 recursive definitions (a chain of distinct `recursive` schemas, which the depth measure alone cannot see because a back edge counts as a leaf);
  - **nodes** — at most 100,000 total schema nodes (a shallow but exponentially wide schema, such as a loop putting a validator twice in one container, `Validator([v, v])`, which doubles its node count each step; `v | v` folds to `v`). The constructor holds it while it reads: a class, an alias or any annotation object is built once per place it is named, so a part shared through several levels multiplies the schema's size with each, and the frontend refuses at the step after the one that passes the bound rather than building the rest. It counts what it holds, and a part a fold drops -- a member a union absorbs into `Any` -- still counts toward the union that dropped it. What a marker or a class yields is read the same way, item by item: a grouped marker's constraints, a protocol's members, a named tuple's fields and a `TypedDict`'s required keys are refused past 100,000 items, so one that never ends is refused rather than read until memory ends.

A real schema stays far under all three. Structural recursion belongs in [`recursive`](<https://ppigazzini.github.io/valgebra/guides/recursion/index.md>), whose back edge does not count toward the depth.

The three numbers are importable, so code that sizes a schema against them reads them rather than repeating them.

```
from valgebra import MAX_DEFINITIONS, MAX_SCHEMA_DEPTH, MAX_SCHEMA_NODES

assert (MAX_SCHEMA_DEPTH, MAX_DEFINITIONS, MAX_SCHEMA_NODES) == (128, 128, 100_000)
```

\- **Pattern size.** A `Regex` the walk runs compiles to a program of at most 32 MiB (`PATTERN_SIZE_LIMIT` in `crates/valgebra-py/src/check/index.rs`), three times the `regex` crate's default, and a pattern past it is refused where the schema is built. A counted Unicode class is what reaches it: the class is copied once a repetition, so `\w{1,255}` keeps 14 MiB and builds in about 150 ms, and `\w{1,1000}` is refused. A validator keeps what its patterns compiled to for as long as it lives, so the patterns of one validator are held to 256 MiB together (`PATTERNS_HELD`), eight programs at the one pattern's bound, each text counted once: a record of sixteen `^[\w.-]{1,n}$` fields keeps 43 MB, and eighteen `\w{1,255}` fit while a nineteenth is refused where the schema is built, in one call or combined from validators holding some each. Validators holding one text hold one program, so a meet, a union or a complement built from a validator adds none, and a program lives while a validator holding it does. Memory a program cannot be given ends the process rather than raising `MemoryError`: the allocation fails in Rust, whose failure aborts. An ASCII class, `(?-u)\w`, is a three-hundredth of the Unicode one. - **Value-walk depth.** Two bounds hold the walk inside the stack, and reaching either fails with `recursion_limit`: at most 128 levels of **recursive unfolding**, and at most 384 levels of **descent** in total. The second is what binds for a deep definition, because a recursive definition descends its whole body once per level of the value — so the frames a value can ask for are the product of the two, not either one. The smallest recursive body, a reference under a union around one container such as `recursive(lambda t: union(int,   [t]))`, opens three levels an unfolding, so it is walked to the unfolding bound: 127 lists nested around an `int` are a member, the `int` being the 128th unfolding, and 128 lists are refused.

```
The walk fits a **1 MiB** thread stack, the least any thread CPython
```

creates has. The CPython wheels for glibc Linux, macOS and Windows x64 are built with profile-guided optimization, whose inlining makes a level cost 2.5 to 3 KiB on the dict and union shapes, and the dearest walk, explaining a value refused at the bound, needs between 828 and 844 KiB on the CPython 3.12 wheel; the musllinux, Windows arm64 and PyPy wheels are plain builds, without the profile's inlining. The release smoke runs the deepest walks on a 1 MiB thread on every wheel it ships. A thread given less can run out before the bound does, and the process ends with it; a thread an embedding host starts at the 512 KiB pthread default on macOS is one. Give a thread that validates deep values 1 MiB or more. This holds on both the object path and the JSON path; an over-deep JSON document is rejected by the parser as `json_invalid`.

```
On PyPy the stack is also the interpreter's to size: PyPy lets its C-API
```

calls use a stack it scales by the recursion limit, `sys.setrecursionlimit` included, and a call past it fails in a way PyPy cannot report, ending the process. So on PyPy a level the walk opens a step deeper than before asks PyPy's own check whether 12 KiB below it are still free, and where they are not the walk refuses at `recursion_limit`, as at its bounds. Under the default limit the bounds come first. Under a limit lowered to a few hundred or below the walk can stop short of them, at a depth its own frames decide, so `is_valid` and the explaining `validate`, whose frames are larger, can stop at different depths and name different reasons; there the explaining walk's rendering, which is Python, can raise `RecursionError`, which propagates. A limit below about 37 leaves PyPy too little stack to run the walk at all.

```
The parser has a bound of its own — a couple of hundred levels of arrays and
objects — and it sits **between** the two: wider than the unfolding bound and
narrower than the descent one. A document therefore has three regions rather
than two. Inside the unfolding bound it is a member. Past it and inside the
parser's, the walk is what refuses, and the code is `recursion_limit`. Past
the parser's, the text stops being a document before the walk sees it, and
the code is `json_invalid`. The descent bound is not reachable through a
document at all, because the parser refuses first — it binds on the object
path, where there is no parser. `tests/test_adversarial_bounds.py` holds the
three regions and their order, which is what keeps this paragraph a
description of the tree rather than of two numbers that have since moved
past each other.
```

- **Relation depth.** A relation -- `relation_to`, `is_subtype_of`, `is_equivalent`, `is_empty` -- holds at most 512 levels of its own recursion, and past them answers undecided, which a relation may always answer. Two recursive schemas whose bodies nest 100 and 99 lists around the back edge prove nothing about each other until the two cycles realign, 9,900 levels down; a long chain of definitions asks its emptiness as deep, and a product split across a wide union takes a level for each branch it narrows by -- without the bound each would outrun the stack. A level costs about 1 KiB on the shipped wheels, so the deepest relation fits in half of a 1 MiB thread, and the release smoke runs it there. Two chains of definitions, each `recursive(lambda t: union(previous, list[t]))`, are told apart up to 21 links and answer undecided from 22, within the 128 a schema may hold, in about a tenth of a second at 22 links and a third at 64.
- **Comparison depth.** `==` reads two definition tables numbered in one order index for index, as deep as one tree. Numbered apart, it pairs the definitions in the order construction numbered them and reads a body inside another only where a definition names one it is nested in, so a tower of fixpoints each naming the one around it adds up its bodies' depths. It holds at most 384 levels open and opens at most four times the node bound in all, and past either answers `False` -- two schemas, the direction it errs in -- where `is_equivalent` still answers the set question. Composing two such validators appends what it could not place, so their union holds both copies. Held at the bound, a comparison takes about 460 KiB of stack on the shipped wheels, inside a 1 MiB thread.
- **Self-reference.** A value that contains itself is caught by an object-identity guard and fails with `recursion_loop` rather than looping forever.
- **Union error reporting.** When a value misses a wide union, the error report is bounded in two independent ways: it searches only a bounded number of branches for the closest match, and `expected` names only a bounded number of **labels** before truncating with `...`, and renders none past them, so a constant's `repr` runs for the labels named and no others. The two counts differ — a branch that is itself a union, such as a wide `Literal[...]`, contributes one branch and many labels — so each carries its own bound. With `fail_fast` the explanation costs a deciding walk of each branch and a fail-fast walk of each branch it searches, whatever the size of the value. Without it every failure of the chosen branch is reported, so the report grows with the value; a service answering untrusted input with the report asks for it with `fail_fast`. A meet reports each member's failures, so where two members read one child the report names the child's failures once per member, and doubles with each level of the value that does: `recursive(lambda t: union(int, intersection(list[t], list[union(t, str)])))` reports 4,096 failures for a refused list nested twelve deep, and one with `fail_fast`.

## What the bounds do not bound

Each bound above caps a size -- a depth, a count of nodes, of definitions or of decision steps. None caps time, and four costs grow inside them:

- **A value is walked as a tree.** The identity guard is a loop guard on the current path, so a sub-object reached by two paths is walked once per path. `x = [x, x]` repeated twenty times is twenty lists and a million paths to the value at the bottom, and each level of sharing doubles the walk. A JSON document cannot share a sub-object; a value built in Python, unpickled or loaded from a YAML document with aliases can.
- **A definition that runs your code is walked once per member that reaches it.** Two branches of a union, two members of a meet or two clauses of a map can read one value as one recursive definition: `recursive(lambda t:   union(int, [t], [union(t, str)]))` reads a list's element as `t` under both list branches. The walk keeps what it answered for the definition at that value, for the call, and the next member finds it there, so the walk is linear in the value on every entry point, a JSON document and the walk a `complement` reads included. A definition that reaches a predicate, or a class whose metaclass is not `type`, is not kept: the walk calls that code at each occurrence it reaches ([refinements](<https://ppigazzini.github.io/valgebra/guides/refinements/index.md>)), so each level of the value is walked once per such member, and the time doubles with the depth. Keep the predicate outside the definition, or write the branches so one value enters one of them. A value nested past the bounds is reached by each path to it with its own room -- the walk levels open and the definitions unfolded -- and walked once for each, at most the product of the two bounds per definition and value, where a value inside them on every path is walked once. An answer kept is found by a member with as much of each bound left as the walk that kept it used, so sharing moves no answer: a value holding one sub-object at two depths answers as the same value sharing nothing does.
- **A relation's budget counts steps, not their size.** A query spends at most a million decision steps an asking, and one that ends undecided at a smaller allowance inside that budget, with steps of its own left, is asked once more under a million of its own, so at most two million in all. A step whose work is linear in a leaf it reads is one step whatever the leaf holds. So a relation over a large leaf costs time in proportion to it inside the budget: `Annotated[int, Ge(0)]` against a union of thousands of literals grows with the square of their number before it answers undecided. What the set representation builds is held by size as well -- an automaton to 4,096 states, a pattern's table to the bytes that takes, a `MultipleOf`'s table and a product of two automata by the entries each holds -- and a length bound is refused before it is built where no table of that many states could count to it, so `Annotated[str, MinLen(1_000_000)]` against another bound answers at once instead of unrolling a million copies of a code point.
- **A walk does not stop for a signal.** No walk or relation asks the interpreter for pending signals, so a `KeyboardInterrupt` raised while one runs arrives when it returns. Asking would cost every element of every walk to serve the shapes above, which a service bounds by what it accepts: a document's size, a decoder without aliases, a schema it wrote.

Nor does any bound cap memory, and where memory runs out a call does not always raise `MemoryError`:

- **Python's allocator refusing inside the extension raises `MemoryError`.** Where valgebra builds a Python object -- a schema's, a report's, a parsed document's, a relation's -- and the interpreter cannot give it memory, the call raises `MemoryError` as the same refusal in Python does, and no answer moves: a refusal ends the call it meets.
- **A JSON document is parsed in Rust, and a parse given no memory ends the process.** `is_valid_json` holds the parsed tree, about sixteen times the text for an array of numbers and thirty-nine times for an array of small objects, and `load` and `validate_json` build their Python values beside it; a Rust allocation that fails aborts, where `json.loads` raises `MemoryError`. pydantic's `validate_json` ends the process or panics on the same documents under the same caps. Bound a document's size before handing it to valgebra, as a service bounds what it accepts.
- **Every allocation in Rust that fails ends the process.** The two above are where a size the caller writes reaches one; building a validator, deciding a relation and writing a report allocate in Rust too, and under a memory limit (`RLIMIT_AS`) a failure in any of them aborts rather than raising `MemoryError`. What a walk hands back to Python is allocated by Python and raises `MemoryError` there. Bound the memory a process is given knowing it ends rather than raises.
- **A report grows with the value, and each failure in it is bounded.** `validate` collects every failure, so a refused value of a million elements builds a million violations; `fail_fast=True` collects one. A failure's message writes at most eighty characters of the value and of each key on its path, and the failures under one key share its string in `errors`, so a document of one long key over many failures reports in its failures' count rather than in their product with the key. A summary is rendered under a bound for a `list`, `tuple`, `dict`, `set` or `frozenset` of exactly that type, and from its head for a `str`, `bytes` or `bytearray`. Any other value -- a subclass of those, a `deque`, an `array`, a `Decimal`, a class with a `__repr__` of its own -- is rendered whole and then cut, once per failure it stands at, so a large one held many times in a refused value pays its render each time; `fail_fast` pays it once.

## Rejection is clean, not catastrophic

```
from valgebra import ValidationError, Validator, recursive, union

schema = Validator(recursive(lambda j: union(int, [j])))

# A value nested far past the walk depth: a clean error, not a crash.
deep: object = 0
for _ in range(5000):
    deep = [deep]
assert not schema.is_valid(deep)
raised = False
try:
    schema.validate(deep)
except ValidationError as error:
    raised = True
    assert error.code == "recursion_limit"
assert raised

# A value that contains itself: caught as a loop.
cyclic: list[object] = []
cyclic.append(cyclic)
assert not schema.is_valid(cyclic)

# An over-deep JSON document: rejected by the parser.
assert not schema.is_valid_json("[" * 5000 + "1" + "]" * 5000)
```

Growing a schema in an unbounded loop is stopped at construction, before the growing schema can overflow the stack or exhaust memory on its next check:

```
from valgebra import Validator

composed: Validator = Validator(int)
raised = False
try:
    for _ in range(1000):
        composed = Validator([composed])
except ValueError as error:
    raised = True
    assert "too deep" in str(error)
assert raised
```

And so is reading one annotation whose parts are shared, before the tree it names is built -- the level below named twice, twenty times over, is a tree of two million nodes:

```
import types

from valgebra import Validator

shared: object = int
for _ in range(20):
    shared = types.GenericAlias(tuple, (shared, shared))  # tuple[shared, shared]
refused = False
try:
    Validator(shared)
except ValueError as error:
    refused = True
    assert "too large" in str(error)
assert refused
```

The worst-case timing of these shapes is measured by the adversarial benchmark and the bounds are correctness-tested, so each limit is an enforced, exercised guarantee rather than a comment.
