mod arena;
pub(crate) mod bias;
mod choices;
mod classes;
mod context;
pub(crate) mod counts;
mod first_order;
mod framed;
mod keyed;
mod memo;
#[cfg(feature = "parallel")]
pub(crate) mod parallel;
mod resumed;
mod schedule;
mod scratch;
mod split;
#[cfg(all(test, feature = "parse"))]
mod tests;
mod waiting;
mod zone;
use self::arena::Arena;
use self::classes::Classes;
use self::counts::{Counts, Split, Tally, intervals_run};
use self::framed::Framed;
use self::memo::{Entry, Failure, Inserted, Key, Table, Zones};
use self::schedule::{Plan, plan, turns};
use self::scratch::{Pooled, Pools};
use self::split::Join;
use self::waiting::Waiting;
use self::zone::{Ground, Linear as _, Unrestricted as _, Zone};
use super::memory::{Account, Charged};
use super::{
Answer, Decide, Finished, Options, Reason, Statistics, Stop, Task, Work, set_up_stopped,
};
use crate::Error;
use crate::limits::Limits;
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::occurrences::{Forest, OccId, Reading};
use crate::linear::proofs::{Branch, Node, NodeId};
use crate::linear::sequents::Kind;
const NO_DEPENDENCY: u32 = u32::MAX;
const SPLITS_PER_POLL: u64 = 4096;
const FORCED_PER_POLL: u64 = 4096;
const NODE_WORK: u64 = 16;
const OCCURRENCES_PER_WORK: usize = 128;
const MEETS_PER_WORK: usize = 16;
const OCCURRENCES_PER_LEAF: usize = 512;
pub(crate) struct Focused {
two_sided: bool,
}
pub(crate) const ONE_SIDED: Focused = Focused { two_sided: false };
pub(crate) const TWO_SIDED: Focused = Focused { two_sided: true };
impl Decide for Focused {
fn admits(&self, task: &Task<'_>) -> Result<(), Error> {
let decides = Fragment::LL1;
let because = if !decides.contains(task.fragment) {
super::NotTaken::Fragment {
decides,
goal: task.fragment,
}
} else if task.mode.intuitionistic != self.two_sided {
super::NotTaken::Mode { mode: task.mode }
} else {
return Ok(());
};
let engine = if self.two_sided {
super::Engine::TwoSided
} else {
super::Engine::Focus
};
Err(Error::EngineRefused { engine, because })
}
fn decide(
&self,
task: &Task<'_>,
options: &Options,
limits: &Limits,
account: &Account,
work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Result<Answer, Error> {
let first_order = task.fragment.has_quantifiers();
#[cfg(feature = "parallel")]
if options.threads() > 1 {
let found = if first_order {
parallel::search_goal::<Framed>(task, options, limits, account, work, stop)?
} else {
parallel::search_goal::<Ground>(task, options, limits, account, work, stop)?
};
return Ok(Answer::of_arena(task.forest, found, stop));
}
let found = if first_order {
search_goal::<Framed>(task, options, limits, account, work, stop)
} else {
search_goal::<Ground>(task, options, limits, account, work, stop)
};
Ok(Answer::of_arena(task.forest, found, stop))
}
}
fn search_goal<Z: Zone>(
task: &Task<'_>,
options: &Options,
limits: &Limits,
account: &Account,
work: &Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Finished {
let forest = task.forest;
let gave_up = |r: Reason| Finished::gave_up(r.as_set(options, limits));
let Some((classes, first, second)) = prepare(task, options, stop) else {
return gave_up(Reason::Stopped);
};
let set_up = SetUp {
task,
classes: &classes,
options,
limits,
};
let Some(second) = second else {
account.charge(classes.bytes());
let counts = match Counts::new_until(forest, first.bias, task.mode, account, stop) {
Ok(counts) => counts,
Err(reason) => return gave_up(reason),
};
let (finished, _) = first.search::<Z>(set_up, &counts, account, Stop::Closure(stop));
return Finished {
result: finished.result.map_err(|r| r.as_set(options, limits)),
..finished
};
};
let accounts = [account.share(2), account.share(2)];
for account in &accounts {
account.charge(classes.bytes());
}
let first_counts = match Counts::new_until(forest, first.bias, task.mode, &accounts[0], stop) {
Ok(counts) => counts,
Err(reason) => return gave_up(reason),
};
let second_counts = match Counts::new_until(forest, second.bias, task.mode, &accounts[1], stop)
{
Ok(counts) => counts,
Err(reason) => return gave_up(reason),
};
let searches = [
(first, &first_counts, &accounts[0]),
(second, &second_counts, &accounts[1]),
];
#[cfg(not(feature = "parallel"))]
let _ = work;
#[cfg(feature = "parallel")]
if options.schedule == super::Schedule::Auto
&& let Some(result) = schedule::alternate::<Z>(set_up, searches, work, stop)
{
return result;
}
turns::<Z>(set_up, searches, stop)
}
#[derive(Clone, Copy)]
struct SetUp<'a> {
task: &'a Task<'a>,
classes: &'a Classes,
options: &'a Options,
limits: &'a Limits,
}
fn prepare(
task: &Task<'_>,
options: &Options,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<(Classes, Plan, Option<Plan>)> {
let classes = Classes::new(task.forest, task.reading);
if set_up_stopped(task.forest, stop) {
return None;
}
let (first, second) = plan(task.forest, task.goal, task.fragment, task.mode, options);
if set_up_stopped(task.forest, stop) {
return None;
}
Some((classes, first, second))
}
#[derive(Clone, Copy, Debug)]
struct Switches {
mix: bool,
equation: bool,
intervals: bool,
exponentials: bool,
affine: bool,
stack: bool,
}
impl Switches {
fn new(fragment: Fragment, mode: Mode, counts: &Counts) -> Self {
let exponentials = fragment.has_exponentials();
Self {
mix: mode.mix && !mode.affine,
equation: !mode.affine
&& !fragment.has_additives()
&& !fragment.has_additive_units()
&& !exponentials,
intervals: intervals_run(mode, counts.absorbs_from_copies()),
exponentials,
affine: mode.affine,
stack: exponentials,
}
}
}
pub(crate) type Searched = Result<Option<NodeId>, Reason>;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Cuts {
exhausted: bool,
dependency: u32,
}
impl Cuts {
const NONE: Self = Self {
exhausted: false,
dependency: NO_DEPENDENCY,
};
const BUDGET: Self = Self {
exhausted: true,
dependency: NO_DEPENDENCY,
};
fn repeat(depth: u32) -> Self {
Self {
exhausted: false,
dependency: depth,
}
}
fn and(self, other: Self) -> Self {
Self {
exhausted: self.exhausted || other.exhausted,
dependency: self.dependency.min(other.dependency),
}
}
}
#[derive(Clone, Copy, Debug)]
enum Found {
Proved(NodeId),
Failed(Cuts),
}
impl Found {
const NOTHING: Self = Self::Failed(Cuts::NONE);
fn proved(node: NodeId) -> Self {
Self::Proved(node)
}
fn failed(cuts: Cuts) -> Self {
Self::Failed(cuts)
}
fn node(self) -> Option<NodeId> {
match self {
Self::Proved(node) => Some(node),
Self::Failed(_) => None,
}
}
fn after(self, cuts: Cuts) -> Self {
match self {
Self::Proved(node) => Self::Proved(node),
Self::Failed(own) => Self::Failed(cuts.and(own)),
}
}
fn map(self, wrap: impl FnOnce(NodeId) -> NodeId) -> Self {
match self {
Self::Proved(node) => Self::Proved(wrap(node)),
failed => failed,
}
}
}
type Step = Result<Found, Reason>;
enum Alternative<'m, Z: Zone> {
Focus(Z::Member),
Copy(Z::Member),
Branch(Z::Member, Branch, Z::Member),
#[cfg_attr(
not(feature = "parallel"),
expect(dead_code, reason = "only a pool hands out the splits of a tensor")
)]
Splits {
join: Join<Z::Member>,
members: &'m [Z::Member],
fixed: usize,
pattern: u64,
sides: (&'m Z::Linear, &'m Z::Linear),
split: &'m Split,
},
}
impl<Z: Zone> Clone for Alternative<'_, Z> {
fn clone(&self) -> Self {
*self
}
}
impl<Z: Zone> Copy for Alternative<'_, Z> {}
#[derive(Clone, Copy)]
struct Problem<'a> {
forest: &'a Forest,
reading: Option<&'a Reading<'a>>,
counts: &'a Counts,
classes: &'a Classes,
rules: Switches,
account: &'a Account,
memoizes: bool,
waits: usize,
recursion_limit: u32,
copies: u32,
}
impl<'a> Problem<'a> {
fn new(set_up: SetUp<'a>, counts: &'a Counts, copies: u32, account: &'a Account) -> Self {
let task = set_up.task;
Self {
forest: task.forest,
reading: task.reading,
counts,
classes: set_up.classes,
rules: Switches::new(task.fragment, task.mode, counts),
account,
memoizes: set_up.options.memo_limit != 0,
waits: set_up.options.memo_entries(),
recursion_limit: set_up.limits.recursion_depth,
copies,
}
}
}
struct Unrestricted<Z: Zone> {
set: Z::Unrestricted,
id: u64,
}
struct ByClass<Z: Zone> {
zone: Option<u64>,
members: Pooled<(Z::Member, Z::Member)>,
}
struct Run<'a, Z: Zone> {
problem: Problem<'a>,
zone: Z,
memo: Table<'a>,
nodes: Arena<'a>,
scratch: Charged<'a>,
statistics: Statistics,
steps: u64,
forced: u64,
work: u64,
depth: u32,
stop: Stop<'a>,
#[cfg(feature = "parallel")]
runtime: Option<&'a super::parallel::Runtime>,
#[cfg(feature = "parallel")]
divided: bool,
#[cfg_attr(
not(feature = "parallel"),
expect(dead_code, reason = "only a pool runs alternatives on several threads")
)]
or_depth: u32,
stack: Vec<Key>,
hashes: Vec<u64>,
stack_len: usize,
marks: Vec<usize>,
waiting: Waiting,
ancestors: Vec<(&'a [Key], &'a [u64])>,
pools: Pools<Z>,
by_class: ByClass<Z>,
}
impl<'a, Z: Zone> Run<'a, Z> {
fn new(
problem: Problem<'a>,
stop: Stop<'a>,
memo: Table<'a>,
nodes: Arena<'a>,
zone: Z,
) -> Self {
Self {
problem,
zone,
memo,
scratch: Charged::new(problem.account),
nodes,
statistics: Statistics::default(),
steps: 0,
forced: 0,
work: 0,
depth: 0,
stop,
#[cfg(feature = "parallel")]
runtime: None,
#[cfg(feature = "parallel")]
divided: false,
or_depth: 0,
stack: Vec::new(),
hashes: Vec::new(),
stack_len: 0,
marks: Vec::new(),
waiting: Waiting::default(),
ancestors: Vec::new(),
pools: Pools::default(),
by_class: ByClass {
zone: None,
members: Pooled::default(),
},
}
}
fn run_kept(&mut self, goal: &[OccId]) -> Result<Option<NodeId>, Reason> {
let Some(root) = self.run(goal)? else {
return Ok(None);
};
let stop = &mut self.stop;
self.nodes.keep_all(root, &mut || stop.fired(0)).map(Some)
}
#[inline]
fn occ(&self, m: Z::Member) -> OccId {
self.zone.occurrence(m)
}
#[inline]
fn kind(&self, m: Z::Member) -> Kind {
self.problem.forest.kind(self.occ(m))
}
#[inline]
fn left(&self, m: Z::Member) -> Z::Member {
let left = self.problem.forest.left(self.occ(m)).unwrap();
self.zone.child(m, left)
}
#[inline]
fn right(&self, m: Z::Member) -> Z::Member {
let right = self.problem.forest.right(self.occ(m)).unwrap();
self.zone.child(m, right)
}
#[inline]
fn class(&self, m: Z::Member) -> Z::Member {
self.zone.class(self.problem.classes, m)
}
fn statistics(&self) -> Statistics {
let mut statistics = Statistics {
memo_hits: self.memo.hits(),
memo_entries: self.memo.peak() as u64,
..self.statistics
};
if Z::FIRST_ORDER {
let (unifications, bindings) = self.zone.counts();
statistics.unifications += unifications;
statistics.bindings += bindings;
}
statistics
}
#[cfg(feature = "parallel")]
fn report(&self) -> Statistics {
let mut statistics = self.statistics;
if Z::FIRST_ORDER {
let (unifications, bindings) = self.zone.counts();
statistics.unifications += unifications;
statistics.bindings += bindings;
}
statistics
}
fn run(&mut self, goal: &[OccId]) -> Searched {
let levels = if self.problem.rules.exponentials {
self.problem.copies
} else {
0
};
let set = self.take_set();
let theta = Unrestricted {
id: self.memo.intern(set.ground(), self.problem.account),
set,
};
let mut generation = 0;
self.memo.begin(generation);
for budget in 0..=levels {
self.statistics.copies = budget;
self.waiting.clear();
if Z::FIRST_ORDER {
if let Err(reason) = self.poll_with() {
self.give_set(theta.set);
return Err(reason);
}
self.zone.begin_level();
#[cfg(feature = "parallel")]
{
self.divided = false;
}
}
let (added, emptied) = (self.memo.added(), self.memo.emptied());
let mut gamma = self.take_context();
let mut list = self.take_list();
list.extend(goal.iter().rev().map(|&o| self.zone.root(o)));
let result = self.asynchronous(&theta, &mut gamma, &mut list, budget);
#[cfg(feature = "parallel")]
let result = if Z::FIRST_ORDER && budget == levels {
self.again_alone(&theta, goal, budget, result, &mut generation)
} else {
result
};
self.give_context(gamma);
self.give_list(list);
match result {
Ok(Found::Failed(cuts)) if cuts.exhausted => {
if self.memo.added() == added || self.memo.emptied() != emptied {
generation += 1;
self.memo.begin(generation);
}
}
decided => {
self.give_set(theta.set);
return decided.map(Found::node);
}
}
}
self.give_set(theta.set);
if Z::FIRST_ORDER
&& let Some(reason) = self.zone.cut()
{
return Err(reason);
}
Err(Reason::CopyBound { copies: levels })
}
#[cfg(feature = "parallel")]
fn again_alone(
&mut self,
theta: &Unrestricted<Z>,
goal: &[OccId],
budget: u32,
result: Step,
generation: &mut u64,
) -> Step {
let cut = matches!(result, Ok(Found::Failed(cuts)) if cuts.exhausted);
if !(cut && std::mem::take(&mut self.divided)) {
return result;
}
*generation += 1;
self.memo.begin(*generation);
let mut gamma = self.take_context();
let mut list = self.take_list();
list.extend(goal.iter().rev().map(|&o| self.zone.root(o)));
let runtime = self.runtime.take();
let again = self.asynchronous(theta, &mut gamma, &mut list, budget);
self.runtime = runtime;
self.give_context(gamma);
self.give_list(list);
again
}
fn asynchronous(
&mut self,
theta: &Unrestricted<Z>,
gamma: &mut Z::Linear,
list: &mut Vec<Z::Member>,
budget: u32,
) -> Step {
self.enter()?;
let result = self.decompose(theta, gamma, list, budget);
self.leave();
result
}
fn decompose(
&mut self,
theta: &Unrestricted<Z>,
gamma: &mut Z::Linear,
list: &mut Vec<Z::Member>,
budget: u32,
) -> Step {
let mut applied = self.take_list();
let mut grown: Option<Z::Unrestricted> = None;
let mut interned: Option<Unrestricted<Z>> = None;
let mark = Z::FIRST_ORDER.then(|| self.zone.mark());
let result = loop {
let Some(o) = list.pop() else {
interned = self.interned(grown.take());
break self.prove(interned.as_ref().unwrap_or(theta), gamma, budget);
};
match self.kind(o) {
Kind::Par => {
list.push(self.right(o));
list.push(self.left(o));
applied.push(o);
}
Kind::Bot => applied.push(o),
Kind::Top => break Ok(Found::proved(self.push(Node::Top(o.into())))),
Kind::With => {
interned = self.interned(grown.take());
break self.with(interned.as_ref().unwrap_or(theta), gamma, list, o, budget);
}
Kind::Quest => {
let a = self.left(o);
if !grown.as_ref().unwrap_or(&theta.set).contains(a) {
if grown.is_none() {
let mut larger = self.take_set();
larger.copy_from(&theta.set);
grown = Some(larger);
}
grown.as_mut().unwrap().insert(a);
}
applied.push(o);
}
kind if Z::FIRST_ORDER && kind == Kind::Forall => {
match self.zone.forall(self.problem.forest, o) {
Ok(Some(body)) => {
list.push(body);
applied.push(o);
}
Ok(None) => break Ok(Found::failed(Cuts::BUDGET)),
Err(reason) => break Err(reason),
}
}
_ => {
gamma.insert(o);
}
}
};
if let Some(larger) = grown.or(interned.map(|zone| zone.set)) {
self.give_set(larger);
}
if let (Some(mark), Ok(Found::Failed(_))) = (mark, &result) {
self.zone.undo(mark);
}
let result = result.map(|found| {
found.map(|mut node| {
for &o in applied.iter().rev() {
node = match self.kind(o) {
Kind::Par => self.push(Node::Par(o.into(), node)),
Kind::Quest => self.push(Node::Quest(o.into(), node)),
kind if Z::FIRST_ORDER && kind == Kind::Forall => {
let eigen = self.zone.introduced();
self.push(Node::Forall(o.into(), eigen, node))
}
_ => self.push(Node::Bot(o.into(), node)),
};
}
node
})
});
self.give_list(applied);
result
}
fn interned(&mut self, grown: Option<Z::Unrestricted>) -> Option<Unrestricted<Z>> {
grown.map(|set| Unrestricted {
id: self.memo.intern(set.ground(), self.problem.account),
set,
})
}
fn with(
&mut self,
theta: &Unrestricted<Z>,
gamma: &mut Z::Linear,
list: &mut Vec<Z::Member>,
o: Z::Member,
budget: u32,
) -> Step {
self.poll_with()?;
if self.problem.account.over() {
self.relieve()?;
}
if Z::FIRST_ORDER {
return self.with_framed(theta, gamma, list, o, budget);
}
#[cfg(feature = "parallel")]
if self.cubes() {
return self.with_parallel(theta, gamma, list, o, budget);
}
let mark = self.nodes.mark();
let left = self.premise(theta, gamma, list, self.left(o), budget)?;
let Found::Proved(left_node) = left else {
return Ok(left);
};
list.push(self.right(o));
let (left_node, right) = self.holding(left_node, |run| {
run.asynchronous(theta, gamma, list, budget)
});
Ok(self.both(o, left_node, right?, mark))
}
fn poll_with(&mut self) -> Result<(), Reason> {
self.work += 1 + (self.problem.forest.len() / OCCURRENCES_PER_WORK) as u64;
self.forced += 1;
if self.forced < FORCED_PER_POLL {
return Ok(());
}
self.forced = 0;
if self.stop.fired(std::mem::take(&mut self.work)) {
Err(Reason::Stopped)
} else {
Ok(())
}
}
fn premise(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
list: &[Z::Member],
sub: Z::Member,
budget: u32,
) -> Step {
let mut premise_gamma = self.take_context_from(gamma);
let mut premise_list = self.take_list();
premise_list.extend_from_slice(list);
premise_list.push(sub);
let result = self.asynchronous(theta, &mut premise_gamma, &mut premise_list, budget);
self.give_context(premise_gamma);
self.give_list(premise_list);
result
}
#[inline(always)]
fn holding<T>(&mut self, first: NodeId, second: impl FnOnce(&mut Self) -> T) -> (NodeId, T) {
let held = self.nodes.hold(first);
let found = second(self);
(self.nodes.unhold(held), found)
}
#[inline(always)]
fn two_premises(
&mut self,
first: impl FnOnce(&mut Self) -> Step,
second: impl FnOnce(&mut Self) -> Step,
join: impl FnOnce(NodeId, NodeId) -> Node,
) -> Step {
let mark = self.nodes.mark();
let l = first(self)?;
let Found::Proved(l_node) = l else {
return Ok(l);
};
let (l_node, r) = self.holding(l_node, second);
let r = r?;
let Found::Proved(r_node) = r else {
self.nodes.release(mark);
return Ok(r);
};
Ok(Found::proved(self.push(join(l_node, r_node))))
}
fn both(&mut self, o: Z::Member, left: NodeId, right: Found, mark: usize) -> Found {
let Found::Proved(right) = right else {
self.nodes.release(mark);
return right;
};
Found::proved(self.push(Node::With(o.into(), left, right)))
}
fn prove(&mut self, theta: &Unrestricted<Z>, gamma: &Z::Linear, budget: u32) -> Step {
Ok(self.prove_part(theta, gamma, budget)?.0)
}
fn prove_part(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
budget: u32,
) -> Result<(Found, bool), Reason> {
self.enter()?;
let result = self.prove_stable(theta, gamma, budget);
self.leave();
result
}
fn prove_stable(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
budget: u32,
) -> Result<(Found, bool), Reason> {
self.statistics.nodes += 1;
let work = NODE_WORK
+ (self.problem.forest.len() / OCCURRENCES_PER_WORK) as u64
+ std::mem::take(&mut self.work);
if self.stop.fired(work) {
return Err(Reason::Stopped);
}
if self.problem.account.over() {
self.relieve()?;
}
if !self.zone.memoizes(&theta.set, gamma) {
return self.prove_unkeyed(theta, gamma, budget);
}
let mut words = self.take_words();
let ground = gamma.ground();
let repeats = ground.repeats();
if repeats {
ground.key_into(&mut words);
} else {
ground.list_into(&mut words);
}
let mut canonical = self.take_words();
let result = self.prove_listed(theta, gamma, (&words, repeats), &mut canonical, budget);
self.give_words(words);
self.give_words(canonical);
result
}
#[cold]
fn prove_unkeyed(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
budget: u32,
) -> Result<(Found, bool), Reason> {
if Z::FIRST_ORDER
&& self.problem.memoizes
&& let Some(decided) = self.prove_keyed(theta, gamma, budget)
{
return decided;
}
let mut members = self.take_list();
gamma.list_into(&mut members);
let mark = self.nodes.mark();
let zone = Z::FIRST_ORDER.then(|| self.zone.mark());
let result = self.decide(theta, gamma, &members, budget);
self.give_list(members);
if let Ok((Found::Failed(_), _)) = result {
self.nodes.release(mark);
if let Some(zone) = zone {
self.zone.undo(zone);
}
}
result
}
fn prove_listed(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
(words, repeats): (&[OccId], bool),
canonical: &mut Vec<OccId>,
budget: u32,
) -> Result<(Found, bool), Reason> {
let key = Zones {
theta: theta.id,
members: words,
};
let hash = if self.problem.memoizes || self.problem.rules.stack {
key.hash()
} else {
0
};
let renamed = self.problem.classes.renames(gamma.ground());
if renamed {
self.problem.classes.canonical(words, repeats, canonical);
debug_assert!(
*canonical != words,
"a member's class is another occurrence"
);
}
let canonical_key = Zones {
theta: theta.id,
members: canonical,
};
let canonical_hash = if renamed && self.problem.memoizes {
canonical_key.hash()
} else {
0
};
let refuted = if renamed {
self.memo.refuted(canonical_key, canonical_hash)
} else {
None
};
let entry = match refuted {
Some(failure) => Some(Entry::Failed(failure)),
None => self.memo.get(key, hash, budget),
};
match entry {
Some(Entry::Proved(node)) => return Ok((Found::proved(node), false)),
Some(Entry::Failed(failure @ (Failure::Complete | Failure::Hereditary))) => {
return Ok((Found::NOTHING, failure == Failure::Hereditary));
}
Some(Entry::Failed(Failure::Exhausted(_))) | None => {}
}
if self.problem.rules.stack
&& let Some(depth) = self.repeated(key, hash)
{
return Ok((Found::failed(Cuts::repeat(depth as u32)), false));
}
if !self.waiting.is_empty()
&& let Some(reused) = self.waiting.find(key, hash, budget, entry.is_some())
{
if entry.is_none() {
self.memo.count_hit(hash);
}
let cuts = Cuts {
exhausted: reused.exhausted,
dependency: reused.leader,
};
return Ok((Found::failed(cuts), reused.hereditary));
}
if entry.is_some() {
return Ok((Found::failed(Cuts::BUDGET), false));
}
if self.problem.rules.stack {
if self.stack_len == self.stack.len() {
self.scratch
.charge(size_of::<Key>() + size_of::<u64>() + size_of::<usize>());
self.stack.push(Key::default());
self.hashes.push(0);
self.marks.push(0);
}
let pushed = &mut self.stack[self.stack_len];
pushed.assign(key);
pushed.members.settle(&mut self.scratch);
self.hashes[self.stack_len] = hash;
self.marks[self.stack_len] = self.waiting.len();
self.stack_len += 1;
}
let mark = self.nodes.mark();
let listed = if repeats { None } else { Z::listed(words) };
let result = if let Some(members) = listed {
self.decide(theta, gamma, members, budget)
} else {
let mut members = self.take_list();
gamma.list_into(&mut members);
let result = self.decide(theta, gamma, &members, budget);
self.give_list(members);
result
};
let own_depth = if self.problem.rules.stack {
self.stack_len -= 1;
(self.above() + self.stack_len) as u32
} else {
NO_DEPENDENCY
};
let (found, hereditary) = result?;
let (node, cuts) = match found {
Found::Proved(node) => (Some(node), Cuts::NONE),
Found::Failed(cuts) => (
None,
Cuts {
exhausted: cuts.exhausted,
dependency: if cuts.dependency >= own_depth {
NO_DEPENDENCY
} else {
cuts.dependency
},
},
),
};
if self.problem.rules.stack && self.problem.memoizes {
let waited = self.marks[self.stack_len];
debug_assert!(
waited <= self.waiting.len(),
"the failures decided below a stable sequent are gone unsettled"
);
let closed = self.close(
key,
hash,
budget,
waited,
own_depth,
(node, cuts, hereditary),
);
self.scratch.charge(self.waiting.grown());
closed?;
}
let recorded = match node {
Some(proof) if self.problem.memoizes => {
self.nodes.keep(mark, proof).and_then(|proof| {
match self.remember(key, hash, Entry::Proved(proof))? {
Entry::Proved(proof) => Ok(Some(proof)),
Entry::Failed(_) => unreachable!("the entry of a proof"),
}
})
}
None => {
self.nodes.release(mark);
let mut recorded = Ok(None);
if cuts.dependency == NO_DEPENDENCY {
let complete = if hereditary {
Failure::Hereditary
} else {
Failure::Complete
};
recorded = if cuts.exhausted {
self.remember(key, hash, Entry::Failed(Failure::Exhausted(budget)))
} else if renamed {
self.remember(canonical_key, canonical_hash, Entry::Failed(complete))
} else {
self.remember(key, hash, Entry::Failed(complete))
}
.map(|_| None);
}
recorded
}
Some(proof) => Ok(Some(proof)),
};
Ok(match recorded? {
Some(node) => (Found::proved(node), false),
None => (Found::failed(cuts), hereditary),
})
}
fn close(
&mut self,
key: Zones<'_>,
hash: u64,
budget: u32,
waited: usize,
own_depth: u32,
(node, cuts, hereditary): (Option<NodeId>, Cuts, bool),
) -> Result<(), Reason> {
if node.is_some() {
self.waiting.drop_from(waited);
return Ok(());
}
if cuts.exhausted {
self.waiting.exhaust_from(waited);
}
if cuts.dependency == NO_DEPENDENCY {
let mut recorded = Ok(());
while let Some(entry) = self.waiting.take_settled(waited, own_depth) {
if recorded.is_ok() {
recorded = self.record_failure(
entry.key.zones(),
entry.hash,
entry.budget,
(entry.exhausted, entry.hereditary),
);
}
self.waiting.give(entry.key);
}
self.waiting.settled();
return recorded;
}
if (cuts.dependency as usize) < self.above() {
self.waiting.drop_from(waited);
return Ok(());
}
self.waiting.lead_from(waited, cuts.dependency);
if self.waiting.len() < self.problem.waits {
let mut entry = self.waiting.spare().unwrap_or_default();
entry.assign(key);
entry.members.settle(&mut self.scratch);
self.waiting.wait(
entry,
hash,
budget,
(cuts.exhausted, hereditary),
cuts.dependency,
);
}
Ok(())
}
fn record_failure(
&mut self,
key: Zones<'_>,
hash: u64,
budget: u32,
(exhausted, hereditary): (bool, bool),
) -> Result<(), Reason> {
if exhausted {
return self
.remember(key, hash, Entry::Failed(Failure::Exhausted(budget)))
.map(|_| ());
}
let complete = if hereditary {
Failure::Hereditary
} else {
Failure::Complete
};
if !self.problem.classes.renames_any(key.members) {
return self
.remember(key, hash, Entry::Failed(complete))
.map(|_| ());
}
let mut canonical = self.take_words();
let repeats = key.members.iter().any(|o| o.get() & memo::REPEATED != 0);
self.problem
.classes
.canonical(key.members, repeats, &mut canonical);
let canonical_key = Zones {
theta: key.theta,
members: &canonical,
};
let recorded = self.remember(canonical_key, canonical_key.hash(), Entry::Failed(complete));
self.give_words(canonical);
recorded.map(|_| ())
}
fn repeated(&self, key: Zones<'_>, hash: u64) -> Option<usize> {
let own = (
&self.stack[..self.stack_len],
&self.hashes[..self.stack_len],
);
self.ancestors
.iter()
.chain([&own])
.flat_map(|&(keys, hashes)| keys.iter().zip(hashes))
.position(|(entry, &h)| h == hash && key.of(entry))
}
fn above(&self) -> usize {
self.ancestors.iter().map(|(keys, _)| keys.len()).sum()
}
fn remember(&mut self, key: Zones<'_>, hash: u64, entry: Entry) -> Result<Entry, Reason> {
if self.memo.insert(key, hash, entry, self.problem.account) == Inserted::Done {
return Ok(entry);
}
self.memo.clear();
let entry = match entry {
Entry::Proved(node) => Entry::Proved(
self.nodes
.collect(Some(node), false)
.expect("the root given"),
),
failed => {
self.nodes.collect(None, false);
failed
}
};
if self.memo.insert(key, hash, entry, self.problem.account) == Inserted::Done {
return Ok(entry);
}
let entry = match entry {
Entry::Proved(node) => Entry::Proved(
self.nodes
.collect(Some(node), true)
.expect("the root given"),
),
failed => {
self.nodes.collect(None, true);
failed
}
};
match self.memo.insert(key, hash, entry, self.problem.account) {
Inserted::Done => Ok(entry),
_ => Err(Reason::MemoryLimit {
limit_bytes: self.problem.account.limit(),
}),
}
}
fn relieve(&mut self) -> Result<(), Reason> {
let charged = self.waiting.release();
self.scratch.resize(charged, 0);
self.marks[..self.stack_len].fill(0);
self.memo.clear();
self.nodes.collect(None, false);
if !self.problem.account.over() {
return Ok(());
}
self.memo.release(self.problem.account);
if self.problem.account.over() {
Err(Reason::MemoryLimit {
limit_bytes: self.problem.account.limit(),
})
} else {
Ok(())
}
}
fn set_bytes(&self) -> usize {
self.problem.forest.len().div_ceil(64) * size_of::<u64>()
}
fn decide(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
members: &[Z::Member],
budget: u32,
) -> Result<(Found, bool), Reason> {
let mut tally = self.take_tally();
let mut candidates = self.take_list();
let mut copies = self.take_list();
let result = self
.decide_with(
theta,
gamma,
members,
&mut tally,
&mut candidates,
&mut copies,
budget,
)
.map(|(found, hereditary)| {
let alone = self.problem.rules.mix
&& members.len() == 1
&& matches!(found, Found::Failed(_));
(found, hereditary || alone)
});
self.give_tally(tally);
self.give_list(candidates);
self.give_list(copies);
result
}
#[allow(clippy::too_many_arguments)]
fn decide_with(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
members: &[Z::Member],
tally: &mut Tally,
candidates: &mut Vec<Z::Member>,
copies: &mut Vec<Z::Member>,
budget: u32,
) -> Result<(Found, bool), Reason> {
let affine = self.problem.rules.affine;
self.work += members.len() as u64;
let mut zero = false;
for &o in members {
tally.add(self.problem.counts, self.occ(o));
match self.kind(o) {
Kind::Zero => zero = true,
Kind::Tensor | Kind::Plus => candidates.push(o),
Kind::One | Kind::Bang if members.len() == 1 || affine => candidates.push(o),
Kind::One | Kind::Bang | Kind::Atom | Kind::DualAtom => {}
kind if Z::FIRST_ORDER && kind == Kind::Exists => candidates.push(o),
kind => unreachable!("{kind:?} in a stable sequent"),
}
}
if zero
&& !affine
&& !tally.absorbs()
&& !theta
.set
.iter()
.any(|a| self.problem.counts.absorbs(self.occ(a)))
{
return Ok((Found::NOTHING, false));
}
let mut cuts = match self.initial(theta, gamma, members, budget)? {
Found::Failed(cuts) => cuts,
proved => return Ok((proved, false)),
};
if self.problem.rules.intervals && !tally.balanced() {
return Ok((Found::failed(cuts), false));
}
if self.problem.rules.equation && !tally.equation(self.problem.rules.mix) {
return Ok((Found::failed(cuts), false));
}
self.one_of_each(candidates);
candidates.sort_by_key(|&o| (self.focus_class(o), o));
if self.problem.rules.exponentials {
let unconsumed = self.one_of_each_copy(theta, gamma, copies);
self.work += 2 * unconsumed as u64;
if budget == 0 {
if !copies.is_empty() {
cuts = cuts.and(Cuts::BUDGET);
}
copies.clear();
} else {
copies.sort_unstable();
self.work += (copies.len() * members.len() / MEETS_PER_WORK) as u64;
self.zone
.mark_literals(self.problem.forest, members, &mut self.scratch);
let mut others = self.take_list();
let mut met = 0;
for i in 0..copies.len() {
let a = copies[i];
if self.zone.meets(self.problem.forest, a) {
copies[met] = a;
met += 1;
} else {
others.push(a);
}
}
copies.truncate(met);
copies.extend_from_slice(&others);
self.give_list(others);
}
}
let alternatives = candidates
.iter()
.map(|&f| Alternative::Focus(f))
.chain(copies.iter().map(|&a| Alternative::Copy(a)));
let cuts = match self.choose(theta, gamma, alternatives, budget)?.after(cuts) {
Found::Failed(cuts) => cuts,
proved => return Ok((proved, false)),
};
let (found, hereditary) = self.last_resort(theta, gamma, members, tally, budget)?;
Ok((found.after(cuts), hereditary))
}
fn choose<'m>(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
alternatives: impl Iterator<Item = Alternative<'m, Z>>,
budget: u32,
) -> Step {
#[cfg(feature = "parallel")]
if self.cubes() {
let alternatives: Vec<Alternative<'m, Z>> = alternatives.collect();
if alternatives.len() >= 2 {
return self.choose_parallel(theta, gamma, &alternatives, budget);
}
return self.choose_here(theta, gamma, alternatives.into_iter(), budget);
}
self.choose_here(theta, gamma, alternatives, budget)
}
fn choose_here<'m>(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
alternatives: impl Iterator<Item = Alternative<'m, Z>>,
budget: u32,
) -> Step {
if Z::FIRST_ORDER {
return self.choose_framed(theta, gamma, alternatives, budget);
}
let mut cuts = Cuts::NONE;
let mut rest = None;
for alternative in alternatives {
match self.alternative(theta, gamma, alternative, &mut rest, budget)? {
Found::Failed(failed) => cuts = cuts.and(failed),
proved => {
if let Some(rest) = rest {
self.give_context(rest);
}
return Ok(proved);
}
}
}
if let Some(rest) = rest {
self.give_context(rest);
}
Ok(Found::failed(cuts))
}
fn alternative(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
alternative: Alternative<'_, Z>,
rest: &mut Option<Z::Linear>,
budget: u32,
) -> Step {
match alternative {
Alternative::Focus(f) => {
if rest.is_none() {
*rest = Some(self.take_context_any());
}
let rest = rest.as_mut().expect("taken");
rest.copy_from(gamma);
rest.remove(f);
self.focus(theta, rest, f, budget)
}
Alternative::Copy(a) => Ok(self
.focus(theta, gamma, a, budget - 1)?
.map(|node| self.push(Node::Copy(a.into(), node)))),
Alternative::Branch(f, side, sub) => Ok(self
.focus(theta, gamma, sub, budget)?
.map(|node| self.push(Node::Plus(f.into(), side, node)))),
Alternative::Splits {
join,
members,
fixed,
pattern,
sides,
split,
} => {
let mut left = self.take_context_from(sides.0);
let mut right = self.take_context_from(sides.1);
let mut counts = self.take_split();
(*counts).clone_from(split);
for (i, &m) in members.iter().enumerate().take(fixed) {
if pattern >> i & 1 == 1 {
right.remove(m);
left.insert(m);
counts.assign(self.problem.counts, self.occ(m), Branch::Left);
} else {
counts.assign(self.problem.counts, self.occ(m), Branch::Right);
}
}
let result = self.search_splits(
theta,
members,
(fixed, pattern),
(&mut left, &mut right),
&mut counts,
join,
budget,
);
self.give_context(left);
self.give_context(right);
self.give_split(counts);
result
}
}
}
fn one_of_each_copy(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
copies: &mut Vec<Z::Member>,
) -> usize {
let by_class = &mut self.by_class;
if by_class.zone != Some(theta.id) {
by_class.zone = Some(theta.id);
by_class.members.clear();
by_class.members.extend(
theta
.set
.iter()
.map(|a| (self.zone.class(self.problem.classes, a), a)),
);
by_class.members.sort_unstable();
by_class.members.settle(&mut self.scratch);
}
let mut unconsumed = 0;
let mut last = None;
for &(class, a) in self.by_class.members.iter() {
if gamma.contains(a) {
continue;
}
unconsumed += 1;
if last != Some(class) {
copies.push(a);
last = Some(class);
}
}
unconsumed
}
fn one_of_each(&self, occurrences: &mut Vec<Z::Member>) {
occurrences.sort_unstable_by_key(|&o| (self.class(o), o));
occurrences.dedup_by_key(|o| self.class(*o));
}
fn last_resort(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
members: &[Z::Member],
tally: &Tally,
budget: u32,
) -> Result<(Found, bool), Reason> {
if self.problem.rules.mix {
return self.mix(theta, gamma, members, tally, budget);
}
Ok((Found::NOTHING, false))
}
fn initial(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
members: &[Z::Member],
budget: u32,
) -> Step {
if Z::FIRST_ORDER {
return self.initial_framed(theta, gamma, members, budget);
}
let affine = self.problem.rules.affine;
if !affine && members.len() > 2 {
return Ok(Found::NOTHING);
}
let f = self.problem.forest;
self.zone.mark_literals(f, members, &mut self.scratch);
let mut cuts = Cuts::NONE;
for &p in members {
let Some(dual) = self.zone.duals(f, p) else {
continue;
};
if (affine || members.len() == 2)
&& let Some(q) = self.zone.marked(dual)
{
let ax = self.push(Node::Ax(p.into(), q.into()));
if !affine {
return Ok(Found::proved(ax));
}
let mut rest = self.take_context_from(gamma);
rest.remove(p);
rest.remove(q);
let node = self.weakened(&rest, ax);
self.give_context(rest);
return Ok(Found::proved(node));
}
if !(affine || members.len() == 1)
|| !self.problem.rules.exponentials
|| !self.zone.first_lookup(dual)
{
continue;
}
if let Some(d) = self.zone.dual_in(f, p, &theta.set) {
if budget == 0 {
cuts = Cuts::BUDGET;
continue;
}
let ax = self.push(Node::Ax(p.into(), d.into()));
let copy = self.push(Node::Copy(d.into(), ax));
if !affine {
return Ok(Found::proved(copy));
}
let mut rest = self.take_context_from(gamma);
rest.remove(p);
let node = self.weakened(&rest, copy);
self.give_context(rest);
return Ok(Found::proved(node));
}
}
Ok(Found::failed(cuts))
}
fn focus_class(&self, o: Z::Member) -> u8 {
match self.kind(o) {
Kind::One | Kind::Bang => 0,
Kind::Tensor => {
let forced = self
.problem
.forest
.children(self.occ(o))
.any(|c| self.forced_side(c).is_some());
if forced { 1 } else { 3 }
}
_ => 2,
}
}
fn focus(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
f: Z::Member,
budget: u32,
) -> Step {
self.enter()?;
let result = self.focus_on(theta, gamma, f, budget);
self.leave();
result
}
fn focus_on(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
f: Z::Member,
budget: u32,
) -> Step {
match self.kind(f) {
Kind::Plus => {
let sides = [
Alternative::Branch(f, Branch::Left, self.left(f)),
Alternative::Branch(f, Branch::Right, self.right(f)),
];
self.choose(theta, gamma, sides.into_iter(), budget)
}
Kind::Tensor => self.split(theta, gamma, f, budget),
Kind::One if self.leftover(gamma) => {
let one = self.push(Node::One(f.into()));
Ok(Found::proved(self.weakened(gamma, one)))
}
Kind::One => Ok(Found::NOTHING),
Kind::Bang => {
if !self.leftover(gamma) {
return Ok(Found::NOTHING);
}
let mut released = self.take_context();
let mut list = self.take_list();
list.push(self.left(f));
let result = self.asynchronous(theta, &mut released, &mut list, budget);
self.give_context(released);
self.give_list(list);
Ok(result?.map(|node| {
let bang = self.push(Node::Bang(f.into(), node));
self.weakened(gamma, bang)
}))
}
Kind::Zero => Ok(Found::NOTHING),
Kind::Atom | Kind::DualAtom
if self
.problem
.counts
.positive(self.problem.forest, self.occ(f)) =>
{
let mut members = self.take_list();
members.push(f);
gamma.list_into(&mut members);
let mut whole = self.take_context_from(gamma);
whole.insert(f);
let result = self.initial(theta, &whole, &members, budget);
self.give_list(members);
self.give_context(whole);
result
}
kind if Z::FIRST_ORDER && kind == Kind::Exists => self.exists(theta, gamma, f, budget),
_ => {
let mut released = self.take_context_from(gamma);
let mut list = self.take_list();
list.push(f);
let result = self.asynchronous(theta, &mut released, &mut list, budget);
self.give_context(released);
self.give_list(list);
result
}
}
}
fn leftover(&self, gamma: &Z::Linear) -> bool {
gamma.is_empty() || self.problem.rules.affine
}
fn weakened(&mut self, gamma: &Z::Linear, mut node: NodeId) -> NodeId {
debug_assert!(
gamma.is_empty() || self.problem.rules.affine,
"weakening needs affine mode"
);
debug_assert!(
self.problem
.reading
.is_none_or(|r| r.outputs(gamma.iter().map(|m| self.occ(m))) == 0),
"a leaf is the goal, so only hypotheses are left over"
);
for o in gamma.iter() {
node = self.push(Node::Weaken(o.into(), node));
}
node
}
fn push(&mut self, node: Node) -> NodeId {
self.nodes.push(node)
}
fn enter(&mut self) -> Result<(), Reason> {
if self.depth >= self.problem.recursion_limit {
return Err(Reason::RecursionLimit {
depth: self.problem.recursion_limit,
});
}
self.depth += 1;
Ok(())
}
fn leave(&mut self) {
self.depth -= 1;
}
}