Emacs の Major Mode におけるインデント計算を楽にする smie.el

Writing a good indentation function can be difficult and
to a large extent it is still a black art.
-- Emacs Lisp Reference Manual

良いインデント関数を書くのは困難であり、
現在においても広い範囲に置いて黒魔術である。

ここではEmacs 24.3の新機能である、インデント計算エンジン smie.elを紹介する。

Emacs の Major Mode の実装

Emacs の Major Mode は、様々なプログラミング言語やテキストフォーマット
用に色付けやインデントなどの編集機能を提供する。

Emacsは多くのプログラミング言語用にMajor Mode が用意されているが、例外
もある。また、独自に言語を設計した場合も、Major Mode を自作することになる。

Major Mode の作り方には、典型的な「型」
( http://www.emacswiki.org/emacs/SampleMode )と「順序」がある。

Major Mode を作るには、対象言語を熟知しなければならない。
Major Mode を作る過程で、対象言語のエディタでの振る舞いをより深く知るこ
とができるよう、以下の手順で作成するのが良い。（ここでXXXはメジャーモー
ド名とする。）

(1) XXX-mode-syntax-table

Emacs は、全ての文字に対して、「シンタックス」と「カテゴリ」と呼ばれる
属性が定められている。「シンタックス」はメジャーモードに依存する属性で、
「カテゴリ」は全バッファに共通の属性である。

XXX-mode-syntax-table は、プログラム言語XXXの、各文字のシンタックスを規
定する。ここにはプログラミング言語における文字の基本的性質、すなわち文
字列を囲むquote文字（e.g. "...."）や、コメントヘッダ（/*....*/ や //....など）、
その言語で有効な括弧の対応（{...}、[...]、{...}）、空白文字などを記述する。

この設定により、Emacs Lisp マニュアルの35章 Motion and Syntax で記述さ
れている、skip-syntax-forward, backward-prefix-chars, skip-lists
等のバッファ走査関数が利用できる。

(2) XXX-mode-font-lock-keywords

文字のシンタックスを決めたら、次はプログラミング言語XXXの予約語・関数・
変数・定数をバッファを検索して、色付けするための変数、
XXX-mode-font-lock-keywordsを設定する。予約語は regexp-opt で正規表現
化し（xxx-mode-keywords-regexp）、定数や変数は前後を正規表現でチェック
して見つけるようにする。

(defconst XXX-mode-keywords-regexp
   (regexp-opt '("begin" "end" ...))) ;; 予約語一覧

(defvar XXX-mode-font-lock-keywords
  `(,XXX-mode-keywords-regexp
    ;; 定数や関数に色付けしたい場合は、consセルにface名とともに設定する。
    ("([0-9]+)" . font-lock-constant-face)
    ("^[[:space:]]*\\(\\w+\\).+?::=" 1 font-lock-variable-name-face)
    ....))

事前に syntax-table を定義しておけば、コメントや文字列は自動的に色付け
される。

この (1) (2) まで実装し、define-derived-mode でメジャーモードを決めれば、
プログラムに綺麗に色付けがなされ、それだけでもかなり「らしさ」が見えて
くるようになる。

;;;###autoload
(define-derived-mode XXX-mode prog-mode "XXX"
  "Major mode for editing XXX programming language."
  (set-syntax-table XXX-mode-syntax-table)
  (setq-local font-lock-defaults '(XXX-mode-font-lock-keywords nil nil)))

プログラミング言語のメジャーモードを作成する場合は、必ずprog-modeから
派生させる。

(3) XXX-mode-indent

Major Mode を作るための最難関が、インデント計算である。タブキーをおした
時、どの程度のインデントを行なうか、その計算は時として非常に複雑になる。
「黒魔術」と呼ばれる所以である。一例を示す。

begin
    def function (x)
       for |x| do {
          if hogehoge then
            ....
          end
          }
    -> | <- タブキーでカーソルをここに移動させたい

このようにコードが複雑にネストしている場合、インデント位置は近辺の構文
を解析して決めなければならない場合がある。

これまで、多くのMajor Modeはインデントを独自に計算していた。この部分は
複雑になりがちで、バグも入りやすく、メンテしにくいものだった。

Emacs 24.3 から装備された、 smie.el (Simply Minded Indentation Engine)
は、このインデント計算をモジュール化する。

(4) smie.el の機能

smie.el は、対象となるプログラミング言語の文法を「演算子順位構文」で記
述することで、プログラムのネスト構造を検出して、適切なインデント位置や
囲みを計算できるようにする。

演算子順位構文は、パーザの中でも比較的単純な構文であり、主な構文の中で
は唯一、前後双方向からパーズができる。インデント計算が厄介なのは、通常、
コンパイラは「前方向」から入力プログラムを解析するのに対し、テキストエ
ディタは「後方向」から解析するためだが、演算子順位構文ならばどちらから
でも解析できる。

smieは define-derived-mode の中で以下のようにセットアップする。

(smie-setup XXX-mode-smie-grammar 'XXX-mode-smie-rules
            :forward-token XXX-mode-forward-token
            :backward-token 'XXX-mode-backward-token)

ここでプログラマが用意するのは、演算子順位文法データ
XXX-mode-smie-grammar、インデント計算関数 XXX-mode-smie-rules、そし
て字句解析器 XXX-mode-forward-token とXXX-mode-backward-token である。

smie.el の演算子順位文法

XXX-mode-smie-grammar 文法は、字句に優先順位を割り当てたリストで指定
する。このリストを人間が作るのは難しいので、まずは人間に分かりやすい
BNFや、演算子を優先順位に並べたリストを指定し、そこから「演算子×演算子」
で優劣を整理した表を作り（smie-bnf->prec2、smie-prec->pre2）、そこから
優先順位を計算して文法を生成する。（smie-prec2->grammar）。

通常は文法は以下のようにBNFで入力する。

(smie-prec2->grammar
  (smie-bnf->prec2
   '((id)
     (inst ("begin" insts "end")
           ("if" exp "then" inst "else" inst)
           (id ":=" exp)
           (exp))
     (insts (insts ";" insts) (inst))
     (exp (exp "+" exp)
          (exp "*" exp)
          ("(" exps ")"))
     (exps (exps "," exps) (exp)))
   '((assoc ";"))
   '((assoc ","))
   '((assoc "+") (assoc "*"))))

興味のある方は、上記またはその中間形を scratch バッファで実行し、内容
を見てみると良いだろう。

演算子順位構文では、非終端記号は連続できない。その基本的な型は、

非終端記号 → (非終端記号 終端記号 非終端記号)

または、

非終端記号 → (終端記号 非終端記号 終端記号)

となるため、プログラミング言語の文法を工夫して、上記のように表記できる
よう努力する。BNFにおいて、終端記号が前後に現れる場合、それはプログラミ
ング言語のブロックの開き（opener）と閉じ（closer）となり、中間に現れる
場合は中間オペレータとなる。

例えば、プログラム言語において式が ; で終わる場合、smie では ; は文
の区切りに現れるあ中間オペレータとしてBNFに記述する。

smie.el の目的は、適切なインデントと標準式を見つけることであり、その言
語の完全なパーザを作ることではない。インデント計算に必要な手がかりとな
る終端記号を文法として入れておけばそれで十分である。また、非終端記号は
空にもマッチする。

どうしても演算子順位文法の形に直せない場合は、字句解析部分
(XXX-mode-forward-token, XXX-mode-backward-token) を工夫し、バッファ
から上記の文法に適した字句を取り出せるようにする。最後の手段としては、
インデント計算ルーチン（XXX-mode-smie-rules）で、自分で前後の字句を解析
してインデント量を計算する。

演算子順位文法では、全ての字句（演算子）はかならず順位が与えられる。例
えば、上記の

'((id)
  (inst ("begin" insts "end")
        ("if" exp "then" inst "else" inst)
        (id ":=" exp)
        (exp))
  (insts (insts ";" insts) (inst))
  (exp (exp "+" exp)
       (exp "*" exp)
       ("(" exps ")"))
  (exps (exps "," exps) (exp)))

では、"begin" と "end" は同じ括弧に現れるので順位は等しい。また、非
終端記号 insts から exp が導出され、exp から 終端記号 + が導出
されるので、insts を囲む begin は + より順位が高い。

しかし、上記のBNFでは exp は、exp + exp と exp "*" exp のどちらに
も導出されるので、exp + exp * exp という式が現れた場合、* と + の
どちらが順位が高いのか、上記のBNFだけでは分からない。または、insts から
insts ";" insts が展開できるが、 insts ; insts ; insts という式は、
左右どちらで区切ったら良いのか分からない。

そのため、 smie-bnf->prec2 では第２引数以降に、演算子の結合方向や順位
を指定できる。上記の例では、

'((assoc "+") (assoc "*"))

は、+ より * の方が優先度が高いことを、また、

'((assoc ";"))

は、";" 左右どちらで結合しても良いことを示している。

smie-prec2->grammar でBNFや演算子順位を演算子表に変換する際、しばしば
"Confilict" や、"Token XX is both neither and closer" 等の警告・エラー
が出る場合がある。これは、以下の様なケースで発生する。

1. 終端記号と非終端記号が同時に現れる式において、非終端記号の導出先で同 じ終端記号が現れる場合。

例：

(smie-prec2->grammar
  (smie-bnf->prec2
    '((a ("A" b "C")) ;; 同時に現れるので、A≐C
      (b (c))
      (c ("C")))) ;; b を導出すると "C" が現れるので、A⋖C だが、これはA≐Cと矛盾。

このような例は、異なる構造文で同じ予約語を使いまわしているプログラミ
ング言語で起こることがある。この場合は非終端記号の項を工夫して、で
きるだけ一つの終端記号は単独の非終端記号でしか出現しないようにする。

1. ある非終端記号が、BNF式の左右両端および中間の両方で現れる場合

(smie-prec2->grammar
  (smie-bnf->prec2
    '((a ("A" b "C")) ;; "A" は opener
      (b (c "A" d))))) ;; "A" は neither → 競合

このようなケースは、非終端記号の選択が上手く言っていない場合に起こる
ことがある。字句解析器や文法を工夫して、同じ終端記号は必ず、opener,
closer, neither のいずれかの役割のみを持たせるようにする。

字句解析器

納得できる文法ができたら、バッファから文法に渡す字句を取り出す解析器、
XXX-mode-backward-token と XXX-mode-forward-token を作る。

字句解析器はバッファのカーソル位置から前・後に走査を行い、終端記号が現
れたらそれを返すようにする。

解析途中で空白をスキップするには通常、

(skip-syntax-forward " ")

を、コメントをスキップするには、

(forward-comment (point-max)) ;; 前方向走査
(forward-comment (- (point))) ;; 後方向走査

を指定する。 "～" で囲まれた文字列をスキップするには、

(if (looking-back "\\s\"") (goto-char (scan-sexps (point) -1)))

のように、シンタックスを使った正規表現でカーソルの前後を確認し、囲まれ
ている部分を scan-sexp で飛ばす。これらの関数が適切に動作するためには、
前述の syntax-table 設定をしっかり行う必要がある。

Rubyのヒアドキュメントのような、特殊な字句を処理するには、字句解析器は
時には複雑になる。

インデント計算ルーチン

最後に、XXX-mode-smie-rules を用意する。この関数が nil を返す場合、
smie は指定された文法に対して、自前のインデント計算ルーチンを使用してイ
ンデントを行なう。

きちんと文法が書けたと思うのならば、まずはこの関数ででは何もせずに nil
を返させるようにして、smieの提供するインデントの動作を観察するのが良い
だろう。その挙動が意図しない場合は、徐々にこの関数を変更していく、とい
うアプローチをとると開発が楽になる。以下はマニュアルのサンプル例である
が、この例のように pcase を使うとすっきりする場合が多い。

(defun sample-smie-rules (kind token)
  (pcase (cons kind token)
    (`(:elem . basic) sample-indent-basic)
    (`(,_ . ",") (smie-rule-separator kind))
    (`(:after . ":=") sample-indent-basic)
    (`(:before . ,(or `"begin" `"(" `"{")))
     (if (smie-rule-hanging-p) (smie-rule-parent)))
    (`(:before . "if")
     (and (not (smie-rule-bolp)) (smie-rule-prev-p "else")
          (smie-rule-parent)))))

XXX-mode-smie-rules には、smie エンジンから KIND と TOKEN という２
つの引数が渡される。 KIND が :before の場合は、その TOKEN の前に
挿入するインデント量を返す。また、KIND が :after の場合は、その
TOKEN の後ろで改行が行われた場合の、次行のインデント量を返す。
TOKENだけでは情報不足である場合に備えて、 smie は様々な前後の文脈を解
析するルーチンを用意している（Emacs Lisp リファレンス 23.7.1.7 節参照）。

返り値は、(column . 数) のconsセルならば絶対位置を、単なる数字ならば、
:afterの場合は 前TOKENの位置、:before の場合は親TOKENの位置から
の相対量を指定する。他にも、特殊ケースとして :elem 等の引数が渡される
場合があるが、それらについても詳細は elisp リファレンスを参照されたい。

最後に

smie.el は、それまで「黒魔術」であったインデント計算を、「字句解析」・
「文法」・「インデント計算」に分離することで、この部分のコードの見通し
を大幅に良くすることを可能にした。これにより、今後はインデント
計算の実装やメンテナンスの負担が軽減されることが期待できる。

ただし、smie.el は、演算子単位で解析を行なうため、文脈に応じて演算子の
役割や優先順位が変わるような仕様の言語には対応しきれない。

smie.el は Emacs 24.3 から導入された。新しい Emacs 24.4 では、Rubyなど
のいくつかの言語のインデント計算ルーチンが smie.el 対応に書き換えられた。

具体的なサンプルを見たい人は、この Emacs 24.4 付属の ruby-mode や、
ocaml の tuareg-mode、または以下のsql-smie-mode が参考になると思われる。