use super::reading::{Reading, Side};
use super::{Forest, OccId};
use crate::linear::sequents::Sequent;
use crate::{Error, Limits};
use std::fmt::{Display, Formatter, Result as FmtResult};
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug)]
pub struct IllSequent {
forest: Forest,
position: Box<[Side]>,
goal: OccId,
}
impl IllSequent {
#[cfg(any(feature = "parse", feature = "serialize"))]
pub(crate) fn lowered(sequent: Sequent, limits: &Limits) -> Result<Self, Error> {
use super::reading::ShapeError;
use crate::linear::sequents::Kind;
let antecedents = sequent.antecedents().unwrap_or(0) as usize;
let succedents = sequent.roots().len().saturating_sub(antecedents);
if succedents != 1 {
return Err(Error::NotIntuitionistic(ShapeError::Succedents {
count: succedents,
}));
}
let forest = Forest::from_owned(sequent, limits)?;
let goal = forest.roots()[antecedents];
let mut position = vec![Side::Input; forest.len()].into_boxed_slice();
position[goal.index()] = Side::Output;
for o in forest.ids() {
let side = position[o.index()];
let implication = matches!(
(forest.kind(o), side),
(Kind::Par, Side::Output) | (Kind::Tensor, Side::Input)
);
if let Some(left) = forest.left(o) {
position[left.index()] = if implication { !side } else { side };
}
if let Some(right) = forest.right(o) {
position[right.index()] = side;
}
}
let lowered = Self {
forest,
position,
goal,
};
debug_assert!(
Reading::new(&lowered.forest).is_ok_and(|reading| reading.goal() == goal
&& lowered
.forest
.ids()
.all(|o| reading.position(o) == lowered.position[o.index()])),
"the recorded sides are the reading's"
);
Ok(lowered)
}
pub fn read_one_sided(sequent: Sequent, limits: &Limits) -> Result<Self, Error> {
let forest = Forest::from_owned(sequent, limits)?;
let (position, goal) = Reading::new(&forest)
.map_err(Error::NotIntuitionistic)?
.into_parts();
Ok(Self {
forest,
position,
goal,
})
}
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 goal(&self) -> OccId {
self.goal
}
pub fn reading(&self) -> Reading<'_> {
Reading::of_parts(&self.forest, &self.position, self.goal, false)
}
}
impl PartialEq for IllSequent {
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))
}
a.len() == b.len()
&& a.roots() == b.roots()
&& self.goal == other.goal
&& self.position == other.position
&& a.ids()
.all(|o| a.kind(o) == b.kind(o) && name(a, o) == name(b, o))
}
}
impl Eq for IllSequent {}
impl Display for IllSequent {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.reading().fmt(f)
}
}
#[cfg(feature = "parse")]
impl IllSequent {
pub fn parse_within(text: &str, limits: &Limits) -> Result<Self, Error> {
let sequent = match Sequent::parse_within(text, limits) {
Ok(sequent) => sequent,
Err(Error::Parse(error)) => {
return Err(crate::linear::parse::classical(text, error.span.start)
.map_or(Error::Parse(error), Error::from));
}
Err(error) => return Err(error),
};
if let Some(error) = crate::linear::parse::classical(text, text.len()) {
return Err(error.into());
}
Self::lowered(sequent, limits)
}
}
#[cfg(feature = "parse")]
impl std::str::FromStr for IllSequent {
type Err = Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Self::parse_within(s, &Limits::default())
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(rename_all = "kebab-case")
)]
pub enum IllSyntax {
#[default]
Strict,
OneSided,
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(default, deny_unknown_fields)
)]
pub struct InputOptions {
pub intuitionistic: IllSyntax,
}
impl InputOptions {
pub const DEFAULT_INTUITIONISTIC: IllSyntax = IllSyntax::Strict;
#[must_use]
pub const fn with_intuitionistic(self, intuitionistic: IllSyntax) -> Self {
Self { intuitionistic }
}
}
impl Default for InputOptions {
fn default() -> Self {
Self {
intuitionistic: Self::DEFAULT_INTUITIONISTIC,
}
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::errors::ParseError;
use crate::linear::occurrences::ShapeError;
use crate::linear::search::generate::{self, IllRules, Rng};
use crate::linear::sequents::notation::TEXT;
use crate::linear::{Mode, search};
fn generated(seed: u64, per: usize) -> Vec<String> {
let mut texts = Vec::new();
for (i, rules) in IllRules::ALL.into_iter().enumerate() {
let mut rng = Rng::new(seed + i as u64);
for _ in 0..per {
let budget = 2 + rng.below(10);
let ill = generate::ill(&mut rng, rules, 3, budget);
texts.push(generate::two_sided(&ill.hypotheses, &ill.goal));
}
}
texts
}
fn refused(text: &str) -> ParseError {
match text.parse::<IllSequent>() {
Err(Error::Parse(error)) => *error,
other => panic!("{text:?}: {other:?}"),
}
}
#[test]
fn the_strict_parser_refuses_classical_symbols() {
for (text, at, hint) in [
("~(A * ~B), A |- B", 0..1, "no negation"),
("A^ |- B", 1..2, "no negation"),
("|- A par B", 5..8, "no par"),
("|- A ⅋ B", 5..8, "no par"),
("|- A | B", 5..6, "no par"),
("?A |- B", 0..1, "no ?"),
("|- bot", 3..6, "no bot"),
("⊥ |- A", 0..3, "no bot"),
] {
let error = refused(text);
assert_eq!(error.span, at, "{text:?}");
assert!(
error.hint.is_some_and(|h| h.contains(hint)),
"{text:?}: {error}"
);
assert!(error.to_string().contains(hint), "{error}");
}
assert_eq!(refused("A -obot |- B").span, 4..7);
assert_eq!(refused("(A -obot) -obot |- A").span, 5..8);
let sequent: IllSequent = "A |-obot".parse().unwrap();
assert_eq!(sequent.to_string(), "A ⊢ obot");
for text in ["A |- B |- C", "(A |- B)"] {
let error = refused(text);
assert_eq!(error.hint, None, "{text:?}");
assert!(text[error.span.start..].starts_with('-'), "{text:?}");
}
let error = refused("A * , ~B |- C");
assert_eq!((error.span, error.hint), (4..5, None));
assert_eq!(refused("~A * , B |- C").span, 0..1);
let sequent: IllSequent = "bottom, parity |- bottom ⊗ parity".parse().unwrap();
assert_eq!(sequent.to_string(), "bottom, parity ⊢ bottom ⊗ parity");
for (text, count) in [("A |- B, C", 2), ("A |-", 0)] {
assert!(
matches!(
text.parse::<IllSequent>(),
Err(Error::NotIntuitionistic(ShapeError::Succedents { count: c })) if c == count
),
"{text:?}"
);
}
}
#[test]
fn a_one_sided_sequent_is_read_explicitly() {
let limits = Limits::default();
let read = |text: &str| {
let sequent: Sequent = text.parse().unwrap();
IllSequent::read_one_sided(sequent, &limits)
};
assert_eq!(
read("~(A * ~B), A |- B").unwrap().to_string(),
"A ⊸ B, A ⊢ B"
);
assert!(matches!(
read("|- A par B"),
Err(Error::NotIntuitionistic(ShapeError::Formula { .. }))
));
let mut unsided: Sequent = "|- 0, top".parse().unwrap();
unsided.antecedents = None;
assert!(matches!(
IllSequent::read_one_sided(unsided, &limits),
Err(Error::NotIntuitionistic(ShapeError::Undetermined { .. }))
));
}
#[test]
fn the_recorded_sides_are_the_readings() {
let units = [
"top |- 0",
"0 |- top",
"top, 0 |- top & 0",
"(top -o 0) -o top |- 0 + top",
"!(0 -o top), 1 |- (1 -o top) * 0",
];
let texts = generated(4000, 20);
for text in units
.iter()
.copied()
.chain(texts.iter().map(String::as_str))
{
let sequent: IllSequent = text.parse().unwrap_or_else(|e| panic!("{text:?}: {e}"));
let reading = Reading::new(sequent.forest()).unwrap();
assert_eq!(reading.goal(), sequent.goal(), "{text:?}");
let recorded = sequent.reading();
for o in sequent.forest().ids() {
assert_eq!(
reading.position(o),
recorded.position(o),
"{text:?} at {o:?}"
);
}
#[cfg(feature = "interactive")]
{
use crate::{
Limits,
linear::{CutFormula, InputOptions, Interactive},
};
let limits = Limits::default();
let goal = recorded.formula(recorded.goal()).to_string();
let mut session =
Interactive::new(sequent.sequent(), Mode::INTUITIONISTIC).unwrap();
let mut open = session.goals().next().unwrap();
for cut in [goal.as_str(), "top -o 0", "0 * top"] {
let len = session.goal(open).unwrap().len();
let formula = CutFormula::parse_within(
cut,
Mode::INTUITIONISTIC,
&InputOptions::default(),
&limits,
)
.unwrap();
open = session.cut(open, &formula, &[], &limits).unwrap()[1];
assert_eq!(session.goal(open).unwrap().len(), len + 1);
}
let forest = session.forest();
let reading = Reading::new(forest).unwrap();
let recorded = session.reading().unwrap();
assert_eq!(forest.cut_pairs().len(), 3);
for o in forest.ids() {
assert_eq!(
reading.position(o),
recorded.position(o),
"{text:?} at {o:?}"
);
}
}
}
}
#[test]
fn a_parsed_sequent_prints_back_to_itself() {
for text in generated(4100, 20) {
let sequent: IllSequent = text.parse().unwrap_or_else(|e| panic!("{text:?}: {e}"));
let printed = sequent.to_string();
let back: IllSequent = printed
.parse()
.unwrap_or_else(|e| panic!("{text:?} printed as {printed:?}: {e}"));
assert_eq!(back, sequent, "{text:?} printed as {printed:?}");
}
}
#[test]
fn every_inference_prints_as_an_intuitionistic_sequent() {
let options = search::Options::default();
let mut inferences = 0;
#[cfg(feature = "interactive")]
let mut cuts = 0;
let mut proofs = vec![];
for text in generated(4200, 6) {
let sequent: IllSequent = text.parse().unwrap();
let outcome = search::prove(sequent.sequent(), Mode::INTUITIONISTIC, &options).unwrap();
if let Some(proof) = outcome.verdict.proof() {
proofs.push((text, proof.clone()));
}
}
#[cfg(feature = "interactive")]
{
let found: Vec<_> = proofs
.iter()
.map(|(_, p)| (p.clone(), Mode::INTUITIONISTIC))
.collect();
for (proof, _) in
crate::linear::proofs::interactive::with_cuts(&found, &mut Rng::new(41))
{
proofs.push((proof.sequent().to_string(), proof));
}
}
for (text, proof) in &proofs {
let derivation = proof.derivation().unwrap();
let reading = derivation
.reading()
.expect("an intuitionistic proof is two-sided");
for inference in derivation.inferences() {
let mut printed = String::new();
TEXT.sequent(
&mut printed,
proof.forest(),
Some(reading),
None,
inference.sequent(),
false,
false,
)
.unwrap();
let back: IllSequent = printed
.parse()
.unwrap_or_else(|e| panic!("{text:?}: {printed:?}: {e}"));
let formulas = |reading: &Reading, members: &mut dyn Iterator<Item = OccId>| {
members
.map(|o| reading.formula(o).to_string())
.collect::<Vec<_>>()
};
let written: Vec<OccId> = reading
.written(inference.sequent())
.map(|p| inference.sequent()[p].occ())
.collect();
let (goals, hypotheses): (Vec<OccId>, Vec<OccId>) = written
.into_iter()
.partition(|&o| reading.position(o) == Side::Output);
assert_eq!(goals.len(), 1, "{text:?}: {printed:?}");
let read = back.reading();
assert_eq!(
formulas(&read, &mut read.hypotheses()),
formulas(reading, &mut hypotheses.into_iter()),
"{text:?}: {printed:?}"
);
assert_eq!(
read.formula(read.goal()).to_string(),
reading.formula(goals[0]).to_string(),
"{text:?}: {printed:?}"
);
#[cfg(feature = "interactive")]
{
cuts += usize::from(inference.cut().is_some());
}
inferences += 1;
}
}
assert!(inferences > 200, "{inferences} inferences");
#[cfg(feature = "interactive")]
assert!(cuts > 50, "{cuts} cuts");
}
#[cfg(all(
feature = "latex",
feature = "typst",
feature = "svg",
feature = "rocq",
feature = "interactive"
))]
const CLASSICAL: [&str; 8] = ["~", "⅋", "⊥", "?", r"\parr", r"\bot", r"\wn", "perp"];
#[cfg(all(
feature = "latex",
feature = "typst",
feature = "svg",
feature = "rocq",
feature = "interactive"
))]
fn intuitionistic(sequent: &str, what: &str, out: &str) {
let out = out.replace("<?xml", "").replace("?>", "");
let rocq = out.contains("Lemma certificate");
let comments: String = out
.lines()
.filter(|line| !rocq || line.starts_with("(*"))
.collect::<Vec<_>>()
.join("\n");
for symbol in CLASSICAL {
assert!(
!comments.contains(symbol),
"{sequent:?}: {what} writes {symbol:?}:\n{out}"
);
}
if rocq {
for word in ["parr", "wn ", "dual", " ll "] {
assert!(
!out.contains(word),
"{sequent:?}: {what} writes {word:?}:\n{out}"
);
}
}
}
#[cfg(all(
feature = "latex",
feature = "typst",
feature = "svg",
feature = "rocq",
feature = "interactive"
))]
#[test]
fn no_intuitionistic_output_writes_a_classical_symbol() {
use crate::export::{Styles, latex, rocq, svg, typst};
use crate::linear::nets::{Criterion, MellStructure, ProofStructure};
use crate::linear::proofs::Node;
use crate::linear::search::Verdict;
use crate::linear::{Interactive, Proof};
let styles = Styles::default();
let limits = Limits::default();
let options = search::Options::default();
let essential = styles.svg.clone().with_essential(true);
let criterion = Criterion::of(Mode::INTUITIONISTIC).unwrap();
let mode = Mode::INTUITIONISTIC;
let mut seen = [0; 4];
let mut rng = Rng::new(4400);
for rules in IllRules::ALL {
for _ in 0..6 {
let budget = 2 + rng.below(8);
let mut ill = generate::ill(&mut rng, rules, 3, budget);
let provable = generate::two_sided(&ill.hypotheses, &ill.goal);
let mutated =
generate::mutate_two_sided(&mut rng, &mut ill.hypotheses, &mut ill.goal, 3)
.then(|| generate::two_sided(&ill.hypotheses, &ill.goal));
for text in std::iter::once(provable).chain(mutated) {
let check = |what: &str, out: &str| intuitionistic(&text, what, out);
let sequent: IllSequent = text.parse().unwrap();
check("the sequent", &sequent.to_string());
let session = Interactive::new(sequent.sequent(), mode).unwrap();
for goal in session.goals() {
for &m in session.goal(goal).unwrap() {
check("a goal's formula", &session.formula(m).to_string());
}
}
let outcome = search::prove(sequent.sequent(), mode, &options).unwrap();
match &outcome.verdict {
Verdict::Proved(proof) => {
seen[0] += 1;
let derivation = proof.derivation().unwrap();
check("the text tree", &derivation.to_string());
let mut out = String::new();
latex::write(&derivation, &styles.latex, &mut out, |_| false).unwrap();
check("LaTeX", &out);
out.clear();
typst::write(&derivation, &styles.typst, &mut out, |_| false).unwrap();
check("Typst", &out);
out.clear();
svg::write(&derivation, &styles.svg, &mut out, |_| false).unwrap();
check("SVG", &out);
out.clear();
rocq::write(&derivation, &styles.rocq, &mut out, |_| false).unwrap();
check("Rocq", &out);
for m in proof.forest().root_members() {
check("a formula of the proof", &proof.formula(m).to_string());
}
let fragment = proof.sequent().fragment();
if crate::linear::nets::exist(fragment, mode).is_ok() {
let net =
ProofStructure::from_proof(proof, criterion, &limits, |_| {
false
})
.unwrap();
check("the net", &net.written_in(mode).to_string());
let drawn = svg::net(&net, &essential, &limits, |_| false).unwrap();
check("the net drawn", &drawn);
seen[2] += 1;
} else if MellStructure::exist(fragment, mode).is_ok() {
let net =
MellStructure::from_proof(proof, criterion, &limits, |_| false)
.unwrap();
check("the net", &net.written_in(mode).to_string());
let drawn =
svg::mell_net(&net, &essential, &limits, |_| false).unwrap();
check("the net drawn", &drawn);
seen[2] += 1;
}
let mut nodes = proof.nodes().to_vec();
if let Some(n) = nodes.iter().position(|n| matches!(n, Node::Ax(..))) {
let Node::Ax(a, _) = nodes[n] else {
unreachable!()
};
nodes[n] = Node::Ax(a, a);
let broken =
Proof::new(proof.forest().clone(), nodes, proof.root())
.unwrap()
.with_mode(mode);
let error = broken.check(mode).unwrap_err();
check("a refused proof", &error.describe(&broken).to_string());
seen[3] += 1;
}
}
Verdict::Unprovable(disproof) => {
seen[1] += 1;
check("the refutation", &disproof.to_string());
let mut out = String::new();
if rocq::write_disproof(disproof, &styles.rocq, &mut out).is_ok() {
check("the refutation's certificate", &out);
}
}
Verdict::Unknown(_) => {}
}
}
}
}
assert!(seen.iter().all(|&n| n > 5), "{seen:?}");
}
#[cfg(feature = "serialize")]
#[test]
fn the_json_form() {
let sequent: IllSequent = "A -o B, top |- 0 & B".parse().unwrap();
let json = serde_json::to_string(&sequent).unwrap();
assert_eq!(
json,
r#"{"version":5,"terms":[{"V":0},{"V":1},{"⊸":[0,1]},"⊤","0",{"&":[4,1]}],"atoms":["A","B"],"hypotheses":[2,3],"goal":5}"#
);
let back: IllSequent = serde_json::from_str(&json).unwrap();
assert_eq!(back, sequent);
for text in generated(4300, 10) {
let sequent: IllSequent = text.parse().unwrap();
let json = serde_json::to_string(&sequent).unwrap();
let back: IllSequent = serde_json::from_str(&json).unwrap();
assert_eq!(back.to_string(), sequent.to_string(), "{json}");
let reading = Reading::new(back.forest()).unwrap();
assert!(
back.forest()
.ids()
.all(|o| reading.position(o) == back.reading().position(o))
);
}
let read = |json: &str| {
let mut document = serde_json::Deserializer::from_str(json);
crate::wire::upgrade::<IllSequent, _>(&mut document, &Limits::default())
};
for tag in [r#"{"D":0}"#, r#"{"⅋":[0,0]}"#, r#"{"?":0}"#, r#""⊥""#] {
let json =
format!(r#"{{"terms":[{{"V":0}},{tag}],"atoms":["A"],"hypotheses":[],"goal":1}}"#);
assert!(
matches!(read(&json), Err(Error::Json { message, .. }) if message.contains("unknown variant")),
"{json}"
);
}
assert!(matches!(
read(r#"{"terms":[{"⊸":[1,1]},{"V":0}],"atoms":["A"],"hypotheses":[],"goal":0}"#),
Err(Error::NotTopological { .. })
));
assert!(matches!(
read(r#"{"terms":[{"V":0}],"atoms":["A"],"hypotheses":[3],"goal":0}"#),
Err(Error::IndexOutOfBounds { index: 3, .. })
));
let above = crate::wire::LEVEL + 1;
let json = format!(
r#"{{"version":{above},"terms":[{{"V":0}}],"atoms":["A"],"hypotheses":[],"goal":0}}"#
);
assert!(matches!(
read(&json),
Err(Error::Version { found, .. }) if found == u64::from(above)
));
}
}