lsp-mode ファイルウォッチャー: 計算量複雑性分析

要約

lsp-watch-root-folder は O(D × E × R) の正規表現マッチ を 無制限のディレクトリツリー 全体で実行するため、Emacs をフリーズさせる。ここで D は走査された総ディレクトリ数、E はディレクトリあたりのエントリ数、R は無視ディレクトリの正規表現パターン数(デフォルト約60)である。シンボリックリンクがプロジェクトルートから逸脱すると、D は 200,000 以上に達し、結果として 1億2000万以上の正規表現評価 が発生する。さらに f-join がインタープリタ実行時にはマクロ展開のオーバーヘッドで CPU の52%を消費し、全走査が Emacs のシングルスレッドイベントループを完全にブロックする。

データフロー概要

flowchart TD
    LSP["LSP Server が<br/>workspace/didChangeWatchedFiles を登録"]
    REG["lsp--server-register-capability<br/>エントリーポイント (L3964)"]
    ROOTS["lsp-find-roots-for-workspace<br/>ワークスペースのルートフォルダ取得"]
    MKWATCH["make-lsp-watch<br/>watch 構造体作成<br/>:root-directory = 生パス"]
    IGNORED["lsp--get-ignored-regexes-for-workspace-root<br/>約60+3の正規表現パターンを収集"]
    TMPBUF["lsp--with-workspace-temp-buffer<br/>dir-local 変数の解決"]
    IGNOREDVAR["lsp-file-watch-ignored-directories<br/>変数値を返す"]

    LSP --> REG
    REG --> ROOTS
    REG --> MKWATCH
    REG --> IGNORED
    IGNORED --> TMPBUF --> IGNOREDVAR

    subgraph watcher_create ["ウォッチャー作成"]
        WATCH["lsp-watch-root-folder (L2121)"]
        SYMLINK_BUG["f-symlink? + file-truename<br/>シンボリックリンク解決"]:::bug
        BUG_NOTE["BUG: watch.root-directory と<br/>走査パスの不一致"]:::danger
        WATCH --> SYMLINK_BUG --> BUG_NOTE
    end

    REG --> WATCH

    subgraph recursive_scan ["再帰的走査"]
        ALLWATCH["lsp--all-watchable-directories (L2097)"]
        SYMRESOLVE["f-symlink? + file-truename<br/>各ディレクトリでシンボリックリンク解決"]
        CYCLE["gethash visited<br/>サイクル検出 — 無限ループ防止のみ"]
        DIRFILES["directory-files<br/>現在のディレクトリのエントリをリスト"]

        ALLWATCH --> SYMRESOLVE
        ALLWATCH --> CYCLE
        ALLWATCH --> DIRFILES

        subgraph filter_phase ["-filter — dash.el のフィルタ関数"]
            PATHWATCH["lsp--path-is-watchable-directory<br/>各エントリをフィルタ (L2085)"]
            FJOIN["f-join dir path"]:::bottleneck
            FJOIN_INTERP["インタープリタ実行時:<br/>cconv-make-interpreted-closure<br/>→ macroexpand-all 毎回マクロ展開<br/>→ f-expand → expand-file-name<br/>→ f-relative-p, f-absolute-p"]
            FILEACC["file-accessible-directory-p<br/>stat(2) システムコール"]
            DOTCHECK["equal path '.' / '..'<br/>カレント・親ディレクトリ除外"]
            STRMATCH["lsp--string-match-any"]:::bottleneck
            DASHFIRST["--first (dash.el) → while ループ<br/>string-match × R<br/>最大60回の正規表現評価"]

            PATHWATCH --> FJOIN
            FJOIN --> FJOIN_INTERP
            PATHWATCH --> FILEACC
            PATHWATCH --> DOTCHECK
            PATHWATCH --> STRMATCH
            STRMATCH --> DASHFIRST
        end

        DIRFILES --> PATHWATCH

        MAP["-map — dash.el のマップ関数"]
        RECURSE["再帰呼び出し:<br/>lsp--all-watchable-directories"]
        FJOIN2["f-join dir path"]:::bottleneck
        NCONC["apply #'nconc<br/>結果リストを破壊的に連結<br/>+ list dir — cons セル割り当て"]

        ALLWATCH --> MAP --> RECURSE --> FJOIN2
        RECURSE -.->|再帰| ALLWATCH
        ALLWATCH --> NCONC
    end

    SYMLINK_BUG --> ALLWATCH

    subgraph result_phase ["結果処理"]
        DIRS["dirs-to-watch<br/>結果リスト: D 個のディレクトリパス文字列"]
        LENGTH["length dirs-to-watch — O(D) のリスト走査<br/>s-join — O(D) のログ文字列生成"]
        THRESHOLD["lsp-file-watch-threshold チェック<br/>D > 1000 なら警告"]
        DIRS --> LENGTH --> THRESHOLD
    end

    NCONC --> DIRS

    subgraph os_watch ["OS ウォッチャー登録"]
        DOLIST["dolist current-dir dirs-to-watch<br/>D 回のループ"]
        FNOTIFY["file-notify-add-watch"]
        LINUX["Linux: inotify_add_watch(2)"]
        MACOS["macOS: FSEvents / kqueue"]
        WIN["Windows: ReadDirectoryChangesW"]
        DOLIST --> FNOTIFY
        FNOTIFY --> LINUX
        FNOTIFY --> MACOS
        FNOTIFY --> WIN
    end

    THRESHOLD --> DOLIST

    subgraph runtime ["ランタイムコールバック"]
        CALLBACK["lsp--folder-watch-callback<br/>イベント発生時"]
        NEWDIR["新ディレクトリ作成時"]
        WATCHAGAIN["lsp-watch-root-folder<br/>再帰的にウォッチ追加"]
        DIRRECUR["directory-files-recursively"]:::vulnerability
        VULNNOTE["INCLUDE-DIRECTORIES=t → シンボリックリンクを追跡<br/>visited テーブルなし、境界チェックなし"]:::danger
        FILECHANGE["ファイル変更時"]
        PROCESS["lsp--file-process-event<br/>glob パターンマッチ (L3932)"]
        CLLOOP["cl-loop for re in regexes<br/>キャッシュ済み正規表現<br/>string-match — 効率的 O(G)"]

        CALLBACK --> NEWDIR
        NEWDIR --> WATCHAGAIN
        NEWDIR --> DIRRECUR --> VULNNOTE
        CALLBACK --> FILECHANGE --> PROCESS --> CLLOOP
    end

    FNOTIFY --> CALLBACK

    classDef bottleneck fill:#ff9,stroke:#f90,stroke-width:3px,color:#000
    classDef bug fill:#fcc,stroke:#f00,stroke-width:2px,color:#000
    classDef danger fill:#f66,stroke:#c00,stroke-width:3px,color:#fff
    classDef vulnerability fill:#f96,stroke:#f60,stroke-width:3px,color:#000

具体的なトレース例: Rust プロジェクト

以下の Rust プロジェクト構造で、rust-analyzer が workspace/didChangeWatchedFiles を登録する際の完全なコールチェーンを追跡する。

/home/user/rust-project/           ← プロジェクトルート
├── src/                           (5 ファイル, 2 サブディレクトリ)
│   ├── main.rs
│   ├── lib.rs
│   ├── utils/                     (3 ファイル)
│   │   ├── mod.rs
│   │   ├── helper.rs
│   │   └── config.rs
│   └── models/                    (2 ファイル)
│       ├── mod.rs
│       └── user.rs
├── tests/                         (3 ファイル, 1 サブディレクトリ)
│   ├── integration_test.rs
│   ├── common/                    (1 ファイル)
│   │   └── mod.rs
│   └── fixtures/                  (2 ファイル)
│       ├── sample.json
│       └── test_data.toml
├── target/                        ★ シンボリックリンク → /nix/store/abc123.../
├── .git/                          (数百のオブジェクト)
├── Cargo.toml
├── Cargo.lock
└── README.md

コールチェーン詳細トレース

Phase 1: 登録開始

rust-analyzer が以下の JSON-RPC メッセージを送信する:

{
  "method": "client/registerCapability",
  "params": {
    "registrations": [{
      "id": "workspace/didChangeWatchedFiles-1",
      "method": "workspace/didChangeWatchedFiles",
      "registerOptions": {
        "watchers": [
          { "globPattern": "**/*.rs", "kind": 7 },
          { "globPattern": "**/*.toml", "kind": 7 },
          { "globPattern": "**/Cargo.lock", "kind": 7 }
        ]
      }
    }]
  }
}

重要: lsp-mode はここでの glob パターン (**/*.rs) をウォッチャー作成時に一切使用しない。これらは後のイベントフィルタリング (L3932) でのみ使われる。

Phase 2: `lsp--server-register-capability` (L3964)

flowchart TD
    P2_1["lsp--server-register-capability"]
    P2_2["method = 'workspace/didChangeWatchedFiles'<br/>→ 条件成立"]
    P2_3["created-watches = lsp-session-watches<br/>→ 空の hash-table"]
    P2_4["root-folders = lsp-find-roots-for-workspace<br/>→ '/home/user/rust-project'"]
    P2_5["cl-set-difference<br/>→ '/home/user/rust-project'<br/>まだウォッチなし"]
    P2_6["dolist folder = '/home/user/rust-project'"]

    P2_7["make-lsp-watch<br/>:root-directory '/home/user/rust-project'"]
    P2_7N["生パス truename ではない"]
    P2_8["lsp--get-ignored-regexes-for-workspace-root"]
    P2_8D["ignored-files: 3パターン<br/>ignored-dirs: 60パターン"]
    P2_9["puthash '/home/user/rust-project' watch"]
    P2_9N["キー = 生パス"]
    P2_10["lsp-watch-root-folder<br/>dir = file-truename '/home/user/rust-project'<br/>この例ではシンボリックリンクでない"]
    P2_10N["callback に渡される root-folder も生パス<br/>watch.root-directory も生パス"]

    P2_1 --> P2_2 --> P2_3 --> P2_4 --> P2_5 --> P2_6
    P2_6 --> P2_7 --> P2_8 --> P2_9 --> P2_10
    P2_7 -.- P2_7N
    P2_8 -.- P2_8D
    P2_9 -.- P2_9N
    P2_10 -.- P2_10N

    classDef bug fill:#ff6b6b,stroke:#c0392b,color:#fff
    classDef note fill:#fff3cd,stroke:#856404,color:#856404
    class P2_7N,P2_9N,P2_10N bug
    class P2_8D note

Phase 3: `lsp-watch-root-folder` (L2121)

flowchart TD
    P3_1["lsp-watch-root-folder<br/>dir = '/home/user/rust-project'"]
    P3_2{"f-symlink?<br/>'/home/user/rust-project'"}
    P3_3["→ nil<br/>シンボリックリンクではない"]
    P3_4["dir はそのまま<br/>'/home/user/rust-project'"]
    P3_5["watch = 引数から受け取った<br/>watch 構造体"]
    P3_6["lsp--all-watchable-directories<br/>'/home/user/rust-project'<br/>ignored-directories"]
    P3_7["Phase 4 へ"]

    P3_1 --> P3_2
    P3_2 -- "nil" --> P3_3 --> P3_4 --> P3_5 --> P3_6 --> P3_7

Phase 4: `lsp--all-watchable-directories` — 再帰走査の詳細

以下は、ルートディレクトリ /home/user/rust-project から走査が始まる瞬間の、完全なコールトレースである。

flowchart TD
    subgraph init ["初期セットアップ"]
        P4_1["lsp--all-watchable-directories<br/>'/home/user/rust-project', ignored-dirs, nil"]
        P4_2{"f-symlink?"}
        P4_3["visited = make-hash-table :test 'equal"]
        P4_4["gethash → nil 未訪問"]
        P4_5["puthash → visited に追加"]
        P4_6["directory-files<br/>→ 9 エントリ E=9<br/>. / .. / .git / Cargo.lock / Cargo.toml<br/>README.md / src / target / tests"]
        P4_1 --> P4_2 -- "nil" --> P4_3 --> P4_4 --> P4_5 --> P4_6
    end

    P4_6 --> FILTER["-filter: 各エントリに<br/>lsp--path-is-watchable-directory を適用"]

    subgraph entry_dot ["エントリ '.'"]
        D1_1["f-join → '/.../.'\n文字列アロケーション"]
        D1_2{"equal '.' '.'"}
        D1_3["除外\n正規表現評価なし"]:::fast_exit
        D1_1 --> D1_2 -- "t" --> D1_3
    end

    subgraph entry_dotdot ["エントリ '..'"]
        D2_1["f-join → '/...' に正規化"]
        D2_2{"equal '..' '..'"}
        D2_3["除外"]:::fast_exit
        D2_1 --> D2_2 -- "t" --> D2_3
    end

    subgraph entry_git ["エントリ '.git'"]
        D3_1["f-join → '.../.git'"]
        D3_2{"file-accessible-directory-p"}
        D3_3["equal '.'/'..' → nil"]
        D3_4["string-match-any"]
        D3_5["パターン1 マッチ!\n位置27でヒット"]:::early_match
        D3_6["除外\n早期終了: 1パターン目"]:::early_match
        D3_1 --> D3_2 -- "t" --> D3_3 --> D3_4 --> D3_5 --> D3_6
    end

    subgraph entry_cargo ["エントリ 'Cargo.lock'"]
        D4_1["f-join → '.../Cargo.lock'"]
        D4_2{"file-accessible-directory-p"}
        D4_3["除外\nファイルでありディレクトリではない"]:::fast_exit
        D4_1 --> D4_2 -- "nil" --> D4_3
    end

    subgraph entry_src ["エントリ 'src'"]
        D5_1["f-join → '.../src'"]
        D5_2{"file-accessible-directory-p"}
        D5_3["equal '.'/'..' → nil"]
        D5_4["string-match-any\n60パターン全て不一致"]
        D5_5["INCLUDED 監視対象"]:::worst_case
        D5_N["全60パターンを試行:\nこれが最悪ケース"]:::worst_case
        D5_1 --> D5_2 -- "t" --> D5_3 --> D5_4 --> D5_5
        D5_4 -.- D5_N
    end

    subgraph entry_target ["エントリ 'target'"]
        D6_1["f-join → '.../target'"]
        D6_2{"file-accessible-directory-p"}
        D6_3["string-match-any"]
        D6_4["パターン1-26: 不一致\nパターン27 マッチ!"]:::early_match
        D6_5["除外\n27パターン目で早期終了"]:::early_match
        D6_N["もし ignore リストになければ:\nf-symlink? → t → file-truename\n→ '/nix/store/abc123.../'\nNix ストア全体を走査開始"]:::worst_case
        D6_1 --> D6_2 -- "t" --> D6_3 --> D6_4 --> D6_5
        D6_5 -.- D6_N
    end

    subgraph entry_tests ["エントリ 'tests'"]
        D7_1["f-join → '.../tests'"]
        D7_2{"file-accessible-directory-p"}
        D7_3["string-match-any\n60パターン全て不一致"]
        D7_4["INCLUDED 監視対象"]:::worst_case
        D7_1 --> D7_2 -- "t" --> D7_3 --> D7_4
    end

    FILTER --> entry_dot
    FILTER --> entry_dotdot
    FILTER --> entry_git
    FILTER --> entry_cargo
    FILTER --> entry_src
    FILTER --> entry_target
    FILTER --> entry_tests

    FILTER_R["-filter 結果: src, tests\n9エントリから2つが生存"]
    entry_dot --> FILTER_R
    entry_dotdot --> FILTER_R
    entry_git --> FILTER_R
    entry_cargo --> FILTER_R
    entry_src --> FILTER_R
    entry_target --> FILTER_R
    entry_tests --> FILTER_R

    FILTER_R --> MAP["-map: 生存した各エントリに再帰呼び出し"]

    subgraph recurse_src ["再帰: .../src"]
        RS_1["directory-files\n→ . / .. / lib.rs / main.rs / models / utils"]
        RS_2["lib.rs → nil ファイル\nmain.rs → nil ファイル"]:::fast_exit
        RS_3["models → t 60パターン不一致\nutils → t 60パターン不一致"]:::worst_case
        RS_4["再帰: .../src/models\ndirectory-files → mod.rs, user.rs\n全てファイル → 空"]:::fast_exit
        RS_5["再帰: .../src/utils\ndirectory-files → config.rs, helper.rs, mod.rs\n全てファイル → 空"]:::fast_exit
        RS_R["結果:\n.../src\n.../src/models\n.../src/utils"]:::result
        RS_1 --> RS_2
        RS_1 --> RS_3
        RS_3 --> RS_4
        RS_3 --> RS_5
        RS_4 --> RS_R
        RS_5 --> RS_R
    end

    subgraph recurse_tests ["再帰: .../tests"]
        RT_1["directory-files\n→ . / .. / common / fixtures / integration_test.rs"]
        RT_2["common → t 60パターン不一致\nfixtures → t 60パターン不一致"]:::worst_case
        RT_3["再帰: .../tests/common\n→ 結果: .../tests/common"]:::fast_exit
        RT_4["再帰: .../tests/fixtures\n→ 結果: .../tests/fixtures"]:::fast_exit
        RT_R["結果:\n.../tests\n.../tests/common\n.../tests/fixtures"]:::result
        RT_1 --> RT_2
        RT_2 --> RT_3
        RT_2 --> RT_4
        RT_3 --> RT_R
        RT_4 --> RT_R
    end

    MAP --> recurse_src
    MAP --> recurse_tests

    NCONC["nconc で結合\ndirs-to-watch = 7 ディレクトリ\n/.../rust-project\n/.../src, /.../src/models, /.../src/utils\n/.../tests, /.../tests/common, /.../tests/fixtures"]:::result

    recurse_src --> NCONC
    recurse_tests --> NCONC

    classDef fast_exit fill:#d4edda,stroke:#28a745,color:#155724
    classDef early_match fill:#fff3cd,stroke:#ffc107,color:#856404
    classDef worst_case fill:#f8d7da,stroke:#dc3545,color:#721c24
    classDef result fill:#cce5ff,stroke:#0d6efd,color:#004085

Phase 4 の統計 (この Rust プロジェクトの場合)

操作	回数	備考
`directory-files`	7回	D=7 ディレクトリ
`f-join`	32回	`-filter` 内 (7ディレクトリ × 平均4.6エントリ) + `-map` 内 (8サブディレクトリ)
`file-accessible-directory-p`	18回	"." と ".." を除く全エントリ
`string-match`	560回	正規表現マッチが必要な10ディレクトリエントリ × 平均56パターン
`f-symlink?`	7回	各ディレクトリの入口で1回

この小さなプロジェクトでは問題なし。 しかし、target/ が無視リストになければ:

flowchart TD
    T0["target/"]
    T1["/nix/store/abc123.../"]
    T0 -- "symlink" --> T1

    T1 --> BIN["bin/<br/>100+ ファイル"]
    T1 --> LIB["lib/<br/>数千ファイル"]
    T1 --> SHARE["share/<br/>数千ファイル"]
    T1 --> DEPS["他の Nix パッケージ<br/>への依存関係"]

    DEPS --> DEP1["依存パッケージ A"]
    DEPS --> DEP2["依存パッケージ B"]
    DEPS --> DEP3["..."]

    DEP1 --> DEP1_BIN["bin/"]
    DEP1 --> DEP1_LIB["lib/"]
    DEP1 --> DEP1_SHARE["share/"]
    DEP1 --> DEP1_DEPS["さらに依存関係..."]

    DEP2 --> DEP2_BIN["bin/"]
    DEP2 --> DEP2_LIB["lib/"]
    DEP2 --> DEP2_DEPS["さらに依存関係..."]

    EXPLOSION["D = 200,000+ に爆発"]:::explosion

    DEP1_DEPS --> EXPLOSION
    DEP2_DEPS --> EXPLOSION

    classDef explosion fill:#dc3545,stroke:#721c24,color:#fff,font-weight:bold

Phase 5: ウォッチャー作成 (L2147-2156)

flowchart TD
    P5_1["lsp-watch-root-folder 続き"]
    P5_2["length dirs-to-watch → 7"]
    P5_3["s-join → ログ文字列生成"]
    P5_4{"warn-big-repo? = t<br/>lsp-file-watch-threshold = 1000<br/>7 < 1000 ?"}
    P5_5["閾値以内、警告なし"]
    P5_6["dolist current-dir dirs-to-watch"]

    P5_1 --> P5_2 --> P5_3 --> P5_4 -- "t" --> P5_5 --> P5_6

    P5_6 --> W1["file-notify-add-watch<br/>'.../rust-project'<br/>→ descriptor 1"]
    P5_6 --> W2["file-notify-add-watch<br/>'.../src'<br/>→ descriptor 2"]
    P5_6 --> W3["file-notify-add-watch<br/>'.../src/models'<br/>→ descriptor 3"]
    P5_6 --> W4["file-notify-add-watch<br/>'.../src/utils'<br/>→ descriptor 4"]
    P5_6 --> W5["file-notify-add-watch<br/>'.../tests'<br/>→ descriptor 5"]
    P5_6 --> W6["file-notify-add-watch<br/>'.../tests/common'<br/>→ descriptor 6"]
    P5_6 --> W7["file-notify-add-watch<br/>'.../tests/fixtures'<br/>→ descriptor 7"]

    TOTAL["合計: 7個の OS ウォッチャーが登録される"]:::result
    W1 --> TOTAL
    W2 --> TOTAL
    W3 --> TOTAL
    W4 --> TOTAL
    W5 --> TOTAL
    W6 --> TOTAL
    W7 --> TOTAL

    classDef result fill:#cce5ff,stroke:#0d6efd,color:#004085

Phase 6: ランタイムイベント処理

src/main.rs を保存した場合:

sequenceDiagram
    participant OS as OS<br/>inotify/kqueue/FSEvents
    participant EN as Emacs<br/>file-notify ハンドラ
    participant CB as lsp--folder-watch-callback
    participant FP as lsp--file-process-event
    participant LSP as LSP Server

    OS->>EN: イベント発火
    EN->>CB: event = descriptor, changed,<br/>".../src/main.rs"

    Note over CB: file-name = ".../src/main.rs"<br/>event-type = changed

    CB->>CB: file-directory-p → nil<br/>ファイルなのでディレクトリ分岐をスキップ
    CB->>CB: memq changed → t
    CB->>CB: file-directory-p → nil 再確認
    CB->>CB: string-match-any ignored-files<br/>→ nil flycheck_*, .#*, ~ いずれも不一致

    CB->>FP: funcall callback event<br/>session, "/home/user/rust-project", event

    Note over FP: changed-file = ".../src/main.rs"<br/>f-relative → "src/main.rs"<br/>event-numeric-kind = 2 Changed

    FP->>FP: cl-loop for capability ...<br/>method = "workspace/didChangeWatchedFiles" → 一致

    FP->>FP: cl-loop for fs-watcher ...<br/>glob-pattern = "**/*.rs"<br/>lsp-glob-to-regexps → regex<br/>string-match regex "src/main.rs" → マッチ!

    FP->>LSP: lsp-notify<br/>"workspace/didChangeWatchedFiles"<br/>LSP サーバーへ通知送信

ステップバイステップの計算量

ステップ1: エントリー — `lsp--server-register-capability` (L3964)

(lsp-defun lsp--server-register-capability ((&Registration :method :id :register-options?))
  (when (and lsp-enable-file-watchers
             (equal method "workspace/didChangeWatchedFiles"))
    (-let* ((created-watches (lsp-session-watches (lsp-session)))
            (root-folders (cl-set-difference
                           (lsp-find-roots-for-workspace lsp--cur-workspace (lsp-session))
                           (ht-keys created-watches))))
      (dolist (folder root-folders)
        (let* ((watch (make-lsp-watch :root-directory folder))  ;; ★ 生パスを格納
               (ignored-things (lsp--get-ignored-regexes-for-workspace-root folder))
               (ignored-files-regex-list (car ignored-things))
               (ignored-directories-regex-list (cadr ignored-things)))
          (puthash folder watch created-watches)
          (lsp-watch-root-folder (file-truename folder)   ;; ★ truename で走査
                                 (-partial #'lsp--file-process-event (lsp-session) folder)
                                 ;;                                               ^^^^^^
                                 ;;                                               生パスを callback に束縛
                                 ignored-files-regex-list
                                 ignored-directories-regex-list
                                 watch
                                 t))))))

操作	計算量	備考
`lsp-session-watches`	O(1)	ハッシュテーブルのルックアップ
`lsp-find-roots-for-workspace`	O(F)	F = `folder->servers` のキー数。通常1-5
`cl-set-difference`	O(W × C)	W = ルート数、C = 既存ウォッチ数
`lsp--get-ignored-regexes-for-workspace-root`	O(1)	dir-local 変数の読み取り
`make-lsp-watch`	O(1)	構造体 + 空ハッシュテーブル作成
`file-truename`	O(L)	L = シンボリックリンク解決ホップ数 (通常1-3)
`root-folders` のループ	O(W)	W = ワークスペースルート数 (通常1)

コスト: 無視できる程度。ボトルネックは lsp-watch-root-folder 以降。

ステップ2: `f-join` 内部 — なぜインタープリタ実行時に遅いのか

f-join は lsp-mode のファイルウォッチャーで 最も頻繁に呼び出される関数 である。lsp--path-is-watchable-directory (L2090) と lsp--all-watchable-directories (L2116) の両方で、すべてのディレクトリエントリに対して呼び出される。

`f-join` のソースコード (f.el L70-87)

(defun f-join (&rest args)
  "Join ARGS to a single path."
  (let (path
        (relative (f-relative-p (car args))))   ;; ← f-relative-p もまたラッパー関数
    (mapc
     (lambda (arg)                               ;; ← ★ この lambda が問題
       (setq path (cond ((not path) arg)
                        ((f-absolute-p arg)      ;; ← f-absolute-p もラッパー
                         (progn
                           (setq relative nil)
                           arg))
                        (t (f-expand arg path))))) ;; ← f-expand は expand-file-name のラッパー
     args)
    (if relative (f-relative path) path)))

バイトコンパイル済み vs インタープリタ実行の差異

バイトコンパイル済みの場合:

flowchart LR
    FJB_1["f-join<br/>'/home/user/project' 'src'"]
    FJB_2["f-relative-p<br/>→ C プリミティブ"]
    FJB_3["mapc + lambda<br/>コンパイル済みバイトコード<br/>約2us"]
    FJB_4["f-expand<br/>→ expand-file-name<br/>→ C プリミティブ"]
    FJB_R["結果:<br/>'/home/user/project/src'<br/>合計: 約2-5us"]:::fast

    FJB_1 --> FJB_2 --> FJB_3 --> FJB_4 --> FJB_R

    classDef fast fill:#d4edda,stroke:#28a745,color:#155724

インタープリタ実行の場合 (f.el が .elc なしで読み込まれた場合):

flowchart LR
    FJI_1["f-join<br/>'/home/user/project' 'src'"]
    FJI_2["f-relative-p<br/>→ C プリミティブ<br/>同じ"]
    FJI_3["mapc + lambda S式"]:::slow

    subgraph closure ["Step A: cconv-make-interpreted-closure"]
        direction TB
        CA_1["lambda ボディを解析"]:::slow
        CA_2["フリー変数 path, relative<br/>をキャプチャ"]:::slow
        CA_3["macroexpand-all:<br/>cond → if/let 入れ子<br/>f-absolute-p, f-expand<br/>内マクロも展開"]:::slow
        CA_4["新クロージャオブジェクト<br/>ヒープ割り当て"]:::slow
        CA_1 --> CA_2 --> CA_3 --> CA_4
    end

    subgraph apply ["Step B: クロージャ適用"]
        direction TB
        CB_1["各引数に適用"]:::slow
        CB_2["インタープリタが<br/>S式を再帰的に eval"]:::slow
        CB_1 --> CB_2
    end

    subgraph gc ["Step C: GC プレッシャー"]
        direction TB
        CC_1["クロージャオブジェクト<br/>cons セル複数個"]:::slow
        CC_2["マクロ展開の<br/>中間リスト"]:::slow
        CC_3["呼び出し終了後<br/>すべてがゴミになる"]:::slow
        CC_1 --> CC_2 --> CC_3
    end

    FJI_4["f-expand<br/>→ expand-file-name<br/>→ C プリミティブ<br/>同じ"]
    FJI_R["結果:<br/>'/home/user/project/src'<br/>合計: 約50us<br/>バイトコンパイル時の約25倍"]:::slow

    FJI_1 --> FJI_2 --> FJI_3
    FJI_3 --> closure --> apply --> gc
    gc --> FJI_4 --> FJI_R

    classDef slow fill:#f8d7da,stroke:#dc3545,color:#721c24

直接比較: `f-join` vs `expand-file-name`

;; f-join (インタープリタ実行時): 約50μs/呼び出し
(f-join dir path)
  → f-relative-p (ラッパー)
  → cconv-make-interpreted-closure (クロージャ生成)
    → macroexpand-all (マクロ展開)
  → mapc (リスト走査)
  → f-absolute-p (ラッパー)
  → f-expand (ラッパー)
    → expand-file-name (Cプリミティブ)
  → f-relative or identity (条件分岐)

;; expand-file-name (C プリミティブ): 約0.5μs/呼び出し
(expand-file-name path dir)
  → Fexpand_file_name() in C
  → 直接文字列操作、中間オブジェクト生成なし

速度差: 約100倍 (f-join インタープリタ vs expand-file-name ネイティブ)

issue #4816 からの実測データ

D = 約5,000 ディレクトリ
E = 約20 エントリ/ディレクトリ
f-join 呼び出し回数 = D × E + D(再帰の-map内) ≈ 105,000
50μs/呼び出し × 105,000 = 5.25秒  (CPU プロファイルの 52%)

ステップ3: 正規表現マッチング深掘り — `lsp--string-match-any`

`--first` マクロの展開

--first は dash.el のアナフォリックマクロである。コンパイル時（またはインタープリタ実行時にマクロ展開されて）以下の while ループに変換される:

;; ソースコード:
(--first (condition-case err
             (string-match it str)
           (invalid-regexp ...))
         regex-list)

;; dash.el による展開結果 (概念的):
(let ((--list regex-list)
      (--result nil))
  (while (and --list (not --result))
    (let ((it (car --list)))           ;; 'it' がアナフォリック変数
      (when (condition-case err
                (string-match it str)
              (invalid-regexp ...))
        (setq --result it)))
    (setq --list (cdr --list)))
  --result)

60パターンの走査: 具体例

パス /home/user/rust-project/src/utils に対する lsp--string-match-any の実行:

(lsp--string-match-any ignored-directories "/home/user/rust-project/src/utils")

パターン  1: "[/\\]\\.git\\'"         vs ".../src/utils" → nil  (string-match ~1μs)
パターン  2: "[/\\]\\.github\\'"      vs ".../src/utils" → nil
パターン  3: "[/\\]\\.gitlab\\'"      vs ".../src/utils" → nil
パターン  4: "[/\\]\\.circleci\\'"    vs ".../src/utils" → nil
パターン  5: "[/\\]\\.hg\\'"          vs ".../src/utils" → nil
パターン  6: "[/\\]\\.bzr\\'"         vs ".../src/utils" → nil
パターン  7: "[/\\]_darcs\\'"         vs ".../src/utils" → nil
パターン  8: "[/\\]\\.svn\\'"         vs ".../src/utils" → nil
パターン  9: "[/\\]_FOSSIL_\\'"       vs ".../src/utils" → nil
パターン 10: "[/\\]\\.jj\\'"          vs ".../src/utils" → nil
パターン 11: "[/\\]\\.idea\\'"        vs ".../src/utils" → nil
パターン 12: "[/\\]\\.ensime_cache\\'"vs ".../src/utils" → nil
パターン 13: "[/\\]\\.eunit\\'"       vs ".../src/utils" → nil
パターン 14: "[/\\]node_modules"      vs ".../src/utils" → nil
パターン 15: "[/\\]\\.yarn\\'"        vs ".../src/utils" → nil
パターン 16: "[/\\]\\.turbo\\'"       vs ".../src/utils" → nil
パターン 17: "[/\\]\\.fslckout\\'"    vs ".../src/utils" → nil
パターン 18: "[/\\]\\.tox\\'"         vs ".../src/utils" → nil
パターン 19: "[/\\]\\.nox\\'"         vs ".../src/utils" → nil
パターン 20: "[/\\]dist\\'"           vs ".../src/utils" → nil
パターン 21: "[/\\]dist-newstyle\\'"  vs ".../src/utils" → nil
パターン 22: "[/\\]\\.hifiles\\'"     vs ".../src/utils" → nil
パターン 23: "[/\\]\\.hiefiles\\'"    vs ".../src/utils" → nil
パターン 24: "[/\\]\\.stack-work\\'"  vs ".../src/utils" → nil
パターン 25: "[/\\]\\.bloop\\'"       vs ".../src/utils" → nil
パターン 26: "[/\\]\\.bsp\\'"         vs ".../src/utils" → nil
パターン 27: "[/\\]\\.metals\\'"      vs ".../src/utils" → nil
パターン 28: "[/\\]target\\'"         vs ".../src/utils" → nil
パターン 29: "[/\\]\\.ccls-cache\\'"  vs ".../src/utils" → nil
パターン 30: "[/\\]\\.vs\\'"          vs ".../src/utils" → nil
パターン 31: "[/\\]\\.vscode\\'"      vs ".../src/utils" → nil
パターン 32: "[/\\]\\.venv\\'"        vs ".../src/utils" → nil
パターン 33: "[/\\]\\.mypy_cache\\'"  vs ".../src/utils" → nil
パターン 34: "[/\\]\\.pytest_cache\\'"vs ".../src/utils" → nil
パターン 35: "[/\\]\\.build\\'"       vs ".../src/utils" → nil
パターン 36: "[/\\]__pycache__\\'"    vs ".../src/utils" → nil
パターン 37: "[/\\]site-packages\\'"  vs ".../src/utils" → nil
パターン 38: "[/\\].pyenv\\'"         vs ".../src/utils" → nil
パターン 39: "[/\\]\\.deps\\'"        vs ".../src/utils" → nil
パターン 40: "[/\\]build-aux\\'"      vs ".../src/utils" → nil
パターン 41: "[/\\]autom4te.cache\\'" vs ".../src/utils" → nil
パターン 42: "[/\\]\\.reference\\'"   vs ".../src/utils" → nil
パターン 43: "[/\\]bazel-[^/\\]+\\'"  vs ".../src/utils" → nil
パターン 44: "[/\\]\\.cache[/\\]lsp-csharp\\'" → nil
パターン 45: "[/\\]\\.meta\\'"        vs ".../src/utils" → nil
パターン 46: "[/\\]\\.nuget\\'"       vs ".../src/utils" → nil
パターン 47: "[/\\]Library\\'"        vs ".../src/utils" → nil
パターン 48: "[/\\]\\.lsp\\'"         vs ".../src/utils" → nil
パターン 49: "[/\\]\\.clj-kondo\\'"   vs ".../src/utils" → nil
パターン 50: "[/\\]\\.shadow-cljs\\'" vs ".../src/utils" → nil
パターン 51: "[/\\]\\.babel_cache\\'" vs ".../src/utils" → nil
パターン 52: "[/\\]\\.cpcache\\'"     vs ".../src/utils" → nil
パターン 53: "[/\\]\\checkouts\\'"    vs ".../src/utils" → nil
パターン 54: "[/\\]\\.gradle\\'"      vs ".../src/utils" → nil
パターン 55: "[/\\]\\.m2\\'"          vs ".../src/utils" → nil
パターン 56: "[/\\]bin/Debug\\'"      vs ".../src/utils" → nil
パターン 57: "[/\\]obj\\'"            vs ".../src/utils" → nil
パターン 58: "[/\\]_opam\\'"          vs ".../src/utils" → nil
パターン 59: "[/\\]_build\\'"         vs ".../src/utils" → nil
パターン 60: "[/\\]\\.elixir_ls\\'"   vs ".../src/utils" → nil
... (残りのパターンも同様)
→ 結果: nil  ★ 全パターン走査完了、マッチなし

核心的な問題: プロジェクト内の 通常のディレクトリ (src, tests, utils, models など) は、60パターンのどれにもマッチしない。つまり、走査されるディレクトリの大多数が 最悪ケース (全60パターン試行) に該当する。

早期終了するのは、.git, node_modules, target など 実際に無視されるべきディレクトリ のみだが、これらはフィルタされるため走査対象に含まれない。結果として、走査対象のディレクトリ (D 個) すべてで60パターン全試行が発生する。

Emacs の正規表現キャッシュの限界

string-match は内部的に正規表現をコンパイルしてキャッシュする。しかし:

Emacs の正規表現キャッシュ (search_regs_saved):
  - キャッシュサイズ: REGEXP_CACHE_SIZE = 20 (compile_pattern in search.c)
  - 60パターンを繰り返し使用する場合、キャッシュ容量を超える
  - キャッシュミス時: 毎回正規表現のコンパイルが発生
  - 特に bazel-[^/\\]+ のような複雑なパターンはコンパイルコストが高い

LRU (Least Recently Used) の挙動:
  パターン1-20: キャッシュに入る
  パターン21: パターン1がキャッシュから追い出される
  パターン22: パターン2がキャッシュから追い出される
  ...
  次のディレクトリエントリで再びパターン1を使おうとする:
    → キャッシュミス! → 再コンパイル

  結果: 60パターン × D×E 回の呼び出しで、キャッシュヒット率は
  最大 20/60 = 33%。残り 67% は毎回再コンパイル。

ステップ4: メモリ割り当て分析

各ディレクトリの処理で発生するメモリ割り当てを詳細に分析する。

1ディレクトリあたりの割り当て (E=20 エントリの場合)

lsp--all-watchable-directories の1呼び出しあたり:

操作	cons セル	文字列	その他
`directory-files`	20	20	各エントリ: (cons "name" rest) + 文字列 "name"
`-filter` のクロージャ (バイトコンパイル時は再利用)	0-2	0	バイトコンパイル時は既存を再利用
`-filter` のクロージャ (インタープリタ時は毎回生成)	3-5	0
`f-join` x 20 (各エントリ分) — f-relative-p の結果	0	20	20文字列
`f-join` x 20 — 中間パス文字列	0	20	expand-file-name の結果
`f-join` x 20 — 最終結果文字列	0	20
`f-join` x 20 — インタープリタ時追加	20-40	0	クロージャ obj
`f-join` x 20 — マクロ展開中間リスト	60-100	0	macroexpand-all
`-filter` 結果リスト (各通過エントリに1 cons)	S	0	S=通過したエントリ数 (通常2-5)
`-map` のクロージャ	0-2	0
`f-join` x S (再帰引数の分)	—	S
`f-join` x S — インタープリタ時追加	3S-5S	0
`-map` 結果リスト	S	0	各サブツリー結果
`(list dir)` — nconc 用	1	0	新しい cons セル
`apply #'nconc`	0	0	破壊的操作
nconc の引数リスト (apply が作成)	S+1	0
`f-symlink?`	0	0	bool のみ
`f-symlink?` (インタープリタ時)	2-3	0	defalias 解決
`puthash`	0	0	hash-table 内部
`puthash` (rehash 時)	0	0	バケット再配置
合計 (バイトコンパイル時)	~45	~65
合計 (インタープリタ時)	~160	~65

メモリ使用量の推定サイズ

Emacs の Lisp オブジェクトサイズ (64-bit):

オブジェクト	サイズ (bytes)	備考
cons セル	16	car + cdr、各8バイト
短い文字列 (< 64文字)	64-128	ヘッダ + データ + パディング
長い文字列 (パス、~60文字)	96-128	典型的なフルパス
ハッシュテーブルエントリ	24	キー + 値 + ハッシュ
クロージャ (インタープリタ)	64-128	環境 + 引数 + ボディ

大規模プロジェクトでの総メモリ推定

パラメータ	値	計算
D (ディレクトリ数)	200,000	シンボリックリンク逸脱時
E (平均エントリ数)	20
S (平均サブディレクトリ数)	5

バイトコンパイル時:

cons セル: 200,000 × 45 × 16 bytes = 144 MB
文字列:   200,000 × 65 × 100 bytes = 1,300 MB
hash table (visited): 200,000 × 24 bytes = 4.8 MB
─────────────────────────────────────────────
合計: 約1.4 GB のメモリ割り当て (GC 前のピーク)

インタープリタ時:

cons セル: 200,000 × 160 × 16 bytes = 512 MB
文字列:   200,000 × 65 × 100 bytes = 1,300 MB
hash table: 4.8 MB
クロージャ: 200,000 × 5 × 96 bytes = 96 MB
─────────────────────────────────────────────
合計: 約1.9 GB のメモリ割り当て (GC 前のピーク)

注意: これらは 総割り当て量 であり、同時にライブなのはその一部。しかし GC の実行頻度が上がり、GC 自体が追加の停止時間を引き起こす。gc-cons-threshold がデフォルト (800KB) の場合、GC は数千回発生する。lsp-mode の推奨設定 (setq gc-cons-threshold 100000000) (100MB) でも、約14-19回の GC が発生する。

`visited` ハッシュテーブルの動的成長

初期状態:     バケット数 = 65  (make-hash-table のデフォルト)
閾値 (0.8):   52 エントリで rehash
rehash:       バケット数を約2倍に拡張

成長パターン (D=200,000 の場合):
  65 → 131 → 263 → 527 → 1055 → 2111 → 4223 →
  8447 → 16895 → 33791 → 67583 → 135167 → 270335

rehash 回数: 約13回
各 rehash: 全エントリの再配置 → O(現在のエントリ数)
rehash の総コスト: 65 + 131 + ... + 135167 ≈ 270,000 操作
  → 大きいが、他のコストと比較すると無視できる程度

ステップ5: 再帰的走査 — `lsp--all-watchable-directories` (L2097)

(defun lsp--all-watchable-directories (dir ignored-directories &optional visited)
  (let* ((dir (if (f-symlink? dir)
                  (file-truename dir)           ;; ← シンボリックリンク解決
                dir))
         (visited (or visited (make-hash-table :test 'equal))))
    (if (gethash dir visited) nil               ;; ← サイクルチェック O(1)
      (puthash dir t visited)
      (apply #'nconc
             (list dir)
             (-map
              (lambda (path)
                (lsp--all-watchable-directories  ;; ← 再帰呼び出し
                 (f-join dir path) ignored-directories visited))
              (-filter
               (lambda (path)
                 (lsp--path-is-watchable-directory path dir ignored-directories))
               (directory-files dir)))))))

操作	ディレクトリごと	合計
`f-symlink?`	O(1)	O(D)
`file-truename` (シンボリックリンクの場合)	O(L)	O(S_link × L)
`gethash` (サイクルチェック)	O(1) 償却	O(D)
`puthash`	O(1) 償却 (rehash 除く)	O(D)
`directory-files`	O(E)	O(D × E)
`-filter` + `lsp--path-is-watchable-directory`	O(E × R)	O(D × E × R)
`-map` + 再帰呼び出し	O(S_sub)	O(D)
`nconc` (リスト連結)	O(1) 償却	O(D)
`(list dir)`	O(1)	O(D) cons セル割り当て
スタック深度	—	最大ツリー深度

総走査計算量: O(D × E × R)

S_link = シンボリックリンクであるディレクトリの数、S_sub = サブディレクトリ数

ルート境界チェックの欠如 — 根本的設計問題

この走査は プロジェクトルートからの距離を一切考慮しない。visited ハッシュテーブルは サイクル (同じディレクトリを2度訪問すること) を防ぐが、逸脱 (プロジェクト外のディレクトリへの到達) は防がない。

flowchart TD
    subgraph expected ["期待される動作: プロジェクトルートの下位ディレクトリのみ走査"]
        direction TB
        E_ROOT["/home/user/myproject/"]
        E_SRC["src/"]
        E_VENDOR["vendor/"]
        E_ROOT --> E_SRC
        E_ROOT --> E_VENDOR
    end

    subgraph actual ["実際の動作: シンボリックリンクを辿ってファイルシステム上の任意の場所へ到達可能"]
        direction TB
        ROOT["/home/user/myproject/"]
        SRC["src/ — 正常: プロジェクト内"]
        VENDOR["vendor -> /usr/<br/>f-symlink? → t<br/>file-truename → '/usr/'"]:::symlink

        ROOT --> SRC
        ROOT --> VENDOR

        subgraph escape ["シンボリックリンク逸脱先: /usr/"]
            direction TB
            BIN["/usr/bin/ を走査開始"]:::danger
            LIB["/usr/lib/ を走査開始<br/>数万ディレクトリ"]:::danger
            SHARE["/usr/share/ を走査開始"]:::danger
            LOCAL["/usr/local/"]:::danger
            LBIN["/usr/local/bin/"]:::danger
            LLIB["/usr/local/lib/"]:::danger
            LDOT["..."]:::danger
            LOCAL --> LBIN
            LOCAL --> LLIB
            LOCAL --> LDOT
        end

        VENDOR --> BIN
        VENDOR --> LIB
        VENDOR --> SHARE
        VENDOR --> LOCAL
    end

    MISSING["必要なルート境界チェック (存在しない):<br/>string-prefix-p root-directory<br/> file-truename dir<br/>→ truename'd パスがルートのプレフィックスを<br/>共有しなければ、走査を打ち切る"]:::missing

    actual --> MISSING

    classDef symlink fill:#ff9,stroke:#f90,stroke-width:3px,color:#000
    classDef danger fill:#f66,stroke:#c00,stroke-width:2px,color:#fff
    classDef missing fill:#ccf,stroke:#66f,stroke-width:2px,stroke-dasharray:5 5,color:#000

スタック深度リスク

D=200,000 で平均分岐係数 b=10 の場合:
  最大深度 = log_b(D) = log_10(200,000) ≈ 5.3

しかし、ファイルシステムの構造は均一ではない。
/nix/store/ のような構造では:
  /nix/store/abc123-pkg/lib/python3.10/site-packages/numpy/core/tests/
  → 深度 = 8+

issue #4287 からの報告:
  Steam/Nix ストアのシンボリックリンクから:
  (excessive-lisp-nesting 1702)
  → max-lisp-eval-depth (デフォルト 1600) を超過してクラッシュ

各再帰呼び出しのスタック消費:
  - let* バインディング: 2 スロット (dir, visited)
  - apply, nconc, -map, -filter の引数: 数スロット
  - 各レベルで約 10-15 スタックスロット消費
  → 深度 100 で 1,000-1,500 スロット
  → 深度 160 で max-lisp-eval-depth に到達する可能性

ステップ6: Emacs イベントループのブロッキング

Emacs のスレッドモデル

Emacs は 協調的シングルスレッド モデルで動作する。すべての Lisp コードは単一のスレッド (メインスレッド) で実行され、OS スレッド (make-thread で作成可能) は存在するが、GIL (Global Interpreter Lock) により同時に1つしか Lisp を実行できない。

flowchart TD
    LOOP["command_loop_1()<br/>Emacs イベントループ<br/>(keyboard.c)"]

    READ["read_key_sequence()<br/>キー入力を待つ"]
    SIT["sit_for() / select(2)"]

    EXEC["command_execute()<br/>コマンドを実行"]
    FUNCALL["Ffuncall()<br/>Lisp 関数実行"]

    subgraph blocking ["ブロッキング区間"]
        direction TB
        LSPREG["lsp--server-register-capability"]:::blocked
        ALLWATCH["lsp--all-watchable-directories<br/>200,000 回の再帰..."]:::blocked
        NORETURN["完了するまで制御は戻らない"]:::blocked
        LSPREG --> ALLWATCH --> NORETURN
    end

    REDISPLAY["redisplay() — 画面を更新"]:::unreachable
    PROCOUT["process_output() — サブプロセス出力処理"]:::unreachable
    TIMER["timer_check() — タイマー実行"]:::unreachable

    LOOP --> READ --> SIT
    LOOP --> EXEC --> FUNCALL --> LSPREG
    LOOP --> REDISPLAY
    LOOP --> PROCOUT
    LOOP --> TIMER
    TIMER -.->|ループ| LOOP

    classDef blocked fill:#f66,stroke:#c00,stroke-width:3px,color:#fff
    classDef unreachable fill:#ccc,stroke:#999,stroke-width:2px,stroke-dasharray:5 5,color:#666

ブロッキングの影響

lsp--all-watchable-directories の実行中:

ユーザー操作	結果
キー入力 (文字の入力)	バッファに蓄積されるが、画面に反映されない
C-g (keyboard-quit)	処理されない可能性が高い
マウスクリック	キューに入るが処理されない
他の LSP サーバーからの応答	プロセスフィルタが実行されず、補完等が停止
タイマー (`run-at-time` 等)	実行されない
`redisplay`	実行されない → 画面がフリーズ
フレーム管理 (ウィンドウのリサイズ)	反映されない

C-g が効かない理由

通常の C-g の処理フロー:
  1. ユーザーが C-g を押す
  2. シグナルハンドラ (SIGINT) が quit-flag をセットする
  3. Lisp 評価器がチェックポイントで quit-flag を確認する
  4. quit-flag が t なら、(signal 'quit nil) を投げる

チェックポイントの位置:
  - Feval() の入口 (各フォームの評価前)
  - Ffuncall() の入口 (各関数呼び出し前)
  - maybe_quit() 呼び出し

問題:
  lsp--all-watchable-directories 内では quit-flag のチェックは行われるが、
  以下の条件で C-g が効かないことがある:

  1. condition-case がエラーを捕捉する場合:
     lsp--string-match-any の condition-case が invalid-regexp を捕捉するが、
     quit シグナルは捕捉しない (condition-case は quit を捕捉しない)。
     → C-g 自体は理論上効くはず。

  2. しかし実際には:
     - 各 string-match は C レベルで実行される
     - C 関数実行中は quit-flag チェックが限定的
     - 大量の短い C 関数呼び出し (string-match × 1億回) の間、
       quit-flag が確認されるのは Lisp 評価器に戻るタイミングのみ
     - string-match 1回は ~1μs なので、チェック間隔は短い
     → 理論上は C-g は効くが、ユーザーの体感では
       「数秒間フリーズして C-g が効かないように見える」状態になる

  3. directory-files や file-accessible-directory-p のような
     ブロッキング I/O 中は、C-g は I/O 完了まで処理されない。
     NFS/ネットワークファイルシステムの場合、これが数秒になることがある。

`sit-for` / `accept-process-output` の欠如

lsp--all-watchable-directories のコードには、制御をイベントループに返す関数呼び出しが一切存在しない:

;; イベントループに制御を返す関数の例:
(sit-for 0)                    ;; pending input を処理し、redisplay を実行
(accept-process-output nil 0)  ;; pending なプロセス出力を処理
(redisplay)                    ;; 画面を強制更新
(read-event nil nil 0)         ;; pending なイベントを1つ読む

;; lsp--all-watchable-directories にはこれらが一切ない
;; → D × E 回のループがすべて完了するまで、Emacs は完全にフリーズ

理論的な修正案 (参考):

;; 例えば 1000 ディレクトリごとに制御を返す場合:
(when (zerop (mod counter 1000))
  (sit-for 0))  ;; イベントループに制御を返す

ステップ7: OS レベルのファイルウォッチャー詳細

file-notify-add-watch は Emacs の filenotify.el を通じて、OS 固有のファイル監視メカニズムに委譲する。

Linux: inotify

Emacs 側:
  (file-notify-add-watch dir '(change) callback)
    → inotify.c: Finotify_add_watch()
      → inotify_add_watch(fd, dir, IN_CREATE | IN_DELETE | IN_MODIFY | IN_MOVE)

カーネル側:
  inotify_add_watch(2):
    - 1つの inotify file descriptor (fd) に対して複数の watch を追加
    - 各 watch はカーネルメモリを消費

リソース制限:
  /proc/sys/fs/inotify/max_user_watches = 8192 (デフォルト)
    → Ubuntu/Fedora の最近のバージョンでは 65536 や 524288 に増やされている場合もある
    → しかし D=200,000 では 8192 を大幅に超過

  各ウォッチのカーネルメモリコスト:
    struct inotify_inode_mark ≈ 936 bytes (Linux 6.x)
    + dentry cache への参照
    → 約 1KB/watch

  D=200,000 の場合:
    カーネルメモリ: 200,000 × 1KB = ~200 MB のカーネルメモリ消費
    → OOM killer のリスク、他のアプリケーションへの影響

  /proc/sys/fs/inotify/max_user_instances = 128 (デフォルト)
    → 1プロセスあたりの inotify fd 数
    → Emacs は通常1つの fd を使うので問題にならない

エラー処理:
  max_user_watches を超えた場合:
    inotify_add_watch() → ENOSPC
    → Emacs: (file-notify-error "No space left on device")
    → lsp-mode: (condition-case err ... (error (lsp-log ...)))
    → エラーはログに記録されるだけで、残りのディレクトリは監視されない

macOS: FSEvents (デフォルト) / kqueue (フォールバック)

macOS での file-notify バックエンド選択:
  Emacs 25+: FSEvents (推奨)
  Emacs 24-: kqueue (フォールバック)

FSEvents (File System Events):
  (file-notify-add-watch dir '(change) callback)
    → fs_event_monitor.c (またはfilenotify-fsevent)
      → FSEventStreamCreate() + FSEventStreamScheduleWithRunLoop()

  特徴:
    - ディレクトリベース: 1つの stream で再帰的にサブディレクトリを監視可能
    - しかし Emacs の実装では各ディレクトリに個別の stream を作成
    - 各 stream はカーネルとの通信チャネルを保持
    - inotify ほどリソース効率は悪くないが、大量のストリームは問題
    - レイテンシ: デフォルトで約 0.5 秒の遅延 (バッチ処理のため)
    - カーネルメモリ: inotify より効率的 (ディレクトリツリー全体を1つの stream で管理)

kqueue:
  - inotify に似た per-directory モデル
  - 各ディレクトリに対して open(2) でファイルディスクリプタを取得
  - struct kevent で監視対象を登録
  - リソース制限: kern.maxfiles (デフォルト 12288)
  - D=200,000 は fd 枯渇を引き起こす

Windows: ReadDirectoryChangesW

(file-notify-add-watch dir '(change) callback)
  → w32notify.c: Fw32notify_add_watch()
    → CreateFileW() + ReadDirectoryChangesW()

特徴:
  - per-directory モデル
  - 各ディレクトリに対して HANDLE を取得
  - FILE_NOTIFY_CHANGE_FILE_NAME | FILE_NOTIFY_CHANGE_DIR_NAME |
    FILE_NOTIFY_CHANGE_SIZE | FILE_NOTIFY_CHANGE_LAST_WRITE
  - 非同期 I/O (OVERLAPPED) 使用
  - 各 HANDLE はカーネルオブジェクトを消費
  - D=200,000 では HANDLE 枯渇のリスク (プロセスあたり上限 ~16M)

プラットフォーム比較表

指標	Linux (inotify)	macOS (FSEvents)	Windows (RDCW)
粒度	per-directory	per-directory (実装上)	per-directory
デフォルト上限	8,192 watches	fd 制限 (12,288)	~16M handles
watch あたりメモリ	~1 KB	可変 (効率的)	~1 KB
イベント遅延	リアルタイム	~0.5 秒	リアルタイム
D=200K の影響	ENOSPC エラー	大量 fd 消費	ハンドル枯渇リスク
D=200K のメモリ	~200 MB (カーネル)	~50 MB	~200 MB
再帰的監視サポート	なし (per-dir のみ)	あり (未使用)	あり (未使用)

重大な無駄: macOS の FSEvents は本来、1つの stream でディレクトリツリー全体を再帰的に監視できる。しかし Emacs の file-notify-add-watch インターフェースが per-directory 設計であるため、この効率的な機能は利用されない。lsp-mode は D 個の個別 watch を作成する。

ステップ8: `root-directory` ミスマッチバグの詳細

バグの発生メカニズム

lsp--server-register-capability (L3964-3984) には、lsp-watch 構造体の root-directory フィールドと実際の走査パスの間に不一致がある。

;; L3974: watch 構造体を作成 — 生パスを格納
(let* ((watch (make-lsp-watch :root-directory folder))
       ;;                                    ^^^^^^
       ;; folder = "/home/user/myproject" (file-truename されていない)

;; L3979: 走査を開始 — truename'd パスで走査
       (lsp-watch-root-folder (file-truename folder) ...
       ;;                     ^^^^^^^^^^^^^^^^^^^^^^^^
       ;; (file-truename "/home/user/myproject") → "/data/repos/myproject"
       ;; (シンボリックリンクの場合)

具体的なシナリオ

sequenceDiagram
    participant FS as ファイルシステム<br/>/home/user/myproject<br/>→ symlink →<br/>/data/repos/myproject
    participant REG as lsp--server-register-capability<br/>folder = "/home/user/myproject"
    participant WATCH as watch 構造体
    participant SCAN as lsp--all-watchable-directories
    participant NOTIFY as file-notify-add-watch
    participant OS as OS イベント
    participant CB as lsp--file-process-event

    Note over REG: Step 1: make-lsp-watch
    REG->>WATCH: root-directory = "/home/user/myproject"<br/>生パス

    Note over REG: Step 2: puthash
    REG->>WATCH: created-watches["/home/user/myproject"] = watch<br/>生パスがキー

    Note over REG: Step 3: lsp-watch-root-folder
    REG->>SCAN: dir = file-truename "/home/user/myproject"<br/>= "/data/repos/myproject"<br/>truename に解決

    Note over SCAN: Step 4: 走査結果
    SCAN-->>NOTIFY: dirs-to-watch =<br/>"/data/repos/myproject"<br/>"/data/repos/myproject/src"<br/>"/data/repos/myproject/tests"<br/>すべて /data/repos/ プレフィックス

    Note over NOTIFY: Step 5: ウォッチャー登録
    NOTIFY-->>WATCH: descriptors["/data/repos/myproject"] = desc-1<br/>descriptors["/data/repos/myproject/src"] = desc-2<br/>キーも /data/repos/ プレフィックス

    Note over OS: Step 6: ランタイムイベント
    OS->>CB: file-name = "/data/repos/myproject/src/main.rs"

    Note over CB: callback の folder = "/home/user/myproject" 生パス!
    CB->>CB: f-relative<br/>"/data/repos/.../main.rs" vs "/home/user/myproject"<br/>→ "../../../../data/repos/myproject/src/main.rs"<br/>正しい相対パスにならない!<br/>glob マッチが失敗する可能性

    Note over CB: gethash "/home/user/myproject"<br/>→ 動作するが folder->servers が<br/>truename で登録されていれば nil

影響の範囲

flowchart TD
    ROOT["生パス vs truename のミスマッチ"]

    subgraph cases ["影響を受けるケース"]
        C1["1. プロジェクトルート自体が<br/>シンボリックリンク"]
        C2["2. macOS /Users → /private/Users<br/>firmlinks による自動シンボリックリンク<br/>全 macOS ユーザーで潜在的に発生"]
        C3["3. Nix/Guix 環境での<br/>シンボリックリンク"]
        C4["4. Docker ボリュームマウント<br/>+ シンボリックリンク"]
    end

    ROOT --> C1
    ROOT --> C2
    ROOT --> C3
    ROOT --> C4

    FREL["f-relative の計算が不正確"]:::bug
    C1 --> FREL
    C2 --> FREL
    C3 --> FREL
    C4 --> FREL

    GLOB["glob パターンマッチの失敗"]:::bug
    FREL --> GLOB

    NO_NOTIFY["ファイル変更通知が<br/>LSP サーバーに届かない"]:::bug
    GLOB --> NO_NOTIFY

    STALE["LSP サーバーが<br/>古いバッファ内容で動作し続ける"]:::bug
    NO_NOTIFY --> STALE

    STALE --> F1["補完候補の欠落"]:::impact
    STALE --> F2["診断の遅延"]:::impact
    STALE --> F3["go-to-definition の失敗"]:::impact

    classDef bug fill:#f8d7da,stroke:#dc3545,color:#721c24
    classDef impact fill:#dc3545,stroke:#721c24,color:#fff,font-weight:bold

ステップ9: `directory-files-recursively` によるランタイム脆弱性 (L2053)

コードの問題箇所

;; lsp--folder-watch-callback (L2041-2065) 内:
((and (file-directory-p file-name)
      (equal 'created event-type)
      (not (lsp--string-match-any ignored-directories file-name)))

 ;; 新ディレクトリのウォッチャーを追加
 (lsp-watch-root-folder (file-truename file-name) callback
                        ignored-files ignored-directories watch)

 ;; ★ 問題の箇所: 新ディレクトリ内の既存ファイルを通知
 (->> (directory-files-recursively file-name ".*" t)  ;; t = INCLUDE-DIRECTORIES
      (seq-do (lambda (f)
                (unless (file-directory-p f)
                  (funcall callback (list nil 'created f)))))))

`directory-files-recursively` の動作 (Emacs 28+ / files.el)

;; files.el の実装 (概念的):
(defun directory-files-recursively (dir regexp &optional include-directories
                                       predicate follow-symlinks)
  (let ((files nil)
        (dirs nil))
    (dolist (file (directory-files dir t))
      (cond
       ((file-directory-p file)
        (when (and (not (member (file-name-nondirectory file) '("." "..")))
                   (or follow-symlinks (not (file-symlink-p file)))  ;; ★
                   (or (null predicate) (funcall predicate file)))
          (setq dirs (nconc dirs (directory-files-recursively
                                  file regexp include-directories
                                  predicate follow-symlinks)))))
       ((string-match-p regexp file)
        (push file files)))
    (if include-directories
        (nconc dirs files)
      files)))

問題点の詳細

lsp-mode (L2053) での呼び出し:

(directory-files-recursively file-name ".*" t)
;;                                      ^^^ ^^
;;                           REGEXP=".*" (全ファイルマッチ)
;;                                INCLUDE-DIRECTORIES=t
;;
;; 重要: follow-symlinks 引数が渡されていない
;; Emacs 28+: follow-symlinks のデフォルトは nil
;; しかし: INCLUDE-DIRECTORIES=t を指定すると、
;;   ディレクトリのシンボリックリンクは file-directory-p で
;;   true を返すため、結果的にシンボリックリンクを辿る

初期走査 (lsp--all-watchable-directories) との比較:

安全機構	初期走査	ランタイムコールバック
`visited` ハッシュテーブル (サイクル防止)	あり	なし
`ignored-directories` チェック	あり (全サブディレクトリ)	トップレベルのみ
ルート境界チェック	なし (両方に問題)	なし
シンボリックリンクの `file-truename`	あり	なし (directory-files-recursively 内)

攻撃シナリオ (ランタイム)

sequenceDiagram
    participant USER as ユーザー/プロセス
    participant FS as ファイルシステム<br/>/home/user/project/<br/>監視中
    participant OS as OS<br/>inotify/FSEvents
    participant CB as lsp--folder-watch-callback
    participant WRF as lsp-watch-root-folder
    participant DFR as directory-files-recursively

    Note over USER,FS: Step 1: シンボリックリンク作成
    USER->>FS: mkdir vendor<br/>ln -s / vendor/root

    Note over OS: Step 2: イベント発火
    OS->>CB: event = created<br/>"/home/user/project/vendor"

    Note over CB: Step 3: コールバック処理
    CB->>CB: file-directory-p → t
    CB->>CB: string-match-any ignored-dirs → nil<br/>"vendor" は 60パターンのいずれにもマッチしない

    Note over WRF: Step 4: ウォッチャー追加
    CB->>WRF: file-truename → "/home/user/project/vendor"
    WRF->>WRF: vendor/ 配下にウォッチャーを再帰追加
    WRF->>WRF: vendor/root/ → "/" への到達<br/>初期走査と同じシンボリックリンク逸脱問題

    Note over DFR: Step 5: 同時に走査開始
    CB->>DFR: directory-files-recursively<br/>"vendor" ".*" t

    DFR->>DFR: vendor/root/bin/...<br/>vendor/root/usr/...<br/>ファイルシステム全体の走査を開始

    Note over DFR: visited テーブルなし<br/>→ サイクルがあれば無限ループ
    Note over DFR: ignored-directories チェックなし<br/>→ .git 等も走査
    Note over DFR: 結果リストが数百万エントリ<br/>→ メモリ枯渇

要約: 時間が費やされる場所

シンボリックリンク逸脱時 (D=200,000, E=20)

ステップ	操作	呼び出し回数	呼び出しごとのコスト	合計時間	全体の%
4a	`f-join` (インタープリタ)	2,000,000	50μs	100s	52%
4c	`lsp--string-match-any`	2,000,000	30μs (60回 × 0.5μs)	60s	31%
4b	`file-accessible-directory-p`	2,000,000	10μs	20s	10%
3	`directory-files`	200,000	30μs	6s	3%
5	`file-truename` (シンボリックリンク)	200,000	15μs	3s	2%
6	`file-notify-add-watch`	200,000	10μs	2s	1%
GC	ガベージコレクション	14-19回	50-200ms	1-4s	1%
				約191-195s	約100%

バイトコンパイル済み環境 (D=200,000, E=20)

ステップ	操作	合計時間	全体の%
4c	`lsp--string-match-any`	60s	66%
4b	`file-accessible-directory-p`	20s	22%
3	`directory-files`	6s	7%
5	`file-truename`	3s	3%
6	`file-notify-add-watch`	2s	2%
GC	ガベージコレクション	0.5-1s	< 1%
		約91-92s	100%

正常なプロジェクト (D=500, E=20, シンボリックリンク逸脱なし)

ステップ	操作	呼び出し回数	合計時間 (インタープリタ)	合計時間 (バイトコンパイル)
4a	`f-join`	10,000	0.5s	0.02s
4c	`lsp--string-match-any`	10,000	0.3s	0.3s
4b	`file-accessible-directory-p`	10,000	0.1s	0.1s
3	`directory-files`	500	0.015s	0.015s
6	`file-notify-add-watch`	500	0.005s	0.005s
			約0.92s	約0.44s

正常なプロジェクトでは 1秒未満 で完了し、ユーザーは気づかない。問題はシンボリックリンク逸脱時にのみ顕在化する。

VSCode との比較

VSCode は同じ workspace/didChangeWatchedFiles プロトコルを使用するが、ファイルウォッチャーの実装が根本的に異なる。

VSCode のアプローチ

flowchart TD
    LSPSERV["LSP Server が<br/>workspace/didChangeWatchedFiles を登録<br/>watchers: globPattern '**/*.rs', kind: 7"]
    GLOB["GlobPattern を解析<br/>'**/*.rs' → 拡張子 '.rs' のファイルのみ監視"]

    LSPSERV --> GLOB

    subgraph prefix ["glob プレフィックスの抽出"]
        P1["'**/*.rs' → プレフィックスなし<br/>ルート全体"]
        P2["'src/**/*.rs' → プレフィックス = 'src/'"]
        P3["'{src,tests}/**' → プレフィックス =<br/>'src/', 'tests/'"]
    end

    GLOB --> prefix

    subgraph native_watch ["ネイティブ OS 再帰監視"]
        CHOKIDAR["chokidar (Node.js) /<br/>parcel-watcher (ネイティブ)<br/>再帰的なディレクトリ監視を<br/>OS レベルで効率的に実行"]
        LINUX["Linux: inotify<br/>再帰的に追加"]
        MAC["macOS: FSEvents<br/>再帰モードを使用"]:::highlight
        WIN["Windows: ReadDirectoryChangesW<br/>再帰モードを使用"]:::highlight
        CHOKIDAR --> LINUX
        CHOKIDAR --> MAC
        CHOKIDAR --> WIN
    end

    prefix --> CHOKIDAR

    FILTER["イベントフィルタリング<br/>glob パターンに基づいてフィルタ<br/>マッチしないイベントは即座に破棄"]
    NOTIFY["LSP サーバーには<br/>必要なイベントのみ通知"]

    native_watch --> FILTER --> NOTIFY

    classDef highlight fill:#9f9,stroke:#090,stroke-width:2px,color:#000

主要な設計差異

設計判断	lsp-mode (Emacs)	VSCode
glob パターンの使用タイミング	イベント受信後にフィルタ	ウォッチャー設定前にスコープ絞り込み
ディレクトリ走査	Lisp で独自に再帰走査	OS のネイティブ再帰監視を活用
無視パターンの数	60個の正規表現 (ハードコード)	`.gitignore` を動的に読み取り
シンボリックリンク処理	無制限に追跡	最大深度制限あり
非同期処理	同期 (UIブロック)	非同期 (別プロセス/ワーカー)
macOS FSEvents 活用	per-directory (非効率)	再帰的 stream (効率的)

具体的な違い: `**/*.rs` パターンの場合

flowchart LR
    subgraph lspmode ["lsp-mode"]
        direction TB
        L1["1. ルートから全ディレクトリを走査<br/>D ディレクトリ"]
        L2["2. 各ディレクトリで<br/>60 正規表現をマッチ"]
        L3["3. 監視可能な全ディレクトリ<br/>D' &le; D にウォッチャーを作成"]
        L4["4. ファイル変更イベント<br/>→ glob マッチ<br/>→ '*.rs' のみ通知"]
        LCOST["作業量: O(D x E x R)<br/>+ D' 個のウォッチャー"]:::cost_bad
        LNOTE["全ファイルの変更イベントを<br/>受信してから破棄"]:::warning

        L1 --> L2 --> L3 --> L4
        L4 --> LCOST
        LCOST --> LNOTE
    end

    subgraph vscode ["VSCode"]
        direction TB
        V1["1. ルートに対して<br/>1 つの再帰的ウォッチャーを作成"]
        V2["2. イベント受信時に<br/>glob パターンでフィルタ"]
        V3["3. マッチしたイベントのみ<br/>LSP サーバーに通知"]
        VCOST["作業量: O(1) のウォッチャー設定<br/>+ イベントごとの O(G) フィルタ"]:::cost_good
        VNOTE["OS レベルの効率的な<br/>再帰監視を活用"]:::good

        V1 --> V2 --> V3
        V3 --> VCOST
        VCOST --> VNOTE
    end

    classDef cost_bad fill:#fcc,stroke:#c00,stroke-width:2px,color:#000
    classDef warning fill:#f96,stroke:#f60,stroke-width:2px,color:#000
    classDef cost_good fill:#cfc,stroke:#0c0,stroke-width:2px,color:#000
    classDef good fill:#9f9,stroke:#090,stroke-width:2px,color:#000

計算量テーブル

シンボル	意味	通常	最悪ケース
D	走査された総ディレクトリ数	100-500	200,000+
E	ディレクトリごとのエントリ数	10-50	1,000+
R	フィルタリング用正規表現パターン数	約60	約60
G	サーバーからの glob パターン数	2-5	20+
L	シンボリックリンク解決ホップ数	1-3	10+
S_link	シンボリックリンクであるディレクトリ数	0-5	D の任意の割合
E'	`file-accessible-directory-p` を通過したエントリ数	2-10	100+

フェーズ	計算量	支配的な要因
ディレクトリ走査	O(D × E)	D (シンボリックリンクにより無制限)
パス構築 (`f-join`)	O(D × E)	マクロ展開定数 (インタープリタ実行時のみ)
正規表現フィルタリング	O(D × E × R)	D × R (60パターン × 無制限ディレクトリ)
ウォッチャー作成	O(D)	カーネルリソース消費
イベントフィルタリング (実行時)	イベントごとに O(G)	効率的 — キャッシュ済み
メモリ割り当て	O(D × E)	GC プレッシャー
全体	O(D × E × R)	D が無制限

各修正が役立つ理由

修正	何を制限するか	修正後の計算量
FR-001: ルート境界	D (プロジェクトディレクトリのみに制限)	O(D_p × E × R), D_p << D
FR-003: `f-join` → `expand-file-name`	ステップ4a の定数係数	同じ O、呼び出しごとに約100倍高速
FR-004: Glob プレフィックス抽出	D (ルートをプレフィックスサブディレクトリに絞り込む)	まれに適用可能 (`*/.ext` にはプレフィックスなし)
FR-005: `.gitignore` フィルタ	D (ポストフィルタで無視ディレクトリを削減)	O(D × E × R + D_git), D_git = git サブプロセス
FR-006: 正規表現の事前結合	R を 1 に削減	O(D × E × 1) = O(D × E)
FR-007: 非同期走査	UI ブロッキング時間	計算量は同じだが UI が応答可能
FR-008: 深度制限	最大再帰深度	スタックオーバーフロー防止

最も影響力のある修正は FR-001 (ルート境界チェック) である。D を 200,000+ から実際のプロジェクトサイズ (約100-500) に制限し、根本原因を排除する。FR-003 (f-join の置換) は定数係数の改善だが、D が制限されていなければ焼け石に水である。両方を組み合わせることで、シンボリックリンク逸脱を防ぎつつ、正常プロジェクトでの速度も向上する。

takeokunn/lsp-mode-performance.md