use super::sequents::{Atoms, FoExpression, Tables};
use crate::hash::HashMap;
use crate::limits::{Limits, Refusal};
use crate::linear::occurrences::{IllConnective, IllSequent, Side};
use crate::linear::sequents::{Atom, Sequent, Term, TermId, Visit};
use crate::wire::{self, Readable};
use serde::{Deserialize, Deserializer, Serialize, Serializer};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename = "I")]
enum Expression {
#[serde(rename = "V")]
Atom(u32),
#[serde(rename = "1")]
One,
#[serde(rename = "0")]
Zero,
#[serde(rename = "⊤")]
Top,
#[serde(rename = "⊗")]
Tensor(u32, u32),
#[serde(rename = "⊸")]
Lollipop(u32, u32),
#[serde(rename = "&")]
With(u32, u32),
#[serde(rename = "⊕")]
Plus(u32, u32),
#[serde(rename = "!")]
Bang(u32),
#[serde(rename = "∀")]
Forall(u32),
#[serde(rename = "∃")]
Exists(u32),
}
impl Expression {
fn shape(self) -> Term {
let t = TermId::new;
match self {
Expression::Atom(a) => Term::Atom(Atom::new(a)),
Expression::One => Term::One,
Expression::Zero => Term::Zero,
Expression::Top => Term::Top,
Expression::Tensor(k, l) | Expression::Lollipop(k, l) => Term::Tensor(t(k), t(l)),
Expression::With(k, l) | Expression::Plus(k, l) => Term::With(t(k), t(l)),
Expression::Bang(k) => Term::Bang(t(k)),
Expression::Forall(k) => Term::Forall(t(k)),
Expression::Exists(k) => Term::Exists(t(k)),
}
}
fn is_binder(self) -> bool {
matches!(self, Expression::Forall(_) | Expression::Exists(_))
}
fn operands(self, side: Side) -> [Option<(u32, Side)>; 2] {
match self {
Expression::Atom(_) | Expression::One | Expression::Zero | Expression::Top => {
[None, None]
}
Expression::Bang(k) | Expression::Forall(k) | Expression::Exists(k) => {
[Some((k, side)), None]
}
Expression::Lollipop(k, l) => [Some((k, !side)), Some((l, side))],
Expression::Tensor(k, l) | Expression::With(k, l) | Expression::Plus(k, l) => {
[Some((k, side)), Some((l, side))]
}
}
}
fn lowered(self, side: Side, left: TermId, right: TermId) -> Term {
let output = side == Side::Output;
match self {
Expression::Atom(a) if output => Term::Atom(Atom::new(a)),
Expression::Atom(a) => Term::DualAtom(Atom::new(a)),
Expression::One if output => Term::One,
Expression::One => Term::Bot,
Expression::Zero if output => Term::Zero,
Expression::Zero => Term::Top,
Expression::Top if output => Term::Top,
Expression::Top => Term::Zero,
Expression::Tensor(..) if output => Term::Tensor(left, right),
Expression::Tensor(..) => Term::Par(left, right),
Expression::Lollipop(..) if output => Term::Par(left, right),
Expression::Lollipop(..) => Term::Tensor(left, right),
Expression::With(..) if output => Term::With(left, right),
Expression::With(..) => Term::Plus(left, right),
Expression::Plus(..) if output => Term::Plus(left, right),
Expression::Plus(..) => Term::With(left, right),
Expression::Bang(_) if output => Term::Bang(left),
Expression::Bang(_) => Term::Quest(left),
Expression::Forall(..) if output => Term::Forall(left),
Expression::Forall(..) => Term::Exists(left),
Expression::Exists(..) if output => Term::Exists(left),
Expression::Exists(..) => Term::Forall(left),
}
}
}
#[derive(Clone, Debug, Serialize, Deserialize)]
struct Ill {
#[serde(
default,
skip_serializing_if = "Option::is_none",
deserialize_with = "wire::version"
)]
version: Option<u32>,
terms: Vec<Expression>,
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>,
hypotheses: Vec<u32>,
goal: u32,
}
impl From<&IllSequent> for Ill {
fn from(sequent: &IllSequent) -> Self {
let reading = sequent.reading();
let forest = sequent.forest();
let mut terms = Vec::new();
let mut binders = Vec::new();
let mut index = HashMap::<(TermId, Side), u32>::default();
let mut written = HashMap::<Expression, u32>::default();
for &root in forest.roots() {
for visit in reading.walk(root) {
let o = match visit {
Visit::Exit(o) => o,
Visit::Enter(o) if forest.left(o).is_none() => o,
Visit::Enter(_) | Visit::Between(..) => continue,
};
let key = (forest.term(o), reading.position(o));
if index.contains_key(&key) {
continue;
}
let at = |k: Option<_>| {
let k = k.expect("a connective has its operands");
index[&(forest.term(k), reading.position(k))]
};
let (l, r) = reading.operands(o);
use IllConnective as C;
let expression = match reading.connective(o) {
C::Atom => Expression::Atom(forest.atom(o).expect("an atom").get()),
C::One => Expression::One,
C::Zero => Expression::Zero,
C::Top => Expression::Top,
C::Bang => Expression::Bang(at(l)),
C::Tensor => Expression::Tensor(at(l), at(r)),
C::With => Expression::With(at(l), at(r)),
C::Plus => Expression::Plus(at(l), at(r)),
C::Lollipop | C::Under | C::Over => Expression::Lollipop(at(l), at(r)),
C::Forall => Expression::Forall(at(l)),
C::Exists => Expression::Exists(at(l)),
};
let n = *written.entry(expression).or_insert_with(|| {
if expression.is_binder() {
let name = forest.sequent().binder_name(forest.term(o));
binders.push(name.unwrap_or("x").to_owned());
}
terms.push(expression);
terms.len() as u32 - 1
});
index.insert(key, n);
}
}
let at = |o| index[&(forest.term(o), reading.position(o))];
let tables = Tables::of(forest.sequent());
Self {
version: None,
terms,
atoms: tables.atoms,
symbols: tables.symbols,
fo: tables.fo,
binders,
hypotheses: reading.hypotheses().map(at).collect(),
goal: at(reading.goal()),
}
}
}
impl Ill {
fn within(self, limits: &Limits) -> Result<IllSequent, crate::Error> {
let (mut fo, atoms) = Tables {
symbols: self.symbols,
fo: self.fo,
atoms: self.atoms,
}
.read(limits)?;
let len = self.terms.len();
let most = u64::from(u32::MAX / 2);
if len as u64 > most {
return Err(crate::Error::Refused(Refusal::Index {
what: crate::limits::Space::Term,
count: len as u64,
most,
}));
}
for (n, e) in self.terms.iter().enumerate() {
e.shape().check_bounds(atoms.len() as u32, n as u32)?;
}
let roots = self.hypotheses.iter().chain([&self.goal]);
if let Some(&n) = roots.clone().find(|&&n| n as usize >= len) {
return Err(crate::Error::IndexOutOfBounds {
space: crate::limits::Space::Term,
index: n as usize,
len,
});
}
let bit = |side: Side| if side == Side::Input { 1u8 } else { 2 };
let mut needed = vec![0u8; len];
for &h in &self.hypotheses {
needed[h as usize] |= bit(Side::Input);
}
needed[self.goal as usize] |= bit(Side::Output);
for n in (0..len).rev() {
for side in [Side::Input, Side::Output] {
if needed[n] & bit(side) != 0 {
for (k, s) in self.terms[n].operands(side).into_iter().flatten() {
needed[k as usize] |= bit(s);
}
}
}
}
let mut lowered = vec![[TermId::new(0); 2]; len];
let mut terms = Vec::new();
let mut names = vec![None; len];
let mut given = self.binders.into_iter();
for (n, e) in self.terms.iter().enumerate() {
if e.is_binder() {
names[n] = Some(given.next().unwrap_or_else(|| "x".to_owned()));
}
}
for n in 0..len {
for side in [Side::Input, Side::Output] {
if needed[n] & bit(side) == 0 {
continue;
}
let [l, r] = self.terms[n]
.operands(side)
.map(|k| k.map_or(TermId::new(0), |(k, s)| lowered[k as usize][s as usize]));
lowered[n][side as usize] = TermId::new(terms.len() as u32);
if let Some(name) = &names[n] {
fo.binders
.push((TermId::new(terms.len() as u32), name.clone()));
}
terms.push(self.terms[n].lowered(side, l, r));
}
}
let mut roots: Vec<TermId> = self
.hypotheses
.iter()
.map(|&h| lowered[h as usize][Side::Input as usize])
.collect();
roots.push(lowered[self.goal as usize][Side::Output as usize]);
let mut sequent = Sequent {
terms,
roots,
atoms,
antecedents: Some(self.hypotheses.len() as u32),
cuts: vec![],
fo,
};
sequent.check()?;
sequent.merge_atoms();
let occurrences = sequent.occurrences();
match limits.occurrences {
Some(limit) if occurrences > limit => {
return Err(crate::Error::Refused(Refusal::Occurrences {
occurrences,
limit,
}));
}
_ => {}
}
IllSequent::lowered(sequent, limits)
}
}
impl Serialize for IllSequent {
fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
let mut proxy = Ill::from(self);
proxy.version = Some(wire::ILL.max(wire::level_of_sequent(self.sequent())));
proxy.serialize(serializer)
}
}
impl<'a> Deserialize<'a> for IllSequent {
fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error> {
Self::read(deserializer, &Limits::default())
}
}
impl crate::sealed::Readable for IllSequent {}
impl Readable for IllSequent {
const FORM: &'static str = "intuitionistic sequent";
fn read<'de, D: Deserializer<'de>>(deserializer: D, limits: &Limits) -> Result<Self, D::Error> {
let proxy = Ill::deserialize(deserializer)?;
proxy.within(limits).map_err(wire::fail)
}
}