/[pcre]/code/tags/pcre-3.2/pcre.c

Diff of /code/tags/pcre-3.2/pcre.c

Parent Directory | Revision Log | View Patch Patch

-revision 27 by nigel,
Sat Feb 24 21:38:49 2007 UTC
+revision 43 by nigel,
Sat Feb 24 21:39:21 2007 UTC
 Line 9 
 the file Tech.Notes for some information
  Written by: Philip Hazel <ph10@cam.ac.uk>
-            Copyright (c) 1997-1999 University of Cambridge
+            Copyright (c) 1997-2000 University of Cambridge
  -----------------------------------------------------------------------------
  Permission is granted to anyone to use this software for any purpose on any
 Line 25 
 restrictions:
 . Altered versions must be plainly marked as such, and must not be
     misrepresented as being the original software.
+. If PCRE is embedded in any software that is released under the GNU
+    General Purpose Licence (GPL), then the terms of that licence shall
+    supersede any condition above with which it is incompatible.
  -----------------------------------------------------------------------------
  */
-Line 78 
 static const char *OP_names[] = {
+Line 82 
 static const char *OP_names[] = {
    "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
    "*", "*?", "+", "+?", "?", "??", "{", "{", "{",
    "*", "*?", "+", "+?", "?", "??", "{", "{",
-   "class", "Ref",
+   "class", "Ref", "Recurse",
    "Alt", "Ket", "KetRmax", "KetRmin", "Assert", "Assert not",
    "AssertB", "AssertB not", "Reverse", "Once", "Cond", "Cref",
    "Brazero", "Braminzero", "Bra"
-Line 103 
 static const short int escapes[] = {
+Line 107 
 static const short int escapes[] = {
 ,      0, -ESC_z                                            /* x - z */
  };
+ /* Tables of names of POSIX character classes and their lengths. The list is
+ terminated by a zero length entry. The first three must be alpha, upper, lower,
+ as this is assumed for handling case independence. */
+ static const char *posix_names[] = {
+   "alpha", "lower", "upper",
+   "alnum", "ascii", "cntrl", "digit", "graph",
+   "print", "punct", "space", "word",  "xdigit" };
+ static const uschar posix_name_lengths[] = {
+, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 6, 0 };
+ /* Table of class bit maps for each POSIX class; up to three may be combined
+ to form the class. */
+ static const int posix_class_maps[] = {
+   cbit_lower, cbit_upper, -1,             /* alpha */
+   cbit_lower, -1,         -1,             /* lower */
+   cbit_upper, -1,         -1,             /* upper */
+   cbit_digit, cbit_lower, cbit_upper,     /* alnum */
+   cbit_print, cbit_cntrl, -1,             /* ascii */
+   cbit_cntrl, -1,         -1,             /* cntrl */
+   cbit_digit, -1,         -1,             /* digit */
+   cbit_graph, -1,         -1,             /* graph */
+   cbit_print, -1,         -1,             /* print */
+   cbit_punct, -1,         -1,             /* punct */
+   cbit_space, -1,         -1,             /* space */
+   cbit_word,  -1,         -1,             /* word */
+   cbit_xdigit,-1,         -1              /* xdigit */
+ };
  /* Definition to allow mutual recursion */
  static BOOL
    compile_regex(int, int, int *, uschar **, const uschar **, const char **,
-     BOOL, int, compile_data *);
+     BOOL, int, int *, int *, compile_data *);
-Line 144 
 tables. */
+Line 180 
 tables. */
  *          Return version string                 *
  *************************************************/
+ #define STRING(a)  # a
+ #define XSTRING(s) STRING(s)
  const char *
  pcre_version(void)
  {
- return PCRE_VERSION;
+ return XSTRING(PCRE_MAJOR) "." XSTRING(PCRE_MINOR) " " XSTRING(PCRE_DATE);
  }
  /*************************************************
- *       Return info about a compiled pattern     *
+ * (Obsolete) Return info about compiled pattern  *
  *************************************************/
- /* This function picks potentially useful data out of the private
+ /* This is the original "info" function. It picks potentially useful data out
- structure.
+ of the private structure, but its interface was too rigid. It remains for
+ backwards compatibility. The public options are passed back in an int - though
+ the re->options field has been expanded to a long int, all the public options
+ at the low end of it, and so even on 16-bit systems this will still be OK.
+ Therefore, I haven't changed the API for pcre_info().
  Arguments:
    external_re   points to compiled code
-Line 167 
 Arguments:
+Line 210 
 Arguments:
                  or -1 if multiline and all branches start ^,
                  or -2 otherwise
- Returns:        number of identifying extraction brackets
+ Returns:        number of capturing subpatterns
                  or negative values on error
  */
-Line 177 
 pcre_info(const pcre *external_re, int *
+Line 220 
 pcre_info(const pcre *external_re, int *
  const real_pcre *re = (const real_pcre *)external_re;
  if (re == NULL) return PCRE_ERROR_NULL;
  if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
- if (optptr != NULL) *optptr = (re->options & PUBLIC_OPTIONS);
+ if (optptr != NULL) *optptr = (int)(re->options & PUBLIC_OPTIONS);
  if (first_char != NULL)
    *first_char = ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
       ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
-Line 186 
 return re->top_bracket;
+Line 229 
 return re->top_bracket;
+ /*************************************************
+ *        Return info about compiled pattern      *
+ *************************************************/
+ /* This is a newer "info" function which has an extensible interface so
+ that additional items can be added compatibly.
+ Arguments:
+   external_re      points to compiled code
+   external_study   points to study data, or NULL
+   what             what information is required
+   where            where to put the information
+ Returns:           0 if data returned, negative on error
+ */
+ int
+ pcre_fullinfo(const pcre *external_re, const pcre_extra *study_data, int what,
+   void *where)
+ {
+ const real_pcre *re = (const real_pcre *)external_re;
+ const real_pcre_extra *study = (const real_pcre_extra *)study_data;
+ if (re == NULL || where == NULL) return PCRE_ERROR_NULL;
+ if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
+ switch (what)
+   {
+   case PCRE_INFO_OPTIONS:
+   *((unsigned long int *)where) = re->options & PUBLIC_OPTIONS;
+   break;
+   case PCRE_INFO_SIZE:
+   *((size_t *)where) = re->size;
+   break;
+   case PCRE_INFO_CAPTURECOUNT:
+   *((int *)where) = re->top_bracket;
+   break;
+   case PCRE_INFO_BACKREFMAX:
+   *((int *)where) = re->top_backref;
+   break;
+   case PCRE_INFO_FIRSTCHAR:
+   *((int *)where) =
+     ((re->options & PCRE_FIRSTSET) != 0)? re->first_char :
+     ((re->options & PCRE_STARTLINE) != 0)? -1 : -2;
+   break;
+   case PCRE_INFO_FIRSTTABLE:
+   *((const uschar **)where) =
+     (study != NULL && (study->options & PCRE_STUDY_MAPPED) != 0)?
+       study->start_bits : NULL;
+   break;
+   case PCRE_INFO_LASTLITERAL:
+   *((int *)where) =
+     ((re->options & PCRE_REQCHSET) != 0)? re->req_char : -1;
+   break;
+   default: return PCRE_ERROR_BADOPTION;
+   }
+ return 0;
+ }
  #ifdef DEBUG
  /*************************************************
-Line 245 
 check_escape(const uschar **ptrptr, cons
+Line 356 
 check_escape(const uschar **ptrptr, cons
    int options, BOOL isclass, compile_data *cd)
  {
  const uschar *ptr = *ptrptr;
- int c = *(++ptr) & 255;   /* Ensure > 0 on signed-char systems */
+ int c, i;
- int i;
+ c = *(++ptr) & 255;   /* Ensure > 0 on signed-char systems */
  if (c == 0) *errorptr = ERR1;
  /* Digits or letters may have special meaning; all others are literals. */
-Line 528 
 for (;;)
+Line 639 
 for (;;)
      case OP_REVERSE:
      cc++;
+     /* Fall through */
      case OP_CREF:
      case OP_OPT:
-Line 611 
 for (;;)
+Line 723 
 for (;;)
  /*************************************************
+ *           Check for POSIX class syntax         *
+ *************************************************/
+ /* This function is called when the sequence "[:" or "[." or "[=" is
+ encountered in a character class. It checks whether this is followed by an
+ optional ^ and then a sequence of letters, terminated by a matching ":]" or
+ ".]" or "=]".
+ Argument:
+   ptr      pointer to the initial [
+   endptr   where to return the end pointer
+   cd       pointer to compile data
+ Returns:   TRUE or FALSE
+ */
+ static BOOL
+ check_posix_syntax(const uschar *ptr, const uschar **endptr, compile_data *cd)
+ {
+ int terminator;          /* Don't combine these lines; the Solaris cc */
+ terminator = *(++ptr);   /* compiler warns about "non-constant" initializer. */
+ if (*(++ptr) == '^') ptr++;
+ while ((cd->ctypes[*ptr] & ctype_letter) != 0) ptr++;
+ if (*ptr == terminator && ptr[1] == ']')
+   {
+   *endptr = ptr;
+   return TRUE;
+   }
+ return FALSE;
+ }
+ /*************************************************
+ *          Check POSIX class name                *
+ *************************************************/
+ /* This function is called to check the name given in a POSIX-style class entry
+ such as [:alnum:].
+ Arguments:
+   ptr        points to the first letter
+   len        the length of the name
+ Returns:     a value representing the name, or -1 if unknown
+ */
+ static int
+ check_posix_name(const uschar *ptr, int len)
+ {
+ register int yield = 0;
+ while (posix_name_lengths[yield] != 0)
+   {
+   if (len == posix_name_lengths[yield] &&
+     strncmp((const char *)ptr, posix_names[yield], len) == 0) return yield;
+   yield++;
+   }
+ return -1;
+ }
+ /*************************************************
  *           Compile one branch                   *
  *************************************************/
-Line 623 
 Arguments:
+Line 800 
 Arguments:
    ptrptr       points to the current pattern pointer
    errorptr     points to pointer to error message
    optchanged   set to the value of the last OP_OPT item compiled
+   reqchar      set to the last literal character required, else -1
+   countlits    set to count of mandatory literal characters
    cd           contains pointers to tables
  Returns:       TRUE on success
-Line 632 
 Returns:       TRUE on success
+Line 811 
 Returns:       TRUE on success
  static BOOL
  compile_branch(int options, int *brackets, uschar **codeptr,
    const uschar **ptrptr, const char **errorptr, int *optchanged,
-   compile_data *cd)
+   int *reqchar, int *countlits, compile_data *cd)
  {
  int repeat_type, op_type;
  int repeat_min, repeat_max;
  int bravalue, length;
  int greedy_default, greedy_non_default;
+ int prevreqchar;
+ int condcount = 0;
+ int subcountlits = 0;
  register int c;
  register uschar *code = *codeptr;
  uschar *tempcode;
-Line 651 
 uschar class[32];
+Line 833 
 uschar class[32];
  greedy_default = ((options & PCRE_UNGREEDY) != 0);
  greedy_non_default = greedy_default ^ 1;
+ /* Initialize no required char, and count of literals */
+ *reqchar = prevreqchar = -1;
+ *countlits = 0;
  /* Switch on next character until the end of the branch */
  for (;; ptr++)
-Line 660 
 for (;; ptr++)
+Line 847 
 for (;; ptr++)
    int class_lastchar;
    int newoptions;
    int condref;
+   int subreqchar;
    c = *ptr;
    if ((options & PCRE_EXTENDED) != 0)
-Line 742 
 for (;; ptr++)
+Line 930 
 for (;; ptr++)
          goto FAILED;
          }
+       /* Handle POSIX class names. Perl allows a negation extension of the
+       form [:^name]. A square bracket that doesn't match the syntax is
+       treated as a literal. We also recognize the POSIX constructions
+       [.ch.] and [=ch=] ("collating elements") and fault them, as Perl
+.6 does. */
+       if (c == '[' &&
+           (ptr[1] == ':' || ptr[1] == '.' || ptr[1] == '=') &&
+           check_posix_syntax(ptr, &tempptr, cd))
+         {
+         BOOL local_negate = FALSE;
+         int posix_class, i;
+         register const uschar *cbits = cd->cbits;
+         if (ptr[1] != ':')
+           {
+           *errorptr = ERR31;
+           goto FAILED;
+           }
+         ptr += 2;
+         if (*ptr == '^')
+           {
+           local_negate = TRUE;
+           ptr++;
+           }
+         posix_class = check_posix_name(ptr, tempptr - ptr);
+         if (posix_class < 0)
+           {
+           *errorptr = ERR30;
+           goto FAILED;
+           }
+         /* If matching is caseless, upper and lower are converted to
+         alpha. This relies on the fact that the class table starts with
+         alpha, lower, upper as the first 3 entries. */
+         if ((options & PCRE_CASELESS) != 0 && posix_class <= 2)
+           posix_class = 0;
+         /* Or into the map we are building up to 3 of the static class
+         tables, or their negations. */
+         posix_class *= 3;
+         for (i = 0; i < 3; i++)
+           {
+           int taboffset = posix_class_maps[posix_class + i];
+           if (taboffset < 0) break;
+           if (local_negate)
+             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+taboffset];
+           else
+             for (c = 0; c < 32; c++) class[c] |= cbits[c+taboffset];
+           }
+         ptr = tempptr + 1;
+         class_charcount = 10;  /* Set > 1; assumes more than 1 per class */
+         continue;
+         }
        /* Backslash may introduce a single character, or it may introduce one
        of the specials, which just set a flag. Escaped items are checked for
        validity in the pre-compiling pass. The sequence \b is a special case.
-Line 769 
 for (;; ptr++)
+Line 1017 
 for (;; ptr++)
              continue;
              case ESC_w:
-             for (c = 0; c < 32; c++)
+             for (c = 0; c < 32; c++) class[c] |= cbits[c+cbit_word];
-               class[c] |= (cbits[c+cbit_digit] | cbits[c+cbit_word]);
              continue;
              case ESC_W:
-             for (c = 0; c < 32; c++)
+             for (c = 0; c < 32; c++) class[c] |= ~cbits[c+cbit_word];
-               class[c] |= ~(cbits[c+cbit_digit] | cbits[c+cbit_word]);
              continue;
              case ESC_s:
-Line 933 
 for (;; ptr++)
+Line 1179 
 for (;; ptr++)
        { repeat_type = greedy_non_default; ptr++; }
      else repeat_type = greedy_default;
-     /* If the maximum is zero then the minimum must also be zero; Perl allows
-     this case, so we do too - by simply omitting the item altogether. */
-     if (repeat_max == 0) code = previous;
      /* If previous was a string of characters, chop off the last one and use it
      as the subject of the repeat. If there was only one character, we can
-     abolish the previous item altogether. */
+     abolish the previous item altogether. A repeat with a zero minimum wipes
+     out any reqchar setting, backing up to the previous value. We must also
+     adjust the countlits value. */
-     else if (*previous == OP_CHARS)
+     if (*previous == OP_CHARS)
        {
        int len = previous[1];
+       if (repeat_min == 0) *reqchar = prevreqchar;
+       *countlits += repeat_min - 1;
        if (len == 1)
          {
          c = previous[2];
-Line 983 
 for (;; ptr++)
+Line 1230 
 for (;; ptr++)
        code = previous;
        OUTPUT_SINGLE_REPEAT:
-       repeat_type += op_type;      /* Combine both values for many cases */
+       /* If the maximum is zero then the minimum must also be zero; Perl allows
+       this case, so we do too - by simply omitting the item altogether. */
+       if (repeat_max == 0) goto END_REPEAT;
+       /* Combine the op_type with the repeat_type */
+       repeat_type += op_type;
        /* A minimum of zero is handled either as the special case * or ?, or as
        an UPTO, with the maximum given. */
-Line 1060 
 for (;; ptr++)
+Line 1315 
 for (;; ptr++)
        }
      /* If previous was a character class or a back reference, we put the repeat
-     stuff after it. */
+     stuff after it, but just skip the item if the repeat was {0,0}. */
      else if (*previous == OP_CLASS || *previous == OP_REF)
        {
+       if (repeat_max == 0)
+         {
+         code = previous;
+         goto END_REPEAT;
+         }
        if (repeat_min == 0 && repeat_max == -1)
          *code++ = OP_CRSTAR + repeat_type;
        else if (repeat_min == 1 && repeat_max == -1)
-Line 1087 
 for (;; ptr++)
+Line 1347 
 for (;; ptr++)
      else if ((int)*previous >= OP_BRA || (int)*previous == OP_ONCE ||
               (int)*previous == OP_COND)
        {
-       int i, ketoffset = 0;
+       register int i;
+       int ketoffset = 0;
        int len = code - previous;
+       uschar *bralink = NULL;
        /* If the maximum repeat count is unlimited, find the end of the bracket
        by scanning through from the start, and compute the offset back to it
-Line 1103 
 for (;; ptr++)
+Line 1365 
 for (;; ptr++)
          ketoffset = code - ket;
          }
-       /* If the minimum is greater than zero, and the maximum is unlimited or
+       /* The case of a zero minimum is special because of the need to stick
-       equal to the minimum, the first copy remains where it is, and is
+       OP_BRAZERO in front of it, and because the group appears once in the
-       replicated up to the minimum number of times. This case includes the +
+       data, whereas in other cases it appears the minimum number of times. For
-       repeat, but of course no replication is needed in that case. */
+       this reason, it is simplest to treat this case separately, as otherwise
+       the code gets far too mess. There are several special subcases when the
+       minimum is zero. */
-       if (repeat_min > 0 && (repeat_max == -1 || repeat_max == repeat_min))
+       if (repeat_min == 0)
          {
-         for (i = 1; i < repeat_min; i++)
+         /* If we set up a required char from the bracket, we must back off
+         to the previous value and reset the countlits value too. */
+         if (subcountlits > 0)
            {
-           memcpy(code, previous, len);
+           *reqchar = prevreqchar;
-           code += len;
+           *countlits -= subcountlits;
            }
-         }
-       /* If the minimum is zero, stick BRAZERO in front of the first copy.
+         /* If the maximum is also zero, we just omit the group from the output
-       Then, if there is a fixed upper limit, replicated up to that many times,
+         altogether. */
-       sticking BRAZERO in front of all the optional ones. */
-       else
+         if (repeat_max == 0)
-         {
+           {
-         if (repeat_min == 0)
+           code = previous;
+           goto END_REPEAT;
+           }
+         /* If the maximum is 1 or unlimited, we just have to stick in the
+         BRAZERO and do no more at this point. */
+         if (repeat_max <= 1)
            {
            memmove(previous+1, previous, len);
            code++;
            *previous++ = OP_BRAZERO + repeat_type;
            }
+         /* If the maximum is greater than 1 and limited, we have to replicate
+         in a nested fashion, sticking OP_BRAZERO before each set of brackets.
+         The first one has to be handled carefully because it's the original
+         copy, which has to be moved up. The remainder can be handled by code
+         that is common with the non-zero minimum case below. We just have to
+         adjust the value or repeat_max, since one less copy is required. */
+         else
+           {
+           int offset;
+           memmove(previous+4, previous, len);
+           code += 4;
+           *previous++ = OP_BRAZERO + repeat_type;
+           *previous++ = OP_BRA;
+           /* We chain together the bracket offset fields that have to be
+           filled in later when the ends of the brackets are reached. */
+           offset = (bralink == NULL)? 0 : previous - bralink;
+           bralink = previous;
+           *previous++ = offset >> 8;
+           *previous++ = offset & 255;
+           }
+         repeat_max--;
+         }
+       /* If the minimum is greater than zero, replicate the group as many
+       times as necessary, and adjust the maximum to the number of subsequent
+       copies that we need. */
+       else
+         {
          for (i = 1; i < repeat_min; i++)
            {
            memcpy(code, previous, len);
            code += len;
            }
+         if (repeat_max > 0) repeat_max -= repeat_min;
+         }
-         for (i = (repeat_min > 0)? repeat_min : 1; i < repeat_max; i++)
+       /* This code is common to both the zero and non-zero minimum cases. If
+       the maximum is limited, it replicates the group in a nested fashion,
+       remembering the bracket starts on a stack. In the case of a zero minimum,
+       the first one was set up above. In all cases the repeat_max now specifies
+       the number of additional copies needed. */
+       if (repeat_max >= 0)
+         {
+         for (i = repeat_max - 1; i >= 0; i--)
            {
            *code++ = OP_BRAZERO + repeat_type;
+           /* All but the final copy start a new nesting, maintaining the
+           chain of brackets outstanding. */
+           if (i != 0)
+             {
+             int offset;
+             *code++ = OP_BRA;
+             offset = (bralink == NULL)? 0 : code - bralink;
+             bralink = code;
+             *code++ = offset >> 8;
+             *code++ = offset & 255;
+             }
            memcpy(code, previous, len);
            code += len;
            }
+         /* Now chain through the pending brackets, and fill in their length
+         fields (which are holding the chain links pro tem). */
+         while (bralink != NULL)
+           {
+           int oldlinkoffset;
+           int offset = code - bralink + 1;
+           uschar *bra = code - offset;
+           oldlinkoffset = (bra[1] << 8) + bra[2];
+           bralink = (oldlinkoffset == 0)? NULL : bralink - oldlinkoffset;
+           *code++ = OP_KET;
+           *code++ = bra[1] = offset >> 8;
+           *code++ = bra[2] = (offset & 255);
+           }
          }
        /* If the maximum is unlimited, set a repeater in the final copy. We
-Line 1149 
 for (;; ptr++)
+Line 1493 
 for (;; ptr++)
        don't know if there's been an options resetting after the ket. The
        correct offset was computed above. */
-       if (repeat_max == -1) code[-ketoffset] = OP_KETRMAX + repeat_type;
+       else code[-ketoffset] = OP_KETRMAX + repeat_type;
        }
      /* Else there's some kind of shambles */
-Line 1162 
 for (;; ptr++)
+Line 1506 
 for (;; ptr++)
      /* In all case we no longer have a previous item. */
+     END_REPEAT:
      previous = NULL;
      break;
-Line 1239 
 for (;; ptr++)
+Line 1584 
 for (;; ptr++)
          ptr++;
          break;
+         case 'R':                 /* Pattern recursion */
+         *code++ = OP_RECURSE;
+         ptr++;
+         continue;
          default:                  /* Option setting */
          set = unset = 0;
          optset = &set;
-Line 1330 
 for (;; ptr++)
+Line 1680 
 for (;; ptr++)
           (bravalue == OP_ASSERTBACK ||
            bravalue == OP_ASSERTBACK_NOT), /* TRUE if back assert */
           condref,                      /* Condition reference number */
+          &subreqchar,                  /* For possible last char */
+          &subcountlits,                /* For literal count */
           cd))                          /* Tables block */
        goto FAILED;
-Line 1343 
 for (;; ptr++)
+Line 1695 
 for (;; ptr++)
      if (bravalue == OP_COND)
        {
-       int branchcount = 0;
        uschar *tc = code;
+       condcount = 0;
        do {
-          branchcount++;
+          condcount++;
           tc += (tc[1] << 8) | tc[2];
           }
        while (*tc != OP_KET);
-       if (branchcount > 2)
+       if (condcount > 2)
          {
          *errorptr = ERR27;
          goto FAILED;
          }
        }
+     /* Handle updating of the required character. If the subpattern didn't
+     set one, leave it as it was. Otherwise, update it for normal brackets of
+     all kinds, forward assertions, and conditions with two branches. Don't
+     update the literal count for forward assertions, however. If the bracket
+     is followed by a quantifier with zero repeat, we have to back off. Hence
+     the definition of prevreqchar and subcountlits outside the main loop so
+     that they can be accessed for the back off. */
+     if (subreqchar > 0 &&
+          (bravalue >= OP_BRA || bravalue == OP_ONCE || bravalue == OP_ASSERT ||
+          (bravalue == OP_COND && condcount == 2)))
+       {
+       prevreqchar = *reqchar;
+       *reqchar = subreqchar;
+       if (bravalue != OP_ASSERT) *countlits += subcountlits;
+       }
      /* Now update the main code pointer to the end of the group. */
      code = tempcode;
-Line 1453 
 for (;; ptr++)
+Line 1822 
 for (;; ptr++)
      while (length < 255 && (cd->ctypes[c = *(++ptr)] & ctype_meta) == 0);
+     /* Update the last character and the count of literals */
+     prevreqchar = (length > 1)? code[-2] : *reqchar;
+     *reqchar = code[-1];
+     *countlits += length;
      /* Compute the length and set it in the data vector, and advance to
      the next state. */
-Line 1496 
 Argument:
+Line 1871 
 Argument:
    errorptr    -> pointer to error message
    lookbehind  TRUE if this is a lookbehind assertion
    condref     > 0 for OPT_CREF setting at start of conditional group
+   reqchar     -> place to put the last required character, or a negative number
+   countlits   -> place to put the shortest literal count of any branch
    cd          points to the data block with tables pointers
  Returns:      TRUE on success
-Line 1504 
 Returns:      TRUE on success
+Line 1881 
 Returns:      TRUE on success
  static BOOL
  compile_regex(int options, int optchanged, int *brackets, uschar **codeptr,
    const uschar **ptrptr, const char **errorptr, BOOL lookbehind, int condref,
-   compile_data *cd)
+   int *reqchar, int *countlits, compile_data *cd)
  {
  const uschar *ptr = *ptrptr;
  uschar *code = *codeptr;
-Line 1512 
 uschar *last_branch = code;
+Line 1889 
 uschar *last_branch = code;
  uschar *start_bracket = code;
  uschar *reverse_count = NULL;
  int oldoptions = options & PCRE_IMS;
+ int branchreqchar, branchcountlits;
+ *reqchar = -1;
+ *countlits = INT_MAX;
  code += 3;
  /* At the start of a reference-based conditional group, insert the reference
-Line 1551 
 for (;;)
+Line 1931 
 for (;;)
    /* Now compile the branch */
-   if (!compile_branch(options,brackets,&code,&ptr,errorptr,&optchanged,cd))
+   if (!compile_branch(options, brackets, &code, &ptr, errorptr, &optchanged,
+       &branchreqchar, &branchcountlits, cd))
      {
      *ptrptr = ptr;
      return FALSE;
-Line 1563 
 for (;;)
+Line 1944 
 for (;;)
    last_branch[1] = length >> 8;
    last_branch[2] = length & 255;
+   /* Save the last required character if all branches have the same; a current
+   value of -1 means unset, while -2 means "previous branch had no last required
+   char".  */
+   if (*reqchar != -2)
+     {
+     if (branchreqchar >= 0)
+       {
+       if (*reqchar == -1) *reqchar = branchreqchar;
+       else if (*reqchar != branchreqchar) *reqchar = -2;
+       }
+     else *reqchar = -2;
+     }
+   /* Keep the shortest literal count */
+   if (branchcountlits < *countlits) *countlits = branchcountlits;
+   DPRINTF(("literal count = %d min=%d\n", branchcountlits, *countlits));
    /* If lookbehind, check that this branch matches a fixed-length string,
    and put the length into the OP_REVERSE item. Temporarily mark the end of
    the branch with OP_END. */
-Line 1657 
 for (;;)
+Line 2057 
 for (;;)
      code += 2;
      break;
+     case OP_WORD_BOUNDARY:
+     case OP_NOT_WORD_BOUNDARY:
+     code++;
+     break;
      case OP_ASSERT_NOT:
      case OP_ASSERTBACK:
      case OP_ASSERTBACK_NOT:
-Line 1684 
 all of whose alternatives start with OP_
+Line 2089 
 all of whose alternatives start with OP_
  it's anchored. However, if this is a multiline pattern, then only OP_SOD
  counts, since OP_CIRC can match in the middle.
- A branch is also implicitly anchored if it starts with .* because that will try
+ A branch is also implicitly anchored if it starts with .* and DOTALL is set,
- the rest of the pattern at all possible matching points, so there is no point
+ because that will try the rest of the pattern at all possible matching points,
- trying them again.
+ so there is no point trying them again.
  Arguments:
    code       points to start of expression (the bracket)
-Line 1704 
 do {
+Line 2109 
 do {
     register int op = *scode;
     if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
       { if (!is_anchored(scode, options)) return FALSE; }
-    else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR)
+    else if ((op == OP_TYPESTAR || op == OP_TYPEMINSTAR) &&
+             (*options & PCRE_DOTALL) != 0)
       { if (scode[1] != OP_ANY) return FALSE; }
     else if (op != OP_SOD &&
             ((*options & PCRE_MULTILINE) != 0 || op != OP_CIRC))
-Line 1718 
 return TRUE;
+Line 2124 
 return TRUE;
  /*************************************************
- *     Check for start with \n line expression    *
+ *         Check for starting with ^ or .*        *
  *************************************************/
- /* This is called for multiline expressions to try to find out if every branch
+ /* This is called to find out if every branch starts with ^ or .* so that
- starts with ^ so that "first char" processing can be done to speed things up.
+ "first char" processing can be done to speed things up in multiline
+ matching and for non-DOTALL patterns that start with .* (which must start at
+ the beginning or after \n).
  Argument:  points to start of expression (the bracket)
  Returns:   TRUE or FALSE
-Line 1736 
 do {
+Line 2144 
 do {
     register int op = *scode;
     if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
       { if (!is_startline(scode)) return FALSE; }
+    else if (op == OP_TYPESTAR || op == OP_TYPEMINSTAR)
+      { if (scode[1] != OP_ANY) return FALSE; }
     else if (op != OP_CIRC) return FALSE;
     code += (code[1] << 8) + code[2];
     }
-Line 1834 
 pcre_compile(const char *pattern, int op
+Line 2244 
 pcre_compile(const char *pattern, int op
  real_pcre *re;
  int length = 3;      /* For initial BRA plus length */
  int runlength;
- int c, size;
+ int c, reqchar, countlits;
  int bracount = 0;
  int top_backref = 0;
  int branch_extra = 0;
  int branch_newextra;
  unsigned int brastackptr = 0;
+ size_t size;
  uschar *code;
  const uschar *ptr;
  compile_data compile_block;
-Line 2067 
 while ((c = *(++ptr)) != 0)
+Line 2478 
 while ((c = *(++ptr)) != 0)
          ptr += 2;
          break;
+         /* A recursive call to the regex is an extension, to provide the
+         facility which can be obtained by $(?p{perl-code}) in Perl 5.6. */
+         case 'R':
+         if (ptr[3] != ')')
+           {
+           *errorptr = ERR29;
+           goto PCRE_ERROR_RETURN;
+           }
+         ptr += 3;
+         length += 1;
+         break;
          /* Lookbehinds are in Perl from version 5.005 */
          case '<':
-Line 2174 
 while ((c = *(++ptr)) != 0)
+Line 2598 
 while ((c = *(++ptr)) != 0)
              will lead to an over-estimate on the length, but this shouldn't
              matter very much. We also have to allow for resetting options at
              the start of any alternations, which we do by setting
-             branch_newextra to 2. */
+             branch_newextra to 2. Finally, we record whether the case-dependent
+             flag ever changes within the regex. This is used by the "required
+             character" code. */
              case ':':
              if (((set|unset) & PCRE_IMS) != 0)
                {
                length += 4;
                branch_newextra = 2;
+               if (((set|unset) & PCRE_CASELESS) != 0) options |= PCRE_ICHANGED;
                }
              goto END_OPTIONS;
-Line 2268 
 while ((c = *(++ptr)) != 0)
+Line 2695 
 while ((c = *(++ptr)) != 0)
        else if (c == '+') { maxval = -1; ptr++; }
        else if (c == '?') { minval = 0; ptr++; }
-       /* If there is a minimum > 1 we have to replicate up to minval-1 times;
+       /* If the minimum is zero, we have to allow for an OP_BRAZERO before the
-       if there is a limited maximum we have to replicate up to maxval-1 times
+       group, and if the maximum is greater than zero, we have to replicate
-       and allow for a BRAZERO item before each optional copy, as we also have
+       maxval-1 times; each replication acquires an OP_BRAZERO plus a nesting
-       to do before the first copy if the minimum is zero. */
+       bracket set - hence the 7. */
-       if (minval == 0) length++;
+       if (minval == 0)
-         else if (minval > 1) length += (minval - 1) * duplength;
+         {
-       if (maxval > minval) length += (maxval - minval) * (duplength + 1);
+         length++;
+         if (maxval > 0) length += (maxval - 1) * (duplength + 7);
+         }
+       /* When the minimum is greater than zero, 1 we have to replicate up to
+       minval-1 times, with no additions required in the copies. Then, if
+       there is a limited maximum we have to replicate up to maxval-1 times
+       allowing for a BRAZERO item before each optional copy and nesting
+       brackets for all but one of the optional copies. */
+       else
+         {
+         length += (minval - 1) * duplength;
+         if (maxval > minval)   /* Need this test as maxval=-1 means no limit */
+           length += (maxval - minval) * (duplength + 7) - 6;
+         }
        }
      continue;
-Line 2351 
 if (re == NULL)
+Line 2793 
 if (re == NULL)
    return NULL;
    }
- /* Put in the magic number and the options. */
+ /* Put in the magic number, and save the size, options, and table pointer */
  re->magic_number = MAGIC_NUMBER;
+ re->size = size;
  re->options = options;
  re->tables = tables;
-Line 2366 
 code = re->code;
+Line 2809 
 code = re->code;
  *code = OP_BRA;
  bracount = 0;
  (void)compile_regex(options, -1, &bracount, &code, &ptr, errorptr, FALSE, -1,
-   &compile_block);
+   &reqchar, &countlits, &compile_block);
  re->top_bracket = bracount;
  re->top_backref = top_backref;
-Line 2398 
 if (*errorptr != NULL)
+Line 2841 
 if (*errorptr != NULL)
    return NULL;
    }
- /* If the anchored option was not passed, set flag if we can determine that it
+ /* If the anchored option was not passed, set flag if we can determine that the
- is anchored by virtue of ^ characters or \A or anything else. Otherwise, see if
+ pattern is anchored by virtue of ^ characters or \A or anything else (such as
- we can determine what the first character has to be, because that speeds up
+ starting with .* when DOTALL is set).
- unanchored matches no end. In the case of multiline matches, an alternative is
- to set the PCRE_STARTLINE flag if all branches start with ^. */
+ Otherwise, see if we can determine what the first character has to be, because
+ that speeds up unanchored matches no end. If not, see if we can set the
+ PCRE_STARTLINE flag. This is helpful for multiline matches when all branches
+ start with ^. and also when all branches start with .* for non-DOTALL matches.
+ */
  if ((options & PCRE_ANCHORED) == 0)
    {
-Line 2422 
 if ((options & PCRE_ANCHORED) == 0)
+Line 2869 
 if ((options & PCRE_ANCHORED) == 0)
      }
    }
+ /* Save the last required character if there are at least two literal
+ characters on all paths, or if there is no first character setting. */
+ if (reqchar >= 0 && (countlits > 1 || (re->options & PCRE_FIRSTSET) == 0))
+   {
+   re->req_char = reqchar;
+   re->options |= PCRE_REQCHSET;
+   }
  /* Print out the compiled data for debugging */
  #ifdef DEBUG
-Line 2431 
 printf("Length = %d top_bracket = %d top
+Line 2887 
 printf("Length = %d top_bracket = %d top
  if (re->options != 0)
    {
-   printf("%s%s%s%s%s%s%s%s\n",
+   printf("%s%s%s%s%s%s%s%s%s\n",
      ((re->options & PCRE_ANCHORED) != 0)? "anchored " : "",
      ((re->options & PCRE_CASELESS) != 0)? "caseless " : "",
+     ((re->options & PCRE_ICHANGED) != 0)? "case state changed " : "",
      ((re->options & PCRE_EXTENDED) != 0)? "extended " : "",
      ((re->options & PCRE_MULTILINE) != 0)? "multiline " : "",
      ((re->options & PCRE_DOTALL) != 0)? "dotall " : "",
-Line 2448 
 if ((re->options & PCRE_FIRSTSET) != 0)
+Line 2905 
 if ((re->options & PCRE_FIRSTSET) != 0)
      else printf("First char = \\x%02x\n", re->first_char);
    }
+ if ((re->options & PCRE_REQCHSET) != 0)
+   {
+   if (isprint(re->req_char)) printf("Req char = %c\n", re->req_char);
+     else printf("Req char = \\x%02x\n", re->req_char);
+   }
  code_end = code;
  code_base = code = re->code;
-Line 2681 
 Returns:      TRUE if matched
+Line 3144 
 Returns:      TRUE if matched
  static BOOL
  match_ref(int offset, register const uschar *eptr, int length, match_data *md,
-   int ims)
+   unsigned long int ims)
  {
  const uschar *p = md->start_subject + md->offset_vector[offset];
-Line 2740 
 Returns:       TRUE if matched
+Line 3203 
 Returns:       TRUE if matched
  static BOOL
  match(register const uschar *eptr, register const uschar *ecode,
-   int offset_top, match_data *md, int ims, BOOL condassert, const uschar *eptrb)
+   int offset_top, match_data *md, unsigned long int ims, BOOL condassert,
+   const uschar *eptrb)
  {
- int original_ims = ims;   /* Save for resetting on ')' */
+ unsigned long int original_ims = ims;   /* Save for resetting on ')' */
  for (;;)
    {
-Line 2771 
 for (;;)
+Line 3235 
 for (;;)
      int number = op - OP_BRA;
      int offset = number << 1;
-     DPRINTF(("start bracket %d\n", number));
+ #ifdef DEBUG
+     printf("start bracket %d subject=", number);
+     pchars(eptr, 16, TRUE, md);
+     printf("\n");
+ #endif
      if (offset < md->offset_max)
        {
-Line 2853 
 for (;;)
+Line 3321 
 for (;;)
      ecode += 2;
      break;
-     /* End of the pattern */
+     /* End of the pattern. If PCRE_NOTEMPTY is set, fail if we have matched
+     an empty string - recursion will then try other alternatives, if any. */
      case OP_END:
+     if (md->notempty && eptr == md->start_match) return FALSE;
      md->end_match_ptr = eptr;          /* Record where we ended */
      md->end_offset_top = offset_top;   /* and how many extracts were taken */
      return TRUE;
-Line 2865 
 for (;;)
+Line 3335 
 for (;;)
      case OP_OPT:
      ims = ecode[1];
      ecode += 2;
-     DPRINTF(("ims set to %02x\n", ims));
+     DPRINTF(("ims set to %02lx\n", ims));
      break;
      /* Assertion brackets. Check the alternative branches in turn - the
-Line 2921 
 for (;;)
+Line 3391 
 for (;;)
      ecode += 3;
      break;
+     /* Recursion matches the current regex, nested. If there are any capturing
+     brackets started but not finished, we have to save their starting points
+     and reinstate them after the recursion. However, we don't know how many
+     such there are (offset_top records the completed total) so we just have
+     to save all the potential data. There may be up to 99 such values, which
+     is a bit large to put on the stack, but using malloc for small numbers
+     seems expensive. As a compromise, the stack is used when there are fewer
+     than 16 values to store; otherwise malloc is used. A problem is what to do
+     if the malloc fails ... there is no way of returning to the top level with
+     an error. Save the top 15 values on the stack, and accept that the rest
+     may be wrong. */
+     case OP_RECURSE:
+       {
+       BOOL rc;
+       int *save;
+       int stacksave[15];
+       c = md->offset_max;
+       if (c < 16) save = stacksave; else
+         {
+         save = (int *)(pcre_malloc)((c+1) * sizeof(int));
+         if (save == NULL)
+           {
+           save = stacksave;
+           c = 15;
+           }
+         }
+       for (i = 1; i <= c; i++)
+         save[i] = md->offset_vector[md->offset_end - i];
+       rc = match(eptr, md->start_pattern, offset_top, md, ims, FALSE, eptrb);
+       for (i = 1; i <= c; i++)
+         md->offset_vector[md->offset_end - i] = save[i];
+       if (save != stacksave) (pcre_free)(save);
+       if (!rc) return FALSE;
+       /* In case the recursion has set more capturing values, save the final
+       number, then move along the subject till after the recursive match,
+       and advance one byte in the pattern code. */
+       offset_top = md->end_offset_top;
+       eptr = md->end_match_ptr;
+       ecode++;
+       }
+     break;
      /* "Once" brackets are like assertion brackets except that after a match,
      the point in the subject string is not moved back. Thus there can never be
-Line 2972 
 for (;;)
+Line 3489 
 for (;;)
        if (ecode[3] == OP_OPT)
          {
          ims = (ims & ~PCRE_IMS) | ecode[4];
-         DPRINTF(("ims set to %02x at group repeat\n", ims));
+         DPRINTF(("ims set to %02lx at group repeat\n", ims));
          }
        if (*ecode == OP_KETRMIN)
-Line 3066 
 for (;;)
+Line 3583 
 for (;;)
        the group. */
        ims = original_ims;
-       DPRINTF(("ims reset to %02x\n", ims));
+       DPRINTF(("ims reset to %02lx\n", ims));
        /* 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.
-Line 3952 
 Arguments:
+Line 4469 
 Arguments:
    external_extra  points to "hints" from pcre_study() or is NULL
    subject         points to the subject string
    length          length of subject string (may contain binary zeros)
+   start_offset    where to start in the subject string
    options         option bits
    offsets         points to a vector of ints to be filled in with offsets
    offsetcount     the number of elements in the vector
-Line 3964 
 Returns:          > 0 => success; value
+Line 4482 
 Returns:          > 0 => success; value
  int
  pcre_exec(const pcre *external_re, const pcre_extra *external_extra,
-   const char *subject, int length, int options, int *offsets, int offsetcount)
+   const char *subject, int length, int start_offset, int options, int *offsets,
+   int offsetcount)
  {
  int resetcount, ocount;
  int first_char = -1;
- int ims = 0;
+ int req_char = -1;
+ int req_char2 = -1;
+ unsigned long int ims = 0;
  match_data match_block;
  const uschar *start_bits = NULL;
- const uschar *start_match = (const uschar *)subject;
+ const uschar *start_match = (const uschar *)subject + start_offset;
  const uschar *end_subject;
+ const uschar *req_char_ptr = start_match - 1;
  const real_pcre *re = (const real_pcre *)external_re;
  const real_pcre_extra *extra = (const real_pcre_extra *)external_extra;
  BOOL using_temporary_offsets = FALSE;
-Line 3985 
 if (re == NULL || subject == NULL ||
+Line 4507 
 if (re == NULL || subject == NULL ||
     (offsets == NULL && offsetcount > 0)) return PCRE_ERROR_NULL;
  if (re->magic_number != MAGIC_NUMBER) return PCRE_ERROR_BADMAGIC;
+ match_block.start_pattern = re->code;
  match_block.start_subject = (const uschar *)subject;
  match_block.end_subject = match_block.start_subject + length;
  end_subject = match_block.end_subject;
-Line 3993 
 match_block.endonly = (re->options & PCR
+Line 4516 
 match_block.endonly = (re->options & PCR
  match_block.notbol = (options & PCRE_NOTBOL) != 0;
  match_block.noteol = (options & PCRE_NOTEOL) != 0;
+ match_block.notempty = (options & PCRE_NOTEMPTY) != 0;
  match_block.errorcode = PCRE_ERROR_NOMATCH;     /* Default error */
-Line 4063 
 if (!anchored)
+Line 4587 
 if (!anchored)
          start_bits = extra->start_bits;
    }
- /* Loop for unanchored matches; for anchored regexps the loop runs just once. */
+ /* For anchored or unanchored matches, there may be a "last known required
+ character" set. If the PCRE_CASELESS is set, implying that the match starts
+ caselessly, or if there are any changes of this flag within the regex, set up
+ both cases of the character. Otherwise set the two values the same, which will
+ avoid duplicate testing (which takes significant time). This covers the vast
+ majority of cases. It will be suboptimal when the case flag changes in a regex
+ and the required character in fact is caseful. */
+ if ((re->options & PCRE_REQCHSET) != 0)
+   {
+   req_char = re->req_char;
+   req_char2 = ((re->options & (PCRE_CASELESS | PCRE_ICHANGED)) != 0)?
+     (re->tables + fcc_offset)[req_char] : req_char;
+   }
+ /* Loop for handling unanchored repeated matching attempts; for anchored regexs
+ the loop runs just once. */
  do
    {
-Line 4092 
 do
+Line 4632 
 do
    else if (startline)
      {
-     if (start_match > match_block.start_subject)
+     if (start_match > match_block.start_subject + start_offset)
        {
        while (start_match < end_subject && start_match[-1] != '\n')
          start_match++;
        }
      }
-   /* Or to a non-unique first char */
+   /* Or to a non-unique first char after study */
    else if (start_bits != NULL)
      {
-Line 4116 
 do
+Line 4656 
 do
    printf("\n");
  #endif
+   /* If req_char is set, we know that that character must appear in the subject
+   for the match to succeed. If the first character is set, req_char must be
+   later in the subject; otherwise the test starts at the match point. This
+   optimization can save a huge amount of backtracking in patterns with nested
+   unlimited repeats that aren't going to match. We don't know what the state of
+   case matching may be when this character is hit, so test for it in both its
+   cases if necessary. However, the different cased versions will not be set up
+   unless PCRE_CASELESS was given or the casing state changes within the regex.
+   Writing separate code makes it go faster, as does using an autoincrement and
+   backing off on a match. */
+   if (req_char >= 0)
+     {
+     register const uschar *p = start_match + ((first_char >= 0)? 1 : 0);
+     /* We don't need to repeat the search if we haven't yet reached the
+     place we found it at last time. */
+     if (p > req_char_ptr)
+       {
+       /* Do a single test if no case difference is set up */
+       if (req_char == req_char2)
+         {
+         while (p < end_subject)
+           {
+           if (*p++ == req_char) { p--; break; }
+           }
+         }
+       /* Otherwise test for either case */
+       else
+         {
+         while (p < end_subject)
+           {
+           register int pp = *p++;
+           if (pp == req_char || pp == req_char2) { p--; break; }
+           }
+         }
+       /* If we can't find the required character, break the matching loop */
+       if (p >= end_subject) break;
+       /* If we have found the required character, save the point where we
+       found it, so that we don't search again next time round the loop if
+       the start hasn't passed this character yet. */
+       req_char_ptr = p;
+       }
+     }
    /* When a match occurs, substrings will be set for all internal extractions;
    we just need to set up the whole thing as substring 0 before returning. If
    there were too many extractions, set the return code to zero. In the case
-Line 4123 
 do
+Line 4716 
 do
    those back references that we can. In this case there need not be overflow
    if certain parts of the pattern were not used. */
+   match_block.start_match = start_match;
    if (!match(start_match, re->code, 2, &match_block, ims, FALSE, start_match))
      continue;

 Legend:



Removed from v.27
 


changed lines


 
Added in v.43
 Legend:



Removed from v.27
 


changed lines


 
Added in v.43
-Removed from v.27
+Added in v.43

	ViewVC Help
Powered by ViewVC 1.1.5