Soundness argument¶
This page argues, in a form a reader can check, why an accept is never wrong: if valgebra reports a value valid, the value really is in the schema's set. It is a written argument backed by adversarial tests, not a machine-checked proof; the honest limits say exactly what is taken on trust.
The claim¶
Write ⟦S⟧ for the set of Python values a schema S denotes (its
denotation). valgebra rests on three soundness statements:
- Membership is exact. For every schema
Sand valuex, the walk acceptsxif and only ifx ∈ ⟦S⟧. The "only if" half is soundness of acceptance — the property downstream code relies on; the "if" half is completeness of the check. - Construction preserves meaning. The normal form a constructor builds
denotes the set the spelling names:
⟦union(A, B)⟧ = ⟦A⟧ ∪ ⟦B⟧however the members are flattened, absorbed, ordered or folded on the way in. - Decisions are sound. If
is_subtype_of(A, B)isTruethen⟦A⟧ ⊆ ⟦B⟧; ifis_empty(S)isTruethen⟦S⟧ = ∅. The converses are not claimed — the decision is deliberately conservative.
There is no separate specification the implementation could disagree with: the
denotation is the meaning, so soundness is the statement that the Rust walk
computes x ∈ ⟦S⟧. The argument is therefore a node-by-node check that the
walk's accept condition is, line for line, the membership condition of ⟦S⟧.
Why membership is exact: structural induction¶
The walk recurses on the structure of S. Take as induction hypothesis that the
walk is exact on every strict sub-schema; then check each node. The denotation
and the walk's accept condition coincide at every one:
S accepts x ⟺ x ∈ ⟦S⟧, by:
--------------- -----------------------------------------------------------
Anything always (⟦Anything⟧ = all values;
`Any` is this node, spelled)
Nothing never (⟦Nothing⟧ = ∅)
Bool/Int/... issubclass(type(x), T) (the scalar region)
Literal(c) type(x) is type(c) and x == c (same type, equal)
Union(A_i) some A_i accepts x (∃: set union)
Intersection every A_i accepts x (∀: set intersection)
Complement(A) A does not accept x (¬: set complement)
Refine(B, c_j) B accepts x and every c_j (base ∩ constraints)
Seq(kind, s) x is a list or tuple of that (a linear regular
kind whose elements take the language over element
prefix-and-tail shape s denotations)
Coll{kind, A} every element accepts A (homogeneous container)
KeyedMap(f, d) fields present-and-match, and (named fields ∩ keyed
every other key matches a default clauses)
default clause
Instance(C) isinstance(x, C) (class extension)
AttrRecord(f) every field's attribute is (attribute record; no
present on x and matches carrier, so a dataclass is
`Instance(C) ∧ AttrRecord`)
Any admits every value, exactly as the top does, and it is the top: one
node, one denotation, with the spelling kept for repr alone (see Any is the
top, spelled). The row above covers
both.
For the Boolean nodes the equivalence is the definition of the set operation, so
the step is immediate given the hypothesis on the children. For the structural
nodes (Seq, Coll, KeyedMap) the walk evaluates the children exactly by
hypothesis and combines them by the same connective the denotation uses. The
scalar leaves read the value's real type, not the __class__ it declares (the
trust base below says why); Instance reduces to isinstance, which is
Python's own membership test for a class; and Literal adds the same-type guard
that keeps the constants 1, True and 1.0 distinct.
Recursion terminates and stays exact¶
A recursive schema is guarded: every back-edge sits under a structural
constructor. Membership unfolds the definition against the value in hand, and
because the value is a finite Python object each unfolding asks about a
strictly smaller value — so the set is defined by well-founded recursion on the
value rather than chosen among fixpoints, and the guard is what makes that
recursion well founded. An attribute record is the exception: its fields are
computed by getattr rather than taken apart, and (5).real is 5, so a value
read through one need not get smaller -- such a value is outside the model, as
what this argument assumes says. Two further guards keep the unfolding finite in the
walk:
- an object-identity guard rejects a value that contains itself
(
recursion_loop) rather than looping, and - a depth bound rejects a value nested past the limit (
recursion_limit) rather than overflowing the stack (see resource limits).
On the inhabitants — the finite values — the guarded unfolding accepts exactly the members, which is why a coinductive comparison at the greatest fixpoint never contradicts a membership verdict (see recursion).
A stop is not a verdict. Each guard ends the walk without deciding
membership, as a predicate that raises (predicate_error), a container
changed under the walk (mutated_during_validation) and a recursive
placeholder met inside its builder (unresolved_recursion) do, and the walk reports
the stop as a refusal. That is sound in the direction that matters, since no
stop admits a value, and it is where the walk is not exact: a list nested past
the bound is a member of a recursive S and refused by it. complement(S)
refuses it too, because the Complement row above reads the walk of A
finished and refused, and a stopped walk did not. So the walk computes
x ∈ ⟦S⟧ on every value it finishes, and a value on which it decides nothing,
only stopping, is refused by a schema and its complement alike: a part that
refuses, or a branch that admits, decides the walk whatever a part beside it
stopped on (the error model).
A relation reads a walk the same way where it puts a value to one -- a
literal's constant, an enumeration's members, None, the texts of a pattern
too large to build: a value the walk stopped on is neither in the set nor out
of it, so it proves and refutes nothing. Literal[5] is not refuted below
T | ~T for a T whose predicate raises on 5.
Why construction preserves meaning¶
Every fold a constructor applies is a law of the Boolean algebra of sets —
flattening associative nodes and a refinement of a refinement, dropping identities
and duplicates, letting the
top absorb a join and the bottom a meet, ordering the members, canceling ¬¬X
to X, and folding X ∩ ¬X to ⊥ and X ∪ ¬X to ⊤ where X holds no class
and no predicate — each of which holds of the sets, so none can change ⟦S⟧.
Absorption of a member another contains is not among them: that fold needs a
containment, which is a decision (Schema::union in
crates/valgebra-core/src/ir.rs says so). The form is held to this one
invariant and to nothing stronger: it is a lattice normal form, not a decision,
so membership relations are read off the decision procedures, never off the
shape of a term.
Why the decisions are sound (and only sound)¶
is_subtype_of applies structural inclusion rules, each a valid set inclusion:
A ⊆ B₁ ∪ … ∪ Bₙ when A ⊆ some Bᵢ, A₁ ∩ … ∩ Aₙ ⊆ B when some Aᵢ ⊆ B, the
contrapositive between two complements (¬A ⊆ ¬B when B ⊆ A) and emptiness of
the meet against one (A ⊆ ¬B when A ∩ B is empty), componentwise inclusion
for the structural forms,
and the coinductive rule for recursion (assume the goal on the current path —
sound for inclusion at the greatest fixpoint). A leaf the rules cannot relate is
handed to an oracle, which proves, refutes, or declines. Every rule preserves
"the conclusion holds whenever the premises do", so a True from the rules is a
proof.
Where the rules decline, is_subtype_of and is_empty ask the set
representation (crates/valgebra-core/src/descr/): it lowers each side to the
set it denotes and decides A ⊆ B as the emptiness of A ∧ ¬B. A recursive
reference is unfolded once and cut to a bound — the top on the side read
widened, the bottom on the side read narrowed — so the difference it reads
contains the real one: an empty difference proves the inclusion, and an
inhabited one refutes only at a kind no cut reaches, a cut beneath a constructor
changing that constructor's kind of values alone and one beneath an attribute
record changing every kind's. Past that the difference is read cut the other
way, the subject narrowed and the supertype widened, which lies inside the real
one, so a value it holds refutes at any kind and its emptiness proves nothing. A
schema the representation cannot hold, or one past its build bounds, is a
decline rather than an answer, so a True from this reading is a proof too.
is_empty is the primitive, not a derived relation: it decides the value
regions, the complement and disjointness laws, and the refinement bounds
directly, and the subtyping rules call into it — the lattice bounds ∅ ⊆ B and
A ⊆ U are asked of emptiness, and A ⊆ ¬B reduces to A ∩ B being empty. So
emptiness carries its own soundness and lends it upward, which is the direction to
check the argument in. is_equivalent is mutual inclusion and inherits from
subtyping.
The conservatism is the price: when no rule fires, the oracle declines and the
set representation cannot settle the pair, the answer is False — "not proven",
not "disproven". This is why the decidability boundary
maps where False is exact and where it is conservative, and why the docs say
closed algebra, conservative decision.
How the argument is mechanized¶
The argument is checked, not just asserted. Four of the suite's layers bear on
it directly; docs/dev/testing.md in the repository owns the full list, with
what each layer is blind to beside it.
- Denotation oracle. Each node's
⟦S⟧is written as a reference predicate over a value generator, and the walk is property-tested to agree with it — this is the membership-exactness claim, checked on generated values. - Algebra laws. Every law construction relies on is property-tested against the membership relation, in Rust (proptest) and Python (Hypothesis).
- External ground truth. The same schemas and values run through pydantic-core and jsonschema; a divergence is a bug or a documented intentional difference — an independent check that the reference predicates themselves are right, closing the single-author blind spot.
- Coverage-guided fuzzing. libFuzzer drives the decision procedures over the whole IR, asserting the sound order laws (reflexivity, the lattice bounds, equivalence as mutual inclusion); the same invariants gate every merge. A second target asks them again under a pool of constants, bounds and classes drawn beside the schemas, where an inclusion proved knowing nothing of the pool is never refuted knowing it, nor the other way round.
These are partial mechanization — adversarial, independent, and coverage-guided — in place of a fully formal proof.
What this argument assumes¶
The soundness is relative to a small, explicit trust base:
isinstanceand the PyO3 conversions report Python's own membership. A value crosses the boundary as itself, and what Python answers about it is read as a fact about the value rather than checked against a second reading.
A builtin kind is not read through isinstance, and __class__ is not in
the trust base for one. isinstance consults a value's __class__, which a
property can answer with any type at all, so an object declaring itself an
int passes isinstance(value, int) while holding none of an integer's
storage. A schema over a builtin kind reads the value's real type instead.
The sharper case is a genuine int subclass that declares itself a str.
isinstance reads the real type first and the claim second, so Python admits
that value to both kinds — which no value is, and which would put one
value in a meet this library proves empty. Reading the real type gives one
answer to each kind.
Where a schema names a user class, membership is isinstance by definition
and a lying __class__ is honored: overriding it is how a proxy is written,
and a proxy every other consumer treats as a Target is one here too.
- A class relation holds of values whose __class__ is their type. The
walk admits a proxy -- a wrapt.ObjectProxy, a
unittest.mock.Mock(spec=C), any object whose __class__ answers another
class -- to the class it names, as pydantic, msgspec, typeguard and beartype
do. The relations read a class by its bases and the layout it lays down --
the one Python built, along __base__ and from the slots it made with the
class, not a __slots__ or an mro() code writes afterwards, and past those a
builtin its order names, which type refuses an mro() to add -- which a proxy
does not share: two classes with distinct __slots__ are
decided disjoint, and an instance of one that declares itself the other is
admitted by both, so their meet is decided empty beside a value it admits. A
proxy is outside every class relation. Reading the real type in the walk
would refuse every proxy and mock, which no reference does, and declining
the layout proofs would give up the disjointness every decided union of
dataclasses stands on; the case is pinned as a known-unsound test instead.
- A key equal to a declared name is a string. The walk reads a record's
keys the way the dict resolves them, in every one of its readings: an object
of another type that hashes and compares as "a" is field a wherever
d["a"] finds it. Two keys of a dict can reach one name, since str's ==
and a subclass's own need not agree: the field is the entry the lookup finds,
and the other is a key the record does not declare. The relations read a field's key as a str, as the
typing spec writes a TypedDict's keys, which is what puts a record below a
mapping keyed by str: {"a": int} is decided below dict[str, int], and a
dict whose one key is such an object is in the first and not the second.
Reading the key as an undeclared one instead would need the key a probe
matched, and a dict lookup hands back only the value, so every record would
be scanned rather than asked for its keys. The case is pinned as a
known-unsound test.
- A str key's hash and == are those of its text. A field reads a key by
its hash and ==, as the dict does, and a pattern or a length reads it by its
text, and the relations read the two as one: a finite language's words as the
keys it holds, and a field's name as a word of a language. A str subclass
with a __hash__ or __eq__ of its own parts them. {Apart("a"): 1}, whose
== is identity, is in dict[Annotated[str, Regex("a")], int] and outside
{"a?": int}, and {Folded("A"): 1}, equal to "a" by its folded case, is in
{"a": int} and outside that mapping. Each is read exactly by the walk, and
each relation is proved over the keys the assumption holds of, which are every
key JSON gives and the str subclasses that keep str's hash and ==. Reading
a key's text and what it reaches apart gives up every proof between a record and
a mapping narrowed by a language, which is what properties beside
patternProperties asks. The cases are pinned as known-unsound tests.
- An enumeration's instances are made through it. Color is decided to be
the union of its members because the class makes no other instance.
object.__new__(Color) makes one past it: the walk admits it to Color,
and no member's literal holds it, so it is outside the relation that equates
the two. The union is read on both sides, a refutation reading the members
as a proof does, so no answer stands on such a value; a member is read as it
stands, so one given an attribute later refutes as its literal does. A
refutation standing on an instance made past the members is sound where the
class is read as the class it is: an IntEnum is not below Ge(1) although
both its members are, because int.__new__(IE, -5) is an instance the walk
admits and the bound refuses.
A class that makes another instance through itself is no union of its
members at all, and is read as the class it is: a _missing_ of its own
answers E(5) with a new instance, and a metaclass's own __iter__ or
__call__ can hide a member from list(E) or build one past the lookup.
So is one with a subclass: no class statement makes one, but __bases__
assigned to a plain class does on CPython 3.15, whose own constructor then
makes an instance of Color that is no member.
- What a value answers is a function of the value. Membership asks a value
questions through Python — isinstance, __eq__, a rich comparison, __len__,
%, a predicate — and reads the answers as facts about it. A method that
answers differently on two calls with the same argument is not describing a
set, and the walk is built on the assumption that none does.
A & ~A rests on it where Python asks for one answer. That law is a law
about sets, and construction applies it to every atom whose answer Python's
own rules make a fact about the value: an attribute, which is a reading of
the value; a constant's ==, which a record's key lookup asks too; a bound's
comparison; a length; and a step's %. The language reference sets rules
for comparisons, and the data model has __len__ return the object's length,
at most sys.maxsize, past which len() raises, so no value is longer, and
a container is no longer than the one allocation holding its items allows,
so a refutation stands on a length every interpreter builds,
sys.maxsize // 128, and declines past it;
not-a-number is the exception those rules name, and it is read as one:
Literal[nan] is empty and Ge(nan) is refused. A value whose method
answers two calls differently is outside the sets the law is about: P
admits it on one call and complement(P) on the next, and intersection(P,
complement(P)) is folded to nothing all the same. The five atoms are
pinned as known-unsound tests.
Python asks nothing of a predicate, or of a metaclass's __instancecheck__ or
__subclasscheck__, and correct code answers them differently on two calls:
a predicate that admits each value once, a class register adds to. So an
atom running one is declined rather than decided. An abc.ABC is declined by
the same test, because ABCMeta overrides both hooks -- which is how
register changes the relation after a schema is built. A class whose
metaclass leaves the hooks alone is a set, and the decision reads the law of
it: intersection(C, complement(C)).is_empty() is True. Construction folds
the pair for no class, because it holds no class object to ask whether a hook
answers isinstance, so the meet keeps its spelling.
A hook is read where Python dispatches it. isinstance, issubclass,
==, <, math.floor, len, iter, a call and a descriptor's __set__
run what the type's own namespaces hold along the order Python laid down,
and ask no __getattribute__, not even the metaclass's (the language
reference, "Special method lookup"). getattr on a class asks the metaclass
first, so every reading of a class here -- whether a hook, an __eq__, an
order or rounding method, a __len__ or an __iter__ is the base's own, the
namespace a class's slots and descriptors are read from, its method
resolution order, its flags and instance sizes -- looks where the
interpreter looks, as inspect.getattr_static does. A metaclass whose
__getattribute__ answers type's own __subclasscheck__ hides none of its
own: the class is read as one that overrides it, and declined.
A bound conjunction rests on the order besides. A contradiction between
two bounds is decided by comparing the bounds, which holds only because a
value ordered against one is ordered the same way against the other -- the
consistency Python's rules ask of comparisons, which a subclass can break
while answering every call alike. Annotated[int, Gt(0), Lt(1)] is decided
empty, and an int subclass whose comparisons answer True satisfies both
-- a True no value supports. Deciding it soundly means reading
the bounds over the exact builtin, which needs a schema to distinguish
"exactly int" from "an int or a subclass". The set representation has that
class for a literal, which is the constant at its exact type, and a bound is
not read through it: a bound holds of the subclasses too. The case is pinned
as a known-unsound test rather than left unwritten. A step rests on the value's
% the same way: Annotated[float, MultipleOf(1), Gt(0.0), Lt(1.0)] is decided
empty, and a float subclass whose __mod__ answers 0.0 is admitted by it, a
method answering one thing every call. A class need not set out to do this:
np.float64(2.0**53) >= 2**53 + 1 is True where the float of that value
answers False, since numpy converts the int to a float first, and
np.float64(2.0) > -(10**400) raises where the float answers True. So over
an integer bound past 2**53 or past a float's range, a relation over float
holds of the floats that compare as float does; JSON's maximum can be such
a bound. The bound's own operand
is another matter, and is not trusted: a builtin subclass whose __eq__ or
order is its own is read by the walk through the builtin's storage or its
reflected method, so two bounds are compared only where each operand keeps
its builtin's comparisons. A class of no builtin orders as unknown, since
Python implies no relationship among a class's comparison operators and the
walk reads >= alone, unless it is exactly one of the value types below.
- A class whose metaclass leaves isinstance alone holds an object. A
refutation about a class stands on a value of it, and nothing here can build
one: reporting A not below B for two unrelated classes reads the
difference as holding a value, and a class no value can instantiate is empty
and below everything. The assumption licenses one object, on the line of
objects with no builtin kind — a plain class against the complement of int
stays undecided, because an integer that is an instance of it would need a
class deriving from both. The object is a direct instance, and it carries
only what the class leaves room for: a field the class answers with a data
descriptor or a __getattribute__ hook, a name its body defines that a
record requires missing, and a name its instances have no __dict__ or slot
to hold are not assumed onto it, so a relation that would stand on one is
undecided. A __getattr__ hook answers every lookup that finds nothing, so
beside one no name is assumed missing, and a name with no __dict__ or slot
to hold it is the hook's answer. It moves no True: a proof is a proof, and the assumption is only
ever read to believe a refutation.
The decidability page states it with the rows it moves.
- The JSON parser (jiter) agrees with json.loads where both accept. On a
document both parsers build a value from, they build the same value, which is
what makes the JSON path's denotation the object path's.
The grammar is the stricter of the two, and the difference is named.
Documents Python's module parses and this parser refuses: a non-standard
float token (NaN, Infinity, -Infinity), a lone surrogate written as an
escape or held by a str, a document nested past the parser's depth, an
integer past its digit limit once the interpreter's own is lifted, and on
bytes a byte-order mark, a UTF-16 or UTF-32 encoding or bytes that are not
UTF-8. Each is reported as json_invalid before a schema sees it, so the JSON path admits
a subset of what the object path does and never a different value
(the JSON path states both with the queries that show them).
- The regular-expression parser reads a class as the set it writes. A
pattern's class is the set of characters its items name, read by the
regex-syntax crate for the walk and for the relations alike.
A negated class whose set is split at the surrogate gap is the one place it
does not. regex-syntax 0.8.12 negates a set holding
a range that ends at U+D7FF and another that starts at U+E000 into a set that
keeps both, so [^\x{D7FF}\x{E000}] admits "\ud7ff" and "\ue000", and the
relations read the same wrong set: it is decided not_subset of
[^\x{D7FF}], which it is below, and [^\x{D7FF}] subset of it, which holds
U+E000. The two readers agree, so no relation contradicts the walk. A class
meets it only where its own ranges stop and start exactly there -- the
surrogates excluded by hand, or the union of two properties such as
\p{Cn} and \p{Co} -- and never through a Perl class, since none of
\w, \d and \s holds U+E000, a private-use code point. The case is
pinned as a known-unsound test, which fails the day a fixed release is read.
- The crates contain no unsafe. Both crate roots carry
#![forbid(unsafe_code)], which makes an unsafe block below one a compile
error rather than a reviewer's job — so there is no memory-safety obligation
here beyond the compiler's.
- Predicate refinements are opaque. A Predicate constraint runs arbitrary
Python; valgebra checks that it returned truthy, and the soundness of that
leaf is the caller's. Regex constraints are matched natively and match the
text of a str: a string carrying a lone surrogate has no such text and
matches no pattern. The str kind holds one all the same — it is a string of
one character — so a kind is never a subtype of a pattern over it, however
much text that pattern matches, and "\ud800" is the value that says so.
- A literal is its constant's class under ==. Literal[c] denotes
{x | type(x) is type(c) and x == c}. For an int, a bool, a str,
bytes, None, a sentinel and a nonzero float that is one value; for a
float zero it is both zeros, for a Decimal every spelling equal to it, for a
constant whose class defines __eq__ whatever that method admits, and for
float("nan"), which is equal to nothing including itself, the empty set. A
proof that runs the constant through a predicate or reads its attributes
speaks for that one value, so it stands for the literal only where the
constant is the whole class; Literal[0.0] below a predicate refusing -0.0
is not proven. A proof through a kind or a class whose isinstance runs no
hook reads the type alone, which every value of the literal shares as its
exact type, and stands for all of them whatever their equality:
Literal[CI("a")] is below str and outside int. A proof through any other
atom stands where the values == joins to the constant are read alike by it:
under an exact builtin's equality, a builtin subclass's that keeps it, a value
type's, or identity. The value types are, exactly and by identity with the
class their module binds, complex, bytearray, range, the builtin
containers, Decimal, Fraction, the datetime types, UUID, the
ipaddress addresses, networks and interfaces, and the pathlib paths: each
orders, divides and measures, where it does, as its == says. A class stating
one of their modules is none of them, and a module of the program's own
imported under one of those names is its own, and so are its classes: the
module is the interpreter's where the import system loaded it from the
directory sysconfig.get_path("stdlib") names, or froze or built it in, and
a module placed nowhere -- one with no origin, or a standard library read
from an archive -- is taken for the program's, whose classes are declined.
What that module imports in turn, an accelerator such as _decimal, is the
interpreter's as well: a program replacing it, or a class the module binds,
changes the interpreter, and is outside the base. A class
whose __eq__ is its own is read by none of those, so a proof by its constant
is not made: a case-insensitive str subclass holds "A" in the literal of
"a", which Regex("a") refuses, and an __eq__ that is not transitive
would join a value to c that it does not join to an equal d.
- The values are the finite ones. A guarded fixpoint denotes the values built
by finitely many unfoldings, which is what makes membership an induction on the
value. A value that contains itself is not a large member: it is outside the
model, which is why the identity guard reports recursion_loop rather than
deciding. An attribute is computed rather than contained -- (5).real is 5,
and a property can return a new object at every read -- so through an
attribute record a scalar can be such a value too, and is reported the same
way, or by the depth bound where the attributes never repeat an object.
- The value holds still for the length of the call. Membership is a claim
about the value the walk read, so a value that changes while it is being read
has no membership answer. A change the walk can see — a container whose size
moves, or a second reading that disagrees with the first — is reported as
mutated_during_validation rather than answered
(the error model); a change it cannot see, such as a
field rewritten in place after the walk passed it, leaves an answer about the
value as it was.
- The suites check necessary properties, which is weaker than an oracle. A
property-based or metamorphic check fails when the implementation is wrong;
passing need not entail it is right, however many such properties are added. So
the layers above raise the cost of a defect surviving without bounding it.
Within that base, an accept is a claim that x ∈ ⟦S⟧, justified node by node
above and exercised by the layers named there — which is what "rock solid" can
honestly mean before a machine-checked proof and outside review exist.