use super::sequents::{FoExpression, Sequent};
use crate::limits::Limits;
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, Member};
use crate::linear::proofs::{Branch, Named, Node, NodeId, Proof as Prf};
use crate::wire::{self, Readable};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
#[derive(Copy, Clone, Debug, Serialize, Deserialize)]
#[serde(rename = "N")]
pub(super) enum Step {
#[serde(rename = "ax")]
Ax(u32, u32),
#[serde(rename = "⊗")]
Tensor(u32, u32, u32),
#[serde(rename = "⅋")]
Par(u32, u32),
#[serde(rename = "1")]
One(u32),
#[serde(rename = "⊥")]
Bot(u32, u32),
#[serde(rename = "&")]
With(u32, u32, u32),
#[serde(rename = "⊕₁")]
PlusLeft(u32, u32),
#[serde(rename = "⊕₂")]
PlusRight(u32, u32),
#[serde(rename = "⊤")]
Top(u32),
#[serde(rename = "!")]
Bang(u32, u32),
#[serde(rename = "?")]
Quest(u32, u32),
#[serde(rename = "copy")]
Copy(u32, u32),
#[serde(rename = "wk")]
Weaken(u32, u32),
#[serde(rename = "mix")]
Mix(u32, u32),
#[serde(rename = "cut")]
Cut(u32, u32, u32),
#[serde(rename = "∀")]
Forall(u32, u32, u32),
#[serde(rename = "∃")]
Exists(u32, u32, u32),
}
#[derive(Clone, Debug, Default, Serialize, Deserialize)]
#[serde(deny_unknown_fields)]
pub(super) struct Instances {
members: Vec<(u32, u32)>,
frames: Vec<(Option<u32>, u32)>,
terms: Vec<FoExpression>,
}
impl Instances {
fn of(table: &crate::linear::Instances, forest: &Forest) -> Self {
use crate::linear::sequents::FoTerm;
let terms = crate::linear::occurrences::instances::Terms {
fo: &forest.sequent().fo,
table,
};
let fo = |t: &FoTerm| match *t {
FoTerm::Bound(i) => FoExpression::Bound(i),
FoTerm::Eigen(a) => FoExpression::Eigen(a.get()),
FoTerm::Meta(_) => unreachable!("a proof's table holds no metavariable"),
FoTerm::App(f, args) => {
FoExpression::App(f.get(), terms.list(args).iter().map(|t| t.get()).collect())
}
};
Self {
members: table
.members
.iter()
.map(|&(o, f)| (o.get(), f.get()))
.collect(),
frames: table
.frames
.iter()
.map(|&(p, t)| (p.map(crate::linear::FrameId::get), t.get()))
.collect(),
terms: table.terms().iter().map(fo).collect(),
}
}
fn within(
self,
forest: &Forest,
limits: &Limits,
) -> Result<crate::linear::Instances, crate::Error> {
use crate::linear::occurrences::{FrameId, OccId};
use crate::linear::sequents::{Eigen, FoTerm, FoTermId, Symbol};
let entries = (self.members.len() as u64)
.saturating_add(self.frames.len() as u64)
.saturating_add(self.terms.len() as u64);
if let Some(limit) = limits.terms
&& entries > limit
{
return Err(crate::Error::Refused(crate::limits::Refusal::Terms {
terms: entries,
limit,
}));
}
let mut table = crate::linear::Instances::new(forest);
for term in self.terms {
match term {
FoExpression::Bound(i) => {
table.push_term(FoTerm::Bound(i));
}
FoExpression::Eigen(k) => {
table.eigen(Eigen::new(k));
}
FoExpression::App(f, items) => {
let items: Vec<FoTermId> = items.into_iter().map(FoTermId::new).collect();
table.apply(Symbol::new(f), &items);
}
}
}
for (parent, term) in self.frames {
table.frame(parent.map(FrameId::new), FoTermId::new(term));
}
for (o, f) in self.members {
table.member(OccId::new(o), FrameId::new(f));
}
Ok(table)
}
}
#[derive(Clone, Debug, Serialize, Deserialize)]
pub(super) struct Proof {
#[serde(
default,
skip_serializing_if = "Option::is_none",
deserialize_with = "wire::version"
)]
version: Option<u32>,
sequent: Sequent,
nodes: Vec<Step>,
#[serde(default, skip_serializing_if = "Option::is_none")]
mode: Option<Mode>,
#[serde(default, skip_serializing_if = "Option::is_none")]
goal: Option<Vec<u32>>,
#[serde(default, skip_serializing_if = "Option::is_none")]
instances: Option<Instances>,
}
impl From<Node> for Step {
fn from(n: Node) -> Self {
use Node::*;
use Step as S;
let (o, n_) = (|o: Member| o.get(), |p: NodeId| p.get());
match n {
Ax(a, b) => S::Ax(o(a), o(b)),
Tensor(x, l, r) => S::Tensor(o(x), n_(l), n_(r)),
Par(x, p) => S::Par(o(x), n_(p)),
One(x) => S::One(o(x)),
Bot(x, p) => S::Bot(o(x), n_(p)),
With(x, l, r) => S::With(o(x), n_(l), n_(r)),
Plus(x, Branch::Left, p) => S::PlusLeft(o(x), n_(p)),
Plus(x, Branch::Right, p) => S::PlusRight(o(x), n_(p)),
Top(x) => S::Top(o(x)),
Bang(x, p) => S::Bang(o(x), n_(p)),
Quest(x, p) => S::Quest(o(x), n_(p)),
Copy(x, p) => S::Copy(o(x), n_(p)),
Weaken(x, p) => S::Weaken(o(x), n_(p)),
Mix(l, r) => S::Mix(n_(l), n_(r)),
Cut(a, l, r) => S::Cut(o(a), n_(l), n_(r)),
Forall(x, a, p) => S::Forall(o(x), a.get(), n_(p)),
Exists(x, w, p) => S::Exists(o(x), w.get(), n_(p)),
}
}
}
impl From<Step> for Node {
fn from(s: Step) -> Self {
use Node as N;
use Step::*;
let (o, n) = (Member::new, NodeId::new);
match s {
Ax(a, b) => N::Ax(o(a), o(b)),
Tensor(x, l, r) => N::Tensor(o(x), n(l), n(r)),
Par(x, p) => N::Par(o(x), n(p)),
One(x) => N::One(o(x)),
Bot(x, p) => N::Bot(o(x), n(p)),
With(x, l, r) => N::With(o(x), n(l), n(r)),
PlusLeft(x, p) => N::Plus(o(x), Branch::Left, n(p)),
PlusRight(x, p) => N::Plus(o(x), Branch::Right, n(p)),
Top(x) => N::Top(o(x)),
Bang(x, p) => N::Bang(o(x), n(p)),
Quest(x, p) => N::Quest(o(x), n(p)),
Copy(x, p) => N::Copy(o(x), n(p)),
Weaken(x, p) => N::Weaken(o(x), n(p)),
Mix(l, r) => N::Mix(n(l), n(r)),
Cut(a, l, r) => N::Cut(o(a), n(l), n(r)),
Forall(x, a, p) => N::Forall(o(x), crate::linear::Eigen::new(a), n(p)),
Exists(x, w, p) => N::Exists(o(x), crate::linear::sequents::FoTermId::new(w), n(p)),
}
}
}
impl Proof {
pub(super) fn keys(p: &Prf) -> Proof {
Proof {
version: None,
sequent: Sequent::from(p.sequent()),
nodes: p.nodes().iter().copied().map(Step::from).collect(),
mode: None,
goal: p.goal().map(|goal| goal.iter().map(|m| m.get()).collect()),
instances: p.instances().map(|table| Instances::of(table, p.forest())),
}
}
pub(super) const fn of_keys(
sequent: Sequent,
nodes: Vec<Step>,
mode: Mode,
goal: Option<Vec<u32>>,
instances: Option<Instances>,
) -> Proof {
Proof {
version: None,
sequent,
nodes,
mode: Some(mode),
goal,
instances,
}
}
fn document(p: &Prf) -> Proof {
Proof {
version: Some(wire::level_in(p.mode()).max(wire::level_of_sequent(p.sequent()))),
mode: p.mode(),
..Proof::keys(p)
}
}
pub(super) fn within(self, limits: &Limits) -> Result<Prf, crate::Error> {
let sequent = crate::linear::Sequent::try_from(self.sequent)?;
let forest = Forest::from_owned(sequent, limits)?;
let nodes: Vec<Node> = self.nodes.into_iter().map(Node::from).collect();
let Ok(root) = u32::try_from(nodes.len().saturating_sub(1)) else {
return Err(crate::Error::Refused(crate::limits::Refusal::Index {
what: crate::limits::Space::Node,
count: nodes.len() as u64,
most: u64::from(u32::MAX),
}));
};
let root = NodeId::new(root);
let proof = match (self.goal, self.instances) {
(None, Some(instances)) => {
let table = instances.within(&forest, limits)?;
Prf::with_instances(forest, table, nodes, root)?
}
(Some(_), Some(_)) => {
return Err(crate::Error::Json {
form: "proof",
message: "a proof of a goal off the roots has no instance table".to_owned(),
});
}
(None, None) => Prf::new(forest, nodes, root)?,
(Some(goal), None) => {
let goal: Vec<Member> = goal.into_iter().map(Member::new).collect();
Prf::new_of_goal(forest, &goal, nodes, root)?
}
};
Ok(match self.mode {
Some(mode) => proof.with_mode(mode),
None => proof,
})
}
}
impl serde::Serialize for Prf {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
Proof::document(self).serialize(serializer)
}
}
impl<'a> serde::Deserialize<'a> for Prf {
fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
Self::read(deserializer, &Limits::default())
}
}
impl crate::sealed::Readable for Prf {}
impl Readable for Prf {
const FORM: &'static str = "proof";
fn read<'de, D: Deserializer<'de>>(deserializer: D, limits: &Limits) -> Result<Self, D::Error> {
Proof::deserialize(deserializer)?
.within(limits)
.map_err(wire::fail)
}
}
#[derive(Serialize)]
struct StepForm {
cut: u32,
formula: u32,
case: crate::linear::proofs::cut::Case,
#[serde(skip_serializing_if = "Option::is_none")]
above: Option<u32>,
}
#[derive(Serialize)]
struct EliminationForm<'a> {
version: u32,
proof: Proof,
steps: Vec<StepForm>,
end: &'static str,
#[serde(skip_serializing_if = "Option::is_none")]
reason: Option<&'a crate::Error>,
}
impl serde::Serialize for crate::linear::proofs::cut::Elimination {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
use crate::linear::proofs::cut::End;
let reason = match &self.end {
End::CutFree => None,
End::Refused(refusal) => Some(crate::Error::Refused(refusal.clone())),
};
let document = Proof::document(&self.proof);
EliminationForm {
version: document.version.unwrap_or(wire::BASE),
proof: Proof {
version: None,
..document
},
steps: self
.steps
.iter()
.map(|step| StepForm {
cut: step.cut.get(),
formula: step.formula.get(),
case: step.case,
above: step.above.map(NodeId::get),
})
.collect(),
end: if reason.is_some() {
"refused"
} else {
"cut_free"
},
reason: reason.as_ref(),
}
.serialize(serializer)
}
}
impl serde::Serialize for Named {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
serializer.serialize_str(self.name())
}
}
impl<'a> serde::Deserialize<'a> for Named {
fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
let name = <std::borrow::Cow<'a, str>>::deserialize(deserializer)?;
name.parse().map_err(serde::de::Error::custom)
}
}