The decidability boundary¶
valgebra compares schemas as sets: is_subtype_of is set inclusion, is_equivalent is
mutual inclusion, and is_empty reports an unsatisfiable schema. The relation is
s <= t exactly when s and not t share no value, so every comparison reduces
to an emptiness test (see foundations).
Every answer is sound relative to the trust base.
A True from is_subtype_of/is_equivalent, or a True from is_empty, is
correct for every value inside it: one that answers Python's questions as a
function of itself, whose __class__ is its type, and, for an enumeration's
instance, that the enumeration made, among the rest the trust base lists. Where
valgebra cannot yet prove a relation it answers conservatively — False, or
"not empty" — never a wrong True. So a positive answer is a guarantee, and a
negative answer is "no, or not proven".
This page states which queries valgebra decides completely, which stay conservative, and which are undecidable at runtime and so are rejected or treated opaquely by necessity.
is_empty answers in two, and the question behind it answers in three. A
False from is_empty covers both "a value is in this schema" and "no reading
proves it holds none", which are different claims — one names a value, the
other names a limit. Emptiness is s <= nothing, so relation_to(nothing)
is where the third answer is:
from typing import Annotated
import annotated_types as at
from valgebra import Validator, nothing
opaque = Validator(Annotated[int, at.Predicate(lambda value: value > 0)])
assert opaque.is_empty() is False # not proven empty
assert opaque.relation_to(nothing) == "undecided" # and not proven inhabited
assert Validator(int).relation_to(nothing) == "not_subset" # a value says so
Decided exactly¶
Over this fragment, valgebra returns the exact set-theoretic answer: on every case below it agrees with set inclusion in both directions, not only the sound one. This exactness is verified case by case against a completeness ledger — a curated set of relations the procedure is asserted to decide — and re-checked by a fuzzer that confirms the sound direction over a finite value universe; it is a gated, exercised guarantee, not a proved theorem over the whole fragment. Outside this fragment the procedure stays sound (see Sound but conservative).
relation_to reports which of the two a False is: "not_subset" where a
value of the subject is outside the other schema, and "undecided" where no
rule and no set reading answers. Everything in the conservative list below
answers "undecided".
- A subject of finitely many constants. A schema built from literals,
None,bool, fixed sequences, sequences of one exact length, closed records and unions of them denotes finitely many values, and where it denotes at most sixty-four, each of at most 4,096 items or fields, built from anint,bool,str,bytes,Noneor a float, its relation to a schema is the membership of each value:"not_subset"on a value outside,"subset"where every value is inside, and"undecided"where the walk of a value stopped -- at the depth bound, say -- and none is outside, since a stop is no verdict (soundness). A schema holding a predicate, a class or an attribute is not read this way, since its code may answer two calls differently, and neither is a constant whose class==widens past itself. It is the shape a translation from JSON Schema writes forconstandenum. -
A value guessed from the subject. Where neither the rules nor the sets decide a pair, the relation guesses a few small values from the subject's spelling -- a value of each scalar kind it names, each of its constants, the sequences, sets and dicts its items and fields guess, three containers deep, a reference read through its definition, and one value of each kind for a complement -- and walks each through both schemas. A value the subject admits and the other schema refuses, both walks finishing without a stop, refutes the pair:
"not_subset". The guesses prove nothing, so a pair none refutes stays"undecided", and a guess reads a refinement as its base, so a value inside a bound is one it can miss. A schema holding what the subject of constants above may not, or a bound or a step that is neither an exactint,boolorfloatnor the standard library'sFractionorDecimal, is not read this way: a class of the program's own compares by its code, which a second call may answer anew.- A value aimed outside the other schema. Beside the subject's guesses, the relation builds values aimed outside the other schema, its negation pushed one constructor in as a witness generator for JSON Schema pushes it through each operator: outside a list offrom typing import Annotated, Any from annotated_types import MaxLen from valgebra import Validator, recursive nested = recursive(lambda t: [t]) short = Validator(Annotated[list[Any], MaxLen(1)]) assert short.relation_to(nested) == "not_subset" # [None] is guessedX, a list holding one value outsideX; outside a sequence no item may follow, one item more; outside a record, a dict lacking a required key, holding a field outside its type, or holding a key the record closes out or a clause holds under another value; outside a bound, a number beside it; outside a constant, the integer or the string beside it; outside a complement, its operand's members; and one value of each other kind. A complement in the subject is guessed the same way, as what its operand misses. The subject's walk keeps the ones it admits, and one the other schema refuses refutes the pair as a guess from the subject does, so a pair decided this way is"not_subset"and nothing else. Here the key is guessed outsideLiteral["a"]as"aa", and{"aa": 0}is refused by thestrclause.- The scalar Boolean algebra. Every union, intersection, and complement of the scalar atoms (from typing import Literal from valgebra import Validator, complement keyed = Validator({complement(Literal["a"]): int}) assert keyed.relation_to({str: str, complement(str): int}) == "not_subset"None,bool,int,float,str,bytes), withboola subtype ofint. The complement laws hold:int & ~intis empty,int | ~intis the universe. - Complement and disjointness across kinds. An intersection that carries a schema together with its complement (A & ~A), or two members of provably disjoint kinds (a list and a set, anintand astr), is empty — for the structural kinds, not only the scalars. A member is read by its kinds through a union and a meet:intmet with a union ofintersection(str, union(complement(str), Annotated[str, Regex(p)]))for two patterns -- each applied to strings alone, as JSON Schema applies apattern-- is empty whatever the patterns are.Anyis the top, spelled, so the rule reaches it like any other set:intersection(Any, complement(Any))is decided empty. - A bare container class and its parameterized form.listandlist[object]are one schema: an unparameterized generic names its kind's whole set, which is what the typing spec assigns it.tuple,set,frozensetanddictread the same way, asstrandintdo. - Class and literal inclusion. A class is a subtype of its base classes, byissubclass, and a literal is a subtype of any schema its constant is a member of, where the constant is the literal's one value or the schema tells no two equal values apart:Literal[0.0]also holds-0.0, so a predicate that refuses-0.0leaves it undecided (Predicates). A dataclass or named tuple relates the same way: its schema is below one over a base class it carries every attribute of, each with a narrower schema, and below the bare class it is an instance of. A named tuple relates to the tuple its fields lay out as well, in both directions where both hold: its positions are its fields, the schema says so, and the ordinary sequence rules decide from there. A class built on a builtin relates to that builtin too:Validator(MyInt)is belowValidator(int)andValidator(MyStr)belowValidator(str), because every instance of such a class is a value of that kind and the class narrows the kind rather than standing beside it. A class built on no builtin narrows nothing — an instance of a subclass of it may be a string — so it relates to a kind in neither direction. A class whose own__slots__add a slot lays down a layout as a builtin does, and Python refuses a class deriving from two layouts unless one extends the other: two such classes neither of which derives from the other share no instance, so their meet is empty and each is below the other's complement, and one laid down over no builtin is below the complement of every builtin kind. An empty__slots__, or one naming only__dict__and__weakref__, lays down nothing. A type defined in C lays down a layout where its instance is larger than its base's, as Python reads it:complexmeets no JSON kind and is below the complement of each, andValueErrormeetsTypeError, both carrying the layoutBaseExceptionlays down. PyPy names no size, so there a type defined in C is read by its slots alone and such a pair isundecided. The@disjoint_basedecorator of PEP 800 is a promise to a checker that the runtime does not enforce, and it is not read. - A meet holding a literal. A meet holding a literal, or a union of them, is read one constant at a time by the same walk: it is inhabited where a constant is a member of every other member, and empty where each constant is refused by one of them, under the condition on equal values above. So a literal met with the complement of its meet with a recursive universe is empty, at a depth the set representation does not reach. A value the walk cannot read, one at which a predicate raises, is refused by a set and by its complement alike, and decides nothing.from typing import Literal from valgebra import complement, intersection, nothing, recursive, union json = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) paid = Literal["paid"] assert intersection(paid, complement(intersection(paid, json))).is_empty() # `paid & list[int]` is empty, so its complement holds "paid". inhabited = intersection(paid, complement(intersection(paid, list[int]))) assert inhabited.relation_to(nothing) == "not_subset" -
Literals against other kinds. A literal pins
type(x)exactly, so it carries the kind of its constant and is decided against another kind:Literal["a"]is below~int, andLiteral["a"] & Literal["b"]is empty.Literal[1]andLiteral[True]are disjoint although1 == True, because the two pin different types. A plain value of a kind is outside a table of another exact type, solist[str]isnot_subsetofLiteral[Color.RED], on[], and~Literal[Color.RED]ofstr, onNone. The rule reads the constant's type and applies only to the builtin scalars, whose equality is Python's own, and to any type that compares by identity -- which an enumeration does unless it says otherwise, so two of its members are two values and a meet of them is empty, and which 3.15'ssentineldoes by an__eq__of its own. AnIntEnumsays otherwise: its members equal the integers they carry, and a meet of two of them stays conservative. Whatever its constants are, a finite set of them is not a kind with infinitely many values, and its complement holds a value -- an object of a type none of the constants has:intis not belowLiteral[Color.RED], and~Literal[Color.RED]is not empty.None's kind is the literal of its one value, walked through the other side:Noneis not belowLiteral[Color.RED], andintersection(None, ~Literal[Color.RED])is not empty. So aretype(...)andtype(NotImplemented), which admit no subclass either:instance_of(types.EllipsisType)isLiteral[...]. - An enumeration against the union of its members, when every instance of
the class really is one of them -- made through the class, which
object.__new__steps past (the trust base): anEnumthat is not aFlag, carrying at least one member, whose members compare by identity, withEnum's_missing_andEnumMeta's__iter__and__call__. ThenColorandLiteral[Color.RED, Color.GREEN]are one set, decided in both directions, and a refutation reads the members as a proof does. A meet holding the class is empty where the members beside it refuse every member, asColormet with a protocol requiring an attribute no member carries is, and is the class where the members beside it hold every member, soColor & (str | Color)answers asColor. The class is still whatreprprints and what a failure names. The four exclusions are each a value that would stand against the union:
| kind | the value it admits that list(cls) never yields |
|---|---|
Flag, IntFlag |
P.A \| P.B -- \| builds instances the class never listed |
an Enum with no members |
a member of a subclass, since a memberless enum can still be subclassed |
IntEnum, StrEnum |
nothing new, but its members equal the values behind them, so two of them are not two values |
an _missing_, or a metaclass __iter__ or __call__, of its own |
E(5) from the hook, or a member list(cls) leaves out |
Each stays an isinstance atom, which is sound for every enumeration and
merely less complete.
- A class against bool. bool takes no subclass, so a boolean is an instance of a
class only through bool's own order, int and object, and intersection(K, bool)
is empty for a class with a plain metaclass. A metaclass of its own or a registered
virtual subclass answers otherwise, and declines.
- Zero under a step. Zero is a multiple of every step a build admits, 0 % q
being an exact zero for a float, a Fraction and a Decimal alike, so
Annotated[int, MultipleOf(0.5)] and Annotated[int, MultipleOf(Fraction(1, 3))] are
not_subset of nothing and of str, on 0. A step of another type declines here:
a subclass's __rmod__ answers the remainder of an integer and may refuse zero.
- Divisibility between two moduli, where it holds. Every multiple of a is
a multiple of b when b divides a, so the two steps settle the inclusion
between them and the size of either is beside the point: MultipleOf(5000)
is decided below MultipleOf(2500). The question is Python's %, asked of
the two steps, and it carries to the values where % reads a value and both
steps as one kind of number: two int steps over int, two float steps
over int or float, and over float any two steps a float holds exactly.
The other direction is a refutation, and the subject's own multiples name
its value where its constraints are its step and integer bounds: of two
consecutive multiples of a, a step that does not divide a divides at most
one. A subject narrowed by anything else leaves the value to the residues, the
conservative entry below:
```python
from typing import Annotated
from annotated_types import MultipleOf
from valgebra import Validator
fives = Validator(Annotated[int, MultipleOf(5000)])
assert fives.relation_to(Annotated[int, MultipleOf(2500)]) == "subset"
assert fives.relation_to(Annotated[int, MultipleOf(3)]) == "not_subset" # 5000
```
- Refinements. A refinement is a subtype of its base and of a refinement with
looser bounds — a tighter numeric or length bound entails a looser one, not only
a verbatim-contained constraint set; a bound conjunction that cannot be satisfied
— a lower bound above an upper bound, a minimum length above a maximum, or a
length a sequence's shape cannot take — is empty. Where the values are bounded
to the integers the bounds count them, so an interval that skips every integer
—
Annotated[int, Gt(0), Lt(1)]— is empty even though its endpoints are ordered. That holds however the meet is spelled: on one refinement, or across an intersection whose members bound it, since an intersection is a subset of every member. A bound written over every value and met with a base is that bound over the base:intersection(str, Annotated[object, MinLen(2)])is the setAnnotated[str, MinLen(2)]is, andintersection(int, Annotated[object, Gt(0)])the setAnnotated[int, Gt(0)]is. Met with a set or a dict, whose lengths the set representation does not count, it declines. Aboolbase counts too, because it subclassesint; afloatbase holds0.5between the same bounds, so they are not empty. Afloat,FractionorDecimaloperand over the integers is read at its floor or its ceiling, since Python compares anintwith each exactly:Annotated[int, Gt(0.5)]andAnnotated[int, Gt(Fraction(1, 2))]are the setAnnotated[int, Ge(1)]is, andGt(math.inf)holds no integer. A bound over a float base is a set of floats and is decided as one: which side a bound lands on is chosen by the base rather than by the operand's type, soAnnotated[float, Gt(0)]carries the integer zero and still orders the floats.nanis outside every interval, which is the comparison Python makes. AFractionorDecimaloperand is read at the float on the side it keeps, since Python compares afloatwith each exactly: the float0.1is a little aboveDecimal("0.1"), soAnnotated[float, Ge(Decimal("0.1"))]holds it and is the setAnnotated[float, Ge(0.1)]is, andGt(Decimal("0.1"))is that set too. No float lies between a float and the next one, soGt(1.0)is decided equal toGe(math.nextafter(1.0, math.inf)), and a pair of bounds with no float between them is empty. A step over a float base is decided with them:x % n == 0holds of the whole floats of one residue class, and of no fractional float and neither infinity, so a set of floats is a list of intervals per residue beside the intervals of the floats no step holds.Annotated[float, MultipleOf(1), Gt(30), Lt(31)]is empty, the complement of a stepped range is decided, and past2**53the floats that are there are the ones read:2**53 + 1is the multiple of three between2**53and2**53 + 2, and no float, so that meet is empty too. A step that is fractional or past4096, a period two steps share past it among them, is read by the rules against another step and otherwise declines. A bound overstrorbytesis a set of words and is decided as one: Python orders two words symbol by symbol, a prefix first, soAnnotated[str, Gt("a")]isAnnotated[str, Ge("a\x00")]andAnnotated[str, Lt("")]is empty; a lone surrogate is ordered where its code point puts it. The words are Unicode scalar values, which no lone surrogate is, so a bound whose constant holds one is read where it stands and not under a complement:Annotated[str, Ge("\ue000")]issubsetofAnnotated[str, Ge("\ud800")], and the meet of the first with the complement of the second is read as that relation, and is empty. A constraint is asked of one value at a time, so a refinement of a union is the union of its refined branches:Annotated[int | float, Ge(0)]is the non-negative ints and the non-negative floats, decided as each is, and a value of another kind beside them is refuted below it. A constraint is Python's own operation and a value it raises against is refused, soNoneunder any constraint but a predicate is empty:Annotated[int | None, Ge(0)]isAnnotated[int, Ge(0)]. A branch of strings or of another kind a class may derive from stays undecided under a numeric bound, since a subclass may answer the comparison, and so does a base that is neither the whole numbers nor the floats alone, because narrowing it to one component would give a smaller set than the schema denotes. - Sequences. Homogeneous, fixed-length, and prefix-plus-tail lists and tuples,
with the container as part of the type (a list is never a tuple). Every sequence
schema valgebra builds takes this linear shape, so inclusion between two
sequence schemas is decided completely — a bare
listamong them, since it is the sequence node its kind's top spells (above). A repeated element outside the supertype's repeated element refutes whatever the prefix decides, where the subtype is proved to hold a value:[int, int, ...]is decided not below[Y, str, ...]on[1, 2], for aYno rule can read. A fixed-length sequence is also decided against a union of fixed-length ones it splits across, where no single branch contains it:tuple[int | str, int]is belowtuple[int, int] | tuple[str, int]. The rule needs a fixed component count, so a homogeneous or variadic sequence — a star, matching every length — is not decomposed. The split narrows the product by one branch a level, so it runs under the work budget and the relation's depth bound both, and its reach grows with components and branches together: six components eachint | strare decided below their sixty-four corners, seven decline against their 128, and a two-component tuple declines against a few dozen branches that each fix its first position. - Sets and frozensets. By element inclusion.
-
Records and mappings. Closed-record width, depth, and required-ness; pure mappings with several key-pattern clauses, each subtype clause subsumed by a supertype clause or covered by several together over whole kinds, which the set representation decides:
dict[int | str, int]is below{int: int, str: int}; and a record mixed with a catch-all when the subtype carries at least the supertype's fields, or when a field the subtype lacks is optional in the supertype and the subtype's catch-all covers its value type (each extra or optional field covered by a catch-all over all string keys). A closed record is compared against a catch-all mapping by the same rule, so{"x": int}is decided belowdict[str, int]. A key the supertype requires and the subtype does not declare refutes the inclusion however open the subtype is: a clause governs the keys a value carries and requires none, so the subtype holds a value without that key, anddict[str, int]is decided not below a record that requires one. A key the subtype declares optional refutes the same way, whatever the field's types decide of each other:{"a?": int}is decided not below{"a": Y}on{}. A meet of two of them is empty when some key one side requires cannot hold: because the types the two give it share no value, or because the other side is closed and does not declare it. Only a required key can do this — a meet of two mappings, or of two optional fields, always contains the empty dict. Two unions of records told apart that way share no value at any width, each record of one read against each of the other by the key both require: two discriminated unions of two hundred records whose tags are apart meet in nothing, where distributing the meet into record meets runs out of work at sixteen. Where every record pins the key to one constant, the two unions are read at the tag: only records whose constants share a value are read whole, so two unions of sixteen hundred records each answer in about a millisecond.A record is decided against a union of records it splits across as well, by the fixed sequence's rule one kind over: Castagna's backtrack-free split for records, which narrows the record by one member a level, a label at a time.
{"a": int | str, "b": int | str}is below the four records that fix both keys; a record whose tag takes three literals is below the three records that each fix one; and{"a": int, "c?": bool}is below a record requiringcbeside one leaving it out. A member asking for a key the subject leaves free refutes:{"kind": "a" | "b" | "c", "order": int}is decided not below three records fixing the tag where one of them also requires anamount. Its reach is the sequence's -- six fields against their sixty-four corners, seven declining against their 128 (where that bites). A member whose clauses the rule cannot place in the key partition -- a literal key, a key holding part of a kind, two clauses reading one kind -- leaves the pair to the set representation. So does a member the subject's clause forNoneorboolkeys escapes, as far as a refutation goes: those parts hold one key and two, too few for the fresh key the rule's refutation adds to its witness.Read as emptiness, a record minus the records that cover it is empty, one complement at a time, and a record one of them leaves uncovered holds a value: an open record whose key takes sixty-four constants, minus the record of each, is proved empty.
Records met in a meet are one record, their field-by-field meet: a field holds what every record gives its name, through the field or through the clause covering it, and may be missing only where every record lets it be. So the meet of open records is related as one record, below a record and minus records alike, and a member of another shape beside them, a predicate say, leaves a proof standing; so does a record whose clause names part of a kind, an opened record keyed by
1, which the key partition does not hold, beside an emptiness the set representation reads of the rest. The meet holds a value where every field it requires does -- the dict of those fields is in each record -- so a refutation of it stands on that value. A field's meet is a question of its own: a field one record guards to its kind over the JSON values,[T] | ~listmet withjson, the form a translation from JSON Schema writes for anallOfmember narrowing an array's items, meets a field[str]in[str] & [T], since a list of strings is no value of~list. The same holds a level up, where the translation guards the record to objects with~dict, which holds no record. Whether the records hold a value reads the same field meet, so a third record requiring at least one"c"among the tags leaves them none.from typing import Annotated, Any, Literal from annotated_types import MinLen from valgebra import complement, intersection, recursive, union json = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) user = {"id": str, "tier": Literal["free", "pro"], str: json} required = {"tier": Literal["pro", "enterprise"], str: json} pro = {"tier": Literal["pro"], str: json} assert intersection(user, required).relation_to(pro) == "subset" assert intersection(user, required, complement(pro)).is_empty() free = {"tier": Literal["free"], str: json} assert intersection(user, required).relation_to(free) == "not_subset" guarded = intersection(union([Literal["a"]], complement(list[Any])), json) tags = intersection({"tags": [str], str: json}, {"tags?": guarded, str: json}) assert tags.relation_to({"tags": [Literal["a"]], str: json}) == "subset" carries_c = {"tags": Annotated[list[Literal["c"]], MinLen(1)], str: json} assert intersection(tags, carries_c).is_empty() objects = intersection( {"tags": [str], str: json}, union({"tags?": guarded, str: json}, complement(dict[Any, Any])), ) assert objects.relation_to({"tags": [Literal["a"]], str: json}) == "subset"A clause keyed by literals is read one constant at a time, each constant a key the other map reads through its field of that name or through the clause holding it. So
dict[Literal["a"], int]is below{"a?": int}and refuted against{"a?": str}on{"a": 1}, and two mappings keyed by one literal are refuted under it at any depth, as twodict[str, ...]chains are. A record is refuted against a mapping keyed by literals on astrsubclass's key equal to a field's name: the field reads it, since the walk looks the name up, and a literal, which pins the type, does not. -
A difference written as one complemented union.
a ∧ ¬(b ∨ c)anda ∧ ¬b ∧ ¬care one set, and both are decided where either is: no spelling of a difference is the harder one by construction. That is worth stating because the set representation is bounded — a union of dicts, objects or sets holds at most a fixed number of atoms — and complementing a union of n parts multiplies n complements together, which is a width the answer rarely has. A meet against such a union removes one part at a time, so the width the bound sees is the width of the answer rather than of the widest intermediate.The bound stands. A difference wide enough to reach it reaches it, and which of two spellings gets there first depends on the order the parts multiply, so a relation the sets decline under one spelling may be decided under another. No spelling is systematically the one that declines. - A complemented union or meet, as the subject.
¬(a ∨ b)is¬a ∧ ¬b, and¬(a ∧ b)is¬a ∨ ¬b. The subject is read with its complement pushed one level in, and decided where that reading is the supertype or has the supertype among its members, so a complement of a union is below the meet of the complements and below what a complemented member's complement is. Where every decider declines the pair, a complement of a union is asked once more as the meet of the complements, whatever the supertype:¬(¬x ∨ y)belowdictisx ∧ ¬ybelow it, which a member ofxplaces. Emptiness reads a complemented union the same way, so one whose complements, pushed in, meet in nothing as they are built is empty tois_emptyas it is belownothing:from valgebra import Validator, complement, intersection, recursive, union nested = Validator(list[list[int]]) assert complement(union(str, complement(nested))).is_subtype_of(nested) assert complement(union(int, str)).is_subtype_of( intersection(complement(int), complement(str)) ) json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) # str & json_value & ~str, once the complement is pushed in assert complement( union(complement(str), complement(intersection(json_value, complement(str)))) ).is_empty()Only that reading is taken: a complement pushed in and then compared by every rule would be read twice wherever the answer is a decline. - A set split by another, as the supertype.
(r ∧ ¬b) ∨ (r ∧ b)isrwherebanswers alike however often it is asked, so two branches of a union that split one set by another are read as the set they split, and the pair is decided as against that set. It is the shape a guard written once per branch takes:from valgebra import Validator, complement, intersection, recursive, union json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) split = union( intersection(json_value, complement(bool)), intersection(json_value, bool) ) assert Validator(json_value).relation_to(split) == "subset" assert Validator(bytes).relation_to(split) == "not_subset"A split by a predicate is not merged, since a predicate may answer its two occurrences apart. - A length bound over a base that takes any length. A string and a bytes take any, so a bound their lengths admit is met by a value:
Annotated[str, MinLen(1)]is the non-empty string and is decided to have one. A list or a tuple takes any length by repeating one element, so its element answers instead: a bound of zero is met by the empty container whatever the element admits, and a longer one by as many copies of an element as it asks for. A relation reads the same two facts: a list bounded to length zero is the empty list, below every list shape with no prefix whatever its element, and a list shape whose element has a value is refuted below a maximum length by one copy more than the bound lets through, solist[int]isnot_subsetofAnnotated[list[int], MaxLen(1)], on[0, 0]. A set holds each member once, so a bound over one asks how many values its element holds apart:set[bool]underMinLen(3)is empty,set[int]under it has a value, andset[Literal[1, 2]]isnot_subsetofAnnotated[set[int], MaxLen(1)], on{1, 2}, andsubsetofAnnotated[set[Literal[1, 2]], MaxLen(2)]. Literals are counted apart within one kind, since1 == Trueacross two, and an element the rules cannot count declines, but for one member, where its own value is the set's, a value that hashes or has a subclass that does:Annotated[set[tuple[int]], MinLen(1)]isnot_subsetofnothing, on{(0,)}, and a set of a class declines,slicetaking no subclass and hashing on no interpreter before 3.12. A dict's keys are a record's fields, so a closed record's length runs from its required fields to all of them:{"a": int}issubsetofAnnotated[dict[str, int], Len(1, 1)], and{"a": int, "b": int}not_subsetofAnnotated[dict[str, int], MaxLen(1)]. A mapping under bounds that admit its required fields holds the value with those alone, soAnnotated[{"a?": int}, MinLen(0)]isnot_subsetofnothingand of{"a": int}, on{}. A record under a length bound that counts its names is read as the record those leave: a least length counting every name of a closed record requires each, and a greatest length counting its required names admits no other key, soAnnotated[{"a?": int}, MinLen(1)]issubsetof{"a": int}. A bound over every dict, met with records, reads the one record they meet into the same way, which is how a translation from JSON Schema writesminPropertiesandmaxPropertiesbeside an object:{"a": int, str: int} & Annotated[dict[str, Any], MaxLen(1)]issubsetof the closed{"a": int}. A bound counting fewer names than a record has proves nothing of any one of them; a relation takes only proofs through the record, and a refined record's emptiness is read off it. A mapping holds no more keys than its fields and those each clause's key type holds apart, sodict[bool, int]anddict[Literal["a", "b"], int]aresubsetofAnnotated[dict, MaxLen(2)]. A set or a dict bounded to length zero holds the empty ones alone, and is below every set or dict shape of its kind holding each of them, a refinement under bounds that admit zero among them; below a complement it declines. A meet whose members each hold the exact empty one, read off their shapes, is not empty, and a complement holds it where its inner shape refuses it, soAnnotated[dict[str, int], MaxLen(0)] & ~{"a": int}isnot_subsetofnothing, on{}. A set of an element with no value is the empty set alone, and a mapping holds no more keys than its fields and the keys each clause with a value can take, soset[int & str]anddict[str, int & str]underMinLen(1),dict[bool, int]underMinLen(3)and the closed{"a?": int}underMinLen(2)are empty, and so is a meet of such a shape with a length bound it misses,{"a?": int} & Annotated[dict, MinLen(2)]. A bound a mapping's clauses reach is not counted further, and declines. Bounds alone over one base are read as their lengths at any length (the next entry). Met with anything else -- a pattern, an element shape, a second base -- a bound over a list is an automaton with a state per element, and the sets compare two such bounds up to 2,046 elements over a list of integers, where the automaton reaches the state bound; past that they decline. A bound over astrorbytesis there a pattern counting code points or bytes, a few states a code point, and the sets read one up to about 250 code points or 2,000 bytes before its table passes the state bound; past 4,094 the bound is refused before it is built. A tuple or a record holding such a string beside a part only the sets read is read a part at a time, a product holding a value where each part does and none where one part holds none:tuple[Annotated[str, MaxLen(5120)], M], forMthe meet a translation writes for{"type": "integer", "minimum": 0}, isnot_subsetofnothing, on("", 0). A refinement whose base holds a value of every length its bounds admit -- a word, a sequence with a repeated element, a mapping keyed by every name -- is refuted below a bound leaving one of those lengths out, at any length up tosys.maxsize // 128(past it, below, a container is one some interpreter does not build):Annotated[str, MaxLen(256)]isnot_subsetofAnnotated[str, MaxLen(64)], on a text of 65 code points. A base written bare is its refinement under no bound, every length being at least zero, sostrisnot_subsetofAnnotated[str, MaxLen(1000)]anddict[str, int]ofAnnotated[dict, MaxLen(2)]; a set's lengths run to the values its element holds apart, soAnnotated[set[int], MinLen(1)]isnot_subsetofAnnotated[set[int], MinLen(2)], on{0}. A subject holding the empty container of its kind, a refinement under bounds that admit zero among them, is refuted below a supertype refusing it:Annotated[set[int], MinLen(0)]belowAnnotated[set, MinLen(1)], onset(), andAnnotated[dict, MaxLen(0)]below{"a": int}, on{}. A mapping's own lengths leave one out as a written bound does:Annotated[dict, MaxLen(2)]isnot_subsetof{}, on{"a": 1}, and a set's are the values its element holds:set[Literal[1, 2]]isnot_subsetofset[Literal[1]] | set[Literal[2]], on{1, 2}. A union is refused a length its branches each leave out the same way, a branch of another kind leaving out every length, soAnnotated[list[int], MinLen(1)]isnot_subsetofAnnotated[list[int], MaxLen(1)] | Annotated[list[int], MaxLen(3000)], on 3,001 integers. A refinement of a union holds a value where a branch under its bounds does, and is refused a branch's kind the supertype holds none of on that value:Annotated[int | str, MaxLen(1)]isnot_subsetofintand ofnothing, on"". That decides a fixpoint every unfolding of which needs one more element -- each element is a value of the fixpoint, and no finite value satisfies it. A bound over a fixed position, or over a base whose values have no length at all, is not this shape and stays conservative. - A meet of refinements of one base. It is the one refinement holding all their constraints, read so for whether it holds a value, as a refinement of a union reads a branch that is a refinement with what narrows it:intersection(Annotated[dict, MaxLen(2)], Annotated[dict, MinLen(2), MaxLen(3)])isnot_subsetofnothing, by a dict of two entries. A meet over two bases is not this shape:intersection(Annotated[dict[str, int], MinLen(1)], Annotated[dict[str, str], MinLen(1)])staysundecided. - A Boolean term of length bounds over one base. A union, a meet or a complement ofMinLen,MaxLenandLenbounds over onestr,bytes, or list or tuple of one element type that holds a value is the values of that base whose length lies in a union of intervals, and every value outside the base where a complement reaches past it. Two such terms are related as their intervals are, at any length, up to 8,192 nodes nested up to 512 levels, and the meet of one with the other's complement is empty exactly where the one is below the other:Annotated[str, MaxLen(1000)]issubsetofAnnotated[str, MaxLen(64)] | Annotated[str, MinLen(65)], and its meet with that union's complement is empty. A difference holding only lengths pastsys.maxsize // 128declines, as a single bound past it does. - Two schemas that share no value. The inclusion is refuted, whatever either side holds: every value of the subject is outside the supertype. The disjointness read here is the one the concrete types settle -- two distinct builtin scalars, two distinct container kinds -- solist[int]is decided not belowtuple[int, int], and a mapping not below a list. Two records requiring one key, or carrying one attribute, share no value where the two schemas there share none. A subject with no value is the exception the reading catches: it is below both. A class joins the comparison through the bindings, which read the builtin it derives from: a class built ondictholds mappings and nothing else, since a subclass inherits that layout and cannot lay down a second, so a list is decided not below it. A class built on no builtin is not read this way, and the reason is a value: a class deriving from that one and fromstris a string and an instance of it. A meet is read by a member of its own kind, or by a member that is a union of such:(int | float) & ~boolholds numbers whatever bounds its other members carry, so a list of anything meets it in nothing. Two meets are read together where every decider declined the pair: a meet subject with a value is refuted below a meet it shares no value with, so two objects a translation from JSON Schema guards to their kind,OBJ & (~OBJ | R), eachRa recursive record with a tag of its own, are eachnot_subsetof the other. - A kind the supertype holds none of. Every kind is inhabited, so a subject that holds every value of a kind the supertype holds none of is outside it at a value of that kind. The universe holds every value of every kind, and a complement every value of a kind its inner schema holds none of. A union holds none of a kind where each branch holds none, and a reference none where its definition holds none:from valgebra import Validator, anything, complement, recursive, union json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) assert Validator(anything).relation_to(json_value) == "not_subset" # b"" assert complement(json_value).relation_to(json_value) == "not_subset" assert Validator(anything).relation_to(complement(json_value)) == "not_subset" # None -
A pair asked another way. Where every rule declines a pair as it is written, it is asked as the algebra respells it. A difference of the two that holds every value of some kind is a value of the subject outside the supertype, whatever shape the subject has, and against a complement
~cthe pair is also asked as the meet withcbelow the empty set and ascbelow the complement of the subject, and last as that meet read empty the wayis_emptyreads it, a union a member at a time, soanythingis below the complement of a union of members empty to different readings. Against a union holding complements,b | ~c, it is asked as the meet withcbelowb, which is the same question both ways, then as the meet with the union's complement read empty, anddict[anything, anything]in such a union is~~dict, soa <= b | dictis asked asa & ~dict <= b:from valgebra import Validator, anything, complement, intersection, recursive, union json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) # the empty list is a JSON array assert Validator(anything).relation_to(complement([json_value])) == "not_subset" # the dicts below the meet beside them: {} is a dict without "b" with_b = {"b": int, str: anything} meet = intersection( with_b, complement({"a": int}) | complement({"a?": complement(int), anything: anything}), ) assert Validator(anything).relation_to(complement(dict) | meet) == "not_subset" -
A subject outside a base. A refinement is a subset of its base, so a subject the base refutes is refuted against every refinement of it -- the same value settles both. The proof does not carry, since being inside the base says nothing about the constraints, which is why
list[int]belowAnnotated[list[int], MinLen(2)]is left to the set representation whilelist[str]below it is refuted by a rule. - Inclusion in a complement.
Ais below~Bexactly whenAandBshare no value, so the relation is decided wherever emptiness decides disjointness:list[int]is below~int, anddict[str, int]below~str. Two sequences share no value where a position every value of both holds meets in nothing, so[int, None]is below the complement ofrecursive(lambda t: list[t]), whose every item is a list, and a list that may be empty shares[]and is refuted. A length bound names positions as a prefix does:Annotated[list[int], MinLen(1)]is below that complement too. Every sequence of a meet is read at once, so the bound may sit on a member of its own:intersection(list[str], Annotated[list[Any], MinLen(1)], list[rec]), the shape a JSON SchemaminItemsbeside two item types translates to, is empty forreca record over the JSON values, as each pair of its members is not. A meet of sequences is read as the one sequence of its items' meet under all its bounds, sointersection(list[J], union([], list[str]), Annotated[list[Any], MinLen(1)])is refuted below a list of records on["x"], asAnnotated[list[str], MinLen(1)]is. It is read so wherever it stands, as a record's field, a list's items or a mapping's values:intersection(dict[str, J], {"a?": intersection(list[J], union([], list[str]), Annotated[list[Any], MaxLen(5)])}), a closed object with a bounded array property as a translation from JSON Schema writes it, issubsetof{"a?": Annotated[list[str], MaxLen(5)]}andnot_subsetof the same object underMaxLen(4), on five words. This is the semantic-subtyping reduction applied where no structural rule can help — a complement has no shape on the right to recurse into. - Recursion. Equirecursive schemas compare at their greatest fixpoint; the
rule is sound and is witnessed by an independent reference denotation. The
sets are inductive — a guarded fixpoint contains the values built by finitely
many unfoldings — while the comparison assumes its goal and is coinductive;
the two agree because a value is finite. A fixpoint is decided below its own
unfolding, so a
recursiveschema and the body written out around it relate in both directions. A value outside a fixpoint is named where its kind is none of the containers its reference sits beneath:stris not belowrecursive(lambda t: union(Annotated[str, Regex("a")], [t])), which"b"is outside. Where the reference does sit beneath its kind, a value is named if one unfolding holds it with the subject's reference taken as nothing and the supertype's as everything: a protocol whosexisrecursive(lambda t: [t])is not belowint, which an object whosexis[]is outside. A value a second unfolding would place is named where it is a sequence or a mapping of one item:list[str]isnot_subsetofrecursive(lambda t: union(Validator([]), [t]))on["a"]. Where every reading declined a relation, its subject is narrowed through two unfoldings and a value of the difference there is named: the JSON values arenot_subsetofunion(complement(list), Annotated[list, MaxLen(2)])met with them, on[1, 1, 1], which one unfolding cuts to the empty list, and a fixpoint of records met with a class whose instances are mappings holds a value:intersection(recursive(lambda t: union(None, {"next": t})), Node)is not empty, onNode(next=None), forclass Node(dict). Past that it is not named. -
A meet with a recursive reference. A reference denotes its definition, so a meet with one is the definition met with the rest, and a definition that is a union is the union of its branches each met with the rest. The meet of two records then asks the meet of each key's types, which unfolds the reference again where a key names it, and a meet reached again while it is being decided is read as empty: a value is finite, so one that needed a value of the same meet below it would need a smaller one. The meet is its own goal, never the reference's -- the key of
t & {"a": None | {"a": None}}, fort = None | {"a": t}, askst & (None | {"a": None}), which{"a": None}is in, and reading thattas the reference already open would read the meet empty. Emptiness is decided wherever the meet reads, and a value is named where its records meet in one record whose required fields hold values, open or closed:intersection(chain, Validator({"next": None}).open()), which{"next": None}is in, isnot_subsetofnothing. A meet with a class answers"undecided"(below). A reference written inside a key's union, the way a record that names itself is spelled, decides the same way:- A meet of a few unions. A meet holding a union is the union of the meets each branch makes with the rest, so a meet no rule reads whole is read one such clause at a time where its unions span four clauses at most -- the product of their widths, no branch of them a meet or a union. A translation from JSON Schema applies a keyword to its kind alone, so an object schema with two keywords isfrom valgebra import intersection, nothing, recursive, union chain = recursive(lambda t: union(None, {"next": t})) assert intersection(chain, {"next": int}).is_empty() one_value = intersection(chain, {"next": {"next": None}}) assert one_value.relation_to(nothing) == "not_subset" link = recursive(lambda t: {"next": union(t, None)}) assert intersection(link, {"next": {"next": int}}).is_empty()OBJ & (~OBJ | R) & (~OBJ | Q): two unions of two, and each~OBJmeetsOBJin nothing. A branch that is the complement of a member beside its union is dropped before anything is distributed, so any number of keywords on one kind is read as the meet of what they guard: three are eight clauses distributed and one meet narrowed, as a subject as well as alone: the guarded meet is below the record it guards. Two tags fixed two ways meet in nothing, and a tag beside a field it requires holds the dict with that field. Where such a meet is asked below a supertype, a union's branch that is a meet is read in the clause it makes with the members beside it: dropped where one of its conjuncts shares no value with them, its own unions narrowed the same way. A member that is the complement of a union is read as its branches' complements, and one that is the complement of a meet all of whose conjuncts but one are members as that conjunct's complement, where that narrows the meet: within the JSON valuesJ,~(X & J)is the complement ofX. So thenot,if,anyOfandoneOfa translation writes beside an object --not Xas~X & J,if I then Tas(~I & J) | (I & T & J), each keyword guarded to its kind -- are read as the records they hold. A meet of more unions no complement narrows is left to the set representation, and is decided within the depth it descends.- A meet holding a union, asked as its clauses. A meet holding a union is the union of the clauses its distribution writes, so it is below a supertype where each clause is. Where every other reading of a question declines and its subject is such a meet, the question is asked once more with the meet distributed, under steps of its own: the widest union is spread first, and a clause holding a union spreads it in its own turn, so a clause is written only where it is asked. Forfrom typing import Literal from valgebra import complement, intersection, nothing, recursive, union json = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) obj = {str: json} t0 = union(complement(obj), {"tag": Literal["t0"], str: json}) t1 = union(complement(obj), {"tag": Literal["t1"], str: json}) required = union(complement(obj), {"tag": json, str: json}) assert intersection(obj, t0, t1).is_empty() assert intersection(obj, t0, t1, required).is_empty() tagged = intersection(obj, t0, required) assert tagged.is_valid({"tag": "t0"}) assert tagged.relation_to(nothing) == "not_subset" assert tagged.relation_to({"tag": json, str: json}) == "subset" def negated(schema): return intersection(complement(schema), json) twice = intersection(obj, negated(negated(required))) assert twice.relation_to({"tag": json, str: json}) == "subset" named = union(complement(obj), {"n": json, str: json}) if_t0_then_named = union(negated(t0), intersection(t0, named, json)) held = intersection(obj, t0, if_t0_then_named) assert held.relation_to({"n": json, str: json}) == "subset"a = recursive(lambda t: union(None, [t])),(a | str) & (a | bytes)is belowa: the clause besideaby that member, andstr & bytesbecause it is empty, though construction leaves it a meet. The distribution costs the product of the unions' widths, and asked last it spends nothing on a question another reading decides. -
The complement laws, where the constructors reach them.
complementcancels a complement,unionfolds a join carrying a schema beside its own complement, andintersectionfolds the meet of that pair, all where the schema is built. Socomplement(complement(int))isint— one schema, whichreprand==report and which a comparison is never asked about —int | ~intisanything, andint & ~intisnothing.complement(complement(X))folds whateverXis. The two folds over a pair read two occurrences of one schema as one set, so they decline wherever the constructor cannot see that it is one: a schema holding a predicate or any class,list[C] | ~list[C]included. The constructor holds no class object to ask whether a metaclass hook answersisinstance—Schema::union_withinandSchema::meet_withinincrates/valgebra-core/src/ir.rspassNoLeafRelations, anddenotes_a_set_withinincrates/valgebra-core/src/oracle.rsreads a class as a set only on the oracle's word. A plain class denotes a set all the same, and the law holds of it:intersection(C, complement(C))keeps its spelling andis_empty()decides itTrue. A recursive schema is a set where its definition is one, to the decision as to construction, so a class inside the definition does not stop the law: the meet ofrecursive(lambda t: union(complex, [t]))with its complement is empty. A union holding a union beside that union's complement folds too, since construction reads the flattened members:int | str | ~(int | str)isanything. The decision procedure has no rule for a folded shape and never meets one built this way. A shape the folds do not reach is the relations' to decide.
from typing import Annotated, Any
import annotated_types as at
from valgebra import Validator, complement, intersection, recursive, union
assert Validator(bool).is_subtype_of(int) # bool is a subtype of int
assert Validator(1).is_subtype_of(int) # a literal is a member of int
assert Validator(Annotated[int, at.Ge(0)]).is_subtype_of(int) # refinement <= base
assert Validator(Annotated[int, at.Ge(10), at.Le(0)]).is_empty() # no such int
assert Validator(
Annotated[int, at.Gt(0), at.Lt(1)]
).is_empty() # no int strictly between
assert not Validator(Annotated[float, at.Gt(0), at.Lt(1)]).is_empty() # 0.5 is between
assert Validator({str: int}).is_subtype_of({str: int, int: bool}) # mapping clauses
assert Validator({str: int}).is_subtype_of(
{"b?": int, str: int}
) # optional field, catch-all covers it
assert Validator({"x": int}).is_subtype_of(
{str: int}
) # a closed record below a catch-all mapping
assert Validator(list[int]).is_subtype_of(
complement(int)
) # inside a complement: a list shares no value with an int
assert Validator(tuple[int | str, int]).is_subtype_of(
tuple[int, int] | tuple[str, int]
) # a product splits across branches
assert Validator(
recursive(lambda t: Annotated[list[t], at.MinLen(1)])
).is_empty() # every unfolding needs one more element
assert intersection({"a": int}, {"a": str}).is_empty() # 'a' cannot hold both
assert not intersection(
{"a?": int}, {"a?": str}
).is_empty() # the empty dict is in both
assert Validator(bool | int).is_equivalent(int) # bool | int is just int
assert intersection(int, complement(int)).is_empty() # the complement law
assert intersection(
list[int], complement(list[int])
).is_empty() # complement law, structurally
assert intersection(
list[int], set[int]
).is_empty() # disjoint kinds: a list is never a set
assert intersection(
Any, complement(Any)
).is_empty() # Any is the top, spelled, so the law reaches it
json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j}))
assert json_value.is_valid({"a": [1, "x", {"b": None}]})
The one assumption: a class the bindings can read has an instance¶
Every other answer here rests on the value model alone. This one rests on an
assumption, and it is the only place a "not_subset" can be wrong. No True
can: a proof is a proof, and the assumption is only ever read to believe a
refutation.
A class is opaque: what it holds is isinstance, and the library reads the
class hierarchy rather than running it. A class whose metaclass leaves
isinstance and issubclass alone is taken to hold at least one object,
which is what lets A be reported not below B for two classes neither
deriving from the other -- the difference A ∧ ¬B is read as holding a value.
A class no value can instantiate (a __new__ that always raises, an abstract
class with no concrete subclass) is empty, and is below everything; the library
reports it not below, because the assumption says otherwise.
It licenses one object, not one per kind. A class that lays down no builtin
layout confines its instances to no kind, so it constrains values of every
kind: a subclass of it may derive from str as easily as from nothing. That
placement is right for inclusion -- Plain is not below the complement of
int -- and it is not a value. An integer that is an instance of Plain
exists only if some class derives from both, and which classes exist is not
something a snapshot of the order can say. So Plain against the complement of
a kind is undecided, and the same in reverse:
from valgebra import Validator, complement
class Plain:
pass
class Laid(str):
__slots__ = ()
assert Validator(Plain).relation_to(complement(int)) == "undecided"
assert Validator(int).relation_to(complement(Plain)) == "undecided"
# A class laid out as the kind is the case this is not conservative about:
# every instance of it is a string, so it has a value on that line.
assert Validator(Laid).relation_to(complement(str)) == "not_subset"
assert Validator(Laid).relation_to(complement(int)) == "subset"
The assumption is the set representation's open world, which both readings share. Neither decides it; the bindings could not answer it without running a constructor at decision time, which is the same code the pure-metaclass test exists to refuse. What it buys is every relation between two classes decided by a rule, without building a set representation.
A declared attribute does not widen this. A dataclass compiles to the
class beside a record of its fields, and the record narrows the class's
instances rather than reaching outside them. A NamedTuple compiles to the
class met with the tuple its fields lay out, with no record beside it: it is
laid out as tuple and decides as a kind does, and a protocol over its fields
is not proved above it. So a relation that declines beside one declines for the
class: int ≤ ~C is "not proven" for a dataclass and for a class with no
fields alike, and a class laid out as a kind decides either way. The record is
not a second source of conservatism, and in the one place it tells two schemas
apart it makes a refutation reachable that the class alone leaves open. A
Protocol is the record with no class beside it, and relates as records do: a
dataclass declaring its members, each at least as narrowly, is below it, and a
protocol with more members is below one with fewer. Against a builtin kind it
declines in the direction that would stand on a value of the kind: an exact
int carries no __dict__, and whether it has an attribute is int's own
namespace -- it has a real, it has no x -- which the relations do not
hold, so int against a protocol of x is undecided though 1 fails it.
The object carries only what its class leaves room for. The one object the
assumption licenses is a direct instance of the class, and a refutation about
a class met with a record stands on that instance holding a value in each
field. The class decides whether it can, read off the namespaces of its
__mro__ once per relation: a name defined as a property or another data
descriptor holds what its getter returns, a name defined any other way cannot
be missing, an instance laid out without a __dict__ holds nothing its slots
do not name, a __getattribute__ other than the generic lookup answers every
lookup, and a __getattr__ answers every lookup that finds nothing -- so beside
one an unset slot or a name the __dict__ lacks is never missing, and a name
neither can hold is the hook's answer alone. Where the class leaves no room,
the pair is undecided: a subclass may carry the record, and may not exist.
A dataclass whose field is a descriptor, or which defines __getattribute__,
is where an annotation reaches it:
from dataclasses import dataclass
from valgebra import Validator
@dataclass
class Plain:
x: int
@dataclass
class Traced:
x: int
def __getattribute__(self, name: str) -> object:
return super().__getattribute__(name)
assert Validator(Plain).relation_to(Validator(str)) == "not_subset"
assert Validator(Traced).relation_to(Validator(str)) == "undecided"
Sound but conservative¶
Here valgebra is correct but not complete: it may answer False or "not empty"
for a relation that does in fact hold.
A negative answer is one of two different things, and relation_to tells
them apart where the boolean methods do not. A relation can be refuted --
there is a value of the one schema outside the other, so the answer is False
and will stay False however much the procedure improves -- or declined,
which is the list below: nothing was found either way, and the same query
decides once the representation reaches it. The three relations answer with all
three values inside the core. is_subtype_of, is_equivalent and is_empty
map both negatives to False, because False is what their contract promises;
relation_to reports the two apart, "not_subset" for a refutation and
"undecided" for a decline. What the split buys is that "not proven" is
countable: a rule that begins refuting a relation the procedure declines is a
change the tests see rather than one that hides behind an unchanged False.
The list is short, and it is short for one reason. Two representations answer
these questions. The rules recurse over the schema tree, and where they
decline the descriptor is asked: it holds each kind as a set, so a ≤ b is
a ∧ ¬b = ∅ and the answer comes out of the sets rather than out of a rule about
the shape. What is left below is what the descriptor cannot hold.
-
A clause keyed by part of a kind. The set representation partitions a dict's keys by kind and gives each part its own default, so a clause whose key is a kind, a literal, or a union or complement of kinds lands in parts:
complement(str)opens every other kind and the part for a key of no listed kind, a class instance. Astrnarrowed by a pattern or a length, and the connectives over those, names a regular language, and thestrpart is split by it: two clauses overlap and the map reads the join of their values on the refinement of their keys, sodict[Annotated[str, Regex("x-.*")], str]is decided againstdict[str, str], a record namingx-aand another clause's keys, as a key narrowed by no pattern is. A word is one key to these, which the soundness page assumes of astrkey whose hash and==are its text's. A key holding any other part of a kind has no part to land in -- a tuple or a frozenset of narrower elements; a class; the complement ofLiteral["a"], which holds astrsubclass's key equal to"a"and not the exact one, where a label holds both -- and the lowering declines rather than approximating, so a relation about such a map is left to the rules. They refute one key kind at a time: a kind the subject's clause holds whole, read by one of the supertype's clauses or by none, names a key whose entry the two maps judge apart, so{str: int}.open()is outside{str: int}on{7: "x"}. They prove a clause below the supertype where one of its clauses holds the key and the value, or where the clauses holding the value hold the key between them, sodictis below{Literal["a"]: anything, complement(Literal["a"]): anything}. What comes back "not proven" is a refutation whose supertype reads a key kind in part, or with two clauses at once, where no guess holds the key that refutes it:{complement(Literal["a"]): int}against{Literal["b"]: str, complement(Literal["b"]): int}, which{"b": 1}refutes. A refutation a guess does reach is decided, by the value aimed outside the other schema that the decided list names.The partition is the source's: it treats a record as a quasi-
K-step function, whereKis a predefined finite partition of the key domain and the catch-all is split across its parts, and it forbids overlapping domains in one map as "both a design and an implementation choice". A union of parts is a domain it admits, and a complement of whole kinds is the union of the other parts. A key holding part of a kind is not, and it may overlap another clause: the source says a theory of maps with overlapping domains is possible, and that comparing two records under it needs the machinery for comparing intersections of arrow types. Words escape that: clauses here read disjunctively, and languages have a common refinement, so two maps meet in one step function. valgebra admits every other such key where the source has no part for it: the walk reads it exactly, and the comparison it needs is not built. That is a gap rather than a refusal, and what it costs is the refutation a pair needs where a key kind is read in part -- which comes back "not proven" though one dict settles it:from typing import Literal from valgebra import Validator, anything, complement not_str = complement(Validator(str)) free_the_rest = Validator({str: int, not_str: anything}) # The walk is exact: membership never goes through the set representation. assert free_the_rest.is_valid({"a": 1, 7: "anything at all"}) assert not free_the_rest.is_valid({"a": "not an int"}) # A complement of a whole kind is the other kinds, and the sets decide it. assert Validator({str: anything, not_str: anything}).is_equivalent({object: object}) # A key kind the supertype reads one way refutes: `{7: "x"}`. assert Validator({str: int}).open().relation_to({str: int}) == "not_subset" # A complement of a literal holds part of `str`. The clauses holding a value # hold every key between them, so this admits every dict, and is proved to. not_a = complement(Validator(Literal["a"])) long_way = Validator({Literal["a"]: anything, not_a: anything}) assert long_way.is_equivalent(dict) # A refutation needs the part a key falls in: `{"b": 1}` is in one, not the # other, and no guess holds the key "b". part_of_str = Validator({not_a: int}) not_b = complement(Validator(Literal["b"])) by_b = Validator({Literal["b"]: str, not_b: int}) assert part_of_str.is_valid({"b": 1}) and not by_b.is_valid({"b": 1}) assert part_of_str.relation_to(by_b) == "undecided" # Where a guess holds the key, the pair is refuted: `{"aa": 0}`. by_kind = Validator({str: str, not_str: int}) assert part_of_str.relation_to(by_kind) == "not_subset"This is the shape
openwrites on a mapping: freeing the key-types a clause leaves over means a clause over the complement of the ones it claims, which is whole kinds fordict[str, int]and part of one fordict[Literal["a"], int]. Opening a record stays decided, because the regions it frees and the ones its clauses claim cover every key with one value between them, which is one catch-all clause rather than two. -
A clause keyed by a float literal. The partition names a literal key by its value, and it holds no float value: the typing spec admits none in a
Literal. A map keyed byLiteral[1.0]is left to the rules, which read a key by whole kinds: they refute where the literal holds none of a kind the other map's key holds. A pair they do not decide is refuted where a value guessed from the subject is the counterexample --{0.5: 0}fordict[float, int]-- and comes back "not proven" where none is, since a guess reads a refinement as its base:{0.5: 5}refutes the bounded map below, and the guess{0.5: 0}is no value of it. A key literal of any other kind lands in its part.from typing import Annotated, Literal from annotated_types import Ge from valgebra import Validator keyed_by_a_float = Validator(dict[Literal[1.0], int]) assert Validator(dict[int, int]).relation_to(keyed_by_a_float) == "not_subset" assert Validator(dict[float, int]).relation_to(keyed_by_a_float) == "not_subset" bounded = Validator(dict[float, Annotated[int, Ge(5)]]) assert bounded.relation_to(keyed_by_a_float) == "undecided" assert Validator(dict[Literal[1], int]).relation_to(dict[int, int]) == "subset" -
Recursion, past one unfolding. A fixpoint as the supertype costs a refutation rather than an inclusion, and that is the sharper half.
a ≤ bisa ∧ ¬b = ∅, so the supertype is where a schema stands under a complement, and a reference there is lowered to the bottom. The difference then contains the value that refutes the inclusion without being proved to contain it. A value guessed from the subject refutes it where the guesses reach, three containers deep; past them the answer is "not proven" where a value says plainly that it is false:from valgebra import Validator, complement, intersection, recursive, union chain = recursive(lambda t: union(None, {"next": t})) off_chain = Validator({"next": intersection(dict, complement(chain))}) assert not Validator(chain).is_valid({"next": {}}) # the walk is exact assert off_chain.is_valid({"next": {}}) assert off_chain.relation_to(chain) == "not_subset" # {"next": {}} is guessed deeper = Validator({"next": {"next": {"next": {"next": off_chain}}}}) assert deeper.is_valid({"next": {"next": {"next": {"next": {"next": {}}}}}}) # and past the guesses' depth the relation declines rather than refuting assert deeper.relation_to(chain) == "undecided"One unfolding does reach the kinds a fixpoint admits, and a subject that holds every value of a kind the fixpoint holds none of is refuted on them:
complement(int)holds every string and the chain holds none, so it isnot_subsetof the chain at"a", and so is a meet of complements holding every string. The pair above holds no such kind: its values are dicts, a kind the chain holds some of, and which of them are in the chain is a question two levels down.What the rules reach is narrower than that and is reached: a branch of a union the subject shares no value with is dropped before the rest is asked, so a chain of records beside a
Nonebranch is refuted by the record branch alone. Where every branch goes that way the subject is outside the whole union, which is a refutation rather than a decline as long as the subject holds a value at all. And a fixpoint's own unfolding is below it however its body is spelled: a member that is a meet is not placed by any member of the meet, so the reference is unfolded for it and the meet is read as the branch of the definition it is.from valgebra import Validator, intersection, recursive, union meet = intersection(int, union(float, bool)) tree = recursive(lambda t: union(meet, list[t])) assert Validator(union(meet, list[tree])).relation_to(tree) == "subset" assert tree.relation_to(union(meet, list[tree])) == "subset"The record rule refutes a map whatever the supertype's recursion. It reads one key kind at a time, and where the subject's clause holds a kind whole, a value the supertype's clause for that kind refuses -- or any value, where no clause of the supertype reads the kind -- makes an entry the two maps judge apart. So
{str: bytes}is outside a JSON schema on{"a": b""}, anddicton{7: None}, whose key no clause of it reads.from valgebra import Validator, recursive, union json_value = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) assert Validator({str: bytes}).relation_to(json_value) == "not_subset" assert Validator(dict).relation_to(json_value) == "not_subset"Branches are dropped where one of them refutes, which is the answer the narrowing carries back from the branch it leaves. A union no branch of which refutes narrows to a smaller union of declines, so the readings that drop branches -- a meet per branch, on the path already headed for the set representation -- are not spent on it, and the pair goes to that representation instead. What that gives up is the union whose branches the subject shares no value with and which none of them refutes: it is outside the union and is answered
"undecided". Reaching for it on every union adds a reading per branch to every union the decision path meets, whichscripts/perf_gate.py --decision-matrixmeasures.The other half is the lowering. A reference is a cycle and a finite set representation has no room for one, so a recursive schema is lowered by unfolding its body once and putting a bound where the reference was — the top where the schema is used positively, the bottom under a complement, which is what keeps a difference sound. That decides everything about the kinds a fixpoint admits:
bytesshares no value with a JSON value, andbytesis below its complement. What one unfolding does not reach is a relation that needs the body twice — a fixpoint below a differently-written fixpoint whose bodies only agree after two steps — and there the coinductive rule is the whole of the answer.An unfolding spends depth. The fixpoint's body sits one level below every member that names it, so a member met with a recursive universe under a complement nests deeper than the rest. What the depth a build descends bounds is the containers it starts: a scalar past it is read by its kind's regions, and a cut reference is one, so
str & ~(str & json)is proved asstr & ~jsonis. The regions are intervals over the reals, so an integer bound past the depth is not rounded in a reading of the pair whole; a goal is read alone where everything else declined, one holding a reference where a meet, a union or a complement tops it, soAnnotated[int, Gt(4), Lt(7)]issubsetofAnnotated[int, Ge(5), Le(6)]at any depth. A container past the depth is not built: beside the members a proof needs, its member is left out of the reading and the proof stands, as a predicate is, and where it is the member the proof needs, the relation declines.- A length bound over a set or a dict, in the sets. A length is not a word's alone, and two of the kinds that have one state it: a word's length is a pattern over its alphabet, and a sequence's is "any element, that many times", which the automaton holds like any other shape. Sofrom valgebra import complement, intersection, nothing, recursive, union json = recursive(lambda j: union(None, bool, int, float, str, [j], {str: j})) assert intersection(str, complement(json)).relation_to(nothing) == "subset" nested = intersection(str, complement(intersection(str, json))) assert nested.relation_to(nothing) == "subset"Annotated[tuple[int, int], MinLen(3)]is decided empty andAnnotated[list[int], MaxLen(0)]is the empty list. A set and a dict have a length their components do not count, and a bound over one of those refuses rather than being lowered as if it did. What the rules read of one -- whether a set under a bound has a value, the lengths a set's element and a record's fields keep to, and a length a supertype's bounds leave out -- is the bullet on a length bound above. What they do not read is which members a length leaves:Annotated[set[Literal[1, 2]], Len(1, 1)]holds{1}and{2}alone and is belowset[Literal[1]] | set[Literal[2]], and the pair answersundecided. -
A set that needs two members Python's
==makes one. A set ofint | stris not belowset[int] | set[str]:{1, "a"}is in neither. That refutation stands on two members, and a Python set holds no two that compare equal --{1, True}is{1}, and so is{1, 1.0}. So a set refuted only by a member of each, where those members are one number in two kinds, is undecided rather than refuted:set[Literal[1, True]]is belowset[Literal[1]] | set[Literal[True]], since every set of it holds one member, and that pair answersundecided. Two members==keeps apart -- anintand astr, two integers, or two number kinds with other numbers to choose, asfrozenset[int | float]against the frozensets of each -- are refuted. -
An integer bound past 120 bits. The integer component carries its bounds within
2**120of zero, which holds every 64-bit limit a JSON generator writes,2**63as JavaScript prints it and the largest unsigned one included, soGe(2**70)againstGe(2**70 + 1)is refuted on2**70. Past it a bound declines: the schema validates exactly -- membership reads the Python integer -- andGe(2**121)againstGe(2**121 + 1)isundecidedin the direction a value refutes, andsubsetin the direction the carrier proves. Python's integers are unbounded and the carrier is not, which is a property of the representation rather than of the schema. A constant, a key and a step are still read as ani64. -
A length past the one every interpreter builds. A container holds its items in one allocation, which the allocator refuses past
sys.maxsizebytes whatever the memory, so each kind stops short ofsys.maxsizeby its item's size: CPython builds no list longer thansys.maxsize // 8, and no set past about a fifty-third of it. A refutation names a value, and one standing on a longer list stands on none. So a relation or an emptiness whose witness is longer thansys.maxsize // 128, a length every kind reaches on every interpreter the package supports, declines:list[int]belowAnnotated[list[int], MaxLen(sys.maxsize // 8)], which no list escapes, isundecided, and so isAnnotated[list[int], MinLen(sys.maxsize // 8 + 1)]againstnothing. Up to that length the witness stands:list[int]isnot_subsetofAnnotated[list[int], MaxLen(sys.maxsize // 128 - 1)]. -
Two moduli
%reads in different kinds of number. Dividing is a fact about the steps, and%asks it of a value in the kind the value and the step meet in.2**53 + 1is a multiple of4.0, because%reads it as the float2**53, and not of2, which divides4.0.2.0**53is a multiple of2**53 + 1, which%reads as the same float, and not of3, which divides that step.Decimal("2E+28")is a multiple of4and raises against2, because its quotient by2outgrows the context's precision. So a pair of steps of two kinds, a step past2**53overfloat, and a base holding values of any other type -- aDecimal, aFraction,object-- declines. -
A meet of two moduli the representation cannot hold. A
MultipleOfbecomes a residue class, and a class is materialized per residue up to a recorded period. Two steps meet at the period they share, soMultipleOf(64)withMultipleOf(81)is the multiples of 5,184 -- past the period although both steps are well inside it -- and a relation that turns on that meet declines. A rounded period would be wrong in one direction or the other, so it refuses instead.The inclusion between two moduli does not go that way and is decided above: the steps settle it between them, whatever their size, and so does the refutation where the subject's constraints are its step and integer bounds,
MultipleOf(2500)being outsideMultipleOf(5000)at 2500. What the period still bounds is a refutation the subject's other constraints take part in -- a float bound beside the step, or a meet of two steps -- since the value has to satisfy them too and naming it takes the residues. -
A fractional step over floats. The float component holds whole steps. A fractional one reads a finer grid, and most name a grid no table holds:
0.1is an odd number times2**-55, so its period is past any bound. A fractional step is read by the rules against another step and otherwise declines, so no multiple of0.5lies strictly between 0 and0.5, and that meet is not proved empty, where the meet over a whole step is.from typing import Annotated import annotated_types as at from valgebra import Validator, nothing halves = Annotated[float, at.MultipleOf(0.5), at.Gt(0), at.Lt(0.5)] wholes = Annotated[float, at.MultipleOf(1), at.Gt(0), at.Lt(1)] assert Validator(halves).relation_to(nothing) == "undecided" assert Validator(wholes).relation_to(nothing) == "subset" -
A word boundary inside a pattern. A pattern matches the whole text, so a
\bor\Bat either end of it asks about the first or the last character alone, and is read as that:\bab\bis the setabis. One between two parts of a pattern asks about the characters on both sides of a position, which the set representation's automata do not read, so a relation turning on it declines --a\bbincluded, although no string matches it. -
A pattern too large to build. A counted Unicode class under a repetition,
(?:\w{3,4})+, is past the size an automaton is built to, and the set representation does not hold it. A pattern of at most 64 texts on the other side is read a text at a time, each put to the validator's own matcher as a literal is, and a pattern of more by a guess at one text of it -- each repetition its fewest times, each class its first character -- which names a value where the matcher admits it and nothing where it refuses, which is whya\bbabove staysundecided. A proof needs every text, and a supertype that judges astrby more than its text -- a literal, a class, a predicate -- proves nothing this way.from typing import Annotated from valgebra import Regex, Validator, nothing wide = Annotated[str, Regex(r"(?:\w{3,4})+")] assert Validator(Annotated[str, Regex("a")]).relation_to(wide) == "not_subset" assert Validator(Annotated[str, Regex("abc|abcd")]).relation_to(wide) == "subset" assert Validator(wide).relation_to(nothing) == "not_subset" -
A schema too large to build. The descriptor is bounded three ways: the nodes it will read, the depth at which it will still start a container, and the work a build may spend. Past any of them it refuses, and the caller keeps the rules' answer. None of these is a statement about the schema -- the same schema decides under a larger bound -- and each exists because building a descriptor beside a verdict the rules already reached is work whose result is discarded. Every bound is a row of the architecture table in the repository, with the gate that measures it beside it.
Where that bites is width. A record whose fields each take two types is the union of the records that fix every field, and the record rule splits it across them as the product rule splits a tuple, so the two reach as far: six fields against their sixty-four corners are decided, and seven against their 128 spend the decision budget before the split finishes, with the difference past every bound a lowering has. The shape is the first an ordinary annotation reaches, so it is the number to know:
from valgebra import Validator, union
def with_corners(width):
names = [f"f{i}" for i in range(width)]
corners = union(
*[
{name: (int, str)[mask >> i & 1] for i, name in enumerate(names)}
for mask in range(1 << width)
]
)
return Validator(dict.fromkeys(names, int | str)), corners
six, corners = with_corners(6)
assert six.relation_to(corners) == "subset"
seven, corners = with_corners(7)
assert seven.relation_to(corners) == "undecided"
The seventh field's undecided is the conservative answer and not a claim
about the relation: it holds, and proving it takes a larger budget.
A union is asked a part at a time where the pair is past a bound whole and
the rules declined it with steps left. A union subject is below a supertype
where each member is and outside it where one member is, so each member is
asked on its own; a union supertype is first narrowed to the branches the
subject shares a value with. A meet supertype is
asked a member at a time too: int is outside Ge(0) met with a predicate,
-1 being outside the first member whatever the predicate says. A record
against a record is asked a shared field at a time, so one field outside its
counterpart refutes the pair however many fields stand beside it -- two hundred
guarded fields are past the node bound as a pair. Records told apart
by a tag meet one branch each, so a union of them is decided a record at a
time, as wide as the rules leave steps for: forty and two hundred records are
refuted below the same shifted, and five hundred are undecided, the rules
having spent the budget on the pairs of tags. A pair whose steps are spent
asks no part, since every part is a reading the steps do not count:
from typing import Annotated, Literal
from annotated_types import Ge
from valgebra import Validator, union
def tagged(width, shift=0):
return union(
*[
Validator({"type": Literal[f"t{i}"], "v": Annotated[int, Ge(i + shift)]})
for i in range(width)
]
)
# refuted at {"type": "t0", "v": 0}
assert tagged(40).relation_to(tagged(40, shift=1)) == "not_subset"
assert tagged(40, shift=1).relation_to(tagged(40)) == "subset"
A union against a union is not asked a branch at a time: a member that lands
in one branch of a supertype too wide to build is left undecided, since
asking every member against every branch is the product of the two widths.
Two schemas sharing no value are asked as one below the other's
complement, a.relation_to(complement(b)), which needs no meet of the two
to be built. Two schemas near the node bound can each build where their
meet is past it -- intersection(a, b) raises ValueError -- and the
relation still returns, undecided where deciding it needs the meet's set.
An is_disjoint(a, b) entry point would answer the same undecided, so
there is none:
from valgebra import Validator, complement
assert Validator(list[int]).relation_to(complement(str)) == "subset"
assert Validator(int).relation_to(complement(float)) == "subset"
-
A predicate. Its satisfiability is undecidable (below), so neither representation reasons about one -- and that is a statement about the predicate, not about every pair carrying one. A refinement is a subset of its base, so what surrounds the predicate still decides: a bounded integer against a predicate-refined list is refuted by the kinds, a list against its own bounded-and-predicated refinement by the empty list the bound leaves out, and a dataclass against a union with a predicate-refined branch by the kind that branch names. What the predicate costs is the other direction. A refutation stands on a value of the subject, and a subject carrying a predicate is never proven to have one, so the same pair reversed is undecided:
Annotated[int, Ge(0)] <= Annotated[list[int], Predicate(f)]is refuted and its converse is not.A predicate beside the members of a meet hides none of their emptiness: the meet is below the members it holds, so where they share no value neither does the meet, and two patterns no string matches both of stay apart beside a predicate, whether written as three members or as one
Annotatedholding all three. That is a proof of emptiness only: the meet without the predicate holding a value says nothing of the meet with it.
tests/test_completeness_ledger.py is where a relation that leaves this list
lands: it enumerates what the procedure must decide and fails in both
directions, so a relation that regresses to conservatism fails there and one
that becomes decided is added there. It also carries a strict expected-failure
mark for a relation that holds and is not decided, so the row fails on the day
it decides. Those rows are the bound-limited relations above — the seven-field
record and the seven-component tuple against their corners, each carrying the
width at which the budget stops it — and the two sets whose members are one
number in two kinds; the ledger's _LEDGERED list owns them.
from typing import Annotated, Literal, NamedTuple
import annotated_types as at
from valgebra import (
Regex,
Validator,
complement,
intersection,
recursive,
union,
)
class Pair(NamedTuple):
x: int
y: int
# A length bound over a set or a dict is opaque to the sets: their
# representations do not count one. The rules count what the shapes keep to, a
# set's members from its element's values and a record's keys from its fields.
# Over a word or a sequence it is decided.
assert not Validator(Annotated[set[int], at.MinLen(3)]).is_empty()
assert Validator(Annotated[set[bool], at.MinLen(3)]).is_empty()
assert (
Validator(set[Literal[1, 2]]).relation_to(Annotated[set[int], at.MaxLen(1)])
== "not_subset"
)
assert Validator({"a": int}).is_subtype_of(Annotated[dict[str, int], at.Len(1, 1)])
assert Validator(Annotated[tuple[int, int], at.MinLen(3)]).is_empty()
# A named tuple's positions are its fields, and the schema says so, so the
# relation is structural.
assert Validator(Pair).is_subtype_of(tuple[int, int])
# A recursive schema: the laws reach it, and one unfolding decides the kinds its
# body admits. A relation needing the body twice is the coinductive rule's: a
# tree of lists of lists is an integer tree, and `[1]` is an integer tree that
# is not one.
mu = lambda: Validator(recursive(lambda t: union(int, list[t]))) # noqa: E731
nu = recursive(lambda t: union(int, list[list[t]]))
assert intersection(mu(), complement(mu())).is_empty()
assert intersection(mu(), str).is_empty()
assert Validator(nu).is_subtype_of(mu())
assert mu().relation_to(nu) == "not_subset"
# Everything else here decides, on the sets or by a rule.
pattern = Validator(Annotated[str, Regex("a")])
assert pattern.is_subtype_of(Annotated[str, Regex("ab?")]) # L(a) <= L(ab?)
# L(a) is the word "a", and a `str` subclass's "a" is in the pattern and not the
# literal, which pins the exact type.
assert Validator(Literal["a"]).is_subtype_of(pattern)
assert pattern.relation_to(Literal["a"]) == "not_subset"
assert Validator(Annotated[int, at.MultipleOf(4)]).is_subtype_of(
Annotated[int, at.MultipleOf(2)]
)
assert Validator(bool).is_subtype_of(Annotated[int, at.Ge(0)])
assert Validator(bool).is_subtype_of(Literal[True, False])
assert Validator(dict[Literal["a"], int]).is_subtype_of({"a?": int})
# A respelling denotes the same set, and the sets are what the relation reads --
# even though the laws construction settles do not reach this one. `A | (A & B)`
# is `A` by absorption, one case of `A | B` folding to `A` wherever `A` contains
# `B`; that fold needs a containment, and containment is the decision rather
# than a law.
record = Validator({"a": int})
respelled = union(record, intersection(record, Validator(str)))
assert respelled != record
assert record.is_subtype_of(respelled)
assert respelled.is_subtype_of(record)
Two instruments hold this list to the tree. tests/test_completeness_ledger.py
carries each relation above as a decided one, written the way a caller writes it
rather than built from the other operand — a distinction that matters, because
the shortcuts the procedure takes are keyed on two schemas sharing their
constants. An entry of the list above that stops deciding fails there as a
defect rather than a known gap; its strict expected-failure marks are for the
other direction, a relation that holds and is not decided, each naming the
limit that leaves it. tests/test_completeness_probe.py
searches a fixed universe for relations answered False that no value refutes
and fails when one appears without a written reason, so a gap nobody thought of
cannot arrive unnoticed. It reaches a gap only where some atom in its universe
reaches it, which is why that universe carries both constraint families, a
fixpoint beside its own unfolding, and a record beside a literal-keyed map.
A sequence below a union of sequence schemas it splits across, where no single
branch contains it, is decided by the set representation's symbolic automaton
(crates/valgebra-core/src/descr/symbolic.rs): tuple[int, ...] is below
tuple[()] | tuple[int, *tuple[int, ...]]. What has no syntax is the rest of
regular-expression-types inclusion — a repeated heterogeneous group, such as
int and str alternating to any length — because the sequence node carries
the linear prefix-and-tail form, so no schema valgebra builds takes that shape.
A goal a rule reaches beneath a constructor is read by the set representation on
its own, where a reference beside it stopped the pair's reading: tuple[bool, R] is
below tuple[Annotated[int, Lt(8)], R], and {"a": Annotated[str, Regex("a")], "b": J}
below the same record over Regex("[ab]"), for R and J recursive, as the two would
be with neither beside them. Such a goal holds no reference itself.
A supertype proved empty is the bottom: str is not_subset of a protocol whose y
is itself, which no finite value is in, as it is of nothing.
Below a union holding a recursion, where the set representation's unfolding reads
no answer, a sequence or a mapping is refuted on a value of one item: list[bytes]
is not_subset of J | list[J], for the JSON value J, on [b""]. The item below
the union of what the branches hold at one position decides nothing, since
[1, "s"] is in list[int | str] and in neither of list[int] and list[str].
Undecidable at runtime¶
These have no decidable runtime membership, so valgebra rejects them with a clear message or treats them opaquely — it never guesses.
- Erased generics and type variables. A
TypeVar,Generic[T],ParamSpec, orTypeVarTupleis rejected; a runtime value carries no binding for a free type variable. - Abstract-collection generics.
Sequence[int],Mapping[str, int], andIterable[T]are rejected; checkingIterableelements would consume the iterable, andstr/bytesare themselves sequences. Use a concrete container —list[int],tuple[int, ...],dict[str, int]— or the bare abstract type for anisinstancecheck. - Callable signatures.
Callable[[int], str]checks only that the value is callable; a function does not expose its argument and return types at runtime. -
Predicates. An
Annotated[T, predicate]runs the predicate at validation time; its satisfiability cannot be reasoned about (Rice's theorem), so nothing is inferred from it and two refinements relate through a predicate only when they carry the same one.A decision query may nonetheless call it. Deciding whether a literal is a subtype of a refinement is deciding whether that literal's value belongs to it, and belonging runs the predicate — so
is_subtype_ofandis_equivalentexecute user code, asis_emptyexecutes a rich comparison when it orders two refinement bounds. A predicate with side effects, or one that is slow, is one a type query pays for. The constant speaks for its literal only where it is the literal's one value:Literal[0.0]also holds-0.0, andLiteral[Decimal("1.00")]holdsDecimal("1.0"), which a predicate can tell apart, so such a literal below a predicate is not proven.- Typing qualifiers.import math from decimal import Decimal from typing import Annotated, Literal from valgebra import Validator positive = Annotated[float, lambda x: math.copysign(1.0, x) > 0] assert Validator(Literal[1.5]).relation_to(positive) == "subset" assert Validator(Literal[0.0]).relation_to(positive) == "undecided" # -0.0 two_places = Annotated[Decimal, lambda d: d.as_tuple().exponent == -2] assert Validator(Literal[Decimal("1.00")]).relation_to(two_places) == "undecided"FinalandClassVarare rejected as schemas; they qualify a declaration and carry no value-membership meaning. On a class they are read as what they are: aClassVarannotates the class rather than an instance, so a dataclass field carrying one is not an attribute the schema asks for, and neither is anInitVar, which names a constructor parameter the instance does not keep.
from collections.abc import Sequence
from typing import TypeVar
from valgebra import Validator
T = TypeVar("T")
for undecidable in (Sequence[int], T):
try:
Validator(undecidable)
raise AssertionError("expected a rejection")
except NotImplementedError:
pass # rejected with a clear message, never a silent wrong validator
The contract¶
A positive answer (is_subtype_of/is_equivalent/is_empty returning True) is a
proof. A negative answer is "no, or not yet proven". valgebra never reports a
relation it cannot justify, so widening the decided fragment can only turn a
conservative False into a True — it can never change an answer that was
already correct.
Every decision also runs under a budget of a million decision steps, and
exhausting it returns the conservative answer (False, "not proven") rather
than running unbounded. A question that ends undecided at a smaller allowance
inside that budget, with steps of its own left, is asked once more under a
budget of its own, and the first answer stands wherever it decides, so the
second asking adds answers and takes none away. The budget counts steps, not
time: a step linear in a leaf it reads is one step, so a relation over a large
leaf takes time in proportion to it
(limits). This preserves soundness:
a bail-out is never a wrong True. A relation the two schemas settle as written
-- a schema against itself, a schema against a union that holds it, a meet
against one of its own members -- is answered whatever the budget has left.
The boolean methods answer True or False, so through them a False from an
exhausted budget reads the same as a False the procedure decided. Inside the
core the two are distinct — emptiness answers empty, inhabited, or
neither — which is what lets a test say that a bail-out never claims a proof
it does not have, and relation_to reports the split: a query whose budget runs
out, and which the set representation does not settle either, answers
"undecided" rather than "not_subset". The contract does not change with it:
a False is "not proven" either way.
The budget binds where the work is a product rather than a sum. Subtyping distributes over both sides of a union, so relating two unions can cost the product of their member counts, and a Boolean combination nested past a handful of levels demands work exponential in its depth.
One shape avoids the product entirely, and it is the one a contract writes most:
a union of nothing but literals. A literal denotes its constant and the
values its type's == joins to it, so such a union denotes a finite set of
constants, each standing for its class, and inclusion between two finite sets
is membership of every constant of one in the other. That is decided by lookup rather
than by distribution, and it is exact in both directions — every value found is
a proof, and one value found nowhere is a refutation, since it is in the subject
and outside the other schema. Two tables of ten thousand codes each are decided
in a few milliseconds, in either direction, whether they were written out
separately or one was built from the other:
from typing import Literal
from valgebra import Validator
codes = Validator(Literal[tuple(range(10_000))])
wider = Validator(Literal[tuple(range(10_001))])
shifted = Validator(Literal[tuple(range(1, 10_001))])
backwards = Validator(Literal[tuple(reversed(range(10_000)))])
assert codes.relation_to(wider) == "subset"
assert codes.relation_to(shifted) == "not_subset" # 0 is in one and not the other
assert codes.relation_to(backwards) == "subset" # the same set, written the other way
"However they were written" is a claim about the pools: each validator numbers
its constants in the order it met them, relating two validators renumbers one
pool into the other, and a table written backwards is renumbered backwards. A
member list is read as a set only in the canonical order its constructor leaves
it in, so the transform that renumbers one sorts it again
(crates/valgebra-core/src/ir/transform.rs, mapped_member_set). Without that
sort, two tables agreeing on nothing about where each constant sits fall out of
the canonical order and are distributed against each other instead.
A table met with other tables and with the complements of tables is the finite set it leaves, decided by the same lookup, which is what a record's tag narrows to when the record rule splits it:
from typing import Literal
from valgebra import complement, intersection
left = intersection(Literal["a", "b", "c"], complement(Literal["a"]))
assert left.relation_to(Literal["b", "c"]) == "subset"
assert left.relation_to(Literal["b"]) == "not_subset" # "c" is left
A constant is taken away by its pool position, which is exact, and kept only where the bindings say it is a value apart from every table taken away, since two positions may hold one value.
The refutation is the bindings' to give: two constants at two pool positions are
two values only where their type's equality can be trusted, and a constant
that does not equal itself — float("nan") — denotes no value at all, so
Literal[float("nan")] is the empty set and is below everything. Where the
equality cannot be trusted, a refutation between two constants stays undecided
rather than guessing. One constant is still a value of its own literal where
the literal's walk admits it, so Literal[Decimal("1.5")] is not_subset of
nothing, and a literal of a str subclass equal to "a" is not_subset of
Literal["A"]; a constant the walk refuses, or raises on, proves nothing.
A proof does not ask: Literal[c] is below Literal[d] where c == d and the
two are of one exact type, which holds only of an equality that is transitive, as
the trust base says.
What is left under the budget is the Boolean tower: a deeply nested combination
of unions, meets and complements, where subtyping distributes over both sides
and the work is a product of the branches. A False there may mean "not proven
within the bound" rather than "not a subtype"; on anything else it means the
relation is outside the decided fragment above. The bound caps cost and does
not stand in for termination: every goal a query asks is drawn from a finite
closure of its subterms, which docs/dev/decision.md in the repository
writes out. Nor does it stand in for a goal memo on most shapes: over the
--decision, --decision-refute and --decision-repeat workloads of
scripts/perf_gate.py the goals a query repeats number zero, because the
trail absorbs recursion and the per-rule caches absorb the shape where one goal
is asked once per field. The relation matrix (--decision-matrix) is where a
table over goals would hit: a meet against a union repeats goals there, and
decision::goal_tests counts them.