use super::terms::{TermId, Terms};
use crate::Error;
use crate::hash::HashMap;
use crate::limits::{Refusal, Space};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(u32);
impl NodeId {
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct ScopeId(u32);
impl ScopeId {
pub const ROOT: Self = Self(0);
#[cfg(all(feature = "interactive", feature = "parse"))]
pub(crate) const fn new(index: u32) -> Self {
Self(index)
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum Step<'a> {
Rule(&'a str),
Hypothesis,
Open,
}
#[derive(Clone, Copy, Debug)]
#[non_exhaustive]
pub struct Node<'a> {
pub sequent: &'a [Vec<TermId>],
pub step: Step<'a>,
pub premises: &'a [u32],
pub positions: &'a [u32],
pub scope: u32,
}
impl<'a> Node<'a> {
pub const fn new(sequent: &'a [Vec<TermId>], step: Step<'a>) -> Self {
Self {
sequent,
step,
premises: &[],
positions: &[],
scope: 0,
}
}
#[must_use]
pub const fn premises(mut self, premises: &'a [u32]) -> Self {
self.premises = premises;
self
}
#[must_use]
pub const fn positions(mut self, positions: &'a [u32]) -> Self {
self.positions = positions;
self
}
#[must_use]
pub const fn scope(mut self, scope: ScopeId) -> Self {
self.scope = scope.0;
self
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Kind {
Rule(u32),
Hypothesis,
Open,
}
#[derive(Clone, Copy, Debug)]
pub(super) struct Entry {
pub(super) kind: Kind,
pub(super) scope: u32,
premises_end: u32,
positions_end: u32,
}
#[derive(Clone, Debug)]
pub struct Derivation {
calculus: String,
zones: usize,
terms: Terms,
pub(super) rules: Vec<String>,
rule_ids: HashMap<String, u32>,
pub(super) scopes: Vec<u32>,
members: Vec<TermId>,
ends: Vec<u32>,
premises: Vec<NodeId>,
positions: Vec<u32>,
pub(super) nodes: Vec<Entry>,
}
#[derive(Clone, Copy, Debug)]
pub struct NodeRef<'a> {
derivation: &'a Derivation,
index: usize,
}
impl<'a> NodeRef<'a> {
pub const fn id(self) -> NodeId {
NodeId(self.index as u32)
}
pub fn zone(self, zone: usize) -> &'a [TermId] {
let derivation = self.derivation;
assert!(zone < derivation.zones, "no such zone");
let at = self.index * derivation.zones + zone;
let start = at
.checked_sub(1)
.map_or(0, |before| derivation.ends[before]);
&derivation.members[start as usize..derivation.ends[at] as usize]
}
pub fn step(self) -> Step<'a> {
match self.derivation.nodes[self.index].kind {
Kind::Rule(rule) => Step::Rule(&self.derivation.rules[rule as usize]),
Kind::Hypothesis => Step::Hypothesis,
Kind::Open => Step::Open,
}
}
pub fn premises(self) -> &'a [NodeId] {
let nodes = &self.derivation.nodes;
let start = self
.index
.checked_sub(1)
.map_or(0, |before| nodes[before].premises_end);
&self.derivation.premises[start as usize..nodes[self.index].premises_end as usize]
}
pub fn positions(self) -> &'a [u32] {
let nodes = &self.derivation.nodes;
let start = self
.index
.checked_sub(1)
.map_or(0, |before| nodes[before].positions_end);
&self.derivation.positions[start as usize..nodes[self.index].positions_end as usize]
}
pub fn scope(self) -> ScopeId {
ScopeId(self.derivation.nodes[self.index].scope)
}
}
impl Derivation {
pub fn new(calculus: &str, zones: usize) -> Self {
Self {
calculus: calculus.to_owned(),
zones,
terms: Terms::default(),
rules: Vec::new(),
rule_ids: HashMap::default(),
scopes: vec![0],
members: Vec::new(),
ends: Vec::new(),
premises: Vec::new(),
positions: Vec::new(),
nodes: Vec::new(),
}
}
pub fn calculus(&self) -> &str {
&self.calculus
}
pub const fn zones(&self) -> usize {
self.zones
}
pub const fn terms(&self) -> &Terms {
&self.terms
}
#[cfg(all(feature = "interactive", feature = "parse"))]
pub(crate) fn adopt_terms(&mut self, terms: Terms) {
debug_assert!(self.terms.is_empty(), "the derivation has terms of its own");
self.terms = terms;
}
pub const fn terms_mut(&mut self) -> &mut Terms {
&mut self.terms
}
pub fn len(&self) -> usize {
self.nodes.len()
}
pub fn is_empty(&self) -> bool {
self.nodes.is_empty()
}
pub fn node(&self, id: NodeId) -> NodeRef<'_> {
assert!(id.index() < self.nodes.len(), "no such node");
NodeRef {
derivation: self,
index: id.index(),
}
}
pub(super) fn at(&self, index: usize) -> NodeRef<'_> {
debug_assert!(index < self.nodes.len(), "no such node");
NodeRef {
derivation: self,
index,
}
}
pub fn nodes(&self) -> impl ExactSizeIterator<Item = NodeRef<'_>> {
(0..self.nodes.len()).map(|index| NodeRef {
derivation: self,
index,
})
}
pub fn root(&self) -> Option<NodeRef<'_>> {
self.len().checked_sub(1).map(|index| self.at(index))
}
pub fn parent(&self, scope: ScopeId) -> Option<ScopeId> {
(scope != ScopeId::ROOT).then(|| ScopeId(self.scopes[scope.index()]))
}
pub fn hypotheses(&self, scope: ScopeId) -> impl Iterator<Item = NodeRef<'_>> {
self.nodes()
.filter(move |node| node.step() == Step::Hypothesis && node.scope() == scope)
}
pub fn assumptions(&self) -> impl Iterator<Item = NodeRef<'_>> {
self.hypotheses(ScopeId::ROOT)
}
pub fn open(&self) -> impl Iterator<Item = NodeRef<'_>> {
self.nodes().filter(|node| node.step() == Step::Open)
}
pub(crate) fn scope_parents(&self) -> &[u32] {
&self.scopes
}
pub fn scope(&mut self, parent: u32) -> Result<ScopeId, Error> {
if parent as usize >= self.scopes.len() {
return Err(Error::IndexOutOfBounds {
space: Space::Scope,
index: parent as usize,
len: self.scopes.len(),
});
}
let id = fits(self.scopes.len(), Space::Scope)?;
self.scopes.push(parent);
Ok(ScopeId(id))
}
pub fn push(&mut self, node: Node<'_>) -> Result<NodeId, Error> {
if node.sequent.len() != self.zones {
return Err(Error::Zones {
found: node.sequent.len(),
zones: self.zones,
});
}
let outside = |space, index: usize, len| Error::IndexOutOfBounds { space, index, len };
for member in node.sequent.iter().flatten() {
if member.index() >= self.terms.len() {
return Err(outside(Space::Term, member.index(), self.terms.len()));
}
}
if let Some(&premise) = node.premises.iter().find(|&&p| p as usize >= self.len()) {
return Err(outside(Space::Node, premise as usize, self.len()));
}
if node.scope as usize >= self.scopes.len() {
return Err(outside(
Space::Scope,
node.scope as usize,
self.scopes.len(),
));
}
let id = fits(self.nodes.len(), Space::Node)?;
let members: usize = node.sequent.iter().map(Vec::len).sum();
fits(self.members.len().saturating_add(members), Space::Member)?;
let premises_end = fits(self.premises.len() + node.premises.len(), Space::Node)?;
let positions_end = fits(self.positions.len() + node.positions.len(), Space::Member)?;
let kind = match node.step {
Step::Hypothesis => Kind::Hypothesis,
Step::Open => Kind::Open,
Step::Rule(name) => Kind::Rule(match self.rule_ids.get(name) {
Some(&index) => index,
None => {
let index = self.rules.len() as u32;
self.rules.push(name.to_owned());
self.rule_ids.insert(name.to_owned(), index);
index
}
}),
};
for zone in node.sequent {
self.members.extend_from_slice(zone);
self.ends.push(self.members.len() as u32);
}
self.premises
.extend(node.premises.iter().map(|&p| NodeId(p)));
self.positions.extend_from_slice(node.positions);
self.nodes.push(Entry {
kind,
scope: node.scope,
premises_end,
positions_end,
});
Ok(NodeId(id))
}
}
fn fits(count: usize, what: Space) -> Result<u32, Error> {
u32::try_from(count).map_err(|_| {
Error::Refused(Refusal::Index {
what,
count: count as u64,
most: u64::from(u32::MAX),
})
})
}