use super::FORMULA;
use super::derivation::{Derivation, Node, Step};
use super::terms::TermId;
use crate::Error;
use crate::ordinary::{self, Inference, Logic, Rule, Side};
const fn calculus(logic: Logic) -> &'static str {
match logic {
Logic::Classical => "LK",
Logic::Intuitionistic => "LJ",
Logic::Minimal => "LM",
}
}
pub(super) fn terms_of(
formulas: &ordinary::Formulas,
terms: &mut super::Terms,
) -> Result<Vec<TermId>, Error> {
let mut ids: Vec<TermId> = Vec::with_capacity(formulas.len());
for &node in formulas.nodes() {
use ordinary::Node::*;
let id = match node {
Atom(atom) => terms.atom(formulas.atom_name(atom), FORMULA)?,
True => terms.apply("⊤", &[])?,
False => terms.apply("⊥", &[])?,
Not(a) => terms.apply("¬", &[ids[a.index()]])?,
And(a, b) => terms.apply("∧", &[ids[a.index()], ids[b.index()]])?,
Or(a, b) => terms.apply("∨", &[ids[a.index()], ids[b.index()]])?,
Implies(a, b) => terms.apply("→", &[ids[a.index()], ids[b.index()]])?,
Iff(a, b) => terms.apply("↔", &[ids[a.index()], ids[b.index()]])?,
};
ids.push(id);
}
Ok(ids)
}
fn size(inference: &Inference) -> usize {
inference.left().len() + inference.right().len()
}
fn name(logic: Logic, inference: &Inference, premises: &[&Inference]) -> (String, Option<Side>) {
use Rule::*;
use Side::{Left, Right};
let rule = inference.rule();
let shared = |first: usize, second: usize| match premises {
[p, q] => size(p) + 1 == size(inference) + first && size(q) + 1 == size(inference) + second,
_ => true,
};
let split = |shared: bool| if shared { "" } else { " split" };
let lj = logic != Logic::Classical;
let (name, side) = match rule {
Axiom | Cut | Open => (rule.name().to_owned(), None),
WeakenLeft | ContractLeft | AndLeft | AndLeft1 | AndLeft2 | IffLeft | IffLeft1
| IffLeft2 | FalseLeft | TrueLeft => (rule.name().to_owned(), Some(Left)),
WeakenRight | ContractRight | OrRight | OrRight1 | OrRight2 | ImpliesRight | FalseRight
| TrueRight => (rule.name().to_owned(), Some(Right)),
AndRight | IffRight => (format!("{rule}{}", split(shared(1, 1))), Some(Right)),
OrLeft | ImpliesLeft => (format!("{rule}{}", split(shared(1, 1))), Some(Left)),
NotLeft if lj && premises.len() != 1 => {
(format!("¬L ⊥{}", split(shared(1, 1))), Some(Left))
}
NotLeft => (rule.name().to_owned(), Some(Left)),
NotRight
if lj
&& premises
.first()
.is_some_and(|p| p.right().len() == inference.right().len()) =>
{
("¬R ⊥".to_owned(), Some(Right))
}
NotRight => (rule.name().to_owned(), Some(Right)),
};
if rule == Cut
&& let [p, q] = premises
&& inference.right().is_empty()
&& !inference.left().is_empty()
&& p.left().len() == inference.left().len()
&& q.left().len() == inference.left().len() + 1
{
return ("cut shared".to_owned(), None);
}
(name, side)
}
impl Derivation {
pub fn from_ordinary(derivation: &ordinary::Derivation) -> Result<Self, Error> {
let logic = derivation.logic();
let invalid = |reason: String| Error::InvalidDerivation {
calculus: calculus(logic).into(),
reason,
};
let formulas = derivation.formulas();
let mut out = Self::new(calculus(logic), 2);
let ids = terms_of(formulas, out.terms_mut())?;
let zone = |side: &[ordinary::NodeId]| -> Vec<TermId> {
side.iter().map(|formula| ids[formula.index()]).collect()
};
let sorted = |side: &[ordinary::NodeId]| {
let mut side = side.to_vec();
side.sort_unstable();
side
};
let inferences = derivation.inferences();
let (left, right) = derivation.sequent();
let concluded = inferences.last().is_some_and(|root| {
sorted(root.left()) == sorted(left) && sorted(root.right()) == sorted(right)
});
if !concluded {
return Err(invalid("the root does not conclude the sequent".to_owned()));
}
for (index, inference) in inferences.iter().enumerate() {
if inference.premises().iter().any(|p| p.index() >= index) {
return Err(invalid(format!(
"inference {index}: a premise does not precede it"
)));
}
let premises: Vec<&Inference> = inference
.premises()
.iter()
.map(|p| &inferences[p.index()])
.collect();
if let Some((side, at)) = inference.principal()
&& let Some(&formula) = inference.side(side).get(at)
&& let ordinary::Node::Iff(a, b) = formulas.node(formula)
&& matches!(
inference.rule(),
Rule::IffLeft | Rule::IffLeft1 | Rule::IffLeft2 | Rule::IffRight
)
&& (formulas.find(ordinary::Node::Implies(a, b)).is_none()
|| formulas.find(ordinary::Node::Implies(b, a)).is_none())
{
return Err(invalid(format!(
"inference {index} ({}): the implications of the equivalence are missing",
inference.rule()
)));
}
let (name, side) = name(logic, inference, &premises);
let position = match (inference.principal(), side) {
(Some((on, _)), Some(side)) if on != side => {
return Err(invalid(format!(
"inference {index} ({}): the principal formula stands on the side \
the rule does not act on",
inference.rule()
)));
}
(Some((_, at)), _) => u32::try_from(at).ok(),
(None, _) => None,
};
let sequent = [zone(inference.left()), zone(inference.right())];
let premises: Vec<u32> = inference
.premises()
.iter()
.map(|p| p.index() as u32)
.collect();
let step = if inference.rule() == Rule::Open {
Step::Open
} else {
Step::Rule(&name)
};
out.push(
Node::new(&sequent, step)
.premises(&premises)
.positions(position.as_slice()),
)?;
}
Ok(out)
}
}