use super::memo::{Entry, Failure, Key, Zones};
use super::zone::{Linear as _, Zone};
use super::{Cuts, Found, NO_DEPENDENCY, Run, Unrestricted};
use crate::linear::occurrences::OccId;
use crate::linear::search::Reason;
impl<Z: Zone> Run<'_, Z> {
pub(super) fn prove_keyed(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
budget: u32,
) -> Option<Result<(Found, bool), Reason>> {
let mut own = self.take_words();
let mut canonical = self.take_words();
let forest = self.problem.forest;
let keyed = self
.zone
.keys(forest, &theta.set, gamma, &mut own, &mut canonical);
own.settle(&mut self.scratch);
canonical.settle(&mut self.scratch);
let decided = match self.poll_terms() {
Err(reason) => Some(Err(reason)),
Ok(()) => keyed.then(|| self.prove_by_keys(theta, gamma, (&own, &canonical), budget)),
};
self.give_words(own);
self.give_words(canonical);
decided
}
fn prove_by_keys(
&mut self,
theta: &Unrestricted<Z>,
gamma: &Z::Linear,
(own, canonical): (&[OccId], &[OccId]),
budget: u32,
) -> Result<(Found, bool), Reason> {
let own = Zones {
theta: 0,
members: own,
};
let canonical = Zones {
theta: 0,
members: canonical,
};
let (own_hash, canonical_hash) = (own.hash(), canonical.hash());
if let Some(failure) = self.memo.refuted(canonical, canonical_hash) {
return Ok((Found::NOTHING, failure == Failure::Hereditary));
}
let cut = self.memo.get(own, own_hash, budget).is_some();
if self.problem.rules.stack
&& let Some(depth) = self.repeated(own, own_hash)
{
return Ok((Found::failed(Cuts::repeat(depth as u32)), false));
}
if cut {
return Ok((Found::failed(Cuts::BUDGET), false));
}
if self.problem.rules.stack {
self.push_stack(own, own_hash);
}
let nodes = self.nodes.mark();
let zone = self.zone.mark();
let mut members = self.take_list();
gamma.list_into(&mut members);
let result = self.decide(theta, gamma, &members, budget);
self.give_list(members);
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 Found::Failed(cuts) = found else {
return Ok((found, false));
};
self.nodes.release(nodes);
self.zone.undo(zone);
let dependency = if cuts.dependency >= own_depth {
NO_DEPENDENCY
} else {
cuts.dependency
};
if dependency == NO_DEPENDENCY && !self.zone.excluding() {
if cuts.exhausted {
self.remember(own, own_hash, Entry::Failed(Failure::Exhausted(budget)))?;
} else {
let complete = if hereditary {
Failure::Hereditary
} else {
Failure::Complete
};
self.remember(canonical, canonical_hash, Entry::Failed(complete))?;
}
}
let cuts = Cuts {
exhausted: cuts.exhausted,
dependency,
};
Ok((Found::failed(cuts), hereditary))
}
fn push_stack(&mut self, key: Zones<'_>, hash: u64) {
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;
}
}