#![cfg(feature = "serialize")]
use deduxit::linear::sequents::Visit;
use deduxit::linear::{Forest, Fragment, Member, Mode, Node, NodeId, Proof, Reading, Sequent};
const DEPTH: usize = 50_000;
const STACK: usize = 256 * 1024;
fn json(terms: &[String], roots: &[usize]) -> String {
let roots: Vec<String> = roots.iter().map(usize::to_string).collect();
format!(
r#"{{"version":1,"terms":["⊤",{{"D":0}},{{"V":0}},{}],"roots":[0,{}],"atoms":["a"]}}"#,
terms.join(","),
roots.join(",")
)
}
fn right_nested() -> String {
let terms: Vec<String> = (0..DEPTH)
.map(|i| format!(r#"{{"⅋":[1,{}]}}"#, i + 2))
.collect();
json(&terms, &[DEPTH + 2])
}
fn left_nested() -> String {
let terms: Vec<String> = (0..DEPTH)
.map(|i| match i % 2 {
0 => format!(r#"{{"⊗":[{},1]}}"#, i + 2),
_ => format!(r#"{{"⅋":[{},2]}}"#, i + 2),
})
.collect();
json(&terms, &[DEPTH + 2])
}
fn tower() -> String {
let below = |i: usize, leaf: usize, tower: usize| if i == 0 { leaf } else { tower + i - 1 };
let mut terms: Vec<String> = (0..DEPTH)
.map(|i| format!(r#"{{"?":{}}}"#, below(i, 1, 3)))
.collect();
terms.extend((0..DEPTH).map(|i| format!(r#"{{"!":{}}}"#, below(i, 2, DEPTH + 3))));
json(&terms, &[DEPTH + 2, 2 * DEPTH + 2])
}
fn entered<T>(walk: impl Iterator<Item = Visit<T>>) -> usize {
walk.filter(|visit| matches!(visit, Visit::Enter(_)))
.count()
}
fn walk(json: &str, fragment: Fragment) {
let sequent: Sequent = serde_json::from_str(json).unwrap();
assert_eq!(serde_json::to_string(&sequent).unwrap(), json);
assert_eq!(sequent.fragment(), fragment);
let mut optimized = sequent.clone();
optimized.optimize();
assert_eq!(optimized.terms().len(), sequent.terms().len());
let forest = Forest::new(&sequent).unwrap();
let deepest = forest.ids().map(|o| forest.depth(o)).max();
assert_eq!(deepest, Some(DEPTH as u32));
let formulas: Vec<String> = forest
.roots()
.iter()
.map(|&root| forest.formula(root).to_string())
.collect();
let printed = sequent.to_string();
assert!(printed.chars().count() > DEPTH);
assert_eq!(printed, format!("⊢ {}", formulas.join(", ")));
let reading = Reading::new(&forest).unwrap();
let goal = *forest.roots().last().unwrap();
assert_eq!(reading.goal(), goal);
let hypotheses: Vec<String> = reading
.hypotheses()
.map(|h| reading.formula(h).to_string())
.collect();
let two_sided = reading.to_string();
assert!(two_sided.chars().count() > DEPTH);
assert_eq!(
two_sided,
format!("{} ⊢ {}", hypotheses.join(", "), reading.formula(goal))
);
let occurrences = forest.ids().count();
let terms: usize = (sequent.roots().iter())
.map(|&root| entered(sequent.walk(root)))
.sum();
assert_eq!(terms, occurrences);
let read: usize = (forest.roots().iter())
.map(|&root| entered(reading.walk(root)))
.sum();
assert_eq!(read, occurrences);
#[cfg(feature = "latex")]
{
use deduxit::export::latex;
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC] {
let printed = latex::sequent(
&sequent,
mode,
&latex::Options::default(),
&deduxit::Limits::default(),
);
assert!(printed.unwrap().len() > DEPTH);
}
}
#[cfg(feature = "typst")]
{
use deduxit::export::typst;
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC] {
let printed = typst::sequent(
&sequent,
mode,
&typst::Options::default(),
&deduxit::Limits::default(),
);
assert!(printed.unwrap().len() > DEPTH);
}
}
#[cfg(feature = "svg")]
{
use deduxit::export::svg::{self, Style};
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC] {
let printed = svg::sequent(
&sequent,
mode,
&Style::default(),
&deduxit::Limits::default(),
);
assert!(printed.unwrap().len() > DEPTH);
}
}
let top = Node::Top(Member::from(forest.roots()[0]));
let proof = Proof::new(forest.clone(), vec![top], NodeId::new(0)).unwrap();
proof.check(Mode::CLASSICAL).unwrap();
let derivation = proof.derivation().unwrap();
assert!(derivation.to_string().ends_with(&printed));
let intuitionistic = proof.clone().with_mode(Mode::INTUITIONISTIC);
let term = intuitionistic.derivation().unwrap();
let term = term.term(&deduxit::Limits::default(), |_| false).unwrap();
let options = deduxit::lambda::Options::default().with_types(true);
let mut written = String::new();
let unbounded = deduxit::Limits::default().with_derivation_bytes(None);
term.write_judgement(&mut written, &options, &unbounded, |_| false)
.unwrap();
assert!(written.chars().count() > DEPTH);
#[cfg(feature = "rocq")]
{
use deduxit::export::rocq::{self, Options};
let mut certificate = String::new();
rocq::write(&derivation, &Options::default(), &mut certificate, |_| {
false
})
.unwrap();
assert!(certificate.len() > DEPTH);
}
}
#[test]
fn deep_formulas_need_no_stack() {
let walks = std::thread::Builder::new().stack_size(STACK).spawn(|| {
let nested = Fragment::MULTIPLICATIVES | Fragment::ADDITIVE_UNITS;
walk(&right_nested(), nested);
walk(&left_nested(), nested);
walk(&tower(), Fragment::EXPONENTIALS | Fragment::ADDITIVE_UNITS);
});
walks.unwrap().join().unwrap();
}
#[cfg(feature = "parse")]
fn ordinary(text: &str, unicode: &str) {
use deduxit::ordinary::{Logic, Translation, translate};
let sequent: deduxit::ordinary::Sequent = text.parse().unwrap();
assert!(sequent.to_string() == format!("⊢ {unicode}"), "printed");
for &translation in Translation::ALL {
let logic = match translation {
Translation::Affine => Logic::Classical,
_ => Logic::Intuitionistic,
};
let image = translate(&sequent, logic, translation, &deduxit::Limits::default()).unwrap();
assert!(image.sequent().to_string().starts_with('⊢'));
}
}
#[cfg(feature = "parse")]
#[test]
fn deep_ordinary_formulas_need_no_stack() {
let walks = std::thread::Builder::new().stack_size(STACK).spawn(|| {
let negations = format!("{}a", "~".repeat(DEPTH));
ordinary(&negations, &negations.replace('~', "¬"));
let nested = DEPTH - 1;
let implications = format!("{}a -> a{}", "a -> (".repeat(nested), ")".repeat(nested));
ordinary(&implications, &implications.replace("->", "→"));
});
walks.unwrap().join().unwrap();
}