use super::{Forest, OccId};
use crate::errors::describe::{Limit, Names, cut};
use crate::errors::{Described, Owner, Subject};
use crate::linear::sequents::notation::TEXT;
use crate::linear::sequents::{Kind, Walk};
use std::borrow::Cow;
use std::fmt::{Display, Formatter, Result as FmtResult};
#[repr(u8)]
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Side {
Input,
Output,
}
impl std::ops::Not for Side {
type Output = Self;
fn not(self) -> Self {
match self {
Side::Input => Side::Output,
Side::Output => Side::Input,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ShapeError {
NoGoal,
#[non_exhaustive]
SeveralGoals {
first: OccId,
second: OccId,
},
#[non_exhaustive]
Formula {
occurrence: OccId,
formula: Option<Box<str>>,
},
#[non_exhaustive]
Succedents {
count: usize,
},
#[non_exhaustive]
Hypothesis {
index: usize,
},
#[non_exhaustive]
Undetermined {
first: OccId,
second: OccId,
},
EmptyAntecedent,
#[non_exhaustive]
CutFormula {
occurrence: OccId,
},
}
impl Display for ShapeError {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write(f, None, None)
}
}
impl ShapeError {
pub fn describe<'a>(&'a self, owner: &'a impl Owner) -> Described<'a> {
Described::new(Subject::Shape(self), owner)
}
pub(crate) fn write(
&self,
f: &mut Formatter<'_>,
names: Option<Names<'_>>,
limit: Limit,
) -> FmtResult {
let occurrence = |f: &mut Formatter<'_>, o: OccId| cut(f, names, o.into(), limit);
let forest = names.map(|n| n.forest);
match self {
ShapeError::NoGoal => f.write_str(
"no formula can be the goal: an intuitionistic sequent has exactly one formula right of ⊢",
),
ShapeError::Succedents { count } => {
write!(
f,
"an intuitionistic sequent has exactly one formula right of ⊢, not {count}"
)?;
if *count > 1 {
f.write_str(": write the hypotheses left of ⊢")?;
}
Ok(())
}
ShapeError::Hypothesis { index } => write!(
f,
"formula {} left of ⊢ cannot be a hypothesis of an intuitionistic sequent",
index + 1
),
ShapeError::Undetermined { first, second } => {
f.write_str(if forest.is_some() {
"both "
} else {
"both formula "
})?;
occurrence(f, *first)?;
f.write_str(" and ")?;
occurrence(f, *second)?;
f.write_str(
" can be the goal, and the sequent does not say which one stands right of ⊢: write the sequent with both sides",
)
}
ShapeError::SeveralGoals { first: a, second: b } => {
f.write_str(if forest.is_some() {
"both "
} else {
"both formula "
})?;
occurrence(f, *a)?;
f.write_str(" and ")?;
occurrence(f, *b)?;
f.write_str(" can only be the goal, but an intuitionistic sequent has one")
}
ShapeError::EmptyAntecedent => f.write_str(
"the sequent has no formula left of ⊢, which the Lambek calculus without empty antecedents needs",
),
ShapeError::CutFormula { occurrence: o } => {
f.write_str(if forest.is_some() {
"the cut formula "
} else {
"cut formula "
})?;
occurrence(f, *o)?;
f.write_str(" is not an intuitionistic formula")
}
ShapeError::Formula {
occurrence: o,
formula,
} => {
match (forest, formula) {
(None, Some(formula)) => write!(f, "the subformula {formula}")?,
(None, None) => {
f.write_str("subformula ")?;
occurrence(f, *o)?;
}
(Some(_), _) => {
f.write_str("the subformula ")?;
occurrence(f, *o)?;
}
}
if let Some(forest) = forest
&& forest.root(*o) != *o
{
write!(f, " (in {})", forest.formula(forest.root(*o)))?;
}
f.write_str(
" is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation",
)
}
}
}
}
impl std::error::Error for ShapeError {}
impl ShapeError {
const SHOWN: usize = 1 << 12;
fn formula(forest: &Forest, o: OccId) -> Self {
let mut text = String::new();
let names = Names {
forest,
reading: None,
framing: None,
};
let _ = cut(&mut text, Some(names), o.into(), Some(Self::SHOWN));
Self::Formula {
occurrence: o,
formula: Some(text.into_boxed_str()),
}
}
}
const IN: u8 = 1;
const OUT: u8 = 2;
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct Reading<'a> {
forest: &'a Forest,
position: Cow<'a, [Side]>,
goal: OccId,
ordered: bool,
}
impl<'a> Reading<'a> {
pub fn new(forest: &'a Forest) -> Result<Self, ShapeError> {
Self::read(forest, false)
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn of_mode(forest: &'a Forest, mode: crate::linear::Mode) -> Result<Self, ShapeError> {
let reading = Self::read(forest, mode.is_ordered())?;
if !mode.allows_empty_antecedents() && forest.roots().len() < 2 {
return Err(ShapeError::EmptyAntecedent);
}
Ok(reading)
}
fn read(forest: &'a Forest, ordered: bool) -> Result<Self, ShapeError> {
use Kind::*;
let mut can = vec![0u8; forest.len()];
for o in forest.ids().rev() {
let child = |k: Option<OccId>| k.map_or(0, |k| can[k.index()]);
let (l, r) = (child(forest.left(o)), child(forest.right(o)));
let (l_in, l_out, r_in, r_out) = (l & IN != 0, l & OUT != 0, r & IN != 0, r & OUT != 0);
let both = |i: bool, u: bool| (u8::from(i) * IN) | (u8::from(u) * OUT);
can[o.index()] = match forest.kind(o) {
Atom | One | Bang => both(false, l_out || forest.kind(o) != Bang),
DualAtom | Bot | Quest => both(l_in || forest.kind(o) != Quest, false),
Top | Zero => IN | OUT,
Forall | Exists => both(l_in, l_out),
With | Plus => both(l_in && r_in, l_out && r_out),
Tensor => both(l_out && r_in || ordered && l_in && r_out, l_out && r_out),
Par => both(l_in && r_in, l_in && r_out || ordered && l_out && r_in),
};
if can[o.index()] == 0 {
return Err(ShapeError::formula(forest, o));
}
}
let roots = forest.roots();
let goal = match forest.sequent().antecedents() {
Some(k) => {
let (left, right) = roots.split_at(k as usize);
let &[goal] = right else {
return Err(ShapeError::Succedents { count: right.len() });
};
let refused = |o: &OccId| can[o.index()] & IN == 0;
let index = if ordered {
left.iter().rposition(refused).map(|i| left.len() - 1 - i)
} else {
left.iter().position(refused)
};
if let Some(index) = index {
return Err(ShapeError::Hypothesis { index });
}
if can[goal.index()] & OUT == 0 {
return Err(ShapeError::NoGoal);
}
goal
}
None => {
let mut only_goals = roots.iter().copied().filter(|&o| can[o.index()] == OUT);
match (only_goals.next(), only_goals.next()) {
(Some(a), Some(b)) => {
return Err(ShapeError::SeveralGoals {
first: a,
second: b,
});
}
(Some(goal), None) => goal,
(None, _) => {
let mut goals =
roots.iter().copied().filter(|&o| can[o.index()] & OUT != 0);
match (goals.next(), goals.next()) {
(Some(first), Some(second)) => {
return Err(ShapeError::Undetermined { first, second });
}
(Some(goal), None) => goal,
(None, _) => return Err(ShapeError::NoGoal),
}
}
}
}
};
for (a, dual) in forest.cut_pairs() {
if can[a.index()] & OUT == 0 || can[dual.index()] & IN == 0 {
return Err(ShapeError::CutFormula { occurrence: a });
}
}
let mut position = vec![Side::Input; forest.len()].into_boxed_slice();
position[goal.index()] = Side::Output;
for (a, _) in forest.cut_pairs() {
position[a.index()] = Side::Output;
}
for o in forest.ids() {
let p = position[o.index()];
let Some((l, r)) = forest.left(o).zip(forest.right(o)) else {
if let Some(l) = forest.left(o) {
position[l.index()] = p;
}
continue;
};
let implication = matches!(
(forest.kind(o), p),
(Tensor, Side::Input) | (Par, Side::Output)
);
let takes = |k: OccId, side: Side| {
can[k.index()] & if side == Side::Input { IN } else { OUT } != 0
};
let right_flips = implication && ordered && !(takes(l, !p) && takes(r, p));
position[l.index()] = if implication && !right_flips { !p } else { p };
position[r.index()] = if right_flips { !p } else { p };
}
Ok(Self {
forest,
position: Cow::Owned(position.into_vec()),
goal,
ordered,
})
}
pub(crate) fn into_parts(self) -> (Box<[Side]>, OccId) {
(self.position.into_owned().into_boxed_slice(), self.goal)
}
pub(crate) fn held_bytes(&self) -> usize {
match &self.position {
Cow::Owned(position) => position.capacity() * size_of::<Side>(),
Cow::Borrowed(_) => 0,
}
}
pub(crate) const fn of_parts(
forest: &'a Forest,
position: &'a [Side],
goal: OccId,
ordered: bool,
) -> Self {
Self {
forest,
position: Cow::Borrowed(position),
goal,
ordered,
}
}
pub fn is_ordered(&self) -> bool {
self.ordered
}
pub fn forest(&self) -> &'a Forest {
self.forest
}
pub fn position(&self, o: OccId) -> Side {
self.position[o.index()]
}
pub fn goal(&self) -> OccId {
self.goal
}
pub fn hypotheses(&self) -> impl Iterator<Item = OccId> + '_ {
let roots = self.forest.roots();
let at = roots.partition_point(|&r| r < self.goal);
let len = roots.len();
let ordered = self.ordered;
(0..len - 1).map(move |i| {
roots[match (ordered, i < at) {
(false, true) => i,
(false, false) => i + 1,
(true, true) => at - 1 - i,
(true, false) => len - 1 - (i - at),
}]
})
}
pub(crate) fn written<'s>(
&'s self,
sequent: &'s [super::Member],
) -> impl Iterator<Item = usize> + 's {
self.written_by(sequent, super::Member::occ)
}
pub(crate) fn written_by<'s>(
&'s self,
sequent: &'s [super::Member],
occ: impl Fn(super::Member) -> OccId + Copy + 's,
) -> impl Iterator<Item = usize> + 's {
let output = move |p: usize| self.position(occ(sequent[p])) == Side::Output;
let len = sequent.len();
let ordered = self.ordered;
let at = if ordered {
(0..len).rfind(|&p| output(p)).unwrap_or(len)
} else {
0
};
let order = (0..len).map(move |i| match (ordered, i < at) {
(false, _) => i,
(true, true) => at - 1 - i,
(true, false) => len - 1 - (i - at),
});
order
.clone()
.filter(move |&p| !output(p))
.chain(order.filter(move |&p| output(p)))
}
pub fn implication(&self, o: OccId) -> Option<(OccId, OccId)> {
match (self.forest.kind(o), self.position(o)) {
(Kind::Par, Side::Output) | (Kind::Tensor, Side::Input) => {
let (l, r) = (self.forest.left(o)?, self.forest.right(o)?);
if self.ordered && self.position(r) != self.position(o) {
Some((r, l))
} else {
Some((l, r))
}
}
_ => None,
}
}
pub fn outputs(&self, ids: impl IntoIterator<Item = OccId>) -> usize {
ids.into_iter()
.filter(|&o| self.position(o) == Side::Output)
.count()
}
pub fn formula(&self, o: OccId) -> IllFormula<'_> {
IllFormula {
reading: self,
id: o,
}
}
pub fn connective(&self, o: OccId) -> IllConnective {
use IllConnective as C;
if self.ordered
&& let Some((antecedent, _)) = self.implication(o)
{
return if Some(antecedent) == self.operands(o).0 {
C::Under
} else {
C::Over
};
}
match (self.forest.kind(o), self.position(o)) {
(Kind::Atom | Kind::DualAtom, _) => C::Atom,
(Kind::One | Kind::Bot, _) => C::One,
(Kind::Top, Side::Output) | (Kind::Zero, Side::Input) => C::Top,
(Kind::Zero, Side::Output) | (Kind::Top, Side::Input) => C::Zero,
(Kind::Bang | Kind::Quest, _) => C::Bang,
(Kind::Tensor, Side::Output) | (Kind::Par, Side::Input) => C::Tensor,
(Kind::Tensor, Side::Input) | (Kind::Par, Side::Output) => C::Lollipop,
(Kind::With, Side::Output) | (Kind::Plus, Side::Input) => C::With,
(Kind::Plus, Side::Output) | (Kind::With, Side::Input) => C::Plus,
(Kind::Forall, Side::Output) | (Kind::Exists, Side::Input) => C::Forall,
(Kind::Exists, Side::Output) | (Kind::Forall, Side::Input) => C::Exists,
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn walk(&self, o: OccId) -> Walk<'_, OccId> {
Walk::new(o, |o| self.operands(o))
}
pub(crate) fn operands(&self, o: OccId) -> (Option<OccId>, Option<OccId>) {
let (l, r) = (self.forest.left(o), self.forest.right(o));
if self.ordered {
let reversed = self.position(o) == Side::Input
&& matches!(self.forest.kind(o), Kind::Tensor | Kind::Par);
return if reversed { (r, l) } else { (l, r) };
}
match self.implication(o) {
Some((antecedent, consequent)) => (Some(antecedent), Some(consequent)),
None => (l, r),
}
}
}
impl Display for Reading<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
TEXT.reading(f, self)
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum IllConnective {
Atom,
One,
Zero,
Top,
Bang,
Tensor,
With,
Plus,
Lollipop,
Under,
Over,
Forall,
Exists,
}
#[derive(Clone, Copy, Debug)]
pub struct IllFormula<'a> {
reading: &'a Reading<'a>,
id: OccId,
}
impl Display for IllFormula<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
TEXT.ill(f, self.reading, self.id, false)
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::Sequent;
use crate::linear::search::generate::Rng;
fn read(input: &str) -> Result<String, String> {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let forest = Forest::new(&s).unwrap();
Reading::new(&forest)
.map(|r| r.to_string())
.map_err(|e| e.describe(&forest).to_string())
}
#[test]
fn one_occurrence_is_written_in_its_position() {
let s: Sequent = "!(A -o B), A |- !(A -o B) * A".parse().unwrap();
let forest = Forest::new(&s).unwrap();
let reading = Reading::new(&forest).unwrap();
let written: Vec<String> = forest
.ids()
.map(|o| reading.formula(o).to_string())
.collect();
let at = |text: &str| written.iter().filter(|w| *w == text).count();
assert_eq!(at("A ⊸ B"), 2, "{written:?}");
assert_eq!(at("!(A ⊸ B)"), 2, "{written:?}");
assert_eq!(at("!(A ⊸ B) ⊗ A"), 1, "{written:?}");
assert!(
written.iter().all(|w| !w.contains('~') && !w.contains('⊥')),
"{written:?}"
);
}
#[test]
fn shapes() {
for (input, two_sided) in [
("A, A -o B |- B", "A, A ⊸ B ⊢ B"),
("|- A", "⊢ A"),
("A -o B -o C |- (A * B) -o C", "A ⊸ (B ⊸ C) ⊢ (A ⊗ B) ⊸ C"),
("|- A & B -o A + B", "⊢ (A & B) ⊸ (A ⊕ B)"),
("A & B |- A + B", "A & B ⊢ A ⊕ B"),
("!A, !(A -o B) |- !B", "!A, !(A ⊸ B) ⊢ !B"),
("(A -o B) -o C |- D", "(A ⊸ B) ⊸ C ⊢ D"),
("0 |- top", "0 ⊢ ⊤"),
("top |- top * top", "⊤ ⊢ ⊤ ⊗ ⊤"),
("A * top |- A", "A ⊗ ⊤ ⊢ A"),
("1, top, 0 |- 1 * top * 0", "1, ⊤, 0 ⊢ (1 ⊗ ⊤) ⊗ 0"),
] {
assert_eq!(read(input).as_deref(), Ok(two_sided), "{input:?}");
}
for (input, message) in [
(
"|-",
"an intuitionistic sequent has exactly one formula right of ⊢, not 0",
),
(
"A, B |-",
"an intuitionistic sequent has exactly one formula right of ⊢, not 0",
),
(
"A |- B, C",
"an intuitionistic sequent has exactly one formula right of ⊢, not 2: write the hypotheses left of ⊢",
),
(
"~A |- B",
"formula 1 left of ⊢ cannot be a hypothesis of an intuitionistic sequent",
),
(
"|- B par ~A",
"the subformula B ⅋ ~A is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation",
),
(
"|- A par B",
"the subformula A ⅋ B is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation",
),
(
"A * (B par C) |- D",
"the subformula ~B ⊗ ~C (in ~A ⅋ (~B ⊗ ~C)) is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation",
),
(
"|- ?A",
"the subformula ?A is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation",
),
(
"|- ~A",
"no formula can be the goal: an intuitionistic sequent has exactly one formula right of ⊢",
),
] {
assert_eq!(
read(input).as_ref().map_err(String::as_str),
Err(message),
"{input:?}"
);
}
let s: Sequent = "|- A par B".parse().unwrap();
let forest = Forest::new(&s).unwrap();
let error = Reading::new(&forest).unwrap_err();
assert_eq!(
error.to_string(),
"the subformula A ⅋ B is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation"
);
let ShapeError::Formula { occurrence, .. } = error else {
panic!("{error:?}");
};
let unnamed = ShapeError::Formula {
occurrence,
formula: None,
};
assert_eq!(
unnamed.to_string(),
"subformula 0 is neither an intuitionistic formula nor the negation of one: intuitionistic linear logic has ⅋ only in A ⊸ B (~A ⅋ B), and ? only under a negation"
);
}
fn read_unsided(input: &str) -> Result<String, String> {
let mut s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
s.antecedents = None;
let forest = Forest::new(&s).unwrap();
Reading::new(&forest)
.map(|r| r.to_string())
.map_err(|e| e.describe(&forest).to_string())
}
#[test]
fn the_first_written_hypothesis_is_named() {
let sequent = Sequent::parse_ordered(
"~a, b, ~c |- d",
crate::linear::Order::Cyclic,
&crate::Limits::default(),
)
.unwrap();
let forest = Forest::new(&sequent).unwrap();
assert_eq!(
Reading::of_mode(&forest, crate::linear::Mode::LAMBEK).unwrap_err(),
ShapeError::Hypothesis { index: 0 }
);
}
#[test]
fn the_written_sides_decide() {
let several = "an intuitionistic sequent has exactly one formula right of ⊢, not 2: write the hypotheses left of ⊢";
assert_eq!(read("|- top, a"), Err(several.to_owned()));
assert_eq!(read("|- a, top"), Err(several.to_owned()));
let h9 = "(A -o bot) -o bot |- A";
assert!(
read(h9)
.unwrap_err()
.contains("neither an intuitionistic formula")
);
assert!(
read_unsided(h9)
.unwrap_err()
.contains("neither an intuitionistic formula")
);
assert_eq!(read_unsided("|- top, a").as_deref(), Ok("0 ⊢ a"));
assert_eq!(
read_unsided("|- 0, top"),
Err(
"both 0 and ⊤ can be the goal, and the sequent does not say which one stands right of ⊢: write the sequent with both sides".to_owned()
)
);
assert_eq!(
read_unsided("A, A -o B |- B").as_deref(),
Ok("A, A ⊸ B ⊢ B")
);
}
#[test]
fn positions() {
let mut s: Sequent = "|- A -o (B -o C), D".parse().unwrap();
let forest = Forest::new(&s).unwrap();
assert_eq!(
Reading::new(&forest).unwrap_err(),
ShapeError::Succedents { count: 2 }
);
s.antecedents = None;
let forest = Forest::new(&s).unwrap();
assert!(matches!(
Reading::new(&forest),
Err(ShapeError::SeveralGoals { first: a, second: b }) if a == OccId::new(0) && b == OccId::new(5)
));
let s: Sequent = "A -o (B -o C) |- D".parse().unwrap();
let forest = Forest::new(&s).unwrap();
let r = Reading::new(&forest).unwrap();
let o = OccId::new;
assert_eq!(r.goal(), o(5));
assert_eq!(r.hypotheses().collect::<Vec<_>>(), [o(0)]);
let positions: Vec<Side> = forest.ids().map(|i| r.position(i)).collect();
use Side::*;
assert_eq!(positions, [Input, Output, Input, Output, Input, Output]);
assert_eq!(r.implication(o(0)), Some((o(1), o(2))));
assert_eq!(r.implication(o(2)), Some((o(3), o(4))));
assert_eq!(r.implication(o(1)), None);
assert_eq!(r.outputs(forest.roots().iter().copied()), 1);
assert_eq!(r.formula(o(2)).to_string(), "B ⊸ C");
assert_eq!(r.formula(o(3)).to_string(), "B");
}
fn formula(rng: &mut Rng, depth: usize) -> String {
if depth == 0 || rng.one_in(3) {
return match rng.below(6) {
0 => "1".into(),
1 => "top".into(),
2 => "0".into(),
_ => ["a", "b", "c"][rng.below(3)].into(),
};
}
let sub = |rng: &mut Rng| formula(rng, depth - 1);
match rng.below(6) {
0 => format!("({} * {})", sub(rng), sub(rng)),
1 => format!("({} -o {})", sub(rng), sub(rng)),
2 => format!("({} & {})", sub(rng), sub(rng)),
3 => format!("({} + {})", sub(rng), sub(rng)),
4 => format!("!{}", sub(rng)),
_ => format!("({} -o {})", sub(rng), sub(rng)),
}
}
#[test]
fn print_parse_round_trip() {
let mut rng = Rng::new(8);
for _ in 0..500 {
let hypotheses: Vec<String> = (0..rng.below(4)).map(|_| formula(&mut rng, 3)).collect();
let input = format!("{} |- {}", hypotheses.join(", "), formula(&mut rng, 3));
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let forest = Forest::new(&s).unwrap();
let printed = Reading::new(&forest)
.unwrap_or_else(|e| panic!("{input:?}: {}", e.describe(&forest)))
.to_string();
let back: Sequent = printed
.parse()
.unwrap_or_else(|e| panic!("{input:?} printed as {printed:?}: {e}"));
assert_eq!(
back.fragment(),
s.fragment(),
"{input:?} printed as {printed:?}"
);
assert_eq!(
back.roots().len(),
s.roots().len(),
"{input:?} printed as {printed:?}"
);
let forest = Forest::new(&back).unwrap();
assert_eq!(Reading::new(&forest).unwrap().to_string(), printed);
}
}
}