/[pcre]/code/trunk/pcre_exec.c

Diff of /code/trunk/pcre_exec.c

Parent Directory | Revision Log | View Patch Patch

-revision 681 by ph10,
Tue Sep  6 09:16:32 2011 UTC
+revision 835 by ph10,
Wed Dec 28 16:10:09 2011 UTC
 Line 277 
 enum { RM1=1, RM2,  RM3,  RM4,  RM5,  RM
         RM31,  RM32, RM33, RM34, RM35, RM36, RM37, RM38, RM39, RM40,
         RM41,  RM42, RM43, RM44, RM45, RM46, RM47, RM48, RM49, RM50,
         RM51,  RM52, RM53, RM54, RM55, RM56, RM57, RM58, RM59, RM60,
-        RM61,  RM62, RM63 };
+        RM61,  RM62, RM63, RM64, RM65, RM66 };
  /* These versions of the macros use the stack, as normal. There are debugging
  versions and production versions. Note that the "rw" argument of RMATCH isn't
 Line 775 
 for (;;)
      md->start_match_ptr = ecode + 2;
      RRETURN(MATCH_SKIP_ARG);
-     /* For THEN (and THEN_ARG) we pass back the address of the bracket or
+     /* For THEN (and THEN_ARG) we pass back the address of the opcode, so that
-     the alt that is at the start of the current branch. This makes it possible
+     the branch in which it occurs can be determined. Overload the start of
-     to skip back past alternatives that precede the THEN within the current
+     match pointer to do this. */
-     branch. */
      case OP_THEN:
      RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,
        eptrb, RM54);
      if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-     md->start_match_ptr = ecode - GET(ecode, 1);
+     md->start_match_ptr = ecode;
      MRRETURN(MATCH_THEN);
      case OP_THEN_ARG:
-     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode] + ecode[1+LINK_SIZE],
+     RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode] + ecode[1], offset_top,
-       offset_top, md, eptrb, RM58);
+       md, eptrb, RM58);
      if (rrc != MATCH_NOMATCH) RRETURN(rrc);
-     md->start_match_ptr = ecode - GET(ecode, 1);
+     md->start_match_ptr = ecode;
-     md->mark = ecode + LINK_SIZE + 2;
+     md->mark = ecode + 2;
      RRETURN(MATCH_THEN);
+     /* Handle an atomic group that does not contain any capturing parentheses.
+     This can be handled like an assertion. Prior to 8.13, all atomic groups
+     were handled this way. In 8.13, the code was changed as below for ONCE, so
+     that backups pass through the group and thereby reset captured values.
+     However, this uses a lot more stack, so in 8.20, atomic groups that do not
+     contain any captures generate OP_ONCE_NC, which can be handled in the old,
+     less stack intensive way.
+     Check the alternative branches in turn - the matching won't pass the KET
+     for this kind of subpattern. If any one branch matches, we carry on as at
+     the end of a normal bracket, leaving the subject pointer, but resetting
+     the start-of-match value in case it was changed by \K. */
+     case OP_ONCE_NC:
+     prev = ecode;
+     saved_eptr = eptr;
+     do
+       {
+       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM64);
+       if (rrc == MATCH_MATCH)  /* Note: _not_ MATCH_ACCEPT */
+         {
+         mstart = md->start_match_ptr;
+         markptr = md->mark;
+         break;
+         }
+       if (rrc == MATCH_THEN)
+         {
+         next = ecode + GET(ecode,1);
+         if (md->start_match_ptr < next &&
+             (*ecode == OP_ALT || *next == OP_ALT))
+           rrc = MATCH_NOMATCH;
+         }
+       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
+       ecode += GET(ecode,1);
+       }
+     while (*ecode == OP_ALT);
+     /* If hit the end of the group (which could be repeated), fail */
+     if (*ecode != OP_ONCE_NC && *ecode != OP_ALT) RRETURN(MATCH_NOMATCH);
+     /* Continue as from after the group, updating the offsets high water
+     mark, since extracts may have been taken. */
+     do ecode += GET(ecode, 1); while (*ecode == OP_ALT);
+     offset_top = md->end_offset_top;
+     eptr = md->end_match_ptr;
+     /* For a non-repeating ket, just continue at this level. This also
+     happens for a repeating ket if no characters were matched in the group.
+     This is the forcible breaking of infinite loops as implemented in Perl
+.005. */
+     if (*ecode == OP_KET || eptr == saved_eptr)
+       {
+       ecode += 1+LINK_SIZE;
+       break;
+       }
+     /* The repeating kets try the rest of the pattern or restart from the
+     preceding bracket, in the appropriate order. The second "call" of match()
+     uses tail recursion, to avoid using another stack frame. */
+     if (*ecode == OP_KETRMIN)
+       {
+       RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM65);
+       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
+       ecode = prev;
+       goto TAIL_RECURSE;
+       }
+     else  /* OP_KETRMAX */
+       {
+       md->match_function_type = MATCH_CBEGROUP;
+       RMATCH(eptr, prev, offset_top, md, eptrb, RM66);
+       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
+       ecode += 1 + LINK_SIZE;
+       goto TAIL_RECURSE;
+       }
+     /* Control never gets here */
      /* Handle a capturing bracket, other than those that are possessive with an
      unlimited repeat. If there is space in the offset vector, save the current
      subject position in the working slot at the top of the vector. We mustn't
-Line 838 
 for (;;)
+Line 919 
 for (;;)
          RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md,
            eptrb, RM1);
          if (rrc == MATCH_ONCE) break;  /* Backing up through an atomic group */
-         if (rrc != MATCH_NOMATCH &&
-             (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+         /* If we backed up to a THEN, check whether it is within the current
-           RRETURN(rrc);
+         branch by comparing the address of the THEN that is passed back with
+         the end of the branch. If it is within the current branch, and the
+         branch is one of two or more alternatives (it either starts or ends
+         with OP_ALT), we have reached the limit of THEN's action, so convert
+         the return code to NOMATCH, which will cause normal backtracking to
+         happen from now on. Otherwise, THEN is passed back to an outer
+         alternative. This implements Perl's treatment of parenthesized groups,
+         where a group not containing | does not affect the current alternative,
+         that is, (X) is NOT the same as (X|(*F)). */
+         if (rrc == MATCH_THEN)
+           {
+           next = ecode + GET(ecode,1);
+           if (md->start_match_ptr < next &&
+               (*ecode == OP_ALT || *next == OP_ALT))
+             rrc = MATCH_NOMATCH;
+           }
+         /* Anything other than NOMATCH is passed back. */
+         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
          md->capture_last = save_capture_last;
          ecode += GET(ecode, 1);
          if (*ecode != OP_ALT) break;
-Line 851 
 for (;;)
+Line 952 
 for (;;)
        md->offset_vector[offset+1] = save_offset2;
        md->offset_vector[md->offset_end - number] = save_offset3;
-       /* At this point, rrc will be one of MATCH_ONCE, MATCH_NOMATCH, or
+       /* At this point, rrc will be one of MATCH_ONCE or MATCH_NOMATCH. */
-       MATCH_THEN. */
-       if (rrc != MATCH_THEN && md->mark == NULL) md->mark = markptr;
+       if (md->mark == NULL) md->mark = markptr;
-       RRETURN(((rrc == MATCH_ONCE)? MATCH_ONCE:MATCH_NOMATCH));
+       RRETURN(rrc);
        }
      /* FALL THROUGH ... Insufficient room for saving captured contents. Treat
-Line 870 
 for (;;)
+Line 970 
 for (;;)
      /* VVVVVVVVVVVVVVVVVVVVVVVVV */
      /* Non-capturing or atomic group, except for possessive with unlimited
-     repeat. Loop for all the alternatives. When we get to the final alternative
+     repeat and ONCE group with no captures. Loop for all the alternatives.
-     within the brackets, we used to return the result of a recursive call to
-     match() whatever happened so it was possible to reduce stack usage by
+     When we get to the final alternative within the brackets, we used to return
-     turning this into a tail recursion, except in the case of a possibly empty
+     the result of a recursive call to match() whatever happened so it was
-     group. However, now that there is the possiblity of (*THEN) occurring in
+     possible to reduce stack usage by turning this into a tail recursion,
-     the final alternative, this optimization is no longer possible.
+     except in the case of a possibly empty group. However, now that there is
+     the possiblity of (*THEN) occurring in the final alternative, this
+     optimization is no longer always possible.
+     We can optimize if we know there are no (*THEN)s in the pattern; at present
+     this is the best that can be done.
      MATCH_ONCE is returned when the end of an atomic group is successfully
      reached, but subsequent matching fails. It passes back up the tree (causing
-Line 892 
 for (;;)
+Line 997 
 for (;;)
      for (;;)
        {
        if (op >= OP_SBRA || op == OP_ONCE) md->match_function_type = MATCH_CBEGROUP;
+       /* If this is not a possibly empty group, and there are no (*THEN)s in
+       the pattern, and this is the final alternative, optimize as described
+       above. */
+       else if (!md->hasthen && ecode[GET(ecode, 1)] != OP_ALT)
+         {
+         ecode += _pcre_OP_lengths[*ecode];
+         goto TAIL_RECURSE;
+         }
+       /* In all other cases, we have to make another call to match(). */
        RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md, eptrb,
          RM2);
-       if (rrc != MATCH_NOMATCH &&
-           (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+       /* See comment in the code for capturing groups above about handling
+       THEN. */
+       if (rrc == MATCH_THEN)
+         {
+         next = ecode + GET(ecode,1);
+         if (md->start_match_ptr < next &&
+             (*ecode == OP_ALT || *next == OP_ALT))
+           rrc = MATCH_NOMATCH;
+         }
+       if (rrc != MATCH_NOMATCH)
          {
          if (rrc == MATCH_ONCE)
            {
-Line 912 
 for (;;)
+Line 1041 
 for (;;)
        ecode += GET(ecode, 1);
        if (*ecode != OP_ALT) break;
        }
-     if (rrc != MATCH_THEN && md->mark == NULL) md->mark = markptr;
+     if (md->mark == NULL) md->mark = markptr;
      RRETURN(MATCH_NOMATCH);
      /* Handle possessive capturing brackets with an unlimited repeat. We come
-Line 975 
 for (;;)
+Line 1105 
 for (;;)
            matched_once = TRUE;
            continue;
            }
-         if (rrc != MATCH_NOMATCH &&
-             (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+         /* See comment in the code for capturing groups above about handling
-           RRETURN(rrc);
+         THEN. */
+         if (rrc == MATCH_THEN)
+           {
+           next = ecode + GET(ecode,1);
+           if (md->start_match_ptr < next &&
+               (*ecode == OP_ALT || *next == OP_ALT))
+             rrc = MATCH_NOMATCH;
+           }
+         if (rrc != MATCH_NOMATCH) RRETURN(rrc);
          md->capture_last = save_capture_last;
          ecode += GET(ecode, 1);
          if (*ecode != OP_ALT) break;
-Line 990 
 for (;;)
+Line 1130 
 for (;;)
          md->offset_vector[md->offset_end - number] = save_offset3;
          }
-       if (rrc != MATCH_THEN && md->mark == NULL) md->mark = markptr;
+       if (md->mark == NULL) md->mark = markptr;
        if (allow_zero || matched_once)
          {
          ecode += 1 + LINK_SIZE;
-Line 1037 
 for (;;)
+Line 1177 
 for (;;)
          matched_once = TRUE;
          continue;
          }
-       if (rrc != MATCH_NOMATCH &&
-           (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+       /* See comment in the code for capturing groups above about handling
-         RRETURN(rrc);
+       THEN. */
+       if (rrc == MATCH_THEN)
+         {
+         next = ecode + GET(ecode,1);
+         if (md->start_match_ptr < next &&
+             (*ecode == OP_ALT || *next == OP_ALT))
+           rrc = MATCH_NOMATCH;
+         }
+       if (rrc != MATCH_NOMATCH) RRETURN(rrc);
        ecode += GET(ecode, 1);
        if (*ecode != OP_ALT) break;
        }
-Line 1103 
 for (;;)
+Line 1253 
 for (;;)
        else
          {
          int recno = GET2(ecode, LINK_SIZE + 2);   /* Recursion group number*/
-         condition =  (recno == RREF_ANY || recno == md->recursive->group_num);
+         condition = (recno == RREF_ANY || recno == md->recursive->group_num);
          /* If the test is for recursion into a specific subpattern, and it is
          false, but the test was set up by name, scan the table to see if the
          name refers to any other numbers, and test them. The condition is true
          if any one is set. */
-         if (!condition && condcode == OP_NRREF && recno != RREF_ANY)
+         if (!condition && condcode == OP_NRREF)
            {
            uschar *slotA = md->name_table;
            for (i = 0; i < md->name_count; i++)
-Line 1251 
 for (;;)
+Line 1401 
 for (;;)
          ecode += 1 + LINK_SIZE + GET(ecode, LINK_SIZE + 2);
          while (*ecode == OP_ALT) ecode += GET(ecode, 1);
          }
-       else if (rrc != MATCH_NOMATCH &&
-               (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+       /* PCRE doesn't allow the effect of (*THEN) to escape beyond an
+       assertion; it is therefore treated as NOMATCH. */
+       else if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN)
          {
          RRETURN(rrc);         /* Need braces because of following else */
          }
-Line 1263 
 for (;;)
+Line 1416 
 for (;;)
          }
        }
-     /* We are now at the branch that is to be obeyed. As there is only one,
+     /* We are now at the branch that is to be obeyed. As there is only one, can
-     we used to use tail recursion to avoid using another stack frame, except
+     use tail recursion to avoid using another stack frame, except when there is
-     when there was unlimited repeat of a possibly empty group. However, that
+     unlimited repeat of a possibly empty group. In the latter case, a recursive
-     strategy no longer works because of the possibilty of (*THEN) being
+     call to match() is always required, unless the second alternative doesn't
-     encountered in the branch. A recursive call to match() is always required,
+     exist, in which case we can just plough on. Note that, for compatibility
-     unless the second alternative doesn't exist, in which case we can just
+     with Perl, the | in a conditional group is NOT treated as creating two
-     plough on. */
+     alternatives. If a THEN is encountered in the branch, it propagates out to
+     the enclosing alternative (unless nested in a deeper set of alternatives,
+     of course). */
      if (condition || *ecode == OP_ALT)
        {
-       if (op == OP_SCOND) md->match_function_type = MATCH_CBEGROUP;
+       if (op != OP_SCOND)
+         {
+         ecode += 1 + LINK_SIZE;
+         goto TAIL_RECURSE;
+         }
+       md->match_function_type = MATCH_CBEGROUP;
        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, eptrb, RM49);
-       if (rrc == MATCH_THEN && md->start_match_ptr == ecode)
-         rrc = MATCH_NOMATCH;
        RRETURN(rrc);
        }
-     else                         /* Condition false & no alternative */
+      /* Condition false & no alternative; continue after the group. */
+     else
        {
        ecode += 1 + LINK_SIZE;
        }
-Line 1369 
 for (;;)
+Line 1531 
 for (;;)
          markptr = md->mark;
          break;
          }
-       if (rrc != MATCH_NOMATCH &&
-           (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+       /* PCRE does not allow THEN to escape beyond an assertion; it is treated
-         RRETURN(rrc);
+       as NOMATCH. */
+       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);
        ecode += GET(ecode, 1);
        }
      while (*ecode == OP_ALT);
-Line 1412 
 for (;;)
+Line 1576 
 for (;;)
          do ecode += GET(ecode,1); while (*ecode == OP_ALT);
          break;
          }
-       if (rrc != MATCH_NOMATCH &&
-           (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+       /* PCRE does not allow THEN to escape beyond an assertion; it is treated
-         RRETURN(rrc);
+       as NOMATCH. */
+       if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN) RRETURN(rrc);
        ecode += GET(ecode,1);
        }
      while (*ecode == OP_ALT);
-Line 1571 
 for (;;)
+Line 1737 
 for (;;)
            mstart = md->start_match_ptr;
            goto RECURSION_MATCHED;        /* Exit loop; end processing */
            }
-         else if (rrc != MATCH_NOMATCH &&
-                 (rrc != MATCH_THEN || md->start_match_ptr != ecode))
+         /* PCRE does not allow THEN to escape beyond a recursion; it is treated
+         as NOMATCH. */
+         else if (rrc != MATCH_NOMATCH && rrc != MATCH_THEN)
            {
            DPRINTF(("Recursion gave error %d\n", rrc));
            if (new_recursive.offset_save != stacksave)
-Line 1658 
 for (;;)
+Line 1827 
 for (;;)
        }
      else saved_eptr = NULL;
-     /* If we are at the end of an assertion group, stop matching and return
+     /* If we are at the end of an assertion group or a non-capturing atomic
-     MATCH_MATCH, but record the current high water mark for use by positive
+     group, stop matching and return MATCH_MATCH, but record the current high
-     assertions. We also need to record the match start in case it was changed
+     water mark for use by positive assertions. We also need to record the match
-     by \K. */
+     start in case it was changed by \K. */
-     if (*prev == OP_ASSERT || *prev == OP_ASSERT_NOT ||
+     if ((*prev >= OP_ASSERT && *prev <= OP_ASSERTBACK_NOT) ||
-         *prev == OP_ASSERTBACK || *prev == OP_ASSERTBACK_NOT)
+          *prev == OP_ONCE_NC)
        {
-       md->end_match_ptr = eptr;      /* For ONCE */
+       md->end_match_ptr = eptr;      /* For ONCE_NC */
        md->end_offset_top = offset_top;
        md->start_match_ptr = mstart;
        MRRETURN(MATCH_MATCH);         /* Sets md->mark */
-Line 1734 
 for (;;)
+Line 1903 
 for (;;)
      /* For an ordinary non-repeating ket, just continue at this level. This
      also happens for a repeating ket if no characters were matched in the
      group. This is the forcible breaking of infinite loops as implemented in
-     Perl 5.005. For a non-repeating atomic group, establish a backup point by
+     Perl 5.005. For a non-repeating atomic group that includes captures,
-     processing the rest of the pattern at a lower level. If this results in a
+     establish a backup point by processing the rest of the pattern at a lower
-     NOMATCH return, pass MATCH_ONCE back to the original OP_ONCE level, thereby
+     level. If this results in a NOMATCH return, pass MATCH_ONCE back to the
-     bypassing intermediate backup points, but resetting any captures that
+     original OP_ONCE level, thereby bypassing intermediate backup points, but
-     happened along the way. */
+     resetting any captures that happened along the way. */
      if (*ecode == OP_KET || eptr == saved_eptr)
        {
-Line 5659 
 switch (frame->Xwhere)
+Line 5828 
 switch (frame->Xwhere)
    LBL( 9) LBL(10) LBL(11) LBL(12) LBL(13) LBL(14) LBL(15) LBL(17)
    LBL(19) LBL(24) LBL(25) LBL(26) LBL(27) LBL(29) LBL(31) LBL(33)
    LBL(35) LBL(43) LBL(47) LBL(48) LBL(49) LBL(50) LBL(51) LBL(52)
-   LBL(53) LBL(54) LBL(55) LBL(56) LBL(57) LBL(58) LBL(63)
+   LBL(53) LBL(54) LBL(55) LBL(56) LBL(57) LBL(58) LBL(63) LBL(64)
+   LBL(65) LBL(66)
  #ifdef SUPPORT_UTF8
    LBL(16) LBL(18) LBL(20) LBL(21) LBL(22) LBL(23) LBL(28) LBL(30)
    LBL(32) LBL(34) LBL(42) LBL(46)
-Line 5842 
 matching. */
+Line 6012 
 matching. */
  if (extra_data != NULL
      && (extra_data->flags & PCRE_EXTRA_EXECUTABLE_JIT) != 0
      && extra_data->executable_jit != NULL
+     && (extra_data->flags & PCRE_EXTRA_TABLES) == 0
      && (options & ~(PCRE_NO_UTF8_CHECK | PCRE_NOTBOL | PCRE_NOTEOL |
                      PCRE_NOTEMPTY | PCRE_NOTEMPTY_ATSTART)) == 0)
    return _pcre_jit_exec(re, extra_data->executable_jit, subject, length,
-Line 5932 
 md->hitend = FALSE;
+Line 6103 
 md->hitend = FALSE;
  md->mark = NULL;                        /* In case never set */
  md->recursive = NULL;                   /* No recursion at top level */
+ md->hasthen = (re->flags & PCRE_HASTHEN) != 0;
  md->lcc = tables + lcc_offset;
  md->ctypes = tables + ctypes_offset;
-Line 6195 
 for(;;)
+Line 6367 
 for(;;)
    /* The following two optimizations are disabled for partial matching or if
    disabling is explicitly requested. */
-   if ((options & PCRE_NO_START_OPTIMIZE) == 0 && !md->partial)
+   if (((options | re->options) & PCRE_NO_START_OPTIMIZE) == 0 && !md->partial)
      {
      /* If the pattern was studied, a minimum subject length may be set. This is
      a lower bound; no actual string of that length may actually match the
-Line 6403 
 if (rc == MATCH_MATCH || rc == MATCH_ACC
+Line 6575 
 if (rc == MATCH_MATCH || rc == MATCH_ACC
    /* Set the return code to the number of captured strings, or 0 if there were
    too many to fit into the vector. */
    rc = (md->offset_overflow && md->end_offset_top >= arg_offset_max)?
 : md->end_offset_top/2;

 Legend:



Removed from v.681
 


changed lines


 
Added in v.835
 Legend:



Removed from v.681
 


changed lines


 
Added in v.835
-Removed from v.681
+Added in v.835

	ViewVC Help
Powered by ViewVC 1.1.5