JavaのDOM処理を読む

はじめに
DocumentBuilderFactory
DocumentBuilderImpl
Parser2, XmlDocumentBuilder
ParentNode
おわりに

はじめに †

JavaでDOM処理を行う場合、

DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
DocumentBuilder builder = factory.newDocumentBuilder();
Document doc = builder.parse(new File(xmlFile));
Element elem = (Element)doc.getElementsByTagName(tagName).item(0);

のように記述します。SDKドキュメントを見るとDocumentBuilderFactoryとDocumentBuilderは抽象クラス、DocumentやElementはインターフェースであることがわかります。では実際に処理を行っているのは誰なのでしょうか？今回はここら辺のからくりを読み解きたいと思います。

↑

DocumentBuilderFactory †

まずDocumentBuilderFactoryについて見ていきましょう。 newInstance()の動作はSDKドキュメントに記述されています。newInstance()ではDocumentBuilderFactoryを実装するクラスをいろいろな方法で探しているようです。JavaではこのようにAPIだけ定義しておいて実際の処理を行うクラスはプロパティで切り替えられるようにしておくという方式がよく用いられています。

では最後のデフォルトのDocumentBuilderFactoryインスタンスって何者でしょうか？ソースを見ると

public static DocumentBuilderFactory newInstance() {
  return (DocumentBuilderFactory) FactoryFinder.find(
    /* The default property name according to the JAXP spec */
    "javax.xml.parsers.DocumentBuilderFactory",
    /* The fallback implementation class name */
    "org.apache.crimson.jaxp.DocumentBuilderFactoryImpl");
}

となっています。つまりcrimsonがデフォルトのDocumentBuilderFactoryとして利用されていることがわかります。それではcrimsonがどのようにDOMを実装しているか見ていきましょう。

↑

DocumentBuilderImpl †

ソースを見るとnewDocumentBuilder()の実装は単純に新しいDocumentBuilderImplを作っているだけなことがわかります。次にDocumentBuilderImplのコンストラクタを見てみるとxmlReader(XMLReaderImplオブジェクト)のセットアップ、builder(XmlDocumentBuilderオブジェクト)のセットアップが行われていることがわかります。xmlReaderの各種ハンドラにbuilderを設定しているところからxmlReaderとbuilderが協調してDOMが構築されているのだろうと想像できます。実際にparse()のソースを見てみると、

xmlReader.parse(is);
return builder.getDocument();

となっており、XMLの読み込みが終わった時点でDOMが構築されていることがわかります。

↑

Parser2, XmlDocumentBuilder †

XMLReaderImpl.parse()を見てみると実際の処理はParser2が行っていることがわかります。で、Parser2を見てみると3000行以上あって読む気がなくなってくるのですが何をやっているかというとXML仕様に基づいてXML文書をparsingしているだけです。今回の目的であるDOMの構築で重要なのは真ん中ぐらいにあるmaybeElement()の

contentHandler.startElement(parts[0], parts[1], parts[2], attTmp);

です。これによりXmlDocumentBuilderにElementの情報が渡されます。

ではElement情報を受け取ったXmlDocumentBuilderが何をしているかというと以下のような処理をしています。

e = (ElementNode) document.createElementEx(qName);
elementStack[topOfStack++].appendChild(e);
elementStack[topOfStack] = e;

つまりElementが見つかるたびにElementをスタックに積んでいます。また、endElement()が呼ばれると一番上の要素が下ろされます。スタックを下ろされた時点でそのElementの構築は完了しています。なお、elementStackの一番下(topOfStack = 0)にはXmlDocumentオブジェクトが置かれています。

コードだけだとイメージがつかみにくいので簡単なXMLで動作をトレースしてみましょう。

<root>
  <foo>
    <bar>baz</bar>
  </foo>
  <hoge>huga</hoge>
</root>

こんな感じなXMLがあったとすると、

elementStack[top] => document
document.appendChild(root)
elementStack[top] => root
root.appendChild(foo)
elementStack[top] => foo
foo.appendChild(bar)
elementStack[top] => bar
elementStack[top] => foo
elementStack[top] => root
root.appendChild(hoge)
elementStack[top] => hoge
elementStack[top] => root
elementStack[top] => document

とスタックが成長していきます。

↑

ParentNode †

さて最後にgetElementsByTagName()がどのように実装されているか見てみましょう。そのためにはまずdocument.createElementEx()でどのオブジェクトが作られているかを見る必要があります。

if (factory != null) {
  // Ask factory to create appropriate ElementNode subtype
  retval = (ElementNode) factory.createElementEx(tagName);
  // Set the name of the ElementNode
  retval.setTag(tagName);
} else {
  retval = new ElementNode(tagName);
}

まあ多分ElementNodeの方が作られてるでしょう。次にElementNodeを見てもgetElementsByTagName()は定義されていないのでスーパークラスをElementNode2 -> NamespacedNode -> ParentNodeとたどっていくとParentNodeで定義されていることがわかります。

ParentNode.getElementsByTagName()を見ると内部クラスであるTagListを作成して返していることがわかります。では次にTagList.item()を見てみましょう。前半部分はとりあえず置いといてiで指定されたElementを取得しているのは次の箇所

while (i > lastIndex
  && (node = lastWalker.getNextElement (tag)) != null) {
  lastIndex++;
}

lastWalkerはTreeWalkerオブジェクトです。TreeWalker.getNextElement()(正確にはgetNextElement()が呼んでるgetNext())ではDOMツリーをトラバースすることで指定のタグ名を持つElementを返しています。*1

最後に、何故getElementsByTagName()が呼ばれたときにElementリストを作ってしまわないかについて考えたいと思います。item()の前半部分ではmutationCountというものを取得しその値と前回のmutationCountが等しいかどうか調べ、等しくないならツリーを先頭からトラバースするようにしています。これはDOMでは動的に要素の追加・削除ができるためgetElementsByTagName()が呼ばれた時点でのElementリストとitem()が呼ばれた時点のElementリストが一致しない可能性があるためでしょう。

↑

おわりに †

今回はJavaのDOM処理の実装を見てみました。これにより実行時に利用する実装を切り替える方法、インターフェースに対する実装の提供方法を学ぶことができました。それではみなさんもよいコードリーディングを。