use super::derivation::{Derivation, InfId};
use super::style::{Drawn, Labels, OpenGoal, RUN, plain};
use crate::Error;
use crate::linear::occurrences::instances::Framing;
use crate::linear::occurrences::{Forest, Member, Reading};
use crate::linear::sequents::notation::TEXT;
use std::fmt::{Display, Formatter, Result as FmtResult, Write};
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(default, deny_unknown_fields))]
pub struct TextOptions {
pub labels: Labels,
pub open: OpenGoal,
pub bar: char,
pub gap: u16,
}
impl TextOptions {
pub const BAR: char = '─';
pub const GAP: u16 = 3;
}
impl Default for TextOptions {
fn default() -> Self {
Self {
labels: Labels::Upright,
open: OpenGoal::Bare,
bar: Self::BAR,
gap: Self::GAP,
}
}
}
impl TextOptions {
#[must_use]
pub fn with_labels(self, labels: Labels) -> Self {
Self { labels, ..self }
}
#[must_use]
pub fn with_open(self, open: OpenGoal) -> Self {
Self { open, ..self }
}
#[must_use]
pub fn with_bar(self, bar: char) -> Self {
Self { bar, ..self }
}
#[must_use]
pub fn with_gap(self, gap: u16) -> Self {
Self { gap, ..self }
}
}
struct Bar {
line: char,
label: String,
dots: bool,
}
fn bars<T: Drawn>(tree: &T, options: &TextOptions) -> Vec<Option<Bar>> {
let runs = (0..tree.rules()).map(|rule| {
Some(Bar {
line: options.bar,
label: tree
.markup(rule, &options.labels)
.map_or_else(String::new, |label| plain(label) + RUN),
dots: false,
})
});
(0..tree.rules())
.map(|rule| {
let bar = |line, label: &str, dots| Bar {
line,
label: plain(label),
dots,
};
if tree.bare() == Some(rule) {
return None;
}
if tree.open() != Some(rule) {
return Some(bar(
options.bar,
tree.markup(rule, &options.labels).unwrap_or(""),
false,
));
}
match &options.open {
OpenGoal::Bare => None,
OpenGoal::Dots => Some(bar('⋮', "", true)),
OpenGoal::Dashed => Some(bar('╌', "", false)),
OpenGoal::Mark(mark) => Some(bar(options.bar, mark, false)),
}
})
.chain(runs)
.collect()
}
fn bar<'a, T: Drawn>(bars: &'a [Option<Bar>], tree: &T, id: InfId) -> &'a Option<Bar> {
let run = if tree.times(id) > 1 { tree.rules() } else { 0 };
&bars[tree.rule(id) + run]
}
#[derive(Clone, Copy, Debug, Default)]
struct Place {
x: usize,
width: usize,
height: usize,
depth: usize,
left: usize,
conclusion: usize,
bar: Option<(usize, usize)>,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
struct Piece {
row: usize,
column: usize,
id: InfId,
bar: bool,
}
struct Count(usize);
impl Write for Count {
fn write_str(&mut self, s: &str) -> FmtResult {
self.0 += s.chars().count();
Ok(())
}
}
fn spaces(out: &mut impl Write, width: usize) -> FmtResult {
const RUN: &str = " ";
let mut left = width;
while left > 0 {
let n = left.min(RUN.len());
out.write_str(&RUN[..n])?;
left -= n;
}
Ok(())
}
pub(super) fn write_sequent(
out: &mut impl Write,
forest: &Forest,
reading: Option<&Reading>,
framing: Option<&Framing<'_>>,
sequent: &[Member],
) -> FmtResult {
TEXT.sequent(out, forest, reading, framing, sequent, false, false)
}
fn layout<T: Drawn>(tree: &T, options: &TextOptions, bars: &[Option<Bar>]) -> Vec<Place> {
let mut places = vec![Place::default(); tree.len()];
for i in 0..places.len() {
let id = InfId::new(i as u32);
let mut count = Count(0);
tree.write_sequent(&mut count, id)
.expect("counting never fails");
let conclusion = count.0;
let premises = tree.premises(id);
let Some(bar) = bar(bars, tree, id) else {
places[i] = Place {
width: conclusion,
height: 1,
conclusion,
..Place::default()
};
continue;
};
let (mut row, mut height) = (0, 0);
let (mut span_left, mut span_right) = (0, 0);
for (k, p) in premises.iter().enumerate() {
let place = &mut places[p.index()];
place.x = row + if k == 0 { 0 } else { usize::from(options.gap) };
if k == 0 {
span_left = place.left;
}
span_right = place.x + place.left + place.conclusion;
row = place.x + place.width;
height = height.max(place.height);
}
let span = span_right - span_left;
let bar_width = conclusion.max(span);
let overhang = (bar_width - span) / 2;
let shift = overhang.saturating_sub(span_left);
for p in premises {
places[p.index()].x += shift;
}
let bar_left = span_left + shift - overhang;
let left = bar_left + (bar_width - conclusion) / 2;
let (bar_left, bar_width) = if bar.dots {
(left + conclusion.saturating_sub(1) / 2, 1)
} else {
(bar_left, bar_width)
};
let label = match bar.label.chars().count() {
0 => 0,
n => n + 1,
};
let premises = if premises.is_empty() { 0 } else { row + shift };
places[i] = Place {
x: 0,
width: premises
.max(bar_left + bar_width + label)
.max(left + conclusion),
height: height + 2,
depth: 0,
left,
conclusion,
bar: Some((bar_left, bar_width)),
};
}
for i in (0..places.len()).rev() {
let (x, depth) = (places[i].x, places[i].depth);
for p in tree.premises(InfId::new(i as u32)) {
places[p.index()].x += x;
places[p.index()].depth = depth + 1;
}
}
places
}
pub(crate) fn text_size<T: Drawn>(tree: &T, options: &TextOptions) -> (usize, usize) {
let root = layout(tree, options, &bars(tree, options))[tree.root().index()];
(root.width, root.height)
}
pub(crate) fn write_text<T: Drawn>(
tree: &T,
options: &TextOptions,
out: &mut impl Write,
mut stop: impl FnMut() -> bool,
) -> Result<(), Error> {
let bars = bars(tree, options);
let places = layout(tree, options, &bars);
let height = places[tree.root().index()].height;
let mut pieces = Vec::with_capacity(2 * places.len());
for (i, place) in places.iter().enumerate() {
let id = InfId::new(i as u32);
let row = height - 1 - 2 * place.depth;
pieces.push(Piece {
row,
column: place.x + place.left,
id,
bar: false,
});
if let Some((left, _)) = place.bar {
pieces.push(Piece {
row: row - 1,
column: place.x + left,
id,
bar: true,
});
}
}
pieces.sort_unstable();
let (mut row, mut column) = (0, 0);
for piece in pieces {
if stop() {
return Err(Error::Refused(crate::limits::Refusal::Stopped {
phase: crate::limits::Phase::Write,
}));
}
while row < piece.row {
out.write_char('\n')?;
(row, column) = (row + 1, 0);
}
spaces(out, piece.column - column)?;
let place = &places[piece.id.index()];
column = piece.column;
match (place.bar, bar(&bars, tree, piece.id)) {
(Some((_, width)), Some(bar)) if piece.bar => {
for _ in 0..width {
out.write_char(bar.line)?;
}
column += width;
if !bar.label.is_empty() {
write!(out, " {}", bar.label)?;
column += 1 + bar.label.chars().count();
}
}
_ => {
tree.write_sequent(out, piece.id)?;
column += place.conclusion;
}
}
}
Ok(())
}
pub(crate) fn write_steps<T: Drawn, W: Write>(
tree: &T,
out: &mut W,
mut stop: impl FnMut() -> bool,
mut sequent: impl FnMut(&mut W, InfId) -> std::fmt::Result,
) -> Result<(), Error> {
for i in 0..tree.len() {
if stop() {
return Err(Error::Refused(crate::limits::Refusal::Stopped {
phase: crate::limits::Phase::Write,
}));
}
if i > 0 {
out.write_char('\n')?;
}
let id = InfId::new(i as u32);
write!(out, "{}. ", i + 1)?;
sequent(out, id)?;
if tree.is_open(id) {
out.write_str(", open.")?;
continue;
}
write!(out, ", by {}", tree.name(id))?;
if tree.times(id) > 1 {
write!(out, " {} times", tree.times(id))?;
}
let premises = tree.premises(id);
for (k, p) in premises.iter().enumerate() {
let joint = match k {
0 => " from ",
_ if k + 1 == premises.len() => " and ",
_ => ", ",
};
write!(out, "{joint}{}", p.index() + 1)?;
}
out.write_char('.')?;
}
Ok(())
}
impl Derivation<'_> {
pub fn text_size(&self, options: &TextOptions) -> (usize, usize) {
text_size(self, options)
}
pub fn write_text(
&self,
options: &TextOptions,
out: &mut impl Write,
stop: impl FnMut(crate::limits::Progress) -> bool,
) -> Result<(), Error> {
write_text(
self,
options,
out,
crate::limits::counting(stop, crate::limits::Phase::Write),
)
}
pub fn write_steps(
&self,
out: &mut impl Write,
stop: impl FnMut(crate::limits::Progress) -> bool,
) -> Result<(), Error> {
write_steps(
self,
out,
crate::limits::counting(stop, crate::limits::Phase::Write),
|out, id| self.write_sequent(out, id),
)
}
}
impl Display for Derivation<'_> {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
self.write_text(&TextOptions::default(), f, |_| false)
.map_err(|_| std::fmt::Error)
}
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use crate::linear::{Mode, Options, Sequent, Verdict, prove};
#[test]
fn wider_than_a_format_width() {
let name = "a".repeat(70_000);
let sequent: Sequent = format!("|- {name}, ~{name} * ~b, b").parse().unwrap();
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default()).unwrap();
let Verdict::Proved(proof) = outcome.verdict else {
panic!("provable");
};
let tree = proof.derivation().unwrap().to_string();
let premises = tree.lines().nth(1).unwrap();
assert!(premises.len() > 140_000, "{}", premises.len());
assert!(
premises.ends_with("⊢ ~b, b"),
"{}",
&premises[premises.len() - 40..]
);
}
}