Annotation of win32/pcre/pcre_study.c, revision 1.8
1.1 misha 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
1.5 misha 9: Copyright (c) 1997-2012 University of Cambridge
1.1 misha 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:
1.3 misha 51: #define SET_BIT(c) start_bits[c/8] |= (1 << (c&7))
1.1 misha 52:
53: /* Returns from set_start_bits() */
54:
1.5 misha 55: enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE, SSB_UNKNOWN };
1.1 misha 56:
57:
1.3 misha 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:
1.7 moko 69: re compiled pattern block
1.5 misha 70: code pointer to start of group (the bracket)
1.7 moko 71: startcode pointer to start of the whole pattern's code
1.5 misha 72: options the compiling options
1.7 moko 73: recurses chain of recurse_check to catch mutual recursion
1.8 ! moko 74: countptr pointer to call count (to catch over complexity)
1.3 misha 75:
76: Returns: the minimum length
1.5 misha 77: -1 if \C in UTF-8 mode or (*ACCEPT) was encountered
1.3 misha 78: -2 internal error (missing capturing bracket)
1.5 misha 79: -3 internal error (opcode not listed)
1.3 misha 80: */
81:
82: static int
1.7 moko 83: find_minlength(const REAL_PCRE *re, const pcre_uchar *code,
1.8 ! moko 84: const pcre_uchar *startcode, int options, recurse_check *recurses,
! 85: int *countptr)
1.3 misha 86: {
87: int length = -1;
1.5 misha 88: /* PCRE_UTF16 has the same value as PCRE_UTF8. */
89: BOOL utf = (options & PCRE_UTF8) != 0;
1.3 misha 90: BOOL had_recurse = FALSE;
1.7 moko 91: recurse_check this_recurse;
1.3 misha 92: register int branchlength = 0;
1.5 misha 93: register pcre_uchar *cc = (pcre_uchar *)code + 1 + LINK_SIZE;
1.3 misha 94:
1.8 ! moko 95: if ((*countptr)++ > 1000) return -1; /* too complex */
! 96:
1.5 misha 97: if (*code == OP_CBRA || *code == OP_SCBRA ||
98: *code == OP_CBRAPOS || *code == OP_SCBRAPOS) cc += IMM2_SIZE;
1.3 misha 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;
1.5 misha 106: pcre_uchar *cs, *ce;
1.6 misha 107: register pcre_uchar op = *cc;
1.3 misha 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:
1.5 misha 132: case OP_CBRAPOS:
133: case OP_SCBRAPOS:
134: case OP_BRAPOS:
135: case OP_SBRAPOS:
1.3 misha 136: case OP_ONCE:
1.5 misha 137: case OP_ONCE_NC:
1.8 ! moko 138: d = find_minlength(re, cc, startcode, options, recurses, countptr);
1.3 misha 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:
1.5 misha 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:
1.3 misha 151: /* Reached end of a branch; if it's a ket it is the end of a nested
1.5 misha 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. */
1.3 misha 156:
157: case OP_ALT:
158: case OP_KET:
159: case OP_KETRMAX:
160: case OP_KETRMIN:
1.5 misha 161: case OP_KETRPOS:
1.3 misha 162: case OP_END:
163: if (length < 0 || (!had_recurse && branchlength < length))
164: length = branchlength;
1.5 misha 165: if (op != OP_ALT) return length;
1.3 misha 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:
1.7 moko 184: case OP_DNCREF:
1.3 misha 185: case OP_RREF:
1.7 moko 186: case OP_DNRREF:
1.3 misha 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:
1.5 misha 194: case OP_CIRCM:
1.3 misha 195: case OP_DOLL:
1.5 misha 196: case OP_DOLLM:
1.3 misha 197: case OP_NOT_WORD_BOUNDARY:
198: case OP_WORD_BOUNDARY:
1.5 misha 199: cc += PRIV(OP_lengths)[*cc];
1.3 misha 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:
1.5 misha 206: case OP_BRAPOSZERO:
1.3 misha 207: case OP_SKIPZERO:
1.5 misha 208: cc += PRIV(OP_lengths)[*cc];
1.3 misha 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:
1.5 misha 216: case OP_CHARI:
1.3 misha 217: case OP_NOT:
1.5 misha 218: case OP_NOTI:
1.3 misha 219: case OP_PLUS:
1.5 misha 220: case OP_PLUSI:
1.3 misha 221: case OP_MINPLUS:
1.5 misha 222: case OP_MINPLUSI:
1.3 misha 223: case OP_POSPLUS:
1.5 misha 224: case OP_POSPLUSI:
1.3 misha 225: case OP_NOTPLUS:
1.5 misha 226: case OP_NOTPLUSI:
1.3 misha 227: case OP_NOTMINPLUS:
1.5 misha 228: case OP_NOTMINPLUSI:
1.3 misha 229: case OP_NOTPOSPLUS:
1.5 misha 230: case OP_NOTPOSPLUSI:
1.3 misha 231: branchlength++;
232: cc += 2;
1.5 misha 233: #ifdef SUPPORT_UTF
234: if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
1.3 misha 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:
1.5 misha 249: case OP_EXACTI:
1.3 misha 250: case OP_NOTEXACT:
1.5 misha 251: case OP_NOTEXACTI:
1.3 misha 252: branchlength += GET2(cc,1);
1.5 misha 253: cc += 2 + IMM2_SIZE;
254: #ifdef SUPPORT_UTF
255: if (utf && HAS_EXTRALEN(cc[-1])) cc += GET_EXTRALEN(cc[-1]);
1.3 misha 256: #endif
257: break;
258:
259: case OP_TYPEEXACT:
260: branchlength += GET2(cc,1);
1.5 misha 261: cc += 2 + IMM2_SIZE + ((cc[1 + IMM2_SIZE] == OP_PROP
262: || cc[1 + IMM2_SIZE] == OP_NOTPROP)? 2 : 0);
1.3 misha 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:
1.5 misha 289: /* "Any newline" might match two characters, but it also might match just
290: one. */
1.3 misha 291:
292: case OP_ANYNL:
1.5 misha 293: branchlength += 1;
1.3 misha 294: cc++;
295: break;
296:
1.5 misha 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.) */
1.3 misha 300:
301: case OP_ANYBYTE:
1.5 misha 302: #ifdef SUPPORT_UTF
303: if (utf) return -1;
1.3 misha 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;
1.5 misha 319: cc += PRIV(OP_lengths)[op];
1.3 misha 320: break;
321:
322: case OP_TYPEUPTO:
323: case OP_TYPEMINUPTO:
324: case OP_TYPEPOSUPTO:
1.5 misha 325: if (cc[1 + IMM2_SIZE] == OP_PROP
326: || cc[1 + IMM2_SIZE] == OP_NOTPROP) cc += 2;
327: cc += PRIV(OP_lengths)[op];
1.3 misha 328: break;
329:
330: /* Check a class for variable quantification */
331:
332: case OP_CLASS:
333: case OP_NCLASS:
1.6 misha 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
1.5 misha 343: cc += PRIV(OP_lengths)[OP_CLASS];
1.6 misha 344: #endif
1.3 misha 345:
346: switch (*cc)
347: {
348: case OP_CRPLUS:
349: case OP_CRMINPLUS:
1.7 moko 350: case OP_CRPOSPLUS:
1.3 misha 351: branchlength++;
352: /* Fall through */
353:
354: case OP_CRSTAR:
355: case OP_CRMINSTAR:
356: case OP_CRQUERY:
357: case OP_CRMINQUERY:
1.7 moko 358: case OP_CRPOSSTAR:
359: case OP_CRPOSQUERY:
1.3 misha 360: cc++;
361: break;
362:
363: case OP_CRRANGE:
364: case OP_CRMINRANGE:
1.7 moko 365: case OP_CRPOSRANGE:
1.3 misha 366: branchlength += GET2(cc,1);
1.5 misha 367: cc += 1 + 2 * IMM2_SIZE;
1.3 misha 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:
1.7 moko 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;
1.8 ! moko 422: dd = find_minlength(re, cs, startcode, options, &this_recurse,
! 423: countptr);
1.7 moko 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 */
1.5 misha 435: case OP_REFI:
1.3 misha 436: if ((options & PCRE_JAVASCRIPT_COMPAT) == 0)
437: {
1.5 misha 438: ce = cs = (pcre_uchar *)PRIV(find_bracket)(startcode, utf, GET2(cc, 1));
1.3 misha 439: if (cs == NULL) return -2;
440: do ce += GET(ce, 1); while (*ce == OP_ALT);
1.7 moko 441: if (cc > cs && cc < ce) /* Simple recursion */
1.3 misha 442: {
443: d = 0;
444: had_recurse = TRUE;
445: }
1.5 misha 446: else
447: {
1.7 moko 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;
1.8 ! moko 459: d = find_minlength(re, cs, startcode, options, &this_recurse,
! 460: countptr);
1.7 moko 461: }
1.5 misha 462: }
1.3 misha 463: }
464: else d = 0;
1.5 misha 465: cc += 1 + IMM2_SIZE;
1.3 misha 466:
467: /* Handle repeated back references */
468:
1.7 moko 469: REPEAT_BACK_REFERENCE:
1.3 misha 470: switch (*cc)
471: {
472: case OP_CRSTAR:
473: case OP_CRMINSTAR:
474: case OP_CRQUERY:
475: case OP_CRMINQUERY:
1.7 moko 476: case OP_CRPOSSTAR:
477: case OP_CRPOSQUERY:
1.3 misha 478: min = 0;
479: cc++;
480: break;
481:
1.5 misha 482: case OP_CRPLUS:
483: case OP_CRMINPLUS:
1.7 moko 484: case OP_CRPOSPLUS:
1.5 misha 485: min = 1;
486: cc++;
487: break;
488:
1.3 misha 489: case OP_CRRANGE:
490: case OP_CRMINRANGE:
1.7 moko 491: case OP_CRPOSRANGE:
1.3 misha 492: min = GET2(cc, 1);
1.5 misha 493: cc += 1 + 2 * IMM2_SIZE;
1.3 misha 494: break;
495:
496: default:
497: min = 1;
498: break;
499: }
500:
501: branchlength += min * d;
502: break;
503:
1.5 misha 504: /* We can easily detect direct recursion, but not mutual recursion. This is
505: caught by a recursion depth count. */
506:
1.3 misha 507: case OP_RECURSE:
1.5 misha 508: cs = ce = (pcre_uchar *)startcode + GET(cc, 1);
1.3 misha 509: do ce += GET(ce, 1); while (*ce == OP_ALT);
1.7 moko 510: if (cc > cs && cc < ce) /* Simple recursion */
1.3 misha 511: had_recurse = TRUE;
512: else
1.5 misha 513: {
1.7 moko 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,
1.8 ! moko 523: &this_recurse, countptr);
1.7 moko 524: }
1.5 misha 525: }
1.3 misha 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
1.5 misha 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. */
1.3 misha 536:
537: case OP_UPTO:
1.5 misha 538: case OP_UPTOI:
1.3 misha 539: case OP_NOTUPTO:
1.5 misha 540: case OP_NOTUPTOI:
1.3 misha 541: case OP_MINUPTO:
1.5 misha 542: case OP_MINUPTOI:
1.3 misha 543: case OP_NOTMINUPTO:
1.5 misha 544: case OP_NOTMINUPTOI:
1.3 misha 545: case OP_POSUPTO:
1.5 misha 546: case OP_POSUPTOI:
547: case OP_NOTPOSUPTO:
548: case OP_NOTPOSUPTOI:
549:
1.3 misha 550: case OP_STAR:
1.5 misha 551: case OP_STARI:
552: case OP_NOTSTAR:
553: case OP_NOTSTARI:
1.3 misha 554: case OP_MINSTAR:
1.5 misha 555: case OP_MINSTARI:
1.3 misha 556: case OP_NOTMINSTAR:
1.5 misha 557: case OP_NOTMINSTARI:
1.3 misha 558: case OP_POSSTAR:
1.5 misha 559: case OP_POSSTARI:
1.3 misha 560: case OP_NOTPOSSTAR:
1.5 misha 561: case OP_NOTPOSSTARI:
562:
1.3 misha 563: case OP_QUERY:
1.5 misha 564: case OP_QUERYI:
565: case OP_NOTQUERY:
566: case OP_NOTQUERYI:
1.3 misha 567: case OP_MINQUERY:
1.5 misha 568: case OP_MINQUERYI:
1.3 misha 569: case OP_NOTMINQUERY:
1.5 misha 570: case OP_NOTMINQUERYI:
1.3 misha 571: case OP_POSQUERY:
1.5 misha 572: case OP_POSQUERYI:
1.3 misha 573: case OP_NOTPOSQUERY:
1.5 misha 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]);
1.3 misha 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:
1.5 misha 587: case OP_THEN_ARG:
588: cc += PRIV(OP_lengths)[op] + cc[1];
1.4 misha 589: break;
590:
1.5 misha 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];
1.3 misha 601: break;
602:
1.5 misha 603: /* This should not occur: we list all opcodes explicitly so that when
604: new ones get added they are properly considered. */
1.3 misha 605:
606: default:
1.5 misha 607: return -3;
1.3 misha 608: }
609: }
610: /* Control never gets here */
611: }
612:
613:
614:
1.1 misha 615: /*************************************************
616: * Set a bit and maybe its alternate case *
617: *************************************************/
618:
1.3 misha 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.
1.1 misha 623:
624: Arguments:
625: start_bits points to the bit map
1.3 misha 626: p points to the character
1.1 misha 627: caseless the caseless flag
628: cd the block with char table pointers
1.6 misha 629: utf TRUE for UTF-8 / UTF-16 / UTF-32 mode
1.3 misha 630:
631: Returns: pointer after the character
632: */
633:
1.5 misha 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)
1.3 misha 637: {
1.6 misha 638: pcre_uint32 c = *p;
1.3 misha 639:
1.5 misha 640: #ifdef COMPILE_PCRE8
1.3 misha 641: SET_BIT(c);
642:
1.5 misha 643: #ifdef SUPPORT_UTF
644: if (utf && c > 127)
1.3 misha 645: {
646: GETCHARINC(c, p);
647: #ifdef SUPPORT_UCP
648: if (caseless)
649: {
1.5 misha 650: pcre_uchar buff[6];
1.3 misha 651: c = UCD_OTHERCASE(c);
1.5 misha 652: (void)PRIV(ord2utf)(c, buff);
1.3 misha 653: SET_BIT(buff[0]);
654: }
1.6 misha 655: #endif /* Not SUPPORT_UCP */
1.3 misha 656: return p;
657: }
1.6 misha 658: #else /* Not SUPPORT_UTF */
659: (void)(utf); /* Stops warning for unused parameter */
660: #endif /* SUPPORT_UTF */
1.3 misha 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;
1.6 misha 666: #endif /* COMPILE_PCRE8 */
1.5 misha 667:
1.6 misha 668: #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 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: }
1.6 misha 688: #endif /* SUPPORT_UCP */
1.5 misha 689: return p;
690: }
1.6 misha 691: #else /* Not SUPPORT_UTF */
692: (void)(utf); /* Stops warning for unused parameter */
693: #endif /* SUPPORT_UTF */
1.5 misha 694:
695: if (caseless && (cd->ctypes[c] & ctype_letter) != 0) SET_BIT(cd->fcc[c]);
696: return p + 1;
697: #endif
1.3 misha 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
1.6 misha 723: set_type_bits(pcre_uint8 *start_bits, int cbit_type, unsigned int table_limit,
1.3 misha 724: compile_data *cd)
725: {
1.6 misha 726: register pcre_uint32 c;
1.3 misha 727: for (c = 0; c < table_limit; c++) start_bits[c] |= cd->cbits[c+cbit_type];
1.5 misha 728: #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1.3 misha 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: {
1.5 misha 734: pcre_uchar buff[6];
735: (void)PRIV(ord2utf)(c, buff);
1.3 misha 736: SET_BIT(buff[0]);
737: }
738: }
1.5 misha 739: #endif
1.3 misha 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.
1.1 misha 754:
1.3 misha 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
1.1 misha 762: */
763:
764: static void
1.6 misha 765: set_nottype_bits(pcre_uint8 *start_bits, int cbit_type, unsigned int table_limit,
1.3 misha 766: compile_data *cd)
1.1 misha 767: {
1.6 misha 768: register pcre_uint32 c;
1.3 misha 769: for (c = 0; c < table_limit; c++) start_bits[c] |= ~cd->cbits[c+cbit_type];
1.5 misha 770: #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1.3 misha 771: if (table_limit != 32) for (c = 24; c < 32; c++) start_bits[c] = 0xff;
1.5 misha 772: #endif
1.1 misha 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
1.6 misha 792: utf TRUE if in UTF-8 / UTF-16 / UTF-32 mode
1.1 misha 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
1.5 misha 798: SSB_UNKNOWN => Hit an unrecognized opcode
1.1 misha 799: */
800:
801: static int
1.5 misha 802: set_start_bits(const pcre_uchar *code, pcre_uint8 *start_bits, BOOL utf,
803: compile_data *cd)
1.1 misha 804: {
1.6 misha 805: register pcre_uint32 c;
1.1 misha 806: int yield = SSB_DONE;
1.5 misha 807: #if defined SUPPORT_UTF && defined COMPILE_PCRE8
808: int table_limit = utf? 16:32;
809: #else
810: int table_limit = 32;
811: #endif
1.1 misha 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;
1.5 misha 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;
1.1 misha 837:
838: while (try_next) /* Loop for items in this branch */
839: {
840: int rc;
1.5 misha 841:
1.1 misha 842: switch(*tcode)
843: {
1.5 misha 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. */
1.1 misha 847:
848: default:
1.5 misha 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:
1.7 moko 865: case OP_DNCREF:
866: case OP_DNREF:
867: case OP_DNREFI:
868: case OP_DNRREF:
1.5 misha 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:
1.7 moko 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: }
1.5 misha 943: #endif
1.7 moko 944: if (c > 0xff) SET_BIT(0xff); else SET_BIT(c);
945: }
946: }
947: try_next = FALSE;
948: break;
1.1 misha 949:
1.5 misha 950: /* We can ignore word boundary tests. */
951:
952: case OP_WORD_BOUNDARY:
953: case OP_NOT_WORD_BOUNDARY:
954: tcode++;
955: break;
956:
1.1 misha 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:
1.5 misha 966: case OP_BRAPOS:
967: case OP_SBRAPOS:
968: case OP_CBRAPOS:
969: case OP_SCBRAPOS:
1.1 misha 970: case OP_ONCE:
1.5 misha 971: case OP_ONCE_NC:
1.1 misha 972: case OP_ASSERT:
1.5 misha 973: rc = set_start_bits(tcode, start_bits, utf, cd);
974: if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
1.1 misha 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:
1.5 misha 997: case OP_KETRPOS:
1.1 misha 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:
1.5 misha 1019: case OP_BRAPOSZERO:
1020: rc = set_start_bits(++tcode, start_bits, utf, cd);
1021: if (rc == SSB_FAIL || rc == SSB_UNKNOWN) return rc;
1.1 misha 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:
1.2 misha 1034: tcode++;
1.1 misha 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:
1.5 misha 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);
1.1 misha 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:
1.5 misha 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);
1.1 misha 1071: break;
1072:
1073: /* At least one single char sets the bit and stops */
1074:
1.5 misha 1075: case OP_EXACT:
1076: tcode += IMM2_SIZE;
1077: /* Fall through */
1.1 misha 1078: case OP_CHAR:
1079: case OP_PLUS:
1080: case OP_MINPLUS:
1081: case OP_POSPLUS:
1.5 misha 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);
1.3 misha 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:
1.6 misha 1104: SET_BIT(CHAR_HT);
1105: SET_BIT(CHAR_SPACE);
1.5 misha 1106: #ifdef SUPPORT_UTF
1107: if (utf)
1.3 misha 1108: {
1.5 misha 1109: #ifdef COMPILE_PCRE8
1.3 misha 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 */
1.6 misha 1114: #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 1115: SET_BIT(0xA0);
1116: SET_BIT(0xFF); /* For characters > 255 */
1.6 misha 1117: #endif /* COMPILE_PCRE[8|16|32] */
1.5 misha 1118: }
1119: else
1120: #endif /* SUPPORT_UTF */
1121: {
1.6 misha 1122: #ifndef EBCDIC
1.5 misha 1123: SET_BIT(0xA0);
1.6 misha 1124: #endif /* Not EBCDIC */
1125: #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 1126: SET_BIT(0xFF); /* For characters > 255 */
1.6 misha 1127: #endif /* COMPILE_PCRE[16|32] */
1.3 misha 1128: }
1129: try_next = FALSE;
1130: break;
1131:
1132: case OP_ANYNL:
1133: case OP_VSPACE:
1.6 misha 1134: SET_BIT(CHAR_LF);
1135: SET_BIT(CHAR_VT);
1136: SET_BIT(CHAR_FF);
1137: SET_BIT(CHAR_CR);
1.5 misha 1138: #ifdef SUPPORT_UTF
1139: if (utf)
1.3 misha 1140: {
1.5 misha 1141: #ifdef COMPILE_PCRE8
1.3 misha 1142: SET_BIT(0xC2); /* For U+0085 */
1143: SET_BIT(0xE2); /* For U+2028, U+2029 */
1.6 misha 1144: #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1145: SET_BIT(CHAR_NEL);
1.5 misha 1146: SET_BIT(0xFF); /* For characters > 255 */
1.6 misha 1147: #endif /* COMPILE_PCRE[8|16|32] */
1.5 misha 1148: }
1149: else
1150: #endif /* SUPPORT_UTF */
1151: {
1.6 misha 1152: SET_BIT(CHAR_NEL);
1153: #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 1154: SET_BIT(0xFF); /* For characters > 255 */
1155: #endif
1.3 misha 1156: }
1.1 misha 1157: try_next = FALSE;
1158: break;
1159:
1.3 misha 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. */
1.1 misha 1164:
1165: case OP_NOT_DIGIT:
1.3 misha 1166: set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
1.1 misha 1167: try_next = FALSE;
1168: break;
1169:
1170: case OP_DIGIT:
1.3 misha 1171: set_type_bits(start_bits, cbit_digit, table_limit, cd);
1.1 misha 1172: try_next = FALSE;
1173: break;
1174:
1.7 moko 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. */
1.1 misha 1178:
1179: case OP_NOT_WHITESPACE:
1.3 misha 1180: set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1.1 misha 1181: try_next = FALSE;
1182: break;
1183:
1184: case OP_WHITESPACE:
1.3 misha 1185: set_type_bits(start_bits, cbit_space, table_limit, cd);
1.1 misha 1186: try_next = FALSE;
1187: break;
1188:
1189: case OP_NOT_WORDCHAR:
1.3 misha 1190: set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1.1 misha 1191: try_next = FALSE;
1192: break;
1193:
1194: case OP_WORDCHAR:
1.3 misha 1195: set_type_bits(start_bits, cbit_word, table_limit, cd);
1.1 misha 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:
1.3 misha 1204: case OP_TYPEPOSPLUS:
1.1 misha 1205: tcode++;
1206: break;
1207:
1208: case OP_TYPEEXACT:
1.5 misha 1209: tcode += 1 + IMM2_SIZE;
1.1 misha 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:
1.5 misha 1218: tcode += IMM2_SIZE; /* Fall through */
1.1 misha 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: {
1.3 misha 1228: default:
1.1 misha 1229: case OP_ANY:
1230: case OP_ALLANY:
1231: return SSB_FAIL;
1232:
1.3 misha 1233: case OP_HSPACE:
1.6 misha 1234: SET_BIT(CHAR_HT);
1235: SET_BIT(CHAR_SPACE);
1236: #ifdef SUPPORT_UTF
1.5 misha 1237: if (utf)
1.3 misha 1238: {
1.5 misha 1239: #ifdef COMPILE_PCRE8
1.3 misha 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 */
1.6 misha 1244: #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 1245: SET_BIT(0xA0);
1246: SET_BIT(0xFF); /* For characters > 255 */
1.6 misha 1247: #endif /* COMPILE_PCRE[8|16|32] */
1.3 misha 1248: }
1.5 misha 1249: else
1250: #endif /* SUPPORT_UTF */
1.6 misha 1251: #ifndef EBCDIC
1.5 misha 1252: SET_BIT(0xA0);
1.6 misha 1253: #endif /* Not EBCDIC */
1.3 misha 1254: break;
1255:
1256: case OP_ANYNL:
1257: case OP_VSPACE:
1.6 misha 1258: SET_BIT(CHAR_LF);
1259: SET_BIT(CHAR_VT);
1260: SET_BIT(CHAR_FF);
1261: SET_BIT(CHAR_CR);
1262: #ifdef SUPPORT_UTF
1.5 misha 1263: if (utf)
1.3 misha 1264: {
1.5 misha 1265: #ifdef COMPILE_PCRE8
1.3 misha 1266: SET_BIT(0xC2); /* For U+0085 */
1267: SET_BIT(0xE2); /* For U+2028, U+2029 */
1.6 misha 1268: #elif defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1269: SET_BIT(CHAR_NEL);
1.5 misha 1270: SET_BIT(0xFF); /* For characters > 255 */
1.6 misha 1271: #endif /* COMPILE_PCRE16 */
1.3 misha 1272: }
1.5 misha 1273: else
1274: #endif /* SUPPORT_UTF */
1.6 misha 1275: SET_BIT(CHAR_NEL);
1.3 misha 1276: break;
1277:
1.1 misha 1278: case OP_NOT_DIGIT:
1.3 misha 1279: set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
1.1 misha 1280: break;
1281:
1282: case OP_DIGIT:
1.3 misha 1283: set_type_bits(start_bits, cbit_digit, table_limit, cd);
1.1 misha 1284: break;
1285:
1.7 moko 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. */
1.1 misha 1289:
1290: case OP_NOT_WHITESPACE:
1.3 misha 1291: set_nottype_bits(start_bits, cbit_space, table_limit, cd);
1.1 misha 1292: break;
1293:
1294: case OP_WHITESPACE:
1.3 misha 1295: set_type_bits(start_bits, cbit_space, table_limit, cd);
1.1 misha 1296: break;
1297:
1298: case OP_NOT_WORDCHAR:
1.3 misha 1299: set_nottype_bits(start_bits, cbit_word, table_limit, cd);
1.1 misha 1300: break;
1301:
1302: case OP_WORDCHAR:
1.3 misha 1303: set_type_bits(start_bits, cbit_word, table_limit, cd);
1.1 misha 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:
1.7 moko 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:
1.1 misha 1326: case OP_NCLASS:
1.5 misha 1327: #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1328: if (utf)
1.1 misha 1329: {
1330: start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
1331: memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
1332: }
1333: #endif
1.6 misha 1334: #if defined COMPILE_PCRE16 || defined COMPILE_PCRE32
1.5 misha 1335: SET_BIT(0xFF); /* For characters > 255 */
1336: #endif
1.1 misha 1337: /* Fall through */
1338:
1339: case OP_CLASS:
1340: {
1.5 misha 1341: pcre_uint8 *map;
1.7 moko 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: }
1.1 misha 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:
1.7 moko 1364: #if defined SUPPORT_UTF || !defined COMPILE_PCRE8
1365: if (map != NULL)
1366: #endif
1367: {
1.5 misha 1368: #if defined SUPPORT_UTF && defined COMPILE_PCRE8
1.7 moko 1369: if (utf)
1.1 misha 1370: {
1.7 moko 1371: for (c = 0; c < 16; c++) start_bits[c] |= map[c];
1372: for (c = 128; c < 256; c++)
1.1 misha 1373: {
1.8 ! moko 1374: if ((map[c/8] & (1 << (c&7))) != 0)
1.7 moko 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: }
1.1 misha 1380: }
1381: }
1.7 moko 1382: else
1.1 misha 1383: #endif
1.7 moko 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: }
1.1 misha 1388: }
1389:
1.5 misha 1390: /* Advance past the bit map, and act on what follows. For a zero
1391: minimum repeat, continue; otherwise stop processing. */
1.1 misha 1392:
1393: switch (*tcode)
1394: {
1395: case OP_CRSTAR:
1396: case OP_CRMINSTAR:
1397: case OP_CRQUERY:
1398: case OP_CRMINQUERY:
1.7 moko 1399: case OP_CRPOSSTAR:
1400: case OP_CRPOSQUERY:
1.1 misha 1401: tcode++;
1402: break;
1403:
1404: case OP_CRRANGE:
1405: case OP_CRMINRANGE:
1.7 moko 1406: case OP_CRPOSRANGE:
1.5 misha 1407: if (GET2(tcode, 1) == 0) tcode += 1 + 2 * IMM2_SIZE;
1.1 misha 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:
1.5 misha 1429:
1430:
1.1 misha 1431: /*************************************************
1432: * Study a compiled expression *
1433: *************************************************/
1434:
1435: /* This function is handed a compiled expression that it must study to produce
1.5 misha 1436: information that will speed up the matching. It returns a pcre[16]_extra block
1.1 misha 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:
1.5 misha 1445: Returns: pointer to a pcre[16]_extra block, with study_data filled in and
1446: the appropriate flags set;
1.1 misha 1447: NULL on error or if no optimization possible
1448: */
1449:
1.6 misha 1450: #if defined COMPILE_PCRE8
1.2 misha 1451: PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
1.1 misha 1452: pcre_study(const pcre *external_re, int options, const char **errorptr)
1.6 misha 1453: #elif defined COMPILE_PCRE16
1.5 misha 1454: PCRE_EXP_DEFN pcre16_extra * PCRE_CALL_CONVENTION
1455: pcre16_study(const pcre16 *external_re, int options, const char **errorptr)
1.6 misha 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)
1.5 misha 1459: #endif
1.1 misha 1460: {
1.3 misha 1461: int min;
1.8 ! moko 1462: int count = 0;
1.3 misha 1463: BOOL bits_set = FALSE;
1.5 misha 1464: pcre_uint8 start_bits[32];
1465: PUBL(extra) *extra = NULL;
1.1 misha 1466: pcre_study_data *study;
1.5 misha 1467: const pcre_uint8 *tables;
1468: pcre_uchar *code;
1.1 misha 1469: compile_data compile_block;
1.5 misha 1470: const REAL_PCRE *re = (const REAL_PCRE *)external_re;
1.1 misha 1471:
1.7 moko 1472:
1.1 misha 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:
1.5 misha 1481: if ((re->flags & PCRE_MODE) == 0)
1482: {
1.6 misha 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";
1.5 misha 1489: #endif
1490: return NULL;
1491: }
1492:
1.1 misha 1493: if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
1494: {
1495: *errorptr = "unknown or incorrect option bit(s) set";
1496: return NULL;
1497: }
1498:
1.5 misha 1499: code = (pcre_uchar *)re + re->name_table_offset +
1.1 misha 1500: (re->name_count * re->name_entry_size);
1501:
1502: /* For an anchored pattern, or an unanchored pattern that has a first char, or
1.3 misha 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: {
1.5 misha 1509: int rc;
1510:
1.3 misha 1511: /* Set the character tables in the block that is passed around */
1.1 misha 1512:
1.3 misha 1513: tables = re->tables;
1.5 misha 1514:
1.6 misha 1515: #if defined COMPILE_PCRE8
1.3 misha 1516: if (tables == NULL)
1517: (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1518: (void *)(&tables));
1.6 misha 1519: #elif defined COMPILE_PCRE16
1.5 misha 1520: if (tables == NULL)
1521: (void)pcre16_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1522: (void *)(&tables));
1.6 misha 1523: #elif defined COMPILE_PCRE32
1524: if (tables == NULL)
1525: (void)pcre32_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
1526: (void *)(&tables));
1.5 misha 1527: #endif
1.3 misha 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:
1.5 misha 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: }
1.3 misha 1545: }
1546:
1547: /* Find the minimum length of subject string. */
1548:
1.8 ! moko 1549: switch(min = find_minlength(re, code, code, re->options, NULL, &count))
1.5 misha 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: }
1.1 misha 1555:
1.5 misha 1556: /* If a set of starting bytes has been identified, or if the minimum length is
1.6 misha 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. */
1.5 misha 1564:
1.6 misha 1565: if (bits_set || min > 0 || (options & (
1.5 misha 1566: #ifdef SUPPORT_JIT
1.6 misha 1567: PCRE_STUDY_JIT_COMPILE | PCRE_STUDY_JIT_PARTIAL_SOFT_COMPILE |
1568: PCRE_STUDY_JIT_PARTIAL_HARD_COMPILE |
1.5 misha 1569: #endif
1.6 misha 1570: PCRE_STUDY_EXTRA_NEEDED)) != 0)
1.5 misha 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. */
1.1 misha 1590:
1.5 misha 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
1.1 misha 1609:
1.5 misha 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. */
1.1 misha 1614:
1.5 misha 1615: if (min > 0)
1616: {
1617: study->flags |= PCRE_STUDY_MINLEN;
1618: study->minlength = min;
1619: }
1620: else study->minlength = 0;
1.1 misha 1621:
1.5 misha 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
1.6 misha 1624: compilation fails, abandon the extra block and return NULL, unless
1625: PCRE_STUDY_EXTRA_NEEDED is set. */
1.5 misha 1626:
1627: #ifdef SUPPORT_JIT
1628: extra->executable_jit = NULL;
1.6 misha 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)
1.5 misha 1638: {
1.6 misha 1639: #if defined COMPILE_PCRE8
1.5 misha 1640: pcre_free_study(extra);
1.6 misha 1641: #elif defined COMPILE_PCRE16
1.5 misha 1642: pcre16_free_study(extra);
1.6 misha 1643: #elif defined COMPILE_PCRE32
1644: pcre32_free_study(extra);
1.5 misha 1645: #endif
1646: extra = NULL;
1647: }
1648: #endif
1.1 misha 1649: }
1650:
1.5 misha 1651: return extra;
1652: }
1.1 misha 1653:
1.3 misha 1654:
1.5 misha 1655: /*************************************************
1656: * Free the study data *
1657: *************************************************/
1658:
1659: /* This function frees the memory that was obtained by pcre_study().
1.3 misha 1660:
1.5 misha 1661: Argument: a pointer to the pcre[16]_extra block
1662: Returns: nothing
1663: */
1.1 misha 1664:
1.6 misha 1665: #if defined COMPILE_PCRE8
1.5 misha 1666: PCRE_EXP_DEFN void
1667: pcre_free_study(pcre_extra *extra)
1.6 misha 1668: #elif defined COMPILE_PCRE16
1.5 misha 1669: PCRE_EXP_DEFN void
1670: pcre16_free_study(pcre16_extra *extra)
1.6 misha 1671: #elif defined COMPILE_PCRE32
1672: PCRE_EXP_DEFN void
1673: pcre32_free_study(pcre32_extra *extra)
1.5 misha 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);
1.1 misha 1684: }
1685:
1686: /* End of pcre_study.c */
E-mail:
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to pcre_study.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [parser3project] / win32 / pcre