1 /* dfa.c - deterministic extended regexp routines for GNU 2 Copyright 1988, 1998, 2000 Free Software Foundation, Inc. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 2, or (at your option) 7 any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software 16 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ 17 18 /* Written June, 1988 by Mike Haertel 19 Modified July, 1988 by Arthur David Olson to assist BMG speedups */ 20 21 /* $FreeBSD$ */ 22 23 #ifdef HAVE_CONFIG_H 24 #include <config.h> 25 #endif 26 27 #include <assert.h> 28 #include <ctype.h> 29 #include <stdio.h> 30 31 #include <sys/types.h> 32 #ifdef STDC_HEADERS 33 #include <stdlib.h> 34 #else 35 extern char *calloc(), *malloc(), *realloc(); 36 extern void free(); 37 #endif 38 39 #if defined(HAVE_STRING_H) || defined(STDC_HEADERS) 40 #include <string.h> 41 #else 42 #include <strings.h> 43 #endif 44 45 #if HAVE_SETLOCALE 46 # include <locale.h> 47 #endif 48 49 #if defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H && defined HAVE_MBRTOWC 50 /* We can handle multibyte string. */ 51 # define MBS_SUPPORT 52 #endif 53 54 #ifdef MBS_SUPPORT 55 # include <wchar.h> 56 # include <wctype.h> 57 #endif 58 59 #ifndef DEBUG /* use the same approach as regex.c */ 60 #undef assert 61 #define assert(e) 62 #endif /* DEBUG */ 63 64 #ifndef isgraph 65 #define isgraph(C) (isprint(C) && !isspace(C)) 66 #endif 67 68 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII)) 69 #define ISALPHA(C) isalpha(C) 70 #define ISUPPER(C) isupper(C) 71 #define ISLOWER(C) islower(C) 72 #define ISDIGIT(C) isdigit(C) 73 #define ISXDIGIT(C) isxdigit(C) 74 #define ISSPACE(C) isspace(C) 75 #define ISPUNCT(C) ispunct(C) 76 #define ISALNUM(C) isalnum(C) 77 #define ISPRINT(C) isprint(C) 78 #define ISGRAPH(C) isgraph(C) 79 #define ISCNTRL(C) iscntrl(C) 80 #else 81 #define ISALPHA(C) (isascii(C) && isalpha(C)) 82 #define ISUPPER(C) (isascii(C) && isupper(C)) 83 #define ISLOWER(C) (isascii(C) && islower(C)) 84 #define ISDIGIT(C) (isascii(C) && isdigit(C)) 85 #define ISXDIGIT(C) (isascii(C) && isxdigit(C)) 86 #define ISSPACE(C) (isascii(C) && isspace(C)) 87 #define ISPUNCT(C) (isascii(C) && ispunct(C)) 88 #define ISALNUM(C) (isascii(C) && isalnum(C)) 89 #define ISPRINT(C) (isascii(C) && isprint(C)) 90 #define ISGRAPH(C) (isascii(C) && isgraph(C)) 91 #define ISCNTRL(C) (isascii(C) && iscntrl(C)) 92 #endif 93 94 /* ISASCIIDIGIT differs from ISDIGIT, as follows: 95 - Its arg may be any int or unsigned int; it need not be an unsigned char. 96 - It's guaranteed to evaluate its argument exactly once. 97 - It's typically faster. 98 Posix 1003.2-1992 section 2.5.2.1 page 50 lines 1556-1558 says that 99 only '0' through '9' are digits. Prefer ISASCIIDIGIT to ISDIGIT unless 100 it's important to use the locale's definition of `digit' even when the 101 host does not conform to Posix. */ 102 #define ISASCIIDIGIT(c) ((unsigned) (c) - '0' <= 9) 103 104 /* If we (don't) have I18N. */ 105 /* glibc defines _ */ 106 #ifndef _ 107 # ifdef HAVE_LIBINTL_H 108 # include <libintl.h> 109 # ifndef _ 110 # define _(Str) gettext (Str) 111 # endif 112 # else 113 # define _(Str) (Str) 114 # endif 115 #endif 116 117 #include "regex.h" 118 #include "dfa.h" 119 #include "hard-locale.h" 120 121 /* HPUX, define those as macros in sys/param.h */ 122 #ifdef setbit 123 # undef setbit 124 #endif 125 #ifdef clrbit 126 # undef clrbit 127 #endif 128 129 static void dfamust PARAMS ((struct dfa *dfa)); 130 static void regexp PARAMS ((int toplevel)); 131 132 static ptr_t 133 xcalloc (size_t n, size_t s) 134 { 135 ptr_t r = calloc(n, s); 136 137 if (!r) 138 dfaerror(_("Memory exhausted")); 139 return r; 140 } 141 142 static ptr_t 143 xmalloc (size_t n) 144 { 145 ptr_t r = malloc(n); 146 147 assert(n != 0); 148 if (!r) 149 dfaerror(_("Memory exhausted")); 150 return r; 151 } 152 153 static ptr_t 154 xrealloc (ptr_t p, size_t n) 155 { 156 ptr_t r = realloc(p, n); 157 158 assert(n != 0); 159 if (!r) 160 dfaerror(_("Memory exhausted")); 161 return r; 162 } 163 164 #define CALLOC(p, t, n) ((p) = (t *) xcalloc((size_t)(n), sizeof (t))) 165 #define MALLOC(p, t, n) ((p) = (t *) xmalloc((n) * sizeof (t))) 166 #define REALLOC(p, t, n) ((p) = (t *) xrealloc((ptr_t) (p), (n) * sizeof (t))) 167 168 /* Reallocate an array of type t if nalloc is too small for index. */ 169 #define REALLOC_IF_NECESSARY(p, t, nalloc, index) \ 170 if ((index) >= (nalloc)) \ 171 { \ 172 do \ 173 (nalloc) *= 2; \ 174 while ((index) >= (nalloc)); \ 175 REALLOC(p, t, nalloc); \ 176 } 177 178 #ifdef DEBUG 179 180 static void 181 prtok (token t) 182 { 183 char const *s; 184 185 if (t < 0) 186 fprintf(stderr, "END"); 187 else if (t < NOTCHAR) 188 fprintf(stderr, "%c", t); 189 else 190 { 191 switch (t) 192 { 193 case EMPTY: s = "EMPTY"; break; 194 case BACKREF: s = "BACKREF"; break; 195 case BEGLINE: s = "BEGLINE"; break; 196 case ENDLINE: s = "ENDLINE"; break; 197 case BEGWORD: s = "BEGWORD"; break; 198 case ENDWORD: s = "ENDWORD"; break; 199 case LIMWORD: s = "LIMWORD"; break; 200 case NOTLIMWORD: s = "NOTLIMWORD"; break; 201 case QMARK: s = "QMARK"; break; 202 case STAR: s = "STAR"; break; 203 case PLUS: s = "PLUS"; break; 204 case CAT: s = "CAT"; break; 205 case OR: s = "OR"; break; 206 case ORTOP: s = "ORTOP"; break; 207 case LPAREN: s = "LPAREN"; break; 208 case RPAREN: s = "RPAREN"; break; 209 case CRANGE: s = "CRANGE"; break; 210 #ifdef MBS_SUPPORT 211 case ANYCHAR: s = "ANYCHAR"; break; 212 case MBCSET: s = "MBCSET"; break; 213 #endif /* MBS_SUPPORT */ 214 default: s = "CSET"; break; 215 } 216 fprintf(stderr, "%s", s); 217 } 218 } 219 #endif /* DEBUG */ 220 221 /* Stuff pertaining to charclasses. */ 222 223 static int 224 tstbit (unsigned b, charclass c) 225 { 226 return c[b / INTBITS] & 1 << b % INTBITS; 227 } 228 229 static void 230 setbit (unsigned b, charclass c) 231 { 232 c[b / INTBITS] |= 1 << b % INTBITS; 233 } 234 235 static void 236 clrbit (unsigned b, charclass c) 237 { 238 c[b / INTBITS] &= ~(1 << b % INTBITS); 239 } 240 241 static void 242 copyset (charclass src, charclass dst) 243 { 244 memcpy (dst, src, sizeof (charclass)); 245 } 246 247 static void 248 zeroset (charclass s) 249 { 250 memset (s, 0, sizeof (charclass)); 251 } 252 253 static void 254 notset (charclass s) 255 { 256 int i; 257 258 for (i = 0; i < CHARCLASS_INTS; ++i) 259 s[i] = ~s[i]; 260 } 261 262 static int 263 equal (charclass s1, charclass s2) 264 { 265 return memcmp (s1, s2, sizeof (charclass)) == 0; 266 } 267 268 /* A pointer to the current dfa is kept here during parsing. */ 269 static struct dfa *dfa; 270 271 /* Find the index of charclass s in dfa->charclasses, or allocate a new charclass. */ 272 static int 273 charclass_index (charclass s) 274 { 275 int i; 276 277 for (i = 0; i < dfa->cindex; ++i) 278 if (equal(s, dfa->charclasses[i])) 279 return i; 280 REALLOC_IF_NECESSARY(dfa->charclasses, charclass, dfa->calloc, dfa->cindex); 281 ++dfa->cindex; 282 copyset(s, dfa->charclasses[i]); 283 return i; 284 } 285 286 /* Syntax bits controlling the behavior of the lexical analyzer. */ 287 static reg_syntax_t syntax_bits, syntax_bits_set; 288 289 /* Flag for case-folding letters into sets. */ 290 static int case_fold; 291 292 /* End-of-line byte in data. */ 293 static unsigned char eolbyte; 294 295 /* Entry point to set syntax options. */ 296 void 297 dfasyntax (reg_syntax_t bits, int fold, unsigned char eol) 298 { 299 syntax_bits_set = 1; 300 syntax_bits = bits; 301 case_fold = fold; 302 eolbyte = eol; 303 } 304 305 /* Like setbit, but if case is folded, set both cases of a letter. */ 306 static void 307 setbit_case_fold (unsigned b, charclass c) 308 { 309 setbit (b, c); 310 if (case_fold) 311 { 312 if (ISUPPER (b)) 313 setbit (tolower (b), c); 314 else if (ISLOWER (b)) 315 setbit (toupper (b), c); 316 } 317 } 318 319 /* Lexical analyzer. All the dross that deals with the obnoxious 320 GNU Regex syntax bits is located here. The poor, suffering 321 reader is referred to the GNU Regex documentation for the 322 meaning of the @#%!@#%^!@ syntax bits. */ 323 324 static char const *lexstart; /* Pointer to beginning of input string. */ 325 static char const *lexptr; /* Pointer to next input character. */ 326 static int lexleft; /* Number of characters remaining. */ 327 static token lasttok; /* Previous token returned; initially END. */ 328 static int laststart; /* True if we're separated from beginning or (, | 329 only by zero-width characters. */ 330 static int parens; /* Count of outstanding left parens. */ 331 static int minrep, maxrep; /* Repeat counts for {m,n}. */ 332 static int hard_LC_COLLATE; /* Nonzero if LC_COLLATE is hard. */ 333 334 #ifdef MBS_SUPPORT 335 /* These variables are used only if (MB_CUR_MAX > 1). */ 336 static mbstate_t mbs; /* Mbstate for mbrlen(). */ 337 static ssize_t cur_mb_len; /* Byte length of the current scanning 338 multibyte character. Must also handle 339 negative result from mbrlen(). */ 340 static ssize_t cur_mb_index; /* Byte index of the current scanning multibyte 341 character. 342 343 singlebyte character : cur_mb_index = 0 344 multibyte character 345 1st byte : cur_mb_index = 1 346 2nd byte : cur_mb_index = 2 347 ... 348 nth byte : cur_mb_index = n */ 349 static unsigned char *mblen_buf;/* Correspond to the input buffer in dfaexec(). 350 Each element store the amount of remain 351 byte of corresponding multibyte character 352 in the input string. A element's value 353 is 0 if corresponding character is a 354 singlebyte chracter. 355 e.g. input : 'a', <mb(0)>, <mb(1)>, <mb(2)> 356 mblen_buf : 0, 3, 2, 1 357 */ 358 static wchar_t *inputwcs; /* Wide character representation of input 359 string in dfaexec(). 360 The length of this array is same as 361 the length of input string(char array). 362 inputstring[i] is a single-byte char, 363 or 1st byte of a multibyte char. 364 And inputwcs[i] is the codepoint. */ 365 static unsigned char const *buf_begin;/* refference to begin in dfaexec(). */ 366 static unsigned char const *buf_end; /* refference to end in dfaexec(). */ 367 #endif /* MBS_SUPPORT */ 368 369 #ifdef MBS_SUPPORT 370 /* This function update cur_mb_len, and cur_mb_index. 371 p points current lexptr, len is the remaining buffer length. */ 372 static void 373 update_mb_len_index (unsigned char const *p, size_t len) 374 { 375 /* If last character is a part of a multibyte character, 376 we update cur_mb_index. */ 377 if (cur_mb_index) 378 cur_mb_index = (cur_mb_index >= cur_mb_len)? 0 379 : cur_mb_index + 1; 380 381 /* If last character is a single byte character, or the 382 last portion of a multibyte character, we check whether 383 next character is a multibyte character or not. */ 384 if (! cur_mb_index) 385 { 386 cur_mb_len = mbrlen(p, len, &mbs); 387 if (cur_mb_len > 1) 388 /* It is a multibyte character. 389 cur_mb_len was already set by mbrlen(). */ 390 cur_mb_index = 1; 391 else if (cur_mb_len < 1) 392 /* Invalid sequence. We treat it as a singlebyte character. 393 cur_mb_index is aleady 0. */ 394 cur_mb_len = 1; 395 /* Otherwise, cur_mb_len == 1, it is a singlebyte character. 396 cur_mb_index is aleady 0. */ 397 } 398 } 399 #endif /* MBS_SUPPORT */ 400 401 #ifdef MBS_SUPPORT 402 /* Note that characters become unsigned here. */ 403 # define FETCH(c, eoferr) \ 404 { \ 405 if (! lexleft) \ 406 { \ 407 if (eoferr != 0) \ 408 dfaerror (eoferr); \ 409 else \ 410 return lasttok = END; \ 411 } \ 412 if (MB_CUR_MAX > 1) \ 413 update_mb_len_index(lexptr, lexleft); \ 414 (c) = (unsigned char) *lexptr++; \ 415 --lexleft; \ 416 } 417 418 /* This function fetch a wide character, and update cur_mb_len, 419 used only if the current locale is a multibyte environment. */ 420 static wint_t 421 fetch_wc (char const *eoferr) 422 { 423 wchar_t wc; 424 if (! lexleft) 425 { 426 if (eoferr != 0) 427 dfaerror (eoferr); 428 else 429 return WEOF; 430 } 431 432 cur_mb_len = mbrtowc(&wc, lexptr, lexleft, &mbs); 433 if (cur_mb_len <= 0) 434 { 435 cur_mb_len = 1; 436 wc = *lexptr; 437 } 438 lexptr += cur_mb_len; 439 lexleft -= cur_mb_len; 440 return wc; 441 } 442 #else 443 /* Note that characters become unsigned here. */ 444 # define FETCH(c, eoferr) \ 445 { \ 446 if (! lexleft) \ 447 { \ 448 if (eoferr != 0) \ 449 dfaerror (eoferr); \ 450 else \ 451 return lasttok = END; \ 452 } \ 453 (c) = (unsigned char) *lexptr++; \ 454 --lexleft; \ 455 } 456 #endif /* MBS_SUPPORT */ 457 458 #ifdef MBS_SUPPORT 459 /* Multibyte character handling sub-routin for lex. 460 This function parse a bracket expression and build a struct 461 mb_char_classes. */ 462 static void 463 parse_bracket_exp_mb () 464 { 465 wint_t wc, wc1, wc2; 466 467 /* Work area to build a mb_char_classes. */ 468 struct mb_char_classes *work_mbc; 469 int chars_al, range_sts_al, range_ends_al, ch_classes_al, 470 equivs_al, coll_elems_al; 471 472 REALLOC_IF_NECESSARY(dfa->mbcsets, struct mb_char_classes, 473 dfa->mbcsets_alloc, dfa->nmbcsets + 1); 474 /* dfa->multibyte_prop[] hold the index of dfa->mbcsets. 475 We will update dfa->multibyte_prop in addtok(), because we can't 476 decide the index in dfa->tokens[]. */ 477 478 /* Initialize work are */ 479 work_mbc = &(dfa->mbcsets[dfa->nmbcsets++]); 480 481 chars_al = 1; 482 range_sts_al = range_ends_al = 0; 483 ch_classes_al = equivs_al = coll_elems_al = 0; 484 MALLOC(work_mbc->chars, wchar_t, chars_al); 485 486 work_mbc->nchars = work_mbc->nranges = work_mbc->nch_classes = 0; 487 work_mbc->nequivs = work_mbc->ncoll_elems = 0; 488 work_mbc->chars = work_mbc->ch_classes = NULL; 489 work_mbc->range_sts = work_mbc->range_ends = NULL; 490 work_mbc->equivs = work_mbc->coll_elems = NULL; 491 492 wc = fetch_wc(_("Unbalanced [")); 493 if (wc == L'^') 494 { 495 wc = fetch_wc(_("Unbalanced [")); 496 work_mbc->invert = 1; 497 } 498 else 499 work_mbc->invert = 0; 500 do 501 { 502 wc1 = WEOF; /* mark wc1 is not initialized". */ 503 504 /* Note that if we're looking at some other [:...:] construct, 505 we just treat it as a bunch of ordinary characters. We can do 506 this because we assume regex has checked for syntax errors before 507 dfa is ever called. */ 508 if (wc == L'[' && (syntax_bits & RE_CHAR_CLASSES)) 509 { 510 #define BRACKET_BUFFER_SIZE 128 511 char str[BRACKET_BUFFER_SIZE]; 512 wc1 = wc; 513 wc = fetch_wc(_("Unbalanced [")); 514 515 /* If pattern contains `[[:', `[[.', or `[[='. */ 516 if (cur_mb_len == 1 && (wc == L':' || wc == L'.' || wc == L'=')) 517 { 518 unsigned char c; 519 unsigned char delim = (unsigned char)wc; 520 int len = 0; 521 for (;;) 522 { 523 if (! lexleft) 524 dfaerror (_("Unbalanced [")); 525 c = (unsigned char) *lexptr++; 526 --lexleft; 527 528 if ((c == delim && *lexptr == ']') || lexleft == 0) 529 break; 530 if (len < BRACKET_BUFFER_SIZE) 531 str[len++] = c; 532 else 533 /* This is in any case an invalid class name. */ 534 str[0] = '\0'; 535 } 536 str[len] = '\0'; 537 538 if (lexleft == 0) 539 { 540 REALLOC_IF_NECESSARY(work_mbc->chars, wchar_t, chars_al, 541 work_mbc->nchars + 2); 542 work_mbc->chars[work_mbc->nchars++] = L'['; 543 work_mbc->chars[work_mbc->nchars++] = delim; 544 break; 545 } 546 547 if (--lexleft, *lexptr++ != ']') 548 dfaerror (_("Unbalanced [")); 549 if (delim == ':') 550 /* build character class. */ 551 { 552 wctype_t wt; 553 /* Query the character class as wctype_t. */ 554 wt = wctype (str); 555 556 if (ch_classes_al == 0) 557 MALLOC(work_mbc->ch_classes, wchar_t, ++ch_classes_al); 558 REALLOC_IF_NECESSARY(work_mbc->ch_classes, wctype_t, 559 ch_classes_al, 560 work_mbc->nch_classes + 1); 561 work_mbc->ch_classes[work_mbc->nch_classes++] = wt; 562 563 } 564 else if (delim == '=' || delim == '.') 565 { 566 char *elem; 567 MALLOC(elem, char, len + 1); 568 strncpy(elem, str, len + 1); 569 570 if (delim == '=') 571 /* build equivalent class. */ 572 { 573 if (equivs_al == 0) 574 MALLOC(work_mbc->equivs, char*, ++equivs_al); 575 REALLOC_IF_NECESSARY(work_mbc->equivs, char*, 576 equivs_al, 577 work_mbc->nequivs + 1); 578 work_mbc->equivs[work_mbc->nequivs++] = elem; 579 } 580 581 if (delim == '.') 582 /* build collating element. */ 583 { 584 if (coll_elems_al == 0) 585 MALLOC(work_mbc->coll_elems, char*, ++coll_elems_al); 586 REALLOC_IF_NECESSARY(work_mbc->coll_elems, char*, 587 coll_elems_al, 588 work_mbc->ncoll_elems + 1); 589 work_mbc->coll_elems[work_mbc->ncoll_elems++] = elem; 590 } 591 } 592 wc1 = wc = WEOF; 593 } 594 else 595 /* We treat '[' as a normal character here. */ 596 { 597 wc2 = wc1; wc1 = wc; wc = wc2; /* swap */ 598 } 599 } 600 else 601 { 602 if (wc == L'\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) 603 wc = fetch_wc(("Unbalanced [")); 604 } 605 606 if (wc1 == WEOF) 607 wc1 = fetch_wc(_("Unbalanced [")); 608 609 if (wc1 == L'-') 610 /* build range characters. */ 611 { 612 wc2 = fetch_wc(_("Unbalanced [")); 613 if (wc2 == L']') 614 { 615 /* In the case [x-], the - is an ordinary hyphen, 616 which is left in c1, the lookahead character. */ 617 lexptr -= cur_mb_len; 618 lexleft += cur_mb_len; 619 wc2 = wc; 620 } 621 else 622 { 623 if (wc2 == L'\\' 624 && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) 625 wc2 = fetch_wc(_("Unbalanced [")); 626 wc1 = fetch_wc(_("Unbalanced [")); 627 } 628 629 if (range_sts_al == 0) 630 { 631 MALLOC(work_mbc->range_sts, wchar_t, ++range_sts_al); 632 MALLOC(work_mbc->range_ends, wchar_t, ++range_ends_al); 633 } 634 REALLOC_IF_NECESSARY(work_mbc->range_sts, wchar_t, 635 range_sts_al, work_mbc->nranges + 1); 636 work_mbc->range_sts[work_mbc->nranges] = (wchar_t)wc; 637 REALLOC_IF_NECESSARY(work_mbc->range_ends, wchar_t, 638 range_ends_al, work_mbc->nranges + 1); 639 work_mbc->range_ends[work_mbc->nranges++] = (wchar_t)wc2; 640 } 641 else if (wc != WEOF) 642 /* build normal characters. */ 643 { 644 REALLOC_IF_NECESSARY(work_mbc->chars, wchar_t, chars_al, 645 work_mbc->nchars + 1); 646 work_mbc->chars[work_mbc->nchars++] = (wchar_t)wc; 647 } 648 } 649 while ((wc = wc1) != L']'); 650 } 651 #endif /* MBS_SUPPORT */ 652 653 #ifdef __STDC__ 654 #define FUNC(F, P) static int F(int c) { return P(c); } 655 #else 656 #define FUNC(F, P) static int F(c) int c; { return P(c); } 657 #endif 658 659 FUNC(is_alpha, ISALPHA) 660 FUNC(is_upper, ISUPPER) 661 FUNC(is_lower, ISLOWER) 662 FUNC(is_digit, ISDIGIT) 663 FUNC(is_xdigit, ISXDIGIT) 664 FUNC(is_space, ISSPACE) 665 FUNC(is_punct, ISPUNCT) 666 FUNC(is_alnum, ISALNUM) 667 FUNC(is_print, ISPRINT) 668 FUNC(is_graph, ISGRAPH) 669 FUNC(is_cntrl, ISCNTRL) 670 671 static int 672 is_blank (int c) 673 { 674 return (c == ' ' || c == '\t'); 675 } 676 677 /* The following list maps the names of the Posix named character classes 678 to predicate functions that determine whether a given character is in 679 the class. The leading [ has already been eaten by the lexical analyzer. */ 680 static struct { 681 const char *name; 682 int (*pred) PARAMS ((int)); 683 } const prednames[] = { 684 { ":alpha:]", is_alpha }, 685 { ":upper:]", is_upper }, 686 { ":lower:]", is_lower }, 687 { ":digit:]", is_digit }, 688 { ":xdigit:]", is_xdigit }, 689 { ":space:]", is_space }, 690 { ":punct:]", is_punct }, 691 { ":alnum:]", is_alnum }, 692 { ":print:]", is_print }, 693 { ":graph:]", is_graph }, 694 { ":cntrl:]", is_cntrl }, 695 { ":blank:]", is_blank }, 696 { 0 } 697 }; 698 699 /* Return non-zero if C is a `word-constituent' byte; zero otherwise. */ 700 #define IS_WORD_CONSTITUENT(C) (ISALNUM(C) || (C) == '_') 701 702 static int 703 looking_at (char const *s) 704 { 705 size_t len; 706 707 len = strlen(s); 708 if (lexleft < len) 709 return 0; 710 return strncmp(s, lexptr, len) == 0; 711 } 712 713 static token 714 lex (void) 715 { 716 unsigned c, c1, c2; 717 int backslash = 0, invert; 718 charclass ccl; 719 int i; 720 721 /* Basic plan: We fetch a character. If it's a backslash, 722 we set the backslash flag and go through the loop again. 723 On the plus side, this avoids having a duplicate of the 724 main switch inside the backslash case. On the minus side, 725 it means that just about every case begins with 726 "if (backslash) ...". */ 727 for (i = 0; i < 2; ++i) 728 { 729 FETCH(c, 0); 730 #ifdef MBS_SUPPORT 731 if (MB_CUR_MAX > 1 && cur_mb_index) 732 /* If this is a part of a multi-byte character, we must treat 733 this byte data as a normal character. 734 e.g. In case of SJIS encoding, some character contains '\', 735 but they must not be backslash. */ 736 goto normal_char; 737 #endif /* MBS_SUPPORT */ 738 switch (c) 739 { 740 case '\\': 741 if (backslash) 742 goto normal_char; 743 if (lexleft == 0) 744 dfaerror(_("Unfinished \\ escape")); 745 backslash = 1; 746 break; 747 748 case '^': 749 if (backslash) 750 goto normal_char; 751 if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS 752 || lasttok == END 753 || lasttok == LPAREN 754 || lasttok == OR) 755 return lasttok = BEGLINE; 756 goto normal_char; 757 758 case '$': 759 if (backslash) 760 goto normal_char; 761 if (syntax_bits & RE_CONTEXT_INDEP_ANCHORS 762 || lexleft == 0 763 || (syntax_bits & RE_NO_BK_PARENS 764 ? lexleft > 0 && *lexptr == ')' 765 : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == ')') 766 || (syntax_bits & RE_NO_BK_VBAR 767 ? lexleft > 0 && *lexptr == '|' 768 : lexleft > 1 && lexptr[0] == '\\' && lexptr[1] == '|') 769 || ((syntax_bits & RE_NEWLINE_ALT) 770 && lexleft > 0 && *lexptr == '\n')) 771 return lasttok = ENDLINE; 772 goto normal_char; 773 774 case '1': 775 case '2': 776 case '3': 777 case '4': 778 case '5': 779 case '6': 780 case '7': 781 case '8': 782 case '9': 783 if (backslash && !(syntax_bits & RE_NO_BK_REFS)) 784 { 785 laststart = 0; 786 return lasttok = BACKREF; 787 } 788 goto normal_char; 789 790 case '`': 791 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 792 return lasttok = BEGLINE; /* FIXME: should be beginning of string */ 793 goto normal_char; 794 795 case '\'': 796 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 797 return lasttok = ENDLINE; /* FIXME: should be end of string */ 798 goto normal_char; 799 800 case '<': 801 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 802 return lasttok = BEGWORD; 803 goto normal_char; 804 805 case '>': 806 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 807 return lasttok = ENDWORD; 808 goto normal_char; 809 810 case 'b': 811 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 812 return lasttok = LIMWORD; 813 goto normal_char; 814 815 case 'B': 816 if (backslash && !(syntax_bits & RE_NO_GNU_OPS)) 817 return lasttok = NOTLIMWORD; 818 goto normal_char; 819 820 case '?': 821 if (syntax_bits & RE_LIMITED_OPS) 822 goto normal_char; 823 if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0)) 824 goto normal_char; 825 if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) 826 goto normal_char; 827 return lasttok = QMARK; 828 829 case '*': 830 if (backslash) 831 goto normal_char; 832 if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) 833 goto normal_char; 834 return lasttok = STAR; 835 836 case '+': 837 if (syntax_bits & RE_LIMITED_OPS) 838 goto normal_char; 839 if (backslash != ((syntax_bits & RE_BK_PLUS_QM) != 0)) 840 goto normal_char; 841 if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) 842 goto normal_char; 843 return lasttok = PLUS; 844 845 case '{': 846 if (!(syntax_bits & RE_INTERVALS)) 847 goto normal_char; 848 if (backslash != ((syntax_bits & RE_NO_BK_BRACES) == 0)) 849 goto normal_char; 850 if (!(syntax_bits & RE_CONTEXT_INDEP_OPS) && laststart) 851 goto normal_char; 852 853 if (syntax_bits & RE_NO_BK_BRACES) 854 { 855 /* Scan ahead for a valid interval; if it's not valid, 856 treat it as a literal '{'. */ 857 int lo = -1, hi = -1; 858 char const *p = lexptr; 859 char const *lim = p + lexleft; 860 for (; p != lim && ISASCIIDIGIT (*p); p++) 861 lo = (lo < 0 ? 0 : lo * 10) + *p - '0'; 862 if (p != lim && *p == ',') 863 while (++p != lim && ISASCIIDIGIT (*p)) 864 hi = (hi < 0 ? 0 : hi * 10) + *p - '0'; 865 else 866 hi = lo; 867 if (p == lim || *p != '}' 868 || lo < 0 || RE_DUP_MAX < hi || (0 <= hi && hi < lo)) 869 goto normal_char; 870 } 871 872 minrep = 0; 873 /* Cases: 874 {M} - exact count 875 {M,} - minimum count, maximum is infinity 876 {M,N} - M through N */ 877 FETCH(c, _("unfinished repeat count")); 878 if (ISASCIIDIGIT (c)) 879 { 880 minrep = c - '0'; 881 for (;;) 882 { 883 FETCH(c, _("unfinished repeat count")); 884 if (! ISASCIIDIGIT (c)) 885 break; 886 minrep = 10 * minrep + c - '0'; 887 } 888 } 889 else 890 dfaerror(_("malformed repeat count")); 891 if (c == ',') 892 { 893 FETCH (c, _("unfinished repeat count")); 894 if (! ISASCIIDIGIT (c)) 895 maxrep = -1; 896 else 897 { 898 maxrep = c - '0'; 899 for (;;) 900 { 901 FETCH (c, _("unfinished repeat count")); 902 if (! ISASCIIDIGIT (c)) 903 break; 904 maxrep = 10 * maxrep + c - '0'; 905 } 906 if (0 <= maxrep && maxrep < minrep) 907 dfaerror (_("malformed repeat count")); 908 } 909 } 910 else 911 maxrep = minrep; 912 if (!(syntax_bits & RE_NO_BK_BRACES)) 913 { 914 if (c != '\\') 915 dfaerror(_("malformed repeat count")); 916 FETCH(c, _("unfinished repeat count")); 917 } 918 if (c != '}') 919 dfaerror(_("malformed repeat count")); 920 laststart = 0; 921 return lasttok = REPMN; 922 923 case '|': 924 if (syntax_bits & RE_LIMITED_OPS) 925 goto normal_char; 926 if (backslash != ((syntax_bits & RE_NO_BK_VBAR) == 0)) 927 goto normal_char; 928 laststart = 1; 929 return lasttok = OR; 930 931 case '\n': 932 if (syntax_bits & RE_LIMITED_OPS 933 || backslash 934 || !(syntax_bits & RE_NEWLINE_ALT)) 935 goto normal_char; 936 laststart = 1; 937 return lasttok = OR; 938 939 case '(': 940 if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0)) 941 goto normal_char; 942 ++parens; 943 laststart = 1; 944 return lasttok = LPAREN; 945 946 case ')': 947 if (backslash != ((syntax_bits & RE_NO_BK_PARENS) == 0)) 948 goto normal_char; 949 if (parens == 0 && syntax_bits & RE_UNMATCHED_RIGHT_PAREN_ORD) 950 goto normal_char; 951 --parens; 952 laststart = 0; 953 return lasttok = RPAREN; 954 955 case '.': 956 if (backslash) 957 goto normal_char; 958 #ifdef MBS_SUPPORT 959 if (MB_CUR_MAX > 1) 960 { 961 /* In multibyte environment period must match with a single 962 character not a byte. So we use ANYCHAR. */ 963 laststart = 0; 964 return lasttok = ANYCHAR; 965 } 966 #endif /* MBS_SUPPORT */ 967 zeroset(ccl); 968 notset(ccl); 969 if (!(syntax_bits & RE_DOT_NEWLINE)) 970 clrbit(eolbyte, ccl); 971 if (syntax_bits & RE_DOT_NOT_NULL) 972 clrbit('\0', ccl); 973 laststart = 0; 974 return lasttok = CSET + charclass_index(ccl); 975 976 case 'w': 977 case 'W': 978 if (!backslash || (syntax_bits & RE_NO_GNU_OPS)) 979 goto normal_char; 980 zeroset(ccl); 981 for (c2 = 0; c2 < NOTCHAR; ++c2) 982 if (IS_WORD_CONSTITUENT(c2)) 983 setbit(c2, ccl); 984 if (c == 'W') 985 notset(ccl); 986 laststart = 0; 987 return lasttok = CSET + charclass_index(ccl); 988 989 case '[': 990 if (backslash) 991 goto normal_char; 992 laststart = 0; 993 #ifdef MBS_SUPPORT 994 if (MB_CUR_MAX > 1) 995 { 996 /* In multibyte environment a bracket expression may contain 997 multibyte characters, which must be treated as characters 998 (not bytes). So we parse it by parse_bracket_exp_mb(). */ 999 parse_bracket_exp_mb(); 1000 return lasttok = MBCSET; 1001 } 1002 #endif 1003 zeroset(ccl); 1004 FETCH(c, _("Unbalanced [")); 1005 if (c == '^') 1006 { 1007 FETCH(c, _("Unbalanced [")); 1008 invert = 1; 1009 } 1010 else 1011 invert = 0; 1012 do 1013 { 1014 /* Nobody ever said this had to be fast. :-) 1015 Note that if we're looking at some other [:...:] 1016 construct, we just treat it as a bunch of ordinary 1017 characters. We can do this because we assume 1018 regex has checked for syntax errors before 1019 dfa is ever called. */ 1020 if (c == '[' && (syntax_bits & RE_CHAR_CLASSES)) 1021 for (c1 = 0; prednames[c1].name; ++c1) 1022 if (looking_at(prednames[c1].name)) 1023 { 1024 int (*pred) PARAMS ((int)) = prednames[c1].pred; 1025 1026 for (c2 = 0; c2 < NOTCHAR; ++c2) 1027 if ((*pred)(c2)) 1028 setbit_case_fold (c2, ccl); 1029 lexptr += strlen(prednames[c1].name); 1030 lexleft -= strlen(prednames[c1].name); 1031 FETCH(c1, _("Unbalanced [")); 1032 goto skip; 1033 } 1034 if (c == '\\' && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) 1035 FETCH(c, _("Unbalanced [")); 1036 FETCH(c1, _("Unbalanced [")); 1037 if (c1 == '-') 1038 { 1039 FETCH(c2, _("Unbalanced [")); 1040 if (c2 == ']') 1041 { 1042 /* In the case [x-], the - is an ordinary hyphen, 1043 which is left in c1, the lookahead character. */ 1044 --lexptr; 1045 ++lexleft; 1046 } 1047 else 1048 { 1049 if (c2 == '\\' 1050 && (syntax_bits & RE_BACKSLASH_ESCAPE_IN_LISTS)) 1051 FETCH(c2, _("Unbalanced [")); 1052 FETCH(c1, _("Unbalanced [")); 1053 if (!hard_LC_COLLATE) { 1054 for (; c <= c2; c++) 1055 setbit_case_fold (c, ccl); 1056 } else { 1057 /* POSIX locales are painful - leave the decision to libc */ 1058 char expr[6] = { '[', c, '-', c2, ']', '\0' }; 1059 regex_t re; 1060 if (regcomp (&re, expr, case_fold ? REG_ICASE : 0) == REG_NOERROR) { 1061 for (c = 0; c < NOTCHAR; ++c) { 1062 char buf[2] = { c, '\0' }; 1063 regmatch_t mat; 1064 if (regexec (&re, buf, 1, &mat, 0) == REG_NOERROR 1065 && mat.rm_so == 0 && mat.rm_eo == 1) 1066 setbit_case_fold (c, ccl); 1067 } 1068 regfree (&re); 1069 } 1070 } 1071 continue; 1072 } 1073 } 1074 1075 setbit_case_fold (c, ccl); 1076 1077 skip: 1078 ; 1079 } 1080 while ((c = c1) != ']'); 1081 if (invert) 1082 { 1083 notset(ccl); 1084 if (syntax_bits & RE_HAT_LISTS_NOT_NEWLINE) 1085 clrbit(eolbyte, ccl); 1086 } 1087 return lasttok = CSET + charclass_index(ccl); 1088 1089 default: 1090 normal_char: 1091 laststart = 0; 1092 if (case_fold && ISALPHA(c)) 1093 { 1094 zeroset(ccl); 1095 setbit_case_fold (c, ccl); 1096 return lasttok = CSET + charclass_index(ccl); 1097 } 1098 return c; 1099 } 1100 } 1101 1102 /* The above loop should consume at most a backslash 1103 and some other character. */ 1104 abort(); 1105 return END; /* keeps pedantic compilers happy. */ 1106 } 1107 1108 /* Recursive descent parser for regular expressions. */ 1109 1110 static token tok; /* Lookahead token. */ 1111 static int depth; /* Current depth of a hypothetical stack 1112 holding deferred productions. This is 1113 used to determine the depth that will be 1114 required of the real stack later on in 1115 dfaanalyze(). */ 1116 1117 /* Add the given token to the parse tree, maintaining the depth count and 1118 updating the maximum depth if necessary. */ 1119 static void 1120 addtok (token t) 1121 { 1122 #ifdef MBS_SUPPORT 1123 if (MB_CUR_MAX > 1) 1124 { 1125 REALLOC_IF_NECESSARY(dfa->multibyte_prop, int, dfa->nmultibyte_prop, 1126 dfa->tindex); 1127 /* Set dfa->multibyte_prop. See struct dfa in dfa.h. */ 1128 if (t == MBCSET) 1129 dfa->multibyte_prop[dfa->tindex] = ((dfa->nmbcsets - 1) << 2) + 3; 1130 else if (t < NOTCHAR) 1131 dfa->multibyte_prop[dfa->tindex] 1132 = (cur_mb_len == 1)? 3 /* single-byte char */ 1133 : (((cur_mb_index == 1)? 1 : 0) /* 1st-byte of multibyte char */ 1134 + ((cur_mb_index == cur_mb_len)? 2 : 0)); /* last-byte */ 1135 else 1136 /* It may be unnecesssary, but it is safer to treat other 1137 symbols as singlebyte characters. */ 1138 dfa->multibyte_prop[dfa->tindex] = 3; 1139 } 1140 #endif 1141 1142 REALLOC_IF_NECESSARY(dfa->tokens, token, dfa->talloc, dfa->tindex); 1143 dfa->tokens[dfa->tindex++] = t; 1144 1145 switch (t) 1146 { 1147 case QMARK: 1148 case STAR: 1149 case PLUS: 1150 break; 1151 1152 case CAT: 1153 case OR: 1154 case ORTOP: 1155 --depth; 1156 break; 1157 1158 default: 1159 ++dfa->nleaves; 1160 case EMPTY: 1161 ++depth; 1162 break; 1163 } 1164 if (depth > dfa->depth) 1165 dfa->depth = depth; 1166 } 1167 1168 /* The grammar understood by the parser is as follows. 1169 1170 regexp: 1171 regexp OR branch 1172 branch 1173 1174 branch: 1175 branch closure 1176 closure 1177 1178 closure: 1179 closure QMARK 1180 closure STAR 1181 closure PLUS 1182 closure REPMN 1183 atom 1184 1185 atom: 1186 <normal character> 1187 <multibyte character> 1188 ANYCHAR 1189 MBCSET 1190 CSET 1191 BACKREF 1192 BEGLINE 1193 ENDLINE 1194 BEGWORD 1195 ENDWORD 1196 LIMWORD 1197 NOTLIMWORD 1198 CRANGE 1199 LPAREN regexp RPAREN 1200 <empty> 1201 1202 The parser builds a parse tree in postfix form in an array of tokens. */ 1203 1204 static void 1205 atom (void) 1206 { 1207 if ((tok >= 0 && tok < NOTCHAR) || tok >= CSET || tok == BACKREF 1208 || tok == BEGLINE || tok == ENDLINE || tok == BEGWORD 1209 #ifdef MBS_SUPPORT 1210 || tok == ANYCHAR || tok == MBCSET /* MB_CUR_MAX > 1 */ 1211 #endif /* MBS_SUPPORT */ 1212 || tok == ENDWORD || tok == LIMWORD || tok == NOTLIMWORD) 1213 { 1214 addtok(tok); 1215 tok = lex(); 1216 #ifdef MBS_SUPPORT 1217 /* We treat a multibyte character as a single atom, so that DFA 1218 can treat a multibyte character as a single expression. 1219 1220 e.g. We construct following tree from "<mb1><mb2>". 1221 <mb1(1st-byte)><mb1(2nd-byte)><CAT><mb1(3rd-byte)><CAT> 1222 <mb2(1st-byte)><mb2(2nd-byte)><CAT><mb2(3rd-byte)><CAT><CAT> 1223 */ 1224 if (MB_CUR_MAX > 1) 1225 { 1226 while (cur_mb_index > 1 && tok >= 0 && tok < NOTCHAR) 1227 { 1228 addtok(tok); 1229 addtok(CAT); 1230 tok = lex(); 1231 } 1232 } 1233 #endif /* MBS_SUPPORT */ 1234 } 1235 else if (tok == CRANGE) 1236 { 1237 /* A character range like "[a-z]" in a locale other than "C" or 1238 "POSIX". This range might any sequence of one or more 1239 characters. Unfortunately the POSIX locale primitives give 1240 us no practical way to find what character sequences might be 1241 matched. Treat this approximately like "(.\1)" -- i.e. match 1242 one character, and then punt to the full matcher. */ 1243 charclass ccl; 1244 zeroset (ccl); 1245 notset (ccl); 1246 addtok (CSET + charclass_index (ccl)); 1247 addtok (BACKREF); 1248 addtok (CAT); 1249 tok = lex (); 1250 } 1251 else if (tok == LPAREN) 1252 { 1253 tok = lex(); 1254 regexp(0); 1255 if (tok != RPAREN) 1256 dfaerror(_("Unbalanced (")); 1257 tok = lex(); 1258 } 1259 else 1260 addtok(EMPTY); 1261 } 1262 1263 /* Return the number of tokens in the given subexpression. */ 1264 static int 1265 nsubtoks (int tindex) 1266 { 1267 int ntoks1; 1268 1269 switch (dfa->tokens[tindex - 1]) 1270 { 1271 default: 1272 return 1; 1273 case QMARK: 1274 case STAR: 1275 case PLUS: 1276 return 1 + nsubtoks(tindex - 1); 1277 case CAT: 1278 case OR: 1279 case ORTOP: 1280 ntoks1 = nsubtoks(tindex - 1); 1281 return 1 + ntoks1 + nsubtoks(tindex - 1 - ntoks1); 1282 } 1283 } 1284 1285 /* Copy the given subexpression to the top of the tree. */ 1286 static void 1287 copytoks (int tindex, int ntokens) 1288 { 1289 int i; 1290 1291 for (i = 0; i < ntokens; ++i) 1292 addtok(dfa->tokens[tindex + i]); 1293 } 1294 1295 static void 1296 closure (void) 1297 { 1298 int tindex, ntokens, i; 1299 1300 atom(); 1301 while (tok == QMARK || tok == STAR || tok == PLUS || tok == REPMN) 1302 if (tok == REPMN) 1303 { 1304 ntokens = nsubtoks(dfa->tindex); 1305 tindex = dfa->tindex - ntokens; 1306 if (maxrep < 0) 1307 addtok(PLUS); 1308 if (minrep == 0) 1309 addtok(QMARK); 1310 for (i = 1; i < minrep; ++i) 1311 { 1312 copytoks(tindex, ntokens); 1313 addtok(CAT); 1314 } 1315 for (; i < maxrep; ++i) 1316 { 1317 copytoks(tindex, ntokens); 1318 addtok(QMARK); 1319 addtok(CAT); 1320 } 1321 tok = lex(); 1322 } 1323 else 1324 { 1325 addtok(tok); 1326 tok = lex(); 1327 } 1328 } 1329 1330 static void 1331 branch (void) 1332 { 1333 closure(); 1334 while (tok != RPAREN && tok != OR && tok >= 0) 1335 { 1336 closure(); 1337 addtok(CAT); 1338 } 1339 } 1340 1341 static void 1342 regexp (int toplevel) 1343 { 1344 branch(); 1345 while (tok == OR) 1346 { 1347 tok = lex(); 1348 branch(); 1349 if (toplevel) 1350 addtok(ORTOP); 1351 else 1352 addtok(OR); 1353 } 1354 } 1355 1356 /* Main entry point for the parser. S is a string to be parsed, len is the 1357 length of the string, so s can include NUL characters. D is a pointer to 1358 the struct dfa to parse into. */ 1359 void 1360 dfaparse (char const *s, size_t len, struct dfa *d) 1361 { 1362 dfa = d; 1363 lexstart = lexptr = s; 1364 lexleft = len; 1365 lasttok = END; 1366 laststart = 1; 1367 parens = 0; 1368 hard_LC_COLLATE = hard_locale (LC_COLLATE); 1369 #ifdef MBS_SUPPORT 1370 if (MB_CUR_MAX > 1) 1371 { 1372 cur_mb_index = 0; 1373 cur_mb_len = 0; 1374 memset(&mbs, 0, sizeof(mbstate_t)); 1375 } 1376 #endif /* MBS_SUPPORT */ 1377 1378 if (! syntax_bits_set) 1379 dfaerror(_("No syntax specified")); 1380 1381 tok = lex(); 1382 depth = d->depth; 1383 1384 regexp(1); 1385 1386 if (tok != END) 1387 dfaerror(_("Unbalanced )")); 1388 1389 addtok(END - d->nregexps); 1390 addtok(CAT); 1391 1392 if (d->nregexps) 1393 addtok(ORTOP); 1394 1395 ++d->nregexps; 1396 } 1397 1398 /* Some primitives for operating on sets of positions. */ 1399 1400 /* Copy one set to another; the destination must be large enough. */ 1401 static void 1402 copy (position_set const *src, position_set *dst) 1403 { 1404 int i; 1405 1406 for (i = 0; i < src->nelem; ++i) 1407 dst->elems[i] = src->elems[i]; 1408 dst->nelem = src->nelem; 1409 } 1410 1411 /* Insert a position in a set. Position sets are maintained in sorted 1412 order according to index. If position already exists in the set with 1413 the same index then their constraints are logically or'd together. 1414 S->elems must point to an array large enough to hold the resulting set. */ 1415 static void 1416 insert (position p, position_set *s) 1417 { 1418 int i; 1419 position t1, t2; 1420 1421 for (i = 0; i < s->nelem && p.index < s->elems[i].index; ++i) 1422 continue; 1423 if (i < s->nelem && p.index == s->elems[i].index) 1424 s->elems[i].constraint |= p.constraint; 1425 else 1426 { 1427 t1 = p; 1428 ++s->nelem; 1429 while (i < s->nelem) 1430 { 1431 t2 = s->elems[i]; 1432 s->elems[i++] = t1; 1433 t1 = t2; 1434 } 1435 } 1436 } 1437 1438 /* Merge two sets of positions into a third. The result is exactly as if 1439 the positions of both sets were inserted into an initially empty set. */ 1440 static void 1441 merge (position_set const *s1, position_set const *s2, position_set *m) 1442 { 1443 int i = 0, j = 0; 1444 1445 m->nelem = 0; 1446 while (i < s1->nelem && j < s2->nelem) 1447 if (s1->elems[i].index > s2->elems[j].index) 1448 m->elems[m->nelem++] = s1->elems[i++]; 1449 else if (s1->elems[i].index < s2->elems[j].index) 1450 m->elems[m->nelem++] = s2->elems[j++]; 1451 else 1452 { 1453 m->elems[m->nelem] = s1->elems[i++]; 1454 m->elems[m->nelem++].constraint |= s2->elems[j++].constraint; 1455 } 1456 while (i < s1->nelem) 1457 m->elems[m->nelem++] = s1->elems[i++]; 1458 while (j < s2->nelem) 1459 m->elems[m->nelem++] = s2->elems[j++]; 1460 } 1461 1462 /* Delete a position from a set. */ 1463 static void 1464 delete (position p, position_set *s) 1465 { 1466 int i; 1467 1468 for (i = 0; i < s->nelem; ++i) 1469 if (p.index == s->elems[i].index) 1470 break; 1471 if (i < s->nelem) 1472 for (--s->nelem; i < s->nelem; ++i) 1473 s->elems[i] = s->elems[i + 1]; 1474 } 1475 1476 /* Find the index of the state corresponding to the given position set with 1477 the given preceding context, or create a new state if there is no such 1478 state. Newline and letter tell whether we got here on a newline or 1479 letter, respectively. */ 1480 static int 1481 state_index (struct dfa *d, position_set const *s, int newline, int letter) 1482 { 1483 int hash = 0; 1484 int constraint; 1485 int i, j; 1486 1487 newline = newline ? 1 : 0; 1488 letter = letter ? 1 : 0; 1489 1490 for (i = 0; i < s->nelem; ++i) 1491 hash ^= s->elems[i].index + s->elems[i].constraint; 1492 1493 /* Try to find a state that exactly matches the proposed one. */ 1494 for (i = 0; i < d->sindex; ++i) 1495 { 1496 if (hash != d->states[i].hash || s->nelem != d->states[i].elems.nelem 1497 || newline != d->states[i].newline || letter != d->states[i].letter) 1498 continue; 1499 for (j = 0; j < s->nelem; ++j) 1500 if (s->elems[j].constraint 1501 != d->states[i].elems.elems[j].constraint 1502 || s->elems[j].index != d->states[i].elems.elems[j].index) 1503 break; 1504 if (j == s->nelem) 1505 return i; 1506 } 1507 1508 /* We'll have to create a new state. */ 1509 REALLOC_IF_NECESSARY(d->states, dfa_state, d->salloc, d->sindex); 1510 d->states[i].hash = hash; 1511 MALLOC(d->states[i].elems.elems, position, s->nelem); 1512 copy(s, &d->states[i].elems); 1513 d->states[i].newline = newline; 1514 d->states[i].letter = letter; 1515 d->states[i].backref = 0; 1516 d->states[i].constraint = 0; 1517 d->states[i].first_end = 0; 1518 #ifdef MBS_SUPPORT 1519 if (MB_CUR_MAX > 1) 1520 d->states[i].mbps.nelem = 0; 1521 #endif 1522 for (j = 0; j < s->nelem; ++j) 1523 if (d->tokens[s->elems[j].index] < 0) 1524 { 1525 constraint = s->elems[j].constraint; 1526 if (SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 0) 1527 || SUCCEEDS_IN_CONTEXT(constraint, newline, 0, letter, 1) 1528 || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 0) 1529 || SUCCEEDS_IN_CONTEXT(constraint, newline, 1, letter, 1)) 1530 d->states[i].constraint |= constraint; 1531 if (! d->states[i].first_end) 1532 d->states[i].first_end = d->tokens[s->elems[j].index]; 1533 } 1534 else if (d->tokens[s->elems[j].index] == BACKREF) 1535 { 1536 d->states[i].constraint = NO_CONSTRAINT; 1537 d->states[i].backref = 1; 1538 } 1539 1540 ++d->sindex; 1541 1542 return i; 1543 } 1544 1545 /* Find the epsilon closure of a set of positions. If any position of the set 1546 contains a symbol that matches the empty string in some context, replace 1547 that position with the elements of its follow labeled with an appropriate 1548 constraint. Repeat exhaustively until no funny positions are left. 1549 S->elems must be large enough to hold the result. */ 1550 static void 1551 epsclosure (position_set *s, struct dfa const *d) 1552 { 1553 int i, j; 1554 int *visited; 1555 position p, old; 1556 1557 MALLOC(visited, int, d->tindex); 1558 for (i = 0; i < d->tindex; ++i) 1559 visited[i] = 0; 1560 1561 for (i = 0; i < s->nelem; ++i) 1562 if (d->tokens[s->elems[i].index] >= NOTCHAR 1563 && d->tokens[s->elems[i].index] != BACKREF 1564 #ifdef MBS_SUPPORT 1565 && d->tokens[s->elems[i].index] != ANYCHAR 1566 && d->tokens[s->elems[i].index] != MBCSET 1567 #endif 1568 && d->tokens[s->elems[i].index] < CSET) 1569 { 1570 old = s->elems[i]; 1571 p.constraint = old.constraint; 1572 delete(s->elems[i], s); 1573 if (visited[old.index]) 1574 { 1575 --i; 1576 continue; 1577 } 1578 visited[old.index] = 1; 1579 switch (d->tokens[old.index]) 1580 { 1581 case BEGLINE: 1582 p.constraint &= BEGLINE_CONSTRAINT; 1583 break; 1584 case ENDLINE: 1585 p.constraint &= ENDLINE_CONSTRAINT; 1586 break; 1587 case BEGWORD: 1588 p.constraint &= BEGWORD_CONSTRAINT; 1589 break; 1590 case ENDWORD: 1591 p.constraint &= ENDWORD_CONSTRAINT; 1592 break; 1593 case LIMWORD: 1594 p.constraint &= LIMWORD_CONSTRAINT; 1595 break; 1596 case NOTLIMWORD: 1597 p.constraint &= NOTLIMWORD_CONSTRAINT; 1598 break; 1599 default: 1600 break; 1601 } 1602 for (j = 0; j < d->follows[old.index].nelem; ++j) 1603 { 1604 p.index = d->follows[old.index].elems[j].index; 1605 insert(p, s); 1606 } 1607 /* Force rescan to start at the beginning. */ 1608 i = -1; 1609 } 1610 1611 free(visited); 1612 } 1613 1614 /* Perform bottom-up analysis on the parse tree, computing various functions. 1615 Note that at this point, we're pretending constructs like \< are real 1616 characters rather than constraints on what can follow them. 1617 1618 Nullable: A node is nullable if it is at the root of a regexp that can 1619 match the empty string. 1620 * EMPTY leaves are nullable. 1621 * No other leaf is nullable. 1622 * A QMARK or STAR node is nullable. 1623 * A PLUS node is nullable if its argument is nullable. 1624 * A CAT node is nullable if both its arguments are nullable. 1625 * An OR node is nullable if either argument is nullable. 1626 1627 Firstpos: The firstpos of a node is the set of positions (nonempty leaves) 1628 that could correspond to the first character of a string matching the 1629 regexp rooted at the given node. 1630 * EMPTY leaves have empty firstpos. 1631 * The firstpos of a nonempty leaf is that leaf itself. 1632 * The firstpos of a QMARK, STAR, or PLUS node is the firstpos of its 1633 argument. 1634 * The firstpos of a CAT node is the firstpos of the left argument, union 1635 the firstpos of the right if the left argument is nullable. 1636 * The firstpos of an OR node is the union of firstpos of each argument. 1637 1638 Lastpos: The lastpos of a node is the set of positions that could 1639 correspond to the last character of a string matching the regexp at 1640 the given node. 1641 * EMPTY leaves have empty lastpos. 1642 * The lastpos of a nonempty leaf is that leaf itself. 1643 * The lastpos of a QMARK, STAR, or PLUS node is the lastpos of its 1644 argument. 1645 * The lastpos of a CAT node is the lastpos of its right argument, union 1646 the lastpos of the left if the right argument is nullable. 1647 * The lastpos of an OR node is the union of the lastpos of each argument. 1648 1649 Follow: The follow of a position is the set of positions that could 1650 correspond to the character following a character matching the node in 1651 a string matching the regexp. At this point we consider special symbols 1652 that match the empty string in some context to be just normal characters. 1653 Later, if we find that a special symbol is in a follow set, we will 1654 replace it with the elements of its follow, labeled with an appropriate 1655 constraint. 1656 * Every node in the firstpos of the argument of a STAR or PLUS node is in 1657 the follow of every node in the lastpos. 1658 * Every node in the firstpos of the second argument of a CAT node is in 1659 the follow of every node in the lastpos of the first argument. 1660 1661 Because of the postfix representation of the parse tree, the depth-first 1662 analysis is conveniently done by a linear scan with the aid of a stack. 1663 Sets are stored as arrays of the elements, obeying a stack-like allocation 1664 scheme; the number of elements in each set deeper in the stack can be 1665 used to determine the address of a particular set's array. */ 1666 void 1667 dfaanalyze (struct dfa *d, int searchflag) 1668 { 1669 int *nullable; /* Nullable stack. */ 1670 int *nfirstpos; /* Element count stack for firstpos sets. */ 1671 position *firstpos; /* Array where firstpos elements are stored. */ 1672 int *nlastpos; /* Element count stack for lastpos sets. */ 1673 position *lastpos; /* Array where lastpos elements are stored. */ 1674 int *nalloc; /* Sizes of arrays allocated to follow sets. */ 1675 position_set tmp; /* Temporary set for merging sets. */ 1676 position_set merged; /* Result of merging sets. */ 1677 int wants_newline; /* True if some position wants newline info. */ 1678 int *o_nullable; 1679 int *o_nfirst, *o_nlast; 1680 position *o_firstpos, *o_lastpos; 1681 int i, j; 1682 position *pos; 1683 1684 #ifdef DEBUG 1685 fprintf(stderr, "dfaanalyze:\n"); 1686 for (i = 0; i < d->tindex; ++i) 1687 { 1688 fprintf(stderr, " %d:", i); 1689 prtok(d->tokens[i]); 1690 } 1691 putc('\n', stderr); 1692 #endif 1693 1694 d->searchflag = searchflag; 1695 1696 MALLOC(nullable, int, d->depth); 1697 o_nullable = nullable; 1698 MALLOC(nfirstpos, int, d->depth); 1699 o_nfirst = nfirstpos; 1700 MALLOC(firstpos, position, d->nleaves); 1701 o_firstpos = firstpos, firstpos += d->nleaves; 1702 MALLOC(nlastpos, int, d->depth); 1703 o_nlast = nlastpos; 1704 MALLOC(lastpos, position, d->nleaves); 1705 o_lastpos = lastpos, lastpos += d->nleaves; 1706 MALLOC(nalloc, int, d->tindex); 1707 for (i = 0; i < d->tindex; ++i) 1708 nalloc[i] = 0; 1709 MALLOC(merged.elems, position, d->nleaves); 1710 1711 CALLOC(d->follows, position_set, d->tindex); 1712 1713 for (i = 0; i < d->tindex; ++i) 1714 #ifdef DEBUG 1715 { /* Nonsyntactic #ifdef goo... */ 1716 #endif 1717 switch (d->tokens[i]) 1718 { 1719 case EMPTY: 1720 /* The empty set is nullable. */ 1721 *nullable++ = 1; 1722 1723 /* The firstpos and lastpos of the empty leaf are both empty. */ 1724 *nfirstpos++ = *nlastpos++ = 0; 1725 break; 1726 1727 case STAR: 1728 case PLUS: 1729 /* Every element in the firstpos of the argument is in the follow 1730 of every element in the lastpos. */ 1731 tmp.nelem = nfirstpos[-1]; 1732 tmp.elems = firstpos; 1733 pos = lastpos; 1734 for (j = 0; j < nlastpos[-1]; ++j) 1735 { 1736 merge(&tmp, &d->follows[pos[j].index], &merged); 1737 REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position, 1738 nalloc[pos[j].index], merged.nelem - 1); 1739 copy(&merged, &d->follows[pos[j].index]); 1740 } 1741 1742 case QMARK: 1743 /* A QMARK or STAR node is automatically nullable. */ 1744 if (d->tokens[i] != PLUS) 1745 nullable[-1] = 1; 1746 break; 1747 1748 case CAT: 1749 /* Every element in the firstpos of the second argument is in the 1750 follow of every element in the lastpos of the first argument. */ 1751 tmp.nelem = nfirstpos[-1]; 1752 tmp.elems = firstpos; 1753 pos = lastpos + nlastpos[-1]; 1754 for (j = 0; j < nlastpos[-2]; ++j) 1755 { 1756 merge(&tmp, &d->follows[pos[j].index], &merged); 1757 REALLOC_IF_NECESSARY(d->follows[pos[j].index].elems, position, 1758 nalloc[pos[j].index], merged.nelem - 1); 1759 copy(&merged, &d->follows[pos[j].index]); 1760 } 1761 1762 /* The firstpos of a CAT node is the firstpos of the first argument, 1763 union that of the second argument if the first is nullable. */ 1764 if (nullable[-2]) 1765 nfirstpos[-2] += nfirstpos[-1]; 1766 else 1767 firstpos += nfirstpos[-1]; 1768 --nfirstpos; 1769 1770 /* The lastpos of a CAT node is the lastpos of the second argument, 1771 union that of the first argument if the second is nullable. */ 1772 if (nullable[-1]) 1773 nlastpos[-2] += nlastpos[-1]; 1774 else 1775 { 1776 pos = lastpos + nlastpos[-2]; 1777 for (j = nlastpos[-1] - 1; j >= 0; --j) 1778 pos[j] = lastpos[j]; 1779 lastpos += nlastpos[-2]; 1780 nlastpos[-2] = nlastpos[-1]; 1781 } 1782 --nlastpos; 1783 1784 /* A CAT node is nullable if both arguments are nullable. */ 1785 nullable[-2] = nullable[-1] && nullable[-2]; 1786 --nullable; 1787 break; 1788 1789 case OR: 1790 case ORTOP: 1791 /* The firstpos is the union of the firstpos of each argument. */ 1792 nfirstpos[-2] += nfirstpos[-1]; 1793 --nfirstpos; 1794 1795 /* The lastpos is the union of the lastpos of each argument. */ 1796 nlastpos[-2] += nlastpos[-1]; 1797 --nlastpos; 1798 1799 /* An OR node is nullable if either argument is nullable. */ 1800 nullable[-2] = nullable[-1] || nullable[-2]; 1801 --nullable; 1802 break; 1803 1804 default: 1805 /* Anything else is a nonempty position. (Note that special 1806 constructs like \< are treated as nonempty strings here; 1807 an "epsilon closure" effectively makes them nullable later. 1808 Backreferences have to get a real position so we can detect 1809 transitions on them later. But they are nullable. */ 1810 *nullable++ = d->tokens[i] == BACKREF; 1811 1812 /* This position is in its own firstpos and lastpos. */ 1813 *nfirstpos++ = *nlastpos++ = 1; 1814 --firstpos, --lastpos; 1815 firstpos->index = lastpos->index = i; 1816 firstpos->constraint = lastpos->constraint = NO_CONSTRAINT; 1817 1818 /* Allocate the follow set for this position. */ 1819 nalloc[i] = 1; 1820 MALLOC(d->follows[i].elems, position, nalloc[i]); 1821 break; 1822 } 1823 #ifdef DEBUG 1824 /* ... balance the above nonsyntactic #ifdef goo... */ 1825 fprintf(stderr, "node %d:", i); 1826 prtok(d->tokens[i]); 1827 putc('\n', stderr); 1828 fprintf(stderr, nullable[-1] ? " nullable: yes\n" : " nullable: no\n"); 1829 fprintf(stderr, " firstpos:"); 1830 for (j = nfirstpos[-1] - 1; j >= 0; --j) 1831 { 1832 fprintf(stderr, " %d:", firstpos[j].index); 1833 prtok(d->tokens[firstpos[j].index]); 1834 } 1835 fprintf(stderr, "\n lastpos:"); 1836 for (j = nlastpos[-1] - 1; j >= 0; --j) 1837 { 1838 fprintf(stderr, " %d:", lastpos[j].index); 1839 prtok(d->tokens[lastpos[j].index]); 1840 } 1841 putc('\n', stderr); 1842 } 1843 #endif 1844 1845 /* For each follow set that is the follow set of a real position, replace 1846 it with its epsilon closure. */ 1847 for (i = 0; i < d->tindex; ++i) 1848 if (d->tokens[i] < NOTCHAR || d->tokens[i] == BACKREF 1849 #ifdef MBS_SUPPORT 1850 || d->tokens[i] == ANYCHAR 1851 || d->tokens[i] == MBCSET 1852 #endif 1853 || d->tokens[i] >= CSET) 1854 { 1855 #ifdef DEBUG 1856 fprintf(stderr, "follows(%d:", i); 1857 prtok(d->tokens[i]); 1858 fprintf(stderr, "):"); 1859 for (j = d->follows[i].nelem - 1; j >= 0; --j) 1860 { 1861 fprintf(stderr, " %d:", d->follows[i].elems[j].index); 1862 prtok(d->tokens[d->follows[i].elems[j].index]); 1863 } 1864 putc('\n', stderr); 1865 #endif 1866 copy(&d->follows[i], &merged); 1867 epsclosure(&merged, d); 1868 if (d->follows[i].nelem < merged.nelem) 1869 REALLOC(d->follows[i].elems, position, merged.nelem); 1870 copy(&merged, &d->follows[i]); 1871 } 1872 1873 /* Get the epsilon closure of the firstpos of the regexp. The result will 1874 be the set of positions of state 0. */ 1875 merged.nelem = 0; 1876 for (i = 0; i < nfirstpos[-1]; ++i) 1877 insert(firstpos[i], &merged); 1878 epsclosure(&merged, d); 1879 1880 /* Check if any of the positions of state 0 will want newline context. */ 1881 wants_newline = 0; 1882 for (i = 0; i < merged.nelem; ++i) 1883 if (PREV_NEWLINE_DEPENDENT(merged.elems[i].constraint)) 1884 wants_newline = 1; 1885 1886 /* Build the initial state. */ 1887 d->salloc = 1; 1888 d->sindex = 0; 1889 MALLOC(d->states, dfa_state, d->salloc); 1890 state_index(d, &merged, wants_newline, 0); 1891 1892 free(o_nullable); 1893 free(o_nfirst); 1894 free(o_firstpos); 1895 free(o_nlast); 1896 free(o_lastpos); 1897 free(nalloc); 1898 free(merged.elems); 1899 } 1900 1901 /* Find, for each character, the transition out of state s of d, and store 1902 it in the appropriate slot of trans. 1903 1904 We divide the positions of s into groups (positions can appear in more 1905 than one group). Each group is labeled with a set of characters that 1906 every position in the group matches (taking into account, if necessary, 1907 preceding context information of s). For each group, find the union 1908 of the its elements' follows. This set is the set of positions of the 1909 new state. For each character in the group's label, set the transition 1910 on this character to be to a state corresponding to the set's positions, 1911 and its associated backward context information, if necessary. 1912 1913 If we are building a searching matcher, we include the positions of state 1914 0 in every state. 1915 1916 The collection of groups is constructed by building an equivalence-class 1917 partition of the positions of s. 1918 1919 For each position, find the set of characters C that it matches. Eliminate 1920 any characters from C that fail on grounds of backward context. 1921 1922 Search through the groups, looking for a group whose label L has nonempty 1923 intersection with C. If L - C is nonempty, create a new group labeled 1924 L - C and having the same positions as the current group, and set L to 1925 the intersection of L and C. Insert the position in this group, set 1926 C = C - L, and resume scanning. 1927 1928 If after comparing with every group there are characters remaining in C, 1929 create a new group labeled with the characters of C and insert this 1930 position in that group. */ 1931 void 1932 dfastate (int s, struct dfa *d, int trans[]) 1933 { 1934 position_set grps[NOTCHAR]; /* As many as will ever be needed. */ 1935 charclass labels[NOTCHAR]; /* Labels corresponding to the groups. */ 1936 int ngrps = 0; /* Number of groups actually used. */ 1937 position pos; /* Current position being considered. */ 1938 charclass matches; /* Set of matching characters. */ 1939 int matchesf; /* True if matches is nonempty. */ 1940 charclass intersect; /* Intersection with some label set. */ 1941 int intersectf; /* True if intersect is nonempty. */ 1942 charclass leftovers; /* Stuff in the label that didn't match. */ 1943 int leftoversf; /* True if leftovers is nonempty. */ 1944 static charclass letters; /* Set of characters considered letters. */ 1945 static charclass newline; /* Set of characters that aren't newline. */ 1946 position_set follows; /* Union of the follows of some group. */ 1947 position_set tmp; /* Temporary space for merging sets. */ 1948 int state; /* New state. */ 1949 int wants_newline; /* New state wants to know newline context. */ 1950 int state_newline; /* New state on a newline transition. */ 1951 int wants_letter; /* New state wants to know letter context. */ 1952 int state_letter; /* New state on a letter transition. */ 1953 static int initialized; /* Flag for static initialization. */ 1954 #ifdef MBS_SUPPORT 1955 int next_isnt_1st_byte = 0; /* Flag If we can't add state0. */ 1956 #endif 1957 int i, j, k; 1958 1959 /* Initialize the set of letters, if necessary. */ 1960 if (! initialized) 1961 { 1962 initialized = 1; 1963 for (i = 0; i < NOTCHAR; ++i) 1964 if (IS_WORD_CONSTITUENT(i)) 1965 setbit(i, letters); 1966 setbit(eolbyte, newline); 1967 } 1968 1969 zeroset(matches); 1970 1971 for (i = 0; i < d->states[s].elems.nelem; ++i) 1972 { 1973 pos = d->states[s].elems.elems[i]; 1974 if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR) 1975 setbit(d->tokens[pos.index], matches); 1976 else if (d->tokens[pos.index] >= CSET) 1977 copyset(d->charclasses[d->tokens[pos.index] - CSET], matches); 1978 #ifdef MBS_SUPPORT 1979 else if (d->tokens[pos.index] == ANYCHAR 1980 || d->tokens[pos.index] == MBCSET) 1981 /* MB_CUR_MAX > 1 */ 1982 { 1983 /* ANYCHAR and MBCSET must match with a single character, so we 1984 must put it to d->states[s].mbps, which contains the positions 1985 which can match with a single character not a byte. */ 1986 if (d->states[s].mbps.nelem == 0) 1987 { 1988 MALLOC(d->states[s].mbps.elems, position, 1989 d->states[s].elems.nelem); 1990 } 1991 insert(pos, &(d->states[s].mbps)); 1992 continue; 1993 } 1994 #endif /* MBS_SUPPORT */ 1995 else 1996 continue; 1997 1998 /* Some characters may need to be eliminated from matches because 1999 they fail in the current context. */ 2000 if (pos.constraint != 0xFF) 2001 { 2002 if (! MATCHES_NEWLINE_CONTEXT(pos.constraint, 2003 d->states[s].newline, 1)) 2004 clrbit(eolbyte, matches); 2005 if (! MATCHES_NEWLINE_CONTEXT(pos.constraint, 2006 d->states[s].newline, 0)) 2007 for (j = 0; j < CHARCLASS_INTS; ++j) 2008 matches[j] &= newline[j]; 2009 if (! MATCHES_LETTER_CONTEXT(pos.constraint, 2010 d->states[s].letter, 1)) 2011 for (j = 0; j < CHARCLASS_INTS; ++j) 2012 matches[j] &= ~letters[j]; 2013 if (! MATCHES_LETTER_CONTEXT(pos.constraint, 2014 d->states[s].letter, 0)) 2015 for (j = 0; j < CHARCLASS_INTS; ++j) 2016 matches[j] &= letters[j]; 2017 2018 /* If there are no characters left, there's no point in going on. */ 2019 for (j = 0; j < CHARCLASS_INTS && !matches[j]; ++j) 2020 continue; 2021 if (j == CHARCLASS_INTS) 2022 continue; 2023 } 2024 2025 for (j = 0; j < ngrps; ++j) 2026 { 2027 /* If matches contains a single character only, and the current 2028 group's label doesn't contain that character, go on to the 2029 next group. */ 2030 if (d->tokens[pos.index] >= 0 && d->tokens[pos.index] < NOTCHAR 2031 && !tstbit(d->tokens[pos.index], labels[j])) 2032 continue; 2033 2034 /* Check if this group's label has a nonempty intersection with 2035 matches. */ 2036 intersectf = 0; 2037 for (k = 0; k < CHARCLASS_INTS; ++k) 2038 (intersect[k] = matches[k] & labels[j][k]) ? (intersectf = 1) : 0; 2039 if (! intersectf) 2040 continue; 2041 2042 /* It does; now find the set differences both ways. */ 2043 leftoversf = matchesf = 0; 2044 for (k = 0; k < CHARCLASS_INTS; ++k) 2045 { 2046 /* Even an optimizing compiler can't know this for sure. */ 2047 int match = matches[k], label = labels[j][k]; 2048 2049 (leftovers[k] = ~match & label) ? (leftoversf = 1) : 0; 2050 (matches[k] = match & ~label) ? (matchesf = 1) : 0; 2051 } 2052 2053 /* If there were leftovers, create a new group labeled with them. */ 2054 if (leftoversf) 2055 { 2056 copyset(leftovers, labels[ngrps]); 2057 copyset(intersect, labels[j]); 2058 MALLOC(grps[ngrps].elems, position, d->nleaves); 2059 copy(&grps[j], &grps[ngrps]); 2060 ++ngrps; 2061 } 2062 2063 /* Put the position in the current group. Note that there is no 2064 reason to call insert() here. */ 2065 grps[j].elems[grps[j].nelem++] = pos; 2066 2067 /* If every character matching the current position has been 2068 accounted for, we're done. */ 2069 if (! matchesf) 2070 break; 2071 } 2072 2073 /* If we've passed the last group, and there are still characters 2074 unaccounted for, then we'll have to create a new group. */ 2075 if (j == ngrps) 2076 { 2077 copyset(matches, labels[ngrps]); 2078 zeroset(matches); 2079 MALLOC(grps[ngrps].elems, position, d->nleaves); 2080 grps[ngrps].nelem = 1; 2081 grps[ngrps].elems[0] = pos; 2082 ++ngrps; 2083 } 2084 } 2085 2086 MALLOC(follows.elems, position, d->nleaves); 2087 MALLOC(tmp.elems, position, d->nleaves); 2088 2089 /* If we are a searching matcher, the default transition is to a state 2090 containing the positions of state 0, otherwise the default transition 2091 is to fail miserably. */ 2092 if (d->searchflag) 2093 { 2094 wants_newline = 0; 2095 wants_letter = 0; 2096 for (i = 0; i < d->states[0].elems.nelem; ++i) 2097 { 2098 if (PREV_NEWLINE_DEPENDENT(d->states[0].elems.elems[i].constraint)) 2099 wants_newline = 1; 2100 if (PREV_LETTER_DEPENDENT(d->states[0].elems.elems[i].constraint)) 2101 wants_letter = 1; 2102 } 2103 copy(&d->states[0].elems, &follows); 2104 state = state_index(d, &follows, 0, 0); 2105 if (wants_newline) 2106 state_newline = state_index(d, &follows, 1, 0); 2107 else 2108 state_newline = state; 2109 if (wants_letter) 2110 state_letter = state_index(d, &follows, 0, 1); 2111 else 2112 state_letter = state; 2113 for (i = 0; i < NOTCHAR; ++i) 2114 trans[i] = (IS_WORD_CONSTITUENT(i)) ? state_letter : state; 2115 trans[eolbyte] = state_newline; 2116 } 2117 else 2118 for (i = 0; i < NOTCHAR; ++i) 2119 trans[i] = -1; 2120 2121 for (i = 0; i < ngrps; ++i) 2122 { 2123 follows.nelem = 0; 2124 2125 /* Find the union of the follows of the positions of the group. 2126 This is a hideously inefficient loop. Fix it someday. */ 2127 for (j = 0; j < grps[i].nelem; ++j) 2128 for (k = 0; k < d->follows[grps[i].elems[j].index].nelem; ++k) 2129 insert(d->follows[grps[i].elems[j].index].elems[k], &follows); 2130 2131 #ifdef MBS_SUPPORT 2132 if (MB_CUR_MAX > 1) 2133 { 2134 /* If a token in follows.elems is not 1st byte of a multibyte 2135 character, or the states of follows must accept the bytes 2136 which are not 1st byte of the multibyte character. 2137 Then, if a state of follows encounter a byte, it must not be 2138 a 1st byte of a multibyte character nor singlebyte character. 2139 We cansel to add state[0].follows to next state, because 2140 state[0] must accept 1st-byte 2141 2142 For example, we assume <sb a> is a certain singlebyte 2143 character, <mb A> is a certain multibyte character, and the 2144 codepoint of <sb a> equals the 2nd byte of the codepoint of 2145 <mb A>. 2146 When state[0] accepts <sb a>, state[i] transit to state[i+1] 2147 by accepting accepts 1st byte of <mb A>, and state[i+1] 2148 accepts 2nd byte of <mb A>, if state[i+1] encounter the 2149 codepoint of <sb a>, it must not be <sb a> but 2nd byte of 2150 <mb A>, so we can not add state[0]. */ 2151 2152 next_isnt_1st_byte = 0; 2153 for (j = 0; j < follows.nelem; ++j) 2154 { 2155 if (!(d->multibyte_prop[follows.elems[j].index] & 1)) 2156 { 2157 next_isnt_1st_byte = 1; 2158 break; 2159 } 2160 } 2161 } 2162 #endif 2163 2164 /* If we are building a searching matcher, throw in the positions 2165 of state 0 as well. */ 2166 #ifdef MBS_SUPPORT 2167 if (d->searchflag && (MB_CUR_MAX == 1 || !next_isnt_1st_byte)) 2168 #else 2169 if (d->searchflag) 2170 #endif 2171 for (j = 0; j < d->states[0].elems.nelem; ++j) 2172 insert(d->states[0].elems.elems[j], &follows); 2173 2174 /* Find out if the new state will want any context information. */ 2175 wants_newline = 0; 2176 if (tstbit(eolbyte, labels[i])) 2177 for (j = 0; j < follows.nelem; ++j) 2178 if (PREV_NEWLINE_DEPENDENT(follows.elems[j].constraint)) 2179 wants_newline = 1; 2180 2181 wants_letter = 0; 2182 for (j = 0; j < CHARCLASS_INTS; ++j) 2183 if (labels[i][j] & letters[j]) 2184 break; 2185 if (j < CHARCLASS_INTS) 2186 for (j = 0; j < follows.nelem; ++j) 2187 if (PREV_LETTER_DEPENDENT(follows.elems[j].constraint)) 2188 wants_letter = 1; 2189 2190 /* Find the state(s) corresponding to the union of the follows. */ 2191 state = state_index(d, &follows, 0, 0); 2192 if (wants_newline) 2193 state_newline = state_index(d, &follows, 1, 0); 2194 else 2195 state_newline = state; 2196 if (wants_letter) 2197 state_letter = state_index(d, &follows, 0, 1); 2198 else 2199 state_letter = state; 2200 2201 /* Set the transitions for each character in the current label. */ 2202 for (j = 0; j < CHARCLASS_INTS; ++j) 2203 for (k = 0; k < INTBITS; ++k) 2204 if (labels[i][j] & 1 << k) 2205 { 2206 int c = j * INTBITS + k; 2207 2208 if (c == eolbyte) 2209 trans[c] = state_newline; 2210 else if (IS_WORD_CONSTITUENT(c)) 2211 trans[c] = state_letter; 2212 else if (c < NOTCHAR) 2213 trans[c] = state; 2214 } 2215 } 2216 2217 for (i = 0; i < ngrps; ++i) 2218 free(grps[i].elems); 2219 free(follows.elems); 2220 free(tmp.elems); 2221 } 2222 2223 /* Some routines for manipulating a compiled dfa's transition tables. 2224 Each state may or may not have a transition table; if it does, and it 2225 is a non-accepting state, then d->trans[state] points to its table. 2226 If it is an accepting state then d->fails[state] points to its table. 2227 If it has no table at all, then d->trans[state] is NULL. 2228 TODO: Improve this comment, get rid of the unnecessary redundancy. */ 2229 2230 static void 2231 build_state (int s, struct dfa *d) 2232 { 2233 int *trans; /* The new transition table. */ 2234 int i; 2235 2236 /* Set an upper limit on the number of transition tables that will ever 2237 exist at once. 1024 is arbitrary. The idea is that the frequently 2238 used transition tables will be quickly rebuilt, whereas the ones that 2239 were only needed once or twice will be cleared away. */ 2240 if (d->trcount >= 1024) 2241 { 2242 for (i = 0; i < d->tralloc; ++i) 2243 if (d->trans[i]) 2244 { 2245 free((ptr_t) d->trans[i]); 2246 d->trans[i] = NULL; 2247 } 2248 else if (d->fails[i]) 2249 { 2250 free((ptr_t) d->fails[i]); 2251 d->fails[i] = NULL; 2252 } 2253 d->trcount = 0; 2254 } 2255 2256 ++d->trcount; 2257 2258 /* Set up the success bits for this state. */ 2259 d->success[s] = 0; 2260 if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 1, d->states[s].letter, 0, 2261 s, *d)) 2262 d->success[s] |= 4; 2263 if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 1, 2264 s, *d)) 2265 d->success[s] |= 2; 2266 if (ACCEPTS_IN_CONTEXT(d->states[s].newline, 0, d->states[s].letter, 0, 2267 s, *d)) 2268 d->success[s] |= 1; 2269 2270 MALLOC(trans, int, NOTCHAR); 2271 dfastate(s, d, trans); 2272 2273 /* Now go through the new transition table, and make sure that the trans 2274 and fail arrays are allocated large enough to hold a pointer for the 2275 largest state mentioned in the table. */ 2276 for (i = 0; i < NOTCHAR; ++i) 2277 if (trans[i] >= d->tralloc) 2278 { 2279 int oldalloc = d->tralloc; 2280 2281 while (trans[i] >= d->tralloc) 2282 d->tralloc *= 2; 2283 REALLOC(d->realtrans, int *, d->tralloc + 1); 2284 d->trans = d->realtrans + 1; 2285 REALLOC(d->fails, int *, d->tralloc); 2286 REALLOC(d->success, int, d->tralloc); 2287 while (oldalloc < d->tralloc) 2288 { 2289 d->trans[oldalloc] = NULL; 2290 d->fails[oldalloc++] = NULL; 2291 } 2292 } 2293 2294 /* Newline is a sentinel. */ 2295 trans[eolbyte] = -1; 2296 2297 if (ACCEPTING(s, *d)) 2298 d->fails[s] = trans; 2299 else 2300 d->trans[s] = trans; 2301 } 2302 2303 static void 2304 build_state_zero (struct dfa *d) 2305 { 2306 d->tralloc = 1; 2307 d->trcount = 0; 2308 CALLOC(d->realtrans, int *, d->tralloc + 1); 2309 d->trans = d->realtrans + 1; 2310 CALLOC(d->fails, int *, d->tralloc); 2311 MALLOC(d->success, int, d->tralloc); 2312 build_state(0, d); 2313 } 2314 2315 #ifdef MBS_SUPPORT 2316 /* Multibyte character handling sub-routins for dfaexec. */ 2317 2318 /* Initial state may encounter the byte which is not a singlebyte character 2319 nor 1st byte of a multibyte character. But it is incorrect for initial 2320 state to accept such a byte. 2321 For example, in sjis encoding the regular expression like "\\" accepts 2322 the codepoint 0x5c, but should not accept the 2nd byte of the codepoint 2323 0x815c. Then Initial state must skip the bytes which are not a singlebyte 2324 character nor 1st byte of a multibyte character. */ 2325 #define SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p) \ 2326 if (s == 0) \ 2327 { \ 2328 while (inputwcs[p - buf_begin] == 0 \ 2329 && mblen_buf[p - buf_begin] > 0 \ 2330 && p < buf_end) \ 2331 ++p; \ 2332 if (p >= end) \ 2333 { \ 2334 free(mblen_buf); \ 2335 free(inputwcs); \ 2336 return (size_t) -1; \ 2337 } \ 2338 } 2339 2340 static void 2341 realloc_trans_if_necessary(struct dfa *d, int new_state) 2342 { 2343 /* Make sure that the trans and fail arrays are allocated large enough 2344 to hold a pointer for the new state. */ 2345 if (new_state >= d->tralloc) 2346 { 2347 int oldalloc = d->tralloc; 2348 2349 while (new_state >= d->tralloc) 2350 d->tralloc *= 2; 2351 REALLOC(d->realtrans, int *, d->tralloc + 1); 2352 d->trans = d->realtrans + 1; 2353 REALLOC(d->fails, int *, d->tralloc); 2354 REALLOC(d->success, int, d->tralloc); 2355 while (oldalloc < d->tralloc) 2356 { 2357 d->trans[oldalloc] = NULL; 2358 d->fails[oldalloc++] = NULL; 2359 } 2360 } 2361 } 2362 2363 /* Return values of transit_state_singlebyte(), and 2364 transit_state_consume_1char. */ 2365 typedef enum 2366 { 2367 TRANSIT_STATE_IN_PROGRESS, /* State transition has not finished. */ 2368 TRANSIT_STATE_DONE, /* State transition has finished. */ 2369 TRANSIT_STATE_END_BUFFER /* Reach the end of the buffer. */ 2370 } status_transit_state; 2371 2372 /* Consume a single byte and transit state from 's' to '*next_state'. 2373 This function is almost same as the state transition routin in dfaexec(). 2374 But state transition is done just once, otherwise matching succeed or 2375 reach the end of the buffer. */ 2376 static status_transit_state 2377 transit_state_singlebyte (struct dfa *d, int s, unsigned char const *p, 2378 int *next_state) 2379 { 2380 int *t; 2381 int works = s; 2382 2383 status_transit_state rval = TRANSIT_STATE_IN_PROGRESS; 2384 2385 while (rval == TRANSIT_STATE_IN_PROGRESS) 2386 { 2387 if ((t = d->trans[works]) != NULL) 2388 { 2389 works = t[*p]; 2390 rval = TRANSIT_STATE_DONE; 2391 if (works < 0) 2392 works = 0; 2393 } 2394 else if (works < 0) 2395 { 2396 if (p == buf_end) 2397 /* At the moment, it must not happen. */ 2398 return TRANSIT_STATE_END_BUFFER; 2399 works = 0; 2400 } 2401 else if (d->fails[works]) 2402 { 2403 works = d->fails[works][*p]; 2404 rval = TRANSIT_STATE_DONE; 2405 } 2406 else 2407 { 2408 build_state(works, d); 2409 } 2410 } 2411 *next_state = works; 2412 return rval; 2413 } 2414 2415 /* Check whether period can match or not in the current context. If it can, 2416 return the amount of the bytes with which period can match, otherwise 2417 return 0. 2418 `pos' is the position of the period. `index' is the index from the 2419 buf_begin, and it is the current position in the buffer. */ 2420 static int 2421 match_anychar (struct dfa *d, int s, position pos, int index) 2422 { 2423 int newline = 0; 2424 int letter = 0; 2425 wchar_t wc; 2426 int mbclen; 2427 2428 wc = inputwcs[index]; 2429 mbclen = (mblen_buf[index] == 0)? 1 : mblen_buf[index]; 2430 2431 /* Check context. */ 2432 if (wc == (wchar_t)eolbyte) 2433 { 2434 if (!(syntax_bits & RE_DOT_NEWLINE)) 2435 return 0; 2436 newline = 1; 2437 } 2438 else if (wc == (wchar_t)'\0') 2439 { 2440 if (syntax_bits & RE_DOT_NOT_NULL) 2441 return 0; 2442 newline = 1; 2443 } 2444 2445 if (iswalnum(wc) || wc == L'_') 2446 letter = 1; 2447 2448 if (!SUCCEEDS_IN_CONTEXT(pos.constraint, d->states[s].newline, 2449 newline, d->states[s].letter, letter)) 2450 return 0; 2451 2452 return mbclen; 2453 } 2454 2455 /* Check whether bracket expression can match or not in the current context. 2456 If it can, return the amount of the bytes with which expression can match, 2457 otherwise return 0. 2458 `pos' is the position of the bracket expression. `index' is the index 2459 from the buf_begin, and it is the current position in the buffer. */ 2460 int 2461 match_mb_charset (struct dfa *d, int s, position pos, int index) 2462 { 2463 int i; 2464 int match; /* Flag which represent that matching succeed. */ 2465 int match_len; /* Length of the character (or collating element) 2466 with which this operator match. */ 2467 size_t op_len; /* Length of the operator. */ 2468 char buffer[128]; 2469 wchar_t wcbuf[6]; 2470 2471 /* Pointer to the structure to which we are currently reffering. */ 2472 struct mb_char_classes *work_mbc; 2473 2474 int newline = 0; 2475 int letter = 0; 2476 wchar_t wc; /* Current reffering character. */ 2477 2478 wc = inputwcs[index]; 2479 2480 /* Check context. */ 2481 if (wc == (wchar_t)eolbyte) 2482 { 2483 if (!(syntax_bits & RE_DOT_NEWLINE)) 2484 return 0; 2485 newline = 1; 2486 } 2487 else if (wc == (wchar_t)'\0') 2488 { 2489 if (syntax_bits & RE_DOT_NOT_NULL) 2490 return 0; 2491 newline = 1; 2492 } 2493 if (iswalnum(wc) || wc == L'_') 2494 letter = 1; 2495 if (!SUCCEEDS_IN_CONTEXT(pos.constraint, d->states[s].newline, 2496 newline, d->states[s].letter, letter)) 2497 return 0; 2498 2499 /* Assign the current reffering operator to work_mbc. */ 2500 work_mbc = &(d->mbcsets[(d->multibyte_prop[pos.index]) >> 2]); 2501 match = !work_mbc->invert; 2502 match_len = (mblen_buf[index] == 0)? 1 : mblen_buf[index]; 2503 2504 /* match with a character class? */ 2505 for (i = 0; i<work_mbc->nch_classes; i++) 2506 { 2507 if (iswctype((wint_t)wc, work_mbc->ch_classes[i])) 2508 goto charset_matched; 2509 } 2510 2511 strncpy(buffer, buf_begin + index, match_len); 2512 buffer[match_len] = '\0'; 2513 2514 /* match with an equivalent class? */ 2515 for (i = 0; i<work_mbc->nequivs; i++) 2516 { 2517 op_len = strlen(work_mbc->equivs[i]); 2518 strncpy(buffer, buf_begin + index, op_len); 2519 buffer[op_len] = '\0'; 2520 if (strcoll(work_mbc->equivs[i], buffer) == 0) 2521 { 2522 match_len = op_len; 2523 goto charset_matched; 2524 } 2525 } 2526 2527 /* match with a collating element? */ 2528 for (i = 0; i<work_mbc->ncoll_elems; i++) 2529 { 2530 op_len = strlen(work_mbc->coll_elems[i]); 2531 strncpy(buffer, buf_begin + index, op_len); 2532 buffer[op_len] = '\0'; 2533 2534 if (strcoll(work_mbc->coll_elems[i], buffer) == 0) 2535 { 2536 match_len = op_len; 2537 goto charset_matched; 2538 } 2539 } 2540 2541 wcbuf[0] = wc; 2542 wcbuf[1] = wcbuf[3] = wcbuf[5] = '\0'; 2543 2544 /* match with a range? */ 2545 for (i = 0; i<work_mbc->nranges; i++) 2546 { 2547 wcbuf[2] = work_mbc->range_sts[i]; 2548 wcbuf[4] = work_mbc->range_ends[i]; 2549 2550 #ifdef __FreeBSD__ 2551 if (wcscmp(wcbuf, wcbuf+2) >= 0 && 2552 wcscmp(wcbuf+4, wcbuf) >= 0) 2553 #else 2554 if (wcscoll(wcbuf, wcbuf+2) >= 0 && 2555 wcscoll(wcbuf+4, wcbuf) >= 0) 2556 #endif 2557 goto charset_matched; 2558 } 2559 2560 /* match with a character? */ 2561 if (case_fold) 2562 wc = towlower (wc); 2563 for (i = 0; i<work_mbc->nchars; i++) 2564 { 2565 if (wc == work_mbc->chars[i]) 2566 goto charset_matched; 2567 } 2568 2569 match = !match; 2570 2571 charset_matched: 2572 return match ? match_len : 0; 2573 } 2574 2575 /* Check each of `d->states[s].mbps.elem' can match or not. Then return the 2576 array which corresponds to `d->states[s].mbps.elem' and each element of 2577 the array contains the amount of the bytes with which the element can 2578 match. 2579 `index' is the index from the buf_begin, and it is the current position 2580 in the buffer. 2581 Caller MUST free the array which this function return. */ 2582 static int* 2583 check_matching_with_multibyte_ops (struct dfa *d, int s, int index) 2584 { 2585 int i; 2586 int* rarray; 2587 2588 MALLOC(rarray, int, d->states[s].mbps.nelem); 2589 for (i = 0; i < d->states[s].mbps.nelem; ++i) 2590 { 2591 position pos = d->states[s].mbps.elems[i]; 2592 switch(d->tokens[pos.index]) 2593 { 2594 case ANYCHAR: 2595 rarray[i] = match_anychar(d, s, pos, index); 2596 break; 2597 case MBCSET: 2598 rarray[i] = match_mb_charset(d, s, pos, index); 2599 break; 2600 default: 2601 break; /* can not happen. */ 2602 } 2603 } 2604 return rarray; 2605 } 2606 2607 /* Consume a single character and enumerate all of the positions which can 2608 be next position from the state `s'. 2609 `match_lens' is the input. It can be NULL, but it can also be the output 2610 of check_matching_with_multibyte_ops() for optimization. 2611 `mbclen' and `pps' are the output. `mbclen' is the length of the 2612 character consumed, and `pps' is the set this function enumerate. */ 2613 static status_transit_state 2614 transit_state_consume_1char (struct dfa *d, int s, unsigned char const **pp, 2615 int *match_lens, int *mbclen, position_set *pps) 2616 { 2617 int i, j; 2618 int s1, s2; 2619 int* work_mbls; 2620 status_transit_state rs = TRANSIT_STATE_DONE; 2621 2622 /* Calculate the length of the (single/multi byte) character 2623 to which p points. */ 2624 *mbclen = (mblen_buf[*pp - buf_begin] == 0)? 1 2625 : mblen_buf[*pp - buf_begin]; 2626 2627 /* Calculate the state which can be reached from the state `s' by 2628 consuming `*mbclen' single bytes from the buffer. */ 2629 s1 = s; 2630 for (i = 0; i < *mbclen; i++) 2631 { 2632 s2 = s1; 2633 rs = transit_state_singlebyte(d, s2, (*pp)++, &s1); 2634 } 2635 /* Copy the positions contained by `s1' to the set `pps'. */ 2636 copy(&(d->states[s1].elems), pps); 2637 2638 /* Check (inputed)match_lens, and initialize if it is NULL. */ 2639 if (match_lens == NULL && d->states[s].mbps.nelem != 0) 2640 work_mbls = check_matching_with_multibyte_ops(d, s, *pp - buf_begin); 2641 else 2642 work_mbls = match_lens; 2643 2644 /* Add all of the positions which can be reached from `s' by consuming 2645 a single character. */ 2646 for (i = 0; i < d->states[s].mbps.nelem ; i++) 2647 { 2648 if (work_mbls[i] == *mbclen) 2649 for (j = 0; j < d->follows[d->states[s].mbps.elems[i].index].nelem; 2650 j++) 2651 insert(d->follows[d->states[s].mbps.elems[i].index].elems[j], 2652 pps); 2653 } 2654 2655 if (match_lens == NULL && work_mbls != NULL) 2656 free(work_mbls); 2657 return rs; 2658 } 2659 2660 /* Transit state from s, then return new state and update the pointer of the 2661 buffer. This function is for some operator which can match with a multi- 2662 byte character or a collating element(which may be multi characters). */ 2663 static int 2664 transit_state (struct dfa *d, int s, unsigned char const **pp) 2665 { 2666 int s1; 2667 int mbclen; /* The length of current input multibyte character. */ 2668 int maxlen = 0; 2669 int i, j; 2670 int *match_lens = NULL; 2671 int nelem = d->states[s].mbps.nelem; /* Just a alias. */ 2672 position_set follows; 2673 unsigned char const *p1 = *pp; 2674 status_transit_state rs; 2675 wchar_t wc; 2676 2677 if (nelem > 0) 2678 /* This state has (a) multibyte operator(s). 2679 We check whether each of them can match or not. */ 2680 { 2681 /* Note: caller must free the return value of this function. */ 2682 match_lens = check_matching_with_multibyte_ops(d, s, *pp - buf_begin); 2683 2684 for (i = 0; i < nelem; i++) 2685 /* Search the operator which match the longest string, 2686 in this state. */ 2687 { 2688 if (match_lens[i] > maxlen) 2689 maxlen = match_lens[i]; 2690 } 2691 } 2692 2693 if (nelem == 0 || maxlen == 0) 2694 /* This state has no multibyte operator which can match. 2695 We need to check only one singlebyte character. */ 2696 { 2697 status_transit_state rs; 2698 rs = transit_state_singlebyte(d, s, *pp, &s1); 2699 2700 /* We must update the pointer if state transition succeeded. */ 2701 if (rs == TRANSIT_STATE_DONE) 2702 ++*pp; 2703 2704 if (match_lens != NULL) 2705 free(match_lens); 2706 return s1; 2707 } 2708 2709 /* This state has some operators which can match a multibyte character. */ 2710 follows.nelem = 0; 2711 MALLOC(follows.elems, position, d->nleaves); 2712 2713 /* `maxlen' may be longer than the length of a character, because it may 2714 not be a character but a (multi character) collating element. 2715 We enumerate all of the positions which `s' can reach by consuming 2716 `maxlen' bytes. */ 2717 rs = transit_state_consume_1char(d, s, pp, match_lens, &mbclen, &follows); 2718 2719 wc = inputwcs[*pp - mbclen - buf_begin]; 2720 s1 = state_index(d, &follows, wc == L'\n', iswalnum(wc)); 2721 realloc_trans_if_necessary(d, s1); 2722 2723 while (*pp - p1 < maxlen) 2724 { 2725 follows.nelem = 0; 2726 rs = transit_state_consume_1char(d, s1, pp, NULL, &mbclen, &follows); 2727 2728 for (i = 0; i < nelem ; i++) 2729 { 2730 if (match_lens[i] == *pp - p1) 2731 for (j = 0; 2732 j < d->follows[d->states[s1].mbps.elems[i].index].nelem; j++) 2733 insert(d->follows[d->states[s1].mbps.elems[i].index].elems[j], 2734 &follows); 2735 } 2736 2737 wc = inputwcs[*pp - mbclen - buf_begin]; 2738 s1 = state_index(d, &follows, wc == L'\n', iswalnum(wc)); 2739 realloc_trans_if_necessary(d, s1); 2740 } 2741 free(match_lens); 2742 free(follows.elems); 2743 return s1; 2744 } 2745 2746 #endif 2747 2748 /* Search through a buffer looking for a match to the given struct dfa. 2749 Find the first occurrence of a string matching the regexp in the buffer, 2750 and the shortest possible version thereof. Return the offset of the first 2751 character after the match, or (size_t) -1 if none is found. BEGIN points to 2752 the beginning of the buffer, and SIZE is the size of the buffer. If SIZE 2753 is nonzero, BEGIN[SIZE - 1] must be a newline. BACKREF points to a place 2754 where we're supposed to store a 1 if backreferencing happened and the 2755 match needs to be verified by a backtracking matcher. Otherwise 2756 we store a 0 in *backref. */ 2757 size_t 2758 dfaexec (struct dfa *d, char const *begin, size_t size, int *backref) 2759 { 2760 register int s; /* Current state. */ 2761 register unsigned char const *p; /* Current input character. */ 2762 register unsigned char const *end; /* One past the last input character. */ 2763 register int **trans, *t; /* Copy of d->trans so it can be optimized 2764 into a register. */ 2765 register unsigned char eol = eolbyte; /* Likewise for eolbyte. */ 2766 static int sbit[NOTCHAR]; /* Table for anding with d->success. */ 2767 static int sbit_init; 2768 2769 if (! sbit_init) 2770 { 2771 int i; 2772 2773 sbit_init = 1; 2774 for (i = 0; i < NOTCHAR; ++i) 2775 sbit[i] = (IS_WORD_CONSTITUENT(i)) ? 2 : 1; 2776 sbit[eol] = 4; 2777 } 2778 2779 if (! d->tralloc) 2780 build_state_zero(d); 2781 2782 s = 0; 2783 p = (unsigned char const *) begin; 2784 end = p + size; 2785 trans = d->trans; 2786 2787 #ifdef MBS_SUPPORT 2788 if (MB_CUR_MAX > 1) 2789 { 2790 int remain_bytes, i; 2791 buf_begin = begin; 2792 buf_end = end; 2793 2794 /* initialize mblen_buf, and inputwcs. */ 2795 MALLOC(mblen_buf, unsigned char, end - (unsigned char const *)begin + 2); 2796 MALLOC(inputwcs, wchar_t, end - (unsigned char const *)begin + 2); 2797 memset(&mbs, 0, sizeof(mbstate_t)); 2798 remain_bytes = 0; 2799 for (i = 0; i < end - (unsigned char const *)begin + 1; i++) 2800 { 2801 if (remain_bytes == 0) 2802 { 2803 remain_bytes 2804 = mbrtowc(inputwcs + i, begin + i, 2805 end - (unsigned char const *)begin - i + 1, &mbs); 2806 if (remain_bytes <= 1) 2807 { 2808 remain_bytes = 0; 2809 inputwcs[i] = (wchar_t)begin[i]; 2810 mblen_buf[i] = 0; 2811 } 2812 else 2813 { 2814 mblen_buf[i] = remain_bytes; 2815 remain_bytes--; 2816 } 2817 } 2818 else 2819 { 2820 mblen_buf[i] = remain_bytes; 2821 inputwcs[i] = 0; 2822 remain_bytes--; 2823 } 2824 } 2825 mblen_buf[i] = 0; 2826 inputwcs[i] = 0; /* sentinel */ 2827 } 2828 #endif /* MBS_SUPPORT */ 2829 2830 for (;;) 2831 { 2832 #ifdef MBS_SUPPORT 2833 if (MB_CUR_MAX > 1) 2834 while ((t = trans[s])) 2835 { 2836 if (d->states[s].mbps.nelem != 0) 2837 { 2838 /* Can match with a multibyte character( and multi character 2839 collating element). */ 2840 unsigned char const *nextp; 2841 2842 SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); 2843 2844 nextp = p; 2845 s = transit_state(d, s, &nextp); 2846 p = nextp; 2847 2848 /* Trans table might be updated. */ 2849 trans = d->trans; 2850 } 2851 else 2852 { 2853 SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); 2854 s = t[*p++]; 2855 } 2856 } 2857 else 2858 #endif /* MBS_SUPPORT */ 2859 while ((t = trans[s])) 2860 s = t[*p++]; 2861 2862 if (s < 0) 2863 { 2864 if (p == end) 2865 { 2866 #ifdef MBS_SUPPORT 2867 if (MB_CUR_MAX > 1) 2868 { 2869 free(mblen_buf); 2870 free(inputwcs); 2871 } 2872 #endif /* MBS_SUPPORT */ 2873 return (size_t) -1; 2874 } 2875 s = 0; 2876 } 2877 else if ((t = d->fails[s])) 2878 { 2879 if (d->success[s] & sbit[*p]) 2880 { 2881 if (backref) 2882 *backref = (d->states[s].backref != 0); 2883 #ifdef MBS_SUPPORT 2884 if (MB_CUR_MAX > 1) 2885 { 2886 free(mblen_buf); 2887 free(inputwcs); 2888 } 2889 #endif /* MBS_SUPPORT */ 2890 return (char const *) p - begin; 2891 } 2892 2893 #ifdef MBS_SUPPORT 2894 if (MB_CUR_MAX > 1) 2895 { 2896 SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p); 2897 if (d->states[s].mbps.nelem != 0) 2898 { 2899 /* Can match with a multibyte character( and multi 2900 character collating element). */ 2901 unsigned char const *nextp; 2902 nextp = p; 2903 s = transit_state(d, s, &nextp); 2904 p = nextp; 2905 2906 /* Trans table might be updated. */ 2907 trans = d->trans; 2908 } 2909 else 2910 s = t[*p++]; 2911 } 2912 else 2913 #endif /* MBS_SUPPORT */ 2914 s = t[*p++]; 2915 } 2916 else 2917 { 2918 build_state(s, d); 2919 trans = d->trans; 2920 } 2921 } 2922 } 2923 2924 /* Initialize the components of a dfa that the other routines don't 2925 initialize for themselves. */ 2926 void 2927 dfainit (struct dfa *d) 2928 { 2929 d->calloc = 1; 2930 MALLOC(d->charclasses, charclass, d->calloc); 2931 d->cindex = 0; 2932 2933 d->talloc = 1; 2934 MALLOC(d->tokens, token, d->talloc); 2935 d->tindex = d->depth = d->nleaves = d->nregexps = 0; 2936 #ifdef MBS_SUPPORT 2937 if (MB_CUR_MAX > 1) 2938 { 2939 d->nmultibyte_prop = 1; 2940 MALLOC(d->multibyte_prop, int, d->nmultibyte_prop); 2941 d->nmbcsets = 0; 2942 d->mbcsets_alloc = 1; 2943 MALLOC(d->mbcsets, struct mb_char_classes, d->mbcsets_alloc); 2944 } 2945 #endif 2946 2947 d->searchflag = 0; 2948 d->tralloc = 0; 2949 2950 d->musts = 0; 2951 } 2952 2953 /* Parse and analyze a single string of the given length. */ 2954 void 2955 dfacomp (char const *s, size_t len, struct dfa *d, int searchflag) 2956 { 2957 if (case_fold) /* dummy folding in service of dfamust() */ 2958 { 2959 char *lcopy; 2960 int i; 2961 2962 lcopy = malloc(len); 2963 if (!lcopy) 2964 dfaerror(_("out of memory")); 2965 2966 /* This is a kludge. */ 2967 case_fold = 0; 2968 for (i = 0; i < len; ++i) 2969 if (ISUPPER ((unsigned char) s[i])) 2970 lcopy[i] = tolower ((unsigned char) s[i]); 2971 else 2972 lcopy[i] = s[i]; 2973 2974 dfainit(d); 2975 dfaparse(lcopy, len, d); 2976 free(lcopy); 2977 dfamust(d); 2978 d->cindex = d->tindex = d->depth = d->nleaves = d->nregexps = 0; 2979 case_fold = 1; 2980 dfaparse(s, len, d); 2981 dfaanalyze(d, searchflag); 2982 } 2983 else 2984 { 2985 dfainit(d); 2986 dfaparse(s, len, d); 2987 dfamust(d); 2988 dfaanalyze(d, searchflag); 2989 } 2990 } 2991 2992 /* Free the storage held by the components of a dfa. */ 2993 void 2994 dfafree (struct dfa *d) 2995 { 2996 int i; 2997 struct dfamust *dm, *ndm; 2998 2999 free((ptr_t) d->charclasses); 3000 free((ptr_t) d->tokens); 3001 3002 #ifdef MBS_SUPPORT 3003 if (MB_CUR_MAX > 1) 3004 { 3005 free((ptr_t) d->multibyte_prop); 3006 for (i = 0; i < d->nmbcsets; ++i) 3007 { 3008 int j; 3009 struct mb_char_classes *p = &(d->mbcsets[i]); 3010 if (p->chars != NULL) 3011 free(p->chars); 3012 if (p->ch_classes != NULL) 3013 free(p->ch_classes); 3014 if (p->range_sts != NULL) 3015 free(p->range_sts); 3016 if (p->range_ends != NULL) 3017 free(p->range_ends); 3018 3019 for (j = 0; j < p->nequivs; ++j) 3020 free(p->equivs[j]); 3021 if (p->equivs != NULL) 3022 free(p->equivs); 3023 3024 for (j = 0; j < p->ncoll_elems; ++j) 3025 free(p->coll_elems[j]); 3026 if (p->coll_elems != NULL) 3027 free(p->coll_elems); 3028 } 3029 free((ptr_t) d->mbcsets); 3030 } 3031 #endif /* MBS_SUPPORT */ 3032 3033 for (i = 0; i < d->sindex; ++i) 3034 free((ptr_t) d->states[i].elems.elems); 3035 free((ptr_t) d->states); 3036 for (i = 0; i < d->tindex; ++i) 3037 if (d->follows[i].elems) 3038 free((ptr_t) d->follows[i].elems); 3039 free((ptr_t) d->follows); 3040 for (i = 0; i < d->tralloc; ++i) 3041 if (d->trans[i]) 3042 free((ptr_t) d->trans[i]); 3043 else if (d->fails[i]) 3044 free((ptr_t) d->fails[i]); 3045 if (d->realtrans) free((ptr_t) d->realtrans); 3046 if (d->fails) free((ptr_t) d->fails); 3047 if (d->success) free((ptr_t) d->success); 3048 for (dm = d->musts; dm; dm = ndm) 3049 { 3050 ndm = dm->next; 3051 free(dm->must); 3052 free((ptr_t) dm); 3053 } 3054 } 3055 3056 /* Having found the postfix representation of the regular expression, 3057 try to find a long sequence of characters that must appear in any line 3058 containing the r.e. 3059 Finding a "longest" sequence is beyond the scope here; 3060 we take an easy way out and hope for the best. 3061 (Take "(ab|a)b"--please.) 3062 3063 We do a bottom-up calculation of sequences of characters that must appear 3064 in matches of r.e.'s represented by trees rooted at the nodes of the postfix 3065 representation: 3066 sequences that must appear at the left of the match ("left") 3067 sequences that must appear at the right of the match ("right") 3068 lists of sequences that must appear somewhere in the match ("in") 3069 sequences that must constitute the match ("is") 3070 3071 When we get to the root of the tree, we use one of the longest of its 3072 calculated "in" sequences as our answer. The sequence we find is returned in 3073 d->must (where "d" is the single argument passed to "dfamust"); 3074 the length of the sequence is returned in d->mustn. 3075 3076 The sequences calculated for the various types of node (in pseudo ANSI c) 3077 are shown below. "p" is the operand of unary operators (and the left-hand 3078 operand of binary operators); "q" is the right-hand operand of binary 3079 operators. 3080 3081 "ZERO" means "a zero-length sequence" below. 3082 3083 Type left right is in 3084 ---- ---- ----- -- -- 3085 char c # c # c # c # c 3086 3087 ANYCHAR ZERO ZERO ZERO ZERO 3088 3089 MBCSET ZERO ZERO ZERO ZERO 3090 3091 CSET ZERO ZERO ZERO ZERO 3092 3093 STAR ZERO ZERO ZERO ZERO 3094 3095 QMARK ZERO ZERO ZERO ZERO 3096 3097 PLUS p->left p->right ZERO p->in 3098 3099 CAT (p->is==ZERO)? (q->is==ZERO)? (p->is!=ZERO && p->in plus 3100 p->left : q->right : q->is!=ZERO) ? q->in plus 3101 p->is##q->left p->right##q->is p->is##q->is : p->right##q->left 3102 ZERO 3103 3104 OR longest common longest common (do p->is and substrings common to 3105 leading trailing q->is have same p->in and q->in 3106 (sub)sequence (sub)sequence length and 3107 of p->left of p->right content) ? 3108 and q->left and q->right p->is : NULL 3109 3110 If there's anything else we recognize in the tree, all four sequences get set 3111 to zero-length sequences. If there's something we don't recognize in the tree, 3112 we just return a zero-length sequence. 3113 3114 Break ties in favor of infrequent letters (choosing 'zzz' in preference to 3115 'aaa')? 3116 3117 And. . .is it here or someplace that we might ponder "optimizations" such as 3118 egrep 'psi|epsilon' -> egrep 'psi' 3119 egrep 'pepsi|epsilon' -> egrep 'epsi' 3120 (Yes, we now find "epsi" as a "string 3121 that must occur", but we might also 3122 simplify the *entire* r.e. being sought) 3123 grep '[c]' -> grep 'c' 3124 grep '(ab|a)b' -> grep 'ab' 3125 grep 'ab*' -> grep 'a' 3126 grep 'a*b' -> grep 'b' 3127 3128 There are several issues: 3129 3130 Is optimization easy (enough)? 3131 3132 Does optimization actually accomplish anything, 3133 or is the automaton you get from "psi|epsilon" (for example) 3134 the same as the one you get from "psi" (for example)? 3135 3136 Are optimizable r.e.'s likely to be used in real-life situations 3137 (something like 'ab*' is probably unlikely; something like is 3138 'psi|epsilon' is likelier)? */ 3139 3140 static char * 3141 icatalloc (char *old, char *new) 3142 { 3143 char *result; 3144 size_t oldsize, newsize; 3145 3146 newsize = (new == NULL) ? 0 : strlen(new); 3147 if (old == NULL) 3148 oldsize = 0; 3149 else if (newsize == 0) 3150 return old; 3151 else oldsize = strlen(old); 3152 if (old == NULL) 3153 result = (char *) malloc(newsize + 1); 3154 else 3155 result = (char *) realloc((void *) old, oldsize + newsize + 1); 3156 if (result != NULL && new != NULL) 3157 (void) strcpy(result + oldsize, new); 3158 return result; 3159 } 3160 3161 static char * 3162 icpyalloc (char *string) 3163 { 3164 return icatalloc((char *) NULL, string); 3165 } 3166 3167 static char * 3168 istrstr (char *lookin, char *lookfor) 3169 { 3170 char *cp; 3171 size_t len; 3172 3173 len = strlen(lookfor); 3174 for (cp = lookin; *cp != '\0'; ++cp) 3175 if (strncmp(cp, lookfor, len) == 0) 3176 return cp; 3177 return NULL; 3178 } 3179 3180 static void 3181 ifree (char *cp) 3182 { 3183 if (cp != NULL) 3184 free(cp); 3185 } 3186 3187 static void 3188 freelist (char **cpp) 3189 { 3190 int i; 3191 3192 if (cpp == NULL) 3193 return; 3194 for (i = 0; cpp[i] != NULL; ++i) 3195 { 3196 free(cpp[i]); 3197 cpp[i] = NULL; 3198 } 3199 } 3200 3201 static char ** 3202 enlist (char **cpp, char *new, size_t len) 3203 { 3204 int i, j; 3205 3206 if (cpp == NULL) 3207 return NULL; 3208 if ((new = icpyalloc(new)) == NULL) 3209 { 3210 freelist(cpp); 3211 return NULL; 3212 } 3213 new[len] = '\0'; 3214 /* Is there already something in the list that's new (or longer)? */ 3215 for (i = 0; cpp[i] != NULL; ++i) 3216 if (istrstr(cpp[i], new) != NULL) 3217 { 3218 free(new); 3219 return cpp; 3220 } 3221 /* Eliminate any obsoleted strings. */ 3222 j = 0; 3223 while (cpp[j] != NULL) 3224 if (istrstr(new, cpp[j]) == NULL) 3225 ++j; 3226 else 3227 { 3228 free(cpp[j]); 3229 if (--i == j) 3230 break; 3231 cpp[j] = cpp[i]; 3232 cpp[i] = NULL; 3233 } 3234 /* Add the new string. */ 3235 cpp = (char **) realloc((char *) cpp, (i + 2) * sizeof *cpp); 3236 if (cpp == NULL) 3237 return NULL; 3238 cpp[i] = new; 3239 cpp[i + 1] = NULL; 3240 return cpp; 3241 } 3242 3243 /* Given pointers to two strings, return a pointer to an allocated 3244 list of their distinct common substrings. Return NULL if something 3245 seems wild. */ 3246 static char ** 3247 comsubs (char *left, char *right) 3248 { 3249 char **cpp; 3250 char *lcp; 3251 char *rcp; 3252 size_t i, len; 3253 3254 if (left == NULL || right == NULL) 3255 return NULL; 3256 cpp = (char **) malloc(sizeof *cpp); 3257 if (cpp == NULL) 3258 return NULL; 3259 cpp[0] = NULL; 3260 for (lcp = left; *lcp != '\0'; ++lcp) 3261 { 3262 len = 0; 3263 rcp = strchr (right, *lcp); 3264 while (rcp != NULL) 3265 { 3266 for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i) 3267 continue; 3268 if (i > len) 3269 len = i; 3270 rcp = strchr (rcp + 1, *lcp); 3271 } 3272 if (len == 0) 3273 continue; 3274 if ((cpp = enlist(cpp, lcp, len)) == NULL) 3275 break; 3276 } 3277 return cpp; 3278 } 3279 3280 static char ** 3281 addlists (char **old, char **new) 3282 { 3283 int i; 3284 3285 if (old == NULL || new == NULL) 3286 return NULL; 3287 for (i = 0; new[i] != NULL; ++i) 3288 { 3289 old = enlist(old, new[i], strlen(new[i])); 3290 if (old == NULL) 3291 break; 3292 } 3293 return old; 3294 } 3295 3296 /* Given two lists of substrings, return a new list giving substrings 3297 common to both. */ 3298 static char ** 3299 inboth (char **left, char **right) 3300 { 3301 char **both; 3302 char **temp; 3303 int lnum, rnum; 3304 3305 if (left == NULL || right == NULL) 3306 return NULL; 3307 both = (char **) malloc(sizeof *both); 3308 if (both == NULL) 3309 return NULL; 3310 both[0] = NULL; 3311 for (lnum = 0; left[lnum] != NULL; ++lnum) 3312 { 3313 for (rnum = 0; right[rnum] != NULL; ++rnum) 3314 { 3315 temp = comsubs(left[lnum], right[rnum]); 3316 if (temp == NULL) 3317 { 3318 freelist(both); 3319 return NULL; 3320 } 3321 both = addlists(both, temp); 3322 freelist(temp); 3323 free(temp); 3324 if (both == NULL) 3325 return NULL; 3326 } 3327 } 3328 return both; 3329 } 3330 3331 typedef struct 3332 { 3333 char **in; 3334 char *left; 3335 char *right; 3336 char *is; 3337 } must; 3338 3339 static void 3340 resetmust (must *mp) 3341 { 3342 mp->left[0] = mp->right[0] = mp->is[0] = '\0'; 3343 freelist(mp->in); 3344 } 3345 3346 static void 3347 dfamust (struct dfa *dfa) 3348 { 3349 must *musts; 3350 must *mp; 3351 char *result; 3352 int ri; 3353 int i; 3354 int exact; 3355 token t; 3356 static must must0; 3357 struct dfamust *dm; 3358 static char empty_string[] = ""; 3359 3360 result = empty_string; 3361 exact = 0; 3362 musts = (must *) malloc((dfa->tindex + 1) * sizeof *musts); 3363 if (musts == NULL) 3364 return; 3365 mp = musts; 3366 for (i = 0; i <= dfa->tindex; ++i) 3367 mp[i] = must0; 3368 for (i = 0; i <= dfa->tindex; ++i) 3369 { 3370 mp[i].in = (char **) malloc(sizeof *mp[i].in); 3371 mp[i].left = malloc(2); 3372 mp[i].right = malloc(2); 3373 mp[i].is = malloc(2); 3374 if (mp[i].in == NULL || mp[i].left == NULL || 3375 mp[i].right == NULL || mp[i].is == NULL) 3376 goto done; 3377 mp[i].left[0] = mp[i].right[0] = mp[i].is[0] = '\0'; 3378 mp[i].in[0] = NULL; 3379 } 3380 #ifdef DEBUG 3381 fprintf(stderr, "dfamust:\n"); 3382 for (i = 0; i < dfa->tindex; ++i) 3383 { 3384 fprintf(stderr, " %d:", i); 3385 prtok(dfa->tokens[i]); 3386 } 3387 putc('\n', stderr); 3388 #endif 3389 for (ri = 0; ri < dfa->tindex; ++ri) 3390 { 3391 switch (t = dfa->tokens[ri]) 3392 { 3393 case LPAREN: 3394 case RPAREN: 3395 goto done; /* "cannot happen" */ 3396 case EMPTY: 3397 case BEGLINE: 3398 case ENDLINE: 3399 case BEGWORD: 3400 case ENDWORD: 3401 case LIMWORD: 3402 case NOTLIMWORD: 3403 case BACKREF: 3404 resetmust(mp); 3405 break; 3406 case STAR: 3407 case QMARK: 3408 if (mp <= musts) 3409 goto done; /* "cannot happen" */ 3410 --mp; 3411 resetmust(mp); 3412 break; 3413 case OR: 3414 case ORTOP: 3415 if (mp < &musts[2]) 3416 goto done; /* "cannot happen" */ 3417 { 3418 char **new; 3419 must *lmp; 3420 must *rmp; 3421 int j, ln, rn, n; 3422 3423 rmp = --mp; 3424 lmp = --mp; 3425 /* Guaranteed to be. Unlikely, but. . . */ 3426 if (strcmp(lmp->is, rmp->is) != 0) 3427 lmp->is[0] = '\0'; 3428 /* Left side--easy */ 3429 i = 0; 3430 while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i]) 3431 ++i; 3432 lmp->left[i] = '\0'; 3433 /* Right side */ 3434 ln = strlen(lmp->right); 3435 rn = strlen(rmp->right); 3436 n = ln; 3437 if (n > rn) 3438 n = rn; 3439 for (i = 0; i < n; ++i) 3440 if (lmp->right[ln - i - 1] != rmp->right[rn - i - 1]) 3441 break; 3442 for (j = 0; j < i; ++j) 3443 lmp->right[j] = lmp->right[(ln - i) + j]; 3444 lmp->right[j] = '\0'; 3445 new = inboth(lmp->in, rmp->in); 3446 if (new == NULL) 3447 goto done; 3448 freelist(lmp->in); 3449 free((char *) lmp->in); 3450 lmp->in = new; 3451 } 3452 break; 3453 case PLUS: 3454 if (mp <= musts) 3455 goto done; /* "cannot happen" */ 3456 --mp; 3457 mp->is[0] = '\0'; 3458 break; 3459 case END: 3460 if (mp != &musts[1]) 3461 goto done; /* "cannot happen" */ 3462 for (i = 0; musts[0].in[i] != NULL; ++i) 3463 if (strlen(musts[0].in[i]) > strlen(result)) 3464 result = musts[0].in[i]; 3465 if (strcmp(result, musts[0].is) == 0) 3466 exact = 1; 3467 goto done; 3468 case CAT: 3469 if (mp < &musts[2]) 3470 goto done; /* "cannot happen" */ 3471 { 3472 must *lmp; 3473 must *rmp; 3474 3475 rmp = --mp; 3476 lmp = --mp; 3477 /* In. Everything in left, plus everything in 3478 right, plus catenation of 3479 left's right and right's left. */ 3480 lmp->in = addlists(lmp->in, rmp->in); 3481 if (lmp->in == NULL) 3482 goto done; 3483 if (lmp->right[0] != '\0' && 3484 rmp->left[0] != '\0') 3485 { 3486 char *tp; 3487 3488 tp = icpyalloc(lmp->right); 3489 if (tp == NULL) 3490 goto done; 3491 tp = icatalloc(tp, rmp->left); 3492 if (tp == NULL) 3493 goto done; 3494 lmp->in = enlist(lmp->in, tp, 3495 strlen(tp)); 3496 free(tp); 3497 if (lmp->in == NULL) 3498 goto done; 3499 } 3500 /* Left-hand */ 3501 if (lmp->is[0] != '\0') 3502 { 3503 lmp->left = icatalloc(lmp->left, 3504 rmp->left); 3505 if (lmp->left == NULL) 3506 goto done; 3507 } 3508 /* Right-hand */ 3509 if (rmp->is[0] == '\0') 3510 lmp->right[0] = '\0'; 3511 lmp->right = icatalloc(lmp->right, rmp->right); 3512 if (lmp->right == NULL) 3513 goto done; 3514 /* Guaranteed to be */ 3515 if (lmp->is[0] != '\0' && rmp->is[0] != '\0') 3516 { 3517 lmp->is = icatalloc(lmp->is, rmp->is); 3518 if (lmp->is == NULL) 3519 goto done; 3520 } 3521 else 3522 lmp->is[0] = '\0'; 3523 } 3524 break; 3525 default: 3526 if (t < END) 3527 { 3528 /* "cannot happen" */ 3529 goto done; 3530 } 3531 else if (t == '\0') 3532 { 3533 /* not on *my* shift */ 3534 goto done; 3535 } 3536 else if (t >= CSET 3537 #ifdef MBS_SUPPORT 3538 || t == ANYCHAR 3539 || t == MBCSET 3540 #endif /* MBS_SUPPORT */ 3541 ) 3542 { 3543 /* easy enough */ 3544 resetmust(mp); 3545 } 3546 else 3547 { 3548 /* plain character */ 3549 resetmust(mp); 3550 mp->is[0] = mp->left[0] = mp->right[0] = t; 3551 mp->is[1] = mp->left[1] = mp->right[1] = '\0'; 3552 mp->in = enlist(mp->in, mp->is, (size_t)1); 3553 if (mp->in == NULL) 3554 goto done; 3555 } 3556 break; 3557 } 3558 #ifdef DEBUG 3559 fprintf(stderr, " node: %d:", ri); 3560 prtok(dfa->tokens[ri]); 3561 fprintf(stderr, "\n in:"); 3562 for (i = 0; mp->in[i]; ++i) 3563 fprintf(stderr, " \"%s\"", mp->in[i]); 3564 fprintf(stderr, "\n is: \"%s\"\n", mp->is); 3565 fprintf(stderr, " left: \"%s\"\n", mp->left); 3566 fprintf(stderr, " right: \"%s\"\n", mp->right); 3567 #endif 3568 ++mp; 3569 } 3570 done: 3571 if (strlen(result)) 3572 { 3573 dm = (struct dfamust *) malloc(sizeof (struct dfamust)); 3574 dm->exact = exact; 3575 dm->must = malloc(strlen(result) + 1); 3576 strcpy(dm->must, result); 3577 dm->next = dfa->musts; 3578 dfa->musts = dm; 3579 } 3580 mp = musts; 3581 for (i = 0; i <= dfa->tindex; ++i) 3582 { 3583 freelist(mp[i].in); 3584 ifree((char *) mp[i].in); 3585 ifree(mp[i].left); 3586 ifree(mp[i].right); 3587 ifree(mp[i].is); 3588 } 3589 free((char *) mp); 3590 } 3591 /* vim:set shiftwidth=2: */ 3592