1 /* Extended regular expression matching and search library,
3 (Implements POSIX draft P1003.2/D11.2, except for some of the
4 internationalization features.)
5 Copyright (C) 1993-1999, 2000, 2001 Free Software Foundation, Inc.
6 This file is part of the GNU C Library.
8 The GNU C Library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU Lesser General Public
10 License as published by the Free Software Foundation; either
11 version 2.1 of the License, or (at your option) any later version.
13 The GNU C Library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 Lesser General Public License for more details.
18 You should have received a copy of the GNU Lesser General Public
19 License along with the GNU C Library; if not, write to the Free
20 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
24 #define memset __memset
25 #define memcmp __memcmp
26 #define strcmp __strcmp
27 #define strlen __strlen
28 #define wcslen __wcslen
29 /* for some reason this does not work */
30 #define memcpy __memcpy
31 #define mbrtowc __mbrtowc
32 #define wcrtomb __wcrtomb
33 #define wcscoll __wcscoll
34 #define wctype __wctype
35 #define iswctype __iswctype
36 #define iswalnum __iswalnum
37 #define printf __printf
39 /* To exclude some unwanted junk.... */
42 #define _REGEX_RE_COMP
47 #define RE_TRANSLATE_TYPE char *
49 extern void *__mempcpy (void *__restrict __dest,
50 __const void *__restrict __src, size_t __n) /*attribute_hidden*/;
52 /* AIX requires this to be the first thing in the file. */
53 #if defined _AIX && !defined REGEX_MALLOC
65 # if defined __GNUC__ || (defined __STDC__ && __STDC__)
66 # define PARAMS(args) args
68 # define PARAMS(args) ()
70 #endif /* Not PARAMS. */
72 #ifndef INSIDE_RECURSION
74 # if defined STDC_HEADERS && !defined emacs
77 /* We need this for `regex.h', and perhaps for the Emacs include files. */
78 # include <sys/types.h>
82 /* For platform which support the ISO C amendement 1 functionality we
83 support user defined character classes. */
84 #if defined __UCLIBC_HAS_WCHAR__
85 # define WIDE_CHAR_SUPPORT 1
86 /* Solaris 2.5 has a bug: <wchar.h> must be included before <wctype.h>. */
92 /* We have to keep the namespace clean. */
93 # define regfree(preg) __regfree (preg)
94 # define regexec(pr, st, nm, pm, ef) __regexec (pr, st, nm, pm, ef)
95 # define regcomp(preg, pattern, cflags) __regcomp (preg, pattern, cflags)
96 # define regerror(errcode, preg, errbuf, errbuf_size) \
97 __regerror(errcode, preg, errbuf, errbuf_size)
98 # define re_set_registers(bu, re, nu, st, en) \
99 __re_set_registers (bu, re, nu, st, en)
100 # define re_match_2(bufp, string1, size1, string2, size2, pos, regs, stop) \
101 __re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
102 # define re_match(bufp, string, size, pos, regs) \
103 __re_match (bufp, string, size, pos, regs)
104 # define re_search(bufp, string, size, startpos, range, regs) \
105 __re_search (bufp, string, size, startpos, range, regs)
106 # define re_compile_pattern(pattern, length, bufp) \
107 __re_compile_pattern (pattern, length, bufp)
108 # define re_set_syntax(syntax) __re_set_syntax (syntax)
109 # define re_search_2(bufp, st1, s1, st2, s2, startpos, range, regs, stop) \
110 __re_search_2 (bufp, st1, s1, st2, s2, startpos, range, regs, stop)
111 # define re_compile_fastmap(bufp) __re_compile_fastmap (bufp)
113 # define btowc __btowc
115 /* We are also using some library internals. */
116 # include <locale/localeinfo.h>
117 # include <locale/elem-hash.h>
118 # include <langinfo.h>
119 # include <locale/coll-lookup.h>
122 /* This is for other GNU distributions with internationalized messages. */
123 # if HAVE_LIBINTL_H || defined _LIBC
124 # include <libintl.h>
127 # define gettext(msgid) __dcgettext ("libc", msgid, LC_MESSAGES)
130 # define gettext(msgid) (msgid)
133 # ifndef gettext_noop
134 /* This define is so xgettext can find the internationalizable
136 # define gettext_noop(String) String
139 /* The `emacs' switch turns on certain matching commands
140 that make sense only in Emacs. */
147 # else /* not emacs */
149 /* If we are not linking with Emacs proper,
150 we can't use the relocating allocator
151 even if config.h says that we can. */
154 # if defined STDC_HEADERS || defined _LIBC
161 /* When used in Emacs's lib-src, we need to get bzero and bcopy somehow.
162 If nothing else has been done, use the method below. */
163 # ifdef INHIBIT_STRING_HEADER
164 # if !(defined HAVE_BZERO && defined HAVE_BCOPY)
165 # if !defined bzero && !defined bcopy
166 # undef INHIBIT_STRING_HEADER
171 /* This is the normal way of making sure we have a bcopy and a bzero.
172 This is used in most programs--a few other programs avoid this
173 by defining INHIBIT_STRING_HEADER. */
174 # ifndef INHIBIT_STRING_HEADER
175 # if defined HAVE_STRING_H || defined STDC_HEADERS || defined _LIBC
179 # define bzero(s, n) (memset (s, '\0', n), (s))
181 # define bzero(s, n) __bzero (s, n)
185 # include <strings.h>
187 # define memcmp(s1, s2, n) bcmp (s1, s2, n)
190 # define memcpy(d, s, n) (bcopy (s, d, n), (d))
195 /* Define the syntax stuff for \<, \>, etc. */
197 /* This must be nonzero for the wordchar and notwordchar pattern
198 commands in re_match_2. */
203 # ifdef SWITCH_ENUM_BUG
204 # define SWITCH_ENUM_CAST(x) ((int)(x))
206 # define SWITCH_ENUM_CAST(x) (x)
209 # endif /* not emacs */
211 # if defined _LIBC || HAVE_LIMITS_H
216 # define MB_LEN_MAX 1
219 /* Get the interface, including the syntax bits. */
222 /* isalpha etc. are used for the character classes. */
225 /* Jim Meyering writes:
227 "... Some ctype macros are valid only for character codes that
228 isascii says are ASCII (SGI's IRIX-4.0.5 is one such system --when
229 using /bin/cc or gcc but without giving an ansi option). So, all
230 ctype uses should be through macros like ISPRINT... If
231 STDC_HEADERS is defined, then autoconf has verified that the ctype
232 macros don't need to be guarded with references to isascii. ...
233 Defining isascii to 1 should let any compiler worth its salt
234 eliminate the && through constant folding."
235 Solaris defines some of these symbols so we must undefine them first. */
238 # if defined STDC_HEADERS || (!defined isascii && !defined HAVE_ISASCII)
239 # define ISASCII(c) 1
241 # define ISASCII(c) isascii(c)
245 # define ISBLANK(c) (ISASCII (c) && isblank (c))
247 # define ISBLANK(c) ((c) == ' ' || (c) == '\t')
250 # define ISGRAPH(c) (ISASCII (c) && isgraph (c))
252 # define ISGRAPH(c) (ISASCII (c) && isprint (c) && !isspace (c))
256 # define ISPRINT(c) (ISASCII (c) && isprint (c))
257 # define ISDIGIT(c) (ISASCII (c) && isdigit (c))
258 # define ISALNUM(c) (ISASCII (c) && isalnum (c))
259 # define ISALPHA(c) (ISASCII (c) && isalpha (c))
260 # define ISCNTRL(c) (ISASCII (c) && iscntrl (c))
261 # define ISLOWER(c) (ISASCII (c) && islower (c))
262 # define ISPUNCT(c) (ISASCII (c) && ispunct (c))
263 # define ISSPACE(c) (ISASCII (c) && isspace (c))
264 # define ISUPPER(c) (ISASCII (c) && isupper (c))
265 # define ISXDIGIT(c) (ISASCII (c) && isxdigit (c))
268 # define TOLOWER(c) _tolower(c)
270 # define TOLOWER(c) tolower(c)
274 # define NULL (void *)0
277 /* We remove any previous definition of `SIGN_EXTEND_CHAR',
278 since ours (we hope) works properly with all combinations of
279 machines, compilers, `char' and `unsigned char' argument types.
280 (Per Bothner suggested the basic approach.) */
281 # undef SIGN_EXTEND_CHAR
283 # define SIGN_EXTEND_CHAR(c) ((signed char) (c))
284 # else /* not __STDC__ */
285 /* As in Harbison and Steele. */
286 # define SIGN_EXTEND_CHAR(c) ((((unsigned char) (c)) ^ 128) - 128)
290 /* How many characters in the character set. */
291 # define CHAR_SET_SIZE 256
295 extern char *re_syntax_table;
297 # else /* not SYNTAX_TABLE */
299 static char re_syntax_table[CHAR_SET_SIZE];
301 static void init_syntax_once PARAMS ((void));
311 bzero (re_syntax_table, sizeof re_syntax_table);
313 for (c = 0; c < CHAR_SET_SIZE; ++c)
315 re_syntax_table[c] = Sword;
317 re_syntax_table['_'] = Sword;
322 # endif /* not SYNTAX_TABLE */
324 # define SYNTAX(c) re_syntax_table[(unsigned char) (c)]
328 /* Integer type for pointers. */
330 typedef unsigned long int uintptr_t;
333 /* Should we use malloc or alloca? If REGEX_MALLOC is not defined, we
334 use `alloca' instead of `malloc'. This is because using malloc in
335 re_search* or re_match* could cause memory leaks when C-g is used in
336 Emacs; also, malloc is slower and causes storage fragmentation. On
337 the other hand, malloc is more portable, and easier to debug.
339 Because we sometimes use alloca, some routines have to be macros,
340 not functions -- `alloca'-allocated space disappears at the end of the
341 function it is called in. */
345 # define REGEX_ALLOCATE malloc
346 # define REGEX_REALLOCATE(source, osize, nsize) realloc (source, nsize)
347 # define REGEX_FREE free
349 # else /* not REGEX_MALLOC */
351 /* Emacs already defines alloca, sometimes. */
354 /* Make alloca work the best possible way. */
356 # define alloca __builtin_alloca
357 # else /* not __GNUC__ */
360 # endif /* HAVE_ALLOCA_H */
361 # endif /* not __GNUC__ */
363 # endif /* not alloca */
365 # define REGEX_ALLOCATE alloca
367 /* Assumes a `char *destination' variable. */
368 # define REGEX_REALLOCATE(source, osize, nsize) \
369 (destination = (char *) alloca (nsize), \
370 memcpy (destination, source, osize))
372 /* No need to do anything to free, after alloca. */
373 # define REGEX_FREE(arg) ((void)0) /* Do nothing! But inhibit gcc warning. */
375 # endif /* not REGEX_MALLOC */
377 /* Define how to allocate the failure stack. */
379 # if defined REL_ALLOC && defined REGEX_MALLOC
381 # define REGEX_ALLOCATE_STACK(size) \
382 r_alloc (&failure_stack_ptr, (size))
383 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
384 r_re_alloc (&failure_stack_ptr, (nsize))
385 # define REGEX_FREE_STACK(ptr) \
386 r_alloc_free (&failure_stack_ptr)
388 # else /* not using relocating allocator */
392 # define REGEX_ALLOCATE_STACK malloc
393 # define REGEX_REALLOCATE_STACK(source, osize, nsize) realloc (source, nsize)
394 # define REGEX_FREE_STACK free
396 # else /* not REGEX_MALLOC */
398 # define REGEX_ALLOCATE_STACK alloca
400 # define REGEX_REALLOCATE_STACK(source, osize, nsize) \
401 REGEX_REALLOCATE (source, osize, nsize)
402 /* No need to explicitly free anything. */
403 # define REGEX_FREE_STACK(arg)
405 # endif /* not REGEX_MALLOC */
406 # endif /* not using relocating allocator */
409 /* True if `size1' is non-NULL and PTR is pointing anywhere inside
410 `string1' or just past its end. This works if PTR is NULL, which is
412 # define FIRST_STRING_P(ptr) \
413 (size1 && string1 <= (ptr) && (ptr) <= string1 + size1)
415 /* (Re)Allocate N items of type T using malloc, or fail. */
416 # define TALLOC(n, t) ((t *) malloc ((n) * sizeof (t)))
417 # define RETALLOC(addr, n, t) ((addr) = (t *) realloc (addr, (n) * sizeof (t)))
418 # define RETALLOC_IF(addr, n, t) \
419 if (addr) RETALLOC((addr), (n), t); else (addr) = TALLOC ((n), t)
420 # define REGEX_TALLOC(n, t) ((t *) REGEX_ALLOCATE ((n) * sizeof (t)))
422 # define BYTEWIDTH 8 /* In bits. */
424 # define STREQ(s1, s2) ((strcmp (s1, s2) == 0))
428 # define MAX(a, b) ((a) > (b) ? (a) : (b))
429 # define MIN(a, b) ((a) < (b) ? (a) : (b))
431 typedef char boolean;
435 static reg_errcode_t byte_regex_compile _RE_ARGS ((const char *pattern, size_t size,
437 struct re_pattern_buffer *bufp));
439 static int byte_re_match_2_internal PARAMS ((struct re_pattern_buffer *bufp,
440 const char *string1, int size1,
441 const char *string2, int size2,
443 struct re_registers *regs,
445 static int byte_re_search_2 PARAMS ((struct re_pattern_buffer *bufp,
446 const char *string1, int size1,
447 const char *string2, int size2,
448 int startpos, int range,
449 struct re_registers *regs, int stop));
450 static int byte_re_compile_fastmap PARAMS ((struct re_pattern_buffer *bufp));
453 static reg_errcode_t wcs_regex_compile _RE_ARGS ((const char *pattern, size_t size,
455 struct re_pattern_buffer *bufp));
458 static int wcs_re_match_2_internal PARAMS ((struct re_pattern_buffer *bufp,
459 const char *cstring1, int csize1,
460 const char *cstring2, int csize2,
462 struct re_registers *regs,
464 wchar_t *string1, int size1,
465 wchar_t *string2, int size2,
466 int *mbs_offset1, int *mbs_offset2));
467 static int wcs_re_search_2 PARAMS ((struct re_pattern_buffer *bufp,
468 const char *string1, int size1,
469 const char *string2, int size2,
470 int startpos, int range,
471 struct re_registers *regs, int stop));
472 static int wcs_re_compile_fastmap PARAMS ((struct re_pattern_buffer *bufp));
475 /* These are the command codes that appear in compiled regular
476 expressions. Some opcodes are followed by argument bytes. A
477 command code can specify any interpretation whatsoever for its
478 arguments. Zero bytes may appear in the compiled regular expression. */
484 /* Succeed right away--no more backtracking. */
487 /* Followed by one byte giving n, then by n literal bytes. */
491 /* Same as exactn, but contains binary data. */
495 /* Matches any (more or less) character. */
498 /* Matches any one char belonging to specified set. First
499 following byte is number of bitmap bytes. Then come bytes
500 for a bitmap saying which chars are in. Bits in each byte
501 are ordered low-bit-first. A character is in the set if its
502 bit is 1. A character too large to have a bit in the map is
503 automatically not in the set. */
504 /* ifdef MBS_SUPPORT, following element is length of character
505 classes, length of collating symbols, length of equivalence
506 classes, length of character ranges, and length of characters.
507 Next, character class element, collating symbols elements,
508 equivalence class elements, range elements, and character
510 See regex_compile function. */
513 /* Same parameters as charset, but match any character that is
514 not one of those specified. */
517 /* Start remembering the text that is matched, for storing in a
518 register. Followed by one byte with the register number, in
519 the range 0 to one less than the pattern buffer's re_nsub
520 field. Then followed by one byte with the number of groups
521 inner to this one. (This last has to be part of the
522 start_memory only because we need it in the on_failure_jump
526 /* Stop remembering the text that is matched and store it in a
527 memory register. Followed by one byte with the register
528 number, in the range 0 to one less than `re_nsub' in the
529 pattern buffer, and one byte with the number of inner groups,
530 just like `start_memory'. (We need the number of inner
531 groups here because we don't have any easy way of finding the
532 corresponding start_memory when we're at a stop_memory.) */
535 /* Match a duplicate of something remembered. Followed by one
536 byte containing the register number. */
539 /* Fail unless at beginning of line. */
542 /* Fail unless at end of line. */
545 /* Succeeds if at beginning of buffer (if emacs) or at beginning
546 of string to be matched (if not). */
549 /* Analogously, for end of buffer/string. */
552 /* Followed by two byte relative address to which to jump. */
555 /* Same as jump, but marks the end of an alternative. */
558 /* Followed by two-byte relative address of place to resume at
559 in case of failure. */
560 /* ifdef MBS_SUPPORT, the size of address is 1. */
563 /* Like on_failure_jump, but pushes a placeholder instead of the
564 current string position when executed. */
565 on_failure_keep_string_jump,
567 /* Throw away latest failure point and then jump to following
568 two-byte relative address. */
569 /* ifdef MBS_SUPPORT, the size of address is 1. */
572 /* Change to pop_failure_jump if know won't have to backtrack to
573 match; otherwise change to jump. This is used to jump
574 back to the beginning of a repeat. If what follows this jump
575 clearly won't match what the repeat does, such that we can be
576 sure that there is no use backtracking out of repetitions
577 already matched, then we change it to a pop_failure_jump.
578 Followed by two-byte address. */
579 /* ifdef MBS_SUPPORT, the size of address is 1. */
582 /* Jump to following two-byte address, and push a dummy failure
583 point. This failure point will be thrown away if an attempt
584 is made to use it for a failure. A `+' construct makes this
585 before the first repeat. Also used as an intermediary kind
586 of jump when compiling an alternative. */
587 /* ifdef MBS_SUPPORT, the size of address is 1. */
590 /* Push a dummy failure point and continue. Used at the end of
594 /* Followed by two-byte relative address and two-byte number n.
595 After matching N times, jump to the address upon failure. */
596 /* ifdef MBS_SUPPORT, the size of address is 1. */
599 /* Followed by two-byte relative address, and two-byte number n.
600 Jump to the address N times, then fail. */
601 /* ifdef MBS_SUPPORT, the size of address is 1. */
604 /* Set the following two-byte relative address to the
605 subsequent two-byte number. The address *includes* the two
607 /* ifdef MBS_SUPPORT, the size of address is 1. */
610 wordchar, /* Matches any word-constituent character. */
611 notwordchar, /* Matches any char that is not a word-constituent. */
613 wordbeg, /* Succeeds if at word beginning. */
614 wordend, /* Succeeds if at word end. */
616 wordbound, /* Succeeds if at a word boundary. */
617 notwordbound /* Succeeds if not at a word boundary. */
620 ,before_dot, /* Succeeds if before point. */
621 at_dot, /* Succeeds if at point. */
622 after_dot, /* Succeeds if after point. */
624 /* Matches any character whose syntax is specified. Followed by
625 a byte which contains a syntax code, e.g., Sword. */
628 /* Matches any character whose syntax is not that specified. */
632 #endif /* not INSIDE_RECURSION */
637 # define UCHAR_T unsigned char
638 # define COMPILED_BUFFER_VAR bufp->buffer
639 # define OFFSET_ADDRESS_SIZE 2
640 # define PREFIX(name) byte_##name
641 # define ARG_PREFIX(name) name
642 # define PUT_CHAR(c) putchar (c)
645 # define CHAR_T wchar_t
646 # define UCHAR_T wchar_t
647 # define COMPILED_BUFFER_VAR wc_buffer
648 # define OFFSET_ADDRESS_SIZE 1 /* the size which STORE_NUMBER macro use */
649 # define CHAR_CLASS_SIZE ((__alignof__(wctype_t)+sizeof(wctype_t))/sizeof(CHAR_T)+1)
650 # define PREFIX(name) wcs_##name
651 # define ARG_PREFIX(name) c##name
652 /* Should we use wide stream?? */
653 # define PUT_CHAR(c) printf ("%C", c);
659 # define INSIDE_RECURSION
660 # include "regex_old.c"
661 # undef INSIDE_RECURSION
664 # define INSIDE_RECURSION
665 # include "regex_old.c"
666 # undef INSIDE_RECURSION
670 #ifdef INSIDE_RECURSION
671 /* Common operations on the compiled pattern. */
673 /* Store NUMBER in two contiguous bytes starting at DESTINATION. */
674 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
677 # define STORE_NUMBER(destination, number) \
679 *(destination) = (UCHAR_T)(number); \
682 # define STORE_NUMBER(destination, number) \
684 (destination)[0] = (number) & 0377; \
685 (destination)[1] = (number) >> 8; \
689 /* Same as STORE_NUMBER, except increment DESTINATION to
690 the byte after where the number is stored. Therefore, DESTINATION
691 must be an lvalue. */
692 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
694 # define STORE_NUMBER_AND_INCR(destination, number) \
696 STORE_NUMBER (destination, number); \
697 (destination) += OFFSET_ADDRESS_SIZE; \
700 /* Put into DESTINATION a number stored in two contiguous bytes starting
702 /* ifdef MBS_SUPPORT, we store NUMBER in 1 element. */
705 # define EXTRACT_NUMBER(destination, source) \
707 (destination) = *(source); \
710 # define EXTRACT_NUMBER(destination, source) \
712 (destination) = *(source) & 0377; \
713 (destination) += SIGN_EXTEND_CHAR (*((source) + 1)) << 8; \
718 static void PREFIX(extract_number) _RE_ARGS ((int *dest, UCHAR_T *source));
720 PREFIX(extract_number) (dest, source)
727 int temp = SIGN_EXTEND_CHAR (*(source + 1));
728 *dest = *source & 0377;
733 # ifndef EXTRACT_MACROS /* To debug the macros. */
734 # undef EXTRACT_NUMBER
735 # define EXTRACT_NUMBER(dest, src) PREFIX(extract_number) (&dest, src)
736 # endif /* not EXTRACT_MACROS */
740 /* Same as EXTRACT_NUMBER, except increment SOURCE to after the number.
741 SOURCE must be an lvalue. */
743 # define EXTRACT_NUMBER_AND_INCR(destination, source) \
745 EXTRACT_NUMBER (destination, source); \
746 (source) += OFFSET_ADDRESS_SIZE; \
750 static void PREFIX(extract_number_and_incr) _RE_ARGS ((int *destination,
753 PREFIX(extract_number_and_incr) (destination, source)
757 PREFIX(extract_number) (destination, *source);
758 *source += OFFSET_ADDRESS_SIZE;
761 # ifndef EXTRACT_MACROS
762 # undef EXTRACT_NUMBER_AND_INCR
763 # define EXTRACT_NUMBER_AND_INCR(dest, src) \
764 PREFIX(extract_number_and_incr) (&dest, &src)
765 # endif /* not EXTRACT_MACROS */
771 /* If DEBUG is defined, Regex prints many voluminous messages about what
772 it is doing (if the variable `debug' is nonzero). If linked with the
773 main program in `iregex.c', you can enter patterns and strings
774 interactively. And if linked with the main program in `main.c' and
775 the other test files, you can run the already-written tests. */
779 # ifndef DEFINED_ONCE
781 /* We use standard I/O for debugging. */
784 /* It is useful to test things that ``must'' be true when debugging. */
789 # define DEBUG_STATEMENT(e) e
790 # define DEBUG_PRINT1(x) if (debug) printf (x)
791 # define DEBUG_PRINT2(x1, x2) if (debug) printf (x1, x2)
792 # define DEBUG_PRINT3(x1, x2, x3) if (debug) printf (x1, x2, x3)
793 # define DEBUG_PRINT4(x1, x2, x3, x4) if (debug) printf (x1, x2, x3, x4)
794 # endif /* not DEFINED_ONCE */
796 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e) \
797 if (debug) PREFIX(print_partial_compiled_pattern) (s, e)
798 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2) \
799 if (debug) PREFIX(print_double_string) (w, s1, sz1, s2, sz2)
802 /* Print the fastmap in human-readable form. */
804 # ifndef DEFINED_ONCE
806 print_fastmap (fastmap)
809 unsigned was_a_range = 0;
812 while (i < (1 << BYTEWIDTH))
818 while (i < (1 << BYTEWIDTH) && fastmap[i])
832 # endif /* not DEFINED_ONCE */
835 /* Print a compiled pattern string in human-readable form, starting at
836 the START pointer into it and ending just before the pointer END. */
839 PREFIX(print_partial_compiled_pattern) (start, end)
854 /* Loop over pattern commands. */
858 printf ("%td:\t", p - start);
860 printf ("%ld:\t", (long int) (p - start));
863 switch ((re_opcode_t) *p++)
871 printf ("/exactn/%d", mcnt);
883 printf ("/exactn_bin/%d", mcnt);
886 printf("/%lx", (long int) *p++);
890 # endif /* MBS_SUPPORT */
894 printf ("/start_memory/%d/%ld", mcnt, (long int) *p++);
899 printf ("/stop_memory/%d/%ld", mcnt, (long int) *p++);
903 printf ("/duplicate/%ld", (long int) *p++);
916 printf ("/charset [%s",
917 (re_opcode_t) *(workp - 1) == charset_not ? "^" : "");
919 length = *workp++; /* the length of char_classes */
920 for (i=0 ; i<length ; i++)
921 printf("[:%lx:]", (long int) *p++);
922 length = *workp++; /* the length of collating_symbol */
923 for (i=0 ; i<length ;)
927 PUT_CHAR((i++,*p++));
931 length = *workp++; /* the length of equivalence_class */
932 for (i=0 ; i<length ;)
936 PUT_CHAR((i++,*p++));
940 length = *workp++; /* the length of char_range */
941 for (i=0 ; i<length ; i++)
943 wchar_t range_start = *p++;
944 wchar_t range_end = *p++;
945 printf("%C-%C", range_start, range_end);
947 length = *workp++; /* the length of char */
948 for (i=0 ; i<length ; i++)
952 register int c, last = -100;
953 register int in_range = 0;
955 printf ("/charset [%s",
956 (re_opcode_t) *(p - 1) == charset_not ? "^" : "");
958 assert (p + *p < pend);
960 for (c = 0; c < 256; c++)
962 && (p[1 + (c/8)] & (1 << (c % 8))))
964 /* Are we starting a range? */
965 if (last + 1 == c && ! in_range)
970 /* Have we broken a range? */
971 else if (last + 1 != c && in_range)
1001 case on_failure_jump:
1002 PREFIX(extract_number_and_incr) (&mcnt, &p);
1004 printf ("/on_failure_jump to %td", p + mcnt - start);
1006 printf ("/on_failure_jump to %ld", (long int) (p + mcnt - start));
1010 case on_failure_keep_string_jump:
1011 PREFIX(extract_number_and_incr) (&mcnt, &p);
1013 printf ("/on_failure_keep_string_jump to %td", p + mcnt - start);
1015 printf ("/on_failure_keep_string_jump to %ld",
1016 (long int) (p + mcnt - start));
1020 case dummy_failure_jump:
1021 PREFIX(extract_number_and_incr) (&mcnt, &p);
1023 printf ("/dummy_failure_jump to %td", p + mcnt - start);
1025 printf ("/dummy_failure_jump to %ld", (long int) (p + mcnt - start));
1029 case push_dummy_failure:
1030 printf ("/push_dummy_failure");
1033 case maybe_pop_jump:
1034 PREFIX(extract_number_and_incr) (&mcnt, &p);
1036 printf ("/maybe_pop_jump to %td", p + mcnt - start);
1038 printf ("/maybe_pop_jump to %ld", (long int) (p + mcnt - start));
1042 case pop_failure_jump:
1043 PREFIX(extract_number_and_incr) (&mcnt, &p);
1045 printf ("/pop_failure_jump to %td", p + mcnt - start);
1047 printf ("/pop_failure_jump to %ld", (long int) (p + mcnt - start));
1052 PREFIX(extract_number_and_incr) (&mcnt, &p);
1054 printf ("/jump_past_alt to %td", p + mcnt - start);
1056 printf ("/jump_past_alt to %ld", (long int) (p + mcnt - start));
1061 PREFIX(extract_number_and_incr) (&mcnt, &p);
1063 printf ("/jump to %td", p + mcnt - start);
1065 printf ("/jump to %ld", (long int) (p + mcnt - start));
1070 PREFIX(extract_number_and_incr) (&mcnt, &p);
1072 PREFIX(extract_number_and_incr) (&mcnt2, &p);
1074 printf ("/succeed_n to %td, %d times", p1 - start, mcnt2);
1076 printf ("/succeed_n to %ld, %d times",
1077 (long int) (p1 - start), mcnt2);
1082 PREFIX(extract_number_and_incr) (&mcnt, &p);
1084 PREFIX(extract_number_and_incr) (&mcnt2, &p);
1085 printf ("/jump_n to %d, %d times", p1 - start, mcnt2);
1089 PREFIX(extract_number_and_incr) (&mcnt, &p);
1091 PREFIX(extract_number_and_incr) (&mcnt2, &p);
1093 printf ("/set_number_at location %td to %d", p1 - start, mcnt2);
1095 printf ("/set_number_at location %ld to %d",
1096 (long int) (p1 - start), mcnt2);
1101 printf ("/wordbound");
1105 printf ("/notwordbound");
1109 printf ("/wordbeg");
1113 printf ("/wordend");
1118 printf ("/before_dot");
1126 printf ("/after_dot");
1130 printf ("/syntaxspec");
1132 printf ("/%d", mcnt);
1136 printf ("/notsyntaxspec");
1138 printf ("/%d", mcnt);
1143 printf ("/wordchar");
1147 printf ("/notwordchar");
1159 printf ("?%ld", (long int) *(p-1));
1166 printf ("%td:\tend of pattern.\n", p - start);
1168 printf ("%ld:\tend of pattern.\n", (long int) (p - start));
1174 PREFIX(print_compiled_pattern) (bufp)
1175 struct re_pattern_buffer *bufp;
1177 UCHAR_T *buffer = (UCHAR_T*) bufp->buffer;
1179 PREFIX(print_partial_compiled_pattern) (buffer, buffer
1180 + bufp->used / sizeof(UCHAR_T));
1181 printf ("%ld bytes used/%ld bytes allocated.\n",
1182 bufp->used, bufp->allocated);
1184 if (bufp->fastmap_accurate && bufp->fastmap)
1186 printf ("fastmap: ");
1187 print_fastmap (bufp->fastmap);
1191 printf ("re_nsub: %Zd\t", bufp->re_nsub);
1193 printf ("re_nsub: %ld\t", (long int) bufp->re_nsub);
1195 printf ("regs_alloc: %d\t", bufp->regs_allocated);
1196 printf ("can_be_null: %d\t", bufp->can_be_null);
1197 printf ("newline_anchor: %d\n", bufp->newline_anchor);
1198 printf ("no_sub: %d\t", bufp->no_sub);
1199 printf ("not_bol: %d\t", bufp->not_bol);
1200 printf ("not_eol: %d\t", bufp->not_eol);
1201 printf ("syntax: %lx\n", bufp->syntax);
1202 /* Perhaps we should print the translate table? */
1207 PREFIX(print_double_string) (where, string1, size1, string2, size2)
1208 const CHAR_T *where;
1209 const CHAR_T *string1;
1210 const CHAR_T *string2;
1222 if (FIRST_STRING_P (where))
1224 for (this_char = where - string1; this_char < size1; this_char++)
1225 PUT_CHAR (string1[this_char]);
1231 for (this_char = where - string2; this_char < size2; this_char++)
1233 PUT_CHAR (string2[this_char]);
1236 fputs ("...", stdout);
1243 # ifndef DEFINED_ONCE
1252 # else /* not DEBUG */
1254 # ifndef DEFINED_ONCE
1258 # define DEBUG_STATEMENT(e)
1259 # define DEBUG_PRINT1(x)
1260 # define DEBUG_PRINT2(x1, x2)
1261 # define DEBUG_PRINT3(x1, x2, x3)
1262 # define DEBUG_PRINT4(x1, x2, x3, x4)
1263 # endif /* not DEFINED_ONCE */
1264 # define DEBUG_PRINT_COMPILED_PATTERN(p, s, e)
1265 # define DEBUG_PRINT_DOUBLE_STRING(w, s1, sz1, s2, sz2)
1267 # endif /* not DEBUG */
1272 /* This convert a multibyte string to a wide character string.
1273 And write their correspondances to offset_buffer(see below)
1274 and write whether each wchar_t is binary data to is_binary.
1275 This assume invalid multibyte sequences as binary data.
1276 We assume offset_buffer and is_binary is already allocated
1279 static size_t convert_mbs_to_wcs (CHAR_T *dest, const unsigned char* src,
1280 size_t len, int *offset_buffer,
1283 convert_mbs_to_wcs (dest, src, len, offset_buffer, is_binary)
1285 const unsigned char* src;
1286 size_t len; /* the length of multibyte string. */
1288 /* It hold correspondances between src(char string) and
1289 dest(wchar_t string) for optimization.
1291 dest = {'X', 'Y', 'Z'}
1292 (each "xxx", "y" and "zz" represent one multibyte character
1293 corresponding to 'X', 'Y' and 'Z'.)
1294 offset_buffer = {0, 0+3("xxx"), 0+3+1("y"), 0+3+1+2("zz")}
1300 wchar_t *pdest = dest;
1301 const unsigned char *psrc = src;
1302 size_t wc_count = 0;
1306 size_t mb_remain = len;
1307 size_t mb_count = 0;
1309 /* Initialize the conversion state. */
1310 memset (&mbs, 0, sizeof (mbstate_t));
1312 offset_buffer[0] = 0;
1313 for( ; mb_remain > 0 ; ++wc_count, ++pdest, mb_remain -= consumed,
1317 consumed = __mbrtowc (pdest, psrc, mb_remain, &mbs);
1319 consumed = mbrtowc (pdest, psrc, mb_remain, &mbs);
1323 /* failed to convert. maybe src contains binary data.
1324 So we consume 1 byte manualy. */
1328 is_binary[wc_count] = TRUE;
1331 is_binary[wc_count] = FALSE;
1332 /* In sjis encoding, we use yen sign as escape character in
1333 place of reverse solidus. So we convert 0x5c(yen sign in
1334 sjis) to not 0xa5(yen sign in UCS2) but 0x5c(reverse
1335 solidus in UCS2). */
1336 if (consumed == 1 && (int) *psrc == 0x5c && (int) *pdest == 0xa5)
1337 *pdest = (wchar_t) *psrc;
1339 offset_buffer[wc_count + 1] = mb_count += consumed;
1342 /* Fill remain of the buffer with sentinel. */
1343 for (i = wc_count + 1 ; i <= len ; i++)
1344 offset_buffer[i] = mb_count + 1;
1351 #else /* not INSIDE_RECURSION */
1353 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
1354 also be assigned to arbitrarily: each pattern buffer stores its own
1355 syntax, so it can be changed between regex compilations. */
1356 /* This has no initializer because initialized variables in Emacs
1357 become read-only after dumping. */
1358 reg_syntax_t re_syntax_options;
1361 /* Specify the precise syntax of regexps for compilation. This provides
1362 for compatibility for various utilities which historically have
1363 different, incompatible syntaxes.
1365 The argument SYNTAX is a bit mask comprised of the various bits
1366 defined in regex.h. We return the old syntax. */
1369 re_set_syntax (syntax)
1370 reg_syntax_t syntax;
1372 reg_syntax_t ret = re_syntax_options;
1374 re_syntax_options = syntax;
1376 if (syntax & RE_DEBUG)
1378 else if (debug) /* was on but now is not */
1384 weak_alias (__re_set_syntax, re_set_syntax)
1387 /* This table gives an error message for each of the error codes listed
1388 in regex.h. Obviously the order here has to be same as there.
1389 POSIX doesn't require that we do anything for REG_NOERROR,
1390 but why not be nice? */
1392 static const char re_error_msgid[] =
1394 # define REG_NOERROR_IDX 0
1395 gettext_noop ("Success") /* REG_NOERROR */
1397 # define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
1398 gettext_noop ("No match") /* REG_NOMATCH */
1400 # define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
1401 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
1403 # define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
1404 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
1406 # define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
1407 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
1409 # define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
1410 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
1412 # define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
1413 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
1415 # define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
1416 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
1418 # define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
1419 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
1421 # define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
1422 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
1424 # define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
1425 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
1427 # define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
1428 gettext_noop ("Invalid range end") /* REG_ERANGE */
1430 # define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
1431 gettext_noop ("Memory exhausted") /* REG_ESPACE */
1433 # define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
1434 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
1436 # define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
1437 gettext_noop ("Premature end of regular expression") /* REG_EEND */
1439 # define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
1440 gettext_noop ("Regular expression too big") /* REG_ESIZE */
1442 # define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
1443 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
1446 static const size_t re_error_msgid_idx[] =
1467 #endif /* INSIDE_RECURSION */
1469 #ifndef DEFINED_ONCE
1470 /* Avoiding alloca during matching, to placate r_alloc. */
1472 /* Define MATCH_MAY_ALLOCATE unless we need to make sure that the
1473 searching and matching functions should not call alloca. On some
1474 systems, alloca is implemented in terms of malloc, and if we're
1475 using the relocating allocator routines, then malloc could cause a
1476 relocation, which might (if the strings being searched are in the
1477 ralloc heap) shift the data out from underneath the regexp
1480 Here's another reason to avoid allocation: Emacs
1481 processes input from X in a signal handler; processing X input may
1482 call malloc; if input arrives while a matching routine is calling
1483 malloc, then we're scrod. But Emacs can't just block input while
1484 calling matching routines; then we don't notice interrupts when
1485 they come in. So, Emacs blocks input around all regexp calls
1486 except the matching calls, which it leaves unprotected, in the
1487 faith that they will not malloc. */
1489 /* Normally, this is fine. */
1490 # define MATCH_MAY_ALLOCATE
1492 /* When using GNU C, we are not REALLY using the C alloca, no matter
1493 what config.h may say. So don't take precautions for it. */
1498 /* The match routines may not allocate if (1) they would do it with malloc
1499 and (2) it's not safe for them to use malloc.
1500 Note that if REL_ALLOC is defined, matching would not use malloc for the
1501 failure stack, but we would still use it for the register vectors;
1502 so REL_ALLOC should not affect this. */
1503 # if (defined C_ALLOCA || defined REGEX_MALLOC) && defined emacs
1504 # undef MATCH_MAY_ALLOCATE
1506 #endif /* not DEFINED_ONCE */
1508 #ifdef INSIDE_RECURSION
1509 /* Failure stack declarations and macros; both re_compile_fastmap and
1510 re_match_2 use a failure stack. These have to be macros because of
1511 REGEX_ALLOCATE_STACK. */
1514 /* Number of failure points for which to initially allocate space
1515 when matching. If this number is exceeded, we allocate more
1516 space, so it is not a hard limit. */
1517 # ifndef INIT_FAILURE_ALLOC
1518 # define INIT_FAILURE_ALLOC 5
1521 /* Roughly the maximum number of failure points on the stack. Would be
1522 exactly that if always used MAX_FAILURE_ITEMS items each time we failed.
1523 This is a variable only so users of regex can assign to it; we never
1524 change it ourselves. */
1526 # ifdef INT_IS_16BIT
1528 # ifndef DEFINED_ONCE
1529 # if defined MATCH_MAY_ALLOCATE
1530 /* 4400 was enough to cause a crash on Alpha OSF/1,
1531 whose default stack limit is 2mb. */
1532 long int re_max_failures = 4000;
1534 long int re_max_failures = 2000;
1538 union PREFIX(fail_stack_elt)
1544 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1548 PREFIX(fail_stack_elt_t) *stack;
1549 unsigned long int size;
1550 unsigned long int avail; /* Offset of next open position. */
1551 } PREFIX(fail_stack_type);
1553 # else /* not INT_IS_16BIT */
1555 # ifndef DEFINED_ONCE
1556 # if defined MATCH_MAY_ALLOCATE
1557 /* 4400 was enough to cause a crash on Alpha OSF/1,
1558 whose default stack limit is 2mb. */
1559 int re_max_failures = 4000;
1561 int re_max_failures = 2000;
1565 union PREFIX(fail_stack_elt)
1571 typedef union PREFIX(fail_stack_elt) PREFIX(fail_stack_elt_t);
1575 PREFIX(fail_stack_elt_t) *stack;
1577 unsigned avail; /* Offset of next open position. */
1578 } PREFIX(fail_stack_type);
1580 # endif /* INT_IS_16BIT */
1582 # ifndef DEFINED_ONCE
1583 # define FAIL_STACK_EMPTY() (fail_stack.avail == 0)
1584 # define FAIL_STACK_PTR_EMPTY() (fail_stack_ptr->avail == 0)
1585 # define FAIL_STACK_FULL() (fail_stack.avail == fail_stack.size)
1589 /* Define macros to initialize and free the failure stack.
1590 Do `return -2' if the alloc fails. */
1592 # ifdef MATCH_MAY_ALLOCATE
1593 # define INIT_FAIL_STACK() \
1595 fail_stack.stack = (PREFIX(fail_stack_elt_t) *) \
1596 REGEX_ALLOCATE_STACK (INIT_FAILURE_ALLOC * sizeof (PREFIX(fail_stack_elt_t))); \
1598 if (fail_stack.stack == NULL) \
1601 fail_stack.size = INIT_FAILURE_ALLOC; \
1602 fail_stack.avail = 0; \
1605 # define RESET_FAIL_STACK() REGEX_FREE_STACK (fail_stack.stack)
1607 # define INIT_FAIL_STACK() \
1609 fail_stack.avail = 0; \
1612 # define RESET_FAIL_STACK()
1616 /* Double the size of FAIL_STACK, up to approximately `re_max_failures' items.
1618 Return 1 if succeeds, and 0 if either ran out of memory
1619 allocating space for it or it was already too large.
1621 REGEX_REALLOCATE_STACK requires `destination' be declared. */
1623 # define DOUBLE_FAIL_STACK(fail_stack) \
1624 ((fail_stack).size > (unsigned) (re_max_failures * MAX_FAILURE_ITEMS) \
1626 : ((fail_stack).stack = (PREFIX(fail_stack_elt_t) *) \
1627 REGEX_REALLOCATE_STACK ((fail_stack).stack, \
1628 (fail_stack).size * sizeof (PREFIX(fail_stack_elt_t)), \
1629 ((fail_stack).size << 1) * sizeof (PREFIX(fail_stack_elt_t))),\
1631 (fail_stack).stack == NULL \
1633 : ((fail_stack).size <<= 1, \
1637 /* Push pointer POINTER on FAIL_STACK.
1638 Return 1 if was able to do so and 0 if ran out of memory allocating
1640 # define PUSH_PATTERN_OP(POINTER, FAIL_STACK) \
1641 ((FAIL_STACK_FULL () \
1642 && !DOUBLE_FAIL_STACK (FAIL_STACK)) \
1644 : ((FAIL_STACK).stack[(FAIL_STACK).avail++].pointer = POINTER, \
1647 /* Push a pointer value onto the failure stack.
1648 Assumes the variable `fail_stack'. Probably should only
1649 be called from within `PUSH_FAILURE_POINT'. */
1650 # define PUSH_FAILURE_POINTER(item) \
1651 fail_stack.stack[fail_stack.avail++].pointer = (UCHAR_T *) (item)
1653 /* This pushes an integer-valued item onto the failure stack.
1654 Assumes the variable `fail_stack'. Probably should only
1655 be called from within `PUSH_FAILURE_POINT'. */
1656 # define PUSH_FAILURE_INT(item) \
1657 fail_stack.stack[fail_stack.avail++].integer = (item)
1659 /* Push a fail_stack_elt_t value onto the failure stack.
1660 Assumes the variable `fail_stack'. Probably should only
1661 be called from within `PUSH_FAILURE_POINT'. */
1662 # define PUSH_FAILURE_ELT(item) \
1663 fail_stack.stack[fail_stack.avail++] = (item)
1665 /* These three POP... operations complement the three PUSH... operations.
1666 All assume that `fail_stack' is nonempty. */
1667 # define POP_FAILURE_POINTER() fail_stack.stack[--fail_stack.avail].pointer
1668 # define POP_FAILURE_INT() fail_stack.stack[--fail_stack.avail].integer
1669 # define POP_FAILURE_ELT() fail_stack.stack[--fail_stack.avail]
1671 /* Used to omit pushing failure point id's when we're not debugging. */
1673 # define DEBUG_PUSH PUSH_FAILURE_INT
1674 # define DEBUG_POP(item_addr) *(item_addr) = POP_FAILURE_INT ()
1676 # define DEBUG_PUSH(item)
1677 # define DEBUG_POP(item_addr)
1681 /* Push the information about the state we will need
1682 if we ever fail back to it.
1684 Requires variables fail_stack, regstart, regend, reg_info, and
1685 num_regs_pushed be declared. DOUBLE_FAIL_STACK requires `destination'
1688 Does `return FAILURE_CODE' if runs out of memory. */
1690 # define PUSH_FAILURE_POINT(pattern_place, string_place, failure_code) \
1692 char *destination; \
1693 /* Must be int, so when we don't save any registers, the arithmetic \
1694 of 0 + -1 isn't done as unsigned. */ \
1695 /* Can't be int, since there is not a shred of a guarantee that int \
1696 is wide enough to hold a value of something to which pointer can \
1698 active_reg_t this_reg; \
1700 DEBUG_STATEMENT (failure_id++); \
1701 DEBUG_STATEMENT (nfailure_points_pushed++); \
1702 DEBUG_PRINT2 ("\nPUSH_FAILURE_POINT #%u:\n", failure_id); \
1703 DEBUG_PRINT2 (" Before push, next avail: %d\n", (fail_stack).avail);\
1704 DEBUG_PRINT2 (" size: %d\n", (fail_stack).size);\
1706 DEBUG_PRINT2 (" slots needed: %ld\n", NUM_FAILURE_ITEMS); \
1707 DEBUG_PRINT2 (" available: %d\n", REMAINING_AVAIL_SLOTS); \
1709 /* Ensure we have enough space allocated for what we will push. */ \
1710 while (REMAINING_AVAIL_SLOTS < NUM_FAILURE_ITEMS) \
1712 if (!DOUBLE_FAIL_STACK (fail_stack)) \
1713 return failure_code; \
1715 DEBUG_PRINT2 ("\n Doubled stack; size now: %d\n", \
1716 (fail_stack).size); \
1717 DEBUG_PRINT2 (" slots available: %d\n", REMAINING_AVAIL_SLOTS);\
1720 /* Push the info, starting with the registers. */ \
1721 DEBUG_PRINT1 ("\n"); \
1724 for (this_reg = lowest_active_reg; this_reg <= highest_active_reg; \
1727 DEBUG_PRINT2 (" Pushing reg: %lu\n", this_reg); \
1728 DEBUG_STATEMENT (num_regs_pushed++); \
1730 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1731 PUSH_FAILURE_POINTER (regstart[this_reg]); \
1733 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1734 PUSH_FAILURE_POINTER (regend[this_reg]); \
1736 DEBUG_PRINT2 (" info: %p\n ", \
1737 reg_info[this_reg].word.pointer); \
1738 DEBUG_PRINT2 (" match_null=%d", \
1739 REG_MATCH_NULL_STRING_P (reg_info[this_reg])); \
1740 DEBUG_PRINT2 (" active=%d", IS_ACTIVE (reg_info[this_reg])); \
1741 DEBUG_PRINT2 (" matched_something=%d", \
1742 MATCHED_SOMETHING (reg_info[this_reg])); \
1743 DEBUG_PRINT2 (" ever_matched=%d", \
1744 EVER_MATCHED_SOMETHING (reg_info[this_reg])); \
1745 DEBUG_PRINT1 ("\n"); \
1746 PUSH_FAILURE_ELT (reg_info[this_reg].word); \
1749 DEBUG_PRINT2 (" Pushing low active reg: %ld\n", lowest_active_reg);\
1750 PUSH_FAILURE_INT (lowest_active_reg); \
1752 DEBUG_PRINT2 (" Pushing high active reg: %ld\n", highest_active_reg);\
1753 PUSH_FAILURE_INT (highest_active_reg); \
1755 DEBUG_PRINT2 (" Pushing pattern %p:\n", pattern_place); \
1756 DEBUG_PRINT_COMPILED_PATTERN (bufp, pattern_place, pend); \
1757 PUSH_FAILURE_POINTER (pattern_place); \
1759 DEBUG_PRINT2 (" Pushing string %p: `", string_place); \
1760 DEBUG_PRINT_DOUBLE_STRING (string_place, string1, size1, string2, \
1762 DEBUG_PRINT1 ("'\n"); \
1763 PUSH_FAILURE_POINTER (string_place); \
1765 DEBUG_PRINT2 (" Pushing failure id: %u\n", failure_id); \
1766 DEBUG_PUSH (failure_id); \
1769 # ifndef DEFINED_ONCE
1770 /* This is the number of items that are pushed and popped on the stack
1771 for each register. */
1772 # define NUM_REG_ITEMS 3
1774 /* Individual items aside from the registers. */
1776 # define NUM_NONREG_ITEMS 5 /* Includes failure point id. */
1778 # define NUM_NONREG_ITEMS 4
1781 /* We push at most this many items on the stack. */
1782 /* We used to use (num_regs - 1), which is the number of registers
1783 this regexp will save; but that was changed to 5
1784 to avoid stack overflow for a regexp with lots of parens. */
1785 # define MAX_FAILURE_ITEMS (5 * NUM_REG_ITEMS + NUM_NONREG_ITEMS)
1787 /* We actually push this many items. */
1788 # define NUM_FAILURE_ITEMS \
1790 ? 0 : highest_active_reg - lowest_active_reg + 1) \
1794 /* How many items can still be added to the stack without overflowing it. */
1795 # define REMAINING_AVAIL_SLOTS ((fail_stack).size - (fail_stack).avail)
1796 # endif /* not DEFINED_ONCE */
1799 /* Pops what PUSH_FAIL_STACK pushes.
1801 We restore into the parameters, all of which should be lvalues:
1802 STR -- the saved data position.
1803 PAT -- the saved pattern position.
1804 LOW_REG, HIGH_REG -- the highest and lowest active registers.
1805 REGSTART, REGEND -- arrays of string positions.
1806 REG_INFO -- array of information about each subexpression.
1808 Also assumes the variables `fail_stack' and (if debugging), `bufp',
1809 `pend', `string1', `size1', `string2', and `size2'. */
1810 # define POP_FAILURE_POINT(str, pat, low_reg, high_reg, regstart, regend, reg_info)\
1812 DEBUG_STATEMENT (unsigned failure_id;) \
1813 active_reg_t this_reg; \
1814 const UCHAR_T *string_temp; \
1816 assert (!FAIL_STACK_EMPTY ()); \
1818 /* Remove failure points and point to how many regs pushed. */ \
1819 DEBUG_PRINT1 ("POP_FAILURE_POINT:\n"); \
1820 DEBUG_PRINT2 (" Before pop, next avail: %d\n", fail_stack.avail); \
1821 DEBUG_PRINT2 (" size: %d\n", fail_stack.size); \
1823 assert (fail_stack.avail >= NUM_NONREG_ITEMS); \
1825 DEBUG_POP (&failure_id); \
1826 DEBUG_PRINT2 (" Popping failure id: %u\n", failure_id); \
1828 /* If the saved string location is NULL, it came from an \
1829 on_failure_keep_string_jump opcode, and we want to throw away the \
1830 saved NULL, thus retaining our current position in the string. */ \
1831 string_temp = POP_FAILURE_POINTER (); \
1832 if (string_temp != NULL) \
1833 str = (const CHAR_T *) string_temp; \
1835 DEBUG_PRINT2 (" Popping string %p: `", str); \
1836 DEBUG_PRINT_DOUBLE_STRING (str, string1, size1, string2, size2); \
1837 DEBUG_PRINT1 ("'\n"); \
1839 pat = (UCHAR_T *) POP_FAILURE_POINTER (); \
1840 DEBUG_PRINT2 (" Popping pattern %p:\n", pat); \
1841 DEBUG_PRINT_COMPILED_PATTERN (bufp, pat, pend); \
1843 /* Restore register info. */ \
1844 high_reg = (active_reg_t) POP_FAILURE_INT (); \
1845 DEBUG_PRINT2 (" Popping high active reg: %ld\n", high_reg); \
1847 low_reg = (active_reg_t) POP_FAILURE_INT (); \
1848 DEBUG_PRINT2 (" Popping low active reg: %ld\n", low_reg); \
1851 for (this_reg = high_reg; this_reg >= low_reg; this_reg--) \
1853 DEBUG_PRINT2 (" Popping reg: %ld\n", this_reg); \
1855 reg_info[this_reg].word = POP_FAILURE_ELT (); \
1856 DEBUG_PRINT2 (" info: %p\n", \
1857 reg_info[this_reg].word.pointer); \
1859 regend[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1860 DEBUG_PRINT2 (" end: %p\n", regend[this_reg]); \
1862 regstart[this_reg] = (const CHAR_T *) POP_FAILURE_POINTER (); \
1863 DEBUG_PRINT2 (" start: %p\n", regstart[this_reg]); \
1867 for (this_reg = highest_active_reg; this_reg > high_reg; this_reg--) \
1869 reg_info[this_reg].word.integer = 0; \
1870 regend[this_reg] = 0; \
1871 regstart[this_reg] = 0; \
1873 highest_active_reg = high_reg; \
1876 set_regs_matched_done = 0; \
1877 DEBUG_STATEMENT (nfailure_points_popped++); \
1878 } /* POP_FAILURE_POINT */
1880 /* Structure for per-register (a.k.a. per-group) information.
1881 Other register information, such as the
1882 starting and ending positions (which are addresses), and the list of
1883 inner groups (which is a bits list) are maintained in separate
1886 We are making a (strictly speaking) nonportable assumption here: that
1887 the compiler will pack our bit fields into something that fits into
1888 the type of `word', i.e., is something that fits into one item on the
1892 /* Declarations and macros for re_match_2. */
1896 PREFIX(fail_stack_elt_t) word;
1899 /* This field is one if this group can match the empty string,
1900 zero if not. If not yet determined, `MATCH_NULL_UNSET_VALUE'. */
1901 # define MATCH_NULL_UNSET_VALUE 3
1902 unsigned match_null_string_p : 2;
1903 unsigned is_active : 1;
1904 unsigned matched_something : 1;
1905 unsigned ever_matched_something : 1;
1907 } PREFIX(register_info_type);
1909 # ifndef DEFINED_ONCE
1910 # define REG_MATCH_NULL_STRING_P(R) ((R).bits.match_null_string_p)
1911 # define IS_ACTIVE(R) ((R).bits.is_active)
1912 # define MATCHED_SOMETHING(R) ((R).bits.matched_something)
1913 # define EVER_MATCHED_SOMETHING(R) ((R).bits.ever_matched_something)
1916 /* Call this when have matched a real character; it sets `matched' flags
1917 for the subexpressions which we are currently inside. Also records
1918 that those subexprs have matched. */
1919 # define SET_REGS_MATCHED() \
1922 if (!set_regs_matched_done) \
1925 set_regs_matched_done = 1; \
1926 for (r = lowest_active_reg; r <= highest_active_reg; r++) \
1928 MATCHED_SOMETHING (reg_info[r]) \
1929 = EVER_MATCHED_SOMETHING (reg_info[r]) \
1935 # endif /* not DEFINED_ONCE */
1937 /* Registers are set to a sentinel when they haven't yet matched. */
1938 static CHAR_T PREFIX(reg_unset_dummy);
1939 # define REG_UNSET_VALUE (&PREFIX(reg_unset_dummy))
1940 # define REG_UNSET(e) ((e) == REG_UNSET_VALUE)
1942 /* Subroutine declarations and macros for regex_compile. */
1943 static void PREFIX(store_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc, int arg));
1944 static void PREFIX(store_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1945 int arg1, int arg2));
1946 static void PREFIX(insert_op1) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1947 int arg, UCHAR_T *end));
1948 static void PREFIX(insert_op2) _RE_ARGS ((re_opcode_t op, UCHAR_T *loc,
1949 int arg1, int arg2, UCHAR_T *end));
1950 static boolean PREFIX(at_begline_loc_p) _RE_ARGS ((const CHAR_T *pattern,
1952 reg_syntax_t syntax));
1953 static boolean PREFIX(at_endline_loc_p) _RE_ARGS ((const CHAR_T *p,
1955 reg_syntax_t syntax));
1957 static reg_errcode_t wcs_compile_range _RE_ARGS ((CHAR_T range_start,
1958 const CHAR_T **p_ptr,
1961 reg_syntax_t syntax,
1964 static void insert_space _RE_ARGS ((int num, CHAR_T *loc, CHAR_T *end));
1966 static reg_errcode_t byte_compile_range _RE_ARGS ((unsigned int range_start,
1970 reg_syntax_t syntax,
1974 /* Fetch the next character in the uncompiled pattern---translating it
1975 if necessary. Also cast from a signed character in the constant
1976 string passed to us by the user to an unsigned char that we can use
1977 as an array index (in, e.g., `translate'). */
1978 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
1979 because it is impossible to allocate 4GB array for some encodings
1980 which have 4 byte character_set like UCS4. */
1983 # define PATFETCH(c) \
1984 do {if (p == pend) return REG_EEND; \
1985 c = (UCHAR_T) *p++; \
1986 if (translate && (c <= 0xff)) c = (UCHAR_T) translate[c]; \
1989 # define PATFETCH(c) \
1990 do {if (p == pend) return REG_EEND; \
1991 c = (unsigned char) *p++; \
1992 if (translate) c = (unsigned char) translate[c]; \
1997 /* Fetch the next character in the uncompiled pattern, with no
1999 # define PATFETCH_RAW(c) \
2000 do {if (p == pend) return REG_EEND; \
2001 c = (UCHAR_T) *p++; \
2004 /* Go backwards one character in the pattern. */
2005 # define PATUNFETCH p--
2008 /* If `translate' is non-null, return translate[D], else just D. We
2009 cast the subscript to translate because some data is declared as
2010 `char *', to avoid warnings when a string constant is passed. But
2011 when we use a character as a subscript we must make it unsigned. */
2012 /* ifdef MBS_SUPPORT, we translate only if character <= 0xff,
2013 because it is impossible to allocate 4GB array for some encodings
2014 which have 4 byte character_set like UCS4. */
2018 # define TRANSLATE(d) \
2019 ((translate && ((UCHAR_T) (d)) <= 0xff) \
2020 ? (char) translate[(unsigned char) (d)] : (d))
2022 # define TRANSLATE(d) \
2023 (translate ? (char) translate[(unsigned char) (d)] : (d))
2028 /* Macros for outputting the compiled pattern into `buffer'. */
2030 /* If the buffer isn't allocated when it comes in, use this. */
2031 # define INIT_BUF_SIZE (32 * sizeof(UCHAR_T))
2033 /* Make sure we have at least N more bytes of space in buffer. */
2035 # define GET_BUFFER_SPACE(n) \
2036 while (((unsigned long)b - (unsigned long)COMPILED_BUFFER_VAR \
2037 + (n)*sizeof(CHAR_T)) > bufp->allocated) \
2040 # define GET_BUFFER_SPACE(n) \
2041 while ((unsigned long) (b - bufp->buffer + (n)) > bufp->allocated) \
2045 /* Make sure we have one more byte of buffer space and then add C to it. */
2046 # define BUF_PUSH(c) \
2048 GET_BUFFER_SPACE (1); \
2049 *b++ = (UCHAR_T) (c); \
2053 /* Ensure we have two more bytes of buffer space and then append C1 and C2. */
2054 # define BUF_PUSH_2(c1, c2) \
2056 GET_BUFFER_SPACE (2); \
2057 *b++ = (UCHAR_T) (c1); \
2058 *b++ = (UCHAR_T) (c2); \
2062 /* As with BUF_PUSH_2, except for three bytes. */
2063 # define BUF_PUSH_3(c1, c2, c3) \
2065 GET_BUFFER_SPACE (3); \
2066 *b++ = (UCHAR_T) (c1); \
2067 *b++ = (UCHAR_T) (c2); \
2068 *b++ = (UCHAR_T) (c3); \
2071 /* Store a jump with opcode OP at LOC to location TO. We store a
2072 relative address offset by the three bytes the jump itself occupies. */
2073 # define STORE_JUMP(op, loc, to) \
2074 PREFIX(store_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)))
2076 /* Likewise, for a two-argument jump. */
2077 # define STORE_JUMP2(op, loc, to, arg) \
2078 PREFIX(store_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), arg)
2080 /* Like `STORE_JUMP', but for inserting. Assume `b' is the buffer end. */
2081 # define INSERT_JUMP(op, loc, to) \
2082 PREFIX(insert_op1) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)), b)
2084 /* Like `STORE_JUMP2', but for inserting. Assume `b' is the buffer end. */
2085 # define INSERT_JUMP2(op, loc, to, arg) \
2086 PREFIX(insert_op2) (op, loc, (int) ((to) - (loc) - (1 + OFFSET_ADDRESS_SIZE)),\
2089 /* This is not an arbitrary limit: the arguments which represent offsets
2090 into the pattern are two bytes long. So if 2^16 bytes turns out to
2091 be too small, many things would have to change. */
2092 /* Any other compiler which, like MSC, has allocation limit below 2^16
2093 bytes will have to use approach similar to what was done below for
2094 MSC and drop MAX_BUF_SIZE a bit. Otherwise you may end up
2095 reallocating to 0 bytes. Such thing is not going to work too well.
2096 You have been warned!! */
2097 # ifndef DEFINED_ONCE
2098 # if defined _MSC_VER && !defined WIN32
2099 /* Microsoft C 16-bit versions limit malloc to approx 65512 bytes.
2100 The REALLOC define eliminates a flurry of conversion warnings,
2101 but is not required. */
2102 # define MAX_BUF_SIZE 65500L
2103 # define REALLOC(p,s) realloc ((p), (size_t) (s))
2105 # define MAX_BUF_SIZE (1L << 16)
2106 # define REALLOC(p,s) realloc ((p), (s))
2109 /* Extend the buffer by twice its current size via realloc and
2110 reset the pointers that pointed into the old block to point to the
2111 correct places in the new one. If extending the buffer results in it
2112 being larger than MAX_BUF_SIZE, then flag memory exhausted. */
2113 # if __BOUNDED_POINTERS__
2114 # define SET_HIGH_BOUND(P) (__ptrhigh (P) = __ptrlow (P) + bufp->allocated)
2115 # define MOVE_BUFFER_POINTER(P) \
2116 (__ptrlow (P) += incr, SET_HIGH_BOUND (P), __ptrvalue (P) += incr)
2117 # define ELSE_EXTEND_BUFFER_HIGH_BOUND \
2120 SET_HIGH_BOUND (b); \
2121 SET_HIGH_BOUND (begalt); \
2122 if (fixup_alt_jump) \
2123 SET_HIGH_BOUND (fixup_alt_jump); \
2125 SET_HIGH_BOUND (laststart); \
2126 if (pending_exact) \
2127 SET_HIGH_BOUND (pending_exact); \
2130 # define MOVE_BUFFER_POINTER(P) (P) += incr
2131 # define ELSE_EXTEND_BUFFER_HIGH_BOUND
2133 # endif /* not DEFINED_ONCE */
2136 # define EXTEND_BUFFER() \
2138 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2140 if (bufp->allocated + sizeof(UCHAR_T) > MAX_BUF_SIZE) \
2142 bufp->allocated <<= 1; \
2143 if (bufp->allocated > MAX_BUF_SIZE) \
2144 bufp->allocated = MAX_BUF_SIZE; \
2145 /* How many characters the new buffer can have? */ \
2146 wchar_count = bufp->allocated / sizeof(UCHAR_T); \
2147 if (wchar_count == 0) wchar_count = 1; \
2148 /* Truncate the buffer to CHAR_T align. */ \
2149 bufp->allocated = wchar_count * sizeof(UCHAR_T); \
2150 RETALLOC (COMPILED_BUFFER_VAR, wchar_count, UCHAR_T); \
2151 bufp->buffer = (char*)COMPILED_BUFFER_VAR; \
2152 if (COMPILED_BUFFER_VAR == NULL) \
2153 return REG_ESPACE; \
2154 /* If the buffer moved, move all the pointers into it. */ \
2155 if (old_buffer != COMPILED_BUFFER_VAR) \
2157 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2158 MOVE_BUFFER_POINTER (b); \
2159 MOVE_BUFFER_POINTER (begalt); \
2160 if (fixup_alt_jump) \
2161 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2163 MOVE_BUFFER_POINTER (laststart); \
2164 if (pending_exact) \
2165 MOVE_BUFFER_POINTER (pending_exact); \
2167 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2170 # define EXTEND_BUFFER() \
2172 UCHAR_T *old_buffer = COMPILED_BUFFER_VAR; \
2173 if (bufp->allocated == MAX_BUF_SIZE) \
2175 bufp->allocated <<= 1; \
2176 if (bufp->allocated > MAX_BUF_SIZE) \
2177 bufp->allocated = MAX_BUF_SIZE; \
2178 bufp->buffer = (UCHAR_T *) REALLOC (COMPILED_BUFFER_VAR, \
2180 if (COMPILED_BUFFER_VAR == NULL) \
2181 return REG_ESPACE; \
2182 /* If the buffer moved, move all the pointers into it. */ \
2183 if (old_buffer != COMPILED_BUFFER_VAR) \
2185 int incr = COMPILED_BUFFER_VAR - old_buffer; \
2186 MOVE_BUFFER_POINTER (b); \
2187 MOVE_BUFFER_POINTER (begalt); \
2188 if (fixup_alt_jump) \
2189 MOVE_BUFFER_POINTER (fixup_alt_jump); \
2191 MOVE_BUFFER_POINTER (laststart); \
2192 if (pending_exact) \
2193 MOVE_BUFFER_POINTER (pending_exact); \
2195 ELSE_EXTEND_BUFFER_HIGH_BOUND \
2199 # ifndef DEFINED_ONCE
2200 /* Since we have one byte reserved for the register number argument to
2201 {start,stop}_memory, the maximum number of groups we can report
2202 things about is what fits in that byte. */
2203 # define MAX_REGNUM 255
2205 /* But patterns can have more than `MAX_REGNUM' registers. We just
2206 ignore the excess. */
2207 typedef unsigned regnum_t;
2210 /* Macros for the compile stack. */
2212 /* Since offsets can go either forwards or backwards, this type needs to
2213 be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1. */
2214 /* int may be not enough when sizeof(int) == 2. */
2215 typedef long pattern_offset_t;
2219 pattern_offset_t begalt_offset;
2220 pattern_offset_t fixup_alt_jump;
2221 pattern_offset_t inner_group_offset;
2222 pattern_offset_t laststart_offset;
2224 } compile_stack_elt_t;
2229 compile_stack_elt_t *stack;
2231 unsigned avail; /* Offset of next open position. */
2232 } compile_stack_type;
2235 # define INIT_COMPILE_STACK_SIZE 32
2237 # define COMPILE_STACK_EMPTY (compile_stack.avail == 0)
2238 # define COMPILE_STACK_FULL (compile_stack.avail == compile_stack.size)
2240 /* The next available element. */
2241 # define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
2243 # endif /* not DEFINED_ONCE */
2245 /* Set the bit for character C in a list. */
2246 # ifndef DEFINED_ONCE
2247 # define SET_LIST_BIT(c) \
2248 (b[((unsigned char) (c)) / BYTEWIDTH] \
2249 |= 1 << (((unsigned char) c) % BYTEWIDTH))
2250 # endif /* DEFINED_ONCE */
2252 /* Get the next unsigned number in the uncompiled pattern. */
2253 # define GET_UNSIGNED_NUMBER(num) \
2258 if (c < '0' || c > '9') \
2260 if (num <= RE_DUP_MAX) \
2264 num = num * 10 + c - '0'; \
2269 # ifndef DEFINED_ONCE
2270 # if defined _LIBC || WIDE_CHAR_SUPPORT
2271 /* The GNU C library provides support for user-defined character classes
2272 and the functions from ISO C amendement 1. */
2273 # ifdef CHARCLASS_NAME_MAX
2274 # define CHAR_CLASS_MAX_LENGTH CHARCLASS_NAME_MAX
2276 /* This shouldn't happen but some implementation might still have this
2277 problem. Use a reasonable default value. */
2278 # define CHAR_CLASS_MAX_LENGTH 256
2282 # define IS_CHAR_CLASS(string) __wctype (string)
2284 # define IS_CHAR_CLASS(string) wctype (string)
2287 # define CHAR_CLASS_MAX_LENGTH 6 /* Namely, `xdigit'. */
2289 # define IS_CHAR_CLASS(string) \
2290 (STREQ (string, "alpha") || STREQ (string, "upper") \
2291 || STREQ (string, "lower") || STREQ (string, "digit") \
2292 || STREQ (string, "alnum") || STREQ (string, "xdigit") \
2293 || STREQ (string, "space") || STREQ (string, "print") \
2294 || STREQ (string, "punct") || STREQ (string, "graph") \
2295 || STREQ (string, "cntrl") || STREQ (string, "blank"))
2297 # endif /* DEFINED_ONCE */
2299 # ifndef MATCH_MAY_ALLOCATE
2301 /* If we cannot allocate large objects within re_match_2_internal,
2302 we make the fail stack and register vectors global.
2303 The fail stack, we grow to the maximum size when a regexp
2305 The register vectors, we adjust in size each time we
2306 compile a regexp, according to the number of registers it needs. */
2308 static PREFIX(fail_stack_type) fail_stack;
2310 /* Size with which the following vectors are currently allocated.
2311 That is so we can make them bigger as needed,
2312 but never make them smaller. */
2313 # ifdef DEFINED_ONCE
2314 static int regs_allocated_size;
2316 static const char ** regstart, ** regend;
2317 static const char ** old_regstart, ** old_regend;
2318 static const char **best_regstart, **best_regend;
2319 static const char **reg_dummy;
2320 # endif /* DEFINED_ONCE */
2322 static PREFIX(register_info_type) *PREFIX(reg_info);
2323 static PREFIX(register_info_type) *PREFIX(reg_info_dummy);
2325 /* Make the register vectors big enough for NUM_REGS registers,
2326 but don't make them smaller. */
2329 PREFIX(regex_grow_registers) (num_regs)
2332 if (num_regs > regs_allocated_size)
2334 RETALLOC_IF (regstart, num_regs, const char *);
2335 RETALLOC_IF (regend, num_regs, const char *);
2336 RETALLOC_IF (old_regstart, num_regs, const char *);
2337 RETALLOC_IF (old_regend, num_regs, const char *);
2338 RETALLOC_IF (best_regstart, num_regs, const char *);
2339 RETALLOC_IF (best_regend, num_regs, const char *);
2340 RETALLOC_IF (PREFIX(reg_info), num_regs, PREFIX(register_info_type));
2341 RETALLOC_IF (reg_dummy, num_regs, const char *);
2342 RETALLOC_IF (PREFIX(reg_info_dummy), num_regs, PREFIX(register_info_type));
2344 regs_allocated_size = num_regs;
2348 # endif /* not MATCH_MAY_ALLOCATE */
2350 # ifndef DEFINED_ONCE
2351 static boolean group_in_compile_stack _RE_ARGS ((compile_stack_type
2354 # endif /* not DEFINED_ONCE */
2356 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
2357 Returns one of error codes defined in `regex.h', or zero for success.
2359 Assumes the `allocated' (and perhaps `buffer') and `translate'
2360 fields are set in BUFP on entry.
2362 If it succeeds, results are put in BUFP (if it returns an error, the
2363 contents of BUFP are undefined):
2364 `buffer' is the compiled pattern;
2365 `syntax' is set to SYNTAX;
2366 `used' is set to the length of the compiled pattern;
2367 `fastmap_accurate' is zero;
2368 `re_nsub' is the number of subexpressions in PATTERN;
2369 `not_bol' and `not_eol' are zero;
2371 The `fastmap' and `newline_anchor' fields are neither
2372 examined nor set. */
2374 /* Return, freeing storage we allocated. */
2376 # define FREE_STACK_RETURN(value) \
2377 return (free(pattern), free(mbs_offset), free(is_binary), free (compile_stack.stack), value)
2379 # define FREE_STACK_RETURN(value) \
2380 return (free (compile_stack.stack), value)
2383 static reg_errcode_t
2384 PREFIX(regex_compile) (ARG_PREFIX(pattern), ARG_PREFIX(size), syntax, bufp)
2385 const char *ARG_PREFIX(pattern);
2386 size_t ARG_PREFIX(size);
2387 reg_syntax_t syntax;
2388 struct re_pattern_buffer *bufp;
2390 /* We fetch characters from PATTERN here. Even though PATTERN is
2391 `char *' (i.e., signed), we declare these variables as unsigned, so
2392 they can be reliably used as array indices. */
2393 register UCHAR_T c, c1;
2396 /* A temporary space to keep wchar_t pattern and compiled pattern. */
2397 CHAR_T *pattern, *COMPILED_BUFFER_VAR;
2399 /* offset buffer for optimization. See convert_mbs_to_wc. */
2400 int *mbs_offset = NULL;
2401 /* It hold whether each wchar_t is binary data or not. */
2402 char *is_binary = NULL;
2403 /* A flag whether exactn is handling binary data or not. */
2404 char is_exactn_bin = FALSE;
2407 /* A random temporary spot in PATTERN. */
2410 /* Points to the end of the buffer, where we should append. */
2411 register UCHAR_T *b;
2413 /* Keeps track of unclosed groups. */
2414 compile_stack_type compile_stack;
2416 /* Points to the current (ending) position in the pattern. */
2421 const CHAR_T *p = pattern;
2422 const CHAR_T *pend = pattern + size;
2425 /* How to translate the characters in the pattern. */
2426 RE_TRANSLATE_TYPE translate = bufp->translate;
2428 /* Address of the count-byte of the most recently inserted `exactn'
2429 command. This makes it possible to tell if a new exact-match
2430 character can be added to that command or if the character requires
2431 a new `exactn' command. */
2432 UCHAR_T *pending_exact = 0;
2434 /* Address of start of the most recently finished expression.
2435 This tells, e.g., postfix * where to find the start of its
2436 operand. Reset at the beginning of groups and alternatives. */
2437 UCHAR_T *laststart = 0;
2439 /* Address of beginning of regexp, or inside of last group. */
2442 /* Address of the place where a forward jump should go to the end of
2443 the containing expression. Each alternative of an `or' -- except the
2444 last -- ends with a forward jump of this sort. */
2445 UCHAR_T *fixup_alt_jump = 0;
2447 /* Counts open-groups as they are encountered. Remembered for the
2448 matching close-group on the compile stack, so the same register
2449 number is put in the stop_memory as the start_memory. */
2450 regnum_t regnum = 0;
2453 /* Initialize the wchar_t PATTERN and offset_buffer. */
2454 p = pend = pattern = TALLOC(csize + 1, CHAR_T);
2455 mbs_offset = TALLOC(csize + 1, int);
2456 is_binary = TALLOC(csize + 1, char);
2457 if (pattern == NULL || mbs_offset == NULL || is_binary == NULL)
2464 pattern[csize] = L'\0'; /* sentinel */
2465 size = convert_mbs_to_wcs(pattern, cpattern, csize, mbs_offset, is_binary);
2477 DEBUG_PRINT1 ("\nCompiling pattern: ");
2480 unsigned debug_count;
2482 for (debug_count = 0; debug_count < size; debug_count++)
2483 PUT_CHAR (pattern[debug_count]);
2488 /* Initialize the compile stack. */
2489 compile_stack.stack = TALLOC (INIT_COMPILE_STACK_SIZE, compile_stack_elt_t);
2490 if (compile_stack.stack == NULL)
2500 compile_stack.size = INIT_COMPILE_STACK_SIZE;
2501 compile_stack.avail = 0;
2503 /* Initialize the pattern buffer. */
2504 bufp->syntax = syntax;
2505 bufp->fastmap_accurate = 0;
2506 bufp->not_bol = bufp->not_eol = 0;
2508 /* Set `used' to zero, so that if we return an error, the pattern
2509 printer (for debugging) will think there's no pattern. We reset it
2513 /* Always count groups, whether or not bufp->no_sub is set. */
2516 #if !defined emacs && !defined SYNTAX_TABLE
2517 /* Initialize the syntax table. */
2518 init_syntax_once ();
2521 if (bufp->allocated == 0)
2524 { /* If zero allocated, but buffer is non-null, try to realloc
2525 enough space. This loses if buffer's address is bogus, but
2526 that is the user's responsibility. */
2528 /* Free bufp->buffer and allocate an array for wchar_t pattern
2531 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE/sizeof(UCHAR_T),
2534 RETALLOC (COMPILED_BUFFER_VAR, INIT_BUF_SIZE, UCHAR_T);
2538 { /* Caller did not allocate a buffer. Do it for them. */
2539 COMPILED_BUFFER_VAR = TALLOC (INIT_BUF_SIZE / sizeof(UCHAR_T),
2543 if (!COMPILED_BUFFER_VAR) FREE_STACK_RETURN (REG_ESPACE);
2545 bufp->buffer = (char*)COMPILED_BUFFER_VAR;
2547 bufp->allocated = INIT_BUF_SIZE;
2551 COMPILED_BUFFER_VAR = (UCHAR_T*) bufp->buffer;
2554 begalt = b = COMPILED_BUFFER_VAR;
2556 /* Loop through the uncompiled pattern until we're at the end. */
2565 if ( /* If at start of pattern, it's an operator. */
2567 /* If context independent, it's an operator. */
2568 || syntax & RE_CONTEXT_INDEP_ANCHORS
2569 /* Otherwise, depends on what's come before. */
2570 || PREFIX(at_begline_loc_p) (pattern, p, syntax))
2580 if ( /* If at end of pattern, it's an operator. */
2582 /* If context independent, it's an operator. */
2583 || syntax & RE_CONTEXT_INDEP_ANCHORS
2584 /* Otherwise, depends on what's next. */
2585 || PREFIX(at_endline_loc_p) (p, pend, syntax))
2595 if ((syntax & RE_BK_PLUS_QM)
2596 || (syntax & RE_LIMITED_OPS))
2600 /* If there is no previous pattern... */
2603 if (syntax & RE_CONTEXT_INVALID_OPS)
2604 FREE_STACK_RETURN (REG_BADRPT);
2605 else if (!(syntax & RE_CONTEXT_INDEP_OPS))
2610 /* Are we optimizing this jump? */
2611 boolean keep_string_p = false;
2613 /* 1 means zero (many) matches is allowed. */
2614 char zero_times_ok = 0, many_times_ok = 0;
2616 /* If there is a sequence of repetition chars, collapse it
2617 down to just one (the right one). We can't combine
2618 interval operators with these because of, e.g., `a{2}*',
2619 which should only match an even number of `a's. */
2623 zero_times_ok |= c != '+';
2624 many_times_ok |= c != '?';
2632 || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
2635 else if (syntax & RE_BK_PLUS_QM && c == '\\')
2637 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2640 if (!(c1 == '+' || c1 == '?'))
2655 /* If we get here, we found another repeat character. */
2658 /* Star, etc. applied to an empty pattern is equivalent
2659 to an empty pattern. */
2663 /* Now we know whether or not zero matches is allowed
2664 and also whether or not two or more matches is allowed. */
2666 { /* More than one repetition is allowed, so put in at the
2667 end a backward relative jump from `b' to before the next
2668 jump we're going to put in below (which jumps from
2669 laststart to after this jump).
2671 But if we are at the `*' in the exact sequence `.*\n',
2672 insert an unconditional jump backwards to the .,
2673 instead of the beginning of the loop. This way we only
2674 push a failure point once, instead of every time
2675 through the loop. */
2676 assert (p - 1 > pattern);
2678 /* Allocate the space for the jump. */
2679 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2681 /* We know we are not at the first character of the pattern,
2682 because laststart was nonzero. And we've already
2683 incremented `p', by the way, to be the character after
2684 the `*'. Do we have to do something analogous here
2685 for null bytes, because of RE_DOT_NOT_NULL? */
2686 if (TRANSLATE (*(p - 2)) == TRANSLATE ('.')
2688 && p < pend && TRANSLATE (*p) == TRANSLATE ('\n')
2689 && !(syntax & RE_DOT_NEWLINE))
2690 { /* We have .*\n. */
2691 STORE_JUMP (jump, b, laststart);
2692 keep_string_p = true;
2695 /* Anything else. */
2696 STORE_JUMP (maybe_pop_jump, b, laststart -
2697 (1 + OFFSET_ADDRESS_SIZE));
2699 /* We've added more stuff to the buffer. */
2700 b += 1 + OFFSET_ADDRESS_SIZE;
2703 /* On failure, jump from laststart to b + 3, which will be the
2704 end of the buffer after this jump is inserted. */
2705 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE' instead of
2707 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2708 INSERT_JUMP (keep_string_p ? on_failure_keep_string_jump
2710 laststart, b + 1 + OFFSET_ADDRESS_SIZE);
2712 b += 1 + OFFSET_ADDRESS_SIZE;
2716 /* At least one repetition is required, so insert a
2717 `dummy_failure_jump' before the initial
2718 `on_failure_jump' instruction of the loop. This
2719 effects a skip over that instruction the first time
2720 we hit that loop. */
2721 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
2722 INSERT_JUMP (dummy_failure_jump, laststart, laststart +
2723 2 + 2 * OFFSET_ADDRESS_SIZE);
2724 b += 1 + OFFSET_ADDRESS_SIZE;
2738 boolean had_char_class = false;
2740 CHAR_T range_start = 0xffffffff;
2742 unsigned int range_start = 0xffffffff;
2744 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2747 /* We assume a charset(_not) structure as a wchar_t array.
2748 charset[0] = (re_opcode_t) charset(_not)
2749 charset[1] = l (= length of char_classes)
2750 charset[2] = m (= length of collating_symbols)
2751 charset[3] = n (= length of equivalence_classes)
2752 charset[4] = o (= length of char_ranges)
2753 charset[5] = p (= length of chars)
2755 charset[6] = char_class (wctype_t)
2756 charset[6+CHAR_CLASS_SIZE] = char_class (wctype_t)
2758 charset[l+5] = char_class (wctype_t)
2760 charset[l+6] = collating_symbol (wchar_t)
2762 charset[l+m+5] = collating_symbol (wchar_t)
2763 ifdef _LIBC we use the index if
2764 _NL_COLLATE_SYMB_EXTRAMB instead of
2767 charset[l+m+6] = equivalence_classes (wchar_t)
2769 charset[l+m+n+5] = equivalence_classes (wchar_t)
2770 ifdef _LIBC we use the index in
2771 _NL_COLLATE_WEIGHT instead of
2774 charset[l+m+n+6] = range_start
2775 charset[l+m+n+7] = range_end
2777 charset[l+m+n+2o+4] = range_start
2778 charset[l+m+n+2o+5] = range_end
2779 ifdef _LIBC we use the value looked up
2780 in _NL_COLLATE_COLLSEQ instead of
2783 charset[l+m+n+2o+6] = char
2785 charset[l+m+n+2o+p+5] = char
2789 /* We need at least 6 spaces: the opcode, the length of
2790 char_classes, the length of collating_symbols, the length of
2791 equivalence_classes, the length of char_ranges, the length of
2793 GET_BUFFER_SPACE (6);
2795 /* Save b as laststart. And We use laststart as the pointer
2796 to the first element of the charset here.
2797 In other words, laststart[i] indicates charset[i]. */
2800 /* We test `*p == '^' twice, instead of using an if
2801 statement, so we only need one BUF_PUSH. */
2802 BUF_PUSH (*p == '^' ? charset_not : charset);
2806 /* Push the length of char_classes, the length of
2807 collating_symbols, the length of equivalence_classes, the
2808 length of char_ranges and the length of chars. */
2809 BUF_PUSH_3 (0, 0, 0);
2812 /* Remember the first position in the bracket expression. */
2815 /* charset_not matches newline according to a syntax bit. */
2816 if ((re_opcode_t) b[-6] == charset_not
2817 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
2820 laststart[5]++; /* Update the length of characters */
2823 /* Read in characters and ranges, setting map bits. */
2826 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2830 /* \ might escape characters inside [...] and [^...]. */
2831 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
2833 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
2837 laststart[5]++; /* Update the length of chars */
2842 /* Could be the end of the bracket expression. If it's
2843 not (i.e., when the bracket expression is `[]' so
2844 far), the ']' character bit gets set way below. */
2845 if (c == ']' && p != p1 + 1)
2848 /* Look ahead to see if it's a range when the last thing
2849 was a character class. */
2850 if (had_char_class && c == '-' && *p != ']')
2851 FREE_STACK_RETURN (REG_ERANGE);
2853 /* Look ahead to see if it's a range when the last thing
2854 was a character: if this is a hyphen not at the
2855 beginning or the end of a list, then it's the range
2858 && !(p - 2 >= pattern && p[-2] == '[')
2859 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
2863 /* Allocate the space for range_start and range_end. */
2864 GET_BUFFER_SPACE (2);
2865 /* Update the pointer to indicate end of buffer. */
2867 ret = wcs_compile_range (range_start, &p, pend, translate,
2868 syntax, b, laststart);
2869 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2870 range_start = 0xffffffff;
2872 else if (p[0] == '-' && p[1] != ']')
2873 { /* This handles ranges made up of characters only. */
2876 /* Move past the `-'. */
2878 /* Allocate the space for range_start and range_end. */
2879 GET_BUFFER_SPACE (2);
2880 /* Update the pointer to indicate end of buffer. */
2882 ret = wcs_compile_range (c, &p, pend, translate, syntax, b,
2884 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
2885 range_start = 0xffffffff;
2888 /* See if we're at the beginning of a possible character
2890 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
2891 { /* Leave room for the null. */
2892 char str[CHAR_CLASS_MAX_LENGTH + 1];
2897 /* If pattern is `[[:'. */
2898 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2903 if ((c == ':' && *p == ']') || p == pend)
2905 if (c1 < CHAR_CLASS_MAX_LENGTH)
2908 /* This is in any case an invalid class name. */
2913 /* If isn't a word bracketed by `[:' and `:]':
2914 undo the ending character, the letters, and leave
2915 the leading `:' and `[' (but store them as character). */
2916 if (c == ':' && *p == ']')
2921 /* Query the character class as wctype_t. */
2922 wt = IS_CHAR_CLASS (str);
2924 FREE_STACK_RETURN (REG_ECTYPE);
2926 /* Throw away the ] at the end of the character
2930 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2932 /* Allocate the space for character class. */
2933 GET_BUFFER_SPACE(CHAR_CLASS_SIZE);
2934 /* Update the pointer to indicate end of buffer. */
2935 b += CHAR_CLASS_SIZE;
2936 /* Move data which follow character classes
2937 not to violate the data. */
2938 insert_space(CHAR_CLASS_SIZE,
2939 laststart + 6 + laststart[1],
2941 alignedp = ((uintptr_t)(laststart + 6 + laststart[1])
2942 + __alignof__(wctype_t) - 1)
2943 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
2944 /* Store the character class. */
2945 *((wctype_t*)alignedp) = wt;
2946 /* Update length of char_classes */
2947 laststart[1] += CHAR_CLASS_SIZE;
2949 had_char_class = true;
2958 laststart[5] += 2; /* Update the length of characters */
2960 had_char_class = false;
2963 else if (syntax & RE_CHAR_CLASSES && c == '[' && (*p == '='
2966 CHAR_T str[128]; /* Should be large enough. */
2967 CHAR_T delim = *p; /* '=' or '.' */
2970 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2975 /* If pattern is `[[=' or '[[.'. */
2976 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
2981 if ((c == delim && *p == ']') || p == pend)
2983 if (c1 < sizeof (str) - 1)
2986 /* This is in any case an invalid class name. */
2991 if (c == delim && *p == ']' && str[0] != '\0')
2993 unsigned int i, offset;
2994 /* If we have no collation data we use the default
2995 collation in which each character is in a class
2996 by itself. It also means that ASCII is the
2997 character set and therefore we cannot have character
2998 with more than one byte in the multibyte
3001 /* If not defined _LIBC, we push the name and
3002 `\0' for the sake of matching performance. */
3003 int datasize = c1 + 1;
3011 FREE_STACK_RETURN (REG_ECOLLATE);
3016 const int32_t *table;
3017 const int32_t *weights;
3018 const int32_t *extra;
3019 const int32_t *indirect;
3022 /* This #include defines a local function! */
3023 # include <locale/weightwc.h>
3027 /* We push the index for equivalence class. */
3030 table = (const int32_t *)
3031 _NL_CURRENT (LC_COLLATE,
3032 _NL_COLLATE_TABLEWC);
3033 weights = (const int32_t *)
3034 _NL_CURRENT (LC_COLLATE,
3035 _NL_COLLATE_WEIGHTWC);
3036 extra = (const int32_t *)
3037 _NL_CURRENT (LC_COLLATE,
3038 _NL_COLLATE_EXTRAWC);
3039 indirect = (const int32_t *)
3040 _NL_CURRENT (LC_COLLATE,
3041 _NL_COLLATE_INDIRECTWC);
3043 idx = findidx ((const wint_t**)&cp);
3044 if (idx == 0 || cp < (wint_t*) str + c1)
3045 /* This is no valid character. */
3046 FREE_STACK_RETURN (REG_ECOLLATE);
3048 str[0] = (wchar_t)idx;
3050 else /* delim == '.' */
3052 /* We push collation sequence value
3053 for collating symbol. */
3055 const int32_t *symb_table;
3056 const unsigned char *extra;
3063 /* We have to convert the name to a single-byte
3064 string. This is possible since the names
3065 consist of ASCII characters and the internal
3066 representation is UCS4. */
3067 for (i = 0; i < c1; ++i)
3068 char_str[i] = str[i];
3071 _NL_CURRENT_WORD (LC_COLLATE,
3072 _NL_COLLATE_SYMB_HASH_SIZEMB);
3073 symb_table = (const int32_t *)
3074 _NL_CURRENT (LC_COLLATE,
3075 _NL_COLLATE_SYMB_TABLEMB);
3076 extra = (const unsigned char *)
3077 _NL_CURRENT (LC_COLLATE,
3078 _NL_COLLATE_SYMB_EXTRAMB);
3080 /* Locate the character in the hashing table. */
3081 hash = elem_hash (char_str, c1);
3084 elem = hash % table_size;
3085 second = hash % (table_size - 2);
3086 while (symb_table[2 * elem] != 0)
3088 /* First compare the hashing value. */
3089 if (symb_table[2 * elem] == hash
3090 && c1 == extra[symb_table[2 * elem + 1]]
3091 && memcmp (char_str,
3092 &extra[symb_table[2 * elem + 1]
3095 /* Yep, this is the entry. */
3096 idx = symb_table[2 * elem + 1];
3097 idx += 1 + extra[idx];
3105 if (symb_table[2 * elem] != 0)
3107 /* Compute the index of the byte sequence
3109 idx += 1 + extra[idx];
3110 /* Adjust for the alignment. */
3111 idx = (idx + 3) & ~3;
3113 str[0] = (wchar_t) idx + 4;
3115 else if (symb_table[2 * elem] == 0 && c1 == 1)
3117 /* No valid character. Match it as a
3118 single byte character. */
3119 had_char_class = false;
3121 /* Update the length of characters */
3123 range_start = str[0];
3125 /* Throw away the ] at the end of the
3126 collating symbol. */
3128 /* exit from the switch block. */
3132 FREE_STACK_RETURN (REG_ECOLLATE);
3137 /* Throw away the ] at the end of the equivalence
3138 class (or collating symbol). */
3141 /* Allocate the space for the equivalence class
3142 (or collating symbol) (and '\0' if needed). */
3143 GET_BUFFER_SPACE(datasize);
3144 /* Update the pointer to indicate end of buffer. */
3148 { /* equivalence class */
3149 /* Calculate the offset of char_ranges,
3150 which is next to equivalence_classes. */
3151 offset = laststart[1] + laststart[2]
3154 insert_space(datasize, laststart + offset, b - 1);
3156 /* Write the equivalence_class and \0. */
3157 for (i = 0 ; i < datasize ; i++)
3158 laststart[offset + i] = str[i];
3160 /* Update the length of equivalence_classes. */
3161 laststart[3] += datasize;
3162 had_char_class = true;
3164 else /* delim == '.' */
3165 { /* collating symbol */
3166 /* Calculate the offset of the equivalence_classes,
3167 which is next to collating_symbols. */
3168 offset = laststart[1] + laststart[2] + 6;
3169 /* Insert space and write the collationg_symbol
3171 insert_space(datasize, laststart + offset, b-1);
3172 for (i = 0 ; i < datasize ; i++)
3173 laststart[offset + i] = str[i];
3175 /* In re_match_2_internal if range_start < -1, we
3176 assume -range_start is the offset of the
3177 collating symbol which is specified as
3178 the character of the range start. So we assign
3179 -(laststart[1] + laststart[2] + 6) to
3181 range_start = -(laststart[1] + laststart[2] + 6);
3182 /* Update the length of collating_symbol. */
3183 laststart[2] += datasize;
3184 had_char_class = false;
3194 laststart[5] += 2; /* Update the length of characters */
3195 range_start = delim;
3196 had_char_class = false;
3201 had_char_class = false;
3203 laststart[5]++; /* Update the length of characters */
3209 /* Ensure that we have enough space to push a charset: the
3210 opcode, the length count, and the bitset; 34 bytes in all. */
3211 GET_BUFFER_SPACE (34);
3215 /* We test `*p == '^' twice, instead of using an if
3216 statement, so we only need one BUF_PUSH. */
3217 BUF_PUSH (*p == '^' ? charset_not : charset);
3221 /* Remember the first position in the bracket expression. */
3224 /* Push the number of bytes in the bitmap. */
3225 BUF_PUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
3227 /* Clear the whole map. */
3228 bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
3230 /* charset_not matches newline according to a syntax bit. */
3231 if ((re_opcode_t) b[-2] == charset_not
3232 && (syntax & RE_HAT_LISTS_NOT_NEWLINE))
3233 SET_LIST_BIT ('\n');
3235 /* Read in characters and ranges, setting map bits. */
3238 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3242 /* \ might escape characters inside [...] and [^...]. */
3243 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
3245 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3253 /* Could be the end of the bracket expression. If it's
3254 not (i.e., when the bracket expression is `[]' so
3255 far), the ']' character bit gets set way below. */
3256 if (c == ']' && p != p1 + 1)
3259 /* Look ahead to see if it's a range when the last thing
3260 was a character class. */
3261 if (had_char_class && c == '-' && *p != ']')
3262 FREE_STACK_RETURN (REG_ERANGE);
3264 /* Look ahead to see if it's a range when the last thing
3265 was a character: if this is a hyphen not at the
3266 beginning or the end of a list, then it's the range
3269 && !(p - 2 >= pattern && p[-2] == '[')
3270 && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
3274 = byte_compile_range (range_start, &p, pend, translate,
3276 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3277 range_start = 0xffffffff;
3280 else if (p[0] == '-' && p[1] != ']')
3281 { /* This handles ranges made up of characters only. */
3284 /* Move past the `-'. */
3287 ret = byte_compile_range (c, &p, pend, translate, syntax, b);
3288 if (ret != REG_NOERROR) FREE_STACK_RETURN (ret);
3289 range_start = 0xffffffff;
3292 /* See if we're at the beginning of a possible character
3295 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == ':')
3296 { /* Leave room for the null. */
3297 char str[CHAR_CLASS_MAX_LENGTH + 1];
3302 /* If pattern is `[[:'. */
3303 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3308 if ((c == ':' && *p == ']') || p == pend)
3310 if (c1 < CHAR_CLASS_MAX_LENGTH)
3313 /* This is in any case an invalid class name. */
3318 /* If isn't a word bracketed by `[:' and `:]':
3319 undo the ending character, the letters, and leave
3320 the leading `:' and `[' (but set bits for them). */
3321 if (c == ':' && *p == ']')
3323 # if defined _LIBC || WIDE_CHAR_SUPPORT
3324 boolean is_lower = STREQ (str, "lower");
3325 boolean is_upper = STREQ (str, "upper");
3329 wt = IS_CHAR_CLASS (str);
3331 FREE_STACK_RETURN (REG_ECTYPE);
3333 /* Throw away the ] at the end of the character
3337 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3339 for (ch = 0; ch < 1 << BYTEWIDTH; ++ch)
3342 if (__iswctype (__btowc (ch), wt))
3345 if (iswctype (btowc (ch), wt))
3349 if (translate && (is_upper || is_lower)
3350 && (ISUPPER (ch) || ISLOWER (ch)))
3354 had_char_class = true;
3357 boolean is_alnum = STREQ (str, "alnum");
3358 boolean is_alpha = STREQ (str, "alpha");
3359 boolean is_blank = STREQ (str, "blank");
3360 boolean is_cntrl = STREQ (str, "cntrl");
3361 boolean is_digit = STREQ (str, "digit");
3362 boolean is_graph = STREQ (str, "graph");
3363 boolean is_lower = STREQ (str, "lower");
3364 boolean is_print = STREQ (str, "print");
3365 boolean is_punct = STREQ (str, "punct");
3366 boolean is_space = STREQ (str, "space");
3367 boolean is_upper = STREQ (str, "upper");
3368 boolean is_xdigit = STREQ (str, "xdigit");
3370 if (!IS_CHAR_CLASS (str))
3371 FREE_STACK_RETURN (REG_ECTYPE);
3373 /* Throw away the ] at the end of the character
3377 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3379 for (ch = 0; ch < 1 << BYTEWIDTH; ch++)
3381 /* This was split into 3 if's to
3382 avoid an arbitrary limit in some compiler. */
3383 if ( (is_alnum && ISALNUM (ch))
3384 || (is_alpha && ISALPHA (ch))
3385 || (is_blank && ISBLANK (ch))
3386 || (is_cntrl && ISCNTRL (ch)))
3388 if ( (is_digit && ISDIGIT (ch))
3389 || (is_graph && ISGRAPH (ch))
3390 || (is_lower && ISLOWER (ch))
3391 || (is_print && ISPRINT (ch)))
3393 if ( (is_punct && ISPUNCT (ch))
3394 || (is_space && ISSPACE (ch))
3395 || (is_upper && ISUPPER (ch))
3396 || (is_xdigit && ISXDIGIT (ch)))
3398 if ( translate && (is_upper || is_lower)
3399 && (ISUPPER (ch) || ISLOWER (ch)))
3402 had_char_class = true;
3403 # endif /* libc || wctype.h */
3413 had_char_class = false;
3416 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '=')
3418 unsigned char str[MB_LEN_MAX + 1];
3421 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3427 /* If pattern is `[[='. */
3428 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3433 if ((c == '=' && *p == ']') || p == pend)
3435 if (c1 < MB_LEN_MAX)
3438 /* This is in any case an invalid class name. */
3443 if (c == '=' && *p == ']' && str[0] != '\0')
3445 /* If we have no collation data we use the default
3446 collation in which each character is in a class
3447 by itself. It also means that ASCII is the
3448 character set and therefore we cannot have character
3449 with more than one byte in the multibyte
3456 FREE_STACK_RETURN (REG_ECOLLATE);
3458 /* Throw away the ] at the end of the equivalence
3462 /* Set the bit for the character. */
3463 SET_LIST_BIT (str[0]);
3468 /* Try to match the byte sequence in `str' against
3469 those known to the collate implementation.
3470 First find out whether the bytes in `str' are
3471 actually from exactly one character. */
3472 const int32_t *table;
3473 const unsigned char *weights;
3474 const unsigned char *extra;
3475 const int32_t *indirect;
3477 const unsigned char *cp = str;
3480 /* This #include defines a local function! */
3481 # include <locale/weight.h>
3483 table = (const int32_t *)
3484 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3485 weights = (const unsigned char *)
3486 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3487 extra = (const unsigned char *)
3488 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3489 indirect = (const int32_t *)
3490 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3492 idx = findidx (&cp);
3493 if (idx == 0 || cp < str + c1)
3494 /* This is no valid character. */
3495 FREE_STACK_RETURN (REG_ECOLLATE);
3497 /* Throw away the ] at the end of the equivalence
3501 /* Now we have to go throught the whole table
3502 and find all characters which have the same
3505 XXX Note that this is not entirely correct.
3506 we would have to match multibyte sequences
3507 but this is not possible with the current
3509 for (ch = 1; ch < 256; ++ch)
3510 /* XXX This test would have to be changed if we
3511 would allow matching multibyte sequences. */
3514 int32_t idx2 = table[ch];
3515 size_t len = weights[idx2];
3517 /* Test whether the lenghts match. */
3518 if (weights[idx] == len)
3520 /* They do. New compare the bytes of
3525 && (weights[idx + 1 + cnt]
3526 == weights[idx2 + 1 + cnt]))
3530 /* They match. Mark the character as
3537 had_char_class = true;
3547 had_char_class = false;
3550 else if (syntax & RE_CHAR_CLASSES && c == '[' && *p == '.')
3552 unsigned char str[128]; /* Should be large enough. */
3555 _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3561 /* If pattern is `[[.'. */
3562 if (p == pend) FREE_STACK_RETURN (REG_EBRACK);
3567 if ((c == '.' && *p == ']') || p == pend)
3569 if (c1 < sizeof (str))
3572 /* This is in any case an invalid class name. */
3577 if (c == '.' && *p == ']' && str[0] != '\0')
3579 /* If we have no collation data we use the default
3580 collation in which each character is the name
3581 for its own class which contains only the one
3582 character. It also means that ASCII is the
3583 character set and therefore we cannot have character
3584 with more than one byte in the multibyte
3591 FREE_STACK_RETURN (REG_ECOLLATE);
3593 /* Throw away the ] at the end of the equivalence
3597 /* Set the bit for the character. */
3598 SET_LIST_BIT (str[0]);
3599 range_start = ((const unsigned char *) str)[0];
3604 /* Try to match the byte sequence in `str' against
3605 those known to the collate implementation.
3606 First find out whether the bytes in `str' are
3607 actually from exactly one character. */
3609 const int32_t *symb_table;
3610 const unsigned char *extra;
3617 _NL_CURRENT_WORD (LC_COLLATE,
3618 _NL_COLLATE_SYMB_HASH_SIZEMB);
3619 symb_table = (const int32_t *)
3620 _NL_CURRENT (LC_COLLATE,
3621 _NL_COLLATE_SYMB_TABLEMB);
3622 extra = (const unsigned char *)
3623 _NL_CURRENT (LC_COLLATE,
3624 _NL_COLLATE_SYMB_EXTRAMB);
3626 /* Locate the character in the hashing table. */
3627 hash = elem_hash (str, c1);
3630 elem = hash % table_size;
3631 second = hash % (table_size - 2);
3632 while (symb_table[2 * elem] != 0)
3634 /* First compare the hashing value. */
3635 if (symb_table[2 * elem] == hash
3636 && c1 == extra[symb_table[2 * elem + 1]]
3638 &extra[symb_table[2 * elem + 1]
3642 /* Yep, this is the entry. */
3643 idx = symb_table[2 * elem + 1];
3644 idx += 1 + extra[idx];
3652 if (symb_table[2 * elem] == 0)
3653 /* This is no valid character. */
3654 FREE_STACK_RETURN (REG_ECOLLATE);
3656 /* Throw away the ] at the end of the equivalence
3660 /* Now add the multibyte character(s) we found
3663 XXX Note that this is not entirely correct.
3664 we would have to match multibyte sequences
3665 but this is not possible with the current
3666 implementation. Also, we have to match
3667 collating symbols, which expand to more than
3668 one file, as a whole and not allow the
3669 individual bytes. */
3672 range_start = extra[idx];
3675 SET_LIST_BIT (extra[idx]);
3680 had_char_class = false;
3690 had_char_class = false;
3695 had_char_class = false;
3701 /* Discard any (non)matching list bytes that are all 0 at the
3702 end of the map. Decrease the map-length byte too. */
3703 while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
3712 if (syntax & RE_NO_BK_PARENS)
3719 if (syntax & RE_NO_BK_PARENS)
3726 if (syntax & RE_NEWLINE_ALT)
3733 if (syntax & RE_NO_BK_VBAR)
3740 if (syntax & RE_INTERVALS && syntax & RE_NO_BK_BRACES)
3741 goto handle_interval;
3747 if (p == pend) FREE_STACK_RETURN (REG_EESCAPE);
3749 /* Do not translate the character after the \, so that we can
3750 distinguish, e.g., \B from \b, even if we normally would
3751 translate, e.g., B to b. */
3757 if (syntax & RE_NO_BK_PARENS)
3758 goto normal_backslash;
3764 if (COMPILE_STACK_FULL)
3766 RETALLOC (compile_stack.stack, compile_stack.size << 1,
3767 compile_stack_elt_t);
3768 if (compile_stack.stack == NULL) return REG_ESPACE;
3770 compile_stack.size <<= 1;
3773 /* These are the values to restore when we hit end of this
3774 group. They are all relative offsets, so that if the
3775 whole pattern moves because of realloc, they will still
3777 COMPILE_STACK_TOP.begalt_offset = begalt - COMPILED_BUFFER_VAR;
3778 COMPILE_STACK_TOP.fixup_alt_jump
3779 = fixup_alt_jump ? fixup_alt_jump - COMPILED_BUFFER_VAR + 1 : 0;
3780 COMPILE_STACK_TOP.laststart_offset = b - COMPILED_BUFFER_VAR;
3781 COMPILE_STACK_TOP.regnum = regnum;
3783 /* We will eventually replace the 0 with the number of
3784 groups inner to this one. But do not push a
3785 start_memory for groups beyond the last one we can
3786 represent in the compiled pattern. */
3787 if (regnum <= MAX_REGNUM)
3789 COMPILE_STACK_TOP.inner_group_offset = b
3790 - COMPILED_BUFFER_VAR + 2;
3791 BUF_PUSH_3 (start_memory, regnum, 0);
3794 compile_stack.avail++;
3799 /* If we've reached MAX_REGNUM groups, then this open
3800 won't actually generate any code, so we'll have to
3801 clear pending_exact explicitly. */
3807 if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
3809 if (COMPILE_STACK_EMPTY)
3811 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3812 goto normal_backslash;
3814 FREE_STACK_RETURN (REG_ERPAREN);
3819 { /* Push a dummy failure point at the end of the
3820 alternative for a possible future
3821 `pop_failure_jump' to pop. See comments at
3822 `push_dummy_failure' in `re_match_2'. */
3823 BUF_PUSH (push_dummy_failure);
3825 /* We allocated space for this jump when we assigned
3826 to `fixup_alt_jump', in the `handle_alt' case below. */
3827 STORE_JUMP (jump_past_alt, fixup_alt_jump, b - 1);
3830 /* See similar code for backslashed left paren above. */
3831 if (COMPILE_STACK_EMPTY)
3833 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
3836 FREE_STACK_RETURN (REG_ERPAREN);
3839 /* Since we just checked for an empty stack above, this
3840 ``can't happen''. */
3841 assert (compile_stack.avail != 0);
3843 /* We don't just want to restore into `regnum', because
3844 later groups should continue to be numbered higher,
3845 as in `(ab)c(de)' -- the second group is #2. */
3846 regnum_t this_group_regnum;
3848 compile_stack.avail--;
3849 begalt = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.begalt_offset;
3851 = COMPILE_STACK_TOP.fixup_alt_jump
3852 ? COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.fixup_alt_jump - 1
3854 laststart = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.laststart_offset;
3855 this_group_regnum = COMPILE_STACK_TOP.regnum;
3856 /* If we've reached MAX_REGNUM groups, then this open
3857 won't actually generate any code, so we'll have to
3858 clear pending_exact explicitly. */
3861 /* We're at the end of the group, so now we know how many
3862 groups were inside this one. */
3863 if (this_group_regnum <= MAX_REGNUM)
3865 UCHAR_T *inner_group_loc
3866 = COMPILED_BUFFER_VAR + COMPILE_STACK_TOP.inner_group_offset;
3868 *inner_group_loc = regnum - this_group_regnum;
3869 BUF_PUSH_3 (stop_memory, this_group_regnum,
3870 regnum - this_group_regnum);
3876 case '|': /* `\|'. */
3877 if (syntax & RE_LIMITED_OPS || syntax & RE_NO_BK_VBAR)
3878 goto normal_backslash;
3880 if (syntax & RE_LIMITED_OPS)
3883 /* Insert before the previous alternative a jump which
3884 jumps to this alternative if the former fails. */
3885 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3886 INSERT_JUMP (on_failure_jump, begalt,
3887 b + 2 + 2 * OFFSET_ADDRESS_SIZE);
3889 b += 1 + OFFSET_ADDRESS_SIZE;
3891 /* The alternative before this one has a jump after it
3892 which gets executed if it gets matched. Adjust that
3893 jump so it will jump to this alternative's analogous
3894 jump (put in below, which in turn will jump to the next
3895 (if any) alternative's such jump, etc.). The last such
3896 jump jumps to the correct final destination. A picture:
3902 If we are at `b', then fixup_alt_jump right now points to a
3903 three-byte space after `a'. We'll put in the jump, set
3904 fixup_alt_jump to right after `b', and leave behind three
3905 bytes which we'll fill in when we get to after `c'. */
3908 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
3910 /* Mark and leave space for a jump after this alternative,
3911 to be filled in later either by next alternative or
3912 when know we're at the end of a series of alternatives. */
3914 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3915 b += 1 + OFFSET_ADDRESS_SIZE;
3923 /* If \{ is a literal. */
3924 if (!(syntax & RE_INTERVALS)
3925 /* If we're at `\{' and it's not the open-interval
3927 || (syntax & RE_NO_BK_BRACES))
3928 goto normal_backslash;
3932 /* If got here, then the syntax allows intervals. */
3934 /* At least (most) this many matches must be made. */
3935 int lower_bound = -1, upper_bound = -1;
3937 /* Place in the uncompiled pattern (i.e., just after
3938 the '{') to go back to if the interval is invalid. */
3939 const CHAR_T *beg_interval = p;
3942 goto invalid_interval;
3944 GET_UNSIGNED_NUMBER (lower_bound);
3948 GET_UNSIGNED_NUMBER (upper_bound);
3949 if (upper_bound < 0)
3950 upper_bound = RE_DUP_MAX;
3953 /* Interval such as `{1}' => match exactly once. */
3954 upper_bound = lower_bound;
3956 if (! (0 <= lower_bound && lower_bound <= upper_bound))
3957 goto invalid_interval;
3959 if (!(syntax & RE_NO_BK_BRACES))
3961 if (c != '\\' || p == pend)
3962 goto invalid_interval;
3967 goto invalid_interval;
3969 /* If it's invalid to have no preceding re. */
3972 if (syntax & RE_CONTEXT_INVALID_OPS
3973 && !(syntax & RE_INVALID_INTERVAL_ORD))
3974 FREE_STACK_RETURN (REG_BADRPT);
3975 else if (syntax & RE_CONTEXT_INDEP_OPS)
3978 goto unfetch_interval;
3981 /* We just parsed a valid interval. */
3983 if (RE_DUP_MAX < upper_bound)
3984 FREE_STACK_RETURN (REG_BADBR);
3986 /* If the upper bound is zero, don't want to succeed at
3987 all; jump from `laststart' to `b + 3', which will be
3988 the end of the buffer after we insert the jump. */
3989 /* ifdef WCHAR, 'b + 1 + OFFSET_ADDRESS_SIZE'
3990 instead of 'b + 3'. */
3991 if (upper_bound == 0)
3993 GET_BUFFER_SPACE (1 + OFFSET_ADDRESS_SIZE);
3994 INSERT_JUMP (jump, laststart, b + 1
3995 + OFFSET_ADDRESS_SIZE);
3996 b += 1 + OFFSET_ADDRESS_SIZE;
3999 /* Otherwise, we have a nontrivial interval. When
4000 we're all done, the pattern will look like:
4001 set_number_at <jump count> <upper bound>
4002 set_number_at <succeed_n count> <lower bound>
4003 succeed_n <after jump addr> <succeed_n count>
4005 jump_n <succeed_n addr> <jump count>
4006 (The upper bound and `jump_n' are omitted if
4007 `upper_bound' is 1, though.) */
4009 { /* If the upper bound is > 1, we need to insert
4010 more at the end of the loop. */
4011 unsigned nbytes = 2 + 4 * OFFSET_ADDRESS_SIZE +
4012 (upper_bound > 1) * (2 + 4 * OFFSET_ADDRESS_SIZE);
4014 GET_BUFFER_SPACE (nbytes);
4016 /* Initialize lower bound of the `succeed_n', even
4017 though it will be set during matching by its
4018 attendant `set_number_at' (inserted next),
4019 because `re_compile_fastmap' needs to know.
4020 Jump to the `jump_n' we might insert below. */
4021 INSERT_JUMP2 (succeed_n, laststart,
4022 b + 1 + 2 * OFFSET_ADDRESS_SIZE
4023 + (upper_bound > 1) * (1 + 2 * OFFSET_ADDRESS_SIZE)
4025 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
4027 /* Code to initialize the lower bound. Insert
4028 before the `succeed_n'. The `5' is the last two
4029 bytes of this `set_number_at', plus 3 bytes of
4030 the following `succeed_n'. */
4031 /* ifdef WCHAR, The '1+2*OFFSET_ADDRESS_SIZE'
4032 is the 'set_number_at', plus '1+OFFSET_ADDRESS_SIZE'
4033 of the following `succeed_n'. */
4034 PREFIX(insert_op2) (set_number_at, laststart, 1
4035 + 2 * OFFSET_ADDRESS_SIZE, lower_bound, b);
4036 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
4038 if (upper_bound > 1)
4039 { /* More than one repetition is allowed, so
4040 append a backward jump to the `succeed_n'
4041 that starts this interval.
4043 When we've reached this during matching,
4044 we'll have matched the interval once, so
4045 jump back only `upper_bound - 1' times. */
4046 STORE_JUMP2 (jump_n, b, laststart
4047 + 2 * OFFSET_ADDRESS_SIZE + 1,
4049 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
4051 /* The location we want to set is the second
4052 parameter of the `jump_n'; that is `b-2' as
4053 an absolute address. `laststart' will be
4054 the `set_number_at' we're about to insert;
4055 `laststart+3' the number to set, the source
4056 for the relative address. But we are
4057 inserting into the middle of the pattern --
4058 so everything is getting moved up by 5.
4059 Conclusion: (b - 2) - (laststart + 3) + 5,
4060 i.e., b - laststart.
4062 We insert this at the beginning of the loop
4063 so that if we fail during matching, we'll
4064 reinitialize the bounds. */
4065 PREFIX(insert_op2) (set_number_at, laststart,
4067 upper_bound - 1, b);
4068 b += 1 + 2 * OFFSET_ADDRESS_SIZE;
4075 if (!(syntax & RE_INVALID_INTERVAL_ORD))
4076 FREE_STACK_RETURN (p == pend ? REG_EBRACE : REG_BADBR);
4078 /* Match the characters as literals. */
4081 if (syntax & RE_NO_BK_BRACES)
4084 goto normal_backslash;
4088 /* There is no way to specify the before_dot and after_dot
4089 operators. rms says this is ok. --karl */
4097 BUF_PUSH_2 (syntaxspec, syntax_spec_code[c]);
4103 BUF_PUSH_2 (notsyntaxspec, syntax_spec_code[c]);
4109 if (syntax & RE_NO_GNU_OPS)
4112 BUF_PUSH (wordchar);
4117 if (syntax & RE_NO_GNU_OPS)
4120 BUF_PUSH (notwordchar);
4125 if (syntax & RE_NO_GNU_OPS)
4131 if (syntax & RE_NO_GNU_OPS)
4137 if (syntax & RE_NO_GNU_OPS)
4139 BUF_PUSH (wordbound);
4143 if (syntax & RE_NO_GNU_OPS)
4145 BUF_PUSH (notwordbound);
4149 if (syntax & RE_NO_GNU_OPS)
4155 if (syntax & RE_NO_GNU_OPS)
4160 case '1': case '2': case '3': case '4': case '5':
4161 case '6': case '7': case '8': case '9':
4162 if (syntax & RE_NO_BK_REFS)
4168 FREE_STACK_RETURN (REG_ESUBREG);
4170 /* Can't back reference to a subexpression if inside of it. */
4171 if (group_in_compile_stack (compile_stack, (regnum_t) c1))
4175 BUF_PUSH_2 (duplicate, c1);
4181 if (syntax & RE_BK_PLUS_QM)
4184 goto normal_backslash;
4188 /* You might think it would be useful for \ to mean
4189 not to translate; but if we don't translate it
4190 it will never match anything. */
4198 /* Expects the character in `c'. */
4200 /* If no exactn currently being built. */
4203 /* If last exactn handle binary(or character) and
4204 new exactn handle character(or binary). */
4205 || is_exactn_bin != is_binary[p - 1 - pattern]
4208 /* If last exactn not at current position. */
4209 || pending_exact + *pending_exact + 1 != b
4211 /* We have only one byte following the exactn for the count. */
4212 || *pending_exact == (1 << BYTEWIDTH) - 1
4214 /* If followed by a repetition operator. */
4215 || *p == '*' || *p == '^'
4216 || ((syntax & RE_BK_PLUS_QM)
4217 ? *p == '\\' && (p[1] == '+' || p[1] == '?')
4218 : (*p == '+' || *p == '?'))
4219 || ((syntax & RE_INTERVALS)
4220 && ((syntax & RE_NO_BK_BRACES)
4222 : (p[0] == '\\' && p[1] == '{'))))
4224 /* Start building a new exactn. */
4229 /* Is this exactn binary data or character? */
4230 is_exactn_bin = is_binary[p - 1 - pattern];
4232 BUF_PUSH_2 (exactn_bin, 0);
4234 BUF_PUSH_2 (exactn, 0);
4236 BUF_PUSH_2 (exactn, 0);
4238 pending_exact = b - 1;
4245 } /* while p != pend */
4248 /* Through the pattern now. */
4251 STORE_JUMP (jump_past_alt, fixup_alt_jump, b);
4253 if (!COMPILE_STACK_EMPTY)
4254 FREE_STACK_RETURN (REG_EPAREN);
4256 /* If we don't want backtracking, force success
4257 the first time we reach the end of the compiled pattern. */
4258 if (syntax & RE_NO_POSIX_BACKTRACKING)
4266 free (compile_stack.stack);
4268 /* We have succeeded; set the length of the buffer. */
4270 bufp->used = (uintptr_t) b - (uintptr_t) COMPILED_BUFFER_VAR;
4272 bufp->used = b - bufp->buffer;
4278 DEBUG_PRINT1 ("\nCompiled pattern: \n");
4279 PREFIX(print_compiled_pattern) (bufp);
4283 #ifndef MATCH_MAY_ALLOCATE
4284 /* Initialize the failure stack to the largest possible stack. This
4285 isn't necessary unless we're trying to avoid calling alloca in
4286 the search and match routines. */
4288 int num_regs = bufp->re_nsub + 1;
4290 /* Since DOUBLE_FAIL_STACK refuses to double only if the current size
4291 is strictly greater than re_max_failures, the largest possible stack
4292 is 2 * re_max_failures failure points. */
4293 if (fail_stack.size < (2 * re_max_failures * MAX_FAILURE_ITEMS))
4295 fail_stack.size = (2 * re_max_failures * MAX_FAILURE_ITEMS);
4298 if (! fail_stack.stack)
4300 = (PREFIX(fail_stack_elt_t) *) xmalloc (fail_stack.size
4301 * sizeof (PREFIX(fail_stack_elt_t)));
4304 = (PREFIX(fail_stack_elt_t) *) xrealloc (fail_stack.stack,
4306 * sizeof (PREFIX(fail_stack_elt_t))));
4307 # else /* not emacs */
4308 if (! fail_stack.stack)
4310 = (PREFIX(fail_stack_elt_t) *) malloc (fail_stack.size
4311 * sizeof (PREFIX(fail_stack_elt_t)));
4314 = (PREFIX(fail_stack_elt_t) *) realloc (fail_stack.stack,
4316 * sizeof (PREFIX(fail_stack_elt_t))));
4317 # endif /* not emacs */
4320 PREFIX(regex_grow_registers) (num_regs);
4322 #endif /* not MATCH_MAY_ALLOCATE */
4325 } /* regex_compile */
4327 /* Subroutines for `regex_compile'. */
4329 /* Store OP at LOC followed by two-byte integer parameter ARG. */
4330 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4333 PREFIX(store_op1) (op, loc, arg)
4338 *loc = (UCHAR_T) op;
4339 STORE_NUMBER (loc + 1, arg);
4343 /* Like `store_op1', but for two two-byte parameters ARG1 and ARG2. */
4344 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4347 PREFIX(store_op2) (op, loc, arg1, arg2)
4352 *loc = (UCHAR_T) op;
4353 STORE_NUMBER (loc + 1, arg1);
4354 STORE_NUMBER (loc + 1 + OFFSET_ADDRESS_SIZE, arg2);
4358 /* Copy the bytes from LOC to END to open up three bytes of space at LOC
4359 for OP followed by two-byte integer parameter ARG. */
4360 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4363 PREFIX(insert_op1) (op, loc, arg, end)
4369 register UCHAR_T *pfrom = end;
4370 register UCHAR_T *pto = end + 1 + OFFSET_ADDRESS_SIZE;
4372 while (pfrom != loc)
4375 PREFIX(store_op1) (op, loc, arg);
4379 /* Like `insert_op1', but for two two-byte parameters ARG1 and ARG2. */
4380 /* ifdef WCHAR, integer parameter is 1 wchar_t. */
4383 PREFIX(insert_op2) (op, loc, arg1, arg2, end)
4389 register UCHAR_T *pfrom = end;
4390 register UCHAR_T *pto = end + 1 + 2 * OFFSET_ADDRESS_SIZE;
4392 while (pfrom != loc)
4395 PREFIX(store_op2) (op, loc, arg1, arg2);
4399 /* P points to just after a ^ in PATTERN. Return true if that ^ comes
4400 after an alternative or a begin-subexpression. We assume there is at
4401 least one character before the ^. */
4404 PREFIX(at_begline_loc_p) (pattern, p, syntax)
4405 const CHAR_T *pattern, *p;
4406 reg_syntax_t syntax;
4408 const CHAR_T *prev = p - 2;
4409 boolean prev_prev_backslash = prev > pattern && prev[-1] == '\\';
4412 /* After a subexpression? */
4413 (*prev == '(' && (syntax & RE_NO_BK_PARENS || prev_prev_backslash))
4414 /* After an alternative? */
4415 || (*prev == '|' && (syntax & RE_NO_BK_VBAR || prev_prev_backslash));
4419 /* The dual of at_begline_loc_p. This one is for $. We assume there is
4420 at least one character after the $, i.e., `P < PEND'. */
4423 PREFIX(at_endline_loc_p) (p, pend, syntax)
4424 const CHAR_T *p, *pend;
4425 reg_syntax_t syntax;
4427 const CHAR_T *next = p;
4428 boolean next_backslash = *next == '\\';
4429 const CHAR_T *next_next = p + 1 < pend ? p + 1 : 0;
4432 /* Before a subexpression? */
4433 (syntax & RE_NO_BK_PARENS ? *next == ')'
4434 : next_backslash && next_next && *next_next == ')')
4435 /* Before an alternative? */
4436 || (syntax & RE_NO_BK_VBAR ? *next == '|'
4437 : next_backslash && next_next && *next_next == '|');
4440 #else /* not INSIDE_RECURSION */
4442 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
4443 false if it's not. */
4446 group_in_compile_stack (compile_stack, regnum)
4447 compile_stack_type compile_stack;
4452 for (this_element = compile_stack.avail - 1;
4455 if (compile_stack.stack[this_element].regnum == regnum)
4460 #endif /* not INSIDE_RECURSION */
4462 #ifdef INSIDE_RECURSION
4465 /* This insert space, which size is "num", into the pattern at "loc".
4466 "end" must point the end of the allocated buffer. */
4468 insert_space (num, loc, end)
4473 register CHAR_T *pto = end;
4474 register CHAR_T *pfrom = end - num;
4476 while (pfrom >= loc)
4482 static reg_errcode_t
4483 wcs_compile_range (range_start_char, p_ptr, pend, translate, syntax, b,
4485 CHAR_T range_start_char;
4486 const CHAR_T **p_ptr, *pend;
4487 CHAR_T *char_set, *b;
4488 RE_TRANSLATE_TYPE translate;
4489 reg_syntax_t syntax;
4491 const CHAR_T *p = *p_ptr;
4492 CHAR_T range_start, range_end;
4496 uint32_t start_val, end_val;
4502 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4505 const char *collseq = (const char *) _NL_CURRENT(LC_COLLATE,
4506 _NL_COLLATE_COLLSEQWC);
4507 const unsigned char *extra = (const unsigned char *)
4508 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4510 if (range_start_char < -1)
4512 /* range_start is a collating symbol. */
4514 /* Retreive the index and get collation sequence value. */
4515 wextra = (int32_t*)(extra + char_set[-range_start_char]);
4516 start_val = wextra[1 + *wextra];
4519 start_val = collseq_table_lookup(collseq, TRANSLATE(range_start_char));
4521 end_val = collseq_table_lookup (collseq, TRANSLATE (p[0]));
4523 /* Report an error if the range is empty and the syntax prohibits
4525 ret = ((syntax & RE_NO_EMPTY_RANGES)
4526 && (start_val > end_val))? REG_ERANGE : REG_NOERROR;
4528 /* Insert space to the end of the char_ranges. */
4529 insert_space(2, b - char_set[5] - 2, b - 1);
4530 *(b - char_set[5] - 2) = (wchar_t)start_val;
4531 *(b - char_set[5] - 1) = (wchar_t)end_val;
4532 char_set[4]++; /* ranges_index */
4537 range_start = (range_start_char >= 0)? TRANSLATE (range_start_char):
4539 range_end = TRANSLATE (p[0]);
4540 /* Report an error if the range is empty and the syntax prohibits
4542 ret = ((syntax & RE_NO_EMPTY_RANGES)
4543 && (range_start > range_end))? REG_ERANGE : REG_NOERROR;
4545 /* Insert space to the end of the char_ranges. */
4546 insert_space(2, b - char_set[5] - 2, b - 1);
4547 *(b - char_set[5] - 2) = range_start;
4548 *(b - char_set[5] - 1) = range_end;
4549 char_set[4]++; /* ranges_index */
4551 /* Have to increment the pointer into the pattern string, so the
4552 caller isn't still at the ending character. */
4558 /* Read the ending character of a range (in a bracket expression) from the
4559 uncompiled pattern *P_PTR (which ends at PEND). We assume the
4560 starting character is in `P[-2]'. (`P[-1]' is the character `-'.)
4561 Then we set the translation of all bits between the starting and
4562 ending characters (inclusive) in the compiled pattern B.
4564 Return an error code.
4566 We use these short variable names so we can use the same macros as
4567 `regex_compile' itself. */
4569 static reg_errcode_t
4570 byte_compile_range (range_start_char, p_ptr, pend, translate, syntax, b)
4571 unsigned int range_start_char;
4572 const char **p_ptr, *pend;
4573 RE_TRANSLATE_TYPE translate;
4574 reg_syntax_t syntax;
4578 const char *p = *p_ptr;
4581 const unsigned char *collseq;
4582 unsigned int start_colseq;
4583 unsigned int end_colseq;
4591 /* Have to increment the pointer into the pattern string, so the
4592 caller isn't still at the ending character. */
4595 /* Report an error if the range is empty and the syntax prohibits this. */
4596 ret = syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
4599 collseq = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
4600 _NL_COLLATE_COLLSEQMB);
4602 start_colseq = collseq[(unsigned char) TRANSLATE (range_start_char)];
4603 end_colseq = collseq[(unsigned char) TRANSLATE (p[0])];
4604 for (this_char = 0; this_char <= (unsigned char) -1; ++this_char)
4606 unsigned int this_colseq = collseq[(unsigned char) TRANSLATE (this_char)];
4608 if (start_colseq <= this_colseq && this_colseq <= end_colseq)
4610 SET_LIST_BIT (TRANSLATE (this_char));
4615 /* Here we see why `this_char' has to be larger than an `unsigned
4616 char' -- we would otherwise go into an infinite loop, since all
4617 characters <= 0xff. */
4618 range_start_char = TRANSLATE (range_start_char);
4619 /* TRANSLATE(p[0]) is casted to char (not unsigned char) in TRANSLATE,
4620 and some compilers cast it to int implicitly, so following for_loop
4621 may fall to (almost) infinite loop.
4622 e.g. If translate[p[0]] = 0xff, end_char may equals to 0xffffffff.
4623 To avoid this, we cast p[0] to unsigned int and truncate it. */
4624 end_char = ((unsigned)TRANSLATE(p[0]) & ((1 << BYTEWIDTH) - 1));
4626 for (this_char = range_start_char; this_char <= end_char; ++this_char)
4628 SET_LIST_BIT (TRANSLATE (this_char));
4637 /* re_compile_fastmap computes a ``fastmap'' for the compiled pattern in
4638 BUFP. A fastmap records which of the (1 << BYTEWIDTH) possible
4639 characters can start a string that matches the pattern. This fastmap
4640 is used by re_search to skip quickly over impossible starting points.
4642 The caller must supply the address of a (1 << BYTEWIDTH)-byte data
4643 area as BUFP->fastmap.
4645 We set the `fastmap', `fastmap_accurate', and `can_be_null' fields in
4648 Returns 0 if we succeed, -2 if an internal error. */
4651 /* local function for re_compile_fastmap.
4652 truncate wchar_t character to char. */
4653 static unsigned char truncate_wchar (CHAR_T c);
4655 static unsigned char
4659 unsigned char buf[MB_CUR_MAX];
4662 memset (&state, '\0', sizeof (state));
4664 retval = __wcrtomb (buf, c, &state);
4666 retval = wcrtomb (buf, c, &state);
4668 return retval > 0 ? buf[0] : (unsigned char) c;
4673 PREFIX(re_compile_fastmap) (bufp)
4674 struct re_pattern_buffer *bufp;
4677 #ifdef MATCH_MAY_ALLOCATE
4678 PREFIX(fail_stack_type) fail_stack;
4680 #ifndef REGEX_MALLOC
4684 register char *fastmap = bufp->fastmap;
4687 /* We need to cast pattern to (wchar_t*), because we casted this compiled
4688 pattern to (char*) in regex_compile. */
4689 UCHAR_T *pattern = (UCHAR_T*)bufp->buffer;
4690 register UCHAR_T *pend = (UCHAR_T*) (bufp->buffer + bufp->used);
4692 UCHAR_T *pattern = bufp->buffer;
4693 register UCHAR_T *pend = pattern + bufp->used;
4695 UCHAR_T *p = pattern;
4698 /* This holds the pointer to the failure stack, when
4699 it is allocated relocatably. */
4700 fail_stack_elt_t *failure_stack_ptr;
4703 /* Assume that each path through the pattern can be null until
4704 proven otherwise. We set this false at the bottom of switch
4705 statement, to which we get only if a particular path doesn't
4706 match the empty string. */
4707 boolean path_can_be_null = true;
4709 /* We aren't doing a `succeed_n' to begin with. */
4710 boolean succeed_n_p = false;
4712 assert (fastmap != NULL && p != NULL);
4715 bzero (fastmap, 1 << BYTEWIDTH); /* Assume nothing's valid. */
4716 bufp->fastmap_accurate = 1; /* It will be when we're done. */
4717 bufp->can_be_null = 0;
4721 if (p == pend || *p == succeed)
4723 /* We have reached the (effective) end of pattern. */
4724 if (!FAIL_STACK_EMPTY ())
4726 bufp->can_be_null |= path_can_be_null;
4728 /* Reset for next path. */
4729 path_can_be_null = true;
4731 p = fail_stack.stack[--fail_stack.avail].pointer;
4739 /* We should never be about to go beyond the end of the pattern. */
4742 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
4745 /* I guess the idea here is to simply not bother with a fastmap
4746 if a backreference is used, since it's too hard to figure out
4747 the fastmap for the corresponding group. Setting
4748 `can_be_null' stops `re_search_2' from using the fastmap, so
4749 that is all we do. */
4751 bufp->can_be_null = 1;
4755 /* Following are the cases which match a character. These end
4760 fastmap[truncate_wchar(p[1])] = 1;
4774 /* It is hard to distinguish fastmap from (multi byte) characters
4775 which depends on current locale. */
4780 bufp->can_be_null = 1;
4784 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4785 if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
4791 /* Chars beyond end of map must be allowed. */
4792 for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
4795 for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
4796 if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
4802 for (j = 0; j < (1 << BYTEWIDTH); j++)
4803 if (SYNTAX (j) == Sword)
4809 for (j = 0; j < (1 << BYTEWIDTH); j++)
4810 if (SYNTAX (j) != Sword)
4817 int fastmap_newline = fastmap['\n'];
4819 /* `.' matches anything ... */
4820 for (j = 0; j < (1 << BYTEWIDTH); j++)
4823 /* ... except perhaps newline. */
4824 if (!(bufp->syntax & RE_DOT_NEWLINE))
4825 fastmap['\n'] = fastmap_newline;
4827 /* Return if we have already set `can_be_null'; if we have,
4828 then the fastmap is irrelevant. Something's wrong here. */
4829 else if (bufp->can_be_null)
4832 /* Otherwise, have to check alternative paths. */
4839 for (j = 0; j < (1 << BYTEWIDTH); j++)
4840 if (SYNTAX (j) == (enum syntaxcode) k)
4847 for (j = 0; j < (1 << BYTEWIDTH); j++)
4848 if (SYNTAX (j) != (enum syntaxcode) k)
4853 /* All cases after this match the empty string. These end with
4873 case push_dummy_failure:
4878 case pop_failure_jump:
4879 case maybe_pop_jump:
4882 case dummy_failure_jump:
4883 EXTRACT_NUMBER_AND_INCR (j, p);
4888 /* Jump backward implies we just went through the body of a
4889 loop and matched nothing. Opcode jumped to should be
4890 `on_failure_jump' or `succeed_n'. Just treat it like an
4891 ordinary jump. For a * loop, it has pushed its failure
4892 point already; if so, discard that as redundant. */
4893 if ((re_opcode_t) *p != on_failure_jump
4894 && (re_opcode_t) *p != succeed_n)
4898 EXTRACT_NUMBER_AND_INCR (j, p);
4901 /* If what's on the stack is where we are now, pop it. */
4902 if (!FAIL_STACK_EMPTY ()
4903 && fail_stack.stack[fail_stack.avail - 1].pointer == p)
4909 case on_failure_jump:
4910 case on_failure_keep_string_jump:
4911 handle_on_failure_jump:
4912 EXTRACT_NUMBER_AND_INCR (j, p);
4914 /* For some patterns, e.g., `(a?)?', `p+j' here points to the
4915 end of the pattern. We don't want to push such a point,
4916 since when we restore it above, entering the switch will
4917 increment `p' past the end of the pattern. We don't need
4918 to push such a point since we obviously won't find any more
4919 fastmap entries beyond `pend'. Such a pattern can match
4920 the null string, though. */
4923 if (!PUSH_PATTERN_OP (p + j, fail_stack))
4925 RESET_FAIL_STACK ();
4930 bufp->can_be_null = 1;
4934 EXTRACT_NUMBER_AND_INCR (k, p); /* Skip the n. */
4935 succeed_n_p = false;
4942 /* Get to the number of times to succeed. */
4943 p += OFFSET_ADDRESS_SIZE;
4945 /* Increment p past the n for when k != 0. */
4946 EXTRACT_NUMBER_AND_INCR (k, p);
4949 p -= 2 * OFFSET_ADDRESS_SIZE;
4950 succeed_n_p = true; /* Spaghetti code alert. */
4951 goto handle_on_failure_jump;
4957 p += 2 * OFFSET_ADDRESS_SIZE;
4968 abort (); /* We have listed all the cases. */
4971 /* Getting here means we have found the possible starting
4972 characters for one path of the pattern -- and that the empty
4973 string does not match. We need not follow this path further.
4974 Instead, look at the next alternative (remembered on the
4975 stack), or quit if no more. The test at the top of the loop
4976 does these things. */
4977 path_can_be_null = false;
4981 /* Set `can_be_null' for the last path (also the first path, if the
4982 pattern is empty). */
4983 bufp->can_be_null |= path_can_be_null;
4986 RESET_FAIL_STACK ();
4990 #else /* not INSIDE_RECURSION */
4993 re_compile_fastmap (bufp)
4994 struct re_pattern_buffer *bufp;
4997 if (MB_CUR_MAX != 1)
4998 return wcs_re_compile_fastmap(bufp);
5001 return byte_re_compile_fastmap(bufp);
5002 } /* re_compile_fastmap */
5004 weak_alias (__re_compile_fastmap, re_compile_fastmap)
5008 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
5009 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
5010 this memory for recording register information. STARTS and ENDS
5011 must be allocated using the malloc library routine, and must each
5012 be at least NUM_REGS * sizeof (regoff_t) bytes long.
5014 If NUM_REGS == 0, then subsequent matches should allocate their own
5017 Unless this function is called, the first search or match using
5018 PATTERN_BUFFER will allocate its own register data, without
5019 freeing the old data. */
5022 re_set_registers (bufp, regs, num_regs, starts, ends)
5023 struct re_pattern_buffer *bufp;
5024 struct re_registers *regs;
5026 regoff_t *starts, *ends;
5030 bufp->regs_allocated = REGS_REALLOCATE;
5031 regs->num_regs = num_regs;
5032 regs->start = starts;
5037 bufp->regs_allocated = REGS_UNALLOCATED;
5039 regs->start = regs->end = (regoff_t *) 0;
5043 weak_alias (__re_set_registers, re_set_registers)
5046 /* Searching routines. */
5048 /* Like re_search_2, below, but only one string is specified, and
5049 doesn't let you say where to stop matching. */
5052 re_search (bufp, string, size, startpos, range, regs)
5053 struct re_pattern_buffer *bufp;
5055 int size, startpos, range;
5056 struct re_registers *regs;
5058 return re_search_2 (bufp, NULL, 0, string, size, startpos, range,
5062 weak_alias (__re_search, re_search)
5066 /* Using the compiled pattern in BUFP->buffer, first tries to match the
5067 virtual concatenation of STRING1 and STRING2, starting first at index
5068 STARTPOS, then at STARTPOS + 1, and so on.
5070 STRING1 and STRING2 have length SIZE1 and SIZE2, respectively.
5072 RANGE is how far to scan while trying to match. RANGE = 0 means try
5073 only at STARTPOS; in general, the last start tried is STARTPOS +
5076 In REGS, return the indices of the virtual concatenation of STRING1
5077 and STRING2 that matched the entire BUFP->buffer and its contained
5080 Do not consider matching one past the index STOP in the virtual
5081 concatenation of STRING1 and STRING2.
5083 We return either the position in the strings at which the match was
5084 found, -1 if no match, or -2 if error (such as failure
5088 re_search_2 (bufp, string1, size1, string2, size2, startpos, range, regs, stop)
5089 struct re_pattern_buffer *bufp;
5090 const char *string1, *string2;
5094 struct re_registers *regs;
5098 if (MB_CUR_MAX != 1)
5099 return wcs_re_search_2 (bufp, string1, size1, string2, size2, startpos,
5103 return byte_re_search_2 (bufp, string1, size1, string2, size2, startpos,
5107 weak_alias (__re_search_2, re_search_2)
5110 #endif /* not INSIDE_RECURSION */
5112 #ifdef INSIDE_RECURSION
5114 #ifdef MATCH_MAY_ALLOCATE
5115 # define FREE_VAR(var) if (var) REGEX_FREE (var); var = NULL
5117 # define FREE_VAR(var) if (var) free (var); var = NULL
5121 # define MAX_ALLOCA_SIZE 2000
5123 # define FREE_WCS_BUFFERS() \
5125 if (size1 > MAX_ALLOCA_SIZE) \
5127 free (wcs_string1); \
5128 free (mbs_offset1); \
5132 FREE_VAR (wcs_string1); \
5133 FREE_VAR (mbs_offset1); \
5135 if (size2 > MAX_ALLOCA_SIZE) \
5137 free (wcs_string2); \
5138 free (mbs_offset2); \
5142 FREE_VAR (wcs_string2); \
5143 FREE_VAR (mbs_offset2); \
5151 PREFIX(re_search_2) (bufp, string1, size1, string2, size2, startpos, range,
5153 struct re_pattern_buffer *bufp;
5154 const char *string1, *string2;
5158 struct re_registers *regs;
5162 register char *fastmap = bufp->fastmap;
5163 register RE_TRANSLATE_TYPE translate = bufp->translate;
5164 int total_size = size1 + size2;
5165 int endpos = startpos + range;
5167 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5168 wchar_t *wcs_string1 = NULL, *wcs_string2 = NULL;
5169 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5170 int wcs_size1 = 0, wcs_size2 = 0;
5171 /* offset buffer for optimization. See convert_mbs_to_wc. */
5172 int *mbs_offset1 = NULL, *mbs_offset2 = NULL;
5173 /* They hold whether each wchar_t is binary data or not. */
5174 char *is_binary = NULL;
5177 /* Check for out-of-range STARTPOS. */
5178 if (startpos < 0 || startpos > total_size)
5181 /* Fix up RANGE if it might eventually take us outside
5182 the virtual concatenation of STRING1 and STRING2.
5183 Make sure we won't move STARTPOS below 0 or above TOTAL_SIZE. */
5185 range = 0 - startpos;
5186 else if (endpos > total_size)
5187 range = total_size - startpos;
5189 /* If the search isn't to be a backwards one, don't waste time in a
5190 search for a pattern that must be anchored. */
5191 if (bufp->used > 0 && range > 0
5192 && ((re_opcode_t) bufp->buffer[0] == begbuf
5193 /* `begline' is like `begbuf' if it cannot match at newlines. */
5194 || ((re_opcode_t) bufp->buffer[0] == begline
5195 && !bufp->newline_anchor)))
5204 /* In a forward search for something that starts with \=.
5205 don't keep searching past point. */
5206 if (bufp->used > 0 && (re_opcode_t) bufp->buffer[0] == at_dot && range > 0)
5208 range = PT - startpos;
5214 /* Update the fastmap now if not correct already. */
5215 if (fastmap && !bufp->fastmap_accurate)
5216 if (re_compile_fastmap (bufp) == -2)
5220 /* Allocate wchar_t array for wcs_string1 and wcs_string2 and
5221 fill them with converted string. */
5224 if (size1 > MAX_ALLOCA_SIZE)
5226 wcs_string1 = TALLOC (size1 + 1, CHAR_T);
5227 mbs_offset1 = TALLOC (size1 + 1, int);
5228 is_binary = TALLOC (size1 + 1, char);
5232 wcs_string1 = REGEX_TALLOC (size1 + 1, CHAR_T);
5233 mbs_offset1 = REGEX_TALLOC (size1 + 1, int);
5234 is_binary = REGEX_TALLOC (size1 + 1, char);
5236 if (!wcs_string1 || !mbs_offset1 || !is_binary)
5238 if (size1 > MAX_ALLOCA_SIZE)
5246 FREE_VAR (wcs_string1);
5247 FREE_VAR (mbs_offset1);
5248 FREE_VAR (is_binary);
5252 wcs_size1 = convert_mbs_to_wcs(wcs_string1, string1, size1,
5253 mbs_offset1, is_binary);
5254 wcs_string1[wcs_size1] = L'\0'; /* for a sentinel */
5255 if (size1 > MAX_ALLOCA_SIZE)
5258 FREE_VAR (is_binary);
5262 if (size2 > MAX_ALLOCA_SIZE)
5264 wcs_string2 = TALLOC (size2 + 1, CHAR_T);
5265 mbs_offset2 = TALLOC (size2 + 1, int);
5266 is_binary = TALLOC (size2 + 1, char);
5270 wcs_string2 = REGEX_TALLOC (size2 + 1, CHAR_T);
5271 mbs_offset2 = REGEX_TALLOC (size2 + 1, int);
5272 is_binary = REGEX_TALLOC (size2 + 1, char);
5274 if (!wcs_string2 || !mbs_offset2 || !is_binary)
5276 FREE_WCS_BUFFERS ();
5277 if (size2 > MAX_ALLOCA_SIZE)
5280 FREE_VAR (is_binary);
5283 wcs_size2 = convert_mbs_to_wcs(wcs_string2, string2, size2,
5284 mbs_offset2, is_binary);
5285 wcs_string2[wcs_size2] = L'\0'; /* for a sentinel */
5286 if (size2 > MAX_ALLOCA_SIZE)
5289 FREE_VAR (is_binary);
5294 /* Loop through the string, looking for a place to start matching. */
5297 /* If a fastmap is supplied, skip quickly over characters that
5298 cannot be the start of a match. If the pattern can match the
5299 null string, however, we don't need to skip characters; we want
5300 the first null string. */
5301 if (fastmap && startpos < total_size && !bufp->can_be_null)
5303 if (range > 0) /* Searching forwards. */
5305 register const char *d;
5306 register int lim = 0;
5309 if (startpos < size1 && startpos + range >= size1)
5310 lim = range - (size1 - startpos);
5312 d = (startpos >= size1 ? string2 - size1 : string1) + startpos;
5314 /* Written out as an if-else to avoid testing `translate'
5318 && !fastmap[(unsigned char)
5319 translate[(unsigned char) *d++]])
5322 while (range > lim && !fastmap[(unsigned char) *d++])
5325 startpos += irange - range;
5327 else /* Searching backwards. */
5329 register CHAR_T c = (size1 == 0 || startpos >= size1
5330 ? string2[startpos - size1]
5331 : string1[startpos]);
5333 if (!fastmap[(unsigned char) TRANSLATE (c)])
5338 /* If can't match the null string, and that's all we have left, fail. */
5339 if (range >= 0 && startpos == total_size && fastmap
5340 && !bufp->can_be_null)
5343 FREE_WCS_BUFFERS ();
5349 val = wcs_re_match_2_internal (bufp, string1, size1, string2,
5350 size2, startpos, regs, stop,
5351 wcs_string1, wcs_size1,
5352 wcs_string2, wcs_size2,
5353 mbs_offset1, mbs_offset2);
5355 val = byte_re_match_2_internal (bufp, string1, size1, string2,
5356 size2, startpos, regs, stop);
5359 #ifndef REGEX_MALLOC
5368 FREE_WCS_BUFFERS ();
5376 FREE_WCS_BUFFERS ();
5396 FREE_WCS_BUFFERS ();
5402 /* This converts PTR, a pointer into one of the search wchar_t strings
5403 `string1' and `string2' into an multibyte string offset from the
5404 beginning of that string. We use mbs_offset to optimize.
5405 See convert_mbs_to_wcs. */
5406 # define POINTER_TO_OFFSET(ptr) \
5407 (FIRST_STRING_P (ptr) \
5408 ? ((regoff_t)(mbs_offset1 != NULL? mbs_offset1[(ptr)-string1] : 0)) \
5409 : ((regoff_t)((mbs_offset2 != NULL? mbs_offset2[(ptr)-string2] : 0) \
5412 /* This converts PTR, a pointer into one of the search strings `string1'
5413 and `string2' into an offset from the beginning of that string. */
5414 # define POINTER_TO_OFFSET(ptr) \
5415 (FIRST_STRING_P (ptr) \
5416 ? ((regoff_t) ((ptr) - string1)) \
5417 : ((regoff_t) ((ptr) - string2 + size1)))
5420 /* Macros for dealing with the split strings in re_match_2. */
5422 #define MATCHING_IN_FIRST_STRING (dend == end_match_1)
5424 /* Call before fetching a character with *d. This switches over to
5425 string2 if necessary. */
5426 #define PREFETCH() \
5429 /* End of string2 => fail. */ \
5430 if (dend == end_match_2) \
5432 /* End of string1 => advance to string2. */ \
5434 dend = end_match_2; \
5437 /* Test if at very beginning or at very end of the virtual concatenation
5438 of `string1' and `string2'. If only one string, it's `string2'. */
5439 #define AT_STRINGS_BEG(d) ((d) == (size1 ? string1 : string2) || !size2)
5440 #define AT_STRINGS_END(d) ((d) == end2)
5443 /* Test if D points to a character which is word-constituent. We have
5444 two special cases to check for: if past the end of string1, look at
5445 the first character in string2; and if before the beginning of
5446 string2, look at the last character in string1. */
5448 /* Use internationalized API instead of SYNTAX. */
5449 # define WORDCHAR_P(d) \
5450 (iswalnum ((wint_t)((d) == end1 ? *string2 \
5451 : (d) == string2 - 1 ? *(end1 - 1) : *(d))) != 0 \
5452 || ((d) == end1 ? *string2 \
5453 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) == L'_')
5455 # define WORDCHAR_P(d) \
5456 (SYNTAX ((d) == end1 ? *string2 \
5457 : (d) == string2 - 1 ? *(end1 - 1) : *(d)) \
5461 /* Disabled due to a compiler bug -- see comment at case wordbound */
5463 /* Test if the character before D and the one at D differ with respect
5464 to being word-constituent. */
5465 #define AT_WORD_BOUNDARY(d) \
5466 (AT_STRINGS_BEG (d) || AT_STRINGS_END (d) \
5467 || WORDCHAR_P (d - 1) != WORDCHAR_P (d))
5470 /* Free everything we malloc. */
5471 #ifdef MATCH_MAY_ALLOCATE
5473 # define FREE_VARIABLES() \
5475 REGEX_FREE_STACK (fail_stack.stack); \
5476 FREE_VAR (regstart); \
5477 FREE_VAR (regend); \
5478 FREE_VAR (old_regstart); \
5479 FREE_VAR (old_regend); \
5480 FREE_VAR (best_regstart); \
5481 FREE_VAR (best_regend); \
5482 FREE_VAR (reg_info); \
5483 FREE_VAR (reg_dummy); \
5484 FREE_VAR (reg_info_dummy); \
5485 if (!cant_free_wcs_buf) \
5487 FREE_VAR (string1); \
5488 FREE_VAR (string2); \
5489 FREE_VAR (mbs_offset1); \
5490 FREE_VAR (mbs_offset2); \
5494 # define FREE_VARIABLES() \
5496 REGEX_FREE_STACK (fail_stack.stack); \
5497 FREE_VAR (regstart); \
5498 FREE_VAR (regend); \
5499 FREE_VAR (old_regstart); \
5500 FREE_VAR (old_regend); \
5501 FREE_VAR (best_regstart); \
5502 FREE_VAR (best_regend); \
5503 FREE_VAR (reg_info); \
5504 FREE_VAR (reg_dummy); \
5505 FREE_VAR (reg_info_dummy); \
5510 # define FREE_VARIABLES() \
5512 if (!cant_free_wcs_buf) \
5514 FREE_VAR (string1); \
5515 FREE_VAR (string2); \
5516 FREE_VAR (mbs_offset1); \
5517 FREE_VAR (mbs_offset2); \
5521 # define FREE_VARIABLES() ((void)0) /* Do nothing! But inhibit gcc warning. */
5523 #endif /* not MATCH_MAY_ALLOCATE */
5525 /* These values must meet several constraints. They must not be valid
5526 register values; since we have a limit of 255 registers (because
5527 we use only one byte in the pattern for the register number), we can
5528 use numbers larger than 255. They must differ by 1, because of
5529 NUM_FAILURE_ITEMS above. And the value for the lowest register must
5530 be larger than the value for the highest register, so we do not try
5531 to actually save any registers when none are active. */
5532 #define NO_HIGHEST_ACTIVE_REG (1 << BYTEWIDTH)
5533 #define NO_LOWEST_ACTIVE_REG (NO_HIGHEST_ACTIVE_REG + 1)
5535 #else /* not INSIDE_RECURSION */
5536 /* Matching routines. */
5538 #ifndef emacs /* Emacs never uses this. */
5539 /* re_match is like re_match_2 except it takes only a single string. */
5542 re_match (bufp, string, size, pos, regs)
5543 struct re_pattern_buffer *bufp;
5546 struct re_registers *regs;
5550 if (MB_CUR_MAX != 1)
5551 result = wcs_re_match_2_internal (bufp, NULL, 0, string, size,
5553 NULL, 0, NULL, 0, NULL, NULL);
5556 result = byte_re_match_2_internal (bufp, NULL, 0, string, size,
5558 # ifndef REGEX_MALLOC
5566 weak_alias (__re_match, re_match)
5568 #endif /* not emacs */
5570 #endif /* not INSIDE_RECURSION */
5572 #ifdef INSIDE_RECURSION
5573 static boolean PREFIX(group_match_null_string_p) _RE_ARGS ((UCHAR_T **p,
5575 PREFIX(register_info_type) *reg_info));
5576 static boolean PREFIX(alt_match_null_string_p) _RE_ARGS ((UCHAR_T *p,
5578 PREFIX(register_info_type) *reg_info));
5579 static boolean PREFIX(common_op_match_null_string_p) _RE_ARGS ((UCHAR_T **p,
5581 PREFIX(register_info_type) *reg_info));
5582 static int PREFIX(bcmp_translate) _RE_ARGS ((const CHAR_T *s1, const CHAR_T *s2,
5583 int len, char *translate));
5584 #else /* not INSIDE_RECURSION */
5586 /* re_match_2 matches the compiled pattern in BUFP against the
5587 the (virtual) concatenation of STRING1 and STRING2 (of length SIZE1
5588 and SIZE2, respectively). We start matching at POS, and stop
5591 If REGS is non-null and the `no_sub' field of BUFP is nonzero, we
5592 store offsets for the substring each group matched in REGS. See the
5593 documentation for exactly how many groups we fill.
5595 We return -1 if no match, -2 if an internal error (such as the
5596 failure stack overflowing). Otherwise, we return the length of the
5597 matched substring. */
5600 re_match_2 (bufp, string1, size1, string2, size2, pos, regs, stop)
5601 struct re_pattern_buffer *bufp;
5602 const char *string1, *string2;
5605 struct re_registers *regs;
5610 if (MB_CUR_MAX != 1)
5611 result = wcs_re_match_2_internal (bufp, string1, size1, string2, size2,
5613 NULL, 0, NULL, 0, NULL, NULL);
5616 result = byte_re_match_2_internal (bufp, string1, size1, string2, size2,
5619 #ifndef REGEX_MALLOC
5627 weak_alias (__re_match_2, re_match_2)
5630 #endif /* not INSIDE_RECURSION */
5632 #ifdef INSIDE_RECURSION
5635 static int count_mbs_length PARAMS ((int *, int));
5637 /* This check the substring (from 0, to length) of the multibyte string,
5638 to which offset_buffer correspond. And count how many wchar_t_characters
5639 the substring occupy. We use offset_buffer to optimization.
5640 See convert_mbs_to_wcs. */
5643 count_mbs_length(offset_buffer, length)
5649 /* Check whether the size is valid. */
5653 if (offset_buffer == NULL)
5656 /* If there are no multibyte character, offset_buffer[i] == i.
5657 Optmize for this case. */
5658 if (offset_buffer[length] == length)
5661 /* Set up upper with length. (because for all i, offset_buffer[i] >= i) */
5667 int middle = (lower + upper) / 2;
5668 if (middle == lower || middle == upper)
5670 if (offset_buffer[middle] > length)
5672 else if (offset_buffer[middle] < length)
5682 /* This is a separate function so that we can force an alloca cleanup
5686 wcs_re_match_2_internal (bufp, cstring1, csize1, cstring2, csize2, pos,
5687 regs, stop, string1, size1, string2, size2,
5688 mbs_offset1, mbs_offset2)
5689 struct re_pattern_buffer *bufp;
5690 const char *cstring1, *cstring2;
5693 struct re_registers *regs;
5695 /* string1 == string2 == NULL means string1/2, size1/2 and
5696 mbs_offset1/2 need seting up in this function. */
5697 /* We need wchar_t* buffers correspond to cstring1, cstring2. */
5698 wchar_t *string1, *string2;
5699 /* We need the size of wchar_t buffers correspond to csize1, csize2. */
5701 /* offset buffer for optimization. See convert_mbs_to_wc. */
5702 int *mbs_offset1, *mbs_offset2;
5705 byte_re_match_2_internal (bufp, string1, size1,string2, size2, pos,
5707 struct re_pattern_buffer *bufp;
5708 const char *string1, *string2;
5711 struct re_registers *regs;
5715 /* General temporaries. */
5719 /* They hold whether each wchar_t is binary data or not. */
5720 char *is_binary = NULL;
5721 /* If true, we can't free string1/2, mbs_offset1/2. */
5722 int cant_free_wcs_buf = 1;
5725 /* Just past the end of the corresponding string. */
5726 const CHAR_T *end1, *end2;
5728 /* Pointers into string1 and string2, just past the last characters in
5729 each to consider matching. */
5730 const CHAR_T *end_match_1, *end_match_2;
5732 /* Where we are in the data, and the end of the current string. */
5733 const CHAR_T *d, *dend;
5735 /* Where we are in the pattern, and the end of the pattern. */
5737 UCHAR_T *pattern, *p;
5738 register UCHAR_T *pend;
5740 UCHAR_T *p = bufp->buffer;
5741 register UCHAR_T *pend = p + bufp->used;
5744 /* Mark the opcode just after a start_memory, so we can test for an
5745 empty subpattern when we get to the stop_memory. */
5746 UCHAR_T *just_past_start_mem = 0;
5748 /* We use this to map every character in the string. */
5749 RE_TRANSLATE_TYPE translate = bufp->translate;
5751 /* Failure point stack. Each place that can handle a failure further
5752 down the line pushes a failure point on this stack. It consists of
5753 restart, regend, and reg_info for all registers corresponding to
5754 the subexpressions we're currently inside, plus the number of such
5755 registers, and, finally, two char *'s. The first char * is where
5756 to resume scanning the pattern; the second one is where to resume
5757 scanning the strings. If the latter is zero, the failure point is
5758 a ``dummy''; if a failure happens and the failure point is a dummy,
5759 it gets discarded and the next next one is tried. */
5760 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5761 PREFIX(fail_stack_type) fail_stack;
5764 static unsigned failure_id;
5765 unsigned nfailure_points_pushed = 0, nfailure_points_popped = 0;
5769 /* This holds the pointer to the failure stack, when
5770 it is allocated relocatably. */
5771 fail_stack_elt_t *failure_stack_ptr;
5774 /* We fill all the registers internally, independent of what we
5775 return, for use in backreferences. The number here includes
5776 an element for register zero. */
5777 size_t num_regs = bufp->re_nsub + 1;
5779 /* The currently active registers. */
5780 active_reg_t lowest_active_reg = NO_LOWEST_ACTIVE_REG;
5781 active_reg_t highest_active_reg = NO_HIGHEST_ACTIVE_REG;
5783 /* Information on the contents of registers. These are pointers into
5784 the input strings; they record just what was matched (on this
5785 attempt) by a subexpression part of the pattern, that is, the
5786 regnum-th regstart pointer points to where in the pattern we began
5787 matching and the regnum-th regend points to right after where we
5788 stopped matching the regnum-th subexpression. (The zeroth register
5789 keeps track of what the whole pattern matches.) */
5790 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5791 const CHAR_T **regstart, **regend;
5794 /* If a group that's operated upon by a repetition operator fails to
5795 match anything, then the register for its start will need to be
5796 restored because it will have been set to wherever in the string we
5797 are when we last see its open-group operator. Similarly for a
5799 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5800 const CHAR_T **old_regstart, **old_regend;
5803 /* The is_active field of reg_info helps us keep track of which (possibly
5804 nested) subexpressions we are currently in. The matched_something
5805 field of reg_info[reg_num] helps us tell whether or not we have
5806 matched any of the pattern so far this time through the reg_num-th
5807 subexpression. These two fields get reset each time through any
5808 loop their register is in. */
5809 #ifdef MATCH_MAY_ALLOCATE /* otherwise, this is global. */
5810 PREFIX(register_info_type) *reg_info;
5813 /* The following record the register info as found in the above
5814 variables when we find a match better than any we've seen before.
5815 This happens as we backtrack through the failure points, which in
5816 turn happens only if we have not yet matched the entire string. */
5817 unsigned best_regs_set = false;
5818 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5819 const CHAR_T **best_regstart, **best_regend;
5822 /* Logically, this is `best_regend[0]'. But we don't want to have to
5823 allocate space for that if we're not allocating space for anything
5824 else (see below). Also, we never need info about register 0 for
5825 any of the other register vectors, and it seems rather a kludge to
5826 treat `best_regend' differently than the rest. So we keep track of
5827 the end of the best match so far in a separate variable. We
5828 initialize this to NULL so that when we backtrack the first time
5829 and need to test it, it's not garbage. */
5830 const CHAR_T *match_end = NULL;
5832 /* This helps SET_REGS_MATCHED avoid doing redundant work. */
5833 int set_regs_matched_done = 0;
5835 /* Used when we pop values we don't care about. */
5836 #ifdef MATCH_MAY_ALLOCATE /* otherwise, these are global. */
5837 const CHAR_T **reg_dummy;
5838 PREFIX(register_info_type) *reg_info_dummy;
5842 /* Counts the total number of registers pushed. */
5843 unsigned num_regs_pushed = 0;
5846 DEBUG_PRINT1 ("\n\nEntering re_match_2.\n");
5850 #ifdef MATCH_MAY_ALLOCATE
5851 /* Do not bother to initialize all the register variables if there are
5852 no groups in the pattern, as it takes a fair amount of time. If
5853 there are groups, we include space for register 0 (the whole
5854 pattern), even though we never use it, since it simplifies the
5855 array indexing. We should fix this. */
5858 regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5859 regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5860 old_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5861 old_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5862 best_regstart = REGEX_TALLOC (num_regs, const CHAR_T *);
5863 best_regend = REGEX_TALLOC (num_regs, const CHAR_T *);
5864 reg_info = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5865 reg_dummy = REGEX_TALLOC (num_regs, const CHAR_T *);
5866 reg_info_dummy = REGEX_TALLOC (num_regs, PREFIX(register_info_type));
5868 if (!(regstart && regend && old_regstart && old_regend && reg_info
5869 && best_regstart && best_regend && reg_dummy && reg_info_dummy))
5877 /* We must initialize all our variables to NULL, so that
5878 `FREE_VARIABLES' doesn't try to free them. */
5879 regstart = regend = old_regstart = old_regend = best_regstart
5880 = best_regend = reg_dummy = NULL;
5881 reg_info = reg_info_dummy = (PREFIX(register_info_type) *) NULL;
5883 #endif /* MATCH_MAY_ALLOCATE */
5885 /* The starting position is bogus. */
5887 if (pos < 0 || pos > csize1 + csize2)
5889 if (pos < 0 || pos > size1 + size2)
5897 /* Allocate wchar_t array for string1 and string2 and
5898 fill them with converted string. */
5899 if (string1 == NULL && string2 == NULL)
5901 /* We need seting up buffers here. */
5903 /* We must free wcs buffers in this function. */
5904 cant_free_wcs_buf = 0;
5908 string1 = REGEX_TALLOC (csize1 + 1, CHAR_T);
5909 mbs_offset1 = REGEX_TALLOC (csize1 + 1, int);
5910 is_binary = REGEX_TALLOC (csize1 + 1, char);
5911 if (!string1 || !mbs_offset1 || !is_binary)
5914 FREE_VAR (mbs_offset1);
5915 FREE_VAR (is_binary);
5921 string2 = REGEX_TALLOC (csize2 + 1, CHAR_T);
5922 mbs_offset2 = REGEX_TALLOC (csize2 + 1, int);
5923 is_binary = REGEX_TALLOC (csize2 + 1, char);
5924 if (!string2 || !mbs_offset2 || !is_binary)
5927 FREE_VAR (mbs_offset1);
5929 FREE_VAR (mbs_offset2);
5930 FREE_VAR (is_binary);
5933 size2 = convert_mbs_to_wcs(string2, cstring2, csize2,
5934 mbs_offset2, is_binary);
5935 string2[size2] = L'\0'; /* for a sentinel */
5936 FREE_VAR (is_binary);
5940 /* We need to cast pattern to (wchar_t*), because we casted this compiled
5941 pattern to (char*) in regex_compile. */
5942 p = pattern = (CHAR_T*)bufp->buffer;
5943 pend = (CHAR_T*)(bufp->buffer + bufp->used);
5947 /* Initialize subexpression text positions to -1 to mark ones that no
5948 start_memory/stop_memory has been seen for. Also initialize the
5949 register information struct. */
5950 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
5952 regstart[mcnt] = regend[mcnt]
5953 = old_regstart[mcnt] = old_regend[mcnt] = REG_UNSET_VALUE;
5955 REG_MATCH_NULL_STRING_P (reg_info[mcnt]) = MATCH_NULL_UNSET_VALUE;
5956 IS_ACTIVE (reg_info[mcnt]) = 0;
5957 MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5958 EVER_MATCHED_SOMETHING (reg_info[mcnt]) = 0;
5961 /* We move `string1' into `string2' if the latter's empty -- but not if
5962 `string1' is null. */
5963 if (size2 == 0 && string1 != NULL)
5970 mbs_offset2 = mbs_offset1;
5976 end1 = string1 + size1;
5977 end2 = string2 + size2;
5979 /* Compute where to stop matching, within the two strings. */
5983 mcnt = count_mbs_length(mbs_offset1, stop);
5984 end_match_1 = string1 + mcnt;
5985 end_match_2 = string2;
5989 if (stop > csize1 + csize2)
5990 stop = csize1 + csize2;
5992 mcnt = count_mbs_length(mbs_offset2, stop-csize1);
5993 end_match_2 = string2 + mcnt;
5996 { /* count_mbs_length return error. */
6003 end_match_1 = string1 + stop;
6004 end_match_2 = string2;
6009 end_match_2 = string2 + stop - size1;
6013 /* `p' scans through the pattern as `d' scans through the data.
6014 `dend' is the end of the input string that `d' points within. `d'
6015 is advanced into the following input string whenever necessary, but
6016 this happens before fetching; therefore, at the beginning of the
6017 loop, `d' can be pointing at the end of a string, but it cannot
6020 if (size1 > 0 && pos <= csize1)
6022 mcnt = count_mbs_length(mbs_offset1, pos);
6028 mcnt = count_mbs_length(mbs_offset2, pos-csize1);
6034 { /* count_mbs_length return error. */
6039 if (size1 > 0 && pos <= size1)
6046 d = string2 + pos - size1;
6051 DEBUG_PRINT1 ("The compiled pattern is:\n");
6052 DEBUG_PRINT_COMPILED_PATTERN (bufp, p, pend);
6053 DEBUG_PRINT1 ("The string to match is: `");
6054 DEBUG_PRINT_DOUBLE_STRING (d, string1, size1, string2, size2);
6055 DEBUG_PRINT1 ("'\n");
6057 /* This loops over pattern commands. It exits by returning from the
6058 function if the match is complete, or it drops through if the match
6059 fails at this starting point in the input data. */
6063 DEBUG_PRINT2 ("\n%p: ", p);
6065 DEBUG_PRINT2 ("\n0x%x: ", p);
6069 { /* End of pattern means we might have succeeded. */
6070 DEBUG_PRINT1 ("end of pattern ... ");
6072 /* If we haven't matched the entire string, and we want the
6073 longest match, try backtracking. */
6074 if (d != end_match_2)
6076 /* 1 if this match ends in the same string (string1 or string2)
6077 as the best previous match. */
6078 boolean same_str_p = (FIRST_STRING_P (match_end)
6079 == MATCHING_IN_FIRST_STRING);
6080 /* 1 if this match is the best seen so far. */
6081 boolean best_match_p;
6083 /* AIX compiler got confused when this was combined
6084 with the previous declaration. */
6086 best_match_p = d > match_end;
6088 best_match_p = !MATCHING_IN_FIRST_STRING;
6090 DEBUG_PRINT1 ("backtracking.\n");
6092 if (!FAIL_STACK_EMPTY ())
6093 { /* More failure points to try. */
6095 /* If exceeds best match so far, save it. */
6096 if (!best_regs_set || best_match_p)
6098 best_regs_set = true;
6101 DEBUG_PRINT1 ("\nSAVING match as best so far.\n");
6103 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6105 best_regstart[mcnt] = regstart[mcnt];
6106 best_regend[mcnt] = regend[mcnt];
6112 /* If no failure points, don't restore garbage. And if
6113 last match is real best match, don't restore second
6115 else if (best_regs_set && !best_match_p)
6118 /* Restore best match. It may happen that `dend ==
6119 end_match_1' while the restored d is in string2.
6120 For example, the pattern `x.*y.*z' against the
6121 strings `x-' and `y-z-', if the two strings are
6122 not consecutive in memory. */
6123 DEBUG_PRINT1 ("Restoring best registers.\n");
6126 dend = ((d >= string1 && d <= end1)
6127 ? end_match_1 : end_match_2);
6129 for (mcnt = 1; (unsigned) mcnt < num_regs; mcnt++)
6131 regstart[mcnt] = best_regstart[mcnt];
6132 regend[mcnt] = best_regend[mcnt];
6135 } /* d != end_match_2 */
6138 DEBUG_PRINT1 ("Accepting match.\n");
6139 /* If caller wants register contents data back, do it. */
6140 if (regs && !bufp->no_sub)
6142 /* Have the register data arrays been allocated? */
6143 if (bufp->regs_allocated == REGS_UNALLOCATED)
6144 { /* No. So allocate them with malloc. We need one
6145 extra element beyond `num_regs' for the `-1' marker
6147 regs->num_regs = MAX (RE_NREGS, num_regs + 1);
6148 regs->start = TALLOC (regs->num_regs, regoff_t);
6149 regs->end = TALLOC (regs->num_regs, regoff_t);
6150 if (regs->start == NULL || regs->end == NULL)
6155 bufp->regs_allocated = REGS_REALLOCATE;
6157 else if (bufp->regs_allocated == REGS_REALLOCATE)
6158 { /* Yes. If we need more elements than were already
6159 allocated, reallocate them. If we need fewer, just
6161 if (regs->num_regs < num_regs + 1)
6163 regs->num_regs = num_regs + 1;
6164 RETALLOC (regs->start, regs->num_regs, regoff_t);
6165 RETALLOC (regs->end, regs->num_regs, regoff_t);
6166 if (regs->start == NULL || regs->end == NULL)
6175 /* These braces fend off a "empty body in an else-statement"
6176 warning under GCC when assert expands to nothing. */
6177 assert (bufp->regs_allocated == REGS_FIXED);
6180 /* Convert the pointer data in `regstart' and `regend' to
6181 indices. Register zero has to be set differently,
6182 since we haven't kept track of any info for it. */
6183 if (regs->num_regs > 0)
6185 regs->start[0] = pos;
6187 if (MATCHING_IN_FIRST_STRING)
6188 regs->end[0] = mbs_offset1 != NULL ?
6189 mbs_offset1[d-string1] : 0;
6191 regs->end[0] = csize1 + (mbs_offset2 != NULL ?
6192 mbs_offset2[d-string2] : 0);
6194 regs->end[0] = (MATCHING_IN_FIRST_STRING
6195 ? ((regoff_t) (d - string1))
6196 : ((regoff_t) (d - string2 + size1)));
6200 /* Go through the first `min (num_regs, regs->num_regs)'
6201 registers, since that is all we initialized. */
6202 for (mcnt = 1; (unsigned) mcnt < MIN (num_regs, regs->num_regs);
6205 if (REG_UNSET (regstart[mcnt]) || REG_UNSET (regend[mcnt]))
6206 regs->start[mcnt] = regs->end[mcnt] = -1;
6210 = (regoff_t) POINTER_TO_OFFSET (regstart[mcnt]);
6212 = (regoff_t) POINTER_TO_OFFSET (regend[mcnt]);
6216 /* If the regs structure we return has more elements than
6217 were in the pattern, set the extra elements to -1. If
6218 we (re)allocated the registers, this is the case,
6219 because we always allocate enough to have at least one
6221 for (mcnt = num_regs; (unsigned) mcnt < regs->num_regs; mcnt++)
6222 regs->start[mcnt] = regs->end[mcnt] = -1;
6223 } /* regs && !bufp->no_sub */
6225 DEBUG_PRINT4 ("%u failure points pushed, %u popped (%u remain).\n",
6226 nfailure_points_pushed, nfailure_points_popped,
6227 nfailure_points_pushed - nfailure_points_popped);
6228 DEBUG_PRINT2 ("%u registers pushed.\n", num_regs_pushed);
6231 if (MATCHING_IN_FIRST_STRING)
6232 mcnt = mbs_offset1 != NULL ? mbs_offset1[d-string1] : 0;
6234 mcnt = (mbs_offset2 != NULL ? mbs_offset2[d-string2] : 0) +
6238 mcnt = d - pos - (MATCHING_IN_FIRST_STRING
6243 DEBUG_PRINT2 ("Returning %d from re_match_2.\n", mcnt);
6249 /* Otherwise match next pattern command. */
6250 switch (SWITCH_ENUM_CAST ((re_opcode_t) *p++))
6252 /* Ignore these. Used to ignore the n of succeed_n's which
6253 currently have n == 0. */
6255 DEBUG_PRINT1 ("EXECUTING no_op.\n");
6259 DEBUG_PRINT1 ("EXECUTING succeed.\n");
6262 /* Match the next n pattern characters exactly. The following
6263 byte in the pattern defines n, and the n bytes after that
6264 are the characters to match. */
6270 DEBUG_PRINT2 ("EXECUTING exactn %d.\n", mcnt);
6272 /* This is written out as an if-else so we don't waste time
6273 testing `translate' inside the loop. */
6282 if ((UCHAR_T) translate[(unsigned char) *d++]
6288 if (*d++ != (CHAR_T) *p++)
6292 if ((UCHAR_T) translate[(unsigned char) *d++]
6304 if (*d++ != (CHAR_T) *p++) goto fail;
6308 SET_REGS_MATCHED ();
6312 /* Match any character except possibly a newline or a null. */
6314 DEBUG_PRINT1 ("EXECUTING anychar.\n");
6318 if ((!(bufp->syntax & RE_DOT_NEWLINE) && TRANSLATE (*d) == '\n')
6319 || (bufp->syntax & RE_DOT_NOT_NULL && TRANSLATE (*d) == '\000'))
6322 SET_REGS_MATCHED ();
6323 DEBUG_PRINT2 (" Matched `%ld'.\n", (long int) *d);
6333 unsigned int i, char_class_length, coll_symbol_length,
6334 equiv_class_length, ranges_length, chars_length, length;
6335 CHAR_T *workp, *workp2, *charset_top;
6336 #define WORK_BUFFER_SIZE 128
6337 CHAR_T str_buf[WORK_BUFFER_SIZE];
6342 boolean not = (re_opcode_t) *(p - 1) == charset_not;
6344 DEBUG_PRINT2 ("EXECUTING charset%s.\n", not ? "_not" : "");
6346 c = TRANSLATE (*d); /* The character to match. */
6349 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
6351 charset_top = p - 1;
6352 char_class_length = *p++;
6353 coll_symbol_length = *p++;
6354 equiv_class_length = *p++;
6355 ranges_length = *p++;
6356 chars_length = *p++;
6357 /* p points charset[6], so the address of the next instruction
6358 (charset[l+m+n+2o+k+p']) equals p[l+m+n+2*o+p'],
6359 where l=length of char_classes, m=length of collating_symbol,
6360 n=equivalence_class, o=length of char_range,
6361 p'=length of character. */
6363 /* Update p to indicate the next instruction. */
6364 p += char_class_length + coll_symbol_length+ equiv_class_length +
6365 2*ranges_length + chars_length;
6367 /* match with char_class? */
6368 for (i = 0; i < char_class_length ; i += CHAR_CLASS_SIZE)
6371 uintptr_t alignedp = ((uintptr_t)workp
6372 + __alignof__(wctype_t) - 1)
6373 & ~(uintptr_t)(__alignof__(wctype_t) - 1);
6374 wctype = *((wctype_t*)alignedp);
6375 workp += CHAR_CLASS_SIZE;
6377 if (__iswctype((wint_t)c, wctype))
6378 goto char_set_matched;
6380 if (iswctype((wint_t)c, wctype))
6381 goto char_set_matched;
6385 /* match with collating_symbol? */
6389 const unsigned char *extra = (const unsigned char *)
6390 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
6392 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;
6396 wextra = (int32_t*)(extra + *workp++);
6397 for (i = 0; i < *wextra; ++i)
6398 if (TRANSLATE(d[i]) != wextra[1 + i])
6403 /* Update d, however d will be incremented at
6404 char_set_matched:, we decrement d here. */
6406 goto char_set_matched;
6410 else /* (nrules == 0) */
6412 /* If we can't look up collation data, we use wcscoll
6415 for (workp2 = workp + coll_symbol_length ; workp < workp2 ;)
6417 const CHAR_T *backup_d = d, *backup_dend = dend;
6419 length = __wcslen (workp);
6421 length = wcslen (workp);
6424 /* If wcscoll(the collating symbol, whole string) > 0,
6425 any substring of the string never match with the
6426 collating symbol. */
6428 if (__wcscoll (workp, d) > 0)
6430 if (wcscoll (workp, d) > 0)
6433 workp += length + 1;
6437 /* First, we compare the collating symbol with
6438 the first character of the string.
6439 If it don't match, we add the next character to
6440 the compare buffer in turn. */
6441 for (i = 0 ; i < WORK_BUFFER_SIZE-1 ; i++, d++)
6446 if (dend == end_match_2)
6452 /* add next character to the compare buffer. */
6453 str_buf[i] = TRANSLATE(*d);
6454 str_buf[i+1] = '\0';
6457 match = __wcscoll (workp, str_buf);
6459 match = wcscoll (workp, str_buf);
6462 goto char_set_matched;
6465 /* (str_buf > workp) indicate (str_buf + X > workp),
6466 because for all X (str_buf + X > str_buf).
6467 So we don't need continue this loop. */
6470 /* Otherwise(str_buf < workp),
6471 (str_buf+next_character) may equals (workp).
6472 So we continue this loop. */
6477 workp += length + 1;
6480 /* match with equivalence_class? */
6484 const CHAR_T *backup_d = d, *backup_dend = dend;
6485 /* Try to match the equivalence class against
6486 those known to the collate implementation. */
6487 const int32_t *table;
6488 const int32_t *weights;
6489 const int32_t *extra;
6490 const int32_t *indirect;
6495 /* This #include defines a local function! */
6496 # include <locale/weightwc.h>
6498 table = (const int32_t *)
6499 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
6500 weights = (const wint_t *)
6501 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
6502 extra = (const wint_t *)
6503 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
6504 indirect = (const int32_t *)
6505 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
6507 /* Write 1 collating element to str_buf, and
6511 for (i = 0 ; idx2 == 0 && i < WORK_BUFFER_SIZE - 1; i++)
6513 cp = (wint_t*)str_buf;
6516 if (dend == end_match_2)
6521 str_buf[i] = TRANSLATE(*(d+i));
6522 str_buf[i+1] = '\0'; /* sentinel */
6523 idx2 = findidx ((const wint_t**)&cp);
6526 /* Update d, however d will be incremented at
6527 char_set_matched:, we decrement d here. */
6528 d = backup_d + ((wchar_t*)cp - (wchar_t*)str_buf - 1);
6531 if (dend == end_match_2)
6540 len = weights[idx2];
6542 for (workp2 = workp + equiv_class_length ; workp < workp2 ;
6545 idx = (int32_t)*workp;
6546 /* We already checked idx != 0 in regex_compile. */
6548 if (idx2 != 0 && len == weights[idx])
6551 while (cnt < len && (weights[idx + 1 + cnt]
6552 == weights[idx2 + 1 + cnt]))
6556 goto char_set_matched;
6563 else /* (nrules == 0) */
6565 /* If we can't look up collation data, we use wcscoll
6568 for (workp2 = workp + equiv_class_length ; workp < workp2 ;)
6570 const CHAR_T *backup_d = d, *backup_dend = dend;
6572 length = __wcslen (workp);
6574 length = wcslen (workp);
6577 /* If wcscoll(the collating symbol, whole string) > 0,
6578 any substring of the string never match with the
6579 collating symbol. */
6581 if (__wcscoll (workp, d) > 0)
6583 if (wcscoll (workp, d) > 0)
6586 workp += length + 1;
6590 /* First, we compare the equivalence class with
6591 the first character of the string.
6592 If it don't match, we add the next character to
6593 the compare buffer in turn. */
6594 for (i = 0 ; i < WORK_BUFFER_SIZE - 1 ; i++, d++)
6599 if (dend == end_match_2)
6605 /* add next character to the compare buffer. */
6606 str_buf[i] = TRANSLATE(*d);
6607 str_buf[i+1] = '\0';
6610 match = __wcscoll (workp, str_buf);
6612 match = wcscoll (workp, str_buf);
6616 goto char_set_matched;
6619 /* (str_buf > workp) indicate (str_buf + X > workp),
6620 because for all X (str_buf + X > str_buf).
6621 So we don't need continue this loop. */
6624 /* Otherwise(str_buf < workp),
6625 (str_buf+next_character) may equals (workp).
6626 So we continue this loop. */
6631 workp += length + 1;
6635 /* match with char_range? */
6639 uint32_t collseqval;
6640 const char *collseq = (const char *)
6641 _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
6643 collseqval = collseq_table_lookup (collseq, c);
6645 for (; workp < p - chars_length ;)
6647 uint32_t start_val, end_val;
6649 /* We already compute the collation sequence value
6650 of the characters (or collating symbols). */
6651 start_val = (uint32_t) *workp++; /* range_start */
6652 end_val = (uint32_t) *workp++; /* range_end */
6654 if (start_val <= collseqval && collseqval <= end_val)
6655 goto char_set_matched;
6661 /* We set range_start_char at str_buf[0], range_end_char
6662 at str_buf[4], and compared char at str_buf[2]. */
6667 for (; workp < p - chars_length ;)
6669 wchar_t *range_start_char, *range_end_char;
6671 /* match if (range_start_char <= c <= range_end_char). */
6673 /* If range_start(or end) < 0, we assume -range_start(end)
6674 is the offset of the collating symbol which is specified
6675 as the character of the range start(end). */
6679 range_start_char = charset_top - (*workp++);
6682 str_buf[0] = *workp++;
6683 range_start_char = str_buf;
6688 range_end_char = charset_top - (*workp++);
6691 str_buf[4] = *workp++;
6692 range_end_char = str_buf + 4;
6696 if (__wcscoll (range_start_char, str_buf+2) <= 0
6697 && __wcscoll (str_buf+2, range_end_char) <= 0)
6699 if (wcscoll (range_start_char, str_buf+2) <= 0
6700 && wcscoll (str_buf+2, range_end_char) <= 0)
6702 goto char_set_matched;
6706 /* match with char? */
6707 for (; workp < p ; workp++)
6709 goto char_set_matched;
6716 /* Cast to `unsigned' instead of `unsigned char' in case the
6717 bit list is a full 32 bytes long. */
6718 if (c < (unsigned) (*p * BYTEWIDTH)
6719 && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
6724 if (!not) goto fail;
6725 #undef WORK_BUFFER_SIZE
6727 SET_REGS_MATCHED ();
6733 /* The beginning of a group is represented by start_memory.
6734 The arguments are the register number in the next byte, and the
6735 number of groups inner to this one in the next. The text
6736 matched within the group is recorded (in the internal
6737 registers data structure) under the register number. */
6739 DEBUG_PRINT3 ("EXECUTING start_memory %ld (%ld):\n",
6740 (long int) *p, (long int) p[1]);
6742 /* Find out if this group can match the empty string. */
6743 p1 = p; /* To send to group_match_null_string_p. */
6745 if (REG_MATCH_NULL_STRING_P (reg_info[*p]) == MATCH_NULL_UNSET_VALUE)
6746 REG_MATCH_NULL_STRING_P (reg_info[*p])
6747 = PREFIX(group_match_null_string_p) (&p1, pend, reg_info);
6749 /* Save the position in the string where we were the last time
6750 we were at this open-group operator in case the group is
6751 operated upon by a repetition operator, e.g., with `(a*)*b'
6752 against `ab'; then we want to ignore where we are now in
6753 the string in case this attempt to match fails. */
6754 old_regstart[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6755 ? REG_UNSET (regstart[*p]) ? d : regstart[*p]
6757 DEBUG_PRINT2 (" old_regstart: %d\n",
6758 POINTER_TO_OFFSET (old_regstart[*p]));
6761 DEBUG_PRINT2 (" regstart: %d\n", POINTER_TO_OFFSET (regstart[*p]));
6763 IS_ACTIVE (reg_info[*p]) = 1;
6764 MATCHED_SOMETHING (reg_info[*p]) = 0;
6766 /* Clear this whenever we change the register activity status. */
6767 set_regs_matched_done = 0;
6769 /* This is the new highest active register. */
6770 highest_active_reg = *p;
6772 /* If nothing was active before, this is the new lowest active
6774 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
6775 lowest_active_reg = *p;
6777 /* Move past the register number and inner group count. */
6779 just_past_start_mem = p;
6784 /* The stop_memory opcode represents the end of a group. Its
6785 arguments are the same as start_memory's: the register
6786 number, and the number of inner groups. */
6788 DEBUG_PRINT3 ("EXECUTING stop_memory %ld (%ld):\n",
6789 (long int) *p, (long int) p[1]);
6791 /* We need to save the string position the last time we were at
6792 this close-group operator in case the group is operated
6793 upon by a repetition operator, e.g., with `((a*)*(b*)*)*'
6794 against `aba'; then we want to ignore where we are now in
6795 the string in case this attempt to match fails. */
6796 old_regend[*p] = REG_MATCH_NULL_STRING_P (reg_info[*p])
6797 ? REG_UNSET (regend[*p]) ? d : regend[*p]
6799 DEBUG_PRINT2 (" old_regend: %d\n",
6800 POINTER_TO_OFFSET (old_regend[*p]));
6803 DEBUG_PRINT2 (" regend: %d\n", POINTER_TO_OFFSET (regend[*p]));
6805 /* This register isn't active anymore. */
6806 IS_ACTIVE (reg_info[*p]) = 0;
6808 /* Clear this whenever we change the register activity status. */
6809 set_regs_matched_done = 0;
6811 /* If this was the only register active, nothing is active
6813 if (lowest_active_reg == highest_active_reg)
6815 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6816 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6819 { /* We must scan for the new highest active register, since
6820 it isn't necessarily one less than now: consider
6821 (a(b)c(d(e)f)g). When group 3 ends, after the f), the
6822 new highest active register is 1. */
6824 while (r > 0 && !IS_ACTIVE (reg_info[r]))
6827 /* If we end up at register zero, that means that we saved
6828 the registers as the result of an `on_failure_jump', not
6829 a `start_memory', and we jumped to past the innermost
6830 `stop_memory'. For example, in ((.)*) we save
6831 registers 1 and 2 as a result of the *, but when we pop
6832 back to the second ), we are at the stop_memory 1.
6833 Thus, nothing is active. */
6836 lowest_active_reg = NO_LOWEST_ACTIVE_REG;
6837 highest_active_reg = NO_HIGHEST_ACTIVE_REG;
6840 highest_active_reg = r;
6843 /* If just failed to match something this time around with a
6844 group that's operated on by a repetition operator, try to
6845 force exit from the ``loop'', and restore the register
6846 information for this group that we had before trying this
6848 if ((!MATCHED_SOMETHING (reg_info[*p])
6849 || just_past_start_mem == p - 1)
6852 boolean is_a_jump_n = false;
6856 switch ((re_opcode_t) *p1++)
6860 case pop_failure_jump:
6861 case maybe_pop_jump:
6863 case dummy_failure_jump:
6864 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6866 p1 += OFFSET_ADDRESS_SIZE;
6874 /* If the next operation is a jump backwards in the pattern
6875 to an on_failure_jump right before the start_memory
6876 corresponding to this stop_memory, exit from the loop
6877 by forcing a failure after pushing on the stack the
6878 on_failure_jump's jump in the pattern, and d. */
6879 if (mcnt < 0 && (re_opcode_t) *p1 == on_failure_jump
6880 && (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == start_memory
6881 && p1[2+OFFSET_ADDRESS_SIZE] == *p)
6883 /* If this group ever matched anything, then restore
6884 what its registers were before trying this last
6885 failed match, e.g., with `(a*)*b' against `ab' for
6886 regstart[1], and, e.g., with `((a*)*(b*)*)*'
6887 against `aba' for regend[3].
6889 Also restore the registers for inner groups for,
6890 e.g., `((a*)(b*))*' against `aba' (register 3 would
6891 otherwise get trashed). */
6893 if (EVER_MATCHED_SOMETHING (reg_info[*p]))
6897 EVER_MATCHED_SOMETHING (reg_info[*p]) = 0;
6899 /* Restore this and inner groups' (if any) registers. */
6900 for (r = *p; r < (unsigned) *p + (unsigned) *(p + 1);
6903 regstart[r] = old_regstart[r];
6905 /* xx why this test? */
6906 if (old_regend[r] >= regstart[r])
6907 regend[r] = old_regend[r];
6911 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
6912 PUSH_FAILURE_POINT (p1 + mcnt, d, -2);
6918 /* Move past the register number and the inner group count. */
6923 /* \<digit> has been turned into a `duplicate' command which is
6924 followed by the numeric value of <digit> as the register number. */
6927 register const CHAR_T *d2, *dend2;
6928 int regno = *p++; /* Get which register to match against. */
6929 DEBUG_PRINT2 ("EXECUTING duplicate %d.\n", regno);
6931 /* Can't back reference a group which we've never matched. */
6932 if (REG_UNSET (regstart[regno]) || REG_UNSET (regend[regno]))
6935 /* Where in input to try to start matching. */
6936 d2 = regstart[regno];
6938 /* Where to stop matching; if both the place to start and
6939 the place to stop matching are in the same string, then
6940 set to the place to stop, otherwise, for now have to use
6941 the end of the first string. */
6943 dend2 = ((FIRST_STRING_P (regstart[regno])
6944 == FIRST_STRING_P (regend[regno]))
6945 ? regend[regno] : end_match_1);
6948 /* If necessary, advance to next segment in register
6952 if (dend2 == end_match_2) break;
6953 if (dend2 == regend[regno]) break;
6955 /* End of string1 => advance to string2. */
6957 dend2 = regend[regno];
6959 /* At end of register contents => success */
6960 if (d2 == dend2) break;
6962 /* If necessary, advance to next segment in data. */
6965 /* How many characters left in this segment to match. */
6968 /* Want how many consecutive characters we can match in
6969 one shot, so, if necessary, adjust the count. */
6970 if (mcnt > dend2 - d2)
6973 /* Compare that many; failure if mismatch, else move
6976 ? PREFIX(bcmp_translate) (d, d2, mcnt, translate)
6977 : memcmp (d, d2, mcnt*sizeof(UCHAR_T)))
6979 d += mcnt, d2 += mcnt;
6981 /* Do this because we've match some characters. */
6982 SET_REGS_MATCHED ();
6988 /* begline matches the empty string at the beginning of the string
6989 (unless `not_bol' is set in `bufp'), and, if
6990 `newline_anchor' is set, after newlines. */
6992 DEBUG_PRINT1 ("EXECUTING begline.\n");
6994 if (AT_STRINGS_BEG (d))
6996 if (!bufp->not_bol) break;
6998 else if (d[-1] == '\n' && bufp->newline_anchor)
7002 /* In all other cases, we fail. */
7006 /* endline is the dual of begline. */
7008 DEBUG_PRINT1 ("EXECUTING endline.\n");
7010 if (AT_STRINGS_END (d))
7012 if (!bufp->not_eol) break;
7015 /* We have to ``prefetch'' the next character. */
7016 else if ((d == end1 ? *string2 : *d) == '\n'
7017 && bufp->newline_anchor)
7024 /* Match at the very beginning of the data. */
7026 DEBUG_PRINT1 ("EXECUTING begbuf.\n");
7027 if (AT_STRINGS_BEG (d))
7032 /* Match at the very end of the data. */
7034 DEBUG_PRINT1 ("EXECUTING endbuf.\n");
7035 if (AT_STRINGS_END (d))
7040 /* on_failure_keep_string_jump is used to optimize `.*\n'. It
7041 pushes NULL as the value for the string on the stack. Then
7042 `pop_failure_point' will keep the current value for the
7043 string, instead of restoring it. To see why, consider
7044 matching `foo\nbar' against `.*\n'. The .* matches the foo;
7045 then the . fails against the \n. But the next thing we want
7046 to do is match the \n against the \n; if we restored the
7047 string value, we would be back at the foo.
7049 Because this is used only in specific cases, we don't need to
7050 check all the things that `on_failure_jump' does, to make
7051 sure the right things get saved on the stack. Hence we don't
7052 share its code. The only reason to push anything on the
7053 stack at all is that otherwise we would have to change
7054 `anychar's code to do something besides goto fail in this
7055 case; that seems worse than this. */
7056 case on_failure_keep_string_jump:
7057 DEBUG_PRINT1 ("EXECUTING on_failure_keep_string_jump");
7059 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7061 DEBUG_PRINT3 (" %d (to %p):\n", mcnt, p + mcnt);
7063 DEBUG_PRINT3 (" %d (to 0x%x):\n", mcnt, p + mcnt);
7066 PUSH_FAILURE_POINT (p + mcnt, NULL, -2);
7070 /* Uses of on_failure_jump:
7072 Each alternative starts with an on_failure_jump that points
7073 to the beginning of the next alternative. Each alternative
7074 except the last ends with a jump that in effect jumps past
7075 the rest of the alternatives. (They really jump to the
7076 ending jump of the following alternative, because tensioning
7077 these jumps is a hassle.)
7079 Repeats start with an on_failure_jump that points past both
7080 the repetition text and either the following jump or
7081 pop_failure_jump back to this on_failure_jump. */
7082 case on_failure_jump:
7084 DEBUG_PRINT1 ("EXECUTING on_failure_jump");
7086 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7088 DEBUG_PRINT3 (" %d (to %p)", mcnt, p + mcnt);
7090 DEBUG_PRINT3 (" %d (to 0x%x)", mcnt, p + mcnt);
7093 /* If this on_failure_jump comes right before a group (i.e.,
7094 the original * applied to a group), save the information
7095 for that group and all inner ones, so that if we fail back
7096 to this point, the group's information will be correct.
7097 For example, in \(a*\)*\1, we need the preceding group,
7098 and in \(zz\(a*\)b*\)\2, we need the inner group. */
7100 /* We can't use `p' to check ahead because we push
7101 a failure point to `p + mcnt' after we do this. */
7104 /* We need to skip no_op's before we look for the
7105 start_memory in case this on_failure_jump is happening as
7106 the result of a completed succeed_n, as in \(a\)\{1,3\}b\1
7108 while (p1 < pend && (re_opcode_t) *p1 == no_op)
7111 if (p1 < pend && (re_opcode_t) *p1 == start_memory)
7113 /* We have a new highest active register now. This will
7114 get reset at the start_memory we are about to get to,
7115 but we will have saved all the registers relevant to
7116 this repetition op, as described above. */
7117 highest_active_reg = *(p1 + 1) + *(p1 + 2);
7118 if (lowest_active_reg == NO_LOWEST_ACTIVE_REG)
7119 lowest_active_reg = *(p1 + 1);
7122 DEBUG_PRINT1 (":\n");
7123 PUSH_FAILURE_POINT (p + mcnt, d, -2);
7127 /* A smart repeat ends with `maybe_pop_jump'.
7128 We change it to either `pop_failure_jump' or `jump'. */
7129 case maybe_pop_jump:
7130 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7131 DEBUG_PRINT2 ("EXECUTING maybe_pop_jump %d.\n", mcnt);
7133 register UCHAR_T *p2 = p;
7135 /* Compare the beginning of the repeat with what in the
7136 pattern follows its end. If we can establish that there
7137 is nothing that they would both match, i.e., that we
7138 would have to backtrack because of (as in, e.g., `a*a')
7139 then we can change to pop_failure_jump, because we'll
7140 never have to backtrack.
7142 This is not true in the case of alternatives: in
7143 `(a|ab)*' we do need to backtrack to the `ab' alternative
7144 (e.g., if the string was `ab'). But instead of trying to
7145 detect that here, the alternative has put on a dummy
7146 failure point which is what we will end up popping. */
7148 /* Skip over open/close-group commands.
7149 If what follows this loop is a ...+ construct,
7150 look at what begins its body, since we will have to
7151 match at least one of that. */
7155 && ((re_opcode_t) *p2 == stop_memory
7156 || (re_opcode_t) *p2 == start_memory))
7158 else if (p2 + 2 + 2 * OFFSET_ADDRESS_SIZE < pend
7159 && (re_opcode_t) *p2 == dummy_failure_jump)
7160 p2 += 2 + 2 * OFFSET_ADDRESS_SIZE;
7166 /* p1[0] ... p1[2] are the `on_failure_jump' corresponding
7167 to the `maybe_finalize_jump' of this case. Examine what
7170 /* If we're at the end of the pattern, we can change. */
7173 /* Consider what happens when matching ":\(.*\)"
7174 against ":/". I don't really understand this code
7176 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7179 (" End of pattern: change to `pop_failure_jump'.\n");
7182 else if ((re_opcode_t) *p2 == exactn
7184 || (re_opcode_t) *p2 == exactn_bin
7186 || (bufp->newline_anchor && (re_opcode_t) *p2 == endline))
7189 = *p2 == (UCHAR_T) endline ? '\n' : p2[2];
7191 if (((re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn
7193 || (re_opcode_t) p1[1+OFFSET_ADDRESS_SIZE] == exactn_bin
7195 ) && p1[3+OFFSET_ADDRESS_SIZE] != c)
7197 p[-(1+OFFSET_ADDRESS_SIZE)] = (UCHAR_T)
7200 DEBUG_PRINT3 (" %C != %C => pop_failure_jump.\n",
7202 (wint_t) p1[3+OFFSET_ADDRESS_SIZE]);
7204 DEBUG_PRINT3 (" %c != %c => pop_failure_jump.\n",
7206 (char) p1[3+OFFSET_ADDRESS_SIZE]);
7211 else if ((re_opcode_t) p1[3] == charset
7212 || (re_opcode_t) p1[3] == charset_not)
7214 int not = (re_opcode_t) p1[3] == charset_not;
7216 if (c < (unsigned) (p1[4] * BYTEWIDTH)
7217 && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
7220 /* `not' is equal to 1 if c would match, which means
7221 that we can't change to pop_failure_jump. */
7224 p[-3] = (unsigned char) pop_failure_jump;
7225 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7228 #endif /* not WCHAR */
7231 else if ((re_opcode_t) *p2 == charset)
7233 /* We win if the first character of the loop is not part
7235 if ((re_opcode_t) p1[3] == exactn
7236 && ! ((int) p2[1] * BYTEWIDTH > (int) p1[5]
7237 && (p2[2 + p1[5] / BYTEWIDTH]
7238 & (1 << (p1[5] % BYTEWIDTH)))))
7240 p[-3] = (unsigned char) pop_failure_jump;
7241 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7244 else if ((re_opcode_t) p1[3] == charset_not)
7247 /* We win if the charset_not inside the loop
7248 lists every character listed in the charset after. */
7249 for (idx = 0; idx < (int) p2[1]; idx++)
7250 if (! (p2[2 + idx] == 0
7251 || (idx < (int) p1[4]
7252 && ((p2[2 + idx] & ~ p1[5 + idx]) == 0))))
7257 p[-3] = (unsigned char) pop_failure_jump;
7258 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7261 else if ((re_opcode_t) p1[3] == charset)
7264 /* We win if the charset inside the loop
7265 has no overlap with the one after the loop. */
7267 idx < (int) p2[1] && idx < (int) p1[4];
7269 if ((p2[2 + idx] & p1[5 + idx]) != 0)
7272 if (idx == p2[1] || idx == p1[4])
7274 p[-3] = (unsigned char) pop_failure_jump;
7275 DEBUG_PRINT1 (" No match => pop_failure_jump.\n");
7279 #endif /* not WCHAR */
7281 p -= OFFSET_ADDRESS_SIZE; /* Point at relative address again. */
7282 if ((re_opcode_t) p[-1] != pop_failure_jump)
7284 p[-1] = (UCHAR_T) jump;
7285 DEBUG_PRINT1 (" Match => jump.\n");
7286 goto unconditional_jump;
7288 /* Note fall through. */
7291 /* The end of a simple repeat has a pop_failure_jump back to
7292 its matching on_failure_jump, where the latter will push a
7293 failure point. The pop_failure_jump takes off failure
7294 points put on by this pop_failure_jump's matching
7295 on_failure_jump; we got through the pattern to here from the
7296 matching on_failure_jump, so didn't fail. */
7297 case pop_failure_jump:
7299 /* We need to pass separate storage for the lowest and
7300 highest registers, even though we don't care about the
7301 actual values. Otherwise, we will restore only one
7302 register from the stack, since lowest will == highest in
7303 `pop_failure_point'. */
7304 active_reg_t dummy_low_reg, dummy_high_reg;
7305 UCHAR_T *pdummy = NULL;
7306 const CHAR_T *sdummy = NULL;
7308 DEBUG_PRINT1 ("EXECUTING pop_failure_jump.\n");
7309 POP_FAILURE_POINT (sdummy, pdummy,
7310 dummy_low_reg, dummy_high_reg,
7311 reg_dummy, reg_dummy, reg_info_dummy);
7313 /* Note fall through. */
7317 DEBUG_PRINT2 ("\n%p: ", p);
7319 DEBUG_PRINT2 ("\n0x%x: ", p);
7321 /* Note fall through. */
7323 /* Unconditionally jump (without popping any failure points). */
7325 EXTRACT_NUMBER_AND_INCR (mcnt, p); /* Get the amount to jump. */
7326 DEBUG_PRINT2 ("EXECUTING jump %d ", mcnt);
7327 p += mcnt; /* Do the jump. */
7329 DEBUG_PRINT2 ("(to %p).\n", p);
7331 DEBUG_PRINT2 ("(to 0x%x).\n", p);
7336 /* We need this opcode so we can detect where alternatives end
7337 in `group_match_null_string_p' et al. */
7339 DEBUG_PRINT1 ("EXECUTING jump_past_alt.\n");
7340 goto unconditional_jump;
7343 /* Normally, the on_failure_jump pushes a failure point, which
7344 then gets popped at pop_failure_jump. We will end up at
7345 pop_failure_jump, also, and with a pattern of, say, `a+', we
7346 are skipping over the on_failure_jump, so we have to push
7347 something meaningless for pop_failure_jump to pop. */
7348 case dummy_failure_jump:
7349 DEBUG_PRINT1 ("EXECUTING dummy_failure_jump.\n");
7350 /* It doesn't matter what we push for the string here. What
7351 the code at `fail' tests is the value for the pattern. */
7352 PUSH_FAILURE_POINT (NULL, NULL, -2);
7353 goto unconditional_jump;
7356 /* At the end of an alternative, we need to push a dummy failure
7357 point in case we are followed by a `pop_failure_jump', because
7358 we don't want the failure point for the alternative to be
7359 popped. For example, matching `(a|ab)*' against `aab'
7360 requires that we match the `ab' alternative. */
7361 case push_dummy_failure:
7362 DEBUG_PRINT1 ("EXECUTING push_dummy_failure.\n");
7363 /* See comments just above at `dummy_failure_jump' about the
7365 PUSH_FAILURE_POINT (NULL, NULL, -2);
7368 /* Have to succeed matching what follows at least n times.
7369 After that, handle like `on_failure_jump'. */
7371 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7372 DEBUG_PRINT2 ("EXECUTING succeed_n %d.\n", mcnt);
7375 /* Originally, this is how many times we HAVE to succeed. */
7379 p += OFFSET_ADDRESS_SIZE;
7380 STORE_NUMBER_AND_INCR (p, mcnt);
7382 DEBUG_PRINT3 (" Setting %p to %d.\n", p - OFFSET_ADDRESS_SIZE
7385 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p - OFFSET_ADDRESS_SIZE
7392 DEBUG_PRINT2 (" Setting two bytes from %p to no_op.\n",
7393 p + OFFSET_ADDRESS_SIZE);
7395 DEBUG_PRINT2 (" Setting two bytes from 0x%x to no_op.\n",
7396 p + OFFSET_ADDRESS_SIZE);
7400 p[1] = (UCHAR_T) no_op;
7402 p[2] = (UCHAR_T) no_op;
7403 p[3] = (UCHAR_T) no_op;
7410 EXTRACT_NUMBER (mcnt, p + OFFSET_ADDRESS_SIZE);
7411 DEBUG_PRINT2 ("EXECUTING jump_n %d.\n", mcnt);
7413 /* Originally, this is how many times we CAN jump. */
7417 STORE_NUMBER (p + OFFSET_ADDRESS_SIZE, mcnt);
7420 DEBUG_PRINT3 (" Setting %p to %d.\n", p + OFFSET_ADDRESS_SIZE,
7423 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p + OFFSET_ADDRESS_SIZE,
7426 goto unconditional_jump;
7428 /* If don't have to jump any more, skip over the rest of command. */
7430 p += 2 * OFFSET_ADDRESS_SIZE;
7435 DEBUG_PRINT1 ("EXECUTING set_number_at.\n");
7437 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7439 EXTRACT_NUMBER_AND_INCR (mcnt, p);
7441 DEBUG_PRINT3 (" Setting %p to %d.\n", p1, mcnt);
7443 DEBUG_PRINT3 (" Setting 0x%x to %d.\n", p1, mcnt);
7445 STORE_NUMBER (p1, mcnt);
7450 /* The DEC Alpha C compiler 3.x generates incorrect code for the
7451 test WORDCHAR_P (d - 1) != WORDCHAR_P (d) in the expansion of
7452 AT_WORD_BOUNDARY, so this code is disabled. Expanding the
7453 macro and introducing temporary variables works around the bug. */
7456 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7457 if (AT_WORD_BOUNDARY (d))
7462 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7463 if (AT_WORD_BOUNDARY (d))
7469 boolean prevchar, thischar;
7471 DEBUG_PRINT1 ("EXECUTING wordbound.\n");
7472 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7475 prevchar = WORDCHAR_P (d - 1);
7476 thischar = WORDCHAR_P (d);
7477 if (prevchar != thischar)
7484 boolean prevchar, thischar;
7486 DEBUG_PRINT1 ("EXECUTING notwordbound.\n");
7487 if (AT_STRINGS_BEG (d) || AT_STRINGS_END (d))
7490 prevchar = WORDCHAR_P (d - 1);
7491 thischar = WORDCHAR_P (d);
7492 if (prevchar != thischar)
7499 DEBUG_PRINT1 ("EXECUTING wordbeg.\n");
7500 if (!AT_STRINGS_END (d) && WORDCHAR_P (d)
7501 && (AT_STRINGS_BEG (d) || !WORDCHAR_P (d - 1)))
7506 DEBUG_PRINT1 ("EXECUTING wordend.\n");
7507 if (!AT_STRINGS_BEG (d) && WORDCHAR_P (d - 1)
7508 && (AT_STRINGS_END (d) || !WORDCHAR_P (d)))
7514 DEBUG_PRINT1 ("EXECUTING before_dot.\n");
7515 if (PTR_CHAR_POS ((unsigned char *) d) >= point)
7520 DEBUG_PRINT1 ("EXECUTING at_dot.\n");
7521 if (PTR_CHAR_POS ((unsigned char *) d) != point)
7526 DEBUG_PRINT1 ("EXECUTING after_dot.\n");
7527 if (PTR_CHAR_POS ((unsigned char *) d) <= point)
7532 DEBUG_PRINT2 ("EXECUTING syntaxspec %d.\n", mcnt);
7537 DEBUG_PRINT1 ("EXECUTING Emacs wordchar.\n");
7541 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7543 if (SYNTAX (d[-1]) != (enum syntaxcode) mcnt)
7545 SET_REGS_MATCHED ();
7549 DEBUG_PRINT2 ("EXECUTING notsyntaxspec %d.\n", mcnt);
7551 goto matchnotsyntax;
7554 DEBUG_PRINT1 ("EXECUTING Emacs notwordchar.\n");
7558 /* Can't use *d++ here; SYNTAX may be an unsafe macro. */
7560 if (SYNTAX (d[-1]) == (enum syntaxcode) mcnt)
7562 SET_REGS_MATCHED ();
7565 #else /* not emacs */
7567 DEBUG_PRINT1 ("EXECUTING non-Emacs wordchar.\n");
7569 if (!WORDCHAR_P (d))
7571 SET_REGS_MATCHED ();
7576 DEBUG_PRINT1 ("EXECUTING non-Emacs notwordchar.\n");
7580 SET_REGS_MATCHED ();
7583 #endif /* not emacs */
7588 continue; /* Successfully executed one pattern command; keep going. */
7591 /* We goto here if a matching operation fails. */
7593 if (!FAIL_STACK_EMPTY ())
7594 { /* A restart point is known. Restore to that state. */
7595 DEBUG_PRINT1 ("\nFAIL:\n");
7596 POP_FAILURE_POINT (d, p,
7597 lowest_active_reg, highest_active_reg,
7598 regstart, regend, reg_info);
7600 /* If this failure point is a dummy, try the next one. */
7604 /* If we failed to the end of the pattern, don't examine *p. */
7608 boolean is_a_jump_n = false;
7610 /* If failed to a backwards jump that's part of a repetition
7611 loop, need to pop this failure point and use the next one. */
7612 switch ((re_opcode_t) *p)
7616 case maybe_pop_jump:
7617 case pop_failure_jump:
7620 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7623 if ((is_a_jump_n && (re_opcode_t) *p1 == succeed_n)
7625 && (re_opcode_t) *p1 == on_failure_jump))
7633 if (d >= string1 && d <= end1)
7637 break; /* Matching at this starting point really fails. */
7641 goto restore_best_regs;
7645 return -1; /* Failure to match. */
7648 /* Subroutine definitions for re_match_2. */
7651 /* We are passed P pointing to a register number after a start_memory.
7653 Return true if the pattern up to the corresponding stop_memory can
7654 match the empty string, and false otherwise.
7656 If we find the matching stop_memory, sets P to point to one past its number.
7657 Otherwise, sets P to an undefined byte less than or equal to END.
7659 We don't handle duplicates properly (yet). */
7662 PREFIX(group_match_null_string_p) (p, end, reg_info)
7664 PREFIX(register_info_type) *reg_info;
7667 /* Point to after the args to the start_memory. */
7668 UCHAR_T *p1 = *p + 2;
7672 /* Skip over opcodes that can match nothing, and return true or
7673 false, as appropriate, when we get to one that can't, or to the
7674 matching stop_memory. */
7676 switch ((re_opcode_t) *p1)
7678 /* Could be either a loop or a series of alternatives. */
7679 case on_failure_jump:
7681 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7683 /* If the next operation is not a jump backwards in the
7688 /* Go through the on_failure_jumps of the alternatives,
7689 seeing if any of the alternatives cannot match nothing.
7690 The last alternative starts with only a jump,
7691 whereas the rest start with on_failure_jump and end
7692 with a jump, e.g., here is the pattern for `a|b|c':
7694 /on_failure_jump/0/6/exactn/1/a/jump_past_alt/0/6
7695 /on_failure_jump/0/6/exactn/1/b/jump_past_alt/0/3
7698 So, we have to first go through the first (n-1)
7699 alternatives and then deal with the last one separately. */
7702 /* Deal with the first (n-1) alternatives, which start
7703 with an on_failure_jump (see above) that jumps to right
7704 past a jump_past_alt. */
7706 while ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] ==
7709 /* `mcnt' holds how many bytes long the alternative
7710 is, including the ending `jump_past_alt' and
7713 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt -
7714 (1 + OFFSET_ADDRESS_SIZE),
7718 /* Move to right after this alternative, including the
7722 /* Break if it's the beginning of an n-th alternative
7723 that doesn't begin with an on_failure_jump. */
7724 if ((re_opcode_t) *p1 != on_failure_jump)
7727 /* Still have to check that it's not an n-th
7728 alternative that starts with an on_failure_jump. */
7730 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7731 if ((re_opcode_t) p1[mcnt-(1+OFFSET_ADDRESS_SIZE)] !=
7734 /* Get to the beginning of the n-th alternative. */
7735 p1 -= 1 + OFFSET_ADDRESS_SIZE;
7740 /* Deal with the last alternative: go back and get number
7741 of the `jump_past_alt' just before it. `mcnt' contains
7742 the length of the alternative. */
7743 EXTRACT_NUMBER (mcnt, p1 - OFFSET_ADDRESS_SIZE);
7745 if (!PREFIX(alt_match_null_string_p) (p1, p1 + mcnt, reg_info))
7748 p1 += mcnt; /* Get past the n-th alternative. */
7754 assert (p1[1] == **p);
7760 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7763 } /* while p1 < end */
7766 } /* group_match_null_string_p */
7769 /* Similar to group_match_null_string_p, but doesn't deal with alternatives:
7770 It expects P to be the first byte of a single alternative and END one
7771 byte past the last. The alternative can contain groups. */
7774 PREFIX(alt_match_null_string_p) (p, end, reg_info)
7776 PREFIX(register_info_type) *reg_info;
7783 /* Skip over opcodes that can match nothing, and break when we get
7784 to one that can't. */
7786 switch ((re_opcode_t) *p1)
7789 case on_failure_jump:
7791 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7796 if (!PREFIX(common_op_match_null_string_p) (&p1, end, reg_info))
7799 } /* while p1 < end */
7802 } /* alt_match_null_string_p */
7805 /* Deals with the ops common to group_match_null_string_p and
7806 alt_match_null_string_p.
7808 Sets P to one after the op and its arguments, if any. */
7811 PREFIX(common_op_match_null_string_p) (p, end, reg_info)
7813 PREFIX(register_info_type) *reg_info;
7820 switch ((re_opcode_t) *p1++)
7840 assert (reg_no > 0 && reg_no <= MAX_REGNUM);
7841 ret = PREFIX(group_match_null_string_p) (&p1, end, reg_info);
7843 /* Have to set this here in case we're checking a group which
7844 contains a group and a back reference to it. */
7846 if (REG_MATCH_NULL_STRING_P (reg_info[reg_no]) == MATCH_NULL_UNSET_VALUE)
7847 REG_MATCH_NULL_STRING_P (reg_info[reg_no]) = ret;
7853 /* If this is an optimized succeed_n for zero times, make the jump. */
7855 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7863 /* Get to the number of times to succeed. */
7864 p1 += OFFSET_ADDRESS_SIZE;
7865 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7869 p1 -= 2 * OFFSET_ADDRESS_SIZE;
7870 EXTRACT_NUMBER_AND_INCR (mcnt, p1);
7878 if (!REG_MATCH_NULL_STRING_P (reg_info[*p1]))
7883 p1 += 2 * OFFSET_ADDRESS_SIZE;
7886 /* All other opcodes mean we cannot match the empty string. */
7892 } /* common_op_match_null_string_p */
7895 /* Return zero if TRANSLATE[S1] and TRANSLATE[S2] are identical for LEN
7896 bytes; nonzero otherwise. */
7899 PREFIX(bcmp_translate) (s1, s2, len, translate)
7900 const CHAR_T *s1, *s2;
7902 RE_TRANSLATE_TYPE translate;
7904 register const UCHAR_T *p1 = (const UCHAR_T *) s1;
7905 register const UCHAR_T *p2 = (const UCHAR_T *) s2;
7909 if (((*p1<=0xff)?translate[*p1++]:*p1++)
7910 != ((*p2<=0xff)?translate[*p2++]:*p2++))
7913 if (translate[*p1++] != translate[*p2++]) return 1;
7921 #else /* not INSIDE_RECURSION */
7923 /* Entry points for GNU code. */
7925 /* re_compile_pattern is the GNU regular expression compiler: it
7926 compiles PATTERN (of length SIZE) and puts the result in BUFP.
7927 Returns 0 if the pattern was valid, otherwise an error string.
7929 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
7930 are set in BUFP on entry.
7932 We call regex_compile to do the actual compilation. */
7935 re_compile_pattern (pattern, length, bufp)
7936 const char *pattern;
7938 struct re_pattern_buffer *bufp;
7942 /* GNU code is written to assume at least RE_NREGS registers will be set
7943 (and at least one extra will be -1). */
7944 bufp->regs_allocated = REGS_UNALLOCATED;
7946 /* And GNU code determines whether or not to get register information
7947 by passing null for the REGS argument to re_match, etc., not by
7951 /* Match anchors at newline. */
7952 bufp->newline_anchor = 1;
7955 if (MB_CUR_MAX != 1)
7956 ret = wcs_regex_compile (pattern, length, re_syntax_options, bufp);
7959 ret = byte_regex_compile (pattern, length, re_syntax_options, bufp);
7963 return gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
7966 weak_alias (__re_compile_pattern, re_compile_pattern)
7969 /* Entry points compatible with 4.2 BSD regex library. We don't define
7970 them unless specifically requested. */
7972 #if defined _REGEX_RE_COMP || defined _LIBC
7974 /* BSD has one and only one pattern buffer. */
7975 static struct re_pattern_buffer re_comp_buf;
7979 /* Make these definitions weak in libc, so POSIX programs can redefine
7980 these names if they don't use our functions, and still use
7981 regcomp/regexec below without link errors. */
7991 if (!re_comp_buf.buffer)
7992 return gettext ("No previous regular expression");
7996 if (!re_comp_buf.buffer)
7998 re_comp_buf.buffer = (unsigned char *) malloc (200);
7999 if (re_comp_buf.buffer == NULL)
8000 return (char *) gettext (re_error_msgid
8001 + re_error_msgid_idx[(int) REG_ESPACE]);
8002 re_comp_buf.allocated = 200;
8004 re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH);
8005 if (re_comp_buf.fastmap == NULL)
8006 return (char *) gettext (re_error_msgid
8007 + re_error_msgid_idx[(int) REG_ESPACE]);
8010 /* Since `re_exec' always passes NULL for the `regs' argument, we
8011 don't need to initialize the pattern buffer fields which affect it. */
8013 /* Match anchors at newlines. */
8014 re_comp_buf.newline_anchor = 1;
8017 if (MB_CUR_MAX != 1)
8018 ret = wcs_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
8021 ret = byte_regex_compile (s, strlen (s), re_syntax_options, &re_comp_buf);
8026 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
8027 return (char *) gettext (re_error_msgid + re_error_msgid_idx[(int) ret]);
8038 const int len = strlen (s);
8040 0 <= re_search (&re_comp_buf, s, len, 0, len, (struct re_registers *) 0);
8043 #endif /* _REGEX_RE_COMP */
8045 /* POSIX.2 functions. Don't define these for Emacs. */
8049 /* regcomp takes a regular expression as a string and compiles it.
8051 PREG is a regex_t *. We do not expect any fields to be initialized,
8052 since POSIX says we shouldn't. Thus, we set
8054 `buffer' to the compiled pattern;
8055 `used' to the length of the compiled pattern;
8056 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
8057 REG_EXTENDED bit in CFLAGS is set; otherwise, to
8058 RE_SYNTAX_POSIX_BASIC;
8059 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
8060 `fastmap' to an allocated space for the fastmap;
8061 `fastmap_accurate' to zero;
8062 `re_nsub' to the number of subexpressions in PATTERN.
8064 PATTERN is the address of the pattern string.
8066 CFLAGS is a series of bits which affect compilation.
8068 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
8069 use POSIX basic syntax.
8071 If REG_NEWLINE is set, then . and [^...] don't match newline.
8072 Also, regexec will try a match beginning after every newline.
8074 If REG_ICASE is set, then we considers upper- and lowercase
8075 versions of letters to be equivalent when matching.
8077 If REG_NOSUB is set, then when PREG is passed to regexec, that
8078 routine will report only success or failure, and nothing about the
8081 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
8082 the return codes and their meanings.) */
8085 regcomp (preg, pattern, cflags)
8087 const char *pattern;
8092 = (cflags & REG_EXTENDED) ?
8093 RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
8095 /* regex_compile will allocate the space for the compiled pattern. */
8097 preg->allocated = 0;
8100 /* Try to allocate space for the fastmap. */
8101 preg->fastmap = (char *) malloc (1 << BYTEWIDTH);
8103 if (cflags & REG_ICASE)
8108 = (RE_TRANSLATE_TYPE) malloc (CHAR_SET_SIZE
8109 * sizeof (*(RE_TRANSLATE_TYPE)0));
8110 if (preg->translate == NULL)
8111 return (int) REG_ESPACE;
8113 /* Map uppercase characters to corresponding lowercase ones. */
8114 for (i = 0; i < CHAR_SET_SIZE; i++)
8115 preg->translate[i] = ISUPPER (i) ? TOLOWER (i) : i;
8118 preg->translate = NULL;
8120 /* If REG_NEWLINE is set, newlines are treated differently. */
8121 if (cflags & REG_NEWLINE)
8122 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
8123 syntax &= ~RE_DOT_NEWLINE;
8124 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
8125 /* It also changes the matching behavior. */
8126 preg->newline_anchor = 1;
8129 preg->newline_anchor = 0;
8131 preg->no_sub = !!(cflags & REG_NOSUB);
8133 /* POSIX says a null character in the pattern terminates it, so we
8134 can use strlen here in compiling the pattern. */
8136 if (MB_CUR_MAX != 1)
8137 ret = wcs_regex_compile (pattern, strlen (pattern), syntax, preg);
8140 ret = byte_regex_compile (pattern, strlen (pattern), syntax, preg);
8142 /* POSIX doesn't distinguish between an unmatched open-group and an
8143 unmatched close-group: both are REG_EPAREN. */
8144 if (ret == REG_ERPAREN) ret = REG_EPAREN;
8146 if (ret == REG_NOERROR && preg->fastmap)
8148 /* Compute the fastmap now, since regexec cannot modify the pattern
8150 if (re_compile_fastmap (preg) == -2)
8152 /* Some error occurred while computing the fastmap, just forget
8154 free (preg->fastmap);
8155 preg->fastmap = NULL;
8162 weak_alias (__regcomp, regcomp)
8166 /* regexec searches for a given pattern, specified by PREG, in the
8169 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
8170 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
8171 least NMATCH elements, and we set them to the offsets of the
8172 corresponding matched substrings.
8174 EFLAGS specifies `execution flags' which affect matching: if
8175 REG_NOTBOL is set, then ^ does not match at the beginning of the
8176 string; if REG_NOTEOL is set, then $ does not match at the end.
8178 We return 0 if we find a match and REG_NOMATCH if not. */
8181 regexec (preg, string, nmatch, pmatch, eflags)
8182 const regex_t *preg;
8185 regmatch_t pmatch[];
8189 struct re_registers regs;
8190 regex_t private_preg;
8191 int len = strlen (string);
8192 boolean want_reg_info = !preg->no_sub && nmatch > 0;
8194 private_preg = *preg;
8196 private_preg.not_bol = !!(eflags & REG_NOTBOL);
8197 private_preg.not_eol = !!(eflags & REG_NOTEOL);
8199 /* The user has told us exactly how many registers to return
8200 information about, via `nmatch'. We have to pass that on to the
8201 matching routines. */
8202 private_preg.regs_allocated = REGS_FIXED;
8206 regs.num_regs = nmatch;
8207 regs.start = TALLOC (nmatch * 2, regoff_t);
8208 if (regs.start == NULL)
8209 return (int) REG_NOMATCH;
8210 regs.end = regs.start + nmatch;
8213 /* Perform the searching operation. */
8214 ret = re_search (&private_preg, string, len,
8215 /* start: */ 0, /* range: */ len,
8216 want_reg_info ? ®s : (struct re_registers *) 0);
8218 /* Copy the register information to the POSIX structure. */
8225 for (r = 0; r < nmatch; r++)
8227 pmatch[r].rm_so = regs.start[r];
8228 pmatch[r].rm_eo = regs.end[r];
8232 /* If we needed the temporary register info, free the space now. */
8236 /* We want zero return to mean success, unlike `re_search'. */
8237 return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
8240 weak_alias (__regexec, regexec)
8244 /* Returns a message corresponding to an error code, ERRCODE, returned
8245 from either regcomp or regexec. We don't use PREG here. */
8248 regerror (errcode, preg, errbuf, errbuf_size)
8250 const regex_t *preg;
8258 || errcode >= (int) (sizeof (re_error_msgid_idx)
8259 / sizeof (re_error_msgid_idx[0])))
8260 /* Only error codes returned by the rest of the code should be passed
8261 to this routine. If we are given anything else, or if other regex
8262 code generates an invalid error code, then the program has a bug.
8263 Dump core so we can fix it. */
8266 msg = gettext (re_error_msgid + re_error_msgid_idx[errcode]);
8268 msg_size = strlen (msg) + 1; /* Includes the null. */
8270 if (errbuf_size != 0)
8272 if (msg_size > errbuf_size)
8274 #if defined HAVE_MEMPCPY || defined _LIBC
8275 *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
8277 memcpy (errbuf, msg, errbuf_size - 1);
8278 errbuf[errbuf_size - 1] = 0;
8282 memcpy (errbuf, msg, msg_size);
8288 weak_alias (__regerror, regerror)
8292 /* Free dynamically allocated space used by PREG. */
8298 if (preg->buffer != NULL)
8299 free (preg->buffer);
8300 preg->buffer = NULL;
8302 preg->allocated = 0;
8305 if (preg->fastmap != NULL)
8306 free (preg->fastmap);
8307 preg->fastmap = NULL;
8308 preg->fastmap_accurate = 0;
8310 if (preg->translate != NULL)
8311 free (preg->translate);
8312 preg->translate = NULL;
8315 weak_alias (__regfree, regfree)
8318 #endif /* not emacs */
8320 #endif /* not INSIDE_RECURSION */
8324 #undef STORE_NUMBER_AND_INCR
8325 #undef EXTRACT_NUMBER
8326 #undef EXTRACT_NUMBER_AND_INCR
8328 #undef DEBUG_PRINT_COMPILED_PATTERN
8329 #undef DEBUG_PRINT_DOUBLE_STRING
8331 #undef INIT_FAIL_STACK
8332 #undef RESET_FAIL_STACK
8333 #undef DOUBLE_FAIL_STACK
8334 #undef PUSH_PATTERN_OP
8335 #undef PUSH_FAILURE_POINTER
8336 #undef PUSH_FAILURE_INT
8337 #undef PUSH_FAILURE_ELT
8338 #undef POP_FAILURE_POINTER
8339 #undef POP_FAILURE_INT
8340 #undef POP_FAILURE_ELT
8343 #undef PUSH_FAILURE_POINT
8344 #undef POP_FAILURE_POINT
8346 #undef REG_UNSET_VALUE
8354 #undef INIT_BUF_SIZE
8355 #undef GET_BUFFER_SPACE
8363 #undef EXTEND_BUFFER
8364 #undef GET_UNSIGNED_NUMBER
8365 #undef FREE_STACK_RETURN
8367 # undef POINTER_TO_OFFSET
8368 # undef MATCHING_IN_FRST_STRING
8370 # undef AT_STRINGS_BEG
8371 # undef AT_STRINGS_END
8374 # undef FREE_VARIABLES
8375 # undef NO_HIGHEST_ACTIVE_REG
8376 # undef NO_LOWEST_ACTIVE_REG
8380 # undef COMPILED_BUFFER_VAR
8381 # undef OFFSET_ADDRESS_SIZE
8382 # undef CHAR_CLASS_SIZE
8389 # define DEFINED_ONCE