1
/*************************************************
2
* Perl-Compatible Regular Expressions *
3
*************************************************/
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.
10
Written by: Philip Hazel <ph10@cam.ac.uk>
12
Copyright (c) 1997-2004 University of Cambridge
14
-----------------------------------------------------------------------------
15
Redistribution and use in source and binary forms, with or without
16
modification, are permitted provided that the following conditions are met:
18
* Redistributions of source code must retain the above copyright notice,
19
this list of conditions and the following disclaimer.
21
* Redistributions in binary form must reproduce the above copyright
22
notice, this list of conditions and the following disclaimer in the
23
documentation and/or other materials provided with the distribution.
25
* Neither the name of the University of Cambridge nor the names of its
26
contributors may be used to endorse or promote products derived from
27
this software without specific prior written permission.
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
30
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
31
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
32
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
33
LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
34
CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
35
SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
36
INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
37
CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
38
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
39
POSSIBILITY OF SUCH DAMAGE.
40
-----------------------------------------------------------------------------
44
/* Include the internals header, which itself includes Standard C headers plus
45
the external pcre header. */
51
/*************************************************
52
* Set a bit and maybe its alternate case *
53
*************************************************/
55
/* Given a character, set its bit in the table, and also the bit for the other
56
version of a letter if we are caseless.
59
start_bits points to the bit map
61
caseless the caseless flag
62
cd the block with char table pointers
68
set_bit(uschar *start_bits, unsigned int c, BOOL caseless, compile_data *cd)
70
start_bits[c/8] |= (1 << (c&7));
71
if (caseless && (cd->ctypes[c] & ctype_letter) != 0)
72
start_bits[cd->fcc[c]/8] |= (1 << (cd->fcc[c]&7));
77
/*************************************************
78
* Create bitmap of starting chars *
79
*************************************************/
81
/* This function scans a compiled unanchored expression and attempts to build a
82
bitmap of the set of initial characters. If it can't, it returns FALSE. As time
83
goes by, we may be able to get more clever at doing this.
86
code points to an expression
87
start_bits points to a 32-byte table, initialized to 0
88
caseless the current state of the caseless flag
89
utf8 TRUE if in UTF-8 mode
90
cd the block with char table pointers
92
Returns: TRUE if table built, FALSE otherwise
96
set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
97
BOOL utf8, compile_data *cd)
101
/* This next statement and the later reference to dummy are here in order to
102
trick the optimizer of the IBM C compiler for OS/2 into generating correct
103
code. Apparently IBM isn't going to fix the problem, and we would rather not
104
disable optimization (in this module it actually makes a big difference, and
105
the pcre module can use all the optimization it can get). */
111
const uschar *tcode = code + 1 + LINK_SIZE;
112
BOOL try_next = TRUE;
116
/* If a branch starts with a bracket or a positive lookahead assertion,
117
recurse to set bits from within them. That's all for this branch. */
119
if ((int)*tcode >= OP_BRA || *tcode == OP_ASSERT)
121
if (!set_start_bits(tcode, start_bits, caseless, utf8, cd))
131
/* Skip over callout */
134
tcode += 2 + 2*LINK_SIZE;
137
/* Skip over extended extraction bracket number */
143
/* Skip over lookbehind and negative lookahead assertions */
147
case OP_ASSERTBACK_NOT:
148
do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
149
tcode += 1+LINK_SIZE;
152
/* Skip over an option setting, changing the caseless flag */
155
caseless = (tcode[1] & PCRE_CASELESS) != 0;
159
/* BRAZERO does the bracket, but carries on. */
163
if (!set_start_bits(++tcode, start_bits, caseless, utf8, cd))
166
do tcode += GET(tcode,1); while (*tcode == OP_ALT);
167
tcode += 1+LINK_SIZE;
170
/* Single-char * or ? sets the bit and tries the next item */
176
set_bit(start_bits, tcode[1], caseless, cd);
179
if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;
183
/* Single-char upto sets the bit and tries the next */
187
set_bit(start_bits, tcode[3], caseless, cd);
190
if (utf8) while ((*tcode & 0xc0) == 0x80) tcode++;
194
/* At least one single char sets the bit and stops */
196
case OP_EXACT: /* Fall through */
203
set_bit(start_bits, tcode[1], caseless, cd);
207
/* Single character type sets the bits and stops */
210
for (c = 0; c < 32; c++)
211
start_bits[c] |= ~cd->cbits[c+cbit_digit];
216
for (c = 0; c < 32; c++)
217
start_bits[c] |= cd->cbits[c+cbit_digit];
221
case OP_NOT_WHITESPACE:
222
for (c = 0; c < 32; c++)
223
start_bits[c] |= ~cd->cbits[c+cbit_space];
228
for (c = 0; c < 32; c++)
229
start_bits[c] |= cd->cbits[c+cbit_space];
233
case OP_NOT_WORDCHAR:
234
for (c = 0; c < 32; c++)
235
start_bits[c] |= ~cd->cbits[c+cbit_word];
240
for (c = 0; c < 32; c++)
241
start_bits[c] |= cd->cbits[c+cbit_word];
245
/* One or more character type fudges the pointer and restarts, knowing
246
it will hit a single character type and stop there. */
257
/* Zero or more repeats of character types set the bits and then
262
tcode += 2; /* Fall through */
267
case OP_TYPEMINQUERY:
274
for (c = 0; c < 32; c++)
275
start_bits[c] |= ~cd->cbits[c+cbit_digit];
279
for (c = 0; c < 32; c++)
280
start_bits[c] |= cd->cbits[c+cbit_digit];
283
case OP_NOT_WHITESPACE:
284
for (c = 0; c < 32; c++)
285
start_bits[c] |= ~cd->cbits[c+cbit_space];
289
for (c = 0; c < 32; c++)
290
start_bits[c] |= cd->cbits[c+cbit_space];
293
case OP_NOT_WORDCHAR:
294
for (c = 0; c < 32; c++)
295
start_bits[c] |= ~cd->cbits[c+cbit_word];
299
for (c = 0; c < 32; c++)
300
start_bits[c] |= cd->cbits[c+cbit_word];
307
/* Character class where all the information is in a bit map: set the
308
bits and either carry on or not, according to the repeat count. If it was
309
a negative class, and we are operating with UTF-8 characters, any byte
310
with a value >= 0xc4 is a potentially valid starter because it starts a
311
character with a value > 255. */
316
start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
317
memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
325
/* In UTF-8 mode, the bits in a bit map correspond to character
326
values, not to byte values. However, the bit map we are constructing is
327
for byte values. So we have to do a conversion for characters whose
328
value is > 127. In fact, there are only two possible starting bytes for
329
characters in the range 128 - 255. */
333
for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
334
for (c = 128; c < 256; c++)
336
if ((tcode[c/8] && (1 << (c&7))) != 0)
338
int d = (c >> 6) | 0xc0; /* Set bit for this starter */
339
start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
340
c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
345
/* In non-UTF-8 mode, the two bit maps are completely compatible. */
349
for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
352
/* Advance past the bit map, and act on what follows */
366
if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
367
else try_next = FALSE;
375
break; /* End of bitmap class handling */
377
} /* End of switch */
378
} /* End of try_next loop */
380
code += GET(code, 1); /* Advance to next branch */
382
while (*code == OP_ALT);
388
/*************************************************
389
* Study a compiled expression *
390
*************************************************/
392
/* This function is handed a compiled expression that it must study to produce
393
information that will speed up the matching. It returns a pcre_extra block
394
which then gets handed back to pcre_exec().
397
re points to the compiled expression
398
options contains option bits
399
errorptr points to where to place error messages;
400
set NULL unless error
402
Returns: pointer to a pcre_extra block, with study_data filled in and the
403
appropriate flag set;
404
NULL on error or if no optimization possible
408
pcre_study(const pcre *external_re, int options, const char **errorptr)
410
uschar start_bits[32];
412
pcre_study_data *study;
413
const uschar *tables;
414
const real_pcre *re = (const real_pcre *)external_re;
415
uschar *code = (uschar *)re + re->name_table_offset +
416
(re->name_count * re->name_entry_size);
417
compile_data compile_block;
421
if (re == NULL || re->magic_number != MAGIC_NUMBER)
423
*errorptr = "argument is not a compiled regular expression";
427
if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
429
*errorptr = "unknown or incorrect option bit(s) set";
433
/* For an anchored pattern, or an unanchored pattern that has a first char, or
434
a multiline pattern that matches only at "line starts", no further processing
437
if ((re->options & (PCRE_ANCHORED|PCRE_FIRSTSET|PCRE_STARTLINE)) != 0)
440
/* Set the character tables in the block that is passed around */
444
(void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES, (void*)&tables);
446
compile_block.lcc = tables + lcc_offset;
447
compile_block.fcc = tables + fcc_offset;
448
compile_block.cbits = tables + cbits_offset;
449
compile_block.ctypes = tables + ctypes_offset;
451
/* See if we can find a fixed set of initial characters for the pattern. */
453
memset(start_bits, 0, 32 * sizeof(uschar));
454
if (!set_start_bits(code, start_bits, (re->options & PCRE_CASELESS) != 0,
455
(re->options & PCRE_UTF8) != 0, &compile_block)) return NULL;
457
/* Get a pcre_extra block and a pcre_study_data block. The study data is put in
458
the latter, which is pointed to by the former, which may also get additional
459
data set later by the calling program. At the moment, the size of
460
pcre_study_data is fixed. We nevertheless save it in a field for returning via
461
the pcre_fullinfo() function so that if it becomes variable in the future, we
462
don't have to change that code. */
464
extra = (pcre_extra *)(pcre_malloc)
465
(sizeof(pcre_extra) + sizeof(pcre_study_data));
469
*errorptr = "failed to get memory";
473
study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
474
extra->flags = PCRE_EXTRA_STUDY_DATA;
475
extra->study_data = study;
477
study->size = sizeof(pcre_study_data);
478
study->options = PCRE_STUDY_MAPPED;
479
memcpy(study->start_bits, start_bits, sizeof(start_bits));
added
removed
srclib/pcre/study.c
