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

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