有没有一种方法可以在纯PHP中检测循环数组？

Question

我正在尝试在PHP中实现自己的序列化/var_dump样式函数。如果存在可能的循环数组，它似乎是不可能的（而有的确实存在）。

在最近的PHP版本中，var_dump似乎能够检测到循环数组：

php > $a = array();
php > $a[] = &$a;
php > var_dump($a);
array(1) {
  [0]=>
  &array(1) {
    [0]=>
    *RECURSION*
  }
}

如何在PHP中实现自己的序列化方法并检测相似之处？我不能只跟踪访问过的数组，因为在PHP中严格比较包含相同元素的不同数组返回true，并且比较循环数组会导致致命错误。

php > $b = array(1,2);
php > $c = array(1,2);
php > var_dump($b === $c);
bool(true)
php > $a = array();
php > $a[] = &$a;
php > var_dump($a === $a);
PHP Fatal error:  Nesting level too deep - recursive dependency? in php shell code on line 1

我一直在寻找一种找到数组的唯一标识符（指针）的方法，但我找不到。spl_object_hash只适用于对象，而不是数组。如果我将多个不同的数组强制转换为对象，则它们都会获得相同的spl_object_hash值（为什么？）。

编辑：

对每个数组调用print_r、var_dump或serialize，然后使用某种机制检测这些方法检测到的递归存在与否，是一个算法复杂度的噩梦，并且基本上会使任何使用过慢以至于在大型嵌套数组上不实用。

已接受答案：

我接受下面的答案，它首先建议暂时更改数组以查看它是否与另一个数组相同。这回答了“如何比较两个数组的身份”的问题，从而递归检测就变得简单了。

- postfuturist

---

答案将是：你不能。请参见检查对象/数组是否为引用。没有指针类似的引用比较，因此也无法检测循环。在您的情况下更好的解决方法可能是通过其中一个本地函数（json_decode(json_encode())）将其转换，以摆脱引用，并且仅在之后应用自己的序列化工具。 - mario

现在，连PHPUnit也在使用临时“标记”方法来检测数组递归。 - postfuturist

相关的 Bug #55564。 - Kontrollfreak

Answer 1

下面的isRecursiveArray(array)方法可以检测循环/递归数组。它通过临时在数组末尾添加包含已知对象引用的元素来跟踪已访问的数组。如果您需要编写序列化方法，请更新您的主题问题，并在问题中提供样本序列化格式。

function removeLastElementIfSame(array & $array, $reference) {
    if(end($array) === $reference) {
        unset($array[key($array)]);
    }
}

function isRecursiveArrayIteration(array & $array, $reference) {
    $last_element   = end($array);
    if($reference === $last_element) {
        return true;
    }
    $array[]    = $reference;

    foreach($array as &$element) {
        if(is_array($element)) {
            if(isRecursiveArrayIteration($element, $reference)) {
                removeLastElementIfSame($array, $reference);
                return true;
            }
        }
    }

    removeLastElementIfSame($array, $reference);

    return false;
}

function isRecursiveArray(array $array) {
    $some_reference = new stdclass();
    return isRecursiveArrayIteration($array, $some_reference);
}



$array      = array('a','b','c');
var_dump(isRecursiveArray($array));
print_r($array);



$array      = array('a','b','c');
$array[]    = $array;
var_dump(isRecursiveArray($array));
print_r($array);



$array      = array('a','b','c');
$array[]    = &$array;
var_dump(isRecursiveArray($array));
print_r($array);



$array      = array('a','b','c');
$array[]    = &$array;
$array      = array($array);
var_dump(isRecursiveArray($array));
print_r($array);

- lightster

---

我认为暂时改变数组可能是测试两个数组是否相同的唯一合理方法。这是第一个建议采用这种方法的答案，所以我会接受它。 - postfuturist

如果引用循环的变量丢失，也能检测到循环引用吗？例如，以下代码会导致无限循环（直到内存耗尽）：$array = [[&$array]]; $copy = $array; unset($array); isRecursiveArray($copy); - Kontrollfreak

Answer 2

有趣的方法（我知道这很愚蠢 :))，但是你可以修改它并跟踪递归元素的“路径”。这只是一个想法 :) 基于串行化字符串的属性，在递归开始时，它将与原始数组的字符串相同。正如你所看到的-我尝试了许多不同的变化，可能会有一些东西能够'欺骗'它，但它会'检测'所有列出的递归。而且我没有尝试包含对象的递归数组。

$a = array('b1'=>'a1','b2'=>'a2','b4'=>'a3','b5'=>'R:1;}}}');
$a['a1'] = &$a;
$a['b6'] = &$a;
$a['b6'][] = array(1,2,&$a);
$b = serialize($a); 
print_r($a);
function WalkArrayRecursive(&$array_name, &$temp){
    if (is_array($array_name)){
        foreach ($array_name as $k => &$v){
           if (is_array($v)){
                if (strpos($temp, preg_replace('#R:\d+;\}+$#', '', 
                               serialize($v)))===0) 
                { 
                  echo "\n Recursion detected at " . $k ."\n"; 
                  continue; 
                }
                WalkArrayRecursive($v, $temp);
            }
        }
    }
}
WalkArrayRecursive($a, $b);

regexp是针对递归元素位于数组“末尾”的情况。是的，这个递归与整个数组有关。可以递归子元素，但现在想太晚了。某种程度上，应该检查数组的每个元素是否存在递归子元素。同样的方式，通过print_r函数的输出或在序列化字符串中查找递归的特定记录（R:4;}之类的）。然后从那个元素开始跟踪，通过我的脚本比较下面的所有内容。所有这些只是为了检测递归开始的位置，而不仅仅是确定是否存在递归。

附：但我认为最好的方法是编写自己的反序列化函数，从php本身创建的序列化字符串中创建。

- Cheery

Answer 3

这是我的方法。关键是将数组通过引用传递给递归函数simple_var_dump()，并使用一个标记（在本例中为“iterating_in_a_higher_level”）来区分正在更高嵌套级别中迭代的数组。

#!/usr/bin/php
<?php

   function simple_var_dump(&$var, $depth = 0)
   {
      if (!is_array($var)) {
         if (is_scalar($var)) {
            return (string)$var;
         } else {
            return '?';
         }
      }
      if (isset($var['__iterating_in_a_higher_level__'])) {
         $r = 'array(' . (count($var)-1) . ')';
         return $r . ' *RECURSION*';
      }
      $r = 'array(' . count($var) . ')';
      $var['__iterating_in_a_higher_level__'] = true;
      foreach ($var as $key => &$value) {
         if ($key !== '__iterating_in_a_higher_level__') {
            $r .= "\n" . str_repeat('  ', $depth + 1) . '[' . $key . '] => ' . simple_var_dump($value, $depth + 1);
         }
      }
      unset($var['__iterating_in_a_higher_level__']);
      return $r;
   }

   // example:
   //
   $a = [new stdClass(), &$a, 30, [40, [[&$a]]], [1, true, &$a], []];
   echo simple_var_dump($a) . "\n";

输出：

array(6)
  [0] => ?
  [1] => array(6) *RECURSION*
  [2] => 30
  [3] => array(2)
    [0] => 40
    [1] => array(1)
      [0] => array(1)
        [0] => array(6) *RECURSION*
  [4] => array(3)
    [0] => 1
    [1] => 1
    [2] => array(6) *RECURSION*
  [5] => array(0)

- richi

Answer 4

我的方法是使用一个临时数组来保存已经迭代过的所有对象的副本，就像这样：

// We use this to detect recursion.
global $recursion;
$recursion = [];

function dump( $data, $label, $level = 0 ) {
    global $recursion;

    // Some nice output for debugging/testing...
    echo "\n";
    echo str_repeat( "  ", $level );
    echo $label . " (" . gettype( $data ) . ") ";

    // -- start of our recursion detection logic
    if ( is_object( $data ) ) {
        foreach ( $recursion as $done ) {
            if ( $done === $data ) {
                echo "*RECURSION*";
                return;
            }
        }

        // This is the key-line: Remember that we processed this item!
        $recursion[] = $data;
    }
    // -- end of recursion check

    if ( is_array( $data ) || is_object( $data ) ) {
        foreach ( (array) $data as $key => $item ) {
            dump( $item, $key, $level + 1 );
        }
    } else {
        echo "= " . $data;
    }
}

以下是一些快速演示代码，以说明它的工作原理：

$obj = new StdClass();
$obj->arr = [];
$obj->arr[] = 'Foo';
$obj->arr[] = $obj;
$obj->arr[] = 'Bar';
$obj->final = 12345;
$obj->a2 = $obj->arr;

dump( $obj, 'obj' );

此脚本将生成以下输出：

obj (object) 
  arr (array) 
    0 (string) = Foo
    1 (object) *RECURSION*
    2 (string) = Bar
  final (integer) = 12345
  a2 (array) 
    0 (string) = Foo
    1 (object) *RECURSION*
    2 (string) = Bar

- Philipp

---

问题是关于循环数组，而不是对象。如果这样的数组被传递给您的 dump() 函数，它会无限循环。 - Kontrollfreak

Answer 5

它不够优雅，但可以解决你的问题（至少如果你没有人将*递归*用作值）。

<?php
$a[] = &$a;
if(strpos(print_r($a,1),'*RECURSION*') !== FALSE) echo 1;

- dvicino

---

如果你的数组中出现了字符串“RECURSION”，那么它就无法正常工作...虽然这种情况很少见，但确实有可能发生。 - deceze

是的，当我谈到“递归”作为一种值时，我的意思就是这个。无论如何，您可以通过迭代数组并检查该值来添加对该情况的检查，并且您得到的迭代次数限制取决于print_r输出给您的行数。 - dvicino

嗯，那种方式（极其低效）可以检测到“某处”存在递归，但并不能真正解决我的使用情况。 - postfuturist

正如Mario之前所说，没有办法检测引用，print_r使用了您无法访问的内部，这是低效的，但是这已经是最好的了 :( - dvicino