💭
コード検索クエリのデザインについて

2024/12/26に公開
AST
code
tech
Zennの皆さん、こんにちは、メリクリ！ast-grepの作者、Herringtonです。この記事は、ブログをA翻訳したものです。それでも、この記事が皆さんのインスピレーションになれば幸いです。
コード検索は、現代のソフトウェア開発において不可欠なツールです。開発者はコード検索を利用することで、既存のコードを迅速に見つけ、理解し、再利用できるようになり、生産性を向上させ、プロジェクト全体でコードの一貫性を確保できます。
その中核において、ast-grep はコード検索ツールです。lintやコード書き換えなどの他の機能は、コード検索機能を基盤として構築されています。
このブログ記事では、コード検索のデザイン空間、特にクエリがどのように設計され使用されるかに焦点を当てて掘り下げていきます。優れた論文である「Code Search: A Survey of Techniques for Finding Code」からインスピレーションを得ています。ただし、その論文のすべての詳細を網羅するわけではありません。代わりに、コード検索ツールがユーザーに検索意図を表現させる多様な方法に焦点を当てます。

 クエリの設計とクエリのタイプすべてのコード検索はクエリから始まります。クエリは、検索エンジンにどのようなコードを探しているかを伝えるための単なる手段です。これらのクエリがどのように設計されるかは非常に重要です。コード検索ツールの設計者は、いくつかの重要な目標を達成することを目指しています。

 簡単さクエリは簡単に記述できる必要があり、ユーザーが広範な学習を必要とせずに迅速に検索できるようにする必要があります。クエリを書くのが難しすぎると、ツールを使用すること自体をためらってしまう可能性があります。

 表現力ユーザーは探しているものを何でも表現できる必要があります。クエリ言語が制限されすぎていると、特定の結果を見つけることができません。

 正確さクエリは関連性の高い結果を生み出すのに十分なほど具体的である必要があり、無関係な結果を回避する必要があります。
これらの3つの目標すべてを同時に達成することは、多くの場合、反対の方向に引っ張られるため、困難です。たとえば、非常にシンプルで簡単なクエリ言語では表現力が十分でない可能性があり、非常に正確なクエリ言語はなユーザーにとっては複雑すぎる可能性があります。
コード検索ツールは、これらの目標のバランスをどのように取っているのでしょうか？このブログでは、コード検索クエリをいくつかの主要なタイプに分類し、それぞれに独自の特徴があります。それは、非形式的クエリ、形式的クエリ、およびハイブリッドクエリです。

 非形式的クエリこれらのクエリは、私たちが自然に自分自身を表現する方法に最も近く、さらに次のように細分化できます。

 自由形式のクエリこれらは多くの場合、自由形式であり、Web検索のように、目的のコード機能を説明するために自然言語を使用します。たとえば、「ファイルを1行ずつ読み込む」または「FileReaderを閉じる」などです。

長所: ユーザーが簡単に作成でき、Web検索エンジンの使用に似ており、表現力が高い。

短所: 自然言語の性質と、クエリとコードベースの間の語彙の不一致の可能性により、曖昧で精度が低い可能性がある。
GitHub Copilotのようなツールはこのアプローチを使用しています。

 入出力の例これらのクエリは、入出力ペアを提供することにより、コードの望ましい動作を指定します。入力とその対応する出力のペアを使用して、望ましい動作を指定します。たとえば、入力 "susie@mail.com" は、出力 "susie" になるはずです。

長所: 望ましい動作を正確に指定できる

短所: 十分な例を提供するために多少の労力が必要になる可能性がある
このアプローチは、実用的なツールよりも学術研究でより一般的です。このブログでは、このアプローチを使用するオープンソースツールを認識していません。
非形式的クエリは精度が低いため、ここでは詳細には説明しません。

 既存のプログラミング言語に基づく形式的クエリ
形式的クエリは、より正確な構造化されたアプローチを使用します。それらはさらにいくつかのサブカテゴリに分類できます。

 プレーンコード最も単純なバージョンでは、コードベースで一致する必要がある正確なコードスニペットを提供します。たとえば、ユーザーは次のJavaスニペットのインスタンスを検索する場合があります。
try {
  File file = File.createTempFile("foo", "bar");
} catch (IOException e) {
}
プレーンコード検索を直接サポートするツールは多くありません。それらは通常、従来の検索エンジンのように、トークン化プロセスを通じて検索クエリをより小さな部分に分割します。
注目すべき例としては、grep.appがあります。

 穴付きのコードこのアプローチでは、コードフラグメントを検索するためにプレースホルダー付きのコードスニペットを提供します。たとえば、ユーザーはJavaで次のパターンを検索する場合があります。
public void actionClose (JButton a, JFrame f) {
 $$$BODY
}
ここで、$$$BODY はプレースホルダーであり、コード検索エンジンは一致するすべてのコードを見つけようとします。ast-grep はこのカテゴリに該当し、クエリを穴付きの抽象構文木（AST）として扱います。ast-grepの穴はメタ変数と呼ばれます。
GritQLやIntelliJ IDEAの構造検索機能などの他のツールもこの手法を使用しています。

 パターンマッチング記号付きのコードこれらのクエリでは、コード構造を表して一致させるために特殊記号を使用します。たとえば、Combyの次のクエリは、条件が比較であるすべてのifステートメントを検索しようとします。
if (:[var] <= :[rest])
Combyでは、:[var]と:[rest]はコードの文字列に一致する特殊なマーカーです。
if (width <= 1280 && height <= 800) {
  return 1;
}
:[var]は<=文字が見つかるまですべての文字列に一致し、この場合はwidthになります。:[rest]はそれに続くすべて、つまり1280 && height <= 800に一致します。ast-grepとは異なり、CombyはASTを認識していません。例の:[rest]は複数のASTノードにまたがっているためです。CombyやShishoのようなツールはこのアプローチを使用しています。

 長所と短所長所: プログラミング言語に精通している開発者にとっては、簡単に作成できます。
短所: 不完全なコードスニペットを解析するのは難しい場合があります。
既存の言語を使用することの欠点は、IntelliJ IDEAのドキュメントでも強調されています。
入力された（SSR）テンプレートは、適切に形成されたJava構造である必要があります...
クエリが不完全またはあいまいであるため、プログラミング言語の既製の文法ではクエリを解析できない場合があります。たとえば、"key": "value" は有効なJSONオブジェクトではなく、JSONパーサーはそれを拒否し、クエリの作成に失敗します。人間にはキーと値のペアであることが明確かもしれませんが、パーサーはそれを認識していません。他の例としては、C/C++での関数呼び出しとマクロ呼び出しの区別などがあります。
ast-grep は、この問題に対して独自のアプローチをとります。パターンオブジェクトを使用して完全で有効なコードスニペットを表して明確にし、セレクターを利用してクエリに一致する部分を抽出します。

 カスタム言語を使用した形式的クエリ
 既存のプログラミング言語の拡張機能これらの言語は、既存のプログラミング言語をワイルドカードトークンや正規表現演算子などの機能で拡張します。たとえば、パターン $(if $$ else $) $+ を使用して、コードベース内のすべてのネストされたif-elseステートメントを見つける場合があります。CoccinelleとSemgrepはこのアプローチを採用しているツールです。
たとえば、Semgrepのパターン構文には、省略記号メタ変数、型付きメタ変数、ディープ式演算子など、標準的なプログラミング言語の実装では解析できない広範な機能があります。
省略記号メタ変数
# 省略記号とメタ変数を組み合わせて、ASTのシーケンスに一致させる
# 省略記号は有効なプログラミング言語の構文ではないことに注意してください
pattern: foo($...ARGS, 3, $...ARGS)
# このパターンは foo(1, 2, 3, 4, 5) に一致します
型付きメタ変数
# Loggerオブジェクトのlogメソッドの呼び出しを探す。
# このような単純なパターンは `Math.log()` にも一致します
pattern: $LOGGER.log(...)
# 型付きメタ変数は、メタ変数に型制約を設けることができます
# ただし、これは有効なJavaコードではなくなりました
pattern: (java.util.logging.Logger $LOGGER).log(...)
ディープ式演算子
# ディープ式演算子 <... [your_pattern] ...> を使用して、
# 別の式の中に深くネストされている可能性のある式に一致させる
pattern: |
  if <... $USER.is_admin() ...>:
    ...
長所: これらの言語は、プレーンなプログラミング言語よりも表現力が高い場合があります。
短所: ユーザーは新しい構文とセマンティクスを学習する必要があり、ツール開発者は拡張機能をサポートする必要があります。
ast-grep も $$$VARS の形式で複数のメタ変数をサポートしていることに注意してください。Semgrepと比較して、ast-grepのメタ変数は依然として有効なコードスニペットを生成します。
ドメイン固有言語を使用して検索クエリを表すこともできます。

 論理ベースのクエリ言語これらの言語は、コードのプロパティを表現するために、一階述語論理またはDatalogのような言語を利用します。たとえば、ユーザーは名前が「HelloWorld」のすべてのクラスを見つけることができます。これらの言語の一部はSQLに似ています。CodeQLとGleanは、2つの注目すべき例です。CodeQLの例を次に示します。
from If ifstmt, Stmt pass
where pass = ifstmt.getStmt(0) and
  pass instanceof Pass
select ifstmt, "この'if'ステートメントは冗長です。"
このCodeQLクエリは、ifブロック内の最初のステートメントがpassステートメントであるPythonの冗長なifステートメントを特定します。
クエリの説明:

from If ifstmt, Stmt pass: クエリのこの部分では、クエリで使用される2つの変数 ifstmt と pass を定義します。

where pass = ifstmt.getStmt(0) and pass instanceof Pass: クエリのこの部分は、結果をフィルタリングします。ifstmt の最初のステートメントが Pass ステートメントであるかどうかを確認します。

select ifstmt, "この'if'ステートメントは冗長です。" : クエリのこの部分は、結果を選択します。ifstmt とメッセージを返します。

長所: これらの言語は、構文を超えた複雑なコードのプロパティを正確に表現できます。
短所: 学習曲線が急です。

 埋め込みドメイン固有言語埋め込みDSLは、ホスト言語を使用してクエリを表現します。クエリはホスト言語に埋め込まれ、ホスト言語はクエリを表現するために必要な構成を提供します。次に、クエリはツールによって解析および解釈されます。
埋め込みDSLには、構成ベースとプログラムベースの2つの種類があります。

 構成ベースのeDSL構成ベースのeDSLを使用すると、ユーザーはクエリを記述する構成オブジェクトを提供できます。次に、ツールはこの構成オブジェクトを解釈して検索を実行します。ast-grep CLIとsemgrep CLIはどちらも、YAMLファイルを使用してこのアプローチを採用しています。
ast-grep YAMLルール
id: match_func_call
language: c
rule:
  pattern:
    context: $M($$$);
    selector: call_expression
Semgrep YAMLルール
rules:
  - id: my-pattern-name
    pattern: |
      TODO
    message: "ユーザーに表示するメッセージ"
    languages: [python]
    severity: ERROR
構成ファイルはパターンよりも表現力があり、それでも比較的簡単に記述できます。ユーザーは通常、ホスト言語（YAML）をすでに知っており、その構成を利用してクエリを表現できます。

 プログラムベースのeDSLプログラムベースのeDSLは、ASTノードオブジェクトを介してASTに直接アクセスできます。
プログラムによるAPIの例としては、JSCodeshift、Joernのコードプロパティグラフ、およびast-grepのNAPIなどがあります。
@ast-grep/napi
import { parse, Lang } from '@ast-grep/napi'

let source = `console.log("hello world")`
const ast = parse(Lang.JavaScript, source)  // 1. ソースの解析
const root = ast.root()                     // 2. ルートの取得
const node = root.find('console.log($A)')   // 3. ノードの検索
node.getMatch('A').text()                   // 4. 情報の収集
// "hello world"
JSCodeshift
const j = require('jscodeshift');

const root = j(`const a = 1; const b = 2;`);

const types = root.find(j.VariableDeclarator).getTypes();
console.log(types); // Set { 'VariableDeclarator' }
コードプロパティグラフ
import io.shiftleft.codepropertygraph.Cpg
import io.shiftleft.semanticcpg.language._

object FindExecCalls {
  def main(args: Array[String]): Unit = {
    // Cコードベースの読み込み
    val cpg: Cpg = Cpg.apply("path/to/your/codebase")

    // すべての `exec` 関数呼び出しを見つけて、それらの場所を出力します
    cpg.call("exec").location.l.foreach(println)
  }
}
長所: より正確で表現力があり、比較的簡単に記述できます。
短所: ホスト言語と検索ツール間の通信のオーバーヘッドが高くなる可能性があります。

 汎用プログラミング言語のような言語最後に、ツールは独自の汎用プログラミング言語を設計することもできます。これらの言語は、コードのプロパティを記述するための完全なプログラミング言語を提供します。GritQLはこのアプローチの例です。
たとえば、このGritQLクエリは、すべての console.log 呼び出しを winston.debug に、すべての console.error 呼び出しを winston.warn に書き換えます。
`console.$method($msg)` => `winston.$method($msg)` where {
  $method <: or {
    `log` => `debug`,
    `error` => `warn`
  }
}
クエリの説明パターンマッチング: パターン console.$method($msg) は、メソッド ($method) と引数 ($msg) を持つ console オブジェクトがあるコードに一致するために使用されます。ここで、$method と $msg はそれぞれ任意のメソッドと引数のプレースホルダーです。
書き換え: 書き換え記号 => は、一致した console コードが winston を使用するように変換する必要があることを指定し、その後にメソッド ($method) と引数 ($msg) が続きます。
メソッドマッピング: where 句は、書き換えに関する追加の制約を指定します。具体的には、$method <: or { 'log' => 'debug', 'error' => 'warn' } は、次のことを意味します。

$method が log の場合、debug に変換する必要があります。

$method が error の場合、warn に変換する必要があります。
要するに、このルールはコンソールログメソッドを対応するWinstonログメソッドに置き換えます。

console.log('message') は winston.debug('message') になります

console.error('message') は winston.warn('message') になります
長所: シンプルなパターンや構成ベースの埋め込みDSLと比較して、より正確で表現力があります。ただし、プログラムベースのeDSLほど柔軟ではなく、論理ベースの言語ほど強力ではない可能性があります。
短所: ユーザーがカスタム言語を最初に学習する必要があるという欠点があります。論理ベースの言語よりも学習は簡単ですが、埋め込みDSLを使用する場合と比較すると、それでもいくらかの学習が必要です。

 ハイブリッドクエリハイブリッドクエリは、複数のクエリタイプを組み合わせます。たとえば、自由形式のクエリを入力と出力の例と組み合わせたり、自然言語クエリをプログラム要素参照と組み合わせたりできます。
ast-grepは、ハイブリッドクエリを使用するツールの良い例です。YAMLルールで直接パターンを定義するか、プログラムによるAPIを使用できます。
まず、次のようにYAMLルールにパターンを埋め込むことができます。
rule:
  pattern: console.log($A)
  inside:
    kind: function_declaration
プログラムによるAPIでも同様の概念を使用できます。
import { Lang, parse } from '@ast-grep/napi'

const sg = parse(Lang.JavaScript, code)
sg.root().find({
  rule: {
    pattern: 'console.log($A)',
    inside: {
      kind: 'function_declaration'
    }
  }
})
この柔軟な設計により、基本的なクエリをより大きく、より複雑なクエリに結合でき、非常に複雑で具体的な検索には常に汎用言語を使用できます。
ast-grepは既存のプログラミング言語を優先します。ユーザーに新しい言語を学習させるのではなく、既存の言語構造を使用してクエリを記述できるようにしたいと考えています。また、TypeScriptは優れた型システムを備えた優れた言語であると考えています。コード検索ロジックを表現するために新しい言語を再発明する必要はありません。

 ast-grepのデザイン選択コード検索ツールの設計には、微妙なバランスが必要です。使いやすさ、表現力、および精度を同時に達成することは、これらの目標がしばしば競合するため、困難です。コード検索ツールは、ユーザーの多様なニーズを満たすために、これらのトレードオフを慎重に乗り越える必要があります。
ast-grepは、この課題に対処するために特定の選択をしています。

馴染みやすさの優先: 既存のプログラミング言語の構文に基づくパターンマッチングを使用しているため、開発者は使い慣れたコーディング構造でツールを使い始めるのが簡単です。

柔軟性の拡張: 構成ベース（YAML）およびプログラムベース（NAPI）の埋め込みDSLを組み込むことで、複雑な検索のための追加の表現力が提供されます。

ハイブリッドかつ進歩的なデザイン: パターンマッチング、YAMLルール、およびNAPIは、ハイブリッドでの使用を想定して設計されており、ユーザーは単純なものから始めて徐々に複雑さを追加できます。各APIの概念も転用可能であり、ユーザーはより高度な手法を段階的に学習できます。

ASTベースの精度: すべてのクエリがASTベースであることを要求することにより、精度を重視し、正確な結果を保証します。ただし、クエリは慎重に作成する必要があるというトレードオフがあります。

多言語サポート: すべてのプログラミング言語用の新しいクエリ言語を作成したり、コード検索のために既存の言語を大幅に拡張したりする代わりに（これは非常に大きな事業になります）、ast-grepはそのパターンで既存のプログラミング言語の使い慣れた構文を再利用します。これにより、複数の言語で作業する開発者にとってツールがより親しみやすくなります。

 その他の考慮事項クエリの設計に焦点を当ててきましたが、コード検索ツールの有効性に影響を与える他の要因もあります。これらには、以下が含まれます。
オフラインインデックス作成: これは高速なオフライン検索に不可欠です。現在、ast-grepは各クエリに対して常にメモリ内にASTを構築するため、オフラインインデックス作成をサポートしていません。インデックス作成を使用するgrep.appのようなツールは、数百万のリポジトリを検索する場合に高速です。
情報インデックス作成: コード検索では、コード要素以外にもさまざまな種類の情報をインデックス化できます。変数スコープ、型情報、定義、および制御フローとデータフローは、コード検索にとってすべて貴重なデータです。現在、ast-grepはAST自体のみをインデックス化します。
取得手法: ツールがクエリに基づいて一致するコードをどのように見つけるかは、重要な側面です。このために、さまざまなアルゴリズムと機械学習アプローチが存在します。ast-grepは、クエリのASTとコードのASTを比較する手動実装を使用します。
ランキングとプルーニング: 検索結果がどのように順序付けられるかも、優れた検索結果を提供する上で重要な要素です。
クエリの設計とクエリのタイプ

簡単さ

表現力

正確さ

非形式的クエリ

自由形式のクエリ

入出力の例

既存のプログラミング言語に基づく形式的クエリ

プレーンコード

穴付きのコード

パターンマッチング記号付きのコード

長所と短所

カスタム言語を使用した形式的クエリ

既存のプログラミング言語の拡張機能

論理ベースのクエリ言語

埋め込みドメイン固有言語

構成ベースのeDSL

プログラムベースのeDSL

汎用プログラミング言語のような言語

ハイブリッドクエリ

ast-grepのデザイン選択

その他の考慮事項

Discussion
