Есть ли способ обнаружить круговые массивы в чистом PHP? - PullRequest
Новая
       39

Есть ли способ обнаружить круговые массивы в чистом PHP?

18 голосов
/ 02 февраля 2012

Я пытаюсь реализовать свою собственную функцию стиля сериализации / var_dump в PHP. Кажется невозможным, если есть возможность создания круговых массивов (которые есть).

В последних версиях 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 (почему?).

EDIT:

Вызов print_r, var_dump или serialize для каждого массива, а затем использование какого-либо механизма для обнаружения наличия рекурсии, обнаруживаемой этими методами, - кошмар алгоритмической сложности, и, по сути, делает любое использование слишком медленным для практического применения на больших вложенных массивах.

ПРИНЯТО ОТВЕТ:

Я принял ответ ниже, который первым предложил временно изменить массив, чтобы увидеть, действительно ли он совпадает с другим массивом. Это отвечает на вопрос «как сравнить два массива на идентичность?» из которого обнаружение рекурсии тривиально.

Ответы [ 4 ]

5 голосов
/ 15 февраля 2012

Метод 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);
0 голосов
/ 01 мая 2017

Мой подход состоит в том, чтобы иметь временный массив, содержащий копию всех объектов, которые уже были повторены.вот так: 

// 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
0 голосов
/ 02 февраля 2012

Забавный метод (я знаю, что это глупо :)), но вы можете изменить его и отследить «путь» к рекурсивному элементу. Это всего лишь идея :) Исходя из свойства сериализованной строки, при запуске рекурсии будет то же самое, что и строка для исходного массива. Как вы можете видеть - я пробовал это на разных вариациях и, возможно, что-то может «обмануть» его, но он «обнаруживает» все перечисленные рекурсии. И я не пробовал рекурсивные массивы с объектами. 

$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;} что-то вроде этого). И трассировка должна начинаться с этого элемента, сравнивая все ниже по моему сценарию. Все это только в том случае, если вы хотите определить, где начинается рекурсия, а не только, имеете ли вы ее или нет.

ps: но лучше всего, как я думаю, написать свою собственную несериализованную функцию из serailized string, созданной самим php.

0 голосов
/ 02 февраля 2012

Это не элегантно, но решает вашу проблему (по крайней мере, если у вас нет человека, использующего * RECURSION * в качестве значения). 

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