use crate::Error;
use crate::hash::HashMap;
use crate::limits::Space;
use crate::linear::occurrences::{Forest, Member, OccId};
use crate::linear::proofs::Node;
use crate::linear::sequents::fo::FirstOrder;
use crate::linear::sequents::{Args, Eigen, FoTerm, FoTermId, Symbol};
use std::fmt::{Result as FmtResult, Write};
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct FrameId(u32);
impl FrameId {
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
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct Instances {
pub(crate) occurrences: u32,
pub(crate) base_terms: u32,
pub(crate) base_lists: u32,
pub(crate) members: Vec<(OccId, FrameId)>,
pub(crate) frames: Vec<(Option<FrameId>, FoTermId)>,
pub(crate) terms: Vec<FoTerm>,
pub(crate) args: Vec<FoTermId>,
pub(crate) lists: Vec<(u32, u32)>,
}
impl Instances {
pub fn new(forest: &Forest) -> Self {
let fo = &forest.sequent().fo;
Self {
occurrences: forest.len() as u32,
base_terms: fo.terms.len() as u32,
base_lists: fo.lists.len() as u32,
..Self::default()
}
}
pub fn eigen(&mut self, a: Eigen) -> FoTermId {
self.push_term(FoTerm::Eigen(a))
}
pub fn apply(&mut self, symbol: Symbol, args: &[FoTermId]) -> FoTermId {
let start = saturated(self.args.len());
self.args.extend_from_slice(args);
self.lists.push((start, saturated(args.len())));
let list = Args::new(
self.base_lists
.saturating_add(saturated(self.lists.len() - 1)),
);
self.push_term(FoTerm::App(symbol, list))
}
pub fn frame(&mut self, parent: Option<FrameId>, term: FoTermId) -> FrameId {
self.frames.push((parent, term));
FrameId::new(saturated(self.frames.len() - 1))
}
pub fn member(&mut self, occurrence: OccId, frame: FrameId) -> Member {
self.members.push((occurrence, frame));
Member::new(
self.occurrences
.saturating_add(saturated(self.members.len() - 1)),
)
}
pub fn len(&self) -> usize {
self.members.len()
}
pub fn is_empty(&self) -> bool {
self.members.is_empty()
}
pub fn instance(&self, member: Member) -> Option<(OccId, FrameId)> {
let at = member.get().checked_sub(self.occurrences)?;
self.members.get(at as usize).copied()
}
pub fn frame_parts(&self, frame: FrameId) -> (Option<FrameId>, FoTermId) {
self.frames[frame.index()]
}
pub fn frame_terms(&self, frame: FrameId) -> Vec<FoTermId> {
let mut terms = Vec::new();
let mut next = Some(frame);
while let Some(f) = next {
let (parent, term) = self.frames[f.index()];
terms.push(term);
next = parent;
}
terms
}
pub fn terms(&self) -> &[FoTerm] {
&self.terms
}
pub fn first_term(&self) -> FoTermId {
FoTermId::new(self.base_terms)
}
pub fn eigenvariables(&self) -> Vec<Eigen> {
let mut eigens: Vec<Eigen> = self
.terms
.iter()
.filter_map(|t| match *t {
FoTerm::Eigen(a) => Some(a),
FoTerm::Bound(_) | FoTerm::App(..) | FoTerm::Meta(_) => None,
})
.collect();
eigens.sort_unstable();
eigens.dedup();
eigens
}
pub(crate) fn push_term(&mut self, term: FoTerm) -> FoTermId {
self.terms.push(term);
FoTermId::new(
self.base_terms
.saturating_add(saturated(self.terms.len() - 1)),
)
}
}
fn saturated(n: usize) -> u32 {
u32::try_from(n).unwrap_or(u32::MAX)
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Terms<'a> {
pub(crate) fo: &'a FirstOrder,
pub(crate) table: &'a Instances,
}
impl Terms<'_> {
pub(crate) fn len(&self) -> usize {
self.fo.terms.len() + self.table.terms.len()
}
pub(crate) fn term(&self, id: FoTermId) -> FoTerm {
match id.index().checked_sub(self.fo.terms.len()) {
None => self.fo.terms[id.index()],
Some(at) => self.table.terms[at],
}
}
pub(crate) fn list(&self, args: Args) -> &[FoTermId] {
match args.index().checked_sub(self.fo.lists.len()) {
None => self.fo.list(args),
Some(at) => {
let (start, len) = self.table.lists[at];
&self.table.args[start as usize..(start + len) as usize]
}
}
}
fn lists(&self) -> usize {
self.fo.lists.len() + self.table.lists.len()
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
enum Key {
Bound(u32),
App(Symbol, u64),
Eigen(Eigen),
}
#[derive(Default)]
pub(crate) struct Hashcons {
terms: HashMap<Key, u64>,
lists: HashMap<Box<[u64]>, u64>,
}
impl Hashcons {
fn term(&mut self, key: Key) -> (u64, bool) {
let next = self.terms.len() as u64;
match self.terms.entry(key) {
std::collections::hash_map::Entry::Occupied(e) => (*e.get(), false),
std::collections::hash_map::Entry::Vacant(e) => (*e.insert(next), true),
}
}
fn list(&mut self, items: &[u64]) -> (u64, bool) {
if let Some(&n) = self.lists.get(items) {
return (n, false);
}
let n = self.lists.len() as u64;
self.lists.insert(items.into(), n);
(n, true)
}
}
pub(crate) struct Numbering<'a> {
terms: Terms<'a>,
cons: Hashcons,
numbers: Vec<u64>,
loose: Vec<u32>,
list_numbers: Vec<Option<u64>>,
}
impl<'a> Numbering<'a> {
pub(crate) fn new(terms: Terms<'a>) -> Self {
let mut this = Self {
terms,
cons: Hashcons::default(),
numbers: Vec::with_capacity(terms.len()),
loose: Vec::with_capacity(terms.len()),
list_numbers: vec![None; terms.lists()],
};
for id in 0..terms.len() {
let id = FoTermId::new(id as u32);
let (key, loose) = match terms.term(id) {
FoTerm::Bound(i) => (Key::Bound(i), i.saturating_add(1)),
FoTerm::Eigen(a) => (Key::Eigen(a), 0),
FoTerm::Meta(_) => unreachable!("a proof's table holds no metavariable"),
FoTerm::App(f, args) => {
let loose = terms
.list(args)
.iter()
.map(|t| this.loose[t.index()])
.max()
.unwrap_or(0);
(Key::App(f, this.list_number(args)), loose)
}
};
this.numbers.push(this.cons.term(key).0);
this.loose.push(loose);
}
this
}
fn list_number(&mut self, args: Args) -> u64 {
if let Some(n) = self.list_numbers[args.index()] {
return n;
}
let items: Vec<u64> = self
.terms
.list(args)
.iter()
.map(|t| self.numbers[t.index()])
.collect();
let n = self.cons.list(&items).0;
self.list_numbers[args.index()] = Some(n);
n
}
pub(crate) fn terms(&self) -> Terms<'a> {
self.terms
}
pub(crate) fn number(&self, id: FoTermId) -> u64 {
self.numbers[id.index()]
}
pub(crate) fn is_closed(&self, id: FoTermId) -> bool {
self.loose[id.index()] == 0
}
pub(crate) fn instance(&mut self, args: Args, frame: &[u64]) -> u64 {
let mut memo: HashMap<FoTermId, u64> = HashMap::default();
let terms = self.terms;
let list = terms.list(args);
let mut items = Vec::with_capacity(list.len());
for &t in list {
items.push(self.substitute(t, frame, &mut memo));
}
self.cons.list(&items).0
}
fn substitute(&mut self, t: FoTermId, frame: &[u64], memo: &mut HashMap<FoTermId, u64>) -> u64 {
if self.loose[t.index()] == 0 {
return self.numbers[t.index()];
}
let mut stack = vec![(t, false)];
while let Some((u, expanded)) = stack.pop() {
if memo.contains_key(&u) {
continue;
}
match self.terms.term(u) {
FoTerm::Bound(i) => {
memo.insert(u, frame[i as usize]);
}
FoTerm::App(f, args) if expanded => {
let items: Vec<u64> = self
.terms
.list(args)
.iter()
.map(|&c| {
if self.loose[c.index()] == 0 {
self.numbers[c.index()]
} else {
memo[&c]
}
})
.collect();
let list = self.cons.list(&items).0;
memo.insert(u, self.cons.term(Key::App(f, list)).0);
}
FoTerm::App(_, args) => {
stack.push((u, true));
for &c in self.terms.list(args) {
if self.loose[c.index()] > 0 && !memo.contains_key(&c) {
stack.push((c, false));
}
}
}
FoTerm::Eigen(_) => unreachable!("an eigenvariable is a closed term"),
FoTerm::Meta(_) => unreachable!("a proof's table holds no metavariable"),
}
}
memo[&t]
}
}
pub(crate) fn binders(forest: &Forest) -> Vec<u32> {
let mut depth = vec![0u32; forest.len()];
for o in forest.ids() {
if let Some(p) = forest.parent(o) {
depth[o.index()] = depth[p.index()] + u32::from(forest.kind(p).is_binder());
}
}
depth
}
fn malformed(message: String) -> Error {
Error::Json {
form: "instance table",
message,
}
}
pub(crate) fn canonical(
forest: &Forest,
table: &Instances,
nodes: &mut [Node],
) -> Result<Instances, Error> {
let fo = &forest.sequent().fo;
let made_for = Instances::new(forest);
if (table.occurrences, table.base_terms, table.base_lists)
!= (
made_for.occurrences,
made_for.base_terms,
made_for.base_lists,
)
{
return Err(malformed("the table was made for another sequent".into()));
}
let count = nodes.len() as u64;
let most = u64::from(u32::MAX);
let ids = [
(
Space::Member,
u64::from(table.occurrences) + table.members.len() as u64 + 3 * count,
),
(
Space::Term,
u64::from(table.base_terms) + table.terms.len() as u64 + count,
),
(
Space::Term,
u64::from(table.base_lists) + table.lists.len() as u64 + count,
),
(Space::Term, table.args.len() as u64),
(Space::Term, table.frames.len() as u64 + count),
];
if let Some(&(what, count)) = ids.iter().find(|&&(_, count)| count > most) {
return Err(Error::Refused(crate::limits::Refusal::Index {
what,
count,
most,
}));
}
let terms = Terms { fo, table };
let all_terms = terms.len();
let all_lists = terms.lists();
let mut predicate = vec![false; fo.symbols.len()];
for &(p, _) in &fo.atoms {
predicate[p.index()] = true;
}
for (&(start, len), n) in table.lists.iter().zip(0..) {
if (start as usize).saturating_add(len as usize) > table.args.len() {
return Err(malformed(format!("list {n} runs past the arguments")));
}
}
for (i, &term) in table.terms.iter().enumerate() {
let id = fo.terms.len() + i;
match term {
FoTerm::Bound(_) => {
return Err(malformed(format!("term {id} is a bound variable")));
}
FoTerm::Meta(_) => {
return Err(malformed(format!(
"term {id} is a metavariable, an open witness"
)));
}
FoTerm::Eigen(_) => {}
FoTerm::App(f, args) => {
let Some(&(_, arity)) = fo.symbols.get(f.index()) else {
return Err(malformed(format!("term {id} applies no symbol")));
};
if predicate[f.index()] {
return Err(malformed(format!("term {id} applies a predicate")));
}
if args.index() >= all_lists {
return Err(malformed(format!("term {id} has no argument list")));
}
let list = terms.list(args);
if list.len() != arity as usize {
return Err(malformed(format!(
"term {id} applies a symbol of {arity} arguments to {}",
list.len()
)));
}
if list.iter().any(|t| t.index() >= id) {
return Err(malformed(format!("term {id} refers to a later term")));
}
}
}
}
let numbering = Numbering::new(terms);
let mut lengths: Vec<u32> = Vec::with_capacity(table.frames.len());
for (n, &(parent, term)) in table.frames.iter().enumerate() {
if term.index() >= all_terms || !numbering.is_closed(term) {
return Err(malformed(format!("frame {n} pushes no closed term")));
}
let length = match parent {
None => 1,
Some(p) if p.index() < n => lengths[p.index()] + 1,
Some(_) => return Err(malformed(format!("frame {n} refers to a later frame"))),
};
lengths.push(length);
}
let depth = binders(forest);
for (n, &(o, frame)) in table.members.iter().enumerate() {
let member = u64::from(table.occurrences) + n as u64;
if o.index() >= forest.len() || frame.index() >= table.frames.len() {
return Err(malformed(format!("member {member} names no instance")));
}
if lengths[frame.index()] != depth[o.index()] {
return Err(malformed(format!(
"member {member} stands under {} binders with a frame of {} terms",
depth[o.index()],
lengths[frame.index()]
)));
}
}
for node in nodes.iter() {
if let Node::Exists(_, w, _) = *node {
if w.index() >= all_terms {
return Err(malformed(format!(
"the witness {} is past the {all_terms} terms",
w.get()
)));
}
if !numbering.is_closed(w) {
return Err(malformed(format!(
"the witness {} holds a loose bound variable",
w.get()
)));
}
}
}
Canonical::new(forest, table, numbering).finish(nodes)
}
struct Canonical<'a> {
forest: &'a Forest,
table: &'a Instances,
numbering: Numbering<'a>,
out: Instances,
term_at: HashMap<u64, FoTermId>,
list_at: HashMap<u64, Args>,
frame_at: HashMap<(Option<FrameId>, FoTermId), FrameId>,
made: Vec<Option<FrameId>>,
member_at: HashMap<(OccId, FrameId), Member>,
}
impl<'a> Canonical<'a> {
fn new(forest: &'a Forest, table: &'a Instances, numbering: Numbering<'a>) -> Self {
let fo = &forest.sequent().fo;
let mut this = Self {
forest,
table,
numbering,
out: Instances::new(forest),
term_at: HashMap::default(),
list_at: HashMap::default(),
frame_at: HashMap::default(),
made: vec![None; table.frames.len()],
member_at: HashMap::default(),
};
for id in 0..fo.terms.len() {
let id = FoTermId::new(id as u32);
this.term_at.entry(this.numbering.number(id)).or_insert(id);
}
for args in 0..fo.lists.len() {
let args = Args::new(args as u32);
let n = this.numbering.list_number(args);
this.list_at.entry(n).or_insert(args);
}
this
}
fn term(&mut self, id: FoTermId) -> FoTermId {
let mut walk = vec![(id, false)];
while let Some((t, expanded)) = walk.pop() {
let n = self.numbering.number(t);
if self.term_at.contains_key(&n) {
continue;
}
let term = match self.numbering.terms.term(t) {
FoTerm::App(f, args) => {
let ln = self.numbering.list_number(args);
let list = match self.list_at.get(&ln) {
Some(&list) => list,
None if !expanded => {
walk.push((t, true));
walk.extend(
self.numbering.terms.list(args).iter().map(|&a| (a, false)),
);
continue;
}
None => {
let items: Vec<FoTermId> = self
.numbering
.terms
.list(args)
.iter()
.map(|&a| self.term_at[&self.numbering.number(a)])
.collect();
let start = self.out.args.len() as u32;
self.out.args.extend_from_slice(&items);
self.out.lists.push((start, items.len() as u32));
let list =
Args::new(self.out.base_lists + self.out.lists.len() as u32 - 1);
self.list_at.insert(ln, list);
list
}
};
FoTerm::App(f, list)
}
other @ (FoTerm::Eigen(_) | FoTerm::Bound(_) | FoTerm::Meta(_)) => other,
};
let at = self.out.push_term(term);
self.term_at.insert(n, at);
}
self.term_at[&self.numbering.number(id)]
}
fn eigen(&mut self, a: Eigen) -> FoTermId {
let (n, _) = self.numbering.cons.term(Key::Eigen(a));
if let Some(&at) = self.term_at.get(&n) {
return at;
}
let at = self.out.push_term(FoTerm::Eigen(a));
self.term_at.insert(n, at);
at
}
fn push(&mut self, parent: Option<FrameId>, term: FoTermId) -> FrameId {
*self.frame_at.entry((parent, term)).or_insert_with(|| {
self.out.frames.push((parent, term));
FrameId::new(self.out.frames.len() as u32 - 1)
})
}
fn frame(&mut self, f: FrameId) -> FrameId {
let mut chain = Vec::new();
let mut next = Some(f);
let mut below = None;
while let Some(f) = next {
if let Some(made) = self.made[f.index()] {
below = Some(made);
break;
}
chain.push(f);
next = self.table.frames[f.index()].0;
}
for f in chain.into_iter().rev() {
let term = self.term(self.table.frames[f.index()].1);
let made = self.push(below, term);
self.made[f.index()] = Some(made);
below = Some(made);
}
below.expect("a frame holds a term")
}
fn member(&mut self, o: OccId, frame: Option<FrameId>) -> Member {
let Some(frame) = frame else {
return Member::from(o);
};
*self.member_at.entry((o, frame)).or_insert_with(|| {
self.out.members.push((o, frame));
Member::new(self.out.occurrences + self.out.members.len() as u32 - 1)
})
}
fn resolve(&self, m: Member) -> (OccId, Option<FrameId>) {
match self.out.instance(m) {
Some((o, f)) => (o, Some(f)),
None => (m.occ(), None),
}
}
fn finish(mut self, nodes: &mut [Node]) -> Result<Instances, Error> {
let read: Vec<Member> = (0..self.table.members.len())
.map(|n| {
let (o, f) = self.table.members[n];
let f = self.frame(f);
self.member(o, Some(f))
})
.collect();
let occurrences = self.table.occurrences;
let renumber = |m: Member| -> Result<Member, Error> {
match m.get().checked_sub(occurrences) {
None => Ok(m),
Some(at) => read
.get(at as usize)
.copied()
.ok_or(Error::IndexOutOfBounds {
space: Space::Member,
index: m.index(),
len: occurrences as usize + read.len(),
}),
}
};
for node in nodes.iter_mut() {
*node = node.renamed(renumber)?;
if let Node::Exists(m, w, p) = *node {
*node = Node::Exists(m, self.term(w), p);
}
}
let forest = self.forest;
for node in nodes.iter() {
for m in node.members() {
let (o, frame) = self.resolve(m);
if frame.is_some() && !forest.kind(o).is_binder() {
for c in forest.children(o) {
self.member(c, frame);
}
}
}
match *node {
Node::Forall(m, a, _) => {
let (o, frame) = self.resolve(m);
if forest.kind(o).is_binder() {
let term = self.eigen(a);
let frame = self.push(frame, term);
self.member(OccId::new(o.get() + 1), Some(frame));
}
}
Node::Exists(m, w, _) => {
let (o, frame) = self.resolve(m);
if forest.kind(o).is_binder() {
let frame = self.push(frame, w);
self.member(OccId::new(o.get() + 1), Some(frame));
}
}
Node::Cut(m, ..) => {
let (o, frame) = self.resolve(m);
if let Some(dual) = forest.dual(o) {
self.member(dual, frame);
}
}
Node::Ax(..)
| Node::Tensor(..)
| Node::Par(..)
| Node::One(_)
| Node::Bot(..)
| Node::With(..)
| Node::Plus(..)
| Node::Top(_)
| Node::Bang(..)
| Node::Quest(..)
| Node::Copy(..)
| Node::Weaken(..)
| Node::Mix(..) => {}
}
}
Ok(self.out)
}
}
pub(crate) fn eigen_names(fo: &FirstOrder, eigens: &[Eigen]) -> HashMap<Eigen, String> {
let taken: std::collections::HashSet<&str> =
fo.symbols.iter().map(|(s, _)| s.as_str()).collect();
let mut names = HashMap::default();
let mut candidates = (0u64..).map(|n| {
let letter = char::from(b'a' + (n % 26) as u8);
match n / 26 {
0 => letter.to_string(),
k => format!("{letter}_{k}"),
}
});
for &a in eigens {
let name = candidates
.by_ref()
.find(|c| !taken.contains(c.as_str()))
.expect("the candidates never end");
names.insert(a, name);
}
names
}
pub(crate) fn meta_name(k: u32) -> String {
format!("${}", u64::from(k) + 1)
}
#[derive(Clone, Debug)]
pub(crate) struct Framing<'a> {
pub(crate) table: &'a Instances,
terms: Terms<'a>,
names: HashMap<Eigen, String>,
}
impl<'a> Framing<'a> {
pub(crate) fn new(fo: &'a FirstOrder, table: &'a Instances) -> Self {
Self {
table,
terms: Terms { fo, table },
names: eigen_names(fo, &table.eigenvariables()),
}
}
pub(crate) fn occurrence(&self, m: Member) -> OccId {
self.table.instance(m).map_or(m.occ(), |(o, _)| o)
}
#[cfg(feature = "rocq")]
pub(crate) const fn terms(&self) -> Terms<'a> {
self.terms
}
#[cfg(feature = "rocq")]
pub(crate) fn list(&self, args: Args) -> &[FoTermId] {
self.terms.list(args)
}
pub(crate) fn names(&self) -> impl Iterator<Item = &str> {
self.names.values().map(String::as_str)
}
pub(crate) fn name(&self, a: Eigen) -> &str {
self.names.get(&a).map_or("?", String::as_str)
}
pub(crate) fn write_term<W: Write + ?Sized>(
&self,
out: &mut W,
term: FoTermId,
atom: &mut impl FnMut(&mut W, &str) -> 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.term(t) {
FoTerm::App(f, args) => {
atom(out, &self.terms.fo.symbols[f.index()].0)?;
if !self.terms.list(args).is_empty() {
out.write_char('(')?;
open.push((args, 0));
}
}
FoTerm::Eigen(a) => atom(out, self.name(a))?,
FoTerm::Meta(k) => atom(out, &meta_name(k))?,
FoTerm::Bound(index) => write!(out, "#{index}")?,
}
}
let Some(&mut (args, ref mut i)) = open.last_mut() else {
return Ok(());
};
let list = self.terms.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();
}
}
}
}