Conao3 Notes

Lean本体と応答が同じで最大730倍速い言語サーバーLeansailを作った

Leanの言語サーバーLeansailを作りました。Lean本体の言語サーバー Lean.Server をそのまま組み込み、Mathlibで計測して遅いと分かった処理だけを直しています。応答の中身は本体と同じです。

いちばん差が出たのは、カーソルを置いた識別子の出現箇所を強調表示するハイライトで、LSPの textDocument/documentHighlight の要求にあたります。本体はこの要求のたびに文書内の参照索引を作り直します。Mathlibの78KBのファイルでは1回に672 msかかりました。Leansailは同じ版の文書で作った索引を使い回すので、2回目からは0.92 msで返ります。速さは本体の約730倍です。

ほかにも、初回のハイライトは5.7倍、補完は4.6倍、 workspace/symbol は9.7倍速くなりました。直した処理はすべてLeanで書いた部分にあります。Rustで書いた部分はエディタとのあいだの中継と、Leanで証明した規則の実行だけです。

リポジトリはconao3/rust-leansailで、ライセンスはApache-2.0です。この記事はLean 4.35.0とLeansail 0.1.0で動かした結果をもとに書いています。

構成

Leansailは、Rustで書いたhostと、Leanで書いたbackendの2つのプロセスで動きます。

img

hostはエディタとLSPで話し、受け取ったメッセージをbackendへ中継します。backendはLean.Serverを組み込んだ実行ファイルです。本体と同じく、Watchdogがプロジェクト全体の索引を持ち、開いたファイルごとにFileWorkerを起動して解析させます。hover、ゴールの表示、Widgetなど、Leanの言語サーバーの機能は本体の実装をそのまま使っています。

hostが自分で判断するのは、メッセージを中継してよいかどうかです。判断の規則はLeanで書いて証明し、leanfranでRustの関数にしています。初期化の前後や終了の後に届いたリクエストの扱いと、クライアントが対応を宣言していない要求の止め方をこの規則で決めます。FileWorkerが落ちたときの立て直し方も、同じように規則で決めます。

使い方

Lean 4.35.0のプロジェクトのルートで次のコマンドを実行すると、標準入出力で話す言語サーバーが起動します。Nixのパッケージには、backendと対応するLeanが入っています。

nix run github:conao3/rust-leansail -- server run-server

leansail をPATHに置いた場合、EmacsのEglotでは次のように設定します。依存ライブラリを使うプロジェクトでのコマンドは lake env leansail server run-server です。

(require 'eglot)
(define-derived-mode leansail-lean-mode prog-mode "Lean")
(add-to-list 'auto-mode-alist '("\\.lean\\'" . leansail-lean-mode))
(add-to-list 'eglot-server-programs
             '(leansail-lean-mode . ("leansail" "server" "run-server")))
(add-hook 'leansail-lean-mode-hook #'eglot-ensure)
(add-hook 'kill-emacs-hook #'eglot-shutdown-all)

Neovimの設定とゴールを表示するコマンドはREADMEにあります。

本体と同じ応答を返すことの確かめ方

速くしても応答が変わっては使えません。そこで、同じLean 4.35.0の lean --server とLeansailを並べて起動し、同じ操作の結果を比べる検査を用意しました。

  • 本体が扱う59種類のメッセージについて、応答を比べます。内訳は、リクエスト34件、クライアントからの通知10件、サーバーからのリクエスト3件と通知2件、Widgetの呼び出し10件です。解析の途中に届く通知の回数と順序は実行のたびに変わるので、最後の状態で比べます。
  • 編集の途中で取り消されたリクエストと、編集で古くなったリクエストに、それぞれ -32800 と -32801 のエラーが返ることを確かめます。
  • FileWorkerのプロセスを止めて、次のリクエストで同じ内容から立ち直ることを確かめます。
  • EmacsのEglotとNeovimの組み込みのLSPを画面なしで起動し、診断、hover、定義へのジャンプ、補完、ゴールの表示、閉じて開き直す操作の結果を本体と比べます。

通信が仕様どおりかは、以前作ったlsp-touchstoneで検査しています。最初に検査したとき、本体のbackendはクライアントが対応を宣言していない workspace/semanticTokens/refresh などのリクエストを送っていました。Leansailでは、hostがこのリクエストをクライアントへ送らず、backendには代わりに null を返します。これらの検査はすべてCIで回しています。

Leanで書いた規則

クライアントの宣言に応じてサーバーからの要求を通すかどうかは、次のように書いています。refreshCapability の定義とほかの定理は省きました。

inductive Decision where
  | forward | acknowledge | unsupported
  deriving DecidableEq, Repr

def decide (method : String) (declared registrationsAllowed : Bool) : Decision :=
  if method == "client/registerCapability" then
    if registrationsAllowed then .forward else .unsupported
  else
    match refreshCapability method with
    | some _ => if declared then .forward else .acknowledge
    | none => .forward

theorem refresh_requires_support (method path : String)
    (h : refreshCapability method = some path)
    (hr : (method == "client/registerCapability") = false) (declared : Bool)
    (registrationsAllowed : Bool) :
    decide method declared registrationsAllowed = .forward ↔ declared = true := by
  cases declared <;> simp [decide, hr, h]

refresh_requires_support は、refreshの要求をクライアントへ通すのは、クライアントが対応を宣言したときだけであることを示しています。このコードはRustのソースの leanfran::lean! の中に書きました。ビルドのときにLeanが証明を検査し、leanfranがRustの関数にします。lifecycle、取り消しと古いリクエストの判定、FileWorkerの立て直しも同じ形で書いていて、定理は21件です。hostはJSONを読んで宣言の有無を取り出し、この関数の結果に従って中継します。

Mathlibで計測して分かったこと

計測には、Mathlib v4.35.0の3つのファイルを開いて編集する手順を使いました。いちばん大きいのは78KBの IntegralEqImproper.lean で、ほかの2つは FiniteDimension.lean と、397個のファイルをimportする Mathlib/Tactic.lean です。6コアのマシンで、ほかのプロセスの負荷が低い回だけを各条件5回ずつ採用しました。

まず、言語サーバーがどこに時間を使っているかをperfで調べました。CPU時間の78.7%はFileWorker、17.7%はWatchdogで、Rustのhostは0.15%でした。FileWorkerの時間の多くは証明の検査と型クラスの推論です。中継をRustで速くしても縮む時間はほとんどありません。そこで、言語サーバーが自分で計算している部分を探して直しました。

IntegralEqImproper.lean で本体とLeansailを同じ回の計測の中で交互に動かして測った中央値です。

img

処理 本体 Leansail 比
ハイライト (初回) 674 ms 118 ms 5.7倍
ハイライト (2回目以降) 672 ms 0.92 ms 730倍
semantic tokens (2回目以降) 75 ms 4.0 ms 19倍
補完 (2回目以降) 322 ms 70 ms 4.6倍
workspace/symbol 851 ms 87 ms 9.7倍
参照 21 ms 13 ms 1.6倍
定義 21 ms 13 ms 1.6倍
hover 1.4 ms 1.4 ms 0.94倍
plainGoal 1.4 ms 1.6 ms 0.92倍
プロジェクトの索引の準備 21.4 秒 5.5 秒 3.9倍
3つの文書を解析した直後のメモリ 3596 MiB 2526 MiB 1.4倍

hoverと plainGoal は本体より0.1 msほど遅くなります。メモリは全プロセスのPSSの合計です。

  • ハイライトは、importしたモジュールの名前の配列を識別子ごとに作り直していました。配列を作らずに直接引くようにし、同じ版の文書では作った索引を使い回します。
  • semantic tokensは、同じ版の文書に対して作った応答を使い回します。
  • 補完は、importした定数の中から候補を探した結果を、名前空間と open が同じあいだ使い回します。
  • workspace/symbol と索引は、MathlibとLeanの約1万2千個の .ilean から毎回作っていた索引を保存し、次の起動では読み込むだけにしました。

使い回す結果が毎回計算した結果と等しいことはLeanの定理で示しています。応答の中身はどの処理でも本体と一致しました。ファイルを開いてから最初の診断が出るまでは、本体が6.9秒、Leansailが7.0秒でした。ほとんど差はありません。ここはLakeの準備、import、ファイルの解析にかかる時間で、言語サーバーの外にあります。

計測を重ねても、Rustに移すと速くなる処理は見つかりませんでした。FileWorkerの管理をRustに移す案も、3つのファイルを同時に解析させて測ったうえで、効果が小さいので見送りました。

計測の条件、全部の表、再現の手順はdocs/mathlib-benchmark.mdにあります。