use super::Switches;
use super::split::Forced;
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::occurrences::{Forest, OccId, Sign};
use crate::linear::proofs::Branch;
use crate::linear::search::Bias;
use crate::linear::search::memory::{Account, bytes_of};
use crate::linear::search::{
Equation, OneSided, OneSidedSymbol, Reason, Refutation, Unbalanced, UnbalancedSymbol,
set_up_stopped,
};
use crate::linear::sequents::{Atom, Kind};
#[cfg(test)]
thread_local! {
static ONE_SIDED: std::cell::Cell<bool> = const { std::cell::Cell::new(true) };
}
#[cfg(test)]
pub(crate) fn without_one_sided<T>(f: impl FnOnce() -> T) -> T {
struct Restore;
impl Drop for Restore {
fn drop(&mut self) {
ONE_SIDED.set(true);
}
}
ONE_SIDED.set(false);
let _restore = Restore;
f()
}
pub(crate) const fn intervals_run(mode: Mode, absorbs_from_copies: bool) -> bool {
!mode.affine && !absorbs_from_copies
}
#[derive(Clone, Debug)]
pub(crate) struct Counts {
bound: Box<[u32]>,
entries: Box<[RowEntry]>,
absorbs: Box<[bool]>,
weight: Box<[i32]>,
row_atoms: usize,
ranked: Box<[Atom]>,
copied: Box<[Option<Sign>]>,
one_sided: bool,
absorbs_from_copies: bool,
forced: Box<[Option<Forced>]>,
positive: Box<[Sign]>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub(crate) struct Rank(u32);
impl Rank {
pub(crate) const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct RowEntry {
pub(crate) rank: Rank,
pub(crate) lo: i32,
pub(crate) hi: i32,
}
#[derive(Default)]
struct Rows {
entries: Vec<RowEntry>,
}
impl Rows {
fn at(&self, i: usize) -> RowEntry {
self.entries[i]
}
fn copy(&mut self, row: std::ops::Range<usize>) -> usize {
for i in row.clone() {
self.push(self.at(i));
}
row.len()
}
fn push(&mut self, e: RowEntry) {
self.entries.push(e);
}
fn bytes(&self) -> usize {
bytes_of(&self.entries)
}
fn merge(&mut self, a: std::ops::Range<usize>, b: std::ops::Range<usize>, sum: bool) -> usize {
let (mut i, mut j) = (a.start, b.start);
let zero = |rank| RowEntry { rank, lo: 0, hi: 0 };
while i < a.end || j < b.end {
let (x, y) = match (i < a.end, j < b.end) {
(true, true) if self.at(i).rank == self.at(j).rank => {
i += 1;
j += 1;
(self.at(i - 1), self.at(j - 1))
}
(true, other) if !other || self.at(i).rank < self.at(j).rank => {
i += 1;
(self.at(i - 1), zero(self.at(i - 1).rank))
}
_ => {
j += 1;
(zero(self.at(j - 1).rank), self.at(j - 1))
}
};
self.push(RowEntry {
rank: x.rank,
lo: if sum { x.lo + y.lo } else { x.lo.min(y.lo) },
hi: if sum { x.hi + y.hi } else { x.hi.max(y.hi) },
});
}
a.len() + b.len()
}
}
pub(crate) struct Predicates {
counted: Box<[Atom]>,
open: Box<[bool]>,
}
#[inline(always)]
fn counted_atom(forest: &Forest, predicates: Option<&Predicates>, o: OccId) -> Option<Atom> {
let atom = forest.atom(o)?;
Some(match predicates {
None => atom,
Some(p) => p.counted(atom),
})
}
#[inline(always)]
fn open_atom(forest: &Forest, predicates: Option<&Predicates>, o: OccId) -> bool {
match predicates {
None => false,
Some(p) => forest.atom(o).is_some_and(|a| p.open(a)),
}
}
impl Predicates {
pub(crate) fn of(sequent: &crate::linear::Sequent) -> Option<Self> {
let fo = &sequent.fo;
if fo.atoms.is_empty() || fo.binders.is_empty() {
return None;
}
let loose = fo.loose();
let mut first: Vec<Option<Atom>> = vec![None; fo.symbols.len()];
let mut open = vec![false; fo.symbols.len()];
for (i, &(symbol, args)) in fo.atoms.iter().enumerate() {
first[symbol.index()].get_or_insert(Atom::new(i as u32));
open[symbol.index()] |= fo.list(args).iter().any(|t| loose[t.index()] > 0);
}
if !open.contains(&true) {
return None;
}
let (counted, open): (Vec<Atom>, Vec<bool>) = fo
.atoms
.iter()
.enumerate()
.map(|(i, &(symbol, _))| {
let s = symbol.index();
if open[s] {
(first[s].expect("its own atom"), true)
} else {
(Atom::new(i as u32), false)
}
})
.unzip();
Some(Self {
counted: counted.into_boxed_slice(),
open: open.into_boxed_slice(),
})
}
pub(crate) fn counted(&self, atom: Atom) -> Atom {
self.counted[atom.index()]
}
pub(crate) fn open(&self, atom: Atom) -> bool {
self.open[atom.index()]
}
}
impl Counts {
#[cfg(any(all(test, feature = "parse"), feature = "interactive"))]
pub(crate) fn new(forest: &Forest, bias: Bias) -> Self {
Self::new_until(
forest,
bias,
Mode::CLASSICAL,
&Account::new(None),
&mut |_| false,
)
.expect("nothing stops it")
}
pub(crate) fn new_until(
forest: &Forest,
bias: Bias,
mode: Mode,
account: &Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Self, Reason> {
const PERIOD: usize = 1 << 16;
let mut visited = 0;
let mut stopped = |steps: usize| {
visited += steps;
visited >= PERIOD && {
visited = 0;
set_up_stopped(forest, stop)
}
};
let n = forest.len();
if n > i32::MAX as usize {
return Err(Reason::IndexLimit);
}
let positive = super::bias::signs(forest, bias);
let predicates = Predicates::of(forest.sequent());
let predicates = predicates.as_ref();
let atom_of = |o: OccId| counted_atom(forest, predicates, o);
let open = |o: OccId| open_atom(forest, predicates, o);
let num_atoms = forest.sequent().atom_names().len();
let fixed = n * (size_of::<u32>() + size_of::<i32>() + 2 * size_of::<bool>())
+ num_atoms
* (2 * size_of::<bool>()
+ 2 * size_of::<u32>()
+ size_of::<Sign>()
+ size_of::<Option<Sign>>());
account.charge(fixed);
if account.over() {
return Err(Reason::MemoryLimit {
limit_bytes: account.limit(),
});
}
let mut exponential = vec![[false; 2]; num_atoms];
let mut absorbs_from_copies = false;
let mut inside = 0;
for o in forest.ids() {
if o.index() < inside {
if let (Some(atom), Some(sign)) = (atom_of(o), forest.sign(o)) {
exponential[atom.index()][sign as usize] = true;
}
absorbs_from_copies |= forest.kind(o) == Kind::Top;
}
if matches!(forest.kind(o), Kind::Bang | Kind::Quest) {
inside = inside.max(o.index() + forest.size(o) as usize);
}
if stopped(1) {
return Err(Reason::Stopped);
}
}
let one_sided = intervals_run(mode, absorbs_from_copies);
#[cfg(test)]
let one_sided = one_sided && ONE_SIDED.get();
if !one_sided {
for signs in &mut exponential {
if signs.contains(&true) {
*signs = [true; 2];
}
}
}
let mut rank = vec![0u32; num_atoms];
let mut ranked = Vec::new();
let mut copied = Vec::new();
for (atom, rank) in rank.iter_mut().enumerate() {
*rank = ranked.len() as u32;
let [positive, negative] = exponential[atom];
if !(positive && negative) {
ranked.push(Atom::new(atom as u32));
copied.push(match (positive, negative) {
(true, _) => Some(Sign::Atom),
(_, true) => Some(Sign::Dual),
_ => None,
});
}
}
let row_atoms = ranked.len();
let mut unrestricted = vec![[false; 2]; num_atoms];
for o in forest.ids() {
if forest.kind(o) == Kind::Quest
&& let Some(below) = forest.left(o)
&& let (Some(atom), Some(sign)) = (atom_of(below), forest.sign(below))
{
unrestricted[atom.index()][sign as usize] = true;
}
}
let linear = |o: OccId| match (atom_of(o), forest.sign(o)) {
(Some(atom), Some(sign)) => {
sign == positive[atom.index()]
&& !unrestricted[atom.index()][!sign as usize]
&& !open(o)
}
_ => false,
};
let mut forced = vec![None; n];
let mut rows = Rows::default();
let mut bound = Vec::with_capacity(n + 1);
bound.push(0u32);
let row = |bound: &[u32], o: OccId| {
let at = n - 1 - o.index();
bound[at] as usize..bound[at + 1] as usize
};
let mut absorbs = vec![false; n];
let mut weight = vec![0i32; n];
let mut charged = 0;
for o in forest.ids().rev() {
use Kind::*;
let kind = forest.kind(o);
let mut steps = 1;
let (absorb, w) = match kind {
Atom | DualAtom => {
let sign = if kind == Atom { 1 } else { -1 };
let atom = atom_of(o).unwrap();
if !exponential[atom.index()].iter().all(|&below| below) {
rows.push(RowEntry {
rank: Rank(rank[atom.index()]),
lo: sign,
hi: sign,
});
}
(false, 0)
}
One => (false, -1),
Bot => (false, 1),
Top => (true, 0),
Zero => (false, 0),
Forall | Exists => {
let c = forest.left(o).unwrap();
steps += rows.copy(row(&bound, c));
(absorbs[c.index()], weight[c.index()])
}
Bang | Quest => {
let c = forest.left(o).unwrap();
(absorbs[c.index()], weight[c.index()])
}
Tensor | Par | With | Plus => {
let (l, r) = (forest.left(o).unwrap(), forest.right(o).unwrap());
let (li, ri) = (l.index(), r.index());
let absorb = absorbs[li] || absorbs[ri];
if !absorb {
let sum = matches!(kind, Tensor | Par);
steps += rows.merge(row(&bound, l), row(&bound, r), sum);
}
let w = weight[li]
+ weight[ri]
+ if kind == Tensor {
1
} else if kind == Par {
-1
} else {
0
};
(absorb, w)
}
};
let Ok(end) = u32::try_from(rows.entries.len()) else {
return Err(Reason::IndexLimit);
};
bound.push(end);
absorbs[o.index()] = absorb;
weight[o.index()] = w;
forced[o.index()] = match kind {
Zero => Some(Forced::Nothing),
One => Some(Forced::Empty),
Bang if predicates.is_none() => Some(Forced::Empty),
Atom | DualAtom
if forest.sign(o) == Some(positive[forest.atom(o).unwrap().index()])
&& !open(o) =>
{
Some(Forced::Dual)
}
Tensor
if forest
.children(o)
.all(|c| linear(c) || forced[c.index()] == Some(Forced::Duals)) =>
{
Some(Forced::Duals)
}
Atom | DualAtom | Bang | Bot | Top | Quest | Tensor | Par | With | Plus
| Forall | Exists => None,
};
if rows.bytes() != charged {
account.resize(charged, rows.bytes());
charged = rows.bytes();
if account.over() {
return Err(Reason::MemoryLimit {
limit_bytes: account.limit(),
});
}
}
if stopped(steps) {
return Err(Reason::Stopped);
}
}
let counts = Self {
bound: bound.into_boxed_slice(),
entries: rows.entries.into_boxed_slice(),
absorbs: absorbs.into_boxed_slice(),
weight: weight.into_boxed_slice(),
row_atoms,
ranked: ranked.into_boxed_slice(),
one_sided: copied.iter().any(Option::is_some),
copied: copied.into_boxed_slice(),
absorbs_from_copies,
forced: forced.into_boxed_slice(),
positive,
};
account.resize(charged, counts.entries.len() * size_of::<RowEntry>());
Ok(counts)
}
fn span(&self, o: OccId) -> (usize, usize) {
let at = self.absorbs.len() - 1 - o.index();
(self.bound[at] as usize, self.bound[at + 1] as usize)
}
pub(crate) fn positive(&self, forest: &Forest, o: OccId) -> bool {
match (forest.atom(o), forest.sign(o)) {
(Some(atom), Some(sign)) => sign == self.positive[atom.index()],
_ => false,
}
}
pub(super) fn forced(&self, o: OccId) -> Option<Forced> {
self.forced[o.index()]
}
pub(crate) fn row(&self, o: OccId) -> impl Iterator<Item = RowEntry> + '_ {
let (start, end) = self.span(o);
self.entries[start..end].iter().copied()
}
pub(crate) fn absorbs(&self, o: OccId) -> bool {
self.absorbs[o.index()]
}
pub(crate) fn weight(&self, o: OccId) -> i32 {
self.weight[o.index()]
}
pub(crate) fn absorbs_from_copies(&self) -> bool {
self.absorbs_from_copies
}
pub(crate) fn first_rank(&self, o: OccId) -> u32 {
let (start, end) = self.span(o);
if start == end {
u32::MAX
} else {
self.entries[start].rank.0
}
}
pub(crate) fn row_len(&self, o: OccId) -> u32 {
let (start, end) = self.span(o);
(end - start) as u32
}
pub(crate) fn tally_bytes(&self) -> usize {
self.row_atoms * size_of::<Sum>()
}
pub(crate) fn split_bytes(&self) -> usize {
size_of::<Split>() + self.row_atoms * size_of::<Column>()
}
pub(crate) fn split(&self) -> Split {
Split {
columns: vec![Column::default(); self.row_atoms],
bad: [0; 2],
absorbers: [0; 2],
open_absorbers: 0,
slack: [-2; 2],
slack_below: 0,
slack_above: 0,
inert: false,
touched: Vec::new(),
}
}
pub(crate) fn tight(&self, o: OccId) -> bool {
self.row(o)
.any(|e| self.excluded(e.rank.index(), e.lo, e.hi))
}
pub(crate) fn excluded(&self, rank: usize, lo: i32, hi: i32) -> bool {
match self.copied[rank] {
None => lo > 0 || hi < 0,
Some(Sign::Atom) => lo > 0,
Some(Sign::Dual) => hi < 0,
}
}
#[inline(always)]
fn excluded_as<const PLAIN: bool>(&self, rank: usize, lo: i32, hi: i32) -> bool {
if PLAIN {
lo > 0 || hi < 0
} else {
self.excluded(rank, lo, hi)
}
}
pub(crate) fn tally(&self) -> Tally {
Tally {
sums: vec![Sum::default(); self.row_atoms],
touched: Vec::new(),
bad: 0,
absorbers: 0,
len: 0,
weight: 0,
}
}
}
#[derive(Clone, Debug)]
pub(crate) struct Tally {
sums: Vec<Sum>,
touched: Vec<u32>,
bad: u32,
absorbers: u32,
len: u32,
weight: i32,
}
impl Tally {
pub(crate) fn clear(&mut self) {
for a in self.touched.drain(..) {
self.sums[a as usize] = Sum::default();
}
self.bad = 0;
self.absorbers = 0;
self.len = 0;
self.weight = 0;
}
pub(crate) fn add(&mut self, counts: &Counts, o: OccId) {
self.apply(counts, o, 1);
}
#[cfg(all(test, feature = "parse"))]
pub(crate) fn remove(&mut self, counts: &Counts, o: OccId) {
self.apply(counts, o, -1);
}
fn apply(&mut self, counts: &Counts, o: OccId, sign: i32) {
if counts.one_sided {
self.apply_as::<false>(counts, o, sign);
} else {
self.apply_as::<true>(counts, o, sign);
}
}
#[inline(always)]
fn apply_as<const PLAIN: bool>(&mut self, counts: &Counts, o: OccId, sign: i32) {
for e in counts.row(o) {
let a = e.rank.index();
let sum = &mut self.sums[a];
if *sum == Sum::default() {
self.touched.push(a as u32);
}
let was_bad = counts.excluded_as::<PLAIN>(a, sum.lo, sum.hi);
sum.lo += sign * e.lo;
sum.hi += sign * e.hi;
let is_bad = counts.excluded_as::<PLAIN>(a, sum.lo, sum.hi);
if is_bad && !was_bad {
self.bad += 1;
} else if was_bad && !is_bad {
self.bad -= 1;
}
}
if counts.absorbs(o) {
self.absorbers = self.absorbers.wrapping_add_signed(sign);
}
self.len = self.len.wrapping_add_signed(sign);
self.weight += sign * counts.weight(o);
}
pub(crate) fn unbalanced(&self, counts: &Counts) -> Option<(Atom, i32, i32, Option<Sign>)> {
if self.absorbs() {
return None;
}
let rank = self
.touched
.iter()
.map(|&a| a as usize)
.filter(|&a| counts.excluded(a, self.sums[a].lo, self.sums[a].hi))
.min()?;
Some((
counts.ranked[rank],
self.sums[rank].lo,
self.sums[rank].hi,
counts.copied[rank],
))
}
pub(crate) fn absorbs(&self) -> bool {
self.absorbers > 0
}
pub(crate) fn balanced(&self) -> bool {
self.absorbs() || self.bad == 0
}
pub(crate) fn equation(&self, mix: bool) -> bool {
let c = i64::from(self.len);
let rhs = i64::from(self.weight) + 2;
if mix { c >= rhs } else { c == rhs }
}
pub(crate) fn admits_mix(&self) -> bool {
i64::from(self.len) > i64::from(self.weight) + 2
}
#[cfg(all(test, feature = "parse"))]
pub(crate) fn len(&self) -> u32 {
self.len
}
}
#[derive(Clone, Debug)]
pub(crate) struct Split {
columns: Vec<Column>,
bad: [u32; 2],
absorbers: [u32; 2],
open_absorbers: u32,
slack: [i64; 2],
slack_below: i64,
slack_above: i64,
inert: bool,
touched: Vec<u32>,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct Sum {
lo: i32,
hi: i32,
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
struct Column {
lo: [i32; 2],
hi: [i32; 2],
below: i32,
above: i32,
}
impl Column {
#[inline(always)]
fn excludes<const PLAIN: bool>(&self, counts: &Counts, atom: usize) -> [bool; 2] {
[0, 1].map(|side| {
counts.excluded_as::<PLAIN>(
atom,
self.lo[side] + self.below,
self.hi[side] + self.above,
)
})
}
}
impl Split {
#[inline(always)]
fn count_bad(&mut self, was: [bool; 2], is: [bool; 2]) {
for side in 0..2 {
match (was[side], is[side]) {
(false, true) => self.bad[side] += 1,
(true, false) => self.bad[side] -= 1,
_ => {}
}
}
}
pub(crate) fn clear(&mut self) {
for a in self.touched.drain(..) {
self.columns[a as usize] = Column::default();
}
self.bad = [0; 2];
self.absorbers = [0; 2];
self.open_absorbers = 0;
self.slack = [-2; 2];
self.slack_below = 0;
self.slack_above = 0;
self.inert = false;
}
pub(crate) fn set_inert(&mut self, inert: bool) {
self.inert = inert;
}
fn shift(&mut self, counts: &Counts, o: OccId, side: Branch, settled: i32, opened: i32) {
if counts.one_sided {
self.shift_as::<false>(counts, o, side, settled, opened);
} else {
self.shift_as::<true>(counts, o, side, settled, opened);
}
}
#[inline(always)]
fn shift_as<const PLAIN: bool>(
&mut self,
counts: &Counts,
o: OccId,
side: Branch,
settled: i32,
opened: i32,
) {
let side = side as usize;
for e in counts.row(o) {
let a = e.rank.index();
let column = &mut self.columns[a];
let was = column.excludes::<PLAIN>(counts, a);
column.lo[side] += settled * e.lo;
column.hi[side] += settled * e.hi;
column.below += opened * e.lo.min(0);
column.above += opened * e.hi.max(0);
let is = column.excludes::<PLAIN>(counts, a);
self.count_bad(was, is);
}
if counts.absorbs(o) {
self.absorbers[side] = self.absorbers[side].wrapping_add_signed(settled);
self.open_absorbers = self.open_absorbers.wrapping_add_signed(opened);
}
let slack = 1 - i64::from(counts.weight(o));
self.slack[side] += i64::from(settled) * slack;
self.slack_below += i64::from(opened) * slack.min(0);
self.slack_above += i64::from(opened) * slack.max(0);
}
pub(crate) fn place(&mut self, counts: &Counts, o: OccId, side: Branch) {
self.touch(counts, o);
self.shift(counts, o, side, 1, 0);
}
pub(crate) fn open(&mut self, counts: &Counts, o: OccId) {
self.touch(counts, o);
self.shift(counts, o, Branch::Left, 0, 1);
}
fn touch(&mut self, counts: &Counts, o: OccId) {
for e in counts.row(o) {
if self.columns[e.rank.index()] == Column::default() {
self.touched.push(e.rank.0);
}
}
}
pub(crate) fn assign(&mut self, counts: &Counts, o: OccId, side: Branch) {
if !self.inert {
self.shift(counts, o, side, 1, -1);
}
}
pub(crate) fn flip(&mut self, counts: &Counts, o: OccId, side: Branch) {
if self.inert {
return;
}
if counts.one_sided {
self.flip_as::<false>(counts, o, side);
} else {
self.flip_as::<true>(counts, o, side);
}
}
#[inline(always)]
fn flip_as<const PLAIN: bool>(&mut self, counts: &Counts, o: OccId, side: Branch) {
let (to, from) = (side as usize, 1 - side as usize);
for e in counts.row(o) {
let a = e.rank.index();
let column = &mut self.columns[a];
let was = column.excludes::<PLAIN>(counts, a);
column.lo[from] -= e.lo;
column.hi[from] -= e.hi;
column.lo[to] += e.lo;
column.hi[to] += e.hi;
let is = column.excludes::<PLAIN>(counts, a);
self.count_bad(was, is);
}
if counts.absorbs(o) {
self.absorbers[from] -= 1;
self.absorbers[to] += 1;
}
let slack = 1 - i64::from(counts.weight(o));
self.slack[from] -= slack;
self.slack[to] += slack;
}
pub(crate) fn unassign(&mut self, counts: &Counts, o: OccId, side: Branch) {
if !self.inert {
self.shift(counts, o, side, -1, 1);
}
}
pub(crate) fn feasible(&self, intervals: bool, equation: bool, mix: bool) -> bool {
if self.inert {
return true;
}
if intervals {
let needy = (0..2)
.filter(|&side| self.absorbers[side] == 0 && self.bad[side] > 0)
.count();
if needy > self.open_absorbers as usize {
return false;
}
}
!equation
|| self.slack.iter().all(|slack| {
slack + self.slack_above >= 0 && (mix || slack + self.slack_below <= 0)
})
}
}
pub(crate) fn refutation(
forest: &Forest,
goal: &[OccId],
fragment: Fragment,
mode: Mode,
account: &Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> Refutation {
let Ok(counts) = Counts::new_until(forest, Bias::Rarer, mode, account, stop) else {
return Refutation::Exhausted;
};
let rules = Switches::new(fragment, mode, &counts);
let mut tally = counts.tally();
for &o in goal {
tally.add(&counts, o);
}
if rules.intervals
&& let Some((atom, least, most, copied)) = tally.unbalanced(&counts)
{
let predicate = Predicates::of(forest.sequent())
.filter(|p| p.open(atom))
.and_then(|_| forest.sequent().atom_predicate(atom))
.map(|(symbol, _)| symbol);
return match (copied, predicate) {
(None, None) => Refutation::Unbalanced(Unbalanced { atom, least, most }),
(Some(copied), None) => Refutation::OneSided(OneSided {
atom,
least,
most,
copied,
}),
(None, Some(symbol)) => Refutation::UnbalancedSymbol(UnbalancedSymbol {
symbol,
least,
most,
}),
(Some(copied), Some(symbol)) => Refutation::OneSidedSymbol(OneSidedSymbol {
symbol,
least,
most,
copied,
}),
};
}
if rules.equation && !tally.equation(rules.mix) {
let (mut tensors, mut pars, mut ones, mut bottoms) = (0, 0, 0, 0);
for &o in goal {
for x in forest.subtree(o) {
match forest.kind(x) {
Kind::Tensor => tensors += 1,
Kind::Par => pars += 1,
Kind::One => ones += 1,
Kind::Bot => bottoms += 1,
_ => {}
}
}
}
let needed = tensors as i64 - pars as i64 - ones as i64 + bottoms as i64 + 2;
return Refutation::Equation(Equation {
formulas: goal.len() as u64,
needed,
tensors,
pars,
ones,
bottoms,
mix: rules.mix,
});
}
Refutation::Exhausted
}
#[cfg(feature = "interactive")]
pub(crate) fn split_passes(
forest: &Forest,
fragment: Fragment,
mode: Mode,
left: &[OccId],
right: &[OccId],
) -> bool {
let counts = Counts::new(forest, Bias::Auto);
let rules = Switches::new(fragment, mode, &counts);
let mut split = counts.split();
for (members, side) in [(left, Branch::Left), (right, Branch::Right)] {
for &m in members {
split.place(&counts, m, side);
}
}
split.feasible(rules.intervals, rules.equation, rules.mix)
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::Sequent;
fn counts(input: &str) -> (Forest, Counts) {
let s: Sequent = input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"));
let f = Forest::new(&s).unwrap();
let c = Counts::new(&f, Bias::Auto);
(f, c)
}
fn roots(input: &str) -> (Forest, Counts, Tally) {
let (f, c) = counts(input);
let mut t = c.tally();
for &r in f.roots() {
t.add(&c, r);
}
(f, c, t)
}
#[test]
fn copies_list_their_atoms_once() {
let (f, c) = counts("|- ?(a & 1), ~a");
let copy = f.left(f.roots()[0]).unwrap();
let mut tally = c.tally();
let mut split = c.split();
for _ in 0..100 {
tally.add(&c, copy);
split.place(&c, copy, Branch::Left);
}
assert_eq!((tally.touched.len(), split.touched.len()), (1, 1));
}
#[test]
fn rows_of_one_sign_only_where_the_check_runs() {
let ranked = |input: &str, mode: Mode| {
let s: Sequent = input.parse().unwrap();
let f = Forest::new(&s).unwrap();
let c = Counts::new_until(&f, Bias::Auto, mode, &Account::new(None), &mut |_| false)
.unwrap();
c.ranked.len()
};
assert_eq!(ranked("|- ?a, a", Mode::CLASSICAL), 1);
assert_eq!(ranked("|- ?a, a", Mode::INTUITIONISTIC), 1);
assert_eq!(ranked("|- ?a, a", Mode::CLASSICAL.with_affine()), 0);
assert_eq!(ranked("|- ?(a & top), a", Mode::CLASSICAL), 0);
assert_eq!(ranked("|- ?a, ?~a, a", Mode::CLASSICAL), 0);
}
#[test]
fn rows() {
let (f, c) = counts("|- (a * ~a) par b, (a & ~b) + ~a, 1");
let rank = |name| Rank(f.sequent().atom(name).unwrap().index() as u32);
let (a, b) = (rank("a"), rank("b"));
let row = |o: u32| c.row(OccId::new(o)).collect::<Vec<_>>();
let e = |rank, lo, hi| RowEntry { rank, lo, hi };
assert_eq!(row(0), [e(a, 0, 0), e(b, 1, 1)], "the ⅋");
assert_eq!(row(1), [e(a, 0, 0)], "the ⊗");
assert_eq!(row(2), [e(a, 1, 1)]);
assert_eq!(row(3), [e(a, -1, -1)]);
assert_eq!(row(5), [e(a, -1, 1), e(b, -1, 0)], "the ⊕");
assert_eq!(row(6), [e(a, 0, 1), e(b, -1, 0)], "the &");
assert_eq!(row(10), [], "the 1");
assert!(c.tight(OccId::new(2)), "a literal's interval excludes zero");
assert!(!c.tight(OccId::new(5)), "the ⊕ can be balanced by itself");
assert!(!c.absorbs(OccId::new(0)));
assert_eq!(c.weight(OccId::new(0)), 0, "one ⊗, one ⅋");
assert_eq!(c.weight(OccId::new(10)), -1);
}
#[test]
fn intervals() {
for (input, balanced) in [
("|- a, ~a", true),
("|- a, a", false),
("|- a, ~a, b", false),
("|- a + b, ~a", true),
("|- a & b, ~a", true),
("|- (a * b) + (a * c), ~a, ~b", true),
("|- (a * b) + (a * c), ~a, ~c, ~c", false),
("|- 1, bot, 0", true),
("|- a", false),
("|-", true),
] {
let (_, _, t) = roots(input);
assert_eq!(t.balanced(), balanced, "{input:?}");
}
}
#[test]
fn top_absorbs() {
for input in [
"|- top, a",
"|- top * a, b",
"|- (a & top) + c, ~b",
"|- top par a, b",
"|- a & top, ~b",
"|- top & a, ~b",
] {
let (f, c, t) = roots(input);
assert!(c.absorbs(f.roots()[0]), "{input:?}");
assert!(t.balanced(), "{input:?}");
}
}
#[test]
fn equation() {
for (input, holds, holds_with_mix) in [
("|- 1", true, true),
("|- bot, 1", true, true),
("|- 1 * 1", true, true),
("|- bot par 1", true, true),
("|- bot par bot", false, false),
("|- a, ~a", true, true),
("|- a * b, ~a, ~b", true, true),
("|- a par b, ~a, ~b", false, true),
("|- a, ~a, b, ~b", false, true),
("|- 1, a, ~a", false, true),
("|-", false, false),
] {
let (_, _, t) = roots(input);
assert_eq!(t.equation(false), holds, "{input:?}");
assert_eq!(t.equation(true), holds_with_mix, "{input:?}");
}
}
#[test]
fn tally_moves() {
let (f, c, mut t) = roots("|- a * b, ~a, ~b");
assert!(t.balanced());
assert_eq!(t.len(), 3);
t.remove(&c, f.roots()[1]);
assert!(!t.balanced(), "~a alone is unbalanced");
assert_eq!(t.len(), 2);
t.remove(&c, f.roots()[0]);
t.remove(&c, f.roots()[2]);
assert!(t.balanced(), "the empty set is balanced");
assert!(!t.equation(false));
t.add(&c, f.roots()[1]);
t.add(&c, f.roots()[2]);
assert!(!t.balanced());
t.clear();
assert!(t.balanced());
assert_eq!(t.len(), 0);
}
}