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