タブ文字ありで桁揃えされたコードからタブ幅を推定

コードなどを書く際、タブ文字をインデントに使えばエディター側の設定で自分好みの幅に変えられる。GitHubでもURLに ts=2 などのクエリを追加すれば反映される。

一方で、コメントや配列要素などの桁揃えの目的で使うと、一見手軽に揃えられるように見えるが、タブ幅を変えると崩れてしまうことがほとんど。

タブ幅が2の前提で書いたコード

func(                 # とあるメソッド
  arg,
  key:        "test",
  log_level:  :DEBUG  # 何かのオプション
)

タブ幅を4に変えた場合

func(                                   # とあるメソッド
    arg,
    key:                "test",
    log_level:  :DEBUG  # 何かのオプション
)

---

では逆に、「この箇所は桁揃えしているはず」という仮定をおくことで、本来のタブ幅を推定できるのではないか。問題を簡略化して考えてみた。記事の最後の方には問題を解くRubyコードを添付する。

問題設定

「生のコードを読み込んで自動で適切なタブ幅を推定する」というのは私には難しすぎるので、要点だけ再現できる程度の問題を設定する。

---

問：半角文字とタブ文字からなる、0文字以上の文字列が2行与えられる。これらの文字列の見た目上の長さが等しくなるには、タブ幅は半角文字何個分に設定すれば良いか。

入力例（タブ文字の代わりに _ で表示）

__abc__#
___xy_#

（コメント開始 # をタブ文字で揃えようとしている状態をイメージした）

タブ文字の性質

タブ幅 T という1以上の整数値を設定すると、（ゼロは考えない）

• タブ文字は表示時は 1 以上 T 以下の適当な長さに見える
• 行の先頭から数えるとタブ文字の終了位置は T の整数倍になる

入力例のタブ文字を »--- と可視化すると以下のようになる。

タブ幅1〜6、目盛付

01234567
»»abc»»#
»»»xy»#

0 2 4 6 810
»-»-abc»»-#
»-»-»-xy»-#

0  3  6  9 12 15
»--»--abc»--»--#
»--»--»--xy»#

0   4   8  12  16
»---»---abc»»---#
»---»---»---xy»-#

0    5   10   15   20
»----»----abc»-»----#
»----»----»----xy»--#

0     6    12    18    24
»-----»-----abc»--»-----#
»-----»-----»-----xy»---#

入力例の答え

答えはひとつとは限らない。0個なこともあれば、複数どころか無限なことさえある。これを全部求められれば、様々なコード片の結果を組み合わせてタブ幅の候補を絞り込める。

入力例の答えは 2 および 4以上 。前節で様々なタブ幅を試したテキストからも確認できる。

解法の検討

見た目上の長さの計算

タブ文字は長さが可変なので、タブ文字自体からは長さを求められない。そこでタブ文字を除外し、タブ文字毎に区切られた文字列の長さ（0文字ということもある）を元に考えてみる。

タブ幅 T で、 n 個のタブ文字で区切られた各文字列の長さを a_i （ 0 ≦ i ≦ n ）とする。このとき見た目上の長さは以下のように求められる。

# T = ...; line = "...\n"
a = line.chomp.split("\t").map!(&:length)
n = a.size - 1
l = a[0...n].sum { |ai| ai - (ai % T) + T } + a[n]

- (ai % T) と補正をかけることでタブ文字の伸縮を反映し、タブ文字の終わりの位置は必ず T の倍数になる。具体的には例えば ai = 13; T = 8 なら、 13 - (13 % 8) + 8 == 16 となる。

※ 最後の部分 a[n] は、後ろにタブ文字が無いため補正がかからない。

答えが無数にある場合を判定

答えが無数にある場合は面倒そうなので、あらかじめ知っておきたい。（ただし次節では別の判定方法を使う）

答えが無数にある状況では「十分に大きなタブ幅が（無数に）解になる」ことが言える。このことを利用して文字列の見た目上の長さを考えてみる。

前節の式で T が十分に大きいと、 a[i] % T == a[i] とできるため、 sum の部分は ai がキャンセルして T * n になる。従って全体の長さは l = T * n + a[n] 。

これが line1 と line2 とで T に依らず同じ値になるのは、 n1 == n2 && a1[n1] == a2[n2] のときである。つまりタブ文字の数が等しく、最後のタブ文字より後の半角文字の数も等しいときに、答えが無数にあるということ。

---

この検討は「「十分に大きなタブ幅」とは具体的にいくつか？」という疑問にも答えている。 sum の部分で a[i] % T == a[i] が成り立つことが条件なので、 T = a[0...n].max + 1 であれば十分。
※ ただし「解が無数にある場合」についての話であり、解が有限個の場合は何も言っていないことに注意。

総当たり探索

適切なタブ幅を抜け漏れなく見つける上手な方法は思いつかなかったので、単純に「 T を1から全て試す」ことにして、 line1 と line2 の長さが等しくなるものを抽出する。この場合、探索を打ち切っていい値 T_limit を決めておく必要がある。

前節の検討では十分に大きな T の値を見積もったが、解が有限個の場合にまで適用すると探索漏れを起こしてしまう。

探索漏れ（正しいタブ幅は4）

__1234#
___#

--> a1 = [0, 0, 5]; a2 = [0, 0, 0, 1]
--> T_limit = 1 ???

探索漏れを防ぐには、最後の a[n] も含めて最大値を計算するのが良い（この例では T_limit = 6 ）。こうするとタブ文字の数が異なる場合には、 T = T_limit だと文字列の長さが決して一致しなくなる。さらに言うと、 T = T_limit で一致する場合に限りそれ以上のタブ幅でも一致する（解が無数にある）ため、前節の判定法は不要になる。

コード

guess_tabwidth.rb

TAB_PATTERN = /\t/

# 文字列をタブ文字で分割する
def split_by_tab(str)
    # 空文字列でも一貫性のある結果を返す
    str.empty? ? [""] : str.split(TAB_PATTERN, -1)
end

# タブ幅 t のときの文字列の長さを計算する
def len(a, t)
    n = a.size - 1
    a[0...n].sum { |ai| ai - (ai % t) + t } + a[n]
end

line1 = gets
line2 = gets

a1 = split_by_tab(line1.chomp).map!(&:length)
a2 = split_by_tab(line2.chomp).map!(&:length)
t_limit = [a1.max, a2.max].max + 1

ans = (1..t_limit).select { |t| len(a1, t) == len(a2, t) }
inf = ans[-1] == t_limit  # t_limit が解になる ⇔ それ以上の t も全て解になる

# 答えが "3, 4, 5.." のようになる場合は "3.." のように短縮する
if inf
    ans.pop while ans[-1] - 1 == ans[-2]
end

puts ans * ", " + (inf ? ".." : "")

冒頭の例を入力すると、 2, 4.. と出力される。

雑記

もし答えが 1.. になれば、これはタブ幅の設定に依存しないよう桁揃えされていることを意味する。（タブ文字を使っていない場合も当然こうなる）

タブ文字以外を何文字にしてもタブ幅の影響を受けないためには、少なくとも以下の条件を満たす必要がある。

• 桁揃えのためにタブ文字を使わない
• インデントのタブ数の異なる行同士で桁揃えしない