[php-src] Issue #13630: [FEATURE REQUEST] _array_walk_recursive with path and reference processing
| From: | 6562680 | Date: | Fri, 08 Mar 2024 08:24:37 +0000 |
| Subject: | [php-src] Issue #13630: [FEATURE REQUEST] _array_walk_recursive with path and reference processing | ||
| Groups: | php.bugs | ||
| Request: | Send a blank email to php-bugs+get-246535@lists.php.net to get a copy of this message | ||
Issue: https://github.com/php/php-src/issues/13630
Author: 6562680
### 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.
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 btw, 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, позволяющий:
* - 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 from 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;
}
}
```