88

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

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

時間の制約もあります。リストを作成するのに数秒かかる場合、補完は役に立ちません。補完アルゴリズムが数千のクラスを処理する場合があります。

これに適したアルゴリズムとデータ構造は何ですか?

4

3 に答える 3

68

UnrealScript 言語サービス製品の IntelliSense エンジンは複雑ですが、ここではできる限り概要を説明します。VS2008 SP1 の C# 言語サービスは、私のパフォーマンス目標です (正当な理由があります)。まだそこにはありませんが、ctrl + スペースまたはユーザーが.(ドット) を入力するのを待たずに、1 文字を入力した後に安全に提案を提供できるほど高速で正確です。[言語サービスに取り組んでいる] 人々がこの主題についてより多くの情報を入手すればするほど、私が彼らの製品を使用した場合に得られるエンド ユーザー エクスペリエンスは向上します。私が扱った製品の多くは、細部に細心の注意を払っていなかったため、コーディングよりも IDE と格闘していました。

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

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

IntelliSense バックエンドに関する追加の注意事項を次に示します。

  • を実装する際に、LINQ の遅延評価メカニズムを多用していますGetMembers。キャッシュ内の各オブジェクトは、そのメンバーを評価するファンクターを提供できるため、ツリーで複雑なアクションを実行することはほとんど簡単です。
  • List<IDeclaration>各オブジェクトがそのメンバーの を保持する代わりに、 を保持しますList<Name>。ここで、Nameはメンバーを説明する特別にフォーマットされた文字列のハッシュを含む構造体です。名前をオブジェクトにマップする巨大なキャッシュがあります。このようにして、ファイルを再解析するときに、ファイルで宣言されているすべての項目をキャッシュから削除し、更新されたメンバーで再設定できます。ファンクターの構成方法により、すべての式はすぐに新しい項目に評価されます。

IntelliSense「フロントエンド」

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

  • 償還要因の 1 つは、パーサーが高速であることです。優先度の低いバックグラウンド スレッドで自己完結型で動作しながら、20000 行のソース ファイルの完全なキャッシュ更新を 150 ミリ秒で処理できます。このパーサーが開いているファイルのパスを (構文的に) 正常に完了するたびに、ファイルの現在の状態がグローバル キャッシュに移動されます。
  • ファイルの構文が正しくない場合は、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

このレイアウトで実装した IntelliSense 機能のリストを追加することにしました。それぞれの写真はこちらにあります。

  • オートコンプリート
  • ツールのヒント
  • メソッドのヒント
  • クラス ビュー
  • コード定義ウィンドウ
  • Call Browser (VS 2010 は最終的にこれを C# に追加します)
  • 意味的に正しいすべての参照を検索
于 2009-08-02T23:59:54.623 に答える
17

特定の実装でどのアルゴリズムが使用されているかは正確にはわかりませんが、ある程度の推測はできます。トライは、この問題に非常に役立つデータ構造です。IDE は、プロジェクト内のすべてのシンボルのメモリに大きなトライを保持し、各ノードに追加のメタデータを追加できます。

文字を入力すると、トライのパスをたどります。特定のトライ ノードのすべての子孫は、可能な補完です。その後、IDE は、現在のコンテキストで意味のあるものによってそれらを除外する必要がありますが、タブ補完ポップアップ ウィンドウに表示できる数だけ計算する必要があります。

より高度なタブ補完には、より複雑な試行が必要です。たとえば、Visual Assist Xには、キャメルケース記号の大文字のみを入力する必要があるという機能があります。たとえば、SFN と入力するとSomeFunctionName、タブ補完ウィンドウに記号が表示されます。

トライ (または他のデータ構造) を計算するには、すべてのコードを解析して、プロジェクト内のすべてのシンボルのリストを取得する必要があります。Visual Studio はこれを、.ncbプロジェクトと共に保存されるファイルである IntelliSense データベースに保存するため、プロジェクトを閉じて再度開くたびにすべてを再解析する必要はありません。大規模なプロジェクト (たとえば、ソース管理から同期したばかりのプロジェクト) を初めて開くと、VS はすべてを解析してデータベースを生成するのに時間がかかります。

増分変更をどのように処理するかわかりません。あなたが言ったように、コードを書いているときは、90% の確率で無効な構文であり、アイドル状態になるたびにすべてを再解析すると、CPU に莫大な負担がかかり、ほとんどメリットがありません。大量のソース ファイル。

(a) プロジェクトを実際にビルドするとき (または、プロジェクトを閉じたり開いたりするとき) にのみ再解析するか、(b) ローカル解析のようなものを実行して、その周辺のコードのみを解析するかのいずれかであると思われます。関連するシンボルの名前を取得するためだけに、いくつかの限られた方法で編集されました。C++ は非常に複雑な文法を持っているため、大量のテンプレート メタプログラミングなどを使用している場合、隅々までおかしな動作をする可能性があります。

于 2009-08-02T23:12:30.043 に答える
1

次のリンクはさらに役立ちます..

構文の強調表示: 構文の強調表示用の高速に色分けされたテキスト ボックス

于 2012-04-01T08:21:43.210 に答える