Bosatsu packages

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),
])