#![cfg(all(feature = "parse", feature = "serialize", feature = "interactive"))]
use deduxit::linear::proofs::Fault;
use deduxit::linear::proofs::interactive::{GoalId, Needs, StepError, TermNode, Witness};
use deduxit::linear::search::Engine;
use deduxit::{
Error, Limits,
linear::{
CheckError, Criterion, CutFormula, Disproof, Eigen, Forest, InputOptions, Interactive,
Member, Mode, Options, Proof, ProofStructure, Rule, Sequent, Step, Verdict,
},
};
#[test]
fn the_focused_engine_takes_a_quantified_goal_and_no_other() {
let sequent: Sequent = "forall x. p(x) |- p(a)".parse().unwrap();
assert_eq!(sequent.fragment().to_string(), "MLL1");
for mode in [
Mode::CLASSICAL,
Mode::INTUITIONISTIC,
Mode::CLASSICAL.with_mix(),
Mode::INTUITIONISTIC.with_affine(),
] {
let focused = if mode.is_intuitionistic() {
Engine::TwoSided
} else {
Engine::Focus
};
let outcome = deduxit::linear::prove(&sequent, mode, &Options::default()).unwrap();
assert!(matches!(outcome.verdict, Verdict::Proved(_)), "{mode}");
assert_eq!(outcome.engine, focused);
for &engine in Engine::ALL {
let options = Options::default().with_engine(Some(engine));
match deduxit::linear::prove(&sequent, mode, &options) {
Ok(outcome) if engine == focused => {
assert!(matches!(outcome.verdict, Verdict::Proved(_)), "{mode}");
}
Err(Error::EngineRefused { .. }) => {}
other => panic!("{engine} in {mode}: {other:?}"),
}
}
}
let cyclic = Sequent::parse_ordered(
"forall x. p(x) |- p(a)",
deduxit::linear::Order::Cyclic,
&Limits::default(),
)
.unwrap();
let error = deduxit::linear::prove(&cyclic, Mode::CYCLIC, &Options::default()).unwrap_err();
assert!(matches!(error, Error::OrderedFragment { .. }), "{error}");
let ground: Sequent = "p(a), p(a) -o q(f(a)) |- q(f(a))".parse().unwrap();
let outcome =
deduxit::linear::prove(&ground, Mode::INTUITIONISTIC, &Options::default()).unwrap();
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert_eq!(outcome.fragment.to_string(), "MLL");
}
#[test]
fn the_views_refuse_a_quantified_sequent_and_the_checker_judges_it() {
let sequent: Sequent = "forall x. p(x) |- p(a)".parse().unwrap();
let json = format!(
r#"{{"version":7,"sequent":{},"nodes":[{{"ax":[1,2]}}],"mode":"classical"}}"#,
serde_json::to_string(&sequent).unwrap()
);
let proof: Proof = serde_json::from_str(&json).unwrap();
let Err(CheckError::Invalid(invalid)) = proof.check(Mode::CLASSICAL) else {
panic!("an open atom named bare is no instance");
};
assert!(
matches!(invalid.fault, Fault::Instance { member, .. } if member == Member::new(1)),
"{invalid:?}"
);
let forest = Forest::new(&sequent).unwrap();
let error = ProofStructure::new(forest, Criterion::default()).unwrap_err();
assert!(matches!(error, Error::Net(_)), "{error}");
let json = format!(
r#"{{"version":7,"sequent":{},"mode":"classical","refutation":{{"kind":"exhausted"}}}}"#,
serde_json::to_string(&sequent).unwrap()
);
let disproof: Disproof = serde_json::from_str(&json).unwrap();
let error = disproof.check().unwrap_err();
assert!(matches!(error, Error::Refutation(_)), "{error}");
}
#[test]
fn a_session_refuses_a_quantifier_on_every_path() {
let sequent: Sequent = "forall x. p(x) |- p(a)".parse().unwrap();
let json = format!(
r#"{{"version":7,"sequent":{},"mode":"classical","inferences":[{{"sequent":[0,2],"rule":"∃","principal":0,"premises":[1]}},{{"sequent":[1,2]}}],"history":[0]}}"#,
serde_json::to_string(&sequent).unwrap()
);
let error = serde_json::from_str::<Interactive>(&json).unwrap_err();
assert!(error.to_string().contains("instance"), "{error}");
let limits = Limits::default();
let input = InputOptions::default();
let mut session = Interactive::new(&"a |- a".parse().unwrap(), Mode::CLASSICAL).unwrap();
let goal = session.goals().next().unwrap();
let formula =
CutFormula::parse_within("forall x. p(x)", Mode::CLASSICAL, &input, &limits).unwrap();
let before = serde_json::to_string(&session).unwrap();
session.cut(goal, &formula, &[], &limits).unwrap();
let json = serde_json::to_string(&session).unwrap();
assert!(json.contains(r#""instances":"#), "{json}");
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
assert_eq!(session.undo(), Some(goal));
assert_eq!(serde_json::to_string(&session).unwrap(), before);
let mut quantified = Interactive::new(&sequent, Mode::CLASSICAL).unwrap();
let root = quantified.goals().next().unwrap();
let ground = CutFormula::parse_within("q(b)", Mode::CLASSICAL, &input, &limits).unwrap();
let error = quantified.cut(root, &ground, &[], &limits).unwrap_err();
assert!(
matches!(&error, Error::Step(StepError::CutSymbol { name, .. }) if name == "b"),
"{error}"
);
let formula = CutFormula::parse_within("p(b)", Mode::CLASSICAL, &input, &limits).unwrap();
session.cut(goal, &formula, &[], &limits).unwrap();
let json = serde_json::to_string(&session).unwrap();
assert!(json.starts_with(r#"{"version":7,"#), "{json}");
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
}
#[test]
fn adding_sequents_joins_their_tables() {
let mut s: Sequent = "|- q, p(a)".parse().unwrap();
s.add("|- ~q, p(f(a))".parse().unwrap());
assert_eq!(s.to_string(), "⊢ q, p(a), ~q, p(f(a))");
assert_eq!(s.atom_names(), ["q", "p(a)", "p(f(a))"]);
let json = serde_json::to_string(&s).unwrap();
assert_eq!(serde_json::from_str::<Sequent>(&json).unwrap(), s);
let mut t: Sequent = "|- ~q".parse().unwrap();
t.add("|- q, p(a)".parse().unwrap());
assert_eq!(t.atom_names(), ["q", "p(a)"]);
let cyclic = Sequent::parse_ordered(
"p(a) |- p(a)",
deduxit::linear::Order::Cyclic,
&Limits::default(),
)
.unwrap();
let outcome = deduxit::linear::prove(&cyclic, Mode::CYCLIC, &Options::default()).unwrap();
let net = outcome.net.expect("a net");
assert!(
serde_json::to_string(&net)
.unwrap()
.starts_with(r#"{"version":7,"#)
);
}
#[test]
fn the_written_proofs_read_back_and_are_judged() {
let accepted = [
"apart",
"cut",
"cut_deep",
"cut_deep_ill",
"cut_ill",
"cut_instance",
"cut_shared",
"cut_shared_ill",
"cut_tensor",
"cut_tensor_ill",
"swap",
"swap_ill",
"unintroduced",
"witness",
"witness_ill",
];
let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/first-order");
let mut read = 0;
for entry in std::fs::read_dir(dir).unwrap() {
let path = entry.unwrap().path();
let name = path.file_stem().unwrap().to_str().unwrap().to_owned();
let json = std::fs::read_to_string(&path).unwrap();
let proof: Proof = serde_json::from_str(&json).unwrap();
let mode = proof.mode().unwrap_or(Mode::CLASSICAL);
let mode = if name.starts_with("apart") || name.starts_with("shared") {
mode.with_affine()
} else {
mode
};
let result = proof.check(mode);
if accepted.contains(&name.as_str()) {
assert_eq!(result, Ok(()), "{name}");
} else {
let error = result.expect_err(&name);
assert!(matches!(error, CheckError::Invalid(_)), "{name}: {error}");
let message = error.describe(&proof).to_string();
assert!(message.starts_with("node "), "{name}: {message}");
}
read += 1;
}
assert_eq!(read, 22);
let json = std::fs::read_to_string(
std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/first-order/swap_back.json"),
)
.unwrap();
let proof: Proof = serde_json::from_str(&json).unwrap();
let error = proof.check(Mode::CLASSICAL).unwrap_err();
assert_eq!(
error.describe(&proof).to_string(),
"node 4 (∃ on ∃x. (∀y. p(x, y)) from 3) with premises ⊢ ∃y. (∀x. ~p(x, y)), \
∀y. p(a, y): eigenvariable a occurs outside the ∀ step that introduces it"
);
}
#[test]
fn the_written_cuts_are_eliminated() {
use deduxit::linear::proofs::cut::{self, Case, End};
let dir = std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/first-order");
let mut cases: Vec<Case> = Vec::new();
for name in [
"cut",
"cut_ill",
"cut_instance",
"cut_shared",
"cut_shared_ill",
"cut_tensor",
"cut_tensor_ill",
"cut_deep",
"cut_deep_ill",
] {
let json = std::fs::read_to_string(dir.join(format!("{name}.json"))).unwrap();
let proof: Proof = serde_json::from_str(&json).unwrap();
assert!(!proof.is_cut_free(), "{name}");
let mode = proof.mode().unwrap_or(Mode::CLASSICAL);
let mut taken = 0;
let elimination = cut::eliminate(
&proof,
mode,
None,
&cut::Options::default(),
&Limits::default(),
|_| false,
|before, step| {
assert!(before.check(mode).is_ok(), "{name}: step {taken}");
cases.push(step.case);
taken += 1;
},
)
.unwrap();
assert_eq!(elimination.end, End::CutFree, "{name}");
assert_eq!(elimination.steps.len(), taken, "{name}");
assert!(elimination.proof.is_cut_free(), "{name}");
assert_eq!(elimination.proof.check(mode), Ok(()), "{name}");
assert_eq!(
elimination.proof.sequent().to_string(),
proof.sequent().to_string()
);
let net =
ProofStructure::from_proof(&proof, Criterion::default(), &Limits::default(), |_| false);
assert!(net.is_err(), "{name}");
}
for case in [
Case::ForallExists,
Case::TensorPar,
Case::Axiom,
Case::Commutative,
] {
assert!(cases.contains(&case), "{case:?} not met");
}
}
#[test]
fn the_term_limit_refuses_at_every_reader() {
let text = "|- p(f(f(a)))";
let sequent: Sequent = text.parse().unwrap();
assert_eq!(sequent.fo_size(), 3);
let tight = Limits::default().with_terms(Some(2));
let error = Sequent::parse_within(text, &tight).unwrap_err();
assert_eq!(error.code(), "too_many_terms", "{error}");
assert!(Sequent::parse_within(text, &Limits::default().with_terms(Some(3))).is_ok());
let json = serde_json::to_string(&sequent).unwrap();
let mut document = serde_json::Deserializer::from_str(&json);
let error = deduxit::wire::upgrade::<Sequent, _>(&mut document, &tight).unwrap_err();
assert_eq!(error.code(), "too_many_terms", "{error}");
let json = std::fs::read_to_string(
std::path::Path::new(env!("CARGO_MANIFEST_DIR")).join("tests/first-order/swap.json"),
)
.unwrap();
let proof: Proof = serde_json::from_str(&json).unwrap();
assert_eq!(proof.instances().unwrap().len(), 4);
assert_eq!(proof.sequent().fo_size(), 4);
let limits = Limits::default().with_terms(Some(5));
let mut document = serde_json::Deserializer::from_str(&json);
let error = deduxit::wire::upgrade::<Proof, _>(&mut document, &limits).unwrap_err();
assert_eq!(error.code(), "too_many_terms", "{error}");
assert_eq!(error.setting(), Some("limits.terms"));
}
#[test]
fn a_cut_formula_with_a_loose_variable_is_refused() {
let json = r#"{"version":7,"sequent":{"terms":[{"V":0},{"∀":0},"⊤",{"D":0},{"∃":3}],"roots":[2],"atoms":[{"P":[0,[0]]}],"symbols":[["p",1]],"fo":[{"B":1}],"binders":["x","x"],"antecedents":0,"cuts":[1]},"nodes":[{"ax":[5,6]}],"instances":{"members":[[2,0],[4,0]],"frames":[[null,1]],"terms":[{"E":0}]}}"#;
let error = serde_json::from_str::<Proof>(json).unwrap_err();
assert!(error.to_string().contains("bound variable"), "{error}");
}
fn decided(text: &str, mode: Mode, options: &Options) -> Option<bool> {
let sequent: Sequent = text.parse().unwrap();
let outcome = deduxit::linear::prove(&sequent, mode, options).unwrap();
let engine = if mode.is_intuitionistic() {
Engine::TwoSided
} else {
Engine::Focus
};
assert_eq!(outcome.engine, engine, "{text}");
match outcome.verdict {
Verdict::Proved(proof) => {
assert_eq!(proof.check(mode), Ok(()), "{text}");
assert!(proof.instances().is_some(), "{text}");
Some(true)
}
Verdict::Unprovable(_) => Some(false),
Verdict::Unknown(_) => None,
}
}
#[test]
fn the_memo_and_the_loop_check_key_first_order_sequents() {
let looping = [
"!(forall x. (p(x) -o p(x))), !(q -o r), !(r -o q), p(e) |- r",
"!(a -o a), !(b -o c), !(c -o b), a |- forall z. c",
];
let options = Options::default().with_copies(Some(6));
for text in looping {
let outcome =
deduxit::linear::prove(&text.parse().unwrap(), Mode::INTUITIONISTIC, &options).unwrap();
assert!(matches!(outcome.verdict, Verdict::Unprovable(_)), "{text}");
assert!(outcome.statistics.memo_hits > 0, "{text}");
let unkeyed = options.clone().with_memo_limit(0);
let outcome =
deduxit::linear::prove(&text.parse().unwrap(), Mode::INTUITIONISTIC, &unkeyed).unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(_)), "{text}");
}
let proved = "!(forall x. (p(x) -o p(x))), !(forall x. (p(x) -o q(x))), p(e) |- q(e)";
assert_eq!(decided(proved, Mode::INTUITIONISTIC, &options), Some(true));
}
#[test]
fn a_part_asked_about_leaves_no_binding() {
let text = "|- exists x. ((~a(s) * 1) par a(x) par (~a(t) + 1))";
let mix = Mode::CLASSICAL.with_mix();
assert_eq!(decided(text, mix, &Options::default()), Some(true));
assert_eq!(
decided(text, mix, &Options::default().with_memo_limit(0)),
Some(true)
);
}
#[test]
fn the_focused_engine_decides_first_order_sequents() {
let (classical, mix, affine) = (
Mode::CLASSICAL,
Mode::CLASSICAL.with_mix(),
Mode::CLASSICAL.with_affine(),
);
let options = Options::default();
for (text, mode, expected) in [
("forall x. p(x) |- p(a)", classical, true),
("forall x. p(x) |- exists y. p(y)", classical, true),
("exists x. p(x) |- forall y. p(y)", classical, false),
(
"exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)",
classical,
true,
),
(
"forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)",
classical,
false,
),
(
"p(a) & p(b), q(b) |- exists x. (p(x) * q(x))",
classical,
true,
),
(
"p(b) & p(a), q(b) |- exists x. (p(x) * q(x))",
classical,
true,
),
(
"p(a) & p(b), q(c) |- exists x. (p(x) * q(x))",
classical,
false,
),
("|- exists x. (~p(x) par p(f(x)))", classical, false),
("|- forall y. exists x. (~p(x) par p(y))", classical, true),
("|- exists x. forall y. (~p(x) par p(y))", classical, false),
("forall x. (p(x) & q(x)) |- p(a) & q(a)", classical, true),
("forall x. p(x) |- p(a) * p(b)", classical, false),
("!forall x. p(x) |- p(a) * p(b)", classical, true),
(
"p(z), !forall x. (p(x) -o p(s(x))) |- p(s(s(s(z))))",
classical,
true,
),
(
"|- exists x. (p(x) * q(x)), ~p(a), ~q(a), r, ~r",
classical,
false,
),
("|- exists x. (p(x) * q(x)), ~p(a), ~q(a), r, ~r", mix, true),
("forall x. p(x), q(b) |- p(a)", affine, true),
("forall x. p(x) |- q(a)", affine, false),
] {
assert_eq!(
decided(text, mode, &options),
Some(expected),
"{text} in {mode}"
);
}
}
#[test]
fn the_two_sided_engine_decides_first_order_sequents() {
let (linear, affine) = (Mode::INTUITIONISTIC, Mode::INTUITIONISTIC.with_affine());
let options = Options::default();
for (text, mode, expected) in [
("forall x. p(x) |- exists y. p(y)", linear, true),
("exists x. p(x) |- p(a)", linear, false),
(
"exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)",
linear,
true,
),
(
"forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)",
linear,
false,
),
(
"exists x. (p(x) * q(x)) |- exists y. (q(y) * p(y))",
linear,
true,
),
("forall x. (p(x) -o q(x)), p(a) |- q(a)", linear, true),
("forall x. (p(x) -o q(x)), p(a) |- q(b)", linear, false),
("p(a) & p(b), q(b) |- exists x. (p(x) * q(x))", linear, true),
(
"p(a) & p(b), q(c) |- exists x. (p(x) * q(x))",
linear,
false,
),
(
"p(z), !forall x. (p(x) -o p(s(x))) |- p(s(s(z)))",
linear,
true,
),
(
"exists x. (p(x) -o q) |- (forall x. p(x)) -o q",
linear,
true,
),
(
"(forall x. p(x)) -o q |- exists x. (p(x) -o q)",
linear,
false,
),
("forall x. p(x), q(b) |- p(a)", affine, true),
("forall x. p(x) |- q(a)", affine, false),
] {
assert_eq!(
decided(text, mode, &options),
Some(expected),
"{text} in {mode}"
);
}
}
#[test]
fn a_premise_gives_its_answers_in_turn() {
let options = Options::default();
for (goal, provable) in [("q(a4)", true), ("q(b)", false)] {
let ill = format!(
"p(a1), p(a2), p(a3), p(a4), {goal} |- exists x. (p(x) * q(x)) * exists x. p(x) * exists x. p(x) * exists x. p(x)"
);
assert_eq!(
decided(&ill, Mode::INTUITIONISTIC, &options),
Some(provable),
"{ill}"
);
let one_sided = format!(
"|- ~p(a1), ~p(a2), ~p(a3), ~p(a4), ~{goal}, exists x. (p(x) * q(x)) * exists x. p(x) * exists x. p(x) * exists x. p(x)"
);
assert_eq!(
decided(&one_sided, Mode::CLASSICAL, &options),
Some(provable),
"{one_sided}"
);
}
}
#[test]
fn the_first_order_families_have_their_verdicts() {
for n in 1..=5 {
let alternatives: Vec<String> = (1..=n).map(|i| format!("p(a{i})")).collect();
let choice = alternatives.join(" & ");
for k in 1..=n {
let text = format!("{choice}, q(a{k}) |- exists x. (p(x) * q(x))");
assert_eq!(
decided(&text, Mode::CLASSICAL, &Options::default()),
Some(true),
"{text}"
);
}
let text = format!("{choice}, q(b) |- exists x. (p(x) * q(x))");
assert_eq!(
decided(&text, Mode::CLASSICAL, &Options::default()),
Some(false),
"{text}"
);
}
for n in 1..=4u32 {
let mut goal = "z".to_owned();
for _ in 0..n {
goal = format!("s({goal})");
}
let text = format!("p(z), !forall x. (p(x) -o p(s(x))) |- p({goal})");
let options = |copies| Options::default().with_copies(Some(copies));
assert_eq!(
decided(&text, Mode::CLASSICAL, &options(n)),
Some(true),
"{text}"
);
assert_eq!(
decided(&text, Mode::CLASSICAL, &options(n - 1)),
None,
"{text}"
);
}
}
#[test]
fn a_first_order_search_counts_its_unifications() {
let counted = |text: &str, mode: Mode| {
let sequent: Sequent = text.parse().unwrap();
deduxit::linear::prove(&sequent, mode, &Options::default())
.unwrap()
.statistics
};
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC] {
let statistics = counted("p(a), p(b) & q(c) |- exists x. (p(x) * p(b))", mode);
assert!(statistics.unifications >= 2, "{mode}: {statistics:?}");
assert!(statistics.bindings >= 1, "{mode}: {statistics:?}");
}
let statistics = counted("a, b |- a * b", Mode::CLASSICAL);
assert_eq!((statistics.unifications, statistics.bindings), (0, 0));
let written = serde_json::to_value(statistics).unwrap();
assert!(written.get("unifications").is_none() && written.get("bindings").is_none());
}
#[test]
fn the_first_order_bounds_stop_the_search() {
use deduxit::linear::Reason;
let deep = "|- exists x. p(x), ~p(f(f(f(a))))";
let outcome = |text: &str, options: &Options| {
deduxit::linear::prove(&text.parse().unwrap(), Mode::CLASSICAL, options)
.unwrap()
.verdict
};
let depth = |d| Options::default().with_witness_depth(d);
let Verdict::Unknown(reason) = outcome(deep, &depth(2)) else {
panic!("{deep} past the witness depth");
};
assert!(matches!(reason, Reason::WitnessDepth { depth: 2, .. }));
assert_eq!(reason.setting(), Some("search.witness_depth"));
assert!(matches!(outcome(deep, &depth(3)), Verdict::Proved(_)));
let two = "|- exists x. exists y. (p(x) * p(y)), ~p(a), ~p(b)";
let instances = |n| Options::default().with_instances(n);
let Verdict::Unknown(reason) = outcome(two, &instances(1)) else {
panic!("{two} past the instances");
};
assert!(matches!(reason, Reason::Instances { instances: 1, .. }));
assert_eq!(reason.setting(), Some("search.instances"));
assert!(matches!(outcome(two, &instances(2)), Verdict::Proved(_)));
let cut = "exists x. p(x), exists x. !p(x) |- q";
let limits = Limits::default().with_work(Some(1 << 20));
for mode in [Mode::CLASSICAL, Mode::INTUITIONISTIC] {
let options = instances(1).with_copies(None);
let outcome =
deduxit::linear::prove_within(&cut.parse().unwrap(), mode, &options, &limits, |_| {
false
})
.unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(_)), "{mode}");
}
}
#[test]
fn the_counts_refute_first_order_sequents() {
use deduxit::linear::Refutation;
let refuted = |text: &str| {
let sequent: Sequent = text.parse().unwrap();
match deduxit::linear::prove(&sequent, Mode::CLASSICAL, &Options::default())
.unwrap()
.verdict
{
Verdict::Unprovable(disproof) => *disproof,
other => panic!("{text}: {other:?}"),
}
};
let symbol = refuted("forall x. p(x), p(a) |- p(b)");
assert!(
matches!(symbol.refutation(), Refutation::UnbalancedSymbol(_)),
"{symbol:?}"
);
assert_eq!(symbol.check(), Ok(()));
assert!(
symbol
.to_string()
.contains("p(…) occurs 1 more time on the left than on the right"),
"{symbol}"
);
let json = serde_json::to_string(&symbol).unwrap();
assert!(json.contains("\"kind\":\"unbalanced_symbol\""), "{json}");
let read: Disproof = serde_json::from_str(&json).unwrap();
assert_eq!(read.check(), Ok(()));
let atom = refuted("forall x. p(x) |- p(a) * q(b)");
assert!(
matches!(atom.refutation(), Refutation::Unbalanced(_)),
"{atom:?}"
);
assert_eq!(atom.check(), Ok(()));
let equation = refuted("forall x. (p(x) * q(x)) |- p(a) par q(a)");
assert!(
matches!(equation.refutation(), Refutation::Equation(_)),
"{equation:?}"
);
assert_eq!(equation.check(), Ok(()));
let open = refuted("|- exists x. forall y. (~p(x) par p(y))");
assert!(
matches!(open.refutation(), Refutation::Exhausted),
"{open:?}"
);
}
#[test]
fn a_deep_witness_closes_without_recursion() {
let n = 100_000;
let text = format!(
"|- forall z. (~p({}z{}) par (exists y. p(y)))",
"f(".repeat(n),
")".repeat(n)
);
let options = Options::default().with_witness_depth(u32::MAX);
assert_eq!(decided(&text, Mode::CLASSICAL, &options), Some(true));
}
#[test]
fn a_deep_unification_is_counted_work() {
use deduxit::linear::Reason;
let deep = format!("{}z{}", "f(".repeat(2000), ")".repeat(2000));
let literals: Vec<String> = (0..6).map(|i| format!("~p(g{i}({deep}))")).collect();
let text = format!(
"|- forall z. ({} par ~q(a) par (exists y. (p(y) * q(y))))",
literals.join(" par ")
);
let sequent: Sequent = text.parse().unwrap();
let options = Options::default().with_witness_depth(u32::MAX);
let limits = Limits::default().with_work(Some(20_000));
let outcome = deduxit::linear::prove_within(
&sequent,
Mode::CLASSICAL.with_affine(),
&options,
&limits,
|_| false,
)
.unwrap();
assert!(
matches!(outcome.verdict, Verdict::Unknown(Reason::WorkLimit { .. })),
"{:?}",
outcome.verdict
);
}
#[test]
fn the_first_order_keys_are_charged_and_counted() {
use deduxit::linear::Reason;
let tower = |height: usize, inner: String| {
(0..height).rev().fold(inner, |body, i| {
format!("exists x{i}. (forall y{i}. {body})")
})
};
let literals: Vec<String> = (0..150).map(|t| format!("q{t}(x39, y39)")).collect();
let duals: Vec<String> = (0..150).map(|t| format!("~q{t}(a, b)")).collect();
let wide = format!(
"|- {}, {}, ~r",
tower(
40,
format!("({} par {})", literals.join(" par "), tower(60, "r".into()))
),
duals.join(", ")
);
let limits = Limits::default()
.with_memory_bytes(Some(2 << 20))
.with_work(Some(500_000));
let outcome = deduxit::linear::prove_within(
&wide.parse().unwrap(),
Mode::CLASSICAL.with_mix(),
&Options::default(),
&limits,
|_| false,
)
.unwrap();
assert!(
matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { .. })
),
"{:?}",
outcome.verdict
);
let variables: Vec<String> = (0..100).map(|i| format!("x{i}")).collect();
let high = format!(
"|- {}, ~p({}, b)",
tower(100, format!("p({}, x0)", variables.join(", "))),
vec!["a"; 100].join(", ")
);
let work = |memo_limit| {
let options = Options::default().with_memo_limit(memo_limit);
let outcome =
deduxit::linear::prove(&high.parse().unwrap(), Mode::CLASSICAL, &options).unwrap();
assert!(matches!(outcome.verdict, Verdict::Unprovable(_)));
outcome.statistics.work
};
assert!(work(1 << 20) > 2 * work(0));
}
#[test]
fn a_deep_witness_is_one_word_of_a_key() {
let n = 64;
let chain: Sequent = "p(z), !forall x. (p(x) -o p(s(x))) |- p(b)"
.parse()
.unwrap();
let work = move |memo_limit| {
let options = Options::default()
.with_copies(Some(n))
.with_witness_depth(n - 1)
.with_memo_limit(memo_limit);
let outcome = deduxit::linear::prove(&chain, Mode::CLASSICAL, &options).unwrap();
assert!(matches!(outcome.verdict, Verdict::Unknown(_)));
outcome.statistics.work
};
let works = std::thread::Builder::new()
.stack_size(Limits::default().stack_bytes())
.spawn(move || (work(1 << 20), work(0)))
.unwrap()
.join()
.unwrap();
assert!(works.0 * 20 < works.1 * 23, "{works:?}");
}
fn at(state: &Interactive, goal: GoalId, text: &str) -> usize {
let goal = state.goal(goal).unwrap();
goal.iter()
.position(|&m| state.formula(m).to_string() == text)
.unwrap_or_else(|| {
let shown: Vec<String> = goal.iter().map(|&m| state.formula(m).to_string()).collect();
panic!("no {text} among {shown:?}")
})
}
fn step(state: &mut Interactive, text: &str, rule: Rule, witness: Option<&str>) -> Vec<GoalId> {
let goal = state.goals().next().expect("an open goal");
let mut step = Step::new(at(state, goal, text), rule);
if let Some(witness) = witness {
step = step.with_witness(state.witness(witness).unwrap());
}
state.apply(goal, &step).unwrap()
}
#[test]
fn a_session_proves_with_the_quantifier_rules() {
let sequent: Sequent = "exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)"
.parse()
.unwrap();
let mode = Mode::INTUITIONISTIC;
let mut state = Interactive::new(&sequent, mode).unwrap();
let root = state.goals().next().unwrap();
let rules = state
.rules(root, at(&state, root, "∃y. (∀x. r(x, y))"))
.unwrap();
assert_eq!(rules[0].rule.to_string(), "∃L");
let given = Witness::Term(vec![TermNode::Eigen(Eigen::new(0))]);
let error = state
.apply(
root,
&Step::new(at(&state, root, "∃y. (∀x. r(x, y))"), Rule::Forall).with_witness(given),
)
.unwrap_err();
assert!(matches!(error, StepError::NoWitness { .. }), "{error}");
step(&mut state, "∃y. (∀x. r(x, y))", Rule::Forall, None);
step(&mut state, "∀x. (∃y. r(x, y))", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let rules = state.rules(goal, at(&state, goal, "∀x. r(x, a)")).unwrap();
assert_eq!(
(rules[0].rule.to_string(), rules[0].needs),
("∀L".to_owned(), Needs::Witness)
);
assert!(matches!(
state.witness("r(a)"),
Err(StepError::Witness { .. })
));
assert!(matches!(state.witness("c"), Err(StepError::Witness { .. })));
step(&mut state, "∀x. r(x, a)", Rule::Exists, None);
step(&mut state, "∃y. r(b, y)", Rule::Exists, Some("a"));
let goal = state.goals().next().unwrap();
let open: Vec<String> = state
.goal(goal)
.unwrap()
.iter()
.map(|&m| state.formula(m).to_string())
.collect();
assert_eq!(open, ["r($1, a)", "r(b, a)"]);
for text in ["|- r($1, a)", "|- $1", "r($1, a) |- r(b, a)"] {
assert!(text.parse::<Sequent>().is_err(), "{text}");
assert!(
text.parse::<deduxit::linear::IllSequent>().is_err(),
"{text}"
);
}
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
state.apply(goal, &Step::new(0, Rule::Ax)).unwrap();
assert!(state.is_complete());
let derivation = state.derivation().unwrap().to_string();
assert!(derivation.contains("r(b, a) ⊢ r(b, a)"), "{derivation}");
let json = serde_json::to_string(&state).unwrap();
assert!(json.contains(r#""bindings":"#), "{json}");
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
let proof = back.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
assert_eq!(state.undo(), Some(goal));
let open: Vec<String> = state
.goal(goal)
.unwrap()
.iter()
.map(|&m| state.formula(m).to_string())
.collect();
assert_eq!(open, ["r($1, a)", "r(b, a)"]);
state.apply(goal, &Step::new(0, Rule::Ax)).unwrap();
let proof = state.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
}
#[test]
fn a_session_keeps_the_eigenvariable_condition() {
let sequent: Sequent = "forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
step(&mut state, "∃y. (∀x. r(x, y))", Rule::Exists, None);
step(&mut state, "∀x. r(x, $1)", Rule::Forall, None);
step(&mut state, "∀x. (∃y. r(x, y))", Rule::Exists, Some("a"));
step(&mut state, "∃y. r(a, y)", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let error = state.apply(goal, &Step::new(0, Rule::Ax)).unwrap_err();
assert!(
matches!(&error, StepError::Eigenvariable { name, .. } if name == "b"),
"{error}"
);
let sequent: Sequent = "forall x. p(x), forall x. q(x) |- (forall x. p(x)) * (forall x. q(x))"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
let root = state.goals().next().unwrap();
let tensor = at(&state, root, "(∀x. p(x)) ⊗ (∀x. q(x))");
let left = at(&state, root, "∀x. p(x)");
let goals = state
.apply(root, &Step::new(tensor, Rule::Tensor).left(&[left]))
.unwrap();
let factor = state.goal(goals[0]).unwrap().len() - 1;
let opened = state
.apply(goals[0], &Step::new(factor, Rule::Forall))
.unwrap();
assert_eq!(opened.len(), 1);
let error = state
.apply(
goals[1],
&Step::new(at(&state, goals[1], "∀x. q(x)"), Rule::Exists)
.with_witness(state.witness("a").unwrap()),
)
.unwrap_err();
assert!(
matches!(&error, StepError::Eigenvariable { name, .. } if name == "a"),
"{error}"
);
}
#[test]
fn the_search_closes_a_session_goal() {
let (options, view, limits) = (
Options::default(),
deduxit::linear::ViewOptions::default(),
Limits::default(),
);
let mode = Mode::INTUITIONISTIC;
let sequent: Sequent = "forall x. p(x) |- p(f(a))".parse().unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∀x. p(x)", Rule::Exists, None);
let goal = state.goals().next().unwrap();
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
assert_eq!(closed.grafted, Ok(()));
assert!(state.is_complete());
let derivation = state.derivation().unwrap().to_string();
assert!(derivation.contains("p(f(a)) ⊢ p(f(a))"), "{derivation}");
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
assert_eq!(state.proof(&limits, |_| false).unwrap().check(mode), Ok(()));
assert_eq!(state.undo(), Some(goal));
let open: Vec<String> = state
.goal(goal)
.unwrap()
.iter()
.map(|&m| state.formula(m).to_string())
.collect();
assert_eq!(open, ["p(f(a))", "p($1)"]);
let sequent: Sequent = "exists y. forall x. r(x, y) |- forall x. exists y. r(x, y)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∃y. (∀x. r(x, y))", Rule::Forall, None);
step(&mut state, "∀x. (∃y. r(x, y))", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
assert!(state.is_complete());
assert_eq!(state.proof(&limits, |_| false).unwrap().check(mode), Ok(()));
let sequent: Sequent = "forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∃y. (∀x. r(x, y))", Rule::Exists, None);
step(&mut state, "∀x. r(x, $1)", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(
matches!(closed.outcome.verdict, Verdict::Unprovable(_)),
"{:?}",
closed.outcome.verdict
);
assert!(!state.is_complete());
let sequent: Sequent = "forall x. p(x) |- p(c)".parse().unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∀x. p(x)", Rule::Exists, Some("c"));
let goal = state.goals().next().unwrap();
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
assert_eq!(state.proof(&limits, |_| false).unwrap().check(mode), Ok(()));
let sequent: Sequent = "|- (exists x. p(x)) * bot".parse().unwrap();
let mut state = Interactive::new(&sequent, Mode::CLASSICAL).unwrap();
let goals = step(&mut state, "(∃x. p(x)) ⊗ ⊥", Rule::Tensor, None);
let bot = state.apply(goals[1], &Step::new(0, Rule::Bot)).unwrap();
let closed = state
.close(bot[0], &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Unprovable(_)));
}
#[test]
fn a_session_holds_deep_witnesses_and_bounds_its_table() {
let sequent: Sequent = "forall x. p(x) |- p(f(c))".parse().unwrap();
let symbol = |name: &str| {
let index = sequent
.symbols()
.iter()
.position(|(n, _)| n == name)
.unwrap();
deduxit::linear::sequents::Symbol::new(u32::try_from(index).unwrap())
};
let mut nodes = vec![TermNode::App(symbol("c"), vec![])];
for i in 0..100_000u32 {
nodes.push(TermNode::App(symbol("f"), vec![i]));
}
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
let root = state.goals().next().unwrap();
let position = at(&state, root, "∀x. p(x)");
let deep = Step::new(position, Rule::Exists).with_witness(Witness::Term(nodes));
let goals = state.apply(root, &deep).unwrap();
let deep = state.formula(state.goal(goals[0]).unwrap()[1]).to_string();
assert_eq!(deep.len(), 2 + 200_000 + 1 + 100_001);
assert!(deep.starts_with("p(f(f(") && deep.contains("f(f(c))"));
let view = deduxit::linear::ViewOptions::default();
let closed = state
.close(
goals[0],
&Options::default(),
&view,
&Limits::default(),
|_| false,
)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Unprovable(_)));
assert_eq!(state.undo(), Some(root));
step(&mut state, "∀x. p(x)", Rule::Exists, Some("f(c)"));
let json = serde_json::to_string(&state).unwrap();
let limits = Limits::default().with_terms(Some(1));
let error = <Interactive as deduxit::wire::Readable>::read(
&mut serde_json::Deserializer::from_str(&json),
&limits,
)
.unwrap_err();
assert!(error.to_string().contains("terms"), "{error}");
}
#[test]
fn undo_drops_what_its_step_made() {
let sequent: Sequent = "|- exists x. exists y. (p(x) -o p(y))".parse().unwrap();
let mut state = Interactive::new(&sequent, Mode::CLASSICAL).unwrap();
step(&mut state, "∃x. (∃y. (~p(x) ⅋ p(y)))", Rule::Exists, None);
let before = serde_json::to_string(&state).unwrap();
let goal = state.goals().next().unwrap();
let (options, view, limits) = (
Options::default(),
deduxit::linear::ViewOptions::default(),
Limits::default(),
);
for _ in 0..3 {
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
assert_eq!(state.undo(), Some(goal));
}
assert_eq!(serde_json::to_string(&state).unwrap(), before);
assert!(matches!(state.witness("a"), Err(StepError::Witness { .. })));
}
#[test]
fn a_session_read_back_undoes_as_it_was_written() {
let sequent: Sequent = "|- forall x. exists y. p(f(x), y) -o p(f(x), y)"
.parse()
.unwrap();
let mut live = Interactive::new(&sequent, Mode::CLASSICAL).unwrap();
let mut json = serde_json::to_string(&live).unwrap();
let forall = "∀x. (∃y. (~p(f(x), y) ⅋ p(f(x), y)))";
let exists = "∃y. (~p(f(a), y) ⅋ p(f(a), y))";
for round in 0..3 {
let witness = if round == 1 { None } else { Some("f(a)") };
let ops: [&dyn Fn(&mut Interactive); 5] = [
&|state| drop(step(state, forall, Rule::Forall, None)),
&|state| drop(step(state, exists, Rule::Exists, witness)),
&|state| assert!(state.undo().is_some()),
&|state| assert!(state.undo().is_some()),
&|state| drop(step(state, forall, Rule::Forall, None)),
];
for op in ops {
op(&mut live);
let mut read: Interactive = serde_json::from_str(&json).unwrap();
op(&mut read);
json = serde_json::to_string(&read).unwrap();
assert_eq!(json, serde_json::to_string(&live).unwrap(), "round {round}");
}
let goal = live.goals().next().unwrap();
assert_eq!(at(&live, goal, exists), 0);
assert!(live.undo().is_some());
let mut read: Interactive = serde_json::from_str(&json).unwrap();
assert!(read.undo().is_some());
json = serde_json::to_string(&read).unwrap();
}
assert_eq!(json, serde_json::to_string(&live).unwrap());
assert_eq!(
json,
serde_json::to_string(&Interactive::new(&sequent, Mode::CLASSICAL).unwrap()).unwrap()
);
step(&mut live, forall, Rule::Forall, None);
step(&mut live, exists, Rule::Exists, Some("f(a)"));
let json = serde_json::to_string(&live).unwrap();
assert!(
json.contains(r#""marks":[[0,0,0,0,0,0],[1,1,1,1,1,0]]"#),
"{json}"
);
let forged = json.replace("[1,1,1,1,1,0]", "[1,1,1,0,1,0]");
let error = serde_json::from_str::<Interactive>(&forged).unwrap_err();
assert!(error.to_string().contains("mark"), "{error}");
}
fn cut_formula(text: &str, mode: Mode) -> CutFormula {
CutFormula::parse_within(text, mode, &InputOptions::default(), &Limits::default()).unwrap()
}
#[test]
fn a_first_order_session_cuts() {
let mode = Mode::INTUITIONISTIC;
let sequent: Sequent = "forall x. p(x) |- forall y. p(y)".parse().unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∀y. p(y)", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let before = serde_json::to_string(&state).unwrap();
let error = state
.cut(goal, &cut_formula("q", mode), &[0], &Limits::default())
.unwrap_err();
assert!(
matches!(&error, Error::Step(StepError::CutSymbol { name, .. }) if name == "q"),
"{error}"
);
let left = at(&state, goal, "∀x. p(x)");
let [first, second] = state
.cut(
goal,
&cut_formula("forall z. p(z)", mode),
&[left],
&Limits::default(),
)
.unwrap();
let shown = |state: &Interactive, goal: GoalId| -> Vec<String> {
let goal = state.goal(goal).unwrap();
goal.iter().map(|&m| state.formula(m).to_string()).collect()
};
assert_eq!(shown(&state, first), ["∀x. p(x)", "∀z. p(z)"]);
assert_eq!(shown(&state, second), ["∀x. p(x)", "p(a)"]);
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
let mut cut = state.clone();
assert_eq!(cut.undo(), Some(goal));
assert_eq!(serde_json::to_string(&cut).unwrap(), before);
let mut read: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(read.undo(), Some(goal));
assert_eq!(
serde_json::to_string(&read).unwrap(),
serde_json::to_string(&cut).unwrap()
);
let ax = |state: &mut Interactive| {
let goal = state.goals().next().unwrap();
state.apply(goal, &Step::new(0, Rule::Ax)).unwrap();
};
let goal = |state: &Interactive, n: usize| state.goals().nth(n).unwrap();
let g = goal(&state, 1);
let p = at(&state, g, "∀x. p(x)");
let a = state.witness("a").unwrap();
state
.apply(g, &Step::new(p, Rule::Exists).with_witness(a))
.unwrap();
let g = goal(&state, 1);
state.apply(g, &Step::new(0, Rule::Ax)).unwrap();
step(&mut state, "∀z. p(z)", Rule::Forall, None);
step(&mut state, "∀x. p(x)", Rule::Exists, None);
assert_eq!(
shown(&state, goal(&state, 0)),
["p(b)", "p($1)"],
"the eigenvariable after the cut is the next letter"
);
ax(&mut state);
assert!(state.is_complete());
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
for state in [&state, &back] {
let proof = state.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
}
let sequent: Sequent = "forall x. p(x) |- forall y. exists w. p(f(w))"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∀y. (∃w. p(f(w)))", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let uncut = serde_json::to_string(&state).unwrap();
let left = at(&state, goal, "∀x. p(x)");
let formula = cut_formula("forall z. p(f(f(z)))", mode);
let [first, second] = state
.cut(goal, &formula, &[left], &Limits::default())
.unwrap();
assert_eq!(shown(&state, second), ["∀z. p(f(f(z)))", "∃w. p(f(w))"]);
let apply = |state: &mut Interactive, g: GoalId, text: &str, witness: &str| {
let witness = state.witness(witness).unwrap();
let p = at(state, g, text);
state
.apply(g, &Step::new(p, Rule::Exists).with_witness(witness))
.unwrap()[0]
};
let g = apply(&mut state, second, "∃w. p(f(w))", "f(a)");
let g = apply(&mut state, g, "∀z. p(f(f(z)))", "a");
assert_eq!(shown(&state, g), ["p(f(f(a)))", "p(f(f(a)))"]);
state.apply(g, &Step::new(0, Rule::Ax)).unwrap();
assert_eq!(state.goals().next(), Some(first));
step(&mut state, "∀z. p(f(f(z)))", Rule::Forall, None);
step(&mut state, "∀x. p(x)", Rule::Exists, Some("f(f(b))"));
ax(&mut state);
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
let proof = back.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
let mut back = back;
while back.steps() > 1 {
back.undo();
}
assert_eq!(serde_json::to_string(&back).unwrap(), uncut);
let sequent: Sequent = "forall x. p(f(x)), q(c) |- exists y. p(y) * q(c)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
let opened = step(&mut state, "∀x. p(f(x))", Rule::Exists, Some("f(c)"));
assert!(shown(&state, opened[0]).contains(&"p(f(f(c)))".to_owned()));
state
.cut(
opened[0],
&cut_formula("q(f(c))", mode),
&[],
&Limits::default(),
)
.unwrap();
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
let mode = Mode::CLASSICAL;
let sequent: Sequent = "p(a) |- exists x. p(x)".parse().unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
let root = state.goals().next().unwrap();
let left = at(&state, root, "~p(a)");
let [first, _] = state
.cut(
root,
&cut_formula("exists y. p(y)", mode),
&[left],
&Limits::default(),
)
.unwrap();
assert_eq!(shown(&state, first), ["~p(a)", "∃y. p(y)"]);
let a = state.witness("a").unwrap();
state
.apply(first, &Step::new(1, Rule::Exists).with_witness(a))
.unwrap();
loop {
let Some(g) = state.goals().next() else {
break;
};
let formulas = shown(&state, g);
if formulas.iter().any(|f| f.starts_with("∀")) {
let p = formulas.iter().position(|f| f.starts_with("∀")).unwrap();
state.apply(g, &Step::new(p, Rule::Forall)).unwrap();
} else if let Some(p) = formulas.iter().position(|f| f.starts_with("∃")) {
state.apply(g, &Step::new(p, Rule::Exists)).unwrap();
} else {
state.apply(g, &Step::new(0, Rule::Ax)).unwrap();
}
}
let proof = state.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
let json = serde_json::to_string(&state).unwrap();
let mut back: Interactive = serde_json::from_str(&json).unwrap();
while back.undo().is_some() {}
assert_eq!(
serde_json::to_string(&back).unwrap(),
serde_json::to_string(&Interactive::new(&sequent, mode).unwrap()).unwrap()
);
}
#[test]
fn a_cut_formula_names_the_goals_eigenvariables() {
let mode = Mode::INTUITIONISTIC;
let sequent: Sequent = "forall x. (p(x) -o q(x)), forall x. p(x) |- forall y. q(y)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
step(&mut state, "∀y. q(y)", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let before = serde_json::to_string(&state).unwrap();
let left = at(&state, goal, "∀x. p(x)");
let [first, second] = state
.cut(
goal,
&cut_formula("p(a)", mode),
&[left],
&Limits::default(),
)
.unwrap();
let shown = |state: &Interactive, goal: GoalId| -> Vec<String> {
let goal = state.goal(goal).unwrap();
goal.iter().map(|&m| state.formula(m).to_string()).collect()
};
assert_eq!(shown(&state, first), ["∀x. p(x)", "p(a)"]);
assert_eq!(shown(&state, second), ["∀x. (p(x) ⊸ q(x))", "q(a)", "p(a)"]);
let json = serde_json::to_string(&state).unwrap();
let mut back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
assert_eq!(back.undo(), Some(goal));
assert_eq!(serde_json::to_string(&back).unwrap(), before);
let (options, view, limits) = (
Options::default(),
deduxit::linear::ViewOptions::default(),
Limits::default(),
);
for goal in [first, second] {
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
}
assert!(state.is_complete());
let derivation = state.derivation().unwrap().to_string();
assert!(derivation.contains("∀x. p(x) ⊢ p(a)"), "{derivation}");
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
for state in [&state, &back] {
let proof = state.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
}
let sequent: Sequent = "forall x. (p(x) -o q(x)), forall x. p(x) |- forall y. q(y)"
.parse()
.unwrap();
let fresh = serde_json::to_string(&Interactive::new(&sequent, mode).unwrap()).unwrap();
let mut state: Interactive = serde_json::from_str(&fresh).unwrap();
step(&mut state, "∀y. q(y)", Rule::Forall, None);
let goal = state.goals().next().unwrap();
let left = at(&state, goal, "∀x. p(x)");
let [_, second] = state
.cut(
goal,
&cut_formula("p(a)", mode),
&[left],
&Limits::default(),
)
.unwrap();
let left = at(&state, second, "∀x. (p(x) ⊸ q(x))");
state
.cut(
second,
&cut_formula("p(a) -o q(a)", mode),
&[left],
&Limits::default(),
)
.unwrap();
let json = serde_json::to_string(&state).unwrap();
let back: Interactive = serde_json::from_str(&json).unwrap();
assert_eq!(serde_json::to_string(&back).unwrap(), json);
let goals: Vec<GoalId> = state.goals().collect();
for goal in goals {
let closed = state
.close(goal, &options, &view, &limits, |_| false)
.unwrap();
assert!(matches!(closed.outcome.verdict, Verdict::Proved(_)));
}
let proof = state.proof(&Limits::default(), |_| false).unwrap();
assert_eq!(proof.check(mode), Ok(()));
let mut back: Interactive =
serde_json::from_str(&serde_json::to_string(&state).unwrap()).unwrap();
while back.undo().is_some() {}
assert_eq!(serde_json::to_string(&back).unwrap(), fresh);
let sequent: Sequent = "forall x. p(x), forall x. q(x) |- (forall y. p(y)) * (forall y. q(y))"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
let root = state.goals().next().unwrap();
let tensor = at(&state, root, "(∀y. p(y)) ⊗ (∀y. q(y))");
let left = at(&state, root, "∀x. p(x)");
let goals = state
.apply(root, &Step::new(tensor, Rule::Tensor).left(&[left]))
.unwrap();
let factor = at(&state, goals[0], "∀y. p(y)");
state
.apply(goals[0], &Step::new(factor, Rule::Forall))
.unwrap();
let error = state
.cut(
goals[1],
&cut_formula("q(a)", mode),
&[0],
&Limits::default(),
)
.unwrap_err();
assert!(
matches!(&error, Error::Step(StepError::Eigenvariable { name, .. }) if name == "a"),
"{error}"
);
assert!(error.to_string().contains("eigenvariable a"), "{error}");
}
#[test]
fn undoing_a_cut_keeps_what_the_table_names() {
let mode = Mode::INTUITIONISTIC;
let sequent: Sequent = "p(f(c)) |- exists y. p(y)".parse().unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
let root = state.goals().next().unwrap();
let [_, second] = state
.cut(
root,
&cut_formula("p(f(f(c)))", mode),
&[],
&Limits::default(),
)
.unwrap();
let p = at(&state, second, "∃y. p(y)");
let witness = state.witness("f(f(c))").unwrap();
state
.apply(second, &Step::new(p, Rule::Exists).with_witness(witness))
.unwrap();
let mut json: serde_json::Value = serde_json::to_value(&state).unwrap();
json["instances"].as_object_mut().unwrap().remove("marks");
let mut read: Interactive = serde_json::from_value(json).unwrap();
assert!(read.undo().is_some() && read.undo().is_some());
let again = serde_json::to_string(&read).unwrap();
serde_json::from_str::<Interactive>(&again).unwrap();
let mut sequent =
serde_json::to_value("p(c) |- exists y. p(y)".parse::<Sequent>().unwrap()).unwrap();
sequent["symbols"]
.as_array_mut()
.unwrap()
.push(serde_json::json!(["g", 1]));
let sequent: Sequent = serde_json::from_value(sequent).unwrap();
let mut state = Interactive::new(&sequent, mode).unwrap();
let root = state.goals().next().unwrap();
let p = at(&state, root, "∃y. p(y)");
let witness = state.witness("g(c)").unwrap();
let goal = state
.apply(root, &Step::new(p, Rule::Exists).with_witness(witness))
.unwrap()[0];
let before = serde_json::to_string(&state).unwrap();
state
.cut(goal, &cut_formula("p(c)", mode), &[], &Limits::default())
.unwrap();
assert_eq!(state.undo(), Some(goal));
assert_eq!(serde_json::to_string(&state).unwrap(), before);
}
#[test]
fn a_session_refuses_what_no_step_could_make() {
let sequent: Sequent = "forall x. p(x) |- p(g(c, c))".parse().unwrap();
let index = |name: &str| {
let i = sequent
.symbols()
.iter()
.position(|(n, _)| n == name)
.unwrap();
deduxit::linear::sequents::Symbol::new(u32::try_from(i).unwrap())
};
let mut nodes = vec![TermNode::App(index("c"), vec![])];
for i in 0..40u32 {
nodes.push(TermNode::App(index("g"), vec![i, i]));
}
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
let root = state.goals().next().unwrap();
let position = at(&state, root, "∀x. p(x)");
let error = state
.apply(
root,
&Step::new(position, Rule::Exists).with_witness(Witness::Term(nodes)),
)
.unwrap_err();
assert!(
matches!(&error, StepError::Witness { reason, .. } if reason.contains("unfold")),
"{error}"
);
assert_eq!(state.steps(), 0);
let sequent: Sequent = "|- exists x. p(x), ~p(a), q(g(b))".parse().unwrap();
let limits = Limits::default().with_terms(Some(4));
let mut state = Interactive::within(&sequent, Mode::CLASSICAL, &limits).unwrap();
let root = state.goals().next().unwrap();
let deep = state.witness("g(g(g(g(g(g(g(g(g(g(a))))))))))").unwrap();
let error = state
.apply(root, &Step::new(0, Rule::Exists).with_witness(deep))
.unwrap_err();
assert!(matches!(error, StepError::Witness { .. }), "{error}");
let a = state.witness("a").unwrap();
state
.apply(root, &Step::new(0, Rule::Exists).with_witness(a))
.unwrap();
let json = serde_json::to_string(&state).unwrap();
<Interactive as deduxit::wire::Readable>::read(
&mut serde_json::Deserializer::from_str(&json),
&limits,
)
.unwrap();
let sequent: Sequent = "forall x. p(x) |- p(c)".parse().unwrap();
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
let goals = step(&mut state, "∀x. p(x)", Rule::Exists, None);
state.apply(goals[0], &Step::new(0, Rule::Ax)).unwrap();
let json = serde_json::to_string(&state).unwrap();
let forged = json.replace(r#""bindings":[[0,1,1]]"#, r#""bindings":[[0,1,0]]"#);
assert_ne!(forged, json, "{json}");
assert!(serde_json::from_str::<Interactive>(&json).is_ok());
let error = serde_json::from_str::<Interactive>(&forged).unwrap_err();
assert!(error.to_string().contains("binding"), "{error}");
let sequent: Sequent = "forall x. exists y. r(x, y) |- exists y. forall x. r(x, y)"
.parse()
.unwrap();
let mut state = Interactive::new(&sequent, Mode::INTUITIONISTIC).unwrap();
step(&mut state, "∃y. (∀x. r(x, y))", Rule::Exists, None);
step(&mut state, "∀x. r(x, $1)", Rule::Forall, None);
step(&mut state, "∀x. (∃y. r(x, y))", Rule::Exists, Some("a"));
step(&mut state, "∃y. r(a, y)", Rule::Forall, None);
let json = serde_json::to_string(&state).unwrap();
let forged = json.replace(r#""metas":[0]"#, r#""metas":[2]"#);
assert_ne!(forged, json, "{json}");
assert!(serde_json::from_str::<Interactive>(&json).is_ok());
let error = serde_json::from_str::<Interactive>(&forged).unwrap_err();
assert!(error.to_string().contains("level"), "{error}");
let sequent: Sequent = "|- (exists x. 1) & (forall y. 1)".parse().unwrap();
let mut state = Interactive::new(&sequent, Mode::CLASSICAL).unwrap();
let root = state.goals().next().unwrap();
let goals = state.apply(root, &Step::new(0, Rule::With)).unwrap();
let opened = state.apply(goals[0], &Step::new(0, Rule::Exists)).unwrap();
let closed = state
.close(
opened[0],
&Options::default(),
&deduxit::linear::ViewOptions::default(),
&Limits::default(),
|_| false,
)
.unwrap();
assert!(closed.grafted.is_ok());
let goal = state.goals().next().unwrap();
state.apply(goal, &Step::new(0, Rule::Forall)).unwrap();
let json = serde_json::to_string(&state).unwrap();
let forged = json.replace("[3,1,1,2,1,1]", "[3,1,1,2,1,0]");
assert_ne!(forged, json, "{json}");
let error = serde_json::from_str::<Interactive>(&forged).unwrap_err();
assert!(error.to_string().contains("mark"), "{error}");
}