순수한 PHP에서 순환 배열을 감지할 수 없는 이유

이 글은 소수의 PHP 프로그래머들만 관련될 수 있는 문제입니다. 그들은 사용자 정의 서열화 프로그램이나 다른 반복적인 그룹을 작성하려고 할 수도 있습니다.하지만 이 문제를 해결하려 할 때 흥미로운 PHP의 이상한 점을 발견했으니 강조할 만하다고 생각한다.
겸사겸사 한마디 하자면
순환수 그룹을 신뢰할 수 있는 해결 방안을 찾고 있을 뿐이고, 쿨한 PHP 괴벽을 놓치고 싶다면, 이 시리즈의 두 번째 부분으로 넘어가십시오.
우선, 우리의 용어를 정의합시다.이 글에서 우리는 매우 실용적인 정의를 지원할 수 있다. 수조는 순환적이며, 모든 항목과 하위 항목을 교체하는 것이 끝나지 않는다면.순환수조는 때때로 순환수조 또는 귀속수조라고도 부른다.몇 가지 예를 살펴보겠습니다.

// 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에서 대상을 대하는 것처럼 수조의 실례 표식을 비교할 수 없다는 것이다.두 변수가 같은 그룹을 인용하는지 확인하는 유일한 방법은 하나의 변수로 그룹을 표시한 다음에 다른 변수로 표시를 검사하는 것이다.따라서 만약에 우리가 이 과정에서 관건적인 결함을 찾을 수 있다면 순수 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*
  }
}

예상한 바와 같이, 덤프는 동일하지만, 하나의 그룹은 우리의 프로그램을 붕괴시키고, 다른 하나는 그렇지 않다.분명히 일이 이뿐만이 아니다.

실행 코드 어레이 내부에 무슨 일이 일어났는지

사진 작성자 출처cottonbro
프로그램에서 실제로 무슨 일이 일어났는지 알아보기 위해 printf 디버깅을 진행합시다.호출 시 함수 매개 변수를 덤프할 때마다 다음과 같은 출력이 제공됩니다(Pexels.

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
...

이 두 개의 수조 저장은 영원히 교체될 것이다.흥미로운 것은 만약 우리가 값을 통해 전달 함수 파라미터를 인용하지 않는다면, 우리는 앞에서 언급한 바와 같이 완전히 같은 출력을 얻을 수 있다는 것이다.이것은 일부 복제가 진행되고 있음을 나타낸다. 이것은 매우 이상하다. 왜냐하면 함수 코드만 보면 알 수 없기 때문이다.
함수 매개 변수보다 더 통찰력이 있는 것은 원시 입력 수조의 변화이다.모든 함수에 덤프를 호출할 때, 우리는 매우 이상한 것들을 볼 수 있다. (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) {
  }
}

...

이것은 좋은 예이지만, 우리는 수조의 저장이 함수가 호출될 때마다 더욱 깊어지는 것을 보았다.이 밖에 스크립트의 메모리 사용량은 시간의 추이에 따라 안정적으로 증가한다run code.이것은 우리가 호출 체인을 따라 아래로 내려갈 때, 실행할 때, 메모리의 순환 그룹을 타성적으로 구체화하는 것이라고 믿게 한다.그것은 또한 우리의 프로그램을 영원히 운행하게 하는 메커니즘을 설명할 것이다.
우리는 왜 수조가 이런 방식으로 운행되는지, 왜 그것이 로컬 구조의 수조와 같지 않은지 여전히 모른다.

실행 코드 배열을 신뢰할 수 없습니다.

사진 작성자 출처Sharath G.
일반적으로 수조의 작업 방식은 사람들이 예상한 것과 같다.그러나 인용을 포함하는 그룹 실행 값을 사용하면 예측성이 사라집니다."왜?"물어볼 수도 있어.이 코드를 보고 원하는 출력을 고려하십시오 (Pexels:

$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

run code에서 한 절은 이런 행위에 관한 것으로 수조의 값 부여 주제와 관련된다.요컨대 두 가지 중요한 요점은 우리의 문제와 관련이 있다.

소스 그룹에서 별명 (인용) 으로 사용되는 모든 항목은 값이나 인용 (실행할 때의 알고리즘에 의해 정의됨) 을 통해 목표 그룹에 분배됩니다.

$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.

이 두 가지 규칙을 통해 우리는 왜 함수is_cyclic가 국부 작용역에서 구성된 수조와 함수가 되돌아오는 수조의 행위가 다른지 합리적으로 해석할 수 있다.
첫 번째 상황에서, 수조에 대해 어떠한 값 부여도 실행하지 않았는데, 이것이 바로 함수의 행동이 예상과 일치하는 이유이다.
두 번째 상황에서 수조는 함수에서 값에 따라 되돌아와 국부 변수에 분배된다.복제가 지연되었습니다(규칙 2).우리가 그룹을 표시하려고 할 때, 실행할 때, 먼저 복사본을 만들고, 이 복사본은 표시를 받을 것이다. (규칙 2)복제를 실행하는 데는 복제 플러그인 그룹도 포함됩니다. 이것은 다시 지연되고 반복됩니다.매번 우리가 하나의 그룹을 표시할 때마다 새로운 복사본을 생성하고, 초기 그룹은 더욱 깊어진다.
나는 이것이 이해하기 어려울 수도 있다는 것을 알고 chapter 4 of the PHP Language Specification를 만들어서 이 장면의 추상적인 메모리 모델을 설명했다.그것은 대체로 diagram의 메모리 모델 표현법을 따른다.

PHP 언어 사양 이 이야기의 사기

별명을 포함하는 그룹을 복제하는 것을 최대한 피하십시오.이 동작은 실행할 때에 의존하며, 이 동작은 당신이 원하는 것이 아닐 수도 있습니다.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에 올라왔다.