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