use super::{MellStructure, Parts, Placed, Placement};
use crate::Error;
use crate::limits::{Limits, Refusal};
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::nets::{Criterion, NetError, ProofStructure, VertexId};
use crate::linear::occurrences::{Forest, Member, OccId};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::search::generate::{self, IllRules, Rng, Rules};
use crate::linear::search::{Engine, Options, Verdict};
use crate::linear::sequents::{Kind, Sequent};
const fn v(id: u32) -> VertexId {
VertexId::new(id)
}
const fn o(id: u32) -> OccId {
OccId::new(id)
}
fn forest(input: &str) -> Forest {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
Forest::new(&s).unwrap()
}
fn build(
input: &str,
vertices: &[(u32, u32, Option<u32>)],
links: &[(u32, u32)],
weakenings: &[(u32, u32)],
) -> Result<MellStructure, Error> {
let parts = Parts {
vertices: vertices
.iter()
.map(|&(oc, p, b)| Placed::new(o(oc), v(p), b.map(v)))
.collect(),
cuts: Vec::new(),
links: links.iter().map(|&(x, y)| (v(x), v(y))).collect(),
weakenings: weakenings.iter().map(|&(x, y)| (v(x), v(y))).collect(),
};
MellStructure::from_parts(forest(input), Criterion::MLL, &parts, &Limits::default())
}
fn round_trip(net: &MellStructure) -> Proof {
assert_eq!(net.is_correct(|_| false), Ok(()));
let proof = net.sequentialize(&Limits::default(), |_| false).unwrap();
let mode = if net.criterion().mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
assert_eq!(proof.mode(), Some(mode));
assert_eq!(proof.check(mode), Ok(()));
let back =
MellStructure::from_proof(&proof, net.criterion(), &Limits::default(), |_| false).unwrap();
let mut seen = vec![false; net.forest().len()];
let repeats = net.vertices().any(|x| {
let o = net.occurrence(x).unwrap().index();
std::mem::replace(&mut seen[o], true)
});
assert!(
repeats || isomorphic(net, &back),
"{net:?}\nback as\n{back:?}"
);
proof
}
#[derive(Clone)]
enum Pending {
Pair(u32, u32),
Bag(Vec<u32>, Vec<u32>),
}
pub(in crate::linear::nets) fn isomorphic(a: &MellStructure, b: &MellStructure) -> bool {
if a.len() != b.len() || a.links().len() != b.links().len() {
return false;
}
let roots = a.forest().roots().len() as u32;
let pending = (0..roots).map(|r| Pending::Pair(r, r)).collect();
matches(a, b, vec![None; a.len()], vec![None; b.len()], pending)
}
fn matches(
a: &MellStructure,
b: &MellStructure,
mut map: Vec<Option<u32>>,
mut back: Vec<Option<u32>>,
mut pending: Vec<Pending>,
) -> bool {
while let Some(next) = pending.pop() {
match next {
Pending::Pair(x, y) => {
match (map[x as usize], back[y as usize]) {
(Some(m), _) if m == y => continue,
(None, None) => {}
_ => return false,
}
let (vx, vy) = (v(x), v(y));
if a.occurrence(vx) != b.occurrence(vy) {
return false;
}
map[x as usize] = Some(y);
back[y as usize] = Some(x);
match (a.inside(vx), b.inside(vy)) {
(None, None) => {}
(Some(p), Some(q)) => pending.push(Pending::Pair(p.get(), q.get())),
_ => return false,
}
match (a.partner(vx), b.partner(vy)) {
(None, None) => {}
(Some(p), Some(q)) => pending.push(Pending::Pair(p.get(), q.get())),
_ => return false,
}
let px: Vec<u32> = a.premises(vx).map(VertexId::get).collect();
let py: Vec<u32> = b.premises(vy).map(VertexId::get).collect();
if px.len() != py.len() {
return false;
}
if a.forest().kind(a.occurrence(vx).unwrap()) == Kind::Quest {
pending.push(Pending::Bag(px, py));
} else {
pending.extend(px.into_iter().zip(py).map(|(p, q)| Pending::Pair(p, q)));
}
}
Pending::Bag(xs, ys) => {
let Some((&first, rest)) = xs.split_first() else {
continue;
};
return (0..ys.len()).any(|j| {
let mut others = ys.clone();
let y = others.remove(j);
let mut pending = pending.clone();
pending.push(Pending::Bag(rest.to_vec(), others));
pending.push(Pending::Pair(first, y));
matches(a, b, map.clone(), back.clone(), pending)
});
}
}
}
true
}
fn proof_of(sequent: &Sequent, mode: Mode, copies: u32) -> Option<Proof> {
let engine = (!mode.is_intuitionistic()).then_some(Engine::Focus);
let options = 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),
Verdict::Unprovable(_) | Verdict::Unknown(_) => None,
}
}
#[test]
fn classic_nets() {
let net = build(
"|- ?~a, !a",
&[(3, 1, Some(1)), (1, 0, Some(1))],
&[(2, 3)],
&[],
)
.unwrap();
assert_eq!(net.auxiliary_doors(v(1)), [v(0)]);
let proof = round_trip(&net);
assert_eq!(
proof.nodes(),
[
Node::Ax(Member::from(o(1)), Member::from(o(3))),
Node::Copy(Member::from(o(1)), NodeId::new(0)),
Node::Bang(Member::from(o(2)), NodeId::new(1)),
Node::Quest(Member::from(o(0)), NodeId::new(2)),
]
);
assert!(matches!(
build("|- ?~a, !a", &[(3, 1, Some(1)), (1, 0, None)], &[(2, 3)], &[]),
Err(Error::Net(e)) if *e == NetError::Placement { vertex: v(2), fault: Placement::Link }
));
let net = build(
"|- ?~a, !a * !a",
&[
(3, 1, None),
(5, 1, None),
(4, 2, Some(2)),
(6, 3, Some(3)),
(1, 0, Some(2)),
(1, 0, Some(3)),
],
&[(4, 6), (5, 7)],
&[],
)
.unwrap();
round_trip(&net);
let weakened = build("|- ?b, a, ~a", &[], &[(1, 2)], &[(0, 1)]).unwrap();
round_trip(&weakened);
assert_eq!(
build("|- ?b, a, ~a", &[], &[(1, 2)], &[])
.unwrap()
.is_correct(|_| false),
Err(NetError::Unattached { vertex: v(0) })
);
for literal in [1, 4, 6, 7] {
let net = build(
"|- ?c * (a par (b par ~b)), ~a",
&[
(1, 0, None),
(3, 0, None),
(4, 3, None),
(5, 3, None),
(6, 5, None),
(7, 5, None),
],
&[(4, 1), (6, 7)],
&[(2, literal)],
)
.unwrap();
assert!(
matches!(
net.is_correct(|_| false),
Err(NetError::SwitchingCycle { .. })
),
"hung on {literal}"
);
}
let vertices = [
(1, 0, Some(0)),
(2, 3, Some(0)),
(3, 3, Some(0)),
(5, 1, Some(0)),
(7, 2, Some(0)),
];
let net = build("|- !(a * b), ?~a, ?~b", &vertices, &[(4, 6), (5, 7)], &[]).unwrap();
round_trip(&net);
let net = build("|- !(a par b), ?~a, ?~b", &vertices, &[(4, 6), (5, 7)], &[]).unwrap();
let Err(NetError::InBox { door, error }) = net.is_correct(|_| false) else {
panic!("a box whose contents fall apart is no net");
};
assert_eq!(door, v(0));
assert!(matches!(*error, NetError::Disconnected { ref parts } if parts.len() == 2));
assert_eq!(
NetError::InBox { door, error }.describe(&net).to_string(),
"inside the box of !(a ⅋ b)[0], every switching falls into 2 parts; keeping every left \
premise, they are {a ⅋ b[3], ?~a[1]} and {b[5], ?~b[2]}"
);
}
#[test]
fn round_trips() {
let mut cases = (0, 0, 0);
for (seed, mix) in [(11, false), (12, true)] {
let mut rng = Rng::new(seed);
for _ in 0..120 {
let rules = Rules {
units: false,
additives: false,
mix,
exponentials: true,
};
let budget = 2 + rng.below(10);
let provable = generate::provable(&mut rng, rules, 3, budget);
let text = generate::sequent(&provable.formulas);
let sequent: Sequent = text.parse().unwrap();
let mode = if mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
let Some(proof) = proof_of(&sequent, mode, provable.copies) else {
continue;
};
let criterion = Criterion {
mix,
..Criterion::MLL
};
let net = MellStructure::from_proof(&proof, criterion, &Limits::default(), |_| false)
.unwrap_or_else(|e| panic!("{text:?}: {e}"));
round_trip(&net);
cases.0 += 1;
if net.boxes().next().is_some() {
cases.1 += 1;
}
if net.vertices().any(|q| net.hangs_on(q).is_some()) {
cases.2 += 1;
}
}
}
assert!(cases.0 > 100 && cases.1 > 30 && cases.2 > 10, "{cases:?}");
}
#[test]
fn agrees_with_the_multiplicative_criterion() {
let mut rng = Rng::new(21);
let mut verdicts = [0; 2];
for i in 0..300 {
let rules = Rules {
units: false,
additives: false,
mix: i % 3 == 2,
exponentials: false,
};
let budget = 2 + rng.below(9);
let mut formulas = generate::provable(&mut rng, rules, 3, budget).formulas;
if i % 2 == 1 {
generate::mutate(&mut rng, &mut formulas, 3);
}
let s: Sequent = generate::sequent(&formulas).parse().unwrap();
let forest = Forest::new(&s).unwrap();
let mut links = Vec::new();
for a in 0..s.atom_names().len() {
let atom = crate::linear::sequents::Atom::new(a as u32);
let atoms = forest.literals(atom, crate::linear::occurrences::Sign::Atom);
let mut duals = forest
.literals(atom, crate::linear::occurrences::Sign::Dual)
.to_vec();
for k in (1..duals.len()).rev() {
duals.swap(k, rng.below(k + 1));
}
links.extend(atoms.iter().zip(duals).map(|(&x, y)| (x, y)));
}
let mix = i % 4 == 0;
let criterion = Criterion {
mix,
..Criterion::MLL
};
let pairs: Vec<_> = links
.iter()
.map(|&(x, y)| (v(x.get()), v(y.get())))
.collect();
let mll = ProofStructure::from_links(forest.clone(), criterion, &pairs).unwrap();
let roots = forest.roots().len() as u32;
let mut vertex = vec![0; forest.len()];
for (i, &r) in forest.roots().iter().enumerate() {
vertex[r.index()] = i as u32;
}
let mut next = roots;
let mut vertices = Vec::new();
for occurrence in forest.ids() {
if let Some(p) = forest.parent(occurrence) {
vertex[occurrence.index()] = next;
next += 1;
vertices.push(Placed::new(occurrence, v(vertex[p.index()]), None));
}
}
let parts = Parts {
vertices,
cuts: Vec::new(),
links: links
.iter()
.map(|&(x, y)| (v(vertex[x.index()]), v(vertex[y.index()])))
.collect(),
weakenings: Vec::new(),
};
let net = MellStructure::from_parts(forest, criterion, &parts, &Limits::default()).unwrap();
let expected = mll.is_correct(|_| false).is_ok();
assert_eq!(
net.is_correct(|_| false).is_ok(),
expected,
"{s} with {links:?}"
);
verdicts[usize::from(expected)] += 1;
if expected {
round_trip(&net);
}
}
assert!(verdicts[0] > 50 && verdicts[1] > 50, "{verdicts:?}");
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Place {
Vertex(u32),
Door(u32),
}
type Edge = (Place, Place, Option<Place>);
fn find(parent: &[usize], mut x: usize) -> usize {
while parent[x] != x {
x = parent[x];
}
x
}
fn enumerate(net: &MellStructure) -> Option<bool> {
let f = net.forest();
let kind = |x: VertexId| f.kind(net.occurrence(x).unwrap());
let mut depths: Vec<Option<VertexId>> = vec![None];
depths.extend(net.boxes().map(Some));
for depth in depths {
let mut nodes: Vec<Place> = net
.vertices()
.filter(|&x| net.inside(x) == depth)
.map(|x| Place::Vertex(x.get()))
.collect();
let mut edges: Vec<Edge> = Vec::new();
let add = |edges: &mut Vec<Edge>, e: Edge| {
if !edges.contains(&e) {
edges.push(e);
}
};
for x in net.vertices().filter(|&x| net.inside(x) == depth) {
if let Some(p) = net.partner(x)
&& p > x
{
add(
&mut edges,
(Place::Vertex(x.get()), Place::Vertex(p.get()), None),
);
}
if matches!(kind(x), Kind::Tensor | Kind::Par) {
for c in net.premises(x) {
let switch = (kind(x) == Kind::Par).then_some(Place::Vertex(x.get()));
add(
&mut edges,
(Place::Vertex(x.get()), Place::Vertex(c.get()), switch),
);
}
}
}
for q in net.vertices().filter(|&q| kind(q) == Kind::Quest) {
let ends: Vec<VertexId> = net.premises(q).chain(net.hangs_on(q)).collect();
for end in ends {
let mut at = end;
let mut b = net.inside(end);
loop {
let here = b;
let source = if here == net.inside(q) {
Place::Vertex(q.get())
} else {
Place::Door(q.get())
};
if here == depth {
if source != Place::Vertex(q.get()) && !nodes.contains(&source) {
nodes.push(source);
}
add(&mut edges, (source, Place::Vertex(at.get()), Some(source)));
}
if here == net.inside(q) {
break;
}
let bang = here.unwrap();
at = bang;
b = net.inside(bang);
}
}
}
let switched: Vec<Place> = {
let mut s: Vec<Place> = edges.iter().filter_map(|e| e.2).collect();
s.sort_by_key(|p| format!("{p:?}"));
s.dedup();
s
};
let choices: Vec<Vec<usize>> = switched
.iter()
.map(|&s| {
(0..edges.len())
.filter(|&i| edges[i].2 == Some(s))
.collect()
})
.collect();
let count: usize = choices.iter().map(Vec::len).product();
if count > 4096 {
return None;
}
for mut k in 0..count {
let mut kept: Vec<usize> = (0..edges.len()).filter(|&i| edges[i].2.is_none()).collect();
for c in &choices {
kept.push(c[k % c.len()]);
k /= c.len();
}
let index = |p: Place| nodes.iter().position(|&q| q == p).unwrap();
let mut parent: Vec<usize> = (0..nodes.len()).collect();
for &i in &kept {
let (a, b) = (
find(&parent, index(edges[i].0)),
find(&parent, index(edges[i].1)),
);
if a == b {
return Some(false);
}
parent[a] = b;
}
if !net.criterion().mix && kept.len() + 1 != nodes.len() {
return Some(false);
}
}
}
Some(true)
}
#[test]
fn agrees_with_enumeration() {
let mut cases = [0; 2];
for (seed, mix) in [(31, false), (32, true)] {
let mut rng = Rng::new(seed);
for _ in 0..150 {
let rules = Rules {
units: false,
additives: false,
mix,
exponentials: true,
};
let budget = 2 + rng.below(8);
let provable = generate::provable(&mut rng, rules, 2, budget);
let sequent: Sequent = generate::sequent(&provable.formulas).parse().unwrap();
let mode = if mix {
Mode::CLASSICAL.with_mix()
} else {
Mode::CLASSICAL
};
let Some(proof) = proof_of(&sequent, mode, provable.copies) else {
continue;
};
let criterion = Criterion {
mix,
..Criterion::MLL
};
let net = MellStructure::from_proof(&proof, criterion, &Limits::default(), |_| false)
.unwrap();
for round in 0..8 {
let mut parts = net.parts();
if round > 0 {
mutate(&net, &mut parts, &mut rng);
}
let Ok(mutant) = MellStructure::from_parts(
net.forest().clone(),
criterion,
&parts,
&Limits::default(),
) else {
continue;
};
let Some(expected) = enumerate(&mutant) else {
continue;
};
let verdict = mutant.is_correct(|_| false);
assert_eq!(verdict.is_ok(), expected, "{mutant:?}: {verdict:?}");
cases[usize::from(expected)] += 1;
if expected {
round_trip(&mutant);
}
}
}
}
assert!(cases[0] > 30 && cases[1] > 100, "{cases:?}");
}
#[test]
fn intuitionistic_nets() {
assert_eq!(
MellStructure::exist(Fragment::MELL, Mode::INTUITIONISTIC),
Err(NetError::NotMell {
fragment: Fragment::MELL,
mode: Mode::INTUITIONISTIC
})
);
let imell = Fragment::MLL.union(Fragment::EXPONENTIALS);
assert_eq!(MellStructure::exist(imell, Mode::INTUITIONISTIC), Ok(()));
for affine in [
Mode::INTUITIONISTIC.with_affine(),
Mode::CLASSICAL.with_affine(),
] {
assert!(MellStructure::exist(imell, affine).is_err(), "{affine}");
}
let text = "|- !((a -o a) * (a -o a))";
let vertices = [
(1, 0, Some(0)),
(2, 1, Some(0)),
(3, 2, Some(0)),
(4, 2, Some(0)),
(5, 1, Some(0)),
(6, 5, Some(0)),
(7, 5, Some(0)),
];
let net = build(text, &vertices, &[(3, 4), (6, 7)], &[]).unwrap();
let proof = round_trip(&net);
assert_eq!(proof.check(Mode::INTUITIONISTIC), Ok(()));
let crossed = build(text, &vertices, &[(3, 7), (6, 4)], &[]).unwrap();
assert!(
matches!(
crossed.is_correct(|_| false),
Err(NetError::InBox { door, error })
if door == v(0) && matches!(*error, NetError::SwitchingCycle { .. })
),
"{:?}",
crossed.is_correct(|_| false)
);
let criterion = Criterion::of(Mode::INTUITIONISTIC).unwrap();
let rules = IllRules {
units: false,
additives: false,
zero: false,
exponentials: true,
};
let mut rng = Rng::new(41);
let mut cases = [0; 3];
for _ in 0..200 {
let budget = 2 + rng.below(9);
let ill = generate::ill(&mut rng, rules, 2, budget);
let text = generate::two_sided(&ill.hypotheses, &ill.goal);
let sequent: Sequent = text.parse().unwrap();
let Some(proof) = proof_of(&sequent, Mode::INTUITIONISTIC, ill.copies) else {
continue;
};
let net = MellStructure::from_proof(&proof, criterion, &Limits::default(), |_| false)
.unwrap_or_else(|e| panic!("{text:?}: {e}"));
assert!(net.reading().is_ok(), "{text:?}");
cases[2] += usize::from(net.boxes().next().is_some());
for round in 0..8 {
let mut parts = net.parts();
if round > 0 {
mutate(&net, &mut parts, &mut rng);
}
let Ok(mutant) = MellStructure::from_parts(
net.forest().clone(),
criterion,
&parts,
&Limits::default(),
) else {
continue;
};
let verdict = mutant.is_correct(|_| false);
if let Some(expected) = enumerate(&mutant) {
assert_eq!(verdict.is_ok(), expected, "{mutant:?}: {verdict:?}");
}
cases[usize::from(verdict.is_ok())] += 1;
if verdict.is_ok() {
let term = round_trip(&mutant);
assert_eq!(
term.check(Mode::INTUITIONISTIC),
Ok(()),
"{text:?}: {mutant:?}"
);
}
}
}
assert!(
cases[0] > 30 && cases[1] > 150 && cases[2] > 40,
"{cases:?}"
);
}
fn mutate(net: &MellStructure, parts: &mut Parts, rng: &mut Rng) {
let roots = net.forest().roots().len();
match rng.below(3) {
0 if parts.links.len() >= 2 => {
let (i, j) = (rng.below(parts.links.len()), rng.below(parts.links.len()));
let ((a, b), (c, d)) = (parts.links[i], parts.links[j]);
if net
.forest()
.dual_literals(net.occurrence(a).unwrap(), net.occurrence(d).unwrap())
{
parts.links[i] = (a, d);
parts.links[j] = (c, b);
}
}
1 => {
let copies: Vec<usize> = (0..parts.vertices.len())
.filter(|&i| {
let p = parts.vertices[i].parent.unwrap();
net.forest().kind(net.occurrence(p).unwrap()) == Kind::Quest
})
.collect();
let boxes: Vec<VertexId> = net.boxes().collect();
if let (false, false) = (copies.is_empty(), boxes.is_empty()) {
let i = copies[rng.below(copies.len())];
let b = boxes[rng.below(boxes.len())];
let inside = if rng.one_in(3) { None } else { Some(b) };
let moved = VertexId::new((roots + i) as u32);
let old = parts.vertices[i].inside;
for k in 0..parts.vertices.len() {
let mut x = Some(VertexId::new((roots + k) as u32));
while let Some(y) = x
&& y != moved
{
x = net.parent(y);
}
if x.is_some() && parts.vertices[k].inside == old {
parts.vertices[k].inside = inside;
}
}
}
}
_ if !parts.weakenings.is_empty() => {
let i = rng.below(parts.weakenings.len());
let literals: Vec<VertexId> = net
.vertices()
.filter(|&x| net.forest().is_literal(net.occurrence(x).unwrap()))
.collect();
parts.weakenings[i].1 = literals[rng.below(literals.len())];
}
_ => {}
}
}
#[test]
fn an_unfolding_past_the_vertices_is_refused() {
let f = forest("|- ?(a par ~a)");
let m = |id| Member::from(o(id));
let mut nodes = vec![Node::Ax(m(2), m(3)), Node::Par(m(1), NodeId::new(0))];
for _ in 0..48 {
let last = NodeId::new(nodes.len() as u32 - 1);
nodes.push(Node::Mix(last, last));
nodes.push(Node::Copy(m(1), NodeId::new(nodes.len() as u32 - 1)));
}
nodes.push(Node::Copy(m(1), NodeId::new(nodes.len() as u32 - 1)));
nodes.push(Node::Quest(m(0), NodeId::new(nodes.len() as u32 - 1)));
let root = NodeId::new(nodes.len() as u32 - 1);
let proof = Proof::new(f, nodes, root).unwrap();
let mix = Mode::CLASSICAL.with_mix();
assert_eq!(proof.check(mix), Ok(()));
let criterion = Criterion::MLL.with_mix();
let refused = MellStructure::from_proof(&proof, criterion, &Limits::default(), |_| false);
assert!(
matches!(refused, Err(Error::Refused(Refusal::Index { count, .. })) if count > 1 << 49),
"{refused:?}"
);
}
#[test]
fn text_form() {
let sequent: Sequent = "!a, !b |- !a".parse().unwrap();
let outcome =
crate::linear::search::prove(&sequent, Mode::CLASSICAL, &Options::default()).unwrap();
let Verdict::Proved(proof) = &outcome.verdict else {
panic!("{:?}", outcome.verdict);
};
let net =
MellStructure::from_proof(proof, Criterion::MLL, &Limits::default(), |_| false).unwrap();
assert_eq!(
net.to_string(),
"⊢ ?~a, ?~b, !a\n?~a[0]: ~a[3] in !a[2]\n?~b[1]: no copy, hangs on a[4]\n~a[3] — a[4]\nproof net"
);
}