VSCode のソースコードを読んでファイル検索の仕組みを調べてみた

はじめに

VSCode などのエディタにはファイルの検索機能があり、かなり直感的な順序でファイルを提示してくれることが多いです。
どういったアルゴリズムで順序を決めているのかが気になったので、調査をしてみます。

使用されているコードの調査

せっかくなので、調査した際にどのようにコードを追っていったかも書いていきます。
アルゴリズムのみを知りたい場合は、ファイルのソート方法まで飛んでください。

まずは GitHub で公開されているコードから探っていきます。
手元で探しやすくなるように、最新のコミットを Clone します。

git clone --depth 1 [e-mail]:microsoft/vscode.git

ノーヒントで膨大なコードの中から探るのは難しいので、VSCode のショートカット設定をまず見てみます。

workbench.action.quickOpen とあるので、これをもとに探っていきます。

git grep 'workbench.action.quickOpen'

結果 (長いので折り畳んでいます)

extensions/emmet/src/emmetCommon.ts:            vscode.commands.executeCommand('workbench.action.quickOpen', '>Emmet: ');
extensions/github/src/test/github.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/github/src/test/github.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/github/src/test/github.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/quickInput.test.ts:                  await
commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/quickInput.test.ts:                  await
commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/quickInput.test.ts:                  await
commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/window.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/window.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
extensions/vscode-api-tests/src/singlefolder-tests/window.test.ts:              await commands.executeCommand('workbench.action.quickOpenSelectNext');
src/vs/workbench/browser/actions/quickAccessActions.ts:const quickAccessNavigateNextInFilePickerId = 'workbench.action.quickOpenNavigateNextInFilePicker';
src/vs/workbench/browser/actions/quickAccessActions.ts:const quickAccessNavigatePreviousInFilePickerId = 'workbench.action.quickOpenNavigatePreviousInFilePicker';
src/vs/workbench/browser/actions/quickAccessActions.ts:                 id: 'workbench.action.quickOpen',
src/vs/workbench/browser/actions/quickAccessActions.ts:                 id: 'workbench.action.quickOpenWithModes',
src/vs/workbench/browser/actions/quickAccessActions.ts:CommandsRegistry.registerCommand('workbench.action.quickOpenPreviousEditor', async accessor => {
src/vs/workbench/browser/actions/quickAccessActions.ts:         super('workbench.action.quickOpenNavigateNext', localize2('quickNavigateNext', 'Navigate Next in Quick Open'), true, true);
src/vs/workbench/browser/actions/quickAccessActions.ts:         super('workbench.action.quickOpenNavigatePrevious', localize2('quickNavigatePrevious', 'Navigate Previous in Quick Open'), false, true);
src/vs/workbench/browser/actions/quickAccessActions.ts:                 'workbench.action.quickOpenSelectNext',
src/vs/workbench/browser/actions/quickAccessActions.ts:                 'workbench.action.quickOpenSelectPrevious',
src/vs/workbench/browser/actions/windowActions.ts:                      id: 'workbench.action.quickOpenRecent',
src/vs/workbench/browser/actions/windowActions.ts:const quickPickNavigateNextInRecentFilesPickerId = 'workbench.action.quickOpenNavigateNextInRecentFilesPicker';
src/vs/workbench/browser/actions/windowActions.ts:const quickPickNavigatePreviousInRecentFilesPicker = 'workbench.action.quickOpenNavigatePreviousInRecentFilesPicker';
src/vs/workbench/browser/parts/editor/editor.contribution.ts:const quickAccessNavigateNextInEditorPickerId = 'workbench.action.quickOpenNavigateNextInEditorPicker';
src/vs/workbench/browser/parts/editor/editor.contribution.ts:const quickAccessNavigatePreviousInEditorPickerId = 'workbench.action.quickOpenNavigatePreviousInEditorPicker';
src/vs/workbench/browser/parts/editor/editorActions.ts:                 id: 'workbench.action.quickOpenPreviousRecentlyUsedEditor',
src/vs/workbench/browser/parts/editor/editorActions.ts:                 id: 'workbench.action.quickOpenLeastRecentlyUsedEditor',
src/vs/workbench/browser/parts/editor/editorActions.ts:                 id: 'workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup',
src/vs/workbench/browser/parts/editor/editorActions.ts:                 id: 'workbench.action.quickOpenLeastRecentlyUsedEditorInGroup',
src/vs/workbench/browser/parts/editor/editorGroupWatermark.ts:const gotoFile: WatermarkEntry = { text: localize('watermark.quickAccess', "Go to File"), id: 'workbench.action.quickOpen' };
src/vs/workbench/browser/parts/titlebar/commandCenterControl.ts:        private static readonly _quickOpenCommandId = 'workbench.action.quickOpenWithModes';
src/vs/workbench/browser/parts/titlebar/commandCenterControl.ts:                super(undefined, _submenu.actions.find(action => action.id === 'workbench.action.quickOpenWithModes') ?? _submenu.actions[0], options);
src/vs/workbench/contrib/files/browser/fileActions.contribution.ts:     MenuRegistry.appendMenuItem(menuId, { command: { id: 'workbench.action.quickOpen', title: nls.localize('openFile', "Open File...") }, group: '1_file', order: 20 });
src/vs/workbench/contrib/files/browser/fileActions.contribution.ts:             id: 'workbench.action.quickOpen',
src/vs/workbench/contrib/quickaccess/browser/quickAccess.contribution.ts:const quickAccessNavigateNextInViewPickerId = 'workbench.action.quickOpenNavigateNextInViewPicker';
src/vs/workbench/contrib/quickaccess/browser/quickAccess.contribution.ts:const quickAccessNavigatePreviousInViewPickerId = 'workbench.action.quickOpenNavigatePreviousInViewPicker';
src/vs/workbench/contrib/quickaccess/browser/viewQuickAccess.ts:        static readonly ID = 'workbench.action.quickOpenView';
src/vs/workbench/contrib/search/browser/search.contribution.ts:         commandId: 'workbench.action.quickOpen',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpen',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenPreviousEditor',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenPreviousRecentlyUsedEditor',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenLeastRecentlyUsedEditor',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenPreviousRecentlyUsedEditorInGroup',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenLeastRecentlyUsedEditorInGroup',
src/vs/workbench/contrib/terminal/common/terminal.ts:   'workbench.action.quickOpenView',
src/vs/workbench/contrib/terminal/common/terminalConfiguration.ts:                      "A set of command IDs whose keybindings will not be sent to the shell but instead always be handled
by VS Code. This allows keybindings that would normally be consumed by the shell to act instead the same as when the terminal is not focused, for example `Ctrl+P` to launch Quick Open.\n\n \n\nMany commands are skipped by default. To override a default and pass that command's
keybinding to the shell instead, add the command prefixed with the `-` character. For example
add `-workbench.action.quickOpen` to allow `Ctrl+P` to reach the shell.\n\n \n\nThe following list of default skipped commands is truncated when viewed in Settings Editor. To see the
full list, {1} and search for the first command from the list below.\n\n \n\nDefault Skipped Commands:\n\n{0}",
src/vs/workbench/contrib/terminalContrib/quickAccess/browser/terminal.quickAccess.contribution.ts:    QuickOpenTerm = 'workbench.action.quickOpenTerm',
src/vs/workbench/contrib/terminalContrib/quickAccess/browser/terminal.quickAccess.contribution.ts:const quickAccessNavigateNextInTerminalPickerId = 'workbench.action.quickOpenNavigateNextInTerminalPicker';
src/vs/workbench/contrib/terminalContrib/quickAccess/browser/terminal.quickAccess.contribution.ts:const quickAccessNavigatePreviousInTerminalPickerId = 'workbench.action.quickOpenNavigatePreviousInTerminalPicker';
src/vs/workbench/contrib/welcomeGettingStarted/common/gettingStartedContent.ts:
                        description: localize('gettingStarted.quickOpen.description.interpolated', "Navigate between files in an instant with one keystroke. Tip: Open multiple files by pressing the right arrow key.\n{0}", Button(localize('quickOpen', "Quick Open a File"), 'command:toSide:workbench.action.quickOpen')),

いくつか該当するものが出てくるので、この中で最も関連が高そうな、

src/vs/workbench/contrib/search/browser/search.contribution.ts:         commandId: 'workbench.action.quickOpen',

に注目してみます。(search とあるのでそれっぽいという程度の理由です)

このようにあるので、次は AnythingQuickAccessProvider を見てみます。

先ほど見た、AnythingQuickAccessProvider.PREFIX は空文字になっており、実際の挙動と一致していそうです。

補足

例えば、コマンドパレットは PREFIX が > となっているときに開かれます。
実際、該当するコードを追っていくとそのようになっていることが分かります。

https://github.com/microsoft/vscode/blob/5886936cd0c23a5599a8d3b3aea5b48618e27ab3/src/vs/workbench/contrib/quickaccess/browser/quickAccess.contribution.ts#L42-L48

AnythingQuickAccessProvider のメソッドを見ると、_getPicks があり、ここで doGetPicks が使われているので、これを見てみます。

高速に結果を返す picks と、遅延して結果を返す additionalPicks に分かれていることが分かります。
全部を追っていくと長くなってしまいますし、(Ctrl+P からの動作において) picks は最近開いたファイルの履歴くらいしか関係しないと思われるので、今回は additionalPicks の方を見ていきます。

履歴のファイルを除いて検索し、セパレータを先頭に入れた上でその結果を返していることが分かります。

セパレータの確認

そんな表示あったかなと思ったので確認してみたら、確かに「最近開いたもの」と「検索ファイル」の間に表示されていました。

というわけで、getAdditionalPicks を次は見ていきます。
以下で、ファイル検索とシンボル検索を行っています。

次に、その結果をマージし、compareItemsByFuzzyScore で表示順序を決定しています。

なので、compareItemsByFuzzyScore を見ればアルゴリズムが分かりそうです。

ファイルのソート方法

上記の調査で、compareItemsByFuzzyScore を使ってファイルをソートしていることが分かったので、これを見ていきます。

この関数は、6つの条件を順に見ていき、比較を行うような関数になっています。
そのため、優先度が高い条件から順に説明していきます。

1. どちらかの絶対パスがクエリと完全一致している場合

どちらかのスコアが PATH_IDENTITY_SCORE と一致しているときに、一致しているものが前へと来るようにしています。
この PATH_IDENTITY_SCORE が返されるのは、

にあるように、クエリと絶対パスが一致しているケースのみです。

2. ラベルでの一致

ここでのラベルとは、ファイルの basename のことを指します。

スコアが LABEL_SCORE_THRESHOLD より大きいときの条件なので、LABEL_SCORE_THRESHOLD が関係する部分を見ます。

ラベルでマッチした場合、スコアは baseScore + labelScore として計算されます。
また、baseScore は以下のように決まります。

• 前方一致した場合: LABEL_PREFIX_SCORE_THRESHOLD (1 << 17) + prefixLengthBoost
  • より短いファイル名が優先される (window.ts は windowActions.ts よりスコアが高くなる)
• それ以外の場合: LABEL_SCORE_THRESHOLD (1 << 16)

そして、labelScore ですが、簡単な説明がコメントとして残してあります。

つまるところ、動的計画法を使ってスコアを計算しているというものです。
LCS のようなアルゴリズムを理解していると、コードが読みやすくなるかもしれません。
詳細は省きますが、

• ラベルの先頭文字へのマッチ
• 連続した文字列でのマッチ
• _ や . のような区切り文字の直後の文字へのマッチ

のようなものを高めに評価しています。
コメントを拾うだけでも、そこそこ理解できるかと思います。

3. description を含めたスコアでの比較

ここでの description とは、basename 以外の部分のパスのことです。
ただし、絶対パスではなく、相対パスで見たときのものです。

ラベルでマッチしなかった場合、description + ラベルを結合した文字列でスコアリングされます。
この場合、baseScore が加算されないため、スコアは LABEL_SCORE_THRESHOLD 未満になります。

また、スコアについては、先程説明したスコアの評価に加えて、パスを含むときに、
パスの区切り直後の文字 (ディレクトリ名の先頭文字) へのマッチのような条件も高く評価されるようになります。

4. ラベルにマッチするものがあるかどうか

ここからは、スコアが一致する際の条件になります。

ラベル部分にマッチするものがあるものを優先するようにしています。

5. マッチ距離による比較

マッチがコンパクトな方を優先します。
つまり、マッチの開始位置から終了位置の距離での比較を行います。
例えば、クエリ hts で helper.ts と httpService.ts を比較する場合、h から s までの距離が近い helper.ts が httpService.ts より優先されます。
また、ラベルと description にまたがらないようなマッチが、より優先されます。

6. フォールバック

1. ~ 5. までで決まらない場合にフォールバック処理として、fallbackCompare が呼ばれます。

ラベル + description の長さによる比較

まず、ラベルと description の長さの短い方が優先されます。
つまり、相対パスを文字列としてみた際に短いものです。

絶対パスの長さによる比較

次に、絶対パスを文字列としてみた際に、短いものが優先されます。
ラベル + description との違いが無いように思うかもしれませんが、マルチルートワークスペース環境などのときに違いが出ます。

ラベルの辞書順

ラベルを辞書順比較します。
かなりフォールバック感が出てきました。

description の辞書順比較

description を辞書順比較します。

絶対パスの辞書順比較

絶対パスを辞書順比較します。
これでも差がでなければ、完全に同じものになります。

まとめ

ごちゃごちゃしてきたので、改めてまとめます。

優先度	条件	説明	例 (クエリが window)
1	絶対パスの完全一致	クエリと絶対パスが完全一致
2	ラベルの前方一致	ファイル名 (basename) が前方一致、短いファイル名を優先	window.ts → windowActions.ts
3	ラベルの連続一致	ファイル名のどこかでのマッチ	myWindow.ts
4	ラベル内での非連続一致	ファイル名で飛び飛びにマッチ	w_i_n_d_o_w.ts
5	description でのマッチ	パスのマッチ	src/window/helper.ts
6	ラベルでのマッチの有無	スコアが同じ際に、ファイル名にマッチがある方を優先	src/win/dow.ts → src/win/dow/helper.ts
7	マッチ距離	マッチがコンパクトな方を優先	src/win/dow.ts → src/win/foo/dow.ts
8	フォールバック	パスの長さ、辞書順で比較	短いパス → 長いパス

あくまで例は、その条件中での比較なので、実際に検索をした際には、その順にならない場合があります。

おわりに

ファイル検索の裏側には、かなり細かい優先順位が設定されていました。
ユーザー体験への配慮がにじみ出ていて、調査していて面白かったです。