use super::reading::Side;
use super::{Forest, Member, OccId};
use crate::linear::sequents::notation::TEXT;
use crate::linear::sequents::{Kind, Sequent};
use crate::{Error, Limits};
use std::fmt::{Display, Formatter, Result as FmtResult};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub struct Written(u8);
impl Written {
const INPUT: u8 = 1;
const IMPLICATION: u8 = 2;
pub(crate) const fn new(side: Side, implication: bool) -> Self {
let input = match side {
Side::Input => Self::INPUT,
Side::Output => 0,
};
Self(input | if implication { Self::IMPLICATION } else { 0 })
}
pub const fn side(self) -> Side {
if self.0 & Self::INPUT == 0 {
Side::Output
} else {
Side::Input
}
}
pub const fn is_implication(self) -> bool {
self.0 & Self::IMPLICATION != 0
}
}
pub(crate) fn context(forest: &Forest, writing: &[Written], o: OccId) -> Side {
match forest.parent(o) {
Some(parent) => {
let written = writing[parent.index()];
if written.is_implication() && forest.left(parent) == Some(o) {
!written.side()
} else {
written.side()
}
}
None if !forest.is_conclusion(o) => {
if forest.is_cut_formula(o) {
Side::Output
} else {
Side::Input
}
}
None => {
let roots = forest.roots();
let antecedents = forest.sequent().antecedents().unwrap_or(0) as usize;
match roots.binary_search(&o) {
Ok(index) if index < antecedents => Side::Input,
_ => Side::Output,
}
}
}
}
pub(crate) fn negated(forest: &Forest, writing: &[Written], o: OccId) -> bool {
writing[o.index()].side() != context(forest, writing, o)
}
pub(crate) fn fault(forest: &Forest, writing: &[Written]) -> Option<&'static str> {
if writing.len() != forest.len() {
return Some("the record has another number of occurrences than the sequent");
}
for o in forest.ids() {
let (kind, written) = (forest.kind(o), writing[o.index()]);
let side = written.side();
if (kind == Kind::Atom && side == Side::Input)
|| (kind == Kind::DualAtom && side == Side::Output)
{
return Some("an atom is recorded on the wrong side");
}
let implication = (kind == Kind::Par && side == Side::Output)
|| (kind == Kind::Tensor && side == Side::Input);
if written.is_implication() && !implication {
return Some("an implication is recorded on what is no implication");
}
}
None
}
pub(crate) fn one_sided(forest: &Forest) -> Box<[Written]> {
let mut writing = vec![Written::new(Side::Output, false); forest.len()];
let antecedents = forest.sequent().antecedents().unwrap_or(0) as usize;
let roots = forest.roots().iter().enumerate().map(|(index, &root)| {
let side = if index < antecedents {
Side::Input
} else {
Side::Output
};
(root, side)
});
let cuts = forest
.cut_pairs()
.flat_map(|(a, dual)| [(a, Side::Output), (dual, Side::Input)]);
for (root, side) in roots.chain(cuts) {
let end = root.index() + forest.size(root) as usize;
for (k, written) in writing.iter_mut().enumerate().take(end).skip(root.index()) {
let side = match forest.kind(OccId::new(k as u32)) {
Kind::Atom => Side::Output,
Kind::DualAtom => Side::Input,
Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::Tensor
| Kind::Par
| Kind::With
| Kind::Plus
| Kind::Bang
| Kind::Quest
| Kind::Forall
| Kind::Exists => side,
};
*written = Written::new(side, false);
}
}
writing.into_boxed_slice()
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct ClassicalSequent {
forest: Forest,
writing: Box<[Written]>,
}
impl ClassicalSequent {
pub fn read_one_sided(sequent: Sequent, limits: &Limits) -> Result<Self, Error> {
let forest = Forest::from_owned(sequent, limits)?;
let writing = one_sided(&forest);
Ok(Self { forest, writing })
}
pub fn sequent(&self) -> &Sequent {
self.forest.sequent()
}
pub fn forest(&self) -> &Forest {
&self.forest
}
pub fn into_sequent(self) -> Sequent {
self.forest.sequent().clone()
}
pub fn writing(&self) -> &[Written] {
&self.writing
}
pub fn written(&self, o: OccId) -> Written {
self.writing[o.index()]
}
pub fn is_negated(&self, o: OccId) -> bool {
negated(&self.forest, &self.writing, o)
}
pub fn formula(&self, o: OccId) -> impl Display + '_ {
Shown {
forest: &self.forest,
writing: &self.writing,
o,
negated: self.is_negated(o),
}
}
}
pub(crate) struct Shown<'a> {
pub(crate) forest: &'a Forest,
pub(crate) writing: &'a [Written],
pub(crate) o: OccId,
pub(crate) negated: bool,
}
impl Display for Shown<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
TEXT.written(f, self.forest, self.writing, self.o, self.negated)
}
}
impl PartialEq for ClassicalSequent {
fn eq(&self, other: &Self) -> bool {
let (a, b) = (&self.forest, &other.forest);
fn name(forest: &Forest, o: OccId) -> Option<&str> {
forest.atom(o).map(|x| forest.sequent().atom_name(x))
}
let antecedents = |forest: &Forest| forest.sequent().antecedents().unwrap_or(0);
a.len() == b.len()
&& a.roots() == b.roots()
&& antecedents(a) == antecedents(b)
&& self.writing == other.writing
&& a.ids()
.all(|o| a.kind(o) == b.kind(o) && name(a, o) == name(b, o))
}
}
impl Eq for ClassicalSequent {}
impl Display for ClassicalSequent {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
let (forest, writing) = (&self.forest, &self.writing[..]);
let antecedents = forest.sequent().antecedents().unwrap_or(0) as usize;
let shown = |&o: &OccId| (Member::from(o), negated(forest, writing, o));
let roots = forest.roots();
let (left, right) = roots.split_at(antecedents.min(roots.len()));
TEXT.classical(
f,
forest,
writing,
None,
left.iter().map(shown),
right.iter().map(shown),
false,
false,
)
}
}
#[cfg(feature = "parse")]
impl ClassicalSequent {
pub fn parse_within(text: &str, limits: &Limits) -> Result<Self, Error> {
let (sequent, writing) = crate::linear::parse::written(text, limits)?;
let forest = Forest::from_owned(sequent, limits)?;
debug_assert_eq!(fault(&forest, &writing), None, "a parsed record fits");
Ok(Self {
forest,
writing: writing.into_boxed_slice(),
})
}
}
#[cfg(feature = "parse")]
impl std::str::FromStr for ClassicalSequent {
type Err = Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Self::parse_within(s, &Limits::default())
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::generate::{self, Rng, Rules};
fn letters(writing: &[Written]) -> String {
let letter = |w: &Written| match (w.side(), w.is_implication()) {
(Side::Output, false) => 'o',
(Side::Input, false) => 'i',
(Side::Output, true) => 'O',
(Side::Input, true) => 'I',
};
writing.iter().map(letter).collect()
}
#[test]
fn the_parser_records_what_was_written() {
let cases = [
("A -o B |- ~(C * D), ~~E", "Ioiiiio", "A ⊸ B ⊢ ~(C ⊗ D), E"),
("|- A -o B, A^ par B", "Oiooio", "⊢ A ⊸ B, ~A ⅋ B"),
(
"bot, 1 |- top, ~0, !A, ?~B",
"iioioooi",
"⊥, 1 ⊢ ⊤, ~0, !A, ?~B",
),
("~(A -o B) |- ~!A", "Oioii", "~(A ⊸ B) ⊢ ~!A"),
];
for (text, record, printed) in cases {
let written: ClassicalSequent = text.parse().unwrap();
assert_eq!(letters(written.writing()), record, "{text}");
assert_eq!(written.to_string(), printed, "{text}");
let one_sided: Sequent = text.parse().unwrap();
assert_eq!(written.sequent(), &one_sided, "{text}");
}
}
#[test]
fn a_one_sided_sequent_is_written_one_sided() {
let limits = Limits::default();
for (text, printed) in [("|- ~a, a", "⊢ ~a, a"), ("a |- a", "a ⊢ a")] {
let sequent: Sequent = text.parse().unwrap();
let written = ClassicalSequent::read_one_sided(sequent, &limits).unwrap();
assert_eq!(fault(written.forest(), written.writing()), None);
assert_eq!(written.to_string(), printed);
}
}
#[test]
fn a_written_sequent_prints_back_to_itself() {
let mut tried = 0;
for (i, rules) in Rules::ALL.into_iter().enumerate() {
let mut rng = Rng::new(40 + i as u64);
for _ in 0..12 {
let budget = 2 + rng.below(10);
let provable = generate::provable(&mut rng, rules, 3, budget);
let one_sided: Sequent = generate::sequent(&provable.formulas).parse().unwrap();
for _ in 0..3 {
let (text, record) = generate::written(&mut rng, &provable.formulas);
let written: ClassicalSequent = text.parse().unwrap();
assert_eq!(written.writing(), &record[..], "{text}");
assert_eq!(fault(written.forest(), written.writing()), None);
assert_eq!(
written.sequent().to_string(),
one_sided.to_string(),
"{text}"
);
let printed = written.to_string();
let again: ClassicalSequent = printed.parse().unwrap();
assert_eq!(again, written, "{text} printed as {printed}");
assert_eq!(again.to_string(), printed, "{text}");
tried += 1;
}
}
}
assert_eq!(tried, 16 * 12 * 3);
}
}