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

Contents of /code/trunk/pcre_study.c

Parent Directory Parent Directory | Revision Log Revision Log


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