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

Diff of /code/trunk/pcre_study.c

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

revision 603 by ph10, Fri May 27 10:14:09 2011 UTC revision 666 by ph10, Mon Aug 22 14:56:43 2011 UTC
# Line 52  supporting functions. */ Line 52  supporting functions. */
52    
53  /* Returns from set_start_bits() */  /* Returns from set_start_bits() */
54    
55  enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };  enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE, SSB_UNKNOWN };
56    
57    
58    
# Line 66  string of that length that matches. In U Line 66  string of that length that matches. In U
66  rather than bytes.  rather than bytes.
67    
68  Arguments:  Arguments:
69    code       pointer to start of group (the bracket)    code        pointer to start of group (the bracket)
70    startcode  pointer to start of the whole pattern    startcode   pointer to start of the whole pattern
71    options    the compiling options    options     the compiling options
72      had_accept  pointer to flag for (*ACCEPT) encountered
73      int         RECURSE depth
74    
75  Returns:   the minimum length  Returns:   the minimum length
76             -1 if \C was encountered             -1 if \C was encountered
77             -2 internal error (missing capturing bracket)             -2 internal error (missing capturing bracket)
78             -3 internal error (opcode not listed)             -3 internal error (opcode not listed)
79  */  */
80    
81  static int  static int
82  find_minlength(const uschar *code, const uschar *startcode, int options)  find_minlength(const uschar *code, const uschar *startcode, int options,
83      BOOL *had_accept_ptr, int recurse_depth)
84  {  {
85  int length = -1;  int length = -1;
86  BOOL utf8 = (options & PCRE_UTF8) != 0;  BOOL utf8 = (options & PCRE_UTF8) != 0;
# Line 85  BOOL had_recurse = FALSE; Line 88  BOOL had_recurse = FALSE;
88  register int branchlength = 0;  register int branchlength = 0;
89  register uschar *cc = (uschar *)code + 1 + LINK_SIZE;  register uschar *cc = (uschar *)code + 1 + LINK_SIZE;
90    
91  if (*code == OP_CBRA || *code == OP_SCBRA) cc += 2;  if (*code == OP_CBRA || *code == OP_SCBRA ||
92        *code == OP_CBRAPOS || *code == OP_SCBRAPOS) cc += 2;
93    
94  /* Scan along the opcodes for this branch. If we get to the end of the  /* Scan along the opcodes for this branch. If we get to the end of the
95  branch, check the length against that of the other branches. */  branch, check the length against that of the other branches. */
# Line 119  for (;;) Line 123  for (;;)
123      case OP_SCBRA:      case OP_SCBRA:
124      case OP_BRA:      case OP_BRA:
125      case OP_SBRA:      case OP_SBRA:
126        case OP_CBRAPOS:
127        case OP_SCBRAPOS:
128        case OP_BRAPOS:
129        case OP_SBRAPOS:
130      case OP_ONCE:      case OP_ONCE:
131      d = find_minlength(cc, startcode, options);      d = find_minlength(cc, startcode, options, had_accept_ptr, recurse_depth);
132      if (d < 0) return d;      if (d < 0) return d;
133      branchlength += d;      branchlength += d;
134        if (*had_accept_ptr) return branchlength;
135      do cc += GET(cc, 1); while (*cc == OP_ALT);      do cc += GET(cc, 1); while (*cc == OP_ALT);
136      cc += 1 + LINK_SIZE;      cc += 1 + LINK_SIZE;
137      break;      break;
138    
139      /* Reached end of a branch; if it's a ket it is the end of a nested      /* Reached end of a branch; if it's a ket it is the end of a nested
140      call. If it's ALT it is an alternation in a nested call. If it is      call. If it's ALT it is an alternation in a nested call. If it is END it's
141      END it's the end of the outer call. All can be handled by the same code. */      the end of the outer call. All can be handled by the same code. If it is
142        ACCEPT, it is essentially the same as END, but we set a flag so that
143        counting stops. */
144    
145        case OP_ACCEPT:
146        case OP_ASSERT_ACCEPT:
147        *had_accept_ptr = TRUE;
148        /* Fall through */
149      case OP_ALT:      case OP_ALT:
150      case OP_KET:      case OP_KET:
151      case OP_KETRMAX:      case OP_KETRMAX:
152      case OP_KETRMIN:      case OP_KETRMIN:
153        case OP_KETRPOS:
154      case OP_END:      case OP_END:
155      if (length < 0 || (!had_recurse && branchlength < length))      if (length < 0 || (!had_recurse && branchlength < length))
156        length = branchlength;        length = branchlength;
157      if (*cc != OP_ALT) return length;      if (op != OP_ALT) return length;
158      cc += 1 + LINK_SIZE;      cc += 1 + LINK_SIZE;
159      branchlength = 0;      branchlength = 0;
160      had_recurse = FALSE;      had_recurse = FALSE;
# Line 179  for (;;) Line 195  for (;;)
195    
196      case OP_BRAZERO:      case OP_BRAZERO:
197      case OP_BRAMINZERO:      case OP_BRAMINZERO:
198        case OP_BRAPOSZERO:
199      case OP_SKIPZERO:      case OP_SKIPZERO:
200      cc += _pcre_OP_lengths[*cc];      cc += _pcre_OP_lengths[*cc];
201      do cc += GET(cc, 1); while (*cc == OP_ALT);      do cc += GET(cc, 1); while (*cc == OP_ALT);
# Line 260  for (;;) Line 277  for (;;)
277      cc++;      cc++;
278      break;      break;
279    
280      /* "Any newline" might match two characters */      /* "Any newline" might match two characters, but it also might match just
281        one. */
282    
283      case OP_ANYNL:      case OP_ANYNL:
284      branchlength += 2;      branchlength += 1;
285      cc++;      cc++;
286      break;      break;
287    
# Line 359  for (;;) Line 377  for (;;)
377          d = 0;          d = 0;
378          had_recurse = TRUE;          had_recurse = TRUE;
379          }          }
380        else d = find_minlength(cs, startcode, options);        else
381            {
382            d = find_minlength(cs, startcode, options, had_accept_ptr,
383              recurse_depth);
384            *had_accept_ptr = FALSE;
385            }
386        }        }
387      else d = 0;      else d = 0;
388      cc += 3;      cc += 3;
# Line 376  for (;;) Line 399  for (;;)
399        cc++;        cc++;
400        break;        break;
401    
402          case OP_CRPLUS:
403          case OP_CRMINPLUS:
404          min = 1;
405          cc++;
406          break;
407    
408        case OP_CRRANGE:        case OP_CRRANGE:
409        case OP_CRMINRANGE:        case OP_CRMINRANGE:
410        min = GET2(cc, 1);        min = GET2(cc, 1);
# Line 390  for (;;) Line 419  for (;;)
419      branchlength += min * d;      branchlength += min * d;
420      break;      break;
421    
422        /* We can easily detect direct recursion, but not mutual recursion. This is
423        caught by a recursion depth count. */
424    
425      case OP_RECURSE:      case OP_RECURSE:
426      cs = ce = (uschar *)startcode + GET(cc, 1);      cs = ce = (uschar *)startcode + GET(cc, 1);
427      if (cs == NULL) return -2;      if (cs == NULL) return -2;
428      do ce += GET(ce, 1); while (*ce == OP_ALT);      do ce += GET(ce, 1); while (*ce == OP_ALT);
429      if (cc > cs && cc < ce)      if ((cc > cs && cc < ce) || recurse_depth > 10)
430        had_recurse = TRUE;        had_recurse = TRUE;
431      else      else
432        branchlength += find_minlength(cs, startcode, options);        {
433          branchlength += find_minlength(cs, startcode, options, had_accept_ptr,
434            recurse_depth + 1);
435          *had_accept_ptr = FALSE;
436          }
437      cc += 1 + LINK_SIZE;      cc += 1 + LINK_SIZE;
438      break;      break;
439    
# Line 406  for (;;) Line 442  for (;;)
442      of a character, we must take special action for UTF-8 characters. As it      of a character, we must take special action for UTF-8 characters. As it
443      happens, the "NOT" versions of these opcodes are used at present only for      happens, the "NOT" versions of these opcodes are used at present only for
444      ASCII characters, so they could be omitted from this list. However, in      ASCII characters, so they could be omitted from this list. However, in
445      future that may change, so we include them here so as not to leave a      future that may change, so we include them here so as not to leave a
446      gotcha for a future maintainer. */      gotcha for a future maintainer. */
447    
448      case OP_UPTO:      case OP_UPTO:
# Line 468  for (;;) Line 504  for (;;)
504    
505      /* The remaining opcodes are just skipped over. */      /* The remaining opcodes are just skipped over. */
506    
     case OP_ACCEPT:  
507      case OP_CLOSE:      case OP_CLOSE:
508      case OP_COMMIT:      case OP_COMMIT:
509      case OP_FAIL:      case OP_FAIL:
510      case OP_PRUNE:      case OP_PRUNE:
511      case OP_SET_SOM:      case OP_SET_SOM:
512      case OP_SKIP:      case OP_SKIP:
513      case OP_THEN:      case OP_THEN:
514      cc += _pcre_OP_lengths[op];      cc += _pcre_OP_lengths[op];
515      break;      break;
516    
517      /* This should not occur: we list all opcodes explicitly so that when      /* This should not occur: we list all opcodes explicitly so that when
518      new ones get added they are properly considered. */      new ones get added they are properly considered. */
519    
# Line 635  Arguments: Line 670  Arguments:
670  Returns:       SSB_FAIL     => Failed to find any starting bytes  Returns:       SSB_FAIL     => Failed to find any starting bytes
671                 SSB_DONE     => Found mandatory starting bytes                 SSB_DONE     => Found mandatory starting bytes
672                 SSB_CONTINUE => Found optional starting bytes                 SSB_CONTINUE => Found optional starting bytes
673                   SSB_UNKNOWN  => Hit an unrecognized opcode
674  */  */
675    
676  static int  static int
677  set_start_bits(const uschar *code, uschar *start_bits, BOOL utf8,  set_start_bits(const uschar *code, uschar *start_bits, BOOL utf8,
678    compile_data *cd)    compile_data *cd)
679  {  {
680  register int c;  register int c;
# Line 664  volatile int dummy; Line 700  volatile int dummy;
700    
701  do  do
702    {    {
   const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;  
703    BOOL try_next = TRUE;    BOOL try_next = TRUE;
704      const uschar *tcode = code + 1 + LINK_SIZE;
705    
706      if (*code == OP_CBRA || *code == OP_SCBRA ||
707          *code == OP_CBRAPOS || *code == OP_SCBRAPOS) tcode += 2;
708    
709    while (try_next)    /* Loop for items in this branch */    while (try_next)    /* Loop for items in this branch */
710      {      {
711      int rc;      int rc;
712    
713      switch(*tcode)      switch(*tcode)
714        {        {
715        /* Fail if we reach something we don't understand */        /* If we reach something we don't understand, it means a new opcode has
716          been created that hasn't been added to this code. Hopefully this problem
717          will be discovered during testing. */
718    
719        default:        default:
720          return SSB_UNKNOWN;
721    
722          /* Fail for a valid opcode that implies no starting bits. */
723    
724          case OP_ACCEPT:
725          case OP_ASSERT_ACCEPT:
726          case OP_ALLANY:
727          case OP_ANY:
728          case OP_ANYBYTE:
729          case OP_CIRC:
730          case OP_CIRCM:
731          case OP_CLOSE:
732          case OP_COMMIT:
733          case OP_COND:
734          case OP_CREF:
735          case OP_DEF:
736          case OP_DOLL:
737          case OP_DOLLM:
738          case OP_END:
739          case OP_EOD:
740          case OP_EODN:
741          case OP_EXTUNI:
742          case OP_FAIL:
743          case OP_MARK:
744          case OP_NCREF:
745          case OP_NOT:
746          case OP_NOTEXACT:
747          case OP_NOTEXACTI:
748          case OP_NOTI:
749          case OP_NOTMINPLUS:
750          case OP_NOTMINPLUSI:
751          case OP_NOTMINQUERY:
752          case OP_NOTMINQUERYI:
753          case OP_NOTMINSTAR:
754          case OP_NOTMINSTARI:
755          case OP_NOTMINUPTO:
756          case OP_NOTMINUPTOI:
757          case OP_NOTPLUS:
758          case OP_NOTPLUSI:
759          case OP_NOTPOSPLUS:
760          case OP_NOTPOSPLUSI:
761          case OP_NOTPOSQUERY:
762          case OP_NOTPOSQUERYI:
763          case OP_NOTPOSSTAR:
764          case OP_NOTPOSSTARI:
765          case OP_NOTPOSUPTO:
766          case OP_NOTPOSUPTOI:
767          case OP_NOTPROP:
768          case OP_NOTQUERY:
769          case OP_NOTQUERYI:
770          case OP_NOTSTAR:
771          case OP_NOTSTARI:
772          case OP_NOTUPTO:
773          case OP_NOTUPTOI:
774          case OP_NOT_HSPACE:
775          case OP_NOT_VSPACE:
776          case OP_NRREF:
777          case OP_PROP:
778          case OP_PRUNE:
779          case OP_PRUNE_ARG:
780          case OP_RECURSE:
781          case OP_REF:
782          case OP_REFI:
783          case OP_REVERSE:
784          case OP_RREF:
785          case OP_SCOND:
786          case OP_SET_SOM:
787          case OP_SKIP:
788          case OP_SKIP_ARG:
789          case OP_SOD:
790          case OP_SOM:
791          case OP_THEN:
792          case OP_THEN_ARG:
793          case OP_XCLASS:
794        return SSB_FAIL;        return SSB_FAIL;
795    
796          /* We can ignore word boundary tests. */
797    
798          case OP_WORD_BOUNDARY:
799          case OP_NOT_WORD_BOUNDARY:
800          tcode++;
801          break;
802    
803        /* If we hit a bracket or a positive lookahead assertion, recurse to set        /* If we hit a bracket or a positive lookahead assertion, recurse to set
804        bits from within the subpattern. If it can't find anything, we have to        bits from within the subpattern. If it can't find anything, we have to
805        give up. If it finds some mandatory character(s), we are done for this        give up. If it finds some mandatory character(s), we are done for this
# Line 686  do Line 809  do
809        case OP_SBRA:        case OP_SBRA:
810        case OP_CBRA:        case OP_CBRA:
811        case OP_SCBRA:        case OP_SCBRA:
812          case OP_BRAPOS:
813          case OP_SBRAPOS:
814          case OP_CBRAPOS:
815          case OP_SCBRAPOS:
816        case OP_ONCE:        case OP_ONCE:
817        case OP_ASSERT:        case OP_ASSERT:
818        rc = set_start_bits(tcode, start_bits, utf8, cd);        rc = set_start_bits(tcode, start_bits, utf8, cd);
819        if (rc == SSB_FAIL) return SSB_FAIL;        if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
820        if (rc == SSB_DONE) try_next = FALSE; else        if (rc == SSB_DONE) try_next = FALSE; else
821          {          {
822          do tcode += GET(tcode, 1); while (*tcode == OP_ALT);          do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
# Line 712  do Line 839  do
839        case OP_KET:        case OP_KET:
840        case OP_KETRMAX:        case OP_KETRMAX:
841        case OP_KETRMIN:        case OP_KETRMIN:
842          case OP_KETRPOS:
843        return SSB_CONTINUE;        return SSB_CONTINUE;
844    
845        /* Skip over callout */        /* Skip over callout */
# Line 733  do Line 861  do
861    
862        case OP_BRAZERO:        case OP_BRAZERO:
863        case OP_BRAMINZERO:        case OP_BRAMINZERO:
864        if (set_start_bits(++tcode, start_bits, utf8, cd) == SSB_FAIL)        case OP_BRAPOSZERO:
865          return SSB_FAIL;        rc = set_start_bits(++tcode, start_bits, utf8, cd);
866          if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
867  /* =========================================================================  /* =========================================================================
868        See the comment at the head of this function concerning the next line,        See the comment at the head of this function concerning the next line,
869        which was an old fudge for the benefit of OS/2.        which was an old fudge for the benefit of OS/2.
# Line 1036  do Line 1165  do
1165            for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];            for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
1166            }            }
1167    
1168          /* Advance past the bit map, and act on what follows */          /* Advance past the bit map, and act on what follows. For a zero
1169            minimum repeat, continue; otherwise stop processing. */
1170    
1171          tcode += 32;          tcode += 32;
1172          switch (*tcode)          switch (*tcode)
# Line 1072  return yield; Line 1202  return yield;
1202    
1203    
1204    
1205    
1206    
1207  /*************************************************  /*************************************************
1208  *          Study a compiled expression           *  *          Study a compiled expression           *
1209  *************************************************/  *************************************************/
# Line 1096  pcre_study(const pcre *external_re, int Line 1228  pcre_study(const pcre *external_re, int
1228  {  {
1229  int min;  int min;
1230  BOOL bits_set = FALSE;  BOOL bits_set = FALSE;
1231    BOOL had_accept = FALSE;
1232  uschar start_bits[32];  uschar start_bits[32];
1233  pcre_extra *extra;  pcre_extra *extra;
1234  pcre_study_data *study;  pcre_study_data *study;
# Line 1128  seeking a list of starting bytes. */ Line 1261  seeking a list of starting bytes. */
1261  if ((re->options & PCRE_ANCHORED) == 0 &&  if ((re->options & PCRE_ANCHORED) == 0 &&
1262      (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)      (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)
1263    {    {
1264      int rc;
1265    
1266    /* Set the character tables in the block that is passed around */    /* Set the character tables in the block that is passed around */
1267    
1268    tables = re->tables;    tables = re->tables;
# Line 1143  if ((re->options & PCRE_ANCHORED) == 0 & Line 1278  if ((re->options & PCRE_ANCHORED) == 0 &
1278    /* See if we can find a fixed set of initial characters for the pattern. */    /* See if we can find a fixed set of initial characters for the pattern. */
1279    
1280    memset(start_bits, 0, 32 * sizeof(uschar));    memset(start_bits, 0, 32 * sizeof(uschar));
1281    bits_set = set_start_bits(code, start_bits, (re->options & PCRE_UTF8) != 0,    rc = set_start_bits(code, start_bits, (re->options & PCRE_UTF8) != 0,
1282      &compile_block) == SSB_DONE;      &compile_block);
1283      bits_set = rc == SSB_DONE;
1284      if (rc == SSB_UNKNOWN) *errorptr = "internal error: opcode not recognized";
1285    }    }
1286    
1287  /* Find the minimum length of subject string. */  /* Find the minimum length of subject string. */
1288    
1289  switch(min = find_minlength(code, code, re->options))  switch(min = find_minlength(code, code, re->options, &had_accept, 0))
1290    {    {
1291    case -2: *errorptr = "internal error: missing capturing bracket"; break;    case -2: *errorptr = "internal error: missing capturing bracket"; break;
1292    case -3: *errorptr = "internal error: opcode not recognized"; break;    case -3: *errorptr = "internal error: opcode not recognized"; break;
1293    default: break;    default: break;
1294    }    }
1295    
1296  /* Return NULL if no optimization is possible. */  /* Return NULL if there's been an error or if no optimization is possible. */
1297    
1298  if (!bits_set && min < 0) return NULL;  if (*errorptr != NULL || (!bits_set && min < 0)) return NULL;
1299    
1300  /* Get a pcre_extra block and a pcre_study_data block. The study data is put in  /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
1301  the latter, which is pointed to by the former, which may also get additional  the latter, which is pointed to by the former, which may also get additional
# Line 1195  if (min >= 0) Line 1332  if (min >= 0)
1332    study->minlength = min;    study->minlength = min;
1333    }    }
1334    
1335    extra->executable_jit = NULL;
1336    #ifdef SUPPORT_JIT
1337    if ((options & PCRE_STUDY_JIT_COMPILE) != 0) _pcre_jit_compile(re, extra);
1338    #endif
1339    
1340  return extra;  return extra;
1341  }  }
1342    
1343    
1344    /*************************************************
1345    *          Free the study data                   *
1346    *************************************************/
1347    
1348    /* This function frees the memory that was obtained by pcre_study().
1349    
1350    Argument:   a pointer to the pcre_extra block
1351    Returns:    nothing
1352    */
1353    
1354    PCRE_EXP_DEFN void
1355    pcre_free_study(pcre_extra *extra)
1356    {
1357    #ifdef SUPPORT_JIT
1358    if ((extra->flags & PCRE_EXTRA_EXECUTABLE_JIT) != 0 &&
1359         extra->executable_jit != NULL)
1360      _pcre_jit_free(extra->executable_jit);
1361    #endif
1362    pcre_free(extra);
1363    }
1364    
1365  /* End of pcre_study.c */  /* End of pcre_study.c */
Legend:
Removed from v.603  
changed lines
  Added in v.666
webmaster@exim.org
 ViewVC Help
Powered by ViewVC 1.1.12