/[pcre]/code/trunk/pcre_study.c
ViewVC logotype

Contents of /code/trunk/pcre_study.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1584 - (show annotations)
Sat Aug 1 09:30:02 2015 UTC (2 days, 5 hours ago) by ph10
File MIME type: text/plain
File size: 48588 byte(s)
Error occurred while calculating annotation data.
Give up on minimum length for overly complex patterns.
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-2012 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 #define SET_BIT(c) start_bits[c/8] |= (1 << (c&7))
52
53 /* Returns from set_start_bits() */
54
55 enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE, SSB_UNKNOWN };
56
57
58
59 /*************************************************
60 * Find the minimum subject length for a group *
61 *************************************************/
62
63 /* Scan a parenthesized group and compute the minimum length of subject that
64 is needed to match it. This is a lower bound; it does not mean there is a
65 string of that length that matches. In UTF8 mode, the result is in characters
66 rather than bytes.
67
68 Arguments:
69 re compiled pattern block
70 code pointer to start of group (the bracket)
71 startcode pointer to start of the whole pattern's code
72 options the compiling options
73 recurses chain of recurse_check to catch mutual recursion
74 countptr pointer to call count (to catch over complexity)
75
76 Returns: the minimum length
77 -1 if \C in UTF-8 mode or (*ACCEPT) was encountered
78 -2 internal error (missing capturing bracket)
79 -3 internal error (opcode not listed)
80 */
81
82 static int
83 find_minlength(const REAL_PCRE *re, const pcre_uchar *code,
84 const pcre_uchar *startcode, int options, recurse_check *recurses,
85 int *countptr)
86 {
87 int length = -1;
88 /* PCRE_UTF16 has the same value as PCRE_UTF8. */
89 BOOL utf = (options & PCRE_UTF8) != 0;
90 BOOL had_recurse = FALSE;
91 recurse_check this_recurse;
92 register int branchlength = 0;
93 register pcre_uchar *cc = (pcre_uchar *)code + 1 + LINK_SIZE;
94
95 if ((*countptr)++ > 1000) return -1; /* too complex */
96
97 if (*code == OP_CBRA || *code == OP_SCBRA ||
98 *code == OP_CBRAPOS || *code == OP_SCBRAPOS) cc += IMM2_SIZE;
99
100 /* Scan along the opcodes for this branch. If we get to the end of the
101 branch, check the length against that of the other branches. */
102
103 for (;;)
104 {
105 int d, min;
106 pcre_uchar *cs, *ce;
107 register pcre_uchar op = *cc;
108
109 switch (op)
110 {
111 case OP_COND:
112 case OP_SCOND:
113
114 /* If there is only one branch in a condition, the implied branch has zero
115 length, so we don't add anything. This covers the DEFINE "condition"
116 automatically. */
117
118 cs = cc + GET(cc, 1);
119 if (*cs != OP_ALT)
120 {
121 cc = cs + 1 + LINK_SIZE;
122 break;
123 }
124
125 /* Otherwise we can fall through and treat it the same as any other
126 subpattern. */
127
128 case OP_CBRA:
129 case OP_SCBRA:
130 case OP_BRA:
131 case OP_SBRA:
132 case OP_CBRAPOS:
133 case OP_SCBRAPOS:
134 case OP_BRAPOS:
135 case OP_SBRAPOS:
136 case OP_ONCE:
137 case OP_ONCE_NC:
138 d = find_minlength(re, cc, startcode, options, recurses, countptr);
139 if (d < 0) return d;
140 branchlength += d;
141 do cc += GET(cc, 1); while (*cc == OP_ALT);
142 cc += 1 + LINK_SIZE;
143 break;
144
145 /* ACCEPT makes things far too complicated; we have to give up. */
146
147 case OP_ACCEPT:
148 case OP_ASSERT_ACCEPT:
149 return -1;
150
151 /* Reached end of a branch; if it's a ket it is the end of a nested
152 call. If it's ALT it is an alternation in a nested call. If it is END it's
153 the end of the outer call. All can be handled by the same code. If an
154 ACCEPT was previously encountered, use the length that was in force at that
155 time, and pass back the shortest ACCEPT length. */
156
157 case OP_ALT:
158 case OP_KET:
159 case OP_KETRMAX:
160 case OP_KETRMIN:
161 case OP_KETRPOS:
162 case OP_END:
163 if (length < 0 || (!had_recurse && branchlength < length))
164 length = branchlength;
165 if (op != OP_ALT) return length;
166 cc += 1 + LINK_SIZE;
167 branchlength = 0;
168 had_recurse = FALSE;
169 break;
170
171 /* Skip over assertive subpatterns */
172
173 case OP_ASSERT:
174 case OP_ASSERT_NOT:
175 case OP_ASSERTBACK:
176 case OP_ASSERTBACK_NOT:
177 do cc += GET(cc, 1); while (*cc == OP_ALT);
178 /* Fall through */
179
180 /* Skip over things that don't match chars */
181
182 case OP_REVERSE:
183 case OP_CREF:
184 case OP_DNCREF:
185 case OP_RREF:
186 case OP_DNRREF:
187 case OP_DEF:
188 case OP_CALLOUT:
189 case OP_SOD:
190 case OP_SOM:
191 case OP_EOD:
192 case OP_EODN:
193 case OP_CIRC:
194 case OP_CIRCM:
195 case OP_DOLL:
196 case OP_DOLLM:
197 case OP_NOT_WORD_BOUNDARY:
198 case OP_WORD_BOUNDARY:
199 cc += PRIV(OP_lengths)[*cc];
200 break;
201
202 /* Skip over a subpattern that has a {0} or {0,x} quantifier */
203
204 case OP_BRAZERO:
205 case OP_BRAMINZERO:
206 case OP_BRAPOSZERO:
207 case OP_SKIPZERO:
208 cc += PRIV(OP_lengths)[*cc];
209 do cc += GET(cc, 1); while (*cc == OP_ALT);
210 cc += 1 + LINK_SIZE;
211 break;
212
213 /* Handle literal characters and + repetitions */
214
215 case OP_CHAR:
216 case OP_CHARI:
217 case OP_NOT:
218 case OP_NOTI:
219 case OP_PLUS:
220 case OP_PLUSI:
221 case OP_MINPLUS:
222 case OP_MINPLUSI:
223 case OP_POSPLUS:
224 case OP_POSPLUSI:
225 case OP_NOTPLUS:
226 case OP_NOTPLUSI:
227 case OP_NOTMINPLUS:
228 case OP_NOTMINPLUSI:
229 case OP_NOTPOSPLUS:
230 case OP_NOTPOSPLUSI:
231 branchlength++;
232 cc += 2;
233 #ifdef SUPPORT_UTF
234 if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
235 #endif
236 break;
237
238 case OP_TYPEPLUS:
239 case OP_TYPEMINPLUS:
240 case OP_TYPEPOSPLUS:
241 branchlength++;
242 cc += (cc[1] == OP_PROP || cc[1] == OP_NOTPROP)? 4 : 2;
243 break;
244
245 /* Handle exact repetitions. The count is already in characters, but we
246 need to skip over a multibyte character in UTF8 mode. */
247
248 case OP_EXACT:
249 case OP_EXACTI:
250 case OP_NOTEXACT:
251 case OP_NOTEXACTI:
252 branchlength += GET2(cc,1);
253 cc += 2 + IMM2_SIZE;
254 #ifdef SUPPORT_UTF
255 if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
256 #endif
257 break;
258
259 case OP_TYPEEXACT:
260 branchlength += GET2(cc,1);
261 cc += 2 + IMM2_SIZE + ((cc[1 + IMM2_SIZE] == OP_PROP
262 || cc[1 + IMM2_SIZE] == OP_NOTPROP)? 2 : 0);
263 break;
264
265 /* Handle single-char non-literal matchers */
266
267 case OP_PROP:
268 case OP_NOTPROP:
269 cc += 2;
270 /* Fall through */
271
272 case OP_NOT_DIGIT:
273 case OP_DIGIT:
274 case OP_NOT_WHITESPACE:
275 case OP_WHITESPACE:
276 case OP_NOT_WORDCHAR:
277 case OP_WORDCHAR:
278 case OP_ANY:
279 case OP_ALLANY:
280 case OP_EXTUNI:
281 case OP_HSPACE:
282 case OP_NOT_HSPACE:
283 case OP_VSPACE:
284 case OP_NOT_VSPACE:
285 branchlength++;
286 cc++;
287 break;
288
289 /* "Any newline" might match two characters, but it also might match just
290 one. */
291
292 case OP_ANYNL:
293 branchlength += 1;
294 cc++;
295 break;
296
297 /* The single-byte matcher means we can't proceed in UTF-8 mode. (In
298 non-UTF-8 mode \C will actually be turned into OP_ALLANY, so won't ever
299 appear, but leave the code, just in case.) */
300
301 case OP_ANYBYTE:
302 #ifdef SUPPORT_UTF
303 if (utf) return -1;
304 #endif
305 branchlength++;
306 cc++;
307 break;
308
309 /* For repeated character types, we have to test for \p and \P, which have
310 an extra two bytes of parameters. */
311
312 case OP_TYPESTAR:
313 case OP_TYPEMINSTAR:
314 case OP_TYPEQUERY:
315 case OP_TYPEMINQUERY:
316 case OP_TYPEPOSSTAR:
317 case OP_TYPEPOSQUERY:
318 if (cc[1] == OP_PROP || cc[1] == OP_NOTPROP) cc += 2;
319 cc += PRIV(OP_lengths)[op];
320 break;
321
322 case OP_TYPEUPTO:
323 case OP_TYPEMINUPTO:
324 case OP_TYPEPOSUPTO:
325 if (cc[1 + IMM2_SIZE] == OP_PROP
326 || cc[1 + IMM2_SIZE] == OP_NOTPROP) cc += 2;
327 cc += PRIV(OP_lengths)[op];
328 break;
329
330 /* Check a class for variable quantification */
331
332 case OP_CLASS:
333 case OP_NCLASS:
334 #if defined SUPPORT_UTF || defined COMPILE_PCRE16 || defined COMPILE_PCRE32
335 case OP_XCLASS:
336 /* The original code caused an unsigned overflow in 64 bit systems,
337 so now we use a conditional statement. */
338 if (op == OP_XCLASS)
339 cc += GET(cc, 1);
340 else
341 cc += PRIV(OP_lengths)[OP_CLASS];
342 #else
343 cc += PRIV(OP_lengths)[OP_CLASS];
344 #endif
345
346 switch (*cc)
347 {
348 case OP_CRPLUS:
349 case OP_CRMINPLUS:
350 case OP_CRPOSPLUS:
351 branchlength++;
352 /* Fall through */
353
354 case OP_CRSTAR:
355 case OP_CRMINSTAR:
356 case OP_CRQUERY:
357 case OP_CRMINQUERY:
358 case OP_CRPOSSTAR:
359 case OP_CRPOSQUERY:
360 cc++;
361 break;
362
363 case OP_CRRANGE:
364 case OP_CRMINRANGE:
365 case OP_CRPOSRANGE:
366 branchlength += GET2(cc,1);
367 cc += 1 + 2 * IMM2_SIZE;
368 break;
369
370 default:
371 branchlength++;
372 break;
373 }
374 break;
375
376 /* Backreferences and subroutine calls are treated in the same way: we find
377 the minimum length for the subpattern. A recursion, however, causes an
378 a flag to be set that causes the length of this branch to be ignored. The
379 logic is that a recursion can only make sense if there is another
380 alternation that stops the recursing. That will provide the minimum length
381 (when no recursion happens). A backreference within the group that it is
382 referencing behaves in the same way.
383
384 If PCRE_JAVASCRIPT_COMPAT is set, a backreference to an unset bracket
385 matches an empty string (by default it causes a matching failure), so in
386 that case we must set the minimum length to zero. */
387
388 case OP_DNREF: /* Duplicate named pattern back reference */
389 case OP_DNREFI:
390 if ((options & PCRE_JAVASCRIPT_COMPAT) == 0)
391 {
392 int count = GET2(cc, 1+IMM2_SIZE);
393 pcre_uchar *slot = (pcre_uchar *)re +
394 re->name_table_offset + GET2(cc, 1) * re->name_entry_size;
395 d = INT_MAX;
396 while (count-- > 0)
397 {
398 ce = cs = (pcre_uchar *)PRIV(find_bracket)(startcode, utf, GET2(slot, 0));
399 if (cs == NULL) return -2;
400 do ce += GET(ce, 1); while (*ce == OP_ALT);
401 if (cc > cs && cc < ce) /* Simple recursion */
402 {
403 d = 0;
404 had_recurse = TRUE;
405 break;
406 }
407 else
408 {
409 recurse_check *r = recurses;
410 for (r = recurses; r != NULL; r = r->prev) if (r->group == cs) break;
411 if (r != NULL) /* Mutual recursion */
412 {
413 d = 0;
414 had_recurse = TRUE;
415 break;
416 }
417 else
418 {
419 int dd;
420 this_recurse.prev = recurses;
421 this_recurse.group = cs;
422 dd = find_minlength(re, cs, startcode, options, &this_recurse,
423 countptr);
424 if (dd < d) d = dd;
425 }
426 }
427 slot += re->name_entry_size;
428 }
429 }
430 else d = 0;
431 cc += 1 + 2*IMM2_SIZE;
432 goto REPEAT_BACK_REFERENCE;
433
434 case OP_REF: /* Single back reference */
435 case OP_REFI:
436 if ((options & PCRE_JAVASCRIPT_COMPAT) == 0)
437 {
438 ce = cs = (pcre_uchar *)PRIV(find_bracket)(startcode, utf, GET2(cc, 1));
439 if (cs == NULL) return -2;
440 do ce += GET(ce, 1); while (*ce == OP_ALT);
441 if (cc > cs && cc < ce) /* Simple recursion */
442 {
443 d = 0;
444 had_recurse = TRUE;
445 }
446 else
447 {
448 recurse_check *r = recurses;
449 for (r = recurses; r != NULL; r = r->prev) if (r->group == cs) break;
450 if (r != NULL) /* Mutual recursion */
451 {
452 d = 0;
453 had_recurse = TRUE;
454 }
455 else
456 {
457 this_recurse.prev = recurses;
458 this_recurse.group = cs;
459 d = find_minlength(re, cs, startcode, options, &this_recurse,
460 countptr);
461 }
462 }
463 }
464 else d = 0;
465 cc += 1 + IMM2_SIZE;
466
467 /* Handle repeated back references */
468
469 REPEAT_BACK_REFERENCE:
470 switch (*cc)
471 {
472 case OP_CRSTAR:
473 case OP_CRMINSTAR:
474 case OP_CRQUERY:
475 case OP_CRMINQUERY:
476 case OP_CRPOSSTAR:
477 case OP_CRPOSQUERY:
478 min = 0;
479 cc++;
480 break;
481
482 case OP_CRPLUS:
483 case OP_CRMINPLUS:
484 case OP_CRPOSPLUS:
485 min = 1;
486 cc++;
487 break;
488
489 case OP_CRRANGE:
490 case OP_CRMINRANGE:
491 case OP_CRPOSRANGE:
492 min = GET2(cc, 1);
493 cc += 1 + 2 * IMM2_SIZE;
494 break;
495
496 default:
497 min = 1;
498 break;
499 }
500
501 branchlength += min * d;
502 break;
503
504 /* We can easily detect direct recursion, but not mutual recursion. This is
505 caught by a recursion depth count. */
506
507 case OP_RECURSE:
508 cs = ce = (pcre_uchar *)startcode + GET(cc, 1);
509 do ce += GET(ce, 1); while (*ce == OP_ALT);
510 if (cc > cs && cc < ce) /* Simple recursion */
511 had_recurse = TRUE;
512 else
513 {
514 recurse_check *r = recurses;
515 for (r = recurses; r != NULL; r = r->prev) if (r->group == cs) break;
516 if (r != NULL) /* Mutual recursion */
517 had_recurse = TRUE;
518 else
519 {
520 this_recurse.prev = recurses;
521 this_recurse.group = cs;
522 branchlength += find_minlength(re, cs, startcode, options,
523 &this_recurse, countptr);
524 }
525 }
526 cc += 1 + LINK_SIZE;
527 break;
528
529 /* Anything else does not or need not match a character. We can get the
530 item's length from the table, but for those that can match zero occurrences
531 of a character, we must take special action for UTF-8 characters. As it
532 happens, the "NOT" versions of these opcodes are used at present only for
533 ASCII characters, so they could be omitted from this list. However, in
534 future that may change, so we include them here so as not to leave a
535 gotcha for a future maintainer. */
536
537 case OP_UPTO:
538 case OP_UPTOI:
539 case OP_NOTUPTO:
540 case OP_NOTUPTOI:
541 case OP_MINUPTO:
542 case OP_MINUPTOI:
543 case OP_NOTMINUPTO:
544 case OP_NOTMINUPTOI:
545 case OP_POSUPTO:
546 case OP_POSUPTOI:
547 case OP_NOTPOSUPTO:
548 case OP_NOTPOSUPTOI:
549
550 case OP_STAR:
551 case OP_STARI:
552 case OP_NOTSTAR:
553 case OP_NOTSTARI:
554 case OP_MINSTAR:
555 case OP_MINSTARI:
556 case OP_NOTMINSTAR:
557 case OP_NOTMINSTARI:
558 case OP_POSSTAR:
559 case OP_POSSTARI:
560 case OP_NOTPOSSTAR:
561 case OP_NOTPOSSTARI:
562
563 case OP_QUERY:
564 case OP_QUERYI:
565 case OP_NOTQUERY:
566 case OP_NOTQUERYI:
567 case OP_MINQUERY:
568 case OP_MINQUERYI:
569 case OP_NOTMINQUERY:
570 case OP_NOTMINQUERYI:
571 case OP_POSQUERY:
572 case OP_POSQUERYI:
573 case OP_NOTPOSQUERY:
574 case OP_NOTPOSQUERYI:
575
576 cc += PRIV(OP_lengths)[op];
577 #ifdef SUPPORT_UTF
578 if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
579 #endif
580 break;
581
582 /* Skip these, but we need to add in the name length. */
583
584 case OP_MARK:
585 case OP_PRUNE_ARG:
586 case OP_SKIP_ARG:
587 case OP_THEN_ARG:
588 cc += PRIV(OP_lengths)[op] + cc[1];
589 break;
590
591 /* The remaining opcodes are just skipped over. */
592
593 case OP_CLOSE:
594 case OP_COMMIT:
595 case OP_FAIL:
596 case OP_PRUNE:
597 case OP_SET_SOM:
598 case OP_SKIP:
599 case OP_THEN:
600 cc += PRIV(OP_lengths)[op];
601 break;
602
603 /* This should not occur: we list all opcodes explicitly so that when
604 new ones get added they are properly considered. */
605
606 default:
607 return -3;
608 }
609 }
610 /* Control never gets here */
611 }
612
613
614
615 /*************************************************
616 * Set a bit and maybe its alternate case *
617 *************************************************/
618
619 /* Given a character, set its first byte's bit in the table, and also the
620 corresponding bit for the other version of a letter if we are caseless. In
621 UTF-8 mode, for characters greater than 127, we can only do the caseless thing
622 when Unicode property support is available.
623
624 Arguments:
625 start_bits points to the bit map
626 p points to the character
627 caseless the caseless flag
628 cd the block with char table pointers
629 utf TRUE for UTF-8 / UTF-16 / UTF-32 mode
630
631 Returns: pointer after the character
632 */
633
634 static const pcre_uchar *
635 set_table_bit(pcre_uint8 *start_bits, const pcre_uchar *p, BOOL caseless,
636 compile_data *cd, BOOL utf)
637 {
638 pcre_uint32 c = *p;
639
640 #ifdef COMPILE_PCRE8
641 SET_BIT(c);
642
643 #ifdef SUPPORT_UTF
644 if (utf && c > 127)
645 {
646 GETCHARINC(c, p);
647 #ifdef SUPPORT_UCP
648 if (caseless)
649 {
650 pcre_uchar buff[6];
651 c = UCD_OTHERCASE(c);
652 (void)PRIV(ord2utf)(c, buff);
653 SET_BIT(buff[0]);
654 }
655 #endif /* Not SUPPORT_UCP */
656 return p;
657 }
658 #else /* Not SUPPORT_UTF */
659 (void)(utf); /* Stops warning for unused parameter */
660 #endif /* SUPPORT_UTF */
661
662 /* Not UTF-8 mode, or character is less than 127. */
663
664 if (caseless && (cd->ctypes[c] & ctype_letter) != 0) SET_BIT(cd->fcc[c]);
665 return p + 1;
666 #endif /* COMPILE_PCRE8 */
667
668 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
669 if (c > 0xff)
670 {
671 c = 0xff;
672 caseless = FALSE;
673 }
674 SET_BIT(c);
675
676 #ifdef SUPPORT_UTF
677 if (utf && c > 127)
678 {
679 GETCHARINC(c, p);
680 #ifdef SUPPORT_UCP
681 if (caseless)
682 {
683 c = UCD_OTHERCASE(c);
684 if (c > 0xff)
685 c = 0xff;
686 SET_BIT(c);
687 }
688 #endif /* SUPPORT_UCP */
689 return p;
690 }
691 #else /* Not SUPPORT_UTF */
692 (void)(utf); /* Stops warning for unused parameter */
693 #endif /* SUPPORT_UTF */
694
695 if (caseless && (cd->ctypes[c] & ctype_letter) != 0) SET_BIT(cd->fcc[c]);
696 return p + 1;
697 #endif
698 }
699
700
701
702 /*************************************************
703 * Set bits for a positive character type *
704 *************************************************/
705
706 /* This function sets starting bits for a character type. In UTF-8 mode, we can
707 only do a direct setting for bytes less than 128, as otherwise there can be
708 confusion with bytes in the middle of UTF-8 characters. In a "traditional"
709 environment, the tables will only recognize ASCII characters anyway, but in at
710 least one Windows environment, some higher bytes bits were set in the tables.
711 So we deal with that case by considering the UTF-8 encoding.
712
713 Arguments:
714 start_bits the starting bitmap
715 cbit type the type of character wanted
716 table_limit 32 for non-UTF-8; 16 for UTF-8
717 cd the block with char table pointers
718
719 Returns: nothing
720 */
721
722 static void
723 set_type_bits(pcre_uint8 *start_bits, int cbit_type, unsigned int table_limit,
724 compile_data *cd)
725 {
726 register pcre_uint32 c;
727 for (c = 0; c < table_limit; c++) start_bits[c] |= cd->cbits[c+cbit_type];
728 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
729 if (table_limit == 32) return;
730 for (c = 128; c < 256; c++)
731 {
732 if ((cd->cbits[c/8] & (1 << (c&7))) != 0)
733 {
734 pcre_uchar buff[6];
735 (void)PRIV(ord2utf)(c, buff);
736 SET_BIT(buff[0]);
737 }
738 }
739 #endif
740 }
741
742
743 /*************************************************
744 * Set bits for a negative character type *
745 *************************************************/
746
747 /* This function sets starting bits for a negative character type such as \D.
748 In UTF-8 mode, we can only do a direct setting for bytes less than 128, as
749 otherwise there can be confusion with bytes in the middle of UTF-8 characters.
750 Unlike in the positive case, where we can set appropriate starting bits for
751 specific high-valued UTF-8 characters, in this case we have to set the bits for
752 all high-valued characters. The lowest is 0xc2, but we overkill by starting at
753 0xc0 (192) for simplicity.
754
755 Arguments:
756 start_bits the starting bitmap
757 cbit type the type of character wanted
758 table_limit 32 for non-UTF-8; 16 for UTF-8
759 cd the block with char table pointers
760
761 Returns: nothing
762 */
763
764 static void
765 set_nottype_bits(pcre_uint8 *start_bits, int cbit_type, unsigned int table_limit,
766 compile_data *cd)
767 {
768 register pcre_uint32 c;
769 for (c = 0; c < table_limit; c++) start_bits[c] |= ~cd->cbits[c+cbit_type];
770 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
771 if (table_limit != 32) for (c = 24; c < 32; c++) start_bits[c] = 0xff;
772 #endif
773 }
774
775
776
777 /*************************************************
778 * Create bitmap of starting bytes *
779 *************************************************/
780
781 /* This function scans a compiled unanchored expression recursively and
782 attempts to build a bitmap of the set of possible starting bytes. As time goes
783 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
784 useful for parenthesized groups in patterns such as (a*)b where the group
785 provides some optional starting bytes but scanning must continue at the outer
786 level to find at least one mandatory byte. At the outermost level, this
787 function fails unless the result is SSB_DONE.
788
789 Arguments:
790 code points to an expression
791 start_bits points to a 32-byte table, initialized to 0
792 utf TRUE if in UTF-8 / UTF-16 / UTF-32 mode
793 cd the block with char table pointers
794
795 Returns: SSB_FAIL => Failed to find any starting bytes
796 SSB_DONE => Found mandatory starting bytes
797 SSB_CONTINUE => Found optional starting bytes
798 SSB_UNKNOWN => Hit an unrecognized opcode
799 */
800
801 static int
802 set_start_bits(const pcre_uchar *code, pcre_uint8 *start_bits, BOOL utf,
803 compile_data *cd)
804 {
805 register pcre_uint32 c;
806 int yield = SSB_DONE;
807 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
808 int table_limit = utf? 16:32;
809 #else
810 int table_limit = 32;
811 #endif
812
813 #if 0
814 /* ========================================================================= */
815 /* The following comment and code was inserted in January 1999. In May 2006,
816 when it was observed to cause compiler warnings about unused values, I took it
817 out again. If anybody is still using OS/2, they will have to put it back
818 manually. */
819
820 /* This next statement and the later reference to dummy are here in order to
821 trick the optimizer of the IBM C compiler for OS/2 into generating correct
822 code. Apparently IBM isn't going to fix the problem, and we would rather not
823 disable optimization (in this module it actually makes a big difference, and
824 the pcre module can use all the optimization it can get). */
825
826 volatile int dummy;
827 /* ========================================================================= */
828 #endif
829
830 do
831 {
832 BOOL try_next = TRUE;
833 const pcre_uchar *tcode = code + 1 + LINK_SIZE;
834
835 if (*code == OP_CBRA || *code == OP_SCBRA ||
836 *code == OP_CBRAPOS || *code == OP_SCBRAPOS) tcode += IMM2_SIZE;
837
838 while (try_next) /* Loop for items in this branch */
839 {
840 int rc;
841
842 switch(*tcode)
843 {
844 /* If we reach something we don't understand, it means a new opcode has
845 been created that hasn't been added to this code. Hopefully this problem
846 will be discovered during testing. */
847
848 default:
849 return SSB_UNKNOWN;
850
851 /* Fail for a valid opcode that implies no starting bits. */
852
853 case OP_ACCEPT:
854 case OP_ASSERT_ACCEPT:
855 case OP_ALLANY:
856 case OP_ANY:
857 case OP_ANYBYTE:
858 case OP_CIRC:
859 case OP_CIRCM:
860 case OP_CLOSE:
861 case OP_COMMIT:
862 case OP_COND:
863 case OP_CREF:
864 case OP_DEF:
865 case OP_DNCREF:
866 case OP_DNREF:
867 case OP_DNREFI:
868 case OP_DNRREF:
869 case OP_DOLL:
870 case OP_DOLLM:
871 case OP_END:
872 case OP_EOD:
873 case OP_EODN:
874 case OP_EXTUNI:
875 case OP_FAIL:
876 case OP_MARK:
877 case OP_NOT:
878 case OP_NOTEXACT:
879 case OP_NOTEXACTI:
880 case OP_NOTI:
881 case OP_NOTMINPLUS:
882 case OP_NOTMINPLUSI:
883 case OP_NOTMINQUERY:
884 case OP_NOTMINQUERYI:
885 case OP_NOTMINSTAR:
886 case OP_NOTMINSTARI:
887 case OP_NOTMINUPTO:
888 case OP_NOTMINUPTOI:
889 case OP_NOTPLUS:
890 case OP_NOTPLUSI:
891 case OP_NOTPOSPLUS:
892 case OP_NOTPOSPLUSI:
893 case OP_NOTPOSQUERY:
894 case OP_NOTPOSQUERYI:
895 case OP_NOTPOSSTAR:
896 case OP_NOTPOSSTARI:
897 case OP_NOTPOSUPTO:
898 case OP_NOTPOSUPTOI:
899 case OP_NOTPROP:
900 case OP_NOTQUERY:
901 case OP_NOTQUERYI:
902 case OP_NOTSTAR:
903 case OP_NOTSTARI:
904 case OP_NOTUPTO:
905 case OP_NOTUPTOI:
906 case OP_NOT_HSPACE:
907 case OP_NOT_VSPACE:
908 case OP_PRUNE:
909 case OP_PRUNE_ARG:
910 case OP_RECURSE:
911 case OP_REF:
912 case OP_REFI:
913 case OP_REVERSE:
914 case OP_RREF:
915 case OP_SCOND:
916 case OP_SET_SOM:
917 case OP_SKIP:
918 case OP_SKIP_ARG:
919 case OP_SOD:
920 case OP_SOM:
921 case OP_THEN:
922 case OP_THEN_ARG:
923 return SSB_FAIL;
924
925 /* A "real" property test implies no starting bits, but the fake property
926 PT_CLIST identifies a list of characters. These lists are short, as they
927 are used for characters with more than one "other case", so there is no
928 point in recognizing them for OP_NOTPROP. */
929
930 case OP_PROP:
931 if (tcode[1] != PT_CLIST) return SSB_FAIL;
932 {
933 const pcre_uint32 *p = PRIV(ucd_caseless_sets) + tcode[2];
934 while ((c = *p++) < NOTACHAR)
935 {
936 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
937 if (utf)
938 {
939 pcre_uchar buff[6];
940 (void)PRIV(ord2utf)(c, buff);
941 c = buff[0];
942 }
943 #endif
944 if (c > 0xff) SET_BIT(0xff); else SET_BIT(c);
945 }
946 }
947 try_next = FALSE;
948 break;
949
950 /* We can ignore word boundary tests. */
951
952 case OP_WORD_BOUNDARY:
953 case OP_NOT_WORD_BOUNDARY:
954 tcode++;
955 break;
956
957 /* If we hit a bracket or a positive lookahead assertion, recurse to set
958 bits from within the subpattern. If it can't find anything, we have to
959 give up. If it finds some mandatory character(s), we are done for this
960 branch. Otherwise, carry on scanning after the subpattern. */
961
962 case OP_BRA:
963 case OP_SBRA:
964 case OP_CBRA:
965 case OP_SCBRA:
966 case OP_BRAPOS:
967 case OP_SBRAPOS:
968 case OP_CBRAPOS:
969 case OP_SCBRAPOS:
970 case OP_ONCE:
971 case OP_ONCE_NC:
972 case OP_ASSERT:
973 rc = set_start_bits(tcode, start_bits, utf, cd);
974 if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
975 if (rc == SSB_DONE) try_next = FALSE; else
976 {
977 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
978 tcode += 1 + LINK_SIZE;
979 }
980 break;
981
982 /* If we hit ALT or KET, it means we haven't found anything mandatory in
983 this branch, though we might have found something optional. For ALT, we
984 continue with the next alternative, but we have to arrange that the final
985 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
986 return SSB_CONTINUE: if this is the top level, that indicates failure,
987 but after a nested subpattern, it causes scanning to continue. */
988
989 case OP_ALT:
990 yield = SSB_CONTINUE;
991 try_next = FALSE;
992 break;
993
994 case OP_KET:
995 case OP_KETRMAX:
996 case OP_KETRMIN:
997 case OP_KETRPOS:
998 return SSB_CONTINUE;
999
1000 /* Skip over callout */
1001
1002 case OP_CALLOUT:
1003 tcode += 2 + 2*LINK_SIZE;
1004 break;
1005
1006 /* Skip over lookbehind and negative lookahead assertions */
1007
1008 case OP_ASSERT_NOT:
1009 case OP_ASSERTBACK:
1010 case OP_ASSERTBACK_NOT:
1011 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
1012 tcode += 1 + LINK_SIZE;
1013 break;
1014
1015 /* BRAZERO does the bracket, but carries on. */
1016
1017 case OP_BRAZERO:
1018 case OP_BRAMINZERO:
1019 case OP_BRAPOSZERO:
1020 rc = set_start_bits(++tcode, start_bits, utf, cd);
1021 if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
1022 /* =========================================================================
1023 See the comment at the head of this function concerning the next line,
1024 which was an old fudge for the benefit of OS/2.
1025 dummy = 1;
1026 ========================================================================= */
1027 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
1028 tcode += 1 + LINK_SIZE;
1029 break;
1030
1031 /* SKIPZERO skips the bracket. */
1032
1033 case OP_SKIPZERO:
1034 tcode++;
1035 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
1036 tcode += 1 + LINK_SIZE;
1037 break;
1038
1039 /* Single-char * or ? sets the bit and tries the next item */
1040
1041 case OP_STAR:
1042 case OP_MINSTAR:
1043 case OP_POSSTAR:
1044 case OP_QUERY:
1045 case OP_MINQUERY:
1046 case OP_POSQUERY:
1047 tcode = set_table_bit(start_bits, tcode + 1, FALSE, cd, utf);
1048 break;
1049
1050 case OP_STARI:
1051 case OP_MINSTARI:
1052 case OP_POSSTARI:
1053 case OP_QUERYI:
1054 case OP_MINQUERYI:
1055 case OP_POSQUERYI:
1056 tcode = set_table_bit(start_bits, tcode + 1, TRUE, cd, utf);
1057 break;
1058
1059 /* Single-char upto sets the bit and tries the next */
1060
1061 case OP_UPTO:
1062 case OP_MINUPTO:
1063 case OP_POSUPTO:
1064 tcode = set_table_bit(start_bits, tcode + 1 + IMM2_SIZE, FALSE, cd, utf);
1065 break;
1066
1067 case OP_UPTOI:
1068 case OP_MINUPTOI:
1069 case OP_POSUPTOI:
1070 tcode = set_table_bit(start_bits, tcode + 1 + IMM2_SIZE, TRUE, cd, utf);
1071 break;
1072
1073 /* At least one single char sets the bit and stops */
1074
1075 case OP_EXACT:
1076 tcode += IMM2_SIZE;
1077 /* Fall through */
1078 case OP_CHAR:
1079 case OP_PLUS:
1080 case OP_MINPLUS:
1081 case OP_POSPLUS:
1082 (void)set_table_bit(start_bits, tcode + 1, FALSE, cd, utf);
1083 try_next = FALSE;
1084 break;
1085
1086 case OP_EXACTI:
1087 tcode += IMM2_SIZE;
1088 /* Fall through */
1089 case OP_CHARI:
1090 case OP_PLUSI:
1091 case OP_MINPLUSI:
1092 case OP_POSPLUSI:
1093 (void)set_table_bit(start_bits, tcode + 1, TRUE, cd, utf);
1094 try_next = FALSE;
1095 break;
1096
1097 /* Special spacing and line-terminating items. These recognize specific
1098 lists of characters. The difference between VSPACE and ANYNL is that the
1099 latter can match the two-character CRLF sequence, but that is not
1100 relevant for finding the first character, so their code here is
1101 identical. */
1102
1103 case OP_HSPACE:
1104 SET_BIT(CHAR_HT);
1105 SET_BIT(CHAR_SPACE);
1106 #ifdef SUPPORT_UTF
1107 if (utf)
1108 {
1109 #ifdef COMPILE_PCRE8
1110 SET_BIT(0xC2); /* For U+00A0 */
1111 SET_BIT(0xE1); /* For U+1680, U+180E */
1112 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
1113 SET_BIT(0xE3); /* For U+3000 */
1114 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1115 SET_BIT(0xA0);
1116 SET_BIT(0xFF); /* For characters > 255 */
1117 #endif /* COMPILE_PCRE[8|16|32] */
1118 }
1119 else
1120 #endif /* SUPPORT_UTF */
1121 {
1122 #ifndef EBCDIC
1123 SET_BIT(0xA0);
1124 #endif /* Not EBCDIC */
1125 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1126 SET_BIT(0xFF); /* For characters > 255 */
1127 #endif /* COMPILE_PCRE[16|32] */
1128 }
1129 try_next = FALSE;
1130 break;
1131
1132 case OP_ANYNL:
1133 case OP_VSPACE:
1134 SET_BIT(CHAR_LF);
1135 SET_BIT(CHAR_VT);
1136 SET_BIT(CHAR_FF);
1137 SET_BIT(CHAR_CR);
1138 #ifdef SUPPORT_UTF
1139 if (utf)
1140 {
1141 #ifdef COMPILE_PCRE8
1142 SET_BIT(0xC2); /* For U+0085 */
1143 SET_BIT(0xE2); /* For U+2028, U+2029 */
1144 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1145 SET_BIT(CHAR_NEL);
1146 SET_BIT(0xFF); /* For characters > 255 */
1147 #endif /* COMPILE_PCRE[8|16|32] */
1148 }
1149 else
1150 #endif /* SUPPORT_UTF */
1151 {
1152 SET_BIT(CHAR_NEL);
1153 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1154 SET_BIT(0xFF); /* For characters > 255 */
1155 #endif
1156 }
1157 try_next = FALSE;
1158 break;
1159
1160 /* Single character types set the bits and stop. Note that if PCRE_UCP
1161 is set, we do not see these op codes because \d etc are converted to
1162 properties. Therefore, these apply in the case when only characters less
1163 than 256 are recognized to match the types. */
1164
1165 case OP_NOT_DIGIT:
1166 set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
1167 try_next = FALSE;
1168 break;
1169
1170 case OP_DIGIT:
1171 set_type_bits(start_bits, cbit_digit, table_limit, cd);
1172 try_next = FALSE;
1173 break;
1174
1175 /* The cbit_space table has vertical tab as whitespace; we no longer
1176 have to play fancy tricks because Perl added VT to its whitespace at
1177 release 5.18. PCRE added it at release 8.34. */
1178
1179 case OP_NOT_WHITESPACE:
1180 set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1181 try_next = FALSE;
1182 break;
1183
1184 case OP_WHITESPACE:
1185 set_type_bits(start_bits, cbit_space, table_limit, cd);
1186 try_next = FALSE;
1187 break;
1188
1189 case OP_NOT_WORDCHAR:
1190 set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1191 try_next = FALSE;
1192 break;
1193
1194 case OP_WORDCHAR:
1195 set_type_bits(start_bits, cbit_word, table_limit, cd);
1196 try_next = FALSE;
1197 break;
1198
1199 /* One or more character type fudges the pointer and restarts, knowing
1200 it will hit a single character type and stop there. */
1201
1202 case OP_TYPEPLUS:
1203 case OP_TYPEMINPLUS:
1204 case OP_TYPEPOSPLUS:
1205 tcode++;
1206 break;
1207
1208 case OP_TYPEEXACT:
1209 tcode += 1 + IMM2_SIZE;
1210 break;
1211
1212 /* Zero or more repeats of character types set the bits and then
1213 try again. */
1214
1215 case OP_TYPEUPTO:
1216 case OP_TYPEMINUPTO:
1217 case OP_TYPEPOSUPTO:
1218 tcode += IMM2_SIZE; /* Fall through */
1219
1220 case OP_TYPESTAR:
1221 case OP_TYPEMINSTAR:
1222 case OP_TYPEPOSSTAR:
1223 case OP_TYPEQUERY:
1224 case OP_TYPEMINQUERY:
1225 case OP_TYPEPOSQUERY:
1226 switch(tcode[1])
1227 {
1228 default:
1229 case OP_ANY:
1230 case OP_ALLANY:
1231 return SSB_FAIL;
1232
1233 case OP_HSPACE:
1234 SET_BIT(CHAR_HT);
1235 SET_BIT(CHAR_SPACE);
1236 #ifdef SUPPORT_UTF
1237 if (utf)
1238 {
1239 #ifdef COMPILE_PCRE8
1240 SET_BIT(0xC2); /* For U+00A0 */
1241 SET_BIT(0xE1); /* For U+1680, U+180E */
1242 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
1243 SET_BIT(0xE3); /* For U+3000 */
1244 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1245 SET_BIT(0xA0);
1246 SET_BIT(0xFF); /* For characters > 255 */
1247 #endif /* COMPILE_PCRE[8|16|32] */
1248 }
1249 else
1250 #endif /* SUPPORT_UTF */
1251 #ifndef EBCDIC
1252 SET_BIT(0xA0);
1253 #endif /* Not EBCDIC */
1254 break;
1255
1256 case OP_ANYNL:
1257 case OP_VSPACE:
1258 SET_BIT(CHAR_LF);
1259 SET_BIT(CHAR_VT);
1260 SET_BIT(CHAR_FF);
1261 SET_BIT(CHAR_CR);
1262 #ifdef SUPPORT_UTF
1263 if (utf)
1264 {
1265 #ifdef COMPILE_PCRE8
1266 SET_BIT(0xC2); /* For U+0085 */
1267 SET_BIT(0xE2); /* For U+2028, U+2029 */
1268 #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1269 SET_BIT(CHAR_NEL);
1270 SET_BIT(0xFF); /* For characters > 255 */
1271 #endif /* COMPILE_PCRE16 */
1272 }
1273 else
1274 #endif /* SUPPORT_UTF */
1275 SET_BIT(CHAR_NEL);
1276 break;
1277
1278 case OP_NOT_DIGIT:
1279 set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
1280 break;
1281
1282 case OP_DIGIT:
1283 set_type_bits(start_bits, cbit_digit, table_limit, cd);
1284 break;
1285
1286 /* The cbit_space table has vertical tab as whitespace; we no longer
1287 have to play fancy tricks because Perl added VT to its whitespace at
1288 release 5.18. PCRE added it at release 8.34. */
1289
1290 case OP_NOT_WHITESPACE:
1291 set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1292 break;
1293
1294 case OP_WHITESPACE:
1295 set_type_bits(start_bits, cbit_space, table_limit, cd);
1296 break;
1297
1298 case OP_NOT_WORDCHAR:
1299 set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1300 break;
1301
1302 case OP_WORDCHAR:
1303 set_type_bits(start_bits, cbit_word, table_limit, cd);
1304 break;
1305 }
1306
1307 tcode += 2;
1308 break;
1309
1310 /* Character class where all the information is in a bit map: set the
1311 bits and either carry on or not, according to the repeat count. If it was
1312 a negative class, and we are operating with UTF-8 characters, any byte
1313 with a value >= 0xc4 is a potentially valid starter because it starts a
1314 character with a value > 255. */
1315
1316 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
1317 case OP_XCLASS:
1318 if ((tcode[1 + LINK_SIZE] & XCL_HASPROP) != 0)
1319 return SSB_FAIL;
1320 /* All bits are set. */
1321 if ((tcode[1 + LINK_SIZE] & XCL_MAP) == 0 && (tcode[1 + LINK_SIZE] & XCL_NOT) != 0)
1322 return SSB_FAIL;
1323 #endif
1324 /* Fall through */
1325
1326 case OP_NCLASS:
1327 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1328 if (utf)
1329 {
1330 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
1331 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
1332 }
1333 #endif
1334 #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1335 SET_BIT(0xFF); /* For characters > 255 */
1336 #endif
1337 /* Fall through */
1338
1339 case OP_CLASS:
1340 {
1341 pcre_uint8 *map;
1342 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
1343 map = NULL;
1344 if (*tcode == OP_XCLASS)
1345 {
1346 if ((tcode[1 + LINK_SIZE] & XCL_MAP) != 0)
1347 map = (pcre_uint8 *)(tcode + 1 + LINK_SIZE + 1);
1348 tcode += GET(tcode, 1);
1349 }
1350 else
1351 #endif
1352 {
1353 tcode++;
1354 map = (pcre_uint8 *)tcode;
1355 tcode += 32 / sizeof(pcre_uchar);
1356 }
1357
1358 /* In UTF-8 mode, the bits in a bit map correspond to character
1359 values, not to byte values. However, the bit map we are constructing is
1360 for byte values. So we have to do a conversion for characters whose
1361 value is > 127. In fact, there are only two possible starting bytes for
1362 characters in the range 128 - 255. */
1363
1364 #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
1365 if (map != NULL)
1366 #endif
1367 {
1368 #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1369 if (utf)
1370 {
1371 for (c = 0; c < 16; c++) start_bits[c] |= map[c];
1372 for (c = 128; c < 256; c++)
1373 {
1374 if ((map[c/8] && (1 << (c&7))) != 0)
1375 {
1376 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
1377 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
1378 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
1379 }
1380 }
1381 }
1382 else
1383 #endif
1384 {
1385 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
1386 for (c = 0; c < 32; c++) start_bits[c] |= map[c];
1387 }
1388 }
1389
1390 /* Advance past the bit map, and act on what follows. For a zero
1391 minimum repeat, continue; otherwise stop processing. */
1392
1393 switch (*tcode)
1394 {
1395 case OP_CRSTAR:
1396 case OP_CRMINSTAR:
1397 case OP_CRQUERY:
1398 case OP_CRMINQUERY:
1399 case OP_CRPOSSTAR:
1400 case OP_CRPOSQUERY:
1401 tcode++;
1402 break;
1403
1404 case OP_CRRANGE:
1405 case OP_CRMINRANGE:
1406 case OP_CRPOSRANGE:
1407 if (GET2(tcode, 1) == 0) tcode += 1 + 2 * IMM2_SIZE;
1408 else try_next = FALSE;
1409 break;
1410
1411 default:
1412 try_next = FALSE;
1413 break;
1414 }
1415 }
1416 break; /* End of bitmap class handling */
1417
1418 } /* End of switch */
1419 } /* End of try_next loop */
1420
1421 code += GET(code, 1); /* Advance to next branch */
1422 }
1423 while (*code == OP_ALT);
1424 return yield;
1425 }
1426
1427
1428
1429
1430
1431 /*************************************************
1432 * Study a compiled expression *
1433 *************************************************/
1434
1435 /* This function is handed a compiled expression that it must study to produce
1436 information that will speed up the matching. It returns a pcre[16]_extra block
1437 which then gets handed back to pcre_exec().
1438
1439 Arguments:
1440 re points to the compiled expression
1441 options contains option bits
1442 errorptr points to where to place error messages;
1443 set NULL unless error
1444
1445 Returns: pointer to a pcre[16]_extra block, with study_data filled in and
1446 the appropriate flags set;
1447 NULL on error or if no optimization possible
1448 */
1449
1450 #if defined COMPILE_PCRE8
1451 PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
1452 pcre_study(const pcre *external_re, int options, const char **errorptr)
1453 #elif defined COMPILE_PCRE16
1454 PCRE_EXP_DEFN pcre16_extra * PCRE_CALL_CONVENTION
1455 pcre16_study(const pcre16 *external_re, int options, const char **errorptr)
1456 #elif defined COMPILE_PCRE32
1457 PCRE_EXP_DEFN pcre32_extra * PCRE_CALL_CONVENTION
1458 pcre32_study(const pcre32 *external_re, int options, const char **errorptr)
1459 #endif
1460 {
1461 int min;
1462 int count = 0;
1463 BOOL bits_set = FALSE;
1464 pcre_uint8 start_bits[32];
1465 PUBL(extra) *extra = NULL;
1466 pcre_study_data *study;
1467 const pcre_uint8 *tables;
1468 pcre_uchar *code;
1469 compile_data compile_block;
1470 const REAL_PCRE *re = (const REAL_PCRE *)external_re;
1471
1472
1473 *errorptr = NULL;
1474
1475 if (re == NULL || re->magic_number != MAGIC_NUMBER)
1476 {
1477 *errorptr = "argument is not a compiled regular expression";
1478 return NULL;
1479 }
1480
1481 if ((re->flags & PCRE_MODE) == 0)
1482 {
1483 #if defined COMPILE_PCRE8
1484 *errorptr = "argument not compiled in 8 bit mode";
1485 #elif defined COMPILE_PCRE16
1486 *errorptr = "argument not compiled in 16 bit mode";
1487 #elif defined COMPILE_PCRE32
1488 *errorptr = "argument not compiled in 32 bit mode";
1489 #endif
1490 return NULL;
1491 }
1492
1493 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
1494 {
1495 *errorptr = "unknown or incorrect option bit(s) set";
1496 return NULL;
1497 }
1498
1499 code = (pcre_uchar *)re + re->name_table_offset +
1500 (re->name_count * re->name_entry_size);
1501
1502 /* For an anchored pattern, or an unanchored pattern that has a first char, or
1503 a multiline pattern that matches only at "line starts", there is no point in
1504 seeking a list of starting bytes. */
1505
1506 if ((re->options & PCRE_ANCHORED) == 0 &&
1507 (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)
1508 {
1509 int rc;
1510
1511 /* Set the character tables in the block that is passed around */
1512
1513 tables = re->tables;
1514
1515 #if defined COMPILE_PCRE8
1516 if (tables == NULL)
1517 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1518 (void *)(&tables));
1519 #elif defined COMPILE_PCRE16
1520 if (tables == NULL)
1521 (void)pcre16_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1522 (void *)(&tables));
1523 #elif defined COMPILE_PCRE32
1524 if (tables == NULL)
1525 (void)pcre32_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1526 (void *)(&tables));
1527 #endif
1528
1529 compile_block.lcc = tables + lcc_offset;
1530 compile_block.fcc = tables + fcc_offset;
1531 compile_block.cbits = tables + cbits_offset;
1532 compile_block.ctypes = tables + ctypes_offset;
1533
1534 /* See if we can find a fixed set of initial characters for the pattern. */
1535
1536 memset(start_bits, 0, 32 * sizeof(pcre_uint8));
1537 rc = set_start_bits(code, start_bits, (re->options & PCRE_UTF8) != 0,
1538 &compile_block);
1539 bits_set = rc == SSB_DONE;
1540 if (rc == SSB_UNKNOWN)
1541 {
1542 *errorptr = "internal error: opcode not recognized";
1543 return NULL;
1544 }
1545 }
1546
1547 /* Find the minimum length of subject string. */
1548
1549 switch(min = find_minlength(re, code, code, re->options, NULL, &count))
1550 {
1551 case -2: *errorptr = "internal error: missing capturing bracket"; return NULL;
1552 case -3: *errorptr = "internal error: opcode not recognized"; return NULL;
1553 default: break;
1554 }
1555
1556 /* If a set of starting bytes has been identified, or if the minimum length is
1557 greater than zero, or if JIT optimization has been requested, or if
1558 PCRE_STUDY_EXTRA_NEEDED is set, get a pcre[16]_extra block and a
1559 pcre_study_data block. The study data is put in the latter, which is pointed to
1560 by the former, which may also get additional data set later by the calling
1561 program. At the moment, the size of pcre_study_data is fixed. We nevertheless
1562 save it in a field for returning via the pcre_fullinfo() function so that if it
1563 becomes variable in the future, we don't have to change that code. */
1564
1565 if (bits_set || min > 0 || (options & (
1566 #ifdef SUPPORT_JIT
1567 PCRE_STUDY_JIT_COMPILE | PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE |
1568 PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE |
1569 #endif
1570 PCRE_STUDY_EXTRA_NEEDED)) != 0)
1571 {
1572 extra = (PUBL(extra) *)(PUBL(malloc))
1573 (sizeof(PUBL(extra)) + sizeof(pcre_study_data));
1574 if (extra == NULL)
1575 {
1576 *errorptr = "failed to get memory";
1577 return NULL;
1578 }
1579
1580 study = (pcre_study_data *)((char *)extra + sizeof(PUBL(extra)));
1581 extra->flags = PCRE_EXTRA_STUDY_DATA;
1582 extra->study_data = study;
1583
1584 study->size = sizeof(pcre_study_data);
1585 study->flags = 0;
1586
1587 /* Set the start bits always, to avoid unset memory errors if the
1588 study data is written to a file, but set the flag only if any of the bits
1589 are set, to save time looking when none are. */
1590
1591 if (bits_set)
1592 {
1593 study->flags |= PCRE_STUDY_MAPPED;
1594 memcpy(study->start_bits, start_bits, sizeof(start_bits));
1595 }
1596 else memset(study->start_bits, 0, 32 * sizeof(pcre_uint8));
1597
1598 #ifdef PCRE_DEBUG
1599 if (bits_set)
1600 {
1601 pcre_uint8 *ptr = start_bits;
1602 int i;
1603
1604 printf("Start bits:\n");
1605 for (i = 0; i < 32; i++)
1606 printf("%3d: %02x%s", i * 8, *ptr++, ((i + 1) & 0x7) != 0? " " : "\n");
1607 }
1608 #endif
1609
1610 /* Always set the minlength value in the block, because the JIT compiler
1611 makes use of it. However, don't set the bit unless the length is greater than
1612 zero - the interpretive pcre_exec() and pcre_dfa_exec() needn't waste time
1613 checking the zero case. */
1614
1615 if (min > 0)
1616 {
1617 study->flags |= PCRE_STUDY_MINLEN;
1618 study->minlength = min;
1619 }
1620 else study->minlength = 0;
1621
1622 /* If JIT support was compiled and requested, attempt the JIT compilation.
1623 If no starting bytes were found, and the minimum length is zero, and JIT
1624 compilation fails, abandon the extra block and return NULL, unless
1625 PCRE_STUDY_EXTRA_NEEDED is set. */
1626
1627 #ifdef SUPPORT_JIT
1628 extra->executable_jit = NULL;
1629 if ((options & PCRE_STUDY_JIT_COMPILE) != 0)
1630 PRIV(jit_compile)(re, extra, JIT_COMPILE);
1631 if ((options & PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE) != 0)
1632 PRIV(jit_compile)(re, extra, JIT_PARTIAL_SOFT_COMPILE);
1633 if ((options & PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE) != 0)
1634 PRIV(jit_compile)(re, extra, JIT_PARTIAL_HARD_COMPILE);
1635
1636 if (study->flags == 0 && (extra->flags & PCRE_EXTRA_EXECUTABLE_JIT) == 0 &&
1637 (options & PCRE_STUDY_EXTRA_NEEDED) == 0)
1638 {
1639 #if defined COMPILE_PCRE8
1640 pcre_free_study(extra);
1641 #elif defined COMPILE_PCRE16
1642 pcre16_free_study(extra);
1643 #elif defined COMPILE_PCRE32
1644 pcre32_free_study(extra);
1645 #endif
1646 extra = NULL;
1647 }
1648 #endif
1649 }
1650
1651 return extra;
1652 }
1653
1654
1655 /*************************************************
1656 * Free the study data *
1657 *************************************************/
1658
1659 /* This function frees the memory that was obtained by pcre_study().
1660
1661 Argument: a pointer to the pcre[16]_extra block
1662 Returns: nothing
1663 */
1664
1665 #if defined COMPILE_PCRE8
1666 PCRE_EXP_DEFN void
1667 pcre_free_study(pcre_extra *extra)
1668 #elif defined COMPILE_PCRE16
1669 PCRE_EXP_DEFN void
1670 pcre16_free_study(pcre16_extra *extra)
1671 #elif defined COMPILE_PCRE32
1672 PCRE_EXP_DEFN void
1673 pcre32_free_study(pcre32_extra *extra)
1674 #endif
1675 {
1676 if (extra == NULL)
1677 return;
1678 #ifdef SUPPORT_JIT
1679 if ((extra->flags & PCRE_EXTRA_EXECUTABLE_JIT) != 0 &&
1680 extra->executable_jit != NULL)
1681 PRIV(jit_free)(extra->executable_jit);
1682 #endif
1683 PUBL(free)(extra);
1684 }
1685
1686 /* End of pcre_study.c */

Properties

Name Value
svn:eol-style native
svn:keywords "Author Date Id Revision Url"

  ViewVC Help
Powered by ViewVC 1.1.5