Yichus/Law
Builtin package (resource law.bosatsu).
This is the complete package source used by this build. The export
list names its public API; definitions below give the types and behavior.
New to the API? Start with Make a data app or Build an API, then use this page to look up a definition.
package Yichus/Law
from Bosatsu/Char import string_to_Char_List
from Yichus/Num/Float64 import Float64, cmp_Float64, LT as LT_Float64
from Zafu/Control/IterState import (
foldl_List as iter_foldl_List,
done as iter_done,
continue as iter_continue,
value as iter_value,
)
# Universal claims about pure total functions. Existing `yichus law`
# checks Obligation values over seeded generated inputs: a bounded
# observation, never proof. FiniteObligation names an explicit finite
# domain for a separate exhaustive method; it does not change the sampled
# meaning of an ordinary Obligation.
#
# Spec-first, persona-first: the property suggester (`api_suggest_properties`)
# proposes Obligations as complete compilable units filled from the typed IR;
# a piece it cannot fill from facts arrives as a WitnessTodo — a typed named
# hole. Totality is why holes are a variant and not a `hole[a]` function: a
# total language cannot conjure an `a`, so an unfilled hole is a constructor
# the checker sees and reports as `inconclusive: hole not filled`, never as
# a pass.
export (
Domain(),
Law(),
WitnessSpec(),
Obligation(),
FiniteObligation(),
PageObligation(),
CommitObligation(),
Discharge(),
Obligations(),
FoldRun(),
Pair(),
Triple(),
TypeRef(),
FieldFact(),
AccessPolicy(),
TableFact(),
ParamFact(),
Relation(),
GuardFact(),
BindingFact(),
StructField(),
StructFact(),
ProgramFacts(),
Suggestion(),
Rule(),
RuleSet(),
Dismissed(),
default_rules,
guards_near,
first_bound_guard,
is_lower_rel,
is_upper_rel,
exists_List,
filter_List,
flat_map_List,
contains_String,
never_below,
never_above,
conserves,
inverse,
idempotent,
commutative,
associative,
order_independent,
permutes,
permute_by,
multiset_eq,
size_List,
at_least,
at_least_Float64,
all_true,
)
exposes Yichus/Num/Float64
# Everything type-specific about an input domain in one place: how to print
# it in a counterexample, how to generate it, how to shrink it.
# `gen = None` means "derive from the type" (ValueGen, seeded by the
# checker's portable splitmix64); `shrink = None` means the structural
# default. The catalog fills these in, so a user pasting a suggested law
# never constructs one by hand.
struct Domain[i](
name: String,
describe: i -> String,
gen: Option[Int -> i],
shrink: Option[i -> List[i]]
)
# A universal claim about a pure total function: `check` must hold for
# every input of the domain. Checked by seeded generation.
struct Law[i](name: String, domain: Domain[i], check: i -> Bool)
# Anti-vacuity. A law that holds because nothing ever happens is worse than
# no law: an enrollment fold that admits nobody satisfies "no seat count
# goes negative". Every Law needs a Witness some generated input satisfies,
# or its verdict is `inconclusive: vacuous`. WitnessTodo is the suggester's
# named hole: the check cannot be derived from the program's facts, and
# `why` says exactly what is missing. An Obligation carrying a WitnessTodo
# checks `inconclusive: hole not filled`.
enum WitnessSpec[i]:
Witness(name: String, check: i -> Bool)
WitnessTodo(name: String, why: String)
struct Obligation[i](law: Law[i], witnesses: List[WitnessSpec[i]])
# An explicit, complete domain for one obligation. The values are the entire
# claimed scope, not a seed or a sample. Repeated values do not enlarge it.
# First occurrence order is significant: it sets normalized value indices and
# the domain identity, so reordering the same values changes that identity.
# Keeping this wrapper separate preserves the sampled meaning of every
# existing Obligation and Domain declaration.
struct FiniteObligation[i](obligation: Obligation[i], values: List[i])
# A law over a data app's page: the law's input is the page's own inputs,
# named by their ids in the page config (the `.sim.bosatsu` file), in the
# order the input holds them: one id for a single value, two for a pair,
# and so on. Its scope is what the page's controls can enter (each slider
# or number box's steps from min to max, a checkbox's two values, a
# dropdown's choices, and each starting value), never a value the page
# cannot show. A complete check of that scope covers every case the page
# allows; a larger scope is sampled inside it. Domain.gen and Domain.shrink
# are not used: inputs and smaller failing cases come from the page.
struct PageObligation[i](obligation: Obligation[i], inputs: List[String])
# --- Commit obligations ----------------------------------------------------
# The strategy ladder: what the engine may do at commit time depends on
# which obligations the checked laws discharge. The user never needs this
# table — `api_obligations` walks them down it one proposed property at a
# time. A Discharge NAMES the laws (by their Law.name) that stand as
# bounded evidence for an obligation; the engine checks those laws hold
# and fails closed on anything violated, inconclusive, or unnamed. The
# binding is a declaration: the evidence is the named laws' verdicts,
# and a licensed strategy is licensed by bounded evidence, never proof.
# The rungs, in licensing order:
# - DistinctKeyCommutativity: applying two operations with distinct keys
# commutes; licenses per-key independence (a larger effective
# interleaving bound).
# - PerOpMonotonicity: each operation moves its key's value
# monotonically; with commutativity, licenses escrow interval
# arithmetic and the single-write commit.
# - DeclaredLattice: a declared lattice (zero, combine, le) extends the
# same arithmetic past Int to sets, multisets, and max-registers.
# - NonMonotoneWitness: an explicitly declared non-monotone key
# property; licenses bounded witness search instead of the monotone
# ladder.
# Constructor order is a wire format: ObligationsExtractor decodes these
# by variant index (0-3). Append new rungs at the end; never reorder.
enum CommitObligation:
DistinctKeyCommutativity
PerOpMonotonicity
DeclaredLattice
NonMonotoneWitness
struct Discharge(obligation: CommitObligation, laws: List[String])
# The program's declared obligation evidence, discovered by binding type
# like Obligation. Several bindings per module are collected and all
# considered; one is the conventional shape.
struct Obligations(discharges: List[Discharge])
# The catalog's own input shape for "run a fold over some operations".
# `shuffle` seeds the permutation the order-independence law compares
# against, so ordering is generated rather than assumed.
struct FoldRun[s, o](initial: s, ops: List[o], shuffle: Int)
# Argument shapes for the binary/ternary catalog laws (a tuple-free
# vocabulary keeps generated snippets dependent only on this package).
struct Pair[a](fst: a, snd: a)
struct Triple[a](t1: a, t2: a, t3: a)
# --- Suggestion vocabulary -------------------------------------------------
# Facts are reified from the typed IR by the suggester: Scala names each
# constructor and field, and the encoding is checked against these
# declarations by name, so a drift between the two fails loudly. A rule is
# an ordinary Bosatsu function over the facts; teams add their own RuleSet,
# which is what keeps the suggester open rather than an eighth closed
# checker.
# A checked type as the compiler holds it: a named type constructor or a
# type variable, applied to arguments. Function and tuple types are the
# Predef constructors the compiler applies (`Fn2[Int, Int, Bool]`,
# `Tuple2[a, b]`). Quantifiers are dropped: a variable they bind appears as
# TypeVar, so a generic signature is visibly not nameable by a generated
# file.
enum TypeRef:
TypeNamed(package_name: String, name: String, args: List[TypeRef])
TypeVar(name: String, args: List[TypeRef])
struct FieldFact(name: String, field_type: TypeRef)
# The declared access policy of a table, as the static access checker
# reads it from an AccessSpec; Undeclared when no AccessRule names the
# table. Guards and roles are listed as declared.
enum AccessPolicy:
Undeclared
DeclaredPublic
DeclaredOwnerScoped
DeclaredGuarded(guards: List[String])
DeclaredGuardedOrRoles(guards: List[String], roles: List[String])
DeclaredPublicReadRoleWrite(roles: List[String])
DeclaredUnder(parent: String, roles: List[String])
# access_proven is the static access checker's verdict, the same analyzer
# api_access_check runs. Rules over these facts propose declarations and
# defer the proving to the checker: access is a static proof, never a
# bounded law.
#
# conformances names the handler bindings a declared Yichus/Spec
# Conformance already binds to a model of this table: rules over it
# propose drafts for the writers no model covers, and the conformance
# checker (api_conformance_check) decides whether code and model agree.
struct TableFact(
name: String,
package_name: String,
fields: List[FieldFact],
readers: List[String],
writers: List[String],
access_policy: AccessPolicy,
access_proven: Bool,
conformances: List[String]
)
struct ParamFact(name: String, param_type: TypeRef)
# How a guarded value compares with an Int literal, normalized so the
# guarded value is on the left: Gt 0 is `value > 0`.
enum Relation:
Eq
Ne
Lt
Lte
Gt
Gte
# A comparison against an Int literal, recovered from the compiled IR's
# CompareLit/CompareInt nodes and checked cmp_Int/eq_Int results. The
# relation is what lets a rule tell a floor guard from a ceiling guard.
struct GuardFact(literal: Int, relation: Relation)
# type_imports lists the binding's own package's type names in its
# signature. importable means the package exports the binding and every
# one of those types, so a generated standalone file can import it: rules
# whose snippet imports the binding fire only on importable bindings,
# since any other snippet would not compile.
struct BindingFact(
name: String,
package_name: String,
params: List[ParamFact],
result_type: TypeRef,
is_pure: Bool,
reads: List[String],
writes: List[String],
read_modify_writes: List[String],
guards: List[GuardFact],
calls: List[String],
type_imports: List[String],
declared_laws: List[String],
importable: Bool
)
# A struct a user package defines (one constructor), its fields in
# declaration order with the bindings ("Pkg::name") that read each field:
# readers holds those whose compiled IR extracts it and every user binding
# that calls one of them, at any depth and across packages;
# direct_readers holds only the first kind.
# importable means a sibling package can import the type with its
# constructor (`export (Name())`), so a generated file can build and
# take apart its values.
struct StructField(name: String, field_type: TypeRef, readers: List[String], direct_readers: List[String])
struct StructFact(
name: String,
package_name: String,
fields: List[StructField],
importable: Bool
)
struct ProgramFacts(bindings: List[BindingFact], tables: List[TableFact], structs: List[StructFact])
# unlocks names what acting on the suggestion enables, and its shape is
# a contract: a suggestion proposing an Obligation names its catalog law
# as `laws.<name>`; a suggestion proposing a declaration a static
# checker proves names the tool (`api_access_check`). Consumers route on
# this: the report's needed channel carries only `laws.*` suggestions
# as Obligation artifacts. The default rules build each snippet as a
# Snippet and render it with render_snippet.
struct Suggestion(
template: String,
because: String,
unlocks: String,
snippet: String,
targets: List[String]
)
struct Rule(name: String, run: ProgramFacts -> List[Suggestion])
struct RuleSet(name: String, rules: List[Rule])
# A declined suggestion. The suggester drops any suggestion matching a
# discovered Dismissed binding and reports it under `dismissed`, never
# silently, so a declined suggestion stops firing instead of looping an
# agent forever. The reason is required: the next reader learns why.
# A grouped suggestion (several targets sharing one snippet, like the
# per-package access rules) is dismissed only when every target has its
# own Dismissed binding: declining one table never silences a sibling
# that still needs a policy.
struct Dismissed(template: String, target: String, reason: String)
# --- Int and list helpers --------------------------------------------------
def size_List[a](items: List[a]) -> Int:
items.foldl_List(0, (acc, _) -> add(acc, 1))
def at_least(value: Int, floor: Int) -> Bool:
match cmp_Int(value, floor):
case LT: False
case _: True
# Compares in cmp_Float64's total order: a NaN sorts above every number, so
# it passes any floor, and -0.0 sorts below 0.0. A law that must turn away
# a NaN answer says so in its in_use_hole or its own check.
def at_least_Float64(value: Float64, floor: Float64) -> Bool:
match cmp_Float64(value, floor):
case LT_Float64: False
case _: True
def all_true(checks: List[Bool]) -> Bool:
checks.foldl_List(True, (acc, c) -> c if acc else False)
def at_most(value: Int, ceiling: Int) -> Bool:
match cmp_Int(value, ceiling):
case GT: False
case _: True
def all_Ints(values: List[Int], pred: Int -> Bool) -> Bool:
values.foldl_List(True, (acc, v) ->
match acc:
case False: False
case True: pred(v)
)
def rev_append[a](items: List[a], tail: List[a]) -> List[a]:
loop items:
case []: tail
case [head, *rest]: rev_append(rest, [head, *tail])
# Remove the first element equal (by `eq`) to `target`; None if absent.
def remove_first[a](items: List[a], target: a, eq: (a, a) -> Bool) -> Option[List[a]]:
recur items:
case []: None
case [head, *rest]:
match eq(head, target):
case True: Some(rest)
case False:
match remove_first(rest, target, eq):
case Some(pruned): Some([head, *pruned])
case None: None
# Equality of multisets under a caller-supplied element equality.
def multiset_eq[a](left: List[a], right: List[a], eq: (a, a) -> Bool) -> Bool:
loop left:
case []: right matches []
case [head, *rest]:
match remove_first(right, head, eq):
case Some(pruned): multiset_eq(rest, pruned, eq)
case None: False
# Internal carrier for pick_at: the element and the list without it.
struct Picked[a](item: a, rest: List[a])
# Element at `idx` plus the list without it; None when out of range.
def pick_at[a](items: List[a], idx: Int) -> Option[Picked[a]]:
match cmp_Int(idx, 0):
case LT: None
case _:
recur items:
case []: None
case [head, *rest]:
match cmp_Int(idx, 0):
case EQ: Some(Picked(head, rest))
case _:
match pick_at(rest, sub(idx, 1)):
case Some(Picked(picked, pruned)): Some(Picked(picked, [head, *pruned]))
case None: None
def permute_step[a](
fuel: List[a],
remaining: List[a],
count: Int,
code: Int,
acc: List[a]
) -> List[a]:
loop fuel:
case []: rev_append(acc, remaining)
case [_, *fs]:
match cmp_Int(count, 0):
case GT:
idx = mod_Int(code, count)
match pick_at(remaining, idx):
case Some(Picked(picked, pruned)):
permute_step(fs, pruned, sub(count, 1), div(code, count), [picked, *acc])
case None: rev_append(acc, remaining)
case _: rev_append(acc, remaining)
# Seed-indexed permutation of a list: the seed is read as a Lehmer code,
# so every permutation of the list is reachable from some seed (codes are
# taken mod n! implicitly, digit by digit). Deterministic, total, and the
# same on every runtime — the checker derives `shuffle` from its portable
# splitmix64 stream.
def permute_by[a](seed: Int, items: List[a]) -> List[a]:
n = size_List(items)
code = match cmp_Int(seed, 0):
case LT: sub(0, seed)
case _: seed
permute_step(items, items, n, code, [])
# --- The catalog -----------------------------------------------------------
# Named templates: a suggestion is a one-line instantiation, and each law's
# `name` is a plain sentence, so a verdict reads as a claim about the user's
# domain rather than about a combinator.
def never_below[i](name: String, d: Domain[i], values: i -> List[Int], floor: Int) -> Law[i]:
Law(name, d, x -> all_Ints(values(x), v -> at_least(v, floor)))
def never_above[i](name: String, d: Domain[i], values: i -> List[Int], ceiling: Int) -> Law[i]:
Law(name, d, x -> all_Ints(values(x), v -> at_most(v, ceiling)))
def conserves[i](name: String, d: Domain[i], before: i -> Int, after: i -> Int) -> Law[i]:
Law(name, d, x -> eq_Int(before(x), after(x)))
def inverse[i, s](
name: String,
d: Domain[i],
start: i -> s,
roundtrip: i -> s,
eq: (s, s) -> Bool
) -> Law[i]:
Law(name, d, x -> eq(start(x), roundtrip(x)))
def idempotent[i, s](
name: String,
d: Domain[i],
once: i -> s,
twice: i -> s,
eq: (s, s) -> Bool
) -> Law[i]:
Law(name, d, x -> eq(once(x), twice(x)))
def commutative[a, r](
name: String,
d: Domain[Pair[a]],
f: (a, a) -> r,
eq: (r, r) -> Bool
) -> Law[Pair[a]]:
def chk(p: Pair[a]) -> Bool:
Pair(x, y) = p
eq(f(x, y), f(y, x))
Law(name, d, chk)
def associative[a](
name: String,
d: Domain[Triple[a]],
f: (a, a) -> a,
eq: (a, a) -> Bool
) -> Law[Triple[a]]:
def chk(t: Triple[a]) -> Bool:
Triple(x, y, z) = t
eq(f(f(x, y), z), f(x, f(y, z)))
Law(name, d, chk)
# The output is a permutation of the input: catches the fold that silently
# drops or duplicates an item.
def permutes[i, a](
name: String,
d: Domain[i],
input: i -> List[a],
output: i -> List[a],
eq: (a, a) -> Bool
) -> Law[i]:
Law(name, d, x -> multiset_eq(input(x), output(x), eq))
# Running the fold over the ops and over a seed-indexed permutation of the
# ops gives equal results. Ordering is generated, not assumed.
def order_independent[s, o, r](
name: String,
fold: (s, List[o]) -> r,
eq: (r, r) -> Bool,
d: Domain[FoldRun[s, o]]
) -> Law[FoldRun[s, o]]:
def chk(run: FoldRun[s, o]) -> Bool:
FoldRun(initial, ops, shuffle) = run
eq(fold(initial, ops), fold(initial, permute_by(shuffle, ops)))
Law(name, d, chk)
# --- List and String helpers for rules -------------------------------------
def exists_List[a](items: List[a], pred: a -> Bool) -> Bool:
def step(acc: Bool, item: a) -> Bool:
match acc:
case True: True
case False: pred(item)
items.foldl_List(False, step)
def filter_List[a](items: List[a], pred: a -> Bool) -> List[a]:
def step(acc: List[a], item: a) -> List[a]:
match pred(item):
case True: [item, *acc]
case False: acc
rev_append(items.foldl_List([], step), [])
def flat_map_List[a, b](items: List[a], f: a -> List[b]) -> List[b]:
def step(acc: List[b], item: a) -> List[b]:
rev_append(f(item), acc)
rev_append(items.foldl_List([], step), [])
def contains_String(items: List[String], target: String) -> Bool:
exists_List(items, s -> eq_String(s, target))
def join_String(sep: String, xs: List[String]) -> String:
match xs:
case []: ""
case [x, *rest]: concat_String([x, *rest.flat_map_List(r -> [sep, r])])
# --- Type references -------------------------------------------------------
predef_package = "Bosatsu/Predef"
def predef_type(name: String) -> TypeRef:
TypeNamed(predef_package, name, [])
def list_of(elem: TypeRef) -> TypeRef:
TypeNamed(predef_package, "List", [elem])
# The type is exactly `package_name::name`, with no arguments.
def is_type(t: TypeRef, package_name: String, name: String) -> Bool:
match t:
case TypeNamed(p, n, []): eq_String(n, name) if eq_String(p, package_name) else False
case _: False
def list_element(t: TypeRef) -> Option[TypeRef]:
match t:
case TypeNamed(p, "List", [elem]): Some(elem) if eq_String(p, predef_package) else None
case _: None
def same_types(left: List[TypeRef], right: List[TypeRef]) -> Bool:
recur left:
case []: right matches []
case [TypeNamed(p, n, args), *rest]:
match right:
case [TypeNamed(q, m, rargs), *rrest]:
match (eq_String(p, q), eq_String(n, m)):
case (True, True): same_types(rest, rrest) if same_types(args, rargs) else False
case _: False
case _: False
case [TypeVar(v, args), *rest]:
match right:
case [TypeVar(w, rargs), *rrest]:
match eq_String(v, w):
case True: same_types(rest, rrest) if same_types(args, rargs) else False
case False: False
case _: False
def same_type(left: TypeRef, right: TypeRef) -> Bool:
same_types([left], [right])
# Every type the list names is Predef's or home's, and none is a variable:
# a standalone file in home's package family can name each one after
# importing home's types. A rule whose snippet would name anything else
# stays silent.
def nameable_in(ts: List[TypeRef], home: String) -> Bool:
recur ts:
case []: True
case [TypeVar(_, _), *_]: False
case [TypeNamed(p, _, args), *rest]:
local = True if eq_String(p, predef_package) else eq_String(p, home)
match local:
case False: False
case True: nameable_in(rest, home) if nameable_in(args, home) else False
# The names of home's types among the list, in order, each as often as it
# appears: what a generated file imports from home to name these types.
def home_names(ts: List[TypeRef], home: String) -> List[String]:
recur ts:
case []: []
case [TypeVar(_, args), *rest]: [*home_names(args, home), *home_names(rest, home)]
case [TypeNamed(p, n, args), *rest]:
inner = [*home_names(args, home), *home_names(rest, home)]
[n, *inner] if eq_String(p, home) else inner
# Types as a generated file names them: bare, since the file imports every
# type it names (rules check nameable_in first).
def render_types(ts: List[TypeRef]) -> List[String]:
recur ts:
case []: []
case [TypeVar(n, []), *rest] | [TypeNamed(_, n, []), *rest]: [n, *render_types(rest)]
case [TypeVar(n, args), *rest] | [TypeNamed(_, n, args), *rest]:
["${n}[${join_String(", ", render_types(args))}]", *render_types(rest)]
def render_type(t: TypeRef) -> String:
join_String("", render_types([t]))
# --- Snippets as syntax ----------------------------------------------------
# A suggested file is built as syntax and rendered once, so every name and
# literal lands in its own position: program text (a table name, a role)
# only ever appears as an escaped string literal, never spliced into
# source. The syntax covers what the default rules write.
enum Expr:
Ref(name: String)
Text(value: String)
Num(value: Int)
Call(fn: String, args: List[Expr])
Items(items: List[Expr])
enum Pat:
Bind(name: String)
Skip
Unpack(constructor: String, fields: List[Pat])
struct Param(pat: Pat, param_type: TypeRef)
struct Let(pat: Pat, value: Expr)
# One comment line is a list of words: Says is the rule author's own
# text, Names an identifier (rendered in backticks), Quotes program text
# (rendered as an escaped string literal, so it cannot end the comment).
enum Prose:
Says(text: String)
Names(name: String)
Quotes(text: String)
enum Decl:
Def(name: String, type_params: List[String], params: List[Param], result: TypeRef, lets: List[Let], value: Expr)
Val(name: String, value: Expr)
Note(lines: List[List[Prose]])
struct Import(package_name: String, names: List[String])
struct Snippet(
package_name: String,
imports: List[Import],
exports: List[String],
exposes: List[String],
decls: List[Decl]
)
def escape_char(c: Char) -> String:
match c:
case .'"': "\\\""
case .'\\': "\\\\"
case .'$': "\\$"
case .'\n': "\\n"
case .'\r': "\\r"
case .'\t': "\\t"
case _: char_to_String(c)
# The Bosatsu string literal whose value is exactly text.
def quote(text: String) -> String:
concat_String(["\"", *string_to_Char_List(text).map_List(escape_char), "\""])
def render_exprs(es: List[Expr]) -> List[String]:
recur es:
case []: []
case [Ref(n), *rest]: [n, *render_exprs(rest)]
case [Text(t), *rest]: [quote(t), *render_exprs(rest)]
case [Num(n), *rest]: [int_to_String(n), *render_exprs(rest)]
case [Call(f, args), *rest]: ["${f}(${join_String(", ", render_exprs(args))})", *render_exprs(rest)]
case [Items(items), *rest]: ["[${join_String(", ", render_exprs(items))}]", *render_exprs(rest)]
def render_expr(e: Expr) -> String:
join_String("", render_exprs([e]))
def render_pats(ps: List[Pat]) -> List[String]:
recur ps:
case []: []
case [Bind(n), *rest]: [n, *render_pats(rest)]
case [Skip, *rest]: ["_", *render_pats(rest)]
case [Unpack(c, fields), *rest]: ["${c}(${join_String(", ", render_pats(fields))})", *render_pats(rest)]
def render_pat(p: Pat) -> String:
join_String("", render_pats([p]))
# A value's call breaks one item per line when its one argument is a
# non-empty list, and one argument per line when it is long.
def render_laid_out(e: Expr) -> String:
flat = render_expr(e)
match e:
case Call(f, [Items([first, *more])]):
lines = render_exprs([first, *more]).map_List(i -> " ${i},\n")
concat_String(["${f}([\n", *lines, "])"])
case Call(f, args):
match cmp_Int(length_String(flat), 72):
case GT: concat_String(["${f}(\n", join_String(",\n", render_exprs(args).map_List(a -> " ${a}")), "\n)"])
case _: flat
case _: flat
def prose_text(word: Prose) -> String:
match word:
case Says(text): text
case Names(name): "`${name}`"
case Quotes(text): quote(text)
def note_line(line: List[Prose]) -> String:
match concat_String(line.map_List(prose_text)):
case "": "#\n"
case text: "# ${text}\n"
def render_param(p: Param) -> String:
Param(pat, t) = p
"${render_pat(pat)}: ${render_type(t)}"
def render_let(l: Let) -> String:
Let(pat, value) = l
" ${render_pat(pat)} = ${render_expr(value)}\n"
def render_decl(d: Decl) -> String:
match d:
case Def(name, type_params, params, result, lets, value):
tps = match type_params:
case []: ""
case _: "[${join_String(", ", type_params)}]"
concat_String([
"def ${name}${tps}(${join_String(", ", params.map_List(render_param))}) -> ${render_type(result)}:\n",
*lets.map_List(render_let),
" ${render_expr(value)}\n"
])
case Val(name, value): "${name} = ${render_laid_out(value)}\n"
case Note(lines): concat_String(lines.map_List(note_line))
def render_import(i: Import) -> String:
Import(pkg, names) = i
"from ${pkg} import (${join_String(", ", names)})\n"
def header_section(keyword: String, names: List[String]) -> List[String]:
match names:
case []: []
case _: ["${keyword} (${join_String(", ", names)})\n", "\n"]
def render_snippet(s: Snippet) -> String:
Snippet(pkg, imports, exports, exposes, decls) = s
import_lines = match imports:
case []: []
case _: [*imports.map_List(render_import), "\n"]
concat_String([
"package ${pkg}\n",
"\n",
*import_lines,
*header_section("export", exports),
*header_section("exposes", exposes),
join_String("\n", decls.map_List(render_decl))
])
# --- The default suggestion rules ------------------------------------------
#
# Rules run over ProgramFacts reified from the compiled IR. Every
# suggestion is a complete standalone Bosatsu file: package declaration,
# imports, and an Obligation whose unfillable pieces are NAMED HOLES: a
# stub projection returning [], a permissive eq returning True, a
# WitnessTodo. The holes are safe by construction: a hole can make the
# verdict inconclusive, never a false pass and never a false violation.
# A rule that cannot fill a piece from the facts emits a hole and says
# what is missing; a rule with nothing honest to say emits nothing.
def is_lower_rel(rel: Relation) -> Bool:
match rel:
case Gt | Gte: True
case _: False
def is_upper_rel(rel: Relation) -> Bool:
match rel:
case Lt | Lte: True
case _: False
def relation_text(rel: Relation) -> String:
match rel:
case Eq: "eq"
case Ne: "ne"
case Lt: "lt"
case Lte: "lte"
case Gt: "gt"
case Gte: "gte"
int_type = predef_type("Int")
string_type = predef_type("String")
bool_type = predef_type("Bool")
def is_world_type(t: TypeRef) -> Bool:
match is_type(t, "Yichus/Data", "Db"):
case True: True
case False: is_type(t, "Yichus/Access", "Principal")
# The fold shape the fold rules fire on: two parameters, a state and a
# List of operations (either order), returning the state's own type.
# `(S, List[O]) -> S` is a fold of operations; `(List[a], a) -> Bool` or
# `(List[a], a) -> List[a]` is not. The binding must be importable, since
# every fold snippet imports it, and its state and operation types must be
# nameable there. state_first records the call spelling.
struct FoldShape(state: TypeRef, op: TypeRef, state_first: Bool)
def fold_shape(b: BindingFact) -> Option[FoldShape]:
BindingFact(_, pkg, params, result_type, _, _, _, _, _, _, _, _, importable) = b
shape = match params:
case [ParamFact(_, first), ParamFact(_, second)]:
match (list_element(first), list_element(second)):
case (None, Some(op)): Some(FoldShape(first, op, True))
case (Some(op), None): Some(FoldShape(second, op, False))
case _: None
case _: None
match shape:
case Some(FoldShape(state, op, _)):
match (importable, nameable_in([state, op], pkg), same_type(state, result_type)):
case (True, True, True): shape
case _: None
case None: None
# Own guards first, in declaration order, then called bindings' guards in
# their order: first_bound_guard takes the first match, so ordering is
# part of the contract.
def guards_near(b: BindingFact, all_bindings: List[BindingFact]) -> List[GuardFact]:
BindingFact(_, _, _, _, _, _, _, _, own, calls, _, _, _) = b
called = all_bindings.flat_map_List(other -> (
BindingFact(oname, _, _, _, _, _, _, _, oguards, _, _, _, _) = other
match contains_String(calls, oname):
case True: oguards
case False: []
))
rev_append(rev_append(own, []), called)
def law_import(names: List[String]) -> Import:
Import("Yichus/Law", names)
def binding_import(pkg: String, binding_name: String, type_imports: List[String]) -> Import:
Import(pkg, [binding_name, *type_imports])
# A fold snippet exports an Obligation over FoldRun[S, O]; S and O are
# exactly the signature's types, so the fold's package is exposed only
# when its own types appear there.
def fold_exposes(pkg: String, type_imports: List[String]) -> List[String]:
match type_imports:
case []: ["Yichus/Law"]
case _: [pkg, "Yichus/Law"]
def fold_call(binding_name: String, shape: FoldShape) -> Expr:
FoldShape(_, _, state_first) = shape
match state_first:
case True: Call(binding_name, [Ref("initial"), Ref("ops")])
case False: Call(binding_name, [Ref("ops"), Ref("initial")])
def fold_run_type(shape: FoldShape) -> TypeRef:
FoldShape(state, op, _) = shape
TypeNamed("Yichus/Law", "FoldRun", [state, op])
# The Domain every snippet declares: a describe hole and the type-driven
# default generator and shrinker.
def describe_hole(subject: TypeRef, label: String) -> Decl:
Def("describe_hole", [], [Param(Skip, subject)], string_type, [], Text(label))
def domain_of(name: String, label: String) -> Decl:
Val(name, Call("Domain", [Text(label), Ref("describe_hole"), Ref("None"), Ref("None")]))
def gen_hole_note(run_type: TypeRef, ordinal: String) -> List[List[Prose]]:
[
[Says("The Domain's gen is a ${ordinal} hole when the type-driven default cannot")],
[Says("build a ${render_type(run_type)}: if the verdict says 'not generable', replace")],
[Says("the first None in the Domain with Some(seed -> ...)")],
]
# Shared skeleton for the floor and ceiling suggestions: a standalone
# file with a stub projection (values_hole) and a WitnessTodo, both named
# holes. The pasted file compiles and checks `inconclusive` until the
# holes are filled, never a false pass.
def bound_snippet(
b: BindingFact,
shape: FoldShape,
literal: Int,
catalog_fn: String,
phrase: String,
suffix: String
) -> String:
BindingFact(bname, pkg, _, _, _, _, _, _, _, _, type_imports, _, _) = b
run_type = fold_run_type(shape)
lit = int_to_String(literal)
runs = "${bname}_runs"
obligation = "${bname}_${suffix}"
render_snippet(Snippet(
"${pkg}/Laws",
[law_import(["Domain", "FoldRun", "Obligation", "WitnessTodo", catalog_fn]), binding_import(pkg, bname, type_imports)],
[obligation],
fold_exposes(pkg, type_imports),
[
Note([
[Says("Suggested by the ${catalog_fn} rule: a guard in or reachable from")],
[Names(bname), Says(" compares an Int against ${lit}. Two named holes:")],
[Says(" values_hole: project the Ints this law bounds from a completed run")],
[Says(" the WitnessTodo: prove a generated run actually exercised "), Names(bname)],
*gen_hole_note(run_type, "third"),
]),
Def(
"values_hole",
[],
[Param(Bind("run"), run_type)],
list_of(int_type),
[Let(Unpack("FoldRun", [Bind("initial"), Bind("ops"), Skip]), Ref("run")), Let(Skip, fold_call(bname, shape))],
Items([])
),
describe_hole(run_type, "${bname} run"),
domain_of(runs, "${bname} runs"),
Val(obligation, Call("Obligation", [
Call(catalog_fn, [Text("${bname} results stay ${phrase} ${lit}"), Ref(runs), Ref("values_hole"), Num(literal)]),
Items([Call("WitnessTodo", [
Text("the run is meaningful"),
Text("replace values_hole's [] with the projected values, then turn this into a Witness that some generated run exercises ${bname}")
])])
])),
]
))
def first_bound_guard(
b: BindingFact,
all_bindings: List[BindingFact],
keep: Relation -> Bool
) -> Option[GuardFact]:
iter_value(iter_foldl_List(guards_near(b, all_bindings), None, (_, g) -> (
GuardFact(_, rel) = g
match keep(rel):
case True: iter_done(Some(g))
case False: iter_continue(None)
)))
def bound_rule_run(
facts: ProgramFacts,
keep: Relation -> Bool,
template: String,
catalog_fn: String,
phrase: String,
suffix: String
) -> List[Suggestion]:
ProgramFacts(bindings, _, _) = facts
def suggest(b: BindingFact) -> List[Suggestion]:
BindingFact(bname, _, _, _, _, _, _, _, _, _, _, declared, _) = b
match declared:
case [_, *_]: []
case []:
match fold_shape(b):
case None: []
case Some(shape):
match first_bound_guard(b, bindings, keep):
case None: []
case Some(GuardFact(lit, rel)):
because = concat_String([
"a guard in or reachable from `", bname,
"` compares an Int against the literal ", int_to_String(lit),
" (relation ", relation_text(rel), "), and `", bname, "` folds a list of operations"
])
unlocks = concat_String(["laws.", catalog_fn])
[Suggestion(template, because, unlocks, bound_snippet(b, shape, lit, catalog_fn, phrase, suffix), [bname])]
bindings.flat_map_List(suggest)
def rule_numeric_floor(facts: ProgramFacts) -> List[Suggestion]:
bound_rule_run(facts, is_lower_rel, "numeric-floor", "never_below", "at or above", "floor")
def rule_numeric_ceiling(facts: ProgramFacts) -> List[Suggestion]:
bound_rule_run(facts, is_upper_rel, "numeric-ceiling", "never_above", "at or below", "ceiling")
def rule_fold_ordering(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(bindings, _, _) = facts
def suggest(b: BindingFact) -> List[Suggestion]:
BindingFact(bname, pkg, _, result_type, is_pure, _, _, _, _, _, type_imports, declared, _) = b
match (is_pure, declared):
case (False, _): []
case (_, [_, *_]): []
case (True, []):
match fold_shape(b):
case None: []
case Some(shape):
run_type = fold_run_type(shape)
FoldShape(state_type, op_type, _) = shape
runs = "${bname}_runs"
obligation = "${bname}_order"
because = concat_String([
"`", bname, "` folds a list of operations over a ", render_type(state_type),
"; whether the outcome depends on operation order is a property worth pinning either way"
])
snippet = render_snippet(Snippet(
"${pkg}/Laws",
[law_import(["Domain", "FoldRun", "Obligation", "WitnessTodo", "order_independent"]), binding_import(pkg, bname, type_imports)],
[obligation],
fold_exposes(pkg, type_imports),
[
Note([
[Says("Suggested by the fold-ordering rule. One named hole:")],
[Says(" eq_hole: real equality for ${render_type(result_type)}; it returns True so the")],
[Says(" stub can never report a false violation, and the WitnessTodo blocks")],
[Says(" any pass until it is filled.")],
*gen_hole_note(run_type, "second"),
]),
Def(
"fold_hole",
[],
[Param(Bind("initial"), state_type), Param(Bind("ops"), list_of(op_type))],
result_type,
[],
fold_call(bname, shape)
),
Def(
"eq_hole",
[],
[Param(Bind("left"), result_type), Param(Bind("right"), result_type)],
bool_type,
[Let(Skip, Ref("left")), Let(Skip, Ref("right"))],
Ref("True")
),
describe_hole(run_type, "${bname} run"),
domain_of(runs, "${bname} runs"),
Val(obligation, Call("Obligation", [
Call("order_independent", [Text("${bname} is order independent"), Ref("fold_hole"), Ref("eq_hole"), Ref(runs)]),
Items([Call("WitnessTodo", [
Text("orders can differ"),
Text("fill eq_hole with real equality, then turn this into a Witness that some generated run has at least two operations")
])])
])),
]
))
[Suggestion("fold-ordering", because, "laws.order_independent", snippet, [bname])]
bindings.flat_map_List(suggest)
def rule_unbounded_numeric(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(bindings, tables, _) = facts
# Silence is per package: a guard silences only its own package's
# tables, since the because-text claims no bound is checked in the
# module that owns the table; a guard elsewhere says nothing here.
def pkg_has_guard(pkg: String) -> Bool:
bindings.exists_List(b -> (
BindingFact(_, bpkg, _, _, _, _, _, _, guards, _, _, _, _) = b
match guards:
case []: False
case [_, *_]: eq_String(bpkg, pkg)
))
def suggest(t: TableFact) -> List[Suggestion]:
TableFact(tname, tpkg, fields, _, writers, _, _, _) = t
match (pkg_has_guard(tpkg), writers):
case (True, _): []
case (_, []): []
case (False, [_, *_]):
int_fields = fields.filter_List(f -> (
FieldFact(_, field_type) = f
same_type(field_type, int_type)
))
def per_field(f: FieldFact) -> List[Suggestion]:
FieldFact(fname, _) = f
target = "${tname}.${fname}"
domain = "${fname}_domain"
obligation = "${fname}_floor"
because = concat_String([
"`", target, "` is an Int written by handlers, and no bound on any",
" Int is checked anywhere in this module: is that intended?"
])
snippet = render_snippet(Snippet(
"${tpkg}/Laws",
[law_import(["Domain", "Obligation", "WitnessTodo", "never_below"])],
[obligation],
["Yichus/Law"],
[
Note([
[Says("Suggested by the unbounded-numeric rule. Two named holes:")],
[Says(" floor_hole: the intended lower bound for "), Quotes(target)],
[Says(" the Domain: connect it to the real states this field takes")],
]),
Val("floor_hole", Num(0)),
Def("field_values_hole", [], [Param(Bind("state"), int_type)], list_of(int_type), [], Items([Ref("state")])),
Val(domain, Call("Domain", [Text("${target} values"), Ref("int_to_String"), Ref("None"), Ref("None")])),
Val(obligation, Call("Obligation", [
Call("never_below", [Text("${target} stays at or above the floor"), Ref(domain), Ref("field_values_hole"), Ref("floor_hole")]),
Items([Call("WitnessTodo", [
Text("a written value appears"),
Text("the Int domain is a placeholder; generate the real states ${target} takes")
])])
])),
]
))
[Suggestion("unbounded-numeric", because, "laws.never_below", snippet, [target])]
int_fields.flat_map_List(per_field)
tables.flat_map_List(suggest)
# The access rules group per package: a suggestion's snippet is a whole
# standalone file named `{pkg}/Access` (or `{pkg}/AccessNotes`), so two
# tables sharing a package must share one snippet: two files declaring
# the same package could not both be pasted.
def table_pkg(t: TableFact) -> String:
TableFact(_, tpkg, _, _, _, _, _, _) = t
tpkg
def table_name(t: TableFact) -> String:
TableFact(tname, _, _, _, _, _, _, _) = t
tname
def table_policy(t: TableFact) -> AccessPolicy:
TableFact(_, _, _, _, _, policy, _, _) = t
policy
def distinct_pkgs(ts: List[TableFact]) -> List[String]:
def add(acc: List[String], t: TableFact) -> List[String]:
p = table_pkg(t)
match acc.exists_List(q -> eq_String(p, q)):
case True: acc
case False: [p, *acc]
reverse(ts.foldl_List([], add))
def quoted_list(items: List[String]) -> List[Prose]:
match items:
case []: []
case [first, *rest]: [Quotes(first), *rest.flat_map_List(r -> [Says(", "), Quotes(r)])]
# The policy as its declaration reads; guards and roles are program text.
def policy_prose(policy: AccessPolicy) -> List[Prose]:
match policy:
case Undeclared: [Says("no policy")]
case DeclaredPublic: [Says("Public")]
case DeclaredOwnerScoped: [Says("OwnerScoped")]
case DeclaredGuarded(guards): [Says("Guarded("), *quoted_list(guards), Says(")")]
case DeclaredGuardedOrRoles(guards, roles):
[Says("GuardedOrRoles("), *quoted_list(guards), Says("; requires "), *quoted_list(roles), Says(")")]
case DeclaredPublicReadRoleWrite(roles): [Says("PublicReadRoleWrite(requires "), *quoted_list(roles), Says(")")]
case DeclaredUnder(parent, []): [Says("Under("), Quotes(parent), Says(")")]
case DeclaredUnder(parent, roles): [Says("Under("), Quotes(parent), Says("; or requires "), *quoted_list(roles), Says(")")]
def policy_text(policy: AccessPolicy) -> String:
concat_String(policy_prose(policy).map_List(prose_text))
def backticked(names: List[String]) -> String:
join_String(", ", names.map_List(n -> concat_String(["`", n, "`"])))
# A table handlers read or write with no declared access policy gets the
# paste-ready AccessSpec proposed. OwnerScoped is the safe starting
# point; api_access_check proves or refutes the declaration against the
# compiled IR: the rule proposes, the static checker decides. One
# suggestion per package: its AccessSpec covers every undeclared touched
# table there.
def rule_undeclared_access(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(_, tables, _) = facts
def undeclared_touched(t: TableFact) -> Bool:
TableFact(_, _, _, readers, writers, policy, _, _) = t
match (policy, readers, writers):
case (Undeclared, [_, *_], _) | (Undeclared, _, [_, *_]): True
case _: False
undeclared = tables.filter_List(undeclared_touched)
def per_pkg(pkg: String) -> List[Suggestion]:
names = undeclared.filter_List(t -> eq_String(table_pkg(t), pkg)).map_List(table_name)
subject = match names:
case [one]: [Quotes(one)]
case _: [Says("these tables")]
because = match names:
case [one]:
concat_String([
"handlers touch `", one,
"` and no AccessRule names it: who may read this data is undeclared, so nothing is proven about it"
])
case _:
concat_String([
"handlers touch ", backticked(names),
" and no AccessRule names them: who may read this data is undeclared, so nothing is proven about it"
])
snippet = render_snippet(Snippet(
"${pkg}/Access",
[Import("Yichus/Access", ["AccessRule", "AccessSpec", "OwnerScoped"])],
["access_rules"],
["Yichus/Access"],
[
Note([
[Says("Suggested by the undeclared-access rule: handlers read or write")],
[*subject, Says(" with no declared access policy. OwnerScoped is the")],
[Says("safe starting point; api_access_check proves or refutes it against")],
[Says("the compiled IR. Change to Public only if this data really is.")],
]),
Val("access_rules", Call("AccessSpec", [Items(names.map_List(n -> Call("AccessRule", [Text(n), Ref("OwnerScoped")])))])),
]
))
[Suggestion("undeclared-access", because, "api_access_check", snippet, names)]
distinct_pkgs(undeclared).flat_map_List(per_pkg)
# A declared policy the static checker cannot prove is a finding, not a
# pass: the fix is in the code (key every operation on the table by
# Principal.user_id for OwnerScoped), never in weakening the declaration.
# The snippet is a note file: it compiles as pasted and records the
# finding, because the real change belongs in the handler. One note file
# per package, listing every unproven declaration there.
def rule_unproven_access(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(_, tables, _) = facts
def declared_unproven(t: TableFact) -> Bool:
TableFact(_, _, _, _, _, policy, proven, _) = t
match (policy, proven):
case (Undeclared, _) | (_, True): False
case _: True
unproven = tables.filter_List(declared_unproven)
def per_pkg(pkg: String) -> List[Suggestion]:
in_pkg = unproven.filter_List(t -> eq_String(table_pkg(t), pkg))
names = in_pkg.map_List(table_name)
declarations = in_pkg.map_List(t -> [Says(" "), Quotes(table_name(t)), Says(" declares "), *policy_prose(table_policy(t))])
because = match in_pkg:
case [t]:
concat_String([
"`", table_name(t), "` declares ", policy_text(table_policy(t)),
" but api_access_check cannot prove it from the compiled IR: fix the code, never weaken the declaration"
])
case _:
concat_String([
backticked(names),
" declare access policies api_access_check cannot prove from the compiled IR: fix the code, never weaken the declarations"
])
snippet = render_snippet(Snippet(
"${pkg}/AccessNotes",
[],
[],
[],
[
Note([
[Says("Suggested by the unproven-access rule: these declarations cannot be")],
[Says("proven by the static checker:")],
*declarations,
[Says("Key every db operation on these tables by Principal.user_id (for")],
[Says("OwnerScoped), then run api_access_check for the precise failing")],
[Says("operation. This note file records the findings; the fixes belong")],
[Says("in the handlers.")],
]),
]
))
[Suggestion("unproven-access", because, "api_access_check", snippet, names)]
distinct_pkgs(unproven).flat_map_List(per_pkg)
# --- Conformance derivation ------------------------------------------------
# The engine knows the handler, the table, and the input from the typed
# IR; a first-cut model filled from those facts is a far better starting
# point than a blank Conformance, and it is what lets a non-expert get a
# model at all. The draft models ROW COUNT: sound for a handler that
# appends one row per call, and immediately reported as a located
# divergence (with the exact input) by api_conformance_check for a
# handler that updates or deletes: the user edits the step, never the
# code to match a wrong model.
def table_conformances(t: TableFact) -> List[String]:
TableFact(_, _, _, _, _, _, _, confs) = t
confs
def find_binding(bindings: List[BindingFact], target: String) -> Option[BindingFact]:
iter_value(iter_foldl_List(bindings, None, (_, b) -> (
BindingFact(bname, _, _, _, _, _, _, _, _, _, _, _, _) = b
match eq_String(bname, target):
case True: iter_done(Some(b))
case False: iter_continue(None)
)))
def table_writers(t: TableFact) -> List[String]:
TableFact(_, _, _, _, writers, _, _, _) = t
writers
def add_distinct(acc: List[String], x: String) -> List[String]:
match contains_String(acc, x):
case True: acc
case False: [x, *acc]
# The handler's one modelable input: its parameters minus the world the
# runtime injects (Db, Principal). Exactly one, nameable in the handler's
# package: anything else is out of conformance v1's shape and the rule
# stays silent rather than proposing a draft that cannot compile.
def conformable_input(b: BindingFact) -> Option[TypeRef]:
BindingFact(_, pkg, params, _, _, _, _, _, _, _, _, _, _) = b
inputs = params.flat_map_List(p -> (
ParamFact(_, t) = p
[] if is_world_type(t) else [t]
))
match inputs:
case [one]: Some(one) if nameable_in([one], pkg) else None
case _: None
struct ConformanceDraftee(handler_name: String, input_type: TypeRef)
def draftee_of(bindings: List[BindingFact], confs: List[String], w: String) -> List[ConformanceDraftee]:
match contains_String(confs, w):
case True: []
case False:
match find_binding(bindings, w):
case None: []
case Some(b):
# The draft imports the handler: an unexported one would not compile.
BindingFact(_, _, _, _, _, _, _, _, _, _, _, _, importable) = b
match (importable, conformable_input(b)):
case (True, Some(input_type)): [ConformanceDraftee(w, input_type)]
case _: []
# A writer's n-th table model: `w_model`, then `w_model_2`, ... A table
# name is program text, so it never becomes part of an identifier.
def model_name(w: String, n: Int) -> String:
match n:
case 1: "${w}_model"
case _: "${w}_model_${int_to_String(n)}"
def model_val(w: String, show_input: String, model: String, t_name: String) -> Decl:
Val(model, Call("Conformance", [
Text("${w} row count"),
Text(t_name),
Items([]),
Num(0),
Ref("int_to_String"),
Ref(show_input),
Ref("count_rows"),
Ref("eq_Int"),
Call("handler", [Text(w), Ref(w)]),
Ref("count_step"),
]))
def writer_models(w: String, t_names: List[String], n: Int) -> List[(String, String)]:
recur t_names:
case []: []
case [t_name, *rest]: [(model_name(w, n), t_name), *writer_models(w, rest, n.add(1))]
# One writer's drafts: its show_input once, and a model per table it writes.
def writer_drafts(d: ConformanceDraftee, t_names: List[String]) -> (List[String], List[Decl]):
ConformanceDraftee(w, input_type) = d
show_input = "${w}_show_input"
models = writer_models(w, t_names, 1)
(
models.map_List(((model, _)) -> model),
[
Def(show_input, [], [Param(Skip, input_type)], string_type, [], Text("<input>")),
*models.map_List(((model, t_name)) -> model_val(w, show_input, model, t_name)),
],
)
def draftee_writer(pair: (TableFact, ConformanceDraftee)) -> String:
(_, ConformanceDraftee(w, _)) = pair
w
def rule_unmodeled_conformance(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(bindings, tables, _) = facts
def per_pkg(pkg: String) -> List[Suggestion]:
in_pkg = tables.filter_List(t -> eq_String(table_pkg(t), pkg))
draftees = in_pkg.flat_map_List(t -> (
confs = table_conformances(t)
table_writers(t).flat_map_List(w -> draftee_of(bindings, confs, w).map_List(d -> (t, d)))
))
match draftees:
case []: []
case _:
names = reverse(draftees.map_List(draftee_writer).foldl_List([], add_distinct))
writers = names.flat_map_List(w -> (
match draftees.filter_List(pair -> eq_String(draftee_writer(pair), w)):
case []: []
case [(_, d), *_] as mine: [writer_drafts(d, mine.map_List(((t, _)) -> table_name(t)))]
))
type_imports = reverse(home_names(draftees.map_List(pair -> (
(_, ConformanceDraftee(_, input_type)) = pair
input_type
)), pkg).foldl_List([], add_distinct))
exposes = match type_imports:
case []: ["Yichus/Spec"]
case _: [pkg, "Yichus/Spec"]
a_type = TypeVar("a", [])
because = concat_String([
backticked(names),
" write tables no Conformance binds to a model: the checker cannot say whether the code matches any model of its effect"
])
snippet = render_snippet(Snippet(
"${pkg}/Conformance",
[Import(pkg, [*names, *type_imports]), Import("Yichus/Service", ["handler"]), Import("Yichus/Spec", ["Conformance"])],
writers.flat_map_List(((models, _)) -> models),
exposes,
[
Note([
[Says("Suggested by the unmodeled-conformance rule. First-cut model: ROW")],
[Says("COUNT: init 0 over an empty seed, each call appends one row. For a")],
[Says("handler that updates or deletes instead, api_conformance_check")],
[Says("reports the divergence with the exact input; edit that model's step")],
[Says("(the last argument) to the intended effect, never the code to")],
[Says("match a wrong model. Replace each show_input hole with a real")],
[Says("rendering so counterexamples read in your domain's terms.")],
]),
Def("count_step", ["a"], [Param(Bind("n"), int_type), Param(Skip, a_type)], int_type, [], Call("add", [Ref("n"), Num(1)])),
Def("count_rows", ["a"], [Param(Bind("rows"), list_of(a_type))], int_type, [], Call("foldl_List", [Ref("rows"), Num(0), Ref("count_step")])),
*writers.flat_map_List(((_, decls)) -> decls),
]
))
[Suggestion("unmodeled-conformance", because, "api_conformance_check", snippet, names)]
distinct_pkgs(tables).flat_map_List(per_pkg)
# --- Round trip: a value's own field fed back -------------------------
#
# A pure binding that takes a value and a String (or lists of each), where
# the value's struct carries String fields and the binding (directly or
# through any binding it calls) reads one of them, is a reader or checker
# of text the program also writes: an answer checker given a question and
# an answer, a parser given a record and its rendering. Other field types
# (an order and a quantity) are ordinary arguments, not a round trip.
# Feeding each value its own field back should be accepted: the inverse
# law between whatever produced the field and the binding that reads it.
# The rule matches types only: which field is "its own" and what
# "accepted" means are named holes.
struct OwnFields(read: List[String], unread: List[String])
# own: the field the snippet fills own_hole with (one the checker reads);
# others: the struct's remaining String fields, named in the snippet.
struct RoundTrip(value: StructFact, own: String, others: List[String], lists: Bool)
# The struct's String fields, split by whether the binding reads them
# (a field's readers include every caller of a reader). The fields it
# extracts itself come first: a checker reads the field it checks against
# (an answer checker reads answer_text, not prompt), even when a helper it
# calls reads another.
def own_fields(st: StructFact, b: BindingFact) -> OwnFields:
StructFact(_, _, fields, _) = st
BindingFact(bname, pkg, _, _, _, _, _, _, _, _, _, _, _) = b
me = "${pkg}::${bname}"
texts = fields.flat_map_List(f -> (
StructField(fname, ftype, readers, direct) = f
[(fname, contains_String(direct, me), contains_String(readers, me))] if same_type(ftype, string_type) else []
))
mine = texts.flat_map_List(t -> (
(fname, by_me, _) = t
[fname] if by_me else []
))
through_calls = texts.flat_map_List(t -> (
(fname, by_me, is_read) = t
match (by_me, is_read):
case (False, True): [fname]
case _: []
))
OwnFields(
[*mine, *through_calls],
texts.flat_map_List(t -> (
(fname, _, is_read) = t
[] if is_read else [fname]
))
)
# (value type, lists) when the parameters are a value and a String, or a
# List of values and a List[String].
def value_and_text(params: List[ParamFact]) -> Option[(TypeRef, Bool)]:
match params:
case [ParamFact(_, value_type), ParamFact(_, text_type)]:
match (list_element(value_type), list_element(text_type)):
case (Some(elem), Some(text_elem)): Some((elem, True)) if same_type(text_elem, string_type) else None
case (None, None): Some((value_type, False)) if same_type(text_type, string_type) else None
case _: None
case _: None
def struct_type(st: StructFact) -> TypeRef:
StructFact(sname, spkg, _, _) = st
TypeNamed(spkg, sname, [])
# The snippet names the result type, so a result type it cannot name
# keeps the rule silent rather than proposing a file that cannot compile.
def round_trip_of(structs: List[StructFact], b: BindingFact) -> Option[RoundTrip]:
BindingFact(_, pkg, params, result_type, is_pure, _, _, _, _, _, _, declared, importable) = b
match (is_pure, importable, nameable_in([result_type], pkg), declared, value_and_text(params)):
case (True, True, True, [], Some((value_type, lists))):
value_struct = structs.filter_List(st -> (
StructFact(_, _, _, st_importable) = st
same_type(struct_type(st), value_type) if st_importable else False
))
match value_struct:
case [st, *_]:
match own_fields(st, b):
case OwnFields([own, *more], unread): Some(RoundTrip(st, own, [*more, *unread], lists))
case _: None
case []: None
case _: None
def field_pattern(fields: List[StructField], own: String) -> List[Pat]:
fields.map_List(f -> (
StructField(fname, _, _, _) = f
Bind("own") if eq_String(fname, own) else Skip
))
def rule_round_trip(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(bindings, _, structs) = facts
def suggest(b: BindingFact) -> List[Suggestion]:
match round_trip_of(structs, b):
case None: []
case Some(RoundTrip(st, first_own, rest, lists)):
BindingFact(bname, pkg, _, result_type, _, _, _, _, _, _, type_imports, _, _) = b
StructFact(sname, spkg, fields, _) = st
value_type = struct_type(st)
values = "${bname}_values"
obligation = "${bname}_round_trip"
struct_imports = [] if eq_String(spkg, pkg) else [Import(spkg, [sname])]
call = Call(bname, [Items([Ref("x")]), Items([Call("own_hole", [Ref("x")])])]) if lists else Call(bname, [Ref("x"), Call("own_hole", [Ref("x")])])
others = match rest:
case []: []
case _: [[Says(" (the other String fields of ${sname}: ${join_String(", ", rest)})")]]
because = concat_String([
"`", bname, "` takes a ", sname, " and a String, and a ", sname,
" carries String fields of its own (", join_String(", ", [first_own, *rest]),
"): feeding a value its own field back is a round trip worth pinning"
])
snippet = render_snippet(Snippet(
"${pkg}/Laws",
[law_import(["Domain", "Obligation", "WitnessTodo", "inverse"]), binding_import(pkg, bname, type_imports), *struct_imports],
[obligation],
[spkg, "Yichus/Law"],
[
Note([
[Says("Suggested by the round-trip rule. Two named holes:")],
[Says(" own_hole: the field that is the value's own String; filled")],
[Says(" with one "), Names(bname), Says(" or a binding it calls reads")],
*others,
[Says(" accepted_hole: whether the result counts as accepted; it returns")],
[Says(" True so the stub can never report a false violation, and the")],
[Says(" WitnessTodo blocks any pass until it is filled.")],
[Says("The Domain's gen is a third hole: the type-driven default builds")],
[Says("arbitrary ${sname} values, not ones the program produces. Replace")],
[Says("the first None in the Domain with Some(seed -> ...) built by the")],
[Says("program's own constructor of ${sname} values.")],
]),
Def("own_hole", [], [Param(Bind("x"), value_type)], string_type, [Let(Unpack(sname, field_pattern(fields, first_own)), Ref("x"))], Ref("own")),
Def("accepted_hole", [], [Param(Bind("result"), result_type)], bool_type, [Let(Skip, Ref("result"))], Ref("True")),
Def("fed_back", [], [Param(Bind("x"), value_type)], bool_type, [], Call("accepted_hole", [call])),
Def("accepted", [], [Param(Skip, value_type)], bool_type, [], Ref("True")),
describe_hole(value_type, sname),
domain_of(values, "${sname} values"),
Val(obligation, Call("Obligation", [
Call("inverse", [Text("${bname} accepts each ${sname}'s own ${first_own}"), Ref(values), Ref("accepted"), Ref("fed_back"), Ref("eq_Bool")]),
Items([Call("WitnessTodo", [
Text("the value is one the program produces"),
Text("fill own_hole and accepted_hole, give the Domain a gen built by the program's own constructor, then turn this into a Witness that some generated value is accepted")
])])
])),
]
))
[Suggestion("round-trip", because, "laws.inverse", snippet, [bname])]
bindings.flat_map_List(suggest)
# --- Calculation answers ---------------------------------------------------
# A program that is a calculation (it keeps no records and nothing in it
# reads, writes or calls out) whose exported function works out a number,
# or a record of numbers, from numbers entered, with no law yet, and is no
# helper another part of its package calls: which of those numbers can never go
# below a floor (a payment, a total) is a rule worth stating, and nothing
# states one. A program with effects gets the rules about its records
# instead. The snippet names the calculation's inputs and its answer, so the
# rule fires only where a standalone file can name them.
float64_package = "Yichus/Num/Float64"
float64_type = TypeNamed(float64_package, "Float64", [])
def is_number(t: TypeRef) -> Bool:
[int_type, float64_type].exists_List(n -> same_type(t, n))
# The answer's numbers: the answer itself, or each number field of the
# program's own record it is, with its type. None for any other answer.
enum Answer:
Number(answer_type: TypeRef)
Fields(record: StructFact, numbers: List[StructField])
def answer_of(structs: List[StructFact], t: TypeRef) -> Option[Answer]:
match is_number(t):
case True: Some(Number(t))
case False:
records = structs.filter_List(st -> (
StructFact(_, _, _, st_importable) = st
same_type(struct_type(st), t) if st_importable else False
))
match records:
case [st, *_]:
StructFact(_, _, fields, _) = st
numbers = fields.filter_List(f -> (
StructField(_, ftype, _, _) = f
is_number(ftype)
))
match numbers:
case []: None
case _: Some(Fields(st, numbers))
case []: None
# Several inputs are one tuple the Domain generates.
def inputs_type(params: List[ParamFact]) -> TypeRef:
match params:
case [ParamFact(_, t)]: t
case _: TypeNamed(predef_package, "Tuple${int_to_String(size_List(params))}", params.map_List(p -> (
ParamFact(_, t) = p
t
)))
# One input is the parameter itself; several are taken apart from the tuple.
def inputs_name(params: List[ParamFact]) -> String:
match params:
case [ParamFact(n, _)]: n
case _: "input"
def inputs_lets(params: List[ParamFact]) -> List[Let]:
match params:
case [_]: []
case _: [Let(Unpack("", params.map_List(p -> (
ParamFact(n, _) = p
Bind(n)
))), Ref("input"))]
def at_floor(name: String, t: TypeRef) -> Expr:
match same_type(t, int_type):
case True: Call("at_least", [Ref(name), Ref("floor_hole")])
case False: Call("at_least_Float64", [Ref(name), Call("int_to_Float64", [Ref("floor_hole")])])
def rule_calculation_answers(facts: ProgramFacts) -> List[Suggestion]:
ProgramFacts(bindings, tables, structs) = facts
effects = bindings.exists_List(b -> (
BindingFact(_, _, _, _, is_pure, _, _, _, _, _, _, _, _) = b
False if is_pure else True
))
calculation = not(effects).and(tables matches [])
def suggest(b: BindingFact) -> List[Suggestion]:
BindingFact(bname, pkg, params, result_type, is_pure, _, _, _, _, _, type_imports, declared, importable) = b
param_types = params.map_List(p -> (
ParamFact(_, t) = p
t
))
nameable = nameable_in([result_type, *param_types], pkg)
numbers_in = all_true(param_types.map_List(is_number))
# a calculation that calls itself is no helper of its own
helper = bindings.exists_List(other -> (
BindingFact(oname, opkg, _, _, _, _, _, _, _, ocalls, _, _, _) = other
match (eq_String(opkg, pkg), eq_String(oname, bname)):
case (True, False): contains_String(ocalls, bname)
case _: False
))
found = None if helper else (answer_of(structs, result_type) if numbers_in else None)
match (is_pure, importable, nameable, declared, params, fold_shape(b), found):
case (True, True, True, [], [_, *_], None, Some(answer)):
call = Call(bname, params.map_List(p -> (
ParamFact(n, _) = p
Ref(n)
)))
(answer_lets, checks, number_types, what) = match answer:
case Number(t): ([], [at_floor("answer", t)], [t], "a number")
case Fields(StructFact(sname, _, fields, _), numbers):
pats = fields.map_List(f -> (
StructField(fname, ftype, _, _) = f
Bind(fname) if is_number(ftype) else Skip
))
([Let(Unpack(sname, pats), Ref("answer"))],
numbers.map_List(f -> (
StructField(fname, ftype, _, _) = f
at_floor(fname, ftype)
)),
numbers.map_List(f -> (
StructField(_, ftype, _, _) = f
ftype
)),
"a ${sname} of numbers (${join_String(", ", numbers.map_List(f -> (
StructField(fname, _, _, _) = f
fname
)))})")
floats = number_types.exists_List(t -> same_type(t, float64_type))
input = inputs_type(params)
inputs = "${bname}_inputs"
obligation = "${bname}_answers"
float_import = [Import(float64_package, ["int_to_Float64"])] if floats else []
law_names = ["Domain", "Law", "Obligation", "WitnessTodo", "all_true",
*(["at_least"] if number_types.exists_List(t -> same_type(t, int_type)) else []),
*(["at_least_Float64"] if floats else [])]
because = concat_String([
"`", bname, "` works out ", what, " from what is entered, and no law checks it:",
" which of its numbers can never go below a floor (a payment, a total) is a rule worth stating"
])
snippet = render_snippet(Snippet(
"${pkg}/Laws",
[law_import(law_names), binding_import(pkg, bname, type_imports), *float_import],
[obligation],
["Yichus/Law"],
[
Note([
[Says("Suggested by the calculation-answers rule. Three named holes:")],
[Says(" in_use_hole: the inputs the calculation is used with (a loan")],
[Says(" above zero, say); it answers False so the draft can never report")],
[Says(" a false violation, and the WitnessTodo blocks any pass until it")],
[Says(" is filled.")],
[Says(" floor_hole: the lowest each number may be.")],
[Says(" answer_hole: one check for each number that must stay at or above")],
[Says(" the floor; leave out a number that may go below it, such as a")],
[Says(" difference that can be negative.")],
[Says("The Domain's gen is a fourth hole when the type-driven default")],
[Says("cannot build ${render_type(input)} values: replace the first None")],
[Says("with Some(seed -> ...).")],
]),
Val("floor_hole", Num(0)),
Def("in_use_hole", [], [Param(Skip, input)], bool_type, [], Ref("False")),
Def("answer_hole", [], [Param(Bind(inputs_name(params)), input)], bool_type,
[*inputs_lets(params), Let(Bind("answer"), call), *answer_lets],
Call("implies", [Call("in_use_hole", [Ref(inputs_name(params))]), Call("all_true", [Items(checks)])])),
describe_hole(input, "${bname} inputs"),
domain_of(inputs, "${bname} inputs"),
Val(obligation, Call("Obligation", [
Call("Law", [Text("no number ${bname} works out goes below its floor"), Ref(inputs), Ref("answer_hole")]),
Items([Call("WitnessTodo", [
Text("the inputs the rule is about"),
Text("fill in_use_hole, floor_hole and answer_hole from the person's rule, then turn this into a Witness that in_use_hole accepts some input")
])])
])),
]
))
[Suggestion("calculation-answers", because, "laws.Law", snippet, [bname])]
case _: []
bindings.flat_map_List(suggest) if calculation else []
default_rules = RuleSet("yichus-default", [
Rule("numeric-floor", rule_numeric_floor),
Rule("numeric-ceiling", rule_numeric_ceiling),
Rule("fold-ordering", rule_fold_ordering),
Rule("round-trip", rule_round_trip),
Rule("calculation-answers", rule_calculation_answers),
Rule("unbounded-numeric", rule_unbounded_numeric),
Rule("undeclared-access", rule_undeclared_access),
Rule("unproven-access", rule_unproven_access),
Rule("unmodeled-conformance", rule_unmodeled_conformance),
])