use super::arena::{Arena, Kept};
use super::counts::Counts;
use super::memo::{Interner, Memo, Table};
use super::zone::Zone;
use super::{Problem, Run, SetUp};
#[cfg(feature = "parallel")]
use crate::limits::Limits;
use crate::linear::Instances;
use crate::linear::fragment::{Fragment, Mode};
use crate::linear::occurrences::{Forest, OccId};
use crate::linear::proofs::{Node, NodeId};
use crate::linear::search::Bias;
use crate::linear::search::memory::Account;
use crate::linear::search::{Finished, Options, Reason, Statistics, Stop};
use crate::linear::sequents::Kind;
#[cfg(feature = "parallel")]
use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
#[cfg(feature = "parallel")]
use std::sync::{Condvar, Mutex};
pub(super) fn turns<Z: Zone>(
set_up: SetUp<'_>,
searches: [(Plan, &Counts, &Account); 2],
stop: &mut dyn FnMut(u64) -> bool,
) -> Finished {
let (options, limits) = (set_up.options, set_up.limits);
let mut ended: [Option<Reason>; 2] = [None, None];
let mut statistics = Statistics::default();
let mut levels = [0, 0];
let leveled = |mut statistics: Statistics, levels: [u32; 2], decider: usize| {
statistics.copies = levels[decider];
statistics.forward_copies = levels[0];
statistics
};
let mut turn = FIRST_TURN;
loop {
for (i, (plan, counts, account)) in searches.into_iter().enumerate() {
if ended[i].is_some() {
continue;
}
let stop = if ended[1 - i].is_some() {
Stop::Closure(&mut *stop)
} else if i == 0 {
Stop::Turn(&mut *stop, turn)
} else {
Stop::Turn(&mut *stop, turn.saturating_mul(BACKWARD_SHARE))
};
let (
Finished {
result,
nodes,
statistics: run,
instances,
},
over,
) = plan.search::<Z>(
set_up,
counts,
&account.fork(),
stop,
);
statistics.add(&run);
levels[i] = levels[i].max(run.copies);
match result {
Err(Reason::Stopped) if over => {}
Err(Reason::Stopped) => {
return Finished {
result: Err(Reason::Stopped),
nodes,
statistics: leveled(statistics, levels, 1),
instances: None,
};
}
Err(reason) => ended[i] = Some(reason),
decided => {
return Finished {
result: decided,
nodes,
statistics: leveled(statistics, levels, i),
instances,
};
}
}
}
if let [Some(_), Some(backward)] = ended {
return Finished {
result: Err(backward.as_set(options, limits)),
nodes: Vec::new(),
statistics: leveled(statistics, levels, 1),
instances: None,
};
}
turn = turn.saturating_mul(TURN_GROWTH);
}
}
const FIRST_TURN: u64 = 1 << 16;
const BACKWARD_SHARE: u64 = 2;
const TURN_GROWTH: u64 = 4;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Plan {
pub(super) bias: Bias,
pub(super) copies: u32,
}
impl Plan {
pub(super) fn search<'a, Z: Zone>(
self,
set_up: SetUp<'a>,
counts: &'a Counts,
account: &'a Account,
stop: Stop<'a>,
) -> (Finished, bool) {
let problem = Problem::new(set_up, counts, self.copies, account);
let memo = if Z::FIRST_ORDER {
Table::Own(Memo::new(set_up.options.memo_entries()), Interner::new(0))
} else {
Table::own(set_up.options.memo_entries())
};
let mut engine = Run::new(
problem,
stop,
memo,
Arena::new(Kept::Own(Vec::new()), account),
Z::new(set_up.task.forest, set_up.options),
);
let mut result = engine.run_kept(set_up.task.goal);
let statistics = engine.statistics();
let over = matches!(engine.stop, Stop::Turn(_, 0));
let mut nodes = match engine.nodes.kept {
Kept::Own(nodes) => nodes,
Kept::Shared(_) => unreachable!("a sequential search owns its arena"),
};
let instances = closed(&engine.zone, set_up.task.forest, &mut result, &mut nodes);
(
Finished {
result,
nodes,
statistics,
instances,
},
over,
)
}
}
pub(super) fn closed<Z: Zone>(
zone: &Z,
forest: &Forest,
result: &mut Result<Option<NodeId>, Reason>,
nodes: &mut [Node],
) -> Option<Box<Instances>> {
if !Z::FIRST_ORDER || !matches!(result, Ok(Some(_))) {
return None;
}
match zone.close(forest, nodes) {
Ok(table) => Some(Box::new(table)),
Err(reason) => {
*result = Err(reason);
None
}
}
}
pub(crate) fn plan(
forest: &Forest,
goal: &[OccId],
fragment: Fragment,
mode: Mode,
options: &Options,
) -> (Plan, Option<Plan>) {
let copies = options.copy_bound();
let both = options.bias == Bias::Auto
&& !mode.affine
&& fragment.has_exponentials()
&& forest.sequent().fragment().has_exponentials();
if !both {
let bias = if options.bias == Bias::Auto && mode.affine {
Bias::Rarer
} else {
options.bias
};
return (Plan { bias, copies }, None);
}
let forward = Plan {
bias: Bias::Factors,
copies: if !mode.mix && chains(forest, goal) {
copies.max(options.forward_copies)
} else {
copies
},
};
let backward = Plan {
bias: Bias::Rarer,
copies,
};
let same = super::bias::signs(forest, Bias::Factors) == super::bias::signs(forest, Bias::Rarer);
(forward, (!same).then_some(backward))
}
pub(super) fn chains(forest: &Forest, goal: &[OccId]) -> bool {
use crate::linear::occurrences::Sign;
use crate::linear::search::horn::{clause_head, is_head};
[Sign::Atom, Sign::Dual].into_iter().any(|body| {
let clause = |o: OccId| clause_head(forest, body, o).is_some();
goal.iter().all(|&member| {
if forest.kind(member) == Kind::Quest {
clause(forest.left(member).unwrap())
} else {
is_head(forest, body, member) || clause(member)
}
})
})
}
#[cfg(feature = "parallel")]
const SLICE: u64 = 1 << 16;
#[cfg(feature = "parallel")]
const POLL: std::time::Duration = std::time::Duration::from_millis(1);
#[cfg(feature = "parallel")]
#[derive(Default)]
struct Baton {
state: Mutex<Turns>,
changed: Condvar,
polls: AtomicU64,
halt: AtomicBool,
}
#[cfg(feature = "parallel")]
#[derive(Default)]
struct Turns {
holder: usize,
ended: [bool; 2],
stop: bool,
}
#[cfg(feature = "parallel")]
impl Baton {
fn lock(&self) -> std::sync::MutexGuard<'_, Turns> {
crate::linear::search::lock(&self.state)
}
fn wait(&self, me: usize) -> bool {
let mut turns = self.lock();
while turns.holder != me && !turns.stop {
turns = self
.changed
.wait(turns)
.unwrap_or_else(|poisoned| poisoned.into_inner());
}
turns.stop
}
fn pass(&self, me: usize) -> bool {
{
let mut turns = self.lock();
if turns.stop || turns.ended[1 - me] {
return turns.stop;
}
turns.holder = 1 - me;
}
self.changed.notify_all();
self.wait(me)
}
fn pass_polling(&self, stop: &mut dyn FnMut(u64) -> bool) -> bool {
{
let mut turns = self.lock();
if turns.stop || turns.ended[1] {
return turns.stop;
}
turns.holder = 1;
}
self.changed.notify_all();
loop {
{
let turns = self.lock();
if turns.stop {
return true;
}
if turns.holder == 0 {
break;
}
let waited = self.changed.wait_timeout(turns, POLL);
drop(waited.unwrap_or_else(|poisoned| poisoned.into_inner()));
}
if self.caught_up(stop) {
self.stop();
return true;
}
}
self.caught_up(stop)
}
fn stop(&self) {
self.halt.store(true, Ordering::Relaxed);
self.lock().stop = true;
self.changed.notify_all();
}
fn caught_up(&self, stop: &mut dyn FnMut(u64) -> bool) -> bool {
(0..self.polls.swap(0, Ordering::Relaxed)).any(|_| stop(0))
}
}
#[cfg(feature = "parallel")]
struct StopOnPanic<'a>(&'a Baton);
#[cfg(feature = "parallel")]
impl Drop for StopOnPanic<'_> {
fn drop(&mut self) {
if std::thread::panicking() {
self.0.stop();
}
}
}
#[cfg(feature = "parallel")]
struct Ended<'a>(&'a Baton, usize);
#[cfg(feature = "parallel")]
impl Drop for Ended<'_> {
fn drop(&mut self) {
let Ended(baton, me) = *self;
{
let mut turns = baton.lock();
turns.ended[me] = true;
turns.holder = 1 - me;
turns.stop |= std::thread::panicking();
if turns.stop {
baton.halt.store(true, Ordering::Relaxed);
}
}
baton.changed.notify_all();
}
}
#[cfg(feature = "parallel")]
pub(super) fn alternate<Z: Zone>(
set_up: SetUp<'_>,
[
(first, first_counts, first_account),
(second, second_counts, second_account),
]: [(Plan, &Counts, &Account); 2],
work: &crate::linear::search::Work,
stop: &mut dyn FnMut(u64) -> bool,
) -> Option<Finished> {
let (options, limits) = (set_up.options, set_up.limits);
let baton = Baton::default();
let (forward, backward) = std::thread::scope(|scope| {
let baton = &baton;
let thread = std::thread::Builder::new()
.name("deduxit-search".to_owned())
.stack_size(limits.stack_bytes())
.spawn_scoped(scope, move || {
let _ended = Ended(baton, 1);
if baton.wait(1) {
return Finished::gave_up(Reason::Stopped);
}
let mut counted = crate::linear::search::Counted::new(work);
let mut give_way = |units: u64, passed: bool| {
counted.add(units);
baton.polls.fetch_add(1, Ordering::Relaxed);
counted.passed()
|| baton.halt.load(Ordering::Relaxed)
|| (passed && baton.pass(1))
};
let slice = SLICE * BACKWARD_SHARE;
let (finished, _) = second.search::<Z>(
set_up,
second_counts,
second_account,
Stop::Slice(&mut give_way, slice, slice),
);
drop(counted);
if finished.result.is_ok() {
baton.stop();
}
finished
})
.ok()?;
let _stop = StopOnPanic(baton);
let forward = {
let _ended = Ended(baton, 0);
let mut give_way =
|units: u64, passed: bool| stop(units) || (passed && baton.pass_polling(stop));
let (finished, _) = first.search::<Z>(
set_up,
first_counts,
first_account,
Stop::Slice(&mut give_way, SLICE, SLICE),
);
if !matches!(finished.result, Err(reason) if reason != Reason::Stopped) {
baton.stop();
}
finished
};
loop {
let turns = baton.lock();
if turns.ended[1] {
break;
}
let waited = baton.changed.wait_timeout(turns, POLL);
drop(waited.unwrap_or_else(|poisoned| poisoned.into_inner()));
if baton.caught_up(stop) {
baton.stop();
}
}
let backward = thread
.join()
.unwrap_or_else(|panic| std::panic::resume_unwind(panic));
Some((forward, backward))
})?;
Some(merged(forward, backward, options, limits))
}
#[cfg(feature = "parallel")]
pub(super) fn merged(
first: Finished,
second: Finished,
options: &Options,
limits: &Limits,
) -> Finished {
let mut statistics = first.statistics;
statistics.add_run(&second.statistics);
statistics.memo_hits += second.statistics.memo_hits;
statistics.memo_entries += second.statistics.memo_entries;
statistics.forward_copies = first.statistics.copies;
statistics.copies = if first.result.is_ok() {
first.statistics.copies
} else {
second.statistics.copies
};
debug_assert!(
!matches!((&first.result, &second.result), (Ok(a), Ok(b)) if a.is_some() != b.is_some()),
"the two searches contradict each other"
);
let (result, nodes, instances) = match (first.result, second.result) {
(Ok(root), _) => (Ok(root), first.nodes, first.instances),
(_, Ok(root)) => (Ok(root), second.nodes, second.instances),
(Err(Reason::Stopped), _) | (_, Err(Reason::Stopped)) => {
(Err(Reason::Stopped), Vec::new(), None)
}
(Err(_), Err(reason)) => (Err(reason.as_set(options, limits)), Vec::new(), None),
};
Finished {
result,
nodes,
statistics,
instances,
}
}