use super::memory::{Account, Charged, bytes_of};
use super::net::{self, Correctness, Linker, Prunes};
use super::planar::Planar;
use super::{Answer, Decide, Engine, NotTaken, Options, Reason, Statistics, Stop, Task, Work};
use crate::Error;
use crate::limits::Limits;
use crate::linear::fragment::{Fragment, Mode, Order};
use crate::linear::nets::essential::{fixed_successors, is_implication};
use crate::linear::nets::{Criterion, ProofStructure, VertexId};
use crate::linear::occurrences::{Forest, OccId, Reading, ShapeError, Side, Sign};
use crate::linear::sequents::{Atom, Kind};
const NONE: u32 = u32::MAX;
const LINEAR_BYTES: usize = 24;
const NONEMPTY_BYTES: usize = 16;
const SETUP_ROWS: usize = 1024;
pub(crate) struct Essentials;
impl Decide for Essentials {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let refused = |because| Error::EngineRefused {
engine: Engine::Essential,
because,
};
let mode = task.mode;
if !mode.is_intuitionistic() || mode.is_affine() {
return Err(refused(NotTaken::Mode { mode }));
}
if !task.fragment.has_nets() {
return Err(refused(NotTaken::Fragment {
decides: Fragment::MLL,
goal: task.fragment,
}));
}
if !task.roots && !(mode.is_ordered() && net::apart(task.forest, task.goal)) {
return Err(refused(NotTaken::Goal));
}
crate::linear::nets::fits(task.forest.len())
}
fn decide(
&self,
task: &Task<'_>,
options: &Options,
limits: &Limits,
account: &Account,
_work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
let mode = task.mode;
if !task.roots {
return net::goal(task, limits, |own| {
match Reading::of_mode(own, mode) {
Ok(reading) => Ok(search(own, &reading, mode, options, limits, account, stop)),
Err(ShapeError::EmptyAntecedent) => Ok(net::answer(
Ok(false),
Statistics::default(),
None,
limits,
stop,
)),
Err(shape) => Err(Error::NotIntuitionistic(shape)),
}
});
}
let reading = task
.reading
.expect("intuitionistic mode reads the sequent first");
Ok(search(
task.forest,
reading,
mode,
options,
limits,
account,
stop,
))
}
}
pub(crate) fn search(
forest: &Forest,
reading: &Reading<'_>,
mode: Mode,
options: &Options,
limits: &Limits,
account: &Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> Answer {
if !net::counts_admit(forest, false) {
return net::answer(Ok(false), Statistics::default(), None, limits, stop);
}
let (result, statistics, structure) = match Essential::new(forest, reading, mode, account, stop)
{
Err(reason) => (Err(reason), Statistics::default(), None),
Ok(criterion) if mode.is_ordered() => {
let criterion = Planar::new(criterion);
let mut engine = Linker::with(criterion, options, Stop::Closure(stop), Prunes::PLANAR);
let result = engine.run();
let structure =
matches!(result, Ok(true)).then(|| engine.criterion.inner().structure());
(result, engine.statistics, structure)
}
Ok(criterion) => {
let mut engine = Linker::with(criterion, options, Stop::Closure(stop), Prunes::ALL);
let result = engine.run();
let structure = matches!(result, Ok(true)).then(|| engine.criterion.structure());
(result, engine.statistics, structure)
}
};
debug_assert!(
structure
.as_ref()
.is_none_or(|net| net.is_essential(|_| false).is_ok()),
"the search's test is the essential criterion"
);
net::answer(result, statistics, structure, limits, stop)
}
#[derive(Clone, Copy, Debug)]
struct Change {
row: u32,
word: u32,
old: u64,
}
pub(super) struct Essential<'a> {
forest: &'a Forest,
partner: Box<[u32]>,
links: Vec<(VertexId, VertexId)>,
words: usize,
reach: Box<[u64]>,
log: Vec<Change>,
marks: Vec<usize>,
branching: Box<[u64]>,
implications: Box<[(u32, u32)]>,
binder: Box<[u32]>,
goal: u32,
nonempty: Option<Nonempty>,
order: Order,
charged: Charged<'a>,
}
struct Nonempty {
bodies: Box<[(u32, u32)]>,
sources: Box<[(u32, u32)]>,
}
impl<'a> Essential<'a> {
fn new(
forest: &'a Forest,
reading: &Reading<'_>,
mode: Mode,
account: &'a Account,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Self, Reason> {
let n = forest.len();
let words = n.div_ceil(64);
let cells = n as u64 * words as u64;
let limit = Reason::MemoryLimit {
limit_bytes: account.limit(),
};
let linear = if mode.allows_empty_antecedents() {
LINEAR_BYTES
} else {
LINEAR_BYTES + NONEMPTY_BYTES
};
let held = usize::try_from(cells)
.ok()
.and_then(|cells| cells.checked_mul(size_of::<u64>()))
.and_then(|matrix| matrix.checked_add(n.checked_mul(linear)?))
.and_then(|bytes| bytes.checked_add(words * size_of::<u64>()))
.filter(|&bytes| bytes <= isize::MAX as usize && account.fits(bytes))
.ok_or(limit)?;
let mut charged = Charged::new(account);
charged.charge(held);
let mut reach = Vec::new();
reach.try_reserve_exact(cells as usize).map_err(|_| limit)?;
reach.resize(cells as usize, 0u64);
let mut reach = reach.into_boxed_slice();
let mut rows = 0usize;
let mut poll = |stop: &mut dyn FnMut(u64) -> bool| {
rows += 1;
rows.is_multiple_of(SETUP_ROWS) && stop(0)
};
let position = |o: OccId| reading.position(o);
let set = |row: &mut [u64], v: usize| row[v / 64] |= 1 << (v % 64);
for o in forest.ids().rev().filter(|&o| position(o) == Side::Input) {
if poll(stop) {
return Err(Reason::Stopped);
}
let (u, row) = (o.index(), o.index() * words);
set(&mut reach[row..row + words], u);
for s in fixed_successors(forest, reading, o) {
let from = s.index() * words;
for w in 0..words {
reach[row + w] |= reach[from + w];
}
}
}
for o in forest.ids().filter(|&o| position(o) == Side::Output) {
if poll(stop) {
return Err(Reason::Stopped);
}
let (u, row) = (o.index(), o.index() * words);
set(&mut reach[row..row + words], u);
for s in fixed_successors(forest, reading, o) {
let from = s.index() * words;
for w in 0..words {
reach[row + w] |= reach[from + w];
}
}
}
let goal = reading.goal();
let mut branching = vec![0u64; words].into_boxed_slice();
let mut implications = Vec::new();
let mut binder = vec![NONE; n].into_boxed_slice();
for o in forest.ids() {
if position(o) == Side::Input {
if forest.kind(o) == Kind::Par {
set(&mut branching, o.index());
}
binder[o.index()] = match forest.parent(o) {
Some(p) if position(p) == Side::Output && p != goal => p.get(),
Some(p) if position(p) == Side::Input => binder[p.index()],
_ => NONE,
};
} else if is_implication(forest, reading, o) && o != goal {
let (antecedent, _) = reading.implication(o).expect("an implication");
implications.push((o.get(), antecedent.get()));
}
}
let nonempty = (!mode.allows_empty_antecedents()).then(|| {
let bodies = forest
.ids()
.filter(|&o| o != goal)
.filter_map(|o| {
reading
.implication(o)
.filter(|_| is_implication(forest, reading, o))
})
.map(|(antecedent, consequent)| (consequent.get(), antecedent.get()))
.collect();
let hypotheses = reading.hypotheses().map(|h| (h.get(), NONE));
let antecedents = forest
.ids()
.filter(|&o| is_implication(forest, reading, o))
.map(|o| {
(
reading.implication(o).expect("an implication").0.get(),
o.get(),
)
});
Nonempty {
bodies,
sources: hypotheses.chain(antecedents).collect(),
}
});
Ok(Self {
forest,
partner: vec![NONE; n].into_boxed_slice(),
links: Vec::with_capacity(forest.all_literals().len() / 2),
words,
reach,
log: Vec::new(),
marks: Vec::with_capacity(forest.all_literals().len() / 2),
branching,
implications: implications.into_boxed_slice(),
binder,
goal: goal.get(),
nonempty,
order: mode.order(),
charged,
})
}
fn keeps_antecedents(&self, nonempty: &Nonempty) -> bool {
nonempty.bodies.iter().all(|&(body, bound)| {
nonempty.sources.iter().any(|&(source, binder)| {
source != bound
&& self.reaches(source, body)
&& (binder == NONE || !self.reaches(binder, body))
})
})
}
fn reaches(&self, u: u32, v: u32) -> bool {
let (u, v) = (u as usize, v as usize);
self.reach[u * self.words + v / 64] >> (v % 64) & 1 == 1
}
fn row(&self, u: u32) -> &[u64] {
let start = u as usize * self.words;
&self.reach[start..start + self.words]
}
fn escapes(&self, q: u32, l: u32) -> bool {
self.reaches(q, self.goal) || self.row(q).iter().zip(self.row(l)).any(|(a, b)| a & b != 0)
}
fn dominated(&self, l: u32, s: u32) -> bool {
if !self.reaches(s, l) {
return !self.escapes(s, l);
}
for (w, (&reached, &branching)) in self.row(s).iter().zip(&self.branching).enumerate() {
let mut bits = reached & branching;
while bits != 0 {
let p = (w * 64) as u32 + bits.trailing_zeros();
bits &= bits - 1;
if !self.reaches(p, l) {
continue;
}
let p = OccId::new(p);
for q in [self.forest.left(p), self.forest.right(p)] {
let q = q.expect("a `⅋` has two premises").get();
if !self.reaches(q, l) && self.escapes(q, l) {
return false;
}
}
}
}
true
}
fn oriented(&self, x: OccId, y: OccId) -> (u32, u32) {
match self.forest.sign(x) {
Some(Sign::Dual) => (x.get(), y.get()),
_ => (y.get(), x.get()),
}
}
fn reserve(&mut self) -> Result<(), Reason> {
if self.log.len() < self.log.capacity() {
return Ok(());
}
let before = bytes_of(&self.log);
let more = self.log.capacity().max(1024);
if !self
.charged
.account()
.fits(more.saturating_mul(size_of::<Change>()))
{
return Err(Reason::MemoryLimit {
limit_bytes: self.charged.account().limit(),
});
}
self.log
.try_reserve_exact(more)
.map_err(|_| Reason::MemoryLimit {
limit_bytes: self.charged.account().limit(),
})?;
self.charged.resize(before, bytes_of(&self.log));
Ok(())
}
pub(super) fn structure(&self) -> ProofStructure {
let criterion = Criterion {
order: self.order,
..Criterion::MLL
};
let mut net = ProofStructure::new(self.forest.clone(), criterion)
.expect("the engine admits unit-free IMLL only");
for &(x, y) in &self.links {
net.link_unchecked(x, y);
}
net
}
}
impl Correctness for Essential<'_> {
fn forest(&self) -> &Forest {
self.forest
}
fn mate(&self, x: OccId) -> Option<OccId> {
let p = self.partner[x.index()];
(p != NONE).then(|| OccId::new(p))
}
fn links(&self) -> &[(VertexId, VertexId)] {
&self.links
}
fn is_complete(&self) -> bool {
2 * self.links.len() == self.forest.all_literals().len()
}
fn admits(&self, x: OccId, y: OccId) -> bool {
let (i, o) = self.oriented(x, y);
if self.reaches(o, i) {
return false;
}
let l = self.binder[i as usize];
l == NONE || self.reaches(o, l) || !self.reaches(o, self.goal)
}
fn link(&mut self, x: OccId, y: OccId) -> Result<(), Reason> {
let (i, o) = self.oriented(x, y);
debug_assert!(!self.reaches(o, i), "a link closes no cycle");
let mark = self.log.len();
let words = self.words;
let (column, bit) = (i as usize / 64, i % 64);
let from = o as usize * words;
for u in 0..self.forest.len() {
let row = u * words;
if self.reach[row + column] >> bit & 1 == 0 {
continue;
}
for w in 0..words {
let (old, new) = (
self.reach[row + w],
self.reach[row + w] | self.reach[from + w],
);
if old != new {
if let Err(reason) = self.reserve() {
while self.log.len() > mark {
let change = self.log.pop().unwrap();
self.reach[change.row as usize * words + change.word as usize] =
change.old;
}
return Err(reason);
}
self.log.push(Change {
row: u as u32,
word: w as u32,
old,
});
self.reach[row + w] = new;
}
}
}
self.marks.push(mark);
self.partner[x.index()] = y.get();
self.partner[y.index()] = x.get();
self.links.push((VertexId::of(x), VertexId::of(y)));
Ok(())
}
fn unlink(&mut self) -> OccId {
let (x, y) = self.links.pop().expect("a link to take back");
let mark = self.marks.pop().expect("a mark per link");
while self.log.len() > mark {
let change = self.log.pop().unwrap();
self.reach[change.row as usize * self.words + change.word as usize] = change.old;
}
self.partner[x.index()] = NONE;
self.partner[y.index()] = NONE;
x.occ()
}
fn test(&mut self) -> bool {
self.implications.iter().all(|&(l, s)| self.dominated(l, s))
&& (self.nonempty.is_none() || !self.is_complete() || {
let nonempty = self.nonempty.as_ref().expect("asked");
self.keeps_antecedents(nonempty)
})
}
fn balanced(&self, _atom: Atom, _remaining: u32, _tally: &mut [u32]) -> bool {
true
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::Essential;
use crate::limits::Limits;
use crate::linear::fragment::Mode;
use crate::linear::nets::{Criterion, ProofStructure};
use crate::linear::occurrences::{Forest, Reading};
use crate::linear::search::generate::{self, IllRules, Rng};
use crate::linear::search::memory::Account;
use crate::linear::search::net::Correctness;
use crate::linear::search::{
Engine, Error, NotTaken, Options, Outcome, Reason, Verdict, prove,
};
use crate::linear::search::{Statistics, prove_within};
use crate::linear::sequents::Sequent;
const IMLL: IllRules = IllRules {
units: false,
additives: false,
zero: false,
exponentials: false,
};
fn sequent(input: &str) -> Sequent {
input.parse().unwrap_or_else(|e| panic!("{input:?}: {e}"))
}
fn essential() -> Options {
Options::default().with_engine(Some(Engine::Essential))
}
fn verdict(text: &str, outcome: Outcome) -> bool {
let i = Mode::INTUITIONISTIC;
match outcome.verdict {
Verdict::Proved(proof) => {
assert!(outcome.checked);
assert_eq!(proof.check(i), Ok(()), "{text:?} by {}", outcome.engine);
if outcome.engine == Engine::Essential {
let net = outcome.net.expect("the net found");
let read = ProofStructure::from_proof(
&proof,
Criterion::MLL,
&Limits::default(),
|_| false,
)
.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(&read), sorted(&net), "{text:?}");
assert_eq!(net.is_essential(|_| false), Ok(()), "{text:?}");
}
true
}
Verdict::Unprovable(_) => false,
Verdict::Unknown(reason) => panic!("{text:?} by {}: {reason}", outcome.engine),
}
}
fn most_copies(s: &Sequent) -> usize {
let forest = Forest::new(s).unwrap();
forest
.all_literals()
.chunk_by(|x, y| {
forest.atom(*x) == forest.atom(*y) && forest.sign(*x) == forest.sign(*y)
})
.map(<[_]>::len)
.max()
.unwrap_or(0)
}
#[test]
fn agrees_with_the_two_sided_engine() {
let i = Mode::INTUITIONISTIC;
let mut rng = Rng::new(35);
let (mut compared, mut provable, mut embedded) = (0, 0, 0);
for _ in 0..300 {
let budget = 2 + rng.below(10);
let generate::Ill {
mut hypotheses,
mut goal,
..
} = generate::ill(&mut rng, IMLL, 3, budget);
for mutated in [false, true] {
if mutated && !generate::mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
continue;
}
let text = generate::two_sided(&hypotheses, &goal);
let s = sequent(&text);
let copies = most_copies(&s);
if copies > 3 {
continue;
}
let by_essential = prove(&s, i, &essential()).unwrap();
assert_eq!(by_essential.engine, Engine::Essential);
let two_sided = Options::default().with_engine(Some(Engine::TwoSided));
let by_two_sided = prove(&s, i, &two_sided).unwrap();
let (e, t) = (verdict(&text, by_essential), verdict(&text, by_two_sided));
assert_eq!(e, t, "{text:?}: essential {e}, two-sided {t}");
if copies <= 2 {
let net = Options::default().with_engine(Some(Engine::Net));
let n = verdict(&text, prove(&s, i, &net).unwrap());
assert_eq!(e, n, "{text:?}: essential {e}, net {n}");
embedded += 1;
}
assert!(mutated || e, "{text:?} is provable");
compared += 1;
provable += usize::from(e);
}
}
assert!(
compared > 300 && provable > 150 && provable < compared - 100 && embedded > 200,
"{provable} of {compared}, {embedded} on the embedding"
);
}
#[test]
fn unlinking_restores_the_closure() {
let s = sequent("a -o b, b -o c, c -o d, d -o e |- a -o e");
let forest = Forest::new(&s).unwrap();
let reading = Reading::new(&forest).unwrap();
let account = Account::new(None);
let mut criterion = Essential::new(
&forest,
&reading,
Mode::INTUITIONISTIC,
&account,
&mut |_| false,
)
.unwrap();
let mut snapshots = vec![criterion.reach.clone()];
let mut linked = 0;
loop {
let next = forest.all_literals().iter().find_map(|&x| {
let free = |o| criterion.mate(o).is_none();
(free(x) && forest.sign(x) == Some(crate::linear::occurrences::Sign::Dual))
.then(|| {
forest
.literals(
forest.atom(x).unwrap(),
crate::linear::occurrences::Sign::Atom,
)
.iter()
.copied()
.find(|&y| free(y) && criterion.admits(x, y))
.map(|y| (x, y))
})
.flatten()
});
let Some((x, y)) = next else { break };
criterion.link(x, y).unwrap();
linked += 1;
snapshots.push(criterion.reach.clone());
}
assert!(criterion.is_complete() && linked == 5, "{linked} links");
assert!(criterion.test(), "the composition is a net");
assert!(criterion.log.len() > 10, "{} changes", criterion.log.len());
while !criterion.links().is_empty() {
snapshots.pop();
criterion.unlink();
assert_eq!(&criterion.reach, snapshots.last().unwrap());
}
assert!(criterion.log.is_empty() && criterion.marks.is_empty());
}
#[test]
fn the_closure_is_charged() {
let s = sequent(&format!(
"a0{} |- a40",
(0..40)
.map(|k| format!(", a{k} -o a{}", k + 1))
.collect::<String>()
));
let i = Mode::INTUITIONISTIC;
let within = |bytes| {
let limits = Limits {
memory_bytes: Some(bytes),
..Limits::default()
};
prove_within(&s, i, &essential(), &limits, |_| false).unwrap()
};
let outcome = within(2_000);
assert!(
matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { limit_bytes: 2_000 })
),
"{:?}",
outcome.verdict
);
assert_eq!(outcome.statistics, Statistics::default());
assert!(matches!(within(1 << 20).verdict, Verdict::Proved(_)));
}
#[test]
fn lambek_has_no_handover() {
let text = format!(
"a0{} |- a40",
(0..40)
.map(|k| format!(", a{k} \\ a{}", k + 1))
.collect::<String>()
);
let s = Sequent::parse_ordered(&text, crate::linear::Order::Cyclic, &Limits::default())
.unwrap();
let limits = Limits {
memory_bytes: Some(2_000),
..Limits::default()
};
let outcome =
prove_within(&s, Mode::LAMBEK, &Options::default(), &limits, |_| false).unwrap();
assert_eq!(outcome.engine, Engine::Essential);
assert!(matches!(
outcome.verdict,
Verdict::Unknown(Reason::MemoryLimit { .. })
));
let net = Options::default().with_engine(Some(Engine::Net));
assert!(matches!(
prove(&s, Mode::LAMBEK, &net),
Err(Error::EngineRefused {
engine: Engine::Net,
..
})
));
}
#[test]
fn the_review_s_witnesses() {
let i = Mode::INTUITIONISTIC;
let decided = |text: &str| verdict(text, prove(&sequent(text), i, &essential()).unwrap());
assert!(!decided("a -o (a * a) |- (a -o a) * a"));
assert!(decided("|- b -o (a -o (b * a))"));
}
#[test]
fn refusals() {
let refused = |text: &str, mode: Mode| match prove(&sequent(text), mode, &essential()) {
Err(Error::EngineRefused {
engine: Engine::Essential,
because,
}) => because,
other => panic!("{text:?}: {other:?}"),
};
assert!(matches!(
refused("|- a, ~a", Mode::CLASSICAL),
NotTaken::Mode { .. }
));
let affine = Mode::INTUITIONISTIC.with_affine();
assert!(matches!(refused("a |- a", affine), NotTaken::Mode { .. }));
let units = refused("a * 1 |- a", Mode::INTUITIONISTIC);
assert_eq!(
units.explained(Engine::Essential).to_string(),
"essential nets exist for IMLL without units only, not for MLL with units"
);
}
}