git.sur5r.net Git - openldap/blob - libraries/liblunicode/ure/ure.c

   1 /*
   2  * Copyright 1997, 1998, 1999 Computing Research Labs,
   3  * New Mexico State University
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a
   6  * copy of this software and associated documentation files (the "Software"),
   7  * to deal in the Software without restriction, including without limitation
   8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
   9  * and/or sell copies of the Software, and to permit persons to whom the
  10  * Software is furnished to do so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in
  13  * all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  18  * THE COMPUTING RESEARCH LAB OR NEW MEXICO STATE UNIVERSITY BE LIABLE FOR ANY
  19  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT
  20  * OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR
  21  * THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  22  */
  23 #ifndef lint
  24 static char rcsid[] = "$Id: ure.c,v 1.2 1999/09/21 15:47:43 mleisher Exp $";
  25 #endif
  26
  27 #include "portable.h"
  28
  29 #include <stdlib.h>
  30 #include <ac/unistd.h>
  31 #include <ac/string.h>
  32
  33 #include "ure.h"
  34
  35 /*
  36  * Flags used internally in the DFA.
  37  */
  38 #define _URE_DFA_CASEFOLD  0x01
  39 #define _URE_DFA_BLANKLINE 0x02
  40
  41 static unsigned long cclass_flags[] = {
  42     0,
  43     _URE_NONSPACING,
  44     _URE_COMBINING,
  45     _URE_NUMDIGIT,
  46     _URE_NUMOTHER,
  47     _URE_SPACESEP,
  48     _URE_LINESEP,
  49     _URE_PARASEP,
  50     _URE_CNTRL,
  51     _URE_PUA,
  52     _URE_UPPER,
  53     _URE_LOWER,
  54     _URE_TITLE,
  55     _URE_MODIFIER,
  56     _URE_OTHERLETTER,
  57     _URE_DASHPUNCT,
  58     _URE_OPENPUNCT,
  59     _URE_CLOSEPUNCT,
  60     _URE_OTHERPUNCT,
  61     _URE_MATHSYM,
  62     _URE_CURRENCYSYM,
  63     _URE_OTHERSYM,
  64     _URE_LTR,
  65     _URE_RTL,
  66     _URE_EURONUM,
  67     _URE_EURONUMSEP,
  68     _URE_EURONUMTERM,
  69     _URE_ARABNUM,
  70     _URE_COMMONSEP,
  71     _URE_BLOCKSEP,
  72     _URE_SEGMENTSEP,
  73     _URE_WHITESPACE,
  74     _URE_OTHERNEUT,
  75 };
  76
  77 /*
  78  * Symbol types for the DFA.
  79  */
  80 #define _URE_ANY_CHAR   1
  81 #define _URE_CHAR       2
  82 #define _URE_CCLASS     3
  83 #define _URE_NCCLASS    4
  84 #define _URE_BOL_ANCHOR 5
  85 #define _URE_EOL_ANCHOR 6
  86
  87 /*
  88  * Op codes for converting the NFA to a DFA.
  89  */
  90 #define _URE_SYMBOL     10
  91 #define _URE_PAREN      11
  92 #define _URE_QUEST      12
  93 #define _URE_STAR       13
  94 #define _URE_PLUS       14
  95 #define _URE_ONE        15
  96 #define _URE_AND        16
  97 #define _URE_OR         17
  98
  99 #define _URE_NOOP       0xffff
 100
 101 #define _URE_REGSTART 0x8000
 102 #define _URE_REGEND   0x4000
 103
 104 /*
 105  * Structure used to handle a compacted range of characters.
 106  */
 107 typedef struct {
 108     ucs4_t min_code;
 109     ucs4_t max_code;
 110 } _ure_range_t;
 111
 112 typedef struct {
 113     _ure_range_t *ranges;
 114     ucs2_t ranges_used;
 115     ucs2_t ranges_size;
 116 } _ure_ccl_t;
 117
 118 typedef union {
 119     ucs4_t chr;
 120     _ure_ccl_t ccl;
 121 } _ure_sym_t;
 122
 123 /*
 124  * This is a general element structure used for expressions and stack
 125  * elements.
 126  */
 127 typedef struct {
 128     ucs2_t reg;
 129     ucs2_t onstack;
 130     ucs2_t type;
 131     ucs2_t lhs;
 132     ucs2_t rhs;
 133 } _ure_elt_t;
 134
 135 /*
 136  * This is a structure used to track a list or a stack of states.
 137  */
 138 typedef struct {
 139     ucs2_t *slist;
 140     ucs2_t slist_size;
 141     ucs2_t slist_used;
 142 } _ure_stlist_t;
 143
 144 /*
 145  * Structure to track the list of unique states for a symbol
 146  * during reduction.
 147  */
 148 typedef struct {
 149     ucs2_t id;
 150     ucs2_t type;
 151     unsigned long mods;
 152     unsigned long props;
 153     _ure_sym_t sym;
 154     _ure_stlist_t states;
 155 } _ure_symtab_t;
 156
 157 /*
 158  * Structure to hold a single state.
 159  */
 160 typedef struct {
 161     ucs2_t id;
 162     ucs2_t accepting;
 163     ucs2_t pad;
 164     _ure_stlist_t st;
 165     _ure_elt_t *trans;
 166     ucs2_t trans_size;
 167     ucs2_t trans_used;
 168 } _ure_state_t;
 169
 170 /*
 171  * Structure used for keeping lists of states.
 172  */
 173 typedef struct {
 174     _ure_state_t *states;
 175     ucs2_t states_size;
 176     ucs2_t states_used;
 177 } _ure_statetable_t;
 178
 179 /*
 180  * Structure to track pairs of DFA states when equivalent states are
 181  * merged.
 182  */
 183 typedef struct {
 184     ucs2_t l;
 185     ucs2_t r;
 186 } _ure_equiv_t;
 187
 188 /*
 189  * Structure used for constructing the NFA and reducing to a minimal DFA.
 190  */
 191 typedef struct _ure_buffer_t {
 192     int reducing;
 193     int error;
 194     unsigned long flags;
 195
 196     _ure_stlist_t stack;
 197
 198     /*
 199      * Table of unique symbols encountered.
 200      */
 201     _ure_symtab_t *symtab;
 202     ucs2_t symtab_size;
 203     ucs2_t symtab_used;
 204
 205     /*
 206      * Tracks the unique expressions generated for the NFA and when the NFA is
 207      * reduced.
 208      */
 209     _ure_elt_t *expr;
 210     ucs2_t expr_used;
 211     ucs2_t expr_size;
 212
 213     /*
 214      * The reduced table of unique groups of NFA states.
 215      */
 216     _ure_statetable_t states;
 217
 218     /*
 219      * Tracks states when equivalent states are merged.
 220      */
 221     _ure_equiv_t *equiv;
 222     ucs2_t equiv_used;
 223     ucs2_t equiv_size;
 224 } _ure_buffer_t;
 225
 226 typedef struct {
 227     ucs2_t symbol;
 228     ucs2_t next_state;
 229 } _ure_trans_t;
 230
 231 typedef struct {
 232     ucs2_t accepting;
 233     ucs2_t ntrans;
 234     _ure_trans_t *trans;
 235 } _ure_dstate_t;
 236
 237 typedef struct _ure_dfa_t {
 238     unsigned long flags;
 239
 240     _ure_symtab_t *syms;
 241     ucs2_t nsyms;
 242
 243     _ure_dstate_t *states;
 244     ucs2_t nstates;
 245
 246     _ure_trans_t *trans;
 247     ucs2_t ntrans;
 248 } _ure_dfa_t;
 249
 250 /*************************************************************************
 251  *
 252  * Functions.
 253  *
 254  *************************************************************************/
 255
 256 static void
 257 _ure_memmove(char *dest, char *src, unsigned long bytes)
 258 {
 259     long i, j;
 260
 261     i = (long) bytes;
 262     j = i & 7;
 263     i = (i + 7) >> 3;
 264
 265     /*
 266      * Do a memmove using Ye Olde Duff's Device for efficiency.
 267      */
 268     if (src < dest) {
 269         src += bytes;
 270         dest += bytes;
 271
 272         switch (j) {
 273           case 0: do {
 274               *--dest = *--src;
 275             case 7: *--dest = *--src;
 276             case 6: *--dest = *--src;
 277             case 5: *--dest = *--src;
 278             case 4: *--dest = *--src;
 279             case 3: *--dest = *--src;
 280             case 2: *--dest = *--src;
 281             case 1: *--dest = *--src;
 282           } while (--i > 0);
 283         }
 284     } else if (src > dest) {
 285         switch (j) {
 286           case 0: do {
 287               *dest++ = *src++;
 288             case 7: *dest++ = *src++;
 289             case 6: *dest++ = *src++;
 290             case 5: *dest++ = *src++;
 291             case 4: *dest++ = *src++;
 292             case 3: *dest++ = *src++;
 293             case 2: *dest++ = *src++;
 294             case 1: *dest++ = *src++;
 295           } while (--i > 0);
 296         }
 297     }
 298 }
 299
 300 static void
 301 _ure_push(ucs2_t v, _ure_buffer_t *b)
 302 {
 303     _ure_stlist_t *s;
 304
 305     if (b == 0)
 306       return;
 307
 308     /*
 309      * If the `reducing' parameter is non-zero, check to see if the value
 310      * passed is already on the stack.
 311      */
 312     if (b->reducing != 0 && b->expr[v].onstack != 0)
 313       return;
 314
 315     s = &b->stack;
 316     if (s->slist_used == s->slist_size) {
 317         if (s->slist_size == 0)
 318           s->slist = (ucs2_t *) malloc(sizeof(ucs2_t) << 3);
 319         else
 320           s->slist = (ucs2_t *) realloc((char *) s->slist,
 321                                         sizeof(ucs2_t) * (s->slist_size + 8));
 322         s->slist_size += 8;
 323     }
 324     s->slist[s->slist_used++] = v;
 325
 326     /*
 327      * If the `reducing' parameter is non-zero, flag the element as being on
 328      * the stack.
 329      */
 330     if (b->reducing != 0)
 331       b->expr[v].onstack = 1;
 332 }
 333
 334 static ucs2_t
 335 _ure_peek(_ure_buffer_t *b)
 336 {
 337     if (b == 0 || b->stack.slist_used == 0)
 338       return _URE_NOOP;
 339
 340     return b->stack.slist[b->stack.slist_used - 1];
 341 }
 342
 343 static ucs2_t
 344 _ure_pop(_ure_buffer_t *b)
 345 {
 346     ucs2_t v;
 347
 348     if (b == 0 || b->stack.slist_used == 0)
 349       return _URE_NOOP;
 350
 351     v = b->stack.slist[--b->stack.slist_used];
 352     if (b->reducing)
 353       b->expr[v].onstack = 0;
 354
 355     return v;
 356 }
 357
 358 /*************************************************************************
 359  *
 360  * Start symbol parse functions.
 361  *
 362  *************************************************************************/
 363
 364 /*
 365  * Parse a comma-separated list of integers that represent character
 366  * properties.  Combine them into a mask that is returned in the `mask'
 367  * variable, and return the number of characters consumed.
 368  */
 369 static unsigned long
 370 _ure_prop_list(ucs2_t *pp, unsigned long limit, unsigned long *mask,
 371                _ure_buffer_t *b)
 372 {
 373     unsigned long n, m;
 374     ucs2_t *sp, *ep;
 375
 376     sp = pp;
 377     ep = sp + limit;
 378
 379     for (m = n = 0; b->error == _URE_OK && sp < ep; sp++) {
 380         if (*sp == ',') {
 381             /*
 382              * Encountered a comma, so select the next character property flag
 383              * and reset the number.
 384              */
 385             m |= cclass_flags[n];
 386             n = 0;
 387         } else if (*sp >= '0' && *sp <= '9')
 388           /*
 389            * Encountered a digit, so start or continue building the cardinal
 390            * that represents the character property flag.
 391            */
 392           n = (n * 10) + (*sp - '0');
 393         else
 394           /*
 395            * Encountered something that is not part of the property list.
 396            * Indicate that we are done.
 397            */
 398           break;
 399
 400         /*
 401          * If a property number greater than 32 occurs, then there is a
 402          * problem.  Most likely a missing comma separator.
 403          */
 404         if (n > 32)
 405           b->error = _URE_INVALID_PROPERTY;
 406     }
 407
 408     if (n != 0)
 409       m |= cclass_flags[n];
 410
 411     /*
 412      * Set the mask that represents the group of character properties.
 413      */
 414     *mask = m;
 415
 416     /*
 417      * Return the number of characters consumed.
 418      */
 419     return sp - pp;
 420 }
 421
 422 /*
 423  * Collect a hex number with 1 to 4 digits and return the number
 424  * of characters used.
 425  */
 426 static unsigned long
 427 _ure_hex(ucs2_t *np, unsigned long limit, ucs4_t *n)
 428 {
 429     ucs2_t i;
 430     ucs2_t *sp, *ep;
 431     ucs4_t nn;
 432
 433     sp = np;
 434     ep = sp + limit;
 435
 436     for (nn = 0, i = 0; i < 4 && sp < ep; i++, sp++) {
 437         if (*sp >= '0' && *sp <= '9')
 438           nn = (nn << 4) + (*sp - '0');
 439         else if (*sp >= 'A' && *sp <= 'F')
 440           nn = (nn << 4) + ((*sp - 'A') + 10);
 441         else if (*sp >= 'a' && *sp <= 'f')
 442           nn = (nn << 4) + ((*sp - 'a') + 10);
 443         else
 444           /*
 445            * Encountered something that is not a hex digit.
 446            */
 447           break;
 448     }
 449
 450     /*
 451      * Assign the character code collected and return the number of
 452      * characters used.
 453      */
 454     *n = nn;
 455
 456     return sp - np;
 457 }
 458
 459 /*
 460  * Insert a range into a character class, removing duplicates and ordering
 461  * them in increasing range-start order.
 462  */
 463 static void
 464 _ure_add_range(_ure_ccl_t *ccl, _ure_range_t *r, _ure_buffer_t *b)
 465 {
 466     ucs2_t i;
 467     ucs4_t tmp;
 468     _ure_range_t *rp;
 469
 470     /*
 471      * If the `casefold' flag is set, then make sure both endpoints of the
 472      * range are converted to lower case.
 473      */
 474     if (b->flags & _URE_DFA_CASEFOLD) {
 475         r->min_code = _ure_tolower(r->min_code);
 476         r->max_code = _ure_tolower(r->max_code);
 477     }
 478
 479     /*
 480      * Swap the range endpoints if they are not in increasing order.
 481      */
 482     if (r->min_code > r->max_code) {
 483         tmp = r->min_code;
 484         r->min_code = r->max_code;
 485         r->max_code = tmp;
 486     }
 487
 488     for (i = 0, rp = ccl->ranges;
 489          i < ccl->ranges_used && r->min_code < rp->min_code; i++, rp++) ;
 490
 491     /*
 492      * Check for a duplicate.
 493      */
 494     if (i < ccl->ranges_used &&
 495         r->min_code == rp->min_code && r->max_code == rp->max_code)
 496       return;
 497
 498     if (ccl->ranges_used == ccl->ranges_size) {
 499         if (ccl->ranges_size == 0)
 500           ccl->ranges = (_ure_range_t *) malloc(sizeof(_ure_range_t) << 3);
 501         else
 502           ccl->ranges = (_ure_range_t *)
 503               realloc((char *) ccl->ranges,
 504                       sizeof(_ure_range_t) * (ccl->ranges_size + 8));
 505         ccl->ranges_size += 8;
 506     }
 507
 508     rp = ccl->ranges + ccl->ranges_used;
 509
 510     if (i < ccl->ranges_used)
 511       _ure_memmove((char *) (rp + 1), (char *) rp,
 512                    sizeof(_ure_range_t) * (ccl->ranges_used - i));
 513
 514     ccl->ranges_used++;
 515     rp->min_code = r->min_code;
 516     rp->max_code = r->max_code;
 517 }
 518
 519 #define _URE_ALPHA_MASK  (_URE_UPPER|_URE_LOWER|_URE_OTHERLETTER|\
 520 _URE_MODIFIER|_URE_TITLE|_URE_NONSPACING|_URE_COMBINING)
 521 #define _URE_ALNUM_MASK  (_URE_ALPHA_MASK|_URE_NUMDIGIT)
 522 #define _URE_PUNCT_MASK  (_URE_DASHPUNCT|_URE_OPENPUNCT|_URE_CLOSEPUNCT|\
 523 _URE_OTHERPUNCT)
 524 #define _URE_GRAPH_MASK (_URE_NUMDIGIT|_URE_NUMOTHER|_URE_ALPHA_MASK|\
 525 _URE_MATHSYM|_URE_CURRENCYSYM|_URE_OTHERSYM)
 526 #define _URE_PRINT_MASK (_URE_GRAPH_MASK|_URE_SPACESEP)
 527 #define _URE_SPACE_MASK  (_URE_SPACESEP|_URE_LINESEP|_URE_PARASEP)
 528
 529 typedef void (*_ure_cclsetup_t)(
 530     _ure_symtab_t *sym,
 531     unsigned long mask,
 532     _ure_buffer_t *b
 533 );
 534
 535 typedef struct {
 536     ucs2_t key;
 537     unsigned long len;
 538     unsigned long next;
 539     _ure_cclsetup_t func;
 540     unsigned long mask;
 541 } _ure_trie_t;
 542
 543 static void
 544 _ure_ccl_setup(_ure_symtab_t *sym, unsigned long mask, _ure_buffer_t *b)
 545 {
 546     sym->props |= mask;
 547 }
 548
 549 static void
 550 _ure_space_setup(_ure_symtab_t *sym, unsigned long mask, _ure_buffer_t *b)
 551 {
 552     _ure_range_t range;
 553
 554     sym->props |= mask;
 555
 556     /*
 557      * Add the additional characters needed for handling isspace().
 558      */
 559     range.min_code = range.max_code = '\t';
 560     _ure_add_range(&sym->sym.ccl, &range, b);
 561     range.min_code = range.max_code = '\r';
 562     _ure_add_range(&sym->sym.ccl, &range, b);
 563     range.min_code = range.max_code = '\n';
 564     _ure_add_range(&sym->sym.ccl, &range, b);
 565     range.min_code = range.max_code = '\f';
 566     _ure_add_range(&sym->sym.ccl, &range, b);
 567     range.min_code = range.max_code = 0xfeff;
 568     _ure_add_range(&sym->sym.ccl, &range, b);
 569 }
 570
 571 static void
 572 _ure_xdigit_setup(_ure_symtab_t *sym, unsigned long mask, _ure_buffer_t *b)
 573 {
 574     _ure_range_t range;
 575
 576     /*
 577      * Add the additional characters needed for handling isxdigit().
 578      */
 579     range.min_code = '0';
 580     range.max_code = '9';
 581     _ure_add_range(&sym->sym.ccl, &range, b);
 582     range.min_code = 'A';
 583     range.max_code = 'F';
 584     _ure_add_range(&sym->sym.ccl, &range, b);
 585     range.min_code = 'a';
 586     range.max_code = 'f';
 587     _ure_add_range(&sym->sym.ccl, &range, b);
 588 }
 589
 590 static _ure_trie_t cclass_trie[] = {
 591     {0x003a, 1, 1, 0, 0},
 592     {0x0061, 9, 10, 0, 0},
 593     {0x0063, 8, 19, 0, 0},
 594     {0x0064, 7, 24, 0, 0},
 595     {0x0067, 6, 29, 0, 0},
 596     {0x006c, 5, 34, 0, 0},
 597     {0x0070, 4, 39, 0, 0},
 598     {0x0073, 3, 49, 0, 0},
 599     {0x0075, 2, 54, 0, 0},
 600     {0x0078, 1, 59, 0, 0},
 601     {0x006c, 1, 11, 0, 0},
 602     {0x006e, 2, 13, 0, 0},
 603     {0x0070, 1, 16, 0, 0},
 604     {0x0075, 1, 14, 0, 0},
 605     {0x006d, 1, 15, 0, 0},
 606     {0x003a, 1, 16, _ure_ccl_setup, _URE_ALNUM_MASK},
 607     {0x0068, 1, 17, 0, 0},
 608     {0x0061, 1, 18, 0, 0},
 609     {0x003a, 1, 19, _ure_ccl_setup, _URE_ALPHA_MASK},
 610     {0x006e, 1, 20, 0, 0},
 611     {0x0074, 1, 21, 0, 0},
 612     {0x0072, 1, 22, 0, 0},
 613     {0x006c, 1, 23, 0, 0},
 614     {0x003a, 1, 24, _ure_ccl_setup, _URE_CNTRL},
 615     {0x0069, 1, 25, 0, 0},
 616     {0x0067, 1, 26, 0, 0},
 617     {0x0069, 1, 27, 0, 0},
 618     {0x0074, 1, 28, 0, 0},
 619     {0x003a, 1, 29, _ure_ccl_setup, _URE_NUMDIGIT},
 620     {0x0072, 1, 30, 0, 0},
 621     {0x0061, 1, 31, 0, 0},
 622     {0x0070, 1, 32, 0, 0},
 623     {0x0068, 1, 33, 0, 0},
 624     {0x003a, 1, 34, _ure_ccl_setup, _URE_GRAPH_MASK},
 625     {0x006f, 1, 35, 0, 0},
 626     {0x0077, 1, 36, 0, 0},
 627     {0x0065, 1, 37, 0, 0},
 628     {0x0072, 1, 38, 0, 0},
 629     {0x003a, 1, 39, _ure_ccl_setup, _URE_LOWER},
 630     {0x0072, 2, 41, 0, 0},
 631     {0x0075, 1, 45, 0, 0},
 632     {0x0069, 1, 42, 0, 0},
 633     {0x006e, 1, 43, 0, 0},
 634     {0x0074, 1, 44, 0, 0},
 635     {0x003a, 1, 45, _ure_ccl_setup, _URE_PRINT_MASK},
 636     {0x006e, 1, 46, 0, 0},
 637     {0x0063, 1, 47, 0, 0},
 638     {0x0074, 1, 48, 0, 0},
 639     {0x003a, 1, 49, _ure_ccl_setup, _URE_PUNCT_MASK},
 640     {0x0070, 1, 50, 0, 0},
 641     {0x0061, 1, 51, 0, 0},
 642     {0x0063, 1, 52, 0, 0},
 643     {0x0065, 1, 53, 0, 0},
 644     {0x003a, 1, 54, _ure_space_setup, _URE_SPACE_MASK},
 645     {0x0070, 1, 55, 0, 0},
 646     {0x0070, 1, 56, 0, 0},
 647     {0x0065, 1, 57, 0, 0},
 648     {0x0072, 1, 58, 0, 0},
 649     {0x003a, 1, 59, _ure_ccl_setup, _URE_UPPER},
 650     {0x0064, 1, 60, 0, 0},
 651     {0x0069, 1, 61, 0, 0},
 652     {0x0067, 1, 62, 0, 0},
 653     {0x0069, 1, 63, 0, 0},
 654     {0x0074, 1, 64, 0, 0},
 655     {0x003a, 1, 65, _ure_xdigit_setup, 0},
 656 };
 657
 658 /*
 659  * Probe for one of the POSIX colon delimited character classes in the static
 660  * trie.
 661  */
 662 static unsigned long
 663 _ure_posix_ccl(ucs2_t *cp, unsigned long limit, _ure_symtab_t *sym,
 664                _ure_buffer_t *b)
 665 {
 666     int i;
 667     unsigned long n;
 668     _ure_trie_t *tp;
 669     ucs2_t *sp, *ep;
 670
 671     /*
 672      * If the number of characters left is less than 7, then this cannot be
 673      * interpreted as one of the colon delimited classes.
 674      */
 675     if (limit < 7)
 676       return 0;
 677
 678     sp = cp;
 679     ep = sp + limit;
 680     tp = cclass_trie;
 681     for (i = 0; sp < ep && i < 8; i++, sp++) {
 682         n = tp->len;
 683
 684         for (; n > 0 && tp->key != *sp; tp++, n--) ;
 685
 686         if (n == 0)
 687           return 0;
 688
 689         if (*sp == ':' && (i == 6 || i == 7)) {
 690             sp++;
 691             break;
 692         }
 693         if (sp + 1 < ep)
 694           tp = cclass_trie + tp->next;
 695     }
 696     if (tp->func == 0)
 697       return 0;
 698
 699     (*tp->func)(sym, tp->mask, b);
 700
 701     return sp - cp;
 702 }
 703
 704 /*
 705  * Construct a list of ranges and return the number of characters consumed.
 706  */
 707 static unsigned long
 708 _ure_cclass(ucs2_t *cp, unsigned long limit, _ure_symtab_t *symp,
 709             _ure_buffer_t *b)
 710 {
 711     int range_end;
 712     unsigned long n;
 713     ucs2_t *sp, *ep;
 714     ucs4_t c, last;
 715     _ure_ccl_t *cclp;
 716     _ure_range_t range;
 717
 718     sp = cp;
 719     ep = sp + limit;
 720
 721     if (*sp == '^') {
 722       symp->type = _URE_NCCLASS;
 723       sp++;
 724     } else
 725       symp->type = _URE_CCLASS;
 726
 727     for (last = 0, range_end = 0;
 728          b->error == _URE_OK && sp < ep && *sp != ']'; ) {
 729         c = *sp++;
 730         if (c == '\\') {
 731             if (sp == ep) {
 732                 /*
 733                  * The EOS was encountered when expecting the reverse solidus
 734                  * to be followed by the character it is escaping.  Set an
 735                  * error code and return the number of characters consumed up
 736                  * to this point.
 737                  */
 738                 b->error = _URE_UNEXPECTED_EOS;
 739                 return sp - cp;
 740             }
 741
 742             c = *sp++;
 743             switch (c) {
 744               case 'a':
 745                 c = 0x07;
 746                 break;
 747               case 'b':
 748                 c = 0x08;
 749                 break;
 750               case 'f':
 751                 c = 0x0c;
 752                 break;
 753               case 'n':
 754                 c = 0x0a;
 755                 break;
 756               case 'r':
 757                 c = 0x0d;
 758                 break;
 759               case 't':
 760                 c = 0x09;
 761                 break;
 762               case 'v':
 763                 c = 0x0b;
 764                 break;
 765               case 'p':
 766               case 'P':
 767                 sp += _ure_prop_list(sp, ep - sp, &symp->props, b);
 768                 /*
 769                  * Invert the bit mask of the properties if this is a negated
 770                  * character class or if 'P' is used to specify a list of
 771                  * character properties that should *not* match in a
 772                  * character class.
 773                  */
 774                 if (c == 'P')
 775                   symp->props = ~symp->props;
 776                 continue;
 777                 break;
 778               case 'x':
 779               case 'X':
 780               case 'u':
 781               case 'U':
 782                 if (sp < ep &&
 783                     ((*sp >= '0' && *sp <= '9') ||
 784                      (*sp >= 'A' && *sp <= 'F') ||
 785                      (*sp >= 'a' && *sp <= 'f')))
 786                   sp += _ure_hex(sp, ep - sp, &c);
 787             }
 788         } else if (c == ':') {
 789             /*
 790              * Probe for a POSIX colon delimited character class.
 791              */
 792             sp--;
 793             if ((n = _ure_posix_ccl(sp, ep - sp, symp, b)) == 0)
 794               sp++;
 795             else {
 796                 sp += n;
 797                 continue;
 798             }
 799         }
 800
 801         cclp = &symp->sym.ccl;
 802
 803         /*
 804          * Check to see if the current character is a low surrogate that needs
 805          * to be combined with a preceding high surrogate.
 806          */
 807         if (last != 0) {
 808             if (c >= 0xdc00 && c <= 0xdfff)
 809               /*
 810                * Construct the UTF16 character code.
 811                */
 812               c = 0x10000 + (((last & 0x03ff) << 10) | (c & 0x03ff));
 813             else {
 814                 /*
 815                  * Add the isolated high surrogate to the range.
 816                  */
 817                 if (range_end == 1)
 818                   range.max_code = last & 0xffff;
 819                 else
 820                   range.min_code = range.max_code = last & 0xffff;
 821
 822                 _ure_add_range(cclp, &range, b);
 823                 range_end = 0;
 824             }
 825         }
 826
 827         /*
 828          * Clear the last character code.
 829          */
 830         last = 0;
 831
 832         /*
 833          * This slightly awkward code handles the different cases needed to
 834          * construct a range.
 835          */
 836         if (c >= 0xd800 && c <= 0xdbff) {
 837             /*
 838              * If the high surrogate is followed by a range indicator, simply
 839              * add it as the range start.  Otherwise, save it in case the next
 840              * character is a low surrogate.
 841              */
 842             if (*sp == '-') {
 843                 sp++;
 844                 range.min_code = c;
 845                 range_end = 1;
 846             } else
 847               last = c;
 848         } else if (range_end == 1) {
 849             range.max_code = c;
 850             _ure_add_range(cclp, &range, b);
 851             range_end = 0;
 852         } else {
 853             range.min_code = range.max_code = c;
 854             if (*sp == '-') {
 855                 sp++;
 856                 range_end = 1;
 857             } else
 858               _ure_add_range(cclp, &range, b);
 859         }
 860     }
 861
 862     if (sp < ep && *sp == ']')
 863       sp++;
 864     else
 865       /*
 866        * The parse was not terminated by the character class close symbol
 867        * (']'), so set an error code.
 868        */
 869       b->error = _URE_CCLASS_OPEN;
 870
 871     return sp - cp;
 872 }
 873
 874 /*
 875  * Probe for a low surrogate hex code.
 876  */
 877 static unsigned long
 878 _ure_probe_ls(ucs2_t *ls, unsigned long limit, ucs4_t *c)
 879 {
 880     ucs4_t i, code;
 881     ucs2_t *sp, *ep;
 882
 883     for (i = code = 0, sp = ls, ep = sp + limit; i < 4 && sp < ep; sp++) {
 884         if (*sp >= '0' && *sp <= '9')
 885           code = (code << 4) + (*sp - '0');
 886         else if (*sp >= 'A' && *sp <= 'F')
 887           code = (code << 4) + ((*sp - 'A') + 10);
 888         else if (*sp >= 'a' && *sp <= 'f')
 889           code = (code << 4) + ((*sp - 'a') + 10);
 890         else
 891           break;
 892     }
 893
 894     *c = code;
 895     return (0xdc00 <= code && code <= 0xdfff) ? sp - ls : 0;
 896 }
 897
 898 static unsigned long
 899 _ure_compile_symbol(ucs2_t *sym, unsigned long limit, _ure_symtab_t *symp,
 900                     _ure_buffer_t *b)
 901 {
 902     ucs4_t c;
 903     ucs2_t *sp, *ep;
 904
 905     sp = sym;
 906     ep = sym + limit;
 907
 908     if ((c = *sp++) == '\\') {
 909
 910         if (sp == ep) {
 911             /*
 912              * The EOS was encountered when expecting the reverse solidus to
 913              * be followed by the character it is escaping.  Set an error code
 914              * and return the number of characters consumed up to this point.
 915              */
 916             b->error = _URE_UNEXPECTED_EOS;
 917             return sp - sym;
 918         }
 919
 920         c = *sp++;
 921         switch (c) {
 922           case 'p':
 923           case 'P':
 924             symp->type = (c == 'p') ? _URE_CCLASS : _URE_NCCLASS;
 925             sp += _ure_prop_list(sp, ep - sp, &symp->props, b);
 926             break;
 927           case 'a':
 928             symp->type = _URE_CHAR;
 929             symp->sym.chr = 0x07;
 930             break;
 931           case 'b':
 932             symp->type = _URE_CHAR;
 933             symp->sym.chr = 0x08;
 934             break;
 935           case 'f':
 936             symp->type = _URE_CHAR;
 937             symp->sym.chr = 0x0c;
 938             break;
 939           case 'n':
 940             symp->type = _URE_CHAR;
 941             symp->sym.chr = 0x0a;
 942             break;
 943           case 'r':
 944             symp->type = _URE_CHAR;
 945             symp->sym.chr = 0x0d;
 946             break;
 947           case 't':
 948             symp->type = _URE_CHAR;
 949             symp->sym.chr = 0x09;
 950             break;
 951           case 'v':
 952             symp->type = _URE_CHAR;
 953             symp->sym.chr = 0x0b;
 954             break;
 955           case 'x':
 956           case 'X':
 957           case 'u':
 958           case 'U':
 959             /*
 960              * Collect between 1 and 4 digits representing a UCS2 code.  Fall
 961              * through to the next case.
 962              */
 963             if (sp < ep &&
 964                 ((*sp >= '0' && *sp <= '9') ||
 965                  (*sp >= 'A' && *sp <= 'F') ||
 966                  (*sp >= 'a' && *sp <= 'f')))
 967               sp += _ure_hex(sp, ep - sp, &c);
 968             /* FALLTHROUGH */
 969           default:
 970             /*
 971              * Simply add an escaped character here.
 972              */
 973             symp->type = _URE_CHAR;
 974             symp->sym.chr = c;
 975         }
 976     } else if (c == '^' || c == '$')
 977       /*
 978        * Handle the BOL and EOL anchors.  This actually consists simply of
 979        * setting a flag that indicates that the user supplied anchor match
 980        * function should be called.  This needs to be done instead of simply
 981        * matching line/paragraph separators because beginning-of-text and
 982        * end-of-text tests are needed as well.
 983        */
 984       symp->type = (c == '^') ? _URE_BOL_ANCHOR : _URE_EOL_ANCHOR;
 985     else if (c == '[')
 986       /*
 987        * Construct a character class.
 988        */
 989       sp += _ure_cclass(sp, ep - sp, symp, b);
 990     else if (c == '.')
 991       symp->type = _URE_ANY_CHAR;
 992     else {
 993         symp->type = _URE_CHAR;
 994         symp->sym.chr = c;
 995     }
 996
 997     /*
 998      * If the symbol type happens to be a character and is a high surrogate,
 999      * then probe forward to see if it is followed by a low surrogate that
1000      * needs to be added.
1001      */
1002     if (sp < ep && symp->type == _URE_CHAR &&
1003         0xd800 <= symp->sym.chr && symp->sym.chr <= 0xdbff) {
1004
1005         if (0xdc00 <= *sp && *sp <= 0xdfff) {
1006             symp->sym.chr = 0x10000 + (((symp->sym.chr & 0x03ff) << 10) |
1007                                        (*sp & 0x03ff));
1008             sp++;
1009         } else if (*sp == '\\' && (*(sp + 1) == 'x' || *(sp + 1) == 'X' ||
1010                                  *(sp + 1) == 'u' || *(sp + 1) == 'U')) {
1011             sp += _ure_probe_ls(sp + 2, ep - (sp + 2), &c);
1012             if (0xdc00 <= c && c <= 0xdfff) {
1013                 /*
1014                  * Take into account the \[xu] in front of the hex code.
1015                  */
1016                 sp += 2;
1017                 symp->sym.chr = 0x10000 + (((symp->sym.chr & 0x03ff) << 10) |
1018                                            (c & 0x03ff));
1019             }
1020         }
1021     }
1022
1023     /*
1024      * Last, make sure any _URE_CHAR type symbols are changed to lower case if
1025      * the `casefold' flag is set.
1026      */
1027     if ((b->flags & _URE_DFA_CASEFOLD) && symp->type == _URE_CHAR)
1028       symp->sym.chr = _ure_tolower(symp->sym.chr);
1029
1030     /*
1031      * If the symbol constructed is anything other than one of the anchors,
1032      * make sure the _URE_DFA_BLANKLINE flag is removed.
1033      */
1034     if (symp->type != _URE_BOL_ANCHOR && symp->type != _URE_EOL_ANCHOR)
1035       b->flags &= ~_URE_DFA_BLANKLINE;
1036
1037     /*
1038      * Return the number of characters consumed.
1039      */
1040     return sp - sym;
1041 }
1042
1043 static int
1044 _ure_sym_neq(_ure_symtab_t *a, _ure_symtab_t *b)
1045 {
1046     if (a->type != b->type || a->mods != b->mods || a->props != b->props)
1047       return 1;
1048
1049     if (a->type == _URE_CCLASS || a->type == _URE_NCCLASS) {
1050         if (a->sym.ccl.ranges_used != b->sym.ccl.ranges_used)
1051           return 1;
1052         if (a->sym.ccl.ranges_used > 0 &&
1053             memcmp((char *) a->sym.ccl.ranges, (char *) b->sym.ccl.ranges,
1054                    sizeof(_ure_range_t) * a->sym.ccl.ranges_used) != 0)
1055           return 1;
1056     } else if (a->type == _URE_CHAR && a->sym.chr != b->sym.chr)
1057       return 1;
1058     return 0;
1059 }
1060
1061 /*
1062  * Construct a symbol, but only keep unique symbols.
1063  */
1064 static ucs2_t
1065 _ure_make_symbol(ucs2_t *sym, unsigned long limit, unsigned long *consumed,
1066                  _ure_buffer_t *b)
1067 {
1068     ucs2_t i;
1069     _ure_symtab_t *sp, symbol;
1070
1071     /*
1072      * Build the next symbol so we can test to see if it is already in the
1073      * symbol table.
1074      */
1075     (void) memset((char *) &symbol, 0, sizeof(_ure_symtab_t));
1076     *consumed = _ure_compile_symbol(sym, limit, &symbol, b);
1077
1078     /*
1079      * Check to see if the symbol exists.
1080      */
1081     for (i = 0, sp = b->symtab;
1082          i < b->symtab_used && _ure_sym_neq(&symbol, sp); i++, sp++) ;
1083
1084     if (i < b->symtab_used) {
1085         /*
1086          * Free up any ranges used for the symbol.
1087          */
1088         if ((symbol.type == _URE_CCLASS || symbol.type == _URE_NCCLASS) &&
1089             symbol.sym.ccl.ranges_size > 0)
1090           free((char *) symbol.sym.ccl.ranges);
1091
1092         return b->symtab[i].id;
1093     }
1094
1095     /*
1096      * Need to add the new symbol.
1097      */
1098     if (b->symtab_used == b->symtab_size) {
1099         if (b->symtab_size == 0)
1100           b->symtab = (_ure_symtab_t *) malloc(sizeof(_ure_symtab_t) << 3);
1101         else
1102           b->symtab = (_ure_symtab_t *)
1103               realloc((char *) b->symtab,
1104                       sizeof(_ure_symtab_t) * (b->symtab_size + 8));
1105         sp = b->symtab + b->symtab_size;
1106         (void) memset((char *) sp, 0, sizeof(_ure_symtab_t) << 3);
1107         b->symtab_size += 8;
1108     }
1109
1110     symbol.id = b->symtab_used++;
1111     (void) memcpy((char *) &b->symtab[symbol.id], (char *) &symbol,
1112                   sizeof(_ure_symtab_t));
1113
1114     return symbol.id;
1115 }
1116
1117 /*************************************************************************
1118  *
1119  * End symbol parse functions.
1120  *
1121  *************************************************************************/
1122
1123 static ucs2_t
1124 _ure_make_expr(ucs2_t type, ucs2_t lhs, ucs2_t rhs, _ure_buffer_t *b)
1125 {
1126     ucs2_t i;
1127
1128     if (b == 0)
1129       return _URE_NOOP;
1130
1131     /*
1132      * Determine if the expression already exists or not.
1133      */
1134     for (i = 0; i < b->expr_used; i++) {
1135         if (b->expr[i].type == type && b->expr[i].lhs == lhs &&
1136             b->expr[i].rhs == rhs)
1137           break;
1138     }
1139     if (i < b->expr_used)
1140       return i;
1141
1142     /*
1143      * Need to add a new expression.
1144      */
1145     if (b->expr_used == b->expr_size) {
1146         if (b->expr_size == 0)
1147           b->expr = (_ure_elt_t *) malloc(sizeof(_ure_elt_t) << 3);
1148         else
1149           b->expr = (_ure_elt_t *)
1150               realloc((char *) b->expr,
1151                       sizeof(_ure_elt_t) * (b->expr_size + 8));
1152         b->expr_size += 8;
1153     }
1154
1155     b->expr[b->expr_used].onstack = 0;
1156     b->expr[b->expr_used].type = type;
1157     b->expr[b->expr_used].lhs = lhs;
1158     b->expr[b->expr_used].rhs = rhs;
1159
1160     return b->expr_used++;
1161 }
1162
1163 static unsigned char spmap[] = {
1164     0x00, 0x00, 0x00, 0x00, 0x00, 0x0f, 0x00, 0x80, 0x00, 0x00, 0x00, 0x00,
1165     0x00, 0x00, 0x00, 0x10, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1166     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
1167 };
1168
1169 #define _ure_isspecial(cc) ((cc) > 0x20 && (cc) < 0x7f && \
1170                             (spmap[(cc) >> 3] & (1 << ((cc) & 7))))
1171
1172 /*
1173  * Convert the regular expression into an NFA in a form that will be easy to
1174  * reduce to a DFA.  The starting state for the reduction will be returned.
1175  */
1176 static ucs2_t
1177 _ure_re2nfa(ucs2_t *re, unsigned long relen, _ure_buffer_t *b)
1178 {
1179     ucs2_t c, state, top, sym, *sp, *ep;
1180     unsigned long used;
1181
1182     state = _URE_NOOP;
1183
1184     sp = re;
1185     ep = sp + relen;
1186     while (b->error == _URE_OK && sp < ep) {
1187         c = *sp++;
1188         switch (c) {
1189           case '(':
1190             _ure_push(_URE_PAREN, b);
1191             break;
1192           case ')':
1193             /*
1194              * Check for the case of too many close parentheses.
1195              */
1196             if (_ure_peek(b) == _URE_NOOP) {
1197                 b->error = _URE_UNBALANCED_GROUP;
1198                 break;
1199             }
1200
1201             while ((top = _ure_peek(b)) == _URE_AND || top == _URE_OR)
1202               /*
1203                * Make an expression with the AND or OR operator and its right
1204                * hand side.
1205                */
1206               state = _ure_make_expr(_ure_pop(b), _ure_pop(b), state, b);
1207
1208             /*
1209              * Remove the _URE_PAREN off the stack.
1210              */
1211             (void) _ure_pop(b);
1212             break;
1213           case '*':
1214             state = _ure_make_expr(_URE_STAR, state, _URE_NOOP, b);
1215             break;
1216           case '+':
1217             state = _ure_make_expr(_URE_PLUS, state, _URE_NOOP, b);
1218             break;
1219           case '?':
1220             state = _ure_make_expr(_URE_QUEST, state, _URE_NOOP, b);
1221             break;
1222           case '|':
1223             while ((top = _ure_peek(b)) == _URE_AND || top == _URE_OR)
1224               /*
1225                * Make an expression with the AND or OR operator and its right
1226                * hand side.
1227                */
1228               state = _ure_make_expr(_ure_pop(b), _ure_pop(b), state, b);
1229
1230             _ure_push(state, b);
1231             _ure_push(_URE_OR, b);
1232             break;
1233           default:
1234             sp--;
1235             sym = _ure_make_symbol(sp, ep - sp, &used, b);
1236             sp += used;
1237             state = _ure_make_expr(_URE_SYMBOL, sym, _URE_NOOP, b);
1238             break;
1239         }
1240
1241         if (c != '(' && c != '|' && sp < ep &&
1242             (!_ure_isspecial(*sp) || *sp == '(')) {
1243             _ure_push(state, b);
1244             _ure_push(_URE_AND, b);
1245         }
1246     }
1247     while ((top = _ure_peek(b)) == _URE_AND || top == _URE_OR)
1248       /*
1249        * Make an expression with the AND or OR operator and its right
1250        * hand side.
1251        */
1252       state = _ure_make_expr(_ure_pop(b), _ure_pop(b), state, b);
1253
1254     if (b->stack.slist_used > 0)
1255       b->error = _URE_UNBALANCED_GROUP;
1256
1257     return (b->error == _URE_OK) ? state : _URE_NOOP;
1258 }
1259
1260 static void
1261 _ure_add_symstate(ucs2_t sym, ucs2_t state, _ure_buffer_t *b)
1262 {
1263     ucs2_t i, *stp;
1264     _ure_symtab_t *sp;
1265
1266     /*
1267      * Locate the symbol in the symbol table so the state can be added.
1268      * If the symbol doesn't exist, then a real problem exists.
1269      */
1270     for (i = 0, sp = b->symtab; i < b->symtab_used && sym != sp->id;
1271          i++, sp++) ;
1272
1273     /*
1274      * Now find out if the state exists in the symbol's state list.
1275      */
1276     for (i = 0, stp = sp->states.slist;
1277          i < sp->states.slist_used && state > *stp; i++, stp++) ;
1278
1279     if (i == sp->states.slist_used || state < *stp) {
1280         /*
1281          * Need to add the state in order.
1282          */
1283         if (sp->states.slist_used == sp->states.slist_size) {
1284             if (sp->states.slist_size == 0)
1285               sp->states.slist = (ucs2_t *) malloc(sizeof(ucs2_t) << 3);
1286             else
1287               sp->states.slist = (ucs2_t *)
1288                   realloc((char *) sp->states.slist,
1289                           sizeof(ucs2_t) * (sp->states.slist_size + 8));
1290             sp->states.slist_size += 8;
1291         }
1292         if (i < sp->states.slist_used)
1293           (void) _ure_memmove((char *) (sp->states.slist + i + 1),
1294                               (char *) (sp->states.slist + i),
1295                               sizeof(ucs2_t) * (sp->states.slist_used - i));
1296         sp->states.slist[i] = state;
1297         sp->states.slist_used++;
1298     }
1299 }
1300
1301 static ucs2_t
1302 _ure_add_state(ucs2_t nstates, ucs2_t *states, _ure_buffer_t *b)
1303 {
1304     ucs2_t i;
1305     _ure_state_t *sp;
1306
1307     for (i = 0, sp = b->states.states; i < b->states.states_used; i++, sp++) {
1308         if (sp->st.slist_used == nstates &&
1309             memcmp((char *) states, (char *) sp->st.slist,
1310                    sizeof(ucs2_t) * nstates) == 0)
1311           break;
1312     }
1313
1314     if (i == b->states.states_used) {
1315         /*
1316          * Need to add a new DFA state (set of NFA states).
1317          */
1318         if (b->states.states_used == b->states.states_size) {
1319             if (b->states.states_size == 0)
1320               b->states.states = (_ure_state_t *)
1321                   malloc(sizeof(_ure_state_t) << 3);
1322             else
1323               b->states.states = (_ure_state_t *)
1324                   realloc((char *) b->states.states,
1325                           sizeof(_ure_state_t) * (b->states.states_size + 8));
1326             sp = b->states.states + b->states.states_size;
1327             (void) memset((char *) sp, 0, sizeof(_ure_state_t) << 3);
1328             b->states.states_size += 8;
1329         }
1330
1331         sp = b->states.states + b->states.states_used++;
1332         sp->id = i;
1333
1334         if (sp->st.slist_used + nstates > sp->st.slist_size) {
1335             if (sp->st.slist_size == 0)
1336               sp->st.slist = (ucs2_t *)
1337                   malloc(sizeof(ucs2_t) * (sp->st.slist_used + nstates));
1338             else
1339               sp->st.slist = (ucs2_t *)
1340                   realloc((char *) sp->st.slist,
1341                           sizeof(ucs2_t) * (sp->st.slist_used + nstates));
1342             sp->st.slist_size = sp->st.slist_used + nstates;
1343         }
1344         sp->st.slist_used = nstates;
1345         (void) memcpy((char *) sp->st.slist, (char *) states,
1346                       sizeof(ucs2_t) * nstates);
1347     }
1348
1349     /*
1350      * Return the ID of the DFA state representing a group of NFA states.
1351      */
1352     return i;
1353 }
1354
1355 static void
1356 _ure_reduce(ucs2_t start, _ure_buffer_t *b)
1357 {
1358     ucs2_t i, j, state, eval, syms, rhs;
1359     ucs2_t s1, s2, ns1, ns2;
1360     _ure_state_t *sp;
1361     _ure_symtab_t *smp;
1362
1363     b->reducing = 1;
1364
1365     /*
1366      * Add the starting state for the reduction.
1367      */
1368     _ure_add_state(1, &start, b);
1369
1370     /*
1371      * Process each set of NFA states that get created.
1372      */
1373     for (i = 0; i < b->states.states_used; i++) {
1374         sp = b->states.states + i;
1375
1376         /*
1377          * Push the current states on the stack.
1378          */
1379         for (j = 0; j < sp->st.slist_used; j++)
1380           _ure_push(sp->st.slist[j], b);
1381
1382         /*
1383          * Reduce the NFA states.
1384          */
1385         for (j = sp->accepting = syms = 0; j < b->stack.slist_used; j++) {
1386             state = b->stack.slist[j];
1387             eval = 1;
1388
1389             /*
1390              * This inner loop is the iterative equivalent of recursively
1391              * reducing subexpressions generated as a result of a reduction.
1392              */
1393             while (eval) {
1394                 switch (b->expr[state].type) {
1395                   case _URE_SYMBOL:
1396                     ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
1397                     _ure_add_symstate(b->expr[state].lhs, ns1, b);
1398                     syms++;
1399                     eval = 0;
1400                     break;
1401                   case _URE_ONE:
1402                     sp->accepting = 1;
1403                     eval = 0;
1404                     break;
1405                   case _URE_QUEST:
1406                     s1 = b->expr[state].lhs;
1407                     ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
1408                     state = _ure_make_expr(_URE_OR, ns1, s1, b);
1409                     break;
1410                   case _URE_PLUS:
1411                     s1 = b->expr[state].lhs;
1412                     ns1 = _ure_make_expr(_URE_STAR, s1, _URE_NOOP, b);
1413                     state = _ure_make_expr(_URE_AND, s1, ns1, b);
1414                     break;
1415                   case _URE_STAR:
1416                     s1 = b->expr[state].lhs;
1417                     ns1 = _ure_make_expr(_URE_ONE, _URE_NOOP, _URE_NOOP, b);
1418                     ns2 = _ure_make_expr(_URE_PLUS, s1, _URE_NOOP, b);
1419                     state = _ure_make_expr(_URE_OR, ns1, ns2, b);
1420                     break;
1421                   case _URE_OR:
1422                     s1 = b->expr[state].lhs;
1423                     s2 = b->expr[state].rhs;
1424                     _ure_push(s1, b);
1425                     _ure_push(s2, b);
1426                     eval = 0;
1427                     break;
1428                   case _URE_AND:
1429                     s1 = b->expr[state].lhs;
1430                     s2 = b->expr[state].rhs;
1431                     switch (b->expr[s1].type) {
1432                       case _URE_SYMBOL:
1433                         _ure_add_symstate(b->expr[s1].lhs, s2, b);
1434                         syms++;
1435                         eval = 0;
1436                         break;
1437                       case _URE_ONE:
1438                         state = s2;
1439                         break;
1440                       case _URE_QUEST:
1441                         ns1 = b->expr[s1].lhs;
1442                         ns2 = _ure_make_expr(_URE_AND, ns1, s2, b);
1443                         state = _ure_make_expr(_URE_OR, s2, ns2, b);
1444                         break;
1445                       case _URE_PLUS:
1446                         ns1 = b->expr[s1].lhs;
1447                         ns2 = _ure_make_expr(_URE_OR, s2, state, b);
1448                         state = _ure_make_expr(_URE_AND, ns1, ns2, b);
1449                         break;
1450                       case _URE_STAR:
1451                         ns1 = b->expr[s1].lhs;
1452                         ns2 = _ure_make_expr(_URE_AND, ns1, state, b);
1453                         state = _ure_make_expr(_URE_OR, s2, ns2, b);
1454                         break;
1455                       case _URE_OR:
1456                         ns1 = b->expr[s1].lhs;
1457                         ns2 = b->expr[s1].rhs;
1458                         ns1 = _ure_make_expr(_URE_AND, ns1, s2, b);
1459                         ns2 = _ure_make_expr(_URE_AND, ns2, s2, b);
1460                         state = _ure_make_expr(_URE_OR, ns1, ns2, b);
1461                         break;
1462                       case _URE_AND:
1463                         ns1 = b->expr[s1].lhs;
1464                         ns2 = b->expr[s1].rhs;
1465                         ns2 = _ure_make_expr(_URE_AND, ns2, s2, b);
1466                         state = _ure_make_expr(_URE_AND, ns1, ns2, b);
1467                         break;
1468                     }
1469                 }
1470             }
1471         }
1472
1473         /*
1474          * Clear the state stack.
1475          */
1476         while (_ure_pop(b) != _URE_NOOP) ;
1477
1478         /*
1479          * Reset the state pointer because the reduction may have moved it
1480          * during a reallocation.
1481          */
1482         sp = b->states.states + i;
1483
1484         /*
1485          * Generate the DFA states for the symbols collected during the
1486          * current reduction.
1487          */
1488         if (sp->trans_used + syms > sp->trans_size) {
1489             if (sp->trans_size == 0)
1490               sp->trans = (_ure_elt_t *)
1491                   malloc(sizeof(_ure_elt_t) * (sp->trans_used + syms));
1492             else
1493               sp->trans = (_ure_elt_t *)
1494                   realloc((char *) sp->trans,
1495                           sizeof(_ure_elt_t) * (sp->trans_used + syms));
1496             sp->trans_size = sp->trans_used + syms;
1497         }
1498
1499         /*
1500          * Go through the symbol table and generate the DFA state transitions
1501          * for each symbol that has collected NFA states.
1502          */
1503         for (j = syms = 0, smp = b->symtab; j < b->symtab_used; j++, smp++) {
1504             sp = b->states.states + i;
1505
1506             if (smp->states.slist_used > 0) {
1507                 sp->trans[syms].lhs = smp->id;
1508                 rhs = _ure_add_state(smp->states.slist_used,
1509                                      smp->states.slist, b);
1510                 /*
1511                  * Reset the state pointer in case the reallocation moves it
1512                  * in memory.
1513                  */
1514                 sp = b->states.states + i;
1515                 sp->trans[syms].rhs = rhs;
1516
1517                 smp->states.slist_used = 0;
1518                 syms++;
1519             }
1520         }
1521
1522         /*
1523          * Set the number of transitions actually used.
1524          */
1525         sp->trans_used = syms;
1526     }
1527     b->reducing = 0;
1528 }
1529
1530 static void
1531 _ure_add_equiv(ucs2_t l, ucs2_t r, _ure_buffer_t *b)
1532 {
1533     ucs2_t tmp;
1534
1535     l = b->states.states[l].id;
1536     r = b->states.states[r].id;
1537
1538     if (l == r)
1539       return;
1540
1541     if (l > r) {
1542         tmp = l;
1543         l = r;
1544         r = tmp;
1545     }
1546
1547     /*
1548      * Check to see if the equivalence pair already exists.
1549      */
1550     for (tmp = 0; tmp < b->equiv_used &&
1551              (b->equiv[tmp].l != l || b->equiv[tmp].r != r);
1552          tmp++) ;
1553
1554     if (tmp < b->equiv_used)
1555       return;
1556
1557     if (b->equiv_used == b->equiv_size) {
1558         if (b->equiv_size == 0)
1559           b->equiv = (_ure_equiv_t *) malloc(sizeof(_ure_equiv_t) << 3);
1560         else
1561           b->equiv = (_ure_equiv_t *) realloc((char *) b->equiv,
1562                                               sizeof(_ure_equiv_t) *
1563                                               (b->equiv_size + 8));
1564         b->equiv_size += 8;
1565     }
1566     b->equiv[b->equiv_used].l = l;
1567     b->equiv[b->equiv_used].r = r;
1568     b->equiv_used++;
1569 }
1570
1571 /*
1572  * Merge the DFA states that are equivalent.
1573  */
1574 static void
1575 _ure_merge_equiv(_ure_buffer_t *b)
1576 {
1577     ucs2_t i, j, k, eq, done;
1578     _ure_state_t *sp1, *sp2, *ls, *rs;
1579
1580     for (i = 0; i < b->states.states_used; i++) {
1581         sp1 = b->states.states + i;
1582         if (sp1->id != i)
1583           continue;
1584         for (j = 0; j < i; j++) {
1585             sp2 = b->states.states + j;
1586             if (sp2->id != j)
1587               continue;
1588             b->equiv_used = 0;
1589             _ure_add_equiv(i, j, b);
1590             for (eq = 0, done = 0; eq < b->equiv_used; eq++) {
1591                 ls = b->states.states + b->equiv[eq].l;
1592                 rs = b->states.states + b->equiv[eq].r;
1593                 if (ls->accepting != rs->accepting ||
1594                     ls->trans_used != rs->trans_used) {
1595                     done = 1;
1596                     break;
1597                 }
1598                 for (k = 0; k < ls->trans_used &&
1599                          ls->trans[k].lhs == rs->trans[k].lhs; k++) ;
1600                 if (k < ls->trans_used) {
1601                     done = 1;
1602                     break;
1603                 }
1604
1605                 for (k = 0; k < ls->trans_used; k++)
1606                   _ure_add_equiv(ls->trans[k].rhs, rs->trans[k].rhs, b);
1607             }
1608             if (done == 0)
1609               break;
1610         }
1611         for (eq = 0; j < i && eq < b->equiv_used; eq++)
1612           b->states.states[b->equiv[eq].r].id =
1613               b->states.states[b->equiv[eq].l].id;
1614     }
1615
1616     /*
1617      * Renumber the states appropriately.
1618      */
1619     for (i = eq = 0, sp1 = b->states.states; i < b->states.states_used;
1620          sp1++, i++)
1621       sp1->id = (sp1->id == i) ? eq++ : b->states.states[sp1->id].id;
1622 }
1623
1624 /*************************************************************************
1625  *
1626  * API.
1627  *
1628  *************************************************************************/
1629
1630 ure_buffer_t
1631 ure_buffer_create(void)
1632 {
1633     ure_buffer_t b;
1634
1635     b = (ure_buffer_t) calloc(1, sizeof(_ure_buffer_t));
1636
1637     return b;
1638 }
1639
1640 void
1641 ure_buffer_free(ure_buffer_t buf)
1642 {
1643     unsigned long i;
1644
1645     if (buf == 0)
1646       return;
1647
1648     if (buf->stack.slist_size > 0)
1649       free((char *) buf->stack.slist);
1650
1651     if (buf->expr_size > 0)
1652       free((char *) buf->expr);
1653
1654     for (i = 0; i < buf->symtab_size; i++) {
1655         if (buf->symtab[i].states.slist_size > 0)
1656           free((char *) buf->symtab[i].states.slist);
1657     }
1658
1659     if (buf->symtab_size > 0)
1660       free((char *) buf->symtab);
1661
1662     for (i = 0; i < buf->states.states_size; i++) {
1663         if (buf->states.states[i].trans_size > 0)
1664           free((char *) buf->states.states[i].trans);
1665         if (buf->states.states[i].st.slist_size > 0)
1666           free((char *) buf->states.states[i].st.slist);
1667     }
1668
1669     if (buf->states.states_size > 0)
1670       free((char *) buf->states.states);
1671
1672     if (buf->equiv_size > 0)
1673       free((char *) buf->equiv);
1674
1675     free((char *) buf);
1676 }
1677
1678 ure_dfa_t
1679 ure_compile(ucs2_t *re, unsigned long relen, int casefold, ure_buffer_t buf)
1680 {
1681     ucs2_t i, j, state;
1682     _ure_state_t *sp;
1683     _ure_dstate_t *dsp;
1684     _ure_trans_t *tp;
1685     ure_dfa_t dfa;
1686
1687     if (re == 0 || *re == 0 || relen == 0 || buf == 0)
1688       return 0;
1689
1690     /*
1691      * Reset the various fields of the compilation buffer.  Default the flags
1692      * to indicate the presense of the "^$" pattern.  If any other pattern
1693      * occurs, then this flag will be removed.  This is done to catch this
1694      * special pattern and handle it specially when matching.
1695      */
1696     buf->flags = _URE_DFA_BLANKLINE | ((casefold) ? _URE_DFA_CASEFOLD : 0);
1697     buf->reducing = 0;
1698     buf->stack.slist_used = 0;
1699     buf->expr_used = 0;
1700
1701     for (i = 0; i < buf->symtab_used; i++)
1702       buf->symtab[i].states.slist_used = 0;
1703     buf->symtab_used = 0;
1704
1705     for (i = 0; i < buf->states.states_used; i++) {
1706         buf->states.states[i].st.slist_used = 0;
1707         buf->states.states[i].trans_used = 0;
1708     }
1709     buf->states.states_used = 0;
1710
1711     /*
1712      * Construct the NFA.  If this stage returns a 0, then an error occured or
1713      * an empty expression was passed.
1714      */
1715     if ((state = _ure_re2nfa(re, relen, buf)) == _URE_NOOP)
1716       return 0;
1717
1718     /*
1719      * Do the expression reduction to get the initial DFA.
1720      */
1721     _ure_reduce(state, buf);
1722
1723     /*
1724      * Merge all the equivalent DFA states.
1725      */
1726     _ure_merge_equiv(buf);
1727
1728     /*
1729      * Construct the minimal DFA.
1730      */
1731     dfa = (ure_dfa_t) malloc(sizeof(_ure_dfa_t));
1732     (void) memset((char *) dfa, 0, sizeof(_ure_dfa_t));
1733
1734     dfa->flags = buf->flags & (_URE_DFA_CASEFOLD|_URE_DFA_BLANKLINE);
1735
1736     /*
1737      * Free up the NFA state groups and transfer the symbols from the buffer
1738      * to the DFA.
1739      */
1740     for (i = 0; i < buf->symtab_size; i++) {
1741         if (buf->symtab[i].states.slist_size > 0)
1742           free((char *) buf->symtab[i].states.slist);
1743     }
1744     dfa->syms = buf->symtab;
1745     dfa->nsyms = buf->symtab_used;
1746
1747     buf->symtab_used = buf->symtab_size = 0;
1748
1749     /*
1750      * Collect the total number of states and transitions needed for the DFA.
1751      */
1752     for (i = state = 0, sp = buf->states.states; i < buf->states.states_used;
1753          i++, sp++) {
1754         if (sp->id == state) {
1755             dfa->nstates++;
1756             dfa->ntrans += sp->trans_used;
1757             state++;
1758         }
1759     }
1760
1761     /*
1762      * Allocate enough space for the states and transitions.
1763      */
1764     dfa->states = (_ure_dstate_t *) malloc(sizeof(_ure_dstate_t) *
1765                                            dfa->nstates);
1766     dfa->trans = (_ure_trans_t *) malloc(sizeof(_ure_trans_t) * dfa->ntrans);
1767
1768     /*
1769      * Actually transfer the DFA states from the buffer.
1770      */
1771     dsp = dfa->states;
1772     tp = dfa->trans;
1773     for (i = state = 0, sp = buf->states.states; i < buf->states.states_used;
1774          i++, sp++) {
1775         if (sp->id == state) {
1776             dsp->trans = tp;
1777             dsp->ntrans = sp->trans_used;
1778             dsp->accepting = sp->accepting;
1779
1780             /*
1781              * Add the transitions for the state.
1782              */
1783             for (j = 0; j < dsp->ntrans; j++, tp++) {
1784                 tp->symbol = sp->trans[j].lhs;
1785                 tp->next_state = buf->states.states[sp->trans[j].rhs].id;
1786             }
1787
1788             dsp++;
1789             state++;
1790         }
1791     }
1792
1793     return dfa;
1794 }
1795
1796 void
1797 ure_dfa_free(ure_dfa_t dfa)
1798 {
1799     ucs2_t i;
1800
1801     if (dfa == 0)
1802       return;
1803
1804     for (i = 0; i < dfa->nsyms; i++) {
1805         if ((dfa->syms[i].type == _URE_CCLASS ||
1806              dfa->syms[i].type == _URE_NCCLASS) &&
1807             dfa->syms[i].sym.ccl.ranges_size > 0)
1808           free((char *) dfa->syms[i].sym.ccl.ranges);
1809     }
1810     if (dfa->nsyms > 0)
1811       free((char *) dfa->syms);
1812
1813     if (dfa->nstates > 0)
1814       free((char *) dfa->states);
1815     if (dfa->ntrans > 0)
1816       free((char *) dfa->trans);
1817     free((char *) dfa);
1818 }
1819
1820 void
1821 ure_write_dfa(ure_dfa_t dfa, FILE *out)
1822 {
1823     ucs2_t i, j, k, h, l;
1824     _ure_dstate_t *sp;
1825     _ure_symtab_t *sym;
1826     _ure_range_t *rp;
1827
1828     if (dfa == 0 || out == 0)
1829       return;
1830
1831     /*
1832      * Write all the different character classes.
1833      */
1834     for (i = 0, sym = dfa->syms; i < dfa->nsyms; i++, sym++) {
1835         if (sym->type == _URE_CCLASS || sym->type == _URE_NCCLASS) {
1836             fprintf(out, "C%hd = ", sym->id);
1837             if (sym->sym.ccl.ranges_used > 0) {
1838                 putc('[', out);
1839                 if (sym->type == _URE_NCCLASS)
1840                   putc('^', out);
1841             }
1842             if (sym->props != 0) {
1843                 if (sym->type == _URE_NCCLASS)
1844                   fprintf(out, "\\P");
1845                 else
1846                   fprintf(out, "\\p");
1847                 for (k = h = 0; k < 32; k++) {
1848                     if (sym->props & (1 << k)) {
1849                         if (h != 0)
1850                           putc(',', out);
1851                         fprintf(out, "%hd", k + 1);
1852                         h = 1;
1853                     }
1854                 }
1855             }
1856             /*
1857              * Dump the ranges.
1858              */
1859             for (k = 0, rp = sym->sym.ccl.ranges;
1860                  k < sym->sym.ccl.ranges_used; k++, rp++) {
1861                 /*
1862                  * Check for UTF16 characters.
1863                  */
1864                 if (0x10000 <= rp->min_code &&
1865                     rp->min_code <= 0x10ffff) {
1866                     h = ((rp->min_code - 0x10000) >> 10) + 0xd800;
1867                     l = ((rp->min_code - 0x10000) & 1023) + 0xdc00;
1868                     fprintf(out, "\\x%04hX\\x%04hX", h, l);
1869                 } else
1870                   fprintf(out, "\\x%04lX", rp->min_code & 0xffff);
1871                 if (rp->max_code != rp->min_code) {
1872                     putc('-', out);
1873                     if (rp->max_code >= 0x10000 &&
1874                         rp->max_code <= 0x10ffff) {
1875                         h = ((rp->max_code - 0x10000) >> 10) + 0xd800;
1876                         l = ((rp->max_code - 0x10000) & 1023) + 0xdc00;
1877                         fprintf(out, "\\x%04hX\\x%04hX", h, l);
1878                     } else
1879                       fprintf(out, "\\x%04lX", rp->max_code & 0xffff);
1880                 }
1881             }
1882             if (sym->sym.ccl.ranges_used > 0)
1883               putc(']', out);
1884             putc('\n', out);
1885         }
1886     }
1887
1888     for (i = 0, sp = dfa->states; i < dfa->nstates; i++, sp++) {
1889         fprintf(out, "S%hd = ", i);
1890         if (sp->accepting) {
1891             fprintf(out, "1 ");
1892             if (sp->ntrans)
1893               fprintf(out, "| ");
1894         }
1895         for (j = 0; j < sp->ntrans; j++) {
1896             if (j > 0)
1897               fprintf(out, "| ");
1898
1899             sym = dfa->syms + sp->trans[j].symbol;
1900             switch (sym->type) {
1901               case _URE_CHAR:
1902                 if (0x10000 <= sym->sym.chr && sym->sym.chr <= 0x10ffff) {
1903                     /*
1904                      * Take care of UTF16 characters.
1905                      */
1906                     h = ((sym->sym.chr - 0x10000) >> 10) + 0xd800;
1907                     l = ((sym->sym.chr - 0x10000) & 1023) + 0xdc00;
1908                     fprintf(out, "\\x%04hX\\x%04hX ", h, l);
1909                 } else
1910                   fprintf(out, "\\x%04lX ", sym->sym.chr & 0xffff);
1911                 break;
1912               case _URE_ANY_CHAR:
1913                 fprintf(out, "<any> ");
1914                 break;
1915               case _URE_BOL_ANCHOR:
1916                 fprintf(out, "<bol-anchor> ");
1917                 break;
1918               case _URE_EOL_ANCHOR:
1919                 fprintf(out, "<eol-anchor> ");
1920                 break;
1921               case _URE_CCLASS:
1922               case _URE_NCCLASS:
1923                 fprintf(out, "[C%hd] ", sym->id);
1924                 break;
1925             }
1926             fprintf(out, "S%hd", sp->trans[j].next_state);
1927             if (j + 1 < sp->ntrans)
1928               putc(' ', out);
1929         }
1930         putc('\n', out);
1931     }
1932 }
1933
1934 #define _ure_issep(cc) ((cc) == '\n' || (cc) == '\r' || (cc) == 0x2028 ||\
1935                         (cc) == 0x2029)
1936
1937 int
1938 ure_exec(ure_dfa_t dfa, int flags, ucs2_t *text, unsigned long textlen,
1939          unsigned long *match_start, unsigned long *match_end)
1940 {
1941     int i, j, matched, found, skip;
1942     unsigned long ms, me;
1943     ucs4_t c;
1944     ucs2_t *sp, *ep, *lp;
1945     _ure_dstate_t *stp;
1946     _ure_symtab_t *sym;
1947     _ure_range_t *rp;
1948
1949     if (dfa == 0 || text == 0)
1950       return 0;
1951
1952     /*
1953      * Handle the special case of an empty string matching the "^$" pattern.
1954      */
1955     if (textlen == 0 && (dfa->flags & _URE_DFA_BLANKLINE)) {
1956         *match_start = *match_end = 0;
1957         return 1;
1958     }
1959
1960     sp = text;
1961     ep = sp + textlen;
1962
1963     ms = me = ~0;
1964
1965     stp = dfa->states;
1966
1967     for (found = skip = 0; found == 0 && sp < ep; ) {
1968         lp = sp;
1969         c = *sp++;
1970
1971         /*
1972          * Check to see if this is a high surrogate that should be
1973          * combined with a following low surrogate.
1974          */
1975         if (sp < ep && 0xd800 <= c && c <= 0xdbff &&
1976             0xdc00 <= *sp && *sp <= 0xdfff)
1977           c = 0x10000 + (((c & 0x03ff) << 10) | (*sp++ & 0x03ff));
1978
1979         /*
1980          * Determine if the character is non-spacing and should be skipped.
1981          */
1982         if (_ure_matches_properties(_URE_NONSPACING, c) &&
1983             (flags & URE_IGNORE_NONSPACING)) {
1984             sp++;
1985             continue;
1986         }
1987
1988         if (dfa->flags & _URE_DFA_CASEFOLD)
1989           c = _ure_tolower(c);
1990
1991         /*
1992          * See if one of the transitions matches.
1993          */
1994         for (i = 0, matched = 0; matched == 0 && i < stp->ntrans; i++) {
1995             sym = dfa->syms + stp->trans[i].symbol;
1996             switch (sym->type) {
1997               case _URE_ANY_CHAR:
1998                 if ((flags & URE_DOT_MATCHES_SEPARATORS) ||
1999                     !_ure_issep(c))
2000                   matched = 1;
2001                 break;
2002               case _URE_CHAR:
2003                 if (c == sym->sym.chr)
2004                   matched = 1;
2005                 break;
2006               case _URE_BOL_ANCHOR:
2007                 if (lp == text) {
2008                     sp = lp;
2009                     matched = 1;
2010                 } else if (_ure_issep(c)) {
2011                     if (c == '\r' && sp < ep && *sp == '\n')
2012                       sp++;
2013                     lp = sp;
2014                     matched = 1;
2015                 }
2016                 break;
2017               case _URE_EOL_ANCHOR:
2018                 if (_ure_issep(c)) {
2019                     /*
2020                      * Put the pointer back before the separator so the match
2021                      * end position will be correct.  This case will also
2022                      * cause the `sp' pointer to be advanced over the current
2023                      * separator once the match end point has been recorded.
2024                      */
2025                     sp = lp;
2026                     matched = 1;
2027                 }
2028                 break;
2029               case _URE_CCLASS:
2030               case _URE_NCCLASS:
2031                 if (sym->props != 0)
2032                   matched = _ure_matches_properties(sym->props, c);
2033                 for (j = 0, rp = sym->sym.ccl.ranges;
2034                      j < sym->sym.ccl.ranges_used; j++, rp++) {
2035                     if (rp->min_code <= c && c <= rp->max_code)
2036                       matched = 1;
2037                 }
2038                 if (sym->type == _URE_NCCLASS)
2039                   matched = !matched;
2040                 break;
2041             }
2042
2043             if (matched) {
2044                 if (ms == ~0)
2045                   ms = lp - text;
2046                 else
2047                   me = sp - text;
2048                 stp = dfa->states + stp->trans[i].next_state;
2049
2050                 /*
2051                  * If the match was an EOL anchor, adjust the pointer past the
2052                  * separator that caused the match.  The correct match
2053                  * position has been recorded already.
2054                  */
2055                 if (sym->type == _URE_EOL_ANCHOR) {
2056                     /*
2057                      * Skip the character that caused the match.
2058                      */
2059                     sp++;
2060
2061                     /*
2062                      * Handle the infamous CRLF situation.
2063                      */
2064                     if (sp < ep && c == '\r' && *sp == '\n')
2065                       sp++;
2066                 }
2067             }
2068         }
2069
2070         if (matched == 0) {
2071             if (stp->accepting == 0) {
2072                 /*
2073                  * If the last state was not accepting, then reset
2074                  * and start over.
2075                  */
2076                 stp = dfa->states;
2077                 ms = me = ~0;
2078             } else
2079               /*
2080                * The last state was accepting, so terminate the matching
2081                * loop to avoid more work.
2082                */
2083               found = 1;
2084         } else if (sp == ep) {
2085             if (!stp->accepting) {
2086                 /*
2087                  * This ugly hack is to make sure the end-of-line anchors
2088                  * match when the source text hits the end.  This is only done
2089                  * if the last subexpression matches.
2090                  */
2091                 for (i = 0; found == 0 && i < stp->ntrans; i++) {
2092                     sym = dfa->syms + stp->trans[i].symbol;
2093                     if (sym->type ==_URE_EOL_ANCHOR) {
2094                         stp = dfa->states + stp->trans[i].next_state;
2095                         if (stp->accepting) {
2096                             me = sp - text;
2097                             found = 1;
2098                         } else
2099                           break;
2100                     }
2101                 }
2102             } else {
2103                 /*
2104                  * Make sure any conditions that match all the way to the end
2105                  * of the string match.
2106                  */
2107                 found = 1;
2108                 me = sp - text;
2109             }
2110         }
2111     }
2112
2113     if (found == 0)
2114       ms = me = ~0;
2115
2116     *match_start = ms;
2117     *match_end = me;
2118
2119     return (ms != ~0) ? 1 : 0;
2120 }