Chapter 9: Greedy iterative pretty printing

Introduction

This chapter introduction frames automatic code formatting as a pretty-printing problem and previews a fast nonrecursive greedy solution and its parse-tree transformation design.

• Pretty-printing problem context: Explain why automatic code formatters, or pretty printers, are useful when a language permits many equivalent choices of spaces and line breaks. Describe the team conventions of formatting new files consistently while avoiding unrelated reformatting of existing files.
  Why it matters: Pretty printing is not merely cosmetic; consistent formatting helps teams work safely in shared codebases.
• Greedy nonrecursive formatter preview: Describe the chapter's proposed simplified pretty-printing solution as an elegant, fast greedy algorithm that finds a nonoptimal solution quickly without deep recursion. State that it uses explicit stacks and a directed acyclic graph with about a half-dozen node kinds.
  Why it matters: The chapter's central implementation approach trades guaranteed optimal layout for a fast practical formatter that avoids recursion-depth problems.
• Visitor pattern separation: Explain that compiler developers can use the visitor pattern to keep pretty-printing logic separate from parse-tree code. Describe this separation of concerns as part of transforming parse trees for formatting.
  Why it matters: Separating formatting behavior from parse-tree code makes the formatter's responsibilities clearer and keeps concerns from being mixed together.

Key terms: automatic code formatter, pretty printer, greedy algorithm, nonoptimal solution, explicit stacks, directed acyclic graph, visitor pattern, parse tree, separating concerns, pretty-printing logic

9.1 The pretty-printing problem

This section defines pretty printing as formatting a parsed expression tree under competing readability constraints and states the simplified problem used in the chapter.

• Parse tree prerequisite: Explain why a pretty printer works from a parse tree rather than directly from the original source string. State that lexing produces tokens, parsing derives the tree, and the tree identifies logical code structure such as statements, expressions, and literals.
  Why it matters: The formatter needs the code’s logical structure before it can choose whitespace that makes that structure visible.
• Formatting priority tradeoffs: Describe the three competing goals of pretty printing and their usual priority: keep lines within a specified width unless necessary, use indentation to reveal structure, and minimize line breaks. Explain that these goals can conflict, so a formatting choice balances indentation against vertical compactness after giving width the highest priority.
  Why it matters: A pretty-printing algorithm must make consistent choices when readable indentation, short lines, and compact output cannot all be maximized together.
• Simplified formatting scope: State the chapter's simplified pretty-printing assumptions: output has no comments, whitespace consists only of spaces and line breaks, indentation is four spaces per level, and expressions have no required line breaks. Distinguish this from full-language formatting, where comments and statement boundaries create additional cases.
  Why it matters: These limits define exactly which formatting cases the algorithm in the chapter is intended to handle.

Key terms: lexer, tokens, parser, parse tree, statements, expressions, line limit, line wrapping, horizontal scrolling, indentation

9.2 Greedy algorithms and making change

This section introduces greedy algorithms through change making, showing why a fast acceptable pretty-printing layout can be preferable to a slow optimal one.

• Greedy algorithm strategy: Explain how a greedy algorithm solves a large problem by choosing an optimal solution for each smaller subproblem and combining those choices. Describe both its implementation advantage and the risk that locally optimal choices may not produce a globally optimal result.
  Why it matters: Greedy choices make an algorithm simple and fast, but you must recognize when local choices do not guarantee the best overall answer.
• American change-making example: Describe the greedy change-making method for American coins: use as many higher-value coins as possible before moving to lower-value coins. Trace its result for 73 cents, and distinguish the usual optimal case from the failure when nickels are unavailable.
  Why it matters: Making change gives a concrete example of both the appeal and the limitation of greedy decision making.
• Speed versus layout optimality: Justify using a greedy pretty-printing algorithm when formatting large files in an IDE. Explain why a quick acceptable layout can be more valuable during editing than a slow optimal layout whose improvement is not appreciable.
  Why it matters: Pretty printers are interactive tools, so responsiveness can matter more than a marginally better layout.

Key terms: greedy algorithm, subproblem, optimal solution, change-making problem, quarter, dime, nickel, penny, pretty printer, IDE

9.3 A greedy pretty-printing algorithm

This section introduces the two-phase greedy pretty-printing approach and the order in which its components will be developed.

• Two-phase pretty-printing pipeline: Describe the two phases of the greedy pretty-printing algorithm: transforming a parse tree into a doc graph, then transforming that doc into formatted text.
  Why it matters: The separation between constructing layout instructions and rendering them is the organizing idea for the rest of the pretty-printer implementation.
• Doc layout representation: Explain that a doc represents desired source-code layout, including program text and rules for concatenation, indentation, grouping, spacing, and line breaks, as nodes in a directed graph.
  Why it matters: A doc captures formatting choices independently of the final line layout, allowing the rendering phase to decide what fits.
• Implementation teaching order: Trace the section's deliberately out-of-order presentation: define and visualize docs, implement phase 2 first, and then return to phase 1 because parse-tree-to-doc transformation depends on understanding grouping, indentation, and optional breaks.
  Why it matters: This order makes the parse-tree transformation easier to understand because its target layout rules have already been established.

Key terms: greedy pretty-printing algorithm, parse tree, doc, phase 1, phase 2, document, concatenation, indentation, grouping, spacing

9.3.1 The doc data structure

This section defines an immutable document representation for expressing formatting choices and illustrates how grouped optional breaks yield a greedy layout.

• Doc variant semantics: Describe the five immutable doc variants and what each represents in a formatting specification: literal text, an optional break, a group, indentation, and concatenation.
  Why it matters: These variants are the vocabulary from which the pretty printer builds and interprets formatting preferences.
• Optional break and group rules: Explain that an OptBreakDoc can stand for either its designated spacing text or a line break, while a GroupDoc makes a consistent choice for all optional breaks directly in that group, excluding nested groups.
  Why it matters: Consistent group decisions prevent a line from breaking at an arbitrary single separator while related separators remain unbroken.
• Nested expression layout example: Trace why the Foo.Bar(xx + yy * zz) doc at width 20 keeps the Foo.Bar group on the first line but breaks after the left parenthesis and indents the parenthesized contents by four spaces.
  Why it matters: This example shows how greedy fitting decisions compose through nested groups rather than selecting a break globally.

Key terms: TextDoc, OptBreakDoc, GroupDoc, IndentDoc, ConcatDoc, space break, no-space break, nested group, callfb, foobar

9.3.2 Visualizing a doc: How deep does it get?

This subsection visualizes a doc as a potentially very deep immutable directed graph and motivates iterative implementations of later formatting operations.

• Doc graph shape: Describe a doc as an immutable directed graph whose nodes have zero, one, or two child docs, and identify the visual node forms used in the example.
  Why it matters: Seeing the doc as a graph makes its nesting structure and traversal requirements concrete.
• Deep doc nesting: Explain why docs can become very deep as formatted source grows: groups and indentations are common one-child nodes, so they tend to increase depth rather than width. Relate that depth to the need to consider nonrecursive strategies for Fits(width) and Pretty(width).
  Why it matters: A formatter must cope safely with deeply nested documents instead of assuming recursion will always be practical.

Key terms: doc, immutable directed graph, concatenation, Ind, Grp, OptBreak, deep, groups, indentations, Fits(width)

9.3.3 Phase 2: Implementing Fits() without recursion

This section implements the Fits check iteratively so a pretty printer can decide whether a Doc can remain on the current line without risking call-stack overflow.

• Fits decision semantics: Explain what Fits asks—whether a Doc fits within the remaining width when all descendant optional breaks stay non-line-breaking—and trace how each Doc kind contributes to that decision.
  Why it matters: Fits supplies the greedy decision about whether optional breaks can remain inline instead of becoming line breaks.
• Explicit work-stack traversal: Describe how Fits replaces recursive calls with an explicit Stack of Docs: it pops pending docs, processes their cases, and pushes child docs representing the remaining work.
  Why it matters: An explicit work stack preserves the traversal logic while avoiding dependence on a limited thread call stack.
• Fits space and time behavior: Justify why the iterative Fits method uses constant call-stack space, why its work stack is bounded by the number of ConcatDocs, and why it is usually fast in practice.
  Why it matters: The performance argument explains why an iterative traversal is reliable even for deeply structured documents.

Key terms: Fits, Doc, TextDoc, GroupDoc, IdentDoc, IndentDoc, work-stack, Stack<Doc>, call stack, nonrecursive

9.3.4 Phase 2 continued: Implementing Pretty() without recursion

This section implements the second phase of pretty printing as an iterative Pretty method that uses explicit state to format docs efficiently.

• Iterative Pretty traversal: Describe how Pretty processes each Doc variant without recursion using an explicit work stack and a StringBuilder. Explain the actions for TextDoc, GroupDoc, IndentDoc, OptBreakDoc, and ConcatDoc.
  Why it matters: This is the formatting pass that turns the abstract doc structure into the final formatted text.
• Work-stack formatting state: Explain why each work-stack entry is a (bool, int, Doc) tuple rather than only a Doc. State that the Boolean records whether optional breaks print their text or become line breaks, and the integer records indentation to add after a line break.
  Why it matters: Carrying formatting context with every pending doc lets the algorithm remain iterative while preserving the context descendants need.
• Root grouping guarantee: Explain why Pretty wraps the requested doc in a GroupDoc before printing it: an OptBreakDoc is not guaranteed to descend from an existing group, and the added outer group ensures every optional break has a fit decision.
  Why it matters: The outer group prevents optional breaks from lacking the group context needed to choose flat text or a line break.
• Typical linear performance: State why Pretty is typically O(n) in document size: it processes every doc, calls Fits for groups, and uses StringBuilder so output construction is linear when text segments are small and indentation is not deep. Describe the intended scale as source files with thousands of characters.
  Why it matters: The iterative design is intended to make formatting large source documents fast enough in typical use.

Key terms: Pretty, StringBuilder, TextDoc, GroupDoc, IndentDoc, OptBreakDoc, (bool, int, Doc) tuple, work stack, optional break, indentation

9.4 Phase 1: Transforming parse trees with the visitor pattern

This section positions phase 1 of pretty printing as a parse-tree-to-doc transformation and motivates the visitor pattern for keeping that transformation separate from the parse-tree hierarchy.

• Three-phase pretty-printing pipeline: Describe the three phases of the pretty-printing problem: parsing source code into a parse tree, transforming that tree into a doc with grouping and indentation rules, and rendering the doc as a string.
  Why it matters: This separates the formatting-policy work of phase 1 from the layout-rendering work already completed in phase 2.
• Visitor pattern separation: Explain why putting a ToDoc-style virtual method on every parse-tree node is undesirable, and how the visitor pattern instead places each tree-processing concern in its own class without modifying the parse-tree hierarchy.
  Why it matters: Keeping operations outside the tree lets separate teams and multiple independent tools work with the same parse-tree representation.

Key terms: Phase 0, Phase 1, Phase 2, parse tree, doc, visitor pattern, parse-tree hierarchy, virtual method, ToDoc, Conway's Law

9.4.1 Implementing the visitor pattern

This section implements the visitor pattern on expression parse-tree nodes so external visitors can perform type-specific operations through double dispatch.

• Visitor interface abstraction: Explain how a generic IExprVisitor<T> represents the separate Visit methods that an abstract virtual Visit returning T would require on Expr and each derived expression type.
  Why it matters: The visitor interface lets new operations be defined outside the parse-tree class hierarchy.
• Accept-based double dispatch: Trace how expr.Accept(visitor) selects the correct visitor overload: virtual dispatch first chooses the concrete node's Accept implementation, then that implementation calls Visit with its concrete this type, allowing interface dispatch to reach the visitor's matching Visit method.
  Why it matters: Accept overcomes the fact that overload resolution cannot select a concrete Visit overload when the expression is statically typed as Expr.
• External operation extensibility: Describe the tradeoff of adding boilerplate Accept implementations to every parse-tree node: it is tedious for the parse-tree team, but it lets other teams add unrelated visitor classes that behave like new abstract Expr operations without modifying the parse-tree code.
  Why it matters: This tradeoff makes a stable parse-tree hierarchy extensible with new operations while avoiding repeated changes to that hierarchy.

Key terms: visitor pattern, visitor, IExprVisitor<T>, Expr, Id, Paren, Accept, double dispatch, overload resolution, virtual dispatch

9.4.2 From parse tree to doc

This section defines visitor rules that transform each parse-tree expression into a doc with optional breaks, grouping, and indentation for greedy pretty printing.

• Expression-to-doc formatting rules: Describe how the visitor creates docs for identifiers, parenthesized expressions, binary addition or multiplication, and member access. Explain where each form permits optional breaks, how grouping keeps related pieces together, and when indentation applies after a chosen line break.
  Why it matters: These rules determine whether the generic pretty printer produces readable expression layouts.
• Call argument-list layout: Explain the special doc-building rules for a call with a comma-separated parenthesized argument list, including the empty-list case and the placement of breaks and indentation for a nonempty list.
  Why it matters: Calls need distinct list formatting so that arguments remain readable when they no longer fit on one line.
• Width-sensitive formatting results: Describe how the completed docs respond to narrower line-width limits in the example: an 84-character one-line expression must break at width 80, then uses additional breaks at smaller widths, while the chosen rules may produce an imperfect but acceptable narrow layout.
  Why it matters: The example shows that formatting rules and available width jointly determine the output rather than guaranteeing a universally ideal layout.
• Formatting-rule experimentation: State the suggested extension: add required breaks to the doc hierarchy and devise rules for formatting statements, recognizing that the chosen pretty-printing rules can be adjusted to match formatting intuition.
  Why it matters: It highlights that a pretty printer's output quality comes from deliberate, revisable formatting rules.

Key terms: parse tree, doc, optional break, group, indentation, parenthesized expression, call, argument list, comma-separated, space break

9.5 Summary

This summary recaps a two-phase greedy pretty printer and the implementation and design lessons drawn from it.