const BRIDGE_SUPPORT_MODULE: &str = "BridgeSupport";
const BRIDGE_IMAGES_MODULE: &str = "BridgeImages";
const BRIDGE_BODIES_MODULE: &str = "BridgeBodies";
fn bridge_part_header(description: &str, imports: &BTreeSet<String>) -> String {
let imports: String = imports.iter().map(|name| format!("import {name}\n")).collect();
format!(
"-- {description}\n{imports}\n\
set_option autoImplicit false\n\
set_option maxRecDepth 200000\n\
set_option linter.unusedSimpArgs false\n\
set_option linter.unusedVariables false\n\
set_option maxHeartbeats {FILE_HEARTBEATS}\n\n\
namespace AverCert.Bridge\n\n"
)
}
fn render_bridge_support() -> String {
let mut s = bridge_part_header(
"Shared decoders and symbolic-evaluation lemmas; no program data.",
&BTreeSet::from(["GrammarBridge".into()]),
);
s.push_str(LIST_DECODERS);
s.push_str(STEP_LEMMAS);
s.push_str(
"\ntheorem withDefault_ite {α ε : Type} (F : Except ε α → α → α)\n \
(c : Prop) [Decidable c] (e : ε) (v d : α) :\n \
F (if c then Except.error e else Except.ok v) d =\n \
if c then F (Except.error e) d else F (Except.ok v) d := by\n \
split <;> rfl\n\nend AverCert.Bridge\n"
);
s
}
const BRIDGE_ELEMS_MODULE: &str = "BridgeElems";
fn full_rcases_pattern(enc: &SourceEncoder) -> Option<String> {
let sub = |e: &SourceEncoder| full_rcases_pattern(e).unwrap_or_else(|| "_".to_string());
match enc {
SourceEncoder::Record { fields, .. } => Some(format!(
"⟨{}⟩",
fields.iter().map(|(_, f)| sub(f)).collect::<Vec<_>>().join(", ")
)),
SourceEncoder::Tuple { elems, .. } => Some(format!(
"⟨{}⟩",
elems.iter().map(sub).collect::<Vec<_>>().join(", ")
)),
_ => rcases_pattern(enc).map(|_| match enc {
SourceEncoder::Sum { ctors, .. } => format!(
"({})",
ctors
.iter()
.map(|(_, fields)| format!(
"⟨{}⟩",
fields.iter().map(sub).collect::<Vec<_>>().join(", ")
))
.collect::<Vec<_>>()
.join(" | ")
),
SourceEncoder::Option(e) => format!("(⟨⟩ | {})", sub(e)),
SourceEncoder::Result { ok, err } => format!("({} | {})", sub(err), sub(ok)),
_ => "_".to_string(),
}),
}
}
fn render_bridge_elems(plan: &BridgePlan) -> String {
let mut imports: BTreeSet<String> = plan.elem_roots.clone();
imports.insert(BRIDGE_SUPPORT_MODULE.into());
let mut s = bridge_part_header(
"Decoders of the elements of the bridged functions' List arguments.",
&imports,
);
let mut sound = String::from(
"\n | (have e := decListInt_sound _ hl; subst e)\
\n | (have e := decListBool_sound _ hl; subst e)\
\n | (have e := decListString_sound _ hl; subst e)",
);
let mut enc = String::from(
"AverCert.GrammarBridge.decodeStr_strBytes, decListInt_enc, decListBool_enc, \
decListString_enc, decList",
);
for (k, elem) in plan.elems.elems.iter().enumerate() {
let ty = elem.enc.binder_type();
let gty = elem.enc.grammar_ty();
let at = |value: &str| elem.enc.encode(value, &mut 0);
let list_at =
|value: &str| SourceEncoder::List(Box::new(elem.enc.clone())).encode(value, &mut 0);
s.push_str(&format!(
"/-- Decode one element of a List of `{ty}`. -/\n\
noncomputable def decElem_{k} : _root_.AverCert.Grammar.SVal → _root_.Option {ty} := \
fun a =>\n"
));
let rhs = |alt: &Alt| {
let mut rhs = format!("_root_.Option.some {}", alt.source);
for (v, t, decode) in alt.binds.iter().rev() {
rhs = format!("({decode} {v}).bind (fun {t} => {rhs})");
}
rhs
};
match elem.alts.as_slice() {
[only] if only.binds.len() == 1 && only.pattern == only.binds[0].0 => {
s.push_str(&format!(" (fun {} => {}) a\n\n", only.pattern, rhs(only)));
}
alts => {
s.push_str(" match a with\n");
for alt in alts {
s.push_str(&format!(" | {} => {}\n", alt.pattern, rhs(alt)));
}
s.push_str(" | _ => _root_.Option.none\n\n");
}
}
let cases = full_rcases_pattern(&elem.enc)
.map(|pattern| format!("rcases x with {pattern}\n all_goals "))
.unwrap_or_default();
s.push_str(&format!(
"theorem decElem_{k}_sound : ∀ (v : _root_.AverCert.Grammar.SVal) (x : {ty}),\n \
decElem_{k} v = _root_.Option.some x → v = {x} := by\n \
intro v x h\n \
unfold decElem_{k} at h\n \
(try split at h) <;> (try simp only [_root_.Option.bind_eq_some_iff, \
_root_.Option.some.injEq, reduceCtorEq, AverCert.GrammarBridge.decodeStr_eq_some] at h)\n \
all_goals (repeat' (first\n \
| (obtain ⟨_, rfl, h⟩ := h)\n \
| (obtain ⟨_, hl, h⟩ := h\n \
first{sound})))\n \
all_goals (try subst h)\n \
all_goals rfl\n\n\
theorem decElem_{k}_enc : ∀ (x : {ty}), decElem_{k} ({x}) = _root_.Option.some x := by\n \
intro x\n \
{cases}first\n \
| (simp [decElem_{k}, {enc}]; done)\n \
| (simp [decElem_{k}, {enc}] <;> rfl)\n\n\
theorem decList_{k}_enc : ∀ (l : _root_.List {ty}),\n \
decList {gty} decElem_{k} {list_l} = _root_.Option.some l :=\n \
decList_enc _ _ _ decElem_{k}_enc\n\n\
theorem decList_{k}_sound : ∀ (a : _root_.List {ty}) {{v : _root_.AverCert.Grammar.SVal}},\n \
decList {gty} decElem_{k} v = _root_.Option.some a → v = {list_a} :=\n \
decList_sound _ _ _ decElem_{k}_sound\n\n\
theorem decList_{k}_split {{v : _root_.AverCert.Grammar.SVal}} {{a : _root_.List {ty}}}\n \
(h : decList {gty} decElem_{k} v = _root_.Option.some a) :\n \
(v = _root_.AverCert.Grammar.SVal.nil {gty} ∧ a = []) ∨\n \
∃ x t, v = _root_.AverCert.Grammar.SVal.cons {gty} ({x}) {list_t} ∧ a = x :: t :=\n \
decList_split _ _ _ decElem_{k}_sound h\n\n\
theorem cons_map_{k} (x : {ty}) (l : _root_.List {ty}) :\n \
({x}) :: l.map (fun x => {x}) = (x :: l).map (fun x => {x}) := rfl\n\n\
theorem listOf_nil_{k} : _root_.AverCert.Grammar.listOf? (_root_.AverCert.Grammar.SVal.nil {gty}) =\n \
_root_.Option.some ({gty}, ([] : _root_.List {ty}).map (fun x => {x})) := rfl\n\n",
x = at("x"),
list_l = list_at("l"),
list_a = list_at("a"),
list_t = list_at("t"),
));
sound.push_str(&format!(
"\n | (have e := decList_{k}_sound _ hl; subst e)"
));
enc.push_str(&format!(", decElem_{k}_enc, decList_{k}_enc"));
}
s.push_str("end AverCert.Bridge\n");
s
}
fn render_bridge_literals(plan: &BridgePlan) -> (String, BTreeMap<Vec<u8>, usize>) {
let mut s = bridge_part_header(
"The bytes of the String literals the bridge steps rewrite with.",
&BTreeSet::from(["GrammarBridge".into()]),
);
s.push_str(
"-- Read UTF-8 bytes directly from the literal's characters.\n\
theorem strBytes_ofList (cs : List Char) :\n \
AverCert.GrammarBridge.strBytes (String.ofList cs) =\n \
(cs.flatMap String.utf8EncodeChar).map UInt8.toNat := by\n \
unfold AverCert.GrammarBridge.strBytes\n \
rw [String.toByteArray_ofList]\n \
unfold List.utf8Encode\n \
rw [List.toList_data_toByteArray]\n\n"
);
let mut index = BTreeMap::new();
for (i, bytes) in plan.literals.iter().enumerate() {
let Some(text) = lean_string_literal(bytes) else { continue };
let chars = lean_char_list(std::str::from_utf8(bytes).unwrap());
let list = bytes.iter().map(u8::to_string).collect::<Vec<_>>().join(", ");
s.push_str(&format!(
"theorem strLit_{i} : AverCert.GrammarBridge.strBytes {text} = [{list}] := by\n \
first | exact (strBytes_ofList {chars}).trans (by decide +kernel) | sorry\n\n"
));
index.insert(bytes.clone(), i);
}
s.push_str("end AverCert.Bridge\n");
(s, index)
}
fn render_bridge_lean(
plan: &BridgePlan,
model_roots: &[String],
exports_module: &str,
) -> (String, Vec<(String, String)>) {
let steps: Vec<&BridgedFn> = plan.fns.values().collect();
let owners: BTreeMap<u32, usize> = steps.iter().enumerate()
.map(|(i, b)| (b.func_idx, i / BRIDGE_STEPS_PER_MODULE)).collect();
let (literals, lit_index) = render_bridge_literals(plan);
let mut parts = vec![
(format!("{BRIDGE_SUPPORT_MODULE}.lean"), render_bridge_support()),
(format!("{BRIDGE_LITS_MODULE}.lean"), literals),
];
if !plan.elems.elems.is_empty() {
parts.push((format!("{BRIDGE_ELEMS_MODULE}.lean"), render_bridge_elems(plan)));
}
let mut defs_imports: BTreeSet<String> = model_roots.iter().cloned().collect();
defs_imports.insert(BRIDGE_SUPPORT_MODULE.into());
for (i, slice) in steps.chunks(BRIDGE_STEPS_PER_MODULE).enumerate() {
let mut imports: BTreeSet<String> = slice.iter().map(|b| b.model_root.clone()).collect();
imports.insert(BRIDGE_SUPPORT_MODULE.into());
if slice.iter().any(|b| !b.elem_decoders.is_empty()) {
imports.insert(BRIDGE_ELEMS_MODULE.into());
}
let name = format!("{BRIDGE_IMAGES_MODULE}{i}");
let mut s = bridge_part_header("One slice of source decoders and images.", &imports);
for b in slice { render_fn_defs(b, &mut s); }
s.push_str("end AverCert.Bridge\n");
parts.push((format!("{name}.lean"), s));
defs_imports.insert(name);
}
let mut defs = bridge_part_header("The complete source image table.", &defs_imports);
render_image_table(&plan.fns, &mut defs);
defs.push_str("end AverCert.Bridge\n");
parts.push((format!("{BRIDGE_DEFS_MODULE}.lean"), defs));
for (i, slice) in steps.chunks(BRIDGE_STEPS_PER_MODULE).enumerate() {
let mut imports = BTreeSet::from([BRIDGE_SUPPORT_MODULE.into(), BRIDGE_LITS_MODULE.into()]);
for b in slice {
for f in image_dependencies(b) {
imports.insert(format!("{BRIDGE_IMAGES_MODULE}{}", owners[&f]));
}
}
let mut body = bridge_part_header("Cached body proofs, parametric in the source image table.", &imports);
for b in slice {
render_step_body(b, &plan.fns, &lit_index, plan.with_default, &plan.elems, &mut body);
}
body.push_str("end AverCert.Bridge\n");
parts.push((format!("{BRIDGE_BODIES_MODULE}{i}.lean"), body));
let imports = BTreeSet::from([
BRIDGE_DEFS_MODULE.into(), "Plans".into(), format!("{BRIDGE_BODIES_MODULE}{i}"),
]);
let mut bindings = bridge_part_header("Bind cached body proofs to this certificate's authoritative plans.", &imports);
for b in slice { render_step_binding(b, &mut bindings); }
bindings.push_str("end AverCert.Bridge\n");
parts.push((format!("{BRIDGE_STEPS_MODULE}{i}.lean"), bindings));
}
parts.push((format!("{BRIDGE_NAMES_MODULE}.lean"), render_bridge_names(exports_module)));
let slices = plan.bridges.len().div_ceil(BRIDGE_PROOFS_PER_MODULE).max(1);
let per_slice = plan.bridges.len().div_ceil(slices).max(1);
let mut corollaries = String::new();
let mut proof_imports = String::new();
for (i, slice) in plan.bridges.chunks(per_slice).enumerate() {
let name = format!("{BRIDGE_PROOF_MODULE}{i}");
let images: BTreeSet<_> = slice.iter()
.map(|(_, f)| format!("{BRIDGE_IMAGES_MODULE}{}", owners[f])).collect();
let mut assembly = bridge_part_header(
"Cached export assembly, parametric in the plan and image tables.", &images,
);
for (bridge, f) in slice { render_export_assembly(bridge, *f, plan, &mut assembly); }
assembly.push_str("end AverCert.Bridge\n");
parts.push((format!("{BRIDGE_ASSEMBLY_MODULE}{i}.lean"), assembly));
let needed_steps: BTreeSet<usize> = slice.iter()
.flat_map(|(_, f)| closure_of(*f, &plan.fns)).map(|f| owners[&f]).collect();
let step_imports: String = needed_steps.iter()
.map(|i| format!("import {BRIDGE_STEPS_MODULE}{i}\n")).collect();
let mut part = format!(
"-- One slice of the plan-equals-source bridges of this certificate: the\n\
-- export theorems, over the step lemmas of the slices imported below.\n\
import {BRIDGE_NAMES_MODULE}\n\
import {BRIDGE_ASSEMBLY_MODULE}{i}\n\
{step_imports}\n\
set_option autoImplicit false\n\
set_option maxRecDepth 200000\n\
set_option linter.unusedSimpArgs false\n\
set_option linter.unusedVariables false\n\
set_option maxHeartbeats {FILE_HEARTBEATS}\n\n\
namespace AverCert.Bridge\n\n"
);
for (bridge, func_idx) in slice {
render_export(bridge, *func_idx, plan, &mut part, &mut corollaries);
}
part.push_str("end AverCert.Bridge\n");
parts.push((format!("{name}.lean"), part));
proof_imports.push_str(&format!("import {name}\n"));
}
let mut bridge = format!(
"-- The plan-equals-source claims of this certificate: each bridge theorem\n\
-- of the `{BRIDGE_PROOF_MODULE}` slices conjoined with the artifact-level\n\
-- `Holds` fact.\n\
{proof_imports}\
import Final\n"
);
for root in model_roots { bridge.push_str(&format!("import {root}\n")); }
bridge.push_str("\nset_option autoImplicit false\n\n");
bridge.push_str(&corollaries);
(bridge, parts)
}
#[cfg(test)]
mod literal_proof_tests {
use super::*;
#[test]
fn literal_proofs_encode_characters_without_building_byte_arrays() {
let literals = [b"".to_vec(), b"a'\"\\\n\r\t".to_vec(), "é中🦀".as_bytes().to_vec(), vec![0xff]];
let plan = BridgePlan {
fns: BTreeMap::new(), bridges: Vec::new(), declined: Vec::new(),
depth: BTreeMap::new(), literals: literals.into_iter().collect(),
with_default: false, entries: BTreeMap::new(), type_pieces: Vec::new(),
elems: ElemDecoders::default(), elem_roots: BTreeSet::new(),
};
let (text, index) = render_bridge_literals(&plan);
assert_eq!(index.len(), 3, "invalid UTF-8 is still not a String literal");
assert_eq!(text.matches("theorem strBytes_ofList").count(), 1);
assert!(text.contains("String.toByteArray_ofList"));
assert!(text.contains("List.toList_data_toByteArray"));
assert!(text.contains("(strBytes_ofList []).trans (by decide +kernel)"));
assert!(text.contains("['a', (Char.ofNat 39), (Char.ofNat 34), (Char.ofNat 92), (Char.ofNat 10), (Char.ofNat 13), (Char.ofNat 9)]"));
assert!(text.contains("[(Char.ofNat 233), (Char.ofNat 20013), (Char.ofNat 129408)]"));
assert!(text.contains("[195, 169, 228, 184, 173, 240, 159, 166, 128]"));
for (bytes, i) in index {
let literal = lean_string_literal(&bytes).unwrap();
assert!(text.contains(&format!("theorem strLit_{i} : AverCert.GrammarBridge.strBytes {literal} =")));
}
}
}