use super::choices::Choices;
use super::classes::Classes;
use super::context::Context;
use super::framed::{Mark, Unified};
use super::scratch::{Pooled, Pools};
use crate::linear::Instances;
use crate::linear::occurrences::{Forest, Member, OccId, OccSet};
use crate::linear::proofs::Node;
use crate::linear::search::memory::Charged;
use crate::linear::search::{Options, Reason};
use crate::linear::sequents::{Eigen, FoTermId};
use std::fmt::Debug;
use std::hash::Hash;
pub(super) trait Zone: Sized + Send + Sync {
const FIRST_ORDER: bool = false;
type Member: Copy + Eq + Ord + Hash + Debug + Send + Sync + Into<Member> + 'static;
type Linear: Linear<Self::Member> + 'static;
type Unrestricted: Unrestricted<Self::Member> + 'static;
type Duals: Copy;
fn new(forest: &Forest, options: &Options) -> Self;
#[cfg(feature = "parallel")]
fn fork(&self) -> Self;
#[cfg(feature = "parallel")]
fn share(&mut self) {}
#[cfg(feature = "parallel")]
fn divides(&self) -> bool {
true
}
#[cfg(feature = "parallel")]
fn adopt(&mut self, _worker: Self) {}
#[cfg(feature = "parallel")]
fn cut_by(&mut self, _reason: Reason) {}
fn root(&self, o: OccId) -> Self::Member;
fn occurrence(&self, m: Self::Member) -> OccId;
fn child(&self, m: Self::Member, child: OccId) -> Self::Member;
fn dual_in(
&self,
forest: &Forest,
literal: Self::Member,
within: &Self::Unrestricted,
) -> Option<Self::Member>;
fn dual_from(
&self,
forest: &Forest,
literal: Self::Member,
rest: &Self::Linear,
cursors: &mut Cursors,
) -> Option<Self::Member>;
fn mark_literals(&mut self, forest: &Forest, members: &[Self::Member], scratch: &mut Charged);
fn duals(&self, forest: &Forest, literal: Self::Member) -> Option<Self::Duals>;
fn marked(&self, duals: Self::Duals) -> Option<Self::Member>;
fn first_lookup(&mut self, duals: Self::Duals) -> bool;
fn meets(&self, forest: &Forest, formula: Self::Member) -> bool;
fn class(&self, classes: &Classes, m: Self::Member) -> Self::Member;
fn same(&self, classes: &Classes, x: Self::Member, y: Self::Member) -> bool;
fn memoizes(&self, theta: &Self::Unrestricted, gamma: &Self::Linear) -> bool;
fn word_lists(pools: &mut Pools<Self>) -> &mut Vec<Pooled<OccId>>;
fn listed(words: &[OccId]) -> Option<&[Self::Member]>;
fn mark(&self) -> Mark {
unreachable!("a zone without binders binds nothing")
}
fn undo(&mut self, _mark: Mark) {
unreachable!("a zone without binders binds nothing")
}
fn begin_level(&mut self) {}
fn cut(&self) -> Option<Reason> {
None
}
fn forall(
&mut self,
_forest: &Forest,
_binder: Self::Member,
) -> Result<Option<Self::Member>, Reason> {
unreachable!("a zone without binders opens none")
}
fn introduced(&mut self) -> Eigen {
unreachable!("a zone without binders opens none")
}
fn exists(
&mut self,
_forest: &Forest,
_binder: Self::Member,
) -> Result<Option<(Self::Member, FoTermId)>, Reason> {
unreachable!("a zone without binders opens none")
}
fn opposite(&self, _forest: &Forest, _p: Self::Member, _q: Self::Member) -> bool {
unreachable!("a zone without binders unifies nothing")
}
fn unify(&mut self, _forest: &Forest, _p: Self::Member, _q: Self::Member) -> Unified {
unreachable!("a zone without binders unifies nothing")
}
fn open_answers(
&mut self,
_forest: &Forest,
_members: &mut dyn Iterator<Item = Self::Member>,
) -> bool {
unreachable!("a zone without binders has one answer")
}
fn searching_first(&mut self, _first: bool) {
unreachable!("a zone without binders has one answer")
}
fn record(&mut self, _forest: &Forest) -> usize {
unreachable!("a zone without binders has one answer")
}
fn exhausted(&mut self, _forest: &Forest) -> bool {
unreachable!("a zone without binders has one answer")
}
fn close_answers(&mut self) {
unreachable!("a zone without binders has one answer")
}
fn keys(
&mut self,
_forest: &Forest,
_theta: &Self::Unrestricted,
_gamma: &Self::Linear,
_own: &mut Vec<OccId>,
_canonical: &mut Vec<OccId>,
) -> bool {
unreachable!("a zone without binders keys its sequents by occurrence")
}
fn excluding(&self) -> bool {
unreachable!("a zone without binders has one answer")
}
fn take_steps(&mut self) -> u64 {
unreachable!("a zone without binders walks no term")
}
fn counts(&self) -> (u64, u64) {
unreachable!("a zone without binders unifies nothing")
}
fn held(&mut self) -> (usize, usize) {
unreachable!("a zone without binders holds no table")
}
fn close(&self, _forest: &Forest, _nodes: &mut [Node]) -> Result<Instances, Reason> {
unreachable!("a zone without binders keeps its proofs as they are")
}
fn choices(&mut self) -> &mut Choices {
unreachable!("a zone without binders has one answer")
}
}
pub(super) trait Linear<M>: Debug + Send + Sync {
fn empty(forest: &Forest) -> Self;
fn insert(&mut self, m: M);
fn remove(&mut self, m: M);
fn contains(&self, m: M) -> bool;
fn clear(&mut self);
fn copy_from(&mut self, other: &Self);
fn is_empty(&self) -> bool;
fn iter(&self) -> impl Iterator<Item = M> + '_;
fn list_into(&self, list: &mut Vec<M>);
fn ground(&self) -> &Context;
}
pub(super) trait Unrestricted<M>: Debug + Send + Sync {
fn empty(forest: &Forest) -> Self;
fn insert(&mut self, m: M);
fn contains(&self, m: M) -> bool;
fn clear(&mut self);
fn copy_from(&mut self, other: &Self);
fn iter(&self) -> impl Iterator<Item = M> + '_;
fn ground(&self) -> &OccSet;
}
impl Linear<OccId> for Context {
#[inline]
fn empty(forest: &Forest) -> Self {
Self::empty(forest.len())
}
#[inline]
fn insert(&mut self, m: OccId) {
Self::insert(self, m);
}
#[inline]
fn remove(&mut self, m: OccId) {
Self::remove(self, m);
}
#[inline]
fn contains(&self, m: OccId) -> bool {
Self::contains(self, m)
}
#[inline]
fn clear(&mut self) {
Self::clear(self);
}
#[inline]
fn copy_from(&mut self, other: &Self) {
self.clone_from(other);
}
#[inline]
fn is_empty(&self) -> bool {
Self::is_empty(self)
}
#[inline]
fn iter(&self) -> impl Iterator<Item = OccId> + '_ {
Self::iter(self)
}
#[inline]
fn list_into(&self, list: &mut Vec<OccId>) {
Self::list_into(self, list);
}
#[inline]
fn ground(&self) -> &Context {
self
}
}
impl Unrestricted<OccId> for OccSet {
#[inline]
fn empty(forest: &Forest) -> Self {
forest.empty_set()
}
#[inline]
fn insert(&mut self, m: OccId) {
Self::insert(self, m);
}
#[inline]
fn contains(&self, m: OccId) -> bool {
Self::contains(self, m)
}
#[inline]
fn clear(&mut self) {
Self::clear(self);
}
#[inline]
fn copy_from(&mut self, other: &Self) {
self.clone_from(other);
}
#[inline]
fn iter(&self) -> impl Iterator<Item = OccId> + '_ {
Self::iter(self)
}
#[inline]
fn ground(&self) -> &OccSet {
self
}
}
pub(super) struct Cursors {
pub(super) passed: Vec<u32>,
pub(super) moved: Vec<u32>,
}
#[derive(Clone, Copy, Debug)]
struct Marks {
stamp: u64,
first: OccId,
tried: u64,
}
pub(super) struct Ground {
lists: Vec<Marks>,
stamp: u64,
}
impl Zone for Ground {
type Member = OccId;
type Linear = Context;
type Unrestricted = OccSet;
type Duals = usize;
#[inline]
fn new(_: &Forest, _: &Options) -> Self {
Self {
lists: Vec::new(),
stamp: 0,
}
}
#[cfg(feature = "parallel")]
#[inline]
fn fork(&self) -> Self {
Self {
lists: Vec::new(),
stamp: 0,
}
}
#[inline]
fn root(&self, o: OccId) -> OccId {
o
}
#[inline]
fn occurrence(&self, m: OccId) -> OccId {
m
}
#[inline]
fn child(&self, _: OccId, child: OccId) -> OccId {
child
}
#[inline(always)]
fn dual_in(&self, f: &Forest, literal: OccId, within: &OccSet) -> Option<OccId> {
let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
f.literals(atom, !sign)
.iter()
.copied()
.find(|&d| within.contains(d))
}
#[inline]
fn dual_from(
&self,
f: &Forest,
literal: OccId,
rest: &Context,
cursors: &mut Cursors,
) -> Option<OccId> {
let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
let duals = f.literals(atom, !sign);
let list = Forest::list(atom, !sign);
let start = cursors.passed[list] as usize;
let found = duals[start..].iter().position(|&d| rest.contains(d));
let passed = found.map_or(duals.len(), |at| start + at);
if passed != start {
if start == 0 {
cursors.moved.push(list as u32);
}
cursors.passed[list] = passed as u32;
}
found.map(|at| duals[start + at])
}
#[inline]
fn mark_literals(&mut self, f: &Forest, members: &[OccId], scratch: &mut Charged) {
if self.lists.is_empty() {
let lists = f.lists();
scratch.charge(lists * size_of::<Marks>());
self.lists = vec![
Marks {
stamp: 0,
first: OccId::new(0),
tried: 0,
};
lists
];
}
self.stamp += 1;
for &m in members {
if let (Some(atom), Some(sign)) = (f.atom(m), f.sign(m)) {
let list = &mut self.lists[Forest::list(atom, sign)];
if list.stamp != self.stamp {
list.stamp = self.stamp;
list.first = m;
}
}
}
}
#[inline]
fn duals(&self, f: &Forest, literal: OccId) -> Option<usize> {
let (atom, sign) = (f.atom(literal)?, f.sign(literal)?);
Some(Forest::list(atom, !sign))
}
#[inline]
fn marked(&self, dual: usize) -> Option<OccId> {
let list = &self.lists[dual];
(list.stamp == self.stamp).then_some(list.first)
}
#[inline]
fn first_lookup(&mut self, dual: usize) -> bool {
let list = &mut self.lists[dual];
if list.tried == self.stamp {
return false;
}
list.tried = self.stamp;
true
}
#[inline]
fn meets(&self, f: &Forest, a: OccId) -> bool {
f.subtree(a).any(|l| match (f.atom(l), f.sign(l)) {
(Some(atom), Some(sign)) => self.lists[Forest::list(atom, !sign)].stamp == self.stamp,
_ => false,
})
}
#[inline]
fn class(&self, classes: &Classes, m: OccId) -> OccId {
classes.of(m)
}
#[inline]
fn same(&self, classes: &Classes, x: OccId, y: OccId) -> bool {
classes.same(x, y)
}
#[inline]
fn memoizes(&self, _: &OccSet, _: &Context) -> bool {
true
}
#[inline]
fn word_lists(pools: &mut Pools<Self>) -> &mut Vec<Pooled<OccId>> {
&mut pools.lists
}
#[inline]
fn listed(words: &[OccId]) -> Option<&[OccId]> {
Some(words)
}
}