Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_text/src/fmt/render.rs

12.0 KiB, 10 runs

created by r1870400018:11634, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! Layout renderer.
2//!
3//! Converts a `Doc` into a formatted `String` by making optimal
4//! line-breaking decisions. Based on Lindig's strict version of
5//! Wadler's algorithm, extended with alignment support.
6//!
7
8use crate::fmt::doc::Doc;
9
10use oxedyne_fe2o3_core::prelude::*;
11
12
13/// Rendering mode for the current group.
14#[derive(Clone, Copy, Debug, Eq, PartialEq)]
15enum Mode {
16 /// Try to fit everything on one line.
17 Flat,
18 /// Break at every `Line`.
19 Break,
20}
21
22/// A command on the rendering work stack.
23#[derive(Clone, Debug)]
24struct Cmd {
25 indent: usize,
26 mode: Mode,
27 doc: Doc,
28}
29
30/// Render a `Doc` to a formatted string.
31///
32/// # Arguments
33/// * `width` — maximum line width (soft limit; `Text` nodes that
34/// exceed it are never broken).
35/// * `indent_str` — the string used for one level of indentation
36/// (e.g. `" "` for four spaces).
37/// * `doc` — the layout document to render.
38pub fn render(
39 width: usize,
40 indent_str: &str,
41 doc: &Doc,
42) -> String {
43 let indent_w = indent_str.len();
44 let mut out = String::with_capacity(1024);
45 let mut col: usize = 0; // Current column position.
46 // Work stack (processed back to front).
47 let mut stack: Vec<Cmd> = vec![Cmd {
48 indent: 0,
49 mode: Mode::Break,
50 doc: doc.clone(),
51 }];
52
53 while let Some(cmd) = stack.pop() {
54 match cmd.doc {
55 Doc::Empty => {}
56
57 Doc::Text(ref s) => {
58 out.push_str(s);
59 col += s.len();
60 }
61
62 Doc::Line => {
63 match cmd.mode {
64 Mode::Flat => {
65 // In flat mode, a Line becomes a single space.
66 out.push(' ');
67 col += 1;
68 }
69 Mode::Break => {
70 trim_inline_trailing(&mut out);
71 out.push('\n');
72 let spaces = cmd.indent;
73 emit_indent(&mut out, spaces, indent_str, indent_w);
74 col = spaces;
75 }
76 }
77 }
78
79 Doc::HardLine => {
80 trim_inline_trailing(&mut out);
81 out.push('\n');
82 let spaces = cmd.indent;
83 emit_indent(&mut out, spaces, indent_str, indent_w);
84 col = spaces;
85 }
86
87 Doc::Nest(n, ref inner) => {
88 stack.push(Cmd {
89 indent: cmd.indent + (n as usize),
90 mode: cmd.mode,
91 doc: (**inner).clone(),
92 });
93 }
94
95 Doc::Concat(ref docs) => {
96 // Push in reverse so the first doc is processed first.
97 for d in docs.iter().rev() {
98 stack.push(Cmd {
99 indent: cmd.indent,
100 mode: cmd.mode,
101 doc: d.clone(),
102 });
103 }
104 }
105
106 Doc::Group(ref inner) => {
107 // Try flat mode: measure whether the group fits.
108 let flat_len = measure_flat(&inner, width.saturating_sub(col));
109 if flat_len.is_some() {
110 stack.push(Cmd {
111 indent: cmd.indent,
112 mode: Mode::Flat,
113 doc: (**inner).clone(),
114 });
115 } else {
116 stack.push(Cmd {
117 indent: cmd.indent,
118 mode: Mode::Break,
119 doc: (**inner).clone(),
120 });
121 }
122 }
123
124 Doc::Align(ref inner) => {
125 // Align sets the indent to the current column.
126 stack.push(Cmd {
127 indent: col,
128 mode: cmd.mode,
129 doc: (**inner).clone(),
130 });
131 }
132
133 Doc::IfBreak { ref flat, ref broken } => {
134 match cmd.mode {
135 Mode::Flat => {
136 stack.push(Cmd {
137 indent: cmd.indent,
138 mode: cmd.mode,
139 doc: (**flat).clone(),
140 });
141 }
142 Mode::Break => {
143 stack.push(Cmd {
144 indent: cmd.indent,
145 mode: cmd.mode,
146 doc: (**broken).clone(),
147 });
148 }
149 }
150 }
151 }
152 }
153
154 out
155}
156
157/// Measure the flat-mode width of a document. Returns `Some(width)`
158/// if it fits within `remaining`, or `None` if it would overflow.
159fn measure_flat(doc: &Doc, remaining: usize) -> Option<usize> {
160 let mut rem = remaining as isize;
161 let mut stack = vec![doc];
162
163 while let Some(d) = stack.pop() {
164 if rem < 0 {
165 return None;
166 }
167 match d {
168 Doc::Empty => {}
169 Doc::Text(s) => rem -= s.len() as isize,
170 Doc::Line => rem -= 1, // Space in flat mode.
171 Doc::HardLine => return None, // Cannot flatten.
172 Doc::Nest(_, inner) => stack.push(inner),
173 Doc::Group(inner) => stack.push(inner),
174 Doc::Align(inner) => stack.push(inner),
175 Doc::Concat(docs) => {
176 for d in docs.iter().rev() {
177 stack.push(d);
178 }
179 }
180 Doc::IfBreak { flat, .. } => stack.push(flat),
181 }
182 }
183
184 if rem >= 0 { Some((remaining as isize - rem) as usize) } else { None }
185}
186
187/// Emit indentation using the indent string.
188fn emit_indent(
189 out: &mut String,
190 columns: usize,
191 indent_str: &str,
192 indent_w: usize,
193) {
194 if indent_w == 0 {
195 return;
196 }
197 let full = columns / indent_w;
198 let frac = columns % indent_w;
199 for _ in 0..full {
200 out.push_str(indent_str);
201 }
202 for _ in 0..frac {
203 out.push(' ');
204 }
205}
206
207/// Remove trailing spaces and tabs from the current (last) physical
208/// line of `out`, stopping at the preceding newline.
209///
210/// This is called only at layout line breaks (`Doc::Line` in break
211/// mode and `Doc::HardLine`), which always occur in code context. The
212/// newlines that appear *inside* a multi-line string literal arrive as
213/// part of a `Doc::Text` blob and never trigger a layout break, so the
214/// interior of string literals is left byte-for-byte intact. This is
215/// what a formatter must guarantee: it may reflow code, but it must
216/// never alter the contents of a string.
217fn trim_inline_trailing(out: &mut String) {
218 while let Some(&b) = out.as_bytes().last() {
219 if b == b' ' || b == b'\t' {
220 out.pop();
221 } else {
222 break;
223 }
224 }
225}
226
227
228#[cfg(test)]
229mod tests {
230 use super::*;
231 use crate::fmt::doc::*;
232
233 #[test]
234 fn test_simple_text() {
235 let d = text("hello");
236 let out = render(80, " ", &d);
237 assert_eq!(out, "hello");
238 }
239
240 #[test]
241 fn test_concat() {
242 let d = concat(vec![text("hello"), text(" "), text("world")]);
243 let out = render(80, " ", &d);
244 assert_eq!(out, "hello world");
245 }
246
247 #[test]
248 fn test_group_fits() {
249 // Group that fits on one line.
250 let d = group(concat(vec![text("a"), line(), text("b"), line(), text("c")]));
251 let out = render(80, " ", &d);
252 assert_eq!(out, "a b c");
253 }
254
255 #[test]
256 fn test_group_breaks() {
257 // Group that does not fit on one line.
258 let d = group(concat(vec![text("aaaa"), line(), text("bbbb"), line(), text("cccc")]));
259 let out = render(10, " ", &d);
260 assert_eq!(out, "aaaa\nbbbb\ncccc");
261 }
262
263 #[test]
264 fn test_nest() {
265 let d = group(concat(vec![
266 text("fn foo("),
267 nest(4, concat(vec![line(), text("x: u32,"), line(), text("y: u32,")])),
268 line(),
269 text(")"),
270 ]));
271 // Too wide for 20 columns.
272 let out = render(20, " ", &d);
273 assert_eq!(out, "fn foo(\n x: u32,\n y: u32,\n)");
274 }
275
276 #[test]
277 fn test_nest_fits() {
278 let d = group(concat(vec![
279 text("fn foo("),
280 nest(4, concat(vec![line(), text("x: u32")])),
281 line(),
282 text(")"),
283 ]));
284 let out = render(80, " ", &d);
285 assert_eq!(out, "fn foo( x: u32 )");
286 }
287
288 #[test]
289 fn test_hardline() {
290 let d = concat(vec![text("a"), hardline(), text("b")]);
291 let out = render(80, " ", &d);
292 assert_eq!(out, "a\nb");
293 }
294
295 #[test]
296 fn test_if_break() {
297 let comma = if_break(empty(), text(","));
298 let d = group(concat(vec![
299 text("foo("),
300 nest(4, concat(vec![line(), text("a"), comma.clone()])),
301 line(),
302 text(")"),
303 ]));
304 // Fits: no trailing comma.
305 let flat = render(80, " ", &d);
306 assert_eq!(flat, "foo( a )");
307 // Breaks: trailing comma.
308 let broken = render(5, " ", &d);
309 assert_eq!(broken, "foo(\n a,\n)");
310 }
311
312 #[test]
313 fn test_align() {
314 let d = concat(vec![
315 text("let x = "),
316 align(concat(vec![text("foo"), line(), text("bar"), line(), text("baz")])),
317 ]);
318 // When broken, continuation aligns to column after "let x = ".
319 let out = render(15, " ", &d);
320 assert_eq!(out, "let x = foo\n bar\n baz");
321 }
322
323 #[test]
324 fn test_fn_signature_rust_style() {
325 // Simulates:
326 // fn generate_random_string(len: usize, charset: &str) -> String {
327 // or when broken:
328 // fn generate_random_string(
329 // len: usize,
330 // charset: &str,
331 // ) -> String {
332 let params = join(concat(vec![text(","), line()]), vec![
333 text("len: usize"),
334 text("charset: &str"),
335 ]);
336 let d = group(concat(vec![
337 text("fn generate_random_string("),
338 nest(4, concat(vec![line(), params, trailing_comma()])),
339 line(),
340 text(") -> String {"),
341 ]));
342
343 // Fits on one line.
344 let flat = render(100, " ", &d);
345 assert_eq!(flat, "fn generate_random_string( len: usize, charset: &str ) -> String {");
346
347 // Broken.
348 let broken = render(40, " ", &d);
349 assert_eq!(broken, "fn generate_random_string(\n len: usize,\n charset: &str,\n) -> String {");
350 }
351
352 #[test]
353 fn test_struct_fields() {
354 // Struct with fields.
355 let fields = join(concat(vec![text(","), hardline()]), vec![
356 text("date: CalendarDate"),
357 text("time: ClockTime"),
358 ]);
359 let d = concat(vec![
360 text("pub struct CalClock {"),
361 nest(4, concat(vec![hardline(), fields, text(",")])),
362 hardline(),
363 text("}"),
364 ]);
365 let out = render(80, " ", &d);
366 assert_eq!(out, "pub struct CalClock {\n date: CalendarDate,\n time: ClockTime,\n}");
367 }
368
369 #[test]
370 fn test_nested_groups() {
371 // Outer group broken, inner group fits.
372 let inner = group(concat(vec![text("a"), line(), text("b")]));
373 let d = group(concat(vec![
374 text("outer("),
375 nest(4, concat(vec![line(), inner, text(","), line(), text("c")])),
376 line(),
377 text(")"),
378 ]));
379 // Width 14: outer group breaks but inner group "a b" still fits.
380 let out = render(14, " ", &d);
381 assert_eq!(out, "outer(\n a b,\n c\n)");
382 }
383
384 #[test]
385 fn test_trim_inline_trailing() {
386 // Trims trailing spaces/tabs of the current line only, back to
387 // the preceding newline.
388 let mut s = String::from("hello\nworld ");
389 trim_inline_trailing(&mut s);
390 assert_eq!(s, "hello\nworld");
391
392 // Stops at the newline; does not cross it.
393 let mut s = String::from("code \n");
394 trim_inline_trailing(&mut s);
395 assert_eq!(s, "code \n");
396 }
397}