[FEATURE REQUEST] _array_walk_recursive with path and reference processing

[gzhegow1991]

Description

1. RecursiveArrayIterator + RecursiveIteratorIterator still works without path/level collection
2. flags SELF_FIRST/CHILD_FIRST works strange:
   2.1. SELF_FIRST returns "DEPTH_FIRST + as-is" (traverse using stack)
   2.2. CHILD_FIRST returns unpredictable values, guess it should returns [ child first, then all parents ], so:
   2.2.1. first return non-arrays
   2.2.2. then empty arrays
   2.2.3. then arrays.
   Instead it returns child-parent-child-parent-child-parent-parent-parent.
   At least it should return or:
   a) child-child-child-parent-parent-parent-parent
   b) child-parent-parent-child-parent-parent-child-parent
   Instead it returns unpredictable collapse of two expectations. Maybe because variant (b) requires repeating of parents after each child, and the iterator tries to output non-repeating just in time, and repeating - after all non-repeated is yielded.

To return non-arrays you have to first traverse arrays, so if you try to change order of yield you non-expectedly await until iterator finished the job for at least one branch. If tree is "unlimited", i mean [ buiding tree at runtime ] its possible to never reach any child and trap to unlimited cycle without any child received. Thats non-practical case, runtime error i guess, btw. And as the point, changing yield order is not an opportunity of traversal, but opportunity of sort results of that traversal.

Main benefit - receive path of the element, and use breadth-first to traverse parents before the children. If you process tree - you sometimes needed to traverse parents tree, but if you print tree - you most of times needed depth-traversal. Its not about child/self first stuff.

<?php
/**
 * array_walk_recursive, designed for:
 * - receive path to the element (and level of the tree using count() function)
 * - replace value or parent by reference (and possible retraverse that replacement) (use case: object-to-array then traverse children)
 * - traverse depth-first/breadth-first, т.е. (1 -> 1.1 -> 2 -> 2.1) vs (1 -> 2 -> 1.1 -> 2.1)
 * - include/exclude leaves/empty-arrays/parents to the output
 *
 * @param array $array
 * @param int     $flags
 *
 * @return Iterator<array, mixed>|Generator<array, mixed>
 */
define('_ARRAY_WALK_DEPTH_FIRST', 0b00000001);
define('_ARRAY_WALK_BREADTH_FIRST', 0b00000010);
define('_ARRAY_WALK_WITH_LEAVES', 0b00000100);
define('_ARRAY_WALK_WITHOUT_LEAVES', 0b00001000);
define('_ARRAY_WALK_WITH_EMPTY_ARRAYS', 0b00010000);
define('_ARRAY_WALK_WITHOUT_EMPTY_ARRAYS', 0b00100000);
define('_ARRAY_WALK_WITH_PARENTS', 0b01000000);
define('_ARRAY_WALK_WITHOUT_PARENTS', 0b10000000);
function &_array_walk_recursive(array &$array, int $flags = null) : \Generator
{
    if (! $array) return;

    $flags = $flags ?? 0;

    $isModeFirst = _ARRAY_WALK_DEPTH_FIRST | _ARRAY_WALK_BREADTH_FIRST;
    $isDepthFirst = (bool) ($flags & _ARRAY_WALK_DEPTH_FIRST);
    $isBreadthFirst = (bool) ($flags & _ARRAY_WALK_BREADTH_FIRST);
    $_both = $flags & $isModeFirst;
    if (($_both === 0) || ($_both === $isModeFirst)) {
        $isDepthFirst = true;
        $isBreadthFirst = false;
    }

    $isLeaves = _ARRAY_WALK_WITH_LEAVES | _ARRAY_WALK_WITHOUT_LEAVES;
    $withLeaves = (bool) ($flags & _ARRAY_WALK_WITH_LEAVES);
    $_both = $flags & $isLeaves;
    if (($_both === 0) || ($_both === $isLeaves)) {
        $withLeaves = true;
    }

    $isEmptyArrays = _ARRAY_WALK_WITH_EMPTY_ARRAYS | _ARRAY_WALK_WITHOUT_EMPTY_ARRAYS;
    $withEmptyArrays = (bool) ($flags & _ARRAY_WALK_WITH_EMPTY_ARRAYS);
    $_both = $flags & $isEmptyArrays;
    if (($_both === 0) || ($_both === $isEmptyArrays)) {
        $withEmptyArrays = false;
    }

    $isParents = _ARRAY_WALK_WITH_PARENTS | _ARRAY_WALK_WITHOUT_PARENTS;
    $withParents = (bool) ($flags & _ARRAY_WALK_WITH_PARENTS);
    $_both = $flags & $isParents;
    if (($_both === 0) || ($_both === $isParents)) {
        $withParents = false;
    }

    $queue = [];
    $stack = [];
    if ($isBreadthFirst) {
        $buffer =& $queue;
    } elseif ($isDepthFirst) {
        $buffer =& $stack;
    }

    // > src, path
    $buffer[] = [ &$array, [] ];

    $isRoot = true;
    while ( ! empty($buffer) ) {
        if ($isBreadthFirst) {
            $cur = array_shift($buffer);
        } elseif ($isDepthFirst) {
            $cur = array_pop($buffer);
        }

        $isEmpty = empty($cur[ 0 ]);
        $isArray = is_array($cur[ 0 ]);

        $isLeaf = ! $isArray;
        $isEmptyArray = $isArray || $isEmpty;
        $isParent = $isArray && ! $isEmpty;

        if (! $isRoot) {
            if (false
                || ($withLeaves && $isLeaf)
                || ($withEmptyArrays && $isEmptyArray)
                || ($withParents && $isParent)
            ) {
                yield $cur[ 1 ] => $cur[ 0 ];

                // > value could be changed by reference
                $isEmpty = empty($cur[ 0 ]);
                $isArray = is_array($cur[ 0 ]);

                $isParent = $isArray && ! $isEmpty;
            }
        }

        if ($isParent) {
            if ($isBreadthFirst) {
                reset($cur[ 0 ]);

            } elseif ($isDepthFirst) {
                end($cur[ 0 ]);
            }

            while ( null !== ($kk = key($cur[ 0 ])) ) {
                $fullpath = $cur[ 1 ];
                $fullpath[] = $kk;

                $buffer[] = [ &$cur[ 0 ][ $kk ], $fullpath ];

                if ($isBreadthFirst) {
                    next($cur[ 0 ]);

                } elseif ($isDepthFirst) {
                    prev($cur[ 0 ]);
                }
            }
        }

        $isRoot = false;
    }
}

[gzhegow1991]

So, overengineered version of PHP's RecursiveIteratorIterator CHILD_FIRST behavior, not sure it could be required by any person, but it works like that (or could simple internally use recursive call + iterator object creation call):

<?php

$arr = [ [ '1' ], [ [ '1.1' ], [ [ '1.1.1' ], [ [ '1.1.1.1' ] ] ] ]];

function &_array_walk_recursive_child_first(array &$array) {
	$tree = [];

	$stack = [];
	$stack[] = [ $array, [], [] ];
	
	$isRoot = true;
	while (! empty($stack)) {
		$cur = array_pop($stack);
		
		$k = 0;
		if (! empty($cur[1])) {
			end($cur[1]);
			$k = key($cur[1]);
		}
		
		$isEmpty = empty($cur[0]);
		$isArray = is_array($cur[0]);
		
		if ($isArray && ! $isEmpty) {
			end($cur[0]);
			while (null !== ($kk = key($cur[0]))) {
                                // > we collect fullpath to just build keys into branch/tree stuff or we have to use weakmap with array as key
				$path = $cur[2];
				$fullpath = $path;
				$fullpath[] = $kk;
				
				$pathString = implode("\0", $path);
				$fullpathString = implode("\0", $fullpath);

                                // > we collect current branch to output certain one
				$branch = $cur[1];
				$branch[ $fullpathString ] =& $cur[0][$kk];
				
                                // > we collect tree just to evade parent repeats on output
				$tree[ $pathString ][ $fullpathString ] = true; // > or debug, json_encode($cur[0][$kk]);
				
				$stack[] = [ &$cur[0][$kk], $branch, $fullpath ];
				
				prev($cur[0]);
			}
			
		} else {
                        // > output only that children from the branch that is only-child of its parent in the tree
			end($cur[1]);
			while (null !== ($fullpathString = key($cur[1]))) {
				$fullpath = explode("\0", $fullpathString);

			 	if (empty($tree[ $fullpathString ])) {
			 		yield $fullpath => $cur[1][ $fullpathString ];
			 		
					$path = $fullpath;
					array_pop($path);
					$pathString = implode("\0", $path);
				 	unset($tree[ $pathString ][ $fullpathString ]);
				 	if (empty($tree[ $pathString ])) {
				 		unset($tree[ $pathString ]);
				 	}			 		
			 	}
			 	
			 	prev($cur[1]);
			}
		}
		
		$isRoot = false;
	}
}

foreach (_array_walk_recursive_child_first($arr) as $path => $val) {
	var_dump(json_encode($path) . ' => ' . json_encode($val));
}

// string(16) "["0","0"] => "1""
// string(14) "["0"] => ["1"]"
// string(22) "["1","0","0"] => "1.1""
// string(20) "["1","0"] => ["1.1"]"
// string(28) "["1","1","0","0"] => "1.1.1""
// string(26) "["1","1","0"] => ["1.1.1"]"
// string(34) "["1","1","1","0","0"] => "1.1.1.1""
// string(32) "["1","1","1","0"] => ["1.1.1.1"]"
// string(30) "["1","1","1"] => [["1.1.1.1"]]"
// string(38) "["1","1"] => [["1.1.1"],[["1.1.1.1"]]]"
// string(44) "["1"] => [["1.1"],[["1.1.1"],[["1.1.1.1"]]]]"

Any needs of trees is covered with filtering results and selecting breadth/depth first mode.
But for complete example of the thing i had just put code here.

[bancer]

... not sure it could be required by any person ...

En example scenario where this can be used: rename all children folders recursively from uppercase to lowercase. Children should be renamed first otherwise "UnexpectedValueException: RecursiveDirectoryIterator::__construct(/path/to/Uppercase/Folders): Failed to open directory: No such file or directory" exception is thrown. Ref.: cakephp/upgrade#281

[gzhegow1991]

You're right, so above i've posted "alpha" of the children first.

Its like _itertools_reverse() that MUST internally call iterator_to_array() so if iterator is infinite - causes memory overflow or unlimited waiting.

To rename folders you have to build tree first... So you first call _array_walk to get all pathes, then walk the results, unable to get reversed order in single operation at runtime. The point of my topic is "this is two operations" but first of them is not required to be two-steps too...

Exactly if you need child_first - you have to create iterator, and wrap it in second iterator. Otherwise you can't do it with single one. Also you have to be sure that first iterator has countable number of items, otherwise you never reach child first order... Or maybe it could be simplified to one branch that potentially could be unlimited.

Guess i need to implement the flag that is "processing branch is done", and inside foreach an user could check if level becomes lower that was in previous iteration.

[gzhegow1991]

Implementation

define('_ARRAY_WALK_MODE_DEPTH_FIRST', 1 << 0);
define('_ARRAY_WALK_MODE_BREADTH_FIRST', 1 << 1);
define('_ARRAY_WALK_SORT_SELF_FIRST', 1 << 2);
define('_ARRAY_WALK_SORT_PARENT_FIRST', 1 << 3);
define('_ARRAY_WALK_SORT_CHILD_FIRST', 1 << 4);
define('_ARRAY_WALK_WITH_LEAVES', 1 << 5);
define('_ARRAY_WALK_WITHOUT_LEAVES', 1 << 6);
define('_ARRAY_WALK_WITH_EMPTY_ARRAYS', 1 << 7);
define('_ARRAY_WALK_WITHOUT_EMPTY_ARRAYS', 1 << 8);
define('_ARRAY_WALK_WITH_PARENTS', 1 << 9);
define('_ARRAY_WALK_WITHOUT_PARENTS', 1 << 10);
/**
 * array_walk_recursive, позволяющий:
 * - получить путь до элемента
 * - подменить значение по ссылке
 * - сделать обход в ширину/глубину, т.е. (1 -> 1.1 -> 2 -> 2.1) => (1 -> 2 -> 1.1 -> 2.1)
 * - пройти с потомками/пустыми-массивами/родителями
 *
 * @param array    $array
 * @param int|null $flags
 *
 * @return \Iterator<array<int|string>, mixed>|Generator<array<int|string>, mixed>
 */
function &_array_walk(array &$array, int $flags = null) : \Generator
{
    if (! $array) return;

    $flags = $flags ?? 0;

    $isModeDepthFirst = (bool) ($flags & _ARRAY_WALK_MODE_DEPTH_FIRST);
    $isModeBreadthFirst = (bool) ($flags & _ARRAY_WALK_MODE_BREADTH_FIRST);
    $sum = $isModeDepthFirst + $isModeBreadthFirst;
    if (! $sum || ($sum > 1)) {
        $isModeDepthFirst = true;
        $isModeBreadthFirst = false;
    }

    $isSortSelfFirst = (bool) ($flags & _ARRAY_WALK_SORT_SELF_FIRST);
    $isSortParentFirst = (bool) ($flags & _ARRAY_WALK_SORT_PARENT_FIRST);
    $isSortChildFirst = (bool) ($flags & _ARRAY_WALK_SORT_CHILD_FIRST);
    $sum = $isSortSelfFirst + $isSortParentFirst + $isSortChildFirst;
    if (! $sum || ($sum > 1)) {
        $isSortSelfFirst = true;
        $isSortParentFirst = false;
        $isSortChildFirst = false;
    }

    $isWithLeaves = (bool) ($flags & _ARRAY_WALK_WITH_LEAVES);
    $isWithoutLeaves = (bool) ($flags & _ARRAY_WALK_WITHOUT_LEAVES);
    $sum = $isWithLeaves + $isWithoutLeaves;
    if (! $sum || ($sum > 1)) {
        $isWithLeaves = true;
        $isWithoutLeaves = false;
    }
    $withLeaves = $isWithLeaves && ! $isWithoutLeaves;
    unset($sum);

    $isWithoutEmptyArrays = (bool) ($flags & _ARRAY_WALK_WITHOUT_EMPTY_ARRAYS);
    $isWithEmptyArrays = (bool) ($flags & _ARRAY_WALK_WITH_EMPTY_ARRAYS);
    $sum = $isWithoutEmptyArrays + $isWithEmptyArrays;
    if (! $sum || ($sum > 1)) {
        $isWithoutEmptyArrays = true;
        $isWithEmptyArrays = false;
    }
    $withEmptyArrays = $isWithEmptyArrays && ! $isWithoutEmptyArrays;
    unset($sum);

    $isWithoutParents = (bool) ($flags & _ARRAY_WALK_WITHOUT_PARENTS);
    $isWithParents = (bool) ($flags & _ARRAY_WALK_WITH_PARENTS);
    $sum = $isWithoutParents + $isWithParents;
    if (! $sum || ($sum > 1)) {
        $isWithoutParents = true;
        $isWithParents = false;
    }
    $withParents = $isWithParents && ! $isWithoutParents;
    unset($sum);

    if ($isSortSelfFirst) {
        $fnUsort = null;

    } elseif ($isSortParentFirst) {
        $fnUsort = static function ($a, $b) {
            $isParentA = is_array($a) && ! empty($a);
            $isParentB = is_array($b) && ! empty($b);

            return $isParentA <=> $isParentB;
        };

    } elseif ($isSortChildFirst) {
        $fnUsort = static function ($a, $b) {
            $isParentA = is_array($a) && ! empty($a);
            $isParentB = is_array($b) && ! empty($b);

            return $isParentB <=> $isParentA;
        };

    } else {
        throw new \LogicException('Invalid `sort`');
    }

    if ($isModeDepthFirst) {
        $stack = [];
        $buffer_ =& $stack;

    } elseif ($isModeBreadthFirst) {
        $queue = [];
        $buffer_ =& $queue;

    } else {
        throw new \LogicException('Invalid `mode`');
    }

    // > value, fullpath, force
    $buffer_[] = [ &$array, [], false ];

    $isRoot = true;
    while ( ! empty($buffer_) ) {
        $cur = [];
        if ($isModeDepthFirst) {
            $cur = array_pop($buffer_);

        } elseif ($isModeBreadthFirst) {
            $cur = array_shift($buffer_);
        }

        $isYieldLeaf = ! is_array($cur[ 0 ]);
        $isYieldParent = ! $isRoot && ! $isYieldLeaf && ! empty($cur[ 0 ]);
        $isYieldEmptyArray = ! $isRoot && ! $isYieldLeaf && empty($cur[ 0 ]);

        if (
            ($withLeaves && $isYieldLeaf)
            || ($withParents && $isYieldParent)
            || ($withEmptyArrays && $isYieldEmptyArray)
        ) {
            $before = $cur[ 0 ];

            $ref_ =& $cur[ 0 ];

            yield $cur[ 1 ] => $ref_;

            if ($ref_ !== $before) {
                $isYieldParent = is_array($ref_) && ! empty($ref_);
            }

            unset($ref_);
            $ref_ = null;
        }

        if ($isRoot || $isYieldParent) {
            $children = $cur[ 0 ];

            if ($fnUsort) {
                uasort($children, $fnUsort);
            }

            $keys = [];
            if ($isModeDepthFirst) {
                end($children);
                while ( null !== ($kk = key($children)) ) {
                    $keys[] = $kk;

                    prev($children);
                }

            } elseif ($isModeBreadthFirst) {
                while ( null !== ($kk = key($children)) ) {
                    $keys[] = $kk;

                    next($children);
                }
            }

            unset($children);

            foreach ( $keys as $kk ) {
                $fullpath = $cur[ 1 ];
                $fullpath[] = $kk;

                $buffer_[] = [ &$cur[ 0 ][ $kk ], $fullpath ];
            }

            unset($keys);
        }

        $isRoot = false;
    }
}

Test

<?php

ini_set('memory_limit', '32M');

$arr = [ 1, [ 2, [ 3, [ 4, [ 51, 52, 53 ], 6 ], 7 ], 8 ], 9 ];

foreach ( _array_walk($arr, _ARRAY_WALK_SORT_CHILD_FIRST) as $path => $value ) {
    var_dump(json_encode($path) . ' | ' . json_encode($value));
}

// string(16) "[1,1,1,1,0] | 51"
// string(16) "[1,1,1,1,1] | 52"
// string(16) "[1,1,1,1,2] | 53"
// string(13) "[1,1,1,0] | 4"
// string(13) "[1,1,1,2] | 6"
// string(11) "[1,1,0] | 3"
// string(11) "[1,1,2] | 7"
// string(9) "[1,0] | 2"
// string(9) "[1,2] | 8"
// string(7) "[0] | 1"
// string(7) "[2] | 9"

Actually is not a "CHILD_FIRST" cus of theoretical part tree walking confusion, its implementation for "FIRST WALK CHILDREN THAT HAVE CHILDREN"