#[derive(Clone, Debug)]
pub enum Doc {
Text(Span),
Source(Span),
Group(Group),
Indent(Fragment),
Line(Line),
LineSuffix(Fragment),
BreakParent,
}
#[derive(Clone, Copy, Debug)]
pub struct Group {
pub broken: bool,
pub contents: Fragment,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Span {
start: u32,
end: u32,
}
impl Span {
fn new(start: usize, end: usize) -> Self {
Self {
start: u32::try_from(start).expect("a document contains fewer than 2^32 bytes"),
end: u32::try_from(end).expect("a document contains fewer than 2^32 bytes"),
}
}
pub fn range(self) -> std::ops::Range<usize> {
self.start as usize..self.end as usize
}
}
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Fragment {
start: u32,
end: u32,
}
impl Fragment {
fn new(start: usize, end: usize) -> Self {
Self {
start: u32::try_from(start).expect("a document contains fewer than 2^32 edges"),
end: u32::try_from(end).expect("a document contains fewer than 2^32 edges"),
}
}
fn range(self) -> std::ops::Range<usize> {
self.start as usize..self.end as usize
}
}
#[derive(Debug)]
pub struct Document {
docs: Vec<Doc>,
children: Vec<u32>,
text: String,
root: Fragment,
}
impl Document {
fn doc(&self, id: u32) -> &Doc {
&self.docs[id as usize]
}
fn ids(&self, fragment: Fragment) -> &[u32] {
&self.children[fragment.range()]
}
fn text(&self, span: Span) -> &str {
&self.text[span.range()]
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Separator {
Empty,
Space,
}
impl Separator {
fn as_str(self) -> &'static str {
match self {
Self::Empty => "",
Self::Space => " ",
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Line {
separator: Separator,
pub force: bool,
}
pub const SOFT: Line = Line {
separator: Separator::Empty,
force: false,
};
pub const SPACE: Line = Line {
separator: Separator::Space,
force: false,
};
pub const HARD: Line = Line {
separator: Separator::Space,
force: true,
};
pub struct Builder {
docs: Vec<Doc>,
children: Vec<u32>,
text: String,
working: Vec<u32>,
groups: Vec<OpenGroup>,
target_starts: Vec<usize>,
}
struct OpenGroup {
broken: bool,
target_depth: usize,
}
impl Default for Builder {
fn default() -> Self {
Self::new()
}
}
impl Builder {
pub fn new() -> Self {
Self::with_capacity(0)
}
pub fn with_capacity(capacity: usize) -> Self {
Self {
docs: Vec::with_capacity(capacity),
children: Vec::with_capacity(capacity),
text: String::new(),
working: Vec::new(),
groups: vec![OpenGroup {
broken: false,
target_depth: 0,
}],
target_starts: vec![0],
}
}
fn push_doc(&mut self, doc: Doc) {
let id = u32::try_from(self.docs.len()).expect("a document contains fewer than 2^32 nodes");
self.docs.push(doc);
self.working.push(id);
}
fn target_last(&self) -> Option<u32> {
let start = *self.target_starts.last().expect("builder always has a target");
(self.working.len() > start).then(|| *self.working.last().expect("non-empty target"))
}
fn seal_target(&mut self) -> Fragment {
let start = self.target_starts.pop().expect("builder always has a target");
let fragment_start = self.children.len();
self.children.extend_from_slice(&self.working[start..]);
self.working.truncate(start);
Fragment::new(fragment_start, self.children.len())
}
pub fn text(&mut self, s: &str) {
if s.is_empty() {
return;
}
if s == " "
&& let Some(id) = self.target_last()
&& let Doc::Text(previous) = &self.docs[id as usize]
&& self.text[previous.range()].ends_with(' ')
{
return;
}
let start = self.text.len();
self.text.push_str(s);
let span = Span::new(start, self.text.len());
if let Some(id) = self.target_last()
&& let Doc::Text(previous) = &mut self.docs[id as usize]
&& previous.end == span.start
{
previous.end = span.end;
} else {
self.push_doc(Doc::Text(span));
}
}
pub fn source(&mut self, start: usize, end: usize) {
if start == end {
return;
}
let span = Span::new(start, end);
if let Some(id) = self.target_last()
&& let Doc::Source(previous) = &mut self.docs[id as usize]
&& previous.end == span.start
{
previous.end = span.end;
} else {
self.push_doc(Doc::Source(span));
}
}
pub fn line(&mut self, line: Line) {
self.push_doc(Doc::Line(line));
if line.force {
self.break_parent();
}
}
#[cfg(test)]
pub fn space(&mut self) {
self.line(SPACE);
}
#[cfg(test)]
pub fn soft(&mut self) {
self.line(SOFT);
}
#[cfg(test)]
pub fn hard(&mut self) {
self.line(HARD);
}
pub fn break_parent(&mut self) {
self.push_doc(Doc::BreakParent);
for group in self.groups.iter_mut().rev() {
if group.broken {
break;
}
group.broken = true;
}
}
fn push_target(&mut self) {
self.target_starts.push(self.working.len());
}
fn pop_target(&mut self) -> Fragment {
assert!(self.target_starts.len() > 1, "popped the root target");
self.seal_target()
}
pub fn open_group(&mut self) {
self.groups.push(OpenGroup {
broken: false,
target_depth: self.target_starts.len(),
});
self.push_target();
}
pub fn close_group(&mut self) {
let contents = self.pop_target();
let group = self.groups.pop().expect("open group");
assert_eq!(
self.target_starts.len(),
group.target_depth,
"group closed with containers still open"
);
self.push_doc(Doc::Group(Group {
broken: group.broken,
contents,
}));
}
#[cfg(test)]
pub fn group(&mut self, f: impl FnOnce(&mut Self)) {
self.open_group();
f(self);
self.close_group();
}
pub fn open_indent(&mut self) {
self.push_target();
}
pub fn close_indent(&mut self) {
let contents = self.pop_target();
self.push_doc(Doc::Indent(contents));
}
#[cfg(test)]
pub fn indent(&mut self, f: impl FnOnce(&mut Self)) {
self.open_indent();
f(self);
self.close_indent();
}
pub fn line_suffix(&mut self, f: impl FnOnce(&mut Self)) {
self.push_target();
f(self);
let contents = self.pop_target();
self.push_doc(Doc::LineSuffix(contents));
}
pub fn finish(mut self) -> Document {
assert_eq!(self.groups.len(), 1, "unclosed group");
assert_eq!(self.target_starts.len(), 1, "unclosed container");
let root = self.seal_target();
Document {
docs: self.docs,
children: self.children,
text: self.text,
root,
}
}
}
#[derive(Clone, Copy, PartialEq, Eq)]
enum Mode {
Break,
Flat,
}
#[derive(Clone, Copy)]
struct Command {
indent: usize,
mode: Mode,
id: u32,
}
struct Suffix {
indent: usize,
mode: Mode,
contents: Fragment,
}
#[derive(Clone, Copy, Debug)]
pub struct PrintOptions {
pub line_width: usize,
pub indent_width: usize,
pub output_capacity: usize,
}
pub fn print(document: &Document, source: &str, options: PrintOptions) -> String {
render(
document,
source,
options,
String::with_capacity(options.output_capacity),
)
}
pub fn matches_source(document: &Document, source: &str, options: PrintOptions) -> bool {
render(document, source, options, MatchOutput::new(source.as_bytes())).matches()
}
trait Output {
fn write_str(&mut self, text: &str);
fn write_spaces(&mut self, count: usize);
fn trim_trailing(&mut self);
}
impl Output for String {
fn write_str(&mut self, text: &str) {
self.push_str(text);
}
fn write_spaces(&mut self, count: usize) {
self.extend(std::iter::repeat_n(' ', count));
}
fn trim_trailing(&mut self) {
let trimmed = self.trim_end_matches([' ', '\t']).len();
self.truncate(trimmed);
}
}
struct MatchOutput<'a> {
expected: &'a [u8],
cursor: usize,
matches: bool,
trailing_cursor: usize,
trailing_matches: bool,
trailing_len: usize,
}
impl<'a> MatchOutput<'a> {
fn new(expected: &'a [u8]) -> Self {
Self {
expected,
cursor: 0,
matches: true,
trailing_cursor: 0,
trailing_matches: true,
trailing_len: 0,
}
}
fn compare(&mut self, bytes: &[u8]) {
let available = self.expected.len().saturating_sub(self.cursor).min(bytes.len());
self.matches &= available == bytes.len()
&& self.expected.get(self.cursor..self.cursor + available) == Some(&bytes[..available]);
self.cursor = self.cursor.saturating_add(bytes.len());
}
fn begin_trailing(&mut self) {
if self.trailing_len == 0 {
self.trailing_cursor = self.cursor;
self.trailing_matches = self.matches;
}
}
fn matches(self) -> bool {
self.matches && self.cursor == self.expected.len()
}
}
impl Output for MatchOutput<'_> {
fn write_str(&mut self, text: &str) {
let bytes = text.as_bytes();
let prefix_len = bytes
.iter()
.rposition(|byte| !matches!(byte, b' ' | b'\t'))
.map_or(0, |index| index + 1);
if prefix_len > 0 {
self.compare(&bytes[..prefix_len]);
self.trailing_len = 0;
}
if prefix_len < bytes.len() {
self.begin_trailing();
self.compare(&bytes[prefix_len..]);
self.trailing_len += bytes.len() - prefix_len;
}
}
fn write_spaces(&mut self, count: usize) {
if count == 0 {
return;
}
self.begin_trailing();
let available = self.expected.len().saturating_sub(self.cursor).min(count);
self.matches &= available == count
&& self
.expected
.get(self.cursor..self.cursor.saturating_add(available))
.is_some_and(|bytes| bytes.iter().all(|&byte| byte == b' '));
self.cursor = self.cursor.saturating_add(count);
self.trailing_len += count;
}
fn trim_trailing(&mut self) {
if self.trailing_len > 0 {
self.cursor = self.trailing_cursor;
self.matches = self.trailing_matches;
self.trailing_len = 0;
}
}
}
fn render<T: Output>(document: &Document, source: &str, options: PrintOptions, mut out: T) -> T {
debug_assert!(options.line_width > 0);
debug_assert!(options.indent_width > 0);
let mut position = 0usize;
let mut commands = Vec::new();
push_all(&mut commands, document, document.root, 0, Mode::Break);
let mut remeasure = false;
let mut suffixes: Vec<Suffix> = Vec::new();
let mut fit_commands = Vec::new();
while let Some(Command { indent, mode, id }) = commands.pop() {
match document.doc(id) {
Doc::Text(span) => {
let text = document.text(*span);
out.write_str(text);
position += text_width(text);
}
Doc::Source(span) => {
let text = &source[span.range()];
out.write_str(text);
position += text_width(text);
}
Doc::Group(group) => {
if mode == Mode::Flat && !remeasure {
let next = if group.broken { Mode::Break } else { Mode::Flat };
push_all(&mut commands, document, group.contents, indent, next);
} else {
remeasure = false;
if group.broken {
push_all(&mut commands, document, group.contents, indent, Mode::Break);
} else {
let mode = if fits(
document,
group.contents,
&commands,
source,
&mut fit_commands,
FitOptions {
indent,
remaining: options.line_width.saturating_sub(position),
within_width: position <= options.line_width,
indent_width: options.indent_width,
},
) {
Mode::Flat
} else {
Mode::Break
};
push_all(&mut commands, document, group.contents, indent, mode);
}
}
}
Doc::Line(line) => {
if mode == Mode::Flat {
if line.force {
remeasure = true;
} else {
let separator = line.separator.as_str();
out.write_str(separator);
position += separator.len();
continue;
}
}
if !suffixes.is_empty() {
commands.push(Command { indent, mode, id });
flush_suffixes(&mut commands, document, &mut suffixes);
continue;
}
out.trim_trailing();
out.write_str("\n");
out.write_spaces(indent);
position = indent;
}
Doc::Indent(contents) => push_all(
&mut commands,
document,
*contents,
indent.saturating_add(options.indent_width),
mode,
),
Doc::LineSuffix(contents) => suffixes.push(Suffix {
indent,
mode,
contents: *contents,
}),
Doc::BreakParent => {}
}
if commands.is_empty() && !suffixes.is_empty() {
flush_suffixes(&mut commands, document, &mut suffixes);
}
}
out
}
fn push_all(commands: &mut Vec<Command>, document: &Document, docs: Fragment, indent: usize, mode: Mode) {
commands.extend(document.ids(docs).iter().rev().map(|&id| Command { indent, mode, id }));
}
fn flush_suffixes(commands: &mut Vec<Command>, document: &Document, suffixes: &mut Vec<Suffix>) {
for suffix in suffixes.drain(..).rev() {
push_all(commands, document, suffix.contents, suffix.indent, suffix.mode);
}
}
struct FitOptions {
indent: usize,
remaining: usize,
within_width: bool,
indent_width: usize,
}
fn fits(
document: &Document,
contents: Fragment,
rest: &[Command],
source: &str,
commands: &mut Vec<Command>,
options: FitOptions,
) -> bool {
if !options.within_width {
return false;
}
let mut remaining = options.remaining as isize;
let mut rest_index = rest.len();
commands.clear();
push_all(commands, document, contents, options.indent, Mode::Flat);
while remaining >= 0 {
let Command { indent, mode, id } = match commands.pop() {
Some(command) => command,
None => {
if rest_index == 0 {
return true;
}
rest_index -= 1;
commands.push(rest[rest_index]);
continue;
}
};
match document.doc(id) {
Doc::Text(span) => remaining -= text_width(document.text(*span)) as isize,
Doc::Source(span) => remaining -= text_width(&source[span.range()]) as isize,
Doc::Group(group) => {
let next = if group.broken { Mode::Break } else { mode };
push_all(commands, document, group.contents, indent, next);
}
Doc::Line(line) => {
if mode == Mode::Flat && !line.force {
remaining -= line.separator.as_str().len() as isize;
continue;
}
return true;
}
Doc::Indent(contents) => push_all(
commands,
document,
*contents,
indent.saturating_add(options.indent_width),
mode,
),
Doc::LineSuffix(_) | Doc::BreakParent => {}
}
}
false
}
fn text_width(text: &str) -> usize {
if text.is_ascii() {
text.len()
} else {
text.chars().count()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn render(f: impl FnOnce(&mut Builder), width: usize) -> String {
let mut b = Builder::new();
f(&mut b);
print(
&b.finish(),
"",
PrintOptions {
line_width: width,
indent_width: 4,
output_capacity: 0,
},
)
}
fn list(b: &mut Builder) {
b.group(|b| {
b.text("[");
b.indent(|b| {
b.soft();
b.text("aaaa,");
b.space();
b.text("bbbb");
});
b.soft();
b.text("]");
});
}
#[test]
fn flat_when_it_fits() {
assert_eq!(render(list, 80), "[aaaa, bbbb]");
}
#[test]
fn breaks_and_indents_when_it_does_not_fit() {
assert_eq!(render(list, 8), "[\n aaaa,\n bbbb\n]");
}
#[test]
fn forced_break_propagates_to_enclosing_groups() {
let s = render(
|b| {
b.group(|b| {
b.text("a");
b.space();
b.group(|b| {
b.text("b");
b.hard();
b.text("c");
});
})
},
80,
);
assert_eq!(s, "a\nb\nc");
}
#[test]
fn line_suffix_defers_to_end_of_line() {
let s = render(
|b| {
b.text("x = 1;");
b.line_suffix(|b| b.text(" // hi"));
b.text(";");
b.hard();
b.text("y");
},
80,
);
assert_eq!(s, "x = 1;; // hi\ny");
}
#[test]
fn trailing_whitespace_is_trimmed_before_a_line_break() {
let s = render(
|b| {
b.text("a ");
b.hard();
b.text("b");
},
80,
);
assert_eq!(s, "a\nb");
}
#[test]
fn compares_rendered_output_without_materialising_it() {
let mut b = Builder::new();
b.text("a ");
b.indent(|b| {
b.hard();
b.text("b");
});
let docs = b.finish();
let options = PrintOptions {
line_width: 80,
indent_width: 4,
output_capacity: 0,
};
assert_eq!(print(&docs, "", options), "a\n b");
assert!(matches_source(&docs, "a\n b", options));
assert!(!matches_source(&docs, "a \n b", options));
assert!(!matches_source(&docs, "a\n b", options));
assert!(!matches_source(&docs, "a\n b\n", options));
}
#[test]
fn adjacent_source_spans_merge() {
let mut b = Builder::new();
b.source(0, 1);
b.source(1, 3);
let docs = b.finish();
assert_eq!(docs.ids(docs.root).len(), 1);
assert_eq!(
print(
&docs,
"abc",
PrintOptions {
line_width: 80,
indent_width: 2,
output_capacity: 3,
},
),
"abc"
);
}
}