use super::{Calculus, Node, Notation, Options, Term, TermId, Type, TypeId, VarId};
use crate::Error;
use crate::limits::{Limits, Phase, Progress, Refusal};
use crate::linear::sequents::notation::Atoms;
use std::fmt::Write;
#[derive(Debug)]
pub(crate) struct Connectives {
tensor: &'static str,
with: &'static str,
plus: &'static str,
lollipop: &'static str,
bang: &'static str,
one: &'static str,
top: &'static str,
zero: &'static str,
}
#[derive(Debug)]
pub(crate) struct Spelling {
lambda: &'static str,
dot: &'static str,
colon: &'static str,
has_type: &'static str,
turnstile: &'static str,
tensor: &'static str,
unit: &'static str,
empty_pair: &'static str,
open_pair: &'static str,
close_pair: &'static str,
arrow: &'static str,
bar: &'static str,
space: &'static str,
apply: &'static str,
keyword: (&'static str, &'static str),
subscript: (&'static str, &'static str),
index: Index,
atom: Atoms,
linear: Connectives,
simple: Connectives,
}
#[derive(Clone, Copy, Debug)]
pub(crate) enum Index {
Subscript,
Digits,
#[cfg(any(feature = "latex", feature = "typst"))]
Marked(&'static str, &'static str),
}
pub(crate) const UNICODE: Spelling = Spelling {
lambda: "λ",
dot: ". ",
colon: ":",
has_type: " : ",
turnstile: " ⊢ ",
tensor: " ⊗ ",
unit: "∗",
empty_pair: "⟨⟩",
open_pair: "⟨",
close_pair: "⟩",
arrow: " → ",
bar: " ‖ ",
space: " ",
apply: " ",
keyword: ("", ""),
subscript: ("_", ""),
index: Index::Subscript,
atom: Atoms::Plain,
linear: Connectives {
tensor: " ⊗ ",
with: " & ",
plus: " ⊕ ",
lollipop: " ⊸ ",
bang: "!",
one: "1",
top: "⊤",
zero: "0",
},
simple: SIMPLE_UNICODE,
};
const SIMPLE_UNICODE: Connectives = Connectives {
tensor: " ⊗ ",
with: " ∧ ",
plus: " ∨ ",
lollipop: " → ",
bang: "!",
one: "1",
top: "⊤",
zero: "⊥",
};
pub(crate) const ASCII: Spelling = Spelling {
lambda: "\\",
dot: ". ",
colon: ":",
has_type: " : ",
turnstile: " |- ",
tensor: " * ",
unit: "()",
empty_pair: "<>",
open_pair: "<",
close_pair: ">",
arrow: " -> ",
bar: " | ",
space: " ",
apply: " ",
keyword: ("", ""),
subscript: ("_", ""),
index: Index::Digits,
atom: Atoms::Plain,
linear: Connectives {
tensor: " * ",
with: " & ",
plus: " + ",
lollipop: " -o ",
bang: "!",
one: "1",
top: "top",
zero: "0",
},
simple: Connectives {
tensor: " * ",
with: " /\\ ",
plus: " \\/ ",
lollipop: " -> ",
bang: "!",
one: "1",
top: "true",
zero: "false",
},
};
#[cfg(feature = "latex")]
pub(crate) const LATEX: Spelling = Spelling {
lambda: r"\lambda ",
dot: r".\,",
colon: r"{:}",
has_type: r" : ",
turnstile: r" \vdash ",
tensor: r" \otimes ",
unit: r"\ast",
empty_pair: r"\langle\rangle",
open_pair: r"\langle ",
close_pair: r"\rangle",
arrow: r" \to ",
bar: r" \parallel ",
space: r"\ ",
apply: r"\ ",
keyword: (r"\mathsf{", "}"),
subscript: ("_{", "}"),
index: Index::Marked("_{", "}"),
atom: Atoms::Latex,
linear: Connectives {
tensor: r" \otimes ",
with: r" \with ",
plus: r" \oplus ",
lollipop: r" \multimap ",
bang: r"\oc ",
one: r"\mathbf{1}",
top: r"\top",
zero: "0",
},
simple: Connectives {
tensor: r" \otimes ",
with: r" \land ",
plus: r" \lor ",
lollipop: r" \to ",
bang: r"\oc ",
one: r"\mathbf{1}",
top: r"\top",
zero: r"\bot",
},
};
#[cfg(feature = "typst")]
pub(crate) const TYPST: Spelling = Spelling {
lambda: "lambda ",
dot: ". ",
colon: ":",
has_type: " : ",
turnstile: " ⊢ ",
tensor: " ⊗ ",
unit: "∗",
empty_pair: "⟨⟩",
open_pair: "⟨",
close_pair: "⟩",
arrow: " → ",
bar: " ‖ ",
space: " space ",
apply: " space ",
keyword: ("\"", "\""),
subscript: ("_(", ")"),
index: Index::Marked("_", ""),
atom: Atoms::Typst,
linear: Connectives {
tensor: " ⊗ ",
with: " \\& ",
plus: " ⊕ ",
lollipop: " ⊸ ",
bang: "!",
one: "bold(1)",
top: "⊤",
zero: "0",
},
simple: SIMPLE_UNICODE,
};
#[cfg(feature = "svg")]
pub(crate) const SVG: Spelling = Spelling {
atom: Atoms::Italic,
..UNICODE
};
impl Notation {
pub(crate) const fn spelling(self) -> &'static Spelling {
match self {
Self::Unicode => &UNICODE,
Self::Ascii => &ASCII,
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Place {
Free,
Operand,
Function,
Argument,
}
const fn bracketed(node: &Node, place: Place) -> bool {
match node {
Node::Lambda { .. }
| Node::LetTensor { .. }
| Node::LetUnit { .. }
| Node::Case { .. }
| Node::Promote { .. }
| Node::Discard { .. }
| Node::Copy { .. } => !matches!(place, Place::Free),
Node::Tensor { .. } => !matches!(place, Place::Free),
Node::Apply { .. } => matches!(place, Place::Argument),
Node::Var { .. }
| Node::Unit
| Node::Pair { .. }
| Node::First { .. }
| Node::Second { .. }
| Node::Left { .. }
| Node::Right { .. }
| Node::True { .. }
| Node::False { .. }
| Node::Derelict { .. } => false,
}
}
#[derive(Clone, Copy, Debug)]
enum Piece {
Text(&'static str),
Keyword(&'static str),
Term(TermId, Place),
Var(VarId),
Type(TypeId, bool),
}
struct Printer<'t> {
term: &'t Term,
spelling: &'t Spelling,
types: bool,
type_lengths: Vec<u64>,
}
impl<'t> Printer<'t> {
fn new(term: &'t Term, spelling: &'t Spelling, types: bool) -> Self {
let mut printer = Self {
term,
spelling,
types,
type_lengths: Vec::with_capacity(term.types.len()),
};
let c = printer.connectives();
let mut lengths: Vec<u64> = Vec::with_capacity(term.types.len());
for ty in &term.types {
let of = |t: TypeId| lengths[t.index()];
let binary = |l: TypeId, op: &str, r: TypeId| {
of(l)
.saturating_add(of(r))
.saturating_add(op.len() as u64 + 2)
};
let length = match *ty {
Type::Atom { atom } => {
let mut name = String::new();
let written = spelling.atom.write(&mut name, &term.atoms[atom as usize]);
written.map_or(u64::MAX, |()| name.len() as u64)
}
Type::One => c.one.len() as u64,
Type::Top => c.top.len() as u64,
Type::Zero => c.zero.len() as u64,
Type::Bang { of: a } => of(a).saturating_add(c.bang.len() as u64 + 2),
Type::Tensor { left, right } => binary(left, c.tensor, right),
Type::With { left, right } => binary(left, c.with, right),
Type::Plus { left, right } => binary(left, c.plus, right),
Type::Lollipop { from, to } => binary(from, c.lollipop, to),
};
lengths.push(length);
}
printer.type_lengths = lengths;
printer
}
const fn connectives(&self) -> &Connectives {
match self.term.calculus {
Calculus::Linear | Calculus::Affine => &self.spelling.linear,
Calculus::Simple => &self.spelling.simple,
}
}
fn var(&self, out: &mut impl Write, v: VarId) -> std::fmt::Result {
let variable = &self.term.variables[v.index()];
out.write_char(variable.letter)?;
if variable.index == 0 {
return Ok(());
}
match self.spelling.index {
Index::Digits => write!(out, "{}", variable.index),
#[cfg(any(feature = "latex", feature = "typst"))]
Index::Marked(open, close) => write!(out, "{open}{}{close}", variable.index),
Index::Subscript => {
for digit in variable.index.to_string().chars() {
let d = digit.to_digit(10).unwrap_or(0);
out.write_char(char::from_u32(0x2080 + d).unwrap_or(digit))?;
}
Ok(())
}
}
}
fn ty(&self, out: &mut impl Write, ty: TypeId, bracket: bool) -> std::fmt::Result {
enum Step {
Type(TypeId, bool),
Text(&'static str),
}
let c = self.connectives();
let mut stack = vec![Step::Type(ty, bracket)];
while let Some(step) = stack.pop() {
let (t, bracket) = match step {
Step::Text(s) => {
out.write_str(s)?;
continue;
}
Step::Type(t, bracket) => (t, bracket),
};
let binary = |stack: &mut Vec<Step>, l: TypeId, op: &'static str, r: TypeId| {
if bracket {
stack.push(Step::Text(")"));
}
stack.push(Step::Type(r, true));
stack.push(Step::Text(op));
stack.push(Step::Type(l, true));
if bracket {
stack.push(Step::Text("("));
}
};
match self.term.types[t.index()] {
Type::Atom { atom } => self
.spelling
.atom
.write(out, &self.term.atoms[atom as usize])?,
Type::One => out.write_str(c.one)?,
Type::Top => out.write_str(c.top)?,
Type::Zero => out.write_str(c.zero)?,
Type::Bang { of } => {
out.write_str(c.bang)?;
stack.push(Step::Type(of, true));
}
Type::Tensor { left, right } => binary(&mut stack, left, c.tensor, right),
Type::With { left, right } => binary(&mut stack, left, c.with, right),
Type::Plus { left, right } => binary(&mut stack, left, c.plus, right),
Type::Lollipop { from, to } => binary(&mut stack, from, c.lollipop, to),
}
}
Ok(())
}
fn pieces(&self, node: &Node) -> Vec<Piece> {
use Piece::{Keyword, Term as T, Text, Var};
let s = self.spelling;
let linear = self.term.calculus != Calculus::Simple;
let typed = |v: VarId| {
if self.types {
vec![
Var(v),
Text(s.colon),
Piece::Type(self.term.variables[v.index()].ty, true),
]
} else {
vec![Var(v)]
}
};
let list = |terms: &[TermId]| {
let mut pieces = Vec::new();
for (i, &t) in terms.iter().enumerate() {
if i > 0 {
pieces.push(Text(", "));
}
pieces.push(T(t, Place::Free));
}
pieces
};
let call = |keyword: &'static str, term: TermId| {
vec![Keyword(keyword), Text("("), T(term, Place::Free), Text(")")]
};
match node {
Node::Var { variable } => vec![Var(*variable)],
Node::Lambda { variable, body } => {
let mut pieces = vec![Text(s.lambda)];
pieces.extend(typed(*variable));
pieces.extend([Text(s.dot), T(*body, Place::Free)]);
pieces
}
Node::Apply { function, argument } => vec![
T(*function, Place::Function),
Text(s.apply),
T(*argument, Place::Argument),
],
Node::Tensor { left, right } => vec![
T(*left, Place::Operand),
Text(s.tensor),
T(*right, Place::Operand),
],
Node::LetTensor {
term,
left,
right,
body,
} => vec![
Keyword("let"),
Text(s.space),
T(*term, Place::Free),
Text(s.space),
Keyword("be"),
Text(s.space),
Var(*left),
Text(s.tensor),
Var(*right),
Text(s.space),
Keyword("in"),
Text(s.space),
T(*body, Place::Free),
],
Node::Unit => vec![Text(s.unit)],
Node::LetUnit { term, body } => vec![
Keyword("let"),
Text(s.space),
T(*term, Place::Free),
Text(s.space),
Keyword("be"),
Text(s.space),
Text(s.unit),
Text(s.space),
Keyword("in"),
Text(s.space),
T(*body, Place::Free),
],
Node::Pair { left, right } => vec![
Text(s.open_pair),
T(*left, Place::Free),
Text(", "),
T(*right, Place::Free),
Text(s.close_pair),
],
Node::First { term } => call("fst", *term),
Node::Second { term } => call("snd", *term),
Node::Left { term, .. } => call("inl", *term),
Node::Right { term, .. } => call("inr", *term),
Node::Case {
term,
left,
left_body,
right,
right_body,
} => vec![
Keyword("case"),
Text(s.space),
T(*term, Place::Free),
Text(s.space),
Keyword("of"),
Text(s.space),
Keyword("inl"),
Text("("),
Var(*left),
Text(")"),
Text(s.arrow),
T(*left_body, Place::Operand),
Text(s.bar),
Keyword("inr"),
Text("("),
Var(*right),
Text(")"),
Text(s.arrow),
T(*right_body, Place::Free),
],
Node::True { .. } if !linear => vec![Text(s.empty_pair)],
Node::True { context } => {
let mut pieces = vec![Keyword("true"), Text("(")];
pieces.extend(list(context));
pieces.push(Text(")"));
pieces
}
Node::False { term, goal, .. } if !linear => {
let mut pieces = vec![Keyword("abort")];
if self.types {
pieces.extend([
Text(s.subscript.0),
Piece::Type(*goal, false),
Text(s.subscript.1),
]);
}
pieces.extend([Text("("), T(*term, Place::Free), Text(")")]);
pieces
}
Node::False {
context,
term,
goal,
} => {
let mut pieces = vec![Keyword("false")];
if self.types {
pieces.extend([
Text(s.subscript.0),
Piece::Type(*goal, false),
Text(s.subscript.1),
]);
}
pieces.push(Text("("));
pieces.extend(list(context));
pieces.extend([Text("; "), T(*term, Place::Free), Text(")")]);
pieces
}
Node::Promote {
terms,
variables,
body,
} => {
let mut pieces = vec![Keyword("promote")];
for (i, &t) in terms.iter().enumerate() {
pieces.push(Text(if i == 0 { s.space } else { ", " }));
pieces.push(T(t, Place::Free));
}
pieces.extend([Text(s.space), Keyword("for")]);
for (i, &v) in variables.iter().enumerate() {
pieces.push(Text(if i == 0 { s.space } else { ", " }));
pieces.push(Var(v));
}
pieces.extend([
Text(s.space),
Keyword("in"),
Text(s.space),
T(*body, Place::Free),
]);
pieces
}
Node::Derelict { term } => call("derelict", *term),
Node::Discard { term, body } => vec![
Keyword("discard"),
Text(s.space),
T(*term, Place::Free),
Text(s.space),
Keyword("in"),
Text(s.space),
T(*body, Place::Free),
],
Node::Copy {
term,
left,
right,
body,
} => vec![
Keyword("copy"),
Text(s.space),
T(*term, Place::Free),
Text(s.space),
Keyword("as"),
Text(s.space),
Var(*left),
Text(", "),
Var(*right),
Text(s.space),
Keyword("in"),
Text(s.space),
T(*body, Place::Free),
],
}
}
fn length(&self, piece: Piece) -> u64 {
let mut text = String::new();
let written = match piece {
Piece::Text(t) => return t.len() as u64,
Piece::Keyword(k) => {
return (self.spelling.keyword.0.len() + k.len() + self.spelling.keyword.1.len())
as u64;
}
Piece::Term(..) => return 0,
Piece::Var(v) => self.var(&mut text, v),
Piece::Type(t, _) => return self.type_lengths[t.index()],
};
written.map_or(u64::MAX, |()| text.len() as u64)
}
fn lengths(&self) -> Vec<u64> {
let mut lengths: Vec<u64> = Vec::with_capacity(self.term.nodes.len());
for node in &self.term.nodes {
let mut sum = 2u64;
for piece in self.pieces(node) {
let add = match piece {
Piece::Term(t, _) => lengths[t.index()],
other @ (Piece::Text(_)
| Piece::Keyword(_)
| Piece::Var(_)
| Piece::Type(..)) => self.length(other),
};
sum = sum.saturating_add(add);
}
lengths.push(sum);
}
lengths
}
fn write(
&self,
out: &mut impl Write,
judgement: bool,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
let term = self.term;
let s = self.spelling;
let mut estimate = self.lengths()[term.root.index()];
let mut written = Vec::new();
if judgement {
for (i, &v) in term.context.iter().enumerate() {
if i > 0 {
written.push(Piece::Text(", "));
}
written.extend([
Piece::Var(v),
Piece::Text(s.has_type),
Piece::Type(term.variables[v.index()].ty, false),
]);
}
let turnstile = if term.context.is_empty() {
s.turnstile.trim_start()
} else {
s.turnstile
};
written.push(Piece::Text(turnstile));
}
written.push(Piece::Term(term.root, Place::Free));
if judgement {
written.extend([Piece::Text(s.has_type), Piece::Type(term.goal, false)]);
}
for piece in &written {
if !matches!(piece, Piece::Term(..)) {
estimate = estimate.saturating_add(self.length(*piece));
}
}
let mut stack: Vec<Piece> = written.into_iter().rev().collect();
if let Some(limit) = limits.derivation_bytes
&& estimate > limit
{
return Err(Error::Refused(Refusal::Output {
what: "term",
estimate_bytes: estimate,
limit_bytes: limit,
least_bytes: None,
}));
}
let mut stop = crate::limits::counting(stop, Phase::Write);
while let Some(piece) = stack.pop() {
match piece {
Piece::Text(t) => out.write_str(t)?,
Piece::Keyword(k) => {
out.write_str(s.keyword.0)?;
out.write_str(k)?;
out.write_str(s.keyword.1)?;
}
Piece::Var(v) => self.var(out, v)?,
Piece::Type(t, bracket) => self.ty(out, t, bracket)?,
Piece::Term(t, place) => {
if stop() {
return Err(Error::Refused(Refusal::Stopped {
phase: Phase::Write,
}));
}
let node = &term.nodes[t.index()];
let bracket = bracketed(node, place);
if bracket {
stack.push(Piece::Text(")"));
}
stack.extend(self.pieces(node).into_iter().rev());
if bracket {
stack.push(Piece::Text("("));
}
}
}
}
Ok(())
}
}
impl Term {
pub fn write(
&self,
out: &mut impl Write,
options: &Options,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
self.write_in(
options.notation.spelling(),
options.types,
false,
out,
limits,
stop,
)
}
pub fn write_judgement(
&self,
out: &mut impl Write,
options: &Options,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
self.write_in(
options.notation.spelling(),
options.types,
true,
out,
limits,
stop,
)
}
pub(crate) fn write_in(
&self,
spelling: &Spelling,
types: bool,
judgement: bool,
out: &mut impl Write,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), Error> {
Printer::new(self, spelling, types).write(out, judgement, limits, stop)
}
}