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), and it
propagates as every fatal signal does
(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 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_DEPTHincrates/valgebra-py/src/build.rs) and refuses anything deeper with theValueErrorthe 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 withNotImplementedErrorwhere it is reached again while its own fields are being built, under the type arguments it is applied to and with notypealias opened since, because its field type names the class and the build never bottoms out; model it withrecursiveinstead. An alias opened since ties the cycle where the fields reach it again (recursion). - Schema construction size. Every way of growing a schema — the
Validatorconstructor, 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 raisesValueError:- depth — at most
MAX_SCHEMA_DEPTHlevels 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 anintare 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
recursiveschemas, 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 | vfolds tov). 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 intoAny-- 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 aTypedDict's required keys are refused past 100,000 items, so one that never ends is refused rather than read until memory ends.
- depth — at most
A real schema stays far under all three. Structural recursion belongs in
recursive, 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)
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, eachrecursive(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 answersFalse-- two schemas, the direction it errs in -- whereis_equivalentstill 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_looprather 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
expectednames only a bounded number of labels before truncating with..., and renders none past them, so a constant'sreprruns for the labels named and no others. The two counts differ — a branch that is itself a union, such as a wideLiteral[...], contributes one branch and many labels — so each carries its own bound. Withfail_fastthe 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 withfail_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 withfail_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 astunder 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 acomplementreads included. A definition that reaches a predicate, or a class whose metaclass is nottype, is not kept: the walk calls that code at each occurrence it reaches (refinements), 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, aMultipleOf'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, soAnnotated[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
KeyboardInterruptraised 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 raisesMemoryErroras 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_jsonholds the parsed tree, about sixteen times the text for an array of numbers and thirty-nine times for an array of small objects, andloadandvalidate_jsonbuild their Python values beside it; a Rust allocation that fails aborts, wherejson.loadsraisesMemoryError. pydantic'svalidate_jsonends 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 raisingMemoryError. What a walk hands back to Python is allocated by Python and raisesMemoryErrorthere. 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.
validatecollects every failure, so a refused value of a million elements builds a million violations;fail_fast=Truecollects 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 inerrors, 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 alist,tuple,dict,setorfrozensetof exactly that type, and from its head for astr,bytesorbytearray. Any other value -- a subclass of those, adeque, anarray, aDecimal, 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_fastpays 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.