use super::derivation::Side;
use super::{Derivation, Formulas, Image, Logic, Node, NodeId, Rule, Symbols};
use crate::Error;
use crate::export::Form;
use crate::export::rocq::{CLASSICAL_PRELUDE, Options, Unsupported, identifiers};
use crate::hash::HashMap;
use crate::linear::proofs::InfId;
use crate::linear::search::{Classical, Disproof, Refutation};
use std::fmt::Write;
const USED: &[&str] = &[
"conj",
"or_introl",
"or_intror",
"proj1",
"proj2",
"I",
"True",
"False",
"False_ind",
"NNPP",
"iff",
"and",
"or",
"not",
];
const ROCQ: Symbols = Symbols {
not: "~ ",
and: "/\\",
or: "\\/",
implies: "->",
iff: "<->",
truth: "True",
falsity: "False",
};
enum Task {
Enter(InfId),
Text(String),
Bind(Vec<((NodeId, Side), String)>),
Unbind(Vec<(NodeId, Side)>),
}
struct Certificate<'a> {
derivation: &'a Derivation,
atoms: Vec<String>,
names: HashMap<(NodeId, Side), Vec<String>>,
fresh: u64,
}
impl Certificate<'_> {
fn formula(&self, id: NodeId) -> String {
let mut out = String::new();
let formulas: &Formulas = self.derivation.formulas();
let negation = matches!(formulas.node(id), super::Node::Not(_));
if negation {
out.push('(');
}
formulas
.write(&mut out, id, true, &ROCQ, |o, a| {
o.write_str(&self.atoms[a as usize])
})
.unwrap();
if negation {
out.push(')');
}
out
}
fn name(&mut self, letter: char) -> String {
self.fresh += 1;
format!("{letter}'{}", self.fresh)
}
fn of(&self, node: NodeId, side: Side) -> String {
self.names
.get(&(node, side))
.and_then(|v| v.last())
.cloned()
.expect("a checked derivation names only formulas in scope")
}
fn goal(&self, id: InfId) -> String {
match self.derivation.inference(id).right.first() {
Some(&c) => self.formula(c),
None => "False".to_owned(),
}
}
fn tasks(&mut self, id: InfId) -> Vec<Task> {
use Rule::*;
use Side::{Left, Right};
let d = self.derivation;
let inference = d.inference(id);
let classical = d.logic() == Logic::Classical;
let f = d.formulas();
let principal = inference
.principal
.map(|(side, at)| inference.side(side)[at]);
let p = principal.unwrap_or(NodeId(0));
let operands = f.node(p).operands();
let (a, b) = (operands.0.unwrap_or(p), operands.1.unwrap_or(p));
let premises = &inference.premises;
let text = |s: String| Task::Text(s);
let premise = |n: usize, binds: Vec<((NodeId, Side), String)>| {
let keys = binds.iter().map(|(k, _)| *k).collect();
[
Task::Bind(binds),
Task::Enter(premises[n]),
Task::Unbind(keys),
]
};
let fa = self.formula(a);
let fb = self.formula(b);
let mut tasks = Vec::new();
let excluded = |this: &mut Self, n: usize, node: NodeId, tasks: &mut Vec<Task>| {
let k = this.name('k');
let shown = this.formula(node);
tasks.push(text(format!("(NNPP {shown} (fun {k} : ~ {shown} => ")));
tasks.extend(premise(n, vec![((node, Right), k)]));
tasks.push(text("))".to_owned()));
};
match inference.rule {
Open => unreachable!("an open goal has no term"),
Axiom => {
let (x, y) = (inference.left[0], inference.right[0]);
let h = self.of(x, Left);
tasks.push(text(if classical {
format!("({} {h})", self.of(y, Right))
} else {
h
}));
}
WeakenLeft | ContractLeft | ContractRight | TrueLeft | FalseRight => {
tasks.extend(premise(0, vec![]));
}
WeakenRight if classical => tasks.extend(premise(0, vec![])),
WeakenRight => {
tasks.push(text(format!("(False_ind {} ", self.goal(id))));
tasks.extend(premise(0, vec![]));
tasks.push(text(")".to_owned()));
}
TrueRight if classical => tasks.push(text(format!("({} I)", self.of(p, Right)))),
TrueRight => tasks.push(text("I".to_owned())),
FalseLeft if classical => tasks.push(text(self.of(p, Left))),
FalseLeft => tasks.push(text(format!(
"(False_ind {} {})",
self.goal(id),
self.of(p, Left)
))),
AndLeft | AndLeft1 | AndLeft2 | IffLeft | IffLeft1 | IffLeft2 => {
let h = self.of(p, Left);
let iff = matches!(inference.rule, IffLeft | IffLeft1 | IffLeft2);
let (x, y) = if iff { implications(f, a, b) } else { (a, b) };
let pair = if iff {
format!("({h} : {} /\\ {})", self.formula(x), self.formula(y))
} else {
h
};
let mut binds = Vec::new();
let mut lets = String::from("(");
for (keep, node, projection) in [
(!matches!(inference.rule, AndLeft2 | IffLeft2), x, "proj1"),
(!matches!(inference.rule, AndLeft1 | IffLeft1), y, "proj2"),
] {
if keep {
let n = self.name('h');
write!(
lets,
"let {n} : {} := {projection} {pair} in ",
self.formula(node)
)
.unwrap();
binds.push(((node, Left), n));
}
}
tasks.push(text(lets));
tasks.extend(premise(0, binds));
tasks.push(text(")".to_owned()));
}
AndRight | IffRight => {
let iff = inference.rule == IffRight;
let (x, y) = if iff { implications(f, a, b) } else { (a, b) };
let cast = format!(" : {} /\\ {}", self.formula(x), self.formula(y));
if classical {
tasks.push(text(format!("({} (conj ", self.of(p, Right))));
excluded(self, 0, x, &mut tasks);
tasks.push(text(" ".to_owned()));
excluded(self, 1, y, &mut tasks);
tasks.push(text(format!("{cast}))")));
} else {
tasks.push(text("(conj ".to_owned()));
tasks.extend(premise(0, vec![]));
tasks.push(text(" ".to_owned()));
tasks.extend(premise(1, vec![]));
tasks.push(text(format!("{cast})")));
}
}
OrLeft => {
let h = self.of(p, Left);
let (h1, h2) = (self.name('h'), self.name('h'));
let goal = if classical {
"False".to_owned()
} else {
self.goal(id)
};
tasks.push(text(format!(
"(match {h} return {goal} with or_introl {h1} => "
)));
tasks.extend(premise(0, vec![((a, Left), h1)]));
tasks.push(text(format!(" | or_intror {h2} => ")));
tasks.extend(premise(1, vec![((b, Left), h2)]));
tasks.push(text(" end)".to_owned()));
}
OrRight => {
let k = self.of(p, Right);
let (k1, k2) = (self.name('k'), self.name('k'));
tasks.push(text(format!(
"(let {k1} : ~ {fa} := fun x' => {k} (or_introl x') in \
let {k2} : ~ {fb} := fun x' => {k} (or_intror x') in "
)));
tasks.extend(premise(0, vec![((a, Right), k1), ((b, Right), k2)]));
tasks.push(text(")".to_owned()));
}
OrRight1 | OrRight2 => {
let (constructor, x) = if inference.rule == OrRight1 {
("or_introl", a)
} else {
("or_intror", b)
};
if classical {
tasks.push(text(format!("({} ({constructor} ", self.of(p, Right))));
excluded(self, 0, x, &mut tasks);
tasks.push(text("))".to_owned()));
} else {
tasks.push(text(format!("({constructor} ")));
tasks.extend(premise(0, vec![]));
tasks.push(text(")".to_owned()));
}
}
ImpliesRight | NotRight => {
let h = self.name('h');
if classical {
tasks.push(text(format!("({} (fun {h} : {fa} => ", self.of(p, Right))));
} else {
tasks.push(text(format!("(fun {h} : {fa} => ")));
}
if classical && inference.rule == ImpliesRight {
let k = self.name('k');
tasks.push(text(format!("NNPP {fb} (fun {k} : ~ {fb} => ")));
tasks.extend(premise(0, vec![((a, Left), h), ((b, Right), k)]));
tasks.push(text(")".to_owned()));
} else {
tasks.extend(premise(0, vec![((a, Left), h)]));
}
tasks.push(text(if classical { "))" } else { ")" }.to_owned()));
}
NotLeft if premises.len() == 1 => {
let k = self.name('k');
tasks.push(text(format!(
"(let {k} : ~ {fa} := {} in ",
self.of(p, Left)
)));
tasks.extend(premise(0, vec![((a, Right), k)]));
tasks.push(text(")".to_owned()));
}
ImpliesLeft | NotLeft => {
let h = self.of(p, Left);
let (consequent, shown) = if inference.rule == NotLeft {
let falsity = f.ids.get(&super::Node::False).copied();
(falsity.expect("a checked ¬L has ⊥"), "False".to_owned())
} else {
(b, fb.clone())
};
let h2 = self.name('h');
tasks.push(text(format!("(let {h2} : {shown} := {h} ")));
if classical {
excluded(self, 0, a, &mut tasks);
} else {
tasks.push(text("(".to_owned()));
tasks.extend(premise(0, vec![]));
tasks.push(text(")".to_owned()));
}
tasks.push(text(" in ".to_owned()));
tasks.extend(premise(1, vec![((consequent, Left), h2)]));
tasks.push(text(")".to_owned()));
}
}
tasks
}
}
fn implications(formulas: &Formulas, a: NodeId, b: NodeId) -> (NodeId, NodeId) {
let id = |node| {
formulas
.ids
.get(&node)
.copied()
.expect("a checked derivation holds the implications of its equivalences")
};
(
id(super::Node::Implies(a, b)),
id(super::Node::Implies(b, a)),
)
}
pub(crate) fn write(
derivation: &Derivation,
options: &Options,
out: &mut impl Write,
mut stop: impl FnMut() -> bool,
) -> Result<(), Error> {
if derivation
.inferences()
.iter()
.any(|i| i.rule() == Rule::Open)
{
return Err(Unsupported::Open.into());
}
let unbounded = crate::Limits {
work: None,
..crate::Limits::default()
};
derivation.check(&unbounded, |_| stop())?;
let classical = derivation.logic() == Logic::Classical;
let formulas = derivation.formulas();
let mut atoms = identifiers(formulas.atom_names(), options.lemma.as_str());
for atom in &mut atoms {
while USED.contains(&atom.as_str()) {
atom.push('\'');
}
}
let mut certificate = Certificate {
derivation,
atoms,
names: HashMap::default(),
fresh: 0,
};
if options.form == Form::Standalone {
let prelude = match &options.prelude {
Some(prelude) => Some(prelude.as_str()),
None if classical => Some(CLASSICAL_PRELUDE),
None => None,
};
if let Some(prelude) = prelude {
write!(out, "{}\n\n", prelude.trim_end())?;
}
}
let root = derivation.inference(derivation.root());
let mut statement = String::new();
let mut binders = String::new();
if !certificate.atoms.is_empty() {
let all = certificate.atoms.join(" ");
write!(statement, "forall {all} : Prop, ").unwrap();
write!(binders, "({all} : Prop) ").unwrap();
}
for &h in &root.left {
let name = certificate.name('h');
let shown = certificate.formula(h);
write!(statement, "{shown} -> ").unwrap();
write!(binders, "({name} : {shown}) ").unwrap();
certificate
.names
.entry((h, Side::Left))
.or_default()
.push(name);
}
let mut body = String::new();
let mut closing = String::new();
let right: Vec<String> = root.right.iter().map(|&d| certificate.formula(d)).collect();
match right.len() {
0 => statement.push_str("False"),
_ if !classical => statement.push_str(&right[0]),
n => {
let disjunction = right.join(" \\/ ");
statement.push_str(&disjunction);
if n == 1 {
let k = certificate.name('k');
write!(body, "NNPP {} (fun {k} : ~ {} => ", right[0], right[0]).unwrap();
certificate
.names
.entry((root.right[0], Side::Right))
.or_default()
.push(k);
} else {
let k = certificate.name('k');
write!(
body,
"NNPP ({disjunction}) (fun {k} : ~ ({disjunction}) => "
)
.unwrap();
for (i, &d) in root.right.iter().enumerate() {
let ki = certificate.name('k');
let mut injection = "x'".to_owned();
if i + 1 < n {
injection = format!("(or_introl {injection})");
}
for _ in 0..i {
injection = format!("(or_intror {injection})");
}
write!(
body,
"let {ki} : ~ {} := fun x' => {k} {injection} in ",
right[i]
)
.unwrap();
certificate
.names
.entry((d, Side::Right))
.or_default()
.push(ki);
}
}
closing.push(')');
}
}
let lambda = if binders.is_empty() {
String::new()
} else {
format!("fun {binders}=> ")
};
write!(
out,
"Lemma {} : {statement}.\nProof.\n exact ({lambda}{body}",
options.lemma
)?;
let mut stack = vec![Task::Enter(derivation.root())];
while let Some(task) = stack.pop() {
match task {
Task::Enter(id) => {
let tasks = certificate.tasks(id);
stack.extend(tasks.into_iter().rev());
if stop() {
return Err(Error::Refused(crate::limits::Refusal::Stopped {
phase: crate::limits::Phase::Write,
}));
}
}
Task::Text(text) => out.write_str(&text)?,
Task::Bind(binds) => {
for (key, name) in binds {
certificate.names.entry(key).or_default().push(name);
}
}
Task::Unbind(keys) => {
for key in keys {
if let Some(names) = certificate.names.get_mut(&key) {
names.pop();
}
}
}
}
}
write!(out, "{closing}).\nQed.\n")?;
Ok(())
}
pub(crate) fn not_valid(
image: &Image,
disproof: &Disproof,
options: &Options,
out: &mut impl Write,
) -> Result<(), Error> {
let Refutation::Classical(Classical { assignment }) = disproof.refutation() else {
return Err(Unsupported::NotValid.into());
};
disproof.check()?;
let sequent = image.ordinary();
let formulas = sequent.formulas();
let linear = image.sequent();
let value = |name: &str| linear.atom(name).is_some_and(|a| assignment[a.index()]);
let mut truth: Vec<bool> = Vec::with_capacity(formulas.len());
for id in 0..formulas.len() {
let of = |k: NodeId| truth[k.index()];
let node = formulas.node(NodeId(id as u32));
let t = match node {
Node::Atom(a) => value(&formulas.atom_names()[a as usize]),
Node::True => true,
Node::False => false,
Node::Not(a) => !of(a),
Node::And(a, b) => of(a) && of(b),
Node::Or(a, b) => of(a) || of(b),
Node::Implies(a, b) => !of(a) || of(b),
Node::Iff(a, b) => of(a) == of(b),
};
truth.push(t);
}
let holds = |id: NodeId| truth[id.index()];
if !sequent.left().iter().all(|&h| holds(h)) || sequent.right().iter().any(|&d| holds(d)) {
return Err(Unsupported::NotValid.into());
}
let mut atoms = identifiers(formulas.atom_names(), options.lemma.as_str());
for atom in &mut atoms {
while USED.contains(&atom.as_str()) {
atom.push('\'');
}
}
if options.form == Form::Standalone
&& let Some(prelude) = &options.prelude
{
write!(out, "{}\n\n", prelude.trim_end())?;
}
let shown = |id: NodeId| {
let mut text = String::new();
let negation = matches!(formulas.node(id), Node::Not(_));
if negation {
text.push('(');
}
formulas
.write(&mut text, id, true, &ROCQ, |o, a| {
o.write_str(&atoms[a as usize])
})
.expect("a string takes the text");
if negation {
text.push(')');
}
text
};
let mut statement = String::new();
if !atoms.is_empty() {
write!(statement, "forall {} : Prop, ", atoms.join(" ")).expect("a string");
}
for &h in sequent.left() {
write!(statement, "{} -> ", shown(h)).expect("a string");
}
let right: Vec<String> = sequent.right().iter().map(|&d| shown(d)).collect();
if right.is_empty() {
statement.push_str("False");
} else {
statement.push_str(&right.join(" \\/ "));
}
let instances: Vec<&str> = (0..atoms.len())
.map(|a| {
if value(&formulas.atom_names()[a]) {
"True"
} else {
"False"
}
})
.collect();
let specialize = if instances.is_empty() {
String::new()
} else {
format!(" specialize (H {}).", instances.join(" "))
};
write!(
out,
"Lemma {} : ~ ({statement}).\nProof.\n intro H.{specialize} tauto.\nQed.",
options.lemma
)?;
Ok(())
}