use super::FORMULA;
use crate::Error;
use crate::hash::{HashMap, HashSet};
use crate::limits::{Limits, Phase, Refusal};
use crate::serialize::rules::{CalculusForm, DISCHARGES, PatternForm, RuleForm, SequentForm};
const ARITY: u32 = 255;
const SLOT_BYTES: u64 = 64;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
#[serde(rename_all = "lowercase")]
#[non_exhaustive]
pub enum Discipline {
Set,
Multiset,
Sequence,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
#[serde(rename_all = "lowercase")]
#[non_exhaustive]
pub enum Fixity {
Prefix,
Infix,
Postfix,
Function,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, serde::Serialize, serde::Deserialize)]
#[serde(rename_all = "lowercase")]
#[non_exhaustive]
pub enum Associativity {
Left,
Right,
None,
}
#[derive(Clone, Debug)]
pub(crate) struct Connective {
pub(crate) arguments: Vec<u32>,
pub(crate) result: u32,
}
#[derive(Clone, Debug)]
pub(crate) struct Zone {
pub(crate) name: String,
pub(crate) sort: u32,
pub(crate) discipline: Discipline,
pub(crate) least: u32,
pub(crate) most: Option<u32>,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Pattern {
Variable(u32),
Apply {
connective: u32,
start: u32,
len: u32,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Find {
Start(u32),
End(u32),
Value,
Position,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Item {
pub(crate) first: u32,
pub(crate) root: u32,
pub(crate) find: Find,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Entry {
Item(Item),
Context {
variable: u32,
under: Option<u32>,
},
}
#[derive(Clone, Debug, Default)]
pub(crate) struct Shape {
pub(crate) zones: Vec<Vec<Entry>>,
}
#[derive(Clone, Debug)]
pub(crate) struct Premise {
pub(crate) shape: Shape,
pub(crate) discharges: Vec<Vec<Vec<(u32, u32)>>>,
}
#[derive(Clone, Debug)]
pub(crate) struct Equation {
pub(crate) sequent: u32,
pub(crate) zone: u32,
pub(crate) segment: u32,
pub(crate) contexts: Vec<(u32, Option<u32>)>,
pub(crate) define: Option<u32>,
}
#[derive(Clone, Debug)]
pub(crate) struct Rule {
pub(crate) patterns: Vec<Pattern>,
pub(crate) arguments: Vec<u32>,
pub(crate) conclusion: Shape,
pub(crate) premises: Vec<Premise>,
pub(crate) fresh: Vec<u32>,
pub(crate) atomic: Vec<u32>,
pub(crate) equations: Vec<Equation>,
pub(crate) positions: u32,
}
impl Rule {
pub(crate) fn shape(&self, index: usize) -> &Shape {
match index.checked_sub(1) {
None => &self.conclusion,
Some(premise) => &self.premises[premise].shape,
}
}
pub(crate) fn arguments(&self, start: u32, len: u32) -> &[u32] {
&self.arguments[start as usize..][..len as usize]
}
}
#[derive(Clone, Debug)]
pub struct Calculus {
form: CalculusForm,
pub(crate) sort_ids: HashMap<String, u32>,
pub(crate) connectives: Vec<Connective>,
pub(crate) connective_ids: HashMap<String, u32>,
pub(crate) zones: Vec<Zone>,
pub(crate) variables: u32,
pub(crate) contexts: Vec<Option<Discipline>>,
#[cfg_attr(
not(all(feature = "interactive", feature = "parse")),
expect(dead_code, reason = "a session reads them")
)]
pub(crate) variable_names: Vec<(String, u32)>,
#[cfg_attr(
not(all(feature = "interactive", feature = "parse")),
expect(dead_code, reason = "a session reads them")
)]
pub(crate) context_names: Vec<(String, Option<u32>)>,
pub(crate) rules: Vec<Rule>,
pub(crate) rule_ids: HashMap<String, u32>,
}
#[derive(Clone, Copy, Debug)]
enum Name {
Variable(u32, u32),
Context(u32),
Connective(u32),
}
fn declare<'a>(names: &mut HashMap<&'a str, Name>, name: &'a str, what: Name) -> Result<(), Error> {
if name.is_empty() {
return Err(invalid("a name is empty".to_owned()));
}
match names.insert(name, what) {
None => Ok(()),
Some(_) => Err(invalid(format!("the name {name:?} is declared twice"))),
}
}
fn invalid(reason: String) -> Error {
Error::InvalidCalculus { reason }
}
impl Calculus {
pub fn name(&self) -> &str {
&self.form.name
}
pub fn description(&self) -> &str {
&self.form.description
}
pub fn zones(&self) -> impl ExactSizeIterator<Item = &str> {
self.zones.iter().map(|zone| &*zone.name)
}
pub fn marks(&self) -> impl ExactSizeIterator<Item = Option<&str>> {
self.form.sequent.iter().map(|zone| zone.mark.as_deref())
}
pub fn rules(&self) -> impl ExactSizeIterator<Item = &str> {
self.form.rules.iter().map(|rule| &*rule.name)
}
pub fn positions(&self, rule: &str) -> Option<usize> {
let index = *self.rule_ids.get(rule)?;
Some(self.rules[index as usize].positions as usize)
}
pub(crate) const fn form(&self) -> &CalculusForm {
&self.form
}
pub(crate) fn from_form(form: CalculusForm, limits: &Limits) -> Result<Self, Error> {
let mut names: HashMap<&str, Name> = HashMap::default();
if form.name.is_empty() {
return Err(invalid("the calculus has no name".to_owned()));
}
let written = std::iter::once(form.name.as_str())
.chain(
form.connectives
.iter()
.flat_map(|c| std::iter::once(c.name.as_str()).chain(c.symbol.as_deref())),
)
.chain(
form.sequent
.iter()
.flat_map(|z| std::iter::once(z.name.as_str()).chain(z.mark.as_deref())),
)
.chain(form.rules.iter().map(|r| r.name.as_str()));
for text in written {
if text.chars().any(char::is_control) {
return Err(invalid(format!(
"the name or symbol {text:?} holds a control character"
)));
}
}
let slots = form.rules.iter().fold(0u64, |sum, rule| {
let sequents = rule.premises.iter().fold(1u64, |sum, premise| {
sum.saturating_add(1)
.saturating_add(premise.discharges.len() as u64)
});
sum.saturating_add(sequents.saturating_mul(form.sequent.len() as u64))
});
let needed = slots.saturating_mul(SLOT_BYTES);
if let Some(limit_bytes) = limits.memory_bytes
&& needed > limit_bytes
{
return Err(Error::Refused(Refusal::Memory {
phase: Phase::Read,
limit_bytes,
needed_bytes: Some(needed),
}));
}
let mut sort_ids: HashMap<String, u32> = HashMap::default();
sort_ids.insert(FORMULA.to_owned(), 0);
for sort in &form.sorts {
let index = sort_ids.len() as u32;
if sort.is_empty() || sort_ids.insert(sort.clone(), index).is_some() {
return Err(invalid(format!("the sort {sort:?} is declared twice")));
}
}
let sort_of = |name: &str| {
sort_ids
.get(name)
.copied()
.ok_or_else(|| invalid(format!("no sort is named {name:?}")))
};
let mut connectives = Vec::with_capacity(form.connectives.len());
for (index, connective) in form.connectives.iter().enumerate() {
if connective.arity > ARITY {
return Err(invalid(format!(
"the connective {:?} takes {} arguments; a connective takes {ARITY} at most",
connective.name, connective.arity
)));
}
let arity = connective.arity as usize;
let (arguments, result) = match &connective.sorts {
None => (vec![0; arity], 0),
Some(list) if list.len() == arity + 1 => {
let mut list = list
.iter()
.map(|name| sort_of(name))
.collect::<Result<Vec<_>, _>>()?;
let result = list.pop().unwrap_or(0);
(list, result)
}
Some(list) => {
return Err(invalid(format!(
"the connective {:?} takes {arity} arguments and names {} sorts: \
it needs one for each argument and one for the term it makes",
connective.name,
list.len()
)));
}
};
declare(&mut names, &connective.name, Name::Connective(index as u32))?;
connectives.push(Connective { arguments, result });
}
let mut zones = Vec::with_capacity(form.sequent.len());
let mut zone_names: HashSet<&str> = HashSet::default();
for zone in &form.sequent {
if zone.name == DISCHARGES || !zone_names.insert(&zone.name) {
return Err(invalid(format!(
"the zone name {:?} is taken: by another zone, or as a premise's key",
zone.name
)));
}
let least = zone.least.unwrap_or(0);
if zone.most.is_some_and(|most| most < least) {
return Err(invalid(format!(
"the zone {:?} holds at least {least} members and at most fewer",
zone.name
)));
}
zones.push(Zone {
name: zone.name.clone(),
sort: sort_of(zone.sort.as_deref().unwrap_or(FORMULA))?,
discipline: zone.discipline,
least,
most: zone.most,
});
}
if zones.is_empty() {
return Err(invalid("a sequent has at least one zone".to_owned()));
}
let mut variables = 0;
let mut variable_names = Vec::new();
for (sort, list) in &form.variables {
let sort = sort_of(sort)?;
for name in list {
declare(&mut names, name, Name::Variable(variables, sort))?;
variable_names.push((name.clone(), sort));
variables += 1;
}
}
for (index, name) in form.contexts.iter().enumerate() {
declare(&mut names, name, Name::Context(index as u32))?;
}
let mut compiler = Compiler {
names: &names,
connectives: &connectives,
zones: &zones,
zone_ids: zones
.iter()
.enumerate()
.map(|(index, zone)| (&*zone.name, index))
.collect(),
contexts: vec![None; form.contexts.len()],
budget: limits.occurrences,
nodes: 0,
};
let mut rules = Vec::with_capacity(form.rules.len());
let mut rule_ids = HashMap::default();
for (index, rule) in form.rules.iter().enumerate() {
if rule.name.is_empty() || rule_ids.insert(rule.name.clone(), index as u32).is_some() {
return Err(invalid(format!(
"the rule name {:?} is empty or used twice",
rule.name
)));
}
let compiled = compiler
.rule(rule, variables)
.map_err(|error| match error {
Error::InvalidCalculus { reason } => {
invalid(format!("rule {:?}: {reason}", rule.name))
}
other => other,
})?;
rules.push(compiled);
}
let contexts = compiler
.contexts
.iter()
.map(|c| c.map(|(d, _)| d))
.collect();
let context_names = form
.contexts
.iter()
.zip(&compiler.contexts)
.map(|(name, c)| (name.clone(), c.map(|(_, sort)| sort)))
.collect();
let connective_ids = form
.connectives
.iter()
.enumerate()
.map(|(index, connective)| (connective.name.clone(), index as u32))
.collect();
Ok(Self {
sort_ids,
connectives,
connective_ids,
zones,
variables,
contexts,
variable_names,
context_names,
rules,
rule_ids,
form,
})
}
}
struct Compiler<'a> {
names: &'a HashMap<&'a str, Name>,
connectives: &'a [Connective],
zones: &'a [Zone],
zone_ids: HashMap<&'a str, usize>,
contexts: Vec<Option<(Discipline, u32)>>,
budget: Option<u64>,
nodes: u64,
}
#[derive(Default)]
struct Patterns {
nodes: Vec<Pattern>,
arguments: Vec<u32>,
}
impl Compiler<'_> {
fn name(&self, name: &str) -> Result<Name, Error> {
self.names.get(name).copied().ok_or_else(|| {
invalid(format!(
"{name:?} is neither a declared variable or context nor a connective"
))
})
}
fn pattern(
&mut self,
form: &PatternForm,
patterns: &mut Patterns,
) -> Result<(u32, u32), Error> {
self.nodes += 1;
if let Some(limit) = self.budget
&& self.nodes > limit
{
return Err(Error::Refused(Refusal::Occurrences {
occurrences: self.nodes,
limit,
}));
}
let (name, arguments) = match form {
PatternForm::Name(name) => (name, &[][..]),
PatternForm::Apply(name, arguments) => (name, &arguments[..]),
};
let (node, sort) = match self.name(name)? {
Name::Variable(variable, sort) if arguments.is_empty() => {
(Pattern::Variable(variable), sort)
}
Name::Variable(..) => {
return Err(invalid(format!("the variable {name:?} takes no arguments")));
}
Name::Context(_) => {
return Err(invalid(format!(
"the context {name:?} stands where a term does: a context is an entry \
of a zone, alone or under one unary connective"
)));
}
Name::Connective(connective) => {
let signature = &self.connectives[connective as usize];
if signature.arguments.len() != arguments.len() {
return Err(invalid(format!(
"{name:?} takes {} arguments, not {}",
signature.arguments.len(),
arguments.len()
)));
}
let mut roots = Vec::with_capacity(arguments.len());
for (argument, &expected) in arguments.iter().zip(&signature.arguments) {
let (root, sort) = self.pattern(argument, patterns)?;
if sort != expected {
return Err(invalid(format!(
"an argument of {name:?} has another sort than the connective takes"
)));
}
roots.push(root);
}
let start = patterns.arguments.len() as u32;
patterns.arguments.extend(roots);
let node = Pattern::Apply {
connective,
start,
len: arguments.len() as u32,
};
(node, signature.result)
}
};
patterns.nodes.push(node);
Ok((patterns.nodes.len() as u32 - 1, sort))
}
fn zone(&self, name: &str) -> Result<usize, Error> {
self.zone_ids
.get(name)
.copied()
.ok_or_else(|| invalid(format!("no zone is named {name:?}")))
}
fn shape(
&mut self,
form: &SequentForm,
patterns: &mut Patterns,
contexts: bool,
) -> Result<Shape, Error> {
let mut shape = Shape {
zones: vec![Vec::new(); self.zones.len()],
};
let mut placed: HashSet<(usize, u32)> = HashSet::default();
for (name, entries) in form {
let zone = self.zone(name)?;
let (sort, discipline) = (self.zones[zone].sort, self.zones[zone].discipline);
for entry in entries {
let context = match entry {
PatternForm::Name(name) => match self.name(name)? {
Name::Context(variable) => Some((variable, None, sort)),
Name::Variable(..) | Name::Connective(_) => None,
},
PatternForm::Apply(head, arguments) => match arguments.as_slice() {
[PatternForm::Name(inner)] => match (self.name(head)?, self.name(inner)?) {
(Name::Connective(connective), Name::Context(variable)) => {
let signature = &self.connectives[connective as usize];
if signature.arguments.len() != 1 {
return Err(invalid(format!(
"{head:?} over the context {inner:?} takes {} \
arguments: only a connective of one argument stands \
over a context",
signature.arguments.len()
)));
}
if signature.result != sort {
return Err(invalid(format!(
"{head:?} over the context {inner:?} makes no member \
of the zone {name:?}"
)));
}
Some((variable, Some(connective), signature.arguments[0]))
}
_ => None,
},
_ => None,
},
};
let Some((variable, under, members)) = context else {
let first = patterns.nodes.len() as u32;
let (root, item) = self.pattern(entry, patterns)?;
if item != sort {
return Err(invalid(format!(
"an entry of the zone {name:?} has another sort than the zone"
)));
}
shape.zones[zone].push(Entry::Item(Item {
first,
root,
find: Find::Position,
}));
continue;
};
if !contexts {
return Err(invalid(
"a discharged hypothesis writes out its members: it has no context"
.to_owned(),
));
}
if !placed.insert((zone, variable)) {
return Err(invalid(format!(
"a context stands twice in the zone {name:?}"
)));
}
match self.contexts[variable as usize] {
None => self.contexts[variable as usize] = Some((discipline, members)),
Some(known) if known == (discipline, members) => {}
Some(_) => {
return Err(invalid(format!(
"a context of the zone {name:?} is used elsewhere with another \
discipline or sort"
)));
}
}
shape.zones[zone].push(Entry::Context { variable, under });
}
}
Ok(shape)
}
fn rule(&mut self, form: &RuleForm, variables: u32) -> Result<Rule, Error> {
let mut patterns = Patterns::default();
let conclusion = self.shape(&form.conclusion, &mut patterns, true)?;
let mut premises = Vec::with_capacity(form.premises.len());
for premise in &form.premises {
let shape = self.shape(&premise.sequent, &mut patterns, true)?;
let mut discharges = Vec::with_capacity(premise.discharges.len());
for hypothesis in &premise.discharges {
let shape = self.shape(hypothesis, &mut patterns, false)?;
let ranges = |zone: &Vec<Entry>| {
zone.iter()
.filter_map(|entry| match entry {
Entry::Item(item) => Some((item.first, item.root)),
Entry::Context { .. } => None,
})
.collect()
};
discharges.push(shape.zones.iter().map(ranges).collect());
}
premises.push(Premise { shape, discharges });
}
let mut rule = Rule {
patterns: patterns.nodes,
arguments: patterns.arguments,
conclusion,
premises,
fresh: Vec::new(),
atomic: Vec::new(),
equations: Vec::new(),
positions: 0,
};
let mut bound = vec![false; variables as usize];
for index in 0..=rule.premises.len() {
for zone in 0..self.zones.len() {
let sequence = self.zones[zone].discipline == Discipline::Sequence;
let entries = rule.shape(index).zones[zone].clone();
let contexts = entries
.iter()
.filter(|e| matches!(e, Entry::Context { .. }))
.count();
let mut found = Vec::with_capacity(entries.len());
let mut seen_context = false;
let mut place = 0;
for (at, entry) in entries.iter().enumerate() {
let Entry::Item(item) = entry else {
seen_context = true;
continue;
};
let range = item.first as usize..=item.root as usize;
let unbound = rule.patterns[range.clone()]
.iter()
.any(|node| matches!(node, Pattern::Variable(v) if !bound[*v as usize]));
let find = if contexts <= 1 && (sequence || entries.len() == 1) {
if seen_context {
Find::End((entries.len() - 1 - at) as u32)
} else {
Find::Start(place)
}
} else if sequence || unbound || index == 0 {
rule.positions += 1;
Find::Position
} else {
Find::Value
};
place += 1;
for node in &rule.patterns[range] {
if let Pattern::Variable(variable) = node {
bound[*variable as usize] = true;
}
}
found.push((at, find));
}
let shape = match index.checked_sub(1) {
None => &mut rule.conclusion,
Some(premise) => &mut rule.premises[premise].shape,
};
for (at, find) in found {
if let Entry::Item(item) = &mut shape.zones[zone][at] {
item.find = find;
}
}
}
}
let unbound = |what: &str| {
invalid(format!(
"a variable of {what} occurs in no sequent of the rule"
))
};
for (list, into) in [(&form.fresh, 0), (&form.atomic, 1)] {
for name in list {
let Name::Variable(variable, _) = self.name(name)? else {
return Err(invalid(format!("{name:?} is no schematic variable")));
};
if !bound[variable as usize] {
return Err(unbound("a condition"));
}
let list = if into == 0 {
&mut rule.fresh
} else {
&mut rule.atomic
};
if list.contains(&variable) {
return Err(invalid(format!("{name:?} is named twice in a condition")));
}
list.push(variable);
}
}
for premise in &rule.premises {
for &(first, root) in premise.discharges.iter().flatten().flatten() {
let open = rule.patterns[first as usize..=root as usize]
.iter()
.any(|node| matches!(node, Pattern::Variable(v) if !bound[*v as usize]));
if open {
return Err(unbound("a discharged hypothesis"));
}
}
}
rule.equations = self.equations(&rule)?;
Ok(rule)
}
fn equations(&self, rule: &Rule) -> Result<Vec<Equation>, Error> {
let mut equations = Vec::new();
for sequent in 0..=rule.premises.len() {
for (zone, entries) in rule.shape(sequent).zones.iter().enumerate() {
let sequence = match self.zones[zone].discipline {
Discipline::Set => continue,
Discipline::Multiset => false,
Discipline::Sequence => true,
};
let mut segment = 0;
let mut contexts = Vec::new();
for entry in entries {
match *entry {
Entry::Context { variable, under } => contexts.push((variable, under)),
Entry::Item(_) if sequence => {
equations.push(Equation {
sequent: sequent as u32,
zone: zone as u32,
segment,
contexts: std::mem::take(&mut contexts),
define: None,
});
segment += 1;
}
Entry::Item(_) => {}
}
}
equations.push(Equation {
sequent: sequent as u32,
zone: zone as u32,
segment,
contexts,
define: None,
});
}
}
let mut waiting: Vec<usize> = equations.iter().map(|e| e.contexts.len()).collect();
let mut stands: Vec<Vec<usize>> = vec![Vec::new(); self.contexts.len()];
for (index, equation) in equations.iter().enumerate() {
for &(variable, _) in &equation.contexts {
stands[variable as usize].push(index);
}
}
let mut defined = vec![false; self.contexts.len()];
let mut done = vec![false; equations.len()];
let mut ready: Vec<usize> = (0..equations.len()).filter(|&e| waiting[e] <= 1).collect();
let mut order = Vec::with_capacity(equations.len());
while let Some(index) = ready.pop() {
if std::mem::replace(&mut done[index], true) {
continue;
}
let mut equation = equations[index].clone();
let unknown = equation
.contexts
.iter()
.position(|&(variable, _)| !defined[variable as usize]);
if let Some(place) = unknown {
let variable = equation.contexts[place].0;
defined[variable as usize] = true;
equation.define = Some(place as u32);
for &other in &stands[variable as usize] {
waiting[other] -= 1;
if waiting[other] <= 1 && !done[other] {
ready.push(other);
}
}
}
order.push(equation);
}
if order.len() < equations.len() {
return Err(invalid(
"its contexts cannot be told apart: every context must stand alone in \
some zone, or beside contexts that do"
.to_owned(),
));
}
Ok(order)
}
}