テキストの差分

2つの文章を貼ると、差分チェックとして、 どこが変わったかを行ごとに並べます。貼り付けた文章はどこにも送りません。行末の空白のように、見比べても見つからない違いも名前で示します。

貼り付けた文章は、この機器から出ません

この道具は、読み込みから比較まですべてこの画面の中で動いています。 文章をどこかへ送って結果を受け取る、という作りではありません。 ブラウザの開発者ツールで通信の様子を見ながら文章を貼り付けても、新しい通信は1件も増えません。確かめられる形になっています。

差分を求める計算も、外から部品を持ってこずに自分で書いてあります。 「送っていません」と言いながら外部の部品を読み込んでいては、読み込んだ先が何をするかまでは保証できないからです。 そのぶん扱える大きさに上限がありますが、公開前の原稿や、社外に出せない書類をそのまま貼れることを優先しました。

差分は「違うところ探し」ではなく「いちばん少ない編集」を探しています

文章の3行目に1行だけ足したとします。素直に同じ行番号どうしを見比べると、それ以降の行はすべて1つずつ後ろへずれるので、3行目から最後まで全部が「変わった」ことになってしまいます。 1行足しただけなのに、100行の文章なら98行が赤くなります。

そこで実際の差分は、まったく別の問い方をします。「AをBに変えるには、どこを消してどこを足すのが、いちばん少なくて済むか」。 こう問うと、答えは「3行目に1行足す」だけになります。 この計算は最長共通部分列（2つの文章に共通して、 同じ順番で現れる行の並びのうち、いちばん長いもの）を求めることと同じです。

この2つが同じものだということは、差分の研究では古くから知られていました。 1986年のマイヤーズの論文は、冒頭で「最長共通部分列を求める問題と、AをBに変える最も短い編集手順を求める問題は、 双対であることが古くから知られている」と書いています。いま git が既定で使っている差分の算法も、この論文のものです。

面白いのは、同じ論文が用途としてこう並べていることです。「プログラマは、自分がテキストファイルをどう変えたのかを知りたい。 生物学者は、あるDNAの鎖がどう別のものへ変わったのかを知りたい」。文章の差分と、生きものの遺伝子の変化。まったく違って見える2つを、同じ計算が引き受けています。

見た目が同じなのに違う文章があります

2つの行を画面で見比べて、どう見ても同じなのに「違います」と出ることがあります。 道具が壊れているのではありません。目に見えない文字が違うのです。 よくあるのは次の6つで、名前と番号はUnicode の文字データベース（新しいタブで開きます）に載っているとおりです。

ここで面白いのは、Unicode 自身が「これは空白の仲間だ」と書いていることです。 文字データベースには、U+00A0 に「U+0020 の、折り返さない版」、U+3000 に「U+0020 の、全角の版」という関係が記録されています。親戚だと分かっていて、それでも別の文字として扱う。 だから画面では同じに見えて、機械にとっては違うものになります。

逆に U+200B ゼロ幅スペースは、名前に「スペース」と入っているのにUnicode の分類では空白ではなく「書式」の仲間です。 幅を持たないので、空白としては働かないからです。

この困りごとが昔からあることは、道具の側からも分かります。git には--ignore-space-at-eol（行末の空白を見なかったことにする）という指定が用意されています。わざわざ専用の指定があるということは、それだけ人が困ってきたということです。

改行コードは3種類あって、どれも画面には出ません

行の終わりにも文字が入っています。使われるのは次の3つです。

この英語の名前は、印字機（タイプライター）の動きをそのまま指しています。 紙を載せた台を左端まで戻すのが「復帰」、紙を1行ぶん送るのが「行送り」。2つは別々の動作だったので、文字も2つありました。 画面の中に紙も台も無くなった今も、その2文字が残っています。

どれが正しいということはありませんが、決まりで指定されている場面はあります。 メールの規格であるRFC 5322（新しいタブで開きます）は、行を「復帰と行送りの2文字で区切られたもの」と定義したうえで、 本文では「復帰と行送りは、必ず CRLF として一緒にしか現れてはならない」とまで書いています。

困るのは、この違いで全部の行が「変わった」ことになってしまうときです。git に --ignore-cr-at-eolという指定があるのは、まさにこのためです。 この道具は行の中身だけを比べるので、改行コードの違いで差分が壊れることはありません。 そのうえで黙って直したことにもしません ── 「改行コードが違います」と、別にお知らせします。

入力欄に貼り付けた瞬間、ブラウザが改行コードを書き換えています

ここに、この道具を作っていて見つけた困りごとがあります。Web ページの入力欄は、貼り付けられた文章の改行コードを勝手に LF へ直します。利用者にも、道具を作った側にも、何の断りもありません。

気まぐれではなく、決められた動きです。HTML の標準（新しいタブで開きます）は入力欄の中身について「改行が U+000A LINE FEED になるように正規化される」と定めていて、その直し方はInfra の標準（新しいタブで開きます）に「CR と LF の組を1つの LF に置き換え、残った CR をすべて LF に置き換える」と書かれています。

つまり入力欄の中身だけを見ている差分の道具は、改行コードの違いを一生見つけられません。検査は全部通り、画面もそれらしく見えるのに、その働きだけが一度も動かない ── いちばん見つけにくい壊れ方です。

そこでこの道具は、貼り付けられた瞬間に、貼り付け元の中身をそのまま受け取って覚えておきます。そちらには CR がまだ残っているので、改行コードの違いに気づけます。 覚えた中身を使っているときは、そのことも画面に出します。 入力欄で書き直すと分からなくなってしまうので、そのときは「分からなくなりました」と出します。

最後の1行に改行があるかどうかも、目には見えません

ファイルの終わりが「改行で終わっているか」も、画面ではほとんど分かりません。 ところがこれは、決まりの上でははっきり別のものです。POSIX の用語の定義（新しいタブで開きます）は、1行を「改行でない文字が0個以上と、終わりの改行1つ」と決めています （3.185 Line）。

つまり改行で終わっていない最後のかたまりは、そもそも「行」ではありません。 POSIX はこれを「不完全な行」という別の言葉で呼んでいます（3.172 Incomplete Line）。 文章を書く道具が最後に自動で改行を足すのは、この決まりに合わせるためです。

この道具は、最後の改行を「空っぽの行が1行増えた」とは数えません。 そう数えると、改行を1つ足しただけで「1行増えました」と出てしまうからです。 かわりに文章そのものの性質として持っていて、 片方だけ改行で終わっているときに、そうお知らせします。

出どころ: 差分の考え方は Myers, E. W.「An O(ND) Difference Algorithm and Its Variations」（Algorithmica 1(2): 251-266, 1986）、git の既定の算法と各指定はgit-diff の説明書（新しいタブで開きます）、文字の名前と番号は Unicode の文字データベース、行の定義は POSIX、改行コードの決まりは RFC 5322 から取っています。 いずれも一次資料で確かめた値だけを書いていて、推測で埋めた欄はありません。