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

Diff of /code/trunk/pcre_dfa_exec.c

Parent Directory | Revision Log | View Patch Patch

-revision 406 by ph10,
Mon Mar 23 12:05:43 2009 UTC
+revision 459 by ph10,
Sun Oct  4 09:21:39 2009 UTC
 Line 45 
 FSM). This is NOT Perl- compatible, but
  applications. */
+ /* NOTE ABOUT PERFORMANCE: A user of this function sent some code that improved
+ the performance of his patterns greatly. I could not use it as it stood, as it
+ was not thread safe, and made assumptions about pattern sizes. Also, it caused
+ test 7 to loop, and test 9 to crash with a segfault.
+ The issue is the check for duplicate states, which is done by a simple linear
+ search up the state list. (Grep for "duplicate" below to find the code.) For
+ many patterns, there will never be many states active at one time, so a simple
+ linear search is fine. In patterns that have many active states, it might be a
+ bottleneck. The suggested code used an indexing scheme to remember which states
+ had previously been used for each character, and avoided the linear search when
+ it knew there was no chance of a duplicate. This was implemented when adding
+ states to the state lists.
+ I wrote some thread-safe, not-limited code to try something similar at the time
+ of checking for duplicates (instead of when adding states), using index vectors
+ on the stack. It did give a 13% improvement with one specially constructed
+ pattern for certain subject strings, but on other strings and on many of the
+ simpler patterns in the test suite it did worse. The major problem, I think,
+ was the extra time to initialize the index. This had to be done for each call
+ of internal_dfa_exec(). (The supplied patch used a static vector, initialized
+ only once - I suspect this was the cause of the problems with the tests.)
+ Overall, I concluded that the gains in some cases did not outweigh the losses
+ in others, so I abandoned this code. */
  #ifdef HAVE_CONFIG_H
  #include "config.h"
  #endif
-Line 389 
 if (*first_op == OP_REVERSE)
+Line 417 
 if (*first_op == OP_REVERSE)
        current_subject - start_subject : max_back;
      current_subject -= gone_back;
      }
+   /* Save the earliest consulted character */
+   if (current_subject < md->start_used_ptr)
+     md->start_used_ptr = current_subject;
    /* Now we can process the individual branches. */
-Line 454 
 for (;;)
+Line 487 
 for (;;)
    int i, j;
    int clen, dlen;
    unsigned int c, d;
+   int forced_fail = 0;
+   int reached_end = 0;
    /* Make the new state list into the active state list and empty the
    new state list. */
-Line 543 
 for (;;)
+Line 578 
 for (;;)
          }
        }
-     /* Check for a duplicate state with the same count, and skip if found. */
+     /* Check for a duplicate state with the same count, and skip if found.
+     See the note at the head of this module about the possibility of improving
+     performance here. */
      for (j = 0; j < i; j++)
        {
-Line 610 
 for (;;)
+Line 647 
 for (;;)
  /* ========================================================================== */
        /* Reached a closing bracket. If not at the end of the pattern, carry
        on with the next opcode. Otherwise, unless we have an empty string and
-       PCRE_NOTEMPTY is set, save the match data, shifting up all previous
+       PCRE_NOTEMPTY is set, or PCRE_NOTEMPTY_ATSTART is set and we are at the
+       start of the subject, save the match data, shifting up all previous
        matches so we always have the longest first. */
        case OP_KET:
-Line 624 
 for (;;)
+Line 662 
 for (;;)
            ADD_ACTIVE(state_offset - GET(code, 1), 0);
            }
          }
-       else if (ptr > current_subject || (md->moptions & PCRE_NOTEMPTY) == 0)
+       else
          {
-         if (match_count < 0) match_count = (offsetcount >= 2)? 1 : 0;
+         reached_end++;    /* Count branches that reach the end */
-           else if (match_count > 0 && ++match_count * 2 >= offsetcount)
+         if (ptr > current_subject ||
-             match_count = 0;
+             ((md->moptions & PCRE_NOTEMPTY) == 0 &&
-         count = ((match_count == 0)? offsetcount : match_count * 2) - 2;
+               ((md->moptions & PCRE_NOTEMPTY_ATSTART) == 0 ||
-         if (count > 0) memmove(offsets + 2, offsets, count * sizeof(int));
+                 current_subject > start_subject + md->start_offset)))
-         if (offsetcount >= 2)
+           {
-           {
+           if (match_count < 0) match_count = (offsetcount >= 2)? 1 : 0;
-           offsets[0] = current_subject - start_subject;
+             else if (match_count > 0 && ++match_count * 2 >= offsetcount)
-           offsets[1] = ptr - start_subject;
+               match_count = 0;
-           DPRINTF(("%.*sSet matched string = \"%.*s\"\n", rlevel*2-2, SP,
+           count = ((match_count == 0)? offsetcount : match_count * 2) - 2;
-             offsets[1] - offsets[0], current_subject));
+           if (count > 0) memmove(offsets + 2, offsets, count * sizeof(int));
-           }
+           if (offsetcount >= 2)
-         if ((md->moptions & PCRE_DFA_SHORTEST) != 0)
+             {
-           {
+             offsets[0] = current_subject - start_subject;
-           DPRINTF(("%.*sEnd of internal_dfa_exec %d: returning %d\n"
+             offsets[1] = ptr - start_subject;
-             "%.*s---------------------\n\n", rlevel*2-2, SP, rlevel,
+             DPRINTF(("%.*sSet matched string = \"%.*s\"\n", rlevel*2-2, SP,
-             match_count, rlevel*2-2, SP));
+               offsets[1] - offsets[0], current_subject));
-           return match_count;
+             }
-           }
+           if ((md->moptions & PCRE_DFA_SHORTEST) != 0)
+             {
+             DPRINTF(("%.*sEnd of internal_dfa_exec %d: returning %d\n"
+               "%.*s---------------------\n\n", rlevel*2-2, SP, rlevel,
+               match_count, rlevel*2-2, SP));
+             return match_count;
+             }
+           }
          }
        break;
-Line 794 
 for (;;)
+Line 839 
 for (;;)
          if (ptr > start_subject)
            {
            const uschar *temp = ptr - 1;
+           if (temp < md->start_used_ptr) md->start_used_ptr = temp;
  #ifdef SUPPORT_UTF8
            if (utf8) BACKCHAR(temp);
  #endif
-Line 802 
 for (;;)
+Line 848 
 for (;;)
            }
          else left_word = 0;
-         if (clen > 0) right_word = c < 256 && (ctypes[c] & ctype_word) != 0;
+         if (clen > 0)
-           else right_word = 0;
+           right_word = c < 256 && (ctypes[c] & ctype_word) != 0;
+         else              /* This is a fudge to ensure that if this is the */
+           {               /* last item in the pattern, we don't count it as */
+           reached_end--;  /* reached, thus disabling a partial match. */
+           right_word = 0;
+           }
          if ((left_word == right_word) == (codevalue == OP_NOT_WORD_BOUNDARY))
            { ADD_ACTIVE(state_offset + 1, 0); }
-Line 2157 
 for (;;)
+Line 2208 
 for (;;)
  /* ========================================================================== */
        /* These are the opcodes for fancy brackets of various kinds. We have
-       to use recursion in order to handle them. The "always failing" assersion
+       to use recursion in order to handle them. The "always failing" assertion
-       (?!) is optimised when compiling to OP_FAIL, so we have to support that,
+       (?!) is optimised to OP_FAIL when compiling, so we have to support that,
        though the other "backtracking verbs" are not supported. */
        case OP_FAIL:
+       forced_fail++;    /* Count FAILs for multiple states */
        break;
        case OP_ASSERT:
-Line 2235 
 for (;;)
+Line 2287 
 for (;;)
          /* Back reference conditions are not supported */
-         if (condcode == OP_CREF) return PCRE_ERROR_DFA_UCOND;
+         if (condcode == OP_CREF || condcode == OP_NCREF)
+           return PCRE_ERROR_DFA_UCOND;
          /* The DEFINE condition is always false */
-Line 2246 
 for (;;)
+Line 2299 
 for (;;)
          which means "test if in any recursion". We can't test for specifically
          recursed groups. */
-         else if (condcode == OP_RREF)
+         else if (condcode == OP_RREF || condcode == OP_NRREF)
            {
            int value = GET2(code, LINK_SIZE+2);
            if (value != RREF_ANY) return PCRE_ERROR_DFA_UCOND;
-Line 2469 
 for (;;)
+Line 2522 
 for (;;)
    /* We have finished the processing at the current subject character. If no
    new states have been set for the next character, we have found all the
    matches that we are going to find. If we are at the top level and partial
-   matching has been requested, check for appropriate conditions. */
+   matching has been requested, check for appropriate conditions. The "forced_
+   fail" variable counts the number of (*F) encountered for the character. If it
+   is equal to the original active_count (saved in workspace[1]) it means that
+   (*F) was found on every active state. In this case we don't want to give a
+   partial match. */
    if (new_count <= 0)
      {
-     if (match_count < 0 &&                     /* No matches found */
+     if (rlevel == 1 &&                               /* Top level, and */
-         rlevel == 1 &&                         /* Top level match function */
+         reached_end != workspace[1] &&               /* Not all reached end */
-         (md->moptions & PCRE_PARTIAL) != 0 &&  /* Want partial matching */
+         forced_fail != workspace[1] &&               /* Not all forced fail & */
-         ptr >= end_subject &&                  /* Reached end of subject */
+         (                                            /* either... */
-         ptr > current_subject)                 /* Matched non-empty string */
+         (md->moptions & PCRE_PARTIAL_HARD) != 0      /* Hard partial */
+         ||                                           /* or... */
+         ((md->moptions & PCRE_PARTIAL_SOFT) != 0 &&  /* Soft partial and */
+          match_count < 0)                            /* no matches */
+         ) &&                                         /* And... */
+         ptr >= end_subject &&                     /* Reached end of subject */
+         ptr > current_subject)                    /* Matched non-empty string */
        {
        if (offsetcount >= 2)
          {
-         offsets[0] = current_subject - start_subject;
+         offsets[0] = md->start_used_ptr - start_subject;
          offsets[1] = end_subject - start_subject;
          }
        match_count = PCRE_ERROR_PARTIAL;
-Line 2589 
 if (extra_data != NULL)
+Line 2652 
 if (extra_data != NULL)
    if ((flags & PCRE_EXTRA_TABLES) != 0)
      md->tables = extra_data->tables;
    }
  /* Check that the first field in the block is the magic number. If it is not,
  test for a regex that was compiled on a host of opposite endianness. If this is
  the case, flipped values are put in internal_re and internal_study if there was
-Line 2623 
 md->start_code = (const uschar *)argumen
+Line 2686 
 md->start_code = (const uschar *)argumen
      re->name_table_offset + re->name_count * re->name_entry_size;
  md->start_subject = (const unsigned char *)subject;
  md->end_subject = end_subject;
+ md->start_offset = start_offset;
  md->moptions = options;
  md->poptions = re->options;
-Line 2727 
 if (!anchored)
+Line 2791 
 if (!anchored)
      }
    else
      {
-     if (startline && study != NULL &&
+     if (!startline && study != NULL &&
-          (study->options & PCRE_STUDY_MAPPED) != 0)
+          (study->flags & PCRE_STUDY_MAPPED) != 0)
        start_bits = study->start_bits;
      }
    }
-Line 2779 
 for (;;)
+Line 2843 
 for (;;)
        }
      /* There are some optimizations that avoid running the match if a known
-     starting point is not found, or if a known later character is not present.
+     starting point is not found. However, there is an option that disables
-     However, there is an option that disables these, for testing and for
+     these, for testing and for ensuring that all callouts do actually occur. */
-     ensuring that all callouts do actually occur. */
      if ((options & PCRE_NO_START_OPTIMIZE) == 0)
        {
        /* Advance to a known first byte. */
        if (first_byte >= 0)
-Line 2851 
 for (;;)
+Line 2913 
 for (;;)
      /* Restore fudged end_subject */
      end_subject = save_end_subject;
-     }
-   /* If req_byte is set, we know that that character must appear in the subject
+     /* The following two optimizations are disabled for partial matching or if
-   for the match to succeed. If the first character is set, req_byte must be
+     disabling is explicitly requested (and of course, by the test above, this
-   later in the subject; otherwise the test starts at the match point. This
+     code is not obeyed when restarting after a partial match). */
-   optimization can save a huge amount of work in patterns with nested unlimited
-   repeats that aren't going to match. Writing separate code for cased/caseless
+     if ((options & PCRE_NO_START_OPTIMIZE) == 0 &&
-   versions makes it go faster, as does using an autoincrement and backing off
+         (options & (PCRE_PARTIAL_HARD|PCRE_PARTIAL_SOFT)) == 0)
-   on a match.
+       {
+       /* If the pattern was studied, a minimum subject length may be set. This
-   HOWEVER: when the subject string is very, very long, searching to its end can
+       is a lower bound; no actual string of that length may actually match the
-   take a long time, and give bad performance on quite ordinary patterns. This
+       pattern. Although the value is, strictly, in characters, we treat it as
-   showed up when somebody was matching /^C/ on a 32-megabyte string... so we
+       bytes to avoid spending too much time in this optimization. */
-   don't do this when the string is sufficiently long.
+       if (study != NULL && (study->flags & PCRE_STUDY_MINLEN) != 0 &&
-   ALSO: this processing is disabled when partial matching is requested, and can
+           end_subject - current_subject < study->minlength)
-   also be explicitly deactivated. */
+         return PCRE_ERROR_NOMATCH;
-   if ((options & PCRE_NO_START_OPTIMIZE) == 0 &&
+       /* If req_byte is set, we know that that character must appear in the
-       req_byte >= 0 &&
+       subject for the match to succeed. If the first character is set, req_byte
-       end_subject - current_subject < REQ_BYTE_MAX &&
+       must be later in the subject; otherwise the test starts at the match
-       (options & PCRE_PARTIAL) == 0)
+       point. This optimization can save a huge amount of work in patterns with
-     {
+       nested unlimited repeats that aren't going to match. Writing separate
-     register const uschar *p = current_subject + ((first_byte >= 0)? 1 : 0);
+       code for cased/caseless versions makes it go faster, as does using an
+       autoincrement and backing off on a match.
-     /* We don't need to repeat the search if we haven't yet reached the
-     place we found it at last time. */
+       HOWEVER: when the subject string is very, very long, searching to its end
+       can take a long time, and give bad performance on quite ordinary
-     if (p > req_byte_ptr)
+       patterns. This showed up when somebody was matching /^C/ on a 32-megabyte
-       {
+       string... so we don't do this when the string is sufficiently long. */
-       if (req_byte_caseless)
-         {
+       if (req_byte >= 0 && end_subject - current_subject < REQ_BYTE_MAX)
-         while (p < end_subject)
+         {
-           {
+         register const uschar *p = current_subject + ((first_byte >= 0)? 1 : 0);
-           register int pp = *p++;
-           if (pp == req_byte || pp == req_byte2) { p--; break; }
+         /* We don't need to repeat the search if we haven't yet reached the
-           }
+         place we found it at last time. */
-         }
-       else
+         if (p > req_byte_ptr)
-         {
-         while (p < end_subject)
            {
-           if (*p++ == req_byte) { p--; break; }
+           if (req_byte_caseless)
+             {
+             while (p < end_subject)
+               {
+               register int pp = *p++;
+               if (pp == req_byte || pp == req_byte2) { p--; break; }
+               }
+             }
+           else
+             {
+             while (p < end_subject)
+               {
+               if (*p++ == req_byte) { p--; break; }
+               }
+             }
+           /* If we can't find the required character, break the matching loop,
+           which will cause a return or PCRE_ERROR_NOMATCH. */
+           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_byte_ptr = p;
            }
          }
-       /* If we can't find the required character, break the matching loop,
-       which will cause a return or PCRE_ERROR_NOMATCH. */
-       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_byte_ptr = p;
        }
-     }
+     }   /* End of optimizations that are done when not restarting */
    /* OK, now we can do the business */
+   md->start_used_ptr = current_subject;
    rc = internal_dfa_exec(
      md,                                /* fixed match data */
      md->start_code,                    /* this subexpression's code */

 Legend:



Removed from v.406
 


changed lines


 
Added in v.459
 Legend:



Removed from v.406
 


changed lines


 
Added in v.459
-Removed from v.406
+Added in v.459

webmaster@exim.org	ViewVC Help
Powered by ViewVC 1.1.12