use super::error::Fault;
use crate::hash::{HashMap, HashSet};
use crate::linear::occurrences::instances::{Numbering, Terms, binders};
use crate::linear::occurrences::{Forest, FrameId, Instances, Member, OccId};
use crate::linear::proofs::{Node, NodeId, Proof};
use crate::linear::sequents::{Eigen, FoTerm, FoTermId};
pub(crate) trait Instancing {
const FRAMED: bool;
fn occ(&self, m: Member) -> OccId;
fn child(&self, m: Member, c: OccId) -> Member;
fn parent(&self, m: Member, p: OccId) -> Member;
fn dual_literals(&mut self, forest: &Forest, a: Member, b: Member) -> bool;
fn dual(&self, forest: &Forest, m: Member) -> Option<Member>;
fn fault(&self, node: NodeId) -> Option<Fault>;
fn body(&self, node: NodeId) -> Member;
fn bring(&self, node: Node, into: &mut Vec<Eigen>) -> u64;
fn introduces(&self, a: Eigen) -> bool;
fn frame_len(&self, m: Member) -> u64;
}
pub(crate) struct Ground;
impl Instancing for Ground {
const FRAMED: bool = false;
#[inline(always)]
fn occ(&self, m: Member) -> OccId {
m.occ()
}
#[inline(always)]
fn child(&self, _: Member, c: OccId) -> Member {
Member::from(c)
}
#[inline(always)]
fn parent(&self, _: Member, p: OccId) -> Member {
Member::from(p)
}
#[inline(always)]
fn dual_literals(&mut self, forest: &Forest, a: Member, b: Member) -> bool {
forest.dual_literals(a.occ(), b.occ())
}
#[inline(always)]
fn dual(&self, forest: &Forest, m: Member) -> Option<Member> {
forest.dual(m.occ()).map(Member::from)
}
#[inline(always)]
fn fault(&self, _: NodeId) -> Option<Fault> {
None
}
fn body(&self, _: NodeId) -> Member {
unreachable!("a binder's step on a forest without binders fails its kind")
}
fn bring(&self, _: Node, _: &mut Vec<Eigen>) -> u64 {
0
}
#[inline(always)]
fn frame_len(&self, _: Member) -> u64 {
0
}
fn introduces(&self, _: Eigen) -> bool {
false
}
}
#[derive(Debug, Default)]
struct Found {
fault: Option<Fault>,
body: Option<Member>,
}
pub(crate) struct Framed<'a> {
table: &'a Instances,
numbering: Numbering<'a>,
frames: HashMap<(Option<FrameId>, FoTermId), FrameId>,
members: HashMap<(OccId, FrameId), Member>,
found: HashMap<NodeId, Found>,
lengths: Vec<u64>,
introduced: HashSet<Eigen>,
}
impl<'a> Framed<'a> {
pub(crate) fn new(proof: &'a Proof, table: &'a Instances) -> Self {
let forest = proof.forest();
let terms = Terms {
fo: &forest.sequent().fo,
table,
};
let mut this = Self {
table,
numbering: Numbering::new(terms),
frames: table
.frames
.iter()
.zip(0..)
.map(|(&key, f)| (key, FrameId::new(f)))
.collect(),
members: table
.members
.iter()
.zip(0..)
.map(|(&key, n)| (key, Member::new(table.occurrences + n)))
.collect(),
found: HashMap::default(),
lengths: Vec::with_capacity(table.frames.len()),
introduced: HashSet::default(),
};
for &(parent, _) in &table.frames {
let length = parent.map_or(1, |p| this.lengths[p.index()].saturating_add(1));
this.lengths.push(length);
}
let eigen_terms: HashMap<Eigen, FoTermId> = table
.terms
.iter()
.zip(0..)
.filter_map(|(t, n)| match *t {
FoTerm::Eigen(a) => Some((a, FoTermId::new(table.base_terms + n))),
FoTerm::Bound(_) | FoTerm::App(..) | FoTerm::Meta(_) => None,
})
.collect();
let depth = binders(forest);
let mut introduced: HashMap<Eigen, NodeId> = HashMap::default();
for id in proof.ids().rev() {
let node = proof.node(id);
let mut found = Found::default();
let bare = node
.members()
.find(|m| m.index() < forest.len() && depth[m.index()] > 0);
if let Some(member) = bare {
found.fault = Some(Fault::Instance { member });
}
match node {
Node::Forall(m, a, _) if bare.is_none() => {
introduced
.entry(a)
.and_modify(|first| *first = (*first).min(id))
.or_insert(id);
let o = this.occ(m);
if forest.kind(o).is_binder() {
let term = eigen_terms[&a];
found.body = Some(this.pushed(m, o, term));
}
}
Node::Exists(m, w, _) if bare.is_none() => {
let o = this.occ(m);
if forest.kind(o).is_binder() {
found.body = Some(this.pushed(m, o, w));
}
}
_ => {}
}
if found.fault.is_some() || found.body.is_some() {
this.found.insert(id, found);
}
}
this.introduced = introduced.keys().copied().collect();
for id in proof.ids() {
if let Node::Forall(_, a, _) = proof.node(id)
&& introduced.get(&a).is_some_and(|&first| first != id)
{
let found = this.found.entry(id).or_default();
found.fault.get_or_insert(Fault::Reintroduced { eigen: a });
}
}
this
}
fn frame(&self, m: Member) -> Option<FrameId> {
self.table.instance(m).map(|(_, f)| f)
}
fn pushed(&self, m: Member, o: OccId, term: FoTermId) -> Member {
let frame = self.frames[&(self.frame(m), term)];
self.members[&(OccId::new(o.get() + 1), frame)]
}
}
impl Instancing for Framed<'_> {
const FRAMED: bool = true;
fn occ(&self, m: Member) -> OccId {
self.table.instance(m).map_or(m.occ(), |(o, _)| o)
}
fn child(&self, m: Member, c: OccId) -> Member {
match self.frame(m) {
None => Member::from(c),
Some(frame) => self.members[&(c, frame)],
}
}
fn parent(&self, m: Member, p: OccId) -> Member {
match self.frame(m) {
None => Member::from(p),
Some(frame) => self
.members
.get(&(p, frame))
.copied()
.unwrap_or(Member::from(p)),
}
}
fn dual_literals(&mut self, forest: &Forest, a: Member, b: Member) -> bool {
let (x, y) = (self.occ(a), self.occ(b));
let (Some(sx), Some(sy)) = (forest.sign(x), forest.sign(y)) else {
return false;
};
if sx == sy {
return false;
}
let sequent = forest.sequent();
let atoms = (forest.atom(x), forest.atom(y));
let (Some(ax), Some(ay)) = atoms else {
return false;
};
let predicates = (sequent.atom_predicate(ax), sequent.atom_predicate(ay));
let (Some((px, lx)), Some((py, ly))) = predicates else {
return ax == ay;
};
if px != py {
return false;
}
let mut args = |m: Member, list| {
let frame: Vec<u64> = self.frame(m).map_or_else(Vec::new, |f| {
self.table
.frame_terms(f)
.into_iter()
.map(|t| self.numbering.number(t))
.collect()
});
self.numbering.instance(list, &frame)
};
args(a, lx) == args(b, ly)
}
fn dual(&self, forest: &Forest, m: Member) -> Option<Member> {
let dual = forest.dual(self.occ(m))?;
Some(self.child(m, dual))
}
fn fault(&self, node: NodeId) -> Option<Fault> {
self.found.get(&node).and_then(|f| f.fault.clone())
}
fn body(&self, node: NodeId) -> Member {
self.found[&node]
.body
.expect("the kind test passed: the step acts on a binder")
}
fn frame_len(&self, m: Member) -> u64 {
self.frame(m).map_or(0, |f| self.lengths[f.index()])
}
fn introduces(&self, a: Eigen) -> bool {
self.introduced.contains(&a)
}
fn bring(&self, node: Node, into: &mut Vec<Eigen>) -> u64 {
let mut stack = match node {
Node::Exists(_, w, _) => vec![w],
Node::Cut(m, ..) => match self.frame(m) {
Some(frame) => self.table.frame_terms(frame),
None => return 0,
},
_ => return 0,
};
let mut units = stack.len() as u64;
let terms = self.numbering.terms();
let mut seen = HashSet::default();
while let Some(t) = stack.pop() {
if !seen.insert(t) {
continue;
}
units = units.saturating_add(1);
match terms.term(t) {
FoTerm::Eigen(a) => into.push(a),
FoTerm::App(_, args) => stack.extend_from_slice(terms.list(args)),
FoTerm::Bound(_) | FoTerm::Meta(_) => {}
}
}
units
}
}