make peep optimiser recurse mostly only shallowly

Long blocks of code that include logical or loop ops (i.e. those with
multiple 'branches' of ops, such as op_other, op_redo etc) cause
Perl_rpeep to recurse deeply and eventaully SEGV.

For example this crashes, due to the ENTERLOOP:

    eval ("{\$x = 1 }\n" x 10000)

The deep recursion happens because the processing of the entire rest of
the code occurs in within the nested call. For example in the code

    A && B; C; D; E;

the ops are structured as

A -> AND -> C -> D -> E
       \   /
         B

where AND->op_next points to C, while AND->op_other points to B.
rpeep() would normally process each op in the op_next sequence in turn
(i.e. A/AND/C/D/E), but when it reaches AND, it recursively calls
rpeep(B), which happens to then process B/C/D/E. Finally it returns,
and the parent rpeep processes C, finds it's already done, and exits.

Clearly, if C,D,E etc also contain conditional/loop ops, then the
recursion level gradually stacks up.

The fix for this is to add a small deferred queue to rpeep().
Whenever rpeep wants to recurse with op_other or op_lastop etc,
it instead adds it to the deferred queue. Only if the queue is full is
rpeep actually called. The hope is that by deferring, when we do
eventually process it, enough of the main op_next chain has already been
processed to ensure that the child rpeep returns very early.

In the example above, processing of AND causes B to be added to the queue,
and the main rpeep process continues processing C, D etc. Sometime later,
the queue becomes full and B is processed via a recursive call to rpeep.
B is processed, and op_next is followed to C, but C is marked as already
processed, so the child rpeep returns almost immediately.

For LOOP ops, I've stopped following op_redoop and op_nextop, since
AFAIKT the ops these point to will also be reachable vie op_next anyway.
op_lastop is the exception; in while(1){..} only op_lastop points to the
rest of the code block.

Note that this commit doesn't guarantee only shallow recursion, it just
makes deep recursion fairly unlikely.

Note also that this commit causes the order of the processing of op_next
chains to be altered; this can affect the ordering of compiler warnings
and fatal messages among potentially other things.

1 files changed, 12 insertions, 9 deletions

diff --git a/ext/XS-APItest/t/peep.t b/ext/XS-APItest/t/peep.t
index 08928c44c9..87d749b7ff 100644
--- a/ext/XS-APItest/t/peep.t
+++ b/ext/XS-APItest/t/peep.t
@@ -2,7 +2,7 @@
 
 use strict;
 use warnings;
-use Test::More tests => 9;
+use Test::More tests => 6;
 
 use XS::APItest;
 
@@ -20,14 +20,17 @@ is($record->[0], 'affe');
 is($rrecord->[0], 'affe');
 
 
-# peep got called for each root op of the branch
-$::moo = $::moo = 0;
+# A deep-enough nesting of conditionals defeats the deferring mechanism
+# and triggers recursion. Note that this test is sensitive to the details
+# rpeep: the main thing it is testing is that rpeep is called more than
+# peep; the details are less important.
+
+my $code =  q[my ($a,$b); $a =];
+$code .= qq{ \$b ? "foo$_" :} for (1..10);
+$code .= qq{ "foo11" };
 XS::APItest::peep_enable;
-eval q[my $foo = $::moo ? q/x/ : q/y/];
+eval $code;
 XS::APItest::peep_disable;
 
-is(scalar @{ $record }, 1);
-is(scalar @{ $rrecord }, 2);
-is($record->[0], 'y');
-is($rrecord->[0], 'x');
-is($rrecord->[1], 'y');
+is_deeply($record,  [ "foo11" ]);
+is_deeply($rrecord, [ qw(foo1 foo2 foo3 foo4 foo5 foo6 foo11) ]);