りんごがでている

何か役に立つことを書きます

EzXML.jlを作った話

Julia

先月ですが、EzXML.jlというXMLやHTMLを扱うためのパッケージをリリースしました。 EzXML.jlはlibxml2というC言語で書かれたメジャーなライブラリのラッパーなのですが、それをJuliaでラップする過程で色々と工夫がありましたので、その辺を共有したいと思います。また、パッケージの開発についても私の思うところを色々と紹介していきたいとも居ますので、これからJuliaのパッケージを作ってみようと思う方には参考になるかと思います。

何故作ったか

そもそも、JuliaにはLightXML.jlというパッケージがあり、こちらもlibxml2をラップしたパッケージでEzXML.jlと重複する部分がかなりあります。LightXML.jlはJuliaのXMLを扱うパッケージの中では最もよく使われているもので、多くの依存パッケージがあります。しかしながら、いくつか問題があり、私はこのパッケージにパッチを送るでもなく新しいパッケージを作ることにしました。

LightXML.jlで問題だと思われたものを列挙すると主に以下の様なものが挙げられます。 * APIがJuliaっぽくない * 型の設計があまりうまくない * 機能が少ない * C側で確保されたメモリーを自動的に解放してくれない

まず、APIに関してですが妙な名前の関数が提供されています。例えば、XMLファイルをパースして読み込む関数はparse_fileという何をするのか分からない名前です。Juliaではしょっちゅうusingを使ってパッケージから提供されている関数をパッケージ名を付けずに利用しますから、例えばちょっと大きめのプログラムでparse_fileという関数が呼ばれていても、これがXMLを読み込む関数だとはなかなか思えません。また、幾つかの関数名にはchild_nodesやis_elementnodeなどアンダースコアが使われていて、これもJuliaっぽい関数の命名法ではないです。例えば、Juliaの標準関数を見てみるとeachlineやhaskeyなどアンダースコアを使わない関数名が一般的で、スタイルガイドにもそのように記述されています。

型に関しても、ちょっと設計がよくない気がします。XMLのDOMモデルでは、XMLの文書中を構成する要素をノードと呼び、<element/>のような要素ノードや<!-- comment -->のようなコメントノードなど様々な種類のノードがあるのですが、LightXML.jlではそのようなノードを別々のJuliaの型でラップしています。ですので、以下のようにノードを見つけるとその種類を判別して目的の型のノードのキャストする必要があります。

for c in child_nodes(xroot)
    if is_elementnode(c)
        e = XMLElement(c)
        # ...
    end
end

これはいかにも面倒くさいですし、一度生成したオブジェクトを別のオブジェクトへキャストすることで余計なオブジェクトの生成も起きますから、パフォーマンス上もあまりよろしくないと思います。

また、libxml2は名前空間やXPathなど様々な機能を実装しているのですが、LightXML.jlから提供されているのはそのごく一部でXMLの読み書きとDOM操作だけです。それに、libxml2を通して確保したメモリー領域は、Julia側からの参照がなくなっても自動的には解放してくれないので、自分で解放しないとメモリーリークを起こします。

これらの問題を解決して快適にXMLを扱えるようにするため、EzXML.jlという新しいパッケージを開発することに決めました。

EzXML.jlの売り

EzXML.jlの売りは、その名前の通り簡単に(easy)にXMLを扱えるようにすることです。そのため、APIや型の設計をもう一度考え直し、かつlibxml2が提供する便利な機能を使えるようにしています。次のコードは、EzXML.jlを使ってXMLのツリーを辿ったり、XPathを使うデモです。

using EzXML

# Parse an XML string
# (use `readxml(<filename>)` to read a document from a file).
doc = parsexml("""
<primates>
    <genus name="Homo">
        <species name="sapiens">Human</species>
    </genus>
    <genus name="Pan">
        <species name="paniscus">Bonobo</species>
        <species name="troglodytes">Chimpanzee</species>
    </genus>
</primates>
""")

# Get the root element from `doc`.
primates = root(doc)

# Iterate over child elements.
for genus in eachelement(primates)
    # Get an attribute value by name.
    genus_name = genus["name"]
    println("- ", genus_name)
    for species in eachelement(genus)
        # Get the content within an element.
        species_name = content(species)
        println("  └ ", species["name"], " (", species_name, ")")
    end
end
println()

# Find texts using XPath query.
for species_name in content.(find(primates, "//species/text()"))
    println("- ", species_name)
end

EzXML.jlがXMLファイルを読み込むときの関数名はreadxmlです。これは、標準ライブラリにもあるreadcsvに沿って命名したものです。readという関数名はJuliaの標準ライブラリではファイルから読み込む際に使われる一般的な動詞ですので、その点でも一貫性があります。文字列からデータを読み込む場合にはparsexmlという関数名になっていて、これもJuliaではparseが文字列に対して頻繁に使われることを反映されています。ある要素の属性を取るには辞書(Dict)と同じようにelement[name]という構文が使えます。値をセットするにはもちろんelement[name] = valueと書きます。他の関数に関しても、一貫性があって一度理解すればあまりレファレンスを引かなくてもプログラミングできるようになっています。

型の設計に関してもなるべくシンプルになるようにしています。EzXML.jlが提供している型は主にEzXML.DocumentとEzXML.Nodeの2種類だけです。EzXML.DocumentはXML文書全体に対応する型で、EzXML.Nodeはその構成要素であるノードを表す型です。EzXML.NodeはXML中のノードっぽいものすべてをラップしますので、要素も、テキストも、コメントも、属性もすべてがEzXML.Nodeです。そのノードがどのような種類のノードか知るにはnodetype関数を呼びます。これらの型の名前はコード中で使われることはあまりないですから、パッケージとしてはexportしていません。しかし、必要であれば上のようにモジュール名を付けて使うこともできます。

機能もLightXML.jlより豊富です。名前空間を扱うこともできますし、XPathを使って目的の要素を検索することもできます。XPathはfindという関数をオーバーロードしていて、find(node, "//foo")とすればnodeノード以下のfoo要素をすべて取得することができます。また、メモリに乗り切らない大規模なXMLファイルを高速にパースするために、streaming readerも提供しています。

最後に、EzXML.jlはメモリリソースを自動的に解放してくれます。普通にJuliaを使っている人はメモリリソースの解放なんて気にしたくないでしょうから、自動的にやってくれれば大変楽です。なので、EzXML.jlではこの辺の面倒を見てあげることにしています。この次では、この実装がどのようになっているのかを説明していきます。

内部実装

まずはJuliaでCのライブラリーをラップする際の基本的なことを確認しておきましょう。JuliaのオブジェクトとC言語の構造体ではメモリレイアウトに互換性があります。例えば、struct point_s { int kind; double x; double y; }という構造体があれば、Julia側からはimmutable Point; kind::Cint; x::Float64; y::Float64; endのような型のオブジェクトを定義してやれば、そのメモリレイアウトをそのままJulia側に写すことができます。Cの関数からpoint_s*のようなポインタ値が返された場合は、Julia側でunsafe_load(ptr::Ptr{Point})を使ってJuliaのPointオブジェクトに変換できます。また、C言語の関数の呼び出しはccallで実現できます。

EzXML.jlでは、libxml2のノードを扱う時は以下の_Node型に写しています。これは、libxml2のどんな種類のノードも共通して持っているフィールドです。後で述べますが、最初の_privateフィールドが重要です。

immutable _Node
    _private::Ptr{Void}
    typ::Cint
    name::Cstring
    children::Ptr{_Node}
    last::Ptr{_Node}
    parent::Ptr{_Node}
    next::Ptr{_Node}
    prev::Ptr{_Node}
    doc::Ptr{_Node}
end

Juliaはオブジェクトが解放されるときに関数を呼び出す仕組み(finalizer関数)を提供しており、これを使うことでリソースの解放ができます。しかしこれは、想像するよりちょっと複雑です。何故なら、XMLのノードはlibxml2内で繋がっていますから、誤ってつながっている一部のノードを勝手に解放してしまうと、一貫性が保たれなくなってしまいます。以下のコードを見てみましょう。

function extract_first_child(filename)
    doc = readxml(filename)
    r = root(doc)
    c1 = firstchild(r)
    return c1
end

# foo.xml:
# <root>
#   <child1/>
#   <child2/>
# </root>
child = extract_first_child("foo.xml")

この関数ではXML文書中の最初の要素を返しています。関数が返った後はJuliaレベルではdocへの参照が無くなりますから、Juliaのガーベッジコレクション(GC)はdocを解放しようとします。このときにlibxml2のメモリーも解放して良さそうに思えますが、実際にはそうではありません。docが参照しているlibxml2の構造体はrを通してc1につながっていて、c1もdocへのポインターを持っています。ですので、領域を解放するには、XMLのツリーのどこにもJuliaからの参照が残っていない状態である必要があります。

f:id:bicycle1885:20161215084858p:plain

この問題を回避するために、EzXML.jlではメモリーの解放は常に特定のノードから起きるようにしています。実装上は、Node型のオブジェクトはptrというlibxml2のノードを表す構造体へのポインターと自身を管理しているownerという2つのフィールドを持っています。このownerオブジェクトが他のノードのメモリー管理を担っているオブジェクトです。

type Node
    ptr::Ptr{_Node}
    owner::Node
end

Nodeのコンストラクターの内部では、以下の様なコードを使って最上位のNodeのポインターを手繰り寄せて、そのノードのownerに指定しています。つまり、オーナーはXMLツリーの最上位にあるノードがその役割を果たします。

# determine the owner of this node
owner_ptr = ptr
while unsafe_load(owner_ptr).parent != C_NULL
    owner_ptr = unsafe_load(owner_ptr).parent
end

このownerフィールドを持つ理由は他にもあります。ownerを持つことで、GCがその子(子孫)ノードより先にオーナーを解放しようとするのを防ぐことができます。上の関数の例で言えば、c1がdocへの参照をJuliaのレベルで保持しているため、c1がある限りdocが先に解放されることはありません。さらに途中に挟まれているrは自身や他のノードのオーナーではないので、JuliaはrをGCするときにlibxml2で確保されたメモリー領域を解放しません。こうして、常にノードは最上位のノードへの参照を持ち、最上位のノードがメモリーを解放することにして、誤ってGCされるのを防いでいます。

しかし実は、もうひとつ考えなければいけない問題があります。それは、Julia側からあるlibxml2のノードに対して複数の参照を作ってしまうことです。以下の様な簡単なコードを考えてみると、すぐに問題が分かります。

doc1 = readxml("foo.xml")
doc2 = document(root(doc1))

このとき、単純に実装するとdoc1とdoc2はlibxml2の同じノードを指しているのに別々のJuliaオブジェクトになっています。すると、あるノードの対して2つのオーナーが存在することになり、両者が最終的に同じノードを解放しようとして後のほうが不正な操作になります。

この問題はlibxml2のノードの構造体にJuliaオブジェクトへのポインターを保持することで解決しています。既に述べたように、libxml2のノードの構造体には_privateと呼ばれるフィールドがあり、ユーザーが自由に使うことができます。そこで、このフィールドにJuliaのNodeオブジェクトに対するポインターを保持しておき、あるノードに対するJulia側のNodeオブジェクトを作る際には、もしあればここからオブジェクトを取り出しています。つまり、既にJulia側であるノードに対するオブジェクトを作成していればそれを使い、無ければ新しく作ってポインターをノードの保持しておくという操作をNodeのコンストラクター内で行っています。こうすることで、あるlibxml2のノードに対するJulia側のNodeオブジェクトは常に高々1個になり、二重に領域を解放してしまうことを防ぐことができます。

最終的に、Nodeのコンストラクターは以下の様な感じになります(実際のコードを少し簡略化しています)。 CのポインターからJuliaのオブジェクトを取り出すのがunsafe_pointer_to_objrefで、Juliaのオブジェクトのポインターを取得するのがpointer_from_objrefです。

function Node(ptr::Ptr{_Node})
    # return a preallocated proxy object if any
    str = unsafe_load(ptr)
    if str._private != C_NULL
        # found a valid proxy
        return unsafe_pointer_to_objref(str._private)::Node
    end

    # find the owner of this node
    owner_ptr = ptr
    while unsafe_load(owner_ptr).parent != C_NULL
        owner_ptr = unsafe_load(owner_ptr).parent
    end

    if ptr == owner_ptr
        # manage itself
        node = new(ptr)
        node.owner = node
    else
        # delegate management to its owner
        owner = Node(owner_ptr)
        node = new(ptr, owner)
    end

    # register finalizer and store the pointer to a node object
    finalizer(node, finalize_node)
    unsafe_store!(convert(Ptr{UInt}, ptr), convert(UInt, pointer_from_objref(node)))

    return node
end

finalize_nodeは自身がオーナーである場合は、それ以下の管理するノードにつながっているJuliaのオブジェクトを切り離し、libxml2の関数を呼んでノードを解放しています。もしオーナーでなければ、_privateにNULLポインターを代入して、JuliaのオブジェクトがGCされてもう存在しないことを示しています。

# Finalize a Node object.
function finalize_node(node)
    node_ptr = node.ptr
    if node === node.owner
        # detach pointers to C structs of descendant nodes
        traverse_tree(node_ptr) do ptr
            str = unsafe_load(ptr)
            if has_proxy(str)
                # detach!
                unsafe_extract_proxy(str).ptr = C_NULL
            end
        end
        # free the descendants
        if unsafe_load(node_ptr).typ == DOCUMENT_NODE
            ccall((:xmlFreeDoc, libxml2), Void, (Ptr{Void},), node_ptr)
        else
            ccall((:xmlFreeNode, libxml2), Void, (Ptr{Void},), node_ptr)
        end
    elseif node_ptr != C_NULL
        # indicate the proxy does not exit anymore
        store_proxy_pointer!(node, C_NULL)
    end
    return nothing
end

以上で、EzXML.jlの大まかな内部実装がお分かりになるかと思います。実際には、サブツリーを別のツリーへと動かす際にはオーナーをアップデートする必要があるなど細かい処理が多少あるのですが、そのへんまで興味ある方は元のコードを読んでみて下さい。まだ新しいパッケージですので、使ってみてバグや提案などがある場合は報告して下さい。