デモ
オムニ補完とは？
オムニ補完は vim 界隈でわりとよく耳にする言葉ですが、IDE よろしくメソッド名などをいい感じに補完する機能です。
Emacs でも perl の変数名とかメソッド名をいい感じに補完してくれるperl-completion.el とか、 C/C++ の IDE モドキ CEDET などがあります。
auto-complete.el に最初から入っている CSS の補完も、プロパティ名によって補完候補を変えてくれたりかなりオシャレです。
なにをやったの？
オムニ補完は便利なのですが、エディタがその言語のことを良く知っているか、あるいは言語処理系側がいい感じに補完候補を探してエディタに報告してくれる機能を持っていないと基本的には実装できません。なので、言語ごとに別々のプラグインを入れるのが普通で、設定のほうはわりと面倒です。
そこで今回は git の力を借りて、言語の知識がない状態でもオムニ補完を（それなりに）やってくれるプラグインを書いてみました。 git grep でプロジェクト内を見渡せば、なにを入力したいのかある程度予測できるのでは？という作戦です。
git を利用した補完の元ネタは hitode909 さんの
auto-programming.el
です。今回作った git-complete.el はそれにさらに機能をゴテゴテ盛った感じのプラグインです。auto-programming.el のアイデアがなければ作れなかったです。
ダウンロード・使い方
https://github.com/zk-phi/git-complete に置いてあります。
git-complete.el をロードパスに置いてロード、適当なキーをバインド：
(reqiure 'git-complete)
(global-set-key (kbd "C-c C-c") 'git-complete)
git 管理下のファイルで何か入力して、
SHA
git-complete を呼ぶと、それっぽい式をプロジェクト内から探してきて補完します。
use Digest::SHA;
行全体だけでなく、一部分の補完もできます。たとえば
window.addEventListener()
ここまで入力して git-complete を呼ぶと
window.addEventListner("click", )
イベント名の候補をサジェストしてくれたりします。
Pros / Cons
git-complete のいいところは
オムニ補完のように次に入力する可能性が高いイディオムを予想して持ってきてくれるので、たとえば次に何を入力すべきか本人も覚えてない場合とかでも使える
イディオム単位での補完なので、２シンボル以上いっぺんに補完してくれることもある
オムニ補完と違って言語ごとの設定が不要
だめなところは
git 管理下のプロジェクトでしか使えない、初期段階のプロジェクトだと精度が悪い
git grepの特性で、プロジェクト内での一発目の補完が遅い
しくみ（ざっくり）
git-complete.el は２種類の補完アルゴリズムを順に試します：
- 行補完
- オムニ補完
行補完
入力途中のテキスト
SHA
でプロジェクト内を git grep して、
> git grep "SHA"
hoge.pl: use Digest::SHA;
hoge.pl: my $sha = Digest::SHA->new(256);
piyo.pl: use Digest::SHA;
piyo.el: $hash = Digest::SHA->new(256)->add($_)->hexdigest;
でてきた結果のなかから出現頻度が高い行（デフォルトでは結果の 2% 以上を占めるもの）を補完候補としてサジェストします。
上の例だと、 use Digest::SHA; が複数回出てきているので、補完候補として使えそうです。
use Digest::SHA;
主にインポート文などを楽して入力する場合に便利です。
オムニ補完
入力途中のテキスト
window.addEventlistener(
で行補完と同様にプロジェクト内を git grep します
> git grep "window.addEventListener("
hoge.js: window.addEventListener("scroll", myAwesomeScrollHandler);
hoge.js: window.addEventListener("click", myAwesomeClickHandler);
piyo.js: window.addEventListener("scroll", anotherScrollHandler);
piyo.js: window.addEventListener("click", anotherClickHandler);
fuga.js: window.addEventListener("click", yetAnotherClickHandler);
これといった行補完の候補がなかった場合、まず、それぞれの検索結果から「クエリ文字列より右の部分」だけを取り出します。
"scroll", myAwesomeScrollHandler);
"click", myAwesomeClickHandler);
"scroll", anotherScrollHandler);
"click", anotherClickHandler);
"click", yetAnotherClickHandler);
そして、その結果から「頻出する共通部分」（デフォルトでは 0.5% 以上を占めるもの）を取り出して、補完候補にします。たとえば上の例だと、
"click", myAwesomeScrollHandler);
は１度しか出てきていませんが、イベント名にあたる
"click",
や
"scroll",
は何度も出てきているので、補完候補として需要がありそうです：
window.addEventlistener("click", )
クエリが長すぎてそれらしい候補が見つからなかった場合は、クエリを縮めて再度試します。クエリの縮め方はオプションで変えられますが、デフォルトでは先頭から１ subword を削除します。
subword とは、たとえば hogePiyoFuga でいうと hoge, Piyo, Fuga がそれぞれ subword です (subword-mode と同じです)。
「頻出する共通部分」抽出のしくみ
ひょっとしたら役に立つかもしれないので、「頻出する共通部分」をどうやって抽出したかメモしておきます。
たんにいくつかの文字列から共通部分を取り出すとかだと簡単なのですが、そもそも共通部分があるかもわからない文字列のセットから、「補完候補としていい感じに使えそうな部分列」のセットをどうやって選んだらいいか悩みました。
自分はトライ木の変形版のようなものを中で作って、トラバースしました。
普通のトライ木は、文字列（バイト列）の集合を、
{ "hoge", "hoga", "hige", "hogera", "piyo" }
こんな感じの木で持つデータ構造です：
*
/ \
h p
/ \ |
o i i
| | |
g g y
/ \ | |
a e e o
|
r
|
a
git-complete で使っているトライ木は、ひとつひとつのノードが単一の文字ではなく、シンボルを担当します。たとえば
> git grep "window.addEventListener("
hoge.js: window.addEventListener("scroll", myAwesomeScrollHandler);
hoge.js: window.addEventListener("click", myAwesomeClickHandler);
piyo.js: window.addEventListener("scroll", anotherScrollHandler);
piyo.js: window.addEventListener("click", anotherClickHandler);
fuga.js: window.addEventListener("click", yetAnotherClickHandler);
この検索結果を次のように整理します：
*
|
+-----+-----+
| |
+----+----+ +----+----+
|"scroll",| |"click", |
+----+----+ +---------+
| |
| +-----------------------------------+
+-------------------+ |
| |
+------------+------------+ |
| | |
+-----------+------------+ +----------+-----------+ |
|myAwesomeScrollHandler);| |anotherScrollHandler);| |
+------------------------+ +----------------------+ |
|
+---------------+
|
+------------------------+-------------------------+
| | |
+-----------+-----------+ +----------+----------+ +------------+-----------+
|myAwesomeClickHandler);| |anotherClickHandler);| |yetAnotherClickHandler);|
+-----------------------+ +---------------------+ +------------------------+
そしてそれぞれのノードに、そのノード以下にある葉ノードの枚数を定数時間で得られるようにメモしておきます。
*
| (5)
+-----+-----+
|(2) |(3)
+----+----+ +----+----+
|"scroll",| |"click", |
+----+----+ +---------+
| |
| +-----------------------------------+
+-------------------+ |
| |
+------------+------------+ |
|(1) |(1) |
+-----------+------------+ +----------+-----------+ |
|myAwesomeScrollHandler);| |anotherScrollHandler);| |
+------------------------+ +----------------------+ |
|
+---------------+
|
+------------------------+-------------------------+
|(1) |(1) |(1)
+-----------+-----------+ +----------+----------+ +------------+-----------+
|myAwesomeClickHandler);| |anotherClickHandler);| |yetAnotherClickHandler);|
+-----------------------+ +---------------------+ +------------------------+
やりたかったことは、 0.5 %以上の頻度で出現するそれっぽい部分文字列を探すことでした。マッチの総数から、いくつ以上の出現があれば 0.5% 以上になるかを逆算できるので、トライ木をルートから、その個数を切るギリギリのところまで掘っていって、それを補完候補として採用すればいい感じになります。