Annotation of embedaddon/php/ext/pcre/pcrelib/pcre_study.c, revision 1.1
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
! 9: Copyright (c) 1997-2010 University of Cambridge
! 10:
! 11: -----------------------------------------------------------------------------
! 12: Redistribution and use in source and binary forms, with or without
! 13: modification, are permitted provided that the following conditions are met:
! 14:
! 15: * Redistributions of source code must retain the above copyright notice,
! 16: this list of conditions and the following disclaimer.
! 17:
! 18: * Redistributions in binary form must reproduce the above copyright
! 19: notice, this list of conditions and the following disclaimer in the
! 20: documentation and/or other materials provided with the distribution.
! 21:
! 22: * Neither the name of the University of Cambridge nor the names of its
! 23: contributors may be used to endorse or promote products derived from
! 24: this software without specific prior written permission.
! 25:
! 26: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
! 27: AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 28: IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 29: ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
! 30: LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
! 31: CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
! 32: SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
! 33: INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
! 34: CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
! 35: ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
! 36: POSSIBILITY OF SUCH DAMAGE.
! 37: -----------------------------------------------------------------------------
! 38: */
! 39:
! 40:
! 41: /* This module contains the external function pcre_study(), along with local
! 42: supporting functions. */
! 43:
! 44:
! 45: #include "config.h"
! 46:
! 47: #include "pcre_internal.h"
! 48:
! 49: #define SET_BIT(c) start_bits[c/8] |= (1 << (c&7))
! 50:
! 51: /* Returns from set_start_bits() */
! 52:
! 53: enum { SSB_FAIL, SSB_DONE, SSB_CONTINUE };
! 54:
! 55:
! 56:
! 57: /*************************************************
! 58: * Find the minimum subject length for a group *
! 59: *************************************************/
! 60:
! 61: /* Scan a parenthesized group and compute the minimum length of subject that
! 62: is needed to match it. This is a lower bound; it does not mean there is a
! 63: string of that length that matches. In UTF8 mode, the result is in characters
! 64: rather than bytes.
! 65:
! 66: Arguments:
! 67: code pointer to start of group (the bracket)
! 68: startcode pointer to start of the whole pattern
! 69: options the compiling options
! 70:
! 71: Returns: the minimum length
! 72: -1 if \C was encountered
! 73: -2 internal error (missing capturing bracket)
! 74: */
! 75:
! 76: static int
! 77: find_minlength(const uschar *code, const uschar *startcode, int options)
! 78: {
! 79: int length = -1;
! 80: BOOL utf8 = (options & PCRE_UTF8) != 0;
! 81: BOOL had_recurse = FALSE;
! 82: register int branchlength = 0;
! 83: register uschar *cc = (uschar *)code + 1 + LINK_SIZE;
! 84:
! 85: if (*code == OP_CBRA || *code == OP_SCBRA) cc += 2;
! 86:
! 87: /* Scan along the opcodes for this branch. If we get to the end of the
! 88: branch, check the length against that of the other branches. */
! 89:
! 90: for (;;)
! 91: {
! 92: int d, min;
! 93: uschar *cs, *ce;
! 94: register int op = *cc;
! 95:
! 96: switch (op)
! 97: {
! 98: case OP_COND:
! 99: case OP_SCOND:
! 100:
! 101: /* If there is only one branch in a condition, the implied branch has zero
! 102: length, so we don't add anything. This covers the DEFINE "condition"
! 103: automatically. */
! 104:
! 105: cs = cc + GET(cc, 1);
! 106: if (*cs != OP_ALT)
! 107: {
! 108: cc = cs + 1 + LINK_SIZE;
! 109: break;
! 110: }
! 111:
! 112: /* Otherwise we can fall through and treat it the same as any other
! 113: subpattern. */
! 114:
! 115: case OP_CBRA:
! 116: case OP_SCBRA:
! 117: case OP_BRA:
! 118: case OP_SBRA:
! 119: case OP_ONCE:
! 120: d = find_minlength(cc, startcode, options);
! 121: if (d < 0) return d;
! 122: branchlength += d;
! 123: do cc += GET(cc, 1); while (*cc == OP_ALT);
! 124: cc += 1 + LINK_SIZE;
! 125: break;
! 126:
! 127: /* Reached end of a branch; if it's a ket it is the end of a nested
! 128: call. If it's ALT it is an alternation in a nested call. If it is
! 129: END it's the end of the outer call. All can be handled by the same code. */
! 130:
! 131: case OP_ALT:
! 132: case OP_KET:
! 133: case OP_KETRMAX:
! 134: case OP_KETRMIN:
! 135: case OP_END:
! 136: if (length < 0 || (!had_recurse && branchlength < length))
! 137: length = branchlength;
! 138: if (*cc != OP_ALT) return length;
! 139: cc += 1 + LINK_SIZE;
! 140: branchlength = 0;
! 141: had_recurse = FALSE;
! 142: break;
! 143:
! 144: /* Skip over assertive subpatterns */
! 145:
! 146: case OP_ASSERT:
! 147: case OP_ASSERT_NOT:
! 148: case OP_ASSERTBACK:
! 149: case OP_ASSERTBACK_NOT:
! 150: do cc += GET(cc, 1); while (*cc == OP_ALT);
! 151: /* Fall through */
! 152:
! 153: /* Skip over things that don't match chars */
! 154:
! 155: case OP_REVERSE:
! 156: case OP_CREF:
! 157: case OP_NCREF:
! 158: case OP_RREF:
! 159: case OP_NRREF:
! 160: case OP_DEF:
! 161: case OP_OPT:
! 162: case OP_CALLOUT:
! 163: case OP_SOD:
! 164: case OP_SOM:
! 165: case OP_EOD:
! 166: case OP_EODN:
! 167: case OP_CIRC:
! 168: case OP_DOLL:
! 169: case OP_NOT_WORD_BOUNDARY:
! 170: case OP_WORD_BOUNDARY:
! 171: cc += _pcre_OP_lengths[*cc];
! 172: break;
! 173:
! 174: /* Skip over a subpattern that has a {0} or {0,x} quantifier */
! 175:
! 176: case OP_BRAZERO:
! 177: case OP_BRAMINZERO:
! 178: case OP_SKIPZERO:
! 179: cc += _pcre_OP_lengths[*cc];
! 180: do cc += GET(cc, 1); while (*cc == OP_ALT);
! 181: cc += 1 + LINK_SIZE;
! 182: break;
! 183:
! 184: /* Handle literal characters and + repetitions */
! 185:
! 186: case OP_CHAR:
! 187: case OP_CHARNC:
! 188: case OP_NOT:
! 189: case OP_PLUS:
! 190: case OP_MINPLUS:
! 191: case OP_POSPLUS:
! 192: case OP_NOTPLUS:
! 193: case OP_NOTMINPLUS:
! 194: case OP_NOTPOSPLUS:
! 195: branchlength++;
! 196: cc += 2;
! 197: #ifdef SUPPORT_UTF8
! 198: if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
! 199: #endif
! 200: break;
! 201:
! 202: case OP_TYPEPLUS:
! 203: case OP_TYPEMINPLUS:
! 204: case OP_TYPEPOSPLUS:
! 205: branchlength++;
! 206: cc += (cc[1] == OP_PROP || cc[1] == OP_NOTPROP)? 4 : 2;
! 207: break;
! 208:
! 209: /* Handle exact repetitions. The count is already in characters, but we
! 210: need to skip over a multibyte character in UTF8 mode. */
! 211:
! 212: case OP_EXACT:
! 213: case OP_NOTEXACT:
! 214: branchlength += GET2(cc,1);
! 215: cc += 4;
! 216: #ifdef SUPPORT_UTF8
! 217: if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
! 218: #endif
! 219: break;
! 220:
! 221: case OP_TYPEEXACT:
! 222: branchlength += GET2(cc,1);
! 223: cc += (cc[3] == OP_PROP || cc[3] == OP_NOTPROP)? 6 : 4;
! 224: break;
! 225:
! 226: /* Handle single-char non-literal matchers */
! 227:
! 228: case OP_PROP:
! 229: case OP_NOTPROP:
! 230: cc += 2;
! 231: /* Fall through */
! 232:
! 233: case OP_NOT_DIGIT:
! 234: case OP_DIGIT:
! 235: case OP_NOT_WHITESPACE:
! 236: case OP_WHITESPACE:
! 237: case OP_NOT_WORDCHAR:
! 238: case OP_WORDCHAR:
! 239: case OP_ANY:
! 240: case OP_ALLANY:
! 241: case OP_EXTUNI:
! 242: case OP_HSPACE:
! 243: case OP_NOT_HSPACE:
! 244: case OP_VSPACE:
! 245: case OP_NOT_VSPACE:
! 246: branchlength++;
! 247: cc++;
! 248: break;
! 249:
! 250: /* "Any newline" might match two characters */
! 251:
! 252: case OP_ANYNL:
! 253: branchlength += 2;
! 254: cc++;
! 255: break;
! 256:
! 257: /* The single-byte matcher means we can't proceed in UTF-8 mode */
! 258:
! 259: case OP_ANYBYTE:
! 260: #ifdef SUPPORT_UTF8
! 261: if (utf8) return -1;
! 262: #endif
! 263: branchlength++;
! 264: cc++;
! 265: break;
! 266:
! 267: /* For repeated character types, we have to test for \p and \P, which have
! 268: an extra two bytes of parameters. */
! 269:
! 270: case OP_TYPESTAR:
! 271: case OP_TYPEMINSTAR:
! 272: case OP_TYPEQUERY:
! 273: case OP_TYPEMINQUERY:
! 274: case OP_TYPEPOSSTAR:
! 275: case OP_TYPEPOSQUERY:
! 276: if (cc[1] == OP_PROP || cc[1] == OP_NOTPROP) cc += 2;
! 277: cc += _pcre_OP_lengths[op];
! 278: break;
! 279:
! 280: case OP_TYPEUPTO:
! 281: case OP_TYPEMINUPTO:
! 282: case OP_TYPEPOSUPTO:
! 283: if (cc[3] == OP_PROP || cc[3] == OP_NOTPROP) cc += 2;
! 284: cc += _pcre_OP_lengths[op];
! 285: break;
! 286:
! 287: /* Check a class for variable quantification */
! 288:
! 289: #ifdef SUPPORT_UTF8
! 290: case OP_XCLASS:
! 291: cc += GET(cc, 1) - 33;
! 292: /* Fall through */
! 293: #endif
! 294:
! 295: case OP_CLASS:
! 296: case OP_NCLASS:
! 297: cc += 33;
! 298:
! 299: switch (*cc)
! 300: {
! 301: case OP_CRPLUS:
! 302: case OP_CRMINPLUS:
! 303: branchlength++;
! 304: /* Fall through */
! 305:
! 306: case OP_CRSTAR:
! 307: case OP_CRMINSTAR:
! 308: case OP_CRQUERY:
! 309: case OP_CRMINQUERY:
! 310: cc++;
! 311: break;
! 312:
! 313: case OP_CRRANGE:
! 314: case OP_CRMINRANGE:
! 315: branchlength += GET2(cc,1);
! 316: cc += 5;
! 317: break;
! 318:
! 319: default:
! 320: branchlength++;
! 321: break;
! 322: }
! 323: break;
! 324:
! 325: /* Backreferences and subroutine calls are treated in the same way: we find
! 326: the minimum length for the subpattern. A recursion, however, causes an
! 327: a flag to be set that causes the length of this branch to be ignored. The
! 328: logic is that a recursion can only make sense if there is another
! 329: alternation that stops the recursing. That will provide the minimum length
! 330: (when no recursion happens). A backreference within the group that it is
! 331: referencing behaves in the same way.
! 332:
! 333: If PCRE_JAVASCRIPT_COMPAT is set, a backreference to an unset bracket
! 334: matches an empty string (by default it causes a matching failure), so in
! 335: that case we must set the minimum length to zero. */
! 336:
! 337: case OP_REF:
! 338: if ((options & PCRE_JAVASCRIPT_COMPAT) == 0)
! 339: {
! 340: ce = cs = (uschar *)_pcre_find_bracket(startcode, utf8, GET2(cc, 1));
! 341: if (cs == NULL) return -2;
! 342: do ce += GET(ce, 1); while (*ce == OP_ALT);
! 343: if (cc > cs && cc < ce)
! 344: {
! 345: d = 0;
! 346: had_recurse = TRUE;
! 347: }
! 348: else d = find_minlength(cs, startcode, options);
! 349: }
! 350: else d = 0;
! 351: cc += 3;
! 352:
! 353: /* Handle repeated back references */
! 354:
! 355: switch (*cc)
! 356: {
! 357: case OP_CRSTAR:
! 358: case OP_CRMINSTAR:
! 359: case OP_CRQUERY:
! 360: case OP_CRMINQUERY:
! 361: min = 0;
! 362: cc++;
! 363: break;
! 364:
! 365: case OP_CRRANGE:
! 366: case OP_CRMINRANGE:
! 367: min = GET2(cc, 1);
! 368: cc += 5;
! 369: break;
! 370:
! 371: default:
! 372: min = 1;
! 373: break;
! 374: }
! 375:
! 376: branchlength += min * d;
! 377: break;
! 378:
! 379: case OP_RECURSE:
! 380: cs = ce = (uschar *)startcode + GET(cc, 1);
! 381: if (cs == NULL) return -2;
! 382: do ce += GET(ce, 1); while (*ce == OP_ALT);
! 383: if (cc > cs && cc < ce)
! 384: had_recurse = TRUE;
! 385: else
! 386: branchlength += find_minlength(cs, startcode, options);
! 387: cc += 1 + LINK_SIZE;
! 388: break;
! 389:
! 390: /* Anything else does not or need not match a character. We can get the
! 391: item's length from the table, but for those that can match zero occurrences
! 392: of a character, we must take special action for UTF-8 characters. */
! 393:
! 394: case OP_UPTO:
! 395: case OP_NOTUPTO:
! 396: case OP_MINUPTO:
! 397: case OP_NOTMINUPTO:
! 398: case OP_POSUPTO:
! 399: case OP_STAR:
! 400: case OP_MINSTAR:
! 401: case OP_NOTMINSTAR:
! 402: case OP_POSSTAR:
! 403: case OP_NOTPOSSTAR:
! 404: case OP_QUERY:
! 405: case OP_MINQUERY:
! 406: case OP_NOTMINQUERY:
! 407: case OP_POSQUERY:
! 408: case OP_NOTPOSQUERY:
! 409: cc += _pcre_OP_lengths[op];
! 410: #ifdef SUPPORT_UTF8
! 411: if (utf8 && cc[-1] >= 0xc0) cc += _pcre_utf8_table4[cc[-1] & 0x3f];
! 412: #endif
! 413: break;
! 414:
! 415: /* Skip these, but we need to add in the name length. */
! 416:
! 417: case OP_MARK:
! 418: case OP_PRUNE_ARG:
! 419: case OP_SKIP_ARG:
! 420: cc += _pcre_OP_lengths[op] + cc[1];
! 421: break;
! 422:
! 423: case OP_THEN_ARG:
! 424: cc += _pcre_OP_lengths[op] + cc[1+LINK_SIZE];
! 425: break;
! 426:
! 427: /* For the record, these are the opcodes that are matched by "default":
! 428: OP_ACCEPT, OP_CLOSE, OP_COMMIT, OP_FAIL, OP_PRUNE, OP_SET_SOM, OP_SKIP,
! 429: OP_THEN. */
! 430:
! 431: default:
! 432: cc += _pcre_OP_lengths[op];
! 433: break;
! 434: }
! 435: }
! 436: /* Control never gets here */
! 437: }
! 438:
! 439:
! 440:
! 441: /*************************************************
! 442: * Set a bit and maybe its alternate case *
! 443: *************************************************/
! 444:
! 445: /* Given a character, set its first byte's bit in the table, and also the
! 446: corresponding bit for the other version of a letter if we are caseless. In
! 447: UTF-8 mode, for characters greater than 127, we can only do the caseless thing
! 448: when Unicode property support is available.
! 449:
! 450: Arguments:
! 451: start_bits points to the bit map
! 452: p points to the character
! 453: caseless the caseless flag
! 454: cd the block with char table pointers
! 455: utf8 TRUE for UTF-8 mode
! 456:
! 457: Returns: pointer after the character
! 458: */
! 459:
! 460: static const uschar *
! 461: set_table_bit(uschar *start_bits, const uschar *p, BOOL caseless,
! 462: compile_data *cd, BOOL utf8)
! 463: {
! 464: unsigned int c = *p;
! 465:
! 466: SET_BIT(c);
! 467:
! 468: #ifdef SUPPORT_UTF8
! 469: if (utf8 && c > 127)
! 470: {
! 471: GETCHARINC(c, p);
! 472: #ifdef SUPPORT_UCP
! 473: if (caseless)
! 474: {
! 475: uschar buff[8];
! 476: c = UCD_OTHERCASE(c);
! 477: (void)_pcre_ord2utf8(c, buff);
! 478: SET_BIT(buff[0]);
! 479: }
! 480: #endif
! 481: return p;
! 482: }
! 483: #endif
! 484:
! 485: /* Not UTF-8 mode, or character is less than 127. */
! 486:
! 487: if (caseless && (cd->ctypes[c] & ctype_letter) != 0) SET_BIT(cd->fcc[c]);
! 488: return p + 1;
! 489: }
! 490:
! 491:
! 492:
! 493: /*************************************************
! 494: * Set bits for a positive character type *
! 495: *************************************************/
! 496:
! 497: /* This function sets starting bits for a character type. In UTF-8 mode, we can
! 498: only do a direct setting for bytes less than 128, as otherwise there can be
! 499: confusion with bytes in the middle of UTF-8 characters. In a "traditional"
! 500: environment, the tables will only recognize ASCII characters anyway, but in at
! 501: least one Windows environment, some higher bytes bits were set in the tables.
! 502: So we deal with that case by considering the UTF-8 encoding.
! 503:
! 504: Arguments:
! 505: start_bits the starting bitmap
! 506: cbit type the type of character wanted
! 507: table_limit 32 for non-UTF-8; 16 for UTF-8
! 508: cd the block with char table pointers
! 509:
! 510: Returns: nothing
! 511: */
! 512:
! 513: static void
! 514: set_type_bits(uschar *start_bits, int cbit_type, int table_limit,
! 515: compile_data *cd)
! 516: {
! 517: register int c;
! 518: for (c = 0; c < table_limit; c++) start_bits[c] |= cd->cbits[c+cbit_type];
! 519: if (table_limit == 32) return;
! 520: for (c = 128; c < 256; c++)
! 521: {
! 522: if ((cd->cbits[c/8] & (1 << (c&7))) != 0)
! 523: {
! 524: uschar buff[8];
! 525: (void)_pcre_ord2utf8(c, buff);
! 526: SET_BIT(buff[0]);
! 527: }
! 528: }
! 529: }
! 530:
! 531:
! 532: /*************************************************
! 533: * Set bits for a negative character type *
! 534: *************************************************/
! 535:
! 536: /* This function sets starting bits for a negative character type such as \D.
! 537: In UTF-8 mode, we can only do a direct setting for bytes less than 128, as
! 538: otherwise there can be confusion with bytes in the middle of UTF-8 characters.
! 539: Unlike in the positive case, where we can set appropriate starting bits for
! 540: specific high-valued UTF-8 characters, in this case we have to set the bits for
! 541: all high-valued characters. The lowest is 0xc2, but we overkill by starting at
! 542: 0xc0 (192) for simplicity.
! 543:
! 544: Arguments:
! 545: start_bits the starting bitmap
! 546: cbit type the type of character wanted
! 547: table_limit 32 for non-UTF-8; 16 for UTF-8
! 548: cd the block with char table pointers
! 549:
! 550: Returns: nothing
! 551: */
! 552:
! 553: static void
! 554: set_nottype_bits(uschar *start_bits, int cbit_type, int table_limit,
! 555: compile_data *cd)
! 556: {
! 557: register int c;
! 558: for (c = 0; c < table_limit; c++) start_bits[c] |= ~cd->cbits[c+cbit_type];
! 559: if (table_limit != 32) for (c = 24; c < 32; c++) start_bits[c] = 0xff;
! 560: }
! 561:
! 562:
! 563:
! 564: /*************************************************
! 565: * Create bitmap of starting bytes *
! 566: *************************************************/
! 567:
! 568: /* This function scans a compiled unanchored expression recursively and
! 569: attempts to build a bitmap of the set of possible starting bytes. As time goes
! 570: by, we may be able to get more clever at doing this. The SSB_CONTINUE return is
! 571: useful for parenthesized groups in patterns such as (a*)b where the group
! 572: provides some optional starting bytes but scanning must continue at the outer
! 573: level to find at least one mandatory byte. At the outermost level, this
! 574: function fails unless the result is SSB_DONE.
! 575:
! 576: Arguments:
! 577: code points to an expression
! 578: start_bits points to a 32-byte table, initialized to 0
! 579: caseless the current state of the caseless flag
! 580: utf8 TRUE if in UTF-8 mode
! 581: cd the block with char table pointers
! 582:
! 583: Returns: SSB_FAIL => Failed to find any starting bytes
! 584: SSB_DONE => Found mandatory starting bytes
! 585: SSB_CONTINUE => Found optional starting bytes
! 586: */
! 587:
! 588: static int
! 589: set_start_bits(const uschar *code, uschar *start_bits, BOOL caseless,
! 590: BOOL utf8, compile_data *cd)
! 591: {
! 592: register int c;
! 593: int yield = SSB_DONE;
! 594: int table_limit = utf8? 16:32;
! 595:
! 596: #if 0
! 597: /* ========================================================================= */
! 598: /* The following comment and code was inserted in January 1999. In May 2006,
! 599: when it was observed to cause compiler warnings about unused values, I took it
! 600: out again. If anybody is still using OS/2, they will have to put it back
! 601: manually. */
! 602:
! 603: /* This next statement and the later reference to dummy are here in order to
! 604: trick the optimizer of the IBM C compiler for OS/2 into generating correct
! 605: code. Apparently IBM isn't going to fix the problem, and we would rather not
! 606: disable optimization (in this module it actually makes a big difference, and
! 607: the pcre module can use all the optimization it can get). */
! 608:
! 609: volatile int dummy;
! 610: /* ========================================================================= */
! 611: #endif
! 612:
! 613: do
! 614: {
! 615: const uschar *tcode = code + (((int)*code == OP_CBRA)? 3:1) + LINK_SIZE;
! 616: BOOL try_next = TRUE;
! 617:
! 618: while (try_next) /* Loop for items in this branch */
! 619: {
! 620: int rc;
! 621: switch(*tcode)
! 622: {
! 623: /* Fail if we reach something we don't understand */
! 624:
! 625: default:
! 626: return SSB_FAIL;
! 627:
! 628: /* If we hit a bracket or a positive lookahead assertion, recurse to set
! 629: bits from within the subpattern. If it can't find anything, we have to
! 630: give up. If it finds some mandatory character(s), we are done for this
! 631: branch. Otherwise, carry on scanning after the subpattern. */
! 632:
! 633: case OP_BRA:
! 634: case OP_SBRA:
! 635: case OP_CBRA:
! 636: case OP_SCBRA:
! 637: case OP_ONCE:
! 638: case OP_ASSERT:
! 639: rc = set_start_bits(tcode, start_bits, caseless, utf8, cd);
! 640: if (rc == SSB_FAIL) return SSB_FAIL;
! 641: if (rc == SSB_DONE) try_next = FALSE; else
! 642: {
! 643: do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
! 644: tcode += 1 + LINK_SIZE;
! 645: }
! 646: break;
! 647:
! 648: /* If we hit ALT or KET, it means we haven't found anything mandatory in
! 649: this branch, though we might have found something optional. For ALT, we
! 650: continue with the next alternative, but we have to arrange that the final
! 651: result from subpattern is SSB_CONTINUE rather than SSB_DONE. For KET,
! 652: return SSB_CONTINUE: if this is the top level, that indicates failure,
! 653: but after a nested subpattern, it causes scanning to continue. */
! 654:
! 655: case OP_ALT:
! 656: yield = SSB_CONTINUE;
! 657: try_next = FALSE;
! 658: break;
! 659:
! 660: case OP_KET:
! 661: case OP_KETRMAX:
! 662: case OP_KETRMIN:
! 663: return SSB_CONTINUE;
! 664:
! 665: /* Skip over callout */
! 666:
! 667: case OP_CALLOUT:
! 668: tcode += 2 + 2*LINK_SIZE;
! 669: break;
! 670:
! 671: /* Skip over lookbehind and negative lookahead assertions */
! 672:
! 673: case OP_ASSERT_NOT:
! 674: case OP_ASSERTBACK:
! 675: case OP_ASSERTBACK_NOT:
! 676: do tcode += GET(tcode, 1); while (*tcode == OP_ALT);
! 677: tcode += 1 + LINK_SIZE;
! 678: break;
! 679:
! 680: /* Skip over an option setting, changing the caseless flag */
! 681:
! 682: case OP_OPT:
! 683: caseless = (tcode[1] & PCRE_CASELESS) != 0;
! 684: tcode += 2;
! 685: break;
! 686:
! 687: /* BRAZERO does the bracket, but carries on. */
! 688:
! 689: case OP_BRAZERO:
! 690: case OP_BRAMINZERO:
! 691: if (set_start_bits(++tcode, start_bits, caseless, utf8, cd) == SSB_FAIL)
! 692: return SSB_FAIL;
! 693: /* =========================================================================
! 694: See the comment at the head of this function concerning the next line,
! 695: which was an old fudge for the benefit of OS/2.
! 696: dummy = 1;
! 697: ========================================================================= */
! 698: do tcode += GET(tcode,1); while (*tcode == OP_ALT);
! 699: tcode += 1 + LINK_SIZE;
! 700: break;
! 701:
! 702: /* SKIPZERO skips the bracket. */
! 703:
! 704: case OP_SKIPZERO:
! 705: tcode++;
! 706: do tcode += GET(tcode,1); while (*tcode == OP_ALT);
! 707: tcode += 1 + LINK_SIZE;
! 708: break;
! 709:
! 710: /* Single-char * or ? sets the bit and tries the next item */
! 711:
! 712: case OP_STAR:
! 713: case OP_MINSTAR:
! 714: case OP_POSSTAR:
! 715: case OP_QUERY:
! 716: case OP_MINQUERY:
! 717: case OP_POSQUERY:
! 718: tcode = set_table_bit(start_bits, tcode + 1, caseless, cd, utf8);
! 719: break;
! 720:
! 721: /* Single-char upto sets the bit and tries the next */
! 722:
! 723: case OP_UPTO:
! 724: case OP_MINUPTO:
! 725: case OP_POSUPTO:
! 726: tcode = set_table_bit(start_bits, tcode + 3, caseless, cd, utf8);
! 727: break;
! 728:
! 729: /* At least one single char sets the bit and stops */
! 730:
! 731: case OP_EXACT: /* Fall through */
! 732: tcode += 2;
! 733:
! 734: case OP_CHAR:
! 735: case OP_CHARNC:
! 736: case OP_PLUS:
! 737: case OP_MINPLUS:
! 738: case OP_POSPLUS:
! 739: (void)set_table_bit(start_bits, tcode + 1, caseless, cd, utf8);
! 740: try_next = FALSE;
! 741: break;
! 742:
! 743: /* Special spacing and line-terminating items. These recognize specific
! 744: lists of characters. The difference between VSPACE and ANYNL is that the
! 745: latter can match the two-character CRLF sequence, but that is not
! 746: relevant for finding the first character, so their code here is
! 747: identical. */
! 748:
! 749: case OP_HSPACE:
! 750: SET_BIT(0x09);
! 751: SET_BIT(0x20);
! 752: if (utf8)
! 753: {
! 754: SET_BIT(0xC2); /* For U+00A0 */
! 755: SET_BIT(0xE1); /* For U+1680, U+180E */
! 756: SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
! 757: SET_BIT(0xE3); /* For U+3000 */
! 758: }
! 759: else SET_BIT(0xA0);
! 760: try_next = FALSE;
! 761: break;
! 762:
! 763: case OP_ANYNL:
! 764: case OP_VSPACE:
! 765: SET_BIT(0x0A);
! 766: SET_BIT(0x0B);
! 767: SET_BIT(0x0C);
! 768: SET_BIT(0x0D);
! 769: if (utf8)
! 770: {
! 771: SET_BIT(0xC2); /* For U+0085 */
! 772: SET_BIT(0xE2); /* For U+2028, U+2029 */
! 773: }
! 774: else SET_BIT(0x85);
! 775: try_next = FALSE;
! 776: break;
! 777:
! 778: /* Single character types set the bits and stop. Note that if PCRE_UCP
! 779: is set, we do not see these op codes because \d etc are converted to
! 780: properties. Therefore, these apply in the case when only characters less
! 781: than 256 are recognized to match the types. */
! 782:
! 783: case OP_NOT_DIGIT:
! 784: set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
! 785: try_next = FALSE;
! 786: break;
! 787:
! 788: case OP_DIGIT:
! 789: set_type_bits(start_bits, cbit_digit, table_limit, cd);
! 790: try_next = FALSE;
! 791: break;
! 792:
! 793: /* The cbit_space table has vertical tab as whitespace; we have to
! 794: ensure it is set as not whitespace. */
! 795:
! 796: case OP_NOT_WHITESPACE:
! 797: set_nottype_bits(start_bits, cbit_space, table_limit, cd);
! 798: start_bits[1] |= 0x08;
! 799: try_next = FALSE;
! 800: break;
! 801:
! 802: /* The cbit_space table has vertical tab as whitespace; we have to
! 803: not set it from the table. */
! 804:
! 805: case OP_WHITESPACE:
! 806: c = start_bits[1]; /* Save in case it was already set */
! 807: set_type_bits(start_bits, cbit_space, table_limit, cd);
! 808: start_bits[1] = (start_bits[1] & ~0x08) | c;
! 809: try_next = FALSE;
! 810: break;
! 811:
! 812: case OP_NOT_WORDCHAR:
! 813: set_nottype_bits(start_bits, cbit_word, table_limit, cd);
! 814: try_next = FALSE;
! 815: break;
! 816:
! 817: case OP_WORDCHAR:
! 818: set_type_bits(start_bits, cbit_word, table_limit, cd);
! 819: try_next = FALSE;
! 820: break;
! 821:
! 822: /* One or more character type fudges the pointer and restarts, knowing
! 823: it will hit a single character type and stop there. */
! 824:
! 825: case OP_TYPEPLUS:
! 826: case OP_TYPEMINPLUS:
! 827: case OP_TYPEPOSPLUS:
! 828: tcode++;
! 829: break;
! 830:
! 831: case OP_TYPEEXACT:
! 832: tcode += 3;
! 833: break;
! 834:
! 835: /* Zero or more repeats of character types set the bits and then
! 836: try again. */
! 837:
! 838: case OP_TYPEUPTO:
! 839: case OP_TYPEMINUPTO:
! 840: case OP_TYPEPOSUPTO:
! 841: tcode += 2; /* Fall through */
! 842:
! 843: case OP_TYPESTAR:
! 844: case OP_TYPEMINSTAR:
! 845: case OP_TYPEPOSSTAR:
! 846: case OP_TYPEQUERY:
! 847: case OP_TYPEMINQUERY:
! 848: case OP_TYPEPOSQUERY:
! 849: switch(tcode[1])
! 850: {
! 851: default:
! 852: case OP_ANY:
! 853: case OP_ALLANY:
! 854: return SSB_FAIL;
! 855:
! 856: case OP_HSPACE:
! 857: SET_BIT(0x09);
! 858: SET_BIT(0x20);
! 859: if (utf8)
! 860: {
! 861: SET_BIT(0xC2); /* For U+00A0 */
! 862: SET_BIT(0xE1); /* For U+1680, U+180E */
! 863: SET_BIT(0xE2); /* For U+2000 - U+200A, U+202F, U+205F */
! 864: SET_BIT(0xE3); /* For U+3000 */
! 865: }
! 866: else SET_BIT(0xA0);
! 867: break;
! 868:
! 869: case OP_ANYNL:
! 870: case OP_VSPACE:
! 871: SET_BIT(0x0A);
! 872: SET_BIT(0x0B);
! 873: SET_BIT(0x0C);
! 874: SET_BIT(0x0D);
! 875: if (utf8)
! 876: {
! 877: SET_BIT(0xC2); /* For U+0085 */
! 878: SET_BIT(0xE2); /* For U+2028, U+2029 */
! 879: }
! 880: else SET_BIT(0x85);
! 881: break;
! 882:
! 883: case OP_NOT_DIGIT:
! 884: set_nottype_bits(start_bits, cbit_digit, table_limit, cd);
! 885: break;
! 886:
! 887: case OP_DIGIT:
! 888: set_type_bits(start_bits, cbit_digit, table_limit, cd);
! 889: break;
! 890:
! 891: /* The cbit_space table has vertical tab as whitespace; we have to
! 892: ensure it gets set as not whitespace. */
! 893:
! 894: case OP_NOT_WHITESPACE:
! 895: set_nottype_bits(start_bits, cbit_space, table_limit, cd);
! 896: start_bits[1] |= 0x08;
! 897: break;
! 898:
! 899: /* The cbit_space table has vertical tab as whitespace; we have to
! 900: avoid setting it. */
! 901:
! 902: case OP_WHITESPACE:
! 903: c = start_bits[1]; /* Save in case it was already set */
! 904: set_type_bits(start_bits, cbit_space, table_limit, cd);
! 905: start_bits[1] = (start_bits[1] & ~0x08) | c;
! 906: break;
! 907:
! 908: case OP_NOT_WORDCHAR:
! 909: set_nottype_bits(start_bits, cbit_word, table_limit, cd);
! 910: break;
! 911:
! 912: case OP_WORDCHAR:
! 913: set_type_bits(start_bits, cbit_word, table_limit, cd);
! 914: break;
! 915: }
! 916:
! 917: tcode += 2;
! 918: break;
! 919:
! 920: /* Character class where all the information is in a bit map: set the
! 921: bits and either carry on or not, according to the repeat count. If it was
! 922: a negative class, and we are operating with UTF-8 characters, any byte
! 923: with a value >= 0xc4 is a potentially valid starter because it starts a
! 924: character with a value > 255. */
! 925:
! 926: case OP_NCLASS:
! 927: #ifdef SUPPORT_UTF8
! 928: if (utf8)
! 929: {
! 930: start_bits[24] |= 0xf0; /* Bits for 0xc4 - 0xc8 */
! 931: memset(start_bits+25, 0xff, 7); /* Bits for 0xc9 - 0xff */
! 932: }
! 933: #endif
! 934: /* Fall through */
! 935:
! 936: case OP_CLASS:
! 937: {
! 938: tcode++;
! 939:
! 940: /* In UTF-8 mode, the bits in a bit map correspond to character
! 941: values, not to byte values. However, the bit map we are constructing is
! 942: for byte values. So we have to do a conversion for characters whose
! 943: value is > 127. In fact, there are only two possible starting bytes for
! 944: characters in the range 128 - 255. */
! 945:
! 946: #ifdef SUPPORT_UTF8
! 947: if (utf8)
! 948: {
! 949: for (c = 0; c < 16; c++) start_bits[c] |= tcode[c];
! 950: for (c = 128; c < 256; c++)
! 951: {
! 952: if ((tcode[c/8] && (1 << (c&7))) != 0)
! 953: {
! 954: int d = (c >> 6) | 0xc0; /* Set bit for this starter */
! 955: start_bits[d/8] |= (1 << (d&7)); /* and then skip on to the */
! 956: c = (c & 0xc0) + 0x40 - 1; /* next relevant character. */
! 957: }
! 958: }
! 959: }
! 960:
! 961: /* In non-UTF-8 mode, the two bit maps are completely compatible. */
! 962:
! 963: else
! 964: #endif
! 965: {
! 966: for (c = 0; c < 32; c++) start_bits[c] |= tcode[c];
! 967: }
! 968:
! 969: /* Advance past the bit map, and act on what follows */
! 970:
! 971: tcode += 32;
! 972: switch (*tcode)
! 973: {
! 974: case OP_CRSTAR:
! 975: case OP_CRMINSTAR:
! 976: case OP_CRQUERY:
! 977: case OP_CRMINQUERY:
! 978: tcode++;
! 979: break;
! 980:
! 981: case OP_CRRANGE:
! 982: case OP_CRMINRANGE:
! 983: if (((tcode[1] << 8) + tcode[2]) == 0) tcode += 5;
! 984: else try_next = FALSE;
! 985: break;
! 986:
! 987: default:
! 988: try_next = FALSE;
! 989: break;
! 990: }
! 991: }
! 992: break; /* End of bitmap class handling */
! 993:
! 994: } /* End of switch */
! 995: } /* End of try_next loop */
! 996:
! 997: code += GET(code, 1); /* Advance to next branch */
! 998: }
! 999: while (*code == OP_ALT);
! 1000: return yield;
! 1001: }
! 1002:
! 1003:
! 1004:
! 1005: /*************************************************
! 1006: * Study a compiled expression *
! 1007: *************************************************/
! 1008:
! 1009: /* This function is handed a compiled expression that it must study to produce
! 1010: information that will speed up the matching. It returns a pcre_extra block
! 1011: which then gets handed back to pcre_exec().
! 1012:
! 1013: Arguments:
! 1014: re points to the compiled expression
! 1015: options contains option bits
! 1016: errorptr points to where to place error messages;
! 1017: set NULL unless error
! 1018:
! 1019: Returns: pointer to a pcre_extra block, with study_data filled in and the
! 1020: appropriate flags set;
! 1021: NULL on error or if no optimization possible
! 1022: */
! 1023:
! 1024: PCRE_EXP_DEFN pcre_extra * PCRE_CALL_CONVENTION
! 1025: pcre_study(const pcre *external_re, int options, const char **errorptr)
! 1026: {
! 1027: int min;
! 1028: BOOL bits_set = FALSE;
! 1029: uschar start_bits[32];
! 1030: pcre_extra *extra;
! 1031: pcre_study_data *study;
! 1032: const uschar *tables;
! 1033: uschar *code;
! 1034: compile_data compile_block;
! 1035: const real_pcre *re = (const real_pcre *)external_re;
! 1036:
! 1037: *errorptr = NULL;
! 1038:
! 1039: if (re == NULL || re->magic_number != MAGIC_NUMBER)
! 1040: {
! 1041: *errorptr = "argument is not a compiled regular expression";
! 1042: return NULL;
! 1043: }
! 1044:
! 1045: if ((options & ~PUBLIC_STUDY_OPTIONS) != 0)
! 1046: {
! 1047: *errorptr = "unknown or incorrect option bit(s) set";
! 1048: return NULL;
! 1049: }
! 1050:
! 1051: code = (uschar *)re + re->name_table_offset +
! 1052: (re->name_count * re->name_entry_size);
! 1053:
! 1054: /* For an anchored pattern, or an unanchored pattern that has a first char, or
! 1055: a multiline pattern that matches only at "line starts", there is no point in
! 1056: seeking a list of starting bytes. */
! 1057:
! 1058: if ((re->options & PCRE_ANCHORED) == 0 &&
! 1059: (re->flags & (PCRE_FIRSTSET|PCRE_STARTLINE)) == 0)
! 1060: {
! 1061: /* Set the character tables in the block that is passed around */
! 1062:
! 1063: tables = re->tables;
! 1064: if (tables == NULL)
! 1065: (void)pcre_fullinfo(external_re, NULL, PCRE_INFO_DEFAULT_TABLES,
! 1066: (void *)(&tables));
! 1067:
! 1068: compile_block.lcc = tables + lcc_offset;
! 1069: compile_block.fcc = tables + fcc_offset;
! 1070: compile_block.cbits = tables + cbits_offset;
! 1071: compile_block.ctypes = tables + ctypes_offset;
! 1072:
! 1073: /* See if we can find a fixed set of initial characters for the pattern. */
! 1074:
! 1075: memset(start_bits, 0, 32 * sizeof(uschar));
! 1076: bits_set = set_start_bits(code, start_bits,
! 1077: (re->options & PCRE_CASELESS) != 0, (re->options & PCRE_UTF8) != 0,
! 1078: &compile_block) == SSB_DONE;
! 1079: }
! 1080:
! 1081: /* Find the minimum length of subject string. */
! 1082:
! 1083: min = find_minlength(code, code, re->options);
! 1084:
! 1085: /* Return NULL if no optimization is possible. */
! 1086:
! 1087: if (!bits_set && min < 0) return NULL;
! 1088:
! 1089: /* Get a pcre_extra block and a pcre_study_data block. The study data is put in
! 1090: the latter, which is pointed to by the former, which may also get additional
! 1091: data set later by the calling program. At the moment, the size of
! 1092: pcre_study_data is fixed. We nevertheless save it in a field for returning via
! 1093: the pcre_fullinfo() function so that if it becomes variable in the future, we
! 1094: don't have to change that code. */
! 1095:
! 1096: extra = (pcre_extra *)(pcre_malloc)
! 1097: (sizeof(pcre_extra) + sizeof(pcre_study_data));
! 1098:
! 1099: if (extra == NULL)
! 1100: {
! 1101: *errorptr = "failed to get memory";
! 1102: return NULL;
! 1103: }
! 1104:
! 1105: study = (pcre_study_data *)((char *)extra + sizeof(pcre_extra));
! 1106: extra->flags = PCRE_EXTRA_STUDY_DATA;
! 1107: extra->study_data = study;
! 1108:
! 1109: study->size = sizeof(pcre_study_data);
! 1110: study->flags = 0;
! 1111:
! 1112: if (bits_set)
! 1113: {
! 1114: study->flags |= PCRE_STUDY_MAPPED;
! 1115: memcpy(study->start_bits, start_bits, sizeof(start_bits));
! 1116: }
! 1117:
! 1118: if (min >= 0)
! 1119: {
! 1120: study->flags |= PCRE_STUDY_MINLEN;
! 1121: study->minlength = min;
! 1122: }
! 1123:
! 1124: return extra;
! 1125: }
! 1126:
! 1127: /* 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