#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
use super::{Options as SearchOptions, Outcome};
use crate::{
Error, Limits,
linear::{Mode, Sequent},
};
use std::sync::Arc;
use std::sync::atomic::{AtomicBool, Ordering};
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Cores {
#[default]
Auto,
Across,
Within,
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(default, deny_unknown_fields)
)]
pub struct Options {
pub mode: Mode,
pub cores: Cores,
pub workers: usize,
#[cfg_attr(feature = "serialize", serde(with = "crate::serialize::exact"))]
pub total_memory_bytes: Option<u64>,
}
impl Options {
pub const DEFAULT_WORKERS: usize = 1;
pub const DEFAULT_TOTAL_MEMORY_BYTES: u64 = 4 << 30;
#[must_use]
pub const fn with_mode(self, mode: Mode) -> Self {
Self { mode, ..self }
}
#[must_use]
pub const fn with_cores(self, cores: Cores) -> Self {
Self { cores, ..self }
}
#[must_use]
pub const fn with_workers(self, workers: usize) -> Self {
Self { workers, ..self }
}
#[must_use]
pub const fn with_total_memory_bytes(self, total_memory_bytes: Option<u64>) -> Self {
Self {
total_memory_bytes,
..self
}
}
pub(crate) fn plan(&self, within: bool, search: &SearchOptions, limits: &Limits) -> Plan {
let search = search.clone();
let mut limits = *limits;
let total = self.total_memory_bytes;
if within {
limits.memory_bytes = smaller(limits.memory_bytes, total);
return Plan {
workers: 1,
search,
limits,
};
}
let most = self.workers.clamp(1, SearchOptions::MAX_JOBS);
let workers = match (limits.memory_bytes, total) {
(Some(each), Some(total)) => usize::try_from(total / each.max(1)).unwrap_or(usize::MAX),
(None, Some(total)) => {
limits.memory_bytes = Some(total / u64::try_from(most).unwrap_or(u64::MAX));
usize::MAX
}
(_, None) => usize::MAX,
};
limits.memory_bytes = smaller(limits.memory_bytes, total);
Plan {
workers: workers.clamp(1, most),
search: search.with_jobs(1),
limits,
}
}
}
fn smaller(a: Option<u64>, b: Option<u64>) -> Option<u64> {
match (a, b) {
(Some(a), Some(b)) => Some(a.min(b)),
(a, None) => a,
(None, b) => b,
}
}
impl Default for Options {
fn default() -> Self {
Self {
mode: Mode::CLASSICAL,
cores: Cores::Auto,
workers: Self::DEFAULT_WORKERS,
total_memory_bytes: Some(Self::DEFAULT_TOTAL_MEMORY_BYTES),
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Plan {
pub workers: usize,
pub search: SearchOptions,
pub limits: Limits,
}
impl Plan {
pub const fn alone(search: SearchOptions, limits: Limits) -> Self {
Self {
workers: 1,
search,
limits,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Problem {
pub name: String,
pub sequent: Sequent,
pub mode: Option<Mode>,
}
impl Problem {
pub fn new(name: impl Into<String>, sequent: Sequent, mode: Option<Mode>) -> Self {
Self {
name: name.into(),
sequent,
mode,
}
}
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Answer {
pub name: String,
pub outcome: Result<Outcome, Error>,
}
pub fn prove(
problems: impl IntoIterator<Item = Problem, IntoIter: Send + 'static>,
options: &Options,
search: &SearchOptions,
limits: &Limits,
) -> Results<Answer> {
let mode = options.mode;
run(
problems,
options,
search,
limits,
move |problem: Problem, plan: &Plan, cancel: &Cancel| {
let mode = problem.mode.unwrap_or(mode);
let outcome =
super::prove_within(&problem.sequent, mode, &plan.search, &plan.limits, |_| {
cancel.is_cancelled()
});
Answer {
outcome,
name: problem.name,
}
},
)
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
pub fn run<P, R>(
problems: impl IntoIterator<Item = P, IntoIter: Send + 'static>,
options: &Options,
search: &SearchOptions,
limits: &Limits,
work: impl Fn(P, &Plan, &Cancel) -> R + Send + Sync + 'static,
) -> Results<R>
where
P: Send + 'static,
R: Send + 'static,
{
let mut problems = problems.into_iter();
let mut first = Vec::new();
let within = match options.cores {
Cores::Across => false,
Cores::Within => true,
Cores::Auto => {
let workers = options.workers.clamp(1, SearchOptions::MAX_JOBS);
first.extend(problems.by_ref().take(workers));
first.len() < workers
}
};
let problems: Box<dyn Iterator<Item = P> + Send> = Box::new(first.into_iter().chain(problems));
let plan = options.plan(within, search, limits);
let cancel = Cancel::default();
#[cfg(feature = "parallel")]
let (problems, work) = if plan.workers > 1 {
match workers::Workers::start(problems, plan.clone(), cancel.clone(), work) {
Ok(workers) => {
return Results {
inner: Inner::Workers(workers),
cancel,
};
}
Err(unstarted) => unstarted,
}
} else {
(problems, work)
};
let canceller = cancel.clone();
Results {
inner: Inner::Here(Box::new(
problems.map(move |problem| work(problem, &plan, &canceller)),
)),
cancel,
}
}
#[derive(Clone, Debug, Default)]
pub struct Cancel(Arc<AtomicBool>);
impl Cancel {
pub fn is_cancelled(&self) -> bool {
self.0.load(Ordering::Relaxed)
}
pub fn cancel(&self) {
self.0.store(true, Ordering::Relaxed);
}
}
pub struct Results<R> {
inner: Inner<R>,
cancel: Cancel,
}
impl<R> Results<R> {
pub fn cancel(&self) {
self.cancel.cancel();
}
pub fn canceller(&self) -> Cancel {
self.cancel.clone()
}
}
impl<R> Drop for Results<R> {
fn drop(&mut self) {
self.cancel.cancel();
}
}
impl<R> std::fmt::Debug for Results<R> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("Results").finish_non_exhaustive()
}
}
enum Inner<R> {
Here(Box<dyn Iterator<Item = R> + Send>),
#[cfg(feature = "parallel")]
Workers(workers::Workers<R>),
}
impl<R> Iterator for Results<R> {
type Item = R;
fn next(&mut self) -> Option<R> {
match &mut self.inner {
Inner::Here(results) => results.next(),
#[cfg(feature = "parallel")]
Inner::Workers(workers) => workers.next(),
}
}
}
#[cfg(feature = "parallel")]
mod workers {
use super::{Cancel, Plan};
use std::collections::BTreeMap;
use std::panic::AssertUnwindSafe;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use std::sync::mpsc::{Receiver, channel};
use std::sync::{Arc, Condvar, Mutex};
use std::thread::JoinHandle;
use std::time::Duration;
pub(super) const AHEAD: usize = 4;
const WAIT: Duration = Duration::from_millis(10);
struct Queue<P> {
problems: Box<dyn Iterator<Item = P> + Send>,
taken: usize,
ended: bool,
}
struct Shared<P> {
queue: Mutex<Queue<P>>,
given: AtomicUsize,
turn: Condvar,
over: AtomicBool,
}
pub(super) struct Workers<R> {
done: Receiver<(usize, std::thread::Result<R>)>,
held: BTreeMap<usize, std::thread::Result<R>>,
next: usize,
given: Box<dyn Fn(usize) + Send>,
end: Box<dyn Fn() + Send>,
threads: Vec<JoinHandle<()>>,
}
impl<R: Send + 'static> Workers<R> {
pub(super) fn start<P: Send + 'static, W>(
problems: Box<dyn Iterator<Item = P> + Send>,
plan: Plan,
cancel: Cancel,
work: W,
) -> Result<Self, (Box<dyn Iterator<Item = P> + Send>, W)>
where
W: Fn(P, &Plan, &Cancel) -> R + Send + Sync + 'static,
{
let shared = Arc::new(Shared {
queue: Mutex::new(Queue {
problems,
taken: 0,
ended: false,
}),
given: AtomicUsize::new(0),
turn: Condvar::new(),
over: AtomicBool::new(false),
});
let work = Arc::new(work);
let (sender, done) = channel();
let ahead = AHEAD * plan.workers;
let mut threads = Vec::with_capacity(plan.workers);
for _ in 0..plan.workers {
let (shared, work, sender) = (shared.clone(), work.clone(), sender.clone());
let (plan, cancel) = (plan.clone(), cancel.clone());
let started = std::thread::Builder::new()
.name("batch".into())
.stack_size(plan.limits.stack_bytes())
.spawn(move || {
loop {
let (place, problem) = {
let mut queue = crate::linear::search::lock(&shared.queue);
while !queue.ended
&& !shared.over.load(Ordering::Acquire)
&& queue.taken >= shared.given.load(Ordering::Acquire) + ahead
{
queue = shared
.turn
.wait_timeout(queue, WAIT)
.unwrap_or_else(|poisoned| poisoned.into_inner())
.0;
}
if queue.ended || shared.over.load(Ordering::Acquire) {
return;
}
let next = std::panic::catch_unwind(AssertUnwindSafe(|| {
queue.problems.next()
}));
let place = queue.taken;
match next {
Ok(Some(problem)) => {
queue.taken += 1;
(place, problem)
}
Ok(None) => {
queue.ended = true;
return;
}
Err(panic) => {
queue.taken += 1;
drop(queue);
let _ = sender.send((place, Err(panic)));
cancel.cancel();
shared.over.store(true, Ordering::Release);
shared.turn.notify_all();
return;
}
}
};
let result = std::panic::catch_unwind(AssertUnwindSafe(|| {
work(problem, &plan, &cancel)
}));
let panicked = result.is_err();
if sender.send((place, result)).is_err() || panicked {
if panicked {
cancel.cancel();
shared.over.store(true, Ordering::Release);
shared.turn.notify_all();
}
return;
}
}
});
match started {
Ok(thread) => threads.push(thread),
Err(_) => break,
}
}
if threads.is_empty() {
let queue = Arc::try_unwrap(shared).ok().map(|s| s.queue);
let work = Arc::try_unwrap(work).ok();
if let (Some(queue), Some(work)) = (queue, work) {
let Queue { problems, .. } = crate::linear::search::taken(queue);
return Err((problems, work));
}
unreachable!("no worker started, so none holds the queue or the work");
}
let (raise, end) = (shared.clone(), shared);
Ok(Self {
done,
held: BTreeMap::new(),
next: 0,
given: Box::new(move |n| {
raise.given.store(n, Ordering::Release);
raise.turn.notify_all();
}),
end: Box::new(move || {
end.over.store(true, Ordering::Release);
end.turn.notify_all();
}),
threads,
})
}
}
impl<R> Workers<R> {
pub(super) fn next(&mut self) -> Option<R> {
loop {
if let Some(result) = self.held.remove(&self.next) {
self.next += 1;
(self.given)(self.next);
match result {
Ok(result) => return Some(result),
Err(panic) => std::panic::resume_unwind(panic),
}
}
match self.done.recv() {
Ok((place, result)) => {
self.held.insert(place, result);
}
Err(_) => {
for thread in self.threads.drain(..) {
if let Err(panic) = thread.join() {
std::panic::resume_unwind(panic);
}
}
return None;
}
}
}
}
}
impl<R> Drop for Workers<R> {
fn drop(&mut self) {
(self.end)();
}
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
use crate::linear::search::{Jobs, Reason, Verdict};
#[test]
fn answers_keep_the_problems_order() {
let texts: Vec<String> = (0..40)
.map(|i| match i % 3 {
0 => format!("a{i} |- a{i}"),
1 => format!("a{i} |- b{i}"),
_ => format!("a{i}, a{i} -o b{i} |- b{i}"),
})
.collect();
for (workers, cores) in [(1, Cores::Auto), (4, Cores::Across), (4, Cores::Auto)] {
let problems: Vec<Problem> = texts
.iter()
.map(|t| Problem::new(t.clone(), t.parse().unwrap(), None))
.collect();
let options = Options {
workers,
cores,
..Options::default()
};
let search = SearchOptions::default();
let answers: Vec<(String, bool)> =
prove(problems, &options, &search, &Limits::default())
.map(|a| {
let proved = matches!(a.outcome.unwrap().verdict, Verdict::Proved(_));
(a.name, proved)
})
.collect();
let expected: Vec<(String, bool)> = texts
.iter()
.enumerate()
.map(|(i, t)| (t.clone(), i % 3 != 1))
.collect();
assert_eq!(answers, expected);
}
}
#[test]
fn the_batch_bound_shares_out_the_memory() {
let options = Options {
workers: 16,
total_memory_bytes: Some(5 << 30),
..Options::default()
};
let search = SearchOptions::default().with_jobs(4);
let limits = Limits::default().with_memory_bytes(Some(1 << 30));
let across = options.plan(false, &search, &limits);
assert_eq!(
(across.workers, across.limits.memory_bytes),
(5, Some(1 << 30))
);
assert_eq!(across.search.jobs, Jobs::Count(1));
let within = Options {
total_memory_bytes: Some(1 << 30),
..options.clone()
}
.plan(true, &search, &limits);
assert_eq!(
(within.workers, within.limits.memory_bytes),
(1, Some(1 << 30))
);
let unbounded = options.with_workers(100_000).with_total_memory_bytes(None);
let plan = unbounded.plan(false, &search, &Limits::UNBOUNDED);
assert_eq!(plan.workers, SearchOptions::MAX_JOBS);
}
#[test]
fn cancelled_results_stop_their_searches() {
let literals: Vec<String> = (0..40).map(|i| format!("x{i}")).collect();
let text = format!(
"|- p * q, 0 * (~p par ~p), 0 * (~q par ~q), {}",
literals.join(", ")
);
let sequent: Sequent = text.parse().unwrap();
for workers in [1, 2] {
let problems: Vec<Problem> = (0..4)
.map(|i| Problem::new(i.to_string(), sequent.clone(), None))
.collect();
let options = Options::default()
.with_mode(Mode::CLASSICAL.with_affine())
.with_workers(workers)
.with_cores(Cores::Across);
let results = prove(
problems,
&options,
&SearchOptions::default(),
&Limits::default(),
);
results.cancel();
for answer in results {
let verdict = answer.outcome.unwrap().verdict;
assert!(
matches!(verdict, Verdict::Unknown(Reason::Stopped)),
"{verdict:?}"
);
}
}
}
#[test]
fn workers_that_cannot_start_leave_the_batch_here() {
let sequent: Sequent = "|- a, ~a".parse().unwrap();
let problems: Vec<Problem> = (0..3)
.map(|i| Problem::new(i.to_string(), sequent.clone(), None))
.collect();
let options = Options::default().with_workers(2).with_cores(Cores::Across);
let limits = Limits::default().with_recursion_depth(u32::MAX);
for answer in prove(problems, &options, &SearchOptions::default(), &limits) {
let verdict = answer.outcome.unwrap().verdict;
assert!(matches!(verdict, Verdict::Proved(_)), "{verdict:?}");
}
let options = Options::default()
.with_workers(usize::MAX)
.with_cores(Cores::Auto);
let endless =
std::iter::repeat_with(move || Problem::new("p".to_owned(), sequent.clone(), None));
let first = prove(
endless,
&options,
&SearchOptions::default(),
&Limits::default(),
)
.next();
assert!(matches!(
first.unwrap().outcome.unwrap().verdict,
Verdict::Proved(_)
));
}
#[cfg(feature = "parallel")]
#[test]
fn a_stream_is_answered_question_by_question() {
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::mpsc::channel;
let (sender, received) = channel();
std::thread::spawn(move || {
let (answered, answers) = channel::<usize>();
let questions = (0..20usize).inspect(move |&i| {
if i > 0 {
assert_eq!(answers.recv().unwrap(), i - 1);
}
});
let options = Options::default().with_workers(4).with_cores(Cores::Across);
let results = run(
questions,
&options,
&SearchOptions::default(),
&Limits::default(),
|i, _, _| i,
);
for answer in results {
let _ = answered.send(answer);
}
sender.send(()).unwrap();
});
assert!(
received
.recv_timeout(std::time::Duration::from_secs(20))
.is_ok()
);
let taken = std::sync::Arc::new(AtomicUsize::new(0));
let counted = taken.clone();
let problems = (0..1_000usize).inspect(move |_| {
counted.fetch_add(1, Ordering::Relaxed);
});
let options = Options::default().with_workers(2).with_cores(Cores::Across);
let mut results = run(
problems,
&options,
&SearchOptions::default(),
&Limits::default(),
|i, _, _| {
std::thread::sleep(std::time::Duration::from_millis(1));
i
},
);
assert_eq!(results.next(), Some(0));
std::thread::sleep(std::time::Duration::from_millis(50));
let window = 1 + workers::AHEAD * 2;
assert!(taken.load(Ordering::Relaxed) <= window, "{taken:?}");
}
#[test]
fn a_panic_ends_the_batch_at_its_place() {
let (sender, received) = std::sync::mpsc::channel();
std::thread::spawn(move || {
let options = Options::default().with_workers(2).with_cores(Cores::Across);
let mut results = run(
0..100usize,
&options,
&SearchOptions::default(),
&Limits::default(),
|i, _, _| {
assert_ne!(i, 5, "the work panics on problem 5");
i
},
);
let before: Vec<usize> = results.by_ref().take(5).collect();
let panicked =
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| results.next())).is_err();
sender.send((before, panicked)).unwrap();
});
let answer = received.recv_timeout(std::time::Duration::from_secs(20));
assert_eq!(answer, Ok(((0..5).collect(), true)));
}
#[cfg(feature = "parallel")]
#[test]
fn a_panic_of_the_problems_ends_the_batch_at_its_place() {
let (sender, received) = std::sync::mpsc::channel();
std::thread::spawn(move || {
let options = Options::default().with_workers(2).with_cores(Cores::Across);
let problems = (0..100usize).inspect(|&i| assert_ne!(i, 5, "the problems panic at 5"));
let mut results = run(
problems,
&options,
&SearchOptions::default(),
&Limits::default(),
|i, _, _| i,
);
let before: Vec<usize> = results.by_ref().take(5).collect();
let panicked =
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| results.next())).is_err();
sender.send((before, panicked)).unwrap();
});
let answer = received.recv_timeout(std::time::Duration::from_secs(20));
assert_eq!(answer, Ok(((0..5).collect(), true)));
}
#[cfg(feature = "parallel")]
#[test]
fn dropped_results_end_the_batch() {
use std::sync::atomic::{AtomicUsize, Ordering};
use std::sync::mpsc::{RecvTimeoutError, channel};
let taken = Arc::new(AtomicUsize::new(0));
let counted = taken.clone();
let (gone, problems_kept) = channel::<()>();
let problems = (0..1_000usize).inspect(move |_| {
let _ = &gone;
counted.fetch_add(1, Ordering::Relaxed);
});
let workers = 2;
let options = Options::default()
.with_workers(workers)
.with_cores(Cores::Across);
let mut results = run(
problems,
&options,
&SearchOptions::default(),
&Limits::default(),
|i, _, cancel: &Cancel| {
while i > 0 && !cancel.is_cancelled() {
std::thread::sleep(std::time::Duration::from_millis(1));
}
i
},
);
let cancel = results.canceller();
assert_eq!(results.next(), Some(0));
drop(results);
assert!(cancel.is_cancelled());
assert_eq!(
problems_kept.recv_timeout(std::time::Duration::from_secs(20)),
Err(RecvTimeoutError::Disconnected)
);
let window = 1 + workers::AHEAD * workers;
assert!(taken.load(Ordering::Relaxed) <= window, "{taken:?}");
}
}