/[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 77 by nigel, Sat Feb 24 21:40:45 2007 UTC revision 145 by ph10, Wed Apr 4 14:06:52 2007 UTC
# Line 6  Line 6 
6  and semantics are as close as possible to those of the Perl 5 language.  and semantics are as close as possible to those of the Perl 5 language.
7    
8                         Written by Philip Hazel                         Written by Philip Hazel
9             Copyright (c) 1997-2005 University of Cambridge             Copyright (c) 1997-2007 University of Cambridge
10    
11  -----------------------------------------------------------------------------  -----------------------------------------------------------------------------
12  Redistribution and use in source and binary forms, with or without  Redistribution and use in source and binary forms, with or without
# Line 45  supporting functions. */ Line 45  supporting functions. */
45  #include "pcre_internal.h"  #include "pcre_internal.h"
46    
47    
48    /* Returns from set_start_bits() */
49    
50    enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
51    
52    
53  /*************************************************  /*************************************************
54  *      Set a bit and maybe its alternate case    *  *      Set a bit and maybe its alternate case    *
55  *************************************************/  *************************************************/
# Line 72  if (caseless && (cd->ctypes[c] & ctype_l Line 77  if (caseless && (cd->ctypes[c] & ctype_l
77    
78    
79  /*************************************************  /*************************************************
80  *          Create bitmap of starting chars       *  *          Create bitmap of starting bytes       *
81  *************************************************/  *************************************************/
82    
83  /* This function scans a compiled unanchored expression and attempts to build a  /* This function scans a compiled unanchored expression recursively and
84  bitmap of the set of initial characters. If it can't, it returns FALSE. As time  attempts to build a bitmap of the set of possible starting bytes. As time goes
85  goes by, we may be able to get more clever at doing this.  by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
86    useful for parenthesized groups in patterns such as (a*)b where the group
87    provides some optional starting bytes but scanning must continue at the outer
88    level to find at least one mandatory byte. At the outermost level, this
89    function fails unless the result is SSB_DONE.
90    
91  Arguments:  Arguments:
92    code         points to an expression    code         points to an expression
# Line 86  Arguments: Line 95  Arguments:
95    utf8         TRUE if in UTF-8 mode    utf8         TRUE if in UTF-8 mode
96    cd           the block with char table pointers    cd           the block with char table pointers
97    
98  Returns:       TRUE if table built, FALSE otherwise  Returns:       SSB_FAIL     => Failed to find any starting bytes
99                   SSB_DONE     => Found mandatory starting bytes
100                   SSB_CONTINUE => Found optional starting bytes
101  */  */
102    
103  static BOOL  static int
104  set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,  set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
105    BOOL utf8, compile_data *cd)    BOOL utf8, compile_data *cd)
106  {  {
107  register int c;  register int c;
108    int yield = SSB_DONE;
109    
110    #if 0
111    /* ========================================================================= */
112    /* The following comment and code was inserted in January 1999. In May 2006,
113    when it was observed to cause compiler warnings about unused values, I took it
114    out again. If anybody is still using OS/2, they will have to put it back
115    manually. */
116    
117  /* This next statement and the later reference to dummy are here in order to  /* This next statement and the later reference to dummy are here in order to
118  trick the optimizer of the IBM C compiler for OS/2 into generating correct  trick the optimizer of the IBM C compiler for OS/2 into generating correct
# Line 102  disable optimization (in this module it Line 121  disable optimization (in this module it
121  the pcre module can use all the optimization it can get). */  the pcre module can use all the optimization it can get). */
122    
123  volatile int dummy;  volatile int dummy;
124    /* ========================================================================= */
125    #endif
126    
127  do  do
128    {    {
129    const uschar *tcode = code + 1 + LINK_SIZE;    const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
130    BOOL try_next = TRUE;    BOOL try_next = TRUE;
131    
132    while (try_next)    while (try_next)    /* Loop for items in this branch */
133      {      {
134      /* If a branch starts with a bracket or a positive lookahead assertion,      int rc;
135      recurse to set bits from within them. That's all for this branch. */      switch(*tcode)
   
     if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT)  
136        {        {
137        if (!set_start_bits(tcode, start_bits, caseless, utf8, cd))        /* Fail if we reach something we don't understand */
         return FALSE;  
       try_next = FALSE;  
       }  
138    
     else switch(*tcode)  
       {  
139        default:        default:
140        return FALSE;        return SSB_FAIL;
141    
142        /* Skip over callout */        /* If we hit a bracket or a positive lookahead assertion, recurse to set
143          bits from within the subpattern. If it can't find anything, we have to
144          give up. If it finds some mandatory character(s), we are done for this
145          branch. Otherwise, carry on scanning after the subpattern. */
146    
147          case OP_BRA:
148          case OP_SBRA:
149          case OP_CBRA:
150          case OP_SCBRA:
151          case OP_ONCE:
152          case OP_ASSERT:
153          rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
154          if (rc == SSB_FAIL) return SSB_FAIL;
155          if (rc == SSB_DONE) try_next = FALSE; else
156            {
157            do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
158            tcode += 1 + LINK_SIZE;
159            }
160          break;
161    
162        case OP_CALLOUT:        /* If we hit ALT or KET, it means we haven't found anything mandatory in
163        tcode += 2 + 2*LINK_SIZE;        this branch, though we might have found something optional. For ALT, we
164          continue with the next alternative, but we have to arrange that the final
165          result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
166          return SSB_CONTINUE: if this is the top level, that indicates failure,
167          but after a nested subpattern, it causes scanning to continue. */
168    
169          case OP_ALT:
170          yield = SSB_CONTINUE;
171          try_next = FALSE;
172        break;        break;
173    
174        /* Skip over extended extraction bracket number */        case OP_KET:
175          case OP_KETRMAX:
176          case OP_KETRMIN:
177          return SSB_CONTINUE;
178    
179        case OP_BRANUMBER:        /* Skip over callout */
180        tcode += 3;  
181          case OP_CALLOUT:
182          tcode += 2 + 2*LINK_SIZE;
183        break;        break;
184    
185        /* Skip over lookbehind and negative lookahead assertions */        /* Skip over lookbehind and negative lookahead assertions */
# Line 143  do Line 188  do
188        case OP_ASSERTBACK:        case OP_ASSERTBACK:
189        case OP_ASSERTBACK_NOT:        case OP_ASSERTBACK_NOT:
190        do tcode += GET(tcode, 1); while (*tcode == OP_ALT);        do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
191        tcode += 1+LINK_SIZE;        tcode += 1 + LINK_SIZE;
192        break;        break;
193    
194        /* Skip over an option setting, changing the caseless flag */        /* Skip over an option setting, changing the caseless flag */
# Line 157  do Line 202  do
202    
203        case OP_BRAZERO:        case OP_BRAZERO:
204        case OP_BRAMINZERO:        case OP_BRAMINZERO:
205        if (!set_start_bits(++tcode, start_bits, caseless, utf8, cd))        if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
206          return FALSE;          return SSB_FAIL;
207    /* =========================================================================
208          See the comment at the head of this function concerning the next line,
209          which was an old fudge for the benefit of OS/2.
210        dummy = 1;        dummy = 1;
211      ========================================================================= */
212        do tcode += GET(tcode,1); while (*tcode == OP_ALT);        do tcode += GET(tcode,1); while (*tcode == OP_ALT);
213        tcode += 1+LINK_SIZE;        tcode += 1 + LINK_SIZE;
214        break;        break;
215    
216        /* Single-char * or ? sets the bit and tries the next item */        /* Single-char * or ? sets the bit and tries the next item */
217    
218        case OP_STAR:        case OP_STAR:
219        case OP_MINSTAR:        case OP_MINSTAR:
220          case OP_POSSTAR:
221        case OP_QUERY:        case OP_QUERY:
222        case OP_MINQUERY:        case OP_MINQUERY:
223          case OP_POSQUERY:
224        set_bit(start_bits, tcode[1], caseless, cd);        set_bit(start_bits, tcode[1], caseless, cd);
225        tcode += 2;        tcode += 2;
226  #ifdef SUPPORT_UTF8  #ifdef SUPPORT_UTF8
227        if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;        if (utf8 && tcode[-1] >= 0xc0)
228            tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
229  #endif  #endif
230        break;        break;
231    
# Line 181  do Line 233  do
233    
234        case OP_UPTO:        case OP_UPTO:
235        case OP_MINUPTO:        case OP_MINUPTO:
236          case OP_POSUPTO:
237        set_bit(start_bits, tcode[3], caseless, cd);        set_bit(start_bits, tcode[3], caseless, cd);
238        tcode += 4;        tcode += 4;
239  #ifdef SUPPORT_UTF8  #ifdef SUPPORT_UTF8
240        if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;        if (utf8 && tcode[-1] >= 0xc0)
241            tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
242  #endif  #endif
243        break;        break;
244    
# Line 197  do Line 251  do
251        case OP_CHARNC:        case OP_CHARNC:
252        case OP_PLUS:        case OP_PLUS:
253        case OP_MINPLUS:        case OP_MINPLUS:
254          case OP_POSPLUS:
255        set_bit(start_bits, tcode[1], caseless, cd);        set_bit(start_bits, tcode[1], caseless, cd);
256        try_next = FALSE;        try_next = FALSE;
257        break;        break;
# Line 215  do Line 270  do
270        try_next = FALSE;        try_next = FALSE;
271        break;        break;
272    
273          /* The cbit_space table has vertical tab as whitespace; we have to
274          discard it. */
275    
276        case OP_NOT_WHITESPACE:        case OP_NOT_WHITESPACE:
277        for (c = 0; c < 32; c++)        for (c = 0; c < 32; c++)
278          start_bits[c] |= ~cd->cbits[c+cbit_space];          {
279            int d = cd->cbits[c+cbit_space];
280            if (c == 1) d &= ~0x08;
281            start_bits[c] |= ~d;
282            }
283        try_next = FALSE;        try_next = FALSE;
284        break;        break;
285    
286          /* The cbit_space table has vertical tab as whitespace; we have to
287          discard it. */
288    
289        case OP_WHITESPACE:        case OP_WHITESPACE:
290        for (c = 0; c < 32; c++)        for (c = 0; c < 32; c++)
291          start_bits[c] |= cd->cbits[c+cbit_space];          {
292            int d = cd->cbits[c+cbit_space];
293            if (c == 1) d &= ~0x08;
294            start_bits[c] |= d;
295            }
296        try_next = FALSE;        try_next = FALSE;
297        break;        break;
298    
# Line 256  do Line 325  do
325    
326        case OP_TYPEUPTO:        case OP_TYPEUPTO:
327        case OP_TYPEMINUPTO:        case OP_TYPEMINUPTO:
328          case OP_TYPEPOSUPTO:
329        tcode += 2;               /* Fall through */        tcode += 2;               /* Fall through */
330    
331        case OP_TYPESTAR:        case OP_TYPESTAR:
332        case OP_TYPEMINSTAR:        case OP_TYPEMINSTAR:
333          case OP_TYPEPOSSTAR:
334        case OP_TYPEQUERY:        case OP_TYPEQUERY:
335        case OP_TYPEMINQUERY:        case OP_TYPEMINQUERY:
336          case OP_TYPEPOSQUERY:
337        switch(tcode[1])        switch(tcode[1])
338          {          {
339          case OP_ANY:          case OP_ANY:
340          return FALSE;          return SSB_FAIL;
341    
342          case OP_NOT_DIGIT:          case OP_NOT_DIGIT:
343          for (c = 0; c < 32; c++)          for (c = 0; c < 32; c++)
# Line 277  do Line 349  do
349            start_bits[c] |= cd->cbits[c+cbit_digit];            start_bits[c] |= cd->cbits[c+cbit_digit];
350          break;          break;
351    
352            /* The cbit_space table has vertical tab as whitespace; we have to
353            discard it. */
354    
355          case OP_NOT_WHITESPACE:          case OP_NOT_WHITESPACE:
356          for (c = 0; c < 32; c++)          for (c = 0; c < 32; c++)
357            start_bits[c] |= ~cd->cbits[c+cbit_space];            {
358              int d = cd->cbits[c+cbit_space];
359              if (c == 1) d &= ~0x08;
360              start_bits[c] |= ~d;
361              }
362          break;          break;
363    
364            /* The cbit_space table has vertical tab as whitespace; we have to
365            discard it. */
366    
367          case OP_WHITESPACE:          case OP_WHITESPACE:
368          for (c = 0; c < 32; c++)          for (c = 0; c < 32; c++)
369            start_bits[c] |= cd->cbits[c+cbit_space];            {
370              int d = cd->cbits[c+cbit_space];
371              if (c == 1) d &= ~0x08;
372              start_bits[c] |= d;
373              }
374          break;          break;
375    
376          case OP_NOT_WORDCHAR:          case OP_NOT_WORDCHAR:
# Line 308  do Line 394  do
394        character with a value > 255. */        character with a value > 255. */
395    
396        case OP_NCLASS:        case OP_NCLASS:
397    #ifdef SUPPORT_UTF8
398        if (utf8)        if (utf8)
399          {          {
400          start_bits[24] |= 0xf0;              /* Bits for 0xc4 - 0xc8 */          start_bits[24] |= 0xf0;              /* Bits for 0xc4 - 0xc8 */
401          memset(start_bits+25, 0xff, 7);      /* Bits for 0xc9 - 0xff */          memset(start_bits+25, 0xff, 7);      /* Bits for 0xc9 - 0xff */
402          }          }
403    #endif
404        /* Fall through */        /* Fall through */
405    
406        case OP_CLASS:        case OP_CLASS:
# Line 325  do Line 413  do
413          value is > 127. In fact, there are only two possible starting bytes for          value is > 127. In fact, there are only two possible starting bytes for
414          characters in the range 128 - 255. */          characters in the range 128 - 255. */
415    
416    #ifdef SUPPORT_UTF8
417          if (utf8)          if (utf8)
418            {            {
419            for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];            for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
# Line 342  do Line 431  do
431          /* In non-UTF-8 mode, the two bit maps are completely compatible. */          /* In non-UTF-8 mode, the two bit maps are completely compatible. */
432    
433          else          else
434    #endif
435            {            {
436            for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];            for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
437            }            }
# Line 377  do Line 467  do
467    code += GET(code, 1);   /* Advance to next branch */    code += GET(code, 1);   /* Advance to next branch */
468    }    }
469  while (*code == OP_ALT);  while (*code == OP_ALT);
470  return TRUE;  return yield;
471  }  }
472    
473    
# Line 401  Returns: pointer to a pcre_extra bloc Line 491  Returns: pointer to a pcre_extra bloc
491              NULL on error or if no optimization possible              NULL on error or if no optimization possible
492  */  */
493    
494  EXPORT pcre_extra *  PCRE_EXP_DEFN pcre_extra *
495  pcre_study(const pcre *external_re, int options, const char **errorptr)  pcre_study(const pcre *external_re, int options, const char **errorptr)
496  {  {
497  uschar start_bits[32];  uschar start_bits[32];
498  pcre_extra *extra;  pcre_extra *extra;
499  pcre_study_data *study;  pcre_study_data *study;
500  const uschar *tables;  const uschar *tables;
501  const real_pcre *re = (const real_pcre *)external_re;  uschar *code;
 uschar *code = (uschar *)re + re->name_table_offset +  
   (re->name_count * re->name_entry_size);  
502  compile_data compile_block;  compile_data compile_block;
503    const real_pcre *re = (const real_pcre *)external_re;
504    
505  *errorptr = NULL;  *errorptr = NULL;
506    
# Line 427  if ((options & ~PUBLIC_STUDY_OPTIONS) != Line 516  if ((options & ~PUBLIC_STUDY_OPTIONS) !=
516    return NULL;    return NULL;
517    }    }
518    
519    code = (uschar *)re + re->name_table_offset +
520      (re->name_count * re->name_entry_size);
521    
522  /* For an anchored pattern, or an unanchored pattern that has a first char, or  /* For an anchored pattern, or an unanchored pattern that has a first char, or
523  a multiline pattern that matches only at "line starts", no further processing  a multiline pattern that matches only at "line starts", no further processing
524  at present. */  at present. */
# Line 449  compile_block.ctypes = tables + ctypes_o Line 541  compile_block.ctypes = tables + ctypes_o
541  /* 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. */
542    
543  memset(start_bits, 0, 32 * sizeof(uschar));  memset(start_bits, 0, 32 * sizeof(uschar));
544  if (!set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,  if (set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
545    (re->options & PCRE_UTF8) != 0, &compile_block)) return NULL;    (re->options & PCRE_UTF8) != 0, &compile_block) != SSB_DONE) return NULL;
546    
547  /* 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
548  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
Legend:
Removed from v.77  
changed lines
  Added in v.145
webmaster@exim.org
 ViewVC Help
Powered by ViewVC 1.1.12