glib/pcre/pcre_study.c

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