A greedy pretty-printing algorithm formats structured source text in two phases. It first converts a parse tree into a document, or doc, whose graph encodes text, concatenation, indentation, grouping, spacing, and optional line breaks. It then renders that doc by fitting as much as possible onto the current line before continuing later. section 9.3
The design separates layout decisions from text generation:
- Build a doc graph that expresses layout choices rather than emitting formatted text immediately. section 9.3
- Render the doc iteratively with a stack, tracking the current indentation and line width. section 9.3.4
- Treat groups as fit-or-break decisions: when a group fits, optional breaks remain spaces; otherwise, they become line breaks. section 9.3.4
- Accept that conflicting goals can produce unavoidable overflow, favoring simple, fast, good-enough formatting over perfect line widths. section 9.3.4
A narrow-width call
Formatting Foo.Bar(xx + yy * zz) at progressively narrower widths can produce: Foo.Bar(xx + yy * zz), then Foo.Bar(\n xx + yy * zz), and finally Foo.Bar(\n xx +\n yy * zz). At width 15, a final line may reach 16 characters because the algorithm avoids inserting a break before the closing parenthesis. section 9.3.4
Listing 9.4 A nonrecursive Pretty method
using System.Text;
abstract record class Doc
{
// […]
public string Pretty(int width)
{
var sb = new StringBuilder();
int used = 0; #1
var docs = new Stack<(bool, int, Doc)>(); #2
docs.Push((true, 0, new GroupDoc(this))); #3
while (docs.Count > 0) #4
{
(bool fits, int indent, Doc doc) = docs.Pop(); #5
switch (doc)
{
case TextDoc td:
sb.Append(td.text); #6
used += td.text.Length;
break;
case GroupDoc gd: #7
docs.Push((gd.doc.Fits(width - used), indent, gd.doc));
break;
case IndentDoc id: #8
docs.Push((fits, indent + IndentSpaces, id.doc));
break;
case OptBreakDoc bd:
if (fits) #9
{
sb.Append(bd.text);
used += bd.text.Length;
}
else #10
{
sb.AppendLine();
sb.Append(' ', indent);
used = indent;
}
break;
case ConcatDoc cd: #11
docs.Push((fits, indent, cd.right));
docs.Push((fits, indent, cd.left));
break;
}
}
return sb.ToString();
} }
Inspect the nonrecursive C# Pretty method to see how a stack replaces recursive traversal, groups test remaining width, and text nodes append to a StringBuilder. section 9.3.4
