有没有办法在纯PHP中检测循环数组？

php arrays recursion circular-reference identity

2022-08-30 21:20:24

我正在尝试在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

我一直在寻找一种方法来查找数组的唯一id（指针），但我找不到一个。spl_object_hash仅适用于对象，不适用于数组。如果我将多个不同的数组投射到对象中，它们都会获得相同的spl_object_hash值（为什么？）。

编辑：

调用print_r，var_dump或在每个数组上序列化，然后使用某种机制来检测这些方法检测到的递归的存在，这是一个算法复杂性的噩梦，基本上会使任何使用都太慢，无法在大型嵌套数组上实现。

接受的答案：

我接受了下面的答案，这是第一个建议暂时改变数组以查看它是否确实与另一个数组相同。这回答了“我如何比较两个数组的标识？”，从中递归检测是微不足道的。

答案 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);

答案 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);

正则表达式适用于具有递归的元素位于数组的“末尾”的情况。而且，是的，这种递归与整个数组有关。可以对子元素进行递归，但是现在考虑它们为时已晚。不知何故，数组的每个元素都应该检查其子元素中的递归。同样的方式，如上所述，通过print_r函数的输出，或在序列化字符串中查找要递归的特定记录（类似如下）。跟踪应该从该元素开始，通过我的脚本比较下面的所有内容。所有这一切都只是当你想要检测递归开始的位置，而不仅仅是你是否拥有它。R:4;}

ps：但最好的事情应该是，正如我所认为的，从php本身创建的seleized字符串编写自己的非序列化函数。