マトモなXML操作クレートはどれか？

Rustの話です。

XMLのサポートを謳うクレートは数多あるのですが、その中でマトモなものはどれなんでしょうという話です。
普通に考えれば使用実績の多いクレートがマトモそうに思えるのですが、本当にそうでしょうか？

ということで、色々探してみた結果の私見です。

どうなっていれば「マトモ」か？

とりあえず周辺規格は置いておいて、XML仕様に適合しているか否かをベースに見てみることにします。
バグ起因の仕様違反は見逃しましょう。そんなものまで目くじらを立てていては、おそらく「マトモ」な実装なんてこの世にはないでしょう。明らかに処理をサボっているとかだけを対象にします。

「DTDによる妥当性検証をしないこと」は「マトモではない」わけではありません。XML仕様においても"non-validating processor"という括りでの適合性が述べられているので、実装上サボっても特に問題はありません。
ただし「DTDを読み飛ばすこと」は、その読み飛ばし方によってはマトモとは見做せません。DTDの整形式性制約を検査することや、DTDから読み取った属性宣言によって属性値を正規化することや既定値を提供すること、内部実体宣言によって実体参照を置換することは非検証プロセッサでも必須です。

とはいえ、きょう日DTDをマトモに処理できなくても困る人はあんまりいないでしょうし、整形式性制約違反の報告はともかくとして、属性値正規化や属性既定値の提供、実体参照の展開は最悪できなくても、目を瞑れる部分ではあります。

実体参照の展開を真面目にやろうとすると、まずzero-copy/zero-allocationにはなり得ません。文字参照の展開や行末正規化や属性値の正規化も、工夫すればzero-allocationにはなるでしょうが、zero-copyにはなり得ません。
zero-copyやzero-allocationを謳うクレートはこのあたりをサボっていると見てまず間違いなく、その意味で完璧に仕様適合したXMLプロセッサではないでしょう。
もちろん、私なんぞでは思いつきもしない手段でそれを達成する仕様適合プロセッサが存在する可能性もありますが。

使用実績の多いクレート

crates.ioでkeywordに"xml"を持つクレートをダウンロード数の多い順で探してみます。

https://crates.io/keywords/xml

ダウンロード数の多い順といっても、全期間のダウンロード数と最近のダウンロード数の2つの基準があります。ここでは最近のダウンロード数が多い順に並べます。

上位から独断と偏見で何個か選びますが、ここではquick-xml, xml, roxmltree, libxmlあたりを見てみましょう。
xmlparserは最終更新が3年前と古く、READMEではトークナイザであると名乗っているように見えるので外しました。
xml-rsはxmlに移行しているので、外したというかxmlを見るので十分です。
逆にlibxmlは最上位というわけでもないのですが、そこは独断と偏見です。

quick-xml

圧倒的によく使われているクレートです。とにかく速いことがウリで、またserdeによる直列化のサポート、encoding_rsによる非UTFエンコーディングのサポート、async/awaitサポートなどがあります。

パーサはStAXパーサのみが提供されていて、SAXパーサはありません。また、文書木もありません。
名前空間はサポートしているようです。パーサのオプションで切り替えるのではなく、パーサが名前空間サポート用と非サポート用で分かれています。

roxmltreeのリポジトリにベンチマーク比較用のコードが置いてあり、その中にquick-xmlも入っているのですが、群を抜いて圧倒的に速いのがわかります。
ただこの速さは整形式性制約の検査をサボることによって実現されています。つまり、XMLとして正しくない文書に対してエラーを出さないことがあります。
この中で特にパフォーマンス上顕著なのが、文字がXMLで規定された範囲に含まれるかの検査です。UTF-8のデコードは重いため、XMLプロセッサを実装する上でボトルネックになるのですが、quick-xmlは一切検査をせずに読み飛ばすため速いわけです。
結果として、quick-xmlは以下のようにXMLではないXMLっぽい文書をエラーなく通します。

use quick_xml::{Reader, events::Event};

const NOT_XML: &str = "<\0\0\0 \0\0='\0\0\0'>\0\0\0\0</\0\0\0>";

fn main() {
    let mut reader = Reader::from_str(NOT_XML);
    while !matches!(reader.read_event().unwrap(), Event::Eof) {}
}

NULL文字はXML1.0でも1.1でも、名前文字はおろか文字ですらないので、上のコードのNOT_XMLはXMLではありません。XML仕様に適合するために整形式性制約エラーの報告はMUSTであるため、この点では全くマトモではありません。
たぶん、速さに魅力を感じて使う人が多いクレートなのだと思いますが、確実に整形式であることが分かりきっているXML文書以外に使うのはおすすめしません。

ちなみに、DTDの検証もしませんし、実体参照の展開、行末正規化、属性値の正規化、属性既定値の提供も一切しません。
以上のことから考えると、XMLプロセッサというより、トークナイザに近いような気がします。

xml

もともとxml-rsという名前のクレートでしたが、v1.0.0を迎えるあたりでxmlに改称したようです。
xml-rsはv1.0.0で止まっているので、xml-rsを使っていた方はバージョンを上げる際にxmlに変更する必要があります。また、新規に採用する場合はxml-rsでなくxmlを採用するべきです。

たぶん老舗のXMLクレートなのでしょう。quick-xmlのREADMEには"Syntax is inspired by xml-rs"と書いてあるので、少なくともquick-xmlよりは以前からあったクレートだと思います。

quick-xmlと同様StAXパーサのみを提供しています。quick-xmlのパーサはIteratorを実装していませんが、xmlのパーサはIteratorを実装しているため、forでループできます。
quick-xmlはzero-copyを実現するためにライフタイムとのせめぎあいをした結果Iteratorを実装できなかった一方、xmlはイベントごとに文字列をクローンしているので、普通にIteratorを実装できます。
JAXPでいうところのStreamReaderとEventReaderの関係にあるようなものでしょうか？Javaに詳しくないので合っているかわかりませんが。

名前空間はデフォルトでサポートされていますが、無効にすることもできません。

serdeサポートや非同期サポートなどはなく、純粋にパーサ(とライタ)のみを提供するクレートです。高機能・多機能を要求するなら他のクレートを探したほうがよいかもしれません。

パフォーマンスはかなりひどいもので、先述のroxmltreeクレートのベンチマークによると、quick-xml比で数倍〜数十倍遅いです。
私が自作のXMLプロセッサのベンチ目的で数百MB程度のXMLのパース速度を比較した際は、quick-xmlと100倍近い差が開いていました。（自作のXMLプロセッサはxmlより50倍速かったです）

整形式性制約の検査についていえば、W3CのXML Conformance Test Suitesをある程度は通しているようなので、一定レベルの適合性は期待できそうです。 妥当性検証はサポートしない、とREADMEに明記されているので、妥当性検証に関するテストはスキップしているのでしょう。
非UTFエンコーディングはサポートしないとも記載があるので、EBCDICのような古いエンコーディングや、latin-1を除くISO-8859シリーズ、Shift_JISやEUC、ISO-2022シリーズに関連するテストもスキップしているでしょう。

実体参照は、内部実体のみ展開するとREADMEに記載があります。実際試してみると、正しく展開されているように見えます。
属性リスト宣言は保持しない作りになっているようなので、属性型に応じた属性値正規化や属性既定値の提供はしません。
以下のようなコードを書いて試してみると、内部実体の内容に応じて"ent"が要素として認識されますし、全属性型に共通な属性値の正規化は行われています。一方で、属性"att"の既定値は提供されていませんし、属性"id"はID型に従った属性値正規化がされておらず、空白文字が残っています。

use xml::EventReader;

const XML: &str = "<!DOCTYPE root [<!ENTITY ent1 '<ent>internal</ent>'><!ATTLIST root id ID REQUIRED><!ATTLIST root att NMTOKEN 'nmtoken'><!ELEMENT root ANY>]><root id='\troot\n'>chardata\rnewline&ent1;</root>";

fn main() {
    let reader = EventReader::new(XML.as_bytes());
    for ev in reader {
        println!("{ev:?}");
    }
}

以上のことから考えると、quick-xmlと比べるとマトモなXMLプロセッサと言えると思います。
あまりにも遅すぎることや、機能が若干貧弱なのが微妙ではあるものの、巨大文書を読むとかでなければ満足できるでしょう。

roxmltree

先程からベンチマークの話で名前が出てきているクレートですが、これはquick-xml, xmlと異なり、文書木を組み立てるパーサです。
文書の内容をすべて保持するので、巨大文書ではメモリの使用量がとんでもないことになりそうです。理論上はSAXパーサやStAXパーサと比べてその点不利ですが、quick-xmlやxmlがどういう文書ストリームの読み方をしているのかは見ていないので、それらと比べてどうなるかは不明です。

名前空間はデフォルトでサポートされており、xmlと同じく、無効にはできないように見えます。

READMEを見る限り、属性値正規化、実体参照の展開（内部・外部問わず）はできると書いてあります。
実体参照については、試してみると確かに展開できるようです。ちょっとEntityResolverの使い方がわからずめちゃくちゃになっていますが、以下のようなコードで試せます。

use roxmltree::{Document, ParsingOptions};

const EXT_ENT: &str = "<!DOCTYPE root [<!ENTITY ent SYSTEM 'ext.ent'>]><root>&ent;</root>";

fn main() {
    let doc = Document::parse_with_options(
        EXT_ENT,
        ParsingOptions {
            allow_dtd: true,
            entity_resolver: Some(&|_pubid, sysid| match sysid {
                "ext.ent" => Ok(Some("internal")),
                _ => Ok(None),
            }),
            ..Default::default()
        },
    )
    .unwrap();
    println!("{doc:?}");
}

ただ、リポジトリに置いてあるparsing.mdを読むと、DTDにおいて認識するのは実体宣言だけとのことなので、属性型に対応する属性値正規化は行われません。
上のコードのEXT_ENTの中身をxmlのコード例のXMLに置き換えて試すと分かりますが、ID型属性値の前後の空白は除去されません。
READMEの比較表ではlibxml2と同様にできるような書き方になっていますが、同等の動作にはなりません。そこは注意が必要です。

エンコーディングのサポートについてはxml以上に貧弱で、非UTFエンコーディングどころか、非UTF-8エンコーディングは一切サポートしないとREADMEに書いてあります。
XML仕様は、すべてのXMLプロセッサはUTF-8、UTF-16でエンコーディングされた実体を読み取れなければならない、と規定しているので、その点では仕様を満たしていません。

整形式性制約の遵守度合いについては、xmlのようにW3Cのテストスイートを通しているわけではないので、なんとも言えません。
quick-xmlのような、文字種の検査すらサボるということまではしていないようです。
しかし、DTDの読み飛ばしはダメなようです。マークアップ宣言であるか、それが整形式であるかのチェックをロクにせずに読み飛ばしているので、例えば以下のような文書は整形式であるにも関わらず、パースを試行するとパニックして落ちます。

const CORRECT_DTD: &str = "<!DOCTYPE root [<!ATTLIST root att CDATA '>'>]><root/>";
// mainの中身は上のコードと同じ

属性値に">"をそのまま含むのは完全に合法ですから、通らないのはダメです。もちろん、xmllintのようなツールで試せば普通に整形式文書として検査をパスできます。
割とこの手のマークアップ宣言を正しく読み飛ばしできなくて落ちる雑な実装は多くて、ついこの間までquick-xmlも同じような問題を抱えていました。

`Reader::read_event_into` panics because of incorrect DTD handling · Issue #923 · tafia/quick-xml · GitHub

この点で言えば、roxmltreeもマトモとは言い難い実装なのかもしれません。
有名所のquick-xmlやxmlが文書木構築用のAPIを持っていないので、DOMみたいな操作がしたいときには重宝するかもしれませんが、信頼できない文書をパースするのに使ってもいいのかは微妙なところです。

libxml

最後はlibxmlです。名前から察せられますが、C言語で書かれた有名なXMLライブラリであるlibxml2のRustバインディングです。

枯れに枯れきったライブラリのバインディングですので、仕様適合性という意味で言えば、上の3つのライブラリよりも断然適合性が高いです。
パフォーマンスについても、素のlibxml2はquick-xmlより2倍遅いかどうかという程度なので、全く満足できる水準だと思います。

バインディング側ではまだすべての機能を用意できているわけではないようで、XMLプロセッサのほか、XSD、XPathプロセッサは用意がありますが、XSD以外のスキーマ（RELAX NG, Schematron）やXInclude, XPointer, Catalog, C14Nなど、素のlibxml2に存在する多数の機能が使えません。

ちょっと面倒なところとしては、システムライブラリとしてlibxml2をインストールしておかないとならないことでしょう。
まあ最初の一回面倒なだけではありますが、他のクレートならcargo addするだけで済むクレートのインストールなのに、追加でシステムライブラリも用意しなければならないというのは面倒なものです。

また、ちょっと前には大元のlibxml2の主要メンテナが辞任してしまうという事件もあり、開発体制が大丈夫かという心配もあったりはしますが、現在は新しいメンテナの元ちゃんと開発が継続しているらしいと噂に聞くので、その点はたぶん大丈夫でしょう。

それ以外のクレート

ここまでは使用実績が多めのクレートから選びましたが、ここからは更に独断と偏見で数個だけ、新興のクレートから選んでみます。

私が最近気になっている、新興で実装がマトモそうなXML操作クレートはxmloxide, uppsala, fastxmlの3つあります。
どれも出てきたのはここ1年以内くらいで、libxml2並に多機能・高パフォーマンスを目指しているとともに、XML仕様への適合性にある程度気を使って実装されているように見えます。

実績アリなクレートから選ぶならlibxmlをおすすめしたいところなのですが、ピュアなRust実装がいいよ〜という場合は、この3つから探してみると幸せになれるんじゃないかなあというのが今の所の私見です。

xmloxide

libxml2を純粋にRustだけで再実装するよというのがこのクレートの目標のようです。今の時代にありがちですが、かなりAIを使い込んで実装されているらしいと聞きます。
ちなみに、xml_oxideという瓜二つの名前のクレートも存在しており、これはxmloxideとは別物です。xml_oxideのほうが昔からあるクレートですが、長いことメンテナンスされていないようです。

わざわざlibxml2_compatという名前のテストを組み込むくらいにはlibxml2との互換性に気を使っているようで、C言語側からxmloxideを使えるようなバインディングが用意され、WASMやPythonからも使えるように実装されています。
しかしlibxml2の機能だけにこだわるわけでもなく、HTML用のモジュールがHTML Living Standardに対応していたり、libxml2にはないCSSセレクタによる文書木操作もできるようになっていたりと、このクレートなりの進化も目指しているようです。

仕様適合性という点では、W3Cテストスイートをすべて通しているように見えるので、高い適合性を持っているのではないかと思われます。
これまで挙げたクレートはlibxmlを除いてすべて、妥当性検証をサポートしない実装になっていましたが、このクレートは妥当性検証においてもW3Cテストスイートを通しています。

パーサはlibxml2と同様、SAX、SAX(push type)、StAXとあり、文書木も扱えます。
注意点として、Push type SAXパーサはlibxml2のそれと異なり、外観上はメモリチャンクを少しずつパーサに読ませているように見えるのですが、その実パーサ内部で文書ストリームがすべて揃ったら初めてパースするという形になっているので、全くメモリの節約にならないどころか、メモリ無駄遣いになっている可能性すらあります。本来は、読んだチャンクをインクリメンタルにイベントに分解してパースし、パースできた部分は捨てるという形でメモリを削減するものだと思うのですが、なんでそうなっていないのでしょうか。
内部実装をちゃんと読んでいないのですが、この感じだとSAXパーサなども、文書ストリームを一旦全部かき集めてからパース開始するという、無駄な実装になっている可能性もあるのかもしれません。

ともあれ、XML仕様への適合性という点では外観上は特に文句はつけようもないですが、それ以外で気になるところをちょっと後述します。

uppsala

こちらは特にlibxml2にこだわっているというわけではなく、このクレートの作者が別で実装しているbergshamraというXMLセキュリティ？ライブラリのために実装したように見えます。
ただ、だからテキトーな実装というわけでもなく、W3Cテストスイートを通していたり、XPath, XSD, XSLTなど、真面目に実装すると重たそうな機能を実装していたりと、実用的なライブラリに仕上がっています。
ほかの2つのクレートはAIを使い込んで実装しているようですが、このクレートはそれらしい痕跡がありません。まあローカルで使っていてGitHubにそれっぽいファイルをアップロードしていないだけなのかもしれませんが。

READMEが述べるこのライブラリの特徴としては、SSE2を使用することでパース速度を底上げしている点かと思います。どの辺でそれが役に立っているのかはイマイチよくわかりませんが、quick-xmlやroxmltreeがマークアップの区切りを見つけるのにmemchrを使うのと同じノリで使っているのでしょうか。
とにかく、READMEが主張する限りでは、roxmltreeの等倍から最大9倍程度のパフォーマンス向上を成し遂げたとのことです。（本当かなあ？）

XML仕様適合性の点で気になるところがあるとするなら、たしかにW3Cテストスイートを通してはいるのですが、READMEの表によればその総数1208件とのことで、そんなにテストの件数って少なかったっけな？というのが気になります。
私の手元で試した限りでは数件スキップしても2000件弱あるはずなのですが…まあだから適合性に疑いがあるかと言われるとわかりませんが、表に書いてある「100%」とは何なのかという気になってしまいます。

そのほか、こちらも、xmloxideと同様に気になる点があるので、後述します。

fastxml

上の2つはダウンロード数の伸びからしても注目されているな〜というのがわかりますが、このクレートはそうでもないようです。
しかし、サポートする機能としては完全なXML仕様準拠、XPath, XSDサポート、非同期サポートという、特にuppsalaとは遜色ないものです。

このクレートにもfast-xmlという瓜二つの名前のクレートがありますが、別物です。
fast-xmlはquick-xmlが一時的に非公開になっていた時期にフォークして代替として作成されたクレートで、quick-xmlが復活した際に放棄されています。メンテナンスもされていません。

このクレートはStAXパーサと文書木パーサを提供しており、特にCityGMLのような巨大なXML文書においてパフォーマンスが出るように実装しているとのことです。
READMEを信用するならば、パフォーマンスは文書木パーサ、StAXパーサともにlibxml2と比べて高いということらしいです。ただ、libxml2のパフォーマンスは文書木を組む場合のみしか示されておらず、文書木を組まずに(xmllint --saxに相当)パースする場合のパフォーマンスが示されていないので、それと比べてどうなのかは不明です。

仕様適合性について言えば、このクレートもW3Cテストスイートを一定数通しており、やはり高い適合性を示しています。
ちなみに、こちらはv0.11.0現在ではPass=1691, Fail=147件となっており、計1838件のテストを実施していることになります。ますますuppsalaの1208件で100%とは？という気になります。

XML仕様適合以外の気になる点

一応今回の主題はXML仕様に適合しているかという点でマトモか？が主題なので、その点で言えばこの3つのクレートは現時点で使用実績が多いクレートと比べてもだいぶマトモという印象を受けます。
が、ちょっとそこから道を逸れて、リポジトリのソースを読んでいるなかでたまたま気になってしまった点を呟いておこうかと思います。

それはXSDへの適合性の話で、fastxmlは現在時点総数39613件のテストを実施し、うち(blockedとあるものを除き)97%通していると主張しています。実際、XSDテストスイートの総数はそんなものだったと思うので、たぶん正しいのでしょう。

一方で、uppsalaはどうかというと、21123件に対して100%と主張しています。
さらに、uppsalaはXSD 1.1をサポートしていると主張しています。XSD 1.1が1.0からどう更新されたのか、その詳細を語れるほど詳しくはないのですが、パッと見てわかる更新ポイントは組み込み型の派生構造が変わったことでしょう。anyAtomicTypeというものが組み込み原子型とanySimpleTypeの間に挟まり、dateTimeの派生型としてdateTimeStampが、durationの派生型としてdayTimeDuration, yearMonthDurationが、それぞれ追加されました。
dateTimeStamp, dayTimeDuration, yearMonthDurationを使用するスキーマをuppsalaに読ませると、そんな型はない、というエラーが出ます。それでXSD 1.1サポート、と謳うのは流石にダメじゃないのかな？と思います。読めた上で正しく検査できないとかならともかく。
そもそも通しているテストスイートも、XSD 1.1ではなく1.0用のテストスイートです。

xmloxideについていえば、libxml2への互換を目指しているとは思えないほど実装がスカスカです。
リポジトリのソースコードを読むと分かりますが、XSDの実装がテストを除き2300行ほどしかありません。libxml2の実装が3万行以上あるのに、たった2300行で実装できるわけありません。
なぜこんなに実装が軽いかというと、明らかにわかる一点は、スキーマ文書自体の検証がザルになっていることです。つまり、以下のようなスキーマ文書ではない文書を、xmloxideのXSDプロセッサは受け付けます。

<schema>
    <hogehoge/>
    <element bar="foo" name="root" type="xs:string"/>
</schema>

色々とツッコミどころはあると思いますが、XSD名前空間配下の要素ですらない謎の要素のみで構成された文書をスキーマとして受け付けます。
以下の文書も受け付けます。

<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xs:hogehoge/>
    <xs:element bar="foo" name="root" type="xs:string"/>
</xs:schema>

今度はXSD名前空間配下のスキーマっぽい要素で構成されているように見えますが、中にはSchema of Schemaで許可されない謎の要素やローカル属性が含まれており、これもスキーマとして正しくありません。こんな実装でXSDサポートを謳うのはダメじゃないでしょうか。
XSDのモジュールのドキュメントに"This module implements a subset of the W3C XML Schema Definition Language..."とも書いてあるので、フル実装ではないのは明らかですが、であればLimitationにそう記すべきと思います。

uppsala, xmloxideはこんな調子で実態と違う機能アピールが罷り通っているクレートでもあるので、個人的にはこの3つならfastxmlを推したいかなあと思う次第です。
別にXSDの実装が不十分なのが良くないわけではなく、明らかに分かっていて実装をサボっている機能をアピールしているのがちょっと気に食わないなと思いました。XSDだけじゃなくて他にもそういうのがあるかもしれませんから。
まあたまたま見つけられていないだけで、fastxmlにもそういうのがあるのかもわかりませんが…

おわりに

結論らしい結論を述べていませんが、システムライブラリをインストールすることが面倒でない、Pure Rustにこだわりがないなら、身も蓋もないようではありますがlibxmlを使うのがベストかなと個人的には思います。
Pure Rustがいい、あるいはシステムライブラリをインストールするのが億劫だと言う場合は、xmloxide, uppsala, fastxmlから選ぶのがいいかなと思います。ただ、新興ライブラリなので、プロジェクト継続性は不明なのがネックです。

他の言語には仕様をかっちり遵守するマトモなフル機能ライブラリがあるのにRustにはそういうライブラリがないというのは悲しいので、新興のつよつよライブラリにも頑張って欲しいです。
C言語のlibxml2、Java/C++のXercesのような、とりあえずこれ使っとけばいいよという信頼できる実装がほしいです。

ちなみに…

私もXML操作クレート作っています。私はかなりマトモな実装だと思っていますが、流石に自分のは本編では紹介しませんでした。

GitHub - tayu0110/anyxml: A fully spec-conformant XML library · GitHub

SAX, Push type SAX (私のクレートではProgressiveと呼びます), StAX全部あります。文書をちゃんとチャンク化して読み取るので、メモリ使用量小さいです。
ちゃんとDTDを全部読んで実体の展開、属性値正規化、属性規定値の提供、行末正規化なども全部やりますし、外部実体も読めますし、妥当性検証もできます。
UTF-8/UTF-16はもちろん、UCS4, EBCDIC, ISO-8859, EUCなどもいくらか使えます。
XPath, Catalog, XInclude, XPointer, C14N, RELAX NGも実装しました。（XPointer, C14Nはフル実装じゃないですが…）特にRELAX NG Compact Syntaxは他のクレートでサポートしているものは私の知る限りはありません。
XSDは実装中ですが、大いに苦労しているのでいつ実装終わるかわかりません…

とまあアピールポイントはこんな感じです。今の時代にあってもAIレスコーディングなので、実装に時間がかかっています。
テストスイートが存在するものについてはテストを通していますが、それでもたまにアホみたいなバグが出ることがあるので、見つけたら教えてください。

ABC467E - Adjacent Sums (hard)

たいへんひどい目に遭いました。青コーダーがABC2完とか意味不明です。
E問題に粘着し続けて解けなかった結果なのですが、なんとかコンテスト後に自力で通したので、メモです。

解説は読んでいないですが、たぶん想定解も似たような感じじゃないかなと思います。

解法

題意としては、すべてのについてとなるように任意の順序でにを足す操作を繰り返すとき、その最小回数はいくらか？ということである。

となる列を考えると、隣接する2項に1を足す、もしくは先頭・末尾に1を足すことを繰り返し、でになるまでの最小操作回数を求める問題に変わる。

ひとまず先頭に1を足す操作が許可されていることを忘れて、隣接する2項に1を足す操作と末尾に1を足す操作だけが許可されている場合に最小回数を満たす方法を考える。
これは、単純に先頭から末尾に向けて順に各項がになるように操作をするだけでよい。（ここの厳密な証明はわからなかったが、を合わせてからを合わせるとを合わせ直すのに無駄な操作が出る、ということを考えると、前に遡る操作が最適な順序に組み込まれることはなさそうだ、と考えられる）

ここで、各に対する操作回数の列を考える。なお、先頭・末尾に足す操作回数はそれぞれの先頭・末尾に付加することにする。
3つ目のサンプルを例に考えると、以下のようになる。

先頭に1を足す操作を忘れると、の総和（つまり）が解になる。しかし実際には先頭に1を足す操作があるため、それによってに起こる変化を観察する。
ここで、先頭にを足した場合のをとすると、以下のようになる。

つまり、偶数番目の項は1ずつ増加し、奇数番目は１ずつ減少することがわかる。
結果として、を変化させるにつれてその総和は

• が奇数の場合、1ずつ増加する
• 偶数番目の項がをまたぐときにだけ減少する
• 奇数番目の項がをまたぐときにだけ増加する

という形で変化することがわかる。
したがって、この動きをシミュレートしながら最小値を更新することで、解を求めることができる。

は通りあるが、それをシミュレートするのは当然間に合わないため工夫が必要である。
これはを偶数番目についてはをまたぐまでの回数、奇数番目についてはをまたぐまでの回数に変換した新たな列を考え、その小さい項から総和の差分を更新していくことによって、に改善することができる。

実装例は以下の通り。

https://atcoder.jp/contests/abc467/submissions/77651496

にあたる列が、境をまたぐまでの回数ではなくて、奇数番目を偶数番目の操作に揃えた列になっており、大きい項から見ることによって、操作回数が小さいものから見ることに代えている。

あとがき

実装例の変数名がシッチャカメッチャカですが、そこはいい感じに読み替えてください。

実装例がコンテスト後に通したコードなのですが、これの28行目の-1がなかったがばかりにWAが消えなかったわけです。言ってみれば、奇数番目がをまたぐまでの回数の算出を間違えたわけですね。ああ愚か。

解法の肝は「先頭にを足す回数を確定すればその条件下での最小回数が確定する」という点でした。つまり、が十分に小さければ、先頭にを足すことを回繰り返し、その間に操作回数を愚直に求めれば、最小値が簡単に求められます。C問題はつまりそういう問題です。
途中でその肝の部分に気づいてはいたので、E問題に粘着せずに冷静にC問題を見直していれば、容易にC問題は通せたでしょう。愚かです。

TCP/IP自作本 - Step 4

前回

TCP/IP自作本 - Step 3 - 競プロ備忘録

当初は1~2日で1Step進める計算でしたが、なんか仕事で疲れてなかなか進みません。
そんなめっちゃ忙しいわけでもないですが、体力がありません。

Step 4

この章では、IPパケットを解析、検証する仕組みを実装します。

IPパケットの中身はネスペとかのテキストで必ず出てくるのですが、ネットワークのSEを6年やっている今もまだ覚えられていません。たぶん今後も覚えることはできないでしょう。

MTUもパケットのどこからどこまでの長さを示すのか、毎回忘れます。似たようなやつにMSSというのもあるのですが、同様にどこまでを示すのか覚えられません。
改めてググってみると、MTUはIPパケットの頭から尻まで、MSSはIPヘッダとTCPヘッダを除いたペイロードの長さを示すもののようです。

この章の実装で悩ましいのは、バイト列からIPヘッダを切り取る実装でしょうか。
原作のコードでは、よくありがちな実装のようにバイト列のポインタをIPヘッダ型のポインタにキャストして切り取っています。

Rustで同じことをするなら、1つの方法としては、バイト列をtransmuteしてIPヘッダ型のスライスにキャストしてやり、ゼロ番目だけを使うようにするという方法が考えられます。
どう考えても安全ではない処理方法なので気が乗りませんが、簡単ではあります。

もう1つはbincodeクレートを使う方法でしょうか。もうすでに開発停止しているクレートなので、ちゃんとしたプロジェクトに使用するのはリスクがありそうですが、そうは言ってもこの手の処理で使用されるスタンダードなクレートなので、今回みたいなお勉強用のクレートで使うくらいは許されるでしょう。
というわけで、今回はbincodeで解析をしていこうと思います。

エンディアンの扱いも普通なら面倒なところですが、bincodeを使う場合はオプションをいい感じに付与することでバイト列をビッグエンディアンとして扱うことができます。
configモジュールを参照すると良いでしょう。

今回はやりませんが、bincodeを使わずに手でIPヘッダを組み立てることもできます。
この場合、エンディアンの扱いにはRustの整数型に組み込まれている関数を利用できます。具体的には、バイト列→整数の場合はfrom_be_bytes、整数→バイト列の場合はto_be_bytesで対応可能です。

実装は以下のとおりです。

GitHub - tayu0110/ty-microps at step4 · GitHub

bincodeをあまり使ったことがなかったので詰まりましたが、ビッグエンディアンでのデコードを設定するだけでなく、with_fixed_int_encodingというやつも設定する必要があるみたいです。
これを設定しないと、bincodeの独自ルール(?)で数値が可変長バイト列としてエンコードされているものとみなされてしまいます。これはbincodeでエンコードしたバイト列以外には役に立たないので、固定長エンコードとしてデコードするようにwith_fixed_int_encodingを設定する必要があります。

原作コードでは、構造体からの値読み出しごとにエンディアン変換やビットセットからの値抽出をしていますが、それは流石に面倒くさいのでゲッタを実装しました。
フラグのチェックを行う定数が値抽出前の16ビット値に対するマスクとして設定されていますが、それは原作に合わせておきました。

次回はStep 5をやります。

TCP/IP自作本 - Step 3

前回

TCP/IP自作本 - Step 2 - 競プロ備忘録

Step 3

この章では、ネットワークデバイスからの入力をプロトコルごとに振り分け、適切なハンドラに引き渡すような仕組みを構築します。
最終的には複数のプロトコルを扱うようになりますが、この章ではIPのみを扱います。

原作コードの大枠としては、

• net_protocol構造体にそのデータが扱うプロトコルとそれに対応したハンドラを紐付けて登録する
• ネットワークデバイスから入力があると、登録されたプロトコルのリストから適切なnet_protocolを探し、ハンドラを呼ぶ

の2つが、この章で実装する内容です。

net_protocolは、例によって連結リストによってプロトコルのリストを表現します。
これはnet_deviceの実装をRustに写したときと同様、配列で管理すれば良いでしょう。

リンクを表現するnextを除くと、net_protocolのフィールドはプロトコルの種別を表現するtypeと、そのプロトコルの入力をさばくハンドラであるhandlerだけです。
普通にこれをRustに写すだけでも特に問題はなさそうですが、これらのフィールドはおそらく初期化時に一度設定されたら再設定することはないでしょうから、トレイトオブジェクトとして実装してもそう面倒なことにはならなさそうです。具体的には、フィールドを持たないゼロサイズの構造体を用意して、typeというゲッタとhandlerというハンドラを実装するNetProtocolというトレイトを実装する形です。

悩ましいところですが、とはいえnet_protocolに後の章でフィールドを足されると厄介なことになる可能性もあるので、ここは普通にtype, handlerというフィールドを持つNetProtocolという構造体を実装することにします。

ほかの検討事項は特にないでしょう。というわけで実装してみた結果が以下のとおりです。

GitHub - tayu0110/ty-microps at step3 · GitHub

NetDevice::inputでサポート外プロトコルに対してinfoとか出さなくていいのかな？と思いましたが、ここは原作のコードに従っておきます。
一応、本文でもそこに言及はあるので、想定したとおりの処理ではあるようです。

NET_DEVICESと同じように、NetProtocolを管理するリストは今の所別のデータ構造を作るのではなく、PROTOCOLSという名前のグローバル変数でMutex<Vec<NetProtocol>>として管理しています。

相変わらず未使用の定数や構造体フィールドが多数あり、警告が出続けていますが、引き続き無視します。完走したときには警告がすべて消えているとよいのですが。

次回はStep 4です。

TCP/IP自作本 - Step 2

前回

TCP/IP自作本 - Step 1 - 競プロ備忘録

Step 2

Step 2はデバイスドライバの実装ということですが、Step 1と同様、実際のネットワークデバイスをいじるというところまでは辿り着きません。

ただ、Loopback相当の機能を実装するので、データの入出力機能が使えるようになります。
一応Linuxの機能としてLoopbackデバイスが存在するのですが、そこに何らかの方法で接続するということではなくて、我々が実装しているソフトウェア上に、入力をただエコーするだけの関数を実装する形になります。

この章でまず1つ悩ましいのは、net_device_opsの実装でしょうか。
Rust的にトレイトとして実装したいところですが、そうするとNetDeviceをデバイスの種類ごとに異なる型として実装する必要があります。それ自体は特に問題ないですが、デバイスは1つのリストで管理されているので、トレイトオブジェクトとして管理する必要があり、かなり面倒なことになります。
他に考えられるのは、デバイス種別をヴァリアントとして持つ列挙体を実装し、デバイス種別で分岐してコールバックを呼ぶ形にするのもアリかもしれません。

もう1つの悩ましいポイントは、net_deviceに追加されたprivというフィールドです。これはデバイス種別やそのデバイス自身の固有データを持つためのフィールドですが、原作のコードではvoid*として実装されています。
Rustで全く同じようなものを実装しようと思うとBox<dyn Any>を使う方法などが考えられそうです。

いずれも悩ましいポイントですが、後者はおそらくどんなデータ構造でもアリというわけではなく、サポートしているデバイスごとに決まりきったデータを格納するだけだと考えられるので、デバイス種別ごとに構造体ヴァリアントを持つようなenumを持たせるというのがいいかもしれません。
そうすると1つ目のnet_device_opsの実装もヴァリアントごとに分岐させるような感じで実装できて嬉しいです。ただ、コールバックの呼び出しごとに分岐が発生するので、パフォーマンス上嬉しくないかもしれません。まあこれは実測して確認しつつ、問題があるならリファクタリングするしかないでしょう。

コールバックはpriv相当のデータのメソッドとして実装しても良さそうですが、そうするとpriv側から所有者であるNetDeviceのフィールドにアクセスできません。
原作でのコールバックはnet_deviceへのポインタを受取りますが、同じようにNetDeviceへの可変参照を渡そうとすると、渡す可変参照とprivのメソッドのレシーバとで可変参照が2回出現してしまいます。
なので、コールバックは原作と同じように関数ポインタで保持することにします。そして、privからゲッタを通じて関数ポインタを取得します。こうすると、コールバックがNetDeviceの可変参照を受け取ることで、NetDeviceのフィールドにアクセスできますし、privのヴァリアントの構造体フィールドにもアクセスできます。

原作では、open, closeはNULLでもよいが、outputは必須ということになっています。
C言語では関数ポインタをNULLにすることができるので、outputに対するNULLチェックが必要ですが、RustではOptionでラップしない限りNULLにはできないので、そのようなNULLチェックは不要です。
open, closeはOptionでラップして、使用するときにはif let Some(...) = ...で引き剥がすようにします。

net_inputはNetDeviceのメソッドとして実装するか、独立した関数として実装するかで悩ましいところです。
net_device_outputと命名が異なるのが気になるところですが、とりあえずNetDeviceのメソッドとして実装します。不都合が出たら関数として分離します。

実装は以下のような感じになりました。

GitHub - tayu0110/ty-microps at step2 · GitHub

おおよそ上述の通りの内容になっています。

ログ用のマクロについてですが、logクレートのデフォルトのフォーマットではどのモジュールから発生したログなのかは表示されますが、どのファイルのどの関数から出てきたログなのかは表示されません。
これがちょっと不便になりつつあったので、logクレートのマクロをラップして、ファイルと行を表示させるようにしました。どの関数から発生したものかを表示させるのは難しそうだったので、それはやめました。まあファイルと行数がわかればデバッグには十分でしょう。
Rustにも__func__相当のマクロが欲しいですが、将来的に実装されることはあるんでしょうか。

マクロの定義箇所はなんかごちゃごちゃしていますが、macro_rules!のなかでmacro_rules!を使ってボイラープレートを削減しようとしたところ、macro_rules!の中で#[macro_export]をするとエラーが発生してしまったのでこうなっています。
なんで今の状態ならエラーが出ないのかはよくわからないのですが、とりあえずこれで動いているのでヨシとします。
warnマクロはそのままエクスポートしようとしたところ、warnという組み込み属性マクロがあるのでダメだと言われたのでこうなっています。よくわかりませんが、別名でマクロ定義してasで改名してエクスポートするのはセーフらしいです。

次回はStep 3をやっていきます。

TCP/IP自作本 - Step 1

前回

TCP/IP自作本 - Step 0 - 競プロ備忘録

Step 1

Step 1はネットワークデバイスの管理のお話です。
デバイス探索とかするんかなあとか思いましたが、この章では実際のデバイスを管理するところまでは行かず、管理用のデータ構造を作るところまで書くことになります。

ネットワークデバイスの呼称ですけども、私は割とNICと呼びがちな気がします。やっぱりPCIスロットに刺さっている拡張カードをイメージしてしまいます。
スイッチならインタフェースとかIFとか呼んだり書いたりしていることが多いです。

さてコードの話で、やはりこの章で一番悩ましいのはstruct net_deviceの実装方法です。

C言語のコードをRustに移植するときあるあるで、連結リストが割とどこでも使われがちで素直に移植ができなくてよく悩むものですが、今回も初っ端からその悩みにぶち当たります。

方針としては、unsafeを使ってC言語のコードを素直にそのまま書き写す、参照カウンタと内部可変コンテナでsafeに再現する、配列で代用する、などが容易に思いつきます。

後々どんな使われ方をするかわからないため、あえてunsafeで純粋な移植を書くというのはかなりアリな方針ではあるのですが、見た感じ別に連結リストであることに何か意味があるコードというわけではないと思うので、今回は配列で代用にしようかなと思います。
たぶん、net_deviceへのポインタをいろんなところで取り回すのではないかなという気がするので、それは配列のインデックスで代えましょう。

このように設計を変更すると、net_deviceをデータを直接持つ構造体と、データを直接持つ構造体をリストに収める構造体の2つに分けることが必要です。これらは適当な名前をつけて分割します。

実装した結果が以下です。

GitHub - tayu0110/ty-microps at step1 · GitHub

Rust的な命名にしたいので、net_deviceをパスカルケースに修正しています。また、いくつかの関数はNetDeviceのメソッドとして実装しています。

net_deviceのリストを格納するデータ構造を作っても良かったですが、今の所そんなに複雑な操作はないので、一旦Mutex<Vec<NetDevice>>にしています。

やはり原作コードではnet_deviceのポインタを色々取り回しています。
リストへの登録は私のコードでは所有権の明け渡しで行っているので、登録関数からインデックスを返してもらわないといけません。登録関数は原作ではゼロか-1かを返すだけなので、返り値にインデックスを乗せるように修正しました。

テストコードのいくつかの関数もやはり、デバイスの登録後にデバイスへのポインタを使い続けられる前提のコードとなっているので、ポインタ相当のインデックスを返してもらえるように修正しています。
また、デバイスへのポインタをグローバル変数で管理しているのですが、これもRustらしくはないので、引数で渡すように修正しました。

まだ使っていない関数やNetDeviceのフィールドがいくつかあるので警告は出ていますが、一応本の出力例と同じような感じで動いています。

次回はStep 2です。デバイスドライバのお話になるらしいです。

TCP/IP自作本 - Step 0

TCP/IP自作本を買いました。

発売当初からかなり気になっていたのですが、家にまだ大量の積読が残っているため購入を躊躇していました。
しかし、いつまで経っても積読が解消できる見込みもないですので、うだうだしていてもしょうもないなと思い、購入しました。

この本は、C言語でTCP/IPスタックをユーザランド上に実装しよう、というものですが、私はRustで挑戦してみます。
C言語で本の通りになぞっていくのもいいですが、これまでの経験からいえば、トラブった際に自力解決が強制されるようにしないと途中からただの写経になりがちなので、あえてC言語ではない言語で挑戦します。まあ私はRust信者なので、C言語以外で挑戦するということになると、必然的にRustになります。
ツイッターを見ている感じ、先駆者もいるみたいなので、最悪にっちもさっちも行かなくなった際は先駆者の足跡を辿ればなんとかなるはずです。

本の内容は本を読めばわかることなので、ブログではRustでの実装の様子でも書こうかなと思います。詰まったところとか工夫したところとかです。

Step 0

Step 0はTCP/IPの前提知識とか、この本で実装していくソフトウェアの概要の話です。
TCP/IPの歴史とか、いろんな書籍で説明されているのと同じようにOSI参照モデルの話とかが書いてあります。

いきなり余談ですけども、いまどきOSI由来のプロトコルは廃れていて、TCP/IPモデルが主流なわけですが、現場ではL2, L3とか言ってOSI参照モデルをベースに話が進んだりします。私はネットワーク系のSEなので、新人の頃はそういう書籍を読んで勉強してから現場に入りましたが、普通にOSIモデルめっちゃ生きてるじゃんって思ったものです。
現在でも使われているプロトコルだと、IS-ISとかはOSI由来のプロトコルらしいですね。CCNAのテキストとかではIGPだとRIP2とかOSPFが人気なイメージがあるのですが、私が実際に使われているのを見たことがあるIGPはIS-ISしかありません。

余談はここまでにして、コードを書こうと思います。

原作ではMakefileを使ってビルドを行っていますが、内容を見る限り複雑な処理はないので、build.rsは必要なさそうです。
tapデバイスを作る処理がちょっと気にはなりますが、どうやって使うのかまだ不明なので、一旦スルーして必要になったらまた考えることにします。

platform/linuxディレクトリの内容について、intr, timer, schedについてはやはりまだ使い方が不明なので、一旦スルーします。Appendixに詳細が書いてあるみたいなので、必要になったら実装することにします。
platform.cの内容はメモリ管理、ロック、乱数に関する処理ですが、メモリ管理とロックについてはRustでは標準ライブラリでカバーできますので、必要ありません。乱数についてはrandクレートを使うことにします。なのでやはり書く必要はありません。
この通りStep 0時点で書いてあるplatform.cの処理は一切不要なわけですが、platform_init, platform_run, platform_shutdownはあとで何か処理を加えて使うかもしれないので、一応ゼロを返すだけの関数として実装しておくことにします。

testの内容は書きますが、名前はtestなもののmain関数があるので、testsにテストとして収めるよりは、binに収めて実行バイナリとして扱ったほうが良さそうです。
テストの内容が明らかでないのであとで方針変更するかもしれませんが、とりあえずはbinに収めることにします。

testのコードはシグナル処理を必要としますが、Rustの標準ライブラリではシグナル処理ができません。
Rustでシグナル処理をやったことがなかったのでどうしようかなと悩みましたが、よく使われているライブラリにsignal-hookというものがあるようなので、これを使うことにします。
SIGINTしか使わない場合にはctrlcというクレートが楽に使えるらしいのですが、Step 0の時点ではそれでも問題ないものの、以降もそうなのかはわからないので、一応機能が豊富そうなsignal-hookを選択します。

utilの内容は、この章ではログ出力用関数だけが必要なようです。
基本的にはlogクレートを使おうかなと思いますが、hexdump関数は原作のutil.cの内容を元に実装します。
logクレートを使うと原作とはログの出力形式が変わってしまいますが、まあそれは妥協しようと思います。どうしても気に食わなかったらまた原作を参考に実装します。

netには今の所大した内容はありませんが、本の内容のとおりに書いていきます。

というわけで実装した結果が以下です。

GitHub - tayu0110/ty-microps at step0 · GitHub

まだ大したことはしていないので、特に何事もなく動くはずです。手元では動いています。

ロガーにはenv_loggerを使いますが、いちいち実行のたびに環境変数を設定するのが面倒くさかったので、.cargo/config.tomlで環境変数を固定しました。
こいつをいじれば、簡単にログレベルを変更できます。

次回はStep 1をやっていきます。