use super::*;
use crate::linear::nets::{Criterion, MellStructure, Placement};
use crate::linear::occurrences::Forest;
use crate::linear::proofs::cut as terms;
use crate::linear::proofs::{CutFormula, Interactive, Node, Proof};
use crate::linear::search::generate::{self, IllRules, Rng, Rules};
use crate::linear::search::{Engine, Verdict};
use crate::linear::{InputOptions, Mode, Sequent, ViewOptions};
use std::collections::BTreeMap;
const MOST_STEPS: usize = 5_000;
fn never(_: Progress) -> bool {
false
}
trait Tested: Net + std::fmt::Debug {
fn of(proof: &Proof, criterion: Criterion) -> Result<Self, Error>;
fn proof(&self) -> Proof;
}
impl Tested for ProofStructure {
fn of(proof: &Proof, criterion: Criterion) -> Result<Self, Error> {
Self::from_proof(proof, criterion, &Limits::default(), never)
}
fn proof(&self) -> Proof {
self.sequentialize(&Limits::default(), never).unwrap()
}
}
impl Tested for MellStructure {
fn of(proof: &Proof, criterion: Criterion) -> Result<Self, Error> {
Self::from_proof(proof, criterion, &Limits::default(), never)
}
fn proof(&self) -> Proof {
self.sequentialize(&Limits::default(), never).unwrap()
}
}
fn cut_proof(text: &str, mode: Mode, formula: &str, left: &[usize]) -> Proof {
let limits = Limits::default();
let sequent: Sequent = text.parse().unwrap();
let mut session = Interactive::new(&sequent, mode).unwrap();
let goal = session.goals().next().unwrap();
let formula =
CutFormula::parse_within(formula, mode, &InputOptions::default(), &limits).unwrap();
session.cut(goal, &formula, left, &limits).unwrap();
let closed = session.close_all(
&crate::linear::Options::default(),
&ViewOptions::default(),
&limits,
never,
);
assert!(
closed
.iter()
.all(|(_, c)| c.as_ref().is_ok_and(|c| c.grafted.is_ok())),
"{text}: {closed:?}"
);
session.proof(&limits, never).unwrap()
}
fn proof_of(text: &str, mode: Mode, copies: u32) -> Option<(Proof, Mode)> {
let sequent: Sequent = text.parse().unwrap();
let engine = (!mode.is_intuitionistic()).then_some(Engine::Focus);
let options = crate::linear::Options::default()
.with_copies(Some(copies))
.with_engine(engine);
let mut polls = 0u32;
let outcome =
crate::linear::search::prove_within(&sequent, mode, &options, &Limits::default(), |_| {
polls += 1;
polls > 20_000
})
.ok()?;
match outcome.verdict {
Verdict::Proved(proof) => Some((*proof, mode)),
Verdict::Unprovable(_) | Verdict::Unknown(_) => None,
}
}
fn proofs() -> Vec<(Proof, Mode)> {
let mut rng = Rng::new(4103);
let mut plain = Vec::new();
for (mix, exponentials) in [(false, false), (true, false), (false, true), (true, true)] {
let rules = Rules {
units: false,
additives: false,
mix,
exponentials,
};
let mode = if mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
for _ in 0..60 {
let budget = 2 + rng.below(9);
let provable = generate::provable(&mut rng, rules, 3, budget);
let text = generate::sequent(&provable.formulas);
plain.extend(proof_of(&text, mode, provable.copies));
}
}
for exponentials in [false, true] {
let rules = IllRules {
units: false,
additives: false,
zero: false,
exponentials,
};
for _ in 0..60 {
let budget = 2 + rng.below(9);
let ill = generate::ill(&mut rng, rules, 3, budget);
let text = generate::two_sided(&ill.hypotheses, &ill.goal);
plain.extend(proof_of(&text, Mode::INTUITIONISTIC, ill.copies));
}
}
let mut proofs = crate::linear::proofs::interactive::with_cuts(&plain, &mut rng);
for text in [
"!a |- a * a",
"!a |- !a",
"!a, b |- b",
"!a, !a -o b |- b * a",
"!a, !b |- !(a * b) * a",
] {
let mode = Mode::INTUITIONISTIC;
proofs.push((cut_proof(text, mode, "!a", &[0]), mode));
}
for mode in [Mode::CLASSICAL, Mode::CLASSICAL.with_mix()] {
for (text, rest) in [
("|- ?~a, a * a", &[1][..]),
("|- ?~a, !a", &[1]),
("|- ?~a, ~b, b", &[1, 2]),
("|- ?~a, ?~b, !(a * b) * a", &[1, 2]),
] {
proofs.push((cut_proof(text, mode, "!a", &[0]), mode));
proofs.push((cut_proof(text, mode, "?~a", rest), mode));
}
}
proofs
}
fn cuts_of(proof: &Proof) -> usize {
proof
.nodes()
.iter()
.filter(|n| matches!(n, Node::Cut(..)))
.count()
}
fn sound<N: Tested>(net: &N, proof: &Proof, mode: Mode) {
assert_eq!(net.check(&mut never), Ok(()), "{net:?}");
let back = net.proof();
assert_eq!(back.check(mode), Ok(()), "{mode:?}: {net:?}");
assert_eq!(back.sequent(), proof.sequent());
assert_eq!(back.conclusion(), proof.conclusion());
assert_eq!(cuts_of(&back), net.cut_links().len(), "{net:?}");
}
#[derive(Default)]
struct Seen {
modes: BTreeMap<String, usize>,
cases: BTreeMap<&'static str, usize>,
nested: usize,
exponential: usize,
compared: [usize; 2],
}
fn eliminated<N: Tested>(proof: &Proof, mode: Mode, seen: &mut Seen) -> N {
let criterion = Criterion::of(mode).unwrap();
let net = N::of(proof, criterion).unwrap_or_else(|e| panic!("{e} in {mode:?}: {proof:?}"));
assert_eq!(net.cut_links().len(), cuts_of(proof));
sound(&net, proof, mode);
let (mut current, mut steps) = (net.clone(), Vec::new());
while !current.cut_links().is_empty() {
assert!(steps.len() < MOST_STEPS, "no end in {mode:?}: {net:?}");
let reduction = step(
¤t,
None,
&Options::default(),
&Limits::default(),
never,
)
.unwrap_or_else(|e| panic!("{e} in {mode:?} at {current:?}"));
sound(&reduction.net, proof, mode);
assert_eq!(reduction.step.cut, current.cut_links()[0]);
*seen.cases.entry(reduction.step.case.name()).or_default() += 1;
steps.push(reduction.step);
current = reduction.net;
}
let mut visited = Vec::new();
let elimination = eliminate(
&net,
&Options::default(),
&Limits::default(),
never,
|_, step| visited.push(*step),
)
.unwrap();
assert_eq!(elimination.end, End::CutFree);
assert_eq!(elimination.steps, steps);
assert_eq!(visited, steps);
assert_eq!(
format!("{:?}", elimination.net.proof().nodes()),
format!("{:?}", current.proof().nodes())
);
current
}
#[test]
fn every_step_keeps_the_criterion_and_the_conclusion() {
let mut seen = Seen::default();
for (proof, mode) in proofs() {
let forest = proof.forest();
let cuts: Vec<Node> = proof
.nodes()
.iter()
.copied()
.filter(|n| matches!(n, Node::Cut(..)))
.collect();
seen.nested += usize::from(cuts.len() > 1);
seen.exponential += usize::from(cuts.iter().any(|&node| {
matches!(node, Node::Cut(a, ..)
if matches!(forest.kind(a.occ()), Kind::Bang | Kind::Quest))
}));
*seen.modes.entry(format!("{mode:?}")).or_default() += 1;
let normal = terms::eliminate(
&proof,
mode,
None,
&terms::Options::default(),
&Limits::default(),
never,
|_, _| {},
)
.unwrap();
assert_eq!(normal.end, End::CutFree);
let criterion = Criterion::of(mode).unwrap();
if proof.sequent().fragment().has_nets() {
let net: ProofStructure = eliminated(&proof, mode, &mut seen);
let term = ProofStructure::of(&normal.proof, criterion).unwrap();
let sorted = |net: &ProofStructure| {
let mut links: Vec<_> = net
.links()
.iter()
.map(|&(x, y)| (x.min(y), x.max(y)))
.collect();
links.sort_unstable();
links
};
assert_eq!(sorted(&net), sorted(&term), "{mode:?}: {proof:?}");
seen.compared[0] += 1;
} else {
let net: MellStructure = eliminated(&proof, mode, &mut seen);
let term = MellStructure::of(&normal.proof, criterion).unwrap();
let once = |net: &MellStructure| {
let mut met = vec![false; net.forest().len()];
net.vertices().all(|v| {
let o = net.occurrence(v).unwrap().index();
!std::mem::replace(&mut met[o], true)
})
};
if once(&net) && once(&term) {
assert!(
crate::linear::nets::mell::tests::isomorphic(&net, &term),
"{mode:?}: {net:?}\nagainst the term's\n{term:?}"
);
seen.compared[1] += 1;
}
}
}
let Seen {
modes,
cases,
nested,
exponential,
compared,
} = seen;
for case in [
Case::Axiom,
Case::TensorPar,
Case::Weakening,
Case::Dereliction,
Case::Contraction,
Case::BoxIntoBox,
] {
assert!(
cases.get(case.name()).is_some_and(|&k| k > 5),
"{case:?}: {cases:?}"
);
}
assert!(
modes.len() == 3 && modes.values().all(|&k| k > 40),
"{modes:?}"
);
assert!(
nested > 150 && exponential > 20 && compared[0] > 150 && compared[1] > 50,
"{nested} {exponential} {compared:?} {cases:?} {modes:?}"
);
}
#[test]
fn any_cut_link_may_be_reduced() {
fn reduced<N: Tested>(proof: &Proof, mode: Mode, at: VertexId) -> (VertexId, VertexId) {
let net = N::of(proof, Criterion::of(mode).unwrap()).unwrap();
let r = step(
&net,
Some(at),
&Options::default(),
&Limits::default(),
never,
)
.unwrap();
sound(&r.net, proof, mode);
r.step.cut
}
let mut steps = 0;
for (proof, mode) in proofs().into_iter().step_by(3) {
let criterion = Criterion::of(mode).unwrap();
let mll = proof.sequent().fragment().has_nets();
let cuts = if mll {
ProofStructure::of(&proof, criterion)
.unwrap()
.cuts()
.to_vec()
} else {
MellStructure::of(&proof, criterion)
.unwrap()
.cuts()
.to_vec()
};
for (i, &(x, y)) in cuts.iter().enumerate() {
let at = if i % 2 == 0 { x } else { y };
let named = if mll {
reduced::<ProofStructure>(&proof, mode, at)
} else {
reduced::<MellStructure>(&proof, mode, at)
};
assert_eq!(named, (x, y), "{mode:?}: {proof:?}");
steps += 1;
}
}
assert!(steps > 100, "{steps}");
}
#[test]
fn a_step_needs_a_cut_link() {
let proof = cut_proof("|- ?~a, a * a", Mode::CLASSICAL, "!a", &[0]);
let net = MellStructure::of(&proof, Criterion::MLL).unwrap();
let options = Options::default();
let refused = step(
&net,
Some(VertexId::new(0)),
&options,
&Limits::default(),
never,
);
assert!(matches!(
refused,
Err(Error::Net(e)) if *e == NetError::NoCut { vertex: Some(VertexId::new(0)) }
));
let normal = eliminate(&net, &options, &Limits::default(), never, |_, _| {}).unwrap();
let refused = step(&normal.net, None, &options, &Limits::default(), never);
assert!(matches!(refused, Err(Error::Net(e)) if *e == NetError::NoCut { vertex: None }));
}
#[test]
fn a_bound_stops_with_a_net() {
let proof = cut_proof("|- ?~a, !(a * a) * a", Mode::CLASSICAL, "!a", &[0]);
let net = MellStructure::of(&proof, Criterion::MLL).unwrap();
let mut largest = 0;
let full = eliminate(
&net,
&Options::default(),
&Limits::default(),
never,
|net, _| {
largest = largest.max(net.len());
},
)
.unwrap();
assert_eq!(full.end, End::CutFree);
let largest = largest.max(full.net.len()) as u64;
let options = Options::default().with_steps(Some(1));
let one = eliminate(&net, &options, &Limits::default(), never, |_, _| {}).unwrap();
assert_eq!(
one.end,
End::Refused(Refusal::Elimination {
what: Bound::Steps,
limit: 1
})
);
assert_eq!(one.steps.len(), 1);
let options = Options::default().with_nodes(Some(largest - 1));
let few = eliminate(&net, &options, &Limits::default(), never, |_, _| {}).unwrap();
assert_eq!(
few.end,
End::Refused(Refusal::Elimination {
what: Bound::Vertices,
limit: largest - 1
})
);
for ended in [&one, &few] {
assert_ne!(ended.net.cuts(), []);
sound(&ended.net, &proof, Mode::CLASSICAL);
}
let mut stopped_with_cuts = 0;
for polls in 1..40 {
let mut asked = 0;
let stopped = eliminate(
&net,
&Options::default(),
&Limits::default(),
|_| {
asked += 1;
asked > polls
},
|_, _| {},
);
match stopped {
Ok(e) if e.end == End::CutFree => {}
Ok(e) => {
assert!(matches!(e.end, End::Refused(Refusal::Stopped { .. })));
assert_ne!(e.net.cuts(), []);
sound(&e.net, &proof, Mode::CLASSICAL);
stopped_with_cuts += 1;
}
Err(Error::Net(e)) => assert!(matches!(*e, NetError::Refused { .. })),
Err(e) => panic!("{e}"),
}
}
assert!(stopped_with_cuts > 3, "{stopped_with_cuts}");
}
#[test]
fn cut_links_are_checked() {
let mut sequent: Sequent = "|- a, ~a".parse().unwrap();
sequent.add_cut("|- a par ~a".parse().unwrap()).unwrap();
let forest = Forest::new(&sequent).unwrap();
let v = VertexId::new;
let built = |cuts: &[(u32, u32)], links: &[(u32, u32)]| {
let pairs =
|list: &[(u32, u32)]| list.iter().map(|&(x, y)| (v(x), v(y))).collect::<Vec<_>>();
ProofStructure::with_cuts(forest.clone(), Criterion::MLL, &pairs(cuts), &pairs(links))
};
let net = built(&[(5, 2)], &[(3, 4), (0, 6), (1, 7)]).unwrap();
assert_eq!(net.cuts(), [(v(2), v(5))]);
assert_eq!(net.is_correct(never), Ok(()));
let cut = |vertex: u32| {
format!(
"{:?}",
Err::<(), Error>(
NetError::Placement {
vertex: v(vertex),
fault: Placement::Cut,
}
.into()
)
)
};
let error = |built: Result<ProofStructure, Error>| format!("{:?}", built.map(|_| ()));
assert_eq!(error(built(&[(2, 6)], &[])), cut(2));
assert_eq!(error(built(&[(0, 1)], &[])), cut(0));
assert_eq!(error(built(&[(2, 5), (3, 6)], &[])), cut(3));
assert!(matches!(
built(&[], &[(1, 3)]),
Err(Error::Net(e)) if matches!(*e, NetError::Placement { fault: Placement::Uncut, .. })
));
let net = built(&[(3, 6), (4, 7)], &[(0, 1), (3, 6), (4, 7)]).unwrap();
assert!(matches!(
net.is_correct(never),
Err(NetError::SwitchingCycle { .. })
));
assert!(!net.is_acyclic(&mut net.scratch()));
}
#[test]
fn a_cut_occurrence_twice_needs_a_structure_with_boxes() {
use crate::linear::occurrences::{Member, OccId};
use crate::linear::proofs::NodeId;
let m = |o: u32| Member::from(OccId::new(o));
let n = NodeId::new;
let made = |text: &str, cut: &str, nodes: Vec<Node>| {
let mut sequent: Sequent = text.parse().unwrap();
sequent.add_cut(cut.parse().unwrap()).unwrap();
let forest = Forest::new(&sequent).unwrap();
let root = n(nodes.len() as u32 - 1);
Proof::new(forest, nodes, root).unwrap()
};
let twice = made(
"|- a * a, ~a, ~a",
"|- a",
vec![
Node::Ax(m(5), m(3)),
Node::Ax(m(1), m(6)),
Node::Cut(m(5), n(0), n(1)),
Node::Ax(m(5), m(4)),
Node::Ax(m(2), m(6)),
Node::Cut(m(5), n(3), n(4)),
Node::Tensor(m(0), n(2), n(5)),
],
);
let nested = made(
"|- ((~a par ~b) par (a * b)) * (~a par a)",
"|- a * b",
vec![
Node::Ax(m(12), m(3)),
Node::Ax(m(13), m(4)),
Node::Tensor(m(11), n(0), n(1)),
Node::Ax(m(15), m(6)),
Node::Ax(m(16), m(7)),
Node::Tensor(m(5), n(3), n(4)),
Node::Par(m(14), n(5)),
Node::Cut(m(11), n(2), n(6)),
Node::Par(m(2), n(7)),
Node::Par(m(1), n(8)),
Node::Ax(m(12), m(9)),
Node::Ax(m(15), m(10)),
Node::Cut(m(12), n(10), n(11)),
Node::Par(m(8), n(12)),
Node::Tensor(m(0), n(9), n(13)),
],
);
for proof in [twice, nested] {
for mode in [Mode::CLASSICAL, Mode::CLASSICAL.with_mix()] {
assert_eq!(proof.check(mode), Ok(()));
let criterion = Criterion::of(mode).unwrap();
assert!(matches!(
ProofStructure::of(&proof, criterion),
Err(Error::Net(e)) if matches!(*e, NetError::Placement { fault: Placement::Cut, .. })
));
let mut seen = Seen::default();
let net: MellStructure = eliminated(&proof, mode, &mut seen);
assert_eq!(net.cuts(), []);
}
}
}