てきとうなさいと べぇたばん

PHP extension 写経 - var_dump編 - その3 arrayと参照

無限ループに陥る絵

dump関数3

今回はPHPのarrayとreference(参照)を実装していくぞ。

Arrayを実装する前の変更

Arrayは様々な変数を一つにまとめられるデータ型なので、今まで一つの関数でやっていたことを他の関数にまとめるように作り変えとこう。

今までのコードを書いてると、こんな事になっているはず

PHP_FUNCTION(study_extension_dump)
{
    zval *zv_ptr;
    int argc, i;

    ZEND_PARSE_PARAMETERS_START(1, -1)
        Z_PARAM_VARIADIC('+', zv_ptr, argc)
    ZEND_PARSE_PARAMETERS_END();

    switch(Z_TYPE_P(zv_ptr))
    {
        case IS_NULL:
            php_printf("NULL: null\n");
            break;
        case IS_TRUE:
            php_printf("BOOL: true\n");
            break;
        case IS_FALSE:
            php_printf("BOOL: false\n");
            break;
        case IS_LONG:
            php_printf("LONG: " ZEND_LONG_FMT "\n", Z_LVAL_P(zv_ptr));
            break;
        case IS_DOUBLE:
            php_printf("DOUBLE: %.*G\n", EG(precision), Z_DVAL_P(zv_ptr));
            break;
        case IS_STRING:
            php_printf("STRING: value=\"");
            PHPWRITE(Z_STRVAL_P(struc), Z_STRLEN_P(zv_ptr));
            php_printf("\", length=%zd\n", Z_STRLEN_P(zv_ptr));
            break;
        case IS_RESOURCE: {
            const char *type_name = zend_rsrc_list_get_rsrc_type(Z_RES_P(zv_ptr));
            php_printf("RESOURCE: id=%d type=%s\n", Z_RES_P(zv_ptr)->handle, type_name ? type_name : "Unknown");
            break;
        }
        case default:
            php_printf("UNKNOWN\n");
            break;
    }
}

ここからarrayを追加したいのだけど、arrayは更にarrayを重ねられる

$values = array(
    array(
        array(
            "value",
        ),
    ),
);

arrayの値は任意の型にできるので、arrayとわかったらまた次の値を調べてなんかのスカラー型だったら該当するデータ型を今まで実装したとおりにprintするし、arrayだったらまた繰り返す。繰り返すということは、何らかの方法でループしたい。では何が考えられるのだろうと思ったときにext/standard/var.cを見てみるとそもそも関数に分けて再帰をしていることがわかる。

写経なのだから同じように書けばいいじゃないか、というのもわかるけど、ソースの内容を理解するためにわかりやすくしたので書き直す方法をとった。今更すまないとおもう。

というわけで、関数を分けていこう。実際に出力する関数はstudy_extension_var_dump関数としよう。

PHPAPI void study_extension_var_dump(zval *struc, int level)
{
    switch(Z_TYPE_P(struc))
    {
        case IS_NULL:
            php_printf("NULL: null\n");
            break;
        case IS_TRUE:
            php_printf("BOOL: true\n");
            break;
        case IS_FALSE:
            php_printf("BOOL: false\n");
            break;
        case IS_LONG:
            php_printf("LONG: " ZEND_LONG_FMT "\n", Z_LVAL_P(struc));
            break;
        case IS_DOUBLE:
            php_printf("DOUBLE: %.*G\n", EG(precision), Z_DVAL_P(struc));
            break;
        case IS_STRING:
            php_printf("STRING: value=\"");
            PHPWRITE(Z_STRVAL_P(struc), Z_STRLEN_P(struc));
            php_printf("\", length=%zd\n", Z_STRLEN_P(struc));
            break;
        case IS_RESOURCE: {
            const char *type_name = zend_rsrc_list_get_rsrc_type(Z_RES_P(struc));
            php_printf("RESOURCE: id=%d type=%s\n", Z_RES_P(struc)->handle, type_name ? type_name : "Unknown");
            break;
        }
        case default:
            php_printf("UNKNOWN\n");
            break;
    }
}

今までのstudy_extension_dump関数はこうなる

PHP_FUNCTION(study_extension_dump)
{
    zval *zv_ptr;
    int argc, i;

    ZEND_PARSE_PARAMETERS_START(1, -1)
        Z_PARAM_VARIADIC('+', zv_ptr, argc)
    ZEND_PARSE_PARAMETERS_END();

    for (i = 0; i < argc; i++) {
        study_extension_var_dump(&zv_ptr[i], 1);
    }
}

実は、ZEND_PARSE_PARAMETERS_STARTの引数それぞれ1と-1で、これは「1つ以上、上限なし」を意味している。今までのやり方では引数は一つしか受け入れていないことになっていて、それをfor文で回して一つ一つ引数を出力していく方法に変更している。今まで黙ってて本当に申し訳ない。

したがって、for文のところは、PHPのユーザーランドでいえば次のような文でいうところの、引数を処理していることになる。

<?php
study_extension_dump("abc", "def");
?>

Array部分の実装

それではArray部分の実装に移っていこう。まず、必要な変数宣言を行う

PHPAPI void study_extension_var_dump(zval *struc, int level)
{
    HashTable *myht;
    zend_ulong num;
    zend_string *key;
    zval *val;

    if (level > 1) {
        php_printf("%*c", level - 1, ' ');
    }

このif文は、levelという変数が1より大きいときにその数のスペースをprintfする。ここは2次元配列とか3次元配列とかになってくるとその分ネストされることになる。この段階になって必要になってくるのである。

Arrayであることを知る定数はIS_ARRAYだからこういうコードになる。

    case IS_ARRAY:
        // do something
        break;

というわけで書いていこう。長くなるのでまずは一番外側だけ

    case IS_ARRAY:
        myht = Z_ARRVAL_P(struc);
        count = zend_array_count(myht);
        php_printf("ARRAY(%d) { \n", count);

        PUTS("}\n");
        break;

Z_ARRVAL_PでHashTableへのポインタを取得し、そのポインタを引数にとってzend_array_countでarrayの数を取得してphp_printfでprintしている。PUTSで{}を囲む形になるので出力はこのようになる。

ARRAY(1) {
}

実際の中身を書いていこう

    case IS_ARRAY:
        myht = Z_ARRVAL_P(struc);
        count = zend_array_count(myht);
        php_printf("ARRAY(%d) { \n", count);

        ZEND_HASH_FOREACH_KEY_VAL_IND(myht, num, key, val) {
            if (key == NULL) { /* numeric key */
                php_printf("*c[" ZEND_LONG_FMT "]=>\n", level + 1, ' ', num);
            } else { /* string key */
                php_printf("%*c[\"", level + 1, ' ');
                PHPWRITE(ZSTR_VAL(key), ZSTR_LEN(key));
                php_printf("\""]=>\n");
            }

            study_extension_var_dump(val, level + 2);
        }

        if (level > 1) {
            php_printf("%*c", level - 1, ' ');
        }

        PUTS("}\n");
        break;

これでコンパイルしてみて、早速arrayをdumpしてみよう。

$ sapi/cli/php -r 'study_extension_dump(array(array("abc")));'
ARRAY(1) {
  [0]=>
  ARRAY(1) {
    [0]=>
    STRING: value="abc", length=3
  }
}

中身として必要なコードはこれ。具体的にはZEND_HASH_FOREACH_KEY_VAL_INDでHashTableあるBucketを走査していく。HashTableという構造体と、Bucket構造体を見ていく。

typedef struct _zend_array HashTable;

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

Bucket構造体はこのようになってる。valがこの要素の値になる。

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

ZEND_HASH_FOREACH_KEY_VAL_INDにあるZEND_HASH_FOREACHをみてみると、Bucket構造体をポインタにとって、そのポインタのアドレスをすすめることで走査している。

#define ZEND_HASH_FOREACH(_ht, indirect) do { \
        HashTable *__ht = (_ht); \
        Bucket *_p = __ht->arData; \
        Bucket *_end = _p + __ht->nNumUsed; \
        for (; _p != _end; _p++) { \
            zval *_z = &_p->val; \
            if (indirect && Z_TYPE_P(_z) == IS_INDIRECT) { \
                _z = Z_INDIRECT_P(_z); \
            } \
            if (UNEXPECTED(Z_TYPE_P(_z) == IS_UNDEF)) continue;

&(参照)の実装

実はarrayの実装では一つ足りないものがある。次に参照を実装するときに、arrayで問題点が出てくる。それを再現しながらやっていきたい。まずは参照部分の実装から。

    int is_ref = 0;

again:
    switch(Z_TYPE_P(struc))
    {
        case IS_REFERENCE:
            is_ref = 1;
            struc = Z_REFVAL_P(struc);
            goto again;
            break;
    }

それぞれのデータ型の出力部分に、参照先であることを示す&を表示させる。そうすると、study_extension_var_dump関数はこうなる。

#define STUDY_COMMON (is_ref ? "&" : "")

PHPAPI void study_extension_var_dump(zval *struc, int level) /* {{{ */
{
    uint32_t count;
    HashTable *myht;
    zend_ulong num;
    zend_string *key;
    zval *val;
    int is_ref = 0;

    if (level > 1) {
        php_printf("%*c", level - 1, ' ');
    }

again:
    switch(Z_TYPE_P(struc))
    {
        case IS_NULL:
            php_printf("%sNULL: null\n", STUDY_COMMON);
            break;
        case IS_TRUE:
            php_printf("%sBOOL: true\n", STUDY_COMMON);
            break;
        case IS_FALSE:
            php_printf("%sBOOL: false\n", STUDY_COMMON);
            break;
        case IS_LONG:
            php_printf("%sLONG: " ZEND_LONG_FMT "\n", STUDY_COMMON, Z_LVAL_P(struc));
            break;
        case IS_DOUBLE:
            php_printf("%sDOUBLE: %.*G\n", STUDY_COMMON, (int) EG(precision), Z_DVAL_P(struc));
            break;
        case IS_STRING:
            php_printf("%sSTRING: value=\"", STUDY_COMMON);
            PHPWRITE(Z_STRVAL_P(struc), Z_STRLEN_P(struc));
            php_printf("\", length=%zd\n", Z_STRLEN_P(struc));
            break;
        case IS_RESOURCE: {
            const char *type_name = zend_rsrc_list_get_rsrc_type(Z_RES_P(struc));
            php_printf("%sRESOURCE: id=%d type=%s\n", STUDY_COMMON, Z_RES_P(struc)->handle, type_name ? type_name : "Unknown");
            break;
        }
        case IS_ARRAY:
            myht = Z_ARRVAL_P(struc);
            count = zend_array_count(myht);
            php_printf("%sARRAY(%d) {\n", STUDY_COMMON, count);

            ZEND_HASH_FOREACH_KEY_VAL_IND(myht, num, key, val) {
                if (key == NULL) { /* numeric key */
                    php_printf("%*c[" ZEND_LONG_FMT "]=>\n", level + 1, ' ', num);
                } else { /* string key */
                    php_printf("%*c[\"", level + 1, ' ');
                    PHPWRITE(ZSTR_VAL(key), ZSTR_LEN(key));
                    php_printf("\"]=>\n");
                }
                study_extension_var_dump(val, level + 2);
            } ZEND_HASH_FOREACH_END();

            if (level > 1) {
                php_printf("%*c", level - 1, ' ');
            }
            PUTS("}\n");
            break;
        case IS_REFERENCE:
            is_ref = 1;
            struc = Z_REFVAL_P(struc);
            goto again;
            break;
        default:
            php_printf("UNKNOWN\n");
            break;
    }
}

これでコンパイルしてまずは参照先の値になっているか確認してみよう

$ php -r '$z = 134; $y = array(&$x); $x["abc"] = &$z; study_extension_dump($y);'
ARRAY(1) {
  [0]=>
  &ARRAY(1) {
    ["abc"]=>
    &LONG: 134
  }
}

うまくいったようだ…しかしつぎはどうだろう。

$ php -r '$a = array(); $a[] = &$a; study_extension_dump($a);' | head -n 30
ARRAY(1) {
  [0]=>
  &ARRAY(1) {
    [0]=>
    &ARRAY(1) {
      [0]=>
      &ARRAY(1) {
        [0]=>
        &ARRAY(1) {
          [0]=>
          &ARRAY(1) {
            [0]=>
            &ARRAY(1) {
              [0]=>
              &ARRAY(1) {
                [0]=>
                &ARRAY(1) {
                  [0]=>
                  &ARRAY(1) {
                    [0]=>
                    &ARRAY(1) {
                      [0]=>
                      &ARRAY(1) {
                        [0]=>
                        &ARRAY(1) {
                          [0]=>
                          &ARRAY(1) {
                            [0]=>
                            &ARRAY(1) {
                              [0]=>

head -n 30をとってみると無限ループに陥り、画面上をこれが埋め尽くすことになる。これは、変数$aがarrayのとき、要素の中に$aへの参照が入っていることで、$aを再帰してたどり、また参照になるので$aを再起してたどり、また…という無限ループを繰り返しているのである。

コードベースで確認してみると、最初にIS_REFERENCEにたどり着くと、次にgoto againとなり、switch文をやり直す。

        case IS_REFERENCE:
            is_ref = 1;
            struc = Z_REFVAL_P(struc);
            goto again;
            break;

するとIS_ARRAYにたどり着くので、要素をループして再帰で値を出力する。

        case IS_ARRAY:
            myht = Z_ARRVAL_P(struc);
            count = zend_array_count(myht);
            php_printf("%sARRAY(%d) {\n", STUDY_COMMON, count);

            ZEND_HASH_FOREACH_KEY_VAL_IND(myht, num, key, val) {
                if (key == NULL) { /* numeric key */
                    php_printf("%*c[" ZEND_LONG_FMT "]=>\n", level + 1, ' ', num);
                } else { /* string key */
                    php_printf("%*c[\"", level + 1, ' ');
                    PHPWRITE(ZSTR_VAL(key), ZSTR_LEN(key));
                    php_printf("\"]=>\n");
                }
                study_extension_var_dump(val, level + 2);
            } ZEND_HASH_FOREACH_END();

そのはずだが、そのときに自身への再帰だった場合には、IS_REFERENCEにたどり着いてgoto again、IS_ARRAYに来てまた…となるのである…と確認できる。

これを防ぐ方法はどうすればよいのかと言うと、ここで再帰を防止するため循環参照のフラグをつけて、フラグを検知したら止めて関数を抜ける。次のコードがそのような機構をもっている。

        case IS_ARRAY:
            myht = Z_ARRVAL_P(struc);

            /* recursion protection */
            if (level > 1 && !(GC_FLAGS(myht) & GC_IMMUTABLE)) {
                if (GC_IS_RECURSIVE(myht)) {
                    PUTS("*RECURSION*\n");
                    return;
                }
                GC_PROTECT_RECURSION(myht);
            }

また、この循環参照のフラグを取らないといけないので、ZEND_HASH_FOREACHでのループを終わったら取るブロックも追加する。

            ZEND_HASH_FOREACH_KEY_VAL_IND(myht, num, key, val) {
                // 省略
                study_extension_var_dump(val, level + 2);
            } ZEND_HASH_FOREACH_END();

            if (level > 1 && !(GC_FLAGS(myht) & GC_IMMUTABLE)) {
                GC_UNPROTECT_RECURSION(myht);
            }

これでコンパイルして、実行してみよう。

$ php -r '$a = array(); $a[] = &$a; study_extension_dump($a);' 
ARRAY(1) {
  [0]=>
  &ARRAY(1) {
    [0]=>
    *RECURSION*
  }
}

よし、これでうまくいった。

今回は終わり

次はオブジェクト。次回で完成する。