CDT ベースのエディターを構築する、第 4 回: 高度な CDT 構文解析と Persisted Document Object Model

CDT の索引付けと PDOM を理解する

5 回からなる「CDT ベースのエディターを構築する」シリーズ第 4 回目の今回は、Eclipse の CDT (C/C++ Development Tooling) で 2 番目に使われている高度なパーサーを紹介します。この新しいプロセスは、その情報を PDOM (Persisted Document Object Model) で構成しており、索引付けやコード・コンプリーション、コンテンツ・アシストなどが可能です。皆さんが独自のカスタム・ツールとして CDT を改善、あるいは拡張しようとする場合には、この PDOM と新しい構文解析の理解が必須です。

Matthew Scarpino, Java Developer, Eclipse Engineering, LLC

Matthew Scarpino は、Eclipse Engineering LLC のプロジェクト・マネージャーであり、Java 開発者です。彼は SWT/JFace in Action の中心著者であり、また SWT (Standard Widget Toolkit) に対して、小さいながらも重要な貢献をしました。彼が好きなものはアイルランドの民族音楽やマラソン、William Blake の詩、そして GEF (Graphical Editing Framework) です。


developerWorks 貢献著者レベル

2006年 10月 24日

なぜ別のパーサーを学ぶ必要があるのか

外部リンケージは C/C++ の持つ数多くの機能の 1 つであり、このおかげでコード分析が難しくなります。変数や関数をどこで宣言しても、extern キーワードを使えば、その変数や関数がどこで定義されたものかわからなくても、他のファイルでそれらを使うことができます。この相互依存関係を表示するとなると、Eclipse の Outline ビュー (図 1 の左側) は役に立ちません。Outline ビュー は 1 つのソース・ファイルの要素しか表示しないのです。しかし右側の Index ビューは、すべての CDT プロジェクトのすべてのファイルの要素を表示します。複雑で相互に接続されたプロジェクトを理解しようとする場合には、2 番目の方法を使う必要があります。

図 1. Outline ビューと Index ビュー
Outline ビューと Index ビュー

もちろん、第 3 回で説明したパーサーを使って Index ビューを作成することもできますが、何らかのコードが変更された場合には、CDT ワークスペースにある、すべてのソース・ファイルを構文解析しなければなりません。それは現実的ではありません。

Index ビューのような機能を実現するために、CDT 開発者達は新しい構文解析プロセスを開発しました。このプロセスでは、結果をメモリー・マップされたファイルに保存します。このパーシスタンスによって、パーサーはプロジェクトの中に保存された要素にアクセスできる一方、最近変更されたファイルのみを分析できるようになります。この改善された構文解析プロセスによって、Index ビューを提供できるだけではなく、コード・コンプリーションやコンテンツ・アシストのような機能も実現することができます。


PDOM パーサーの動作

新しい構文解析プロセスは、第 3 回での説明と無関係ではありません。この新しいパーサーは、基本的には以前の Parser と同じように動作します。どちらも同じようなメソッドを持ち、同じような AST (abstract syntax tree) を作成します。しかし新しいプロセスでは、多くのことが変わっています。このプロセスの動作は、次の 4 つのステップで要約することができます。

  1. インデクサー (indexer) ジョブの開始
  2. TranslationUnit の構文解析
  3. PDOM の更新
  4. PDOM の Structure と Storage

こうした概念がコードとしてどのように実装されているかを示すために、私は BBCDT (Bare Bones C/C++ Development Tooling) を更新し、プロジェクト要素の索引を作成して特定のノード・タイプを表示するようにしました。そしてこれを有効にするために、前回の ASTAction を更新して、AST の要素と PDOM のストレージを訪問するようにしました。(コードについては「ダウンロード」セクションを参照してください。)

ステップ 1: インデクサー (indexer) ジョブの開始

コア・プラグインは起動すると、新しい構文解析とパーシスタンスを管理する PDOMManager を作成します。PDOMManager は、独自に何かをすることはほとんどありませんが、新しい CDT 要素 (特に CProject と TranslationUnit) がワークスペースに作成されると、それに応じて動作します。新しい CProject が作成された場合、PDOMManager はインデクサーを作成し、プロジェクトのソース・ファイル内でその要素を見つけて保存します。

インデクサーは IPDOMIndexer を実装していますが、そのクラスはユーザーの CDT のプリファレンスに依存します。図 2 は 3 つの索引付けのオプションを示しており、デフォルトとして No Indexer が選択されています。No Indexer が選択されると、PDOMManager は、何もしない NullPDOMIndexer を作成します。また、Fast C/C++ Indexer が選択されると FastPDOMIndexer を作成し、Full C/C++ Indexer が選択されると FullPDOMIndexer を作成します。インデクサーが作成されると、PDOMManager はインデクサーに対して、索引の作成を開始するように命令します。

図 2. インデクサーのプリファレンス
インデクサーのプリファレンス

索引付けの目的は、プロジェクトのソースコードの中にある名前付き要素をすべて記録し、それらを関連データと共に保存することです。これは複雑なプロセスであり、バックグラウンドで実行できるため、Eclipseの Job として実行されます。具体的には、インデクサーは優先度 Job.LONG を持つ索引付け Job を作成し、それをプラットフォームのキューに追加します。

もしプロジェクトが作成されたばかりの場合には、索引付けの対象となるコードがないため、この Job は大したことはしません。それでも Job は、プロジェクトにとって非常に重要なオブジェクト、PDOM を作成します。これによって、インデクサーのデータを PDOM 内に保存するルーチンが提供されます。

変化し続ける PDOM

この記事を書いている 2006 年 10 月の時点で、PDOM とその構文解析は、まだ決定していません。実際、CDT のニュースグループを見ると、戸惑った多くの人が、PDOM は安定してすらいないと言っています。しかし、これが CDT コード分析の将来なのであり、たとえ詳細が変更されたとしても、概念を理解することが重要です。PDOM は CDT の機能 (コンテンツ・アシストやコード・コンプリーション、索引付けなど) を実現する上で重要な役割を担うものであり、この役割は開発が続く限り拡張を続けるのです。

インデクサーは第 3 回での Parser とは異なり、即座に動作を開始せず、また自動的に動作を開始することもありません。PDOMManager は、CProject に変更 (新規のソース・ファイルや、ソース・ファイルの修正や削除) が加えられるのを待機しています。そして変更を検出すると、分析を開始するようにインデクサーに命令します。そして今度は、このインデクサー Job は本格的に動作をします。特に、変更された TranslationUnit と、そのユニットのソースコードの言語を表す ILanguage を見つけようとします。そして、ILanguage.getASTTranslationUnit() をコールすることで構文解析プロセスを開始します。

ステップ 2: TranslationUnit の構文解析

第 3 回の Parser は、プログラミング言語を区別せず、C と C++ の要素を探し、それらを使って汎用の AST を作ります。新しいプロセスの動作は、それとは異なります。各 TranslationUnit には ILanguage オブジェクトがあり、このオブジェクトは、何よりも、そのユニットの構文解析方法を指定します。もし CDT にカスタム言語を追加したい場合には、独自の ILanguage を作ることが第一歩です。幸い CDT には、GCCLanguageと GPPLanguage という 2 つが、デフォルトで用意されています。

同様に CDT には、ISourceCodeParser を実装した 2 つのパーサー、GNUCSourceParser と GNUCPPSourceParser がデフォルトで用意されています。構文解析のプロセスそのものは、第 3 回で説明したプロセスと同じです。コード・リーダーがソース・ファイルから文字バッファーを作成し、スキャナーが文字を組み合わせて IToken にし、パーサーが IToken を組み合わせて IASTNode にします。メソッド名さえも同じです (translationUnit() や declaration()、statement() など)。前回の構文解析プロセスと今回のプロセスとの主な違いは次のとおりです。

  • 新しいパーサーは言語固有に作られています。ノードは CASTNode または CPPASTNode を拡張します。
  • 新しいパーサーは常に COMPLETE_PARSE モードで実行します。そのため、必ず内部関数を構文解析します。
  • 新しいパーサーは、追加の構文解析情報 (問題やノード位置) を、コールバック・オブジェクトの中ではなく ILocationResolver の中に保存します。
  • 新しいパーサーが要素のスコープを判断するのは、要求があった時にのみです。
  • 新しい AST の先頭ノードは IASTTranslationUnit であり、その構造をトラバースするためには ASTVisitors を使います。

注意: 古い Parser は IASTCompilationUnit を返しましたが、PDOM パーサーは、IASTTranslationUnits を、もっと具体的には、CASTTranslationUnit と CPPASTTranslationUnit を返します。

上記の 4 番目の違いは重要です。パーサーは、その要素のスコープがわからない限り、その要素の使い方を判断できません。古い Parser は、構文解析を開始する際に translationUnit() で最上位レベルのスコープを作成します。そしてそのスコープを、その先のメソッド (declaration() など) に渡します。これらのメソッドは、必要に応じてサブスコープを作成し、渡していきます。古い Parser は、終了すると、その AST の全要素のスコープを持っていることになります。新しいパーサーは 1 つのスコープしか作成せず、動作中にそれを変更しません。これは、インデクサーが特定のノード・セットにしか働きかけないからです。このことを説明するためには、またその他の興味深い機能について説明するためには、インデクサーがパーサーの AST を使って何をするのか、また PDOM とどんなやり取りをするのかを説明する必要があります。

ステップ 3: PDOM の更新

インデクサーは、IASTTranslationUnit を受け取ると PDOM に対する書き込みロックを取得し、TranslationUnit のデータの追跡 (persist) を開始します。まず、インデクサーは IASTTranslationUnit.getIncludeDirectives() と IASTTranslationUnit.getMacroDefinitions() を呼び出します。次に、このユニットのファイルへの参照を、インクルードされているディレクティブとマクロ定義への参照と共に PDOM に保存します。これらの参照は PDOMFile の形式をとり、PDOM.addFile() として保存されます。

AST を検索、つまり訪問するために、インデクサーは新しい ASTVisitor を作成し、IASTTranslationUnit.accept(ASTVisitor) を呼び出します。AST の中の IASTNodes は、それぞれ accept() メソッドを持っており、どれもほとんど同じように次のような動作をします。

  1. IASTNodes は、ある ASTVisitor のブール・フィールドをチェックし、そのビジターがこのノードを訪問したいのかどうかを判断します。
  2. もしビジターが訪問したい場合には、そのノードはビジターの visit() メソッドを呼び出します。このメソッドは、次の 3 つの値のどれかを返します。
    • PROCESS_SKIP -- ビジターは、ノードの子には関心がないので、accept() は真を返します。
    • PROCESS_CONTINUE -- ビジターは訪問することにまったく関心がないので、accept() は偽を返します。
    • PROCESS_CONTINUE -- ビジターはノードの子を訪問することに関心があるので、accept() は次のステップに続きます。
  3. もしブール・フィールドが偽の場合、あるいは visit() が PROCESS_CONTINUE を返した場合、accept() はノードの子それぞれの accept() メソッドをコールし、その引数としてビジターを渡します。

例えば、もし、ある C 関数宣言が宣言指定子 (typedef や static など) を持っていたら、その関数に対応する CASTFunctionDefinition.accept() メソッドは、ビジターの shouldVisitDeclarations フィールドをチェックします。そのフィールドが真であれば、ビジターの visit() メソッドをコールします。そのフィールドが偽の場合、あるいはvisit() が PROCESS_CONTINUE を返した場合、その関数ノードはその子にアクセスし、CASTSimpleDeclSpecifier.accept() をコールします。ビジターが最終ノード、つまりターミナル・ノードの 1 つに達したら、accept() は単純に真を返します。

表 1 は、どのノード・タイプがビジターの visit() メソッドを呼び出すことができるかをコントロールする、ブール・フィールドを示しています。これらのフィールドは、デフォルトですべて偽に設定されているので、visit() メソッドが呼ばれることはありません。

表 1. ノード訪問をコントロールする ASTVisitor フィールド
shouldVisitNamesshouldVisitDeclarationsshouldVisitInitializers
shouldVisitDeclaratorsshouldVisitDeclSpecifiersshouldVisitExpressions
shouldVisitTypeIdsshouldVisitEnumeratorsshouldVisitTranslationUnit
shouldVisitParameterDeclarationsshouldVisitStatementsshouldVisitProblems

ASTVisitor の動作を理解するためには、例を見るのが一番です。リスト 1 は、PDOMFullIndexerJob が IASTName ノードを見つけるために使用するビジターを示しています。これらのノードを訪問するために、ビジターは shouldVisitNames と shouldVisitDeclarations を真に設定します。

リスト 1. PDOMFullIndexerJob の ASTVisitor
ast.accept(new ASTVisitor() {
   // Set the Boolean fields so that name and declaration nodes call visit()
   {
      shouldVisitNames = true;
      shouldVisitDeclarations = true;
   }

   // Perform the visit
   public int visit(IASTName name) {
      try {
         IASTFileLocation fileloc = name.getFileLocation();
         if (fileloc != null) {
            PDOMFile file = pdom.addFile(fileloc.getFileName());
            linkage.addName(name, file);
         }
         return PROCESS_CONTINUE;
      } catch (Throwable e) {
         CCorePlugin.log(e);
         return ++errorCount > MAX_ERRORS ? PROCESS_ABORT : PROCESS_CONTINUE;
      }
   };
});

これを見るとわかるように、インデクサーのビジターは、IASTName のみに関心を持っています。そして PDOM に保存されるノードは IASTName のみです。これらは特定の指定子、例えば関数名や変数名、列挙型の名前などを表しています。ビジターがこうしたノードのどれかに到達すると、その名前のソース・ファイルを表す PDOMFile オブジェクトにアクセスします。そして PDOM のリンケージ・オブジェクト (PDOMLinkage) を使って索引に IASTName を追加します。

IASTName が保存される前に、リンケージは、そのタイプ、つまりバインディング を知る必要があります。例えば、それが変数名なのか関数名なのか、などです。それを見つけるために、リンケージは、ノードの親と、そのスコープを見つけます。リンケージはこのスコープを使って、どのように名前が使われているかを判断し、その情報を IBinding の中にカプセル化します。新しい構文解析プロセスがスコープの判断を構文解析の後に行っているのは、このためです。つまり IASTName のスコープのみが関心対象なのです。

名前とバインディングを明確にするために、私は Hello World プログラムでの CDT の構文解析をデバッグし、図 3のようにAST を展開しました。AST には、main() 関数を表す 1 つの IASTDeclarationUnit が含まれています。CASTFunctionDeclarator は CASTName を持ち、CASTName の IBinding は CFunction です。

図 3. Hello World AST
Hello World AST

リンケージは、永続性を持つ PDOMBinding に IBinding を、そして IASTName を PDOMName に適用します。こうした新しいオブジェクトのコンストラクターは PDOM にアクセスし、オブジェクトの情報を保存します。この動作を示すためには、少し前に戻って PDOM の動作を説明する必要があります。

ステップ 4: PDOM の構造

CDT プロジェクトを作成してある人は、ワークスペース・ディレクトリーと、その下の .metadata/plugins/org.eclipse.cdt.core ディレクトリーを開いてみるとよいでしょう。そこを見ると、各プロジェクトに対して *.pdom ファイルがあるのがわかります。あるプロジェクトに対して PDOM が作成されると、PDOM は下位レベル・ストレージを管理するための Database オブジェクトを構築します。Database は新しい RandomAccessFile を構築し、それにプロジェクトの名前と、ミリ秒単位での時刻を付加します。これが、そこに見える *.pdom ファイルです。

Java I/O と Java NIO

私がこれまで見てきた大部分の Java™ 入出力ルーチンは、相変わらず Java API (application program interface) を使っています。この場合、データはバイト・ストリームで移動するため、InputStream や OutputStream、Writer、Reader などがあります。これは、パフォーマンスが重要ではない場合には問題ありません。一方 Java NIO (New I/O) API のクラスは、オペレーティング・システムと同じように、効率の良いバルク転送を使ってデータを移動します。これは小さなファイルでは大したことはありませんが、ファイルサイズがオペレーティング・システムのページ (2 KB、4 KB、8 KB など) のサイズに近づくと、大きな差を生じます。実際、Database は *.pdom ファイルを 16 KB で初期化します。

CDT では、最も重要な Java NIO Buffer は、既存の RandomAccessFile 上に作成される MappedByteBuffer です。通常のファイル・アクセスには、バッファリングやヒープ割り当て、ファイル I/O ルーチンが必要です。一方、MappedByteBuffers は仮想メモリー・コントローラーによって即座に更新され、メモリーは Java ヒープに影響を与えません。そして最後に、MappedByteBuffers はプロセス・メモリーの外にあるため、それに対して複数のプロセスが同時に効率的にアクセスできます。しかし、その動作はオペレーティング・システムに密接に結びついているため、Java I/O ルーチンよりも大きくオペレーティング・システムに依存します。

この Database は、名前以外にも通常のデータベースと多くの共通点を持っています。Database は、メモリーを 16 バイト・ブロックの可変長レコードに分割します。各レコードは、別々の PDOMNode(PDOMLinkage や PDOMBinding など) を表します。またメモリー・アクセスを実現するために、int や char、byte に対する put メソッドと set メソッドが用意されています。

Database は、ファイルの読み書きをできるだけ効率的にするために、Chunk の配列を使って *.pdom ファイルの MappedByteBuffers を管理します。Database が *.pdom ファイルを作成する際には、ファイル・サイズを 16 KB に設定し、配列の中の最初の Chunk をバッファーに割り当てます。索引のために、さらにメモリーが必要になると、Database はさらに 16 KB の Chunk を作成します。

データベースに追加される最初のオブジェクトは PDOMLinkage です。プロジェクトの中で新しい言語が使われると、それに応じて新しいリンケージが追加されます。PDOMLinkage は、そのコンストラクターがコールされると、以下を行います。

  • 初期レコード・サイズを 24 バイトに設定します。
  • ノードのタイプ (リンケージ) の表現として 0 を保存します。
  • 親ノードがないことを示すために 0 を保存します。
  • リンケージの名前を保存するために必要なメモリーのサイズを保存します。
  • メモリーを割り当て、リンケージの名前を保存します。
  • リンケージの ID を保存するために必要なメモリーのサイズを保存します。
  • メモリーを割り当て、リンケージの ID を保存します。
  • これがプロジェクトの最初のリンケージである場合には、そのレコード・サイズを特定のアドレスに保存します。それ以外の場合には、次に利用可能なアドレスを見つけ、そこにサイズを保存します。

メモリー割り当ては、Database.malloc(int size) が行います。Database.malloc(int size) はまず、要求されたメモリーを提供するために必要な最小ブロック数を判断することから始めます。もし十分なメモリーがない場合には、新しい Chunk を作成します。十分なメモリーがある場合には、メモリーを提供できる Chunk にアクセスし、必要な数のブロックをクリアーし、そして最初に割り当てたブロックの位置を返します。

このストレージ・プロセスは、他のプロジェクトの場合 (例えば、リンケージが名前付きノードを保存する動作の一部として新しい PDOMBinding を作成する場合) も同様です。もし、あるバインディングが別のバインディングのスコープ内に含まれていない場合には、リンケージは自分自身をバインディングの親として設定します。そして PDOMBinding コンストラクターは自分の初期レコード・サイズを 24 バイトに設定し、上で説明したステップの大部分を同じように実行します。

PDOMName は、これとは異なる動作をします。名前をバインディングと関連付ける方法には、3 種類あり、定義として、宣言として、または参照として関連付ける方法があります。PDOMName は、PDOMName がどの役割を演じるのかを判断すると、PDOMBinding のレコードを更新します。そして、PDOMFile (このファイルがレコードを含んでいます) の位置を、レコードの位置と長さと共に保存します。そして最後に、PDOMFile に PDOMName のブロック位置を追加することによって、このファイルの索引に中身を入れます。

PDOMNode の親子関係のため、索引はパーサーの AST に似たツリーを形成します。初めて PDOMLinkage.getIndex() がコールされると、PDOMLinkage.getIndex() は PDOM の Database とルート・ブロックの位置を使って BTree を作成します。このツリーの中を検索するには、IPDOMVisitor を使います。これは ASTVisitor と似た動作をしますが、下記の 3 つの重要な点が異なります。

  • ブール・フィールドがありません。すべてのノードに訪問します。
  • 1 つの visit(IPDOMNode node) メソッドしか使いません。このメソッドは、訪問したノードが、あるタイプかどうかをチェックします。
  • ある特定のノード・タイプに到達したときに検索を停止するための、leave(IPDOMNode node) を含んでいます。

また、DOMSearchUtil クラスに提供されている静的メソッドを使って PDOM を検索することもできます。


BBCDT の更新

私は PDOM クラスを追加しましたが、アプリケーションのサイズを考えると、もはや Bare Bones は適切ではないようです。私は、プロジェクトの索引付けのために PDOMFullIndexer しか作成しないように PDOMManager を設定したので、プリファレンスや記述子が関係することはありません。また、ASTAction を、2 つのタスクを行うように変更しました。つまり BBASTVisitor を使って IASTTranslationUnit を検索し、BBPDOMVisitor を使って PDOM を検索するようにしました。これらのクラスは、org.dworks.bbcdt.ui.action パッケージの中にあります。ASTAction をクリックした結果を図 4 に示します。

図 4. BBCDT の索引の内容
BBCDT の索引の内容

BBASTVisitor は AST を検索し、IASTName と IASTForStatement を見つけます。ループを見つけると、イニシャライザー (initializer)、条件 (condition)、繰り返し (iteration) という 3 つの表現を表示します。BBPDOMVisitor は BBPDOMVisitor の中にある関数を見つけ、その関数の数を表示します。


まとめ

構文解析や Java NIO、そして疑似データベース・アクセスなどに関しては、索引付けが複雑なプロセスであることは確かです。しかし、効率的で包括的なコード分析とストレージを提供するためには、こうした複雑さは必要なのです。

これで PDOM の説明は完了しますが、今度は CDT が PDOM をどのように応用するのかを調べる必要があります。第 5 回では、コード・コンプリーションとコンテンツ・アシストについて、その動作と PDOM 索引へのアクセス方法を含めて解説します。


ダウンロード

内容ファイル名サイズ
BBCDT code for Part 4os-ecl-cdt4.zip512KB

参考文献

学ぶために

製品や技術を入手するために

  • Eclipse CDT をダウンロードしてください。
  • IBM alphaWorks に用意された、最新の Eclipse technology downloads を調べてみてください。
  • 皆さんの次期オープンソース開発プロジェクトを、IBM trial software を使って構築してください。ダウンロード、あるいは DVD で入手することができます。

議論するために

  • Eclipse newsgroups は、Eclipse を利用し、拡張することに関心を持つ人達のために、豊富なリソースを提供しています。
  • developerWorks blogs から developerWorks のコミュニティーに加わってください。

コメント

developerWorks: サイン・イン

必須フィールドは(*)で示されます。


IBM ID が必要ですか?
IBM IDをお忘れですか?


パスワードをお忘れですか?
パスワードの変更

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


お客様が developerWorks に初めてサインインすると、お客様のプロフィールが作成されます。会社名を非表示とする選択を行わない限り、プロフィール内の情報(名前、国/地域や会社名)は公開され、投稿するコンテンツと一緒に表示されますが、いつでもこれらの情報を更新できます。

送信されたすべての情報は安全です。

ディスプレイ・ネームを選択してください



developerWorks に初めてサインインするとプロフィールが作成されますので、その際にディスプレイ・ネームを選択する必要があります。ディスプレイ・ネームは、お客様が developerWorks に投稿するコンテンツと一緒に表示されます。

ディスプレイ・ネームは、3文字から31文字の範囲で指定し、かつ developerWorks コミュニティーでユニークである必要があります。また、プライバシー上の理由でお客様の電子メール・アドレスは使用しないでください。

必須フィールドは(*)で示されます。

3文字から31文字の範囲で指定し

「送信する」をクリックすることにより、お客様は developerWorks のご使用条件に同意したことになります。 ご使用条件を読む

 


送信されたすべての情報は安全です。


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Open source
ArticleID=236843
ArticleTitle=CDT ベースのエディターを構築する、第 4 回: 高度な CDT 構文解析と Persisted Document Object Model
publish-date=10242006