実用的なXML: パスのコンパイルとテストの自動化

ページオプション JavaScript を要するドキュメントオプションは表示されません 原文はこちら

レベル: 初級

Benoit Marchal (bmarchal@pineapplesoft.com), Consultant, Pineapplesoft

2002年 1月 01日

SAXContentHandler コンパイラー、HCの作業を続けます。今月は、コンパイル・アルゴリズムについての説明です。また、JUnitの自動化テストにも少し時間を割いています。

「実用的なXML」 の毎月のコラムにおいて、Benoit Marchalは、彼が行っているXML開発者向けのオープン・ソース・プロジェクトの進行状況を解説しています。その内容は、設計に関する決定からコーディングの課題にまで及びます。新規プロジェクトHC (Handler Compilerの頭文字) は、XPathのリストに関するSAX ContentHandlerの生成を自動化することにより、イベント・ベースのXML構文解析に付き物の単調作業を軽減してくれます。

HC (Handler Compiler) の作業を続けます。先月このコラムで紹介したHCは、SAXContentHandler の状態の追跡を行わずに済むようにすることを目的としています。状態の追跡は、退屈で、誤りが生じやすい作業です。HCはContentHandler というプロキシーをコンパイルすることにより、このプロセスを自動化します。このプロキシーは状態管理を行い、アプリケーション・ロジックが適合する場合にはアプリケーション・ハンドラーを呼び出します。

一見すると、HCはプログラマーに対してより多くの作業を要求するように見えますが、このプロキシーがアプリケーション・ハンドラーから自動的にコンパイルされることを理解することが重要です。プログラミングは必要ありません。

プロキシーのコンパイル

先月述べたように、私はこのプロキシーをコンパイルするために決定性有限オートマトン (DFA) を使用する予定です。DFAは、非常に効率が良いので、魅力的です。また、DFAを構成するためのアルゴリズムも、十分に文書化されています。私が使用する予定のアルゴリズムは、もともと、正規表現をコンパイルするために設計されたものですが、XPathsにも簡単に適用できると確信しています。

ほとんどのアルゴリズム素材は、コンパイラ - 原理・技法・ツール (参考文献を参照) から引用する予定です。同書は、コンパイラーの構成に関する解説書としては定番の1つです。この本が手元にある読者は、DFA構成はアルゴリズム3.5ですので、そこを参照してください。

アルゴリズムの基本

先月お話しした、DFAが状態遷移図であるということを思い出してください。図1 は、simpara/ulink XPathの状態遷移図を示しています。円は、プロキシーが通過する状態を表しています。矢印には、DFAの状態遷移の原因となったエレメントがラベルとして示されています。太い線の円は、XPathが正常に認識されたことを表しています。

このアルゴリズムをよく理解するために、この状態遷移図をスタックと比較してみてください。基本的に、このプロキシーはsimpara エレメントを検出すると、そのエレメントをスタックにプッシュします。次に、ulink を検出するとスタックにそれ をプッシュします。これで、スタックには、simpara とulink の2つが入っていることになります。これが、simpara/ulink の構成です。

この図に示されるさまざまな状態は、それぞれ、スタックの1つの構成を表しています。状態0は、空のスタックを表し、状態1は1つのエレメントsimpara だけのスタックを表します。状態2は、2つのエレメントsimpara とulink を含むスタックを表します。

つまり、DFAを構築するには、可能なスタック構成の数だけ状態を割り振り、それらすべての状態の間の状態遷移関数を計算する必要があります。

読者のご想像どおり、図1は単純化されすぎています。実際のプロキシーは、1つでなく複数のXPathを認識しようとするため、いくつかの状態遷移図を並列に処理することになります。たとえば、あるプロキシーが次の3つのXPathのうちいずれかを探すものとします。

simpara/ulink
/
/article/articleinfo/title

DFAがより多くのXPathを認識しようとすると、状態の数はさらに増えます。実際、スタックについて考えると、これら3つのXPathを認識するには、simpara/ulink を認識するよりも多くのスタック構成が必要になります。

QName

XMLエレメントは、ネーム・スペースURIとローカル名の組み合わせによって識別されます。このペアをより効率よく扱うために、私はQName というクラスを作成しました。XMLノードを完全に識別するために、QName はノードの性質として、エレメント、属性、またはルート (/) も記録します。QName のコードはリスト1 に示してあります。

QName は、ハッシュテーブルとの互換性を維持するためにequals() およびhashCode() をインプリメントします。

HCNode

このアルゴリズムはXPathのセットを処理し、3つのものをコンパイルします。すなわち、状態遷移図が通過する可能性のある状態のセット、ある状態から別の状態に移るための状態遷移関数、どの状態がXPathの正常な認識を示しているのかを表す標識です。

このアルゴリズムでは、フロントエンド (フロントエンドとバックエンドの詳細については、前回のコラムを参照してください) が、認識対象となるすべてのXPathを含む解析ツリーを戻すことが予期されています。リスト2 は、このツリーで表示されるエレメントHCNode です。ただし、このリストは、HC開発の現段階では未完成であることに注意してください。次回のコラムでは、より完成されたバージョンを示す予定です。

HCNode はコンパイラーに特定のものであるため、org.ananas.hc.compiler パッケージに含まれています。QName は、プロキシーで使用することを想定してorg.ananas.hc に入れておきました。

ノードは次のいずれかです (type プロパティーによって異なります)。

• QNameによって表されるXMLノード
• XMLノード間の「親」関係を示すための、XPath内の/ 区切り文字
• プロキシーが複数のXPathを認識する場合のXPathの組み合わせ
• 解析ツリーの終わりを示す特別なノード

XMLノードはQName への参照を保持します。その他のタイプのノードは、ツリーを構成するために左側および右側のHCNode への参照を保持します。

DFA構成アルゴリズムは、前回のコラムで説明したように、この解析ツリーを状態のセットに変換します。そのために、特定のノードの後にXMLノードがいくつあるのかを計算します。それぞれの状態が特定のスタック構成を表すことを覚えておくと、アルゴリズムのこの部分が理解しやすくなります。このアルゴリズムは基本的に、解析ツリー内で特定のノードに到達する可能性のある、すべてのスタック構成を計算します。

そのために、HCNode により以下のメソッドが提供されます。

• n.firstpos(): ノードn をルートとするXPathの最初のエレメントと一致するXMLノードのセット
• n.lastpost(): ノードn をルートとするXPathの最後のエレメントと一致するXMLノードのセット
• n.nullable(): ノードn が、空になる可能性のあるXPathのルートである場合には、true。それ以外の場合にはfalse。

いくつかの例を示します。最初はXPathsimpara です。このXPathを構文解析すると、XML_NODE というタイプの単一ノードn になります。XPathsimpara に一致するXMLノードはsimpara だけですので、そのn.firstpos() とn.lastpos() はsimpara になります。

XPathsimpara/ulink を構文解析すると、左側と右側のノードがそれぞれsimpara とulink を指す、PARENT_OF というタイプのノードn になります。XPathの先頭に一致するXMLノードはsimpara であり、XPathの末尾に一致するXMLノードはulink であるため、メソッドn.firstpos() はsimpara であり、n.lastpost() はulink です。

表1 は、firstpos() とnullable() を計算するための規則を表しています。lastpos() はfirstpos() に似ていますが、left とright に関する規則が逆になっています。ところで、ヌル可能とはどういうことなのかと、不審に思う読者もおられるかもしれません。これは、今後の記事で相対XPathの処理を説明することにより、明らかになるはずです。

分かりにくいと感じた場合には、状態がスタック構成を表しているということを思い出してください。firstpos() とlastpos() は、特定のスタック構成におけるXMLノードの集合です。そのうちに、これらの各集合に対し、状態に対応させるための固有の番号を割り当てたいと考えています。

DFAの計算

解析ツリーが得られると、リスト3 のアルゴリズムを適用して状態遷移関数を計算することができます。状態遷移関数は、2次元マトリックスdtran で表現することができます。このマトリックスは、XMLノードが指定されると次の状態を戻します。リスト3のアルゴリズムは実際のJavaコードではなく、疑似コードですので注意してください。

                
dstates <- root.firstpos()
for-each s as a state in dstates
for-each a as an XML node in the input vocabulary
U <- s.followpos(a)
if U is not empty and is not in dstates
dstates.append(U)
dtran[s,a] <- U

followpos(a) は、XPath内の特定のXMLノードにつながっている可能性があるノードを示します。これは、次の規則を適用して計算します。

• n がPARENT_OF ノードで、a がleft.lastpos() にあるXMLノードである場合、right.firstpos() 内のすべてのノードはfollowpos(a) 内にある。
• n が相対パスを表し、aがn.lastpos() 内にある場合、n.firstpos() 内すべてのノードはfollowpos(a) 内にある。

上に戻る

JUnit

私は、今回のコラムでこのアルゴリズムを完全にインプリメントできるものと期待していましたが、JUnitの学習にある程度の時間を割くことが必要になりました。JUnitは、テストを自動化するためのオープン・ソースのフレームワークです (参考文献を参照)。私は自分の経験から、コンパイラーを書くにはテストの自動化が不可欠であることを身にしみて感じました。

自動化されたテスト

ソフトウェア・プロジェクトにおける明らかな事実は、プログラマーが自分のソフトウェアにバグを持ち込んでしまうということです。私が目にした統計では、平均的なプログラマーは、10行のコードごとに1つバグを書いてしてしまうとのことです。バグを検出し、修正するためにテストが設計されます。テストは、反復性の高い、退屈な作業の代表的な例です。ソフトウェアのテストには、創造性を発揮する余地はきわめて少なく、特定の値を入力して結果を観察するだけです。結果が予想と異なる場合には、バグを検出したことになります。

同じことの繰り返しで退屈なテストを (少なくともある種のテストを) 自動化する必要があります。なんと言っても、コンピューターはプログラマーよりも辛抱強く出来ています。したがってコンピューターは、退屈で反復的な作業を行うにはうってつけです。

テストを自動化するということは、他のソフトウェアをテストするソフトウェアを書くことを意味します。この方法のすばらしさは、必要に応じて何度でもテスト・ソフトウェアを実行できることです。私たちはよく、アプリケーションのうちの変更個所だけをテストします。この場合、どこが変更されたのかを決めることが問題となります。コード内のあるセクションの変更が他のセクションのバグの原因となることは珍しくありません。2つのセクションが関連していることを覚えていないと、この条件を満たすテストが行われない可能性があります。

一方、自動化されたテストは、「力任せ」方式を利用します。実行のたびにアプリケーション全体をテストすることも可能ですので、コード内の無関係なセクション内のバグも検出できる機会が増えます。

自動化されたテストのもう1つの利点は、バグがアプリケーション内で再発する傾向があるという事実に対処できることです。バグを修正した場合には、そのバグを実行するテストを書くことをお勧めします。プロジェクトの存続期間中にバグが繰り返し現れて、テストが何回か失敗する可能性もあります。

Extreme programing (XP) の動向 (参考文献を参照) により、自動化されたテストが普及しました。白状すると、私は自動化されたテストをいつも使用しているわけではありません。私の経験では、自動化されたテストが最も有効なのは、共通インターフェースがあまり頻繁に変更されないクラスの場合だからです。共通インターフェースが何度も変更されるようなクラスや、多くのユーザー・インターフェース・コードを含んでいるようなクラスでは、あまり有効ではありません。

「自動化されたテスト」の中で肝心な単語は自動化 ですが、頻繁に使用するつもりがないものを自動化しても仕方がありません。頻繁に実行することが分かっているテストを書いたほうが効果的です。自動化されたテストは、ツリー操作や、特にコンパイラーなどのような、かなり難解なコードにも最適です。

JUnit

テストの自動化が苦労なしに行えるなどとは、考えないでください。テスト・ケースを作成するために時間をかける必要があり、また当然ながら、テスト・アプリケーションを定期的に実行しなければなりません。事実、自動化されたテストにあまり時間を割いていなければ、私は今月、バグだらけでテストが不十分なDFAコンパイラーのバージョンを世に出していたことでしょう。公平に言って、JUnitの学習を始めたことにより、私が自動化されたテストに割いた時間は、通常の許容限度を超えたものでした。

それでも、自動化されたテストは、プロジェクトの存続期間全体で考えれば、十分に元が取れる投資です。テストを自動化しようとするよりも、テストを実行してしまったほうが速く済みます。たとえば、特定のクラスに関するテスト・ケースを書くには、そのクラスを手作業で1度テストする場合の5倍の手間がかかるかもしれません。もちろん、テスト・ケースの作成は、そのテストを6回以上実行すれば元が取れます。テストを50回実行すると (中規模のプロジェクトでも、これは大げさな数字ではありません)、かなり得することになります。

現実的に言って、自動化されたテストを作成するには、次の2つのいずれかの戦略に従うことができます。テスト対象のコードを書くときに自分でテストを作成する方法と、別の開発者チームにテストの作成を任せる方法のいずれかです。さしあたり、私はコードを書きながら自分でテストを作ることにしますが、テスト・スイートの作成を引き受けてもよいという方は、ぜひananas-discussionメーリング・リストに書き込んでください。

かつて私は、独自のテストをプレーンJavaクラスとして作成しました。しかし、ある友人が、JUnitを試すように勧めてくれました。HCはJUnitをテストするには格好のプロジェクトと思えたので、それをダウンロードしました。JUnitは、自動化されたテストを書くための単純で小型のフレームワークです。JUnitはあまり多くのことを行いません (クラスも一握りにすぎません) が、テスト・プロセスを形式化するには役立ちます。

リスト4 は、QName を実行するために私が書いたテスト手順です。これを見て分かるように、このテスト・クラスは、JUnitで定義されたクラスTestCase から継承されています。私のテストは、testXXX() メソッドの中で書かれています。このソフトウェアのさまざまな側面を実習するために、コンストラクターのテスト、getterのテスト、そしてequals() およびhashCode() メソッドのテストの、3つのメソッドを用意しました。JUnitによって宣言されたsetUp() メソッドは、テスト・オブジェクトを初期化するものです。

これらのテストは、別パッケージ (org.ananas.hc.test) に収めました。このやり方は、JUnitの作成者の推奨に反するものです。こうした選択については、後悔することになるかもしれませんが、実際のコードとテストを分けたほうが、配布物からテストを除去しやすいと考えて、このようにしました。

JUnitを使用する利点は、テスト・クラスのロード、テストの実行、および結果の報告がフレームワークによって管理されることです。このフレームワークは、テスト・スイートの概念もサポートします。これにより、テストを論理装置内で編成できるようになります。最後に、このフレームワークはグラフィカルな実行機能とコンソール実行機能を備えています。グラフィカル・コンソールは、1つまたは2つのクラスを対話式でテストするのに適していて、コンソールは、たとえば完全な再構築の一環として、バッチ・モードですべてのテストを実行するものです。

上に戻る

次回の予定

HCのためのコードは、まだ皆さんに披露するほど整っていないため、ananas.orgリポジトリーには掲示されていません。まずDFAコンパイルを仕上げなければ、掲示するに値するものはできないでしょう。ただし、自動化されたテストの構築 (およびJUnitの学習) にかけた時間は、無駄ではないと確信しています。このプロジェクト全体を通して見れば、十分に見返りがあることでしょう。来月には、実際に動くバージョンのコンパイラーを (最適化までは手が回らないとしても) 作り上げ、プロキシーの作業に進みたいと考えています。

参考文献

• いわゆるドラゴン・ブック (「コンパイラ ー 原理・技法・ツール」A. Aho、R. Sethi、J. Ullman共著) は、コンパイラーの設計と構成に関する信頼できる書籍です。
  
  
• JUnit は、自動化されたテストのためのオープン・ソースのフレームワークです。
  
  
• Extreme programming (XP) は、より高品質なソフトウェアを実現するための推奨事項を集めたものです。
  
  
• Pragmatic Programmers でも、方法論の分野における最新の議論が行われています。
  

著者について

		Benoit Marchal氏は、ベルギーのナミュールを拠点にしたコンサルタントおよび著述家です。彼の著作には、 XML by Example(Que社、邦訳: インプレス社「実例で学ぶXML」。間もなく第2版が出版される予定です)、 Applied XML Solutions および XML and the Enterprise があります。また、Gamelanのコラムや、developerWorks XML zoneのコラムWorking XML の著者でもあります。最新プロジェクトの詳細については、www.marchal.com をご覧ください。

記事の評価

サイト改善のため、ご意見をお寄せください。こちらのフォームからお願いいたします。 この情報はお客様が目的を達成するうえで役に立ちましたか？ はい いいえ わからない   お気軽にご意見・ご感想をお寄せください。   この記事は役に立ちましたか？ 1 2 3 4 5 不充分・不完全である 大変素晴らしい

この記事を共有する del.icio.us newsing FC2ブックマーク Choix！ ニフティクリップ Yahoo!ブックマーク MM/memo CZブックマーク livedoorクリップ はてなブックマーク Buzzurl（バザール）

上に戻る