pye 把 Wadler-Leijen pretty printer 重新拆過——document IR + 攤分的 group 決策

把一個 AST 印成「寬螢幕橫排、窄螢幕折行」的 source code，是每個 formatter（rustfmt、prettier、black）每天在做的事。Wadler-Leijen 代數提供的是一套描述「文件可能的所有版式」的小語言：用 Doc 構造節點，用 group 標記「這段可以選擇橫排或折行」，最後丟給 layout algorithm 在給定的寬度限制下挑一個版式。pye 是 Rust 上的新實作，作者觀察到——標準演算法在病態輸入下會退化成 O(n²)，而且每個實作為了避開這個雷都自己刻一套 lookahead，互不相容。pye 的回應是：把 IR、measure、render 三件事用型別徹底解耦，把 group 的決策外推到一個可以被測量代理的 streaming 過程。

Doc IR——七個變體把所有版式可能性壓成一棵樹

Wadler 原始 paper 用代數型別定義 Doc，Leijen 的 wl-pprint 加了 FlatAlt 變體支援「橫排顯示 A，折行顯示 B」。pye 的 IR 沿用這個七元組，但把每個變體的不變量寫進 Rust 的 enum 設計。文件不是「會輸出什麼字元」的 program，而是「有哪些版式可選」的陳述——layout 階段才從中挑一個。

七個變體裡，前六個是純粹的描述——它們告訴 layout algorithm「這裡有個字串」、「這裡可以選縮排」、「這兩棵子文件接在一起」。第七個 Group 才是真正的決策點：它是唯一能讓「flat 或 broken」這個布林值翻轉的構造子。pye 的設計強調這個不對稱——所有 layout 複雜度都集中在 Group 周圍，其他六個變體在實作上幾乎是免費的傳遞。

從 Rust 型別簽章看，pye 把 Doc 設計成 'a 生命週期的 borrowed enum——大部分文件節點不會被擁有（owned），而是借用 caller 持有的字串。這允許 pretty-print 一個 AST 時直接借 identifier 字面，而不是每個 token 都 alloc 一份 String。對 rustfmt-scale 的文件（一個 crate 可能展開成數十萬個 Doc 節點），這個微觀選擇直接影響 print 的吞吐量。

另一個值得展開的設計細節是為什麼不把 FlatAlt 折進 Group。直觀上 Group(Cat(a, b)) 配合 FlatAlt(flat, broken) 應該能用單一構造子表達——例如把 Group 改成 Group(flat, broken)，讓 group 自己帶兩個分支。Leijen 嘗試過這個合併，最後放棄——因為 FlatAlt 可以在 Group 外面用（譬如在一個沒被 group 包住的 hard line 旁邊放一個 trailing comma），把它跟 Group 綁死會讓某些常見模式變得難寫。pye 沿用 Leijen 的分離設計。

七個變體的選擇也隱含了「什麼不在 IR 裡」的設計決策。沒有 Choice(a, b) 構造子——Wadler 原始 paper 有這個，a <|> b 表達「選 a 或選 b 中比較好的」。但這個 choice 是 unrestricted 的——比較需要遍歷整個子樹，原文 paper 的演算法在這上面是 O(2ⁿ)。Wadler 後來自己把它限制成「group 是兩個特定分支的 choice：flatten 後的版本，跟原始版本」——這個限制讓 layout 演算法從指數變線性。pye 接受這個限制，把它寫進型別——沒有泛 choice 構造子，只有 Group 跟 FlatAlt。

還有沒有 alignment 構造子。Hughes-Peyton-Jones 風格的 pretty printer 把「對齊到當前欄」當基本操作；Leijen 風格沒有，因為對齊跟 measure 的單調性不相容——對齊後的寬度依賴它前面的內容寬度，破壞了「子樹寬度可以獨立 cache」這個性質。pye 提供 align 作為 derived combinator（用 Nest 加 current_column 巧妙組合而成），但 IR 層面沒有獨立節點——這保留了 measure 的線性性質。

群組決策的 O(n²) 陷阱——naive recursion 為什麼會炸

把 Doc 鋪平成輸出的演算法在 Wadler paper 裡叫做 best。它的工作是：給定「目前在第幾欄」、「目前該縮多少」，從根節點往下走，每碰到一個 Group 就決定要 flat 還是要 broken。問題是這個決定需要 lookahead——你必須知道「如果選 flat，這個 group 鋪平後會佔幾欄；當前欄位加上這個寬度會不會超過 ribbon width」。

naive 寫法是：碰到 Group，遞迴計算它 flat 後的寬度。算完，比較，挑分支。但這個 flat 寬度的計算本身又會碰到內層 Group——而內層 Group 的決策又會影響它 flat 寬度的計算。Wadler 原版用 lazy evaluation 在 Haskell 上裝作這個沒事，但實際求值的步數仍然可以漂亮地塞滿 O(n²)。

更精確地說：fits 函式在每個 Group 上要走一遍它的子樹計算 flat 寬度。如果 group 巢狀深度是 d、平均子樹大小是 s，那麼 N 個節點上 fits 被叫的次數約 d × s，總工作量 d × s × N。最壞情況下 d ≈ N、s ≈ N／2，工作量退化成 O(N²)。對 N = 10⁴ 級的文件，這從毫秒級變成秒級——使用者可以感覺到。

那為什麼 Wadler 跟 Leijen 沒解這個？答案是時代——1997 跟 2001 那時候，pretty printer 的典型輸入是手寫 source code，N 在 100-1000 之間，O(N²) 跑起來人類感受不到。直到 generated code（macro expansion、protobuf compiler output、ORM-generated SQL）變成 mainstream，輸入規模才大到讓退化可見。pye 是對這個 workload shift 的回應。

fn pathological(n: usize) -> Doc<'static> {
    let mut d = Doc::text("end");
    for i in 0..n {
        d = Doc::group(
            Doc::text(format!("g{}", i)) + Doc::line() + d
        );
    }
    d
}
// n = 1000 時，naive best 在 ribbon=80 下要做約 500_000 次寬度比較

fn best(col, indent, doc) -> SDoc:
    match doc:
        Group(inner) if fits(width - col, flatten(inner)):
            best(col, indent, flatten(inner))     // 走 flat 分支
        Group(inner):
            best(col, indent, inner)              // 走 broken 分支
        ...

fn fits(remaining, doc) -> bool:
    // 走過整棵 doc，累加 flat 寬度，遇 Line 失敗

best @ G0 → fits(整棵 4 層 group)         // 走完 4 個節點
best @ G1 → fits(整棵 3 層 group)         // 走完 3 個節點
best @ G2 → fits(整棵 2 層 group)         // 走完 2 個節點
best @ G3 → fits(整棵 1 層 group)         // 走完 1 個節點
// 總走訪次數：4 + 3 + 2 + 1 = O(n²/2)

這個 O(n²) 在小文件上看不出來——印 100 行 JSON 跟印 1000 行 JSON 的差距，使用者只感覺前者瞬間後者稍頓。但 formatter 不是只跑 1000 行；當它在一個 monorepo 上跑全量 format，輸入的文件樹節點數很容易達到 10⁵ 以上。Bernardy 在 2017 年的 paper《A Pretty But Not Greedy Printer》討論過——Wadler-Leijen 的 greedy decision 在某些輸入下不只慢，還會選出 sub-optimal 的版式。pye 不打算解 optimality 問題（這需要動態規劃，代價是 O(nW)），但它確實解了實作上的 O(n²) 退化。

為什麼 lazy evaluation 能在 Haskell 上「裝作沒事」值得稍微說清楚。fits 函式的工作是「走一遍 doc，累加 flat 寬度，遇到 Line 就回 false」。在 strict 語言裡這意味著整個 doc 都被走過；但在 Haskell 裡 fits 的計算是 demand-driven——如果 ribbon 容量檢查在前 10 個字元就失敗（譬如當前 column 已經很接近上限），fits 只走了 10 個字元就回 false，剩下的 thunk 被丟掉。實務上「ribbon 接近滿」的情況很常見（典型 formatter 在大部分時間都在 80 欄附近），這給 lazy 版本 O(n) amortized 的表現。

但這個「常見情況下表現好」不等於「worst case 不存在」。如果輸入剛好讓 ribbon 從來不接近滿——譬如一個極窄的 flat group 嵌在另一個極窄的 flat group 裡，外層每次檢查內層都要走完——lazy 救不了你。Bernardy 給出的具體 counter-example 是一個 N 層深的 group tree，每層只有一個短 Text 跟一個 Line，全程 fit 在 ribbon 內。這時 lazy 版本退化成 O(n²)，跟 strict 版本一樣慢。

pye 的作者觀察到：與其依賴 lazy 救命，不如直接把 lookahead 改成 measure pass。一旦 measure 把每個 group 的 flat 寬度算好了，render 階段在每個 group 上的決策成本是 O(1)——不論輸入長相多病態。代價是 measure 階段本身是 O(n)，但這個 O(n) 是必然發生的，不會因為輸入形狀爆掉。pretty printer 從「平均快但有壞輸入」變成「永遠 O(n)，常數因子比 lazy 略大」——對 production formatter 而言這是值得的交換。

Measure 階段——把寬度從遞迴拆成展平的 fold

pye 的核心觀察是：在 Group 上做決策需要的資訊不是「整個 group 的 flat 寬度」，而是「從這個 group 開始到下一個會中斷它的點之間，flat 模式下會佔多少欄」。「會中斷它的點」是指：碰到一個沒被 group 包住的 Line（強制換行）、或文件結束。這個距離有名字——文獻上叫 horizontal extent，pye 在程式碼裡直接叫 flat_width。

為什麼這個量足以做決策？因為 group 的 flat-or-broken 是局部選擇——一旦選定，這個 group 內部的所有 line 都按那個模式輸出，跟外層 group 的決策無關。pye 把這個「局部性」明確編碼進演算法：measure 階段算每個 group 的 flat_width 是 self-contained 的，外層只需把內層算好的 flat_width 加上自己的 inline 內容寬度，往上累。

這跟 dynamic programming 的精神一致——把「決策」拆成「準備子問題答案」跟「組合子答案」。Wadler 的原版沒這個拆分，因為 Haskell 的 lazy evaluation 隱式做掉了。pye 在 strict 語境下顯式做：先一遍 post-order 算所有子答案，再一遍 pre-order 做所有決策。兩 pass 共 O(n)，遠勝單 pass O(n²)。

把 flat_width 從遞迴算法改成 measure pass 的好處是：每個節點只被走訪一次。pye 的 measure 走一遍 Doc tree，給每個 Group 節點 cache 它的 flat_width——後續 layout 階段在這個 group 上做決策只需要 O(1) 讀取。整個 measure 走訪是 post-order 的 fold：

struct Measured<'a> {
    doc: &'a Doc<'a>,
    flat_width: u32,      // 此節點 flat 模式下佔幾欄
    has_break: bool,      // flat 模式下是否含未被群組包住的 Line
}

fn measure<'a>(doc: &'a Doc<'a>) -> Measured<'a> {
    match doc {
        Doc::Empty => Measured { doc, flat_width: 0, has_break: false },
        Doc::Text(s) => Measured { doc, flat_width: s.width() as u32, has_break: false },
        Doc::Line => Measured { doc, flat_width: 1, has_break: true },
        Doc::FlatAlt(flat, _) => {
            let m = measure(flat);
            Measured { doc, flat_width: m.flat_width, has_break: m.has_break }
        }
        Doc::Cat(a, b) => {
            let ma = measure(a);
            let mb = measure(b);
            Measured {
                doc,
                flat_width: ma.flat_width.saturating_add(mb.flat_width),
                has_break: ma.has_break || mb.has_break,
            }
        }
        Doc::Nest(_, inner) => measure(inner),  // nest 不影響 flat 寬度
        Doc::Group(inner) => {
            let m = measure(inner);
            Measured { doc, flat_width: m.flat_width, has_break: false }
            //                                       ^^^ group 一旦選 flat，內部 Line 都變空白
        }
    }
}

關鍵點在 Group(inner) 的 has_break: false——這是說，當 layout 決定讓這個 group flat 時，內部所有 Line 都被視為空白，所以從外層看這個 group 是「flat-able」。如果 group 內部有 FlatAlt，measure 取 flat 子樹的寬度。如果 group 內含另一個 group，內層 group 的 flat_width 已經是它 flat 後的寬度，外層直接加上去就好——這就是為什麼能避開 O(n²)：寬度資訊由下往上 cache，不需要在每個外層節點重新展開內部。

這個「向上傳遞 cached width」的模式跟 incremental computation 的精神是一致的。GHC 的 STG machine、Roc 的 compiler、Salsa-style 的 query system，核心都是「子結果 cache 一次，父結果用 cache 算」。pye 把這個 idiom 帶進 pretty printer——讓 measure pass 成為一個顯式的「子問題求解」階段，render pass 成為一個顯式的「組合子答案」階段。

實作上 measure pass 用迭代 explicit stack 而非遞迴——同樣是為了避開深度限制。pye 用 Vec<&Doc> 當作 post-order traversal 的 stack，每個 Doc 被 visit 兩次：第一次標記為「展開了，但子結點還沒處理」，第二次標記為「子結點都處理完了，可以算 flat_width」。這個 two-pass-visit 是 explicit post-order traversal 的標準作法。

measure 階段走訪每個節點恰好一次，時間複雜度 O(n)；空間上每個節點額外吞 (u32, bool) 八個 byte（加 padding）。對 10 萬節點的文件，measure 的 overhead 是 800 KiB 上下，遠小於 Doc 本身。

實作上有一個值得注意的細節：flat_width 用 u32 而不是 usize。Wadler-Leijen 系演算法的 ribbon width 通常是 80 或 120，極少超過 200；單一 group 的 flat 寬度也很少超過幾百欄（更長的內容會被外層 group 強制換行）。u32 上限是 4 GiB 欄寬，遠超實際需求，但相對 usize 省下 4 byte。對熱迴圈裡的 measure cache 結構，這個窄化能讓 cache line 多塞兩個 entry。

saturating_add 而不是 wrapping 或 checked 是另一個選擇。理論上 flat 寬度不可能溢位——如果 doc 真的有 4 GiB 寬度，pretty printer 也救不了。但 saturate 的好處是：即使輸入是某種 adversarial 構造，measure 不會 panic，render 階段拿到 saturated max 值就會直接走 broken 分支。整個 measure pass 在 release build 是 panic-free 的——這對 library code 是很重要的性質。

還有一個微妙的選擇：Measured 結構體攜帶 &'a Doc<'a> 反向引用回原始節點。這個冗餘讓 render 階段在 stack push 時可以直接拿到 (Measured, mode) 配對，不需要分別維護兩個 stack。代價是 Measured 比 raw 寬度大；好處是 render 的 stack frame 結構更乾淨。pye 在這點上選擇可讀性。

Render 階段——四狀態有限機與 group 的 streaming 決策

measure 跑完以後，render 階段拿著一個「已標註寬度」的 Doc tree，從根節點開始往輸出 buffer 寫字。Wadler 原版用一個 explicit stack 模擬遞迴（避開 Haskell 的 stack overflow），pye 沿用這個結構但把 stack frame 設計成可以表達四種待辦狀態——這就是文件標題裡的「攤分的 group 決策」的本體：

為什麼用 stack 而不是 native recursion？因為 pretty printer 的輸入可以非常深。一個 lisp 程式碼可能有上千層的 paren；一個從 protobuf 自動生成的 Doc 樹可以巢狀十萬層。Rust 的預設 thread stack 是 8 MiB，每個 stack frame 通常 0.5-1 KiB——能容納幾千層遞迴，但不能容納幾萬層。Explicit stack 把這個上限抬到「heap 容量」的等級，本質上沒有深度限制。

狀態機 push/pop 自己的 stack 而不是用 native call stack——這是 pretty printer 的標準作法，理由是文件深度可以遠超 OS 給的 thread stack（10 萬層 nested expression 不是病態輸入，是 generated code 的常態）。pye 的 stack frame 是上面四個 variant 的 enum，Resume 跟 Indent 是被動的，TryFlat 跟 ForceBreak 才是決策的結果。

決策本身在 Group 第一次被 push 上 stack 的瞬間就完成——根據 measure 階段預先算好的 flat_width 跟「當前欄位 + ribbon width」比較，立刻決定下推 TryFlat 還是 ForceBreak。後續所有 Line 在這個 group 範圍內遇到時，只要看 stack top 是 TryFlat 還是 ForceBreak，就知道該寫空白還是換行——不需要回頭問外層。

這個 streaming 性質是「攤分」的本意：每個 Group 節點的決策只發生一次，後續所有受它影響的 Line 是 O(1) 查表。從外面看 render 階段是 single-pass linear scan——measure 階段把所有需要 lookahead 的計算前置，render 階段把所有決策動作 amortize 到 stack push 時點。

四個狀態的選擇值得進一步解釋。Resume(d, k) 是「繼續處理子節點 d，繼承父層的 layout mode k」——這是大部分時候 stack 上的內容。當演算法走進一個 Cat([a, b, c])，它把 Resume(c, k)、Resume(b, k)、Resume(a, k) 依序 push（反向推因為 stack 是 LIFO），下一輪 pop 出 Resume(a, k) 處理。這個機械式的反向 push 是 explicit-stack iterative traversal 的標準作法。

Indent(i) 是「離開當前 nest 範圍，把縮排層級回到 i」。當演算法進入 Nest(i, d)，它先 push Indent(current_indent) 作為恢復標記，然後把 current_indent 加上 i，再 push Resume(d, k)。當 Resume(d, k) 處理完了，pop 到 Indent(current_indent)，把 indent 還原。這個 explicit 的恢復棧避開了 native call stack——重要，因為 Rust 的 thread stack 預設 8 MiB，深度遞迴的文件可能塞不下。

TryFlat(d, k) 跟 ForceBreak(d, k) 是 Group 決策的結果。TryFlat 標記「這段的所有 Line 印成空白」；ForceBreak 標記「這段的所有 Line 印成換行」。決策本身在進入 Group 時做一次——拿 flat_width 跟 remaining = min(page, ribbon) - current_col 比較。flat_width ≤ remaining 就 push TryFlat，否則 push ForceBreak。

分開兩個變體而不是一個 Group(mode, d, k) 是為了讓 render 主迴圈的 match arm 直接 dispatch，不需要再讀 mode 欄位。對熱路徑的 single-byte discriminant 分支預測友好——pye 的 micro-benchmark 顯示這個拆分讓 render 吞吐量比合併版本高約 6%。在「pretty printer 是 formatter 熱路徑」的 use case 下值得。

這是 Rust enum 設計的一個小但實質的技巧——把「邏輯上的布林參數」拆成兩個 variant，讓 match 在 discriminant 比較階段直接分流，省一次欄位讀。pattern matching 對 enum 的優化在 LLVM 後端已經很成熟，但前提是 variant 多到值得分流。pye 在熱迴圈裡選擇這個寫法是 perf-driven 的決策。

// step 03 · group 決策完成
┌ TryFlat(inner, k=4) ◀ top
│ Indent(0)            
│ Resume(text(";"))    
└ (bottom)             

// step 05 · TryFlat 內部走過
┌ Resume("+ 3", flat) ◀ top
│ Indent(0)            
│ Resume(text(";"))    
└ (bottom)             

// step 07 · 全部 pop 完
┌ (empty) ◀ render done
└ output: "let x = 1 + 2 + 3;"

有一個值得提到的邊界情況：Group 內含 hard Line（沒被任何子 group 包住的 line）。measure 階段把這個 group 的 has_break 設為 false，但 flat_width 仍然會算——因為 Wadler-Leijen 語義上 Group(d) 嘗試把 d flatten，flatten 的定義是「把 Line 換成空白」。所以即使 d 含 hard line，flatten 後仍有「全部攤平」的版本。pye 的處理是：如果 flat_width ≤ remaining，TryFlat 還是會生效——這是 Leijen 原版的行為，pye 沿用。

Rust 落地——型別、ribbon、builder API

怎麼把這套表達出來——Cow、SmallVec、Iterator

把上面的演算法落地到 Rust，主要的工程張力在三個地方：怎麼避免 unnecessary allocation、怎麼避免 stack overflow、怎麼讓 caller 既能 streaming 消費輸出也能 collect 成 String。pye 的選擇：

這三個張力對應到 Rust 的三個慣用語：Cow 給 ownership 的 polymorphism；SmallVec 給 small-size optimization；impl Iterator 給 lazy / streaming。每個都是 Rust 生態系從 2015 到 2025 的累積——直接拿來組合，pye 的核心程式碼只有 600 多行就能完整實作 Wadler-Leijen。

pub enum Doc<'a> {
    Empty,
    Text(Cow<'a, str>),
    Line,
    FlatAlt(Box<Doc<'a>>, Box<Doc<'a>>),
    Cat(SmallVec<[Doc<'a>; 4]>),
    Nest(u16, Box<Doc<'a>>),
    Group(Box<Doc<'a>>),
}

impl<'a> Doc<'a> {
    pub fn render(&self, width: u32) -> impl Iterator<Item = &str> + '_ {
        Renderer::new(self, width)
    }
}

三個小選擇值得展開。第一，Cat 不是二元而是 SmallVec。Wadler 代數上 Cat 是二元的，但 builder API 把連續的 + 操作平攤成 N-ary 後，measure 跟 render 都不必處理深度遞迴。SmallVec<[Doc; 4]> 在 ≤ 4 個子節點時 inline 儲存，避開常見短文件的 heap allocation。

第二，render 回傳 impl Iterator<Item = &str> 而不是 String。caller 可以 .collect::<String>()、可以直接寫進 io::Write、可以 stream 到 socket——pye 不替使用者做 buffer policy。Item 是 &str 不是 char，因為大部分輸出是長字串連續寫出（一個 keyword、一個 identifier），逐字元 yield 會把 iterator overhead 變成主成本。

第三，Nest(u16, Box<Doc>) 用 u16。usize 在 64-bit 平台是 8 byte；u16 是 2 byte。對於一個會在熱路徑被 millions 次 match 的 enum，這個窄化讓整個 Doc variant 的最大 size 從 32 byte 降到 24 byte——多少 cache line miss 因此被省下，需要 perf 才能告訴你。

有一個跟生命週期相關的工程張力值得提：當 caller 用 format!("g{}", i) 動態建構字串時，這個字串是 String（owned），不是 &str（borrowed）。pye 的 Text(Cow<'a, str>) 用 Cow 同時容納兩者——Cow::Borrowed(&'a str) 對靜態字面，Cow::Owned(String) 對動態字串。差別在 size：Cow 是 24 byte（discriminant + 16 byte payload），&str 是 16 byte。pye 接受這個 8 byte 的代價，換來 API 的靈活性。

Box<Doc> 而不是 Doc 直接遞迴是 Rust 的固定模式——遞迴型別必須間接化才能定 size。pye 選 Box 而不是 Rc 或 Arc，因為大部分文件是建構一次、render 一次後丟掉，引用計數的 overhead 純粹是浪費。對需要重複 render 同一份 Doc 的 caller，pye 提供 Doc::shared 把 Box 升級成 Arc——這是顯式的選擇，不是預設成本。

這個「預設選最便宜的、需要進階能力時顯式升級」的設計哲學，是 Rust library 的常見模式。String vs Cow、Vec vs SmallVec、Box vs Arc——每一對都是「便宜版」跟「進階版」的選擇。pye 在這個維度上做得徹底：每個型別決定都有明確的 trade-off rationale 寫在 doc comment 裡。

Iterator 介面的另一個好處是背壓。如果 caller 是 BufWriter，內部 buffer 滿了會 block；pye 的 Iterator 自然處理這個——下一次 next() 才繼續計算下一段。如果 caller 想要 timeout、想要 cancel、想要 progress reporting，把 iterator 包一層就好——pye 不需要為這些 use case 新增 API。這是 Rust iterator 一貫的 composability 優勢，pretty printer 剛好特別適合 stream。

Ribbon width vs page width——兩個寬度限制怎麼合作

Wadler-Leijen 對「合適的寬度」用兩個變數描述：page width（整列的硬上限）跟 ribbon width（在縮排之後，內容可用的「軟上限」）。前者通常是 80 或 100；後者通常是 page width − 縮排層數。兩個分開是有意義的——一個深度縮排的表達式即使橫排了也可能因為被縮進太多而超出 page width，這時候要不要強制換行，是 ribbon width 在管。

具體場景：你在第 60 欄縮排內寫一個 group，page width 是 80。group 的 flat 寬度是 30——加上 current_col 是 90，超 page width。直觀上應該選 broken。但如果 ribbon 是 60——只看「縮排之後內容寬度上限」——這個 group 的 flat 內容只佔 30，遠在 ribbon 之內，按 ribbon 規則應該選 flat。Wadler-Leijen 的決策是 min(page - current_col, ribbon)——兩個限制取嚴的。pye 直接遵循。

下方的小工具讓你拖兩個 slider 看 layout 怎麼隨之變。試試把 page 設 80、ribbon 設 30——struct 的所有 field 都會換行；把 ribbon 拉到 90——struct 變成一列。注意 page 跟 ribbon 不是線性疊加的——它們各自獨立 binding，layout 取嚴。

實作上 pye 對這兩個寬度的處理是：layout 階段比較的是 current_col + flat_width ≤ min(page, ribbon)。如果 ribbon 比 page 小，ribbon 是 binding constraint；如果 page 比 ribbon 小（caller 把 ribbon 設得太寬），page 接手。當兩個都管不住——比方說一個 identifier 比 page width 還長——pye 不會試圖把它切開，而是讓那行 overflow。pretty printer 不是 word-wrap 工具，它的工作是挑分支，不是拆原子。

這個「認賠」的選擇有實務理由：嘗試 wrap atom 會把 layout 跟 token 層耦合，那是 prettier 走的路（它知道 JavaScript 識別符號的命名規則），代價是 pretty 邏輯被綁死在語言上。pye 走 Wadler-Leijen 路線——layout algorithm 對輸入 token 的內部結構不假設任何事，超寬就讓使用者自己看著辦。這也是為什麼 rustfmt 在處理 200 字元的 identifier 時不會切——切了會破壞 syntax；layout 演算法把這個邊界守得很清楚。

ribbon 跟 page 分離還有一個少被討論的好處：讓縮排敏感的內容好讀。考慮一個八層深的巢狀 JSON——如果 page width 是 80、ribbon width 也設成 80，每進一層 nest 4，到第六層後內容只剩 8 欄寬，layout algorithm 還是會試圖讓內容 fit 在 80 欄裡（page width），結果是 broken 模式下右側留白極大、極窄的內容貼著縮排。把 ribbon 設成 60，演算法會在第二三層就強制換行，保留閱讀節奏。

Leijen 把這個用 ribbonFrac 參數參數化——讓使用者指定 ribbon 是 page 的多少倍（譬如 0.75）。pye 延續這個 API：renderer.set_ribbon_frac(0.6) 在 page width 100 時把 ribbon 設成 60。實作上 ribbon 在 measure 階段不用——measure 算的是 flat width，跟視窗無關；只有 render 階段在比較 current_col + flat_width 時才會用到 min(page, ribbon)。

還有一個 Wadler 原版沒處理、Leijen 加進來的邊界情況：第一行的縮排不算 nest。當 caller 從非零 column 開始 render（譬如把 pretty 結果嵌進已經印了一半的句子），第一個 group 的 ribbon 比較應該扣掉 starting column。pye 的 render 接受 start_col 參數讓 caller 指定起點——這是 prettier 跟 pretty.rs 都做的事，pye 沿用。

對照同類實作——pye 在生態系裡的位置

Wadler-Leijen 演算法在生態系裡至少有三條主流實作血脈：Haskell 上的 prettyprinter（Leijen 系，cabal-install / pandoc 都在用）、Rust 上的 pretty.rs（Andy Lokhorst 維護，rustfmt 早期版本基於它）、以及 OCaml 上的 PPrint（François Pottier 維護）。三者都支援 group、nest、FlatAlt，但對 O(n²) 退化的回應不同。

三個實作的差異可以從一個維度概括：什麼時候算 flat 寬度。Haskell 在「需要時」算（lazy）；pretty.rs 在「進入 group 時」算（eager）；PPrint 跟 pye 在「建構 doc tree 後一次性算所有」（measure pass）。三種策略各有 trade-off，沒有單一答案——對 short-lived doc lazy 最快、對長 doc measure pass 最穩、對中等規模 doc eager 簡單。pye 押注「中到大規模 doc 是主流」，賭注是 measure pass 的 amortized 成本可接受。

Haskell prettyprinter 靠 lazy evaluation 在實際輸入上避開 worst case——fits 函式在第一個 newline 之後立刻 short-circuit，搭配 GHC 的 thunk fusion，大部分輸入的 amortized 複雜度是接近 O(n)。但這個性質是應急性的：lazy 在 strict 語言（Rust、OCaml）上不容易複製，而且就算在 Haskell 上，「在 sufficient-width ribbon 下退化」的 worst case 仍然存在。

pretty.rs 採用顯式的 fits + memoization。每次進入 Group 它都會跑一遍 fits，但在實作上限制 fits 只看到 next break。這個 cutoff 在絕大多數輸入上把 amortized 複雜度壓回 O(n)——代價是某些深度嵌套的 corner case 仍然會退化。pretty.rs 的 README 直接承認這點，建議在 pathological 輸入上手動拆 group。

pye 的選擇是把 measure 階段分出來——它顯式跑一次完整的 post-order traversal，付出 O(n) 的時間與空間，換來 render 階段嚴格 O(n) 沒有 corner case。對小文件這個 measure pass 是 overhead；對大文件這是「保證不會炸」的代價。pye 的 builder API 還支援 Doc::eager——把 measure 結果跟 Doc 一起 cache，多次 render 同一份文件不需要重跑 measure。

有趣的是 OCaml 的 PPrint 用了類似 pye 的「分階段」想法——François Pottier 把 layout 拆成「需求計算」跟「印出」兩階段，理論上的最壞複雜度是 O(n)。pye 的設計顯式向 PPrint 致敬，但實作上多了幾個 Rust 特有的工程細節：SmallVec 攤平 Cat、u16 緊縮 Nest、impl Iterator 而非 String 回傳。這些是「Rust 上做這件事的當代寫法」——不是演算法本身的貢獻，但是把演算法落地成可用 crate 的工程選擇。

從生態系角度看，rustfmt 跟 prettier 都不會立刻換成 pye——這類專案有自己的 layout 需求（rustfmt 的 vertical alignment、prettier 的 conditional groups），跟通用 Wadler-Leijen 不完全一致。pye 的目標讀者是「想印 AST、想印 SQL plan、想印 graph database query」這類中度複雜輸出的 library 作者——他們需要 pretty 邏輯，但不需要 fork 一份 prettier 來改。

另一個有趣的比較點是記憶體 footprint。prettyprinter 在 GHC 上靠 thunk 共享達到極低 working set；pretty.rs 因為 strict 求值，每個中間文件節點都實體化在 heap 上，記憶體用量比 Haskell 版高 2-3 倍。pye 的 measure pass 加重了這個負擔——多了一層 Measured 結構——但 Cow 跟 SmallVec 把這個損失補回來。實測上 pye 在大文件（10⁵ 節點）上的記憶體峰值跟 pretty.rs 接近，比 prettyprinter 多大約 60%。

對於 caller 在意「重複 print 同一份 doc」的場景——譬如把同一個 AST 用不同 ribbon width 多次 render——pye 的 Doc::eager 變體把 measure 結果一起 cache。後續 render 只跑第二階段，時間是 O(n) 而且常數因子比 first-time render 小 30%。這是 pye 相對 pretty.rs 的另一個小但實質的勝利。

OCaml PPrint 提供了一個 pye 沒做的功能：富文字輸出。PPrint 的 Doc 可以攜帶 colour、style 標記，render 階段把這些標記翻譯成 ANSI escape 或 HTML span。pye 0.1 沒做這個，但 Doc enum 預留 Annotate 變體的空間——0.2 預計加上。這個延後是有意識的——先把 O(n) 性質鎖住，再加 annotation。

建構器 API——為什麼 + 跟 / 不是 macro

使用者建構 Doc 的方式對人因影響很大。Wadler 的代數有 <>（接合）、<|>（選擇）、<+>（空白接合）、$$（換行接合）四個常用算符；Haskell 用 infix operator 直接表達。Rust 沒有自訂 infix，pye 的選擇是 Add trait 重載 + 作為 Cat，跟 Div 重載 / 作為「換行接合」（$$）。其他算符靠 method chain。

用 + 跟 / 重載是有爭議的——對不熟悉這個習慣的讀者，a / b 看起來像數字相除而不是「a 接 b 中間放一個 line」。pye 文件強調這個 convention 並提供 .line_with(b) 作為清楚版本給偏好 verbose 的使用者。但 / 的好處是 method chain 寫起來很流暢——pretty printer builder 經常一行寫到 80 欄，operator overload 把它壓到一半長度。

use pye::*;

// "let x = " <> group("1 + 2 + 3" 縮排 4 折行) <> ";"
let doc =
    text("let x = ")
    + (text("1") + line() + text("+ 2") + line() + text("+ 3"))
        .nest(4)
        .group()
    + text(";");

// 印到 80 欄
println!("{}", doc.render(80).collect::<String>());
// 縮短 ribbon 到 20 欄
println!("{}", doc.render(20).collect::<String>());

選擇 + 而不是 macro 的理由：macro 在 IDE 補全、type inference、error message 上都比 method chain 差。method chain 的代價是「不能 short-circuit」——Empty + d 還是會走 Add::add，需要在 method 內手動跳過 Empty 維持 monoid 不變量。pye 在 Add::add 裡 fast-path 掉 Empty，這個成本相對 layout 階段是噪音。

更微妙的選擇是 group() 的位置。Wadler 代數上 group 是 prefix function；pye 上是 method on Doc——d.group() 而非 group(d)。這讓 method chain 讀起來像「先建構這段 doc，然後 nest 它，然後 group 它」——跟人在想「這段文件的版式變換順序」的思路一致。Haskell 上同樣選擇的是 François Pottier 的 PPrint API，pye 在這點上向 OCaml 借鏡。

Builder 的另一個常見痛點是「兩個 doc 之間夾換行」——Wadler 用 $$ 表達，Leijen 改名 line + 接合。pye 提供 Doc::lines helper：Doc::lines([a, b, c]) 等於 a + line() + b + line() + c。這是一個小但常用的 sugar——typical pretty 文件裡 80% 以上的 cat 是「X + line + Y」結構，把它命名為 lines 讓 caller 的程式碼少一半的 ceremony。

還有 Doc::comma_sep——「以逗號 + 空白/換行接合一群 doc，每兩個之間放可 group 的 line」。這對印 function call argument、struct field list 是最常見模式。Leijen 上對應的是 punctuate (comma <> line)，可讀性差；pye 直接給名字。這類 helper 看起來瑣碎，但對日常使用者體驗影響很大——一個 pretty printer library 的 80% builder code 都在拼這幾種模式。

留下的開放問題——optimality、conditional group、annotation

pye 解了 O(n²) 退化，但沒解 optimality 問題——Wadler-Leijen 的 greedy 決策會在某些輸入上選出非最短的版式。Bernardy 2017 給出一個顯式 counterexample：兩個並排的 group，外層 group flat 時內層必須 broken，但 greedy 算法可能反過來選——導致整體比 optimal 多出幾行。修這個需要動態規劃，狀態空間 O(nW)，這對 W=80 跟 n=10⁵ 的輸入是 8 × 10⁶ 的 table——可控但不便宜。pye 的決定是「greedy 在絕大多數實務輸入上夠用」，把 optimal 留給 future work。

greedy 跟 optimal 的差距在實務上有多大？Bernardy 的 paper 給出實驗：在 Haskell pretty-print 的標準 benchmark 上，greedy 版本的輸出行數平均比 optimal 多 2-3%。最壞 case（人工構造的 adversarial input）可以差 20-30%。對 formatter 來說 2-3% 不痛——使用者不會注意；對 code-golf 或受限頻寬的 protocol，這個差距可能 matter。pye 的 use case 偏 formatter，greedy 是合理選擇。

Prettier 風格的 conditional group——「如果這個 group 選 flat，那個 group 也選 flat」——也不在 pye 的 IR 範圍內。Wadler-Leijen 代數設計上 group 是獨立決策，跨 group 的條件相依需要更強的 IR。pye 維持 Wadler-Leijen 的純度，意味著它印不出某些 prettier 印得出來的版式（最有名的是 chained method call 在父鏈展開時要連動展開子鏈）。對這類需求，pye 的建議是把整段一起當一個 group 處理，或者用 FlatAlt 手動編排兩個版式。

另一個生態系功能是 annotation——讓 Doc 帶上 metadata，render 時觸發 colour、hyperlink、source-map 之類的副作用。Haskell prettyprinter 有 Doc ann，pretty.rs 也支援。pye 在 0.1 版本沒做，但 Doc enum 預留了未來加 Annotate(A, Box<Doc>) 變體的空間——這個擴展不會影響 O(n) 性質，因為 annotation 在 measure 階段是 transparent，在 render 階段是 O(1) 的 sink 寫入。

第四個值得放在 TODO 的是 derived line break preferences。實務上常見的需求是：「優先在這些位置換行；不得已才在那些位置換行」——譬如 SQL formatter 偏好在 FROM / WHERE 之間換行而不是 SELECT 列之間。Wadler-Leijen 代數沒有 priority 概念；prettier 用 conditionalGroup 跟 indentIfBreak 表達。pye 目前沒有 priority——caller 要自己用 FlatAlt 手刻偏好的版本。這個 IR 擴充比 annotation 更影響演算法核心，pye 路線圖上沒有時間表。

最後一個 limitation：pye 不處理東亞字寬（CJK fullwidth）。Text::width 算的是 Unicode codepoint 數而非 East Asian Width 屬性下的 display column。對純 ASCII 的程式碼這沒問題；對混 CJK 註解或字串的源碼，layout 算的 width 跟實際螢幕欄寬會錯。修這個需要在 measure 階段查 Unicode 表，常數因子變慢 20-30%。pye 把這個選擇留給 caller——提供 Text::with_width 讓 caller 預先算好 display width 自己塞進去。

什麼時候不該用 pye——當 pretty 不是真的 pretty

pretty printer 對「輸入是樹狀、輸出是行寬限制下的文字」的場景最有效。但實務上不是每個 pretty 需求都長這樣。三個邊界場景：

Pretty printer 的核心抽象是「輸入是組合構造、輸出是受限文字流」。當輸入不是組合構造（譬如已經是字串模板），或輸出不是受限文字流（譬如要寫進 GUI 的 rich text），這個抽象就不貼合 problem。強推 pretty printer 進去這些場景，會得到 over-engineered 解法。

第一，逐 token 已知 layout。如果 caller 已經知道每個 token 該換行還是該接著（譬如從另一個已 format 的源頭轉換），用 pretty printer 是繞遠路——直接寫字串。pye 的 layout 邏輯對「無選擇」的輸入仍然是 O(n)，但 constant factor 比直接 print 高。

第二，需要對齊（vertical alignment）。Wadler-Leijen 代數本身沒有 align 構造子——對齊一群東西到同一個欄位是 Hughes-Peyton-Jones 風格的領地。Leijen 加了 align 跟 hang 的 derived combinator，但這些在 worst case 下仍可能讓 measure 階段失效。pye 提供 align combinator，但建議只在 group depth ≤ 3 時用——更深的 alignment 會讓 flat_width 的快取結構失準。

第三，輸出不是純文字。Markdown table、HTML attribute、SQL CTE——這些有「邏輯結構」不純粹是「行寬決策」的格式，pretty printer 印得出但不見得印得漂亮。pye 對這類場景的態度是：先用 pretty printer 印骨架，再用 domain-specific 後處理修細節。

還有一個常被低估的場景：需要 round-trip。如果 caller 想要「print, parse, print 仍得到同一個輸出」，pretty printer 是危險選擇——因為 layout 決策跟 ribbon width 綁定，第二次 print 時 ribbon 可能稍有不同就走不同分支。對 round-trip 敏感的場合（譬如 source code refactor），pretty printer 應該被當成最後一步，而不是中間 IR。pye 沒有提供 round-trip 保證的 API；這是 Wadler-Leijen 框架本身的限制。

把 pye 跟它的同類比一比：對需要列印中度複雜 AST 的 Rust library 作者——譬如寫一個 SQL parser 想印回美觀 SQL、寫一個 query optimizer 想印 plan tree、寫一個 IR debugger 想印 SSA form——pye 是 2026 年的合理預設。對已經在 prettier 上的 JavaScript 生態——不需要動。對rustfmt——它的 needs 已經超出通用 Wadler-Leijen 能表達的範圍，自己 fork 一份是對的。pye 不試圖 boil the ocean，它把一個明確定義的問題解到 production-ready。

從演算法演進的角度回看：Wadler 1997 給了乾淨的代數；Leijen 2001 加了實用構造子（FlatAlt、align）；Pottier 在 PPrint 上把 measure 跟 render 分階段；Bernardy 2017 證明 greedy 不是 optimal、給出 O(nW) 的 optimal 演算法；pye 2026 把這些 collective wisdom 整理進 Rust 慣用語。每一代都不是「重新發明」——而是把前人的設計選擇做更顯式的取捨。pretty printer 這個小 corner 三十年的演進，能看出整個 PL 社群「先要正確，再要簡單，再要快」的折返軌跡。

有趣的是這個演進並不是線性的——Bernardy 的 optimal 演算法在 2017 發表後，並沒有取代 greedy 成為主流。原因是 optimal 的 O(nW) 在實務上常數因子比 greedy 大 10 倍以上，而 greedy 的「次優」差距通常在 2-3%——這個 trade-off 對大部分 formatter 場景不值得。pye 接受這個工程現實，把火力集中在「greedy 不退化」上而不是「保證最優」。

對讀完這篇文章還想動手的讀者：pye 的 source code 大約 1500 行 Rust（含 doc 註解），結構上 IR / measure / render 三個檔案各 500 行左右，依賴 smallvec 跟 unicode-width 兩個 crate。從零實作這個演算法不會超過一個週末——讀懂背後的 Wadler-Leijen 代數可能要花更久。如果你正在寫 SQL formatter、protobuf descriptor printer、graph query plan visualizer，pye 是一個值得評估的依賴；如果你只是想學 IR design 的精神，pye 的 source 是一份小而完整的範例。

對 Rust 開發者，pye 的價值不只是「另一個 pretty printer」——它是一個示範：怎麼把 Haskell 上 lazy-evaluation-dependent 的優雅演算法搬到 strict 語境而不損失複雜度保證。同樣的思路可以套到 lazy stream processing、incremental computation、build system 等場景——把 lazy 的「按需求值」翻譯成 strict 的「分階段預算」。這個 idiom translation 比演算法本身更通用。

從 library 設計角度，pye 還示範了一個常被忽略的原則：把性能保證寫進型別簽章。Doc::eager 跟 Doc::lazy 在型別層面顯式表達 measure cache 的存在；render 回傳 impl Iterator 顯式表達 lazy 的 streaming 性質。caller 看 API 就知道效能 contract，不用看 implementation。這對 library 的長期可維護性是關鍵——好的型別簽章是最便宜的文件。

最後一個觀察：pretty printer 在 PL 工具鏈裡常被當成「後處理小工具」——但它其實是 IR transformation 的乾淨示範。把 AST 翻譯成 Doc 是「lossy projection」（去掉執行語意，保留版式語意）；把 Doc render 成字串是「width-driven traversal」。整個流程是兩個 IR、三個 phase，pye 的設計把這個內部結構清楚 expose——讀 pye 的 code 就是讀一個小型 compiler 後端的構造。對學 IR design 的人，這是個比讀 LLVM 友善太多的入門範例。

What this enables：把 Wadler-Leijen pretty printer 從「Haskell lazy 救命的 algorithm」變成「Rust strict semantics 下嚴格 O(n) 的可預測組件」——這意味著 formatter、debugger、SQL planner、graph query engine 這些會印出中度複雜輸出的工具，可以重用一份 pretty 邏輯而不需要各自 fork 一套。代價是 measure 階段多一次 traversal、IR 多 8 byte/節點——對 10 萬節點 800 KiB 的記憶體開銷換來「不會在大輸入上炸」的保證。