y_uti のブログ

統計、機械学習、自然言語処理などに興味を持つエンジニアの技術ブログです

PHP プログラムのファイルサイズと抽象構文木のノード数の分布

PHP7 で利用できる php-ast 拡張モジュールを導入して、PHP のプログラムのファイルサイズと抽象構文木のノード数の関係をプロットしてみます。

PHP7 では、プログラムを実行する際、構文解析の結果を抽象構文木 (Abstract Syntax Tree) の形にして、それからバイトコードを生成するようになりました*1。抽象構文木を作ってフェーズを分けることには、コンパイラの実装の見通しがよくなる、さまざまな最適化を実装しやすくなる、といった利点があります。このようにフェーズを分けることはコンパイラの実装では一般的で、下記の Wikipedia の説明にもあるように、おおまかには、抽象構文木を作るところまでの処理をフロントエンド、抽象構文木を解析、最適化して実行コードを出力する処理をバックエンドと呼びます。
コンパイラ - Wikipedia

抽象構文木コンパイラの内部で利用されるデータ構造であり、通常は特に意識することはありませんが、php-ast という拡張モジュールを利用すると、抽象構文木PHP のオブジェクトとして取り出せます。今回はこのモジュールを利用して抽象構文木のノード数を数え、ファイルサイズとの関係を散布図に描いてみます。
nikic/php-ast · GitHub

php-ast の導入

php-ast の導入方法は、PHP の拡張モジュールをインストールする通常の手順と同じです。GitHubリポジトリを clone してビルド、インストールした後、ini ファイルを作成して拡張モジュールを有効にします。なお、私は anyenv を利用しているので次のコード例のようになりますが、ファイルの置き場所などは環境に合わせて読み替えてください。

$ git clone https://github.com/nikic/php-ast.git
$ cd php-ast
$ phpize
$ ./configure
$ make
$ make install
$ echo 'extension="ast.so"' >~/.anyenv/envs/phpenv/versions/7.0.0/etc/conf.d/ast.ini

次のようにして、php-ast が正常に導入されたことを確認できます。

$ php -i | grep ^ast
ast
ast support => enabled

php-ast を導入すると、次のような簡単なプログラムで抽象構文木を表示できます。先頭の require で、php-ast のソースコードに同梱されている util.php ファイルを要求します*2。ast\parse_file 関数が抽象構文木を生成し、ast_dump 関数が見やすく整形して出力します。ast_dump 関数は util.php で定義されています。

<?php
require __DIR__ . '/util.php';

$ast = ast\parse_file('php://stdin', $version = 15);
echo ast_dump($ast) . "\n";

このプログラムを dump.php とすると、実行例は次のようになります。以下は、test.php というファイルを作成して抽象構文木を表示させてみたものです。

$ cat test.php
<?php
echo 1 + 2;
$ php dump.php <test.php
AST_STMT_LIST
    0: AST_STMT_LIST
        0: AST_ECHO
            0: AST_BINARY_OP
                flags: BINARY_ADD (1)
                0: 1
                1: 2
ノード数をカウントするプログラムの作成

php-ast モジュールを利用して、抽象構文木のノード数を出力するプログラムを作成します。抽象構文木のノードは ast\Node クラスのインスタンスになっており、children フィールドが子要素の配列を持っています。したがって、次のようなコードでノード数をカウントできます。なお、先ほどの dump.php の出力でもわかるように、children の要素は必ずしも ast\Node オブジェクトになるわけではなく、整数定数などは直接格納されます。これに対応するため children 関数を定義しています。

<?php
function count_node($node) {
    return 1 + array_sum(array_map(function ($child) { return count_node($child); }, children($node)));
}

function children($node) {
    return $node instanceof ast\Node ? $node->children : [];
}

$ast = ast\parse_file('php://stdin', $version = 15);
echo count_node($ast) . "\n";

先ほど作成した test.php で確認してみると、次のように 6 が出力されます。抽象構文木の出力と比較してみると、AST_STMT_LIST が二つ、AST_ECHO, AST_BINARY_OP と続き、末端に整数 1, 2 の合計 6 ノードで、たしかに結果が一致しています。なお、BINARY_ADD は AST_BINARY_OP ノードの属性で、抽象構文木のノードではありません。

$ php count.php <test.php
6
散布図のプロット

それでは、作成したプログラムを使って、さまざまな PHP ファイルのバイト数とノード数の関係を調べてみます。まず、調査対象として composer で適当なパッケージを取得します。今回は Symfony を対象にしました*3

$ composer require symfony/symfony

取得された PHP ファイル数は次のとおりでした。Symfony が依存するパッケージも composer によって自動的に取得されるため、symfony の他にもいくつかのパッケージがあります。すべての合計は 3,474 ファイルでした。

$ find vendor -type f -name '*.php' -print | cut -f1-2 -d/ | uniq -c
     20 vendor/paragonie
      6 vendor/composer
   2973 vendor/symfony
      9 vendor/psr
    255 vendor/twig
    210 vendor/doctrine
      1 vendor/autoload.php

取得した各ファイルについて、ファイルパス、バイト数、ノード数を csv 形式で出力します。確認のため head コマンドで先頭の 5 行を表示してみます。

$ find vendor -type f -name '*.php' -print | while read f; do
    echo $f,$(wc -c $f | cut -f1 -d' '),$(php count.php <$f);
  done >results.csv

$ head -n 5 results.csv
vendor/paragonie/random_compat/lib/byte_safe_strings.php,5631,321
vendor/paragonie/random_compat/lib/cast_to_int.php,2395,89
vendor/paragonie/random_compat/lib/error_polyfill.php,1533,35
vendor/paragonie/random_compat/lib/random.php,5614,308
vendor/paragonie/random_compat/lib/random_bytes_com_dotnet.php,2536,116

あとは、これを Excel で開いてグラフを描画します。次のような結果になりました。横軸がバイト数、縦軸がノード数です。左は調査したすべてのファイルをプロットしたもの、右はバイト数が 10 kbytes までの範囲を拡大したものです。

散布図を眺めてみると、全体的には当然予想できるように比例の関係になっているようです。原点の近くをよく見ると、1 kbyte あたりでノード数が 0 近くに落ちてしまうファイル群と、原点に向かっているファイル群に分かれるように見えます。いくつかのファイルを調べてみたところ、原点に向かっている群は単体テストのファイルなどで、ファイル先頭にライセンスの記述がないなどの理由で違いが出ているものでした。

*1:PHP5 では、抽象構文木を作らずに構文解析しながら直接バイトコード命令を生成していました。

*2:この記事では util.php ファイルをコピーして __DIR__ で指定しました。

*3:最近は仕事で PHP を使う機会が少なく情報を追えていなかったのですが、いつのまにか Symfony 3.0 がリリースされていたようで、バージョンを指定せず require したところ Symfony 3.0 が入ってきました。