use crate::Error;
use crate::hash::{BuildHasher, HashMap};
use crate::limits::{Refusal, Space};
use crate::linear::sequents::name;
use std::hash::BuildHasher as _;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct TermId(u32);
impl TermId {
pub const fn new(index: u32) -> Self {
Self(index)
}
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum Term<'a> {
Atom {
name: &'a str,
sort: &'a str,
},
Apply {
connective: &'a str,
arguments: &'a [TermId],
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub(crate) enum Head {
Atom(u32),
Connective(u32),
}
#[derive(Clone, Copy, Debug)]
struct Entry {
head: Head,
start: u32,
len: u32,
}
const NONE: u32 = u32::MAX;
#[derive(Clone, Debug, Default)]
pub struct Terms {
connectives: Vec<String>,
connective_ids: HashMap<String, u32>,
sorts: Vec<String>,
sort_ids: HashMap<String, u32>,
atoms: Vec<(String, u32)>,
atom_ids: HashMap<(u32, String), u32>,
entries: Vec<Entry>,
arguments: Vec<TermId>,
latest: HashMap<u64, u32>,
earlier: Vec<u32>,
}
impl Terms {
const MOST: usize = (u32::MAX - 1) as usize;
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn term(&self, id: TermId) -> Term<'_> {
let entry = self.entries[id.index()];
match entry.head {
Head::Atom(atom) => {
let (name, sort) = &self.atoms[atom as usize];
Term::Atom {
name,
sort: &self.sorts[*sort as usize],
}
}
Head::Connective(connective) => Term::Apply {
connective: &self.connectives[connective as usize],
arguments: self.arguments_of(entry),
},
}
}
pub fn atom(&mut self, name: &str, sort: &str) -> Result<TermId, Error> {
let name = &*name::normalized(name);
for word in [name, sort] {
if !name::is_identifier(word) {
return Err(Error::AtomName {
name: word.to_owned(),
});
}
}
let sort = match self.sort_ids.get(sort) {
Some(&index) => index,
None => {
let index = self.sorts.len() as u32;
self.sorts.push(sort.to_owned());
self.sort_ids.insert(sort.to_owned(), index);
index
}
};
let key = (sort, name.to_owned());
let atom = match self.atom_ids.get(&key) {
Some(&atom) => atom,
None => {
let atom = self.atoms.len() as u32;
self.atoms.push((key.1.clone(), sort));
self.atom_ids.insert(key, atom);
atom
}
};
self.add(Head::Atom(atom), &[])
}
pub fn apply(&mut self, connective: &str, arguments: &[TermId]) -> Result<TermId, Error> {
if let Some(outside) = arguments.iter().find(|id| id.index() >= self.len()) {
return Err(Error::IndexOutOfBounds {
space: Space::Term,
index: outside.index(),
len: self.len(),
});
}
let index = match self.connective_ids.get(connective) {
Some(&index) => index,
None => {
let index = self.connectives.len() as u32;
self.connectives.push(connective.to_owned());
self.connective_ids.insert(connective.to_owned(), index);
index
}
};
self.add(Head::Connective(index), arguments)
}
#[cfg(all(feature = "interactive", feature = "parse"))]
pub(crate) fn names(&self, name: &str) -> bool {
self.atoms.iter().any(|(atom, _)| atom == name)
}
pub(crate) fn connectives(&self) -> &[String] {
&self.connectives
}
pub(crate) fn sorts(&self) -> &[String] {
&self.sorts
}
pub(crate) fn parts(&self, id: TermId) -> (Head, &[TermId]) {
let entry = self.entries[id.index()];
(entry.head, self.arguments_of(entry))
}
pub(crate) fn sort_of(&self, atom: u32) -> u32 {
self.atoms[atom as usize].1
}
pub(crate) fn find(&self, head: Head, arguments: &[TermId]) -> Option<TermId> {
let mut at = *self.latest.get(&Self::hash(head, arguments))?;
while at != NONE {
let entry = self.entries[at as usize];
if entry.head == head && self.arguments_of(entry) == arguments {
return Some(TermId(at));
}
at = self.earlier[at as usize];
}
None
}
fn arguments_of(&self, entry: Entry) -> &[TermId] {
&self.arguments[entry.start as usize..][..entry.len as usize]
}
fn hash(head: Head, arguments: &[TermId]) -> u64 {
BuildHasher::default().hash_one((head, arguments))
}
fn add(&mut self, head: Head, arguments: &[TermId]) -> Result<TermId, Error> {
if let Some(id) = self.find(head, arguments) {
return Ok(id);
}
let full = |count: usize| {
Error::Refused(Refusal::Index {
what: Space::Term,
count: count as u64,
most: Self::MOST as u64,
})
};
if self.entries.len() >= Self::MOST {
return Err(full(self.entries.len() + 1));
}
let end = self.arguments.len() + arguments.len();
if end > Self::MOST {
return Err(full(end));
}
let id = self.entries.len() as u32;
self.entries.push(Entry {
head,
start: self.arguments.len() as u32,
len: arguments.len() as u32,
});
self.arguments.extend_from_slice(arguments);
let before = self.latest.insert(Self::hash(head, arguments), id);
self.earlier.push(before.unwrap_or(NONE));
Ok(TermId(id))
}
}