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