use super::derivation::Kind;
use super::{Calculus, Derivation, NodeId, Step, TermId};
use crate::hash::{HashMap, HashSet};
use crate::limits::Refusal;
use crate::{Error, Limits};
use std::cmp::Reverse;
use std::collections::BinaryHeap;
use std::fmt::{self, Display, Formatter, Write};
const LINE: u64 = 256;
const MEMBER: u64 = 64;
const BAR: u64 = 8;
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq, serde::Serialize, serde::Deserialize)]
#[serde(default, deny_unknown_fields)]
pub struct FitchOptions {
pub hypothesis: String,
pub open: String,
}
impl Default for FitchOptions {
fn default() -> Self {
Self {
hypothesis: String::new(),
open: "?".to_owned(),
}
}
}
impl FitchOptions {
#[must_use]
pub fn with_hypothesis(self, hypothesis: impl Into<String>) -> Self {
Self {
hypothesis: hypothesis.into(),
..self
}
}
#[must_use]
pub fn with_open(self, open: impl Into<String>) -> Self {
Self {
open: open.into(),
..self
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Cite {
Line(u32),
Range(u32, u32),
}
#[derive(Clone, Debug)]
pub(crate) struct Line {
pub(crate) node: NodeId,
pub(crate) depth: u32,
pub(crate) cites: Vec<Cite>,
pub(crate) opens: u32,
pub(crate) closes: u32,
pub(crate) closes_hypotheses: bool,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Block {
pub(crate) depth: u32,
pub(crate) first: u32,
pub(crate) hypotheses: u32,
pub(crate) last: u32,
}
#[derive(Clone, Debug)]
pub struct Fitch<'a> {
calculus: &'a Calculus,
derivation: &'a Derivation,
options: FitchOptions,
lines: Vec<Line>,
#[cfg_attr(
not(feature = "svg"),
expect(
dead_code,
reason = "only the SVG drawing reads the blocks: the other writers read the lines' flags"
)
)]
blocks: Vec<Block>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
enum Unit {
Node(u32),
Block(u32),
}
impl<'a> Fitch<'a> {
pub fn new(
calculus: &'a Calculus,
derivation: &'a Derivation,
options: &FitchOptions,
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 = |reason: String| Error::NotFitch { reason };
let count = derivation.len();
let parents = derivation.scope_parents();
let id = |node: u32| derivation.at(node as usize).id();
let scope = |node: u32| derivation.at(node as usize).scope().index() as u32;
let depth = depths(parents);
let mut firsts = vec![u32::MAX; parents.len()];
for node in (0..count as u32).rev() {
firsts[scope(node) as usize] = node;
}
let first_node = |scope: u32| firsts[scope as usize];
let mut shown: Vec<u32> = (0..count as u32).collect();
let mut uses: HashMap<(u32, Vec<&[TermId]>), u32> = HashMap::default();
for (node, at) in derivation.nodes().enumerate() {
if derivation.nodes[node].kind == Kind::Hypothesis {
let sequent = (0..derivation.zones()).map(|z| at.zone(z)).collect();
shown[node] = *uses
.entry((scope(node as u32), sequent))
.or_insert(node as u32);
}
}
let mut estimate = 0u64;
for node in derivation.nodes() {
let members = (0..derivation.zones()).map(|z| node.zone(z).len() as u64);
let bars = u64::from(depth[node.scope().index()]) + 1;
estimate = estimate
.saturating_add(LINE)
.saturating_add(MEMBER.saturating_mul(members.sum()))
.saturating_add(BAR.saturating_mul(bars));
}
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(Error::Refused(Refusal::Output {
what: "Fitch proof",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
}));
}
let mut climb = Climb {
parents,
depth: &depth,
work: 0,
limit: limits.work,
};
let root_index = shown[root.id().index()];
if scope(root_index) != 0 {
return Err(refused(
"the last node lies inside a subproof, not in the main proof".to_owned(),
));
}
let mut parts: Vec<Vec<Unit>> = vec![Vec::new(); parents.len()];
let mut seen: HashSet<Unit> = HashSet::default();
for node in (0..count as u32).filter(|&node| shown[node as usize] == node) {
let mut level = scope(node);
let mut part = Unit::Node(node);
loop {
if !seen.insert(part) {
break;
}
parts[level as usize].push(part);
if level == 0 {
break;
}
climb.tick()?;
part = Unit::Block(level);
level = parents[level as usize];
}
}
let mut waits: HashMap<Unit, Vec<Unit>> = HashMap::default();
let mut edges: HashSet<(Unit, Unit)> = HashSet::default();
let mut owed: HashMap<Unit, u32> = HashMap::default();
let mut concludes: Vec<Option<u32>> = vec![None; parents.len()];
for node in 0..count as u32 {
let at = scope(node);
for &premise in derivation.at(node as usize).premises() {
let premise = shown[premise.index()];
let there = scope(premise);
let (level, from) = if climb.inside(at, there)?.is_some() || at == there {
(there, Unit::Node(premise))
} else if there != 0
&& (parents[there as usize] == at
|| climb.inside(at, parents[there as usize])?.is_some())
{
match concludes[there as usize] {
Some(other) if other != premise => {
return Err(refused(format!(
"two rules take the subproof of node {} with different \
conclusions, nodes {} and {}",
first_node(there),
other,
premise
)));
}
_ => concludes[there as usize] = Some(premise),
}
(parents[there as usize], Unit::Block(there))
} else {
return Err(refused(format!(
"node {node} cites node {premise}, which lies in a subproof out of \
its reach"
)));
};
let Some(to) = climb.unit(scope(node), node, level)? else {
return Err(refused(format!(
"node {node} cites node {premise}, which lies in a subproof out of \
its reach"
)));
};
if to != from && edges.insert((from, to)) {
waits.entry(from).or_default().push(to);
*owed.entry(to).or_default() += 1;
}
}
}
let key = |part: Unit| match part {
Unit::Node(node) => node,
Unit::Block(s) => first_node(s),
};
let hypothesis = |part: Unit| matches!(part, Unit::Node(n) if derivation.nodes[n as usize].kind == Kind::Hypothesis);
let mut orders: Vec<Vec<Unit>> = vec![Vec::new(); parents.len()];
for (level, list) in parts.iter().enumerate() {
if list.is_empty() {
continue;
}
let last = if level == 0 {
Some(Unit::Node(root_index))
} else {
concludes[level].map(Unit::Node)
}
.filter(|&part| !hypothesis(part));
let mut ready: BinaryHeap<Reverse<(bool, u32, Unit)>> = BinaryHeap::new();
for &part in list {
if owed.get(&part).copied().unwrap_or(0) == 0 && Some(part) != last {
ready.push(Reverse((!hypothesis(part), key(part), part)));
}
}
let order = &mut orders[level];
while let Some(Reverse((_, _, part))) = ready.pop() {
climb.tick()?;
order.push(part);
for &next in waits.get(&part).map_or(&[][..], Vec::as_slice) {
let left = owed.entry(next).or_default();
*left -= 1;
if *left == 0 && Some(next) != last {
ready.push(Reverse((!hypothesis(next), key(next), next)));
}
}
}
if let Some(last) = last
&& owed.get(&last).copied().unwrap_or(0) == 0
&& !order.contains(&last)
{
order.push(last);
}
if order.len() != list.len() {
let what = if level == 0 {
"the main proof".to_owned()
} else {
format!("the subproof of node {}", first_node(level as u32))
};
return Err(refused(format!(
"no order of {what} puts every line after the lines it cites and the \
line it concludes last: a line inside it uses its conclusion, or it \
uses a subproof that uses it"
)));
}
let opening = order.iter().take_while(|&&part| hypothesis(part)).count();
if order.iter().skip(opening).any(|&part| hypothesis(part)) {
return Err(refused(format!(
"a hypothesis of {} cannot stand among its first lines",
if level == 0 {
"the main proof".to_owned()
} else {
format!("the subproof of node {}", first_node(level as u32))
}
)));
}
}
let mut lines: Vec<Line> = Vec::with_capacity(count);
let mut blocks: Vec<Block> = Vec::new();
let mut number = vec![0u32; count];
let mut spans = vec![(0u32, 0u32); parents.len()];
let mut stack: Vec<(u32, usize, usize)> = vec![(0, 0, 0)];
blocks.push(Block {
depth: 0,
first: 0,
hypotheses: 0,
last: 0,
});
while let Some(&mut (level, ref mut at, block)) = stack.last_mut() {
let order = &orders[level as usize];
let Some(&part) = order.get(*at) else {
let last = lines.len() as u32 - 1;
blocks[block].last = last;
spans[level as usize] = (blocks[block].first, last);
stack.pop();
continue;
};
*at += 1;
match part {
Unit::Node(node) => {
if hypothesis(part) {
blocks[block].hypotheses += 1;
}
number[node as usize] = lines.len() as u32 + 1;
lines.push(Line {
node: id(node),
depth: depth[level as usize],
cites: Vec::new(),
opens: 0,
closes: 0,
closes_hypotheses: false,
});
}
Unit::Block(inner) => {
blocks.push(Block {
depth: depth[inner as usize],
first: lines.len() as u32,
hypotheses: 0,
last: lines.len() as u32,
});
stack.push((inner, 0, blocks.len() - 1));
}
}
}
for block in &blocks {
if block.depth > 0 {
lines[block.first as usize].opens += 1;
lines[block.last as usize].closes += 1;
}
if block.hypotheses > 0 {
lines[(block.first + block.hypotheses - 1) as usize].closes_hypotheses = true;
}
}
for line in &mut lines {
let at = scope(line.node.index() as u32);
for &premise in derivation.node(line.node).premises() {
let there = scope(premise.index() as u32);
let cite = if there == at || climb.inside(at, there)?.is_some() {
Cite::Line(number[shown[premise.index()] as usize])
} else {
let (first, last) = spans[there as usize];
Cite::Range(first + 1, last + 1)
};
line.cites.push(cite);
}
}
Ok(Self {
calculus,
derivation,
options: options.clone(),
lines,
blocks,
})
}
pub fn len(&self) -> usize {
self.lines.len()
}
pub fn is_empty(&self) -> bool {
self.lines.is_empty()
}
pub fn nodes(&self) -> impl ExactSizeIterator<Item = NodeId> + '_ {
self.lines.iter().map(|line| line.node)
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
pub(crate) fn lines(&self) -> &[Line] {
&self.lines
}
#[cfg(feature = "svg")]
pub(crate) fn blocks(&self) -> &[Block] {
&self.blocks
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
pub(crate) fn rule(&self, line: &Line) -> Option<String> {
match self.derivation.node(line.node).step() {
Step::Rule(name) => Some(super::draw::markup(name)),
Step::Hypothesis | Step::Open => None,
}
}
pub(crate) fn note(&self, line: &Line) -> &str {
match self.derivation.node(line.node).step() {
Step::Rule(_) => "",
Step::Hypothesis => &self.options.hypothesis,
Step::Open => &self.options.open,
}
}
#[cfg(any(feature = "latex", feature = "svg"))]
pub(crate) fn is_hypothesis(&self, line: &Line) -> bool {
self.derivation.node(line.node).step() == Step::Hypothesis
}
pub(crate) fn write_cites(line: &Line, range: &str, out: &mut impl Write) -> fmt::Result {
for (k, cite) in line.cites.iter().enumerate() {
if k > 0 {
out.write_str(", ")?;
}
match *cite {
Cite::Line(n) => write!(out, "{n}")?,
Cite::Range(a, b) => write!(out, "{a}{range}{b}")?,
}
}
Ok(())
}
#[cfg(any(feature = "latex", feature = "typst", feature = "svg"))]
pub(crate) fn formula(
&self,
line: &Line,
notation: &crate::linear::sequents::notation::Notation,
out: &mut String,
) {
let spelling = super::print::Spelling::of(notation, false, false);
self.calculus
.write_sequent_in(self.derivation, line.node, spelling, out);
}
pub(crate) fn plain_formula(&self, line: &Line, out: &mut impl Write) -> fmt::Result {
write!(
out,
"{}",
self.calculus.show_sequent(self.derivation, line.node)
)
}
#[cfg(feature = "svg")]
pub(crate) fn plain_rule(&self, line: &Line, out: &mut impl Write) -> fmt::Result {
match self.derivation.node(line.node).step() {
Step::Rule(name) => out.write_str(name),
Step::Hypothesis | Step::Open => Ok(()),
}
}
pub(crate) fn plain_justification(&self, line: &Line, out: &mut impl Write) -> fmt::Result {
match self.derivation.node(line.node).step() {
Step::Rule(name) => {
out.write_str(name)?;
if !line.cites.is_empty() {
out.write_char(' ')?;
Self::write_cites(line, "–", out)?;
}
Ok(())
}
Step::Hypothesis | Step::Open => out.write_str(self.note(line)),
}
}
}
pub(super) fn depths(parents: &[u32]) -> Vec<u32> {
let mut depth = vec![0u32; parents.len()];
for s in 1..parents.len() {
depth[s] = depth[parents[s] as usize] + 1;
}
depth
}
pub(super) struct Climb<'d> {
pub(super) parents: &'d [u32],
pub(super) depth: &'d [u32],
pub(super) work: u64,
pub(super) limit: Option<u64>,
}
impl Climb<'_> {
pub(super) fn tick(&mut self) -> Result<(), Error> {
self.work = self.work.saturating_add(1);
match self.limit {
Some(limit) if self.work > limit => Err(Error::Refused(Refusal::Work { limit })),
_ => Ok(()),
}
}
pub(super) fn inside(&mut self, mut inner: u32, level: u32) -> Result<Option<u32>, Error> {
let below = self.depth[level as usize] + 1;
while self.depth[inner as usize] > below {
self.tick()?;
inner = self.parents[inner as usize];
}
Ok(
(self.depth[inner as usize] == below && self.parents[inner as usize] == level)
.then_some(inner),
)
}
fn unit(&mut self, at: u32, node: u32, level: u32) -> Result<Option<Unit>, Error> {
if at == level {
return Ok(Some(Unit::Node(node)));
}
Ok(self.inside(at, level)?.map(Unit::Block))
}
}
impl Display for Fitch<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
let width = self.lines.len().to_string().len();
let mut heads = Vec::with_capacity(self.lines.len());
for (index, line) in self.lines.iter().enumerate() {
let mut head = format!("{:>width$} ", index + 1);
for _ in 0..=line.depth {
head.push_str("│ ");
}
self.plain_formula(line, &mut head)?;
heads.push(head);
}
let column = heads.iter().map(|h| h.chars().count()).max().unwrap_or(0);
for (index, line) in self.lines.iter().enumerate() {
let head = &heads[index];
let mut justification = String::new();
self.plain_justification(line, &mut justification)?;
if justification.is_empty() {
f.write_str(head)?;
} else {
let pad = column - head.chars().count();
write!(f, "{head}{:pad$} {justification}", "")?;
}
f.write_char('\n')?;
if line.closes_hypotheses {
write!(f, "{:width$} ", "")?;
for _ in 0..line.depth {
f.write_str("│ ")?;
}
f.write_str("├───\n")?;
}
}
Ok(())
}
}