9 Greedy iterative pretty printing
The chapter introduces pretty printing as the problem of turning a parse tree back into readable source code while balancing three goals: keeping lines within a target width, preserving indentation that reveals structure, and avoiding unnecessary vertical space. It shows why real code-formatting tools must handle awkward cases such as comments, line wrapping, and language-specific punctuation, then simplifies the task to a cleaner setting with no comments, fixed indentation, spaces and line breaks only, and no required breaks. In that simplified world, the challenge becomes deciding where optional breaks should turn into spaces or newlines so that the output looks good and remains compact.
To solve this efficiently, the chapter presents a greedy approach inspired by classic work on pretty printing. The idea is to first convert the parse tree into an intermediate “doc” structure that records text, optional breaks, grouping, indentation, and concatenation, then to render that doc by fitting as much as possible on each line. A group is printed on one line if it fits; otherwise, its optional breaks become line breaks, with indentation applied where needed. The chapter walks through examples showing how nested groups and break points produce sensible layouts even when line widths are very small, while acknowledging that the result is not always globally optimal but is usually good enough.
Because the docs can become very deep, the chapter avoids recursion in the core rendering logic and instead uses an explicit work stack. One iterative method checks whether a doc fits in the remaining width, and another uses a stack of tuples to track fit mode, indentation, and the next doc to print, building the final string with a StringBuilder. The chapter then shifts to phase one, showing how to separate pretty-printing from parse-tree definitions using the visitor pattern, so the parser code does not need to absorb formatting logic. This clean separation lets an external visitor turn expressions into docs, and then into formatted text, achieving a practical, modular, and fast pretty printer.
The doc from listing 9.2 visualized as a graph. +, Grp, and Ind nodes are concatenations, groups, and indentations; quoted strings are text. I’ve also pointed out which portions are referred to by variables in the sample code. To simplify the figure, the left and right children of concatenations are sometimes shown in the “wrong” order. Notice that the graph is 17 levels deep for only 21 characters of original source code.
Summary
- Pretty printing is the long-standing problem of formatting source code in a pleasant way by balancing the use of horizontal space, vertical space, and indentation.
- Pretty printers start by parsing the program text, but this book doesn’t cover that operation. The first phase transforms the parse tree into a doc that describes the desired grouping, indentation, and line-break behavior. The second phase transforms the doc back into source code that fits in the desired page width.
- Greedy algorithms break a big problem into subproblems, find the optimal solutions to those subproblems, and combine them into a solution to the big problem. Greedy algorithms often find suboptimal solutions to the big problem but can perform better than algorithms that find optimal solutions.
- The doc data structure is a graph that can get very deep—often much deeper than the corresponding parse tree. In languages that suffer call-stack overflows, it’s often wise to make nonrecursive implementations that use an explicit
Stackdata structure. - The visitor pattern allows us to simulate adding any number of virtual methods to the base class of a tree data structure by making a few tedious modifications to the tree source code only once.
- Having an API to try out formatting policies is a powerful tool for experimentation. Generally, good library design makes it easy to express the concepts of a specific domain concisely in code.
FAQ
What is the pretty-printing problem in source code formatting?
The pretty-printing problem is to take a parse tree and turn it back into readable text while balancing three goals: keeping lines within a width limit, using indentation to show structure, and minimizing vertical space by avoiding unnecessary line breaks.Why is pretty-printing often treated as a greedy algorithm problem?
A greedy approach makes local decisions that are fast to compute, such as fitting as much as possible onto the current line. It may not always produce the globally best layout, but it usually gives a good-enough result quickly, which is ideal for editors and large codebases.What simplifications does this chapter make to the pretty-printing problem?
The chapter assumes the output contains no comments, only spaces and line breaks are valid whitespace, indentation is fixed at four spaces per level, and there are no required line breaks. These simplifications make it easier to focus on the core algorithm.What are the two phases of the greedy pretty-printing algorithm?
Phase 1 transforms a parse tree into a doc structure that describes formatting preferences. Phase 2 transforms that doc into formatted text by greedily fitting content onto each line as it is printed.What is a doc in this chapter’s pretty-printing system?
A doc is an intermediate data structure made of nodes such as text, optional breaks, groups, indentation, and concatenation. It encodes how the final source code should be laid out before the text is actually generated.What do the main doc node types represent?
TextDoc stores fixed text, OptBreakDoc stores a place where a space may become a line break, GroupDoc makes optional breaks act together, IndentDoc adds indentation after line breaks, and ConcatDoc joins two docs together.Why does the algorithm avoid recursion when implementing Fits() and Pretty()?
The doc graph can be very deep, so recursive traversal could overflow the call stack. Using an explicit work stack avoids that risk and uses only constant call-stack space.How does Fits() determine whether a doc fits on the current line?
Fits() walks the doc structure using a stack, tracking how many characters have been used so far. It returns false if the used width exceeds the limit, and true if it finishes processing the relevant docs without exceeding the width.How does Pretty() decide whether optional breaks become spaces or line breaks?
Pretty() stores a “fits” flag with each doc on a stack. When it reaches an optional break, it prints the break text if the surrounding group fits, otherwise it inserts a line break and adds the current indentation.
Fabulous Adventures in Data Structures and Algorithms ebook for free
