【競プロ】Pythonの自作ライブラリを1ファイルにまとめるツールを作った話

## 要約

競プロ向けに、[oj-bundle](https://github.com/online-judge-tools/verification-helper)や[webpack](https://webpack.js.org)、[AtCoder Libraryのexpander.py](https://github.com/atcoder/ac-library)のようなツールのPython版を作りました。このツールを使うことで、それまでコピー＆ペーストで運用していたスニペット集をパッケージとして管理することができます。

https://github.com/bayashi-cl/expander

## 使い方

### インストール

```
pip install git+https://github.com/bayashi-cl/expander
```

### 実行コマンド

```
python -m expander <source file> [-o <output file>] [-m <expand module names...>]
```

例:
```
python -m expander main.py -o out.py -m yourlib
```

出力先の指定がない場合は標準出力に出力されます。

### サンプル

* 展開前のコード

```python
import sys

from byslib.core import IINF, MOD, debug, sinput
from byslib.data.union_find import UnionFindTree


def main() -> None:
    n, q = map(int, sinput().split())
    uft = UnionFindTree(n + 1)
    for _ in range(q):
        l, r = map(int, sinput().split())
        uft.union(l - 1, r)
    print("Yes" if uft.same(0, n) else "No")


if __name__ == "__main__":
    sys.setrecursionlimit(10**6)
    main()
```

* [展開後のコード(AtCoder)](https://atcoder.jp/contests/abc238/submissions/29410034)(若干のネタバレを含みます。)


### パフォーマンス

Library Checkerで検証しました。

Problem: [Shortest Path](https://judge.yosupo.jp/problem/shortest_path)

|CPython  |Submission                                 |Time   |
|:--------|:------------------------------------------|:------|
|expander |<https://judge.yosupo.jp/submission/79094> |2745 ms|
|pure     |<https://judge.yosupo.jp/submission/79093> |2970 ms|

|PyPy     |Submission                                 |Time   |
|:--------|:------------------------------------------|:------|
|expander |<https://judge.yosupo.jp/submission/79096> |913 ms |
|pure     |<https://judge.yosupo.jp/submission/79097> |918 ms |

ライブラリをそのまま貼り付けたときより若干速くなっています。これは関数などの定義がグローバルからモジュール内に移っためだと考えられます。

## 技術的な話

内部の実装の話をします。興味がある方はどうぞ。

### 文字列からのimport

オンラインジャッジに提出するためには、ソースコードを一つのファイルにまとめる必要があります。しかし、パッケージ内のコードをそのまま貼り付けるだけでは、名前の衝突などの問題が発生する可能性があります。

そこで本ツールでは、**コードを文字列として埋め込み、そこから動的にモジュールを作成する**という手法をとっています。([ac-library-python内の実装](https://github.com/not522/ac-library-python/blob/master/atcoder/__main__.py)を参考にしました。)

例として、以下のモジュール`a.b.c`を展開する場合を考えます。

```python
import sys
import a.b.d
from a.e import f

def function() -> None:
    """docstring"""
    pass
```

この場合の手順は次のとおりです。

1. 提出コード内に`a.b = types.ModuleType("a.b")`で動的なモジュールを作成する。
1. モジュール内のimport文のうち、更に展開が必要なもの(この場合では`import a.c` と `from a.e import f`)を依存先として記録し、コメントアウトしたうえで提出コードに文字列として書き込む。
1. 依存先を`a.b.__dict__`に登録する
1. `exec`関数でコードを読み込む。このとき第2引数に`a.b.__dict__`を渡すことでモジュールに関数などが登録される。

提出コードは以下のようになります。

```python
a.b = types.ModuleType("a.b")
_code_a_b = """
import sys
# import a.c
# from a.e import f

def function() -> None:
    \"""docstring\""" # <- 必要に応じてエスケープ処理をする
    pass
"""
a.b.__dict__["a.c"] = a.c
a.b.__dict__["f"] = a.e.f
exec(_code_a_b, a.b.__dict__)
```

### import文を探す

コードからimport文を見つけるには[AST](https://docs.python.org/ja/3/library/ast.html)(抽象構文木)を使います。`ast.NodeVisitor`を継承したクラスに、適切な名前のメゾットを実装することで、コード内の全てのimport文に対してそのメゾットを適用することができます。これにより、import文が何行目にあるか、どのモジュールから何をimportしているのかを取得することができます。

### 依存関係を解決する

モジュールの作成とコードの読み込みはモジュール同士の依存関係に応じた適切な順番で行う必要があります。

モジュール作成の依存関係は例えば `a.b`が`a`に依存する、というようなもので、依存関係はグラフ用語で言うところの**木**になります。また、コードの読み込みの依存関係はimport文によるもので、その関係は**DAG**(Directed acyclic graph)になります。

よって、モジュールの作成は最上位パッケージを根とした深さ優先探索の**行きがけ順**、コードの読み込みはimport文による依存関係を深さ優先探索したときの**帰りがけ順**に行います。

### importされているモジュール一覧を取得する

あらかじめ読み込むべき全てのモジュールを列挙できれば見通しよく探索することができます。標準ライブラリである[`modulefinder`](https://docs.python.org/ja/3/library/modulefinder.html)を使うことで、コード内でimportされているモジュールの一覧とそのファイルの場所を調べる事ができます。

使用例
```python
from modulefinder import ModuleFinder
finder = ModuleFinder()
finder.run_script("path/to/source.py")
finder.modules # <- ここに情報が辞書として格納される
```

### ライセンスへの対処

展開するパッケージがMITなどで公開されていた場合、提出コード内にライセンスの条文を含める必要があります。パッケージのライセンス情報などは`importlib.metadata`を使って取得することができます。しかし、ここで必要なのはパッケージ名であり、これはモジュール名と異なる可能性があります(sklearnがモジュール名、scikit-learnがパッケージ名、など)。モジュール名からパッケージ名を取得するのは不可能なようなので、パッケージを全探索して目的のモジュールを見つけています。

## おわりに

自作ライブラリの管理に悩まれているpythonistaの方に使っていただければ幸いです。

テストを書いたり、実際にコンテストで使ったりして確認はしていますが、もしバグ等をを見つけた方はissueなどで報告していただけると助かります。