LoginSignup
17
13

More than 3 years have passed since last update.

RustAdvent Calendar 2020Day 23
@qryxip

競技プログラミングにprocedural macroを持ち込む

Last updated at Posted at 2020-12-22

動機

競技プログラミングではよく $N < 10^6$個程度の値を改行区切りで出力することが要求されます。

fn main() {
    // ...

    let ans: Vec<i64> = unimplemented!();

    for ans in ans {
        println!("{}", ans);
    }
}

しかしRustのprintln!はバッファリングを行わず、毎回フラッシュされます。$10^6$個だと150msくらい持っていかれます。これは致命的ではないものの、あまり気分は良くないでしょう。

Rustで高速な標準出力 - κeenのHappy Hacκing Blog の方法で高速化してみましょう。

 fn main() {
     // ...

     let ans: Vec<i64> = unimplemented!();
​
+    use std::io::{self, BufWriter, Write as _};
+
+    let stdout = io::stdout();
+    let stdout = &mut BufWriter::new(stdout.lock());
+
     for ans in ans {
-        println!("{}", ans);
+        // 間違えて`println!`を使わないようにする。
+        writeln!(stdout, "{}", ans).unwrap();
     }
+    stdout.flush().unwrap();
 }

高速化はできましたが、間違えてprintln!を使ったら意味がありません。ifやmatchの分岐で両方使おうものなら大惨事です。println!を新しく定義してしまいましょう。

 fn main() {
     // ...

     let ans: Vec<i64> = unimplemented!();

     use std::io::{self, BufWriter, Write as _};

     let stdout = io::stdout();
     let stdout = &mut BufWriter::new(stdout.lock());

     for ans in ans {
-        // 間違えて`println!`を使わないようにする。
-        writeln!(stdout, "{}", ans).unwrap();
+        macro_rules! println(($($tt:tt)*) => (writeln!(stdout, $($tt)*).unwrap()));
+        println!("{}", ans);
     }
     stdout.flush().unwrap();
 }

安心して使えるようになりましたが、これを関数や宣言型マクロでまとめようとすると上手くいきません。このような形になってしまいます。

use std::io::{self, BufWriter, StdoutLock, Write as _};

fn main() {
    // ...

    let ans: Vec<i64> = unimplemented!();

    buffered_print(|stdout| {
        macro_rules! println(($($tt:tt)*) => (writeln!(stdout, $($tt)*).unwrap()));
        for ans in ans {
            println!("{}", ans);
        }
    });
}

fn buffered_print(f: impl FnOnce(&mut BufWriter<StdoutLock<'_>>)) {
    let stdout = io::stdout();
    let stdout = &mut BufWriter::new(stdout.lock());
    f(stdout);
    stdout.flush().unwrap();
}

このような問題にぶつかった場合、通常のプログラミングであればprocedural macroに頼りたくなることでしょう。AtCoderで使えるクレートであるproconioを使えば一行attributeを足せば高速化ができます。

+#[proconio::fastout]
 fn main() {
     // ...

     let ans: Vec<i64> = unimplemented!();

     for ans in ans {
         println!("{}", ans);
     }
 }

しかしAtCoderやCafeCoder以外ではproconioは使えません。なんとかしてprocedural macroを手元で展開できれば他のサイトでも#[fastout]のようなマクロが使えるのですが...

私はcargo-equipというRustの競プロライブラリを一つの.rsファイルにバンドルするツールを開発しています。これに条件付きでproc-macroを展開する機能を追加してみました。

手法

syn

procedural macroに使われるsynクレートとproc-macro2クレートは通常のプログラムでも普通に使用できます。

cargo-equipでは「binクレート側でマクロを使うときは#[macro_use]で使って下さい」としているのでこの制約をそのまま使いましょう。そうすると展開予定のマクロのパスは一意と考えることができるので、マクロの入出力が再現できれば後はsynクレートで適当にやるだけです。

#[macro_use]
extern crate my_proc_macros as _;

#[twice]
pub fn hello() {
    println!("Hello!");
}

↓

/*#[macro_rules]
extern crate my_proc_macros as _;*/

/*#[twice]
pub fn hello() {
    println!("Hello!");
}*/
pub fn hello() {
    hello();
    hello();

    fn hello() {
        println!("Hello!");
    }
}

watt

wattというクレートがあります。procedural macroの実装部分をWASMのライブラリとしてコンパイルしてレポジトリに含めておいて、実行時にこれを実行することにより軽量なproc_macroクレートを実現するためのライブラリです。マクロをこれで書いてしまえば楽に展開できそうです。

またcustom build内でWASMのランタイムをコンパイルするためにwattbuildというクレートを作りました。
python(.exe)を使いcache directory下でビルドするという雑なもので、ビルド時間も当然増加してしまいますが、数MB単位のバイナリをレポジトリに入れなくて良くなります。

proc_macroクレート側のAPIは適当にパースすれば(macro_rules!等が使われてない限り)なんとか取れそうではありますが、面倒なので次のようなpackage.metadataを要求します。

[package.metadata.cargo-equip.watt.proc-macro-attribute]
name = { path = "$OUT_DIR/my_macros.wasm", function = "name" }

マクロの実行

あとはcargo-equip側で.wasmファイルをwattで実行するだけですが...

     Running `/home/ryo/.rustup/toolchains/1.42.0-x86_64-unknown-linux-gnu/bin/cargo check --message-format json -p 'solve:0.0.0' --bin solve`
    Finished dev [unoptimized + debuginfo] target(s) in 0.18s
    Bundling the code
thread 'main' panicked at 'procedural macro API is used outside of a procedural macro', library/proc_macro/src/bridge/client.rs:331:17
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

はい。proc-macro2が何のためにあるのかを考えれば当然ですね。しかし困りました。wattを使わずにとなると手間がかかりそうです。

ここで考えました。出力結果を得るだけなら

  1. watt
  2. WASMのランタイム(のファイルパス)
  3. 入力のトークン列

の3つさえあれば良いのでwattbuildのときのように適当なディレクトリ内でコンパイルを走らせればwattを実行できるのではないかと。

proc_macroクレートでは普通に何でもできるので結果はファイルに出力することにしましょう。あとはproc_macroクレートとbinクレートに分けます。proc_macroクレートは再コンパイルされないようにしてopt-levelを3にしておき、binクレート側に2.と3.を入力することでwattの出力を得ます。

他のアプローチ

他にまともな手段はいくらでもあると思います。例えばrust-analyzerのマクロを扱う部分等が使えそうです。

またrustcには--pretty=expandedというnightlyでしか使えないオプションがあり、それを使ったcargo-expandというツールがあります。しかしこれはstdのマクロも普通に展開されてしまい、直接利用することが禁じられた関数等が出てきてしまいます。

fn main() {
    println!("Hello, World");
}

$ cargo +nightly expand

#![feature(prelude_import)]
#[prelude_import]
use std::prelude::v1::*;
#[macro_use]
extern crate std;
fn main() {
    {
        ::std::io::_print(::core::fmt::Arguments::new_v1(
            &["Hello, World\n"],
            &match () {
                () => [],
            },
        ));
    };
}

ただこれ、展開後の形からある程度は元のマクロの形式に戻せそうなんですよね。それができたら楽に使えてなおかつ高速だと思います。

試す

Submission Info #33434 - Library Checker

proconio v0.4のものを真似たfastoutというクレートを作りました。次のようにして試すことができます。

$ cargo install cargo-equip cargo-udeps # or downloads from GitHub Releases

$ rustup update nightly # for cargo-udeps

[package]
name = "solve"
version = "0.0.0"
edition = "2018"

[dependencies]
qryxip-competitive-fastout = { git = "https://github.com/qryxip/competitive-programming-library" }

$ cargo equip --resolve-cfgs --remove comments docs --rustfmt --check --bin "$bin_name"

競技プログラミングで使えそうなprocedural macro

競技プログラミングにおいても(binクレート側で使う)procedural macroはある程度は役に立つと思います。

@tanakhさんのargio, comprehension, memoize, interpol等のようなクレートが既にあります。

17
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
17
13