1 /* Extended regular expression matching and search library, version 2 0.12. (Implements POSIX draft P10003.2/D11.2, except for 3 internationalization features.) 4 5 Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998 Free Software Foundation, Inc. 6 7 This program is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 2, or (at your option) 10 any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program; if not, write to the Free Software 19 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20 USA. */ 21 22 /* AIX requires this to be the first thing in the file. */ 23 #if defined (_AIX) && !defined (REGEX_MALLOC) 24 #pragma alloca 25 #endif 26 27 #undef _GNU_SOURCE 28 #define _GNU_SOURCE 29 30 #ifdef emacs 31 /* Converts the pointer to the char to BEG-based offset from the start. */ 32 #define PTR_TO_OFFSET(d) \ 33 POS_AS_IN_BUFFER (MATCHING_IN_FIRST_STRING \ 34 ? (d) - string1 : (d) - (string2 - size1)) 35 #define POS_AS_IN_BUFFER(p) ((p) + (NILP (re_match_object) || BUFFERP (re_match_object))) 36 #else 37 #define PTR_TO_OFFSET(d) 0 38 #endif 39 40 #ifdef HAVE_CONFIG_H 41 #include <config.h> 42 #endif 43 44 /* We need this for `regex.h', and perhaps for the Emacs include files. */ 45 #include <sys/types.h> 46 47 /* This is for other GNU distributions with internationalized messages. */ 48 #if HAVE_LIBINTL_H || defined (_LIBC) 49 # include <libintl.h> 50 #else 51 # define gettext(msgid) (msgid) 52 #endif 53 54 #ifndef gettext_noop 55 /* This define is so xgettext can find the internationalizable 56 strings. */ 57 #define gettext_noop(String) String 58 #endif 59 60 /* The `emacs' switch turns on certain matching commands 61 that make sense only in Emacs. */ 62 #ifdef emacs 63 64 #include "lisp.h" 65 #include "buffer.h" 66 67 /* Make syntax table lookup grant data in gl_state. */ 68 #define SYNTAX_ENTRY_VIA_PROPERTY 69 70 #include "syntax.h" 71 #include "charset.h" 72 #include "category.h" 73 74 #define malloc xmalloc 75 #define realloc xrealloc 76 #define free xfree 77 78 #else /* not emacs */ 79 80 /* If we are not linking with Emacs proper, 81 we can't use the relocating allocator 82 even if config.h says that we can. */ 83 #undef REL_ALLOC 84 85 #if defined (STDC_HEADERS) || defined (_LIBC) 86 #include <stdlib.h> 87 #else 88 char *malloc (); 89 char *realloc (); 90 #endif 91 92 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow. 93 If nothing else has been done, use the method below. */ 94 #ifdef INHIBIT_STRING_HEADER 95 #if !(defined (HAVE_BZERO) && defined (HAVE_BCOPY)) 96 #if !defined (bzero) && !defined (bcopy) 97 #undef INHIBIT_STRING_HEADER 98 #endif 99 #endif 100 #endif 101 102 /* This is the normal way of making sure we have a bcopy and a bzero. 103 This is used in most programs--a few other programs avoid this 104 by defining INHIBIT_STRING_HEADER. */ 105 #ifndef INHIBIT_STRING_HEADER 106 #if defined (HAVE_STRING_H) || defined (STDC_HEADERS) || defined (_LIBC) 107 #include <string.h> 108 #ifndef bcmp 109 #define bcmp(s1, s2, n) memcmp ((s1), (s2), (n)) 110 #endif 111 #ifndef bcopy 112 #define bcopy(s, d, n) memcpy ((d), (s), (n)) 113 #endif 114 #ifndef bzero 115 #define bzero(s, n) memset ((s), 0, (n)) 116 #endif 117 #else 118 #include <strings.h> 119 #endif 120 #endif 121 122 /* Define the syntax stuff for \<, \>, etc. */ 123 124 /* This must be nonzero for the wordchar and notwordchar pattern 125 commands in re_match_2. */ 126 #ifndef Sword 127 #define Sword 1 128 #endif 129 130 #ifdef SWITCH_ENUM_BUG 131 #define SWITCH_ENUM_CAST(x) ((int)(x)) 132 #else 133 #define SWITCH_ENUM_CAST(x) (x) 134 #endif 135 136 #ifdef SYNTAX_TABLE 137 138 extern char *re_syntax_table; 139 140 #else /* not SYNTAX_TABLE */ 141 142 /* How many characters in the character set. */ 143 #define CHAR_SET_SIZE 256 144 145 static char re_syntax_table[CHAR_SET_SIZE]; 146 147 static void 148 init_syntax_once () 149 { 150 register int c; 151 static int done = 0; 152 153 if (done) 154 return; 155 156 bzero (re_syntax_table, sizeof re_syntax_table); 157 158 for (c = 'a'; c <= 'z'; c++) 159 re_syntax_table[c] = Sword; 160 161 for (c = 'A'; c <= 'Z'; c++) 162 re_syntax_table[c] = Sword; 163 164 for (c = '0'; c <= '9'; c++) 165 re_syntax_table[c] = Sword; 166 167 re_syntax_table['_'] = Sword; 168 169 done = 1; 170 } 171 172 #endif /* not SYNTAX_TABLE */ 173 174 #define SYNTAX(c) re_syntax_table[c] 175 176 /* Dummy macros for non-Emacs environments. */ 177 #define BASE_LEADING_CODE_P(c) (0) 178 #define WORD_BOUNDARY_P(c1, c2) (0) 179 #define CHAR_HEAD_P(p) (1) 180 #define SINGLE_BYTE_CHAR_P(c) (1) 181 #define SAME_CHARSET_P(c1, c2) (1) 182 #define MULTIBYTE_FORM_LENGTH(p, s) (1) 183 #define STRING_CHAR(p, s) (*(p)) 184 #define STRING_CHAR_AND_LENGTH(p, s, actual_len) ((actual_len) = 1, *(p)) 185 #define GET_CHAR_AFTER_2(c, p, str1, end1, str2, end2) \ 186 (c = ((p) == (end1) ? *(str2) : *(p))) 187 #define GET_CHAR_BEFORE_2(c, p, str1, end1, str2, end2) \ 188 (c = ((p) == (str2) ? *((end1) - 1) : *((p) - 1))) 189 #endif /* not emacs */ 190 191 /* Get the interface, including the syntax bits. */ 192 #include "regex.h" 193 194 /* isalpha etc. are used for the character classes. */ 195 #include <ctype.h> 196 197 /* Jim Meyering writes: 198 199 "... Some ctype macros are valid only for character codes that 200 isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when 201 using /bin/cc or gcc but without giving an ansi option). So, all 202 ctype uses should be through macros like ISPRINT... If 203 STDC_HEADERS is defined, then autoconf has verified that the ctype 204 macros don't need to be guarded with references to isascii. ... 205 Defining isascii to 1 should let any compiler worth its salt 206 eliminate the && through constant folding." */ 207 208 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII)) 209 #define ISASCII(c) 1 210 #else 211 #define ISASCII(c) isascii(c) 212 #endif 213 214 #ifdef isblank 215 #define ISBLANK(c) (ISASCII (c) && isblank (c)) 216 #else 217 #define ISBLANK(c) ((c) == ' ' || (c) == '\t') 218 #endif 219 #ifdef isgraph 220 #define ISGRAPH(c) (ISASCII (c) && isgraph (c)) 221 #else 222 #define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c)) 223 #endif 224 225 #define ISPRINT(c) (ISASCII (c) && isprint (c)) 226 #define ISDIGIT(c) (ISASCII (c) && isdigit (c)) 227 #define ISALNUM(c) (ISASCII (c) && isalnum (c)) 228 #define ISALPHA(c) (ISASCII (c) && isalpha (c)) 229 #define ISCNTRL(c) (ISASCII (c) && iscntrl (c)) 230 #define ISLOWER(c) (ISASCII (c) && islower (c)) 231 #define ISPUNCT(c) (ISASCII (c) && ispunct (c)) 232 #define ISSPACE(c) (ISASCII (c) && isspace (c)) 233 #define ISUPPER(c) (ISASCII (c) && isupper (c)) 234 #define ISXDIGIT(c) (ISASCII (c) && isxdigit (c)) 235 236 #ifndef NULL 237 #define NULL (void *)0 238 #endif 239 240 /* We remove any previous definition of `SIGN_EXTEND_CHAR', 241 since ours (we hope) works properly with all combinations of 242 machines, compilers, `char' and `unsigned char' argument types. 243 (Per Bothner suggested the basic approach.) */ 244 #undef SIGN_EXTEND_CHAR 245 #if __STDC__ 246 #define SIGN_EXTEND_CHAR(c) ((signed char) (c)) 247 #else /* not __STDC__ */ 248 /* As in Harbison and Steele. */ 249 #define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128) 250 #endif 251 252 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we 253 use `alloca' instead of `malloc'. This is because using malloc in 254 re_search* or re_match* could cause memory leaks when C-g is used in 255 Emacs; also, malloc is slower and causes storage fragmentation. On 256 the other hand, malloc is more portable, and easier to debug. 257 258 Because we sometimes use alloca, some routines have to be macros, 259 not functions -- `alloca'-allocated space disappears at the end of the 260 function it is called in. */ 261 262 #ifdef REGEX_MALLOC 263 264 #define REGEX_ALLOCATE malloc 265 #define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize) 266 #define REGEX_FREE free 267 268 #else /* not REGEX_MALLOC */ 269 270 /* Emacs already defines alloca, sometimes. */ 271 #ifndef alloca 272 273 /* Make alloca work the best possible way. */ 274 #ifdef __GNUC__ 275 #define alloca __builtin_alloca 276 #else /* not __GNUC__ */ 277 #if HAVE_ALLOCA_H 278 #include <alloca.h> 279 #else /* not __GNUC__ or HAVE_ALLOCA_H */ 280 #if 0 /* It is a bad idea to declare alloca. We always cast the result. */ 281 #ifndef _AIX /* Already did AIX, up at the top. */ 282 char *alloca (); 283 #endif /* not _AIX */ 284 #endif 285 #endif /* not HAVE_ALLOCA_H */ 286 #endif /* not __GNUC__ */ 287 288 #endif /* not alloca */ 289 290 #define REGEX_ALLOCATE alloca 291 292 /* Assumes a `char *destination' variable. */ 293 #define REGEX_REALLOCATE(source, osize, nsize) \ 294 (destination = (char *) alloca (nsize), \ 295 bcopy (source, destination, osize), \ 296 destination) 297 298 /* No need to do anything to free, after alloca. */ 299 #define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */ 300 301 #endif /* not REGEX_MALLOC */ 302 303 /* Define how to allocate the failure stack. */ 304 305 #if defined (REL_ALLOC) && defined (REGEX_MALLOC) 306 307 #define REGEX_ALLOCATE_STACK(size) \ 308 r_alloc (&failure_stack_ptr, (size)) 309 #define REGEX_REALLOCATE_STACK(source, osize, nsize) \ 310 r_re_alloc (&failure_stack_ptr, (nsize)) 311 #define REGEX_FREE_STACK(ptr) \ 312 r_alloc_free (&failure_stack_ptr) 313 314 #else /* not using relocating allocator */ 315 316 #ifdef REGEX_MALLOC 317 318 #define REGEX_ALLOCATE_STACK malloc 319 #define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize) 320 #define REGEX_FREE_STACK free 321 322 #else /* not REGEX_MALLOC */ 323 324 #define REGEX_ALLOCATE_STACK alloca 325 326 #define REGEX_REALLOCATE_STACK(source, osize, nsize) \ 327 REGEX_REALLOCATE (source, osize, nsize) 328 /* No need to explicitly free anything. */ 329 #define REGEX_FREE_STACK(arg) 330 331 #endif /* not REGEX_MALLOC */ 332 #endif /* not using relocating allocator */ 333 334 335 /* True if `size1' is non-NULL and PTR is pointing anywhere inside 336 `string1' or just past its end. This works if PTR is NULL, which is 337 a good thing. */ 338 #define FIRST_STRING_P(ptr) \ 339 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1) 340 341 /* (Re)Allocate N items of type T using malloc, or fail. */ 342 #define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t))) 343 #define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t))) 344 #define RETALLOC_IF(addr, n, t) \ 345 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t) 346 #define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t))) 347 348 #define BYTEWIDTH 8 /* In bits. */ 349 350 #define STREQ(s1, s2) ((strcmp (s1, s2) == 0)) 351 352 #undef MAX 353 #undef MIN 354 #define MAX(a, b) ((a) > (b) ? (a) : (b)) 355 #define MIN(a, b) ((a) < (b) ? (a) : (b)) 356 357 typedef char boolean; 358 #define false 0 359 #define true 1 360 361 static int re_match_2_internal (); 362 363 /* These are the command codes that appear in compiled regular 364 expressions. Some opcodes are followed by argument bytes. A 365 command code can specify any interpretation whatsoever for its 366 arguments. Zero bytes may appear in the compiled regular expression. */ 367 368 typedef enum 369 { 370 no_op = 0, 371 372 /* Succeed right away--no more backtracking. */ 373 succeed, 374 375 /* Followed by one byte giving n, then by n literal bytes. */ 376 exactn, 377 378 /* Matches any (more or less) character. */ 379 anychar, 380 381 /* Matches any one char belonging to specified set. First 382 following byte is number of bitmap bytes. Then come bytes 383 for a bitmap saying which chars are in. Bits in each byte 384 are ordered low-bit-first. A character is in the set if its 385 bit is 1. A character too large to have a bit in the map is 386 automatically not in the set. */ 387 charset, 388 389 /* Same parameters as charset, but match any character that is 390 not one of those specified. */ 391 charset_not, 392 393 /* Start remembering the text that is matched, for storing in a 394 register. Followed by one byte with the register number, in 395 the range 0 to one less than the pattern buffer's re_nsub 396 field. Then followed by one byte with the number of groups 397 inner to this one. (This last has to be part of the 398 start_memory only because we need it in the on_failure_jump 399 of re_match_2.) */ 400 start_memory, 401 402 /* Stop remembering the text that is matched and store it in a 403 memory register. Followed by one byte with the register 404 number, in the range 0 to one less than `re_nsub' in the 405 pattern buffer, and one byte with the number of inner groups, 406 just like `start_memory'. (We need the number of inner 407 groups here because we don't have any easy way of finding the 408 corresponding start_memory when we're at a stop_memory.) */ 409 stop_memory, 410 411 /* Match a duplicate of something remembered. Followed by one 412 byte containing the register number. */ 413 duplicate, 414 415 /* Fail unless at beginning of line. */ 416 begline, 417 418 /* Fail unless at end of line. */ 419 endline, 420 421 /* Succeeds if at beginning of buffer (if emacs) or at beginning 422 of string to be matched (if not). */ 423 begbuf, 424 425 /* Analogously, for end of buffer/string. */ 426 endbuf, 427 428 /* Followed by two byte relative address to which to jump. */ 429 jump, 430 431 /* Same as jump, but marks the end of an alternative. */ 432 jump_past_alt, 433 434 /* Followed by two-byte relative address of place to resume at 435 in case of failure. */ 436 on_failure_jump, 437 438 /* Like on_failure_jump, but pushes a placeholder instead of the 439 current string position when executed. */ 440 on_failure_keep_string_jump, 441 442 /* Throw away latest failure point and then jump to following 443 two-byte relative address. */ 444 pop_failure_jump, 445 446 /* Change to pop_failure_jump if know won't have to backtrack to 447 match; otherwise change to jump. This is used to jump 448 back to the beginning of a repeat. If what follows this jump 449 clearly won't match what the repeat does, such that we can be 450 sure that there is no use backtracking out of repetitions 451 already matched, then we change it to a pop_failure_jump. 452 Followed by two-byte address. */ 453 maybe_pop_jump, 454 455 /* Jump to following two-byte address, and push a dummy failure 456 point. This failure point will be thrown away if an attempt 457 is made to use it for a failure. A `+' construct makes this 458 before the first repeat. Also used as an intermediary kind 459 of jump when compiling an alternative. */ 460 dummy_failure_jump, 461 462 /* Push a dummy failure point and continue. Used at the end of 463 alternatives. */ 464 push_dummy_failure, 465 466 /* Followed by two-byte relative address and two-byte number n. 467 After matching N times, jump to the address upon failure. */ 468 succeed_n, 469 470 /* Followed by two-byte relative address, and two-byte number n. 471 Jump to the address N times, then fail. */ 472 jump_n, 473 474 /* Set the following two-byte relative address to the 475 subsequent two-byte number. The address *includes* the two 476 bytes of number. */ 477 set_number_at, 478 479 wordchar, /* Matches any word-constituent character. */ 480 notwordchar, /* Matches any char that is not a word-constituent. */ 481 482 wordbeg, /* Succeeds if at word beginning. */ 483 wordend, /* Succeeds if at word end. */ 484 485 wordbound, /* Succeeds if at a word boundary. */ 486 notwordbound /* Succeeds if not at a word boundary. */ 487 488 #ifdef emacs 489 ,before_dot, /* Succeeds if before point. */ 490 at_dot, /* Succeeds if at point. */ 491 after_dot, /* Succeeds if after point. */ 492 493 /* Matches any character whose syntax is specified. Followed by 494 a byte which contains a syntax code, e.g., Sword. */ 495 syntaxspec, 496 497 /* Matches any character whose syntax is not that specified. */ 498 notsyntaxspec, 499 500 /* Matches any character whose category-set contains the specified 501 category. The operator is followed by a byte which contains a 502 category code (mnemonic ASCII character). */ 503 categoryspec, 504 505 /* Matches any character whose category-set does not contain the 506 specified category. The operator is followed by a byte which 507 contains the category code (mnemonic ASCII character). */ 508 notcategoryspec 509 #endif /* emacs */ 510 } re_opcode_t; 511 512 /* Common operations on the compiled pattern. */ 513 514 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */ 515 516 #define STORE_NUMBER(destination, number) \ 517 do { \ 518 (destination)[0] = (number) & 0377; \ 519 (destination)[1] = (number) >> 8; \ 520 } while (0) 521 522 /* Same as STORE_NUMBER, except increment DESTINATION to 523 the byte after where the number is stored. Therefore, DESTINATION 524 must be an lvalue. */ 525 526 #define STORE_NUMBER_AND_INCR(destination, number) \ 527 do { \ 528 STORE_NUMBER (destination, number); \ 529 (destination) += 2; \ 530 } while (0) 531 532 /* Put into DESTINATION a number stored in two contiguous bytes starting 533 at SOURCE. */ 534 535 #define EXTRACT_NUMBER(destination, source) \ 536 do { \ 537 (destination) = *(source) & 0377; \ 538 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \ 539 } while (0) 540 541 #ifdef DEBUG 542 static void 543 extract_number (dest, source) 544 int *dest; 545 unsigned char *source; 546 { 547 int temp = SIGN_EXTEND_CHAR (*(source + 1)); 548 *dest = *source & 0377; 549 *dest += temp << 8; 550 } 551 552 #ifndef EXTRACT_MACROS /* To debug the macros. */ 553 #undef EXTRACT_NUMBER 554 #define EXTRACT_NUMBER(dest, src) extract_number (&dest, src) 555 #endif /* not EXTRACT_MACROS */ 556 557 #endif /* DEBUG */ 558 559 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number. 560 SOURCE must be an lvalue. */ 561 562 #define EXTRACT_NUMBER_AND_INCR(destination, source) \ 563 do { \ 564 EXTRACT_NUMBER (destination, source); \ 565 (source) += 2; \ 566 } while (0) 567 568 #ifdef DEBUG 569 static void 570 extract_number_and_incr (destination, source) 571 int *destination; 572 unsigned char **source; 573 { 574 extract_number (destination, *source); 575 *source += 2; 576 } 577 578 #ifndef EXTRACT_MACROS 579 #undef EXTRACT_NUMBER_AND_INCR 580 #define EXTRACT_NUMBER_AND_INCR(dest, src) \ 581 extract_number_and_incr (&dest, &src) 582 #endif /* not EXTRACT_MACROS */ 583 584 #endif /* DEBUG */ 585 586 /* Store a multibyte character in three contiguous bytes starting 587 DESTINATION, and increment DESTINATION to the byte after where the 588 character is stored. Therefore, DESTINATION must be an lvalue. */ 589 590 #define STORE_CHARACTER_AND_INCR(destination, character) \ 591 do { \ 592 (destination)[0] = (character) & 0377; \ 593 (destination)[1] = ((character) >> 8) & 0377; \ 594 (destination)[2] = (character) >> 16; \ 595 (destination) += 3; \ 596 } while (0) 597 598 /* Put into DESTINATION a character stored in three contiguous bytes 599 starting at SOURCE. */ 600 601 #define EXTRACT_CHARACTER(destination, source) \ 602 do { \ 603 (destination) = ((source)[0] \ 604 | ((source)[1] << 8) \ 605 | ((source)[2] << 16)); \ 606 } while (0) 607 608 609 /* Macros for charset. */ 610 611 /* Size of bitmap of charset P in bytes. P is a start of charset, 612 i.e. *P is (re_opcode_t) charset or (re_opcode_t) charset_not. */ 613 #define CHARSET_BITMAP_SIZE(p) ((p)[1] & 0x7F) 614 615 /* Nonzero if charset P has range table. */ 616 #define CHARSET_RANGE_TABLE_EXISTS_P(p) ((p)[1] & 0x80) 617 618 /* Return the address of range table of charset P. But not the start 619 of table itself, but the before where the number of ranges is 620 stored. `2 +' means to skip re_opcode_t and size of bitmap. */ 621 #define CHARSET_RANGE_TABLE(p) (&(p)[2 + CHARSET_BITMAP_SIZE (p)]) 622 623 /* Test if C is listed in the bitmap of charset P. */ 624 #define CHARSET_LOOKUP_BITMAP(p, c) \ 625 ((c) < CHARSET_BITMAP_SIZE (p) * BYTEWIDTH \ 626 && (p)[2 + (c) / BYTEWIDTH] & (1 << ((c) % BYTEWIDTH))) 627 628 /* Return the address of end of RANGE_TABLE. COUNT is number of 629 ranges (which is a pair of (start, end)) in the RANGE_TABLE. `* 2' 630 is start of range and end of range. `* 3' is size of each start 631 and end. */ 632 #define CHARSET_RANGE_TABLE_END(range_table, count) \ 633 ((range_table) + (count) * 2 * 3) 634 635 /* Test if C is in RANGE_TABLE. A flag NOT is negated if C is in. 636 COUNT is number of ranges in RANGE_TABLE. */ 637 #define CHARSET_LOOKUP_RANGE_TABLE_RAW(not, c, range_table, count) \ 638 do \ 639 { \ 640 int range_start, range_end; \ 641 unsigned char *p; \ 642 unsigned char *range_table_end \ 643 = CHARSET_RANGE_TABLE_END ((range_table), (count)); \ 644 \ 645 for (p = (range_table); p < range_table_end; p += 2 * 3) \ 646 { \ 647 EXTRACT_CHARACTER (range_start, p); \ 648 EXTRACT_CHARACTER (range_end, p + 3); \ 649 \ 650 if (range_start <= (c) && (c) <= range_end) \ 651 { \ 652 (not) = !(not); \ 653 break; \ 654 } \ 655 } \ 656 } \ 657 while (0) 658 659 /* Test if C is in range table of CHARSET. The flag NOT is negated if 660 C is listed in it. */ 661 #define CHARSET_LOOKUP_RANGE_TABLE(not, c, charset) \ 662 do \ 663 { \ 664 /* Number of ranges in range table. */ \ 665 int count; \ 666 unsigned char *range_table = CHARSET_RANGE_TABLE (charset); \ 667 \ 668 EXTRACT_NUMBER_AND_INCR (count, range_table); \ 669 CHARSET_LOOKUP_RANGE_TABLE_RAW ((not), (c), range_table, count); \ 670 } \ 671 while (0) 672 673 /* If DEBUG is defined, Regex prints many voluminous messages about what 674 it is doing (if the variable `debug' is nonzero). If linked with the 675 main program in `iregex.c', you can enter patterns and strings 676 interactively. And if linked with the main program in `main.c' and 677 the other test files, you can run the already-written tests. */ 678 679 #ifdef DEBUG 680 681 /* We use standard I/O for debugging. */ 682 #include <stdio.h> 683 684 /* It is useful to test things that ``must'' be true when debugging. */ 685 #include <assert.h> 686 687 static int debug = 0; 688 689 #define DEBUG_STATEMENT(e) e 690 #define DEBUG_PRINT1(x) if (debug) printf (x) 691 #define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2) 692 #define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3) 693 #define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4) 694 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \ 695 if (debug) print_partial_compiled_pattern (s, e) 696 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \ 697 if (debug) print_double_string (w, s1, sz1, s2, sz2) 698 699 700 /* Print the fastmap in human-readable form. */ 701 702 void 703 print_fastmap (fastmap) 704 char *fastmap; 705 { 706 unsigned was_a_range = 0; 707 unsigned i = 0; 708 709 while (i < (1 << BYTEWIDTH)) 710 { 711 if (fastmap[i++]) 712 { 713 was_a_range = 0; 714 putchar (i - 1); 715 while (i < (1 << BYTEWIDTH) && fastmap[i]) 716 { 717 was_a_range = 1; 718 i++; 719 } 720 if (was_a_range) 721 { 722 printf ("-"); 723 putchar (i - 1); 724 } 725 } 726 } 727 putchar ('\n'); 728 } 729 730 731 /* Print a compiled pattern string in human-readable form, starting at 732 the START pointer into it and ending just before the pointer END. */ 733 734 void 735 print_partial_compiled_pattern (start, end) 736 unsigned char *start; 737 unsigned char *end; 738 { 739 int mcnt, mcnt2; 740 unsigned char *p = start; 741 unsigned char *pend = end; 742 743 if (start == NULL) 744 { 745 printf ("(null)\n"); 746 return; 747 } 748 749 /* Loop over pattern commands. */ 750 while (p < pend) 751 { 752 printf ("%d:\t", p - start); 753 754 switch ((re_opcode_t) *p++) 755 { 756 case no_op: 757 printf ("/no_op"); 758 break; 759 760 case exactn: 761 mcnt = *p++; 762 printf ("/exactn/%d", mcnt); 763 do 764 { 765 putchar ('/'); 766 putchar (*p++); 767 } 768 while (--mcnt); 769 break; 770 771 case start_memory: 772 mcnt = *p++; 773 printf ("/start_memory/%d/%d", mcnt, *p++); 774 break; 775 776 case stop_memory: 777 mcnt = *p++; 778 printf ("/stop_memory/%d/%d", mcnt, *p++); 779 break; 780 781 case duplicate: 782 printf ("/duplicate/%d", *p++); 783 break; 784 785 case anychar: 786 printf ("/anychar"); 787 break; 788 789 case charset: 790 case charset_not: 791 { 792 register int c, last = -100; 793 register int in_range = 0; 794 795 printf ("/charset [%s", 796 (re_opcode_t) *(p - 1) == charset_not ? "^" : ""); 797 798 assert (p + *p < pend); 799 800 for (c = 0; c < 256; c++) 801 if (c / 8 < *p 802 && (p[1 + (c/8)] & (1 << (c % 8)))) 803 { 804 /* Are we starting a range? */ 805 if (last + 1 == c && ! in_range) 806 { 807 putchar ('-'); 808 in_range = 1; 809 } 810 /* Have we broken a range? */ 811 else if (last + 1 != c && in_range) 812 { 813 putchar (last); 814 in_range = 0; 815 } 816 817 if (! in_range) 818 putchar (c); 819 820 last = c; 821 } 822 823 if (in_range) 824 putchar (last); 825 826 putchar (']'); 827 828 p += 1 + *p; 829 } 830 break; 831 832 case begline: 833 printf ("/begline"); 834 break; 835 836 case endline: 837 printf ("/endline"); 838 break; 839 840 case on_failure_jump: 841 extract_number_and_incr (&mcnt, &p); 842 printf ("/on_failure_jump to %d", p + mcnt - start); 843 break; 844 845 case on_failure_keep_string_jump: 846 extract_number_and_incr (&mcnt, &p); 847 printf ("/on_failure_keep_string_jump to %d", p + mcnt - start); 848 break; 849 850 case dummy_failure_jump: 851 extract_number_and_incr (&mcnt, &p); 852 printf ("/dummy_failure_jump to %d", p + mcnt - start); 853 break; 854 855 case push_dummy_failure: 856 printf ("/push_dummy_failure"); 857 break; 858 859 case maybe_pop_jump: 860 extract_number_and_incr (&mcnt, &p); 861 printf ("/maybe_pop_jump to %d", p + mcnt - start); 862 break; 863 864 case pop_failure_jump: 865 extract_number_and_incr (&mcnt, &p); 866 printf ("/pop_failure_jump to %d", p + mcnt - start); 867 break; 868 869 case jump_past_alt: 870 extract_number_and_incr (&mcnt, &p); 871 printf ("/jump_past_alt to %d", p + mcnt - start); 872 break; 873 874 case jump: 875 extract_number_and_incr (&mcnt, &p); 876 printf ("/jump to %d", p + mcnt - start); 877 break; 878 879 case succeed_n: 880 extract_number_and_incr (&mcnt, &p); 881 extract_number_and_incr (&mcnt2, &p); 882 printf ("/succeed_n to %d, %d times", p + mcnt - start, mcnt2); 883 break; 884 885 case jump_n: 886 extract_number_and_incr (&mcnt, &p); 887 extract_number_and_incr (&mcnt2, &p); 888 printf ("/jump_n to %d, %d times", p + mcnt - start, mcnt2); 889 break; 890 891 case set_number_at: 892 extract_number_and_incr (&mcnt, &p); 893 extract_number_and_incr (&mcnt2, &p); 894 printf ("/set_number_at location %d to %d", p + mcnt - start, mcnt2); 895 break; 896 897 case wordbound: 898 printf ("/wordbound"); 899 break; 900 901 case notwordbound: 902 printf ("/notwordbound"); 903 break; 904 905 case wordbeg: 906 printf ("/wordbeg"); 907 break; 908 909 case wordend: 910 printf ("/wordend"); 911 912 #ifdef emacs 913 case before_dot: 914 printf ("/before_dot"); 915 break; 916 917 case at_dot: 918 printf ("/at_dot"); 919 break; 920 921 case after_dot: 922 printf ("/after_dot"); 923 break; 924 925 case syntaxspec: 926 printf ("/syntaxspec"); 927 mcnt = *p++; 928 printf ("/%d", mcnt); 929 break; 930 931 case notsyntaxspec: 932 printf ("/notsyntaxspec"); 933 mcnt = *p++; 934 printf ("/%d", mcnt); 935 break; 936 #endif /* emacs */ 937 938 case wordchar: 939 printf ("/wordchar"); 940 break; 941 942 case notwordchar: 943 printf ("/notwordchar"); 944 break; 945 946 case begbuf: 947 printf ("/begbuf"); 948 break; 949 950 case endbuf: 951 printf ("/endbuf"); 952 break; 953 954 default: 955 printf ("?%d", *(p-1)); 956 } 957 958 putchar ('\n'); 959 } 960 961 printf ("%d:\tend of pattern.\n", p - start); 962 } 963 964 965 void 966 print_compiled_pattern (bufp) 967 struct re_pattern_buffer *bufp; 968 { 969 unsigned char *buffer = bufp->buffer; 970 971 print_partial_compiled_pattern (buffer, buffer + bufp->used); 972 printf ("%d bytes used/%d bytes allocated.\n", bufp->used, bufp->allocated); 973 974 if (bufp->fastmap_accurate && bufp->fastmap) 975 { 976 printf ("fastmap: "); 977 print_fastmap (bufp->fastmap); 978 } 979 980 printf ("re_nsub: %d\t", bufp->re_nsub); 981 printf ("regs_alloc: %d\t", bufp->regs_allocated); 982 printf ("can_be_null: %d\t", bufp->can_be_null); 983 printf ("newline_anchor: %d\n", bufp->newline_anchor); 984 printf ("no_sub: %d\t", bufp->no_sub); 985 printf ("not_bol: %d\t", bufp->not_bol); 986 printf ("not_eol: %d\t", bufp->not_eol); 987 printf ("syntax: %d\n", bufp->syntax); 988 /* Perhaps we should print the translate table? */ 989 } 990 991 992 void 993 print_double_string (where, string1, size1, string2, size2) 994 const char *where; 995 const char *string1; 996 const char *string2; 997 int size1; 998 int size2; 999 { 1000 unsigned this_char; 1001 1002 if (where == NULL) 1003 printf ("(null)"); 1004 else 1005 { 1006 if (FIRST_STRING_P (where)) 1007 { 1008 for (this_char = where - string1; this_char < size1; this_char++) 1009 putchar (string1[this_char]); 1010 1011 where = string2; 1012 } 1013 1014 for (this_char = where - string2; this_char < size2; this_char++) 1015 putchar (string2[this_char]); 1016 } 1017 } 1018 1019 #else /* not DEBUG */ 1020 1021 #undef assert 1022 #define assert(e) 1023 1024 #define DEBUG_STATEMENT(e) 1025 #define DEBUG_PRINT1(x) 1026 #define DEBUG_PRINT2(x1, x2) 1027 #define DEBUG_PRINT3(x1, x2, x3) 1028 #define DEBUG_PRINT4(x1, x2, x3, x4) 1029 #define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) 1030 #define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) 1031 1032 #endif /* not DEBUG */ 1033 1034 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can 1035 also be assigned to arbitrarily: each pattern buffer stores its own 1036 syntax, so it can be changed between regex compilations. */ 1037 /* This has no initializer because initialized variables in Emacs 1038 become read-only after dumping. */ 1039 reg_syntax_t re_syntax_options; 1040 1041 1042 /* Specify the precise syntax of regexps for compilation. This provides 1043 for compatibility for various utilities which historically have 1044 different, incompatible syntaxes. 1045 1046 The argument SYNTAX is a bit mask comprised of the various bits 1047 defined in regex.h. We return the old syntax. */ 1048 1049 reg_syntax_t 1050 re_set_syntax (syntax) 1051 reg_syntax_t syntax; 1052 { 1053 reg_syntax_t ret = re_syntax_options; 1054 1055 re_syntax_options = syntax; 1056 return ret; 1057 } 1058 1059 /* This table gives an error message for each of the error codes listed 1060 in regex.h. Obviously the order here has to be same as there. 1061 POSIX doesn't require that we do anything for REG_NOERROR, 1062 but why not be nice? */ 1063 1064 static const char *re_error_msgid[] = 1065 { 1066 gettext_noop ("Success"), /* REG_NOERROR */ 1067 gettext_noop ("No match"), /* REG_NOMATCH */ 1068 gettext_noop ("Invalid regular expression"), /* REG_BADPAT */ 1069 gettext_noop ("Invalid collation character"), /* REG_ECOLLATE */ 1070 gettext_noop ("Invalid character class name"), /* REG_ECTYPE */ 1071 gettext_noop ("Trailing backslash"), /* REG_EESCAPE */ 1072 gettext_noop ("Invalid back reference"), /* REG_ESUBREG */ 1073 gettext_noop ("Unmatched [ or [^"), /* REG_EBRACK */ 1074 gettext_noop ("Unmatched ( or \\("), /* REG_EPAREN */ 1075 gettext_noop ("Unmatched \\{"), /* REG_EBRACE */ 1076 gettext_noop ("Invalid content of \\{\\}"), /* REG_BADBR */ 1077 gettext_noop ("Invalid range end"), /* REG_ERANGE */ 1078 gettext_noop ("Memory exhausted"), /* REG_ESPACE */ 1079 gettext_noop ("Invalid preceding regular expression"), /* REG_BADRPT */ 1080 gettext_noop ("Premature end of regular expression"), /* REG_EEND */ 1081 gettext_noop ("Regular expression too big"), /* REG_ESIZE */ 1082 gettext_noop ("Unmatched ) or \\)"), /* REG_ERPAREN */ 1083 }; 1084 1085 /* Avoiding alloca during matching, to placate r_alloc. */ 1086 1087 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the 1088 searching and matching functions should not call alloca. On some 1089 systems, alloca is implemented in terms of malloc, and if we're 1090 using the relocating allocator routines, then malloc could cause a 1091 relocation, which might (if the strings being searched are in the 1092 ralloc heap) shift the data out from underneath the regexp 1093 routines. 1094 1095 Here's another reason to avoid allocation: Emacs 1096 processes input from X in a signal handler; processing X input may 1097 call malloc; if input arrives while a matching routine is calling 1098 malloc, then we're scrod. But Emacs can't just block input while 1099 calling matching routines; then we don't notice interrupts when 1100 they come in. So, Emacs blocks input around all regexp calls 1101 except the matching calls, which it leaves unprotected, in the 1102 faith that they will not malloc. */ 1103 1104 /* Normally, this is fine. */ 1105 #define MATCH_MAY_ALLOCATE 1106 1107 /* When using GNU C, we are not REALLY using the C alloca, no matter 1108 what config.h may say. So don't take precautions for it. */ 1109 #ifdef __GNUC__ 1110 #undef C_ALLOCA 1111 #endif 1112 1113 /* The match routines may not allocate if (1) they would do it with malloc 1114 and (2) it's not safe for them to use malloc. 1115 Note that if REL_ALLOC is defined, matching would not use malloc for the 1116 failure stack, but we would still use it for the register vectors; 1117 so REL_ALLOC should not affect this. */ 1118 #if (defined (C_ALLOCA) || defined (REGEX_MALLOC)) && defined (emacs) 1119 #undef MATCH_MAY_ALLOCATE 1120 #endif 1121 1122 1123 /* Failure stack declarations and macros; both re_compile_fastmap and 1124 re_match_2 use a failure stack. These have to be macros because of 1125 REGEX_ALLOCATE_STACK. */ 1126 1127 1128 /* Approximate number of failure points for which to initially allocate space 1129 when matching. If this number is exceeded, we allocate more 1130 space, so it is not a hard limit. */ 1131 #ifndef INIT_FAILURE_ALLOC 1132 #define INIT_FAILURE_ALLOC 20 1133 #endif 1134 1135 /* Roughly the maximum number of failure points on the stack. Would be 1136 exactly that if always used TYPICAL_FAILURE_SIZE items each time we failed. 1137 This is a variable only so users of regex can assign to it; we never 1138 change it ourselves. */ 1139 #if defined (MATCH_MAY_ALLOCATE) 1140 /* Note that 4400 is enough to cause a crash on Alpha OSF/1, 1141 whose default stack limit is 2mb. In order for a larger 1142 value to work reliably, you have to try to make it accord 1143 with the process stack limit. */ 1144 int re_max_failures = 40000; 1145 #else 1146 int re_max_failures = 4000; 1147 #endif 1148 1149 union fail_stack_elt 1150 { 1151 unsigned char *pointer; 1152 int integer; 1153 }; 1154 1155 typedef union fail_stack_elt fail_stack_elt_t; 1156 1157 typedef struct 1158 { 1159 fail_stack_elt_t *stack; 1160 unsigned size; 1161 unsigned avail; /* Offset of next open position. */ 1162 } fail_stack_type; 1163 1164 #define FAIL_STACK_EMPTY() (fail_stack.avail == 0) 1165 #define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0) 1166 #define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size) 1167 1168 1169 /* Define macros to initialize and free the failure stack. 1170 Do `return -2' if the alloc fails. */ 1171 1172 #ifdef MATCH_MAY_ALLOCATE 1173 #define INIT_FAIL_STACK() \ 1174 do { \ 1175 fail_stack.stack = (fail_stack_elt_t *) \ 1176 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * TYPICAL_FAILURE_SIZE \ 1177 * sizeof (fail_stack_elt_t)); \ 1178 \ 1179 if (fail_stack.stack == NULL) \ 1180 return -2; \ 1181 \ 1182 fail_stack.size = INIT_FAILURE_ALLOC; \ 1183 fail_stack.avail = 0; \ 1184 } while (0) 1185 1186 #define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack) 1187 #else 1188 #define INIT_FAIL_STACK() \ 1189 do { \ 1190 fail_stack.avail = 0; \ 1191 } while (0) 1192 1193 #define RESET_FAIL_STACK() 1194 #endif 1195 1196 1197 /* Double the size of FAIL_STACK, up to a limit 1198 which allows approximately `re_max_failures' items. 1199 1200 Return 1 if succeeds, and 0 if either ran out of memory 1201 allocating space for it or it was already too large. 1202 1203 REGEX_REALLOCATE_STACK requires `destination' be declared. */ 1204 1205 /* Factor to increase the failure stack size by 1206 when we increase it. 1207 This used to be 2, but 2 was too wasteful 1208 because the old discarded stacks added up to as much space 1209 were as ultimate, maximum-size stack. */ 1210 #define FAIL_STACK_GROWTH_FACTOR 4 1211 1212 #define GROW_FAIL_STACK(fail_stack) \ 1213 (((fail_stack).size * sizeof (fail_stack_elt_t) \ 1214 >= re_max_failures * TYPICAL_FAILURE_SIZE) \ 1215 ? 0 \ 1216 : ((fail_stack).stack \ 1217 = (fail_stack_elt_t *) \ 1218 REGEX_REALLOCATE_STACK ((fail_stack).stack, \ 1219 (fail_stack).size * sizeof (fail_stack_elt_t), \ 1220 MIN (re_max_failures * TYPICAL_FAILURE_SIZE, \ 1221 ((fail_stack).size * sizeof (fail_stack_elt_t) \ 1222 * FAIL_STACK_GROWTH_FACTOR))), \ 1223 \ 1224 (fail_stack).stack == NULL \ 1225 ? 0 \ 1226 : ((fail_stack).size \ 1227 = (MIN (re_max_failures * TYPICAL_FAILURE_SIZE, \ 1228 ((fail_stack).size * sizeof (fail_stack_elt_t) \ 1229 * FAIL_STACK_GROWTH_FACTOR)) \ 1230 / sizeof (fail_stack_elt_t)), \ 1231 1))) 1232 1233 1234 /* Push pointer POINTER on FAIL_STACK. 1235 Return 1 if was able to do so and 0 if ran out of memory allocating 1236 space to do so. */ 1237 #define PUSH_PATTERN_OP(POINTER, FAIL_STACK) \ 1238 ((FAIL_STACK_FULL () \ 1239 && !GROW_FAIL_STACK (FAIL_STACK)) \ 1240 ? 0 \ 1241 : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER, \ 1242 1)) 1243 1244 /* Push a pointer value onto the failure stack. 1245 Assumes the variable `fail_stack'. Probably should only 1246 be called from within `PUSH_FAILURE_POINT'. */ 1247 #define PUSH_FAILURE_POINTER(item) \ 1248 fail_stack.stack[fail_stack.avail++].pointer = (unsigned char *) (item) 1249 1250 /* This pushes an integer-valued item onto the failure stack. 1251 Assumes the variable `fail_stack'. Probably should only 1252 be called from within `PUSH_FAILURE_POINT'. */ 1253 #define PUSH_FAILURE_INT(item) \ 1254 fail_stack.stack[fail_stack.avail++].integer = (item) 1255 1256 /* Push a fail_stack_elt_t value onto the failure stack. 1257 Assumes the variable `fail_stack'. Probably should only 1258 be called from within `PUSH_FAILURE_POINT'. */ 1259 #define PUSH_FAILURE_ELT(item) \ 1260 fail_stack.stack[fail_stack.avail++] = (item) 1261 1262 /* These three POP... operations complement the three PUSH... operations. 1263 All assume that `fail_stack' is nonempty. */ 1264 #define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer 1265 #define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer 1266 #define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail] 1267 1268 /* Used to omit pushing failure point id's when we're not debugging. */ 1269 #ifdef DEBUG 1270 #define DEBUG_PUSH PUSH_FAILURE_INT 1271 #define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT () 1272 #else 1273 #define DEBUG_PUSH(item) 1274 #define DEBUG_POP(item_addr) 1275 #endif 1276 1277 1278 /* Push the information about the state we will need 1279 if we ever fail back to it. 1280 1281 Requires variables fail_stack, regstart, regend, reg_info, and 1282 num_regs be declared. GROW_FAIL_STACK requires `destination' be 1283 declared. 1284 1285 Does `return FAILURE_CODE' if runs out of memory. */ 1286 1287 #define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \ 1288 do { \ 1289 char *destination; \ 1290 /* Must be int, so when we don't save any registers, the arithmetic \ 1291 of 0 + -1 isn't done as unsigned. */ \ 1292 int this_reg; \ 1293 \ 1294 DEBUG_STATEMENT (failure_id++); \ 1295 DEBUG_STATEMENT (nfailure_points_pushed++); \ 1296 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \ 1297 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\ 1298 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\ 1299 \ 1300 DEBUG_PRINT2 (" slots needed: %d\n", NUM_FAILURE_ITEMS); \ 1301 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \ 1302 \ 1303 /* Ensure we have enough space allocated for what we will push. */ \ 1304 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \ 1305 { \ 1306 if (!GROW_FAIL_STACK (fail_stack)) \ 1307 return failure_code; \ 1308 \ 1309 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \ 1310 (fail_stack).size); \ 1311 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\ 1312 } \ 1313 \ 1314 /* Push the info, starting with the registers. */ \ 1315 DEBUG_PRINT1 ("\n"); \ 1316 \ 1317 if (1) \ 1318 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \ 1319 this_reg++) \ 1320 { \ 1321 DEBUG_PRINT2 (" Pushing reg: %d\n", this_reg); \ 1322 DEBUG_STATEMENT (num_regs_pushed++); \ 1323 \ 1324 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \ 1325 PUSH_FAILURE_POINTER (regstart[this_reg]); \ 1326 \ 1327 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \ 1328 PUSH_FAILURE_POINTER (regend[this_reg]); \ 1329 \ 1330 DEBUG_PRINT2 (" info: 0x%x\n ", reg_info[this_reg]); \ 1331 DEBUG_PRINT2 (" match_null=%d", \ 1332 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \ 1333 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \ 1334 DEBUG_PRINT2 (" matched_something=%d", \ 1335 MATCHED_SOMETHING (reg_info[this_reg])); \ 1336 DEBUG_PRINT2 (" ever_matched=%d", \ 1337 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \ 1338 DEBUG_PRINT1 ("\n"); \ 1339 PUSH_FAILURE_ELT (reg_info[this_reg].word); \ 1340 } \ 1341 \ 1342 DEBUG_PRINT2 (" Pushing low active reg: %d\n", lowest_active_reg);\ 1343 PUSH_FAILURE_INT (lowest_active_reg); \ 1344 \ 1345 DEBUG_PRINT2 (" Pushing high active reg: %d\n", highest_active_reg);\ 1346 PUSH_FAILURE_INT (highest_active_reg); \ 1347 \ 1348 DEBUG_PRINT2 (" Pushing pattern 0x%x: ", pattern_place); \ 1349 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \ 1350 PUSH_FAILURE_POINTER (pattern_place); \ 1351 \ 1352 DEBUG_PRINT2 (" Pushing string 0x%x: `", string_place); \ 1353 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \ 1354 size2); \ 1355 DEBUG_PRINT1 ("'\n"); \ 1356 PUSH_FAILURE_POINTER (string_place); \ 1357 \ 1358 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \ 1359 DEBUG_PUSH (failure_id); \ 1360 } while (0) 1361 1362 /* This is the number of items that are pushed and popped on the stack 1363 for each register. */ 1364 #define NUM_REG_ITEMS 3 1365 1366 /* Individual items aside from the registers. */ 1367 #ifdef DEBUG 1368 #define NUM_NONREG_ITEMS 5 /* Includes failure point id. */ 1369 #else 1370 #define NUM_NONREG_ITEMS 4 1371 #endif 1372 1373 /* Estimate the size of data pushed by a typical failure stack entry. 1374 An estimate is all we need, because all we use this for 1375 is to choose a limit for how big to make the failure stack. */ 1376 1377 #define TYPICAL_FAILURE_SIZE 20 1378 1379 /* This is how many items we actually use for a failure point. 1380 It depends on the regexp. */ 1381 #define NUM_FAILURE_ITEMS \ 1382 (((0 \ 1383 ? 0 : highest_active_reg - lowest_active_reg + 1) \ 1384 * NUM_REG_ITEMS) \ 1385 + NUM_NONREG_ITEMS) 1386 1387 /* How many items can still be added to the stack without overflowing it. */ 1388 #define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail) 1389 1390 1391 /* Pops what PUSH_FAIL_STACK pushes. 1392 1393 We restore into the parameters, all of which should be lvalues: 1394 STR -- the saved data position. 1395 PAT -- the saved pattern position. 1396 LOW_REG, HIGH_REG -- the highest and lowest active registers. 1397 REGSTART, REGEND -- arrays of string positions. 1398 REG_INFO -- array of information about each subexpression. 1399 1400 Also assumes the variables `fail_stack' and (if debugging), `bufp', 1401 `pend', `string1', `size1', `string2', and `size2'. */ 1402 1403 #define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\ 1404 { \ 1405 DEBUG_STATEMENT (fail_stack_elt_t failure_id;) \ 1406 int this_reg; \ 1407 const unsigned char *string_temp; \ 1408 \ 1409 assert (!FAIL_STACK_EMPTY ()); \ 1410 \ 1411 /* Remove failure points and point to how many regs pushed. */ \ 1412 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \ 1413 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \ 1414 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \ 1415 \ 1416 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \ 1417 \ 1418 DEBUG_POP (&failure_id); \ 1419 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \ 1420 \ 1421 /* If the saved string location is NULL, it came from an \ 1422 on_failure_keep_string_jump opcode, and we want to throw away the \ 1423 saved NULL, thus retaining our current position in the string. */ \ 1424 string_temp = POP_FAILURE_POINTER (); \ 1425 if (string_temp != NULL) \ 1426 str = (const char *) string_temp; \ 1427 \ 1428 DEBUG_PRINT2 (" Popping string 0x%x: `", str); \ 1429 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \ 1430 DEBUG_PRINT1 ("'\n"); \ 1431 \ 1432 pat = (unsigned char *) POP_FAILURE_POINTER (); \ 1433 DEBUG_PRINT2 (" Popping pattern 0x%x: ", pat); \ 1434 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \ 1435 \ 1436 /* Restore register info. */ \ 1437 high_reg = (unsigned) POP_FAILURE_INT (); \ 1438 DEBUG_PRINT2 (" Popping high active reg: %d\n", high_reg); \ 1439 \ 1440 low_reg = (unsigned) POP_FAILURE_INT (); \ 1441 DEBUG_PRINT2 (" Popping low active reg: %d\n", low_reg); \ 1442 \ 1443 if (1) \ 1444 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \ 1445 { \ 1446 DEBUG_PRINT2 (" Popping reg: %d\n", this_reg); \ 1447 \ 1448 reg_info[this_reg].word = POP_FAILURE_ELT (); \ 1449 DEBUG_PRINT2 (" info: 0x%x\n", reg_info[this_reg]); \ 1450 \ 1451 regend[this_reg] = (const char *) POP_FAILURE_POINTER (); \ 1452 DEBUG_PRINT2 (" end: 0x%x\n", regend[this_reg]); \ 1453 \ 1454 regstart[this_reg] = (const char *) POP_FAILURE_POINTER (); \ 1455 DEBUG_PRINT2 (" start: 0x%x\n", regstart[this_reg]); \ 1456 } \ 1457 else \ 1458 { \ 1459 for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \ 1460 { \ 1461 reg_info[this_reg].word.integer = 0; \ 1462 regend[this_reg] = 0; \ 1463 regstart[this_reg] = 0; \ 1464 } \ 1465 highest_active_reg = high_reg; \ 1466 } \ 1467 \ 1468 set_regs_matched_done = 0; \ 1469 DEBUG_STATEMENT (nfailure_points_popped++); \ 1470 } /* POP_FAILURE_POINT */ 1471 1472 1473 1474 /* Structure for per-register (a.k.a. per-group) information. 1475 Other register information, such as the 1476 starting and ending positions (which are addresses), and the list of 1477 inner groups (which is a bits list) are maintained in separate 1478 variables. 1479 1480 We are making a (strictly speaking) nonportable assumption here: that 1481 the compiler will pack our bit fields into something that fits into 1482 the type of `word', i.e., is something that fits into one item on the 1483 failure stack. */ 1484 1485 typedef union 1486 { 1487 fail_stack_elt_t word; 1488 struct 1489 { 1490 /* This field is one if this group can match the empty string, 1491 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */ 1492 #define MATCH_NULL_UNSET_VALUE 3 1493 unsigned match_null_string_p : 2; 1494 unsigned is_active : 1; 1495 unsigned matched_something : 1; 1496 unsigned ever_matched_something : 1; 1497 } bits; 1498 } register_info_type; 1499 1500 #define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p) 1501 #define IS_ACTIVE(R) ((R).bits.is_active) 1502 #define MATCHED_SOMETHING(R) ((R).bits.matched_something) 1503 #define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something) 1504 1505 1506 /* Call this when have matched a real character; it sets `matched' flags 1507 for the subexpressions which we are currently inside. Also records 1508 that those subexprs have matched. */ 1509 #define SET_REGS_MATCHED() \ 1510 do \ 1511 { \ 1512 if (!set_regs_matched_done) \ 1513 { \ 1514 unsigned r; \ 1515 set_regs_matched_done = 1; \ 1516 for (r = lowest_active_reg; r <= highest_active_reg; r++) \ 1517 { \ 1518 MATCHED_SOMETHING (reg_info[r]) \ 1519 = EVER_MATCHED_SOMETHING (reg_info[r]) \ 1520 = 1; \ 1521 } \ 1522 } \ 1523 } \ 1524 while (0) 1525 1526 /* Registers are set to a sentinel when they haven't yet matched. */ 1527 static char reg_unset_dummy; 1528 #define REG_UNSET_VALUE (®_unset_dummy) 1529 #define REG_UNSET(e) ((e) == REG_UNSET_VALUE) 1530 1531 /* Subroutine declarations and macros for regex_compile. */ 1532 1533 static void store_op1 (), store_op2 (); 1534 static void insert_op1 (), insert_op2 (); 1535 static boolean at_begline_loc_p (), at_endline_loc_p (); 1536 static boolean group_in_compile_stack (); 1537 static reg_errcode_t compile_range (); 1538 1539 /* Fetch the next character in the uncompiled pattern---translating it 1540 if necessary. Also cast from a signed character in the constant 1541 string passed to us by the user to an unsigned char that we can use 1542 as an array index (in, e.g., `translate'). */ 1543 #ifndef PATFETCH 1544 #define PATFETCH(c) \ 1545 do {if (p == pend) return REG_EEND; \ 1546 c = (unsigned char) *p++; \ 1547 if (RE_TRANSLATE_P (translate)) c = RE_TRANSLATE (translate, c); \ 1548 } while (0) 1549 #endif 1550 1551 /* Fetch the next character in the uncompiled pattern, with no 1552 translation. */ 1553 #define PATFETCH_RAW(c) \ 1554 do {if (p == pend) return REG_EEND; \ 1555 c = (unsigned char) *p++; \ 1556 } while (0) 1557 1558 /* Go backwards one character in the pattern. */ 1559 #define PATUNFETCH p-- 1560 1561 1562 /* If `translate' is non-null, return translate[D], else just D. We 1563 cast the subscript to translate because some data is declared as 1564 `char *', to avoid warnings when a string constant is passed. But 1565 when we use a character as a subscript we must make it unsigned. */ 1566 #ifndef TRANSLATE 1567 #define TRANSLATE(d) \ 1568 (RE_TRANSLATE_P (translate) \ 1569 ? (unsigned) RE_TRANSLATE (translate, (unsigned) (d)) : (d)) 1570 #endif 1571 1572 1573 /* Macros for outputting the compiled pattern into `buffer'. */ 1574 1575 /* If the buffer isn't allocated when it comes in, use this. */ 1576 #define INIT_BUF_SIZE 32 1577 1578 /* Make sure we have at least N more bytes of space in buffer. */ 1579 #define GET_BUFFER_SPACE(n) \ 1580 while (b - bufp->buffer + (n) > bufp->allocated) \ 1581 EXTEND_BUFFER () 1582 1583 /* Make sure we have one more byte of buffer space and then add C to it. */ 1584 #define BUF_PUSH(c) \ 1585 do { \ 1586 GET_BUFFER_SPACE (1); \ 1587 *b++ = (unsigned char) (c); \ 1588 } while (0) 1589 1590 1591 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */ 1592 #define BUF_PUSH_2(c1, c2) \ 1593 do { \ 1594 GET_BUFFER_SPACE (2); \ 1595 *b++ = (unsigned char) (c1); \ 1596 *b++ = (unsigned char) (c2); \ 1597 } while (0) 1598 1599 1600 /* As with BUF_PUSH_2, except for three bytes. */ 1601 #define BUF_PUSH_3(c1, c2, c3) \ 1602 do { \ 1603 GET_BUFFER_SPACE (3); \ 1604 *b++ = (unsigned char) (c1); \ 1605 *b++ = (unsigned char) (c2); \ 1606 *b++ = (unsigned char) (c3); \ 1607 } while (0) 1608 1609 1610 /* Store a jump with opcode OP at LOC to location TO. We store a 1611 relative address offset by the three bytes the jump itself occupies. */ 1612 #define STORE_JUMP(op, loc, to) \ 1613 store_op1 (op, loc, (to) - (loc) - 3) 1614 1615 /* Likewise, for a two-argument jump. */ 1616 #define STORE_JUMP2(op, loc, to, arg) \ 1617 store_op2 (op, loc, (to) - (loc) - 3, arg) 1618 1619 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */ 1620 #define INSERT_JUMP(op, loc, to) \ 1621 insert_op1 (op, loc, (to) - (loc) - 3, b) 1622 1623 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */ 1624 #define INSERT_JUMP2(op, loc, to, arg) \ 1625 insert_op2 (op, loc, (to) - (loc) - 3, arg, b) 1626 1627 1628 /* This is not an arbitrary limit: the arguments which represent offsets 1629 into the pattern are two bytes long. So if 2^16 bytes turns out to 1630 be too small, many things would have to change. */ 1631 #define MAX_BUF_SIZE (1L << 16) 1632 1633 1634 /* Extend the buffer by twice its current size via realloc and 1635 reset the pointers that pointed into the old block to point to the 1636 correct places in the new one. If extending the buffer results in it 1637 being larger than MAX_BUF_SIZE, then flag memory exhausted. */ 1638 #define EXTEND_BUFFER() \ 1639 do { \ 1640 unsigned char *old_buffer = bufp->buffer; \ 1641 if (bufp->allocated == MAX_BUF_SIZE) \ 1642 return REG_ESIZE; \ 1643 bufp->allocated <<= 1; \ 1644 if (bufp->allocated > MAX_BUF_SIZE) \ 1645 bufp->allocated = MAX_BUF_SIZE; \ 1646 bufp->buffer = (unsigned char *) realloc (bufp->buffer, bufp->allocated);\ 1647 if (bufp->buffer == NULL) \ 1648 return REG_ESPACE; \ 1649 /* If the buffer moved, move all the pointers into it. */ \ 1650 if (old_buffer != bufp->buffer) \ 1651 { \ 1652 b = (b - old_buffer) + bufp->buffer; \ 1653 begalt = (begalt - old_buffer) + bufp->buffer; \ 1654 if (fixup_alt_jump) \ 1655 fixup_alt_jump = (fixup_alt_jump - old_buffer) + bufp->buffer;\ 1656 if (laststart) \ 1657 laststart = (laststart - old_buffer) + bufp->buffer; \ 1658 if (pending_exact) \ 1659 pending_exact = (pending_exact - old_buffer) + bufp->buffer; \ 1660 } \ 1661 } while (0) 1662 1663 1664 /* Since we have one byte reserved for the register number argument to 1665 {start,stop}_memory, the maximum number of groups we can report 1666 things about is what fits in that byte. */ 1667 #define MAX_REGNUM 255 1668 1669 /* But patterns can have more than `MAX_REGNUM' registers. We just 1670 ignore the excess. */ 1671 typedef unsigned regnum_t; 1672 1673 1674 /* Macros for the compile stack. */ 1675 1676 /* Since offsets can go either forwards or backwards, this type needs to 1677 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */ 1678 typedef int pattern_offset_t; 1679 1680 typedef struct 1681 { 1682 pattern_offset_t begalt_offset; 1683 pattern_offset_t fixup_alt_jump; 1684 pattern_offset_t inner_group_offset; 1685 pattern_offset_t laststart_offset; 1686 regnum_t regnum; 1687 } compile_stack_elt_t; 1688 1689 1690 typedef struct 1691 { 1692 compile_stack_elt_t *stack; 1693 unsigned size; 1694 unsigned avail; /* Offset of next open position. */ 1695 } compile_stack_type; 1696 1697 1698 #define INIT_COMPILE_STACK_SIZE 32 1699 1700 #define COMPILE_STACK_EMPTY (compile_stack.avail == 0) 1701 #define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size) 1702 1703 /* The next available element. */ 1704 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail]) 1705 1706 1707 /* Structure to manage work area for range table. */ 1708 struct range_table_work_area 1709 { 1710 int *table; /* actual work area. */ 1711 int allocated; /* allocated size for work area in bytes. */ 1712 int used; /* actually used size in words. */ 1713 }; 1714 1715 /* Make sure that WORK_AREA can hold more N multibyte characters. */ 1716 #define EXTEND_RANGE_TABLE_WORK_AREA(work_area, n) \ 1717 do { \ 1718 if (((work_area).used + (n)) * sizeof (int) > (work_area).allocated) \ 1719 { \ 1720 (work_area).allocated += 16 * sizeof (int); \ 1721 if ((work_area).table) \ 1722 (work_area).table \ 1723 = (int *) realloc ((work_area).table, (work_area).allocated); \ 1724 else \ 1725 (work_area).table \ 1726 = (int *) malloc ((work_area).allocated); \ 1727 if ((work_area).table == 0) \ 1728 FREE_STACK_RETURN (REG_ESPACE); \ 1729 } \ 1730 } while (0) 1731 1732 /* Set a range (RANGE_START, RANGE_END) to WORK_AREA. */ 1733 #define SET_RANGE_TABLE_WORK_AREA(work_area, range_start, range_end) \ 1734 do { \ 1735 EXTEND_RANGE_TABLE_WORK_AREA ((work_area), 2); \ 1736 (work_area).table[(work_area).used++] = (range_start); \ 1737 (work_area).table[(work_area).used++] = (range_end); \ 1738 } while (0) 1739 1740 /* Free allocated memory for WORK_AREA. */ 1741 #define FREE_RANGE_TABLE_WORK_AREA(work_area) \ 1742 do { \ 1743 if ((work_area).table) \ 1744 free ((work_area).table); \ 1745 } while (0) 1746 1747 #define CLEAR_RANGE_TABLE_WORK_USED(work_area) ((work_area).used = 0) 1748 #define RANGE_TABLE_WORK_USED(work_area) ((work_area).used) 1749 #define RANGE_TABLE_WORK_ELT(work_area, i) ((work_area).table[i]) 1750 1751 1752 /* Set the bit for character C in a list. */ 1753 #define SET_LIST_BIT(c) \ 1754 (b[((unsigned char) (c)) / BYTEWIDTH] \ 1755 |= 1 << (((unsigned char) c) % BYTEWIDTH)) 1756 1757 1758 /* Get the next unsigned number in the uncompiled pattern. */ 1759 #define GET_UNSIGNED_NUMBER(num) \ 1760 { if (p != pend) \ 1761 { \ 1762 PATFETCH (c); \ 1763 while (ISDIGIT (c)) \ 1764 { \ 1765 if (num < 0) \ 1766 num = 0; \ 1767 num = num * 10 + c - '0'; \ 1768 if (p == pend) \ 1769 break; \ 1770 PATFETCH (c); \ 1771 } \ 1772 } \ 1773 } 1774 1775 #define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */ 1776 1777 #define IS_CHAR_CLASS(string) \ 1778 (STREQ (string, "alpha") || STREQ (string, "upper") \ 1779 || STREQ (string, "lower") || STREQ (string, "digit") \ 1780 || STREQ (string, "alnum") || STREQ (string, "xdigit") \ 1781 || STREQ (string, "space") || STREQ (string, "print") \ 1782 || STREQ (string, "punct") || STREQ (string, "graph") \ 1783 || STREQ (string, "cntrl") || STREQ (string, "blank")) 1784 1785 #ifndef MATCH_MAY_ALLOCATE 1786 1787 /* If we cannot allocate large objects within re_match_2_internal, 1788 we make the fail stack and register vectors global. 1789 The fail stack, we grow to the maximum size when a regexp 1790 is compiled. 1791 The register vectors, we adjust in size each time we 1792 compile a regexp, according to the number of registers it needs. */ 1793 1794 static fail_stack_type fail_stack; 1795 1796 /* Size with which the following vectors are currently allocated. 1797 That is so we can make them bigger as needed, 1798 but never make them smaller. */ 1799 static int regs_allocated_size; 1800 1801 static const char ** regstart, ** regend; 1802 static const char ** old_regstart, ** old_regend; 1803 static const char **best_regstart, **best_regend; 1804 static register_info_type *reg_info; 1805 static const char **reg_dummy; 1806 static register_info_type *reg_info_dummy; 1807 1808 /* Make the register vectors big enough for NUM_REGS registers, 1809 but don't make them smaller. */ 1810 1811 static 1812 regex_grow_registers (num_regs) 1813 int num_regs; 1814 { 1815 if (num_regs > regs_allocated_size) 1816 { 1817 RETALLOC_IF (regstart, num_regs, const char *); 1818 RETALLOC_IF (regend, num_regs, const char *); 1819 RETALLOC_IF (old_regstart, num_regs, const char *); 1820 RETALLOC_IF (old_regend, num_regs, const char *); 1821 RETALLOC_IF (best_regstart, num_regs, const char *); 1822 RETALLOC_IF (best_regend, num_regs, const char *); 1823 RETALLOC_IF (reg_info, num_regs, register_info_type); 1824 RETALLOC_IF (reg_dummy, num_regs, const char *); 1825 RETALLOC_IF (reg_info_dummy, num_regs, register_info_type); 1826 1827 regs_allocated_size = num_regs; 1828 } 1829 } 1830 1831 #endif /* not MATCH_MAY_ALLOCATE */ 1832 1833 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX. 1834 Returns one of error codes defined in `regex.h', or zero for success. 1835 1836 Assumes the `allocated' (and perhaps `buffer') and `translate' 1837 fields are set in BUFP on entry. 1838 1839 If it succeeds, results are put in BUFP (if it returns an error, the 1840 contents of BUFP are undefined): 1841 `buffer' is the compiled pattern; 1842 `syntax' is set to SYNTAX; 1843 `used' is set to the length of the compiled pattern; 1844 `fastmap_accurate' is zero; 1845 `re_nsub' is the number of subexpressions in PATTERN; 1846 `not_bol' and `not_eol' are zero; 1847 1848 The `fastmap' and `newline_anchor' fields are neither 1849 examined nor set. */ 1850 1851 /* Return, freeing storage we allocated. */ 1852 #define FREE_STACK_RETURN(value) \ 1853 do { \ 1854 FREE_RANGE_TABLE_WORK_AREA (range_table_work); \ 1855 free (compile_stack.stack); \ 1856 return value; \ 1857 } while (0) 1858 1859 static reg_errcode_t 1860 regex_compile (pattern, size, syntax, bufp) 1861 const char *pattern; 1862 int size; 1863 reg_syntax_t syntax; 1864 struct re_pattern_buffer *bufp; 1865 { 1866 /* We fetch characters from PATTERN here. Even though PATTERN is 1867 `char *' (i.e., signed), we declare these variables as unsigned, so 1868 they can be reliably used as array indices. */ 1869 register unsigned int c, c1; 1870 1871 /* A random temporary spot in PATTERN. */ 1872 const char *p1; 1873 1874 /* Points to the end of the buffer, where we should append. */ 1875 register unsigned char *b; 1876 1877 /* Keeps track of unclosed groups. */ 1878 compile_stack_type compile_stack; 1879 1880 /* Points to the current (ending) position in the pattern. */ 1881 #ifdef AIX 1882 /* `const' makes AIX compiler fail. */ 1883 char *p = pattern; 1884 #else 1885 const char *p = pattern; 1886 #endif 1887 const char *pend = pattern + size; 1888 1889 /* How to translate the characters in the pattern. */ 1890 RE_TRANSLATE_TYPE translate = bufp->translate; 1891 1892 /* Address of the count-byte of the most recently inserted `exactn' 1893 command. This makes it possible to tell if a new exact-match 1894 character can be added to that command or if the character requires 1895 a new `exactn' command. */ 1896 unsigned char *pending_exact = 0; 1897 1898 /* Address of start of the most recently finished expression. 1899 This tells, e.g., postfix * where to find the start of its 1900 operand. Reset at the beginning of groups and alternatives. */ 1901 unsigned char *laststart = 0; 1902 1903 /* Address of beginning of regexp, or inside of last group. */ 1904 unsigned char *begalt; 1905 1906 /* Place in the uncompiled pattern (i.e., the {) to 1907 which to go back if the interval is invalid. */ 1908 const char *beg_interval; 1909 1910 /* Address of the place where a forward jump should go to the end of 1911 the containing expression. Each alternative of an `or' -- except the 1912 last -- ends with a forward jump of this sort. */ 1913 unsigned char *fixup_alt_jump = 0; 1914 1915 /* Counts open-groups as they are encountered. Remembered for the 1916 matching close-group on the compile stack, so the same register 1917 number is put in the stop_memory as the start_memory. */ 1918 regnum_t regnum = 0; 1919 1920 /* Work area for range table of charset. */ 1921 struct range_table_work_area range_table_work; 1922 1923 #ifdef DEBUG 1924 DEBUG_PRINT1 ("\nCompiling pattern: "); 1925 if (debug) 1926 { 1927 unsigned debug_count; 1928 1929 for (debug_count = 0; debug_count < size; debug_count++) 1930 putchar (pattern[debug_count]); 1931 putchar ('\n'); 1932 } 1933 #endif /* DEBUG */ 1934 1935 /* Initialize the compile stack. */ 1936 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t); 1937 if (compile_stack.stack == NULL) 1938 return REG_ESPACE; 1939 1940 compile_stack.size = INIT_COMPILE_STACK_SIZE; 1941 compile_stack.avail = 0; 1942 1943 range_table_work.table = 0; 1944 range_table_work.allocated = 0; 1945 1946 /* Initialize the pattern buffer. */ 1947 bufp->syntax = syntax; 1948 bufp->fastmap_accurate = 0; 1949 bufp->not_bol = bufp->not_eol = 0; 1950 1951 /* Set `used' to zero, so that if we return an error, the pattern 1952 printer (for debugging) will think there's no pattern. We reset it 1953 at the end. */ 1954 bufp->used = 0; 1955 1956 /* Always count groups, whether or not bufp->no_sub is set. */ 1957 bufp->re_nsub = 0; 1958 1959 #ifdef emacs 1960 /* bufp->multibyte is set before regex_compile is called, so don't alter 1961 it. */ 1962 #else /* not emacs */ 1963 /* Nothing is recognized as a multibyte character. */ 1964 bufp->multibyte = 0; 1965 #endif 1966 1967 #if !defined (emacs) && !defined (SYNTAX_TABLE) 1968 /* Initialize the syntax table. */ 1969 init_syntax_once (); 1970 #endif 1971 1972 if (bufp->allocated == 0) 1973 { 1974 if (bufp->buffer) 1975 { /* If zero allocated, but buffer is non-null, try to realloc 1976 enough space. This loses if buffer's address is bogus, but 1977 that is the user's responsibility. */ 1978 RETALLOC (bufp->buffer, INIT_BUF_SIZE, unsigned char); 1979 } 1980 else 1981 { /* Caller did not allocate a buffer. Do it for them. */ 1982 bufp->buffer = TALLOC (INIT_BUF_SIZE, unsigned char); 1983 } 1984 if (!bufp->buffer) FREE_STACK_RETURN (REG_ESPACE); 1985 1986 bufp->allocated = INIT_BUF_SIZE; 1987 } 1988 1989 begalt = b = bufp->buffer; 1990 1991 /* Loop through the uncompiled pattern until we're at the end. */ 1992 while (p != pend) 1993 { 1994 PATFETCH (c); 1995 1996 switch (c) 1997 { 1998 case '^': 1999 { 2000 if ( /* If at start of pattern, it's an operator. */ 2001 p == pattern + 1 2002 /* If context independent, it's an operator. */ 2003 || syntax & RE_CONTEXT_INDEP_ANCHORS 2004 /* Otherwise, depends on what's come before. */ 2005 || at_begline_loc_p (pattern, p, syntax)) 2006 BUF_PUSH (begline); 2007 else 2008 goto normal_char; 2009 } 2010 break; 2011 2012 2013 case '$': 2014 { 2015 if ( /* If at end of pattern, it's an operator. */ 2016 p == pend 2017 /* If context independent, it's an operator. */ 2018 || syntax & RE_CONTEXT_INDEP_ANCHORS 2019 /* Otherwise, depends on what's next. */ 2020 || at_endline_loc_p (p, pend, syntax)) 2021 BUF_PUSH (endline); 2022 else 2023 goto normal_char; 2024 } 2025 break; 2026 2027 2028 case '+': 2029 case '?': 2030 if ((syntax & RE_BK_PLUS_QM) 2031 || (syntax & RE_LIMITED_OPS)) 2032 goto normal_char; 2033 handle_plus: 2034 case '*': 2035 /* If there is no previous pattern... */ 2036 if (!laststart) 2037 { 2038 if (syntax & RE_CONTEXT_INVALID_OPS) 2039 FREE_STACK_RETURN (REG_BADRPT); 2040 else if (!(syntax & RE_CONTEXT_INDEP_OPS)) 2041 goto normal_char; 2042 } 2043 2044 { 2045 /* Are we optimizing this jump? */ 2046 boolean keep_string_p = false; 2047 2048 /* 1 means zero (many) matches is allowed. */ 2049 char zero_times_ok = 0, many_times_ok = 0; 2050 2051 /* If there is a sequence of repetition chars, collapse it 2052 down to just one (the right one). We can't combine 2053 interval operators with these because of, e.g., `a{2}*', 2054 which should only match an even number of `a's. */ 2055 2056 for (;;) 2057 { 2058 zero_times_ok |= c != '+'; 2059 many_times_ok |= c != '?'; 2060 2061 if (p == pend) 2062 break; 2063 2064 PATFETCH (c); 2065 2066 if (c == '*' 2067 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?'))) 2068 ; 2069 2070 else if (syntax & RE_BK_PLUS_QM && c == '\\') 2071 { 2072 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE); 2073 2074 PATFETCH (c1); 2075 if (!(c1 == '+' || c1 == '?')) 2076 { 2077 PATUNFETCH; 2078 PATUNFETCH; 2079 break; 2080 } 2081 2082 c = c1; 2083 } 2084 else 2085 { 2086 PATUNFETCH; 2087 break; 2088 } 2089 2090 /* If we get here, we found another repeat character. */ 2091 } 2092 2093 /* Star, etc. applied to an empty pattern is equivalent 2094 to an empty pattern. */ 2095 if (!laststart) 2096 break; 2097 2098 /* Now we know whether or not zero matches is allowed 2099 and also whether or not two or more matches is allowed. */ 2100 if (many_times_ok) 2101 { /* More than one repetition is allowed, so put in at the 2102 end a backward relative jump from `b' to before the next 2103 jump we're going to put in below (which jumps from 2104 laststart to after this jump). 2105 2106 But if we are at the `*' in the exact sequence `.*\n', 2107 insert an unconditional jump backwards to the ., 2108 instead of the beginning of the loop. This way we only 2109 push a failure point once, instead of every time 2110 through the loop. */ 2111 assert (p - 1 > pattern); 2112 2113 /* Allocate the space for the jump. */ 2114 GET_BUFFER_SPACE (3); 2115 2116 /* We know we are not at the first character of the pattern, 2117 because laststart was nonzero. And we've already 2118 incremented `p', by the way, to be the character after 2119 the `*'. Do we have to do something analogous here 2120 for null bytes, because of RE_DOT_NOT_NULL? */ 2121 if (TRANSLATE ((unsigned char)*(p - 2)) == TRANSLATE ('.') 2122 && zero_times_ok 2123 && p < pend 2124 && TRANSLATE ((unsigned char)*p) == TRANSLATE ('\n') 2125 && !(syntax & RE_DOT_NEWLINE)) 2126 { /* We have .*\n. */ 2127 STORE_JUMP (jump, b, laststart); 2128 keep_string_p = true; 2129 } 2130 else 2131 /* Anything else. */ 2132 STORE_JUMP (maybe_pop_jump, b, laststart - 3); 2133 2134 /* We've added more stuff to the buffer. */ 2135 b += 3; 2136 } 2137 2138 /* On failure, jump from laststart to b + 3, which will be the 2139 end of the buffer after this jump is inserted. */ 2140 GET_BUFFER_SPACE (3); 2141 INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump 2142 : on_failure_jump, 2143 laststart, b + 3); 2144 pending_exact = 0; 2145 b += 3; 2146 2147 if (!zero_times_ok) 2148 { 2149 /* At least one repetition is required, so insert a 2150 `dummy_failure_jump' before the initial 2151 `on_failure_jump' instruction of the loop. This 2152 effects a skip over that instruction the first time 2153 we hit that loop. */ 2154 GET_BUFFER_SPACE (3); 2155 INSERT_JUMP (dummy_failure_jump, laststart, laststart + 6); 2156 b += 3; 2157 } 2158 } 2159 break; 2160 2161 2162 case '.': 2163 laststart = b; 2164 BUF_PUSH (anychar); 2165 break; 2166 2167 2168 case '[': 2169 { 2170 CLEAR_RANGE_TABLE_WORK_USED (range_table_work); 2171 2172 if (p == pend) FREE_STACK_RETURN (REG_EBRACK); 2173 2174 /* Ensure that we have enough space to push a charset: the 2175 opcode, the length count, and the bitset; 34 bytes in all. */ 2176 GET_BUFFER_SPACE (34); 2177 2178 laststart = b; 2179 2180 /* We test `*p == '^' twice, instead of using an if 2181 statement, so we only need one BUF_PUSH. */ 2182 BUF_PUSH (*p == '^' ? charset_not : charset); 2183 if (*p == '^') 2184 p++; 2185 2186 /* Remember the first position in the bracket expression. */ 2187 p1 = p; 2188 2189 /* Push the number of bytes in the bitmap. */ 2190 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH); 2191 2192 /* Clear the whole map. */ 2193 bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH); 2194 2195 /* charset_not matches newline according to a syntax bit. */ 2196 if ((re_opcode_t) b[-2] == charset_not 2197 && (syntax & RE_HAT_LISTS_NOT_NEWLINE)) 2198 SET_LIST_BIT ('\n'); 2199 2200 /* Read in characters and ranges, setting map bits. */ 2201 for (;;) 2202 { 2203 int len; 2204 boolean escaped_char = false; 2205 2206 if (p == pend) FREE_STACK_RETURN (REG_EBRACK); 2207 2208 PATFETCH (c); 2209 2210 /* \ might escape characters inside [...] and [^...]. */ 2211 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\') 2212 { 2213 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE); 2214 2215 PATFETCH (c); 2216 escaped_char = true; 2217 } 2218 else 2219 { 2220 /* Could be the end of the bracket expression. If it's 2221 not (i.e., when the bracket expression is `[]' so 2222 far), the ']' character bit gets set way below. */ 2223 if (c == ']' && p != p1 + 1) 2224 break; 2225 } 2226 2227 /* If C indicates start of multibyte char, get the 2228 actual character code in C, and set the pattern 2229 pointer P to the next character boundary. */ 2230 if (bufp->multibyte && BASE_LEADING_CODE_P (c)) 2231 { 2232 PATUNFETCH; 2233 c = STRING_CHAR_AND_LENGTH (p, pend - p, len); 2234 p += len; 2235 } 2236 /* What should we do for the character which is 2237 greater than 0x7F, but not BASE_LEADING_CODE_P? 2238 XXX */ 2239 2240 /* See if we're at the beginning of a possible character 2241 class. */ 2242 2243 else if (!escaped_char && 2244 syntax & RE_CHAR_CLASSES && c == '[' && *p == ':') 2245 { 2246 /* Leave room for the null. */ 2247 char str[CHAR_CLASS_MAX_LENGTH + 1]; 2248 2249 PATFETCH (c); 2250 c1 = 0; 2251 2252 /* If pattern is `[[:'. */ 2253 if (p == pend) FREE_STACK_RETURN (REG_EBRACK); 2254 2255 for (;;) 2256 { 2257 PATFETCH (c); 2258 if (c == ':' || c == ']' || p == pend 2259 || c1 == CHAR_CLASS_MAX_LENGTH) 2260 break; 2261 str[c1++] = c; 2262 } 2263 str[c1] = '\0'; 2264 2265 /* If isn't a word bracketed by `[:' and `:]': 2266 undo the ending character, the letters, and 2267 leave the leading `:' and `[' (but set bits for 2268 them). */ 2269 if (c == ':' && *p == ']') 2270 { 2271 int ch; 2272 boolean is_alnum = STREQ (str, "alnum"); 2273 boolean is_alpha = STREQ (str, "alpha"); 2274 boolean is_blank = STREQ (str, "blank"); 2275 boolean is_cntrl = STREQ (str, "cntrl"); 2276 boolean is_digit = STREQ (str, "digit"); 2277 boolean is_graph = STREQ (str, "graph"); 2278 boolean is_lower = STREQ (str, "lower"); 2279 boolean is_print = STREQ (str, "print"); 2280 boolean is_punct = STREQ (str, "punct"); 2281 boolean is_space = STREQ (str, "space"); 2282 boolean is_upper = STREQ (str, "upper"); 2283 boolean is_xdigit = STREQ (str, "xdigit"); 2284 2285 if (!IS_CHAR_CLASS (str)) 2286 FREE_STACK_RETURN (REG_ECTYPE); 2287 2288 /* Throw away the ] at the end of the character 2289 class. */ 2290 PATFETCH (c); 2291 2292 if (p == pend) FREE_STACK_RETURN (REG_EBRACK); 2293 2294 for (ch = 0; ch < 1 << BYTEWIDTH; ch++) 2295 { 2296 int translated = TRANSLATE (ch); 2297 /* This was split into 3 if's to 2298 avoid an arbitrary limit in some compiler. */ 2299 if ( (is_alnum && ISALNUM (ch)) 2300 || (is_alpha && ISALPHA (ch)) 2301 || (is_blank && ISBLANK (ch)) 2302 || (is_cntrl && ISCNTRL (ch))) 2303 SET_LIST_BIT (translated); 2304 if ( (is_digit && ISDIGIT (ch)) 2305 || (is_graph && ISGRAPH (ch)) 2306 || (is_lower && ISLOWER (ch)) 2307 || (is_print && ISPRINT (ch))) 2308 SET_LIST_BIT (translated); 2309 if ( (is_punct && ISPUNCT (ch)) 2310 || (is_space && ISSPACE (ch)) 2311 || (is_upper && ISUPPER (ch)) 2312 || (is_xdigit && ISXDIGIT (ch))) 2313 SET_LIST_BIT (translated); 2314 } 2315 2316 /* Repeat the loop. */ 2317 continue; 2318 } 2319 else 2320 { 2321 c1++; 2322 while (c1--) 2323 PATUNFETCH; 2324 SET_LIST_BIT ('['); 2325 2326 /* Because the `:' may starts the range, we 2327 can't simply set bit and repeat the loop. 2328 Instead, just set it to C and handle below. */ 2329 c = ':'; 2330 } 2331 } 2332 2333 if (p < pend && p[0] == '-' && p[1] != ']') 2334 { 2335 2336 /* Discard the `-'. */ 2337 PATFETCH (c1); 2338 2339 /* Fetch the character which ends the range. */ 2340 PATFETCH (c1); 2341 if (bufp->multibyte && BASE_LEADING_CODE_P (c1)) 2342 { 2343 PATUNFETCH; 2344 c1 = STRING_CHAR_AND_LENGTH (p, pend - p, len); 2345 p += len; 2346 } 2347 2348 if (SINGLE_BYTE_CHAR_P (c) 2349 && ! SINGLE_BYTE_CHAR_P (c1)) 2350 { 2351 /* Handle a range such as \177-\377 in multibyte mode. 2352 Split that into two ranges,, 2353 the low one ending at 0237, and the high one 2354 starting at ...040. */ 2355 int c1_base = (c1 & ~0177) | 040; 2356 SET_RANGE_TABLE_WORK_AREA (range_table_work, c, c1); 2357 c1 = 0237; 2358 } 2359 else if (!SAME_CHARSET_P (c, c1)) 2360 FREE_STACK_RETURN (REG_ERANGE); 2361 } 2362 else 2363 /* Range from C to C. */ 2364 c1 = c; 2365 2366 /* Set the range ... */ 2367 if (SINGLE_BYTE_CHAR_P (c)) 2368 /* ... into bitmap. */ 2369 { 2370 unsigned this_char; 2371 int range_start = c, range_end = c1; 2372 2373 /* If the start is after the end, the range is empty. */ 2374 if (range_start > range_end) 2375 { 2376 if (syntax & RE_NO_EMPTY_RANGES) 2377 FREE_STACK_RETURN (REG_ERANGE); 2378 /* Else, repeat the loop. */ 2379 } 2380 else 2381 { 2382 for (this_char = range_start; this_char <= range_end; 2383 this_char++) 2384 SET_LIST_BIT (TRANSLATE (this_char)); 2385 } 2386 } 2387 else 2388 /* ... into range table. */ 2389 SET_RANGE_TABLE_WORK_AREA (range_table_work, c, c1); 2390 } 2391 2392 /* Discard any (non)matching list bytes that are all 0 at the 2393 end of the map. Decrease the map-length byte too. */ 2394 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0) 2395 b[-1]--; 2396 b += b[-1]; 2397 2398 /* Build real range table from work area. */ 2399 if (RANGE_TABLE_WORK_USED (range_table_work)) 2400 { 2401 int i; 2402 int used = RANGE_TABLE_WORK_USED (range_table_work); 2403 2404 /* Allocate space for COUNT + RANGE_TABLE. Needs two 2405 bytes for COUNT and three bytes for each character. */ 2406 GET_BUFFER_SPACE (2 + used * 3); 2407 2408 /* Indicate the existence of range table. */ 2409 laststart[1] |= 0x80; 2410 2411 STORE_NUMBER_AND_INCR (b, used / 2); 2412 for (i = 0; i < used; i++) 2413 STORE_CHARACTER_AND_INCR 2414 (b, RANGE_TABLE_WORK_ELT (range_table_work, i)); 2415 } 2416 } 2417 break; 2418 2419 2420 case '(': 2421 if (syntax & RE_NO_BK_PARENS) 2422 goto handle_open; 2423 else 2424 goto normal_char; 2425 2426 2427 case ')': 2428 if (syntax & RE_NO_BK_PARENS) 2429 goto handle_close; 2430 else 2431 goto normal_char; 2432 2433 2434 case '\n': 2435 if (syntax & RE_NEWLINE_ALT) 2436 goto handle_alt; 2437 else 2438 goto normal_char; 2439 2440 2441 case '|': 2442 if (syntax & RE_NO_BK_VBAR) 2443 goto handle_alt; 2444 else 2445 goto normal_char; 2446 2447 2448 case '{': 2449 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES) 2450 goto handle_interval; 2451 else 2452 goto normal_char; 2453 2454 2455 case '\\': 2456 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE); 2457 2458 /* Do not translate the character after the \, so that we can 2459 distinguish, e.g., \B from \b, even if we normally would 2460 translate, e.g., B to b. */ 2461 PATFETCH_RAW (c); 2462 2463 switch (c) 2464 { 2465 case '(': 2466 if (syntax & RE_NO_BK_PARENS) 2467 goto normal_backslash; 2468 2469 handle_open: 2470 bufp->re_nsub++; 2471 regnum++; 2472 2473 if (COMPILE_STACK_FULL) 2474 { 2475 RETALLOC (compile_stack.stack, compile_stack.size << 1, 2476 compile_stack_elt_t); 2477 if (compile_stack.stack == NULL) return REG_ESPACE; 2478 2479 compile_stack.size <<= 1; 2480 } 2481 2482 /* These are the values to restore when we hit end of this 2483 group. They are all relative offsets, so that if the 2484 whole pattern moves because of realloc, they will still 2485 be valid. */ 2486 COMPILE_STACK_TOP.begalt_offset = begalt - bufp->buffer; 2487 COMPILE_STACK_TOP.fixup_alt_jump 2488 = fixup_alt_jump ? fixup_alt_jump - bufp->buffer + 1 : 0; 2489 COMPILE_STACK_TOP.laststart_offset = b - bufp->buffer; 2490 COMPILE_STACK_TOP.regnum = regnum; 2491 2492 /* We will eventually replace the 0 with the number of 2493 groups inner to this one. But do not push a 2494 start_memory for groups beyond the last one we can 2495 represent in the compiled pattern. */ 2496 if (regnum <= MAX_REGNUM) 2497 { 2498 COMPILE_STACK_TOP.inner_group_offset = b - bufp->buffer + 2; 2499 BUF_PUSH_3 (start_memory, regnum, 0); 2500 } 2501 2502 compile_stack.avail++; 2503 2504 fixup_alt_jump = 0; 2505 laststart = 0; 2506 begalt = b; 2507 /* If we've reached MAX_REGNUM groups, then this open 2508 won't actually generate any code, so we'll have to 2509 clear pending_exact explicitly. */ 2510 pending_exact = 0; 2511 break; 2512 2513 2514 case ')': 2515 if (syntax & RE_NO_BK_PARENS) goto normal_backslash; 2516 2517 if (COMPILE_STACK_EMPTY) 2518 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD) 2519 goto normal_backslash; 2520 else 2521 FREE_STACK_RETURN (REG_ERPAREN); 2522 2523 handle_close: 2524 if (fixup_alt_jump) 2525 { /* Push a dummy failure point at the end of the 2526 alternative for a possible future 2527 `pop_failure_jump' to pop. See comments at 2528 `push_dummy_failure' in `re_match_2'. */ 2529 BUF_PUSH (push_dummy_failure); 2530 2531 /* We allocated space for this jump when we assigned 2532 to `fixup_alt_jump', in the `handle_alt' case below. */ 2533 STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1); 2534 } 2535 2536 /* See similar code for backslashed left paren above. */ 2537 if (COMPILE_STACK_EMPTY) 2538 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD) 2539 goto normal_char; 2540 else 2541 FREE_STACK_RETURN (REG_ERPAREN); 2542 2543 /* Since we just checked for an empty stack above, this 2544 ``can't happen''. */ 2545 assert (compile_stack.avail != 0); 2546 { 2547 /* We don't just want to restore into `regnum', because 2548 later groups should continue to be numbered higher, 2549 as in `(ab)c(de)' -- the second group is #2. */ 2550 regnum_t this_group_regnum; 2551 2552 compile_stack.avail--; 2553 begalt = bufp->buffer + COMPILE_STACK_TOP.begalt_offset; 2554 fixup_alt_jump 2555 = COMPILE_STACK_TOP.fixup_alt_jump 2556 ? bufp->buffer + COMPILE_STACK_TOP.fixup_alt_jump - 1 2557 : 0; 2558 laststart = bufp->buffer + COMPILE_STACK_TOP.laststart_offset; 2559 this_group_regnum = COMPILE_STACK_TOP.regnum; 2560 /* If we've reached MAX_REGNUM groups, then this open 2561 won't actually generate any code, so we'll have to 2562 clear pending_exact explicitly. */ 2563 pending_exact = 0; 2564 2565 /* We're at the end of the group, so now we know how many 2566 groups were inside this one. */ 2567 if (this_group_regnum <= MAX_REGNUM) 2568 { 2569 unsigned char *inner_group_loc 2570 = bufp->buffer + COMPILE_STACK_TOP.inner_group_offset; 2571 2572 *inner_group_loc = regnum - this_group_regnum; 2573 BUF_PUSH_3 (stop_memory, this_group_regnum, 2574 regnum - this_group_regnum); 2575 } 2576 } 2577 break; 2578 2579 2580 case '|': /* `\|'. */ 2581 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR) 2582 goto normal_backslash; 2583 handle_alt: 2584 if (syntax & RE_LIMITED_OPS) 2585 goto normal_char; 2586 2587 /* Insert before the previous alternative a jump which 2588 jumps to this alternative if the former fails. */ 2589 GET_BUFFER_SPACE (3); 2590 INSERT_JUMP (on_failure_jump, begalt, b + 6); 2591 pending_exact = 0; 2592 b += 3; 2593 2594 /* The alternative before this one has a jump after it 2595 which gets executed if it gets matched. Adjust that 2596 jump so it will jump to this alternative's analogous 2597 jump (put in below, which in turn will jump to the next 2598 (if any) alternative's such jump, etc.). The last such 2599 jump jumps to the correct final destination. A picture: 2600 _____ _____ 2601 | | | | 2602 | v | v 2603 a | b | c 2604 2605 If we are at `b', then fixup_alt_jump right now points to a 2606 three-byte space after `a'. We'll put in the jump, set 2607 fixup_alt_jump to right after `b', and leave behind three 2608 bytes which we'll fill in when we get to after `c'. */ 2609 2610 if (fixup_alt_jump) 2611 STORE_JUMP (jump_past_alt, fixup_alt_jump, b); 2612 2613 /* Mark and leave space for a jump after this alternative, 2614 to be filled in later either by next alternative or 2615 when know we're at the end of a series of alternatives. */ 2616 fixup_alt_jump = b; 2617 GET_BUFFER_SPACE (3); 2618 b += 3; 2619 2620 laststart = 0; 2621 begalt = b; 2622 break; 2623 2624 2625 case '{': 2626 /* If \{ is a literal. */ 2627 if (!(syntax & RE_INTERVALS) 2628 /* If we're at `\{' and it's not the open-interval 2629 operator. */ 2630 || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES)) 2631 || (p - 2 == pattern && p == pend)) 2632 goto normal_backslash; 2633 2634 handle_interval: 2635 { 2636 /* If got here, then the syntax allows intervals. */ 2637 2638 /* At least (most) this many matches must be made. */ 2639 int lower_bound = -1, upper_bound = -1; 2640 2641 beg_interval = p - 1; 2642 2643 if (p == pend) 2644 { 2645 if (syntax & RE_NO_BK_BRACES) 2646 goto unfetch_interval; 2647 else 2648 FREE_STACK_RETURN (REG_EBRACE); 2649 } 2650 2651 GET_UNSIGNED_NUMBER (lower_bound); 2652 2653 if (c == ',') 2654 { 2655 GET_UNSIGNED_NUMBER (upper_bound); 2656 if (upper_bound < 0) upper_bound = RE_DUP_MAX; 2657 } 2658 else 2659 /* Interval such as `{1}' => match exactly once. */ 2660 upper_bound = lower_bound; 2661 2662 if (lower_bound < 0 || upper_bound > RE_DUP_MAX 2663 || lower_bound > upper_bound) 2664 { 2665 if (syntax & RE_NO_BK_BRACES) 2666 goto unfetch_interval; 2667 else 2668 FREE_STACK_RETURN (REG_BADBR); 2669 } 2670 2671 if (!(syntax & RE_NO_BK_BRACES)) 2672 { 2673 if (c != '\\') FREE_STACK_RETURN (REG_EBRACE); 2674 2675 PATFETCH (c); 2676 } 2677 2678 if (c != '}') 2679 { 2680 if (syntax & RE_NO_BK_BRACES) 2681 goto unfetch_interval; 2682 else 2683 FREE_STACK_RETURN (REG_BADBR); 2684 } 2685 2686 /* We just parsed a valid interval. */ 2687 2688 /* If it's invalid to have no preceding re. */ 2689 if (!laststart) 2690 { 2691 if (syntax & RE_CONTEXT_INVALID_OPS) 2692 FREE_STACK_RETURN (REG_BADRPT); 2693 else if (syntax & RE_CONTEXT_INDEP_OPS) 2694 laststart = b; 2695 else 2696 goto unfetch_interval; 2697 } 2698 2699 /* If the upper bound is zero, don't want to succeed at 2700 all; jump from `laststart' to `b + 3', which will be 2701 the end of the buffer after we insert the jump. */ 2702 if (upper_bound == 0) 2703 { 2704 GET_BUFFER_SPACE (3); 2705 INSERT_JUMP (jump, laststart, b + 3); 2706 b += 3; 2707 } 2708 2709 /* Otherwise, we have a nontrivial interval. When 2710 we're all done, the pattern will look like: 2711 set_number_at <jump count> <upper bound> 2712 set_number_at <succeed_n count> <lower bound> 2713 succeed_n <after jump addr> <succeed_n count> 2714 <body of loop> 2715 jump_n <succeed_n addr> <jump count> 2716 (The upper bound and `jump_n' are omitted if 2717 `upper_bound' is 1, though.) */ 2718 else 2719 { /* If the upper bound is > 1, we need to insert 2720 more at the end of the loop. */ 2721 unsigned nbytes = 10 + (upper_bound > 1) * 10; 2722 2723 GET_BUFFER_SPACE (nbytes); 2724 2725 /* Initialize lower bound of the `succeed_n', even 2726 though it will be set during matching by its 2727 attendant `set_number_at' (inserted next), 2728 because `re_compile_fastmap' needs to know. 2729 Jump to the `jump_n' we might insert below. */ 2730 INSERT_JUMP2 (succeed_n, laststart, 2731 b + 5 + (upper_bound > 1) * 5, 2732 lower_bound); 2733 b += 5; 2734 2735 /* Code to initialize the lower bound. Insert 2736 before the `succeed_n'. The `5' is the last two 2737 bytes of this `set_number_at', plus 3 bytes of 2738 the following `succeed_n'. */ 2739 insert_op2 (set_number_at, laststart, 5, lower_bound, b); 2740 b += 5; 2741 2742 if (upper_bound > 1) 2743 { /* More than one repetition is allowed, so 2744 append a backward jump to the `succeed_n' 2745 that starts this interval. 2746 2747 When we've reached this during matching, 2748 we'll have matched the interval once, so 2749 jump back only `upper_bound - 1' times. */ 2750 STORE_JUMP2 (jump_n, b, laststart + 5, 2751 upper_bound - 1); 2752 b += 5; 2753 2754 /* The location we want to set is the second 2755 parameter of the `jump_n'; that is `b-2' as 2756 an absolute address. `laststart' will be 2757 the `set_number_at' we're about to insert; 2758 `laststart+3' the number to set, the source 2759 for the relative address. But we are 2760 inserting into the middle of the pattern -- 2761 so everything is getting moved up by 5. 2762 Conclusion: (b - 2) - (laststart + 3) + 5, 2763 i.e., b - laststart. 2764 2765 We insert this at the beginning of the loop 2766 so that if we fail during matching, we'll 2767 reinitialize the bounds. */ 2768 insert_op2 (set_number_at, laststart, b - laststart, 2769 upper_bound - 1, b); 2770 b += 5; 2771 } 2772 } 2773 pending_exact = 0; 2774 beg_interval = NULL; 2775 } 2776 break; 2777 2778 unfetch_interval: 2779 /* If an invalid interval, match the characters as literals. */ 2780 assert (beg_interval); 2781 p = beg_interval; 2782 beg_interval = NULL; 2783 2784 /* normal_char and normal_backslash need `c'. */ 2785 PATFETCH (c); 2786 2787 if (!(syntax & RE_NO_BK_BRACES)) 2788 { 2789 if (p > pattern && p[-1] == '\\') 2790 goto normal_backslash; 2791 } 2792 goto normal_char; 2793 2794 #ifdef emacs 2795 /* There is no way to specify the before_dot and after_dot 2796 operators. rms says this is ok. --karl */ 2797 case '=': 2798 BUF_PUSH (at_dot); 2799 break; 2800 2801 case 's': 2802 laststart = b; 2803 PATFETCH (c); 2804 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]); 2805 break; 2806 2807 case 'S': 2808 laststart = b; 2809 PATFETCH (c); 2810 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]); 2811 break; 2812 2813 case 'c': 2814 laststart = b; 2815 PATFETCH_RAW (c); 2816 BUF_PUSH_2 (categoryspec, c); 2817 break; 2818 2819 case 'C': 2820 laststart = b; 2821 PATFETCH_RAW (c); 2822 BUF_PUSH_2 (notcategoryspec, c); 2823 break; 2824 #endif /* emacs */ 2825 2826 2827 case 'w': 2828 laststart = b; 2829 BUF_PUSH (wordchar); 2830 break; 2831 2832 2833 case 'W': 2834 laststart = b; 2835 BUF_PUSH (notwordchar); 2836 break; 2837 2838 2839 case '<': 2840 BUF_PUSH (wordbeg); 2841 break; 2842 2843 case '>': 2844 BUF_PUSH (wordend); 2845 break; 2846 2847 case 'b': 2848 BUF_PUSH (wordbound); 2849 break; 2850 2851 case 'B': 2852 BUF_PUSH (notwordbound); 2853 break; 2854 2855 case '`': 2856 BUF_PUSH (begbuf); 2857 break; 2858 2859 case '\'': 2860 BUF_PUSH (endbuf); 2861 break; 2862 2863 case '1': case '2': case '3': case '4': case '5': 2864 case '6': case '7': case '8': case '9': 2865 if (syntax & RE_NO_BK_REFS) 2866 goto normal_char; 2867 2868 c1 = c - '0'; 2869 2870 if (c1 > regnum) 2871 FREE_STACK_RETURN (REG_ESUBREG); 2872 2873 /* Can't back reference to a subexpression if inside of it. */ 2874 if (group_in_compile_stack (compile_stack, c1)) 2875 goto normal_char; 2876 2877 laststart = b; 2878 BUF_PUSH_2 (duplicate, c1); 2879 break; 2880 2881 2882 case '+': 2883 case '?': 2884 if (syntax & RE_BK_PLUS_QM) 2885 goto handle_plus; 2886 else 2887 goto normal_backslash; 2888 2889 default: 2890 normal_backslash: 2891 /* You might think it would be useful for \ to mean 2892 not to translate; but if we don't translate it 2893 it will never match anything. */ 2894 c = TRANSLATE (c); 2895 goto normal_char; 2896 } 2897 break; 2898 2899 2900 default: 2901 /* Expects the character in `c'. */ 2902 normal_char: 2903 p1 = p - 1; /* P1 points the head of C. */ 2904 #ifdef emacs 2905 if (bufp->multibyte) 2906 { 2907 c = STRING_CHAR (p1, pend - p1); 2908 c = TRANSLATE (c); 2909 /* Set P to the next character boundary. */ 2910 p += MULTIBYTE_FORM_LENGTH (p1, pend - p1) - 1; 2911 } 2912 #endif 2913 /* If no exactn currently being built. */ 2914 if (!pending_exact 2915 2916 /* If last exactn not at current position. */ 2917 || pending_exact + *pending_exact + 1 != b 2918 2919 /* We have only one byte following the exactn for the count. */ 2920 || *pending_exact >= (1 << BYTEWIDTH) - (p - p1) 2921 2922 /* If followed by a repetition operator. */ 2923 || (p != pend && (*p == '*' || *p == '^')) 2924 || ((syntax & RE_BK_PLUS_QM) 2925 ? p + 1 < pend && *p == '\\' && (p[1] == '+' || p[1] == '?') 2926 : p != pend && (*p == '+' || *p == '?')) 2927 || ((syntax & RE_INTERVALS) 2928 && ((syntax & RE_NO_BK_BRACES) 2929 ? p != pend && *p == '{' 2930 : p + 1 < pend && p[0] == '\\' && p[1] == '{'))) 2931 { 2932 /* Start building a new exactn. */ 2933 2934 laststart = b; 2935 2936 BUF_PUSH_2 (exactn, 0); 2937 pending_exact = b - 1; 2938 } 2939 2940 #ifdef emacs 2941 if (! SINGLE_BYTE_CHAR_P (c)) 2942 { 2943 unsigned char work[4], *str; 2944 int i = CHAR_STRING (c, work, str); 2945 int j; 2946 for (j = 0; j < i; j++) 2947 { 2948 BUF_PUSH (str[j]); 2949 (*pending_exact)++; 2950 } 2951 } 2952 else 2953 #endif 2954 { 2955 BUF_PUSH (c); 2956 (*pending_exact)++; 2957 } 2958 break; 2959 } /* switch (c) */ 2960 } /* while p != pend */ 2961 2962 2963 /* Through the pattern now. */ 2964 2965 if (fixup_alt_jump) 2966 STORE_JUMP (jump_past_alt, fixup_alt_jump, b); 2967 2968 if (!COMPILE_STACK_EMPTY) 2969 FREE_STACK_RETURN (REG_EPAREN); 2970 2971 /* If we don't want backtracking, force success 2972 the first time we reach the end of the compiled pattern. */ 2973 if (syntax & RE_NO_POSIX_BACKTRACKING) 2974 BUF_PUSH (succeed); 2975 2976 free (compile_stack.stack); 2977 2978 /* We have succeeded; set the length of the buffer. */ 2979 bufp->used = b - bufp->buffer; 2980 2981 #ifdef DEBUG 2982 if (debug) 2983 { 2984 DEBUG_PRINT1 ("\nCompiled pattern: \n"); 2985 print_compiled_pattern (bufp); 2986 } 2987 #endif /* DEBUG */ 2988 2989 #ifndef MATCH_MAY_ALLOCATE 2990 /* Initialize the failure stack to the largest possible stack. This 2991 isn't necessary unless we're trying to avoid calling alloca in 2992 the search and match routines. */ 2993 { 2994 int num_regs = bufp->re_nsub + 1; 2995 2996 if (fail_stack.size < re_max_failures * TYPICAL_FAILURE_SIZE) 2997 { 2998 fail_stack.size = re_max_failures * TYPICAL_FAILURE_SIZE; 2999 3000 #ifdef emacs 3001 if (! fail_stack.stack) 3002 fail_stack.stack 3003 = (fail_stack_elt_t *) xmalloc (fail_stack.size 3004 * sizeof (fail_stack_elt_t)); 3005 else 3006 fail_stack.stack 3007 = (fail_stack_elt_t *) xrealloc (fail_stack.stack, 3008 (fail_stack.size 3009 * sizeof (fail_stack_elt_t))); 3010 #else /* not emacs */ 3011 if (! fail_stack.stack) 3012 fail_stack.stack 3013 = (fail_stack_elt_t *) malloc (fail_stack.size 3014 * sizeof (fail_stack_elt_t)); 3015 else 3016 fail_stack.stack 3017 = (fail_stack_elt_t *) realloc (fail_stack.stack, 3018 (fail_stack.size 3019 * sizeof (fail_stack_elt_t))); 3020 #endif /* not emacs */ 3021 } 3022 3023 regex_grow_registers (num_regs); 3024 } 3025 #endif /* not MATCH_MAY_ALLOCATE */ 3026 3027 return REG_NOERROR; 3028 } /* regex_compile */ 3029 3030 /* Subroutines for `regex_compile'. */ 3031 3032 /* Store OP at LOC followed by two-byte integer parameter ARG. */ 3033 3034 static void 3035 store_op1 (op, loc, arg) 3036 re_opcode_t op; 3037 unsigned char *loc; 3038 int arg; 3039 { 3040 *loc = (unsigned char) op; 3041 STORE_NUMBER (loc + 1, arg); 3042 } 3043 3044 3045 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */ 3046 3047 static void 3048 store_op2 (op, loc, arg1, arg2) 3049 re_opcode_t op; 3050 unsigned char *loc; 3051 int arg1, arg2; 3052 { 3053 *loc = (unsigned char) op; 3054 STORE_NUMBER (loc + 1, arg1); 3055 STORE_NUMBER (loc + 3, arg2); 3056 } 3057 3058 3059 /* Copy the bytes from LOC to END to open up three bytes of space at LOC 3060 for OP followed by two-byte integer parameter ARG. */ 3061 3062 static void 3063 insert_op1 (op, loc, arg, end) 3064 re_opcode_t op; 3065 unsigned char *loc; 3066 int arg; 3067 unsigned char *end; 3068 { 3069 register unsigned char *pfrom = end; 3070 register unsigned char *pto = end + 3; 3071 3072 while (pfrom != loc) 3073 *--pto = *--pfrom; 3074 3075 store_op1 (op, loc, arg); 3076 } 3077 3078 3079 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */ 3080 3081 static void 3082 insert_op2 (op, loc, arg1, arg2, end) 3083 re_opcode_t op; 3084 unsigned char *loc; 3085 int arg1, arg2; 3086 unsigned char *end; 3087 { 3088 register unsigned char *pfrom = end; 3089 register unsigned char *pto = end + 5; 3090 3091 while (pfrom != loc) 3092 *--pto = *--pfrom; 3093 3094 store_op2 (op, loc, arg1, arg2); 3095 } 3096 3097 3098 /* P points to just after a ^ in PATTERN. Return true if that ^ comes 3099 after an alternative or a begin-subexpression. We assume there is at 3100 least one character before the ^. */ 3101 3102 static boolean 3103 at_begline_loc_p (pattern, p, syntax) 3104 const char *pattern, *p; 3105 reg_syntax_t syntax; 3106 { 3107 const char *prev = p - 2; 3108 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\'; 3109 3110 return 3111 /* After a subexpression? */ 3112 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash)) 3113 /* After an alternative? */ 3114 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash)); 3115 } 3116 3117 3118 /* The dual of at_begline_loc_p. This one is for $. We assume there is 3119 at least one character after the $, i.e., `P < PEND'. */ 3120 3121 static boolean 3122 at_endline_loc_p (p, pend, syntax) 3123 const char *p, *pend; 3124 int syntax; 3125 { 3126 const char *next = p; 3127 boolean next_backslash = *next == '\\'; 3128 const char *next_next = p + 1 < pend ? p + 1 : 0; 3129 3130 return 3131 /* Before a subexpression? */ 3132 (syntax & RE_NO_BK_PARENS ? *next == ')' 3133 : next_backslash && next_next && *next_next == ')') 3134 /* Before an alternative? */ 3135 || (syntax & RE_NO_BK_VBAR ? *next == '|' 3136 : next_backslash && next_next && *next_next == '|'); 3137 } 3138 3139 3140 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and 3141 false if it's not. */ 3142 3143 static boolean 3144 group_in_compile_stack (compile_stack, regnum) 3145 compile_stack_type compile_stack; 3146 regnum_t regnum; 3147 { 3148 int this_element; 3149 3150 for (this_element = compile_stack.avail - 1; 3151 this_element >= 0; 3152 this_element--) 3153 if (compile_stack.stack[this_element].regnum == regnum) 3154 return true; 3155 3156 return false; 3157 } 3158 3159 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in 3160 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible 3161 characters can start a string that matches the pattern. This fastmap 3162 is used by re_search to skip quickly over impossible starting points. 3163 3164 The caller must supply the address of a (1 << BYTEWIDTH)-byte data 3165 area as BUFP->fastmap. 3166 3167 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in 3168 the pattern buffer. 3169 3170 Returns 0 if we succeed, -2 if an internal error. */ 3171 3172 int 3173 re_compile_fastmap (bufp) 3174 struct re_pattern_buffer *bufp; 3175 { 3176 int i, j, k; 3177 #ifdef MATCH_MAY_ALLOCATE 3178 fail_stack_type fail_stack; 3179 #endif 3180 #ifndef REGEX_MALLOC 3181 char *destination; 3182 #endif 3183 /* We don't push any register information onto the failure stack. */ 3184 unsigned num_regs = 0; 3185 3186 register char *fastmap = bufp->fastmap; 3187 unsigned char *pattern = bufp->buffer; 3188 unsigned long size = bufp->used; 3189 unsigned char *p = pattern; 3190 register unsigned char *pend = pattern + size; 3191 3192 /* This holds the pointer to the failure stack, when 3193 it is allocated relocatably. */ 3194 fail_stack_elt_t *failure_stack_ptr; 3195 3196 /* Assume that each path through the pattern can be null until 3197 proven otherwise. We set this false at the bottom of switch 3198 statement, to which we get only if a particular path doesn't 3199 match the empty string. */ 3200 boolean path_can_be_null = true; 3201 3202 /* We aren't doing a `succeed_n' to begin with. */ 3203 boolean succeed_n_p = false; 3204 3205 /* If all elements for base leading-codes in fastmap is set, this 3206 flag is set true. */ 3207 boolean match_any_multibyte_characters = false; 3208 3209 /* Maximum code of simple (single byte) character. */ 3210 int simple_char_max; 3211 3212 assert (fastmap != NULL && p != NULL); 3213 3214 INIT_FAIL_STACK (); 3215 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */ 3216 bufp->fastmap_accurate = 1; /* It will be when we're done. */ 3217 bufp->can_be_null = 0; 3218 3219 while (1) 3220 { 3221 if (p == pend || *p == succeed) 3222 { 3223 /* We have reached the (effective) end of pattern. */ 3224 if (!FAIL_STACK_EMPTY ()) 3225 { 3226 bufp->can_be_null |= path_can_be_null; 3227 3228 /* Reset for next path. */ 3229 path_can_be_null = true; 3230 3231 p = fail_stack.stack[--fail_stack.avail].pointer; 3232 3233 continue; 3234 } 3235 else 3236 break; 3237 } 3238 3239 /* We should never be about to go beyond the end of the pattern. */ 3240 assert (p < pend); 3241 3242 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++)) 3243 { 3244 3245 /* I guess the idea here is to simply not bother with a fastmap 3246 if a backreference is used, since it's too hard to figure out 3247 the fastmap for the corresponding group. Setting 3248 `can_be_null' stops `re_search_2' from using the fastmap, so 3249 that is all we do. */ 3250 case duplicate: 3251 bufp->can_be_null = 1; 3252 goto done; 3253 3254 3255 /* Following are the cases which match a character. These end 3256 with `break'. */ 3257 3258 case exactn: 3259 fastmap[p[1]] = 1; 3260 break; 3261 3262 3263 #ifndef emacs 3264 case charset: 3265 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) 3266 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) 3267 fastmap[j] = 1; 3268 break; 3269 3270 3271 case charset_not: 3272 /* Chars beyond end of map must be allowed. */ 3273 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++) 3274 fastmap[j] = 1; 3275 3276 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--) 3277 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))) 3278 fastmap[j] = 1; 3279 break; 3280 3281 3282 case wordchar: 3283 for (j = 0; j < (1 << BYTEWIDTH); j++) 3284 if (SYNTAX (j) == Sword) 3285 fastmap[j] = 1; 3286 break; 3287 3288 3289 case notwordchar: 3290 for (j = 0; j < (1 << BYTEWIDTH); j++) 3291 if (SYNTAX (j) != Sword) 3292 fastmap[j] = 1; 3293 break; 3294 #else /* emacs */ 3295 case charset: 3296 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++; 3297 j >= 0; j--) 3298 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))) 3299 fastmap[j] = 1; 3300 3301 if (CHARSET_RANGE_TABLE_EXISTS_P (&p[-2]) 3302 && match_any_multibyte_characters == false) 3303 { 3304 /* Set fastmap[I] 1 where I is a base leading code of each 3305 multibyte character in the range table. */ 3306 int c, count; 3307 3308 /* Make P points the range table. */ 3309 p += CHARSET_BITMAP_SIZE (&p[-2]); 3310 3311 /* Extract the number of ranges in range table into 3312 COUNT. */ 3313 EXTRACT_NUMBER_AND_INCR (count, p); 3314 for (; count > 0; count--, p += 2 * 3) /* XXX */ 3315 { 3316 /* Extract the start of each range. */ 3317 EXTRACT_CHARACTER (c, p); 3318 j = CHAR_CHARSET (c); 3319 fastmap[CHARSET_LEADING_CODE_BASE (j)] = 1; 3320 } 3321 } 3322 break; 3323 3324 3325 case charset_not: 3326 /* Chars beyond end of bitmap are possible matches. 3327 All the single-byte codes can occur in multibyte buffers. 3328 So any that are not listed in the charset 3329 are possible matches, even in multibyte buffers. */ 3330 simple_char_max = (1 << BYTEWIDTH); 3331 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH; 3332 j < simple_char_max; j++) 3333 fastmap[j] = 1; 3334 3335 for (j = CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH - 1, p++; 3336 j >= 0; j--) 3337 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))) 3338 fastmap[j] = 1; 3339 3340 if (bufp->multibyte) 3341 /* Any character set can possibly contain a character 3342 which doesn't match the specified set of characters. */ 3343 { 3344 set_fastmap_for_multibyte_characters: 3345 if (match_any_multibyte_characters == false) 3346 { 3347 for (j = 0x80; j < 0xA0; j++) /* XXX */ 3348 if (BASE_LEADING_CODE_P (j)) 3349 fastmap[j] = 1; 3350 match_any_multibyte_characters = true; 3351 } 3352 } 3353 break; 3354 3355 3356 case wordchar: 3357 /* All the single-byte codes can occur in multibyte buffers, 3358 and they may have word syntax. So do consider them. */ 3359 simple_char_max = (1 << BYTEWIDTH); 3360 for (j = 0; j < simple_char_max; j++) 3361 if (SYNTAX (j) == Sword) 3362 fastmap[j] = 1; 3363 3364 if (bufp->multibyte) 3365 /* Any character set can possibly contain a character 3366 whose syntax is `Sword'. */ 3367 goto set_fastmap_for_multibyte_characters; 3368 break; 3369 3370 3371 case notwordchar: 3372 /* All the single-byte codes can occur in multibyte buffers, 3373 and they may not have word syntax. So do consider them. */ 3374 simple_char_max = (1 << BYTEWIDTH); 3375 for (j = 0; j < simple_char_max; j++) 3376 if (SYNTAX (j) != Sword) 3377 fastmap[j] = 1; 3378 3379 if (bufp->multibyte) 3380 /* Any character set can possibly contain a character 3381 whose syntax is not `Sword'. */ 3382 goto set_fastmap_for_multibyte_characters; 3383 break; 3384 #endif 3385 3386 case anychar: 3387 { 3388 int fastmap_newline = fastmap['\n']; 3389 3390 /* `.' matches anything, except perhaps newline. 3391 Even in a multibyte buffer, it should match any 3392 conceivable byte value for the fastmap. */ 3393 if (bufp->multibyte) 3394 match_any_multibyte_characters = true; 3395 3396 simple_char_max = (1 << BYTEWIDTH); 3397 for (j = 0; j < simple_char_max; j++) 3398 fastmap[j] = 1; 3399 3400 /* ... except perhaps newline. */ 3401 if (!(bufp->syntax & RE_DOT_NEWLINE)) 3402 fastmap['\n'] = fastmap_newline; 3403 3404 /* Return if we have already set `can_be_null'; if we have, 3405 then the fastmap is irrelevant. Something's wrong here. */ 3406 else if (bufp->can_be_null) 3407 goto done; 3408 3409 /* Otherwise, have to check alternative paths. */ 3410 break; 3411 } 3412 3413 #ifdef emacs 3414 case wordbound: 3415 case notwordbound: 3416 case wordbeg: 3417 case wordend: 3418 case notsyntaxspec: 3419 case syntaxspec: 3420 /* This match depends on text properties. These end with 3421 aborting optimizations. */ 3422 bufp->can_be_null = 1; 3423 goto done; 3424 #if 0 3425 k = *p++; 3426 simple_char_max = bufp->multibyte ? 0x80 : (1 << BYTEWIDTH); 3427 for (j = 0; j < simple_char_max; j++) 3428 if (SYNTAX (j) == (enum syntaxcode) k) 3429 fastmap[j] = 1; 3430 3431 if (bufp->multibyte) 3432 /* Any character set can possibly contain a character 3433 whose syntax is K. */ 3434 goto set_fastmap_for_multibyte_characters; 3435 break; 3436 3437 case notsyntaxspec: 3438 k = *p++; 3439 simple_char_max = bufp->multibyte ? 0x80 : (1 << BYTEWIDTH); 3440 for (j = 0; j < simple_char_max; j++) 3441 if (SYNTAX (j) != (enum syntaxcode) k) 3442 fastmap[j] = 1; 3443 3444 if (bufp->multibyte) 3445 /* Any character set can possibly contain a character 3446 whose syntax is not K. */ 3447 goto set_fastmap_for_multibyte_characters; 3448 break; 3449 #endif 3450 3451 3452 case categoryspec: 3453 k = *p++; 3454 simple_char_max = (1 << BYTEWIDTH); 3455 for (j = 0; j < simple_char_max; j++) 3456 if (CHAR_HAS_CATEGORY (j, k)) 3457 fastmap[j] = 1; 3458 3459 if (bufp->multibyte) 3460 /* Any character set can possibly contain a character 3461 whose category is K. */ 3462 goto set_fastmap_for_multibyte_characters; 3463 break; 3464 3465 3466 case notcategoryspec: 3467 k = *p++; 3468 simple_char_max = (1 << BYTEWIDTH); 3469 for (j = 0; j < simple_char_max; j++) 3470 if (!CHAR_HAS_CATEGORY (j, k)) 3471 fastmap[j] = 1; 3472 3473 if (bufp->multibyte) 3474 /* Any character set can possibly contain a character 3475 whose category is not K. */ 3476 goto set_fastmap_for_multibyte_characters; 3477 break; 3478 3479 /* All cases after this match the empty string. These end with 3480 `continue'. */ 3481 3482 3483 case before_dot: 3484 case at_dot: 3485 case after_dot: 3486 continue; 3487 #endif /* emacs */ 3488 3489 3490 case no_op: 3491 case begline: 3492 case endline: 3493 case begbuf: 3494 case endbuf: 3495 #ifndef emacs 3496 case wordbound: 3497 case notwordbound: 3498 case wordbeg: 3499 case wordend: 3500 #endif 3501 case push_dummy_failure: 3502 continue; 3503 3504 3505 case jump_n: 3506 case pop_failure_jump: 3507 case maybe_pop_jump: 3508 case jump: 3509 case jump_past_alt: 3510 case dummy_failure_jump: 3511 EXTRACT_NUMBER_AND_INCR (j, p); 3512 p += j; 3513 if (j > 0) 3514 continue; 3515 3516 /* Jump backward implies we just went through the body of a 3517 loop and matched nothing. Opcode jumped to should be 3518 `on_failure_jump' or `succeed_n'. Just treat it like an 3519 ordinary jump. For a * loop, it has pushed its failure 3520 point already; if so, discard that as redundant. */ 3521 if ((re_opcode_t) *p != on_failure_jump 3522 && (re_opcode_t) *p != succeed_n) 3523 continue; 3524 3525 p++; 3526 EXTRACT_NUMBER_AND_INCR (j, p); 3527 p += j; 3528 3529 /* If what's on the stack is where we are now, pop it. */ 3530 if (!FAIL_STACK_EMPTY () 3531 && fail_stack.stack[fail_stack.avail - 1].pointer == p) 3532 fail_stack.avail--; 3533 3534 continue; 3535 3536 3537 case on_failure_jump: 3538 case on_failure_keep_string_jump: 3539 handle_on_failure_jump: 3540 EXTRACT_NUMBER_AND_INCR (j, p); 3541 3542 /* For some patterns, e.g., `(a?)?', `p+j' here points to the 3543 end of the pattern. We don't want to push such a point, 3544 since when we restore it above, entering the switch will 3545 increment `p' past the end of the pattern. We don't need 3546 to push such a point since we obviously won't find any more 3547 fastmap entries beyond `pend'. Such a pattern can match 3548 the null string, though. */ 3549 if (p + j < pend) 3550 { 3551 if (!PUSH_PATTERN_OP (p + j, fail_stack)) 3552 { 3553 RESET_FAIL_STACK (); 3554 return -2; 3555 } 3556 } 3557 else 3558 bufp->can_be_null = 1; 3559 3560 if (succeed_n_p) 3561 { 3562 EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */ 3563 succeed_n_p = false; 3564 } 3565 3566 continue; 3567 3568 3569 case succeed_n: 3570 /* Get to the number of times to succeed. */ 3571 p += 2; 3572 3573 /* Increment p past the n for when k != 0. */ 3574 EXTRACT_NUMBER_AND_INCR (k, p); 3575 if (k == 0) 3576 { 3577 p -= 4; 3578 succeed_n_p = true; /* Spaghetti code alert. */ 3579 goto handle_on_failure_jump; 3580 } 3581 continue; 3582 3583 3584 case set_number_at: 3585 p += 4; 3586 continue; 3587 3588 3589 case start_memory: 3590 case stop_memory: 3591 p += 2; 3592 continue; 3593 3594 3595 default: 3596 abort (); /* We have listed all the cases. */ 3597 } /* switch *p++ */ 3598 3599 /* Getting here means we have found the possible starting 3600 characters for one path of the pattern -- and that the empty 3601 string does not match. We need not follow this path further. 3602 Instead, look at the next alternative (remembered on the 3603 stack), or quit if no more. The test at the top of the loop 3604 does these things. */ 3605 path_can_be_null = false; 3606 p = pend; 3607 } /* while p */ 3608 3609 /* Set `can_be_null' for the last path (also the first path, if the 3610 pattern is empty). */ 3611 bufp->can_be_null |= path_can_be_null; 3612 3613 done: 3614 RESET_FAIL_STACK (); 3615 return 0; 3616 } /* re_compile_fastmap */ 3617 3618 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and 3619 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use 3620 this memory for recording register information. STARTS and ENDS 3621 must be allocated using the malloc library routine, and must each 3622 be at least NUM_REGS * sizeof (regoff_t) bytes long. 3623 3624 If NUM_REGS == 0, then subsequent matches should allocate their own 3625 register data. 3626 3627 Unless this function is called, the first search or match using 3628 PATTERN_BUFFER will allocate its own register data, without 3629 freeing the old data. */ 3630 3631 void 3632 re_set_registers (bufp, regs, num_regs, starts, ends) 3633 struct re_pattern_buffer *bufp; 3634 struct re_registers *regs; 3635 unsigned num_regs; 3636 regoff_t *starts, *ends; 3637 { 3638 if (num_regs) 3639 { 3640 bufp->regs_allocated = REGS_REALLOCATE; 3641 regs->num_regs = num_regs; 3642 regs->start = starts; 3643 regs->end = ends; 3644 } 3645 else 3646 { 3647 bufp->regs_allocated = REGS_UNALLOCATED; 3648 regs->num_regs = 0; 3649 regs->start = regs->end = (regoff_t *) 0; 3650 } 3651 } 3652 3653 /* Searching routines. */ 3654 3655 /* Like re_search_2, below, but only one string is specified, and 3656 doesn't let you say where to stop matching. */ 3657 3658 int 3659 re_search (bufp, string, size, startpos, range, regs) 3660 struct re_pattern_buffer *bufp; 3661 const char *string; 3662 int size, startpos, range; 3663 struct re_registers *regs; 3664 { 3665 return re_search_2 (bufp, NULL, 0, string, size, startpos, range, 3666 regs, size); 3667 } 3668 3669 /* End address of virtual concatenation of string. */ 3670 #define STOP_ADDR_VSTRING(P) \ 3671 (((P) >= size1 ? string2 + size2 : string1 + size1)) 3672 3673 /* Address of POS in the concatenation of virtual string. */ 3674 #define POS_ADDR_VSTRING(POS) \ 3675 (((POS) >= size1 ? string2 - size1 : string1) + (POS)) 3676 3677 /* Using the compiled pattern in BUFP->buffer, first tries to match the 3678 virtual concatenation of STRING1 and STRING2, starting first at index 3679 STARTPOS, then at STARTPOS + 1, and so on. 3680 3681 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively. 3682 3683 RANGE is how far to scan while trying to match. RANGE = 0 means try 3684 only at STARTPOS; in general, the last start tried is STARTPOS + 3685 RANGE. 3686 3687 In REGS, return the indices of the virtual concatenation of STRING1 3688 and STRING2 that matched the entire BUFP->buffer and its contained 3689 subexpressions. 3690 3691 Do not consider matching one past the index STOP in the virtual 3692 concatenation of STRING1 and STRING2. 3693 3694 We return either the position in the strings at which the match was 3695 found, -1 if no match, or -2 if error (such as failure 3696 stack overflow). */ 3697 3698 int 3699 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop) 3700 struct re_pattern_buffer *bufp; 3701 const char *string1, *string2; 3702 int size1, size2; 3703 int startpos; 3704 int range; 3705 struct re_registers *regs; 3706 int stop; 3707 { 3708 int val; 3709 register char *fastmap = bufp->fastmap; 3710 register RE_TRANSLATE_TYPE translate = bufp->translate; 3711 int total_size = size1 + size2; 3712 int endpos = startpos + range; 3713 int anchored_start = 0; 3714 3715 /* Nonzero if we have to concern multibyte character. */ 3716 int multibyte = bufp->multibyte; 3717 3718 /* Check for out-of-range STARTPOS. */ 3719 if (startpos < 0 || startpos > total_size) 3720 return -1; 3721 3722 /* Fix up RANGE if it might eventually take us outside 3723 the virtual concatenation of STRING1 and STRING2. 3724 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */ 3725 if (endpos < 0) 3726 range = 0 - startpos; 3727 else if (endpos > total_size) 3728 range = total_size - startpos; 3729 3730 /* If the search isn't to be a backwards one, don't waste time in a 3731 search for a pattern anchored at beginning of buffer. */ 3732 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == begbuf && range > 0) 3733 { 3734 if (startpos > 0) 3735 return -1; 3736 else 3737 range = 0; 3738 } 3739 3740 #ifdef emacs 3741 /* In a forward search for something that starts with \=. 3742 don't keep searching past point. */ 3743 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0) 3744 { 3745 range = PT_BYTE - BEGV_BYTE - startpos; 3746 if (range < 0) 3747 return -1; 3748 } 3749 #endif /* emacs */ 3750 3751 /* Update the fastmap now if not correct already. */ 3752 if (fastmap && !bufp->fastmap_accurate) 3753 if (re_compile_fastmap (bufp) == -2) 3754 return -2; 3755 3756 /* See whether the pattern is anchored. */ 3757 if (bufp->buffer[0] == begline) 3758 anchored_start = 1; 3759 3760 #ifdef emacs 3761 gl_state.object = re_match_object; 3762 { 3763 int adjpos = NILP (re_match_object) || BUFFERP (re_match_object); 3764 int charpos = SYNTAX_TABLE_BYTE_TO_CHAR (startpos + adjpos); 3765 3766 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1); 3767 } 3768 #endif 3769 3770 /* Loop through the string, looking for a place to start matching. */ 3771 for (;;) 3772 { 3773 /* If the pattern is anchored, 3774 skip quickly past places we cannot match. 3775 We don't bother to treat startpos == 0 specially 3776 because that case doesn't repeat. */ 3777 if (anchored_start && startpos > 0) 3778 { 3779 if (! (bufp->newline_anchor 3780 && ((startpos <= size1 ? string1[startpos - 1] 3781 : string2[startpos - size1 - 1]) 3782 == '\n'))) 3783 goto advance; 3784 } 3785 3786 /* If a fastmap is supplied, skip quickly over characters that 3787 cannot be the start of a match. If the pattern can match the 3788 null string, however, we don't need to skip characters; we want 3789 the first null string. */ 3790 if (fastmap && startpos < total_size && !bufp->can_be_null) 3791 { 3792 register const char *d; 3793 register unsigned int buf_ch; 3794 3795 d = POS_ADDR_VSTRING (startpos); 3796 3797 if (range > 0) /* Searching forwards. */ 3798 { 3799 register int lim = 0; 3800 int irange = range; 3801 3802 if (startpos < size1 && startpos + range >= size1) 3803 lim = range - (size1 - startpos); 3804 3805 /* Written out as an if-else to avoid testing `translate' 3806 inside the loop. */ 3807 if (RE_TRANSLATE_P (translate)) 3808 { 3809 if (multibyte) 3810 while (range > lim) 3811 { 3812 int buf_charlen; 3813 3814 buf_ch = STRING_CHAR_AND_LENGTH (d, range - lim, 3815 buf_charlen); 3816 3817 buf_ch = RE_TRANSLATE (translate, buf_ch); 3818 if (buf_ch >= 0400 3819 || fastmap[buf_ch]) 3820 break; 3821 3822 range -= buf_charlen; 3823 d += buf_charlen; 3824 } 3825 else 3826 while (range > lim 3827 && !fastmap[(unsigned char) 3828 RE_TRANSLATE (translate, (unsigned char) *d)]) 3829 { 3830 d++; 3831 range--; 3832 } 3833 } 3834 else 3835 while (range > lim && !fastmap[(unsigned char) *d]) 3836 { 3837 d++; 3838 range--; 3839 } 3840 3841 startpos += irange - range; 3842 } 3843 else /* Searching backwards. */ 3844 { 3845 int room = (size1 == 0 || startpos >= size1 3846 ? size2 + size1 - startpos 3847 : size1 - startpos); 3848 3849 buf_ch = STRING_CHAR (d, room); 3850 if (RE_TRANSLATE_P (translate)) 3851 buf_ch = RE_TRANSLATE (translate, buf_ch); 3852 3853 if (! (buf_ch >= 0400 3854 || fastmap[buf_ch])) 3855 goto advance; 3856 } 3857 } 3858 3859 /* If can't match the null string, and that's all we have left, fail. */ 3860 if (range >= 0 && startpos == total_size && fastmap 3861 && !bufp->can_be_null) 3862 return -1; 3863 3864 val = re_match_2_internal (bufp, string1, size1, string2, size2, 3865 startpos, regs, stop); 3866 #ifndef REGEX_MALLOC 3867 #ifdef C_ALLOCA 3868 alloca (0); 3869 #endif 3870 #endif 3871 3872 if (val >= 0) 3873 return startpos; 3874 3875 if (val == -2) 3876 return -2; 3877 3878 advance: 3879 if (!range) 3880 break; 3881 else if (range > 0) 3882 { 3883 /* Update STARTPOS to the next character boundary. */ 3884 if (multibyte) 3885 { 3886 const unsigned char *p 3887 = (const unsigned char *) POS_ADDR_VSTRING (startpos); 3888 const unsigned char *pend 3889 = (const unsigned char *) STOP_ADDR_VSTRING (startpos); 3890 int len = MULTIBYTE_FORM_LENGTH (p, pend - p); 3891 3892 range -= len; 3893 if (range < 0) 3894 break; 3895 startpos += len; 3896 } 3897 else 3898 { 3899 range--; 3900 startpos++; 3901 } 3902 } 3903 else 3904 { 3905 range++; 3906 startpos--; 3907 3908 /* Update STARTPOS to the previous character boundary. */ 3909 if (multibyte) 3910 { 3911 const unsigned char *p 3912 = (const unsigned char *) POS_ADDR_VSTRING (startpos); 3913 int len = 0; 3914 3915 /* Find the head of multibyte form. */ 3916 while (!CHAR_HEAD_P (*p)) 3917 p--, len++; 3918 3919 /* Adjust it. */ 3920 #if 0 /* XXX */ 3921 if (MULTIBYTE_FORM_LENGTH (p, len + 1) != (len + 1)) 3922 ; 3923 else 3924 #endif 3925 { 3926 range += len; 3927 if (range > 0) 3928 break; 3929 3930 startpos -= len; 3931 } 3932 } 3933 } 3934 } 3935 return -1; 3936 } /* re_search_2 */ 3937 3938 /* Declarations and macros for re_match_2. */ 3939 3940 static int bcmp_translate (); 3941 static boolean alt_match_null_string_p (), 3942 common_op_match_null_string_p (), 3943 group_match_null_string_p (); 3944 3945 /* This converts PTR, a pointer into one of the search strings `string1' 3946 and `string2' into an offset from the beginning of that string. */ 3947 #define POINTER_TO_OFFSET(ptr) \ 3948 (FIRST_STRING_P (ptr) \ 3949 ? ((regoff_t) ((ptr) - string1)) \ 3950 : ((regoff_t) ((ptr) - string2 + size1))) 3951 3952 /* Macros for dealing with the split strings in re_match_2. */ 3953 3954 #define MATCHING_IN_FIRST_STRING (dend == end_match_1) 3955 3956 /* Call before fetching a character with *d. This switches over to 3957 string2 if necessary. */ 3958 #define PREFETCH() \ 3959 while (d == dend) \ 3960 { \ 3961 /* End of string2 => fail. */ \ 3962 if (dend == end_match_2) \ 3963 goto fail; \ 3964 /* End of string1 => advance to string2. */ \ 3965 d = string2; \ 3966 dend = end_match_2; \ 3967 } 3968 3969 3970 /* Test if at very beginning or at very end of the virtual concatenation 3971 of `string1' and `string2'. If only one string, it's `string2'. */ 3972 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2) 3973 #define AT_STRINGS_END(d) ((d) == end2) 3974 3975 3976 /* Test if D points to a character which is word-constituent. We have 3977 two special cases to check for: if past the end of string1, look at 3978 the first character in string2; and if before the beginning of 3979 string2, look at the last character in string1. */ 3980 #define WORDCHAR_P(d) \ 3981 (SYNTAX ((d) == end1 ? *string2 \ 3982 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \ 3983 == Sword) 3984 3985 /* Disabled due to a compiler bug -- see comment at case wordbound */ 3986 3987 /* The comment at case wordbound is following one, but we don't use 3988 AT_WORD_BOUNDARY anymore to support multibyte form. 3989 3990 The DEC Alpha C compiler 3.x generates incorrect code for the 3991 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of 3992 AT_WORD_BOUNDARY, so this code is disabled. Expanding the 3993 macro and introducing temporary variables works around the bug. */ 3994 3995 #if 0 3996 /* Test if the character before D and the one at D differ with respect 3997 to being word-constituent. */ 3998 #define AT_WORD_BOUNDARY(d) \ 3999 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \ 4000 || WORDCHAR_P (d - 1) != WORDCHAR_P (d)) 4001 #endif 4002 4003 /* Free everything we malloc. */ 4004 #ifdef MATCH_MAY_ALLOCATE 4005 #define FREE_VAR(var) if (var) { REGEX_FREE (var); var = NULL; } else 4006 #define FREE_VARIABLES() \ 4007 do { \ 4008 REGEX_FREE_STACK (fail_stack.stack); \ 4009 FREE_VAR (regstart); \ 4010 FREE_VAR (regend); \ 4011 FREE_VAR (old_regstart); \ 4012 FREE_VAR (old_regend); \ 4013 FREE_VAR (best_regstart); \ 4014 FREE_VAR (best_regend); \ 4015 FREE_VAR (reg_info); \ 4016 FREE_VAR (reg_dummy); \ 4017 FREE_VAR (reg_info_dummy); \ 4018 } while (0) 4019 #else 4020 #define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */ 4021 #endif /* not MATCH_MAY_ALLOCATE */ 4022 4023 /* These values must meet several constraints. They must not be valid 4024 register values; since we have a limit of 255 registers (because 4025 we use only one byte in the pattern for the register number), we can 4026 use numbers larger than 255. They must differ by 1, because of 4027 NUM_FAILURE_ITEMS above. And the value for the lowest register must 4028 be larger than the value for the highest register, so we do not try 4029 to actually save any registers when none are active. */ 4030 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH) 4031 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1) 4032 4033 /* Matching routines. */ 4034 4035 #ifndef emacs /* Emacs never uses this. */ 4036 /* re_match is like re_match_2 except it takes only a single string. */ 4037 4038 int 4039 re_match (bufp, string, size, pos, regs) 4040 struct re_pattern_buffer *bufp; 4041 const char *string; 4042 int size, pos; 4043 struct re_registers *regs; 4044 { 4045 int result = re_match_2_internal (bufp, NULL, 0, string, size, 4046 pos, regs, size); 4047 #ifndef REGEX_MALLOC /* CVS */ 4048 #ifdef C_ALLOCA /* CVS */ 4049 alloca (0); 4050 #endif /* CVS */ 4051 #endif /* CVS */ 4052 return result; 4053 } 4054 #endif /* not emacs */ 4055 4056 #ifdef emacs 4057 /* In Emacs, this is the string or buffer in which we 4058 are matching. It is used for looking up syntax properties. */ 4059 Lisp_Object re_match_object; 4060 #endif 4061 4062 /* re_match_2 matches the compiled pattern in BUFP against the 4063 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1 4064 and SIZE2, respectively). We start matching at POS, and stop 4065 matching at STOP. 4066 4067 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we 4068 store offsets for the substring each group matched in REGS. See the 4069 documentation for exactly how many groups we fill. 4070 4071 We return -1 if no match, -2 if an internal error (such as the 4072 failure stack overflowing). Otherwise, we return the length of the 4073 matched substring. */ 4074 4075 int 4076 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop) 4077 struct re_pattern_buffer *bufp; 4078 const char *string1, *string2; 4079 int size1, size2; 4080 int pos; 4081 struct re_registers *regs; 4082 int stop; 4083 { 4084 int result; 4085 4086 #ifdef emacs 4087 int charpos; 4088 int adjpos = NILP (re_match_object) || BUFFERP (re_match_object); 4089 gl_state.object = re_match_object; 4090 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos + adjpos); 4091 SETUP_SYNTAX_TABLE_FOR_OBJECT (re_match_object, charpos, 1); 4092 #endif 4093 4094 result = re_match_2_internal (bufp, string1, size1, string2, size2, 4095 pos, regs, stop); 4096 #ifndef REGEX_MALLOC /* CVS */ 4097 #ifdef C_ALLOCA /* CVS */ 4098 alloca (0); 4099 #endif /* CVS */ 4100 #endif /* CVS */ 4101 return result; 4102 } 4103 4104 /* This is a separate function so that we can force an alloca cleanup 4105 afterwards. */ 4106 static int 4107 re_match_2_internal (bufp, string1, size1, string2, size2, pos, regs, stop) 4108 struct re_pattern_buffer *bufp; 4109 const char *string1, *string2; 4110 int size1, size2; 4111 int pos; 4112 struct re_registers *regs; 4113 int stop; 4114 { 4115 /* General temporaries. */ 4116 int mcnt; 4117 unsigned char *p1; 4118 4119 /* Just past the end of the corresponding string. */ 4120 const char *end1, *end2; 4121 4122 /* Pointers into string1 and string2, just past the last characters in 4123 each to consider matching. */ 4124 const char *end_match_1, *end_match_2; 4125 4126 /* Where we are in the data, and the end of the current string. */ 4127 const char *d, *dend; 4128 4129 /* Where we are in the pattern, and the end of the pattern. */ 4130 unsigned char *p = bufp->buffer; 4131 register unsigned char *pend = p + bufp->used; 4132 4133 /* Mark the opcode just after a start_memory, so we can test for an 4134 empty subpattern when we get to the stop_memory. */ 4135 unsigned char *just_past_start_mem = 0; 4136 4137 /* We use this to map every character in the string. */ 4138 RE_TRANSLATE_TYPE translate = bufp->translate; 4139 4140 /* Nonzero if we have to concern multibyte character. */ 4141 int multibyte = bufp->multibyte; 4142 4143 /* Failure point stack. Each place that can handle a failure further 4144 down the line pushes a failure point on this stack. It consists of 4145 restart, regend, and reg_info for all registers corresponding to 4146 the subexpressions we're currently inside, plus the number of such 4147 registers, and, finally, two char *'s. The first char * is where 4148 to resume scanning the pattern; the second one is where to resume 4149 scanning the strings. If the latter is zero, the failure point is 4150 a ``dummy''; if a failure happens and the failure point is a dummy, 4151 it gets discarded and the next next one is tried. */ 4152 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */ 4153 fail_stack_type fail_stack; 4154 #endif 4155 #ifdef DEBUG 4156 static unsigned failure_id = 0; 4157 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0; 4158 #endif 4159 4160 /* This holds the pointer to the failure stack, when 4161 it is allocated relocatably. */ 4162 fail_stack_elt_t *failure_stack_ptr; 4163 4164 /* We fill all the registers internally, independent of what we 4165 return, for use in backreferences. The number here includes 4166 an element for register zero. */ 4167 unsigned num_regs = bufp->re_nsub + 1; 4168 4169 /* The currently active registers. */ 4170 unsigned lowest_active_reg = NO_LOWEST_ACTIVE_REG; 4171 unsigned highest_active_reg = NO_HIGHEST_ACTIVE_REG; 4172 4173 /* Information on the contents of registers. These are pointers into 4174 the input strings; they record just what was matched (on this 4175 attempt) by a subexpression part of the pattern, that is, the 4176 regnum-th regstart pointer points to where in the pattern we began 4177 matching and the regnum-th regend points to right after where we 4178 stopped matching the regnum-th subexpression. (The zeroth register 4179 keeps track of what the whole pattern matches.) */ 4180 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */ 4181 const char **regstart, **regend; 4182 #endif 4183 4184 /* If a group that's operated upon by a repetition operator fails to 4185 match anything, then the register for its start will need to be 4186 restored because it will have been set to wherever in the string we 4187 are when we last see its open-group operator. Similarly for a 4188 register's end. */ 4189 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */ 4190 const char **old_regstart, **old_regend; 4191 #endif 4192 4193 /* The is_active field of reg_info helps us keep track of which (possibly 4194 nested) subexpressions we are currently in. The matched_something 4195 field of reg_info[reg_num] helps us tell whether or not we have 4196 matched any of the pattern so far this time through the reg_num-th 4197 subexpression. These two fields get reset each time through any 4198 loop their register is in. */ 4199 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */ 4200 register_info_type *reg_info; 4201 #endif 4202 4203 /* The following record the register info as found in the above 4204 variables when we find a match better than any we've seen before. 4205 This happens as we backtrack through the failure points, which in 4206 turn happens only if we have not yet matched the entire string. */ 4207 unsigned best_regs_set = false; 4208 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */ 4209 const char **best_regstart, **best_regend; 4210 #endif 4211 4212 /* Logically, this is `best_regend[0]'. But we don't want to have to 4213 allocate space for that if we're not allocating space for anything 4214 else (see below). Also, we never need info about register 0 for 4215 any of the other register vectors, and it seems rather a kludge to 4216 treat `best_regend' differently than the rest. So we keep track of 4217 the end of the best match so far in a separate variable. We 4218 initialize this to NULL so that when we backtrack the first time 4219 and need to test it, it's not garbage. */ 4220 const char *match_end = NULL; 4221 4222 /* This helps SET_REGS_MATCHED avoid doing redundant work. */ 4223 int set_regs_matched_done = 0; 4224 4225 /* Used when we pop values we don't care about. */ 4226 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */ 4227 const char **reg_dummy; 4228 register_info_type *reg_info_dummy; 4229 #endif 4230 4231 #ifdef DEBUG 4232 /* Counts the total number of registers pushed. */ 4233 unsigned num_regs_pushed = 0; 4234 #endif 4235 4236 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n"); 4237 4238 INIT_FAIL_STACK (); 4239 4240 #ifdef MATCH_MAY_ALLOCATE 4241 /* Do not bother to initialize all the register variables if there are 4242 no groups in the pattern, as it takes a fair amount of time. If 4243 there are groups, we include space for register 0 (the whole 4244 pattern), even though we never use it, since it simplifies the 4245 array indexing. We should fix this. */ 4246 if (bufp->re_nsub) 4247 { 4248 regstart = REGEX_TALLOC (num_regs, const char *); 4249 regend = REGEX_TALLOC (num_regs, const char *); 4250 old_regstart = REGEX_TALLOC (num_regs, const char *); 4251 old_regend = REGEX_TALLOC (num_regs, const char *); 4252 best_regstart = REGEX_TALLOC (num_regs, const char *); 4253 best_regend = REGEX_TALLOC (num_regs, const char *); 4254 reg_info = REGEX_TALLOC (num_regs, register_info_type); 4255 reg_dummy = REGEX_TALLOC (num_regs, const char *); 4256 reg_info_dummy = REGEX_TALLOC (num_regs, register_info_type); 4257 4258 if (!(regstart && regend && old_regstart && old_regend && reg_info 4259 && best_regstart && best_regend && reg_dummy && reg_info_dummy)) 4260 { 4261 FREE_VARIABLES (); 4262 return -2; 4263 } 4264 } 4265 else 4266 { 4267 /* We must initialize all our variables to NULL, so that 4268 `FREE_VARIABLES' doesn't try to free them. */ 4269 regstart = regend = old_regstart = old_regend = best_regstart 4270 = best_regend = reg_dummy = NULL; 4271 reg_info = reg_info_dummy = (register_info_type *) NULL; 4272 } 4273 #endif /* MATCH_MAY_ALLOCATE */ 4274 4275 /* The starting position is bogus. */ 4276 if (pos < 0 || pos > size1 + size2) 4277 { 4278 FREE_VARIABLES (); 4279 return -1; 4280 } 4281 4282 /* Initialize subexpression text positions to -1 to mark ones that no 4283 start_memory/stop_memory has been seen for. Also initialize the 4284 register information struct. */ 4285 for (mcnt = 1; mcnt < num_regs; mcnt++) 4286 { 4287 regstart[mcnt] = regend[mcnt] 4288 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE; 4289 4290 REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE; 4291 IS_ACTIVE (reg_info[mcnt]) = 0; 4292 MATCHED_SOMETHING (reg_info[mcnt]) = 0; 4293 EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0; 4294 } 4295 4296 /* We move `string1' into `string2' if the latter's empty -- but not if 4297 `string1' is null. */ 4298 if (size2 == 0 && string1 != NULL) 4299 { 4300 string2 = string1; 4301 size2 = size1; 4302 string1 = 0; 4303 size1 = 0; 4304 } 4305 end1 = string1 + size1; 4306 end2 = string2 + size2; 4307 4308 /* Compute where to stop matching, within the two strings. */ 4309 if (stop <= size1) 4310 { 4311 end_match_1 = string1 + stop; 4312 end_match_2 = string2; 4313 } 4314 else 4315 { 4316 end_match_1 = end1; 4317 end_match_2 = string2 + stop - size1; 4318 } 4319 4320 /* `p' scans through the pattern as `d' scans through the data. 4321 `dend' is the end of the input string that `d' points within. `d' 4322 is advanced into the following input string whenever necessary, but 4323 this happens before fetching; therefore, at the beginning of the 4324 loop, `d' can be pointing at the end of a string, but it cannot 4325 equal `string2'. */ 4326 if (size1 > 0 && pos <= size1) 4327 { 4328 d = string1 + pos; 4329 dend = end_match_1; 4330 } 4331 else 4332 { 4333 d = string2 + pos - size1; 4334 dend = end_match_2; 4335 } 4336 4337 DEBUG_PRINT1 ("The compiled pattern is: "); 4338 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend); 4339 DEBUG_PRINT1 ("The string to match is: `"); 4340 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2); 4341 DEBUG_PRINT1 ("'\n"); 4342 4343 /* This loops over pattern commands. It exits by returning from the 4344 function if the match is complete, or it drops through if the match 4345 fails at this starting point in the input data. */ 4346 for (;;) 4347 { 4348 DEBUG_PRINT2 ("\n0x%x: ", p); 4349 4350 if (p == pend) 4351 { /* End of pattern means we might have succeeded. */ 4352 DEBUG_PRINT1 ("end of pattern ... "); 4353 4354 /* If we haven't matched the entire string, and we want the 4355 longest match, try backtracking. */ 4356 if (d != end_match_2) 4357 { 4358 /* 1 if this match ends in the same string (string1 or string2) 4359 as the best previous match. */ 4360 boolean same_str_p = (FIRST_STRING_P (match_end) 4361 == MATCHING_IN_FIRST_STRING); 4362 /* 1 if this match is the best seen so far. */ 4363 boolean best_match_p; 4364 4365 /* AIX compiler got confused when this was combined 4366 with the previous declaration. */ 4367 if (same_str_p) 4368 best_match_p = d > match_end; 4369 else 4370 best_match_p = !MATCHING_IN_FIRST_STRING; 4371 4372 DEBUG_PRINT1 ("backtracking.\n"); 4373 4374 if (!FAIL_STACK_EMPTY ()) 4375 { /* More failure points to try. */ 4376 4377 /* If exceeds best match so far, save it. */ 4378 if (!best_regs_set || best_match_p) 4379 { 4380 best_regs_set = true; 4381 match_end = d; 4382 4383 DEBUG_PRINT1 ("\nSAVING match as best so far.\n"); 4384 4385 for (mcnt = 1; mcnt < num_regs; mcnt++) 4386 { 4387 best_regstart[mcnt] = regstart[mcnt]; 4388 best_regend[mcnt] = regend[mcnt]; 4389 } 4390 } 4391 goto fail; 4392 } 4393 4394 /* If no failure points, don't restore garbage. And if 4395 last match is real best match, don't restore second 4396 best one. */ 4397 else if (best_regs_set && !best_match_p) 4398 { 4399 restore_best_regs: 4400 /* Restore best match. It may happen that `dend == 4401 end_match_1' while the restored d is in string2. 4402 For example, the pattern `x.*y.*z' against the 4403 strings `x-' and `y-z-', if the two strings are 4404 not consecutive in memory. */ 4405 DEBUG_PRINT1 ("Restoring best registers.\n"); 4406 4407 d = match_end; 4408 dend = ((d >= string1 && d <= end1) 4409 ? end_match_1 : end_match_2); 4410 4411 for (mcnt = 1; mcnt < num_regs; mcnt++) 4412 { 4413 regstart[mcnt] = best_regstart[mcnt]; 4414 regend[mcnt] = best_regend[mcnt]; 4415 } 4416 } 4417 } /* d != end_match_2 */ 4418 4419 succeed_label: 4420 DEBUG_PRINT1 ("Accepting match.\n"); 4421 4422 /* If caller wants register contents data back, do it. */ 4423 if (regs && !bufp->no_sub) 4424 { 4425 /* Have the register data arrays been allocated? */ 4426 if (bufp->regs_allocated == REGS_UNALLOCATED) 4427 { /* No. So allocate them with malloc. We need one 4428 extra element beyond `num_regs' for the `-1' marker 4429 GNU code uses. */ 4430 regs->num_regs = MAX (RE_NREGS, num_regs + 1); 4431 regs->start = TALLOC (regs->num_regs, regoff_t); 4432 regs->end = TALLOC (regs->num_regs, regoff_t); 4433 if (regs->start == NULL || regs->end == NULL) 4434 { 4435 FREE_VARIABLES (); 4436 return -2; 4437 } 4438 bufp->regs_allocated = REGS_REALLOCATE; 4439 } 4440 else if (bufp->regs_allocated == REGS_REALLOCATE) 4441 { /* Yes. If we need more elements than were already 4442 allocated, reallocate them. If we need fewer, just 4443 leave it alone. */ 4444 if (regs->num_regs < num_regs + 1) 4445 { 4446 regs->num_regs = num_regs + 1; 4447 RETALLOC (regs->start, regs->num_regs, regoff_t); 4448 RETALLOC (regs->end, regs->num_regs, regoff_t); 4449 if (regs->start == NULL || regs->end == NULL) 4450 { 4451 FREE_VARIABLES (); 4452 return -2; 4453 } 4454 } 4455 } 4456 else 4457 { 4458 /* These braces fend off a "empty body in an else-statement" 4459 warning under GCC when assert expands to nothing. */ 4460 assert (bufp->regs_allocated == REGS_FIXED); 4461 } 4462 4463 /* Convert the pointer data in `regstart' and `regend' to 4464 indices. Register zero has to be set differently, 4465 since we haven't kept track of any info for it. */ 4466 if (regs->num_regs > 0) 4467 { 4468 regs->start[0] = pos; 4469 regs->end[0] = (MATCHING_IN_FIRST_STRING 4470 ? ((regoff_t) (d - string1)) 4471 : ((regoff_t) (d - string2 + size1))); 4472 } 4473 4474 /* Go through the first `min (num_regs, regs->num_regs)' 4475 registers, since that is all we initialized. */ 4476 for (mcnt = 1; mcnt < MIN (num_regs, regs->num_regs); mcnt++) 4477 { 4478 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt])) 4479 regs->start[mcnt] = regs->end[mcnt] = -1; 4480 else 4481 { 4482 regs->start[mcnt] 4483 = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]); 4484 regs->end[mcnt] 4485 = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]); 4486 } 4487 } 4488 4489 /* If the regs structure we return has more elements than 4490 were in the pattern, set the extra elements to -1. If 4491 we (re)allocated the registers, this is the case, 4492 because we always allocate enough to have at least one 4493 -1 at the end. */ 4494 for (mcnt = num_regs; mcnt < regs->num_regs; mcnt++) 4495 regs->start[mcnt] = regs->end[mcnt] = -1; 4496 } /* regs && !bufp->no_sub */ 4497 4498 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n", 4499 nfailure_points_pushed, nfailure_points_popped, 4500 nfailure_points_pushed - nfailure_points_popped); 4501 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed); 4502 4503 mcnt = d - pos - (MATCHING_IN_FIRST_STRING 4504 ? string1 4505 : string2 - size1); 4506 4507 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt); 4508 4509 FREE_VARIABLES (); 4510 return mcnt; 4511 } 4512 4513 /* Otherwise match next pattern command. */ 4514 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++)) 4515 { 4516 /* Ignore these. Used to ignore the n of succeed_n's which 4517 currently have n == 0. */ 4518 case no_op: 4519 DEBUG_PRINT1 ("EXECUTING no_op.\n"); 4520 break; 4521 4522 case succeed: 4523 DEBUG_PRINT1 ("EXECUTING succeed.\n"); 4524 goto succeed_label; 4525 4526 /* Match the next n pattern characters exactly. The following 4527 byte in the pattern defines n, and the n bytes after that 4528 are the characters to match. */ 4529 case exactn: 4530 mcnt = *p++; 4531 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt); 4532 4533 /* This is written out as an if-else so we don't waste time 4534 testing `translate' inside the loop. */ 4535 if (RE_TRANSLATE_P (translate)) 4536 { 4537 #ifdef emacs 4538 if (multibyte) 4539 do 4540 { 4541 int pat_charlen, buf_charlen; 4542 unsigned int pat_ch, buf_ch; 4543 4544 PREFETCH (); 4545 pat_ch = STRING_CHAR_AND_LENGTH (p, pend - p, pat_charlen); 4546 buf_ch = STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen); 4547 4548 if (RE_TRANSLATE (translate, buf_ch) 4549 != pat_ch) 4550 goto fail; 4551 4552 p += pat_charlen; 4553 d += buf_charlen; 4554 mcnt -= pat_charlen; 4555 } 4556 while (mcnt > 0); 4557 else 4558 #endif /* not emacs */ 4559 do 4560 { 4561 PREFETCH (); 4562 if ((unsigned char) RE_TRANSLATE (translate, (unsigned char) *d) 4563 != (unsigned char) *p++) 4564 goto fail; 4565 d++; 4566 } 4567 while (--mcnt); 4568 } 4569 else 4570 { 4571 do 4572 { 4573 PREFETCH (); 4574 if (*d++ != (char) *p++) goto fail; 4575 } 4576 while (--mcnt); 4577 } 4578 SET_REGS_MATCHED (); 4579 break; 4580 4581 4582 /* Match any character except possibly a newline or a null. */ 4583 case anychar: 4584 { 4585 int buf_charlen; 4586 unsigned int buf_ch; 4587 4588 DEBUG_PRINT1 ("EXECUTING anychar.\n"); 4589 4590 PREFETCH (); 4591 4592 #ifdef emacs 4593 if (multibyte) 4594 buf_ch = STRING_CHAR_AND_LENGTH (d, dend - d, buf_charlen); 4595 else 4596 #endif /* not emacs */ 4597 { 4598 buf_ch = (unsigned char) *d; 4599 buf_charlen = 1; 4600 } 4601 4602 buf_ch = TRANSLATE (buf_ch); 4603 4604 if ((!(bufp->syntax & RE_DOT_NEWLINE) 4605 && buf_ch == '\n') 4606 || ((bufp->syntax & RE_DOT_NOT_NULL) 4607 && buf_ch == '\000')) 4608 goto fail; 4609 4610 SET_REGS_MATCHED (); 4611 DEBUG_PRINT2 (" Matched `%d'.\n", *d); 4612 d += buf_charlen; 4613 } 4614 break; 4615 4616 4617 case charset: 4618 case charset_not: 4619 { 4620 register unsigned int c; 4621 boolean not = (re_opcode_t) *(p - 1) == charset_not; 4622 int len; 4623 4624 /* Start of actual range_table, or end of bitmap if there is no 4625 range table. */ 4626 unsigned char *range_table; 4627 4628 /* Nonzero if there is range table. */ 4629 int range_table_exists; 4630 4631 /* Number of ranges of range table. Not in bytes. */ 4632 int count; 4633 4634 DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : ""); 4635 4636 PREFETCH (); 4637 c = (unsigned char) *d; 4638 4639 range_table = CHARSET_RANGE_TABLE (&p[-1]); /* Past the bitmap. */ 4640 range_table_exists = CHARSET_RANGE_TABLE_EXISTS_P (&p[-1]); 4641 if (range_table_exists) 4642 EXTRACT_NUMBER_AND_INCR (count, range_table); 4643 else 4644 count = 0; 4645 4646 if (multibyte && BASE_LEADING_CODE_P (c)) 4647 c = STRING_CHAR_AND_LENGTH (d, dend - d, len); 4648 4649 if (SINGLE_BYTE_CHAR_P (c)) 4650 { /* Lookup bitmap. */ 4651 c = TRANSLATE (c); /* The character to match. */ 4652 len = 1; 4653 4654 /* Cast to `unsigned' instead of `unsigned char' in 4655 case the bit list is a full 32 bytes long. */ 4656 if (c < (unsigned) (CHARSET_BITMAP_SIZE (&p[-1]) * BYTEWIDTH) 4657 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) 4658 not = !not; 4659 } 4660 else if (range_table_exists) 4661 CHARSET_LOOKUP_RANGE_TABLE_RAW (not, c, range_table, count); 4662 4663 p = CHARSET_RANGE_TABLE_END (range_table, count); 4664 4665 if (!not) goto fail; 4666 4667 SET_REGS_MATCHED (); 4668 d += len; 4669 break; 4670 } 4671 4672 4673 /* The beginning of a group is represented by start_memory. 4674 The arguments are the register number in the next byte, and the 4675 number of groups inner to this one in the next. The text 4676 matched within the group is recorded (in the internal 4677 registers data structure) under the register number. */ 4678 case start_memory: 4679 DEBUG_PRINT3 ("EXECUTING start_memory %d (%d):\n", *p, p[1]); 4680 4681 /* Find out if this group can match the empty string. */ 4682 p1 = p; /* To send to group_match_null_string_p. */ 4683 4684 if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE) 4685 REG_MATCH_NULL_STRING_P (reg_info[*p]) 4686 = group_match_null_string_p (&p1, pend, reg_info); 4687 4688 /* Save the position in the string where we were the last time 4689 we were at this open-group operator in case the group is 4690 operated upon by a repetition operator, e.g., with `(a*)*b' 4691 against `ab'; then we want to ignore where we are now in 4692 the string in case this attempt to match fails. */ 4693 old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p]) 4694 ? REG_UNSET (regstart[*p]) ? d : regstart[*p] 4695 : regstart[*p]; 4696 DEBUG_PRINT2 (" old_regstart: %d\n", 4697 POINTER_TO_OFFSET (old_regstart[*p])); 4698 4699 regstart[*p] = d; 4700 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p])); 4701 4702 IS_ACTIVE (reg_info[*p]) = 1; 4703 MATCHED_SOMETHING (reg_info[*p]) = 0; 4704 4705 /* Clear this whenever we change the register activity status. */ 4706 set_regs_matched_done = 0; 4707 4708 /* This is the new highest active register. */ 4709 highest_active_reg = *p; 4710 4711 /* If nothing was active before, this is the new lowest active 4712 register. */ 4713 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG) 4714 lowest_active_reg = *p; 4715 4716 /* Move past the register number and inner group count. */ 4717 p += 2; 4718 just_past_start_mem = p; 4719 4720 break; 4721 4722 4723 /* The stop_memory opcode represents the end of a group. Its 4724 arguments are the same as start_memory's: the register 4725 number, and the number of inner groups. */ 4726 case stop_memory: 4727 DEBUG_PRINT3 ("EXECUTING stop_memory %d (%d):\n", *p, p[1]); 4728 4729 /* We need to save the string position the last time we were at 4730 this close-group operator in case the group is operated 4731 upon by a repetition operator, e.g., with `((a*)*(b*)*)*' 4732 against `aba'; then we want to ignore where we are now in 4733 the string in case this attempt to match fails. */ 4734 old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p]) 4735 ? REG_UNSET (regend[*p]) ? d : regend[*p] 4736 : regend[*p]; 4737 DEBUG_PRINT2 (" old_regend: %d\n", 4738 POINTER_TO_OFFSET (old_regend[*p])); 4739 4740 regend[*p] = d; 4741 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p])); 4742 4743 /* This register isn't active anymore. */ 4744 IS_ACTIVE (reg_info[*p]) = 0; 4745 4746 /* Clear this whenever we change the register activity status. */ 4747 set_regs_matched_done = 0; 4748 4749 /* If this was the only register active, nothing is active 4750 anymore. */ 4751 if (lowest_active_reg == highest_active_reg) 4752 { 4753 lowest_active_reg = NO_LOWEST_ACTIVE_REG; 4754 highest_active_reg = NO_HIGHEST_ACTIVE_REG; 4755 } 4756 else 4757 { /* We must scan for the new highest active register, since 4758 it isn't necessarily one less than now: consider 4759 (a(b)c(d(e)f)g). When group 3 ends, after the f), the 4760 new highest active register is 1. */ 4761 unsigned char r = *p - 1; 4762 while (r > 0 && !IS_ACTIVE (reg_info[r])) 4763 r--; 4764 4765 /* If we end up at register zero, that means that we saved 4766 the registers as the result of an `on_failure_jump', not 4767 a `start_memory', and we jumped to past the innermost 4768 `stop_memory'. For example, in ((.)*) we save 4769 registers 1 and 2 as a result of the *, but when we pop 4770 back to the second ), we are at the stop_memory 1. 4771 Thus, nothing is active. */ 4772 if (r == 0) 4773 { 4774 lowest_active_reg = NO_LOWEST_ACTIVE_REG; 4775 highest_active_reg = NO_HIGHEST_ACTIVE_REG; 4776 } 4777 else 4778 highest_active_reg = r; 4779 } 4780 4781 /* If just failed to match something this time around with a 4782 group that's operated on by a repetition operator, try to 4783 force exit from the ``loop'', and restore the register 4784 information for this group that we had before trying this 4785 last match. */ 4786 if ((!MATCHED_SOMETHING (reg_info[*p]) 4787 || just_past_start_mem == p - 1) 4788 && (p + 2) < pend) 4789 { 4790 boolean is_a_jump_n = false; 4791 4792 p1 = p + 2; 4793 mcnt = 0; 4794 switch ((re_opcode_t) *p1++) 4795 { 4796 case jump_n: 4797 is_a_jump_n = true; 4798 case pop_failure_jump: 4799 case maybe_pop_jump: 4800 case jump: 4801 case dummy_failure_jump: 4802 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 4803 if (is_a_jump_n) 4804 p1 += 2; 4805 break; 4806 4807 default: 4808 /* do nothing */ ; 4809 } 4810 p1 += mcnt; 4811 4812 /* If the next operation is a jump backwards in the pattern 4813 to an on_failure_jump right before the start_memory 4814 corresponding to this stop_memory, exit from the loop 4815 by forcing a failure after pushing on the stack the 4816 on_failure_jump's jump in the pattern, and d. */ 4817 if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump 4818 && (re_opcode_t) p1[3] == start_memory && p1[4] == *p) 4819 { 4820 /* If this group ever matched anything, then restore 4821 what its registers were before trying this last 4822 failed match, e.g., with `(a*)*b' against `ab' for 4823 regstart[1], and, e.g., with `((a*)*(b*)*)*' 4824 against `aba' for regend[3]. 4825 4826 Also restore the registers for inner groups for, 4827 e.g., `((a*)(b*))*' against `aba' (register 3 would 4828 otherwise get trashed). */ 4829 4830 if (EVER_MATCHED_SOMETHING (reg_info[*p])) 4831 { 4832 unsigned r; 4833 4834 EVER_MATCHED_SOMETHING (reg_info[*p]) = 0; 4835 4836 /* Restore this and inner groups' (if any) registers. */ 4837 for (r = *p; r < *p + *(p + 1); r++) 4838 { 4839 regstart[r] = old_regstart[r]; 4840 4841 /* xx why this test? */ 4842 if (old_regend[r] >= regstart[r]) 4843 regend[r] = old_regend[r]; 4844 } 4845 } 4846 p1++; 4847 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 4848 PUSH_FAILURE_POINT (p1 + mcnt, d, -2); 4849 4850 goto fail; 4851 } 4852 } 4853 4854 /* Move past the register number and the inner group count. */ 4855 p += 2; 4856 break; 4857 4858 4859 /* \<digit> has been turned into a `duplicate' command which is 4860 followed by the numeric value of <digit> as the register number. */ 4861 case duplicate: 4862 { 4863 register const char *d2, *dend2; 4864 int regno = *p++; /* Get which register to match against. */ 4865 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno); 4866 4867 /* Can't back reference a group which we've never matched. */ 4868 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno])) 4869 goto fail; 4870 4871 /* Where in input to try to start matching. */ 4872 d2 = regstart[regno]; 4873 4874 /* Where to stop matching; if both the place to start and 4875 the place to stop matching are in the same string, then 4876 set to the place to stop, otherwise, for now have to use 4877 the end of the first string. */ 4878 4879 dend2 = ((FIRST_STRING_P (regstart[regno]) 4880 == FIRST_STRING_P (regend[regno])) 4881 ? regend[regno] : end_match_1); 4882 for (;;) 4883 { 4884 /* If necessary, advance to next segment in register 4885 contents. */ 4886 while (d2 == dend2) 4887 { 4888 if (dend2 == end_match_2) break; 4889 if (dend2 == regend[regno]) break; 4890 4891 /* End of string1 => advance to string2. */ 4892 d2 = string2; 4893 dend2 = regend[regno]; 4894 } 4895 /* At end of register contents => success */ 4896 if (d2 == dend2) break; 4897 4898 /* If necessary, advance to next segment in data. */ 4899 PREFETCH (); 4900 4901 /* How many characters left in this segment to match. */ 4902 mcnt = dend - d; 4903 4904 /* Want how many consecutive characters we can match in 4905 one shot, so, if necessary, adjust the count. */ 4906 if (mcnt > dend2 - d2) 4907 mcnt = dend2 - d2; 4908 4909 /* Compare that many; failure if mismatch, else move 4910 past them. */ 4911 if (RE_TRANSLATE_P (translate) 4912 ? bcmp_translate (d, d2, mcnt, translate) 4913 : bcmp (d, d2, mcnt)) 4914 goto fail; 4915 d += mcnt, d2 += mcnt; 4916 4917 /* Do this because we've match some characters. */ 4918 SET_REGS_MATCHED (); 4919 } 4920 } 4921 break; 4922 4923 4924 /* begline matches the empty string at the beginning of the string 4925 (unless `not_bol' is set in `bufp'), and, if 4926 `newline_anchor' is set, after newlines. */ 4927 case begline: 4928 DEBUG_PRINT1 ("EXECUTING begline.\n"); 4929 4930 if (AT_STRINGS_BEG (d)) 4931 { 4932 if (!bufp->not_bol) break; 4933 } 4934 else if (d[-1] == '\n' && bufp->newline_anchor) 4935 { 4936 break; 4937 } 4938 /* In all other cases, we fail. */ 4939 goto fail; 4940 4941 4942 /* endline is the dual of begline. */ 4943 case endline: 4944 DEBUG_PRINT1 ("EXECUTING endline.\n"); 4945 4946 if (AT_STRINGS_END (d)) 4947 { 4948 if (!bufp->not_eol) break; 4949 } 4950 4951 /* We have to ``prefetch'' the next character. */ 4952 else if ((d == end1 ? *string2 : *d) == '\n' 4953 && bufp->newline_anchor) 4954 { 4955 break; 4956 } 4957 goto fail; 4958 4959 4960 /* Match at the very beginning of the data. */ 4961 case begbuf: 4962 DEBUG_PRINT1 ("EXECUTING begbuf.\n"); 4963 if (AT_STRINGS_BEG (d)) 4964 break; 4965 goto fail; 4966 4967 4968 /* Match at the very end of the data. */ 4969 case endbuf: 4970 DEBUG_PRINT1 ("EXECUTING endbuf.\n"); 4971 if (AT_STRINGS_END (d)) 4972 break; 4973 goto fail; 4974 4975 4976 /* on_failure_keep_string_jump is used to optimize `.*\n'. It 4977 pushes NULL as the value for the string on the stack. Then 4978 `pop_failure_point' will keep the current value for the 4979 string, instead of restoring it. To see why, consider 4980 matching `foo\nbar' against `.*\n'. The .* matches the foo; 4981 then the . fails against the \n. But the next thing we want 4982 to do is match the \n against the \n; if we restored the 4983 string value, we would be back at the foo. 4984 4985 Because this is used only in specific cases, we don't need to 4986 check all the things that `on_failure_jump' does, to make 4987 sure the right things get saved on the stack. Hence we don't 4988 share its code. The only reason to push anything on the 4989 stack at all is that otherwise we would have to change 4990 `anychar's code to do something besides goto fail in this 4991 case; that seems worse than this. */ 4992 case on_failure_keep_string_jump: 4993 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump"); 4994 4995 EXTRACT_NUMBER_AND_INCR (mcnt, p); 4996 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt); 4997 4998 PUSH_FAILURE_POINT (p + mcnt, NULL, -2); 4999 break; 5000 5001 5002 /* Uses of on_failure_jump: 5003 5004 Each alternative starts with an on_failure_jump that points 5005 to the beginning of the next alternative. Each alternative 5006 except the last ends with a jump that in effect jumps past 5007 the rest of the alternatives. (They really jump to the 5008 ending jump of the following alternative, because tensioning 5009 these jumps is a hassle.) 5010 5011 Repeats start with an on_failure_jump that points past both 5012 the repetition text and either the following jump or 5013 pop_failure_jump back to this on_failure_jump. */ 5014 case on_failure_jump: 5015 on_failure: 5016 DEBUG_PRINT1 ("EXECUTING on_failure_jump"); 5017 5018 #if defined (WINDOWSNT) && defined (emacs) 5019 QUIT; 5020 #endif 5021 5022 EXTRACT_NUMBER_AND_INCR (mcnt, p); 5023 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt); 5024 5025 /* If this on_failure_jump comes right before a group (i.e., 5026 the original * applied to a group), save the information 5027 for that group and all inner ones, so that if we fail back 5028 to this point, the group's information will be correct. 5029 For example, in \(a*\)*\1, we need the preceding group, 5030 and in \(zz\(a*\)b*\)\2, we need the inner group. */ 5031 5032 /* We can't use `p' to check ahead because we push 5033 a failure point to `p + mcnt' after we do this. */ 5034 p1 = p; 5035 5036 /* We need to skip no_op's before we look for the 5037 start_memory in case this on_failure_jump is happening as 5038 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1 5039 against aba. */ 5040 while (p1 < pend && (re_opcode_t) *p1 == no_op) 5041 p1++; 5042 5043 if (p1 < pend && (re_opcode_t) *p1 == start_memory) 5044 { 5045 /* We have a new highest active register now. This will 5046 get reset at the start_memory we are about to get to, 5047 but we will have saved all the registers relevant to 5048 this repetition op, as described above. */ 5049 highest_active_reg = *(p1 + 1) + *(p1 + 2); 5050 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG) 5051 lowest_active_reg = *(p1 + 1); 5052 } 5053 5054 DEBUG_PRINT1 (":\n"); 5055 PUSH_FAILURE_POINT (p + mcnt, d, -2); 5056 break; 5057 5058 5059 /* A smart repeat ends with `maybe_pop_jump'. 5060 We change it to either `pop_failure_jump' or `jump'. */ 5061 case maybe_pop_jump: 5062 #if defined (WINDOWSNT) && defined (emacs) 5063 QUIT; 5064 #endif 5065 EXTRACT_NUMBER_AND_INCR (mcnt, p); 5066 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt); 5067 { 5068 register unsigned char *p2 = p; 5069 5070 /* Compare the beginning of the repeat with what in the 5071 pattern follows its end. If we can establish that there 5072 is nothing that they would both match, i.e., that we 5073 would have to backtrack because of (as in, e.g., `a*a') 5074 then we can change to pop_failure_jump, because we'll 5075 never have to backtrack. 5076 5077 This is not true in the case of alternatives: in 5078 `(a|ab)*' we do need to backtrack to the `ab' alternative 5079 (e.g., if the string was `ab'). But instead of trying to 5080 detect that here, the alternative has put on a dummy 5081 failure point which is what we will end up popping. */ 5082 5083 /* Skip over open/close-group commands. 5084 If what follows this loop is a ...+ construct, 5085 look at what begins its body, since we will have to 5086 match at least one of that. */ 5087 while (1) 5088 { 5089 if (p2 + 2 < pend 5090 && ((re_opcode_t) *p2 == stop_memory 5091 || (re_opcode_t) *p2 == start_memory)) 5092 p2 += 3; 5093 else if (p2 + 6 < pend 5094 && (re_opcode_t) *p2 == dummy_failure_jump) 5095 p2 += 6; 5096 else 5097 break; 5098 } 5099 5100 p1 = p + mcnt; 5101 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding 5102 to the `maybe_finalize_jump' of this case. Examine what 5103 follows. */ 5104 5105 /* If we're at the end of the pattern, we can change. */ 5106 if (p2 == pend) 5107 { 5108 /* Consider what happens when matching ":\(.*\)" 5109 against ":/". I don't really understand this code 5110 yet. */ 5111 p[-3] = (unsigned char) pop_failure_jump; 5112 DEBUG_PRINT1 5113 (" End of pattern: change to `pop_failure_jump'.\n"); 5114 } 5115 5116 else if ((re_opcode_t) *p2 == exactn 5117 || (bufp->newline_anchor && (re_opcode_t) *p2 == endline)) 5118 { 5119 register unsigned int c 5120 = *p2 == (unsigned char) endline ? '\n' : p2[2]; 5121 5122 if ((re_opcode_t) p1[3] == exactn) 5123 { 5124 if (!(multibyte /* && (c != '\n') */ 5125 && BASE_LEADING_CODE_P (c)) 5126 ? c != p1[5] 5127 : (STRING_CHAR (&p2[2], pend - &p2[2]) 5128 != STRING_CHAR (&p1[5], pend - &p1[5]))) 5129 { 5130 p[-3] = (unsigned char) pop_failure_jump; 5131 DEBUG_PRINT3 (" %c != %c => pop_failure_jump.\n", 5132 c, p1[5]); 5133 } 5134 } 5135 5136 else if ((re_opcode_t) p1[3] == charset 5137 || (re_opcode_t) p1[3] == charset_not) 5138 { 5139 int not = (re_opcode_t) p1[3] == charset_not; 5140 5141 if (multibyte /* && (c != '\n') */ 5142 && BASE_LEADING_CODE_P (c)) 5143 c = STRING_CHAR (&p2[2], pend - &p2[2]); 5144 5145 /* Test if C is listed in charset (or charset_not) 5146 at `&p1[3]'. */ 5147 if (SINGLE_BYTE_CHAR_P (c)) 5148 { 5149 if (c < CHARSET_BITMAP_SIZE (&p1[3]) * BYTEWIDTH 5150 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH))) 5151 not = !not; 5152 } 5153 else if (CHARSET_RANGE_TABLE_EXISTS_P (&p1[3])) 5154 CHARSET_LOOKUP_RANGE_TABLE (not, c, &p1[3]); 5155 5156 /* `not' is equal to 1 if c would match, which means 5157 that we can't change to pop_failure_jump. */ 5158 if (!not) 5159 { 5160 p[-3] = (unsigned char) pop_failure_jump; 5161 DEBUG_PRINT1 (" No match => pop_failure_jump.\n"); 5162 } 5163 } 5164 } 5165 else if ((re_opcode_t) *p2 == charset) 5166 { 5167 if ((re_opcode_t) p1[3] == exactn) 5168 { 5169 register unsigned int c = p1[5]; 5170 int not = 0; 5171 5172 if (multibyte && BASE_LEADING_CODE_P (c)) 5173 c = STRING_CHAR (&p1[5], pend - &p1[5]); 5174 5175 /* Test if C is listed in charset at `p2'. */ 5176 if (SINGLE_BYTE_CHAR_P (c)) 5177 { 5178 if (c < CHARSET_BITMAP_SIZE (p2) * BYTEWIDTH 5179 && (p2[2 + c / BYTEWIDTH] 5180 & (1 << (c % BYTEWIDTH)))) 5181 not = !not; 5182 } 5183 else if (CHARSET_RANGE_TABLE_EXISTS_P (p2)) 5184 CHARSET_LOOKUP_RANGE_TABLE (not, c, p2); 5185 5186 if (!not) 5187 { 5188 p[-3] = (unsigned char) pop_failure_jump; 5189 DEBUG_PRINT1 (" No match => pop_failure_jump.\n"); 5190 } 5191 } 5192 5193 /* It is hard to list up all the character in charset 5194 P2 if it includes multibyte character. Give up in 5195 such case. */ 5196 else if (!multibyte || !CHARSET_RANGE_TABLE_EXISTS_P (p2)) 5197 { 5198 /* Now, we are sure that P2 has no range table. 5199 So, for the size of bitmap in P2, `p2[1]' is 5200 enough. But P1 may have range table, so the 5201 size of bitmap table of P1 is extracted by 5202 using macro `CHARSET_BITMAP_SIZE'. 5203 5204 Since we know that all the character listed in 5205 P2 is ASCII, it is enough to test only bitmap 5206 table of P1. */ 5207 5208 if ((re_opcode_t) p1[3] == charset_not) 5209 { 5210 int idx; 5211 /* We win if the charset_not inside the loop lists 5212 every character listed in the charset after. */ 5213 for (idx = 0; idx < (int) p2[1]; idx++) 5214 if (! (p2[2 + idx] == 0 5215 || (idx < CHARSET_BITMAP_SIZE (&p1[3]) 5216 && ((p2[2 + idx] & ~ p1[5 + idx]) == 0)))) 5217 break; 5218 5219 if (idx == p2[1]) 5220 { 5221 p[-3] = (unsigned char) pop_failure_jump; 5222 DEBUG_PRINT1 (" No match => pop_failure_jump.\n"); 5223 } 5224 } 5225 else if ((re_opcode_t) p1[3] == charset) 5226 { 5227 int idx; 5228 /* We win if the charset inside the loop 5229 has no overlap with the one after the loop. */ 5230 for (idx = 0; 5231 (idx < (int) p2[1] 5232 && idx < CHARSET_BITMAP_SIZE (&p1[3])); 5233 idx++) 5234 if ((p2[2 + idx] & p1[5 + idx]) != 0) 5235 break; 5236 5237 if (idx == p2[1] 5238 || idx == CHARSET_BITMAP_SIZE (&p1[3])) 5239 { 5240 p[-3] = (unsigned char) pop_failure_jump; 5241 DEBUG_PRINT1 (" No match => pop_failure_jump.\n"); 5242 } 5243 } 5244 } 5245 } 5246 } 5247 p -= 2; /* Point at relative address again. */ 5248 if ((re_opcode_t) p[-1] != pop_failure_jump) 5249 { 5250 p[-1] = (unsigned char) jump; 5251 DEBUG_PRINT1 (" Match => jump.\n"); 5252 goto unconditional_jump; 5253 } 5254 /* Note fall through. */ 5255 5256 5257 /* The end of a simple repeat has a pop_failure_jump back to 5258 its matching on_failure_jump, where the latter will push a 5259 failure point. The pop_failure_jump takes off failure 5260 points put on by this pop_failure_jump's matching 5261 on_failure_jump; we got through the pattern to here from the 5262 matching on_failure_jump, so didn't fail. */ 5263 case pop_failure_jump: 5264 { 5265 /* We need to pass separate storage for the lowest and 5266 highest registers, even though we don't care about the 5267 actual values. Otherwise, we will restore only one 5268 register from the stack, since lowest will == highest in 5269 `pop_failure_point'. */ 5270 unsigned dummy_low_reg, dummy_high_reg; 5271 unsigned char *pdummy; 5272 const char *sdummy; 5273 5274 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n"); 5275 POP_FAILURE_POINT (sdummy, pdummy, 5276 dummy_low_reg, dummy_high_reg, 5277 reg_dummy, reg_dummy, reg_info_dummy); 5278 } 5279 /* Note fall through. */ 5280 5281 5282 /* Unconditionally jump (without popping any failure points). */ 5283 case jump: 5284 unconditional_jump: 5285 #if defined (WINDOWSNT) && defined (emacs) 5286 QUIT; 5287 #endif 5288 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */ 5289 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt); 5290 p += mcnt; /* Do the jump. */ 5291 DEBUG_PRINT2 ("(to 0x%x).\n", p); 5292 break; 5293 5294 5295 /* We need this opcode so we can detect where alternatives end 5296 in `group_match_null_string_p' et al. */ 5297 case jump_past_alt: 5298 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n"); 5299 goto unconditional_jump; 5300 5301 5302 /* Normally, the on_failure_jump pushes a failure point, which 5303 then gets popped at pop_failure_jump. We will end up at 5304 pop_failure_jump, also, and with a pattern of, say, `a+', we 5305 are skipping over the on_failure_jump, so we have to push 5306 something meaningless for pop_failure_jump to pop. */ 5307 case dummy_failure_jump: 5308 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n"); 5309 /* It doesn't matter what we push for the string here. What 5310 the code at `fail' tests is the value for the pattern. */ 5311 PUSH_FAILURE_POINT (0, 0, -2); 5312 goto unconditional_jump; 5313 5314 5315 /* At the end of an alternative, we need to push a dummy failure 5316 point in case we are followed by a `pop_failure_jump', because 5317 we don't want the failure point for the alternative to be 5318 popped. For example, matching `(a|ab)*' against `aab' 5319 requires that we match the `ab' alternative. */ 5320 case push_dummy_failure: 5321 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n"); 5322 /* See comments just above at `dummy_failure_jump' about the 5323 two zeroes. */ 5324 PUSH_FAILURE_POINT (0, 0, -2); 5325 break; 5326 5327 /* Have to succeed matching what follows at least n times. 5328 After that, handle like `on_failure_jump'. */ 5329 case succeed_n: 5330 EXTRACT_NUMBER (mcnt, p + 2); 5331 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt); 5332 5333 assert (mcnt >= 0); 5334 /* Originally, this is how many times we HAVE to succeed. */ 5335 if (mcnt > 0) 5336 { 5337 mcnt--; 5338 p += 2; 5339 STORE_NUMBER_AND_INCR (p, mcnt); 5340 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p, mcnt); 5341 } 5342 else if (mcnt == 0) 5343 { 5344 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n", p+2); 5345 p[2] = (unsigned char) no_op; 5346 p[3] = (unsigned char) no_op; 5347 goto on_failure; 5348 } 5349 break; 5350 5351 case jump_n: 5352 EXTRACT_NUMBER (mcnt, p + 2); 5353 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt); 5354 5355 /* Originally, this is how many times we CAN jump. */ 5356 if (mcnt) 5357 { 5358 mcnt--; 5359 STORE_NUMBER (p + 2, mcnt); 5360 goto unconditional_jump; 5361 } 5362 /* If don't have to jump any more, skip over the rest of command. */ 5363 else 5364 p += 4; 5365 break; 5366 5367 case set_number_at: 5368 { 5369 DEBUG_PRINT1 ("EXECUTING set_number_at.\n"); 5370 5371 EXTRACT_NUMBER_AND_INCR (mcnt, p); 5372 p1 = p + mcnt; 5373 EXTRACT_NUMBER_AND_INCR (mcnt, p); 5374 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1, mcnt); 5375 STORE_NUMBER (p1, mcnt); 5376 break; 5377 } 5378 5379 case wordbound: 5380 DEBUG_PRINT1 ("EXECUTING wordbound.\n"); 5381 5382 /* We SUCCEED in one of the following cases: */ 5383 5384 /* Case 1: D is at the beginning or the end of string. */ 5385 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d)) 5386 break; 5387 else 5388 { 5389 /* C1 is the character before D, S1 is the syntax of C1, C2 5390 is the character at D, and S2 is the syntax of C2. */ 5391 int c1, c2, s1, s2; 5392 int pos1 = PTR_TO_OFFSET (d - 1); 5393 int charpos; 5394 5395 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2); 5396 GET_CHAR_AFTER_2 (c2, d, string1, end1, string2, end2); 5397 #ifdef emacs 5398 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1); 5399 UPDATE_SYNTAX_TABLE (charpos); 5400 #endif 5401 s1 = SYNTAX (c1); 5402 #ifdef emacs 5403 UPDATE_SYNTAX_TABLE_FORWARD (charpos + 1); 5404 #endif 5405 s2 = SYNTAX (c2); 5406 5407 if (/* Case 2: Only one of S1 and S2 is Sword. */ 5408 ((s1 == Sword) != (s2 == Sword)) 5409 /* Case 3: Both of S1 and S2 are Sword, and macro 5410 WORD_BOUNDARY_P (C1, C2) returns nonzero. */ 5411 || ((s1 == Sword) && WORD_BOUNDARY_P (c1, c2))) 5412 break; 5413 } 5414 goto fail; 5415 5416 case notwordbound: 5417 DEBUG_PRINT1 ("EXECUTING notwordbound.\n"); 5418 5419 /* We FAIL in one of the following cases: */ 5420 5421 /* Case 1: D is at the beginning or the end of string. */ 5422 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d)) 5423 goto fail; 5424 else 5425 { 5426 /* C1 is the character before D, S1 is the syntax of C1, C2 5427 is the character at D, and S2 is the syntax of C2. */ 5428 int c1, c2, s1, s2; 5429 int pos1 = PTR_TO_OFFSET (d - 1); 5430 int charpos; 5431 5432 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2); 5433 GET_CHAR_AFTER_2 (c2, d, string1, end1, string2, end2); 5434 #ifdef emacs 5435 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1); 5436 UPDATE_SYNTAX_TABLE (charpos); 5437 #endif 5438 s1 = SYNTAX (c1); 5439 #ifdef emacs 5440 UPDATE_SYNTAX_TABLE_FORWARD (charpos + 1); 5441 #endif 5442 s2 = SYNTAX (c2); 5443 5444 if (/* Case 2: Only one of S1 and S2 is Sword. */ 5445 ((s1 == Sword) != (s2 == Sword)) 5446 /* Case 3: Both of S1 and S2 are Sword, and macro 5447 WORD_BOUNDARY_P (C1, C2) returns nonzero. */ 5448 || ((s1 == Sword) && WORD_BOUNDARY_P (c1, c2))) 5449 goto fail; 5450 } 5451 break; 5452 5453 case wordbeg: 5454 DEBUG_PRINT1 ("EXECUTING wordbeg.\n"); 5455 5456 /* We FAIL in one of the following cases: */ 5457 5458 /* Case 1: D is at the end of string. */ 5459 if (AT_STRINGS_END (d)) 5460 goto fail; 5461 else 5462 { 5463 /* C1 is the character before D, S1 is the syntax of C1, C2 5464 is the character at D, and S2 is the syntax of C2. */ 5465 int c1, c2, s1, s2; 5466 int pos1 = PTR_TO_OFFSET (d); 5467 int charpos; 5468 5469 GET_CHAR_AFTER_2 (c2, d, string1, end1, string2, end2); 5470 #ifdef emacs 5471 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1); 5472 UPDATE_SYNTAX_TABLE (charpos); 5473 #endif 5474 s2 = SYNTAX (c2); 5475 5476 /* Case 2: S2 is not Sword. */ 5477 if (s2 != Sword) 5478 goto fail; 5479 5480 /* Case 3: D is not at the beginning of string ... */ 5481 if (!AT_STRINGS_BEG (d)) 5482 { 5483 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2); 5484 #ifdef emacs 5485 UPDATE_SYNTAX_TABLE_BACKWARD (charpos - 1); 5486 #endif 5487 s1 = SYNTAX (c1); 5488 5489 /* ... and S1 is Sword, and WORD_BOUNDARY_P (C1, C2) 5490 returns 0. */ 5491 if ((s1 == Sword) && !WORD_BOUNDARY_P (c1, c2)) 5492 goto fail; 5493 } 5494 } 5495 break; 5496 5497 case wordend: 5498 DEBUG_PRINT1 ("EXECUTING wordend.\n"); 5499 5500 /* We FAIL in one of the following cases: */ 5501 5502 /* Case 1: D is at the beginning of string. */ 5503 if (AT_STRINGS_BEG (d)) 5504 goto fail; 5505 else 5506 { 5507 /* C1 is the character before D, S1 is the syntax of C1, C2 5508 is the character at D, and S2 is the syntax of C2. */ 5509 int c1, c2, s1, s2; 5510 int pos1 = PTR_TO_OFFSET (d); 5511 int charpos; 5512 5513 GET_CHAR_BEFORE_2 (c1, d, string1, end1, string2, end2); 5514 #ifdef emacs 5515 charpos = SYNTAX_TABLE_BYTE_TO_CHAR (pos1 - 1); 5516 UPDATE_SYNTAX_TABLE (charpos); 5517 #endif 5518 s1 = SYNTAX (c1); 5519 5520 /* Case 2: S1 is not Sword. */ 5521 if (s1 != Sword) 5522 goto fail; 5523 5524 /* Case 3: D is not at the end of string ... */ 5525 if (!AT_STRINGS_END (d)) 5526 { 5527 GET_CHAR_AFTER_2 (c2, d, string1, end1, string2, end2); 5528 #ifdef emacs 5529 UPDATE_SYNTAX_TABLE_FORWARD (charpos); 5530 #endif 5531 s2 = SYNTAX (c2); 5532 5533 /* ... and S2 is Sword, and WORD_BOUNDARY_P (C1, C2) 5534 returns 0. */ 5535 if ((s2 == Sword) && !WORD_BOUNDARY_P (c1, c2)) 5536 goto fail; 5537 } 5538 } 5539 break; 5540 5541 #ifdef emacs 5542 case before_dot: 5543 DEBUG_PRINT1 ("EXECUTING before_dot.\n"); 5544 if (PTR_BYTE_POS ((unsigned char *) d) >= PT_BYTE) 5545 goto fail; 5546 break; 5547 5548 case at_dot: 5549 DEBUG_PRINT1 ("EXECUTING at_dot.\n"); 5550 if (PTR_BYTE_POS ((unsigned char *) d) != PT_BYTE) 5551 goto fail; 5552 break; 5553 5554 case after_dot: 5555 DEBUG_PRINT1 ("EXECUTING after_dot.\n"); 5556 if (PTR_BYTE_POS ((unsigned char *) d) <= PT_BYTE) 5557 goto fail; 5558 break; 5559 5560 case syntaxspec: 5561 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt); 5562 mcnt = *p++; 5563 goto matchsyntax; 5564 5565 case wordchar: 5566 DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n"); 5567 mcnt = (int) Sword; 5568 matchsyntax: 5569 PREFETCH (); 5570 #ifdef emacs 5571 { 5572 int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (PTR_TO_OFFSET (d)); 5573 UPDATE_SYNTAX_TABLE (pos1); 5574 } 5575 #endif 5576 { 5577 int c, len; 5578 5579 if (multibyte) 5580 /* we must concern about multibyte form, ... */ 5581 c = STRING_CHAR_AND_LENGTH (d, dend - d, len); 5582 else 5583 /* everything should be handled as ASCII, even though it 5584 looks like multibyte form. */ 5585 c = *d, len = 1; 5586 5587 if (SYNTAX (c) != (enum syntaxcode) mcnt) 5588 goto fail; 5589 d += len; 5590 } 5591 SET_REGS_MATCHED (); 5592 break; 5593 5594 case notsyntaxspec: 5595 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt); 5596 mcnt = *p++; 5597 goto matchnotsyntax; 5598 5599 case notwordchar: 5600 DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n"); 5601 mcnt = (int) Sword; 5602 matchnotsyntax: 5603 PREFETCH (); 5604 #ifdef emacs 5605 { 5606 int pos1 = SYNTAX_TABLE_BYTE_TO_CHAR (PTR_TO_OFFSET (d)); 5607 UPDATE_SYNTAX_TABLE (pos1); 5608 } 5609 #endif 5610 { 5611 int c, len; 5612 5613 if (multibyte) 5614 c = STRING_CHAR_AND_LENGTH (d, dend - d, len); 5615 else 5616 c = *d, len = 1; 5617 5618 if (SYNTAX (c) == (enum syntaxcode) mcnt) 5619 goto fail; 5620 d += len; 5621 } 5622 SET_REGS_MATCHED (); 5623 break; 5624 5625 case categoryspec: 5626 DEBUG_PRINT2 ("EXECUTING categoryspec %d.\n", *p); 5627 mcnt = *p++; 5628 PREFETCH (); 5629 { 5630 int c, len; 5631 5632 if (multibyte) 5633 c = STRING_CHAR_AND_LENGTH (d, dend - d, len); 5634 else 5635 c = *d, len = 1; 5636 5637 if (!CHAR_HAS_CATEGORY (c, mcnt)) 5638 goto fail; 5639 d += len; 5640 } 5641 SET_REGS_MATCHED (); 5642 break; 5643 5644 case notcategoryspec: 5645 DEBUG_PRINT2 ("EXECUTING notcategoryspec %d.\n", *p); 5646 mcnt = *p++; 5647 PREFETCH (); 5648 { 5649 int c, len; 5650 5651 if (multibyte) 5652 c = STRING_CHAR_AND_LENGTH (d, dend - d, len); 5653 else 5654 c = *d, len = 1; 5655 5656 if (CHAR_HAS_CATEGORY (c, mcnt)) 5657 goto fail; 5658 d += len; 5659 } 5660 SET_REGS_MATCHED (); 5661 break; 5662 5663 #else /* not emacs */ 5664 case wordchar: 5665 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n"); 5666 PREFETCH (); 5667 if (!WORDCHAR_P (d)) 5668 goto fail; 5669 SET_REGS_MATCHED (); 5670 d++; 5671 break; 5672 5673 case notwordchar: 5674 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n"); 5675 PREFETCH (); 5676 if (WORDCHAR_P (d)) 5677 goto fail; 5678 SET_REGS_MATCHED (); 5679 d++; 5680 break; 5681 #endif /* not emacs */ 5682 5683 default: 5684 abort (); 5685 } 5686 continue; /* Successfully executed one pattern command; keep going. */ 5687 5688 5689 /* We goto here if a matching operation fails. */ 5690 fail: 5691 #if defined (WINDOWSNT) && defined (emacs) 5692 QUIT; 5693 #endif 5694 if (!FAIL_STACK_EMPTY ()) 5695 { /* A restart point is known. Restore to that state. */ 5696 DEBUG_PRINT1 ("\nFAIL:\n"); 5697 POP_FAILURE_POINT (d, p, 5698 lowest_active_reg, highest_active_reg, 5699 regstart, regend, reg_info); 5700 5701 /* If this failure point is a dummy, try the next one. */ 5702 if (!p) 5703 goto fail; 5704 5705 /* If we failed to the end of the pattern, don't examine *p. */ 5706 assert (p <= pend); 5707 if (p < pend) 5708 { 5709 boolean is_a_jump_n = false; 5710 5711 /* If failed to a backwards jump that's part of a repetition 5712 loop, need to pop this failure point and use the next one. */ 5713 switch ((re_opcode_t) *p) 5714 { 5715 case jump_n: 5716 is_a_jump_n = true; 5717 case maybe_pop_jump: 5718 case pop_failure_jump: 5719 case jump: 5720 p1 = p + 1; 5721 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5722 p1 += mcnt; 5723 5724 if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n) 5725 || (!is_a_jump_n 5726 && (re_opcode_t) *p1 == on_failure_jump)) 5727 goto fail; 5728 break; 5729 default: 5730 /* do nothing */ ; 5731 } 5732 } 5733 5734 if (d >= string1 && d <= end1) 5735 dend = end_match_1; 5736 } 5737 else 5738 break; /* Matching at this starting point really fails. */ 5739 } /* for (;;) */ 5740 5741 if (best_regs_set) 5742 goto restore_best_regs; 5743 5744 FREE_VARIABLES (); 5745 5746 return -1; /* Failure to match. */ 5747 } /* re_match_2 */ 5748 5749 /* Subroutine definitions for re_match_2. */ 5750 5751 5752 /* We are passed P pointing to a register number after a start_memory. 5753 5754 Return true if the pattern up to the corresponding stop_memory can 5755 match the empty string, and false otherwise. 5756 5757 If we find the matching stop_memory, sets P to point to one past its number. 5758 Otherwise, sets P to an undefined byte less than or equal to END. 5759 5760 We don't handle duplicates properly (yet). */ 5761 5762 static boolean 5763 group_match_null_string_p (p, end, reg_info) 5764 unsigned char **p, *end; 5765 register_info_type *reg_info; 5766 { 5767 int mcnt; 5768 /* Point to after the args to the start_memory. */ 5769 unsigned char *p1 = *p + 2; 5770 5771 while (p1 < end) 5772 { 5773 /* Skip over opcodes that can match nothing, and return true or 5774 false, as appropriate, when we get to one that can't, or to the 5775 matching stop_memory. */ 5776 5777 switch ((re_opcode_t) *p1) 5778 { 5779 /* Could be either a loop or a series of alternatives. */ 5780 case on_failure_jump: 5781 p1++; 5782 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5783 5784 /* If the next operation is not a jump backwards in the 5785 pattern. */ 5786 5787 if (mcnt >= 0) 5788 { 5789 /* Go through the on_failure_jumps of the alternatives, 5790 seeing if any of the alternatives cannot match nothing. 5791 The last alternative starts with only a jump, 5792 whereas the rest start with on_failure_jump and end 5793 with a jump, e.g., here is the pattern for `a|b|c': 5794 5795 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6 5796 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3 5797 /exactn/1/c 5798 5799 So, we have to first go through the first (n-1) 5800 alternatives and then deal with the last one separately. */ 5801 5802 5803 /* Deal with the first (n-1) alternatives, which start 5804 with an on_failure_jump (see above) that jumps to right 5805 past a jump_past_alt. */ 5806 5807 while ((re_opcode_t) p1[mcnt-3] == jump_past_alt) 5808 { 5809 /* `mcnt' holds how many bytes long the alternative 5810 is, including the ending `jump_past_alt' and 5811 its number. */ 5812 5813 if (!alt_match_null_string_p (p1, p1 + mcnt - 3, 5814 reg_info)) 5815 return false; 5816 5817 /* Move to right after this alternative, including the 5818 jump_past_alt. */ 5819 p1 += mcnt; 5820 5821 /* Break if it's the beginning of an n-th alternative 5822 that doesn't begin with an on_failure_jump. */ 5823 if ((re_opcode_t) *p1 != on_failure_jump) 5824 break; 5825 5826 /* Still have to check that it's not an n-th 5827 alternative that starts with an on_failure_jump. */ 5828 p1++; 5829 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5830 if ((re_opcode_t) p1[mcnt-3] != jump_past_alt) 5831 { 5832 /* Get to the beginning of the n-th alternative. */ 5833 p1 -= 3; 5834 break; 5835 } 5836 } 5837 5838 /* Deal with the last alternative: go back and get number 5839 of the `jump_past_alt' just before it. `mcnt' contains 5840 the length of the alternative. */ 5841 EXTRACT_NUMBER (mcnt, p1 - 2); 5842 5843 if (!alt_match_null_string_p (p1, p1 + mcnt, reg_info)) 5844 return false; 5845 5846 p1 += mcnt; /* Get past the n-th alternative. */ 5847 } /* if mcnt > 0 */ 5848 break; 5849 5850 5851 case stop_memory: 5852 assert (p1[1] == **p); 5853 *p = p1 + 2; 5854 return true; 5855 5856 5857 default: 5858 if (!common_op_match_null_string_p (&p1, end, reg_info)) 5859 return false; 5860 } 5861 } /* while p1 < end */ 5862 5863 return false; 5864 } /* group_match_null_string_p */ 5865 5866 5867 /* Similar to group_match_null_string_p, but doesn't deal with alternatives: 5868 It expects P to be the first byte of a single alternative and END one 5869 byte past the last. The alternative can contain groups. */ 5870 5871 static boolean 5872 alt_match_null_string_p (p, end, reg_info) 5873 unsigned char *p, *end; 5874 register_info_type *reg_info; 5875 { 5876 int mcnt; 5877 unsigned char *p1 = p; 5878 5879 while (p1 < end) 5880 { 5881 /* Skip over opcodes that can match nothing, and break when we get 5882 to one that can't. */ 5883 5884 switch ((re_opcode_t) *p1) 5885 { 5886 /* It's a loop. */ 5887 case on_failure_jump: 5888 p1++; 5889 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5890 p1 += mcnt; 5891 break; 5892 5893 default: 5894 if (!common_op_match_null_string_p (&p1, end, reg_info)) 5895 return false; 5896 } 5897 } /* while p1 < end */ 5898 5899 return true; 5900 } /* alt_match_null_string_p */ 5901 5902 5903 /* Deals with the ops common to group_match_null_string_p and 5904 alt_match_null_string_p. 5905 5906 Sets P to one after the op and its arguments, if any. */ 5907 5908 static boolean 5909 common_op_match_null_string_p (p, end, reg_info) 5910 unsigned char **p, *end; 5911 register_info_type *reg_info; 5912 { 5913 int mcnt; 5914 boolean ret; 5915 int reg_no; 5916 unsigned char *p1 = *p; 5917 5918 switch ((re_opcode_t) *p1++) 5919 { 5920 case no_op: 5921 case begline: 5922 case endline: 5923 case begbuf: 5924 case endbuf: 5925 case wordbeg: 5926 case wordend: 5927 case wordbound: 5928 case notwordbound: 5929 #ifdef emacs 5930 case before_dot: 5931 case at_dot: 5932 case after_dot: 5933 #endif 5934 break; 5935 5936 case start_memory: 5937 reg_no = *p1; 5938 assert (reg_no > 0 && reg_no <= MAX_REGNUM); 5939 ret = group_match_null_string_p (&p1, end, reg_info); 5940 5941 /* Have to set this here in case we're checking a group which 5942 contains a group and a back reference to it. */ 5943 5944 if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE) 5945 REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret; 5946 5947 if (!ret) 5948 return false; 5949 break; 5950 5951 /* If this is an optimized succeed_n for zero times, make the jump. */ 5952 case jump: 5953 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5954 if (mcnt >= 0) 5955 p1 += mcnt; 5956 else 5957 return false; 5958 break; 5959 5960 case succeed_n: 5961 /* Get to the number of times to succeed. */ 5962 p1 += 2; 5963 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5964 5965 if (mcnt == 0) 5966 { 5967 p1 -= 4; 5968 EXTRACT_NUMBER_AND_INCR (mcnt, p1); 5969 p1 += mcnt; 5970 } 5971 else 5972 return false; 5973 break; 5974 5975 case duplicate: 5976 if (!REG_MATCH_NULL_STRING_P (reg_info[*p1])) 5977 return false; 5978 break; 5979 5980 case set_number_at: 5981 p1 += 4; 5982 5983 default: 5984 /* All other opcodes mean we cannot match the empty string. */ 5985 return false; 5986 } 5987 5988 *p = p1; 5989 return true; 5990 } /* common_op_match_null_string_p */ 5991 5992 5993 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN 5994 bytes; nonzero otherwise. */ 5995 5996 static int 5997 bcmp_translate (s1, s2, len, translate) 5998 unsigned char *s1, *s2; 5999 register int len; 6000 RE_TRANSLATE_TYPE translate; 6001 { 6002 register unsigned char *p1 = s1, *p2 = s2; 6003 unsigned char *p1_end = s1 + len; 6004 unsigned char *p2_end = s2 + len; 6005 6006 while (p1 != p1_end && p2 != p2_end) 6007 { 6008 int p1_charlen, p2_charlen; 6009 int p1_ch, p2_ch; 6010 6011 p1_ch = STRING_CHAR_AND_LENGTH (p1, p1_end - p1, p1_charlen); 6012 p2_ch = STRING_CHAR_AND_LENGTH (p2, p2_end - p2, p2_charlen); 6013 6014 if (RE_TRANSLATE (translate, p1_ch) 6015 != RE_TRANSLATE (translate, p2_ch)) 6016 return 1; 6017 6018 p1 += p1_charlen, p2 += p2_charlen; 6019 } 6020 6021 if (p1 != p1_end || p2 != p2_end) 6022 return 1; 6023 6024 return 0; 6025 } 6026 6027 /* Entry points for GNU code. */ 6028 6029 /* re_compile_pattern is the GNU regular expression compiler: it 6030 compiles PATTERN (of length SIZE) and puts the result in BUFP. 6031 Returns 0 if the pattern was valid, otherwise an error string. 6032 6033 Assumes the `allocated' (and perhaps `buffer') and `translate' fields 6034 are set in BUFP on entry. 6035 6036 We call regex_compile to do the actual compilation. */ 6037 6038 const char * 6039 re_compile_pattern (pattern, length, bufp) 6040 const char *pattern; 6041 int length; 6042 struct re_pattern_buffer *bufp; 6043 { 6044 reg_errcode_t ret; 6045 6046 /* GNU code is written to assume at least RE_NREGS registers will be set 6047 (and at least one extra will be -1). */ 6048 bufp->regs_allocated = REGS_UNALLOCATED; 6049 6050 /* And GNU code determines whether or not to get register information 6051 by passing null for the REGS argument to re_match, etc., not by 6052 setting no_sub. */ 6053 bufp->no_sub = 0; 6054 6055 /* Match anchors at newline. */ 6056 bufp->newline_anchor = 1; 6057 6058 ret = regex_compile (pattern, length, re_syntax_options, bufp); 6059 6060 if (!ret) 6061 return NULL; 6062 return gettext (re_error_msgid[(int) ret]); 6063 } 6064 6065 /* Entry points compatible with 4.2 BSD regex library. We don't define 6066 them unless specifically requested. */ 6067 6068 #if defined (_REGEX_RE_COMP) || defined (_LIBC) 6069 6070 /* BSD has one and only one pattern buffer. */ 6071 static struct re_pattern_buffer re_comp_buf; 6072 6073 char * 6074 #ifdef _LIBC 6075 /* Make these definitions weak in libc, so POSIX programs can redefine 6076 these names if they don't use our functions, and still use 6077 regcomp/regexec below without link errors. */ 6078 weak_function 6079 #endif 6080 re_comp (s) 6081 const char *s; 6082 { 6083 reg_errcode_t ret; 6084 6085 if (!s) 6086 { 6087 if (!re_comp_buf.buffer) 6088 return gettext ("No previous regular expression"); 6089 return 0; 6090 } 6091 6092 if (!re_comp_buf.buffer) 6093 { 6094 re_comp_buf.buffer = (unsigned char *) malloc (200); 6095 if (re_comp_buf.buffer == NULL) 6096 /* CVS: Yes, we're discarding `const' here if !HAVE_LIBINTL. */ 6097 return (char *) gettext (re_error_msgid[(int) REG_ESPACE]); 6098 re_comp_buf.allocated = 200; 6099 6100 re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH); 6101 if (re_comp_buf.fastmap == NULL) 6102 /* CVS: Yes, we're discarding `const' here if !HAVE_LIBINTL. */ 6103 return (char *) gettext (re_error_msgid[(int) REG_ESPACE]); 6104 } 6105 6106 /* Since `re_exec' always passes NULL for the `regs' argument, we 6107 don't need to initialize the pattern buffer fields which affect it. */ 6108 6109 /* Match anchors at newlines. */ 6110 re_comp_buf.newline_anchor = 1; 6111 6112 ret = regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf); 6113 6114 if (!ret) 6115 return NULL; 6116 6117 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */ 6118 return (char *) gettext (re_error_msgid[(int) ret]); 6119 } 6120 6121 6122 int 6123 #ifdef _LIBC 6124 weak_function 6125 #endif 6126 re_exec (s) 6127 const char *s; 6128 { 6129 const int len = strlen (s); 6130 return 6131 0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0); 6132 } 6133 #endif /* _REGEX_RE_COMP */ 6134 6135 /* POSIX.2 functions. Don't define these for Emacs. */ 6136 6137 #ifndef emacs 6138 6139 /* regcomp takes a regular expression as a string and compiles it. 6140 6141 PREG is a regex_t *. We do not expect any fields to be initialized, 6142 since POSIX says we shouldn't. Thus, we set 6143 6144 `buffer' to the compiled pattern; 6145 `used' to the length of the compiled pattern; 6146 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the 6147 REG_EXTENDED bit in CFLAGS is set; otherwise, to 6148 RE_SYNTAX_POSIX_BASIC; 6149 `newline_anchor' to REG_NEWLINE being set in CFLAGS; 6150 `fastmap' and `fastmap_accurate' to zero; 6151 `re_nsub' to the number of subexpressions in PATTERN. 6152 6153 PATTERN is the address of the pattern string. 6154 6155 CFLAGS is a series of bits which affect compilation. 6156 6157 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we 6158 use POSIX basic syntax. 6159 6160 If REG_NEWLINE is set, then . and [^...] don't match newline. 6161 Also, regexec will try a match beginning after every newline. 6162 6163 If REG_ICASE is set, then we considers upper- and lowercase 6164 versions of letters to be equivalent when matching. 6165 6166 If REG_NOSUB is set, then when PREG is passed to regexec, that 6167 routine will report only success or failure, and nothing about the 6168 registers. 6169 6170 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for 6171 the return codes and their meanings.) */ 6172 6173 int 6174 regcomp (preg, pattern, cflags) 6175 regex_t *preg; 6176 const char *pattern; 6177 int cflags; 6178 { 6179 reg_errcode_t ret; 6180 unsigned syntax 6181 = (cflags & REG_EXTENDED) ? 6182 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC; 6183 6184 /* regex_compile will allocate the space for the compiled pattern. */ 6185 preg->buffer = 0; 6186 preg->allocated = 0; 6187 preg->used = 0; 6188 6189 /* Don't bother to use a fastmap when searching. This simplifies the 6190 REG_NEWLINE case: if we used a fastmap, we'd have to put all the 6191 characters after newlines into the fastmap. This way, we just try 6192 every character. */ 6193 preg->fastmap = 0; 6194 6195 if (cflags & REG_ICASE) 6196 { 6197 unsigned i; 6198 6199 preg->translate 6200 = (RE_TRANSLATE_TYPE) malloc (CHAR_SET_SIZE 6201 * sizeof (*(RE_TRANSLATE_TYPE)0)); 6202 if (preg->translate == NULL) 6203 return (int) REG_ESPACE; 6204 6205 /* Map uppercase characters to corresponding lowercase ones. */ 6206 for (i = 0; i < CHAR_SET_SIZE; i++) 6207 preg->translate[i] = ISUPPER (i) ? tolower (i) : i; 6208 } 6209 else 6210 preg->translate = NULL; 6211 6212 /* If REG_NEWLINE is set, newlines are treated differently. */ 6213 if (cflags & REG_NEWLINE) 6214 { /* REG_NEWLINE implies neither . nor [^...] match newline. */ 6215 syntax &= ~RE_DOT_NEWLINE; 6216 syntax |= RE_HAT_LISTS_NOT_NEWLINE; 6217 /* It also changes the matching behavior. */ 6218 preg->newline_anchor = 1; 6219 } 6220 else 6221 preg->newline_anchor = 0; 6222 6223 preg->no_sub = !!(cflags & REG_NOSUB); 6224 6225 /* POSIX says a null character in the pattern terminates it, so we 6226 can use strlen here in compiling the pattern. */ 6227 ret = regex_compile (pattern, strlen (pattern), syntax, preg); 6228 6229 /* POSIX doesn't distinguish between an unmatched open-group and an 6230 unmatched close-group: both are REG_EPAREN. */ 6231 if (ret == REG_ERPAREN) ret = REG_EPAREN; 6232 6233 return (int) ret; 6234 } 6235 6236 6237 /* regexec searches for a given pattern, specified by PREG, in the 6238 string STRING. 6239 6240 If NMATCH is zero or REG_NOSUB was set in the cflags argument to 6241 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at 6242 least NMATCH elements, and we set them to the offsets of the 6243 corresponding matched substrings. 6244 6245 EFLAGS specifies `execution flags' which affect matching: if 6246 REG_NOTBOL is set, then ^ does not match at the beginning of the 6247 string; if REG_NOTEOL is set, then $ does not match at the end. 6248 6249 We return 0 if we find a match and REG_NOMATCH if not. */ 6250 6251 int 6252 regexec (preg, string, nmatch, pmatch, eflags) 6253 const regex_t *preg; 6254 const char *string; 6255 size_t nmatch; 6256 regmatch_t pmatch[]; 6257 int eflags; 6258 { 6259 int ret; 6260 struct re_registers regs; 6261 regex_t private_preg; 6262 int len = strlen (string); 6263 boolean want_reg_info = !preg->no_sub && nmatch > 0; 6264 6265 private_preg = *preg; 6266 6267 private_preg.not_bol = !!(eflags & REG_NOTBOL); 6268 private_preg.not_eol = !!(eflags & REG_NOTEOL); 6269 6270 /* The user has told us exactly how many registers to return 6271 information about, via `nmatch'. We have to pass that on to the 6272 matching routines. */ 6273 private_preg.regs_allocated = REGS_FIXED; 6274 6275 if (want_reg_info) 6276 { 6277 regs.num_regs = nmatch; 6278 regs.start = TALLOC (nmatch, regoff_t); 6279 regs.end = TALLOC (nmatch, regoff_t); 6280 if (regs.start == NULL || regs.end == NULL) 6281 return (int) REG_NOMATCH; 6282 } 6283 6284 /* Perform the searching operation. */ 6285 ret = re_search (&private_preg, string, len, 6286 /* start: */ 0, /* range: */ len, 6287 want_reg_info ? ®s : (struct re_registers *) 0); 6288 6289 /* Copy the register information to the POSIX structure. */ 6290 if (want_reg_info) 6291 { 6292 if (ret >= 0) 6293 { 6294 unsigned r; 6295 6296 for (r = 0; r < nmatch; r++) 6297 { 6298 pmatch[r].rm_so = regs.start[r]; 6299 pmatch[r].rm_eo = regs.end[r]; 6300 } 6301 } 6302 6303 /* If we needed the temporary register info, free the space now. */ 6304 free (regs.start); 6305 free (regs.end); 6306 } 6307 6308 /* We want zero return to mean success, unlike `re_search'. */ 6309 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH; 6310 } 6311 6312 6313 /* Returns a message corresponding to an error code, ERRCODE, returned 6314 from either regcomp or regexec. We don't use PREG here. */ 6315 6316 size_t 6317 regerror (errcode, preg, errbuf, errbuf_size) 6318 int errcode; 6319 const regex_t *preg; 6320 char *errbuf; 6321 size_t errbuf_size; 6322 { 6323 const char *msg; 6324 size_t msg_size; 6325 6326 if (errcode < 0 6327 || errcode >= (sizeof (re_error_msgid) / sizeof (re_error_msgid[0]))) 6328 /* Only error codes returned by the rest of the code should be passed 6329 to this routine. If we are given anything else, or if other regex 6330 code generates an invalid error code, then the program has a bug. 6331 Dump core so we can fix it. */ 6332 abort (); 6333 6334 msg = gettext (re_error_msgid[errcode]); 6335 6336 msg_size = strlen (msg) + 1; /* Includes the null. */ 6337 6338 if (errbuf_size != 0) 6339 { 6340 if (msg_size > errbuf_size) 6341 { 6342 strncpy (errbuf, msg, errbuf_size - 1); 6343 errbuf[errbuf_size - 1] = 0; 6344 } 6345 else 6346 strcpy (errbuf, msg); 6347 } 6348 6349 return msg_size; 6350 } 6351 6352 6353 /* Free dynamically allocated space used by PREG. */ 6354 6355 void 6356 regfree (preg) 6357 regex_t *preg; 6358 { 6359 if (preg->buffer != NULL) 6360 free (preg->buffer); 6361 preg->buffer = NULL; 6362 6363 preg->allocated = 0; 6364 preg->used = 0; 6365 6366 if (preg->fastmap != NULL) 6367 free (preg->fastmap); 6368 preg->fastmap = NULL; 6369 preg->fastmap_accurate = 0; 6370 6371 if (preg->translate != NULL) 6372 free (preg->translate); 6373 preg->translate = NULL; 6374 } 6375 6376 #endif /* not emacs */ 6377