use crate::limits::{Limits, Refusal};
use crate::linear::sequents::fo::{Args, FirstOrder, FoTerm, FoTermId, Symbol};
use crate::linear::sequents::{Sequent as Seq, Term, TermId, name};
use crate::wire::{self, Readable};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use std::borrow::Cow;
#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename = "T")]
pub(super) enum FoExpression {
#[serde(rename = "B")]
Bound(u32),
#[serde(rename = "F")]
App(u32, Vec<u32>),
#[serde(rename = "E")]
Eigen(u32),
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize)]
#[serde(untagged)]
pub(super) enum AtomForm {
Name(String),
Predicate(Box<Predicate>),
}
impl<'de> Deserialize<'de> for AtomForm {
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
struct Visitor;
impl<'de> serde::de::Visitor<'de> for Visitor {
type Value = AtomForm;
fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("an atom's name, or a predicate applied to its arguments")
}
fn visit_str<E: serde::de::Error>(self, name: &str) -> Result<AtomForm, E> {
Ok(AtomForm::Name(name.to_owned()))
}
fn visit_string<E: serde::de::Error>(self, name: String) -> Result<AtomForm, E> {
Ok(AtomForm::Name(name))
}
fn visit_map<A: serde::de::MapAccess<'de>>(self, map: A) -> Result<AtomForm, A::Error> {
Predicate::deserialize(serde::de::value::MapAccessDeserializer::new(map))
.map(|predicate| AtomForm::Predicate(Box::new(predicate)))
}
}
deserializer.deserialize_any(Visitor)
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename = "A")]
pub(super) enum Predicate {
#[serde(rename = "P")]
P(u32, Vec<u32>),
}
#[derive(Clone, Debug)]
pub(super) enum Atoms {
Names(Vec<String>),
Mixed(Vec<AtomForm>),
}
impl Serialize for Atoms {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
match self {
Atoms::Names(names) => names.serialize(serializer),
Atoms::Mixed(atoms) => atoms.serialize(serializer),
}
}
}
impl<'de> Deserialize<'de> for Atoms {
fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
struct Visitor;
impl<'de> serde::de::Visitor<'de> for Visitor {
type Value = Atoms;
fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("the atoms, by name or as predicates")
}
fn visit_seq<A: serde::de::SeqAccess<'de>>(
self,
mut seq: A,
) -> Result<Atoms, A::Error> {
let mut atoms = Atoms::Names(Vec::new());
while seq.next_element_seed(Push(&mut atoms))?.is_some() {}
Ok(atoms)
}
}
struct Push<'a>(&'a mut Atoms);
impl<'de> serde::de::DeserializeSeed<'de> for Push<'_> {
type Value = ();
fn deserialize<D: Deserializer<'de>>(self, deserializer: D) -> Result<(), D::Error> {
deserializer.deserialize_any(self)
}
}
impl<'de> serde::de::Visitor<'de> for Push<'_> {
type Value = ();
fn expecting(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str("an atom's name, or a predicate applied to its arguments")
}
fn visit_str<E: serde::de::Error>(self, name: &str) -> Result<(), E> {
match self.0 {
Atoms::Names(names) => names.push(name.to_owned()),
Atoms::Mixed(atoms) => atoms.push(AtomForm::Name(name.to_owned())),
}
Ok(())
}
fn visit_string<E: serde::de::Error>(self, name: String) -> Result<(), E> {
match self.0 {
Atoms::Names(names) => names.push(name),
Atoms::Mixed(atoms) => atoms.push(AtomForm::Name(name)),
}
Ok(())
}
fn visit_map<A: serde::de::MapAccess<'de>>(self, map: A) -> Result<(), A::Error> {
let predicate =
Predicate::deserialize(serde::de::value::MapAccessDeserializer::new(map))?;
if let Atoms::Names(names) = self.0 {
let mixed = std::mem::take(names)
.into_iter()
.map(AtomForm::Name)
.collect();
*self.0 = Atoms::Mixed(mixed);
}
let Atoms::Mixed(atoms) = self.0 else {
unreachable!("mixed from the first predicate on");
};
atoms.push(AtomForm::Predicate(Box::new(predicate)));
Ok(())
}
}
deserializer.deserialize_seq(Visitor)
}
}
pub(super) struct Tables {
pub(super) symbols: Vec<(String, u32)>,
pub(super) fo: Vec<FoExpression>,
pub(super) atoms: Atoms,
}
impl Tables {
pub(super) fn of(sequent: &Seq) -> Self {
let fo = &sequent.fo;
if fo.atoms.is_empty() {
return Self {
symbols: vec![],
fo: vec![],
atoms: Atoms::Names(sequent.atoms.clone()),
};
}
let list = |args: Args| fo.list(args).iter().map(|t| t.get()).collect();
Self {
symbols: fo.symbols.clone(),
fo: fo
.terms
.iter()
.map(|term| match *term {
FoTerm::Bound(i) => FoExpression::Bound(i),
FoTerm::App(f, args) => FoExpression::App(f.get(), list(args)),
FoTerm::Eigen(a) => FoExpression::Eigen(a.get()),
FoTerm::Meta(_) => unreachable!("a sequent's arena holds no metavariable"),
})
.collect(),
atoms: Atoms::Mixed(
fo.atoms
.iter()
.map(|&(p, args)| {
AtomForm::Predicate(Box::new(Predicate::P(p.get(), list(args))))
})
.collect(),
),
}
}
pub(super) fn read(self, limits: &Limits) -> Result<(FirstOrder, Vec<String>), crate::Error> {
let mut tables = FirstOrder::new();
let first_order = !self.symbols.is_empty() || !self.fo.is_empty();
let atoms = match self.atoms {
Atoms::Names(mut names) if !first_order => {
for name in &mut names {
if let Cow::Owned(composed) = name::normalized(name) {
*name = composed;
}
name::check(name)?;
}
return Ok((tables, names));
}
Atoms::Names(names) => names.into_iter().map(AtomForm::Name).collect(),
Atoms::Mixed(atoms) => atoms,
};
let mut names = Vec::with_capacity(atoms.len());
tables.symbols = self
.symbols
.into_iter()
.map(|(name, arity)| Ok((normalized(name)?, arity)))
.collect::<Result<_, crate::Error>>()?;
let mut known = crate::hash::HashMap::<Vec<u32>, Args>::default();
let mut list = |tables: &mut FirstOrder, items: Vec<u32>| {
if let Some(&args) = known.get(&items) {
return args;
}
let args = Args::new(tables.lists.len() as u32);
let start = tables.args.len() as u32;
tables.args.extend(items.iter().map(|&t| FoTermId::new(t)));
tables.lists.push((start, items.len() as u32));
known.insert(items, args);
args
};
for term in self.fo {
let term = match term {
FoExpression::Bound(i) => FoTerm::Bound(i),
FoExpression::App(f, items) => {
let args = list(&mut tables, items);
FoTerm::App(Symbol::new(f), args)
}
FoExpression::Eigen(_) => {
return Err(crate::Error::Json {
form: "sequent",
message: "an eigenvariable stands only in a proof's terms".to_owned(),
});
}
};
tables.terms.push(term);
}
for atom in atoms {
let (symbol, args) = match atom {
AtomForm::Predicate(predicate) => {
let Predicate::P(p, items) = *predicate;
(Symbol::new(p), list(&mut tables, items))
}
AtomForm::Name(name) => {
let name = normalized(name)?;
let symbol = match tables.symbols.iter().position(|(n, _)| *n == name) {
Some(i) => Symbol::new(i as u32),
None => {
tables.symbols.push((name, 0));
Symbol::new(tables.symbols.len() as u32 - 1)
}
};
(symbol, list(&mut tables, vec![]))
}
};
tables.atoms.push((symbol, args));
}
tables.check(tables.atoms.len())?;
let unfolded = tables.unfolded();
let terms = tables.atoms.iter().fold(0u64, |sum, &(_, args)| {
tables
.list(args)
.iter()
.fold(sum, |sum, t| sum.saturating_add(unfolded[t.index()]))
});
if let Some(limit) = limits.terms
&& terms > limit
{
return Err(crate::Error::Refused(Refusal::Terms { terms, limit }));
}
for &(p, args) in &tables.atoms {
names.push(tables.atom_key(p, args));
}
Ok((tables, names))
}
}
fn normalized(name: String) -> Result<String, crate::Error> {
let name = match name::normalized(&name) {
Cow::Owned(composed) => composed,
Cow::Borrowed(_) => name,
};
name::check(&name)?;
Ok(name)
}
#[derive(Clone, Copy, Debug, Serialize, Deserialize)]
#[serde(rename = "E")]
enum Expression {
#[serde(rename = "V")]
Atom(u32),
#[serde(rename = "D")]
DualAtom(u32),
#[serde(rename = "1")]
One,
#[serde(rename = "⊥")]
Bot,
#[serde(rename = "⊤")]
Top,
#[serde(rename = "0")]
Zero,
#[serde(rename = "⊗")]
Tensor(u32, u32),
#[serde(rename = "⅋")]
Par(u32, u32),
#[serde(rename = "&")]
With(u32, u32),
#[serde(rename = "⊕")]
Plus(u32, u32),
#[serde(rename = "!")]
Bang(u32),
#[serde(rename = "?")]
Quest(u32),
#[serde(rename = "∀")]
Forall(u32),
#[serde(rename = "∃")]
Exists(u32),
}
#[derive(Clone, Debug, Serialize, Deserialize)]
pub(super) struct Sequent {
#[serde(
default,
skip_serializing_if = "Option::is_none",
deserialize_with = "wire::version"
)]
version: Option<u32>,
terms: Vec<Expression>,
roots: Vec<u32>,
atoms: Atoms,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
symbols: Vec<(String, u32)>,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
fo: Vec<FoExpression>,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
binders: Vec<String>,
#[serde(default, skip_serializing_if = "Option::is_none")]
antecedents: Option<u32>,
#[serde(default, skip_serializing_if = "Vec::is_empty")]
cuts: Vec<u32>,
}
impl Expression {
fn of(e: Term) -> Self {
use Expression as E;
use Term::*;
match e {
Atom(a) => E::Atom(a.get()),
DualAtom(a) => E::DualAtom(a.get()),
One => E::One,
Bot => E::Bot,
Top => E::Top,
Zero => E::Zero,
Tensor(k, l) => E::Tensor(k.get(), l.get()),
Par(k, l) => E::Par(k.get(), l.get()),
With(k, l) => E::With(k.get(), l.get()),
Plus(k, l) => E::Plus(k.get(), l.get()),
Bang(k) => E::Bang(k.get()),
Quest(k) => E::Quest(k.get()),
Forall(k) => E::Forall(k.get()),
Exists(k) => E::Exists(k.get()),
}
}
fn into_term(self) -> Term {
use Expression::*;
use Term as E;
let t = TermId::new;
match self {
Atom(a) => E::Atom(crate::linear::sequents::Atom::new(a)),
DualAtom(a) => E::DualAtom(crate::linear::sequents::Atom::new(a)),
One => E::One,
Bot => E::Bot,
Top => E::Top,
Zero => E::Zero,
Tensor(k, l) => E::Tensor(t(k), t(l)),
Par(k, l) => E::Par(t(k), t(l)),
With(k, l) => E::With(t(k), t(l)),
Plus(k, l) => E::Plus(t(k), t(l)),
Bang(k) => E::Bang(t(k)),
Quest(k) => E::Quest(t(k)),
Forall(k) => E::Forall(t(k)),
Exists(k) => E::Exists(t(k)),
}
}
}
impl From<&Seq> for Sequent {
fn from(s: &Seq) -> Sequent {
let tables = Tables::of(s);
Sequent {
version: None,
terms: s.terms.iter().copied().map(Expression::of).collect(),
binders: s.fo.binders.iter().map(|(_, name)| name.clone()).collect(),
roots: s.roots.iter().map(|k| k.get()).collect(),
atoms: tables.atoms,
symbols: tables.symbols,
fo: tables.fo,
antecedents: s.antecedents,
cuts: s.cuts.iter().map(|[a, _]| a.get()).collect(),
}
}
}
impl Sequent {
pub(super) fn within(self, limits: &Limits) -> Result<Seq, crate::Error> {
let sequent = Seq::read_within(self, limits)?;
let occurrences = sequent.occurrences();
match limits.occurrences {
Some(limit) if occurrences > limit => {
Err(crate::Error::Refused(Refusal::Occurrences {
occurrences,
limit,
}))
}
_ => Ok(sequent),
}
}
}
impl TryFrom<Sequent> for Seq {
type Error = crate::Error;
fn try_from(s: Sequent) -> Result<Seq, Self::Error> {
Self::read_within(s, &Limits::default())
}
}
impl Seq {
fn read_within(s: Sequent, limits: &Limits) -> Result<Seq, crate::Error> {
let (mut fo, atoms) = Tables {
symbols: s.symbols,
fo: s.fo,
atoms: s.atoms,
}
.read(limits)?;
let cuts = s.cuts;
let terms: Vec<Term> = s.terms.into_iter().map(Expression::into_term).collect();
if !s.binders.is_empty() {
let mut names = s.binders.into_iter();
for (n, term) in terms.iter().enumerate() {
if term.kind().is_binder() {
let name = names.next().unwrap_or_else(|| "x".to_owned());
fo.binders.push((TermId::new(n as u32), normalized(name)?));
}
}
}
let mut s = Seq {
terms,
roots: s.roots.into_iter().map(TermId::new).collect(),
atoms,
antecedents: s.antecedents,
cuts: vec![],
fo,
};
s.check()?;
let len = s.terms.len();
if let Some(&a) = cuts.iter().find(|&&a| a as usize >= len) {
return Err(crate::Error::IndexOutOfBounds {
space: crate::limits::Space::Term,
index: a as usize,
len,
});
}
let cuts: Vec<TermId> = cuts.into_iter().map(TermId::new).collect();
s.push_cuts(&cuts);
if !cuts.is_empty() && !s.fo.is_empty() {
s.check()?;
}
s.merge_atoms();
Ok(s)
}
}
impl serde::Serialize for Seq {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
let mut proxy = Sequent::from(self);
proxy.version = Some(wire::level_of_sequent(self));
proxy.serialize(serializer)
}
}
impl<'a> serde::Deserialize<'a> for Seq {
fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
Self::read(deserializer, &Limits::default())
}
}
impl crate::sealed::Readable for Seq {}
impl Readable for Seq {
const FORM: &'static str = "sequent";
fn read<'de, D: Deserializer<'de>>(deserializer: D, limits: &Limits) -> Result<Self, D::Error> {
let proxy = Sequent::deserialize(deserializer)?;
proxy.within(limits).map_err(wire::fail)
}
}