Code Formatting
How other languages decide where a line breaks, what happens to your comments, and what a formatter owes you in return for rewriting every line of your source. A survey of twenty papers (1980–2023) and thirteen production formatters, read from pinned source trees, feeding a concrete proposal for a D formatter on sparkles:dmd-lsp.
Last reviewed: August 15, 2026
The survey answers seven questions, each a dimension analyzed uniformly in every deep-dive (the fixed spine) and synthesized in the comparison:
- What does the formatter read? Token stream, full-fidelity CST, or a lossy AST — and what happens when the input does not parse. → Concepts §3, comparison §1
- How is the layout decided? Six paradigms, from "reuse the author's newlines" to "shortest path over break states". →
theory/, comparison §2 - What happens to comments? The problem with no general solution, and the three answers. → Concepts §2, layout preservation
- Who decides the style? Zero options to 6,586 lines of them. → comparison §5
- How does it prove it didn't break your code? → Verification
- What does it emit — a document or edits? The axis that decides whether an editor can use it. → comparison §6
- What should D build? → The D landscape · The substrate · The proposal
IMPORTANT
The central finding: the literature and the practice solve different halves of the problem.Hughes 1995 explicitly excludes code formatting — "not the harder problem of improving the layout of an existing text, such as a program … How should we handle comments?" — and the combinator and optimality families inherit the exclusion. Across the seven combinator/optimality papers held locally, "comment" appears zero times in four of them and only in the acknowledgements of two more. Meanwhile, in real formatters, comment handling costs two to four times what the layout engine costs: prettier's printer is 578 lines and its JavaScript comment placement is 1,255; rustfmt's comment.rs is 2,149.
The half the papers skip is solved in one small, under-cited family published in a different research community — and, in practice, by simply not throwing the tokens away.
Master catalog
One row per surveyed system, ordered by layout paradigm. Paradigm is the break-decision mechanism (developed in theory/); input is what the formatter reads; output contract is document vs edits, the axis the D decision turns on.
| System | Ecosystem | Paradigm | Input | Output contract | Deep-dive |
|---|---|---|---|---|---|
| gofmt | Go | author's-breaks + elastic tabstops | AST + comment map | document | gofmt |
| zig fmt | Zig | source-hint (trailing comma) | AST + token index | document | zig fmt |
| Roslyn | C#/VB | local rule chain | full-fidelity CST | TextEdit[] | Roslyn |
| prettier | JS/TS/CSS/… | combinator group/flat | AST + attached comments | document | prettier |
| swift-format | Swift | combinator | SwiftSyntax CST | document | swift-format |
| ocamlformat | OCaml | combinator | AST + attached comments | document | ocamlformat |
| ruff / Biome / dprint | Python, JS, … | combinator (ports) | AST | document | the Rust wave |
| black | Python | greedy + magic trailing comma | AST | document | long tail |
| google-java-format | Java | combinator (Op → Doc) | AST | document | long tail |
| rustfmt | Rust | heuristic budget (Shape) | AST + source spans | document | rustfmt |
| clang-format | C/C++/… | cost-minimizing search | token stream | Replacements | clang-format |
| dfmt | D | cost search, capped | token stream | document | dfmt |
| sdfmt | D | cost search, memoized | own parser → chunks | document | D landscape |
| dart_style | Dart | n-way constraint solver | AST → Piece tree | document | dart_style |
| scalafmt | Scala | best-first search | AST → Splits | document | cost & search |
| topiary | any (tree-sitter) | declarative from foreign CST | tree-sitter CST | document | topiary |
Foundations (theory)
| Family | What it pins down | Canonical results | Link |
|---|---|---|---|
| Oppen one-pass | linear time, bounded space, consistent/inconsistent | Oppen 1980 | oppen |
| Combinators | the Doc algebra; what ships in prettier | Hughes 1995; Wadler 1998; Lindig 2000; Chitil 2005/2006; Swierstra & Chitil 2009 | combinators |
| Optimality | what "best" means, and its price in W | Bernardy 2017; Yelland 2016; Podkopaev 2015; Porncharoenwase 2023 | optimality |
| Cost & search | the industrial approximation, and its budget | clang-format; Geirsson 2016 | cost & search |
| Layout preservation | comments, and formatting text that already exists | van den Brand & Visser 1996; de Jonge & Visser 2011 | layout preservation |
Plus readability evidence — what the empirical literature does and (mostly) does not support — kept deliberately outside theory/, because three of its four papers are dominated by non-whitespace features.
Taxonomies
By layout paradigm
| Paradigm | What decides a break | Theory | Systems |
|---|---|---|---|
| Author's-breaks-preserved | the input's own newlines | — | gofmt, Roslyn |
| Source-hint | a one-bit author signal (trailing comma, blank line) | — | zig fmt, black, prettier (partly), topiary (@append_input_softline) |
| Oppen one-pass | bounded lookahead, O(width) space | oppen | rustc_ast_pretty, OCaml Format |
| Combinator group/flat | fits on the flattened group | combinators | prettier, swift-format, ocamlformat, google-java-format, ruff, Biome |
| Cost-minimizing search | shortest path / solver over break sets | cost & search, optimality | clang-format, dfmt, scalafmt, dart_style, sdfmt |
| Declarative from foreign CST | grammar-attached formatting captures | layout preservation | topiary |
By input model & fidelity
| Input model | Round-trip | On unparseable input | Who owns comments | Systems |
|---|---|---|---|---|
| Token stream | exact | formats anyway | nobody — order is enough | clang-format, dfmt |
| Full-fidelity CST | exact | formats around errors | the token (trivia) | Roslyn, swift-format, topiary, rust-analyzer |
| AST + comment table/spans | no | refuses | a heuristic attachment module | prettier, rustfmt, black, ocamlformat, dart_style |
| AST + source line numbers | no | refuses | a position-indexed map | gofmt |
| AST-only | no | n/a | — | DMD's frontend — see the substrate |
By output contract
| Contract | Range formatting | On-type | Cursor | Systems |
|---|---|---|---|---|
Edits (Replacements / TextEdit[]) | ✅ | ✅ | ✅ | clang-format, Roslyn |
Whole document + --check | partial (prettier) | ❌ | prettier only | everyone else |
This is the axis the D decision turns on. Two systems, opposite architectures, same conclusion.
By configuration posture
| Posture | Systems |
|---|---|
| Zero options | gofmt, zig fmt, dart_style, google-java-format |
| Tiny by policy | black, prettier, swift-format |
| Large + presets | clang-format (6,586 lines of option docs), rustfmt (3,345), ocamlformat |
Delegated to .editorconfig | dfmt, Roslyn |
| The queries are the config | topiary |
Milestones
| Year | Theory | Practice |
|---|---|---|
| 1973 | Goldstein's LISP survey; the "recursive re-predictor" | GRINDEF |
| 1980 | Oppen, TOPLAS — O(n) time, O(m) space | Karlton's Mesa printer |
| 1981 | Knuth & Plass (covered in ui-layout) | TeX |
| 1995 | Hughes — and the scope disclaimer | Haskell pretty |
| 1996 | van den Brand & Visser — Box; comments by position | ASF+SDF |
| 1998 | Wadler — one associative concatenation | |
| 2000 | Lindig — the strict form prettier actually ships | |
| 2005–09 | Chitil, Swierstra & Chitil — Oppen's bound, purely | |
| 2009 | gofmt | |
| 2011 | de Jonge & Visser — text patching, comment patterns | |
| 2013* | clang-format | |
| 2015 | Podkopaev & Boulytchev — arbitrary choice made polynomial | dfmt |
| 2016 | Yelland (rfmt), Geirsson (scalafmt thesis) | |
| 2017 | Bernardy — greed provably insufficient | prettier 1.0 (2017-04-13) |
| 2018 | black | |
| 2023 | Porncharoenwase et al. — Π_e, Lean-verified | Racket fmt |
| 2023–24 | ruff-format, Biome; dart_style 3.0 tall style* |
* Not datable from this survey's evidence: llvm-project and dart_style are pinned as depth-1 clones. See the theory index's footnote.
Suggested reading paths
"I want to understand the field."Oppen → combinators → optimality → comparison.
"I am building a formatter."Concepts → layout preservation (the half the papers skip) → dfmt and clang-format (token-spine architecture) → verification → the incompleteness budget.
"I am designing the D formatter."The substrate first — it changes the assumptions — then the D landscape, comparison's delta table, and the proposal.
"I have five minutes."The Hughes remark, the incompleteness budget, and comparison §4 (what comments actually cost).
Sources
Twenty papers, seventeen archived under $REPOS/papers/code-formatting/ with pdftotext extractions for locator-precise citation; three are paywalled (Podkopaev & Boulytchev 2015; Mi et al. 2018 and 2022) and are marked 🌐 wherever used. Source trees pinned by SHA in this tree's internal grounding/_sources.md.
Every page has a claim-by-claim internal grounding ledger recording what was verified against a local artifact, what is this survey's own synthesis, and what could not be checked.