なぜ純粋なPHPでサイクリックアレイを検出できないのか

この記事は、カスタムシリアライザーを書きたいと思うPHPプログラマの少数の少数派や、再帰的に配列を反復する必要がある他の何かに関連しているかもしれない問題についてです.しかし、それを解決しようとして、私は、私がハイライトする価値があると思う若干の面白いPHP奇怪を見つけました.
脇で
あなただけの循環配列を検出するための信頼性の高いソリューションを探している場合は、いくつかのクールな(しかし、複雑な)PHPのquirksについての学習をお見逃しなくしたい-その後、このシリーズのスキップします.
まず第一に、私たちの用語を定義しましょう.このポストの目的のために、我々は非常に実用的な定義を支持することができます.循環配列も時々循環的であるか再帰的です.いくつかの例を見てみましょう.

// Contains a reference to itself
$v = [1, 2, 3];
$v[1] = &$v;

// Contains a nested array that contains a reference to $x
$x = [1, [2, 3]];
$x[1][1] = &$x;

// Contains a nested array that contains a reference to an ancestor
$y = [1, [2, [3, 4]]];
$y[1][1][1] = &$y[1];

// Contains a nested array that contains a reference to itself
$z = [1, [2, 3]];
$z[1][1] = &$z[1];

あなたはアイデアを得ると思う.これらのアレイの全ては、あるレベルのサイクルを含む.

純粋なPHPソリューションの試み

ここでは、循環配列を検出するための簡単なアルゴリズムを示します.与えられた配列については、すべての項目と同様にサブ項目を反復し、道に沿ってすべての配列をマークします.任意の時点で既にマークされた配列に遭遇した場合、サイクルを見つけ、入力配列は循環的です.PHPで書く方法

function is_cyclic(array &$array)
{
    $lastKey = array_key_last($array);
    if ($lastKey === null) {
        // Array is empty
        return false;
    }
    static $marker;
    if ($marker === null) {
        $marker = new stdClass();
    }
    if ($array[$lastKey] === $marker) {
        return true;
    }
    $array[] = $marker;
    foreach ($array as &$item) {
        if (is_array($item) && is_cyclic($item)) {
            array_pop($array); // Remove marker
            return true;
        }
    }
    array_pop($array); // Remove marker
    return false;
}

配列引数を参照渡しする必要があることを指摘する価値がありますまたは、私たちはコピーにマーカーを追加するでしょう、そして、入力として再帰的な配列を与えられるとき、アルゴリズムは決して終わらないでしょう.それが後で我々を噛むために戻って来るので、これを心にとめておいてください.しかし、少なくとも今のところ、この機能は、ちょうどうまく働くようですrun code ).

純粋なPHPソリューションの破壊

この節では、PHPでは、オブジェクトとして行うことができるインスタンスIDの配列を比較することはできません.つの変数が同じ配列を参照しているかどうかを判断する唯一の方法は、1つの変数を使用して配列をマークし、それから他の変数を使用してマークをチェックすることです.したがって、この手順で重大な欠陥を見つけることができれば、純粋なPHPで循環配列を確実に検出することは不可能です.
以前から我々の機能を破るために、我々はそれに特別に巧みに作られた配列を供給しなければなりません.それにはいくつかの方法がある.私があなたを示しているものは、非常に疑わしく見えて、実際に本当のコードに現れるかもしれません.

function craft_bomb() {
    $array = [1, [2, 3]];
    $array[1][1] = &$array;
    return $array;
}

$bomb = craft_bomb();
var_export(is_cyclic($bomb));

この印刷は本当か偽か答えは:どちらも.代わりに、メモリが不足したりタイムアウトしたりするまで、このコードは決して完成しませんrun code ). どうしてこれができますか.配列は明らかに再帰的であるvar_dump では、

$bomb = craft_bomb();
var_dump($bomb);

array(2) {
  [0]=>
  int(1)
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    *RECURSION*
  }
}

ここで普通の何も.確認するには、同じ構造体を持つ配列をダンプしましょう.ローカルスコープで構築されている点だけが違います.

$local = [1, [2, 3]];
$local[1][1] = &$local;
var_dump($local);

array(2) {
  [0]=>
  int(1)
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    *RECURSION*
  }
}

予想通り、ダンプは同一です(run code ), しかし、1つの配列は、我々のプログラムをクラッシュさせる他の1つはありません.目に会うより明らかにそこにあります.

配列内で何が起こっているか

写真でcottonbro からPexels
実際に我々のプログラムで起こっていることについてのアイデアを得るためにいくつかのprintfデバッグをしましょう.すべての呼び出しで関数引数をダンプすると、以下の出力が得られますrun code ):

Call 1:
array(2) {
  [0]=>
  int(1)
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    _RECURSION_
  }
}

Call 2:
array(2) {
  [0]=>
  int(2)
  [1]=>
  array(2) {
    [0]=>
    int(1)
    [1]=>
    _RECURSION_
  }
}

Call 3:
Same as call 1

Call 4:
Same as call 2
...

これらの2つの配列ダンプは永遠に交替し続けます.興味深いことに、私たちが以前に言及したように、私たちが参照ではなく値で関数引数を渡すなら、私たちは全く同じ出力を得ます.これは、いくつかのコピーが起こっていることを示唆しています.
おそらく関数引数よりも洞察力があるのは、元の入力配列がどのように変化するかである.それぞれの関数コールをダンプすると、何かとてもユニークなものが見えますrun code ):

Call 1:
array(2) {
  [0]=>
  int(1)
  [1]=>
  array(2) {
    [0]=>
    int(2)
    [1]=>
    _RECURSION_
  }
}

Call 2:
array(3) {
  [0]=>
  int(1)
  [1]=>
  &array(2) {
    [0]=>
    int(2)
    [1]=>
    array(2) {
      [0]=>
      int(1)
      [1]=>
      _RECURSION_
    }
  }
  [2]=>
  object(stdClass)#1 (0) {
  }
}

Call 3:
array(3) {
  [0]=>
  int(1)
  [1]=>
  &array(3) {
    [0]=>
    int(2)
    [1]=>
    &array(2) {
      [0]=>
      int(1)
      [1]=>
      array(2) {
        [0]=>
        int(2)
        [1]=>
        _RECURSION_
      }
    }
    [2]=>
    object(stdClass)#1 (0) {
    }
  }
  [2]=>
  object(stdClass)#1 (0) {
  }
}

...

これはかなり面倒なことですが、配列のダンプがすべての関数呼び出しで1つのレベルより深くなることがわかります.それに加えて、スクリプトのメモリ使用量は時間とともに着実に増加しますrun code ). これによって、ランタイムがメモリチェーンの下に行くときに、メモリ上の循環配列をlazalyに実体化しているということになります.また、我々のプログラムを永遠に実行させるメカニズムについて説明します.
我々がまだ知らないことは、配列がなぜこのように振る舞うのか、そしてなぜそれがローカルに構築された配列と異なるのかです.

配列を信頼できません

写真でSharath G. からPexels
一般に、配列は期待通りに動作します.ただし、参照を含む配列で値代入を実行すると、その予測可能性がウィンドウに表示されます.「なぜ?」聞いてください.このコードを見て、どんな出力を期待しているかを考えてみましょう.run code ):

$a = 1;
$b = [&$a];
$c = $b;
$b[0] = 2;
echo "$b[0] $c[0]"; // 2 2

あなたが言うならば2 2 それから、あなたは正しいでしょう.でも、2 1 この例が示すように、プログラムの残りに応じてrun code ):

$a = 1;
$b = [&$a];
$c = $b;
unset($a); // <--
$b[0] = 2;
echo "$b[0] $c[0]"; // 2 1

この正確な振る舞いについてのセクションがありますchapter 4 of the PHP Language Specification これは配列の値割り当ての対象を扱います.要約すると、我々の問題に関連している2つのキーの持ち帰りがあります.

エイリアスであるソース配列内の任意の項目(参照)は、ランタイム固有のアルゴリズムで定義されるように、値または参照によって、宛先配列に割り当てられます.

$a = 1;
$b = [&$a]; // $b[0] is an alias for $a
$c = $b;
// The last line is equivalent to either:
// $c = [&$a] or $c = [$a];

配列の実際のコピーは、配列が突然変異されるまでコピーされます.

$a = 1;
$b = [&$a];
$c = $b;
// The last line might be sort of equivalent to $c = &$b
// until the array is mutated through either $b or $c.

これらの2つの規則を使えば、なぜ機能がis_cyclic ローカルスコープで構成されている配列と、関数によって返された配列に対して異なる動作をします.
最初のケースでは、値の割り当ては、配列を使用して実行されません.これは、関数が期待するように動作する理由です.
番目の場合、配列は値から関数から返され、ローカル変数に割り当てられます繰返されたコピー(規則2 ).配列をマークしたい場合、ランタイムは最初にマークを受け取るコピーを作成します(規則2).コピーを実行すると、入れ子になった配列をコピーすることもできます.配列をマークするたびに、新しいコピーが作られ、初期配列は1つのレベルを深くします.
私は知っている、これはあなたの頭を包むのは難しいかもしれないので、私はdiagram このシナリオの抽象メモリモデルを示します.からのメモリモデル表記法にゆるく従うPHP Language Specification .

この話の士気

エイリアスを含む配列をコピーしないようにしてください.動作はランタイム依存であり、動作は予期しないものではないかもしれません.PHPの言語仕様から引用する

For portability, it is generally recommended that programs written in PHP should avoid performing value assignment with a right-hand side that is an array with one or more elements or sub-elements that have an alias relationship.

PHP Language Specification, https://phplang.org/spec/04-basic-concepts.html

ラッピング

私が最初に言ったように、あなたが循環配列を確実に見つけるための解決に興味があるならば、それは非常に単純です、そして、私は約束します.
このポストからすべてのコードサンプルを見つけることができますGitHub repository .

関連業務

Copy-on-write in the PHP language (2009), Akihiko Tozawa, Michiaki Tatsubori, Tamiya Onodera, Yasuhiko Minamide

郵便Why it is impossible to detect cyclic arrays in pure PHP 最初に現れたhbgl .