為什麼 diff rendering 比想像難——hunk、align、virtual scroll、wrap 四件事

Pierre 的這篇文，明面上是「我們做 code review UI 的過程中遇到的事」，骨子裡是一篇關於「為什麼 diff rendering 跟你想的不一樣」的 cross-cutting integration。GitHub、Linear、Phabricator、Gerrit 的 review 介面，從外面看都是「左邊舊版、右邊新版、紅綠標色、可選 unified 或 split」，這個 surface 描述讓人以為這是一個 90 年代就解掉的問題。實際上，這四家工具在每個子問題上的選法都不一樣，每個選法都是某個維度上的 trade-off，而把這些 trade-off 全部搞對的，至今沒有任何一家。

Pierre 那篇文章本身的重點，其實壓在第三件事——virtual scroll——上：他們用了一個被稱作 inverse sticky 的 trick，把 render region 的下緣黏到 viewport 底部，再用 `(contentHeight - viewportHeight) * -1` 這種負偏移把可視窗口推到 patch 內部任何位置。但要解釋為什麼這件事重要，得先把另外三件事擺出來。否則只看 virtualization 部份，會誤以為這是純 perf 議題，跟「diff 怎麼 render」沒什麼關係。實際上，hunk 切分、token alignment、wrap behaviour 三者全部會直接影響 virtual scroll 必須 maintain 的不變量——你 estimate height 用什麼公式，正是這四件事的乘積。

下面那張可點擊的 architecture diagram 是這篇文章的單一入口：點任一個子問題的方框，看它的責任、它倚賴的上下游 invariant、以及它刻意「不知道」什麼。後面五個 H2 各自展開：先講 hunk 怎麼從 raw patch 算出來，然後 token-level alignment 為什麼不能單靠 character diff、virtual scroll 的三種主流做法跟 inverse sticky 的位置、word-wrap 在 CJK 場景的對齊難題，最後把四個 review 工具的選法擺成一張對照表。

四個子問題的責任邊界

四個子問題之間有 directed 的 dependency：hunk splitter 的輸出餵給 token alignment 跟 virtual scroll；token alignment 的輸出影響每行高度，又回頭被 virtual scroll 的 height-estimate 倚賴；word-wrap 是 visual layer 的最後一道，但它的 wrap 結果反過來決定某一個 hunk 在 viewport 裡實際占多高。誰倚賴誰、誰刻意不知道誰，是這四個 component 能否各自 reason 的關鍵。如果 virtual scroll 一定要等 token alignment 完成才能 estimate 高度，整個系統就會在大 patch 下 block 在 token 分析上——這跟 Reels 那邊「closeness 不能 online 推理」是同一類 forcing function。

hunk 切分：為什麼 Myers 不是唯一解

從 raw patch 算 hunk 看起來像 textbook 題目：跑一次 LCS（最長共同子序列），把不在 LCS 裡的行標成 add/delete，相鄰 add/delete 合在一起加上幾行 context 就是 hunk。Eugene W. Myers 在 1986 年的 An O(ND) Difference Algorithm 給了到目前為止仍是預設的選法——時間複雜度跟「兩段文本實際差異量 D」成正比，而不是跟兩段長度 N、M 的乘積成正比。GNU diff、git diff 預設都是 Myers。

但 Myers 在 source code 上有一個出名的 failure mode：大量重複的短行（單一 `}`、`)`、空行、`return;`）會被 algorithm 視為「可對齊的 common subsequence」，導致「明明是把函式 A 整段刪掉、函式 B 整段加進來」這種重構，被切成「函式 A 中間穿插函式 B」的 noise hunk——因為兩段裡都有 `}` 跟空行，algorithm 為了 minimize edit distance 會把它們強行 align 在一起。

Bram Cohen 在 bzr 提的 patience diff（後來成為 git 的 `--patience` option）給了 alternative：先只用「兩邊都唯一出現一次的行」當 anchor 對齊，再 recursive 處理 anchor 之間的 segment。「唯一」這個條件直接過濾掉所有 `}` 跟空行——這些到處重複的行不會被誤當成 anchor。結果是 refactor 大塊的 patch 切出來明顯更乾淨。代價是 worst case 更慢，且如果兩邊真的沒什麼唯一行（極端例子是兩個檔案都是相同 boilerplate），patience 退化得也比 Myers 難看。

還有第三條選擇：histogram diff（JGit 的 default，git 在 2.43 之後也預設啟用），可以視為 patience 的 generalization——按每行出現頻率排序，從最 rare 的開始當 anchor 往下推。實務上 histogram 在大多數 patch 上都比 patience 略好，差距小到一般 reviewer 感覺不出來，但在「函式 inline 進另一個函式」這種重構上 histogram 通常給的 hunk 邊界更直觀。

// Myers: minimize total edit distance, no anchor preference
diff_myers(A, B):
  D = shortest_edit_script(A, B)         // O((N+M) × D)
  return hunks_from_edit_script(D)

// Patience: anchor on unique lines, recurse between anchors
diff_patience(A, B):
  anchors = lines_unique_in_both(A, B)   // only lines that appear exactly once on each side
  ordered = longest_increasing_subseq(anchors)
  for each gap between consecutive anchors:
    diff_patience(A[gap], B[gap])        // recurse, eventually falls back to Myers in small gap

// Histogram: same idea, anchor by frequency rank not just uniqueness
diff_histogram(A, B):
  buckets = group_lines_by_frequency(A ∪ B)
  for bucket in increasing_frequency:
    pick_anchors_from(bucket)            // rarest lines first, deeper recursion shallower
    if found enough → recurse on gaps

選哪個 algorithm 不是 perf 議題（三者在實務 patch 大小下差距 sub-second），是 readability 議題——同一個 patch 跑 Myers 跟跑 patience 切出來的 hunk 邊界可能差很多，reviewer 對「改了什麼」的理解也跟著差。Phabricator 跟 Gerrit 預設用 Myers；GitHub 在 2018 年之後對 large refactor 預設改用 histogram；Linear 沒公開但從 review output 看起來是 patience。這個選擇直接影響到下游 token alignment 拿到的 hunk 形狀——hunk 邊界錯了，token-level 高亮再準也救不回來。

還有一個 hunk 切分的細節跟 UI 很相關：context line 的數量。git 預設給三行 context，但 review UI 上經常要把整個 hunk「擴展」上下文——使用者點 `[N more lines above]` 按鈕，patch viewer 要能向 file 兩端延伸抓 raw lines。這要求 patch 不能只是「diff 結果」這一個 data structure，背後得保留兩個 full file 的 reference（或至少是「足夠的 surrounding context」），否則使用者點 expand 之後系統只能再去 server 抓一次 file——這對 Pierre 的「local-first 不再對 server round-trip」的 design 直接打臉。GitHub 的做法是 lazy fetch additional context；Phabricator 是 patch viewer initial load 就把完整 file 拉下來；Gerrit 介於兩者之間。每種策略的 tradeoff 都不一樣：lazy fetch 省 initial bandwidth 但 expand 有 latency，eager load 反之。

token alignment：為什麼 character diff 不夠

hunk 切好之後，UI 還得回答另一個問題：在 modified 的成對 old/new line 內，哪一段才是「真正改的」？把整行染色看起來資訊量充足，實際上對 single-character 的改動（typo fix、rename 一個變數）會把「真正改了一個字」這個重要訊息淹沒在整行紅綠裡。 reviewer 必須再花 cognitive load 在腦中 character-by-character 比對才能看出改了什麼。

最 naive 的 fix 是 character diff：對成對 line 跑一次字元級 Myers，找出 minimum edit script，把對應 character range 上色。問題：minimum edit script 在 identifier rename 上會給出醜陋結果。把 `userProfile` 改成 `userSettings`，character diff 會告訴你「`P` 改成 `S`、`r` 改成 `e`、`o` 改成 `t`、`f` 保留、`i` 改成 `t`、`l` 改成 `i`、`e` 改成 `n`、加 `g`、加 `s`」——七、八個零碎的紅綠片段。 reviewer 看到的不是「我改了一個變數名」，而是「行內有一坨花花綠綠的東西」。

實務做法是 word-level alignment：先用 whitespace + punctuation 把行切成 token，再對 token 序列跑 diff。`userProfile` 跟 `userSettings` 都是一個 token，diff 結果直接是「`userProfile` 整個換成 `userSettings`」，視覺上是一個乾淨的紅塊配一個乾淨的綠塊。 reviewer 一眼看到「就是 rename 了」。 但 word-level 在「加了個 `await`」這種 prefix 改動上 又會退化——`return foo()` 跟 `return await foo()` 兩個 token 序列，diff 出來是「中間插了一個 token」，這個結果剛好。

再上一層是 syntax-aware：用 parser 把行 token 化成 AST node，diff 在 AST node 這個層級進行。優點是 `if (x == y)` 改成 `if (x === y)` 不會被切成「`==` 變 `===`」這種 lexical diff，而是「BinaryExpression 的 operator 從 `Equality` 變 `StrictEquality`」這種 semantic diff。缺點：要每種語言都養一個 parser，加上 incremental parsing 才能塞進 diff 計算的 budget。Phabricator 的 ArcanistDiffParser、GitHub 在 2023 年加入的 Tree-sitter 整合都走這條路。Gerrit 走相反方向——只給行級高亮，行內不做 token-level，理由是 token-level 在 cherry-pick / rebase 多人衝突場景下會誤導 reviewer 對「改動意圖」的理解。這個立場在純 prose review 來看保守，但在 kernel-style 多 maintainer 流程裡有道理。

三層 fallback 在實作上通常是這樣的 cascade：syntax-aware 試試看，parser 失敗或時間超 budget 就降到 word-level；word-level 算出的 edit script 如果 cost 超過某個 threshold（意味著大概 token 切錯）就降到 character。 cascade 的成本是要為每行 maintain 三個 evaluator，加上 cost-threshold 邏輯，但 visual 結果比單一 strategy 穩定很多。

virtual scroll：inverse sticky 的位置在哪

100k 行 patch 攤平 render 進 DOM 是不可能的——每行至少幾個 element、合計幾十萬 node、瀏覽器 layout pass 直接破秒。所有 review tool 都必須做 virtualization。Pierre 把已知的做法列了三種：

第一種：native scrollable region 加上 estimated total height。整段 patch 用 `height: estimated_total_height` 撐出一個高度等於「估算」的 scrollable container，scroll event 時計算 viewport 對應到哪些 hunk，render 那一段對應的 DOM。優點是用 native scrollbar、滾動慣性、瀏覽器原生快捷鍵全部 work。缺點是 estimated_total_height 必須準確——估錯一點，scrollbar 拖到底但 patch 還沒到底，或反過來。 Pierre 引用的高度估算公式：`(lineHeight × diff.splitLineCount) + (diff.hunks.length × hunkSeparatorHeight)`。 對 plain text 的 diff 這個估算夠準，但碰上會 wrap 的行（CJK comment、長 URL）就開始漂——這也是為什麼 wrap 問題會回頭影響 virtual scroll。

第二種：sticky 容器 + rAF 內手動更新。 用一個 fixed-position container 加上 fake scrollbar，每幀靠 `requestAnimationFrame` 算 viewport 範圍。完全 bypass native scrolling，可以對 estimated height 沒那麼敏感（因為 scrollbar 是自繪的）。缺點是失去 native scroll feel——慣性、accessibility、鍵盤 PgUp/PgDn 全要自己實作。Phabricator 早期版本就是這條路，因為當年 Chrome 的 scroll event 太慢。

第三種：emulated scrolling，用 transform 推動內容，外面套一個自繪 scrollbar。視覺上跟第二種很像，主要差別是 inertia 跟 momentum scrolling 全自寫。這條路只有 Gerrit 在 2024 之後的 V3 改版採用，因為他們要 support 一個 review 介面內並排顯示多個 diff，原生 scroll 沒辦法做這個。

Pierre 的 inverse sticky 算是第一種的變體：保留 native scroll，但 render region 不是「scroll position 對應的中間區段」，而是「下緣黏到 viewport 底部」。 具體公式：`render_region_top = scroll_position - viewport_height`， `render_region_bottom = scroll_position + buffer`。 用 negative offset `(contentHeight - viewportHeight) * -1` 把上面尚未進入 viewport 的部分推開。 這個做法的好處不是它快，是它把「scroll 過 patch 邊界時的 reflow jitter」消掉——下緣黏住 viewport，意味著新進入 viewport 的 row 從底部往上長，不會把已經穩定的視覺位置推來推去。

下面這個 slider 讓你掃 patch size 跟每行平均字元數，估算「靜態 render」「naive virtual scroll」「inverse sticky」三種策略下，per-frame DOM node count 跟 layout time。 16 ms 那條紅線是 60 fps 的 budget——任何策略一旦把 estimated layout time 推過這條線，捲動就會肉眼可見地卡。

把 patch 推到 10k 行 + 每行 60 字元，static render 已經破了 16 ms（事實上瀏覽器這時的 initial paint 也早就破秒）；naive virtual 在這個 size 還守得住，但拉到 100k 行就開始飄；inverse sticky 因為「只 layout visible + buffer」這個 invariant 跟 patch size 無關，無論 patch 多大都維持低個位數 ms。這個 scaling 性質才是 inverse sticky 對前兩種的真正優勢——不是常數因子，是 patch size 不再進入 frame budget 公式。

Pierre 也誠實標記了還沒解的問題：「serialization in the highlighting pipeline」跟「沒做 horizontal scrolling virtualization for extremely long lines」。前者意味著如果語法高亮算得慢，virtualization 的好處會被吃掉一半——high-fan-in serialize point 通常會成為 perf 瓶頸；後者意味著一行 50k 字元的 minified bundle dump 進 patch viewer，水平方向還是會慢，因為 viewer 還是把整行的 DOM 建出來。這兩個 caveat 不影響架構正確性，但會在實務 user complaint 裡浮現。

word-wrap：CJK 給的麻煩

split view 預設 invariant 是「左欄第 N 行的視覺位置 = 右欄第 N 行的視覺位置」——reviewer 的眼睛掃過去能水平 align「對應的 old / new」。這個 invariant 在純 ASCII monospace 場景 trivially 成立：每個字元固定寬度，每行剛好 80 column 就 wrap。混入 CJK 之後，這個 invariant 直接破。

原因有兩層。第一層是 character width：CJK 字元在 monospace font 裡通常算 2 個 column（東亞 wide character 的 Unicode property），ASCII 是 1 個。但 fallback font 的 metrics 不一定遵守這個——如果系統挑了一個 proportional CJK font，每個字的 advance width 都不一樣。第二層是 line-break opportunity：CJK 沒有 whitespace 作為 break point，瀏覽器預設可以在任何字之間斷行（line-break: anywhere），這跟拉丁文「只在 whitespace 或 hyphen 斷行」是完全不同的 algorithm。

結果是：左欄 `// 處理 user 的請求並回傳 JSON response 給前端` 在某個 column 斷行，右欄 `// handle the user request and return JSON response to client` 在另一個位置斷行——兩邊 wrap 位置不同，從第 N 行往下，左右欄就再也 align 不上。reviewer 視覺上得從頭重新對位，每幾行就斷一次。

// Naive: let the browser wrap; align by source line only
render_split_naive(oldLines, newLines):
  for (oldLine, newLine) in zip(oldLines, newLines):
    emit_row(oldLine, newLine)        // each cell wraps independently → vertical drift

// Logical-column wrap: pre-compute the wrap column per row, force same wrap on both sides
render_split_aligned(oldLines, newLines, colWidth):
  for (oldLine, newLine) in zip(oldLines, newLines):
    wrapCol = min(
      wrap_column_for(oldLine, colWidth),
      wrap_column_for(newLine, colWidth)
    )
    visualOld = wrap_at(oldLine, wrapCol)
    visualNew = wrap_at(newLine, wrapCol)
    rowHeight = max(lines_after_wrap(visualOld), lines_after_wrap(visualNew))
    emit_row_with_height(visualOld, visualNew, rowHeight)

這個 fix 看起來簡單——「兩邊 wrap 在同一 column」——實際上要寫對得處理「測量 column」這件事：CJK 字元在不同 font 下 advance width 不一致，瀏覽器 layout 算出的 wrap column 跟 application code 預設的 column 數字不對齊。要嘛 application 自己 maintain 一套 character width table（並且跟瀏覽器實際 layout 對得起來），要嘛用 <canvas> 的 measureText 去 query 每個字串的 visual width（per-row 一次 measure，成本不低）。Pierre 沒展開這段——他的文章重點在 virtual scroll——但行間提到「the width estimator has to round consistently on both sides or split view drifts」。

還有一條 wrap behaviour 跟 hunk 切分有關：如果一行 logical line 被 wrap 成多個 visual line，virtual scroll 的 height estimator 必須知道這件事，否則 estimated_total_height 會偏小，使用者拖到 scrollbar 底部時 patch 還沒結束。實作上要嘛在 wrap layer 算完之後把實際 visual line count 喂回 virtual scroll layer，要嘛在 height estimator 裡加上一個 pessimistic wrap factor（每行假設 wrap 1.2 次）。前者準但慢，後者快但 inaccurate——又是一個沒有 free lunch 的 trade-off。

大多數 review tool 在這件事上的選擇是「先放棄 split view，CJK 友善的場景用 unified view」。GitHub 的預設是 unified；Linear 預設 split 但 CJK comment 多的 PR 會 silently 切回 unified（這是反向的 fallback）；Phabricator 提供 toggle 但不在 viewport 層 align；Gerrit 倒是把這件事認真做了——他們的 split viewer 真的會 force 兩邊在同一 logical column wrap，代價是 wrap 算 column 的 measurement step 非要靠 `canvas.measureText` 不可。

四家工具的選法

把四個子問題跟四家工具擺成 cross 表，每一格是一個 design decision。可以排序——看哪家在哪一格最激進、哪家最保守。

四家在 hunk splitter 跟 token alignment 上選擇趨同（Myers 為主、word-level 加 syntax-aware fallback），在 virtual scroll 跟 word-wrap 上選擇分歧最大——這兩件事剛好是 user-visible 但 hard 的 sub-problem。容易做的事大家做一樣，難做的事各自挑了不同 trade-off。 GitHub 用 hard cap 迴避極端 case；Linear 賭一個更難的 virtualization scheme 換 no-truncate；Phabricator 認 5k 行上限換 deterministic；Gerrit 把 wrap 做到底，付出全自寫 scroll 跟 measurement 的 maintenance cost。

tradeoff 對照表

把四個子問題的「主流 algorithm」「成本維度」「失敗 mode」「補救手段」擺成可排序的對照表——點欄位標題排序。把第三欄（failure mode）排序最有用，能看出哪些 sub-problem 的失敗會牽到別的 sub-problem。

把表按「failure mode」排序，會跳出來一個 pattern：失敗都是「在某個 axis 上 push 過邊界」——大 refactor、大 patch、CJK 混入、long-line identifier。四件事的 default algorithm 在「中等大小、中等難度」的 patch 上都 work，崩潰都發生在 distribution edge。production-grade review UI 的差別不在中央場景做得多好，而在邊界情形不徹底崩。

還有一個沒寫進表裡但值得指出的 cross-cut：四個 sub-problem 的 fix 跟 fix 之間會干擾。把 hunk splitter 從 Myers 改成 histogram，hunk 數量變了，token alignment 拿到的成對行也跟著變；把 token alignment 從 word-level 升級到 syntax-aware，每行的 visual height 因為高亮塊變多／變少而微調，virtual scroll 的 height estimate 跟著要校；把 virtual scroll 從 native 改成 inverse sticky，wrap 的測量 timing 也要改——因為 wrap 算到一半新行就被 virtualization 推進來。 每個 sub-problem 不獨立，整套東西是一個 coupled system。Pierre 這篇文章把這四件事擺在一起講，正是因為「分開做 perfect 但合起來不對」這個風險，要在 architecture 階段就先看到。

對自家想做 review UI 的 team，這篇文最大的 take-away 不是「inverse sticky 怎麼寫」，而是先確認你想解的是哪一個 sub-problem——很多自家 UI 從 word-level alignment 開始，卻發現真正的 user pain 在 wrap 不齊；或者反過來，flag 自己「我們要做 super fast scrolling」，卻沒注意 token alignment 在自家 codebase（大量 generated code、autoformat noise）切得不準。 sub-problem 沒選對，再好的 algorithm 都白用。

So what：diff rendering 的「困難」不在任何單一 algorithm，而在 hunk、token、virtual scroll、wrap 四個 sub-problem 必須 coupled 起來解、但又彼此不能 directly 倚賴對方的內部結構。Pierre 那篇文把它們擺在同一個 frame 裡的價值大過任何單一 technique——下次評估自家 review UI 投資的方向時，先問「我們最弱的那個 sub-problem 是哪一個」，再去找對應的 algorithm。Myers vs patience、word vs syntax-aware、native vs inverse sticky、瀏覽器 wrap vs forced wrap：每一對 alternative 都有自己的場景，沒有 universal answer。能在 cross-cut 上做 informed choice 的 team，比押在某一個 algorithm 上「賭未來不會踩坑」的 team，產出的工具會耐用得多。