use super::derivation::Kind;
use super::{Calculus, Derivation, NodeId, Step};
use crate::hash::HashMap;
use crate::linear::InfId;
use crate::linear::proofs::Labels;
use crate::linear::proofs::style::{Drawn, LITERAL, RAISED, superscript};
use crate::{Error, Limits};
use std::fmt::Write;
const INFERENCE: u64 = 256;
const MEMBER: u64 = 64;
#[derive(Clone, Debug)]
pub struct Drawing<'a> {
calculus: &'a Calculus,
derivation: &'a Derivation,
nodes: Vec<NodeId>,
ends: Vec<u32>,
premises: Vec<InfId>,
labels: Vec<String>,
rules: Vec<u32>,
marks: HashMap<u32, u32>,
}
impl<'a> Drawing<'a> {
pub fn new(
calculus: &'a Calculus,
derivation: &'a Derivation,
limits: &Limits,
) -> Result<Self, Error> {
let invalid = |reason: String| Error::InvalidDerivation {
calculus: calculus.name().into(),
reason,
};
if derivation.zones() != calculus.zones.len() {
return Err(invalid(format!(
"its sequents have {} zones, the calculus's {}",
derivation.zones(),
calculus.zones.len()
)));
}
let Some(root) = derivation.root() else {
return Err(invalid("it has no node".to_owned()));
};
let refused = |estimate, limit| {
Error::Refused(crate::limits::Refusal::Output {
what: "drawing",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
})
};
enum Visit {
Enter(NodeId),
Exit(NodeId),
}
let (mut nodes, mut ends, mut premises) = (Vec::new(), Vec::new(), Vec::new());
let mut made: Vec<InfId> = Vec::new();
let mut stack = vec![Visit::Enter(root.id())];
let mut estimate = 0u64;
while let Some(visit) = stack.pop() {
match visit {
Visit::Enter(node) => {
let at = derivation.node(node);
let members = (0..derivation.zones()).map(|z| at.zone(z).len() as u64);
estimate = estimate
.saturating_add(INFERENCE)
.saturating_add(MEMBER.saturating_mul(members.sum()));
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(refused(estimate, limit));
}
stack.push(Visit::Exit(node));
stack.extend(at.premises().iter().rev().map(|&p| Visit::Enter(p)));
}
Visit::Exit(node) => {
let count = derivation.node(node).premises().len();
premises.extend(made.drain(made.len() - count..));
let id = InfId::new(
u32::try_from(nodes.len())
.map_err(|_| refused(estimate, u64::from(u32::MAX)))?,
);
nodes.push(node);
ends.push(
u32::try_from(premises.len())
.map_err(|_| refused(estimate, u64::from(u32::MAX)))?,
);
made.push(id);
}
}
}
let mut labels: Vec<String> = derivation
.rules
.iter()
.map(|name| markup(name))
.chain(std::iter::once(String::new()))
.collect();
let hypothesis = derivation.rules.len() as u32;
let scope = |node: NodeId| derivation.node(node).scope().index() as u32;
let mut marks: HashMap<u32, u32> = HashMap::default();
let mut marked: HashMap<(u32, Vec<u32>), u32> = HashMap::default();
let mut rules = Vec::with_capacity(nodes.len());
let parents = derivation.scope_parents();
let depth = super::fitch::depths(parents);
let mut climb = super::fitch::Climb {
parents,
depth: &depth,
work: 0,
limit: limits.work,
};
for &node in &nodes {
let rule = match derivation.nodes[node.index()].kind {
Kind::Rule(rule) => rule,
Kind::Hypothesis => hypothesis,
Kind::Open => u32::MAX,
};
let at = derivation.node(node);
let mut own = Vec::new();
let outer = scope(node);
for &premise in at.premises() {
let inner = scope(premise);
if inner == outer || climb.inside(outer, inner)?.is_some() {
continue;
}
let next = marks.len() as u32 + 1;
own.push(*marks.entry(inner).or_insert(next));
}
if own.is_empty() || rule == u32::MAX {
rules.push(rule);
continue;
}
let index = *marked.entry((rule, own.clone())).or_insert_with(|| {
let numbers: Vec<String> = own.iter().map(u32::to_string).collect();
labels.push(format!(
"{}{RAISED}{{{}}}",
labels[rule as usize],
numbers.join(",")
));
labels.len() as u32 - 1
});
rules.push(index);
}
let open = labels.len() as u32;
for rule in &mut rules {
if *rule == u32::MAX {
*rule = open;
}
}
Ok(Self {
calculus,
derivation,
nodes,
ends,
premises,
labels,
rules,
marks,
})
}
fn node(&self, id: InfId) -> NodeId {
self.nodes[id.index()]
}
pub fn nodes(&self) -> impl ExactSizeIterator<Item = NodeId> + '_ {
self.nodes.iter().copied()
}
fn mark(&self, id: InfId) -> Option<u32> {
let node = self.derivation.node(self.node(id));
if node.step() != Step::Hypothesis {
return None;
}
self.marks.get(&(node.scope().index() as u32)).copied()
}
}
pub(super) fn markup(name: &str) -> String {
let mut out = String::new();
for c in name.chars() {
match c {
'₀'..='₉' => {
out.push('_');
out.extend(char::from_digit(u32::from(c) - u32::from('₀'), 10));
}
'_' | '*' => {
out.push(LITERAL);
out.push(c);
}
c => out.push(c),
}
}
out
}
impl Drawn for Drawing<'_> {
fn rules(&self) -> usize {
self.labels.len() + 1
}
fn open(&self) -> Option<usize> {
Some(self.labels.len())
}
fn markup<'a>(&'a self, rule: usize, labels: &'a Labels) -> Option<&'a str> {
match labels {
Labels::Off => None,
Labels::Upright | Labels::Subscript | Labels::Table(_) => {
self.labels.get(rule).map(String::as_str)
}
}
}
fn len(&self) -> usize {
self.nodes.len()
}
fn root(&self) -> InfId {
InfId::new(u32::try_from(self.nodes.len() - 1).unwrap_or(u32::MAX))
}
fn premises(&self, id: InfId) -> &[InfId] {
let start = match id.index() {
0 => 0,
index => self.ends[index - 1] as usize,
};
&self.premises[start..self.ends[id.index()] as usize]
}
fn rule(&self, id: InfId) -> usize {
self.rules[id.index()] as usize
}
fn bare(&self) -> Option<usize> {
Some(self.derivation.rules.len())
}
fn name(&self, id: InfId) -> &str {
match self.derivation.node(self.node(id)).step() {
Step::Rule(name) => name,
Step::Hypothesis => "hypothesis",
Step::Open => "open",
}
}
fn times(&self, _: InfId) -> u32 {
1
}
fn write_sequent(&self, out: &mut impl Write, id: InfId) -> std::fmt::Result {
let shown = self.calculus.show_sequent(self.derivation, self.node(id));
match self.mark(id) {
None => write!(out, "{shown}"),
Some(mark) => {
write!(out, "[{shown}]")?;
mark.to_string()
.chars()
.try_for_each(|c| out.write_char(superscript(c)))
}
}
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
fn sequent(
&self,
out: &mut String,
notation: &crate::linear::sequents::notation::Notation,
id: InfId,
aligned: bool,
marks: bool,
) {
let spelling = super::print::Spelling::of(notation, aligned, marks);
let mark = self.mark(id);
if mark.is_some() {
out.push('[');
}
self.calculus
.write_sequent_in(self.derivation, self.node(id), spelling, out);
if let Some(mark) = mark {
out.push(']');
let _ = notation.atom.superscript(out, &mark.to_string());
}
}
#[cfg(feature = "svg")]
fn positions(&self, id: InfId) -> Vec<usize> {
let node = self.derivation.node(self.node(id));
let members = (0..self.derivation.zones()).map(|z| node.zone(z).len());
(0..members.sum()).collect()
}
}