use crate::linear::search::focus::memo::{Key, Zones};
const NONE: u32 = u32::MAX;
#[derive(Debug)]
pub(super) struct Waited {
pub(super) key: Key,
pub(super) hash: u64,
pub(super) budget: u32,
pub(super) exhausted: bool,
pub(super) hereditary: bool,
pub(super) leader: u32,
previous: u32,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) struct Reused {
pub(super) exhausted: bool,
pub(super) hereditary: bool,
pub(super) leader: u32,
}
#[derive(Debug, Default)]
pub(super) struct Waiting {
entries: Vec<Waited>,
index: crate::hash::HashMap<u64, u32>,
spare: Vec<Key>,
held: Vec<Waited>,
charged: usize,
}
impl Waiting {
pub(super) fn len(&self) -> usize {
self.entries.len()
}
pub(super) fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub(super) fn find(
&self,
key: Zones<'_>,
hash: u64,
budget: u32,
cut_known: bool,
) -> Option<Reused> {
let mut found = None;
let mut at = self.index.get(&hash).copied().unwrap_or(NONE);
while at != NONE {
let entry = &self.entries[at as usize];
if entry.hash == hash && key.of(&entry.key) {
if !entry.exhausted {
return Some(Reused {
exhausted: false,
hereditary: entry.hereditary,
leader: entry.leader,
});
}
if !cut_known && budget <= entry.budget && found.is_none() {
found = Some(Reused {
exhausted: true,
hereditary: false,
leader: entry.leader,
});
}
}
at = entry.previous;
}
found
}
pub(super) fn spare(&mut self) -> Option<Key> {
self.spare.pop()
}
pub(super) fn wait(
&mut self,
key: Key,
hash: u64,
budget: u32,
cuts: (bool, bool),
leader: u32,
) {
let (exhausted, hereditary) = cuts;
self.push(Waited {
key,
hash,
budget,
exhausted,
hereditary: hereditary && !exhausted,
leader,
previous: NONE,
});
}
fn push(&mut self, mut entry: Waited) {
let at = u32::try_from(self.entries.len()).expect("fewer entries than the memo holds");
entry.previous = self.index.insert(entry.hash, at).unwrap_or(NONE);
self.entries.push(entry);
}
fn pop(&mut self) -> Option<Waited> {
let entry = self.entries.pop()?;
if entry.previous == NONE {
self.index.remove(&entry.hash);
} else {
self.index.insert(entry.hash, entry.previous);
}
Some(entry)
}
pub(super) fn drop_from(&mut self, mark: usize) {
while self.entries.len() > mark {
let entry = self.pop().expect("an entry above the mark");
self.spare.push(entry.key);
}
}
pub(super) fn exhaust_from(&mut self, mark: usize) {
for entry in self.entries.iter_mut().skip(mark) {
entry.exhausted = true;
entry.hereditary = false;
}
}
pub(super) fn lead_from(&mut self, mark: usize, leader: u32) {
for entry in self.entries.iter_mut().skip(mark) {
entry.leader = entry.leader.min(leader);
}
}
pub(super) fn take_settled(&mut self, mark: usize, depth: u32) -> Option<Waited> {
while self.entries.len() > mark {
let entry = self.pop().expect("an entry above the mark");
if entry.leader >= depth {
return Some(entry);
}
self.held.push(entry);
}
None
}
pub(super) fn give(&mut self, key: Key) {
self.spare.push(key);
}
pub(super) fn settled(&mut self) {
while let Some(entry) = self.held.pop() {
self.push(entry);
}
}
pub(super) fn clear(&mut self) {
self.drop_from(0);
}
pub(super) fn grown(&mut self) -> usize {
const GROUP: usize = 16;
let index = match self.index.capacity() {
0 => 0,
held => {
(held * 8).div_ceil(7).next_power_of_two() * (size_of::<(u64, u32)>() + 1) + GROUP
}
};
let bytes = (self.entries.capacity() + self.held.capacity()) * size_of::<Waited>()
+ self.spare.capacity() * size_of::<Key>()
+ index;
let grown = bytes.saturating_sub(self.charged);
self.charged = self.charged.max(bytes);
grown
}
pub(super) fn release(&mut self) -> usize {
self.clear();
let keys: usize = self.spare.iter().map(|key| key.members.charged()).sum();
let charged = keys + self.charged;
*self = Self::default();
charged
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use crate::linear::search::{Bias, Engine, Options, Verdict, prove_within};
use crate::{
Limits,
linear::{Mode, Sequent},
};
#[test]
fn a_close_settles_by_every_rule() {
let mix = Mode::CLASSICAL.with_mix();
let (rarer, factors) = (Bias::Rarer, Bias::Factors);
for (text, mode, copies, bias, memo, proved, nodes, hits, entries) in [
(
"|- ~c, ?~c, ?((1 * c) * ?b), (c * !?~c)",
mix,
6,
rarer,
Some(16),
false,
1552,
434,
16,
),
(
"|- ?!?(~c * 1), !?!b, ?!(!bot par bot)",
Mode::CLASSICAL,
3,
factors,
None,
false,
28,
10,
7,
),
(
"|- !(?(bot par (?(1 * ~a) par a)) * ?(bot par (?(1 * ~a) par c))), ?bot",
mix,
4,
factors,
None,
false,
22,
7,
6,
),
(
"|- (?~a par ?~c), !~c, (?~a par ?~c), !~c, ?(c * c), ?~a, ?a, (?a * ?a)",
mix,
12,
factors,
None,
true,
287,
175,
69,
),
(
"|- ?(~b par ~b), ?b, !(b * ?!~c), ?(?(a par a) par !(a * b))",
mix,
2,
rarer,
None,
true,
166,
92,
57,
),
(
"!a, b, (!((c + (a + top)) & b) + !((c + (a + top)) & b)) |- (((!top * b) + (b * \
(top & top))) * (((c + (b + top)) & b) * b))",
mix,
2,
factors,
None,
true,
313,
202,
71,
),
(
"|- ?c, !(c * b), ?~c, (?~a par ?(~b * a))",
mix,
3,
factors,
None,
true,
38,
17,
11,
),
] {
let s: Sequent = text.parse().unwrap();
let mut options = Options::default()
.with_engine(Some(Engine::Focus))
.with_copies(Some(copies))
.with_bias(bias)
.with_jobs(1);
if let Some(memo) = memo {
options = options.with_memo_limit(memo);
}
let outcome = prove_within(&s, mode, &options, &Limits::default(), |_| false).unwrap();
let decided = match outcome.verdict {
Verdict::Proved(_) => Some(true),
Verdict::Unprovable(_) => Some(false),
Verdict::Unknown(_) => None,
};
let statistics = &outcome.statistics;
let counted = (
statistics.nodes,
statistics.memo_hits,
statistics.memo_entries,
);
assert_eq!(
(decided, counted),
(Some(proved), (nodes, hits, entries)),
"{text:?} in {mode} mode, copy bound {copies}, {bias:?}, memo {memo:?}"
);
}
}
#[test]
fn the_lists_are_charged_as_they_grow() {
use super::{Waited, Waiting};
use crate::linear::occurrences::OccId;
use crate::linear::search::focus::memo::Key;
use crate::linear::search::memory::{Account, Charged};
let account = Account::new(None);
let mut scratch = Charged::new(&account);
let mut waiting = Waiting::default();
let mut charged = 0;
for hash in 0..1000 {
let mut key = Key::default();
key.members.push(OccId::new(hash as u32));
key.members.settle(&mut scratch);
waiting.wait(key, hash, 0, (false, false), 1);
charged += waiting.grown();
}
assert_eq!(waiting.grown(), 0, "nothing grew since");
let entries = size_of::<Waited>() + size_of::<(u64, u32)>();
assert!(charged >= 1000 * entries, "{charged} bytes");
waiting.drop_from(0);
let spares = waiting.grown();
assert!(spares >= 1000 * size_of::<Key>(), "{spares} bytes");
let keys = account.used() as usize;
assert!(keys >= 1000 * size_of::<OccId>(), "{keys} bytes");
assert_eq!(waiting.release(), keys + charged + spares);
assert_eq!(waiting.grown(), 0, "released");
}
#[test]
fn a_relieved_search_settles_what_waits() {
let s: Sequent = "|- ?((((!~a par c) + c) par a) par ~c) par ?((~c * ~c) * c)"
.parse()
.unwrap();
let options = Options::default()
.with_copies(Some(2))
.with_bias(Bias::Rarer)
.with_jobs(1);
for kibibytes in [8, 12, 16, 24] {
let limits = Limits::default().with_memory_bytes(Some(kibibytes << 10));
let outcome =
prove_within(&s, Mode::CLASSICAL.with_mix(), &options, &limits, |_| false).unwrap();
assert!(
matches!(outcome.verdict, Verdict::Unknown(_)),
"{kibibytes} KiB: {:?}",
outcome.verdict
);
}
}
}