use super::choices::Choices;
use super::classes::Classes;
use super::context::Context;
use super::scratch::{Pooled, Pools};
use super::zone::{Cursors, Linear, Unrestricted, Zone};
use crate::hash::{HashMap, HashSet};
use crate::linear::Instances;
use crate::linear::occurrences::{Forest, FrameId, Member, OccId, OccSet};
use crate::linear::proofs::Node;
use crate::linear::search::memory::{Charged, bytes_of};
use crate::linear::search::{Options, Reason};
use crate::linear::sequents::fo::FirstOrder;
use crate::linear::sequents::{Eigen, FoTerm, FoTermId, Symbol};
use std::cell::RefCell;
use std::collections::hash_map::Entry;
use std::sync::Arc;
use std::sync::atomic::{AtomicU64, Ordering};
const NONE: u32 = u32::MAX;
#[cfg(test)]
thread_local! {
pub(super) static MEMBER_LIMIT: std::cell::Cell<u32> = const { std::cell::Cell::new(u32::MAX) };
}
fn member_limit() -> u32 {
#[cfg(test)]
{
MEMBER_LIMIT.with(std::cell::Cell::get)
}
#[cfg(not(test))]
{
u32::MAX
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub(super) struct FMember(u32);
impl From<FMember> for Member {
fn from(m: FMember) -> Self {
Self::new(m.0)
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct TRef {
id: u32,
frame: u32,
}
#[derive(Clone, Copy, Debug)]
enum Var {
Meta {
binding: Option<TRef>,
level: u32,
},
Eigen(u32),
}
#[derive(Clone, Copy, Debug)]
enum Undone {
Bound(u32),
Lowered(u32, u32),
Named(u32),
}
#[derive(Clone, Copy, Debug)]
enum Named {
Unknown,
Ground(u32),
Open(u32),
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
enum Head {
Symbol(u32),
Applied(u32),
}
#[derive(Clone, Debug)]
enum Grounds {
Own(HashMap<(Head, u32), u32>),
#[cfg(feature = "parallel")]
Shared(Arc<SharedGrounds>),
}
#[cfg(feature = "parallel")]
#[derive(Debug)]
struct SharedGrounds {
table: std::sync::Mutex<HashMap<(Head, u32), u32>>,
slots: std::sync::atomic::AtomicUsize,
}
impl Grounds {
fn apply(&mut self, symbol: Symbol, args: &[Name]) -> Name {
match self {
Self::Own(table) => Framed::apply(table, symbol, args),
#[cfg(feature = "parallel")]
Self::Shared(shared) => {
let mut table = crate::linear::search::lock(&shared.table);
let name = Framed::apply(&mut table, symbol, args);
shared.slots.store(table.capacity(), Ordering::Relaxed);
name
}
}
}
fn capacity(&self) -> usize {
match self {
Self::Own(table) => table.capacity(),
#[cfg(feature = "parallel")]
Self::Shared(shared) => shared.slots.load(Ordering::Relaxed),
}
}
}
#[derive(Clone, Copy, Debug)]
enum Naming {
Term(TRef),
Var(u32),
Apply(Symbol, u32),
Keep(u32),
}
#[derive(Clone, Copy, Debug)]
enum Name {
Ground(u32),
Open(u32),
Past,
}
#[derive(Clone, Copy, Debug)]
struct Span {
base: u32,
end: u32,
first: u32,
frame: u32,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Mark {
spans: usize,
frames: usize,
vars: usize,
eigens: u32,
trail: usize,
introduced: usize,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Unified {
Yes,
No,
Cut,
}
#[derive(Clone, Copy, Debug)]
enum Pat {
Var(u32),
Eigen(u32),
Closed(u32),
App(Symbol, u32, u32),
}
#[derive(Clone, Debug, Default)]
struct Pattern {
nodes: Vec<Pat>,
kids: Vec<u32>,
roots: Vec<u32>,
levels: Vec<u32>,
}
#[derive(Clone, Debug)]
struct Answers {
metas: Vec<u32>,
patterns: Vec<Pattern>,
first: bool,
}
pub(super) struct Framed {
occurrences: u32,
base: u32,
spans: Vec<Span>,
frames: Vec<(u32, TRef)>,
vars: Vec<Var>,
eigens: u32,
trail: Vec<Undone>,
introduced: Vec<Eigen>,
answers: Vec<Answers>,
choices: Choices,
witness_depth: u32,
instances: u32,
cut: Option<Reason>,
closed: Arc<[bool]>,
depth: Arc<[u32]>,
marks: Vec<u64>,
stamp: u64,
steps: AtomicU64,
unifications: u64,
bindings: u64,
charged: usize,
pairs: Vec<(TRef, TRef)>,
met: HashSet<(TRef, TRef)>,
walk: Vec<(TRef, bool)>,
depths: HashMap<TRef, u32>,
key: KeyScratch,
ground: Grounds,
arena: Arc<[u32]>,
named: Vec<Named>,
naming: Vec<Naming>,
names: Vec<Name>,
}
impl Framed {
fn step(&self) {
self.steps.fetch_add(1, Ordering::Relaxed);
}
fn instance(&self, m: FMember) -> (OccId, u32) {
if m.0 < self.occurrences {
return (OccId::new(m.0), NONE);
}
let span = self.spans[self.spans.partition_point(|s| s.base <= m.0) - 1];
(OccId::new(span.first + (m.0 - span.base)), span.frame)
}
fn frame_term(&self, mut frame: u32, i: u32) -> TRef {
for _ in 0..i {
frame = self.frames[frame as usize].0;
}
self.frames[frame as usize].1
}
fn deref(&self, fo: &FirstOrder, mut t: TRef) -> TRef {
loop {
if t.id < self.base {
if let FoTerm::Bound(i) = fo.terms[t.id as usize] {
t = self.frame_term(t.frame, i);
continue;
}
if self.closed[t.id as usize] {
t.frame = NONE;
}
return t;
}
match self.vars[(t.id - self.base) as usize] {
Var::Meta {
binding: Some(b), ..
} => t = b,
_ => return t,
}
}
}
fn var(&self, t: TRef) -> Option<u32> {
t.id.checked_sub(self.base)
}
fn level(&self, v: u32) -> u32 {
match self.vars[v as usize] {
Var::Meta { level, .. } => level,
Var::Eigen(number) => number + 1,
}
}
fn app(fo: &FirstOrder, t: TRef) -> (Symbol, &[FoTermId]) {
match fo.terms[t.id as usize] {
FoTerm::App(symbol, args) => (symbol, fo.list(args)),
term => unreachable!("{term:?} is no application after a deref"),
}
}
fn push_var(&mut self, var: Var) -> Result<TRef, Reason> {
let id = u32::try_from(self.vars.len())
.ok()
.and_then(|v| self.base.checked_add(v))
.filter(|&id| id < u32::MAX)
.ok_or(Reason::IndexLimit)?;
self.vars.push(var);
self.named.push(Named::Unknown);
Ok(TRef { id, frame: NONE })
}
fn open(&mut self, forest: &Forest, binder: FMember, term: TRef) -> Result<FMember, Reason> {
let (o, frame) = self.instance(binder);
let frames = u32::try_from(self.frames.len())
.ok()
.filter(|&f| f < NONE)
.ok_or(Reason::IndexLimit)?;
let base = self.spans.last().map_or(self.occurrences, |s| s.end);
let end = base
.checked_add(forest.size(o) - 1)
.filter(|&end| end <= member_limit())
.ok_or(Reason::IndexLimit)?;
self.frames.push((frame, term));
self.spans.push(Span {
base,
end,
first: o.get() + 1,
frame: frames,
});
Ok(FMember(base))
}
fn full(&mut self) -> bool {
if self.spans.len() >= self.instances as usize {
self.cut = Some(Reason::Instances {
instances: self.instances,
});
return true;
}
false
}
fn bind(&mut self, fo: &FirstOrder, x: u32, t: TRef) -> Unified {
let level = self.level(x);
self.depths.clear();
self.walk.clear();
self.walk.push((t, false));
while let Some((u, expanded)) = self.walk.pop() {
self.step();
let u = self.deref(fo, u);
if !expanded && self.depths.contains_key(&u) {
continue;
}
let depth = if let Some(v) = self.var(u) {
match self.vars[v as usize] {
Var::Meta { level: l, .. } => {
if v == x {
return Unified::No;
}
if l > level {
self.trail.push(Undone::Lowered(v, l));
self.vars[v as usize] = Var::Meta {
binding: None,
level,
};
}
}
Var::Eigen(number) => {
if number + 1 > level {
return Unified::No;
}
}
}
0
} else if self.closed[u.id as usize] {
self.depth[u.id as usize]
} else {
let (_, args) = Self::app(fo, u);
if !expanded {
self.walk.push((u, true));
self.walk.extend(args.iter().map(|&a| {
(
TRef {
id: a.get(),
frame: u.frame,
},
false,
)
}));
continue;
}
let deepest = args
.iter()
.map(|&a| {
let child = self.deref(
fo,
TRef {
id: a.get(),
frame: u.frame,
},
);
self.depths[&child]
})
.max();
deepest.map_or(0, |d| d + 1)
};
if depth > self.witness_depth {
self.cut = Some(Reason::WitnessDepth {
depth: self.witness_depth,
});
return Unified::Cut;
}
self.depths.insert(u, depth);
}
self.trail.push(Undone::Bound(x));
self.bindings += 1;
self.vars[x as usize] = Var::Meta {
binding: Some(t),
level,
};
Unified::Yes
}
fn unify_pairs(&mut self, fo: &FirstOrder) -> Unified {
self.met.clear();
while let Some((a, b)) = self.pairs.pop() {
self.step();
let (a, b) = (self.deref(fo, a), self.deref(fo, b));
if a == b || !self.met.insert((a, b)) {
continue;
}
let found = match (self.var(a), self.var(b)) {
(Some(x), Some(y)) => match (self.vars[x as usize], self.vars[y as usize]) {
(Var::Meta { level: l, .. }, Var::Meta { level: m, .. }) => {
if l >= m {
self.bind(fo, x, b)
} else {
self.bind(fo, y, a)
}
}
(Var::Meta { .. }, Var::Eigen(_)) => self.bind(fo, x, b),
(Var::Eigen(_), Var::Meta { .. }) => self.bind(fo, y, a),
(Var::Eigen(_), Var::Eigen(_)) => Unified::No,
},
(Some(x), None) => match self.vars[x as usize] {
Var::Meta { .. } => self.bind(fo, x, b),
Var::Eigen(_) => Unified::No,
},
(None, Some(y)) => match self.vars[y as usize] {
Var::Meta { .. } => self.bind(fo, y, a),
Var::Eigen(_) => Unified::No,
},
(None, None) => {
let ((s, xs), (r, ys)) = (Self::app(fo, a), Self::app(fo, b));
if s != r {
Unified::No
} else {
self.pairs.extend(xs.iter().zip(ys).map(|(&x, &y)| {
(
TRef {
id: x.get(),
frame: a.frame,
},
TRef {
id: y.get(),
frame: b.frame,
},
)
}));
Unified::Yes
}
}
};
if found != Unified::Yes {
self.pairs.clear();
return found;
}
}
Unified::Yes
}
fn equal(&self, fo: &FirstOrder, a: TRef, b: TRef) -> bool {
let mut pairs = vec![(a, b)];
let mut met = HashSet::default();
while let Some((a, b)) = pairs.pop() {
self.step();
let (a, b) = (self.deref(fo, a), self.deref(fo, b));
if a == b || !met.insert((a, b)) {
continue;
}
if self.var(a).is_some() || self.var(b).is_some() {
return false;
}
let ((s, xs), (r, ys)) = (Self::app(fo, a), Self::app(fo, b));
if s != r {
return false;
}
pairs.extend(xs.iter().zip(ys).map(|(&x, &y)| {
(
TRef {
id: x.get(),
frame: a.frame,
},
TRef {
id: y.get(),
frame: b.frame,
},
)
}));
}
true
}
fn fits(&self, fo: &FirstOrder, t: TRef, level: u32) -> bool {
let mut walk = vec![t];
let mut met = HashSet::default();
while let Some(u) = walk.pop() {
self.step();
let u = self.deref(fo, u);
if !met.insert(u) {
continue;
}
if let Some(v) = self.var(u) {
let fits = match self.vars[v as usize] {
Var::Meta { level: l, .. } => l <= level,
Var::Eigen(number) => number < level,
};
if !fits {
return false;
}
} else if !self.closed[u.id as usize] {
walk.extend(Self::app(fo, u).1.iter().map(|&a| TRef {
id: a.get(),
frame: u.frame,
}));
}
}
true
}
fn instance_of(&self, fo: &FirstOrder, metas: &[u32], pattern: &Pattern) -> bool {
let mut theta: Vec<Option<TRef>> = vec![None; pattern.levels.len()];
let mut walk: Vec<(u32, TRef)> = metas
.iter()
.zip(&pattern.roots)
.map(|(&m, &root)| {
(
root,
TRef {
id: self.base + m,
frame: NONE,
},
)
})
.collect();
let mut met = HashSet::default();
while let Some((node, t)) = walk.pop() {
self.step();
let t = self.deref(fo, t);
if !met.insert((node, t)) {
continue;
}
let fits = match pattern.nodes[node as usize] {
Pat::Var(k) => match theta[k as usize] {
None => {
theta[k as usize] = Some(t);
self.fits(fo, t, pattern.levels[k as usize])
}
Some(u) => self.equal(fo, u, t),
},
Pat::Eigen(number) => self
.var(t)
.is_some_and(|v| matches!(self.vars[v as usize], Var::Eigen(n) if n == number)),
Pat::Closed(id) => self.equal(fo, TRef { id, frame: NONE }, t),
Pat::App(symbol, start, len) => {
if self.var(t).is_some() {
false
} else {
let (s, args) = Self::app(fo, t);
let kids = &pattern.kids[start as usize..(start + len) as usize];
walk.extend(kids.iter().zip(args).map(|(&kid, &a)| {
(
kid,
TRef {
id: a.get(),
frame: t.frame,
},
)
}));
s == symbol
}
}
};
if !fits {
return false;
}
}
true
}
fn passes(&self, fo: &FirstOrder) -> bool {
self.answers
.iter()
.filter(|answers| answers.first)
.all(|answers| {
answers
.patterns
.iter()
.all(|p| !self.instance_of(fo, &answers.metas, p))
})
}
fn pattern(&self, fo: &FirstOrder, metas: &[u32]) -> Pattern {
let mut pattern = Pattern::default();
let mut nodes: HashMap<TRef, u32> = HashMap::default();
let mut numbered: HashMap<u32, u32> = HashMap::default();
for &m in metas {
let root = TRef {
id: self.base + m,
frame: NONE,
};
let mut walk = vec![(root, false)];
while let Some((u, expanded)) = walk.pop() {
self.step();
let u = self.deref(fo, u);
if !expanded && nodes.contains_key(&u) {
continue;
}
let node = if let Some(v) = self.var(u) {
match self.vars[v as usize] {
Var::Meta { level, .. } => {
let k = *numbered.entry(v).or_insert_with(|| {
pattern.levels.push(level);
(pattern.levels.len() - 1) as u32
});
Pat::Var(k)
}
Var::Eigen(number) => Pat::Eigen(number),
}
} else if self.closed[u.id as usize] {
Pat::Closed(u.id)
} else {
let (symbol, args) = Self::app(fo, u);
let child = |a: &FoTermId| TRef {
id: a.get(),
frame: u.frame,
};
if !expanded {
walk.push((u, true));
walk.extend(args.iter().map(|a| (child(a), false)));
continue;
}
let start = pattern.kids.len() as u32;
for a in args {
let kid = nodes[&self.deref(fo, child(a))];
pattern.kids.push(kid);
}
Pat::App(symbol, start, args.len() as u32)
};
pattern.nodes.push(node);
nodes.insert(u, (pattern.nodes.len() - 1) as u32);
}
pattern.roots.push(nodes[&self.deref(fo, root)]);
}
pattern
}
fn key(forest: &Forest, o: OccId, dual: bool) -> Option<usize> {
let (atom, sign) = (forest.atom(o)?, forest.sign(o)?);
let fo = &forest.sequent().fo;
let index = match fo.atoms.get(atom.index()) {
Some(&(symbol, _)) => symbol.index(),
None => atom.index(),
};
Some(2 * index + (sign as usize ^ usize::from(dual)))
}
}
const TAG: u32 = 3 << 30;
const GROUND: u32 = 0;
const APP: u32 = 1 << 30;
const EIGEN: u32 = 2 << 30;
const META: u32 = 3 << 30;
const VALUE: u32 = !TAG;
const KEY_WORDS: usize = 1 << 16;
#[derive(Debug, Default)]
struct KeyScratch {
words: Vec<u32>,
starts: Vec<usize>,
copies: Vec<u32>,
order: Vec<usize>,
eigens: Vec<u32>,
metas: Vec<u32>,
numbers: HashMap<u32, u32>,
walk: Vec<TRef>,
}
impl KeyScratch {
fn bytes(&self) -> usize {
bytes_of(&self.words)
+ bytes_of(&self.starts)
+ bytes_of(&self.copies)
+ bytes_of(&self.order)
+ bytes_of(&self.eigens)
+ bytes_of(&self.metas)
+ bytes_of(&self.walk)
+ self.numbers.capacity() * (size_of::<(u32, u32)>() + 1)
}
fn range(&self, i: usize) -> std::ops::Range<usize> {
let end = self.starts.get(i + 1).copied().unwrap_or(self.words.len());
self.starts[i]..end
}
fn member(&self, i: usize) -> &[u32] {
&self.words[self.range(i)]
}
fn abstract_order(&self, x: usize, y: usize) -> std::cmp::Ordering {
let (x, y) = (self.member(x), self.member(y));
x[0].cmp(&y[0]).then_with(|| {
x[1..]
.iter()
.map(|&w| self.abstracted(w))
.cmp(y[1..].iter().map(|&w| self.abstracted(w)))
})
}
fn abstracted(&self, word: u32) -> u32 {
match word & TAG {
META => META,
EIGEN => EIGEN | self.rank(word & VALUE),
_ => word,
}
}
fn rank(&self, number: u32) -> u32 {
self.eigens.partition_point(|&n| n < number) as u32
}
}
impl Framed {
fn write_keys(
&mut self,
forest: &Forest,
theta: &Set,
gamma: &Members,
own: &mut Vec<OccId>,
canonical: &mut Vec<OccId>,
) -> bool {
let fo = &forest.sequent().fo;
let mut s = std::mem::take(&mut self.key);
s.words.clear();
s.starts.clear();
s.copies.clear();
s.eigens.clear();
let written = gamma
.0
.chunk_by(|x, y| x == y)
.chain(theta.0.chunks(1))
.all(|copies| {
u32::try_from(copies.len()).is_ok_and(|n| {
s.copies.push(n);
self.write_member(fo, copies[0], &mut s)
})
});
if written {
let sorting = usize::BITS - s.starts.len().leading_zeros();
self.steps.fetch_add(
(s.words.len() as u64).saturating_mul(2 * u64::from(1 + sorting)),
Ordering::Relaxed,
);
s.eigens.sort_unstable();
s.eigens.dedup();
let n = gamma.0.chunk_by(|x, y| x == y).count();
self.own_key(&mut s, n, own);
self.canonical_key(&mut s, n, canonical);
}
self.key = s;
written
}
fn write_member(&mut self, fo: &FirstOrder, m: FMember, s: &mut KeyScratch) -> bool {
let (o, mut frame) = self.instance(m);
s.starts.push(s.words.len());
s.words.push(o.get());
while frame != NONE {
let (parent, term) = self.frames[frame as usize];
s.walk.clear();
s.walk.push(term);
while let Some(t) = s.walk.pop() {
self.step();
if s.words.len() >= KEY_WORDS {
return false;
}
let (tag, value) = match self.name(fo, t) {
Name::Ground(id) => (GROUND, id),
Name::Past => return false,
Name::Open(_) => {
let t = self.deref(fo, t);
if let Some(v) = self.var(t) {
match self.vars[v as usize] {
Var::Meta { .. } => (META, v),
Var::Eigen(number) => {
s.eigens.push(number);
(EIGEN, number)
}
}
} else {
let (symbol, args) = Self::app(fo, t);
s.walk.extend(args.iter().rev().map(|a| TRef {
id: a.get(),
frame: t.frame,
}));
(APP, symbol.get())
}
}
};
if value > VALUE {
return false;
}
s.words.push(tag | value);
}
frame = parent;
}
true
}
fn name(&mut self, fo: &FirstOrder, t: TRef) -> Name {
if let Some(v) = self.var(t) {
match self.vars[v as usize] {
Var::Meta {
binding: Some(_), ..
} => {
if let Some(name) = self.kept(v) {
return name;
}
}
_ => return Name::Open(v),
}
}
let mut steps = std::mem::take(&mut self.naming);
let mut names = std::mem::take(&mut self.names);
steps.clear();
names.clear();
steps.push(Naming::Term(t));
while let Some(step) = steps.pop() {
self.step();
match step {
Naming::Term(mut t) => {
while t.id < self.base
&& let FoTerm::Bound(i) = fo.terms[t.id as usize]
{
t = self.frame_term(t.frame, i);
}
if let Some(v) = self.var(t) {
steps.push(Naming::Var(v));
} else if self.closed[t.id as usize] {
names.push(match self.arena[t.id as usize] {
NONE => Name::Past,
id => Name::Ground(id),
});
} else {
let (symbol, args) = Self::app(fo, t);
steps.push(Naming::Apply(symbol, args.len() as u32));
steps.extend(args.iter().rev().map(|a| {
Naming::Term(TRef {
id: a.get(),
frame: t.frame,
})
}));
}
}
Naming::Var(v) => match self.vars[v as usize] {
Var::Meta {
binding: Some(b), ..
} => match self.kept(v) {
Some(name) => names.push(name),
None => {
steps.push(Naming::Keep(v));
steps.push(Naming::Term(b));
}
},
_ => names.push(Name::Open(v)),
},
Naming::Apply(symbol, arity) => {
let at = names.len() - arity as usize;
let name = self.ground.apply(symbol, &names[at..]);
names.truncate(at);
names.push(name);
}
Naming::Keep(v) => {
let kept = match names.last() {
Some(&Name::Ground(id)) => Named::Ground(id),
Some(&Name::Open(w)) => Named::Open(w),
_ => continue,
};
self.named[v as usize] = kept;
self.trail.push(Undone::Named(v));
}
}
}
let name = names.pop().expect("a walk names its term");
self.naming = steps;
self.names = names;
name
}
fn kept(&self, v: u32) -> Option<Name> {
match self.named[v as usize] {
Named::Unknown => None,
Named::Ground(id) => Some(Name::Ground(id)),
Named::Open(w) => match self.vars[w as usize] {
Var::Meta {
binding: Some(_), ..
} => None,
_ => Some(Name::Open(w)),
},
}
}
fn apply(ground: &mut HashMap<(Head, u32), u32>, symbol: Symbol, args: &[Name]) -> Name {
let mut past = false;
for &arg in args {
match arg {
Name::Open(v) => return Name::Open(v),
Name::Past => past = true,
Name::Ground(_) => {}
}
}
if past {
return Name::Past;
}
let ids = args.iter().map(|&arg| match arg {
Name::Ground(id) => id,
Name::Open(_) | Name::Past => unreachable!("every argument is ground"),
});
let mut head = Head::Symbol(symbol.get());
let mut id = NONE;
for arg in ids.chain(args.is_empty().then_some(NONE)) {
let next = u32::try_from(ground.len())
.ok()
.filter(|&next| next <= VALUE);
id = match (ground.entry((head, arg)), next) {
(Entry::Occupied(entry), _) => *entry.get(),
(Entry::Vacant(entry), Some(next)) => *entry.insert(next),
(Entry::Vacant(_), None) => return Name::Past,
};
head = Head::Applied(id);
}
Name::Ground(id)
}
fn meta_level(&self, v: u32) -> u32 {
match self.vars[v as usize] {
Var::Meta { level, .. } => level,
Var::Eigen(_) => unreachable!("a metavariable's word names a metavariable"),
}
}
fn own_key(&self, s: &mut KeyScratch, n: usize, key: &mut Vec<OccId>) {
let total = s.starts.len();
s.order.clear();
s.order.extend(0..total);
let mut order = std::mem::take(&mut s.order);
order[..n].sort_by(|&x, &y| s.member(x).cmp(s.member(y)));
order[n..].sort_by(|&x, &y| s.member(x).cmp(s.member(y)));
s.metas.clear();
s.numbers.clear();
key.clear();
for members in [&order[..n], &order[n..]] {
key.push(OccId::new(members.len() as u32));
for &i in members {
let range = s.range(i);
key.push(OccId::new(s.copies[i]));
key.push(OccId::new(s.words[range.start]));
for &w in &s.words[range.start + 1..range.end] {
if w & TAG == META && s.numbers.insert(w & VALUE, 0).is_none() {
s.metas.push(w & VALUE);
}
key.push(OccId::new(w));
}
}
}
key.extend(s.metas.iter().map(|&v| OccId::new(self.meta_level(v))));
s.order = order;
}
fn canonical_key(&self, s: &mut KeyScratch, n: usize, key: &mut Vec<OccId>) {
let mut order = std::mem::take(&mut s.order);
order[..n].sort_by(|&x, &y| s.abstract_order(x, y));
order[n..].sort_by(|&x, &y| s.abstract_order(x, y));
s.metas.clear();
s.numbers.clear();
key.clear();
for members in [&order[..n], &order[n..]] {
key.push(OccId::new(members.len() as u32));
for &i in members {
let range = s.range(i);
key.push(OccId::new(s.copies[i]));
key.push(OccId::new(s.words[range.start]));
for j in range.start + 1..range.end {
let w = s.words[j];
let word = match w & TAG {
META => {
let v = w & VALUE;
let next = s.metas.len() as u32;
let number = *s.numbers.entry(v).or_insert(next);
if number == next {
s.metas.push(v);
}
META | number
}
EIGEN => EIGEN | s.rank(w & VALUE),
_ => w,
};
key.push(OccId::new(word));
}
}
}
key.extend(
s.metas
.iter()
.map(|&v| OccId::new(s.rank(self.meta_level(v)))),
);
s.order = order;
}
}
impl Zone for Framed {
const FIRST_ORDER: bool = true;
type Member = FMember;
type Linear = Members;
type Unrestricted = Set;
type Duals = usize;
fn new(forest: &Forest, options: &Options) -> Self {
let fo = &forest.sequent().fo;
let mut closed = vec![true; fo.terms.len()];
let mut depth = vec![0; fo.terms.len()];
for (i, term) in fo.terms.iter().enumerate() {
(closed[i], depth[i]) = match *term {
FoTerm::Bound(_) => (false, 0),
FoTerm::App(_, args) => {
let args = fo.list(args);
(
args.iter().all(|a| closed[a.index()]),
args.iter().map(|a| depth[a.index()] + 1).max().unwrap_or(0),
)
}
FoTerm::Eigen(_) | FoTerm::Meta(_) => {
unreachable!("a sequent's arena holds no eigenvariable or metavariable")
}
};
}
let occurrences = forest.len() as u32;
let mut ground = Grounds::Own(HashMap::default());
let mut arena = vec![NONE; fo.terms.len()];
let mut names = Vec::new();
for (i, term) in fo.terms.iter().enumerate() {
if let FoTerm::App(symbol, args) = *term
&& closed[i]
{
names.clear();
names.extend(fo.list(args).iter().map(|a| match arena[a.index()] {
NONE => Name::Past,
id => Name::Ground(id),
}));
if let Name::Ground(id) = ground.apply(symbol, &names) {
arena[i] = id;
}
}
}
Self {
occurrences,
base: fo.terms.len() as u32,
spans: Vec::new(),
frames: Vec::new(),
vars: Vec::new(),
eigens: 0,
trail: Vec::new(),
introduced: Vec::new(),
answers: Vec::new(),
choices: Choices::default(),
witness_depth: options.witness_depth,
instances: options.instances,
cut: None,
closed: closed.into(),
depth: depth.into(),
marks: Vec::new(),
stamp: 0,
steps: AtomicU64::new(0),
unifications: 0,
bindings: 0,
charged: 0,
pairs: Vec::new(),
met: HashSet::default(),
walk: Vec::new(),
depths: HashMap::default(),
key: KeyScratch::default(),
ground,
arena: arena.into(),
named: Vec::new(),
naming: Vec::new(),
names: Vec::new(),
}
}
#[cfg(feature = "parallel")]
fn fork(&self) -> Self {
Self {
occurrences: self.occurrences,
base: self.base,
spans: self.spans.clone(),
frames: self.frames.clone(),
vars: self.vars.clone(),
eigens: self.eigens,
trail: self.trail.clone(),
introduced: self.introduced.clone(),
answers: Vec::new(),
choices: Choices::default(),
witness_depth: self.witness_depth,
instances: self.instances,
cut: None,
closed: Arc::clone(&self.closed),
depth: Arc::clone(&self.depth),
marks: Vec::new(),
stamp: 0,
steps: AtomicU64::new(0),
unifications: 0,
bindings: 0,
charged: 0,
pairs: Vec::new(),
met: HashSet::default(),
walk: Vec::new(),
depths: HashMap::default(),
key: KeyScratch::default(),
ground: self.ground.clone(),
arena: Arc::clone(&self.arena),
named: self.named.clone(),
naming: Vec::new(),
names: Vec::new(),
}
}
#[cfg(feature = "parallel")]
fn share(&mut self) {
if let Grounds::Own(table) = &mut self.ground {
let table = std::mem::take(table);
self.ground = Grounds::Shared(Arc::new(SharedGrounds {
slots: std::sync::atomic::AtomicUsize::new(table.capacity()),
table: std::sync::Mutex::new(table),
}));
}
}
#[cfg(feature = "parallel")]
fn divides(&self) -> bool {
self.answers.is_empty()
}
#[cfg(feature = "parallel")]
fn adopt(&mut self, worker: Self) {
let (unifications, bindings, cut, charged) =
(self.unifications, self.bindings, self.cut, self.charged);
let steps = *self.steps.get_mut();
*self = Self {
unifications,
bindings,
cut,
charged,
steps: AtomicU64::new(steps),
..worker
};
}
#[cfg(feature = "parallel")]
fn cut_by(&mut self, reason: Reason) {
self.cut.get_or_insert(reason);
}
fn root(&self, o: OccId) -> FMember {
FMember(o.get())
}
fn occurrence(&self, m: FMember) -> OccId {
self.instance(m).0
}
fn child(&self, m: FMember, child: OccId) -> FMember {
FMember(m.0 + (child.get() - self.occurrence(m).get()))
}
fn dual_in(&self, forest: &Forest, literal: FMember, within: &Set) -> Option<FMember> {
let o = self.occurrence(literal);
let (atom, sign) = (forest.atom(o)?, forest.sign(o)?);
within.iter().find(|&d| {
let d = self.occurrence(d);
forest.atom(d) == Some(atom) && forest.sign(d) == Some(!sign)
})
}
fn dual_from(
&self,
forest: &Forest,
literal: FMember,
rest: &Members,
_cursors: &mut Cursors,
) -> Option<FMember> {
let o = self.occurrence(literal);
let (atom, sign) = (forest.atom(o)?, forest.sign(o)?);
rest.iter().find(|&d| {
let d = self.occurrence(d);
forest.atom(d) == Some(atom) && forest.sign(d) == Some(!sign)
})
}
fn mark_literals(&mut self, forest: &Forest, members: &[FMember], scratch: &mut Charged) {
if self.marks.is_empty() {
let fo = &forest.sequent().fo;
let keys = 2 * fo.symbols.len().max(forest.sequent().atom_names().len());
scratch.charge(keys * size_of::<u64>());
self.marks = vec![0; keys];
}
self.stamp += 1;
for &m in members {
if let Some(key) = Self::key(forest, self.occurrence(m), false) {
self.marks[key] = self.stamp;
}
}
}
fn duals(&self, _: &Forest, _: FMember) -> Option<usize> {
None
}
fn marked(&self, _: usize) -> Option<FMember> {
None
}
fn first_lookup(&mut self, _: usize) -> bool {
false
}
fn meets(&self, forest: &Forest, formula: FMember) -> bool {
forest
.subtree(self.occurrence(formula))
.filter_map(|l| Self::key(forest, l, true))
.any(|key| self.marks[key] == self.stamp)
}
fn class(&self, classes: &Classes, m: FMember) -> FMember {
if m.0 < self.occurrences {
FMember(classes.of(OccId::new(m.0)).get())
} else {
m
}
}
fn same(&self, classes: &Classes, x: FMember, y: FMember) -> bool {
if x.0 < self.occurrences && y.0 < self.occurrences {
classes.same(OccId::new(x.0), OccId::new(y.0))
} else {
x == y
}
}
fn memoizes(&self, _: &Set, _: &Members) -> bool {
false
}
fn word_lists(pools: &mut Pools<Self>) -> &mut Vec<Pooled<OccId>> {
&mut pools.words
}
fn listed(_: &[OccId]) -> Option<&[FMember]> {
None
}
fn mark(&self) -> Mark {
Mark {
spans: self.spans.len(),
frames: self.frames.len(),
vars: self.vars.len(),
eigens: self.eigens,
trail: self.trail.len(),
introduced: self.introduced.len(),
}
}
fn undo(&mut self, mark: Mark) {
while self.trail.len() > mark.trail {
match self.trail.pop().expect("longer than the mark") {
Undone::Bound(v) => {
if let Var::Meta { binding, .. } = &mut self.vars[v as usize] {
*binding = None;
}
}
Undone::Lowered(v, old) => {
if let Var::Meta { level, .. } = &mut self.vars[v as usize] {
*level = old;
}
}
Undone::Named(v) => self.named[v as usize] = Named::Unknown,
}
}
self.spans.truncate(mark.spans);
self.frames.truncate(mark.frames);
self.vars.truncate(mark.vars);
self.named.truncate(mark.vars);
self.eigens = mark.eigens;
self.introduced.truncate(mark.introduced);
}
fn begin_level(&mut self) {
self.cut = None;
}
fn cut(&self) -> Option<Reason> {
self.cut
}
fn forall(&mut self, forest: &Forest, binder: FMember) -> Result<Option<FMember>, Reason> {
if self.full() {
return Ok(None);
}
let number = self.eigens;
let term = self.push_var(Var::Eigen(number))?;
self.eigens += 1;
self.introduced.push(Eigen::new(number));
self.open(forest, binder, term).map(Some)
}
fn introduced(&mut self) -> Eigen {
self.introduced
.pop()
.expect("an eigenvariable per `∀` step")
}
fn exists(
&mut self,
forest: &Forest,
binder: FMember,
) -> Result<Option<(FMember, FoTermId)>, Reason> {
if self.full() {
return Ok(None);
}
let term = self.push_var(Var::Meta {
binding: None,
level: self.eigens,
})?;
let body = self.open(forest, binder, term)?;
Ok(Some((body, FoTermId::new(term.id))))
}
fn opposite(&self, forest: &Forest, p: FMember, q: FMember) -> bool {
let (p, q) = (self.occurrence(p), self.occurrence(q));
let (Some(a), Some(s), Some(b), Some(t)) = (
forest.atom(p),
forest.sign(p),
forest.atom(q),
forest.sign(q),
) else {
return false;
};
if s == t {
return false;
}
let fo = &forest.sequent().fo;
match (fo.atoms.get(a.index()), fo.atoms.get(b.index())) {
(Some(&(x, _)), Some(&(y, _))) => x == y,
_ => a == b,
}
}
fn unify(&mut self, forest: &Forest, p: FMember, q: FMember) -> Unified {
self.unifications += 1;
let fo = &forest.sequent().fo;
let ((o, f), (r, g)) = (self.instance(p), self.instance(q));
let (Some(a), Some(b)) = (forest.atom(o), forest.atom(r)) else {
return Unified::No;
};
if let (Some(&(_, xs)), Some(&(_, ys))) = (fo.atoms.get(a.index()), fo.atoms.get(b.index()))
{
self.pairs.clear();
self.pairs
.extend(fo.list(xs).iter().zip(fo.list(ys)).map(|(&x, &y)| {
(
TRef {
id: x.get(),
frame: f,
},
TRef {
id: y.get(),
frame: g,
},
)
}));
let found = self.unify_pairs(fo);
if found != Unified::Yes {
return found;
}
} else if a != b {
return Unified::No;
}
if self.choices.replaying() || self.passes(fo) {
Unified::Yes
} else {
Unified::No
}
}
fn open_answers(
&mut self,
forest: &Forest,
members: &mut dyn Iterator<Item = FMember>,
) -> bool {
let fo = &forest.sequent().fo;
let mut metas = Vec::new();
let mut frames = HashSet::default();
let mut met = HashSet::default();
let mut walk = Vec::new();
for m in members {
let mut frame = self.instance(m).1;
while frame != NONE && frames.insert(frame) {
let (parent, term) = self.frames[frame as usize];
walk.push(term);
frame = parent;
}
}
while let Some(t) = walk.pop() {
self.step();
let t = self.deref(fo, t);
if !met.insert(t) {
continue;
}
match self.var(t) {
Some(v) => {
if matches!(self.vars[v as usize], Var::Meta { .. }) {
metas.push(v);
}
}
None if !self.closed[t.id as usize] => {
walk.extend(Self::app(fo, t).1.iter().map(|&a| TRef {
id: a.get(),
frame: t.frame,
}));
}
None => {}
}
}
if metas.is_empty() {
return false;
}
metas.sort_unstable();
self.answers.push(Answers {
metas,
patterns: Vec::new(),
first: true,
});
true
}
fn searching_first(&mut self, first: bool) {
self.answers.last_mut().expect("answers open").first = first;
}
fn record(&mut self, forest: &Forest) -> usize {
let fo = &forest.sequent().fo;
let answers = self.answers.last().expect("answers open");
let pattern = self.pattern(fo, &answers.metas);
let bytes = size_of::<Pattern>()
+ pattern.nodes.len() * size_of::<Pat>()
+ (pattern.kids.len() + pattern.roots.len() + pattern.levels.len()) * size_of::<u32>();
self.answers
.last_mut()
.expect("answers open")
.patterns
.push(pattern);
bytes
}
fn exhausted(&mut self, forest: &Forest) -> bool {
let fo = &forest.sequent().fo;
let answers = self.answers.last().expect("answers open");
answers
.patterns
.iter()
.any(|p| self.instance_of(fo, &answers.metas, p))
}
fn close_answers(&mut self) {
self.answers.pop();
}
fn keys(
&mut self,
forest: &Forest,
theta: &Set,
gamma: &Members,
own: &mut Vec<OccId>,
canonical: &mut Vec<OccId>,
) -> bool {
self.write_keys(forest, theta, gamma, own, canonical)
}
fn excluding(&self) -> bool {
self.answers
.iter()
.any(|answers| answers.first && !answers.patterns.is_empty())
}
fn take_steps(&mut self) -> u64 {
std::mem::take(self.steps.get_mut())
}
fn counts(&self) -> (u64, u64) {
(self.unifications, self.bindings)
}
fn held(&mut self) -> (usize, usize) {
let entries = |slots: usize, size: usize| slots * (size + 1);
let held = bytes_of(&self.spans)
+ bytes_of(&self.frames)
+ bytes_of(&self.vars)
+ bytes_of(&self.trail)
+ bytes_of(&self.introduced)
+ bytes_of(&self.pairs)
+ bytes_of(&self.walk)
+ self.key.bytes()
+ entries(self.met.capacity(), size_of::<(TRef, TRef)>())
+ entries(self.depths.capacity(), size_of::<(TRef, u32)>())
+ entries(self.ground.capacity(), size_of::<((Head, u32), u32)>())
+ bytes_of(&self.named)
+ bytes_of(&self.naming)
+ bytes_of(&self.names)
+ self.choices.bytes();
(std::mem::replace(&mut self.charged, held), held)
}
fn close(&self, forest: &Forest, nodes: &mut [Node]) -> Result<Instances, Reason> {
let closing = RefCell::new(Closing {
framed: self,
fo: &forest.sequent().fo,
table: Instances::new(forest),
terms: HashMap::default(),
frames: HashMap::default(),
members: HashMap::default(),
fresh: HashMap::default(),
});
for node in nodes.iter_mut() {
let renamed = node.renamed(|m| -> Result<Member, Reason> {
Ok(closing.borrow_mut().member(FMember(m.get())))
})?;
*node = match renamed {
Node::Exists(m, w, p) => Node::Exists(
m,
closing.borrow_mut().term(TRef {
id: w.get(),
frame: NONE,
}),
p,
),
node => node,
};
}
Ok(closing.into_inner().table)
}
fn choices(&mut self) -> &mut Choices {
&mut self.choices
}
}
struct Closing<'a> {
framed: &'a Framed,
fo: &'a FirstOrder,
table: Instances,
terms: HashMap<TRef, FoTermId>,
frames: HashMap<u32, FrameId>,
members: HashMap<u32, Member>,
fresh: HashMap<u32, Eigen>,
}
impl Closing<'_> {
fn term(&mut self, t: TRef) -> FoTermId {
let framed = self.framed;
let mut walk = vec![(t, false)];
while let Some((u, expanded)) = walk.pop() {
let u = framed.deref(self.fo, u);
if !expanded && self.terms.contains_key(&u) {
continue;
}
let id = if let Some(v) = framed.var(u) {
let eigen = match framed.vars[v as usize] {
Var::Eigen(number) => Eigen::new(number),
Var::Meta { .. } => {
let next = framed.eigens.saturating_add(self.fresh.len() as u32);
*self.fresh.entry(v).or_insert(Eigen::new(next))
}
};
self.table.eigen(eigen)
} else if framed.closed[u.id as usize] {
FoTermId::new(u.id)
} else {
let (symbol, args) = Framed::app(self.fo, u);
let child = |a: &FoTermId| TRef {
id: a.get(),
frame: u.frame,
};
if !expanded {
walk.push((u, true));
walk.extend(args.iter().map(|a| (child(a), false)));
continue;
}
let ids: Vec<FoTermId> = args
.iter()
.map(|a| self.terms[&framed.deref(self.fo, child(a))])
.collect();
self.table.apply(symbol, &ids)
};
self.terms.insert(u, id);
}
self.terms[&framed.deref(self.fo, t)]
}
fn frame(&mut self, frame: u32) -> FrameId {
let mut chain = Vec::new();
let mut f = frame;
while f != NONE && !self.frames.contains_key(&f) {
chain.push(f);
f = self.framed.frames[f as usize].0;
}
for &f in chain.iter().rev() {
let (parent, term) = self.framed.frames[f as usize];
let parent = (parent != NONE).then(|| self.frames[&parent]);
let term = self.term(term);
let id = self.table.frame(parent, term);
self.frames.insert(f, id);
}
self.frames[&frame]
}
fn member(&mut self, m: FMember) -> Member {
if m.0 < self.framed.occurrences {
return Member::new(m.0);
}
if let Some(&member) = self.members.get(&m.0) {
return member;
}
let (o, frame) = self.framed.instance(m);
let frame = self.frame(frame);
let member = self.table.member(o, frame);
self.members.insert(m.0, member);
member
}
}
#[derive(Clone, Debug, Default)]
pub(super) struct Members(Vec<FMember>);
impl Linear<FMember> for Members {
fn empty(_: &Forest) -> Self {
Self(Vec::new())
}
fn insert(&mut self, m: FMember) {
let at = self.0.partition_point(|&x| x <= m);
self.0.insert(at, m);
}
fn remove(&mut self, m: FMember) {
let at = self.0.binary_search(&m).expect("a member");
self.0.remove(at);
}
fn contains(&self, m: FMember) -> bool {
self.0.binary_search(&m).is_ok()
}
fn clear(&mut self) {
self.0.clear();
}
fn copy_from(&mut self, other: &Self) {
self.0.clone_from(&other.0);
}
fn is_empty(&self) -> bool {
self.0.is_empty()
}
fn iter(&self) -> impl Iterator<Item = FMember> + '_ {
self.0.iter().copied()
}
fn list_into(&self, list: &mut Vec<FMember>) {
list.extend_from_slice(&self.0);
}
fn ground(&self) -> &Context {
unreachable!("a first-order search keys no sequent by occurrence")
}
}
#[derive(Clone, Debug)]
pub(super) struct Set(Vec<FMember>, OccSet);
impl Unrestricted<FMember> for Set {
fn empty(_: &Forest) -> Self {
Self(Vec::new(), OccSet::empty(0))
}
fn insert(&mut self, m: FMember) {
if let Err(at) = self.0.binary_search(&m) {
self.0.insert(at, m);
}
}
fn contains(&self, m: FMember) -> bool {
self.0.binary_search(&m).is_ok()
}
fn clear(&mut self) {
self.0.clear();
}
fn copy_from(&mut self, other: &Self) {
self.0.clone_from(&other.0);
}
fn iter(&self) -> impl Iterator<Item = FMember> + '_ {
self.0.iter().copied()
}
fn ground(&self) -> &OccSet {
&self.1
}
}