use super::{Formulas, Logic, Node, NodeId, Sequent, Side, Translation};
use crate::hash::HashMap;
use crate::linear::sequents::{Atom, Term, TermId};
use crate::{Error, linear::Mode};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Core {
Atom,
Unit(Term),
Tensor,
Par,
With,
Plus,
Lollipop,
Pass,
}
pub(super) type Operand = (NodeId, u8, u8);
#[derive(Clone, Copy, Debug)]
pub(super) struct Pattern {
pub(super) bangs: u8,
pub(super) core: Core,
pub(super) operands: [Option<Operand>; 2],
}
pub const FALSE: &str = "false";
const RIGHT: u8 = 0;
const LEFT: u8 = 1;
const T0: u8 = 0;
const T1: u8 = 1;
#[derive(Clone, Debug)]
pub(super) struct Extra {
pub(super) iff: HashMap<NodeId, (NodeId, NodeId)>,
pub(super) falsity: NodeId,
}
impl Extra {
pub(super) fn add(formulas: &mut Formulas) -> Result<Self, Error> {
let mut iff = HashMap::default();
for n in 0..formulas.len() {
let id = NodeId(n as u32);
if let Node::Iff(a, b) = formulas.node(id) {
let pair = (
formulas.add(Node::Implies(a, b))?,
formulas.add(Node::Implies(b, a))?,
);
iff.insert(id, pair);
}
}
let falsity = formulas.add(Node::False)?;
Ok(Self { iff, falsity })
}
}
pub(super) fn pattern(
formulas: &Formulas,
extra: &Extra,
translation: Translation,
logic: Logic,
id: NodeId,
function: u8,
) -> Pattern {
use Core::*;
let node = formulas.node(id);
let make = |bangs, core, a: Option<Operand>, b: Option<Operand>| Pattern {
bangs,
core,
operands: [a, b],
};
let falsity = extra.falsity;
let (forward, backward) = match node {
Node::Iff(..) => extra.iff[&id],
Node::Atom(_)
| Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..) => (id, id),
};
let minimal_false = logic == Logic::Minimal && node == Node::False;
match translation {
Translation::Affine => {
let (f, flip) = (function, 1 - function);
let right = function == RIGHT;
match node {
Node::Atom(_) => make(0, Atom, None, None),
Node::True => make(
0,
Unit(if right { Term::Top } else { Term::Bot }),
None,
None,
),
Node::False => make(
0,
Unit(if right { Term::Bot } else { Term::Top }),
None,
None,
),
Node::Not(a) => make(0, Pass, Some((a, flip, 0)), None),
Node::And(a, b) => make(
0,
if right { With } else { Par },
Some((a, f, 0)),
Some((b, f, 0)),
),
Node::Or(a, b) => make(
0,
if right { Par } else { With },
Some((a, f, 0)),
Some((b, f, 0)),
),
Node::Implies(a, b) => make(
0,
if right { Par } else { With },
Some((a, flip, 0)),
Some((b, f, 0)),
),
Node::Iff(..) => make(
0,
if right { With } else { Par },
Some((forward, f, 0)),
Some((backward, f, 0)),
),
}
}
_ if minimal_false => make(
u8::from(translation == Translation::CallByValue),
Atom,
None,
None,
),
Translation::CallByName => match node {
Node::Atom(_) => make(0, Atom, None, None),
Node::True => make(0, Unit(Term::Top), None, None),
Node::False => make(0, Unit(Term::Zero), None, None),
Node::Not(a) => make(0, Lollipop, Some((a, 0, 1)), Some((falsity, 0, 0))),
Node::And(a, b) => make(0, With, Some((a, 0, 0)), Some((b, 0, 0))),
Node::Or(a, b) => make(0, Plus, Some((a, 0, 1)), Some((b, 0, 1))),
Node::Implies(a, b) => make(0, Lollipop, Some((a, 0, 1)), Some((b, 0, 0))),
Node::Iff(..) => make(0, With, Some((forward, 0, 0)), Some((backward, 0, 0))),
},
Translation::CallByValue => match node {
Node::Atom(_) => make(1, Atom, None, None),
Node::True => make(0, Unit(Term::One), None, None),
Node::False => make(0, Unit(Term::Zero), None, None),
Node::Not(a) => make(1, Lollipop, Some((a, 0, 0)), Some((falsity, 0, 0))),
Node::And(a, b) => make(0, Tensor, Some((a, 0, 0)), Some((b, 0, 0))),
Node::Or(a, b) => make(0, Plus, Some((a, 0, 0)), Some((b, 0, 0))),
Node::Implies(a, b) => make(1, Lollipop, Some((a, 0, 0)), Some((b, 0, 0))),
Node::Iff(..) => make(0, Tensor, Some((forward, 0, 0)), Some((backward, 0, 0))),
},
Translation::ZeroOne if function == T0 => match node {
Node::Atom(_) => make(0, Atom, None, None),
Node::True => make(0, Unit(Term::Top), None, None),
Node::False => make(0, Unit(Term::Zero), None, None),
Node::Not(a) => make(0, Lollipop, Some((a, T1, 1)), Some((falsity, T0, 1))),
Node::And(a, b) => make(0, With, Some((a, T0, 1)), Some((b, T0, 1))),
Node::Or(a, b) => make(0, Plus, Some((a, T0, 1)), Some((b, T0, 1))),
Node::Implies(a, b) => make(0, Lollipop, Some((a, T1, 1)), Some((b, T0, 1))),
Node::Iff(..) => make(0, With, Some((forward, T0, 1)), Some((backward, T0, 1))),
},
Translation::ZeroOne => match node {
Node::Atom(_) => make(0, Atom, None, None),
Node::True => make(0, Unit(Term::One), None, None),
Node::False => make(0, Unit(Term::Zero), None, None),
Node::Not(a) => make(1, Lollipop, Some((a, T0, 1)), Some((falsity, T1, 0))),
Node::And(a, b) => make(1, With, Some((a, T1, 0)), Some((b, T1, 0))),
Node::Or(a, b) => make(0, Plus, Some((a, T1, 1)), Some((b, T1, 1))),
Node::Implies(a, b) => make(1, Lollipop, Some((a, T0, 1)), Some((b, T1, 0))),
Node::Iff(..) => make(1, With, Some((forward, T1, 0)), Some((backward, T1, 0))),
},
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Root {
pub(super) node: NodeId,
pub(super) function: u8,
pub(super) bangs: u8,
pub(super) side: Side,
}
#[derive(Clone, Debug)]
pub struct Image {
pub(super) sequent: crate::linear::Sequent,
pub(super) mode: Mode,
pub(super) logic: Logic,
pub(super) translation: Translation,
pub(super) ordinary: Sequent,
pub(super) extra: Extra,
pub(super) roots: Vec<Root>,
}
impl Image {
pub fn sequent(&self) -> &crate::linear::Sequent {
&self.sequent
}
pub fn mode(&self) -> Mode {
self.mode
}
pub fn logic(&self) -> Logic {
self.logic
}
pub fn translation(&self) -> Translation {
self.translation
}
pub fn ordinary(&self) -> &Sequent {
&self.ordinary
}
}
#[expect(
clippy::missing_panics_doc,
reason = "the expects state facts of the pattern table the translation builds from"
)]
pub fn translate(
sequent: &Sequent,
logic: Logic,
translation: Translation,
limits: &crate::Limits,
) -> Result<Image, Error> {
if !translation.decides(logic) {
return Err(Error::Translation { translation, logic });
}
let mut ordinary = sequent.clone();
let classical = logic == Logic::Classical;
if !classical && ordinary.right.len() > 1 {
return Err(Error::Succedents {
count: ordinary.right.len(),
});
}
let extra = Extra::add(&mut ordinary.formulas)?;
if !classical && ordinary.right.is_empty() {
ordinary.right.push(extra.falsity);
}
let formulas = &ordinary.formulas;
let functions: u8 = match translation {
Translation::Affine | Translation::ZeroOne => 2,
Translation::CallByName | Translation::CallByValue => 1,
};
let mut builder = Builder::default();
let mut images: Vec<Option<(TermId, TermId)>> = vec![None; formulas.len() * functions as usize];
let slot = |id: NodeId, function: u8| id.index() * functions as usize + function as usize;
let mut order = Vec::with_capacity(formulas.len() + 1);
order.push(extra.falsity);
for n in 0..formulas.len() {
let id = NodeId(n as u32);
if let Some(&(forward, backward)) = extra.iff.get(&id) {
order.extend([forward, backward]);
}
order.push(id);
}
for id in order {
for function in 0..functions {
if images[slot(id, function)].is_some() {
continue;
}
let pattern = pattern(formulas, &extra, translation, logic, id, function);
let operand =
|(k, f, bangs): Operand, b: &mut Builder| -> Result<(TermId, TermId), Error> {
let (mut positive, mut negative) =
images[slot(k, f)].expect("an operand precedes its formula");
for _ in 0..bangs {
positive = b.add(Term::Bang(positive))?;
negative = b.add(Term::Quest(negative))?;
}
Ok((positive, negative))
};
let a = pattern.operands[0]
.map(|o| operand(o, &mut builder))
.transpose()?;
let b = pattern.operands[1]
.map(|o| operand(o, &mut builder))
.transpose()?;
let mut image = match pattern.core {
Core::Atom => {
let name = match formulas.node(id) {
Node::Atom(a) => formulas.atom_name(a),
Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Or(..)
| Node::Implies(..)
| Node::Iff(..) => FALSE,
};
let atom = builder.atom(name);
let (var, dual) = (
builder.add(Term::Atom(atom))?,
builder.add(Term::DualAtom(atom))?,
);
if classical && function == LEFT {
(dual, var)
} else {
(var, dual)
}
}
Core::Unit(unit) => (builder.add(unit)?, builder.add(unit.dual())?),
Core::Pass => a.expect("a negation has an operand"),
core @ Core::Tensor
| core @ Core::Par
| core @ Core::With
| core @ Core::Plus
| core @ Core::Lollipop => {
let ((pa, na), (pb, nb)) = (a.expect("binary"), b.expect("binary"));
let (positive, negative) = match core {
Core::Tensor => (Term::Tensor(pa, pb), Term::Par(na, nb)),
Core::Par => (Term::Par(pa, pb), Term::Tensor(na, nb)),
Core::With => (Term::With(pa, pb), Term::Plus(na, nb)),
Core::Plus => (Term::Plus(pa, pb), Term::With(na, nb)),
Core::Atom | Core::Unit(_) | Core::Lollipop | Core::Pass => {
(Term::Par(na, pb), Term::Tensor(pa, nb))
}
};
(builder.add(positive)?, builder.add(negative)?)
}
};
for _ in 0..pattern.bangs {
image = (
builder.add(Term::Bang(image.0))?,
builder.add(Term::Quest(image.1))?,
);
}
images[slot(id, function)] = Some(image);
}
}
let mut roots = Vec::with_capacity(ordinary.left.len() + ordinary.right.len());
let mut terms = Vec::with_capacity(roots.capacity());
for (side, list) in [(Side::Left, &ordinary.left), (Side::Right, &ordinary.right)] {
for &node in list {
let (function, extra_bang) = match (translation, side) {
(Translation::Affine, Side::Left) => (LEFT, 0),
(Translation::Affine, Side::Right) => (RIGHT, 0),
(Translation::CallByName, Side::Left) => (0, 1),
(Translation::ZeroOne, Side::Left) => (T0, 1),
(Translation::ZeroOne, Side::Right) => (T1, 0),
_ => (0, 0),
};
let pattern = pattern(formulas, &extra, translation, logic, node, function);
let (mut positive, mut negative) =
images[slot(node, function)].expect("every image is made");
for _ in 0..extra_bang {
positive = builder.add(Term::Bang(positive))?;
negative = builder.add(Term::Quest(negative))?;
}
let dual = side == Side::Left && !classical;
terms.push(if dual { negative } else { positive });
roots.push(Root {
node,
function,
bangs: pattern.bangs + extra_bang,
side,
});
}
}
let antecedents = if classical {
0
} else {
ordinary.left.len() as u32
};
let mut linear = crate::linear::Sequent {
terms: builder.terms,
roots: terms,
atoms: builder.atoms,
antecedents: Some(antecedents),
cuts: vec![],
fo: crate::linear::sequents::fo::FirstOrder::new(),
};
linear.optimize();
let mode = if classical {
Mode::CLASSICAL.with_affine()
} else {
Mode::INTUITIONISTIC
};
let occurrences = linear.occurrences();
if let Some(limit) = limits.occurrences
&& occurrences > limit
{
return Err(Error::Refused(crate::Refusal::Occurrences {
occurrences,
limit,
}));
}
Ok(Image {
sequent: linear,
mode,
logic,
translation,
ordinary,
extra,
roots,
})
}
#[derive(Default)]
struct Builder {
terms: Vec<Term>,
ids: HashMap<Term, TermId>,
atoms: Vec<String>,
names: HashMap<String, Atom>,
}
impl Builder {
fn add(&mut self, term: Term) -> Result<TermId, Error> {
if let Some(&id) = self.ids.get(&term) {
return Ok(id);
}
let most = crate::linear::Forest::MOST;
if self.terms.len() as u64 >= most {
return Err(Error::Refused(crate::limits::Refusal::Occurrences {
occurrences: most.saturating_add(1),
limit: most,
}));
}
let id = TermId::new(self.terms.len() as u32);
self.terms.push(term);
self.ids.insert(term, id);
Ok(id)
}
fn atom(&mut self, name: &str) -> Atom {
if let Some(&atom) = self.names.get(name) {
return atom;
}
let atom = Atom::new(self.atoms.len() as u32);
self.atoms.push(name.to_owned());
self.names.insert(name.to_owned(), atom);
atom
}
}