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