search

online-judge-tools / verification-helper

a testing framework for snippet libraries used in competitive programming
MIT License
225 stars 54 forks source link

Rust 対応 #113

Closed kmyk closed 3 years ago

kmyk commented 4 years ago

親 issue: #116

Rust は必要だろ

kmyk commented 4 years ago

cc: @yosupo06 @fukatani

kmyk commented 4 years ago

@niuez https://github.com/niuez/cp-rust-library https://github.com/niuez/rust-data-structures

kmyk commented 4 years ago

あまり交流ないけどこの前おもしろいもの作ってたし @tanakh

qryxip commented 4 years ago

私のアイディアを書いておきます。 これを書くにあたりrust-jp.slack.comでアドバイスを貰いました。

compile, get_executable_command

$ rustup run "$VERSION" rustc "$EDITION_OPTION" -C "opt-level=$OPT_LEVEL" -o "$BIN" "$SRC"

ただし$BINは"$(cargo metadata --format-version 1 | jq -r .target_directory)/release/examples/$(basename "$SRC" .rs)"、$EDITION_OPTIONは""、$OPT_LEVELは"2"で

list_attribute

良くわからないのですがMarkdown生成用のと一緒にmodule docにdoxygen形式で書くようにするのでは駄目でしょうか。 あとはこういう方法しか思い浮かばないです。

//! ```json, online-judge-verify-helper
//! {
//!   "foo": 42
//! }
//! ```

list_dependencies, bundle

Rustのmodは構文解析時にファイルの中身がそのまま展開されます。

mod foo;

↓

mod foo {
    {{./foo.rsまたは./foo/mod.rsの中身。 両方がある、または両方無いとエラー}}
}

このとき#[path = ".."]を付けることでマウントする対象を指定することができます。

#[path = "path/to/foo.rs"]
mod foo;

これでmainのやつの上で必要な分だけpath指定したmodをマウントするのがいいんじゃないかと思います。 ↓の例だとmy_complibがlib crateとしてビルドされますがそれは無視します。 『lib crateとしての利用』 → 『直に埋め込んでの利用』の変換をやろうとすると恐らく地獄が発生しそうです。 そもそもあまり嬉しくもないでしょうし。

またCargoでビルドすると./target下に.dが生成されますがこの例でのznz/thread_local.rsとかを排することはできないようです。

で、bundleはと言うと少しだけ面倒が発生する可能性があります。 #[path = "path/to/foo.rs"] (pub) mod foo;または(pub) mod foo;を置換する必要があるのですがこれを一発でやるツールはありません。 (マクロごと展開するのはあるけれどstd::println!のようなstdのマクロも展開して、マクロ越しにしか呼んじゃ駄目な関数等が出現する)

またファイルを辿ってインデントもかける必要もあります。 インデントについては最後にrustfmt (公式フォーマッタ。 今Rustをインストールするともれなく付いてくる)をかけるのでいいんじゃないかと思うのですが競プロerにおいてはrustfmtを使うのは一般的ではないようです。 私なんかはVimキーバインドのnormal modeでのESCでフォーマッタがかかるようにしてますがそんなことをしている人は少数でしょうし面倒であるだしゆえに馴染みが無いというのは理解できます。

Rustでcargo-expand-modsみたいなのをサッと実装するという手もありそうです。

// my_complib
// ├── examples
// │   └── problem.rs (このファイル) (num_traits.rs, znz/*.rsに依存)
// └── src
//     ├── lib.rs (`mod`以外のアイテムを含まない)
//     ├── num_traits.rs
//     ├── unrelated.rs (problem.rs上にマウントされない)
//     └── znz
//         ├── constant.rs (num_traits.rs, znz/implementation.rsに依存)
//         ├── implementation.rs (num_traits.rsに依存)
//         ├── mod.rs (znz/constant.rs, znz/implementation.rsに依存)
//         └── thread_local.rs (num_traits.rs, znz/implementation.rsに依存。 problem.rsには使われていないはずだがそこは諦める)

fn main() {
    assert_eq!(*(Z::new(1_000_000_006) + Z::new(2)), 1);
}

decl_znz!(Z = Znz<u64, 1_000_000_007>);

//#[path = "../src/num_traits.rs"]
//mod num_traits;
//#[path = "../src/znz/mod.rs"]
//mod znz;

// ↓ 展開

mod znz {
    //! _ℤ/nℤ_

    pub(crate) mod constant {
        //! Represents _ℤ/nℤ_ where _n_ is a **constant value**.

        use crate::num_traits::PrimInt;
        use crate::znz::implementation;

        use std::marker::PhantomData;
        use std::ops::{Add, Deref};

        #[macro_export]
        macro_rules! decl_znz(($name:ident = Znz<$ty:ty, $modulus:literal>) => {
            type $name = crate::znz::constant::Znz<$ty, __Modulus>;

            enum __Modulus {}

            impl crate::znz::constant::PseudoConst for __Modulus {
                type Value = $ty;
                const VALUE: $ty = $modulus;
            }
        });

        pub(crate) trait PseudoConst {
            type Value: Copy;
            const VALUE: Self::Value;
        }

        /// Represents _ℤ/nℤ_ where _n_ is a **constant value**.
        pub(crate) struct Znz<R, M> {
            repr: R,
            phantom: PhantomData<fn() -> M>,
        }

        impl<R: PrimInt, M: PseudoConst<Value = R>> Znz<R, M> {
            pub(crate) fn new(val: R) -> Self {
                Self {
                    repr: val % M::VALUE,
                    phantom: PhantomData,
                }
            }
        }

        impl<R, M> Deref for Znz<R, M> {
            type Target = R;

            fn deref(&self) -> &R {
                &self.repr
            }
        }

        impl<R: PrimInt, M: PseudoConst<Value = R>> Add for Znz<R, M> {
            type Output = Self;

            fn add(self, rhs: Self) -> Self {
                Self::new(implementation::mod_add(*self, *rhs, M::VALUE))
            }
        }
    }

    pub(crate) mod thread_local {
        use crate::num_traits as _;
        use crate::znz::implementation as _;

        //
    }

    pub(super) mod implementation {
        use crate::num_traits::PrimInt;

        pub(super) fn mod_add<T: PrimInt>(lhs: T, rhs: T, modulus: T) -> T {
            (lhs + rhs) % modulus
        }
    }
}

mod num_traits {
    //! Pseudo `num-traits`.

    use std::ops::{Add, Div, Mul, Rem, Sub};

    pub(crate) trait PrimInt: Copy + NumOps + EtcEtc {}

    impl PrimInt for u8 {}
    impl PrimInt for u16 {}
    impl PrimInt for u32 {}
    impl PrimInt for u64 {}
    impl PrimInt for u128 {}
    impl PrimInt for usize {}
    impl PrimInt for i8 {}
    impl PrimInt for i16 {}
    impl PrimInt for i32 {}
    impl PrimInt for i64 {}
    impl PrimInt for i128 {}
    impl PrimInt for isize {}

    pub(crate) trait NumOps<Rhs = Self, Output = Self>:
        Add<Rhs, Output = Output>
        + Sub<Rhs, Output = Output>
        + Mul<Rhs, Output = Output>
        + Div<Rhs, Output = Output>
        + Rem<Rhs, Output = Output>
    {
    }

    impl<T, Rhs, Output> NumOps<Rhs, Output> for T where
        T: Add<Rhs, Output = Output>
            + Sub<Rhs, Output = Output>
            + Mul<Rhs, Output = Output>
            + Div<Rhs, Output = Output>
            + Rem<Rhs, Output = Output>
    {
    }

    pub(crate) trait EtcEtc {}

    impl<T> EtcEtc for T {}
}
qryxip commented 4 years ago

cargo-expand-mods、サッとはいきませんでしたがとりあえず作りました。 テストも書いてませんが上のコードの例ではちゃんと展開されました。

$ tokei
-------------------------------------------------------------------------------
 Language            Files        Lines         Code     Comments       Blanks
-------------------------------------------------------------------------------
 Markdown                1           53           53            0            0
 Rust                    1          267          220           14           33
 TOML                    1           23           22            0            1
-------------------------------------------------------------------------------
 Total                   3          343          295           14           34
-------------------------------------------------------------------------------
kmyk commented 4 years ago

これどうなったんだろう。誰かプルリクを出してほしい

qryxip commented 4 years ago

とりあえずこれを片したついでに試したらrust-analyzer (rls-2.0として開発されているlanguage server)がこんなことに..

rust-analyzer3

「#[path = ".."]はサポートされているはずでは?」と思って色々試したら

rust-analzyer

こういうことみたいなのでライブラリはworkspace内(正確にはworkspace_directory下)に入れとく必要があるっぽいですね。 一応ライブラリに関する補間及びhover docが一切効かないのと画面が赤くなる以外に実害はありませんが。 RLSはどうなのかな.. 前は大丈夫だった気がするしとりあえずrust-analyzerにissue立てられそうなら立ててきます。

qryxip commented 4 years ago

「前は大丈夫だった気がする」というよりも

// my_complib
// ├── examples
// │   └── problem.rs (このファイル) (num_traits.rs, znz/*.rsに依存)
// └── src
//     ├── lib.rs (`mod`以外のアイテムを含まない)
//     ├── num_traits.rs
//     ├── unrelated.rs (problem.rs上にマウントされない)
//     └── znz
//         ├── constant.rs (num_traits.rs, znz/implementation.rsに依存)
//         ├── implementation.rs (num_traits.rsに依存)
//         ├── mod.rs (znz/constant.rs, znz/implementation.rsに依存)
//         └── thread_local.rs (num_traits.rs, znz/implementation.rsに依存。 problem.rsには使われていないはずだがそこは諦める)

踏まなかっただけですね..

qryxip commented 4 years ago

これ、自力でなんとかしている人を発見しました。 RLS (RustのLSP serverの前世代のもの)をforkし、Nightly Rust限定の機能であるsave-analysisから大雑把なローカルの依存関係を読み出しています。

その人のTwitterを検索したら

酷いハックをかましているので本家にパッチ送れるようなアレではないが…

とのことですが...

qryxip commented 4 years ago

実際見てもメンテの手間が間違いなく全言語中最大になりそうな感じではありますが一応参考として。

kmyk commented 4 years ago

記録用 @shino16

kmyk commented 4 years ago

記録用2 @MiSawa

https://github.com/MiSawa/ralgo

kmyk commented 4 years ago

本体側に Rust のコードを同梱しちゃうとメンテコストが爆発してつらいと思うけど、依存関係解析や単一ファイル化などをすべて Rust で書いて crate などとして公開してもらって、oj-verify からはそれをプラグインとして叩くだけというのはかなりあり。 MiSawa/ralgo は「酷いハック」と言うから oj-verify 側に影響範囲の広いパッチ当ててるのかなと思ってたけど、他の言語と同じ標準のインターフェースに乗る形になってて、かなりきれいに見える。「Rust の unstable な機能を使ってる」とかぐらいなら (メンテできる人の確保さえできれば) 特に問題ないはず。

(なお私は Rust の crate を作るとかは分からないので作業はできません。依然としてプルリク待ちです)

qryxip commented 4 years ago

bundleの方をやるにあたって重要だと思っているのが

  1. Clippy (静的エラー表示ツール)が動くか
  2. rust-analyzer (保管やインテリセンスをやるLSPサーバー)が動くか
  3. bundleした状態で動くか
  4. 当然であるがエディタやcatで開いてコピー&ペースト、よりも手間が少ない

で、私のcargo-expand-modsだと4.が駄目で2.も怪しいという惨状だったので諦めたのですが最近1..4を満たす方法をもう一つ思い付きました。この方法だとcargo-expand-modsのときと同じく、各アイテムのパスを探し回って変更する必要がありません。

[dependencies]
__complib__ = { package = "complib", path = "../complib" } # 誤って`complib`を直接使わないようにリネーム
dummy_attribute = "1.0.0" # ダミーのためだけのproc-macroをCrates.ioに上げておく
// `mod`の深さは最大1という規約でライブラリを書く
#[dummy_attribute::use_competitive_library("complib")]
pub use __complib__::{algebra, fenwich};

↓ ツールで変換

pub mod fenwick {
    pub use crate::algebra;
    pub use crate::numeric;

    //
}

pub mod algebra {
    pub use crate::numeric;

    //
}

pub mod numeric {
    //
}

依存関係は最悪手で書けますし、この方法ならmain.rs → ライブラリの各modの依存は自然な形で手で書けます。

cargo-oj-bundle (?)もちゃんと動きそうに見えるのですが、個人的に相対パスやマクロを普通に使えた方が良いんじゃないかと考えてしまいます。

(なお「コードに表われる相対パスを一つずつずらす」アプローチで、それを真面目にやろうとすると面倒どころではなく地獄だと思います)

Rustのモジュールを詳細に理解する(4) インポート解決

shino16 commented 4 years ago

ここのissueの存在に今気が付きました…　先にこちらを確認すべきでしたね。

このようなツールを今日作りました。テストが不十分なため期待される動作が正しくできているかも怪しいのですが、README.mdにあるような機能は実現できたと思っています。

https://github.com/shino16/cargo-auto-bundle

相対パスは近いうちに対応したいです…　仕様に厳密に沿うことは最初からあきらめていて（いずれにせよ不可能）、よくある使い方にだけ対応できればよいかと思っています。

shino16 commented 4 years ago

もともとonline-judge-toolsのことを考えて作ったものではないですが、list_dependenciesくらいならMiSawa/ralgoも参考にしてきちんとしたものが出せるかもしれません。

(追記) 「ハック」というのは、外部パッケージをforkしプライベートな関数をパブリックに書き換えて呼び出していたことのようです（！）。

bundleについてはどのみちまともなものになるとは思えないので、PRを出すつもりはありません。良くてonline-judge-toolsのconfig.tomlに書ける外部ツールくらいかなと思います。（そうすることによってどんな良いことがあるのかは分からないのですが…）

qryxip commented 4 years ago

私の方でも昨日言ったやりかたでcargo-equipというのを実装してみました。

依存関係の推測は一切せず、ライブラリ側で明示的に指定する形です。指定が欠けている場合はwarningと共にすべてのモジュールを展開します。

また深さ2以降のモジュールはその親や兄弟とと区別しません。

# lib側

[package.metadata.cargo-equip.mod-dependencies]
"algebra" = []
"bit" = ["algebra"]
"input" = []

例としてはこのコードを

# bin側

[dependencies]
__complib = { package = "complib", path = "/home/ryo/src/local/complib" }
cargo_equip_marker = { path = "/home/ryo/src/github.com/qryxip/cargo-equip/cargo_equip_marker" }
/* aaaaa */
#[cargo_equip::equip]
use ::__complib::{bit::AdditiveBit, input}; /* aaaaa */

fn main() {
    input! {
        n: usize,
        q: usize,
        r#as: [i64; n],
        queries: [(u32, usize, i32); q],
    }

    let mut bit = AdditiveBit::new(n);

    for (i, a) in r#as.into_iter().enumerate() {
        bit.plus(i, a);
    }

    for (kind, v1, v2) in queries {
        match kind {
            0 => {
                let (p, x) = (v1, v2 as i64);
                bit.plus(p, x);
            }
            1 => {
                let (l, r) = (v1, v2 as usize);
                println!("{}", bit.query(l..r));
            }
            _ => unreachable!(),
        }
    }
}

このように展開できます。

https://judge.yosupo.jp/submission/20610

#[cargo_equip::equip]が付いたuse文を展開します。 useにはtrailing colon (::)を要求します。そうするとpathの1つめはextern_crate_nameと言えるのでそこからdependencies内のlibを割り出します。 2つめは展開するモジュールの絞り込みに使い、3つめ以降はuse self::..と置き換えます。

Clippy, rust-analyzer, 展開後のコード, すべて騙せているように思えます。今のところは。

あとやりたいのは

qryxip commented 4 years ago

READMEを書いてCrates.ioにアップしました。テストはこれから書きます。

手で書いた依存関係は

$ cargo metadata --format-version 1 --no-deps | jq '.packages[].metadata."cargo-equip-lib"."mod-dependencies"'

として読むことができます。

cargo-auto-bundleとアプローチ(≠ ツール自体)を比べたときの利点欠点はこのあたりでしょうか:

pros:

cons:

ところで本っ当に今更なんですが、verificationに直接bundleを使うのではなくlist_dependencies通りの絞り込みを行うバンドル方法が1つ以上存在することが重要、という理解でいいんでしょうか...?

kmyk commented 4 years ago

ところで本っ当に今更なんですが、verificationに直接bundleを使うのではなくlist_dependencies通りの絞り込みを行うバンドル方法が1つ以上存在することが重要、という理解でいいんでしょうか...?

なにを確認しようとしているのか理解できませんでした。とりあえず関連しそうな情報を列挙しておきます。

qryxip commented 4 years ago

bundleはverifyに必須ではないというのは認識していたのですが、compileの引数にしている訳ではなさそうだしverify側でどうbundleを使うのかがわかりませんでした。oj verify docsで使ってたんですね。手元で生成して初めて気付きました。なるほどライブラリ側のbundleも何に使うのかと思っていたのですがこういう形なら第三者とかが使いやすくなるという利点がありますね。あとよく見たらoj-verify runでもバンドルを実行している。

cargo-equipを使ったそれっぽいセットをとりあえず作ってみました。

qryxip/oj-verify-playground

Screenshot1

Screenshot2

qryxip commented 4 years ago

一応整えましたがこれでいいのか感が

https://qryxip.github.io/oj-verify-playground

(edit) config.tomlの設定である程度動いちゃうのを見てしまうとPR出す気が薄れてきますね。(自分で作ったツールですが)cargo-equpみたいなのがベストかどうかわからないですし。

qryxip commented 4 years ago

メモ:

regexident/cargo-modules

A cargo plugin for showing an overview of a crate's modules.

cargo modules treeとcargo modules graphのサブコマンドからなる老舗(since 2016)のツールである。rustc-ap-*系を用いておりNightly Rustを要求する。cargo modules treeはクレート内のモジュールをtree(1)のように表示する。

そしてcargo modules graphはモジュールの依存関係をグラフで出力する。READMEには(当時の)cargo-modules自身に使った図が載っている。

READMEの画像

これはまさしく我々が求めていたものに見える。しかしREADMEをblameするとこの画像が貼られたのは2018月5月、Rust 2018年がリリースされる少し前である。

現在のRustで動作させた場合、このような悲しい図しか得られない。(実際にはモジュール同士は依存しあってるし、さらに言えばngは4つのサブモジュールを持っているはずである)

なにこれ

いろいろ試した結果だが、Rust 2018では動作しないと言っても良い。依存関係を伝える方法も無さそう。 ただしなんとかしようとはしている模様。

https://github.com/regexident/cargo-modules/issues/34

これを助けてRust 2018で動くようになったcargo-modulesを使う、という選択肢がある。

kmyk commented 3 years ago

メモ: https://github.com/ngtkana/procon-bundler

kmyk commented 3 years ago

メモ: https://github.com/kenkoooo/cargo-concat by @kenkoooo

qryxip commented 3 years ago

cargo-equip、結局ngtkana/procon-bundlerのようにライブラリを小さなクレートに分割する方式でいきました。

というのもRustのコンパイル単位はクレートなので「モジュール同士の依存関係」というものを考えようとした時点で辛くなります。クレートを分割んかつする方針で行けばlibクレート → libクレートの依存はJSONのデータから連結成分を求めるだけですし、binクレート → libクレートも(私がcollaboratorをやっている)cargo-udepsで列挙できます。cargo-udepsはralgoと同じくsave-analysisを使いますが、こちらはRLSは使わずにJSON内のlib.nameをそのまま読むだけです。

懸念であった「ライブラリ同士の名前解決」はextern preludeからの解決を制約で禁じてextern crateでマウントしてそこを処理するという形で、「マクロの名前解決」は$crateを置き換え、#[macro_export]するものは上手い位置でre-exportするという形で解決できました。

この方針であればlist_dependenciesを列挙するのにRustのコードを書く必要はなくなり、このような簡単なコードですべてが賄えます。(bundleがどうなるかはcargo-equipのREADMEから)

https://github.com/qryxip/oj-verify-playground/blob/master/.verify-helper/oj-verify-rust.py https://qryxip.github.io/oj-verify-playground

問題は競プロライブラリをこのように小さなクレートに分割している人が今現在は皆無であることですね... rust-lang-ja/ac-library-rsもモジュールで区切られた大きな単一のクレートです。cargo-equip用にはこのようなものを用意して対応しましたが...

qryxip/ac-library-rs-parted (oj-verify-playgroundでも使ってます)

あと一応現段階でのバンドルツール5つを比較してみました。誤りがあるかもしれませんが。

kmyk commented 3 years ago

ところでいまさらだけど、Rust の作法的に最も正しいのは oj-verify を使うことでなくて #![verify("https://judge.yosupo.jp/problem/unionfind")] みたいな attribute を使って cargo に組み込む方針なはずなんですよね。これについては @ngtkana が詳しいはずだし、放っておけば作ってくれるはず。

qryxip commented 3 years ago

cargo subcommandにするのならCargo.toml内のpackage.metadataの方がいいんじゃないかと。作法的にも。

というよりcargo-compete (snowchainsのコア部分を流用したRust専用競プロツール)が既にそれっぽいですね。Dropboxからのダウンロード機能を備えているので(snowchainsのと共用)今のままでもAtCoderの問題のverifyに使える...?

[package.metadata.cargo-compete.bin]
a = { name = "arc107-a", problem = { platform = "atcoder", contest = "arc107", index = "A", url = "https://atcoder.jp/contests/arc107/tasks/arc107_a" } }
b = { name = "arc107-b", problem = { platform = "atcoder", contest = "arc107", index = "B", url = "https://atcoder.jp/contests/arc107/tasks/arc107_b" } }
c = { name = "arc107-c", problem = { platform = "atcoder", contest = "arc107", index = "C", url = "https://atcoder.jp/contests/arc107/tasks/arc107_c" } }
d = { name = "arc107-d", problem = { platform = "atcoder", contest = "arc107", index = "D", url = "https://atcoder.jp/contests/arc107/tasks/arc107_d" } }
e = { name = "arc107-e", problem = { platform = "atcoder", contest = "arc107", index = "E", url = "https://atcoder.jp/contests/arc107/tasks/arc107_e" } }
f = { name = "arc107-f", problem = { platform = "atcoder", contest = "arc107", index = "F", url = "https://atcoder.jp/contests/arc107/tasks/arc107_f" } }
qryxip commented 3 years ago

見栄えを良くする案:

(edit1) cargo xtask new fooか./new.py fooでパッケージを追加できるようにするのもいいかも

(edit2) my-complib-*のtop level documentがそのままだとmy-complibに持ってこれないけどcustom-buildを駆使すれば... (クレート分割した上での全部入りのは多分直接使わない。私のcargo-equipだとinclude!(concnat!(env!("OUT_DIR"), "/generated.rs"))に対応してますが)

.
├── Cargo.toml
├── crates
│   ├── manifests
│   │   ├── my-complib-a
│   │   │   └── Cargo.toml
│   │   ├── my-complib-b
│   │   │   └── Cargo.toml
│   │   └── my-complib-c
│   │       └── Cargo.toml
│   └── src
│       ├── a.rs
│       ├── b.rs
│       └── c.rs
└── src
    └── lib.rs

7 directories, 8 files
# Cargo.toml

[workspace]

[package]
name = "my-complib"
version = "0.0.0"
authors = ["Ryo Yamashita <qryxip@gmail.com>"]
edition = "2018"
publish = false

[dependencies]
my-complib-a = { path = "./crates/manifests/my-complib-a" }
my-complib-b = { path = "./crates/manifests/my-complib-b" }
my-complib-c = { path = "./crates/manifests/my-complib-c" }
// src/lib.rs

pub mod a {
    //! A re-export of `my-complib-a`.
    pub use a::*;
}

pub mod b {
    //! A re-export of `my-complib-b`.
    pub use b::*;
}

pub mod c {
    //! A re-export of `my-complib-c`.
    pub use c::*;
}
# crates/manifests/my-complib-a/Cargo.toml

[package]
name = "my-complib-a"
version = "0.0.0"
authors = ["Ryo Yamashita <qryxip@gmail.com>"]
edition = "2018"
publish = false

[lib]
name = "a"
path = "../../src/a.rs"

[dependencies]
my-complib-b = { path = "../my-complib-b" }
my-complib-c = { path = "../my-complib-c" }
// crates/src/a.rs

use b::B;
use c::C;

/// A.
pub struct A(B, C);

Screenshot3 Screenshot1 Screenshot2