Include-what-you-useを使って過剰Includeを防ぐ【競技プログラミング】

## Include-what-you-useとは
Include-what-you-use(IWYU)は、C-like言語(C,C++)のソースコードに登場する`#include`を解析し、不要な`#include`の削除や適切なインクルードタグの順番を提案指摘してくれるツールです。

https://github.com/include-what-you-use/include-what-you-use

Clangでのコンパイル用に作られていますが、競プロでよく使われるg++にも使えています。

この記事では、Include-what-you-useの利点からインストール方法、そしてどのくらい早くなるのかを紹介します。

## 何がうれしいのか
競技プログラミングは普段のコーディング作業に比べ、コードをテストする機会・回数が多いと思います。C++など実行するのにコンパイルが必要な言語では「ちょっとここをデバッグしたい」と思ったときに数秒のコンパイルを挟まなければなりません。

「**数秒ならいいじゃん．．．**」と思ったあなた。正直そうです。

ただ、コードが巨大になるにつれコンパイルの問題はコーディング作業により影響を与えると思います。

### 競プロでの`#include<bits/stdc++.h>`問題

[AtCoderの記事(APG4b)](https://atcoder.jp/contests/APG4b/tasks/APG4b_b)にある通り`#include<bits/stdc++.h>`は「C++の機能を「全て」読み込むための命令」です。そのため、これを読み込むことによるコンパイル時間の増加が懸念されます。

一方で、同記事には「業務におけるプログラミングでは推奨されないことがありますが、競技プログラミングやAPG4bで利用する場合は全く問題ありません。」とあるように、競技プログラミングではコードを簡潔化させるため、またインクルードのし忘れの観点から推奨されています。

競技プログラミングでIWYUを使うことの意義はこの「`#include<bits/stdc++.h>`」で読み込まれたC++の機能の全てから必要なものだけを抽出することにあります。

## 環境

* Ubuntu 22.04.4 LTS (WSL2)
* g++ 11.4.0

```shell-session
$ cat /etc/lsb-release
DISTRIB_ID=Ubuntu
DISTRIB_RELEASE=22.04
DISTRIB_CODENAME=jammy
DISTRIB_DESCRIPTION="Ubuntu 22.04.4 LTS"

$ apt --version
apt 2.4.12 (amd64)

$ g++ --version
g++ (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
```

## インストール

以下のコマンドを実行します。

```shell-session
$ sudo apt-get update
$ sudo apt-get upgrade  # 必要に応じて
$ sudo apt-get install iwyu
```

バージョンを確認してインストールされているっぽい感じなら大丈夫です。

```shell-session
$ include-what-you-use --version
include-what-you-use 0.17 based on Ubuntu clang version 13.0.1-2ubuntu2.2
```

## 使い方

基本形
```shell-session
$ include-what-you-use <your_cpp_file.cpp>
```

ほとんどの場合、インクルードパスの不足で失敗します。インクルードパスを追加するには以下のように入力します。

```shell-session
$ include-what-you-use -I/path/to/your/includes -I/another/include/path <your_cpp_file.cpp>
```

この場合は`/path/to/your/includes`と`/another/include/path`がインクルードパスとして探索されます。

### パスの指定がわからない or エラー

以下のようなエラーが発生することがあります。パスの指定が適切にできていない可能性があります。
```shell-session
$ include-what-you-use main.cpp 

<path>::fatal error: 'float.h' file not found
#include <float.h>
         ^~~~~~~~~
```

以下のコマンドを実行して、いつも使っているコンパイラで使用しているインクルードパスを取得します。(g++の場合)

```shell-session
$ g++ -E -v -
    ~~~ (略) ~~~
#include <...> search starts here:
 /usr/lib/gcc/x86_64-linux-gnu/11/include
 /usr/local/include
 /usr/include/x86_64-linux-gnu
 /usr/include
End of search list.
```

`#include <...> search starts here:`から始まるパスがインクルード時に使用しているパスになります。上のほうが強いです。

したがってこの例では

```shell
$ include-what-you-use \
    -I/usr/lib/gcc/x86_64-linux-gnu/11/include \
    -I/usr/local/include \
    -I/usr/include/x86_64-linux-gnu \
    -I/usr/include \
    main.cpp
```

のようにすることで正しくパスを指定できます。AtCoder-Libraryを使用している場合はそのパスを指定しましょう。(`/usr/include/`にac-libraryのディレクトリを置くといちいち書かなくて済みます。)

### 使ってみる

簡単なプログラムで実験してみます。

```cpp:main.cpp
// author: TsuruNoTsurugi
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    map<int, int> mp;
    atcoder::dsu d(N);
}
```

このプログラムでは`iostream`の`cin`、`vector`の`vector`、`map`の`map`([C++日本語リファレンスより](https://cpprefjp.github.io))、さらに`atcoder`の`dsu`をプログラム内で使用しています。

```shell-session
$ include-what-you-use -I/usr/lib/gcc/x86_64-linux-gnu/11/include main.cpp

main.cpp should add these lines:
#include <atcoder/dsu.hpp>  // for dsu
#include <iostream>         // for basic_istream::operator>>, basic_istream<...
#include <map>              // for map
#include <vector>           // for vector

main.cpp should remove these lines:
- #include <bits/stdc++.h>  // lines 2-2
- #include <atcoder/all>  // lines 3-3

The full include-list for main.cpp:
#include <atcoder/dsu.hpp>  // for dsu
#include <iostream>         // for basic_istream::operator>>, basic_istream<...
#include <map>              // for map
#include <vector>           // for vector
---
```

上から、「追加したほうがいいやつ」「消したほうがいいやつ」→「それを踏まえた最終的なリスト」です。しっかりと使用しているライブラリのみインクルードする設定になっています。なお、順番も処理ができる限り軽くなるような順番にしてくれています。

### どのくらい早くなるのか

`time`コマンドを使って計測してみました。

```shell-session
$ time g++ main.cpp  # 変更前

real    0m1.506s
user    0m1.313s
sys     0m0.091s

$ time g++ main.cpp  # 変更後

real    0m0.449s
user    0m0.306s
sys     0m0.042s
```

実時間で1秒近く短くなっています。すごい。~~ま、Pythonには敵いませんが…~~

### 欠点

IWYUの実行にまあまあ時間がかかります。(←は?)
ただ、これを「コーディング→終わったら`IWYU`実行」ではなくコーディングしながら解析してもらう、とすることである程度改善します。

また、実装内容を大きく変更しないなら1回目の実装の終わりに一度だけ実行してインクルードを減らすという方法があります。

## 結果取得 & 自動改変

`fix_includes.py`をダウンロードします。

https://github.com/include-what-you-use/include-what-you-use/blob/master/fix_includes.py

```shell-session
$ wget https://raw.githubusercontent.com/include-what-you-use/include-what-you-use/master/fix_includes.py
$ chmod +x fix_includes.py
```

:::note warn
`fix_includes.py`の112行目が
```Python
_INCLUDE_RE = re.compile(r'\s*#\s*include\s+([<"][^">]+[>"])')
```
となっていますが、
```Python
_INCLUDE_RE = re.compile(r'\s*#\s*include ?([<"][^">]+[>"])')
```
にしたほうがいいと思います。
そのままだと`#include <bits/stdc++.h>`が許容、`#include<bits/stdc++.h>`が不可になります。(それか、コード整形ツールを使うか)
:::

### fix_include.py使い方

まず、`include-what-you-use`の結果をテキストファイルなどに保存します。パイプラインを使うと便利です。
`include-what-you-use`のファイル指定はフルパスを推奨します。

```shell-session
$ include-what-you-use -I/usr/lib/gcc/x86_64-linux-gnu/11/include /home/ubuntu/main.cpp > iwyu_output.txt
```

結果が、`iwyu_output.txt`に保存されます。

:::note info
`> iwyu_output.txt`は標準出力を取得(?)して保存します。私の環境では`include-what-you-use`がエラーコードをはいて標準出力ではうまく取得できませんでした。その場合は、標準エラー出力から取得するといいです。

`2> iwyu_output.txt`と前に`2`をつけましょう。
:::

つぎに、Python3環境で`fix_includes.py`を実行します。

```shell-session
$ python3 fix_includes.py /home/ubuntu/main.cpp < iwyu_output.txt
```

`fix_includes.py`を見ると、途中でパスを確認する部分がある(同ファイル2200行あたり)のですが、どうやらフルパスでないと通らないっぽいので**フルパスで書くのをお勧めします**。

## まとめ

* `#include<bits/stdc++.h>`から本当に使うライブラリだけ、インクルードするとコンパイル時間がかなり短縮された。
* 実は、IWYUが遅い。
    * いつ実行させるかを選ぶ必要がある。

私はAtCoder-CLIの機能をGUI化し(?)、パネルにまとめて使っています。ここにIWYUの機能を追加してみようと思います。

https://github.com/TsuruNoTsurugi/atcoder-GUI