[解決済み] コード補完の仕組みを教えてください。

質問

多くのエディタや IDE がコード補完機能を備えています。それらのいくつかは非常に知的であり、他のものはそうではありません。私は、よりインテリジェントなタイプに興味があります。例えば、ある関数がa)現在のスコープで利用可能である場合、b)その戻り値が有効である場合にのみ、その関数を提供するIDEを見たことがあります。(例えば、"5 + foo[tab]" の後は、整数に加えることができる何かを返す関数や正しい型の変数名だけを提供します)。また、より頻繁に使用される、または長いオプションをリストの前に配置することも見受けられます。

あなたがコードを解析する必要があることは理解しています。しかし、通常、現在のコードが無効であることを編集している間は、その中に構文エラーがあります。不完全でエラーが含まれている場合、どのように解析するのですか?

また、時間的な制約もあります。リストを出すのに数秒かかるようでは、補完は意味がありません。補完アルゴリズムが何千ものクラスを扱うこともあります。

このための良いアルゴリズムやデータ構造は何でしょうか？

どのように解決するのですか？

私の UnrealScript 言語サービス製品のインテリセンス エンジンは複雑ですが、ここではできる限り最高の概要を説明します。VS2008 SP1 の C# 言語サービスは、私のパフォーマンス目標です (これには理由があります)。まだそこまでは到達していませんが、十分に高速かつ正確であるため、1 文字が入力された後に、Ctrl+Space やユーザーが入力した . (ドット)を入力するのを待つことなく、1文字入力しただけで安全に提案を行うことができます。言語サービスに携わる人々がこのテーマについてより多くの情報を得れば得るほど、私がその製品を使用する際のエンドユーザー体験がより良いものになります。私がこれまで使ってきた製品の中には、このような細部にまで注意が払われておらず、その結果、コーディングよりも IDE との戦いが多くなってしまった不幸な経験がいくつもあります。

私の言語サービスでは、次のようにレイアウトしています。

1. カーソル位置の式を取得する．これは メンバアクセス式 の先頭からカーソルのある識別子の末尾までをたどります。メンバアクセス式は一般に次のような形式です。 aa.bb.cc のようなメソッド呼び出しを含むことができます。 aa.bb(3+2).cc .
2. を取得します。 コンテキスト を取得します。これは非常に厄介で、コンパイラと同じルールに従うとは限りませんが（長い話です）、ここではそうだと仮定します。一般的に、これはカーソルが含まれるメソッド/クラスに関するキャッシュされた情報を取得することを意味します。
3. コンテキストオブジェクトが IDeclarationProvider を実装しており、ここで GetDeclarations() を取得するために IEnumerable<IDeclaration> を取得します。私の場合、このリストには、ローカル/パラメータ（メソッド内の場合）、メンバー（フィールドとメソッド、インスタンスメソッド内でない限り静的のみ、ベースタイプのプライベートメンバーはなし）、グローバル（作業中の言語の型と定数）、およびキーワードが含まれています。このリストの中には、名前が aa . 1 の式を評価する最初のステップとして、コンテキスト列挙から名前 aa という名前の項目を選択し IDeclaration を与えます。
4. 次に、オペレータを適用して IDeclaration を表す aa を取得するために、別の IEnumerable<IDeclaration> の(ある意味)メンバーを含む aa . このため . 演算子は -> 演算子とは異なるため、私は declaration.GetMembers(".") を呼び、その後に IDeclaration オブジェクトがリストされた演算子を正しく適用することを期待します。
5. これは、私が cc で、ここで宣言リスト は という名前のオブジェクトが含まれています。 cc . お気づきだと思いますが、複数の項目が cc で始まる場合、それらも同様に表示されるはずです。私はこれを解決するために、最後の列挙を取り出し、それを 私の文書化されたアルゴリズム を通して、ユーザーに最も有用な情報を提供することで解決しています。

IntelliSenseバックエンドに関する追加の注意事項です。

• LINQの遅延評価機構を多用した GetMembers . 私のキャッシュ内の各オブジェクトは、そのメンバーに対して評価するファンクタを提供することができるので、ツリーで複雑なアクションを実行することはほとんど些細なことです。
• 各オブジェクトが List<IDeclaration> を保持する代わりに、私は List<Name> で、ここで Name は、メンバーを説明する特別にフォーマットされた文字列のハッシュを含む構造体です。名前とオブジェクトを対応付ける膨大なキャッシュがある。このようにして、ファイルを再解析するときに、そのファイルで宣言されているすべての項目をキャッシュから削除し、更新されたメンバーで再投入することができます。ファンクターが構成されているため、すべての式が直ちに新しい項目で評価されます。

IntelliSense "frontend"。

ユーザーが入力するとき、ファイルは構文的に 不正確 になることが多くなります。そのため、ユーザーがタイプしたときに、キャッシュのセクションを無計画に削除したくありません。私は、インクリメンタルな更新をできるだけ速く処理するために、多数の特殊なケースのルールを用意しています。インクリメンタル キャッシュは、開いているファイルに対してローカルにのみ保持され、ユーザーが自分の入力によってファイル内の各メソッドのようなバックエンド キャッシュに不正な行/列情報が保持されていることに気づかないようにするのに役立ちます。

• 1 つの救いは、私のパーサーは 速い . 優先度の低いバックグラウンド スレッドで自己完結的に動作しながら、20000 行のソース ファイルのキャッシュの完全な更新を 150ms で処理することができます。このパーサーは、開いているファイルに対して正常に（構文的に）パスを完了するたびに、そのファイルの現在の状態をグローバル キャッシュに移動します。
• ファイルが構文的に正しくない場合、私は ANTLR フィルタ パーサー (リンクについては申し訳ありません。ほとんどの情報はメーリングリストに掲載されているか、ソースを読んで収集したものです) を使って、ファイルを再解析して探します。
  • 変数/フィールドの宣言。
  • クラス/構造体定義のためのシグネチャ。
  • メソッド定義のためのシグネチャ。
• ローカルキャッシュでは、クラス/構造体/メソッド定義はシグネチャから始まり、ブレースのネストレベルが偶数に戻ると終了します。メソッドは、別のメソッド宣言に到達した場合にも終了することができます (メソッドのネストはありません)。
• ローカルキャッシュでは、変数/フィールドは直前の 閉じていない 要素にリンクされます。なぜこれが重要なのかについては、以下の簡単なコードスニペットを参照してください。
• また、ユーザーが入力する際に、追加/削除された文字範囲をマークするリマップテーブルを保持しています。これは、次のような場合に使用されます。
  • メソッドは完全なパースの間にファイル内で移動することがあるので、カーソルの正しいコンテキストを識別できることを確認する。
  • Go To Declaration/Definition/Reference が開いているファイルで正しくアイテムを見つけることを確認する。

前節のコードスニペットです。

class A
{
    int x; // linked to A

    void foo() // linked to A
    {
        int local; // linked to foo()

    // foo() ends here because bar() is starting
    void bar() // linked to A
    {
        int local2; // linked to bar()
    }

    int y; // linked again to A

このレイアウトで実装したインテリセンス機能の一覧を追加しておこうと思いました。 それぞれの画像はこちらにあります。

• オートコンプリート
• ツールチップ
• メソッドのヒント
• クラス表示
• コード定義ウィンドウ
• コールブラウザ (VS 2010 でようやく C# に追加されました)
• 意味的に正しい全参照の検索