クレートのコンパイルとインストール

このページではAtCoderのジャッジサーバにRustの外部ライブラリであるクレートをインストールする手順を説明します。

インストールするクレートについて

今回インストールするクレートは、SlackのRust日本語コミュニティ「rust-jp」のメンバーがAtCoderでぜひ使いたいと考えているものです。大半は既存のクレートですが、この機会に新たに開発したものもあります。

これらのクレートは主に以下の種類に分類されます。

Rust の標準ライブラリにないが、他のいくつかの言語では標準の機能であって、かつ競プロ以外でも広く使われているもの
- 例：C++のlower_boundやbitsetに相当する機能
競技プログラミング特化型だが、競プロの面白さを損なわない範囲（ズルにならない範囲）で便利になるもの
- 例：Rustでは入力関連の記述が煩雑になりがちなので、それらを簡潔に記述できるマクロ集
セキュリティなどの理由から高速性が犠牲になっている機能を置き換え、特にマラソンにおいて威力を発揮するもの
- 例：標準ライブラリのハッシュ関数はDoS攻撃を避けるために暗号強度があり、計算量が多い。競技プログラミングでは暗号強度は求められず、より計算量の少ないハッシュ関数で十分

AtCoder運営者様へのお願い

対象クレートの一覧はこのページにあります。ジャッジサーバで使用して問題ない内容か、インストール前にレビューをお願いいたします。

質問や要望などがありましたら、GitHub Issueなどでご連絡ください。

インストール作業に入る前に、背景を説明します。一般的なCargoを使用した開発では、Cargo.tomlという設定ファイルに依存クレートの情報を記述します。 cargo buildコマンドを実行すると、Cargoはそれらのクレートのソースコードをダウンロードし、適切なオプションと共にrustcを実行することでクレートをコンパイルします。クレートのソースコードは$CARGO_HOME/registory/srcにダウンロードされ、コンパイル済みのクレート（rlibファイル）はCargo.tomlが置かれたディレクトリを起点とする相対ディレクトリ./target/release/deps配下に出力されます。

一般的な開発時のファイルレイアウト

$HOME   # ユーザのホームディレクトリ
|-- $CARGO_HOME (~/.cargo)
|   └-- registory
|       └-- src
|           └-- クレートのソースコード
|
└-- my-package
    |-- Cargo.toml    # 設定ファイル。依存クレートの情報が書かれている
    |-- src
    |   └-- main.rs   # Rustプログラムのソースコード
    └-- target
        └-- release
            |-- deps
            |   |-- X.rlib  # コンパイル済みのクレート
            |   └-- Y.rlib
            └-- main        # コンパイル、リンク済みの実行ファイル

ジャッジサーバーでは様々な条件が通常の環境と異なるため、最初に説明した通りいくつか工夫をする必要があります。

まず、今回は各ファイルを以下のように配置し、クレートのコンパイルは導入時に済ませておくことにします。

AtCoderジャッジサーバでのファイルレイアウト（導入時に配置するもの）

$RUST_HOME (/usr/local/lib/rust)
|-- $CARGO_HOME (/usr/local/lib/rust/cargo)
|   └-- registory
|       └-- src
|           └-- クレートのソースコード
└-- lib
    |-- Cargo.toml          # 設定ファイル。依存クレートの情報が書かれている
    └-- target
        └-- release
            └-- deps
                |-- X.rlib  # コンパイル済みのクレート
                └-- Y.rlib

そしてジャッジの際には以前説明したCargoを利用する方法とrustcを利用する方法のいずれかを利用してコンパイルします。

[cargo] AtCoderジャッジサーバでのファイルレイアウト（ジャッジの際に作成するもの）

$HOME                      # ユーザのホームディレクトリ
└-- WORKAREA               # ジャッジ用の一時ディレクトリ
    └-- lib                # 全部入りプロジェクトをまるまるコピーしたもの
        |-- main.rs        # ユーザプログラム（提出されたプログラム）のソースコードに置き換える
        |-- Cargo.toml
        └-- target
            └-- release
                |-- deps   # (外部クレートのコンパイルキャッシュ)
                └-- atcoder-rust-base # コンパイル、リンク済みの実行ファイル

[rustc] AtCoderジャッジサーバでのファイルレイアウト（ジャッジの際に作成するもの）

Cargoを使用せず、rustcに適切なオプション（ライブラリ検索パスなど）を与えて実行することで、事前にコンパイルしておいたrlibファイルとリンクさせます。

$HOME             # ユーザのホームディレクトリ
└-- WORKAREA      # ジャッジ用の一時ディレクトリ
    |-- main.rs   # ユーザプログラム（提出されたプログラム）のソースコード
    └-- main      # コンパイル、リンク済みの実行ファイル

クレートのコンパイルに使用するCargoパッケージのダウンロード

それではインストール作業に入りましょう。実際のコンパイルにCargoを使う場合もrustcを使う場合もここは同様です。クレートの事前コンパイルに使用するCargoパッケージは、GitHub rust-lang-ja/atcoder-rust-base（ja-all-enabledブランチ）に用意されています。このパッケージにはCargo.tomlファイルなどが含まれており、インストール対象のクレートがすでに設定されています。（[dependencies]セクションに書かれています）

このリポジトリをgit cloneし、/usr/local/lib/rust/libに配置します。以下のコマンドを実行します。

## rootユーザで作業する
$ sudo -i
# whoami
root

# echo $RUST_HOME
/usr/local/lib/rust

## Cargoパッケージをgit cloneする
# git clone https://github.com/rust-lang-ja/atcoder-rust-base.git \
    --branch ja-all-enabled --single-branch \
    ${RUST_HOME}/lib

クレートを削除する

検討の結果、一部のクレートは残念ながら導入すべきでないクレートだと判断されることもあるかと思います。そういった場合はGitHub Issueを通してご連絡頂ければ当該クレートとそれに関連するテストの削除等の対応をさせていただきますが、一応、その方法も説明しておこうと思います。

例えば、競プロ入出力補助のproconioが相応しくないので削除したいとなったとします。まずはこのクレートを依存から削除する必要があります。git cloneしたディレクトリ内のCargo.tomlファイルを開き、[dependencies]セクションを見つけてください。すると例えば次のようにクレートが並んでいるかと思います。

[dependencies]
# AtCoder 2019年言語アップデート以降に使用できるクレート

# 競技プログラミングの入出力サポート
proconio = { version = "=0.3.4", features = ["derive"] }

# f64のOrd/Eq実装
ordered-float = "=1.0.2"

(...以下略...)

クレートによってオプションが付せられていることもありますが、{削除したいクレート名} = ...となっている行をコメントアウトまたは削除してください。

続いてテストを削除します。src/main.rsファイルを開くと、ずらっとテスト関数が並んでいます。これらの関数からrun_{削除したいクレート名}とtest_{削除したいクレート名}という関数を丸ごと削除してください。test_{削除したいクレート名}関数は、その前の行に#[test]アトリビュートがついているかと思いますので、それごと削除してください。

そしてmain()関数内にあるrun_{削除したいクレート名}関数を呼び出す文を削除してください。

基本的にはこれで削除は完了です。この後クレートのテストを行いますが、ここでunresolved import系のエラーが出るようなら適宜削除してください。

削除するべきコードが無い場合、テストが別のファイルに分かれている場合があります。例えばjemallocator系を削除したいならばtests/test_jemallocator.rsというファイルを削除してください。

またjemallocator系を削除する場合、Cargo.toml内の以下の部分も削除してください。

[features]
jemalloc = ["jemalloc-ctl", "jemallocator"]
default = ["jemalloc"]

# 代替ヒープアロケータ。条件によってはシステムアロケータより速いことも
[target.'cfg(not(windows))'.dependencies]
jemallocator = { version = "=0.3.2", optional = true }
jemalloc-ctl = { version = "=0.3.3", optional = true }

[[test]]
name = "jemallocator"
path = "tests/test_jemallocator.rs"
required-features = ["jemalloc"]

クレートのテスト

一度、導入したクレートが正しく動作するのかを確認しましょう。

テストコードは$RUST_HOME/lib/src/及び$RUST_HOME/lib/testsにあります。先に述べたように使わないクレートに関わるコードは削除してください。実行するには、cargo testコマンドを入力します。

# cd $RUST_HOME/lib
$ cargo test --release
   Compiling atcoder-rust-base v0.1.0 (...)
    Finished release [optimized] target(s) in 7.31s
     Running target\release\deps\...

running 11 tests
test test_ascii ... okYes
Yes

test test_bitset_fixed ... ok
test test_modtype ... ok
test test_ordered_float ... ok
test test_permutohedron ... ok
test test_itertools ... ok
test test_rand_family ... ok
test test_proconio ... ok
test test_regex ... ok
test test_rustc_hash ... ok
test test_superslice ... ok

test result: ok. 11 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

多少表示されるテストの個数は異なるかもしれませんが、一番下の行がtest result: ok.で0 failed;となっていれば問題ありません。

また今回、使用するクレート自体のテストを実行するためのツール、dep-testsを作成しました。 dep-testsはcargo commandのエイリアスとして、cargo dep-testsで起動できます。ただしaliasは任意のスクリプトを実行できないのでcwdが$RUST_HOME/libである必要があります。以下、cwdを$RUST_HOME/libとします。

参考: cargo で npm-scripts 的なことをする

[alias]
dep-tests = ["run", "--manifest-path", "./dep-tests/Cargo.toml", "--"]

$ cargo dep-tests --help
    Finished dev [unoptimized + debuginfo] target(s) in 0.07s
     Running `dep-tests/target/debug/dep-tests --help`
dep-tests 0.0.0
Run all of the tests in the dependency graph.

USAGE:
    dep-tests [FLAGS] [OPTIONS] <dir>

FLAGS:
        --all-features           Activate all available features
        --no-default-features    Do not activate the `default` feature
        --frozen                 Require Cargo.lock and cache are up to date
        --locked                 Require Cargo.lock is up to date
        --offline                Run without accessing the network
    -h, --help                   Prints help information
    -V, --version                Prints version information

OPTIONS:
    -p, --package <SPEC>...         Package to run test for
        --features <FEATURES>...    Space-separated list of features to activate
        --color <WHEN>              Coloring: auto, always, never
    -d, --depth <N>                 How deep in the dependency chain to search

ARGS:
    <dir>    Directory to run tests [default: /tmp/atcoder-rust-base-dep-tests]

$ cargo dep-tests --all-features -d 1

いくつかのクレートはdep-testsで動かないのでテストしないように除外されています。そのリストと理由は$RUST_HOME/lib/dep-tests.tomlに記述されています。

dep-testsの動作の説明をしておきます。

実はcargoにはdependency graph上にあるクレートのテストをそのまま実行する機能があります。

$ cargo test -p maplit -p num

しかしこれには致命的な欠点があり、[dev-dependencies]が一つでもあると問答無用で拒否されます。

$ cargo test -p regex
error: package `regex` cannot be tested because it requires dev-dependencies and is not a member of the workspace

このエラーはrust-lang/cargo#6192で追加されました。禁止されている理由はこのPRで言及されている通り、dev-dependencyがある場合ワースクペース上には無い新たなクレートが必要になることがあるためです。 dep-testsは『拡張』したワークスペースを新たに作成してその上でテストを実行します。

例えばitertools v0.8.1, regex v1.3.1を対象にした場合、以下のようなCargo.tomlが生成されます。

[package]
name = "atcoder-rust-base-dep-tests"
version = "0.0.0"
edition = "2018"
publish = false

[workspace]
members = ["./itertools-0.8.1", "./regex-1.3.1"]

[patch.crates-io]
itertools = {path = "./itertools-0.8.1"}
regex = {path = "./regex-1.3.1"}

[dependencies]
_0 = {package = "aho-corasick",version = "=0.7.6",default-features = false,features = ["default", "std"]}
_1 = {package = "alga",version = "=0.9.2",default-features = false,features = ["default", "std"]}
# 略
_25 = {package = "itertools",path = "./itertools-0.8.1",default-features = false,features = ["default", "use_std"]}
# 略
_84 = {package = "regex",path = "./regex-1.3.1",default-features = false,features = ["aho-corasick", "default", "memchr", "perf", "perf-cache", "perf-dfa", "perf-inline", "perf-literal", "std", "thread_local", "unicode", "unicode-age", "unicode-bool", "unicode-case", "unicode-gencat", "unicode-perl", "unicode-script", "unicode-segment"]}
# 略
_107 = {package = "version_check",version = "=0.9.1",default-features = false,features = []}
_108 = {package = "whiteread",version = "=0.4.4",default-features = false,features = []}

具体的な動作は以下の通りです。

現在のdependency graph上のatcoder-rust-baseから現在のプラットフォームに適合する、normal-dependencyのみで繋がれた部分グラフを求める。そしてその節点からatcoder-rust-baseを除いたクレートを得る。またコマンドラインオプションで-d, --depthが指定されている場合さらにそのうちの一部に絞る。 -d 1を指定したならばCargo.tomlの[dependencies]にあるものだけになる。
コマンドラインオプションの<dir>で指定された場所に1.のうちdev-dependencyを含むもののためのワークスペースを一つ、以下の手順で作成する。
- 対象のクレートについて、$CARGO_HOME/registory/srcに展開されている.crateファイルの中身をコピーする。
- このコピーしたクレートをworkspace membersとしてCargo.tomlを作成する。このときダミーのdependenciesとして元のnormal-dependencyとdev-dependencyをバージョンとフィーチャを指定する。
- Cargo.lockをatcoder-rust-baseのもので上書きする。これで大体は元のバージョンが再現できる。
1.のうちdev-dependencyを含まないものはatcoder-rust-base上で直接テストを実行する。
2.で作ったワークスペース上でテストを実行する。

ワークスペースを一つにまとめることには以下の問題があり、ワークスペースを分割することで軽減できそうですがどうせ厳密なバージョン, フィーチャの保存は無理だしビルド時間と消費するディスク容量を激増させてまで分割するべきではない、と考えたため一つにまとめてしまいました。

同一の名前のpackageはworkspace memberとしては共存できない
既存のpackageのminor, patch versionの増加
オフになっていたフィーチャの有効化