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

Diff of /code/trunk/pcre_exec.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 196 by ph10, Thu Jul 19 10:38:20 2007 UTC revision 197 by ph10, Tue Jul 31 10:50:18 2007 UTC
# Line 53  possible. There are also some static sup Line 53  possible. There are also some static sup
53  #undef min  #undef min
54  #undef max  #undef max
55    
 /* The chain of eptrblocks for tail recursions uses memory in stack workspace,  
 obtained at top level, the size of which is defined by EPTR_WORK_SIZE. */  
   
 #define EPTR_WORK_SIZE (1000)  
   
56  /* Flag bits for the match() function */  /* Flag bits for the match() function */
57    
58  #define match_condassert     0x01  /* Called to check a condition assertion */  #define match_condassert     0x01  /* Called to check a condition assertion */
59  #define match_cbegroup       0x02  /* Could-be-empty unlimited repeat group */  #define match_cbegroup       0x02  /* Could-be-empty unlimited repeat group */
 #define match_tail_recursed  0x04  /* Tail recursive call */  
60    
61  /* Non-error returns from the match() function. Error returns are externally  /* Non-error returns from the match() function. Error returns are externally
62  defined PCRE_ERROR_xxx codes, which are all negative. */  defined PCRE_ERROR_xxx codes, which are all negative. */
# Line 212  enum { RM1=1, RM2,  RM3,  RM4,  RM5,  RM Line 206  enum { RM1=1, RM2,  RM3,  RM4,  RM5,  RM
206         RM11,  RM12, RM13, RM14, RM15, RM16, RM17, RM18, RM19, RM20,         RM11,  RM12, RM13, RM14, RM15, RM16, RM17, RM18, RM19, RM20,
207         RM21,  RM22, RM23, RM24, RM25, RM26, RM27, RM28, RM29, RM30,         RM21,  RM22, RM23, RM24, RM25, RM26, RM27, RM28, RM29, RM30,
208         RM31,  RM32, RM33, RM34, RM35, RM36, RM37, RM38, RM39, RM40,         RM31,  RM32, RM33, RM34, RM35, RM36, RM37, RM38, RM39, RM40,
209         RM41,  RM42, RM43, RM44, RM45, RM46, RM47 };         RM41,  RM42, RM43, RM44, RM45, RM46, RM47, RM48, RM49, RM50 };
210    
211    
212  /* These versions of the macros use the stack, as normal. There are debugging  /* These versions of the macros use the stack, as normal. There are debugging
# Line 384  Arguments: Line 378  Arguments:
378                   match_condassert - this is an assertion condition                   match_condassert - this is an assertion condition
379                   match_cbegroup - this is the start of an unlimited repeat                   match_cbegroup - this is the start of an unlimited repeat
380                     group that can match an empty string                     group that can match an empty string
                  match_tail_recursed - this is a tail_recursed group  
381     rdepth      the recursion depth     rdepth      the recursion depth
382    
383  Returns:       MATCH_MATCH if matched            )  these values are >= 0  Returns:       MATCH_MATCH if matched            )  these values are >= 0
# Line 586  original_ims = ims;    /* Save for reset Line 579  original_ims = ims;    /* Save for reset
579  string, the match_cbegroup flag is set. When this is the case, add the current  string, the match_cbegroup flag is set. When this is the case, add the current
580  subject pointer to the chain of such remembered pointers, to be checked when we  subject pointer to the chain of such remembered pointers, to be checked when we
581  hit the closing ket, in order to break infinite loops that match no characters.  hit the closing ket, in order to break infinite loops that match no characters.
582  When match() is called in other circumstances, don't add to the chain. If this  When match() is called in other circumstances, don't add to the chain. The
583  is a tail recursion, use a block from the workspace, as the one on the stack is  match_cbegroup flag must NOT be used with tail recursion, because the memory
584  already used. */  block that is used is on the stack, so a new one may be required for each
585    match(). */
586    
587  if ((flags & match_cbegroup) != 0)  if ((flags & match_cbegroup) != 0)
588    {    {
589    eptrblock *p;    newptrb.epb_saved_eptr = eptr;
590    if ((flags & match_tail_recursed) != 0)    newptrb.epb_prev = eptrb;
591      {    eptrb = &newptrb;
     if (md->eptrn >= EPTR_WORK_SIZE) RRETURN(PCRE_ERROR_NULLWSLIMIT);  
     p = md->eptrchain + md->eptrn++;  
     }  
   else p = &newptrb;  
   p->epb_saved_eptr = eptr;  
   p->epb_prev = eptrb;  
   eptrb = p;  
592    }    }
593    
594  /* Now start processing the opcodes. */  /* Now start processing the opcodes. */
# Line 677  for (;;) Line 664  for (;;)
664        RRETURN(MATCH_NOMATCH);        RRETURN(MATCH_NOMATCH);
665        }        }
666    
667      /* Insufficient room for saving captured contents. Treat as a non-capturing      /* FALL THROUGH ... Insufficient room for saving captured contents. Treat
668      bracket. */      as a non-capturing bracket. */
669    
670        /* VVVVVVVVVVVVVVVVVVVVVVVVV */
671        /* VVVVVVVVVVVVVVVVVVVVVVVVV */
672    
673      DPRINTF(("insufficient capture room: treat as non-capturing\n"));      DPRINTF(("insufficient capture room: treat as non-capturing\n"));
674    
675        /* VVVVVVVVVVVVVVVVVVVVVVVVV */
676        /* VVVVVVVVVVVVVVVVVVVVVVVVV */
677    
678      /* Non-capturing bracket. Loop for all the alternatives. When we get to the      /* Non-capturing bracket. Loop for all the alternatives. When we get to the
679      final alternative within the brackets, we would return the result of a      final alternative within the brackets, we would return the result of a
680      recursive call to match() whatever happened. We can reduce stack usage by      recursive call to match() whatever happened. We can reduce stack usage by
681      turning this into a tail recursion. */      turning this into a tail recursion, except in the case when match_cbegroup
682        is set.*/
683    
684      case OP_BRA:      case OP_BRA:
685      case OP_SBRA:      case OP_SBRA:
# Line 693  for (;;) Line 687  for (;;)
687      flags = (op >= OP_SBRA)? match_cbegroup : 0;      flags = (op >= OP_SBRA)? match_cbegroup : 0;
688      for (;;)      for (;;)
689        {        {
690        if (ecode[GET(ecode, 1)] != OP_ALT)        if (ecode[GET(ecode, 1)] != OP_ALT)   /* Final alternative */
691          {          {
692          ecode += _pcre_OP_lengths[*ecode];          if (flags == 0)    /* Not a possibly empty group */
693          flags |= match_tail_recursed;            {
694          DPRINTF(("bracket 0 tail recursion\n"));            ecode += _pcre_OP_lengths[*ecode];
695          goto TAIL_RECURSE;            DPRINTF(("bracket 0 tail recursion\n"));
696              goto TAIL_RECURSE;
697              }
698    
699            /* Possibly empty group; can't use tail recursion. */
700    
701            RMATCH(eptr, ecode + _pcre_OP_lengths[*ecode], offset_top, md, ims,
702              eptrb, flags, RM48);
703            RRETURN(rrc);
704          }          }
705    
706        /* For non-final alternatives, continue the loop for a NOMATCH result;        /* For non-final alternatives, continue the loop for a NOMATCH result;
# Line 766  for (;;) Line 768  for (;;)
768        }        }
769    
770      /* 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,
771      we can use tail recursion to avoid using another stack frame. If the second      we can use tail recursion to avoid using another stack frame, except when
772      alternative doesn't exist, we can just plough on. */      match_cbegroup is required for an unlimited repeat of a possibly empty
773        group. If the second alternative doesn't exist, we can just plough on. */
774    
775      if (condition || *ecode == OP_ALT)      if (condition || *ecode == OP_ALT)
776        {        {
777        ecode += 1 + LINK_SIZE;        ecode += 1 + LINK_SIZE;
778        flags = match_tail_recursed | ((op == OP_SCOND)? match_cbegroup : 0);        if (op == OP_SCOND)        /* Possibly empty group */
779        goto TAIL_RECURSE;          {
780            RMATCH(eptr, ecode, offset_top, md, ims, eptrb, match_cbegroup, RM49);
781            RRETURN(rrc);
782            }
783          else                       /* Group must match something */
784            {
785            flags = 0;
786            goto TAIL_RECURSE;
787            }
788        }        }
789      else      else                         /* Condition false & no 2nd alternative */
790        {        {
791        ecode += 1 + LINK_SIZE;        ecode += 1 + LINK_SIZE;
792        }        }
# Line 1027  for (;;) Line 1038  for (;;)
1038    
1039      do      do
1040        {        {
1041        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims,        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0, RM7);
         eptrb, 0, RM7);  
1042        if (rrc == MATCH_MATCH) break;        if (rrc == MATCH_MATCH) break;
1043        if (rrc != MATCH_NOMATCH) RRETURN(rrc);        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1044        ecode += GET(ecode,1);        ecode += GET(ecode,1);
# Line 1073  for (;;) Line 1083  for (;;)
1083    
1084      if (*ecode == OP_KETRMIN)      if (*ecode == OP_KETRMIN)
1085        {        {
1086        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0,        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0, RM8);
         RM8);  
1087        if (rrc != MATCH_NOMATCH) RRETURN(rrc);        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1088        ecode = prev;        ecode = prev;
1089        flags = match_tail_recursed;        flags = 0;
1090        goto TAIL_RECURSE;        goto TAIL_RECURSE;
1091        }        }
1092      else  /* OP_KETRMAX */      else  /* OP_KETRMAX */
# Line 1085  for (;;) Line 1094  for (;;)
1094        RMATCH(eptr, prev, offset_top, md, ims, eptrb, match_cbegroup, RM9);        RMATCH(eptr, prev, offset_top, md, ims, eptrb, match_cbegroup, RM9);
1095        if (rrc != MATCH_NOMATCH) RRETURN(rrc);        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1096        ecode += 1 + LINK_SIZE;        ecode += 1 + LINK_SIZE;
1097        flags = match_tail_recursed;        flags = 0;
1098        goto TAIL_RECURSE;        goto TAIL_RECURSE;
1099        }        }
1100      /* Control never gets here */      /* Control never gets here */
# Line 1216  for (;;) Line 1225  for (;;)
1225    
1226      /* The repeating kets try the rest of the pattern or restart from the      /* The repeating kets try the rest of the pattern or restart from the
1227      preceding bracket, in the appropriate order. In the second case, we can use      preceding bracket, in the appropriate order. In the second case, we can use
1228      tail recursion to avoid using another stack frame. */      tail recursion to avoid using another stack frame, unless we have an
1229        unlimited repeat of a group that can match an empty string. */
1230    
1231      flags = (*prev >= OP_SBRA)? match_cbegroup : 0;      flags = (*prev >= OP_SBRA)? match_cbegroup : 0;
1232    
1233      if (*ecode == OP_KETRMIN)      if (*ecode == OP_KETRMIN)
1234        {        {
1235        RMATCH(eptr, ecode + 1+LINK_SIZE, offset_top, md, ims, eptrb, 0,        RMATCH(eptr, ecode + 1 + LINK_SIZE, offset_top, md, ims, eptrb, 0, RM12);
         RM12);  
1236        if (rrc != MATCH_NOMATCH) RRETURN(rrc);        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1237          if (flags != 0)    /* Could match an empty string */
1238            {
1239            RMATCH(eptr, prev, offset_top, md, ims, eptrb, flags, RM50);
1240            RRETURN(rrc);
1241            }
1242        ecode = prev;        ecode = prev;
       flags |= match_tail_recursed;  
1243        goto TAIL_RECURSE;        goto TAIL_RECURSE;
1244        }        }
1245      else  /* OP_KETRMAX */      else  /* OP_KETRMAX */
# Line 1234  for (;;) Line 1247  for (;;)
1247        RMATCH(eptr, prev, offset_top, md, ims, eptrb, flags, RM13);        RMATCH(eptr, prev, offset_top, md, ims, eptrb, flags, RM13);
1248        if (rrc != MATCH_NOMATCH) RRETURN(rrc);        if (rrc != MATCH_NOMATCH) RRETURN(rrc);
1249        ecode += 1 + LINK_SIZE;        ecode += 1 + LINK_SIZE;
1250        flags = match_tail_recursed;        flags = 0;
1251        goto TAIL_RECURSE;        goto TAIL_RECURSE;
1252        }        }
1253      /* Control never gets here */      /* Control never gets here */
# Line 4290  const uschar *start_bits = NULL; Line 4303  const uschar *start_bits = NULL;
4303  USPTR start_match = (USPTR)subject + start_offset;  USPTR start_match = (USPTR)subject + start_offset;
4304  USPTR end_subject;  USPTR end_subject;
4305  USPTR req_byte_ptr = start_match - 1;  USPTR req_byte_ptr = start_match - 1;
 eptrblock eptrchain[EPTR_WORK_SIZE];  
4306    
4307  pcre_study_data internal_study;  pcre_study_data internal_study;
4308  const pcre_study_data *study;  const pcre_study_data *study;
# Line 4376  md->partial = (options & PCRE_PARTIAL) ! Line 4388  md->partial = (options & PCRE_PARTIAL) !
4388  md->hitend = FALSE;  md->hitend = FALSE;
4389    
4390  md->recursive = NULL;                   /* No recursion at top level */  md->recursive = NULL;                   /* No recursion at top level */
 md->eptrchain = eptrchain;              /* Make workspace generally available */  
4391    
4392  md->lcc = tables + lcc_offset;  md->lcc = tables + lcc_offset;
4393  md->ctypes = tables + ctypes_offset;  md->ctypes = tables + ctypes_offset;
# Line 4674  for(;;) Line 4685  for(;;)
4685    
4686    md->start_match_ptr = start_match;      /* Insurance */    md->start_match_ptr = start_match;      /* Insurance */
4687    md->match_call_count = 0;    md->match_call_count = 0;
4688    md->eptrn = 0;                          /* Next free eptrchain slot */    rc = match(start_match, md->start_code, start_match, 2, md, ims, NULL, 0, 0);
   rc = match(start_match, md->start_code, start_match, 2, md,  
     ims, NULL, 0, 0);  
4689    
4690    /* Any return other than MATCH_NOMATCH breaks the loop. */    /* Any return other than MATCH_NOMATCH breaks the loop. */
4691    
Legend:
Removed from v.196  
changed lines
  Added in v.197
  ViewVC Help
Powered by ViewVC 1.1.5