競技プログラミング用に、Rustのコードを単一ファイルにバンドルする #Rust

What I did

cargo-equipという、競技プログラミング用にライブラリを一つの.rsファイルにバンドルするツールを作りました。

動機

競技プログラミングで提出するコードは、外部ライブラリへの依存を持たない単一ファイルに収める必要があります。

コンテストに何度も参加していると、一から手書きするのがキツいデータ構造や、痒いところに手を伸ばすユーティリティだったりを「ライブラリ」として事前に用意しておきたくなります。そのような「ライブラリ」を極力要求しないようにしているAtCoderにおいても同様です。AtCoderでは今年から39個のRustのクレートが使えるようになりましたが、足りない機能は多いです。

しかし競技プログラミングでは通常のプログラミングのようにパッケージマネージャからライブラリを使用する、といったことができません。毎回それらを提出するファイルに含める必要があります。手でコピー&ペーストするというのが一般的な手法です。

これを自動化する方法を考えてみます。Rustには手続き型マクロのために、容易に構文木を解析, 編集, 生成することができます。手続き型マクロの要領で自動でバンドルするツールを作る、という考えは以前から持ってましたし多くの競プロRust使いも同様だったと思います。

まず思いつくのが外部クレートとして使ったライブラリを「展開」する、というものですが、これにはざっと思いつくだけでも様々な問題があります。まず各アイテムのパスを全部一段ずらす必要がありますが、Rustのモジュールの挙動は機械どころか人間にとっても非自明です。部分的な対応だけして各ファイルがちゃんと展開されるかのテストを書くようにする、という方針もありますが#[macro_export]をどうするかという問題だってあります。

次に私が考えたのはmod foo;を展開するツール、cargo-expand-modsを作り、使う際一つ一つのモジュールを#[path = ".."]で指定して使用するといったものですがこれは煩雑すぎました。

そもそもコード片を持ち込むだけならエディタかcat(1)でファイルを開き、コピー&ペーストすれば事足ります。数時間のコンテストならその手間は誤差です。

スニペットにするという方法だってあります。スニペットの管理にはcargo-snippetという優れたツールがあります。

Rustで競技プログラミングをするときの"スニペット管理"をまじめに考える(cargo-snippetの紹介) - Qiita

手持ちのコードを全部まとめてminify、するツールはまだ無いのでそれっぽく一行に圧縮したものをソースファイルのテンプレートに含めるという方法だってあります。多くの競プロプラットフォームのサイズ制限は64KiBですが、AtCoder等であれば512KiBのコードまで提出できます。AtCoderであればバイナリ提出もまだ許されています。そのためバンドルするツールの必要性は感じていませんでした。

ところが最近このようなツイートを偶然見かけました。

Rust のマクロ全然詳しくないんだけど、競プロやる上でこういうの欲しくなる。 pic.twitter.com/Z3lfJ25pP9
— 宇宙ツイッタラーX (@kenkoooo) August 29, 2020

こういう方法なら問題点が完全ではないにしろ解決するのではないか、と感じました。ダミーのアトリビュートが付いたアイテムを外部ツールで拾っていく、という方法はcargo-snippetが既にやっています。そして作ったのがcargo-equipです。

これがcargo-equipの提供する#[kore_tenkai_shitekureya]です。

src/bin/foo.rs

#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::__my_lib::{a, b::Foo, c::Bar};

cargo-equipは上のコードをこのように展開します。

use self::b::Foo;
use self::c::Bar;

pub mod a { /* `a.rs`の中身そのまま */ }
pub mod b { /* `b.rs`の中身そのまま */ }
pub mod c { /* `c.rs`の中身そのまま */ }
pub mod other_dependent { /* `other_dependent.rs`の中身そのまま */ }

使用例

"Code"の右上の"Bundle"/"Unbundle"をクリックすることで展開前/後を切り替えることができます。

ライブラリの制約

cargo-equipで扱えるライブラリには以下の制約があります。

非inline module (mod $name;)は深さ1まで
深さ2以上のモジュールはすべてinline module (mod $name { .. })
crate root直下にはmod以外のpubなアイテムが置かれていない (置いてもいいですが使わないでください)
#[macro_export] macro_rules! name { .. }はmod nameの中に置かれている (それ以外の場所に置いていいですがその場合#[macro_use]で使ってください)
#[macro_export]には組み込み以外のアトリビュート(e.g. #[rustfmt::skip])を使用しない (原理的に展開すると壊れる)

1.と2.はそのうち対応しようと思います。

このように薄く広く作ってください。

my_lib/src
├── a.rs
├── b.rs
├── c.rs
├── lib.rs
└── other_dependent.rs

my_lib/src/lib.rs

pub mod a;
pub mod b;
pub mod c;
pub mod other_dependent;

また、Cargo.tomlにモジュール間の依存関係を手で記述してください。直接useしたモジュールと、その連結成分だけを展開します。欠けている場合、warningと共にすべてのモジュールを展開します。

[package.metadata.cargo-equip-lib.mod-dependencies]
"a" = []
"b" = []
"c" = ["other_dependent"]
"other_dependent" = []

ある一つのモジュールを分割したい場合、クレートを作るときのように共通のprefixを付けたモジュールを作り、それらをre-exportしてください。(参考: num)

これらの制約により各ファイルの中身をそのまま展開できます。これにより壊れにくくなっているはず。

今のところ制約の違反を検出してエラーにする機能はありません。

展開方法

leading colonは必須です。

#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::{__my_lib::{a, b::Foo, c::Bar}};
    ^^

そうするとパスの第一セグメントは"extern crate name"だと言えるので、そこから対象がdependenciesの中のどれなのかを特定します。誤って#[cargo_equip::equip]以外で直接使わないよう、ライブラリのlib targetの名前はそのCargo.tomlか使う側のCargo.tomlの中でリネームしておくことを強く推奨します。

~~複数のライブラリの展開は未実装です。~~ 対応しました。

#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::{__my_lib::{a, b::Foo, c::Bar}};
       ^^^^^^^^

先述したライブラリの制約より、パスの第二セグメントはモジュールとみなします。これらのモジュールと、先程書いたmod-dependenciesで繋がっているモジュールが展開されます。

#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::{__my_lib::{a, b::Foo, c::Bar}};
                  ^  ^       ^

第三セグメント以降はuse self::$name::{..}と展開されます。

#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::{__my_lib::{a, b::Foo, c::Bar}};
                      ^^^^^   ^^^^^

ソースコード全体はこのように変換されます。

//! # Bundled libraries
//!
//! ## [`my_lib`]({ a link to Crates.io or the repository })
//!
//! ### Modules
//!
//! - `::__my_lib::a` → `$crate::a`
//! - `::__my_lib::b` → `$crate::b`
//! - `::__my_lib::c` → `$crate::c`
//! - `::__my_lib::other_dependent` → `$crate::other_dependent`

/*#[cfg_attr(cargo_equip, cargo_equip::equip)]
use ::{__my_lib::{a, b::Foo, c::Bar}};*/

fn main() {
    todo!();
}

// The following code was expanded by `cargo-equip`.

use self::b::Foo;
use self::c::Bar;

pub mod a { /* `a.rs`の中身そのまま */ }
pub mod b { /* `b.rs`の中身そのまま */ }
pub mod c { /* `c.rs`の中身そのまま */ }
pub mod other_dependent { /* `other_dependent.rs`の中身そのまま */ }

展開結果のチェック

展開結果をチェックするために--checkというオプションを用意しています。出力する前にcargo checkします。

$ cargo equip --check -o /dev/null
    Bundling code
    Checking cargo-equip-check-output-r3cw9cy0swqb5yac v0.1.0 (/tmp/cargo-equip-check-output-r3cw9cy0swqb5yac)
    Finished dev [unoptimized + debuginfo] target(s) in 0.18s

ただworkspaceを一時的に拡張する方法がわからなかったので、一時パッケージを作ってその上でcargo check --target-dir {元のtarget directory}する方法になりました。 (折角依存ライブラリが小さめになったのにcargoクレートを導入したくなかったので)

一応衝突を避けるため、パッケージcargo-equip-check-output-r3cw9cy0swqb5yac上でsrc/bin/cargo-equip-check-output-r3cw9cy0swqb5yac.rsを実行、ということをしています。

trybuildがどうやってコンパイルを行っているのかがわからないのですが、調べて真似できそうならそうしたいと思っています。

競プロツールとの統合

cargo-atcoderの代替品を作った - Qiita

cargo-competeの方でも提出にcargo-equipを使えるようにする設定を追加しておきました。

[submit.transpile]
kind = "command"
args = ["cargo", "equip", "--oneline", "mods", "--rustfmt", "--check", "--bin", "{{ bin_name }}"]
#language_id = ""

--bin aの代わりに--src ./src/bin/a.rsのように指定できるようにもしてあるので、他ツールとの統合もやりやすいはずです。