Skip to content

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:

  1. Membership is exact. For every schema S and value x, the walk accepts x if and only if x ∈ ⟦S⟧. The "only if" half is soundness of acceptance — the property downstream code relies on; the "if" half is completeness of the check.
  2. 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.
  3. Decisions are sound. If is_subtype_of(A, B) is True then ⟦A⟧ ⊆ ⟦B⟧; if is_empty(S) is True then ⟦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:

  • isinstance and 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.