/[pcre]/code/branches/pcre16/pcre_study.c
ViewVC logotype

Contents of /code/branches/pcre16/pcre_study.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 781 - (show annotations)
Sat Dec 3 07:58:30 2011 UTC (9 years, 4 months ago) by zherczeg
File MIME type: text/plain
File size: 39775 byte(s)
renaming utf8 to utf, JIT compiler update, disallowing invalid utf chars
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-2010 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 int 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_UTF8
228 if (utf && cc[-1] >= 0xc0) cc += PRIV(utf8_table4)[cc[-1] & 0x3f];
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_UTF8
249 if (utf && cc[-1] >= 0xc0) cc += PRIV(utf8_table4)[cc[-1] & 0x3f];
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_UTF8
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_UTF8 || !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_UTF8
490 if (utf && cc[-1] >= 0xc0) cc += PRIV(utf8_table4)[cc[-1] & 0x3f];
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 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 unsigned int c = *p;
551
552 SET_BIT(c);
553
554 #ifdef SUPPORT_UTF8
555 if (utf && c > 127)
556 {
557 GETCHARINC(c, p);
558 #ifdef SUPPORT_UCP
559 if (caseless)
560 {
561 pcre_uchar buff[6];
562 c = UCD_OTHERCASE(c);
563 (void)PRIV(ord2utf)(c, buff);
564 SET_BIT(buff[0]);
565 }
566 #endif
567 return p;
568 }
569 #endif
570
571 /* Not UTF-8 mode, or character is less than 127. */
572
573 if (caseless && (cd->ctypes[c] & ctype_letter) != 0) SET_BIT(cd->fcc[c]);
574 return p + 1;
575 }
576
577
578
579 /*************************************************
580 * Set bits for a positive character type *
581 *************************************************/
582
583 /* This function sets starting bits for a character type. In UTF-8 mode, we can
584 only do a direct setting for bytes less than 128, as otherwise there can be
585 confusion with bytes in the middle of UTF-8 characters. In a "traditional"
586 environment, the tables will only recognize ASCII characters anyway, but in at
587 least one Windows environment, some higher bytes bits were set in the tables.
588 So we deal with that case by considering the UTF-8 encoding.
589
590 Arguments:
591 start_bits the starting bitmap
592 cbit type the type of character wanted
593 table_limit 32 for non-UTF-8; 16 for UTF-8
594 cd the block with char table pointers
595
596 Returns: nothing
597 */
598
599 static void
600 set_type_bits(pcre_uint8 *start_bits, int cbit_type, int table_limit,
601 compile_data *cd)
602 {
603 register int c;
604 for (c = 0; c < table_limit; c++) start_bits[c] |= cd->cbits[c+cbit_type];
605 #ifdef SUPPORT_UTF8
606 if (table_limit == 32) return;
607 for (c = 128; c < 256; c++)
608 {
609 if ((cd->cbits[c/8] & (1 << (c&7))) != 0)
610 {
611 pcre_uchar buff[6];
612 (void)PRIV(ord2utf)(c, buff);
613 SET_BIT(buff[0]);
614 }
615 }
616 #endif
617 }
618
619
620 /*************************************************
621 * Set bits for a negative character type *
622 *************************************************/
623
624 /* This function sets starting bits for a negative character type such as \D.
625 In UTF-8 mode, we can only do a direct setting for bytes less than 128, as
626 otherwise there can be confusion with bytes in the middle of UTF-8 characters.
627 Unlike in the positive case, where we can set appropriate starting bits for
628 specific high-valued UTF-8 characters, in this case we have to set the bits for
629 all high-valued characters. The lowest is 0xc2, but we overkill by starting at
630 0xc0 (192) for simplicity.
631
632 Arguments:
633 start_bits the starting bitmap
634 cbit type the type of character wanted
635 table_limit 32 for non-UTF-8; 16 for UTF-8
636 cd the block with char table pointers
637
638 Returns: nothing
639 */
640
641 static void
642 set_nottype_bits(pcre_uint8 *start_bits, int cbit_type, int table_limit,
643 compile_data *cd)
644 {
645 register int c;
646 for (c = 0; c < table_limit; c++) start_bits[c] |= ~cd->cbits[c+cbit_type];
647 if (table_limit != 32) for (c = 24; c < 32; c++) start_bits[c] = 0xff;
648 }
649
650
651
652 /*************************************************
653 * Create bitmap of starting bytes *
654 *************************************************/
655
656 /* This function scans a compiled unanchored expression recursively and
657 attempts to build a bitmap of the set of possible starting bytes. As time goes
658 by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
659 useful for parenthesized groups in patterns such as (a*)b where the group
660 provides some optional starting bytes but scanning must continue at the outer
661 level to find at least one mandatory byte. At the outermost level, this
662 function fails unless the result is SSB_DONE.
663
664 Arguments:
665 code points to an expression
666 start_bits points to a 32-byte table, initialized to 0
667 utf TRUE if in UTF-8 / UTF-16 mode
668 cd the block with char table pointers
669
670 Returns: SSB_FAIL => Failed to find any starting bytes
671 SSB_DONE => Found mandatory starting bytes
672 SSB_CONTINUE => Found optional starting bytes
673 SSB_UNKNOWN => Hit an unrecognized opcode
674 */
675
676 static int
677 set_start_bits(const pcre_uchar *code, pcre_uint8 *start_bits, BOOL utf,
678 compile_data *cd)
679 {
680 register int c;
681 int yield = SSB_DONE;
682 int table_limit = utf? 16:32;
683
684 #if 0
685 /* ========================================================================= */
686 /* The following comment and code was inserted in January 1999. In May 2006,
687 when it was observed to cause compiler warnings about unused values, I took it
688 out again. If anybody is still using OS/2, they will have to put it back
689 manually. */
690
691 /* This next statement and the later reference to dummy are here in order to
692 trick the optimizer of the IBM C compiler for OS/2 into generating correct
693 code. Apparently IBM isn't going to fix the problem, and we would rather not
694 disable optimization (in this module it actually makes a big difference, and
695 the pcre module can use all the optimization it can get). */
696
697 volatile int dummy;
698 /* ========================================================================= */
699 #endif
700
701 do
702 {
703 BOOL try_next = TRUE;
704 const pcre_uchar *tcode = code + 1 + LINK_SIZE;
705
706 if (*code == OP_CBRA || *code == OP_SCBRA ||
707 *code == OP_CBRAPOS || *code == OP_SCBRAPOS) tcode += IMM2_SIZE;
708
709 while (try_next) /* Loop for items in this branch */
710 {
711 int rc;
712
713 switch(*tcode)
714 {
715 /* If we reach something we don't understand, it means a new opcode has
716 been created that hasn't been added to this code. Hopefully this problem
717 will be discovered during testing. */
718
719 default:
720 return SSB_UNKNOWN;
721
722 /* Fail for a valid opcode that implies no starting bits. */
723
724 case OP_ACCEPT:
725 case OP_ASSERT_ACCEPT:
726 case OP_ALLANY:
727 case OP_ANY:
728 case OP_ANYBYTE:
729 case OP_CIRC:
730 case OP_CIRCM:
731 case OP_CLOSE:
732 case OP_COMMIT:
733 case OP_COND:
734 case OP_CREF:
735 case OP_DEF:
736 case OP_DOLL:
737 case OP_DOLLM:
738 case OP_END:
739 case OP_EOD:
740 case OP_EODN:
741 case OP_EXTUNI:
742 case OP_FAIL:
743 case OP_MARK:
744 case OP_NCREF:
745 case OP_NOT:
746 case OP_NOTEXACT:
747 case OP_NOTEXACTI:
748 case OP_NOTI:
749 case OP_NOTMINPLUS:
750 case OP_NOTMINPLUSI:
751 case OP_NOTMINQUERY:
752 case OP_NOTMINQUERYI:
753 case OP_NOTMINSTAR:
754 case OP_NOTMINSTARI:
755 case OP_NOTMINUPTO:
756 case OP_NOTMINUPTOI:
757 case OP_NOTPLUS:
758 case OP_NOTPLUSI:
759 case OP_NOTPOSPLUS:
760 case OP_NOTPOSPLUSI:
761 case OP_NOTPOSQUERY:
762 case OP_NOTPOSQUERYI:
763 case OP_NOTPOSSTAR:
764 case OP_NOTPOSSTARI:
765 case OP_NOTPOSUPTO:
766 case OP_NOTPOSUPTOI:
767 case OP_NOTPROP:
768 case OP_NOTQUERY:
769 case OP_NOTQUERYI:
770 case OP_NOTSTAR:
771 case OP_NOTSTARI:
772 case OP_NOTUPTO:
773 case OP_NOTUPTOI:
774 case OP_NOT_HSPACE:
775 case OP_NOT_VSPACE:
776 case OP_NRREF:
777 case OP_PROP:
778 case OP_PRUNE:
779 case OP_PRUNE_ARG:
780 case OP_RECURSE:
781 case OP_REF:
782 case OP_REFI:
783 case OP_REVERSE:
784 case OP_RREF:
785 case OP_SCOND:
786 case OP_SET_SOM:
787 case OP_SKIP:
788 case OP_SKIP_ARG:
789 case OP_SOD:
790 case OP_SOM:
791 case OP_THEN:
792 case OP_THEN_ARG:
793 #if defined SUPPORT_UTF8 || !defined COMPILE_PCRE8
794 case OP_XCLASS:
795 #endif
796 return SSB_FAIL;
797
798 /* We can ignore word boundary tests. */
799
800 case OP_WORD_BOUNDARY:
801 case OP_NOT_WORD_BOUNDARY:
802 tcode++;
803 break;
804
805 /* If we hit a bracket or a positive lookahead assertion, recurse to set
806 bits from within the subpattern. If it can't find anything, we have to
807 give up. If it finds some mandatory character(s), we are done for this
808 branch. Otherwise, carry on scanning after the subpattern. */
809
810 case OP_BRA:
811 case OP_SBRA:
812 case OP_CBRA:
813 case OP_SCBRA:
814 case OP_BRAPOS:
815 case OP_SBRAPOS:
816 case OP_CBRAPOS:
817 case OP_SCBRAPOS:
818 case OP_ONCE:
819 case OP_ONCE_NC:
820 case OP_ASSERT:
821 rc = set_start_bits(tcode, start_bits, utf, cd);
822 if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
823 if (rc == SSB_DONE) try_next = FALSE; else
824 {
825 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
826 tcode += 1 + LINK_SIZE;
827 }
828 break;
829
830 /* If we hit ALT or KET, it means we haven't found anything mandatory in
831 this branch, though we might have found something optional. For ALT, we
832 continue with the next alternative, but we have to arrange that the final
833 result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
834 return SSB_CONTINUE: if this is the top level, that indicates failure,
835 but after a nested subpattern, it causes scanning to continue. */
836
837 case OP_ALT:
838 yield = SSB_CONTINUE;
839 try_next = FALSE;
840 break;
841
842 case OP_KET:
843 case OP_KETRMAX:
844 case OP_KETRMIN:
845 case OP_KETRPOS:
846 return SSB_CONTINUE;
847
848 /* Skip over callout */
849
850 case OP_CALLOUT:
851 tcode += 2 + 2*LINK_SIZE;
852 break;
853
854 /* Skip over lookbehind and negative lookahead assertions */
855
856 case OP_ASSERT_NOT:
857 case OP_ASSERTBACK:
858 case OP_ASSERTBACK_NOT:
859 do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
860 tcode += 1 + LINK_SIZE;
861 break;
862
863 /* BRAZERO does the bracket, but carries on. */
864
865 case OP_BRAZERO:
866 case OP_BRAMINZERO:
867 case OP_BRAPOSZERO:
868 rc = set_start_bits(++tcode, start_bits, utf, cd);
869 if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
870 /* =========================================================================
871 See the comment at the head of this function concerning the next line,
872 which was an old fudge for the benefit of OS/2.
873 dummy = 1;
874 ========================================================================= */
875 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
876 tcode += 1 + LINK_SIZE;
877 break;
878
879 /* SKIPZERO skips the bracket. */
880
881 case OP_SKIPZERO:
882 tcode++;
883 do tcode += GET(tcode,1); while (*tcode == OP_ALT);
884 tcode += 1 + LINK_SIZE;
885 break;
886
887 /* Single-char * or ? sets the bit and tries the next item */
888
889 case OP_STAR:
890 case OP_MINSTAR:
891 case OP_POSSTAR:
892 case OP_QUERY:
893 case OP_MINQUERY:
894 case OP_POSQUERY:
895 tcode = set_table_bit(start_bits, tcode + 1, FALSE, cd, utf);
896 break;
897
898 case OP_STARI:
899 case OP_MINSTARI:
900 case OP_POSSTARI:
901 case OP_QUERYI:
902 case OP_MINQUERYI:
903 case OP_POSQUERYI:
904 tcode = set_table_bit(start_bits, tcode + 1, TRUE, cd, utf);
905 break;
906
907 /* Single-char upto sets the bit and tries the next */
908
909 case OP_UPTO:
910 case OP_MINUPTO:
911 case OP_POSUPTO:
912 tcode = set_table_bit(start_bits, tcode + 1 + IMM2_SIZE, FALSE, cd, utf);
913 break;
914
915 case OP_UPTOI:
916 case OP_MINUPTOI:
917 case OP_POSUPTOI:
918 tcode = set_table_bit(start_bits, tcode + 1 + IMM2_SIZE, TRUE, cd, utf);
919 break;
920
921 /* At least one single char sets the bit and stops */
922
923 case OP_EXACT:
924 tcode += IMM2_SIZE;
925 /* Fall through */
926 case OP_CHAR:
927 case OP_PLUS:
928 case OP_MINPLUS:
929 case OP_POSPLUS:
930 (void)set_table_bit(start_bits, tcode + 1, FALSE, cd, utf);
931 try_next = FALSE;
932 break;
933
934 case OP_EXACTI:
935 tcode += IMM2_SIZE;
936 /* Fall through */
937 case OP_CHARI:
938 case OP_PLUSI:
939 case OP_MINPLUSI:
940 case OP_POSPLUSI:
941 (void)set_table_bit(start_bits, tcode + 1, TRUE, cd, utf);
942 try_next = FALSE;
943 break;
944
945 /* Special spacing and line-terminating items. These recognize specific
946 lists of characters. The difference between VSPACE and ANYNL is that the
947 latter can match the two-character CRLF sequence, but that is not
948 relevant for finding the first character, so their code here is
949 identical. */
950
951 case OP_HSPACE:
952 SET_BIT(0x09);
953 SET_BIT(0x20);
954 if (utf)
955 {
956 SET_BIT(0xC2); /* For U+00A0 */
957 SET_BIT(0xE1); /* For U+1680, U+180E */
958 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
959 SET_BIT(0xE3); /* For U+3000 */
960 }
961 else SET_BIT(0xA0);
962 try_next = FALSE;
963 break;
964
965 case OP_ANYNL:
966 case OP_VSPACE:
967 SET_BIT(0x0A);
968 SET_BIT(0x0B);
969 SET_BIT(0x0C);
970 SET_BIT(0x0D);
971 if (utf)
972 {
973 SET_BIT(0xC2); /* For U+0085 */
974 SET_BIT(0xE2); /* For U+2028, U+2029 */
975 }
976 else SET_BIT(0x85);
977 try_next = FALSE;
978 break;
979
980 /* Single character types set the bits and stop. Note that if PCRE_UCP
981 is set, we do not see these op codes because \d etc are converted to
982 properties. Therefore, these apply in the case when only characters less
983 than 256 are recognized to match the types. */
984
985 case OP_NOT_DIGIT:
986 set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
987 try_next = FALSE;
988 break;
989
990 case OP_DIGIT:
991 set_type_bits(start_bits, cbit_digit, table_limit, cd);
992 try_next = FALSE;
993 break;
994
995 /* The cbit_space table has vertical tab as whitespace; we have to
996 ensure it is set as not whitespace. */
997
998 case OP_NOT_WHITESPACE:
999 set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1000 start_bits[1] |= 0x08;
1001 try_next = FALSE;
1002 break;
1003
1004 /* The cbit_space table has vertical tab as whitespace; we have to
1005 not set it from the table. */
1006
1007 case OP_WHITESPACE:
1008 c = start_bits[1]; /* Save in case it was already set */
1009 set_type_bits(start_bits, cbit_space, table_limit, cd);
1010 start_bits[1] = (start_bits[1] & ~0x08) | c;
1011 try_next = FALSE;
1012 break;
1013
1014 case OP_NOT_WORDCHAR:
1015 set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1016 try_next = FALSE;
1017 break;
1018
1019 case OP_WORDCHAR:
1020 set_type_bits(start_bits, cbit_word, table_limit, cd);
1021 try_next = FALSE;
1022 break;
1023
1024 /* One or more character type fudges the pointer and restarts, knowing
1025 it will hit a single character type and stop there. */
1026
1027 case OP_TYPEPLUS:
1028 case OP_TYPEMINPLUS:
1029 case OP_TYPEPOSPLUS:
1030 tcode++;
1031 break;
1032
1033 case OP_TYPEEXACT:
1034 tcode += 1 + IMM2_SIZE;
1035 break;
1036
1037 /* Zero or more repeats of character types set the bits and then
1038 try again. */
1039
1040 case OP_TYPEUPTO:
1041 case OP_TYPEMINUPTO:
1042 case OP_TYPEPOSUPTO:
1043 tcode += IMM2_SIZE; /* Fall through */
1044
1045 case OP_TYPESTAR:
1046 case OP_TYPEMINSTAR:
1047 case OP_TYPEPOSSTAR:
1048 case OP_TYPEQUERY:
1049 case OP_TYPEMINQUERY:
1050 case OP_TYPEPOSQUERY:
1051 switch(tcode[1])
1052 {
1053 default:
1054 case OP_ANY:
1055 case OP_ALLANY:
1056 return SSB_FAIL;
1057
1058 case OP_HSPACE:
1059 SET_BIT(0x09);
1060 SET_BIT(0x20);
1061 if (utf)
1062 {
1063 SET_BIT(0xC2); /* For U+00A0 */
1064 SET_BIT(0xE1); /* For U+1680, U+180E */
1065 SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
1066 SET_BIT(0xE3); /* For U+3000 */
1067 }
1068 else SET_BIT(0xA0);
1069 break;
1070
1071 case OP_ANYNL:
1072 case OP_VSPACE:
1073 SET_BIT(0x0A);
1074 SET_BIT(0x0B);
1075 SET_BIT(0x0C);
1076 SET_BIT(0x0D);
1077 if (utf)
1078 {
1079 SET_BIT(0xC2); /* For U+0085 */
1080 SET_BIT(0xE2); /* For U+2028, U+2029 */
1081 }
1082 else SET_BIT(0x85);
1083 break;
1084
1085 case OP_NOT_DIGIT:
1086 set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
1087 break;
1088
1089 case OP_DIGIT:
1090 set_type_bits(start_bits, cbit_digit, table_limit, cd);
1091 break;
1092
1093 /* The cbit_space table has vertical tab as whitespace; we have to
1094 ensure it gets set as not whitespace. */
1095
1096 case OP_NOT_WHITESPACE:
1097 set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1098 start_bits[1] |= 0x08;
1099 break;
1100
1101 /* The cbit_space table has vertical tab as whitespace; we have to
1102 avoid setting it. */
1103
1104 case OP_WHITESPACE:
1105 c = start_bits[1]; /* Save in case it was already set */
1106 set_type_bits(start_bits, cbit_space, table_limit, cd);
1107 start_bits[1] = (start_bits[1] & ~0x08) | c;
1108 break;
1109
1110 case OP_NOT_WORDCHAR:
1111 set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1112 break;
1113
1114 case OP_WORDCHAR:
1115 set_type_bits(start_bits, cbit_word, table_limit, cd);
1116 break;
1117 }
1118
1119 tcode += 2;
1120 break;
1121
1122 /* Character class where all the information is in a bit map: set the
1123 bits and either carry on or not, according to the repeat count. If it was
1124 a negative class, and we are operating with UTF-8 characters, any byte
1125 with a value >= 0xc4 is a potentially valid starter because it starts a
1126 character with a value > 255. */
1127
1128 case OP_NCLASS:
1129 #ifdef SUPPORT_UTF8
1130 if (utf)
1131 {
1132 start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
1133 memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
1134 }
1135 #endif
1136 /* Fall through */
1137
1138 case OP_CLASS:
1139 {
1140 pcre_uint8 *map;
1141 tcode++;
1142 map = (pcre_uint8 *)tcode;
1143
1144 /* In UTF-8 mode, the bits in a bit map correspond to character
1145 values, not to byte values. However, the bit map we are constructing is
1146 for byte values. So we have to do a conversion for characters whose
1147 value is > 127. In fact, there are only two possible starting bytes for
1148 characters in the range 128 - 255. */
1149
1150 #ifdef SUPPORT_UTF8
1151 if (utf)
1152 {
1153 for (c = 0; c < 16; c++) start_bits[c] |= map[c];
1154 for (c = 128; c < 256; c++)
1155 {
1156 if ((map[c/8] && (1 << (c&7))) != 0)
1157 {
1158 int d = (c >> 6) | 0xc0; /* Set bit for this starter */
1159 start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
1160 c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
1161 }
1162 }
1163 }
1164
1165 /* In non-UTF-8 mode, the two bit maps are completely compatible. */
1166
1167 else
1168 #endif
1169 {
1170 for (c = 0; c < 32; c++) start_bits[c] |= map[c];
1171 }
1172
1173 /* Advance past the bit map, and act on what follows. For a zero
1174 minimum repeat, continue; otherwise stop processing. */
1175
1176 tcode += 32 / sizeof(pcre_uchar);
1177 switch (*tcode)
1178 {
1179 case OP_CRSTAR:
1180 case OP_CRMINSTAR:
1181 case OP_CRQUERY:
1182 case OP_CRMINQUERY:
1183 tcode++;
1184 break;
1185
1186 case OP_CRRANGE:
1187 case OP_CRMINRANGE:
1188 if (GET2(tcode, 1) == 0) tcode += 1 + 2 * IMM2_SIZE;
1189 else try_next = FALSE;
1190 break;
1191
1192 default:
1193 try_next = FALSE;
1194 break;
1195 }
1196 }
1197 break; /* End of bitmap class handling */
1198
1199 } /* End of switch */
1200 } /* End of try_next loop */
1201
1202 code += GET(code, 1); /* Advance to next branch */
1203 }
1204 while (*code == OP_ALT);
1205 return yield;
1206 }
1207
1208
1209
1210
1211
1212 /*************************************************
1213 * Study a compiled expression *
1214 *************************************************/
1215
1216 /* This function is handed a compiled expression that it must study to produce
1217 information that will speed up the matching. It returns a pcre_extra block
1218 which then gets handed back to pcre_exec().
1219
1220 Arguments:
1221 re points to the compiled expression
1222 options contains option bits
1223 errorptr points to where to place error messages;
1224 set NULL unless error
1225
1226 Returns: pointer to a pcre_extra block, with study_data filled in and the
1227 appropriate flags set;
1228 NULL on error or if no optimization possible
1229 */
1230
1231 #ifdef COMPILE_PCRE8
1232 PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
1233 pcre_study(const pcre *external_re, int options, const char **errorptr)
1234 #else
1235 PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
1236 pcre16_study(const pcre *external_re, int options, const char **errorptr)
1237 #endif
1238 {
1239 int min;
1240 BOOL bits_set = FALSE;
1241 pcre_uint8 start_bits[32];
1242 pcre_extra *extra = NULL;
1243 pcre_study_data *study;
1244 const pcre_uint8 *tables;
1245 pcre_uchar *code;
1246 compile_data compile_block;
1247 const real_pcre *re = (const real_pcre *)external_re;
1248
1249 *errorptr = NULL;
1250
1251 if (re == NULL || re->magic_number != MAGIC_NUMBER)
1252 {
1253 *errorptr = "argument is not a compiled regular expression";
1254 return NULL;
1255 }
1256
1257 if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
1258 {
1259 *errorptr = "unknown or incorrect option bit(s) set";
1260 return NULL;
1261 }
1262
1263 code = (pcre_uchar *)re + re->name_table_offset +
1264 (re->name_count * re->name_entry_size);
1265
1266 /* For an anchored pattern, or an unanchored pattern that has a first char, or
1267 a multiline pattern that matches only at "line starts", there is no point in
1268 seeking a list of starting bytes. */
1269
1270 if ((re->options & PCRE_ANCHORED) == 0 &&
1271 (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)
1272 {
1273 int rc;
1274
1275 /* Set the character tables in the block that is passed around */
1276
1277 tables = re->tables;
1278 if (tables == NULL)
1279 (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1280 (void *)(&tables));
1281
1282 compile_block.lcc = tables + lcc_offset;
1283 compile_block.fcc = tables + fcc_offset;
1284 compile_block.cbits = tables + cbits_offset;
1285 compile_block.ctypes = tables + ctypes_offset;
1286
1287 /* See if we can find a fixed set of initial characters for the pattern. */
1288
1289 memset(start_bits, 0, 32 * sizeof(pcre_uint8));
1290 rc = set_start_bits(code, start_bits, (re->options & PCRE_UTF8) != 0,
1291 &compile_block);
1292 bits_set = rc == SSB_DONE;
1293 if (rc == SSB_UNKNOWN)
1294 {
1295 *errorptr = "internal error: opcode not recognized";
1296 return NULL;
1297 }
1298 }
1299
1300 /* Find the minimum length of subject string. */
1301
1302 switch(min = find_minlength(code, code, re->options, 0))
1303 {
1304 case -2: *errorptr = "internal error: missing capturing bracket"; return NULL;
1305 case -3: *errorptr = "internal error: opcode not recognized"; return NULL;
1306 default: break;
1307 }
1308
1309 /* If a set of starting bytes has been identified, or if the minimum length is
1310 greater than zero, or if JIT optimization has been requested, get a pcre_extra
1311 block and a pcre_study_data block. The study data is put in the latter, which
1312 is pointed to by the former, which may also get additional data set later by
1313 the calling program. At the moment, the size of pcre_study_data is fixed. We
1314 nevertheless save it in a field for returning via the pcre_fullinfo() function
1315 so that if it becomes variable in the future, we don't have to change that
1316 code. */
1317
1318 if (bits_set || min > 0
1319 #ifdef SUPPORT_JIT
1320 || (options & PCRE_STUDY_JIT_COMPILE) != 0
1321 #endif
1322 )
1323 {
1324 extra = (pcre_extra *)(pcre_malloc)
1325 (sizeof(pcre_extra) + sizeof(pcre_study_data));
1326 if (extra == NULL)
1327 {
1328 *errorptr = "failed to get memory";
1329 return NULL;
1330 }
1331
1332 study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
1333 extra->flags = PCRE_EXTRA_STUDY_DATA;
1334 extra->study_data = study;
1335
1336 study->size = sizeof(pcre_study_data);
1337 study->flags = 0;
1338
1339 if (bits_set)
1340 {
1341 study->flags |= PCRE_STUDY_MAPPED;
1342 memcpy(study->start_bits, start_bits, sizeof(start_bits));
1343 }
1344
1345 /* Always set the minlength value in the block, because the JIT compiler
1346 makes use of it. However, don't set the bit unless the length is greater than
1347 zero - the interpretive pcre_exec() and pcre_dfa_exec() needn't waste time
1348 checking the zero case. */
1349
1350 if (min > 0)
1351 {
1352 study->flags |= PCRE_STUDY_MINLEN;
1353 study->minlength = min;
1354 }
1355 else study->minlength = 0;
1356
1357 /* If JIT support was compiled and requested, attempt the JIT compilation.
1358 If no starting bytes were found, and the minimum length is zero, and JIT
1359 compilation fails, abandon the extra block and return NULL. */
1360
1361 #ifdef SUPPORT_JIT
1362 extra->executable_jit = NULL;
1363 if ((options & PCRE_STUDY_JIT_COMPILE) != 0) PRIV(jit_compile)(re, extra);
1364 if (study->flags == 0 && (extra->flags & PCRE_EXTRA_EXECUTABLE_JIT) == 0)
1365 {
1366 pcre_free_study(extra);
1367 extra = NULL;
1368 }
1369 #endif
1370 }
1371
1372 return extra;
1373 }
1374
1375
1376 /*************************************************
1377 * Free the study data *
1378 *************************************************/
1379
1380 /* This function frees the memory that was obtained by pcre_study().
1381
1382 Argument: a pointer to the pcre_extra block
1383 Returns: nothing
1384 */
1385
1386 #ifdef COMPILE_PCRE8
1387 PCRE_EXP_DEFN void
1388 pcre_free_study(pcre_extra *extra)
1389 #else
1390 PCRE_EXP_DEFN void
1391 pcre16_free_study(pcre_extra *extra)
1392 #endif
1393 {
1394 #ifdef SUPPORT_JIT
1395 if ((extra->flags & PCRE_EXTRA_EXECUTABLE_JIT) != 0 &&
1396 extra->executable_jit != NULL)
1397 PRIV(jit_free)(extra->executable_jit);
1398 #endif
1399 pcre_free(extra);
1400 }
1401
1402 /* 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