use super::TermId;
#[cfg(any(test, feature = "parse", feature = "serialize"))]
use super::name;
#[cfg(any(test, feature = "parse", feature = "serialize"))]
use crate::Error;
use crate::hash::HashMap;
use std::fmt::{Result as FmtResult, Write};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Symbol(u32);
impl Symbol {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct FoTermId(u32);
impl FoTermId {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct Args(u32);
impl Args {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn get(self) -> u32 {
self.0
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize, serde::Deserialize),
serde(transparent)
)]
pub struct Eigen(u32);
impl Eigen {
pub const fn new(number: u32) -> Self {
Self(number)
}
pub const fn get(self) -> u32 {
self.0
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum FoTerm {
Bound(u32),
App(Symbol, Args),
Eigen(Eigen),
Meta(u32),
}
const _: () = assert!(size_of::<FoTerm>() == 12);
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct FirstOrder {
pub(crate) symbols: Vec<(String, u32)>,
pub(crate) terms: Vec<FoTerm>,
pub(crate) args: Vec<FoTermId>,
pub(crate) lists: Vec<(u32, u32)>,
pub(crate) atoms: Vec<(Symbol, Args)>,
pub(crate) binders: Vec<(TermId, String)>,
}
impl FirstOrder {
pub(crate) const fn new() -> Self {
Self {
symbols: Vec::new(),
terms: Vec::new(),
args: Vec::new(),
lists: Vec::new(),
atoms: Vec::new(),
binders: Vec::new(),
}
}
pub(crate) fn is_empty(&self) -> bool {
self.atoms.is_empty() && self.binders.is_empty()
}
#[cfg(feature = "interactive")]
pub(crate) fn trim(&mut self, keep: usize, all_symbols: bool) {
let nullary = self
.atoms
.iter()
.all(|&(_, args)| self.list(args).is_empty());
if nullary && self.binders.is_empty() {
*self = Self::new();
return;
}
let (mut terms, mut lists, mut symbols) = (keep.min(self.terms.len()), 0, 0);
for &(p, args) in &self.atoms {
symbols = symbols.max(p.index() + 1);
lists = lists.max(args.index() + 1);
for &t in self.list(args) {
terms = terms.max(t.index() + 1);
}
}
for term in &self.terms[..terms] {
if let FoTerm::App(f, args) = *term {
symbols = symbols.max(f.index() + 1);
lists = lists.max(args.index() + 1);
}
}
self.terms.truncate(terms);
self.lists.truncate(lists);
let args = self
.lists
.iter()
.map(|&(start, len)| (start + len) as usize);
let args = args.max().unwrap_or(0);
self.args.truncate(args);
if !all_symbols || self.binders.is_empty() {
self.symbols.truncate(symbols);
}
}
pub(crate) fn list(&self, args: Args) -> &[FoTermId] {
let (start, len) = self.lists[args.index()];
&self.args[start as usize..(start + len) as usize]
}
pub(crate) fn binder_name(&self, term: TermId) -> Option<&str> {
self.binders
.binary_search_by_key(&term, |&(t, _)| t)
.ok()
.map(|i| self.binders[i].1.as_str())
}
pub(crate) fn write<W: Write + ?Sized>(
&self,
out: &mut W,
term: FoTermId,
symbol: &mut impl FnMut(&mut W, &str) -> FmtResult,
bound: &mut impl FnMut(&mut W, u32) -> FmtResult,
) -> FmtResult {
let mut open: Vec<(Args, u32)> = Vec::new();
let mut next = Some(term);
loop {
if let Some(t) = next.take() {
match self.terms[t.index()] {
FoTerm::Bound(index) => bound(out, index)?,
FoTerm::App(f, args) => {
symbol(out, &self.symbols[f.index()].0)?;
if self.lists[args.index()].1 > 0 {
out.write_char('(')?;
open.push((args, 0));
}
}
FoTerm::Eigen(_) | FoTerm::Meta(_) => {
unreachable!("a sequent's arena holds no eigenvariable or metavariable")
}
}
}
let Some(&mut (args, ref mut i)) = open.last_mut() else {
return Ok(());
};
let list = self.list(args);
if (*i as usize) < list.len() {
if *i > 0 {
out.write_str(", ")?;
}
next = Some(list[*i as usize]);
*i += 1;
} else {
out.write_char(')')?;
open.pop();
}
}
}
pub(crate) fn write_atom<W: Write + ?Sized>(
&self,
out: &mut W,
symbol: Symbol,
args: Args,
) -> FmtResult {
out.write_str(&self.symbols[symbol.index()].0)?;
if self.lists[args.index()].1 == 0 {
return Ok(());
}
out.write_char('(')?;
for (i, &t) in self.list(args).iter().enumerate() {
if i > 0 {
out.write_str(", ")?;
}
self.write(
out,
t,
&mut |out, name| out.write_str(name),
&mut |out, index| write!(out, "#{index}"),
)?;
}
out.write_char(')')
}
pub(crate) fn atom_key(&self, symbol: Symbol, args: Args) -> String {
let mut key = String::new();
self.write_atom(&mut key, symbol, args)
.expect("writing into a string cannot fail");
key
}
pub(crate) fn unfolded(&self) -> Vec<u64> {
let mut unfolded = vec![0u64; self.terms.len()];
for (n, term) in self.terms.iter().enumerate() {
unfolded[n] = match *term {
FoTerm::Bound(_) | FoTerm::Eigen(_) | FoTerm::Meta(_) => 1,
FoTerm::App(_, args) => self
.list(args)
.iter()
.fold(1u64, |sum, t| sum.saturating_add(unfolded[t.index()])),
};
}
unfolded
}
pub(crate) fn loose(&self) -> Vec<u32> {
let mut loose = vec![0u32; self.terms.len()];
for (n, term) in self.terms.iter().enumerate() {
loose[n] = match *term {
FoTerm::Bound(index) => index.saturating_add(1),
FoTerm::Eigen(_) | FoTerm::Meta(_) => 0,
FoTerm::App(_, args) => self
.list(args)
.iter()
.map(|t| loose[t.index()])
.max()
.unwrap_or(0),
};
}
loose
}
#[cfg(any(test, feature = "parse", feature = "serialize"))]
pub(crate) fn check(&self, atom_count: usize) -> Result<(), Error> {
use crate::limits::Space;
if !self.atoms.is_empty() && self.atoms.len() != atom_count {
return Err(Error::Predicates {
predicates: self.atoms.len(),
atoms: atom_count,
});
}
for (name, _) in &self.symbols {
name::check(name)?;
}
let mut names = std::collections::BTreeSet::<&str>::new();
for (name, _) in &self.symbols {
if !names.insert(name.as_str()) {
return Err(Error::Symbol {
name: name.clone(),
fault: SymbolFault::Repeated,
});
}
}
let symbols = self.symbols.len();
if let Some(t) = self.args.iter().find(|t| t.index() >= self.terms.len()) {
return Err(Error::IndexOutOfBounds {
space: Space::Term,
index: t.index(),
len: self.terms.len(),
});
}
for (n, &(start, len)) in self.lists.iter().enumerate() {
let end = (start as usize).saturating_add(len as usize);
if end > self.args.len() {
return Err(Error::IndexOutOfBounds {
space: Space::Term,
index: n,
len: self.args.len(),
});
}
}
let mut role = vec![None; symbols];
let mut arity = |symbol: Symbol, args: Args, predicate: bool| -> Result<(), Error> {
if symbol.index() >= symbols {
return Err(Error::IndexOutOfBounds {
space: Space::Symbol,
index: symbol.index(),
len: symbols,
});
}
if args.index() >= self.lists.len() {
return Err(Error::IndexOutOfBounds {
space: Space::Term,
index: args.index(),
len: self.lists.len(),
});
}
let (name, declared) = &self.symbols[symbol.index()];
if self.lists[args.index()].1 != *declared {
return Err(Error::Symbol {
name: name.clone(),
fault: SymbolFault::Arity {
declared: *declared,
found: self.lists[args.index()].1,
},
});
}
let slot = &mut role[symbol.index()];
if slot.is_some_and(|p| p != predicate) {
return Err(Error::Symbol {
name: name.clone(),
fault: SymbolFault::Role,
});
}
*slot = Some(predicate);
Ok(())
};
for (n, term) in self.terms.iter().enumerate() {
if let FoTerm::App(f, args) = *term {
arity(f, args, false)?;
for t in self.list(args) {
if t.index() >= n {
return Err(Error::NotTopological {
space: Space::Term,
index: t.index(),
parent: n,
});
}
}
}
}
for &(p, args) in &self.atoms {
arity(p, args, true)?;
}
if self.binders.windows(2).any(|w| w[0].0 >= w[1].0) {
return Err(Error::NotTopological {
space: Space::Term,
index: 0,
parent: 0,
});
}
for (_, name) in &self.binders {
name::check(name)?;
}
Ok(())
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, thiserror::Error)]
#[cfg_attr(
feature = "serialize",
derive(serde::Serialize),
serde(rename_all = "snake_case")
)]
pub enum SymbolFault {
#[error("is listed twice")]
Repeated,
#[error("takes {declared} arguments, not {found}")]
Arity {
declared: u32,
found: u32,
},
#[error("is a predicate and a function symbol at once")]
Role,
}
#[derive(Debug, Default)]
pub(crate) struct Interner {
pub(crate) tables: FirstOrder,
symbols: HashMap<String, Symbol>,
predicate: Vec<Option<bool>>,
terms: HashMap<FoTerm, FoTermId>,
lists: HashMap<Box<[FoTermId]>, Args>,
}
impl Interner {
pub(crate) fn new() -> Self {
Self::default()
}
pub(crate) fn symbol(
&mut self,
name: &str,
arity: u32,
predicate: bool,
) -> Result<Symbol, SymbolFault> {
let symbol = match self.symbols.get(name) {
Some(&symbol) => symbol,
None => {
let symbol = Symbol::new(self.tables.symbols.len() as u32);
self.tables.symbols.push((name.to_owned(), arity));
self.symbols.insert(name.to_owned(), symbol);
self.predicate.push(None);
symbol
}
};
let declared = self.tables.symbols[symbol.index()].1;
if declared != arity {
return Err(SymbolFault::Arity {
declared,
found: arity,
});
}
let slot = &mut self.predicate[symbol.index()];
if slot.is_some_and(|p| p != predicate) {
return Err(SymbolFault::Role);
}
*slot = Some(predicate);
Ok(symbol)
}
pub(crate) fn term(&mut self, term: FoTerm) -> FoTermId {
if let Some(&id) = self.terms.get(&term) {
return id;
}
let id = FoTermId::new(self.tables.terms.len() as u32);
self.tables.terms.push(term);
self.terms.insert(term, id);
id
}
pub(crate) fn list(&mut self, items: &[FoTermId]) -> Args {
if let Some(&args) = self.lists.get(items) {
return args;
}
let args = Args::new(self.tables.lists.len() as u32);
let start = self.tables.args.len() as u32;
self.tables.args.extend_from_slice(items);
self.tables.lists.push((start, items.len() as u32));
self.lists.insert(items.into(), args);
args
}
}