tags/pcre-3.9/study.c

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

/*
This 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. See
the file Tech.Notes for some information on the internals.

Written by: Philip Hazel <ph10@cam.ac.uk>

           Copyright (c) 1997-2001 University of Cambridge

-----------------------------------------------------------------------------
Permission is granted to anyone to use this software for any purpose on any
computer system, and to redistribute it freely, subject to the following
restrictions:

1. This software is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

2. The origin of this software must not be misrepresented, either by
   explicit claim or by omission.

3. Altered versions must be plainly marked as such, and must not be
   misrepresented as being the original software.

4. 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.
-----------------------------------------------------------------------------
*/


/* Include the internals header, which itself includes Standard C headers plus
the external pcre header. */

#include "internal.h"


/*************************************************
*      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, 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 chars       *
*************************************************/

/* This function scans a compiled unanchored expression and attempts to build a
bitmap of the set of initial characters. If it can't, it returns FALSE. As time
goes by, we may be able to get more clever at doing this.

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
  cd           the block with char table pointers

Returns:       TRUE if table built, FALSE otherwise
*/

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

/* 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;

do
  {
  const uschar *tcode = code + 3;
  BOOL try_next = TRUE;

  while (try_next)
    {
    /* If a branch starts with a bracket or a positive lookahead assertion,
    recurse to set bits from within them. That's all for this branch. */

    if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT)
      {
      if (!set_start_bits(tcode, start_bits, caseless, cd))
        return FALSE;
      try_next = FALSE;
      }

    else switch(*tcode)
      {
      default:
      return FALSE;

      /* Skip over extended extraction bracket number */

      case OP_BRANUMBER:
      tcode += 3;
      break;

      /* Skip over lookbehind and negative lookahead assertions */

      case OP_ASSERT_NOT:
      case OP_ASSERTBACK:
      case OP_ASSERTBACK_NOT:
      do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
      tcode += 3;
      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, cd))
        return FALSE;
      dummy = 1;
      do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
      tcode += 3;
      break;

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

      case OP_STAR:
      case OP_MINSTAR:
      case OP_QUERY:
      case OP_MINQUERY:
      set_bit(start_bits, tcode[1], caseless, cd);
      tcode += 2;
      break;

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

      case OP_UPTO:
      case OP_MINUPTO:
      set_bit(start_bits, tcode[3], caseless, cd);
      tcode += 4;
      break;

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

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

      case OP_CHARS:       /* Fall through */
      tcode++;

      case OP_PLUS:
      case OP_MINPLUS:
      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;

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

      case OP_WHITESPACE:
      for (c = 0; c < 32; c++)
        start_bits[c] |= cd->cbits[c+cbit_space];
      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:
      tcode += 2;               /* Fall through */

      case OP_TYPESTAR:
      case OP_TYPEMINSTAR:
      case OP_TYPEQUERY:
      case OP_TYPEMINQUERY:
      switch(tcode[1])
        {
        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;

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

        case OP_WHITESPACE:
        for (c = 0; c < 32; c++)
          start_bits[c] |= cd->cbits[c+cbit_space];
        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: set the bits and either carry on or not,
      according to the repeat count. */

      case OP_CLASS:
        {
        tcode++;
        for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
        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 class handling */

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

  code += (code[1] << 8) + code[2];   /* Advance to next branch */
  }
while (*code == OP_ALT);
return TRUE;
}


/*************************************************
*          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,
            NULL on error or if no optimization possible
*/

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

*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;
  }

/* For an anchored pattern, or an unchored 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 which is passed around */

compile_block.lcc = re->tables + lcc_offset;
compile_block.fcc = re->tables + fcc_offset;
compile_block.cbits = re->tables + cbits_offset;
compile_block.ctypes = re->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(re->code, start_bits, (re->options & PCRE_CASELESS) != 0,
  &compile_block)) return NULL;

/* Get an "extra" block and put the information therein. */

extra = (real_pcre_extra *)(pcre_malloc)(sizeof(real_pcre_extra));

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

extra->options = PCRE_STUDY_MAPPED;
memcpy(extra->start_bits, start_bits, sizeof(start_bits));

return (pcre_extra *)extra;
}

/* End of study.c */
1	/*************************************************
2	* Perl-Compatible Regular Expressions *
3	*************************************************/
4
5	/*
6	This is a library of functions to support regular expressions whose syntax
7	and semantics are as close as possible to those of the Perl 5 language. See
8	the file Tech.Notes for some information on the internals.
9
10	Written by: Philip Hazel <ph10@cam.ac.uk>
11
12	Copyright (c) 1997-2001 University of Cambridge
13
14	-----------------------------------------------------------------------------
15	Permission is granted to anyone to use this software for any purpose on any
16	computer system, and to redistribute it freely, subject to the following
17	restrictions:
18
19	1. This software is distributed in the hope that it will be useful,
20	but WITHOUT ANY WARRANTY; without even the implied warranty of
21	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
22
23	2. The origin of this software must not be misrepresented, either by
24	explicit claim or by omission.
25
26	3. Altered versions must be plainly marked as such, and must not be
27	misrepresented as being the original software.
28
29	4. If PCRE is embedded in any software that is released under the GNU
30	General Purpose Licence (GPL), then the terms of that licence shall
31	supersede any condition above with which it is incompatible.
32	-----------------------------------------------------------------------------
33	*/
34
35
36	/* Include the internals header, which itself includes Standard C headers plus
37	the external pcre header. */
38
39	#include "internal.h"
40
41
42
43	/*************************************************
44	* Set a bit and maybe its alternate case *
45	*************************************************/
46
47	/* Given a character, set its bit in the table, and also the bit for the other
48	version of a letter if we are caseless.
49
50	Arguments:
51	start_bits points to the bit map
52	c is the character
53	caseless the caseless flag
54	cd the block with char table pointers
55
56	Returns: nothing
57	*/
58
59	static void
60	set_bit(uschar start_bits, int c, BOOL caseless, compile_data cd)
61	{
62	start_bits[c/8] \|= (1 << (c&7));
63	if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
64	start_bits[cd->fcc[c]/8] \|= (1 << (cd->fcc[c]&7));
65	}
66
67
68
69	/*************************************************
70	* Create bitmap of starting chars *
71	*************************************************/
72
73	/* This function scans a compiled unanchored expression and attempts to build a
74	bitmap of the set of initial characters. If it can't, it returns FALSE. As time
75	goes by, we may be able to get more clever at doing this.
76
77	Arguments:
78	code points to an expression
79	start_bits points to a 32-byte table, initialized to 0
80	caseless the current state of the caseless flag
81	cd the block with char table pointers
82
83	Returns: TRUE if table built, FALSE otherwise
84	*/
85
86	static BOOL
87	set_start_bits(const uschar code, uschar start_bits, BOOL caseless,
88	compile_data *cd)
89	{
90	register int c;
91
92	/* This next statement and the later reference to dummy are here in order to
93	trick the optimizer of the IBM C compiler for OS/2 into generating correct
94	code. Apparently IBM isn't going to fix the problem, and we would rather not
95	disable optimization (in this module it actually makes a big difference, and
96	the pcre module can use all the optimization it can get). */
97
98	volatile int dummy;
99
100	do
101	{
102	const uschar *tcode = code + 3;
103	BOOL try_next = TRUE;
104
105	while (try_next)
106	{
107	/* If a branch starts with a bracket or a positive lookahead assertion,
108	recurse to set bits from within them. That's all for this branch. */
109
110	if ((int)tcode >= OP_BRA \|\| tcode == OP_ASSERT)
111	{
112	if (!set_start_bits(tcode, start_bits, caseless, cd))
113	return FALSE;
114	try_next = FALSE;
115	}
116
117	else switch(*tcode)
118	{
119	default:
120	return FALSE;
121
122	/* Skip over extended extraction bracket number */
123
124	case OP_BRANUMBER:
125	tcode += 3;
126	break;
127
128	/* Skip over lookbehind and negative lookahead assertions */
129
130	case OP_ASSERT_NOT:
131	case OP_ASSERTBACK:
132	case OP_ASSERTBACK_NOT:
133	do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
134	tcode += 3;
135	break;
136
137	/* Skip over an option setting, changing the caseless flag */
138
139	case OP_OPT:
140	caseless = (tcode[1] & PCRE_CASELESS) != 0;
141	tcode += 2;
142	break;
143
144	/* BRAZERO does the bracket, but carries on. */
145
146	case OP_BRAZERO:
147	case OP_BRAMINZERO:
148	if (!set_start_bits(++tcode, start_bits, caseless, cd))
149	return FALSE;
150	dummy = 1;
151	do tcode += (tcode[1] << 8) + tcode[2]; while (*tcode == OP_ALT);
152	tcode += 3;
153	break;
154
155	/* Single-char * or ? sets the bit and tries the next item */
156
157	case OP_STAR:
158	case OP_MINSTAR:
159	case OP_QUERY:
160	case OP_MINQUERY:
161	set_bit(start_bits, tcode[1], caseless, cd);
162	tcode += 2;
163	break;
164
165	/* Single-char upto sets the bit and tries the next */
166
167	case OP_UPTO:
168	case OP_MINUPTO:
169	set_bit(start_bits, tcode[3], caseless, cd);
170	tcode += 4;
171	break;
172
173	/* At least one single char sets the bit and stops */
174
175	case OP_EXACT: /* Fall through */
176	tcode++;
177
178	case OP_CHARS: /* Fall through */
179	tcode++;
180
181	case OP_PLUS:
182	case OP_MINPLUS:
183	set_bit(start_bits, tcode[1], caseless, cd);
184	try_next = FALSE;
185	break;
186
187	/* Single character type sets the bits and stops */
188
189	case OP_NOT_DIGIT:
190	for (c = 0; c < 32; c++)
191	start_bits[c] \|= ~cd->cbits[c+cbit_digit];
192	try_next = FALSE;
193	break;
194
195	case OP_DIGIT:
196	for (c = 0; c < 32; c++)
197	start_bits[c] \|= cd->cbits[c+cbit_digit];
198	try_next = FALSE;
199	break;
200
201	case OP_NOT_WHITESPACE:
202	for (c = 0; c < 32; c++)
203	start_bits[c] \|= ~cd->cbits[c+cbit_space];
204	try_next = FALSE;
205	break;
206
207	case OP_WHITESPACE:
208	for (c = 0; c < 32; c++)
209	start_bits[c] \|= cd->cbits[c+cbit_space];
210	try_next = FALSE;
211	break;
212
213	case OP_NOT_WORDCHAR:
214	for (c = 0; c < 32; c++)
215	start_bits[c] \|= ~cd->cbits[c+cbit_word];
216	try_next = FALSE;
217	break;
218
219	case OP_WORDCHAR:
220	for (c = 0; c < 32; c++)
221	start_bits[c] \|= cd->cbits[c+cbit_word];
222	try_next = FALSE;
223	break;
224
225	/* One or more character type fudges the pointer and restarts, knowing
226	it will hit a single character type and stop there. */
227
228	case OP_TYPEPLUS:
229	case OP_TYPEMINPLUS:
230	tcode++;
231	break;
232
233	case OP_TYPEEXACT:
234	tcode += 3;
235	break;
236
237	/* Zero or more repeats of character types set the bits and then
238	try again. */
239
240	case OP_TYPEUPTO:
241	case OP_TYPEMINUPTO:
242	tcode += 2; /* Fall through */
243
244	case OP_TYPESTAR:
245	case OP_TYPEMINSTAR:
246	case OP_TYPEQUERY:
247	case OP_TYPEMINQUERY:
248	switch(tcode[1])
249	{
250	case OP_NOT_DIGIT:
251	for (c = 0; c < 32; c++)
252	start_bits[c] \|= ~cd->cbits[c+cbit_digit];
253	break;
254
255	case OP_DIGIT:
256	for (c = 0; c < 32; c++)
257	start_bits[c] \|= cd->cbits[c+cbit_digit];
258	break;
259
260	case OP_NOT_WHITESPACE:
261	for (c = 0; c < 32; c++)
262	start_bits[c] \|= ~cd->cbits[c+cbit_space];
263	break;
264
265	case OP_WHITESPACE:
266	for (c = 0; c < 32; c++)
267	start_bits[c] \|= cd->cbits[c+cbit_space];
268	break;
269
270	case OP_NOT_WORDCHAR:
271	for (c = 0; c < 32; c++)
272	start_bits[c] \|= ~cd->cbits[c+cbit_word];
273	break;
274
275	case OP_WORDCHAR:
276	for (c = 0; c < 32; c++)
277	start_bits[c] \|= cd->cbits[c+cbit_word];
278	break;
279	}
280
281	tcode += 2;
282	break;
283
284	/* Character class: set the bits and either carry on or not,
285	according to the repeat count. */
286
287	case OP_CLASS:
288	{
289	tcode++;
290	for (c = 0; c < 32; c++) start_bits[c] \|= tcode[c];
291	tcode += 32;
292	switch (*tcode)
293	{
294	case OP_CRSTAR:
295	case OP_CRMINSTAR:
296	case OP_CRQUERY:
297	case OP_CRMINQUERY:
298	tcode++;
299	break;
300
301	case OP_CRRANGE:
302	case OP_CRMINRANGE:
303	if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
304	else try_next = FALSE;
305	break;
306
307	default:
308	try_next = FALSE;
309	break;
310	}
311	}
312	break; /* End of class handling */
313
314	} /* End of switch */
315	} /* End of try_next loop */
316
317	code += (code[1] << 8) + code[2]; /* Advance to next branch */
318	}
319	while (*code == OP_ALT);
320	return TRUE;
321	}
322
323
324
325	/*************************************************
326	* Study a compiled expression *
327	*************************************************/
328
329	/* This function is handed a compiled expression that it must study to produce
330	information that will speed up the matching. It returns a pcre_extra block
331	which then gets handed back to pcre_exec().
332
333	Arguments:
334	re points to the compiled expression
335	options contains option bits
336	errorptr points to where to place error messages;
337	set NULL unless error
338
339	Returns: pointer to a pcre_extra block,
340	NULL on error or if no optimization possible
341	*/
342
343	pcre_extra *
344	pcre_study(const pcre external_re, int options, const char *errorptr)
345	{
346	uschar start_bits[32];
347	real_pcre_extra *extra;
348	const real_pcre re = (const real_pcre )external_re;
349	compile_data compile_block;
350
351	*errorptr = NULL;
352
353	if (re == NULL \|\| re->magic_number != MAGIC_NUMBER)
354	{
355	*errorptr = "argument is not a compiled regular expression";
356	return NULL;
357	}
358
359	if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
360	{
361	*errorptr = "unknown or incorrect option bit(s) set";
362	return NULL;
363	}
364
365	/* For an anchored pattern, or an unchored pattern that has a first char, or a
366	multiline pattern that matches only at "line starts", no further processing at
367	present. */
368
369	if ((re->options & (PCRE_ANCHORED\|PCRE_FIRSTSET\|PCRE_STARTLINE)) != 0)
370	return NULL;
371
372	/* Set the character tables in the block which is passed around */
373
374	compile_block.lcc = re->tables + lcc_offset;
375	compile_block.fcc = re->tables + fcc_offset;
376	compile_block.cbits = re->tables + cbits_offset;
377	compile_block.ctypes = re->tables + ctypes_offset;
378
379	/* See if we can find a fixed set of initial characters for the pattern. */
380
381	memset(start_bits, 0, 32 * sizeof(uschar));
382	if (!set_start_bits(re->code, start_bits, (re->options & PCRE_CASELESS) != 0,
383	&compile_block)) return NULL;
384
385	/* Get an "extra" block and put the information therein. */
386
387	extra = (real_pcre_extra *)(pcre_malloc)(sizeof(real_pcre_extra));
388
389	if (extra == NULL)
390	{
391	*errorptr = "failed to get memory";
392	return NULL;
393	}
394
395	extra->options = PCRE_STUDY_MAPPED;
396	memcpy(extra->start_bits, start_bits, sizeof(start_bits));
397
398	return (pcre_extra *)extra;
399	}
400
401	/* End of study.c */