aver-cert 0.1.5

Independent artifact certificate engine and verifier for Aver WebAssembly
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
-- Authored by aver-cert; never accepted from the certificate.
--
-- The checker's audit program. It is elaborated with only the Lean toolchain
-- in scope: no certificate module is imported while this file is elaborated,
-- so nothing a package declares (an instance, a notation, a name in some
-- namespace) can change what the code below computes. At run time it loads
-- the built `CheckerWitness` environment and inspects it.
import Lean

namespace AverCertAudit

open Lean

/-- The certificate package's own modules (validated module roots). -/
def packageModules : List Name := @PACKAGE_MODULES@

/-- The axiom whitelist. -/
def allowed : List Name := @ALLOWED@

/-- Roots whose closure must stay inside the whitelist: the accepted
    artifact and every report pin. -/
def strictRoots : List Name := @STRICT_ROOTS@

/-- Every record a bridge encoder reads, with the accessors it lists. -/
def recordShapes : List (Name × List Name) := @RECORDS@

/-- Every sum a bridge encoder matches on, with the constructors it lists and
    the number of fields it encodes for each. -/
def sumShapes : List (Name × List (Name × Nat)) := @SUMS@

/-- The namespace roots the wall and the checker declare in. A package
    declares nothing under them. -/
def wallRoots : List Name := @WALL_ROOTS@

/-- The only constants a package declares directly under `AverCert`: the
    manifest's `subject` and `manifest`. -/
def packageAverCertLeaves : List Name := @PACKAGE_AVERCERT_LEAVES@

/-- The only namespaces under `AverCert` a package declares in: its plans,
    byte facts, final theorem, bridges and law corollaries. -/
def packageAverCertChildren : List Name := @PACKAGE_AVERCERT_CHILDREN@

/-- Why the package constant `n` is refused for where it is declared, if it
    is. A package name under a wall namespace, or one nesting `AverCert`
    below its first component, is where a dotted reference in the wall or the
    witness could resolve first, since Lean tries the innermost enclosing
    namespace before the root. Under `AverCert` the admitted names are exact
    shapes: `AverCert.manifest`, `AverCert.subject`, and names at least one
    component deep in a producer namespace. The caller exempts exactly two
    kinds of package constant from this rule: a private constant, and a
    `leanAuxiliary` one. -/
def namespaceRefusal (n : Name) : Option String :=
  match n.eraseMacroScopes.components with
  | [] => none
  | first :: rest =>
    if rest.any (fun c => c == `AverCert || c == `AverCertChecker) then
      some s!"a certificate module declares {n}, which nests a checker namespace"
    else if first == `AverCert then
      match rest with
      | [leaf] =>
        if packageAverCertLeaves.contains leaf then none
        else some s!"a certificate module declares {n} inside the checker's AverCert namespace"
      | second :: _ :: _ =>
        if packageAverCertChildren.contains second then none
        else some s!"a certificate module declares {n} inside the checker's AverCert namespace"
      | [] => some s!"a certificate module declares {n} inside the checker's AverCert namespace"
    else if wallRoots.contains first then
      some s!"a certificate module declares {n} inside the checker's {first} namespace"
    else none

/-- The longest proper prefix of `n` that is itself a declared constant, if
    any. Lean resolves a dotted identifier to the longest prefix that is a
    constant and reads the rest as fields, so a package constant
    `AverCert.manifest.subject` is what `AverCert.manifest.subject.contracts`
    would mean. The witness reads every field through a wall projection
    function; this refusal keeps a second layer under that. -/
def extendedConstant (env : Environment) (n : Name) : Option Name := Id.run do
  let mut p := n.getPrefix
  for _ in [0:n.getNumParts] do
    if p.isAnonymous then return none
    if env.contains p then return some p
    p := p.getPrefix
  return none

/-- Whether `s` is `<stem><k>`, where `k` is digits, possibly joined by
    underscores (`match_1_1`), and starts with a digit. -/
def numberedAs (stem s : String) : Bool :=
  let rest := s.toList.drop stem.length
  s.startsWith stem &&
    (match rest with
     | c :: _ => c.isDigit
     | [] => false) &&
    rest.all (fun c => c.isDigit || c == '_')

/-- Whether the last component of `n` is `proof_<k>`, `match_<k>` or
    `eq_<k>`, the names Lean gives an abstracted proof, a matcher and an
    equation lemma. (The environment the audit imports does not rebuild the
    matcher extension's state, so a matcher is recognised by its name.) -/
def numberedAuxiliary : Name → Bool
  | .str _ s => numberedAs "proof_" s || numberedAs "match_" s || numberedAs "eq_" s
  | _ => false

/-- Whether the last component of `n` is `eq_def` or `eq_unfold`, the
    names of the unfolding lemmas Lean realizes for a definition. -/
def unfoldAuxiliary : Name → Bool
  | .str _ s => s == "eq_def" || s == "eq_unfold"
  | _ => false

/-- Whether `n` is an auxiliary Lean itself declares beside the constant
    `n.getPrefix`. Two cases:
    * beside a constant the package does NOT declare (a wall or core
      constant), a reserved name such as an equation lemma. That parent
      existed before every package module, and Lean refuses a user
      declaration of a reserved name whose parent exists, so such a
      constant can only have been realized by Lean, in the package module
      that first unfolded the parent. (Beside a package constant a reserved
      name is not exempt on that ground: a package can declare `V.h.eq_1`
      itself before it declares `V.h`.)
    * beside a constant the package declares, an internal (`_`-prefixed)
      compiler constant, an abstracted `proof_<k>`, a matcher `match_<k>`,
      an equation `eq_<k>`, or an unfolding lemma `eq_def` or `eq_unfold`,
      recognised by name alone.
    None of these is a field name a wall structure has, so no field read
    can land on one. -/
def leanAuxiliary (env : Environment) (inPkg : Name → Bool) (n : Name) : Bool :=
  let parent := n.getPrefix
  env.contains parent &&
    (if inPkg parent then n.isInternal || numberedAuxiliary n || unfoldAuxiliary n
     else isReservedName env n)

/-- Every bridged law's statement definition in the witness, with the model
    constants its bridges are about. -/
def lawModelUses : List (Name × List Name) := @LAW_MODEL_USES@

def lawRoots : List Name := @LAW_ROOTS@
def bridgedLawRoots : List Name := @BRIDGED_LAW_ROOTS@
def bridgeRoots : List Name := @BRIDGE_ROOTS@

/-- Classes whose instances carry proofs, not choices: an instance of one of
    these cannot make a proposition mean something else, and a false one
    needs an axiom the audit sees. Admitted at any type. -/
def proofClasses : List Name :=
  [``Decidable, ``DecidableEq, ``DecidableRel, ``DecidablePred, ``Nonempty,
   ``ReflBEq, ``LawfulBEq]

/-- Data classes admitted only at a type the package itself declares as an
    inductive type: `==`, a default value, and the `SizeOf` instance Lean
    generates for every inductive type, of the model's own records and sums. -/
def ownTypeClasses : List Name := [``Inhabited, ``BEq, ``SizeOf]

def decline (reason : String) : IO UInt32 := do
  IO.println ("@DECLINE_MARKER@ " ++ reason)
  return 1

def moduleOf (env : Environment) (n : Name) : Option Name :=
  match env.getModuleIdxFor? n with
  | some idx => env.header.moduleNames[idx.toNat]?
  | none => none

def inPackage (env : Environment) (n : Name) : Bool :=
  match moduleOf env n with
  | some m => packageModules.contains m
  | none => false

-- The axiom memo begins (a unit test elaborates this part alone).
/-! ### Axioms, collected once for every root

`Lean.collectAxioms` starts from nothing on every call: the environment
the audit imports does not load the extension that stores each imported
constant's axioms, so every call walks the root's whole closure again,
and the roots of a large certificate share most of theirs. The walk below
reads the same edges `collectAxioms` reads (a constant's type, the value
of a definition, theorem or opaque, the constructors of an inductive), and
keeps one memo for all roots.

The memo holds a constant's axioms only once they are final. Constants
can reach each other in a cycle (an inductive and its constructors), and
while such a constant is still being walked what has been collected for
it is partial, so the walk finds the cycles (Tarjan's strongly connected
components) and records one set for a whole component when it is
complete: the axioms of its members and of everything they reach. What a
root reports is therefore exactly the axioms reachable from it, the same
set `collectAxioms` returns on its own, whichever roots were asked
before. -/

structure AxiomMemo where
  /-- The final axiom set of every constant whose component is complete. -/
  done : NameMap NameSet := {}
  /-- The depth-first index and low link of every constant being walked. -/
  index : NameMap Nat := {}
  low : NameMap Nat := {}
  /-- Constants being walked whose component is not complete, in visit order. -/
  stack : Array Name := #[]
  onStack : NameSet := {}
  /-- Axioms found so far for a constant being walked: its own, and the
      final sets of the successors outside its component. -/
  partialAxioms : NameMap NameSet := {}
  next : Nat := 0

/-- The constants `collectAxioms` visits after `c`, and whether `c` is itself
    an axiom. -/
def axiomEdges (env : Environment) (c : Name) : Bool × Array Name :=
  let used (e : Expr) : Array Name := e.getUsedConstants
  match env.checked.get.find? c with
  | some (.axiomInfo v) => (true, used v.type)
  | some (.defnInfo v) => (false, used v.type ++ used v.value)
  | some (.thmInfo v) => (false, used v.type ++ used v.value)
  | some (.opaqueInfo v) => (false, used v.type ++ used v.value)
  | some (.quotInfo _) => (false, #[])
  | some (.ctorInfo v) => (false, used v.type)
  | some (.recInfo v) => (false, used v.type)
  | some (.inductInfo v) => (false, used v.type ++ v.ctors.toArray)
  | none => (false, #[])

partial def axiomWalk (env : Environment) (c : Name) : StateM AxiomMemo Unit := do
  let s ← get
  if s.done.contains c || s.index.contains c then return
  let (isAxiom, succs) := axiomEdges env c
  modify fun s => { s with
    index := s.index.insert c s.next, low := s.low.insert c s.next, next := s.next + 1,
    stack := s.stack.push c, onStack := s.onStack.insert c,
    partialAxioms := s.partialAxioms.insert c (if isAxiom then ({} : NameSet).insert c else {}) }
  for w in succs do
    axiomWalk env w
    let s ← get
    match s.done.find? w with
    | some axs =>
      -- `w` is in a complete component: its set is final.
      let mine := (s.partialAxioms.find? c).getD {}
      set { s with partialAxioms := s.partialAxioms.insert c (axs.foldl (·.insert ·) mine) }
    | none =>
      -- `w` is on the stack, in `c`'s component: joined when it completes.
      let lw := (s.low.find? w).getD 0
      let lc := (s.low.find? c).getD 0
      if lw < lc then set { s with low := s.low.insert c lw }
  let s ← get
  if s.low.find? c == s.index.find? c then
    -- `c` roots a component: pop it and give every member the joined set.
    let mut members : Array Name := #[]
    let mut stack := s.stack
    repeat
      match stack.back? with
      | none => break
      | some m =>
        stack := stack.pop
        members := members.push m
        if m == c then break
    let joined := members.foldl
      (fun acc m => ((s.partialAxioms.find? m).getD {}).foldl (·.insert ·) acc) ({} : NameSet)
    set { s with
      stack := stack,
      onStack := members.foldl (·.erase ·) s.onStack,
      partialAxioms := members.foldl (·.erase ·) s.partialAxioms,
      done := members.foldl (·.insert · joined) s.done }

/-- The axioms reachable from `n`, sorted, reading and extending `memo`. -/
def axiomsOf (env : Environment) (memo : IO.Ref AxiomMemo) (n : Name) : IO (Array Name) := do
  let s ← memo.get
  let s := (axiomWalk env n).run s |>.2
  memo.set s
  return ((s.done.find? n).getD {}).toArray.qsort Name.lt
-- The axiom memo ends.

def runMeta (env : Environment) (x : MetaM α) : IO α := do
  let (a, _) ← (x.run' {} {}).toIO
    { fileName := "<aver-cert audit>", fileMap := default } { env := env }
  return a

/-- Whether the type of the declaration `n` ends in `Prop` (it is a
    proposition former, e.g. a structure or an inductive in `Prop`). -/
def isPropFormer (env : Environment) (type : Expr) : IO Bool :=
  runMeta env (Meta.forallTelescopeReducing type fun _ body => return body.isProp)

/-- Why a record encoder is refused, if it is: the type must be a structure
    outside `Prop`, the encoder must list exactly its fields in declaration
    order, and no field may be a proof. A proof field (`h : False`) or an
    unlisted field would let a bridge quantify over values the plan never
    sees, or over none at all. -/
def recordRefusal (env : Environment) (ty : Name) (fields : List Name) : IO (Option String) := do
  let some info := env.find? ty | return some s!"bridge record {ty} is not declared"
  unless isStructure env ty do
    return some s!"bridge record {ty} is not a structure"
  if ← isPropFormer env info.type then
    return some s!"bridge record {ty} is a proposition"
  unless (getStructureFields env ty).toList == fields do
    return some s!"the bridge encoder of {ty} does not list exactly its fields in order"
  for field in fields do
    let some proj := getProjFnForField? env ty field
      | return some s!"bridge record {ty} has no projection for {field}"
    let some projInfo := env.find? proj
      | return some s!"bridge record {ty} has no projection for {field}"
    let proof ← runMeta env (Meta.forallTelescopeReducing projInfo.type fun _ body => Meta.isProp body)
    if proof then
      return some s!"bridge record {ty} has the proof field {field}"
  return none

/-- Why a sum encoder is refused, if it is: the type must be an inductive
    outside `Prop` whose constructors are exactly the listed ones in order,
    each with the listed number of fields, none of them a proof. -/
def sumRefusal (env : Environment) (ty : Name) (ctors : List (Name × Nat)) : IO (Option String) := do
  let some (.inductInfo info) := env.find? ty | return some s!"bridge sum {ty} is not an inductive type"
  if ← isPropFormer env info.type then
    return some s!"bridge sum {ty} is a proposition"
  unless info.ctors == ctors.map (·.1) do
    return some s!"the bridge encoder of {ty} does not list exactly its constructors in order"
  for (ctor, fields) in ctors do
    let some (.ctorInfo ci) := env.find? ctor | return some s!"bridge constructor {ctor} is not declared"
    unless ci.numFields == fields do
      return some s!"the bridge encoder of {ctor} does not encode exactly its fields"
    let proof ← runMeta env (Meta.forallTelescopeReducing ci.type fun xs _ => do
      let mut found := false
      for x in xs.toList.drop ci.numParams do
        if ← Meta.isProp (← Meta.inferType x) then found := true
      return found)
    if proof then
      return some s!"bridge constructor {ctor} has a proof field"
  return none

/-- Whether `cls` is declared a class by the module that declares it. Read
    off that module's own class-extension entries: the environment the audit
    imports does not rebuild the extension's state, so `isClass` would answer
    false for every imported class. -/
def declaredClass (env : Environment) (cls : Name) : Bool :=
  match env.getModuleIdxFor? cls with
  | some idx => (classExtension.getModuleEntries env idx).any (·.name == cls)
  | none => false

/-- The conclusion of a (non-reducing) pi telescope. -/
def conclusion : Expr → Expr
  | .forallE _ _ body _ => conclusion body
  | e => e

/-- The value an admitted core instance must have, when its class and
    arguments are one of the two data instances the model prelude declares
    over core types: `Coe Int Float` and `HAdd String String String`. -/
def expectedCoreValue (cls : Name) (args : Array Expr) : Option Expr :=
  let one := Level.succ Level.zero
  if cls == ``Coe && args.size == 2 && args[0]! == mkConst ``Int && args[1]! == mkConst ``Float then
    some (mkAppN (mkConst ``Coe.mk [one, one])
      #[mkConst ``Int, mkConst ``Float,
        .lam `n (mkConst ``Int) (mkApp (mkConst ``Float.ofInt) (.bvar 0)) .default])
  else if cls == ``HAdd && args.size == 3 && args.all (· == mkConst ``String) then
    some (mkAppN (mkConst ``HAdd.mk [Level.zero, Level.zero, Level.zero])
      #[mkConst ``String, mkConst ``String, mkConst ``String, mkConst ``String.append])
  else none

/-- Why the instance `inst` (declared in a package module) is refused, if it
    is. The class is read off the ELABORATED type: a name alias or a class
    parent projection does not change the constant at its head. -/
def instanceRefusal (env : Environment) (inst : Name) : Option String :=
  match env.find? inst with
  | none => some s!"instance {inst} has no declaration"
  | some info =>
    let concl := conclusion info.type
    match concl.getAppFn with
    | .const cls _ =>
      let args := concl.getAppArgs
      if proofClasses.contains cls then none
      else if ownTypeClasses.contains cls then
        match args[0]?.map Expr.getAppFn with
        | some (.const ty _) =>
          match env.find? ty with
          | some (.inductInfo _) =>
            if inPackage env ty then none
            else some s!"instance {inst} of {cls} is at a type the package does not declare"
          | _ => some s!"instance {inst} of {cls} is not at an inductive type"
        | _ => some s!"instance {inst} of {cls} is not at a named type"
      else if inPackage env cls && declaredClass env cls then none
      else match expectedCoreValue cls args with
        | some expected =>
          match info.value? with
          | some value =>
            if value == expected then none
            else some s!"instance {inst} of {cls} does not have the admitted value"
          | none => some s!"instance {inst} of {cls} has no value"
        | none => some s!"instance {inst} of class {cls} is not admitted in a certificate"
    | _ => some s!"instance {inst} has no class at its head"

def main : IO UInt32 := do
  initSearchPath (← findSysroot)
  let env ← importModules #[{ module := `CheckerWitness }] {}
  -- One axiom memo for every root below (see `AxiomMemo`).
  let memo ← IO.mkRef ({} : AxiomMemo)
  -- 1. Names reserved for the checker's witness.
  for (name, _) in env.constants.map₁.toList do
    if (`AverCertChecker).isPrefixOf name && !(moduleOf env name == some `CheckerWitness) then
      return ← decline s!"a certificate module declares {name} under the checker's reserved prefix"
  -- 1b. Names under the wall's and the checker's namespaces.
  --     Exactly two kinds of package constant are exempt from both rules of
  --     this step, because no name the wall or the witness writes resolves
  --     to them: a private one (a match splitter or other auxiliary Lean
  --     builds while a package proof unfolds a wall definition), which no
  --     other module can name, and a `leanAuxiliary` one: a reserved name
  --     (an equation lemma) realized for a wall or core constant, which
  --     states that constant's own fact, or, beside a package constant, an
  --     internal compiler constant or a numbered or unfolding auxiliary.
  --     A package constant under `AverCert` must also not extend another
  --     declared constant's name, since a dotted reference to that constant's
  --     fields would resolve to it.
  for (name, _) in env.constants.map₁.toList do
    if inPackage env name then
      let auxiliary := isPrivateName name || leanAuxiliary env (inPackage env) name
      unless auxiliary do
        if let some reason := namespaceRefusal name then
          return ← decline reason
        if name.getRoot == `AverCert then
          if let some parent := extendedConstant env name then
            return ← decline s!"a certificate module declares {name}, which extends the declared constant {parent}, so a field read of {parent} could resolve to it"
  -- 2. Parser extensions and instances declared by package modules.
  for m in packageModules do
    match env.getModuleIdx? m with
    | none => pure ()
    | some idx =>
      unless (Parser.parserExtension.ext.getModuleEntries env idx).isEmpty do
        return ← decline s!"certificate module {m} extends the parser (notation, syntax or an operator)"
      for entry in Meta.instanceExtension.ext.getModuleEntries env idx do
        match entry with
        | .scoped ns _ =>
          return ← decline s!"certificate module {m} declares a scoped instance in {ns}"
        | .global e =>
          match e.globalName? with
          | none => return ← decline s!"certificate module {m} declares an anonymous instance"
          | some inst =>
            match instanceRefusal env inst with
            | some reason => return ← decline reason
            | none => pure ()
  -- 3. The shapes the bridge encoders read.
  for (ty, fields) in recordShapes do
    if let some reason ← recordRefusal env ty fields then
      return ← decline reason
  for (ty, ctors) in sumShapes do
    if let some reason ← sumRefusal env ty ctors then
      return ← decline reason
  -- 3b. The law statements. The witness elaborates them at the root, where a
  --     `_root_.`-spelled model name is exactly the root constant, whatever
  --     else the package declares; this re-checks the outcome on the
  --     elaborated terms: each bridged law's statement must use every model
  --     constant its bridges are about.
  for (stmt, models) in lawModelUses do
    let some info := env.find? stmt
      | return ← decline s!"the witness does not declare {stmt}"
    let some value := info.value?
      | return ← decline s!"the law statement {stmt} has no value"
    let used := value.getUsedConstants
    for model in models do
      unless used.contains model do
        return ← decline s!"the law statement {stmt} does not use the bridged model {model}"
  -- 4. The accepted root and the report pins: whitelisted axioms only.
  for root in strictRoots do
    if (env.find? root).isNone then
      return ← decline s!"the witness does not declare {root}"
    for used in ← axiomsOf env memo root do
      unless allowed.contains used do
        return ← decline s!"non-whitelisted axiom: {used} (under {root})"
  -- 5. Per-claim audit lines, read back by the checker.
  for root in lawRoots ++ bridgedLawRoots ++ bridgeRoots do
    if (env.find? root).isNone then
      return ← decline s!"the witness does not declare {root}"
  let audit (marker : String) (roots : List Name) : IO Unit := do
    for root in roots do
      let offending := (← axiomsOf env memo root).filter (fun used => !allowed.contains used)
      if offending.isEmpty then
        IO.println s!"{marker} {root} ok"
      else
        let names := ",".intercalate (offending.toList.map Name.toString)
        IO.println s!"{marker} {root} axioms {names}"
  audit "@LAW_MARKER@" lawRoots
  audit "@BRIDGED_LAW_MARKER@" bridgedLawRoots
  audit "@BRIDGE_MARKER@" bridgeRoots
  IO.println "@OK_MARKER@"
  return 0

end AverCertAudit

def main : IO UInt32 := AverCertAudit.main