use crate::hash::HashMap;
use crate::linear::occurrences::instances::Framing;
use crate::linear::occurrences::written::{self, Written};
use crate::linear::occurrences::{Forest, IllConnective, Member, OccId, Reading, Side};
use crate::linear::sequents::{Atom, Kind, Sequent, Stop, Stops, Term, TermId};
use crate::ordinary::{Formulas, NodeId, Symbols};
use std::borrow::Cow;
use std::fmt::{Result as FmtResult, Write};
pub(crate) struct Notation {
pub(crate) tensor: &'static str,
pub(crate) par: &'static str,
pub(crate) with: &'static str,
pub(crate) plus: &'static str,
pub(crate) lollipop: &'static str,
pub(crate) under: &'static str,
pub(crate) over: &'static str,
pub(crate) bang: &'static str,
pub(crate) quest: &'static str,
pub(crate) one: &'static str,
pub(crate) bot: &'static str,
pub(crate) top: &'static str,
pub(crate) zero: &'static str,
pub(crate) dual_prefix: &'static str,
pub(crate) dual: &'static str,
pub(crate) turnstile: &'static str,
pub(crate) align: &'static str,
pub(crate) atom: Atoms,
pub(crate) forall: &'static str,
pub(crate) exists: &'static str,
pub(crate) dot: &'static str,
pub(crate) ordinary: Symbols,
}
pub(crate) const TEXT: Notation = Notation {
tensor: "⊗",
par: "⅋",
with: "&",
plus: "⊕",
lollipop: "⊸",
under: "\\",
over: "/",
bang: "!",
quest: "?",
one: "1",
bot: "⊥",
top: "⊤",
zero: "0",
dual_prefix: "~",
dual: "",
turnstile: "⊢",
align: "",
atom: Atoms::Plain,
forall: "∀",
exists: "∃",
dot: ". ",
ordinary: Symbols::UNICODE,
};
#[derive(Clone, Copy, Debug)]
pub(crate) enum Atoms {
Plain,
#[cfg(feature = "latex")]
Latex,
#[cfg(feature = "typst")]
Typst,
#[cfg(feature = "svg")]
Italic,
}
impl Atoms {
pub(crate) fn write<W: Write + ?Sized>(self, out: &mut W, name: &str) -> FmtResult {
match self {
Self::Plain => out.write_str(name),
#[cfg(feature = "latex")]
Self::Latex => crate::export::latex::atom(out, name),
#[cfg(feature = "typst")]
Self::Typst => crate::export::typst::atom(out, name),
#[cfg(feature = "svg")]
Self::Italic => crate::export::svg::italic(out, name),
}
}
}
#[derive(Default)]
pub(crate) struct Scope<'a> {
names: Vec<Cow<'a, str>>,
open: HashMap<Cow<'a, str>, u32>,
symbols: Option<std::collections::HashSet<&'a str>>,
frame: Vec<String>,
}
struct Sides<'r, 'f> {
reading: Option<&'r Reading<'r>>,
framing: &'f Framing<'f>,
marks: (&'static str, &'static str),
}
struct Capped {
text: String,
left: usize,
}
impl Write for Capped {
fn write_str(&mut self, s: &str) -> FmtResult {
let n = s.chars().count();
if n <= self.left {
self.left -= n;
self.text.push_str(s);
return Ok(());
}
self.text.extend(s.chars().take(self.left));
self.left = 0;
Err(std::fmt::Error)
}
}
struct Apart<'w, W: ?Sized>(&'w mut W);
impl<W: Write + ?Sized> Write for Apart<'_, W> {
fn write_str(&mut self, s: &str) -> FmtResult {
self.0.write_str(s)
}
fn write_char(&mut self, c: char) -> FmtResult {
self.0.write_char(c)
}
}
enum Bound<'s> {
Name(&'s str),
Term(&'s str),
}
impl<'a> Scope<'a> {
#[cold]
#[inline(never)]
fn enter(&mut self, sequent: &'a Sequent, name: &'a str) -> &str {
let symbols = self
.symbols
.get_or_insert_with(|| sequent.fo.symbols.iter().map(|(s, _)| s.as_str()).collect());
let clashes = |open: &HashMap<Cow<'a, str>, u32>, candidate: &str| {
symbols.contains(candidate) || open.contains_key(candidate)
};
let mut written = Cow::Borrowed(name);
let mut n = 0u32;
while clashes(&self.open, &written) {
n += 1;
written = Cow::Owned(format!("{name}_{n}"));
}
*self.open.entry(written.clone()).or_insert(0) += 1;
self.names.push(written);
self.names.last().expect("just pushed")
}
#[cold]
#[inline(never)]
fn exit(&mut self) {
if let Some(name) = self.names.pop()
&& let Some(count) = self.open.get_mut(&name)
{
*count -= 1;
if *count == 0 {
self.open.remove(&name);
}
}
}
fn name(&self, index: u32) -> Option<Bound<'_>> {
match self.names.len().checked_sub(index as usize + 1) {
Some(at) => Some(Bound::Name(self.names[at].as_ref())),
None => self
.frame
.get(index as usize - self.names.len())
.map(|t| Bound::Term(t)),
}
}
pub(crate) fn framed(frame: Vec<String>, taken: impl Iterator<Item = &'a str>) -> Self {
let mut open = HashMap::default();
for name in taken {
open.insert(Cow::Borrowed(name), 1);
}
Self {
names: Vec::new(),
open,
symbols: None,
frame,
}
}
}
fn bracketed(kind: Kind) -> bool {
kind.arity() == 2 || kind.is_binder()
}
type Slot<'a> = std::mem::ManuallyDrop<Option<Box<Scope<'a>>>>;
#[inline(always)]
fn close(slot: Slot<'_>) {
if let Some(scope) = std::mem::ManuallyDrop::into_inner(slot) {
drop(scope);
}
}
impl Notation {
#[inline(always)]
pub(crate) fn write_atom<W: Write + ?Sized>(
&self,
out: &mut W,
sequent: &Sequent,
atom: Atom,
predicates: bool,
scope: Option<&Scope<'_>>,
) -> FmtResult {
if predicates {
self.write_predicate(out, sequent, atom, scope)
} else {
self.atom.write(out, sequent.atom_name(atom))
}
}
#[cold]
#[inline(never)]
fn write_predicate<W: Write + ?Sized>(
&self,
out: &mut W,
sequent: &Sequent,
atom: Atom,
scope: Option<&Scope<'_>>,
) -> FmtResult {
let (symbol, args) = sequent.fo.atoms[atom.index()];
let fo = &sequent.fo;
self.atom.write(out, &fo.symbols[symbol.index()].0)?;
let list = fo.list(args);
if list.is_empty() {
return Ok(());
}
out.write_char('(')?;
for (i, &t) in list.iter().enumerate() {
if i > 0 {
out.write_str(", ")?;
}
fo.write(
out,
t,
&mut |out, name| self.atom.write(out, name),
&mut |out, index| match scope.and_then(|scope| scope.name(index)) {
Some(Bound::Name(name)) => self.atom.write(out, name),
Some(Bound::Term(term)) => out.write_str(term),
None => write!(out, "#{index}"),
},
)?;
}
out.write_char(')')
}
#[cold]
#[inline(never)]
fn binder<'a, W: Write + ?Sized>(
&self,
out: &mut W,
sequent: &'a Sequent,
term: TermId,
kind: Kind,
scope: &mut Option<Box<Scope<'a>>>,
) -> FmtResult {
out.write_str(if kind == Kind::Forall {
self.forall
} else {
self.exists
})?;
let scope = scope.get_or_insert_with(Box::default);
let name = scope.enter(sequent, sequent.binder_name(term).unwrap_or("x"));
self.atom.write(out, name)?;
out.write_str(self.dot)
}
pub(crate) fn term<W: Write>(
&self,
out: &mut W,
sequent: &Sequent,
id: TermId,
brackets: bool,
) -> FmtResult {
let mut slot: Slot<'_> = std::mem::ManuallyDrop::new(None);
let written = self.term_in(out, sequent, id, brackets, &mut slot);
close(slot);
written
}
#[cold]
#[inline(never)]
pub(crate) fn instance<W: Write>(
&self,
out: &mut W,
forest: &Forest,
reading: Option<&Reading>,
framing: &Framing<'_>,
member: Member,
cap: Option<usize>,
) -> FmtResult {
let (o, mut slot) = self.framed_scope(framing, member, cap)?;
let mut out = Apart(out);
let written = match reading {
Some(reading) => self.ill_in(&mut out, reading, o, false, &mut slot),
None => self.term_in(&mut out, forest.sequent(), forest.term(o), false, &mut slot),
};
close(slot);
written
}
#[cold]
#[inline(never)]
fn written_instance<W: Write>(
&self,
out: &mut W,
forest: &Forest,
writing: &[Written],
framing: &Framing<'_>,
member: Member,
negated: bool,
) -> FmtResult {
let (o, mut slot) = self.framed_scope(framing, member, None)?;
let written = self.written_in(&mut Apart(out), forest, writing, o, negated, &mut slot);
close(slot);
written
}
fn framed_scope<'f>(
&self,
framing: &'f Framing<'_>,
member: Member,
cap: Option<usize>,
) -> Result<(OccId, Slot<'f>), std::fmt::Error> {
let (o, frame) = framing
.table
.instance(member)
.expect("a member of the proof's table");
let frame = framing
.table
.frame_terms(frame)
.into_iter()
.map(|t| {
let mut text = Capped {
text: String::new(),
left: cap.unwrap_or(usize::MAX),
};
match framing.write_term(&mut text, t, &mut |out, name| self.atom.write(out, name))
{
Ok(()) => Ok(text.text),
Err(_) if text.left == 0 => Ok(text.text + "…"),
Err(e) => Err(e),
}
})
.collect::<Result<Vec<String>, _>>()?;
let scope = Scope::framed(frame, framing.names());
Ok((o, std::mem::ManuallyDrop::new(Some(Box::new(scope)))))
}
#[inline(always)]
fn term_in<'a, W: Write>(
&self,
out: &mut W,
sequent: &'a Sequent,
id: TermId,
brackets: bool,
scope: &mut Option<Box<Scope<'a>>>,
) -> FmtResult {
use Term::*;
debug_assert!(id.index() < sequent.terms.len());
let predicates = !sequent.fo.atoms.is_empty();
for visit in Stops::new(id, brackets, |k| sequent.term(k).operands()) {
match visit {
Stop::Enter(k, nested) => {
let term = sequent.term(k);
debug_assert!(term.subterms().all(|sub| sub < k));
match term {
Atom(a) => {
self.write_atom(out, sequent, a, predicates, scope.as_deref())?
}
DualAtom(a) => {
if !self.dual_prefix.is_empty() {
out.write_str(self.dual_prefix)?;
}
self.write_atom(out, sequent, a, predicates, scope.as_deref())?;
out.write_str(self.dual)?;
}
One => out.write_str(self.one)?,
Bot => out.write_str(self.bot)?,
Top => out.write_str(self.top)?,
Zero => out.write_str(self.zero)?,
Tensor(..) | Par(..) | With(..) | Plus(..) if nested => {
out.write_char('(')?;
}
Tensor(..) | Par(..) | With(..) | Plus(..) => {}
Bang(_) => out.write_str(self.bang)?,
Quest(_) => out.write_str(self.quest)?,
Forall(_) | Exists(_) => {
if nested {
out.write_char('(')?;
}
self.binder(out, sequent, k, term.kind(), scope)?;
}
}
}
Stop::Between(k) => {
out.write_char(' ')?;
out.write_str(match sequent.term(k) {
Tensor(..) => self.tensor,
Par(..) => self.par,
With(..) => self.with,
Atom(_) | DualAtom(_) | One | Bot | Top | Zero | Plus(..) | Bang(_)
| Quest(_) | Forall(_) | Exists(_) => self.plus,
})?;
out.write_char(' ')?;
}
Stop::Exit(k, nested) => {
let kind = sequent.term(k).kind();
if kind.is_binder()
&& let Some(scope) = scope
{
scope.exit();
}
if nested && bracketed(kind) {
out.write_char(')')?;
}
}
}
}
Ok(())
}
pub(crate) fn ill<W: Write>(
&self,
out: &mut W,
reading: &Reading,
o: OccId,
brackets: bool,
) -> FmtResult {
let mut slot: Slot<'_> = std::mem::ManuallyDrop::new(None);
let written = self.ill_in(out, reading, o, brackets, &mut slot);
close(slot);
written
}
#[inline(always)]
fn ill_in<'a, W: Write>(
&self,
out: &mut W,
reading: &'a Reading,
o: OccId,
brackets: bool,
scope: &mut Option<Box<Scope<'a>>>,
) -> FmtResult {
use IllConnective as C;
let forest = reading.forest();
let sequent = forest.sequent();
let predicates = !sequent.fo.atoms.is_empty();
for visit in Stops::new(o, brackets, |o| reading.operands(o)) {
match visit {
Stop::Enter(o, nested) => match reading.connective(o) {
C::Atom => {
let atom = forest.atom(o).expect("a literal has an atom");
self.write_atom(out, sequent, atom, predicates, scope.as_deref())?;
}
C::One => out.write_str(self.one)?,
C::Top => out.write_str(self.top)?,
C::Zero => out.write_str(self.zero)?,
C::Tensor | C::With | C::Plus | C::Lollipop | C::Under | C::Over if nested => {
out.write_char('(')?;
}
C::Tensor | C::With | C::Plus | C::Lollipop | C::Under | C::Over => {}
C::Bang => out.write_str(self.bang)?,
connective @ (C::Forall | C::Exists) => {
if nested {
out.write_char('(')?;
}
let kind = if connective == C::Forall {
Kind::Forall
} else {
Kind::Exists
};
self.binder(out, sequent, forest.term(o), kind, scope)?;
}
},
Stop::Between(o) => {
out.write_char(' ')?;
out.write_str(match reading.connective(o) {
C::Tensor => self.tensor,
C::Lollipop => self.lollipop,
C::Under => self.under,
C::Over => self.over,
C::With => self.with,
C::Atom
| C::One
| C::Top
| C::Zero
| C::Bang
| C::Plus
| C::Forall
| C::Exists => self.plus,
})?;
out.write_char(' ')?;
}
Stop::Exit(o, nested) => {
let kind = forest.kind(o);
if kind.is_binder()
&& let Some(scope) = scope
{
scope.exit();
}
if nested && bracketed(kind) {
out.write_char(')')?;
}
}
}
}
Ok(())
}
pub(crate) fn written<W: Write>(
&self,
out: &mut W,
forest: &Forest,
writing: &[Written],
o: OccId,
negated: bool,
) -> FmtResult {
let mut slot: Slot<'_> = std::mem::ManuallyDrop::new(None);
let written = self.written_in(out, forest, writing, o, negated, &mut slot);
close(slot);
written
}
#[inline(always)]
fn written_in<'a, W: Write>(
&self,
out: &mut W,
forest: &'a Forest,
writing: &[Written],
o: OccId,
negated: bool,
scope: &mut Option<Box<Scope<'a>>>,
) -> FmtResult {
let top = o;
let negation = |k: OccId| {
if k == top {
negated
} else {
written::negated(forest, writing, k)
}
};
let core = |k: OccId| match writing[k.index()].side() {
Side::Output => forest.kind(k),
Side::Input => forest.kind(k).dual(),
};
let postfix = !self.dual.is_empty();
let operands = |k: OccId| (forest.left(k), forest.right(k));
let sequent = forest.sequent();
let predicates = !sequent.fo.atoms.is_empty();
for visit in Stops::new(o, false, operands) {
match visit {
Stop::Enter(k, nested) => {
let negated = negation(k);
if negated {
out.write_str(self.dual_prefix)?;
}
match core(k) {
Kind::Atom => {
let atom = forest.atom(k).expect("a literal has an atom");
self.write_atom(out, sequent, atom, predicates, scope.as_deref())?;
}
Kind::DualAtom => {
let atom = forest.atom(k).expect("a literal has an atom");
out.write_str(self.dual_prefix)?;
self.write_atom(out, sequent, atom, predicates, scope.as_deref())?;
out.write_str(self.dual)?;
}
Kind::One => out.write_str(self.one)?,
Kind::Bot => out.write_str(self.bot)?,
Kind::Top => out.write_str(self.top)?,
Kind::Zero => out.write_str(self.zero)?,
Kind::Tensor | Kind::Par | Kind::With | Kind::Plus => {
if nested || negated {
out.write_char('(')?;
}
}
kind @ (Kind::Bang | Kind::Quest) => {
if negated && postfix {
out.write_char('(')?;
}
out.write_str(if kind == Kind::Bang {
self.bang
} else {
self.quest
})?;
}
kind @ (Kind::Forall | Kind::Exists) => {
if nested || negated {
out.write_char('(')?;
}
self.binder(out, sequent, forest.term(k), kind, scope)?;
}
}
if negated && forest.kind(k).arity() == 0 {
out.write_str(self.dual)?;
}
}
Stop::Between(k) => {
out.write_char(' ')?;
out.write_str(if writing[k.index()].is_implication() {
self.lollipop
} else {
match core(k) {
Kind::Tensor => self.tensor,
Kind::Par => self.par,
Kind::With => self.with,
Kind::Plus
| Kind::Atom
| Kind::DualAtom
| Kind::One
| Kind::Bot
| Kind::Top
| Kind::Zero
| Kind::Bang
| Kind::Quest
| Kind::Forall
| Kind::Exists => self.plus,
}
})?;
out.write_char(' ')?;
}
Stop::Exit(k, nested) => {
let negated = negation(k);
let kind = forest.kind(k);
if kind.is_binder()
&& let Some(scope) = scope
{
scope.exit();
}
let arity = kind.arity();
if (bracketed(kind) && (nested || negated))
|| (arity == 1 && !kind.is_binder() && negated && postfix)
{
out.write_char(')')?;
}
if negated {
out.write_str(self.dual)?;
}
}
}
}
Ok(())
}
#[expect(
clippy::too_many_arguments,
reason = "the sides, the instances and the two switches are what every target passes"
)]
pub(crate) fn classical<W: Write>(
&self,
out: &mut W,
forest: &Forest,
writing: &[Written],
framing: Option<&Framing<'_>>,
left: impl Iterator<Item = (Member, bool)>,
right: impl Iterator<Item = (Member, bool)>,
aligned: bool,
marks: bool,
) -> FmtResult {
let (open, close) = if marks { ("\u{2}", "\u{3}") } else { ("", "") };
let formula = |out: &mut W, m: Member, negated: bool| {
out.write_str(open)?;
match framing {
Some(framing) if m.index() >= forest.len() => {
self.written_instance(out, forest, writing, framing, m, negated)?;
}
_ => self.written(out, forest, writing, m.occ(), negated)?,
}
out.write_str(close)
};
let mut any = false;
for (m, negated) in left {
if any {
out.write_str(", ")?;
}
formula(out, m, negated)?;
any = true;
}
if any {
out.write_char(' ')?;
}
if aligned {
out.write_str(self.align)?;
}
out.write_str(self.turnstile)?;
for (i, (m, negated)) in right.enumerate() {
out.write_str(if i == 0 { " " } else { ", " })?;
formula(out, m, negated)?;
}
Ok(())
}
pub(crate) fn one_sided<W: Write>(&self, out: &mut W, sequent: &Sequent) -> FmtResult {
out.write_str(self.turnstile)?;
for (i, &id) in sequent.roots().iter().enumerate() {
out.write_str(if i == 0 { " " } else { ", " })?;
self.term(out, sequent, id, false)?;
}
Ok(())
}
#[expect(
clippy::too_many_arguments,
reason = "the sides, the instances and the two switches are what every target passes"
)]
pub(crate) fn sequent<W: Write>(
&self,
out: &mut W,
forest: &Forest,
reading: Option<&Reading>,
framing: Option<&Framing<'_>>,
sequent: &[Member],
aligned: bool,
marks: bool,
) -> FmtResult {
let (open, close) = if marks { ("\u{2}", "\u{3}") } else { ("", "") };
if let Some(framing) = framing {
let sides = Sides {
reading,
framing,
marks: (open, close),
};
return self.framed(out, forest, &sides, sequent, aligned);
}
let Some(reading) = reading else {
out.write_str(self.turnstile)?;
for (i, o) in sequent.iter().map(|m| m.occ()).enumerate() {
out.write_str(if i == 0 { " " } else { ", " })?;
out.write_str(open)?;
self.term(out, forest.sequent(), forest.term(o), false)?;
out.write_str(close)?;
}
return Ok(());
};
let output = |o: OccId| reading.position(o) == Side::Output;
let goal = sequent.iter().map(|m| m.occ()).rfind(|&o| output(o));
let hypotheses = reading
.written(sequent)
.map(|p| sequent[p].occ())
.filter(|&o| !output(o));
self.two_sided(out, reading, hypotheses, goal, aligned, (open, close))
}
#[cold]
#[inline(never)]
fn framed<W: Write>(
&self,
out: &mut W,
forest: &Forest,
sides: &Sides<'_, '_>,
sequent: &[Member],
aligned: bool,
) -> FmtResult {
let (open, close) = sides.marks;
let framing = sides.framing;
let Some(reading) = sides.reading else {
out.write_str(self.turnstile)?;
for (i, &m) in sequent.iter().enumerate() {
out.write_str(if i == 0 { " " } else { ", " })?;
out.write_str(open)?;
self.member(out, forest, None, framing, m)?;
out.write_str(close)?;
}
return Ok(());
};
let occ = |m: Member| framing.occurrence(m);
let output = |m: Member| reading.position(occ(m)) == Side::Output;
let goal = sequent.iter().copied().rfind(|&m| output(m));
let mut any = false;
for m in reading
.written_by(sequent, occ)
.map(|p| sequent[p])
.filter(|&m| !output(m))
{
if any {
out.write_str(", ")?;
}
out.write_str(open)?;
self.member(out, forest, Some(reading), framing, m)?;
out.write_str(close)?;
any = true;
}
if any {
out.write_char(' ')?;
}
if aligned {
out.write_str(self.align)?;
}
out.write_str(self.turnstile)?;
if let Some(goal) = goal {
out.write_char(' ')?;
out.write_str(open)?;
self.member(out, forest, Some(reading), framing, goal)?;
out.write_str(close)?;
}
Ok(())
}
fn member<W: Write>(
&self,
out: &mut W,
forest: &Forest,
reading: Option<&Reading>,
framing: &Framing<'_>,
m: Member,
) -> FmtResult {
if m.index() >= forest.len() {
return self.instance(out, forest, reading, framing, m, None);
}
match reading {
Some(reading) => self.ill(out, reading, m.occ(), false),
None => self.term(out, forest.sequent(), forest.term(m.occ()), false),
}
}
pub(crate) fn reading<W: Write>(&self, out: &mut W, reading: &Reading) -> FmtResult {
let goal = Some(reading.goal());
self.two_sided(out, reading, reading.hypotheses(), goal, false, ("", ""))
}
fn two_sided<W: Write>(
&self,
out: &mut W,
reading: &Reading,
hypotheses: impl Iterator<Item = OccId>,
goal: Option<OccId>,
aligned: bool,
marks: (&str, &str),
) -> FmtResult {
let (open, close) = marks;
let mut any = false;
for o in hypotheses {
if any {
out.write_str(", ")?;
}
out.write_str(open)?;
self.ill(out, reading, o, false)?;
out.write_str(close)?;
any = true;
}
if any {
out.write_char(' ')?;
}
if aligned {
out.write_str(self.align)?;
}
out.write_str(self.turnstile)?;
if let Some(goal) = goal {
out.write_char(' ')?;
out.write_str(open)?;
self.ill(out, reading, goal, false)?;
out.write_str(close)?;
}
Ok(())
}
pub(crate) fn ordinary<W: Write>(
&self,
out: &mut W,
formulas: &Formulas,
sides: (&[NodeId], &[NodeId]),
aligned: bool,
marks: bool,
) -> FmtResult {
let (open, close) = if marks { ("\u{2}", "\u{3}") } else { ("", "") };
let formula = |out: &mut W, id: NodeId| {
out.write_str(open)?;
formulas.write(out, id, false, &self.ordinary, |o, a| {
self.atom.write(o, formulas.atom_name(a))
})?;
out.write_str(close)
};
let (left, right) = sides;
for (i, &id) in left.iter().enumerate() {
if i > 0 {
out.write_str(", ")?;
}
formula(out, id)?;
}
if !left.is_empty() {
out.write_char(' ')?;
}
if aligned {
out.write_str(self.align)?;
}
out.write_str(self.turnstile)?;
for (i, &id) in right.iter().enumerate() {
out.write_str(if i == 0 { " " } else { ", " })?;
formula(out, id)?;
}
Ok(())
}
}