code/trunk/pcre_study.c

/*************************************************
*      Perl-Compatible Regular Expressions       *
*************************************************/

/* PCRE is a library of functions to support regular expressions whose syntax
and semantics are as close as possible to those of the Perl 5 language.

                       Written by Philip Hazel
           Copyright (c) 1997-2007 University of Cambridge

-----------------------------------------------------------------------------
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:

    * Redistributions of source code must retain the above copyright notice,
      this list of conditions and the following disclaimer.

    * Redistributions in binary form must reproduce the above copyright
      notice, this list of conditions and the following disclaimer in the
      documentation and/or other materials provided with the distribution.

    * Neither the name of the University of Cambridge nor the names of its
      contributors may be used to endorse or promote products derived from
      this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
POSSIBILITY OF SUCH DAMAGE.
-----------------------------------------------------------------------------
*/


/* This module contains the external function pcre_study(), along with local
supporting functions. */


#ifdef HAVE_CONFIG_H                         
#include <config.h>
#endif                                                               

#include "pcre_internal.h"


/* Returns from set_start_bits() */

enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };


/*************************************************
*      Set a bit and maybe its alternate case    *
*************************************************/

/* Given a character, set its bit in the table, and also the bit for the other
version of a letter if we are caseless.

Arguments:
  start_bits    points to the bit map
  c             is the character
  caseless      the caseless flag
  cd            the block with char table pointers

Returns:        nothing
*/

static void
set_bit(uschar *start_bits, unsigned int c, BOOL caseless, compile_data *cd)
{
start_bits[c/8] |= (1 << (c&7));
if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
  start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
}


/*************************************************
*          Create bitmap of starting bytes       *
*************************************************/

/* This function scans a compiled unanchored expression recursively and
attempts to build a bitmap of the set of possible starting bytes. As time goes
by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
useful for parenthesized groups in patterns such as (a*)b where the group
provides some optional starting bytes but scanning must continue at the outer
level to find at least one mandatory byte. At the outermost level, this
function fails unless the result is SSB_DONE.

Arguments:
  code         points to an expression
  start_bits   points to a 32-byte table, initialized to 0
  caseless     the current state of the caseless flag
  utf8         TRUE if in UTF-8 mode
  cd           the block with char table pointers

Returns:       SSB_FAIL     => Failed to find any starting bytes
               SSB_DONE     => Found mandatory starting bytes
               SSB_CONTINUE => Found optional starting bytes
*/

static int
set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
  BOOL utf8, compile_data *cd)
{
register int c;
int yield = SSB_DONE;

#if 0
/* ========================================================================= */
/* The following comment and code was inserted in January 1999. In May 2006,
when it was observed to cause compiler warnings about unused values, I took it
out again. If anybody is still using OS/2, they will have to put it back
manually. */

/* This next statement and the later reference to dummy are here in order to
trick the optimizer of the IBM C compiler for OS/2 into generating correct
code. Apparently IBM isn't going to fix the problem, and we would rather not
disable optimization (in this module it actually makes a big difference, and
the pcre module can use all the optimization it can get). */

volatile int dummy;
/* ========================================================================= */
#endif

do
  {
  const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
  BOOL try_next = TRUE;

  while (try_next)    /* Loop for items in this branch */
    {
    int rc;
    switch(*tcode)
      {
      /* Fail if we reach something we don't understand */

      default:
      return SSB_FAIL;

      /* If we hit a bracket or a positive lookahead assertion, recurse to set
      bits from within the subpattern. If it can't find anything, we have to
      give up. If it finds some mandatory character(s), we are done for this
      branch. Otherwise, carry on scanning after the subpattern. */

      case OP_BRA:
      case OP_SBRA:
      case OP_CBRA:
      case OP_SCBRA:
      case OP_ONCE:
      case OP_ASSERT:
      rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
      if (rc == SSB_FAIL) return SSB_FAIL;
      if (rc == SSB_DONE) try_next = FALSE; else
        {
        do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
        tcode += 1 + LINK_SIZE;
        }
      break;

      /* If we hit ALT or KET, it means we haven't found anything mandatory in
      this branch, though we might have found something optional. For ALT, we
      continue with the next alternative, but we have to arrange that the final
      result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
      return SSB_CONTINUE: if this is the top level, that indicates failure,
      but after a nested subpattern, it causes scanning to continue. */

      case OP_ALT:
      yield = SSB_CONTINUE;
      try_next = FALSE;
      break;

      case OP_KET:
      case OP_KETRMAX:
      case OP_KETRMIN:
      return SSB_CONTINUE;

      /* Skip over callout */

      case OP_CALLOUT:
      tcode += 2 + 2*LINK_SIZE;
      break;

      /* Skip over lookbehind and negative lookahead assertions */

      case OP_ASSERT_NOT:
      case OP_ASSERTBACK:
      case OP_ASSERTBACK_NOT:
      do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
      tcode += 1 + LINK_SIZE;
      break;

      /* Skip over an option setting, changing the caseless flag */

      case OP_OPT:
      caseless = (tcode[1] & PCRE_CASELESS) != 0;
      tcode += 2;
      break;

      /* BRAZERO does the bracket, but carries on. */

      case OP_BRAZERO:
      case OP_BRAMINZERO:
      if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
        return SSB_FAIL;
/* =========================================================================
      See the comment at the head of this function concerning the next line,
      which was an old fudge for the benefit of OS/2.
      dummy = 1;
  ========================================================================= */
      do tcode += GET(tcode,1); while (*tcode == OP_ALT);
      tcode += 1 + LINK_SIZE;
      break;

      /* Single-char * or ? sets the bit and tries the next item */

      case OP_STAR:
      case OP_MINSTAR:
      case OP_POSSTAR:
      case OP_QUERY:
      case OP_MINQUERY:
      case OP_POSQUERY:
      set_bit(start_bits, tcode[1], caseless, cd);
      tcode += 2;
#ifdef SUPPORT_UTF8
      if (utf8 && tcode[-1] >= 0xc0)
        tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
#endif
      break;

      /* Single-char upto sets the bit and tries the next */

      case OP_UPTO:
      case OP_MINUPTO:
      case OP_POSUPTO:
      set_bit(start_bits, tcode[3], caseless, cd);
      tcode += 4;
#ifdef SUPPORT_UTF8
      if (utf8 && tcode[-1] >= 0xc0)
        tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
#endif
      break;

      /* At least one single char sets the bit and stops */

      case OP_EXACT:       /* Fall through */
      tcode += 2;

      case OP_CHAR:
      case OP_CHARNC:
      case OP_PLUS:
      case OP_MINPLUS:
      case OP_POSPLUS:
      set_bit(start_bits, tcode[1], caseless, cd);
      try_next = FALSE;
      break;

      /* Single character type sets the bits and stops */

      case OP_NOT_DIGIT:
      for (c = 0; c < 32; c++)
        start_bits[c] |= ~cd->cbits[c+cbit_digit];
      try_next = FALSE;
      break;

      case OP_DIGIT:
      for (c = 0; c < 32; c++)
        start_bits[c] |= cd->cbits[c+cbit_digit];
      try_next = FALSE;
      break;

      /* The cbit_space table has vertical tab as whitespace; we have to
      discard it. */

      case OP_NOT_WHITESPACE:
      for (c = 0; c < 32; c++)
        {
        int d = cd->cbits[c+cbit_space];
        if (c == 1) d &= ~0x08;
        start_bits[c] |= ~d;
        }
      try_next = FALSE;
      break;

      /* The cbit_space table has vertical tab as whitespace; we have to
      discard it. */

      case OP_WHITESPACE:
      for (c = 0; c < 32; c++)
        {
        int d = cd->cbits[c+cbit_space];
        if (c == 1) d &= ~0x08;
        start_bits[c] |= d;
        }
      try_next = FALSE;
      break;

      case OP_NOT_WORDCHAR:
      for (c = 0; c < 32; c++)
        start_bits[c] |= ~cd->cbits[c+cbit_word];
      try_next = FALSE;
      break;

      case OP_WORDCHAR:
      for (c = 0; c < 32; c++)
        start_bits[c] |= cd->cbits[c+cbit_word];
      try_next = FALSE;
      break;

      /* One or more character type fudges the pointer and restarts, knowing
      it will hit a single character type and stop there. */

      case OP_TYPEPLUS:
      case OP_TYPEMINPLUS:
      tcode++;
      break;

      case OP_TYPEEXACT:
      tcode += 3;
      break;

      /* Zero or more repeats of character types set the bits and then
      try again. */

      case OP_TYPEUPTO:
      case OP_TYPEMINUPTO:
      case OP_TYPEPOSUPTO:
      tcode += 2;               /* Fall through */

      case OP_TYPESTAR:
      case OP_TYPEMINSTAR:
      case OP_TYPEPOSSTAR:
      case OP_TYPEQUERY:
      case OP_TYPEMINQUERY:
      case OP_TYPEPOSQUERY:
      switch(tcode[1])
        {
        case OP_ANY:
        return SSB_FAIL;

        case OP_NOT_DIGIT:
        for (c = 0; c < 32; c++)
          start_bits[c] |= ~cd->cbits[c+cbit_digit];
        break;

        case OP_DIGIT:
        for (c = 0; c < 32; c++)
          start_bits[c] |= cd->cbits[c+cbit_digit];
        break;

        /* The cbit_space table has vertical tab as whitespace; we have to
        discard it. */

        case OP_NOT_WHITESPACE:
        for (c = 0; c < 32; c++)
          {
          int d = cd->cbits[c+cbit_space];
          if (c == 1) d &= ~0x08;
          start_bits[c] |= ~d;
          }
        break;

        /* The cbit_space table has vertical tab as whitespace; we have to
        discard it. */

        case OP_WHITESPACE:
        for (c = 0; c < 32; c++)
          {
          int d = cd->cbits[c+cbit_space];
          if (c == 1) d &= ~0x08;
          start_bits[c] |= d;
          }
        break;

        case OP_NOT_WORDCHAR:
        for (c = 0; c < 32; c++)
          start_bits[c] |= ~cd->cbits[c+cbit_word];
        break;

        case OP_WORDCHAR:
        for (c = 0; c < 32; c++)
          start_bits[c] |= cd->cbits[c+cbit_word];
        break;
        }

      tcode += 2;
      break;

      /* Character class where all the information is in a bit map: set the
      bits and either carry on or not, according to the repeat count. If it was
      a negative class, and we are operating with UTF-8 characters, any byte
      with a value >= 0xc4 is a potentially valid starter because it starts a
      character with a value > 255. */

      case OP_NCLASS:
#ifdef SUPPORT_UTF8
      if (utf8)
        {
        start_bits[24] |= 0xf0;              /* Bits for 0xc4 - 0xc8 */
        memset(start_bits+25, 0xff, 7);      /* Bits for 0xc9 - 0xff */
        }
#endif
      /* Fall through */

      case OP_CLASS:
        {
        tcode++;

        /* In UTF-8 mode, the bits in a bit map correspond to character
        values, not to byte values. However, the bit map we are constructing is
        for byte values. So we have to do a conversion for characters whose
        value is > 127. In fact, there are only two possible starting bytes for
        characters in the range 128 - 255. */

#ifdef SUPPORT_UTF8
        if (utf8)
          {
          for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
          for (c = 128; c < 256; c++)
            {
            if ((tcode[c/8] && (1 << (c&7))) != 0)
              {
              int d = (c >> 6) | 0xc0;            /* Set bit for this starter */
              start_bits[d/8] |= (1 << (d&7));    /* and then skip on to the */
              c = (c & 0xc0) + 0x40 - 1;          /* next relevant character. */
              }
            }
          }

        /* In non-UTF-8 mode, the two bit maps are completely compatible. */

        else
#endif
          {
          for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
          }

        /* Advance past the bit map, and act on what follows */

        tcode += 32;
        switch (*tcode)
          {
          case OP_CRSTAR:
          case OP_CRMINSTAR:
          case OP_CRQUERY:
          case OP_CRMINQUERY:
          tcode++;
          break;

          case OP_CRRANGE:
          case OP_CRMINRANGE:
          if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
            else try_next = FALSE;
          break;

          default:
          try_next = FALSE;
          break;
          }
        }
      break; /* End of bitmap class handling */

      }      /* End of switch */
    }        /* End of try_next loop */

  code += GET(code, 1);   /* Advance to next branch */
  }
while (*code == OP_ALT);
return yield;
}


/*************************************************
*          Study a compiled expression           *
*************************************************/

/* This function is handed a compiled expression that it must study to produce
information that will speed up the matching. It returns a pcre_extra block
which then gets handed back to pcre_exec().

Arguments:
  re        points to the compiled expression
  options   contains option bits
  errorptr  points to where to place error messages;
            set NULL unless error

Returns:    pointer to a pcre_extra block, with study_data filled in and the
              appropriate flag set;
            NULL on error or if no optimization possible
*/

PCRE_EXP_DEFN pcre_extra *
pcre_study(const pcre *external_re, int options, const char **errorptr)
{
uschar start_bits[32];
pcre_extra *extra;
pcre_study_data *study;
const uschar *tables;
uschar *code;
compile_data compile_block;
const real_pcre *re = (const real_pcre *)external_re;

*errorptr = NULL;

if (re == NULL || re->magic_number != MAGIC_NUMBER)
  {
  *errorptr = "argument is not a compiled regular expression";
  return NULL;
  }

if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
  {
  *errorptr = "unknown or incorrect option bit(s) set";
  return NULL;
  }

code = (uschar *)re + re->name_table_offset +
  (re->name_count * re->name_entry_size);

/* For an anchored pattern, or an unanchored pattern that has a first char, or
a multiline pattern that matches only at "line starts", no further processing
at present. */

if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
  return NULL;

/* Set the character tables in the block that is passed around */

tables = re->tables;
if (tables == NULL)
  (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
  (void *)(&tables));

compile_block.lcc = tables + lcc_offset;
compile_block.fcc = tables + fcc_offset;
compile_block.cbits = tables + cbits_offset;
compile_block.ctypes = tables + ctypes_offset;

/* See if we can find a fixed set of initial characters for the pattern. */

memset(start_bits, 0, 32 * sizeof(uschar));
if (set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
  (re->options & PCRE_UTF8) != 0, &compile_block) != SSB_DONE) return NULL;

/* Get a pcre_extra block and a pcre_study_data block. The study data is put in
the latter, which is pointed to by the former, which may also get additional
data set later by the calling program. At the moment, the size of
pcre_study_data is fixed. We nevertheless save it in a field for returning via
the pcre_fullinfo() function so that if it becomes variable in the future, we
don't have to change that code. */

extra = (pcre_extra *)(pcre_malloc)
  (sizeof(pcre_extra) + sizeof(pcre_study_data));

if (extra == NULL)
  {
  *errorptr = "failed to get memory";
  return NULL;
  }

study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
extra->flags = PCRE_EXTRA_STUDY_DATA;
extra->study_data = study;

study->size = sizeof(pcre_study_data);
study->options = PCRE_STUDY_MAPPED;
memcpy(study->start_bits, start_bits, sizeof(start_bits));

return extra;
}

/* End of pcre_study.c */
1	/*************************************************
2	* Perl-Compatible Regular Expressions *
3	*************************************************/
4
5	/* PCRE is a library of functions to support regular expressions whose syntax
6	and semantics are as close as possible to those of the Perl 5 language.
7
8	Written by Philip Hazel
9	Copyright (c) 1997-2007 University of Cambridge
10
11	-----------------------------------------------------------------------------
12	Redistribution and use in source and binary forms, with or without
13	modification, are permitted provided that the following conditions are met:
14
15	* Redistributions of source code must retain the above copyright notice,
16	this list of conditions and the following disclaimer.
17
18	* Redistributions in binary form must reproduce the above copyright
19	notice, this list of conditions and the following disclaimer in the
20	documentation and/or other materials provided with the distribution.
21
22	* Neither the name of the University of Cambridge nor the names of its
23	contributors may be used to endorse or promote products derived from
24	this software without specific prior written permission.
25
26	THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
27	AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28	IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
29	ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
30	LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
31	CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
32	SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
33	INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
34	CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
35	ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36	POSSIBILITY OF SUCH DAMAGE.
37	-----------------------------------------------------------------------------
38	*/
39
40
41	/* This module contains the external function pcre_study(), along with local
42	supporting functions. */
43
44
45	#ifdef HAVE_CONFIG_H
46	#include <config.h>
47	#endif
48
49	#include "pcre_internal.h"
50
51
52	/* Returns from set_start_bits() */
53
54	enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
55
56
57	/*************************************************
58	* Set a bit and maybe its alternate case *
59	*************************************************/
60
61	/* Given a character, set its bit in the table, and also the bit for the other
62	version of a letter if we are caseless.
63
64	Arguments:
65	start_bits points to the bit map
66	c is the character
67	caseless the caseless flag
68	cd the block with char table pointers
69
70	Returns: nothing
71	*/
72
73	static void
74	set_bit(uschar start_bits, unsigned int c, BOOL caseless, compile_data cd)
75	{
76	start_bits[c/8] \|= (1 << (c&7));
77	if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
78	start_bits[cd->fcc[c]/8] \|= (1 << (cd->fcc[c]&7));
79	}
80
81
82
83	/*************************************************
84	* Create bitmap of starting bytes *
85	*************************************************/
86
87	/* This function scans a compiled unanchored expression recursively and
88	attempts to build a bitmap of the set of possible starting bytes. As time goes
89	by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
90	useful for parenthesized groups in patterns such as (a*)b where the group
91	provides some optional starting bytes but scanning must continue at the outer
92	level to find at least one mandatory byte. At the outermost level, this
93	function fails unless the result is SSB_DONE.
94
95	Arguments:
96	code points to an expression
97	start_bits points to a 32-byte table, initialized to 0
98	caseless the current state of the caseless flag
99	utf8 TRUE if in UTF-8 mode
100	cd the block with char table pointers
101
102	Returns: SSB_FAIL => Failed to find any starting bytes
103	SSB_DONE => Found mandatory starting bytes
104	SSB_CONTINUE => Found optional starting bytes
105	*/
106
107	static int
108	set_start_bits(const uschar code, uschar start_bits, BOOL caseless,
109	BOOL utf8, compile_data *cd)
110	{
111	register int c;
112	int yield = SSB_DONE;
113
114	#if 0
115	/* ========================================================================= */
116	/* The following comment and code was inserted in January 1999. In May 2006,
117	when it was observed to cause compiler warnings about unused values, I took it
118	out again. If anybody is still using OS/2, they will have to put it back
119	manually. */
120
121	/* This next statement and the later reference to dummy are here in order to
122	trick the optimizer of the IBM C compiler for OS/2 into generating correct
123	code. Apparently IBM isn't going to fix the problem, and we would rather not
124	disable optimization (in this module it actually makes a big difference, and
125	the pcre module can use all the optimization it can get). */
126
127	volatile int dummy;
128	/* ========================================================================= */
129	#endif
130
131	do
132	{
133	const uschar tcode = code + (((int)code == OP_CBRA)? 3:1) + LINK_SIZE;
134	BOOL try_next = TRUE;
135
136	while (try_next) /* Loop for items in this branch */
137	{
138	int rc;
139	switch(*tcode)
140	{
141	/* Fail if we reach something we don't understand */
142
143	default:
144	return SSB_FAIL;
145
146	/* If we hit a bracket or a positive lookahead assertion, recurse to set
147	bits from within the subpattern. If it can't find anything, we have to
148	give up. If it finds some mandatory character(s), we are done for this
149	branch. Otherwise, carry on scanning after the subpattern. */
150
151	case OP_BRA:
152	case OP_SBRA:
153	case OP_CBRA:
154	case OP_SCBRA:
155	case OP_ONCE:
156	case OP_ASSERT:
157	rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
158	if (rc == SSB_FAIL) return SSB_FAIL;
159	if (rc == SSB_DONE) try_next = FALSE; else
160	{
161	do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
162	tcode += 1 + LINK_SIZE;
163	}
164	break;
165
166	/* If we hit ALT or KET, it means we haven't found anything mandatory in
167	this branch, though we might have found something optional. For ALT, we
168	continue with the next alternative, but we have to arrange that the final
169	result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
170	return SSB_CONTINUE: if this is the top level, that indicates failure,
171	but after a nested subpattern, it causes scanning to continue. */
172
173	case OP_ALT:
174	yield = SSB_CONTINUE;
175	try_next = FALSE;
176	break;
177
178	case OP_KET:
179	case OP_KETRMAX:
180	case OP_KETRMIN:
181	return SSB_CONTINUE;
182
183	/* Skip over callout */
184
185	case OP_CALLOUT:
186	tcode += 2 + 2*LINK_SIZE;
187	break;
188
189	/* Skip over lookbehind and negative lookahead assertions */
190
191	case OP_ASSERT_NOT:
192	case OP_ASSERTBACK:
193	case OP_ASSERTBACK_NOT:
194	do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
195	tcode += 1 + LINK_SIZE;
196	break;
197
198	/* Skip over an option setting, changing the caseless flag */
199
200	case OP_OPT:
201	caseless = (tcode[1] & PCRE_CASELESS) != 0;
202	tcode += 2;
203	break;
204
205	/* BRAZERO does the bracket, but carries on. */
206
207	case OP_BRAZERO:
208	case OP_BRAMINZERO:
209	if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
210	return SSB_FAIL;
211	/* =========================================================================
212	See the comment at the head of this function concerning the next line,
213	which was an old fudge for the benefit of OS/2.
214	dummy = 1;
215	========================================================================= */
216	do tcode += GET(tcode,1); while (*tcode == OP_ALT);
217	tcode += 1 + LINK_SIZE;
218	break;
219
220	/* Single-char * or ? sets the bit and tries the next item */
221
222	case OP_STAR:
223	case OP_MINSTAR:
224	case OP_POSSTAR:
225	case OP_QUERY:
226	case OP_MINQUERY:
227	case OP_POSQUERY:
228	set_bit(start_bits, tcode[1], caseless, cd);
229	tcode += 2;
230	#ifdef SUPPORT_UTF8
231	if (utf8 && tcode[-1] >= 0xc0)
232	tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
233	#endif
234	break;
235
236	/* Single-char upto sets the bit and tries the next */
237
238	case OP_UPTO:
239	case OP_MINUPTO:
240	case OP_POSUPTO:
241	set_bit(start_bits, tcode[3], caseless, cd);
242	tcode += 4;
243	#ifdef SUPPORT_UTF8
244	if (utf8 && tcode[-1] >= 0xc0)
245	tcode += _pcre_utf8_table4[tcode[-1] & 0x3f];
246	#endif
247	break;
248
249	/* At least one single char sets the bit and stops */
250
251	case OP_EXACT: /* Fall through */
252	tcode += 2;
253
254	case OP_CHAR:
255	case OP_CHARNC:
256	case OP_PLUS:
257	case OP_MINPLUS:
258	case OP_POSPLUS:
259	set_bit(start_bits, tcode[1], caseless, cd);
260	try_next = FALSE;
261	break;
262
263	/* Single character type sets the bits and stops */
264
265	case OP_NOT_DIGIT:
266	for (c = 0; c < 32; c++)
267	start_bits[c] \|= ~cd->cbits[c+cbit_digit];
268	try_next = FALSE;
269	break;
270
271	case OP_DIGIT:
272	for (c = 0; c < 32; c++)
273	start_bits[c] \|= cd->cbits[c+cbit_digit];
274	try_next = FALSE;
275	break;
276
277	/* The cbit_space table has vertical tab as whitespace; we have to
278	discard it. */
279
280	case OP_NOT_WHITESPACE:
281	for (c = 0; c < 32; c++)
282	{
283	int d = cd->cbits[c+cbit_space];
284	if (c == 1) d &= ~0x08;
285	start_bits[c] \|= ~d;
286	}
287	try_next = FALSE;
288	break;
289
290	/* The cbit_space table has vertical tab as whitespace; we have to
291	discard it. */
292
293	case OP_WHITESPACE:
294	for (c = 0; c < 32; c++)
295	{
296	int d = cd->cbits[c+cbit_space];
297	if (c == 1) d &= ~0x08;
298	start_bits[c] \|= d;
299	}
300	try_next = FALSE;
301	break;
302
303	case OP_NOT_WORDCHAR:
304	for (c = 0; c < 32; c++)
305	start_bits[c] \|= ~cd->cbits[c+cbit_word];
306	try_next = FALSE;
307	break;
308
309	case OP_WORDCHAR:
310	for (c = 0; c < 32; c++)
311	start_bits[c] \|= cd->cbits[c+cbit_word];
312	try_next = FALSE;
313	break;
314
315	/* One or more character type fudges the pointer and restarts, knowing
316	it will hit a single character type and stop there. */
317
318	case OP_TYPEPLUS:
319	case OP_TYPEMINPLUS:
320	tcode++;
321	break;
322
323	case OP_TYPEEXACT:
324	tcode += 3;
325	break;
326
327	/* Zero or more repeats of character types set the bits and then
328	try again. */
329
330	case OP_TYPEUPTO:
331	case OP_TYPEMINUPTO:
332	case OP_TYPEPOSUPTO:
333	tcode += 2; /* Fall through */
334
335	case OP_TYPESTAR:
336	case OP_TYPEMINSTAR:
337	case OP_TYPEPOSSTAR:
338	case OP_TYPEQUERY:
339	case OP_TYPEMINQUERY:
340	case OP_TYPEPOSQUERY:
341	switch(tcode[1])
342	{
343	case OP_ANY:
344	return SSB_FAIL;
345
346	case OP_NOT_DIGIT:
347	for (c = 0; c < 32; c++)
348	start_bits[c] \|= ~cd->cbits[c+cbit_digit];
349	break;
350
351	case OP_DIGIT:
352	for (c = 0; c < 32; c++)
353	start_bits[c] \|= cd->cbits[c+cbit_digit];
354	break;
355
356	/* The cbit_space table has vertical tab as whitespace; we have to
357	discard it. */
358
359	case OP_NOT_WHITESPACE:
360	for (c = 0; c < 32; c++)
361	{
362	int d = cd->cbits[c+cbit_space];
363	if (c == 1) d &= ~0x08;
364	start_bits[c] \|= ~d;
365	}
366	break;
367
368	/* The cbit_space table has vertical tab as whitespace; we have to
369	discard it. */
370
371	case OP_WHITESPACE:
372	for (c = 0; c < 32; c++)
373	{
374	int d = cd->cbits[c+cbit_space];
375	if (c == 1) d &= ~0x08;
376	start_bits[c] \|= d;
377	}
378	break;
379
380	case OP_NOT_WORDCHAR:
381	for (c = 0; c < 32; c++)
382	start_bits[c] \|= ~cd->cbits[c+cbit_word];
383	break;
384
385	case OP_WORDCHAR:
386	for (c = 0; c < 32; c++)
387	start_bits[c] \|= cd->cbits[c+cbit_word];
388	break;
389	}
390
391	tcode += 2;
392	break;
393
394	/* Character class where all the information is in a bit map: set the
395	bits and either carry on or not, according to the repeat count. If it was
396	a negative class, and we are operating with UTF-8 characters, any byte
397	with a value >= 0xc4 is a potentially valid starter because it starts a
398	character with a value > 255. */
399
400	case OP_NCLASS:
401	#ifdef SUPPORT_UTF8
402	if (utf8)
403	{
404	start_bits[24] \|= 0xf0; /* Bits for 0xc4 - 0xc8 */
405	memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
406	}
407	#endif
408	/* Fall through */
409
410	case OP_CLASS:
411	{
412	tcode++;
413
414	/* In UTF-8 mode, the bits in a bit map correspond to character
415	values, not to byte values. However, the bit map we are constructing is
416	for byte values. So we have to do a conversion for characters whose
417	value is > 127. In fact, there are only two possible starting bytes for
418	characters in the range 128 - 255. */
419
420	#ifdef SUPPORT_UTF8
421	if (utf8)
422	{
423	for (c = 0; c < 16; c++) start_bits[c] \|= tcode[c];
424	for (c = 128; c < 256; c++)
425	{
426	if ((tcode[c/8] && (1 << (c&7))) != 0)
427	{
428	int d = (c >> 6) \| 0xc0; /* Set bit for this starter */
429	start_bits[d/8] \|= (1 << (d&7)); /* and then skip on to the */
430	c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
431	}
432	}
433	}
434
435	/* In non-UTF-8 mode, the two bit maps are completely compatible. */
436
437	else
438	#endif
439	{
440	for (c = 0; c < 32; c++) start_bits[c] \|= tcode[c];
441	}
442
443	/* Advance past the bit map, and act on what follows */
444
445	tcode += 32;
446	switch (*tcode)
447	{
448	case OP_CRSTAR:
449	case OP_CRMINSTAR:
450	case OP_CRQUERY:
451	case OP_CRMINQUERY:
452	tcode++;
453	break;
454
455	case OP_CRRANGE:
456	case OP_CRMINRANGE:
457	if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
458	else try_next = FALSE;
459	break;
460
461	default:
462	try_next = FALSE;
463	break;
464	}
465	}
466	break; /* End of bitmap class handling */
467
468	} /* End of switch */
469	} /* End of try_next loop */
470
471	code += GET(code, 1); /* Advance to next branch */
472	}
473	while (*code == OP_ALT);
474	return yield;
475	}
476
477
478
479	/*************************************************
480	* Study a compiled expression *
481	*************************************************/
482
483	/* This function is handed a compiled expression that it must study to produce
484	information that will speed up the matching. It returns a pcre_extra block
485	which then gets handed back to pcre_exec().
486
487	Arguments:
488	re points to the compiled expression
489	options contains option bits
490	errorptr points to where to place error messages;
491	set NULL unless error
492
493	Returns: pointer to a pcre_extra block, with study_data filled in and the
494	appropriate flag set;
495	NULL on error or if no optimization possible
496	*/
497
498	PCRE_EXP_DEFN pcre_extra *
499	pcre_study(const pcre external_re, int options, const char *errorptr)
500	{
501	uschar start_bits[32];
502	pcre_extra *extra;
503	pcre_study_data *study;
504	const uschar *tables;
505	uschar *code;
506	compile_data compile_block;
507	const real_pcre re = (const real_pcre )external_re;
508
509	*errorptr = NULL;
510
511	if (re == NULL \|\| re->magic_number != MAGIC_NUMBER)
512	{
513	*errorptr = "argument is not a compiled regular expression";
514	return NULL;
515	}
516
517	if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
518	{
519	*errorptr = "unknown or incorrect option bit(s) set";
520	return NULL;
521	}
522
523	code = (uschar *)re + re->name_table_offset +
524	(re->name_count * re->name_entry_size);
525
526	/* For an anchored pattern, or an unanchored pattern that has a first char, or
527	a multiline pattern that matches only at "line starts", no further processing
528	at present. */
529
530	if ((re->options & (PCRE_ANCHORED\|PCRE_FIRSTSET\|PCRE_STARTLINE)) != 0)
531	return NULL;
532
533	/* Set the character tables in the block that is passed around */
534
535	tables = re->tables;
536	if (tables == NULL)
537	(void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
538	(void *)(&tables));
539
540	compile_block.lcc = tables + lcc_offset;
541	compile_block.fcc = tables + fcc_offset;
542	compile_block.cbits = tables + cbits_offset;
543	compile_block.ctypes = tables + ctypes_offset;
544
545	/* See if we can find a fixed set of initial characters for the pattern. */
546
547	memset(start_bits, 0, 32 * sizeof(uschar));
548	if (set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
549	(re->options & PCRE_UTF8) != 0, &compile_block) != SSB_DONE) return NULL;
550
551	/* Get a pcre_extra block and a pcre_study_data block. The study data is put in
552	the latter, which is pointed to by the former, which may also get additional
553	data set later by the calling program. At the moment, the size of
554	pcre_study_data is fixed. We nevertheless save it in a field for returning via
555	the pcre_fullinfo() function so that if it becomes variable in the future, we
556	don't have to change that code. */
557
558	extra = (pcre_extra *)(pcre_malloc)
559	(sizeof(pcre_extra) + sizeof(pcre_study_data));
560
561	if (extra == NULL)
562	{
563	*errorptr = "failed to get memory";
564	return NULL;
565	}
566
567	study = (pcre_study_data )((char )extra + sizeof(pcre_extra));
568	extra->flags = PCRE_EXTRA_STUDY_DATA;
569	extra->study_data = study;
570
571	study->size = sizeof(pcre_study_data);
572	study->options = PCRE_STUDY_MAPPED;
573	memcpy(study->start_bits, start_bits, sizeof(start_bits));
574
575	return extra;
576	}
577
578	/* End of pcre_study.c */
Name	Value
svn:eol-style	native
svn:keywords	"Author Date Id Revision Url"