use super::refutation::{RefutationFault, Saturated, Stable};
use crate::hash::HashMap;
use crate::linear::fragment::Mode;
use crate::linear::occurrences::{Forest, OccId, Reading, Side, Sign};
use crate::linear::sequents::Kind;
#[derive(Debug, PartialEq, Eq)]
pub(crate) enum Failed {
Fault(RefutationFault),
Stopped,
}
impl From<RefutationFault> for Failed {
fn from(fault: RefutationFault) -> Self {
Failed::Fault(fault)
}
}
const UNITS_PER_POLL: u64 = 1 << 16;
#[derive(Clone, Debug, Default, PartialEq, Eq)]
struct Zone {
linear: Vec<OccId>,
unrestricted: Vec<OccId>,
absorbs: bool,
}
#[derive(Clone, Copy, Debug)]
enum Step {
Axiom(OccId, usize),
One(OccId),
Top(OccId),
Hole(usize),
Tensor(OccId),
Plus(OccId, OccId),
Bang(OccId),
Par(OccId),
Bot(OccId),
Quest(OccId),
With(OccId),
Copy(OccId),
}
#[derive(Clone, Copy, Debug)]
struct Partner {
literal: OccId,
unrestricted: bool,
}
#[derive(Clone, Debug)]
struct Hole {
leaves: Vec<OccId>,
met: Vec<OccId>,
release: usize,
}
#[derive(Debug, Default)]
struct Rule {
steps: Vec<Step>,
holes: Vec<Hole>,
slots: Vec<Vec<Partner>>,
}
#[derive(Clone, Copy)]
enum Start<'g> {
Focus(OccId),
Copy(OccId),
Goal(&'g [OccId]),
}
enum Pending {
Focus(OccId),
Phase(Phase),
}
#[derive(Clone, Default)]
struct Phase {
top: Option<OccId>,
unary: Vec<OccId>,
withs: Vec<OccId>,
leaves: Vec<OccId>,
met: Vec<OccId>,
release: usize,
}
struct Calculus<'a> {
forest: &'a Forest,
positive: &'a [Sign],
reading: Option<Reading<'a>>,
affine: bool,
copied: Vec<bool>,
inside: Vec<bool>,
goal: Vec<OccId>,
globals: Vec<OccId>,
}
impl<'a> Calculus<'a> {
fn positive(&self, o: OccId) -> bool {
match self.forest.kind(o) {
Kind::Tensor | Kind::One | Kind::Plus | Kind::Zero | Kind::Bang | Kind::Exists => true,
Kind::Atom | Kind::DualAtom => {
self.forest.atom(o).map(|a| self.positive[a.index()]) == self.forest.sign(o)
}
Kind::Par | Kind::Bot | Kind::With | Kind::Top | Kind::Quest | Kind::Forall => false,
}
}
fn stable(&self, o: OccId) -> bool {
self.positive(o) || self.forest.is_literal(o)
}
fn output(&self, o: OccId) -> bool {
self.reading
.as_ref()
.is_some_and(|r| r.position(o) == Side::Output)
}
fn outputs(&self, list: &[OccId]) -> usize {
list.iter().filter(|&&o| self.output(o)).count()
}
fn weak(&self, z: &Zone) -> bool {
z.absorbs || self.affine
}
fn shaped(&self, z: &Zone) -> bool {
self.reading.is_none() || {
let outputs = self.outputs(&z.linear);
outputs == 1 || (outputs == 0 && z.absorbs)
}
}
fn coherent(&self, x: OccId, y: OccId) -> bool {
let Some(w) = self.forest.lca(x, y) else {
return true;
};
self.forest.kind(w) == Kind::Quest
|| self.copied[w.index()]
|| (w != x && w != y && self.forest.kind(w) == Kind::Par)
}
fn coherent_list(&self, sorted: &[OccId]) -> bool {
sorted.windows(2).all(|w| self.coherent(w[0], w[1]))
}
fn place(&self, phase: &mut Phase, o: OccId) {
if self.stable(o) {
phase.leaves.push(o);
return;
}
match self.forest.kind(o) {
Kind::Top => {
phase.top.get_or_insert(o);
}
Kind::With => phase.withs.push(o),
_ => phase.unary.push(o),
}
}
fn partners(&self, p: OccId) -> Vec<Partner> {
let forest = self.forest;
let (Some(atom), Some(sign)) = (forest.atom(p), forest.sign(p)) else {
return Vec::new();
};
let mut found = Vec::new();
for &x in forest.literals(atom, !sign) {
if !self.inside[x.index()] {
continue;
}
if self.reading.is_some() && self.output(x) == self.output(p) {
continue;
}
let quest = forest
.parent(x)
.is_some_and(|q| forest.kind(q) == Kind::Quest);
if quest {
found.push(Partner {
literal: x,
unrestricted: true,
});
}
if !quest || self.goal.binary_search(&x).is_ok() {
found.push(Partner {
literal: x,
unrestricted: false,
});
}
}
found
}
fn write(&self, start: Start<'_>, sides: &[(OccId, OccId)]) -> Rule {
let forest = self.forest;
let mut rule = Rule::default();
let mut found: Vec<Step> = Vec::new();
let mut releases = 0;
let mut release = |phase: &mut Phase| {
phase.release = releases;
releases += 1;
};
let under_focus = |o: OccId, release: &mut dyn FnMut(&mut Phase)| {
if self.positive(o) {
Pending::Focus(o)
} else {
let mut phase = Phase::default();
release(&mut phase);
self.place(&mut phase, o);
Pending::Phase(phase)
}
};
let root = match start {
Start::Focus(o) => Pending::Focus(o),
Start::Copy(o) => {
found.push(Step::Copy(o));
under_focus(o, &mut release)
}
Start::Goal(members) => {
let mut phase = Phase::default();
release(&mut phase);
for &o in members {
self.place(&mut phase, o);
}
Pending::Phase(phase)
}
};
let mut stack = vec![root];
while let Some(pending) = stack.pop() {
match pending {
Pending::Focus(o) => match forest.kind(o) {
Kind::Tensor => {
found.push(Step::Tensor(o));
let (l, r) = (forest.left(o), forest.right(o));
for c in [l, r].into_iter().flatten() {
stack.push(under_focus(c, &mut release));
}
}
Kind::Plus => {
let Some(&(_, child)) = sides.iter().find(|&&(p, _)| p == o) else {
unreachable!("every ⊕ under the focus has a side");
};
found.push(Step::Plus(o, child));
stack.push(under_focus(child, &mut release));
}
Kind::One => found.push(Step::One(o)),
Kind::Bang => {
found.push(Step::Bang(o));
let mut phase = Phase::default();
release(&mut phase);
if let Some(c) = forest.left(o) {
self.place(&mut phase, c);
}
stack.push(Pending::Phase(phase));
}
Kind::Atom | Kind::DualAtom => {
found.push(Step::Axiom(o, rule.slots.len()));
rule.slots.push(self.partners(o));
}
Kind::Zero
| Kind::Par
| Kind::Bot
| Kind::With
| Kind::Top
| Kind::Quest
| Kind::Forall
| Kind::Exists => {
unreachable!("no focus on a 0, a negative formula or a binder")
}
},
Pending::Phase(mut phase) => loop {
if let Some(t) = phase.top {
found.push(Step::Top(t));
break;
}
if let Some(o) = phase.unary.pop() {
match forest.kind(o) {
Kind::Par => {
found.push(Step::Par(o));
for c in forest.children(o) {
self.place(&mut phase, c);
}
}
Kind::Bot => found.push(Step::Bot(o)),
Kind::Quest => {
found.push(Step::Quest(o));
phase.met.extend(forest.left(o));
}
_ => unreachable!("only ⅋, ⊥ and ? are unary"),
}
continue;
}
if let Some(o) = phase.withs.pop() {
found.push(Step::With(o));
let mut left = phase.clone();
left.place_child(self, forest.left(o));
phase.place_child(self, forest.right(o));
stack.push(Pending::Phase(left));
continue;
}
phase.leaves.sort_unstable();
phase.met.sort_unstable();
found.push(Step::Hole(rule.holes.len()));
rule.holes.push(Hole {
leaves: phase.leaves,
met: phase.met,
release: phase.release,
});
break;
},
}
}
found.reverse();
rule.steps = found;
rule
}
}
impl Phase {
fn place_child(&mut self, calculus: &Calculus<'_>, o: Option<OccId>) {
if let Some(o) = o {
calculus.place(self, o);
}
}
}
fn insert(list: &mut Vec<OccId>, o: OccId) {
let at = list.partition_point(|&x| x <= o);
list.insert(at, o);
}
fn sum(a: &[OccId], b: &[OccId]) -> Vec<OccId> {
let mut out = Vec::with_capacity(a.len() + b.len());
let (mut i, mut j) = (0, 0);
while i < a.len() || j < b.len() {
if j == b.len() || (i < a.len() && a[i] <= b[j]) {
out.push(a[i]);
i += 1;
} else {
out.push(b[j]);
j += 1;
}
}
out
}
fn union(a: &[OccId], b: &[OccId]) -> Vec<OccId> {
let mut out = sum(a, b);
out.dedup();
out
}
fn excess(of: &[OccId], within: &[OccId]) -> Vec<OccId> {
let mut out = Vec::new();
let mut j = 0;
for &o in of {
while j < within.len() && within[j] < o {
j += 1;
}
if j < within.len() && within[j] == o {
j += 1;
} else {
out.push(o);
}
}
out
}
fn within(small: &[OccId], large: &[OccId]) -> bool {
let mut j = 0;
for &o in small {
while j < large.len() && large[j] < o {
j += 1;
}
if j == large.len() || large[j] != o {
return false;
}
j += 1;
}
true
}
fn sorted(list: &[OccId], set: bool) -> bool {
list.windows(2)
.all(|w| w[0] < w[1] || (!set && w[0] == w[1]))
}
impl Calculus<'_> {
fn take(&self, z: &mut Zone, o: OccId) -> bool {
if let Ok(at) = z.linear.binary_search(&o) {
z.linear.remove(at);
return true;
}
if z.absorbs {
return !(self.output(o) && self.outputs(&z.linear) > 0);
}
self.affine && !self.output(o)
}
fn join(&self, l: Zone, r: Zone) -> Option<Zone> {
let most = sum(&l.linear, &excess(&r.linear, &l.linear));
let joined = match (l.absorbs, r.absorbs) {
(true, true) => true,
(false, false) => l.linear == r.linear,
(true, false) => within(&l.linear, &r.linear),
(false, true) => within(&r.linear, &l.linear),
};
if !joined {
let weakened = |side: &Zone| {
side.absorbs || excess(&most, &side.linear).iter().all(|&o| !self.output(o))
};
if !(self.affine && weakened(&l) && weakened(&r)) {
return None;
}
}
Some(Zone {
linear: most,
unrestricted: union(&l.unrestricted, &r.unrestricted),
absorbs: l.absorbs && r.absorbs,
})
}
fn derive(
&self,
rule: &Rule,
set: &[Zone],
premises: &[usize],
partners: &[usize],
units: &mut u64,
) -> Option<Zone> {
let forest = self.forest;
let mut stack: Vec<Zone> = Vec::new();
for &step in &rule.steps {
let z = match step {
Step::Axiom(p, slot) => {
let partner = rule.slots[slot][partners[slot]];
let mut z = Zone {
linear: vec![p],
..Zone::default()
};
if partner.unrestricted {
z.unrestricted.push(partner.literal);
} else {
insert(&mut z.linear, partner.literal);
}
z
}
Step::One(o) => Zone {
linear: vec![o],
..Zone::default()
},
Step::Top(o) => Zone {
linear: vec![o],
unrestricted: Vec::new(),
absorbs: true,
},
Step::Hole(h) => set[premises[h]].clone(),
Step::Tensor(o) => {
let mut r = stack.pop()?;
let mut l = stack.pop()?;
if !self.take(&mut l, forest.left(o)?) || !self.take(&mut r, forest.right(o)?) {
return None;
}
let mut z = Zone {
linear: sum(&l.linear, &r.linear),
unrestricted: union(&l.unrestricted, &r.unrestricted),
absorbs: l.absorbs || r.absorbs,
};
insert(&mut z.linear, o);
z
}
Step::Plus(o, child) => {
let mut z = stack.pop()?;
if !self.take(&mut z, child) {
return None;
}
insert(&mut z.linear, o);
z
}
Step::Bang(o) => {
let mut z = stack.pop()?;
if !self.take(&mut z, forest.left(o)?) || !z.linear.is_empty() {
return None;
}
z.absorbs = false;
insert(&mut z.linear, o);
z
}
Step::Par(o) => {
let mut z = stack.pop()?;
if !self.take(&mut z, forest.left(o)?) || !self.take(&mut z, forest.right(o)?) {
return None;
}
insert(&mut z.linear, o);
z
}
Step::Bot(o) => {
let mut z = stack.pop()?;
insert(&mut z.linear, o);
z
}
Step::Quest(o) => {
let mut z = stack.pop()?;
let a = forest.left(o)?;
z.unrestricted.retain(|&x| x != a);
insert(&mut z.linear, o);
z
}
Step::With(o) => {
let mut r = stack.pop()?;
let mut l = stack.pop()?;
if !self.take(&mut l, forest.left(o)?) || !self.take(&mut r, forest.right(o)?) {
return None;
}
let mut z = self.join(l, r)?;
insert(&mut z.linear, o);
z
}
Step::Copy(o) => {
let mut z = stack.pop()?;
if !self.take(&mut z, o) {
return None;
}
z.unrestricted = union(&z.unrestricted, &[o]);
z
}
};
*units += 1 + (z.linear.len() + z.unrestricted.len()) as u64;
if !self.shaped(&z) {
return None;
}
stack.push(z);
}
let z = stack.pop()?;
stack.is_empty().then_some(z)
}
fn rules(
&self,
work: &mut Work<'_>,
each: &mut dyn FnMut(&Rule, &mut Work<'_>) -> Result<(), Failed>,
) -> Result<(), Failed> {
let forest = self.forest;
let mut previous = None;
for &g in &self.goal {
if previous.replace(g) == Some(g) {
continue;
}
for o in forest.subtree(g) {
let parent = forest.parent(o).filter(|_| o != g).map(|p| forest.kind(p));
let mut starts = Vec::new();
if self.positive(o)
&& matches!(parent, None | Some(Kind::Par | Kind::With | Kind::Bang))
{
starts.push(Start::Focus(o));
}
if parent == Some(Kind::Quest) && !(forest.is_literal(o) && !self.positive(o)) {
starts.push(Start::Copy(o));
}
for start in starts {
let mut open: Vec<Vec<(OccId, OccId)>> = vec![Vec::new()];
'plans: while let Some(sides) = open.pop() {
work.add(1)?;
let mut walk = vec![o];
while let Some(x) = walk.pop() {
match forest.kind(x) {
Kind::Tensor => {
walk.extend(forest.children(x).filter(|&c| self.positive(c)))
}
Kind::Plus => match sides.iter().find(|&&(p, _)| p == x) {
Some(&(_, child)) => {
if self.positive(child) {
walk.push(child);
}
}
None => {
for child in forest.children(x) {
let mut more = sides.clone();
more.push((x, child));
open.push(more);
}
continue 'plans;
}
},
Kind::Zero => continue 'plans,
_ => {}
}
}
let rule = self.write(start, &sides);
work.add(rule.steps.len() as u64)?;
each(&rule, work)?;
}
}
}
}
Ok(())
}
}
struct Work<'s> {
unpolled: u64,
stop: &'s mut dyn FnMut(u64) -> bool,
}
impl Work<'_> {
fn add(&mut self, units: u64) -> Result<(), Failed> {
self.unpolled = self.unpolled.saturating_add(units);
if self.unpolled >= UNITS_PER_POLL && (self.stop)(std::mem::take(&mut self.unpolled)) {
return Err(Failed::Stopped);
}
Ok(())
}
}
struct Set {
zones: Vec<Zone>,
exact: HashMap<Vec<OccId>, Vec<usize>>,
holding: HashMap<OccId, Vec<usize>>,
exact_empty: Vec<usize>,
weak: Vec<usize>,
weak_first: HashMap<OccId, Vec<usize>>,
weak_empty: Vec<usize>,
}
impl Set {
fn new(calculus: &Calculus<'_>, zones: Vec<Zone>) -> Self {
let mut set = Set {
zones: Vec::new(),
exact: HashMap::default(),
holding: HashMap::default(),
exact_empty: Vec::new(),
weak: Vec::new(),
weak_first: HashMap::default(),
weak_empty: Vec::new(),
};
for (i, z) in zones.iter().enumerate() {
if calculus.weak(z) {
set.weak.push(i);
match z.linear.first() {
Some(&o) => set.weak_first.entry(o).or_default().push(i),
None => set.weak_empty.push(i),
}
} else {
set.exact.entry(z.linear.clone()).or_default().push(i);
let mut members = z.linear.clone();
members.dedup();
for o in members {
set.holding.entry(o).or_default().push(i);
}
if z.linear.is_empty() {
set.exact_empty.push(i);
}
}
}
set.zones = zones;
set
}
fn candidates(&self, hole: &Hole, work: &mut Work<'_>) -> Result<Vec<usize>, Failed> {
let mut out: Vec<usize> = match hole.leaves.first() {
None => self.exact.values().flatten().copied().collect(),
Some(o) => {
let holding = self.holding.get(o).map_or(&[][..], Vec::as_slice);
let compared: usize = holding.iter().map(|&i| self.zones[i].linear.len()).sum();
work.add((holding.len() + compared) as u64)?;
holding
.iter()
.copied()
.filter(|&i| within(&hole.leaves, &self.zones[i].linear))
.collect()
}
};
out.extend(&self.weak);
work.add(out.len() as u64)?;
Ok(out)
}
fn subsumes(
&self,
calculus: &Calculus<'_>,
c: &Zone,
work: &mut Work<'_>,
) -> Result<bool, Failed> {
if !calculus.weak(c)
&& let Some(list) = self.exact.get(&c.linear)
{
for &i in list {
work.add(1 + self.zones[i].unrestricted.len() as u64)?;
if within(&self.zones[i].unrestricted, &c.unrestricted) {
return Ok(true);
}
}
}
let mut firsts = c.linear.clone();
firsts.dedup();
let lists = firsts
.iter()
.filter_map(|o| self.weak_first.get(o))
.chain([&self.weak_empty]);
for list in lists {
for &i in list {
let s = &self.zones[i];
work.add(1 + (s.linear.len() + s.unrestricted.len()) as u64)?;
if within(&s.linear, &c.linear) && within(&s.unrestricted, &c.unrestricted) {
return Ok(true);
}
}
}
Ok(false)
}
}
pub(crate) fn check(
forest: &Forest,
goal: &[OccId],
mode: Mode,
saturated: &Saturated,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<(), Failed> {
const INVARIANT: &str = "saturation";
let not_applicable = |why| {
Failed::Fault(RefutationFault::NotApplicable {
invariant: INVARIANT,
why,
})
};
if mode.is_ordered() {
return Err(not_applicable(
"its rules are those of the commutative modes",
));
}
if mode.intuitionistic && mode.has_mix() {
return Err(not_applicable("intuitionistic mode has no Mix"));
}
if saturated.positive.len() != forest.sequent().atom_names().len() {
return Err(RefutationFault::Mismatch.into());
}
let len = forest.len();
let ours =
|list: &[OccId], set: bool| sorted(list, set) && list.iter().all(|o| o.index() < len);
if !saturated
.sequents
.iter()
.all(|s| ours(&s.linear, false) && ours(&s.unrestricted, true))
{
return Err(RefutationFault::Mismatch.into());
}
let reading = if mode.intuitionistic {
Some(
Reading::of_mode(forest, mode)
.map_err(|_| not_applicable("the sequent has no intuitionistic reading"))?,
)
} else {
None
};
let mut copied = vec![false; len];
for i in 0..len {
let o = OccId::new(i as u32);
if let Some(p) = forest.parent(o) {
copied[i] = copied[p.index()] || forest.kind(p) == Kind::Quest;
}
}
let mut members = goal.to_vec();
members.sort_unstable();
let mut inside = vec![false; len];
for &g in goal {
for o in forest.subtree(g) {
inside[o.index()] = true;
}
}
let mut globals = Vec::new();
let mut walk = members.clone();
while let Some(o) = walk.pop() {
match forest.kind(o) {
Kind::Par => walk.extend(forest.children(o)),
Kind::Quest => globals.extend(forest.left(o)),
_ => {}
}
}
globals.sort_unstable();
globals.dedup();
let calculus = Calculus {
forest,
positive: &saturated.positive,
reading,
affine: mode.is_affine(),
copied,
inside,
goal: members,
globals,
};
if !calculus.coherent_list(&calculus.goal) {
return Err(not_applicable(
"two members of the goal can stand in no sequent of a proof together",
));
}
let zones: Vec<Zone> = saturated
.sequents
.iter()
.map(|s: &Stable| Zone {
linear: s.linear.clone(),
unrestricted: s.unrestricted.clone(),
absorbs: s.absorbs,
})
.collect();
if !zones.iter().all(|z| calculus.shaped(z)) {
return Err(RefutationFault::Unshaped.into());
}
let set = Set::new(&calculus, zones);
let mut work = Work { unpolled: 0, stop };
let closed = |mut c: Zone, work: &mut Work<'_>| -> Result<(), Failed> {
c.unrestricted
.retain(|o| calculus.globals.binary_search(o).is_err());
work.add((c.linear.len() + c.unrestricted.len()) as u64)?;
let all = sum(&c.linear, &c.unrestricted);
if !calculus.coherent_list(&all) || set.subsumes(&calculus, &c, work)? {
return Ok(());
}
Err(RefutationFault::NotClosed.into())
};
calculus.rules(&mut work, &mut |rule, work| {
let lists = rule
.holes
.iter()
.map(|h| set.candidates(h, work))
.collect::<Result<Vec<Vec<usize>>, Failed>>()?;
if lists.iter().any(Vec::is_empty) || rule.slots.iter().any(Vec::is_empty) {
return Ok(());
}
let contexts: Vec<Vec<Vec<OccId>>> = rule
.holes
.iter()
.zip(&lists)
.map(|(h, list)| {
list.iter()
.map(|&i| excess(&set.zones[i].linear, &h.leaves))
.collect()
})
.collect();
let compared: usize = lists
.iter()
.flatten()
.map(|&i| set.zones[i].linear.len())
.sum();
work.add(compared as u64)?;
let fits = |at: &[usize], j: usize| {
let p = lists[j][at[j]];
calculus.weak(&set.zones[p])
|| (0..j).all(|i| {
let q = lists[i][at[i]];
rule.holes[i].release != rule.holes[j].release
|| calculus.weak(&set.zones[q])
|| contexts[i][at[i]] == contexts[j][at[j]]
})
};
let holes = rule.holes.len();
let mut at = vec![0usize; holes];
let mut premises = vec![0usize; holes];
let mut j = 0;
loop {
if j == holes {
for (p, (&a, list)) in premises.iter_mut().zip(at.iter().zip(&lists)) {
*p = list[a];
}
let mut partners = vec![0usize; rule.slots.len()];
loop {
let mut units = 0;
let derived =
calculus.derive(rule, &set.zones, &premises, &partners, &mut units);
work.add(units)?;
if let Some(c) = derived {
closed(c, work)?;
}
let mut more = false;
for (k, p) in partners.iter_mut().enumerate() {
*p += 1;
if *p < rule.slots[k].len() {
more = true;
break;
}
*p = 0;
}
if !more {
break;
}
}
if holes == 0 {
return Ok(());
}
j = holes - 1;
at[j] += 1;
}
while at[j] < lists[j].len() && !fits(&at, j) {
work.add(1 + j as u64)?;
at[j] += 1;
}
if at[j] < lists[j].len() {
j += 1;
} else if j == 0 {
return Ok(());
} else {
at[j] = 0;
j -= 1;
at[j] += 1;
}
}
})?;
if mode.has_mix() && !calculus.affine {
for i in 0..set.zones.len() {
for k in i..set.zones.len() {
let (l, r) = (&set.zones[i], &set.zones[k]);
closed(
Zone {
linear: sum(&l.linear, &r.linear),
unrestricted: union(&l.unrestricted, &r.unrestricted),
absorbs: l.absorbs || r.absorbs,
},
&mut work,
)?;
}
}
}
let phase = calculus.write(Start::Goal(&calculus.goal), &[]);
let fills = |s: &Zone, hole: &Hole| {
within(&s.unrestricted, &hole.met)
&& within(&s.linear, &hole.leaves)
&& (calculus.weak(s) || s.linear.len() == hole.leaves.len())
&& (s.absorbs
|| excess(&hole.leaves, &s.linear)
.iter()
.all(|&o| !calculus.output(o)))
};
let mut open = false;
for hole in &phase.holes {
let mut filled = false;
for s in &set.zones {
work.add(1 + (s.linear.len() + s.unrestricted.len()) as u64)?;
if fills(s, hole) {
filled = true;
break;
}
}
if !filled {
open = true;
break;
}
}
if !open {
return Err(RefutationFault::Filled.into());
}
Ok(())
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::{Failed, check};
use crate::linear::occurrences::{Forest, OccId, Sign};
use crate::linear::search::{
Engine, Options, Refutation, RefutationFault, Saturated, Stable, Verdict, prove,
};
use crate::linear::{Mode, Sequent};
fn saturated(text: &str, mode: Mode) -> (Forest, Saturated) {
let sequent: Sequent = text.parse().unwrap();
let options = Options::default().with_engine(Some(Engine::Inverse));
let outcome = prove(&sequent, mode, &options).unwrap();
let Verdict::Unprovable(disproof) = outcome.verdict else {
panic!("{text} in {mode}: {:?}", outcome.verdict);
};
let Refutation::Saturated(set) = disproof.refutation().clone() else {
panic!("{text} in {mode}: {disproof}");
};
(Forest::new(&sequent).unwrap(), set)
}
fn checked(forest: &Forest, mode: Mode, set: &Saturated) -> Result<(), Failed> {
check(forest, forest.roots(), mode, set, &mut |_| false)
}
#[test]
fn a_goal_off_the_roots_is_refuted() {
let sequent: Sequent = "|- ((?a par ?~a) par (b * ~b)) * (a * ~a)".parse().unwrap();
let forest = Forest::new(&sequent).unwrap();
let members = [crate::linear::Member::new(1)];
let goal = crate::linear::search::Goal::new(&forest, &members).unwrap();
let options = Options::default().with_engine(Some(Engine::Inverse));
let outcome = crate::linear::search::prove_goal(
goal,
Mode::CLASSICAL,
&options,
&crate::Limits::default(),
|_| false,
)
.unwrap();
let Verdict::Unprovable(disproof) = outcome.verdict else {
panic!("{:?}", outcome.verdict);
};
assert!(matches!(disproof.refutation(), Refutation::Saturated(_)));
assert_eq!(disproof.check(), Ok(()));
}
#[test]
fn the_engines_sets_pass() {
for (text, mode) in [
("|- ?~a * ?~a, !a", Mode::CLASSICAL),
("|- ?~a * ?~a, !a", Mode::CLASSICAL.with_mix()),
("|- ?~a * ?~a, !a", Mode::CLASSICAL.with_affine()),
("|- ?(~a * ~a), !a", Mode::CLASSICAL),
("|- a, ~a, !b, ?~b", Mode::CLASSICAL),
("!(a -o b), a |- b * b", Mode::INTUITIONISTIC),
("!(a -o b), !(b -o c), a |- c * c", Mode::INTUITIONISTIC),
("!(a -o b), a |- b * b", Mode::INTUITIONISTIC.with_affine()),
] {
let (forest, set) = saturated(text, mode);
assert_eq!(checked(&forest, mode, &set), Ok(()), "{text} in {mode}");
}
}
#[test]
fn a_wrong_set_is_refused() {
let fault = |f| Err(Failed::Fault(f));
let intuitionistic = Mode::INTUITIONISTIC;
let (forest, set) = saturated("!(a -o b), a |- b * b", intuitionistic);
let refused = |set: Saturated| checked(&forest, intuitionistic, &set);
let with = |change: &dyn Fn(&mut Saturated)| {
let mut set = set.clone();
change(&mut set);
set
};
let past = OccId::new(forest.len() as u32);
assert_eq!(
refused(with(&|s| s.positive.push(Sign::Atom))),
fault(RefutationFault::Mismatch)
);
assert_eq!(
refused(with(&|s| s.sequents[0].linear.push(past))),
fault(RefutationFault::Mismatch)
);
assert_eq!(
refused(with(&|s| {
let z = &mut s.sequents[0].unrestricted;
z.extend([OccId::new(1), OccId::new(0)]);
})),
fault(RefutationFault::Mismatch)
);
let goal = forest.roots()[forest.roots().len() - 1];
assert_eq!(
refused(with(&|s| s.sequents.push(Stable::new(
vec![goal, goal],
Vec::new(),
false
)))),
fault(RefutationFault::Unshaped)
);
assert_eq!(
refused(with(&|s| s.sequents.clear())),
fault(RefutationFault::NotClosed)
);
assert!((0..set.sequents.len()).any(|i| refused(with(&|s| {
s.sequents.remove(i);
})) == fault(RefutationFault::NotClosed)));
assert_eq!(
refused(with(
&|s| s.sequents = vec![Stable::new(Vec::new(), Vec::new(), true)]
)),
fault(RefutationFault::Filled)
);
assert_eq!(
checked(&forest, Mode::CYCLIC, &set),
fault(RefutationFault::NotApplicable {
invariant: "saturation",
why: "its rules are those of the commutative modes",
})
);
let (forest, set) = saturated("|- a, ~a, !b, ?~b", Mode::CLASSICAL);
assert_eq!(
checked(&forest, Mode::CLASSICAL.with_mix(), &set),
fault(RefutationFault::NotClosed)
);
}
}