Fix RT #120600: Variable length lookbehind is not variable

Inside of study_chunk() we have to guard against infinite
recursion with recursive subpatterns. The existing logic
sort of worked, but didn't address all cases properly.

  qr/
    (?<W>a)
    (?<BB>
      (?=(?&W))(?<=(?&W))
    )
    (?&BB)
  /x;

The pattern in the test would fail when the optimizer
was expanding (&BB). When it recursed, it creates a bitmap
for the recursion it performs, it then jumps back to
the BB node and then eventually does the first (&W) call.
At this point the bit for (&W) would be set in the bitmask.
When the recursion for the (&W) exited (fake exit through
the study frame logic) the bit was not /unset/. When the parser
then entered the (&W) again it was treated as a nested and
potentially infinite length pattern.

The fake-recursion in study-chunk made it little less obvious
what was going on in the debug output.

By reorganizing the code and adding logic to unset the bitmap
when exiting this bug was fixed. Unfortunately this also revealed
another little issue with patterns like this:

  qr/x|(?0)/
  qr/(x|(?1))/

which forced the creation of a new bitmask for each branch.
Effectively study_chunk treats each branch as an independent
pattern, so when we are expanding (?1) via the 'x' branch
we dont want that to prevent us from detecting the infinite recursion
in the (?1) branch. If you were to think of trips through study_chunk
as paths, and [] as recursive processing you would get something like:

  BRANCH 'x' END
  BRANCH (?0) [ 'x' END ]
  BRANCH (?0) [ (?0) [ 'x' END ] ]
  ...

When we want something like:

  BRANCH 'x' END
  BRANCH (?0) [ 'x' END ]
  BRANCH (?0) [ (?0) INFINITE_RECURSION ]

So when we deal with a branch we need to make a new recursion bitmask.

diff --git a/regcomp.c b/regcomp.c
index 9c47bd9..5800d36 100644 (file)
--- a/regcomp.c
+++ b/regcomp.c
@@ -3345,8 +3345,14 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
 #ifdef DEBUGGING
     StructCopy(&zero_scan_data, &data_fake, scan_data_t);
 #endif
+    if (!recursed) {
+        Newxz(recursed, (((RExC_npar + 1)>>3) + 1), U8);
+        SAVEFREEPV(recursed);
+    }
 
     if ( depth == 0 ) {
+        /* Set up a bitmask of which recursive component we have
+         * already entered. */
         while (first_non_open && OP(first_non_open) == OPEN)
             first_non_open=regnext(first_non_open);
     }
@@ -3407,6 +3413,7 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
                SSize_t max1 = 0, min1 = SSize_t_MAX, num = 0;
                regnode_ssc accum;
                regnode * const startbranch=scan;
+                U8 *myrecursed= NULL;
 
                if (flags & SCF_DO_SUBSTR)
                    SCAN_COMMIT(pRExC_state, data, minlenp); /* Cannot merge strings after this. */
@@ -3440,10 +3447,16 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
                    if (flags & SCF_WHILEM_VISITED_POS)
                        f |= SCF_WHILEM_VISITED_POS;
 
+                    /* create a new recursed for this branch */
+                    if (!myrecursed) {
+                        Newx(myrecursed, (((RExC_npar + 1)>>3) + 1), U8);
+                        SAVEFREEPV(myrecursed);
+                    }
+                    Copy(recursed, myrecursed, (((RExC_npar + 1)>>3) + 1), U8);
                    /* we suppose the run is continuous, last=next...*/
                    minnext = study_chunk(pRExC_state, &scan, minlenp, &deltanext,
                                          next, &data_fake,
-                                         stopparen, recursed, NULL, f,depth+1);
+                                         stopparen, myrecursed, NULL, f,depth+1);
                    if (min1 > minnext)
                        min1 = minnext;
                    if (deltanext == SSize_t_MAX) {
@@ -3852,14 +3865,15 @@ S_study_chunk(pTHX_ RExC_state_t *pRExC_state, regnode **scanp,
                     start = RExC_rxi->program + 1;
                     end   = RExC_opend;
                 }
-                if (!recursed) {
-                    Newxz(recursed, (((RExC_npar)>>3) +1), U8);
-                    SAVEFREEPV(recursed);
-                }
-                if (!PAREN_TEST(recursed,paren+1)) {
-                   PAREN_SET(recursed,paren+1);
+
+                if (!PAREN_TEST(recursed,paren)) {
+                    /* we havent recursed into this paren yet, so recurse into it */
+                   DEBUG_STUDYDATA("set:", data,depth);
+                    PAREN_SET(recursed, paren);
                     Newx(newframe,1,scan_frame);
                 } else {
+                   DEBUG_STUDYDATA("inf:", data,depth);
+                    /* some form of infinite recursion, assume infinite length */
                     if (flags & SCF_DO_SUBSTR) {
                         SCAN_COMMIT(pRExC_state,data,minlenp);
                         data->longest = &(data->longest_float);
@@ -5031,6 +5045,13 @@ PerlIO_printf(Perl_debug_log, "LHS=%"UVdf" RHS=%"UVdf"\n",
        /* Else: zero-length, ignore. */
        scan = regnext(scan);
     }
+    /* If we are exiting a recursion we can unset its recursed bit
+     * and allow ourselves to enter it again - no danger of an
+     * infinite loop there. */
+    if (stopparen > -1 && recursed) {
+       DEBUG_STUDYDATA("unset:", data,depth);
+        PAREN_UNSET( recursed, stopparen);
+    }
     if (frame) {
         last = frame->last;
         scan = frame->next;

diff --git a/t/re/re_tests b/t/re/re_tests
index 9bd36ef..18a34dd 100644 (file)
--- a/t/re/re_tests
+++ b/t/re/re_tests
@@ -1840,5 +1840,7 @@ A+(*PRUNE)BC(?{}) AAABC   y       $&      AAABC
 /\N* /x        ab      y       $&      ab               # Under /x was ignoring the '*'
 /\N (?#comment) * /x   ab      y       $&      ab      # likewise
 
+# RT #120600: Variable length lookbehind is not variable
+(?<W>a)(?<BB>(?=(?&W))(?<=(?&W)))(?&BB)        aa      y       $&      a       # test repeated recursive patterns
 # Keep these lines at the end of the file
 # vim: softtabstop=0 noexpandtab