ID: 35438
User updated by: csaba at alum dot mit dot edu
Reported By: csaba at alum dot mit dot edu
-Status: Feedback
+Status: Open
Bug Type: Unknown/Other Function
Operating System: Win XP Pro
PHP Version: 5CVS-2005-11-28 (snap)
New Comment:
Sorry Tony, truly I do not like submitting such a complicated example.
I tried to construct a simpler version before submitting and I wasn't
able to.
I tried to give an overview of how the code is supposed to work in the
three paragraphs just under the code itself in the original posting,
but I'll try a more detailed explanation with example here:
The original array starts off as ["B/", "file", "B/C/"]. Terminating
slashes indicate a directory. So the main directory had "B/" and
"file" in it, and "B/" has an empty subdirectory "B/C/".
I want the array to acquire the form ["B/", "B/C/", "file"] where the
"B/C/" follows the "B/" since it's a subdirectory, but the code has to
deal with more general situations (specifically, there may be filters
to weed out some of the entries in the original array). But all this
is just background in where $aDir is coming from. On to the code,
which which I'll try to illustrate by example.
The foreach starts off with ($i => $file) of
0 => B/
and the while tries to see if there are any directories above 'B/'.
There aren't so we're on to the next iteration.
1 => file
There are again no directories above 'file' so we're on to the next
iteration
2 => B/C/
This time the while sees a '/' (prior to the final one) so it knows
there is a higher level directory above 'B/C/', namely 'B/' (at this
point $slashPos=1).
The if tests to see if this higher level directory ($common='B/') is an
entry in $aDir. It is, with $key=0 (in the more general case, specific
ancestor directories are not guaranteed because of possible filters) so
we get to the body of the if.
Now the entries in $aDir from 0 to $i-1 are in DFS order (because that
is what the function is producing). This means that the descendants of
the (or any given) ancestor will be grouped in a contiguous block just
after said ancestor. We can test for this block by checking for (with
the for loop) the first entry of which $common, the ancester, is not
the initial starting substring (which is what the if is doing). In our
example, this happens right away with "file" so that $j=1 and we break
out of the for loop.
Thus we have identified where the current entry being processed ($i=2;
$file="B/C/") should go (just before position $j=1). So we snip out
the current entry with array_splice($aDir, $i, 1) and we insert it to
position $j with array_splice($aDir, $j, 0, array_splice($aDir, $i,
1))
This correctly gives us $aDir = ["B/", "B/C/", "file"] as the print and
var_dump show. At this point we are ready to continue with the foreach,
hence the continue 2;
Unfortunately, the foreach loop has been reset at this point and gives
($i=0; $file="B/"). We'll wind up in an infinite loop, but that is not
the issue - the resetting of the foreach is what is in question.
Tony, I'm happy to answer further questions, but I can't figure out how
to simplify my example currently, though I wish I could.
Csaba
Previous Comments:
------------------------------------------------------------------------
[2005-11-28 12:35:08] [EMAIL PROTECTED]
Are you able to understand your code yourself?
Can you make it CLEAR, so I don't have to spend half of the day trying
to get what this code does?
------------------------------------------------------------------------
[2005-11-28 12:32:52] csaba at alum dot mit dot edu
<?php
$aDir = array("B/", "file", "B/C/");
var_dump($aDir); print "<br>\n";
bfs2dfs($aDir);
function bfs2dfs(&$aDir) {
foreach ($aDir as $i => $file) {
print "$i: $file<br>\n";
$slashPos = strlen($file)-1; // final slash pos
while (($slashPos = strrpos($file, "/",
$slashPos-strlen($file)-1))!==false)
if (($key=array_search($common=substr($file,
0,$slashPos+1),$aDir))!==false) {
for ($j=$key+1;$j<$i;++$j)
if ($common!=substr($aDir[$j],0, $slashPos+1)) break;
array_splice($aDir, $j, 0, array_splice($aDir, $i, 1));
print "after splice with (i, j, file) as ($i, $j, $file)<br>\n";
var_dump($aDir);
print "<br>\n";
continue 2; }}
}
?>
------------------------------------------------------------------------
[2005-11-28 12:14:04] [EMAIL PROTECTED]
Thank you for this bug report. To properly diagnose the problem, we
need a short but complete example script to be able to reproduce
this bug ourselves.
A proper reproducing script starts with <?php and ends with ?>,
is max. 10-20 lines long and does not require any external
resources such as databases, etc.
If possible, make the script source available online and provide
an URL to it here. Try to avoid embedding huge scripts into the report.
------------------------------------------------------------------------
[2005-11-28 04:33:42] csaba at alum dot mit dot edu
Description:
------------
I apologize in advance if this is not a bug, but I've narrowed it down
as far as I can and can't see the problem, so here goes...
I have an array that essentially contains the results of a (BFS)
breadth first search, a recursive directory listing. I want to
represent the heirarchical nature of the listing which means that I
want the results of the BFS converted to a DFS (depth first search)
format. I accomplish this by means of a double loop. The actual
transpositioning of the array elements happens by means of a double
array_splice: Use an inner array_splice to cut out a single entry
(which returns that entry) and then splice that in using the outer
array_splice. In fact, this works when the code is implemented at the
top level.
However, if I encapsulate the code in a function which passes $aDir by
reference, and then call the function, I wind up in an infinite loop.
The double splice is performed just fine, but then outer loop counter
($i) resets upon the next pass through the foreach, whereas this does
not happen if the code is not encapsulated within a function.
After spending some time on this, I can't spot the reason. Now I know
all bets are off you are modifying the array (which is the reason for
the advance apology), but the behaviour difference of top level vs.
function seemed interesting enough to warrant a report. I can
additionally say that this is specific to foreach and pass by
reference. If I replace the foreach with a
for ($i=0;$i<sizeof($aDir);++$i) {
$file = $aDir[$i];
then the code works as expected.
Also, if I keep the foreach but declare the bfs2dfs with
function bfs2dfs ($aDir) {
then the code also works as expected.
It is only the pass by reference, foreach version that goes into the
infinite loop.
Sincerely,
Csaba Gabor from Vienna
Reproduce code:
---------------
$aDir = array("B/", "file", "B/C/");
var_dump($aDir); print "<br>\n";
bfs2dfs($aDir);
function bfs2dfs(&$aDir) {
foreach ($aDir as $i => $file) {
print "$i: $file<br>\n";
$slashPos = strlen($file)-1; // final slash pos
while (($slashPos = strrpos($file, "/",
$slashPos-strlen($file)-1))!==false)
if (($key=array_search($common=substr($file,
0,$slashPos+1),$aDir))!==false) {
for ($j=$key+1;$j<$i;++$j)
if ($common!=substr($aDir[$j],0,
$slashPos+1))
break;
array_splice($aDir, $j, 0,
array_splice($aDir, $i, 1)); print "after
splice with (i,
j, file) " .
"as ($i, $j, $file)<br>\n";
var_dump($aDir);
print "<br>\n";
continue 2; }}
}
The idea behind this code is that we march through the array and each
time we encounter a file or dir, we move it to be the last child (of
already encountered children) of the most immediate (already
encountered) ancestor.
We do this by peeling off lower level subdirectories one after another
(that's what the while does) and see if what remains has already been
encountered (that's what the first if tests), hence processed. If so,
we march forward from that point (the for loop), checking to see (the
second if) when we are no longer a descendent of this ancestor. That
gives the position to insert the current file, which is done by means
of the double array_splice.
Again, if I comment out the function definition line and its closing
'}' and the bfs2dfs($aDir) call, the code works as expected. If the
foreach is replace by a for, the code works as expected, and if the
function declares $aDir by value instead of &$aDir by ref, the code
also works as expected.
Expected result:
----------------
array(3) { [0]=> string(2) "B/" [1]=> string(4) "file" [2]=>
string(4) "B/C/" }
0: B/
1: file
2: B/C/
after splice with (i, j, file) as (2, 1, B/C/)
array(3) { [0]=> string(2) "B/" [1]=> string(4) "B/C/" [2]=> string(4)
"file" }
Actual result:
--------------
exactly the same as with the expected result, but then it continues
looping infinitely with the following:
0: B/
1: B/C/
after splice with (i, j, file) as (1, 1, B/C/)
array(3) { [0]=> string(2) "B/" [1]=> string(4) "B/C/" [2]=> string(4)
"file" }
The interesting thing here is not the infinite loop, but the fact that
the loop counter ($i) reset to 0.
------------------------------------------------------------------------
--
Edit this bug report at http://bugs.php.net/?id=35438&edit=1
