An explicit stack technique replaces recursive traversal with a programmer-managed work stack. Each item records pending work and the state needed when that work resumes. In pretty printing, a tuple of (bool, int, Doc) carries break behavior, indentation, and the document being processed. section 9.3.4
A nonrecursive pretty printer processes document variants incrementally:
- Append TextDoc content and update the number of characters used on the current line. section 9.3.4
- Push a group’s child with a computed fits value so descendant optional breaks know whether to remain inline. section 9.3.4
- Increase indentation when processing an IndentDoc, and process concatenated children from left to right. section 9.3.4
- Turn an OptBreakDoc into spaces or a line break according to the saved group decision. section 9.3.4
Formatting at narrower widths
The same document can remain on one line at width 30, break once at width 20, and break more deeply at width 15, producing progressively indented output. 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();
} }
The complete C# implementation shows how tuple state, stack pushes, pattern matching, and StringBuilder output cooperate in a nonrecursive Pretty method. section 9.3.4
